Sistema de "ecuaciones estocásticas"

11

Considere una gráfica con vértices ym aristas. Los vértices están etiquetados con variables reales x i , donde x 1 = 0 es fijo. Cada borde representa una "medida": para el borde ( u , v ) , obtengo una medida z ≈ x u - x v . Más precisamente, z es una cantidad verdaderamente aleatoria en ( x u - x v ) ± 1 , distribuida uniformemente e independiente de todas las demás medidas (aristas).nmxix1=0(u,v)z≈xu−xvz(xu−xv)±1

Me dan el gráfico y las medidas, con la promesa de distribución de arriba. Quiero "resolver" el sistema y obtener el vector de 's. ¿Existe algún trabajo sobre problemas de este tipo?xi

En realidad, quieren resolver un problema aún más simple: puntos a alguien me vértices y t , y tengo para calcular x s - x t . Hay muchas cosas para probar, como encontrar un camino más corto o encontrar tantos caminos disjuntos como sea posible y promediarlos (ponderado por el inverso de la raíz cuadrada de la longitud). ¿Hay una respuesta "óptima"?stxs−xt

El problema de calcular sí mismo no está completamente definido (por ejemplo, ¿debería asumir un previo sobre las variables?)xs−xt

ds.algorithms graph-algorithms Mihai
fuente
Si bien esto no es una respuesta, viene a la mente usar un filtro de Kalman a lo largo de una ruta de s a t como una forma de obtener un control decente sobre la longitud de la ruta.
Suresh Venkat
Esto podría no ayudar, o podría ser una tecnología mucho más de lo que se necesita, pero hay una teoría en desarrollo de la topología algebraica estocástica para abordar preguntas en robótica y biología molecular sobre complejos cuyos bordes se miden de manera imprecisa. Existen teoremas sobre la asintótica de los enlaces aleatorios (enlace = gráfico con pesos de borde). Por ejemplo, creo que los resultados en este documento le permitirán obtener los números Betti esperados de su gráfico: arxiv.org/abs/0708.2997
Aaron Sterling
¿Es el hecho de que los errores están distribuidos uniformemente en [-1,1] en lugar de alguna otra distribución inherente a su problema o una decisión de modelado arbitrario? Si es esto último, probablemente puedas simplificar mucho las cosas usando gaussianos.
Warren Schudy
±1

Respuestas:

3

El área en la que desea buscar respuestas es el aprendizaje automático. Has descrito un modelo gráfico. Creo que en este caso, los métodos tan fáciles como la Propagación de creencias deberían ser suficientes.

Rafael
fuente
La propagación de creencias no es exacta en los gráficos generales. El problema de Mihai parece resolverse con métodos más basados ​​en principios que la propagación de creencias.
Warren Schudy
3

x

Warren Schudy
fuente
st
xxs−xtxs−xtxs−xt=c
Warren Schudy
Por supuesto, calcular el volumen del politopo particular en cuestión podría ser mucho más fácil. Tendría que pensarlo.
Warren Schudy
Tengo la sospecha de que los gaussianos se comportan mejor porque el MLE de la distribución conjunta también proporciona MLE de cada variable. Pero tendría que pensar más y / o buscarlo para estar seguro.
Warren Schudy
Su ejemplo de serie / paralelo sugiere que minimizar la suma de los residuos al cuadrado puede ser una heurística efectiva para algunos gráficos, incluso cuando sus errores no son gaussianos.
Warren Schudy