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

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален.
Найти источники: «Теория вычислительного обучения» - новости · газеты · книги · ученый · JSTOR ( ноябрь 2018 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

Машинное обучение и интеллектуальный анализ данных
Часть серии по

Проблемы Классификация Кластеризация Регресс Обнаружение аномалий AutoML Правила ассоциации Обучение с подкреплением Структурированный прогноз Функциональная инженерия Особенности обучения Онлайн обучение Полу-контролируемое обучение Обучение без учителя Учимся ранжировать Введение в грамматику
Обучение с учителем ( классификация • регрессия ) Деревья решений Ансамбли Упаковка Повышение Случайный лес k -NN Линейная регрессия Наивный байесовский Искусственные нейронные сети Логистическая регрессия Перцептрон Вектор релевантности (RVM) Машина опорных векторов (SVM)
Кластеризация БЕРЕЗА ИЗЛЕЧИВАТЬ Иерархический k -средство Ожидание – максимизация (EM) DBSCAN ОПТИКА Средний сдвиг
Снижение размерности Факторный анализ CCA ICA LDA NMF PCA PGD t-SNE
Структурированный прогноз Графические модели Сеть Байеса Условное случайное поле Скрытый Марков
Обнаружение аномалий k -NN Фактор местного выброса
Искусственная нейронная сеть Автоэнкодер Когнитивные вычисления Глубокое обучение DeepDream Многослойный перцептрон RNN LSTM ГРУ ESN Ограниченная машина Больцмана GAN SOM Сверточная нейронная сеть U-Net Трансформатор Пиковая нейронная сеть Мемтранзистор Электрохимическая RAM (ECRAM)
Обучение с подкреплением Q-обучение SARSA Временная разница (TD)
Теория Компромисс смещения и дисперсии Теория вычислительного обучения Минимизация эмпирического риска Обучение Оккама PAC обучение Статистическое обучение Теория ВК
Площадки для машинного обучения NeurIPS ICML ML JMLR ArXiv: cs.LG
Статьи по Теме Глоссарий искусственного интеллекта Список наборов данных для исследований в области машинного обучения Краткое описание машинного обучения
v т е

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

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

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

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

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

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

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

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

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

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

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

Введение в грамматику
Теория информации
Стабильность (теория обучения)
Толерантность к ошибкам (обучение 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

Размер VC [ править ]

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

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

А. Дагат и Л. Хеллерстайн, «Обучение 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 [ править ]

Одед Гольдрайх , Дана Рон . Об универсальных алгоритмах обучения . 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

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

D.Haussler, M.Kearns, N.Littlestone и M. Warmuth , Эквивалентность моделей для полиномиальной обучаемости, Proc. 1-й семинар ACM по вычислительной теории обучения, (1988) 42-55.
Pitt, L .; Вармут, МК (1990). «Сводимость с сохранением прогнозов». Журнал компьютерных и системных наук . 41 (3): 430–467. DOI : 10.1016 / 0022-0000 (90) 90028-J .

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

Теория обучения распределению [ править ]

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

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

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