Введение

Рамочная структура для анализа алгоритмов машинного обучения

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

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

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

Обучение в пределах возможностей

Концепция была введена в основополагающей работе Э. Марка Голда «Идентификация языка в пределе». Целью идентификации языка является способность машины, выполняющей одну программу, разработать другую программу, с помощью которой любое заданное предложение можно проверить на предмет того, является ли оно «грамматичным» или «неграмматичным». Изучаемый язык не обязательно должен быть английским или каким-либо другим естественным языком — фактически, определение «грамматичного» может быть абсолютно любым, известным тестировщику. В модели обучения Голда тестировщик предоставляет учащемуся пример предложения на каждом шаге, а учащийся отвечает гипотезой, представляющей собой предлагаемую программу для определения грамматической корректности. Требуется, чтобы тестировщик в конечном итоге предоставил все возможные предложения (грамматичные или неграмматичные) в списке, хотя какого-либо конкретного порядка не требуется. Требуется, чтобы учащийся на каждом шаге гипотеза была верна для всех предложений, полученных до этого момента. Говорят, что конкретный учащийся способен «изучить язык в пределе», если существует определенное число шагов, после которого его гипотеза больше не изменяется. На этом этапе он действительно изучил язык, поскольку каждое возможное предложение появляется где-то в последовательности входных данных (в прошлом или будущем), и гипотеза верна для всех входных данных (в прошлом или будущем), следовательно, гипотеза верна для каждого предложения. Учащемуся не требуется определять, когда он достиг правильной гипотезы, достаточно, чтобы она была истинной. Голд показал, что любой язык, определяемый программой машины Тьюринга, может быть изучен в пределе другой машиной Тьюринга, полной по Тьюрингу, с использованием перечисления. Это достигается путем последовательного тестирования учащимся всех возможных программ машины Тьюринга, пока не будет найдена программа, которая на данный момент является правильной — она и формирует гипотезу для текущего шага. В конечном итоге будет достигнута правильная программа, после чего гипотеза больше не изменится (но следует отметить, что учащийся не знает, что она больше не должна меняться). Голд также показал, что если учащемуся предоставляются только положительные примеры (то есть во входных данных появляются только грамматичные предложения, а не неграмматичные), то язык может быть гарантированно изучен в пределе только в том случае, если в языке существует конечное число возможных предложений (это возможно, например, если известно, что предложения имеют ограниченную длину). Идентификация языка в пределе — это высоко абстрактная модель. Она не учитывает ограничения времени выполнения или объема компьютерной памяти, которые могут возникать на практике, и метод перечисления может оказаться неэффективным при наличии ошибок во входных данных. Однако эта структура очень мощная, поскольку при соблюдении этих строгих условий она позволяет изучать любую программу, которая, как известно, вычислима. Это связано с тем, что программу машины Тьюринга можно написать для имитации любой программы на любом стандартном языке программирования. См. тезис Черча — Тьюринга.

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

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

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

С 1990 года проводится Международная конференция по теории алгоритмического обучения (ALT), в первые годы (1990–1997) носившая название Workshop. В период с 1992 по 2016 год материалы конференций публиковались в серии LNCS. Начиная с 2017 года, публикации осуществляются в Proceedings of Machine Learning Research. 34-я конференция пройдет в Сингапуре в феврале 2023 года. Темы конференции охватывают все области теоретического машинного обучения, включая статистическую и вычислительную теорию обучения, онлайн-обучение, активное обучение, обучение с подкреплением и глубокое обучение.