algorithm - 最尤とサポート ベクターの複雑さ

Question

最尤法を決定し、ベクター マシン分類器の計算の複雑さをサポートする方法を示す参考文献を誰か教えてもらえますか? 私はウェブを検索してきましたが、これらの分類器アルゴリズムの計算の複雑さをモデル化する方程式を見つける方法を詳しく説明している適切なドキュメントが見つからないようです。ありがとう

Answer 1

サポート ベクター マシン、および多数の最尤近似は、凸最小化問題です。したがって、理論的にはhttp://en.wikipedia.org/wiki/Ellipsoid_methodを使用して多項式時間で解決できます。

方法を検討すれば、より良い見積もりを得ることができると思います。http://www.cse.ust.hk/~jamesk/papers/jmlr05.pdfによると、m インスタンスへの標準 SVM フィッティングには O(m^3) 時間と O(m^2) スペースが必要です。http://research.microsoft.com/en-us/um/people/minka/papers/logreg/minka-logreg.pdfは、ロジスティック回帰の反復あたりのコストを示していますが、反復回数を推定するための理論的根拠は示していません。実際には、これがほとんどの場合二次収束に行き、それほど悪くないことを願っています。