We present a novel distribution-free approach, the data-driven threshold machine (DTM), for a fundamental problem at the core of many learning tasks: choose a threshold for a given pre-specified level that bounds the tail probability of the maximum of a (possibly dependent but stationary) random sequence. We do not assume data distribution, but rather relying on the asymptotic distribution of extremal values, and reduce the problem to estimate three parameters of the extreme value distributions and the extremal index. We specially take care of data dependence via estimating extremal index since in many settings, such as scan statistics, change-point detection, and extreme bandits, where dependence in the sequence of statistics can be significant. Key features of our DTM also include robustness and the computational efficiency, and it only requires one sample path to form a reliable estimate of the threshold, in contrast to the Monte Carlo sampling approach which requires drawing a large number of sample paths. We demonstrate the good performance of DTM via numerical examples in various dependent settings.
Extreme Value Theory (EVT) describes the distribution of data considered extreme with respect to some generative distribution, effectively modelling the tails of that distribution. In novelty detection, or one-class classification, we wish to determine if data are “normal” with respect to some model of normality. If that model consists of generative distributions, then EVT is appropriate for describing the behaviour of extremes generated from the model, and can be used to determine the location of decision boundaries that separate “normal” areas of data space from “abnormal” areas in a principled manner. This paper introduces existing work in the use of EVT for novelty detection, shows that existing work does not accurately describe the extrema of multivariate, multimodal generative distributions, and proposes a novel method for overcoming such problems. The method is numerical, and provides optimal solutions for generative multivariate, multimodal distributions of arbitrary complexity. In a companion paper, we present analytical closed-form solutions which are currently limited to unimodal, multivariate generative distributions. This article presents a hierarchical classification method for high-resolution satellite imagery incorporating extreme value theory EVT-based normalization to calibrate multiple-feature scores. First, a simple linear iterative clustering algorithm is used to over-segment an image to build a superpixel representation of the scene. Then, each superpixel is characterized by three different visual descriptors. Finally, a two-phase classification model is proposed for achieving classification of the scene: 1 in the first phase, a support vector machine SVM with histogram intersection kernel is applied to each feature channel to obtain raw soft probability; and 2 in the second phase, the derived soft outputs are multiplied to build a product space for score-level fusion. The fused scores are subsequently further calibrated using the EVT and fed to an L1-regularized L2-loss SVM to obtain the final result. Experimental analysis on high-resolution satellite scenes shows that the proposed method achieves promising classification results and outperforms other competitive methods. Recognition problems in computer vision often benefit from a fusion of different algorithms and or sensors, with score level fusion being among the most widely used fusion approaches. Choosing an appropriate score normalization technique before fusion is a fundamentally difficult problem because of the disparate nature of the underlying distributions of scores for different sources of data. Further complications are introduced when one or more fusion inputs outright fail or have adversarial inputs, which we find in the fields of biometrics and forgery detection. Ideally a score normalization should be robust to model assumptions, modeling errors, and parameter estimation errors, as well as robust to algorithm failure. In this paper, we introduce the w-score, a new technique for robust recognition score normalization. We do not assume a match or non-match distribution, but instead suggest that the top scores of a recognition system's non-match scores follow the statistical Extreme Value Theory, and show how to use that to provide consistent robust normalization with a strong statistical basis. Determining a detection threshold to automatically maintain a low false alarm rate is a challenging problem. In a number of different applications, the underlying parametric assumptions of most automatic target detection algorithms are invalid. Therefore, thresholds derived using these incorrect distribution assumptions do not produce desirable results when applied to real sensor data. Monte Carlo methods for threshold determination work well but tend to perform poorly when targets are present. In order to mitigate these effects, we propose an algorithm using extreme value theory through the use of the generalized Pareto distribution (GPD) and a Kolmogorov-Smirnov statistical test. Unlike previous work based on GPD estimates, this algorithm incorporates a way to adaptively maintain low false alarm rates in the presence of targets. Both synthetic and real-world detection results demonstrate the usefulness of this algorithm. In this paper, we define meta-recognition, a performance prediction method for recognition algorithms, and examine the theoretical basis for its postrecognition score analysis form through the use of the statistical extreme value theory (EVT). The ability to predict the performance of a recognition system based on its outputs for each match instance is desirable for a number of important reasons, including automatic threshold selection for determining matches and nonmatches, and automatic algorithm selection or weighting for multi-algorithm fusion. The emerging body of literature on postrecognition score analysis has been largely constrained to biometrics, where the analysis has been shown to successfully complement or replace image quality metrics as a predictor. We develop a new statistical predictor based upon the Weibull distribution, which produces accurate results on a per instance recognition basis across different recognition problems. Experimental results are provided for two different face recognition algorithms, a fingerprint recognition algorithm, a SIFT-based object recognition system, and a content-based image retrieval system.