Say $\Omega$ is a finite set and $f$ a probability mass function (pmf) over $\Omega^d$. Now let $T$ be a spanning tree on the set $V=\{1,2,\ldots,d\}$, and consider a collection of one- and two- dimensional pmfs $f_i$ over $\Omega$ and $f_{ij}$ over $\Omega^2$, respectively. Together, these induce a tree distribution over $\Omega^d$ as follows: $$ f_{T}(x)=\prod\limits_{(i,j)\in T}\frac{f_{ij}(x_{i},x_{j})}{f_{i}(x_{i})f_{j}(x_{j})}\prod_{i=1}^{d}f_{i}(x_{i}). $$

One can ask, for a given pmf $f$: what is the best approximation by some $f_T$? To make the question well-posed, one must provide a cost function on pairs of pmfs. For the choice of KL-divergence (corresponding, for finite samples, to maximum likelihood), Chow and Liu [1] gave a beautiful efficient algorithm based on Kruskal's MST.

Question: What if we want to minimize $||f-f_T||_1$ -- that is, under the $L_1$ distance? I suspect that this is computationally hard, but am hoping for a more quantitative statement. Is there any formal sense in which this problem is known to be hard? Are there any known efficient approximation algorithms?

[1] https://ieeexplore.ieee.org/document/1054142

  • 1
    $\begingroup$ So, roughly speaking, you're asking about the complexity of agnostically learning (in TV distance) degree-1 Bayes nets? $\endgroup$
    – Clement C.
    Dec 16, 2021 at 9:43
  • 1
    $\begingroup$ Now that you put it that way... I guess! But the learning is a bit of a red herring, since the question is about computational complexity on finite data. An interesting issue, though, is one of representation. If your input is the tensor of all of the $|\Omega|^d$ values of $f$, then you should be allowed $\exp(d)$ time just to read the data. So maybe you have oracle access to $f$ and the 1- and 2- dim marginals?.. Like I said, even getting some sort of a formal statement is non-trivial. $\endgroup$
    – Aryeh
    Dec 16, 2021 at 9:48


Your Answer

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