CoBoosting

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

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

Мотивация [ править ]

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

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

Алгоритм [ править ]

Входные данные : ,${\ Displaystyle \ {(х_ {1, я}, х_ {2, я}) \} _ {я = 1} ^ {п}}$${\ Displaystyle \ {у_ {я} \} _ {я = 1} ^ {м}}$

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

Для и для :${\ displaystyle t = 1, ..., T}$${\displaystyle j=1,2}$

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

${\displaystyle {\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.}$

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

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

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

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

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

${\displaystyle \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}}})}$

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

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

Настройка AdaBoost [ править ]

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

${\displaystyle {\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}}$

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

${\displaystyle 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}}})}}$

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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}}})}}$

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

${\displaystyle {\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.}$

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

${\displaystyle 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}}}))}}$

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

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

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

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

Ссылки [ править ]

Сноски [ править ]