Számítástudományi és Információelméleti Tanszék

Alakfelismerés

Tantárgyi adatlap

Elôadó:

Antos András

Heti óraszám:

4

Kreditpont:

5

Vizsga:

írásbeli
1999.január 29. 14h, V2.102.
1999.február 5. 12h, V2.102.

Elôfeltétel:

nincs, de sokat segíthet a valószínûségszámítás, alapjainak ismerete.

Idõpont, hely:

Kedd 12:15-13:45, I.B.134
Péntek 12:15-13:45, I.B.134

Jegyzet:

• L. Devroye, L. Györfi, G. Lugosi: A Probabilistic Theory of Pattern Recognition, Springer-Verlag, New York, 1996. Hibajegyzék.

• A. Antos, ``Lower bounds for the rate of convergence of nonparametric pattern recognition,'' (112k) Theoretical Computer Science, 284 (1):3-24, 2002. Abstract

• A. Antos, L. Devroye and L. Györfi, ``Lower bounds for Bayes error estimation,'' (60k) IEEE Transactions on Pattern Analysis and Machine Intelligence, 21:643-645, 1999. Abstract

• A. Antos and G. Lugosi, ``Strong minimax lower bounds for learning,'' (88k) Machine Learning, 30:31-56, 1998. Abstract

• A. Antos, Függvényosztályok tulajdonságai és szerepe az alakfelismerésben. Diplomaterv, Technical University of Budapest, Budapest, Hungary, June 1995.

Házifeladatok

Tematika

Valószínûségszámítás alapok.

Bayes-hiba: a Bayes-probléma, helyettesítõ döntések, osztályozás és regresszióbecslés.

Konzisztencia: (erõs) univerzális konzisztencia, osztályozás és regresszióbecslés, osztályozás könnyebb, mint a regressziófüggvény becslés.

Particiós szabályok: univ. konz., (reguláris) hisztogram szabály, erõs univ. konz., legközelebbi szomszéd szabály.

Lokális átlag becslések: univ. konz. (Stone-tétel), hisztogram szabály, k-legközelebbi szomszéd szabály növekvõ k-val, távolság egyenlõségek feloldása, erõs univ. konz., fix k-val az aszimptotikus hibavalószínüség, egyenlõtlenségek a hibavalószínüségre, kis L*, L*=0, magfüggvényes szabály, reguláris magfüggvény, erõs univ. konz., furcsa magfüggvények.

Lassú konvergenciasebesség: véges tanító sorozat, lassú sebesség, gazdag osztályokra.

Hibabecslés: hibaszámoló becslés, Hoeffding (Bennett, Bernstein)-egyenlõtlenség, osztályozó választás, a Bayes-hiba becslése, véges tanító sorozat, lassú sebesség.

Vapnik-Chervonenkis elmélet: empirikus hiba minimalizálás, nagy számok egyenletes törvénye, véges osztályok, túl gazdag osztályok, Glivenko-Cantelli tétel, relativgyakoriságok egyenletes eltérése valószínüségektõl (V-C tétel), VC dimenzió, VC osztályok, osztályozó választás, konv. sebesség, mintabonyolultság, nulla-hiba eset, konv. sebesség, mintabonyolultság.

Vapnik-Chervonenkis elmélet kombinatorikai aspektusai: shatter együtthatók és VC dimenzió, Assouad dimenzió, néhány osztály shatter együtthatói, konvex halmazok és monoton rétegek.

Alsó korlátok az empirikus osztályozó hibájára: nulla-hiba eset, minimax alsó korlátok, individuális alsó korlátok, végtelen VC dimenziójú és végtelen halmazt shatter-elõ osztályok, általános eset, minimax alsó korlátok.

Back to the Home Page

Updated: Jul 24. 2010