WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 || 3 |

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

(xi, α)>α0 (i=1,...,n)

(yj, α)<α0 (j=1,...,m).

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

Удобно переформулировать задачу. Увеличим размерности всех векторов на единицу, добавив еще одну координату ‑α0 к α, x0 =1 - ко всем x и y0 =1 ‑ ко всем y. Сохраним для новых векторов прежние обозначения - это не приведет к путанице.

Наконец, положим zi =xi (i=1,...,n), zj = ‑yj (j=1,...,m).

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

(zi,α)>0 (i=1,...,n+m),

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

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

2. Сети Хопфилда

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

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

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

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

Что можно сделать, если мы умеем вычислять градиент квадратичной формы

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

Зададим теперь функционирование сети формулой

(8)

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

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

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

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

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


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

(9)

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

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

,

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

.

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

,

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

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

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

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

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

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

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

(10)

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

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

=

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

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

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

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

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

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

, (11)

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

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

(12)

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

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

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

. (13)

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

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

3. Сети Кохонена для кластер-анализа и классификации без учителя

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

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

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

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

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

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

Какую форму могут иметь правила отнесения к классу Веками освящена традиция представлять класс его "типичным", "средним", "идеальным" и т.п. элементом. Этот типичный объект является идеальной конструкцией, олицетворяющей класс.

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

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

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

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

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

Pages:     | 1 || 3 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.