識別精度が一様でない識別子の集合による多数決

情報処理北海道シンポジウム 2014
識別精度が一様でない識別子の集合による多数決
三上絢子 ∗ 工藤峰一中村篤祥
(北大情報科学研究科)†
はじめに
1
教師あり学習は既知のデータ（トレーニングデータ）
を元に未知のデータを識別する関数, 識別子 (classifier),
を学習する問題である. 複雑な識別境界を表現できる識

1 (C が x のラベルを正しく推定した場合)
C(x) =
0 (otherwise)
別子はトレーニングデータに対して敏感で過学習を起こ
つまり, 識別子はクラスラベルを正しく識別した時
しやすく, テストデータを識別した際の性能, 汎化性能,
に”1” を, その他の場合では ”0” を出力すると考える.
が低くなる傾向にある. アンサンブル学習は複数の単純
C が x のラベルを正しく推定する確率を（平均）識別精
な識別子を組み合わせることにより精度の高い識別子を
度と呼ぶ. 識別精度が {p, p − δ, p + δ}(0 ≤ p ≤ 1, δ は
生み出す, 教師あり学習の枠組みである. 2 クラス識別の
場合, 弱識別子, すなわち識別精度が 0.5 よりもわずかに
p + δ ≤ 1 かつ 0 ≤ p − δ となるような任意の定数) で
ある三種類の識別子を考える. この三つの識別子がそれ
良い識別子を複数使うことにより, 単独の識別子による
ぞれ n 個あり, 全ての識別子は互いに独立であると仮定
ものよりも汎化性能の高い識別子が構成できることは知
する. つまり全部で 3n 個の識別子がある. この時, 一つ
られている [1, 2].
のデータ x に対し識別精度 p, p − δ, p + δ の識別子が n
アンサンブル学習における識別子の組み合わせ方法で
最も多く使われるのは多数決である. 多数決を用いた手
法の例として, ランダムサブスペース法 [3] やランダム
フォレスト [4] が挙げられる.
多数決による識別精度の改善が成功するための要件と
して,
• 個々の識別子の識別精度 p > 0.5 であること
• 識別子同士が十分に異なっている（多様である）こと
が挙げられる.
識別子同士が十分に異なっているときには, 識別子の
「多様性が高い」と言える. これまでに多様性を計る目的
個中 i 個誤る確率を, それぞれ Fp (i), Fp−δ (i), Fp+δ (i) と
し, 以下のように定義する.
( )
n
Fp (i) =
(1 − p)i (p)n−i
i
( )
n
Fp+δ (i) =
(1 − p − δ)i (p + δ)n−i
i
( )
n
Fp−δ (i) =
(1 − p + δ)i (p − δ)n−i
i
また, 高々i 個の識別子が誤る確率 Ip (i), Ip−δ (i), Ip+δ (i)
を以下のように定義する.
でペアワイズ相関や κ 係数など様々な尺度が提案されて
Ip (i) = Σij=0 Fp (j)
いる [5]. 相関が高い識別子は多様性が低く, 実際に Oh
Ip+δ (i) = Σij=0 Fp+δ (j)
は相関の高い識別子による多数決では識別精度の改善率
Ip−δ (i) = Σij=0 Fp−δ (j)
が低下することがあることを示した [6].
従来の多様性尺度を用いた性能解析は殆どの場合, 統
合するすべての識別子が同一の識別率を持つと仮定して
(1)
(2)
この時, 多数決による識別精度 Pmaj は以下のように
表せられる.
行われている. しかし, 一般には識別率の異なる識別子
を複数用いることになる. 本研究では, 識別率の異なる 3
種類の識別子が多数あるとして, 多数決としてそれらの
推測結果を統合する場合の効果を解析する.
多数決による識別精度
2
問題の定式化
2.1
特徴ベクトル x とクラスラベル y の組である入力デー
タ (x, y) があるとき, 識別子 C の出力を次のように評価
する.
Pmaj
= Σi+j+k≤⌈ 23 n⌉ [Fp (i) + Fp−δ (j) + Fp−δ (k)]
1
1
2n
= Ip (n)Σi=0
Fp−δ (i)Ip+δ ( n − i)
2
1
1
1
2n
2 n+i
+ Σi=0 Ip (n − i)Σj=0 Fp−δ (j)Fp+δ ( n + i − j)
2
3
1
n
2 n−i
+Σi= 1 n+1 Ip (n−i)Σj=0 Fp−δ (i− n+j)Fp+δ (n−j)
2
2
(3)
一例として, p = 0.51, n=20 のとき, δ を変化させたと
∗
[email protected]
†
札幌市北区北
14 条西 9 丁目北海道大学大学院情報科学研究科
きの Pmaj の値を図 1 に示す.
情報処理北海道シンポジウム 2014
このとき, 正規分布の再生性から以下に示すような正
規分布に従う.
U=
1
vX + vY + vZ
(X + Y + Z) ≃ N (p,
)
3n
3n
(6)
この分布について, δ の値が変化したときの分散の値
を図 2 に示す. 分散
vX +vY +vZ
3n
は三点 vx , vy , vz の重心
の y 軸座標値を n で割った値である. 識別子の数が 3n
で固定, つまり n が一定で δ が増加した場合, この分散
の値は減少する. 多数決では過半数の得票が正解して
いる場合に正しく識別できるので, 多数決の識別精度は
1
Pmaj = P ( 3n
(X + Y + Z) > 12 ) と表せられる. 従って
分布の平均 p が 0.5 よりわずかでも大きい場合, 分散の
Fig. 1 精度の差 δ が増加するに伴い多数決による識別
減少に伴って値が 0.5 を下回る確率が減少するため, 多
精度も向上する様子（p = 0.51, n=20）
数決の識別精度が改善する. また当然 n に反比例して分
散は減少する. 実際には正規分布の仮定に依らず, 具体
2.2
的な式変形により Pmaj < p を示すことができる.
正規分布への近似による直感的な理解
識別精度 p, p − δ, p + δ のそれぞれ n 個の識別子のう
ち正解する識別子の個数をそれぞれ X, Y, Z と表記する.
確率変数 X, Y, Z はそれぞれ二項分布に従い, 以下のよ
うに定義できる.
( )
n i
P (X = i) =
p (1 − p)n−i
i
( )
n
P (Y = i) =
(p − δ)i (1 − p + δ)n−i
i
( )
n
P (Z = i) =
(p + δ)i (1 − p − δ)n−i
i
(4)
また, X, Y, Z にそれぞれの期待値 E[X], E[Y ], E[Z] と
分散 V [X], V [Y ], V [Z] は,
V [X] = nvx = np(1 − p)
E[X] = np
E[Y ] = n(p − δ) V [Y ] = nvy = n(p − δ)(1 − p + δ)
E[Z] = n(p + δ)
V [Z] = nvz = n(p + δ)(1 − p − δ)
(5)
ここで, n が十分に大きい時, X, Y, Z の分布は正規分
布で以下のように近似できる.
Fig. 2 多数決による分散 (n = 1, p = 0.6). こ
こで, f (p) = p(1 − p) 上の三点, p(1 − p) = vx ,
(p − δ)(1 − p + δ) = vy , (p + δ)(1 − p − δ) = vz の
重心が
(vx +vy +vz )
3
の値であり, p, (p − δ), (p + δ) で多数
決を行った際の識別率の分散の n 倍である. 精度差 δ が
大きいとき分散は減少する.
3
まとめ
本論文ではアンサンブル学習において, 識別精度の異
なる識別子同士を組み合わせた場合の多数決での識別精
X ≃ N (np, nvX )
Y ≃ N (n(p − δ), nvY )
Z ≃ N (n(p + δ), nvZ )
度の効果を検討した. 具体的には, 三種類の識別子を複
数個使った場合には, それらの識別率が離れている方が
近い時よりも多数決を取る効果があることを理論的に明
らかにした.
一方で, それならば, 最も識別率の高い識別子だけを使
多数決の得票割合を U =
1
3n (X
+ Y + Z) と表す.
えばよいという議論もあるかもしれない. しかし, 識別
子の識別率をトレーニングデータから推測するのは難し
情報処理北海道シンポジウム 2014
く, それ自体, パターン認識の主要課題の一つとなってい
る. そのため実用上は, 平均識別率の正しい値は分から
ない複数の識別子を利用することになる. 本研究は, 複
数の識別子全体の平均識別率が 1/2 よりも高いことだけ
が分かっている状況で, ばらばらな識別率を持つ識別子
を複数使って多数決をとることの効果を裏付けたもので
ある. これまでは同一の平均識別率を仮定した解析が主
であったため, 本研究で行われた異なる平均識別率の仮
定下での成果は意義深い. 特に, 組み合わせに依っては,
平均識別率が 1/2 よりも低い識別子が含まれていても統
合する効果があることがわかったことが興味深い.
今回は全ての識別子が独立であると仮定したが, 実際
には正の相関を持つ場合が多い. 特に識別精度が高い識
別子の場合には相関が高くならざるを得ないため, 多数
決の精度に強い影響を与える. このような時に識別精度
の低い識別子を多数決に加えることの効果を今後検討し
たい.
参考文献
[1] L. K. Hansen and P. Salamon. Neural network ensembles. IEEE transactions on Pattern Analysis
and Machine Intelligence, Vol. 12, No. 10, pp. 993–
1001, 1990.
[2] L. Breiman. Bagging predictors. Machine Learning,
Vol. 24, No. 2, pp. 123–140, 1996.
[3] T. K. Ho. The random subspace method for constructing decision forests. Pattern Analysis and Machine Intelligence, IEEE, Vol. 20, No. 8, pp. 832–
844, 1998.
[4] L. Breiman. Random forests. Machine learning,
Vol. 45, pp. 5–32, 2001.
[5] L. I. Kuncheva and C. J. Whitaker. Measures of Diversity in Classifier Ensembles. Machine Learning,
Vol. 51, No. 2, pp. 181–207, 2003.
[6] S. B. Oh. On the relationship between majority
vote accuracy and dependency in multiple classifier
systems. Pattern Recognition Letters, Vol. 24, No.
1-3, pp. 359–363, 2003.

Download Report