日記

日本語の勉強のためのブログ

【Adaboost】インスタンスの重みの更新について疑問が浮かんだ

「scikit-learn、Keras、TensorFlowによる実践機械学習」[1]を読んでいる。
この本で説明されているAdaBoostのアルゴリズムについて、数式に分からないところがあったので書く。

前提知識

Boostingとは、複数の「弱学習器」を結合して「強学習器」を作成する手法である。一般的には逐次的に予測器を訓練し、直前の予測器が間違えたデータを、間違えずに予測できるように学習することで、予測精度を高めていく[1]。
AdaBoostとは、Boostingの一種であり、直前の予測器が間違えたデータ(インスタンス)の重みを増やして学習していく手法である[1]。

アルゴリズムの数式

(以下の式はすべて[1]からの引用)

j番目の予測器の重み付き誤り率は


r_j = \frac{
    \sum_{i=1, {\hat{y}}_j^{(i)} \neq y^{(i)}}^m w^{(i)}
}{
    \sum_{i=1}^m w^{(i)}
} \tag{1}

(ここで {\hat{y}}_j^{(i)}はi番目のインスタンスに対するj番目の予測器の予測)

j番目の予測器の重みは


\alpha_j = \eta \log{\frac{1-r_j}{r_j}} \tag{2}

(ここで \etaは学習率、デフォルトで1)

インスタンスの重みは次式で更新する。


w^{(i)}_{new} = 
    \begin{cases} 
        w^{(i)} & (\hat{y}_j^{(i)} = y^{(i)}) \\
        w^{(i)}e^{\alpha_j} & (\hat{y}_j^{(i)} \neq y^{(i)}) \\
    \end{cases}
\text{for } i = 1, 2, \cdots, m \tag{3}

わからないところ

誤り率 r_jが大きい(具体的には、0.5より大きい)とき、式(2)より \alpha_jは負になる。
すると式(3)において、予測が外れているとき w^{(i)}_{new} = w^{(i)}e^{負数}となり、予測の外れたインスタンスの重みが小さくならないか?( \because 0 \lt e^{負数} \lt 1)
AdaBoostは予測の外れたインスタンス重みを大きくするのではなかったか?

予想

もしかしたら、予測器の誤り率が0.5より大きくなることはありえないから、 r_j \gt 0.5の場合は考えなくてもよいのか?
(誤り率0.5というのは乱数を使って適当に予測したときの値だった気がする)

調査

調べてみたらこの予想に言及している資料が見つかった。
例えば[2]の3ページ目では

AdaBoostの基本的考え方
(中略)
1.ランダムに推測するよりは正答率の高い(50%を超える)クラス分類器を生成

とある。また8ページ目には

WeakLearn:エラー率が0.5未満のクラス分類器を常に出力する学習アルゴリズム

とも書かれている。

確かにAdaBoostの元論文[3]を見てもそれっぽいことが書いてある。「誤り率は0.5未満」というのが前提のようだ。

Perhaps the most surprising of these applicationsis the derivation of a new algorithm for "boosting," i.e., for converting a "weak" PAC learning algorithm that performsjust slightly better than random guessing into one witharbitrarily high accuracy. ([3]より引用)

一応:誤り率が0.5より大きいとどうなるか?

[4]では

α の値が正で大きい:間違えたサンプルがあると、そのサンプルがすごく強調されるので、次はそのサンプルを間違えないように学習する
α の値が負で大きい:正解のサンプルに対して、そのサンプルが強調されるので、次はそのサンプルを間違えないように学習する

とある。AdaBoostの考え方(予測に失敗したインスタンスの重みを増やす)とは異なるものの、誤り率が0.5より大きい場合であっても、予測は改善に向かうだろうと考えられる。

参考文献/リンク

[1] Aurélien Géron. "scikit-learn、Keras、TensorFlowによる実践機械学習". 下田倫大監訳, 長尾高弘訳. 第2版, オライリー・ジャパン, 2020, p. 201-204. (ISBN 978-4-87311-928-1)
[2] https://mlab.cb.k.u-tokyo.ac.jp/~moris/lecture/upbsb/2008-ai/open-5_20_bio-datamining-morishita-classification-adaboost-kNN-naiveBayes.pdf
[3] A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting - ScienceDirect
[4] AdaBoostについて調べたのでまとめる - St_Hakky’s blog