VC dimension Support Vector Machines Kernel Method

Slides:



Advertisements
Similar presentations
Maxent model への挑戦 - 驚きとドキドキ感の理論 - 大野ゆかり Phillips et al. (2006) Maximum entropy modeling of species geographic distributions. Ecological Modeling 190:
Advertisements

第 5 章 2 次元モデル Chapter 5 2-dimensional model. Contents 1.2 次元モデル 2-dimensional model 2. 弱形式 Weak form 3.FEM 近似 FEM approximation 4. まとめ Summary.
要論B 講義日程 12/18 1. Overview,ニユーラルネット (福水) 2. グラフィカルモデル (土谷)
Pattern Recognition and Machine Learning 1.5 決定理論
Extremal Combinatorics 14.1 ~ 14.2
上坂吉則 尾関和彦 文一総合出版 宮崎大輔2003年6月28日(土)
大規模データの線形識別 Recent Advances of Large-scale Linear Classification
Bias2 - Variance - Noise 分解
Bias2 - Variance - Noise 分解
整数計画法を用いた ペグソリティアの解法 ver. 2.1
初級ミクロ経済学 -ゲーム理論入門- 2014年12月15日 古川徹也 2014年12月15日 初級ミクロ経済学.
第 七 回 双対問題とその解法 山梨大学.
Probabilistic Method 6-3,4
VC dimension Support Vector Machines Kernel Method
誤差の二乗和の一次導関数 偏微分.
ガウス過程による回帰 Gaussian Process Regression GPR
第6章 カーネル法 修士2年 藤井 敬士.
発表日:平成15年4月25日 担当者:時田 陽一 担当箇所:第3章 誤差評価に基づく学習 3.1 Widrow-Hoffの学習規則
Linear Relaxation for Hub Network Design Problems
パターン認識とニューラルネットワーク 栗田多喜夫 2018/11/8 早稲田大学大学院理工学研究科講義.
サポートベクターマシン によるパターン認識
独立成分分析 1.問題は何か:例:解法:全体の見通し 2007/10/17 名雪 勲.
決定木とランダムフォレスト 和田 俊和.
混合ガウスモデルによる回帰分析および 逆解析 Gaussian Mixture Regression GMR
人工知能特論 9.パーセプトロン 北陸先端科学技術大学院大学 鶴岡 慶雅.
モデルの逆解析 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
7.4 Two General Settings D3 杉原堅也.
情報理工学系研究科 数理情報学専攻 数理第四研究室 博士三年 指導教員: 駒木 文保 准教授 鈴木 大慈 2008年8月14日
Songzhu Gao, Tetsuya Takiguchi, Yasuo Ariki (Kobe University) 
独立成分分析 5 アルゴリズムの安定性と効率 2007/10/24   名雪 勲.
VC dimension Support Vector Machines Kernel Method
第5章 特徴の評価とベイズ誤り確率 5.5 ベイズ誤り確率の推定法 [1] 誤識別率の偏りと分散 [2] ベイズ誤り確率の上限および下限
第6章 特徴空間の変換 6.1 特徴選択と特徴空間の変換 6.2 特徴量の正規化 平成15年5月23日(金) 発表者 藤井 丈明
訓練データとテストデータが 異なる分布に従う場合の学習
第7章 疎な解を持つカーネルマシン 修士2年 山川佳洋.
Data Clustering: A Review
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
パターン認識特論 担当:和田 俊和 部屋 A513 主成分分析
1-Q-9 SVMとCARTの組み合わせによる AdaBoostを用いた音声区間検出
部分的最小二乗回帰 Partial Least Squares Regression PLS
Nightmare at Test Time: Robust Learning by Feature Deletion
Number of random matrices
「データ学習アルゴリズム」 第3章 複雑な学習モデル 報告者 佐々木 稔 2003年6月25日 3.1 関数近似モデル
ナップサック問題 クマさん人形をめぐる熱いドラマの結末.
わかりやすいパターン認識 第7章:部分空間法  7.1 部分空間法の基本  7.2 CLAFIC法                  6月13日(金)                  大城 亜里沙.
第3章 線形回帰モデル 修士1年 山田 孝太郎.
法数学のための 機械学習の基礎 京大(医) 統計遺伝学分野 山田 亮 2017/04/15.
サポートベクターマシン Support Vector Machine SVM
京都大学 化学研究所 バイオインフォマティクスセンター
第9章 学習アルゴリズムとベイズ決定側 〔3〕最小2乗法とベイズ決定側 発表:2003年7月4日 時田 陽一
HMM音声合成における 変分ベイズ法に基づく線形回帰
距離空間ピラミッドを用いた LLCによる3次元物体認識
パターン認識 ークラスタリングとEMアルゴリズムー 担当:和田 俊和 部屋 A513
Max Cut and the Smallest Eigenvalue 論文紹介
土木計画学 第12回(1月14日) 計画における代替案の作成2 担当:榊原 弘之.
パターン認識 ークラスタリングとEMアルゴリズムー 担当:和田 俊和 部屋 A513
``Exponentiated Gradient Algorithms for Log-Linear Structured Prediction’’ A.Globerson, T.Y.Koo, X.Carreras, M.Collins を読んで 渡辺一帆(東大・新領域)
人工知能特論II 第8回 二宮 崇.
データ解析 静岡大学工学部 安藤和敏
7.8 Kim-Vu Polynomial Concentration
パターン認識特論 ADA Boosting.
行列 一次変換,とくに直交変換.
パターン認識特論 ADA Boosting.
モデルの微分による非線形モデルの解釈 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
音響伝達特性を用いた単一チャネル 音源位置推定における特徴量選択の検討
パターン認識特論 カーネル主成分分析 和田俊和.
「データ学習アルゴリズム」 第3章 複雑な学習モデル 報告者 佐々木 稔 2003年8月1日 3.2 競合学習
重力波解析ライブラリKagaliのためのAntenna pattern functionの作成
グラフ-ベクトル変換を用いたグラフ構造表現による一般物体認識
混合ガウスモデル Gaussian Mixture Model GMM
Presentation transcript:

VC dimension Support Vector Machines Kernel Method パターン認識特論 VC dimension Support Vector Machines Kernel Method

汎化と分化の制御 中間(隠れ層)素子数の設定 中間層の素子数を増やせ ば分化が進み、減らせば 汎化が進む

VC dimension ある空間で、ある関数形で表現可能な識別面を設定し,特徴ベクトルを2クラスに分類する問題を考える。 h個の特徴ベクトルに対して任意のラベリングをしても、識別面のパラメータをうまく選べば、これらの特徴点が分離可能になるとする。このような特徴点の最大個数hを、この空間中でのこの識別関数のVC(Vapnik-Chervonenkis) dimensionと呼ぶ。 注意すべきことは、上述のようなh個の特徴ベクトルが存在するということであり、任意の特徴ベクトルの配置に対して上記が成立する必要は無いということである。

VC dimension の例 2次元平面上での線形識別面(h=3)

VC dimension の性質 期待リスク 実リスク 期待リスクの上限 VC Confidence y:教師信号、f():識別関数、h:VC次元、l: サンプル数、 1-η:上限が正しい確率

VC Confidence の性質 η=0.05: 上限が正しい確率=0.95の場合

SRM:Structural Risk Management  Remp(α)が小さく,且つ,VC confidence が小さいとき、リスクの上限が低く押さえられる。 ある識別関数の集合を、VC dimension の値に応じて部分集合に分けておく。そして、各集合の中でそれぞれRemp(α)の最小化を行う。そして、 Remp(α)+VC confidence が一番小さいものを選べば、その識別関数の集合の中で最適な識別機械が構成できる。

Linear Support Vector Machine: Separable Case どんな識別面が「良い」識別面か? Margin 線形識別面から、最近傍の サンプル点までの距離が最 大になるように識別面を設 定すればよい。 B A

Linear Support Vector Machine: Separable Case(問題) 識別面の方程式   x・w+b=0 とし、教師信号t を±1とする。 また、Bの点が x・w+b≧1、 Aの点が x・w+b≦-1 を満足するとする。 条件1 このとき、各サンプル(xi ,ti)は、   ti(xi・w+b)-1 ≧0 を満足する。 B A

Linear Support Vector Machine: Separable Case(何をすべきか) このとき、識別面に最も近いB、Aの点はそれぞれ  x・w+b=1, x・w+b= -1 上に存在する。原点からこれ らの超平面までの距離は、 それぞれ | 1-b | / ||w||, |-1-b | / ||w|| なの で2平面間の距離(Margin)は、 2/||w||となる。すなわち、 ||w|| が小さくなるほど、Marginが 大きくなる。 A B Margin したがって、前述の条件1の下 で||w||を最小化すれば良い。

Linear Support Vector Machine: Separable Case(定式化と解法) この問題は、Lagrange の未定係数法により、以下の関数を最小化 する問題に帰着する(後述のKuhn-Tucker条件を使うことが前提)。 Lp =1/2 ||w||2 –Σαi( ti(xi・w+b) –1) i 右辺第1項はMarginを最大化する項、第2項はすべてのデータが正 しく識別されるための項である。このとき、∂Lp/∂w, ∂Lp/∂b とも に0になるという条件から式の簡単化が行え,結果的に上の式は Σαi–1/2Σαiαj ti tj xi・xj i i,j となる。これを∂Lp/∂ w =0、 ∂Lp/∂b =0、 ti(xi・w+b) –1≧0、 αi≧0、αi( ti(xi・w+b) –1)=0 という条件(Kuhn-Tucker条件) のもとで最小化すれば良い。(これらの等式不等式制約は、ある正 則化条件の下で全て線形化することができ、結果的に2次計画問 題になる。この問題は、内点法などを用いて解くことができる。)

Linear Support Vector Machine: Separable Case(何が得られるか) 明らかにαi ≠0となるxiが識別面に最も近い点となり、この点では、 ti(xi・w+b) –1=0 となる。このような点をサポートベクターと呼ぶ. 最適化後には、 Σαi( ti(xi・w+b) –1)=0 i となり、Support Vector以外ではαi =0 。 また、最適なbは、A,BのSupport Vector のうち任意の2つxA , xB および最適化 されたwから、     b= -½ w ・ ( xA + xB ) と計算される。 Support Vectorの標識 集合をSvtとすると、最適識別面は次式 で表される。    Σ tiαi(xi・ (x -½( xA + xB ) )=0 i∈Sv また、    w =Σ tiαixi   となる。        i∈Sv A B Margin

実例 http://svm.cs.rhul.ac.uk/pagesnew/GPat.shtml

Linear Support Vector Machine: Non-Separable Case(どうすれば良いか) 線形識別可能でないとき、前述の方法では安定な解が得られない。 B 学習サンプルを用いたとき のエラーを許容する定式化 を行う。Soft Marginの導入 B A A B A A B B A B A A ? A B A

Linear Support Vector Machine: Non-Separable Case(何を最適化するか) 識別面の方程式 x・w+b=0、教師信号tを±1とする。 また、Bの点が xi・w+b≧1-ξi 、Aの点がx・w+b≦-1+ξi を満足するとする。ξiは、 スラック変数と呼ばれる0以上の変数。 このとき、各サンプル(xi ,ti)は、   ti(xi・w+b)-1+ξi ≧0 を満足する。また、Σξiは、 i トレーニング時のエラーの総和 を表している。したがって、最小 化の対象を 1/2 ||w||2 +CΣξiとすれば 線形分離不可能な場合にも対 処でき、トレーニング時のエラー も最小化できる。 B B A A B A A B B A B A A ? A B A

Linear Support Vector Machine: Non-Separable Case(定式化と解法) この問題 は、    Lp =1/2 ||w||2 +CΣ ξi – Σαi( ti(xi・w+b) –1+ξi)-Σμi ξi   i i i となり、式変形により先の問題と同様に、 Σαi–1/2Σαiαj ti tj xi・xj   i i,j を最大化する問題となる。 この場合,Kuhn-Tucker条件は異なるが、 同様に内点法などで解くことができる。 この場合のサポートベクターはαi ≠0 かつξi =0となるxiであり、 ti(xi・w+b) –1=0 を満足する。 ξi ≠0となる点では、誤識別が起きて いる。

実例 http://svm.cs.rhul.ac.uk/pagesnew/GPat.shtml

Non-Linear Support Vector Machine: Kernel Method(アイデア) 識別面が線形であっても入力xを非線形変換φ(x)で次元を拡張す れば、元の空間で非線形識別面を構成したのと同じことになる。 例: 入力xを(x, x2)に変換して、その空間で線形識別面を構成することはもとの空間で2次式で表される識別面を構成したことと等価である. 疑問点:計算が複雑になるのではないか?次元が上がると、膨大なメモリが必要ではないか? 答え:次元拡張しても、内積の形でしかφ(x)を使わないのであれ ば、ほとんど同様の方法で、SVMが構成できる。このときに使う φ(x)の内積のことをkernelと呼ぶ。 K(x, y)= φ(x)・ φ(y)

Non-Linear Support Vector Machine: Kernel Method を用いたSVM Σαi–1/2Σαiαj ti tj xi・xj   i i,j を最大化する問題が、 Σαi–1/2Σαiαj ti tj K(xi , xj ) を最大化する問題になるだけで、本質的な問題の構造に影響を与 えない。このときの最適識別面は、    Σ tiαi(K(xi , x) -½( K(xi , xA )  + K(xi , xB ) ) =0 i∈Sv となる 。

Non-Linear Support Vector Machine: Kernel の拡張  Hij = ti tj K(xi , xj )とすれば、 Σαi–1/2Σαiαj ti tj K(xi , xj )=Σαi–1/2Σαi Hijαj   i i,j          i i,j となる。この式の最大化が行える条件は、行列[Hij]の固有値が全 て正であることである。 このためにK(x , y )はMercerの条件と呼ばれる次式を満足するよう に選ばれることが多い。 ∞ K(x , y ) =ΣCp(xi・xj)pかつ、Cpが一様収束。                     p=0 この条件を満足するものとしては、次のようなものがある。 および、(x・y)p 多項式カーネル Radial Basis Function(RBF) κとδの選び方によっては、条件を満足しない

実例 http://svm.cs.rhul.ac.uk/pagesnew/GPat.shtml

SVMの性質(準備) Gap Tolerant Classifiers 球内の点を shutter する問題。Gapの中と円の外の点は無視する。以下は2次元平面上の直径2の場合、M≦3/2, h=3, 3/2<M<2, h=2, 2≦M, h=2

SVMの性質(準備) Gap Tolerant Classifiers   h≦min{「D2/M2 ,n}+1 Gap Tolerant Classifier (GTC) を用いた Structural Risk Minimization.: トレーニングを行い、直径を変えて複数のGTCを得る。そして、そのVC dimension とトレーニングエラーからリスクの上限を計算し、最適なGTCを決定する。 得られたGTCは、超球の外部を見ないという点だけ がSVMと異なる。 SVMの場合、 VC dimension は、データに依存して変化するため、一概には決められないが、上述の上限以下であることは示されている。(実際の実験例では、理論上界の約1/100以下のリスク値が得られている。)

SVMの性質(1) マージンとリスクの関係:GTCの議論から,マージンが大きいほどVC次元が下がると言える。特殊な例として、以下の定理が示されている。「サンプル数l-1でトレーニングされた原点を通過する最適識別面のエラーの期待値は、次式で与えられる。」   また、期待リスクRは、Remp+λ/2 ||w||2 とも表される。 サポートベクターの個数とリスクの関係(線形分離可能な場合) サポートベクターを除去して学習した識別面に、サポートベ クターをテストデータとして与えたとき、誤りが生じ得るため。

SVMのTutorial C. J. C. Burges. A Tutorial on Support Vector Machines for Pattern Recognition. Knowledge Discovery and Data Mining, 2(2), 1998. A detailed tutorial on Support Vector machines for the classification task, from background material (e.g. VC dimension, structural risk minimization) through notes on training algorithms. Many examples are given. A. J. Smola and B. Schölkopf. A Tutorial on Support Vector Regression. NeuroCOLT Technical Report NC-TR-98-030, Royal Holloway College, University of London, UK, 1998. This tutorial gives an overview of the basic ideas underlying Support Vector (SV) machines for regression and function estimation. Furthermore, it includes a summary of currently used algorithms for training SV machines, covering both the quadratic (or convex) programming part and advanced methods for dealing with large datasets. Finally, some modifications and extensions that have been applied to the standard SV algorithm are mentioned, and it discusses the aspect of regularization and capacity control from a SV point of view. B. Schölkopf. Support vector learning, 1999. Tutorial given at DAGM'99.

SVMのプログラム Nearest Point Algorithm. by Sathiya Keerthi (in FORTRAN). SVM Java Applet. by Chris Burges et al. BSVM. A decomposition method for bound-constrained SVM formulations. QP SVM Classification and Regression. Fortran Implementation. Chunking Code. by C. Saunders, M. O. Stitson, J. Weston, L. Bottou, B. Schölkopf, and A. Smola at Royal Holloway, AT&T, and GMD FIRST (Documentation). Interior Point Optimizer for SVM Pattern Recognition. by Alex Smola. LEARNSC. SVM, NN and FL MATLAB based user-friendly routines. LIBSVM. An SVM library with a graphic interface. looms. a leave-one-out model selection software based on BSVM. mySVM. SVM implementation for pattern recognition and regression. mySVM and SVMlight for Windows. SVM implementation for Windows, uses Microsoft Visual C++ 6.0. Sequential Minimal Optimization. by Xianping Ge. SMOBR. SMOBR is an implementation of the original Sequential Minimal Optimisation proposed by Platt written in C++. SvmFu. by Ryan Rifkin. SVMLight. by Thorsten Joachims. SVM/LOO. Matlab code for SVM incremental learning and decremental unlearning (LOO validation). SVM/optima. SVM QP routines in Fortran for classification/regression. SVMTorch. Support Vector Machine for Large-Scale Regression and Classification Problems. Matlab SVM Toolbox. by Steve Gunn. Matlab SVM Toolbox. Matlab implementation in the style of SVMlight, can train 1-norm and 2-norm SVMs. OSU SVM Classifier Matlab Toolbox. A matlab toolbox with a C++ mex core to fast implement the SVM classifiers. SVM Toolbox. Object Oriented MATLAB Support Vector Machine Toolbox, including C++ MEX implementation of the sequential minimal optimisation algorithm.