Лекция 3. Конечные автоматы и нейронные сети.

Пусть нейронная сеть Nсостоит изgнейронов, имеетmвходных иrвыходных линий.

Будем говорить, что задан входсетиN, если из­вестно, какие входные линии возбуждены, а какие— не возбуждены. Так как значения «возбужден» и «не возбужден»mвходным линиям можно приписать 2^m различными способами, то в сетиNимеется 2^mвхо­дов. Аналогично в ней имеется 2^rвыходов.

Будем говорить, что задано состояниесетиNв мо­ментt,если известно, какие нейроны в этот момент возбуждены, а какие не возбуждены. Таким образом,Nимеет 2^gсостояний.

Обозначим через Qмножество состояний, черезX —множество входов и черезY— множество выхо­дов сетиN.Возбуждение любого нейрона сетиNв мо­ментt+1определяется тем, какие входы этого нейрона возбуждены в моментtи, следовательно, определяется состоянием и входом всей сетиNв моментt.Но это означает, что вход и состояние сети в моментtодно­значно определяют выход и состояние сети в моментt+1. Следовательно, конечный автомат теперь можно определить как простое обобщение нейронной сети. В дальнейшем конечный автомат будем рассматри­вать как «черный ящик» с конечным числом входов, конечным числом «внутренних состояний» (это могут быть либо состояния нейронной сети, либо позиции зубцов часового механизма и т. п.) и конечным числом выходов. Предполагаем, что вход и состояние в моментtопределяют выход и состояние в моментt+1.Более точно эти требования можно сформулировать следующим образом.

Определение 3.1.Конечным автоматомназывается пятерка

А=(Х, Y, Q, ,  ),

где Х – конечное множество (множество входов),Y – конечное множество (множество выходов),Q – конечное множество (множество внутренних состоя­ний),:QXQ – функция перехода),: QXY – функция выхода. Предполагается, чтоАработает в дискретной шкале времени так, что если в моментtон находился в состоянииqи воспринимал входа, то в моментt+1он перейдет в состояние(q,a), а(q,а)будет его выходом.

Легко видеть, что любая нейронная сеть является конечным автоматом. Аналогично, что любой конечный автомат можно заме­нить подходящей нейронной сетью.

Действительно, пусть конечный автомат Аимееттвозможных входовиrвозможных выходов.Сопоставим этому автомату нейронную сетьN с т входными линиями (заметим, чтоN,таким образом, имеет 2^mвходов)иrвыходными линиями.Входx_jавтоматаАсопоставим такому входу сетиN,в котором возбуждена толькоh_j-я входная линия. Аналогично определим выход, сетиN.Искомая сетьN состоит изтп+rнейронов:тпнейронов сопостав­ляются возможным парам «вход—состояние» автома­таА,а остальныеrнейронов — выходамА.Нейрон, соответствующийk-му состоянию иj-му входу авто­матаA, обозначим(k, j), а нейрон, который соответ­ствуетk-му выходу, обозначим(k).Выходная линияp_kнашей сетиNподсоединена к нейрону(k).

Нейроны соединим таким образом, чтобы нейрон (k, j)возбуждался в моментt+1тогда и только то­гда, когда автоматАв моментtимеет входх_jи на­ходится вk-м состоянии; нейрон(k)возбуждается в моментt+1тогда и только тогда, когда автоматАв моментtдает выходy_k.

Пусть ,т. е. это множество таких пар«состояние — вход»,которые переводят автоматАвсостояние k.Тогда нейрон(k,s)должен быть возбужден в моментt+1тогда и только тогда, когда

т. е. тогда и только тогда, когда автомат Ав моментt находится вk-м состоянии и имеетs-й вход.

Пусть

,

т. е. это множество таких пар «состояние – выход», при которых автоматАимеетвыход k.

Тогда нейрон (k)возбужден в моментt+1тогда и только тогда, когда.

Легко убедиться, что каждый нейрон сети Nдействительно может быть реализован при условии под­ходящего выбора весов и порога. Таким образом, наша сетьNудовлетворяет следующей теореме.

Теорема 3.1.Пусть А=(Х, Y, Q, ,  ) - произ­вольный конечный автомат, где

, , .

Тогда существуют нейронная сеть Nи подмножества ее входов, выходов, состоянийтакие, что если автоматA, первоначально находящийся в состоянии q_j, под дей­ствием входавыдает, то сетьN, первоначально находящаяся в состоянииq_j,noд действием входоввыдает.Это означает, что любой автомат с заданным поведением «вход—вы­ход» можно заменить подходящей нейронной сетью с тем же поведением.

Исходя из того, что любой ко­нечный автомат можно заменить нейронной сетью, теперь нетрудно убедиться в том, что нейронные сети способны хранить информацию и производить вычисления. Для этого достаточно показать, что любая цифровая вычислительная машина может быть представлена в виде надлежащего соединения конеч­ных автоматов, поскольку нам известно, что возмож­но заменить эти автоматы нейрон се­тями. Цифровая вычислительная машина является, конечно, менее «интеллектуальным» объектом, нежели мозг. Здесь же мы только хотим показать, что наша модель мозга, как бы груба она ни была, от­носится к категории вычислительных машин.

Любая цифровая вычислительная машина обычно состоит из четырех устройств: устройства ввода и вы­вода, устройства памяти, устройства управления и арифметического устройства. Устройство ввода и вы­вода служит для чтения команд и исходных данных с входной ленты и их пересылки в устройство памяти и, наоборот, для вывода из устройства памяти резуль­татов вычислений на выходную ленту. Устройство па­мяти состоит из конечного числа «ячеек», каждая из которых имеет свой адрес и вмещает одно «слово», где «слово» может быть как числом (исходные дан­ные, промежуточный или окончательный результат), так и командой. Устройство управления в каждый такт работы машины выбирает из устройства памяти по одной команде и выполняет ее. Если эта команда является операцией ввода или вывода или операцией обращения к устройству памяти, то устройство управления приводит в действие либо устройство ввода и вывода, либо устройство памяти; если команда яв­ляется арифметической операцией, то устройство управления приводит в действие арифметическое устройство; если условным переходом, то оно осуществляет необходимую проверку и принимает решение о выполнении следующей команды.

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