Введение в нейронные сети

ОГЛАВЛЕНИЕ ВВЕДЕНИЕ ГЛАВА 1. ИСКУССТВЕННЫЕ НЕЙРОННЫЕ СЕТИ

1.1 Возникновение искусственных нейронных сетей

1.2 Основные виды искусственных нейронных сетей

1.3 Применение искусственных нейронных сетей ГЛАВА 2. ПЕРСЕПТРОН РОЗЕНБЛАТТА

2.1 Задачи, решаемые при помощи Персептрона Розенблатта

2.2 Методика обучения Персептрона Розенблатта

2.3 Пример использования Персептрона Розенблатта ГЛАВА 3. КОМПЬЮТЕРНАЯ ИМИТАЦИОННАЯ МОДЕЛЬ ПЕРСЕПТРОНА РОЗЕНБЛАТТА

3.1 Ограничения, накладываемые на имитационную модель

3.2 Схема имитационной модели Персептрона Розенблатта в среде Delphi

3.3 Описание сеанса работы с компьютерной программой ЗАКЛЮЧЕНИЕ БИБЛИОГРАФИЧЕСКИЙ СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ ПРИЛОЖЕНИЕ. Исходные коды программы Perseptron

ВВЕДЕНИЕ

Человеческий мозг содержит триллионы особых клеток, называемых нейронами. Все они связаны друг с другом сотнями триллионов нервных нитей, называемых синапсами. Получившаяся таким образом огромная сеть нейронов отвечает за все те явления, которые мы привыкли называть мыслями и эмоциями, а также за все многообразие сенсомоторных функций [6,9,16,18,19,24,27,28,29]. До сих пор нет четкого ответа на вопрос, каким образом биологическая нейросеть осуществляет управление всеми этими процессами, хотя уже исследовано достаточно много аспектов ее работы. Из-за технической невозможности создания биологических нейронных сетей, в настоящее время создаются их неодушевленные аналоги — искусственные нейронные сети [6,7,9,12,13,20,21,22,25,26,27,28,29]. Актуальность исследований в этом направлении подтверждается массой различных применений нейронных сетей. Это автоматизация процессов распознавания образов, адаптивное управление, аппроксимация функционалов, прогнозирование, создание экспертных систем, организация ассоциативной памяти и многие другие приложения. С помощью нейронных сетей можно, например, предсказывать показатели биржевого рынка, выполнять распознавание оптических или звуковых сигналов, создавать самообучающиеся системы, способные управлять автомашиной при парковке или синтезировать речь по тексту [4,9,15,20,27,29].

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

Возвращаясь к общим чертам, присущим всем нейронным сетям следует отметить принцип параллельной обработки сигналов, который достигается путем объединения большого числа нейронов в так называемые слои и соединения определенным образом нейронов различных слоев, а также, в некоторых конфигурациях, и нейронов одного слоя между собой, причем обработка взаимодействия всех нейронов ведется послойно [6,13,15,20,22,29].

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

Широкий круг задач, решаемый нейронными сетями, не позволяет в настоящее время создавать универсальные, мощные сети, вынуждая разрабатывать специализированные нейронные сети, функционирующие по различным алгоритмам. Тип используемой нейросети во много диктуется поставленной задачей. Так, для задачи классификации удобными могут оказаться многослойный персептрон [6,9,20,28,29] и сеть Липпмана-Хемминга [13,20,29]. Персептрон также применим и для задач идентификации систем и прогноза. При решении задач категоризации потребуются карта Кохонена [14,28,29], архитектура встречного распространения [20,27,28,29] или сеть с адаптивным резонансом [28,29]. Задачи нейроматематики обычно решаются с использованием различных модификаций модели Хопфилда [6,9,13,21,27,28,29]. На выбор конкретной нейронной сети может повлиять наличие или отсутствие соответствующих задаче программ.

Объектом данной дипломной работы являются нейронные сети.

Предметом данной дипломной работы является искусственная нейронная сеть на базе классической модели нейрона.

Целью данной дипломной работы является разработка элективного курса по теме «Введение в нейронные сети» .

В соответствии с объектом, предметом и целью в данной дипломной работе были успешно решены следующие задачи:

1. Изучена история возникновения нейронных сетей.

2. Приведены архитектуры простейших нейронных сетей.

3. Рассмотрены прикладные программы для создания моделей искусственных нейронных сетей.

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

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

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

В третьей главе дипломной работы рассматривается процесс разработки имитационной модели Персептрона Роземблатта.

В заключении сделаны выводы и подведен итог проделанной работы.

Приложение содержит разработанные автором дипломной работы исходный текст компьютерной программы

ГЛАВА 1. ИСКУСТВЕННЫЕ НЕЙРОНЫЕ СЕТИ

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

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

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

Параллельно с прогрессом в нейроанатомии и нейрофизиологии психологами были созданы модели человеческого обучения. Одной из таких моделей, оказавшейся наиболее плодотворной, была модель Д. Хэбба, который в 1949 г. предложил закон обучения, явившийся стартовой точкой для алгоритмов обучения искусственных нейронных сетей. Дополненный сегодня множеством других методов он продемонстрировал ученым того времени, как сеть нейронов может обучаться.

И все же, что такое искусственные нейронные сети? Что они могут делать? Как они работают? Как их можно использовать? Эти и множество подобных вопросов задают специалисты из разных областей. Найти вразумительный ответ нелегко Наиболее емким представляется следующее определение искусственных нейронных сетей, как адаптивной машины, данное в [2]:

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

— знание приобретается сетью в процессе обучения;

— для сохранения знания используются силы межнейронных соединений, называемые также синаптическими весами.

Имеется много впечатляющих демонстраций возможностей искусственных нейронных сетей: сеть научили превращать текст в фонетическое представление, которое затем с помощью уже иных методов превращалось в речь [3]; другая сеть может распознавать рукописные буквы [1]; сконструирована система сжатия изображений, основанная на нейронной сети. Все они используют сеть обратного распространения — наиболее успешный, по-видимому, из современных алгоритмов. Обратное распространение, независимо предложенное в трех различных работах [5, 6, 7,], является систематическим методом для обучения многослойных сетей, и тем самым преодолевает ограничения, указанные Минским.

Обратное распространение не свободно от проблем. Прежде всего нет гарантии, что сеть может быть обучена за конечное время. Много усилий, израсходованных на обучение, пропадает напрасно после затрат большого количества машинного времени. Когда это происходит, попытка обучения повторяется — без всякой уверенности, что результат окажется лучше. Нет также уверенности, что сеть обучится наилучшим возможным образом.

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

Мы имеем дело с областью, продемонстрировавшей свою работоспособность, имеющей уникальные потенциальные возможности, много ограничений и множество открытых вопросов. Такая ситуация настраивает на умеренный оптимизм. Авторы склонны публиковать свои успехи, но не неудачи, создавая тем самым впечатление, которое может оказаться нереалистичным. Те, кто ищет капитал, чтобы рискнуть и основать новые фирмы, должны представить убедительный проект последующего осуществления и прибыли. Существует, следовательно, опасность, что искусственные нейронные сети начнут продавать раньше, чем придет их время, обещая функциональные возможности, которых пока невозможно достигнуть. Если это произойдет, то область в целом может пострадать от потери кредита доверия и вернется к застойному периоду семидесятых годов. Для улучшения существующих сетей требуется много основательной работы. Должны быть развиты новые технологии, улучшены существующие методы и расширены теоретические основы, прежде чем данная область сможет полностью реализовать свои потенциальные возможности.

1.2 Основные виды искусственных нейронных сетей

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

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

Несмотря на сделанные предупреждения, полезно все же знать кое-что о нервной системе млекопитающих, так как она успешно решает задачи, к выполнению которых лишь стремятся искусственные системы.

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

На рисунке 1.1 показана структура пары типичных биологических нейронов. Дендриты идут от тела нервной клетки к другим нейронам, где они принимают сигналы в точках соединения, называемых синапсами. Принятые синапсом входные сигналы подводятся к телу нейрона. Здесь они суммируются, причем одни входы стремятся возбудить нейрон, другие — воспрепятствовать его возбуждению. Когда суммарное возбуждение в теле нейрона превышает некоторый порог, нейрон возбуждается, посылая по аксону сигнал другим нейронам. У этой основной функциональной схемы много усложнений и исключений, тем не менее большинство искусственных нейронных сетей моделируют лишь эти простые свойства.

Рисунок 1.1 — Биологический нейрон

Искусственный нейрон имитирует в первом приближении свойства биологического нейрона. На вход искусственного нейрона поступает некоторое множество сигналов, каждый из которых является выходом другого нейрона. Каждый вход умножается на соответствующий вес, аналогичный синаптической силе, и все произведения суммируются, определяя уровень активации нейрона. На рисунке 1.2 представлена модель, реализующая эту идею. Хотя сетевые парадигмы весьма разнообразны, в основе почти всех их лежит эта конфигурация. Здесь множество входных сигналов, обозначенных x1, x2,…, xn, поступает на искусственный нейрон. Эти входные сигналы, в совокупности обозначаемые вектором X, соответствуют сигналам, приходящим в синапсы биологического нейрона. Каждый сигнал умножается на соответствующий вес w1, w2,…, wn, и поступает на суммирующий блок, обозначенный У. Каждый вес соответствует «силе» одной биологической синаптической связи. (Множество весов в совокупности обозначается вектором W.) Суммирующий блок, соответствующий телу биологического элемента, складывает взвешенные входы алгебраически, создавая выход, который мы будем называть NET. В векторных обозначениях это может быть компактно записано следующим образом

NET = XW. (1.1)

Рисунок 1.2 — Искусственный нейрон

Сигнал NET далее, как правило, преобразуется активационной функцией F и дает выходной нейронный сигнал OUT. Активационная функция может быть обычной линейной функцией

OUT = K (NET), (1.2)

где К — постоянная, пороговой функции

OUT = 1, если NET > T,

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

Рисунок 1.3 — Искусственный нейрон с активационной функцией

На рисунке 1.3 блок, обозначенный F, принимает сигнал NET и выдает сигнал OUT. Если блок F сужает диапазон изменения величины NET так, что при любых значениях NET значения OUT принадлежат некоторому конечному интервалу, то F называется «сжимающей» функцией. В качестве «сжимающей» функции часто используется логистическая или «сигмоидальная» (S-образная) функция, показанная на рисунке 1.4. Эта функция математически выражается как F (x) = 1/(1 + е-x). Таким образом

. (1.3)

Рисунок 1.4 — Сигмоидальная логистическая функция

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

. (1.4)

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

OUT = th (x). (1.5)

Как показано на рисунке 1.5 подобно логистической функции гиперболический тангенс является S-образной функцией, но он симметричен относительно начала координат, и в точке NET = 0 значение выходного сигнала OUT равно нулю. В отличие от логистической функции гиперболический тангенс принимает значения различных знаков, что оказывается выгодным для ряда сетей.

Рисунке 1.5 — Функция гиперболического тангенса

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

Рисунок 1.6 — Однослойная нейронная сеть

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

Удобно считать веса элементами матрицы W. Матрица имеет т строк и п столбцов, где m — число входов, а n — число нейронов. Например, w2,3 — это вес, связывающий третий вход со вторым нейроном. Таким образом, вычисление выходного вектора N, компонентами которого являются выходы OUT нейронов, сводится к матричному умножению N = XW, где N и Х — векторы-строки.

Более крупные и сложные нейронные сети обладают, как правило, и большими вычислительными возможностями.

Многослойные сети могут образовываться каскадами слоев. Выход одного слоя является входом для последующего слоя. Подобная сеть показана на рисунке 1.7 и снова изображена со всеми соединениями.

Рисунок 1.7 — Двухслойная нейронная сеть

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

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

1.3 Применение искусственных нейронных сетей

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

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

Начнем с систем, состоящих из одного элемента.

Даже системы из одного адаптивного сумматора находят очень широкое применение. Вычисление линейных функций необходимо во многих задачах. Вот неполный перечень «специальностей» адаптивного сумматора:

— линейная регрессия и восстановление простейших закономерностей [13−14];

— линейная фильтрация и адаптивная обработка сигналов [15];

— линейное разделение классов и простейшие задачи распознавания образов [16−18].

Задача линейной регрессии состоит в поиске наилучшего линейного приближения функции, заданной конечным набором значений: дана выборка значений вектора аргументов x1, …, xm, заданы значения функции F в этих точках: F (xi)=fi, требуется найти линейную (неоднородную) функцию (x)=(, x)+0, ближайшую к F. Чтобы однозначно поставить задачу, необходимо доопределить, что значит «ближайшую». Наиболее популярен метод наименьших квадратов, согласно которому ищется из условия

(1.6)

Необходимо особенно подчеркнуть, что метод наименьших квадратов не является ни единственным, ни наилучшим во всех отношениях способом доопределения задачи регрессии. Его главное достоинство _ квадратичность минимизируемого критерия и линейность получаемых уравнений на коэффициенты. Явные формулы линейной регрессии легко получить, минимизируя квадратичный критерий качества регрессии. Обозначим

(1.7)

Найдем производные минимизируемой функции H по настраиваемым параметрам:

(1.8)

где x_ij _ j-я координата вектора x_i.

Приравнивая частные производные H нулю, получаем уравнения, из которых легко найти все j (j=0,…, n). Решение удобно записать в общем виде, если для всех i=1,…, m обозначить и рассматривать n+1-мерные векторы данных xi и коэффициентов. Тогда

Обозначим p _n+1-мерный вектор с координатами

Q — матрицу размером (n+1)(n+1) с элементами

.

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

(x)=(, x), =Q^_1p. (1.9)

Приведем это решение в традиционных обозначениях математической статистики. Обозначим M_о среднее значение j-й координаты векторов исходной выборки:

.

Пусть M _ вектор с координатами M_о. Введем также обозначение s_j для выборочного среднеквадратичного отклонения:

.

Величины s_j задают естественный масштаб для измерения j-х координат векторов x. Кроме того, нам потребуются величина s_f и коэффициенты корреляции f с j-ми координатами векторов x _ r_fj:

(1.10)

Вернемся к n-мерным векторам данных и коэффициентов. Представим, что векторы сигналов проходят предобработку _ центрирование и нормировку и далее мы имеем дело с векторами y_i

Это, в частности, означает, что все рассматриваемые координаты вектора x имеют ненулевую дисперсию, т. е. постоянные координаты исключаются из рассмотрения _ они не несут полезной информации. Уравнения регрессии будем искать в форме: (y)=(, y)+0. Получим

₀=M_f, =s_fR^_1R_f, (1.11)

где R_f _ вектор коэффициентов корреляции f с j-ми координатами векторов x, имеющий координаты r_fj, R _ матрица коэффициентов корреляции между координатами вектора данных:

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

В рамках первого подхода рассмотрим, как будет изменяться при добавлении нового вектора данных. В первом порядке теории возмущений найдем изменение вектора коэффициента при изменении вектора p и матрицы Q:

Пусть на выборке вычислены p, Q, Q₁. При получении нового вектора данных x_m+1 и соответствующего значения F (x_m+1)=f _m+1 имеем

(1.12)

где _ ошибка на векторе данных x_m+1 регрессионной зависимости, полученной на основании выборки .

Пересчитывая по приведенным формулам p, Q, Q₁ и после каждого получения данных, получаем процесс, в котором последовательно уточняются уравнения линейной регрессии. И требуемый объем памяти, и количество операций имеют порядок n₂ _ из-за необходимости накапливать и модифицировать матрицу Q₁. Конечно, это меньше, чем потребуется на обычное обращение матрицы Q на каждом шаге, однако следующий простой алгоритм еще экономнее. Он вовсе не обращается к матрицам Q, Q₁ и основан на уменьшении на каждом шаге величины _ квадрата ошибки на векторе данных x_m+1 регрессионной зависимости, полученной на основании выборки .

Вновь обратимся к формуле (1.10) и будем рассматривать n+1-мерные векторы данных и коэффициентов. Обозначим. Тогда

. (1.13)

Последняя элементарная формула столь важна в теории адаптивных сумматоров, что носит «именное название» _ формула Уидроу. «Обучение» адаптивного сумматора методом наискорейшего спуска состоит в изменении вектора коэффициентов в направлении антиградиента ₂: на каждом шаге к добавляется hx, где h _ величина шага.

Если при каждом поступлении нового вектора данных x изменять указанным образом, то получим последовательную процедуру построения линейной аппроксимации функции F (x). Такой алгоритм обучения легко реализуется аппаратными средствами (изменение веса связи _j есть произведение прошедшего по ней сигнала x_j на ошибку и на величину шага). Возникает, однако, проблема сходимости: если h слишком мало, то сходимость будет медленной, если же слишком велико, то произойдет потеря устойчивости и сходимости не будет вовсе.

Задача четкого разделения двух классов по обучающей выборке ставится так: имеется два набора векторов x₁, …, x_m и y₁,…, y_m. Заранее известно, что x_i относится к первому классу, а y_i — ко второму. Требуется построить решающее правило, то есть определить такую функцию f (x), что при f (x)>0 вектор x относится к первому классу, а при f (x)<0 _ ко второму.

Координаты классифицируемых векторов представляют собой значения некоторых признаков (свойств) исследуемых объектов.

Эта задача возникает во многих случаях: при диагностике болезней и определении неисправностей машин по косвенным признакам, при распознавании изображений и сигналов и т. п.

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

— искать дополнительные признаки, позволяющие разделить классы;

— примириться с неизбежностью ошибок, назначить за каждый тип ошибок свой штраф (c12 — штраф за то, что объект первого класса отнесен ко второму, c21 — за то, что объект второго класса отнесен к первому) и строить разделяющее правило так, чтобы минимизировать математическое ожидание штрафа;

— перейти к нечеткому разделению классов — строить так называемые «функции принадлежности» f1(x) и f2(x) _ fi (x) оценивает степень уверенности при отнесении объекта к i-му классу (i=1,2), для одного и того же x может быть так, что и f1(x)>0, и f2(x)>0.

Линейное разделение классов состоит в построении линейного решающего правила _ то есть такого вектора и числа ₀ (называемого порогом), что при (x,)>₀ x относится к первому классу, а при (x,)<₀ — ко второму.

Поиск такого решающего правила можно рассматривать как разделение классов в проекции на прямую. Вектор задает прямую, на которую ортогонально проектируются все точки, а число ₀ _ точку на этой прямой, отделяющую первый класс от второго.

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

= (y₁+ y₂+…+y_m)/m _(x₁+ x₂+…+ x _n)/n. (1.14)

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

= ((y₁+ y₂+…+y_m)/m _(x₁+ x₂+…+ x _n)/n)/(y₁+ y₂+…+y_m)/m _(x₁+ x₂+…+ +x_n)/n.

Выбор ₀ может производиться из различных соображений. Простейший вариант _ посередине между центрами масс выборок:

₀= (((y₁+ y₂+…+y_m)/m,) + ((x₁+ x₂+…+ x _n)/n,))/2.

Более тонкие способы построения границы раздела классов ₀ учитывают различные вероятности появления объектов разных классов, и оценки плотности распределения точек классов на прямой. Чем меньше вероятность появления данного класса, тем более граница раздела приближается к центру тяжести соответствующей выборки.

Можно для каждого класса построить приближенную плотность вероятностей распределения проекций его точек на прямую (это намного проще, чем для многомерного распределения) и выбирать ₀, минимизируя вероятность ошибки. Пусть решающее правило имеет вид: при (x,)>₀ x относится к первому классу, а при (x,)<₀ _ ко второму. В таком случае вероятность ошибки будет равна

где p₁, p₂ _ априорные вероятности принадлежности объекта соответствующему классу,

1(), 2() _ плотности вероятности для распределения проекций точек x в каждом классе.

Приравняв нулю производную вероятности ошибки по 0, получим: число 0, доставляющее минимум вероятности ошибки, является корнем уравнения:

p₁₁() = p₂₂(), (1.15)

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

Если принять гипотезу о нормальности распределений:

то для определения ₀ получим:

Если это уравнение имеет два корня y=₁, ₂, (₁<₂) то наилучшим решающим правилом будет: при ₁<(x,)<₂ объект принадлежит одному классу, а при ₁>(x,) или (x,)>₂ _ другому (какому именно, определяется тем, которое из произведений p_ii() больше). Если корней нет, то оптимальным является отнесение к одному из классов. Случай единственного корня представляет интерес только тогда, когда ₁=₂. При этом уравнение превращается в линейное и мы приходим к исходному варианту _ единственной разделяющей точке ₀.

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

Если сразу ставить задачу об оптимальном разделении многомерных нормальных распределений, то получим, что наилучшей разделяющей поверхностью является квадрика (на прямой типичная «квадрика» _ две точки). Предполагая, что ковариационные матрицы классов совпадают (в одномерном случае это предположение о том, что ₁=₂), получаем линейную разделяющую поверхность. Она ортогональна прямой, соединяющей центры выборок не в обычном скалярном произведении, а в специальном:, где _ общая ковариационная матрица классов.

Важная возможность усовершенствовать разделяющее правило состоит с использовании оценки не просто вероятности ошибки, а среднего риска: каждой ошибке приписывается «цена» c_i и минимизируется сумма c₁p₁₁()+c₂p₂₂(). Ответ получается практически тем же (всюду p_i заменяются на c_ip_i), но такая добавка важна для многих приложений.

Требование безошибочности разделяющего правила на обучающей выборке принципиально отличается от обсуждавшихся критериев оптимальности. На основе этого требования строится персептрон Розенблатта.

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

(x_i,)>₀ (i=1,…, n)

(y_j ,)<₀ (j=1,…, m).

Здесь _xi (i=1,., n) — векторы из обучающей выборки, относящиеся к первому классу, а y_j (j=1,., n) — ко второму.

Удобно переформулировать задачу. Увеличим размерности всех векторов на единицу, добавив еще одну координату _₀ к, x₀ =1 — ко всем x и y₀ =1 _ ко всем y. Сохраним для новых векторов прежние обозначения — это не приведет к путанице.

Наконец, положим z_i =x_i (i=1,…, n), z_j = _y_j (j=1,…, m).

Тогда получим систему n+m неравенств

(z_i,)>0 (i=1,…, n+m),

которую будем решать относительно. Если множество решений непусто, то любой его элемент порождает решающее правило, безошибочное на обучающей выборке.

Итерационный алгоритм решения этой системы чрезвычайно прост. Он основан на том, что для любого вектора x его скалярный квадрат (x, x) больше нуля. Пусть _ некоторый вектор, претендующий на роль решения неравенств (z_i,)>0 (i=1,…, n+m), однако часть из них не выполняется. Прибавим те zi, для которых неравенства имеют неверный знак, к вектору и вновь проверим все неравенства (z_i,)>0 и т. д. Если они совместны, то процесс сходится за конечное число шагов. Более того, добавление z_i к можно производить сразу после того, как ошибка ((z_i,)<0) обнаружена, не дожидаясь проверки всех неравенств _ и этот вариант алгоритма тоже сходится.

Перейдем от одноэлементных систем к нейронным сетям. Пусть _ij _ вес связи, ведущей от j-го нейрона к i-му (полезно обратить внимание на порядок индексов). Для полносвязных сетей определены значения _ij при всех i, j, для других архитектур связи, ведущие от j-го нейрона к i-му для некоторых i, j не определены. В этом случае положим _ij=0.

В данном разделе речь пойдет в основном о полносвязных сетях. Пусть на выходах всех нейронов получены сигналы x_j (j-номер нейрона). Обозначим x вектор этих выходных сигналов. Прохождение вектора сигналов x через сеть связей сводится к умножению матрицы (_ij) на вектор сигналов x. В результате получаем вектор входных сигналов нелинейных элементов нейронов:

.

Это соответствие «прохождение сети умножение матрицы связей на вектор сигналов» является основой для перевода обычных численных методов на нейросетевой язык и обратно. Практически всюду, где основной операцией является умножение матрицы на вектор, применимы нейронные сети. С другой стороны, любое устройство, позволяющее быстро осуществлять такое умножение, может использоваться для реализации нейронных сетей. В частности, вычисление градиента квадратичной формы может осуществляться полносвязной сетью с симметричной матрицей связей: (). Соответственно, можно методом наискорейшего спуска искать точку минимума многочлена второго порядка. Пусть задан такой многочлен:. Его градиент равен. Этот вектор может быть получен при прохождении вектора x через сеть с весами связей при условии, что на входной сумматор каждого нейрона по дополнительной связи веса b подается стандартный единичный сигнал. Зададим теперь функционирование сети формулой

(1.16)

Каждый (j-й) нейрон имеет входные веса для связей с другими нейронами (ij), вес для постоянного единичного входного сигнала и вес для связи нейрона с самим собой. Выбор шага h>0 может вызвать затруднение т.к. он зависит от коэффициентов минимизируемого многочлена. Есть, однако, простое решение: в каждый момент дискретного времени T выбирается свое значение. Достаточно, чтобы шаг стремился со временем к нулю, а сумма шагов _ к бесконечности (например,).

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

Решение системы линейных уравнений сводится к минимизации многочлена

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

Небольшая модификация позволяет вместо безусловного минимума многочлена второго порядка P искать точку условного минимума с условиями, то есть точку минимума P в ограничении на аффинное многообразие, параллельное некоторым координатным плоскостям. Для этого вместо формулы

следует использовать:

(1.17)

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

Предположим, что получаемые в ходе испытаний векторы данных подчиняются многомерному нормальному распределению:

где Mx _ вектор математических ожиданий координат, ковариационная матрица, n _ размерность пространства данных,

.

Напомним определение матрицы :

где M _ символ математического ожидания, нижний индекс соответствует номеру координаты.

В частности, простейшая оценка ковариационной матрицы по выборке дает:

где m _ число элементов в выборке, верхний индекс j _ номер вектора данных в выборке, верхний индекс Т означает транспонирование, а _ произведение вектора-столбца на вектор-строку (тензорное произведение).

Пусть у вектора данных x известно несколько координат:. Наиболее вероятные значения неизвестных координат должны доставлять условный максимум показателю нормального распределения _ многочлену второго порядка (при условии). Эти же значения будут условными математическими ожиданиями неизвестных координат при заданных условиях.

Таким образом, чтобы построить сеть, заполняющую пробелы в данных, достаточно сконструировать сеть для поиска точек условного минимума многочлена при условиях следующего вида:. Матрица связей Q выбирается из условия, где _ ковариационная матрица (ее оценка по выборке).

На первый взгляд, пошаговое накопление по мере поступления данных требует слишком много операций _ получив новый вектор данных требуется пересчитать оценку, а потом вычислить. Можно поступать и по-другому, воспользовавшись формулой приближенного обрашения матриц первого порядка точности:

Если же добавка имеет вид, то

(1.18)

Заметим, что решение задачи (точка условного минимума многочлена) не меняется при умножении Q на число. Поэтому полагаем:

где 1 _ единичная матрица, >0 _ достаточно малое число, _ k+1-й вектор данных, _ среднее значение вектора данных, уточненное с учетом :

=

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

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

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

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

До сих пор речь шла о минимизации положительно определенных квадратичных форм и многочленов второго порядка. Однако самое знаменитое приложение полносвязных сетей связано с увеличением значений положительно определенных квадратичных форм. Речь идет о системах ассоциативной памяти [4−7,9,10,12].

Предположим, что задано несколько эталонных векторов данных и при обработке поступившего на вход системы вектора x требуется получить на выходе ближайший к нему эталонный вектор. Мерой сходства в простейшем случае будем считать косинус угла между векторами _ для векторов фиксированной длины это просто скалярное произведение. Можно ожидать, что изменение вектора x по закону

(1.19)

где h _ малый шаг, приведет к увеличению проекции x на те эталоны, скалярное произведение на которые больше.

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

(1.20)

где верхними индексами обозначаются номера векторов-эталонов, нижними _ координаты векторов.

Функция H называется «энергией» сети, она минимизируется в ходе функционирования. Слагаемое вводится для того, чтобы со временем возрастала проекция вектора x на те эталоны, которые к нему ближе, слагаемое обеспечивает стремление координат вектора x к. Параметр определяет соотношение между интенсивностями этих двух процессов. Целесообразно постепенно менять со временем, начиная с малых <1, и приходя в конце концов к >1.

Матрица связей построенной сети определяется функцией, так как вычисляется непосредственно при j-м нейроне без участия сети. Вес связи между i-м и j-м нейронами не зависит от направления связи и равен

. (1.21)

Эта простая формула имеет чрезвычайно важное значение для развития теории нейронных сетей. Вклад k-го эталона в связь между i-м и j-м нейронами () равен +1, если i-я и j-я координаты этого эталона имеют одинаковый знак, и равен _1, если они имеют разный знак.

В результате возбуждение i-го нейрона передается j-му (и симметрично, от j-го к i-му), если у большинства эталонов знак i-й и j-й координат совпадают. В противном случае эти нейроны тормозят друг друга: возбуждение i-го ведет к торможению j-го, торможение i-го _ к возбуждению j-го (воздействие j-го на i-й симметрично). Это правило образования ассоциативных связей (правило Хебба) сыграло огромную роль в теории нейронных сетей.

Построение отношений на множестве объектов — одна из самых загадочных и открытых для творчества областей применения искусственного интеллекта. Первым и наиболее распространенным примером этой задачи является классификация без учителя. Задан набор объектов, каждому объекту сопоставлен вектор значений признаков. Требуется разбить эти объекты на классы эквивалентности.

Для каждого нового объекта мы должны сделать два дела:

— найти класс, к которому он принадлежит;

— использовать новую информацию, полученную об этом объекте, для исправления (коррекции) правил классификации.

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

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

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

Если число классов m заранее определено, то задачу классификации без учителя можно поставить следующим образом.

Пусть {x_p } - векторы значений признаков для рассматриваемых объектов и в пространстве таких векторов определена мера их близости {x, y}. Для определенности примем, что чем ближе объекты, тем меньше. С каждым классом будем связывать его типичный объект. Далее называем его ядром класса. Требуется определить набор из m ядер y₁, y₂, … y_m и разбиение {x_p} на классы:

минимизирующее следующий критерий

(1.22)

где для каждого (i-го) класса _ сумма расстояний от принадлежащих ему точек выборки до ядра класса:

. (1.23)

Минимум Q берется по всем возможным положениям ядер и всем разбиениям {x_p}на m классов Yi.

Если число классов заранее не определено, то полезен критерий слияния классов: классы Y_i и Y_j сливаются, если их ядра ближе, чем среднее расстояние от элемента класса до ядра в одном из них.

Использовать критерий слияния классов можно так: сначала принимаем гипотезу о достаточном числе классов, строим их, минимизируя Q, затем некоторые Y_i объединяем, повторяем минимизацию Q с новым числом классов и т. д.

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

Сетевые алгоритмы классификации без учителя строятся на основе итерационного метода динамических ядер. Опишем его сначала в наиболее общей абстрактной форме. Пусть задана выборка предобработанных векторов данных {x_p}. Пространство векторов данных обозначим E. Каждому классу будет соответствовать некоторое ядро a. Пространство ядер будем обозначать A. Для каждых xE и aA определяется мера близости d (x, a). Для каждого набора из k ядер a₁,…, a_k и любого разбиения {x_p} на k классов {x_p}=P₁P₂…P_k определим критерий качества:

(1.24)

Требуется найти набор a1,…, ak и разбиение {x_p}=P₁P₂…P_k, минимизирующие D.

Шаг алгоритма разбивается на два этапа:

1-й этап — для фиксированного набора ядер a1,…, ak ищем минимизирующее критерий качества D разбиение {xp}=P₁P₂…P_k; оно дается решающим правилом: xP_i, если d (x, a_i)_j) при ij, в том случае, когда для x минимум d (x, a) достигается при нескольких значениях i, выбор между ними может быть сделан произвольно;

2-й этап — для каждого P_i (i=1,…, k), полученного на первом этапе, ищется _aiA, минимизирующее критерий качества (т.е. слагаемое в D для данного i ;

Начальные значения a₁,…, a_k, {x_p}=P₁P₂…P_k выбираются произвольно, либо по какому-нибудь эвристическому правилу.

На каждом шаге и этапе алгоритма уменьшается критерий качества D, отсюда следует сходимость алгоритма — после конечного числа шагов разбиение {x_p}=P₁P₂…P_k уже не меняется.

Если ядру a_i сопоставляется элемент сети, вычисляющий по входному сигналу x функцию d (x, a_i), то решающее правило для классификации дается интерпретатором «победитель забирает все»: элемент x принадлежит классу P_i, если выходной сигнал i-го элемента d (x, a_i) меньше всех остальных

Единственная вычислительная сложность в алгоритме может состоять в поиске ядра по классу на втором этапе алгоритма, т. е. в поиске aA, минимизирующего. В связи с этим, в большинстве конкретных реализаций метода мера близости d выбирается такой, чтобы легко можно было найти a, минимизирующее D для данного P. В простейшем случае пространство ядер A совпадает с пространством векторов x, а мера близости d (x, a) — положительно определенная квадратичная форма от x_a, например, квадрат евклидового расстояния или другая положительно определенная квадратичная форма. Тогда ядро a_i, минимизирующее D_i, есть центр тяжести класса P_i :

(1.25)

где |P_i| _ число элементов в P_i.

В этом случае также упрощается и решающее правило, разделяющее классы. Обозначим d (x, a)=(x-a, x-a), где d (x, a)_ билинейная форма (если d — квадрат евклидового расстояния между x и a, то d (x, a) — обычное скалярное произведение). В силу билинейности

d (x, a)=(x_a, x_a)=(x, x)_2(x, a)+(a, a).

Чтобы сравнить d (x, a_i) для разных i и найти среди них минимальное, достаточно вычислить линейную неоднородную функцию от x:

d1(x, a_i) = (a_i, a_i)_2(x, a_i).

Минимальное значение d (x, a_i) достигается при том же i, что и минимум d1(x, a_i), поэтому решающее правило реализуется с помощью k сумматоров, вычисляющих d (x, a) и интерпретатора, выбирающего сумматор с минимальным выходным сигналом. Номер этого сумматора и есть номер класса, к которому относится x.

Пусть теперь мера близости — коэффициент корреляции между вектором данных и ядром класса:

где _ координаты векторов, (и аналогично), n _ размерность пространства данных, (и аналогично).