Coverage optimized active learning for k - NN classifiers

Ajay J. Joshi, Fatih Porikli, Nikolaos P Papanikolopoulos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)

Abstract

Fast image recognition and classification is extremely important in various robotics applications such as exploration, rescue, localization, etc. k-nearest neighbor (kNN) classifiers are popular tools used in classification since they involve no explicit training phase, and are simple to implement. However, they often require large amounts of training data to work well in practice. In this paper, we propose a batch-mode active learning algorithm for efficient training of kNN classifiers, that substantially reduces the amount of training required. As opposed to much previous work on iterative single-sample active selection, the proposed system selects samples in batches. We propose a coverage formulation that enforces selected samples to be distributed such that all data points have labeled samples at a bounded maximum distance, given the training budget, so that there are labeled neighbors in a small neighborhood of each point. Using submodular function optimization, the proposed algorithm presents a near-optimal selection strategy for an otherwise intractable problem. Further we employ uncertainty sampling along with coverage to incorporate model information and improve classification. Finally, we use locality sensitive hashing for fast retrieval of nearest neighbors during active selection as well as classification, which provides 1-2 orders of magnitude speedups thus allowing real-time classification with large datasets.

Original languageEnglish (US)
Title of host publication2012 IEEE International Conference on Robotics and Automation, ICRA 2012
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages5353-5358
Number of pages6
ISBN (Print)9781467314039
DOIs
StatePublished - Jan 1 2012
Event 2012 IEEE International Conference on Robotics and Automation, ICRA 2012 - Saint Paul, MN, United States
Duration: May 14 2012May 18 2012

Publication series

NameProceedings - IEEE International Conference on Robotics and Automation
ISSN (Print)1050-4729

Other

Other 2012 IEEE International Conference on Robotics and Automation, ICRA 2012
CountryUnited States
CitySaint Paul, MN
Period5/14/125/18/12

Fingerprint

Classifiers
Image recognition
Image classification
Learning algorithms
Robotics
Sampling
Problem-Based Learning

Cite this

Joshi, A. J., Porikli, F., & Papanikolopoulos, N. P. (2012). Coverage optimized active learning for k - NN classifiers. In 2012 IEEE International Conference on Robotics and Automation, ICRA 2012 (pp. 5353-5358). [6225054] (Proceedings - IEEE International Conference on Robotics and Automation). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICRA.2012.6225054

Coverage optimized active learning for k - NN classifiers. / Joshi, Ajay J.; Porikli, Fatih; Papanikolopoulos, Nikolaos P.

2012 IEEE International Conference on Robotics and Automation, ICRA 2012. Institute of Electrical and Electronics Engineers Inc., 2012. p. 5353-5358 6225054 (Proceedings - IEEE International Conference on Robotics and Automation).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Joshi, AJ, Porikli, F & Papanikolopoulos, NP 2012, Coverage optimized active learning for k - NN classifiers. in 2012 IEEE International Conference on Robotics and Automation, ICRA 2012., 6225054, Proceedings - IEEE International Conference on Robotics and Automation, Institute of Electrical and Electronics Engineers Inc., pp. 5353-5358, 2012 IEEE International Conference on Robotics and Automation, ICRA 2012, Saint Paul, MN, United States, 5/14/12. https://doi.org/10.1109/ICRA.2012.6225054
Joshi AJ, Porikli F, Papanikolopoulos NP. Coverage optimized active learning for k - NN classifiers. In 2012 IEEE International Conference on Robotics and Automation, ICRA 2012. Institute of Electrical and Electronics Engineers Inc. 2012. p. 5353-5358. 6225054. (Proceedings - IEEE International Conference on Robotics and Automation). https://doi.org/10.1109/ICRA.2012.6225054
Joshi, Ajay J. ; Porikli, Fatih ; Papanikolopoulos, Nikolaos P. / Coverage optimized active learning for k - NN classifiers. 2012 IEEE International Conference on Robotics and Automation, ICRA 2012. Institute of Electrical and Electronics Engineers Inc., 2012. pp. 5353-5358 (Proceedings - IEEE International Conference on Robotics and Automation).
@inproceedings{8df541edc99444fd8c302d56a0a7b70c,
title = "Coverage optimized active learning for k - NN classifiers",
abstract = "Fast image recognition and classification is extremely important in various robotics applications such as exploration, rescue, localization, etc. k-nearest neighbor (kNN) classifiers are popular tools used in classification since they involve no explicit training phase, and are simple to implement. However, they often require large amounts of training data to work well in practice. In this paper, we propose a batch-mode active learning algorithm for efficient training of kNN classifiers, that substantially reduces the amount of training required. As opposed to much previous work on iterative single-sample active selection, the proposed system selects samples in batches. We propose a coverage formulation that enforces selected samples to be distributed such that all data points have labeled samples at a bounded maximum distance, given the training budget, so that there are labeled neighbors in a small neighborhood of each point. Using submodular function optimization, the proposed algorithm presents a near-optimal selection strategy for an otherwise intractable problem. Further we employ uncertainty sampling along with coverage to incorporate model information and improve classification. Finally, we use locality sensitive hashing for fast retrieval of nearest neighbors during active selection as well as classification, which provides 1-2 orders of magnitude speedups thus allowing real-time classification with large datasets.",
author = "Joshi, {Ajay J.} and Fatih Porikli and Papanikolopoulos, {Nikolaos P}",
year = "2012",
month = "1",
day = "1",
doi = "10.1109/ICRA.2012.6225054",
language = "English (US)",
isbn = "9781467314039",
series = "Proceedings - IEEE International Conference on Robotics and Automation",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "5353--5358",
booktitle = "2012 IEEE International Conference on Robotics and Automation, ICRA 2012",

}

TY - GEN

T1 - Coverage optimized active learning for k - NN classifiers

AU - Joshi, Ajay J.

AU - Porikli, Fatih

AU - Papanikolopoulos, Nikolaos P

PY - 2012/1/1

Y1 - 2012/1/1

N2 - Fast image recognition and classification is extremely important in various robotics applications such as exploration, rescue, localization, etc. k-nearest neighbor (kNN) classifiers are popular tools used in classification since they involve no explicit training phase, and are simple to implement. However, they often require large amounts of training data to work well in practice. In this paper, we propose a batch-mode active learning algorithm for efficient training of kNN classifiers, that substantially reduces the amount of training required. As opposed to much previous work on iterative single-sample active selection, the proposed system selects samples in batches. We propose a coverage formulation that enforces selected samples to be distributed such that all data points have labeled samples at a bounded maximum distance, given the training budget, so that there are labeled neighbors in a small neighborhood of each point. Using submodular function optimization, the proposed algorithm presents a near-optimal selection strategy for an otherwise intractable problem. Further we employ uncertainty sampling along with coverage to incorporate model information and improve classification. Finally, we use locality sensitive hashing for fast retrieval of nearest neighbors during active selection as well as classification, which provides 1-2 orders of magnitude speedups thus allowing real-time classification with large datasets.

AB - Fast image recognition and classification is extremely important in various robotics applications such as exploration, rescue, localization, etc. k-nearest neighbor (kNN) classifiers are popular tools used in classification since they involve no explicit training phase, and are simple to implement. However, they often require large amounts of training data to work well in practice. In this paper, we propose a batch-mode active learning algorithm for efficient training of kNN classifiers, that substantially reduces the amount of training required. As opposed to much previous work on iterative single-sample active selection, the proposed system selects samples in batches. We propose a coverage formulation that enforces selected samples to be distributed such that all data points have labeled samples at a bounded maximum distance, given the training budget, so that there are labeled neighbors in a small neighborhood of each point. Using submodular function optimization, the proposed algorithm presents a near-optimal selection strategy for an otherwise intractable problem. Further we employ uncertainty sampling along with coverage to incorporate model information and improve classification. Finally, we use locality sensitive hashing for fast retrieval of nearest neighbors during active selection as well as classification, which provides 1-2 orders of magnitude speedups thus allowing real-time classification with large datasets.

UR - http://www.scopus.com/inward/record.url?scp=84864428377&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84864428377&partnerID=8YFLogxK

U2 - 10.1109/ICRA.2012.6225054

DO - 10.1109/ICRA.2012.6225054

M3 - Conference contribution

SN - 9781467314039

T3 - Proceedings - IEEE International Conference on Robotics and Automation

SP - 5353

EP - 5358

BT - 2012 IEEE International Conference on Robotics and Automation, ICRA 2012

PB - Institute of Electrical and Electronics Engineers Inc.

ER -