machine-learning - SVM 分類は常に一意の解を生成しますか?

Question

分離可能な線形分類器は、データを分類するために複数の境界を持つことができます。これが、SVM が最大のマージン (見えないデータの最小の一般化エラー) を持つ境界を選択する理由です。

SVM 分類は常に一意の解を生成しますか?

答えはハード マージン SVM とソフト マージン SVM に依存しますか?

Answer 1

はい、標準 SVM のソフト定式化とハード定式化の両方が凸最適化問題であるため、独自の大域的最適値があります。問題が非常に巨大な場合、近似法は正確なソルバーの代わりにそれらを使用するほど十分に倹約的であり、そのトレードオフの利点は検索時間を短縮することであるため、数値解法は純粋に大域的最適解を見つけられない可能性があると思います。

これらに対する典型的なアプローチは、逐次最小最適化です。いくつかの変数を固定して、変数の小さなサブセットを最適化し、目的関数を改善できなくなるまで、さまざまな変数で何度も繰り返します。それを考えると、グローバル最適をもたらさないような方法でこれらの問題を解決しようとする人がいるとは思えません。

もちろん、見つけた大域的最適値は、実際にはデータに適していない可能性があります。これは、モデル、ノイズの多いクラス ラベルなどがデータ生成プロセスをどれだけうまく表現しているかによって異なります。したがって、これを解決しても、絶対に正しい分類子などを見つけたことを保証するものではありません。

大まかな検索でこれについて見つけたいくつかの講義ノートを次に示します: (リンク)

凸性の主張に関するより直接的なリンクは次のとおりです: (リンク)

Answer 2

正則化のないハードマージン分類器の場合、SVM問題は線形制約のある強制二次計画問題に変換できます（解/正のマージンが存在すると仮定）。線形制約を伴う強制二次計画問題には固有のグローバル最小値があり、単純な最適化手法（最急降下法やパーセプトロンアルゴリズムなど）がグローバル最小値に収束することが保証されています。たとえば、

http://optimization-online.org/DB_FILE/2007/05/1662.pdf

ソフトマージンSVMと正則化項のあるSVMの場合、固有のグローバル最小値があり、通常の手法はグローバル最小値に収束すると思いますが、すべての可能性をカバーする証明はありません。