Local case-control sampling

In classification, a dataset is a set of N data points ${\displaystyle (x_{i},y_{i})_{i=1}^{N}}$, where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): x_{i}\in {\mathbb R}^{d} is a feature vector, ${\displaystyle y_{i}\in \{0,1\}}$ is a label. Intuitively, a dataset is imbalanced when certain important statistical patterns are rare. The lack of observations of certain patterns does not always imply their irrelevance. For example, in medical studies of rare diseases, the small number of infected patients (cases) conveys the most valuable information for diagnosis and treatments.

Formally, an imbalanced dataset exhibits one or more of the following properties:

• Marginal Imbalance. A dataset is marginally imbalanced if one class is rare compared to the other class. In other words, ${\displaystyle \mathbb {P} (Y=1)\approx 0}$.
• Conditional Imbalance. A dataset is conditionally imbalanced when it is easy to predict the correct labels in most cases. For example, if ${\displaystyle X\in \{0,1\}}$, the dataset is conditionally imbalanced if ${\displaystyle \mathbb {P} (Y=1\mid X=0)\approx 0}$ and ${\displaystyle \mathbb {P} (Y=1\mid X=1)\approx 1}$.

In logistic regression, given the model ${\displaystyle \theta =(\alpha ,\beta )}$, the prediction is made according to ${\displaystyle \mathbb {P} (Y=1\mid X;\theta )={\tilde {p}}_{\theta }(x)={\frac {\exp(\alpha +\beta ^{T}x)}{1+\exp(\alpha +\beta ^{T}x)}}}$. The local-case control sampling algorithm assumes the availability of a pilot model ${\displaystyle {\tilde {\theta }}=({\tilde {\alpha }},{\tilde {\beta }})}$. Given the pilot model, the algorithm performs a single pass over the entire dataset to select the subset of samples to include in training the logistic regression model. For a sample ${\displaystyle (x,y)}$, define the acceptance probability as ${\displaystyle a(x,y)=|y-{\tilde {p}}_{\tilde {\theta }}(x)|}$. The algorithm proceeds as follows:

1. Generate independent ${\displaystyle z_{i}\sim {\text{Bernoulli}}(a(x_{i},y_{i}))}$ for ${\displaystyle i\in \{1,\ldots ,N\}}$.
2. Fit a logistic regression model to the subsample ${\displaystyle S=\{(x_{i},y_{i}):z_{i}=1\}}$, obtaining the unadjusted estimates ${\displaystyle {\hat {\theta }}_{S}=({\hat {\alpha }}_{S},{\hat {\beta }}_{S})}$.
3. The output model is ${\displaystyle {\hat {\theta }}=({\hat {\alpha }},{\hat {\beta }})}$, where ${\displaystyle {\hat {\alpha }}\leftarrow {\hat {\alpha }}_{S}+{\tilde {\alpha }}}$ and ${\displaystyle {\hat {\beta }}\leftarrow {\hat {\beta }}_{S}+{\tilde {\beta }}}$.

The algorithm can be understood as selecting samples that surprises the pilot model. Intuitively these samples are closer to the decision boundary of the classifier and is thus more informative.

The algorithm has the following properties. When the pilot is consistent, the estimates using the samples from local case-control sampling is consistent even under model misspecification. If the model is correct then the algorithm has exactly twice the asymptotic variance of logistic regression on the full data set. For a larger sample size with ${\displaystyle c>1}$, the factor 2 is improved to ${\displaystyle 1+{\frac {1}{c}}}$.