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]