Linear Classification and Selective Sampling Under Low Noise Conditions
We provide a new analysis of an efficient margin-based algorithm for selective sampling in classification problems. Using the so-called Tsybakov low noise condition to parametrize the instance distribution, we show bounds on the convergence rate to the Bayes risk of both the fully supervised and the selective sampling versions of the basic algorithm. Our analysis reveals that, excluding logarithmic factors, the average risk of the selective sampler converges to the Bayes risk at rate $n^{-(1+\alpha)/(3+\alpha)}$, with labels being sampled at the same rate (here $n$ denotes the sample size, and $\alpha > 0$ is the exponent in the low noise condition). We compare this convergence rate to the rate $n^{-(1+\alpha)/(2+\alpha)}$ achieved by the fully supervised algorithm using all labels. Experiments on textual data reveal that simple variants of the proposed selective sampler perform much better than popular and similarly efficient competitors.
Code (0)
등록된 구현이 없습니다.
Tasks
ClassificationGeneral ClassificationSimilar Papers 제목 키워드 기반
Selective sampling for accelerating training of deep neural networks
We present a selective sampling method designed to accelerate the training of deep neural networks. To this end, we introduce a novel measurement, the minimal margin score (MMS), which measures the minimal amount of disp…
Binary ClassificationClassificationGeneral Classificationimage-classification+1Convergence of Nearest Neighbor Pattern Classification with Selective Sampling
In the panoply of pattern classification techniques, few enjoy the intuitive appeal and simplicity of the nearest neighbor rule: given a set of samples in some metric domain space whose value under some function is known…
ClassificationGeneral ClassificationJointly Resampling and Reconstructing Corrupted Images for Image Classification using Frequency-Selective Mesh-to-Grid Resampling
Neural networks became the standard technique for image classification throughout the last years. They are extracting image features from a large number of images in a training phase. In a following test phase, the netwo…
Classificationimage-classificationImage ClassificationConvergence of Uncertainty Sampling for Active Learning
Uncertainty sampling in active learning is heavily used in practice to reduce the annotation cost. However, there has been no wide consensus on the function to be used for uncertainty estimation in binary classification …
Active LearningBinary ClassificationClassificationMulti-class ClassificationMargin-Based Regularization and Selective Sampling in Deep Neural Networks
We derive a new margin-based regularization formulation, termed multi-margin regularization (MMR), for deep neural networks (DNNs). The MMR is inspired by principles that were applied in margin analysis of shallow linear…
ClassificationGeneral Classificationimage-classificationImage Classification+7