Теорија рачунарског учења
У рачунарској науци, теорија рачунарског учења (или само теорија учења) је подобласт вештачке интелигенције посвећена проучавању дизајна и анализе алгоритама машинског учења.[1]
Преглед[уреди | уреди извор]
Теоријски резултати у машинском учењу углавном се баве врстом индуктивног учења које се назива надгледано учење. У надгледаном учењу, алгоритму се дају узорци који су означени на неки користан начин. На пример, узорци могу бити описи печурака, а ознаке могу бити да ли су печурке јестиве или не. Алгоритам узима ове претходно означене узорке и користи их да индукује класификатор. Овај класификатор је функција која додељује ознаке узорцима, укључујући узорке које алгоритам раније није видео. Циљ алгоритма надгледаног учења је да оптимизује неку меру перформанси, као што је минимизовање броја грешака направљених на новим узорцима.
Поред граница перформанси, теорија рачунарског учења проучава временску сложеност и изводљивост учења. У теорији рачунарског учења, прорачун се сматра изводљивим ако се може обавити у полиномском времену. Постоје две врсте резултата временске сложености:
- Позитивни резултати – Показивање да се одређена класа функција може научити у полиномском времену.
- Негативни резултати – Показују да се одређене класе не могу научити у полиномском времену.
Негативни резултати се често ослањају на уобичајене, али још увек недоказане претпоставке, као што су:
- Рачунска сложеност – П ≠ НП (проблем П наспрам НП);
- Криптографске – постоје једносмерне функције.
Постоји неколико различитих приступа теорији рачунарског учења заснованих на различитим претпоставкама о принципима закључивања који се користе за генерализацију из ограничених података. Ово укључује различите дефиниције вероватноће (погледајте вероватноћу фреквенције, Бајесову вероватноћу) и различите претпоставке о генерисању узорака. Различити приступи укључују:
- Тачно учење, које је предложила Дана Енглуин;
- Вероватно приближно тачно учење (ПАЦ учење), које је предложио Лесли Валијант;[2]
- ВЦ теорија, коју су предложили Владимир Вапник и Алексеј Червоненкис;[3]
- Индуктивно закључивање како га је развио Рај Соломоноф;[4][5]
- Алгоритамска теорија учења, из рада Е. Марк Голда;[6]
- Онлајн машинско учење, из рада Ника Литлстоуна.
Док је њен примарни циљ да апстрактно разуме учење, теорија рачунарског учења је довела до развоја практичних алгоритама. На пример, теорија ПАЦ-а је инспирисала приступ појачања, ВЦ теорија је довела до метода потпорних вектора, а Бајесово закључивање је довело до развоја Бајесових мрежа.
Референце[уреди | уреди извор]
- ^ „АЦЛ - Ассоциатион фор Цомпутатионал Леарнинг”.
- ^ Валиант, Леслие (1984). „А Тхеорy оф тхе Леарнабле” (ПДФ). Цоммуницатионс оф тхе АЦМ. 27 (11): 1134—1142. С2ЦИД 12837541. дои:10.1145/1968.1972. Архивирано из оригинала (ПДФ) 2019-05-17. г. Приступљено 2022-11-24.
- ^ Вапник, V.; Цхервоненкис, А. (1971). „Он тхе униформ цонвергенце оф релативе фреqуенциес оф евентс то тхеир пробабилитиес” (ПДФ). Тхеорy оф Пробабилитy анд Итс Апплицатионс. 16 (2): 264—280. дои:10.1137/1116025.
- ^ Соломонофф, Раy (март 1964). „А Формал Тхеорy оф Индуцтиве Инференце Парт 1”. Информатион анд Цонтрол. 7 (1): 1—22. дои:10.1016/С0019-9958(64)90223-2
.
- ^ Соломонофф, Раy (1964). „А Формал Тхеорy оф Индуцтиве Инференце Парт 2”. Информатион анд Цонтрол. 7 (2): 224—254. дои:10.1016/С0019-9958(64)90131-7.
- ^ Голд, Е. Марк (1967). „Лангуаге идентифицатион ин тхе лимит” (ПДФ). Информатион анд Цонтрол. 10 (5): 447—474. дои:10.1016/С0019-9958(67)91165-5 .
Литература[уреди | уреди извор]
- Англуин, D. 1992. Цомпутатионал леарнинг тхеорy: Сурвеy анд селецтед библиограпхy. Ин Процеедингс оф тхе Тwентy-Фоуртх Аннуал АЦМ Сyмпосиум он Тхеорy оф Цомпутинг (Маy 1992), пагес 351–369. http://portal.acm.org/citation.cfm?id=129712.129746
- D. Хаусслер. Пробаблy аппроxимателy цоррецт леарнинг. Ин АААИ-90 Процеедингс оф тхе Еигхт Натионал Цонференце он Артифициал Интеллигенце, Бостон, МА, пагес 1101–1108. Америцан Ассоциатион фор Артифициал Интеллигенце, 1990. http://citeseer.ist.psu.edu/haussler90probably.html
- А. Дхагат анд L. Хеллерстеин, "ПАЦ леарнинг wитх иррелевант аттрибутес", ин 'Процеедингс оф тхе ИЕЕЕ Сyмп. он Фоундатион оф Цомпутер Сциенце', 1994. http://citeseer.ist.psu.edu/dhagat94pac.html
- Одед Голдреицх, Дана Рон. Он универсал леарнинг алгоритхмс. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.2224
- M. Кеарнс анд Леслие Валиант. 1989. Црyптограпхиц лимитатионс он леарнинг боолеан формулае анд фините аутомата. Ин Процеедингс оф тхе 21ст Аннуал АЦМ Сyмпосиум он Тхеорy оф Цомпутинг, пагес 433–444, Неw Yорк. АЦМ. http://citeseer.ist.psu.edu/kearns89cryptographic.html
- Мицхаел Кеарнс анд Минг Ли. Леарнинг ин тхе пресенце оф малициоус еррорс. СИАМ Јоурнал он Цомпутинг, 22(4):807–837, Аугуст 1993. http://citeseer.ist.psu.edu/kearns93learning.html
- Кеарнс, M. (1993). Еффициент ноисе-толерант леарнинг фром статистицал qуериес. Ин Процеедингс оф тхе Тwентy-Фифтх Аннуал АЦМ Сyмпосиум он Тхеорy оф Цомпутинг, пагес 392–401. http://citeseer.ist.psu.edu/kearns93efficient.html
- D.Хаусслер, M.Кеарнс, Н.Литтлестоне анд M. Wармутх, Еqуиваленце оф моделс фор полyномиал леарнабилитy, Проц. 1ст АЦМ Wорксхоп он Цомпутатионал Леарнинг Тхеорy, (1988) 42-55.
- Питт, L.; Wармутх, M. К. (1990). „Предицтион-Пресервинг Редуцибилитy”. Јоурнал оф Цомпутер анд Сyстем Сциенцес. 41 (3): 430—467. дои:10.1016/0022-0000(90)90028-Ј .