Discussion :

[abidineb]

Bonsoir

J'essaye d’étudier la complexite de quelques algorithmes, mais je ne trouve pas leurs complexité de calcul théorique, l'algorithme recherché est Machine a vecteurs de support (SVM) un-contre-un.

Si qql a la réponse ou lien qui fournit la complexite de l'algorithme cité en haut, ça me sera d'une grande utilité.
Merci d'avance
Cordialement

[abidineb]

Salut a tous
Peut être c'est deja mentionné la complexite temporelle de k-plus SVM(machine a vecteur de support) quelque part dans ce forum, s’il vous plait montrez moi le chemin???
Cordialement

[abidineb]

Salut a tous
Je vais être plus precis, je cherche la complexite du classificateur machine a vecteur de support mais juste pour la phase de test, si qql peut m'aider s'il vous plait, je cherche sur le net mais je n'ai rien trouve pour le moment.
Merci
Cordialement

[Alexis.M]

La complexité du test dans SVM dépend de la méthode utilisée linéaire ou "kernelisée".

Dans la version linéaire il suffit de projeter le point de donnée sur la normale à l'hyperplan séparateur. Donc la complexité sera O(d) si d est le nombre de dimensions dans ton vecteur.

Avec les algorithmes à Noyaux il faut au moins calculer le noyau du point de donnée à tester avec les vecteurs support donc une complexité O(N*k) avec N le nombre de vecteurs supports et k la complexité pour calculer le noyau.

[abidineb]

Bonjour
Votre réponse m’éclaire un petit peu la route. Merci
Donc la complexité de test dépendra se la version utilisée (Linéaire-kernelisee). Je pense que c'est pareil pour la phase d'apprentissage.
Ma question est la suivante
Version linéaire:
Vous dites O(d), est ce que le nombre de classes N ne doit pas apparaitre qql part????????????.

Version kernelisee:
Ma question est similaire (version linéaire)??

Cordialement

[math_lab]

Vous dites O(d), est ce que le nombre de classes N ne doit pas apparaitre qql part????????????.

Les SVM, a l'origine, c'est fait que pour 2 classes. Il y a des bidouillages possibles pour en gérer plus, mais la, la complexité dépend des choix qui ont été faits.

[abidineb]

Bonjour

Merci. Donc ça dépendra de la méthode choisie pour le Multi-classes.
Dernière question puisque la complexité dépendra de la sélection des paramètres SVM. Si on utilise la methode un-contre-un, On doit chercher les paramètres SVM pour chaque pair de classifieur???????????, ou il y a une autre méthode plus générale??
Merci.

Cordialement