DEIM Forum 2019 P2-126

多数決に有効な識別子の構成法
前川広樹†

中村篤祥††

工藤 峰一††† 北海道大学工学部情報エレクトロニクス学科 札幌市北区北 14 条西 9 丁目†† 北海道大学大学院情報科学研究科 札幌市北区北 14 条西 9 丁目
E-mail: †maemitsu@ist.hokudai.ac.jp, ††{atsu,mine}@ist.hokudai.ac.jp
あらまし

ラベル付きの訓練データを用いて未知のデータのラベルを推定する識別子を構築する分類問題において，複数の識別子による識別結果を統合することでより高性能な識別子を構成するアンサンブル学習という方法が知られている．アンサンブル学習は複数の識別結果を多数決によって統合するが，全体の識別結果として最も多い識別結果を採用する単純多数決と，それぞれの識別結果に対して重みをつけた上で最大の値となるラベルを採用する重み付き多数決の 2 つの方法が用いられる．本論文では，最終的な識別結果の統合が単純多数決で行われることを前提とした場合の効果的な投票者の構成方法について検討し，高性能な識別子を構成する新たなアンサンブル手法を提案する．
キーワード

機械学習, アンサンブル学習, ブースティング, バギング, 単純多数決, 多様性には，その結合からは性能の向上は得られず，仮説間が独立で1 はじめにアンサンブル学習とは，精度の低い仮説 (弱仮説) を組み合わせることで精度の高い仮説 (強仮説) を構成する学習の枠組みである．ラベル付きの訓練データを用いて未知のデータのラベルを推定する識別子を構築する分類問題において，アンサンある場合に最大の誤差減少が期待できるという分析がある [1]．
ただし，仮説の多様性については現在統一的な尺度はなく，この指標が誤差減少に確実に寄与するものではないことに注意されたい．

1. 2 本論文の構成

ブル学習は高性能・高信頼度の識別子を構成するために用いら

本論文は本章を含め, 5 章で構成する. 第 2 章では代表的なれている．分類問題のアンサンブル学習では，弱仮説を統合すアンサンブル学習の枠組みと，効果的な識別子を構成するためる方法として，重み付き多数決と単純多数決がある．特徴空間のアンサンブル手法についての関連研究を挙げる. 第 3 章では，X のデータ点に対応するラベルが {−1, 1} である 2 クラスの分本研究が扱う問題を定式化し，単純多数決によるアンサンブル類問題について考えると，重み付き多数決では L 個の弱仮説識別子を構成する新たな手法を提案する．第 4 章では提案手法

hl : X → {−1, 1}, l = 1, . . . , L による強仮説 H は仮説の重みと既存手法を比較した実験の結果を示し，その考察を行う．最αl を用いて次の式で表される.
(∑)
L
H = sign
l=1 αl hl

後に第 5 章では，本論文の結論と今後の研究について述べる．

2 関連研究この式において，仮説の重み αl がすべて 1 である場合に単純多数決となる．

1. 1 本論文の目的
本論文では，仮説の統合が単純多数決で行われる場合の効果的な投票者の構成方法を検討する．ここでは，以下の基準で多数決アンサンブルの性能を考え，優位性のあるアルゴリズムを提案する．

•汎化性能が高い•

仮説の多様性が高い•

並列化が容易である

これらの基準について，未知のデータのラベルを正確に推定するための汎化性能の高さと，複数回の学習をより高速に行うために並列化が容易であることを考えるべきであるのは明らかである．仮説の多様性の高さがアンサンブル性能を考える指標となるのは，直感的には，複数の仮説を統合する際に同一の仮説を結合した際には性能の改善はないということから分かる．
実際にアンサンブルの各仮説間において完全に相関がある場合

2. 1 アンサンブル学習の代表的な枠組み
アンサンブル学習において, 与えられた訓練データから複数の仮説を生成する代表的な枠組みとして Bagging, Boosting,Random Subspace の 3 つがある. それぞれの枠組みの概要を以下で説明する.

2. 1. 1 Bagging
Bagging [2] は与えられた訓練データからランダムに再抽出したデータを用いて 1 つの弱仮説を学習する. 再抽出したデータに対してそれぞれ独立に学習を行うため, 並列に処理が可能である. 一般的には, 仮説の統合は単純多数決により行われる.

2. 1. 2 Boosting
Boosting [3] は直前に学習された仮説の誤りを訂正する仮説を学習するために, 訓練データの分布を逐次更新する手法である. 代表的なブースティング手法である AdaBoost [4] 分布の更新は, 直前に学習した仮説による現在の分布に対する誤識別率を算出し, 誤ったデータに対して誤識別率に応じて単調に減少する値の重みをつける方法で行う. このとき, 仮説による予Boosting by Majority [10] がある. しかし, この手法では学習測が正解であったサンプルは重みが減少し, 誤りであったサンされうる仮説すべての正解率が学習した分布に対して 12 + γ 以

プルは重みが増加する. つまり, 誤識別率が小さい仮説が誤っ上となるようにパラメータ γ を設定する必要があり, 実際の利たデータほど, 次回以降の学習において重要視される. また，各用においては現実的でない. 実際の利用に適した単純多数決

ステップにおいて仮説の誤識別率を算出することで, その性能ブースティング手法として, Vote-boosting [11] がある. この手の高低に基づいた重み付き多数決により, 仮説の統合が行われ法では, 現在までに学習した仮説の投票数が同数に近いデータる. 1 回の学習が直前に学習した仮説に依存するため，並列にに対して大きな重みを付けることで分布を更新する. 本研究に処理することは困難である．

おいては Boosting の枠組みとして，この Vote-boosting のア

2. 1. 3 Random Subspace

ルゴリズムを用いる．アルゴリズムの詳細については，後述す

Random Subspace [5] は与えられた訓練データの属性 (特徴)る第 3.2 節において述べる．

をランダムに選択し, その特徴のみを用いて弱仮説を学習する方法である. 一般的には, 単純多数決により仮説を統合する. ランダムに行われる特徴選択はそれぞれ独立に行うことが可能なため，並列に処理が可能である．

3 提案手法3. 1 問 題 設 定
2 クラスのラベル付きの N 個の訓練サンプル S =2. 2 アンサンブル手法
これらの枠組みを組み合わせて, 高性能な仮説アンサンブルを作る試みは数多く存在する. Bagging と Boosting を混合{(xi , yi )}N
i=1 , (xi , yi ) ∈ X × {−1, +1} が与えられた時に, 未知の入力 x ∈ X のクラスを推定する仮説 H(x) : X → {−1, +1}を学習する問題を考える.

したアンサンブル手法には MultiBoosting [6] と Parallelized

アンサンブル学習において最終的に出力される仮説 H(x)Boosting [7] の大きく 2 つの枠組みがある. MultiBooting は，を強仮説といい, この強仮説は複数の弱仮説 h1 , h2 , . . . , hL

bagging の枠組みによって複数の初期分布を生成し，それぞれ(hl : X → {−1, +1}) を統合することで得られる. このとき, 弱に対して独立に Boosting による逐次的な学習を行う手法であ仮説 hl は正解率が 1/2 を超える, つまりランダムにラベル付す

り，Parallelized Boosting は，Boosting の逐次的な学習の各スるよりは正解率の高いものを学習する.

テップにおいて，Bagging の枠組みを用いて複数の仮説を生成

本論文では, 以降サンプル数 N の訓練データを S, 強仮説する．これらの手法では，Boosting の枠組みによる学習が行

H(x) に含まれる弱仮説 hl の個数を L として議論を行う. 強仮われるため，最終的な仮説の統合には重み付き多数決が用いら

説 H(x) の出力は以下のように, L 個の弱仮説の単純多数決にれる．

よって決定される.

Boosting と Random Subspace を組み合わせた手法は Boosting Random Subspace Method [8] がある．この手法では各Boosting ステップの訓練データの分布において，特徴をランダムに選択し学習を行う手法である．各ステップの学習は Boost-ing によって行われるため，仮説は重み付き多数決によって統合される．

Bagging と Random Subspace を組み合わせた手法には，代表的な Random Forest [9] がある．これは決定木による Bag-ging を行う手法で各サンプリングの際に特徴も同時にランダムに選択する手法である．この手法では最終的な仮説の統合は単純多数決によって行われる．

2. 3 多数決に対応した Boosting
本論文では, 仮説の統合方法が単純多数決となるアンサンブル手法について考える. 効果的なアンサンブル手法を検討するにあたり, 上述したようにアンサンブル手法の枠組みを組み合わせるという取り組みは多く存在する. しかし, 重み付き多数決を前提とする Boosting の枠組みを取り入れた手法では, 単純多数決による統合を行うものについては考えられていない. 効果的な単純多数決アンサンブルを構成するにあたり, Boostingの枠組みを取り入れるために, 多数決に対応した Boosting 手法を導入する.
最初に考案された多数決に対応したブースティング手法に,H(x) = sign(∑L)

l=1 hl (x)3. 2 提 案 手 法
効果的な多数決アンサンブルの構成法として，2 章で述べたアンサンブル学習の枠組みを組み合わせることを考える．すべての仮説を単純多数決で統合するために，Boosting の枠組みにおけるアンサンブル手法として Vote-boosting [11] を導入する．Algorithm1 に Vote-boosting の疑似コードを示す．ただし，II(·) は指示関数を表し，β(p; α, β) はパラメータ α, β であるベータ分布の確率密度関数を表すものとする．アルゴリズム
中において wl (i) はステップ l におけるデータ xi の重みであり，n+ (i) はステップ l までに学習した l 個の仮説のうち，xiを 1 と識別する仮説の数である．
本論文では，アンサンブル学習の枠組みを組み合わせてこのVote-boosting を並列化したアンサンブル手法 (Parallel-VB)を提案する. この手法では，まず 1 回に集める弱仮説の数をP <= L 個として学習を T (= L/P ) 回のステップに分解する.
その後, 1 ステップごとに P 回の Bagging に基づくサンプリ
ングと Random Subspace に基づく特徴選択を行い訓練データ

S̃t,1 , S̃t,2 , . . . , S̃t,P を生成し, それぞれの訓練データに対して弱仮説を学習して統合する. 最後に, そのステップで統合された弱仮説のアンサンブルを元に, Vote-boosting の手法によりデータの分布を調節する. この 1 連の処理を繰り返し行い, 弱仮説を

4. 1 データセット

Algorithm 1 Vote-boostingN
1: 入力:サンプルデータ {(xi , yi )}N
i=1 ∈ (X × {−1, +1})

2: 出力:仮説 H(x) : X → {−1, +1}
3: パラメータ:a(ベータ分布のパラメータ)

これらのデータセットは訓練データとテストデータの比率が4: 初期化: w1 (i) = 1/N , n+ (i) = 0 (i = 1, . . . , N )2 : 1 となるように、ランダムに分割した．

5: for l = 1 to L do
6:

訓練データと重み (S, wl ) によって弱仮説 hl を学習

7:

for i = 1 to N do(n+ (xi )+1t+2g

データの重みを更新: wl+1 (i) =

9:)

Z
Γ(2a)
Z:正規化項 , g(p) = β(p; a, a) = Γ(a)2 pa−1 (1 − p)a−1

end for10:

11: end for
12: 強仮説を生成: H(x) = sign

表 1 使用したデータセット
データセットn+ (i) = n+ (i) + II{hl (xi ) > 0}8:

本実験では UCI dataset repository から, 表 1 に示した 6 種類の 2 クラスのラベル付きデータセットを用いて実験を行った.

(∑ L

l=1 hl (x))

L 個集めたものを統合して強仮説とする. Algorithm2 に，提案手法の擬似コードを示す．

データ数

訓練データ

テストデータ

特徴数

Musk

476

319

157

140

cancer

569

382

187

30Blood

748502246

5Parkinson

756507249753

spam

4601

3083

1518

57

MAGIC

19020

12926

6276

104. 2 評 価 指 標
本実験においては, 1 章の目的において述べたとおり，汎化性能，多様性，並列化容易性の 3 つの観点から学習アルゴリズ

Algorithm 2 提案手法 (Parallel-VB)
N
1: 入力:サンプルデータ {(xi , yi )}N1 ∈ (X × {−1, +1})

2: 出力:仮説 H(x) : X → {−1, +1}

ムを評価する．汎化性能についてはテストデータに対する正解率 (Accuracy rate) によって評価し，多様性の評価については

3: パラメータ:P (並列度), a(ベータ分布のパラメータ)

個々の仮説の識別結果の不一致を測定する以下の disagreement

4: 初期化: w1 (i) = 1/N , n+ (i) = 0 (i = 1, . . . , N )measure を用いて評価を行った．結果の表は，最も高い値を太

5: for t = 1 to T do

字で、2 番目に高い値をイタリック体で表記している．

重み wt を考慮して新たに P 個の訓練データ S̃t,1 , S̃t,2 , . . . , S̃t,P6:を生成する

disagreement measure [12] は 2 個の仮説 hi と hj が異なる

7:

訓練データ S̃t,p によって弱仮説 ht,p を学習 (p = 1, . . . , P )8:for i = 1 to N do(gデータの重みを更新: wt+1 (i) =10:n+ (xi )+1tP +2)

disij =1 ∑II(hi (xi ) =| hj (xi ))
N s=1

Z
Γ(2a)

Z:正規化項 , g(p) = β(p; a, a) = Γ(a)2 pa−1 (1 − p)a−1
end for11:

予測を行う事例の割合を計算する.
Nn+ (i) = n+ (i) + II{hl (xi ) > 0}9:4. 2. 1 disagreement measure

仮説ごとに多くの異なる予測がなされれば, その集まりは多様であると考えられるため, この値が大きければより高い多様性

12: end for
13: 強仮説を生成: H(x) = sign(∑T)∑Pt=1
p=1 ht,p (x)を示す. 実験では, すべての仮説の組について disij を求め, その平均を取ることによって得られる全体の識別結果の不一致の割合 (Dis) を多様性の尺度とする.

4 実

験

Dis =L ∑i∑
2disij
L(L − 1) i=1 j=1

提案手法 (Parallel-VB) が効果的な多数決アンサンブルの構成法であるかを検討する目的で以下の 4 つのアンサンブル法による学習を行い，その結果を比較する実験を行った．

4. 3 実 験 結 果
4. 3. 1 汎 化 性 能•

Bagging Forest(特徴選択を行わない決定木のバギング)•

Random Forestに示す．Random Subspace や Bagging を導入した手法を用い•

Vote-boosting

るため，学習過程にランダムな要素が作用することを考慮して,•提案手法 (Parallel-VB)

全てのアンサンブル法において学習する弱仮説は深さ 3 の決
定木を CART アルゴリズムで学習し，統合する弱仮説の数をまず，汎化性能を測定するために各手法のテスト誤差を表 2各データセットに対して 10 回の学習を行い各学習で計算された指標の平均を結果としている.
表 2 をみると，Accuracy rate に関しては Vote-boosting もL = 500 に固定して実験を行った．Vote-boosting の重み更新

しくは提案手法のどちらかが優位となっている, 本実験に用いの際に利用するパラメータ a と，提案手法の並列度 P についたデータセットの結果のみで観察を行えば, データ数の少ないては 3 重交差検証を用いて決定したものを利用している．

データでは提案手法が優位になっている. Vote-boosting と提案手法の Accuracy rate についてもう少し詳しく示したのが図1 である. 提案手法にはランダム性があるため, 10 回学習を行表 2 Accuracy rate

Muskcancer

BloodParkinsonspamMAGIC

Bagging Forest0.76830.9383

0.78520.85360.90580.7968

Random Forest

0.7854

0.95480.73640.81920.85440.7363Vote-boosting

0.87220.96600.74940.87880.96100.8700Parallel-VB

0.87530.97450.74450.87400.95720.8649

表 3 disagreement measureMuskcancerBlood

Parkinson

spam

MAGIC

BaggingForest

0.26200.07665

0.12850.20890.09037

0.09757

RandomForest

0.38250.12700.096540.22330.25140.1438Vote-boosting

0.45740.26280.27350.43930.42320.4459Parallel-VB

0.47540.3016

0.33880.46190.44600.4567

い, その正解率の 95%信頼区間を求めている. 赤のラインで示めた提案手法の並列度 P と直列処理の総ステップ数 T を示す．

した Vote-boosting の正解率に対して提案手法の正解率がどの

表 4 提案手法の並列度データセットに対しても −0.01 以内に収まることから, 正解率

Musk cancer Blood Parkinson spam MAGICに関しては Vote-boosting と提案手法はほぼ同等であると考え

P

2525

10252られる.

T202050250

100250

この表から，交差検証によって，並列度が高く設定されたデータセットにはデータ数が少ないものであるという点が共通している．また，並列度の高いデータは Vote-boosting と比較した際の正解率においても優位な傾向にある．

4. 4 考察

誤差を bias と variance に分解するという考え方に基づいて,各アンサンブル手法の効果について考察する. 分類問題では, 誤差 (Error) は次の式のように分解することができる [13].

Error =
図 1 Vote-boosting vs Parallel-VB∑

P (x)(σx2 + bias2x + variancex )x

これらの式の各項は次の式で表される．

4. 3. 2 多 様 性
次に, disagreement measure の結果 (表 3) をみると提案手法が一貫して優位であり, この点においては Random Subspace

σx2の効果が顕著にあらわれていると考えられる.

4. 3. 3 並列化容易性
アンサンブル学習では，複数の仮説による識別結果の統合

1
=1−2bias2x =∑variancex =Random Subspace の枠組みによる学習においては，個々の仮1
1−2

2

P (YF = y | x)y∈{−1,1}[P (YF = y | x) − P (YH = y | x)]y∈{−1,1}

によって識別器を構成するため，個々の仮説の学習を並列に行うことで高速に識別子を構成することができる．Bagging，12∑∑
P (YH = y | x)2 y∈{−1,1}∈ {−1, 1} はそれぞれ目標関数と識別子に説の学習に用いる訓練データは，経験分布からそれぞれ独立

ここで，YF , YHにサンプリングしているので並列に行うことができる．一方，よって生起するラベルの確率変数である。σx2 は, 目標関数に依Boosting の枠組みによる学習においては，仮説の学習に用いる存して生まれる誤差であり本質的に取り除けない. そのため, 識訓練データの分布を逐次更新するため並列に処理を行うのは不別子と目標関数それぞれによって生起するラベルの期待値の差可能である．今回の提案手法では，パラメータである並列度 Pを示す bias2x と，各点に対する識別子によるラベルの生起確率に応じて Vote-boosting によって直列に行っていた処理を削減の変動性を示す variancex の 2 項を抑えることが誤差減少に寄しているため，識別器の構成速度が個々の仮説の学習の速度に与する.

のみ依存するとして概算した場合に，Vote-boosting に対してまず, Bagging による誤差への寄与を考える. 同じ分布からT (= L/P ) 倍高速に識別器を構成できる．表 4 に，本実験で各の再抽出することで生成された複数の弱仮説によって, アンデータセットにおいて訓練データに対する交差検証によって定サンブルの出力の標本平均の分散が小さくなるため，多数決

の結果が平均寄りに偏っていくことになり，P (YH = y|x) は1 または 0 に近づく．その結果 variancex を抑える効果が期待できる. Boosting においては, 提案手法において導入したVote-boosting の分布更新は, 決定境界 (識別ラベルの生起確率が 0.5) 付近のデータを重要視するため, bias2x が大きい場合に,それを抑える効果が期待できる. 最後に Random Subspace においては，ランダマイズにより各識別器のラベルの生起確率は0.5 に近づく. そのため, 分散を抑える効果とともに, 識別ラベ
ルの生起確率が 0.5 を下回る場合を補正する効果が期待できる.

5 ま と め本研究では, アンサンブル手法の 3 つの枠組みを取り入れた

Vote-boosting の並列化アルゴリズム Parallel-VB を提案した.
提案手法によって構成された識別子は Vote-boosting による識別子と同等の正解率でより多様性があるものとなっている. また, 提案手法において設定した並列度によって直列な処理を削減できるため, Vote-boosting の 2 倍以上の速度で識別器を構成できる. Vote-boosting に対しては正解率以外の点で, Random

Forest に対しては速度以外の面で効果的な構成法となっている.
今回の提案手法は, 既存手法に対して優位性は見られたが, 並列度のパラメータを設定する必要がある. そのため, この並列度を定めることができればより効果的なアルゴリズムとなる. この並列度を定める, もしくは候補を絞るためにアンサンブルの各手法がどのように性能に寄与するかを解析する必要がある．
また，データ数が少ないデータセットによる学習において提案手法が高い並列度でより良い正解率を達成する傾向が見られた点について，さらなる分析が必要である．

文献[1] K. Tumer and J. Ghosh, “Theoretical Foundations Of Linear And Order Statistics Combiners For Neural Pattern
Classifiers.” Technical report, IEEE Transactions on neuralnetworks, 1996.
[2] L. Breiman, “Bagging Predictors.” Machine Learning, 242(1996), 123–140.
[3] R. E. Schapire, “The Strength of Weak Learnability.” Machine Learning, 5-2(1990), 197–227.
[4] Y. Freund and R.E. Schapire, “A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting.” Journal of Computer System Sciences., 55-1(1997),119–139.
[5] T. K. Ho, “The random subspace method for constructing
decision forests.” IEEE Transactions on Pattern Analysis
and Machine Intelligence, 20-8(1998), 832–844.
[6] G.I. Webb, “Multiboosting: A technique for combining
boosting and wagging.” Machine learning, 40-2(2000), 159–196.
[7] C. Yu and D.B. Skillicorn, “Parallelizing boosting and bagging.” Technical Report 2001-442, Department of Computing and Infomation Science, Queen s University, 2001.
[8] N. Garca-Pedrajas and D. Ortiz-Boyer, “Boosting random
subspace method.” Neural Networks, 21-9(2008), 1344 –1362.
[9] L. Breiman, “Random Forests.” Machine Learning, 451(2001), 5–32.
[10] Y. Freund, “Boosting a Weak Learning Algorithm by Ma-jority.” Information and Computation, 121-2(1995), 256–285.
[11] M. Sabzevari, G. Martnez-Muoz and A. Surez, “Voteboosting ensembles.” Pattern Recognition, 83(2018), 119 –133.
[12] D.B. Skalak, “The sources of increased accuracy for two proposed boosting algorithms.” Proc. American Associationfor Artificial Intelligence, AAAI-96, Integrating Multiple
Learned Models Workshop, 1129, Portland, OR, 120–125.
[13] R. Kohavi and D.H. Wolpert, “Bias plus variance decomposition for zero-one loss functions.” Proc. of the 13th International Conference on Machine Learning (ICML 1996),
Bari, Italy, 275–283.