コブースト

CoBoostは、 1999年にCollinsとSingerによって提案された半教師あり学習アルゴリズムです。^{[ 1 ]}このアルゴリズムの当初の用途は、非常に弱い学習器を使用した固有表現認識のタスクでしたが、データの特徴が冗長な場合の半教師あり学習を実行するために使用できます。 ^{[ 1 ]}

これは、共同学習とブースティングを組み合わせたものと見なすことができます。各サンプルは2つのビュー（特徴セットのサブセクション）で利用可能であり、ブースティングは、前の反復で別のビューで生成された予測ラベルを使用して、各ビューと交互に反復的に適用されます。CoBoostingは、PAC学習の意味での有効なブースティングアルゴリズムではありません。

CoBoostingは、CollinsとSingerが、半教師あり学習で分類器を訓練するために特徴の冗長性を活用する従来の試みを改善しようとした試みです。BlumとMitchellによる先駆的な研究であるCoTrainingは、少数のシード例が与えられた場合に、決定リストにルールを反復的に誘導することで分類器を学習するための強力なフレームワークであることが示されました。CoBoostingのCoTrainingに対する利点は、CoTrainingパターンを一般化して、あらゆる分類器で使用できることです。CoBoostingは、AdaBoostの概念を借用することでこの偉業を達成しています。

CoTrainとCoBoostの両方において、トレーニングおよびテストのサンプルセットは2つの特性を満たす必要があります。1つ目は、サンプルの特徴空間が2つの特徴空間（またはビュー）に分割でき、各ビューが分類に十分な表現力を持つことです。形式的には、2つの関数が存在します。${\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)}$理想的ではあるものの、この制約はノイズやその他の要因により実際には厳しすぎるため、両方のアルゴリズムは代わりに2つの関数の一致を最大化しようとします。2つ目の特性は、2つのビューが高度に相関していないことです。

入力：${\displaystyle \{(x_{1,i},x_{2,i})\}_{i=1}^{n}}$、${\displaystyle \{y_{i}\}_{i=1}^{m}}$

初期化:${\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)}$

CoBoostingはAdaBoostアルゴリズムに基づいて構築されており、AdaBoostは他の多くの学習アルゴリズムと組み合わせて使用​​できるため、CoBoostingに汎化能力を与えています。この構築は2クラス分類タスクを想定していますが、多クラス分類にも適用できます。AdaBoostフレームワークでは、弱分類器がトレーニングセットの例の分布とともに直列に生成されます。各弱分類器には重みが与えられ、最終的な強分類器は、割り当てられた重みで重み付けされた弱分類器の合計の符号として定義されます。（表記についてはAdaBoostのWikipediaページを参照してください）。AdaBoostフレームワークでは、SchapireとSingerは、トレーニング誤差が次の式で制限されることを示しました。

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

どこ${\displaystyle x_{t}}$は、現在の弱い仮説で選択された特徴量です。現在の仮説が正しいラベルまたは間違ったラベルのいずれかを選択した場合の分布の合計を表す3つの式が定義されています。分類器は、提供されたラベルが0である例に対してラベルを選択しない可能性があることに注意してください。2つのラベルは、-1または1のいずれかに選択されます。

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

したがって、トレーニング誤差は、各反復において、前の式を最小化する弱い仮説を選択することによって最小化される。

CoBoostingは、ラベル付きトレーニングセットがある場合にこのフレームワークを拡張します（例：${\displaystyle 1...m}$）とラベルなしトレーニングセット（${\displaystyle m_{1}...n}$）に加えて、以下の形式の機能の冗長性の条件も満たす。${\displaystyle x_{i}=(x_{1,i},x_{2,i})}$このアルゴリズムは、ラベル付きトレーニングセットの正しいラベルについて一致する2つの分類器をAdaBoostと同様の方法でトレーニングし、ラベルなしトレーニングセットで2つの分類器間の一致を最大化します。最終的な分類器は、2つの強力な分類器の合計の符号です。CoBoostの制限付きトレーニングエラーは、次のように拡張されます。${\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}}})}}$

どこ${\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\{{\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}}$2つに分割され、${\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の式と同一です。したがって、同じプロセスを使用して値を更新できます。${\displaystyle \alpha _{t}^{j}}$AdaBoostのように${\displaystyle {\hat {y_{i}}}}$そして${\displaystyle D_{t}^{j}}$これを交互に行うことで、${\displaystyle Z_{CO}^{1}}$そして${\displaystyle Z_{CO}^{2}}$このように${\displaystyle Z_{CO}}$貪欲法によって最小化される。