パラメトリック計画法を用いたマルチインスタンス SVM

平成 25 年度創成シミュレーション工学専攻修士論文梗概集
計算応用科学分野
パラメトリック計画法を用いたマルチインスタンス SVM
学籍番号 24413506 氏名石原直樹
指導教員名竹内一郎准教授
1
はじめに
機械学習における教師あり学習は，過去の入力サン
プルの特徴と出力 (教師ラベル) から，未知のサンプル
に対する出力を予測する問題である．しかし，サンプル
の特徴を取得する容易さに比べ，教師ラベルの取得は
コストが高いことが多く，曖昧な教師ラベル情報を用
いて学習を行う弱ラベルデータ学習が注目されている．
中でも，薬剤活性分析や画像のカテゴリ分類など多く
の現実社会での問題がマルチインスタンス学習 (MIL:
Multi-Instance Learning) と呼ばれる枠組みで扱えるこ
とが指摘されている．
本稿では，MIL に SVM(Support Vector Machine) を
適用したマルチインスタンス SVM[1] に注目する．通
常の教師あり学習の手法である SVM を MIL にそのま
ま適用することはできないため，様々なモデルが提案
されている．このとき，主に二つの問題が生じる．
一つは，解くべき問題に適したモデルを選択するこ
とである．従来研究では，モデルの候補をあらかじめ
決め，候補の中から判別に用いるモデルを決定してい
る．しかし，最適なモデルを選択するには，候補とな
るモデルを増やす必要があり，全ての候補のモデルを
学習するとコストが大きくなる．
二つ目は，一般にマルチインスタンス SVM が非凸
最適化問題となるため，より良い局所最適解を得るこ
とが求められる点である．
本稿では，従来研究で提案されているマルチインス
タンス SVM を統一的な枠組みで定式化し，その局所
最適解の性質を明らかにする．また，二つのモデルを
統合したモデルを示し，パラメトリック計画法を用い
た効率的なアルゴリズムを提案する．
2
マルチインスタンス学習
MIL では，バッグと呼ばれる学習インスタンス (サ
ンプル) の集合に対して教師ラベルが与えられる．正ラ
ベル (+1) が付与されているバッグは正バッグと呼ば
れ，負ラベル (−1) が付与されているバッグは負バッグ
と呼ばれる．バッグのラベルは，
正バッグ : 少なくとも一つのインスタンスが正ラベル
負バッグ : 全てのインスタンスが負ラベル
と定義される．しかし，
「どのインスタンスが正ラベル
であるか」や「正ラベルのインスタンスが何個含まれ
るか」は未知である．
例えば，画像のカテゴリ分類のタスクでは，画像を
物体 (インスタンス) の集合であるバッグとみなし，各
インスタンスを特徴ベクトルとして表現する．画像内
に一つでも対象カテゴリに分類される物体が存在すれ
ば，その画像は対象カテゴリに分類される．
マルチインスタンス学習では，学習インスタンス
{xi ∈ Rd }ni=1 とバッグおよびそのラベル {(Bℓ , Yℓ )}N
ℓ=1
が学習データとして与えられる．ここで，Bℓ はバッ
グ ℓ に属するインスタンスのインデックス集合を表し，
Yℓ ∈ {−1, +1} はバッグのラベルを表す．
3
マルチインスタンス SVM
SVM は，分類境界 f (x) = 0 と 2 クラスとの距離
(マージン) を最大にする判別関数 f (x) = w⊤ x を学習
する問題である．しかし，MIL では与えられているイ
ンスタンスの特徴ベクトルとバッグのラベルが一対一
に対応しないため，SVM をそのまま適用することがで
きない．そこで，主に二つの手法が提案されている．
一つ目は，MI-SVM[1] と呼ばれ，バッグ毎に一つの
代表インスタンスを決定し，代表インスタンスの特徴
ベクトルをバッグの特徴ベクトルとして扱う手法であ
る．バッグの特徴ベクトルとバッグのラベルを用いて分
類器を学習することができるが，分類器によって選ば
れる代表ベクトルが変わるため非凸最適化問題となる．
二つ目は，mi-SVM[1] と呼ばれ，各インスタンスの
ラベルを推定し，その推定ラベルを用いて分類器を学
習する手法である．推定ラベルは分類器によって変化
するため非凸最適化問題となる．
マルチインスタンス SVM は一般に，インスタンス
のラベル y ∈ {−1, +1}n および，正則化パラメータ C
を個別に拡張した個別重み c ∈ Rn
+ を用いて，
min min
y∈Y,c∈C
f
n
∑
1
∥w∥2 +
ci [1 − yi f (xi )]+ ,
2
i=1
(1)
と定式化される．
既存研究で提案されているモデルの多くは，Y およ
び C を適切に設定することで，(1) の形式で表現するこ
とができる．また，詳細は省くが，y = y ′ , c = c′ と固
定したときの (1) の解を fy′ ,c′ と表すと，f = fy′ ,c′ と
固定したときの (1) の解が y ′ , c′ である場合，fy′ ,c′ が
局所最適解であることを証明できる．
平成 25 年度創成シミュレーション工学専攻修士論文梗概集
計算応用科学分野
4
パラメトリック計画法を用いたマルチインスタン
ス SVM
Ele.
Sun.
Hor.
本稿では，パラメトリック計画法と呼ばれる手法を
用いたマルチインスタンス SVM を提案する．
上述の通り，マルチインスタンス SVM は，Y, C を選
ぶことによって様々なモデルを表現できるため，M =
Y × C と表記する．提案手法では，混合パラメータ θ =
[0, 1] を用いて，二つのモデルを混合したパラメトリッ
クモデルを
min (1 − θ)J(f |y0 , c0 ) + θJ(f |y1 , c1 ),
f
と定式化する．このとき，θ = 0 では M0 と一致し，
θ = 1 では M1 と一致する．また，θ = (0, 1) では M0
と M1 を混合したモデルを表現することができる．
提案アルゴリズムでは，局所最適解を θ の関数とし
て表し，θ を 0 から 1 まで変化させた際の局所最適解
の変化を追跡する．
より単純なモデルから複雑なモデルへ変化させれば，
アニーリングとみなすことができ，より良い局所最適
解を得ることが期待される．また，アルゴリズム中で，
モデル選択の基準となる誤分類率なども同時に追跡す
ることにより，最適な θ を決定することができる．こ
れは，θ を無限個の候補の中から選択しているとみな
せるため，θ を固定して交互最適化を行う従来の手法
よりも効率的により良いモデルを選択することが可能
となる．
また，提案アルゴリズムは，半教師あり学習やクラ
スタリングなどに応用することもできる．
5
表 2: mi-SVM の目的関数値
mi-SVM
fix→mi
C-ann.
1450.151 1359.757 1417.255
1013.103 1001.755
667.305
1053.488
1060.348
342.755
Ele.
Sun.
Hor.
計算機実験
提案手法の有効性を実データに対する計算機実験に
よって比較する．本稿では，提案手法と MI-SVM お
よび mi-SVM を比較した．全ての手法でガウシアン
カーネルを使用し，ガウシアンカーネルのパラメータ
は γ ∈ {1/d, 5/d, 10/d} とした．d は入力データの次元
数である．また，正則化パラメータは C ∈ {n, 5n, 10n}
とした．n は学習データのインスタンス数である．
学習データで学習を行い，検証データの誤判別率を最
小にしたパラメータを用いて，測定したテストデータの
誤判別率を表 1 に示す．提案手法として，MI-SVM か
ら mi-SVM へ変化させた MI→mi とその逆の mi→MI
の結果を掲載する．どちらもより良いモデルを選択で
きていることがわかる．
次にアニーリングについて検証する．γ = 1/d, C =
10n とし，バッグのラベルをインスタンスのラベルと
みなした SVM から mi-SVM へ変化させた fix→mi と
mi-SVM の C を 10−3 から提案手法によって増加させ
た C-ann. および交互最適化による mi-SVM の目的関
数値を表 2 に示す．
CPU Time(sec)
min
(c0 , y0 ) ∈ M0
(c1 , y1 ) ∈ M1
表 1: テストデータの誤判別率
MI-SVM mi-SVM MI→mi mi→MI
0.314
0.325
0.285
0.309
0.175
0.175
0.190
0.159
0.107
0.121
0.104
0.107
35
30
25
20
15
10
5
0
Proposed
Naive
1
2 3 4 5 6 7 8 9 10
the number of candidates
図 1: モデル選択にかかる計算時間
提案手法によってアニーリングを実現することがで
き，より良い局所最適解を得られていることがわかる．
特に C を増加させた場合に顕著に向上している．
また，θ を離散的に変化させた場合 (Naive) と提案手
法によって連続的に変化させた場合 (Proposed) のモデ
ル選択にかかる計算時間を図 1 に示す．従来手法では
モデルの候補数が増えると計算時間も増えるのに対し，
提案手法の計算時間はモデルの候補数に依存しない．
6
まとめ
本稿では，マルチインスタンス SVM の一般的な定
式化と局所最適性条件を導出し，二つのモデルを混合
したパラメトリックモデルを考え，効率的なアルゴリ
ズムを提案した．
今後，人工データなどを用いて，インスタンスの分
類の精度や，データの性質による精度の違いを調べる
必要がある．また，他手法との比較も行う．
参考文献
[1] S. Andrews, I. Tsochantaridis, and T. Hofmann.
Support vector machines for multiple-instance
learning. In Advances in Neural Information Processing Systems, Vol. 15, pp. 561–568. The MIT
Press, 2003.

Download Report