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

Версия 15:18, 4 января 2010 (править) Platonova.Elena (Обсуждение | вклад) ← К предыдущему изменению		Текущая версия (23:23, 9 января 2010) (править) (отменить) Vokov (Обсуждение | вклад) (категория)
(21 промежуточная версия не показана)
Строка 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> ближайших соседей.	+
-		+
-	=Примеры работы=	+
-	На графиках, отображающих компоненты, показано по одной из-за большого разброса предельных значений классифицируемых объектов. Следует обратить внимание на интервал, содержащий всю выборку.	+
-		+
-	==Пример №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/	+
-		+
-		+
-	{{Задание|Platonova.Elena|Константин Воронцов|6 января 2010}}	+
		+	=Ссылки=
		+	*http://www.twirpx.com/file/95289/
		+	*http://dfe.karelia.ru/koi/posob/optproc/neucom.html
-	[[Категория:Непроверенные учебные задания]]	+	[[Категория:Линейные классификаторы]]
		+	[[Категория:Нейронные сети]]
		+	{{Задание|Platonova.Elena|Константин Воронцов|8 января 2010}}

---

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

Содержание 1 Устройство модели 2 Результаты теории 3 Недостатки модели 4 См. также 5 Литература 6 Ссылки

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

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

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

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

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

где - ступенчатая функция Хевисайда.

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

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

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

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

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

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

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

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

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

---

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

См. также

• Персептрон
• Перcептрон Розенблатта
• Правила Хэбба
• Адаптивный линейный элемент
• Искусственная нейронная сеть

Литература

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

Ссылки

• http://www.twirpx.com/file/95289/
• http://dfe.karelia.ru/koi/posob/optproc/neucom.html

Данная статья является непроверенным учебным заданием. Студент: Участник:Platonova.Elena Преподаватель: Участник:Константин Воронцов Срок: 8 января 2010 До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.