ALAKFELISMERÉS—HÁZI FELADAT PÉLDÁK

1. Feladat Bizonyítsd be, hogy ha X egy nemnegatív valószínűségi változó , akkor

EX = ∫_{0}^{∞} P{X > t}dt.

2. Feladat Legyenek X_{1}, X_{2}, … korlátos valószínűségi változók , amelyekre P{|X_{n}| ≤ M} = 1 valamely M > 0 számra. Tegyük fel, hogy valamely X valószínűségi változóra, lim_{n→∞} X_{n} = X valószínűségben. Bizonyítsd be, hogy ekkor P{|X| ≤ M} = 1.

3. Feladat Bizonyítsd be, hogy ha X ∈ R^{d} és Y ∈ {0, 1} független valószínűségi változók , akkor L^{∗} = min(p, 1 − p), ahol p = P{Y = 1} és L^{∗} a Bayes hiba. Mutass egy peldát amikor X és Y nem függetlenek, és mégis L^{∗} = min(p, 1 − p).

4. Feladat Bizonyítsd be, hogy ha egy X valószínűségi változó olyan, hogy P{X ∈ [a, b]} = 1, akkor Var{X} ≤ (b − a)^{2}/4.

5. Feladat Legyen X′ = (X_{1}, X_{2}) és jelölje L_{X_{1}}^{∗} az X_{1} megfigyelésére alapozott, az Y bináris valószínűségi változóra adott Bayes döntés hibáját. Legyen L_{X′}^{∗} hasonlóan, az X_{1} és X_{2} együttes megfigyelésére alapozott Bayes hiba. Bizonyítsd be, hogy L_{X_{1}}^{∗} ≥ L_{X′}^{∗}, illetve, ha X_{2} független (X_{1}, Y)-tól, akkor L_{X_{1}}^{∗} = L_{X′}^{∗}.

6. Feladat (Döntés visszautasítással.) Némely döntési feladatban megengedett, hogy azt mondjuk, hogy “nem tudom”, ha ez nem túl gyakran történik. Formálisan, egy döntésfüggvény három értéket vehet fel: 0, 1 és “nem tudom”. Ekkor két valószínűség méri a döntés jóságát: a visszautasítás valószínűsége P{g(X) = “nem tudom”}, illetve a hibavalószínűség P{g(X) ≠ Y |g(X) ≠ “nem tudom”}. Egy 0 < c < 1/2 számra definiáljuk a következő döntést:

g_{c}(x) = \{ \begin{matrix}1 & ha η(x) > 1/2 + c \\ 0 & ha η(x) ≤ 1/2 − c \\ “nem tudom” & egyébként. \end{matrix}

Mutasd meg, hogy ez a döntés optimális olyan értelemben, hogy ha bármely más g döntésre igaz, hogy

P{g(X) = “nem tudom”} ≤ P{g_{c}(X) = “nem tudom”},

akkor

P{g(X) ≠ Y |g(X) ≠ “nem tudom”} ≥ P{g_{c}(X) ≠ Y |g_{c}(X) ≠ “nem tudom”}.

Más szóval, a visszautasítás valószínűségét egy bizonyos szint alatt tartó döntések közül a minimális hibavalószínűségű döntés g_{c} alakú (valamilyen c-re).

7. Feladat Mutasd meg, hogy bármely két döntésre |L(g_{1}) − L(g_{2})| ≤ P{g_{1}(X) ≠ g_{2}(X)}. Mikor áll fenn egyenlőség?

8. Feladat Tegyük fel, hogy az X valószínűségi változó olyan, hogy minden ϵ > 0-ra

P{X > ϵ} ≤ ce^{−nϵ}.

Mutasd meg, hogy

EX ≤ \frac{log c + 1}{n}.

9. Feladat Legyen X ∈ {0, 1}^{d}, és tegyük fel, hogy Y = g(X), ahol g egy Boole monom (egytagú polinom), azaz

g(x) = x^{(i_{1})}x^{(i_{2})} ⋯ x^{(i_{k})}

valamely i_{1}, …, i_{k} ≤ d indexekre, ahol x^{(i)} az x vektor i-edik bitjét jelöli. Vagyis g(x) értéke pontosan akkor egy, ha az x vektor i_{1}, …, i_{k}-adik bitjeinek értéke mind egy. A tanítóadat n darab véletlenül sorsolt X_{i} vektorból, és a hozzájuk tartozó Y_{i} = g(X_{i})-ből áll. Legyen g_{n} az a monom, amelyet definiáló i_{j} koordináták éppen azok, amely pozícióban minden olyan X_{i} vektor, amelyre Y_{i} = 1, egyes. Az órán tanult tétel felhasználásával mutasd meg, hogy

P\{L(g_{n}) > ϵ\} ≤ 2^{d}e^{−nϵ}, és EL(g_{n}) ≤ \frac{d log 2 + 1}{n}.

10. Feladat Legyen B egy binomiális eloszlású valószínűségi változó n és p paraméterekkel, azaz B = ∑_{i=1}^{n} I_{A_{i}}, ahol A_{1}, …, A_{n} független események, és P{A_{i}} = p minden i-re. Mutasd meg a Chernoff technika felhasználásával, hogy bármely k ≥ np = m számra

P\{B > k\} ≤ (\frac{m}{k})^{k} e^{k−m}.

Útmutatás: E [e^{sI_{A_{i}}} ] ≤ e^{p(e^{s}−1)}. (Miért?)

11. Feladat Terjeszd ki az előző feladatot állítását tetszőleges [0, 1]-beli független valószínűségi változók összegére. Pontosabban, legyen B = ∑_{i=1}^{n} X_{i}, ahol X_{i} ∈ [0, 1], és ∑_{i=1}^{n} p_{i} = m, ahol p_{i} = EX_{i}. Ekkor k ≥ m esetén

P\{B > k\} ≤ (\frac{m}{k})^{k} e^{k−m}.

Útmutatás: Hasonlóan a Hoeffding egyenlőtlenség bizonyításához, használd az e^{sx} függvény konvexitását.

12. Feladat Legyen most B egy m paraméterű Poisson eloszlású valószínűségi változó , azaz P{B = i} = m^{i}e^{−m}/i!, ha i = 0, 1, 2, . . .. Mutasd meg a Chernoff technika segítségével, hogy

P\{B > k\} ≤ (\frac{m}{k})^{k} e^{k−m}.

Ez a korlát akkor érdekes, ha visszaemlékszel, hogy hogyan lehet a binomiális eloszlást Poissonnal közelíteni. Útmutatás: Itt a Chernoff felső korlát pontosan minimalizálható s-ben. Használd fel, hogy ∑_{i=0}^{∞} x^{i}/i! = e^{x}.

13. Feladat Tegyük fel, hogy az X valószínűségi változó feltételes eloszlása mind az {Y = 0}, mind az {Y = 1} feltétel mellett d dimenziós normális, azaz a két feltételes sűrűségfüggvény a következő alakú:

f_{i}(x) = f(x|Y = i) = \frac{1}{\sqrt{(2π)^{d} det Σ_{i}}} e^{− \frac{1}{2} (x−m_{i})^{T} Σ_{i}^{−1}(x−m_{i})}, i = 0, 1,

ahol m_{i} = E{X|Y = i} az i-edik osztályhoz tartozó várható érték vektor, és Σ_{i} a megfelelő kovarianciamátrix, amely j-edik sorának k-adik eleme E{(X^{(j)} −m_{i}^{(j)})(X^{(k)} −m_{i}^{(k)})}. Mutasd meg, hogy a Bayes döntés kvadratikus. Mutasd meg, hogy abban a speciális estben, amikor Σ_{0} = Σ_{1} és a két osztály a priori valószínűsége megegyezik, a Bayes döntés lineáris.

14. Feladat Legyen d = 1, és tekintsük azokat a döntésfüggvényeket, amelyek kettévágják a számegyenest, azaz, amelyek

g_{a}(x) = \{ \begin{matrix}0 & ha x ≤ a \\ 1 & ha x > a \end{matrix} vagy \{ \begin{matrix}0 & ha x ≥ a \\ 1 & ha x < a \end{matrix}

alakúak. Mutasd meg, hogy ha L az ilyen döntések hibavalószínűsége közül a minimális, akkor L ≤ min{p, 1 − p}, ahol p = P{Y = 1}.

15. Feladat Mutasd meg, hogy ha p = 1/2, akkor az előző feladatbeli L számra:

L = \frac{1}{2} (1 − sup_{x} |F_{1}(x) − F_{0}(x)|) ,

ahol F_{0}(x) = P{X ≤ x|Y = 0} és F_{1}(x) = P{X ≤ x|Y = 1} a két osztályhoz tartozó feltételes eloszlásfüggvény. Vond le a következtetést, hogy L = 1/2 akkor és csak akkor, ha L^{∗} = 1/2.

16. Feladat A gyakorlatban gyakran nehéz megtalálni az empirikus minimumot szolgáltató döntésfüggvényt, és helyette egy közelítő megoldást kell használni. Legyen tehát C döntésfüggvények egy osztálya, és g̃_{n} egy olyan osztályozási szabály, amelyre valamely ϵ_{n} és δ_{n} számokra,

P {L̂_{n}(g̃_{n}) ≤ L̂_{n}(g_{n}^{∗}) + ϵ_{n}} ≥ 1 − δ_{n},

ahol g_{n}^{∗} egy az empirikus hibat minimalizáló döntés. (L̂_{n} jelöli az empirikus hibát.) Más szóval, g̃_{n} közel minimalizálja az empirikus hibát nagy valószínűséggel. Bizonyítsd be, hogy minden ϵ ≥ ϵ_{n}-re

P {L(g̃_{n}) − inf_{g∈C} L(g) > ϵ} ≤ δ_{n} + P {2 sup_{g∈C} |L̂_{n}(g) − L(g)| > ϵ − ϵ_{n}} .

17. Feladat “Fingering” téglákra. Tegyük fel, hogy az (X, Y) pár eloszlása olyan, hogy L^{∗} = 0, az X-nek létezik a sűrűségfüggvénye, és a Bayes döntés olyan alakú, hogy egy téglán (d dimenziós intervallumon) belül 1, azon kívül nulla. Tegyük fel, hogy adott n független mintánk ebből az eloszlásból. Tekintsük azt a g_{n} osztályozási szabályt, amely nulla azon a legkisebb téglán belül, amely tartalmazza az összes 1-es cimkéjű mintapontot, és a téglán kívül 0. Bizonyítsd be, hogy

P{L(g_{n}) > ϵ} ≤ n^{2d}e^{−(n−2d)ϵ}.

Útmutatás: használd az órán tanult “fingering” módszert.

18. Feladat Legyen A és B két tetszőleges valószínűségi változó , x, y pedig két valós szám. Mutasd meg, hogy

P{A + B > x + y} ≤ P{A > x} + P{B > y}.

19. Feladat Legyen A = {[a, b] : a ≤ b}, azaz a számegyenes összes zárt intervallumának családja. Mennyi s(A, n), az A n-edik shatter koefficiense?

20. Feladat Legyen A_{k} a k intervallum úniójaként felírható halmazok családja. Mennyi az A_{k} Vapnik-Chervonenkis dimenziója?

21. Feladat Legyen A az R^{d}-beli szimplexek (d+1 csúcsú testek) családja. Mekkora az A Vapnik-Chervonenkis dimenziója? (Legalább egy jó felső becslést adj!)

22. Feladat Adj felső becsléseket a következő halmazcsaládok Vapnik-Chervonenkis dimenziójára:

(1) konvex k-szögek a síkon. (2) k-szögek a síkon.

23. Feladat Legyen A az R^{d}-beli intervallumok (téglák) családja. Mutasd meg, hogy V_{A} = 2d.

24. Feladat A sík egy A ⊂ [0, 1]^{2} részhalmazát monoton rétegnek nevezzük, ha igaz az, hogy ha egy x pont eleme A-nak, akkor bármely y ≤ x pont is eleme A-nak, ahol az y ≤ x reláció úgy értendő, hogy y mindkét koordinátája nem nagyobb, mint az x megfelelő koordinátája. Mutasd meg, hogy az összes monoton réteget tartalmazó halmazosztálynak végtelen a Vapnik-Chervonenkis dimenziója.

25. Feladat Legyen

A = {{x : ∑_{i=1}^{d} a_{i}x^{(i)} ≥ 0}; a_{1}, …, a_{d} ∈ R} ,

azaz az origón átmenő hipersíkokkal definiált félterek családja. Bizonyítsd be, hogy minden n-re

s(A, n) = 2 ∑_{i=0}^{d−1} \binom{n − 1}{i},

és hogy V_{A} = d. Útmutatás: Használj teljes indukciót d és n szerint. Ez egy nehéz példa.

26. Feladat Mutasd meg, hogy a shatter koefficiens es a VC dimenzió között fennálló s(A, n) ≤ ∑_{i=0}^{V_{A}} \binom{n}{i} egyenlőtlenség éles, vagyis minden V pozitív egész számra mutass egy olyan A halmazosztályt, amelynek az n-edik shatter koefficiensére s(A, n) = ∑_{i=0}^{V_{A}} \binom{n}{i} teljesül minden n-re! Útmutatás: Legyen A az összes legfeljebb V pontú halmaz osztálya.

27. Feladat Egy egy rejtett rétegű neurális hálózat (l. ábra) egy függvény R^{d} → R, amely a következő alakba írható:

ψ(x) = c_{0} + ∑_{i=1}^{k} c_{i}σ(ψ_{i}(x)),

ahol x = (x^{(1)}, …, x^{(d)})^{T}, a bemenet vektor, σ az ugrásfüggvény: σ(x) = −1 ha x < 0, és σ(x) = 1 ha x ≥ 0, továbbá

ψ_{i}(x) = b_{i} + ∑_{j=1}^{d} a_{i,j}x^{(j)}.

Tekintsük azon halmazok A családját, amelyek {x : ψ(x) > 0} alakúak, ahol az a_{i,j}, b_{i} és c_{i} paraméterek tetszőleges valós értékeket vehetnek fel. Mutasd meg, hogy s(A, n) ≤ (n+1)^{k(d+1)+k+1}. Útmutatás: Emlékezz vissza, hogy n pontot R^{d}-ben lineáris félterekkel legfeljebb n^{d+1}-féleképpen lehet kettévágni.

28. Feladat Mutasd meg, hogy páros k esetén a fent definiált halmazosztály VC dimenziója nem nagyobb, mint kd. Útmutatás: Azt kell tehát belátni, hogy kd pont shatterelhető. Vegyünk kd általános helyzetű pontot. Feltehetjük, hogy a kiválasztandó halmaz legfeljebb kd/2 elemű. Osszuk be a pontokat k/2 legfeljebb d pontot tartalmazó csoportba. Minden ilyen d pontra ráfektethetünk egy hipersíkot, amely csakis ezeket a pontokat tartalmazza. Két neuron súlyainak megfelelő beállításával a ψ függvény értéke pozitívvá tehető ezeken a pontokon...

29. Feladat Legyenek η̃_{0}, η̃_{1} : R^{d} → [0, 1] tetszőleges függvények, és definiáljuk a g döntést a következőképp:

g(x) = \{ \begin{matrix}1 & ha η̃_{1}(x) ≥ η̃_{0}(x) \\ 0 & egyébként. \end{matrix}

Bizonyítsd be, hogy

P{g(X) ≠ Y } − L^{∗} ≤ E|η(X) − η̃_{1}(X)| + E|1 − η(X) − η̃_{0}(X)|.

30. Feladat Jelölje f_{0}(x) és f_{1}(x) az X feltételes sűrűségfüggvényét az {Y = 0}, illetve {Y = 1} feltételekkel. Legyen továbbá q_{0} = P{Y = 0}, q_{1} = P{Y = 1}. Mutasd meg, hogy a Bayes döntés

g^{∗}(x) = \{ \begin{matrix}1 & ha q_{1}f_{1}(x) ≥ q_{0}f_{0}(x) \\ 0 & egyébként \end{matrix}

alakú. Mutasd meg továbbá, hogy a

g(x) = \{ \begin{matrix}1 & ha q̃_{1}f̃_{1}(x) ≥ q̃_{0}f̃_{0}(x) \\ 0 & egyébként \end{matrix}

dönésre

P{g(X) ≠ Y } − L^{∗} ≤ ∫ |q̃_{0}f̃_{0}(x) − q_{0}f_{0}(x)| dx + ∫ |q̃_{1}f̃_{1}(x) − q_{1}f_{1}(x)| dx

teljesül.

31. Feladat Legyenek U, V és Z diszkrét valószínűségi változók úgy, hogy Z független (U, V)-től. Bizonyítsd be, hogy

E{f(U)|V, Z} = E{f(U)|V }.

32. Feladat Bizonyítsd be, hogy az 1-nn szabály admisszibilis. Ez azt jelenti, hogy létezik az (X, Y) párnak egy olyan eloszlása, amelyre az 1-nn szabály várható hibavalószínűsége EL(g_{n}) minden n-re szigorúan \underline{kisebb}, mint a k-nn szabályé, minden k > 1-re. Útmutatás: Legyen X egyenletes eloszlású a [0, 1] ∪ [3, 4] halmazon és legyen Y = 0 ha X ∈ [0, 1] és Y = 1 ha X ∈ [3, 4]. Ekkor az 1-nn szabály csak akkor hibázik, ha a [0, 1] és [3, 4] intervallumok egyikébe egy adatpont sem esik.

33. Feladat Legyen P{Y = 0} = P{Y = 1} = 1/2, és legyenek az X feltételes sűrűségfüggvényei Y = 0 illetve Y = 1 feltétellel f_{0}(x) = 2x és f_{1}(x) = 2 − 2x ha x ∈ [0, 1] és f_{0}(x) = f_{1}(x) = 0 ha x ∉ [0, 1]. Számítsd ki a Bayes hibát, és az 1-nn és 3-nn szabályok aszimptotikus hibavalószínűségét!

34. Feladat Mutasd meg, hogy ha X_{(1)} az X legközelebbi szomszédja X_{1}, …, X_{n} között, akkor ∥X − X_{(1)}∥ nullához tart valószínűségben, ahogy n → ∞. Útmutatás: Rögzített X = x esetén ∥x − X_{(1)}∥ > ϵ pontosan azt jelenti, hogy

\frac{1}{n} ∑_{i=1}^{n} I_{\{X_{i}∈S_{x,ϵ}\}} < \frac{1}{n},

ahol S_{x,ϵ} az x középpontú ϵ sugarú gömböt jelöli. Ha μ(S_{x,ϵ}) > 0, akkor a nagy számok törvénye szerint a bal oldal egy pozitív számhoz konvergál.

35. Feladat Egydimenziós (d = 1) osztályozási feladatok esetén a k-spacing osztályozási szabályt a következőképpen definiáljuk: legyen k < n egy pozitív egész szám, és legyen X_{(1)}, X_{(2)}, …, X_{(n)} az X_{1}, …, X_{n} adatpontok nagyság szerinti sorbarendezése, azaz X_{(1)} ≤ X_{(2)} ≤ ⋯ ≤ X_{(n)}. (Tegyük fel, hogy X-nek létezik a sűrűségfüggvénye, tehát a sorbarendezés egy valószínűséggel egyértemű.) A számegyenest N intervallumra particionáljuk: A_{1}, …, A_{N}, ahol N = ⌈n/k⌉, és j = 1, …, N −1-re

X_{(k(j−1)+1)}, …, X_{(kj)} ∈ A_{j},

továbbá

X_{(k(N−1)+1)}, …, X_{(n)} ∈ A_{N}.

Helyezzük az A_{j} és A_{j+1} intervallumok határát az A_{j}-beli legjobboldalibb és az A_{j+1}-beli legbaloldalibb adatpont közötti felezőpontba. Az osztályozási szabály ekkor többségi döntés az egyes halmazokon belül (l. ábra) , vagy precízebben:

g_{n}(x) = \{ \begin{matrix}1 & if ∑_{i=1}^{n} I_{\{X_{i}∈A(x),Y_{i}=1\}} > ∑_{i=1}^{n} I_{\{X_{i}∈A(x),Y_{i}=0\}} \\ 0 & otherwise, \end{matrix}

ahol A(x) az x-et tartalmazó intervallumot jelöli.

Mutasd meg, hogy g_{n} univerzálisan konzisztens, ha k → ∞ és k/n → 0 ahogy n → ∞.

Útmutatás: használd a partíciós szabályokra kimondott általános konzisztenciatételt.

36. Feladat Legyen d = 2. Vegyük az X_{1}, …, X_{n} adatpontok közül az első k darabot (k < n), és kössünk össze bármely két pontot. (Az ábrán ez k = 4 pontra látszik.) Az egyenesek a síkot 1 + k(k + 1)/2 halmazra particionálják. (Miért?) (Feltehetjük, hogy X-nek létezik a sűrűségfüggvénye.)

A maradék n − k pont segítségével definiálhatunk egy osztályozási szabályt, amely többségi döntést hoz a partíció halmazai fölött. Mutasd meg, hogy a kapott szabály univerzálisan konzisztens, ha k → ∞ és k^{2}/n → 0 ahogy n → ∞.

Útmutatás: használd a partíciós szabályokra kimondott általános konzisztenciatételt.