§ 1.1. Проблеме оптимальности посвящена обширная литература, перечислить которую в обозримой форме, пожалуй, невозможно. Но для наших целей в этом п нет необходимости. Поэтому мы отметим лишь несколько основных книг. В первую очередь отметим книгу Л. Л. Фельдбаума [1.1], в которой изложены различные формулировки проблемы оптимальности и возможные подходы к ее решению.

В книгах Р. Беллмана [1.1], [1.2] эта проблема рассмотрена па основе разработанного им метода динамического программировании, а в книге Л. С. Понтрягнна, В. Г. Болтянского, Р. В. Гамкрелидзе и Е. Ф. Мищенко [1.1] рассмотрение ведется на основе открытого ими принципа максимума. Читателю, пожелавшему расширить своп представления по различным аспектам проблемы оптимальности, можно рекомендовать познакомиться с книгами В. Г. Болтянского [1.1], особенно просто и наглядно излагающей задачи оптимальности, Л. Г. Бутковского [1.1], посвященной оптимальности системы с распределенными параметрами, Ш. Чанга [1.1], охватывающей также и задачи оптимальности линейных непрерывных и дискретных систем.

Для знакомства с проблемой оптимального управления, вероятно. наиболее подходящей будет интересная во многих отношениях небольшая книга Р. Ли [1.1].

Все упомянутые книги содержат довольно подробную библиографию.

Не следует думать, что проблема оптимальности — простая и ясная проблема. Часто вопрос «Что такое оптимальность?» может вызвать грустные размышления и пессимизм, см., например, работы Л. Заде [1.1] и отчасти Р. Калмана [1.1]. Автор, однако, не может полностью разделить этот пессимизм.

§ 1.2. Мы пользуемся здесь обозначениями, принятыми Ф. Р. Гантмахером [1.1]: все векторы представляют собой прямоугольные столбцовые матрицы, и для них используется обозначение транспонирование вектора, т. е. прямоугольной столбцовой матрицы, приводит к строчной матрице .

Байесовские критерии широко используются в теории связи и радиолокации, а в последнее время и в теории управления, см., например, книги Л. С. Гуткнна [1.1]. К. Хелстрома [1.1], Л. А. Фельдбаума [1.1].

В формуле (1.3) принята простая запись: вместо определяющего элементарный объем пространства , мы пишем просто .

О математическом ожидании характеристической функции см.. например, Б. В. Гнеденко [1.1] или Р. Л. Стратонович [1.1].

§ 1.3. Об эргодичности см., например, небольшую, по очень содержательную книгу П. Халмоша [1.1].

§ 1.4. Роль детерминированных ограничении в наиболее выразительной и ясной форме неоднократно подчеркивалась А. А. Фельдбаумом [1.1] (см. также Р. Ли [1.1], Р. Беллман [1.2].

§ 1.5. Именно такая характеристика априорной и текущей информации принята А. А. Красовским [1.1].

§ 1.6. Приведенное деление процессов на детерминированные и стохастические общепринято (см., например, Р. Беллман [1.2]). Однако здесь мы хотели подчеркнуть общность формулировки и решения проблемы оптимальности для этих процессов и поэтому не так настойчиво останавливались на различии между ними.

§ 1.7. Несколько иную трактовку адаптивного подхода можно найти у Р. Беллмана [1.2]. Принятая здесь трактовка совпадает с изложенной ранее в статье автора [1.1]. Весьма интересная связь между стохастической задачей синтеза линейной системы, оптимальной по дисперсии ошибки, и детерминированной задачей синтеза линейной системы, оптимальной по интегральной квадратической ошибке, указана Р. Калманом [1.2]. Эта связь сформулирована им в виде принципа дуальности.

§ 1.8. Кроме упомянутых выше книг, с методами решения проблемы оптимальности, относящихся к обычному подходу, можно познакомиться по книгам Дж. Лейтмана [1.1] и К. Мерриама [1.1].

К главе II

§ 2.2. Мы пользуемся обычной векторной записью необходимых условий экстремума (см., например, Р. Ли [1.1]).

§ 2.3. Регулярный итеративный метод восходит еще к Огюсту Конш. Но мы преодолеем соблазн заняться изложением истории этих методов н предпочтем отослать читателя к превосходной статье Б. Т. Поляка [2.1], а также к книгам по вычислительной математике, например, Б. П. Демидовича и И. А. Марона [2.1], И. С. Березина и Н. П. Жидкова [2.1]. В этих книгах дано традиционное изложение итеративных методов применительно к линейным и нелинейным алгебраическим уравнениям. Специально итеративным методам посвящена книга Дж. Трауба [2.1], а применение этих методов для решения краевых задач изложено в книге В. Е. Шимайского [2.1). См. также обзор В. Ф. Демьянова [2.1].

§ 2.4. Термин дигратор для дискретного интегратора предложен И. JI. Медведевым.

§ 2.5. Это обобщение в наиболее отчетливой форме было описано С. Бингулацем [2.1].

§ 2.6. Единой классификации алгоритмов или, как их еще называют, рекуррентных схем, не существует. Применительно к системам линейных алгебраических уравнений весьма полная классификация приведена в книге Д. К. Фаддеева и В. II. Фаддеевой [2.1]. Читатель, вероятно, заметит, что мы немного отклонились от этой классификации. О конкретных алгоритмах см., например, книгу Б. П. Демидовича и И. Л. Марона [2.1]. Релаксационным алгоритмам посвящена интересная работа И. М. Глазмана [2.1] (см. также И. М. Глазман, 10. Ф. Сенчук [2.1]). Нам кажутся весьма перспективными методы сопряженного градиента (см., например, С. Миттер, JI. Лесдон, Л. Уорен [2.1]). Обзор итеративных методов решения функциональных уравнений содержится в статье JI. В. Канторовича [2.1].

§ 2.7. Идея поисковых алгоритмов, по-видимому, принадлежит Р. Германскому [2.1]. В математической литературе поисковым алгоритмам подобного типа почему-то уделялось мало внимания. О синхронном детектировании см. книги П. И. Дегтяренко [2.1] и А. А. Красовского (1.1). В последней книге широко применяются методы определения градиента с помощью синхронного детектора или коррелятора (при использовании шумов).

§ 2.8. См. книгу Р. Ли [1.1]. Иные способы определения множителей Лагранжа можно найти в работе Б. Т. Поляка [2.1].

§ 2.9. Учету ограничений типа неравенств посвящена большая литература по математическому и, в частности, нелинейному программированию. Среди них укажем па книги К. Эрроу, Л. Гурвица, X. Удзавы [2.1] и Г. Кгонци, В. Крелле [2.1] и статью Е. С. Левитина н Б. Т. Поляка [2.1]. В этих работах читатель может найти точные формулировки теоремы Куна — Таккера и условия регулярности Слейтера. Очень интересный подход решения подобных задач был развит А. Я. Дубовицкнм и А. А. Милютиным [2.1]. Схемы, реализующие алгоритмы с учетом ограничений, описаны Д. Деннисом [2.1].

§ 2.10. Наиболее полное изложение методов возможных направлений дано в книге Т. Зонтендейка — автора этих методов [2.1].

§ 2.11. Мы несколько перефразировали пример, приведенный Р. Ли [1.1].

§ 2.12. Здесь использованы известные соотношения из теории конечных разностей, см., например, книгу автора [2.1]. Многошаговым алгоритмам посвящено сравнительно небольшое число работ, среди которых укажем па статью Б. Т. Поляка [2.1].

§ 2.13. О непрерывных алгоритмах см. статьи М. К. Гавурниа [2.1], [2.2], а также статью С. П. Альбера и Я. П. Альбера [2.1], посвященные математическим вопросам. См. также статьи М. В. Рыбашова [2.1], [2.2] по применению аналоговых вычислительных машин для решения конечных уравнении.

Идея тяжелого шарика принадлежит, по-видимому, И. Кумада [2.1], см. также работу Б. Т. Поляка [2.1].

§ 2.14. Методы случайного поиска, о которых в свое время упоминал У. Эшбн [2.1], получили большое развитие в многочисленных работах JI. А. Растригина и были подытожены в его книге [2.1]. Некоторые применения методов случайного поиска для оценки линейного решающего правила изложены А. Иольфом [2.1]. По этим вопросам см. также статьи И. Матыаша [2.1], И. Майсона и А. Рабина [2.1].

§ 2.15. Изложение применения метода Ляпунова для дискретных систем можно найти, например, в книге 11. 13. Бромберга [2.1] и статье Р. Калмана и Дж. Бертрама [2.1]. Различные формулировки принципа сжатых отображений можно найти, например, в книгах Л. А. Люстерпика и А. П. Соболева [2.1], М. А. Красносельского [2.1].

§ 2.16. Об абсолютной устойчивости см. уже ставшую классической книгу А. И. Лурье [2.1]. К сожалению, условиям неизбежной сходимости в литературе уделялось мало внимания. Что же касается условий сходимости итеративных методов вообще, то им посвящено даже чрезмерно большое число работ. Отметим книги Дж. Трауба [2.1] и А. М. Островского [2.1], а также статью М. II. Яковлева [2.1]. Б этих работах читатель найдет подробную библиографию по сходимости итеративных методов. См. также книгу С. Г. Михлина [2.1]

§ 2.17. Этот способ ускорения сходимости принадлежит Вегстейиу [2.1]. Он описан также в книге Р. Ледли [2.1].

§ 2.18. Когда автор работал над этим вопросом, он был обрадован, найдя ссылку на статью П. С. Бондареико [2.1] с весьма многообещающим названием. Но после знакомства с ней надежда узнать, как же хороню определить понятие «наилучший алгоритм», так и не оправдалась.

§ 2.19. О релаксационных методах см. уже упоминавшуюся статью И. М. Глазмана [2.1], а также статью 10. И. Любича [2.1] и Ч. Б. Томпкинса [2.1].

§ 2.21. Обзор нелокальных методов оптимизации и путей решения многоэкстремальпых задач можно найти в статье Д. Б. Юдина [2.1]. Интересный метод решения многоэкстремальной задачи, так называемый метод «оврагов», предложен И. М. Гельфандом и М. JI. Цетлнным (2.1).

К главе III

§ 3.2. К настоящему времени в определениях понятий обучения и адаптации нет недостатка (см., например. Р. Буш. Ф. Мостеллер [3.1]. Г. Паск [3.1]. (3.2), Л. Заде [3.1]. Дж. Гибсои [3.1], Дж. Скланский [3.1], [3.2]. [3.1], О. Якобе [3.1], А. А. Фельдбаум т. д.). Автору показалось значительно проще выработать еще одно определение, чем пытаться объединить и применить определения, столь щедро разбросанные в литературе.

§ 3.4. Основная идея метода стохастической аппроксимации возникла, по-видимому, довольно давно, но в ясной и четкой форме она была сформулирована Г. Роббнпсом и С. Монро [3.1] в 1951 г. Они указали итеративную процедуру, позволяющую определить по реализации корень уравнения регрессии. Гута процедура представляла собой стохастический вариант итеративной процедуры Р. Фон-Мизсса и Г. Поллячек-Гейрингер [3.1]. Работа Г. Роббинса С. Монро вызвала большой поток работ, развивающих эту идею.

Дж. Вольфовиц [3.1] ослабил условия сходимости. Г. Каллианпур [3.1] и Дж. Блум [3.1] независимо показали, что даже при менее стеснительных условиях, чем у Дж. Вольфовица [3.1], процедура Роббинса-Монро сходится не только по вероятности, по также с вероятностью единица. Процедура Роббинса и Монро была обобщена А. Дворецким (3.1). Более простые доказательства этой обобщенной процедуры были указаны Дж. Вольфовицем [3.1] и К. Дерманш, Дж. Саксом (3.1). Некоторая модификация этой процедуры, состоящая в выборе , предложена А. Фридманом [3.1]. Итеративная процедура бьпа обобщена на многомерный случай Дж. Блумом [3.1]. Простое и ясное доказательство сходимости многомерной процедуры дано Е. Г. Гладышевым (3.1). Для линейной функции регрессии удобной оказывается модификация процедуры, указанная В. Дупачем [3.2].

Асимптотические свойства итеративной процедуры выяснены Л. Шметтерером [3.1], К. Чаигом [3.1] и Дж. Саксом [3.1], Е. Г Гладышевым [3.1], а в частном случае линейной функции регрессии Т. Ходжесом и Е. Лемаиом [3.1]. Т. П. Красулнна [3.1], (10.72) установила связь между итеративной процедурой Дж Блума [3.1] и обобщенной итеративной процедурой Дворецкого [3.1] и привела сжатый обзор методов стохастической аппроксимации.

Упоминание о процедуре Роббииса Монро имеется в книге Б. Л. Ван дер Вардена (3.1). а систематическое изложение можно найти в книге Г. Везернла [3.1].

Отметим ряд работ по разнообразным применениям процедуры Роббииса-Монро, которые, однако, находятся вне области наших интересов. Это работы Т. Гутмана. Р. Гутмана [3.1] по биометрике, В. Кохрана и М. Дэвиса [3.11] по биологии.

Сравнение различных методов оптимизации при наличии помех приводилось Л. С. Гуриным [3.2], [3.3], С. М. Мовшовичем [3.1]. См. также работу Р. 3. Хасьминского [3.2]. Подробные обзоры основных результатов метода стохастической аппроксимации принадлежат К. Дерману [3.1], Л. Шметтереру [3.3] и Н. В. Логинову [3.1].

§ 3.6. В 1952 г. идея стохастической аппроксимации была распространена Е. Кифером и Дж. Вольфовицем [3.1] на случай определения экстремума функции регрессии. Это был первый вероятностный поисковый алгоритм, представляющий собой стохастический вариант поисковой итеративной процедуры, предложенной Р. Германским [2.1].

Сходимость поисковой процедуры Кифера — Вольфовица, с вероятностью единица была доказана Дж. Блумом [3.1] и Д. Буркхолдером [3.1]. Известны различные обобщения на многомерный случай. Им посвящены работы Дж. Блума [3.2] и К. Грея [3.1].

Асимптотические свойства процедуры Кифера — Вольфовица были изучены К. Дерманом [3.1], В. Дупачем [3.1], Дж. Саксом

[3.1] . Упомянутые выше обзоры К. Дермана [3.2], Л. Шметтерера [3.5] и И. В. Логинова [3.1] большое внимание уделяют и процедуре Кифера — Вольфовица.

А. Дворецкий [3.1] показал, что процедуры Роббинса — Монро и Кифера — Вольфовица вытекают как частные случаи из предложенной им общей процедуры.

Обобщение процедуры Дворецкого для случая конечномерного евклидового пространства дано К. Дерманом и Дж. Саксом [3.11, а для случая гильбертового пространства — Л. Шметтерером [3.1]. В последнее время эти все результаты были обобщены Дж. Вентнером [3.1].

§ 3.8. Вопросы сходимости алгоритмов адаптации при учете ограничений вида неравенств к настоящему времени не получили полного решения.

§ 3.9. На возможность такого обобщения нам было указано Я. И. Хургиным.

§ 3.11. Непрерывные алгоритмы подробно изучались А. Шпачеком и его учениками. Результаты работ в этом направлении изложены в трудах М. Дримла и Т. Недомы [3.1], М. Дримла и О. Ханша

[3.2] , О. Ханша и А. Шпачека [3.1] — для непоисковых алгоритмов и Д. Сакрисона [3.1] — для поисковых алгоритмов.

§ 3.12. Точные формулировки различных видов сходимости хорошо изложены в книге М. Лоэва [3.1]; см. также книгу Д. Миддлтона [1.1].

§ 3.13. Здесь приведены условия сходимости, которые можно получить на основании результатов работ по стохастической аппроксимации, перечисленных выше.

Но было бы очень интересно получить условия сходимости как частный случай условий устойчивости стохастических систем. Последним задачам посвящены работы И. Я. Каца, Н. Н. Красовского [3.1], Р. 3. Хасьминского [3.1], Г. Кашнера [3.1].

Неравенство (3.37) было получено Дж. Номером [3.1]. В его работе приводится явное выражение функции .

§ 3.15. Описанные методы ускорения сходимости были предложены Г. Кестеном [3.1] и В. Фабианом [3.1]. См. также Д. Уайлд [3.1].

§ 3.16. Мера качества алгоритмов типа (3.49) использовалась в работах А. Дворецкого [3.1], 3. Николича, К. Фу [10.1] для определения наилучших алгоритмов оценки среднего значения.

§ 3.17. Наилучшее значение для скалярного одномерного случая было получено из иных соображений P. Л. Стратоновичем [3.1].

§ 3.18. Соотношения (3.70)-(3.72) в частном случае при были получены К. Кирвайтисом и К. Фу [5.1].

§ 3.19. Изложенные здесь соображения являются развитием одной идеи А. Дворецкого [3.1]. См. также работу Г. Блока [3.1]. Эти соображения были применены А. А. Первозванским [3.1] для выбора оптимального шага в простейших импульсных экстремальных системах.

§ 3.20. Подробное изложение рекуррентной формы метода наименьших квадратов приведено в работе А. Альберта, Р. Ситтлера [3.1].

Рекуррентная формула вычисления по предшествующим значениям может быть получена на основе очень популярной теперь рекуррентной формулы обращения матриц, предложенной Пепроузом (R. Penrose), — см., например, книгу P. Ли [1.1].

Нетрудно установить связь между всеми этими результатами и теорией калмановских фильтров. См. книгу Р. Ли [1.1].

С весьма интересным методом Качмажа можно познакомиться по статье Томпкинса в книге Э. Беккенбаха [3.1] либо по работе самого С. Качмажа [3.1].

§ 3.21. Формула (3.81) при фиксированном n была установлена Р. Л. Стратоновичем [3.1].

Доказательство сходимости рекуррентных процедур при повторении конечного числа данных дано Б. М. Литваковым [3.1].

§ 3.22. Мы используем некоторые соотношения, изложенные в книге Г. Крамера [3.1], и идеи, развитые в работах Д. Сакрисона [3.1], [3.2]. В этих работах читатель найдет подробное изложение рекуррентных алгоритмов и их применения для решения некоторых радиолокационных задач.

§ 3.23. По вопросам, связанным с наилучшими алгоритмами, см. статьи P. Л. Стратоновича [3.1] и автора [3.1], которые выражают различные точки зрения.

К главе IV

§ 4.1. То, что опознавание является первой ступенью обработки информации, неоднократно, со свойственным ему блеском подчеркивал А. А. Харкевич [4.1], [4.3].

На изучение дискуссий типа «человек или машина» можно потратить довольно много времени. Автор не без удовольствия знакомился с этими дискуссиями по книгам М. Таубе [4.1] и А. Е. Кобринского [4.1] и рекомендует их читателям. Специально проблеме опознавания посвящены книги Г. Себастнана [4.1] и Н. Нильсона [4.1].

§ 4.2. Гипотеза компактности была выдвинута Э. М. Браверманом [4.1]. Она долгое время уточнялась и, по-видимому, нашла свое выражение в гипотезе представимости, о которой говорится в § 4.5.

§ 4.3. Подобные функционалы были введены В. А. Якубовичем [4.2] для квадратичной функции потерь, а в общем случае — автором [5.1], [1.1].

§ 4.4. Аппроксимация произвольной функции с помощью системы линейно независимых и, в частности, ортонормированных функций широко используется для решения разнообразных технических задач.

Изложенный здесь подход основан па результатах заметки автора [4.1] и статьи И. П. Девятерикова, А. И. Пропоя и автора [4.1].

Алгоритмы типа (4.12) для некоторых частных случаев ( — линейная и релейная функции) были выписаны М. А. Айзерманом, Э. М. Браверманом, Л. И. Розоноэром [4.3] на основе развитого ими метода потенциальных функций. Далее из этих алгоритмов они получили соответствующие алгоритмы типа (4.9). По терминологии М. А. Айзермана, Э. М. Бравермана, Л. И. Розоноэра [4.1], алгоритмы типа (4.12) соответствуют «машинной реализации» и рассмотрению задачи в исходном пространстве, а алгоритмы типа (4.9) —«персептронной реализации», и рассмотрению задачи в «спрямляющем» пространстве. Из результатов, приведенных в § 4.4, следует, что эти реализации эквивалентны друг другу.

§ 4.5. «Гипотеза представимости» была введена М. А. Айзерманом, Э. И. Браверманом, Л. И. Розоноэром [4.1] — [4.3]. Отметим, что при этом была доказана сходимость полученных ими алгоритмов не с вероятностью единица, а только по вероятности и при условии, что система функций , ортонормальна. В частности, во второй из упомянутых работ было получено условие (4.19). Э. М. Браверман [4.2] снял одно из ограничений и доказал сходимость соответствующих алгоритмов с вероятностью единица. При изложенном здесь подходе нет нужды использовать гипотезу представимости, при этом доказывается сходимость с вероятностью единица, т. е. почти наверное.

§ 4.6. О персептроне Розенблата написано очень много. Мы здесь укажем лишь наиболее интересные, разумеется, с точки зрения нашего похода, работы. Прежде всего, это работы Ф. Розенблата [4.1] — [4.3]. Важные подробности о персептронах можно найти в работе Г. Блока [4.1]. Возможность построения персептронов не только на пороговых элементах была отмечена В. А. Якубовичем [4.1], [4.2] и М. А. Айзерманом, Э. М. Браверманом, Л. И. Розоноэром [4.1].

§ 4.7. Изложенные результаты основаны на работе И. П. Девятерикова, А. И. Пропоя и автора [4.1].

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

Алгоритмы 1-4 табл. 4.1 были получены М. А. Айзерманом, Э. М. Браверманом, Л. И. Розоноэром [4.1] — [4.3]. В. А. Якубовичем [4.2] получены алгоритмы обучения, близкие к алгоритмам 1 и 3 табл. 4.1. Им было введено понятие С- и L-оптимальности и дано сравнение этих алгоритмов.

М. Е. Шайкин [4.1] показал, что алгоритм 4 табл. 4.1, в том случае, когда выполнена гипотеза представимости, обеспечивает сходимость по вероятности к вектору ; при этом среднеквадратическая ошибка равна нулю.

Упрощение доказательства сходимости этого алгоритма с помощью одного из результатов А. Дворецкого по стохастической аппроксимации получено сравнительно недавно в работе К. Блайдона [4.1].

§ 4.8. Изложенная здесь идея получения поискового алгоритма была впервые описана Д. Купером [4.1], (см. также Д. Бяласевич [4.1], [4.2] и Ю. П. Леонов [4.1]).

§ 4.9. Алгоритмы типа (4.30) были получены В. Н. Вапником, А. Я. Лернером, А. Я. Червоненкисом [4.1] на основе введенного ими понятия обобщенного портрета, см. также В. Н. Вапник, А. Я. Червоненкис [4.1] — [4.3].

§ 4.10. Алгоритм (4.31) при именно в такой форме был получен М. А. Айзерманом, Э. М. Браверманом, Л. И. Розоноэром [4.1]. В несколько иной форме он ранее был получен А. Новиковым [4.1] (см. § 4.12).

§ 4.11. Прием замены системы неравенств системой равенств использовался несколько иначе в работе Ю. Хо и Р. Кашиапа [4.1], [4.2].

§ 4.12. См. также работу И. П. Девятерикова, А. И. Пропоя и автора [4.1]. Алгоритм (4.42), когда Г — матрица, рассматривался А. Новиковым [4.1]. Интересные соображения о сходимости алгоритмов и об использовании периодических показов одних и тех же образов приводятся Б. М. Литваковым [3.1].

§ 4.13. Быть может, полезно продолжить обсуждение, рассмотрев некоторые результаты обучения опознаванию образов. Персептроны и, в частности, персептроны Б. Уидроу [4.3] — [4.5] типа «Адалина» были использованы для предсказания погоды, распознавания речи, почерка, для диагностики, а также как обучаемое устройство, — см. Б. Уидроу, [4.1]. Интересны и сами результаты, полученные при таких применениях.

В первом случае на вход персептрона подавались (после кодирования) измерения барометрического давления в различных точках. Выход персептрона соответствовал ответу — будет или не будет дождь. При этом использовалась система из трех персептронов. Предсказание дождя делалось для трех интервалов по 12 часов:

I. Сегодня — с 8 утра до 8 вечера

II. Сегодня — с 8 вечера до 8 утра

III. Завтра — с 8 утра до 8 вечера

Измерение производилось в первый день в 4 часа утра. В опыте использовались три способа задания информации:

А — «сегодняшняя» карта давлений в 4 часа утра;

В — «сегодняшняя» и «вчерашняя» карта, обе в 4 часа утра;

С — «сегодняшняя» карта и разность между сегодняшним и вчерашним давлением.

Опыт производился в течение 18 дней. Результаты приведены в таблице.

Официальный прогноз	Проценты правильного предсказания
	I	II	III
	78	89	67
А	72	67	67
В	78	78	78
С	78	89	83

Необходимо подчеркнуть успех этого опыта, тем более, что использовались данные только о давлении.

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

В типичном эксперименте выход каждого фильтра разбивался на 4 уровня. Каждому слову соответствовало 10 импульсов, а каждый уровень был представлен трехбитовым кодом, так что на каждое слово приходилось 8х3х10 = 240 битов.

Персептрон сигнала тренировался на голос одного лица. После тренировки (при которой использовалось по 10 образцов каждого слова от одного лица) персептрон разбирал новые образцы этих же слов (и от этого же лица) с точностью 98% или лучше. Если же говорило другое лицо, точность была порядка 90%.

Для диагностики по электрокардиограммам (ЭКГ) использовалась трехдорожечная запись, но все дорожки записывались одновременно, так что имелась и фазовая информация.

На вход персептрона эта информация подавалась с интервалом 10 мсек. После 100 импульсов врач, специалист по ЭКГ, определял правильность заключения «здоров» или «болен». Результаты опыта приведены в таблице.

Результаты

Правильно —

«здоров», %

(27 случаев)

Правильно —«болен», %

(30 случаев)

Заключение врача.

Заключение персептрона ...

Персептрон, основанный на обобщенном портрете, использовался для обнаружения нефтеносных скважин. Но данным В. Н. Вапника, А. Я. Лернера, А. Я. Червоненкиса [4.1], использовались двенадцать параметров, относящиеся к 104 пластам малой мощности. Из этих 104 пластов для обучения было выделено 23 пласта нефтеносных и 23 водоносных, т. е. 46 пластов. В результате экзамена после обучения ошибок в разделении пластов не было.

При разделении же 180 пластов большой мощности (из них 45 выделено для обучения с ранее найденным обобщенным портретом) ряд водоносных пластов был принят за нефтеносные. Подробности читатель может найти в упомянутой работе, а также в работе Ш. А. Губермана, М. Л. Извековой и Я. И. Хургина [4.1], в которой приведены результаты применения для этой же цели алгоритмов опознавания, предложенных М. М. Бонгардом, А. Г. Французом и др.

Интересные результаты получены в работе Б. Н. Козинца, Р. М. Ланцмана, Б. М. Соколова, В. А. Якубовича [4.1] по дифференциации почерков, а также в работе В. А. Якубовича [4.1] по распознаванию профилей.

Многие работы посвящены распознаванию букв или цифр, печатных и рукописных. Мы не будем задерживать внимание читателя на этих результатах. Обзоры работ по опознающим устройствам принадлежат В. П. Сочивко [4.1], [4.2].

§ 4.15. Задачей восстановления плотности распределения занимались А. С. Фролов, Н. Н. Ченцов [4.1], Н. Н. Ченцов [4.1], Н. Е. Кириллов [4.1], М. А. Айзерман, Э. М. Браверман, Л. И. Розоноэр [4.2]. Мы, как и авторы этих работ, оставляем в стороне вопросы нормировки .

§ 4.16. Здесь приводятся алгоритмы, полученные в работах автора [4.1], [4.2]. Модифицированные алгоритмы (типа (4.55)) предложены К. Фу и 3. Николичем (см., например, [10.1]). Их утверждение, что модифицированные алгоритмы сходятся быстрее обычных, оказалось ошибочным. Это обстоятельство было выяснено при обсуждении с В. С. Пугачевым смысла модифицированных алгоритмов.

§ 4.17. Обзор принципов самообучения для классификации образов при довольно полной информации можно найти в работе Дж. Спрегинса [4.1]. К этому обзору мы и адресуем читателя, интересующегося различными частными подходами. Из работ этого направления отметим статьи Д. Купера [4.1], П. Купера [4.1], Е. Патрика и Т. Ханкока [4.1], [4.2].

Самообучение типа «доверчивого оптимиста» или «недоверчивого пессимиста», а также комбинаций их изучалось Б. Уидроу [4.5].

Более общие вариационные формулировки задачи самообучения принадлежат М. И. Шлезингеру [4.1].

§ 4.18. Функционал типа среднего риска (4.61) при квадратичной функции потерь, по существу, рассматривался в упомянутой работе М. И. Шлезингера [4.1], а также (в несколько иных обозначениях) в работе Э. М. Бравермана [4.3].

§ 4.19. При вычислении вариации среднего риска мы пользовались результатами, приведенными в учебнике И. М. Гельфанда и С. В. Фомина [2.1] и статье Р. И. Эльмана [4.1].

§ 4.23. О конкретных рекуррентных алгоритмах самообучения идет речь в ряде работ. В работах А. А. Дорофеюка [4.1] и Э. М. Бравермана и А. А. Дорофеюка [4.1] строятся некоторые алгоритмы самообучения на основании представлений, связанных с методом потенциальных функций.

Такой эвристический путь построения алгоритмов оставляет некоторое неудовлетворение. В работах М. И. Шлезингера [4.1] и Э. М. Бравермана [4.3] вводятся частного вида функционалы, минимизация которых должна привести к алгоритмам самообучения.

Э. М. Браверман в результате минимизации среднего риска при квадратичной функции потерь после довольно длинных и сложных рассуждений обосновал рекуррентные алгоритмы, приведенные в табл. 4.3.

Хотя внешне алгоритмы (4.91) — (4.94) отличаются от алгоритмов, полученных Э. М. Браверманом [4.3], все эти алгоритмы, по существу, совпадают. Просто в приведенных здесь алгоритмах использована связь, существующая между коэффициентами разделяющей функции, которая почему-то не была учтена Э. М. Браверманом. Заметим также, что в силу принятого им метода доказательства алгоритма самообучения, довольно жесткие условия, налагаемые им на и , можно ослабить. Оказывается, что из пяти условий достаточно удовлетворить лишь первым двум, т. е. обычным условиям сходимости вероятности итеративных методов (3.34, а).

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

Изложенное в §§ 4.18—4.23 решение задачи самообучения было дано автором и Г. К. Кельмансом [4.1].

К главе V

§ 5.1. Превосходный обзор различных подходов к задачам идентификации приведен в работе Н. Эйкгофа [5.1], а также в обзорном докладе П. Эйкгофа, П. Ван дер Гринтена, X. Квакернака и Б. Велтмана [5.1] на III Международном конгрессе ИФАК по автоматическому управлению.

§ 5.2. Эти простые и наглядные соображения приводятся также в книгах Ш. Чанга [1.1] и Д. Уайлда [3.1].

§ 5.3. Модифицированный алгоритм (5.9) был предложен К. Фу и 3. Николичем. Авторы этого алгоритма возлагали на него большие надежды, чем он того заслуживает (см. комментарий к § 4.16).

§ 5.5. См. также работу автора [5.1].

§ 5.6. Смысл модифицированных алгоритмов рассмотрен также в работе автора [4.2].

§ 5.7. Эта задача рассматривалась М. А. Айзерманом, Э. М. Браверманом, Л. И. Розоноэром [4.2].

§ 5.8. При квадратической функции потерь из (5.35) мы получаем алгоритм, определяющий коэффициенты статистической линеаризации, которые были введены Р. Бутоном [3.1] и И. Е. Казаковым [5.1], [5.2].

§ 5.9. Алгоритмы типа (5.41) были предложены В. Фабианом [3.1] и X. Круцем (см. Д. Уайлд [3.1]) в качестве более простой модификации алгоритмов типа (5.35). Однако, как было показано Э. Д. Аведьяном [5.1], эти алгоритмы, вообще говоря, не взаимозаменяемы.

§ 5.11. Идея использования результатов решения задачи опознавания для идентификации линейных объектов, описывающихся дифференциальным уравнением высокого порядка, изложена в работе Э. М. Бравермана [5.1]. Полезные соображения в связи с идентификацией нелинейных объектов, а также описание эксперимента приведено в работе К. Кирвайтиса и К. Фу [5.1].

§ 5.13—5.14. О дискретных и непрерывных функциональных рядах Вольтерра см., например, работы П. Альпера [5.1], [5.2] и монографию Г. Ван-Триса [5.1].

§ 5.16. Алгоритм (5.74) совпадает с алгоритмом типа Качмажа [3.1]. Он был получен (для частного случая независимых входных воздействий) и успешно применен для решения задач идентификации В. М. Чадеевым [5.1], [5.2]. Здесь эти ограничения снимаются. Аналогичный алгоритм для восстановления не разностного, а дифференциального уравнения, как мы уже упоминали, был получен Э. М. Браверманом [5.1] для коррелированного внешнего воздействия. Естественно, что в этом случае возникают трудности измерения вектора состояния, который определяется производными высоких порядков. Подобные алгоритмы — типа Качмажа — были недавно снова «открыты» Д. Нагумо и А. Нода [5.1] и применены ими для решения задачи идентификации.

§ 5.17. Подобную задачу па основе иного подхода рассматривал М. Левин [5.1].

§ 5.18. Здесь изложен результат, полученный в работе В. П. Живоглядова и В. X. Кешпова [5.1].

§ 5.19. Подобный способ устранения влияния помех указан Д. Сакрисоном [6.1].

К главе VI

§ 6.4. Алгоритмы типа (6.9) реализуются с помощью дискретных фильтров с настраиваемыми весовыми коэффициентами. Примеры такого рода фильтров описаны в работах А. Гершо [6.1] и Л. Проузы [6.1].

Пороговые функции (6.10) широко использовались М. Шетценом [6.1] для построения оптимальных винеровских фильтров. См. также Ю. Ли и М. Шетцен [6.1].

§ 6.5. Эта задача рассматривалась Р. Лакки [6.1], однако приведенный здесь результат несколько отличается от полученного Р. Лакки.

§ 6.6. Содержание этого параграфа основано на результатах Д. Сакрисона [6.1] — [6.3]. Было бы целесообразно при решении подобных задач использовать параллельные методы поиска, разработанные Л. Н. Фицнером [6.1].

§ 6.7. Более подробные данные о фильтре-предикторе читатель может найти в статье Д. Габора, У. Вилби и Р. Вудкока [6.1].

Теория адаптивных фильтров-предикторов, оптимальных по квадратичному критерию, была развита в работах Л. Гарднера [6.1], [6.2].

§ 6.8. Непрерывный адаптивный фильтр, основанный па непрерывном решении системы уравнений, был рассмотрен О. Шефлом [6.1].

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

Дискретный вариант аналогичного фильтра был описан ранее Л. Проузой [6.1]. Интересные соображения о связи методов стохастической аппроксимации и метода Калмана приводятся в работе Ю. Хо [6.1].

§ § 6.9—6.10. Статистической теории приема посвящены книги Л. С. Гуткина [1.1], С. Е. Фальковича [6.1], Д. Мидлтона [1.1], в которых приведена обширная библиография по этому кругу вопросов. В этих книгах анриорная информация предполагается достаточно полной.

§ 6.11. Подобный подход описывался также в работе Ю. П. Леонова [4.1].

§ 6.13. Алгоритм (6.65) впервые был получен при М. Кацем [6.1] совершенно иным путем. Этот алгоритм соответствует критерию оптимальности типа равенства вероятности ошибок 1-го и 2-го родов. Такой критерий приемлем лишь тогда, когда эти ошибки малы. Таким образом, непоисковый алгоритм М. Каца получается недешевой ценой. Иная возможность обнаружения сигналов с помощью адаптивного приемника описана в работах К. Яковеца, Р. Шея, Г. Вайта [6.1] и X. Грогинского, Л. Вильсона, Д. Миддлтона [6.1]. См. также работу П. Тонга и Б. Лю [6.1]. Обзор по пороговым обнаружителям был дан Г. А. Левиным и А. М. Бонч-Бруевичем [6.1].

§ 6.14—6.16. Эта задача была поставлена Г. Кашнером [6.1]. Мы избрали критерий оптимальности, который также был применен Кашнером. Но хотя Кашнер и рассматривал задачу оптимального выделения с помощью метода стохастической аппроксимации, приведенное здесь решение отличается от решения Кашнера. Нужно сознаться, что наша попытка установить связь между этими решениями не увенчалась успехом. Мы так и не смогли попять ни способа решения, ни результата Г. Кашнера.

§ 6.20. Интересно отметить, что полученная нами схема адаптивного приемника совпадает со схемой, предложенной И. Моришита [6.1] для выделения узкополосных сигналов на фоне помех, либо на фоне других узкополосных сигналов меньшей мощности. Однако эта последняя возможность автором теоретически не обоснована. Мы также не смогли обосновать такое свойство рассмотренного адаптивного приемника.

§ § 6.21—6.22. Этот путь построения адаптивного устройства для восстановления входных сигналов очень тесно связан с аналитической теорией нелинейных систем Н. Винера [6.1], а также с методами оценки сигналов, развиваемыми Р. Калманом [6.1].

К главе VII

§ 7.2. Идея глубокой отрицательной обратной связи была высказана X. Блеком [7.1] в связи с улучшением свойств усилителей путем применения отрицательной обратной связи. Эффект отрицательной обратной связи широко использовался также при создании решающих усилителей аналоговых моделирующих установок, см., например, Б. Я. Коган [7.1].

Условия устойчивости систем, допускающих (разумеется, теоретически) неограниченное повышение коэффициента усиления, установлены М. В. Мееровым [7.1], [7.2]. Эти условия можно рассматривать как условия реализуемости эффекта глубокой отрицательной обратной связи. Эффект глубокой отрицательной обратной связи, как это показано Г. С. Поспеловым [7.1], автором [7.1], достигается при осуществлении скользящих режимов в релейных автоматических системах. Недавно обнаружено (см. М. А. Бермант, С. В. Емельянов [7.1]), что подобного рода эффект проявляется и в системах с переменной структурой. Любопытно то обстоятельство, что, несмотря па различие систем и способов достижения устранения влияния изменения характеристик, в основе их лежит один и тот же эффект глубокой отрицательной обратной связи. Об инвариантности см., например, работу А. И. Кухтенко [7.1]. Обсуждение причин, вызывающих необходимость применения адаптации, приводится в книге А. А. Красовского [1.1].

§ 7.3. Первые работы по применению метода стохастической аппроксимации к простейшим системам управления принадлежат Дж. Бертраму [7.1], М. Ульриху [7.1]. См. также П. Шульц [7.1], Р. Куликовский [7.2].

§ 7.4. О дуальном управлении см. основополагающие работы А. А. Фельдбаума [7.1] — [7.3] и неоднократно упоминавшуюся ранее книгу А. А. Фельдбаума [1.1].

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

§ 7.5. Стратегия изучения и управления через тактов была использована Ю. Хо и Б. Валеном [7.1] в задаче управления линейным объектом, которая, как это можно теперь понять, представляет собой частный случай рассматриваемых нами задач. Некоторые рассуждения о возможных стратегиях изучения и управления читатель может найти в работе Ф. Киши [7.1].

§ 7.7 Интересные результаты по таким беспоисковым адаптивным системам (правда, при отсутствии помех) получены М. Л. Быховским [7.1], П. Кокотовичем [7.1]. См. также Дж. Риссанен [7.1] - [7.3], Л. Г. Евланов [7.1], И. Е. Казаков [7.1], И. Е. Казаков и Л. Г. Евланов [7.1].

§ 7.8. О модели чувствительности см. работы М. Л. Быховского [7.1], П. Кокотовича [7.1], Г. Мейсингера [7.1]. Идея использования одной модели для получения одновременно всех функций чувствительности принадлежит П. Кокотовичу [7.1].

Попытка использования самого объекта в качестве модели чувствительности описана К. Нарендра и Д. Стриром [7.1]. По- видимому, в полной мере эту идею реализовать не удастся.

§ 7.9. Результаты этого параграфа связаны с работой Д. Хилла и К. Фу [7.1]. Им принадлежит идея адаптивного способа уменьшения времени адаптации.

§ 7.10. Адаптивные системы с моделями благодаря их простоте находят широкое применение. Одна из первых работ по этим типам адаптивных систем принадлежат М. Марголису и К. Леондесу [7.1].

Вопросы построения адаптивных систем с моделями рассмотрены в работах Е. Риссанена [7.1], [7.2], И. В. Крутовой, В. Ю. Рутковского [7.1], [7.2] и др.

Обзоры Д. Дональсона, Ф. Киши [7.1], И. В. Крутовой, В. Ю. Рутковского [7.1] содержат изложение принципов построения и применения адаптивных систем с моделями, а также библиографию.

§ 7.11. Постановка задачи об управлении переопределенным объектом принадлежит М. Томасу и Д. Уайлду [7.1].

§ 7.13. Именно эта возможность применения алгоритма релаксационного типа и была описана М. Томасом и Д. Уайлдом [7.1]. Ими же доказана сходимость релаксационного алгоритма (7.51).

§ 7.14. С экстремальными системами читатель может познакомиться, например, по книге А. А. Красовского [1.1].

§ 7.15. Подобное описание экстремального объекта использовалось, например, Ю. С. Попковым [7.1], [7.2].

§ 7.19. См. также статью В. И. Костюка [7.1], где для конкретного случая был предложен именно такой путь синтеза экстремальной системы. Интересные результаты приведены в работах Р. Куликовского [7.1], [7.2].

§ 7.20. Мы используем здесь запись дифференциала (7.88), полученную в интересной во многих отношениях статье Л. И. Розоноэра [7.1].

§ 7.21. Эти результаты основаны на работе А. И. Пропоя и автора [7.1].

§ 7.22. Такая постановка задачи синтеза оптимальных систем принадлежит Ю. Хо и Б. Валену [7.1].

§ 7.23. Пример заимствован нами из работы А. Кноля [7.1]. В эксперименте, который был проделан Кнолем, было выбрано , сек. Начальные значения для были равномерно распределены в интервале . Таким образом, каждый вектор из или состоял из 10 точек; всего было 36 векторов. После того как были определены и , оптимальные значения были найдены за три итерации. Эти оптимальные значения были затем проверены на 15 других начальных состояниях , и разделение было полным.

К главе VIII

§§ 8.2—8.4. По поводу основных определений см., например, книгу Б. В. Гнеденко, 10. К. Беляева, А. Д. Соловьева, [8.1]. Там же имеется библиография по математической теории надежности.

§ 8.11. На эту задачу «с высоты» метода динамического программирования взглянул Р. Беллман [1.1].

§ 8.12. При достаточной априорной информации эта задача была решена В. Пирсом [8.1].

§ 8.13. Решение этой минимаксной задачи на основе метода Монте-Карло описано в работе В. Ф. Евсеева, Т. Д. Кораблиной, С. И. Рожкова [8.1].

§ 8.15. Ряд задач оптимизации по критерию надежности рассмотрен в книге К. А. Иыуду [8.1]. Задачи оптимизации информационных сетей рассматривались в работах А. К. Кельманса [8.1], А. К. Кельманса, А. Г. Мамиконова [8.1]. Интересен цикл работ по поиску неисправностей Е. Клетского [8.1], С. Ю. Рудермана [8.1].

§ 8.16. Постановка этой задачи и описание пути решения на основе поискового алгоритма принадлежит К. Грею [3.1].

К главе IX

§ 9.1. Хорошим начальным введением в теорию исследования операций может служить книга А. Кофмана и Р. Фора [9.1]. Но если читатель не настроен на развлекательный лад, то лучше, пожалуй, начинать с книги Т. Саати [9.1].

§§ 9.2 — 9.8. Большое число задач подобного типа рассмотрено в книге Ф. Хэнссменна [9.1], однако в предположении достаточной априорной информации.

§§ 9.9—9.10. Постановка этих задач и пример принадлежал Д. Уайлду [3.1].

§ § 9.11—9.12. По этим вопросам см. работы Де Гюенина [9.1 |. И. П. Кузнецова [9.1] — [9.3].

В отличие от этих работ мы не предполагаем известным распределение вероятностей.

§§ 9.13—9.15. Задача этою рода рассматривалась в связи с синтезом дискретных устройств с минимальными искажениями Дж. Максом [9.1], В. Н. Кошелевым [9.1], P. Лapсоном [9.1]. Вопросами дискретизации занимались также Н. К. Игнатьев и Э. Л. Блох [9.1], P. Л. Стратонович и Б. А. Гришанин |9.1]. Рассмотренная задача тесно связана с задачей самообучения, о которой была речь в гл. IV. Отметим, что при равномерной плотности распределения эта задача была решена приближенным методом Дж. Максом [9.1].

К главе X

§ 10.2. Изложение основ теории игр можно найти в книгах Т. Л. Саати [9.1], Е. Г. Гольштейна и Д. Б. Юдина [10.1]. Ее приложениям к конкретным задачам различных областей человеческой деятельности посвящена книга Р. Д. Льюса и X. Райфы [10.1].

§ 10.3. Теорема Фон Неймана о минимаксе — основа теории игр. Простое доказательство этой теоремы на основе принципа Брауэра о неподвижной точке, принадлежащее Нэшу, приведено в книге Р. Д. Льюса и X. Райфы [10.1].

§ 10.4. На целесообразность рассмотрения погрешностей в определении оптимальных ответов нам было указано В. А. Волконским.

§ 10.5. Алгоритмы обучения решению игр, как это видно из табл. 10.1, охватывает как частные случаи алгоритмы Г. Брауна [10.1] и его разновидности. Модификация этого алгоритма была предложена В. В. Амвросиенко [10.1]. Сходимость алгоритма Брауна была доказана Дж. Робинсон [10.1]. Это доказательство воспроизведено в книге Р. Беллмана, Н. Гликсберга, О. Гросса [9.1]. Г. И. Шапиро [10.1] оценил скорость сходимости, а Р. Брэйтуайт [10.1] применил алгоритмы типа Брауна или, как их теперь называют, алгоритмы Брауна — Робинсон, для решения систем линейных уравнений, вычисления наименьшего кратного и решения игр определенного класса за конечное число шагов. При отсутствии погрешностей в определении оптимальных ответов (т. е. при ) алгоритмы (10.22) переходят в алгоритмы В. А. Волконского [10.1].

Сходимость всех этих алгоритмов вытекает из условий сходимости вероятностных итеративных методов. Таким образом, этим самым устанавливается еще одна связь между различными подходами, которая связана теперь с играми. Теория одного класса методов решения матричных игр, который содержит, в частности, метод Брауна, развита Я. М. Лихтеровым [10.1]. Им также предложены вычислительные алгоритмы с ускоренной сходимостью.

В работах В. В. Амвросиенко [10.1], Э. И. Борисовой и И. В. Магарика [10.1] предложены модификации алгоритма Брауна с ускоренной сходимостью.

§ 10.6. Здесь изложен классический результат Г. Данцига [10.1]. См. также Д. Гейл [10.1], Е. Г. Гольштейн, Д. Б. Юдин [ 10.1]. [10.1].

Интересные приложения игрового подхода к задачам оптимального планирования большой размерности рассмотрены В. А. Волконским [10.1]; 3. Я. Гальперин [10.1] применил алгоритмы Волконского для решения транспортной задачи большой размерности, а В. Г. Медицкий |10.1] рассмотрел задачу распределения плановых заданий.

§ 10.7. Этот пример заимствован из книги Р. Беллмана [1.1]. Некоторым типам игровых систем уравнения посвящена работа В. Ф. Лебедкина и И. С. Михлина [10.1].

§ 10.8. Сходимость этих непрерывных алгоритмов может быть доказана с помощью условий сходимости непрерывных вероятностных методов.

Иной способ итеративного метода решения игр рассмотрел Дж. Данскин [10.1].

§§ 10.10—10.11. Обзор литературы о пороговых элементах и синтезе схем на пороговых элементах принадлежит И. Н. Боголюбову, Б. Л. Овсиевичу, Л. Я. Розенблюму [10.1]. См. также статью В. И. Варшавского [10.1].

§ 10.12. Связь между пороговой реализуемостью и игрой двух лиц с нулевой суммой, которую мы здесь используем, была установлена Ш. Екерсом [10.1].

§ 10.14. Описание схемы персептронов Розенблата содержится в работе Дж. Хей, Ф. С. Мартина, С. В. Уиттена [10.1]. См. также X. Келлер [10.1].

§ 10.15. Описание схемы Адалины Уидроу содержится в работах Уидроу [4.3], [4.4].

Интересные применения Адалины как обучаемого функционального преобразователя можно найти в работе Ф. Смита [10.1].

§ 10.16. «Педантичный» алгоритм в форме (10.75) был предложен X. Ишида и Р. Стюартом [10.1]. Теперь ясно видно, что этот «новый» алгоритм является небольшой модификацией алгоритма персептрона (10.61). Об обучении пороговых элементов и пороговых сетей см. работу Ю. Э. Сагалова, В. И. Фролова и А. Б. Шубина [10.1].

§ 10.17. С основными понятиями теории конечных автоматов можно познакомиться по следующим книгам: М. А. Айзерман, Л. А. Гусев, Л. И. Розоноэр, И. М. Смирнова, А. А. Таль [10.1], А. Гилл [10.1], В. М. Глушков [4.1], Д. А. Поспелов [10.1]. См. также К. Э. Шеннон, Дж. МакКарти [10.1].

Далее мы рассматриваем конечный автомат как конечную динамическую систему.

§§ 10.18—10.19. Принятая здесь запись уравнений конечных автоматов как дискретных динамических систем и. отказ от описаний автоматов матрицами перехода вызван желанием подчеркнуть общность конечных, импульсных и непрерывных систем. Именно эта общность и позволила применить наиболее естественным путем адаптивный подход. Такая системная точка зрения применительно к «линейным» автоматам или, точнее, линейным последовательностным машинам была разработана Д. А. Хаффменом [10.1]. См. также работу автора и Р. Г. Фараджева [10.1]. Принятая здесь точка зрения объясняет, почему мы не затрагиваем множества превосходных работ по теории конечных автоматов, изложенных на специфическом для этой теории языке.

§ 10.20. Задачи о взаимодействии автоматов со средой были поставлены и в значительной мере решены М. Л. Цетлиным [10.1] — [10.3]. Превосходный обзор результатов по этой проблематике до 1961 г. содержится в работе М. Л. Цетлина [10.3]. См. также книгу Д. А. Поспелова [10.1]. Задачам анализа поведения различных конструкций автоматов в среде посвящена довольно обширная литература. Мы отметим работы А. М. Бланка [10.1], Я. М. Бардзиня [10.1], В. И. Брызгалова, И. И. Пятецкого-Шапиро, М. Л. Шика [10.1], В. А. Пономарева [10.1], В. Ю. Крылова [10.1]. Несколько иной подход был развит Р. МакЛареном [10.1], Г. МакМартри и К. Фу [10.1].

Поведению стохастических автоматов в случайных средах были посвящены работы В. И. Варшавского, И. П. Воронцовой [10.1], Н. П. Канделаки и Г. Н. Церцвадзе [10.1], В. Г. Сраговича и Ю. А. Флерова [10.1].

Во всех этих работах определялась целесообразность поведения автоматов. Для этой цели использовалась теория марковских цепей.

§ 10.22. Задачам обучения автоматов, которые связаны с задачами синтеза, посвящено небольшое число работ. К ним относятся работы В. И. Варшавского, И. П. Воронцовой, М. Л. Цетлина [10.1] по обучению автоматов; А. А. Милютина [10.1] по выбору матриц перехода автомата, обеспечивающих оптимальное поведение; А. В. Добровидова и P. Л. Стратоновича [10.1] по синтезу оптимальных автоматов, учитывающих апостериорные вероятности штрафов в процессе работы; Г. МакМартри и К. Фу [10.1] по применению автоматов с переменной структурой для поиска экстремума.

Как заметил читатель, мы здесь рассматривали обучение конечных автоматов точно таким же образом, как и обычных непрерывных или импульсных систем. Удивительно образная характеристика обучающихся автоматов, приведенная в конце этого параграфа, взята нами из работы В. И. Варшавского, И. П. Воронцовой, М. Л. Цетлина [10.1].

§ 10.23. Связь автоматов и марковских цепей обсуждается в книге В. М. Глушкова [4.1]. Приводимый пример неоднократно рассматривался в работах Дж. Скланского [10.1], [10.2]. Марковские цепи благодаря А. А. Фельдбауму [10.1], [10.2] широко используются для исследования установившихся процессов в дискретных экстремальных системах. Эти вопросы рассматривались в книге А. А. Первозванского [10.1], а также в работах Т. И. Товстухи [10.1], [10.2] и X. Киршбаума [10.1]. Они применялись в работе Л. А. Пчелинцева [10.1] для решения задачи поиска неисправностей.

§ 10.24. Теория марковского обучения развивалась Д. Скланским [10.1] в связи с обучаемым пороговым элементом.

Если отказаться от фиксированных уровней порога, т. е. отойти от автоматной трактовки и принять, что не является постоянной величиной, а удовлетворяет обычным условиям ,,, как это сделал недавно Дж. Скланский [10.2], то мы придем к обычной схеме порогового приемника, который мы рассматривали в § 6.13. Этот адаптивный приемник соответствует обучаемому пороговому элементу. С несколько иной точки зрения марковское обучение рассматривалось в работах МакЛарена [10.1], [10.2]. Связь между марковским обучением и стохастической аппроксимацией рассматривалась 3. Николичем и К. Фу [10.1].

К марковским моделям обучения близки стохастические модели обучения Р. Буша и Ф. Мостеллера [1.1]. В них обучение осуществляется в соответствии с заранее постулированным механизмом, а не на основе оптимизации.

Рассмотрение этих задач также возможно с адаптивной точки зрения. Но это завело бы нас слишком далеко.

О последовательном декодировании см, Дж. Возенкрафт и Б. Рейффен [10.1].

§ 10.25. Играм автоматов и их коллективному поведению посвящены работы М. Л. Цетлина [ 10.3], [10.4], М. Л. Цетлина и В. Ю. Крылова [10.1], В. И. Кринского [10.1], В. И. Варшавского, И. П. Воронцовой [10.1], С. Л. Гинзбурга и М. Л. Цетлина [10.1], В. Л. Стефанюка [10.1], В. А. Волконского [10.2]. Интересные результаты по моделированию игр автоматов на цифровых вычислительных машинах описаны В. И. Брызгаловым, И. М. Гельфандом, И. И. Пятецким-Шапиро и М. Л. Цетлиным [10.1], М. Л. Цетлиным, С. Л. Гинзбургом и В. Ю. Крыловым [10.1].

Игры автоматов вслепую рассмотрены в работах В. И. Кринского и В. А. Пономарева [10.1], [10.2].

Комментарии