11 · Prawa i prawdy · 3 min czytania · aktualizacja
Co mówi twierdzenie no free lunch w uczeniu maszynowym?
W skrócie
Uśredniony po wszystkich możliwych problemach żaden algorytm uczenia nie jest lepszy od innego. Przewaga zawsze bierze się z założeń dopasowanych do danych.
Co to jest
Uśredniony po wszystkich możliwych problemach każdy algorytm uczenia ma dokładnie taką samą skuteczność na danych spoza zbioru treningowego. Twierdzenie sformułował David Wolpert w 1996 roku dla uczenia nadzorowanego, a rok później razem z Williamem Macready’m — dla optymalizacji.
Brzmi jak paradoks: przecież las losowy „zwykle” bije pojedyncze drzewo. Kluczowe jest słowo „wszystkich”. Jeśli dopuścimy każdy możliwy związek między cechami a etykietą — także całkowicie chaotyczny — to na każdy świat, w którym algorytm A wygrywa, przypada świat, w którym w tym samym stopniu przegrywa.
Praktyczny wniosek nie brzmi „wszystko jedno, czego użyjesz”, tylko: nie istnieje uniwersalnie najlepszy model. Każdy algorytm zakłada coś o świecie, a wygrywa tam, gdzie te założenia pasują.
Mechanizm — dlaczego tak działa
Wyobraź sobie zbiór treningowy i punkty testowe, których model nigdy nie widział. O etykietach tych nowych punktów dane treningowe same w sobie nie mówią nic — chyba że założymy jakąś regularność: że podobne punkty mają podobne etykiety, że granica jest liniowa, że ważnych cech jest niewiele. To założenie nazywa się obciążeniem indukcyjnym (inductive bias).
Gdy uśredniamy po wszystkich funkcjach etykietujących z równym prawdopodobieństwem, każda możliwa etykieta nowego punktu jest równie prawdopodobna, niezależnie od tego, co widzieliśmy. Wtedy każda reguła przewidywania — od sieci neuronowej po rzut monetą — trafia średnio tak samo. Przewaga jednego algorytmu na pewnej klasie problemów musi być „spłacona” stratą na innej.
Dlaczego więc uczenie maszynowe w ogóle działa? Bo prawdziwe dane nie są losowane jednostajnie ze wszystkich możliwych światów. Mają strukturę: ciągłość, hierarchię, niski wymiar wewnętrzny, rzadkie zależności. Algorytmy, które te własności zakładają, wygrywają na realnych danych — a przegrywają na zbiorach, których prawie nikt nie spotyka.
Zastrzeżenie: twierdzenie jest matematycznie prawdziwe, ale jego założenie (równy rozkład po wszystkich problemach) jest skrajne. Nie mówi, że na Twoim konkretnym zbiorze wszystkie modele są równie dobre. Mówi, że wybór modelu to zakład o naturę danych i że ten zakład trzeba sprawdzić empirycznie.
Na przykładzie
Porównaliśmy sześć klasyfikatorów (kNN, regresja logistyczna, drzewo, las losowy, naiwny Bayes, SVM) w 5-krotnej walidacji krzyżowej. Regresja logistyczna wygrała na Iris (0,96), Wine (0,98) i Breast Cancer (0,98). Na Digits 8×8 najlepszy był SVM (0,98), a na Titanicu też SVM (0,83), przy regresji logistycznej dopiero na piątym miejscu (0,79).
Teraz dwa sztuczne światy. Gdy klasa zależy od XOR znaków dwóch cech, regresja logistyczna spada do 0,55, a drzewo osiąga 0,98, las 0,99. Gdy klasa zależy od skośnej granicy liniowej w 20 wymiarach, role się odwracają: regresja logistyczna 0,95, drzewo 0,65. Na zbiorze z losowymi etykietami wszystkie modele dały 0,49–0,55, a „zwycięzca” był po prostu najbardziej szczęśliwy. To jest NFL w miniaturze: ranking zależy od świata.
Dane: Titanic Iris (irysy Fishera) Breast Cancer Wisconsin (diagnostyka raka piersi) Wine (wina z Piemontu) Digits (ręcznie pisane cyfry 8×8)
W praktyce
- Zaczynaj od prostego punktu odniesienia (
DummyClassifier, regresja liniowa/logistyczna) i porównuj z nim każdy model. - Wybór modelu rozstrzygaj walidacją krzyżową (
cross_val_score,GridSearchCV), nie reputacją algorytmu. - Na danych tabelarycznych gradient boosting jest mocnym kandydatem, ale to empiryczna prawidłowość, a nie prawo — sprawdzaj.
- Wiedza dziedzinowa (np. wiadomo, że zależność jest monotoniczna) to darmowy lunch, który sam sobie przynosisz: wbuduj ją w model.
- Porównując wiele modeli na małym zbiorze, pamiętaj o szumie wyniku — różnice rzędu 0,01 mogą być przypadkiem.
Najczęstsze pytania
- Czy NFL znaczy, że nie warto szukać lepszych algorytmów?
- Nie. Znaczy, że lepszość jest zawsze względem jakiejś klasy problemów. Algorytm może być wyraźnie lepszy na obrazach, tekstach czy danych tabelarycznych, bo te klasy mają wspólną strukturę.
- Skoro tak, czemu gradient boosting wygrywa tyle konkursów?
- Bo typowe dane tabelaryczne mają strukturę, do której pasują jego założenia: progi na pojedynczych cechach, interakcje niskiego rzędu, odporność na skalę. To fakt o danych, nie wyjątek od twierdzenia.
- Czy NFL dotyczy też optymalizacji?
- Tak, wersja Wolperta i Macready’ego z 1997 roku mówi, że uśrednione po wszystkich funkcjach celu wszystkie algorytmy przeszukiwania są równie dobre. Z tego samego powodu żaden optymalizator nie jest najlepszy wszędzie.
Źródła
- Wolpert D. H. (1996). The Lack of A Priori Distinctions Between Learning Algorithms. Neural Computation, 8(7), 1341–1390.
- Wolpert D. H., Macready W. G. (1997). No Free Lunch Theorems for Optimization. IEEE Transactions on Evolutionary Computation, 1(1), 67–82.
- Shalev-Shwartz S., Ben-David S. (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, rozdz. 5.
- Fernández-Delgado M. i in. (2014). Do we Need Hundreds of Classifiers to Solve Real World Classification Problems? Journal of Machine Learning Research, 15, 3133–3181.