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

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

(Различия между версиями)
Перейти к: навигация, поиск
(переработка)
(→Выбор параметров)
Строка 36: Строка 36:
== Выбор параметров ==
== Выбор параметров ==
-
Как мы уже заметили, в основной формуле метода потенциальных функций используются две группы параметров:
+
Как мы уже заметили, в основной формуле метода потенциальных функций используются две группы параметров: <tex>\{\gamma(x_i)\}</tex> и <tex>\{h(x_i)\}</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>(\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>.
Строка 49: Строка 47:
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 />
-
 
== Преимущества и недостатки ==
== Преимущества и недостатки ==

Версия 23:08, 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_i)\} и \{h(x_i)\}.

Ниже приведён алгоритм, который позволяет «обучать» параметры (\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.
Источник — «http://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»
Личные инструменты