Système «d'équations stochastiques»

Considérons un graphique avec sommets et arêtes. Les sommets sont étiquetés avec des variables réelles , où est fixe. Chaque arête représente une "mesure": pour l'arête , j'obtiens une mesure . Plus précisément, est une grandeur vraiment aléatoire en , uniformément distribuée et indépendante de toutes les autres mesures (bords). $n$ $m$ $x_i$ $x_1=0$ $(u,v)$ $z \approx x_u - x_v$ $z$ $(x_u - x_v) \pm 1$

On me donne le graphique et les mesures, avec la promesse de distribution ci-dessus. Je veux "résoudre" le système et obtenir le vecteur de . Existe-t-il des travaux sur des problèmes de ce type? $x_i$

En fait, je veux résoudre un problème encore plus simple: quelqu'un me pointe vers les sommets et , et je dois calculer . Il y a beaucoup de choses à essayer, comme trouver un chemin le plus court, ou trouver autant de chemins disjoints que possible et en faire la moyenne (pondérée par l'inverse de la racine carrée de la longueur). Y a-t-il une réponse "optimale"? $s$ $t$ $x_s - x_t$

Le problème du calcul de n'est pas lui-même complètement défini (par exemple dois-je supposer un a priori sur les variables?) $x_s - x_t$

ds.algorithms graph-algorithms Mihai
la source

bien que ce ne soit pas une réponse, l'utilisation d'un filtre de Kalman le long d'un chemin de s à t vient à l'esprit comme un moyen d'obtenir une poignée décente sur la longueur du chemin.

Suresh Venkat

Cela pourrait ne pas aider, ou pourrait être bien plus technologique que nécessaire, mais il existe une théorie en développement de la topologie algébrique stochastique pour répondre aux questions en robotique et en biologie moléculaire sur les complexes dont les bords sont mesurés de manière imprécise. Il existe des théorèmes sur l'asymptotique des liaisons aléatoires (liaison = graphique avec poids de bord). Par exemple, je pense que les résultats de cet article vous permettraient d'obtenir les nombres Betti attendus de votre graphique: arxiv.org/abs/0708.2997

Aaron Sterling

Le fait que les erreurs soient uniformément réparties dans [-1,1] plutôt que dans une autre distribution est-il inhérent à votre problème ou une décision de modélisation arbitraire? Si ce dernier est possible, vous pouvez probablement rendre les choses beaucoup plus simples en utilisant des gaussiens à la place.

Warren Schudy

\pm 1

$\pm 1$

Réponses:

Le domaine dans lequel vous souhaitez trouver des réponses est l'apprentissage automatique. Vous avez décrit un modèle graphique. Je pense que dans ce cas, des méthodes aussi simples que la propagation de la croyance devraient suffire.

Raphael
la source

La propagation des croyances n'est pas exacte dans les graphiques généraux. Le problème de Mihai semble être résolu avec des méthodes plus fondées sur des principes que la propagation des croyances.

Warren Schudy

$x$

Warren Schudy
la source

s

$s$

t

$t$

x

$x$

x_{s} - x_{t}

$x_s-x_t$

x_{s} - x_{t}

$x_s-x_t$

x_{s} - x_{t} = c

$x_s - x_t = c$

Warren Schudy

Bien sûr, le calcul du volume du polytope particulier en question pourrait potentiellement être beaucoup plus facile. Il faudrait que j'y pense.

Warren Schudy

Je soupçonne que les Gaussiens se comportent mieux en ce que le MLE de la distribution conjointe donne également le MLE de chaque variable. Mais il faudrait que je réfléchisse davantage et / ou que je vérifie pour être sûr.

Warren Schudy

Votre exemple série / parallèle suggère que la minimisation de la somme des résidus au carré peut être une heuristique efficace pour certains graphiques même lorsque vos erreurs ne sont pas gaussiennes.

Warren Schudy