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

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

(Различия между версиями)

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

Содержание

1 История метода
2 Описание метода второго порядка
3 Алгоритм
4 Смотри также
5 Литература
6 Примечания

Оптимальное прореживание нейронных сетей (англ. optimal brain surgery) — метод упрощения структуры регрессионной модели, например, нейронной сети. Основная идея прореживания (англ. pruning) заключается в том, что те элементы модели или те нейроны сети, которые оказывают малое влияние на ошибку аппроксимации, можно исключить из модели без значительного ухудшения качества аппроксимации.

История метода

Метод второго порядка (использующий анализ чувствительности, основанный на вычислении вторых производных) был предложен ЛеКюном в 1990 году^[1] и назывался «optimal brain damage». Затем он был развит Хассиби^[1] и получил название «optimal brain surgery».

Несколько ранее были предложены методы прореживания^[1] и скелетонизации^[1] нейронных сетей, основанные просто на удалении элементов с наименьшими весами (методы нулевого порядка).

Наконец, в том же 1990 году А. Н. Горбанём был предложен эффективный метод, основанный на анализе первых производных в ходе обучения градиентными методами и не требующий отдельного дифференцирования.^[1] Кроме задачи удаления элементов решались также другие проблемы упрощения: уменьшение разрядности весов и сигналов (огрубление), упрощение функций активации нейронов, получение интерпретируемого знания и т. д. Вся совокупность подходов получила также название «контрастирование нейронных сетей». Описание основных показателей чувствительности представлено в обзоре.^[1]

Е. М. Миркес в проекте «Идеального нейрокомпьютера» на основе подхода Горбаня и опыта разработки прикладного программного обеспечения ввёл элемент «Контрастёр», построил библиотеку его основных функций и разработал язык описания.^[1]

Для подготовки нейронной сети к упрощению оказывается полезным ввести в оценку её работы, минимизируемую при обучении, штрафные слагаемые (англ. penalty), штрафующие за сложность. Эти алгоритмы введены в книге А. Н. Горбаня^[1]. Такой подход был впоследствии переоткрыт и положен в основу теории структурного обучения Ишикавы и Зурады.^[1]^[1]

Описание метода второго порядка

Рассмотрим регрессионную модель $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 E_D}{\partial \mathbf{w}}$ , и $H=H(\mathbf{w})$ — матрица вторых производных (матрица Гессе) $\frac{\partial^2 E_D}{\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\Delta \mathbf{w}+w_i=0$ , для всех значений $i$ . Индекс $i$ , который доставляет минимум квадратичной форме, задает номер исключаемого элемента:

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

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

$S=\Delta\mathbf{w}^TH\Delta\mathbf{w}-\lambda(\mathbf{e}_i^T\Delta\mathbf{w}+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$ . Для упрощения структуры регрессионной модели выполняем следующие шаги.

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

Смотри также

Литература

Хайкин С. Нейронные сети, полный курс. 2е издание, испр. - М: Вильямс. 2008. - 1103 с. ISBN 978-5-8459-0890-2
Миркес Е. М., Нейрокомпьютер. Проект стандарта.- Новосибирск: Наука, Сибирская издательская фирма РАН, 1999. - 337 с. ISBN 5-02-031409-9
Горбань А. Н., Обучение нейронных сетей. М.: изд. СССР-США СП «Параграф», 1990. 160 с.

Примечания

Источник — «http://recognition.su/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»

Категории: Нейронные сети | Регрессионный анализ | Энциклопедия анализа данных

@@ Строка 1: / Строка 1: @@
+{{TOCright}}
 '''Оптимальное прореживание нейронных сетей''' (англ. optimal brain surgery)&nbsp;— метод упрощения структуры [[регрессионная модель|регрессионной модели]], например, [[нейронная сеть|нейронной сети]].
 Основная идея прореживания (англ. pruning) заключается в том, что те элементы модели или те нейроны сети, которые оказывают малое влияние на ошибку аппроксимации,
 можно исключить из модели без значительного ухудшения качества аппроксимации.
-__NOTOC__
 == История метода ==
@@ Строка 9: / Строка 8: @@
 ''Метод второго порядка'' (использующий '''анализ чувствительности''', основанный на вычислении вторых производных) был предложен ЛеКюном в 1990 году<ref>LeCun&nbsp;Y., Denker&nbsp;J.&nbsp;S., Solla&nbsp;S.&nbsp;A. [http://citeseer.ist.psu.edu/lecun90optimal.html Optimal brain damage]&nbsp;/ Touretzky&nbsp;D.&nbsp;S.&nbsp; ed., Advances in Neural Information Processing Systems 2. Morgan Kaufmann, San Mateo, CA. 1990. P.&nbsp;598—605. </ref> и назывался «optimal brain damage». Затем он был развит Хассиби<ref>Hassibi&nbsp;B., Stork&nbsp;D.&nbsp;G. [http://citeseer.ist.psu.edu/hassibi93second.html Second order derivatives for network pruning: Optimal brain surgeon]&nbsp;/ NIPS 5. 1993.</ref> и получил название «optimal brain surgery».
-Несколько ранее и одновременно были предложены методы прореживания<ref>Sietsma J., Dow R.J.F., Neural net pruning — why and how. In: Proc. IEEE IJCNN 1988, San Diego, CA. Vol.1. — pp.325-333.</ref> и скелетонизации<ref>Mozer M.C., Smolensky P. Skeletonization: a technique for trimming the fat from a network via relevance assessment. In: Advances in Neural Network Information Processing Systems, Morgan Kaufmann, 1989. Vol.1, pp.107-115.</ref> нейронных сетей, основанные просто на удалении элементов с наименьшими весами (''методы нулевого порядка'').
+Несколько ранее были предложены методы прореживания<ref>Sietsma J., Dow R.J.F., Neural net pruning — why and how. In: Proc. IJCNN'88, San Diego, CA., IEEE, Vol.1. — pp.325-333.</ref> и скелетонизации<ref>Mozer M.C., Smolensky P. Skeletonization: a technique for trimming the fat from a network via relevance assessment. In: Advances in Neural Network Information Processing Systems, Morgan Kaufmann, 1989. Vol.1, pp.107-115.</ref> нейронных сетей, основанные просто на удалении элементов с наименьшими весами (''методы нулевого порядка'').
-Наконец, в том же 1990 году был предложен эффективный метод, основанный на анализе первых производных в ходе обучений и не требующий отдельного дифференцирования.<ref>Горбань А. Н., Обучение нейронных сетей. М.: изд. СССР-США СП «Параграф», 1990. 160 с.</ref> Кроме задачи удаления элементов решались также другие проблемы упрощения: уменьшение разрядности весов и сигналов (огрубление), получение интерпретируемого знания и&nbsp;т.&nbsp;д. Вся совокупность подходов получила также название «контрастирование нейронных сетей».
+Наконец, в том же 1990 году А. Н. Горбанём был предложен эффективный метод, основанный на анализе первых производных в ходе обучения градиентными методами и не требующий отдельного дифференцирования.<ref name="Gorban">Горбань А. Н., Обучение нейронных сетей. М.: изд. СССР-США СП «Параграф», 1990. 160 с.</ref> Кроме задачи удаления элементов решались также другие проблемы упрощения: уменьшение разрядности весов и сигналов (огрубление), упрощение функций активации нейронов, получение интерпретируемого знания и&nbsp;т.&nbsp;д. Вся совокупность подходов получила также название «''контрастирование нейронных сетей''». Описание основных показателей чувствительности представлено в обзоре.<ref>Gorban A. N., Mirkes Eu. M., Tsaregorodtsev V. G. [http://arxiv.org/abs/cond-mat/0307083 Generation of Explicit Knowledge from Empirical Data through Pruning of Trainable Neural Networks] In: Proc. IJCNN'99, Washington DC, July 1999, IEEE, Vol. 6, pp. 4393-4398.</ref>
-Описание основных показателей чувствительности представлено а обзоре А. Н. Горбаня с соавторами.<ref>Gorban A. N., Mirkes Eu. M., Tsaregorodtsev V. G. [http://arxiv.org/abs/cond-mat/0307083 Generation of Explicit Knowledge from Empirical Data through Pruning of Trainable Neural Networks] The talk was given at the IJCNN '99 (Washington DC, July 1999).</ref>
+[http://ru.wikipedia.org/wiki/Миркес Е. М. Миркес] в проекте «Идеального нейрокомпьютера» на основе подхода Горбаня и опыта разработки прикладного программного обеспечения ввёл элемент «Контрастёр», построил библиотеку его основных функций и разработал язык описания.<ref>Миркес Е. М., [http://pca.narod.ru/MirkesNeurocomputer.htm Нейрокомпьютер. Проект стандарта.]- Новосибирск: Наука, Сибирская издательская фирма РАН, 1999 .- 337 с. ISBN 5-02-031409-9 (Глава 9: «Контрастер»)</ref>
-Е. М. Миркес в проекте «Идеального нейрокомпьютера» ввёл элемент «Контрастёр», описал его основные функции и построил язык описания.<ref>Миркес Е. М., [http://pca.narod.ru/MirkesNeurocomputer.htm Нейрокомпьютер. Проект стандарта.]- Новосибирск: Наука, Сибирская издательская фирма РАН, 1998 .- 337 с (Глава 9: «Контрастер»)</ref>
+Для подготовки нейронной сети к упрощению оказывается полезным ввести в оценку её работы, минимизируемую при обучении, штрафные слагаемые (англ. penalty), штрафующие за сложность. Эти алгоритмы введены в книге А. Н. Горбаня<ref name="Gorban" />. Такой подход был впоследствии переоткрыт и положен в основу ''теории структурного обучения'' Ишикавы и Зурады.<ref>Ishikawa S., Structural learning with forgetting, Neural Networks, 1996, Vol.9, 3, 509-521.</ref><ref>Miller D. A., Zurada, J. M., A dynamical system perspective of structural learning with forgetting, IEEE Transactions on Neural Networks, Vol. 9, 3, 1998, 508-515.</ref>
 == Описание метода второго порядка ==
@@ Строка 25: / Строка 23: @@
 Найдем локальную аппроксимацию функции&nbsp;<tex>E_D</tex> в окрестности точки&nbsp;&nbsp;<tex>\mathbf{w}^{MP}</tex> с помощью разложения в [[ряд Тейлора]]:
-<center><tex>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}\|³),</tex></center>
+::<tex>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),</tex>
-где&nbsp;<tex>\mathbf{w}</tex>&nbsp;— возмущение вектора параметров&nbsp;<tex>\mathbf{w}</tex>, <tex>\mathbf{g}</tex>&nbsp;— градиент <tex>\frac{\partial S}{\partial \mathbf{w}}</tex>,
+где&nbsp;<tex>\mathbf{w}</tex>&nbsp;— возмущение вектора параметров&nbsp;<tex>\mathbf{w}</tex>, <tex>\mathbf{g}</tex>&nbsp;— градиент <tex>\frac{\partial E_D}{\partial \mathbf{w}}</tex>,
-и <tex>H=H(\mathbf{w})</tex>&nbsp;— матрица вторых производных ([[матрица Гессе]]) <tex>\frac{\partial² S}{\partial \mathbf{w}²}</tex>.
+и <tex>H=H(\mathbf{w})</tex>&nbsp;— матрица вторых производных ([[матрица Гессе]]) <tex>\frac{\partial^2 E_D}{\partial \mathbf{w}^2}</tex>.
-Предполагается, что функция&nbsp;<tex>E_D(\mathbf{w})</tex> достигает своего максимума при значении параметров&nbsp;<tex>\mathbf{w}=\mathbf{w}^{MP}</tex> и ее поверхность квадратична.
+Предполагается, что функция&nbsp;<tex>E_D(\mathbf{w})</tex> достигает своего минимума при значении параметров&nbsp;<tex>\mathbf{w}=\mathbf{w}^{MP}</tex> и ее поверхность квадратична.
 Таким образом, предыдущее выражение можно упростить и представить в виде
-<center><tex>\Delta E_D = E_D(\mathbf{w}+\Delta\mathbf{w})-E_D(\mathbf{w}) = \frac{1}{2}\Delta\mathbf{w}^TH\Delta\mathbf{w}.</tex></center>
+::<tex>\Delta E_D = E_D(\mathbf{w}+\Delta\mathbf{w})-E_D(\mathbf{w}) = \frac{1}{2}\Delta\mathbf{w}^TH\Delta\mathbf{w}.</tex>
 Пусть исключение элемента модели есть исключение одного параметра модели,&nbsp;<tex>w_i</tex>.
@@ Строка 37: / Строка 35: @@
 Это самое сильное ограничение, не позволяющее применять данный метод для регрессионных моделей произвольного вида.
 Исключение элемента эквивалентно выражению&nbsp;<tex>\Delta w_i+w_i=0</tex>, иначе
-<center><tex>\mathbf{e}_i^T\Delta\mathbf{w}+w_i=0,</tex></center>
+::<tex>\mathbf{e}_i^T\Delta\mathbf{w}+w_i=0,</tex>
 где&nbsp;<tex>\mathbf{e}_i</tex>&nbsp;— вектор, <tex>i</tex>-й элемент которого равен единице, все остальные элементы равны нулю.
 Для нахождения исключаемого элемента требуется минимизировать квадратичную форму <tex>\Delta\mathbf{w}^TH\Delta\mathbf{w}</tex> относительно <tex>\Delta\mathbf{w}</tex>
-при ограничениях <tex>\mathbf{e}_i^T+w_i=0</tex>, для всех значений&nbsp;<tex>i</tex>. Индекс&nbsp;<tex>i</tex>, который доставляет минимум квадратичной форме,
+при ограничениях <tex>\mathbf{e}_i^T\Delta \mathbf{w}+w_i=0</tex>, для всех значений&nbsp;<tex>i</tex>. Индекс&nbsp;<tex>i</tex>, который доставляет минимум квадратичной форме,
 задает номер исключаемого элемента:
-<center><tex>i = \arg\min_i(\min_{\Delta\mathbf{w}} (\Delta\mathbf{w}^TH\Delta\mathbf{w} | \mathbf{e}_i^T+w_i=0)).</tex></center>
+::<tex>i = \arg\min_i(\min_{\Delta\mathbf{w}} (\Delta\mathbf{w}^TH\Delta\mathbf{w} | \mathbf{e}_i^T\Delta\mathbf{w}+w_i=0)).</tex>
 Задача условной минимизации решается с помощью введения [[Лагранжиан]]а
-<center><tex>S=\Delta\mathbf{w}^TH\Delta\mathbf{w}-\lambda(\mathbf{e}_i^T+w_i),</tex></center>
+::<tex>S=\Delta\mathbf{w}^TH\Delta\mathbf{w}-\lambda(\mathbf{e}_i^T\Delta\mathbf{w}+w_i),</tex>
 в котором&nbsp;<tex>\lambda</tex>&nbsp;— [[множитель Лагранжа]]. Дифференцируя Лагранжиан по приращению параметров и приравнивая его к нулю получаем
 (для каждого индекса&nbsp;<tex>i</tex> параметра&nbsp;<tex>w_i</tex>)
-<center><tex>\Delta\mathbf{w}=-\frac{w_i}{[H^{-1}]_{ii}}H^{-1}\mathbf{e}_i.</tex></center>
+::<tex>\Delta\mathbf{w}=-\frac{w_i}{[H^{-1}]_{ii}}H^{-1}\mathbf{e}_i.</tex>
 Этому значению вектора приращений параметров соответствует минимальное значение Лагранжиана
-<center><tex>L_i=\frac{w_i²}{2[H^{-1}]_{ii}}.</tex></center>
+::<tex>L_i=\frac{w_i^2}{2[H^{-1}]_{ii}}.</tex>
 Полученное выражение называется мерой выпуклости функции ошибки&nbsp;<tex>E_D</tex> при изменении параметра&nbsp;<tex>w_i</tex>.
@@ Строка 72: / Строка 70: @@
 # [[Регрессионный анализ]]
 # [[Регрессионная модель]]
+# [[Нелинейная регрессия]]
+# [[Прореживание двухслойной нейронной сети (пример)]]
 == Литература ==
-# Хайкин С. Нейронные сети, полный курс. М: Вильямс. 2006.
+# Хайкин С. Нейронные сети, полный курс. 2е издание, испр. - М: Вильямс. 2008. - 1103 с. ISBN 978-5-8459-0890-2
-# Миркес Е. М., [http://pca.narod.ru/MirkesNeurocomputer.htm Нейрокомпьютер. Проект стандарта.]- Новосибирск: Наука, Сибирская издательская фирма РАН, 1998 .- 337 с.
+# Миркес Е. М., [http://pca.narod.ru/MirkesNeurocomputer.htm Нейрокомпьютер. Проект стандарта.]- Новосибирск: Наука, Сибирская издательская фирма РАН, 1999. - 337 с. ISBN 5-02-031409-9
+# Горбань А. Н., [http://lib.sibnet.ru/book/11961 Обучение нейронных сетей]. М.: изд. СССР-США СП «Параграф», 1990. 160 с.
 == Примечания ==
 {{список примечаний}}
+[[Категория:Нейронные сети]]
 [[Категория:Регрессионный анализ]]
 [[Категория:Энциклопедия анализа данных]]

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

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

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

Содержание

История метода

Описание метода второго порядка

Алгоритм

Смотри также

Литература

Примечания

Просмотры

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

Навигация

Поиск

Инструменты