machine-learning - SVM の逐次最小最適化の収束の問題

Question

Support Vector Machine に取り組んでから約 2 か月が経ちました。私は自分で SVM をコーディングしました。SVM の最適化問題には、John Platt 博士による逐次最小最適化 (SMO) を使用しました。

現在、自分のデータセットに最適な C 値を見つけるためにグリッド検索を行うフェーズにいます。(私のプロジェクト アプリケーションの詳細とデータセットの詳細については、こちらを参照してくださいSVM 分類 - 各クラスの入力セットの最小数)

2^0 から 2^6 の範囲の C 値について、カスタム実装された SVM の精度を正常にチェックできました。しかし、現在、C> 128 の SMO の収束に関していくつかの問題があります。C=128 のアルファ値を見つけようとしたのと同様に、実際に収束してアルファ値を正常に与えるまでに長い時間がかかります。

SMO が収束するのにかかる時間は、C=100 で約 5 時間です。これは大きいと思います (SMO は高速であるはずなので)。精度は高いのですが? Cのより高い値の精度をテストできないからではなく、私は正しくねじ込まれています.

私は実際に SMO のすべてのパスで変更されたアルファの数を表示しており、10、13、8... アルファが連続的に変化しています。KKT 条件は収束を保証しますが、ここで何が起こっているのでしょうか?

実行時間は長くなりますが、私の実装は C<=100 に対して良好な精度で正常に動作することに注意してください。

この問題に関する情報を教えてください。

ありがとうと乾杯。

Answer 1

ほとんどの SVM 実装では、C の値が大きくなると、トレーニング時間が劇的に増加する可能性があります。SMO の適度に優れた実装でのトレーニング時間が C でどのようにスケーリングされるかを理解するには、下のグラフで libSVM の対数スケールの線を見てください。 .

SVM トレーニング時間 vs. C - Sentelle らのA Fast Revised Simplex Method for SVM Training より。

代替テキスト http://dmcer.net/StackOverflowImages/svm_scaling.png

おそらく、物事を高速化するための 2 つの簡単な方法と、そう簡単ではない方法が 1 つあります。

簡単なことから始めましょう。まず、収束基準を緩めてみてください。epsilon = 0.001 のような厳密な基準はトレーニングに時間がかかりますが、通常、epsilon = 0.01 のような緩い基準よりも優れたモデルは得られません。次に、コードのプロファイリングを試みて、明らかなボトルネックがあるかどうかを確認する必要があります。

それほど簡単ではない解決策は、別の最適化アルゴリズム (たとえば、上記の Sentelle らの論文の SVM-RSQP) に切り替えることです。ただし、SMO の実装が機能している場合は、おそらく最後の手段としてのみ実行する必要があります。