Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
58,563 characters · 19 sections · 24 citation commands
Leveraging Causal Graphs for Blocking in Randomized Experiments
Studying the causal effect of some variable(s) on the other variable(s) is of common interest in social sciences, computer science, and statistics. However, a mistake that people usually make is confusing the causal effect with an associational effect. For instance, if high levels of bad cholesterol and the presence of heart disease are observed at the same time, it does not mean that the heart disease is caused by high levels of bad cholesterol. The question is then how do we get to know if one variable causes the other? If the answer is yes, then what is the direction (positive or negative) and what is the magnitude, of the causal effect? fisher1926arrangement provided the framework of randomized experiments to study the causal effect, where the variable whose causal effect is to be studied (known as treatment or cause), is randomized over the available experimental units (like humans, rats, agricultural plots, etc.) and changes in the variable on which the causal effect is to be studied (known as response or effect), are recorded. A statistical comparison of values of the response with or without the treatment can therefore be done to study the existence, direction, and magnitude of the cause-effect relationship of interest.
Randomized experiments work on three basic principles, viz., randomization, replication, and local control fisher1926arrangement. Randomization states that the assignment of the treatment has to be random, and replication states the treatment should be given to multiple but homogeneous units, i.e., there are multiple observations of the effect variable for both with and without the treatment. Therefore, as long as the available experimental units are homogeneous (for instance, the fertility of all the agricultural plots is the same, the responsiveness of all the humans is the same for the drug, etc.), then a `good' randomized experiment can be carried out using the first two principles, viz., randomization and replication, which gives rise to completely randomized design (CRD). However, when the available experimental units are not homogeneous, i.e., some attributes of experimental units (known as covariates) differ from each other, then the causal effect may get influenced by the covariates causing non-homogeneity (like fertility, responsiveness, etc). The remedy to this problem is the third principle of randomized experiments, i.e., local control (also known as blocking), which states to stratify the available experimental units based on that covariate(s) causing non-homogeneity, and then randomize the treatment within those strata to eliminate the effect of the covariates. These strata are called \textit{blocks}, and this third principle along with the first two gives rise to \textit{randomized block design} (RBD). Blocking tries to control/eliminate the variability in the response attributed through the covariates and leads to a more \textit{precise} estimation of the causal effect of interest. Precision is defined as the inverse of the variance of the estimate of the causal effect of interest.
In this paper, we focus on the problem of deciding which covariates to be used for forming the blocks while performing a randomized experiment. We consider a non-parametric setting and assume that we have access to the underlying causal structure pearl2009causality. We provide an efficient algorithm to obtain a stable set of covariates to be used to form blocks for a general semi-Markovian causal model. The term stable refers to the idea of finding and excluding the covariates that one should never use to create blocks. The notion and the method of achieving this stability are discussed in (ref).
Statistics literature yates1935complex, kempthorne1952design, kempthorne1955randomization, cochran1948experimental presents profound discussions on relative efficiency (ratio of the variances of causal effects) of RBD over CRD. It can be seen that in general, RBD is always more or at least as efficient as CRD. Therefore, the natural question is how do we do blocking in an intelligent manner such that maximum gain in precision can be attained? More specifically, we are interested in answering the following question. Can we decide which covariates to be used for forming blocks using the causal structure (diagram) of all the variables, viz., treatment, response, and covariates (observed and unobserved) provided the causal structure is given?
In the past, efforts have been made to address the problem of efficient adjustments in causal graphical models under static interventions henckel2019graphical, rotnitzky2020efficient and under dynamic interventions 10.1093/biomet/asab018. In contrast to these, we provide an efficient algorithm to obtain the set of covariates to be used for forming blocks for a general semi-Markovian causal model. citet{cinelli2020crash} provided a good discussion on good and bad controls for different causal graphs and emphasized the importance of good adjustments in causal estimation. Some other partially related works include kallus2018optimal which discusses the problem of experimental design in terms of variance reduction and describes the functional assumptions placed on the potential outcome by blocking, harshaw2019balancing which shows that discrepancy minimization (difference in means between treatment and control covariate groups) implicitly performs ridge regression and li2019rerandomization talks about re-randomization and regression adjustment.
In this paper, we focus on deciding what covariates should form the basis of forming blocks. However, a problem that follows our problem is, how to efficiently form blocks by grouping the experimental units which are close to each other based on the chosen covariates. moore2012multivariate,higgins2016improving focus on the latter problem.
In this paper, we formalize the problem of finding a stable set of covariates to be used to form blocks, that minimizes the variance of the causal effect estimates. We leverage the underlying causal graph and provide an efficient algorithm to obtain such a set for a general semi-Markovian causal model.
The rest of the paper is organized as follows. (ref) provides some background and formulates the problem of interest. (ref) discusses our methodology that includes motivating examples, key observations, important lemmas, main results, and the final algorithm. (ref) provide experimental evaluations, and (ref) concludes the paper and provides future directions.
In this section, we provide some background and formulate the problem of interest in this paper.
Let $\mathcal{V}$ be the set of observed random variables and $\mathcal{U}$ be the set of unobserved random variables. Let $\mathcal{G}$ be a directed acyclic graph that depicts the causal relationships among the random variables in $\mathcal{U}$ and $\mathcal{V}$. Formally, we are assuming that the probability distribution of the random variables in $\mathcal{U}$ and $\mathcal{V}$ factorizes according to $\mathcal{G}$ (the causal Markov condition geiger1990logic). Furthermore, we assume that no variables other than the ones that are $d$-separated pearl2009causality in $\mathcal{G}$ are independent, i.e. independence in the joint probability distribution of the random variables in $\mathcal{U}$ and $\mathcal{V}$ is encoded by the causal graph (the causal faithfulness condition meek1995strong).
We are interested in studying the causal effect of $X\in\mathcal{V}$ (treatment) on $Y\in\mathcal{V}$ (response). Studying the causal effect of $X$ on $Y$ means learning the (interventional) probability distribution, $\mathbb{P}(Y|do(X))$ pearl2009causality.
Consider a simple setting where $X$ is an indicator random variable defined as
and $Y$ is a real-valued random variable.
Let there be $n$ experimental units available to study the causal effect of $X$ on $Y$ by performing a randomized experiment. Let $\mathcal{Z}$ denote the set of covariates that vary across the experimental units.
We want to demonstrate the gain in precision due to blocking. Thus, we first ignore these covariates and perform a CRD as follows. We randomize $X$ over the available experimental units, i.e., randomly assign a unit to either have the treatment ($X=1$) or not ($X=0$) and then observe the response. Let $(X_i,Y_i)$ denote the treatment and response pair for the $i$th experimental unit. Define $I_x:=\{i:X_i=x\}$ and $n_x:=|I_x|$.
To demonstrate the gain in precision due to blocking, we focus on estimating $\mathbb{E}(Y|do(X))$. For simplicity, define $Y(x) := Y|do(X=x)$. For our simple setting, we have only two possibilities of that conditional expectation, viz. $\mathbb{E}(Y(1))$ and $\mathbb{E}(Y(0))$. Similar to heckman1992randomization, clements1994making, and heckman1995assessing, we define the effect of treatment (ET) or average treatment effect (ATE) in the population as
A natural non-parametric estimator of ${\mathbb{E}}\,(Y(x))$ is the corresponding sample average, given as
Therefore, we can estimate $\beta$ as
It can be shown that $\mathbb{E}(\hat{\beta}) = \beta$, i.e., $\hat{\beta}$ is unbiased for $\beta$. The variance of $\hat{\beta}$ is given as follows.
where $\beta(\mathcal{Z}):= {\mathbb{E}}\,(Y(1)|\mathcal{Z}) - {\mathbb{E}}\,(Y(0)|\mathcal{Z})$ is called the $\mathcal{Z}$-specific causal effect or conditional average treatment effect (CATE). For proofs of unbiasedness and variance of $\hat{\beta}$, refer to (ref).
We now perform an RBD as follows. We first stratify the experimental units such that units within each stratum (known as a block) are identical, i.e., the covariates in $\mathcal{Z}$ remain the same with a block. We next randomize $X$ over the experimental units within each block and then observe the response. Let $(X_i,Y_i,\mathcal{Z}_i)$ denote the treatment, response, and covariates triplet for the $i$th experimental unit. Define $I_{x,z}:=\{i:X_i=x,\mathcal{Z}_i = z\}$ and $n_{x,z}:=|I_{x,z}|$.
Following petersen2006estimation, ET defined in (ref) can be re-written as
A natural non-parametric estimator of ${\mathbb{E}}\,(Y(x)|\mathcal{Z})$ is the corresponding sample average, given as
Define $n_z:=n_{1,z} + n_{0,z}$. ${\mathbb{P}}\,(\mathcal{Z})$ can be estimated as
Therefore, we can estimate $\beta$ as
It can be shown that $\mathbb{E}(\hat{\beta}_\mathcal{Z}) = \beta$, i.e., $\hat{\beta}_\mathcal{Z}$ is unbiased for $\beta$. The variance of $\hat{\beta}_\mathcal{Z}$ is given as follows.
For proofs of unbiasedness and variance of $\hat{\beta}_\mathcal{Z}$, refer to (ref).
As $\hat{\mathbb{P}}(\mathcal{Z})$ is as an unbiased estimate of $\mathbb{P}(\mathcal{Z})$, $\sum_{\mathcal{Z}}\beta(\mathcal{Z})\hat{{\mathbb{P}}\,}(\mathcal{Z}) = \mathbb{E}_\mathcal{Z}(\beta(\mathcal{Z})) = \beta$. Hence, the second term on the right in (ref) is zero. By comparing (ref) and (ref), we observe that ${\textrm{Var}}\,(\hat{\beta}_\mathcal{Z}) \le {\textrm{Var}}\,(\hat{\beta})$, i.e., blocking improves the precision of the estimate of the population average causal effect.
We observed that in experimental studies under non-homogeneity of the experimental units, blocking improves the precision of causal effect estimation. However, the practical difficulty with blocking is that depending on the number of covariates and the number of distinct values (denoted as $v(\cdot)$) of each covariate, the number of blocks can be very large. For covariates in the set $\mathcal{Z}$, we need to form $\prod_{Z \in \mathcal{Z}}v(Z)$ different blocks. For example, if we want to study the effect of a drug on curing some heart disease where the subjects under consideration have the following attributes (which can potentially affect the effectiveness of the drug). Gender: Male and Female, i.e., $v(\text{Gender})=2$, Age: $<$25, 25-45, 45-65, $>$65, i.e., $v(\text{Age})=4$, Weight: Underweight, Normal, Overweight, Obese I, Obese II, i.e., $v(\text{Weight})=5$, Blood Pressure: Normal, Prehypertension, Hypertension I, Hypertension II, Hypertensive Crisis, i.e., $v(\text{Blood Pressure})=5$, and Bad Cholesterol: Optimal, Above Optimal, Borderline High, High, Very High, i.e., $v(\text{Bad Cholesterol})=5$. Thus, we need to form $2\times4\times5\times5\times5=1000$ blocks. Performing a randomized experiment with a large number of blocks can be very costly. Sometimes, it may not be feasible as the number of blocks can be larger than the number of subjects. This would cause some of the blocks to be empty. For instance, there may not be any male subjects under the age of 25 who are Obese II with a Hypertensive Crisis and Optimal Cholesterol level.
Other than the economic aspects and some blocks being empty, there are reasons why some variables should never be used for forming blocks. Refer to (ref) for details.
So far, we observed that blocking improves the precision of causal effect estimation. However, in situations when the number of blocks to be formed is very large, blocking becomes costly and/or infeasible. One possible way to reduce the number of blocks is to form blocks using some but not all covariates. But the question is which covariates should be preferred over others while forming blocks? One possible way is to select the (smallest) set of covariates that leads to maximum precision in causal effect estimation. In the context of estimating the effect of treatment in the population, $\beta$, (discussed in (ref)), it means finding the smallest set, $\mathcal{Z}$, that minimizes ${\textrm{Var}}\,(\hat{\beta}_\mathcal{Z})$.
We next formalize the problem of interest in this paper as follows. We are given a directed acyclic causal graph, $\mathcal{G}$, that depicts the causal relationships among some observed variables, $\mathcal{V}$, and unobserved variables, $\mathcal{U}$. We are interested in studying the causal effect of $X\in\mathcal{V}$ (treatment) on $Y\in\mathcal{V}$ (response) by performing a randomized block experiment. The set of observed covariates is $\mathcal{C}:=\mathcal{V} \backslash \{X,Y\}$.
Studying the causal effect of $X$ on $Y$ means learning the (interventional) probability distribution, $\mathbb{P}(Y|do(X))$. We can write $\mathbb{P}(Y=y|do(X=x))$ as
For estimating the above probability, we perform an RBD by forming blocks using covariates in $\mathcal{Z} \subseteq \mathcal{V} \backslash \{X,Y\}$, and similar to the estimation of ${\mathbb{E}}\,(Y|do(X))$, we define an estimate of $\mathbb{P}(Y=y|do(X=x))$ as
where $\hat{{\mathbb{P}}\,}(\cdot)$ are the sample relative frequencies.
It is desirable to select the $\mathcal{Z}$ such that ${\textrm{Var}}\,(\hat{{\mathbb{P}}\,}_\mathcal{Z}(Y=y|do(X=x)))$ is minimized, i.e., maximum gain in precision. For ease of notation, we define ${\textrm{Var}}\,(\hat{{\mathbb{P}}\,}_\mathcal{Z}(Y|do(X))):= {\textrm{Var}}\,(\hat{{\mathbb{P}}\,}_\mathcal{Z}(Y=y|do(X=x)))$.
In this section, we develop a methodology to find a solution to (ref). We first examine ${\textrm{Var}}\,(\hat{{\mathbb{P}}\,}_\mathcal{Z}(Y|do(X)))$ as a function of $\mathcal{Z}$ to obviate some edges and nodes from the causal graph, $\mathcal{G}$. We next discuss some motivating examples and make key observations that lead to several lemmas for our main result. In the end, we provide our main result and develop an efficient algorithm for solving (ref).
In (ref), our interest is to minimize ${\textrm{Var}}\,(\hat{{\mathbb{P}}\,}_\mathcal{Z}(Y|do(X)))$ as a function of $\mathcal{Z}\subseteq \mathcal{C}$. $\mathcal{Z}$ can affect ${\textrm{Var}}\,(\hat{{\mathbb{P}}\,}_\mathcal{Z}(Y|do(X)))$ through the causal relationships from $\mathcal{Z}$ to $Y$, and from $\mathcal{Z}$ to $X$. Note that, $X$ is the treatment on which we are performing the intervention, i.e., we set the levels/values of $X$. This is equivalent to saying that $X$ is no longer affected by the rest of the variables. Therefore, $\mathcal{Z}$ also cannot affect $X$ when an intervention is performed on $X$. Therefore, $\mathcal{Z}$ can affect ${\textrm{Var}}\,(\hat{{\mathbb{P}}\,}_\mathcal{Z}(Y|do(X)))$ only through the causal relationships from $\mathcal{Z}$ to $Y$. Therefore, a smallest subset of $\mathcal{C}$ that blocks all causal paths from $\mathcal{C}$ to $Y$ gives a solution to (ref).
Denote the subgraph of $\mathcal{G}$ where all edges coming into $X$ were deleted as $\mathcal{G}_{\widetilde{X}}$.
Following (ref), we restrict ourselves to the subgraph $\mathcal{G}_{\widetilde{X}}$. Following (ref), we further delete the covariates that do not have any causal paths to $Y$. Denote this new subgraph as $\mathcal{G}'_{\widetilde{X}}$ and $\mathcal{C}'=\mathcal{C}\backslash\mathcal{F}$. Therefore, a smallest subset of $\mathcal{C}$ that blocks all causal paths from $\mathcal{C}'$ to $Y$ in $\mathcal{G}'_{\widetilde{X}}$ gives a solution to (ref).
All causal graphs in (ref) represent $\mathcal{G}'_{\widetilde{X}}$. Denote the set of parents of $W$ in $\mathcal{G}'_{\widetilde{X}}$ as $\mathcal{P}(W)$.
Denote the set of ancestors (including itself) of $W$ in $\mathcal{G}'_{\widetilde{X}}$ as $\mathcal{A}(W)$. Denote the subgraph of $\mathcal{G}'_{\widetilde{X}}$ restricted to $\mathcal{A}(Y)$ as $\mathcal{G}'_{\widetilde{X},\mathcal{A}(Y)}$. Based on the insights from (ref), we write (ref).
We now combine the insights from (ref) to provide a solution to (ref).
(ref) provides a sufficient condition for a set $\mathcal{Z}$ to be a solution to (ref). We next provide a method to construct a set $\mathcal{Z}$ that satisfies this sufficient condition.
Let a path composed entirely of bi-directed edges be called a bi-directed path.
In (ref), we observed that due to the presence of latent structures involving $Y$, $\mathcal{P}(Y)$ was not sufficient to block all causal paths from $\mathcal{C}'$ to $Y$. However the parents of $c$-component of $Y$ in $\mathcal{G}'_{\widetilde{X},\mathcal{A}(Y)}$ would be sufficient for that purpose.
We next discuss some concerns with using $\mathcal{Z}^*$ (a solution to (ref)) as a blocking set. We provide a method to address those concerns.
Denote the post-treatment ancestors of the response while studying the causal effect $Y|do(X)$ as $\mathcal{M}(Y|do(X))$, and the set of descendants (including itself) of $W$ in $\mathcal{G}'_{\widetilde{X},\mathcal{A}(Y)}$ as $\mathcal{D}(W)$.
We next provide steps to obtain a stable solution to (ref) based on (ref). First, we reduce $\mathcal{G}$ to $\mathcal{G}'_{\widetilde{X},\mathcal{A}(Y)}$. Next, we obtain the set $\mathcal{Z} = \mathcal{P}(C_{Y,\mathcal{G}_{\widetilde{X},\mathcal{A}(Y)}})\backslash\{X\}$ which is the smallest set such that $Y \perp (\mathcal{A}(Y)\backslash \{X,Y\})\backslash\mathcal{Z}|\mathcal{Z}$ in $\mathcal{G}'_{\widetilde{X},\mathcal{A}(Y)}$. Finally, we drop $\mathcal{M}(Y|do(X))$ from $\mathcal{Z}$ to get a stable solution to (ref).
Denote the edge $W_1\rightarrow W_2$ as directed-edge$(W_1,W_2)$, a path consisting of directed edges from $W_1$ to $W_2$ as directed-path$(W_1,W_2)$, and a path consisting of all bi-directed edges from $W_1$ to $W_2$ as bi-directed-path$(W_1,W_2)$. Algorithm (ref) outlines the psuedocode of the proposed algorithm to obtain a stable solution to (ref).
We next show that (ref) is an efficient polynomial-time algorithm. Finding if there exists a path between any two nodes in a directed graph can be done using breath-first-search which has the worst-case time complexity of $O(|\mathcal{V}|^2)$. (ref) first reduces $\mathcal{G}$ to $\mathcal{G}'_{\widetilde{X},\mathcal{A}(Y)}$ which involves finding variables with edges going into $X$ taking $O(|\mathcal{V}|)$ steps, finding variables with no path into $Y$ taking $O(|\mathcal{V}|^3)$ steps, and finding all ancestors of $Y$ taking $O(|\mathcal{V}|^3)$ steps. (ref) next finds the $c$-component of $Y$ involves traversing all pairs of variables: $O(|\mathcal{V}|^2)$, and finding if there exists a bi-directed path between any pair of variables: $O(|\mathcal{V}|^2)$. Therefore, the total time at this step is $O(|\mathcal{V}|^4)$. Finally (ref) finds $\mathcal{M}(Y|do(X))$ which involves finding descendants of $X$ taking $O(|\mathcal{V}|^3)$ steps, and finding ancestors of $Y$ taking $O(|\mathcal{V}|^3)$ steps. Therefore, the time complexity of (ref) is $O(|\mathcal{V}|^4)$.
We demonstrate the implementation of (ref) to obtain a stable solution to (ref) for a general semi-Markovian causal graph, $\mathcal{G}$ given in (ref).
\if 0
\fi
We first obtain the graph $G_{An_{\widetilde{X}}(Y)}$. We next obtain the $c$-components (following (ref)) of $\mathcal{G}_{\widetilde{X},\mathcal{A}(Y)}$ are $\{X\}, \{\text{Alcohol}, \text{Anxiety}, Y, \text{Cholesterol}\}, \{\text{Food-Habits}\}, \{\text{Age}\}$, and the $c$-component of $Y$ is $\{\text{Alcohol},\text{Anxiety},Y,\text{Cholesterol}\}$. We next obtain the set of parents of the $c$-component of $Y$ as $\{X, \text{Alcohol}, \text{Cholesterol}, \text{Food-Habits}, \text{Age}, \text{Anxiety}\}$. The set $\mathcal{D}(X) \cap \mathcal{A}(Y)$ is $\{X,Y,\text{Anxiety},\text{Sleep-Quality}\}$. Finally, we obtain the final set as: $$(\{X, \text{Alcohol}, \text{Cholesterol}, \text{Food-Habits}, \text{Age}, \text{Anxiety}\}\backslash\{X\})\backslash(\{X,Y,\text{Anxiety},\text{Sleep-Quality}\}\backslash\{X,Y\})$$ $$= \{\text{Alcohol}, \text{Cholesterol}, \text{Food-Habits}, \text{Age}\}.$$
In this section, we provide experimental evaluations to compare our method with other choices of sets of covariates to create blocks. For the causal graph, $\mathcal{G}$ provided in (ref), we are interested in studying the causal effect of Drug ($X$) on Blood-Pressure ($Y$).
We considered a simple setting where all variables under consideration are binary variables taking values in \{0,1\}. We used a simple joint probability distribution that factorizes according to the given causal graph. We then performed simulated randomized experiments for different choices of sets of covariates to create blocks. The estimated causal effect and the variability in the response for different choices of blocking sets are provided in (ref). We observe that the variability in the response is the smallest for the choice of covariates obtained using the algorithm proposed in this paper. For details of the experimental evaluations, refer to (ref).
We investigated the problem of finding a stable set of covariates to be used for forming blocks, that minimizes the variance of the causal effect estimates. By leveraging the underlying causal graph, we provided an efficient algorithm to obtain such a set for a general semi-Markovian causal model.
In the future, we are interested in extending our work towards further pruning the stable causal blocking set obtained in this paper for the reasons of economic cost. If the experimenter has a constraint on the cardinality (size) of the blocking set due to budget limitations, i.e. $|\mathcal{Z}| \le k_1$ where $k_1$ is specified by the experimenter. Furthermore, if blocking variables have different economic costs associated with them, for example, getting data on cholesterol level may be costlier (or difficult) as compared to the age of the patient, then we can introduce a knapsack budget constraint. Let $e(Z)$ be the cost associated with $Z\in \mathcal{Z}$ then the knapsack constraint would be $\sum_{Z\in\mathcal{Z}}e(Z) \le k_2$ where $k_2$ is specified by the experimenter. We are interested in solving the problem of finding stable solutions to (ref) with additional cardinality or knapsack constraint on the feasible solutions. Furthermore, we are interested in extending our work for the cases when the treatment and response variables are sets of variables. For the future direction to use the proposed algorithm for different real-world applications, refer to (ref). \\