Pravděpodobnostní modely učení

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra matematiky

Anotace:

Úvod do teorie PAC modelu pravděpodobnostního učení, VC-dimenze konečných množin, Sauerovo, Coverovo a Radonovo lemma, VC-dimnenze složeného zobrazení, využití VC-dimenze pro odhad vzorů nutných pro PAC učicí algoritmus, analýza vlastností učení založeného na delta pravidle, rozšíření PAC modelu a PAO učení, pravděpodobnostní hledání Fourierových koeficientů Booleovských funkcí.

Požadavky:

Osnova přednášek:

1. Úvod PAC modelu učení

2. Koncepty a třídy konceptů

3. PAC učení pro případ konečných množin

4. Vapnik-Červoněnkova dimenze (Sauerovo, Coverovo a Radonovo lemma)

5. VC-dimenze konečných množin

6. VC-dimenze sjednocení a průniku

7. VC-dimenze of lineárních konceptů

8. Aplikace Coverova lemmatu

9. Vapnik-Červoněnkova dimenze složeného zobrazení

10. Vzorová složitost a VC-dimenze

11. Odhad minimálního počtu vzorů pro PAC učení

12. Učící algoritmy odvozené od delta pravidla

13. Dolní odhad maximálního počtu kroků delta pravidla

14. Polynomiální učení a dimenze vzorů

15. Přibližné řešení problému pokrytí množin

16. Polynomiální učení a popisná složitost vzorů

17. Pravděpodobnostní učící algoritmy

18. Pravděpodobnostní aproximace Fourierova rozvoje

19. Pravděpodobnostní hledání koeficientů Fourierova rozvoje Booleovských funkcí

20. PAO model učení

Osnova cvičení:

Cíle studia:

Znalosti:

Seznámit studenty s teoretickými a matematickými základy teorie pravděpodobnostního PAC modelu učení a jeho

variant.

Schopnosti:

Orientovat se v přednášené problematice a umět ji použít v dalších disciplinách.

Studijní materiály:

Povinná literatura:

[1] F. Hakl, M. Holeňa. Úvod do teorie neuronových sítí. Ediční středisko ČVUT, Praha, 1997.

Doporučená literatura:

[2] Vwani Roychowdhury, Kai-Yeung Siu, Alon Orlitsky. Theoretical Advances in Neural Computation and Learning. Kluwer, Academic Publishers, 1994.

[3] Martin Anthony and Norman Biggs. Computational Learning Theory. Press Syndicate of the University of Cambridge, 1992.

[4] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the Vapnik-Chervonenkis Dimension. Journal of the Association for Computing Machinery, 36:929-965, oct 1989.

Poznámka:

Další informace:

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• Matematické inženýrství (volitelný předmět)
• Aplikace softwarového inženýrství (volitelný předmět)
• Matematická informatika (volitelný předmět)