Border Sampling through Coupling Markov Chain Monte Carlo

Recently, progressive border sampling (PBS) was proposed for sample selection in supervised learning by progressively learning an augmented full border from small labeled datasets. However, this quadratic learning algorithm is inapplicable to large datasets. In this paper, we incorporate the PBS to a state of the art technique called coupling Markov chain Monte Carlo (CMCMC) in an attempt to scale the original algorithm up on large labeled datasets. The CMCMC can produce an exact sample while a naive strategy for Markov chain Monte Carlo cannot guarantee the convergence to a stationary distribution. The resulting CMCMC-PBS algorithm is thus proposed for border sampling on large datasets. CMCMC-PBS exhibits several remarkable characteristics: linear time complexity, learner-independence, and a consistent convergence to an optimal sample from the original training sets by learning from their subsamples. Our experimental results on the 33 either small or large labeled datasets from the UCIKDD repository and a nuclear security application show that our new approach outperforms many previous sampling techniques for sample selection.