Discussion :

[Alexis.M]

Bonjour,

J'ai un problème d'optimisation en grande dimension dans lequel je sais que je vais me retrouver au voisinage d'un point selle. Pour s'en échapper, il est possible de prendre la direction donnée par le vecteur propre associé à la plus petite valeur propre négative de la matrice Hessienne du problème.

Mon problème vient du fait qu'en pratique le calcul de cette valeur propre est bien trop coûteux. Pour trouver une direction acceptable mon idée est de tirer des vecteurs aléatoires xi est de regarder la valeur de xi'Hxi. Si la valeur est négative je suis sûr que la direction xi (ou -xi) est une direction de descente sinon je prends le vecteur qui a donné la plus petite valeur et je regarde si j'arrive à minimiser ma fonction.

Pour justifier cela je me base sur la décomposition en valeurs propres de la matrice Hessienne H:

H = UDU'

et donc

x'Hx = \sum_k d_k (u_k'x)^2

Si la direction de x est principalement colinéaire à un des vecteurs propres, la contribution de la valeur propre associée sera prépondérante. D'autant qu'a priori (vu mon problème) ma matrice H sera de rang faible.

J'aurais voulu savoir si quelqu'un avait un avis sur cette approche ou mieux encore, s'il existait de la littérature sur cette façon de faire.

[Aleph69]

Bonjour,

J'ai un problème d'optimisation en grande dimension

Quelle est la dimension?

Mon problème vient du fait qu'en pratique le calcul de cette valeur propre est bien trop coûteux.

Avec quelle méthode? Quel est le coût?

Pour trouver une direction acceptable mon idée est de tirer des vecteurs aléatoires xi est de regarder la valeur de xi'Hxi. Si la valeur est négative je suis sûr que la direction xi (ou -xi) est une direction de descente sinon je prends le vecteur qui a donné la plus petite valeur et je regarde si j'arrive à minimiser ma fonction.

Qu'est-ce qui assure la convergence de ta méthode? En quoi une approche stochastique serait-elle moins coûteuse qu'un algorithme déterministe?

Si la direction de x est principalement colinéaire à un des vecteurs propres, la contribution de la valeur propre associée sera prépondérante.

Et alors?

D'autant qu'a priori (vu mon problème) ma matrice H sera de rang faible.

Quel est son rang? Pourquoi ne pas tirer profit de cette information? As-tu entendu parler du théorème d'entrelacement de Cauchy?

J'aurais voulu savoir si quelqu'un avait un avis sur cette approche ou mieux encore, s'il existait de la littérature sur cette façon de faire.

Sans information supplémentaire, je dirais que ta méthode ne converge pas nécessairement (a priori tu peux construire une suite alternée sans le vouloir). Tu n'es pas non plus certain de tirer aléatoirement un vecteur x tel que x'Hx soit négatif (il peuvent être situés dans un région tellement petite que tu ne vas pas tomber dedans souvent). Corollairement, lorsqu'il converge, ton algorithme est (en moyenne) moins efficace qu'un algorithme déterministe de recherche de valeur propre.

[Alexis.M]

Bonjour,
Quelle est la dimension?

De l'ordre de 10000x10000 pour la matrice Hessienne, qui est dense a priori.

Avec quelle méthode? Quel est le coût?

Y a-t-il des méthodes qui pourront me calculer cette valeur propre en moins que O(N^3) ? Avec la méthode à laquelle je pense on est de l'ordre de (kN^2) si k est le nombre d'essais.

Qu'est-ce qui assure la convergence de ta méthode? En quoi une approche stochastique serait-elle moins coûteuse qu'un algorithme déterministe?

C'est bien ma question: existe-t-il de la littérature sur la question. Mon problème n'est pas convexe mais ses minima locaux sont aussi des minima globaux.

Quel est son rang? Pourquoi ne pas tirer profit de cette information? As-tu entendu parler du théorème d'entrelacement de Cauchy?

Empiriquement dans mes problèmes le rang est typiquement de l'ordre de 100. C'est parce qu'elle est de rang faible que je pense que cette méthode peut fonctionner. J'espère qu'un nombre restreint de tirages me permettra de trouver une direction exploitable.

S'il existe des algos qui permettent de n'extraire (efficacement) que les vecteurs propres en dehors du "null space", cela peut en effet être ma solution.

Pour le théorème d'entrelacement, je vais y jeter un oeil

Sans information supplémentaire, je dirais que ta méthode ne converge pas nécessairement (a priori tu peux construire une suite alternée sans le vouloir).

Si j'arrive à m'échapper du point celle, une descente de gradient (ou un dérivé) va continuer dans la bonne direction en suite. Je ne pense donc pas pouvoir rentré dans une suite alternée.

Tu n'es pas non plus certain de tirer aléatoirement un vecteur x tel que x'Hx soit négatif (il peuvent être situés dans un région tellement petite que tu ne vas pas tomber dedans souvent).

C'est en effet un problème mon idée était alors de prendre simplement le vecteur correspondant à la plus petite valeur, le tester et m'arrêter si je n'arrive pas à minimiser plus.

Corollairement, lorsqu'il converge, ton algorithme est (en moyenne) moins efficace qu'un algorithme déterministe de recherche de valeur propre.

En fait je ne suis pas forcement intéressé par une évaluation précise de l'optimum, car mon problème s'inscrit dans le cadre d'un algo d'apprentissage supervisé et il est probable qu'une solution approchée donne au final de meilleurs résultats (early stopping).

Merci beaucoup en tout cas pour tes commentaires, je vais réfléchir plus en avant...

[FR119492]

Salut!

point celle

C'est quoi? Je ne trouve nulle part une définition.
Jean-Marc Blanc

[Aleph69]

Y a-t-il des méthodes qui pourront me calculer cette valeur propre en moins que O(N^3) ? Avec la méthode à laquelle je pense on est de l'ordre de (kN^2) si k est le nombre d'essais.

Ton k peut approcher N si la probabilité de trouver un x tel que x'Hx<0 est petite car contrairement à ce que tu sembles dire, je ne pense pas que tu puisses t'affranchir de trouver un tel x à chaque itération. En supposant qu'il fonctionne, ton algorithme est donc en O(mkN^2) où m désigne le nombre d'itérations avant convergence : ceci est en moyenne plus élevé que O(N^3).

Si tu veux récupérer un algorithme en O(mN^2), regarde les méthodes basées sur des sous-espaces de Krylov dans ces livres :
http://www-users.cs.umn.edu/~saad/eig_book_2ndEd.pdf
http://web.eecs.utk.edu/~dongarra/etemplates/index.html

Si j'arrive à m'échapper du point celle, une descente de gradient (ou un dérivé) va continuer dans la bonne direction en suite. Je ne pense donc pas pouvoir rentré dans une suite alternée.

Un exemple de suite alternée : soient deux vecteurs propres e1 et e2 de ta matrice hessienne, chacun associé à une valeur propre négative. On pose uk=e1 si k est pair et uk=e2 si k est impair. Tu construiras une telle suite en tirant aléatoirement e1 puis e2 puis e1 puis e2 et ainsi de suite. En généralisant à plusieurs vecteurs propres à valeurs propres négatives et en admettant une certaine déviation de x par rapport à ces vecteurs propres, tu vas comprendre que la probabilité pour que tu obtiennes un algorithme ne s'arrêtant jamais (suite alternée) ou convergeant très lentement (suite alternée pendant les premières itérations puis convergence) n'est pas nulle.

En fait je ne suis pas forcement intéressé par une évaluation précise de l'optimum, car mon problème s'inscrit dans le cadre d'un algo d'apprentissage supervisé et il est probable qu'une solution approchée donne au final de meilleurs résultats (early stopping).

Euh oui... jusqu'à un certain point quand même! Le "early stopping" part du principe que l'algorithme converge mais que l'on s'arrête avant. Prendre un algorithme qui ne converge pas ce n'est pas faire du early stopping. Par ailleurs, le compromis biais-variance fait intervenir le biais ET la variance : il faut tout de même approcher un minimum ta solution pour obtenir un modèle aléatoire conduisant à une bonne généralisation.

A Jean-Marc : il s'agit bien d'un point-selle comme tu t'en doutes!

[Alexis.M]

Merci pour les suggestions. ils semble que le package Arpack utilisent les méthodes évoquées par Aleph69. Des tests avec le binding python présent dans scipy.sparse.linalg montrent de bien meilleurs performances même sur des données non creuses, que la méthode générique codée dans scipy.linalg.

[Aleph69]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

il semble que le package Arpack utilisent les méthodes évoquées par Aleph69

La bibliothèque Arpack permet de calculer les paires propres des matrices à l'aide de la méthode d'Arnoldi (ArPack=Arnoldi Package), qui est bien une méthode de Krylov.