Введение

Теория машинного обучения

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

Опросы

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

Выбор функций

А. Дхагат и Л. Хеллертстейн, "PAC-обучение с нерелевантными атрибутами", в "Proceedings of the IEEE Symp. on Foundations of Computer Science", 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, Нью-Йорк. ACM. 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

Эквивалентность

Д. Хаусслер, М. Кернс, Н. Литтлстоун и М. Вармут, Эквивалентность моделей для полиномиальной обучаемости, Труды 1-й конференции ACM по вычислительному обучению, (1988) 42–55.