Обучение по прецедентам (по Вапнику, Червоненкису)

12.1. Задача построения классификатора

Пусть

Тогда $$g:\Omega\rightarrow M$$.

Пусть также

Тогда $$\widehat{g}:X\rightarrow M$$

Выбор решающего правила исходит из минимизации $$d(g,\widehat{g})\rightarrow\min$$, где $$d$$ – метрика, мера близости функций $$g(\omega)$$ и $$\widehat{g}(x(\omega))$$. Построение $$\widehat{g}$$ называют задачей обучения. $$\widehat{g}$$ – это ученик, процедура формирования – это учитель, прецеденты – это обучающая последовательность.

12.2. Качество обучения классификатора

Относительная доля несовпадений классификации с учителем для решающего правила есть: $$K=\frac{m}{N}$$, где $$m=|\{\omega_i:g(\omega_i)\neq\widehat{g}(x(\omega_i)),\;i=1,2,\ldots,N\}|$$. Надежность обучения классификатора – это вероятность получения решающего правила с заданным качеством.

Пусть $$f(x,\alpha)$$ – класс дискриминантных функций, где $$\alpha\in A$$ – параметр. Число степеней свободы при выборе конкретной функции в классе определяется количеством параметров в векторе $$\alpha$$, т.е. размерностью $$A$$.

Например, для классов линейных и квадратичных функций имеем:

Линейная дискриминантная функция: $$f(x,\alpha)=\sum_{i=1}^n\alpha_i x_i+\alpha_0$$. В таком случае имеем $$n+1$$ степень свободы.

Квадратичная дискриминантная функция: $$f(x,\alpha)=\sum_{i=1}^n\sum_{j=1}^n\alpha_{ij}x_i x_j+\sum_{i=1}^n\beta_i x_i+\beta_0$$. В таком случае имеем $$n^2+n+1$$ степеней свободы.

С увеличением степеней свободы увеличивается способность классификатора по разделению.

12.3. Вероятностная модель

Пусть прецеденты – это результат реализации случайных величин. Рассмотрим величину риска (т.е. ошибки) связанной с классификацией. Определим понятия риск среднего и риска эмпирического.

Пусть на $$\Omega$$ заданы $$\sigma$$ -алгебра и мера $$P$$. Пусть также

Тогда $$\widehat{g}=f(x,\alpha)$$, где $$f\in\widetilde{f}$$ и $$f:X\times A\rightarrow M$$, $$y=g(\omega)$$.

В данных обозначениях средний риск выглядит следующим образом:$$K(\alpha)=\int\limits_X \chi\{y\neq f(x,\alpha)\}dP.$$

Для случая двух классов, при $$M=\{0,1\}$$, имеем:$$K(\alpha)=\int\limits_{\Omega}(y-f(x,\alpha))^2 dP$$ или$$K(\alpha)=\int\limits_{(X,M)}(y-f(x,\alpha))^2 dP(x,y),$$ где $$dP$$ – это вероятностная мера на пространстве $$X$$.

12.4. Задача поиска наилучшего классификатора

Рассмотрим минимизацию функционала:$$K(\alpha)\rightarrow\min_{\alpha\in A}$$

Задача же поиска наилучшего классификатора состоит в нахождении $$\alpha^*$$ такого, что$$K(\alpha^*)=\min_{\alpha\in A}K(\alpha)$$

Если же минимума не существует, то надо найти $$\alpha^*$$ такое, что$$\left| K(\alpha^*)-\inf_{\alpha\in A}K(\alpha) \right| <\delta.$$

Другими словами, необходимо решить задачу минимизации среднего риска.

Поскольку $$dP$$ неизвестно, будем решать задачу минимизации эмпирического риска. Пусть $$l$$ – число прецедентов. Тогда эмпирический риск задается выражением:$$K_{\textit{эмп}}(\alpha)=\frac{1}{l}\sum_{i=1}^l\left|y-f(x,\alpha)\right|.$$

Таким образом, задача минимизации эмпирического риска выглядит так:$$K_{\textit{эмп}}(\alpha)\rightarrow\min_{\alpha\in A},$$ где случайные величины мы минимизируем по параметру $$\alpha$$ – любой возможный параметр.

В идеале надо получить взаимосвязанные оценки эмпирического и среднего риска.

Отметим, что чем меньше $$l$$, тем легче построить $$f(x,\alpha)$$ такую, что $$K_{\textit{эмп}}(\alpha)$$ обращается в ноль, либо очень мало. Но при этом истинное значение $$K(\alpha)$$ может сильно отличаться от $$K_{\textit{эмп}}(\alpha)$$. Необходимо выбрать $$f(x,\alpha)$$ такую, чтобы имела место равномерная сходимость по $$\alpha$$ выражения:$$P \left\{ \sup_{\alpha} \left| K_{\textit{эмп}}(\alpha)-K(\alpha) \right| >\varepsilon \right\} \xrightarrow[l\rightarrow\infty]{\phantom{0}} 0.$$

Фактически это есть сходимость частот к математическому ожиданию.

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

12.5. Сходимость эмпирического риска к среднему. Случай конечного числа решающих правил.

Пусть

Воспользуемся неравенством Бернштейна, тогда$$P\{|v(A)-P(A)|>\varepsilon\}\leq e^{-2e^2 l}$$ есть оценка – соотношение между частотой и вероятностью при заданном количестве испытаний.

Пусть $$\xi_j$$ – случайная величина. Тогда $$E(\xi_j)=0$$ – математическое ожидание $$\xi_j$$, $$E\xi_j^2=\delta^2$$ – дисперсия, причем $$|\xi_j|\leq L$$. Обозначим $$S_0=\xi_1+\xi_2+\ldots+\xi_n$$. Тогда соответствующая оценка имеет вид:$$P \left\{ |S_n|>t\delta\sqrt{n} \right\} \leq 2\cdot\exp \left\{ -\frac{t^2}{2\cdot\left(1+\frac{a}{3}\right)} \right\}, \text{ где }a=\frac{L\cdot t}{\sqrt{n\delta}}.$$ $$l=\frac{\ln N-\ln\eta}{2e^2}\text{ и }e=\sqrt{\frac{\ln N-\ln\eta}{2l}},$$ где $$l$$ – необходимое количество прецедентов для обеспечения близости.

Теорема. Пусть из множества, состоящего из $$N$$ решающих правил, выбирается правило, частота ошибок которого на прецедентах составляет $$v$$. Тогда с вероятностью $$1-\eta$$ можно утверждать, что вероятность ошибочной классификации с помощью данного правила $$f(x\alpha)$$ составит величину, меньшую $$v+e$$, если длина обучающей последовательности не меньше $$l=\frac{\ln N-\ln\eta}{2e^2}$$, где $$e=\sqrt{\frac{\ln N-\ln\eta}{2l}}$$, $$\eta$$ и $$e$$ заданы и последовательность независима.

Данная теорема справедлива для случая конечного числа решающих правил. Вапник и Червоненкис смогли обобщить эти оценки на случай бесконечного числа решающих правил.

12.6. Случай бесконечного числа решающих правил

Введем понятие "разнообразия класса функций для бесконечного множества". Пусть $$x_1,x_2,\ldots,x_l$$ – прецеденты.

Определение. Дихотомией называется разбиение множества на два подмножества.

В нашем случае имеем $$2^l$$ дихотомий. Итак, пусть $$f(x,\alpha), \; \alpha\in A$$ – это класс решающих правил, причем $$f(x,\alpha)=\{0,1\}$$. Пусть $$\Delta(x_1,x_2,\ldots,x_l)$$ есть количество дихотомий на классе решающих правил. Тогда зададим энтропию следующим образом:$$H(l)=E\{\log_2\Delta(x_1,x_2,\ldots,x_l)\},$$ где математическое ожидание берется по всем выборкам $$(x_1,x_2,\ldots,x_l)$$. Тогда$$H^S(l)=E\{\log_2\Delta^S(x_1,x_2,\ldots,x_l)\}$$ есть энтропия класса $$S$$ решающих правил на выборках длины $$l$$.

12.6.1. Критерий равномерной сходимости $$v(\alpha)$$ к вероятностям $$P(\alpha)$$

Теорема. Для равномерной сходимости $$v(\alpha)=K_{\textit{эмп}}(\alpha)$$ к $$K(\alpha)=P(\alpha)$$ по классу $$\alpha\in A$$ необходимо и достаточно, чтобы $$\frac{H(l)}{l}\xrightarrow[l\rightarrow\infty]{\phantom{0}} 0$$.

Суть данного критерия – не пытаться выделить очень точный классификатор, так как это отдаляет от общности.

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

12.6.2. Достаточное условие равномерной сходимости

Проверка условия критерия равномерной сходимости по вероятности затрудняется неопределенностью распределения выборки. Поэтому достаточные условия формулируются таким образом, чтобы не зависеть от распределения и при этом гарантировать равномерную сходимость. В таком случае вместо энтропии рассматривается величина:$$m^S(l)=\max_{x_1,\ldots,x_l}\Delta^S(x_1,x_2,\ldots,x_l),$$ где $$m^S(l)$$ – это функция роста класса решающих функций $$f(x,\alpha)$$.

Т.к. логарифм максимума равен максимуму логарифмов, что, в свою очередь, не меньше математического ожидания от логарифма, то$$\log_2 m^S(l)\geq H^S(l).$$

Если$$\lim_{l\rightarrow\infty} \left\lfloor \log_2 m^S(l)/l \right\rfloor \rightarrow 0,$$ то по свойствам пределов$$\lim_{l\rightarrow\infty}\frac{H^S(l)}{l}\rightarrow\infty.$$

Данное условие легко проверятся для различных классов решающих правил.

Другими словами $$m^S(l)$$ можно трактовать как максимальное число способов разделения $$l$$ точек на два класса с помощью решающих правил $$f(x,\alpha),\;\alpha\in A$$.

Теорема. Функция роста либо тождественно равна $$2^l$$, либо, мажорируется функцией $$\sum_{i=0}^{n-1} C_l^i$$, где $$n$$ – минимальное значение $$l$$, при котором $$m^S(l)\neq 2^l$$, т.е. либо $$m^S(l)=2^l$$, либо $$m^S(l)\leq\sum_{i=0}^{n-1} C_l^i$$.

В свою очередь$$\sum_{i=0}^{n-1} C_l^i\leq 1,5\cdot\frac{l^{n-1}}{(n-1)!}.$$ Значит$$m^S(l)\leq 1,5\cdot\frac{l^{n-1}}{(n-1)!},$$ где $$l=1,2,\ldots,n$$, и $$\frac{l^{n-1}}{(n-1)!}$$ – степенная функция, мажорирующая $$m^S(l)$$.

Существует максимум $$n-1$$ точка, которая еще разбивается всеми возможными способами с помощью правила $$f(x,\alpha)$$, но никакие $$n$$ точек этим свойством не обладают.

Определение. $$n-1$$ называется емкостью класса решающих функций или мера разнообразия решающих правил в классе $$f()x,\alpha$$ или $$VC$$ – размерностью класса – универсальная характеристика класса решающих функций.

Отметим, что если $$m^S(l)=2^l$$ для всех $$l$$, то емкость бесконечна.

Теорема. Если емкость класса решающих функций конечна, то всегда имеет место равномерная сходимость частот к вероятностям такое, что$$\lim_{l\rightarrow\infty} \left( \frac{\log_2 m^S(l)}{l} \right) \leq\lim_{l\rightarrow\infty} \left( \frac{(n-1)\log l+\log 1.5}{l} \right) =0$$ и достаточное условие выполнено.

12.6.3. Скорость сходимости

Запишем оценку для бесконечного числа решающих правил. Ее вид аналогичен случаю конечного числа решающих правил:$$P \left\{ \sup_{\alpha}|P(\alpha)-v(\alpha)|>\varepsilon \right\} <3m^S(2l)\cdot e^{\frac{\varepsilon^2(l-1)}{4}}.$$

Если емкость бесконечна, то оценка тривиальная (не больше единицы). Пусть $$r$$ – конечная емкость класса решающих функций. Тогда$$P \left\{ \sup_{\alpha}|P(\alpha)-v(\alpha)|>\varepsilon \right\} <4,5\cdot\frac{(2l)^r}{r}\cdot e^{\frac{\varepsilon^2(l-1)}{4}}.$$

Введем обозначение: $$\eta=4,5\cdot\frac{(2l)^r}{r}\cdot e^{\frac{\varepsilon^2(l-1)}{4}}$$, Тогда $$P \left\{ \sup_{\alpha}|P(\alpha)-v(\alpha)|>\varepsilon \right\} <\eta $$.

Отсюда следует, что $$\varepsilon=\sqrt{\frac{r\left(\ln\frac{2l}{r}+1\right)-\ln\frac{\eta}{5}}{l-1}} $$.

Значит, с вероятностью, превышающей $$1-\eta$$ качество эмпирического оптимального решающего правила отличается от истинно оптимально решающего правила не более чем на величину $$\Delta=2\varepsilon$$.

В следующей таблице представлен некоторый итог наших рассуждений.

Таким образом, необходимо минимизировать степени свободы.

12.6.4. Случай класса линейных решающих функций

Пусть $$f(x,\alpha)$$ – линейная решающая функция, $$m$$ – размерность пространства.

Как уже отмечалось выше, имеем $$2^l$$ дихотомий, где $$l$$ – длина выборки. Хотим выяснить, какое количество дихотомий реализуется с помощью гиперплоскостей?

Максимальное число точек в пространстве размерности $$ь$$, которое с помощью гиперплоскостей можно разбить всеми возможными способами на два класса есть $$ь+1$$. Если $$m^S(l)\leq 1,5\cdot\frac{l^{m+1}}{(m+1)!}$$, то линейный риск будет равномерно сходиться к среднему риску. Емкость класса конечна и равна $$m+1$$.