機械学習のアルゴリズム（2） - サポートベクターマシン（SVM）の基礎

SVM に関する論文や書籍は数多くあります。Qiang 兄弟の言葉を引用すると、「SVM は応用数学者が真に適用できるアルゴリズムです。」ほとんどの一般人にとって、SVM に関係する数学を完全に理解することは非常に困難です。したがって、これらの一般の人々に理解してもらうためには、関係する数学的知識を簡単な言葉で説明する必要があります。さらに、これらの数学を理解することは、他の内容を学ぶ際にも大いに役立ちます。私は大多数の普通の人の一人です。SVMを理解するために、多くの情報を読みました。ここで私の経験を共有したいと思います。

実は、SVMに関する中国語の資料は今かなりたくさん見つかりますが、個人的には人それぞれ理解が違うと感じたので、それについて書くことにしました。いくつかの類似点は間違いなく避けられませんが、それでも他の人とは違うものを書けることを願っています。さらに、この記事では数学についてあまり詳しく説明するつもりはなく（多くの記事で取り上げられているため）、タイトル「機械学習のアルゴリズム」（以前は「機械学習の数学」と呼ばれていました）のように、結論を簡単に述べようとしています。そのため、このシリーズの内容は、アプリケーションに重点を置くことになります。より詳細な数学的な説明が必要な場合は、参考文献を参照してください。

1. 線形分類器:

まず、非常に単純な分類問題（線形分離可能）を示します。下の図の黒い点と白い点を直線で分離する必要があります。明らかに、図の直線は必要な直線の 1 つです（このような直線は無数に存在する可能性があります）。

黒い点 = -1、白い点 = +1、直線 f(x) = wx + b とします。ここで、x と w はベクトルです。実際、これを f(x) = w1x1 + w2x2 … + wnxn + b という形式で書くことと同じです。ベクトル x の次元が 2 の場合、f(x) は 2 次元空間の直線を表します。x の次元が 3 の場合、f(x) は 3 次元空間の平面を表します。x の次元が n > 3 の場合、n 次元空間の n-1 次元超平面を表します。これらは比較的基本的な内容です。よくわからない場合は、微積分や線形代数を復習する必要があるかもしれません。

先ほど述べたように、黒と白の点をそれぞれ +1 と -1 に設定しました。そのため、どのカテゴリに属する​​かを予測する必要がある新しい点 x がある場合、sgn(f(x)) を使用して予測を行うことができます。sgn は符号関数を表します。f(x) > 0 の場合、sgn(f(x)) = +1 となり、f(x) < 0 の場合、sgn(f(x)) = –1 となります。

しかし、どうすれば完璧な境界線 f(x) を得ることができるのでしょうか?下の図の直線は、いくつかの可能なf(x)を表している。

非常に直感的な感覚は、与えられたサンプル内の最も近い点からこの直線をできるだけ遠ざけることです。この文章は少し読みにくいです。これを説明するいくつかの図を以下に示します。

*** 分類方法:

2番目の方法:

これら 2 つの分割方法のうち、どちらが優れていますか?直感的に言えば、セグメンテーションギャップが大きいほど良く、2 つのカテゴリのポイントが離れているほど良いと言えます。通常、ある人が男性か女性かを判断するときと同じように、間違った分類をすることは非常に困難です。これは、男性と女性の 2 つのカテゴリ間のギャップが非常に大きいため、より正確に分類できるためです。 SVM では最大周辺と呼ばれ、SVM の理論的基礎の 1 つです。ギャップを最小にする関数を分割面として選択する理由はたくさんあります。たとえば、確率の観点からは、信頼度が最も小さい点が信頼度が最も大きいことを意味します（奇妙に聞こえます）。実用的な観点からは、この効果は非常に良い、などです。ここでは詳細には触れませんが、結論としては問題ありません。:)

上図の赤と青の円で囲まれた点は、いわゆるサポートベクターです。

上の図は、前述のカテゴリのギャップを説明したものです。分類器の境界は f(x) であり、赤い線と青い線 (プラス平面とマイナス平面) はサポート ベクトルが配置されている平面であり、赤い線と青い線の間のギャップは最適化するカテゴリ間のギャップです。

M の式は次のとおりです。(高校の解析幾何学から簡単に入手できます。または、後でムーアの PPT を参照してください)

さらに、サポート ベクトルは、wx + b = 1 と wx + b = -1 の間の直線上にあります。これに、ポイントが属するカテゴリ y (覚えておいてください。y は +1 または -1 のいずれかです) を掛けると、サポート ベクトルの式 y(wx + b) = 1 が得られます。これにより、サポート ベクトルの表現が簡単になります。

サポート ベクトルが決定されると、セグメンテーション関数が決定され、2 つの問題は同等になります。サポート ベクトルを取得するもう 1 つの目的は、サポート ベクトルの背後にあるポイントが計算に参加する必要がなくなるようにすることです。これについては後で詳しく説明します。

このセクションの最後に、最適化して解決したい式を示します。

||w|| は w の双ノルムを意味し、これは上記の式 M の分母と同じ意味を持ちます。すでに得たように、M = 2 / ||w|| です。この式を *** することは、||w|| を最小化することと同じです。また、||w|| は単調関数なので、これに 2 乗と前の係数を加えることができます。慣れている人なら、この式が導出の便宜上のものであることはすぐにわかるでしょう。

この式にはいくつかの制限があります。完全に書き出すと、次のようになります。(元の質問)

st は subject to を意味し、次の制約条件下にあることを意味します。この単語は SVM の論文でよく見かけます。これは実際には制約付き二次計画法 (QP) 問題であり、凸問題です。凸問題とは、局所最適解が存在しないことを意味します。漏斗を想像してみてください。最初に漏斗のどこにボールを入れても、ボールは最終的に漏斗から落ちてしまいます。つまり、グローバル最適解が得られるということです。 st の後の制約は凸多面体とみなすことができます。私たちがすべきことは、この凸多面体の中で最適な解を見つけることです。これらの問題についてはここでは詳しく説明しません。詳しく説明すると、本 1 冊分でも長くなりすぎるからです。疑問がある場合はWikipediaを参照してください。

2. これを双対問題に変換し、ソリューションを最適化します。

この最適化問題は、ラグランジュ乗数法を使用して解決できます。KKT 条件の理論を使用すると、次の式のラグランジュ目的関数を直接作成できます。

この式を解くプロセスには、ラグランジュ双対性に関する関連知識が必要です (pluskid にはこの問題について具体的に議論した記事もあります)。また、特定の式の導出があります。興味がない場合は、最後の青い式で表現されている結論に直接ジャンプできます。導出のこの部分は、主に plukids の記事に基づいています。

まず、wとbに関してLを最小化し、wとbに関するLの偏微分をそれぞれ0に設定して、元の問題の式を取得します。

2つの方程式をL(w,b,a)に代入すると、双対問題の表現が得られます。

新しい問題とその制約は次のようになります (二重問題)。

これは最終的に最適化する必要がある式です。この時点で、線形分離問題の最適化式が得られます。

この方程式を解く方法は、SMO など、数多くあります。個人的には、このような制約付き凸最適化問題を解くことと、この凸最適化問題を得ることは、比較的独立した 2 つの事柄であると考えているため、この記事では、このトピックの解決方法についてはまったく説明しません。後で時間があれば、それについての記事を作成することができます :)。

3. 線形分離不可能なケース（ソフト区間）:

次に、線形分離可能性の仮定が制限的すぎるために線形分離可能性が不可能な場合について説明します。

下の図は、典型的な線形分離不可能な分類図です。直線を使用して 2 つの領域に分割することはできません。各領域には、1 色の点のみが含まれます。

この場合、分類器を使用する方法は 2 つあります。1 つは、曲線を使用して完全に分離する方法です。曲線は非線形な状況であり、後で説明するカーネル関数と特定の関係があります。

もう 1 つの方法は直線を使用することですが、分離可能性は保証されず、誤分類を許容することになります。ただし、誤分類を可能な限り合理的にするために、ペナルティ関数を追加する必要があります。実際、多くの場合、トレーニング中の分類関数の精度が高ければ高いほど良いというわけではありません。トレーニング関数の一部のデータは本質的にノイズであり、分類ラベルを手動で追加するときに誤って追加される可能性があるためです。トレーニング（学習）中にこれらの誤った点を学習すると、モデルは次にこれらのエラーに遭遇したときに必然的に間違いを犯します（たとえば、教師が講義中にある知識のポイントを説明する際に間違いを犯し、それを真実だと信じた場合、試験中に必然的に間違いを犯します）。この「ノイズ」を学習するプロセスはオーバーフィッティングと呼ばれ、機械学習ではタブーとされています。間違った知識を多く学習するよりも、学習する量を減らす方がよいでしょう。話題に戻りましょう。直線を使用して、線形に分離できない点を分離する方法は次のとおりです。

間違ったポイントに対してペナルティを追加することができます。間違ったポイントに対するペナルティ関数は、ポイントから正しい位置までの距離です。

上の図では、青と赤の線はサポートベクターの境界、緑の線は決定関数、紫の線は間違った点から対応する決定面までの距離を表しています。このようにして、元の関数にペナルティ関数を追加し、次の制限を課すことができます。

式の青い部分は、線形分離問題に基づいて追加されたペナルティ関数です。xiが正しい側にある場合、ε=0、Rはポイントの総数、Cはユーザーが指定した係数で、間違ったポイントにどれだけのペナルティが追加されるかを示します。Cが大きい場合、間違ったポイントは少なくなりますが、オーバーフィッティングがより深刻になる可能性があります。Cが非常に小さい場合、間違ったポイントが多くなる可能性がありますが、結果として得られるモデルが正しくない可能性があります。したがって、Cの選択方法については多くの知識がありますが、ほとんどの場合、経験的な試行を通じて得られます。

次のステップは同じで、ラグランジュの双対問題を解き、元の問題の双対問題の式を取得します。

青い部分は線形分離可能な双対問題表現との差異です。線形不可分性の場合に得られる双対問題の違いは、αの範囲が[0, +∞)から[0, C]に変化し、追加されたペナルティεによって双対問題の複雑さが増加しないことです。

4. カーネル関数:

先ほど分離不可能なケースについて話していたときに、非線形手法を使用すると、次に説明するカーネル関数のように、2 つのカテゴリを完全に分割する曲線を取得できることを述べました。

元の線形空間を高次元空間に変換し、超平面を使用して高次元線形空間を分割することができます。分類に役立てるために高次元空間を使用する方法を理解するための例を次に示します (例と画像は pluskid のカーネル関数部分からのものです)。

次の図は典型的な線形分離状況である。

しかし、これら 2 つの楕円のような点を高次元空間にマッピングすると、マッピング関数は次のようになります。

この関数を使用すると、上図の平面上の点を 3 次元空間 (z1、z2、z3) にマッピングし、マッピングされた座標を回転させると、線形に分離可能な点セットを取得できます。

別の哲学的な例を挙げると、世界にはまったく同じ物体は 2 つ存在しません。2 つの物体すべてに、次元を追加することで異なるものにすることができます。たとえば、2 冊の本は (色、内容) の点では同じかもしれません。著者の次元を追加することができます。それがうまくいかない場合は、ページ番号、所有者、購入場所、メモの内容などを追加することもできます。次元が無限次元に増加すると、任意の 2 つのオブジェクトを確実に分離できるようになります。

今得られた双対問題式を思い出してください。

赤い部分を次のように変換できます。

この式は線形空間を高次元空間にマッピングします。k(x, xj) には多くの種類がありますが、代表的なものを 2 つ挙げると次のようになります。

上記のカーネルは多項式カーネルと呼ばれ、下のカーネルはガウスカーネルと呼ばれます。ガウスカーネルは、元の空間を無限次元空間にマッピングします。さらに、カーネル関数には、線形条件と比較して余分な計算負荷がほとんどかからないなど、いくつかの優れた特性があります。ここでは詳細には触れません。一般的に言えば、問題に対して、異なるカーネル関数は異なる結果をもたらす可能性があり、通常は試行錯誤が必要になります。

5. その他の質問:

1) 多重分類問題の実行方法:

上で説明した分類はすべてバイナリ分類です。N 分類の場合、1 対 (N – 1) と 1 対 1 の 2 つの主な方法があります。前者の方法では、N 個の分類器をトレーニングする必要があります。i 番目の分類器は、カテゴリ i に属するか、カテゴリ i の補集合 (i の N-1 カテゴリを除く) に属するかを確認します。

後者の方法では、N * (N – 1) / 2 個の分類器をトレーニングする必要があります。分類器 (i, j) は、点が i に属するか j に属するかを判断できます。

この処理方法は SVM だけでなく、他の多くの分類でも広く使用されています。Lin 教授 (libsvm の作者) の結論によると、1 vs 1 方式は 1 vs (N – 1) 方式よりも優れています。

2) SVM は過剰適合しますか?

SVM はオーバーフィッティングを回避できます。1 つの方法は、前述のペナルティ関数の C を調整することです。もう 1 つの方法は、式を確認することです。min ||w||^2 は見覚えがありますか?この式は最小二乗回帰で見てきました。この式は関数をより滑らかにすることができるため、SVM は過剰適合が発生しにくい方法です。

参考資料:

主な参考文献は、Wikipedia（記事内にハイパーリンクがあります）、pluskidのSVMに関するブログ投稿、Andrew MooreのPPT（記事内の多くの画像はAndrew MooreのPPTから引用または改変されています）、prmlの4か所から引用されています。