機械学習プロショナルシリーズ-サポートベクトルマシン 読書メモ

サマリー

カーネル法とは、機械学習において非線形な関係性を扱うために用いられる手法で、カーネル関数と呼ばれる関数を用いて、データ間の類似性を測定し、入力データの特徴量同士の内積を計算することで、2つのデータ間の類似性を評価するものとなる。カーネル法は、主にサポートベクトルマシン(SVM)やカーネル主成分分析(KPCA)、あるいはガウス過程(GP)などのアルゴリズムで利用されている。

サポートベクトルマシン(Support Vector Machine、SVM)は、線形分離不可能なデータを分類することが可能な機械学習技術であり、教師あり学習の分類や回帰に利用されるものとなる。SVMは、前述のカーネル法を用いることで、2つのクラスを分離する超平面を探索し、線形分離不可能なデータの分類を実現する。

SVMの利点としては、線形分類器だけでなく非線形分類器にも適用可能であること、汎化性能が高いこと、過学習が起こりにくいことなどが挙げられる。また課題として、データ数が非常に多い場合や、カーネル関数の選択によっては過学習の問題が生じる、カーネル関数の設定によっては計算コストが高くなり、処理時間が長くなるなどが挙げられる。

ここでは機械学習プロフェッショナルシリーズ「サポートベクトルマシン」をベースにこのサポートベクトルマシンの理論と応用について述べる。

機械学習プロショナルシリーズ-サポートベクトルマシン 読書メモ

読書メモを以下に述べる。

第1章　2クラス分類

1.1 はじめに
2クラス分類 (binary classification problem)
与えられたカテゴリが2つのカテゴリのどちらに属するかを識別する問題
カテゴリのことを「クラス(class)」と呼ぶ
例:画像が人かどうかを識別
前処理
ウィンドウをどう定めるか
画像をどのような形式で表現するのか
事例:(xi,yi)
xi:画像特徴量
画像を表現する何らかの数値ベクトル
特徴ベクトル(feature vector)
入力ベクトル(input vector)
例:単純に各画素値を並べて数値列を作る
画像中の画素値の局所的な変化から特徴を生成
特徴抽出(feature extraction)
特定のタスクに依存する
Yi:ラベル(label)
クラスを表現するラベル
分類器(classifier)
受け取った画像の属するクラスを推定する処理を行う部分
何らかの特徴ベクトルxが与えられた時にラベルyの予測値を返す関数
使用者に提示するための後処理
後処理と前処理はシステムの用途によって大きく違う
SVM (サーポートベクトルマシン: Support vector machine)
元々2クラス分類だが
回帰問題や教師なし学習への拡張
SV分類 (サポートベクトル分類: support vector classification)
分類問題
1.2 線形SV分類
はじめに
N個の事例からなる訓練集合{(xi,yi)}i∈[n]がd次元実数ベクトルxi ∈ ℝdと、 1か-1の値をとるラベルyi∈{-1,1}から構成されているとする
決定関数(decision function)と呼ばれる実数関数f:ℝd → ℝを用いて、 上式のように分類器g(x)を定義する
f(x)として上記の関数を考える
d次元ベクトルw∈ℝdと スカラーb∈ℝは事前にはわからない未知の変数
スカラーbをバイアスと呼ぶこともある
xの空間においてf(x)=0となるxはクラスを分ける境界
分類境界 (classification boundary)
これらをどのように推定するのかを考えなければならない
SV分類がどのような考え方に基づいてwとbを推定するのか?
1.2.1 ハードマージン
訓練集合内の点全てを正しく分類できる wとbの組が存在する場合
訓練集合はf(x)によって分離可能(separatable)
あるyiについて分類に成功しているなら
yiとf(xi)の符号が一致することと上式は同等
分離可能な訓練集合では 全てのi∈[n]に対してyif(xi)>0が成り立つような f(x)が存在する
一般、訓練集合を分離できる分類境界は複数存在する
SVMではそれぞれのクラスのデータが 分類境界からなるべく離れるようにして 分類境界を定める
分類境界を挟んで二つのクラスがどれくらい離れているかを 「マージン(margin)」と呼ぶ
bがマージンが大きい
マージン最大化 (margin maximization)
なるべく大きなマージンを持つ分類境界を求める
マージン最大化は 「分類境界から最も近くにあるxi」との距離 を最大化すること
あるxiから分類境界までの距離は 点と平面の距離の公式から上式となる
マージン最大化は上式の最適化問題により表現できる
s.t. (subject to の略)
制約条件(constraint)
制約条件が満たされている範囲での最大化を求める
目的関数の値 M/∥w∥を最大化するためには Mをなるべく大きくしたい
Mは制約条件 yi(wTxi + b) ≥ Mによって 全てのyi(wTxi + b)以下でなければならない
Mは全ての事例に対するyi(wTxi + b) の値のうち最も小さい値と同じになる
wとbをMで割ったw/Mとb/Mを、 それぞれẇとṁとして置き換えると
下記の二つを考慮すると 最適化問題はさらに上式のようになる
1/∥w∥の最大化が、逆数である∥w∥の最小化と等価であること
∥w∥の最小化はノルムを2錠した∥w∥2の最小化と等価であること
1.2.2 ソフトマージン
SV分類を分離可能ではないデータに適用する場合
SV分類の持つ制約条件を緩和する
yi(wTxi + b) ≥ 1 – ξi, i∈[n] 新たな非負の変数𝛏iを導入
xiがマージンを超えて異なるクラスに入ることを許容する
サポートベクトルマシンの最適化問題の再定義
係数Cは正規化係数 (regularization parameter)
(左側)Cが大きい時は𝛏を抑制する力が大きいので データがマージンを超えて御分類に入ることはあまりない
(右側)Cが小さく、マージンが広く撮れればデータがマージンを超えることを許容する
∥w∥2を2で割っているのは、後々の計算を簡単にするため
第2項は元の制約条件wTxi+b≥1に対する 違反の度合いであるξiがなるべく小さくなるように抑制している
抑制の度合い調整するためのパラメータず正則化係数Cの役割
Cを大きくするとハードマージンに近づく
具体的にどのようなCを使うかは、「交差検証法(cross valisation)」などを使って評価する
ソフトマージンでは各訓練集合を yi(wTxi+b)の値により3つの種類に分けて考える
マージンの外側 yi(wTxi+b)>1となるようなxi
マージン上 yi(wTxi+b)=1となるようなxi
マージンの内側 yi(wTxi+b)<1となるようなxi
1.3 双対表現
はじめに
最適化問題はSV分類の 主問題(primal problem)
双対問題(dual problem)を解くことで、 同じ最適化問題に対して違った見方を得られることもある
SVMでは主問題の代わりに 双対問題を解くことでも 分類器を得ることができる
非線形化を考える上で 双対問題の形式が有用であることが関係する
1.3.1 双対問題
最適化問題を上式のように書き換える
ラグランジュ関数(Lagrange function)
新たにαi∈ℝ+、i∈[n]とμi∈ℝ+、i∈[n]という非負の変数を導入する
αとμはベクトルα=(α1,…,αn)T、μ=(μ1,…,μn)Tを意味する
αと一つ目の制約条件の左辺 -(yi(wTxi+b)-1+ξi)
μiと二つ目の制約条件の左辺 -𝛏iを乗算したものをそれぞれ目的関数に足し合わせる
主変数(primal variable) w、b、ξ
双対変数(dual variable) α、μ
ラグランジュ変数を双対変数について 最大化した関数をP(w、b、ξ)と定義する
この関数を主変数について最小化する最適化問題
関数p(w, b, ξ)内のmaxはLの後ろ2項にのみ関わるため、 上記の関係が成立する
最適化問題において制約条件を全て満たしていることを 実行可能(feasible)であるという
主変数が実行可能でない場合 – (yi(wTxi+b) -1 +ξi) > 0か -ξi>0となっているiが存在する
ラグランジェ関数Lをどこまでも大きくすることができ、最大値が存在しなくなる
主要変数が実行可能な場合 – (yi(wTxi+b) -1 +ξi) ≤ 0か -ξi≤0であるため
αiとμiの積の項の最大値は0
一般的な最適化問題の式が現れる
ラグランジュ関数を主変数について 最小化した関数をD(α、μ)と定義する
D(α,μ)を双対変数α、μについて 最大化する問題(双対問題)
右辺の内側の最小化 (Lのw,b,𝝃の偏微分が0)
Lはwに関して凸2次間数であり、微分して0になる点で最小
Lはbと𝝃に関しては1次なので 係数(微分して得られる値)が0でない限り、 制約のない最小化ではこれらの変数を動かすことで Lをどこまでも小さくすることができる
式の変形
主変数だけでなく、μも消去された式となる
αだけの式
双対問題の表現式
1.3.2 双対性と鞍点
主問題と双対問題の関係性
主変数w,b,𝛏と双対変数α,μの組が存在することを仮定
主問題の最適解と双対問題の最適解の関係
続き
上式のような双対問題の最適値が 主問題の最適値以下という関係がわかる
弱双対性(weak duality)
サポートベクトルマシンの場合
より強い強双対性(strong duality)と呼ばれる性質が成り立つ
主問題と双対問題の目的関数値が 最適解において一致する
上記の等式が成り立つ
更に上式が成り立つ
L(w*,b*,𝛏*,α*,μ*)が 主変数w,b,𝛏については極小値であり、 双対変数α,μについては極大値である
関数の鞍点(saddle point)
関数がある方向(軸1)では極大値をとり
ある方向(軸2)では極小値をとる
1.3.3 最適性条件
最適化問題の解を得るために、 解の最適性を判定するための条件を知る必要性がある
それらの条件を記述するときにも双対性は現れる
SV分類の解の最適性はカールーシュ・クーン・タッカー条件(Karush-Kuhn-Tucker condition:KKT条件)が必要十分条件になる
ラグランジュ関数の主変数に関する微分
主問題の制約条件
双対変数の非負条件
相補正条件 (complementarity condition)
続き
マージンと特徴ベクトルの位置関係と双対変数
マージンの措置側に位置する特徴ベクトルが多数存在する場合には、 双対変数のベクトルαは沢山の0を持つ(スパース)
1.4 カーネルによる一般化
双対問題はSVMの非線形化を考える上で重要な役割をはたす
入力xを何らかの特徴空間Fへ写像する関数Φ:ℝd→ Fを考える
このΦ(x)を新たな特徴ベクトルとすると
f(x) = wTΦ(x) + b
パラメータwも特徴空間F内の要素(w∈F)
写像Φによる変換が非線形であれば f(x)=0によって定義される分類境界は 元の空間では非線形になる
f(x)はΦ(x)に関しては一次なので、 Φ(x)の空間Fではf(x)=0は線形な分類境界を形成する
双対問題のxをΦ(x)とすれば1.3の議論はそのまま使える
左の式でΦは内積Φ(xi)TΦ(xj)の形でのみ現れる
Φ(x)を直接計算しなくても、 内積Φ(xi)TΦ(xj)さえ計算できれば良い
内積Φ(xi)TΦ(xj)をカーネル関数 (kernel function)として定義する
カーネル関数の例
RBF(radial basis function)カーネル
ガウスカーネルとも呼ばれる
γはハイパーパラメータ(事前の設定が必要)
RBFカーネルによるSV分類例
カーネル関数を使うと双対問題は上式のように記述できる
f(x)もカーネル関数を使うと上式のように記述できる
1.5 計算上の特徴
SVが持つ実装上の計算についての望ましい性質
凸2次最適化問題への帰着
SV分類問題の最適化は凸2次最適化問題 (convex quadratic optimization problem) と呼ばれる種類の最適化問題に帰結
凸2次最適化問題は比較的扱いやすく、 どのような初期値から出発しても大域最適解にたどり着く
双対変数のスパース性
双対変数αの一部が0になることは計算効率上有利に働く
内積によるデータの表現
SV問題の双対問題は 特徴ベクトルxに対して 内積の形でのみ依存する
カーネル関数による非線形化が可能になる
特定の問題が特徴ベクトルの内積のみで表現されている場合に、 内積をカーネル関数で置き換えてモデルを非線形化する考え方
カーネルトリック(kernel trick)
主成分分析(principal component analysis)等でも適用されてきた
1.6 SV分類の性質
はじめに
一般的な統計的推定問題として分類問題がどのように解釈されるのか?
1.6.1 期待損失最小化
入力とラベルを確率変数とみなす
実際の訓練データは確率変数の実現値
データが確率密度p(X,Y)に基づいて生成されているとしたとき
どのような分類器g(x)が望ましいのか
分類のよさを測るために「損失関数(loss function)」ℓ(y,g(x)という関数を導入
2クラス分類の場合(0-1損失)と呼ばれる
起こりうる全てのXとYに対して期待値をとった 期待損失(expected loss)を上式のように定義する
0-1損失の場合の、 期待損失を最小化するような分類器は 条件付き確率を使って上式のようになる
ベイズ分類器(Bayes classifier)
ベイズ決定境界
ベイズ分類器が作る分類の境界
1.6.2 損失関数と正則化
XとYに関する期待値を含む期待損失を 最小化するための分類器を求めることは実際には非常に困難
手持ちの訓練情報によって期待値を近似した 経験損失(empirical loss)を上式のように考える
この値は期待損失と比較して容易に計算できる
分類器の精度を測る基準としては実用的
経験損失を最小化することで 訓練集合をうまく分類する分類器を推定可能
0-1損失の近似的な代理として、「ヒンジ損失(hinge loss)」と呼ばれる損失関数を定義する
ヒンジ関数
連続かつ凸な関数による0-1損失の近似
ヒンジ損失と0-1損失の比較
決定関数をf(x)=wTΦ(x) + bとする
訓練集合に対してヒンジ損失を最小化する 最適化問題は上式のようになる
内側のmaxは新たに変数ξiを導入すると上式のように表現できる
最適化問題の最終的な帰結
訓練集合の分類のみを追求することは 必ずしも期待損失を小さくするとは限らない
ベイズ決定境界(青波線)と 訓練データの後分類を最小化するように 学習した分類境界線(黒実線)の比較
黒い実践の分類協会は訓練データを厳密に分類している
ベイズ決定境界とは大きく異なる
期待値の意味での最適な分類制度を達成していない
過学習(over-fitting)
過学習を防ぐためには 分類器に何らかの制限を加えることが必要
正則化として決定関数のパラメータwのL2ノルムが 大きくなりすぎないように制限する方法
左の手法の最適化問題
λ:正則化係数 (regularization parameter)
分類器がどの程度制限されるかが決定される
Λを2で割る形は、なくても構わない
L2ノルムを用いる形は計算が簡単なうえ 実用上高い制度を出すことが多い
多く用いられる
ソフトマージンSV分類と等価になる
λ=1/Cとすると
Λの値を変えて学習した3通りの分類境界の例
Λを大きくするほど正則化により分類境界が制限されて滑らかになる
損失関数と正則化項の和を最小にする枠組み
ヒンジ損失
損失関数に異なる関数を用いた異なる手法
二乗誤差損失(squared error loss)
回帰分析において古くから用いられてきた損失関数
Yと決定関数f(x)の差の2乗を損失と考える
問題点
yf(x)>1であるような事例にも損失が発生する
2次関数であるため外れ値(oulier)から受ける影響が大きい
ロジスティック損失(logistic loss)
ロジスティック回帰(logistic regression)と呼ばれる統計学で古くから知られる手法
二項分布の負の対数尤度から導かれた損失関数
確率的な解釈が明確
1.6.3 条件付き確率推定
0-1損失はベイズ分類器と 関連づけことができたが、
最適化計算の簡便さから ヒンジ損失などと置き換えていた
各損失関数における期待損失𝔼X,Y[ℓ(Y,f(X)]を最小化するf(x)の比較
二乗誤差損失は、条件付き確率の線形関数を推定
ロジスティック損失は、条件付き確率の比を推定
ヒンジ損失は、条件付き確率を離散値に変換したものを推定
期待値を最小化するf(x)は全てベイズ分類器を実現
期待値での場合であり、有限値では例えば外れ値でそれぞれ異なってくる
条件付き確率が得られればベイズ分類が実現される
ベイズの定理(Bayes’ theorem)を使った直接的な推定も可能
ベイズの定理
分母はYに依存しないため、
観測された入力xについてどのラベルyを割り降るべきか比較するためには p(X=x|Y)p(Y)を計算すれば良い
確率の基本公式によりp(X|Y)p(Y)=p(X,Y)
同時確率p(X,Y)はデータが生成される確率である
この確率密度を推定する方法は 「生成モデル(generative model)」と呼ばれる
生成モデルには確率密度p(X,Y)をどのようにモデル化するかによって様々な手法が存在する
p(Y)
p(Y)はXに依存しないYの分布
単純には訓練データ中の各クラスの事例から推定できる
正のクラスの事例数をn+、負のクラスの事例数をn-とする
p(Y=1)=n+/nかつp(Y=-1)=n-/n
p(X|Y)
それぞれのクラスのp(X|Y)に異なる平均と共通の共分散行列を持つ 正規分布(normal distribution)を導入すると
線形判別分析(linear discriminant analysis)が導かれる
SV分類の特徴は分類に必要な最小限のものを直接推定している
ヴァプニックの法則 (Vapnik’s principle)
ある問題を解く時に、 その問題よりも一般性のある問題を解いてはならない
分類境界だけを直接求めている

第2章　多クラス分類

2.1 はじめに
各事例が1からcまでのc種類のクラスのいずれかに属する 多クラス分類問題(multi-class classification problem)
ラベルはyi∈{1,…,c}と表現できる
多クラス分類の応用例
多クラス分類を実現する方法
通常の2クラス分類器を組み合わせる方法
1対多方式
1対1方式
謝り訂正出力符号
SVMの定式化自体を拡張する方法
2.2 1対他方式 (One-versus-rest)
複数の2クラス分類を組み合わせることで 多クラス分類を実現する最も単純な方法
あるクラスに属するxと属さないxを分ける 分類器を各クラスについて学習する
k番目のクラスに属するxiを正のクラス それ以外のxiを負のクラスとみなして 学習した2クラスSV分類の決定関数をfk(x)と表記する
1対多方式ではfk(x)の最大値を選ぶことでクラス分類を行う
入力xに対する分類器の出力g(x)は上式で表される
各決定関数の出力であるfk(x)が大きいほど xがクラスkに属している確信度が強いという 解釈での分類規則
2クラス分類をクラスの数だけ学習するだけで実現
実装が容易
問題点
異なるSV分類の決定関数fk(x)の大小比較することが適切かどうか?は明確でない
各クラスの分類器を学習する際に、 クラスラベル数の非対称性に 気をつけなければならなす場合もある
クラスkの事例数が少ない場合は、fk(x)は負に偏りがち
2.3 1対1方式
はじめに
1対1方式(one-versus-one)
異なるクラス間のペアに対する分類に基づく方法
c個のクラスに対して、 クラスiとクラスjに属する事例のみを取り出して
その2クラスを分類する
fij(x)と表記する
全てのクラスのペアを考えると
分類器を(c-1)c/2個作成することができる
あるxをどのクラスに分類するかは、 (c-1)c/2個の分類器による投票(多数決)により定められる
問題点
多数の2クラス分類器を用意する必要がある
同数票を獲得したクラスが複数現れると分類が不可能
利点
訓練データは少なくて済むので、1回の学習にかかる計算コストは少なくて済む
ペアに基づく多クラス分類の判定方法
単純な投票による方法
非循環有向グラフによる方法
ペアワイズカップリング法
2.3.1 非循環有向グラフによる方法 (directed acyclic graph)
投票による方法では、あるxを分類するために全ての(c-1)c/2の決定関数を評価した
非循環有向グラフ(directed acyclic graph)による方法では
逐次的に2クラス分類を行っていくことで より少ない決定関数の評価で多クラス分類を行うことができる
多クラス分類のための非循環有効グラフの例
各頂点に対応する分類器を準備するためには (c-1)c/2回SV分類の学習を行う必要があるが
新たな入力xを分類するための出力を 計算する必要のある分類器は少なくなる
2.3.2 ペアワイズカップリング (Pairwise coupling)
確率的な解釈に基づいて1対1間の分類結果から 多クラス分類規則を推定する手法
多クラス分類においては
上式の条件付き確率が得られれば ベイズ分類器が実現できる
1対1方式では
「クラスiかクラスjに属するxが与えられている」という条件の元で
Iとjのどちらのクラスに割り振るべきか
条件付き確率の式
ペア単位の推定結果p(Y=i|Y∈{i,j}, X=x)から、 真に必要な条件付き確率p(Y=i|X=x)を推定する
SV分類の決定関数f(x)は 条件付き確率を推定しているわけではない
クラスiとクラスjのペアに対する決定関数fij(x)から 条件付き確率p(Y=i|Y∈{i,j}, X=x)をモデル化する
A∈ℝとB∈ℝはパラメータとする
パラメータは最尤推定法(maximum likelihood estimation)により推定可能
負の対数尤度の最小化の表現
この最適化問題を解くにはニュートン法などの標準的な手法を適用する
AとBを推定することで、任意のxについてṗij(x)を計算できる
このṗij(x)からp(Y=i|X=x)を推定する
確率の基本的な公式から
2つの確率密度関数の違いを測る指標
カルバック・ライブラー・ダイバージェンス (Kullback-Leibler divergence)
常に非負の値をとる
与えられた2つの確率密度関数が同一の場合に0になる
各クラスペアの事例数で重み付けした KLダイバージェンスの和を基準として定義する
この基準を確立としての制約(足すと1になる)とpi≥0を考慮しつつ
{pi}I∈[c]について最小化すると
条件付き確率pi=p(Y=I|X=x)の推定値を得ることができる
2.4 誤り訂正出力符号
謝り訂正符号(error correcting code)は
伝送された信号に含まれた誤りを除去するための仕組み
この仕組みに基づいて多クラス分類を考える 「誤り訂正出力符号(error correcting output code)」によりより一般的な枠組みを与えられる
2.4.1 クラスラベルの符号化による多クラス分類
各クラスに符号語と呼ばれる異なる数値列が割り当てられている
1か-1の値をとる長さmの符号語を考える
クラス数cに対してそれぞれ符号長mの符号語を作成すると
それらを並べることでcxmの符号化行列と呼ばれる行列Sが得られる
例:0~9までの手書き数字の認識問題
符号化行列Sの例
かく数字が持つ形状的な特徴により符号を割り当てる
符号化行列の列(m個)をラベルyiとする
M個の2クラス分類の学習
ある入力xに対するm個の決定関数をf1(x),…,fm(x)として
Sのどの行(どのクラスの符号語)に近いかで割り当てるクラスを決定する
近さの判定としてハミング距離に対応したものを考える
全く同じでなくても近いものが選ばれる
1対多、1対1方式との対比
符号化アプローチはより一般的なものとなる
2.4.2 ペアワイズカップリングとの併用
符号化アプローチのペアワイズ法との組み合わせ
2.5 多クラス問題の同時定式化
SV分類の定式化そのものを多クラス化するアプローチ
双対問題
決定関数数
変数の数が増えるため、計算に時間がかかる

第3章　回帰分析

3.1 回帰問題
回帰問題とは出力が実数値になっている問題
例 :金融商品の価格を予測する
新薬を服用した人の血圧を予測する
SV回帰を用いると非線形なモデルに基づく予測ができる
3.2 最小二乗法と最小絶対誤差法による回帰
最小二乗法
最小二乗法では、 実際の出力値yiとモデルの予測値の二乗誤差の和が 最小となるようにモデルパラメータwとbを決定する
最少二乗法は上式のRStanとして定式化される
最少二乗法における誤差を絶対誤差に置き換えたもの
定式化
最小二乗法と最小絶対誤差法の損失関数
最小二乗法と最小絶対ごさほうの相違点
最小二乗法の解は線形方程式を解くことにより解析的に求められる 最小絶対誤差法は線形計画問題として定式化されるため何らかのアルゴリズムを使って解く必要がある
ノイズ項zが正規分布の時最小二乗法は最尤推定法と一致する ノイズがラプラス分布の時は最小絶対誤差法と一致する
最小二乗法は条件付き分布p(Y|x)の平均の推定量 最小絶対誤差法は条件付き中央値の推定量
最小二乗法は異常値やはずれ値の影響を受けやすく、最小絶対誤差ほうは異常値に対してロバストである
3.3 SV回帰の定式化
3.3.1 SV回帰の損失関数
3.3.2 SV回帰の主問題
3.3.3 SV回帰の双対問題
3.4 SV回帰による非線形モデリング
カーネル関数を使うことで非線型モデルに基づく回帰を行うことができる
3.5 SV回帰の性質
3.5.1 スパース性とサポートベクトル
スパース性の高いモデルは、 回帰モデルの評価を高速にでき、 リアルタイム性が必要な応用問題で、 高速に処理できる
3.5.2 SV回帰と最小二乗法・最小絶対誤差法との関係
回帰問題において損失関数を選択することは 背後に想定するノイズモデルを選択すると理解できる
3.6 分位点回帰分析
カーネル分位点回帰

第4章　教師なし学習のためのサポートベクトルマシン

4.1 教師なし学習のタスク
4.1.1 クラスタリング (Clustering)
入力データに潜むグループ構造を密れるための手法
目的
分析の前処理としても使われる
よく使われる手法
K平均法 (K-means method)
拡張
マージン最大化クラスタリング (Large margin clustering)
クラスタリングにマージン最大化の概念を取り入れたもの
カーネルk平均法 (Kernel k-means method)
K平均法にカーネル関数を導入して非線型なクラスタリングを可能としたもの
4.1.2 次元削減 (Dimensionarlty reduction)
高次元データを低次元データに変換すること
次元削減の目的
データの前処理として使う
ノイズ除去
データ圧縮
よく使われる手法
主成分分析 (Principal component analysis)
データの線形変換により次元削減を行う
データのばらつきが最も大きくなるような次元が重要な次元とみなす
固有値問題に帰結して解くので効率的
拡張
カーネル主成分分析 (Kernel principal component analysis)
主成分分析にカーネル関数を導入する
非線型変換による次元削減を行うことができる
教師なし次元削減
教師あり次元削減
4.1.3 異常検知 (Anomaly detection)
新しい事例が与えられたときにそれが正常であるか異常であるかを判定する
学習データとして入力事例のみが与えられている状況では、 どのように「異常」を定義すべきか明確ではない
直感的な解釈
確率的に起こりそうなものを正常
確率的に起こりそうにないものを異常
最もシンプルなものは類似度に基づくアプローチ
多くの事例と似ているものを正常
どの事例とも似ていないものを異常
教師なし異常検知
入力事例のみ与えられている場合
教師あり異常検知
異常値と正常値が与えられている場合
異常であることを陽性、 正常であることを陰性と呼ぶ
正常な事例を異常と誤ることを偽陽性、 異常に事例を正常とすることを偽陰性とよぶ
偽陽性率と偽陰性率のバランスをとることが重要
一般的には偽陽性率が1%とか5%
4.1.4 教師なし学習と確率密度推定
教師なし学習タスクの共通点
入力データ{xi}i∈[n]のデータ発生源に関する推測を行う
入力データ発生源の確率分布がわかれば、全てのタスクを容易にこなすことかできる
入力データが高次元の場合(データに対する知見が少ない)
データはっ゛いげんの確率分布を精度よく推定するのは困難
確率分布を推定せず、目的のタスクを直接行うアプローチが望ましい
データ発生源に対する先見知識が得られていたり、 データそのものに対する説明や解釈が必要な場合
まず、データ発生源の確率分布を推定し
その後、推定された確率分布に基づいて タスクを行うアプローチが取られる
生成モデルによるアプローチ
4.2 1クラスSVM
はじめに
1クラスSVMは、 SV分類のアプローチを 教師なし学習のために使うという観点で考案された方法
教師なし異常検知のアルゴリズムとみなせる
入力値が正常であれば+1、異常であれば-1
学習データとして正常な事例しか与えられない
偽陽性率を制御することも検討する必要がある
4.2.1 1クラスSVMの考え方
1クラスSVMでは、 入力空間の線形モデルをそのまま 異常検知に使うことはない
以下のモデルで考える
特徴空間の線形モデル
Φは入力空間から特徴空間への写像を表す変換
とその双対表現
まず双対表現から議論を始める
1クラスSVMの目的
以下を返す判定規則を見つける
ベクトルxが正常である場合に+1
ベクトルxが異常である場合に-1
学習の目的
未知データに対して、 上記の判定規則ができるだけ正解するような パラメータαを見つけること
4.2.2 1クラスSVMの定式化
1クラスSVMの例

第5章　カーネル関数

5.1 カーネル関数の性質
はじめに
特徴空間Fに写像された特徴ベクトルΦ(x)の内積を カーネル関数K(xi,xj)=Φ(xi)TΦ(xj)に置き換えることで 啓示的にΦ(x)を計算することなく複雑なモデルが実現可能
5.1.1 マーサーの定理
ある関数がカーネル関数であるためには
任意の入力xi,xjに対して
何らかの特徴空間F上の内積Φ(xi)TΦ(xj)と対応している必要がある
特徴ベクトルの空間Xが 有限個の要素しか持たない場合
要素の数をmとするとX=(x1,…,xm)
関数K(xi,xj)の各値を要素とする行列K∈ℝnxmを考える
K(xi,xj)がカーネル関数であるためには
Kが半定正値行列であれば良い
半定正値行列とは
非負の固有値を持つ行列
Kの固有ベクトルを並べた行列を V
固有値λを体格に並べた対角行列をΛとする
固有値分解はK=VΛVTとなる
KのI,j要素であるK(xi,xj)は上式のようになる
Φを定義した場合の内積だと解釈できる
より一般的な無限個の要素を持ちうる 特徴ベクトルの空間Xを考える場合
マーサの定理 (Mercer’s theorem)
5.1.2 カーネル関数への操作
マーサの定理を満たしていれば、 どのような関数でもカーネル関数として用いることができる
基本的なカーネル関数の形と、 カーネル関数から新たなカーネル関数を 導く汎用的な操作を示す
対称半正定値行列Bに対して、 上式はカーネル関数になる
関数g(x)をX上の実数値関数とすると、 上式はカーネル関数になる
K1(xi,xj)とK2(xi,xj)をマーサの定理を満たすカーネル関数 A≥0を任意のスカラー変数とすると 上式は全てカーネル関数となる
続き
カーネル関数による多項式もカーネル関数になる
テイラー展開で任意精度の近似ができる関数であれば、 カーネル関数によって構成される関数は全てカーネル関数になる
5.2 いろいろなカーネル関数
はじめに
カーネル関数を変化させることで、学習されるモデルは全く違ってくる
様々な用途に応じて多様なカーネル関数が提案されてきた
5.2.1 基本的なカーネル関数
非常に頻繁に用いられる 基本的なカーネル関数
線形カーネル
Φ(xi)=xiとした場合に導かれる単純なカーネル関数
多項式カーネル
C:ハイパーパラメータ
d:自然数
非線型なモデルを実現可能
RBFカーネル
γ:ハイパーパラメータ
非線型なモデルを実現可能
5.2.2 確率モデルに基づくカーネル関数
「カーネル関数の設計において 入力空間Xの確率分布を反映して定義する」 という考え方がある
フィッシャーカーネル (Fisher kernel)
パラメータθ=(θ1,…,θγ)Tを持つ生成分布p(x|θ)を考える
分布は任意だが、θに関しては確率密度が微分可能である必要がある
Θは最尤推定などを用いて適当に定めるとする
p(x|θ)の対数確率をθに関して微分した フィッシャースコアと呼ばれる値をUxとして定義する
フィッシャースコアは ある特徴ベクトルxを生成する分布の パラメータθの勾配によって表現している
確率分布のパラメータであるθに対して、 確率モデルのつくる多様体(manifold)上で自然な計量を用いると、 上式のカーネル関数が導かれる
Iθはフィッシャー情報行列 (Fisher information matrix)
確率モデルと軽量の関係に関しては 情報幾何(information geometry) という理論で扱われる
24
フィッシャーカーネルの直感的な解釈
確率分布が指数分布であった場合
密度関数
s(x)はxの関数でθと同じ次元のベクトル
Ψ(θ)はxに依存しない正規化の項
確率密度関数p(x|θ)はs(x)を通してのみ入力xに依存する
s(x)ガ確率密度関数と確率変数の関係を決定づける
s(x):十分統計量 (sufficient statistic)
一般に確率分布のパラメータ推定を行う際には 十分統計量がわかれば良いとされる
指数分布族のフィッシャースコア
フィッシャーカーネルは 隠れマルコフモデルなど より複雑なモデルに対して適用されることが多い
5.2.3 文字列のためのカーネル関数
文字列を入力として持つ問題へのカーネル関数の適用
前提条件
入力空間X、有限長の文字列の集合
文字列を構成する個々の文字は集合Aに含まれる
ある文字列の長さを|s|と表記する
Apとして長さpの文字列の集合を表現する
各種カーネル
P-スベクトラムカーネル
全部分列カーネル
ギャップ重み付き部分列カーネル
2つの文字列が共有する部分列を 数えることでカーネル関数を定義する
数え上げを効率よく行うために 動的計画法に基づく方法がよく使われる
(1) p-スペクトラムカーネル
P-spectrum kernel
与えられた二つの文字列が共有している 長さpの部分文字列の頻度を調べる
部分文字列とは
文字列の中で連続するp個の文字
例
長さp=3の部分文字列
ある部分文字列uの文字列s内での出現回数をΦu(s)と表記する
P-スペクトラムカーネルを定義する写像Φは 全ての長さpの部分文字列に対するΦuを並べることで定義される
(Φu(s))u∈ApはApの各要素uに対するΦu(s)を並べたベクトルとする
(2) 全部分文字列カーネル
All-subsequence kernel
(3) ギャップ重み付き部分文字列カーネル
Gap-weighted subsequence kernel
5.2.4 グラフのためのカーネル関数
グラフの行列での表現
例 :グラフのためのカーネル関数
(1) 頂点間のカーネル
一つのグラフが入力として与えられ、 その各頂点が一つの事例に対応する場合
例:タンパク質のネトワーク上での タンパク質の機能を予測する問題
各頂点に対応するタンパク質の機能カテゴリをラベルとする
機能既知のタンパク質から 機能未知のタンパク質の機能カテゴリを予測する
一つの頂点が一つの事例
任意の二つの頂点に対して定義されるカーネル関数が必要となる
グラフ上での学習を考える場合には
グラフラプラシアン(graph Laplacian)という行列がよく使われる
Dは∑Wを対角要素にもつ対角行列
隣接行列は重みのついたものでも良い
グラスラプラシアンの虹形式を展開すると、 半正定値性が確かめられる
fは任意の実数ベクトル
辺でつながっているiとjに対して Fiとfjの差が小さいほど小さくなる
グラフラプラシアンの二次形式が ベクトルfの各要素fiをグラフの各頂点に対応づけたときに {fi}I∈[n]がグラフ上でどの程度滑らかに変化しているかを表現している
グラフラプラシアンの固有ベクトルを考えることで
グラフ上での滑らかさを表現する成分を抽出することができる
グラフラプラシアンからカーネルを導く場合は
固有値分解からカーネル行列を定義する
I番目の固有値をλi
R:ℝ+ → ℝ+を適当な単調減少関数として
グラフの頂点に関するカーネル行列を 上式のように定義する
関数rは単調減少関数なので
小さい固有値に対応するグラフ上で滑らかな成分ほど カーネル行列に強く影響する
上記のカーネル行列は半正定値で 関数rとして上式がよく使われる
Ε∈ℝ++とσ∈ℝ++はハイパーパラメータ
通勤時間カーネルだけはλ=0に対してrが単調現象ではない
非零の固有値に対応する成分については単調減少となる
グラフラプラシアンについては、 正規化を施した上式が用いられる場合もある
グラフラプラシアンLの対角要素が1に正規化される
(2) グラフ間のカーネル
入力の空間Xの各要素一つ一つがグラフである場合を考える
例:化合物の分子構造をグラフとして表現し 化合物が持つ毒性などの性質を予測する問題
与えられた二つのグラフに対してカーネル関数が準備される必要がある
最も単純な方法
二つのグラフが同型かどうかに基づくもの
グラフの頂点を区別しない場合
添字を並べ替えることで二つのグラフが観世に一致するなら
二つのグラフは同型だと定義
例:特徴写像Φ(G)の要素ΦH(G)として グラフGがあるグラフH∈Xと同型な部分グラフを いくつ含むかを使って定義する方法
この方法では必要な計算量は非常に大きくなる
より簡単に計算できるカーネル関数
グラフ上のウォーク(walk)に基づく方法
グラフ上のウォークとは
グラフ上の辺を辿って歩くようにして移動すること
そのとき通った頂点と辺の列として表現
グラフの頂点と辺にラベルが 付随している場合を考える
例:化合物を構成する分子の種類や結合の種類がラベル
グラフ上のウォークはラベルの列として表現可能
二つのグラフ上のウォークが生成する ラベル系列に対するカーネル関数によって グラフ間のカーネル関数を定義できる
任意のラベル系列をsとし、 グラフGに対する特徴写像Φ(G)を 各ラベル系列に対して定義される 特徴写像ΦS(G)によって構成することを考える
ウォークに依存する重みパラメータλ(w)を導入して ΦS(G)を上式のように定義する
W(G)はグラフGのウォークの集合
s(w)はウォークwの生成するラベル系列
二つのグラフG1とG2に対して、 この特徴写像によるカーネル関数は あるうるラベル系列の集合Sに関する和として 上式として表現可能
整理するとありうるウォークの和として表現することも可能
ウォークは長さに制限がなく無限に存在するため 計算が可能かどうかはλ(w)の決め方に依存する
例えば、λ(w)をs(w)の長さがℓであれば1、そうでなければ0とすると 長さがℓのウォークだけの和となり計算が可能になる
λ(w)をその長さℓが大きくなるにつれて減衰するように設定すると 無限級数が収束する値を計算できる場合もある
グラフ上のウォークに確率的な遷移を導入した “ランダムウォークの概要とアルゴリズム及び実装例“でも述べているランダムウォーク(random walk)をカーネル関数に組み込むことも可能
λ(w)はwのグラフ上の遷移確率に応じて定まる
一連のグラフ上のカーネル計算は入力となる二つのグラフに対して
直積グラフ(direct product graph)という グラフから得られる隣接行列を用いると統一的に表現できる

第6章　最適化概論:最適性条件と汎用的解法

6.1 はじめに
SV分類やSV回帰等の手法は全て 数値最適化(numerical optimization problem) として定式化されている
SVMの場合、 通常は解析的に会を得ることはできず、 適当な初期解から開始して 解を探索する反復計算を行う必要がある
標準的な最適化問題において 解を得るにはどのようにすれば良いのか?
SVMの最適化問題は、 目的関数が凸な2次関数、制約条件が1次間数によって構成される 凸2次最適化問題(convex quadratic optimization problem) という問題として解ける
2クラスSV分類の主問題は上式のように定義される
yiyiK(xi,xj)をI,j要素に持つ行列をQ∈ℝnxnとして定義すると 双対問題は上式のようになる
1は1をn個並べたベクトル
y=(y1,…,yn)T
6.2 最適性条件
SVMの解のSVMを考える上で 重要な役割を果たすもの
強双対性(strong duality)
目的関数と制約条件の式
主問題の表記は上式となる
双対変数をまとめてλ=(αT, μT)Tとすると ラグランジュ関数は上式となる
双対問題の目的関数をD(λ)と表記すると 双対問題は上記で表される
カルーシュ・クーン・タッカー条件 (Karush-Kuhn-Tucker condition)
双対変数による上式の決定関数を用いると 上式のような簡単な条件で表現できる
6.3 汎用的解法
はじめに
連続値の数値最適化においては 勾配に基づいて目的関数を減らす (あるいは増やす)方向に進む以下の手法が一般に使われる
最急降下法 (Steepest descent)
ニュートン法 (Newton method)
SVMの最適化の場合に、 制約条件をどう扱うかを考慮する必要がある
アクティプセット方式 (Active set method)
内点法 (Interior point method)
6.3.1 アクティブセット法
制約付き最適化問題を扱う標準的な解法
最適化問題が複数の不等式を持つとき
多くの場合は、一部の制約では等式が成立する状態になる
等号が成立している不等式制約の集合を アクティプセット(active set)と呼ぶ
SVMでは最適なアクティブセットが判明すれば 最適解を線形方程式で表現することが可能
中略
アクティプセット法では、 適当な初期値を与えて、 アクティブセットを更新する
アルゴリズム
6.3.2 内点法
概要
不等式制約付き最適化問題に対する汎用的解法
実行可能領域の内部を通りながら最適解を目指すことから、内点法と呼ばれる
元々線形計画問題(linear programming problem)の解法として考案された
手法
SVMの主問題に新たな非負変数s=(s1,…,sn)T∈ℝnを導入
上式のように書き換える
元の不等式制約-yi(wTΦ(xi)+b)+1-ξi≤0の左辺に 非負変数siを加えることで等式が成り立つようにしている
この操作は最適解に影響を与えない
この書き換えによって不等式制約が各変数の非負制約飲みになる
この非負制約の代わりに「対数障壁関数(log barrier function)」を導入した問題を上式のように考える
μ>0は性のパラメータ
対数障壁関数
Logの中が0に近づくほど∞に向かう
0以下の値に対して定義されない
対数障壁関数は非負制約の近似
μを0に近づけるほど、元の最適化問題に近づく
内点法は適当な初期値μから始まり、 上式の最適化問題を解き、 μを少しづつ0に近づけていくことで解を得る
最適化問題のラグランジュ関数は上式となる
各変数に関する微分から上式を得る
KKT条件になる
∂L/∂wを使ってwを消去してKKT条件を整理すると 上式になる
Diagは引数にとったベクトルを体格要素に並べた行列
非線形な項を含むため、 一次近似を用いて得のが一般的
内点法によるSV分離最適化アルゴリズム

第7章　分割法

はじめに
SVMのための最適化手法のうち分割法と呼ばれるアプローチを提示
訓練集合全体に対して最適化を行うのではなく、 訓練集合の一部を洗濯して小規模な最適化を繰り返す
手法
SMOアルゴリズム
DCDMアルゴリズム
SVMの学習に特化した最適化により高速化する
双対問題を解くための最適化法
7.1 分割法
SV分類の双対問題ではN個の未知変数{αi}i∈[n]を最適化する
双対問題を効率的につくための基本方針
最終的な分類器がサポートベクトルのみに依存するという事実を利用する
どの訓練事例がサポートベクトルになるのか分かっていれば サポートベクトルのみから構成される一部の訓練集合を訓練事例とみなし 少数規模の最適化問題を解けば良い
最適解を得るまでは どの訓練事例がサポートベクトルになるか 知ることはできない
分割法(decomposition method) またはチャンキング法(chunking method)
サポートベクトルのように分類器への影響が大きいと予測される 一部の訓練事例からなる小さな部分集合を考える
この部分集合に関する小規模な最適化問題を解く
途中で得られる暫定会を用いて部分訓練集合を更新
作業集合(working set)
分割法の各ステップで選択される{αi}i∈[n]の部分訓練集合
作業集合をS⊆[n] 作業集合に含まれるもののみを未知変数とみなす
それ以外をṡ=[n]\Sとする
含まれないものは定数とする
最適化問題の定式
行列Qは(i,j)要素がQi,j=yiyjK(xi,xj)であるnxn行列
行列Q∈ℝnxn
ベクトルα∈ℝn+
ベクトルy∈ℝn
作業集合のみを未知変数とした双対問題も凸二次計画問題となる
作業集合のサイズ|S|が十分小さければ、 内点法やアクティブセット法などを用いて効率的に解ける
7.2 カーネルSVMのためのSMOアルゴリズム
はじめに
分割法の一種であるSMOアルゴリズム (sequential minimal optimization algorithm)の紹介
SMOアルゴリズムは作業集合Sのサイズを|S|=2とした分割法
作業集合のサイズを2とすることの利点
各ステップで解くSに対する双対問題の解を解析的に得られる
内点法やアクティブセット法などのソルバーを使わなくても良い
大規模な問題に対して非常に効率的にSVMの学習を行える
LIBSVMでも使われている
2変数の最適解を解析的に求める方法と2変数を選ぶ方法を順次説明する
線形SVM、カーネル関数K(xi,xj)=xiTxjを用いた場合にはより効率的な分解法がある
7.2.1 2変数の最適化
双対変数{αi}i∈[n]を変数変換して上式とする
ラベルはyi∈{±1}なので、αiとβiは上式の関係にある
変数{βi}i∈[n]を用いるとSV分類の双対問題は上式となる
Kij=K(xi,xj)を表す
SMOアルゴリズムでは、 n個の未知変数{αi}i∈[n]のうち、 異なるに変数βs,βt,s≠tを作業集合とする
なぜ作業集合として 変数を一つではなく二つ選ぶのか
上記の等式条件のため
一つの変数βsを除くn-1個の変数を固定すると
等式を満たすために、βsの値も変えることができなくなる
二つの変数βsとβtを変えることができれば
Βs+βtの値が一定である限り 等式制約を満たすことができる
二つの変数を上式のように更新する場合を考える
等式制約条件を満たすためには、 上式と更新する必要がある
∆βt=-∆βsを満たす必要がある
Βsのみが自由に動ける変数
他の制約に代入してみると
βsに関する制約付き最適化問題として書き直すと
最終解は
7.2.2 2変数の選択
二つの変数βsとβtを選ぶ方法
ランダムに選んだとしてもSMOアルゴリズムは最適解に収束する
うまくβsとβtを選ぶことにより、収束の速さを改善できる
SV分類の最適解では 上式の条件を満たす必要がある
二つのパラメータを選択する基本戦略は、 左の式を最も満たしていないような二つの変数のペアを選択すること
最も最適性条件を満たしていないペアは上式となる
最終的に上式を計算する必要がある
7.2.3 SMO アルゴリズムのまとめ
SV分類のためのSMOアルゴリズム
各ステップでカーネル行列K∈ℝnxnの要素をO(n)個計算する必要がある
カーネル行列の同一要素を何度も計算しないために あらかじめ計算してメモリに保持しておく
大規模データの場合はカーネル行列の一部のみをキャッシュに保存しておく
7.3 線形SVMのためのDCDMアルゴリズム
はじめに
線形SVMに特化した分割法のアルゴリズムを紹介
DCDMアルゴリズム (Dual coordinate descent method algorithm)
LIBLINEARでも使われている
LIBSVMを開発したグループが線形SVMに適用した
SVMの利点の一つはカーネル関数を用いて複雑な特徴を捉えること
有益な特徴量が既に分かっている状況では
線形SVMを用いてカーネルSVMと同程度の性能が得られる場合が多くある
高次元でスパースな特徴を持ったデータ
例:自然言語処理でのある単語が文書に現れるか否か
特徴の次元数は非常に高次元なデータとなる
一方多くの特徴が0になるスパース性を持つ
線形SVMを用いることが有効
7.3.1 線形SV分類
バイアスのない線形モデル
SV分類の主問題は上式となる
双対問題は上式となる
7.3.2 DCDMアルゴリズム
DCDMアルゴリズムは 上記の双対問題を解くアルゴリズム
アルゴリズムの基本方針はSMOアルゴリズムと同じ
最小の作業集合Sに対する最適化を繰り返す
SMOでは2変数からなる作業集合
上式ではスータがないため、 一つの変数αs, s∈[n]を更新することができる
一変数∆αsに関する制約付き二次関数最小化問題
上式のように解析的に解くことが可能
DCDMアルゴリズム

第8章　モデル選択と正則化パス追跡

はじめに
SVMの実応用では、 正則化パラメータなどのハイパーパラメータを 適切に決める必要がある
モデル選択
交差検証法法を利用する
正則化パラメータCを徐々に変化させたときに 最適解がどのように変化するのか追跡
正則化パス追跡法
8.1 モデル選択と交差検証法
SVMのモデル選択と交差検証法について
8.1.1 モデル選択
SVMの実応用では、 正則化パラメータやカーネルパラメータなどの ハイパーパラメータを適切に決める必要がある
モデル選択(model selection)
様々なハイパーパラメータにおけるSVMの学習を行い(最適化問題を解き) どのモデルが良いか選択する
文献[8]の第7章
様々な正則化パラメータCに対する SV分類器の分類境界
Cが小さすぎると「未学習(under-fitting)」
Cが大きすぎると「過学習(over-fitting)」
一般的にはハイパーパラメータの候補をいくつか準備しておいて、 その中から最も良いものを選択する
ハイパーパラメータが一つか二つの時は、
候補となる範囲ほ均等分割し、 そのグリッド店の中から選択する場合もある
ハイパーパラメータ数が多い場合
ランダムに選択する
ベイズ最適化アプローチ
勾配情報を使ったアプローチ
適切なモデルを選択するためには、 分類器の汎化誤差(generalization error)を推定する必要がある
汎化誤差
未知の変数に対する誤差の期待値
8.1.2 交差検証法
訓練データを使って分類器を学習し、 評価データを使って学習された分類器を評価する
利点
訓練データと評価データが異なるので、 過学習の影響を受けにくい
問題点
手元にあるデータの一部しか学習に利用できない
データ数が書くないと分類器の精度は落ちる
交差検証法は上記の問題を解決するための方法
交差検証法のイメージ図
分割数kにおける交差検証法をk分割交差検証法 (K-fold cross-validation)
一般にはk=5,10などとすることが多い
手順
手元にnall個の訓練事例からなるデータ集合があるとする
K分割交差検証法では、 Dallをk個の重複のない部分集合D1,…,Dkにランダムに等分割する
K回の学習と評価を行う
K分割交差検証法による汎化誤差の推定値は上式となる
Dkに含まれる事例以外を訓練集合として学習した分類器をg(-Dk)と表す
正則化パラメータに関するモデル選択では、 様々なCに置いて上式を計算して、 最小となるものを選択する
一つ抜き交差検証法 (Leave-one-out cross-validation)
K分割交差検証法のkをnallとした極端なもの
交差検証法は大規模データでは 計算コストが問題になる
逐次学習のアプローチで効率的に行う
8.2 正則化パス追跡アルゴリズム
8.2.1 正則化パス追跡アルゴリズムの概要
SV分類のための正則化パス追跡アルゴリズム
SV分類の双対問題を解く際に利用されることが多い
決定関数の双対表現と双対問題について
SV回帰の決定関数は、 カーネル関数Kと双対変数(α,b)を用いて 上式のように表される
左式の行列やベクトルを用いて、 SV分類の双対問題は上式のように変形される
正則化パス追跡アルゴリズムを導入するための準備として、 上式の行列とベクトルを定義する
0,1は全ての要素が0または1のベクトル
二つのベクトルに関する不等号はその全ての要素に対する不等号
双対変数の最適解が 正則化パラメータCにおけるものである ことを明記するためにα*(C)と表す
正則化パス追跡アルゴリズムでは、 正則化パラメータCを徐々に大きくしていった時、 集合{O,M,I}がどのように変化していくかを追跡する
SV分類の双対問題では、 集合{O,M,I}が基地であれば、 最適解(α*(C),b*(C))をCの関数として 解析的に求めることができる
正則化パス追跡アルゴリズム
ステップ1
固定された集合{O,M,I}の元、 最適解(α*(C),b*(C))を正則化パラメータCで パラメータ表現された形で求める
ステップ2
正則化パラメータCを変化させた時、 集合{O,M,I}が変化するイベントを検出する
8.2.2 最適解のパラメータ表現(ステップ1)
集合{O,M,I}が既知
双対問題の最適解(α*(C),b*(C))を 正則化パラメータCでパラメータ表現した形で求める
最適解において、 最適性条件は上式のように表される
3行目から4行目に関しては上式の性質を用いる
集合Mに含まれる全ての要素を並べ、 最適性条件を整理すると上式のようになる
行列やベクトルを使った最適性条件
最適性条件をまとめると上式になる
|M|+1個の未知数(α*M(C),b*(C))を持つ線形方程式となる
(|M|+1)x(|M|+1)の行列が
逆行列A-1を持てば、 双対変数(α*M(C),b*(C))を上式のように求めることができる
8.2.3 イベント検出(ステップ2)
正則化パラメータCを徐々に増やしていった時、 最適解を特徴付ける集合{O,M,I}が変わるイベントを検出する
考える必要のある4つのイベント
4つのイベントが起きるCの値を 上式のように検出することができる
8.2.4 正則化パス追跡アルゴリズムの区分線形性
SV分類の正則化パス追跡アルゴリズム
ある小さなCminにおける最適解(α*(Cmin), b*(Cmin))が得られているものとする
C∈[Cmin,∞)における最適解のパスを求める
8.2.5 数値計算と計算量
8.2.6 正則化パス追跡アルゴリズムの例
混合正規分布を用いて人工的に生成した n=100,d=2の調練集合と様々なCにおける SV分解器の分類境界の例
生成された区分線形パス

第9章　逐次学習

9.1 はじめに
訓練に用いるデータ集合に変化があった場合、 それに伴って最適解を計算しなおす
逐次学習 (Incremental decremental learning)
すでに得られている解を利用することで効率的に新しい最適解を計算する
例:新しい計測情報などが得られるたびに適時データを追加してモデルを更新する
時系列のデータについての新しいものが入ると同時に古い者は削除するケース
データの種類によらず起こりうる例
交差検証法の計算
ほぼ同じデータに対して繰り返し最適化を行う
最適化計算の高速化を行うため
はじめに訓練データでSVMを最適化
評価用のデータを抜いて最適化を行う際には 全体で得られた最適解から逐次学習する
SVMでは、各双対変数αiと事例(xi,yi)に対応関係があるため
事例の追加や削減を行うことは 双対変数の追加や削減を行うことに対応する
SVMでは非サポートベクトル(αi=0となる事例i)は解に影響を与えない
そのような事例は訓練データに追加しても削除しても影響を与えない
新しい事例(xi,yi)に対するαiは事前にはわからない
現在の解によってyif(xi)≥1となった場合
αi=0とすることでKKT条件を満たす
更新する必要がない
「オンライン機械学習」とは異なる概念
オンライン機械学習ではデータは増えるだけで、削除は考えない
多くの場合はそれまでのデータは保持せずに、 新しい分類器と新しい事例のみを使って更新する
9.2 ウォームスタート
ウォームスタート (warm start)
ある最適解を解く時に、 それと似た最適問題の解を初期解として 最適化を行い高速化を図る
ホットスタート(hot start)とも呼ばれる
現在得られている最適な双対変数をα0∈ℝnとする
事例を追加する場合、 双対変数の初期値としてα0を直接使う場合
例
K個の事例が追加され、 n+k次元の新たな双対変数α∈ℝn+kの末尾k個が この新しい事例に対応する
ベクトルα=(α0T,0,…,0)Tを初期値に加えることができる
事例を削減する場合、
後で・・・・
9.3 アクティブセットに基づく方法
はじめに
逐次学習の異なるアプローチ
初期の最適解から新しい解へアクティブセットの変化を監視しながら更新する方法
9.3.1 更新方向の導出
9.3.2 イベント検出
アクティブセットに基づく逐次学習アルゴリズム

第10章　サポートベクトルマシンのソフトウェアと実装

10.1 統計解析環境Rを用いたSVM
はじめに
統計解析環境Rのkernlabパッケージ
10.1.1 SV分類
2クラスSV分類のベンチマークデータとして “mlbench”というパッケージに用意されている “circle”データを利用する
10.1.1 SV分類
10.2 LIBSVMソフトウェアの実装
10.3 LIBSVMのアルゴリズムの流れ
10.3.1 初期化
10.3.2 停止条件
10.3.3 シュリンキング
10.3.4 第二作業集合の選択

第11章　構造化サポートベクトルマシン

11.1 はじめに
予想される対象となる変数yが単純な数値ではなく、構造を持つような場合を扱う
構造化データは、
例えば木構造や配列として表現されたデータ
自然言語処理における公文予測では各単語館の文法上の関係が木構造として表現される
タンパク質の類似配列検索の問題では、タンパク質をアミノ酸の配列として表現する
例:構文木の予測を考える
Fruit flies like a banana に対する2種類の構文木
入力空間をX、出力となる構造型データの空間をYとすると
構造のあるデータを予測する問題
x∈Xからy∈Yを返す関数g:X→Yを学習する問題と捉えられる
入力x∈Xに対して、ある出力y∈Yがどの程度適合しているかを評価する関数をf:XxY→ℝとする
予測モデルg(x)は上式となる
Yの空間が膨大になることが多く、最適化計算が難しい
構造化サポートベクトルマシン (structural support vector machine)
出力変数が構造を持つ問題に対して最大マージンの考え方を適用する
Yの要素の多さによって増えてしまう制約条件を 「切除平面法(cutting plane method)」により効率的に行う
11.2 結合特徴ベクトル空間における最大マージン
xとyの組み合わせによって定められるベクトルΨ(x,y)を考える
その線形関数としてf(x,y)ほ上式のように考える
ベクトル𝛙(x,y)を結合特徴ベクトルと呼ぶ
結合特徴ベクトルの例
ある事例iについて、 正しい予測を行うには上式の不等式が成り立つ必要がある
Y\yiは集合Yからyiを取り除いたもの
新たにベクトル𝝳Ψi(y)=Ψ(xi,yi) – Ψ(xi,y)を 定義すると不等式は上式のように変形できる
𝝳Ψi(y)を特徴ベクトルとみなすと、 上式のようなマージン最大化問題を定式化できる
通常のSVMと同様に、 変数を書き換えると上式を得る
この式では全てのyiが予測できる仮定になるので、 ソフトマージンと同様の緩和を入れて上式にする
通常のSVMと同じく凸2次最適化問題を解くため、 双対問題を導出する
ラグランジェ関数
主変数に対する微分から得られる式
上の2つの式から双対問題を上式のように導く
行列Qの要素を整理
Qはカーネルによって上式のように表現できる
11.3 最適化法
はじめに
切除平面法と呼ばれる最適化法
一度に全ての制約条件を取り扱うことを避け、 現在の会において最も違反している制約を順番に追加する
一部の制約のみの追加で最適化できる
11.3.1 単一スラック変数による定式化
11.3.2 切除平面法
切除平面法に基づく、 構造化SVMの計算手続きのアルゴリズム
Coche-Kasami-Younger(CKY)アルゴリズムを使った構文木予測
11.4 損失関数の導入
11.5 応用例:ランキング学習
構造化SVMの応用例としての 「ランキング学習(learning to rank)」
検索語(query)となんらかのアイテム集合(主に文書集合)が与えられた時に
アイテム集合を検索語への関連の高い順に並べ替える問題
ランキングを行う関数はg:X→Yと表現できる
文書diの集合(コーパス)をC={d1,…,d|C|}とする
Cに含まれる文書に対するあり得るランキングの空間をYとする
一つの検索語に対して、 各文書には検索語に対する関連の有無が ラベルとして{1,0}で与えられる
APは上式で表現される
ランキングの評価基準として 平均適合率(average precision:AP)を利用する
検索のランキング(並び順)をπ、推定されたランキングをπ’とする
それぞれi番目にランキングされた 文書の検索語への関連度{0,1}をr(πi),r(π’i)と表記する
Prec@jは上式で定義される
推定されたランキングπ’において j位以上に関連のある文書がいくつあるかを表す
APから上式のように損失関数を定義する
π(y),π(ŷ)をそれぞれy,ŷ∈Yが作るランキングとする
複数の検索語に対してAPを計算し、 平均をとった値をMAP(mean average precision)と呼ぶ
構造化SVMの方法に従い、g(x)を上式のように定義する
f:XxY→ℝを結合特徴ベクトルの線形モデルを使う
yはランキングをペア間の関係として行列表現する
Yを|C|x|C|の行列とし、 diがdjより高い順位にランキングされている場合に1、 低い場合であれば-1

第12章　弱ラベル学習のためのサポートベクトルマシン

12.1 はじめに
入力特徴xと出力ラベルyを考える
出力ラベルが部分的に不十分な場合にどうすれば良いのか?
弱ラベルデータ (weakly labeled data)
様々な形式
訓練事例のうち、 ごく一部のものだけに入力特徴xと出力ラベルyのペアが与えられ 残りの大部分は入力特徴xのみが与えられる場合
ここの事例ではなく事例の集合にラベル情報が与えられている場合
一般画像に人が写っているかを判定する問題
セグメンテーションなどの前処理によってここのオブジェクトを抽出
そのオブジェクトを事例とする
半教師あり学習 (Semi-supervised learning)
memo
https://products.sint.co.jp/aisia/blog/vol1-20
教師あり学習と教師なし学習の比較
半教師あり学習のモデル
分類器に基づく手法 (ブートストラップ法(Bootstrap))
ブートストラップとは「自動・時給」の意味
子供が自分で犬や猫を学習していくのと似たモデル
2つのの手法がある
分類器が一つの自己訓練(Self Training)
分類器が複数の共訓練(Co-Training またはMultiview)
古くからあるルールベースの分類法
出会った相手を次々に仲間にしていく
フロー
半教師ありSVM
自己訓練(self training)
例:教師ありデータのみ
教師ありデータと教師なしデータ
高信頼度のデータにラベルつけ
共訓練(Co-Training)
分類器を2つ使う
例:Webページを分類するのに
書かれてある文書を素性とする分類器(view1)
ハイパーリンクの文字を素性とする(view2)
トランスダクティブ学習(transduction learning)と帰納的学習(inductive learning)
アクティブラーニング
データに基づく手法 グラフベースアルゴリズム
半教師ありk近傍グラフ(semi-supervised k-Nearest Neighbor)
ラベルありデータを中心にラベルなしデータをk個含まれる縁を描き、 その範囲に含まれたデータを同じラベルにする
半教師あり金剛ガウスもでる
近さを確率計算で求めるもの
12.2 半教師あり学習のためのSVM
はじめに
S3VMではラベルなしデータも考慮して、 出来るだけ決定境界がラベルなしデータの上を通らないようにする
Introduction to Semi-Supervised Learning (Synthesis Lectures on Artificial Intelligence and Machine Learning)
Semi-Supervised Learning (Adaptive Computation and Machine Learning series): Adaptive Computation and Machine Learning series
http://yamaguchiyuto.hatenablog.com/entry/machine-learning-advent-calendar-2014
12.2.1 半教師あり2クラス分類問題
半教師あり学習のためのSVM
半教師あり 2つクラス分類問題の定式化
ラベルのある訓練事例
ラベルあり事例
ラベルのない訓練事例
ラベルなし事例
入力をxi∈ℝd, I∈L∪U
出力をyi∈{-1,+1},i∈Lとする
12.2.2 半教師ありSVM
12.2.3 半教師ありSVMの非凸最適化
12.2.4 半教師ありSVMの例
図
12.3 マルチインスタンス学習のための SVM
12.3.1 マルチインスタンス学習とは
ここの訓練事例にラベルが与えられているのではなく、 バッグと呼ばれる訓練事例の集合に与えられる
バッグは複数の事例(インスタンス)から構成される
あるバッグに正事例が一つでも含まれていれば、 そのバッグを正バッグと呼ぶ
正バッグの中でどれが正事例でどれが負事例かわからない
正バッグ含まれる事例のラベルを推定しつつ、分類境界を求める
ある事例に含まれている事例が全て負の場合は、負バッグと呼ぶ
マルチインスタンス学習の例
赤で表される正バッグが3つ
赤の中には負もいる
青で表される負バッグが2つ
青は全て負であることはわかる
適用領域
薬として作用する分子を同定する薬剤活性分析
個々の分子をバッグ
分子に含まれる部分構造を事例
タンパク質と結合する部分構造を正事例
結合しない部分構造を負事例
タンパク質と結合する部分構造を持ったぶんしを正バッグ
結合しない部分構造のみからなる分子を負バッグ
画像処理
複数のオブジェクトの中で特定のオブジェクトが含まれているかどうか
例:人かどうか
12.3.2 マルチインスタンス SVM
はじめに
分類例
(1) mi-SVM
全ての事例のラベルを推定し、各事例に対して推定されたラベルに基づいて学習を行う
アルゴリズム
(2) MI-SVM
各バッグの代表事例を決め、代表事例とバッグのラベルを用いて行う
アルゴリズム