Совместное усиление

CoBoost — это алгоритм полуконтролируемого обучения, предложенный Коллинзом и Сингером в 1999 году. Первоначальное применение этого алгоритма заключалось в задаче классификации именованных объектов с использованием очень слабых обучающихся. Его можно использовать для выполнения полуконтролируемого обучения в случаях, когда существует избыточность функций.

Это можно рассматривать как комбинацию совместного обучения и повышения квалификации . Каждый пример доступен в двух представлениях (подразделах набора функций), а повышение применяется итеративно поочередно, при этом в каждом представлении используются прогнозируемые метки, созданные в альтернативном представлении на предыдущей итерации. CoBoosting не является допустимым алгоритмом повышения с точки зрения обучения PAC .

Мотивация

CoBoosting был попыткой Коллинза и Сингера улучшить предыдущие попытки использовать избыточность функций для обучения классификаторов полуконтролируемым способом. CoTraining, плодотворная работа Блюма и Митчелла, оказалась мощной основой для обучения классификаторов на небольшом количестве исходных примеров путем итеративного введения правил в список решений. Преимущество CoBoosting to CoTraining заключается в том, что он обобщает шаблон CoTraining, чтобы его можно было использовать с любым классификатором. CoBoosting достигает этой цели, заимствуя концепции из AdaBoost .

И в CoTrain, и в CoBoost наборы примеров обучения и тестирования должны соответствовать двум свойствам. Во-первых, пространство признаков примеров можно разделить на два пространства признаков (или представления), так что каждое представление будет достаточно выразительным для классификации. Формально существуют две функции $f_{1}(x_{1})$ и $f_{2}(x_{2})$ такой, что для всех примеров $x=(x_{1},x_{2})$, $f_{1}(x_{1})=f_{2}(x_{2})=f(x)$. Хотя это ограничение и идеально, на самом деле оно слишком сильное из-за шума и других факторов, и вместо этого оба алгоритма стремятся максимизировать согласие между двумя функциями. Второе свойство заключается в том, что эти две точки зрения не должны сильно коррелировать.

Алгоритм

Вход: $\{(x_{1,i},x_{2,i})\}_{i=1}^{n}$, $\{y_{i}\}_{i=1}^{m}$

Инициализировать: $\forall i,j:g_{j}^{0}({\boldsymbol {x_{i}}})=0$.

Для $t=1,...,T$ и для $j=1,2$:

Установите псевдометки:

${\hat {y_{i}}}=\left\{{\begin{array}{ll}y_{i},1\leq i\leq m\\sign(g_{3-j}^{t-1}({\boldsymbol {x_{3-j,i}}})),m<i\leq n\end{array}}\right.$

Установите виртуальное распространение: $D_{t}^{j}(i)={\frac {1}{Z_{t}^{j}}}e^{-{\hat {y_{i}}}g_{j}^{t-1}({\boldsymbol {x_{j,i}}})}$

где $Z_{t}^{j}=\sum _{i=1}^{n}e^{-{\hat {y_{i}}}g_{j}^{t-1}({\boldsymbol {x_{j,i}}})}$

Найдите слабую гипотезу $h_{t}^{j}$ это минимизирует расширенную ошибку обучения.

Выберите значение для $\alpha _{t}$ это минимизирует расширенную ошибку обучения.

Обновите значение текущего сильного беспорогового классификатора:

$\forall i:g_{j}^{t}({\boldsymbol {x_{j,i}}})=g_{j}^{t-1}({\boldsymbol {x_{j,i}}})+\alpha _{t}h_{t}^{j}({\boldsymbol {x_{j,i}}})$

Окончательный результат сильного классификатора:

$f({\boldsymbol {x}})=sign\left(\sum _{j=1}^{2}g_{j}^{T}({\boldsymbol {x_{j}}})\right)$

Настройка АдаБуста

CoBoosting основан на алгоритме AdaBoost , который дает CoBoosting возможность обобщения, поскольку AdaBoost можно использовать в сочетании со многими другими алгоритмами обучения. Это построение предполагает задачу классификации двух классов, хотя ее можно адаптировать для классификации нескольких классов. В среде AdaBoost слабые классификаторы генерируются последовательно, а также распределяются по примерам в обучающем наборе. Каждому слабому классификатору присваивается вес, а окончательный сильный классификатор определяется как знак суммы слабых классификаторов, взвешенных по присвоенному им весу. (Обозначения см. на странице AdaBoost в Википедии). В рамках AdaBoost Шапир и Сингер показали, что ошибка обучения ограничена следующим уравнением:

${\frac {1}{m}}\sum _{i=1}^{m}e^{\left(-y_{i}\left(\sum _{t=1}^{T}\alpha _{t}h_{t}({\boldsymbol {x_{i}}})\right)\right)}=\prod _{t}Z_{t}$

Где $Z_{t}$ – нормирующий коэффициент для распределения $D_{t+1}$. Решение для $Z_{t}$ в уравнении для $D_{t}(i)$ мы получаем:

$Z_{t}=\sum _{i:x_{t}\notin x_{i}}D_{t}(i)+\sum _{i:x_{t}\in x_{i}}D_{t}(i)e^{-y_{i}\alpha _{i}h_{t}({\boldsymbol {x_{i}}})}$

Где $x_{t}$ — это признак, выбранный в текущей слабой гипотезе. Определены три уравнения, описывающие сумму распределений, для которых текущая гипотеза выбрала правильную или неправильную метку. Обратите внимание, что классификатор может воздержаться от выбора метки для примера, в котором предоставленная метка равна 0. Две метки выбираются со значениями -1 или 1.

$W_{0}=\sum _{i:h_{t}(x_{i})=0}D_{t}(i)$

$W_{+}=\sum _{i:h_{t}(x_{i})=y_{i}}D_{t}(i)$

$W_{-}=\sum _{i:h_{t}(x_{i})=-y_{i}}D_{t}(i)$

Шапире и Зингер показали, что ценность $Z_{t}$ можно минимизировать (и, следовательно, ошибку обучения), выбрав $\alpha _{t}$ быть следующим:

$\alpha _{t}={\frac {1}{2}}\ln \left({\frac {W_{+}}{W_{-}}}\right)$

Предоставление доверительных значений для текущего гипотетического классификатора на основе количества правильно классифицированных и неправильно классифицированных примеров, взвешенных по распределению по примерам. Это уравнение можно сгладить, чтобы компенсировать случаи, когда $W_{-}$ слишком мал. Получение $Z_{t}$ из этого уравнения получаем:

$Z_{t}=W_{0}+2{\sqrt {W_{+}W_{-}}}$

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

AdaBoost с двумя представлениями

CoBoosting расширяет эту структуру в случае, когда у вас есть помеченный обучающий набор (примеры из $1...m$) и немаркированный обучающий набор (из $m_{1}...n$), а также удовлетворять условиям избыточности признаков в виде $x_{i}=(x_{1,i},x_{2,i})$. Алгоритм обучает два классификатора так же, как AdaBoost , который согласовывает правильные метки помеченных обучающих наборов и максимизирует согласие между двумя классификаторами в неразмеченном обучающем наборе. Последний классификатор является знаком суммы двух сильных классификаторов. Ограниченная ошибка обучения в CoBoost расширяется следующим образом: $Z_{CO}$ является продолжением $Z_{t}$:

$Z_{CO}=\sum _{i=1}^{m}e^{-y_{i}g_{1}({\boldsymbol {x_{1,i}}})}+\sum _{i=1}^{m}e^{-y_{i}g_{2}({\boldsymbol {x_{2,i}}})}+\sum _{i=m+1}^{n}e^{-f_{2}({\boldsymbol {x_{2,i}}})g_{1}({\boldsymbol {x_{1,i}}})}+\sum _{i=m+1}^{n}e^{-f_{1}({\boldsymbol {x_{1,i}}})g_{2}({\boldsymbol {x_{2,i}}})}$

Где $g_{j}$ представляет собой суммирование весов гипотез по их доверительным значениям для $j^{th}$ вид (j = 1 или 2). $f_{j}$ является признаком $g_{j}$. На каждой итерации CoBoost оба классификатора обновляются итеративно. Если $g_{j}^{t-1}$ это сильный выход классификатора для $j^{th}$ посмотреть до $t-1$ итерации мы можем установить псевдометки для j -го обновления:

${\hat {y_{i}}}=\left\{{\begin{array}{ll}y_{i}1\leq i\leq m\\sign(g_{3-j}^{t-1}({\boldsymbol {x_{3-j,i}}}))m<i\leq n\end{array}}\right.$

В котором $3-j$ выбирает другое представление вместо обновляемого в данный момент. $Z_{CO}$ разбивается на две так, что $Z_{CO}=Z_{CO}^{1}+Z_{CO}^{2}$. Где

$Z_{CO}^{j}=\sum _{i=1}^{n}e^{-{\hat {y_{i}}}(g_{j}^{t-1}({\boldsymbol {x_{i}}})+\alpha _{t}^{j}g_{t}^{j}({\boldsymbol {x_{j,i}}}))}$

Распределение по примерам для каждого просмотра $j$ на итерации $t$ определяется следующим образом:

$D_{t}^{j}(i)={\frac {1}{Z_{t}^{j}}}e^{-{\hat {y_{i}}}g_{j}^{t-1}({\boldsymbol {x_{j,i}}})}$

В какой момент $Z_{CO}^{j}$ можно переписать как

$Z_{CO}^{j}=\sum _{i=1}^{n}D_{t}^{j}e^{-{\hat {y_{i}}}\alpha _{t}^{j}g_{t}^{j}({\boldsymbol {x_{j,i}}})}$

Это идентично уравнению в AdaBoost. Таким образом, тот же процесс можно использовать для обновления значений $\alpha _{t}^{j}$ как в AdaBoost, используя ${\hat {y_{i}}}$ и $D_{t}^{j}$. Чередуя это, минимизируем $Z_{CO}^{1}$ и $Z_{CO}^{2}$ таким образом $Z_{CO}$ минимизируется жадным образом.