Контрастирование (редукция) нейронной сети

Показатели значимости вычисляются в два этапа: сначала они оцениваются для одного вектора (примера), потом для всей выборки.

1. Для данного $$x^p$$ значимости $$w_k$$ и $$x_j$$ оцениваются как

$$\begin{align*} \chi(w_k|x^p)=|\partial H(x^{p},w)/ \partial w_k| \times | w_k - w_{k}^{0}|,\\ \chi(x_{j}^{p} |x^p)=|\partial H(x^{p},w)/ \partial x_{j}^{p}| \times |x_{j}^{p} - {x_{j}^{p}}^0|. \end{align*} $$

Здесь $$\chi$$ - вычисленные в линейном приближении абсолютные величины изменения $$H$$ при сокращении описания. Оценка на всей выборке $$x^p, p=1, \ldots, n$$ может проводиться по-разному. Например, может использоваться одна из следующих норм:

1. Сумма модулей:

$$\begin{align*} \chi(w_k)= \sum_p \chi(w_k|x^p),\\ \chi(x_j)= \sum_p \chi(x_j|x^p).\vspace{-2mm} \end{align*} $$

2. Максимум модуля

$$\begin{align*} \chi(w_k)= \max_p \chi(w_k|x^p),\\ \chi(x_j)= \max_p \chi(x_j|x^p). \end{align*} $$

Часто приходится иметь дело с системой, которая меняет свои параметры (например, в ходе обучения). Тогда к моменту принятия решения о значимости может быть накоплена информация о частных производных $$H$$ в разных точках $$w \in \{w_1, \ldots, w_q\}$$. Ее можно использовать следующим образом.

Обозначим угловыми скобками процедуру усреднения по множеству параметров $$\{w^1, \ldots, w^q\}$$:

$$\begin{align*} < f(w,\ldots)> = (1/q)\sum_{i=1}^q f(w^s,\ldots) \end{align*}$$

положим

$$\begin{align*} \chi(w_{k}|x^{p})= < |\partial H(x,w)/ \partial w_{{k|\chi = \chi}^p} > \cdot w_k - |w_{k}^{0}|,\\ \chi(x_{j}|x^{p})= < |\partial H(x,w)/ \partial x_{{j|\chi = \chi}^p} > \cdot x_{j}^{p} - |{x_{j}^{p}}^{0}|. \end{align*} $$

Усредняются абсолютные значения производных, а приращения берутся в тех точках, в которых будет проводиться процедура сокращения описания. Усреднение параметров $$w$$ по нескольким значениям важно для нелинейных систем, в которых производные $$H$$ могут сильно меняться от точки к точке.

Главная задача при сокращении описания - сохранить качество работы системы, оцениваемое с помощью $$H$$. Для этого требуется знать назначение системы и иметь способ оценки ее соответствия своему назначению.

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

Определение значимости параметров по изменению выходных сигналов системы

Значимость параметров определяется практически так же, как и с помощью функции оценки. Пусть $$x$$ - вектор данных, а $$w$$ - вектор параметров. Пусть задан набор векторов $$\{x^p\}$$, на которых будет оцениваться функционирование системы, и определены значения $$x_j^{p0}, w_k^0$$ (в простейшем случае $$w_k^0 = 0, x_{j}^{p0} = (1/n) \sum_{p=1}^n x_j^p$$ ).

Вычислим в линейном приближении изменение вектора $$F$$ при обращении $$w_k$$ в $$w_k^0$$ и $$x_j^p$$ в $$x_j^{p0}$$:

$$\begin{align*} \Delta F= \partial F(x,w)/ \partial w_{{k|\chi = \chi}^p} \times (w_{k}^{0} - w_k),\\ \Delta F= \partial F(x,w)/ \partial x_{{j|\chi = \chi}^p} \times (x_{j}^{p} - {x_{j}^{p}}^{0}). \end{align*} $$

Пусть в пространстве выходных сигналов системы задана некоторая норма (например, евклидова). Тогда положим:

$$\begin{align*} \chi(w_{k}|x^{p})=\|\partial F(x,w)/ \partial w_{k}\|_{\chi = \chi^p} \times |w_{k}^{0} - w_k|,\\ \chi(x_{j}|x^{p})=\|\partial F(x,w)/ \partial x_{j}\|_{\chi = \chi^p} \times |x_{j}^{p} - {x_{j}^{p}}^{0}|. \end{align*} $$

Таким образом, для каждого $$w_k$$ и любого $$x_j$$ определен вектор показателей значимости. Координаты вектора соответствуют точкам $$x^p$$. Теперь нужно вычислить норму этого вектора и объявить ее показателем значимости (можно в качестве нормы взять максимум модуля или сумму модулей). При использовании евклидовой нормы в пространстве выходных сигналов бывает удобно и далее выбирать такую же норму, полагая:

$$\begin{align*} \chi(w_k)= (\sum_p \chi(w_k|x^p)^2)^{1/2},\\ \chi(x_j)= (\sum_p \chi(x_j|x^p)^2)^{1/2}. \end{align*} $$

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

Сокращение числа выходов в адаптивном линейном сумматоре (путь "снизу вверх")

Рассмотрим адаптивный линейный сумматор, вычисляющий линейную функцию $$F(x,w) = w_0 + (x,w)$$.

Решим задачу о сокращении числа выходных сигналов. Рассмотрим определение значимости по изменению выходного сигнала. Заметим, что:

$$\begin{align*} \partial F/ \partial w_0 = 1,\quad \partial F/ \partial w_{{i|\chi = \chi}^p} = x_i^p ,\quad \partial F/ \partial w_{i}|_{\chi = \chi^p} = w_i, i = 1, \ldots, N. \end{align*} $$

Уничтожить $$i$$ -й выходной сигнал можно двумя способами:

заменой параметра $$w_i$$ на 0;

заменой $$x_i$$ на постоянную величину не зависящую от $$p$$.

В последнем случае получаем новую функцию

$$\begin{align*} F_{1i} = w_0 + x_i^0 w_i + \sum_{j=1,j\neq i}^N x_j w_j \end{align*} $$

Такое преобразование означает, что одновременно с уничтожением $$i$$ -й выходной связи $$w_0$$ приобретает новое значение:

$$\begin{align*} w_0:= w_0 + x_i^0 w_i. \end{align*} $$

При этом можно добиться меньшего изменения $$F(x,w)$$, чем просто при приравнивании $$w_i$$ к нулю. Поэтому остановимся на замене $$i$$ -го выходного сигнала на постоянную величину $$x_i^0$$. Значение этой постоянной определим исходя из минимизации изменения $$F(x^p,w)$$. Минимизация этого изменения, вычисленного в евклидовой норме, дает:

$$\begin{align*} x_i^0 = (1/n)\sum_{p=1}^n x_i^p \end{align*} $$

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

$$\begin{align*} x_i^0 = M(x_i),\chi(x_i) = n^{1/2} w_i \sigma(x_i). \end{align*} $$

где $$\sigma(x_i)$$ - среднеквадратичное отклонение от $$x_i^0$$ на выборке $$\{x^p\}$$.

Значимость замены оценивается как

$$\begin{align*} \chi(x_i) =|w_i| \sigma(x_i). \end{align*} $$

При исключении сигналов по одному, они сортируются в соответствии со значениями $$\chi(x_i)$$ и отбрасываются (заменяются средним) сначала те, что соответствуют меньшим $$\chi(x_i)$$. Заметим, что поэтому путь "снизу вверх" универсален, но не оптимален. В частности, для сумматоров и других элементов, линейных по параметрам (например, квадратичных сумматоров), существует учитывающий все корреляции путь исключения "сверху вниз" с ортогонализацией. Далее ограничимся оценкой значимости по изменению выходного сигнала.

Показатели значимости для нейрона с дифференцируемым нелинейным элементом

Эти показатели ищутся почти так же как для сумматора. Пусть

$$\begin{align*} F(x,w) = \varphi (w_0+(x,w)) \end{align*}$$

тогда

$$\begin{align*} \partial F/ \partial x_{i|x=x^p} = \varphi'(w_0+(x^p,w))\cdot w_i. \end{align*} $$

В евклидовой норме (что соответствует методу наименьших квадратов) получаем:

$$\begin{align*} \chi(x_i) =|w_i|[\sum_p(\varphi'(w_0+(x^p,w)))^2(x_i^p - M(x_i))^2]^{1/2}, \end{align*} $$

т.е. произведение модуля параметра $$w_i$$ на среднеквадратичное отклонение с весами. Роль веса играет квадрат производной функции в точке $$w_0+(x^p,w)$$.

Показатели значимости для нейрона с пороговым нелинейным элементом (персептрона)

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

$$F(x,w) = h(w_0+(x,w)),\\ h(x) = \{1, x>0,\\ 0,x \leqslant 0\}$$

Для каждого вектора данных $$x^p$$ необходимо оценить значимость изменения аргумента функции $$h$$ при замене $$x_i^p$$ на $$x_i^0$$. Значение $$h(a)$$ меняется только тогда, когда $$a$$ меняет знак, поэтому естественно оценивать значимость изменения $$\Delta a$$ переменной $$a$$ в масштабе, определенном текущем значением переменной, т.е. значимость $$\Delta a$$ оценивается, как $$|\Delta a/a |$$. Из этого эвристического рассуждения получаем:

$$\begin{align*} (x_i|x^p) =|w_i|\cdot |x_i^p -x_i^0|/|w_0+(x^p,w)|. \end{align*} $$

Если положить $$x_i^0 = M(x_i)$$ и воспользоваться евклидовой мерой, то вновь получим произведение модуля параметров $$w_i$$ на среднеквадратичное отклонение с весом. В качестве весов выступают квадраты величин, обратных выходным сигналам сумматоров:

$$\begin{align*} \chi(x_i) =|w_i|\cdot [\sum_p (x_i^p - M(x_i))^2 /(w_0+(x^p,w))^2]^{1/2}. \end{align*} $$

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

Сокращение описания "сверху вниз" - набор достаточного семейства наиболее значимых параметров

Метод исключения параметров "сверху вниз" с ортогонализацией применим не ко всяким функциям $$F(x,w)$$, а только к таким, которые имеют вид:

$$\begin{align*} F(x,w)= \varphi(\sum_i w_i f_i(x)). \end{align*} $$

Достоинство метода - автоматический учет корреляции между $$f_i(x)$$. Рассмотрим устройства, вычисляющие функции

$$\begin{align*} F(x,w)= \sum_i w_i f_i(x). \end{align*} $$

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

Пусть заданы векторы данных:

$$\begin{align*} x^p = (x_1^p, \ldots, x_i^p, \ldots, x_N^p), p = 1, \ldots, n, i = 1, \ldots, N. \end{align*} $$

Поставим задачу сокращения описания следующим образом: так определить некоторое наименьшее возможное множество индексов $$\beta_J$$ и набор чисел $$\beta_j, j \in J$$, чтобы норма отклонения $$\|\Delta F\| = \|F - F'\|$$, где $$F'= \sum_{j \in J} \beta_j f_j(x)$$, не превышала некоторой наперед заданной величины. Все функции рассматриваются на конечном множестве $$\{x^p\}$$. Для любой функции $$\varphi(x)$$ евклидова норма:

$$\begin{align*} \|\varphi\| =[\sum_p \varphi^2(x^p)]^{1/2}. \end{align*} $$

С каждой функцией $$f(x)$$ связан $$n$$ -мерный вектор $$f$$ с компонентами $$f^p = f(x^p)$$. Вектор $$F$$ с координатами $$F^p = \sum_i w_i f_i(x^p)$$ является линейной комбинацией векторов $$f_i$$ с координатами $$f_i^p = f_i^p(x^p)$$. Линейную оболочку семейства векторов $$f_i$$ обозначим $$L = L(\{f_i\})$$. Построим в пространстве $$L$$ ортонормированный базис с помощью последовательной ортогонализации векторов $$f_i$$. Каждый следующий шаг ортогонализации выполним так, чтобы величина проекции $$F$$ на новый вектор базиса была максимальной из возможных. Процесс ортогонализации продолжим, пока $$\|F\|^2 - \|F_\bot\|^2 > \xi^2$$, где $$F_\bot$$ - проекция $$F$$ на построенную ортогональную систему. По окончании процесса полагаем $$F' = F_\bot$$.

Опишем вычисления более детально.

1. Проводим нормировку: для любого $$i$$ полагаем $$g_i^0 = f_i/\|f_i\|$$.

2. Вычисляем $$|(F, g_i^0)|$$ (модуль проекции вектора $$F$$ на вектор $$g_i^0$$ ), $$i = 1, \ldots, N$$. Находим среди этих чисел максимальное (пусть его номер $$i_{0,max}$$ ), полагаем $$e_1 = g_{i0 max}^0$$, исключаем $$g_{i0 max}^{0}$$ из множества $$\{g_i^0\}$$, получаем $$g_i^1 = g_i^0 - (g_i^0,e_1)e_1$$, исключаем из множества $$\{g_i^1\}$$ нулевые векторы, если таковые существуют, проводим нормировку $$g_i^1 = g_i^1/\|g_i^1\|$$.

3. Пусть определены векторы $$e_1, \ldots, e_l$$ и не более чем $$n-l$$ нормированных векторов $$g_i^l$$. Среди векторов $$g_i^l$$ ищем такой $$g_{i,max}^l$$, для которого $$|(F, g_i^l)|$$ принимает максимальное значение, полагаем $$e_{l+1} = g_{i,max}^l$$, исключаем $$g_{i,max}^l$$ из множества векторов $$\{g_i^l\}$$ ; полагаем $$g_i^{l+1} = g_i^l - (g_i^l,e_{l+1})e_{l+1}$$, исключаем из этого множества нулевые векторы, если таковые существуют, нормируем: $$g_i^{l+1} = g_i^{l+1}/\|g_i^{l+1}\|$$.

Вычисления проводим, пока $$\|F\|^2 - \sum_{i=1,l}(F,e_i)^2 > \varepsilon^2$$.

После завершения вычислений имеем набор ортонормированных векторов $$e_1, \ldots, e_l, l \leqslant n$$. Они являются линейными комбинациями векторов $$f_{i,1max}, \ldots, f_{i,lmax}$$. Коэффициенты разложения $$e_j$$ по набору $$f_{i,1max}, \ldots, f_{i,lmax}$$ могут быть вычислены и сохранены в ходе ортогонализации. Полагаем $$J = \{i_{1max}, \ldots, i_{lmax}\}$$. Тогда $$F' = \sum_{j=1,l}(F,e_j)e_j = \sum_{j \in J} \beta_j f_j$$. Это и есть решение задачи. Числа $$\beta_j$$ выражаются через коэффициенты разложения векторов $$e_i, i = 1, \ldots, l$$ по $$f_j, j \in J$$ и скалярные произведения $$(F,e_j)$$: если $$e_i = \sum_{j \in J} q_{ij} f_j$$, то $$\beta_j = \sum_{i=1,l}(F,e_i)q_{ij}$$.

Разложение $$e_i$$ по $$f_j, j \in J$$ имеет рекурсивную форму:

$$\begin{align*} e_1 = f_{i,1max}/\|f_{i,1max}\|,\\ e_2 = [f_{i,2max} - (f_{i,2max}, e_1)e1]/\|f_{i,2max} - (f_{i,2max},e_1)e_1\|,\\ \ldots,\\ e_j = [f_{i,jmax} - \sum_{r=1,j-1}(f_{i,jmax},e_r)e_r]/\| f_{i,jmax} -\sum_{r=1,j-1}(f_{i,jmax},e_r)e_r\|,\\ \ldots \end{align*} $$

Для функций вида $$F(x,w) = \varphi (\sum_i w_i f_i(x))$$ с дифференцируемой функцией процедура аналогична с точностью до замены скалярного произведения: используется скалярное произведение с весами $$(f,g) = \sum_p V_p f^p g^p$$, где $$V_p = ( (\sum_i w_i f_i(x^p)))^2$$. В этом скалярном произведении вычисляются все нормы и проводится ортогонализация.

Для функций с пороговой нелинейностью на выходе используем скалярное произведение с весами $$V_p = |\sum_i w_i f_i(x^p)|^2$$.

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

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

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

Рекурсивное контрастирование и бинаризация

Рекурсивное контрастирование состоит в модификации параметров системы - одного за другим. Для этого параметры должны быть как-то линейно упорядочены $$w_1, \ldots, w_N$$. При модификации $$w_i$$ используются модифицированные значения $$w_1, \ldots, w_{i-1}$$ и немодифицированные $$w_{i+1}, \ldots, w_N$$.

Пусть для сумматора задана обучающая выборка входных векторов $$x_1, \ldots, x_n$$ и соответствующих выходных сигналов $$f_1, \ldots, f_n$$, а также известны значения параметров, которые реализуют сумматор: $$f_i = w_0 + (x^i,w)$$. Требуется произвести бинаризацию сумматора, т.е. найти числа $$a,b$$ и вектор $$\beta$$ с координатами $$0$$ или $$1$$, чтобы значения функции $$\varphi(x) = a + b(x,\beta)$$ на выборке $$\{x^i\}$$ как можно меньше отличались от $$f_i$$. Критерием такого отличия будем считать $$H = \sum_{i=1,n}(f_i - \varphi(x^i))^2$$. Построим координаты вектора $$\beta$$ по порядку $$\beta_1, \beta_2, \ldots$$.

Пусть построены $$\beta_1 ,\ldots, \beta_{i-1}$$. Обозначим $$\beta^{0i} = (\beta_1 ,\ldots, \beta_{i-1}, 0 ,\ldots, 0)$$ (последние $$N - i + 1$$ координат - нули), $$\beta^{1i} = (\beta_1, \ldots, \beta_{i-1},1,0, \ldots, 0)$$ (последние $$N - i$$ координат - нули), $$\alpha^i = (0, \ldots, 0,\alpha_{i+1},\ldots)$$ (первые $$i$$ координат - нули).

Введем функции:

$$\begin{align*} \varphi_0^i(x) = a_{0i} + b_{0i}(x, \beta^{0i}) + (x, \alpha^i),\\ \varphi_1^i(x) = a_{1i} + b_{1i}(x, \beta^{1i}) + (x, \alpha^i),\\ H_{0i} = \sum_{j=1,n}(f_j - \varphi_0^i(x^j))^2,\\ H_{1i} = \sum_{j=1,n}(f_j - \varphi_1^i(x^j))^2. \end{align*} $$

Определим параметры $$a_{0i}, b_{0i}, a_{1i}, b_{1i}$$ из условий $$H_{0i} \to min, H_{1i} \to min$$, минимизируя функции $$H_{0i}$$ и $$H_{1i}$$. Пусть $$h_{0i} = min H_{0i}$$ и $$h_{1i} = min H_{1i}$$. Если $$h_{1i} \geqslant h_{0i}$$, то полагаем $$\beta_i=0$$, в противном случае $$\beta_i=1$$.

После того как построены все $$\beta_i , i = 1, \ldots, N$$ ( $$N$$ - размерность вектора данных), автоматически определяются $$a$$ и $$b$$: если $$N = 0$$, то полагаем $$a = a_{0N}$$, $$b = b_{0N}$$, иначе $$a = a_{1N}, b = b_{1N}$$.

Если бинаризация проведена, а необходимая точность не достигнута, то можно построить второй бинаризованный сумматор, корректирующий ошибку первого --- так, чтобы в сумме они хорошо аппроксимировали работу исходного сумматора на элементах обучающей выборки. В описанной процедуре делаем замену $$f_i := f_i - \varphi(x^i)$$ и для этих исходных данных вновь строим бинаризованный сумматор по алгоритму рекурсивной бинаризации. Повторяем такое построение, пока не будет достигнута удовлетворительная точность. В результате получим набор бинаризованных сумматоров, которые в совокупности (т.е. в результате суммирования выходных сигналов) достаточно точно аппроксимируют исходный. При появлении весов, определяющих значимость отдельных примеров из обучающей выборки, рекурсивная бинаризация проводится точно так же, только в функциях $$H$$ появляются веса.

Если требуется тем же путем упростить любой другой элемент, линейный по параметрам, $$F(x,w) = \sum_{i} w_{i} f_{i}(x)$$, то вместо обучающей выборки $$\{ x^{j} \}$$ берем семейство векторов $$\{ y^{j} \}$$ с координатами $$y_i^j=f_i(x^j)$$. После такого $$y_{i}^{j}=f_i(x^{j})$$ преобразования рассматриваемый элемент превращается в обычный сумматор, для которого последовательность действий уже описана.