構造化サポートベクターマシン

構造化サポートベクターマシンは、サポートベクターマシン(SVM) 分類器を一般化する機械学習アルゴリズムです。SVM 分類器はバイナリ分類、マルチクラス分類、回帰をサポートしますが、構造化 SVM では、一般的な構造化出力ラベルの分類器のトレーニングが可能です。

たとえば、サンプルインスタンスは自然言語の文で、出力ラベルは注釈付きの構文解析ツリーです。分類器のトレーニングは、正しいサンプルと出力ラベルのペアを示すことから構成されます。トレーニング後、構造化 SVM モデルにより、新しいサンプルインスタンスに対応する出力ラベルを予測できます。つまり、自然言語の文が与えられると、分類器は最も可能性の高い構文解析ツリーを生成できます。

一連のトレーニングインスタンスに対して、サンプル空間とラベル空間から、構造化 SVM は次の正規化されたリスク関数を最小化します。 ${\displaystyle n}$${\displaystyle ({\boldsymbol {x}}_{i},y_{i})\in {\mathcal {X}}\times {\mathcal {Y}}}$${\displaystyle i=1,\dots ,n}$${\displaystyle {\mathcal {X}}}$${\displaystyle {\mathcal {Y}}}$

${\displaystyle {\underset {\boldsymbol {w}}{\min }}\quad \|{\boldsymbol {w}}\|^{2}+C\sum _{i=1}^{n}{\underset {y\in {\mathcal {Y}}}{\max }}\left(0,\Delta (y_{i},y)+\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y)\rangle -\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y_{i})\rangle \right)}$

関数 は、アフィン関数の集合の最大値が凸であるため、において凸です。関数 はラベル空間で距離を測定し、および を満たす任意の関数 (必ずしもメトリックとは限らない)です。関数 は特徴関数であり、指定されたサンプルとラベルから何らかの特徴ベクトルを抽出します。この関数の設計は、アプリケーションによって大きく異なります。 ${\displaystyle {\boldsymbol {w}}}$${\displaystyle \Delta :{\mathcal {Y}}\times {\mathcal {Y}}\to \mathbb {R} _{+}}$${\displaystyle \Delta (y,z)\geq 0}$${\displaystyle \Delta (y,y)=0\;\;\forall y,z\in {\mathcal {Y}}}$${\displaystyle \Psi :{\mathcal {X}}\times {\mathcal {Y}}\to \mathbb {R} ^{d}}$

上記の正規化されたリスク関数は微分不可能であるため、各サンプルに最大値を表す1 つのスラック変数を導入することで、 2 次計画の観点から再定式化されることがよくあります。標準的な構造化 SVM のプライマリ定式化は次のように与えられます。 ${\displaystyle \xi_{i}}$

${\displaystyle {\begin{array}{cl}{\underset {{\boldsymbol {w}},{\boldsymbol {\xi }}}{\min }}&\|{\boldsymbol {w}}\|^{2}+C\sum _{i=1}^{n}\xi _{i}\\{\textrm {st}}&\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y_{i})\rangle -\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y)\rangle +\xi _{i}\geq \Delta (y_{i},y),\qquad i=1,\dots ,n,\quad \forall y\in {\mathcal {Y}}\end{array}}}$

テスト時にはサンプルのみがわかっており、予測関数はそれをラベル空間からの予測ラベルにマッピングします。構造化 SVM の場合、トレーニングから取得されたベクトルが与えられると、予測関数は次のようになります。 ${\displaystyle {\boldsymbol {x}}\in {\mathcal {X}}}$${\displaystyle f:{\mathcal {X}}\to {\mathcal {Y}}}$${\displaystyle {\mathcal {Y}}}$${\displaystyle {\boldsymbol {w}}}$

${\displaystyle f({\boldsymbol {x}})={\underset {y\in {\mathcal {Y}}}{\textrm {argmax}}}\quad \langle {\boldsymbol {w}},\ Psi ({\boldsymbol {x}},y)\rangle }$

したがって、ラベル空間の最大化子は予測ラベルです。この最大化子を解くことは、いわゆる推論問題であり、確率モデルで最大事後確率 (MAP) 予測を行うことに似ています。関数の構造によっては、最大化子を解くことが難しい問題になることがあります。 ${\displaystyle \Psi}$

上記の二次計画法には、非常に大きな、おそらくは無限の数の線形不等式制約が伴います。一般に、不等式の数は多すぎるため、明示的に最適化することはできません。代わりに、制約の有限かつ小さなサブセットのみを使用する遅延制約生成を使用して問題を解決します。制約のサブセットを最適化すると、実行可能なセットが拡大し、目的の下限を提供するソリューションが得られます。ソリューションが完全なセットの不等式の制約に違反するかどうかをテストするには、分離問題を解決する必要があります。不等式がサンプルごとに分解されるため、サンプルごとに次の問題を解決する必要があります。 ${\displaystyle {\boldsymbol {w}}}$${\displaystyle ({\boldsymbol {x}}_{i},y_{i})}$

${\displaystyle y_{n}^{*}={\underset {y\in {\mathcal {Y}}}{\textrm {argmax}}}\left(\Delta (y_{i},y)+\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y)\rangle -\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y_{i})\rangle -\xi _{i}\right)}$

最大化される右側の目的は、定数と、最適化される変数に依存する項、つまりで構成されます。達成された右側の目的がゼロ以下である場合、このサンプルには違反する制約は存在しません。ゼロより厳密に大きい場合、このサンプルに関して最も違反する制約が特定されています。問題はこの制約によって拡大され、解決されます。違反する不等式が特定されなくなるまで、このプロセスは続行されます。 ${\displaystyle -\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y_{i})\rangle -\xi _{i}}$${\displaystyle \Delta (y_{i},y)+\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y)\rangle }$

上記の問題から定数を削除すると、解決すべき次の問題が得られます。

${\displaystyle y_{i}^{*}={\underset {y\in {\mathcal {Y}}}{\textrm {argmax}}}\left(\Delta (y_{i},y)+\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y)\rangle \right)}$

この問題は推論問題と非常によく似ています。唯一の違いは、項 が追加されていることです。ほとんどの場合、これはラベル空間で自然に分解されるように選択されます。その場合、 の影響は推論問題にエンコードすることができ、最も違反する制約を解くことは推論問題を解くことと同等です。 ${\displaystyle \Delta (y_{i},y)}$${\displaystyle \Delta }$

• Ioannis Tsochantaridis、Thorsten Joachims、Thomas Hofmann、Yasemin Altun (2005)、「構造化され相互依存する出力変数に対する大規模マージン法」、JMLR、第 6 巻、1453-1484 ページ。
• Thomas Finley と Thorsten Joachims (2008)、「正確な推論が困難な場合の構造 SVM のトレーニング」、ICML 2008。
• Sunita Sarawagiと Rahul Gupta (2008)、「構造化出力空間の正確な最大マージントレーニング」、ICML 2008。
• Gökhan BakIr、Ben Taskar、Thomas Hofmann、Bernhard Schölkopf、Alex Smola、SVN Vishwanathan (2007)、「Predicting Structured Data」、MIT Press。
• Vojtěch Franc と Bogdan Savchynskyy 最大和分類器の識別学習、Journal of Machine Learning Research、9(Jan):67—104、2008 年、Microtome Publishing
• ケビン・マーフィー[1]機械学習、MITプレス