key: cord-0570318-g0wv29fo
authors: Ribeiro, Andre F.
title: The External Validity of Combinatorial Samples and Populations
date: 2021-08-09
journal: nan
DOI: nan
sha: d3e6a5df6152bf8e168dfd5848793beadab98f07
doc_id: 570318
cord_uid: g0wv29fo

The widely used 'Counterfactual' definition of Causal Effects was derived for unbiasedness and accuracy - and not generalizability. We propose a simple definition for the External Validity (EV) of Interventions, Counterfactual statements and Samples. We use the definition to discuss several issues that have baffled the counterfactual approach to effect estimation: out-of-sample validity, reliance on independence assumptions or estimation, concurrent estimation of many effects and full-models, bias-variance tradeoffs, statistical power, omitted variables, and connections to supervised and explaining techniques. Methodologically, the definition also allow us to replace the parametric and generally ill-posed estimation problems that followed the counterfactual definition by combinatorial enumeration problems on non-experimental samples. We use over 20 contemporary methods and simulations to demonstrate that the approach leads to accuracy gains in standard out-of-sample prediction, intervention effect prediction and causal effect estimation tasks. The COVID19 pandemic highlighted the need for learning solutions to provide general predictions in small samples - many times with missing variables. We also demonstrate applications in this pressing problem.

Donald Rubin's seminal research 25, 32, 33 still provides the most broadly-used and well-accepted definition for what is a causal effect. If y is an outcome of interest and a is a treatment indicator, then the causal effect of a is the difference

where y +a i is the outcome of individual i under the treatment. The central concept behind Eq.

(1) was inspired by experimental estimation: by fixing every factor, other than the treatment, we can declare that the observed difference in outcome was certainly caused by the treatment -and the treatment alone. The definition is an ideal, as it is impossible to observe outcomes for an individual, concurrently, in two different and totally fixed conditions. The theory goes that we may, instead, 'fix' factors in expectation, and across individuals. If the treated and non-treated subpopulations have the same expected values across all factors then any difference between the groups is due to the treatment -given large enough samples. This can be paraphrased with an independence statement:

the treatment must be conditionally independent on all other relevant factors. This train-of-thought lead to the notion of Sample Balance in non-experimental estimation and the objective most current causality estimators minimize.

We consider, instead,

where Π S (m) is a set of permutations of a very large number of factors m, and y < is the outcome of the set of elements before a in the permutation order, and y ≤ the set including a. This is also an ideal, but defines causal effects in a way that is almost opposite to Eq. (1). It calls for effects to be observed under large variation -as opposed to no variation. The most important element of this definition is Π S , the number of permutations observed in a sample. 

EV is here the inverse of the variance (i.e. the precision) of effects under a large Π S . Very importantly, these definitions can be extended to multiple causes, a∈X. We demonstrate that, due to their high number of permutations and equal subpopulation representation, causes defined this way are both predictive and free of sample-biases. We thus look at non-experimental samples as random draws of squares. This is in contrast to simply permuting sample observation orders 34 

A maximally accurate estimator (i.e., one with minimum variance) minimizes the covariance between the individuals, or individual states, it is comparing. Combinatorically, this can be seen as maximizing their intersecting factors, Fig.1 intersecting factors) with the first. A partial permutation is a permutation with d fixed-points, d<m.

The number of permutations, derangements and partial permutations 12 is

The last number indicates that, to form a partial permutation, we select d unique Sample Representation Expected effects for a population can be decomposed into sums of frequencies and effects across all its subpopulations. For

are subpopulation frequencies and higher-order effects are additive interactions. This is, for example, the sample representation behind Factorial Experimental Designs and Analysis of Variance 30 We therefore look at a difference in outcomes ∆ i (X) from the individual x i as Sample Power A square transversal defines an ordering of population members or sample observations. Horizontal and vertical transversals differ in respect to ACC but follows similar patterns in respect to EV and CF. The transversal also defines a random walk and geometric progression of X m subset sizes. The first factor in the transversal splits X into two subsets, those with factor

is the reference's value for a. The second factor splits each of these subsets into two further subsets,

. This is easily visualized as a progression of interval bisections whose lengths correspond the cardinality of factors not yet drawn. Interval lengths follow, Consider what happens as we increase CF and take subpopulations with pairwise differences of 2 (instead of 1). This corresponds to squares with size (m/2) 2 . At each t, the subsequent individuals have two common factors selected from m 2 . These, arbitrarily named a and b, lead to the split

x i (ab) andx i (ab). We miss, in a full square, differences that could parse out a and b's individual effects. A transversal and full sequence of individuals leads now to a geometric progression with shrinking lengths 18, 24 , (1/2) 2t . Fig.1 (e) illustrates how this impacts the generated permutations.

It shows permutation distributions with (1/2) 2n mod m (dark-grey) and (1/2) 3n mod m (light-grey).

Remember that each permutation corresponds to an ordering of factors, a < b < c < d < ... Sample permutations are, in this case, biased towards a heading set of factors a < b < ... 

for the first and many (tending to n) squares scenarios. The number of permutations in observational data are, this way, determined by its rare factors, which demand samples with increasing sizes to match the number of permutations in their balanced counterparts. We will not always assume that m is large, infinite or appropriate. In some cases, we observe m < m. In this case, the previous errors are no longer independent, and we assume a common and additive component ε sq across cells, 

Simulations We consider simulations with increasing complexity, then a real-world application.

Simulations follow common generative models 6 , with m = 10 Binomial factors, X 10 , and sigmoidal outcomes, y (as in logistic and many categorization models). The cases are: probabilities and effects constant and additive (hypercube), both probabilities and effects sampled from a Uniform distribution U ([0, 1]) (additive), variables random sampled but correlated with the previous (correlated), and, 3 variables randomly omitted from samples (omitted). Fig.2(a) shows the number of observed permutations on runs with increasing sample sizes, n (hypercube). The right panel show combinatorial limits for m=10, Eq. (6) . The same is shown as histograms of square member counts, Fig.2(b) . This illustrates how sample sizes directly affect observed permutation counts, with distinct numbers of fixed-points. We expect these non-parametric counts to impact biases and predictive performance, Eq. An understanding of the relationship among samples, ACC and EV is necessary to devise accurate and maximally general models, with minimal samples. To that end, we consider ACC (percentage of correctly classified cases in validation sections) as we increase n. We use two validation sections: internal and external. The internal section is divided in typical training and validation subsections. We use cross validation in the internal section with 4 folds across cases.

When ordered arbitrarily or randomly, the internal-external division is inconsequential (as long as steps contain enough samples). We will define however different sample orderings and consider how they impact learning performance. Starting with n=0, we train several algorithms with increasing n.

We study out-of-sample prediction, y ∼ X, out-of-sample counterfactual prediction, ∆y ∼ (x i −x j ), For the next cases, we enumerate squares from Y X and consider transversals with increasing ACC only (vertical). We use the previous transversal, from X, but repeat it for Y X in each training fold. This increases ACC, without using data (outcomes) unavailable in typical validation. Results are in Fig.2(d,e) Learning in this case no longer minimizes the expected risk, but the risk in the combinatorial set of all subpopulations. In these cases, there is little difference in performance among the widely different models, with low variance, suggesting analytic limits and explanations. Recommended sample sizes for the many squares asymptotic case, Eq.8, are marked with a dotted line across simulated (mean over runs) and real-word cases.

The figure also shows an alternative 'Travel-Salesman' order (rightmost). It is obtained by solving a TSP: individuals are cities, and their factor differences are distances. This order shares an important characteristic with square transversals: differences between sample units are kept small in the output, full-sample order. The orders differ, however, in an important way: differences in the TSP are arbitrary and non-cyclic (following empirical sample frequencies). In this case, EV is steeply reducing, in direct contrast to square enumerations, Fig.2(d,e) . This is not due to algorithms becoming sensitive to sample noise -as typical in overfitting and lack of generalization. It portrays the expected behavior from algorithms when supplied with an increasingly complex population, generating models from specialized to general. The algorithmic stack includes regularized solutions (LASSO and Ridge regressions). Fig.2 (d,e) repeat across generative models, but we observe increased gains proceeding from the hypercube to the correlated case, Fig.2(g) . Current solutions are expected to perform well in samples whose variables are indepedent and unbiased (Sect.2). Fig.2(g) shows increasing EV gains with correlations ρ = {0.1, 0.25, 0.5} (additive). While the concepts above can give researchers larger control over the generalizability of learning solutions, we started with the goal of studying the EV of counterfactual predictions. This case is show in Fig.2(f) . We take this to be the prediction of effect differences from covariate contrasts. The figure illustrates that everyday algorithms are ineffective in this case. The intuition, and why the problem is rarely framed this way, was articulated above: using differences implies loss of large quantities of information in the form of permutations and pairwise overlaps, decreasing the capability of algorithms to generalize effectively. The figure shows, however, that models can generalize effectively if overlaps are considered carefully. This echoes the increased performance over correlated data.

Our current emphasis is on the use of supervised solutions that are highly tuned to gener-20 alizability, but we mention implications to causal and explaining techniques. Fig.3(b) shows the performance of 3 widely used causal effect estimators and the IME with random and square orders (additive, ρ=0.25). The first estimator is the recent Deconfounder 42 (Sect. 3.1, linear Bayesian factor model fit with Variational Bayes, logistic outcomes and Normal priors). The second is gcomputation 6 , a extremely efficient solution popular in epidemiology. A propensity score matching estimator 31 is included for its popularity and baseline significance. The y-axis has sum of square differences between estimated and ground truth (for all variables). These algorithms (causal and explainer) make contrasting assumptions. The first focuses on biasedness, the second combines (biased and often heuristic) predictive regressions for model selection. Performance increases in both fronts under square enumerations. Notice that both the Deconfounder and g-computations are highly-tuned to the used generative models, as all both rely on logistic regressions. This exemplifies the attraction of nonparametric insights that can take the burden of perfect specification away from researchers.

The COVID19 pandemic continues to threaten the lives and livelihoods of billions around the world. As of the break of the pandemic, there was a rush and expectations for ML solutions to help inform policy and individuals' decisions 13, 19, 41 . In practice, few of these approaches were truly useful, with SIR semi-deterministic models 7 , or their specializations, used almost exclusively. These offer predictions at high aggregate levels -most often country and city levels -taking all individuals therein to be the same. Some sources of heterogeneity have been identified, age being the most obvious. We discuss two issues, how to (1) generate general models as fast as possible, and, (2) make predictions with unobservables. We consider two data sources. The first is the UK Biobank 5 : a dataset with ∼500K UK citizens, 100K infected, 5K

variables. It includes a wide variety of variables -not only from individuals' electronic medical records, but also sociodemographic, economic, living, behavior and psychological annotations.

The attraction is its completeness, high-dimensionality, and level (individual). We also consider a recent data dump from the American Center for Disease Control (CDC) 8 with ∼24M cases but limited variables (age, geographic, race, ethnicity and sex). The interest is as platform to discuss the unobserved factors case. Binary outcome is COVID19 infection in both cases. Fig.1(a) . This is a case that squares address directly. Errors across pairs are approximately constant for a given square size (horizontal lines). That's because errors affect all subpopulations uniformly, Eq.(9). Increasing square sizes leads to error increases at regular and linear rates (lines with different colors), due to ε d . Enumeration of multiple squares, with distinct references, reduces these errors for individual population members. Fig.3 (c) also shows the impact of omitted variables (rightmost panels). This is the impact of omitting variables from the sample, and not across individual pairs. Introduction of unobservables leads to an additive increase in horizontal and vertical errors. The presence of this common and latent error component suggests an ANOVA decomposition of empirical sample errors, Eq.9. The COVID19 Case Surveillance database 8 includes patient-level data reported by US states to the CDC. We use the subsample with simultaneously non-missing age, sex, race, ethnicity and location (county-level). This leads to 10 binary variables and ∼11M cases. We additionally generated a set of synthetic controls from the same variables in the 2019 American census (county level). Fig.3(c) repeats the previous plots for the 5 counties with highest case counts. As expected, ANOVA estimates of ε sq (i.e., from unobserved variables) vary significantly across locations (right) but these have little impact over observed variable pairwise errors (as they affect observed square subpopulations uniformly and can be proxied-out). Fig.3(e) shows MSE of a Leave-One-Out task for every American county using 3 of the best performers in the previous tasks. Case information from all other counties are used to predict a given location's COVID19 incidence. Fig.3 (f) repeats the task with the ε sq ANOVA estimate as added feature.

The central methodological challenge in the Sciences, Policy-making and Design remains the evaluation of counterfactual statements (Did this treatment caused the result of interest? Did this policy?) The counterfactual definition of effects formulated sample properties necessary for effects to be free of selection biases, Eq.(1). We formulated sample properties necessary for their External Validity, Eq.(4). We discussed out-of-sample, counterfactual, correlated and missing variables prediction, as well as effect estimation, in simulations and an important real-world example. A central result demonstrated here is that the EV of interventions are, to some extent, predictable from combinatorial properties of the populations they act upon. To a broad audience, ML methods are inherently limited due to the lack of EV, CF and ACC guarantees and bounds when compared to, for example, experimental hypothesis testing. We believe the work could help build further connections between predictive and causal techniques.

Large sample properties of matching estimators for average treatment effects

Estimating the effects of continuousvalued interventions using generative adversarial networks

Invariance, causality and robustness

A review of instrumental variable estimators for mendelian randomization. Statistical methods in medical research

Peter Donnelly, and Jonathan Marchini. The uk biobank resource with deep phenotyping and genomic data

Gcomputation, propensity score-based methods, and targeted maximum likelihood estimator for causal inference with different covariates sets: a comparative simulation study

Causation, prediction, and search / Peter Spirtes, Clark Glymour, and Richard Scheines

Kernel methods for measuring independence

Na\"ive regression requires weaker assumptions than factor models to adjust for multiple cause confounding

Matchings, derangements, rencontres. Mathematics Magazine

Individual and community-level risk for covid-19 mortality in the united states

Learning representations for counterfactual inference

Entropy and diversity

Why propensity scores should not be used for matching

Large-scale parallel breadth-first search

Random walk with shrinking steps

Individual-level fatality prediction of covid-19 patients using ai methods

Causal inference on discrete data via estimating distance correlations

Causal effect inference with deep latent-variable models

Domain adaptation by using causal inference to predict invariant conditional distributions

Identification of treatment effects under conditional partial independence

Similarity and selfsimilarity in random walk with fixed, random and shrinking steps

Counterfactuals and Causal Inference: Methods and Principles for Social Research

Includes bibliographical references

Game Theory: A Multi-Leveled Approach

Causal inference by using invariant prediction: identification and confidence intervals

Learning representations by maximizing mutual information in variational autoencoders

What can the millions of random treatments in nonexperimental data reveal about causes?

The central role of the propensity score in observational studies for causal effects

Estimating causal effects of treatments in randomized and nonrandomized studies

Causal inference using potential outcomes: Design, modeling, decisions

Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead

Topological properties of hypercubes

Elements of Causal Inference : Foundations and Learning Algorithms

Toward causal representation learning

Estimating individual treatment effect: generalization bounds and algorithms

Identification and estimation of causal effects from dependent data

Estimates of the severity of coronavirus disease 2019: a model-based analysis

The blessings of multiple causes

Transformers: State-of-the-art natural language processing

Counterfactual prediction for bundle treatment

Advances in Neural Information Processing Systems