Теория алгоритмического обучения - Algorithmic learning theory

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

Отличительные характеристики

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

Фундаментальная концепция теории алгоритмического обучения - обучение в пределе: по мере увеличения количества точек данных алгоритм обучения должен сходиться к правильной гипотезе на каждый возможная последовательность данных, соответствующая проблемному пространству. Это не вероятностная версия статистическая согласованность, который также требует сходимости к правильной модели в пределе, но позволяет учащемуся терпеть неудачу на последовательностях данных с вероятностной мерой 0.

Теория алгоритмического обучения исследует обучающую способность Машины Тьюринга. Другие фреймворки рассматривают гораздо более ограниченный класс алгоритмов обучения, чем машины Тьюринга, например, учащихся, которые быстрее вычисляют гипотезы, например, в полиномиальное время. Примером такой структуры является наверное примерно правильное обучение.

Обучение на пределе

Концепция была представлена ​​в Э. Марк Голд основополагающая статья "Определение языка в лимите ".[4] Цель идентификация языка для машины, выполняющей одну программу, чтобы иметь возможность разработать другую программу, с помощью которой можно проверить любое данное предложение, чтобы определить, является ли оно «грамматическим» или «неграмматическим». Изучаемый язык не обязательно английский или любой другой естественный язык - по сути, определение «грамматическое» может быть абсолютно любым, известным тестировщику.

В модели обучения Голда тестировщик дает учащемуся пример предложения на каждом этапе, и учащийся отвечает гипотеза, который предлагается программа для определения грамматической правильности. От тестировщика требуется, чтобы каждое возможное предложение (грамматическое или нет) в конечном итоге появлялось в списке, но особого порядка не требуется. От учащегося требуется, чтобы на каждом этапе гипотеза была верной для всех предложений.[нужна цитата ]

Говорят, что конкретный учащийся способен «выучить язык на пределе возможностей», если есть определенное количество шагов, после которых его гипотеза больше не меняется.[нужна цитата ] На данный момент он действительно выучил язык, потому что каждое возможное предложение появляется где-то в последовательности входных данных (прошлое или будущее), а гипотеза верна для всех входных данных (прошлых или будущих), поэтому гипотеза верна для каждого предложения. От обучаемого не требуется, чтобы он мог сказать, когда он пришел к правильной гипотезе, все, что требуется, - это чтобы она была верной.

Голд показал, что любой язык, определяемый Машина Тьюринга программа может быть изучена в пределе другим Полный по Тьюрингу машина с использованием перечисление.[требуется разъяснение ] Это осуществляется учащимся, по очереди тестирующим все возможные программы машины Тьюринга, пока не будет найдена одна, которая на данный момент является правильной - это формирует гипотезу для текущего шага. В конце концов, правильная программа будет достигнута, после чего гипотеза больше никогда не изменится (но учтите, что учащийся не знает, что ее не нужно будет менять).

Голд также показал, что если учащемуся приводятся только положительные примеры (т. Е. Во входных данных появляются только грамматические предложения, а не грамматические предложения), то можно гарантировать, что язык будет изучен в пределе только в том случае, если есть только конечный количество возможных предложений на языке (это возможно, если, например, известно, что предложения имеют ограниченную длину).[требуется разъяснение ]

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

Другие критерии идентификации

Теоретики обучения исследовали другие критерии обучения,[5] такие как следующие.

  • Эффективность: минимизация количества точек данных, необходимых для сходимости к правильной гипотезе.
  • Изменения разума: минимизация количества изменений гипотез, которые происходят перед сходимостью.[6]

Границы изменения разума тесно связаны с границы ошибки которые изучаются в теория статистического обучения.[7] Кевин Келли предположил, что минимизация изменений в сознании тесно связана с выбором максимально простых гипотез в смысле Бритва Оккама.[8]

Ежегодная конференция

С 1990 года существует Международная конференция по теории алгоритмического обучения (ALT), называется цех в первые годы (1990–1997).[9] Начиная с 1992 г., труды публиковались в LNCS серии.[10] 31-я конференция состоится в г. Сан Диего в феврале 2020 года.[11]

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

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

  1. ^ Джайн, С. и др. (1999): Системы, которые учатся 2-е изд. Кембридж, Массачусетс: MIT Press.
  2. ^ Langley, P .; Саймон, H .; Брэдшоу, Г. и Зитков, Дж. (1987), Научное открытие: вычислительные исследования творческих процессов, MIT Press, Кембридж
  3. ^ Шульте, О. (2009), Одновременное открытие законов сохранения и скрытых частиц с разложением матрицы Смита, в материалах Двадцать первой международной совместной конференции по искусственному интеллекту (IJCAI-09), стр. 1481-1487.
  4. ^ Э. Марк Голд (май 1967 г.). «Определение языка в пределе». Информация и контроль. 10 (5): 447–474. Дои:10.1016 / S0019-9958 (67) 91165-5.
  5. ^ Джайн, С. и др. (1999): Системы, которые учатся2-е изд. Кембридж, Массачусетс: MIT Press.
  6. ^ Луо, В. и Шульте, О. (2005), Изменение мышления Эффективное обучение, Питер Ауэр и Рон Меир, ред., Труды конференции по теории обучения (COLT), стр. 398-412.
  7. ^ Джайн, С. и Шарма, А. (1999), Об обобщенном понятии границ ошибки, Труды конференции по теории обучения (COLT), стр.249-256.
  8. ^ Кевин Т. Келли (2007), Бритва Оккама, эмпирическая сложность и эффективность поиска истины, Теоретическая информатика, 383: 270-289.
  9. ^ Архивы ALT-семинаров и конференций в Университет Хоккайдо
  10. ^ Страница процедуры ALT в Springer
  11. ^ Домашняя страница ALT'20

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