*! version 0.2 beta 27fev2015

Title

Combinatorics -- This data mining program performs batch OLS estimation, out-of-sample validation and Leave-one-out cross-validation (LOOCV) on all the 2^n models combined from a set of n candidate explanatory variables.

Syntax

combinatorics
depvar indepvars [if] [in] [weight]
[, options]

Model
add(varlist) Add this list of independent variables to all 2^n models

Reporting
saving(filename [,noreplace]) Save the results in a file instead of replacing the current dataset.

depvar, indepvars and varlist may contain factor-variable operators (see fvvarlist).

depvar, indepvars and varlist may contain time-series operators (see tsvarlist).

aweights, fweights, and iweights are
allowed; see weight.

Description

combinatorics evaluates the OLS explanatory performances and out-of-sample (OOS) predictive performances of all possible 2^n models of a dependent variable that can be generated with a given set of n possible explanatory variables.
This can be used in data mining in order to evaluate the distribution of predictors' coefficients and performances across the space of potential models.
This can also be used as a benchmark tool in order to evaluate model selection and machine learning algorithms in natural datasets.
Given the important risk of overfitting in high-dimensional feature selection problems, a model's performance is better approached by its cross-validation measure of fit, which is calculated here (see LOOCV measures below).
Note that the number of possible models explodes with the number of possible explanatory variables and you would better limit yourself to 20 indepvars max (i.e., 1,048,576 models).
This command is a wrapper for tuples and installs it automatically if necessary.

The resulting dataset contains 2^n rows, one for each evaluated model. For each model are displayed the variables shown below.

Model's characteristics:

i: Identification number of the model.

model: (Only for Stata versions >=13) String variable containing the specification of the model, in a Stata-readable format.

rank: Rank of the model, i.e. the number of non-collinear explanatory variables (constant included).

timer: Time in seconds since the beginning of the program until the evaluation of this model.

Model's estimation results:

n: The sample size of the OLS estimation of this model.

r2: The explanatory performance of the model, as measured by the R-squared.

[Coefficient's name]: Vector of variables containing the model's coefficients, set to missing values if not estimated in this model.

[Coefficient's name_SE]: Vector of variables containing the model coefficients's standard errors, set to missing values if not estimated in this model.

Model's out-of-sample predictive performances:

pseudor2: Leave-one-out Cross-Validation (LOOCV) pseudo-R2, approximated from the hat matrix, calculated in the estimation subsample.

rmse: Root Mean Squared Error of prediction, calculated from the LOOCV procedure.

oosn: Sample size of the validation subsample, which is the complement subsample of the estimation subsample. Should be missing if no [if] [in] options constrain the estimation subsample.

oosr2: Predictive performance of the model in the validation subsample, as measured by the squared of the correlation coefficient between predicted and actual dependent variable (pseudo-R2).
Should be missing if no [if] [in] options constrain the estimation subsample.

Options

Model

add(varlist) Specifies a list of independent variables that will automatically be added in every one
of the 2^n models.

Reporting

saving(filename [,noreplace]) Save the output in this .dta file instead of replacing the current dataset.
Suboption noreplace forbids files to be overwritten. Default behavior is to overwrite any existing files.

Issues

This program is still in beta.

There is no interest for this program if your set of candidate independent variables is too large (e.g. greater than 20 variables).
The program won't interrupt but the computation time doubles for every supplementary variable in indepvars.
You should definitely run model selection algorithms that do not search exhaustively through the models space if you intend to do model selection with tons of potential explanatory variables.

If you experience any trouble or bugs, please send me an e-mail at the address specified at the end of this page.

Examples

Open the 1978 Automobile Dataset, and evaluate the 1,024 models of the cars' price obtained from combining all of their 10 characteristics:

. sysuse auto,clear

. combinatorics price mpg i.rep78 headroom-foreign

In the resulting dataset, plot the histogram of the 512 mpg coefficients obtained across all models:

. hist mpg

Plot the relationship between the models explanatory and predictive performances (R2 and LOOCV Pseudo-R2) against the complexity of the model (Rank):

. twoway (scatter pseudor2 r2 rank,jitter(5 5))(lpolyci pseudor2 rank)(lpolyci r2 rank),xline(6)

* The LOOCV Pseudo-R2 does not increases monotonically with model complexity (it reaches a local maximum at a rank of 6), signing a risk of overfitting and calling for parsimony in the model selection.

(The economist's bad practice:) Generate p-values for mpg coefficients and show the models of rank 6 whose significance is below 1% for these coefficients:

. gen double mpg_p=ttail(n-rank,abs(mpg/mpg_se))*2

. list model pseudor2 if mpg_p<0.01 & rank==6

* ("model" only shows for Stata 13 and above) Best model to predict price with a highly significant mpg coefficient is obtained with the model made of
mpg, headroom, trunk, gear_ratio, and foreign (plus the constant).

Examples with out-of-sample validation

Open again the 1978 Automobile Dataset, and evaluate the same models as above, but this time on only 90% of the sample, chosen randomly:

. sysuse auto,clear

. set seed 100

. gen double oos=(runiform()>0.9)

. combinatorics price mpg i.rep78 headroom-foreign if !oos

The remaining 10% serve for "out-of-sample" (OOS) predictions:
the predictions are made out of their estimation sample and tested against the actual values;
the OOS Pseudo-R² is the squared of the correlation coefficient between OOS predicted and actual values.
It can be used as a measure of predictive performance in the same way as the LOOCV Pseudo R²:

. twoway (lpolyci r2 rank)(lpolyci pseudor2 rank)(lpolyci oosr2 rank)

It is more easy to communicate results with OOS Pseudo-R² but LOOCV Pseudo-R² is a better procedure
as it does not require to spare observations and does not rely on the -arbitrary or random - choice of the validation sample and sample size.
For instance, had we chose another validation sample, the OOS Pseudo-R² could have given a different conclusion but the LOOCV Pseudo R² would keep
showing overfitting:

. sysuse auto,clear

. set seed 200

. gen double oos=(runiform()>0.9)

. combinatorics price mpg i.rep78 headroom-foreign if !oos

. twoway (lpolyci r2 rank)(lpolyci pseudor2 rank)(lpolyci oosr2 rank)

Examples with factor-variables and time-series operators

Open the S&P500 Dataset, and evaluate the models of a day's price change obtained from combining trade volume, price change, and/or price high, low and/or their interaction with values taken one and/or two
days before (10 predictors):

. sysuse sp500,clear

. tsset date,daily

. combinatorics change L(1/2).(volume change c.high##c.low)

In the resulting dataset, look at the statistics of the models' explanatory power (R²) and predictive power (LOOCV Pseudo R²), both are extremely low:

. summarize r2 pseudor2

Looking at the relationship between explanatory and predictive powers as regards model's complexity,
we see a high risk of overfitting (explanatory power increases with rank as predictive power decreases):

. twoway (scatter pseudor2 r2 rank,jitter(5 5))(lpolyci pseudor2 rank)(lpolyci r2 rank)

* The fact that the Pseudo-R² is so low that it attains negative values is theoretically possible.

Examples with adding a fixed explanatory variables set

We reload the previous dataset and run the same command, but this time we add for each of the models the daily differences in price changes from the second to the fourth days before:

. sysuse sp500,clear

. tsset date,daily

. combinatorics change L(1/2).(volume change c.high##c.low),add(D(2/4).change)

In the resulting dataset, the models' performances show cases of perfect collinearity between explanatory and dependent variables (R²=1):

. summarize r2 pseudor2

These collinear cases seem to appear when change is predicted by its second difference, plus twice its first lag minus its second lag:

. format %10.0f D2_change-_constant

. summarize D2_change-_constant if r2==1, sep(0) format

We can check that:

. sysuse sp500,clear

. tsset date,daily

. reg change D2.change L1.change L2.change

References

Hastie, Trevor, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning:
Data Mining, Inference, and Prediction. Springer Science & Business Media, 2013.

Luchman, Joseph, Klein, Daniel and Cox, Nicholas, (2016), TUPLES: Stata module for selecting all possible tuples from a list,
http://EconPapers.repec.org/RePEc:boc:bocode:s456797

Author

Claire Vandendriessche

Paris School of Economics

claire.vandendriessche@psemail.eu