Комитетные методы решения задач распознавания

7.1. Теоретико-множественная постановка задачи выбора алгоритма.

Байесовский подход исходит из статистической природы наблюдений. За основу берется предположение о существовании вероятностной меры на пространстве образов, которая либо известна, либо может быть оценена. Цель состоит в разработке такого классификатора, который будет правильно определять наиболее вероятный класс для пробного образа. Тогда задача состоит в определении "наиболее вероятного" класса.

Пусть $$J$$ – индексное множество; $$D_j,\;j\in J$$ – подмножество некоторого множества (например, множества алгоритмов); $$D=\{D_j|j\in J\}$$ – система подмножеств. Пусть $$Y$$ – множество, в котором необходимо найти решение. Задача заключается в нахождении такого элемента $$y\in Y$$ такое, что $$y\in D_j\quad\forall j\in J$$.

Пример. Пусть $$X_1=\{x_1,x_2,\ldots\,x_{m_1}}$$, $$X_2=\{x_{m_1+1},x_{m_1+2},\ldots\,x_m}$$, $$x_j\in\Omega,\; J=\{1,2,\ldots,m\}$$. $$F:\Omega\rightarrow\{0,1\}$$ так, что $$F(x)= \left\{ \begin{aligned} 0,\;x\in X_1\\ 1,\;x\in X_2 \end{aligned} \right$$.

Тогда $$D_j$$ – множество алгоритмов, дающих правильную классификацию $$x_j$$:$$D_j= \left\{ F|F:\Omega\rightarrow\{0,1\},\;F(x_j)= \left\{ \begin{aligned} 0,1 \leq j\leq m_1 \\ \phantom{0,\,}1,\textit{иначе} \end{aligned} \right. \right\} ,\; j=1,2,\ldots,m$$

Определение. Пусть $$J'\in J,\;D'=\{D_j|j\in J'\}$$. Тогда система подмножеств $$D'$$ называется совместной, если $$\bigcap_J D_j\neq\varnothing$$.

В примере условием совместности является не пересекаемость множеств $$X_1$$ и $$X_2$$. Тогда, очевидно, что в пересечении $$\bigcap_J D_j$$ лежит $$\Phi:\Omega\rightarrow\{0,1\}$$, где$$\Phi(x_j)= \left\{ \begin{aligned} 0,1 \leq j\leq m_1 \\ \phantom{0,\,}1,\textit{иначе} \end{aligned} \right.$$

Тогда возникает вопрос: что делать, если $$D^*=\bigcap_{j\in J}D_j=\varnothing$$? Существует два способа решения данной проблемы:

Смягчить условия, описывающие $$D_j$$, т.е. построить $$\widetilde{D}=\left\{\widetilde{D}_j|j\in J,D_j\subseteq\widetilde{D}_j\right\}$$.

Решить задачу поиска максимальных совместных подсистем системы $$D'=\left\{D_j|j\in J\right\}$$, $$J'\subset J$$

Определени е. Теоретико-множественная задача называется разрешимой в классе $$Y$$, если $$Y\bigcap D^*\neq\varnothing$$, где $$D^*=\bigcap_{j\in J}D_j$$.

7.2. Комитеты

Нас интересует случай, когда теоретико-множественная задача не разрешима. Идея комитетного метода распознавания состоит в использовании нескольких классификаторов, каждый из которых дает свой результат. Далее по какому-либо общему правилу голосования на основе полученных результатов от каждого классификатора выдается итоговый результат.

Определение. Для исходной системы $$D$$ и числа $$p:\;0\leq p<1$$ конечное подмножество $$K\subseteq Y$$ называется $$p$$ -комитетом в классе $$Y$$, если для всех выполнено неравенство $$\left|K\bigcap D_j\right|>p|K|$$ (относительная доля $$K$$, лежащая в $$D_j$$, превосходит $$p$$ ). Если $$p=1\!/2$$, то $$p$$ -комитет называется просто комитетом.

Пример комитета для несовместной системы. Рассмотрим задачу исключающего или. $$x_0=(0,0)$$, $$x_1(1,1)$$, $$x_2=(0,1)$$, $$x_3=(1,0)$$. Пусть $$D$$ а – множество линейных классификаторов. Опишем множество $$D^*$$: $$D_0\{F:F(x_0)=0\}$$, $$D_1\{F:F(x_1)=0\}$$, $$D_2\{F:F(x_2)=1\}$$, $$D_3\{F:F(x_3)=1\}$$, $$D^*=D_0\bigcap D_1\bigcap D_2\bigcap D_3\neq\varnothing$$. Пусть $$Y=D$$. Построим комитет $$K=\{f_1,f_2,f_3\}\subset D$$:$$\begin{aligned} f_1=\left(-x_1+x_2-\frac12>0\right)\quad f_1\in D_0\bigcap D_1\bigcap D_2 \\ f_2=\left( x_1-x_2-\frac12>0\right)\quad f_1\in D_0\bigcap D_1\bigcap D_3 \\ f_3=\left(-x_1-x_2+\frac32>0\right)\quad f_1\in D_1\bigcap D_2\bigcap D_3 \end{aligned}$$

$$K\bigcap D_0=\{f_1,f_2\}$$, $$K\bigcap D_1=K$$, $$K\bigcap D_2=\{f_1,f_3\}$$, $$K\bigcap D_3=\{f_2,f_3\}$$. $$\left|K\bigcap D_j\right|\geq2>\frac12|K|=\frac32$$.

Следовательно, $$K$$ есть комитет в классе линейных классификаторов.

Определение. Пусть $$A,B\subset\Omega$$ (подмножества, возможно, бесконечные) и $$\widetilde{F}=\{F|F:|omega\rightarrow R\}$$ – класс функционалов. Набор функционалов $$\{F_1,F_2,\ldots,F_q\}$$ называется разделяющим комитетом для множеств $$A$$ и $$B$$, если$$\begin{aligned} \left|\{k|F_k(a)>0\}\right|>\frac12 q,\; \forall a\in A \\ \left|\{k|F_k(b)>0\}\right|>\frac12 q,\; \forall b\in A \end{aligned}$$

Утверждение. Чтобы набор $$\{F_1,F_2,\ldots,F_q\}$$ был разделяющим комитетом для $$A$$ и $$B$$ необходимо, чтобы для каждой пары $$a\in A$$ и $$b\in B$$ нашелся такой $$F_k$$, что $$F_k(a)>0$$ и $$F_k(b)<0$$.

Доказательство. Если $$n_a$$ – число функционалов $$f_k(a)>0$$, $$n_b$$ – число функционалов $$F_k(b)>0$$, то$$n_a+n_b>\frac12 q+\frac12 q=q$$ И, т.к. найдется функционал, обладающий обоими свойствами, утверждение доказано.

Теорема. Пусть $$\Omega=R^l, \; l\geq 2$$ ; $$A=\{x_1,x_2,\ldots,x_{m_1}\}$$, $$B+\{x_{m_1+1},x_{m_2+2},\ldots,x_m\},\; 0<m_1<m$$. И пусть $$x_k=0,\;\forall k=1,2,\ldots,m$$ (нет нулевой точки); $$x_i\neq x_j\alpha,\;\alpha\neq 0,\;\forall i,j,\alpha$$, (не коллинеарны). Тогда для таких $$A$$ и $$B$$ существует разделяющий комитет в классе аффинных функционалов: $$\widetilde{F}=\{F|F(x)=(W,x)+W^0,W\in R^l,W^0\in R\}$$.

Доказательство. Построим комитет из $$2m-1$$ элементов (функционалов):$$K=\{F_1,F'_1,F_2,F'_2,\ldots,F_{m-1},F'_{m-1},F_m\}$$

Для каждого функционала необходимо найти $$W_k$$ и $$W_k^)$$ в – пару, которая определяет функционал $$F_k=(W_k,x)+W_k^0$$, причем $$(x_k,W_k)=0$$, т.е. $$W_k\perp S_k$$ и $$\forall r\neq k,\;r=1,2,\ldots,m\quad (W_k,x_r)\neq 0$$, т.е. $$W_k$$ не ортогонален остальным $$x_r$$. Другими словами каждая гиперплоскость должна иметь направляющий вектор, ортогональный своему прецеденту и не ортогональный всем остальным.

Пусть $$\delta_k=\frac12\min_{r\neq k}|(W_k,x_r)|>0$$. Выберем $$W_k^0$$ следующим образом:$$\begin{aligned} W_k^0= \left\{ \begin{aligned} \phantom{-}\delta_k,\textit{ при }k=1,2,\ldots,m_1 \\ -\delta_k,\textit{ при }k=m_1+1,\ldots,m \end{aligned} \right. \\ F'_k(x)=-(W_k,x)+W_k^0 \\ F_k(x)=(W_k,x)+W_k^0 \end{aligned}$$

Покажем, что построенное множество функционалов является комитетом для $$A$$ и $$B$$. Рассмотрим$$\begin{aligned} F_k(x_k)=(W_k,x_k)+W_k^0=W_k^0= \left\{ \begin{aligned} >0,k\leq m_1 \\ <0,k>m_1 \end{aligned} \right. \\ F'_k(x_k)=-(W_k,x_k)+W_k^0=W_k^0= \left\{ \begin{aligned} >0,k\leq m_1 \\ <0,k>m_1 \end{aligned} \right. \end{aligned}$$

$$F'_k(x)$$ и $$F_k(x)$$ правильно классифицируют $$x_k$$. Посмотрим, как будет работать каждй такой функционал на остальных $$x_r$$:$$F_k(x_r)=(W_k,x_k)+W_k^0$$

Т.к. $$W_k^)<(W_k,x_k)$$, то знак $$F_k(x_r)$$ определяется знаком $$W_k,x_r$$.

Рассмотрим $$1\leq k\leq m-1$$. $$F'_k(x_k)$$ и $$F_k(x_k)$$ голосуют правильно, т.е. $$x_k$$ соответствует правильное положение гиперплоскостей. $$F'_k(x_r)$$ и $$F_k(x_r)$$ имеют разные знаки. Следовательно, каждая пара $$F'_k$$ и $$F_k$$ правильно классифицирует на всех $$x_k$$ и дает одну правильную классификацию на остальных $$x_r$$. Таким образом, количество правильно голосующих за $$x_k$$ равно $$2+(m-2)=m$$.

7.3. Комитеты линейных функционалов

Пусть $$A=\{x_1,x_2,\ldots,x_{m_1}\}$$, $$B=\{x_{m_1+1},x_m_2+2,\ldots,x_m\}$$, $$A,B\subseteq R^l$$ в – конечные множества в пространстве признаков; $$x_1,x_2,\ldots,x_m$$ – точки общего положения.

Определение. Точки $$x_1,x_2,\ldots,x_m$$ пространства $$R_l$$ называются точками общего положения, если никакая $$l+1$$ точка не лежит в гиперплоскости размерности $$l-1$$.

Приме р. Пусть $$l=2$$, т.е. рассматривается пространство $$R^2$$ (плоскость). Тогда точки $$x_1,x_2,\ldots,x_m$$ – точки общего положения, если никакие три из них не лежат на одной прямой.

Теорема. Существует разделяющий комитет аффинных функционалов, состоящий из не более, чем $$m$$ членов при нечетном $$m$$ и не более, чем $$m-1$$ при четном $$m$$.

Доказательство. Рассмотрим случай $$l=1$$, т.е. пространство $$R^1$$.

Пусть $$m=2$$, $$m_1=1$$. Тогда возможны два случая.

Для первого случая (рис. слева) функционал имеет вид:$$F(x)=x-\frac{x_1+x_2}{2}$$

Для второго случая (рис. справа) функционал имеет вид:$$F(x)=-\left(x-\frac{x_1+x_2}{2}\right)$$

$$|k|=1$$ – количество функционалов для худшего случая.

Пусть $$m=3$$, $$m_1=2$$. Тогда возможны следующие варианты.

Все случаи вида показанного на рис. слева сводятся к предыдущему $$m=2,m_1=1$$. Во всех остальных случаях функционалы надо располагать аналогично рис. справа. Для худшего случая $$|k|=3$$.

Пусть $$m=2n$$ (четное количество точек). Рассмотрим худший из возможных вариантов.

В данном случае функционалы надо располагать как показано на рис. $$|k|=m-1$$.

Пусть $$m=2n-1$$ (нечетное количество точек). Рассмотрим худший из возможных вариантов.

В данном случае функционалы надо располагать как показано на рис. $$|k|=m$$. Все остальные случаи можно свести либо к этим двум, либо к предыдущим.

Таким образом, по методу математической индукции существует разделяющий комитет аффинных функционалов из не более, чем $$m$$ членов при нечетном $$m$$ и не более, чем $$m-1$$ при четном $$m$$ в пространстве $$R^1$$.

Многомерный случай сводится к одномерному следующим образом. Ищем подпространство $$W\in R^1$$ такое, что $$(W,x_i)\neq(W,x_j)$$, при $$i\neq j$$. Проектируем все $$x_i$$ на соответствующие подпространства, пока не получим одномерную задачу. В многомерном случае для разделения $$x_i$$ и $$x_j$$ служит гиперплоскость:$$(W,x)=\frac12\left[(W,x_i)+(W,x_j)\right]$$

7.4. Функция Шеннона

Пусть $$L_n(m_1,m-m_1)$$ – это число гиперплоскостей, достаточное для разделения любых точечных множеств $$m_1$$ и $$m-m_1$$ точек общего положения в пространстве $$R^n$$.

Лемма 1. Если $$m_1\leq m-m_1$$, то$$L_n(m_1,m-m_1)\leq 2\lceil\frac{m_1}{n}\rceil$$

Доказательство. Если $$m_1\leq n$$, то добавим точки общего положения до $$n$$. Через $$n$$ точек из $$m_1$$ проводим гиперплоскость:$$F(x_1)=F(x_2)=\ldots=F(x_n)=0$$

Для $$x_k$$ такого, что $$k>n\quad F(x_k)\neq 0$$.

Выберем $$\varepsilon=\frac12\min_{n<i\leqm_1}|F(x_i)|$$ и возьмем гиперплоскости $$G_1=F+\varepsilon$$ и $$G_2=F-\varepsilon$$. $$G_1$$ и $$G_2$$ отделяют точки $$x_1,x_2,\ldots,x_n$$ от всех остальных.

Аналогичным образом из оставшихся $$(m_1-n)$$ точек выделяем еще $$n$$ и строим еще пару гиперплоскостей. Далее из оставшихся $$(m_1-2n)$$ точек выделяем еще $$n$$ и строим еще пару гиперплоскостей и т.д. В конце получим $$(m_1-mn)$$ точек. Следовательно:$$L_n(m_1,m-m_1)\leq 2\left\lceil\frac{m_1}{n}\right\rceil$$

Утверждение 1. Если $$W_1,W_2,\ldots,W_q$$ разделяют множества $$A$$ и $$B$$, и $$r(t)$$ – непрерывная кривая в $$R^l$$ такая, что $$r(0)\in A$$, а $$r(1)\in B$$, то существует $$k\in\{1,2,\ldots,q\}$$ и $$t_0\in(0,1)$$ такие, что $$(W_{k_0},r(t_0))=0$$.

Утверждение 2. Любая гиперплоскость пересекает кривую $$r(t)$$ не более, чем в $$n$$ точках.

Доказательство. Рассмотрим линейный функционал $$W$$. Запишем условие пересечения гиперплоскости и кривой $$r(t)$$:$$(W,r(t))=0.$$

Кривая $$r(t)$$ задана многочленом степени $$n$$. Следовательно, $$(W,r(t))$$ – то же многочлен степени $$n$$. Значит, уравнение $$(W,r(t))=0$$ является уравнением степени $$n$$. Следовательно, т.к. корни могут быть кратными, данное уравнение имеет не более $$n$$ корней.

Лемма 2. $$L_n(m_1,m-m_1)\geq\left\lceil\frac{2m_1-1}{n}\right\rceil$$.

Доказательство. Построим $$L_n(m_1,m-m_1)$$. Рассмотрим последовательность точек:$$0<t_1<t_2<\ldots<t_m=1$$

Пусть $$r(t)=(r_1,r_2,\ldots,r_n)$$, где $$r_i=r_i(t)=t^i$$, $$i=1,2,\ldots,n$$. Тогда $$x_j=r(t_j)=\left(t_j,t_j^2,t_j^3,\ldots,t_j^n\right)$$ – точки в $$R^n$$.

Без ограничения общности положим $$x_J\in A$$, при $$j$$ нечетном, и $$x_j\in B$$, при $$j$$ четном. Тогда получим непрерывную кривую (см. рис).

Каждая гиперплоскость дает не более, чем $$n$$ пересечений. Кривая должна иметь $$(m-1)$$ разделение, т.е. должно быть $$(m-1)$$ гиперплоскостей. Следовательно, всего гиперплоскостей должно быть не менее, чем $$\left\lceil\frac{m-1}{n}\right\rceil$$, т.е. $$L_n(m_1,m-m_1)\geq\left\lceil\frac{m-1}{n}\right\rceil$$.

Т.к.$$m_1= \left\{ \begin{gathered} \frac{m}{2},\textit{ при четном }m \\ \frac{(m-1)}{2},\textit{ при нечетном }m \end{gathered} \right. ,$$ то$$\begin{gathered} m=2m_1,\textit{ при четном }m \\ m=2m_1+1,\textit{ при нечетном }m \end{gathered}$$ .

Следовательно, $$L_n(m_1,m-m_1)\geq\left\lceil\frac{2m_1}{n}\right\rceil$$, при нечетном $$m$$, $$L_n(m_1,m-m_1)\geq\left\lceil\frac{2m_1-1}{n}\right\rceil$$, при четном $$m$$.

Окончательно получаем: $$L_n(m_1,m-m_1)\geq\left\lceil\frac{2m_1-1}{n}\right\rceil$$, $$\forall m$$.

Пример. Пусть $$m=5$$, $$m_1=2$$, $$n=2$$. Обозначим $$A=\{x_1,x_3,x_5\}$$ и $$B=\{x_2,x_4\}$$. Тогда$$\begin{aligned} L_n(m_1,m-m_1)=L_2(2,3)\geq\left\lceil\frac{2\cdot 2-1}{2}\right\rceil=2 \quad\text{и} \\ L_n(m_1,m-m_1)=L_2(2,3)\leq 2\cdot\left\lceil\frac{2}{2}\right\rceil=2 \end{aligned}$$

7.5. Метод построения комитета.

Пусть $$X$$ – множество прецедентов; $$l$$ в – размерность пространства признаков; $$m_1$$ и $$m-m_1$$ – количество прецедентов в каждом классе.

Построим $$W(x)$$ – линейный функционал такой, что, если $$W(x_k)>0$$, то объект из класса $$A\;(k=1,2,\ldots,m_1)$$, и, если $$W(x_k)<0$$, то объект из класса $$B\;(k=m_1+1,m_2+2,\ldots,m)$$. Если данный функционал правильно классифицирует меньше половины объектов, то возьмем его со знаком минус.

Итак, пусть линейный функционал $$W(x)$$ правильно классифицирует больше половины объектов. Разобьем множество прецедентов $$X$$ на множество правильно классифицированных объектов $$X_1$$ и множество неправильно классифицированных объектов $$\overline{X}_1$$, т.е. $$X=X_1\bigcup\overline{X}_1$$.

Далее строим последовательно пары функционалов $$W_s$$ и $$W'_s$$:$$W_1,W_2,W'_2,W_3,W'_3,\ldots,W_s,W'_s$$

Делаем очередной шаг. $$X=X_s\bigcup X'_s$$. Пусть на $$X_s$$ – $$(s)$$ правильно классифицированных объектов, а на $$\overline{X}_s$$ – $$(s-1)$$ правильно классифицированных объектов. Строим пару $$W_{s+1},\;W'_{s+1}$$. В $$\overline{X}_s$$ выделяем $$l$$ точек одного класса. Эти точки можно перевести в $$X_{s+1}$$, т.е. $$X_{s+1}=X_s+\{l\textit{ точек}\}$$, а $$\overline{X}_{s+1}=\overline{X}_s$$.

На каждом шаге множество неправильно классифицированных объектов уменьшается на $$l$$, следовательно, процесс сходится.

Общее число функционалов: $$1+2\cdot\left\lceil\frac{m}{2}\cdot\frac{m}{l}\right\rceil=1+\left\lceil\frac{m}{l}\right\rceil$$

Теорема. Существует комитет линейных функционалов, в котором число членов не превосходит $$\left\lceil\frac{m}{l}+1\right\rceil$$.