Теория вычислительного обучения
редактировать
Теория машинного обучения
В информатике, теория вычислительного обучения (или просто теория обучения ) является подполе искусственного интеллект посвящен изучению разработки и анализа алгоритмов машинного обучения.
Содержание
- 1 Обзор
- 2 См. также
- 3 Ссылки
- 3.1 Опросы
- 3.2 Размер VC
- 3.3 Выбор характеристик
- 3.4 Индуктивный вывод
- 3.5 Обучение оптимальной O-нотации
- 3.6 Отрицательные результаты
- 3.7 Повышение (м ачинное обучение)
- 3.8 Обучение Оккаму
- 3.9 Вероятно, приблизительно правильное обучение
- 3.10 Устойчивость к ошибкам
- 3.11 Эквивалентность
- 3.12 Теория распределенного обучения
- 4 Внешние ссылки
Обзор
Теоретические результаты в области машинного обучения в основном касаются типа индуктивного обучения, называемого контролируемым обучением. При обучении с учителем алгоритму предоставляются образцы, которые помечены каким-либо полезным способом. Например, образцы могут быть описанием грибов, а на этикетках может быть указано, съедобны ли грибы. Алгоритм берет эти ранее помеченные образцы и использует их для создания классификатора. Этот классификатор представляет собой функцию, которая назначает метки выборкам, включая образцы, которые ранее не просматривались алгоритмом. Цель алгоритма контролируемого обучения - оптимизировать некоторые показатели производительности, например минимизировать количество ошибок, сделанных на новых выборках.
В дополнение к пределам производительности теория вычислительного обучения изучает временную сложность и возможность обучения. В теории вычислительного обучения вычисление считается выполнимым, если оно может быть выполнено за полиномиальное время. Существует два типа результатов временной сложности:
- Положительные результаты - Показывают, что определенный класс функций можно изучить за полиномиальное время.
- Отрицательные результаты - Показывают, что определенные классы не могут быть изучены за полиномиальное время.
Отрицательные результаты часто основываются на общепринятых, но все же недоказанных предположениях, таких как:
Существует несколько различных подходов к теории вычислительного обучения, основанных на различных предположениях о принципах вывода, используемых для обобщения на основе ограниченных данных. Это включает в себя различные определения вероятности (см. частотная вероятность, байесовская вероятность ) и различные предположения о генерации выборок. К различным подходам относятся:
Хотя его основная цель - абстрактное понимание обучения, теория вычислительного обучения привела к разработке практических алгоритмов. Например, теория PAC привела к усилению, теория VC привела к опорным векторным машинам, а байесовский вывод привел к сетям убеждений.
См. Также
Ссылки
Опросы
- Англуин, Д. 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
Размер VC- V. Вапник и А. Червоненкис. О равномерной сходимости относительных частот событий к их вероятностям. Теория вероятностей и ее приложения, 16 (2): 264–280, 1971.
Выбор характеристик
- A. Дхагат и Л. Хеллерштейн, «Обучение PAC с несущественными атрибутами», в 'Proceedings of the IEEE Symp. on Foundation of Computer Science », 1994. http://citeseer.ist.psu.edu/dhagat94pac.html
Индуктивный вывод
- Голд, Э. Марк (1967). «Определение языка в пределе» (PDF). Информация и контроль. 10 (5): 447–474. doi : 10.1016 / S0019-9958 (67) 91165-5.
Обучение оптимальной нотации O
Отрицательные результаты
- М. Кирнс и Лесли Вэлиант. 1989. Криптографические ограничения на обучение булевых формул и конечных автоматов. В материалах 21-го ежегодного симпозиума ACM по теории вычислений, страницы 433–444, Нью-Йорк. ACM. http://citeseer.ist.psu.edu/kearns89cryptographic.html
Boosting (машинное обучение)- Роберт Э. Шапайр. Сила слабой обучаемости. Машинное обучение, 5 (2): 197–227, 1990 http://citeseer.ist.psu.edu/schapire90strength.html
Обучение Оккама- Блумер, А.; Ehrenfeucht, A.; Haussler, D.; Warmuth, M.K. бритва Оккама Inf.Proc.Lett. 24, 377–380, 1987.
- Blumer, A.; Ehrenfeucht, A.; Haussler, D.; Вармут, М. К. Обучаемость и измерение Вапника-Червоненкиса. Journal of the ACM, 36 (4): 929–865, 1989.
Вероятно, приблизительно правильное обучение- L. Доблестный. Теория обучаемого. Сообщения 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
Эквивалентность
- Д.Хаусслер, М.Кернс, Н.Литтлстоун и М. Вармут, Эквивалентность моделей по полиномиальной обучаемости, Proc. 1-й семинар ACM по теории вычислительного обучения, (1988) 42-55.
- Pitt, L.; Вармут, М. К. (1990). «Сводимость с сохранением прогнозов». Журнал компьютерных и системных наук. 41 (3): 430–467. doi : 10.1016 / 0022-0000 (90) 90028-J.
Описание некоторых из этих публикаций дано в важных публикациях по машинному обучению.