Модель МакКаллока-Питтса

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

(Различия между версиями)
Перейти к: навигация, поиск
(категория)
 
(18 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
'''Сравнение работы ЕМ-алгоритма и k-means для смесей с экспоненциальным распределением компонент.''' (будет в заголовке)
+
{{TOCright}}
 +
Первой формальной моделью [[Нейронная сеть| нейронных сетей]] (НС) была модель МакКаллока-Питтса, уточненная и развитая Клини. Впервые было установлено, что НС могут выполнять любые логические операции и вообще любые преобразования, реализуемые дискретными устройствами с конечной памятью. Эта модель легла в основу теории логических сетей и конечных автоматов и активно использовалась психологами и нейрофизиологами при моделировании некоторых локальных процессов нервной деятельности. В силу своей дискретности она вполне согласуется с компьютерной парадигмой и, более того, служит её «нейронным фундаментом».
-
В статье приведены примеры классификации ЕМ-алгоритмом и методом k ближайших соседей двумерной смеси, компоненты которой имеют экспоненциальное распределение.
+
=Устройство модели=
 +
[[Изображение:pict1.jpg|300px|thumb|Рис.1 модель нейрона МакКалока-Питтса]]
 +
Пусть имеется <tex>n</tex> входных величин x<sub>1</sub>,&hellip;,x<sub>n</sub> бинарных признаков, описывающих объект <tex>x</tex>.
 +
Значения этих признаков будем трактовать как величины импульсов, поступающих на вход нейрона через <tex>n</tex> входных синапсов.
 +
Будем считать, что, попадая в нейрон, импульсы складываются с весами &omega;<sub>1</sub>,&hellip;,&omega;<sub>n</sub>.
-
='''Краткое описание исследуемых алгоритмов'''=
+
Если вес положительный, то соответствующий синапс возбуждающий, если отрицательный, то тормозящий.
-
==ЕМ алгоритм==
+
Если суммарный импульс превышает заданный порог активации &omega;<sub>0</sub>, то нейрон возбуждается и выдаёт на выходе 1, иначе выдаётся 0.
-
Основа EM-алгоритма - предположение, что исследуемое множество данных может быть представлено с помощью линейной комбинации распределений, а цель - оценка параметров распределения, которые максимизируют логарифмическую функцию правдоподобия, используемую в качестве меры качества модели.
+
-
Пусть рассматривается смесь из <tex>k</tex> распределений, каждое описывается функцией правдоподобия <tex>p_j(x)</tex>
+
-
<center><tex>p(x) = \sum_{i=1}^k w_jp_j(x)</tex></center>
+
Таким образом, нейрон вычисляет n-арную булеву функцию
 +
<center><tex>a(x) = \varphi(\sum_{j=1}^n \omega_jx^j - \omega_0)</tex></center>
 +
где <tex>\varphi(z) = [z \ge 0]</tex> - ступенчатая функция Хевисайда.
-
<tex>w_j</tex> - априорная вероятность <tex>j</tex>-й компоненты. Функции правдоподобия принадлежат параметрическому семейству распределений <tex>\varphi(x; \theta)</tex> и отличаются только значениями параметра <tex>p_j(x) = \varphi(x; \theta_j)</tex>
+
В теории нейронных сетей функцию &phi;, преобразующую значение суммарного импульса в выходное значение нейрона, принято называть функцией активации.
 +
Таким образом, модель МакКаллока-Питтса эквивалентна пороговому [[Линейный классификатор| линейному классификатору]].
 +
=Результаты теории=
 +
Теоретические основы нейроматематики были заложены в начале 40-х годов и в 1943 году У. МакКалок и его ученик У. Питтс сформулировали основные положения теории деятельности головного мозга.
 +
Ими были получены следующие результаты:
 +
*разработана модель нейрона как простейшего процессорного элемента, выполняющего вычисление переходной функции от скалярного произведения вектора входных сигналов и вектора весовых коэффициентов;
 +
*предложена конструкция сети таких элементов для выполнения логических и арифметических операций;
 +
*сделано основополагающее предположение о том, что такая сеть способна обучаться, распознавать образы, обобщать полученную информацию.
-
'''Вывод формул для алгоритма'''
+
=Недостатки модели=
-
----
+
Недостатком данной модели является сама модель нейрона &laquo;пороговой&raquo; вид переходной функции. В формализме У. Маккалока-Питтса нейроны имеют состояния 0, 1 и пороговую логику перехода из состояния в состояние. Каждый нейрон в сети определяет взвешенную сумму состояний всех других нейронов и сравнивает ее с порогом, чтобы определить свое собственное состояние.
-
'''Вход''':
+
-
<tex> R, M, Delta, L</tex> – общая длина выборки
+
Пороговый вид функции не предоставляет нейронной сети достаточную гибкость при обучении и настройке на заданную задачу. Если значение вычисленного скалярного произведения, даже незначительно, не достигает до заданного порога, то выходной сигнал не формируется вовсе и нейрон &laquo;не срабатывает&raquo;. Это значит, что теряется интенсивность выходного сигнала (аксона) данного нейрона и, следовательно, формируется невысокое значение уровня на взвешенных входах в следующем слое нейронов.
-
'''Выход''':
+
К тому же модель не учитывает многих особенностей работы реальных нейронов (импульсного характера активности, нелинейности суммирования входной информации, рефрактерности).
-
 
+
-
<tex>\theta = (\omega_1, \omega_2, ..., \omega_k, \theta_1, \theta_2, ..., \theta_k)</tex> параметры распределения и весы компонент.
+
-
 
+
-
'''Оценка максимального правдоподобия (ОМП) θ'''
+
-
для одно- и двумерного случая экспоненциального распределения.
 
-
 
-
Необходимо максимизировать
 
-
 
-
<center><tex>Q(\Theta) = ln\prod_{i=1}^m p(x_i)=\sum_{i=1}^mln\sum_{j=1}^k\omega_jp_j(x_i) \rightarrow ma\limits_{\Theta}x</tex></center>
 
-
 
-
Из Лагранжиана следует:
 
-
 
-
<tex>
 
-
\omega_j=\frac{1}m \sum_{i=1}^mg_{ij} </tex> j=1,...,k
 
-
 
-
<tex>\frac{\partial L}{\partial\theta_j}=\frac{\partial}{\partial\theta_j}\sum_{i=1}^mg_{ij}lnp_j(x_i)=0,</tex> j=1,...,k.
 
-
 
-
С учетом <tex>p_j(x)\equiv \varphi(x, \theta_j) = \theta_j \cdot exp{-\theta_j \cdot x}</tex> получаем ОМП <tex>\theta </tex> для экспоненциального закона:
 
-
 
-
<center><tex>\frac{\partial}{\partial \theta_j}\sum_{i=1}^mg_{ij}(ln \theta_j - \theta_jx_i)=0</tex></center>
 
-
 
-
''В одномерном случае'':
 
-
 
-
<tex>\theta_j=\frac{\sum_{i=1}^mg_{ij}}{\sum_{i=1}^mx_ig_{ij}}</tex>
 
-
 
-
''В двумерном случае'':
 
-
 
-
<tex>\theta_{jx}=\frac{\sum_{i=1}^mg_{ij}}{\sum_{i=1}^mx_ig_{ij}}\\\theta_{jy}=\frac{\sum_{i=1}^mg_{ij}}{\sum_{i=1}^my_ig_{ij}}</tex>
 
-
 
-
==k-means (k ближайших соседей)==
 
-
 
-
Метод <tex>K</tex> ближайших соседей - это [[Метрический классификатор|метрический алгоритм классификации]], основанный на оценивании сходства объектов. Классифицируемый объект относится к тому классу, которому принадлежат ближайшие к нему объекты [[выборка|обучающей выборки]].
 
-
 
-
'''Постановка задачи'''
 
----
----
 +
Несмотря на то, что за прошедшие годы нейроматематика ушла далеко вперед, многие утверждения МакКалока остаются актуальными и поныне. В частности, при большом разнообразии моделей нейронов принцип их действия, заложенный МакКалоком и Питтсом, остается неизменным.
-
Пусть <tex>X \in \mathbb{R}^n\</tex> - множество объектов; <tex>Y</tex> - множество допустимых ответов. Задана обучающая выборка <tex>\{(x_i,y_i)\}_{i=1}^\ell</tex>. Задано множество объектов <tex>\ X^m =\{x_i\}_{i=1}^m</tex>.
+
= См. также =
-
Требуется найти множество ответов <tex>\{y_i\}_{i=1}^m</tex> для объектов <tex>\{x_i\}_{i=1}^m</tex>.
+
* [[Персептрон]]
-
 
+
* [[Перcептрон Розенблатта]]
-
На множестве объектов задается некоторая функция расстояния, в данном случае <tex>\rho(x,x')</tex> - максимум модулей
+
* [[Правила Хэбба]]
-
<center><tex>\rho(x,x') = \max_{i} |x_i-x'_i|;</tex></center>
+
* [[Адаптивный линейный элемент]]
-
 
+
* [[Искусственная нейронная сеть]]
-
Для произвольного объекта <tex>x\in X</tex> расположим
+
-
объекты обучающей выборки <tex>x_i</tex> в порядке возрастания расстояний до <tex>x</tex>:
+
-
::<tex>\rho(x,x_{1; x}) \leq \rho(x,x_{2; x}) \leq \cdots \leq \rho(x,x_{m; x}),</tex>
+
-
где через <tex>x_{i; x}</tex> обозначается
+
-
тот объект обучающей выборки, который является <tex>i</tex>-м соседом объекта <tex>x</tex>.
+
-
Аналогично для ответа на <tex>i</tex>-м соседе:
+
-
<tex>y_{i; x}</tex>.
+
-
 
+
-
Таким образом, произвольный объект <tex>x</tex> порождает свою перенумерацию выборки.
+
-
В наиболее общем виде [[алгоритм]] ближайших соседей есть
+
-
::<tex>a(x) = \mathrm{arg}\max_{y\in Y} \sum_{i=1}^m \bigl[ x_{i; x}=y \bigr] w(i,x),</tex>
+
-
где <tex>w(i,x)</tex> — заданная ''весовая функция'',
+
-
которая оценивает степень важности <tex>i</tex>-го соседа для классификации объекта <tex>u</tex>.
+
-
 
+
-
В рассматриваемом примере <tex>w(i,x) = [i\leq k] ,</tex> что соответствует методу <tex>k</tex> ближайших соседей.
+
-
 
+
-
=Примеры работы=
+
-
Сравнение проводилось с использованием написанных на практикуме алгоритмов EM и k-means.
+
-
На графиках, отображающих компоненты, показано по одной из-за большого разброса предельных значений классифицируемых объектов. Следует обратить внимание на интервал, содержащий всю выборку.
+
-
 
+
-
==Пример №1 (две компоненты)==
+
-
Смесь из двух компонент по 500 элементов.
+
-
 
+
-
<tex>\theta_x=1, \theta_y=0,01</tex>
+
-
 
+
-
<tex>\theta_x=0,01, \theta_y=1</tex>
+
-
 
+
-
[[Изображение:1,_001.png|300px|Распределение theta_x=1 theta_y=0,01]]
+
-
[[Изображение:Rev1,_001.png|300px|Распределение theta_x=0,01 theta_y=1]]
+
-
 
+
-
В результате работы ЕМ-алгоритма с последовательным добавлением компонент с параметрами R = 30, M = 20, Delta = 0,001 восстанавливается <tex>\theta_1 = (1.01831, 0.0101044)</tex>, <tex>\theta_2=(0.0104461, 0.917726)</tex>
+
-
 
+
-
'''Количество ошибок при классификации:'''
+
-
 
+
-
''ЕМ'' 1 из 500 (0.2%)
+
-
 
+
-
''k-means (k=1)'' 0 из 500
+
-
 
+
-
''k-means (k=5)'' 1 из 500 (0.2%)
+
-
 
+
-
==Пример №2 (три компоненты)==
+
-
Смесь из трех компонент по 500 элементов
+
-
 
+
-
[[Изображение:Image006.gif|550px|Распределение theta_x=0,03 theta_y=2]]
+
-
 
+
-
[[Изображение:Image007.gif|550px|Распределение theta_x=1 theta_y=0,04]]
+
-
 
+
-
[[Изображение:Image008.gif|550px|Распределение theta_x=7 theta_y=7]]
+
-
 
+
-
В результате работы ЕМ-алгоритма с последовательным добавлением компонент с параметрами R = 30, M = 40, Delta = 0,001 восстанавливается
+
-
 
+
-
<tex>\theta_1 = (0.0309435, 2.05189)</tex>,
+
-
 
+
-
<tex>\theta_2=(1.05747, 0.0394895)</tex>,
+
-
 
+
-
<tex>\theta_3=(6.56629, 6.79212)</tex>
+
-
 
+
-
'''Количество ошибок при классификации:'''
+
-
 
+
-
''ЕМ'' 6 из 500 (1.2%)
+
-
 
+
-
''k-means (k=1)'' 12 из 500 (2.2%)
+
-
 
+
-
''k-means (k=5)'' 18 из 500 (3.6%)
+
-
 
+
-
==Пример №3 (четыре компоненты)==
+
-
Смесь из четырех компонент по 500 элементов. Добавлена компонента с <tex>\theta_x=15,\theta_y=15</tex>
+
-
 
+
-
[[Изображение:Image012.gif|550px|Распределение theta_x=15 theta_y=15]]
+
-
 
+
-
В результате работы ЕМ-алгоритма с последовательным добавлением компонент с параметрами R = 15, M = 30, Delta = 0,001 восстанавливается
+
-
 
+
-
<tex>\theta_1 = (0.0300939, 1.96699)</tex>,
+
-
 
+
-
<tex>\theta_2=(1.02279, 0.041855)</tex>,
+
-
 
+
-
<tex>\theta_3=(6.1976, 6.23407)</tex>,
+
-
 
+
-
<tex>\theta_4=(14.8266, 12.9193)</tex>
+
-
 
+
-
'''Количество ошибок при классификации:'''
+
-
 
+
-
''ЕМ'' 37 из 500 (7.4%)
+
-
 
+
-
''k-means (k=1)'' 9 из 500 (1.8%)
+
-
 
+
-
''k-means (k=5)'' 26 из 500 (5.2%)
+
-
 
+
-
==Пример №4 (пять компонент)==
+
-
Смесь из пяти компонент по 500 элементов. Добавили компоненту с <tex>\theta_x=75,\theta_y=3</tex>
+
-
 
+
-
[[Изображение:Image026.gif|550px|Распределение theta_x=75 theta_y=3]]
+
-
 
+
-
В результате работы ЕМ-алгоритма с последовательным добавлением компонент с параметрами R = 7, M = 20, Delta = 0,001 восстанавливается
+
-
 
+
-
<tex>\theta_1 = (0.0311774, 1.88446)</tex>,
+
-
 
+
-
<tex>\theta_2=(1.00218, 0.0372523)</tex>,
+
-
 
+
-
<tex>\theta_3=(5.9531, 6.10164)</tex>,
+
-
 
+
-
<tex>\theta_4=(14.6564, 13.2964)</tex>,
+
-
 
+
-
<tex>\theta_5 = (81.433, 3.10389)</tex>,
+
-
 
+
-
'''Количество ошибок при классификации:'''
+
-
 
+
-
''ЕМ'' 243 из 500 (48.6%)
+
-
 
+
-
''k-means (k=1)'' 35 из 500 (7%)
+
-
 
+
-
''k-means (k=5)'' 22 из 500 (4.2%)
+
=Литература=
=Литература=
-
*К. В. Воронцов, Лекции по статистическим (байесовским) алгоритмам классификации
+
#[[Машинное обучение (курс лекций, К.В.Воронцов)]]
-
*Королёв В.Ю. ЕМ-алгоритм, его модификации и их применение к задаче разделения смесей вероятностных распределений. Теоретический обзор. - М.: ИПИРАН, 2007
+
#Дж. фон Нейман Теория самовоспроизводящихся автоматов/ закончено и отредактировано А. Бёрксом. - М.: Мир, 1971. - 384 с
-
*http://en.wikipedia.org/wiki/Maximum_likelihood#Discrete_distribution.2C_finite_parameter_space
+
#Маккалох Дж., Питтс У. Логические исчисления идей, относящихся к нервной деятельности.// Автоматы. М.: ИЛ, 1956.
-
*http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/AppletKM.html
+
#http://bio-net.by.ru/public/model_net_rus.pdf
-
*http://www.basegroup.ru/library/analysis/clusterization/em/
+
-
*http://fedc.wiwi.hu-berlin.de/xplore/ebooks/html/csa/node45.html
+
-
 
+
-
{{Задание|Platonova.Elena|Константин Воронцов|6 января 2010}}
+
 +
=Ссылки=
 +
*http://www.twirpx.com/file/95289/
 +
*http://dfe.karelia.ru/koi/posob/optproc/neucom.html
-
[[Категория:Непроверенные учебные задания]]
+
[[Категория:Линейные классификаторы]]
 +
[[Категория:Нейронные сети]]
 +
{{Задание|Platonova.Elena|Константин Воронцов|8 января 2010}}

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

Содержание

Первой формальной моделью нейронных сетей (НС) была модель МакКаллока-Питтса, уточненная и развитая Клини. Впервые было установлено, что НС могут выполнять любые логические операции и вообще любые преобразования, реализуемые дискретными устройствами с конечной памятью. Эта модель легла в основу теории логических сетей и конечных автоматов и активно использовалась психологами и нейрофизиологами при моделировании некоторых локальных процессов нервной деятельности. В силу своей дискретности она вполне согласуется с компьютерной парадигмой и, более того, служит её «нейронным фундаментом».

Устройство модели

Рис.1 модель нейрона МакКалока-Питтса
Рис.1 модель нейрона МакКалока-Питтса

Пусть имеется n входных величин x1,…,xn бинарных признаков, описывающих объект x. Значения этих признаков будем трактовать как величины импульсов, поступающих на вход нейрона через n входных синапсов. Будем считать, что, попадая в нейрон, импульсы складываются с весами ω1,…,ωn.

Если вес положительный, то соответствующий синапс возбуждающий, если отрицательный, то тормозящий. Если суммарный импульс превышает заданный порог активации ω0, то нейрон возбуждается и выдаёт на выходе 1, иначе выдаётся 0.

Таким образом, нейрон вычисляет n-арную булеву функцию

a(x) = \varphi(\sum_{j=1}^n \omega_jx^j - \omega_0)

где \varphi(z) = [z \ge 0] - ступенчатая функция Хевисайда.

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

Результаты теории

Теоретические основы нейроматематики были заложены в начале 40-х годов и в 1943 году У. МакКалок и его ученик У. Питтс сформулировали основные положения теории деятельности головного мозга.

Ими были получены следующие результаты:

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

Недостатки модели

Недостатком данной модели является сама модель нейрона «пороговой» вид переходной функции. В формализме У. Маккалока-Питтса нейроны имеют состояния 0, 1 и пороговую логику перехода из состояния в состояние. Каждый нейрон в сети определяет взвешенную сумму состояний всех других нейронов и сравнивает ее с порогом, чтобы определить свое собственное состояние.

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

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



Несмотря на то, что за прошедшие годы нейроматематика ушла далеко вперед, многие утверждения МакКалока остаются актуальными и поныне. В частности, при большом разнообразии моделей нейронов принцип их действия, заложенный МакКалоком и Питтсом, остается неизменным.

См. также

Литература

  1. Машинное обучение (курс лекций, К.В.Воронцов)
  2. Дж. фон Нейман Теория самовоспроизводящихся автоматов/ закончено и отредактировано А. Бёрксом. - М.: Мир, 1971. - 384 с
  3. Маккалох Дж., Питтс У. Логические исчисления идей, относящихся к нервной деятельности.// Автоматы. М.: ИЛ, 1956.
  4. http://bio-net.by.ru/public/model_net_rus.pdf

Ссылки

Данная статья является непроверенным учебным заданием.
Студент: Участник:Platonova.Elena
Преподаватель: Участник:Константин Воронцов
Срок: 8 января 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

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


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