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

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

Версия от 23:56, 3 января 2010; Osa (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

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

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

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

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

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

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

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

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

Содержание

[убрать]

1 Введение
2 Основная формула
3 Выбор параметров
4 Преимущества и недостатки

Введение

Общая идея метода иллюстрируется на примере электростатического взаимодействия элементарных частиц. Известно, что потенциал («мера воздействия») электрического поля элементарной заряженной частицы в некоторой точке пространства пропорционален отношению заряда частицы (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)\}$ и $\{h(x_i)\}$ .

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

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

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

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

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

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

   2.2   Если , то ;

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

4. Вернуть значения  для всех .

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

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

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

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

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