サポートベクターマシン理論

サポートベクターマシン理論 — 概要

マージン最大化とカーネル法に基づく分類・回帰理論の全体像への入門ガイド

最大マージン分類器 — 分離超平面とマージン最大化の原理

分離超平面、決定関数、線形分離可能性、幾何マージン、法線ベクトルとバイアス

統計的学習理論 — SVMを基礎付ける学習の数理

経験リスク最小化、一様収束、一致性、Vapnik流の帰納原理、有限標本理論

VC次元 — 仮説集合の複雑さを測る組合せ指標

シャッタリング、成長関数、Sauerの補題、線形識別器のVC次元、容量制御

構造的リスク最小化 — 経験誤差と複雑性の均衡原理

SRM原理、入れ子仮説クラス、容量項と訓練誤差のトレードオフ、モデル階層選択

マージン依存汎化誤差界 — 性能保証の理論

マージン界、信頼区間、標本数と次元の関係、大マージンが汎化を助ける根拠

ハードマージンSVM — 線形分離可能データの最適超平面

制約付き最適化、正準超平面、マージン幅2/||w||、分離可能性の仮定と限界

ソフトマージンSVM — スラック変数による誤分類の許容

スラック変数ξ、L1/L2ペナルティ、C-SVM定式化、ノイズ耐性、マージン違反

ヒンジ損失 — SVMの損失関数と凸サロゲート

max(0,1-yf(x))、0-1損失の凸上界、二乗ヒンジ、ロジスティック損失との比較

正則化パラメータC — マージンと誤分類の均衡制御

Cの意味、過学習と過小適合、正則化経路、λ=1/(nC)対応、感度分析

ラグランジュ双対性 — 主問題から双対問題への変換

ラグランジュ関数、双対関数、弱双対と強双対、双対ギャップ、鞍点条件

KKT条件 — 最適性条件とサポートベクトルの特徴付け

相補性条件、停留条件、双対変数αの範囲、境界上/内部/違反点の三分類

双対問題の定式化 — 二次計画問題としての表現

凸二次計画、グラム行列による目的関数、箱制約、等式制約、内積のみへの依存

サポートベクトル — 解の疎性と境界点の役割

非零α、疎な解表現、マージン上の点、決定境界への寄与、記憶量削減効果

カーネルトリック — 内積置換による非線形化

k(x,x')による内積置換、明示写像不要の計算、非線形決定境界、双対形式との親和性

特徴空間と特徴写像 — 高次元空間への暗黙的埋め込み

写像φ、高次元での線形分離、Coverの定理、次元の呪いとカーネルの回避策

Mercerの定理 — カーネル関数の正定値性条件

積分作用素、固有関数展開、Mercer条件、有効なカーネルの判定基準

正定値カーネルとグラム行列 — 半正定値性の理論

グラム行列の半正定値性、対称性、カーネルの存在定理、条件付き正定値カーネル

再生核ヒルベルト空間 — RKHSと関数解析的基盤

再生性、評価汎関数の連続性、Moore-Aronszajnの定理、ノルムと滑らかさ

リプレゼンター定理 — 解の有限和表現の保証

訓練点カーネルの線形結合による最適解表現、正則化汎関数、無限次元問題の有限化

RBFカーネル — ガウスカーネルと帯域幅パラメータ

exp(-γ||x-x'||²)、γの選択、局所性、無限次元特徴空間、普遍近似性

多項式カーネル — 次数と係数による特徴の組合せ

(x·x'+c)^d、次数dと単項式特徴、同次/非同次形、数値スケーリングの注意

シグモイドカーネル — ニューラルネットとの接点

tanh型カーネル、パラメータ域による正定値性の破れ、2層パーセプトロンとの対応

文字列カーネル — 系列データ向け類似度設計

部分列カーネル、スペクトラムカーネル、k-mer、テキスト・DNA系列への適用

グラフカーネル — 構造データの類似度計算

ランダムウォークカーネル、部分グラフ比較、分子構造・化合物分類への応用

Fisherカーネル — 生成モデルから導くカーネル

対数尤度の勾配ベクトル、Fisher情報行列、生成モデルと識別学習の橋渡し

カーネルの構成則 — 和・積・合成による設計

カーネルの閉包性、和・積・スカラー倍、指数化、正規化カーネル、設計指針

普遍カーネル・特性カーネル — 表現能力の理論

普遍近似性、特性カーネルと分布の識別、稠密性、RBFの普遍性

カーネル正規化と前処理 — グラム行列の調整

単位ノルム正規化、中心化、スケーリング、対角強調、数値安定性の確保

二次計画ソルバ — QPによるSVM学習

凸二次計画、内点法、有効制約法、疎性の利用、メモリと計算量の壁

チャンキング法と分解法 — 大規模QPの部分問題分割

作業集合による部分問題化、逐次解の更新、収束保証、メモリ制約下の学習

SMOアルゴリズム — 2変数逐次最適化による解法

Plattの逐次最小最適化、2変数解析解、KKT違反点の選択、QPソルバ不要の学習

作業集合選択 — 分解法における変数選択戦略

最大違反対、勾配情報による選択、二次情報の利用、収束速度への影響

シュリンキングとキャッシュ — 実装上の高速化技法

非活性変数の除外、カーネル値キャッシュ、LIBSVM系実装の工夫、再検査手順

双対座標降下法 — 線形SVMの高速学習

座標ごとの閉形式更新、LIBLINEAR系の解法、疎特徴での効率、大規模文書分類

確率的劣勾配法 — 主問題を直接解く学習

Pegasos型解法、劣勾配、学習率スケジュール、ミニバッチ、収束率解析

カッティングプレーン法 — 切除平面による最適化

制約の逐次生成、バンドル法、構造化SVM学習への適用、精度と反復回数

線形SVMの大規模学習 — 高次元疎データでの効率化

疎ベクトル演算、特徴ハッシング、バイアス項の扱い、テキスト規模データへの適用

ν-SVM — サポートベクトル数を制御する定式化

νパラメータ、マージン誤り率の上界とSV率の下界、C-SVMとの等価性

最小二乗SVM — 等式制約による線形方程式化

LS-SVM、二乗誤差損失、線形系での求解、疎性の喪失とプルーニング

双子SVM・近接SVM — 2超平面による変種

クラスごとの近接超平面、2つの小規模QP、非平行超平面、計算量削減の狙い

サポートベクトル回帰 — ε不感応損失によるSVR

εチューブ、上下スラック変数、双対定式化、疎な回帰モデル、外挿の性質

ν-SVR — チューブ幅を自動調整する回帰定式化

νによるε自動決定、チューブ外率の制御、ε-SVRとのパラメータ対応関係

SVRの応用 — 時系列予測と関数近似

需要予測、負荷予測、非線形回帰、埋め込み次元の設計、残差診断

1クラスSVM — 教師なし外れ値検出の定式化

原点分離型定式化、ν制御の外れ値率、密度サポート推定、新規性検知

SVDD — 超球によるデータ領域記述

最小包含球、中心と半径の最適化、カーネル化、1クラスSVMとの関係

異常・新規性検知応用 — 監視と品質管理への展開

故障検知、侵入検知、製造ラインの品質監視、閾値設定、誤警報率管理

多クラス化: 一対他方式 — one-vs-restの構成

クラス数分の二値分類器、スコア比較による判定、不均衡化と較正の課題

多クラス化: 一対一方式 — ペア分類と投票

全ペア分類器、多数決、DAGによる高速判定、分類器数と学習コスト

単一最適化型多クラスSVM — 同時学習の定式化

Crammer-Singer型定式化、クラス間マージン、単一QPによる同時学習

構造化SVM — 系列・木・グラフ出力の学習

構造化出力、結合特徴写像、マージン再スケーリング、損失増強推論

ランキングSVM — 順位学習と情報検索応用

ペアワイズ制約、順位反転ペナルティ、検索結果ランキング、クリックログ学習

順序回帰SVM — 順序カテゴリの閾値モデル

順序ラベル、閾値付き超平面、等級評価、格付け予測への適用

多ラベル分類への適用 — ラベル集合の予測

二値関連法、ラベル相関、閾値調整、タグ付け・文書多重分類への応用

確率出力への較正 — スコアの確率変換

Plattスケーリング、シグモイド当てはめ、交差検証による較正、等張回帰との比較

不均衡データ対応 — クラス重みとコスト考慮学習

クラス別C、コスト行列、リサンプリング併用、少数クラス再現率の改善

再帰的特徴消去 — 重みに基づく特徴選択RFE

重みベクトルによる特徴順位付け、逐次削除、遺伝子選択への応用、安定性評価

モデル選択とパラメータ調整 — C/γの探索

交差検証、グリッドサーチ、対数スケール探索、ネストCV、過調整の回避

カーネルターゲットアライメント — カーネル良否の評価

グラム行列とラベル行列の整合度、カーネル選択基準、学習前スクリーニング

多重カーネル学習 — 複数カーネルの重み付き結合

MKL、凸結合の重み最適化、異種特徴の統合、スパース重みと解釈性

半教師ありSVM — ラベルなしデータの活用

トランスダクティブSVM、低密度分離仮定、S3VM、非凸最適化の難しさ

オンライン・逐次学習SVM — 増分減分アルゴリズム

逐次データへの追随、増分学習、忘却、KKT条件維持による厳密更新

Nyström近似 — グラム行列の低ランク近似

標本列による低ランク分解、ランドマーク選択、近似誤差、計算量O(nm²)化

ランダムフーリエ特徴 — シフト不変カーネルの明示近似

Bochnerの定理、ランダム射影特徴、線形化による高速学習、近似精度と次元

バジェット法・縮約SVM — サポートベクトル数の制限

SV上限付き学習、統合・破棄戦略、推論高速化、精度と圧縮率の均衡

コアセットによる高速化 — 最小包含球への帰着

コアベクターマシン、コアセット近似、超大規模データでの近似学習保証

Rademacher複雑度 — マージン界の現代的解析

経験Rademacher複雑度、カーネルクラスの容量、データ依存汎化界の導出

Leave-one-out誤差界 — SV数と汎化の関係

LOO誤差のSV数上界、スパン界、半径マージン界、モデル選択への利用

マージン分布と幾何 — マージンの統計的見方

マージン分布、最小マージンと平均マージン、ブースティング理論との対比

ロバストSVM — 外れ値・ラベルノイズ耐性の設計

打ち切り損失、ランプ損失、外れ値の影響抑制、非凸化と最適化戦略

スパースSVM — L1正則化と特徴の疎性

L1ノルム正則化、特徴選択の内在化、線形計画型SVM、解釈性の向上

不定値カーネル — 非正定値類似度の扱い

非正定値類似度行列、スペクトル修正、クライン空間的解釈、実務での対処法

カーネル法ファミリー — カーネルPCA等との関係

カーネルPCA、カーネルリッジ回帰、カーネル判別分析、共通基盤としてのRKHS

ガウス過程との比較 — ベイズ的カーネル法との対比

事後分布と点推定、予測分散の有無、共分散関数とカーネル、計算量比較

関連ベクターマシン — ベイズ的スパースモデルRVM

自動関連度決定、確率的出力、関連ベクトルの疎性、SVMとの精度・速度比較

パーセプトロンからの系譜 — 線形識別器の発展史

パーセプトロン、線形判別分析、最適分離超平面の着想、識別学習の潮流

SVMの誕生 — 1992年のカーネル版発表

Boser・Guyon・Vapnikによる最適マージン分類器とカーネルトリックの結合

ソフトマージンの提案 — 1995年の定式化確立

CortesとVapnikのサポートベクトルネットワーク論文、実データへの道を開いた拡張

Vapnikと学習理論の人々 — 理論創始者たち

Vapnik、Chervonenkis、統計的学習理論の形成、産業研究所での発展

テキスト分類応用 — 文書分類とスパム判定

BoW/TF-IDF特徴、高次元疎データ適性、カテゴリ分類、スパムフィルタ

画像認識応用 — 特徴量とSVMによる物体検出

HOG特徴と歩行者検出、顔検出、局所特徴とBoVW、スライディングウィンドウ

手書き文字認識 — ベンチマークでの実績

MNIST等の数字認識、多項式/RBFカーネルの高精度、仮想サンプルによる不変性

バイオインフォマティクス応用 — 配列と発現の分類

遺伝子発現による癌分類、タンパク質機能予測、配列カーネル、少数標本高次元

医療診断支援応用 — 疾患判別への活用

画像診断支援、検査値による判別、感度特異度評価、少数データでの堅実性

金融応用 — 信用リスクと市場予測

信用スコアリング、倒産予測、SVRによる価格予測、不均衡データと評価指標

リモートセンシング応用 — 衛星画像の分類

土地被覆分類、ハイパースペクトル画像、少数教師画素での高精度、帯域選択

音声・話者認識応用 — 音響特徴の分類

MFCC特徴、話者照合、GMMスーパーベクトルとの併用、系列カーネル

実装ライブラリ — 標準ツールと使い分け

LIBSVM、LIBLINEAR、scikit-learnのSVC/SVR、パラメータ既定値と注意点

前処理とスケーリング — 学習前のデータ整備

特徴の標準化・区間正規化、カテゴリ変数符号化、欠損処理、スケール差の悪影響

計算量とスケーラビリティ — 学習・推論コスト解析

学習のO(n²)〜O(n³)性、推論のSV数依存、メモリ要件、大規模化の障壁

深層学習との比較 — 表現学習時代の位置付け

特徴設計対表現学習、小規模データでの優位、深層特徴+SVM、解釈性と保証

ファジィSVM — 帰属度重み付けによる変種

標本ごとの重み付け、ノイズ点の影響低減、帰属度設計、外れ値混入データ対応

分散・並列SVM — 大規模データの分散学習

データ分割学習、カスケード構成、パラメータ集約、クラスタ環境での実装

GPU実装 — カーネル計算の並列高速化

グラム行列計算の並列化、行列演算ライブラリ活用、学習・推論の高速化事例

プライバシー保護SVM — 秘匿環境での学習

秘密計算、準同型暗号での推論、連合学習、差分プライバシー付き学習

敵対的頑健性 — 回避攻撃とSVMの脆弱性

敵対的摂動、回避攻撃・汚染攻撃、頑健最適化との関連、防御手法の研究

量子計算とカーネル法 — 量子SVMの探究

量子特徴写像、量子カーネル推定、量子優位性の検討、研究段階の位置付け

教育と可視化 — SVMの教え方と教材

2次元可視化デモ、マージンの図解、演習用データセット、講義カリキュラム設計

研究動向と再評価 — カーネル法の現代的展望

深層学習理論との接続、ニューラルタンジェントカーネル、カーネル法再評価の議論

サポートベクターマシン理論 — 退避・古典資料archive

旧版教科書、初期実装ドキュメント、歴史的論文ノートなど参照頻度の低い資料の保管