Войти
Теория алгоритмического обучения - это математическая основа для анализа задач и алгоритмов машинного обучения. Синонимы включают формальную теорию обучения и алгоритмический индуктивный вывод . Теория алгоритмического обучения отличается от теории статистического обучения тем, что в ней не используются статистические допущения и анализ. Как алгоритмическая, так и статистическая теория обучения связаны с машинным обучением и, таким образом, могут рассматриваться как ветви теории вычислительного обучения.
В отличие от теории статистического обучения и большинства статистических теорий в целом теория алгоритмического обучения не Предположим, что данные являются случайными выборками, то есть точки данных независимы друг от друга. Это делает теорию подходящей для областей, в которых наблюдения (относительно) свободны от шума, но не случайны, таких как изучение языка и автоматическое научное открытие.
Фундаментальная концепция теории алгоритмического обучения предполагает обучение в пределе: как количество точек данных увеличивается, алгоритм обучения должен сходиться к правильной гипотезе по каждой возможной последовательности данных, согласующейся с пространством проблемы. Это не вероятностная версия статистической согласованности, которая также требует сходимости к правильной модели в пределе, но позволяет учащемуся терпеть неудачу в последовательностях данных с вероятностной мерой 0.
Алгоритмический Теория обучения исследует обучающую способность машин Тьюринга. Другие структуры рассматривают гораздо более ограниченный класс алгоритмов обучения, чем машины Тьюринга, например, учащиеся, которые вычисляют гипотезы быстрее, например, за полиномиальное время. Примером такой структуры является приблизительно правильное обучение.
Эта концепция была введена в E. Основополагающая статья Марка Голда "Определение языка в пределе ". Задача идентификации языка состоит в том, чтобы машина, выполняющая одну программу, была способна разработать другую программу, с помощью которой можно проверить любое данное предложение, чтобы определить, является ли оно «грамматическим» или «неграмматическим». Изучаемый язык не обязательно должен быть английским или любым другим естественным языком - фактически определение «грамматического» может быть абсолютно любым, известным тестирующему.
В модели обучения Голда тестировщик дает учащемуся пример предложения на каждом этапе, а учащийся отвечает гипотезой, которая представляет собой предлагаемую программу для определения грамматическая правильность. От тестировщика требуется, чтобы все возможные предложения (грамматические или нет) в конечном итоге появлялись в списке, но особого порядка не требуется. От учащегося требуется, чтобы на каждом этапе гипотеза была верной для всех предложений на данный момент.
Говорят, что конкретный учащийся способен «выучить язык в пределе», если существует определенный количество шагов, после которых его гипотеза больше не меняется. На данный момент он действительно выучил язык, потому что каждое возможное предложение появляется где-то в последовательности входных данных (прошлое или будущее), а гипотеза верна для всех входных данных (прошлых или будущих), поэтому гипотеза верна для каждого предложения. От обучаемого не требуется, чтобы он мог сказать, когда он пришел к правильной гипотезе, все, что требуется, - это чтобы она была верной.
Голд показал, что любой язык, который определяется программой машины Тьюринга, может быть изучен в пределе другой полной по Тьюрингу машиной с использованием перечисления. Это осуществляется учащимся, по очереди тестирующим все возможные программы машины Тьюринга, пока не будет найдена одна, которая на данный момент является правильной - это формирует гипотезу для текущего шага. В конце концов, правильная программа будет достигнута, после чего гипотеза больше никогда не изменится (но учтите, что учащийся не знает, что ее не нужно будет менять).
Голд также показал, что если учащемуся приводятся только положительные примеры (то есть во входных данных появляются только грамматические предложения, а не грамматические предложения), то язык может быть гарантированно изучен в пределе только при наличии являются только конечным числом возможных предложений на языке (это возможно, если, например, известно, что предложения имеют ограниченную длину).
Идентификация языка в предельном количестве очень абстрактная модель. Он не допускает ограничений времени выполнения или памяти компьютера, которые могут иметь место на практике, и метод перечисления может дать сбой, если есть ошибки во вводе. Однако структура очень мощная, потому что при соблюдении этих строгих условий она позволяет изучать любую программу, которая, как известно, является вычислимой. Это связано с тем, что программа машины Тьюринга может быть написана для имитации любой программы на любом стандартном языке программирования. См. тезис Черча-Тьюринга.
Теоретики обучения исследовали другие критерии обучения, например следующие.
Границы изменения мышления тесно связаны с границы ошибок, которые изучаются в теории статистического обучения. Кевин Келли предположил, что минимизация изменений мышления тесно связана с выбором максимально простых гипотез в смысле Бритвы Оккама.
С 1990 года проводится Международная конференция по теории алгоритмического обучения (ALT).), который в первые годы (1990–1997) назывался Workshop. Начиная с 1992 года, труды публиковались в серии LNCS. 31-я конференция состоится в Сан-Диего в феврале 2020 года.
