Прореживание двухслойной нейронной сети (пример)

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(См. также)
(Исходный код)
 
(50 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
'''Прореживание двухслойной нейронной сети '''(optimal brain damage) - метод упрощения структуры нейронной сети. Идея прореживания состоит в том, что из сети удаляются параметры, оказывающие малое влияние на ошибку аппроксимации. Таким образом, модель упрощается, а ошибка аппроксимации возрастает незначительно.
+
'''Прореживание двухслойной нейронной сети '''(optimal brain damage) — метод упрощения структуры нейронной сети. Идея прореживания состоит в том, что из сети удаляются параметры, оказывающие малое влияние на ошибку аппроксимации. Таким образом, модель упрощается, а ошибка аппроксимации возрастает незначительно.
-
 
+
== Постановка задачи ==
== Постановка задачи ==
-
Задана обучающая выборка <tex>X^l, Y^l</tex>. Требуется решить задачу классификации с использованием двухслойной нейронной сети; затем упростить сеть, выбросив из нее параметры, соответствующие наименьшей степени выпуклости; среднеквадратичная ошибка классификации при этом не должна сильно возрасти.
+
Задана обучающая выборка <tex>X^l, Y^l</tex>. Требуется решить задачу классификации с использованием двухслойной [http://ru.wikipedia.org/wiki/%D0%9D%D0%B5%D0%B9%D1%80%D0%BE%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%B5%D1%82%D1%8C нейронной сети], настроив параметры сети - весовые матрицы <tex>W_1</tex> и <tex>W_2</tex>, соответствующие соответственно первому и второму слою. Посчитать гессиан <tex>H = \frac{\partial^2\bf{E}(\bf{w})}{\partial \bf{w}^2}</tex>, где <tex>\bf{w}</tex> - вектор параметров, <tex>\bf {E}</tex> - функция стоимости; посчитать функцию выпуклости и упростить сеть, выбросив из нее параметры, соответствующие наименьшей степени выпуклости. Среднеквадратичная ошибка классификации <tex>\bf {E}</tex> при этом не должна сильно возрасти.
== Настройка нейронной сети ==
== Настройка нейронной сети ==
-
Двухслойная нейронная сеть состоит из одного скрытого слоя и выходного слоя. Каждый нейрон сети имеет сигмоидальную функции активации <tex>\phi(z) = 1 / (1 + e^{-z})</tex>. Значения признаков <tex>x^i</tex> поступают на вход первому (скрытому) слою сети с весовой матрицей <tex>W_1</tex>, выходы первого слоя поступают на вход второму с весовой матрицей <tex>W_2</tex>.На выходе второго слоя вычисляется вектор-функция <tex>\bf{F} = (F_1(x),...,F_P(x))</tex>, где <tex>P</tex> - количество нейронов на втором слое. Необходимо настроить параметры сети, используя алгоритм обратного распространения (back propagation). <tex>\bf{E}(\bf{w}) = \frac{1}{2N} \sum_{n = 1}^N \sum_{p = 1}^P(F_p(n) - Y_p(n))^2</tex> - нормированная среднеквадратичная ошибка. Пусть <tex>w_{ji}</tex> - вес, соединяющий нейрон <tex>i </tex> с нейроном <tex>j</tex> следующего слоя. Тогда коррекция веса, применяемая к <tex>w_{ji}(n)</tex>, определяется согласно правилу <tex>\Delta w_{ji} = \eta \bf{\delta}_j(n)y_i(n)</tex>, где <tex>\bf{\delta}_j(n) = - \frac{\partial \bf{E}(n)}{\partial y_j(n)}\phi_j'(v_j(n))</tex> - локальный градиент нейрона j. Здесь <tex>y_i(n)</tex> - выход i-го нейрона, <tex>v_j(n) = \sum_{i = 1}^m w_{ji}(n)y_i(n)</tex> - значение, которое получает на вход функция активации, соответствующая j-му нейрону (m - количество его входов), <tex>\eta</tex> - темп обучения. Поскольку ошибка представляется в виде <tex>\bf{E}(n) = \frac{1}{2}\sum_{p = 1}^P (F_p(n) - y_p(n))^2</tex>, то для выходного слоя <tex>\frac {\partial \bf{E}(n)}{\partial y_j(n)} = y_j(n) - F_j(n) =: e_j(n)</tex>, и для него справедливо <tex>\Delta w_{ji} = - \eta e_j(n)\phi_j'(v_j(n))y_i(n)</tex>.
+
[[Изображение:Something.jpg|500px]] <br />
-
Соответственно, для первого, скрытого, слоя справедлива формула обратного распространения <tex>\delta_j(n) = \phi_j'(v_j(n)) \sum_{p = 1}^P \delta_p(n) w_{pj}(n) </tex>.
+
Двухслойная нейронная сеть состоит из одного скрытого слоя и выходного слоя. Входной слой - это объект со своим признаковым описанием <tex>x_1, ... , x_n</tex>. Первый и второй слои сети состоят из так называемых нейронов, или [[Персептрон|персептронов]]. Каждый нейрон вычисляет <tex>n</tex>-арную функцию вида <tex>a(x) = \phi (<w,x>)</tex>. В нашем случае <tex>\phi</tex> - сигмоидальная функция активации <tex>\phi(z) = 1 / (1 + e^{-z})</tex>. Значения признаков <tex>x_i</tex> поступают на вход первому (скрытому) слою сети с весовой матрицей <tex>W_1</tex>, выходы первого слоя поступают на вход второму с весовой матрицей <tex>W_2</tex>.На выходе второго слоя вычисляется вектор-функция <tex>\bf{F} = (F_1(x),...,F_P(x))</tex>, где <tex>P</tex> - количество нейронов на втором слое. Необходимо настроить параметры сети, используя алгоритм обратного распространения (back propagation). <br />Введем функции ошибок: <tex>\bf{E}(\bf{w}) = \frac{1}{2N} \sum_{n = 1}^N \sum_{p = 1}^P(F_p(n) - Y_p(n))^2</tex> - нормированная среднеквадратичная ошибка, <tex>\bf{E}(n) = \frac{1}{2}\sum_{p = 1}^P (F_p(n) - y_p(n))^2</tex> - ошибка на конкретном объекте. Пусть <tex>w_{ji}</tex> - вес, соединяющий нейрон <tex>i </tex> с нейроном <tex>j</tex> следующего слоя. Тогда коррекция веса, применяемая к <tex>w_{ji}(n)</tex>, определяется согласно правилу <tex>\Delta w_{ji} = \eta \bf{\delta}_j(n)y_i(n)</tex>, где <tex>\bf{\delta}_j(n) = - \frac{\partial \bf{E}(n)}{\partial y_j(n)}\phi_j'(v_j(n))</tex> - локальный градиент нейрона <tex>j</tex>. Здесь <tex>y_i(n)</tex> - выход <tex>i</tex>-го нейрона, <tex>v_j(n) = \sum_{i = 1}^m w_{ji}(n)y_i(n)</tex> - значение, которое получает на вход функция активации, соответствующая <tex>j</tex>-му нейрону (<tex>m</tex> - количество его входов), <tex>\eta</tex> - темп обучения. Для выходного слоя <tex>\frac {\partial \bf{E}(n)}{\partial y_j(n)} = y_j(n) - F_j(n) =: e_j(n)</tex>, и для него справедливо <tex>\Delta w_{ji} = - \eta e_j(n)\phi_j'(v_j(n))y_i(n)</tex>.
 +
Соответственно, для первого, скрытого, слоя справедлива формула обратного распространения <tex>\delta_j(n) = \phi_j'(v_j(n)) \sum_{p = 1}^P \delta_p(n) w_{pj}(n) </tex>. <br /> <br />
 +
Отметим, что эти формулы взяты из книги С. Хайкина "Нейронные сети. Полный курс".
== Алгоритм оптимального прореживания ==
== Алгоритм оптимального прореживания ==
 +
Описание метода второго порядка приводится в статье [[Оптимальное прореживание нейронных сетей]]. <br />
 +
Локальная аппроксимация функции ошибки в окрестности стационарного положения: <tex>E(\mathbf{w}+\Delta\mathbf{w}) = E(\mathbf{w}) + \mathbf{g}^T(\mathbf{w})\Delta\mathbf{w} + \frac{1}{2}\Delta\mathbf{w}^TH\Delta\mathbf{w} +o(\|\mathbf{w}\|^3),</tex>
 +
где&nbsp;<tex>\Delta \mathbf{w}</tex>&nbsp;— возмущение вектора параметров&nbsp;<tex>\mathbf{w}</tex>, <tex>\mathbf{g}</tex>&nbsp;— градиент <tex>\frac{\partial E}{\partial \mathbf{w}}</tex>,
 +
и <tex>H=H(\mathbf{w})</tex>&nbsp;— матрица вторых производных <tex>\frac{\partial^2 E}{\partial \mathbf{w}^2}</tex>. <br />
 +
Необходимо минимизировать квадратичную форму <tex>\Delta E = \frac{1}{2}\Delta \bf{w}^T\bf{H}\Delta \bf{w}</tex> по отношению к <tex>\Delta \bf{w}</tex>при ограничении <tex>\bf{e}_i^T \Delta \bf{w} + w_i = 0</tex>. Для решения этой условной задачи строится лагранжиан <tex>S = \frac{1}{2}\Delta \bf{w}^T \bf{H} \Delta \bf{w} - \lambda (\bf{e}_i^T\Delta \bf{w} + w_i)</tex>. Получаем, что оптимальное приращение вектора весов <tex>\Delta\mathbf{w}=-\frac{w_i}{[H^{-1}]_{ii}}H^{-1}\mathbf{e}_i</tex>, а соответствующее ему оптимальное значение лагранжиана для элемента <tex>w_i</tex>: <tex>S_i=\frac{w_i^2}{2[\bf{H}^{-1}]_{ii}}.</tex>
-
Описание метода второго порядка приводится в статье [http://www.machinelearning.ru/wiki/index.php?title=%D0%9E%D0%BF%D1%82%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D1%80%D0%B5%D0%B6%D0%B8%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BD%D0%B5%D0%B9%D1%80%D0%BE%D0%BD%D0%BD%D1%8B%D1%85_%D1%81%D0%B5%D1%82%D0%B5%D0%B9 "Оптимальное прореживание нейронных сетей"]. Основное отличие данного метода состоит в допущении, что матрица Гессе является диагональной. Таким образом, алгоритм немного видоизменяется:
+
 
 +
Основное отличие данного метода состоит в допущении, что матрица Гессе является диагональной. Таким образом, алгоритм немного видоизменяется:
Задана выборка <tex>X</tex>, модель <tex>f(w)</tex>, функция ошибки <tex>E_X</tex>. Для упрощения структуры сети выполняем следующие шаги: <br />
Задана выборка <tex>X</tex>, модель <tex>f(w)</tex>, функция ошибки <tex>E_X</tex>. Для упрощения структуры сети выполняем следующие шаги: <br />
Строка 17: Строка 24:
2. пока значение ошибки не превосходит заранее заданного (3-5): <br />
2. пока значение ошибки не превосходит заранее заданного (3-5): <br />
3. вычисляем гессиан <tex>H</tex>согласно формуле <br />
3. вычисляем гессиан <tex>H</tex>согласно формуле <br />
-
<tex>H_{jk} = \frac{1}{N}\sum_{n = 1}^N \sum_{p = 1}^P ((\frac{\partial F_p}{\partial w_{kj}})^2 - \frac{\partial^2 F_p}{\partial w_{kj}^2}(F_p(n) - y_p(n)))</tex>
+
<tex>H_{jk} = \frac{1}{N}\sum_{n = 1}^N \sum_{p = 1}^P ((\frac{\partial F_p}{\partial w_{kj}})^2 - \frac{\partial^2 F_p}{\partial w_{kj}^2}(F_p(n) - Y_p(n)))</tex>
<br />
<br />
-
обозначим за <tex>U_j^{(l)}</tex> аргумент функции активации нейрона <tex>j</tex> на слое <tex>l</tex>. Тогда частные производные на втором слое: <tex>\frac{\partial F_p}{\partial w_{kj}} = \phi'(U_k^{(2)}) \phi (U_j^{(1)}); \frac{\partial^2 F_p}{\partial w_{kj}^2} = \phi''(U_k^{(2)}) \phi^2 (U_j^{(1)})</tex> при <tex>p</tex> = <tex>k</tex> и равны 0 при <tex>p</tex> != <tex>k</tex>,<br />
+
обозначим за <tex>U_j^{(l)}</tex> аргумент функции активации нейрона <tex>j</tex> на слое <tex>l</tex>. Тогда частные производные на втором слое: <br /><tex>\frac{\partial F_p}{\partial w_{kj}} = \phi'(U_k^{(2)}) \phi (U_j^{(1)});</tex> <br /><tex> \frac{\partial^2 F_p}{\partial w_{kj}^2} = \phi''(U_k^{(2)}) \phi^2 (U_j^{(1)})</tex> при <tex>p</tex> = <tex>k</tex> и равны 0 при <tex>p \neq k</tex>,<br />
а на первом слое <br />
а на первом слое <br />
-
<tex>\frac{\partial F_p}{\partial w_{ji}} = \phi'(U_p^{(2)})w_{pj}\phi'(U_j^{(1)})x_iw_{ij}</tex> и <tex>\frac{\partial^2 F_p}{\partial w_{ji}^2} = \phi''(U_p^{(2)})(w_{pj} \phi' (U_j^{(1)})x_iw_{ij})^2 + \phi' (U_p^{(2)})w_{pj} \phi'' (U_j^{(1)})(x_iw_{ij})^2 </tex>
+
<tex>\frac{\partial F_p}{\partial w_{ji}} = \phi'(U_p^{(2)})w_{pj}\phi'(U_j^{(1)})x_iw_{ij}</tex> и <br /> <tex>\frac{\partial^2 F_p}{\partial w_{ji}^2} = \phi''(U_p^{(2)})(w_{pj} \phi' (U_j^{(1)})x_iw_{ij})^2 + \phi' (U_p^{(2)})w_{pj} \phi'' (U_j^{(1)})(x_iw_{ij})^2 </tex>
4. вычисляем функцию выпуклости <tex>S_i = \frac{w_i^2 H_i}{2}</tex>, находим <tex>i</tex>, соответствующее наименьшей степени выпуклости. <br />
4. вычисляем функцию выпуклости <tex>S_i = \frac{w_i^2 H_i}{2}</tex>, находим <tex>i</tex>, соответствующее наименьшей степени выпуклости. <br />
Строка 30: Строка 37:
На графике показаны результаты классификации. На первом и втором слое сети - по 5 нейронов, количество признаков - 4. Итого получается 45 весов. Видно, что алгоритм сработал без ошибок.<br />
На графике показаны результаты классификации. На первом и втором слое сети - по 5 нейронов, количество признаков - 4. Итого получается 45 весов. Видно, что алгоритм сработал без ошибок.<br />
-
[[Изображение:iris2.jpg|500px]] <br />
+
[[Изображение:iriss2.png|500px]] <br /> Ниже приведены графики функции выпуклости (одная кривая - зависимость функции выпуклости от суммы модулей параметров) и график зависимости ошибки от количества удаленных параметров.
-
Ниже приведены графики функции выпуклости (одная кривая - зависимость функции выпуклости от одного параметра) и график зависимости ошибки от количества удаленных параметров.
+
-
[[Изображение:Convexity2.jpg|400px]]
+
[[Изображение:Salency2.png|400px]]
-
[[Изображение:OBD2.jpg|400px]]<br />
+
[[Изображение:OBD2.png|400px]]<br />
Видно, что из сети с 45 параметрами можно удалить 18, практически не проиграв в качестве.
Видно, что из сети с 45 параметрами можно удалить 18, практически не проиграв в качестве.
=== Пример 2: выборка линейно неразделима ===
=== Пример 2: выборка линейно неразделима ===
-
Те же самые 45 весов. Алгоритм допустил 3 ошибки при классификации:
+
Те же самые 45 весов. Алгоритм допустил 4 ошибки при классификации:
-
[[Изображение:Iris12.jpg|500px]]<br />
+
[[Изображение:Iriss.png|500px]]<br />
Графики функции выпуклости и количества ошибок: <br />
Графики функции выпуклости и количества ошибок: <br />
-
[[Изображение:convexity.jpg|400px]]
+
[[Изображение:Salency1.png|400px]]
-
[[Изображение:OBD.jpg|400px]]<br />
+
[[Изображение:OBD1.png|400px]]<br />
-
Результат прореживания здесь более наглядный: можно удалить 35 из 45 параметров без потери качества.
+
Результат прореживания здесь более наглядный: можно удалить 35 из 45 параметров без потери качества. <br />
 +
Для этого случая построим график функции ошибки (<tex>-ln E</tex>)в зависимости от параметров. На этом графике красным показаны параметры первого слоя, а синим - второго. В результате применения алгоритма OBD сначала удалялись те параметры, которые на графике видны плохо - именно они не оказывают большого значения на аппроксимацию.<br />
 +
 
 +
[[Изображение:Errors.png|600px]]<br />
Приведем график зависимости ошибки от количества удаленных параметров для тех же данных и 50 нейронов на каждом из слоев.
Приведем график зависимости ошибки от количества удаленных параметров для тех же данных и 50 нейронов на каждом из слоев.
-
[[Изображение:OBDmany.jpg|400px]]
+
[[Изображение:OBD3.png|400px]]
== Исходный код ==
== Исходный код ==
-
Скачать листинги алгоритмов можно здесь: [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/OptimalBrainDamage/ComputeHessianAndConvexity.m ComputeHessianAndConvexity.m], [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/OptimalBrainDamage/ComputeResult.m ComputeResult.m], [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/OptimalBrainDamage/PlotErrors.m PlotErrors.m],[https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/OptimalBrainDamage/PlotHessian.m PlotHessian.m], [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/OptimalBrainDamage/PlotOBD.m PlotOBD.m], [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/OptimalBrainDamage/TuneNet.m TuneNet.m], [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/OptimalBrainDamage/mainNet.m mainNet.m]
+
Скачать листинги алгоритмов можно здесь: [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/Group774/Kuznetsov2010Thinning]
== См. также ==
== См. также ==
-
[http://www.machinelearning.ru/wiki/index.php?title=%D0%9E%D0%BF%D1%82%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D1%80%D0%B5%D0%B6%D0%B8%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BD%D0%B5%D0%B9%D1%80%D0%BE%D0%BD%D0%BD%D1%8B%D1%85_%D1%81%D0%B5%D1%82%D0%B5%D0%B9 Оптимальное прореживание нейронных сетей] <br />[http://www.machinelearning.ru/wiki/index.php?title=%D0%A0%D0%B5%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D0%BE%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7 Регрессионный анализ]
+
* [[Оптимальное прореживание нейронных сетей]]
 +
* [[Регрессионный анализ]]
 +
*[[Вычисление матриц Якоби и Гессе]]
 +
* [[Оптимальное прореживание нейронных сетей (пример)]]
== Литература ==
== Литература ==
* Хайкин С. Нейронные сети, полный курс. 2е издание, испр.
* Хайкин С. Нейронные сети, полный курс. 2е издание, испр.
* К. В. Воронцов, Лекции по линейным алгоритмам классификации
* К. В. Воронцов, Лекции по линейным алгоритмам классификации
 +
 +
[[Категория:Нейронные сети]]
 +
 +
{{ЗаданиеВыполнено|Михаил Кузнецов|В.В.Стрижов|28 мая 2010|Mikethehuman|Strijov}}
 +
[[Категория:Практика и вычислительные эксперименты]]

Текущая версия

Прореживание двухслойной нейронной сети (optimal brain damage) — метод упрощения структуры нейронной сети. Идея прореживания состоит в том, что из сети удаляются параметры, оказывающие малое влияние на ошибку аппроксимации. Таким образом, модель упрощается, а ошибка аппроксимации возрастает незначительно.

Содержание

Постановка задачи

Задана обучающая выборка X^l, Y^l. Требуется решить задачу классификации с использованием двухслойной нейронной сети, настроив параметры сети - весовые матрицы W_1 и W_2, соответствующие соответственно первому и второму слою. Посчитать гессиан H = \frac{\partial^2\bf{E}(\bf{w})}{\partial \bf{w}^2}, где \bf{w} - вектор параметров, \bf {E} - функция стоимости; посчитать функцию выпуклости и упростить сеть, выбросив из нее параметры, соответствующие наименьшей степени выпуклости. Среднеквадратичная ошибка классификации \bf {E} при этом не должна сильно возрасти.

Настройка нейронной сети


Двухслойная нейронная сеть состоит из одного скрытого слоя и выходного слоя. Входной слой - это объект со своим признаковым описанием x_1, ... , x_n. Первый и второй слои сети состоят из так называемых нейронов, или персептронов. Каждый нейрон вычисляет n-арную функцию вида a(x) = \phi (<w,x>). В нашем случае \phi - сигмоидальная функция активации \phi(z) = 1 / (1 + e^{-z}). Значения признаков x_i поступают на вход первому (скрытому) слою сети с весовой матрицей W_1, выходы первого слоя поступают на вход второму с весовой матрицей W_2.На выходе второго слоя вычисляется вектор-функция \bf{F} = (F_1(x),...,F_P(x)), где P - количество нейронов на втором слое. Необходимо настроить параметры сети, используя алгоритм обратного распространения (back propagation).
Введем функции ошибок: \bf{E}(\bf{w}) = \frac{1}{2N} \sum_{n = 1}^N \sum_{p = 1}^P(F_p(n) - Y_p(n))^2 - нормированная среднеквадратичная ошибка, \bf{E}(n) = \frac{1}{2}\sum_{p = 1}^P (F_p(n) - y_p(n))^2 - ошибка на конкретном объекте. Пусть w_{ji} - вес, соединяющий нейрон i с нейроном j следующего слоя. Тогда коррекция веса, применяемая к w_{ji}(n), определяется согласно правилу \Delta w_{ji} = \eta \bf{\delta}_j(n)y_i(n), где \bf{\delta}_j(n) = - \frac{\partial \bf{E}(n)}{\partial y_j(n)}\phi_j'(v_j(n)) - локальный градиент нейрона j. Здесь y_i(n) - выход i-го нейрона, v_j(n) = \sum_{i = 1}^m w_{ji}(n)y_i(n) - значение, которое получает на вход функция активации, соответствующая j-му нейрону (m - количество его входов), \eta - темп обучения. Для выходного слоя \frac {\partial \bf{E}(n)}{\partial y_j(n)} = y_j(n) - F_j(n) =: e_j(n), и для него справедливо \Delta w_{ji} = - \eta e_j(n)\phi_j'(v_j(n))y_i(n). Соответственно, для первого, скрытого, слоя справедлива формула обратного распространения \delta_j(n) = \phi_j'(v_j(n)) \sum_{p = 1}^P \delta_p(n) w_{pj}(n) .

Отметим, что эти формулы взяты из книги С. Хайкина "Нейронные сети. Полный курс".

Алгоритм оптимального прореживания

Описание метода второго порядка приводится в статье Оптимальное прореживание нейронных сетей.
Локальная аппроксимация функции ошибки в окрестности стационарного положения: E(\mathbf{w}+\Delta\mathbf{w}) = E(\mathbf{w}) + \mathbf{g}^T(\mathbf{w})\Delta\mathbf{w} + \frac{1}{2}\Delta\mathbf{w}^TH\Delta\mathbf{w} +o(\|\mathbf{w}\|^3), где \Delta \mathbf{w} — возмущение вектора параметров \mathbf{w}, \mathbf{g} — градиент \frac{\partial E}{\partial \mathbf{w}}, и H=H(\mathbf{w}) — матрица вторых производных \frac{\partial^2 E}{\partial \mathbf{w}^2}.
Необходимо минимизировать квадратичную форму \Delta E = \frac{1}{2}\Delta \bf{w}^T\bf{H}\Delta \bf{w} по отношению к \Delta \bf{w}при ограничении \bf{e}_i^T \Delta \bf{w} + w_i = 0. Для решения этой условной задачи строится лагранжиан S = \frac{1}{2}\Delta \bf{w}^T \bf{H} \Delta \bf{w} - \lambda (\bf{e}_i^T\Delta \bf{w} + w_i). Получаем, что оптимальное приращение вектора весов \Delta\mathbf{w}=-\frac{w_i}{[H^{-1}]_{ii}}H^{-1}\mathbf{e}_i, а соответствующее ему оптимальное значение лагранжиана для элемента w_i: S_i=\frac{w_i^2}{2[\bf{H}^{-1}]_{ii}}.


Основное отличие данного метода состоит в допущении, что матрица Гессе является диагональной. Таким образом, алгоритм немного видоизменяется:

Задана выборка X, модель f(w), функция ошибки E_X. Для упрощения структуры сети выполняем следующие шаги:
1. настраиваем модель, получаем параметры \bf{w}.
2. пока значение ошибки не превосходит заранее заданного (3-5):
3. вычисляем гессиан Hсогласно формуле
H_{jk} = \frac{1}{N}\sum_{n = 1}^N \sum_{p = 1}^P ((\frac{\partial F_p}{\partial w_{kj}})^2 - \frac{\partial^2 F_p}{\partial w_{kj}^2}(F_p(n) - Y_p(n)))
обозначим за U_j^{(l)} аргумент функции активации нейрона j на слое l. Тогда частные производные на втором слое:
\frac{\partial F_p}{\partial w_{kj}} = \phi'(U_k^{(2)}) \phi (U_j^{(1)});
 \frac{\partial^2 F_p}{\partial w_{kj}^2} = \phi''(U_k^{(2)}) \phi^2 (U_j^{(1)}) при p = k и равны 0 при p \neq k,
а на первом слое
\frac{\partial F_p}{\partial w_{ji}} = \phi'(U_p^{(2)})w_{pj}\phi'(U_j^{(1)})x_iw_{ij} и
\frac{\partial^2 F_p}{\partial w_{ji}^2} = \phi''(U_p^{(2)})(w_{pj} \phi' (U_j^{(1)})x_iw_{ij})^2 + \phi' (U_p^{(2)})w_{pj} \phi'' (U_j^{(1)})(x_iw_{ij})^2

4. вычисляем функцию выпуклости S_i = \frac{w_i^2 H_i}{2}, находим i, соответствующее наименьшей степени выпуклости.
5. вес w_i удаляется из сети

Примеры на модельных данных

Пример 1: выборка линейно разделима

На графике показаны результаты классификации. На первом и втором слое сети - по 5 нейронов, количество признаков - 4. Итого получается 45 весов. Видно, что алгоритм сработал без ошибок.


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


Видно, что из сети с 45 параметрами можно удалить 18, практически не проиграв в качестве.

Пример 2: выборка линейно неразделима

Те же самые 45 весов. Алгоритм допустил 4 ошибки при классификации:


Графики функции выпуклости и количества ошибок:


Результат прореживания здесь более наглядный: можно удалить 35 из 45 параметров без потери качества.
Для этого случая построим график функции ошибки (-ln E)в зависимости от параметров. На этом графике красным показаны параметры первого слоя, а синим - второго. В результате применения алгоритма OBD сначала удалялись те параметры, которые на графике видны плохо - именно они не оказывают большого значения на аппроксимацию.


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


Исходный код

Скачать листинги алгоритмов можно здесь: [1]

См. также

Литература

  • Хайкин С. Нейронные сети, полный курс. 2е издание, испр.
  • К. В. Воронцов, Лекции по линейным алгоритмам классификации


Данная статья была создана в рамках учебного задания.
Студент: Михаил Кузнецов
Преподаватель: В.В.Стрижов
Срок: 28 мая 2010


В настоящее время задание завершено и проверено. Данная страница может свободно правиться другими участниками проекта MachineLearning.ru.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.

Личные инструменты