Bevezetés a matematikai statisztikába [PDF]

Zitiervorschau

Bevezetes a matematikai statisztikaba Dr. Ketskemety Laszlo, Pinter Marta Budapest, 1999. november 1.

Lektoralta: Dr. Gyor Laszlo Szerkesztette: Gy}ori Sandor

2

Tartalomjegyzek 1. A matematikai statisztika alapfogalmai 2. Becsleselmelet 2.1. 2.2. 2.3. 2.4. 2.5.

Torztatlan, konzisztens becsles Hatasos becslesek . . . . . . . . Elegsegesseg . . . . . . . . . . . Maximum-likelihood becsles . . Intervallumbecslesek . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

3. Hipotezisvizsgalat

3.1. Alapfogalmak . . . . . . . . . . . . . . 3.2. Neyman{Pearson- es Stein-lemma . . . 3.3. Parameteres probak . . . . . . . . . . 3.3.1. Egymintas u-proba . . . . . . . 3.3.2. A ketmintas u-proba . . . . . . 3.3.3. Az egymintas t-proba . . . . . 3.3.4. A ketmintas t-proba . . . . . . 3.3.5. Az F-proba . . . . . . . . . . . 3.3.6. A Welch-proba . . . . . . . . . 3.4. Nemparameteres probak . . . . . . . . 3.4.1. 2 -probak . . . . . . . . . . . . 3.4.2. Kolmogorov{Szmirnov-probak .

4. Regresszioanal zis

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

4.1. Veletlen meggyeles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1. Linearis regresszio ket valtozo kozott . . . . . . . . . . . . . . . . . . . . 4.1.2. Polinomialis regresszio . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.3. Linearisra visszvezethet}o ketparameteres regresszios osszefuggesek keresese . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.4. A regresszios illeszkedes josaganak merese . . . . . . . . . . . . . . . . . 4.2. Tervezett (determinisztikus) meggyeles . . . . . . . . . . . . . . . . . . . . . . 4.3. Sztochasztikus approximacio . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1. Linearis regresszios feladat . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.2. Negyzetes hiba minimalizalasa . . . . . . . . . . . . . . . . . . . . . . .

5. Eloszlasbecsles

5 9

9 16 24 28 36

43

43 44 49 49 51 51 52 53 54 54 54 59

61

61 61 63

64 65 66 70 73 74

77

5.1. Eloszlasfuggveny becslese . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 5.2. Vapnik{Chervonenkis-elmelet . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 3

4

Tartalomjegyzek

6. S}ur}usegf uggveny becslese

87

7. Regressziobecsles

95

6.1. Az L1 hiba . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 6.2. A hisztogram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

7.1. A regresszios problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 7.2. Lokalis atlagolason alapulo becsl}ok . . . . . . . . . . . . . . . . . . . . . . . . . 96 7.3. Empirikus hibaminimalizalas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

8. Alakfelismeres

107

Ajanlott irodalom

115

8.1. A Bayes-dontes es kozeltese . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 8.2. Lokalis tobbsegen alapulo dontesek . . . . . . . . . . . . . . . . . . . . . . . . . 109 8.3. Empirikus hibaminimalizalas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

1. fejezet

A matematikai statisztika alapfogalmai A valoszn}usegszamtas elmeleteben az ( F P) Kolmogorov valoszn}usegi mez}on fogalmaztuk meg a teteleinket, azaz a P valoszn}usegi merteket vegig adottnak teteleztuk fel. A gyakorlati problemaknal azonban a valoszn}useg nem ismert, legfeljebb logikus el}ofeltetelezeseink vannak rola. A matematikai statisztika alapfeladata eppen az, hogy a veletlen kserletre, vagy a veletlen tomegjelensegre vonatkozo meggyelessorozat segtsegevel kovetkeztetni tudjunk a jelenseghez tartozo adekvat valoszn}usegi mertekre vagy annak egy jellemz}ojere, azt megfelel}o pontossaggal kozelteni tudjuk. Ilyen ertelemben a veletlen jelensegek matematikai modellezesenel a matematikai statisztika modszerei megel}ozik a valoszn}usegszamtas modszereit. A matematikai statisztika fogalomkore, modszertana viszont a valoszn}usegszamtas fogalmain es modszerein alapul, es ilyen szempontbol a matematikai statisztika koveti a valoszn}usegszamtast. Ugyanugy, mint a valoszn}usegszamtasnal, a veletlen kserlet (K) alapfogalmabol indulunk ki. Azt is feltesszuk, hogy ismert az elemi esemenyek  halmaza es az esemenyek F halmazrendszere. A P valoszn}useg pontosan nem ismert, csak azt tudjuk, hogy a K veletlen kserlethez tartozo valoszn}useg eleme egy P halmaznak. Tehat 8P 2 P eseten Kolmogorovfele valoszn}usegi mez}ot kapunk. A matematikai statisztika alapfeladata ezen P halmazbol kivalasztani azt a valoszn}usegi merteket, amely tenylegesen a kserlethez tartozik. A P valoszn}usegi mertekosztalyra esetenkent szokasos bizonyos megkotesekkel elni. Ilyen pl. az, amikor P-t dominaltnak tetelezzuk fel valamilyen adott  -veges mertekre nezve. Ezen azt ertjuk, hogy adott az ( F) merhet}o teren olyan  -veges mertek, amelyre 8P 2 P abszolut folytonos, azaz ha valamely A 2 F eseten  (A) = 0, akkor P (A) = 0 is 8P 2 P-re. A K veletlen kserlethez meggyelessorozatot szervezunk, azaz adatokat gy}ujtunk. Matematikailag ezt ugy fogalmazzuk meg, hogy adottnak tetelezunk fel egy X1  : : :  Xn Rd ertek}u fuggetlen, azonos eloszlasu valoszn}usegi vektorvaltozo sorozatot, amelyet statisztikai mintanak nevezunk. A P 2 P valoszn}useg eseten a minta kozos eloszlasa X (A) = P(X1 2 A) lesz, ahol A 2 Bd d-dimenzios Borel-halmaz. Tehat minden P 2 P eseten (Rd  Bd  X ) Kolmogorov-fele valoszn}usegi mez}o lesz. Jelolje QX ezen X eloszlasok osztalyat. Az (Rnd  Bnd  QX ) harmast statisztikai mez}onek nevezzuk. A statisztikai vizsgalatok celja ezutan az, hogy a QX eloszlascsaladbol valasszuk ki az X1  : : :  Xn mintahoz tartozo eloszlast. Statisztikai modellekben altalaban adott egy # : QX ! Rk funkcional, amelynek erte(2) keit akarjuk minel pontosabban megbecsulni. Ha teljesul, hogy #((1) X ) 6= #(X ) eseten (2) (1) X 6= X , a # funkcionalt parameternek (parametervektornak) nevezzuk. Ilyenkor a #-nak megfelel}o eloszlast # -val fogjuk jelolni: QX = f#  # 2 g, ahol  a parameterter, azaz a # 5

6

1. FEJEZET A matematikai statisztika alapfogalmai

lekepezes ertekkeszlete. Parameteres problema dominalt statisztikai mez}o eseten praktikusan azt jelenti, hogy a minta eloszlasa valamilyen parametert}ol fugg}o diszkret vagy folytonos eloszlascsaladbol szarmazhat csak. Peldaul, ha feltesszuk, hogy a mintank eloszlasa normalis, akkor a # = (m D) parametervektor egyertelm}uen meghatarozza a

8 Z < QX = :# : # (B ) = B

9 = dnmD (x)

ketparameteres eloszlasosztalyt, ahol

Yn Zxi 1 ; (t2;Dm2 ) n p e mD (x) = dt: i=1;1 2D

Abban az esetben viszont, ha ilyen # parameterfuggveny nem ismert, a statisztikai mez}o es a rajta megfogalmazott problemak nemparameteresek. Peldaul, ha feltesszuk, hogy R az X sta  tisztikai minta 8P 2P eseten veges varhato ertekkel rendelkezik, azaz jEP X1 j =  X1 dP <  1 8P 2P-re. Ilyenkor a # (P) = EP X1 funkcional nem feltetlenul parameter, # jo becslese nem jelenti meg jo valoszn}usegi mertek megvalasztasat. Adott tovabba egy t : Rn ! Rk merhet}o lekepezes, melyet statisztikai fuggvenynek nevezunk. A t(X1  X2  : : :  Xn ) osszetett fuggveny a statisztika. A statisztika tehat nem mas, mint 8P 2 P eseten egy valoszn}usegi vektorvaltozo az ( F P) Kolmogorov-fele valoszn}usegi mez}on.

1.1. den cio: Legyen ( F) merhet}o ter, es P valoszn}usegi mertekek egy halmaza, ahol P eseten ( F P) Kolmogorov-fele valoszn}usegi mez}o. Az X = (X1  X2  : : :  Xn )T

8P 2

statisztikai meggyelest statisztikai mintanak nevezzuk, ha Xi -k teljesen fuggetlen, azonos eloszlasu valoszn}usegi valtozok 8P 2 P eseten ( F P)-n, azaz 8P 2 P-re

P(Xi < x) = FP (x)

(i = 1 2 3 : : :  n)

es

P(Xi < xi  Xi < xi  : : :  Xik < xik ) = 1

1

2

2

Yk =1

FP (xi )

(82  k  n):

n a minta elemszama, FP (x) a minta eloszlasfuggvenye, Xi az i-edik mintaelem, P (A) =

P(Xi 2 A), A 2 Bd a minta eloszlasa. Egy ! 2  eseten az

X1 (!) = x1 X2 (!) = x2  : : :  Xn (!) = xn szam n-es a minta egy realizacioja. Megjegyzes :

1. Amikor egy statisztikai modszert alkalmazunk, mindig egy statisztikai minta realizaltja all a rendelkezesunkre. Ez a szam n-es azonban a veletlent}ol fugg, hiszen ha megismetelnenk a mintavetelezest, egeszen biztos, hogy mas adatokhoz jutnank. A modszerek elmeletenek targyalasakor ezert a mintat fuggetlen, azonos eloszlasu valoszn}usegi valtozok sorozatanak tekintjuk.

7 2. Ha az X statisztikai minta,  a Lebesgue-mertek, akkor a P eloszlasosztaly dominaltsaga most azt jelenti, hogy a minta abszolut folytonos, azaz 8P 2P eseten letezik a minta s}ur}usegfuggvenye, amelyet fP (x)-szel jelolunk. Ha viszont  a szamlalo mertek, vagyis  (B ) azt adja meg, hogy a B halmazban mennyi elem van a minta megszamlalhato ertekkeszleteb}ol, a P dominaltsaga -ra nezve azt jelenti, hogy a statisztikai minta eloszlasa diszkret.

8

1. FEJEZET A matematikai statisztika alapfogalmai

2. fejezet

Becsleselmelet 2.1. Torztatlan, konzisztens becsles Legyen P = fPg egy parameteres valoszn}usegi mertek-csalad. Feladat olyan tn(X1  X2  : : :  Xn ) 2 Rk (n = 1 2 : : :) statisztikasorozat megadasa, amely segtsegevel "jol" tudjuk becsulni a # parametervektort. Ha a parametert "pontosan" meg tudjuk becsulni, akkor ez egyben azt is jelenti, hogy az adekvat # eloszlast is kozelt}oleg megkapjuk. Az alabbiakban az elvarando "jo", "pontos" becslesi tulajdonsagokat denialjuk.

2.1.1. den cio: A tn(X1  X2  : : :  Xn ) 2 Rk statisztika a # 2 Rk parameter torztatlan becslese, ha 8P 2 P eseten a tn -nek mint valoszn}usegi vektorvaltozonak letezik varhatoertekvektora es EP tn = # (P) : Megjegyzes :

1. Az EP tn azt jeloli, hogy a varhatoertek-vektor fugg attol, hogy melyik P valoszn}usegi mertek alapjan szamoljuk az



(2) (k ) Ftn (x1  x2  : : :  xk ) = P t(1) n < x1  tn < x2  : : :  tn < xk



eloszlasfuggvenyt, majd abbol a varhato erteket. 2. Tudjuk, hogy egy valoszn}usegi valtozo ertekei a varhato erteke korul ingadoznak, tehat, hogy egy statisztika a parameter torztatlan becslese, azt az elvarhato tulajdonsagot fejezi ki, hogy a becslesi statisztika realizaltjai az ismeretlen parameter korul ingadoznak a parameterterben.

2.1.2. den cio: A tn(X1  X2  : : :  Xn) 2 Rk statisztikasorozat a # 2 Rk parameter aszimptotikusan torztatlan becslese, ha 8P 2 P eseten a tn -nek, mint valoszn}usegi vektorvaltozonak letezik varhatoertek-vektora es nlim !1 EP tn = # (P) : A torztatlansagbol nyilvanvaloan kovetkezik az aszimptotikusan torztatlansag, tehat ez utobbi a gyengebb tulajdonsag.

2.1.3. den cio: A tn(X1  X2  : : :  Xn ) 2 Rk statisztikasorozat a # 2 Rk parameter konst #, t zisztens becslese, ha 8P 2 P es 8" > 0 eseten nlim P ( ktn ; #k > ") = 0, azaz tn ;! n !1

sztochasztikusan konvergal a # parameterhez.

9

10

2. FEJEZET Becsleselmelet Megjegyzes :

1. A konzisztencia mas kovetelmenyt fejez ki, mint a torztatlansag. A konzisztencia tulajdonsaga azt a jogos elvarast fogalmazza meg, hogy a meggyelesek szamanak novekedtevel javuljon a becsles pontossaga.



2

Pk 

2



2

t(nj) ; #j   ezert a valo2. Mivel t(ni) ; #i   t(nj ) ; #j  = ktn ; #k2  k  1max  j  k j =1 szn}usegi vektorvaltozo sztochasztikus konvergenciaja ekvivalens a koordinantankenti sztochasztikus konvergenciaval. 2.1.4. den cio: A tn(X1  X2  : : :  Xn ) 2 Rk statisztikasorozat a # 2 Rk parameter negy2 zetes kozepben konzisztens becslese, ha nlim !1 EP jjtn ; #jj = 0. 2.1.1. tetel: Ha a tn (n = 1 2 : : :) statisztikasorozat negyzetes kozepben konzisztens becslese #-nak, akkor konzisztens becslese is. Bizonytas : A Markov-egyenl}otlensegb}ol:



P ktn ; #k2 > "2

E#jjtn ; #jj2 !0  "2

(n ! 1):

2.1.2. tetel: Ha a tn (n = 1 2 : : :) statisztikasorozat aszimptotikusan torztatlan becslese (i) #-nak es nlim !1  P tn = 0 (i = 1 2 : : :  k), akkor konzisztens becslese is. Bizonytas :

EP (t(ni) ; #i)2 = EP(t(ni) ; EPt(ni) + EPt(ni) ; #i)2 = h i = EP (t(ni) ; EP t(ni) )2 + (EP t(ni) ; #i )2 + 2EP (t(ni) ; EP t(ni) )(EP t(ni) ; #i) = =  2P (t(ni) ) + (EP t(ni) ; #i )2 ! 0 n ! 1:

Viszont a Markov-egyenl}otlenseg szerint:

(i)    2 P t(ni) ; #i > " = P (t(ni) ; #i)2 > "2  EP(tn"2; #i) ! 0

amib}ol mar kovetkezik az alltas.

Az

2.1.1. pelda: (Varhato ertek becslese) X n = n1

n X i=1

Xi

statisztikat az X1  X2  : : :  Xn statisztikai minta atlag- vagy empirikus kozep statisztikajanak nevezzuk. Legyen az X valoszn}usegi valtozo adott. Tegyuk fel, hogy 8P 2 P-re 9EPX . Legyen most a parameter # = #(P) = EP X . Legyen tovabba X1  X2  : : :  Xn  : : : statisztikai minta, amelynek eloszlasfuggvenye X -evel azonos 8P 2 P-re. Akkor

2.1

11

Torztatlan, konzisztens becsles

P (i) Az X n = n1 Xi empirikus kozep statisztika a # varhato ertek torztatlan becslese. n

i=1

(ii) Ha a feltetelekhez azt is hozzavesszuk, hogy 8P 2 P-re  2P X < 1 is, ugy X n negyzetes kozepben konzisztens becsles is. Bizonytas :





Pn Pn (i) EP X n = EP n1 Xi = n1 EP Xi = n1 n# = #: i=1 i=1

Pn  ;

Pn 2 2 2   (ii) EP Xn ; # =  P Xn = P n1 Xi = n1  2P Xi = n1 n 2P X = PnX ! 0: 2

2

i=1

Az

i=1

2

2.1.2. pelda: (Szorasnegyzet becslese) s2n =

n 1X  2 n (Xi ; Xn) i=1

statisztikat az Xp1  X2  : : :  Xn statisztikai minta empirikus szorasnegyzet statisztikajanak nevezzuk. sn = + s2n az empirikus szoras statisztika. Az

sn2 = n ;1 1

n X i=1

(Xi ; X n )2

statisztikat az X1  X2  : :p :  Xn statisztikai minta korrigalt empirikus szorasnegyzet statisztika janak nevezzuk. sn = + sn2 a korrigalt empirikus szoras statisztika. Legyen az X valoszn}usegi valtozo adott. Tegyuk fel, hogy 8P 2 P-re  2P X < 1. Legyen most a parameter # = #(P) =  2P X . Legyen tovabba X1  X2  : : :  Xn  : : : statisztikai minta, amelynek eloszlasfuggvenye X -evel azonos 8P 2 P-re.

Pn

(i) Az s2n = n1 (Xi ; X n )2 empirikus szorasnegyzet statisztika a # szorasnegyzet aszimpi=1 Pn totikusan torztatlan becslese, az sn 2 = n;1 1 (Xi ; X n )2 korrigalt empirikus szorasi=1 negyzet statisztika pedig a # szorasnegyzet torztatlan becslese. (ii) Ha a feltetelekhez azt is hozzavesszuk, hogy 8P 2 P-re EP X 4 is, ugy s2n konzisztens, sn2 negyzetes kozepben konzisztens becsles is. Bizonytas : Fel fogjuk hasznalni a Steiner-tetelt: Segedtetel: (Steiner) Tetsz}oleges a x1  x2  : : :  xn valos szamokra n n n 1X 1X 1X 2 ( a ; xi )2 = (a ; xn )2 + ( x ; xi )2

n n n n (xn ; xi ) : i=1

Masreszt a = 0 valasztassal, atrendezes utan:

i=1

i=1

n n X 1X 1 2 2 2 n (xn ; xi ) = n xi ; xn: i=1

i=1

12

2. FEJEZET Becsleselmelet A segedtetel bizonytasa:

n n 1X 1X 2 ( a ; xi )2 = n n (a ; xn + xn ; xi ) = i=1

= (a ; xn )2 + 2(a ; xn ) n1

i=1 n X i=1

n X (xn ; xi ) + n1 (xn ; xi )2 : i=1

A kozeps}o tag nulla, gy az alltast igazoltuk. Az alltas bizonytasa: (i)

 X !  X ! X n ; n n

1 1 2 EP s2n = EP n Xi ; Xn = EP n Xi2 ; (Xn )2 = n1 EPXi2 ;EP(Xn )2 = i=1 i=1 i=1

 ;

# 1 n;1

= n  n  # + (EP X1 )2 ; n + (EP X1 )2 = n # ! # (n ! 1) Mivel sn 2 = n;n 1 s2n =) EP sn2 = n;n 1 EP s2n = #: (ii) Belathato, hogy  2 EP X 4 n n ;3 2 2 2 2 2  P sn = (n ; 1)2 n ; n(n ; 1) # ! 0 P sn ! 0: Hivatkozva a 2.1.2. tetelre s2n konzisztenciaja bizonytott.

2.1.3. pelda: (Kovariancia es korrelacios egyutthat o becslese) T

Legyen most az (X1  Y1 )T  (X2  Y2 )T  : : :  (Xn  Yn )T statisztikai meggyeles ketdimenzios statisztikai minta, ahol az (Xi  Yi )T parok azonos eloszlasu, teljesen fuggetlen valoszn}usegi vektorvaltozok. Ekkor a n ; X

;

1 cn = n ; 1 Xi ; X n Yi ; Yi i=1 T T 2  Y2 )  : : :  (Xn  Yn )

)T  (X

statisztika az (X1  Y1 minta empirikus kovarianciaja, n = sXcnsY pedig az empirikus korrelacios egyutthatoja, ahol pl.

v u u  sX = t

1

n ; X

n ; 1 i=1

Xi ; X n

2

az X1  X2  : : :  Xn statisztikai minta korrigalt empirikus szorasat jeloli. (i) A cn empirikus kovariancia az EP (X ; EP X )(Y ; EP Y ) kovariancia torztatlan becslese. Ha meg azt is feltehetjuk, hogy 9EP X 4  EP Y 4 is, akkor cn negyzetes kozepben konzisztens becsles is. (ii) Az n empirikus korrelacios egyutthato a korrelacios egyutthato aszimptotikusan torztatlan becslese. Ha meg azt is feltehetjuk, hogy 9EP X 4  EP Y 4 is, akkor n konzisztens becsles is.

2.1

13

Torztatlan, konzisztens becsles

Bizonytas :

(i) Jelolje cov (Xi  Yi ) = c EXi EYi = m: Ekkor  i = 1 (c + nm) = c + m EX Y = c + m: EXiYi = c + m EXi Y = EXY n n n Tehat (n ; 1) cn = azaz

n ; X

;

X ;X Y ; X Y ; Y X + X Y  Xi ; X Yi ; Y = i i i i n

i=1

i=1

E ((n ; 1) cn) = (nc + nm) ; (c + nm) ; (c + nm) + (c + nm) = (n ; 1) c: Megmutathato, hogy ahol



2 cn = m22 + s1 s2 + c  n n(n ; 1) n(n ; 1)



m22 = E (Xi ; EXi)2 (Yi ; EYi)2  s1 =  2 Xi  s2 =  2Yi : Mivel  2 cn ;! 0 gy a konzisztencia mar kovetkezik. (ii) Nem bizonytjuk. Bizonytasa megtalalhato Cramer: Mathematical statistics c. konyvben.

2.1.4. pelda: (Eloszlasfuggveny becslese) Tekintsuk azokat az ordk (x1  x2  : : :  xn ) skalar{vektor fuggvenyeket, melyek dencioja: xk = ord (x  x  : : :  xn ) = xj  k 1 2 ha xj a k-adik legnagyobb elem x1  x2  : : :  xn kozott. Az

Xk = ord (X1  X2  : : :  Xn ) (k = 1 2 : : :  n) k statisztikak a rendezett mintaelem-statisztikak. Megjegyzes : 1. A rendezett mintaelem-statisztikak kozott 8P 2P eseten 1 valoszn}useggel fennall, hogy X1  X2      Xn . Specialisan X1 = min fX1  X2  : : :  Xn g, es Xn = max fX1 X2  : : :  Xn g : 2. Ha a minta eloszlasfuggvenyet F (x)-szel jeloljuk, konny}u megmutatni, hogy a rendezett mintaelemek eloszlasfuggvenyeit es egyuttes eloszlasfuggvenyeit az alabbi modon lehet szamolni: n  X n F (x)]i 1 ; F (x)]n;i   Fk (x) = P (Xk < x) = i i=k

Fkl (x y) = P (Xk < x Xl < y) =

14

2. FEJEZET Becsleselmelet n X i X

n! F (x)]j F (y) ; F (x)]i;j 1 ; F (y)]n;i  j !( i ; j )!( n ; i )! i=k j =l P (X1 < x1 X2 < x2 : : :  Xn < xn) = i in n X X X n! =  F (x1 )]i F (x2 ) ; F (x1 )]i ;i    1 ; F (xn )]n;in : i !( i ; i )!    ( n ; i )! n in =n in; =n;1 i =1 1 2 1 =

2

1

1

Az

2

1

1

8 0 < Fn (x) = : nk  1

ha x  X1 ha Xk < x  Xk+1 (k = 1 2 : : :  n ; 1) ha x > Xn veletlen fuggvenyt az X1  X2  : : :  Xn statisztikai minta empirikus eloszlasfuggvenyenek nevezzuk. Pn Hasznalatos az el}oz}ovel ekvivalens Fn (x) = IfXi 0 is es m 2 R is ismeretlen. Szerkesszunk D-re adott 0 < " < 1 mellett (1 ; ")-szint}u kondenciaintervallumot! A Lukacs-tetelre hivatkozva megint: (n;D1)sn 2 2n;1 . Az n ; 1 szabadsagfoku 2 -eloszlas tablazatbol megadhatok olyan 0 < c1 < c2 szamok, hogy 2

2



sn 2 < c 1 ; " = P c1 < (n ;D1) 2 2

!

teljesuljon. (A c1  c2 ertekek nyilvan kielegtik a P( 2n;1 > c1 ) = 1 ; 2" es P( 2n;1 > c2 ) = 2" felteteleket.) Egyszer}u atrendezessel kapjuk, hogy

0s 1 s 1 ; " = P @ (n ; 1) sn < D < (n ; 1) snA 

azaz a T1 = lesz D-re.

q (n;1) c2

sn

 T2 =

q (n;1) c1

c2

c1

sn statisztikapar (1 ; ")-szint}u kondenciaintervallum

2.5.4. pelda: (Kon denciaintervallum szerkesztese az ismeretlen parameterre exponenci-

alis eloszlas eseteben) Legyen X1  X2  : : :  Xn E () eloszlasbol szarmazo statisztikai minta, ahol  > 0 ismeretlen. Szerkesszunk -ra adott 0 < " < 1 mellett (1 ; ")-szint}u kondenciaintervallumot! A problema megoldasahoz felhasznaljuk az alabbi segedtetelt: Segedtetel: Legyen X1  X2  : : :  Xn E () eloszlasbol szarmazo statisztikai minta. Ekkor

a) Xi 2 E (1) b)

Pn X = nX 2 ;(n 1) azaz n 1 parameter}u gamma eloszlasu, j n

j =1

n;1 f;(x) = (nx; 1)! e;x (x > 0)

s}ur}usegfuggvennyel. A segedtetel bizonytasa:

a) P(Xj < x) = P(Xj < x ) = 1 ; e; x = 1 ; e;x =) Xj 2 E (1):

h

R1

b) 'Xj (t) = EeiXj t = eixt e;x dx = it;1 1 ex(it;1) 0

'nXn (t) = fuggvenye:

Z1 0

eixt

Yn

j =1

'X (t) =

 1 n 1;it

i1 0

= 1;1it .

=) fnXn (x) = x(nn;;e1)!;x  mert a karakterisztikus 1

xn;1 e;x dx =  xn;1 1 ex(it;1) 1 ; 1 1 Z xn;2 ex(it;1) dx = (n ; 1)! (n ; 1)! it ; 1 (n ; 2)! it ; 1 0 1

0

2.5

41

Intervallumbecslesek

1

1

= 0 ; (n ; 2)! it ; 1 1



1



= (n ; 3)! it ; 1

xn;2

2 Z1 0



1 2 Z1 1 ex(it;1) 1 + 1 xn;3ex(it;1) dx = it ; 1 ( n ; 3)! it ; 1 0 xn;3 ex(it;1) dx =    = (;1)n



1

0 n



it ; 1



1

= 1 ; it

n

:

Az n 1 parameter}u gamma-eloszlashoz tartozo tablazatbol kiolvashatok olyan 0 < 1 < 2 szamok, amelyekkel 1 ; " = P(1 <  n X n < 2 ) = P( 1 <  < 2 ) n Xn n Xn

azaz a T1 = n Xn  T2 = n Xn statisztika par lesz (1 ; ")-szint}u kondenciaintervallum -ra. A 1  2 szamokat ugy kell meghatarozni, hogy P(0 < ;(n 1) < 1 ) = P(;(n 1) > 2 ) = 2" legyen. 1

2

42

2. FEJEZET Becsleselmelet

3. fejezet

Hipotezisvizsgalat 3.1. Alapfogalmak Tekintsuk a K veletlen kserletet es a hozzatartozo ( F) merhet}o teret, es a P valoszn}usegi mertekek osztalyat, ahol ( P P) Kolmogorov-fele valoszn}usegi mez}o 8P 2 P-re. Tegyuk fel, hogy P ket diszjunkt reszhalmazra bonthato: P = P0  P1 , es P0 \ P1 = : Statisztikai modszert (un. probat vagy tesztet) akarunk konstrualni annak eldontesere, hogy a veletlen kserlethez tartozo tenyleges P valoszn}usegi mertek melyik halmazhoz tartozik P0 es P1 kozul. Ehhez felalltunk egy H0 : P 2 P0 nullhipotezist, es egy H1 : P 2 P1 alternatv hipotezist. A nullhipotezis azt a feltevesunket fogalmazza meg, hogy az elmeleti P valoszn}useg a P0 reszhez tartozik, az alternatv hipotezisunk pedig azt, hogy ellenkez}oleg, pont a P1 reszhez. A kett}o felteves kozul az eljaras vegen egyertelm}uen kivalasztjuk es elfogadjuk majd az egyiket. A dontest az X1  X2  : : :  Xn  : : : statisztikai minta segtsegevel fogjuk meghozni. El}oszor is, el fogjuk keszteni a tn (X1  X2  : : :  Xn ) un. probastatisztikat, amely rendelkezni fog az alabbi tulajdonsaggal: adott 0 < " < 1 szamhoz megadhatok olyan K1 (") < K2 (") szamok, hogy P(K1 (")  tn  K2(")) 1 ; " 8P 2 P0 : A K1 (") K2 (") ertekeket kritikus ertekeknek, a segtsegukkel denialt Xe = fx : x 2 Rn  K1(")  tn(x)  K2 (")g n-dimenzios vektorhalmazt elfogadasi tartomanynak, a komplemens halmazat, Xk = Rn n Xe -t, pedig kritikus tartomanynak nevezzuk. Az " szam a proba terjedelme, az 1 ; " ertek pedig a proba szigni kancia szintje. A dontest ugy hajtjuk vegre, hogy ellen}orizzuk, hogy az X1  X2  : : :  Xn minta beleseik-e az Xe elfogadasi tartomanyba. Ha beleesik, akkor a H0 hipotezist, ellenkez}o esetben a H1 alternatv hipotezist fogjuk elfogadni. A hipotezis eldontese maskeppen alakulhat az egyes " terjedelmeken, ezert mindig jelezni kell, hogy milyen 1 ; " szint mellett fogadjuk el (vagy vetjuk el) a nullhipotezist. Termeszetesen szamolunk azzal is, hogy a dontesunk hibas. Azt mondjuk, hogy els}ofaju hibat kovetunk el, ha elvetjuk a nullhipotezist, holott valojaban az igaz. Masodfaju hibat akkor kovetunk el, ha elfogadjuk a nullhipotezist, holott az nem igaz. Minden mas esetben helyesen dontunk. A dontesi hibafajtakat az alabbi tablazatban mutatjuk: Dontes n Valosag H0 igaz H1 igaz H0 mellett jo dontes masodfaju hiba H1 mellett els}o faju hiba jo dontes

3.1.1. den cio: A p1 (" n P) = P((X1  X2  : : :  Xn)T 2 Xk ) P 2 P0  0 < " < 1 n 2 N 43

44

3. FEJEZET Hipotezisvizsgalat

fuggvenyt els}ofaju hibavaloszn}usegnek nevezzuk. A sup P((X1  X2  : : :  Xn )T 2 Xk )  "

8P2P0

relacio teljesulese eseten legfeljebb " terjedelm}u probarol beszelunk.

3.1.2. den cio: A p2 (" n P) = P((X1  X2  : : :  Xn )T 2 Xe ) P 2 P1  0 < " < 1 n 2 N fuggvenyt masodfaju hibavaloszn}usegnek nevezzuk.

3.1.3. den cio: Az E (" n P) = 1 ; p2(" n P) = P((X1  X2  : : :  Xn)T 2 Xk ) P 2 P1 0 < " < 1 n 2 N fuggvenyt a proba er}ofuggvenyenek nevezzuk. A sup P((X1  X2  : : :  Xn )T 2 Xk )

8P2P1

ertek a proba ereje.

3.1.4. den cio: Egy proba torztatlan, ha P ;(X1  X2  : : :  Xn )T 2 Xk  "

8P 2 P0 -bol

kovetkezik, hogy

P((X1 X2  : : :  Xn )T 2 Xk ) "

8 P 2 P1 

80 < " < 1:

Vagyis, ha H0 nem all fenn, nagyobb valoszn}useggel utastjuk el, mint amikor fennall.

3.1.5. den cio: Egy proba konzisztens, ha nlim !1 E (" n P) = 1 8P 2 P1 es 0 < " < 1. 3.1.6. den cio: Egy proba egyenletesen legjobb proba, ha adott els}ofaju hibaval rendelkez}o probak kozott a legkisebb a masodfaju hibaja.

3.2. Neyman{Pearson- es Stein-lemma

3.2.1. den cio: Egy veletlentett proba dontesfuggvenyen azt a  : Rn ! 0 1] fuggvenyt ertjuk, amely megadja, hogy ha a minta realizaltja eppen x akkor  (x) valoszn}useggel fogjuk a H0 hipotezist elutastani. Megjegyzes :

1. Egy (nem veletlentett) statisztikai proba dontesfuggvenye  (x) = I (x 2 Xk )  tehat a veletlentett probak a statisztikai probak kiterjeszteset adjak. 2. Veletlentett proba eseten a dontes ket lepesb}ol all. El}oszor az X minta alapjan kiszamoljuk a p =  (X) valoszn}useget, majd generalunk egy Y veletlen szamot a 0 1]-en egyenletes eloszlasbol. Ha p  Y , akkor elfogadjuk H0 -t, kulonben elvetjuk.

3.2

45

Neyman{Pearson- es Stein-lemma

3. Nyilvan EP (X) jelenti az els}ofaju hiba valoszn}useget, ha P 2 P0 es az er}ofuggvenyt, ha P 2 P1 . 4. Egy veletlentett proba terjedelmet a sup EP  (X) 

8P2P0

az erejet pedig a

sup EP  (X)

8P2P1

ertekek adjak.

3.2.1. tetel: (Neyman{Pearson fundamentalis lemma) Legyen a vizsgalt P valoszn}usegi mertekosztaly ketelem}u: P = fP0  P1 g : Letezzek az X = (X1  X2  : : :  Xn )T statisztikai minta s}ur}usegfuggvenye mindket valoszn}usegi mertekre nezve. Jelolje ezeket rendre f0 (x) es f1 (x). P nyilvan dominalt a  Lebesgue-mertekre nezve. A Qn Qn minta egyuttes s}ur}usegfuggvenyei gy L0 (x) = f0 (xi ) illetve L1 (x) = f1 (xi ) : Donteni i=1 i=1 szeretnenk a H0 : P = P0 hipotezisr}ol a H1 : P = P1 alternatv hipotezissel szemben. Ekkor (i) tetsz}oleges 0 < " < 1 szamhoz letezik olyan 0 < c0 es 0 <  < 1 szam, amivel a

8 1 <  (x) = :  0

ha L1 (x) > c0 L0 (x) ha L1 (x) = c0 L0 (x) ha L1 (x) < c0 L0 (x)

dontesfuggveny olyan veletlentett probahoz tartozik, aminek " a terjedelme, (ii) az (i)-ben denialt proba egyenletesen legjobb proba, (iii) ha  egy " terjedelm}u legjobb proba, akkor

P0 ( (X) =  (X)) = P1 ( (X) =  (X)) = 1: Bizonytas :

(i) Legyen 0 < " < 1 tetsz}oleges. Tekintsuk a G (c) = P0 (L1 (X) > cL0 (X))  c 2 R fuggvenyt. Mivel L0 (x) az X minta s}ur}usegf enye H0 mellett, ezert uLggv ( X) P0 (L0 (X) > 0) = 1 azaz G (c) = P0 L (X) > c : Mivel 1 ; G (c) jobbrol folytonos eloszlasfuggvenye az Y = LL ((XX)) valoszn}usegi valtozonak, G (c) egy monoton nem novekv}o, jobbrol folytonos fuggveny, melyre c!;1 lim G (c) = 1 clim !1 G (c) = 0: Ezert letezik olyan c0 szam, melyre G (c0 )  "  G (c0 ; 0) : Nyilvan G (c0 ; 0) ; G (c0) = P0 (L1 (X) = c0 L0 (X)) : Ha G folytonos c0 -ban, akkor  meghatarozasa erdektelen, hiszen ugyis egy 0-mertek}u halmazon veszi csak fel  ezt az erteket. Ilyenkor EP  (X) = P0 (L1 (X) > c0 L0 (X)) = G (c0 ) = " vagyis a proba terjedelme ": Ha viszont G nem folytonos c0 -ban, es (c0 )  = G (c ";;0)G ; G (c0 ) 0 1

0

1

0

0

46

3. FEJEZET Hipotezisvizsgalat akkor

EP  (X) = P0 (L1 (X) > c0L0 (X)) +  P0 (L1 (X) = cL0 (X)) = 0

= G (c0 ) +  (G (c0 ; 0) ; G (c0 )) = ":

c0 megvalasztasa lenyegeben egyertelm}u. Tegyuk fel ugyanis, hogy G(c) = " c 2 (c  c ) : Tekintsuk a   L ( x ) 1   T = x : p0 (x) > 0 \ c < L (x) < c 0 tartomanyt.

P0 (T ) = G (c) ; G (c ; 0) = " ; " = 0: x 2 T eseten cL0 (x) < L1 (x) < cL0 (x) miatt

Z

Z

T

T

0 = c L0 (x) d (x)
 (x)g es S ; = fx :  (x) <  (x)g : Konnyen lathato, hogy 8x 2 S = S +  S ; eseten ( (x) ;  (x)) (L1 (x) ; c0 L0 (x)) 0 es 8x 2 S eseten  (x) =  (x) : Ezert Z ( (x) ;  (x)) (L1 (x) ; c0 L0 (x)) d (x) = 0

Rn

= azaz

Z Rn

Z

( (x) ;  (x)) (L1 (x) ; c0 L0 (x)) d (x) 0

S

Z

( (x) ;  (x)) L1 (x) d (x) c0

Rn

( (x) ;  (x)) L0 (x) d (x) =

= c0 (" ; EP  (X)) 0 azaz EP  (X) EP  (X)  vagyis  er}osebb, mint  : (iii) Legyen most  egy tetsz}oleges legfeljebb " terjedelm}u egyenletesen legjobb proba dontesfuggvenye. Legyen S = fx :  (x) 6=  (x) \ L1 (x) 6= c0 L0 (x)g : Ha x 2 S akkor 0

1

1

( (x) ;  (x)) (L1 (x) ; c0 L0 (x)) > 0 lesz. Ezert, ha S nem nullmertek}u, vagy P0 vagy P1 szerint, akkor 0< =

Z S

Z

Rn

( (x) ;  (x)) (L1 (x) ; c0 L0 (x)) d (x) = ( (x) ;  (x)) (L1 (x) ; c0 L0 (x)) d (x) :

3.2

47

Neyman{Pearson- es Stein-lemma

Ebb}ol kovetkezik, hogy

Z

Rn

Z

( (x) ;  (x)) L1 (x) d (x) > c0

Rn

( (x) ;  (x)) L0 (x) d (x) = c0 (" ; ") = 0

azaz EP  (X) > EP  (X)  ami ellentmondas azzal, hogy  egyenletesen legjobb proba dontesfuggvenye volt. Az ellentmondas abbol fakadt, hogy feltettuk, hogy S valamelyik valoszn}usegi mertek szerint nem nullmertek}u. Tehat,  es  mindket mertek szerint 1 valoszn}useggel egybeesik. 1

1

3.2.2. tetel: (Stein-lemma) Legyen a vizsgalt P valoszn}usegi mertekosztaly ketelem}u: P = fP0  P1 g : Letezzek az X s}ur}usegfuggvenye mindket valoszn}usegi mertekre nezve. Jelolje ezeket rendre f0 (x) es f1 (x). Az n X = (X1  X2  : : :  Xn )T statisztikai minta egyuttes s}ur}usegfuggvenyei gy L0 (x) = Q f0 (xi) i=1

Qn illetve L1 (x) = f1 (xi ) : Tegyuk fel, hogy i=1  jD (f0 k f1 )j = EP



0

1 )  < 1 log2 ff0 ((X 1 X1 ) 

vagyis, veges a ket eloszlas un. relatv entropiaja. Donteni szeretnenk a H0 : P = P0 hipotezisr}ol a H1 : P = P1 alternatv hipotezissel  szemben. Jelolje X(en)  Rn egy sta( n ) tisztikai proba elfogadasi tartomanyat, n = P0 X 2 Xk az els}ofaju hibavaloszn}useget,  n = P1 X 2 X(en) pedig a masodfaju hibavaloszn}useget. Legyen 0 < " < 21 tetsz}oleges terjedelem, amellyel n" = min n  azaz n" jeloli a legfeljebb " terjedelm}u probak eseten n X(e ) Rn n 0 tetsz}oleges volt. Megmutatjuk, hogy nincsen a fenti X(en) -nel jobb elfogadasi tartomanysorozat. Legyen ( n ) Y egy masik elfogadasi tartomanysorozat, melyhez az ny  ny els}ofaju- illetve masodfaju hibavaloszn}useg-sorozat tartozik.





ny = P1 X 2 Y(n) P1

Z



Xen

( )



X 2 Xe(n) \ Y(n)



=

Z

X(en) \Y(n)

Z

L0 (x) 2;n(D(f0 kf1 )+ ) d (x) 2;n(D(f0 kf1 )+ )

Xen

\Y(n)

L1 (x) d (x)

( )

L0 (x) d (x) :

\Y(n)

A De Morgan azonossagot, majd a Boole-egyenl}otlenseget hasznalva

Z

X(en) \Y(n)



1 ; P0

adodik, azaz





L0 (x) d (x) = P0 X 2 X(en) \ Y(n) = 1 ; P0 X 2 X(en)  Y(n)



X 2 X(en)



; P0









X 2 Y(n) = 1 ; n" ; ny

log2 (1 ; n" ; ny ) : 1 n log2 ny ;D (f0 k f1 ) +  + n 1 log  ;D (f0 k f1 ) : Tehat, Y(n) nem jobb X(en) -nel, Mivel  > 0 tetsz}oleges volt, nlim !1 n 2 ny ahol elertuk az also hatart. Ebb}ol az is kovetkezik, hogy n = n" .

3.3

49

Parameteres pro bak

3.3. Parameteres probak Ha adott egy P = fP#  # 2 g parameteres eloszlascsalad, akkor a

P = P0  P1  es P0 \ P1 =  felbontas helyett a  parameterter  = 0  1  0 \ 1 =  diszjunkt felbontasa segtsegevel is megfogalmazhatjuk a hipoteziseinket:

H0 : # 2 0 H1 : # 2 1 :

3.3.1. Egymintas u-proba

Most csak olyan P valoszn}usegi mertekeket tekintunk, ahol az X = (X1  X2  : : :  Xn )T minta adott D0 > 0 szorasu, ismeretlen m varhato ertek}u normalis eloszlasu lesz, a # parameter a varhato ertek (# = m): 0 = fm0 g  1 = fm 6= m0 g  azaz most a nullhipotezis H0 : EP X = m0  az alternatv hipotezis pedig H1 : EP X 6= m0 : Azt akarjuk tehat eldonteni, hogy lehet-e a minta varhato erteke egy adott m0 ertek, vagy attol szignikansan kulonboz}o lesz. Ha a H0 hipotezis igaz, akkor a mintaelemek N (m0  D0 ) eloszlasuak, amib}ol kovetkezik, hogy a mintaatlag statisztika szinten normalis eloszlasu: X n 2 N (m0  pDn ): Standardizalas p utan: u(X) = XnD;m n 2 N (0 1). A standard normalis eloszlashoz a (u") = 1 ; 2" osszefugges alapjan megadhatok olyan K1 (") = ;u" K2(") = u" kritikus ertekek, melyekre, ha a H0 hipotezis igaz, akkor fenn kell allnia, hogy n P(x;nu;"m 0 lim P(Dnm < y) = 0 nm!1 y0 :

Bizonytas : A tetelt nem q nmbizonytjuk. q Megjegyzes : Dnm = n+m sup jFn (x) ; Gm (x)j = nnm max jFn (Zi ) ; Gm (Zi )j, + m i =1  2 :::n + m x2R ahol Z1  Z2      Zn+m a ket minta egyestesevel kapott minta rendezettje. A szupremum meghatarozasat, most is visszavezettuk maximum meghatarozasara. Ezt a probat homogenitasvizsgalatra hasznalhatjuk, azaz annak eldontesere, hogy a ket valtozo azonos eloszlasu-e. A nullhipotezisunk az, hogy a ket minta eloszlasfuggvenye azonos, az alternatv hipotezis ennek a tagadasa: H0 : F (x)  G(x) es H1 : F (x) 6 G(x): A hipotezis eldontese: tetsz}oleges 0 < " < 1 -hez adhato olyan x" kritikus ertek, hogy K (x" ) = 1 ; " legyen. Ha a Dnm < x" , akkor a nullhipotezist az adott szignikancia szinten elfogadjuk. Az alabbi tetel segtsegevel meg tovabb lehet a mintaelemszamot csokkenteni.

3.4.4. tetel: (Gnyegyenko{Koroljuk) Legyen a X1  X2  : : :  Xn  : : : statisztikai minta, melynek eloszlasfuggvenye F (x), es Y1  Y2  : : :  Yn  : : : az el}oz}ot}ol fuggetlen masik statisztikai minta, melynek eloszlasfuggvenye G(x). F es G abszolut folytonosak. Jelolje Fn (x) es Gn(x) a ket mintahoz tartozo empirikus eloszlasfuggvenyet. Tegyuk fel, hogy F (x)  G(x). Ekkor 8

r n  > < 0 y 1 p12n p n p2n < y  2  P 2 sup jFn (x) ; Gn(x)j < y = > L(y) p x2R : 1 n 0 : E kf (c Z)k2 < K 1 + kc ; k2  ( ) n > 0 Akkor nlim !1

1 P 

n = 1

n=0 kCn ; k = 0

8c 2 Rk+1 

1 2 P  < 1:

n=0

n

1-valoszn}useggel.

Bizonytas : Szuksegunk lesz ket lemmara.

4.3.1. lemma: A 4.3.1. tetel feltetelei mellett teljesul, hogy letezik egy C valoszn}usegi valtozo, melyre nlim !1 kCn ; k = C 1-valoszn}useggel. Bizonytas : A rekurzv egyenlet mindket oldalabol vonjunk le -t, majd emeljuk negyzetre: kCn+1 ; k2 = kCn ; k2 ; 2n (Cn ; )T f (Cn Zn+1 ) + n2 kf (Cn Zn+1 )k2 :

Ezutan vegyuk mindket oldalnak a Z1  Z2  : : :  Zn valoszn}usegi valtozok altal generalt -algebrara vett felteteles varhato ertekeit:









E kCn+1 ; k2 j Z1 Z2  : : :  Zn = E kCn ; k2 j Z1  Z2 : : :  Zn







;



(Cn ; )T f (Cn Zn+1 ) j Z1  Z2  : : :  Zn + n2 E kf (Cn  Zn+1 )k2 j Z1  Z2  : : :  Zn : A fuggetlenseg miatt, es amiatt, hogy Cn csak Zn-t}ol fugg: ;2n E





E kCn ; k2 j Z1 Z2  : : :  Zn = kCn ; k2 

4.3

71

Sztochasztikus approximacio



es

E (Cn

; )T f (C

n  Zn+1 ) j Z1  Z2  : : :  Zn

= ( Cn ;  ) T es

E

Z RM

=

RM

(Cn ; )T f (Cn  y)  (dy) =

f (Cn y)  (dy) = (Cn ; )T r (Cn) 



kf (Cn Zn+1 )k2 j Z1  Z2  : : :  Zn

ahol  jeloli Z eloszlasat. Igy

Z

Z =

kf (Cn  y)k2  (dy)  K

RM



E kCn+1 ; k2 j Z1 Z2  : : :  Zn  kCn ; k2 ; 2n (Cn ; )T r (Cn) + n2 K

Mivel









1 + kCn ; k2 





1 + kCn ; k2 :

inf (c ; )T r (c) > 0

kc;k>"

ezert tovabb noveljuk a baloldalt, ha elhagyjuk a kozeps}o tagot:



E kCn+1 ; k2 j Z1 Z2  : : :  Zn



 kCn ; k2

;1 +  2 K +  2 K: n

n

Most tekintsuk azt a fVn gn=12::: valoszn}usegi valtozo sorozatot, melynek dencioja

Vn+1 = kCn+1

Q1 

; k2 

n+1 + K



1 X

j =n+1

j2 j +1

ahol k = 1 + j2 K : Megmutatjuk, hogy f(Vn  Fn)gn=12::: szupermartingal, ahol Fn = j =k  (Z1 Z2  : : :  Zn ) :

E Vn+1 j Fn]  kCn ; k2

;1 +  2 K  n

2 n+1 + n Kn+1 + K

= kCn ; k2 n + K

1 X j =n

1 X

j =n+1

j2j +1 =

j2j+1 = Vn:

Meg az is igaz, hogy az fE jVn jgn=12::: szamsorozat korlatos. Ugyanis Vn 0 ami a denciojabol latszik, es gy E jVn j = EVn : Masreszt a szupermartingal tulajdonsag miatt fE jVn jgn=12::: monoton fogyo. Vegul EV1 = E jV1 j < 1 miatt 9M : E jVn j  M < 1 n = 1 2 : : : : Alkalmazhato a szupermartingalok konvergenciatetele, miszerint letezik egy C valoszn}usegi valtozo, melyre nlim V = C 1 valoszn}useggel. Mivel megmutathato, hogy nlim  =1 !1 n !1 n 1 P

es nlim  2  = 0 ezert nyilvan az is teljesul, hogy nlim kC ; k2 = C 1 valoszn}useg!1 j =n j j +1 !1 n gel.

72

4. FEJEZET Regresszio analzis

4.3.2. lemma: A 4.3.1. tetel feltevesei mellett 1 X

n=1

1 valoszn}useggel.

n (Cn ; )T r (Cn) < 1

Bizonytas : A fCn gn=12::: rekurzv sorozatot denialo egyenlet mindket oldalabol levonva -t,h negyzetre emelunk, majd kiszamtjuk a varhato ertekeket. Az an = E kCn ; k2  bn = i 2E (Cn ; )T f (Cn  Zn+1 )  dn = E kf (Cn  Zn+1 )k2 jelolesekkel azt kapjuk, hogy an+1 = an ; nbn + n2 dn : Megmutathato, hogy 1 X

n=1

n bn = 2

1 X

n=1

h

i

nE (Cn ; )T f (Cn Zn+1 ) < 1

ahonnan a 4.3.1. lemma eredmenyet felhasznalva kovetkezik a monoton konvergencia tetelt alkalmazva, hogy 1 X

n=1

h

n E (Cn

; )T f (C

=E

"X 1

n=1

n  Zn+1 )

1 h i X

=

n=1

i

E n (Cn ; )T r (Cn) =

n (Cn ; )T r (Cn)

#

< 1:

Ezzel a lemmat bebizonytottuk hiszen, ha a varhato ertek mogotti sor 1 valoszn}useggel 1 lenne, akkor a varhato ertek nem lehetne veges. A 4.3.1. tetel bizonytasa: A 4.3.1. lemmaban bizonytottakbol kovetkezik, hogy letezik egy C valoszn}usegi vektorvaltozo es egy  1 valoszn}useg}u esemeny, hogy 8! 2  elemi  az 1 valoesemenynel fennall a nlim !1 Cn (!) = C (!) konvergencia. Masreszt jelolje  azt 1 P

szn}useg}u esemenyt, amelyen fennall n (Cn (!) ; )T r (Cn (!)) < 1: (Ilyen  a 4.3.2. n=1 lemma ertelmeben letezik.) Ekkor a (***) feltetel miatt megadhato olyan fmn gn=12::: indexT sorozat, hogy nlim ( ) feltetele miatt teljesul, !1 (Cmn (!) ; ) r (Cmn (!)) = 0: Ebb}ola tetel  hogy nlim kC (!) ; k = 0 8! 2  : Tehat, 8! 2  \  elemi esemenyre C (!) =  !1 mn  all, ami P ( \  ) = 1 miatt a tetel alltasat jelenti: nlim !1 kCn ; k = 0 1-valoszn}useggel. Megjegyzes : A 4.3.1. tetel segtsegevel igazolhato a nagy szamok torvenyenek alabbi er}os alakja: Ha fXn gn=12::: fuggetlen, azonos eloszlasu a varhato ertek}u, veges szorasu valoszn}usegi valtozo sorozat, melynek tagjai az RN terb}ol veszik fel az ertekeiket, akkor a Zn+1 = Zn ; n Zn ; Xn ] n = 0 1 : : : rekurzv valoszn}usegi vektorvaltozo sorozatra | ha Z0 = z0 2 RN tetsz}oleges es a n sorozat kielegti a 4.3.1. tetel ( ) felteteleit | teljesul, hogy lim kZ ; ak = 0 1 valoszn}useggel. n!1 n

Zn = an +

n X i=1

ci Xi 

4.3

73

Sztochasztikus approximacio

ahol

an = z0

nY ;1 i=0

(1 ; i ) es ci = i;1 (1 ; i )    (1 ; n;1 ) :

1  akkor Zn = X  n az atlagstatisztika. Ha z0 = 0 es n = n+1

4.3.1. Linearis regresszios feladat

Ebben a szakaszban az el}oz}o pont eredmenyeinek egy kulonlegesen fontos specialis alkalmazasat targyaljuk. Azzal az esettel foglalkozunk, amikor az r regresszios fuggveny r (c) = Ac ; m linearis fuggveny,; ahol A (k + 1)  (k + 1)-es kvadratikus matrix, m pedig Rk+1 -beli vektor. Legyen Z = *  melyre E* = A es E = m es f (c Z) = *c ; : Tegyuk fel, hogy az A matrix szimmetrikus, pozit ;

v denit es invertalhato. (Ekkor a regresszios fuggveny r (c) = Ef (c Z) = E *c ;  = Ac ; m.) 4.3.2. tetel: Jelolje * = (Vij )i=01:::k es  = (0  1  : : :  k ) es tegyuk fel, hogy j =01:::k

PN

es E i2 = M2 < 1: Jelolje Z1  Z2  : : :  Zn  : : : a i=1 Z-vel azonos eloszlasu, teljesen fuggetlen elemekb}ol a1llo sorozatot! Tegy uk fel tovabba, hogy 1 2 P P fn gn=12::: olyan pozitv tagu szamsorozat, melyre n = 1 es n < 1 teljesul.

9M1  M2

> 0, hogy

EVij2 

M1
0 : c ; A m Ac ; m K1 c ; A;1 m 8c 2 Rk+1 -re. Mivel A szimmetrikus es pozitv denit az A' = ' sajatertek egyenletnek letezik fn  'n gn=01:::k megoldasrendszere, ahol f'n gn=01:::k ortonormalt rendszer Rk+1 -ben, es i 0 i = 0 1 : : :  k. S}ot i > 0 i = 0 1 : : :  k is, mivel ellenkez}o esetben az A' = 0 egyenletnek lenne nem trivialis megoldasa, ami ellentmond annak, hogy A;1 letezik. Ekkor tehat Pk Pk Pk vehetjuk a kovetkez}o sorfejteseket: c = ci 'i  m = mi 'i . Ezekkel A;1 m.= 1i mi 'i : i=0 i=0 i=0 Ezt alkalmazva nyerjuk, hogy k

;c ; A;1m T ;Ac ; m = X c

A



i=0

X k

min  0ik i i=0





N X 1 i ci ; 1 mi i ;  mi (i ci ; mi ) = i

ci ; 1 mi i

2

i=1



=

  min i c ; A;1 m2 :

i

2



0ik

K1 = 0min  ik i



valasztassal igazoltuk a ( ) egyenl}otlenseget, ahonnan mar kovetkezik a 4.3.1. tetel ( ) feltetelenek teljesulese. A 4.3.2. tetel bizonytasat tehat befejezhetjuk, ha meg megmutatjuk, hogy 8c 2 Rk+1 -re



  ;

 E kf (c Z)k2 = E  *c ;  2  K 1 + c ; A;1m2



74

4. FEJEZET Regresszio analzis

valamely K > 0-ra. Ugyanis a fenti relacio eppen a 4.3.1. tetel ( ) feltetelenek teljesulesevel ekvivalens. El}oszor is

*c ; 2 = * ;c ; A;1 m+A;1m ; 2  2  2     *2 c ; A;1 m + A;1 m + kk2  0N N 1 X X 2 A  ;1 2  ;1 2 @ Vij c ; A m + A m + k  k2 : i=1 j =1

Innen

*c ; 2  (k + 1)2 M c ; A;1m2 + A;1 m2 + M  K 1 + c ; A;1m2 1 2 n

adodik, ahol



o



K = max (k + 1)2 M1  (k + 1)2 M1 A;1 m2 + M2 :

4.3.2. Negyzetes hiba minimalizalasa

A negyzetes hiba minimalizalasanak problemaja a linearis regresszios problemara vezethet}o vissza. A problema most az, hogy az X = (X0  X1  X2  : : :  XN )T  X0  1 valoszn}usegi vektorvaltozo komponenseinek milyen linearis kombinaciojaval kozelthet}o legjobban az Y celvaltozo, azaz milyen c = (c0 c1  : : :  ck )T 2 Rk+1 sulyok eseten lesz minim alis az m(c) =   2 2 k k E P ci Xi ; Y atlagos negyzetes hiba. Tekintsuk most az l (c y) = P ci yi ; yk+1 i=0 i=0 fuggvenyt! A minimalizalashoz szarmaztatnunk kell az l (c y) fuggveny c vektor szerinti gradiensvektorat:

f (c y) = grad l (c y) = =2

c

X ! X ! k k i=0

ciyi y0 

i=0

ci yi y1  : : : 

X ! !T k

= B c ; b ahol es

i=0

ci yi yk

0yy 0 0 B = 2B @ ...

yk y0

; 2 (yk+1 y0  yk+1 y1  : : :  yk+1 yk )T 

y0 yk



yk yk

...

.. .

1 C A

=

b = 2 (yk+1y0 yk+1y1 : : :  yk+1yk )T :

Masreszt a m negyzetes hiba gradiensere: grad m (c) = grad E c

c

"X k i=0

2k k 3 k X X X ci Xi ; Y = grad E 4 ci cj Xi Xj ; 2 ci Xi Y ; Y 2 5 = c #2

i=0 j =0

i=0

2k k 3 k X X X cicj EXi Xj ; 2 ci EXi Y ; EY 2 5 : = grad 4 c

i=0 j =0

i=0

4.3

75

Sztochasztikus approximacio

Innen, tekintettel arra, hogy k X k k X @ X c c E X X = 2 @cj i=0 j =0 i j i j i=0 ci EXi Xj

es

k @ X @cj i=0 ci EXi Y = EXj Y

eppen az adodik, hogy grad m (c) = 2

X k

c

0 EX X 0 0 B . . A=@ .

ahol

Vegul, ha

EXk X0

i=0

ci EXi X0 



EX0 Xk 1



EXk Xk

...

.. .

C A



X0 Xk



Xk Xk

...

Xk X0

i=0

ci EXi X1  : : : 

k X i=0

ci EXi Xk

!T ;

;2 (EX0 Y EX1 Y : : :  EXk Y ) = Ac ; m

0XX 0 0 B T * = XX = 2 @ ... ;

k X

es m = 2 (EX0 Y EX1 Y : : :  EXk Y )T :

.. .

1 C A

es  = (X0 Y X1 Y : : :  Xk Y )T 



akkor a Z = *  es f (c Z) = *c; jelolesekkel, r (c) = Ef (c Z) = E * c;E = Ac;m a regresszios fuggveny. Keresend}o az r (c) = 0 egyenlet gyoke, ahol a m (c) negyzetes hiba minimalis lesz.

4.3.3. tetel: Tegyuk fel, hogy A;1 letezik es E Xi4  < 1 i = 0 1 : : :  k EY 4 < 1 : Ha fZn gn=12::: Z-vel azonos eloszlasu valoszn}usegi vektorvaltozo sorozat (Zi = *i  i ),





akkor a

Cn+1 = Cn ; n *n+1Cn ; n+1  n = 0 1 2 : : :  C0 = c0 2 Rk+1 C ; A;1m = 0 1 rekurzv keplettel denialt valoszn}usegi vektorvaltozo sorozatra nlim !1 n valoszn}useggel, felteve, hogy

1 P 

n=0

n = 1 es

1 2 P  < 1 teljesul. n

n=0

Bizonytas : A denciojabol lathatoan szimmetrikus es pozitv szemidenit, hiszen tet; ;

; sz}oleges t 2Rk+1 -re tT At = E tT *t = E tT XXT t = E XT t 2 0: Megmutatjuk, hogy 9M1  M2

h

> 0 amivel E Xi2 Xj2

i



M1 es E kk2 =

Pk EX 2 Y 2  M : A Cauchy{Schwarzi

i=0

egyenl}otlenseget felhasznalva ez azonnal adodik, hiszen

r   h i   2 2 E X X  E X4 E X4 < 1 i j

i

j

2

76 es

4. FEJEZET Regresszio analzis k X i=0

EXi2Y 2 

k q   X E Xi4 E Y 4 ] < 1: i=0

Tehat teljesulnek a 4.3.2. tetel feltetelei, akkor az alltas is igaz lesz. Megjegyzes : A sztochasztikus approximacio modszerevel targyalhato a nemlinearis regreszszio feladatanak gradiens vektoros megoldasi modja is, amikor az l (c Z) = kf (c X) ; Y k2 alaku es f (c x) nemlinearis x-ben.

5. fejezet

Eloszlasbecsles Nemparameteres statisztika eseten nem all rendelkezesre semmilyen el}ozetes informacio a valoszn}usegi valtozo eloszlasarol, gy nem hasznalhatjuk azt a tudast | mint parameteres esetben |, hogy az eloszlas egy parameteres osztaly eleme lenne. Igy a szabalyok alapvet}o tulajdonsagainak is eloszlasfuggetlennek kell lenniuk.

5.1. Eloszlasfuggveny becslese Legyen X valos ertek}u valoszn}usegi valtozo. A feladat az X valoszn}usegi valtozo F (x) eloszlasfuggvenyenek becslese fuggetlen, azonos eloszlasu X1  X2  : : :  Xn mintakbol. Mint Pn korabban lattuk, az Fn (x) = n1 IfXi 0 kulonben.

5.1.2. tetel: (Kolmogorov) Ha F (x) folytonos, akkor

p

  K ( y ) lim P n sup jFn (x) ; F (x)j < y = 0 n!1 x2R

ahol

K (y ) =

1 X k=;1

(;1)k e;2k y

77

2 2

ha y > 0 kulonben,

78

5. FEJEZET Eloszlasbecsles

Vegyuk eszre, hogy az el}obbi tetelekben a hatareloszlas nem fugg az elmeleti eloszlasfuggvenyt}ol. Most adunk egy alternatv bizonytast az empirikus eloszlasfuggveny egyenletes konvergenciajara, amely sok hasznos oteletet tartalmaz es segt a kovetkez}o fejezet fontos tetelenek, a Vapnik{Chervonenkis-egyenl}otlensegnek a bizonytasaban.

5.1.3. tetel: (Glivenko{Cantelli) Legyen X1  : : :  Xn fuggetlen, azonos eloszlasu valos ertek}u valoszn}usegi valtozo F (x) = P(X1  x) eloszlasfuggvennyel. Ekkor



P sup jFn(x) ; F (x)j > "



x2R

2  8(n + 1)e;n" =32

es gy a Borel{Cantelli-lemma miatt lim sup jF (x) ; F (x)j = 0 n!1 x2R n 1 valoszn}useggel. A tetel bizonytasahoz szuksegunk lesz a Hoe#ding-egyenl}otlensegre.

5.1.4. tetel: (Hoeding)

Legyenek X1  : : :  Xn fuggetlen korlatos valoszn}usegi valtozok ugy, hogy Xi 2 ai  bi ] egy Pn valoszn}useggel. Jelolje az osszeguket Sn , vagyis Sn = Xi . Ekkor minden " > 0-ra i=1 n

;2"2 = P (bi ;ai )2

PfSn ; ESn "g  e es

i=1 n

;2"2 = P (bi ;ai )2

PfSn ; ESn  ;"g  e

i=1

:

Az egyenl}otlenseg bizonytasahoz hasznalunk egy segedegyenl}otlenseget:

5.1.1. lemma: Legyen X olyan valoszn}usegi valtozo, amelyre EX = 0, a  X  b. Ekkor minden s > 0-ra,   E esX  es (b;a) =8 : 2

2

Bizonytas : Az exponencialis fuggveny konvexitasabol kovetkezik, hogy ; a sb b ; x sa esx  xb ; a e + b ; a e  ha a  x  b.

Legyen p = ;a=(b ; a), ekkor kihasznalva, hogy EX = 0

EesX

b esa ; a esb b;a b ; a s = 1 ; p + pe (b;a) e;ps(b;a) def (u) = e  

5.1

79

Eloszlasfu ggveny becslese

ahol u = s(b ; a), es (u) = ;pu + log(1 ; p + peu ). Mivel  derivaltja

0(u) = ;p + p + (1 ;p p)e;u 

ezert (0) = 0 (0) = 0. A masodik derivalt, pedig

00 (u) =

p(1 ; p)e;u  1 : (p + (1 ; p)e;u )2 4

Igy a Taylor-sorfejtes szerint valamely  2 0 u]-ra, 2

2

2

2

(u) = (0) + u0 (0) + u2 00 ()  u8 = s (b 8; a) : Az 5.1.4 tetel bizonytasa: A bizonytas az ugynevezett Cherno-technikan alapul. A Markov-egyenl}otlensegb}ol tudjuk, hogy minden X nemnegatv valoszn}usegi valtozora es " > 0-ra,

PfX "g  E"X :

Ezert, ha s tetsz}oleges pozitv szam, akkor minden X valoszn}usegi valtozora

PfX "g = PfesX es"g  Eees" : sX

A Cherno#-technika lenyege, hogy keresunk egy olyan s > 0-t, amely minimalizalja, vagy kell}oen kicsive teszi a fels}o korlatot.

PfSn ; ESn( "g !) n X  e;s"E exp s (Xi ; EXi ) i=1

n n o ;s" Y s(Xi ;EXi )

= e 

e;s"

E e

i=1 Yn

es (bi ;ai ) =8 (5.1.1 lemma miatt) 2

2

i=1 n P 2 s (bi ;ai )2 =8 ;s"

= e e ni ;2"2

= e

P

(Xi -k fuggetlensege miatt)

=1

i=1

(bi ;ai )2

(s = 4"

Pn (b ; a )2 -t valasztva): i i

i=1

A masodik egyenl}otlenseg hasonloan bizonythato. Az 5.1.4 tetel ket egyenl}otlenseget osszekombinalva kaphatjuk, hogy n i=1

PfjSn ; ESnj "g  2e

;2"2 P (bi ;ai )2

:

80

5. FEJEZET Eloszlasbecsles

Az 5.1.3 tetel bizonytasa: Pn Vezessuk be a kovetkez}o jeloleseket: (A) = P(X 2 A) es n (A) = n1 IfXi 2Ag minden i=1 A  R merhet}o halmazra. Legyen A a (;1 x]( x 2 R alaku halmazok csaladja. Ezekkel a jelolesekkel sup jFn (x) ; F (x)j = sup jn(A) ; (A)j A2A

x2R

Feltehetjuk, hogy n"2 2, hiszen kulonben a fels}o korlat trivialis ( 1). 1. LE PE S: Szimmetrizalas szellemmintaval Legyenek X10  : : :  Xn0 2 R valoszn}usegi valtozok ugy, hogy X1  : : :  Xn  X10  : : :  Xn0 mind fuggetlen es azonos eloszlasu. Jelolje 0n az uj mintak szerinti empirikus merteket: n X 0 (A) = 1 I 0

n i=1 fXi 2Ag

n

Ekkor megmutatjuk, hogy n"2 2-re







   " 0   P sup jn(A) ; (A)j > "  2P sup n(A) ; n(A) > 2 A2A A2A

Ehhez legyen A 2 A egy olyan halmaz, amelyre jn(A ) ; (A )j > ", ha ilyen halmaz letezik, kulonben legyen A egy rogztett A-beli halmaz. Ekkor



     " 0   P sup n(A) ; n(A) > 2 P n(A ) ; 0n(A ) > 2"

A2A    " =

P jn (A ) ; (A )j > " 0n(A ) ; (A ) <  2    0   "  = E Ifjn (A );(A )j>"g P n (A ) ; (A ) < 2  X1  : : :  Xn

A felteteles valoszn}useget becsulhetjuk a Csebisev-egyenl}otlenseg segtsegevel a kovetkez}okeppen, ha n"2 2:





  P 0n(A ) ; (A ) < 2"  X1 : : :  Xn

1;

 Osszefoglalva tehat





(A )(1 ; (A )) 1 ; 1 1 n"2=4 n"2 2



 1   " 0 P sup n(A) ; n(A) > 2 2 P (jn(A ) ; (A)j > ")

A2A

 1

jn (A) ; (A)j > " 2 P Asup 2A

2. LE PE S: Szimmetrizalas veletlen el}ojelekkel Legyenek 1  : : :  n fuggetlen, azonos eloszlasu X1  : : :  Xn  X10  : : :  Xn0 -t}ol fuggetlen f;1 1g ertek}u valoszn}usegi valtozok, P(i = ;1) = P(i = 1) = 12 valoszn}usegekkel. Mivel X1  X10  : : :  Xn  Xn0 mind fuggetlen es azonos eloszlasu,

X n    sup  IfXi2Ag ; IfXi0 2Ag  A2A  i=1

5.1

81

Eloszlasfu ggveny becslese

X  n  sup  i IfXi 2Ag ; IfXi0 2Ag  A2A i=1

es

azonos eloszlasu. Igy az 1. lepes miatt



P sup jn(A) ; (A)j > "





A2A







!

n X  " 1  2P sup  (IfXi 2Ag ; IfXi0 2Ag ) >  2 = A2A n  i=1

X  ! n 1 = 2P sup n  i (IfXi 2Ag ; IfXi0 2Ag ) > 2" A2A i=1 

Az uniokorlatot hasznalva megszabadulhatunk az X10  : : :  Xn0 seged valoszn}usegi valtozoktol X  !  n 1 P sup n  i(IfXi 2Ag ; IfXi0 2Ag) > 2"  A2A

i=1

X  !  X  ! n n 1 " 1 " =    0 2Ag  > + P sup  I  P sup  i IfXi 2Ag  >  i f X i     4 4 A2A n i=1 A2A n i=1 X  !  n 1 = 2P sup n  i IfXi 2Ag  > 4" A2A i=1 

3. LE PE S:

 P 

n sup n1 i IfXi 2Ag A2A i=1

   Pn    > 4" = P sup n1  iIfXi xg > 4" valoszn}useg becslex2R i=1

AP sehez nezzuk el}oszor a felteteles valoszn}useget felteve X1  : : :  Xn -et. Vegyuk eszre, hogy rogztett x1  : : :  xn 2 R-re, ahogy x vegigfut R-en a kulonboz}o (Ifx 4  X1  : : :  Xn  2e;n" =32 : i=1 2

Igy









!

n X  "  1 P sup n  iIfXi 2Ag > 4  X1 : : :  Xn  2(n + 1)e;n" =32 : A2A 2

i=1

Mindket oldal varhato erteket veve







!

n X  P sup n1  iIfXi2Ag  > 4"  2(n + 1)e;n" =32 : A2A 2

i=1

 Osszefoglalva tehat azt kapjuk, hogy





P sup jn(A) ; (A)j > " A2A

2  8(n + 1)e;n" =32 :

5.2. Vapnik{Chervonenkis-elmelet Ebben a fejezetben a Glivenko{Cantelli-tetel egy altalanostasat bizonytjuk. Legyen most

X d-dimenzios valoszn}usegi valtozo, es legyenek X1  : : :  Xn az X eloszlasabol vettnfuggetlen P mintak. Hasznaljuk a kovetkez}o jeloleseket: (A) = P(X 2 A) es n (A) = n1 IfXi 2Ag i=1 minden merhet}o A  Rd halmazra.

5.2.1. den cio: Legyen x1 : : :  xn n darab Rd -beli rogztett pont, A pedig az Rd -beli

halmazok egy csaladja. Ekkor legyen NA (x1  : : :  xn ) az fx1  : : :  xn g \ A

alaku halmazok szama, ha A 2 A. Vagyis NA (x1  : : :  xn ) azt mutatja, hogy az A-beli halmazokkal az x1  : : :  xn pontoknak hanyfele kulonboz}o reszhalmazat lehet kimetszeni. Az A halmazcsalad n-edik shatter egyutthatoja

s(A n) def =

max NA (x1  : : :  xn ):

x1 :::xn 2Rd

Nyilvanvaloan s(A n)  2n , hiszen egy n pontu halmaznak osszesen 2n reszhalmaza van. Ha s(A n) = 2n , vagyis valamely n pontra NA (x1  : : :  xn ) = 2n , akkor azt mondjuk, hogy A darabokra tori (vagy shattereli) fx1  : : :  xn g-t. Ha ez nem teljesul, akkor barmely n pontnak van olyan reszhalmaza, amelyet nem tudunk kivalasztani A-beli halmazzal. Az is nyilvanvalo, hogy ha valamely n0 -ra s(A n0 ) < 2n , akkor mar minden n > n0 -ra s(A n) < 2n . 0

5.2

83

Vapnik{Chervonenkis-elmelet

5.2.2. den cio: A legnagyobb n0 szamot, amelyre meg van olyan n0 pont, amelyet A

darabokra tor, vagyis

s(A n0 ) = 2n

0

az A csalad Vapnik{Chervonenkis-dimenziojanak (vagy VC-dimenziojanak) nevezzuk, es VA val jeloljuk. Ha minden n-re s(A n) = 2n , akkor dencio szerint VA = 1. Azokat az A halmazcsaladokat, amelyekre VA < 1, Vapnik{Chervonenkis- (vagy VC-) csaladoknak hvjuk.

5.2.1. tetel: (Vapnik{Chervonenkis) Minden  valoszn}usegi mertekre es A halmazosztalyra, minden n-re es " > 0-ra





P sup jn(A) ; (A)j > " A2A

2  8s(A n)e;n" =32

Bizonytas : Kovetjuk a Glivenko{Cantelli-tetel bizonytasanak menetet. Most is feltehetjuk, hogy n"2 2, hiszen kulonben a korlat trivialis ( 1). Az els}o ket lepesben teljesen ugyanugy bebizonytjuk, hogy











n X  P sup jn(A) ; (A)j > "  4P sup n1  iIfXi 2Ag > 4" A2A A2A

!

i=1

Az egyetlen kulonbseg a 3. lepesben van. 3. LE PE S: Vegyuk eszre, hogy rogztett x1  : : :  xn 2 Rd -re ahogy A vegigfut A-n a kulonboz}o (Ifxi 2Ag  : : :  Ifxn 2Ag ) vektorok szama nem mas, mint az fX1  : : :  Xn g kulonboz}o olyan reszhalmazainak a szama, amelyeket ugy kaphatunk, hogy A-beli halmazokkal elmetszszuk, ami dencio szerint legfeljebb s(A n). Ezert rogztett X1  : : :  Xn -re a szupremum a X  !  n 1 P sup n  iIfXi 2Ag > 4" A2A

i=1 legfeljebb NA (X1  : : :  Xn )  s(A n)

valoszn}usegben Az uniokorlattal kapjuk, hogy









valoszn}usegi valtozo maximuma.

!

n X  "  1 P sup n  iIfXi 2Ag > 4  X1  : : :  Xn  A2A i=1

  !  X n " 1     s(A n) sup P n  i=1 i IfXi 2Ag > 4  X1  : : :  Xn A2A

Igy, mivel a szupremum kvulre kerult, eleg a

   X ! n 1 "    P n  iIfXi 2Ag > 4  X1 : : :  Xn i=1

felteteles valoszn}usegre talalni egy exponencialis fels}o korlatot. Ezt a Glivenko{Cantelli-tetel bizonytasanak 4. lepesevel teljesen azonos modon tehetjuk meg, es gy vegul kapjuk, hogy

 P sup jn(A) ; (A)j > "  8s(A n)e;n" =32 : 2

A2A

84

5. FEJEZET Eloszlasbecsles

Ha a valoszn}usegi valtozoink valosak es az A halmazcsalad a (;1 x] alaku halmazokbol all, ahol x 2 R, akkor sup jn (A) ; (A)j = sup jFn (x) ; F (x)j

x2R A2A es s(A n) = n + 1, hiszen (;1 x] felegyenesekkel n pontnak n + 1 kulonboz}o reszhalmazat tudjuk kivalasztani:  fx1 g fx1  x2 g : : :  fx1  x2  : : :  xn g, ha x1 < x2 <    < xn .

Ekkor tehat a fenti tetel azt mondja, hogy



P sup jFn (x) ; F (x)j > "



x2R

2  8(n + 1)e;n" =32 :

Tehat a fenti tetel valoban altalanostja az empirikus eloszlasfuggveny konvergenciajara vonatkozo korabbi eredmenyt. A kovetkez}o tetel megmutatja a kapcsolatot egy halmazcsalad VC-dimenzioja es shatter egyutthatoja kozott.

5.2.2. tetel: Ha az A halmazcsalad VC-dimenzioja VA, akkor minden n-re s(A n) 

VA  X n i=1

i :

Alkalmazva a binomialis tetelt, ebb}ol mindjart az is kovetkezik, hogy s(A n)  (n +1)VA . S}ot az is bebizonythato, hogy VA > 2-re s(A n)  nVA es minden VA -ra s(A n)  nVA + 1. Ez azt jelenti, hogy a shatter egyutthatora vagy az igaz, hogy s(A n) = 2n minden n-re, vagy pedig az, hogy s(A n)  nVA + 1, ami akkor teljesul, ha A Vapnik{Chervonenkis-csalad, vagyis a VC-dimenzioja veges. pE rdekes, hogy s(A n) nem eshet a ket nagysagrend koze, azaz nem lehet peldaul nln n vagy 2 n nagysagrend}u. Ha VA < 1, akkor a Vapnik{Chervonenkisegyenl}otlenseg fels}o korlatja exponencialis sebesseggel csokken, ahogy n n}o. A fenti tetel fels}o korlatja eles.

5.2.3. tetel:

1. Ha A a felegyenesek ; ; csaladja, azaz A = f(;1 x]( x 2 Rg, akkor VA = 1 es s(A n) = n + 1 = n0 + n1 . 2. Ha A az intervallumok ; ; csal ; adja: A = fx1  x2 ]( x1  x2 2 Rg, akkor VA = 2 es s(A n) = n(n+1) 2

+ 1 = n0 + n1 + n2 .

Bizonytas : 1. -et mar lattuk.

2. -ben VA = 2 abbol latszik, hogy ha lerogztunk 3 pontot az egyenesen, akkor nincs olyan intervallum, amelyik tartalmazza a ket szels}ot, de a kozeps}ot nem. A shatter egyutthatot megkapjuk, ha eszrevesszuk, hogy legfeljebb n ; k + 1 halmaz van fA \ fX1  : : :  Xn g( A 2 Ag-ban amelyre jA \ fX1  : : :  Xn gj = k( k = 1 : : :  n es egy amelyre jA \ fX1  : : :  Xn gj = 0. Ebb}ol

s(A n) = 1 +

n X k=1

(n ; k + 1) = n(n2+ 1) + 1:

5.2

85

Vapnik{Chervonenkis-elmelet

A ltalanostsuk a fenti eredmenyt d dimenziora.

5.2.4. tetel: 1. Ha A = f(;1 x1 ]      (;1 xd ]g, akkor VA = d. 2. Ha A az osszes Rd -beli teglalap csaladja, akkor VA = 2d. ra.

Ezek utan megkaphatjuk az 5.1.3 tetel altalanostasat d-dimenzios valoszn}usegi valtozok-

5.2.5. tetel: Legyen X1 : : :  Xn 2 Rd fuggetlen, azonos eloszlasu valos ertek}u valoszn}usegi valtozo F (x) = P(X1  x) eloszlasfuggvennyel. Ekkor



!

P supd jFn (x) ; F (x)j > " x2R

2  8nd e;n" =32

es gy a Borel{Cantelli-lemma miatt lim sup jF (x) ; F (x)j = 0 n!1 x2Rd n 1 valoszn}useggel. Talan az egyik legfontosabb halmazcsalad az Rd -beli felterek csaladja.

5.2.6. tetel: Legyen A az Rd -beli felterek, azaz az fx : aT x b a 2 Rd  b 2 Rg alaku

reszhalmazok csaladja. Ekkor VA = d + 1. Nezzunk meg egy negatv peldat:

5.2.7. tetel: Ha A az osszes R2 -beli konvex sokszog csaladja, akkor VA = 1. Bizonytas : Legyenek x1  : : :  xn 2 R2 az egysegkor kulonboz}o pontjai, ekkor konny}u latni, hogy barmely reszhalmazukhoz letezik olyan konvex sokszog, amelyik pontosan azokat a pontokat tartalmazza.

86

5. FEJEZET Eloszlasbecsles

6. fejezet

S}ur}usegfuggveny becslese 6.1. Az L1 hiba Az egyenletes konvergencia ellenere az empirikus eloszlasfuggveny sokszor nem bizonyul eleg jo eloszlasbecslesnek. A mertekelmeletb}ol tudjuk, hogy az F (x) eloszlasfuggveny egyertelm}uen meghatarozza a (A) eloszlast. A Glivenko{Cantelli-tetel azt mondja, hogy az Fn (x) empirikus eloszlasfuggveny egyenletesen konvergal az F (x) eloszlasfuggvenyhez. U gy t}unik, hogy ezzel megoldottuk a (A) eloszlasbecslesenek problemajat. Sajnos a statisztikaban sok problema eseten a n(A) empirikus eloszlasbecsles hasznalhatatlan. Er}osebb hibakriteriumot kell keresnunk.

6.1.1. den cio: Ket valoszn}usegi mertek,  es  variacios tavolsaga V (  ) = sup j(A) ;  (A)j A

ahol a szupremumot az osszes Borel-halmaz felett vesszuk.

6.1.1. tetel: (Schee) Ha a  es  valoszn}usegi mertek abszolut folytonos f , illetve g s}ur}usegfuggvennyel, akkor Z 1 V (  ) = 2 jf (x) ; g(x)j dx: Bizonytas : Jelolje A = fx : f (x) g(x)g. Ekkor egyreszt

Z  Z   V (  ) = sup j(A) ;  (A)j = sup  f (x) dx ; g(x) dx

A A   A A Z  Z Z  

 f (x) dx ; g(x) dx = (f (x) ; g(x)) dx =  A A A 0 1 Z Z = 21 B @ (f (x) ; g(x)) dx + (g(x) ; f (x)) dxC A= A (A )c Z 1 =2

jf (x) ; g(x)j

87

dx:

88

6. FEJEZET Su}ru}segfuggveny becslese

Masreszt

 Z   Z Z Z    f (x) dx ; g(x) dx =  (f (x) ; g(x)) dx + ( f ( x ) ; g ( x )) d x         A A A\A A\(A )c 0 1 Z Z  max B (g(x) ; f (x)) dxC @ (f (x) ; g(x)) dx A A\A A\(A )c 0 1 Z Z  max B @ (f (x) ; g(x)) dx (g(x) ; f (x)) dxC A=  A (A )c Z 1 =2

jf (x) ; g(x)j

dx:

Z 1 V (  ) = 2 jf (x) ; g(x)j dx:

Tehat

Ebb}ol a tetelb}ol az kovetkezik, hogy ha talalunk egy L1 -ben konzisztens s}ur}usegfuggvenybecsl}ot, akkor abbol kaphatunk egy variacios tavolsagban konzisztens eloszlasbecsl}ot.

6.1.2. den cio: Az fn s}ur}usegfuggvenybecsl}o x-nek es az f s}ur}usegfuggvenyb}ol vett fug-

getlen, azonos eloszlasu X1  : : :  Xn mintaknak Borel-merhet}o fuggvenye:

fn(x) = fn(x X1  : : :  Xn): Ha fn egy L1 -ben konzisztens s}ur}usegfuggvenybecsl}o, azaz

Z

lim jjf ; fnjj = nlim !1 jf (x) ; fn(x)j dx = 0

n!1

(sztochasztikusan) 1 valoszn}useggel, akkor a

Z

~n(A) = fn(x) dx A

eloszlasbecsl}ore (sztochasztikusan) 1 valoszn}useggel.

6.2. A hisztogram

lim V ( ~n ) = 0

n!1

R

Ha f a  valoszn}usegi mertek s}ur}usegfuggvenye, akkor f = (A) minden Borel-merhet}o A

halmazra, f majdnem mindenhol egyenl}o a dd Radon{Nikodym-derivalttal, ahol  a Lebesgue-merteket jeloli. A legtobb s}ur}usegfuggveny-becsl}o ezt a derivaltat probalja kozelteni. Ket standard L1 -ben konzisztens s}ur}usegbecsl}o a hisztogram es a magfuggvenyes becsl}o.

6.2

89

A hisztogram

Legyen Pn = fAn1  An2  : : :g az Rd egy partcioja pozitv es veges Lebesgue-mertek}u cellakra. Ekkor a hisztogram becsl}o az

fn(x) = n((AAn((xx)))) n

fuggveny, ahol n az empirikus mertek, es An (x) = Anj , ha x 2 Anj . A cellak gyakran hn elhosszusagu d dimenzios kockak, ebben az esetben

fn(x) = n(Ahnd (x)) n

6.2.1. tetel: Tegyuk fel, hogy -nek letezik f s}ur}usegfuggvenye. Ha a hisztogram becsl}o-

nel minden origo kozeppontu S gombre

sup diam(Anj ) = 0

lim

n!1 j :Anj \S 6=

es

jfj : Anj \ S 6= gj = 0 lim n!1 n

akkor

lim

Z

n!1

jf (x) ; fn (x)j (dx) = 0

1 valoszn}useggel, ahol diam(A) = sup jjx ; yjj. xy2A

Bizonytas :

Z

Z Z jfn(x) ; f (x)j (dx)  jfn (x) ; Efn (x)j (dx) + jEfn(x) ; f (x)j (dx) | {z } | {z } variacios tag

torztas

ahol Efn(x) a mintak szerinti varhato erteket jeloli. Variacios tag:

Z

jfn (x) ; Efn(x)j (dx) =

XZ

j Anj

jfn (x) ; Efn(x)j (dx) =

X j

jn (Anj ) ; (Anj )j

hiszen fn (x) konstans minden cellan. Jelolje Mn = jfj : Anj \ S 6= gj es szamozzuk at a cellakat ugy, hogy An1  An2  : : :  AnMn MSn legyen az az Mn cella, amelyre Anj \ S 6= . Legyen Sn = Anj .

Z

jfn (x) ; Efn(x)j  

X

j =1

jn (Anj ; (Anj )j + n (Snc ) + (Snc ) 

X jn (Anj ) ; (Anj )j + jn (Snc ) ; (Snc )j + 2(Snc )  X c c c



jn (Anj ) ; (Anj )j + jn (Sn ) ; (Sn )j + 2(S

)

90

6. FEJEZET Su}ru}segfuggveny becslese

Legyen A azon halmazok csaladja, amelyek az An1  An2  : : :  AnMn  Snc veges egyestesei. Ekkor a Sche#e-tetel miatt Mn X

jn (Anj ) ; (Anj )j + jn (Snc ) ; (Snc )j = 2 sup jn (A) ; (A)j A2A j =1

tehat 2(S c ) < " eseten a Vapnik{Chervonenkis-egyenl}otlenseg miatt

P

Z



jfn (x) ; Efn(x)j (dx) > "  P







2 sup jn (A) ; (A)j + 2(S c ) > " A2A



= P sup jn (A) ; (A)j > 2" ; (S c) A2A

=



" c 2  8s(A n)e;n( 2 ;(S )) =32  " c 2  8  2Mn +1 e;n( 2 ;(S )) =32

A tetel masodik feltetele miatt

Mn ! 0 n

tehat elegend}oen nagy n-re a jobb oldal kisebb, mint " e;n( ;(S c )) =64  2

2

amely osszegezhet}o, tehat a Borel{Cantelli-lemma miatt a variacios tag tart 0-hoz 1 valoszn}useggel. Torztas:

Z Z  ( A ( x )) 1 n Efn(x) = (A (x)) = (A (x)) f (z ) (dz) = f (z)Kn (x z ) (dz ) n n An (x)

ahol Kn (x z ) = Ifz(2AAnn(xx))g . Ha f folytonos, es egy kompakt halmazon kvul 0, akkor egyenletesen folytonos, ezert a tetel els}o feltetele miatt a torztas 0-hoz tart. Legyen most f tetsz}oleges, ekkor " > 0-hoz letezik olyan f~, amely folytonos, egy kompakt halmazon kvul 0, es ( )

Z

Ekkor

jf (x) ; f~(x)j (dx) < ":

 Z  Z jf (x) ; Efn(x)j (dx) = f (x) ; f (z )Kn (x z ) (dz ) (dx)   Z Z  Z ~ ~ ~   jf (x) ; f (x)j (dx) + f (x) ; f (z )Kn (x z ) (dz ) (dx)+  Z Z Z +  f~(z )Kn (x z ) (dz ) ; f (z )Kn (x z ) (dz ) (dx)   Z  Z ~ ~   " + f (x) ; f (z )Kn (x z ) (dz ) (dx)+

Z

6.2

A hisztogram

+

Z Z

91



jf~(z ) ; f (z )jKn (x z ) (dx) (dz ) =

 Z  Z Z ~ ~   = " + f (x) ; f (z )Kn (x z ) (dz ) (dx) + jf~(z ) ; f (z )j (dz )

!

2"

Itt igazabol elmondtuk a Banach{Steinhaus-tetel bizonytasat, amely szerint ha egy operatorsorozat pontonkent konvergal egy s}ur}u halmazon, es az operatornormak sorozata korlatos, akkor minden pontban konvergal.

6.2.2. tetel: Ha f egy origo kozep}u S kockan kvul 0, Lipschitz-folytonos, azaz jf (x) ; f (z )j  C jjx ; z jj

akkor hn oldalhosszusagu d-dimenzios kockakbol allo partcio eseten a hisztogramra

Z

E jf ; fnj  pc1 d + c2 hn nhn

tehat

hn = c3 n; d

1 +2

Z

valasztasra

E jf ; fnj  cnn; d : 1 +2

Bizonytas :

Z

Z Z E jf (x) ; fn(x)j (dx)  jf (x) ; Efn(x)j (dx) + E jfn(x) ; Efn(x)j (dx) | {z } | {z } torztas

variacio

Variacio: Legyen S olyan, hogy (S c ) = 0. Jelolje Mn azon cellak szamat a partcioban, amelyek metszik S) S -et, Mn = jfj : Anj \ S 6= gj  Vol( hdn . Akkor

Z



X

E

Z

E jfn(x) ; Efn(x)j (dx) 

j : Anj \S 6= Anj

= 

jfn(x) ; Efn(x)j

X

j : Anj \S 6=

Z

(dx) + 2Efn(x) (dx) = Sc

E jn(Anj ) ; (Anj )j 

X q

j : Anj \S 6=

=

E jn(Anj ) ; (Anj )j2 =

X r (Anj )(1 ; (Anj )) 

j : Anj \S 6=

n

92

6. FEJEZET Su}ru}segfuggveny becslese



v P (A )(1 ; (A )) u u nj t j: Anj \S6= nj

(a Cauchy{Schwarz-egyenl}otlenseg miatt)

n

s



Torztas:

Z

 Mn 

Vol(S ) :

nhdn

 Z  Z jf ; Efnj = f (x) ; f (z )Kn (x z ) (dz ) (dx  ZZ jf (x) ; f (z )jKn (x z ) (dz ) (dx) 



 

ZZ

ZZ

C jjx ; zjjKn (x z) (dz) (dx)  ChnKn(x z ) (dz ) (dx) = Chn

A magfuggvenyes becsl}ot a nemnegatv, merhet}o K (x) magfuggveny es a pozitv hn sorozat hatarozza meg:

x ; Xi  n X 1 fn(x) = nhd K h n i=1

n

lim h = 0 n!1 n

es

6.2.3. tetel: Tegyuk fel, hogy -nek letezik f s}ur}usegfuggvenye. Ha a magfuggvenyes

becsl}onel

Z

K (x) (dx) = 1

akkor

lim

n!1

Z

lim nhdn = 1

n!1

jf (x) ; fn (x)j (dx) = 0

1 valoszn}useggel, vagyis a magfuggvenyes becsl}o is er}osen konzisztens. Peldak magfuggvenyre: 

Naiv magfuggveny

K (x) = Ifx2S r g

ahol S0r origo kozep}u r sugaru gomb.  Gauss magfuggveny

0

K (x) = e;jjxjj



Cauchy magfuggveny



Epanechnikov magfuggveny

2

K (x) = 1 + jj1xjjd+1 K (x) = (1 ; jjxjj2 )Ifjjxjj1g

6.2

93

A hisztogram

6.2.4. tetel: Ha f egy origo kozep}u S gombon kvul 0, f di#erencialhato es a gradiens Lipschitz-folytonos, azaz jjf 0 (x) ; f 0 (z )jj  C jjx ; z jj akkor a magfuggvenyes becslesre

Z

E jf ; fnj  pc1 d + c2 h2n nhn

tehat valasztasra

hn = c3 n; d

1 +4

Z

E jf ; fnj  c4n; d : 2 +4

A parameteres statisztikaban a konzisztencia tisztazasa utan az a legfontosabb kerdes, hogy adott pontossaghoz mekkora mintanagysag kell, azaz mekkora az illet}o becsles konvergenciasebessege. S}ur}usegfuggveny-becsles eseteben, ha nem teszunk fel semmit az f s}ur}usegfuggvenyr}ol, akkor nem tudunk semmit mondani a konvergenciasebessegr}ol, s}ur}usegbecsl}ok minden ffn g sorozatara igaz az, hogy a varhato L1 -hiba konvergenciasebessege tetsz}olegesen kicsi lehet.

6.2.5. tetel: S}ur}usegbecsl}ok minden ffng sorozatahoz es pozitv szamok minden monoton, 0-hoz tarto an < 321 sorozatahoz letezik f s}ur}usegfuggveny ugy, hogy Ejjf ; fnjj > an

minden n-re.

94

6. FEJEZET Su}ru}segfuggveny becslese

7. fejezet

Regressziobecsles 7.1. A regresszios problema Legyen Y valos ertek}u valoszn}usegi valtozo es legyen X d-dimenzios veletlen vektor (meggyeles). X koordinatai kulonboz}o eloszlasuak lehetnek, lehet nemelyik diszkret (peldaul binaris), masok lehetnek abszolut folytonosak. Igy nem teszunk fel semmit X eloszlasarol. A regresszioanalzis celja Y becslese, ha X adott, azaz olyan f fuggvenyt keresunk, amely X ertekkeszleten van denialva, es amelyre f (X ) "kozel" van Y -hoz. Tegyuk fel, hogy az analzis f}o celja a negyzeteskozep-hiba minimalizalasa: min E((f (X ) ; Y )2 ): f Jol ismert, hogy a minimumot az

m(x) = E(Y j X = x) regressziofuggveny eri el, ugyanis minden f merhet}o fuggvenyre

E((f (X ) ; Y )2 ) = E((m(X ) ; Y )2 ) + E((m(X ) ; f (X ))2 ) = = E((m(X ) ; Y )2 ) +

Z

jm(x) ; f (x)j2

(dx)

ahol  az X eloszlasat jeloli. A jobb oldal masodik tagjat a f fuggveny integralt negyzetes hibajanak nevezik, es J (f )-fel jelolik

J (f ) =

Z

jm(x) ; f (x)j2

(dx):

A negyzetes kozep hiba nyilvan pontosan akkor lesz kozel a minimumhoz, ha a J (f ) kozel van a 0-hoz. A s}ur}usegbecslessel szemben, ahol az L1 -hiba volt a legalkalmasabb hibakriterium, itt az L2 -hiba a legfontosabb. Raadasul a s}ur}usegbecslesnel az L1 -teret a Lebesgue-mertekkel denialtuk, mg a regressziobecslesnel az L2 -teret -vel denialjuk. A regressziobecsles feladatanal legyenek (X1  Y1 ) : : :  (Xn  Yn ) fuggetlen, azonos eloszlasu peldanyai (X Y )-nak. Az mn regressziobecsl}o x-nek es az (Xi  Yi ) mintaknak merhet}o fuggvenye: mn = mn(x (X1  Y1 ) : : :  (Xn  Yn )): Az mn regressziobecsles m-hez valo L2 () konvergenciajat vizsgaljuk. 95

96

7. FEJEZET Regresszio becsles

7.1.1. den cio: Az mn becsl}o gyengen univerzalisan konzisztens, ha J (mn ) ! 0 sztochasztikusan (X Y ) minden olyan eloszlasara, amelyre EjY j2 < 1.

7.1.2. den cio: Az mn becsl}o er}osen univerzalisan konzisztens, ha J (mn ) ! 0 1 valoszn}useggel (X Y ) minden olyan eloszlasara, amelyre EjY j2 < 1.

7.2. Lokalis atlagolason alapulo becsl}ok A lokalis atlagolo regressziobecsl}ok az

mn (x) =

n X i=1

Wni (x X1  : : :  Xn )Yi

alaku becsl}ok, ahol a Wni sulyok jellegzetesen nemnegatvak, osszeguk 1, tovabba Wni nagy, ha x kozel van Xi -hez, kulonben kicsi. Ilyen tpusu regressziobecsl}o a hisztogram, a magfuggvenyes es a legkozelebbi szomszed becsl}o. Legyen Pn = fAn1  An2  : : :g az Rd egy partcioja, es minden x 2 Rd -re jelolje An (x) az x-et tartalmazo cellat. Ekkor a hisztogrambecsl}o

8X n > Yi IfXi 2An (x)g > > < i=1n  mn (x) = > X IfXi 2An (x)g > > i =1 :0

ha

n X i=1

IfXi 2An (x)g > 0

kulonben.

A cellak gyakran hn elhosszusagu d-dimenzios kockak.

7.2.1. tetel: Ha minden origo kozep}u S gombre lim

sup

n!1 j : Anj \S 6=

es

diam(Anj ) = 0

jfj : Anj \ S 6= gj lim = 0 n!1 n

akkor a hisztogram regressziobecsl}o er}osen konzisztens, ha jY j  L valamely L < 1-re 1 valoszn}useggel. Megjegyzes : Ha a cellak hn elhosszusagu kockak, akkor a tetel feltetelei: hn ! 0 es

nhdn ! 1.

Miel}ott raternenk a tetel bizonytasara, kimondjuk es bebizonytjuk a Hoe#ding-egyenl}otlenseg egy, McDiarmidtol szarmazo altalanostasat, amelyre a 7.2.1 tetel bizonytasanal szuksegunk lesz. Ehhez el}oszor vezessuk be a martingal fogalmat.

7.2

ha

97

Lokalis atlagolason alapulo becslo} k

7.2.1. den cio: Valoszn}usegi valtozok egy Z1 Z2  : : : sorozatat martingal nak nevezzuk, E fZi+1jZ1  : : :  Zi g = Zi 1 valoszn}useggel

minden i > 0-ra. Legyen X1  X2  : : : valoszn}usegi valtozok egy tetsz}oleges sorozata. Z1  Z2  : : :-t az X1  X2  : : : sorozat szerinti martingal nak nevezzuk, ha minden i > 0-ra Zi az X1  : : :  Xi egy fuggvenye es E fZi+1jX1  : : :  Xi g = Zi 1 valoszn}useggel. Nyilvanvalo, hogy ha Z1  Z2  : : : az X1  X2  : : : sorozat szerinti martingal, akkor Z1  Z2  : : : martingal, hiszen

E fZi+1 jZ1 : : :  Zi g = E fE fZi+1 jX1  : : :  Xi g jZ1  : : :  Zi g = E fZi jZ1  : : :  Zi g

= Zi : A legfontosabb pelda martingalra a fuggetlen, nulla varhato ertek}u valoszn}usegi valtozok osszege. Legyen U1  U2  : : : fuggetlen valoszn}usegi valtozo nulla varhato ertekkel. Ekkor az

Si =

Xi j =1

Uj  i > 0

martingal.

7.2.2. den cio: Valoszn}usegi valtozok egy V1  V2  : : : sorozatat martingal dierencia sorozat nak nevezzuk, ha E fVi+1jV1  : : :  Vi g = 0 1 valoszn}useggel minden i > 0-ra. V1  V2 : : :-t az X1  X2  : : : sorozat szerinti martingal dierencia sorozat nak nevezzuk, ha minden i > 0-ra Vi az X1  : : :  Xi egy fuggvenye es E fVi+1jX1  : : :  Xi g = 0 1 valoszn}useggel. Minden Z1  Z2  : : : martingal termeszetes modon vezet egy martingal di#erenciahoz:

Vi = Zi ; Zi;1 :

7.2.2. tetel: (Azuma{Hoeding) Legyen X1  X2  : : : valoszn}usegi valtozok egy sorozata es V1  V2  : : : az X1  X2  : : : sorozat szerinti martingal di#erencia sorozat. Tegyuk fel, hogy letezik valoszn}usegi valtozok egy Z1 Z2  : : : sorozata es nemnegatv c1  c2  : : : konstansok ugy, hogy minden i > 0-ra Zi az X1  : : :  Xi;1 egy fuggvenye es Zi  Vi  Zi + ci 1 valoszn}useggel. Ekkor minden " > 0-ra es n-re

P

(X n i=1

)

Vi "

n i=1

;2"2 P c2i

e

98

7. FEJEZET Regresszio becsles

es

P

(X n i=1

)

V i  ;"

n

;2"2 P c2i

e

i=1

:

A bizonytas a Hoe#ding-egyenl}otlenseg bizonytasanak kiterjesztese. Szuksegunk lesz az 5.1.1 lemma analogjara:

7.2.1. lemma: Tegyuk fel, hogy a V es Z valoszn}usegi valtozokra 1 valoszn}useggel igaz, hogy EfV jZ g = 0 es, hogy valamely f fuggvenyre es c 0 konstansra f (Z )  V Ekkor minden s > 0-ra



E esV jZ

 f (Z ) + c:

  es c =8: 2 2

A 7.2.2 tetel bizonytasa: A Hoe#ding-egyenl}otlenseg bizonytasahoz hasonloan most is a Cherno#-technikat hasznaljuk. Pk Legyen Sk = Vi . Ekkor minden s > 0-ra i=1

PfSn "g





e;s" E esSn    = e;s" E esSn; E esVn jX1  : : :  Xn;1    e;s" E esSn; es cn =8 (7.2.1 lemma miatt) 

1 1

n

s2 P c2i =8 ; s"  e e i=1 n ;2"2 P c2i

= e

i=1

2 2

(ismetelve az el}oz}o lepeseket)

(ha s = 4"=

Pn c2 ).

i=1

i

A masodik egyenl}otlenseg hasonloan bizonythato.

7.2.3. tetel: (McDiarmid)

Legyenek X1  : : :  Xn fuggetlen valoszn}usegi valtozok, amelyek ertekuket egy A halmazbol veszik, es tegyuk fel, hogy f : An ! R fuggvenyre teljesul, hogy sup jf (x1  : : :  xn ) ; f (x1  : : :  xi;1  x0i  xi+1  : : :  xn )j  ci  1  i  n:

x1 :::x n x0i 2A

Ekkor minden " > 0-ra

P ff (X1  : : :  Xn ) ; Ef (X1 : : :  Xn ) "g  e es

P fEf (X1 : : :  Xn ) ; f (X1  : : :  Xn ) "g  e

n i=1

;2"2 / P c2i n

;2"2 / P c2i i=1

 :

re,

99

Lokalis atlagolason alapulo becslo} k

7.2

Bizonytas : Legyen V = f (X1  : : :  Xn ) ; Ef (X1 : : :  Xn ), V1 = EfV jX1 g ; EV , es k > 1-

Vk = EfV jX1 : : :  Xk g ; EfV jX1  : : :  Xk;1 g:

n Igy V = P Vk . Vilagos, hogy V1  : : :  Vn az X1  : : :  Xn szerinti martingal di#erencia sorozatot k=1 alkot. Denialjuk a kovetkez}o valoszn}usegi valtozokat

Hk (X1  : : :  Xk ) = E ff (X1  : : :  Xn )jX1  : : :  Xk g 

Z

ekkor

Vk = Hk (X1  : : :  Xk ) ; Hk (X1  : : :  Xk;1  x)Fk (dx)

ahol Fk az Xk eloszlasfuggvenye. Vezessuk be a



Z





Z



Wk = sup Hk (X1  : : :  Xk;1  u) ; Hk (X1  : : :  Xk;1  x)Fk (dx)  u

es a

Zk = inf Hk (X1  : : :  Xk;1 v) ; Hk (X1  : : :  Xk;1  x)Fk (dx) : v

valoszn}usegi valtozokat. Vilagos, hogy Zk  Vk  Wk 1 valoszn}useggel. Mivel minden k-ra Pn Zk az X1 : : :  Xk;1 egy fuggvenye, alkalmazhatjuk a 7.2.1 lemmat V = Vk -ra, ha meg k=1 tudjuk mutatni, hogy Wk ; Zk  ck . De ez kovetkezik a tetel feltetelei miatt

Wk ; Zk = sup sup (Hk (X1  : : :  Xk;1  u) ; Hk (X1  : : :  Xk;1  v))  ck  u

v

Pn

Megjegyzes : Ha az Xi -k korlatosak, akkor az f (x1  : : :  xn ) = xi valasztassal a Hoe#i=1 ding-egyenl}otlenseghez jutunk. A 7.2.1 tetel bizonytasa: A tetelt arra az esetre bizonytjuk, amikor m(x) folytonos. A celunk azt bebizonytani, hogy

Z

lim

n!1

1 valoszn}useggel. Legyen

(mn(x) ; m(x))2 (dx) = 0

Pn Y I

i fXi 2An (x)g

mn(x) = i=1n(A (x))  n

Z

ekkor 2

Z

(mn (x) ; m(x))2 (dx) 

(mn (x) ; mn (x))2 (dx) +

Z



(mn (x) ; m(x))2 (dx) =

= 2J1 + 2J2

100

7. FEJEZET Regresszio becsles

J2 1 valoszn}useg}u konvergenciajahoz megmutatjuk, hogy

Z

P amib}ol

J2 =

Z



2 2 jmn (x) ; m(x)j (dx) > "  e;n" =(32L ) 

jmn (x) ; m(x)j2 (dx)  2L

Z

jmn (x) ; m(x)j

(dx)

es a Borel{Cantelli-lemma miatt kovetkezik J2 1 valoszn}useg}u konvergenciaja.

Z

+

jmn (x) ; m(x)j

Z

Z

jmn (x) ; m(x)j

Z

jm (x) ; m(x)j (dx) ; E

n

A haromszog egyenl}otlensegb}ol



Z

(dx) = E

(dx)+



jm (x) ; m(x)j (dx)

n

(*)

Z

E jmn(x) ; m(x)j (dx)  jEmn(x) ; m(x)j

(dx) + E

Z

jmn (x) ; Emn(x)j

(dx)

ahol az els}o tag a torztas, a masodik a variacio. A kozepertektetel miatt R m(z) (dz) Z Ifz2An(x)g Emn(x) = (A (x)) m(z)(dz) = An(x) (A (x)) = m(an(x)) n

n

valamely an (x) 2 An (x)-re. Torztas: Mivel m(x) folytonos, egyenletesen is folytonos az origo kozep}u S gombon: 8 > 0-hoz 90 > 0: 0 jjx ; z jj <  eseten jm(x) ; m(z )j < .

Z

= =

Z ZS S

jEmn(x) ; m(x)j

jEm (x) ; m(x)j (dx) +

n

jm(an (x)) ; m(x)j

Z

Sc

(dx) +

Z

(dx) =

jEmn(x) ; m(x)j

(dx) =

jEmn(x) ; m(x)j

(dx) 

Sc   + 2L(S c ) 

"

4 hiszen ha jY j  L 1 valoszn}useggel, akkor jm()j  L. Tehat a torztas 0-hoz tart. Variacio: Jelolje Mn azon cellak szamat a partcioban, amelyek metszik S -et, Mn = jfj : Anj \ S 6= gj.

Z

=E

Z S

E jmn(x) ; Emn(x)j (dx) = jm (x) ; Em (x)j (dx) + E

n

n

Z

Sc

jmn (x) ; Emn(x)j

(dx) 

7.2

101

Lokalis atlagolason alapulo becslo} k  

X

E

Z

j : Anj \S 6= Anj

jmn (x) ; Emn(x)j

(dx) + 2L(S c ) 

X Z q

E jmn(x) ; Emn(x)j2 (dx) + 2L(S c) 

j : Anj \S 6=Anj 

X Z s nL2(Anj ) (dx) + 2L(S c )  (n(Anj ))2

j : Anj \S 6=Anj 

r

X

L (Annj ) + 2L(S c)  j : Anj \S 6=

 LMn

v P u 1 u t Mn j: Anj \S6= (Anj )

(Jensen-egyenl}otlenseg)

n

r

+ 2L(S c ) 

Mn + 2L(S c)  " n 4 hiszen a tetel masodik feltetele szerint Mnn ! 0, es (S c ) tetsz}olegesen kicsive tehet}o. Igy tehat eleg nagy n-re Z E jm (x) ; m(x)j (dx)  "  L

n

tehat (*) miatt P

Z

P

Z

2

jmn(x) ; m(x)j

jm (x) ; m(x)j (dx) ; E

n

Z



(dx) > "



jm (x) ; m(x)j (dx) >

n

"



2 A jobb oldalon allo valoszn}usegre a McDiarmid-egyenl}otlenseggel kaphatunk exponencialis fels}o korlatot. Rogztsuk le az (x1  y1 ) : : :  (xn  yn ) 2 Rd  ;L L] mintainkat es csereljuk ki (xi  yi )-t 0 (xi  yi0 )-re. Jeloljuk mni-vel az gy kapott becsl}ot. Ekkor mn (x) es mni(x) maximum ket cellan, An (xi )-n es An (x0i )-n, kulonbozik, gy

Z

jm (x) ; m(x)j (dx) ;

n



Z

Z

jmni(x) ; m(x)j

jmn(x) ; mni (x)j

(dx) 

(dx) 

2L 2L 4L 0 n(An (xi )) (An (xi )) + n(An(x0i)) (An (xi ))  n Tehat a McDiarmid-egyenl}otlenseg feltetele ci = 4nL -nel teljesul, gy 

P

Z

jm (x) ; m(x)j (dx) ; E

n

Z

jm (x) ; m(x)j (dx) >

n

"   e;n" =(32L )

2

2

2

102

7. FEJEZET Regresszio becsles

Tehat eleg nagy n -re

P

Z



2 2 jmn (x) ; m(x)j (dx) > "  e;n" =(32L ) 

amib}ol kovetkezik, hogy J2 ! 0 1 valoszn}useggel. J1 1 valoszn}useg}u konvergenciajanak belatasahoz vegyuk eszre, hogy ha n(An (x)) 6= 0, akkor  n n

 P YiIfX 2A (x)g P YiIfX 2A (x)g  i n i n    ; i=1 jmn (x) ; m(x)j =  i=1 n  P  n(An(x)) IfXi 2An (x)g  i=1     n X  1 1  = L IfXi 2An (x)g   n(A (x)) ; P n n  i=1 IfXi 2An (x)g   i=1  Pn   IfXi2An (x)g  = L  i=1n(A (x)) ; 1 = L jMn (x) ; 1j  n  

ahol Mn (x) az mn(x) specialis alakja, ha Y  1. Ha n (An (x)) = 0, akkor

jmn (x) ; mn (x)j = 0  L jMn (x) ; 1j :

Igy tehat

Z

Z

J1 = (mn(x) ; mn(x))2 (dx)  L2 (Mn (x) ; 1)2 (dx) ! 0 1 valoszn}useggel J2 1 valoszn}useg}u konvergenciaja miatt. Tehat a tetelt bebizonytottuk. A magfuggvenyes regressziobecsl}ot, a s}ur}usegbecsl}ohoz hasonloan, az abszolut integralhato K (x) magfuggveny es a pozitv hn simtotenyez}o hatarozza meg

Pn Y K  x;Xi i hn i =1 mn (x) = P  n K x;Xi hn

i=1

7.2.3. den cio: A K (x) magfuggveny regularis, ha nemnegatv es letezik S0r origo ko-

zeppontu, r > 0 sugaru gomb es b > 0 konstans ugy, hogy

K (x) bIfx2S r g 0

es

Z

sup K (u) dx < 1:

u2x+S0r

7.3

103

Empirikus hibaminimalizalas

7.2.4. tetel: Ha a K (x) magfuggveny regularis, hn ! 0, nhdn ! 1 es jY j  L valamely

L < 1-re 1 valoszn}useggel, akkor a magfuggvenyes regressziobecsl}o er}osen konzisztens.

A kn -legkozelebbi szomszed becsl}o az x-hez legkozelebbi kn darab Xi mintahoz tartozo Yi -ket atlagolja. Legyen (X(1n) (x) Y(1n) (x)) : : :  (X(nn) (x) Y(nn) (x)) az Xi-k x-t}ol vett tavolsaga szerint noveked}oen rendezett minta. X(in) (x) az x i-edik legkozelebbi szomszedja. Ha jjXi ; xjj = jjXj ; xjj, akkor Xi kozelebbi, ha i < j . Ekkor

mn (x) = k1

kn X

n i=1

Y(in) (x)

7.2.5. tetel: Ha az jjX ; xjj valoszn}usegi valtozo abszolut folytonos minden x-re, kn !

1, kn =n !

0 es jY j  L valamely L < 1-re 1 valoszn}useggel, akkor a kn -legkozelebbi szomszed regressziobecsl}o er}osen konzisztens. Tehat leteznek univerzalisan konzisztens regressziobecsl}ok, de a konvergenciasebesseg, a s}ur}usegfuggveny-becsleshez hasonloan, itt is tetsz}olegesen kicsi lehet.

7.2.6. tetel: Regressziobecsl}ok minden fmng sorozatahoz es pozitv szamok minden monoton 0-hoz tarto an < 1=64 sorozatahoz letezik (X Y )-nak olyan eloszlasa, amelyre X egyenletes eloszlasu 0 1]-en, Y = m(X ) es

Z

EJ (mn) = E (mn(x) ; m(x))2 (dx) > an minden n-re.

7.3. Empirikus hibaminimalizalas Az eddig ismertetett regressziobecslesi modszerek a lokalis atlagolas elven alapulnak. Letezik egy masik, hasonloan termeszetes alapelv, az empirikus hibaminimalizalas, amely szinten elvezethet univerzalisan konzisztens becslesekhez. Valasztunk egy Fn fuggvenycsaladot, es a regressziobecsles ebb}ol a csaladbol vehet fuggvenyeket. Az Fn kivalasztasakor vagy az m(x) regressziofuggvenyr}ol szerzett ismereteink jatszhatnak szerepet, vagy Fn olyan fuggvenyekb}ol all, amelyek szamtogeppel bizonyos szamtasi bonyolultsaggal realizalhatok. Korabban mar lattuk, hogy az m(x) regressziofuggveny minimalizalja az L2 -hibat. Tehat mondhatnank azt, hogy minimalizaljuk E(f (X ) ; Y )2 -t az Fn csaladon. Ez azonban nyilvanvaloan lehetetlen, mert a minimalizalando fuggveny fugg az (X Y ) ismeretlen eloszlasatol.

7.3.1. den cio: Az empirikus L2-hiba a mintakon elkovetett hibak negyzeteinek atlaga: n 1X (f (X ) ; Y )2

n i=1

i

i

Az empirikus hibaminimalizalas soran azt a fuggvenyt valasztjuk ki Fn-b}ol, amelynek az empirikus hibaja minimalis:

 X 1 n

mn = argmin n (f (Xi ) ; Yi )2 f 2Fn i=1

!

104

7. FEJEZET Regresszio becsles

A kerdes, hogy mekkora az gy valasztott mn (x) becsl}o L2 hibaja.

Z

jmn (x) ; m(x)j2





(dx) =





= E jmn (X ) ; Y j2 j Dn ; E jm(X ) ; Y j2 =



= E jmn







E n ; finf 2Fn

(X ) ; Y j2 j D





jf (X ) ; Y j2



+ finf E jf (X ) ; Y j2 ; E jm(X ) ; Y j2 2F





+

n

A jobb oldalon szerepl}o els}o tag a becslesi hiba, a masodik tag pedig az approximacios hiba. A becslesi hiba azt meri, hogy a becsl}o L2 -hibaja mennyire ter el a fuggvenycsaladbeli legjobb fuggveny L2 -hibajatol, az approximacios hiba pedig azt, hogy mennyire jol lehet a regressziofuggvenyt Fn-beli fuggvenyekkel kozelteni L2 ertelemben. Ha az Fn csalad nagy, akkor az approximacios hiba ugyan lehet nagyon kozel 0-hoz, de lehet, hogy nincs eleg mintank ahhoz, hogy Fn-b}ol jo becsl}ot valasszunk, azaz a becslesi hiba nagy lehet. Ha Fn kicsi, akkor pedig az approximacios hiba lehet nagyon nagy. Ahhoz, hogy univerzalisan konzisztens becsl}ot kapjunk, azt kell megmutatni, hogy mindket tag 0-hoz tart. Az approximacios hibara ez gyakran eleg egyszer}u. El}oszor is konnyen lathato, hogy inf

f 2Fn

E jf (X ) ; Y j2 ; E jm(X ) ; Y j2

= finf 2F

Z

n

jf (x) ; m(x)j

(dx):

Ha peldaul Fn  Fn+1 minden n-re, akkor az, hogy minden  mertekre es m 2 L2 -re lim inf

Z

n!1 f 2Fn

egyszer}uen azt jelenti, hogy

S1 F

S1 F

n=1

n

jf (x) ; m(x)j2

(dx) = 0

s}ur}u L2 ()-ben minden  mertekre. Ez igaz peldaul, ha

s}ur}u C01 (Rd )-ben a szupremum norma szerint, mivel C01(Rd ) s}ur}u L2 ()-ben minden  eloszlasra es Z jf (x) ; m(x)j2 (dx)  jjf ; mjj21

n=1

n

Most nezzuk tehat a becslesi hibat.

7.3.1. lemma:





E jmn (X ) ; Y j2 j Dn ; finf E jf (X ) ; Y j2  2Fn

 X  n 1  2 sup  jf (Xi ) ; Yi j2 ; E jf (X ) ; Y j2    n f 2Fn i=1

Bizonytas :





E jmn (X ) ; Y j2 j Dn ; finf E jf (X ) ; Y j2 = 2Fn   n 1X 2 = sup E (mn (X ) ; Y ) j Dn ; n jmn (Xi ) ; Yi j2 + f 2Fn

i=1

7.3

105

Empirikus hibaminimalizalas

+ n1

n X

jmn(Xi ) ; Yi j2 ;

i=1 n X

+1

n i=1



 

n 1X jf (X ) ; Y j2 +

n i=1

i

jf (Xi ) ; Yi j2 ; E jf (X ) ; Y j2

!

i



n X sup E (mn (X ) ; Y )2 j Dn ; n1 jmn (Xi ) ; Yi j2 + f 2Fn i=1 ! n X 1 2 2 + jf (X ) ; Y j ; E jf (X ) ; Y j  i

n i=1

i

  X n 1  2 2 jf (Xi ) ; Yi j ; E jf (X ) ; Y j   2 sup    n f 2Fn i=1

Az els}o egyenl}otlenseg mn valasztasabol adodik, mn minimalizalja az empirikus L2 -hibat Fnben, gy 8f 2 Fn-re n n 1X 1X 2 jmn (Xi ) ; Yi j2 ; n n jf (Xi ) ; Yij  0 i=1

i=1

Tehat ahhoz, hogy megmutassuk, hogy a becslesi hiba 0-hoz tart, a lemma jobb oldalan allo kifejezest kell vizsgalnunk. Legyen Z = (X Y ) Zi = (Xi  Yi ) i = 1 : : :  n gf (x y) = jf (x) ; yj2 minden f 2 Fn-re es Gn = fgf : f 2 Fng. Ekkor a fenti kifejezes a kovetkez}o alakban rhato

 X  n 1  sup  n g(Zi ) ; Eg(Z ): g2Gn i=1

Tehat egy atlag es a varhato erteke kozotti kulonbseget akarjuk felulr}ol becsulni egyenletesen egy fuggvenycsalad felett. Ha g korlatos, azaz g : Rd R ! 0 M ], akkor a Hoe#ding-egyenl}otlensegb}ol kapjuk, hogy

 !  X n 1  P  n g(Zi ) ; Eg(Z ) > "  2e;2n" =M i=1 2

7.3.2. lemma:

2

  X   X n n 1 1    sup  n g(Zi ) ; Eg(Z )  M sup  n Ifg(Zi )>tg ; P (g(Z ) > t) g2Gn i=1 g2Gn i=1 t>0

Bizonytas : Hasznaljuk a nemnegatv valoszn}usegi valtozokra ervenyes

Z1 0

azonossagot.

P(X > t) dt = EX

 X  n 1  sup  n g(Zi ) ; Eg(Z ) = g2Gn i=1

106

7. FEJEZET Regresszio becsles

Z1  n !  X  = sup  n1 Ifg(Zi )>tg ; P (g(Z ) > t) dt  g2Gn   i=1 0   X n 1  Ifg(Zi )>tg ; P (g(Z ) > t)  M sup   n g2Gn i=1 t>0

Legyen

G^ n = ffz : g(z) > tg : g 2 Gn t 2 0 M ]g :

Bebizonythato a Vapnik{Chervonenkis-egyenl}otlenseg altalanostasa, amib}ol kovetkezik, hogy

 !  X n 1  P sup  n g(Zi ) ; Eg(Z ) > "  8s(G^ n n)e;n"=(32M ): g2Gn i=1 

2

 Osszefoglalva az eddigieket, a kovetkez}ot kapjuk:

7.3.1. tetel: Tegyuk fel, hogy jY j  L valamely L < 1-re 1 valoszn}useggel. Legyen Fn

olyan f fuggvenyek csaladja, amelyekre jf (x)j  n minden x-re. Ekkor eleg nagy n-re



P E jmn

(X ) ; Y j2 j D



n ; finf 2Fn

E (f (X ) ; Y )2



>"

2 2 2  8nVG^ n e;n" =128(4n ) :

Ahol a fels}o korlat exponencialisan tart 0-hoz, ha G^ n Vapnik{Chervonenkis dimenzioja veges es nn ! 1. Ebben az esetben tehat a becslesi hiba 1 valoszn}useggel 0-hoz tart. Ahhoz, hogy az approximacios hiba 0-hoz tartson viszont kell az, hogy n ! 1. 4

Legyen peldaul Fn a

Kn X j =1

aj +j (x) : a1  : : :  aKn 2 R

alaku linearis kombinaciok csaladja, ahol a +j -k Rd -b}ol R-be kepez}o korlatos fuggvenyek. Ha ezen a csaladon minimalizaljuk az empirikus negyzetes hibat, akkor konzisztens becsl}ot kapunk, ha Kn ! 1 n ! 1 es nnKn ! 0. Ha meg n;n  ! 0 is teljesul valamilyen  > 0-ra, akkor a becsl}o er}osen univerzalisan konzisztens. A korabban latott hisztogram becsl}o is egy emipirikus hibaminimalizalo becsl}o. Legyen Pn = fAn1  An2  : : :g az Rd egy partcioja, es legyen Fn azon fuggvenyek csaladja, amelyek minden cellan konstansok. Ekkor a legkisebb empirikus negyzetes hibaju becsl}ot ugy kapjuk, ha cellankent minimalizalunk. Egy cellan pedig a minimumot az odaes}o Yi -k atlaga adja, ami nem mas, mint a hisztogrambecsl}o erteke az adott cellan. 4

4

1

8. fejezet

Alakfelismeres 8.1. A Bayes-dontes es kozeltese Az alakfelismeresben Y ket erteket vehet fel, 0-t vagy 1-et (peldaul, hogy egy paciens szenved-e egy adott betegsegben vagy nem). Az Y cmke ertekere szeretnenk kovetkeztetni adott X 2 Rd meggyelesvektor alapjan (ami tartalmazhatja pl. a paciens h}omersekletet, vernyomasat stb.). A dontes vagy osztalyozasi szabaly egy g : Rd ! f0 1g fuggveny, amelynek a min}oseget az L(g) = P (g(X ) 6= Y ) hibavaloszn}useg meri. A cel L(g) minimalizalasa. 8.1.1. den cio: Bayes-dontes:  1 ha P (Y = 1 j X = x) 1  2 g (x) = 0 kulonben. L = L(g ) az un. Bayes-hiba. A Bayes-dontes optimalis. 8.1.1. tetel: Minden g : Rd ! f0 1g dontesfuggvenyre P (g (X ) 6= Y )  P (g(X ) 6= Y ) : Bizonytas : Igazak az alabbi egyszer}u atalaktasok: P (g(X ) 6= Y j X = x) = 1 ; P (Y = g(X ) j X = x) = = 1 ; (P (Y = 1 g(X ) = 1 j X = x) + P (Y = 0 g(X ) = 0 j X = x)) = ;

= 1 ; Ifg(x)=1g P (Y = 1 j X = x) + Ifg(x)=0g P (Y = 0 j X = x) Igy tehat minden x 2 Rd -re P (g(X ) 6= Y j X = x) ; P (g (X ) 6= Y j X = x) = ;

= P (Y = 1 j X = x) Ifg (x)=1g ; Ifg(x)=1g + ;

+P (Y = 0 j X = x) Ifg (x)=0g ; Ifg(x)=0g = ;

= (2P (Y = 1 j X = x) ; 1) Ifg (x)=1g ; Ifg(x)=1g 0 g dencioja alapjan. Mindket oldalt  szerint integralva kapjuk a tetel alltasat. 107

108

8. FEJEZET Alakfelismeres

A P (Y = 1 j X = x) es P (Y = 0 j X = x) valoszn}usegek az un. a posteriori valoszn}usegek. Vegyuk eszre, hogy

P (Y = 1 j X = x) = E (Y j X = x) = m(x): Tehat a Bayes-dontes a kovetkez}okeppen rhato

g (x) =

 1

ha m(x) 21 0 kulonben.

A Bayes-donteshez ismernunk kellene a regressziofuggvenyt, ami tipikusan ismeretlen, ezert most is a Dn = f(X1  Y1 ) : : :  (Xn  Yn )g fuggetlen, azonos eloszlasu mintakat hasznalhatjuk. Olyan gn (x) = gn ((X1  Y1 ) : : :  (Xn  Yn ) x) osztalyozasi szabalyt szeretnenk talalni, amelynek az L(gn) = P (gn(X ) 6= Y j (X1  Y1 ) : : :  (Xn  Yn)) hibavaloszn}usege kozel van L -hoz.

8.1.2. den cio: A gn osztalyozasi szabaly gyengen univerzalisan konzisztens, ha (X Y )

minden eloszlasara

EL(gn) = P(gn (X ) 6= Y ) ! L

ha n ! 1, es er}osen univerzalisan konzisztens, ha

lim L(gn ) = L

n!1

1 valoszn}useggel. Termeszetes gondolat, hogy a mintak segtsegevel becsuljuk az m regressziofuggvenyt az mn regressziobecsl}ovel, es vegyuk a Bayes-dontes mintajara az un. "plug-in" dontesfuggvenyt.  1 ha m (x) 1 n 2 (*) g (x) = n

0 kulonben.

A kovetkez}o tetel azt alltja, hogy ha az mn kozel van a valodi m regressziofuggvenyhez, akkor a gn hibavaloszn}usege kozel lesz az optimalis g hibavaloszn}useghez.

8.1.2. tetel: A fent denialt gn dontesfuggvenyre

Z

0  P (gn (X ) 6= Y j Dn ) ; P (g (X ) 6= Y )  2 jmn(x) ; m(x)j (dx)  2

Z

jmn

(x) ; m(x)j2

(dx)



1 2

Bizonytas : Tetsz}oleges x 2 Rd -re

P (gn(X ) 6= Y j Dn X = x) ; P (g (X ) 6= Y j X = x) =

;

= Ifg (x)=1g m(x) + Ifg (x)=0g (1 ; m(x)) ; Ifgn (x)=1g m(x) + Ifgn (x)=0g (1 ; m(x)) = ;

= Ifg (x)=1g m(x) + Ifg (x)=0g (1 ; m(x)) ; Ifg (x)=1g mn (x) + Ifg (x)=0g (1 ; mn(x)) +

8.2

Lokalis to bbsegen alapulo do ntesek

;

109

;

+ Ifg (x)=1g mn(x) + Ifg (x)=0g (1 ; mn(x)) ; Ifgn (x)=1g mn (x) + Ifgn (x)=0g (1 ; mn (x)) + ;

;

+ Ifgn (x)=1g mn(x) + Ifgn (x)=0g (1 ; mn(x)) ; Ifgn (x)=1g m(x) + Ifgn (x)=0g (1 ; m(x))   Ifg (x)=1g (m(x) ; mn (x)) + Ifg (x)=0g (mn (x) ; m(x))+ +Ifgn (x)=1g (mn (x) ; m(x)) + Ifgn (x)=0g (m(x) ; mn (x))   2 jmn (x) ; m(x)j  ahol az utolso el}otti egyenl}otlensegnel azt hasznaltuk, hogy gn dencioja miatt Ifgn(x)=1g mn (x) + Ifgn (x)=0g (1 ; mn(x)) = maxfmn(x) 1 ; mn(x)g amib}ol Ifg (x)=1g mn (x) + Ifg (x)=0g (1 ; mn(x)) ; Ifgn (x)=1g mn(x) + Ifgn (x)=0g  0: Igy 0  P (gn (X ) 6= Y j Dn ) ; P (g (X ) 6= Y ) = =

Z

(P (gn (X ) 6= Y j Dn  X = x) ; P (g (X ) = 6 Y j X = x)) (dx) 

2

Z

jmn(x) ; m(x)j

(dx)  2

Z

jmn

(x) ; m(x)j2



(dx)

1 2

a Cauchy{Schwartz-egyenl}otlenseg miatt. Igy egy L2 -ben konzisztens regressziobecsl}ob}ol automatikusan kaphatunk konzisztens dontesfuggvenyt. De ahhoz, hogy (*) a Bayes-dontest jol kozeltse egyaltalan nem fontos, hogy mn (x) kozel legyen m(x)-hez. Csak az a lenyeges, hogy a dontesi hatar ugyanazon oldalan legyenek, azaz hogy mn(x) 21 legyen, ha m(x) 12 es legyen < 12 , ha m(x) < 21 . Megis gyakran hasznaljak a plug-in donteseket az E jmn(X ) ; Y j2 j Dn L2 -hiba minimalizalasaval kapott regressziobecsl}ovel, mert az L2 -hiba minimalizalasa hatekonyan szamthato becsl}okhoz vezet.

8.2. Lokalis tobbsegen alapulo dontesek A regressziobecsleshez hasonloan itt is denialhatjuk a harom lokalis atlagolason alapulo osztalyozasi szabalyt a hisztogram, a magfuggvenyes es a legkozelebbi szomszed dontest. Legyen Pn = fAn1  An2  : : :g az Rd egy partcioja, es minden x 2 Rd -re jelolje An (x) az x-et tartalmazo cellat. Ekkor a hisztogram szabaly

8 < gn (x) = : 1 0

Pn

Pn

ha IfYi =1g IfXi 2An (x)g IfYi =0g IfXi 2An (x)g i=1 i=1 kulonben. Azaz tobbsegi dontest hoz az An (x)-be es}o mintak cmkei alapjan. Lathato, hogy ha mn(x) a hisztogram regressziobecsl}o, azaz

8X n > Yi IfXi 2An (x)g > > < i=1n  mn(x) = > X IfXi 2An (x)g > > i =1 :0

ha

n X i=1

IfXi 2An (x)g > 0

kulonben,

110

8. FEJEZET Alakfelismeres

akkor a hisztogram szabaly nem mas, mint egy plug-in osztalyozasi szabaly, amelyben az m(x) regressziofuggvenyt az mn(x) becsl}ovel becsuljuk. Tehat a hisztogram szabaly konzisztenciaja a korabbiak miatt kovetkezik a hisztogram regressziobecsl}o konzisztenciajabol.

8.2.1. tetel: Ha minden origo kozep}u S gombre lim

sup

n!1 j : Anj \S 6=

diam(Anj ) = 0

es

lim jfj : Anjn\ S 6= gj = 0 akkor a hisztogram osztalyozasi szabaly er}osen univerzalisan konzisztens. n!1

A magfuggvenyes osztalyozasi szabalyt a

8 < 1 gn (x) = : 0

  Pn Pn ha IfYi =1g K x;hnXi IfYi =0g K x;hnXi i=1 i=1 kulonben.

fuggveny adja meg, ahol a K (x) : Rd ! R egy nemnegatv, integralhato magfuggveny es hn pedig egy n-t}ol fugg}o simto tenyez}o. Ez a szabaly is egy plug-in szabaly, ahol az mn (x) regressziobecsl}o most a magfuggvenyes becsl}o, tehat a konzisztencia itt is a regressziobecsl}o konzisztenciajabol kovetkezik.

8.2.2. tetel: Ha a K (x) magfuggveny regularis, hn ! 0 es nhdn ! 1, akkor a magfugg-

venyes osztalyozasi szabaly er}osen univerzalisan konzisztens.

A kn -legkozelebbi szomsz ; ed szabaly az x-hez legko;zelebbi kn darab X i cmkei alapjan hoz tobbsegi dontest. Legyen X(1n) (x) Y(1n) (x)  : : :  X(nn) (x) Y(nn) (x) az Xi -k x-t}ol vett tavolsaga alapjan rendezett minta. Ekkor

8 < gn (x) = : 1 0

kn P

kn P

ha IfY in (x)=1g IfY in (x)=0g i=1 i=1 kulonben. (

)

(

)

Konnyen lathato, hogy ez is egy plug-in szabaly, ahol most mn (x) a kn -legkozelebbi szomszed regressziobecsl}o, tehat a konzisztencia itt is a regressziobecsl}o konzisztenciajabol kovetkezik.

8.2.3. tetel: Ha az jjX ;xjj valoszn}usegi valtozo abszolut folytonos minden x-re, kn ! 1 es knn ! 0, akkor a kn -legkozelebbi szomszed osztalyozasi szabaly er}osen univerzalisan konzisztens. A s}ur}usegfuggveny-becsleshez es a regressziobecsleshez hasonloan itt sem lehet altalaban semmit mondani a konvergenciasebessegr}ol, a konvergencia tetsz}olegesen lassu lehet.

8.2.4. tetel: Osztalyozasi szabalyok minden fgng sorozatahoz es pozitv szamok minden

monoton, 0-hoz tarto an < 161 sorozatahoz letezik (X Y )-nak olyan eloszlasa, amelyre X egyenletes eloszlasu 0 1]-en, L = 0 es

P (gn(X ) 6= Y ) > an minden n-re.

8.3

111

Empirikus hibaminimalizalas

8.3. Empirikus hibaminimalizalas Hasonloan a regressziobecsleshez, valaszthatunk dontesfuggvenyt az empirikus hibaminimalizalas modszerevel.

8.3.1. den cio: A g szabaly empirikus hibavaloszn}usegen a mintakon elkovetett atlagos

hibat ertjuk, azaz

Ln (g) = n1

n X i=1

Ifg(Xi )6=Yi g

Az empirikus hibavaloszn}useg nyilvan torztatlan becslese a valodi hibavaloszn}usegnek, azaz ELn (g) = L(g). Legyen C a g : Rd ! f0 1g dontesfuggvenyek egy csaladja. A feladat az, hogy valasszunk ki C-b}ol egy olyan dontesfuggvenyt, amelynek hibavaloszn}usege kozel van a C-beli legjobb dontes hibavaloszn}usegehez. A C csalad megallaptasaban sokfele szempont jatszhat szerepet, peldaul az osztalyozando adat eloszlasarol rendelkezesre allo el}ozetes informacio, szamtasi megfontolasok. Valasszuk a C csaladbol azt a dontest, amelynek az empirikus hibavaloszn}usege minimalis, azaz legyen gn = argmin Ln(g) g 2C

Azt varjuk, hogy gn hibavaloszn}usege kozel lesz a csaladbeli optimumhoz, azaz L(gn ) ; inf L(g) becslesi hiba kicsi. g2C

L(gn ) ; L =







L(gn ) ; ginf L(g) + ginf L(g) ; L  2C 2C L(g) ; L az approximacios hiba. El}ofordulhat ahol L(gn ) ; ginf L(g) a becslesi hiba es ginf 2C 2C azonban, hogy a becslesi hiba kicsi, de L(gn ) megis tavol van az L Bayes-hibatol. Tehat lehet, hogy az ginf L(g) ; L approximacios hiba nagy. 2C

A C csalad tehat eleg nagy kell, hogy legyen ahhoz, hogy jo kozeltest adjon az optimalis megoldasra, de nem lehet tul nagy sem, mert akkor az adatok mennyisege nem elegend}o arra, hogy jo dontest valasszunk ki bel}ole. A tovabbiakban a becslesi hibat vizsgaljuk. (Az approximacios hiba a csalad kivalasztasatol fugg csak, es attol nem, hogy a csaladbol hogyan valasztunk dontest.)

8.3.1. lemma:

L(gn ) ; ginf L(g)  2 sup jLn (g) ; L(g)j 2C g 2C

Bizonytas :

L(gn ) ; ginf L(g) = sup (L(gn ) ; Ln(gn) + Ln(gn) ; Ln(g) + Ln(g) ; L(g))  2C g 2C

Az

 sup (L(gn ) ; Ln(gn ) + Ln(g) ; L(g))  2 sup jLn (g) ; L(g)j g2C g2C els}o egyenl}otlenseg gn valasztasabol adodik, Ln (gn )  Ln (g).

112

8. FEJEZET Alakfelismeres Tehat sup jLn(g) ; L(g)j-re kell fels}o korlatot talalnunk. g2C

8.3.1. tetel: Tegyuk fel, hogy C veges sok dontesfuggvenyt tartalmaz, ekkor



!

P sup jLn(g) ; L(g)j > " g2C

Bizonytas :



! X

P sup jLn(g) ; L(g)j > " g2C



g2C

 2jCje;2n"

2

P (jLn(g) ; L(g)j > ")  2  jCje;2n"

2

a Hoe#ding-egyenl}otlenseg miatt, hiszen nLn(g) binomialis eloszlasu valoszn}usegi valtozo n es L(g) parameterekkel. Megjobb fels}o korlatot kaphatunk, ha feltesszuk, hogy a C-beli dontesek kozott van olyan, amelyik hibavaloszn}usege nulla.

8.3.2. tetel: Tegyuk fel, hogy jCj < 1 es min L(g) = 0. Ekkor minden n-re es " > 0-ra g 2C P (L(gn ) > ")  jCje;n"

es

jCj E (L(gn))  1 + log n :

Bizonytas :

P (L(gn ) > ")  P



= E If

max

g2C: Ln (g)=0



L(g)>"g

X

g2C: L(g)>"





max

g2C: Ln (g)=0





L(g) > " =



= E max I I  g2C fLn (g)=0g fL(g)>"g

P (Ln(g) = 0)  jCj(1 ; ")n

mivel annak a valoszn}usege, hogy egy (Xi  Yi ) sem esik az f(x y) : g(x) 6= yg halmazba, kevesebb, mint (1 ; ")n , ha a halmaz valoszn}usege nagyobb, mint ". Innen a tetel els}o alltasa kovetkezik, ha hasznaljuk az 1 ; x  e;x egyenl}otlenseget. A varhato hibavaloszn}useg becsleshez vegyuk eszre, hogy minden u > 0-ra

Z1

E (L(gn)) = P (L(gn ) > t) dt  u+

Z1 u

0

Z1

P (L(gn) > t) dt  u + jCj e;nt dt = u + jCnj e;nu : u

Mivel u tetsz}oleges, valaszthatjuk ugy, hogy minimalizalja a fels}o korlatot. Az optimalis valasztas u = lognjCj , amivel a fels}o korlat jCj u + jCj e;nu = log jCj + jCj  e;n n = log jCj + 1

n

n

n

log

n

8.3

113

Empirikus hibaminimalizalas

Most terjunk vissza az altalanos esethez, azaz felejtsuk el a feltetelezeseinket, hogy jCj < 1 es min L(g) = 0. g 2C Legyen  (X Y ) valoszn}usegi merteke Rd  f0 1g-en, es legyen n a mintainkon alapulo empirikus mertek. Tehat egy A  Rd  f0 1g merhet}o halmazra (A) = P ((X Y ) 2 A) es Pn n (A) = n1 If(Xi Yi )2Ag . Ekkor i=1

L(g) =  (f(x y) : g(x) 6= yg) 

azaz L(g) a -merteke az ffx :

g(x) = 1g  f0gg  ffx : g(x) = 0g  f1gg

halmaznak. Hasonloan gy

Ln(g) = n (f(x y) : g(x) 6= yg) 

  sup jLn (g) ; L(g)j = sup n (A) ; (A) g 2C

ahol A az osszes ffx :

A2A

g(x) = 1g  f0gg  ffx : g(x) = 0g  f1gg  g 2 C

alaku halmaz csaladja. Emlekezzunk vissza, hogy a

  sup n (A) ; (A)

A2A

kifejezesre a Vapnik{Chervonenkis-egyenl}otlenseg ad fels}o korlatot. Most vezessuk be dontesek csaladjainak Vapnik{Chervonenkis-dimenziojat is. 8.3.2. den cio: Legyen C a g : Rd ! f0 1g dontesfuggvenyek egy csaladja, es tartalmazza A az osszes ffx : g(x) = 1g  f0gg  ffx : g(x) = 0g  f1gg  g 2 C alaku halmazt. A C csalad shatter egyutthatoja es VC-dimenzioja egyezzen meg az A halmazcsalad shatter egyutthatojaval es VC-dimenziojaval. S (C n) = s(A n) VC = VA Ekkor tehat a Vapnik{Chervonenkis-egyenl}otlenseg es a 8.3.1. lemma miatt igaz a kovetkez}o:

8.3.3. tetel:



!

P sup jLn(g) ; L(g)j > " es



g2C

P L(gn) ; ginf L(g) > " 2C



ahol gn az empirikus hibat minimalizalo dontes.

2  8S (C n)e;n" =32

2  8S (C n)e;n" =128 

114

8. FEJEZET Alakfelismeres

Ebb}ol a 8.3.2 tetel bizonytasaban latott modon kaphatunk fels}o korlatot a varhato hibavaloszn}usegre r EL(gn) ; ginf L(g)  16 log (8e2Sn(C n))  2C

illetve mivel VC > 2-re S (C n)  nVC

r

EL(gn) ; ginf L(g)  16 VC log2nn + 4 : 2C Ha feltesszuk, hogy ginf L(g) = 0, azaz, hogy a Bayes-dontes benne van C-ben es L = 0, 2C akkor egy gyorsabban 0-hoz tarto fels}o korlatot kapunk.

8.3.4. tetel: A fenti esetben P (L(gn ) > ")  2S (C 2n)2;n"=2 : A dontescsaladok Vapnik{Chervonenkis-dimenziojanak vizsgalatat konnyti meg az alabbi tetel. 8.3.5. tetel: Ha A = fA  f0g  Ac  f1g( A 2 Ag, akkor s(A n) = s(A n) minden n-re es ezert VA = VA . A dontescsaladok shatter egyutthatojanak denciojaban az A halmazok fx : g(x) = 1g alakuak, mg A olyan (x y) parok halmaza, amelyekre g(x) 6= y. A fenti tetel azt jelenti, hogy S (C n) = s(A n), tehat eleg az A tulajdonsagait vizsgalni, ami egyszer}ubb, hiszen Rd reszhalmazainak a csaladja. Ha peldaul x 2 R es C a

 1

ha x  a 0 kulonben alaku dontesek csaladja, akkor az fx : g(x) = 1g halmazok a felegyenesek, tehat ekkor VC = Vffelegyenesekg = 1. Lehet C peldaul a linearis dontesek csaladja, azaz a

g(x) =

g(x) =

 1

ha aT x > b 0 kulonben

alaku dontesfuggvenyeket tartalmazo csalad. Ekkor az fx : g(x) = 1g halmazok pont az Rd -beli fx : aT x > bg felterek, amelyek csaladjarol korabban lattuk, hogy a VC-dimenzioja d + 1.

Ajanlott irodalom 1] H. Cramer: Mathematical methods of Statistics Princeton University Press, Princeton, 1946. 2] E.L. Lehman: Testing Statistical Hipotheses Wiley & Sons, New York, 1959. 3] E.L. Lehman: Theory of Point Estimation Chapman & Hall, New York, 1991. 4] Mogyorodi Jozsef (szerk.): Matematikai statisztika (ELTE jegyzet) Tankonyvkiado, Budapest, 1990. 5] Vincze Istvan: Matematikai statisztika (ELTE jegyzet) Tankonyvkiado, Budapest, 1974.

115