Теория вычислительного обучения

В информатике посвященный теория вычислительного обучения (или просто теория обучения ) — это подраздел искусственного интеллекта, изучению проектирования и анализа алгоритмов машинного обучения . ^[1]

Обзор [ править ]

Теоретические результаты в машинном обучении в основном касаются типа индуктивного обучения, называемого обучением с учителем . При обучении с учителем алгоритму предоставляются образцы, которые помечены каким-либо полезным способом. Например, образцы могут представлять собой описания грибов, а на этикетках может быть указано, съедобны ли грибы или нет. Алгоритм берет эти ранее помеченные образцы и использует их для создания классификатора. Этот классификатор представляет собой функцию, которая присваивает метки образцам, включая образцы, которые алгоритм ранее не видел. Цель алгоритма контролируемого обучения — оптимизировать некоторые показатели производительности, например свести к минимуму количество ошибок, допущенных на новых образцах.

Помимо границ производительности, теория вычислительного обучения изучает временную сложность и осуществимость обучения. ^{[ нужна цитата ]}В В теории вычислительного обучения вычисление считается возможным, если оно может быть выполнено за полиномиальное время . ^{[ нужна цитата ]}Есть два вида времени результаты сложности:

Положительные результаты – показ того, что определенный класс функций можно изучить за полиномиальное время.
Отрицательные результаты — демонстрация того, что определенные классы невозможно выучить за полиномиальное время.

Отрицательные результаты часто основаны на общепринятых, но еще не доказанных предположениях. ^{[ нужна цитата ]} такой как:

Вычислительная сложность – P ≠ NP (проблема P против NP) ;
Криптографические — существуют односторонние функции .

Существует несколько различных подходов к теории вычислительного обучения, основанных на различных предположениях о принципах вывода , используемых для обобщения ограниченных данных. Это включает в себя разные определения вероятности (см. частотную вероятность , байесовскую вероятность ) и разные предположения о создании выборок. ^{[ нужна цитата ]} Различные подходы включают в себя:

Точное обучение, предложенное Даной Англуин. ^{[ нужна цитата ]};
Вероятно, приблизительно правильное обучение (PAC-обучение), предложенное Лесли Валиант ; ^[2]
теория венчурного капитала , предложенная Владимиром Вапником и Алексеем Червоненкисом ; ^[3]
Индуктивный вывод , разработанный Рэем Соломоновым ; ^[4]^[5]
Алгоритмическая теория обучения , из работ Э. Марка Голда ; ^[6]
Машинное обучение онлайн , из работы Ника Литтлстоуна. ^{[ нужна цитата ]}.

Хотя ее основной целью является абстрактное понимание обучения, теория вычислительного обучения привела к разработке практических алгоритмов. Например, теория PAC вдохновила на повышение , теория VC привела к поддержке векторных машин , а байесовский вывод привел к созданию сетей убеждений .

См. также [ править ]

Ссылки [ править ]

^ «ACL — Ассоциация компьютерного обучения» .
^ Валиант, Лесли (1984). «Теория обучаемого» (PDF) . Коммуникации АКМ . 27 (11): 1134–1142. дои : 10.1145/1968.1972 . S2CID 12837541 . Архивировано из оригинала (PDF) 17 мая 2019 г. Проверено 24 ноября 2022 г.
^ Вапник, В.; Червоненкис, А. (1971). «О равномерной сходимости относительных частот событий к их вероятностям» (PDF) . Теория вероятностей и ее приложения . 16 (2): 264–280. дои : 10.1137/1116025 .
^ Соломонов, Рэй (март 1964 г.). «Формальная теория индуктивного вывода. Часть 1» . Информация и контроль . 7 (1): 1–22. дои : 10.1016/S0019-9958(64)90223-2 .
^ Соломонов, Рэй (1964). «Формальная теория индуктивного вывода. Часть 2». Информация и контроль . 7 (2): 224–254. дои : 10.1016/S0019-9958(64)90131-7 .
^ Голд, Э. Марк (1967). «Языковая идентификация в лимите» (PDF) . Информация и контроль . 10 (5): 447–474. дои : 10.1016/S0019-9958(67)91165-5 .

Дальнейшее чтение [ править ]

Опросы [ править ]

Англуин, Д. 1992. Теория компьютерного обучения: обзор и избранная библиография. В материалах двадцать четвертого ежегодного симпозиума ACM по теории вычислений (май 1992 г.), страницы 351–369. http://portal.acm.org/citation.cfm?id=129712.129746
Д. Хаусслер. Наверное примерно правильное обучение. В материалах AAAI-90 Восьмой национальной конференции по искусственному интеллекту, Бостон, Массачусетс, страницы 1101–1108. Американская ассоциация искусственного интеллекта, 1990. http://citeseer.ist.psu.edu/haussler90probally.html.

Выбор функции [ править ]

А. Дагат и Л. Хеллерстайн, «Обучение PAC с нерелевантными атрибутами», в «Proceedings of the IEEE Symp. об основании компьютерных наук», 1994. http://citeseer.ist.psu.edu/dhagat94pac.html.

Оптимальное изучение нотации O [ править ]

Одед Голдрейх , Дана Рон . Об универсальных алгоритмах обучения . http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.2224

Отрицательные результаты

М. Кернс и Лесли Валиант . 1989. Криптографические ограничения на изучение булевых формул и конечных автоматов. В материалах 21-го ежегодного симпозиума ACM по теории вычислений, страницы 433–444, Нью-Йорк. АКМ. http://citeseer.ist.psu.edu/kearns89cryptographic.html

Толерантность к ошибкам [ править ]

Майкл Кернс и Мин Ли. Обучение при наличии вредоносных ошибок. SIAM Journal on Computing, 22(4):807–837, август 1993 г. http://citeseer.ist.psu.edu/kearns93learning.html
Кернс, М. (1993). Эффективное устойчивое к шуму обучение на основе статистических запросов. В материалах двадцать пятого ежегодного симпозиума ACM по теории вычислений, страницы 392–401. http://citeseer.ist.psu.edu/kearns93efficient.html

Эквивалентность [ править ]

Д. Хаусслер, М. Кернс, Н. Литтлстоун и М. Вармут , Эквивалентность моделей полиномиальной обучаемости, Proc. 1-й семинар ACM по теории вычислительного обучения, (1988) 42-55.
Питт, Л.; Вармут, МК (1990). «Сводимость, сохраняющая прогноз» . Журнал компьютерных и системных наук . 41 (3): 430–467. дои : 10.1016/0022-0000(90)90028-J .

Внешние ссылки [ править ]

Основы байесовского вывода

[ACL-1] «ACL — Ассоциация компьютерного обучения» .

[2] Валиант, Лесли (1984). «Теория обучаемого» (PDF) . Коммуникации АКМ . 27 (11): 1134–1142. дои : 10.1145/1968.1972 . S2CID 12837541 . Архивировано из оригинала (PDF) 17 мая 2019 г. Проверено 24 ноября 2022 г.

[3] Вапник, В.; Червоненкис, А. (1971). «О равномерной сходимости относительных частот событий к их вероятностям» (PDF) . Теория вероятностей и ее приложения . 16 (2): 264–280. дои : 10.1137/1116025 .

[4] Соломонов, Рэй (март 1964 г.). «Формальная теория индуктивного вывода. Часть 1» . Информация и контроль . 7 (1): 1–22. дои : 10.1016/S0019-9958(64)90223-2 .

[5] Соломонов, Рэй (1964). «Формальная теория индуктивного вывода. Часть 2». Информация и контроль . 7 (2): 224–254. дои : 10.1016/S0019-9958(64)90131-7 .

[6] Голд, Э. Марк (1967). «Языковая идентификация в лимите» (PDF) . Информация и контроль . 10 (5): 447–474. дои : 10.1016/S0019-9958(67)91165-5 .

[1]

[2]

[3]

[4]

[5]

[6]