TL, DR: Wydaje się, że wbrew często powtarzanym zaleceniom, krzyżowa walidacja typu „jeden do jednego” (LOO-CV) - to znaczy,krotnie CV z(liczbą fałdów) równą(liczba obserwacji treningowych) - daje oszacowania błędu uogólnienia, które są najmniej zmienne dla dowolnego, a nie najbardziej zmienne, przy założeniu pewnegowarunku stabilności w modelu / algorytmie, zestawie danych lub w obu (nie jestem pewien, który jest poprawny, ponieważ tak naprawdę nie rozumiem tego warunku stabilności).K N $K$$K$$N$$K$

• Czy ktoś może jasno wyjaśnić, czym dokładnie jest ten warunek stabilności?
• Czy to prawda, że ​​regresja liniowa jest jednym z takich „stabilnych” algorytmów, co sugeruje, że w tym kontekście LOO-CV jest ściśle najlepszym wyborem CV, jeśli chodzi o stronniczość i wariancję szacunków błędu uogólnienia?

Tradycyjna mądrość mówi, że wybór w krotnym CV wynika z kompromisu wariancji odchylenia, takie niższe wartości (zbliżające się do 2) prowadzą do oszacowań błędu uogólnienia, które mają bardziej pesymistyczne nastawienie, ale mniejszą wariancję, podczas gdy wyższe wartości z (zbliżający się do ) prowadzi do oszacowań, które są mniej stronnicze, ale z większą wariancją. Konwencjonalne wyjaśnienie tego zjawiska wariancji narastającego wraz z jest być może najbardziej widoczne w Elementach uczenia statystycznego (Rozdział 7.10.1):K K K N $K$$K$$K$$K$$N$$K$

Przy K = N estymator krzyżowej walidacji jest w przybliżeniu bezstronny w odniesieniu do prawdziwego (oczekiwanego) błędu prognozowania, ale może wykazywać dużą wariancję, ponieważ N „zestawów treningowych” jest do siebie bardzo podobnych.

Oznacza to, że błędy walidacji są bardziej skorelowane, dzięki czemu ich suma jest bardziej zmienna. Ten tok rozumowania został powtórzony w wielu odpowiedziach na tej stronie (np. Tutaj , tutaj , tutaj , tutaj , tutaj , tutaj i tutaj ), a także na różnych blogach itp. Ale zamiast tego nigdy nie podano szczegółowej analizy tylko intuicja lub krótki szkic tego, jak może wyglądać analiza.$N$

Można jednak znaleźć sprzeczne stwierdzenia, zwykle powołując się na pewien warunek „stabilności”, którego tak naprawdę nie rozumiem. Na przykład w tej sprzecznej odpowiedzi przytacza się kilka akapitów z dokumentu z 2015 r., Który mówi między innymi: „W przypadku modeli / procedur modelowania o niskiej niestabilności , LOO często ma najmniejszą zmienność” (podkreślenie dodane). Ten artykuł (sekcja 5.2) wydaje się zgadzać, że LOO reprezentuje najmniej zmienny wybór o ile model / algorytm jest „stabilny”. Jeśli chodzi o jeszcze inne stanowisko w tej sprawie, istnieje również ten artykuł (Wniosek 2), który mówi: „Wariacja walidacji krzyżowej krotności [...] nie zależy odk $K$$k$$k$, „ponownie powołując się na pewien warunek„ stabilności ”.

Wyjaśnienie, dlaczego LOO może być najbardziej zmiennym CV z foldem, jest dość intuicyjne, ale istnieje kontr-intuicja. Ostateczne oszacowanie CV średniego błędu kwadratu (MSE) jest średnią z oszacowań MSE w każdym krotności. Tak więc, gdy wzrasta do , oszacowanie CV jest średnią rosnącej liczby zmiennych losowych. I wiemy, że wariancja średniej maleje wraz z uśrednianiem liczby zmiennych. Tak więc, aby LOO była najbardziej zmiennym CV z krotnością , musiałoby być prawdą, że wzrost wariancji ze względu na zwiększoną korelację między szacunkami MSE przewyższa spadek wariancji ze względu na większą liczbę fałd uśrednianych w ciąguK N $K$$K$$N$$K$. I wcale nie jest oczywiste, że to prawda.

Stając się całkowicie zdezorientowanym myśląc o tym wszystkim, postanowiłem przeprowadzić małą symulację dla przypadku regresji liniowej. I symulowane 10000 zestawów danych o = 50 i 3 nieskorelowanych predykcyjnych, za każdym razem, oszacowanie błędu generalizacji pomocą CV-krotnie z = 2, 5, 10 lub 50 = . Kod R jest tutaj. Oto otrzymane średnie i warianty szacunków CV dla wszystkich 10 000 zestawów danych (w jednostkach MSE):K K $N$$K$$K$$N$

         k = 2 k = 5 k = 10 k = n = 50
mean     1.187 1.108  1.094      1.087
variance 0.094 0.058  0.053      0.051

Wyniki te pokazują oczekiwany wzorzec, że wyższe wartości prowadzą do mniej pesymistycznego nastawienia, ale wydają się również potwierdzać, że wariancja oszacowań CV jest najniższa, a nie najwyższa, w przypadku LOO.$K$

Wydaje się więc, że regresja liniowa jest jednym ze „stabilnych” przypadków wymienionych w powyższych artykułach, w których zwiększenie wiąże się raczej ze zmniejszeniem, a nie ze wzrostem wariancji w oszacowaniach CV. Ale nadal nie rozumiem:$K$

• Czym dokładnie jest ten warunek „stabilności”? Czy w pewnym stopniu dotyczy modeli / algorytmów, zestawów danych, czy obu?
• Czy istnieje intuicyjny sposób myślenia o tej stabilności?
• Jakie są inne przykłady stabilnych i niestabilnych modeli / algorytmów lub zestawów danych?
• Czy względnie bezpiecznie jest założyć, że większość modeli / algorytmów lub zestawów danych jest „stabilna”, a zatem, że należy zasadniczo wybierać tak wysoko, jak jest to możliwe obliczeniowo?$K$

Ta odpowiedź jest kontynuacją mojej odpowiedzi w zakresie błędu systematycznego i wariancji w krzyżowej walidacji typu „zostaw-jeden-out” i „K-fold”, która omawia, dlaczego LOOCV nie zawsze prowadzi do wyższej wariancji. Stosując podobne podejście, postaram się zwrócić uwagę na przypadek, w którym LOOCV prowadzi do większej wariancji w obecności wartości odstających i „niestabilnego modelu”.

Stabilność algorytmiczna (teoria uczenia się)

Temat stabilności algorytmu jest niedawny, a kilka klasycznych, inspirujących wyników zostało udowodnionych w ciągu ostatnich 20 lat. Oto kilka artykułów, które są często cytowane

• Heurystyka niestabilności i stabilizacji w wyborze modelu (1996): Leo Breiman
• Granice stabilności algorytmu i kontroli poczytalności dla LOOCV (1997): Kearns, Ron
• Stabilność i uogólnienie (2002): Bousquet, Elisseef
• Walidacja krzyżowa i stabilność średnich kwadratów (2011) Kale, Kumar, Vassilvitskii
• Niemal wszędzie błąd stabilności algorytmu i błąd uogólnienia (2012): Kutin, Niyogi
• Kilka uwag na ten temat: University of Arizona

Najlepszą stroną do zrozumienia jest z pewnością strona wikipedia, która zapewnia doskonałe streszczenie napisane przez przypuszczalnie bardzo znającego się na rzeczy użytkownika.

Intuicyjna definicja stabilności

Intuicyjnie stabilny algorytm to taki, dla którego prognozowanie niewiele się zmienia, gdy dane treningowe są nieznacznie modyfikowane.

Formalnie istnieją pół tuzina wersje stabilności, połączone ze sobą za pomocą warunków technicznych i hierarchii, zobaczyć tę grafikę z tutaj na przykład:

Cel jest jednak prosty, chcemy uzyskać ścisłe ograniczenia dotyczące błędu uogólnienia określonego algorytmu uczenia się, gdy algorytm spełnia kryterium stabilności. Jak można się spodziewać, im bardziej restrykcyjne kryterium stateczności, tym ciaśniejsza będzie odpowiednia granica.

Notacja

Poniższy zapis pochodzi z artykułu w Wikipedii, który sam kopiuje artykuł Bousquet i Elisseef:

• Zestaw treningowy został narysowany z nieznanego rozkładu D$S = \{ z_1 = (x_1,y_1), ..., z_m = (x_m, y_m)\}$
• Funkcja straty hipotezy w odniesieniu do przykładu jest zdefiniowana jakof z V ( f , z $V$$f$$z$$V(f,z)$
• Modyfikujemy zestaw szkoleniowy, usuwając -ty element:S | I = { oo 1 , . . . , Z i - 1 , z i + 1 , . . . , z m$i$$S^{|i} = \{ z_1,...,z_{i-1}, z_{i+1},...,z_m\}$
• Lub przez zastąpienie elementu:S, i = { oo 1 , . . . , z i - 1 , $i$$S^{i} = \{ z_1,...,z_{i-1}, z_i^{'}, z_{i+1},...,z_m\}$

Definicje formalne

Być może najsilniejszym pojęciem stabilności, którego można oczekiwać od interesującego algorytmu uczenia się, jest pojęcie jednolitej stabilności :

Jednolita stabilność Algorytm ma jednolitą stabilność względem funkcji straty jeżeli:$\beta$$V$

Uważany za funkcję termin można zapisać jako . Mówimy, że algorytm jest stabilny, gdy zmniejsza się jako . Nieco słabszą formą stabilności jest:β β m β m $m$$\beta$$\beta_m$$\beta_m$$\frac{1}{m}$

Stabilność hipotez

Jeśli jeden punkt zostanie usunięty, różnica w wyniku algorytmu uczenia się jest mierzona przez uśrednioną bezwzględną różnicę strat ( norma ). Intuicyjnie: niewielkie zmiany w próbce mogą spowodować, że algorytm przejdzie do pobliskich hipotez.$L_1$

Zaletą tych form stabilności jest to, że zapewniają one granice błędu i wariancji stabilnych algorytmów. W szczególności Bousquet udowodnił te granice dla stabilności jednolitości i hipotezy w 2002 r. Od tego czasu wiele pracy włożono w próbę złagodzenia warunków stabilności i uogólnienia granic, na przykład w 2011 r. Kale, Kumar, Vassilvitskii twierdzą, że oznacza to kwadratową stabilność zapewnia lepsze wariancje ograniczenia redukcji wariancji ilościowej.

Niektóre przykłady stabilnych algorytmów

Wykazano, że następujące algorytmy są stabilne i mają udowodnione granice uogólnienia:

• Regularna regresja metodą najmniejszych kwadratów (z odpowiednim wcześniejszym)
• Klasyfikator KNN z funkcją strat 0-1
• SVM z ograniczonym jądrem i dużą stałą regularyzacji
• Miękki margines SVM
• Algorytm minimalnej entropii względnej dla klasyfikacji
• Wersja worków regulujących

Eksperymentalna symulacja

Powtarzając eksperyment z poprzedniego wątku ( patrz tutaj ), wprowadzamy teraz pewien zestaw wartości odstających w zbiorze danych. W szczególności:

• 97% danych ma jednolity szum$[-.5,.5]$
• 3% danych przy jednolitym hałasie$[-20,20]$

Ponieważ model wielomianowy rzędowy nie jest uregulowany, duży wpływ na niego będzie obecność kilku wartości odstających dla małych zestawów danych. W przypadku większych zestawów danych lub gdy jest więcej wartości odstających, ich efekt jest mniejszy, ponieważ mają tendencję do anulowania. Zobacz poniżej dwa modele dla 60 i 200 punktów danych.$3$

Wykonanie symulacji jak poprzednio i wykreślenie uzyskanego średniego MSE i wariancji MSE daje wyniki bardzo podobne do eksperymentu 2 artykułu Bengio i Grandvalet 2004 .

Lewa strona : brak wartości odstających. Prawa strona : 3% wartości odstające.

(wyjaśnienie ostatniego rysunku znajduje się w powiązanym dokumencie)

Objaśnienia

Cytując odpowiedź Yves Grandvalet w innym wątku:

Intuicyjnie [w sytuacji niestabilnych algorytmów] pominięte CV może być ślepe na istniejące niestabilności, ale nie może zostać uruchomione przez zmianę pojedynczego punktu w danych treningowych, co czyni go wysoce zmiennym w zależności od realizacji zestaw treningowy.

W praktyce dość trudno jest zasymulować wzrost wariancji z powodu LOOCV. Wymaga szczególnej kombinacji niestabilności, niektórych wartości odstających, ale niezbyt wielu, i dużej liczby iteracji. Być może jest to oczekiwane, ponieważ regresja liniowa okazała się dość stabilna. Ciekawym eksperymentem byłoby powtórzenie tego dla danych o wyższych wymiarach i bardziej niestabilnego algorytmu (np. Drzewo decyzyjne)

Dam odpowiedź w kontekście cytowanego przez ciebie akapitu:

Przy K = N estymator krzyżowej walidacji jest w przybliżeniu bezstronny w odniesieniu do prawdziwego (oczekiwanego) błędu prognozowania, ale może wykazywać dużą wariancję, ponieważ N „zestawów treningowych” jest do siebie bardzo podobnych.

Estymator CV prawdziwego (przewidywanego) błędu prognozowania oparty jest na przykładzie zestawu treningowego, więc tutaj oczekiwanie jest ponad próbkami zestawu treningowego, jeśli dobrze to rozumiem.

Zatem w tym akapicie dotyczącym „dużej wariancji” jest to, że istnieje „duża” różnica między oczekiwanym błędem a błędem oszacowanym przez CV (który jest tutaj, średnią ponad krotności).

Ma to sens, ponieważ model jest dopasowany do określonego zestawu treningowego i ponieważ wszystkie fałdy treningowe są tak podobne w obrębie „odejść”. Jednak podczas gdy fałdy treningowe są bardzo podobne w rundzie CV, szacunki prawdopodobnie różnią się znacznie, jeśli zamienimy próbki treningowe na CV. W CV k-fold, ponieważ „dywersyfikujemy” fałdy treningowe, mamy pewien wpływ na uśrednianie, a dla k-fold, szacunki różnią się mniej.

Innymi słowy, estymator CV z pominięciem jednego z nich jest w zasadzie prawie podobny do metody wstrzymania, jeśli nie obracasz fałdów i nie opierasz swojej oceny błędu na jednym zestawie sprawdzania poprawności. Ponownie, w porównaniu z przykładami treningu, będzie duża wariancja w porównaniu do oszacowań z k-fold, w którym uśredniasz ponad fałdy, już trenując nieco różne modele w rundzie k-fold (innymi słowy, jeśli zamienisz zestawy treningów, oszacowania błąd przez k-fold prawdopodobnie nie będzie się tak bardzo różnić).

EDYTOWAĆ:

Kiedy czytam tutaj kilka odpowiedzi na temat weryfikacji krzyżowej i ogólnie Internetu, wydaje się, że istnieje pewne zamieszanie, do którego estymatora się odnosimy. Myślę, że niektórzy odnoszą się do modelu o dużej wariancji (gdzie ML mówi o stracie mającej dominujący komponent wariancji) w porównaniu do wysokiej wariancji k-krotnego estymatora CV. I inny zestaw odpowiedzi odnosi się do wariancji jako wariancji próbki dotyczącej fałdów, gdy ktoś mówi, że „k-fold ma dużą wariancję”. Proponuję więc być konkretny, ponieważ odpowiedzi są różne w obu przypadkach.

Już to przeszliśmy - masz zbyt matematyczne podejście do martwego konia. Zobacz klasyczną pracę Rona Kohaviego (Stanford-Univ) na temat CV i dylemat wariancji odchylenia tutaj . Kiedy skończysz to czytać, nie będziesz chciał wykonywać LOOCV, i prawdopodobnie przyciągnie Cię 10-krotnie CV i / lub CV biustu bootstrap.

Trzeba także pomyśleć o dużych zestawach danych, dla których LOOCV jest zbyt drogie obliczeniowo. Obecnie LOOCV nie jest tak naprawdę opcją w przepływach pracy / potokach większości grup.

Czym dokładnie jest ten warunek „stabilności”? Czy w pewnym stopniu dotyczy modeli / algorytmów, zestawów danych, czy obu?

We wszechświecie wszystkich funkcji kosztów i we wszechświecie wszystkich zestawów funkcji nie założyłbym, że istnieje ogólny wskaźnik „stabilności”, ponieważ nie byłby on niedopuszczalny i byłby zbyt podatny na rozkładanie się przy nieskończenie dużym zestawie warunki. Zasadniczo jest właściwe, gdy parametry df i / lub # są tak duże, że potrzeba więcej danych treningowych. Odchylenie będzie również większe dla , ponieważ wykorzystuje się więcej danych, a wariancja byłaby sztucznie zerowa, ponieważ zestawy danych szkoleniowych są zbyt podobne do siebie. Będziesz także uczył się więcej szumu w danych, gdy . k = n k = $k=n$$k=n$$k=n$

LREG jako klasyfikator działałby, gdy dane można było liniowo oddzielić, ale średnio jego stronniczość byłaby zbyt wysoka, ponieważ wielu zestawów danych nie można oddzielić liniowo.

Czy istnieje intuicyjny sposób myślenia o tej stabilności?

Moim zdaniem nie - ponieważ nie ma ogólnej zasady stabilności.

Jakie są inne przykłady stabilnych i niestabilnych modeli / algorytmów lub zestawów danych?

Jest to otwarte i zbyt szerokie, ponieważ można uzyskać nieskończenie dużą liczbę odpowiedzi, co nie byłoby pomocne.

Czy względnie bezpiecznie jest założyć, że większość modeli / algorytmów lub zestawów danych jest „stabilna”, a zatem, że należy zasadniczo wybierać tak wysoko, jak jest to możliwe obliczeniowo?$K$

Nie. Nie. Poleganie tylko na zakłada, że ​​wierzysz w dane. Przykładem są Losowe Lasy, dla których tak naprawdę nie ma . Podczas gdy około 37% danych zostanie wykorzystanych do testowania (średnio 37% obiektów nie zostanie wybranych podczas próbkowania z zamiennikiem), istnieje np. 5000 różnych zestawów danych (bootstrapów), z których każdy jest podzielony na szkolenia / testy w różny sposób. Twój przykład zaczerpnięty z dokumentów zakładał, że każdy użyty zestaw danych był prawdziwą realizacją danych - co jest błędnym założeniem. $k$$k$

Biorąc pod uwagę ładowanie, reguła stabilności otaczająca jest dopuszczalna, ponieważ próbka danych zastosowana do bezpośredniego podejścia CV obejmującego nie jest prawdziwą realizacją wszechświata wszystkich danych, z których uzyskano próbkę. $k$$k$