ML Anthology

Boosting Nearest Neighbors for the Efficient Estimation of Posteriors

Roberto D'Ambrosio, Richard Nock, Wafa Bel Haj Ali, Frank Nielsen, Michel Barlaud
ECML-PKDD 2012 pp. 314-329
doi:10.1007/978-3-642-33460-3_26 /ecmlpkdd/2012/daposambrosio2012ecmlpkdd-boosting/

Abstract

It is an admitted fact that mainstream boosting algorithms like AdaBoost do not perform well to estimate class conditional probabilities. In this paper, we analyze, in the light of this problem, a recent algorithm, unn , which leverages nearest neighbors while minimizing a convex loss. Our contribution is threefold. First, we show that there exists a subclass of surrogate losses, elsewhere called balanced, whose minimization brings simple and statistically efficient estimators for Bayes posteriors. Second, we show explicit convergence rates towards these estimators for unn , for any such surrogate loss, under a Weak Learning Assumption which parallels that of classical boosting results. Third and last, we provide experiments and comparisons on synthetic and real datasets, including the challenging SUN computer vision database. Results clearly display that boosting nearest neighbors may provide highly accurate estimators, sometimes more than a hundred times more accurate than those of other contenders like support vector machines.

PDF ECML-PKDD Semantic Scholar

Cite

Text

D'Ambrosio et al. "Boosting Nearest Neighbors for the Efficient Estimation of Posteriors." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2012. doi:10.1007/978-3-642-33460-3_26

Markdown

[D'Ambrosio et al. "Boosting Nearest Neighbors for the Efficient Estimation of Posteriors." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2012.](https://mlanthology.org/ecmlpkdd/2012/daposambrosio2012ecmlpkdd-boosting/) doi:10.1007/978-3-642-33460-3_26

BibTeX

@inproceedings{daposambrosio2012ecmlpkdd-boosting,
  title     = {{Boosting Nearest Neighbors for the Efficient Estimation of Posteriors}},
  author    = {D'Ambrosio, Roberto and Nock, Richard and Ali, Wafa Bel Haj and Nielsen, Frank and Barlaud, Michel},
  booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
  year      = {2012},
  pages     = {314-329},
  doi       = {10.1007/978-3-642-33460-3_26},
  url       = {https://mlanthology.org/ecmlpkdd/2012/daposambrosio2012ecmlpkdd-boosting/}
}