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

В информатике посвященный теория вычислительного обучения (или просто теория обучения ) — это подраздел искусственного интеллекта, изучению проектирования и анализа алгоритмов машинного обучения . ^{[ 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 ]