logo Idiap Research Institute        
 [BibTeX] [Marc21]
Importance Sampling Tree for Large-scale Empirical Expectation
Type of publication: Conference paper
Citation: Canevet_ICML_2016
Publication status: Accepted
Booktitle: Proceedings of the International Conference on Machine Learning (ICML)
Year: 2016
Month: June
Location: New-York
Abstract: We propose a tree-based procedure inspired by the Monte-Carlo Tree Search that dynamically modulates an importance-based sampling to prioritize computation, while getting unbiased estimates of weighted sums. We apply this generic method to learning on very large training sets, and to the evaluation of large-scale SVMs. The core idea is to reformulate the estimation of a score - whether a loss or a prediction estimate - as an empirical expectation, and to use such a tree whose leaves carry the samples to focus efforts over the problematic "heavy weight" ones. We illustrate the potential of this approach on three problems: to improve Adaboost and a multi-layer perceptron on 2D synthetic tasks with several million points, to train a large-scale convolution network on several millions deformations of the CIFAR data-set, and to compute the response of a SVM with several hundreds of thousands of support vectors. In each case, we show how it either cuts down computation by more than one order of magnitude and/or allows to get better loss estimates.
Projects Idiap
Authors Canévet, Olivier
Jose, Cijo
Fleuret, Francois
Added by: [UNK]
Total mark: 0