Настройка одноэлементных систем для решения задач

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

1. Линейная регрессия и восстановление простейших закономерностей [2.13, 2.14];
2. Линейная фильтрация и адаптивная обработка сигналов [2.15];
3. Линейное разделение классов и простейшие задачи распознавания образов [2.16, 2.17, 2.18].

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

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

(1)

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

.

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

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

где xij - j-я координата вектора xi.

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

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

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

; Q - матрицу размером с элементами .

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

(2)

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

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

(5)

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

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

Задача четкого разделения двух классов по обучающей выборке ставится так: имеется два набора векторов x1, ..., xm и y1,...,ym. Заранее известно, что xi относится к первому классу, а yi - ко второму. Требуется построить решающее правило, то есть определить такую функцию f(x), что при f(x)>0 вектор x относится к первому классу, а при f(x)<0 - ко второму.



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

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

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

1. искать дополнительные признаки, позволяющие разделить классы;
2. примириться с неизбежностью ошибок, назначить за каждый тип ошибок свой штраф (c12 - штраф за то, что объект первого класса отнесен ко второму, c21 - за то, что объект второго класса отнесен к первому) и строить разделяющее правило так, чтобы минимизировать математическое ожидание штрафа;
3. перейти к нечеткому разделению классов - строить так называемые "функции принадлежности" f1(x) и f2(x) - fi(x) оценивает степень уверенности при отнесении объекта к i-му классу (i=1,2), для одного и того же x может быть так, что и f1(x)>0, и f2(x)>0.

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

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

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

= (y1 + y2 +... +ym)/m - (x1 + x2 +... + xn)/n. (6)

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


Нормируя , получаем:

= ((y1 + y2 +... +ym)/m - (x1 + x2 +... + xn)/n)/||(y1 + y2 +... +ym)/m - (x1 + x2 +... + x n)/n||.

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

0=(((y1 + y2 +... +ym)/m,) +((x1 + x2 +... + x n)/n, ))/2.

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

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



где p1, p2 - априорные вероятности принадлежности объекта соответствующему классу, , - плотности вероятности для распределения проекций точек x в каждом классе.

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

(7)

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

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



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





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

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



Если сразу ставить задачу об оптимальном разделении многомерных нормальных распределений, то получим, что наилучшей разделяющей поверхностью является квадрика (на прямой типичная "квадрика" - две точки). Предполагая, что ковариационные матрицы классов совпадают (в одномерном случае это предположение о том, что ?1=?2), получаем линейную разделяющую поверхность. Она ортогональна прямой, соединяющей центры выборок не в обычном скалярном произведении, а в специальном: , где ? - общая ковариационная матрица классов. За деталями отсылаем к прекрасно написанной книге [2.17], см. также [2.11, 2.12, 2.16].

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

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

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





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

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

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

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



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

Итерационный алгоритм решения этой системы чрезвычайно прост.


Он основан на том, что для любого вектора x его скалярный квадрат (x,x) больше нуля. Пусть - некоторый вектор, претендующий на роль решения неравенств , однако часть из них не выполняется. Прибавим те zi, для которых неравенства имеют неверный знак, к вектору и вновь проверим все неравенства и т.д. Если они совместны, то процесс сходится за конечное число шагов. Более того, добавление zi к можно производить сразу после того, как ошибка () обнаружена, не дожидаясь проверки всех неравенств - и этот вариант алгоритма тоже сходится [2.2].


Содержание раздела

---

---

---

Главная сайта

---