We consider the problem of learning a Bayesian network or directed acyclic
graph (DAG) model from observational data. A number of constraint-based,
score-based and hybrid algorithms have been developed for this purpose. For
constraint-based methods, statistical consistency guarantees typically rely on
the faithfulness assumption, which has been show to be restrictive especially
for graphs with cycles in the skeleton. However, there is only limited work on
consistency guarantees for score-based and hybrid algorithms and it has been
unclear whether consistency guarantees can be proven under weaker conditions
than the faithfulness assumption. In this paper, we propose the sparsest
permutation (SP) algorithm. This algorithm is based on finding the causal
ordering of the variables that yields the sparsest DAG. We prove that this new
score-based method is consistent under strictly weaker conditions than the
faithfulness assumption. We also demonstrate through simulations on small DAGs
that the SP algorithm compares favorably to the constraint-based PC and SGS
algorithms as well as the score-based Greedy Equivalence Search and hybrid
Max-Min Hill-Climbing method. In the Gaussian setting, we prove that our
algorithm boils down to finding the permutation of the variables with sparsest
Cholesky decomposition for the inverse covariance matrix. Using this
connection, we show that in the oracle setting, where the true covariance
matrix is known, the SP algorithm is in fact equivalent to $\ell_0$-penalized
maximum likelihood estimation.

该研究提出了一种新的基于分数的算法（SP 算法）来学习贝叶斯网络或有向无环图（DAG）模型，该算法在弱于忠实性假设的条件下具有一致性保证，并且在一些小 DAG 的模拟中表现出与其他算法相比的优越性。

基于最稀疏排列的有向无环图学习

Learning directed acyclic graphs based on sparsest permutations

Acyclic directed mixed graphs (ADMGs) are graphs that contain directed
($\rightarrow$) and bidirected ($\leftrightarrow$) edges, subject to the
constraint that there are no cycles of directed edges. Such graphs may be used
to represent the conditional independence structure induced by a DAG model
containing hidden variables on its observed margin. The Markovian model
associated with an ADMG is simply the set of distributions obeying the global
Markov property, given via a simple path criterion (m-separation). We first
present a factorization criterion characterizing the Markovian model that
generalizes the well-known recursive factorization for DAGs. For the case of
finite discrete random variables, we also provide a parameterization of the
model in terms of simple conditional probabilities, and characterize its
variation dependence. We show that the induced models are smooth. Consequently,
Markovian ADMG models for discrete variables are curved exponential families of
distributions.

研究了无向边和有向边混合，并且无向边形成无环图的 acyclic directed mixed graphs (ADMGs) 及其概率模型，提出了一种基于简单路径判据的全局马尔科夫性标准 ——m-separation，并得到了该模型的因子分解准则及离散随机变量的参数化表示，验证了该模型的光滑性，从而证明了马尔科夫性 ADMG 模型是曲率指数族。