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

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

Обзор

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

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

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

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

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

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

Точное обучение, предложенное Дана Англуин;
Наверное, примерно правильное обучение (PAC обучение), предложенный Лесли Валиант;
Теория ВК, предложено Владимир Вапник и Алексей Червоненкис;
Байесовский вывод;
Теория алгоритмического обучения, из работы Э. Марк Голд;
Машинное обучение онлайн, из работы Ника Литтлстоуна.

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

Смотрите также

использованная литература

^ «ACL - Ассоциация вычислительного обучения».

Обзоры

Angluin, D. 1992. Теория вычислительного обучения: обзор и избранная библиография. В материалах двадцать четвертого ежегодного симпозиума ACM по теории вычислений (май 1992 г.), страницы 351–369. http://portal.acm.org/citation.cfm?id=129712.129746
Д. Хаусслер. Наверное, примерно правильное обучение. В AAAI-90 Proceedings of the Eight National Conference on Artificial Intelligence, Boston, MA, pages 1101–1108. Американская ассоциация искусственного интеллекта, 1990 г. http://citeseer.ist.psu.edu/haussler90probably.html

Размер ВК

В. Вапник и А. Червоненкис. О равномерной сходимости относительных частот событий к их вероятностям. Теория вероятностей и ее приложения, 16 (2): 264–280, 1971.

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

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

Индуктивный вывод

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

Оптимальное обучение нотации 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

Повышение (машинное обучение)

Роберт Э. Шапир. Сила слабой обучаемости. Машинное обучение, 5 (2): 197–227, 1990. http://citeseer.ist.psu.edu/schapire90strength.html

Обучение Оккама

Blumer, A .; Ehrenfeucht, A .; Haussler, D .; Вармут, М.К. бритва Оккама Inf.Proc.Lett. 24. С. 377–380, 1987.
Blumer, A .; Ehrenfeucht, A .; Haussler, D .; Вармут, М.К. Обучаемость и измерение Вапника-Червоненкиса. Журнал ACM, 36 (4): 929–865, 1989.

Наверное, примерно правильное обучение

Л. Валиант. Теория обучаемого. Сообщения ACM, 27 (11): 1134–1142, 1984.

Устойчивость к ошибкам

Майкл Кернс и Мин Ли. Обучение при наличии вредоносных ошибок. 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.
Pitt, L .; Вармут, М. К. (1990). «Сводимость с сохранением прогнозов». Журнал компьютерных и системных наук. 41 (3): 430–467. Дои:10.1016 / 0022-0000 (90) 90028-Дж.

Описание некоторых из этих публикаций дано на важные публикации по машинному обучению.

Теория обучения распределению

внешние ссылки

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

[ACL-1] «ACL - Ассоциация вычислительного обучения».

[1]