Discussion :

[steph42]

Bonjour à tous,

je cherche à résoudre un système linéaire Ax=y dont le y cherché est sous forme binaire: par exemple, y=[0 1 0 1 1 ...]

A est une matrice avec des valeurs quelconques (que jai toutefois normalisées entre 0 et 100). D'après ce que j'ai lu, ce que l'on va obtenir (le ypredit) va être une probabilité d'avoir 1. On n'aura donc pas "0" ou "1". Il faut faire intervenir la fonction de lien (en général logit). Mais...

Au moment de mettre ça en application, je ne vois pas comment procéder...

la fonction logit est de la forme p=1/(1-exp(-a)) avec a=Xb+err (err étant un terme d'erreur). a est donc l'estimateur linéaire. A partir de là, tout est confus: si je cherche à résoudre mon glm directement (par moindres carrés directement) Ax=y puis que je remplace mon "a" de l'expression précédente par le ypredit trouvé, ça donne n'importe quoi.

Dois-je changer le y de mon système par la probabilité d'avoir "1"? ex: si j'ai 100 éléments dans mon y, dont 15 "1", la probabilité d'avoir des "1" est de 0.15. Ainsi, je mets 0.15 partout dans le y, puis je cherche "a" tel que a=ln(p/1-p) mais là encore le résultat ne correspond à rien.

Merci de m'éclairer...

[ToTo13]

Bonjour,

ne souhaiterais tu pas résoudre un problème de régression logistique?

Si c'est bien ce que je pense, ton problème est différent de la façon dont tu le pose et ne se résume absolument pas à la résolution d'un système.

[steph42]

Bonjour,

peut être bien, je ne sais pas! Je n'ai fait que reformuler ce que j'ai lu dans un article, où il était bien fait mention de "modèle linéaire généralisé".

J'ai plusieurs variables, qui prennent n'importe quelles valeurs (de 0 à 1000) et on désire trouver des coefficients à appliquer à ses variables qui donnent la meilleur approximation d'un vecteur y qui lui est en binaire.

On résoud Ax=y avec A=[A1 A2 A3 A4] où chaque colonne Ai prend des valeurs réelles entre 0 et 1000. x est le vecteur coefficient que l'on cherche, et y est un vecteur sous forme binaire (0 ou 1).

Comment procéder?
Merci

[ToTo13]

Bonjour,

dans ce genre de cas, tu as un système vraiment SURdéterminé qui n'admet pas de solution => Il faut donc minimiser l'erreur.
Pour tout individu "i", tu as une fonction F qui te donne une probabilité d'appartenance à une classe. Dans ton cas ces classes sont 0/1 et tu les connais grâce à ton vecteur Y.
Tu veux donc minimer : Somme(i=1..N) |F(i)-Yi|, avec N le nombre d'individus.
Dans le cas d'une régression logistique tu as
- F(x) = exp(f(x)) / (1+exp(f(x))).
- f(x) = Somme(i=1..M) Ai.Xi, avec A le vecteur contenant les M caractéristiques de ton individu et X les M coefficients que tu cherches.

Pour converger vers une solution, le mieux dans ce cas est d'utiliser une méthode du simplex.

[steph42]

Bonjour et merci,

cela répond exactement à mon problème. C'est bien de la régression logistique, mais cela peut aussi s'appeler modèle linéaire généralisé.

Par contre, pour la résolution, j'ai quelques soucis... J'ai lu qu'il fallait procéder par maximisation de la vraisemblance, mais comment exprimer cette fonction de vraisemblance? Que vaut elle ici?

D'autre part, j'avais déjà posé une question sur ce forum, concernant l'algo du simplex. J'avais compris qu'en fait, on cherchait tous les n-uplets de coefficients possible qui fonctionnent, et on retient celui qui minimise l'erreur des moindres carrés.
Ex: dans mon cas, j'ai 1 0578 000 équations pour 4 inconnues. Je résouds tous les sytèmes de 4 équations à 4 inconnues, et je retiens le 4-uplet qui minimise mon erreur au sens des moindres carrés.
Est-ce bien cela?

[ToTo13]

Bonjour,

cela répond exactement à mon problème. C'est bien de la régression logistique, mais cela peut aussi s'appeler modèle linéaire généralisé.

Ok, bon à savoir

Par contre, pour la résolution, j'ai quelques soucis... J'ai lu qu'il fallait procéder par maximisation de la vraisemblance, mais comment exprimer cette fonction de vraisemblance? Que vaut elle ici?

C'est un point qui reste un peu obscur pour moi mais d'après ce que j'ai lu, ce serait la fonction que j'explique dans mon précédent message.

D'autre part, j'avais déjà posé une question sur ce forum, concernant l'algo du simplex. J'avais compris qu'en fait, on cherchait tous les n-uplets de coefficients possible qui fonctionnent, et on retient celui qui minimise l'erreur des moindres carrés.
Ex: dans mon cas, j'ai 1 0578 000 équations pour 4 inconnues. Je résouds tous les sytèmes de 4 équations à 4 inconnues, et je retiens le 4-uplet qui minimise mon erreur au sens des moindres carrés.
Est-ce bien cela?

Il me semble que simplex va te donner qu'une seule solution de N coefficients. Tu n'as qu'à lui donner ton système à 10 578 000 équations de quatre inconnues.

[steph42]

Salut,

non la fonction que tu m'as donné est juste celle qui permet "d'expliquer" Y de manière exponentielle. Il faut exprimer la vraisemblance de ce truc là (c'est le produit des fonctions de densité de probabilité je crois), et après on prend le log, qu'on appelle le log-vraisemblance (d'où le nom de régression logistique). Puis on annule ce log et ses dérivées de manière à avoir assez d'équations pour trouver les coefficients. Mais comment exprimer cette vraisemblance?

Pour ce qui est du simplex, ce truc ne peut pas tourner... Le nombre de possibilités de 4 équations parmi 1 0578 000 est beaucoup trop grand. Un calcul simple m'a permis d'estimer à plusieurs années le temps nécessaire à la résolution sous Matlab...

[ToTo13]

Bonjour,

non la fonction que tu m'as donné est juste celle qui permet "d'expliquer" Y de manière exponentielle. Il faut exprimer la vraisemblance de ce truc là (c'est le produit des fonctions de densité de probabilité je crois), et après on prend le log, qu'on appelle le log-vraisemblance (d'où le nom de régression logistique). Puis on annule ce log et ses dérivées de manière à avoir assez d'équations pour trouver les coefficients. Mais comment exprimer cette vraisemblance?

Désolé, je ne l'ai jamais programmé, donc je ne peux t'aider plus.

Pour ce qui est du simplex, ce truc ne peut pas tourner... Le nombre de possibilités de 4 équations parmi 1 0578 000 est beaucoup trop grand. Un calcul simple m'a permis d'estimer à plusieurs années le temps nécessaire à la résolution sous Matlab...

Alors là, pas d'accord...
Je sais de source sûre que c'est un simplex qui est utilisé pour résoudre ce système. Le simplex converge très rapidement en minimisant la fonction de coût, c'est pour cela qu'il est bien adapté à ce problème.

[steph42]

Salut,

très bien, tu dois certainement avoir raison pour le simplex. Par contre, quel est justement cette fonction de coüt? Comment l'exprimer dans mon cas? C'est tout l'objet du problème en fin de compte!

Merci.

[ToTo13]

Bonjour,

pour ce qui est de la fonction de coût, c'est ce que j'ai marqué précédemment :

Tu veux donc minimer : Somme(i=1..N) |F(i)-Yi|, avec N le nombre d'individus.
Dans le cas d'une régression logistique tu as
- F(x) = exp(f(x)) / (1+exp(f(x))).
- f(x) = Somme(i=1..M) Ai.Xi, avec A le vecteur contenant les M caractéristiques de ton individu et X les M coefficients que tu cherches.

[steph42]

Ok! C'est donc ça cette fonction de coût!

Donc le but es de la minimiser. On peut même essayer de la mettre au carré et de minimiser le résultat: ça revient à résoudre par moindres carrés! Il suffit de dériver par rapport à chaque coefficient recherché, et on a autant d'équations que d'inconnues. Dans un cas linéaire, résoudre par moindres carrés est très facile. Ici, c'est loin d'être le cas!

Comment implémenter l'algorithme du simplex alors? Je choisis des coefficients au hasard pour l'initialisation, et après?

[ToTo13]

Bonjour,

j'ai eu le même problème que toi récemment. J'ai essayé de trouver un algo du simplex déjà implémenté et qui fonctionne correctement... et bien j'ai rien trouvé de convainquant .
La plupart des algos sont des versions pour maximiser le problème et ceux qui minimisent mettent les résultats dans un ordre assez peu cohérent (ou du moins que je n'ai pas saisi au premier coup d'oeil).
En tout cas, si tu veux du code pour la régression logistique, tu peux regarder la bibliothèque Weka en Java.

[pseudocode]

Je suis la discussion de loin depuis un moment, mais il y a quelquechose qui m'échappe:

Le simplex a pour but d'optimiser une fonction linéaire soumise à des contraintes linéaires. Quel rapport avec la résolution du système binaire du P.O ?

[ToTo13]

Bonjour,

en fait la fonction f(x) que j'explique plus haut est une fonction linéaire, c'est elle que le simplex doit résoudre.
Seule la fonction de coût à minimiser fait intervenir les exp().

[pseudocode]

Bonjour,

en fait la fonction f(x) que j'explique plus haut est une fonction linéaire, c'est elle que le simplex doit résoudre.
Seule la fonction de coût à minimiser fait intervenir les exp().

Ah, ok. On ne peut pas dire que ca soit vraiment "linéaire", mais en faisant des iterations sur les différences finies ca devrait marcher.

[steph42]

Bonjour,

en fait l'algo du simplex a l'air très apprécié, mais je ne vois vraiment pas comment l'utiliser dans mon cas! En effet, je n'ai AUCUNE contrainte: pas d'a priori sur le signe des coefficients (enfin si: certains doivent être négatifs et d'autres positifs...), et je n'ai que la fonction de coût à minimiser... Les algo déjà implémentés que j'ai trouvés fonctionnent tous dans les cas précis où l'on veut minimiser la fonction de coût cx, avec comme contraintes Ax< (ou >)b et x>0
D'autre part, du moment que l'on fait intervenir des exp dans la fonction de coût, ce n'est malheuresement plus un problème linéaire.

Quel est le principe des différences finies? Il faut bien avoir un a priori sur les "valeurs", non? Car d'après ce que j'ai compris, on fait un Développement limité?

La fonction Matlab fminsearch peut elle être une solution pour utiliser le simplex? Je vais regarder.

D'autre part, je travaille sous Matlab (pas d'autres logiciels dispo au labo), mais j'ai trouvé des fonctions réalisant la régression logistique. Elles ne me donnent pas satisfaction dans les résultats, mais bon, en meme temps, je m'y attendais un peu. A tester donc, sur des cas simples.

[ToTo13]

Bonjour,

en fait l'algo du simplex a l'air très apprécié, mais je ne vois vraiment pas comment l'utiliser dans mon cas! En effet, je n'ai AUCUNE contrainte: pas d'a priori sur le signe des coefficients (enfin si: certains doivent être négatifs et d'autres positifs...), et je n'ai que la fonction de coût à minimiser... Les algo déjà implémentés que j'ai trouvés fonctionnent tous dans les cas précis où l'on veut minimiser la fonction de coût cx, avec comme contraintes Ax< (ou >)b et x>0
D'autre part, du moment que l'on fait intervenir des exp dans la fonction de coût, ce n'est malheuresement plus un problème linéaire.

Bien venue dans le problème que j'ai rencontré il y a quelques temps
Pour ce qui est du problème, le simplex peut quand même le résoudre car il y a une somme de coefficient, donc linéaires. Seul le calcul de la fonction de coût fait intervenir les exp(), donc on s'en sort.