4
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 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

0

Reset to default

Your Answer

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