11
$\begingroup$

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?)

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Suresh Venkat Nov 10 '10 at 23:19
  • $\begingroup$ 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: arxiv.org/abs/0708.2997 $\endgroup$ – Aaron Sterling Nov 11 '10 at 0:45
  • $\begingroup$ 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. $\endgroup$ – Warren Schudy Nov 11 '10 at 17:59
  • $\begingroup$ The $\pm 1$ error model is certainly inherent to the problem. $\endgroup$ – Mihai Nov 12 '10 at 2:16
3
$\begingroup$

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 should suffice.

$\endgroup$
  • $\begingroup$ Belief propagation is not exact in general graphs. Mihai's problem appears to be solvable with more principled methods than belief propagation. $\endgroup$ – Warren Schudy Nov 11 '10 at 18:18
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Mihai Nov 11 '10 at 16:42
  • $\begingroup$ 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: mathoverflow.net/questions/979/… . So you can do a binary search for an approximate max likelihood value. $\endgroup$ – Warren Schudy Nov 11 '10 at 17:57
  • $\begingroup$ Of course computing the volume of the particular polytope in question could potentially be a lot easier. I would have to think about it. $\endgroup$ – Warren Schudy Nov 11 '10 at 17:58
  • $\begingroup$ 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. $\endgroup$ – Warren Schudy Nov 11 '10 at 18:08
  • $\begingroup$ 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. $\endgroup$ – Warren Schudy Nov 11 '10 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.