Structure learning

[felixleopoldo]

Since the tree structure is known (?) given the causal ordering, structure learning should be a matted of finding a stages/contexts and causal ordering (as Liam said) of the nodes.

1. How is the structure learning implemented currently? I think Liam said that there is a naive algorithm somewhere..

[Alex-Markham]

I think the current implementation is in the R code Liam mentioned. And I think he'd like if we can develop a GES-style algorithm (probably working on the minimal context DAGs, but we'd at least theoretically need to also figure out how it looks for the actual CStree), which is why I've been thinking about a transformational characterization of Markov equivalence for CStrees.

[felixleopoldo]

Alright, could you expand a bit what you mean by transformational characterization of Markov equivalence for CStrees.?

[felixleopoldo]

I guess its related to this.

[Alex-Markham]

Extending the existing characterization for Markov equivalent DAGs (Theorem 2 https://arxiv.org/pdf/1302.4938v1.pdf) to CStrees, which will eventually allow us to extend GES (http://www.ai.mit.edu/projects/jmlr/papers/volume3/chickering02b/chickering02b.pdf) to CStrees. The transformational characterization gives us a way of efficiently moving around the space of CStrees so we that we can, e.g., do greedy search

[felixleopoldo]

It is possible to integrate out the parameters for the likelihood of a CStree, to get the marginal "CStree likelihood" as with marginal graph likelihood? It would maybe be a collection of marginal likelihoods, one for each context DAG.

[felixleopoldo]

People use to put constraints on the number of parents/node, for example, max of 2 parents for each node. How is that expressed in a CStree.

[Alex-Markham]

For learning a CStree, we could consider first doing some multi-dimensional clustering of the samples to get different (maybe not minimal) contexts. Then we could do normal DAG structure learning on each cluster to get the corresponding context graph. This would also enable constraint based approaches (as opposed to the GES-style approach we've discussed)

[Alex-Markham]

But this also doesn't necessitate a constraint-based approach. For example, we could use continuous optimization techniques like NOTEARS to learn the context DAGs, and we may even be able to combine the clustering (context learning) with the DAG structure learning into one algorithm/optimization function

[felixleopoldo]

Alrighh, sounds like a good idea to divide the problem. How would the clustering be? I mean since a context is defined by some variables being a fixed value, like XY=xy. Would the clustering be to find such variable settings in the data?

[Alex-Markham]

Yeah, exactly. I'll dig more into it at some point, but the idea came from discussing it with Lukas, the first author of this paper: https://ojs.aaai.org/index.php/AAAI/article/view/5961
The point would be to find/define a clustering objective that "automatically" finds the kind of clusters/contexts we want