Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Отличительные характеристики [ править ]

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

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

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

Обучение в пределе [ править ]

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

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

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

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

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

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

Другие критерии идентификации [ править ]

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

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

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

Ежегодная конференция [ править ]

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

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

  • Формальная эпистемология
  • Параметр исключения выборки

Ссылки [ править ]

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

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

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