機械学習アルゴリズムの実践 - Platt SMO と遺伝的アルゴリズム最適化 SVM

[[206589]]

序文

以前、SVMの双対問題を最適化するために、単純なSMOアルゴリズムを実装しました。αを選択する際には、二重ループを使用して完全にランダムに選択しました。具体的な実装については、「機械学習アルゴリズムの実践 - SVMにおけるSMOアルゴリズム」を参照してください。

この論文では、以前の SMO アルゴリズムの簡略化されたバージョンに基づいて、α ペアを選択するヒューリスティックな方法を使用して SVM を最適化する Platt SMO アルゴリズムを実装します。また、最近遺伝的アルゴリズムフレームワーク GAFT を実装したので、遺伝的アルゴリズムを使用して SVM の元の形式を最適化することも試みました。

このアルゴリズムの対応する実装については、https://github.com/PytLab/MLBox/tree/master/svm を参照してください。
遺伝的アルゴリズムフレームワーク GAFT プロジェクトアドレス: https://github.com/PytLab/gaft

文章

SMOにおけるヒューリスティック変数選択

SMO アルゴリズムでは、最適化のために毎回 α のペアを選択する必要があります。ヒューリスティック選択により、目的関数が最も速く減少するように、最適化する変数をより効率的に選択できます。

最初の α1 Platt SMO と 2 番目の α2 Platt SMO には異なるヒューリスティックが使用されます。

最初の変数の選択

最初の変数選択は外側のループです。以前の便利な全体の αα リストとは異なり、ここでは全体のサンプルセットと非境界サンプルセットを交互に使用します。

まず、トレーニングセット全体を走査して、KKT 条件に違反していないかどうかを確認します。変更されたポイントの αiαi と xi、yixi、yi が KKT 条件に違反している場合は、変更されたポイントを最適化する必要があることを意味します。

Karush-Kuhn-Tucker (KKT) 条件は、正定値二次計画問題の最適点に対する必要十分条件です。 SVM デュアル問題の場合、KKT 条件は非常に単純です。

トレーニングセット全体を走査し、対応する α を最適化した後、反復の 2 回目のラウンドでは、非境界 α のみを走査する必要があります。いわゆる非境界 α とは、境界 0 または C と等しくない α 値を指します。同様に、これらのポイントについても、KKT 条件に違反していないかチェックし、最適化する必要があります。

その後、アルゴリズムは 2 つのデータセットを交互に実行し続け、最終的にすべての α が KKT 条件を満たすと、アルゴリズムは終了します。

最大のステップ長を持つ α を素早く選択するためには、すべてのデータに対応するエラーをキャッシュする必要があるため、SVM の重要な変数といくつかの補助メソッドを保存するための SVMUtil クラスを特別に作成しました。

以下は、最初の変数に対して交互走査を選択するための大まかなコードと、対応する完全な Python 実装です (完全な実装については、https://github.com/PytLab/MLBox/blob/master/svm/svm_platt_smo.py を参照してください)。

2番目の変数の選択

SMO における 2 番目の変数の選択プロセスは内部ループです。最初の α1 を選択した後、最適化後に選択した 2 番目の変数 α2 がより大きな変化を持つことを期待します。先ほど導いた式によれば

新しいα2の変化は|E1−E2|に依存することがわかります。E1が正の場合、最小のEiがE2として選択されます。通常、各サンプルのEiはリストにキャッシュされており、リスト内の|E1−E2|でα2を選択することでステップサイズがほぼ最大化されます。

上記のヒューリスティックでは関数値を十分に削減できない場合があるため、次の手順を使用して選択します。

非境界データセット上の関数値を十分に低減できるサンプルを第2変数として選択する

境界外データセットに変数がない場合、2 番目の変数選択はデータセット全体に対してのみ実行されます。

それでもない場合は、最初のα1を再選択してください

2 番目の変数選択の Python 実装:

KKT条件は一定の誤差を許容する

Platt の論文の KKT 条件の判定では、一定の誤差を許容する許容範囲があります。対応する Python 実装は次のとおりです。

Platt SMO の完全な実装については、https://github.com/PytLab/MLBox/blob/master/svm/svm_platt_smo.py を参照してください。

前のデータセットでは、Platt SMO を使用して最適化し、次の結果を得ました。

セグメンテーションラインとサポートベクトルを視覚化します。

Platt SMO によって最適化されたサポートベクターは、SMO アルゴリズムの簡略化されたバージョンとは若干異なることがわかります。

遺伝的アルゴリズムを使用した SVM の最適化

私は最近、遺伝的アルゴリズムのフレームワークを作成しました。遺伝的アルゴリズムは非常に使いやすいヒューリスティックな無誘導探索アルゴリズムなので、遺伝的アルゴリズムを使用して SVM を最適化しようとしました。

遺伝的アルゴリズムの最適化を使用すると、最も直感的な形式である SVM の初期形式を直接最適化できます。

ちなみに、私は独自の遺伝的アルゴリズムフレームワークを紹介したいと思います。このフレームワークを使用すると、SVM アルゴリズムを最適化するために数十行の Python コードを書くだけで済みます。最も重要なのは、適応度関数を記述することです。上記の式に従って、データセット内の各ポイントから分割線までの距離を計算し、最小距離を返してから、それを遺伝的アルゴリズムに入力して進化的反復を行う必要があります。

遺伝的アルゴリズムフレームワーク GAFT プロジェクトアドレス: https://github.com/PytLab/gaft 、詳細な使用方法については README を参照してください。

さて、進化の反復のための集団の構築を始めましょう。

個人と集団の創造

2次元データポイントの場合、[w1、w2]とbの3つのパラメータを最適化するだけで済みます。個体の定義は次のとおりです。

人口規模は600で、人口が作成されます。

遺伝的演算子とGAエンジンの作成

ここでは特別なことは何もありません。フレームワークに組み込まれている演算子を使用するだけです。

適応度関数

この部分では、上記の svm の初期形式を記述するだけで済みます。これには 3 行のコードのみが必要です。

反復を開始

ここでは人口の300世代を繰り返す

遺伝的アルゴリズムで最適化された分割線を描く