18

高次元のバイナリデータ（テキスト）の場合は、単純な線形SVMが最適だと思う単純なSVM分類器を実装したいと思います。自分で実装する理由は、基本的にはどのように機能するのかを知りたいので、ライブラリを使うのは私が望んでいることではありません。

問題は、ほとんどのチュートリアルが「二次問題」として解くことができる方程式に到達することですが、実際のアルゴリズムを示すことはありません。それで、私が研究できる非常に単純な実装、または（より良い）実装の詳細に至るまでのチュートリアルを教えていただけますか？

どうもありがとう！

4

5 に答える 5

12

逐次最小最適化（SMO）法のいくつかの擬似コードは、ジョンC.プラットによるこの論文で見つけることができます：逐次最小最適化を使用したサポートベクターマシンの高速トレーニング。研究および教育目的で開発されたSMOアルゴリズムのJava実装もあります（SVM-JAVA）。

QP最適化問題を解くために一般的に使用される他の方法は次のとおりです。

  • 制約付き共役勾配
  • 内点法
  • 有効制約法

ただし、このことを理解するには、数学の知識が必要であることに注意してください（ラグランジュ乗数、カルーシュ・クーン・タッカー条件など）。

于 2009-11-18T21:14:22.100 に答える
9

カーネルの使用に興味がありますか？カーネルがない場合、これらの種類の最適化問題を解決する最良の方法は、さまざまな形式の確率的勾配降下法を使用することです。良いバージョンはhttp://ttic.uchicago.edu/~shai/papers/ShalevSiSr07.pdfで説明されており、明示的なアルゴリズムがあります。

明示的なアルゴリズムはカーネルでは機能しませんが、変更できます。ただし、コードと実行時の複雑さの両方の点で、より複雑になります。

于 2009-11-24T05:27:34.567 に答える
1

liblinearおよびlibsvmの非線形SVMをご覧ください

于 2010-04-20T07:32:10.303 に答える
0

次の論文「Pegasos：SVMのPrimal Estimated sub-GrAdient SOlver」では、カーネルのPegasosアルゴリズムについても説明しています。http：//ttic.uchicago.edu/~nati/Publications/PegasosMPB.pdfからダウンロードできます。

座標降下法と劣勾配法のハイブリッドのようです。また、アルゴリズムの6行目が間違っています。述語では、y_i_tの2番目の外観を代わりにy_jに置き換える必要があります。

于 2016-06-12T11:07:03.963 に答える
0

プラットのオリジナル作品についての回答に少し補足を加えたいと思います。Stanford Lecture Notesには少し簡略化されたバージョンがありますが、すべての数式の導出は別の場所で見つける必要があります（たとえば、インターネットで見つけたこのランダムなメモ）。

元の実装から逸脱しても問題がない場合は、次のSMOアルゴリズムの独自のバリエーションを提案できます。

class SVM:
  def __init__(self, kernel='linear', C=10000.0, max_iter=100000, degree=3, gamma=1):
    self.kernel = {'poly':lambda x,y: np.dot(x, y.T)**degree,
                   'rbf':lambda x,y:np.exp(-gamma*np.sum((y-x[:,np.newaxis])**2,axis=-1)),
                   'linear':lambda x,y: np.dot(x, y.T)}[kernel]
    self.C = C
    self.max_iter = max_iter

  def restrict_to_square(self, t, v0, u):
    t = (np.clip(v0 + t*u, 0, self.C) - v0)[1]/u[1]
    return (np.clip(v0 + t*u, 0, self.C) - v0)[0]/u[0]

  def fit(self, X, y):
    self.X = X.copy()
    self.y = y * 2 - 1
    self.lambdas = np.zeros_like(self.y, dtype=float)
    self.K = self.kernel(self.X, self.X) * self.y[:,np.newaxis] * self.y
    
    for _ in range(self.max_iter):
      for idxM in range(len(self.lambdas)):
        idxL = np.random.randint(0, len(self.lambdas))
        Q = self.K[[[idxM, idxM], [idxL, idxL]], [[idxM, idxL], [idxM, idxL]]]
        v0 = self.lambdas[[idxM, idxL]]
        k0 = 1 - np.sum(self.lambdas * self.K[[idxM, idxL]], axis=1)
        u = np.array([-self.y[idxL], self.y[idxM]])
        t_max = np.dot(k0, u) / (np.dot(np.dot(Q, u), u) + 1E-15)
        self.lambdas[[idxM, idxL]] = v0 + u * self.restrict_to_square(t_max, v0, u)
    
    idx, = np.nonzero(self.lambdas > 1E-15)
    self.b = np.sum((1.0-np.sum(self.K[idx]*self.lambdas, axis=1))*self.y[idx])/len(idx)
  
  def decision_function(self, X):
    return np.sum(self.kernel(X, self.X) * self.y * self.lambdas, axis=1) + self.b

単純なケースでは、sklearn.svm.SVCよりもあまり価値がありません。以下に比較を示します（これらの画像を生成するコードをGitHubに投稿しました） ここに画像の説明を入力してください

数式を導出するためにまったく異なるアプローチを使用しました。詳細については、ResearchGateのプレプリントを確認してください。

于 2020-10-25T10:41:09.137 に答える