Обучающийся автомат

Обучающийся автомат — это один из типов алгоритмов машинного обучения , изучаемых с 1970-х годов. Обучающиеся автоматы выбирают свое текущее действие на основе прошлого опыта из окружающей среды. Он попадет в диапазон обучения с подкреплением, если окружающая среда является стохастической и используется процесс принятия решений Маркова (MDP).

Исследования в области обучающихся автоматов можно проследить до работ Михаила Львовича Цетлина в начале 1960-х годов в Советском Союзе. Вместе с некоторыми коллегами он опубликовал сборник статей о том, как использовать матрицы для описания функций автоматов. Кроме того, Цетлин работал над разумным и коллективным поведением автоматов и над играми автоматов . Обучающиеся автоматы также изучались исследователями в Соединенных Штатах в 1960-х годах. Однако термин обучающийся автомат не использовался, пока Нарендра и Тхатхачар не ввели его в обзорной статье в 1974 году.

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

В области обучения с подкреплением обучающиеся автоматы характеризуются как итераторы политики . В отличие от других обучающихся с подкреплением итераторы политики напрямую манипулируют политикой π. Другим примером итераторов политики являются эволюционные алгоритмы .

Формально Нарендра и Татхачар определяют стохастический автомат как состоящий из:

• набор X возможных входов,
• множество Φ = { Φ ₁ , ..., Φ _s } возможных внутренних состояний,
• набор α = { α ₁ , ..., α _r } возможных выходов или действий, где r ≤ s ,
• начальный вектор вероятности состояния p(0) = ≪ p ₁ (0), ..., p _s (0) ≫,
• вычислимая функция A , которая после каждого временного шага t генерирует p ( t +1) из p ( t ), текущего входа и текущего состояния, и
• функция G : Φ → α, которая генерирует выходной сигнал на каждом временном шаге.

В своей статье они исследуют только стохастические автоматы с r = s и G , являющимися биективными , что позволяет им путать действия и состояния. Состояния такого автомата соответствуют состояниям «дискретно-параметрического марковского процесса ». ^[1] На каждом временном шаге t = 0,1,2,3,... автомат считывает входные данные из своей среды, обновляет p ( t ) до p ( t +1) с помощью A , случайным образом выбирает последующее состояние в соответствии с вероятностями p ( t +1) и выводит соответствующее действие. Среда автомата, в свою очередь, считывает действие и отправляет следующие входные данные автомату. Часто используется набор входных данных X = { 0,1 }, где 0 и 1 соответствуют нештрафному и штрафному ответу среды соответственно; в этом случае автомат должен научиться минимизировать количество штрафных ответов, а обратная связь автомата и среды называется «P-моделью». В более общем смысле, «Q-модель» допускает произвольный конечный набор входных данных X , а «S-модель» использует интервал [0,1] действительных чисел в качестве X. ^[2]

Визуализированная демонстрационная версия ^{[3] [4]} / Художественное произведение одного обучающегося автомата была разработана исследовательской группой μSystems (microSystems) в Университете Ньюкасла.

Обучающиеся автоматы с конечным набором действий (FALA) — это класс обучающихся автоматов, для которых число возможных действий конечно или, выражаясь более математическими терминами, для которых размер набора действий конечен. ^[5]

• Обучение с подкреплением
• Теория игр
• Теория автоматов

• Филип Аранзулла и Джон Меллор (Домашняя страница):
  • Меллор Дж. и Аранзулла П. (2000): «Использование среды реагирования S-модели с обучающимися схемами маршрутизации на основе автоматов для сетей IP», Труды Восьмого семинара IFIP по моделированию и оценке производительности сетей ATM и IP, стр. 56/1-56/12, Илкли, Великобритания.
  • Аранзулла П. и Меллор Дж. (1997): «Сравнение двух алгоритмов маршрутизации, требующих сокращенного объема сигнализации при применении в сетях ATM», Труды Четырнадцатого британского симпозиума по телетрафику по проектированию производительности в информационных системах, стр. 20/1-20/4, UMIST, Манчестер, Великобритания.
• Narendra K.; Thathachar MAL (июль 1974 г.). «Обучающиеся автоматы – обзор» (PDF) . IEEE Transactions on Systems, Man, and Cybernetics . SMC-4 (4): 323–334. CiteSeerX  10.1.1.295.2280 . doi :10.1109/tsmc.1974.5408453.
• Цетлин М. Л. Теория автоматики и моделирование биологических систем. Academic Press; 1973. ^{[ постоянная мертвая ссылка ]}