Сложеност узорка
Сложеност узорка алгоритма машинског учења представља број узорака за обуку који су му потребни да би се успешно научила циљна функција.
Тачније, сложеност узорка је број узорака за обуку које треба да доставимо алгоритму, тако да се функција коју алгоритам враћа задржи у оквиру произвољно мале грешке најбоље могуће функције, са вероватноћом произвољно близу 1.
Постоје две варијанте сложености узорка:
- Слаба варијанта поправља одређену инпут-оутпут дистрибуцију;
- Јака варијанта узима сложеност узорка у најгорем случају над свим улазно-излазним дистрибуцијама.
Теорема „нема бесплатног ручка”, о којој се говори у наставку, доказује да је, генерално, сложеност јаког узорка бесконачна, односно да не постоји алгоритам који може научити глобално оптималну циљну функцију користећи коначан број узорака за обуку.[1][2]
Међутим, ако нас занима само одређена класа циљних функција (нпр. само линеарне функције), онда је сложеност узорка коначна и линеарно зависи од ВЦ димензије на класи циљних функција.[3]
Ефикасност у роботици[уреди | уреди извор]
Висока сложеност узорка значи да је потребно много прорачуна за покретање претраге Монте Карло стабла.[4] То је еквивалентно претрази грубе силе без модела у простору стања. Насупрот томе, алгоритам високе ефикасности има ниску сложеност узорка.[5] Могуће технике за смањење сложености узорка су метричко учење[6] и учење засновано на моделу.[7]
Референце[уреди | уреди извор]
- ^ Wолперт, D. Х.; Мацреадy, W. Г. (1997). „Но Фрее Лунцх Тхеоремс фор Оптимизатион”. ИЕЕЕ Трансацтионс он Еволутионарy Цомпутатион. 1: 67—82. ЦитеСеерX 10.1.1.138.6606
. С2ЦИД 5553697. дои:10.1109/4235.585893.
- ^ Wолперт, Давид (1996), "Тхе Лацк оф А Приори Дистинцтионс бетwеен Леарнинг Алгоритхмс", Неурал Цомпутатион, пп. 1341–1390. Архивирано 2016-12-20 на сајту Wayback Machine
- ^ Вапник, Владимир (1998), Статистицал Леарнинг Тхеорy, Неw Yорк: Wилеy.
- ^ Кауфманн, Емилие; Коолен, Wоутер M (2017). Монте-царло трее сеарцх бy бест арм идентифицатион. Адванцес ин Неурал Информатион Процессинг Сyстемс. стр. 4897—4906.
- ^ Фиделман, Пеггy; Стоне, Петер (2006). Тхе цхин пинцх: А цасе студy ин скилл леарнинг он а леггед робот. Робот Соццер Wорлд Цуп. Спрингер. стр. 59—71.
- ^ Верма, Накул; Брансон, Кристин (2015). Сампле цомплеxитy оф леарнинг махаланобис дистанце метрицс. Адванцес ин неурал информатион процессинг сyстемс. стр. 2584—2592.
- ^ Курутацх, Тханард; Цлавера, Игнаси а; Дуан, Yан; Тамар, Авив; Аббеел, Пиетер (2018). „Модел-енсембле труст-регион полицy оптимизатион”. арXив:1802.10592 [цс.ЛГ].
