Qual è l'effettiva complessità computazionale della fase di apprendimento di SVM (diciamo, quella implementata in LibSVM)?Complessità di formazione di SVM lineare
Grazie
Qual è l'effettiva complessità computazionale della fase di apprendimento di SVM (diciamo, quella implementata in LibSVM)?Complessità di formazione di SVM lineare
Grazie
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.
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:
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.