An Adaptive Version of the Boost by Majority Algorithm

Freund, Y.: An adaptive version of the boost by majority algorithm, Machine Learning, vol. 43, no. 3, pp. 293‒318, 2001.

link.springer.com

実装はこちらです．

github.com

以前ゼミで，Introduction to ensemble methods for beginners Introduction to ensemble methods for beginners

というタイトルで以下のようなアンサンブルについての概要を簡単にまとめた資料を発表しました(突貫工事なのでまとまりがないのは目を瞑っていただきたく)．

Introduction to ensemble methods for beginners

その中でも，History of Boosting節のBrownBoost*1について今回は紹介します．

BrownBoost

本論文では，AdaBoostがノイズに弱い*2という特徴を考慮したBrownBoostを提案しています．

本論文以外でも，ノイズ耐性を持つBoostingは提案されています*3．

しかし，PACの枠組みの中で定義されている正式なブースティング特性はありません．

そこで，FreundはBoosting-By-Majorityを適用することでノイズ耐性を受け継いだPACに基づいたBrownBoostを提案しました．

Boosting-By-Majority*4

Boosting-By-Majority(以下，BBM)は，Freundによって提案された最初のブースティングアルゴリズムです．

また，ノイズ耐性*5があります．

しかし，BBMを使用するためには，基本学習器の誤差限界パラメータとして与える必要があり，実用には向きません．

BBMとBrownBoostの関係

このパラメータを削除した手法がBrownBoostです．

具体的には，パラメータを削除し，候補モデルの誤差に適応的に最終的なアンサンブルを生成します．

BrownBoostでは，候補モデルの数を指定するパラメータはなく，代わりに $c$ というパラメータがあります．

このパラメータによって”残り時間”が決められます．

この”残り時間”は，BrownBoostのイテレーションに関するパラメータです．

また，候補モデルが訓練された時，”残り時間”と分類マージンに基づいてそのモデルの重みが決まります．

そして，その重みに基づいて”残り時間”は減算されます．

この分類マージンにより，BBMやBrownBoostでは各インスタンスを正解するように候補モデルを訓練することができます．

一方で，各候補モデルの正答率が低いインスタンスに対しては，負のマージンが割り当てられ，そのようなインスタンスはノイズであると判断されます．

これがBBM，BrownBoostがノイズに強い所以です．

BrownBoostのイテレーションは，”残り時間”が収束するまで続きます．

候補モデルの重み付き誤差によって決まるのでアルゴリズムの実行時間はBBMに比べて非常に長くなり得ます．

この問題に関しては，候補モデルの誤差を0.5に近づけた時のアンサンブルの振る舞いを考えることで答えることが可能です．

モデルの誤差を $(1/2 - \delta)$ とし，時間 $t$ におけるアンサンブルの出力を $\sum h(x)$ と表します．

この時，時間を $t=\delta ^2 i$ をすると，BrownBoostの収束後の時間は $\delta$ とは無関係の定数となり，これにより下式で表現される”位置”を定義します．

\begin{align} r_\delta(t) = \delta \sum^{\lceil t/\delta^2 \rceil}h(x) \end{align}

モデルの誤差を0.5に近づけることが前提であり，この時の”位置 $r_\delta(t)$ ”は下式で得られる平均 $\mu(t)$ と分散 $\sigma ^2 (t)$ によって特徴付けられるブラウン運動による連続時間確率過程 $r(t)$ に近づきます．

${ \begin{align} \mu(t) = \int_{0}^{t} \frac{1}{\gamma(s)}ds \end{align} }$

${ \begin{align} \sigma^{2}(t) = t \end{align} }$

ここで， $1/2 - \gamma(t)$ は時刻 $t$ におけるモデル $h$ の重み付き誤差を表します．

ここまでで誤差を0.5に近づけた時のアンサンブルの振る舞いがわかりました．

ここからはBBMで定義される重みの限界を考えます．

BBMの重み関数は二項分布であり，以下で表します．

\begin{align} \alpha^i_r = {}_{k_\delta - i - 1} C _{\lfloor k_\delta/2 \rfloor - 2} \biggl(\frac{1}{2} + \delta \biggr)^{\lfloor k_\delta/2 \rfloor - r} \biggl(\frac{1}{2} - \delta \biggr)^{\lfloor k_\delta/2 \rfloor - i - 1 + r} \end{align}

ここで， $k_\delta$ はイテレーションの回数で， $i$ は現在のイテレーション番号です．

$r$ はこれまでの正しい予測の数です．

前述の $r_\delta$ と $t$ の定義から誤差を0.5に近づけると $\alpha^{i}_{r}$ の限界を得ることができます．

\begin{align} \alpha(t,r) = \exp \biggl(-\frac{(r(t)+c-t)^2}{c-t} \biggr) \end{align}

ここで， $c = \lim_{\delta \to 0} \delta ^2 k_\delta$ です．

同様に，誤差限界は下式のように表せます．

\begin{align} \beta^i_r = \sum^{\lfloor k_\delta/2 \rfloor - r} {}_{k_\delta - i} C _{j} \biggl(\frac{1}{2} + \delta \biggr)^{j} \biggl(\frac{1}{2} - \delta \biggr)^{\lfloor k_\delta \rfloor - i - j} \end{align}

\begin{align} \beta(t,r) = \frac{1}{2}\biggl(1 - erf \biggl(\frac{r(t)+c-t}{\sqrt{c-t}} \biggr) \biggr) \end{align}

ここで， $erf(\cdot)$ は誤差関数であり，下式で表現されます．

\begin{align} erf(a) = \frac{2}{\pi}\int_{0}^{a} \exp(-x^2)dx \end{align}

以上のように $t$ ， $r(t)$ ， $\alpha(t,r)$ ，及び， $\beta(t,r)$ の定義が与えられると、BBM アルゴリズムを連続時間領域に変換できるようになります．

この領域では，BBMを実行する代わりに，候補モデルの誤差が0.5である分布に対応する $t$ の値を定義する微分方程式を解くことで近似解を得ることができます．

また，BrownBoostの損失関数は， $\beta(t,r)$ に対応した形になり，同様に近似によって多項式時間での収束が可能となります．

ブラウン運動のシュミレーション

ブラウン運動は，連続時間ランダムウォークをモデル化したものです．

2次元ブラウン運動のシュミレーションを行い，その結果を可視化しました．

f:id:lapis_zero09:20180330014413p:plain — 2次元ブラウン運動のシュミレーション

実装はここにあるので，遊んでみてください．

BrownBoost/brownian_motion.ipynb at master · lapis-zero09/BrownBoost · GitHub

BrownBoostの実装

BrownBoostのアルゴリズムは以下に示すとおりです．

f:id:lapis_zero09:20180330014919p:plain

アルゴリズム中ステップ3は論文に示されているとおり，Newton-Raphson法により解を導いています．

実装はこちらです．

github.com

実験

ここに簡単な実験を示しています．

BrownBoost/brownboost.ipynb at master · lapis-zero09/BrownBoost · GitHub

感想など

尻すぼみ感が否めませんが，明日も朝から研修なので許して．

後ほど追加実験をします．

*1:Freund, Y.: An adaptive version of the boost by majority algorithm, Machine Learning, vol. 43, no. 3, pp. 293‒318, 2001.

*2:Dietterich, T. G.: An experimental comparison of three methods for constructing ensembles of decision trees: Bagging, boosting, and randomization. Machine Learning, 40:2, 139–158.

*3:Friedman, J., Hastie, T., Tibshirani, R.: Additive logistic regression: a statistical view of boosting. Ann. Statist. 28 (2000), no. 2, pp. 337-407.

*4:Freund, Y.: Boosting aweaklearning algorithm by majority. Information and Computation, 121:2, 256–285.

*5:J. a. Aslam and S. E. Decatur, General bounds on statistical query learning and PAC learning with noise via hypothesis boosting, Proc. 1993 IEEE 34th Annu. Found. Comput. Sci., vol. 118, pp. 85‒118, 1993.