Složenost uzorka
Složenost uzorka algoritma mašinskog učenja predstavlja broj uzoraka za obuku koji su mu potrebni da bi se uspešno naučila ciljna funkcija.
Tačnije, složenost uzorka je broj uzoraka za obuku koje treba da dostavimo algoritmu, tako da se funkcija koju algoritam vraća zadrži u okviru proizvoljno male greške najbolje moguće funkcije, sa verovatnoćom proizvoljno blizu 1.
Postoje dve varijante složenosti uzorka:
- Slaba varijanta popravlja određenu input-output distribuciju;
- Jaka varijanta uzima složenost uzorka u najgorem slučaju nad svim ulazno-izlaznim distribucijama.
Teorema „nema besplatnog ručka”, o kojoj se govori u nastavku, dokazuje da je, generalno, složenost jakog uzorka beskonačna, odnosno da ne postoji algoritam koji može naučiti globalno optimalnu ciljnu funkciju koristeći konačan broj uzoraka za obuku.[1][2]
Međutim, ako nas zanima samo određena klasa ciljnih funkcija (npr. samo linearne funkcije), onda je složenost uzorka konačna i linearno zavisi od VC dimenzije na klasi ciljnih funkcija.[3]
Efikasnost u robotici уреди
Visoka složenost uzorka znači da je potrebno mnogo proračuna za pokretanje pretrage Monte Karlo stabla.[4] To je ekvivalentno pretrazi grube sile bez modela u prostoru stanja. Nasuprot tome, algoritam visoke efikasnosti ima nisku složenost uzorka.[5] Moguće tehnike za smanjenje složenosti uzorka su metričko učenje[6] i učenje zasnovano na modelu.[7]
Reference уреди
- ^ Wolpert, D. H.; Macready, W. G. (1997). „No Free Lunch Theorems for Optimization”. IEEE Transactions on Evolutionary Computation. 1: 67—82. CiteSeerX 10.1.1.138.6606
. S2CID 5553697. doi:10.1109/4235.585893.
- ^ Wolpert, David (1996), "The Lack of A Priori Distinctions between Learning Algorithms", Neural Computation, pp. 1341–1390. Архивирано 2016-12-20 на сајту Wayback Machine
- ^ Vapnik, Vladimir (1998), Statistical Learning Theory, New York: Wiley.
- ^ Kaufmann, Emilie; Koolen, Wouter M (2017). Monte-carlo tree search by best arm identification. Advances in Neural Information Processing Systems. стр. 4897—4906.
- ^ Fidelman, Peggy; Stone, Peter (2006). The chin pinch: A case study in skill learning on a legged robot. Robot Soccer World Cup. Springer. стр. 59—71.
- ^ Verma, Nakul; Branson, Kristin (2015). Sample complexity of learning mahalanobis distance metrics. Advances in neural information processing systems. стр. 2584—2592.
- ^ Kurutach, Thanard; Clavera, Ignasi a; Duan, Yan; Tamar, Aviv; Abbeel, Pieter (2018). „Model-ensemble trust-region policy optimization”. arXiv:1802.10592 [cs.LG].
