Scientist Stories: Kyra Gan, Causal Discovery in Medical Data

Dr. Kira Gann, an assistant professor of operations research and information engineering at Cornell Tech. Prior to joining Cornell, she was a postdoctoral fellow in the Department of Statistics at Harvard University working with Dr. Susan Murphy. She obtained her degree in operations research from the Tepper School of Business at Carnegie Mellon University, and her interests include adaptive online algorithm design, robust and efficient inference in possible scenarios. Right, so let's pivot the topic a little bit to non-neural network-related areas. So can I just get a sense how many people know about causal inference? Okay, that's great. Okay, so I'll probably quickly go through some things. So we all know that association does not equal causation, right? What does that mean in prediction problems is that oftentimes, right, in medical applications, we see zip code is a predictive feature, for example, for the 30-day hospital readmission rate. However, zip code does not cause the person to get readmitted, meaning that if I just artificially relocate the person to somewhere else, they still have this likelihood of getting readmitted in 30 days. So an alternative explanation is that default is a proxy for the socioeconomic status of the patient, and that's the underlying reason why the person is getting admitted. So now there is really big emphasis of thinking about causality and what's the cause of a particular disease in the domain of health and that's what I work on. So I usually work with small data regimes, both in experimental studies and also observational studies. So what is causal inference in observational studies, right? So here we're interested in estimating the effect of a treatment on a potential outcome, right? For example, a disease. To give you an example of this is that For example, I would like to know what's the treatment effect of a particular drug for treating colds. Say I have a cold, how do I estimate this treatment effect? In an ideal world, I would look at the difference when I take the pill versus I don't take the pill at the same time. So causal inference is precisely hard because you don't observe those two quantities at the same time. So how do people do this? So we, in general, when I talk about causal inference in this talk, you should think about this as the average treatment effect across the entire population, right? So how do we do this? Causal inference fundamentally breaks down into two parts. First part is we need to identify the causal model of interest, and the second part is then perform the inference based on the model that we have, right? So what do I mean by identify the causal model of interest? What are the methods that people have been using historically for identifying this mostly falls into the two categories, right? So the first category of model inference approach assumes an underlying graphical model of my data generating process. You'll probably see some causal DAGs when you read a causal inference paper. That's the data generating distribution they assume. Once you have assumed this causal structure, you can now write down what treatment effect is as a function of the data generating process. So this is a semi-parametric approach. Then I'm going to empirically estimate what this data generating distribution is from the data and plug into my expression for the target parameter and obtain an estimate. So this whole line of literature in inference really focuses on the second part. When I do the plugin estimation, how do I debias the— how do I make sure that my plugin estimate has asymptotically nice behavior? And I want to highlight that recently we have a paper on this topic which automatically biases the plugin estimation without manual derivation. If you're interested, please check it out. So another set of methods that are more common, or like you are probably more familiar with in causal inference, is basically I'm going to assume the underlying causal model is linear, right? For example, I assume T alpha is a linear function of the treatment and some covariates, and I assume additive effects. So once I have this, I can apply the inverse propensity weights for a regression with robust estimation. Obtain the proper estimates. So those are two different approaches. So where does causal discovery kicks in in this picture, right? Where does causal discovery help? It's for the identification of the graphical model. So I really think about the power of causal discovery in the context of inference really since the first approach where we can actually learn what's the underlying data generation process on the data with minimal assumptions. So here I'm not going to make any assumptions on the data generating mechanism. So how familiar people are with graphic models? Very good. Okay, okay, let's again quickly go through what graphic models are, right? Again, we like to think about graphical models as a tool to model the data generation process, right? You see all those graphs are directed acyclic graphs, meaning that the edges do not form a cycle. So just to highlight that in the probabilistic model for Bayesian network setting, we like to call the cause of another variable as the parent. And the ancestor as the child. And we also like to call the child of the child of the descendant of the ancestor. So those are the standard terminologies. So why can graphical models model or represent the data gathering process? It relies on a few assumptions. Just to refresh your mind on the set of assumptions needed, The first assumption is the Markov assumption, which states that given the parents of a node in a DAG, right, if you recall, in the previous node, meaning like if you look at the B node, the parent of B is A here, right? So what this Markov assumption says is given the parents of X node X in the DAG, This node is independent of all its non-descendants, meaning if A has another parent right in the previous graph, then B would have to be independent of the parent. So what's the consequence of this Markov assumption? It enables the factorization of the data generating process based on the graphical model. So now I can look at a graphical model and I can write down what's the mechanism just by looking at it, right? The way it goes is I look at each individual node in my dataset, and the entire joint distribution is characterized by the product of the conditional distribution of each node on its parents. Now, what's the second assumption that we need for representing the data that we can process is the minimality assumption, which says, see a graphic model, if two nodes are adjacent to each other, then this has to mean that x is dependent on y. Okay, just to formalize what's the picture that you have in mind is that first, they have marked the subject in a graphic model. This establishes the typical independence between the variables. And once I have the minimality assumption, this establishes the statistical dependency between the variables. Okay, so what does this have to do— anything to do with causality? Okay, so the way that we're able to tie this model to a causal model is by giving the meaning of those edges. So here we're going to say a directed graph, every parent is a direct cause of all its children. So now with this causal edge assumption, we establish causal dependency, right? So the DAG is no longer just describing the data generating process, we're describing the cause of one variable to another. What is causal discovery trying to do? The causal discovery trying to learn this data-generated process has the causal meaning from the data itself. So we're going to use a data-driven way to infer the underlying causal structure from datasets with minimal assumptions. So how do we do that? It relies on the following building block. We are going to look at the basic structures in graphical models and look at what are the statistical independencies does that structure imply. And in the end, we're going to use the set of statistical independencies to learn the underlying probabilistic design. So here in the graphical models, So in two nodes, right, the scenarios are very simple. We have two nodes, one relationship, one possible relationship is those two nodes does not have the relationship with each other, or one causes the other. So nothing special about this. So people like to talk about the most basic building blocks in graphical models as the following three node types, okay? We are now trying to enumerate all the possible relationships that three different variables can have. From the theoretical perspective. So the first one that we're going to focus on is what we call the chain. What does that mean? It's that X1 causes X2 and causes X3. If you are familiar with causal inference, what we call this node X2 is a mediator. And so mediator is defined with a pair of variables X1 and X3. So why are we calling it a mediator? If the effect of X1 on X3 is fully mediated through X2, meaning that if I intervene on this node X2, X1 now cannot affect X3 in excess, right? So just by this definition, what do we see is that if I don't do anything, X1 is statistically dependent with X3 because they're causal derivatives. And now what's the condition on the middle node x2? I have statistical independencies between those two variables x1 and x3. And you can actually check the correctness of the statistical independencies purely from the Bayesian factorization. Okay, so that's something that's very easy to do. Now what is the second structure? It's called a fork, meaning that my variable x2 now causes both the variable x1 and also causes the variable x3. So it's called a— so x2 is called a confounder between the pair of variables x1 and x3. So intuitively, because x2 is the common cause, it's also going to satisfy the first relationship, right? x1 is statistically dependent with respect to x3. And once I control for the common cause, those two will become statistically independent. So the fork and chain shares the same statistical dependence. So what is special in this building block, right? The asymmetry actually happens when you have the full V structure, meaning that— or in the graphical model language, people sometimes like to call it a V-monology, kind of a model, if you could say. So basically, X1 is the cause of my, you know, X2, and X3 is also the cause of X2. And here's an example, right? Intuitively, let's understand what are the statistical dependencies implied by this graphic model. So say that X2 is traffic. I want to know whether I'm going to run into traffic today. What is the cause of traffic? Whether today is a holiday. The second factor that causes traffic is the hour of the day, right? So if you look at quality and hour of the day, of course they are statistically independent of each other. There's nothing— those two variables have nothing to do with each other. So you have the first condition that X1 is independent of X3. Now, once I control for the traffic, say given at the moment I don't have traffic, what does it imply? Implies it cannot be a holiday and it cannot be a rush hour. So now when I condition on the node X2, I get statistical dependence, right? So I have this conditional dependence between X1 and X3 when conditioned on X2. Okay, so those are the three basic structures, and again, this node X2 here is called a collider. Things get a little bit more interesting. You thought maybe that's all we're going to cover in this case. Okay, so there's one more thing. A graphical model. So funny thing here, so we have a warning condition on the descent of the collider. Okay, you would expect, oh, this is the descent of the collider, it doesn't take a flat, right, the 3-node structure here. So conditionalness still should not change the original independence relationship inferred by those three both sides. However, that is not true, okay? Because x4 is a descendant of the cluster, if I control for this variable, it's actually going to affect the variables that x2 can predict, right? So for example, what's an example of x4 is whether you're late to work. Right? Whether you're late to work isn't because of traffic. So I know that if I am late to work, that's by conditioning on X4. What does that imply? That implies there is traffic. There, with high probability, there is traffic, right? So by conditioning on X4, you're kind of implicitly conditioning on this variable X2. So you get the following condition that X1 and X3 actually become independent with each other, even if you condition on the D sequence of the probability. So that finished all the fundamental pieces of graphical model belief box. What we are going to talk about next is the deseparation, and that's the rule that's going to enable us to learn the graphical model from the data. So what is the path, right? If you look at the model that we saw previously, um, here, right, a path is any combination of the edges that are connected to each other. Now I say that a path between a pair of variables x_i is blocked by S_m^p if and only if the following condition holds, right? One of the following conditions holds. What does it mean by blocked? Simply means that I have conditional independencies between the nodes x_i. How do I do that? Is that if the set of near copies along the path there's either a chain or a fork around this variable w, where then w is inside this condition that 9 seconds have elapsed, right? So going back to the previous example, here we, with respect to x1, x2, x1, x4, x2 is a chain, right? It's on the chain. So how do I block the path between x1 and x4? I condition on x2. So that's what the first condition says. What is the second condition? It's that if naturally w is a collider on the path and it's not conditioned on it in the variable set z, and none of its descendants is conditioned on this set, then I also block this path. Okay, what's that natural example? Um, here is that the path from x1 to x3, but I can travel from x1 to x2 to x3, but x3 is not a condition point, then this path is blocked. Okay, so that is the definition of a blocked path. Any questions? Now, what is D-separation? D-separation simply says that two nodes, two variables X and Y, are D-separated by a set of variables D if all the paths between those two variables are blocked. By max set Z. Okay, so that's simply the definition of G-separation. And let's see an example. So I want to, for example, in the following graph, I would like to find a set that G-separates the variable T and Y. Cover the graph. Anyone wants to try? Right, what does this separation mean when I have the full graphical structure? I want t to be statistically independent of y. So I need to first find all the active paths that are currently inside my graph, right? So here is a valid path that's open because 7, 2 is a component and nothing's being conditioned on for this path. So as long as I condition on any one of the w1, w2, w3, this path is blocked. So I need one of, at least one of those three nodes to be even, conditioning is done. I have another path from t to y through the mediations m1, m2, right? Without conditioning on anything, I can, t1 is finished for me, parents. With respect to y along this path. So I need at least one of m1 and m2 to be in my prediction set. How about the last one? x2 is a collider for t and y. So naturally, this— if you don't do anything, this path is blocked because naturally, if you only look at this path, those nodes are statistically independent. With each other. If you have some condition on x2, then you have some condition on additional nodes, either x1 or x3. Okay, so if you condition on both x1 and x2, it will still block the entire graph. Okay, so that's the separation where we find the set of variables that actually meets that critical 2-node, the T of 1. Yeah. Yeah, I know. So cutting graph is different because cutting graph does not talk about orientation between the edges. For example, here, right? If you are talking about cutting a graph, maybe you just cut here because the orientation does not matter. It's not tied to statistical dependency or independencies. But if you now thinking about what each structure corresponds to in terms of statistical dependencies that you would observe on the data, then this would mean that you either don't do anything or you have to block two nodes. So that's the difference. Any other questions? Okay. So what does this have to do with puzzle discovery? So this is the— this approach is really the building block of those kind of constraint-based puzzle discovery methods where the goal is to perform a sequence of statistical independence tests to detect what is the underlying puzzle structure. I will give you an example of the very common PC algorithm that people use in the puzzle discovery literature. Diagnose the fact that that would be self-imposed. So one more assumption that we need for discovering the causal structure from the data is the faithfulness assumption. Okay, so what does this assumption say? It says, given a probability distribution over variables, the faithful assumption asserts that statistical independence relationships observed in the data basically reflect the absence of certain direct causal effects among other variables. In short, you can think about the following picture. The Markov assumption in the causal discovery literature really established the relationship from causal graphs to data. Now, how do I learn from data? I need to assume whatever I observe from the data truthfully reflects the underlying data generating process. So that's what faithfulness is assuming under the hood. Two more assumptions that we usually need is first, the graph is acyclic, meaning there's no cycles, right? If you think about causes, if I have a circle that goes on and on, how do I distinguish the effect of both variables? There's an effect, right? And the last assumption that we commonly meet in the causal discovery literature is causal sufficiency condition. What does it mean is that my variable contains all sufficient information that enables me to learn the underlying data generating distribution, right? This simply means there's no unobserved confounders in my dataset, if you know what that means. I want to highlight that the algorithm that we proposed does not rely on this causal sufficiency condition, but for the classical PC algorithm, this is required. So let's Talk about what we're talking about, about Markov equivalence, and we'll use sketch of what PC algorithm is and give an example how you would run PC algorithm on datasets. So we see from the previous examples that the chains and the fork structure encode the same statistical dependencies, right? If you read the graph and kind of parts of all the conditional independence kind of implied by each one of the structures, you will get a whole set of conditional independence, and they're the same among all the structures. So we call the resulting graphs that share the same causal independencies as they're in the same Markov equivalence class, because at that point, no statistical independencies can distinguish between those models. Using independence tests. I want to highlight there are more basic methods that can potentially distinguish between those structures, but that's beyond the scope of this one. Now, what's so special again is about this V structure. It really is the key observation, or key kind of observation, why of the descriptive words. So again, these structures share a very unique statistical independence among the structures. And you can see for these structures, the model is the simplest class. I cannot come up with another set of variables, so you know, kind of structure that shares the same statistical independence as the structure. So this really kind of hinges on how a causal discovery algorithm can be potentially kind of sketched out. Among the variables that are marginally equivalent, we can observe that they actually share the same skeleton of the causal structure, meaning that if I remove the orientation between the variables, they actually share the same overall structure. Okay, and now if I give you this graph, how do I know that this graph is different from this class of variables? You will see that the additional graph actually has the kind of different statistical independence as a Markov regular class here. Okay, so that's the key underlying observation is that if two graph frames share different skeletons, then they have a different set of statistical independencies and dependencies associated with them. And that's the key insight. How do you learn what's the structure of the underlying graph? Okay, so again, two things that we are going to 2 quantities that we're going to rely on in learning the causal graphs. The first one is the V-structure, and the second one is the skeleton. And the causal graph model, graphical learning model, simply first trying to learn what the skeleton of the underlying data mechanism and trying to orient the rest of the edges. So there's a theorem, um, already many say that two graphs are Markov equivalent if and only if they have the same skeleton, have the same leaf structures. So here's the sketch of the common PC algorithm, right? So here's the graph algorithm, right? Probably that. How do I start? I start with a complete undirected graph, and what I'm going to do next, I'm going to search, you know, whether I achieve statistical independence between A and B by conditioning on a subset of nodes. Once such a node exists, I know I can remove this particular edge. Okay, so I'm going to do this step iteratively until I'm kind of left with the skeleton, right, of the underlying homograph. Then I'm going to identify what is the B structure because it has— it satisfies a different statistical dependence test. I'm going to use that to orientate the edges, the V structures in the graph. The last step is simply to orientate the rest of the graphs, the rest of the edges that are adjacent to the V structure, right? Because in the previous step, I already identified I have only one V structure here. I know this cannot be a V structure, so there's only one natural way that I can orient that there. Now, what's the problem with this approach? As many of you might already know, that this is not computationally tractable, right? To search for the number, kind of this number, the conditioning set that separates those two nodes. In worst case, you need to condition on the rest of the nodes iteratively, right? So the worst case time complexity for searching the skeleton itself is exponential in the number of variables that I have in my dataset. So that's one of the main reasons. The second reason is that it requires a lot of samples, right? How many samples do I need to estimate a conditional probability law? That sample size grows exponentially in the number of variables I'm conditioning on. So that's the intuition why probabilistic modeling requires a lot of samples. And the last thing that I want to highlight is that if in the end my method returns a Markov equivalence class, right, I don't know whether this is mediator or it's a confounder. That's actually problematic in my downstream inference task because I don't know which node to condition. Okay, so just to give you an example where causal PPL would have failed, Here is the raw truth data that we generated. It's only 10 of that. 10 of that. Okay. So for this 10 of that, we tried 10,000 samples on PC, and you can see even with 10,000 samples, PC does not return the correct results. And similarly, there's a version of global discovery algorithm out there that does not rely on the causal sufficiency assumption, meaning some variables can be missing in the underlying data generation process. So again, here's an experiment where we have access to the underlying true model and we start iteratively dropping some nodes. And you can see PT algorithm, even with 50,000 samples, it does not return meaningful outputs. So really, this really prompts us to design a new discovery algorithm that is tailored towards the downstream input task. If you think about, I still want a global discovery algorithm, where can we cut corners? Probably nowhere, right? And those are the necessary steps for me to get the entire photo structure. Now, if I care about inference, I only need to estimate what treatment effects are, and I don't need to learn the entire graph. I only need to find the variables in my dataset that are relevant for my causal estimation in the downstream inference task. Okay? In other words, we are going to use this notion of a variative adjustment set in the causal inference literature So what does this valid adjustment set mean? Simply, it blocks all the non-causal paths between my exposure and outcome variables. And if I know this set of variables, it is guaranteed that I can get the correct causal estimates. All right, so the problem here is really designing a causal discovery algorithm to discover the set of valid adjustment sets. And just to give you a more concrete example, what do I mean by non-causal association? Is that if you have a confounder, then the flow from the treatment to the outcome through the confounder is a non-causal association because that flow is created by a— if I have a mediation, this is a causal association. So I don't want to block Okay, if I have a quiet attack, I just don't want to do anything on it because if I naturally don't do anything on it, it's wrong, right? I don't infer conditional spurious association between the two. So let me just give you the high-level idea what we're proposing in this local summary random partitioning approach. Is that we actually observe by a very simple observation that I will show you in the next slide that the variables can actually be defined relative to the exposure and outcome. So I can define what a variable is simply using its relative position to the exposure and outcome, and then have 8 such partitions. Okay, so we come up with a independence task-based method that performs this weak partition, we first show that the taxonomy of weak partitions is exhaustive and mutually exclusive. Then we propose a new algorithm to learn the partitions. So there is no skeleton learning, no edge orientation involved at all. The end goal is simply to identify what are the set of variables in the value adjustment sense. One more thing I want to highlight is this method is actually robust to cover insufficiency, meaning in some part of the structure, if there is an observable fault under, this method is going to work fine. So the simple intuition that you would observe here, x is my exposure variable, y is the outcome variable of interest. Now I can kind of enumerate all the possible relationships that the third node can have with respect to the exposure and the outcome. And those are the 8 building blocks of the algorithm. Simply, we want to distinguish between those structures. And you see our algorithm iteratively trying to identify what each category of the variables are. I'm going to skip the theoretical results of the work. You can look it up in the paper, and I want to talk about the performance. Okay, so what's the result of this local partitioning approach? It starts with gaining time efficiency. So instead of having worst-case exponential runtime complexity, here our worst-case runtime is quadratic to the number of variables, and you can see beside the noise, right? Empirically, you can see this is the performance, this number of tests performed by the TCL algorithm, this number of tests performed by LPP on a local benchmark. And similarly, by the fact that we're conditioning on less variables, we have each iteration of gains and coefficients. So now we're able to learn the correct silent adjustment set with less samples than the traditional PC or global discovery algorithms. And the last one is the plausibility. Because LDP is our local discovery by partitioning approach based on conditional independence tests, and those tests can be nonparametric, so we don't really need to assume any kind of causal structure of the underlying model to discover the validity. All right. Quickly, right, I claim that this is the method that we developed for inference. So how well does it do for inference? So the first graph, for the first set of columns of figures, really illustrates the performance of several different algorithms on the identification of valid adjustment sets. You do observe that about the best performance on the both kind of their both ways of, well, combining or identifying valid adjustment sets. Second figure is the bias, or I think it's what's the true value of the average treatment effect. So the dashed red line here overlaps the dollar estimate. We can see our estimate is unbiased. And for the last figure with the variance of the resulting estimate, you can also see that the most receiver has the worst variance, simply because the bad adjustment set is much smaller than the ones identified by the others. Okay, so that concludes what I want to cover. Thanks. Is it still enough for us to apply this method on large scale? That is unclear, right? I mean, it's a huge improvement, but I think there's a lot more room that are left that you can potentially reduce the type of the sample complexity. So I think people— one big challenge being causal inference in observational studies. Is the identification of the valid adjustment set. Without that, we're going to make strong assumptions. So I think, I mean, I would encourage the community to try this method and let us know what is not working.