<p>If the measurements were Gaussian then minimizing the sum of squared residuals (like linear least squares curve fitting) would give you a max likelihood estimator. For your problem I haven't written anything down but I would guess (via Bayes rule) that any set of $x$s that could have generated your data is equally likely to have produced it. You can find one max likelihood solution by finding a point in a polytope (i.e. solving a linear program with no objective). Depending on what you want to do with your estimate (loss function) the best estimator is the one that minimizes the integral of your loss function over that polytope. I'll wait until you tell us what your loss function is before guessing about how to evaluate  and minimize that integral efficiently.</p>

CC BY-SA 2.5
2010-11-11T16:42:53.717Z
This seems hard to believe. Suppose my graph is series-parallel between $s$ and $t$, and every serial path has the same length. Every path gives me an independent measurement of the same quantity, and if the paths are long, the error becomes gaussian. It seems clear that the unique mle is to average the paths, no?
Mihai
CC BY-SA 2.5
2010-11-11T17:57:08.930Z
Good point. Anywhere in the polytope is a maximum likelihood estimator of the joint distribution of the $x$s, but I forgot that you were looking for an estimator of $x_s-x_t$ only. To get the max likelihood estimator of $x_s-x_t$ you need to find the plane $x_s - x_t = c$ with maximum intersection with that polytope. It appears that in general computing volumes of polytopes is hard to do exactly but can be approximated: http://mathoverflow.net/questions/979/algorithm-for-finding-the-volume-of-a-convex-polytope . So you can do a binary search for an approximate max likelihood value.
Warren Schudy
CC BY-SA 2.5
2010-11-11T17:58:55.560Z
Of course computing the volume of the particular polytope in question could potentially be a lot easier. I would have to think about it.
Warren Schudy
CC BY-SA 2.5
2010-11-11T18:08:55.770Z
I have a suspicion that Gaussians are better behaved in that the MLE of the joint distribution also gives MLE of each variable. But I would have to think more and/or look it up to be sure.
Warren Schudy
CC BY-SA 2.5
2010-11-11T18:14:47.543Z
Your series/parallel example suggests that minimizing the sum of squared residuals may be an effective heuristic for some graphs even when your errors are not Gaussian.
Warren Schudy
CC BY-SA 2.5
2010-11-11T14:42:18.437Z
2010-11-11T14:42:18.437Z
Warren Schudy
<p>The area you want to look at for answers to is machine learning. You have desribed a graphical model. I think in this case methods as easy as <a href="http://en.wikipedia.org/wiki/Belief_propagation" rel="nofollow">Belief Propagation</a> should suffice.</p>

CC BY-SA 2.5
2010-11-11T18:18:23.747Z
Belief propagation is not exact in general graphs. Mihai's problem appears to be solvable with more principled methods than belief propagation.
Warren Schudy
CC BY-SA 2.5
2010-11-10T23:34:01.440Z
2010-11-10T23:34:01.440Z
Raphael
<p>Consider a graph with $n$ vertices and $m$ edges. The vertices are labelled with real variables $x_i$, where $x_1=0$ is fixed. Each edge represents a "measurement": for edge $(u,v)$, I obtain a measurement $z \approx x_u - x_v$. More precisely, $z$ is a truly random quantity in $(x_u - x_v) \pm 1$, uniformly distributed and independent of all other measurements (edges).</p>

<p>I am given the graph and the measurements, with the distribution promise for above. I want to "solve" the system and obtain the vector of $x_i$'s. Is there some body of work on problems of this type? </p>

<p>Actually, I want to solve an even simpler problem: somebody points me to vertices $s$ and $t$, and I have to compute $x_s - x_t$. There are many things to try, like finding a shortest path, or finding as many disjoint paths as possible and averaging them (weighted by the inverse of the square root of the length). Is there an "optimal" answer?</p>

<p>The problem of computing $x_s - x_t$ is itself not completely defined (e.g. should I assume a prior on the variables?)</p>

CC BY-SA 2.5
2010-11-10T23:19:26.513Z
while this is not an answer, using a Kalman filter along a path from s to t comes to mind as a way of getting a decent handle on the path length.
Suresh Venkat
CC BY-SA 2.5
2010-11-11T00:45:52.707Z
This might not help, or might be way more technology than is needed, but there's a developing theory of stochastic algebraic topology to address questions in robotics and molecular biology about complexes whose edges are imprecisely measured. There are theorems about asymptotics of random linkages (linkage = graph with edge weights).  For example, I think the results in this paper would allow you to obtain the expected Betti numbers of your graph: http://arxiv.org/abs/0708.2997
Aaron Sterling
CC BY-SA 2.5
2010-11-11T17:59:52.437Z
Is the fact that the errors are uniformly distributed in [-1,1] rather than some other distribution inherent to your problem or an arbitrary modeling decision? If the latter you can probably make things a lot simpler by using Gaussians instead.
Warren Schudy
CC BY-SA 2.5
2010-11-12T02:16:59.653Z
The $\pm 1$ error model is certainly inherent to the problem.
Mihai
<ds.algorithms><graph-algorithms>
System of "stochastic equations"
Mihai
# System of "stochastic equations"

(Asked by: username_0 on 2010-11-10)

Consider a graph with $n$ vertices and $m$ edges. The vertices are labelled with real variables $x\_i$, where $x\_1=0$ is fixed. Each edge represents a "measurement": for edge $(u,v)$, I obtain a measurement $z \approx x\_u - x\_v$. More precisely, $z$ is a truly random quantity in $(x\_u - x\_v) \pm 1$, uniformly distributed and independent of all other measurements (edges).

I am given the graph and the measurements, with the distribution promise for above. I want to "solve" the system and obtain the vector of $x\_i$'s. Is there some body of work on problems of this type?

Actually, I want to solve an even simpler problem: somebody points me to vertices $s$ and $t$, and I have to compute $x\_s - x\_t$. There are many things to try, like finding a shortest path, or finding as many disjoint paths as possible and averaging them (weighted by the inverse of the square root of the length). Is there an "optimal" answer?

The problem of computing $x\_s - x\_t$ is itself not completely defined (e.g. should I assume a prior on the variables?)

**Tags:** ds.algorithms, graph-algorithms

> **Comments:**
> **username_1**: while this is not an answer, using a Kalman filter along a path from s to t comes to mind as a way of getting a decent handle on the path length.  
> **username_2**: This might not help, or might be way more technology than is needed, but there's a developing theory of stochastic algebraic topology to address questions in robotics and molecular biology about complexes whose edges are imprecisely measured. There are theorems about asymptotics of random linkages (linkage = graph with edge weights).  For example, I think the results in this paper would allow you to obtain the expected Betti numbers of your graph: http://arxiv.org/abs/0708.2997  
> **username_3**: Is the fact that the errors are uniformly distributed in [-1,1] rather than some other distribution inherent to your problem or an arbitrary modeling decision? If the latter you can probably make things a lot simpler by using Gaussians instead.  
> **username_0**: The $\pm 1$ error model is certainly inherent to the problem.  

---

## 2 answers

### Answer by username_3 on 2010-11-11. Score: 3

If the measurements were Gaussian then minimizing the sum of squared residuals (like linear least squares curve fitting) would give you a max likelihood estimator. For your problem I haven't written anything down but I would guess (via Bayes rule) that any set of $x$s that could have generated your data is equally likely to have produced it. You can find one max likelihood solution by finding a point in a polytope (i.e. solving a linear program with no objective). Depending on what you want to do with your estimate (loss function) the best estimator is the one that minimizes the integral of your loss function over that polytope. I'll wait until you tell us what your loss function is before guessing about how to evaluate and minimize that integral efficiently.

> **Comments:**
> **username_0**: This seems hard to believe. Suppose my graph is series-parallel between $s$ and $t$, and every serial path has the same length. Every path gives me an independent measurement of the same quantity, and if the paths are long, the error becomes gaussian. It seems clear that the unique mle is to average the paths, no?  
> **username_3**: Good point. Anywhere in the polytope is a maximum likelihood estimator of the joint distribution of the $x$s, but I forgot that you were looking for an estimator of $x_s-x_t$ only. To get the max likelihood estimator of $x_s-x_t$ you need to find the plane $x_s - x_t = c$ with maximum intersection with that polytope. It appears that in general computing volumes of polytopes is hard to do exactly but can be approximated: http://mathoverflow.net/questions/979/algorithm-for-finding-the-volume-of-a-convex-polytope . So you can do a binary search for an approximate max likelihood value.  
> **username_3**: Of course computing the volume of the particular polytope in question could potentially be a lot easier. I would have to think about it.  
> **username_3**: I have a suspicion that Gaussians are better behaved in that the MLE of the joint distribution also gives MLE of each variable. But I would have to think more and/or look it up to be sure.  
> **username_3**: Your series/parallel example suggests that minimizing the sum of squared residuals may be an effective heuristic for some graphs even when your errors are not Gaussian.  

---

### Answer by username_4 on 2010-11-10. Score: 3

The area you want to look at for answers to is machine learning. You have desribed a graphical model. I think in this case methods as easy as [Belief Propagation](http://en.wikipedia.org/wiki/Belief_propagation) should suffice.

> **Comments:**
> **username_3**: Belief propagation is not exact in general graphs. username_0's problem appears to be solvable with more principled methods than belief propagation.  

---

