Sistema de "equações estocásticas"

11

Considere um gráfico com vértices e arestas. Os vértices são rotulados com variáveis ​​reais , onde é fixo. Cada aresta representa uma "medida": para a aresta , obtenho uma medida . Mais precisamente, é uma quantidade verdadeiramente aleatória em , distribuída uniformemente e independente de todas as outras medidas (arestas).m x i x 1 = 0 ( u , v ) z ≈ x u - x v z ( x u - x v ) ± 1nmxix1=0(u,v)z≈xu−xvz(xu−xv)±1

Recebo o gráfico e as medidas, com a promessa de distribuição acima. Eu quero "resolver" o sistema e obter o vetor dexi 's. Existe algum trabalho sobre problemas desse tipo?

Na verdade, eu quero resolver um problema ainda mais simples: pontos Alguém me para vértices e , e eu tenho que computação . Há muitas coisas a serem tentadas, como encontrar um caminho mais curto ou encontrar o maior número possível de caminhos separados e calculá-los como média (ponderada pelo inverso da raiz quadrada do comprimento). Existe uma resposta "ótima"?t x s - x tstxs−xt

O problema de calcular não está completamente definido (por exemplo, devo assumir um prior nas variáveis?)xs−xt

ds.algorithms graph-algorithms Mihai
fonte
Embora isso não seja uma resposta, usar um filtro Kalman ao longo de um caminho de s a t vem à mente como uma maneira de obter um controle decente do comprimento do caminho.
Suresh Venkat
Isso pode não ajudar, ou pode ser muito mais tecnologia do que o necessário, mas existe uma teoria em desenvolvimento da topologia algébrica estocástica para abordar questões em robótica e biologia molecular sobre complexos cujas bordas são medidas imprecisamente. Existem teoremas sobre assintóticos de ligações aleatórias (ligação = gráfico com pesos das arestas). Por exemplo, acho que os resultados deste documento permitiriam obter os números de Betti esperados em seu gráfico: arxiv.org/abs/0708.2997
Aaron Sterling
O fato de os erros serem distribuídos uniformemente em [-1,1] ao invés de alguma outra distribuição inerente ao seu problema ou a uma decisão de modelagem arbitrária? Neste último caso, você provavelmente pode tornar as coisas muito mais simples usando Gaussianos.
Warren Schudy
O modelo de erro é certamente inerente ao problema. ±1
Mihai

Respostas:

3

A área para a qual você deseja obter respostas é o aprendizado de máquina. Você descreveu um modelo gráfico. Penso que, neste caso, métodos tão fáceis quanto a Propagação de Crenças devem ser suficientes.

Rafael
fonte
A propagação de crenças não é exata nos gráficos gerais. O problema de Mihai parece ser solucionável com métodos mais baseados em princípios do que propagação de crenças.
111110 Warren Schudy
3

x

Warren Schudy
fonte
st
xxs−xtxs−xtxs−xt=c
111110 Warren Schudy
É claro que calcular o volume do politopo específico em questão poderia ser muito mais fácil. Eu teria que pensar sobre isso.
Warren Schudy 11/11/2010
Suspeito que os gaussianos se comportem melhor, pois o MLE da distribuição conjunta também fornece o MLE de cada variável. Mas eu teria que pensar mais e / ou procurá-lo para ter certeza.
Warren Schudy 11/11/2010
Seu exemplo de série / paralelo sugere que minimizar a soma dos resíduos quadráticos pode ser uma heurística eficaz para alguns gráficos, mesmo quando seus erros não são gaussianos.
Warren Schudy