「《サポート・ベクター・マシン》」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
(新しいページ: ''''【さぽーと・べくたー・ましん (support vector machine) 】''' 　サポート・ベクター・マシン (SVM) は, 判別関数を求める教師付き学習...')
 
 
(5人の利用者による、間の11版が非表示)
3行目: 3行目:
 
　サポート・ベクター・マシン (SVM) は, 判別関数を求める教師付き学習法のひとつである.  
 
　サポート・ベクター・マシン (SVM) は, 判別関数を求める教師付き学習法のひとつである.  
  
−
　今, $N$個の属性を持ったデータが$M$個与えられており,これを,$N$次元空間$\mathbb{R}^{N}$の点$\Va_{1},$$\Va_{2},\ldots,$ $\Va_{M} \in \mathbb{R}^{N}$と考える.各点$\Va_{j}\ (j=1,2,\ldots,M)$は2種類のクラスのいづれか一方に属しており,対応する2値のラベル$y_{j} \in \{-1,+1\}$が与えられているとする.このとき, ラベルの値にしたがって点を判別する2クラスの判別問題を考える.
+
　今, <math>N\, </math>個の属性を持ったデータが<math>M\, </math>個与えられており,これを,<math>N\, </math>次元空間<math>\mathbb{R}^{N}\, </math>の点<math>\boldsymbol{a}_{1}, \boldsymbol{a}_{2},\ldots, \boldsymbol{a}_{M} \in \mathbb{R}^{N}\, </math>と考える. 各点<math>\boldsymbol{a}_{j}\ (j=1,2,\ldots,M)\, </math>は2種類のクラスのいづれか一方に属しており, 対応する2値のラベル<math>y_{j} \in \{-1,+1\}\, </math>が与えられているとする. このとき, ラベルの値にしたがって点を判別する2クラスの判別問題を考える.
  
−
　SVMでは線形関数を用いた判別を行う.$N$次元の法線ベクトル$\Vw$および実数$b$で定まる線形関数を$f(\Vx) = \Vx^{T} \Vw - b$ とすれば,与えられたデータおよびラベルにしたがって,
+
　SVMでは線形関数を用いた判別を行う. <math>N\, </math>次元の法線ベクトル<math>\boldsymbol{w} \, </math>および実数<math>b\, </math>で定まる線形関数を<math>f(\boldsymbol{x}) = \boldsymbol{x}^{T} \boldsymbol{w}- b\, </math> とすれば, 与えられたデータおよびラベルにしたがって,
  
  
−
\begin{equation}
+
<center>
−
\label{eq:線形分離可能}
+
<math>
−
f(\Va_{j}) = \Va_{j}^{T}\Vw - b \left\{
+
f(\boldsymbol{a}_{j}) = \boldsymbol{a}_{j}^{T} \boldsymbol{w}- b \left\{
 
\begin{array}{ll}
 
\begin{array}{ll}
 
  > 0 & \mbox{if}\ \  y_{j} = 1,\\
 
  > 0 & \mbox{if}\ \  y_{j} = 1,\\
16行目: 16行目:
 
\end{array}
 
\end{array}
 
\right.\quad j=1,2,\ldots,M
 
\right.\quad j=1,2,\ldots,M
−
\end{equation}
+
\, </math>　　　　<math>(1)\, </math>
 +
</center>
  
  
−
となるベクトル$\Vw$とスカラ$b$を次に示す最適化問題を解くことで算出する.
+
となるベクトル<math>\boldsymbol{w} \, </math>とスカラ<math>b\, </math>を次に示す最適化問題を解くことで算出する.
  
−
　一般的には, 与えられた点全てに対して式\,(\ref{eq:線形分離可能})を満たす$\Vw,b$が存在するとは限らないので,非負の変数$\xi_{j}\ (j=1,2,\ldots,M)$を導入し, 次の制約条件
+
　一般的には, 与えられた点全てに対して式 (1) を満たす<math>\boldsymbol{w},b\, </math>が存在するとは限らないので, 非負の変数<math>\xi_{j}\ (j=1,2,\ldots,M)\, </math>を導入し, 次の制約条件
  
  
−
\begin{equation}
+
<center>
 +
<math>
 
  \begin{array}{lll}
 
  \begin{array}{lll}
−
  {\displaystyle  \Va_{j}^{T} \Vw - b + \xi_{j} \geq 1 }
+
  {\displaystyle  \boldsymbol{a}_{j}^{T} \boldsymbol{w}- b + \xi_{j} \geq 1 }
 
   & \mbox{if}& y_{j} = 1, \\
 
   & \mbox{if}& y_{j} = 1, \\
−
  {\displaystyle  \Va_{j} \Vw - b - \xi_{j} \leq -1 }
+
  {\displaystyle  \boldsymbol{a}_{j} \boldsymbol{w}- b - \xi_{j} \leq -1 }
 
   & \mbox{if}& y_{j} = -1
 
   & \mbox{if}& y_{j} = -1
 
\end{array}
 
\end{array}
−
\label{eq:ConstraintsWithSlack}
+
\, </math>　　　　<math>(2)\, </math>
−
\end{equation}
+
</center>
  
  
−
のもと,$\xi_{j}$の和と$\Vw$のノルムができるだけ小さくなる線形関数を考える.すなわち,次の二次計画問題を解き$\Vw,b$を算出する [?].
+
のもと,<math>\xi_{j}\, </math>の和と<math>\boldsymbol{w}\, </math>のノルムができるだけ小さくなる線形関数を考える. すなわち, 次の二次計画問題を解き<math>\boldsymbol{w},b\, </math>を算出する [2].
  
  
−
\begin{equation}
+
<table align="center">
−
\left|
+
<tr>
−
\begin{array}{ll}
+
<td>
−
\mbox{最小化}  
+
<table>
−
  & { % \displaystyle
+
<tr>
−
      \frac{1}{2}\|\Vw\|_{2}^{2} + C \sum_{j=1}^{M} \xi_{j}
+
<td rowspan="4"> <math>\left|  
−
    }\\
+
\begin{array}{l}
−
\mbox{制約}
+
\\
−
  &{ % \displaystyle
+
\\
−
       \Va_{j}^{T} \Vw - b + \xi_{j} \geq 1,
+
\\
−
         \quad \mbox{if } y_{j} = 1,}\\
+
\\
−
  & { % \displaystyle
+
\\
−
       \Va_{j}^{T} \Vw - b - \xi_{j} \leq -1,
+
\end{array} \right.</math></td>
−
         \quad \mbox{if } y_{j} = -1,}\\
+
<td>最大化 </td>
−
  & { % \displaystyle
+
          <td><math>\textstyle \frac{1}{2}\| \boldsymbol{w} \|^{2}_{2} + C \ {\sum}_{j=1}^{M} \xi_{j}</math></td>
−
       \xi_{j} \ge 0, \quad j=1,2,\ldots,M}
+
<td rowspan="4">　　　　<math>(3)\, </math></td>
−
\end{array}
+
</tr>
 +
<tr>
 +
<td>制約 </td>
 +
          <td><math>\textstyle
 +
       \boldsymbol{a}_{j}^{T} \boldsymbol{w}- b + \xi_{j} \geq 1,
 +
         \quad \mbox{if } y_{j} = 1,</math></td>
 +
</tr>
 +
<tr>
 +
<td></td>
 +
<td><math>\textstyle
 +
       \boldsymbol{a}_{j}^{T} \boldsymbol{w}- b - \xi_{j} \leq -1,
 +
         \quad \mbox{if } y_{j} = -1,</math></td>
 +
</tr>
 +
<tr>
 +
<td></td>
 +
<td><math>\textstyle
 +
       \xi_{j} \ge 0, \quad j=1,2,\ldots,M</math></td>
 +
</tr>
 +
</table>
 +
</td>
 +
</tr>
 +
</table>
 +
 
  
  
−
ここで,$C$はあらかじめ設定された正の定数で,$\|\Vw\|^{2}_{2}$と$\sum_{j=1}^{M} \xi_{j}$とのバランスをコントロールするパラメータである.また,$\|\Vw\|^{2}_{2}$は正則化項とも呼ばれ,これを小さくすることは判別関数に用いるデータの属性を少なくし,過学習を防ぐ役割があるとされる [?].問題(??)は,1ノルムソフトマージンSVMと呼ばれる定式化である.
+
ここで,<math>C\, </math>はあらかじめ設定された正の定数で, <math>\textstyle \| \boldsymbol{w} \|^{2}_{2}\, </math>と<math>\textstyle {\sum}_{j=1}^{M} \xi_{j}\, </math>とのバランスをコントロールするパラメータである. また, <math>\textstyle \| \boldsymbol{w} \|^{2}_{2}\, </math>は正則化項とも呼ばれ, これを小さくすることは判別関数に用いるデータの属性を少なくし, 過学習を防ぐ役割があるとされる [6]. 問題 (3) は, 1ノルムソフトマージンSVMと呼ばれる定式化である.
  
−
　通常は,この問題の双対問題を考え最適化を行う [?].$\alpha_{1},\alpha_{2},\ldots,\alpha_{M}$ を双対変数とすれば,問題(??)の双対問題は
+
　通常は,この問題の双対問題を考え最適化を行う [5]. <math>\alpha_{1},\alpha_{2},\ldots,\alpha_{M}\, </math> を双対変数とすれば, 問題 (3) の双対問題は
  
  
−
\begin{equation}
+
<table align="center">
−
\left|
+
<tr>
−
\begin{array}{ll}
+
<td>
−
\mbox{最大化}
+
<table>
−
  & { %\displaystyle
+
<tr>
 +
<td rowspan="4"> <math>\left|  
 +
\begin{array}{l}
 +
\\
 +
\\
 +
\\
 +
\\
 +
\end{array} \right.</math></td>
 +
<td>最大化 </td>
 +
          <td><math>\textstyle
 
       - \frac{1}{2} \sum_{i=1}^{M}\sum_{j=1}^{M}
 
       - \frac{1}{2} \sum_{i=1}^{M}\sum_{j=1}^{M}
−
         y_{i}y_{j}\Va_{i}^{T}\Va_{j}\alpha_{i}\alpha_{j}
+
         y_{i}y_{j} \boldsymbol{a}_{i}^{T} \boldsymbol{a}_{j}\alpha_{i}\alpha_{j}
−
       + \sum_{j=1}^{M} \alpha_{j}
+
       + \sum_{j=1}^{M} \alpha_{j}</math></td>
−
    }\\
+
<td rowspan="4">　　　　<math>(4)\, </math></td>
−
\mbox{制約}
+
</tr>
−
  & { %\displaystyle
+
<tr>
−
      \sum_{j=1}^{M} y_{j} \alpha_{j}= 0,
+
<td>制約 </td>
−
    }\\
+
          <td><math>\textstyle \sum_{j=1}^{M} y_{j} \alpha_{j}= 0,</math></td>
−
  & { 0 \leq \alpha_{j} \leq C,\quad j=1,2,\ldots,M
+
</tr>
−
    }
+
<tr>
−
\end{array}
+
<td></td>
−
\right.
+
<td><math>0 \leq \alpha_{j} \leq C,\quad j=1,2,\ldots,M</math></td>
−
\label{eq:StandradWolfeDualwithQ}
+
</tr>
−
\end{equation}
+
</table>
 +
</td>
 +
</tr>
 +
</table>
 +
 
  
 +
と書くことができ, これは1本の等式制約と各変数の上下限制約のみの凹二次関数の最大化となる. この特殊構造を用いた最適化アルゴリズム [3, 4] が知られており, データ数<math>(M)\, </math>が数10万を超えるような大規模問題であっても, 高速に最適化が可能である.
  
−
と書くことができ,これは1本の等式制約と各変数の上下限制約のみの凹二次関数の最大化となる.この特殊構造を用いた最適化アルゴリズム [?, ?] が知られており,データ数$(M)$が数10万を超えるような大規模問題であっても,高速に最適化が可能である.
+
　双対問題 (4) の最適解を<math>\alpha^{*}_{1},\alpha^{*}_{2},\ldots,\alpha^{*}_{M}\, </math>とすれば,KKT条件より主問題 (3) の最適解<math>\boldsymbol{w}^{*},b^{*}\, </math>とは, <math>\textstyle \boldsymbol{w}^{*} = \sum_{j=1}^{M} \alpha_{j}^{*} y_{j} \boldsymbol{a}_{j}\, </math>となる関係があり, さらに<math>0<\alpha_{k}^{*}<C\, </math>となる添え字を<math>k\, </math>とすれば, <math>b^{*} = \boldsymbol{a}^{T}_{k}  \boldsymbol{w}^{*}-y_{k}\, </math>となることが示される. また, 特に添え字の集合<math>SV=\{j|\alpha_{j}^{*} \not = 0 \}\, </math>を定義すれば,<math>j \in SV\, </math>に対応するデータ<math>\boldsymbol{a}_{j}\, </math>をサポート・ベクターと呼ぶ.したがって, 判別関数は双対問題の最適解とサポート・ベクターにより次のように表されることとなる.
  
−
　双対問題(??)の最適解を$\alpha^{*}_{1},\alpha^{*}_{2},\ldots,\alpha^{*}_{M}$とすれば,KKT条件より主問題(??)の最適解$\Vw^{*},b^{*}$とは,$ \Vw^{*} = \sum_{j=1}^{M} \alpha_{j}^{*} y_{j} \Va_{j}$となる関係があり,さらに$0<\alpha_{k}^{*}<C$となる添え字を$k$とすれば,$b^{*} = \Va^{T}_{k}\Vw^{*}-y_{k}$となることが示される.また,特に添え字の集合$SV=\{j|\alpha_{j}^{*} \not = 0 \}$を定義すれば,$j \in SV$に対応するデータ$\Va_{j}$をサポート・ベクターと呼ぶ.したがって,判別関数は双対問題の最適解とサポート・ベクターにより次のように表されることとなる.
 
  
 +
<center>
 +
<math> f(\boldsymbol{x}) = \boldsymbol{x}^{T}  \boldsymbol{w}^{*} - b^{*}
 +
        = \sum_{j \in SV} \alpha_{j}^{*} y_{j} \boldsymbol{x}^{T} \boldsymbol{a}_{j} - b^{*}\, </math>　　　　　<math>(5)\, </math>
 +
</center>
  
−
\begin{equation}
 
−
\label{eq:線形判別関数}
 
−
f(\Vx) = \Vx^{T} \Vw^{*} - b^{*}
 
−
        = \sum_{j \in SV} \alpha_{j}^{*} y_{j}
 
−
                      \Vx^{T} \Va_{j} - b^{*}
 
−
\end{equation}
 
  
 +
さらに, 双対問題 (4) や主問題 (3) は, サポート・ベクター以外を全て取り除いても最適解は不変であり, これらの点はSVMでの判別にはまったく寄与していないことになる.
  
−
さらに,双対問題(??)や主問題(??)は,サポート・ベクター以外を全て取り除いても最適解は不変であり,これらの点はSVMでの判別にはまったく寄与していないことになる.
+
　SVMの最大の特徴は, 双対問題(4)を応用することで非線形な判別関数を構成できる点にある. 非線形な判別関数を構成するためには, まず, 適当な非線形変換<math>\phi: \mathbb{R}^{N} \to {\mathcal F}\, </math>を使い各データ<math>\boldsymbol{a}_{j}\, </math>をより高い次元の特徴空間<math>{\mathcal F}\, </math>の元へと射影する. 射影された<math>{\mathcal F}\, </math>の元<math>\phi(\boldsymbol{a}_{1}),\phi(\boldsymbol{a}_{2}),\ldots,\phi(\boldsymbol{a}_{M})\, </math>に対して, <math>{\mathcal F}\, </math>上での線形な判別関数を求めれば, 元の空間で見れば非線形な判別関数を求めたこととなる.
  
−
　SVMの最大の特徴は,双対問題(??)を応用することで非線形な判別関数を構成できる点にある.非線形な判別関数を構成するためには,まず,適当な非線形変換$\phi: \mathbb{R}^{N} \to {\cal F}$を使い各データ$\Va_{j}$をより高い次元の特徴空間${\cal F}$の元へと射影する.射影された${\cal F}$の元$\phi(\Va_{1}),\phi(\Va_{2}),\ldots,\phi(\Va_{M})$に対して,${\cal F}$上での線形な判別関数を求めれば,元の空間で見れば非線形な判別関数を求めたこととなる.
+
　ここで, 双対問題 (4) に注目すれば,<math>{\mathcal F}\, </math>上の内積<math>\phi(\boldsymbol{a}_{i})^{T}\phi(\boldsymbol{a}_{j})\, </math>の値のみが得られれば定式化が可能であり, 特徴空間での点<math>\phi(\boldsymbol{a}_{j})\, </math>の座標を必ずしも必要としないことが分かる. そこで, SVMではカーネル関数と呼ばれる特殊な関数<math>\mathcal {K} ( {\cdot} , {\cdot} )\, </math>を用い元のデータ<math>\boldsymbol{x}, \boldsymbol{x}' \in \mathbb{R}^{N}\, </math>から直接<math>{\mathcal F}\, </math>の元<math>\phi(\boldsymbol{x}),\phi(\boldsymbol{x}')\, </math>の内積<math>\phi(\boldsymbol{x})^{T}\phi(\boldsymbol{x}')\, </math>を算出し, 双対問題の最適化により非線形の判別関数が求められる [1]. よく用いられる代表的なカーネル関数として, 多項式カーネル<math>\mathcal{K} (\boldsymbol{x}, \boldsymbol{x}' ) = \left( \boldsymbol{x}^{T}\boldsymbol{x}' + c \right)^{d}\,</math> やRBFカーネル <math>\mathcal{K} (\boldsymbol{x},\boldsymbol{x}' ) = \exp\left( -\| \boldsymbol{x} -  \boldsymbol{x}' \|^{2}/ \sigma^{2} \right )\, </math>, (ただし<math>d\, </math>は自然数のパラメータ, <math>c,\sigma\, </math> は実数のパラメータである) などがある.
  
−
　ここで,双対問題(??)に注目すれば,${\cal F}$上の内積$\phi(\Va_{i})^{T}\phi(\Va_{j})$の値のみが得られれば定式化が可能であり,特徴空間での点$\phi(\Va_{j})$の座標を必ずしも必要としないことが分かる.そこで, SVMではカーネル関数と呼ばれる特殊な関数$\kernel{\cdot}{\cdot}$を用い元のデータ$\Vx,\Vx' \in \mathbb{R}^{N}$から直接${\cal F}$の元$\phi(\Vx),\phi(\Vx')$の内積$\phi(\Vx)^{T}\phi(\Vx')$を算出し,双対問題の最適化により非線形の判別関数が求められる [?].よく用いられる代表的なカーネル関数として,多項式カーネル$\kernel{\Vx}{\Vx'} = \left( \Vx^{T} \Vx' + c \right)^{d}$やRBFカーネル$ \kernel{\Vx}{\Vx'} = \exp\left( -\| \Vx - \Vx' \|^{2}/ \sigma^{2} \right )$,(ただし$d$は自然数のパラメータ,$c,\sigma$ は実数のパラメータである)などがある.
 
  
−
　カーネル関数の値$\kernel{\Va_{i}}{\Va_{j}}$を$i-j$成分とする$M$次の対称行列を$K$とすれば,$K$が半正定値行列となるようなカーネル関数をMercerカーネル(あるいは半正定値カーネル)と呼び,このようなカーネル関数であれば,$\kernel{\Va_{i}}{\Va_{j}}=\phi(\Va_{i})^{T}\phi(\Va_{j})$となる特徴空間への変換$\phi(\cdot)$が存在することが保証される.多項式カーネルやRBFカーネルはMercerカーネルである [?].また,Mercerカーネルを用いるのであれば,対応した双対問題は常に凹二次関数の最大化となり,通常の二次計画問題の解法を用いれば大域的に最適化が可能である.
+
　カーネル関数の値<math>\mathcal{K} ( \boldsymbol{a}_{i}, \boldsymbol{a}_{j} ) \, </math>を<math>i-j\, </math>成分とする<math>M\, </math>次の対称行列を<math>K\, </math>とすれば, <math>K\, </math>が半正定値行列となるようなカーネル関数をMercerカーネル(あるいは半正定値カーネル)と呼び, このようなカーネル関数であれば,<math>\mathcal{K} ( \boldsymbol{a}_{i}, \boldsymbol{a}_{j} )=\phi(\boldsymbol{a}_{i})^{T}\phi(\boldsymbol{a}_{j})\, </math>となる特徴空間への変換<math>\phi(\cdot)\, </math>が存在することが保証される. 多項式カーネルやRBFカーネルはMercerカーネルである [5].また, Mercerカーネルを用いるのであれば, 対応した双対問題は常に凹二次関数の最大化となり, 通常の二次計画問題の解法を用いれば大域的に最適化が可能である.
  
−
　すなわち,双対問題の最適解を$\alpha_{j}^{*}$とすれば,カーネル関数を用いた場合には,次の非線形な判別関数が求められることとなる.
+
　すなわち, 双対問題の最適解を<math>\alpha_{j}^{*}\, </math>とすれば, カーネル関数を用いた場合には, 次の非線形な判別関数が求められることとなる.
  
  
−
\begin{equation}
+
<center>
−
f(\Vx) = \sum_{j \in SV}\alpha_{j}^{*} y_{j}
+
<math>f(\boldsymbol{x}) = \sum_{j \in SV}\alpha_{j}^{*} y_{j}
−
                       \kernel{\Vx}{\Va_{j}} - b^{*}.
+
                       \mathcal{K} ( \boldsymbol{x}, \boldsymbol{a}_{j} )- b^{*}.\, </math>　　　　　<math>(6)\, </math>
−
\end{equation}
+
</center>
  
  
−
　すなわち,判別関数$f(\cdot)$は,サポート・ベクター $\Va_{j}\ (j \in SV)$に対応するカーネル関数$\kernel{\Vx}{\Va_{j}}$の重ね合せとして算出されると見ることができる.
+
　すなわち, 判別関数<math>f(\cdot)\, </math>は, サポート・ベクター <math>\boldsymbol{a}_{j}\ (j \in SV)\, </math>に対応するカーネル関数<math>\mathcal{K} (\boldsymbol{x}, \boldsymbol{a}_{j} )\, </math>の重ね合せとして算出されると見ることができる.
  
  
  
 
----
 
----
−
 
 
'''参考文献'''
 
'''参考文献'''
  
132行目: 166行目:
  
 
[6] V. N. Vapnik, ''The nature of statistical learning theory'', Statistics for Engineering and Information Science, Springer-Verlag, 2000.
 
[6] V. N. Vapnik, ''The nature of statistical learning theory'', Statistics for Engineering and Information Science, Springer-Verlag, 2000.
 +
 +
 +
[[category:近似・知能・感覚的手法|さぽーとべくたーましん]]

2007年8月7日 (火) 02:31時点における最新版

【さぽーと・べくたー・ましん (support vector machine) 】

　サポート・ベクター・マシン (SVM) は, 判別関数を求める教師付き学習法のひとつである.

　今, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle N\, } 個の属性を持ったデータが構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle M\, } 個与えられており,これを,構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle N\, } 次元空間構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mathbb{R}^{N}\, } の点構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \boldsymbol{a}_{1}, \boldsymbol{a}_{2},\ldots, \boldsymbol{a}_{M} \in \mathbb{R}^{N}\, } と考える. 各点構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \boldsymbol{a}_{j}\ (j=1,2,\ldots,M)\, } は2種類のクラスのいづれか一方に属しており, 対応する2値のラベルが与えられているとする. このとき, ラベルの値にしたがって点を判別する2クラスの判別問題を考える.

　SVMでは線形関数を用いた判別を行う. 次元の法線ベクトルおよび実数で定まる線形関数を とすれば, 与えられたデータおよびラベルにしたがって,


　　　　


となるベクトル構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \boldsymbol{w} \, } とスカラ構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle b\, } を次に示す最適化問題を解くことで算出する.

　一般的には, 与えられた点全てに対して式 (1) を満たす構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \boldsymbol{w},b\, } が存在するとは限らないので, 非負の変数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \xi_{j}\ (j=1,2,\ldots,M)\, } を導入し, 次の制約条件


構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \begin{array}{lll} {\displaystyle \boldsymbol{a}_{j}^{T} \boldsymbol{w}- b + \xi_{j} \geq 1 } & \mbox{if}& y_{j} = 1, \\ {\displaystyle \boldsymbol{a}_{j} \boldsymbol{w}- b - \xi_{j} \leq -1 } & \mbox{if}& y_{j} = -1 \end{array} \, } 　　　　構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (2)\, }


のもと,構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \xi_{j}\, } の和とのノルムができるだけ小さくなる線形関数を考える. すなわち, 次の二次計画問題を解きを算出する [2].


構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \left| \begin{array}{l} \\ \\ \\ \\ \\ \end{array} \right.} 最大化 　　　　
制約


ここで,はあらかじめ設定された正の定数で, と構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \textstyle {\sum}_{j=1}^{M} \xi_{j}\, } とのバランスをコントロールするパラメータである. また, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \textstyle \| \boldsymbol{w} \|^{2}_{2}\, } は正則化項とも呼ばれ, これを小さくすることは判別関数に用いるデータの属性を少なくし, 過学習を防ぐ役割があるとされる [6]. 問題 (3) は, 1ノルムソフトマージンSVMと呼ばれる定式化である.

　通常は,この問題の双対問題を考え最適化を行う [5]. 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \alpha_{1},\alpha_{2},\ldots,\alpha_{M}\, } を双対変数とすれば, 問題 (3) の双対問題は


最大化 　　　　構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (4)\, }
制約 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \textstyle \sum_{j=1}^{M} y_{j} \alpha_{j}= 0,}
構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 0 \leq \alpha_{j} \leq C,\quad j=1,2,\ldots,M}


と書くことができ, これは1本の等式制約と各変数の上下限制約のみの凹二次関数の最大化となる. この特殊構造を用いた最適化アルゴリズム [3, 4] が知られており, データ数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (M)\, } が数10万を超えるような大規模問題であっても, 高速に最適化が可能である.

　双対問題 (4) の最適解を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \alpha^{*}_{1},\alpha^{*}_{2},\ldots,\alpha^{*}_{M}\, } とすれば,KKT条件より主問題 (3) の最適解構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \boldsymbol{w}^{*},b^{*}\, } とは, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \textstyle \boldsymbol{w}^{*} = \sum_{j=1}^{M} \alpha_{j}^{*} y_{j} \boldsymbol{a}_{j}\, } となる関係があり, さらに構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 0<\alpha_{k}^{*}<C\, } となる添え字を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle k\, } とすれば, となることが示される. また, 特に添え字の集合構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle SV=\{j|\alpha_{j}^{*} \not = 0 \}\, } を定義すれば,構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle j \in SV\, } に対応するデータ構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \boldsymbol{a}_{j}\, } をサポート・ベクターと呼ぶ.したがって, 判別関数は双対問題の最適解とサポート・ベクターにより次のように表されることとなる.


構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(\boldsymbol{x}) = \boldsymbol{x}^{T} \boldsymbol{w}^{*} - b^{*} = \sum_{j \in SV} \alpha_{j}^{*} y_{j} \boldsymbol{x}^{T} \boldsymbol{a}_{j} - b^{*}\, } 　　　　　構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (5)\, }


さらに, 双対問題 (4) や主問題 (3) は, サポート・ベクター以外を全て取り除いても最適解は不変であり, これらの点はSVMでの判別にはまったく寄与していないことになる.

　SVMの最大の特徴は, 双対問題(4)を応用することで非線形な判別関数を構成できる点にある. 非線形な判別関数を構成するためには, まず, 適当な非線形変換構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \phi: \mathbb{R}^{N} \to {\mathcal F}\, } を使い各データ構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \boldsymbol{a}_{j}\, } をより高い次元の特徴空間構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\mathcal F}\, } の元へと射影する. 射影された構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\mathcal F}\, } の元構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \phi(\boldsymbol{a}_{1}),\phi(\boldsymbol{a}_{2}),\ldots,\phi(\boldsymbol{a}_{M})\, } に対して, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\mathcal F}\, } 上での線形な判別関数を求めれば, 元の空間で見れば非線形な判別関数を求めたこととなる.

　ここで, 双対問題 (4) に注目すれば,構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\mathcal F}\, } 上の内積構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \phi(\boldsymbol{a}_{i})^{T}\phi(\boldsymbol{a}_{j})\, } の値のみが得られれば定式化が可能であり, 特徴空間での点構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \phi(\boldsymbol{a}_{j})\, } の座標を必ずしも必要としないことが分かる. そこで, SVMではカーネル関数と呼ばれる特殊な関数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mathcal {K} ( {\cdot} , {\cdot} )\, } を用い元のデータ構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \boldsymbol{x}, \boldsymbol{x}' \in \mathbb{R}^{N}\, } から直接構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\mathcal F}\, } の元構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \phi(\boldsymbol{x}),\phi(\boldsymbol{x}')\, } の内積構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \phi(\boldsymbol{x})^{T}\phi(\boldsymbol{x}')\, } を算出し, 双対問題の最適化により非線形の判別関数が求められる [1]. よく用いられる代表的なカーネル関数として, 多項式カーネル構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mathcal{K} (\boldsymbol{x}, \boldsymbol{x}' ) = \left( \boldsymbol{x}^{T}\boldsymbol{x}' + c \right)^{d}\,} やRBFカーネル 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mathcal{K} (\boldsymbol{x},\boldsymbol{x}' ) = \exp\left( -\| \boldsymbol{x} - \boldsymbol{x}' \|^{2}/ \sigma^{2} \right )\, } , (ただし構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle d\, } は自然数のパラメータ, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle c,\sigma\, } は実数のパラメータである) などがある.


　カーネル関数の値を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i-j\, } 成分とする構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle M\, } 次の対称行列を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle K\, } とすれば, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle K\, } が半正定値行列となるようなカーネル関数をMercerカーネル(あるいは半正定値カーネル)と呼び, このようなカーネル関数であれば,構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mathcal{K} ( \boldsymbol{a}_{i}, \boldsymbol{a}_{j} )=\phi(\boldsymbol{a}_{i})^{T}\phi(\boldsymbol{a}_{j})\, } となる特徴空間への変換構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \phi(\cdot)\, } が存在することが保証される. 多項式カーネルやRBFカーネルはMercerカーネルである [5].また, Mercerカーネルを用いるのであれば, 対応した双対問題は常に凹二次関数の最大化となり, 通常の二次計画問題の解法を用いれば大域的に最適化が可能である.

　すなわち, 双対問題の最適解を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \alpha_{j}^{*}\, } とすれば, カーネル関数を用いた場合には, 次の非線形な判別関数が求められることとなる.


構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(\boldsymbol{x}) = \sum_{j \in SV}\alpha_{j}^{*} y_{j} \mathcal{K} ( \boldsymbol{x}, \boldsymbol{a}_{j} )- b^{*}.\, } 　　　　　構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (6)\, }


　すなわち, 判別関数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(\cdot)\, } は, サポート・ベクター に対応するカーネル関数の重ね合せとして算出されると見ることができる.


参考文献

[1] B. E. Boser, I. M. Guyon, and V. N. Vapnik, "A training algorithm for optimal margin classifiers," in Proceedings of the fifth annual workshop on Computationa learning theory, USA, 144-152, 1992.

[2] C. Cortes and V. Vapnik, "Support-vector networks," Machine learning, 20 (1995), 273-297.

[3] T. Joachims, "Making large-scale support vector machine learning practical," in Advances in Kernel Methods, B. Schölkopf, C. Burges, and A. Smola, eds., The MIT Press, 169-184, 1999.

[4] J. C. Platt, "Fast training of support vector machines using sequential minimal optimization," in Advances in Kernel Methods, B. Schölkopf, C. Burges, and A. Smola, eds., The MIT Press, 185-208. 1999.

[5] J. Shawe-Taylor and N. Cristianini, Kernel Methods for Pattern Analysis, Cambridge University Press, 2004.

[6] V. N. Vapnik, The nature of statistical learning theory, Statistics for Engineering and Information Science, Springer-Verlag, 2000.

「https://orsj-ml.org/orwiki/wiki/index.php?title=《サポート・ベクター・マシン》&oldid=7828」から取得