Zagadka: ile przykładów, żeby zobaczyć każdą klasę?
W skrócie
Losujesz batch 128 przykładów ze 100 równolicznych klas. Ilu klas w nim zabraknie? Jak duży musi być batch, żeby były wszystkie? Kolekcjoner kuponów w ML.
Trenujesz klasyfikator na zbiorze ze 100 równolicznymi klasami, jak w części treningowej CIFAR-100 (50 000 obrazów, po 500 na klasę). Dane są potasowane, a model dostaje je w mini-batchach po 128 przykładów.
Dla prostoty załóż, że każdy przykład w batchu jest losowany niezależnie, a każda klasa ma szansę 1/100. Przy 500 przykładach na klasę to bardzo dobre przybliżenie losowania bez zwracania (sprawdzimy to w rozwiązaniu).
Pytanie 1. Ile klas średnio brakuje w jednym batchu 128 przykładów? Najpierw zgadnij: 0? 5? 25?
Pytanie 2. Jak duży musi być batch, żeby szansa, że pojawi się w nim każda ze 100 klas, przekroczyła 50%?
Pytanie 3. Wyciągasz przykłady po jednym. Ile średnio musisz ich obejrzeć, zanim zobaczysz każdą klasę przynajmniej raz? A przy 1000 klasach, jak w ImageNet-1k?
Wskazówka. W pytaniu 1 policz szansę, że jedna konkretna klasa się nie pojawi, i skorzystaj z liniowości wartości oczekiwanej. W pytaniu 3 podziel czekanie na etapy: gdy znasz już i klas, następny przykład jest „nowy” z prawdopodobieństwem (100 − i)/100.
Rozwiązanie
Pokaż rozwiązanie
Pytanie 1: średnio brakuje około 27,6 klasy.
Konkretna klasa nie trafia do batcha, jeśli wszystkie 128 losowań ją ominie: 0,99¹²⁸ ≈ 0,2763. Wartość oczekiwana sumy to suma wartości oczekiwanych, więc średnia liczba brakujących klas to 100 × 0,2763 ≈ 27,63. W typowym batchu jest więc tylko około 72 różnych klas, choć przykładów jest 128.
Szansa, że w batchu 128 pojawią się wszystkie klasy, wynosi około 1,5 · 10⁻²², czyli w praktyce zero. Batch 256 też nie wystarcza: brakuje w nim średnio 7,6 klasy, a komplet trafia się z prawdopodobieństwem około 0,00012.
Czy uproszczenie „ze zwracaniem” coś psuje? Przy losowaniu bez zwracania z 50 000 przykładów (po 500 na klasę) średnia liczba brakujących klas wynosi 27,58 zamiast 27,63. Różnica pojawia się dopiero na drugim miejscu po przecinku.
Pytanie 2: 497 przykładów.
Prawdopodobieństwo, że w batchu n przykładów jest każda z K klas, daje wzór włączeń i wyłączeń:
P(wszystkie) = Σⱼ (−1)ʲ · C(K, j) · (1 − j/K)ⁿ, dla j = 0, 1, …, K.
Dla K = 100:
- n = 496: P ≈ 0,49744,
- n = 497: P ≈ 0,50098.
Przybliżenie K ln K − K ln(ln 2) ≈ 497,2 trafia niemal dokładnie. Żeby mieć 90% szans na komplet, potrzeba batcha 683 przykładów, a dla 99% aż 916. Batch musi więc mieć prawie pięć razy więcej przykładów, niż jest klas, żeby komplet był choćby równie prawdopodobny jak jego brak.
Pytanie 3: średnio około 518,7 przykładu, a przy 1000 klasach około 7485.
To klasyczny problem kolekcjonera kuponów. Gdy znasz już i klas, każdy kolejny przykład jest nowy z prawdopodobieństwem (K − i)/K, więc na nową klasę czekasz średnio K/(K − i) losowań. Suma po wszystkich etapach:
E[T] = K × (1 + 1/2 + 1/3 + … + 1/K).
Dla K = 100 daje to 100 × 5,1874 ≈ 518,7. Najciekawszy jest rozkład tego czekania:
- pierwsze 50 klas zobaczysz średnio po 68,8 przykładu,
- na pozostałe 50 czekasz średnio 449,9 przykładu,
- na samą ostatnią klasę średnio 100 przykładów.
Odchylenie standardowe T wynosi około 125,8. W około 8,5% przypadków trzeba obejrzeć ponad 700 przykładów, a w około 3,2% ponad 800. Dla K = 1000 wzór daje około 7485,5, czyli prawie 7,5 przykładu na klasę.
Symulacja. Python 3 z numpy, generator np.random.default_rng(2026), losowanie ze zwracaniem:
- 100 000 batchy po 128: średnio brakuje 27,63 klasy,
- 100 000 batchy po 497: komplet klas w 50,3% batchy,
- 20 000 przebiegów „po jednym aż do kompletu”: średnio 520,0 przykładu, odchylenie 125,6.
Wyniki zgadzają się ze wzorami w granicach błędu losowego. Wzory dokładne policzono na ułamkach (fractions.Fraction), żeby uniknąć błędów zaokrągleń w sumie naprzemiennej.
Co z tego wynika w praktyce?
Przy zwykłym trenowaniu z entropią krzyżową brak części klas w pojedynczym batchu nie szkodzi, bo w ciągu epoki każda klasa i tak się pojawi. Problem zaczyna się wtedy, gdy coś liczysz wewnątrz batcha: metrykę uśrednianą po klasach, statystyki „na klasę” albo stratę, która potrzebuje kilku przykładów z tej samej klasy. Przy 100 klasach batch 128 nie ma szans na komplet, więc takie liczby będą liczone na niepełnym zestawie klas.
Jeszcze gorzej jest przy niezrównoważonych danych. Klasa, która stanowi 0,1% zbioru, nie trafia do batcha 128 przykładów z prawdopodobieństwem 0,999¹²⁸ ≈ 88,0%. Średnio przypada na nią 0,128 przykładu na batch. Pomaga losowanie warstwowe: sampler, który składa batch z ustalonej liczby przykładów z każdej klasy, oraz warstwowe foldy w walidacji krzyżowej. Ten sam rachunek podpowiada też, czego oczekiwać przy wyborze rozmiaru batcha: wzrost liczby obecnych klas jest powolny, bo ostatnie klasy „łapie się” najdłużej.