<p>Say <span class="math-container">$\Omega$</span> is a finite set and <span class="math-container">$f$</span> a probability mass function (pmf) over <span class="math-container">$\Omega^d$</span>. Now let <span class="math-container">$T$</span> be a spanning tree on the set <span class="math-container">$V=\{1,2,\ldots,d\}$</span>, and consider a collection of one- and two- dimensional pmfs <span class="math-container">$f_i$</span> over <span class="math-container">$\Omega$</span> and <span class="math-container">$f_{ij}$</span> over <span class="math-container">$\Omega^2$</span>, respectively. Together, these induce a tree distribution over <span class="math-container">$\Omega^d$</span> as follows:
<span class="math-container">$$
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}).
$$</span></p>
<p>One can ask, for a given pmf <span class="math-container">$f$</span>: what is the best approximation by some <span class="math-container">$f_T$</span>? 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.</p>
<p>Question: What if we want to minimize <span class="math-container">$||f-f_T||_1$</span> -- that is, under the <span class="math-container">$L_1$</span> 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?</p>
<p>[1] <a href="https://ieeexplore.ieee.org/document/1054142" rel="nofollow noreferrer">https://ieeexplore.ieee.org/document/1054142</a></p>

CC BY-SA 4.0
2021-12-16T09:43:02.360Z
So, roughly speaking, you're asking about the complexity of agnostically learning (in TV distance) degree-1 Bayes nets?
Clement C.
CC BY-SA 4.0
2021-12-16T09:48:17.500Z
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.
Aryeh
<np-hardness><optimization><approximation-hardness>
Analogue of Chow-Liu tree for $L_1$
Aryeh
# Analogue of Chow-Liu tree for $L_1$

(Asked by: username_0 on 2021-12-15)

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>

**Tags:** np-hardness, optimization, approximation-hardness
> **Comments:**
> **username_1**: So, roughly speaking, you're asking about the complexity of agnostically learning (in TV distance) degree-1 Bayes nets?  
> **username_0**: 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.  

---

## 0 answers

