réseaux bayésiens Fermé

Question

Bonjour à toutes et à tous,
je travaille dans le cadre de mon stage de recherche sur les reseaux bayésiens.et j'ai une idée pour minimiser les calculs de l'inférence dans un réseaux bayésiens.mais je ne suis pas informaticien, donc j'ai une petite question.
est ce qu'on peut chercher dans un réseaux tous les chemins possibles ?si c'est possible merci de m'aider SVP
merci d'avance.

mamiemando · Answer

En général le calcul exhaustif de tout les chemins d'un graphe est une mauvaise idée car son nombre est exponentiel. 

Que veux tu faire exactement ? 

Il existe des façon de limiter le nombre de chemin (interdire les boucles par exemple) si tu fais un DFS (depth first search), et des algos de calcul de k plus courts chemins (comme l'algorithme d'eppstein) mais ça dépend grandement de ce que tu veux faire.

Bonne chance

mamiemando · Answer

Pas vraiment en fait. Je cherche à comprendre ce que tu veux faire et je n'y arrive pas. Décris-moi le problème d'un point de vue théorie des graphes, sans chercher pour l'instant à me dire comment tu veux le résoudre. Quel est le problème, que veux tu inférer, quelles sont tes paramètres d'entrées etc...

rbdmine · Answer

par exmple je voudrais trouvé les noeud qui représente un puit(c à d le noeud ou le chemin est convergeant)

mamiemando · Answer

Bon comme je n'ai pas eu la joie de faire de réseau bayesien je suis repartie de ça :
https://fr.wikipedia.org/wiki/R%C3%A9seau_bay%C3%A9sien

Toi tu as un graphe G(V,E) acyclique orienté, qui représente la structure de ton modèle. Chaque prédécesseur d'un évènement (par exemple une maladie) représente une cause (par exemple un symptôme) qui a pu l'engendrer. Chaque arc l'importance qu'à cette cause sur un évènement. Chaque arc est pondéré par une probabilité. 

Si j'ai bien compris tu disposes d'une base d'apprentissage qui te permet de régler les poids de ces arcs. En faisant concorder au mieux ces mesures et le résultat attendu tu es capable de régler les poids. Je suppose que c'est la que la d-distance intervient.

Donc concrètement on a un graphe, dont certains sommets sont des symptômes Vs, et les autres des maladies Vm. Les arcs vont forcément de Vs à Vm et sont pondérés entre 0 et 1. C'est bon jusque là ?

Maintenant explique moi comment tu règles ces poids et ce que tu veux faire (un exemple simple est pas de refus :p)

rbdmine · Answer

salut,
pas exactement ca,au fait ce n'est pas les arcs qui portent les poids mais les noeuds qui portent les probabilités conditionnelles à prioris.
pour mon cas je n'utilise pas l'apprentissage parceque les probabilités à priori sont données par l'expert du domaine donc ce n'est pas la peine de faire un apprentissage.
donc chaque noeud est associé à une table de probabilité.
maitenant en fonction des observations  je voudrais localiser l'organe qui est responsable de cette observation en calculant la probabilité conditionnelle sachant cette observation en utilisant le théoreme de bayes,lois jointes et loi marginale et pour la faire il faut inférer cette observation sur tout le reseaux.mais comme je t'avais di l'inférence est NP-difficile .c'est pour je voudrais en fonction des observation détecter les noeuds qui bloquent la propagations et donc limiter les calcules en temps et en mémoire.
pour information, on dit que le chemin est bloqué entre X et Y(noeud) dans les 3 cas suivants:
1-le chemin converge vers un noeuds Z tel que Z est inconnu(c'est pas une observation)
2-le chemin diverge vers un noeuds Z tq Z est connu
3-le chemin est ensérie tq Z est connu
voila j'espere que tu peux m'aider pour faire l'algorithme.

mamiemando · Answer

Mmmh le gros problème c'est que j'ai trop peu de notion en réseau bayesien pour comprendre tout. Il faudrait que tu me dises ce que signifie 
1-le chemin converge vers un noeuds Z tel que Z est inconnu(c'est pas une observation)
2-le chemin diverge vers un noeuds Z tq Z est connu
3-le chemin est ensérie tq Z est connu 

d'un point de vue théorie des graphes. Qu'appelles-tu un chemin qui converge/diverge, que signifie Z est connu ou un connu. Car je ne me vois hélas pas relire la théorie de Bayes :s

rbdmine · Answer

slt,
ce n'est pas un probleme que tu n'as pas de notions de reseaux bayésiens à moins que tu veux l'apprendre,je suis la pour t'aider.sinon mon probleme se pose au niveau de théorie de graphe,je veux avant inférer ,déterminer les chemin bloquées,je m'explique,
je te donne un exemple:
une alarme d'une maison est déclenché dans deux cas :soit un combriolage ou bien un tremblement de terre.
tu peux voir le reseaux sur ce lien:
http://maia.loria.fr/GTMS/Cr/cr5.html
maintenant si je n'ai pas entendu l'alarme (inconnu)donc le tremblemet de terre et le combriolage sont d-séparer (ca veut dire l'alarme a bloqué l'information de l'un à l'autre)
si j'ai entendu une alarme(donc connu) et j'ai senti le tremblement de terre donc autmatiquement je dois dire qu'il ya pas de cambriolage,donc l'information sur le tremblement de terre m'a donné une information sur le cambriolage.
voila, j'espere que j'été clair, 
dans mon algorithme je dois d'abord chercher tous les chemins qui convergent vers un noeud qui n'est pas observé et tous les chemins qui divergent à partir d'un noeud observé et enfin tous les chemins qui sont en séries et qui passent pas un noeud  observé. 
merci

mamiemando · Answer

Ok je vois ce que tu appelles un chemin qui converge et un chemin qui diverge. 

Par contre je ne comprends pas en quoi tu as besoin d'enumérer tous ces chemins. J'aimerais comprendre pourquoi tu as besoin dans ton cas d'énumérer tous les chemins (très coûteux en temps) et pas simplement de regarder les composantes connexes (peu coûteux) après suppression d'un noeud Z. En admettant que tu extraies ces chemins qu'en fais-tu ?

Dans ton exemple je ne comprends pas trop pourquoi il n'y aurait pas pu y avoir simultanément cambriolage + tremblement de terre. 

Enfin si je vois bien à quoi correspond un séparateur dans un graphe j'ai plus de mal à comprendre ce qu'est un d séparateur. Et ce que tu en fais.

Même si tu ne programmes pas en C++ (et a fortiori en boost), la doc ci dessous te donnera un aperçu des algos classiques disponibles en théorie des graphes. Dans ton cas je pense qu'il faut te pencher sur le DFS (vision chemins) et de préférence sur les Connected Components Algorithms (vision composantes du graphes) :
https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/table_of_contents.html

Bonne chance

rbdmine · Answer

salut mamiemando,
merci pour le lien,
pour te répondre , si je trouve tous les chemins bloqués je peux réduire les calculs d'inférence, donc s'il y a une observation sur un noeud et s'il y a un chemin bloqué à partir de ce noeud, les probabilités des noeuds qui sont apres le noeud qui bloquent l'information ne changent pas donc ca serai pas util de propager l'information sur cette partie du graphe.
donc je voudrais séparer les sous graphes qui ne sont pas influencés par l'obseravtion d'ou la limitation des calculs.
en ce qui concerne le tremblement de terre et le cambriolage, si on suit le graphe:
admettant que t'es dans ton bureau , ton voisin t'appel et te di que ton alarme s'est décleché,automatiquement, tu prends ta voiture et tu te dirige vers ta maison pour voir qu'est ce qu'il y a.en meme temps tu allume la radio de ta voiture et tu enttends dire qu'il y a un tremblement de terre dans la region ou se trouve ta maison.en réflechissant tu vas dire que c surement le tremblement de terre qui a fé que l'alarme s'est déclenché et puis tu reviens à ton travail et t'élimine la probabilité qu'il y a un cambriolage.
donc les réseaux bayésiens sont exactement ce qu'on réfléchi dans notre cerveau.
j'espere que j'été clair.
si t'as d'autres questions n'hesite pas

mamiemando · Answer

Pour le cambriolage et le tremblement de terre et le cambriolage c'est donc possible mais très peu probable donc exclu si je suis ton raisonnement. 

J'ai de plus en plus l'impression que dans ton cas il n'est pas utile d'énumérer tous les chemins mais il suffit simplement de considérer les composantes "d-connexe" (je désigne par composante d-connexe les composantes qui restent connexes du graphes lorsqu'on supprime les d-séparateurs du graphe). En terme de complexité ce serait nettement plus rentable (en gros ça devient polynomial) .

Si c'est bel est bien le cas (à toi de me le dire :p) il suffirait de 

1) Déterminer les composantes d-connexe étant donnée une observation (par exemple en s'appuyant sur un algo de strong_component, comme dans boost). Il faudrait que je comprenne mieux ce qu'est un d séparateur pour être plus précise, je n'ai pas très bien compris la définition.

2) Mettre à jour les composantes devant être mises à jour. Peux-tu m'expliquer comment les mises à jours s'effectuent sur un exemple simple. Selon la manière dont la mise à jour se fait il sera peut être possible de repartir sur un DFS ou un BFS.

Si tu veux que je t'aide plus il faut vraiment me définir sur un graphe comment ça marche. Quels sont les propriétés d'un sommet dit d-séparateur, comment est effectuée une mise à jour etc... Tant que je n'aurais pas compris clairement ces notions je ne pourrais pas t'aider plus :s

haned · Answer

Bonjour, 
suppoons que j'ai deux noeud A et B, A est la cause de B, donc la flèche est orienté en direction de B. les noueds sont booléen ( Oui,non)
une probabilité margianle est associée au noeud racine qui est dans notre cas A , P(A=Oui)= 0,5  P(A=non)=0,5;
une probabilité conditionnelle est associée au noeud B , P(B=Oui/A=oui)=  0,45    P(B=Oui/A=non)= 0,56   P(B=non/A=oui)=0,55     P(B=non/A=non)=0,44

En utilisant un outil de réseaux bayésiens, et après inférence on obtient P(B=OUI)= 0,5050, P(B=non)=0,4950 ( on sait calcuer ce résultat on utilisant les lois de probabilité total et la forumules de bayes).

si on change la valeur de Probabilité margianle de A, la probabilité marginale de B change aussi , o utilisant toujours les lois de probabilité connus et applicale sur les réseaux bayésiens.

ma question maintenant est : si change la valeur de probabilité margianle  de B, la valeur de probabilité marginale de A change aussi ( n'oublions pas que A est parent de B), donnons exemple suivant : 
si je pose P(B=oui)=  0,7883 ,  P(B=non)=  0,2117   alors: j'aurais P(A=OUI)= 0,4688    P(A=OUI)=0,5312, les résultats que je vous donne sont botenue d'un outil réseau bayésien qui fait lui même l'inférence. 

est-ce-que possible de m'aider sur la manière dont le calcul  de probabilité  est fait sachant les paramètres de réseaux bayésiens du déprat ( probabilité marginale, probabilité conditionnelle) , moi  je n'arrive pas ;;;;
merci d'avance

Réseaux bayésiens

11 réponses

Discussions similaires