SMO法でSVMの学習してみた - きちめも
SMO法はPRMLに名前はあるけど詳細が無かったので、別の本*1買ってきて読んで理解した気分になったのでコードを書いてみた。 コードはpythonで書いたのだが、アルゴリズム的に行列の計算が全く無かった。 実際に試した対象は学習データが200程度だったので、scipyとOpenOptで素直に2次計画問題を計算させた方が早かった気がしてもにょい。*2 データはPRMLのページからダウンロードしたものを使った。 今はRVMの節を読んでいる。まだ7章終わってない＞ω＜； #!/usr/bin/python # -*- coding: utf-8 -*- import sys import random from scipy import * from scipy.linalg import norm from scipy.io import read_array import matplotli
SVMの学習用アルゴリズムSMOを実装してみる - きしだのHatena
SVMは２次最適化問題になるので、それを勉強してみてはということだったのですが、SVMに特化したSMO(Sequential Minimal Optimisation)アルゴリズムがあるということなので、そちらをやってみました。 SVMの制約条件に というのがあって、yiは正例なら1、負例なら-1となる値なのですが、そうすると、ようするにこの条件は、正例のαの合計と負例のαの合計が等しくなるということを示してるわけです。 この条件をつかうと、ひとつαを操作したときには、ほかのαを操作して、正例と負例のバランスを取る必要があることがわかります。 で、このことを利用して、同時に２つのαを操作することにすると、解析的に一つ目のαが求められて、２つ目のαはそこから足し算引き算で求められてお徳かも、というのがSMOの考え方です。 問題は、いかに効率よく更新する２つのαを決めるかということになります。
SVMコード
SVM（SMO法）のコードを載せておきます。理論についてはこちらをどうぞ。 2011.9.18追記： ここでも書いたのですが，引数 target は -1 or 1 と設定頂く方が正しいはずです。(理論的にも正しいはず) 初出時は簡単なテストデータで動作確認を行っていたためか 0 or 1 でも動作確認が取れていたよう記憶しています。本格的に学習させる場合には 0 or 1 では学習が収束しませんでした。 大まかな流れ SMOではラグランジュ未定乗数が教師データの数量分作成されます。これらを下記の処理フローで更新していきます。 ラグランジュ乗数の更新評価は１つずつ順番に行い，全ての評価を終えたところで実際に更新が行われたかをチェックします。1件でも更新したものがあれば，更新の作業を続けていきます。 下記のコードでは，個々のラグランジュ未定乗数の更新チェックはexaminUpdate()で行
サポートベクターマシン
サポートベクターマシン 赤穂昭太郎 産業技術総合研究所 2006.7.6～7 統数研公開講座 「カーネル法の最前線―ＳＶＭ, 非線形データ解析, 構造化データ―」 目次 1. サポートベクターマシン(SVM)とは 2. SVMの仲間たち 3. 汎化能力の評価 4. 学習アルゴリズム 5. カーネル設計の基本 1.サポートベクターマシンとは？ • サポートベクターマシン＝ 「線形モデル＋高次元写像＋正則化」の一つ （ほかのカーネル法と基本的に共通） • 計算量を少なくするいくつかの工夫 – 凸２次計画法 – スパース表現 – カーネルトリック • ローカルミニマムの問題がない 識別問題 • 入力 x を二つのクラスに分類する関数 を学習する （１クラスあるいは３クラス以上の場合は後で考える） 例： 文字認識、遺伝子解析、データマイニング、 spam filter • 学習サンプルから学習 •
kernel-slide.dvi
カーネルマシン 赤穂 昭太郎 産総研 脳神経情報研究部門 情報数理研究グループ s.akaho@aist.go.jp http://www.neurosci.aist.go.jp/˜akaho/kernel.html 1. はじめに 2. 3. 4. 5. 6. 7. パーセプトロンからサポートベクタマシンへ カーネルマシンの一般性 SVM の汎化能力 いろいろなカーネル いろいろなカーネルマシン むすび 1 識別問題 y x1 x2 ... yi=-1 yi=1 xn x • 入力: • 出力: x∈ d y ∈ {1, −1} • 学習サンプル： (x1 , y1 ), . . . , (xn , yn ) 2 メモリベースド識別器 y x1 x2 ... y x1 x2 ... xn x xn x • × 完全メモリベースド • 正則化: なまし ⇒ カーネル •
再生核ヒルベルト空間!!(ｷﾘｯ - yasuhisa's blog
半教師あり学習の資料作りがあと"Manifold regularization"だけになったんだが、これがいままでより頭に入ってこない。今までの論文とかは他との差分を読めばおkというような感じだったが、差分取るもとのがない、って感じである。というわけで基礎体力が足りていない。この手のは論文じゃなくて本で勉強したほうが頭に入ってくる気がするので、この辺の本を読むことにしよう。 学習システムの理論と実現 作者: 渡辺澄夫,萩原克幸,赤穂昭太郎,本村陽一,福水健次,岡田真人,青柳美輝出版社/メーカー: 森北出版株式会社発売日: 2005/07/25メディア: 単行本購入: 2人 クリック: 10回この商品を含むブログ (9件) を見るカーネル多変量解析―非線形データ解析の新しい展開 (シリーズ確率と情報の科学) 作者: 赤穂昭太郎出版社/メーカー: 岩波書店発売日: 2008/11/27メディア
untitled
ＦＩＴ２００２ ２００２年９月２５日∼２８日 サポートベクター回帰の モデル選択 東京工業大学 計算工学専攻 杉山 将 教師付き学習（回帰） y1 x1 y2 2 yl f (x) : 学習したい関数 ˆ f (x) : 学習結果の関数 {xi , yi }li =1 : 訓練データ yi = f ( x i ) + ε i x 2 L xl εi i.i.d . 平均 0, 分散 σ 2 訓練データ {x i , yi } を用いて、 未知の f (x) にできるだけ近い fˆ (x) を求めよ l i =1 サポートベクター回帰 Vapnik (1995) 次式を最小にする fˆ ( x) を求めよ ⎡1 ˆ 2 C l ˆ ⎤ min⎢ f + ∑ f (xi ) − yi ⎥ ˆ ε f ∈H 2 l i =1 ⎣ ⎦ 滑らかさ Vapnik の ε
070809titech.dvi
池田: サポートベクトルマシンの漸近論 サポートベクトルマシンの漸近論 池田 和司 京都大学 情報学研究科 システム科学専攻 東京工業大学 総合理工学研究科 知能システム科学特別講義第 2 2–3 Aug 2007 池田: サポートベクトルマシンの漸近論 ランダムな直線群 問題: ある点のまわりにランダムに直線を引いた時， 点を含む領域は何角形になるだろうか． • この問題がパーセプトロンの学習理論において重要． 東京工業大学 総合理工学研究科 知能システム科学特別講義第 2 2–3 Aug 2007 池田: サポートベクトルマシンの漸近論 単純パーセプトロン 入力 (x1 , x2 , . . . , xN ) ∈ RN , 出力 y ∈ {+1, −1}. N y = sgn n=1 wn xn − h = sgn [w x] ⎧ ⎨+1 s ≥ 0,
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
統計数理研究所 公開講座「カーネル法の最前線 ―ＳＶＭ, 非線形データ解析, 構造化データ―」
Amazon.co.jp: カーネル多変量解析―非線形データ解析の新しい展開 (シリーズ確率と情報の科学): 赤穂昭太郎: 本