5
$\begingroup$

Assume that I have an array $A$ of $n$ numerical values where some are known and some are unknown (with $A[0]$ and $A[n-1]$ assumed to be known). If I want to estimate an unknown value $A[i]$, a reasonable way is to perform linear interpolation: find the largest $j < i$ such that $A[j]$ is known, find the smallest $k > i$ such that $A[k]$ is known, and do a weighted average $A[j] := {k-i \over k-j}A[k] + {i-j \over k-j}A[j]$. In particular, this ensures that the following property (*) holds:

$$\text{if } A[j] \leq A[k] \text{ then } A[j] \leq A[i] \leq A[k]$$

Now, you can see an array as a totally ordered structure, and wonder about what would happen in the case of a partial order. Assume that I have a DAG $G = (V, E)$ of $n$ nodes where every node $v \in V$ has a numerical value $\mu(v)$ where some values are known and some are unknown (with the values of the roots and leaves assumed to be known). If I want to estimate some unknown $\mu(v)$, it seems that I should interpolate it out of the values of the closest ancestors and descendents of $v$ whose values are known. The question is: what should we do, exactly? Is there a generalization of linear interpolation in this setting?

[Here is a possible choice: for every couple $(u, w)$ of ancestors and descendents of $v$, perform linear interpolation along all the possible chains between $u$, $v$ and $w$ to get a value for $v$, and average all the values over all chains and ancestor-descendent pairs to get your final estimate. Is this the correct way to do things? Can this estimation be computed more efficiently than with this definition? (i.e., could we do it in linear time in the size of the neighborhood of $v$ under consideration, rather than in a quadratic way?). Do we still have some variant of property (*)? (note that, even if you assume monotonicity, i.e. for each ancestor-descendent couple $(u, w)$ you assume $\mu(u) \leq \mu(w)$, then the estimation $\mu(v)$ obtained by the previous process may still violate monotonicity, i.e. $\mu(v) > \mu(u)$ for some ancestor $u$ of $v$)]

Improve this question
$\endgroup$
5
  • $\begingroup$ I'm guessing you assume the function $\mu$ is monotone along the partial order ? In particular, what would you do if for some interpolation paths $\mu$ decreases and for others it increases ? $\endgroup$
    – Suresh Venkat
    Commented Dec 27, 2012 at 18:43
  • $\begingroup$ Assuming that $\mu$ is monotone along the partial order (or Suresh's point is otherwise handled), it looks like basic memoization (to avoid redundant computation) would give a little win over the approach given in the question, at least on average (in the sense of performance on uniform DAGs), and especially so on low treewidth DAGs. $\endgroup$
    – Daniel Apon
    Commented Dec 27, 2012 at 18:50
  • 3
    $\begingroup$ I would reframe this problem as finding the best assignment of values to the nodes such that for each directed edge $(u,v)$ we have $A[u] < A[v]$. But what function are you trying to optimize? One natural choice that's consistent with standard linear interpolation is $\sum_{(u,v)} (A[v] - A[u])^2$, where the sum is over all edges of the dag, but is that what you actually want? $\endgroup$
    – Jeffε
    Commented Dec 27, 2012 at 19:24
  • 1
    $\begingroup$ Suresh Venkat: In the setting I have in mind, $\mu$ is indeed monotone, but even then things are weird (cf. the last sentence of my question). If it is not monotone, there might still be sensible things to do: for instance if there are two immediate ancestors with values -1 and 1, and two immediate descendents with values -1 and 1, then it seems reasonable to interpolate 0. JɛffE: I don't know the function I want to optimize, it's precisely my question: what is the most natural thing to optimize here to follow the spirit of a linear interpolation? $\endgroup$
    – Antoine Amarilli 'a3nm'
    Commented Dec 27, 2012 at 20:01
  • 1
    $\begingroup$ I'm not convinced that the ordering of the array is relevant here. Notice that linear interpolation makes sense for points in an arbitrary dimensional space: find a simplicial decomposition and then do barycentric interpolation in the interior of a simplex. So considering a DAG (or a poset in general) is adding additional structure to the interpolation problem, which means you have an extra degree of freedom which you can *choose to set. It's not entirely clear that there's a single "right" choice unless there is some other consideration deriving from the underlying problem. $\endgroup$
    – Suresh Venkat
    Commented Dec 27, 2012 at 20:43

1 Answer 1

Reset to default
2
$\begingroup$

In a recent paper, we propose such a scheme. The scheme is illustated in a specific crowdsourcing application setting, but the idea is fairly simple. We just see the order constraint $\mu(u) \leq \mu(v)$ of each DAG edge $(u, v)$ as a linear inequality constraint, we consider the admissible convex polytope of assignments to these linear inequalities, and we choose the center of mass of this polytope as our interpolation result.

The paper explains the scheme in more detail, includes an algorithm, computational hardness results, an approximation scheme that derives from existing work, a tractable case when the DAG is a tree, and a discussion of alternate schemes.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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