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

Рассмотрим множество прецедентов. Пусть каждый из них имеет поле притяжения. Берем новый объект и смотрим, каким классом притягивается.

Пусть $$L=2$$ – число классов. Обозначим эти классы через $$K_1$$ и $$K_2$$ соответственно. Рассмотрим обучающую последовательность $$x_1,\ldots,x_{r_1},x_{r_1+1},\ldots,x_{r_2}$$. Без ограничения общности будем считать, что $$x_1,\ldots,x_{r_1}\in K_1$$ и $$x_{r_1+1},\ldots,x_{r_2}\in K_2$$.

Каждая точка образует в пространстве признаков $$X$$ некоторое поле притяжения. Например, можно рассматривать каждую точку как единичный заряд. Поле описывается потенциалом, создаваемым системой зарядов во всем пространстве.

В пространстве задана потенциальная метрика: $$K(x,y)$$ – потенциальная функция, $$x,y\in X$$ такая, что$$\begin{aligned} K(x,y)>0, \text{ при } x\neq y, \\ K(x,y)=K(x,x+\mu(y-x))=\widetilde{K}(\mu), \end{aligned}$$ где $$\widetilde{K}(\mu)$$ – монотонно убывающая функция и $$\widetilde{K}(0)$$ – ее максимальное значение.

Пример. Пусть $$d(x,y)$$ – расстояние в $$R^2$$. Рассмотрим функцию $$K(x,y)=K(d(x,y))$$. Пусть $$\alpha$$ – параметр функции. Рассмотрим два примера функций $$k(x,y)$$:$$\begin{aligned} K(x,y)=e^{-\alpha^2d^2(x,y)}\text{ рис. слева}, \\ K(x,y)=\frac{1}{1+\alpha^2d^2(x,y)}\text{ рис. справа} \end{aligned}$$

Пусть $$X$$ и $$\overline{X}$$ – прецеденты первого и второго класса соответственно, $$y$$ – пробный образ. Тогда потенциалы, создаваемые в пространстве точками из классов $$X$$ и $$\overline{X}$$ будут иметь вид:$$K_X(y)=\sum_{x\in X}K(x,y),\;K_{\overline{X}}(y)=\sum_{\overline{x}\in\overline{X}}K(\overline{x},y)$$ соответственно.

Тогда правило классификации можно записать следующим образом: Если $$K_X(y)>K_{\overline{X}}(y)$$ то пробный образ $$y$$ относится к классу $$X$$, иначе к классу $$\overline{X}$$, при равенстве выдавать ответ "не знаю" (отказ от распознавания).

Если рассмотреть дискриминантную функцию $$\Phi(x)=K_X(x)-K_{\overline{X}}(x)$$, то задача сводится к поиску этой функции по обучающей последовательности.

Рассмотрим вариант метода потенциальных функций называется "наивным". Он имеет следующие недостатки. Если, например, в первом классе точек много больше, чем в остальных, то голоса первого класса подавят голоса других классов, то есть потенциал $$o$$ больше потенциала $$x$$ (рис. слева). Но даже, если множества соизмеримы, могут возникнуть проблемы другого характера, например, погружение одних точек в другие (рис. справа). Поэтому наивный метод подлежит усовершенствованию.

6.1. Общая рекуррентная процедура

Пусть $$\{\varphi_i(x)\}$$ – конечная или бесконечная система функций на $$X$$. Будем искать дискриминантную функцию в виде$$\Phi(x)=\sum_i c_i\varphi_i(x).$$

Требования к рассматриваемому ряду:

Для бесконечного ряда требуем поточечную сходимость.

Также желательно, чтобы $$c_i$$ убывали быстро с ростом $$i$$. Это необходимо для обеспечения хорошего совпадения "обрезанного" бесконечного ряда с $$\Phi(x)$$.

Итак, пусть $$\{\varphi_i(x)\}$$ – базовая система функций. В качестве потенциальной функции будем рассматривать функцию вида$$K(x,y)=\sum_i \lambda_i^2\varphi_i(x)\varphi_i(y),$$ где $$\lambda_i$$ удовлетворяет условиям: $$\sum_i\lambda_i^2<\infty$$ и $$\lambda_i\neq 0$$. Обозначим $$\psi_i(x)=\lambda_i\varphi_i(x)$$. Тогда$$K(x,y)=\sum_i\psi_i(x)\varphi_i(y).$$ Предположим, что$$K(x,x)=\sum_i\varphi_i^2(x)\leq M=const,$$ Тогда$$K(x,y)=\sum_i\psi_i(x)\varphi_i(y)\leq M.$$

Для приближения $$\Phi(x)$$ предлагается рекуррентная процедура, называемая общей рекуррентной процедурой:$$\Phi_{n+1}=q_n*\Phi_n(x)+r_n*K(x_{n+1},x), \; n=1,2,\ldots$$

Пусть

Зададим начальное приближение $$\Phi_0(x)=0$$. Как уже отмечалось, мы ищем функцию $$\Phi(x)$$ в виде:$$\Phi(x)=\sum_{i=1}^{\infty}c_i \varphi_i(x).$$

Мы сделали достаточно сильное допущение, сказав, что наше решение будем выражать через базовую систему функций. Т.е. мы априорно предполагаем, что $$\Phi_n(x)$$ разложимо по системе функций $$\{\varphi_i(x)\}$$:$$K(x,y)=\sum_{i=1}^{\infty}\lambda_i^2\varphi_i(x)\varphi_j(x) \text{ и } \Phi_k(x)=\sum_{i=1}^{\infty}c_i^k\varphi_i(x).$$

Тогда, учитывая, что $$K(x_{n+1},x)=\sum_i\psi_i(x_{n+1})\psi_i(x)$$, получаем:$$\sum_i c_i^{n+1}\varphi_i(x)=q_n\sum_i c_i^n\varphi_i(x)+r_n\sum_i\psi_i(x_{n+1})\psi_i(x).$$

Обозначим через$$\overline{c}_i^k=\frac{c_i^k}{\lambda_i},\;i,k=1,2\ldots$$

Тогда$$\overline{c}_i^{n+1}\psi_i(x)=q_nc_i^n\psi_i(x)+r_n\psi_i(x_{n+1})\psi_i(x).$$

Откуда получаем вторую форму общей рекуррентной процедуры:$$\overline{c}_i^{n+1}=q_nc_i^n+r_n\psi_i(x_{n+1}).$$

Для нахождения связи коэффициентов $$\{c_i^k\}$$ и $$\{c_i^{k+1}\}$$ воспользуемся второй формой для формулы общей рекуррентной процедуры и соотношением$$\overline{c}_i^k=\frac{c_i^k}{\lambda_i},\; i,k=1,2,\ldots$$

Получим соотношение, связывающее коэффициенты $$\{c_i^k\}$$ и $$\{c_i^{k+1}\}$$:$$\frac{c_i^{n+1}}{\lambda_i}=q_n c_i^n+r_n\psi_i(x_{n+1}), \text{ где } \psi_i=\lambda_i\varphi_i(x)$$

Для возможности итерационных вычислений необходимо понять, как вычислять параметры $$q_n$$ и $$r_n$$, а также начальное приближение $$c_i^0$$.

Зададим функцию$$\Phi_i(x)= \left\{ \begin{aligned} K(x,x_i),\text{ при } x_i\in X \\ -K(x,x_i),\text{ при } x_i\in \overline{X} \end{aligned} \right.$$ где$$K(x,x_m)=\sum_{i=1}^{\infty}\lambda_i^2\varphi_i(x)\varphi_i(x_m)\text{ и }c_i^0=\pm(\lambda_i^2\varphi_i(x_1))$$

Тогда процесс перехода от $$\Phi_n$$ к $$\Phi_{n+1}$$ суть процесс подсчета коэффициентов. Обычно $$q_n=1,\;r_n$$, вычисляется по следующему правилу:$$r_n= \left\{ \begin{aligned} 0,\text{ если }\Phi_n(x_{n+1})>0\text{ и }x_{n+1}\in X \\ 0,\text{ если }\Phi_n(x_{n+1})<0\text{ и }x_{n+1}\in \overline{X} \\ 1,\text{ если }\Phi_n(x_{n+1})<0\text{ и }x_{n+1}\in X \\ -1,\text{ если }\Phi_n(x_{n+1})>0\text{ и }x_{n+1}\in \overline{X} \end{aligned} \right..$$

Возьмем следующее начальное приближение:$$\Phi_1(x)= \left\{ \begin{aligned} K(x,x),\text{ при } x_1\in X \\ -K(x,x),\text{ при } x_1\in\overline{X} \end{aligned} \right.$$

Таким образом, при правильном определении $$\Phi_{n+1}$$ получаем, что $$\Phi_{n+1}(x)=\Phi_n(x)$$ ; а в случае ошибки$$\Phi_{n+1}(x) \left\{ \begin{aligned} \Phi_n(x)+K(x_{n+1},x)\text{ при } x_{n+1}\in X \\ \Phi_n(x)-K(x_{n+1},x)\text{ при } x_{n+1}\in \overline{X} \end{aligned} \right.$$

Данный процесс напоминает обучение в алгоритме персептрона.

Возникают следующие естественные вопросы:

Есть ли поточечная сходимость функции $$\Phi_n(x)$$ к $$\Phi(x)$$?

Где взять базисные функции $$\varphi_i(x)$$ в многомерном пространстве?

Попробуем ответить на эти вопросы.

Рассмотрим аналогию данного алгоритма с алгоритмом персептрона. Для функции$$\Phi_n(x)=\sum_{i+1}^{\infty}c_i^k\varphi_i(x)$$ произведем замену $$\varphi_i(x)=z_i$$ и $$z=(z_1,z_2,\ldots),\;z\in Z$$ – это вектор в бесконечномерном пространстве, тогда$$\Phi(x)=\sum_{i+1}^{\infty}c_i\varphi_i(x)=\sum_{i+1}^{\infty}c_i z_i,$$ где $$z$$ – спрямляющее пространство. Таким образом, если $$\Phi(x)>0$$ или $$\Phi(x)<0$$, то $$\sum_{i+1}^{\infty}c_i z_i>0$$ или $$\sum_{i+1}^{\infty}c_i z_i<0$$ соответственно. Пусть $$x_k\in X\bigcup\overline{X}$$, тогда $$x_k \rightarrow(z_1^k,z_2^k,\ldots)$$ и $$z_1^k=\varphi_i(x_k)$$.

6.2. Выбор системы функций

$$\{\varphi_i(x)\}$$. Система функций $$\{\varphi_i(x)\}$$ задается априорно. Обычно используют некую полную систему функций, например, на конечном отрезке можно взять систему тригонометрических функций. Эта система к тому же ортогональна.

Утверждение. Если задана полная ортогональная система функций одной переменной, то можно построить полную ортогональную систему функций любого числа переменных.

Доказательство. Пусть $$\{\varphi_i(x)\}$$ – полная ортогональная система функций на конечном интервале $$I$$. Рассмотрим систему$$\left\{ \varphi_{i_1,\ldots,i_m}(x_1,\ldots,x_m)=\varphi_{i_1}(x_1),\ldots,\varphi_{i_m}(x_m) \right\} ,\;i_1,\ldots,i_m=0,1,2,\ldots$$

Эта система полна и ортогональна на декартовом произведении $$m$$ экземпляров $$I$$, то есть на $$\underbrace{I\times I\times\ldots\times I}_{m\text{ раз}}$$..

Проверим ортогональность. В скалярном произведении двух различных функций $$\varphi_{i_1,\ldots,i_m}$$ и $$\varphi_{j_1,\ldots,j_m}$$:$$\int\limits_I\ldots\int\limits_I(\varphi_{i_1,\ldots,i_m},\varphi_{j_1,\ldots,j_m})dx_1\ldots dx_m$$ всегда найдется такое $$k$$, что $$\varphi_{i_k}(x_k)\neq\varphi_{j_k}(x_k)$$ и, в силу ортогональности системы $$\{\varphi_i(x)\}$$, имеем:$$\int\limits_I(\varphi_{i_k}(x_k),\varphi_{j_k}(x_k))dx_k=0$$

Далее, пусть $$F(x_1,\ldots,x_m)$$ – произвольная функция $$m$$ переменных. Фиксируем все переменные, кроме $$x_1$$, и получаем разложение функции $$F$$:$$F=\sum_{i_1}c_{i_1}(x_2,\ldots,x_m)\varphi_{i_1}$$

Повторяем это рассуждение для $$c_{i_{`1}}$$ последовательности $$m-1$$ раз:$$F(x_1,\ldots,x_m)=\sum_{i_1,\ldots,i_m} c_{i_1\ldots i_m}\varphi_{i_1}(x_1)\ldots\varphi_{i_m}(x_m),$$ что и доказывает полноту системы$$\{\varphi_{i_1,\ldots,i_m}(x_1,\ldots,i_m)\},\; i_1,\ldots,i_m=0,1,2,\ldots$$

6.3. Сходимость общей рекуррентной процедуры

Предположим, что обучающая последовательность есть выборка конечного объема из пространства $$\widetilde{X}$$ ( $$\widetilde{X}$$ – пространство признаков). Тогда последовательность $$\{\Phi_n(x)\}$$ есть последовательность случайных функций, и последовательность $$c_i$$ – последовательность случайных чисел. Поэтому будем говорить о сходимости $$\{\Phi_n(x)\}$$ в вероятностном смысле, то есть либо по вероятности, либо с вероятностью равной 1, либо в среднем.

Пусть $$x$$ – случайные величины из $$\widetilde{X}$$, а $$X, \overline{X}$$ – выборка для конечного объекта.

Теорема. Пусть заданы два множества $$X$$ и $$\overline{X}$$ и выполнены следующие условия.

Теорема. Пусть выполнены все условия предыдущей теоремы. Пусть также на каждом $$n$$ -ом шаге работы общей рекуррентной процедуры существует строго положительная вероятность исправления ошибки, если функция $$\Phi_n(x)$$ к $$n$$ -ому шагу еще не разделила классы $$K_1$$ и $$K_2$$. Пусть с вероятностью единица для каждой реализации процедуры существует конечное число $$l$$ такое, что

$$\Phi_l(x)$$ – правильно разделяет $$X$$ и $$\overline{X}$$,

$$Z$$ – конечный интервал на прямой $$(Z\in R^1)$$,

$$\{\varphi_i(x)\}$$ – полная ортогональная система функций, $$\varphi_1(x)\rightarrow R^1$$,

$$\int\limits_Z \varphi_i(x)\varphi_j(x)dx=0$$ при $$i \neq j$$.

Тогда система функций $$\{\varphi_{i_1,\ldots,i_m}(x_1,\ldots,x_m)=\varphi_{i_1}(x_1)*\ldots*\varphi_{i_m}(x_m)\}$$ полна и ортогональна на пространстве $$\underbrace{Z\times\ldots\times Z}_{m\text{ раз}}$$.

Доказательство. Ортогональность очевидна. Докажем полноту. Пусть $$F(x_1,\ldots,x_m))$$ – произвольная функция в $$Z^m$$ такая, что $$Z^m\rightarrow R^1$$. Фиксируем переменные начиная с $$x_2$$, тогда$$F=F(x_1)=\sum_{i=1}^{\infty}c_i(x_1,\ldots,x_m)\cdot\varphi_i(x_1), \text{ где }c_1(x_2,\ldots,x_m)=\sum_{i=1}^{\infty}c_i(x_3,\ldots,x_m)\cdot\varphi_i(x_l).$$

6.4. Функции Эрмита

Если в качестве системы функций $$\{\varphi_i(x)\}$$ взять функции вида$$\varphi_i(x)=\frac{1}{\left(2_i i!\sqrt{\pi}\right)^{1\!/2}}e^{-\frac{x^2}{2}}H_i(x),$$ где $$H_i(x)=(-1)^i e^{x^2}\left(\frac{d}{dx}\right)^i e^{-x^2}$$ – полином Эрмита.

Тогда$$K(x,y)=\sum_{i=0}^{\infty}\lambda_i^2\varphi_i(x)\varphi_j(x).$$

Обозначим $$\alpha^i=\lambda_i^2$$, где $$|\alpha|<1$$, тогда$$K(x,y)=\frac{1}{\sqrt{\pi(1-\alpha)^2}}\exp\left[\frac{2xy\alpha-(x^2+y^2)\alpha^2}{1-\alpha^2}\right].$$