Zagadka: milion kubełków, tysiąc słów i paradoks urodzin
W skrócie
Hashing trick wrzuca 1000 słów do ponad miliona kubełków. Jaka jest szansa, że dwa słowa trafią do tego samego? Zagadka o paradoksie urodzin w ML, z liczbami.
Budujesz klasyfikator tekstu i zamiast słownika używasz sztuczki z haszowaniem (hashing trick). Każde słowo przechodzi przez funkcję skrótu, a ta wskazuje jedną z m = 2²⁰ = 1 048 576 kolumn macierzy cech. Słownika nie trzeba przechowywać, ale dwa różne słowa mogą trafić do tej samej kolumny. Model nie odróżni ich wtedy od siebie.
Załóż, że funkcja skrótu rozrzuca słowa niezależnie i równomiernie po wszystkich kubełkach.
Pytanie 1. Twój zbiór ma n = 1000 różnych słów. Kubełków jest ponad tysiąc razy więcej niż słów. Jaka jest szansa, że co najmniej jedna para słów trafi do tego samego kubełka? Najpierw zgadnij: 0,1%? 5%? 40%?
Pytanie 2. Ile różnych słów wystarczy, żeby szansa na co najmniej jedną kolizję przekroczyła 50%?
Pytanie 3. Słownik rośnie do 100 000 słów. Jaki odsetek słów dzieli kubełek z przynajmniej jednym innym słowem?
Wskazówka. Licz prawdopodobieństwo zdarzenia przeciwnego, czyli że wszystkie słowa trafią do różnych kubełków. Drugie słowo musi ominąć 1 zajęty kubełek, trzecie 2 zajęte i tak dalej. Pomocna jest też liczba par słów: n(n − 1)/2.
Rozwiązanie
Pokaż rozwiązanie
Pytanie 1: około 37,9%.
Prawdopodobieństwo, że wszystkie n słów trafi do różnych kubełków, to iloczyn:
P(brak kolizji) = (1 − 0/m) × (1 − 1/m) × (1 − 2/m) × … × (1 − (n − 1)/m).
Dla n = 1000 i m = 1 048 576 iloczyn wynosi około 0,6209, więc P(co najmniej jedna kolizja) ≈ 0,3791.
Skąd tak dużo? Kolizja dotyczy par słów, a par jest 1000 × 999 / 2 = 499 500. Każda para zderza się z prawdopodobieństwem 1/m, więc oczekiwana liczba zderzających się par to 499 500 / 1 048 576 ≈ 0,476. Dla rzadkich zdarzeń P(co najmniej jedna) ≈ 1 − e^(−0,476) ≈ 0,379, co zgadza się z dokładnym wynikiem do trzeciego miejsca po przecinku.
To ten sam mechanizm co w klasycznym paradoksie urodzin. Wśród 23 osób są 253 pary, a szansa, że któraś ma urodziny tego samego dnia (365 dni, bez lat przestępnych), wynosi około 50,7%.
Pytanie 2: 1206 słów.
Szukamy najmniejszego n, dla którego iloczyn z pytania 1 spada poniżej 0,5. Bezpośrednie liczenie daje:
- n = 1205: P(kolizja) ≈ 0,49946,
- n = 1206: P(kolizja) ≈ 0,50004.
Przybliżenie √(2m · ln 2) ≈ 1205,7 trafia niemal dokładnie. Ogólna lekcja: kolizje zaczynają się przy liczbie elementów rzędu pierwiastka z liczby kubełków, a nie przy liczbie porównywalnej z m. Przy milionie kubełków już tysiąc elementów daje 38% szans na co najmniej jedną kolizję, a około 1206 — ponad połowę.
Pytanie 3: około 9,1% słów.
Ustalmy jedno słowo. Pozostałe 99 999 słów omija jego kubełek z prawdopodobieństwem (1 − 1/m)^99 999 ≈ 0,9090. Słowo jest więc „samotne” z prawdopodobieństwem 0,9090, a dzieli kubełek z innym z prawdopodobieństwem 0,0910. Wartość oczekiwana: około 9096 ze 100 000 słów ma sąsiada w kubełku. Zajętych kubełków będzie średnio około 95 380, czyli o 4620 mniej niż słów.
Czy to szkodzi modelowi? Zwykle mniej, niż sugerują te liczby. Większość słów jest rzadka (prawo Zipfa), więc typowa kolizja łączy dwa rzadkie słowa o znikomym wpływie na predykcję. Szkodzi kolizja dwóch częstych słów o przeciwnym znaczeniu. Dlatego przy haszowaniu cech do kodowania kategorii czy w cechach tekstowych warto dobierać m z zapasem i sprawdzać w walidacji, czy zwiększenie m poprawia wynik.
Wszystkie wartości policzono w Pythonie: iloczyn liczony przez sumę logarytmów (math.log1p), próg 50% znaleziony przez przeszukanie kolejnych n.