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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Выбор параметров)
(переработка)
Строка 1: Строка 1:
{{Задание|osa|Константин Воронцов|25 января 2010}}
{{Задание|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>\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>\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>(\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 />
1. Начало. Инициализация: <tex>\gamma_i:=0</tex> для всех <tex>i=\overline{1,l}</tex>; <br />
1. Начало. Инициализация: <tex>\gamma_i:=0</tex> для всех <tex>i=\overline{1,l}</tex>; <br />
2. Повторять {<br />
2. Повторять {<br />
Строка 37: Строка 49:
4. Если <tex>a(x_i) \not= y_i</tex>, то <tex>\gamma_i:=\gamma_i+1</tex>;<br />
4. Если <tex>a(x_i) \not= y_i</tex>, то <tex>\gamma_i:=\gamma_i+1</tex>;<br />
5. } пока <tex>Q(a,X^l) > \varepsilon</tex> (то есть пока процесс не стабилизируется).<br />
5. } пока <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>.

Версия 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};


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

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

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

Вход: Обучающая выборка из l пар «объект-ответ» – X^l=((x_1,y_1), \dots, (x_l,y_l) ). 
Выход: Значения параметров \gamma_i \equiv \gamma(x_i) для всех i=\overline{1,l}

1. Начало. Инициализация: \gamma_i:=0 для всех i=\overline{1,l};
2. Повторять {
3. Выбрать очередной объект x_i из выборки X^l;
4. Если a(x_i) \not= y_i, то \gamma_i:=\gamma_i+1;
5. } пока Q(a,X^l) > \varepsilon (то есть пока процесс не стабилизируется).


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

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

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

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

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