Discussion :

[arthy]

Bonjour
Je souhaite déterminer les coefficients A1,A2, ...,Ap qui prédisent le mieux la variable Y par la régression( Yi=A1X1,i+....+ApXp,n 1<=i<=n). Seulement il y a des contraintes sur ces paramètres
- la non négativité Ai>=0, i=1,..p
-A1+A2+...+Ap=1

Après avoir ecrit mon algorithme, j'obtiens des résultats erronnés (en désaccord avec la contrainte de la non négativité) pour ces paramètres.

Que puis-je faire?

Merci

P.S. J'utilise la seconde contrainte en substituant une des variables, ce qui fait qu'en réalitén je cherche à obtenir uniquement les paramètres A1,...,Ap-1

[souviron34]

un moindre carres generalise ??

[corentin59]

tu cherches à faire une minimisation sous contrainte du carré de l'erreur : tournes-toi vers les multiplicateurs de Lagrange, c'est fait pour ça !

[arthy]

Bonjour,

Juste pour préciser mon problème.

Je voudrai faire de la régression linéaire multiple.

Je souhaiterai déterminer avec la meilleure précision les coefficeients les valeurs de la variable Y à partir des variables explicatives X1, X2, ...,Xp.

Ceci revient à déterminer les paramètres A0,A1,...,Ap tels que
Yi=A0+A1X1+...+ApXp.

Dans ce contexte général, j'arrive à résoudre mon problème.

Les particularités à prendre en compte sont les suivantes:
A0=0
Ai>=0, i=1,...,p
A1+...+Ap=1

Je ne parviens pas à intégrere ces contraintes correctement dans mon algorithme.

C'est quoi les multiplicateurs de lagrange?

Merci

[ToTo13]

Bonjour,

en classification, il y a en général un très grand nombre de lignes à prendre en compte et on minimise la somme des erreurs.
Pour résoudre se problème, on se tourne alors vers une méthode du simplex.

[pseudocode]

C'est quoi les multiplicateurs de lagrange?

C'est une méthode pour maximiser une fonction f(x) soumise à des contrainte de la forme g(x)=constante. Ca ne me semble pas evident de modeliser la contrainte "Ai>=0" avec les multiplicateurs de Lagrange.

en classification, il y a en général un très grand nombre de lignes à prendre en compte et on minimise la somme des erreurs.
Pour résoudre se problème, on se tourne alors vers une méthode du simplex.

la fonction objectif ne sera pas linéaire si on veut une erreur chi-carré. Il faudra envisager un simplex "généralisé". Ca risque d'être long s'il y a beaucoup de points.

Comme Souviron, je pencherai plutot pour un moindre carrés NNLS (NNLS=Non-Negative Least-Squares).

[arthy]

Merci pour vos différents réponses.

Je vais de ce pas jeter un coup d'oeil sur l'algorithme NNLS

Je ne pense pas que ce ce problème puisse être résolu par la méthode du simplexe car je ne suis pas parvenu à formuler mon problème sous la forme d'une maximisation ou d'une minimisation d'une fonction coût.

En réalité, j'ai n obesevations ie Xi=(Xi,1,...Xi,n) i=1,..,p et Y=(Y1, ...,Yn)
Une erreur s'est glissé dans mon précédent message. Au lieu de

Code :

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

1
2
 
Yi=A0+A1X1+...+ApXp.

Il faudrait plutôt considérer

Code :

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

1
2
 
Yj=A0+A1X1,j+...+ApXp,j   j=1,..,n

[pseudocode]

Je ne pense pas que ce ce problème puisse être résolu par la méthode du simplexe car je ne suis pas parvenu à formuler mon problème sous la forme d'une maximisation ou d'une minimisation d'une fonction coût.

F(x) = Somme{ Error(i)² } pour i=1,..,n

avec

Error(i) = Yi - (A0+A1*X(1,i)+...+Ap*X(p,i))

[corentin59]

C'est une méthode pour maximiser une fonction f(x) soumise à des contrainte de la forme g(x)=constante. Ca ne me semble pas evident de modeliser la contrainte "Ai>=0" avec les multiplicateurs de Lagrange.

Si, avec les conditions de Karush-Kuhn-Tucker. Voir la théorie de base des SVM : le problème à résoudre ressemble beaucoup au problème d'optimisation posé par les SVM.

[pseudocode]

Si, avec les conditions de Karush-Kuhn-Tucker. Voir la théorie de base des SVM : le problème à résoudre ressemble beaucoup au problème d'optimisation posé par les SVM.

Effectivement, j'avais pas pensé aux SVM.

PS: J'ai toujours du mal avec les problemes duals .

[FR119492]

Salut !

Comme je ne suis pas sur d'avoir bien compris ton problème, je le reformule à ma manière:

Tu veux étudier une fonction de p variables indépendantes f(x_1, x_2, ... , x_p). Pour n jeux de ces p variables (évidemment n>p), tu connais la valeur de ta fonction. Tu cherches la fonction linéaire g(x_1, x_2, ... ,x_p) qui approxime "le moins mal possible" la fonction f(x_1, x_2, ... ,x_p). En d'autres termes, comme g(x_1, x_2, ... ,x_p) peut s'écrire
g = A_0 + A_1*x_1 + A_2*x_2 + ... + A_p*x_p
tu cherches les coefficients A_0, A_1, A_2, ... , A_p
Si c'est bien ça, fais-le moi savoir, car la méthode est élémentaire (1 ligne dans MatLab, un peu plus dans les autres langages!), mais peu de gens la connaissent.

Jean-Marc Blanc

[pseudocode]

En d'autres termes, comme g(x_1, x_2, ... ,x_p) peut s'écrire
g = A_0 + A_1*x_1 + A_2*x_2 + ... + A_p*x_p
tu cherches les coefficients A_0, A_1, A_2, ... , A_p

Avec en plus 2 contraintes:
- tous les Ai>=0
- somme{Ai}=1

[FR119492]

Salut à tous !

Les contraintes imposées me laissent perplexe:

• La contrainte somme{Ai}=1 implique que la fonction à approximer et toutes les variables xi sont des grandeurs "physiques" de dimension un. Est-ce bien le cas ? Si oui, cette contrainte n'implique pas des difficultés insurmontables.
• La contrainte tous les Ai>=0 est beaucoup plus ennuyeuse. Je ne comprend pas comment une contrainte peut s'imposer sur les coefficients et non sur les valeurs de la fonction d'approximation. Cette contrainte est-elle "naturelle" ou l'a-t-on introduite "par maladresse" ?

Jean-Marc Blanc

[Zavonen]

Dans un espace E à n dimensions ayant pour base X1, X2, ..Xn, les vecteurs Y vérifiant Y=A1X1+A2X2+ ...+AnXn avec les Ai >=0 et la somme des Ai égale à 1 , correspondent à la notion de cône de sommet O et ayant pour base les extrêmités des vecteurs X1, X2, ..,Xn (faire un dessin en dimension 2 ou 3).
Supposons maintenant la base Xi orthonormale.
Si Y est un vecteur quelconque de l'espace (pas forcément dans le cône) avec les coordonnées B1,B2, ...,Bn le vecteur du cône 'le plus proche' est celui obtenu en projetant orthogonalement Y sur la face du cône la plus proche.
On se place maintenant dans un espace F de dimension m avec m >=n contenant donc E. M étant un point quelconque de F on cherche le point du cône C le plus proche de M.
Commençons par projeter M sur E, et soit H1, le point obtenu.
Les coordonnées de H1 sont donc les produits scalaires de OM avec les Xi.
Soit H2 le point du cône le plus proche de H1.
Peut-il exister un point H3 dans le cône plus proche de M que H2 ?
A mon sens, non.
Encore une fois il faut faire un dessin:
MH est orthogonal à E.
H1H2, H1H3, et H2H3 sont tous orthogonaux à MH1. De plus MH1 réalise le minimum absolu de la distance d'un point de E à M.
Il suffit donc d'appliquer à répétition Pythagore dans les 2 triangles rectangles
MH1H2 MH1H3 et d'utiliser que H1H2 <= H1H3 pour voir que ce n'est pas possible.
Donc, ma solution :
Projeter M sur E. Soit H1 le résultat
Projeter H1 sur la face la plus proche du cône.(au cas où H1 ne soit pas dans le cône bien sûr)
NB: Les équations des faces sont hypersimples, elles s'obtiennent soit en annulant une coordonnée, soit en faisant X1+X2+..Xn=1 pour la base.
Par ailleurs la formule qui donne la distance d'un point à un hyperplan est un classique.

[souviron34]

Les contraintes imposées me laissent perplexe:

• La contrainte somme{Ai}=1 implique que la fonction à approximer et toutes les variables xi sont des grandeurs "physiques" de dimension un. Est-ce bien le cas ? Si oui, cette contrainte n'implique pas des difficultés insurmontables.
• La contrainte tous les Ai>=0 est beaucoup plus ennuyeuse. Je ne comprend pas comment une contrainte peut s'imposer sur les coefficients et non sur les valeurs de la fonction d'approximation. Cette contrainte est-elle "naturelle" ou l'a-t-on introduite "par maladresse" ?

Ben ya rien de compliqué, ce me semble.. Ce sont des poids....

Vraisemblablment dans le problème du PO il a à priori l'idée que sa mesure est la combinaison d'un certain nombre d'autres. D'où la somme égale à 1 et le fait que ce soit positif...

En fait c'est pour ça que je pensais aux moindres carrés. Ou le Simplex.

[arthy]

Salut à tous,

Je commencerai par vous remercier pour vos différentes réponses sans toutefois oublier de m'excuser pour ce long silence. J'ai effectué un voyage imprévu. Ce qui ne m'a pas permis de de voir si j'obtenais de bons résultats avec la méthode NNLS comme je l'avais affirmé dans mon précédent message

Je retiens que 2 propositions m'ont été faites:

NNLS
multiplicateurs de lagrange.

et je constate également que mon problème a été très bien compris par la majorité des intervenants à l'instar de Souviron34.

En effet, les coefficients A1, ..., Ap à déterminer constituent le poids des variables X1, ..., Xp (Y étant ici une agrégation de celles-ci). D'où la condition de la non négativité et celle selon laquelle leur somme est égale à 1. Ce qui donne p+1 contraintes pour p coefficients à déterminer.

Peut-on encore dans ce cas utiliser la méthode des multiplicateurs de Lagrange?

Je n'ai pas compris le sigle PO utilisé par Souviron34. Zavonen, je n'ai pas du tout saisi tes propos. Peut être cela est du au fait que je n'ai plus de notion de géométrie descriptive. Dès le début, je me suis "planté". Tu parles de vecteur dans le cône, de la représentation d'un vecteur dans le cône ou tout simplement de point dans le cône?

Merci

Arthy

[souviron34]

Je n'ai pas compris le sigle PO utilisé par Souviron34.

Posteur (ou Post) Original (ou Originel)

[Zavonen]

Tu parles de vecteur dans le cône, de la représentation d'un vecteur dans le cône ou tout simplement de point dans le cône?

J'identifie les points et les vecteurs Point M = vecteur OM
Ton premier post est bizarre:

( Yi=A1X1,i+....+ApXp,n 1<=i<=n).

A mon avis il a du sens si on remplace par:

( Yi=A1X1,i+....+ApXp,i 1<=i<=n).

Auquel cas
Les Yi représentent UN vecteur de R^n
les X1, .. Xp représentent p vecteurs de R^n engendrant un sous espace de dimension au plus égale à p et ma réponse prend tout son sens.
Ta relation s'écrit simplement Y=A1X1+A2X2 +...+ApXp quand on l'écrit globalement (vectoriellement) au lieu de l'écrire coordonnée par coordonnée
Identifie les points et les vecteurs.
Dans le cas p=2 tu trouves un segment
Dans le cas p=3 un triangle
Dans le cas p=4 un tétraèdre
Dans le cas général l'enveloppe convexe de p points.
J'utilise maintenant deux fois le théorème de la projection orthogonale sur un fermé convexe (en dimension finie).
Dans un premier temps tu projettes le point Y (ou le vecteur OY comme tu préfères) sur le sous espace engendré par OX1, OX2, .. OXp
Dans un second temps tu projettes cette même projection sur une enveloppe convexe.

[abdali]

j'ai le même problème ou les contraintes sont dues au modèle probabiliste c'est à dire que le résultat de Yi est une probabilité ce qui veut dire que le résultat doit être positif et la somme des probabilites égale à 1.

[Zang76]

Salut !

Comme je ne suis pas sur d'avoir bien compris ton problème, je le reformule à ma manière:

Tu veux étudier une fonction de p variables indépendantes f(x_1, x_2, ... , x_p). Pour n jeux de ces p variables (évidemment n>p), tu connais la valeur de ta fonction. Tu cherches la fonction linéaire g(x_1, x_2, ... ,x_p) qui approxime "le moins mal possible" la fonction f(x_1, x_2, ... ,x_p). En d'autres termes, comme g(x_1, x_2, ... ,x_p) peut s'écrire
g = A_0 + A_1*x_1 + A_2*x_2 + ... + A_p*x_p
tu cherches les coefficients A_0, A_1, A_2, ... , A_p
Si c'est bien ça, fais-le moi savoir, car la méthode est élémentaire (1 ligne dans MatLab, un peu plus dans les autres langages!), mais peu de gens la connaissent.

Jean-Marc Blanc

Est-ce possible de connaitre la méthode dont tu parle, ça m'interesse ! Merci.