Оптимальное прореживание нейронных сетей

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

(Различия между версиями)
Перейти к: навигация, поиск
(шаблон)
Строка 4: Строка 4:
Первоначально метод был предложен ЛеКюном в 1990 году и назывался «optimal brain damage». Затем он был развит Хассиби и получил название
Первоначально метод был предложен ЛеКюном в 1990 году и назывался «optimal brain damage». Затем он был развит Хассиби и получил название
«optimal brain surgery».
«optimal brain surgery».
 +
 +
{{tip|Авторы сомневаются в правильности перевода термина optimal brain surgery и предлагают участникам проекта высказаться по этому поводу в [[Обсуждение:Оптимальная хирургия мозга|обсуждении]]}}
== Описание метода ==
== Описание метода ==

Версия 13:45, 28 апреля 2008

Оптимальная хирургия мозга (optimal brain surgery) — метод упрощения структуры регрессионной модели, например, нейронной сети. Основная идея метода заключается в том, что те элементы модели или те нейроны сети, которые оказывают малое влияние на ошибку аппроксимации, можно исключить из модели без значительного ухудшения качества аппроксимации. Первоначально метод был предложен ЛеКюном в 1990 году и назывался «optimal brain damage». Затем он был развит Хассиби и получил название «optimal brain surgery».


Авторы сомневаются в правильности перевода термина optimal brain surgery и предлагают участникам проекта высказаться по этому поводу в обсуждении


Содержание

Описание метода

Рассмотрим регрессионную модель y_n=f(\mathbf{w},\x_n)+\nu, в которой \x — независимая переменная, y — зависимая переменная, \mathbf{w} — параметры регрессионной модели f, и \nu — аддитивная случайная величина. Задана регрессионная выборка — множество пар D=\{(\mathbf{x}_n, y_n)\}, n=1,\ldots,N. Для построения регрессии требуется найти такие параметры \mathbf{w}^{MP}, которые доставляли бы наименьшее значение функции ошибки E_D.

Найдем локальную аппроксимацию функции E_D в окрестности точки  \mathbf{w}^{MP} с помощью разложения в ряд Тейлора:

E_D(\mathbf{w}+\Delta\mathbf{w}) = E_D(\mathbf{w}) + \mathbf{g}^T(\mathbf{w})\Delta\mathbf{w} + \frac{1}{2}\Delta\mathbf{w}^TH\Delta\mathbf{w} +o(\|\mathbf{w}\|^3),

где \mathbf{w} — возмущение вектора параметров \mathbf{w}, \mathbf{g} — градиент \frac{\partial S}{\partial \mathbf{w}}, и H=H(\mathbf{w}) — матрица вторых производных (матрица Гессе) \frac{\partial^2 S}{\partial \mathbf{w}^2}.

Предполагается, что функция E_D(\mathbf{w}) достигает своего максимума при значении параметров \mathbf{w}=\mathbf{w}^{MP} и ее поверхность квадратична. Таким образом, предыдущее выражение можно упростить и представить в виде

\Delta E_D = E_D(\mathbf{w}+\Delta\mathbf{w})-E_D(\mathbf{w}) = \frac{1}{2}\Delta\mathbf{w}^TH\Delta\mathbf{w}.

Пусть исключение элемента модели есть исключение одного параметра модели, w_i. Исключенный параметр будем считать равным нулю. Это самое сильное ограничение, не позволяющее применять данный метод для регрессионных моделей произвольного вида. Исключение элемента эквивалентно выражению \Delta w_i+w_i=0, иначе

\mathbf{e}_i^T\Delta\mathbf{w}+w_i=0,

где \mathbf{e}_i — вектор, i-й элемент которого равен единице, все остальные элементы равны нулю.

Для нахождения исключаемого элемента требуется минимизировать квадратичную форму \Delta\mathbf{w}^TH\Delta\mathbf{w} относительно \Delta\mathbf{w} при ограничениях \mathbf{e}_i^T+w_i=0, для всех значений i. Индекс i, который доставляет минимум квадратичной форме, задает номер исключаемого элемента:

i = \arg\min_i(\min_{\Delta\mathbf{w}} (\Delta\mathbf{w}^TH\Delta\mathbf{w} | \mathbf{e}_i^T+w_i=0)).

Задача условной минимизации решается с помощью введения Лагранжиана

S=\Delta\mathbf{w}^TH\Delta\mathbf{w}-\lambda(\mathbf{e}_i^T+w_i),

в котором \lambda — множитель Лагранжа. Дифференцируя Лагранжиан по приращению параметров и приравнивая его к нулю получаем (для каждого индекса i параметра w_i)

\Delta\mathbf{w}=-\frac{w_i}{[H^{-1}]_{ii}}H^{-1}\mathbf{e}_i.

Этому значению вектора приращений параметров соответствует минимальное значение Лагранжиана

L_i=\frac{w_i^2}{2[H^{-1}]_{ii}}.

Полученное выражение называется мерой выпуклости функции ошибки E_D при изменении параметра w_i.

Функция L_i зависит от квадрата параметра w_i. Это что говорит о том, что параметр с малым значением скорее всего будет удален из модели. Однако если величина [H^{-1}]_{ii} достаточно мала, это означает, что данный параметр оказывает существенное влияние на качество аппроксимации модели.

Алгоритм

Задана выборка D, модель f(\mathbf{w},\x), функция ошибки E_D. Для упрощения структуры регрессионной модели выполняем следующие шаги.

  1. Настраиваем модель, получаем параметры \mathbf{w}^{MP}=\arg\min(E_D(\mathbf{w}|f,D)).
  2. Для приращения \mathbf{w}^{MP}+\Delta\mathbf{w} решаем оптимизационную задачу, находим для каждого индекса i минимальное значение Лагранжиана L_i.
  3. Выбираем среди L_i минимальное, отсекаем элемент модели, соответствующий i-му параметру.
  4. Добавляем к вектору параметров \mathbf{w}^{MP}, вектор приращений \Delta\mathbf{w}, соответствующий отсеченому параметру.
  5. Получаем упрощенную модель. Модель перенастраивать не требуется.
  6. Процедуру можно повторять до тех пор, пока значение ошибки не превзойдет заранее заданное.

Смотри также

  1. Регрессионный анализ
  2. Регрессионная модель

Литература

  1. Hassibi B., Stork D. G. Second order derivatives for network pruning: Optimal brain surgeon / NIPS 5. 1993. [1]
  2. LeCun Y., Denker J. S., Solla S. A. Optimal brain damage / Touretzky D. S.  ed., Advances in Neural Information Processing Systems 2. Morgan Kaufmann, San Mateo, CA. 1990. P. 598—605. [2]
  3. Хайкин С. Нейронные сети, полный курс. М: Вильямс. 2006.
Личные инструменты