Рекуррентные алгоритмы обучения и самообучения в теории распознавания образов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ
|
Измакова, Ольга Анатольевна
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Санкт-Петербург
МЕСТО ЗАЩИТЫ
|
||||
|
2005
ГОД ЗАЩИТЫ
|
|
01.01.09
КОД ВАК РФ
|
||
|
|
||||
САНКТ-ПЕТЕ РБ>ТГСКИЙ ГОСУДАРСТВЕННЬШ УНИВЕРСИТЕТ
На правах рукописп
Измакова Ольга Анатольевна
РЕКУРРЕНТНЫЕ АЛГОРИТМЫ ОБУЧЕНИЯ И САМООБУЧЕНИЯ В ТЕОРИИ РАСПОЗНАВАНИЯ ОБРАЗОВ
01.01.09 — дискретная математика и математическая кибернетика
АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук
Санкт-Петербург 2005
Работа выполнена на кафедре теоретической кибернетики математико-механпческого факультета Санкт-Петербургского государственного университета.
Научные руководители: доктор физико-математических наук
ФОМИН Владимир Николаевич ,
доктор физико-математических наук ГРАНИЧИН Олег Николаевич.
Официальные оппоненты: доктор физико-математических наук
БАРАБАНОВ Андрей Евгеньевич,
кандидат физико-математических наук, КОСОВСКАЯ Татьяна Матвеевна.
Ведущая организация:
Защита состоится " ^
Санкт-Петербургский институт информатики и автоматизации РАН.
иноил' 2005 года в ^ часов ОО ми-
нут на заседании диссертационного совета Д 212.232.29 по защите диссертаций на соискание ученой степени доктора наук при Санкт- ^ Петербургском государственном университете по адресу:
С диссертацией можно ознакомиться в Научной библиотеке им. А. М. Горького Санкт-Петербургского государственного университета по адресу: Санкт-Петербург, Университетская наб., д.7/9.
Автореферат разослан
2005 г.
Ученый секретарь
диссертационного совета Д 212.232.29, доктор физико-математических наук, профессор
В. М. Нежинский
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Исследования, связанные с развитием теории распознавания образов, не теряют своей актуальности более полувека. Параллельно с рождением п развитием новых прикладных областей науки возникает необходимость и в новых математических инструментах распознавания, обращение к которым позволит получать решения возникающих в этих областях задач. В частности, возникает потребность в алгоритмах, приспособленных к применению в нестандартных, с точки зрения развитой ранее теории, условиях.
Литература, посвященная распознаванию образов, весьма обширна. К ней относятся как: работы теоретического характера (М. А. Ай-зерман, Э. М. Браверман, Л. И. Розоноэр, Р. Дуда, П. Харт, Н. Г. За-горуйко, В. Н. Фомин, К. Фукунага, Я. 3. Цыпкин, М. И. Шлезингер, В. А. Якубович), так и работы, в которых обсуждаются вопросы функционирования конкретных опознающих систем (А. Г. Ивахнен-ко, Ю. П. Зайченко, В. Д. Димитров). Такое разделение достаточно условно, поскольку большинство работ первой группы также содержит практические рекомендации и результаты моделирования конкретных опознающих систем. В вышеперечисленных монографиях и статьях можно найти детальное обсуждение различных постановок задач теории распознавания и методов их решения.
В настоящей работе использованы геометрический подход к задаче распознавания образов, который изложен в монографии В. Н. Фомина "Математическая теория обучаемых опознающих систем" (Л.: Изд-во Ленинградского ун-та, 1976) и подход, основанный на методах стохастической аппроксимации (В. Н. Фомин, "Рекуррентное оценивание и адаптивная фильтрация", М.: Наука, 1984). Традиционными недостатками значительного числа алгоритмов, развитых в рамках указанных подходов, являются неприменимость в условиях большой размерности и/или отсутствие состоятельности без достаточно ограничительных условий на неконтролируемые возмущения (помехи). Между тем, многие из возникающих на современном этапе практических задач характеризуются высокой размерностью. Кроме того, при рассмотрении задач с помехами желательно делать лишь мини-
мальные предположения об их статистических свойствах.
В последнее десятилетие развитие получили рандомизированные алгоритмы многомерной оптимизации и оценивания, позволяющие получать состоятельные оценки без стандартных предположений о независимости и центрированности помех наблюдения (О. Н. Гра-ничин, Б. Т. Поляк, А. Б. Цыбаков, Дж. Спал и др.). В монографии О. Н. Граничина и Б. Т. Поляка "Рандомизированные алгоритмы оптимизации и оценивания при почти произвольных помехах" (М.: I Наука, 2003) была предложена идея использования рандомизированных алгоритмов оптимизации в задаче самообучения.
Целью работы является разработка новых алгоритмов обучения и самообучения для решения задачи классификации, работоспособных в условиях большой размерности и при минимальных ограничениях на неконтролируемые возмущения.
Методы исследования. В диссертации применяются методы теории оценивания и оптимизации, функционального анализа и теории вероятностей, а также компьютерное моделирование.
Научная новизна. В диссертационной работе получены следующие новые результаты: разработан и обоснован метод последовательной аппроксимации, позволяющий строить проекцию элемента гильбертова пространства на замкнутую линейную оболочку конечномерных подпространств, если алгоритм проектирования на конечномерные подпространства задан; получены явные формулы для вычисления коэффициентов аппроксимирующей функции при решении задачи среднеквадратичной аппроксимации методом последовательного проектирования; предложены рандомизированные алгоритмы стохасти- ! ческой оптимизации, адаптированные для решения задачи самообучения; установлены достаточные условия состоятельности рандомизированных алгоритмов стохастической оптимизации в задаче самообучения.
Практическая ценность. Представленные в настоящей работе новые алгоритмы могут быть использованы для решения разнообразных задач теории распознавания образов. Например, метод последовательного проектирования применим для решения задачи среднеква-
дратичной аппроксимации функций, возникающей в рамках теории распознавания образов. Кроме того, этот метод применим для доказательства сходимости метода группового учета аргументов. Рандомизированные алгоритмы стохастической оптимизации могут использоваться при решении конкретных задач самообучения, в частности, в качестве алгоритма настройки весовых коэффициентов ассоциативных нейронных сетей.
Апробация работы. По материалам диссертации были сделаны доклады на Первой международной конференции по мехатронике и робототехнике (Санкт-Петербург, 2000 г.), на заседании международной школы-семинара "Адаптивные роботы - 2004" (Санкт-Петербург), а также на семинарах кафедр теоретической кибернетики и системного программирования математико-механического факультета Санкт-Петербургского государственного университета.
Публикации. Основные результаты диссертации опубликованы в работах [1] — [6].
Работа выполнена при поддержке Российского фонда фундаментальных исследований (гранты 98-01-00581 и 05-07-90179).
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы, содержащего 68 наименований. Включает 10 рисунков. Общий объем работы — 109 страниц.
СОДЕРЖАНИЕ РАБОТЫ
Во введении обосновывается актуальность тематики диссертационной работы и кратко излагаются ее основные результаты.
В первой главе подробно обсуждаются различные постановки задачи распознавания образов, в том числе, задачи обучения с учителем и самообучения. Один из распространенных подходов к задачам обучения с учителем заключается в том, что они могут быть сведены к задаче аппроксимации некоторой функции. Особенность большинства задач обучения с учителем позволяет заменить их задачей аппроксимации конечнозначной функции. Значения этой функции на тренировочной последовательности интерпретируются как указания
"учителя" о принадлежности элементов обучающей последовательности тому или иному классу образов.
Одним из наиболее распространенных подходов к решению задачи самообучения служит вариационный подход, при котором процесс обучения сводится к построению последовательности оценок, минимизирующей функционал специального вида. Вариационный подход позволяет строить алгоритмы обучения в рекуррентной форме, и предоставляет возможность использовать для вывода алгоритмов самообучения метод стохастической оптимизации.
В завершении первой главы описан алгоритм локального обучения, в котором на основе геометрического подхода к задаче распознавания реализована идея построения опознающей системы как набора поверхностей заданного вида, выполняющих разделение на классы на подмножествах признакового пространства, выделение которых происходит в процессе обучения.
Во второй главе обсуждается задача аппроксимации, трактуемая как задача экстраполяция функции с некоторого конечного множества, на котором ее значения известны, на более широкое множество аргументов с помощью восстанавливающей функции — линейной комбинации заданных (базисных) функций. Коэффициенты восстанавливающей функции определяются из требования ее близости в среднеквадратичном смысле к аппроксимируемой функции на множестве, где ее значения известны. Указанная задача всегда разрешима, однако развитые методы ее решения могут оказаться непродуктивными в некоторых задачах, возникающих в приложениях, что может быть, например, связано с большой размерностью или плохой обусловленностью конструируемых в ходе решения матриц. Например, при использовании алгоритма антиградиентного спуска в условиях, когда система базисных функций велика, может возникать необходимость выбора очень малого шага аппроксимации (лемма 1). Применение алгоритма Гаусса также может быть затруднительно или давать большую погрешность вычислений, если матрица коэффициентов плохо обусловлена или имеет большие размеры.
Основной результат второй главы — формулировка и обоснование
метода последовательного проектирования, позволяющего избежать вышеуказанных трудностей. Метод изложен на абстрактном уровне и позволяет строить проекцию заданного элемента гильбертова пространства на замкнутую линейную оболочку набора конечномерных подпространств, используя ортогональное проектирование на произвольные конечномерные подпространства.
Уточним постановку задачи. Пусть в гильбертовом пространстве Н задана последовательность {Н/., к — 1,2,...} базисных подпространств Н/; (которые предполагаем конечномерными). Пусть задан также элемент / £ Н. Требуется найти ортогональную проекцию этого элемента на замкнутую линейную оболочку заданных подпространств, предполагая, что алгоритм вычисления искомой проекции может содержать только проектирование на Н/;, к — 1,2,..., дополненное одномерными проекциями. Обозначим через fi = Рщ/ ортогональную проекцию элемента / на базисное подпространство Hi, а через Н2 = 1Лп{Нг, /1} — линейную оболочку, порождаемую базисным подпространством Нг и элементом f\. Продолжая этот процесс, определим элементы /„ и подпространства H„+i согласно алгоритму:
/„ = Рйп/, Hn+1 = Lin{Hn+1)/„}, n = l,2,.... (1)
Лемма 2 Для произвольного элемента /6 Ни последовательности подпространств {Щ С Н, к — 1,2,...} для последовательных проекций {/„, п Е N} справедливо предельное равенство
lim /„ = f,
n->oo J" J'
где f — некоторый элемент из замкнутой линейной оболочки, порождаемой подпространствами {Н/;, к = 1,2,...}.
Для того, чтобы установить условия, при которых предел последовательных проекций {/„, п = 1,2,...} совпадает с искомой проекцией,, введем следующее определение.
Определение Последовательность {Н/; С Н, к = 1,2,...} назовем чередующейся, если каждый из ее элементов встречается в любой подпоследовательности {Н/:, к = М,М + 1,...}, где М — произвольное положительное число.
Теорема 1 Если последовательность базисных подпространств {Щ С Н, к ~ 1,2,...} чередующаяся, то для произвольного элемента / б Н последовательные проекции /„, п = 1,2,..., построенные в соответствии с алгоритмом (1), сходятся к ортогональной проекции элемента / на замкнутую линейную оболочку подпространств Нл-, к = 1,2,.. .:
/н0 = ¿Цп/п = РН(о,/.
Представленный алгоритм может быть успешно использован для решения задачи среднеквадратичной аппроксимации функции линейной комбинацией функций заданного набора. Действительно, такая задача эквивалентна задаче вычисления ортогональной проекции эле-
мента f =
/ы
пространства 11р на подпространство, которое
\f(xp)J
является линейной оболочкой N одномерных подпространств, каждое
(<Рк(х1)\ <Рк(х г)
из которых определяется вектором щ = . , составленным
\<Рк(Хр))
из значений одной из базисных функций, и нахождения коэффициентов разложения найденного вектора / по векторам уьу>2> • • • ><PN■ В п. 2.4.2 подробно описаны указанные этапы решения поставленной задачи. С помощью вспомогательной леммы 3 получены явные формулы для вычисления компонентов вектора / и коэффициентов, определяющих искомую аппроксимирующую функцию (леммы 4 и 5).
В п. 2.5 и 2.6 рассматриваются методы кусочно-параметрической и локальной аппроксимации функций в основе которых лежит идея построения восстанавливающих функций на подмножествах множества аппроксимации.
Глава 2 завершается обсуждением проблемы выбора системы базисных функций.
Третья глава посвящена развитию рандомизированных алгритмов стохастической оптимизации, адаптированных для решения задачи самообучения. Краткая постановка задачи обучения без учителя такова. Пусть на вход обучающейся опознающей системы поступают входные стимулы. Предположим, что каждый стимул принадлежит одному из классов, число которых фиксировано и равно I. Входным стимулам соответствуют их описания — векторы признакового пространства X, которые будем обозначать через х. По последовательности Ж1,Х2,... ж„> • • являющейся реализацией последовательности случайных величин с неизвестным законом распределения V, найти оценку Т значения Т*, доставляющего минимум функционалу средне-
Здесь дк(х,Т), к = 1,2,...,/ — штрафные функции, <7к(Т,х), к = 1,2,...,/ — характеристические функции множеств Хк (Т):
Для оптимизации функционала среднего риска часто используются различные градиентные алгоритмы. На практике возможность их использования ограничена тем, что точные значения градиента не всегда доступны. Кроме того, при решении задач оптимизации в условиях большой размерности реализация градиентных алгоритмов весьма трудоемка. Эти факторы обуславливают развитие подходов, основанных на аппроксимации градиента. Однако, псевдоградиентные процедуры также имеют серьезные недостатки: для доказательства состоятельности оценок приходится накладывать достаточно ограничительные условия на неконтролируемые возмущения; в многомерном случае приходится делать большое число наблюдений, что может оказаться трудно осуществимым. В последнее десятилетие интерес исследователей вызывают рандомизированные алгоритмы оценивания,
го риска
Хк(Т) = {х€Х: дк(х,Т) < ; = 1,2, 1,
д\х,Г)<^(х,Т), з = к + 1,...,1), ¿ = 1,2,...,/.
в основе которых лежит использование пробных возмущений, статистическая прпрода которых играет существенную роль при обосновании сходимости такого типа алгоритмов. Особенность рандомизированных алгоритмов заключается в том, что для аппроксимации градиента функции на каждом шаге можно использовать небольшое заранее фиксированное число ее измерений независимо от размерности задачи оптимизации. При этом рандомизированные алгоритмы сходятся при "почти произвольных" помехах (под этим понятием подразумевается достаточно широкий класс помех в наблюдениях, содержащий, в частности, детерминированные неизвестные, но ограниченные последовательности). В диссертации предложены рандомизированные алгоритмы стохастической оптимизации, которые применимы для решения задачи обучения без учителя.
Рассматриваемая в третьей главе задача самообучения осложнена тем, что функции д':(-, •) не заданы аналитически, но их значения доступны измерению (может быть с помехами):
ук(х,Т) = як(х,Г) + ук, * = 1,2,...,1.
Через У(х, Т) будем обозначать ¿-мерный вектор, составленный из величин ук(х}Т), к = 1,2,через V — /-мерный вектор помех, через J(■,T) обозначим вектор-функцию, образованную характеристическими функциями J!:{T){•)■¡ к = 1,2,...,1.
Формирование последовательности оценок {Тпоптимального набора % может быть проведено в соответствии с одним из представленных ниже рандомизированных алгоритмов стохастической оптимизации. Алгоритмы основаны на использовании наблюдаемой последовательности случайных независимых друг от друга векторов А я € И"1, п = 1,2,..., называемых в дальнейшем пробным одновременным возмущением и составленных из независимых, бернулли-евских, равных ±1 случайных величин.
Зафиксируем некоторый начальный набор 7о 6 11т/' и выберем последовательности положительных чисел, стремящиеся к нулю: {&„} и Ш- Рассмотрим следующие алгоритмы построения искомой по-
следовательности оценок:
(7* = %-х ± /?„АпЗт{хп,%-х),
\ (2)
1 % = Рт (%-х - а^п^^Щ^^А^х^-х)) ,
' % = %-х+0пАп/г(хп,%-1),
(3)
% = Рт (%-х - |-^(ггп,Г„-1)У(:сп,Гп)Ап/г'(^,Гп-1)) •
Здесь Рт — оператор проектирования на некоторое выпуклое замкнутое ограниченное подмножество Т С К"1*', которое содержит точку %. Предполагается, что такое множество известно.
В п. 3.1. рассматривается случай однотипных функций дк(х, Т), к = 1,2,... и предполагается, что функции дк(х,7~) = г/;(х,тк) не зависят от векторных элементов набора Т, отличных от к. Таким образом, считаем, что дк(х,Т) = д(х,тк), где ?(•,•) : X х К™ И — некоторая общая для разных классов штрафная функция.
Сформулируем предположения, которым должна будет удовлетворять штрафная функция ?(•,•).
П.1. Функция д(ж,-) : И"* Л — дифференцируема при любом а; € X и ее градиент удовлетворяет условию Липшица, т. е.
||Уг?(*,7-1) - утд(ж,г2)|| < М\\тх - 7*||, Угьг2 € к."1 с некоторой постоянной М > 0, не зависящей от ж 6 X.
П.2. При любом т £ К'" функции (¡(-, т) и V,-<?(■, т) равномерно ограничены на X.
П.З. Каждая из функций
1к(т)= ¡хЧ%)ч(х,т)Р(<1х), к = 1,2,...,1
имеет единственный минимум в И/" в некоторой точке тк и
<Г - тк, Чг1к(т)) > ц\\т - г*||2, Уг € ит с некоторой постоянной ¡л > О (условие сильной выпуклости).
Здесь п далее используются обозначения (•, •) и |j • || для скалярного произведения и нормы в Rm. Обозначим
^max = max max \q(x,
Для оценок, доставляемых предложенными алгоритмами, установлены условия сходимости к истинному значению неизвестных параметров.
Теорема 2 Пусть выполнены условия:
1) обучающая последовательность Х\УХ2, • • ■ ,х„,... состоит из независимых, одинаково распределенных векторных случайных величин с таким законом распределения, что они с ненулевой вероятностью принимают значения в каждом из I классов в признаковом пространстве;
2) функция <!(•,•) удовлетворяет (П.1 - П.З);
3) Vn > 1 случайные векторы V*, V*..., V^ и х\,х%,... , £„-1 не зависят от хп, А„, а случайный вектор х„ не зависит от Д„;
4) ЕЮ < оо, < Ы < С„, Cv > 0;
5) из выполнения неравенства < draax для некоторых k е {1,2,...,/}, х е Хк(%) ит€ Rm следует
+ 2Cv W 6 X''(7;), i ф k, i 6 {1,2,..., l};
6)T,n&n = оо и a„ 0, P„ 0, a„/3~2 0 при n^ оо.
Если для последовательности оценок {Тп}, доставляемых алгоритмом (2) (или алгоритмом (3)), выполнено
TWOO (
ni
%-1)) <
^max +
то последовательность оценок \Гп} сходится в среднеквадратичном смысле: Е{||7^ — 7^||2} 0 при п -5- со, к одному из наборов состоящему из векторов г*,...,
Если, более того, £„+ < оо, то 7J, -4 % при п оо с
вероятностью единица.
Глава 3 завершается результатами компьютерного моделирования работы алгоритмов (2) и (3).
Четвертая глава посвящена применению развитых ранее алгоритмов при использовании подхода биологизации к решению задач аппроксимации и распознавания. Под биологизацией понимается построение и исследование моделей поведения сложных объектов и способов управления ими на основе имитации механизмов, реализованных природой в живых существах. Одно из направлений этого подхода получило название эвристической самоорганизации и отражает основные принципы массовой селекции растений и животных, другое связано с моделированием нейронных систем.
Принцип селекции или эвристической самоорганизации нашел свое отражение в таком методе аппроксимации функций как метод группового учета аргументов (МГУА). Кратко он может быть описан следующим образом: на каждом шаге последовательной аппроксимации исходная конечная система функций специальным образом расширяется, из полученной расширенной системы выбираются всевозможные наборы из заданного числа функций и для каждого набора решается стандартная задача аппроксимации. Из функций, давших наилучшее приближение, формируется система, рассматриваемая как исходная на следующем шаге аппроксимации. Достоверность МГУА подтверждается многими численными примерами. Обоснование метода может быть проведено с помощью метода последовательного проектирования. В п. 4.1 представлен модифицированный метод группового учета аргументов, в котором на каждом шаге происходит возврат к функциям из исходной системы.
Знания о функционировании нервной системы живых существ легли в основу одной из областей современной теории интеллектуальных вычислительных систем, которая связана с построением и применением искусственных нейронных сетей (ИНС). В течение последнего десятилетия данная тематика завоевывает все большую популярность, ей посвящается значительное количество современных научных публикаций. Популярность этого направления в значительной степени связана с тем, что модели, разработанные в его рамках, все более серьезно рассматриваются в качестве методологического базиса для создания сверхскоростных технических устройств параллельной об-
работал информации. Во второй части четвертой главы дано краткое описание биологических основ функционирования нейронов п нейронных сетей, рассмотрены некоторые подходы к описанию искусственных нейронных сетей. Основу функционирования нейронных сетей составляют алгоритмы обучения, позволяющие оптимизировать их весовые коэффициенты. В качестве алгоритмов обучения нейронных сетей могут быть успешно использованы развитые в настоящей работе алгоритмы. В качестве примера применения представленных рандомизированных алгоритмов рассмотрена задача обучения нейронной сети Хебба-Хопфилда, и предложен метод ее решения, использующий представленные в третьей главе рекуррентные рандомизированные алгоритмы самообучения.
В заключении формулируются основные результаты работы:
1. Разработан метод последовательного проектирования, предназначенный для построения ортогональной проекции элемента гильбертова пространства на подпространство, представляющее собой замкнутую линейную оболочку конечномерных подпространств из заданной системы.
2. Обоснована сходимость метода последовательного проектирования, получены условия сходимости последовательных проекций к ортогональной проекции заданного элемента гильбертова пространства на замкнутую линейную оболочку подпространств из исходной системы.
3. Получены явные формулы для расчета коэффициентов восстанавливающей функции при решении задачи среднеквадратичной аппроксимации методом последовательного проектирования.
4. Предложены рандомизированные алгоритмы стохастической оптимизации, предназначенные для решения задачи самообучения.
5. Получены достаточные условия состоятельности оценок рандомизированных алгоритмов стохастической аппроксимации.
ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ
[1] Гулъчак О. А., Фомин В. Я. Задача аппроксимации функции в теории распознавания образов. 4.1. Метод последовательного проектирования и персептронная реализация алгоритмов аппроксимации // Деп. в ВИНИТИ, N 1063-В-99. 32 с.
[2] Гулъчак О. А., Фомин В. И. Задача аппроксимации функции в теории распознавания образов. 4.2. Нейроподобные системы распознавания // Деп. в ВИНИТИ, N 1817-В-99. 25 с.
[3] Измакова О. А. Рандомизированные алгоритмы самообучения для нейронных сетей. // Электронный журнал "Дифференциальные уравнения и процессы управления", N 2, 2005 г. С. 122-142.
[4] Измакова О. А. Рандомизированные алгоритмы самообучения для настройки ассоциативных нейронных сетей. // В сб. "Стохастическая оптимизация в информатике" под ред. О. Н. Граничи-на. Изд-во С.-Петерб. ун-та. 2005. С. 81-102.
[5] Измакова О. А., Сысоев С. С. Алгоритм стохастической оптимизации с возмущением на входе в задаче самообучения. // Труды Международной школы-семинара "Адаптивные роботы — 2004". М.-СПб. 2004. С. 49-52.
[6] Фомин В. Е., Измакова О. А. Об одном алгоритме распознавании образов. // Труды Первой международной конференции по мехатронике и робототехнике. СПб, 2000. С. 355-359.
и
РНБ Русский фонд
20074 9752
Подписано в печать 11.05.2005 г. Формат бумаги 60X90 1/16. Бумага офсетная. Печать рпзографичсская. Объем 1 усл. п. л. Тираж 100 экз. Заказ N 737. Отпечатано в ПК "Объединение Вента" с орппшал-макета заказчика. 197000, Санкт-Петербург, Большой пр. П.С., д. '29а.
Введение
1 Задача распознавания образов
1.1 Обучающиеся опознающие системы.
1.2 Задача распознавания как задача аппроксимации индикаторной функции.
1.3 Линейная разделимость образов.
1.3.1 Выпуклые множества на единичном кубе.
1.4 Нелинейная разделимость образов.
1.4.1 Комитет неравентсв.
1.4.2 Переход в спрямляющее пространство.
1.5 Самообучение.
1.5.1 Автоматическая классификация сигналов
1.5.2 Методы стохастической оптимизации в задаче самообучения
1.6 Алгоритм локального обучения
2 Задача аппроксимации функций
2.1 Среднеквадратичное приближение.
2.2 Алгоритм антиградиентного спуска.
2.3 Система нормальных уравнений Гаусса в стандартной задаче аппроксимации.
2.4 Последовательная аппроксимация.
2.4.1 Метод последовательного проектирования.
2.4.2 Последовательное проектирование в случае одномерных подпространств.
2.5 Кусочно-параметрическая аппроксимация.
2.6 Метод локальной аппроксимации.
2.7 Выбор системы базисных функций
3 Рандомизированные алгоритмы стохастической оптимизации в задаче самообучения
3.1 Алгоритмы стохастической оптимизации с возмущением на входе в задаче самообучения.
3.1.1 Примеры применения представленных алгоритмов
4 Применение рекуррентных алгоритмов обучения
4.1 Метод группового учета аргументов.
4.2 Нейроны, нейронные сети и методы их обучения.
4.2.1 Описание искусственных нейронных сетей.
4.2.2 Локальная аппроксимация в нейросетях.
4.2.3 Алгоритмы самообучения для нейронных сетей
Научные исследования, связанные с развитием теории распознавания образов, не теряют своей актуальности более полувека. Параллельно с рождением и развитием новых прикладных областей науки возникает необходимость и в новых математических инструментах распознавания, обращение к которым позволит получать решения возникающих в этих областях задач. В частности, возникает потребность в алгоритмах, приспособленных к применению в нестандартных, с точки зрения развитой ранее теории, условиях.
Литература, посвященная распознаванию образов, весьма обширна. К ней относятся как работы теоретического характера ([1], [17], [20], [28], [43], [44], [47] [48], [49], [50], [52]-[54]), так и работы, в которых обсуждаются вопросы функционирования конкретных опознающих систем ([21], [33]). Такое разделение достаточно условно, поскольку большинство работ первой группы также содержит практические рекомендации и результаты моделирования конкретных опознающих систем. В перечисленных выше монографиях и статьях можно найти детальное обсуждение различных постановок задач теории распознавания и методов их решения.
В настоящей работе использованы геометрический (экстраполяцион-ный) подход и подход на основе методов стохастической аппроксимации. Традиционными недостатками значительного числа алгоритмов, развитых в рамках указанных подходов, являются неприменимость в условиях большой размерности и/или отсутствие состоятельности без достаточно ограничительных условий на неконтролируемые возмущения. Между тем, многие из возникающих на современном этапе практических задач характеризуются высокой размерностью. Кроме того, при рассмотрении задач с помехами желательно делать лишь минимальные предположения об их статистических свойствах.
Основной целью настоящей работы является разработка новых алгоритмов обучения и самообучения для решения задачи классификации, работоспособных в условиях большой размерности и при минимальных ограничениях на неконтролируемые возмущения.
В диссертационной работе получены следующие новые результаты:
• разработан и обоснован метод последовательного проектирования, позволяющий строить проекцию элемента гильбертова пространства на замкнутую линейную оболочку заданных подпространств, используя проектирование на эти подпространства, дополненное одномерными проекциями;
• получены явные формулы для вычисления коэффициентов аппроксимирующей функции при решении задачи среднеквадратичной аппроксимации методом последовательного проектирования;
• предложены рандомизированные алгоритмы стохастической оптимизации, адаптированные для решения задачи самообучения;
• получены достаточные условия состоятельности рандомизированных алгоритмов стохастической оптимизации в задаче самообучения.
Разработанные и обоснованные в настоящей работе новые алгоритмы могут быть использованы для решения разнообразных задач распознавания. Например, метод последовательного проектирования применим для решения задачи среднеквадратичной аппроксимации функций, в том числе возникающей в рамках теории распознавания образов. Кроме того, этот метод применим для доказательства сходимости метода группового учета аргументов. Рандомизированные алгоритмы стохастической оптимизации могут применяться при решении конкретных задач самообучения, в частности, в качестве алгоритма настройки весовых коэффициентов ассоциативных нейронных сетей.
По материалам диссертации были сделаны доклады на Первой международной конференции по мехатронике и робототехнике (Санкт-Петербург, 2000 г.), на заседании международной школы-семинара "Адаптивные роботы - 2004" (Санкт-Петербург), а также на семинарах кафедр теоретической кибернетики и системного программирования математико-механического факультета Санкт-Петербургского государственного университета. Основное содержание диссертации было опубликовано в работах [15], [16], [22] - [24] и [45], часть из которых написана в соавторстве с научным руководителем В. Н. Фоминым, которым осуществлялась общая корректировка направлений исследования. В статье, написанной в соавторстве с С. С. Сысоевым, диссертанту принадлежит метод решения и его обоснование, а ее соавтору — численное моделирование представленного алгоритма.
Работа выполнена при частичной поддержке Российского фонда фундаментальных исследований (гранты 98-01-00581 и 05-07-90179).
Диссертация организована следующим образом.
В первой главе подробно обсуждаются различные постановки задачи распознавания образов, в том числе задачи обучения с учителем и самообучения.
Один из распространенных подходов к задачам обучения с учителем заключается в том, чтобы представить их в виде задачи аппроксимации некоторой функции (Фомин В. Н. [43]). Особенность большинства задач обучения с учителем позволяет заменить их задачей аппроксимации ко-нечнозначной функции (двузначной в случае двух классов изображений). Значения этой функции на тренировочной последовательности интерпретируются как указания "учителя" о принадлежности элементов обучающей последовательности тому или иному классу образов.
Выбор алгоритма для обучения опознающей системы в значительной степени опирается на априорную информацию, которая известна о классах изображений в пространстве признаков. В п. 1.3 и 1.4 рассмотрены случаи линейной и нелинейной разделимости образов и описаны некоторые из возможных алгоритмов решения задачи обучения с учителем в этих ситуациях.
В следующем пункте первой главы обсуждается задача обучения без учителя. Существует несколько возможных математических формулировок задачи самообучения: оценивание смесей распределений (Дуда Р., Харт П. [17], Фукунага К. [47]), вариационный подход (Цыпкин Я. 3. [48], Айзерман М. А., Браверман Э. М., Розоноэр JI. И. [1], Фомин В. Н. [43], [44]) и множество вариантов кластер-анализа. В настоящей работе используется вариационный подход, при котором процесс обучения сводится к построению последовательности оценок оптимальных параметров, которые доставляют минимум функционалу среднего риска, имеющего смысл математического ожидания общих потерь, и определяют оптимальное разбиение выборочного пространства, т. е. оптимальное правило классификации. Отметим, что вариационный подход позволяет строить алгоритмы обучения в рекуррентной форме, и предоставляет возможность использовать для вывода алгоритмов самообучения метод стохастической оптимизации.
В завершении первой главы описан алгоритм локального обучения, в котором на основе геометрического подхода к задаче распознавания реализована идея построения разделяющей поверхности как набора поверхностей заданного вида, каждая из которых выполняет разделение на классы на одном из подмножеств признакового пространства. Разбиение пространства признаков на эти подмножества происходит в процессе обучения.
Во второй главе обсуждается задача аппроксимации, трактуемая как задача экстраполяция функции с некоторого конечного множества, на котором ее значения известны, на более широкое множество аргументов с помощью восстанавливающей функции — линейной комбинации заданных (базисных) функций. Коэффициенты восстанавливающей функции определяются из требования ее близости в среднеквадратичном смысле к аппроксимируемой функции на множестве, где ее значения известны. Указанная задача всегда разрешима, однако развитые методы ее решения могут оказаться непродуктивными в некоторых задачах, возникающих в приложениях, что может быть связано с большой размерностью или плохой обусловленностью конструируемых в ходе решения матриц. Например, при использовании алгоритма антиградиентного спуска в условиях, когда система базисных функций велика, может возникать необходимость выбора очень малого шага аппроксимации (лемма 1). Применение алгоритма Гаусса также может быть затруднительно или давать большую погрешность вычислений, если матрица коэффициентов плохо обусловлена или имеет большие размеры.
Основной результат второй главы — формулировка и обоснование алгоритма последовательного проектирования, позволяющего избежать указанных трудностей. Метод изложен на абстрактном уровне и позволяет строить проекцию заданного элемента гильбертова пространства на замкнутую линейную оболочку набора конечномерных подпространств в предположении, что имеется возможность вычислять ортогональные проекции на произвольные конечномерные подпространства.
Уточним постановку задачи. Пусть в гильбертовом пространстве Н заданы последовательность {Н^, к = 1,2,.} базисных подпространств Н^ (которые предполагаем конечномерными) и некоторый элемент / Е Н. Требуется найти ортогональную проекцию этого элемента на замкнутую линейную оболочку заданных подпространств, предполагая, что алгоритм вычисления искомой проекции может содержать только проектирование на Hjt, к = 1,2,., дополненное одномерными проекциями. Обозначим через /1 = Phi / ортогональную проекцию элемента / на базисное подпространство Hi, а через Н2 = Lin{H2, /1} — линейную оболочку, порождаемую базисным подпространством Н2 и элементом /1. Продолжая этот процесс, определим элементы /„ и подпространства Hn+i согласно алгоритму: п = Рйп/, Hn+i = Lin{Hn+i,/n}, n = 1,2,---- (0.1)
Важное свойство последовательных проекций отражено в нижеследующей лемме.
Лемма 2 Для произвольного элемента / Е Н и последовательности подпространств {Н& С Н, к = 1,2,.} для последовательных проекций {/w? п £ N} справедливо предельное равенство где / — некоторый элемент из замкнутой линейной оболочки, порождаемой подпространствами {Н&, к = 1,2,.}.
Для того, чтобы установить условия, при которых предел последовательных проекций {/„, п = 1,2,.} совпадает с искомой проекцией, введем следующее определение.
Определение Последовательность {Щ С Н, к = 1,2,.} назовем чередующейся, если каждый из ее элементов встречается в любой подпоследовательности {Щ, к = М, М + 1,.}, где М — произвольное положительное число.
Теорема 1 Если последовательность базисных подпространств {Hfc С Н, к = 1,2,.} чередующаяся, то для произвольного элемента / G Н последовательные проекции /„, п = 1,2,., построенные в соответствии с алгоритмом (0.1), сходятся к ортогональной проекции элемента / на замкнутую линейную оболочку базисных подпространств Н&, к — 1,2,.: но = Jim/п = РнС)/
Представленный алгоритм может быть успешно использован для решения задачи среднеквадратичной аппроксимации функции линейной комбинацией функций заданного набора. Действительно, такая задача эквиf(*i)\ t /Ы валентна задаче вычисления ортогональной проекции элемента / = f(Xp)) пространства Rp на подпространство, которое является линейной оболочкой N одномерных подпространств, каждое из которых определяется ((fk{xi)\ вектором (fk = составленным из значений одной из базисных
Wfc(Zp)/ функций, и нахождения коэффициентов разложения найденного вектора / по векторам ipi, <р2,., <pn- В п. 2.4.2 подробно описаны указанные этапы решения поставленной задачи. С помощью вспомогательной леммы 3 получены явные формулы для вычисления компонентов вектора / и коэффициентов, определяющих искомую аппроксимирующую функцию (леммы 4 и 5).
В п. 2.5 и 2.6 рассматриваются методы кусочно-параметрической и локальной аппроксимации функций (Катковник В. Я. [25], [26]), в основе которых лежит идея построения восстанавливающих функций на подмножествах множества аппроксимации.
Глава 2 завершается обсуждением проблемы выбора системы базисных функций.
Третья глава посвящена развитию рандомизированных алгоритмов стохастической оптимизации, адаптированных для решения задачи самообучения. Краткая постановка задачи обучения без учителя такова. Пусть на вход обучающейся опознающей системы поступают входные стимулы. Предположим, что каждый стимул принадлежит одному из классов, число которых фиксировано и равно I. Стимулам в признаковом пространстве X соответствуют их описания, которые будем обозначать через х. По последовательности ,. хп,., являющейся реализацией последовательности случайных величин с неизвестным законом распределения V, найти оценку Т набора = (г^, г*,., тк ^ рт = 1,2,.,/), доставляющего минимум функционалу среднего риска
F(T) = / Е Jk(T,x)qk(x,T)V(dx). х *=1
Здесь Т),к = 1,2,.,/ — штрафные функции, Jk(T, х), к = 1,2,., / — характеристические функции множеств Х*(Т):
Х*(Г) = €Е X : g*(s,T) < q*(x,T), j = 1,2,. , & - 1, qk(x,T)<qj(x,T), j = A + l,.,Z}, A = 1,2,.,/.
Для оптимизации функционала среднего риска часто используются различные градиентные алгоритмы. На практике возможность их использования ограничена тем, что точные значения градиента не всегда доступны. Кроме того, при решении задач оптимизации в условиях большой размерности реализация градиентных алгоритмов весьма трудоемка. Эти факторы обуславливают развитие подходов, основанных на аппроксимации градиента. Однако, псевдоградиентные процедуры также имеют серьезные недостатки: для доказательства состоятельности оценок приходится накладывать достаточно ограничительные условия на неконтролируемые возмущения; в многомерном случае приходится делать большое число наблюдений, что может оказаться трудно осуществимым. В последнее десятилетие интерес как зарубежных, так и российских исследователей вызывают рандомизированные алгоритмы оценивания, получившие развитие в работах Дж. Спала, Граничина О. Н., Поляка Б. Т., Цыбакова А. Б., ([6] - [13], [35], [61], [64] - [66]). В их основе лежит использование пробных возмущений, статистическая природа которых играет существенную роль при обосновании сходимости такого типа алгоритмов. Особенность рандомизированных алгоритмов заключается в том, что для аппроксимации градиента функции на каждом шаге можно использовать небольшое заранее фиксированное число ее измерений независимо от размерности задачи оптимизации. При этом рандомизированные алгоритмы сходятся при "почти произвольных" помехах (под этим понятием подразумевается достаточно широкий класс помех в наблюдениях, содержащий, в частности, детерминированные неизвестные, но ограниченные последовательности). В [13] была предложена идея использования рандомизированных алгоритмов оптимизации в задаче самообучения. В диссертации новые рандомизированные алгоритмы, адаптированные для решения задачи самообучения, были разработаны и обоснованы.
Рассматриваемая в третьей главе задача самообучения осложнена тем, что функции qk(•, •) не заданы аналитически, но их значения доступны измерению (может быть с помехами): yk(x,T)=qk(x,T) + vk, fc = l,2,.,/.
Через Y(x,T) будем обозначать /-мерный вектор, составленный из величин ук(х,Т), к = 1,2,.,/; через V — /-мерный вектор помех, через J(-,T) обозначим вектор-функцию, образованную характеристическими функциями Jk(T)(•), к = 1,2,.,/,
Формирование последовательности оценок оптимального набора % может быть проведено в соответствии с одним из представленных ниже рандомизированных алгоритмов стохастической оптимизации. Алгоритмы основаны на использовании наблюдаемой последовательности случайных независимых друг от друга векторов Дп 6 Rm, п = 1,2,., называемых пробным одновременным возмущением и составленных из независимых, бернуллиевских, равных ±1 случайных величин.
Зафиксируем некоторый начальный набор 7о € Rmxi и выберем последовательности положительных чисел, стремящиеся к нулю: {ап} и {(Зп}-Рассмотрим следующие алгоритмы построения последовательности оценок оптимального набора 7^:
Т± = Tn-i ± PnKJT(x
0.2)
Тп = Рт (tn-1 - anJT(xn,tn-Oy(x"'7;+^Y(x"'7;")AnJrK,r»-i)) ,
Tn = *Тп—i + (3nAnJ (ЖгпТп—l),
0.3)
Тп = Рт (tn-1 - ^JT(xn,tn^)Y(xn,tn)AnJT(xn,rn-i)) .
Здесь Рт — оператор проектирования на некоторое выпуклое замкнутое ограниченное подмножество Т С RmxZ, которое содержит точку Т*. Будем предполагать, что такое множество известно.
В п.3.1 рассматривается случай однотипных функций qk(x,7~), к = 1,2,.,/, и предполагается, что функции qk(x,T) не зависят от векторных элементов набора Т, отличных от к-то: qk(x,T) = qk(x,rk). Таким образом, считаем, что qk(x,T) = q(x,rk), где ?(-,•) : X х Rm —> R — некоторая общая для разных классов штрафная функция.
Сформулируем предположения, которым должна будет удовлетворять штрафная функция <?(-,•)•
П.1. Функция q(x, •) : Rm —> R — дифференцируема при любом х € X и ее градиент удовлетворяет условию Липшица, т. е.
VT£(s,ri) - VTq(x,r2)\\ < М\\П - r2||, Vrbr2 Е Rm с некоторой постоянной М > 0, не зависящей от х (Е X.
П.2. При любом т £ Rm функции q(-,r) и Vr</(-,r) равномерно ограничены на X.
П.З. Каждая из функций имеет единственный минимум в Rm в некоторой точке тк и t-tk,vrfk(t))>n\\t-tk\\\ Vr G Rm с некоторой постоянной ц > О (условие сильной выпуклости).
Здесь и далее используются обозначения (•,•} и || • || для скалярного произведения и нормы в Rm. Обозначим dm ах = max max I q(x,rk)\.
Для оценок, доставляемых предложенными алгоритмами, установлены условия сходимости к истинному значению неизвестных параметров. Теорема 2 Пусть выполнены условия:
1) обучающая последовательность xi,X2, • • ■ ,хп,. состоит из независимых, одинаково распределенных векторных случайных величин с таким законом распределения, что они с ненулевой вероятностью принимают значения в каждом из I классов в признаковом пространстве;
2) функция q{•,•) удовлетворяет (П.1 - П.З);
3) Vn > 1 случайные векторы V^, V^ . и xi,x2,. , не зависят от хп,Ап, а случайный вектор хп не зависит от Ап;
4) E{vn} < оо, < а2п, Н < Cv, Cv > 0;
5) из выполнения неравенства \q(x,r)\ < dmax для некоторых k G {1,2,.,/}, X е Х.к(Т*) ит e~Rm следует W G Хг(7^), i^k, i € {1,2,.,/};
6) En — и ап 0, /Зп 0, ап{3~2 —» 0 при п —> оо.
Если для последовательности оценок {Тп}, вычисляемых по алгоритму (0.2) (или алгоритму (0.3)), выполнено
Тдп (j{xn,tn-i),Q(xn,tni)} < dmax + Cv, то последовательность оценок {Тп} сходится в среднеквадратичном
А смысле: Е{||7^ — } —> 0 при п -4 оо, к одному из наборов 71, состоящему из векторов т*, ., т[.
Если, более того, En+ апРп2 < то 7~п —> % при п —> оо с вероятностью единица.
Глава 3 завершается результатами компьютерного моделирования работы алгоритмов (0.2) и (0.3).
Глава 4 посвящена применению развитых ранее алгоритмов при использовании подхода биологизации к решению задач аппроксимации и распознавания. Под биологизацией понимается построение и исследование моделей поведения сложных объектов и способов управления ими на основе имитации механизмов, заимствованных у живой природы. Одно из направлений этого подхода получило название эвристической самоорганизации и отражает основные принципы массовой селекции растений, и животных, другое связано с моделированием нейронных систем.
Принцип селекции или эвристической самоорганизации нашел свое отражение в одном из методов аппроксимации функций, развитом А. Г. Ивах-ненко ([21, 33]) и получившим название метод группового учета аргументов (МГУА). Кратко этот метод может быть описан следующим образом: на каждом шаге последовательной аппроксимации исходная конечная система функций специальным образом расширяется, из полученной расширенной системы выбираются всевозможные наборы из заданного числа функций и для каждого набора решается стандартная задача аппроксимации. Из функций, давших наилучшее приближение, формируется система, рассматриваемая как исходная на следующем шаге аппроксимации. Достоверность МГУА подтверждается многими численными примерами ([21]). Обоснование метода может быть проведено с помощью метода последовательного проектирования. В п. 4.1 представлен модифицированный метод группового учета аргументов, в котором на каждом шаге происходит возврат к функциям из исходной системы.
Знания о функционировании нервной системы живых существ легли в основу одной из областей современной теории интеллектуальных вычислительных систем, которая связана с построением и применением искусственных нейронных сетей (ИНС). В течение последнего десятилетия данная тематика завоевывает все большую популярность, ей посвящается значительное количество современных научных публикаций, например, монографии Галушкина А. И. ([5]), Осовского С. ([32]), Терехова В. А., Ефимова Д. В. и Тюкина И. Ю. ([39]), работы зарубежных авторов [57], [62], [67], [68]. Популярность тематики нейронных сетей в значительной степени связана с тем, что модели, разработанные в ее рамках, все более серьезно рассматриваются в качестве методологического базиса для создания сверхскоростных технических устройств параллельной обработки информации. Во второй части четвертой главы дано краткое описание биологических основ функционирования нейронов и нейронных сетей, рассмотрены некоторые подходы к описанию искусственных нейронных сетей. Основу функционирования нейронных сетей составляют алгоритмы обучения, позволяющие оптимизировать их весовые коэффициенты. В качестве алгоритмов обучения нейронных сетей могут быть успешно использованы развитые в настоящей работе алгоритмы. В качестве примера применения представленных рандомизированных алгоритмов рассмотрена задача обучения нейронной сети Хебба-Хопфилда, и предложен метод ее решения, использующий представленные в третьей главе рекуррентные рандомизированные алгоритмы самообучения.
Заключение
На защиту выносятся следующие результаты:
1. Метод последовательного проектирования, предназначенный для нахождения проекции элемента гильбертова пространства на некоторое подпространство через проекции этого элемента на подпространства более низкой размерности (п. 2.4.1).
2. Обоснование сходимости метода последовательного проектирования (лемма 2) и условия сходимости последовательных проекций к ортогональной проекции заданного элемента на подпространство, являющееся замкнутой линейной оболочкой подпространств из заданной системы (теорема 1).
3. Явные формулы для расчета коэффициентов восстанавливающей функции при решении задачи среднеквадратичной аппроксимации методом последовательного проектирования (п. 2.4.2, леммы 4,5).
4. Рандомизированные алгоритмы стохастической оптимизации предназначенные для решения задачи самообучения (п. 3.1).
5. Достаточные условия состоятельности оценок рандомизированных алгоритмов стохастической аппроксимации (теорема 2).
1. Акмаев В. Р., Фомин В. Н. Кусочно-параметрическая аппроксимация непрерывных функций. // Деп. в ВИНИТИ, N 481-В-96. 16 с.
2. Альберт А. Регрессия, псевдоинверсия и рекуррентное оценивание. М.: Наука, 1977. 223 с.
3. Буцев А. ВПервозванский А. А. Локальная аппроксимация на искусственных нейросетях // Автоматика и телемеханика. 1995. N 9. С. 127-136.
4. Галушкин А. И. Теория нейронных сетей. Книга 1. М.: ИПРЖР, 2000. 416 с.
5. Граничин О. Н. Алгоритм стохастической аппроксимации с возмущением на входе для идентификации статического нестационарного дискретного объекта // Вестн. ЛГУ. Сер. 1. 1988. Вып. 3. С. 92-93.
6. Граничин О. Н. Об одной стохастической рекуррентной процедуре при зависимых помехах в наблюдении, использующей на входе пробные возмущения // Вестн. ЛГУ. Сер. 1. 1989. Вып. 1. С. 19-21.
7. Граничин О. Я. Стохастическая аппроксимация с возмущением на входе при зависимых помехах наблюдения // Вестн. ЛГУ. 1989. Сер. 1. Вып. 4. С. 27-31.
8. Граничин О. Н. Процедура стохастической аппроксимации с возмущением на входе // Автоматика и телемеханика. 1992. N 2. С. 97-104.
9. Граничин О. Н. Оценивание параметров линейной регрессии при произвольных помехах // Автоматика и телемеханика. 2002. N 1. С. 30-41.
10. Граничим, О. Н. Рандомизированные алгоритмы стохастической аппроксимации при произвольных помехах // Автоматика и телемеханика. 2002. N 2. С. 44-55.
11. Граничин О. Н. Неминимаксная фильтрация при неизвестных ограниченных помехах в наблюдениях j j Автоматика и телемеханика.2002. N 9. С. 125-133.
12. Граничин О. Н., Поляк Б. Т. Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах. М.: Наука,2003. 291 с.
13. Гелиг А. X. Об одном L-оптимальном алгоритме обучения опознающих систем // Вычислительная техника и вопросы кибернетики. Вып. 5. Л., 1968. С. 74-79.
14. Гулъчак О. А., Фомин В. Н. Задача аппроксимации функции в теории распознавания образов. 4.1. Метод последовательного проектирования и персептронная реализация алгоритмов аппроксимации // Деп. в ВИНИТИ, N 1063-В-99. 32 с.
15. Гулъчак О. А., Фомин В. Н. Задача аппроксимации функции в теории распознавания образов. 4.2. Нейроподобные системы распознавания // Деп. в ВИНИТИ, N 1817-В-99. 25 с.
16. Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976. 511 с.
17. Ермаков С. М., Жиглявский А. А. Математическая теория оптимального эксперимента. М.: Наука, 1987. 320 с.
18. Жилинскас А. Глобальная оптимизация. Вильнюс: Мокслас, 1986. 165 с.
19. Загоруйко П. Г. Методы распознавания и их применение. М., 1972. 206 с.
20. Ивахненко А. Г., Зайченко Ю. П., Димитров В. Д. Принятие решений на основе самоорганизации. М.: Советское радио, 1976. 280 с.
21. Измакова О. А. Рандомизированные алгоритмы самообучения для нейронных сетей. // Электронный журнал "Дифференциальные уравнения и процессы управления", N 2, 2005 г. С. 122-142.
22. Измакова О. А. Рандомизированные алгоритмы самообучения для настройки ассоциативных нейронных сетей. // В сб. "Стохастическая оптимизация в информатике" под ред. О. Н. Граничина. Изд-во С.-Петерб. ун-та. 2005. С. 81-102.
23. Измакова О. А., Сысоев С. С. Алгоритм стохастической оптимизации с возмущением на входе в задаче самообучения. // Труды Международной школы-семинара "Адаптивные роботы — 2004". М.-СПб. 2004. С. 49-52.
24. Катковник В. Я. Линейные оценки и стохастические задачи оптимизации. М.: Наука, 1976. 488 с.
25. Катковник В. Я. Непараметрическая идентификация и сглаживание данных. М.: Наука, 1985. 336 с.
26. Козинец Б. Н. Рекуррентный алгоритм разделениядвух множеств. // В кн.: Алгоритм обучения распознаванию образов. М., 1973. С. 4349.
27. Лиховидов В. Н., Фомин В. Н. Математическая постановка задачи классификации изображений // Вестник ЛГУ. Сер.1. 1976. Вып.З (N 19). С. 61-68.
28. Лоэв М. Теория вероятностей. М.: ИЛ, 1962. 719 с.
29. МакКаллок У., Питтс В. Логическое исчисление идей, относящихся к нервной активности // Сб. "Автоматы", пер. с англ.: Изд-во иностр. лит, 1959.
30. Надарая Э. А. Об оценке регрессии // Теория вероятностей и ее применения. 1965. Т. 10. С. 199-203.
31. Осовский С. Нейронные сети для обработки информации // пер. с польского И. Д. Рудинского. М.: Финансы и статистика, 2002. 344 с.
32. Перцептрон — система распознавания образов. Под общ. ред. А. Г. Ивахненко. Киев, 1975. 418 с.
33. Поляк Б. Т. Введение в оптимизацию. М.: Наука, 1983. 384 с.
34. Поляк Б. Т., Цибаков А. Б. Оптимальные порядки точности поисковых алгоритмов стохастической аппроксимации // Проблемы передачи информации. 1990. N 2. С. 45-53.
35. Растригин JI. А. Адаптация сложных систем. Рига: Зинатне, 1981. 386 с.
36. Розенблатт Ф. Принципы нейродинамики (персептроны и теория механизмов мозга). М. 1965, 480 с.
37. Розенблатт Ф. Стратегические подходы к исследованию моделей мозга. — В кн.: Принципы самоорганизации. М, 1966. С. 469-490.
38. Терехов В. А., Ефимов Д. В., Тюкин И. Ю. Нейросетевые системы управления. СПб: Изд-во Спб ун-та, 1999. 265 с.
39. Тимофеев А. В. Методы обучения и самоорганизации полиномиальных нейронных сетей в задачах распознавания образов.// Труды 11-ой международной конференции "Математические методы распознавания образов". Пущино, 2003.
40. Тимофеев А. В. Методы высококачественного управления, интеллектуализации и функциональной диагностики автоматических систем. // "Мехатроника, автоматизация и управление", 2003. С. 13-17.
41. Тимофеев А. В. Эволюция нейроинформатики: от персептронов к квантовым нейрокомпьютерам // Информ. технологии, N 2, 2003. С. 51-55.
42. Фомин В. Н. Математическая теория обучаемых опознающих систем. JL: Изд-во Ленингр. ун-та, 1976. 236 с.
43. Фомин В. Н. Рекуррентное оценивание и адаптивная фильтрация. М.: Наука, 1984. 288 с.
44. Фомин В. Н.} Измакова О. А. Об одном алгоритме распознавания образов. // Труды Первой международной конференции по мехатро-нике и робототехнике. СПб, 2000. С. 355-359.
45. Фомин В. Н., Фрадков A. Л., Якубович В. А. Адаптивное управление динамическими объектами. М.: Наука, 1981. 448 с.
46. Фукунага К. Статистическая теория распознавания образов. М.: Мир, 1979. 367 с.
47. Цыпкин Я. 3. Основы теории обучающихся систем. М.: Наука, 1970. 252 с.
48. Цыпкин Я. 3., Келъманс Г. К. Рекуррентные алгоритмы самообучения. // Изв. АН СССР. Техническая кибернетика, 1967, N 5. С. 78-87.
49. Шлезингер М. И. О самопроизвольном различении образов // Сб. Читающие автоматы. Киев, Наукова думка, 1965. С. 24-34.
50. Эйкхофф 77. Основы идентификации систем управления. М.: Мир, 1975. 683 с.
51. Якубович В. А. Машины, обучающиеся распознаванию образов //В кн.: Методы вычислений, вып. 2. Д., 1963. С. 95-131.
52. Якубович В. А. Некоторые общие теоретические принципы построения обучаемых опознающих систем // В кн.: Вычислительная техника и вопросы программирования, вып. 4, JL, 1965. С. 3-72.
53. Якубович В. А. Рекуррентные конечно-сходящиеся алгоритмы решения систем неравенств // Доклады АН СССР. 1966. Т. 166. N 6. С. 1308-1311.
54. Blum J. R Multidimensional stochastic approximation // Ann.Math.Statist. 1954. Vol.9. P.737-744.
55. Granichin 0. N. Linear regression and filtering under nonstandard assumptions (Arbitrary noise) // Trans on AC, 2004, vol. 49, oct., N 10, P. 1830-1835.
56. Haykin 5., Neural Networks: A Comprehensive Foundation. New York: Macmillan, 1984.
57. Kiefer J., Wolfowitz J. Statistical estimation on the maximum of a regression function // Ann. Math. Statist. 1952. Vol.23. P.462-466.
58. Likhovidov V. Variational approach to unsupervised learning algorithms of neural networks // Neural Netw.(USA). 1997. Vol. 10. N 2. P. 273-289.
59. Lippmann P. R. An introduction to computing with neural nets. IEEE ASSP Magazine, 1987, April, 4-22.
60. Polyak В. Т., Tsybakov A. B. On stochastic approximation with arbitrary noise (the KW case) / In: Topics in Nonparamctric Estimation. Khasminskii R.Z. ed. // Advances in Soviet Mathematics, Amer. Math. Soc. Providence. 1992. N 12. p. 107-113.
61. Poznyak A. S., Sanches E. N., Wen Yu Dynamic Neural Networks for Nonlinear Control: Identification, State Estimation and Trajectory Tracking. World Scientific, 2001.
62. Robbins H., Siegmund D., A convergence theorem for nonnegative almost super-marlingales and some applications // In: Optimizing Methods in Statistics, J.S.Rustagi ed. Academic Press, NY. 1971. P. 233-257.
63. Spall J. C., A stochastic approximation technique for generating maximum likelihood parameter estimates j j In: Proceedings of the American Control Conference. 1987. P. 1161-1167.
64. Spall J. C. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation / / IEEE Transactions on Automatic Control, 1992, vol. 37. P. 332-341.
65. Spall J. C. An overview of the simultaneous perturbation method for efficient optimization // Johns Hopkins APL Technical Digest, 1998, vol. 19. P. 482-492.
66. Vidyasagar M. A Theory of Learning and Generalization with Applications to Neural Networks and Control Systems. Springer, London, 1997.
67. White H. Artifical Neural Networks. Oxford: Blackwell, UK, 1992.
