【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

日記

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