Эквивалентность конечного автомата "нейронной сети"

В книге Марвина Минского «Вычисления и автоматы» наткнулся на одну интересную теорему: «всякая конечная машина эквивалентна некоторой нейронной сети и может быть «смоделирована» ею». Суть заключается в том, что для любой конечной машины можно составить эквивалентную ей нейронную сеть, но это не самое замечательное. Интерес представляет универсальный метод построения нейронной сети по автомату!

Рассмотрим данную задачу на примере. Для начала определимся с терминологией. Раз за основу взята книжка Минского, то воспользуемся определениями из неё. Конечные автоматы это такие машины, которые переходят чётко разграниченными шагами из одного состояния в другое, причём оба этих набора принадлежат к некоторому конечному набору. Конечный автомат можно рассматривать как «чёрный ящик», который характеризуется определённой величиной (обобщённое состояние), Это обобщённое состояние изменяется в соответствии с предыдущими состояниями и входным сигналом (т.е. средой). С другой стороны данную машину можно представить как структуру, состоящую из отдельных элементов. Зная логику работы и связи между элементами, мы можем сказать, как эта система будет работать.

Для конечных автоматов принято рассматривать две функции. Первая – это F-функция, определяющая выход в момент времени t+1 от совокупности предыдущих состояний машины и входного сигнала на момент t.

R(t+1) = F(H(t), S(t)),

где R – выходной сигнал, H – предыстория, S – входной сигнал.

Вторая функция – это G-функция, определяющая состояние машины в зависимости от предыстории и входного сигнала на момент t.

Q(t+1) = G(H(t), Q(t)),

где Q – состояние конечного автомата, H – предыстория.

Проще всего при описании конечного автомата использовать подход «чёрного ящика». В качестве примера можно рассмотреть конечный автомат, реализующий задержку на два такта.

В изображении цифра у начала стрелки является входным сигналом, Q1…Q4 – состояния автомата, цифра в середине стрелки выход.

Под «нейронными» сетями мы будем понимать сети, составленные из «нейронов» Мак-Каллока и Питтса.

Пример «нейрона»:

Линии слева – входные сигналы, линия справа – выход. Цифра внутри круга – это порог срабатывания, если количество входных сигналов больше либо равно порогу, то на выходе появится сигнал (1), в противном случае «нейрон» будет находиться в покое (выход = 0). Вход с кружком (см. на рисунке нижний входной сигнал) называется тормозящим. Если такой вход активен, то «нейрон» переходит в состояние покоя.

Из «нейронов» можно составлять различные автоматы, например шифраторы/дешифраторы, память, сумматоры и т.п. Такие элементы («нейроны») можно рассматривать как строительный материал для автоматов.

Теперь вернёмся к нашей теореме обозначенной в самом начале. «Нейронная сеть» является одним из способов реализации конечного автомата. И имея методологию построения таких сетей, мы сможем довольно быстро решить любую задачу, представленную в виде автомата.

Рассмотрим вышеприведенный конечный автомат, который осуществляет задержку. У него есть входной сигнал, который может быть 0 или 1, четыре внутренних состояния и выходной сигнал (так же 0 или 1). Входной сигнал можно разбить на два взаимоисключающих сигнала: а) наличие/отсутствие 0 на входе, б) наличие/отсутствие 1 на входе. Тоже справедливо и для выхода.

Опишем более формально нашу машину.

Входы.

Количество входов: m=2.

S1 – наличие 0 на входе (1 – подан 0, 0 – не подан 0);

S2 – наличие 1 на входе (1 – подана 1, 0 – не подана 1).

Выходы.

Количество выходов: n=2.

R1 – наличие 0 на выходе;

R2 – наличие 1 на выходе.

Состояния.

Количество состояний: p=4.

Для реализации эквивалентной «нейронной сети» нам понадобится m*p «нейронов» с порогом 2.

Столбцы «нейронов» с порогом 2 представляют собой реализацию состояний системы Q1…Q4. «Нейроны» с порогом 1 – это элементы функции формирования выходного сигнала. Возле каждого столбца «нейронов» имеется пучок связей. За соединение этих связей отвечает функция G. Для формирования входного сигнала будем использовать дешифратор.

В момент запуска автомата необходимо подать сигнал Старт на дешифраторе и сигнал на Вход дешифратора. Так же в момент времени t, в области функции G должна быть активирована какая-либо ветвь.

В принципе это всё, что бы мне хотелось сказать. Как оказывается, в старых книжках хранится много всяких интересных вещей, а самое главное, они очень подробно и понятно описаны.

Спасибо!