La formation de la complexité de SVM Linéaire

Qui est la réelle complexité de calcul de la phase d'apprentissage de SVM (disons, que mis en œuvre dans LibSVM)?

Merci

OriginalL'auteur user1923631 | 2013-05-16

  1. 9

    De formation de la complexité de non linéaire SVM est généralement comprise entre O(n^2) et O(n^3) avec n le montant de la formation des instances. Les documents suivants sont de bonnes références:

    PS: Si vous souhaitez utiliser linéaire du noyau, ne pas utiliser de LIBSVM. LIBSVM est d'un usage général (non-linéaire) SVM solveur. Il n'est pas un idéal de mise en œuvre pour les SVM linéaire. Au lieu de cela, vous devriez considérer les choses comme LIBLINEAR (par les mêmes auteurs que LIBSVM), Pegasos ou SVM^perf. Ceux-ci ont beaucoup une meilleure formation de la complexité pour les SVM linéaire. La vitesse de formation peuvent être des ordres de grandeur supérieurs à l'aide de LIBSVM.

    Lien 2 est mort, et pour le lien 1 le document semble avoir été retiré

    OriginalL'auteur Marc Claesen

  2. 1

    Cela va être fortement dépendante des svm type et le noyau. Il y a une discussion technique http://www.csie.ntu.edu.tw/~cjlin/documents/libsvm.pdf.
    Pour une réponse rapide, http://www.csie.ntu.edu.tw/~cjlin/documents/libsvm.pdf, dit s'attendre à n^2.

    OriginalL'auteur Bull