18

カーネルのトリックは、非線形の問題を線形の問題にマッピングします。

私の質問は:
1. 線形問題と非線形問題の主な違いは何ですか? これら 2 つのクラスの問題の違いの背後にある直感は何ですか? また、カーネルのトリックは、非線形問題で線形分類器を使用するのにどのように役立ちますか?
2. 2 つのケースで内積が重要なのはなぜですか?

ありがとう。

4

5 に答える 5

44

分類問題に関して線形問題と言う場合、通常、線形分離可能な問題を意味します。線形分離可能とは、入力変数の線形結合である 2 つのクラスを分離できる関数があることを意味します。たとえば、2 つの入力変数x1およびがある場合、関数が出力を予測するのに十分な数値およびx2がいくつかあります。2 次元ではこれは直線に対応し、3 次元では平面になり、より高次元の空間では超平面になります。theta1theta2theta1.x1 + theta2.x2

2D/3D で点と線について考えると、これらの概念についてある程度の直感を得ることができます。これは非常に不自然な例のペアです...

2D 散布図

これは線形不可分問題のプロットです。赤点と青点を分ける直線はありません。

3D 散布図

ただし、各点に追加の座標を与えると (具体的1 - sqrt(x*x + y*y)には...これは人為的なものだと言いました)、赤と青の点は を通る 2 次元平面で分離できるため、問題は直線的に分離可能になりますz=0。

願わくば、これらの例がカーネル トリックの背後にある考え方の一部を示していることを願っています。

問題をより多くの次元を持つ空間にマッピングすると、問題が線形分離可能になる可能性が高くなります。

カーネル トリックの背後にある 2 つ目のアイデア (およびそれが非常にトリッキーである理由) は、通常、非常に高次元の空間で作業するのは非常に扱いにくく、計算コストが高くつくということです。ただし、アルゴリズムがポイント間のドット積 (距離と考えることができます) のみを使用する場合は、スカラーの行列を操作するだけで済みます。実際にマッピングを行ったり、高次元データを処理したりする必要なく、高次元空間で暗黙的に計算を実行できます。

于 2009-07-19T09:40:55.237 に答える
35

線形サポート ベクター マシン (SVM)などの多くの分類器は、線形分離可能な問題、つまり、クラス 1 に属する点がクラス 2 に属する点から超平面によって分離できる問題のみを解くことができます。

多くの場合、直線的に分離できない問題は、変換 phi() をデータ ポイントに適用することで解決できます。この変換は、ポイントを特徴空間に変換すると言われています。機能空間では、ポイントが線形に分離可能になることが期待されます。(注: これはまだカーネルのトリックではありません。ご期待ください。)

特徴空間の次元が高いほど、その空間で線形に分離できる問題の数が増えることがわかります。したがって、特徴空間を可能な限り高次元にすることが理想的です。

残念ながら、特徴空間の次元が増加するにつれて、必要な計算量も増加します。ここで、カーネル トリックの出番です。多くの機械学習アルゴリズム (SVM を含む) は、データ ポイントに対して実行する唯一の操作が 2 つのデータ ポイント間のスカラー積であるように定式化できます。(x1 と x2 の間のスカラー積を で表し<x1, x2>ます。)

ポイントを特徴空間に変換すると、スカラー積は次のようになります。

<phi(x1), phi(x2)>

重要な洞察は、このスカラー積の計算を最適化するために使用できるカーネルと呼ばれる関数のクラスが存在することです。カーネルは、次K(x1, x2)のプロパティを持つ関数です。

K(x1, x2) = <phi(x1), phi(x2)>

いくつかの関数 phi() に対して。言い換えると、高次元の特徴空間 (phi(x1) と phi(x2) が存在する場所) に変換する必要なく、低次元のデータ空間 (x1 と x2 が「存在する」場所) でスカラー積を評価できます。 ") -- しかし、高次元の特徴空間に変換する利点はまだあります。これはカーネルトリックと呼ばれます。

Gaussian kernelなどの多くの一般的なカーネルは、実際には、無限次元の特徴空間に変換する変換 phi() に対応しています。カーネルのトリックにより、この空間内の点を明示的に表す必要なく、この空間内のスカラー積を計算できます (これは明らかに、メモリ容量が有限のコンピューターでは不可能です)。

于 2009-07-19T06:09:44.773 に答える
3

主な違い (実用的な目的) は次のとおりです。線形問題には解決策がある (そして簡単に見つけられる) か、解決策がまったくないという明確な答えが得られます。問題をまったく知る前に、あなたはこれをよく知っています。線形である限り、答えが得られます。早く。

これの背後にある直感は、ある空間に 2 本の直線がある場合、それらが交差しているかどうかを確認するのは非常に簡単であり、交差している場合は場所を簡単に知ることができるという事実です。

問題が直線的でない場合、問題は何でもかまいませんが、ほとんど何もわかりません。

2 つのベクトルの内積は、次のことを意味します。対応する要素の積の合計。あなたの問題が

c1 * x1 + c2 * x2 + c3 * x3 = 0

(通常は係数 c を知っていて、変数 x を探している場合)、左辺はベクトル(c1,c2,c3)との内積(x1,x2,x3)です。

上記の方程式は (ほぼ) 線形問題のまさに定義であるため、内積と線形問題の間には関係があります。

于 2009-07-18T21:01:57.497 に答える
2
  1. 線形方程式は同次であり、重ね合わせが適用されます。他の既知のソリューションを組み合わせてソリューションを作成できます。これが、フーリエ変換がうまく機能する理由の 1 つです。非線形方程式は同次ではなく、重ね合わせは適用されません。非線形方程式は通常、反復的なインクリメンタル手法を使用して数値的に解く必要があります。
  2. 内積の重要性を表現する方法がわかりませんが、2 つのベクトルを取り、スカラーを返します。確かに、スカラー方程式の解は、ベクトルまたは高次のテンソル方程式を解くよりも簡単です。これは、処理するコンポーネントが少ないためです。

この問題に関する私の直感は物理学に基づいているため、AI に変換するのに苦労しています。

于 2009-07-18T20:56:43.573 に答える
1

次のリンクも役立つと思います...
http://www.simafore.com/blog/bid/113227/How-support-vector-machines-use-kernel-functions-to-classify-data

于 2014-02-06T11:49:29.490 に答える