Сеть радиальных базисных функций

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

(Различия между версиями)
Перейти к: навигация, поиск
м (Понятие радиальной функции: оформление)
 
(10 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
'''Радиальные функции''' - это функции <tex>f(x)</tex>, зависящие только от расстояния между x и фиксированной точ-
+
'''Сеть радиальных базисных функций''' - нейронная сеть прямого распространения сигнала, которая содержит промежуточный (скрытый) слой радиально симметричных [[нейронов]]. Такой нейрон преобразовывает расстояние от данного входного вектора до соответствующего ему "центра" по некоторому нелинейному закону (обычно функция Гаусса)<ref>http://generation6.narod.ru/glossary_r1.htm</ref>. В данной статье мы рассмотрим применение этой нейронной сети к решению задачи [[классификация|классификации]] с помощью восстановления смесей распределений (частный случай [[ЕМ-алгоритм]]а) <br />
-
кой пространства X. <br /> <br />
+
 
-
Гауссиан <tex>p_j(x) = N(x; \mu _j ,\Sigma _j)</tex> с диагональной матрицей <tex>\Sigma _j</tex> можно записать в виде <br /> <br />
+
 
-
<tex>~p_j(x) = N_j exp(-1/2 \rho ^2 _j (x, \mu _j)</tex> <br /> <br />
+
== Понятие радиальной функции ==
-
где <tex>N_j = (2\pi )^ {-n/2)(\sigma _{j1} ... \sigma _{jn})^{-1}</tex> - нормировочный множитель,<br />
+
'''Радиальная функция''' — это функция <tex>f(x)</tex>, зависящая только от расстояния между <tex>x</tex> и фиксированной точкой пространства <tex>X</tex>. <br /> <br />
-
<tex>\rho _j(x, x')</tex> - взвешенная евклидова метрика в n-мерном пространстве X:<br />
+
Для определения наших радиальных функий введем метрику: <br />
-
<tex>~\rho ^2 (x, x') = \Sigma ^n _{d = 1} \sigma ^{-2} _{jd} |\xi _d - \xi _d '| ^2</tex>, <br />
+
[[Нормальное распределение]] (гауссиан) <tex>p_j(x) = N(x; \mu _j ,\Sigma _j)</tex> с диагональной матрицей ковариации <tex>\Sigma _j</tex> можно записать в виде <br /> <br />
 +
<tex>~p_j(x) = N_j exp(-1/2 \rho _j (x, \mu _j)</tex> <br /> <br />
 +
где <tex>N_j = (2\pi)^ {-n/2}(\sigma _{j1}, \dots ,\sigma _{jn})^{-1}</tex> — нормировочный множитель,<br />
 +
<tex>\rho _j(x, x')</tex> — взвешенная евклидова метрика в n-мерном пространстве X:<br />
 +
<tex>~\rho (x, x') = \sum ^n _{d = 1} \sigma ^{-2} _{jd} |\xi _d - \xi _d '| </tex>, <br />
<tex> x = (\xi _1, . . . ,\xi _n), x' = (\xi _1 ', . . . , \xi _n')</tex>. <br /> <br />
<tex> x = (\xi _1, . . . ,\xi _n), x' = (\xi _1 ', . . . , \xi _n')</tex>. <br /> <br />
-
Чем меньше расстояние <tex>\rho _j(x, \mu _j)</tex>, тем выше значение плотности в точке x. По-
+
Чем меньше расстояние <tex>\rho _j(x, \mu _j)</tex>, тем выше значение плотности в точке x. Поэтому плотность <tex>p _j(x)</tex> можно рассматривать как функцию близости вектора x к фиксированному центру <tex>\mu _j</tex>. <br />
-
этому плотность <tex>p _j(x)</tex> можно рассматривать как функцию близости вектора x к фик-
+
-
сированному центру <tex>\mu _j</tex> .
+
-
== Сеть радиальных базисных функций ==
+
== Постановка задачи ==
 +
Построить алгоритм, который бы решал задачу [[классификация|классификации]] [[байесовский классификатор|байесовским алгоритмом]] (частный случай [[EM-алгоритм]]а) в предположении, что [[Оценивание плотности распределения|плотность распределения]] представима в виде смеси гауссовских распределений с диагональными матрицами ковариации.
 +
== Решение задачи ==
 +
Пусть <tex> |Y| = M</tex> - число классов, каждый класс <tex>y \in Y</tex> имеет свою плотность
 +
распределения <tex>p_y(x)</tex> и представлен частью [[выборка|выборки]] <tex>X ^l _y = \{(x_i, y_i) \in X ^l | y_i = y \}</tex>. <br />
 +
Здесь <tex>Y</tex> - множество ответов (классов),<tex>y \in Y</tex> ,
 +
<tex>x_i</tex> принадлежит множеству объектов <tex>X</tex> <br /><br />
 +
===Гипотеза===
 +
Плотности классов <tex>p_y(x), y \in Y</tex> , представимы в виде
 +
смесей <tex>k_y</tex> компонент. Каждая компонента имеет n-мерную гауссовскую плотность
 +
с параметрами <br />
 +
<tex>\mu _{yj} = (\mu _{yj1}, \dots , \mu _{yjn})</tex> - центр,<br /> <tex>\Sigma _{yj} = diag(\sigma _{yj1}, \dots , \sigma _{yjn})</tex> - ковариационная матрица <br />
 +
<tex>j = 1, . . . , k_y</tex>:<br /><br />
 +
<tex> p_y(x) = \sum ^{k _y} _{j = 1} \omega _{yj} p _{yj}(x), </tex> - смесь плотностей <br />
 +
<tex>p_{yj}(x) = N(x; \mu _{yj} ,\Sigma _{yj}), </tex> - плотность каждой компоненты смеси (имеет вид гауссианы)<br />
 +
<tex> \Sigma ^{k_y} _{j = 1} \omega _{yj} = 1, \omega _{yj} > 0;</tex> - условия нормировки и неотрицательности весов<br /> <br />
 +
===Алгоритм классификации===
 +
Запишем основную формулу [[байесовский классификатор|байесовского классификатора]]
 +
<tex>a(x) = argmax _{y \in Y} \lambda _y P _y p_y(x)</tex>. Здесь <tex>Y</tex> - множество ответов (классов),
 +
<tex>x</tex> принадлежит множеству объектов <tex>X , P_y</tex> - априорная вероятность класса <tex>y , p_y(x)</tex> - функция правдоподобия класса <tex>y , \lambda_{y}</tex> - цена ошибки на объекте класса <tex>y</tex>. Выразим плотность каждой компоненты <tex>p_{yj}(x)</tex> через взвешенное евклидово расстояние от объекта x до центра компоненты <tex>\mu _{yj}</tex>(другими словами - подставим в основную формулу байесовского классификатора вместо <tex>p_y(x)</tex> формулы, которые мы предположили в гипотезе) :<br /><br />
 +
 +
<tex>a(x) = argmax _{y \in Y} \lambda _y P _y \sum ^{k_y} _{j = 1} N _{yj} exp(-1/2 \rho _{yj} (x, \mu _{yj}))</tex> <br /> <br />
 +
 +
где <tex>N _{yj} = (2\pi)^{-n/2} (\sigma _{yj1},\dots , \sigma _{yjn})^{-1}</tex> — нормировочные множители. Алгоритм имеет вид
 +
[[нейронная сеть|нейронной сети]], состоящей из трёх уровней или слоёв.<br />
 +
[[Изображение:NS.PNG]] <br />
 +
Первый слой образован <tex>k_1 + \dots+ k_M</tex> гауссианами <tex>p_{yj}(x), y \in Y , j = 1, \dots, k_y</tex>.
 +
На входе они принимают описание объекта x, на выходе выдают оценки близости
 +
объекта x к центрам <tex>\mu _{yj}</tex> , равные значениям плотностей компонент в точке x.<br />
 +
Второй слой состоит из M сумматоров, вычисляющих взвешенные средние этих
 +
оценок с весами <tex>w_{yj}</tex> . На выходе второго слоя появляются оценки близости
 +
объекта x каждому из классов, равные значениям плотностей классов <tex>p_{yj}(x)</tex>.<br />
 +
Третий слой образуется единственным блоком argmax, принимающим окончательное решение об отнесении объекта x к одному из классов.<br />
 +
Таким образом, при классификации объекта x оценивается его близость к каж-
 +
дому из центров <tex>\mu _{yj}</tex> по метрике <tex>\rho _{yj}(x, \mu _{yj}), j = 1, \dots, k_y</tex>. Объект относится к тому
 +
классу, к чьим центрам он располагается ближе.<br /><br />
 +
Описанный трёхуровневый алгоритм классификации называется ''сетью c радиальными базисными функциями'' или ''RBF-сетью'' (radial basis function network). Это одна из разновидностей [[нейронная сеть|нейронных сетей]].<br />
== Обучение RBF-сети ==
== Обучение RBF-сети ==
Обучение сводится к восстановлению плотности каждого из классов
Обучение сводится к восстановлению плотности каждого из классов
-
<tex>p_y(x)</tex> с помощью EM-алгоритма. Результатом обучения являются центры <tex>\mu _{yj}</tex> и дис-
+
<tex>p_y(x)</tex> с помощью [[EM-алгоритм]]а. Результатом обучения являются центры <tex>\mu _{yj}</tex> и дис-
персии <tex>\Sigma _{yj}</tex> компонент <tex>j = 1, . . . , k_y</tex>. Интересно отметить, что, оценивая дисперсии,
персии <tex>\Sigma _{yj}</tex> компонент <tex>j = 1, . . . , k_y</tex>. Интересно отметить, что, оценивая дисперсии,
-
мы фактически подбираем метрики <tex>\rho _{yj}</tex> , с помощью которых будут вычисляться рас-стояния до центров <tex>\mu _{yj}</tex> . При использовании Алгоритма 1.4 для каждого класса определяется оптимальное число компонент смеси.
+
мы фактически подбираем метрики <tex>\rho _{yj}</tex> , с помощью которых будут вычисляться расстояния до центров <tex>\mu _{yj}</tex> . При использовании Алгоритма, описанного в данной статье, для каждого класса определяется оптимальное число компонент смеси.<ref>{{книга |автор = Воронцов К.В. |заглавие = Лекции по метрическим алгоритмам классификации | ссылка = http://www.machinelearning.ru/wiki/images/9/9d/Voron-ML-Metric.pdf}}</ref>
 +
 
 +
== Литература ==
 +
<references/>
 +
 
 +
== См. также ==
 +
*[[Байесовский классификатор]]
 +
*[[EM-алгоритм]]
 +
*[[Нейронная сеть]]
 +
 
 +
{{Задание|MariaAleshina|Константин Воронцов|8 января 2010}}
 +
 
 +
[[Категория:Байесовская теория классификации]]
 +
[[Категория:Метрические алгоритмы классификации]]
 +
[[Категория:Нейронные сети]]

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

Сеть радиальных базисных функций - нейронная сеть прямого распространения сигнала, которая содержит промежуточный (скрытый) слой радиально симметричных нейронов. Такой нейрон преобразовывает расстояние от данного входного вектора до соответствующего ему "центра" по некоторому нелинейному закону (обычно функция Гаусса)[1]. В данной статье мы рассмотрим применение этой нейронной сети к решению задачи классификации с помощью восстановления смесей распределений (частный случай ЕМ-алгоритма)


Содержание

Понятие радиальной функции

Радиальная функция — это функция f(x), зависящая только от расстояния между x и фиксированной точкой пространства X.

Для определения наших радиальных функий введем метрику:
Нормальное распределение (гауссиан) p_j(x) = N(x; \mu _j ,\Sigma _j) с диагональной матрицей ковариации \Sigma _j можно записать в виде

~p_j(x) = N_j exp(-1/2 \rho  _j (x, \mu _j)

где N_j = (2\pi)^ {-n/2}(\sigma _{j1}, \dots ,\sigma _{jn})^{-1} — нормировочный множитель,
\rho _j(x, x') — взвешенная евклидова метрика в n-мерном пространстве X:
~\rho (x, x') = \sum ^n _{d = 1} \sigma ^{-2} _{jd} |\xi _d - \xi _d '| ,
 x = (\xi _1, . . . ,\xi _n), x' = (\xi _1 ', . . . , \xi _n').

Чем меньше расстояние \rho _j(x, \mu _j), тем выше значение плотности в точке x. Поэтому плотность p _j(x) можно рассматривать как функцию близости вектора x к фиксированному центру \mu _j.

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

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

Решение задачи

Пусть  |Y| = M - число классов, каждый класс y \in Y имеет свою плотность распределения p_y(x) и представлен частью выборки X ^l _y = \{(x_i, y_i) \in X ^l | y_i = y \}.
Здесь Y - множество ответов (классов),y \in Y , x_i принадлежит множеству объектов X

Гипотеза

Плотности классов p_y(x), y \in Y , представимы в виде смесей k_y компонент. Каждая компонента имеет n-мерную гауссовскую плотность с параметрами
\mu _{yj} = (\mu _{yj1}, \dots , \mu _{yjn}) - центр,
\Sigma _{yj} = diag(\sigma  _{yj1}, \dots , \sigma  _{yjn}) - ковариационная матрица
j = 1, . . . , k_y:

 p_y(x) = \sum ^{k _y} _{j = 1} \omega _{yj} p _{yj}(x), - смесь плотностей
p_{yj}(x) = N(x; \mu _{yj} ,\Sigma _{yj}), - плотность каждой компоненты смеси (имеет вид гауссианы)
 \Sigma ^{k_y} _{j = 1} \omega _{yj} = 1, \omega _{yj} > 0; - условия нормировки и неотрицательности весов

Алгоритм классификации

Запишем основную формулу байесовского классификатора a(x) = argmax _{y \in Y} \lambda _y P _y p_y(x). Здесь Y - множество ответов (классов), x принадлежит множеству объектов X , P_y - априорная вероятность класса y , p_y(x) - функция правдоподобия класса y , \lambda_{y} - цена ошибки на объекте класса y. Выразим плотность каждой компоненты p_{yj}(x) через взвешенное евклидово расстояние от объекта x до центра компоненты \mu _{yj}(другими словами - подставим в основную формулу байесовского классификатора вместо p_y(x) формулы, которые мы предположили в гипотезе) :

a(x) = argmax _{y \in Y} \lambda _y P _y \sum ^{k_y} _{j = 1} N _{yj} exp(-1/2 \rho  _{yj} (x, \mu _{yj}))

где N _{yj} = (2\pi)^{-n/2} (\sigma _{yj1},\dots , \sigma _{yjn})^{-1} — нормировочные множители. Алгоритм имеет вид нейронной сети, состоящей из трёх уровней или слоёв.
Изображение:NS.PNG
Первый слой образован k_1 + \dots+ k_M гауссианами p_{yj}(x), y \in Y , j = 1, \dots, k_y. На входе они принимают описание объекта x, на выходе выдают оценки близости объекта x к центрам \mu _{yj} , равные значениям плотностей компонент в точке x.
Второй слой состоит из M сумматоров, вычисляющих взвешенные средние этих оценок с весами w_{yj} . На выходе второго слоя появляются оценки близости объекта x каждому из классов, равные значениям плотностей классов p_{yj}(x).
Третий слой образуется единственным блоком argmax, принимающим окончательное решение об отнесении объекта x к одному из классов.
Таким образом, при классификации объекта x оценивается его близость к каж- дому из центров \mu _{yj} по метрике \rho _{yj}(x, \mu _{yj}), j = 1, \dots, k_y. Объект относится к тому классу, к чьим центрам он располагается ближе.

Описанный трёхуровневый алгоритм классификации называется сетью c радиальными базисными функциями или RBF-сетью (radial basis function network). Это одна из разновидностей нейронных сетей.

Обучение RBF-сети

Обучение сводится к восстановлению плотности каждого из классов p_y(x) с помощью EM-алгоритма. Результатом обучения являются центры \mu _{yj} и дис- персии \Sigma _{yj} компонент j = 1, . . . , k_y. Интересно отметить, что, оценивая дисперсии, мы фактически подбираем метрики \rho _{yj} , с помощью которых будут вычисляться расстояния до центров \mu _{yj} . При использовании Алгоритма, описанного в данной статье, для каждого класса определяется оптимальное число компонент смеси.[1]

Литература


См. также


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

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

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

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