11 · Prawa i prawdy · 3 min czytania · aktualizacja
Co mówi nierówność Hoeffdinga i ile przykładów potrzeba w zbiorze testowym?
W skrócie
Średnia z n niezależnych ograniczonych pomiarów rzadko odbiega od wartości oczekiwanej. Szansa odchylenia o ε maleje wykładniczo z n·ε².
Co to jest
Dla średniej z n niezależnych zmiennych o wartościach w [0, 1] prawdopodobieństwo, że odbiegnie ona od swojej wartości oczekiwanej o co najmniej ε, nie przekracza 2·e^(−2nε²). Udowodnił to Wassily Hoeffding w 1963 roku.
W uczeniu maszynowym zmienną jest zwykle „czy model trafił na przykładzie i” (1 albo 0), a średnią — dokładność na zbiorze testowym. Nierówność mówi więc, jak bardzo możemy ufać dokładności zmierzonej na skończonej próbce, bez żadnych założeń o rozkładzie poza niezależnością i ograniczonością.
Przekształcona daje praktyczną receptę: żeby z prawdopodobieństwem 1 − δ dokładność testowa nie odbiegała od prawdziwej o więcej niż ε, wystarczy n ≥ ln(2/δ) / (2ε²) przykładów.
Mechanizm — dlaczego tak działa
Średnia wielu niezależnych składników nie może łatwo uciec daleko, bo do tego wszystkie składniki musiałyby „zgodnie” odchylić się w tę samą stronę. Hoeffding obliczył górne ograniczenie tej szansy, korzystając z funkcji tworzącej momenty i faktu, że zmienna ograniczona do [0, 1] nie może mieć zbyt grubych ogonów. Kluczowe jest wykładnicze tempo: podwojenie n podnosi wykładnik do kwadratu, a nie tylko zmniejsza szansę dwa razy.
Granica jest celowo zachowawcza — działa dla każdego rozkładu, więc dla konkretnego często jest luźna. Przybliżenie normalne (centralne twierdzenie graniczne) daje węższe przedziały, ale tylko asymptotycznie.
Najważniejsza pułapka: nierówność dotyczy jednego ustalonego z góry modelu. Jeśli porównamy M modeli na tym samym zbiorze testowym i wybierzemy najlepszy, trzeba użyć granicy łącznej (union bound): 2M·e^(−2nε²). Przy tej samej liczbie przykładów margines rośnie jak √ln M. Z tego właśnie rachunku wyrasta teoria generalizacji: wymiar VC zastępuje M dla nieskończonych rodzin modeli.
Druga pułapka: niezależność. Jeśli przykłady testowe są skorelowane (ten sam pacjent wiele razy, kolejne dni w szeregu czasowym), efektywne n jest mniejsze niż liczba wierszy, a granica zbyt optymistyczna.
Na przykładzie
Ile przykładów testowych potrzeba przy δ = 0,05? Dla ε = 0,1 — 185; dla ε = 0,05 — 738; dla ε = 0,03 — 2050; dla ε = 0,01 — 18 445. Pomiar dokładności z precyzją jednego punktu procentowego wymaga więc kilkunastu tysięcy niezależnych przykładów.
Symulacja: model o prawdziwej dokładności 0,80 oceniany na 100 przykładach, 100 000 powtórzeń. Wynik odbiegł od 0,80 o 0,1 lub więcej w 1,4% przypadków; Hoeffding gwarantuje co najwyżej 27,1%. Granica jest prawdziwa, ale kilkanaście razy luźniejsza od rzeczywistości.
Efekt wielu porównań: na zbiorze 1000 przykładów margines przy δ = 0,05 wynosi 0,043 dla jednego modelu, 0,064 dla 100 i 0,073 dla 1000. Symulowaliśmy też M klasyfikatorów rzucających monetą (prawdziwa dokładność 0,5): najlepszy z 10 osiąga średnio 0,525, ze 100 — 0,540, z 1000 — 0,551. Czysty przypadek, który bez poprawki wyglądałby na wynik.
W praktyce
- Zbiór testowy dobierz do potrzebnej precyzji: n ≈ ln(2/δ)/(2ε²) to bezpieczne górne oszacowanie.
- Przedział ufności dla dokładności liczy się częściej metodą Wilsona lub bootstrapem (
scipy.stats.binomtest(...).proportion_ci()), co daje węższe przedziały. - Dzielenie z grupami (
GroupKFold,GroupShuffleSplit) przywraca niezależność, gdy jeden obiekt ma wiele wierszy. - Zbioru testowego używaj raz; każde kolejne „podglądanie” to nowe porównanie, które zjada margines.
- Różnice dokładności rzędu 0,01 na zbiorze kilkuset przykładów zwykle mieszczą się w szumie.
Najczęstsze pytania
- Czym różni się Hoeffding od prawa wielkich liczb?
- Prawo wielkich liczb mówi, że średnia w końcu zbiegnie do wartości oczekiwanej. Hoeffding mówi, jak szybko: podaje konkretną granicę prawdopodobieństwa odchylenia dla danego n.
- Czy można stosować Hoeffdinga do błędu średniokwadratowego?
- Tak, jeśli błąd jest ograniczony do przedziału [a, b]; wtedy w wykładniku pojawia się (b − a)². Dla nieograniczonych strat (np. MSE z odstającymi wartościami) potrzebne są inne nierówności.
- Dlaczego granica jest tak luźna?
- Bo musi działać dla każdego rozkładu, w tym najgorszego. Dla dokładności bliskiej 0,5 jest dość ciasna, dla dokładności bliskiej 0 lub 1 — bardzo luźna, bo wariancja jest wtedy mała.
Źródła
- Hoeffding W. (1963). Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association, 58(301), 13–30.
- Abu-Mostafa Y. S., Magdon-Ismail M., Lin H.-T. (2012). Learning From Data. AMLBook, rozdz. 1–2.
- Shalev-Shwartz S., Ben-David S. (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, rozdz. 4.
- Mohri M., Rostamizadeh A., Talwalkar A. (2018). Foundations of Machine Learning, 2nd ed. MIT Press, dodatek D.