8.2 Véges hipotézisosztály egyenletes korlátja

8.2.1 Cél, előismeret és induló kérdés

A 8.1. Kockázat, mintavétel és baseline alfejezetben láttuk, hogy a Hoeffding-korlát egy rögzített $h$ hipotézisre számszerűsíti az empirikus és a populációs kockázat eltérését. A gyakorlati modellválasztás azonban nem rögzített: több jelölt közül éppen azt választjuk, amelyik a tanítómintán a legjobbnak látszik. Ebben az alfejezetben az a kérdés, hogyan kaphatunk olyan állítást, amely minden $h\in\mathcal H$ jelöltre egyszerre, tehát a mintán választott modellre is érvényes, ha $\mathcal H$ véges.

Előismeret: a 8.1. Kockázat, mintavétel és baseline populációs kockázat, empirikus kockázat, iid minta és a Hoeffding-állítás fogalma; a 7.2. Softmax és többosztályos cross-entropy cross-entropy definíciója; a 4.2. Parciális derivált és gradiens gradiens fogalma annyiban, hogy itt tudatosan nem használunk differenciálhatóságot: a korlát csak korlátosságot és függetlenséget kér.

Induló becslés: ha $M=1000$ jelölt, $n=500$ minta és $5\%$ megengedett kudarcvalószínűség, mekkora $\epsilon$ hibasáv garantálható? A levezetés után ezt pontosan kiszámítjuk.

8.2.2 Definíciók, jelölések és a felhasznált koncentrációs állítás

Legyen $\mathcal X$ a bemeneti tér, $\mathcal Y$ a célok tere, $\mathcal H$ pedig hipotézisosztály, azaz jelöltek egy halmaza; elemei $h:\mathcal X\to\mathcal Y$ függvények. A tanulási feladat loss függvénye $\ell:\mathcal Y\times\mathcal Y\to[0,1]$, tehát értékkészlete a zárt $[0,1]$ intervallumba esik. Egy $h$-ra a populációs kockázat és az $S=\{(x_i,y_i)\}_{i=1}^n$ iid mintán vett empirikus kockázat:

$$R(h)=\mathbb E_{(x,y)}[\ell(h(x),y)],\qquad \hat R(h)=\frac1n\sum_{i=1}^n\ell(h(x_i),y_i).$$

A tenzoralak itt egyszerű: ha a modell $N$ megfigyelésre $Z\in\mathbb R^{N\times K}$ logitokat ad, akkor a loss megfigyelésenként egy-egy skalár, az empirikus kockázat pedig ezek átlaga, tehát skalár. A skalár reduction elengedhetetlen: a Hoeffding-korlát átlagokra szól.

Az alábbi állítást adottnak vesszük; a teljes bizonyítást nem reprodukáljuk, mert forrása [P27] eredeti cikke, amelynek státusza jelen kéziratban kiadói bibliográfiai rekord, nem pedig teljesen olvasott bizonyítás.

Tétel (Hoeffding, $[0,1]$-korlátos alak). Legyen $X_1,\dots,X_n$ független valószínűségi változó, mindegyik a $[0,1]$ intervallumba esik; legyen $\bar X=\frac1n\sum_{i=1}^n X_i$ és $\mu=\frac1n\sum_{i=1}^n\mathbb E[X_i]$. Ekkor minden $\epsilon>0$-ra

$$P\left(\bar X-\mu\ge\epsilon\right)\le e^{-2n\epsilon^2},\qquad P\left(\bar X-\mu\le-\epsilon\right)\le e^{-2n\epsilon^2},$$

és a két irányt összeadva

$$P\left(|\bar X-\mu|\ge\epsilon\right)\le 2e^{-2n\epsilon^2}.$$

A $\log$ a képletekben természetes logaritmus. A $[0,1]$ alakra az általános Hoeffding-állításból $a_i=0$, $b_i=1$ helyettesítéssel jutunk. Az állítást rögzített hipotézisre már 8.1. Kockázat, mintavétel és baseline alkalmazta: ott $X_i=\ell(h(x_i),y_i)$.

8.2.3 Uniókorlát és a véges $\mathcal H$ egyenletes korlátja

A uniókorlát (union bound) elemi valószínűségi egyenlőtlenség: tetszőleges $A_1,\dots,A_M$ eseményekre

$$P(A_1\cup A_2\cup\cdots\cup A_M)\le\sum_{j=1}^M P(A_j).$$

A jobb oldal akkor is igaz, ha az események erősen összefüggenek; ezért a korlát sok eseményre laza lehet, de a levezetés egyszerű és mindig érvényes.

Most bizonyítjuk az alfejezet fő állítását. A felhasznált Hoeffding-alakból indulunk ki; a saját hozzájárulás az uniókorlát alkalmazása.

Tétel (véges hipotézisosztály egyenletes korlátja). Legyen $\mathcal H$ véges, $|\mathcal H|=M$. Tegyük fel, hogy a loss $\ell(\cdot,\cdot)\in[0,1]$ minden bemenetre, és $S=\{(x_i,y_i)\}_{i=1}^n$ iid minta. Ekkor minden $\epsilon>0$-ra

$$P\left(\max_{h\in\mathcal H}\left|\hat R(h)-R(h)\right|\ge\epsilon\right)\le 2M e^{-2n\epsilon^2}.$$

Bizonyítás. Rögzítsünk egy $h\in\mathcal H$-t. Az $X_i^{(h)}=\ell(h(x_i),y_i)$ változók a $[0,1]$-be esnek; az iid minta miatt függetlenek, és $\mathbb E[X_i^{(h)}]=R(h)$. A kétoldali Hoeffding-korlát szerint minden $\epsilon>0$-ra

$$P\left(\left|\hat R(h)-R(h)\right|\ge\epsilon\right)\le 2e^{-2n\epsilon^2}. \tag{1}$$

Definiáljuk az $A_h=\{\left|\hat R(h)-R(h)\right|\ge\epsilon\}$ eseményt. A bal oldalon álló $\max$ akkor és csak akkor éri el $\epsilon$-t, ha valamelyik $h$-ra bekövetkezik $A_h$; tehát

$$\left\{\max_{h\in\mathcal H}\left|\hat R(h)-R(h)\right|\ge\epsilon\right\}=\bigcup_{h\in\mathcal H}A_h.$$

A uniókorlátot és (1)-et alkalmazva, felhasználva, hogy az összegben $|\mathcal H|=M$ tag van:

$$P\left(\bigcup_{h\in\mathcal H}A_h\right)\le\sum_{h\in\mathcal H}P(A_h)\le\sum_{h\in\mathcal H}2e^{-2n\epsilon^2}=2Me^{-2n\epsilon^2}.$$

Ezzel az állítást beláttuk. $\square$

A bizonyítás státusza: a Hoeffding-egyenlőtlenség bizonyítását a kézirat nem végzi el; a tétel kimondott, [P27]-re hivatkozó előfeltétel. A uniókorlátos lépés a jelen alfejezet saját, teljes levezetése.

8.2.4 Konfidenciaparaméter és empirikus kockázatminimalizálás

A tétel kényelmesebb alakját kapjuk, ha a kudarcvalószínűségre adott felső korlátot rögzítünk. Legyen $0<\delta<1$ a konfidenciaparaméter; $1-\delta$ a megcélzott konfidenciaszint. Megoldjuk a

$$2Me^{-2n\epsilon^2}=\delta$$

egyenletet $\epsilon$-ra:

$$\epsilon=\sqrt{\frac{\log(2M/\delta)}{2n}}. \tag{2}$$

Ezzel a tétel így fogalmazható: $1-\delta$ valószínűséggel egyszerre minden $h\in\mathcal H$-ra

$$\left|\hat R(h)-R(h)\right|<\epsilon.$$

Az $\epsilon$ értelmezése feltételes, ismételt mintavételi garancia: ha a kísérletet sok független mintán megismételnénk, a minták legfeljebb $\delta$ hányadán romolhat el az egyenletes hibasáv; az [S02] forrás a konfidenciaintervallum hasonló értelmezését tárgyalja.

Vezessük le az adaptív választásra vonatkozó következményt. Legyen $\hat h\in\mathcal H$ az empirikus kockázatminimalizáló (ERM), azaz $\hat h=\arg\min_{h\in\mathcal H}\hat R(h)$, és legyen $h^*=\arg\min_{h\in\mathcal H}R(h)$ a populáció szerinti legjobb. Az egyenletes eseményen minden $h$-ra, így $\hat h$-ra és $h^*$-ra is igaz, hogy $|\hat R(h)-R(h)|<\epsilon$. Ezért

$$R(\hat h)\le\hat R(\hat h)+\epsilon\le\hat R(h^*)+\epsilon\le R(h^*)+2\epsilon.$$

Itt a középső egyenlőtlenség az ERM definíciója: $\hat h$ minimalizálja $\hat R$-t. A végeredmény a tanulási korlát:

Következmény. A fenti feltételek mellett legalább $1-\delta$ valószínűséggel

$$R(\hat h)\le R(h^*)+2\epsilon,\qquad \epsilon=\sqrt{\frac{\log(2M/\delta)}{2n}}.$$

Ez az, amit a rögzített $h$-ra vonatkozó 8.1. Kockázat, mintavétel és baseline alfejezetbeli korlát nem tudott garantálni: az adaptívan választott $\hat h$ hibája legfeljebb $2\epsilon$-nal haladja meg az osztály legjobb populációs kockázatát, a $2\epsilon$ többlet pedig az uniókorlát ára.

8.2.5 Számpélda és numerikus labor

Tekintsük a bevezető kérdést: $M=1000$, $n=500$, $\delta=0{,}05$. Ekkor

$$\epsilon=\sqrt{\frac{\log(2\cdot1000/0{,}05)}{2\cdot500}}=\sqrt{\frac{\log(40000)}{1000}}\approx\sqrt{0{,}0105966}\approx0{,}1029.$$

Tehát 95% konfidenciaszinten az empirikus kockázat minden jelöltre legfeljebb $10{,}3$ százalékponttal tér el a populációs kockázattól, az ERM pedig legfeljebb $20{,}6$ százalékponttal rosszabb, mint az osztály legjobbja.

A labor kódja determinisztikus: nincs véletlenszám, nincs tensor, ezért seed, dtype és device nem alkalmazandó. A math modul 64 bites lebegőpontos számítást végez.

"""lab/n030_bound.py — Véges H egyenletes korlátjának numerikus számítása.

A számítás determinisztikus, ezért nincs seed, tensor dtype vagy device.
Futtatás: python lab/n030_bound.py
"""
import math

def uniform_bound(M: int, n: int, delta: float) -> tuple[float, float]:
    """Adott M, n, delta mellett visszaadja (epsilon, bound).

    bound = 2*M*exp(-2*n*epsilon**2), amelynek delta körül kell lennie
    a (2) képlet numerikus ellenőrzéseként.
    """
    if not (isinstance(M, int) and isinstance(n, int)):
        raise TypeError("M és n egész típusú legyen")
    if M <= 0 or n <= 0:
        raise ValueError("M és n pozitív egész")
    if not 0.0 < delta < 1.0:
        raise ValueError("delta a nyílt (0,1) intervallumba esik")
    eps = math.sqrt(math.log((2.0 * M) / delta) / (2.0 * n))
    bound = 2.0 * M * math.exp(-2.0 * n * eps * eps)
    return eps, bound

def main() -> None:
    delta = 0.05
    tolerance = 1e-12  # 64 bites lebegőpontos ellenőrzési küszöb
    print(f"delta = {delta}")
    for M in (10, 1000, 1_000_000):
        print(f"M = {M}")
        for n in (100, 500, 1000, 5000, 10_000):
            eps, bound = uniform_bound(M, n, delta)
            ok = abs(bound - delta) <= tolerance * max(1.0, delta)
            print(f"  n={n:6d}  epsilon={eps:.6f}  bound={bound:.6e}  ellenorzes={ok}")

if __name__ == "__main__":
    main()

Az alábbi értékek a (2) képletből számított szemléltetésként szerepelnek, nem mérési eredmények.

A bound oszlop minden sorban $\delta=0{,}05$-öt ad vissza a lebegőpontos pontosság erejéig: a (2) képletet úgy definiáltuk, hogy a helyettesítés kiejtse egymást. Ez az ellenőrzés azt igazolja, hogy a kód az inverz képletet konzisztensen számolja.

Mikor használhatatlanul laza a korlát? A képlet két logaritmusos, két gyökös tényezőt tartalmaz. $M=10^6$, $n=1000$ esetén $\epsilon\approx13{,}2$ százalékpont; egy $[0,1]$-beli losson a teljes $[0,1]$ tartományhoz képest ez hatalmas, és az ERM-korlát $2\epsilon\approx26{,}5$ százalékpont. A gyakorlati összehasonlításokban ennél jóval kisebb különbségek is döntőek. Két ok miatt laza a korlát: (i) a Hoeffding-korlát maga sem használja ki az eloszlás szórását; (ii) az uniókorlát a legrosszabb esetben teljesen független eseményeket feltételező összeget ad, pedig a hipotézisek kockázatbecslései erősen korrelálnak. Ezért a $2Me^{-2n\epsilon^2}$ alakot felső garanciaként, nem pedig éles predikcióként kell olvasni. Kis $n$-re vagy nagy $M$-re a korlát gyakorlati döntésre alkalmatlan lehet, ettől matematikailag helyes.

8.2.6 Gyakori tévedés: korlátlan cross-entropy

A tétel feltétele, hogy a loss minden bemenetre $[0,1]$-be essen. A többosztályos cross-entropy a 7.2. Softmax és többosztályos cross-entropy alfejezetből logitsokra:

$$\ell(z,y)=-z_y+\log\sum_{k=1}^K e^{z_k}.$$

Ez nem korlátos $1$-gyel. Legyen $K=2$, a helyes osztály $y=0$, a logit pedig $z=(0,10)$. Ekkor

$$\ell(z,y)=\log(1+e^{10})\approx10{,}000045>1.$$

A logit növelésével a loss tetszőlegesen nagy lehet, tehát nem létezik rögzített $B$, amellyel a $[0,1]$-re normálás a feladat tartalmi megváltozatása nélkül elvégezhető lenne.

Nézzünk konkrét ellenpéldát arra, hogy a feltétel nélkül a konklúzió ténylegesen hamis lehet. Legyen $\mathcal H=\{h\}$, tehát $M=1$, $n=1$. Tegyük fel, hogy az egyetlen megfigyelés $y$ célja $\frac12$ valószínűséggel $0$, $\frac12$ valószínűséggel $1$, a modell pedig mindig $z=(0,10)$ logitot ad. A loss $y=0$ esetén $\approx10$, $y=1$ esetén $\approx0$; így $R(h)\approx5$. Az egyelemű mintán $\hat R(h)$ vagy $\approx10$, vagy $\approx0$, tehát

$$P\left(|\hat R(h)-R(h)|\ge1\right)=1,$$

hiszen az eltérés mindkét kimenetelben $\approx5$. A $[0,1]$-korlátos tétel viszont $\epsilon=1$-re $2e^{-2}\approx0{,}2707$ felső korlátot adna, ami nyilvánvalóan hamis erre a nem korlátos lossra. A tétel érvényes, a feltételei azonban nem teljesülnek: változtatás nélkül nem alkalmazható korlátlan cross-entropyra. Ha a loss $[0,B]$-be esik, akkor a $[0,1]$-re skálázott változatra alkalmazható a korlát, de a $B$ skálának megfelelően $\epsilon$ is skálázódik; a nyers logits-alapú cross-entropy esetén nincs ilyen véges $B$.

8.2.7 Feladatok

8.2.7.1 F1 — Fogalmi ellenőrzés (nehézség: 1)

Fogalmazza meg saját szavaival a uniókorlátot, és magyarázza el, miért lép be az $M$ szorzó a $2Me^{-2n\epsilon^2}$ képletbe. Adjon két olyan $A_1,A_2$ eseményt, amelyre a uniókorlát egyenlőséggel teljesül, és kettőt, amelyre a korlát szigorúan nagyobb a tényleges valószínűségnél. Elvárt eredmény: definíció, az $M$ szorzó eredete és négy konkrét esemény indoklással.

8.2.7.2 F2 — Levezetési alkalmazás (nehézség: 2)

Legyen $M=5000$, $n=2000$, $\delta=0{,}01$. Számítsa ki a (2) képlettel $\epsilon$-t, majd az egyenletes esemény feltételével vezesse le az ERM-hibakorlátot: igazolja, hogy legalább $99\%$ valószínűséggel $R(\hat h)\le R(h^*)+2\epsilon$, és adja meg a $2\epsilon$ számértékét. Elvárt eredmény: $\epsilon$ levezetése, a három egyenlőtlenség mindegyikének indoklása, végső számérték.

8.2.7.3 F3 — Implementációs feladat (nehézség: 2)

Írjon Python függvényt, amely az $(M,n,\delta)$ hármasból a (2) képlet szerint $\epsilon$-t és a $\delta=2Me^{-2n\epsilon^2}$ azonosság numerikus ellenőrzését adja vissza. Tesztelje $(M,n,\delta)=(1000,500,0{,}05)$-re. A kód tartalmazzon típus- és tartományellenőrzést. Elvárt eredmény: futtatható kód, a fenti paraméterre $\epsilon\approx0{,}145579$ és a bound visszaadása $\delta=0{,}05$ körül $10^{-12}$ relatív tolerancián belül.

8.2.7.4 F4 — Hibakeresés (nehézség: 2)

A következő függvény hibás:

def rossz_epsilon(M: int, n: int, delta: float) -> float:
    import math
    return math.sqrt(math.log(M / delta) / (2 * n))

Lokalizálja a hibát, magyarázza el a matematikai következményét a garantált konfidenciaszintre, javítsa a kódot, és $(M,n,\delta)=(1000,500,0{,}05)$-tel mutassa meg, hogy a hibás érték kisebb, mint a helyes $0{,}145579$. Visszaellenőrzésképpen számítsa ki, hogy a hibás $\epsilon$ mellett a $2Me^{-2n\epsilon^2}$ mennyiség mennyivel haladja meg a megcélzott $\delta$-t. Elvárt eredmény: hiba oka, következmény, javított kód és két numerikus kontroll.

8.2.7.5 F5 — Kísérlettervezési/transzfer feladat (nehézség: 3)

Tervezzen Monte Carlo szimulációt annak vizsgálatára, hogy egy konkrét, véges hipotézisosztályon a tényleges maximális eltérés mennyivel kisebb a Hoeffding-unókorlátnál. Válasszon $M=100$ hipotézist, $p_h$ Bernoulli-paraméterekkel a $[0,1]$-beli lossra, $n=200$ mintát, rögzített seedet és $R=5000$ ismétlést. Írja le a protokollt: megfigyelési egység, a mérendő mennyiség (a minta feletti $\max_h|\hat R(h)-R(h)|$ eloszlása), a Hoeffding-baseline, a Monte Carlo becslés standard hibája, és a következtetés érvényességi határa. A feladat nyitott; nem kell futtatni. Elvárt eredmény: legalább egy teljes protokoll, az alternatívák indoka, és annak megfogalmazása, hogy a szimuláció miért nem cáfolhatja az általános tételt.

8.2.8 Megoldások és indoklás

8.2.8.1 F1 megoldása

A uniókorlát: $P(\bigcup_{j=1}^M A_j)\le\sum_{j=1}^M P(A_j)$. A $2Me^{-2n\epsilon^2}$ képletben a $2e^{-2n\epsilon^2}$ egyetlen hipotézisre vonatkozó kudarc-korlát; mivel $M$ hipotézis van, és a rossz esemény az, hogy bármelyik hipotézisre sérül a sáv, a unió valószínűségét a valószínűségek összege korlátozza, ez az $M$-szeres szorzó.

Egyenlőség például: a kockadobásnál $A_1=\{1\}$, $A_2=\{2\}$, ekkor $P(A_1\cup A_2)=\frac26=\frac16+\frac16$. Szigorú egyenlőtlenség: $A_1=\{1\}$, $A_2=\{1\}$, ekkor a unió valószínűsége $\frac16$, az összeg $\frac26$. Egy másik szigorú pár: $A_1=\{\text{páros}\}=\{2,4,6\}$, $A_2=\{1,2\}$; a unió $\{1,2,4,6\}$ valószínűsége $\frac46$, az összeg $\frac36+\frac26=\frac56>\frac46$.

8.2.8.2 F2 megoldása

Behelyettesítünk a (2) képletbe. $\log$ természetes:

$$\epsilon=\sqrt{\frac{\log(2\cdot5000/0{,}01)}{2\cdot2000}}=\sqrt{\frac{\log(10^6)}{4000}}=\sqrt{\frac{13{,}81551}{4000}}\approx\sqrt{0{,}00345388}\approx0{,}05877.$$

Az egyenletes esemény $1-\delta=0{,}99$ valószínűséggel bekövetkezik; ezen az eseményen minden $h\in\mathcal H$-ra $|\hat R(h)-R(h)|<\epsilon$. Az ERM $\hat h$ és a populációs optimum $h^*$ egyaránt $\mathcal H$-beli, ezért (i) $R(\hat h)<\hat R(\hat h)+\epsilon$, hiszen az egyenletes sáv $\hat h$-ra is igaz; (ii) $\hat R(\hat h)\le\hat R(h^*)$, mert $\hat h$ minimalizálja az empirikus kockázatot; (iii) $\hat R(h^*)<R(h^*)+\epsilon$, mert a sáv $h^*$-ra is igaz. Összekapcsolva $R(\hat h)<R(h^*)+2\epsilon$. A számérték $2\epsilon\approx0{,}1175$, tehát legalább $99\%$ valószínűséggel az ERM populációs kockázata legfeljebb $11{,}75$ százalékponttal haladja meg az osztály optimumát.

8.2.8.3 F3 megoldása

A laborban közölt uniform_bound függvény éppen ezt valósítja meg. A $(1000,500,0{,}05)$-re:

M, n, delta = 1000, 500, 0.05
eps, bound = uniform_bound(M, n, delta)
print(eps, bound)
# Kimenet (lab-profil): 0.1029399569316797 0.05000000000000004

Az ellenőrzés abs(bound - delta) <= 1e-12 * max(1.0, delta): a bound a math.exp és a math.log inverz műveletei miatt $0{,}05$ körül lesz $10^{-12}$ relatív hibán belül. Szélsőeset-kontroll: $M\le0$, $n\le0$ vagy $\delta\notin(0,1)$ ValueError-t ad; ez a (2) képlet logaritmusának és a valószínűség-értelmezésnek a tartományellenőrzése.

8.2.8.4 F4 megoldása

A hiba: a függvény $\log(M/\delta)$-t számol $\log(2M/\delta)$ helyett, tehát a kétoldali Hoeffding-korlát $2$-es szorzóját elveszíti. Következmény: az $\epsilon$ érték kisebb lesz, mint a megcélzott $\delta$-hoz tartozó garantált sáv; az így jelentett konfidenciaszint hamis, mert a tényleges kudarc-korlát $\delta$-nál nagyobb.

Javítás: a logaritmus argumentuma (2.0 * M) / delta legyen:

def helyes_epsilon(M: int, n: int, delta: float) -> float:
    import math
    return math.sqrt(math.log((2.0 * M) / delta) / (2.0 * n))

Numerikus kontroll: $(M,n,\delta)=(1000,500,0{,}05)$-re a hibás érték

$$\epsilon_{\text{hib}}=\sqrt{\frac{\log(1000/0{,}05)}{1000}}=\sqrt{\frac{\log(20000)}{1000}}\approx\sqrt{0{,}00990349}\approx0{,}099516,$$

míg a helyes $\epsilon\approx0{,}145579$; a hibás érték valóban kisebb. A hibás $\epsilon$-nal számolt kudarc-korlát

$$2Me^{-2n\epsilon_{\text{hib}}^2}=2000\,e^{-1000\cdot0{,}00990349}\approx2000\,e^{-9{,}90349}\approx0{,}1000,$$

ami a megcélzott $\delta=0{,}05$ kétszerese; az ellenőrzés tehát kimutatja a konfidenciaszint sérülését.

8.2.8.5 F5 megoldásminta

Kérdés: mennyivel kisebb egy konkrét osztályon a tényleges $\max_h|\hat R(h)-R(h)|$, mint a Hoeffding–uniókorlát $\epsilon$ értéke?

Protokoll. Rögzítsük $M=100$ hipotézist; a $h_j$ jelölthöz tartozó loss legyen Bernoulli$(p_j)$, ahol $p_j=j/101$, tehát $R(h_j)=p_j$ ismert. Minden $r=1,\dots,R$ ismétlésben generáljunk $n=200$ független megfigyelést, minden $j$-re a lossokat; a megfigyelési egység az ismétlésenkénti minta, a mért statisztika $T_r=\max_{j=1}^{M}|\hat p_j^{(r)}-p_j|$. A baseline a (2) képletből $M=100$, $n=200$, $\delta=0{,}05$ mellett:

$$\epsilon=\sqrt{\frac{\log(2\cdot100/0{,}05)}{400}}\approx\sqrt{\frac{\log(4000)}{400}}\approx0{,}1439.$$

A becsült túllépési arány $\hat P=\frac1R\sum_{r=1}^R\mathbf 1[T_r\ge\epsilon]$; a standard hiba $\sqrt{\hat P(1-\hat P)/R}$, amely $R=5000$-nél legfeljebb $0{,}0071$. A seed rögzítése (például np.random.default_rng(20261020)) biztosítja az újrafuttathatóságot.

Értelmezési korlát. A szimuláció egyetlen eloszláson mér; nem cáfolhatja az általános tételt, mert a tétel minden $[0,1]$-beli lossra vonatkozó felső korlát. Ha $\hat P$ jóval kisebb $\delta$-nál, az a uniókorlát lazaságát szemlélteti ezen az eloszláson, nem a képlet hibáját. Alternatívák: $p_j$ változtatása, közös megfigyeléseken számolt veszteségek, vagy a maximális eltérés eloszlásának hisztogramja; ezek a korreláció hatását vizsgálnák, de mindegyik csak illusztráció.

8.2.9 Önellenőrzés és fogalmi visszahívás

1. Miért nem elég a rögzített $h$-ra szóló Hoeffding-korlát, ha a legjobb $h$-t ugyanazon a mintán választjuk? Rövid válasz: a választás adaptív, a kiválasztott $h$ függ a mintától, így az egyetlen korlát nem vonatkozik rá; az uniókorlát minden jelöltre egyszerre érvényes.
2. Ha $M$ nő, mi történik $\epsilon$-nal rögzített $n$ és $\delta$ mellett? Nő, logaritmikusan; a korlát egyre lazább.
3. Melyik feltételt sérti a logits-alapú cross-entropy? A $[0,1]$-korlátosságot; a loss tetszőlegesen nagy lehet, tehát a tétel változtatás nélkül nem alkalmazható.

A 8.1. Kockázat, mintavétel és baseline rögzített hipotézisre mondta ki a Hoeffding-korlátot; most azt egyenletessé tettük. A 7.2. Softmax és többosztályos cross-entropy cross-entropy definíciója adta a nem korlátos ellenpéldát. A 4.2. Parciális derivált és gradiens gradiensfogalma itt tudatosan nem szerepel feltételként: a statisztikai garanciához semmilyen differenciálhatóság nem kell, csak korlátosság, iid minta és véges $\mathcal H$.

8.2.10 Rövid összefoglaló

Ha a hipotézisosztály véges, a rögzített hipotézisre szóló Hoeffding-korlátot uniókorláttal minden jelöltre kiterjeszthetjük: $[0,1]$-korlátos loss és $n$ elemű iid minta esetén legalább $1-\delta$ valószínűséggel minden $h$-ra $|\hat R(h)-R(h)|\le\epsilon$, ahol $\epsilon=\sqrt{\log(2M/\delta)/(2n)}$. Ebből az ERM-hibakorlát $R(\hat h)\le R(h^*)+2\epsilon$; ez az adaptív választás első korrekt garanciája. A korlát gyakran túl laza a gyakorlati döntéshez, mert a Hoeffding-lépés és az uniókorlát is konzervatív. Korlátlan cross-entropyra a tétel változtatás nélkül nem alkalmazható.

8.2.11 Következő alkalmazás

A 8.3. Kapacitás, regularizálás és modellválasztás a kapacitást, a regularizálást és a modellválasztást kapcsolja ehhez a korláthoz: a $2Me^{-2n\epsilon^2}$ alak megmutatja, miért növeli a nagyobb hipotézisosztály a statisztikai hibát, és hogyan ellensúlyozhatja a korlátozott keresési tér a mintakorlátot. A következő egység ezt az elvet viszi át a gyakorlati modellválasztási döntésekre.

8.2.12 Források

• [P27] W. Hoeffding (1963). Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association. https://www.tandfonline.com/doi/abs/10.1080/01621459.1963.10500830.
• [S02] NIST/SEMATECH (n.d.). e-Handbook of Statistical Methods: Confidence Limits for the Mean. https://www.itl.nist.gov/div898/handbook/eda/section3/eda352.htm.
• [B01] M. P. Deisenroth, A. A. Faisal és C. S. Ong (2020). Mathematics for Machine Learning. Cambridge University Press. https://mml-book.github.io/.
• [B02] I. Goodfellow, Y. Bengio és A. Courville (2016). Deep Learning. MIT Press. https://www.deeplearningbook.org/.