Вычислительный центр СО РАН в г. Красноярске
Нейронные сети могут все. Но точно также "все" могут машины Тьюринга, интерполяционные многочлены, схемы Поста, ряды Фурье, рекурсивные функции,
Другое дело, что в конечном итоге решение практически любой задачи можно описать, как построение некоторой функции, перерабатывающей исходные данные в результат, но такое очень общее описание не дает никакой информации о способе построения этой функции. Мало иметь универсальные способности - надо для каждого класса задач указать, как применять эти способности. Именно здесь, при рассмотрении методов настройки нейронных сетей для решения задач должны выявиться реальные рамки их применимости. Конечно, такие реальные рамки изменяются со временем из-за открытия новых методов и решений.
В данной лекции описано несколько базовых задач для нейронных сетей и основных или исторически первых методов настройки сетей для их решения:
Начнем мы, однако, не с сетей, а с систем, состоящих из одного элемента.
Даже системы из одного адаптивного сумматора находят очень широкое применение. Вычисление линейных функций необходимо во многих задачах. Вот неполный перечень "специальностей" адаптивного сумматора:
Задача линейной регрессии состоит в поиске наилучшего линейного приближения функции, заданной конечным набором значений: дана выборка значений вектора аргументов x1, ..., xm, заданы значения функции F в этих точках: F(xi)=fi, требуется найти линейную (неоднородную) функцию $$\varphi {\rm{(x) = (}}\alpha {\rm{,x) +}}\alpha_0$$, ближайшую к F. Чтобы однозначно поставить задачу, необходимо доопределить, что значит "ближайшую". Наиболее популярен метод наименьших квадратов, согласно которому $$\varphi$$ ищется из условия
$$\sum\limits_{i = 1}^m {(F(x^i ) - \varphi (x^i ))^2 \to \min}$$
Необходимо особенно подчеркнуть, что метод наименьших квадратов не является ни единственным, ни наилучшим во всех отношениях способом доопределения задачи регрессии. Его главное достоинство - квадратичность минимизируемого критерия и линейность получаемых уравнений на коэффициенты $$\varphi$$.
Явные формулы линейной регрессии легко получить, минимизируя квадратичный критерий качества регрессии. Обозначим
$$\begin{array}{l} \Delta_i = (F(x^i ) - \varphi (x^i ));{\rm{ }}H = \sum\limits_{i = 1}^m {\Delta_i^2}{\rm{=}}\sum\limits_{i = 1}^m {(F(x^i ) - \varphi (x^i ))^2} = \\ = \sum\limits_{i = 1}^m {(f_i - (\alpha ,x^i ) - \alpha_0 )^2}. \\ \end{array}$$
Найдем производные минимизируемой функции H по настраиваемым параметрам:
$$$ {\frac{\partial H}{\partial \alpha_j}}{\rm{ = }}{\sum\limits_{i = 1}^m {\Delta_i x_j^i}{\rm{, (}}j = 1,...,n)}{\rm{; }}{\frac{\partial H}{\partial \alpha_0}}{\rm{ = }}{\sum\limits_{i = 1}^m {\Delta_i}} $$$.
где xij - j -я координата вектора xi.
Приравнивая частные производные H нулю, получаем уравнения, из которых легко найти все $$\alpha_j$$ ( j=0,...,n ). Решение удобно записать в общем виде, если для всех i=1,...,m обозначить $$x_0^i \equiv 1$$ и рассматривать n +1 -мерные векторы данных xi и коэффициентов $$\alpha$$. Тогда
$$\Delta_i = f_i - (\alpha ,x^i ),{\rm{ }}\partial H/\partial \alpha_j = \sum\limits_{i = 1}^m {\Delta_i x_j^i {\rm{ }}(j = 0,1,...,n).}$$
Обозначим p n +1 -мерный вектор с координатами $$p_j = \frac{1}{m}\sum\limits_{i = 1}^m {f_i x_j^i}$$ ; Q - матрицу размером $${\rm{(n + 1)}} \times {\rm{(n + 1)}}$$ с элементами $$q_{jk} = \frac{1}{m}\sum\limits_{i = 1}^m {x_j^i x_k^i}$$.
В новых обозначениях решение задачи линейной регрессии имеет вид:
$$\varphi {\rm{(x) = (}}\alpha {\rm{,x)}}{\rm{,}}\alpha {\rm{= Q}}^{-1}{\rm{p}}.$$
Приведем это решение в традиционных обозначениях математической статистики. Обозначим Mо среднее значение j -й координаты векторов исходной выборки:
$$M_j = \frac{1}{m}\sum\limits_{i = 1}^m {x_j^i} .$$
Пусть M - вектор с координатами Mо. Введем также обозначение sj для выборочного
$$s_j = \sqrt {\frac{1}{m}\sum\limits_{i = 1}^m {(x_j^i} - M_j )^2}$$
Величины sj задают естественный масштаб для измерения j -х координат векторов x. Кроме того, нам потребуются величина sf и коэффициенты корреляции f с j -ми координатами векторов x - rfj:
$$s_f = \sqrt {\frac{1}{m}\sum\limits_{i = 1}^m {(f_i - M_f )^2}}{\rm{,}}M_f = \frac{1}{m}\sum\limits_{i = 1}^m {f_i} ,{\rm{ }}r_{fj} = \frac{{\frac{1}{m}\sum\limits_{i = 1}^m {(f_i - M_f )(x_j^i - M_j )}}}{{s_f s_j}}.$$
Вернемся к n -мерным векторам данных и коэффициентов. Представим, что векторы сигналов проходят предобработку - центрирование и нормировку и далее мы имеем дело с векторами yi:
$$y_j^i = \frac{{x_j^i - M_j}}{{s_j}}.$$
Это, в частности, означает, что все рассматриваемые координаты вектора x имеют ненулевую дисперсию, т.е. постоянные координаты исключаются из рассмотрения - они не несут полезной информации. Уравнения регрессии будем искать в форме: $$\varphi {\rm{(y) = (}}\beta {\rm{,y) +}}\beta_0$$. Получим:
$$\beta_0 {\rm{= M}}_{\rm{f}}{\rm{,}}\beta {\rm{=}}s_{\rm{f}}{\rm{R}}^{-1}{\rm{R}}_{\rm{f}},$$
где Rf - вектор коэффициентов корреляции f с j -ми координатами векторов x, имеющий координаты rfj, R - матрица коэффициентов корреляции между координатами вектора данных:
$$r_{kj} = \frac{{\frac{1}{m}\sum\limits_{i = 1}^m {(x_k^i - M_k )(x_j^i - M_j )}}}{{s_k s_j}} = \frac{1}{m}\sum\limits_{i = 1}^m {y_k^i y_j^i } .$$
В задачах обработки данных почти всегда возникает вопрос о последовательном уточнении результатов по мере поступления новых данных ( обработка данных "на лету" ). Существует, как минимум, два подхода к ответу на этот вопрос для задачи линейной регрессии. Первый подход состоит в том, что изменения в
В рамках первого подхода рассмотрим, как будет изменяться $$\alpha$$ из формулы (2) при добавлении нового вектора данных. В первом порядке теории возмущений найдем изменение вектора коэффициента $$\alpha$$ при изменении вектора p и матрицы Q:
$$\begin{array}{l} \alpha + \Delta \alpha = (Q + \Delta Q)^{-1} (p + \Delta p); \\ (Q + \Delta Q)^{-1} = (Q(1 + Q^{-1} \Delta Q))^{-1} = Q^{-1} - Q^{-1} \Delta QQ^{-1} + o(\Delta Q); \\ \Delta \alpha \cong Q^{-1} (\Delta p - \Delta Q\alpha ). \\ \end{array}$$
Пусть на выборке $$\{x^i \}_{i = 1}^m$$ вычислены p, Q, Q-1. При получении нового вектора данных xm +1 и соответствующего значения F(xm +1)=f m +1 x, y матрица $${\rm{x}} \otimes {\rm{y}}^{\rm{T}}$$ имеет своими элементами $${\rm{x}}_{\rm{j}}{\rm{y}}_{\rm{k}}$$ .
где $$\Delta_{m + 1}^0 = f_{m + 1} - (\alpha ,x^{m + 1} )$$ - ошибка на векторе данных xm +1
Пересчитывая по приведенным формулам p, Q, Q-1 и $$\alpha$$ после каждого получения данных, получаем процесс, в котором последовательно уточняются уравнения линейной регрессии. И требуемый объем памяти, и количество операций имеют порядок n2 - из-за необходимости накапливать и модифицировать матрицу Q-1. Конечно, это меньше, чем потребуется на обычное обращение матрицы Q на каждом шаге, однако следующий простой алгоритм еще экономнее. Он вовсе не обращается к матрицам Q, Q-1 и основан на уменьшении на каждом шаге величины $$(\Delta_{m + 1}^0 )^2 = (f_{m + 1} - (\alpha ,x^{m + 1} ))^2$$ - квадрата ошибки на векторе данных xm +1
Вновь обратимся к формуле (2) и будем рассматривать n +1 -мерные векторы данных и коэффициентов. Обозначим $$x = x^{m + 1} ;{\rm{ }}\Delta = \Delta_{m + 1}^0 = f_{m + 1} - (\alpha ,x^{m + 1} )$$. Тогда
$$grad_\alpha \Delta = - \Delta \times x$$
Последняя элементарная формула столь важна в теории адаптивных сумматоров, что носит "именное название" - формула Уидроу. "Обучение" адаптивного сумматора h - величина шага.
Если при каждом поступлении нового вектора данных x изменять $$\alpha$$ указанным образом, то получим последовательную процедуру построения линейной аппроксимации функции F(x). Такой алгоритм обучения легко реализуется аппаратными средствами (изменение веса связи $$\alpha_j$$ есть произведение прошедшего по ней сигнала xj на ошибку $$\Delta$$ и на величину шага). Возникает, однако, проблема сходимости: если h слишком мало, то сходимость будет медленной, если же слишком велико, то произойдет потеря устойчивости и сходимости не будет вовсе. Детальному изложению этого подхода и его приложений посвящен учебник [2.15].
Задача четкого разделения двух классов по x1, ..., xm и y1,...,ym. Заранее известно, что xi относится к первому классу, а yi - ко второму. Требуется построить решающее правило, то есть определить такую функцию 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.Линейное разделение классов состоит в построении линейного решающего правила - то есть такого вектора $$\alpha$$ и числа $$\alpha_0$$ (называемого порогом), что при $${(x, \alpha )} > {\alpha_0 x}$$ относится к первому классу, а при $${(x, \alpha )} < {\alpha_0}$$ - ко второму.
Поиск такого решающего правила можно рассматривать как разделение классов в проекции на прямую. Вектор $$\alpha$$ задает прямую, на которую ортогонально проектируются все точки, а число $$\alpha_0$$ - точку на этой прямой, отделяющую первый класс от второго.
Простейший и подчас очень удобный выбор состоит в проектировании на прямую, соединяющую центры масс выборок. Центр масс вычисляется в предположении, что массы всех точек одинаковы и равны 1. Это соответствует заданию $$\alpha$$ в виде
Во многих случаях удобнее иметь дело с векторами единичной длины. Нормируя $$\alpha$$, получаем:
$$\alpha = ((y^{1} + y^{2} +... +y^{m})/m - (x^{1} + x^{2} +... + x^{n})/n)/|| (y^{1} + y^{2} +... +y^{m})/m - (x^{1} + x^{2} +... + x ^{n})/n||.$$Выбор $$\alpha_0$$ может производиться из различных соображений. Простейший вариант - посередине между центрами масс выборок:
$$\alpha _{0}=(((y^{1} + y^{2} +... +y^{m})/m,\alpha ) +((x^{1} + x^{2} +... + x ^{n})/n, \alpha ))/2.$$Более тонкие способы построения
Можно для каждого класса построить приближенную плотность вероятностей распределения проекций его точек на прямую (это намного проще, чем для многомерного распределения) и выбирать $$\alpha_0$$, минимизируя вероятность ошибки. Пусть решающее правило имеет вид: при $$(x, \alpha )$$ > $$\alpha_0$$ x относится к первому классу, а при $$(x, \alpha )$$ < $$\alpha_0$$ - ко второму. В таком случае вероятность ошибки будет равна
$$P = p_1 \int\limits_{- \infty}^{\alpha_0}{\rho_1 (\chi )} d\chi + p_2 \int\limits_{\alpha_0}^\infty {\rho_2 (\chi )} d\chi$$
где p1, p2 - априорные вероятности принадлежности объекта соответствующему классу, $$\rho_1 (\chi )$$, $$\rho_2 (\chi )$$ - плотности вероятности для распределения проекций $$\chi$$ точек x в каждом классе.
Приравняв нулю производную вероятности ошибки по $$\alpha_0$$, получим: число $$\alpha_0$$, доставляющее минимум вероятности ошибки, является корнем уравнения:
$${\rm{p}}_1 \rho_1 {\rm{(}}\chi {\rm{) = p}}_2 \rho_2 {\rm{(}}\chi {\rm{)}}{\rm{,}}$$
либо (если у этого уравнения нет решений) оптимальным является правило, относящее все объекты к одному из классов.
Если принять гипотезу о нормальности распределений:
$$\rho (y) = \frac{1}{{\sqrt {2\pi} \sigma}}e^{- (y - a)^2 /2\sigma^2} ,$$
то для определения $$\alpha_0$$ получим:
$$\frac{{p_1}}{{\sqrt {2\pi} \sigma_1}}e^{- (y - a_1 )^2 /2\sigma_1^2} = \frac{{p_2}}{{\sqrt {2\pi} \sigma_2}}e^{- (y - a_2 )^2 /2\sigma_2^2} ,$$ $$\ln (p_1 /p_2 ) - \ln (\sigma_1 /\sigma_2 ) - (y - a_1 )^2 /2\sigma_1^2 + (y - a_2 )^2 /2\sigma_2^2 = 0$$
Если это уравнение имеет два корня $$y=\alpha_1, \alpha_2$$, ( $$\alpha_1 < \alpha_2$$ ) то наилучшим решающим правилом будет: при $$\alpha_1 < {(x, \alpha )} < \alpha_2$$ объект принадлежит одному классу, а при $$\alpha_1 > {(x, \alpha )}$$ или $${(x, \alpha )} > \alpha_2$$ - другому (какому именно, определяется тем, которое из произведений $$p_i \rho_i (\chi )$$ больше). Если корней нет, то оптимальным является отнесение к одному из классов. Случай единственного корня представляет интерес только тогда, когда $$\sigma _{1}=\sigma _{2}$$. При этом уравнение превращается в линейное и мы приходим к исходному варианту - единственной разделяющей точке $$\alpha_0$$.
Таким образом, разделяющее правило с единственной разделяющей точкой $$\alpha_0$$ не является наилучшим для нормальных распределений и надо искать две разделяющие точки.
Если сразу ставить задачу об оптимальном разделении многомерных нормальных распределений, то получим, что наилучшей разделяющей поверхностью является квадрика (на прямой типичная "квадрика" - две точки). Предполагая, что ковариационные матрицы классов совпадают (в одномерном случае это предположение о том, что $$\sigma _{1}=\sigma _{2}$$ ), получаем линейную разделяющую поверхность. Она ортогональна прямой, соединяющей центры выборок не в обычном скалярном произведении, а в специальном: $$\left\langle {x,y} \right\rangle = \left( {x,\Sigma^{-1} y} \right)$$, где $$\Sigma$$ - общая ковариационная матрица классов. За деталями отсылаем к прекрасно написанной книге [2.17], см. также [2.11, 2.12, 2.16].
Важная возможность усовершенствовать разделяющее правило состоит с использовании оценки не просто вероятности ошибки, а среднего риска: каждой ошибке приписывается "цена" ci и минимизируется сумма $${\rm{c}}_1 {\rm{p}}_1 \rho_1 {\rm{(}}\chi {\rm{) + c}}_2 {\rm{p}}_2 \rho_2 {\rm{(}}\chi {\rm{)}}$$. Ответ получается практически тем же (всюду pi заменяются на ci pi ), но такая добавка важна для многих приложений.
Требование безошибочности разделяющего правила на
Возьмем за основу при построении
$${{\rm{(}}{x^i}{\rm{,}}\alpha )} > \alpha_0 {\rm{(i = 1}},...,{\rm{n)}}$$
$${\rm{(y}}^{\rm{i}}{\rm{,}}\alpha {\rm{)}} < \alpha_0 {\rm{(i = 1}},...,{\rm{m)}}$$
Здесь xi ( i=1,..,n ) - векторы из yi ( j=1,..,m ) - ко второму.
Удобно переформулировать задачу. Увеличим размерности всех векторов на единицу, добавив еще одну координату - $$\alpha_0$$ к $$\alpha$$, x0=1 - ко всем x и y0 =1 - ко всем y. Сохраним для новых векторов прежние обозначения - это не приведет к путанице.
Наконец, положим zi = xi ( i=1,...,n ), zj = -yj ( j=1,...,m ).
Тогда получим систему n +m неравенств
$${\rm{(z}}^{\rm{i}}{\rm{,}}\alpha {\rm{)}} > {0 {\rm{(i = 1}},...,{\rm{n +m)}}}$$
которую будем решать относительно $$\alpha$$. Если множество решений непусто, то любой его элемент $$\alpha$$ порождает решающее правило, безошибочное на
x его скалярный квадрат (x,x) больше нуля. Пусть $$\alpha$$ - некоторый вектор, претендующий на роль решения неравенств $${{\rm{(z}}^{\rm{i}}{\rm{,}}\alpha {\rm{)}}} > {0 {\rm{(i = 1}},...,{\rm{n +m)}}}$$, однако часть из них не выполняется. Прибавим те zi, для которых неравенства имеют неверный знак, к вектору $$\alpha$$ и вновь проверим все неравенства $${{\rm{(z}}^{\rm{i}}{\rm{,}}\alpha {\rm{)}}} > 0$$ и т.д. Если они совместны, то процесс сходится за конечное число шагов. Более того, добавление zi к $$\alpha$$ можно производить сразу после того, как ошибка ( $${{\rm{(z}}^{\rm{i}}{\rm{,}}\alpha {\rm{)}}} < 0$$ ) обнаружена, не дожидаясь проверки всех неравенств - и этот вариант алгоритма
тоже сходится [2.2].
Перейдем от одноэлементных систем к нейронным сетям. Пусть $$\alpha_{ij}$$ - вес связи, ведущей от j -го нейрона к i -му (полезно обратить внимание на порядок индексов). Для полносвязных сетей определены значения $$\alpha_{ij}$$ при всех i,j, для других архитектур связи, ведущие от j -го нейрона к i -му для некоторых i,j не определены. В этом случае положим $$\alpha_{ij} = 0$$.
В данном разделе речь пойдет в основном о полносвязных сетях. Пусть на выходах всех нейронов получены сигналы xj ( j -номер нейрона). Обозначим x вектор этих выходных сигналов. Прохождение вектора сигналов x через сеть связей сводится к умножению матрицы ( $$\alpha_{ij}$$ ) на вектор сигналов x. В результате получаем вектор входных сигналов нелинейных элементов нейронов: $$y_i = \sum\limits_j {\alpha_{ij} x_j}$$.
Это соответствие " прохождение сети $$\equiv$$ умножение матрицы связей на вектор сигналов " является основой для перевода обычных численных методов на нейросетевой язык и обратно. Практически всюду, где основной операцией является умножение матрицы на вектор, применимы нейронные сети. С другой стороны, любое устройство, позволяющее быстро осуществлять такое умножение, может использоваться для реализации нейронных сетей.
В частности, вычисление градиента квадратичной формы $$$ {H =}{{\frac{1}{2}}{\rm{(}}{{x,Qx)}}} $$$ может осуществляться полносвязной сетью с симметричной матрицей связей: $${\rm{grad}}H = Qx$$ ( $$\alpha_{ij} = q_{ij} = q_{ji}$$ ). Именно это наблюдение лежит в основе данного раздела.
Что можно сделать, если мы умеем вычислять градиент квадратичной формы?
В первую очередь, можно x через сеть с весами связей $$\alpha_{ij} = q_{ij} = q_{ji}$$ при условии, что на входной сумматор каждого нейрона по дополнительной связи веса b подается стандартный единичный сигнал.
Зададим теперь функционирование сети формулой
$$x' = x - h{\rm{grad}}P = x - h(Qx + b)$$
Нелинейных элементов вовсе не нужно! Каждый ( j -й) нейрон имеет входные веса $$\alpha_{ij} = - hq_{ij}$$ для связей с другими нейронами ( $${\rm{i}} \ne {\rm{j}}$$ ), вес $$- b_j$$ для постоянного единичного входного сигнала и вес $$\alpha_{jj} = 1 - hq_{jj}$$ для связи нейрона с самим собой (передачи на него его же сигнала с предыдущего шага). Выбор шага h>0 может вызвать затруднение (он зависит от коэффициентов минимизируемого многочлена). Есть, однако, простое решение: в каждый момент дискретного времени T выбирается свое значение $$h_T$$. Достаточно, чтобы шаг стремился со временем к нулю, а сумма шагов - к бесконечности (например, $$h_T = \frac{1}{T}$$, или $$h_T = \frac{1}{{\sqrt T}}$$ ).
Итак, простая симметричная полносвязная сеть без нелинейных элементов может
Решение системы линейных уравнений $$Ax = b$$ сводится к минимизации многочлена
$$P = \frac{1}{2}((Ax - b),(Ax - b)) = \frac{1}{2}(x,A^{\rm T} Ax) - (A^{\rm T} b,x) - \frac{1}{2}(b,b).$$
Поэтому решение системы может производиться нейронной сетью. Простейшая сеть, вычисляющая градиент этого многочлена, не полносвязна, а состоит из двух слоев: первый с матрицей связей A, второй - с транспонированной матрицей $$A^{\rm T}$$. Постоянный единичный сигнал подается на связи с весами $$b_j$$ на первом слое. Минимизация этого многочлена, а значит и
Небольшая модификация позволяет вместо безусловного минимума многочлена второго порядка P искать точку условного минимума с условиями $$x_i = c_i$$ для $$i = i_1 ,...,i_k$$, то есть точку минимума P в ограничении на аффинное многообразие, параллельное некоторым координатным плоскостям. Для этого вместо формулы
$$x' = x - h{\rm{grad}}P = x - h(Qx + b)$$
следует использовать:
$$x'_i = c_i$$ при $$i = i_1 ,...,i_k ;$$
$$x'_i = x_i - h\frac{{\partial P}}{{\partial x_i}} = x_i - h\left( {\sum\limits_j {q_{ij} x_j} + b_i} \right)$$ при $${i \ne i_1 ,...,i_k}$$.
Устройство, способное находить точку условного минимума многочлена второго порядка при условиях вида $$x_i = c_i$$ для $$i = i_1 ,...,i_k$$ позволяет решать важную задачу - заполнять пробелы в данных (и, в частности, строить линейную регрессию).
Предположим, что получаемые в ходе испытаний векторы данных подчиняются многомерному нормальному распределению:
$$\rho (x) = Ce^{- \frac{1}{2}((x - {\bf{M}}x),Q(x - {\bf{M}}x))},$$
где Mx - вектор математических ожиданий координат, $$Q = \Sigma^{-1}$$, $$\Sigma$$ - ковариационная матрица, n - размерность пространства данных,
$$C = \frac{1}{{(2\pi )^{n/2} \sqrt {\det \Sigma}}} .$$
Напомним определение матрицы $$\Sigma$$: $$(\Sigma )_{ij} = {\bf{M}}((x_i - {\bf{M}}x_i )(x_j - {\bf{M}}x_j ))$$,
где M - символ математического ожидания, нижний индекс соответствует номеру координаты.
В частности, простейшая оценка ковариационной матрицы по выборке дает:
$$S = \frac{1}{m}\sum\limits_j {(x^j - {\bf{M}}x)} \otimes ({\bf{M}}x^j - {\bf{M}}x)^{\rm T},$$
где m - число элементов в выборке, верхний индекс j - номер вектора данных в выборке, верхний индекс Т означает транспонирование, а $$\otimes$$ - произведение вектора-столбца на вектор-строку (тензорное произведение).
Пусть у вектора данных x известно несколько координат: $$x_i = c_i$$ для $$i = i_1 ,...,i_k$$. Наиболее вероятные значения неизвестных координат должны доставлять условный максимум показателю нормального распределения - многочлену второго порядка $$((x - {\bf{M}}x),Q(x - {\bf{M}}x))$$ (при условии $$x_i = c_i$$ для $$i = i_1 ,...,i_k$$ ). Эти же значения будут условными математическими ожиданиями неизвестных координат при заданных условиях.
Таким образом, чтобы построить сеть, заполняющую пробелы в данных, достаточно сконструировать сеть для поиска точек условного минимума многочлена
$$((x - {\bf{M}}x),Q(x - {\bf{M}}x))$$
при условиях следующего вида: $$x_i = c_i$$ для $$i = i_1 ,...,i_k$$. Матрица связей Q выбирается из условия $$Q = \Sigma^{-1}$$, где $$\Sigma$$ - ковариационная матрица (ее оценка по выборке).
На первый взгляд, пошаговое накопление $$Q = \Sigma^{-1}$$ по мере поступления данных требует слишком много операций - получив новый вектор данных требуется пересчитать оценку $$\Sigma,$$ а потом вычислить $$Q = \Sigma^{-1}$$. Можно поступать и по-другому, воспользовавшись формулой приближенного обрашения матриц первого порядка точности:
$$(\Sigma + \varepsilon \Delta )^{-1} = \Sigma^{-1} - \varepsilon \Sigma^{-1} \Delta \Sigma^{-1} + o(\varepsilon ).$$
Если же добавка $$\Delta$$ имеет вид $$\Delta = y \otimes y^{\rm T}$$, то
$$(\Sigma + \varepsilon \Delta )^{-1} = \Sigma^{-1} - \varepsilon (\Sigma^{-1} y) \otimes (\Sigma^{-1} y)^{\rm T} + o(\varepsilon ).$$
Заметим, что решение задачи (точка условного минимума многочлена) не меняется при умножении Q на число. Поэтому полагаем:
$$Q_0 = 1,{\rm{ }}Q_{k + 1} = Q_k + \varepsilon (Q_k (x^{k + 1} - ({\bf{M}}x)^{k + 1} )) \otimes (Q_k (x^{k + 1} - ({\bf{M}}x)^{k + 1} ))^{\rm T} ,$$
где 1 - единичная матрица, $$\varepsilon >0$$ - достаточно малое число, $$x^{k + 1}$$ - k +1 -й вектор данных, $$({\bf{M}}x)^{k + 1}$$ - среднее значение вектора данных, уточненное с учетом $$x^{k + 1}$$:
$$({\bf{M}}x)^{k + 1} = \frac{1}{{k + 1}}(k({\bf{M}}x)^k + x^{k + 1} )$$
В формуле для пошагового накопления матрицы Q ее изменение $$\Delta Q$$ при появлении новых данных получается с помощью вектора $$y=x^{k + 1} - ({\bf{M}}x)^{k + 1}$$, пропущенного через сеть: $$(\Delta Q)_{ij} = \varepsilon z_i z_j$$, где z=Qy. Параметр $$\varepsilon$$ выбирается достаточно малым для того, чтобы обеспечить положительную определенность получаемых матриц (и, по возможности, их близость к истинным значениям Q ).
Описанный процесс формирования сети можно назвать обучением. Вообще говоря, можно проводить формальное различение между формированием сети по явным формулам и по алгоритмам, не использующим явных формул для весов связей ( неявным ). Тогда термин "обучение" предполагает неявные алгоритмы, а для явных остается название "формирование". Здесь мы такого различия проводить не будем.
Если при обучении сети поступают некомплектные данные $$x^{k + 1}$$ с отсутствием значений некоторых координат, то сначала эти значения восстанавливаются с помощью имеющейся сети, а потом используются в ее дальнейшем обучении.
Во всех задачах оптимизации существенную роль играет вопрос о правилах остановки: когда следует прекратить циклическое функционирование сети, остановиться и считать полученный результат ответом? Простейший выбор - остановка по малости изменений: если изменения сигналов сети за цикл меньше некоторого фиксированного малого $$\sigma$$ (при использовании переменного шага $$\sigma$$ может быть его функцией), то оптимизация заканчивается.
До сих пор речь шла о минимизации положительно определенных квадратичных форм и многочленов второго порядка. Однако самое знаменитое приложение полносвязных сетей связано с увеличением значений положительно определенных квадратичных форм. Речь идет о системах ассоциативной памяти [2.4, 2.5, 2.6, 2.7, 2.9, 2.10, 2.12].
Предположим, что задано несколько эталонных векторов данных $$x^1 ,...,x^m$$ и при обработке поступившего на вход системы вектора x требуется получить на выходе ближайший к нему эталонный вектор. Мерой сходства в простейшем случае будем считать косинус угла между векторами - для векторов фиксированной длины это просто скалярное произведение. Можно ожидать, что изменение вектора x по закону
$$x' = x + h\sum\limits_k {x^k (x^k ,x)} ,$$
где h - малый шаг, приведет к увеличению проекции x на те эталоны, скалярное произведение на которые $$(x^k ,x)$$ больше.
Ограничимся рассмотрением эталонов, и ожидаемых результатов обработки с координатами $$\pm 1$$. Развивая изложенную идею, приходим к дифференциальному уравнению
$$\begin{array}{l} \frac{{dx}}{{dt}} = - {\rm{grad}}H, \\ H = H_0 + \theta H_1 ,{\rm{ }}H_0 (x) = - \frac{1}{2}\sum\limits_k {(x^k ,x)}^2 ,{\rm{ }}H_1 (x) = \frac{1}{2}\sum\limits_i {(x_i^2 - 1)^2 ,} \\ {\rm{grad}}H_0 = - \sum\limits_k {x^k (x^k ,x)} ,{\rm{(grad}}H_1 )_j = (x_j^2 - 1)x_j , \\ \end{array}$$
где верхними индексами обозначаются номера векторов-эталонов, нижними - координаты векторов.
Функция H называется " энергией " сети, она минимизируется в ходе функционирования. Слагаемое $$H_0$$ вводится для того, чтобы со временем возрастала проекция вектора x на те эталоны, которые к нему ближе, слагаемое $$H_1$$ обеспечивает стремление координат вектора x к $$\pm 1$$. Параметр $$\theta$$ определяет соотношение между интенсивностями этих двух процессов. Целесообразно постепенно менять $$\theta$$ со временем, начиная с малых $$\theta <1$$, и приходя в конце концов к $$\theta >1$$.
Подробнее системы ассоциативной памяти рассмотрены в отдельной лекции. Здесь же мы ограничимся обсуждением получающихся весов связей. Матрица связей построенной сети определяется функцией $$H_0$$, так как $${\rm{(grad}}H_1 )_j = (x_j^2 - 1)x_j$$ вычисляется непосредственно при j -м нейроне без участия сети. Вес связи между i -м и j -м нейронами не зависит от направления связи и равен
$$\alpha_{ij} = \sum\limits_k {x_i^k x_j^k}$$
Эта простая формула имеет чрезвычайно важное значение для развития теории нейронных сетей. Вклад k -го эталона в связь между i -м и j -м нейронами ( $$x_i^k x_j^k$$ ) равен +1, если i -я и j -я координаты этого эталона имеют одинаковый знак, и равен -1, если они имеют разный знак.
В результате возбуждение i -го нейрона передается j -му (и симметрично, от j -го к i -му), если у большинства эталонов знак i -й и j -й координат совпадают. В противном случае эти нейроны тормозят друг друга: возбуждение i -го ведет к торможению j -го, торможение i -го - к возбуждению j -го (воздействие j -го на i -й симметрично). Это правило образования ассоциативных связей (правило Хебба) сыграло огромную роль в теории нейронных сетей.
Построение отношений на множестве объектов - одна из самых загадочных и открытых для творчества областей применения искусственного интеллекта. Первым и наиболее распространенным примером этой задачи является классификация без учителя. Задан набор объектов, каждому объекту сопоставлен вектор значений признаков (строка таблицы). Требуется разбить эти объекты на классы эквивалентности.
Естественно, прежде, чем приступать к решению этой задачи, нужно ответить на один вопрос: зачем производится это разбиение и что мы будем делать с его результатом? Ответ на него позволит приступить к формальной постановке задачи, которая всегда требует компромисса между сложностью решения и точностью формализации: буквальное следование содержательному смыслу задачи нередко порождает сложную вычислительную проблему, а следование за простыми и элегантными алгоритмами может привести к противоречию со здравым смыслом.
Итак, зачем нужно строить отношения эквивалентности между объектами? В первую очередь - для фиксации знаний. Люди накапливают знания о классах объектов - это практика многих тысячелетий, зафиксированная в языке: знание относится к имени класса (пример стандартной древней формы: "люди смертны", "люди" - имя класса). В результате классификации как бы появляются новые имена и правила их присвоения.
Для каждого нового объекта мы должны сделать два дела:
Какую форму могут иметь правила отнесения к классу? Веками освящена традиция представлять класс его "типичным", "средним", "идеальным" и т.п. элементом. Этот типичный объект является идеальной конструкцией, олицетворяющей класс.
Отнесение объекта к классу проводится путем его сравнения с типичными элементами разных классов и выбора ближайшего. Правила, использующие типичные объекты и меры близости для их сравнения с другими, очень популярны и сейчас.
Простейшая мера близости объектов - квадрат
Мы не оговариваем специально существование априорных ограничений, налагаемых на новые объекты - естественно, что "вселенная" задачи много 'уже и гораздо определеннее Вселенной.
Другая мера близости, естественно возникающая при обработке сигналов, изображений и т.п. - квадрат коэффициента корреляции (чем он больше, тем ближе объекты). Возможны и иные варианты - все зависит от задачи.
Если число классов m заранее определено, то задачу классификации без учителя можно поставить следующим образом.
Пусть {xp} - векторы значений признаков для рассматриваемых объектов и в пространстве таких векторов определена мера их близости $$\rho {x,y}$$. Для определенности примем, что чем ближе объекты, тем меньше $$\rho.$$ С каждым классом будем связывать его типичный объект. Далее называем его ядром класса. Требуется определить набор из m ядер y1, y2, ... ym и разбиение {xp} на классы:
$$\{x^p \} = Y_1 \cup Y_2 \cup ... \cup Y_m$$
минимизирующее следующий критерий
$$Q = \sum\limits_{i = 1}^m {D_i \to \min} ,$$
где для каждого ( i -го) класса $$D_i$$ - сумма расстояний от принадлежащих ему точек выборки до ядра класса:
$$D_i = \sum\limits_{x^p \in Y_i}{\rho (x^p ,y^i )}$$
Минимум Q берется по всем возможным положениям ядер $$y^i$$ и всем разбиениям {xp} на m классов Yi.
Если число классов заранее не определено, то полезен критерий слияния классов: классы Yi и Yj сливаются, если их ядра ближе, чем среднее расстояние от элемента класса до ядра в одном из них. (Возможны варианты: использование среднего расстояния по обоим классам, использование порогового коэффициента, показывающего, во сколько раз должно расстояние между ядрами превосходить среднее расстояние от элемента до ядра и др.)
Использовать критерий слияния классов можно так: сначала принимаем гипотезу о достаточном числе классов, строим их, минимизируя Q, затем некоторые Yi объединяем, повторяем минимизацию Q с новым числом классов и т.д.
Существует много эвристических алгоритмов классификации без учителя, основанных на использовании мер близости между объектами. Каждый из них имеет свою область применения, а наиболее распространенным недостатком является отсутствие четкой формализации задачи: совершается переход от идеи кластеризации прямо к алгоритму, в результате неизвестно, что ищется (но что-то в любом случае находится, иногда - неплохо).
Сетевые алгоритмы классификации без учителя строятся на основе итерационного метода динамических ядер. Опишем его сначала в наиболее общей абстрактной форме. Пусть задана выборка предобработанных векторов данных {xp}. Пространство векторов данных обозначим E. Каждому классу будет соответствовать некоторое ядро a. Пространство ядер будем обозначать A. Для каждых $$x \in E$$ и $$a \in A$$ определяется мера близости d(x,a). Для каждого набора из k ядер a1,...,ak и любого разбиения {xp} на k классов $${\rm{\{x}}^{\rm{p}}{\rm{\} = P}}_{\rm{1}} \cup {\rm{P}}_{\rm{2}} \cup ... \cup {\rm{P}}_{\rm{k}}$$ определим критерий качества:
$$D = D(a_1 ,a_2 ,...,a_k ,P_1 ,P_2 ,...P_k ) = \sum\limits_{i = 1}^k {\sum\limits_{x \in P_i}{d(x,a_i )}}$$
Требуется найти набор a1,...,ak и разбиение $${\rm{\{x}}^{\rm{p}}{\rm{\} = P}}_{\rm{1}} \cup {\rm{P}}_{\rm{2}} \cup ... \cup {\rm{P}}_{\rm{k}}$$, минимизирующие D.
Шаг алгоритма разбивается на два этапа:
a1,...,ak ищем минимизирующее критерий качества D разбиение $${\rm{\{x}}^{\rm{p}}{\rm{\} = P}}_{\rm{1}} \cup {\rm{P}}_{\rm{2}} \cup ... \cup {\rm{P}}_{\rm{k}}$$ ; оно дается решающим правилом: $$x \in P_i$$, если d(x, ai)<d(x, aj) при $${\rm{i}} \ne {\rm{j}}$$, в том случае, когда для x минимум d(x,a) достигается при нескольких значениях i, выбор между ними может быть сделан произвольно;Pi ( i=1,...,k ), полученного на первом этапе, ищется $$a_I \in A$$, минимизирующее критерий качества (т.е. слагаемое в D для данного $$i-D_i = \sum\limits_{x \in P_i}{d(x,a_i )}$$Начальные значения a1,...,ak, $${\rm{\{x}}^{\rm{p}}{\rm{\} = P}}_{\rm{1}} \cup {\rm{P}}_{\rm{2}} \cup ... \cup {\rm{P}}_{\rm{k}}$$ выбираются произвольно, либо по какому-нибудь эвристическому правилу.
На каждом шаге и этапе алгоритма уменьшается критерий качества D, отсюда следует сходимость алгоритма - после конечного числа шагов разбиение $${\rm{\{x}}^{\rm{p}}{\rm{\} = P}}_{\rm{1}} \cup {\rm{P}}_{\rm{2}} \cup ... \cup {\rm{P}}_{\rm{k}}$$ уже не меняется.
Если ядру ai сопоставляется элемент сети, вычисляющий по входному сигналу x функцию d(x,ai), то решающее правило для классификации дается интерпретатором "победитель забирает все": элемент x принадлежит классу Pi, если выходной сигнал i -го элемента d(x,ai) меньше всех остальных
Единственная вычислительная сложность в алгоритме может состоять в поиске ядра по классу на втором этапе алгоритма, т.е. в поиске $$a \in A$$, минимизирующего $$D_i = \sum\limits_{x \in P_i}{d(x,a)}$$
В связи с этим, в большинстве конкретных реализаций метода мера близости d выбирается такой, чтобы легко можно было найти a, минимизирующее D для данного P.
В простейшем случае пространство ядер A совпадает с пространством векторов x, а мера близости d(x,a) - положительно определенная квадратичная форма от x-a, например, квадрат ai, минимизирующее Di, есть центр тяжести класса Pi:
$$a_i = \frac{1}{{|P_i |}}\sum\limits_{x \in P_i} x ,$$
где |Pi| - число элементов в Pi.
В этом случае также упрощается и решающее правило, разделяющее классы. Обозначим d(x,a) =(x-a,x-a), где (.,.) - билинейная форма (если d - квадрат x и a, то (.,.) - обычное скалярное произведение). В силу билинейности
d(x,a)=(x-a,x-a)=(x,x)-2(x,a) +(a,a).
Чтобы сравнить d(x,ai) для разных i и найти среди них минимальное, достаточно вычислить линейную неоднородную функцию от x:
d1(x,ai) = (ai,ai)-2(x,ai).
Минимальное значение d(x,ai) достигается при том же i, что и минимум d1(x,ai), поэтому решающее правило реализуется с помощью k сумматоров, вычисляющих d(x,a) и интерпретатора, выбирающего сумматор с минимальным выходным сигналом. Номер этого сумматора и есть номер класса, к которому относится x.
Пусть теперь мера близости - коэффициент корреляции между вектором данных и ядром класса:
$$d(x,a) = r(x,a) = \sum\limits_j {\frac{{(x_j - M_x )(a_j - M_a )}}{{\sigma_x \sigma_a}}}$$
где $$x_j ,a_j$$ - координаты векторов, $$M_x = \frac{1}{n}\sum\limits_j {x_j}$$ (и аналогично $$M_a$$ ), n - размерность пространства данных, $$\sigma_x = \sqrt {\frac{1}{n}\sum\limits_j {(x_j - M_x )^2}}$$ (и аналогично $$\sigma_a$$ ).
Предполагается, что данные предварительно обрабатываются (нормируются и центрируются) по правилу:
$$x \to \frac{{x_j - M_x}}{{\sigma_x}} .$$
Точно также нормированы и центрированы векторы ядер a. Поэтому все обрабатываемые векторы и ядра принадлежат сечению единичной евклидовой сферы ( ||x||=1 )
Задача поиска ядра для данного класса P имеет своим решением
$$a_P = \sum\limits_{x \in P} x / \left \| \sum\limits_{x \in P} x \right\|$$
В описанных простейших случаях, когда ядро класса точно определяется как среднее арифметическое (или нормированное среднее арифметическое) элементов класса, а решающее правило основано на сравнении выходных сигналов линейных адаптивных сумматоров, нейронную сеть, реализующую метод динамических ядер, называют сетью Кохонена. В определении ядер a для сетей Кохонена входят суммы $$\sum\limits_{x \in P} x$$. Это позволяет накапливать новые динамические ядра, обрабатывая по одному примеру и пересчитывая ai после появления в Pi нового примера. Сходимость при такой модификации, однако, ухудшается.
Закончим раздел рассмотрением различных способов использования полученных классификаторов.
xi и каждого ядра ai вычисляется yi=d(x,ai) (условимся считать, что правильному ядру отвечает максимум d, изменяя, если надо, знак d ); по правилу "победитель забирает все" строка ответов yi преобразуется в строку, где только один элемент, соответствующий максимальному yi, равен 1, остальные - нули. Эта строка и является результатом функционирования сети. По ней может быть определен номер класса (номер места, на котором стоит 1 ) и другие показатели.0 или 1 по правилу "победитель забирает все" (далее называем его слоем базового интерпретатора), надстраивается еще один слой выходных сумматоров. С каждым ( i -м) классом ассоциируется q -мерный выходной вектор zi с координатами zij. Он может формироваться по-разному: от двоичного представления номера класса до вектора ядра класса. Вес связи, ведущей от i -го элемента слоя базового интерпретатора к j -му выходному сумматору определяется в точности как zij. Если на этом i -м элементе базового интерпретатора получен сигнал 1, а на остальных - 0, то на выходных сумматорах будут получены числа zij.x обработан слоем элементов, вычисляющих yi=d(x,ai). Идея дальнейшей обработки состоит в том, чтобы выбрать из этого набора {yi} несколько самых больших чисел и после нормировки объявить их значениями функций принадлежности к соответствующим классам. Предполагается, что к остальным классам объект наверняка не принадлежит. Для выбора семейства G наибольших yi определим следующие числа:$$y_{\max} = \max \{y_i \} ,M_y = \frac{1}{k}\sum\limits_i {y_i ,s = (1 - \alpha )} M_y + \alpha y_{\max}$$
где число $$\alpha$$ характеризует отклонение "уровня среза" s от среднего значения $$M_y$$ $$\alpha \in {\rm{[ - 1}}{\rm{,1]}}$$, по умолчанию обычно принимается $$\alpha =0$$.
Множество $${\rm{J = \{i|y}}_{\rm{i}} \in {\rm{G\}}}$$ трактуется как совокупность номеров тех классов, к которым может принадлежать объект, а нормированные на единичную сумму неотрицательные величины
$$f_i = \frac{{y_i - s}}{{\sum\limits_{j \in J}{(y_i - s)}}}$$
(при $$i \in J$$ и f = 0 в противном случае)
интерпретируются как значения функций принадлежности этим классам.
q -мерный выходной вектор zi. Строится слой из q выходных сумматоров, каждый из которых должен выдавать свою компоненту выходного вектора. Весовые коэффициенты связей, ведущих от того элемента нечеткого классификатора, который вычисляет fi, к j -му выходному сумматору определяются как zij. В итоге вектор выходных сигналов сети есть$$z = \sum\limits_i {f_i z^i}$$
В отдельных случаях по смыслу задачи требуется нормировка fi на единичную сумму квадратов или модулей.
Выбор одного из описанных четырех вариантов использования сети (или какого-нибудь другого) определяется нуждами пользователя. Предлагаемые четыре способа покрывают большую часть потребностей.
За пределами этой лекции остался наиболее универсальный способ обучения нейронных сетей методами гладкой оптимизации - минимизации функции оценки. Ему посвящена следующая лекция.
Работа над лекцией была поддержана Красноярским краевым фондом науки, грант 6F0124.
Вычислительный центр СО РАН в г. Красноярске
Нейронные сети могут все. Но точно также "все" могут машины Тьюринга, интерполяционные многочлены, схемы Поста, ряды Фурье, рекурсивные функции,
Другое дело, что в конечном итоге решение практически любой задачи можно описать, как построение некоторой функции, перерабатывающей исходные данные в результат, но такое очень общее описание не дает никакой информации о способе построения этой функции. Мало иметь универсальные способности - надо для каждого класса задач указать, как применять эти способности. Именно здесь, при рассмотрении методов настройки нейронных сетей для решения задач должны выявиться реальные рамки их применимости. Конечно, такие реальные рамки изменяются со временем из-за открытия новых методов и решений.
В данной лекции описано несколько базовых задач для нейронных сетей и основных или исторически первых методов настройки сетей для их решения:
Начнем мы, однако, не с сетей, а с систем, состоящих из одного элемента.
Даже системы из одного адаптивного сумматора находят очень широкое применение. Вычисление линейных функций необходимо во многих задачах. Вот неполный перечень "специальностей" адаптивного сумматора:
Задача линейной регрессии состоит в поиске наилучшего линейного приближения функции, заданной конечным набором значений: дана выборка значений вектора аргументов x1, ..., xm, заданы значения функции F в этих точках: F(xi)=fi, требуется найти линейную (неоднородную) функцию $$\varphi {\rm{(x) = (}}\alpha {\rm{,x) +}}\alpha_0$$, ближайшую к F. Чтобы однозначно поставить задачу, необходимо доопределить, что значит "ближайшую". Наиболее популярен метод наименьших квадратов, согласно которому $$\varphi$$ ищется из условия
$$\sum\limits_{i = 1}^m {(F(x^i ) - \varphi (x^i ))^2 \to \min}$$
Необходимо особенно подчеркнуть, что метод наименьших квадратов не является ни единственным, ни наилучшим во всех отношениях способом доопределения задачи регрессии. Его главное достоинство - квадратичность минимизируемого критерия и линейность получаемых уравнений на коэффициенты $$\varphi$$.
Явные формулы линейной регрессии легко получить, минимизируя квадратичный критерий качества регрессии. Обозначим
$$\begin{array}{l} \Delta_i = (F(x^i ) - \varphi (x^i ));{\rm{ }}H = \sum\limits_{i = 1}^m {\Delta_i^2}{\rm{=}}\sum\limits_{i = 1}^m {(F(x^i ) - \varphi (x^i ))^2} = \\ = \sum\limits_{i = 1}^m {(f_i - (\alpha ,x^i ) - \alpha_0 )^2}. \\ \end{array}$$
Найдем производные минимизируемой функции H по настраиваемым параметрам:
$$$ {\frac{\partial H}{\partial \alpha_j}}{\rm{ = }}{\sum\limits_{i = 1}^m {\Delta_i x_j^i}{\rm{, (}}j = 1,...,n)}{\rm{; }}{\frac{\partial H}{\partial \alpha_0}}{\rm{ = }}{\sum\limits_{i = 1}^m {\Delta_i}} $$$.
где xij - j -я координата вектора xi.
Приравнивая частные производные H нулю, получаем уравнения, из которых легко найти все $$\alpha_j$$ ( j=0,...,n ). Решение удобно записать в общем виде, если для всех i=1,...,m обозначить $$x_0^i \equiv 1$$ и рассматривать n +1 -мерные векторы данных xi и коэффициентов $$\alpha$$. Тогда
$$\Delta_i = f_i - (\alpha ,x^i ),{\rm{ }}\partial H/\partial \alpha_j = \sum\limits_{i = 1}^m {\Delta_i x_j^i {\rm{ }}(j = 0,1,...,n).}$$
Обозначим p n +1 -мерный вектор с координатами $$p_j = \frac{1}{m}\sum\limits_{i = 1}^m {f_i x_j^i}$$ ; Q - матрицу размером $${\rm{(n + 1)}} \times {\rm{(n + 1)}}$$ с элементами $$q_{jk} = \frac{1}{m}\sum\limits_{i = 1}^m {x_j^i x_k^i}$$.
В новых обозначениях решение задачи линейной регрессии имеет вид:
$$\varphi {\rm{(x) = (}}\alpha {\rm{,x)}}{\rm{,}}\alpha {\rm{= Q}}^{-1}{\rm{p}}.$$
Приведем это решение в традиционных обозначениях математической статистики. Обозначим Mо среднее значение j -й координаты векторов исходной выборки:
$$M_j = \frac{1}{m}\sum\limits_{i = 1}^m {x_j^i} .$$
Пусть M - вектор с координатами Mо. Введем также обозначение sj для выборочного
$$s_j = \sqrt {\frac{1}{m}\sum\limits_{i = 1}^m {(x_j^i} - M_j )^2}$$
Величины sj задают естественный масштаб для измерения j -х координат векторов x. Кроме того, нам потребуются величина sf и коэффициенты корреляции f с j -ми координатами векторов x - rfj:
$$s_f = \sqrt {\frac{1}{m}\sum\limits_{i = 1}^m {(f_i - M_f )^2}}{\rm{,}}M_f = \frac{1}{m}\sum\limits_{i = 1}^m {f_i} ,{\rm{ }}r_{fj} = \frac{{\frac{1}{m}\sum\limits_{i = 1}^m {(f_i - M_f )(x_j^i - M_j )}}}{{s_f s_j}}.$$
Вернемся к n -мерным векторам данных и коэффициентов. Представим, что векторы сигналов проходят предобработку - центрирование и нормировку и далее мы имеем дело с векторами yi:
$$y_j^i = \frac{{x_j^i - M_j}}{{s_j}}.$$
Это, в частности, означает, что все рассматриваемые координаты вектора x имеют ненулевую дисперсию, т.е. постоянные координаты исключаются из рассмотрения - они не несут полезной информации. Уравнения регрессии будем искать в форме: $$\varphi {\rm{(y) = (}}\beta {\rm{,y) +}}\beta_0$$. Получим:
$$\beta_0 {\rm{= M}}_{\rm{f}}{\rm{,}}\beta {\rm{=}}s_{\rm{f}}{\rm{R}}^{-1}{\rm{R}}_{\rm{f}},$$
где Rf - вектор коэффициентов корреляции f с j -ми координатами векторов x, имеющий координаты rfj, R - матрица коэффициентов корреляции между координатами вектора данных:
$$r_{kj} = \frac{{\frac{1}{m}\sum\limits_{i = 1}^m {(x_k^i - M_k )(x_j^i - M_j )}}}{{s_k s_j}} = \frac{1}{m}\sum\limits_{i = 1}^m {y_k^i y_j^i } .$$
В задачах обработки данных почти всегда возникает вопрос о последовательном уточнении результатов по мере поступления новых данных ( обработка данных "на лету" ). Существует, как минимум, два подхода к ответу на этот вопрос для задачи линейной регрессии. Первый подход состоит в том, что изменения в
В рамках первого подхода рассмотрим, как будет изменяться $$\alpha$$ из формулы (2) при добавлении нового вектора данных. В первом порядке теории возмущений найдем изменение вектора коэффициента $$\alpha$$ при изменении вектора p и матрицы Q:
$$\begin{array}{l} \alpha + \Delta \alpha = (Q + \Delta Q)^{-1} (p + \Delta p); \\ (Q + \Delta Q)^{-1} = (Q(1 + Q^{-1} \Delta Q))^{-1} = Q^{-1} - Q^{-1} \Delta QQ^{-1} + o(\Delta Q); \\ \Delta \alpha \cong Q^{-1} (\Delta p - \Delta Q\alpha ). \\ \end{array}$$
Пусть на выборке $$\{x^i \}_{i = 1}^m$$ вычислены p, Q, Q-1. При получении нового вектора данных xm +1 и соответствующего значения F(xm +1)=f m +1 x, y матрица $${\rm{x}} \otimes {\rm{y}}^{\rm{T}}$$ имеет своими элементами $${\rm{x}}_{\rm{j}}{\rm{y}}_{\rm{k}}$$ .
где $$\Delta_{m + 1}^0 = f_{m + 1} - (\alpha ,x^{m + 1} )$$ - ошибка на векторе данных xm +1
Пересчитывая по приведенным формулам p, Q, Q-1 и $$\alpha$$ после каждого получения данных, получаем процесс, в котором последовательно уточняются уравнения линейной регрессии. И требуемый объем памяти, и количество операций имеют порядок n2 - из-за необходимости накапливать и модифицировать матрицу Q-1. Конечно, это меньше, чем потребуется на обычное обращение матрицы Q на каждом шаге, однако следующий простой алгоритм еще экономнее. Он вовсе не обращается к матрицам Q, Q-1 и основан на уменьшении на каждом шаге величины $$(\Delta_{m + 1}^0 )^2 = (f_{m + 1} - (\alpha ,x^{m + 1} ))^2$$ - квадрата ошибки на векторе данных xm +1
Вновь обратимся к формуле (2) и будем рассматривать n +1 -мерные векторы данных и коэффициентов. Обозначим $$x = x^{m + 1} ;{\rm{ }}\Delta = \Delta_{m + 1}^0 = f_{m + 1} - (\alpha ,x^{m + 1} )$$. Тогда
$$grad_\alpha \Delta = - \Delta \times x$$
Последняя элементарная формула столь важна в теории адаптивных сумматоров, что носит "именное название" - формула Уидроу. "Обучение" адаптивного сумматора h - величина шага.
Если при каждом поступлении нового вектора данных x изменять $$\alpha$$ указанным образом, то получим последовательную процедуру построения линейной аппроксимации функции F(x). Такой алгоритм обучения легко реализуется аппаратными средствами (изменение веса связи $$\alpha_j$$ есть произведение прошедшего по ней сигнала xj на ошибку $$\Delta$$ и на величину шага). Возникает, однако, проблема сходимости: если h слишком мало, то сходимость будет медленной, если же слишком велико, то произойдет потеря устойчивости и сходимости не будет вовсе. Детальному изложению этого подхода и его приложений посвящен учебник [2.15].
Задача четкого разделения двух классов по x1, ..., xm и y1,...,ym. Заранее известно, что xi относится к первому классу, а yi - ко второму. Требуется построить решающее правило, то есть определить такую функцию 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.Линейное разделение классов состоит в построении линейного решающего правила - то есть такого вектора $$\alpha$$ и числа $$\alpha_0$$ (называемого порогом), что при $${(x, \alpha )} > {\alpha_0 x}$$ относится к первому классу, а при $${(x, \alpha )} < {\alpha_0}$$ - ко второму.
Поиск такого решающего правила можно рассматривать как разделение классов в проекции на прямую. Вектор $$\alpha$$ задает прямую, на которую ортогонально проектируются все точки, а число $$\alpha_0$$ - точку на этой прямой, отделяющую первый класс от второго.
Простейший и подчас очень удобный выбор состоит в проектировании на прямую, соединяющую центры масс выборок. Центр масс вычисляется в предположении, что массы всех точек одинаковы и равны 1. Это соответствует заданию $$\alpha$$ в виде
Во многих случаях удобнее иметь дело с векторами единичной длины. Нормируя $$\alpha$$, получаем:
$$\alpha = ((y^{1} + y^{2} +... +y^{m})/m - (x^{1} + x^{2} +... + x^{n})/n)/|| (y^{1} + y^{2} +... +y^{m})/m - (x^{1} + x^{2} +... + x ^{n})/n||.$$Выбор $$\alpha_0$$ может производиться из различных соображений. Простейший вариант - посередине между центрами масс выборок:
$$\alpha _{0}=(((y^{1} + y^{2} +... +y^{m})/m,\alpha ) +((x^{1} + x^{2} +... + x ^{n})/n, \alpha ))/2.$$Более тонкие способы построения
Можно для каждого класса построить приближенную плотность вероятностей распределения проекций его точек на прямую (это намного проще, чем для многомерного распределения) и выбирать $$\alpha_0$$, минимизируя вероятность ошибки. Пусть решающее правило имеет вид: при $$(x, \alpha )$$ > $$\alpha_0$$ x относится к первому классу, а при $$(x, \alpha )$$ < $$\alpha_0$$ - ко второму. В таком случае вероятность ошибки будет равна
$$P = p_1 \int\limits_{- \infty}^{\alpha_0}{\rho_1 (\chi )} d\chi + p_2 \int\limits_{\alpha_0}^\infty {\rho_2 (\chi )} d\chi$$
где p1, p2 - априорные вероятности принадлежности объекта соответствующему классу, $$\rho_1 (\chi )$$, $$\rho_2 (\chi )$$ - плотности вероятности для распределения проекций $$\chi$$ точек x в каждом классе.
Приравняв нулю производную вероятности ошибки по $$\alpha_0$$, получим: число $$\alpha_0$$, доставляющее минимум вероятности ошибки, является корнем уравнения:
$${\rm{p}}_1 \rho_1 {\rm{(}}\chi {\rm{) = p}}_2 \rho_2 {\rm{(}}\chi {\rm{)}}{\rm{,}}$$
либо (если у этого уравнения нет решений) оптимальным является правило, относящее все объекты к одному из классов.
Если принять гипотезу о нормальности распределений:
$$\rho (y) = \frac{1}{{\sqrt {2\pi} \sigma}}e^{- (y - a)^2 /2\sigma^2} ,$$
то для определения $$\alpha_0$$ получим:
$$\frac{{p_1}}{{\sqrt {2\pi} \sigma_1}}e^{- (y - a_1 )^2 /2\sigma_1^2} = \frac{{p_2}}{{\sqrt {2\pi} \sigma_2}}e^{- (y - a_2 )^2 /2\sigma_2^2} ,$$ $$\ln (p_1 /p_2 ) - \ln (\sigma_1 /\sigma_2 ) - (y - a_1 )^2 /2\sigma_1^2 + (y - a_2 )^2 /2\sigma_2^2 = 0$$
Если это уравнение имеет два корня $$y=\alpha_1, \alpha_2$$, ( $$\alpha_1 < \alpha_2$$ ) то наилучшим решающим правилом будет: при $$\alpha_1 < {(x, \alpha )} < \alpha_2$$ объект принадлежит одному классу, а при $$\alpha_1 > {(x, \alpha )}$$ или $${(x, \alpha )} > \alpha_2$$ - другому (какому именно, определяется тем, которое из произведений $$p_i \rho_i (\chi )$$ больше). Если корней нет, то оптимальным является отнесение к одному из классов. Случай единственного корня представляет интерес только тогда, когда $$\sigma _{1}=\sigma _{2}$$. При этом уравнение превращается в линейное и мы приходим к исходному варианту - единственной разделяющей точке $$\alpha_0$$.
Таким образом, разделяющее правило с единственной разделяющей точкой $$\alpha_0$$ не является наилучшим для нормальных распределений и надо искать две разделяющие точки.
Если сразу ставить задачу об оптимальном разделении многомерных нормальных распределений, то получим, что наилучшей разделяющей поверхностью является квадрика (на прямой типичная "квадрика" - две точки). Предполагая, что ковариационные матрицы классов совпадают (в одномерном случае это предположение о том, что $$\sigma _{1}=\sigma _{2}$$ ), получаем линейную разделяющую поверхность. Она ортогональна прямой, соединяющей центры выборок не в обычном скалярном произведении, а в специальном: $$\left\langle {x,y} \right\rangle = \left( {x,\Sigma^{-1} y} \right)$$, где $$\Sigma$$ - общая ковариационная матрица классов. За деталями отсылаем к прекрасно написанной книге [2.17], см. также [2.11, 2.12, 2.16].
Важная возможность усовершенствовать разделяющее правило состоит с использовании оценки не просто вероятности ошибки, а среднего риска: каждой ошибке приписывается "цена" ci и минимизируется сумма $${\rm{c}}_1 {\rm{p}}_1 \rho_1 {\rm{(}}\chi {\rm{) + c}}_2 {\rm{p}}_2 \rho_2 {\rm{(}}\chi {\rm{)}}$$. Ответ получается практически тем же (всюду pi заменяются на ci pi ), но такая добавка важна для многих приложений.
Требование безошибочности разделяющего правила на
Возьмем за основу при построении
$${{\rm{(}}{x^i}{\rm{,}}\alpha )} > \alpha_0 {\rm{(i = 1}},...,{\rm{n)}}$$
$${\rm{(y}}^{\rm{i}}{\rm{,}}\alpha {\rm{)}} < \alpha_0 {\rm{(i = 1}},...,{\rm{m)}}$$
Здесь xi ( i=1,..,n ) - векторы из yi ( j=1,..,m ) - ко второму.
Удобно переформулировать задачу. Увеличим размерности всех векторов на единицу, добавив еще одну координату - $$\alpha_0$$ к $$\alpha$$, x0=1 - ко всем x и y0 =1 - ко всем y. Сохраним для новых векторов прежние обозначения - это не приведет к путанице.
Наконец, положим zi = xi ( i=1,...,n ), zj = -yj ( j=1,...,m ).
Тогда получим систему n +m неравенств
$${\rm{(z}}^{\rm{i}}{\rm{,}}\alpha {\rm{)}} > {0 {\rm{(i = 1}},...,{\rm{n +m)}}}$$
которую будем решать относительно $$\alpha$$. Если множество решений непусто, то любой его элемент $$\alpha$$ порождает решающее правило, безошибочное на
x его скалярный квадрат (x,x) больше нуля. Пусть $$\alpha$$ - некоторый вектор, претендующий на роль решения неравенств $${{\rm{(z}}^{\rm{i}}{\rm{,}}\alpha {\rm{)}}} > {0 {\rm{(i = 1}},...,{\rm{n +m)}}}$$, однако часть из них не выполняется. Прибавим те zi, для которых неравенства имеют неверный знак, к вектору $$\alpha$$ и вновь проверим все неравенства $${{\rm{(z}}^{\rm{i}}{\rm{,}}\alpha {\rm{)}}} > 0$$ и т.д. Если они совместны, то процесс сходится за конечное число шагов. Более того, добавление zi к $$\alpha$$ можно производить сразу после того, как ошибка ( $${{\rm{(z}}^{\rm{i}}{\rm{,}}\alpha {\rm{)}}} < 0$$ ) обнаружена, не дожидаясь проверки всех неравенств - и этот вариант алгоритма
тоже сходится [2.2].
Перейдем от одноэлементных систем к нейронным сетям. Пусть $$\alpha_{ij}$$ - вес связи, ведущей от j -го нейрона к i -му (полезно обратить внимание на порядок индексов). Для полносвязных сетей определены значения $$\alpha_{ij}$$ при всех i,j, для других архитектур связи, ведущие от j -го нейрона к i -му для некоторых i,j не определены. В этом случае положим $$\alpha_{ij} = 0$$.
В данном разделе речь пойдет в основном о полносвязных сетях. Пусть на выходах всех нейронов получены сигналы xj ( j -номер нейрона). Обозначим x вектор этих выходных сигналов. Прохождение вектора сигналов x через сеть связей сводится к умножению матрицы ( $$\alpha_{ij}$$ ) на вектор сигналов x. В результате получаем вектор входных сигналов нелинейных элементов нейронов: $$y_i = \sum\limits_j {\alpha_{ij} x_j}$$.
Это соответствие " прохождение сети $$\equiv$$ умножение матрицы связей на вектор сигналов " является основой для перевода обычных численных методов на нейросетевой язык и обратно. Практически всюду, где основной операцией является умножение матрицы на вектор, применимы нейронные сети. С другой стороны, любое устройство, позволяющее быстро осуществлять такое умножение, может использоваться для реализации нейронных сетей.
В частности, вычисление градиента квадратичной формы $$$ {H =}{{\frac{1}{2}}{\rm{(}}{{x,Qx)}}} $$$ может осуществляться полносвязной сетью с симметричной матрицей связей: $${\rm{grad}}H = Qx$$ ( $$\alpha_{ij} = q_{ij} = q_{ji}$$ ). Именно это наблюдение лежит в основе данного раздела.
Что можно сделать, если мы умеем вычислять градиент квадратичной формы?
В первую очередь, можно x через сеть с весами связей $$\alpha_{ij} = q_{ij} = q_{ji}$$ при условии, что на входной сумматор каждого нейрона по дополнительной связи веса b подается стандартный единичный сигнал.
Зададим теперь функционирование сети формулой
$$x' = x - h{\rm{grad}}P = x - h(Qx + b)$$
Нелинейных элементов вовсе не нужно! Каждый ( j -й) нейрон имеет входные веса $$\alpha_{ij} = - hq_{ij}$$ для связей с другими нейронами ( $${\rm{i}} \ne {\rm{j}}$$ ), вес $$- b_j$$ для постоянного единичного входного сигнала и вес $$\alpha_{jj} = 1 - hq_{jj}$$ для связи нейрона с самим собой (передачи на него его же сигнала с предыдущего шага). Выбор шага h>0 может вызвать затруднение (он зависит от коэффициентов минимизируемого многочлена). Есть, однако, простое решение: в каждый момент дискретного времени T выбирается свое значение $$h_T$$. Достаточно, чтобы шаг стремился со временем к нулю, а сумма шагов - к бесконечности (например, $$h_T = \frac{1}{T}$$, или $$h_T = \frac{1}{{\sqrt T}}$$ ).
Итак, простая симметричная полносвязная сеть без нелинейных элементов может
Решение системы линейных уравнений $$Ax = b$$ сводится к минимизации многочлена
$$P = \frac{1}{2}((Ax - b),(Ax - b)) = \frac{1}{2}(x,A^{\rm T} Ax) - (A^{\rm T} b,x) - \frac{1}{2}(b,b).$$
Поэтому решение системы может производиться нейронной сетью. Простейшая сеть, вычисляющая градиент этого многочлена, не полносвязна, а состоит из двух слоев: первый с матрицей связей A, второй - с транспонированной матрицей $$A^{\rm T}$$. Постоянный единичный сигнал подается на связи с весами $$b_j$$ на первом слое. Минимизация этого многочлена, а значит и
Небольшая модификация позволяет вместо безусловного минимума многочлена второго порядка P искать точку условного минимума с условиями $$x_i = c_i$$ для $$i = i_1 ,...,i_k$$, то есть точку минимума P в ограничении на аффинное многообразие, параллельное некоторым координатным плоскостям. Для этого вместо формулы
$$x' = x - h{\rm{grad}}P = x - h(Qx + b)$$
следует использовать:
$$x'_i = c_i$$ при $$i = i_1 ,...,i_k ;$$
$$x'_i = x_i - h\frac{{\partial P}}{{\partial x_i}} = x_i - h\left( {\sum\limits_j {q_{ij} x_j} + b_i} \right)$$ при $${i \ne i_1 ,...,i_k}$$.
Устройство, способное находить точку условного минимума многочлена второго порядка при условиях вида $$x_i = c_i$$ для $$i = i_1 ,...,i_k$$ позволяет решать важную задачу - заполнять пробелы в данных (и, в частности, строить линейную регрессию).
Предположим, что получаемые в ходе испытаний векторы данных подчиняются многомерному нормальному распределению:
$$\rho (x) = Ce^{- \frac{1}{2}((x - {\bf{M}}x),Q(x - {\bf{M}}x))},$$
где Mx - вектор математических ожиданий координат, $$Q = \Sigma^{-1}$$, $$\Sigma$$ - ковариационная матрица, n - размерность пространства данных,
$$C = \frac{1}{{(2\pi )^{n/2} \sqrt {\det \Sigma}}} .$$
Напомним определение матрицы $$\Sigma$$: $$(\Sigma )_{ij} = {\bf{M}}((x_i - {\bf{M}}x_i )(x_j - {\bf{M}}x_j ))$$,
где M - символ математического ожидания, нижний индекс соответствует номеру координаты.
В частности, простейшая оценка ковариационной матрицы по выборке дает:
$$S = \frac{1}{m}\sum\limits_j {(x^j - {\bf{M}}x)} \otimes ({\bf{M}}x^j - {\bf{M}}x)^{\rm T},$$
где m - число элементов в выборке, верхний индекс j - номер вектора данных в выборке, верхний индекс Т означает транспонирование, а $$\otimes$$ - произведение вектора-столбца на вектор-строку (тензорное произведение).
Пусть у вектора данных x известно несколько координат: $$x_i = c_i$$ для $$i = i_1 ,...,i_k$$. Наиболее вероятные значения неизвестных координат должны доставлять условный максимум показателю нормального распределения - многочлену второго порядка $$((x - {\bf{M}}x),Q(x - {\bf{M}}x))$$ (при условии $$x_i = c_i$$ для $$i = i_1 ,...,i_k$$ ). Эти же значения будут условными математическими ожиданиями неизвестных координат при заданных условиях.
Таким образом, чтобы построить сеть, заполняющую пробелы в данных, достаточно сконструировать сеть для поиска точек условного минимума многочлена
$$((x - {\bf{M}}x),Q(x - {\bf{M}}x))$$
при условиях следующего вида: $$x_i = c_i$$ для $$i = i_1 ,...,i_k$$. Матрица связей Q выбирается из условия $$Q = \Sigma^{-1}$$, где $$\Sigma$$ - ковариационная матрица (ее оценка по выборке).
На первый взгляд, пошаговое накопление $$Q = \Sigma^{-1}$$ по мере поступления данных требует слишком много операций - получив новый вектор данных требуется пересчитать оценку $$\Sigma,$$ а потом вычислить $$Q = \Sigma^{-1}$$. Можно поступать и по-другому, воспользовавшись формулой приближенного обрашения матриц первого порядка точности:
$$(\Sigma + \varepsilon \Delta )^{-1} = \Sigma^{-1} - \varepsilon \Sigma^{-1} \Delta \Sigma^{-1} + o(\varepsilon ).$$
Если же добавка $$\Delta$$ имеет вид $$\Delta = y \otimes y^{\rm T}$$, то
$$(\Sigma + \varepsilon \Delta )^{-1} = \Sigma^{-1} - \varepsilon (\Sigma^{-1} y) \otimes (\Sigma^{-1} y)^{\rm T} + o(\varepsilon ).$$
Заметим, что решение задачи (точка условного минимума многочлена) не меняется при умножении Q на число. Поэтому полагаем:
$$Q_0 = 1,{\rm{ }}Q_{k + 1} = Q_k + \varepsilon (Q_k (x^{k + 1} - ({\bf{M}}x)^{k + 1} )) \otimes (Q_k (x^{k + 1} - ({\bf{M}}x)^{k + 1} ))^{\rm T} ,$$
где 1 - единичная матрица, $$\varepsilon >0$$ - достаточно малое число, $$x^{k + 1}$$ - k +1 -й вектор данных, $$({\bf{M}}x)^{k + 1}$$ - среднее значение вектора данных, уточненное с учетом $$x^{k + 1}$$:
$$({\bf{M}}x)^{k + 1} = \frac{1}{{k + 1}}(k({\bf{M}}x)^k + x^{k + 1} )$$
В формуле для пошагового накопления матрицы Q ее изменение $$\Delta Q$$ при появлении новых данных получается с помощью вектора $$y=x^{k + 1} - ({\bf{M}}x)^{k + 1}$$, пропущенного через сеть: $$(\Delta Q)_{ij} = \varepsilon z_i z_j$$, где z=Qy. Параметр $$\varepsilon$$ выбирается достаточно малым для того, чтобы обеспечить положительную определенность получаемых матриц (и, по возможности, их близость к истинным значениям Q ).
Описанный процесс формирования сети можно назвать обучением. Вообще говоря, можно проводить формальное различение между формированием сети по явным формулам и по алгоритмам, не использующим явных формул для весов связей ( неявным ). Тогда термин "обучение" предполагает неявные алгоритмы, а для явных остается название "формирование". Здесь мы такого различия проводить не будем.
Если при обучении сети поступают некомплектные данные $$x^{k + 1}$$ с отсутствием значений некоторых координат, то сначала эти значения восстанавливаются с помощью имеющейся сети, а потом используются в ее дальнейшем обучении.
Во всех задачах оптимизации существенную роль играет вопрос о правилах остановки: когда следует прекратить циклическое функционирование сети, остановиться и считать полученный результат ответом? Простейший выбор - остановка по малости изменений: если изменения сигналов сети за цикл меньше некоторого фиксированного малого $$\sigma$$ (при использовании переменного шага $$\sigma$$ может быть его функцией), то оптимизация заканчивается.
До сих пор речь шла о минимизации положительно определенных квадратичных форм и многочленов второго порядка. Однако самое знаменитое приложение полносвязных сетей связано с увеличением значений положительно определенных квадратичных форм. Речь идет о системах ассоциативной памяти [2.4, 2.5, 2.6, 2.7, 2.9, 2.10, 2.12].
Предположим, что задано несколько эталонных векторов данных $$x^1 ,...,x^m$$ и при обработке поступившего на вход системы вектора x требуется получить на выходе ближайший к нему эталонный вектор. Мерой сходства в простейшем случае будем считать косинус угла между векторами - для векторов фиксированной длины это просто скалярное произведение. Можно ожидать, что изменение вектора x по закону
$$x' = x + h\sum\limits_k {x^k (x^k ,x)} ,$$
где h - малый шаг, приведет к увеличению проекции x на те эталоны, скалярное произведение на которые $$(x^k ,x)$$ больше.
Ограничимся рассмотрением эталонов, и ожидаемых результатов обработки с координатами $$\pm 1$$. Развивая изложенную идею, приходим к дифференциальному уравнению
$$\begin{array}{l} \frac{{dx}}{{dt}} = - {\rm{grad}}H, \\ H = H_0 + \theta H_1 ,{\rm{ }}H_0 (x) = - \frac{1}{2}\sum\limits_k {(x^k ,x)}^2 ,{\rm{ }}H_1 (x) = \frac{1}{2}\sum\limits_i {(x_i^2 - 1)^2 ,} \\ {\rm{grad}}H_0 = - \sum\limits_k {x^k (x^k ,x)} ,{\rm{(grad}}H_1 )_j = (x_j^2 - 1)x_j , \\ \end{array}$$
где верхними индексами обозначаются номера векторов-эталонов, нижними - координаты векторов.
Функция H называется " энергией " сети, она минимизируется в ходе функционирования. Слагаемое $$H_0$$ вводится для того, чтобы со временем возрастала проекция вектора x на те эталоны, которые к нему ближе, слагаемое $$H_1$$ обеспечивает стремление координат вектора x к $$\pm 1$$. Параметр $$\theta$$ определяет соотношение между интенсивностями этих двух процессов. Целесообразно постепенно менять $$\theta$$ со временем, начиная с малых $$\theta <1$$, и приходя в конце концов к $$\theta >1$$.
Подробнее системы ассоциативной памяти рассмотрены в отдельной лекции. Здесь же мы ограничимся обсуждением получающихся весов связей. Матрица связей построенной сети определяется функцией $$H_0$$, так как $${\rm{(grad}}H_1 )_j = (x_j^2 - 1)x_j$$ вычисляется непосредственно при j -м нейроне без участия сети. Вес связи между i -м и j -м нейронами не зависит от направления связи и равен
$$\alpha_{ij} = \sum\limits_k {x_i^k x_j^k}$$
Эта простая формула имеет чрезвычайно важное значение для развития теории нейронных сетей. Вклад k -го эталона в связь между i -м и j -м нейронами ( $$x_i^k x_j^k$$ ) равен +1, если i -я и j -я координаты этого эталона имеют одинаковый знак, и равен -1, если они имеют разный знак.
В результате возбуждение i -го нейрона передается j -му (и симметрично, от j -го к i -му), если у большинства эталонов знак i -й и j -й координат совпадают. В противном случае эти нейроны тормозят друг друга: возбуждение i -го ведет к торможению j -го, торможение i -го - к возбуждению j -го (воздействие j -го на i -й симметрично). Это правило образования ассоциативных связей (правило Хебба) сыграло огромную роль в теории нейронных сетей.
Построение отношений на множестве объектов - одна из самых загадочных и открытых для творчества областей применения искусственного интеллекта. Первым и наиболее распространенным примером этой задачи является классификация без учителя. Задан набор объектов, каждому объекту сопоставлен вектор значений признаков (строка таблицы). Требуется разбить эти объекты на классы эквивалентности.
Естественно, прежде, чем приступать к решению этой задачи, нужно ответить на один вопрос: зачем производится это разбиение и что мы будем делать с его результатом? Ответ на него позволит приступить к формальной постановке задачи, которая всегда требует компромисса между сложностью решения и точностью формализации: буквальное следование содержательному смыслу задачи нередко порождает сложную вычислительную проблему, а следование за простыми и элегантными алгоритмами может привести к противоречию со здравым смыслом.
Итак, зачем нужно строить отношения эквивалентности между объектами? В первую очередь - для фиксации знаний. Люди накапливают знания о классах объектов - это практика многих тысячелетий, зафиксированная в языке: знание относится к имени класса (пример стандартной древней формы: "люди смертны", "люди" - имя класса). В результате классификации как бы появляются новые имена и правила их присвоения.
Для каждого нового объекта мы должны сделать два дела:
Какую форму могут иметь правила отнесения к классу? Веками освящена традиция представлять класс его "типичным", "средним", "идеальным" и т.п. элементом. Этот типичный объект является идеальной конструкцией, олицетворяющей класс.
Отнесение объекта к классу проводится путем его сравнения с типичными элементами разных классов и выбора ближайшего. Правила, использующие типичные объекты и меры близости для их сравнения с другими, очень популярны и сейчас.
Простейшая мера близости объектов - квадрат
Мы не оговариваем специально существование априорных ограничений, налагаемых на новые объекты - естественно, что "вселенная" задачи много 'уже и гораздо определеннее Вселенной.
Другая мера близости, естественно возникающая при обработке сигналов, изображений и т.п. - квадрат коэффициента корреляции (чем он больше, тем ближе объекты). Возможны и иные варианты - все зависит от задачи.
Если число классов m заранее определено, то задачу классификации без учителя можно поставить следующим образом.
Пусть {xp} - векторы значений признаков для рассматриваемых объектов и в пространстве таких векторов определена мера их близости $$\rho {x,y}$$. Для определенности примем, что чем ближе объекты, тем меньше $$\rho.$$ С каждым классом будем связывать его типичный объект. Далее называем его ядром класса. Требуется определить набор из m ядер y1, y2, ... ym и разбиение {xp} на классы:
$$\{x^p \} = Y_1 \cup Y_2 \cup ... \cup Y_m$$
минимизирующее следующий критерий
$$Q = \sum\limits_{i = 1}^m {D_i \to \min} ,$$
где для каждого ( i -го) класса $$D_i$$ - сумма расстояний от принадлежащих ему точек выборки до ядра класса:
$$D_i = \sum\limits_{x^p \in Y_i}{\rho (x^p ,y^i )}$$
Минимум Q берется по всем возможным положениям ядер $$y^i$$ и всем разбиениям {xp} на m классов Yi.
Если число классов заранее не определено, то полезен критерий слияния классов: классы Yi и Yj сливаются, если их ядра ближе, чем среднее расстояние от элемента класса до ядра в одном из них. (Возможны варианты: использование среднего расстояния по обоим классам, использование порогового коэффициента, показывающего, во сколько раз должно расстояние между ядрами превосходить среднее расстояние от элемента до ядра и др.)
Использовать критерий слияния классов можно так: сначала принимаем гипотезу о достаточном числе классов, строим их, минимизируя Q, затем некоторые Yi объединяем, повторяем минимизацию Q с новым числом классов и т.д.
Существует много эвристических алгоритмов классификации без учителя, основанных на использовании мер близости между объектами. Каждый из них имеет свою область применения, а наиболее распространенным недостатком является отсутствие четкой формализации задачи: совершается переход от идеи кластеризации прямо к алгоритму, в результате неизвестно, что ищется (но что-то в любом случае находится, иногда - неплохо).
Сетевые алгоритмы классификации без учителя строятся на основе итерационного метода динамических ядер. Опишем его сначала в наиболее общей абстрактной форме. Пусть задана выборка предобработанных векторов данных {xp}. Пространство векторов данных обозначим E. Каждому классу будет соответствовать некоторое ядро a. Пространство ядер будем обозначать A. Для каждых $$x \in E$$ и $$a \in A$$ определяется мера близости d(x,a). Для каждого набора из k ядер a1,...,ak и любого разбиения {xp} на k классов $${\rm{\{x}}^{\rm{p}}{\rm{\} = P}}_{\rm{1}} \cup {\rm{P}}_{\rm{2}} \cup ... \cup {\rm{P}}_{\rm{k}}$$ определим критерий качества:
$$D = D(a_1 ,a_2 ,...,a_k ,P_1 ,P_2 ,...P_k ) = \sum\limits_{i = 1}^k {\sum\limits_{x \in P_i}{d(x,a_i )}}$$
Требуется найти набор a1,...,ak и разбиение $${\rm{\{x}}^{\rm{p}}{\rm{\} = P}}_{\rm{1}} \cup {\rm{P}}_{\rm{2}} \cup ... \cup {\rm{P}}_{\rm{k}}$$, минимизирующие D.
Шаг алгоритма разбивается на два этапа:
a1,...,ak ищем минимизирующее критерий качества D разбиение $${\rm{\{x}}^{\rm{p}}{\rm{\} = P}}_{\rm{1}} \cup {\rm{P}}_{\rm{2}} \cup ... \cup {\rm{P}}_{\rm{k}}$$ ; оно дается решающим правилом: $$x \in P_i$$, если d(x, ai)<d(x, aj) при $${\rm{i}} \ne {\rm{j}}$$, в том случае, когда для x минимум d(x,a) достигается при нескольких значениях i, выбор между ними может быть сделан произвольно;Pi ( i=1,...,k ), полученного на первом этапе, ищется $$a_I \in A$$, минимизирующее критерий качества (т.е. слагаемое в D для данного $$i-D_i = \sum\limits_{x \in P_i}{d(x,a_i )}$$Начальные значения a1,...,ak, $${\rm{\{x}}^{\rm{p}}{\rm{\} = P}}_{\rm{1}} \cup {\rm{P}}_{\rm{2}} \cup ... \cup {\rm{P}}_{\rm{k}}$$ выбираются произвольно, либо по какому-нибудь эвристическому правилу.
На каждом шаге и этапе алгоритма уменьшается критерий качества D, отсюда следует сходимость алгоритма - после конечного числа шагов разбиение $${\rm{\{x}}^{\rm{p}}{\rm{\} = P}}_{\rm{1}} \cup {\rm{P}}_{\rm{2}} \cup ... \cup {\rm{P}}_{\rm{k}}$$ уже не меняется.
Если ядру ai сопоставляется элемент сети, вычисляющий по входному сигналу x функцию d(x,ai), то решающее правило для классификации дается интерпретатором "победитель забирает все": элемент x принадлежит классу Pi, если выходной сигнал i -го элемента d(x,ai) меньше всех остальных
Единственная вычислительная сложность в алгоритме может состоять в поиске ядра по классу на втором этапе алгоритма, т.е. в поиске $$a \in A$$, минимизирующего $$D_i = \sum\limits_{x \in P_i}{d(x,a)}$$
В связи с этим, в большинстве конкретных реализаций метода мера близости d выбирается такой, чтобы легко можно было найти a, минимизирующее D для данного P.
В простейшем случае пространство ядер A совпадает с пространством векторов x, а мера близости d(x,a) - положительно определенная квадратичная форма от x-a, например, квадрат ai, минимизирующее Di, есть центр тяжести класса Pi:
$$a_i = \frac{1}{{|P_i |}}\sum\limits_{x \in P_i} x ,$$
где |Pi| - число элементов в Pi.
В этом случае также упрощается и решающее правило, разделяющее классы. Обозначим d(x,a) =(x-a,x-a), где (.,.) - билинейная форма (если d - квадрат x и a, то (.,.) - обычное скалярное произведение). В силу билинейности
d(x,a)=(x-a,x-a)=(x,x)-2(x,a) +(a,a).
Чтобы сравнить d(x,ai) для разных i и найти среди них минимальное, достаточно вычислить линейную неоднородную функцию от x:
d1(x,ai) = (ai,ai)-2(x,ai).
Минимальное значение d(x,ai) достигается при том же i, что и минимум d1(x,ai), поэтому решающее правило реализуется с помощью k сумматоров, вычисляющих d(x,a) и интерпретатора, выбирающего сумматор с минимальным выходным сигналом. Номер этого сумматора и есть номер класса, к которому относится x.
Пусть теперь мера близости - коэффициент корреляции между вектором данных и ядром класса:
$$d(x,a) = r(x,a) = \sum\limits_j {\frac{{(x_j - M_x )(a_j - M_a )}}{{\sigma_x \sigma_a}}}$$
где $$x_j ,a_j$$ - координаты векторов, $$M_x = \frac{1}{n}\sum\limits_j {x_j}$$ (и аналогично $$M_a$$ ), n - размерность пространства данных, $$\sigma_x = \sqrt {\frac{1}{n}\sum\limits_j {(x_j - M_x )^2}}$$ (и аналогично $$\sigma_a$$ ).
Предполагается, что данные предварительно обрабатываются (нормируются и центрируются) по правилу:
$$x \to \frac{{x_j - M_x}}{{\sigma_x}} .$$
Точно также нормированы и центрированы векторы ядер a. Поэтому все обрабатываемые векторы и ядра принадлежат сечению единичной евклидовой сферы ( ||x||=1 )
Задача поиска ядра для данного класса P имеет своим решением
$$a_P = \sum\limits_{x \in P} x / \left \| \sum\limits_{x \in P} x \right\|$$
В описанных простейших случаях, когда ядро класса точно определяется как среднее арифметическое (или нормированное среднее арифметическое) элементов класса, а решающее правило основано на сравнении выходных сигналов линейных адаптивных сумматоров, нейронную сеть, реализующую метод динамических ядер, называют сетью Кохонена. В определении ядер a для сетей Кохонена входят суммы $$\sum\limits_{x \in P} x$$. Это позволяет накапливать новые динамические ядра, обрабатывая по одному примеру и пересчитывая ai после появления в Pi нового примера. Сходимость при такой модификации, однако, ухудшается.
Закончим раздел рассмотрением различных способов использования полученных классификаторов.
xi и каждого ядра ai вычисляется yi=d(x,ai) (условимся считать, что правильному ядру отвечает максимум d, изменяя, если надо, знак d ); по правилу "победитель забирает все" строка ответов yi преобразуется в строку, где только один элемент, соответствующий максимальному yi, равен 1, остальные - нули. Эта строка и является результатом функционирования сети. По ней может быть определен номер класса (номер места, на котором стоит 1 ) и другие показатели.0 или 1 по правилу "победитель забирает все" (далее называем его слоем базового интерпретатора), надстраивается еще один слой выходных сумматоров. С каждым ( i -м) классом ассоциируется q -мерный выходной вектор zi с координатами zij. Он может формироваться по-разному: от двоичного представления номера класса до вектора ядра класса. Вес связи, ведущей от i -го элемента слоя базового интерпретатора к j -му выходному сумматору определяется в точности как zij. Если на этом i -м элементе базового интерпретатора получен сигнал 1, а на остальных - 0, то на выходных сумматорах будут получены числа zij.x обработан слоем элементов, вычисляющих yi=d(x,ai). Идея дальнейшей обработки состоит в том, чтобы выбрать из этого набора {yi} несколько самых больших чисел и после нормировки объявить их значениями функций принадлежности к соответствующим классам. Предполагается, что к остальным классам объект наверняка не принадлежит. Для выбора семейства G наибольших yi определим следующие числа:$$y_{\max} = \max \{y_i \} ,M_y = \frac{1}{k}\sum\limits_i {y_i ,s = (1 - \alpha )} M_y + \alpha y_{\max}$$
где число $$\alpha$$ характеризует отклонение "уровня среза" s от среднего значения $$M_y$$ $$\alpha \in {\rm{[ - 1}}{\rm{,1]}}$$, по умолчанию обычно принимается $$\alpha =0$$.
Множество $${\rm{J = \{i|y}}_{\rm{i}} \in {\rm{G\}}}$$ трактуется как совокупность номеров тех классов, к которым может принадлежать объект, а нормированные на единичную сумму неотрицательные величины
$$f_i = \frac{{y_i - s}}{{\sum\limits_{j \in J}{(y_i - s)}}}$$
(при $$i \in J$$ и f = 0 в противном случае)
интерпретируются как значения функций принадлежности этим классам.
q -мерный выходной вектор zi. Строится слой из q выходных сумматоров, каждый из которых должен выдавать свою компоненту выходного вектора. Весовые коэффициенты связей, ведущих от того элемента нечеткого классификатора, который вычисляет fi, к j -му выходному сумматору определяются как zij. В итоге вектор выходных сигналов сети есть$$z = \sum\limits_i {f_i z^i}$$
В отдельных случаях по смыслу задачи требуется нормировка fi на единичную сумму квадратов или модулей.
Выбор одного из описанных четырех вариантов использования сети (или какого-нибудь другого) определяется нуждами пользователя. Предлагаемые четыре способа покрывают большую часть потребностей.
За пределами этой лекции остался наиболее универсальный способ обучения нейронных сетей методами гладкой оптимизации - минимизации функции оценки. Ему посвящена следующая лекция.
Работа над лекцией была поддержана Красноярским краевым фондом науки, грант 6F0124.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.