《サポート・ベクター・マシン》 - 版の履歴

2007年8月6日 (月) 17:31にKuwashimaによる

2007-08-06T17:31:21Z

2007年7月23日 (月) 06:53にOrsjwikiによる

2007-07-23T06:53:02Z

2007年7月23日 (月) 05:54にOrsjwikiによる

2007-07-23T05:54:38Z

差分を表示

2007年7月23日 (月) 01:29にOrsjwikiによる

2007-07-23T01:29:53Z

2007年7月23日 (月) 01:28にOrsjwikiによる

2007-07-23T01:28:44Z

Orsjwiki: "《サポート・ベクター・マシン》" を保護しました。 [edit=sysop:move=sysop]

2007-07-19T13:27:54Z

"《サポート・ベクター・マシン》" を保護しました。 [edit=sysop:move=sysop]

2007年7月16日 (月) 14:09に220.104.197.230による

2007-07-16T14:09:16Z

2007年7月12日 (木) 07:11に122.17.2.240による

2007-07-12T07:11:06Z

2007年7月12日 (木) 05:58に122.17.2.240による

2007-07-12T05:58:07Z

2007年7月7日 (土) 15:27に219.165.74.196による

2007-07-07T15:27:42Z

差分を表示

← 古い版		2007年8月6日 (月) 17:31時点における版
166行目:		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:近似・知能・感覚的手法\|さぽーとべくたーましん]]

@@ 3行目: / 3行目: @@
 　サポート・ベクター・マシン (SVM) は, 判別関数を求める教師付き学習法のひとつである.
-　今, <math>N\, </math>個の属性を持ったデータが<math>M\, </math>個与えられており,これを,<math>N\, </math>次元空間<math>\mathbf{R}^{N}\, </math>の点<math>\boldsymbol{a}_{1}, \boldsymbol{a}_{2},\ldots, \boldsymbol{a}_{M} \in \mathbf{R}^{N}\, </math>と考える. 各点<math>\boldsymbol{a}_{j}\ (j=1,2,\ldots,M)\, </math>は2種類のクラスのいづれか一方に属しており, 対応する2値のラベル<math>y_{j} \in \{-1,+1\}\, </math>が与えられているとする. このとき, ラベルの値にしたがって点を判別する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では線形関数を用いた判別を行う. <math>N\, </math>次元の法線ベクトル<math>\boldsymbol{w} \, </math>および実数<math>b\, </math>で定まる線形関数を<math>f(\boldsymbol{x}) = \boldsymbol{x}^{T}  \boldsymbol{w}- b\, </math> とすれば, 与えられたデータおよびラベルにしたがって,
@@ 54行目: / 54行目: @@
 \end{array} \right.</math></td>
 	<td>最大化 </td>
-            <td><math>\textstyle \frac{1}{2}\| \boldsymbol{w} \| \frac{2}{2} + C \ {\sum}_{j=1}^{M} \xi_{j}</math></td>
+            <td><math>\textstyle \frac{1}{2}\| \boldsymbol{w} \|^{2}_{2} + C \ {\sum}_{j=1}^{M} \xi_{j}</math></td>
 <td rowspan="4">　　　　<math>(3)\, </math></td>
 </tr>
@@ 81行目: / 81行目: @@
-ここで,<math>C\, </math>はあらかじめ設定された正の定数で, <math>\textstyle \| \boldsymbol{w} \|\frac{2}{2}\, </math>と<math>\textstyle {\sum}_{j=1}^{M} \xi_{j}\, </math>とのバランスをコントロールするパラメータである. また, <math>\textstyle \| \boldsymbol{w} \|\frac{2}{2}\, </math>は正則化項とも呼ばれ, これを小さくすることは判別関数に用いるデータの属性を少なくし, 過学習を防ぐ役割があるとされる [6]. 問題 (3) は, 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と呼ばれる定式化である.
 　通常は,この問題の双対問題を考え最適化を行う [5]. <math>\alpha_{1},\alpha_{2},\ldots,\alpha_{M}\, </math> を双対変数とすれば, 問題 (3) の双対問題は
@@ 132行目: / 132行目: @@
 さらに, 双対問題 (4) や主問題 (3) は, サポート・ベクター以外を全て取り除いても最適解は不変であり, これらの点はSVMでの判別にはまったく寄与していないことになる.
-　SVMの最大の特徴は, 双対問題(4)を応用することで非線形な判別関数を構成できる点にある. 非線形な判別関数を構成するためには, まず, 適当な非線形変換<math>\phi: \mathbf{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の最大の特徴は, 双対問題(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>上での線形な判別関数を求めれば, 元の空間で見れば非線形な判別関数を求めたこととなる.
-　ここで, 双対問題 (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 \mathbf{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> は実数のパラメータである) などがある.
+　ここで, 双対問題 (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> は実数のパラメータである) などがある.

@@ 47行目: / 47行目: @@
 <td rowspan="4"> <math>\left|
 \begin{array}{l}
 \\
 \\
@@ 94行目: / 93行目: @@
 <td rowspan="4"> <math>\left|
 \begin{array}{l}
 \\
 \\

← 古い版		2007年7月23日 (月) 01:28時点における版
5行目:		5行目:
	今, <math>N\, </math>個の属性を持ったデータが<math>M\, </math>個与えられており,これを,<math>N\, </math>次元空間<math>\boldsymbol{R}^{N}\, </math>の点<math>{ }_{1},{ }_{2},\ldots, { }_{M} \in \boldsymbol{R}^{N}\, </math>と考える. 各点<math>{ }_{j}\ (j=1,2,\ldots,M)\, </math>は2種類のクラスのいづれか一方に属しており, 対応する2値のラベル<math>y_{j} \in \{-1,+1\}\, </math>が与えられているとする. このとき, ラベルの値にしたがって点を判別する2クラスの判別問題を考える.		今, <math>N\, </math>個の属性を持ったデータが<math>M\, </math>個与えられており,これを,<math>N\, </math>次元空間<math>\boldsymbol{R}^{N}\, </math>の点<math>{ }_{1},{ }_{2},\ldots, { }_{M} \in \boldsymbol{R}^{N}\, </math>と考える. 各点<math>{ }_{j}\ (j=1,2,\ldots,M)\, </math>は2種類のクラスのいづれか一方に属しており, 対応する2値のラベル<math>y_{j} \in \{-1,+1\}\, </math>が与えられているとする. このとき, ラベルの値にしたがって点を判別する2クラスの判別問題を考える.

−	SVMでは線形関数を用いた判別を行う. <math>N\, </math>次元の法線ベクトルおよび実数<math>b\,\, </math>で定まる線形関数を<math>f( ) = { }^{T} \ - b\, </math> とすれば, ~~与えられたデータおよびラベ:ルにしたがって~~,	+	SVMでは線形関数を用いた判別を行う. <math>N\, </math>次元の法線ベクトルおよび実数<math>b\,\, </math>で定まる線形関数を<math>f( ) = { }^{T} \ - b\, </math> とすれば, 与えられたデータおよびラベルにしたがって,

@@ 8行目: / 8行目: @@
-:<math>
+<center>
 f({ }_{j}) = { }_{j}^{T}\ - b \left\{
 \begin{array}{ll}
@@ 16行目: / 17行目: @@
 \right.\quad j=1,2,\ldots,M
 \, </math>　　　　<math>(1)\, </math>
@@ 23行目: / 25行目: @@
-:<math>
+<center>
   \begin{array}{lll}
   {\displaystyle  { }_{j}^{T} \ - b + \xi_{j} \geq 1 }
@@ 31行目: / 34行目: @@
 \end{array}
 \, </math>　　　　<math>(2)\, </math>
@@ 36行目: / 40行目: @@
 <table>
 <tr>
@@ 67行目: / 74行目: @@
 	<td><math>\textstyle
        \xi_{j} \ge 0, \quad j=1,2,\ldots,M</math></td>
 </tr>
 </table>
@@ 77行目: / 87行目: @@
 <table>
 <tr>
@@ 101行目: / 114行目: @@
 <td></td>
 	<td><math>0 \leq \alpha_{j} \leq C,\quad j=1,2,\ldots,M</math></td>
 </tr>
 </table>
@@ 110行目: / 126行目: @@
-:<math> f( ) = { }^{T} \ ^{*} - b^{*}
+<center>
          = \sum_{j \in SV} \alpha_{j}^{*} y_{j}^{T} { }_{j} - b^{*}\, </math>　　　　　<math>(5)\, </math>
@@ 126行目: / 144行目: @@
-:<math>f() = \sum_{j \in SV}\alpha_{j}^{*} y_{j}
+<center>
                         { }_{j} - b^{*}.\, </math>　　　　　<math>(6)\, </math>

← 古い版	2007年7月19日 (木) 13:27時点における版
(相違点なし)

@@ 76行目: / 76行目: @@
 　通常は,この問題の双対問題を考え最適化を行う [5]. <math>\alpha_{1},\alpha_{2},\ldots,\alpha_{M}\, </math> を双対変数とすれば, 問題 (3) の双対問題は
-:　　　　<math>(4)\, </math>
-:最大化
+<table>
-:制約
+<tr>
-:<math>\begin{array}{ll}
+<td rowspan="4"> <math>\left|
-  & { \textstyle
+\begin{array}{l}
        - \frac{1}{2} \sum_{i=1}^{M}\sum_{j=1}^{M}
           y_{i}y_{j}{ }_{i}^{T}{ }_{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>
-   & { \textstyle
+</tr>
-       \sum_{j=1}^{M} y_{j} \alpha_{j}= 0,
+<tr>
-    }\\
+	<td>制約 </td>
-   & { 0 \leq \alpha_{j} \leq C,\quad j=1,2,\ldots,M
+           <td><math>\textstyle \sum_{j=1}^{M} y_{j} \alpha_{j}= 0,</math></td>
+</tr>
-\end{array}\, </math>
+<tr>

@@ 35行目: / 35行目: @@
 のもと,<math>\xi_{j}\, </math>の和とのノルムができるだけ小さくなる線形関数を考える. すなわち, 次の二次計画問題を解き<math>\,b\, </math>を算出する [2].
-:　　　　<math>(3)\, </math>
-:最大化
+<table>
-:制約
+<tr>
-:<math>
+<td rowspan="4"> <math>\left|
-\begin{array}{ll}
+\begin{array}{l}
-   &{  \textstyle \frac{1}{2}\| \| \frac{2}{2} + C \ {\sum}_{j=1}^{M} \xi_{j}}\\
+\\
-   &{  \textstyle
+\\
        { }_{j}^{T} \ - b + \xi_{j} \geq 1,
-          \quad \mbox{if } y_{j} = 1,}\\
+          \quad \mbox{if } y_{j} = 1,</math></td>
-   & {  \textstyle
+</tr>
        { }_{j}^{T} \ - b - \xi_{j} \leq -1,
-          \quad \mbox{if } y_{j} = -1,}\\
+          \quad \mbox{if } y_{j} = -1,</math></td>
-   & {  \textstyle
+</tr>
-       \xi_{j} \ge 0, \quad j=1,2,\ldots,M}
+<tr>
-\end{array}\, </math>
+<td></td>