In machine learning, local case-control sampling is an algorithm used to reduce the complexity of training a logistic regression classifier. The algorithm reduces the training complexity by selecting a small subsample of the original dataset for training. It assumes the availability of a (unreliable) pilot estimation of the parameters. It then performs a single pass over the entire dataset using the pilot estimation to identify the most "surprising" samples. In practice, the pilot may come from prior knowledge or training using a subsample of the dataset. The algorithm is most effective when the underlying dataset is imbalanced. It exploits the structures of conditional imbalanced datasets more efficiently than alternative methods, such as case control sampling and weighted case control sampling.
Contents
Imbalanced datasets
In classification, a dataset is a set of N data points
Formally, an imbalanced dataset exhibits one or more of the following properties:
Algorithm outline
In logistic regression, given the model
- Generate independent
z i ∼ Bernoulli ( a ( x i , y i ) ) fori ∈ { 1 , … , N } . - Fit a logistic regression model to the subsample
S = { ( x i , y i ) : z i = 1 } , obtaining the unadjusted estimatesθ ^ S = ( α ^ S , β ^ S ) . - The output model is
θ ^ = ( α ^ , β ^ ) , whereα ^ ← α ^ S + α ~ β ^ ← β ^ S + β ~
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.
Obtaining the pilot model
In practice, for cases where a pilot model is naturally available, the algorithm can be applied directly to reduce the complexity of training. In cases where a natural pilot is nonexistent, an estimate using a subsample selected through another sampling technique can be used instead. In the original paper describing the algorithm, the authors propose to use weighted case-control sampling with half the assigned sampling budget. For example, if the objective is to use a subsample with size
Larger or smaller sample size
It is possible to control the sample size by multiplying the acceptance probability with a constant
Properties
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