Complessità di formazione di SVM lineare

Question

Qual è l'effettiva complessità computazionale della fase di apprendimento di SVM (diciamo, quella implementata in LibSVM)?

Grazie

Answer 1

questo sta per essere fortemente dipendente dal tipo SVM e kernel. C'è una discussione piuttosto tecnica http://www.csie.ntu.edu.tw/~cjlin/papers/libsvm.pdf. Per una risposta rapida, http://www.csie.ntu.edu.tw/~cjlin/papers/libsvm.pdf, si aspetta che sia n^2.

Answer 2

Complessità di formazione di non lineare SVM è generalmente compreso tra O (n^2) e O (n^3) con n la quantità di istanze di addestramento. I seguenti documenti sono buone referenze:

• Support Vector Machine Solvers by Bottou and Lin
• SVM-optimization and steepest-descent line search by List and Simon

PS: Se si desidera utilizzare il kernel lineare, non utilizzare LIBSVM. LIBSVM è un risolutore SVM generico (non lineare). Non è un'implementazione ideale per SVM lineare. Invece, dovresti considerare cose come LIBLINEAR (dagli stessi autori di LIBSVM), Pegasos o SVM^perf. Questi hanno molto complessità di addestramento migliore per SVM lineare. La velocità di allenamento può essere di ordini di grandezza migliore rispetto all'utilizzo di LIBSVM.