機械学習における非凸最適化問題に対するパラメトリック計画法を用いたアプローチ (最適化手法の理論と応用の繋がり)

機械学習における非凸最適化問題に対する

パラメトリック計画法を用いたアプローチ

名古屋工業大学・工学研究科・竹内

一郎

Ichiro Takeuchi

Department

of Engineering,

Nagoya

Institute

of

Technology

名古屋工業大学・工学研究科・小川

晃平

Kohei

Ogawa

Department

of Engineering,

Nagoya

Institute

of

Technology

東京工業大学大学院情報理工学研究科・杉山

将

Masashi

Sugiyama

Department of Computer Science,

Tokyo Institute of Technology

概要

本研究ではさまざまな機械学習問題に共通して現れる非凸最適化問題を考察し，パラ

メトリック計画法を用いた最適化アルゴリズムを提案する．提案アルゴリズムは問題 に含まれるハイパーパラメータを連続的に変化させたときの局所最適解のパスを計算 することができる．これらの問題は局所最適解のパスが不連続点を持つという特徴が あるが，局所最適解の性質を詳しく調べることにょりこの問題に対処する．本稿では 半教師あり学習を例としてこのクラスの問題の性質を議論し，数値実験にょり提案ア ルゴリズムの有効性を検証する．

1

はじめに

本稿では，半教師あり学習やロバスト学習などのさまざまな機械学習問題に共通して現

れる非凸最適化問題を考察する．これらの問題の学習アルゴリズムは，

minimize (convex function) $+\theta$ (non-convex function) (1)

という形式の最適化問題として定式化される．ここで，

$\theta\geq 0$ はモデル選択にょり決定さ

れるハイパーパラメータである．例えば，半教師あり

SVM [1] _{と呼ばれるアルゴリズムは，}

るため，(1) の形式となる．半教師あり SVM の場合，ハイパーパラメータ $\theta$ はラベルなし インスタンスの重要度を決める役割を担い，汎化性能が高くなるような値がモデル選択に より決定される (詳しくは2節を参照). これらの非凸最適化問題においては，よい局所最適解を求めることが現実的な目標とな る．(1) の形式で表される問題では，$\theta=0$ の場合に凸最適化問題となる．このため，まず， $\theta=0$ の最適解を求め，$\theta$ を徐々に増やしながら局所最適解の系列を求めていくアプロー チ [2]

_{が有効である．このようなアプローチはアニーリング法}

[2] の一種と捉えることが でき，$\theta$ はアニーリングパラメータと呼ばれる．

本研究では，このクラスの問題に対し，パラメトリック計画法

[3] を用いた新しいアル ゴリズムを提案する．パラメトリック計画法とは，パラメータ表現された最適化問題にお いて最適解のパスを計算する方法である．提案アルゴリズムを用いると，$\theta$ を $0$から連続 的に増やしたときの局所最適解のパスを計算することができる．このプロセスは凸最適化 問題$(\theta=0)$ を非凸最適化問題へ連続的に変形しながら解の変化を追跡していくものであ り，無限小のステップ幅を持つアニーリング法と解釈できる．

機械学習では，正則化パス追跡

[4,5] の文脈で凸パラメトリック計画法が使われている． 提案アルゴリズムはこれを非凸最適化問題に適用するために拡張したものであるが，前者 は大域最適解のパスを，後者は局所最適解のパスを計算するという点で違いがある．前者 ではどんな最適化アルゴリズムを用いても同一の解が得られるが，後者では一般に異なる 局所最適解が得られる． アニーリング法では，アニーリングパラメータのステップ幅を小さくするほどよい解を 見つける可能性が高いと言われている [7]. ステップ幅を大きくしてしまうと離れた局所 最適解へ移動する可能性が高まるためである．提案アルゴリズムは無限小ステップ幅のア ニーリング法であるため，従来の最適化アルゴリズムよりもよい局所最適解を得られると 期待できる．また，ハイパーパラメータ $\theta$

の刻み幅を小さくしてモデル選択を行えば，よ

り正確なモデル選択を行えるという利点も持つ．従来法ではパラメータのステップ幅と計 算コストはトレードオフの関係にあったが，提案法は無限小ステップ幅のアニーリング法 を行うためこのトレードオフを解消することができる．

局所最適解パスを求めるアルゴリズムの構築に際して，局所最適性条件

(局所最適解の 必要十分条件) を導出する必要がある．この条件を詳しく調べると，このクラスの問題で は，局所最適解のパスが有限個の点で不連続となることが証明される．本研究の技術的な

貢献のひとつは，パスがどのような状況で不連続となるかを明らかにし，そのような場合

に局所最適解を見つける方法を構築することである． 本稿では，非凸最適化問題の例として，主に，半教師あり SVM を考察する．第 2 節で半 教師あり SVM とロバスト SVM _{[6] を定式化し，両者が同じような形式の非凸最適化問題} として定式化されることを示す．第

3

節では，半教師あり SVM の局所最適性条件を求め， 局所最適解の性質を議論する．第 4 節では，局所最適性条件に基づいて局所最適解パスを 計算するアルゴリズムを構築する．第

5

節では，ベンチマークデータに対する数値実験を 行い，最適化性能，汎化性能，計算コストの観点から提案アルゴリズムの有用性を議論する． 本稿では以下の表記を利用する．$\mathbb{R}$

を実数集合とし，$n$ 次元縦ベクトルを $v\in \mathbb{R}^{n},$ $n\cross m$

行列を $M\in \mathbb{R}^{n\cross m}$

などと表す．また，

_$n$ までの自然数の集合を_{$\mathbb{N}_{n}:=\{1,2, \ldots, n\}$} と表す．

$\mathbb{N}_{n}$ の部分集合を $\mathcal{A}$

ベクトルを表す．同様に，

$M_{\mathcal{A}\mathcal{B}}$

は，

に含まれる行と $\mathcal{B}$ に含まれる列を持つ$M$ _の部分行 列を表す．

2

機械学習における非凸最適化問題

本節では，まず，準備としてサポートベクトルマシン

(SVM)

_{を解説する．続いて，本稿}

で主に考察する半教師あり SVM

_{を非凸最適化問題として定式化する．さらに，ロバスト}

SVMについても簡単に紹介し，半教師あり SVM とほぼ同一の構造を持った非凸最適化問 題となっていることを示す．

2.1

サポートベクトルマシン

_(SVM)

2

_{クラス分類問題を考え，学習データを}

$\{(x_{i}, y_{i})\}_{i\in \mathbb{N}_{n}}$

とする．ここで，

$x_{i}\in \mathcal{X}\subseteq \mathbb{R}^{d}$ は

領域$\mathcal{X}$

からの入カベクトル，

$y_{i}\in\{\pm 1\}$

は出力ラベルを表す．識別関数を

$f(x)=w_{0}+w^{T}\phi(x)$ ₍₂₎

と表す．ここで，

$\phi$ : $\mathcal{X}arrow \mathcal{F}$ はカーネル関数$k$ : $\mathcal{X}\cross \mathcal{X}arrow \mathbb{R}$ にょって定義される特徴写

像を表し，上付きの $T$ は行列やベクトルの転置を表す． SVMは識別関数(2)

_{を学習するアルゴリズムであり，以下のような凸最適化問題として}

定式化される: $\min_{f}\frac{1}{2}||w||_{2}^{2}+C\sum_{i=1}^{n}[1-y_{i}f(x_{i})]_{+}$. (3)

ここで，

$C>0$

_{は正則化項と損失項のバランスと制御するための正則化パラメータ，}

$[z]_{+};=$ $\max(O, z)$ _{はヒンジ損失と呼ばれる損失関数である．} 最適化問題(3) の双対問題は $\max_{\{\alpha_{i}\}_{i=1}^{n}}$

$- \frac{1}{2}\sum_{i\in \mathbb{N}_{n}}\sum_{j\in \mathbb{N}_{n}}\alpha_{i}\alpha_{j}Q_{ij}+\sum_{i\in \mathbb{N}_{n}}\alpha_{i}$ subject to

$\sum_{i\in \mathbb{N}_{n}}y_{i}\alpha_{i}=0,0\leq\alpha_{i}\leq C,$

$i\in \mathbb{N}_{n}$

と表される．ここで，

$Q_{ij}=y_{i}y_{j}k(x_{i}, x_{j}),$$(i, j)\in \mathbb{N}_{n}\cross \mathbb{N}_{n}$,

である．双対変数を用いると

(2) は

$f(x)=w_{0}+ \sum_{i\in \mathbb{N}_{n}}\alpha_{i}y_{i}k(x, x_{i})$ (4)

2.2

半教師あり

SVM(

$S^{3}VM$

:

semi-supervised SVM)

半教師あり学習ではラベルありデータに加えてラベルなしデータを学習に利用する．前

者のデータのインデックスの集合を $\mathcal{L}$, 後者のものを$\mathcal{U}$ とすると，ラベルありインスタン

ス $\{(x_{i}, y_{i})\}_{i\in \mathcal{L}}$ とラベルなしインスタンス $\{x_{i}\}_{i\in u}$が学習データとして与えられることに

なる．ラベルなしインスタンスのラベルは未知であるので，予測ラベル

$\hat{y}_{i}\in\{\pm 1\},$$i\in \mathcal{U}$

も同時に学習する必要がある．以後，半教師あり学習について述べる際には，

$P=|\mathcal{L}|$, およ び，$u=|\mathcal{U}|$ とし，$x\in \mathbb{R}^{\ell+u}$ の初めの$\ell$

個の要素がラベルありインスタンス，残りの $u$ 個

の要素がラベルなしインスタンスであるとする．また，

$y=[y_{1}, \ldots , y_{\ell}]\in \mathbb{R}^{\ell}$ をラベルあり インスタンスのラベル，$\hat{y}=[\hat{y}_{p+1}, \ldots,\hat{y}_{\ell+u}]\in \mathbb{R}^{u}$ をラベルなしインスタンスの予測ラベ ノレとする．さらに，$y$ と $\hat{y}$ を並べたベクトルを $\tilde{y}\in\{\pm 1\}^{\ell+u}$ とする．

SVM を半教師あり学習の枠組へ拡張したものとして半教師あり SVM$(S^{3}VM$:

semi-supervised SVM) と呼ばれる手法が提案されている [1]. $S^{3}VM$ _{の学習は以下の最適化}

問題として定式化される [7]:

$\min_{f,\hat{y}\in\{\pm 1\}^{u}}J(f,\hat{y})\equiv\frac{1}{2}||w||_{2}^{2}+C\sum_{i\in \mathcal{L}}[1-y_{i}f(x_{i})]_{+}+\theta C\sum_{i\in u}[1-\hat{y}_{i}f(x_{i})]_{+}$ (5)

ここで，

$\theta\in[0,1]$

はラベルなしインスタンスの影響を制御するパラメータである．

$\theta=0$ のときはラベルなしインスタンスを無視するため，ラベルありインスタンスのみを用いた 通常の _{SVM と等価なものとなる．一方，}$\theta=1$ _{のときはラベルありインスタンスとラベル} なしインスタンスが同程度の影響を持つことを意味する．不確かさを持つラベルなしイン スタンスの影響力はラベルありインスタンスよりも小さいか等しくあるべきなので，$\theta$ は [0,1] の範囲をとる． 分類境界$f$が与えられているとき，予測ラベルは

$\hat{y}_{i}f(x_{i})\geq 0, \forall i\in \mathcal{U}$ (6)

を満たすように決めることが妥当である．このため，

$S^{3}VM$_{の学習は最適な}$\hat{y}\in\{\pm 1\}^{u}$ を

求める組み合わせ最適化問題

$\min_{\hat{y}\in\{\pm 1\}^{u}}$

{

$\min_{f}J(f,\hat{y})$ subject to

(6)}

(7)

とみなすこともできる．

また，制約

(6) のもとでは (5) の右辺第 3 項を $C \theta\sum_{i=1}^{n}[1-|f(x_{i})|]_{+}$ と書けることに留

意すると，S$3VM$_の学習は

$\min_{f}\frac{1}{2}||w||_{2}^{2}+C\sum_{i\in \mathcal{L}}[1-y_{i}f(x_{i})]_{+}+C\theta\sum_{i\in u}[1-|f(x_{i})|]_{+}$ (8)

と書くこともできる．この目的関数の第

3

項は図l(a) のような非凸関数であるので，$S^{3}VM$

の学習は非凸最適化問題とみなすこともできる．

最適化問題(5) _{はすべてのラベルなしインスタンスを同一のクラスヘ分類する，すなわ}

ような不適当な解を回避するため，通常，予測ラベルのバランスに関する制約が導入され

る．文献

[1]ではラベルなしインスタンスのクラス比率がラベルありインスタンスと等し

いという制限が導入されている．その後，文献

[8]ではこの制限を緩和して

$\frac{1}{u}\sum_{i\in \mathcal{U}}f(x_{i})=2r-1$ (9) を制約として加えることが提案されている．ここで，$r$ はラベルありインスタンスのクラ

ス比率で，

$r= \frac{1}{\ell}\sum_{i\in \mathcal{L}}\max(0, y_{i})$ と計算される．この制約はバランス制約と呼ばれ，

(9)

は

線形制約であるため最適化問題へそのまま導入することができる．ここで

$\rangle$ 全ラベルなし インスタンスを $\sum_{i\in u}x_{i}=0$ と中心化すると， $\frac{1}{u}\sum_{i\in \mathcal{U}}(w_{0}+w^{T}x_{i})=w_{0}=2r-1$, (10) となり，識別関数の $w_{0}$ を固定することによってバランス制約を表現可能となる．本稿で も $S^{3}VM$_{の学習において制約}(9) _{を課すこととする．したがって，}

(2)

_{や (4) の識別関数$f$} の定数項$w_{0}$ は (10)

によって固定され，最適化の対象から除外することができる．

2.3

ロバスト

SVM

(R-SVM: robust SVM)

ロバスト学習とは外れ値の影響を軽減するためのアプローチを指す．ロバストなSVM の学習法としてロバスト SVM[6]

が提案されている．ロバスト学習を定式化するため，各

学習インスタンスが外れ値であるか否かを表すフラグ$0_{1}\in\{0,1\},$$i\in \mathbb{N}_{n}$ を定義し，_{$0_{1}=1$}

であればインスタンス $i$ が外れ値であることを表すものとする．ロバスト SVM学習の目 的関数は $\min_{f,0}J(f, 0)\equiv\frac{1}{2}||w||_{2}^{2}+C\sum_{i:0_{i}=0}[1-y_{i}f(x_{i})]_{+}+(1-\theta)C\sum_{i:0_{i}=1}[1-y_{i}f(x_{i})]_{+}$

と表される．ここで，

$\theta\in[0,1]$

は外れ値の影響を制御するパラメータである．

$\theta=0$ _にお

いては外れ値を正常値と同様に扱い，通常の

SVM

と等価になる．一方，

$\theta=1$ は外れ値の 影響を完全に無視することを意味する． 分類境界$f$

が与えられているとき，マージン

$y_{i}f(x_{i})$ の小さなインスタンスを外れ値と みなすことが妥当である．マージンがある定数$s<1$ よりも小さなものを外れ値と定義す る，すなわち，

$y_{i}f(x_{i})\leq s\Leftrightarrow 0_{i}=1$, (11)

とすると，ロバスト

SVM学習は最適な $0\in\{0,1\}^{n}$ を求める組み合わせ最適化問題 $\min_{o\in\{0,1\}^{n}}$

{

$\min_{f}J(f, 0)$ subject to

(11)}

として表される．また，制約 (11) のもとでは，ロバスト SVM の学習は，

$f(x)$ $-1.5$ $-1$ $-0.5$ $0$ 05 15 $y.f(x)$ 図1:(左) 半教師あり SVM におけるラベルなしデータのための非凸損失関数，(右) ロバ スト SVMのための非凸損失関数 と書くこともできる．損失関数$1_{oSS_{robust}}$ は図 1(b) のような非凸関数であるので，ロバス ト SVMの学習は非凸最適化問題とみなすこともできる．

3

S

$3VM$

_{の局所最適解の性質}

前節より半教師あり SVM$(S^{3}VM)$ とロバスト SVM($R$-SVM)の学習は同一の構造を持つ ことがわかる．どちらの問題においても，$\theta=0$ とすると通常の SVM に一致し，$\theta$ を増や すにつれ非凸項の影響が大きくなる．本研究の目的は，$\theta$ を $0$から1へ連続的に動かした ときに局所最適解のパスを計算することである．本節以降では，S$3VM$ _{を例に話を進める} が $R$-SVM についても同様の議論が可能である． 本節では，局所最適解パスを計算する準備として，S$3VM$ _{の局所最適解の必要十分条件} を導出する．凸計画問題では，よく知られた KKT(Karush-Kuhn-Tucker) 条件 [9]が最適

解の必要十分条件となる．一方，非凸最適化問題では，

KKT

条件が局所最適解の (必要条 件であるが)

十分条件であるとは限らない．本節で導出する必要十分条件は，次節で述べ

るアルゴリズムの導出に重要な役割を果たす．

3.1

条件付最適解 S$3VM$ _{を組み合わせ最適化問題と解釈した定式化 (7)}

_{において，内側の最適化問題は以}

下の定義のように凸計画問題となる: 定義1 ラベルなしインスタンスの予測ラベル$\hat{y}\in\{\pm 1\}^{u}$ が与えられたとき，次の凸最適 化問題． $f_{\hat{y}}^{*}$ $:= \arg\min_{f}J(f,\hat{y})$ subject to (6) (12) を $\hat{y}$

が与えられたもとで条件付最適化問題と呼び，その最適解

$f_{\hat{y}}^{*}$ を条件付最適解と呼 ぶ．また，$\hat{y}$ が与えられたもとでの条件 (6) を満たす $f$ の集合は凸ポリトープ (convex

polytope)であり，

$po1_{\hat{y}}:=\{f|\hat{y}_{i}f(x_{i})\geq 0, \forall i\in \mathcal{U}\}$

と表す． 予測ラベル$\hat{y}$ は $2^{u}$ 通りあるので，それぞれに対応する条件付最適解が存在しうる

1.

こ れらの条件付最適解と S$3VM$_{の局所最適解とは以下のような関係がある:} 命題 2 問題 (5) のすべての局所最適解 $f$

は，条件

(6) を満たす予測ラベル $\hat{y}$ のもとでの 条件付最適解である． (証明) ある局所最適解$f$ において条件(6) を満たすように $\hat{y}$

を決め，

_$f$ が$\hat{y}$ のもとでの

条件付最適解でないとする．

$\hat{y}$ を固定した問題(12)

は凸計画問題であるので，polg

上に 条件付最適解$f_{\hat{y}}^{*}$

以外の局所最適解は存在せず，

$f$

が局所最適であることに矛盾する．した

がって，すべての局所最適解が

$\hat{y}$ のもとでの条件付最適解である．(証明終)

一方，ある条件付最適解

$f_{\hat{y}}^{*}$ は制約条件(6)

のもとで最適であるだけで，

$\hat{y}$ を変更すると近 傍によりよい解が存在する場合がある．このため，すべての条件付最適解が局所最適解で あるとは言えない． 条件付最適化問題の双対問題を考えると，条件付最適解を

$f(x)=w_{0}+ \sum_{i\in \mathcal{L}}\alpha_{i}k(x, x_{i})+\sum_{i\in u}\alpha_{i}k(x, x_{i})$ (13)

の形式で表すことができる．命題

2

より，

S

$3VM$ _{の任意の局所最適解も} (13) _{の形式で表さ} れることになる．

条件付最適化問題は凸計画問題であるため最適解の必要十分条件は以下のように表すこ とができる:

補題3ある予測ラベル$\hat{y}$ が与えられたもとでの条件付最適解の必要十分条件は

$y_{i}f(x_{i})>1, i\in \mathcal{L}\Rightarrow y_{i}\alpha_{i}=0$, (14a) $y_{i}f(x_{i})=1, i\in \mathcal{L} \Rightarrow y_{i}\alpha_{i}\in[0, C]$, (14b) $y_{i}f(x_{i})<1, i\in \mathcal{L}\Rightarrow y_{i}\alpha_{i}=y_{i}C$, (14c) $\hat{y}_{i}f(x_{i})>1, i\in \mathcal{U}\Rightarrow\hat{y}_{i}\alpha_{i}=0$, (14d) $\hat{y}_{i}f(x_{i})=1, i\in \mathcal{U}\Rightarrow\hat{y}_{i}\alpha_{i}\in[0, \theta C]$, (14e) $0<\hat{y}_{i}f(x_{i})<1, i\in \mathcal{U}\Rightarrow\hat{y}_{i}\alpha_{i}=\theta C$, (14f)

$\hat{y}_{l}’f(x_{i})\geq 0,\forall i\in \mathcal{U}$, (15)

および，

$\hat{y}_{i}f(x_{i})=0\Rightarrow\hat{y}_{i}\alpha_{i}\geq\theta C, i\in \mathcal{U}$ (16)

である．

補題3は標準的な凸最適化理論 [9]

を用いれば容易に導出が可能なため，証明は省略する．

1 一部の $\hat{y}$ においては制約条件(6) を満たす実行可能解がないことがあり，その場合は条件付最適解が存

在しない．また，条件付最適化問題(12) _{が狭義の凸計画問題でなければ，一つの} $\hat{y}$ に対する条件付最適解が

3.2

局所最適解の必要十分条件

前小節にて，命題

2

の逆は成り立たない，すなわち，条件付最適解であっても局所最適 解であるとは限らないことを述べた．どのような場合にそのような状況となるだろうか． 条件付最適解$f_{\hat{y}}^{*}$ がpol $\hat{y}$

の境界上にある場合を考えてみる．このとき，隣の凸ポリトープ

側の近傍によりよい解が存在する可能性があるため，条件付最適解 $f_{\hat{y}}^{*}$ が局所最適解であ ると断言することはできない．次の定理は隣の凸ポリトープ側に必ずよりよい解が存在す ることを保証するものである: 補題 4 ある予測ラベル$\hat{y}$が与えられたもとでの条件付最適解 $f_{\hat{y}}^{*}$ が$po1_{\hat{y}}$ の境界上にある， すなわち，集合 $\mathcal{S}:=\{i\in \mathcal{U}|\hat{y}_{i}f(x_{i})=0\}$ (17) が空でないとする．ここで，新たな予測ラベル$\hat{y}’$ を

$\hat{y}_{i}’:=\{\begin{array}{l}-\hat{y}_{i}, i\in \mathcal{S},\hat{y}_{i}, i\not\in \mathcal{S}\end{array}$ (18)

と定義する．このとき，任意の

$\theta\in(0,1]$

において，

$f_{\hat{y}}^{*}$

は，

$\hat{y}’$ が与えられたもとでの条件

付最適化問題に関して実行可能解であるが条件付最適解ではない．すなわち，

pol

$\hat{y}’$ 上の

条件付最適解$f_{\hat{y}’}^{*}$ は $po1_{\hat{y}}$ 上の条件付最適解$f_{\hat{y}}^{*}$ よりも厳密によい $S^{3}VM$の解であり，

$J(f_{\hat{y}’}^{*},\hat{y}’)<J(f_{\hat{y}}^{*},\hat{y})$ (19) が成り立つ． (証明)

本補題を証明するため，

$\hat{y}$,

および，

$\hat{y}’$が与えられたもとでの2つの条件付最適化問 題を考え，両者の最適性条件を比較する． 前者の条件付最適化問題はpol$\hat{y}$

上で定義される凸計画問題である．補題

3

より，条件付

最適解$f_{\hat{y}}^{*}$ は (14) と (16) を満たしている．(18)

によりラベルを反転すると，最適性条件

(16) は，$y_{i}’=-y_{i},$$i\in \mathcal{S}$, であるので，

$\hat{y}_{i}’f_{\hat{y}}^{*}(x_{i})=0, i\in \mathcal{U}\Rightarrow\hat{y}_{i}’\alpha_{i}\leq-\theta C$ (20)

と書ける．

続いて，

pol

$\hat{y}’$

上で定義される後者の条件付最適化問題を考える．前者の条件付最適解

$f_{\hat{y}}^{*}$

は$po1_{\hat{y}}$ と $po1_{\hat{y}’}$

の境界上にあるので，後者の凸計画問題の実行可能解でもある．

$f_{\hat{y}}^{*}$ が後者

の凸計画問題の最適解であるためには補題3を満たす必要があるが，(20) より，$\theta\in(0,1]$

のとき，

$\hat{y}_{i}’f_{\hat{y}}^{*}(x_{i})=0, i\in \mathcal{U}\Rightarrow\hat{y}_{i}’\alpha_{i}\geq\theta C$ (21)

を満たすことができない．すなわち，$f_{\hat{y}}^{*}$ は後者の凸計画問題の実行可能解であるが最適解

ではないことになり，(19) が成り立つ．(証明終)

補題

4

より，条件付最適解

$f_{\hat{y}}^{*}$ が凸ポリトープ$po1_{\hat{y}}$

の境界上にある場合，予測ラベルを

(18)

により反転した“隣” の凸ポリトープ上に必ず厳密によい解が存在することがわかった．条

solution space of $f$

図 2: 条件付最適解$f_{\hat{y}}^{*}$ と局所最適解の関係: (左) 条件付最適解$f_{\hat{y}}^{*}$ が凸ポリトープ $po1_{\hat{y}}$

の内点である場合は $S^{3}VM$

_{の局所最適解となるが，}

(

_右

)

_{条件付最適解}

$f_{\hat{y}}^{*}$ が凸ポリトープ $p\circ 1_{y^{-}}$ の境界上にある場合は $S^{3}VM$の局所最適解とはならない．

補題 5 条件付最適解$f_{\hat{y}}^{*}$ が$po1_{\hat{y}}$ の内点にあれば $S^{3}VM$

の局所最適解であり，境界にあれ

ば局所最適解でない．

(証明)解が$po1_{\hat{y}}$ の内点にあればその近傍もすべて $po1_{\hat{y}}$

に含まれるため，

$po1_{\hat{y}}$ 上の極小値

である $f_{\hat{y}}^{*}$

は局所最適解である．一方，補題

4

より，解が

$po1_{\hat{y}}$

境界上にあれば，予測ラベル

を (18) により反転したものに対応する $po1_{\hat{y}’}$ 側の近傍に必ず厳密によい解が存在するた

め局所最適解ではない．(証明終)

以上より，S$3VM$_{の局所最適解の必要十分条件は次の定理のようになる:}

定理 6 $f$ が $S^{3}VM$の局所最適解であるための必要十分条件は，(14), かつ，

$\hat{y}_{i}f(x_{i})>0,\forall i\in \mathcal{U}$ (22)

である． (証明)f が条件付最適解であるための必要十分条件は補題3の条件(14), (15), かつ，(16)

である．一方，

$f$ が $po1_{\hat{y}}$ の内点である条件は (22)

である．補題

5

より，両者を合わせた

(14) と (22) _{が局所最適解の必要十分条件となる．}(_証明終) 図 2 は S$3VM$_{の解空間を模式的に表したものであり，条件付最適解が凸ポリトープの内} 点である場合(左)

_{は局所最適解であるが，境界上にある場合}

(右) は局所最適解でないこ とを例示している．

4

局所最適解パス追跡アルゴリズム

本節では，パラメータ $\theta$ を$0$から1へ連続的に変化させたときの局所最適解のパスを計 算するアルゴリズム ($S^{3}VM^{path}$ _{アルゴリズム})

_{を導入する．このアルゴリズムの構築に際}

Algorithm 1 $S^{3}VM^{path}$

1: Input: ラベルありイ スタ ス $\{(x_{i}, y_{i})\}_{i\in \mathcal{L}}$, ラベルなしインスタ ス $\{x_{i}\}_{i\in u}$, 正則

化パラメータ $C$, カーネル関数$k$

2: ラベルありインスタンスのみを用いて学習した SVM を $f$ とし，予測ラベルを $\hat{y}_{i}arrow$

sgn$(f(x_{i})),$$i\in \mathcal{U}$, とする;

3: $\thetaarrow 0$; 4: while $\theta\leq 1$ do 5: $CP$-phase を実行; 6: $\mathcal{S}arrow\{i\in \mathcal{U}|\hat{y}_{i}f(x_{i})=0\}$; 7: $DJ$-phase を実行;

s:

end while 9: 出力: $\theta\in[0,1]$ における局所最適解のパス しては，前節で導出した S$3VM$_{の局所最適解の性質を利用する．補題 5 より，条件付最適} 解が凸ポリトープの内点である場合は局所最適であり，境界上にある場合は局所最適でな い．したがって，$S^{3}VM^{path}$ _{アルゴリズムでもそれぞれの局面に応じた対処が必要となる．} まず，条件付最適解が$\theta$ のある区間内において1つの凸ポリトープの内点である状況を 考える．このとき，そのポリトープ上で定義される条件付最適化問題は凸であるので，凸 パラメトリック計画法を利用して局所最適解の変化を追跡することができる [10]. この局

面を連続パスフエーズ (continuouspath phase: $CP$-phase) _{と呼ぶことにする．}

一方，局所最適解のパスがある$\theta$ において凸ポリトープの境界に達したとすると，その瞬 間にその解は局所最適でなくなってしまう．$S^{3}VM^{path}$_{アルゴリズムでは，補題}

4

_を利用し てその $\theta$ における局所最適解を求める．(18) による予測ラベル変換を行えば，対応する凸 ポリトープ上によりよい解を見つけることができる．この局面では局所最適解のパスが不

連続にジャンプするため，不連続ジャンプフエーズ

(discontinuos

_ium

$P$ phase: $DJ$-phase)

と呼ぶ． 以下では，連続パスフェーズと不連続ジャンプフェーズを，それぞれ，4.1節と4.2節で 説明する．$S^{3}VM^{path}$_{アルゴリズムの概要をアルゴリズム 1に示す．}

4.1

連続パスフエーズ

連続パスフェーズでは，$\theta$ のある区間内において，条件付最適解が凸ポリトープの内点 である状況を考える．この状況では条件付最適解が $S^{3}VM$_{の局所最適解なので，}$\theta$ の変化 に対する条件付最適解の変化を追跡すればよい．条件付最適化問題は凸二次計画問題であ るので，ここではパラメトリックニ次計画法 [11] を用いる．パラメトリックニ次計画問題 の最適解パスは，パラメータ$\theta$ の区分線形関数となるため効率的に計算できる．

最適解パスを導出するため次の集合を定義する:

$\mathcal{O}:=\{i\in \mathcal{L}\cup \mathcal{U}|\tilde{y}_{i}f(x_{i})>1\},$ $\mathcal{M}:=\{i\in \mathcal{L}\cup \mathcal{U}|\tilde{y}_{i}f(x_{i})=1\},$

(23) $\mathcal{I}_{\ell};=\{i\in \mathcal{L}|y_{i}f(x_{i})<1\},$ $\mathcal{I}_{u}:=\{i\in \mathcal{U}|\hat{y}_{i}f(x_{i})<1\}.$

これらの集合が既知のとき，最適性条件

(14) は $\alpha_{\mathcal{O}}=0,$ $\alpha_{\mathcal{I}_{\ell}}=y_{\mathcal{I}_{l}}C,$ (24) $\alpha_{\mathcal{I}_{u}}=\hat{y}_{\mathcal{I}_{\ell}}C\theta,$ $K_{\mathcal{M}\mathcal{M}}\alpha_{\mathcal{M}}=\tilde{y}_{\mathcal{M}}-1w_{0}-K_{\mathcal{M}\mathcal{I}_{\ell}}1C-K_{\mathcal{M}\mathcal{I}_{u}}1\theta C$

と表される．ここで，

$K\in \mathbb{R}^{(\ell+u)\cross(\ell+u)}$ _{は $(i, j)$ 要素が}

$k(X_{i}, Xj)$

である行列，

_{$0,1$ はすべて}

の要素が，それぞれ，

$0,1$

のベクトルを表す．集合

$\mathcal{O},$$\mathcal{M},$$\mathcal{I}_{\ell},$$\mathcal{I}_{u}$

の要素が変ゎらなければ， $\alpha_{\mathcal{O}},$ $\alpha_{\mathcal{I}_{\ell}}$

は定数，

$\alpha_{\mathcal{I}_{u}}$ は $\theta$

の線形関数である．さらに，

$K_{\mathcal{M}\mathcal{M}}$

が正則ならば，

$\alpha_{M}$ も $\theta$ の線 形関数となる．

集合$\mathcal{O},$$\mathcal{M},$$\mathcal{I}_{\ell},\mathcal{I}_{u}$ の要素が変わらない条件は

$y_{i}f(x_{i})\geq 0, i\in \mathcal{L}\cap \mathcal{O},$ $\hat{y}_{i}f(x_{i})\geq 0, i\in \mathcal{U}\cap \mathcal{O},$ $0\leq y_{i}f(x_{i})\leq 1, i\in \mathcal{L}\cap \mathcal{M},$

(25)

$0\leq\hat{y}_{i}f(x_{i})\leq 1, i\in \mathcal{U}\cap \mathcal{M},$ $y_{i}f(x_{i})\leq 1, i\in \mathcal{I}_{\ell},$ $\hat{y}_{i}f(x_{i})\leq 1, i\in \mathcal{I}_{u}$

と表される．これらの条件が満たされている間は，

$\alpha$ を $\theta$

の線形関数として表すことがで き，(25)

_{のいずれか}

1

_{つの制約がアクティブになった瞬間に集合要素の入れ替えを行う．}

集合要素の入れ替えを行う点はブレイクポイント (breakpoint) と呼ばれる．

Algorithm 2連続パスフレ$-$_{ズ (}$CP$-phase)

1: 入力: 問題パラメ$-$_タ $\theta_{bgn},$ $\theta_{bgn}$ における局所最適解_$f$, 予測ラベル$\hat{y}$

2: $\thetaarrow\theta_{bgn}$;

3: Stepl: (23) に基づいて $\mathcal{O},$$\mathcal{M},\mathcal{I}_{\ell},$$\mathcal{I}_{u}$ を更新;

4: Step2: 線形方程式 (24) を解く (ランク 1更新); 5.: if (25) の制約条件の1_{つがアクティブになれば then} 6: Stepl へ戻る; 7: end if 8: if (6)

_{の制約条件の 1 つがアクティブになる，もしくは，}

$\theta=1$ _ならば then 9; $\theta_{end}arrow\theta$ とし，$CP$-phase を終了する; 10: end if 11: 出力: $\theta\in[\theta_{bgn}, \theta_{end}]$ における局所最適解のパス

パラメトリックニ次計画法は，線形方程式

(24) の計算とブレイクポイントの計算を繰 り返すアルゴリズムである．パラメトリックニ次計画法の計算コストはブレイクポイント 数に依存する．ブレイクポイント数は最悪の場合に問題サイズの指数オーダとなるが通常 は線形オーダであることが実験的に知られている．パラメトリックニ次計画法の各ステッ プでは線形方程式 (24) のランク 1更新の計算コストに大部分の計算資源が費やされるた

め，計算量は

$\mathcal{O}(|\mathcal{M}|^{2})$

である．ブレイクポイント数が線形オーダであれば，総計算コスト

は $\mathcal{O}((\ell+u)|\mathcal{M}|^{2})$

となる．アルゴリズム

2 に $CP$ フェーズの概要を示す．

4.2

不連続ジヤンプフェーズ

連続パスフェーズ ($CP$-phase) _{において局所最適解のパスが凸ポリトープの境界に達し} た瞬間にその解は局所最適でなくなってしまう．そのため，$S^{3}VM^{path}$ _{アルゴリズムは不連} 続ジャンプフェーズ ($DJ$-phase)

_{に移行し，その時点の}

$\theta$ における局所最適解を探す局面 に入る．$DJ$-phase_では補題4_{を利用する．} 境界上のラベルなしインスタンス $S\equiv\{i\in \mathcal{U}|\hat{y}_{i}f(x_{i})=0\}$ の予測ラベルを (18) によっ て反転すれば，新たな予測ラベル$\hat{y}’$ に対する新たな条件付最適化問題を考えることがで

きる．補題

4

より，新たな条件付最適解

$f_{\hat{y}’}^{*}$ は元の条件付最適解$f_{\hat{y}}^{*}$ よりも厳密によい解で

あることが保証される．もし，

$f_{\hat{y}’}^{*}$ が凸ポリトープ$po1_{\hat{y}’}$

の内点にあれば，

$f_{\hat{y}’}^{*}$ はそのときの

$\theta$

における局所最適解となっている．一方，

$f_{\hat{y}’}^{*}$ が$pol_{\hat{y}’}$

の境界上にあれば，

$f_{\hat{y}’}^{*}$ は局所最適

解でない．そのような場合，補題

4

の予測ラベル更新をもう一度適用し，さらに新しい条 件付最適解を計算する．凸ポリトープの内点となる条件付最適解をみつけるまでこの手順 を繰り返すと，局所最適解を見つけることができる． 予測ラベル $\hat{y}$ の取りうる値は有限通りであり，新たな条件付最適解を見つけるたびに $S^{3}VM$_{の解を厳密に改善できるので，}$DJ$-phase _{は有限回で収束する．}$DJ$-phase_では複数 の条件付最適化問題を解く必要があるが，予測ラベルの更新前と更新後の最適解が近い

ことに留意すると，前者から後者を容易に求めることができる．予測ラベル更新前の解

$\{\alpha_{i}\}_{i\in \mathcal{L}\cup u}$

のうち，

$\mathcal{S}$

に対応するものは更新後の問題の最適性条件を満たしていないが，残

りの$\mathcal{L}\cup\overline{S}$ に対応するものは既に更新後の問題の最適性条件を満たしている．アルゴリズ

ム 3 に $DJ$-phaseの概要を示す．

Algorithm 3不連続ジャンプフエーズ ($DJ$-phase)

1: 入力: 問題パラメ$-$_タ $\theta,$ $\theta$ における (局所最適でない)解_$f$, 予測ラベル$\hat{y}$, アクテイブ

集合$S\equiv\{i\in \mathcal{U}|\hat{y}_{i}f(x_{i})=0\}$

2: while $S\neq\emptyset$ do

3: (18) により $\hat{y}’$

を計算し，予測ラベルを

$\hat{y}arrow\hat{y}’$ と反転;

4: 条件付最適解を $farrow$ argmin$fJ(f,\hat{y})$ s.t. (6) と計算;

5: end while

5

数値実験

本節では前節で導入した $S^{3}VM^{path}$ _{アルゴリズムの性能を調べるため数値実験を行う．}

$S^{3}VM^{path}$_{を教師あり} SVM _[12],

および，既存の

$S^{3}VM$ _{アルゴリズムである} $S^{3}VM^{hght}[1],$

deterministicアニーリング ($DA$) _{を用いたアプローチ} [13], convex concave_法(CCCP) _を

用いたアプローチ [14]

と比較する．評価基準として，最適化性能，汎化性能，計算コストに

着目する．比較実験に用いるベンチマークデータの概要を表1に示す．カーネル関数には

ガウスカーネル$k(x_{i}, x_{j})=\exp(-\gamma||x_{i}-x_{j}||_{2}^{2})$

を用いる．ここで，

$\gamma>0$ はガウスカーネ

ルの幅を決めるパラメータである． 最適化性能 S$3VM$ _{の学習は非凸最適化問題であるので，一般に，各アルゴリズムが異な} る解を出力する．CCCP と $S^{3}VM^{path}$ _は $S^{3}VM$ _{の局所最適解を出力することが保証され}

るが，

$S^{3}VM^{light}$ _{と $DA$}

_{の解は必ずしも局所最適解とは限らない．公平な比較をするため，}

各アルゴリズムの出力した予測ラベル$\hat{y}$ を用いて計算した (5) の目的関数値_{$J(f,\hat{y})$} を比 較する．

図 3 に $C\in\{1,10,100,1000\},$ $\gamma=1,$ $\theta=1$

の場合の結果を示す．

$S^{3}VM^{path}$ は従来法に

比べて目的関数値を小さくできており，よい局所最適解が得られていることを示唆してい る．これは，$\theta$を徐々に大きくしながら局所最適解を追跡することによるアニーリング法の

効果と推察できる．通常，アニーリング法ではステップサイズを細かくする方がよいとさ

れる．

$S^{3}VM^{path}$ _が$S^{3}VM^{light}$

_{よりも常によい最適化性能を示しているのは，}

$S^{3}VM^{path}$_が

無限小ステップ幅のアニーリング法を行なっているためと考えられる．

汎化性能 _{まず，各アルゴリズムの汎化性能として，ラベルなしデータ，および，テストデー}

タに対する誤分類率を比較する．モデル選択は，評価データを用いて，

$C\in\{1,10,100,1000\},$

$\theta\in\{\frac{1}{8}, \frac{1}{4}, \frac{1}{2},1\},$ $\gamma\in\{\frac{1}{4d}, \frac{1}{2d}, \frac{1}{d}, \frac{2}{d}, \frac{4}{d}\}$

の候補から選択する．ここで，

$d$ は$\lambda_{\backslash }$力 $x$ の次元数で ある．ただし，$S^{3}VM^{light}$ _は $\theta$ を徐々に大きくしながら学習を行うので，$2^{-9},2^{-8},$ $\ldots,$$2^{-1},1$ 表1: 数値実験で用いるベンチマークデータの概要: $d$

は入力次元，

_$n$は総インスタンス数， $\ell$ はラベルありインスタンス数 $u$はラベルなしインスタンス数，$v$ は評価インスタンス数， $t$ はテストインスタンス数を表す．半教師あり学習は，ラベルありインスンタンスが少量， ラベルなしインスンタンスが大量にある場合に利用されるので，$\ell$が $u$ に比べて十分に小 さくなるように選んでいる．

#D3

#D4

図 3: 各アルゴリズムの最適化性能の比較

の候補から選択する．また，

$S^{3}VM^{path}$ _{はすべての} $\theta\in[0,1]$

における解を計算するため，評

価データを最小にするものを選択する． 表 2 に実験結果を示す．提案法である $S^{3}VM^{path}$ _{は従来法と比べて誤判別率を低くする} 傾向があることがわかった． 計算コスト 最後に各アルゴリズムの計算コストを比較する．図4は各アルゴリズムが複 数の $\theta$ における解を求めるのに要した総計算コストを表している．横軸は異なる $\theta$におけ る解の個数を表している．従来法である $DA$, CCCP, S$3VM^{}$ では解の個数が増えるに 表 2: データの分割を10通り行った際の平均誤判別率 $u$” はラベルなしインスタンスに 対する，$t$” はテストインスタンスに対する平均誤判別率を表す．数値が小さいほど汎化 性能がよいことを示し，太字は各設定において最良のものを表す．

#Dl

#D5

#D6

図4: _{モデル選択における計算コスト}

つれて計算コストも増えていることがわかる．通常，モデル選択における候補数やアニー

リング法のステップ数は多ければ多いほど好ましいが，これは計算コストとトレードオフ

の関係にあることがわかる．一方，

$S^{3}VM^{path}$_{ではすべての} $\theta\in[0,1]$ における局所最適解

を計算するため，解の個数に限らず計算コストは一定となる．これは，解の個数と計算コ

ストのトレードオフを回避できていることを意味し，従来法に対する提案法の有効性を示

唆している．

6

まとめ

本研究では半教師あり SVMやロバスト SVM_{などに共通して現れる非凸最適化問題を}

考察した．このクラスの問題の局所最適解の性質を分析することにょり，パラメトリック

計画法に基づく最適化アルゴリズムを構築した．本稿では，このクラスの非凸最適化問題

の例として，主に，半教師あり

SVM

_{を考察した．提案アルゴリズムを用いると，ラベルな}

しデータの影響を連続的に増加させていったときの局所最適解のパスを計算することがで

きる．ベンチマークデータを用いた数値実験にょり，既存のアルゴリズムよりも最適化性

能，汎化性能，計算コストの観点で利点を持っこと示した．今後は大規模なデータに適用

するため _{coordinate-descent 法を用いた近似的なパラメトリック計画アルゴリズムを構築} する．

参考文献

[1] T. Joachims. Transductive inference for text classification using support vector

ma-chines. International

_Conference

on Machine Learning, 1999.

[2] J. Hromkovic. Algorithmics

_for

_{Hard Problems. Springer, 2001.}

[3] T. Gal. Postoptimal_{Analysis, Parametric Progmmming, and Related Topics. Walter}

de Gruyter, 1995.

[4] B. Efron, T. _{Hastie, I. Johnstone, and R. Tibshirani. Least angle regression. Annals}

[5] T.Hastie,

S.

Rosset, R. Tibshirani,and J. Zhu. The entire regularization path for the

support vector machine. Joumal

_of

Machine Learning Research, 5:1391-415, 2004.

[6] X. Shen, G. Tseng, X. Zhang, and W. H. Wong. On $\psi$-leaming. Journal

of

the

American Statistical Association, $98(463):724-734$, 2003.

[7] $0$. Chapelle, V. Sindhwani, and S. S. Keerthi. optimization techniques for

semi-supervised support vector machines. J. Mach. Learning Res., 9:202-233, Feb. 2008.

[8] O. Chapelle and A. Zien. Semi-supervised classification by low density separation.

Tenth International Workshop on

_Artificial

Intelligence and Statzstics, 2005.

[9] S. Boyd and L. Vandenberghe. Convex optimization. Cambridge University Press,

2004.

[10] E. L. Allgower and K. George. Continuation and path following. Acta Numerica,

2:1-63, 1993.

[11] M. J. Best. An algorithm for the solution of theparametric quadratic programming

problem. Applied Mathemetics and Pamllel Computing, pages 57-76, 1996.

[12] V. N. Vapnik. The Nature

_of

Statistical Leaming Theory. Springer, 1996.

[13] V. Sindhwani, S. Keerthi, and O. Chapelle. Deterministic anneahng for

semi-supervisedkemel machines. Intemational

Conference

on Machine Learning, 2006.

[14] R. Collobert, F. Sinz, J. Weston, and L. Bottou. Large scale transductive SVMs.