CoBoosting - 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 {(x_ {1, i}, x_ {2, i})} _ {i = 1} ^ {n}}$, ${displaystyle {y_ {i}} _ {i = 1} ^ {m}}$

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

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

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

${displaystyle {hat {y_ {i}}} = left {{egin {array} {ll} y_ {i}, 1leq ileq m sign (g_ {3-j} ^ {t-1} ({oldsymbol {x_ {3-j, i}}})), m$

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

куда ${displaystyle Z_ {t} ^ {j} = sum _ {i = 1} ^ {n} e ^ {- {hat {y_ {i}}} g_ {j} ^ {t-1} ({oldsymbol {x_ {j, i}}})}}$

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

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

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

${displaystyle forall i: g_ {j} ^ {t} ({oldsymbol {x_ {j, i}}}) = g_ {j} ^ {t-1} ({oldsymbol {x_ {j, i}}}) + альфа _ {t} h_ {t} ^ {j} ({oldsymbol {x_ {j, i}}})}$

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

${displaystyle f ({oldsymbol {x}}) = signleft (sum _ {j = 1} ^ {2} g_ {j} ^ {T} ({oldsymbol {x_ {j}}}) ight)}$

Настройка AdaBoost

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

${displaystyle {frac {1} {m}} sum _ {i = 1} ^ {m} e ^ {left (-y_ {i} left (sum _ {t = 1} ^ {T} alpha _ {t}) h_ {t} ({oldsymbol {x_ {i}}}) ight) ight)} = 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} otin x_ {i}} D_ {t} (i) + sum _ {i: x_ {t} in x_ {i}} D_ {t} ( i) e ^ {- y_ {i} alpha _ {i} h_ {t} ({oldsymbol {x_ {i}}})}}$

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

${displaystyle W_ {0} = сумма _ {i: h_ {t} (x_ {i}) = 0} D_ {t} (i)}$

${displaystyle W _ {+} = сумма _ {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 _ {-}}} ight)}$

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

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

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

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

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

${displaystyle Z_ {CO} = sum _ {i = 1} ^ {m} e ^ {- y_ {i} g_ {1} ({oldsymbol {x_ {1, i}}})} + sum _ {i = 1} ^ {m} e ^ {- y_ {i} g_ {2} ({oldsymbol {x_ {2, i}}})} + sum _ {i = m + 1} ^ {n} e ^ {- f_ {2} ({oldsymbol {x_ {2, i}}}) g_ {1} ({oldsymbol {x_ {1, i}}})} + сумма _ {i = m + 1} ^ {n} e ^ {- f_ {1} ({oldsymbol {x_ {1, i}}}) g_ {2} ({oldsymbol {x_ {2, i}}})}}$

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

${displaystyle {hat {y_ {i}}} = left {{egin {array} {ll} y_ {i} 1leq ileq m sign (g_ {3-j} ^ {t-1} ({oldsymbol {x_ { 3-j, i}}})) m$

В котором ${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} ({oldsymbol { x_ {i}}}) + альфа _ {t} ^ {j} g_ {t} ^ {j} ({oldsymbol {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} ({oldsymbol {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} ({oldsymbol {x_ {j, i}}})}}$

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

Рекомендации

Сноски