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

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

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

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

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

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

Студент: Участник: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)\}$ и $\{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$ .