アンサンブル法による機械学習 -基礎とアルゴリズム 読書メモ
アンサンブル法による機械学習 -基礎とアルゴリズムより
アンサンブル学習法は，深層学習に続く次のトレンドとして注目されている。ブースティングやバギングなどの代表的な方法で複数の学習器を訓練し，それらを組み合わせて利用するという，最先端の機械学習法である。単一の学習法に比べてはるかに精度の高いことが知られており，実際に多くの場面で成功を収めている。
本書は，機械学習の分野で世界をリードしているZhi-Hua Zhou著の邦訳である。１章はアンサンブル法の背景となる知識をあつかう。2章から5章は，アンサンブル法の核となる知識をあつかう。5章では最近の情報理論多様性と多様性生成について議論する。6章からは，高度なアンサンブル法について述べる。人工知能，機械学習にたずさわる，研究者，技術者，学生には，必読必携の書である。
1. はじめに
1.1 基本概念
機械学習、パターン認識、データマイニングの主要な目的は、データセットから良いモデルを作ること
データセットは一般的に複数の特徴ベクトル(feature vectors)からなる
標本(sample)と呼ばれることもある
各特徴ベクトル
特徴(feature)の集合からなるオブジェクトの表現
インスタンス(instance)と呼ばれることもある
データセットの特徴数
次元(dimension)もしくは次元数(dimensionality)と呼ばれる
特徴
属性(attribute)と呼ばれることもある
データからモデルを生成する過程
学習(learning)もしくは訓練(training)と呼ばれる
学習アルゴリズム(learning algorithm)によって行われる
学習されたモデル
仮説(hypothesis)と呼ばれる
または学習器(learner)
学習状況
教師あり学習(supervised learning)
教師なし学習(unsupervised learning)
まだ観測されていないインスタンスに対する目標特徴の値を予測
学習されたモデルは予測器(predictor)
ラベルは必要としない
データ固有の分布情報を見つけることが目的
クラスタリング(clustering)
ラベルがカテゴリカル(質的)である場合
クラス分類(classification)
学習器
分類器(classifier)
ラベルが数値(量的)である場合は
回帰(regression)
学習器
当てはめた回帰モデル(fitted regression model)
ラベルが既知のインスタンス
事例(example)
二値分類
正(positive)と負(negative)の2つのラベルで分類
学習の基本的な目的
一般化(generalization)
訓練データから学習された「知識」を観測されていないインスタンスに対して一般化する
良い学習器
小さな一般化誤差(generalization error)
グランドトルース(proud-truth)なラベル情報の知識を必要とする
一般化誤差の推定値としてテスト誤差(test error)を用いる
小さな予測誤差(prediction error)
1.2 よく用いられる学習アルゴリズム
1.2.1 線形判別分析(linear classifier)
重みベクトル(weight vector)とバイアス(bias)からなる
y(予測ラベル) = sign(w(重みベクトル)T*x(インスタンス) + b(バイアス))
古典的な整形学習アルゴリズム
フィッシャーの線形判別分析 (Linear Discriminant Analysis, LDA)
異なるクラスのインスタンスはより遠くにあり 同じクラスのインスタンスはより近くにある
異なるクラスの中心間の距離を大きくする
各クラス内の分散を抑える
LDAは J(w) = SB(w)(クラス間の距離) / SW(w)(クラス内分散)を最小にする
1.2.2 決定木(decision tree)
木構造の決定テストの集合
分割統治(divide-and-conquer)法として機能する
葉でないノード(non-leaf-node)には、分割(split)と呼ばれる「特徴テスト」が与えられる
ノードに与えられたデータは特徴テストに対する異なる値に従い、異なる部分集合へ分割される
葉ノード(leaf node)にはラベルがつけられている
インスタンスに対して割り当てられる
ルートノードから始まる一連の特徴テストが行われ、葉ノードに達した時に結果が得られる
学習アルゴリズム
再帰的な過程
ID3アルゴリズム
分割の選択のため情報獲得量(information gain)基準が用いられる
訓練集合Dのエントロピー(entropy)は
Dが部分集合D1..Dkに分割避けるとエントロピーが減少し、その減少量が情報各地区領となる
課題
分類との関連性にも関わらず取りうる値が多い特徴量が選ばれる系恋にある
カテゴリカル特徴のみ扱うことができる
C4.5アルゴリズム
獲得比(gain ratio)を用いて選択
特徴量の数で正規化(normalization)した情報獲得量基準を変形したもの
数値特徴も扱える
CART(Classification and Regression Tree)アルゴリズム
Gini係数(Gini index)を用いて選択
数値特徴も扱える
過剰適合(過学習)(overfitting)
訓練集合に対してい性能が良いが一般化性能が落ちる
ノイズを正解として対応してしまう
枝刈り(pruning)
ノイズが原因の木を切り親とす
事前枝刈り(pre-pruning)
木が成長している時に枝刈りを行う
事後枝刈り(post-pruning)
完全に成長した木に対して再精査を行って枝刈りを行う
決定木の高さが1の場合
決定株(decision stump)
線形分類器
1.2.3 ニューラルネットワーク(artificial neural network)
ニューロンはユニット(unit)とも呼ばれる
一般的なニューロンモデル
M-Pモデル(McCulloch-Pitts Model)
入力信号とそれに対するコネクション重み(connection weight)
信号の総和とニューロンのバイアス(bias)と呼ばれる閾値が比較される
信号の総和が閾値より大きい場合はニューロンは活性化し、 出力信号が伝達関数(transfer function)もしくは スクアッシング(squashing function)と呼ばれる活性化関数(activation function)により生成される
多層フィードフォワードネットワーク (multi-layer feed-forward network)
隠れ層(hidden layer)を持つ
活性化関数はシグモイ関数 (sigmoid function)
訓練の目的はコネクション重みとニューロンのバイアスを決定すること
活性化関数が微分可能であればニューラルネットワーク全体が微分可能な関数となり、 勾配降下(gradient descent)法により最適化可能となる
もとも成功したアルゴリズム
誤差逆伝播法 (Back-Propagation BP)
入力から隠れ層、出力と前向きに処理
誤差が計算される
逆伝搬してコネクション重みとバイアスを最適化
1.2.4 ナイーブベイズ分類器
テキストインスタンスを分類する手法として利用
最大事後確率(Maximum a Posterior:MAP)規則
実測データに基づいて未知量の点推定を行う
統計パラメータ自体も確率変数(手元にあるデータからパラメータが確率的に決まる)
手元にデータがあろうがなかろうが、「データはきっとこうなっているだろう」(主観) と考えられる場合には、それを確率分布に反映することができる
データと主観から確率的にパラメータを推定する
主観の中に経験則とか統計的裏付けがあっても良い
最尤法
「統計パラメータは正しいものが唯一存在する」仮定の世界
尤度
確率分布からデータが実際に生起した際の確率
尤度を最大にするもの
1.2.5 k-最近傍法
入力空間内で近いオブジェクトは祝力空間内でも近い
怠惰学習(lazy learning)アプローチ
明確な訓練課程を持たない代わりに単純に訓練用集合を蓄えるだけ
1.2.6 サポートベクタマシンとカーネル法
ラージマージン分類器 (large margin classifiers)
異なるクラスのインスタンスを最大マージンの超平面を持つように分割する
マージン(margin)
異なるクラスのインスタンスから分類超平面への最小距離
ヒンジ損失(hing loss)
データへの適用評価で用いる
非線形の分類ではクラスを十分に分類することができない
データ点をより高次の特徴空間へ写像し、元の特徴空間では線形的に分離することができないデータを線形に分離数
通常は内積が難しいのをカーネル関数を使うことで内積が容易になるようにしている
1.3. 評価と比較
1.4. アンサンブル法
初期に貢献した3つの道筋
分類器の結合 (combining classifiers)
パターン認識の分野で多く研究された
弱学習器のアンサンブル (enembles of weak learners)
Adaboost
Bagging)
機械学習の分野で多く研究された
エキスパートの混合 (mixture of experts)
ニュラルネットワークの分野で最も多く研究される
分割統治法(divide-and-conquer)
パラメトリッシモデルの混合
構築の2つのステップ
基本学習器の生成
正確(accurate)かつ多様(diverse)であるべき
学習器の統合
ノーフリーランチ定理 (No Free Lunch Theorem)
ある学習アルゴリズムが一貫して他の学習アルゴリズムより すぐれているという理想的状態は存在しない
1.5 アンサンブル法の適用
1.6 参照すべき文献
2. ブースティング
2.1 一般的なブースティング法
ブースティングは、弱学習器を 強学習器へと導くことができるアルゴリズムの集まり
与えられた任意のデータ分布上において、ある学習器を実行する
プロセス
空間X1,X2,X3(1/3の分布を持つ)
空間X1とX2では正確に分類を行えるが、X3では誤った分類を行う分類器h1を得る
h1が誤ったところに注目して、空間X1とX3では正確に分類を行えるが、X2では誤った分類を行う分類器h2を得る
h2が誤ったところに注目して、空間X2とX3では正確に分類を行えるが、X1では誤った分類を行う分類器h3を得る
h1,h2,h3を結合する
2.2 AdaBoost(アダブースト)アルゴリズム
指数損失(expotential loss)関数の最小化で達成
弱学習器の弱結合器の重み付け下方結合 (additive weighted combination)を用いる
再重み付け(re-weighting)により行われる
再重み付けができないサンプルは「再標本抽出(re-sampling)」
サニティチェックを通過することができな買った基本学習器を取り除き、新たなデータ標本を生成
サニティチェック(sanity check)
現在の基本学習がランダムより良いことをチェック
弱学習器が少ないとサニティチェックを満たすものがなくなり早期終了しやすい
多クラス問題でよく起きる
2.3 実例
2.4 理論的問題
2.4.1 初期分析
2.4.2 マージンの解釈
2.4.2 統計的視点
2.5 多クラスへの拡張
2.6 ノイズ耐性
2.7 参照すべき文献
3. バギング
3.1 アンサンブルの2つの枠組み
どのように基本学習器が生成されるかによって アンサンブル法には2つの枠組みが存在する
逐次アンサンブル法 (sequential ensemble method)
基本学習器が逐次生成される
AdaBosst等
基本学習器の従属性(dependence)を考慮する
全体の性能は残差の減少(residual-decreasing)により強化
並列アンサンブル法 (parallel ensemble method)
基本学習器が同時に生成される
バギング等
基本学習器の独立性(dependence)を考慮
ランダム性を取り入れることで従属性が少ない学習器を得る
誤差は独立な基本学習器を結合することにより劇的に減少させる
3.2 Bagging(バギング)アルゴリズム
重要な要素
ブートストラップ(bootstrap)
集約(aggregation)
異なる基本学習器を生成するのに、ブートストラップ分布を用いる
基本学習器を訓練するためのデータのサブセットを得るために、 ブートストラップ標本(bootstrap sampling)を利用する
m個の事例を含む訓練データセットが与えられる
そこからm個の訓練用事例が復元抽出によって生成される
元のデータ内のいくつかの例は1回以上その標本に含まれる一方で、 いくつかの事例は含まれない
この処理をT回以上繰り返す
m個の訓練事例を含むT個の標本が得られる
各標本から基本学習器を訓練する
基本学習器の出力を集約する方法
分類
投票(voting)
回帰
平均化(averaging)
分類での例
テストインスタンスを各分類器に入れて全ての出力を集める
ラベルごとに投票を取り、最も多かったラベルを予測とする
out-of-bag
xに対するout-of-bag予測
xが含まれていない標本を基いて訓練された学習器による予測
事例
決定木への適用
各木の各ノードにおける事後確率の推定
3.3 実例
3.4 理論的問題
3.5 ランダム木のアンサンブル
3.5.1 ランダムフォレスト(Random Forest)
ランダムフォレストは最先端のアンサンブル法の代表的なもの
Baggingの拡張の一つ
Baggingとの主な違いはランダムな特徴抽出を組み込んである点
決定木の構成要素である分割選択の各ステップにおいて、 初めに特徴の部分集合をランダムに選択し、 その選択された特徴の部分集合に対して通常の分割の選択をする
アルゴリズム
パラメータKは組み込むランダム性を制御
Kについて提案される数は特徴数の対数をとった数
ランダムは特徴選択のみで導入され、選択された特徴に対する分割には導入されていない
3.5.2 ランダム化のスペクトル
RFは各ノードにおいてランダムに特徴の部分集合を選択することによりランダム決定木を生成する
選択された特徴の部分集合内における分割店の選択は決定論的なまま
VR-Treeアンサンブル
特徴選択と分割選択の両方でランダム性を加えたもの
木の各ノードにおいて確率αで表(head)が出るコインが投げられる
もく表なら決定論的なノードが構築される
伝統的な決定木と同様に全ての可能な分割点の中で最適な分割点が選択される
表でない場合はランダムなノード、すなわちランダムに一つの特徴点が選択され、その特徴に対してランダムな分割が選択される
アルゴリズム
パラメータαはランダム性を制御する
スペクトルを見ることで最適値を探せる
3.5.3 密度推定におけるランダム木のアンサンブル
ランダム木のアンサンブルは密度推定(density estimation)に用いることができる
密度推定は教師なし学習の問題
訓練用インスタンスのラベル情報が存在しない
完全なランダム(completely random)木が使用される
インスタンスが同じクラスに属するか調べるのではなく 代わりに葉ノードに含まれるインスタンスが一つ もしくは区別不能なインスタンスになるまで木を成長させる
ランダム木のアンサンブルによる密度推定
高次元データやより複雑なデータ分析に応用
オンライン学習やストリーミングデータといったアンサンブルが増加して構築されていく問題にも適用可能
データ間の平均密度で完全なランダム木の分布を推定できる
3.5.4 異常値の検出におけるランダム木のアンサンブル
異常値(anomality)
多くのデータが一般的に予測される振る舞いに従わないデータ点
異常値と外れ値(outlier)は同じ意味で用いられる
確立された手法
分離性が良い指標になる
より少ない分割で用意に分離される
iForest法
各ランダム木におけるデータ点を分離するために必要な分割数
ルートノードからそのデータ点が含まれる葉ノードまでの経路長によって測ることができる
経路長が短いものが分割しやすい
SCiForest法
傾斜型決定木(oblique decision trees)と同じように滑らかな決定境界を得ることを目標としている
超平面を用いたランダムフォレスト
複雑になる
3.6 参照すべき文献
4. 結合法
4.1 結合法による利点
アンサンブル法は結合法(combination method)が重要な役割を示す
結合法の利点
統計的観点
限られた訓練データで調べるには仮説空間が広すぎて、 同様な正確さを与える試掘かの異なった仮説が存在する場合が多々ある
仮説を結合することで間違った仮説を選択するリスクを減らせる
計算的観点
局所的な探索と局所的な最適解を選択するリスクを低減する
表現的観点
真の道の仮説は仮説空間内の任意の仮説では表現できないことがある
仮説を結合することで表現可能な関数の空間を広げることができる
4.2 平均化(averaging)
数値出力に対して最もよく用いられる基本的な結合方法
T個の学習器の集合{h1,..,ht}が与えられ、インスタンスxに対するHiの出力がhi(x)
4.2.1 単純平均化(simple averaging)
個々の学習器の出力を直接平均化することにより結合された出力を得る
4.2.2 重み付け平均化(weighted averaging)
異なる重要度を表す重みを持った個々の学習器の出力ほ平均化する
4.3 投票(voting)
名義出力に対して最もよく用いられている基本的な結合方法
T個の分類器{h1,…,ht)の集合が与えられ、l個の可能なクラスラベル{c1,…,cl}の集合からそのクラスのラベルを予測すること
非正規化マージンを構築する分類器
SVM等
キャリブレーション(calibration)法を用いることで出力ほ確率に変換可能
Plattスケーリング(plat scaling)
単調回帰(isotonic regression)
4.3.1 多数決
4.3.2 相対多数決
4.3.3 重み付け投票
4.3.4 ソフト投票
4.3.5 理論的問題
4.4 学習による結合
4.4.1 スタッキング
4.4.2 無限アンサンブル
4.5 他の結合法
4.5.1 代数的手法
4.5.2 行動知識空間法
4.5.3 決定テンプレート法
4.6 関連する手法
4.6.1 誤差修正出力コード
4.6.2 動的分類器選択
4.6.3 エキスパート混合
4.7 参照すべき文献
5. 多様性
5.1 アンサンブルの多様性
5.2 誤差分解
5.2.1 誤差曖昧性分解
5.2.2 バイアス-分散-共分散分解
5.3 多様性の尺度
5.3.1 ペアワイズ尺度
5.3.2 非ペアワイズ尺度
5.3.3 要約と視覚化
5.3.4 多様性尺度の限界
5.4 情報論的多様性
5.4.1 情報理論とアンサンブル
5.4.2 相互作用の情報量の多様性
5.4.3 多重情報量の多様性
5.4.4 推定量
5.5 多様性の生成
5.6 参照すべき文献
6. アンサンブル枝刈り
6.1 アンサンブル枝刈りとは何か
6.2 多くのほうが全てよりもよくなる
6.3 枝刈り法の分類
6.4 順序付けに基づく枝刈り
6.5 クラスタリングに基づく枝刈り
6.6 最適化に基づく枝刈り
6.6.1 発見的最適化枝刈り
6.6.2 数理計画法枝刈り
6.6.3 確率的枝刈り
6.7 参照すべき文献
7. クラスタリングアンサンブル
7.1. クラスタリング
7.1.1 クラスタリング法
7.1.2 クラスタリング評価
7.1.3 なぜクラスタリングアンサンブルか
7.2 クラスタリングアンサンブル法の分類
7.3 類似性に基づく手法
7.4 グラフに基づく手法
7.5. 祭ラベルに基づく手法
7.6 変換に基づく手法
7.7 参照すべき文献
8. さらなる話題
8.1 半教師あり学習
8.1.1 ラベルなしデータの利便性
8.1.2 アンサンブルによる半教師あり学習
8.2 アクティプラーニング
8.2.1 人の介入の利便性
8.2.2 アンサンブルを用いたアクティブラーニング
8.3 コスト考慮型学習
8.3.1 不均一コストの学習
8.3.2 コスト考慮型学習におけるアンサンブル
8.4 クラス不均衡学習
8.4.1 クラス不均衡における学習
8.4.2 クラス不均衡における性能評価
8.4.3 クラス不均衡学習に対するアンサンブル法
8.5 理解性の改良
8.5.1 アンサンブルの単一モデルへの縮小
8.5.2 アンサンブルからのルール抽出
8.5.3 アンサンブルの視覚化
8.6 アンサンブルの今後
8.7 参照すべき文献
コメント