An efficient search-and-score algorithm for ancestral graphs using multivariate information scores
Nikita Lagrange, Hervé Isambert · 2024
Read An efficient search-and-score algorithm for ancestral graphs using multivariate information scores by Nikita Lagrange, Hervé Isambert (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-17508.txt.
Introduction
Nikita Lagrange and Hervé Isambert speed, in 2024 work, the hunt for cause webs that hide unseen drivers. Such webs mix plain arrows with twin-headed links that mark the hidden hands. Their greedy hunt scores each web by shared facts among tight kin sets — nodes tied by crash paths that stay inside the set's own roots.
For pace, scores are first built from each node's near ring, then from each link's ring. The cap is set at kin sets with up to two crash joints. On hard bench sets the lean hunt beat the known best cause finders. Local facts, well spent, carry the day.
Catalog record
| CREATOR | Nikita Lagrange, Hervé Isambert |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 75 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-17508
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An efficient search-and-score algorithm for ancestral graphs using multivariate information scores Nikita Lagrange, Hervé Isambert Abstract We propose a greedy search-and-score algorithm for ancestral graphs, which include directed as well as bidirected edges, originating from unobserved latent variables. The normalized likelihood score of ancestral graphs is estimated in terms of multivariate information over relevant “ a c ac -connected subsets” of vertices, 𝑪 \bm{C} , that are connected through collider paths confined to the ancestor set of 𝑪 \bm{C} . For computational efficiency, the proposed two-step algorithm relies on local information scores limited to the close surrounding vertices of each node (step 1) and edge (step 2). This computational strategy, although restricted to information contributions from a c ac -connected subsets containing up to two-collider paths, is shown to outperform state-of-the-art causal discovery methods on challenging benchmark datasets. 1 Introduction The likelihood function plays a central role in the selection of a graphical model \mathcal{G} based on observational data \mathcal{D} . Given N independent samples from \mathcal{D} , the likelihood {\mathcal{L_{D|G}}} that they might have been generated by the graphical model \mathcal{G} is given by [ 1 ] , \displaystyle{\mathcal{L_{D|G}}}={1\over Z_{\mathcal{D,G}}}\;{\exp\Big({-NH({p,q})}\Big)}\;\;\;\; (1) where H({p,q})=-\sum_{\bm{x}}p(\bm{x})\log q(\bm{x}) is the cross-entropy between the empirical probability distribution p(\bm{x}) of the observed data \mathcal{D} and the theoretical probability distribution q(\bm{x}) of the model \mathcal{G} and Z_{\mathcal{D,G}} a data- and model-dependent factor ensuring proper normalization condition for finite dataset. In short, Eq. 1 results from the asymptotic probability that the N independent samples, \bm{x}^{(1)},\cdots,\bm{x}^{(N)} , are drawn from the model distribution, q(\bm{x}) , i.e. {\mathcal{L_{D|G}}}\equiv q(\bm{x}^{(1)},\cdots,\bm{x}^{(N)})=\prod_{i}q(\bm{x}^{(i)}) , rather than the empirical distribution, p(\bm{x}) . This leads to, \log{\mathcal{L_{D|G}}}=\sum_{i}\!\log q(\bm{x}^{(i)}) , which converges towards N\sum_{\bm{x}}p(\bm{x})\log q(\bm{x})=-N\,H({p,q}) in the large sample size limit, N\to\infty , with \log Z_{\mathcal{D,G}}={\mathcal{O}}(\log N) . The structural constraints of the model \mathcal{G} translate into the factorization form of the theoretical probability distribution, q(\bm{x}) [ 2 , 3 , 4 , 5 , 6 ] . In particular, the probability distribution of Bayesian networks (BN) factorizes in terms of conditional probabilities of each variable given its parents, as q_{{}_{\rm\tiny BN}}(\bm{x})=\prod_{i}q(x_{i}|\mathbf{pa}_{X_{i}}) , where \mathbf{pa}_{X_{i}} denote the values of the parents of node X_{i} in \mathcal{G} , \mathbf{Pa}_{X_{i}} . For Bayesian networks, the factors of the model distribution, q(x_{i}|\mathbf{pa}_{X_{i}}) , can be directly estimated with the empirical conditional probabilities of each node given its parents as, q(x_{i}|\mathbf{pa}_{X_{i}})\equiv p(x_{i}|\mathbf{pa}_{X_{i}}) , leading to the well known estimation of the likelihood function in terms of conditional entropies H(X_{i}|\mathbf{Pa}_{X_{i}})=-\sum_{\bm{x}}p(x_{i},\mathbf{pa}_{X_{i}})\log p(x_{i}|\mathbf{pa}_{X_{i}}) , {\mathcal{L}_{\mathcal{D|G}_{\rm\tiny BN}}}\!={1\over Z_{\mathcal{D,G}_{{}_{\rm\tiny BN}}}}\;{\exp{\Big(\!-N\!\!\!\sum_{X_{i}\in\bm{V}}^{\rm vertices}\!\!\!H(X_{i}|\mathbf{Pa}_{X_{i}})\Big)}} (2) This paper concerns the experimental setting for which some variables of the underlying Bayesian model are not observed. This frequently occurs in practice for many applications. We derive an explicit likelihood function for the class of ancestral graphs, which include directed as well as bidirected edges, arising from the presence of unobserved latent variables. Tian and Pearl 2002 [ 7 ] showed that the probability distribution of such graphs factorizes into c-components including subsets of variables connected through bidirected paths ( i.e. containing only bidirected edges). Richardson 2009 [ 6 ] later proposed a refined factorization of the model distribution of the broader class of acyclic directed mixed graphs in terms of conditional probabilities over “head” and “tail” subsets of variables within each ancestrally closed subsets of vertices. However, unlike with Bayesian networks, the contributions of c-components or head-and-tail factors to the likelihood function cannot simply be estimated in terms of empirical distribution p(\bm{x}) , as shown below. This leaves the likelihood function of ancestral graphs difficult to estimate from empirical data, in general, although iterative methods have been developped when the data is normally distributed [ 8 , 9 , 10 , 11 , 12 , 13 ] . The present paper provides an explicit decomposition of the likelihood function of ancestral graphs in terms of multivariate cross-information over relevant ‘ ac -connected’ subsets of variables, Figs. 1 ., which do not rely on the head-and-tail factorization but coincide with the parametrizing sets [ 14 ] derived from the head-and-tail factorization. It suggests a natural estimation of these revelant contributions to the likelihood function in terms of empirical distribution p(\bm{x}) . This result extends the likelihood expression of Bayesian Networks (Eq. 2 ) to include the effect of unobserved latent variables and enables the implementation of a greedy search-and-score algorithm for ancestral graphs. For computational efficiency, the proposed two-step algorithm relies on local information scores limited to the close surrounding vertices of each node (step 1) and edge (step 2). This computational strategy is shown to outperform state-of-the-art causal discovery methods on challenging benchmark datasets. 2 Theoretical results 2.1 Multivariate cross-entropy and cross-information The theoretical result of the paper (Theorem 1) is expressed in terms of multivariate cross-information derived from multivariate cross-entropies through the Inclusion-Exclusion Principle. The same expressions can be written between multivariate information and multivariate entropies by simply substituting q(\{x_{i}\}) with p(\{x_{i}\}) in the equations below and will be used to estimate the likelihood function of ancestral graphs (Proposition 3). As recalled above, the cross-entropy between m variables, \bm{V}=\{X_{1},\cdots,X_{m}\} , is defined as, \displaystyle H(\bm{V})\!\!\! \displaystyle= \displaystyle\!\!\!-\!\sum_{\{x_{i}\}}p(x_{1},\cdots,x_{m})\log{{q(x_{1},\cdots,x_{m})\;\;\;\;\;\;}} (3) where p(\{x_{i}\}) is the empirical joint probability distribution of the variables \{X_{i}\} and q(\{x_{i}\}) the joint probability distribution of the model. Bayes formula, q(\{x_{i}\},\{y_{j}\})=q(\{x_{i}\}|\{y_{j}\})\;q(\{y_{j}\}) , directly translates into the definition of conditional cross-entropy through the decomposition, H(\{X_{i}\},\{Y_{j}\})=H(\{X_{i}\}|\{Y_{j}\})+H(\{Y_{j}\}) (4) Multivariate (cross) information, I(\bm{V})\equiv I(X_{1};\cdots;X_{m}) , are defined from multivariate (cross) entropies through Inclusion-Exclusion formulas over all subsets of variables [ 15 , 16 , 17 , 18 ] as, \displaystyle I(X) \displaystyle= \displaystyle H(X) \displaystyle I(X;Y) \displaystyle= \displaystyle H(X)+H(Y)-H(X,Y) \displaystyle I(X;Y;Z) \displaystyle= \displaystyle H(X)+H(Y)+H(Z)-\!H(X,Y)-\!H(X,Z)-\!H(Y,Z)+\!H(X,Y,Z) \displaystyle I(\bm{V}) \displaystyle= \displaystyle-\sum_{\bm{S}\subseteq\bm{V}}(-1)^{|\bm{S}|}H(\bm{S}) (5) where the semicolon separators are needed to distinguish multipoint (cross) information from joint variables as \{X,Z\} in I(\{X,Z\};Y)=I(X;Y)+I(Z;Y)-I(X;Y;Z) . Below, implicit separators between non-conditioning variables in multivariate (cross) information will always correspond to semicolons, e.g. as in I(\bm{V}) in Eq. 5 . Unlike multivariate (cross) entropies, which are always positive, H(X_{1},\cdots,X_{k})\geqslant 0 , multivariate (cross) information, I(X_{1};\cdots;X_{k}) , can be positive or negative for k\geqslant 3 , while they remain always positive for k<3 , i.e. I(X;Y)\geqslant 0 and I(X)\geqslant 0 . In turn, multivariate (cross) entropies can be expressed through the Principle of Inclusion-Exclusion into the same expression form but in terms of multivariate (cross) information, \displaystyle H(\bm{V}) \displaystyle= \displaystyle-\sum_{\bm{S}\subseteq\bm{V}}(-1)^{|\bm{S}|}I(\bm{S}), (6) Conditional multivariate (cross) information I(\bm{V}|Z) are defined similarly as multivariate (cross) information I(\bm{V}) but in terms of conditional (cross) entropies as, \displaystyle I(\bm{V}|Z) \displaystyle= \displaystyle-\sum_{\bm{S}\subseteq\bm{V}}(-1)^{|\bm{S}|}H(\bm{S}|Z) (7) Eqs. 5 & 7 lead to a decomposition rule relative to a variable Z , Eq. 8 , which can be conditioned on a set of joint variables, \bm{A}=\{A_{1},\cdots,A_{m}\} , with implicit comma separators for conditioning variables in Eq. 9 , \displaystyle I(\bm{V}) \displaystyle\!\!\!=\!\!\! \displaystyle I(\bm{V}|Z)+I(\bm{V};Z) (8) \displaystyle I(\bm{V}|\bm{A}) \displaystyle\!\!\!=\!\!\! \displaystyle I(\bm{V}|Z,\bm{A})+I(\bm{V};Z|\bm{A})\;\;\;\; (9) Alternatively, conditional (cross) information, such as I(X;Y|\bm{A}) , can be expressed in terms of non-conditional (cross) entropies using Eq. 4 , \displaystyle I(X;Y|\bm{A}) \displaystyle\!\!\!=\!\!\! \displaystyle H(X|\bm{A})+H(Y|\bm{A})-H(X,Y|\bm{A}) (10) \displaystyle\!\!\!=\!\!\! \displaystyle H(X,\bm{A})+H(Y,\bm{A})-H(X,Y,\bm{A})-H(\bm{A}) which can in turn be expressed in terms of non-conditional (cross) information as, \displaystyle I(X;Y|\bm{A})\!\!\!\! \displaystyle= \displaystyle\!\!\!\!I(X;Y)-\cdots(-1)^{k}\!\!\!\!\!\sum_{{i_{1}}<\cdots<{i_{k}}}\!\!\!\!I(X;Y;A_{i_{1}};\cdots\!;A_{i_{k}})+\cdots(-1)^{m}I(X;Y;A_{1};\cdots\!;A_{m}) (11) \displaystyle= \displaystyle\!\!\!\!\sum_{\bm{S^{\prime}}\subseteq\bm{S}}^{X,Y\in\bm{S^{\prime}}}(-1)^{|\bm{S^{\prime}}|}I(\bm{S^{\prime}}), where \bm{S}=\{X,Y\}\cup\bm{A} . This corresponds, up to an opposite sign, to all (cross) information terms including both X and Y in