June 2013, M. Lapin+

=

学習アルゴリズムに事前知識(prior knowledge)を組み込むことで、

- 学習アルゴリズムの識別率向上
- 訓練に必要なデータ量の削減

が行える。
Vapnikら(2009)によって提案されたLUPI(Learning Using Privileged Information)パラダイムでは、訓練時にのみ使用できる付加情報を利用することでこれを可能にしている。

本論文では、

- privileged information(特権情報?)を重要度の重み付けに利用
- privileged features(特権特徴量)として表現可能な事前知識を、それぞれの訓練事例についての重みによって表現

Weighted SVMがSVM+の解を常に再現する一方、収束せずSVM+の限界となる反例を示す。
privileged informationが利用できない場合のweighted SVMの重み選択問題についても触れる。

=

# 事前知識、特権情報、重み
分類問題において、訓練データの量が限られている場合、訓練用サンプルに加えて利用可能な情報ー事前知識(prior knowledge)ーは識別性能の改善にとって重要な要素。
事前知識は異なる形式をとり、学習問題への組み込み方はアルゴリズムと同様に、独特の設定が必要。
二値分類での事前知識のSVM(Support Vector Machine)への導入に焦点を当てて解説する。

Lauer & Bloch (2008)では、事前知識をSVMに組み込むための異なる方法をレビューし、それらの方法を事前知識の型(type)に応じて分類。

本論文では、目的関数に関するものよりも、”訓練データに関する付加情報”についての場合を考える。

厳密でないが関連する設定としては、半教師あり学習のアプローチがあり、ラベルづけされていないデータが入力空間における周辺分布についてのある情報をもっているというもの。

Vapnik & Vashist(2009)において、LUPI(Learning Using Privileged Information)パラダイムが提案された。
この中では、付加情報は特権特徴量(privileged features)という形式をとり、これは訓練時に利用できるが、テスト時には使用できない。
これらの特徴量は
- 損失関数の上界をパラメータ化
- 与えられた訓練サンプルについて最適な識別器の損失を推定
するのに使用される。

高い損失の値は、与えられたデータ点が外れ値である可能性がある場合の指標という見方もできる。
故に、外れ値でない場合とは異なる取り扱いをしなければならない。

訓練事例が外れ値である可能性がある場合の付加情報は、インスタンスの重みによってエンコードされる。
よって、LUPIフレームワークと重要度重み付けの関係は非常に近いものと予想できる。

重要度重み付けの場合、非負の重みをもつ各訓練事例は、エラーのコストのバランスをとるために損失関数で使用される。
インスタンスの重みが自然にできる典型的な例は、cost-sensitive learningである。(Elkan, 2001)

もしクラスに偏りがあったり、異なる誤分類エラーが異なるペナルティーを受けたりすることがあれば、事前知識をインスタンスの重みとしてエンコードできる。
データ点への高い重みづけは、学習アルゴリズムがその点を正しく、おそらく”重要ではない”として誤分類されたコストで、識別すべきであることを示唆している。

しかしながら、本論文では、cost-sensitiveな仮定を行わない。(つまり、異なるエラーはテスト集合について異なるコストを生むという仮定はしない)

代わりに、訓練集合とテスト集合での重要度重みづけを分ける。
これにより、もしそれによりよいモデルが得られるならば、外れ値に対して高い重みづけを行うこともできる。

事前知識の異なる形式が存在し、エンコードも異なる可能性がある。
本論文では、インスタンスの重みが”事前知識の同じ型”を表現でき、特権特徴量によってエンコードされることを示す。
特に、これにより重要度の重みづけがされたという点において特権特徴量の効果を説明できる。
驚くことに、結果の重みは外れ値を強調する。これはSVMのサポートベクターにも起こる。

SVMをLUPI frameworkに拡張するSVM+アルゴリズム。
凸解析の基本ツールを使い、SVM+解の一意性とその解がweighted SVM (WSVM)と関係することを求める。
SVM+の解とWSVMのインスタンス重みには、単純なつながりがある。
さらに、その関係がSVM+アルゴリズムのさらなる理解と、SVM+の限界を学ぶために使用できる。
WSVMにおけるインスタンス重みがSVM+の特権特徴量のように同じ目的を持っていることを見た上で、特権特徴量が使用できない場合の重み選択の問題に戻る。

- SVM+のnon-trivialな解が主形式において一意であることを示す。オフセットbが一意でないWSVMよりも強い解。
- SVM+を双対最適化問題に変形。WSVMアルゴリズムと密接な繋がりがあることを明らかにする。特に任意のSVM+双対解がWSVMに対する重みを構成できることを示す。適切な重み選択によりWSVMがSVM+を擬似的に模倣できることを示し、これによりSVM+の解からWSVMの解を求めることが常に可能である。
- WSVMの解からSVM+の解が求められるかを調べる(つまり２つのアルゴリズムが同値かどうか)。同値になる必要十分条件を与え、SVM+の解がWSVMの解のstrict subsetになっていることを明らかにする。WSVMの解がSVM+によって求められない場合の例を示す。
- 特権特徴量がない場合の重み選択問題に帰着

(書きかけメモ)