Метод потенциальных функций

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

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

Перейти к: навигация, поиск

Версия 12:41, 3 января 2010

Данная статья является непроверенным учебным заданием.

Студент: Участник:osa

Преподаватель: Участник:Константин Воронцов

Срок: 25 января 2010

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

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

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

Введение

Общая идея метода иллюстрируется на примере электростатического взаимодействия элементарных частиц. Известно, что потенциал («мера воздействия») электрического поля элементарной заряженной частицы в некоторой точке пространства пропорционален отношению заряда частицы (Q) к расстоянию до частицы (r): $\varphi(r) \sim \frac{Q}{r}$ .

Основная формула

Пусть имеется пространство объектов $X$ с заданной метрикой $\rho: X \times X \to R$ и множество ответов $Y$ . Пусть задана обучающая выборка пар «объект—ответ» $X^m = \{(x_1,y_1),\dots,(x_m,y_m)\} \subseteq X \times Y$ .

Пусть также имеется классифицируемый объект $u \in X$ .

Перенумеруем объекты обучающей выборки $x_i \in X^l$ относительно удаления от объекта $u$ индексами $x_u^{p}$ ( $p=\overline{1,l}$ ) – то есть таким образом, что $\rho(u,x_u^{(1)}) \leq \rho(u,x_u^{(2)}) \leq \dots \leq \rho(u,x_u^{(l)})$ .

В общем виде, алгоритм ближайших соседей есть:

$a(u) = \mathrm{arg}\max_{y\in Y} \sum_{i=1}^m \bigl[ x_{i; u}=y \bigr] w(i,u)$ , где $w(i,u)$ – мера «важности» (вес) объекта $x_u^{(i)}$ из обучающей выборки относительно классифицируемого объекта $u$ .

Метод потенциальных функций заключается в выборе в качестве $w(i,u)$ весовой функции следующего вида:

$w(i,u)=\gamma(x_u^{(i)}) K \left(\frac{\rho(u,x_u{(i)})}{h(x_u{(i)})}\right)$ , где

$K(r) = \frac{1}{r+a}$ . Константа $a$ нужна чтобы избежать проблем с делением на ноль. Для простоты обычно полагают $a=1$ .

$\rho(u,x_u{(i)})$ – расстояние от объекта u до i-того ближайшего к u объекта – $x_u^{(i)}$ .

$\gamma(x_u^{(i)})$ – параметр. Общий смысл – «потенциал» объекта $x_i \in X^l$ , $i=\overline{1,l}$ ;

$h(x_u{(i)})$ – параметр. Общий смысл – «ширина потенциала» объекта $x_i \in X^l$ , $i=\overline{1,l}$ . Вводится по аналогии с шириной окна в методе парзеновского окна.

Выбор параметров

Как мы уже заметили, в основной формуле метода потенциальных функций используются две группы параметров:

$\gamma(x_i)$ – «потенциал» объекта $x_i \in X^l$ , $i=\overline{1,l}$
$h(x_i)$ – «ширина потенциала» объекта $x_i \in X^l$ , $i=\overline{1,l}$ – аналог ширины окна в методе парзеновского окна.

Ниже приведён алгоритм, который позволяет «обучать» параметры $(\gamma(x_1), \dots, \gamma(x_n))$ , то есть подбирать их значения по обучающей выборке $X^l$ .

Вход: Обучающая выборка из  пар «объект-ответ» – . 

Выход: Значения параметров  для всех   
 

1.   Начало. Инициализация:  для всех ; 

2.   Повторять {

3.      Выбрать очередной объект  из выборки ;

4.      Если , то ;

5.   } пока  (то есть пока процесс не стабилизируется).

Преимущества и недостатки

Преимущества метода потенциальных функций:

Метод прост для понимания и алгоритмической реализации;
Порождает потоковый алгоритм;
Хранит лишь часть выборки, следовательно, экономит память.

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

Порождаемый алгоритм медленно сходится;
Параметры $\{\gamma_i\}$ и $\{h_i\}$ настраиваются слишком грубо;
Значения параметров $(\gamma_1,\dots,\gamma_l)$ зависят от порядка выбора объектов из выборки $X^l$ .

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BF%D0%BE%D1%82%D0%B5%D0%BD%D1%86%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D1%85_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B9»

Категория: Непроверенные учебные задания

@@ Строка 1: / Строка 1: @@
 {{Задание|osa|Константин Воронцов|25 января 2010}}
-'''Метод потенциальных функций''' - [[метрический классификатор]], частный случай [[Метод ближайших соседей|метода ближайших соседей]].
+'''Метод потенциальных функций''' - [[метрический классификатор]], частный случай [[Метод ближайших соседей|метода ближайших соседей]]. Позволяет с помощью простого алгоритма оценивать вес («важность») объектов [[Выборка|обучающей выборки]] при решении задачи классификации.
 == Введение ==
-Общая идея метода иллюстрируется на примере электростатического взаимодействия элементарных частиц. Известно, что потенциал электрического поля элементарной заряженной частицы в некоторой точке пространства пропорционален отношению ''заряда'' частицы (Q) к расстоянию до частицы (r): <tex>\varphi(r) \sim \frac{Q}{r}</tex>
+Общая идея метода иллюстрируется на примере электростатического взаимодействия элементарных частиц. Известно, что потенциал («мера воздействия») электрического поля элементарной заряженной частицы в некоторой точке пространства пропорционален отношению ''заряда'' частицы (Q) к расстоянию до частицы (r): <tex>\varphi(r) \sim \frac{Q}{r}</tex>.
 == Основная формула ==
+Пусть имеется пространство объектов <tex>X</tex> с заданной метрикой <tex>\rho: X \times X \to R</tex> и множество ответов <tex>Y</tex>.
+Пусть задана [[обучающая выборка]] пар «объект—ответ»
+<tex>X^m = \{(x_1,y_1),\dots,(x_m,y_m)\} \subseteq X \times Y</tex>.
-<tex>w(i,u)=\gamma(x_u^{(i)}) K \left(\frac{\rho(u,x_u{(i)})}{h(x_u{(i)})}\right)</tex>, где
+Пусть также имеется классифицируемый объект <tex>u \in X</tex>.
-* <tex>K(r) = \frac{1}{r+a}</tex> – потенциальная функция. Константа <tex>a</tex> вводится чтобы избежать проблем с делением на ноль и берётся произвольно (например, <tex>a=1</tex>).
+Перенумеруем объекты обучающей выборки <tex>x_i \in X^l</tex> относительно удаления от объекта <tex>u</tex> индексами <tex>x_u^{p}</tex> (<tex>p=\overline{1,l}</tex>) – то есть таким образом, что <tex>\rho(u,x_u^{(1)}) \leq \rho(u,x_u^{(2)}) \leq \dots \leq \rho(u,x_u^{(l)})</tex>.
+В общем виде, [[алгоритм]] [[Метод ближайших соседей|ближайших соседей]] есть:
+::<tex>a(u) = \mathrm{arg}\max_{y\in Y} \sum_{i=1}^m \bigl[ x_{i; u}=y \bigr] w(i,u)</tex>, где <tex>w(i,u)</tex> – ''мера «важности»'' (''вес'') объекта <tex>x_u^{(i)}</tex> из [[Выборка|обучающей выборки]] относительно классифицируемого объекта <tex>u</tex>.
+'''Метод потенциальных функций''' заключается в выборе в качестве <tex>w(i,u)</tex> весовой функции следующего вида:
+:: <tex>w(i,u)=\gamma(x_u^{(i)}) K \left(\frac{\rho(u,x_u{(i)})}{h(x_u{(i)})}\right)</tex>, где
+* <tex>K(r) = \frac{1}{r+a}</tex>. Константа <tex>a</tex> нужна чтобы избежать проблем с делением на ноль. Для простоты обычно полагают <tex>a=1</tex>.
 * <tex>\rho(u,x_u{(i)})</tex> – расстояние от объекта u до i-того ближайшего к u объекта – <tex>x_u^{(i)}</tex>.
-* <tex>\gamma(x_u^{(i)})</tex> – параметр;
+* <tex>\gamma(x_u^{(i)})</tex> – параметр. Общий смысл – «потенциал» объекта <tex>x_i \in X^l</tex>, <tex>i=\overline{1,l}</tex>;
-* <tex>h(x_u{(i)})</tex> – параметр.
+* <tex>h(x_u{(i)})</tex> – параметр. Общий смысл – «ширина потенциала» объекта <tex>x_i \in X^l</tex>, <tex>i=\overline{1,l}</tex>. Вводится по аналогии с шириной окна в [[Метод парзеновского окна|методе парзеновского окна]].
-Вопрос о выборе параметров (их 2l). Необходимо обучать их по выборке.
@@ Строка 26: / Строка 38: @@
 Как мы уже заметили, в основной формуле метода потенциальных функций используются две группы параметров:
 * <tex>\gamma(x_i)</tex> – «потенциал» объекта <tex>x_i \in X^l</tex>, <tex>i=\overline{1,l}</tex>
-* <tex>h(x_i)</tex> – «ширина потенциала» объекта <tex>x_i \in X^l</tex>, <tex>i=\overline{1,l}</tex> – своеобразный аналог ширины окна в [[Метод парзеновского окна|методе парзеновского окна]].
+* <tex>h(x_i)</tex> – «ширина потенциала» объекта <tex>x_i \in X^l</tex>, <tex>i=\overline{1,l}</tex> – аналог ширины окна в [[Метод парзеновского окна|методе парзеновского окна]].
 Ниже приведён алгоритм, который позволяет «обучать» параметры <tex>(\gamma(x_1), \dots, \gamma(x_n))</tex>, то есть подбирать их значения по обучающей выборке <tex>X^l</tex>.
- Вход: Обучающая выборка из <tex>l</tex> объектов – <tex>X^l</tex>. <br />
+ Вход: Обучающая выборка из <tex>l</tex> пар «объект-ответ» – <tex>X^l=((x_1,y_1), \dots, (x_l,y_l) )</tex>. <br />
- Выход: Значения параметров <tex>\gamma_i \equiv \gamma(x_i)</tex> для <tex>i=\overline{1,l}</tex>  <br /> <br />
+ Выход: Значения параметров <tex>\gamma_i \equiv \gamma(x_i)</tex> для всех <tex>i=\overline{1,l}</tex>  <br /> <br />
 .   Начало. Инициализация: <tex>\gamma_i:=0</tex> для всех <tex>i=\overline{1,l}</tex>; <br />
 .   Повторять {<br />
@@ Строка 37: / Строка 49: @@
 .      Если <tex>a(x_i) \not= y_i</tex>, то <tex>\gamma_i:=\gamma_i+1</tex>;<br />
 .   } пока <tex>Q(a,X^l) > \varepsilon</tex> (то есть пока процесс не стабилизируется).<br />
+== Преимущества и недостатки ==
+Преимущества метода потенциальных функций:
+* Метод прост для понимания и алгоритмической реализации;
+* Порождает потоковый алгоритм;
+* Хранит лишь часть выборки, следовательно, экономит память.
+Недостатки метода:
+* Порождаемый алгоритм медленно сходится;
+* Параметры <tex>\{\gamma_i\}</tex> и <tex>\{h_i\}</tex> настраиваются слишком грубо;
+* Значения параметров <tex>(\gamma_1,\dots,\gamma_l)</tex> зависят от порядка выбора объектов из выборки <tex>X^l</tex>.

Метод потенциальных функций

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

Версия 12:41, 3 января 2010

Содержание

Введение

Основная формула

Выбор параметров

Преимущества и недостатки

Просмотры

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

Навигация

Поиск

Инструменты