PaperlayerView exact revision on arXiv

Source-linked AI summary

The Extreme Value Machine

Ethan M. Rudd, Lalit P. Jain, Walter J. Scheirer, Terrance E. Boult

arXiv:1506.06112v4cs.LG

TL;DR

The paper addresses how to recognize and incrementally incorporate classes unseen during training without relying on impractical retraining or weak distributional assumptions. It introduces the Extreme Value Machine, an EVT-derived classifier using compact extreme-vector representations and kernel-free nonlinear modeling. On ImageNet, the EVM outperforms NNO in accuracy and F1-measure while reducing model size, though its current optimization lacks a parameter for balancing positive and negative soft-margin errors.

  • Problem

    Open-world recognition requires detecting and incorporating novel classes, but existing incremental methods can be computationally expensive or lack strong statistical characterization.

  • Method

    The EVM derives Ψ-models from EVT, represents classes with selected extreme vectors, and reduces the model using a greedy Set Cover approximation.

  • Results

    The EVM consistently and dramatically outperforms NNO in accuracy and F1-measure while significantly reducing model size over using all points.

  • Takeaways & Limitations

    The EVM provides kernel-free nonlinear classification with data-derived variable bandwidths and an incrementally updatable compact class representation.

  • Takeaways & Limitations

    The current Set Cover optimization lacks a parameter for adjusting the risk tradeoff between positive and negative classes.

Abstract

from arXiv · show

It is often desirable to be able to recognize when inputs to a recognition function learned in a supervised manner correspond to classes unseen at training time. With this ability, new class labels could be assigned to these inputs by a human operator, allowing them to be incorporated into the recognition function --- ideally under an efficient incremental update mechanism. While good algorithms that assume inputs from a fixed set of classes exist, e.g., artificial neural networks and kernel machines, it is not immediately obvious how to extend them to perform incremental learning in the presence of unknown query classes. Existing algorithms take little to no distributional information into account when learning recognition functions and lack a strong theoretical foundation. We address this gap by formulating a novel, theoretically sound classifier --- the Extreme Value Machine (EVM). The EVM has a well-grounded interpretation derived from statistical Extreme Value Theory (EVT), and is the first classifier to be able to perform nonlinear kernel-free variable bandwidth incremental learning. Compared to other classifiers in the same deep network derived feature space, the EVM is accurate and efficient on an established benchmark partition of the ImageNet dataset.

I. INTRODUCTION

The paper addresses open-world recognition, where classifiers must detect and incorporate novel classes without impractical retraining. It introduces the EVM as a compact, distribution-based model for efficiently updating nonlinear open-set decision boundaries.

  • Incremental recognition systems must incorporate novel classes as recognition problems evolve over time.
  • Periodic retraining can be impractical under time or resource constraints, while existing incremental methods may be computationally expensive or weakly grounded statistically.
  • Closed-set classifiers cannot reliably identify query-time unknown classes because they assume all queries are represented by the training classes.
  • Open-world recognition requires detecting unknowns, selecting and labeling points, and updating the model with new class information.
  • The EVM derives a compact representation of open-world decision boundaries from training-data distributions using statistical Extreme Value Theory.
  • EVM extreme vectors can be efficiently updated, with variable-bandwidth and skewed radial inclusion functions grounded in EVT rather than fixed kernel assumptions.

II. RELATED WORK

Related work includes open-set, novelty-detection, incremental, lifelong-learning, and EVT-based recognition methods. The EVM builds on these areas by deriving its inclusion model from EVT during training rather than applying EVT only after classification.

  • Open-world recognition extends open-set recognition by requiring unknown detection, point selection, labeling, and model updating for new classes.
  • Open-set recognition and novelty detection address unknown or outlier data, but incremental treatment of unknown samples remains less studied.
  • Prior EVT approaches calibrate decision boundaries post hoc, whereas the EVM derives its probability-of-inclusion function from EVT during training.
  • The EVM represents each class with extreme vectors and radial inclusion functions whose statistically guaranteed form follows from EVT under continuity and smoothness assumptions.
  • Margin-distribution methods can provide better error bounds than soft-margin SVMs, motivating the EVM’s use of margin distributions.

A. Probability of Sample Inclusion

The EVM models each sample’s distances to nearby negative points as a margin distribution and uses EVT to obtain a Weibull-based radial probability of sample inclusion. This yields sample-specific inclusion functions with parameters fitted from the smallest margins.

  • For a positive sample, margin estimates are half the distances to its τ closest samples from different classes.
  • The Fisher-Tippett theorem restricts limiting extreme-value distributions to the Gumbel, Fréchet, or reversed Weibull families.
  • Under the stated assumptions, the minimal values of the margin distances follow a Weibull distribution.
  • Each training point estimates its own distance-to-margin distribution, producing a sample-specific inclusion model.
  • The Ψ-model uses Weibull shape and scale parameters fitted to the smallest margin distances to define radial inclusion probability.
  • Using τ points allows the EVT model to retain a soft margin even though inclusion probability is designed to approach zero near the negative margin.

B. Decision Function

The decision function assigns a query to the known class with the largest estimated inclusion probability when that probability exceeds a threshold; otherwise it rejects the query as unknown. The threshold can be selected by cross-class validation.

  • The estimated probability for class C_l is the maximum Ψ value among its extreme vectors for query x′.
  • A query is assigned to the highest-probability known class when its probability meets threshold δ; otherwise it is labeled “unknown.”
  • Threshold δ can be selected by cross-class validation that trades off closed-set accuracy against rejection of unknown classes.

IV. EVM FORMULATION

The EVM constructs compact open-world decision boundaries from distributional models, then reduces each class representation by retaining extreme vectors that cover the training examples. This reduction supports scalable classification and incremental updates while treating outliers as late-added coverage candidates.

  • IV. EVM FORMULATION: The EVM uses Ψ-models to represent open-world decision boundaries while limiting trained model size and supporting favorable scaling characteristics.
  • A. Model Reduction: Keeping every Ψ-model increases model size and classification time as datasets grow, motivating strategic removal of redundant point-model pairs.
  • A. Model Reduction: The binary indicator I(x_i) marks whether a point-model pair is retained, with retained pairs becoming the EVM’s extreme vectors.
  • A. Model Reduction: Model reduction requires every point-model pair to be retained as an extreme vector or covered by at least one other retained pair.
  • A. Model Reduction: The reduction objective is a minimum Set Cover formulation over coverage sets, selecting as few retained pairs as possible while covering all class examples.
  • A. Model Reduction: Outliers are generally covered by points from other classes and therefore tend to enter the coverage set late, as a consequence of minimizing the number of covering points.

B. Incremental Learning

The EVM updates incrementally by refitting models for new data using existing extreme vectors and then reducing the combined set. On OLETTER, it matches W-SVM performance while using a substantially smaller representation and retaining favorable degradation as unknown classes increase.

  • B. Incremental Learning: New EVM batches are fit using current extreme vectors and new training points, after which model reduction selects the next set of extreme vectors.
  • B. Incremental Learning: On OLETTER, the EVM is comparable to W-SVM in F1-Measure while offering substantial training-efficiency and scalability savings.
  • B. Incremental Learning: The EVM’s vector ratio is an order of magnitude smaller than that of the SVM-based models in the OLETTER evaluation.
  • B. Incremental Learning: Both EVM and W-SVM retain favorable performance degradation as the proportion of unseen test classes increases, unlike the two other calibrated algorithms.
  • B. Incremental Learning: The OLETTER protocol trains on 15 randomly selected known Letter labels and incrementally tests with subsets of the remaining 11 unknown labels.
  • B. Incremental Learning: OLETTER results use F1-Measure and a dynamically set open-space threshold, with Euclidean distance defining EVM margins and vector ratio measuring model compactness.
  • B. Incremental Learning: The comparison includes W-SVM, nearest-neighbor CAP calibration, and one-versus-rest RBF SVMs with Platt probability estimation.

B. Open World Recognition on ImageNet

On open-world ImageNet, the EVM is evaluated through alternating recognition and class-update phases using deep AlexNet features. It consistently outperforms NNO in accuracy and F1-Measure, while incremental KDE is not scalable at the benchmark’s size.

  • B. Open World Recognition on ImageNet: The ImageNet open-world protocol alternates recognition and updates after initial training on 50 classes, adding new classes in groups of 50.
  • B. Open World Recognition on ImageNet: The benchmark tests 0, 50, 100, 150, and 200 unknown classes initially and at each subsequent class increment.
  • B. Open World Recognition on ImageNet: The experiments replace dense SIFT with a 4,096-dimensional AlexNet fc7 deep-feature representation.
  • B. Open World Recognition on ImageNet: The incremental KDE classifier enrolled fewer than 40 samples after 24 hours, implying approximately 18 years for the benchmark training experiment at a constant enrollment rate.
  • B. Open World Recognition on ImageNet: Euclidean distance performed poorly for EVM margins on deep features, so the ImageNet experiments used cosine similarity.
  • B. Open World Recognition on ImageNet: The EVM consistently and dramatically outperforms NNO in both accuracy and F1-Measure across the ImageNet open-world evaluation.
  • B. Open World Recognition on ImageNet: The EVM’s rejection behavior tightly bounds class hypotheses by their support while maintaining reasonable classification performance as classes are added.

VI. PRACTICAL CONSIDERATIONS FOR THE EVM

The EVM supports compact, efficient models through Set Cover reduction and budget-aware selection, while its main performance sensitivity lies in tail size τ. Practical constraints also expose limits in tail-size selection and metric compatibility.

  • Model reduction: Set Cover reduction selects representative extreme vectors to increase classification efficiency and compact the training representation.The reduction can be tuned to meet computational, storage, or time budgets.
  • Model reduction: 96% base accuracy on Letter remained comparable using 50% or 40% of training data, while 10% reduced accuracy to 92%.The results support budgeted optimization for classifier compression and portability.
  • Computational efficiency: Class-wise training can be parallelized, and each maximum-likelihood statistical fit has constant time complexity under a capped iteration count.Model reduction is O(N_l^2), while space partitioning can reduce tail retrieval from O(NlogN) to O(τlogN).
  • Parameter sensitivity: Performance variation is dominated by the single hyperparameter τ, while changes across ς and k typically account for less than 2% in accuracy or F1-measure.Searching k over {1, ..., 10} slightly improved test performance, with further decreases for k > 10.
  • Parameter sensitivity: EVT does not provide a principled way to select tail size τ, so the method uses cross-class validation.The selected ImageNet value, τ = 33998, was approximately half the training set, an unintuitive result attributed to high-dimensional boundary directions.

VII. CONCLUSION

The conclusion emphasizes that EVM provides kernel-free nonlinear classification whose functional form follows from EVT rather than an assumed kernel. Weibull fitting also gives robustness to a small number of mislabeled points or outliers, while Set Cover leaves a soft-margin tradeoff for future work.

  • VII. CONCLUSION: EVM performs nonlinear classification without a kernel, using variable Ψ-model parameters derived from bandwidth and data density.For κ = 2 the form matches a Gaussian RBF, for κ = 1 an exponential or Laplacian RBF, while κ > 2 is not a Mercer kernel.
  • VII. CONCLUSION: The Ψ-model’s functional form is obtained directly by applying EVT to input-space distance distributions, rather than assuming a kernel function.This avoids both an ad hoc kernel-trick assumption and a post hoc choice of kernel.
  • VII. CONCLUSION: Weibull fitting prevents a small number of mislabeled points or outliers from determining the estimated margin location.Including more distant points broadens the Ψ-model in scale or shape, providing a data-derived form of margin softness.
  • VII. CONCLUSION: Set Cover currently lacks a parameter for adjusting the risk tradeoff between positive- and negative-class errors.The paper identifies soft-margin parameterization and weighted optimization as future extensions.

The Extreme Value Machine – Supplemental Material

The supplemental algorithms train EVM class models, fit Ψ-models from nearest margins, and reduce models by selecting representative extreme vectors. Reduction can yield either a variable or fixed number of extreme vectors, with fixed-size reduction requiring more computation.

  • EVM training: EVM training iterates over classes, fitting a vector of Ψ-models for each class using the training data, labels, tailsize τ, and coverage threshold ς.The class-fitting loop can be parallelized, as can Ψ-model fitting and pairwise distance computations.
  • Ψ-model fitting: For each class, pairwise distances to other-class points are sorted, and maximum-likelihood Weibull fits are performed on the nearest τ margins.The resulting Weibull models are returned as Ψ_l.
  • Variable-size reduction: The Set Cover approximation greedily selects extreme vectors whose probability-based coverage sets cover all points, producing a non-predetermined number of extreme vectors.The coverage threshold ς determines whether a point is included in an extreme vector’s coverage set.
  • Fixed-size reduction: Fixed-size reduction bisects ς until the output approaches a target Nmax extreme vectors, then returns the Nmax highest-coverage vectors.The tolerance δP controls termination of the bisection search.
  • Computational trade-off: Using Vector Ratio as a hyperparameter is possible through fixed-size reduction, but it increases computational cost because the reduction routine must be called repeatedly.The consequences of this choice are left for future work.

2 Parameter Distributions

The supplemental analysis examines Ψ-model parameter distributions across ImageNet and Letter. Scale parameters behave similarly across datasets, whereas shape parameters vary substantially and lack an obvious principled fixed choice.

  • Scope: The parameter-distribution analysis is presented as a preliminary exploration rather than a completed formulation of a more efficient fitting strategy.The broader question of avoiding fits or improving parameter initialization remains beyond the main text’s scope.
  • Scale parameters: Scale parameters were very close to one for both ImageNet and Letter, despite differences in dataset characteristics, dimensionality, and margin metrics.The authors associate the similar mean scale with normalized input data but note the broader similarity of the distributions.
  • Shape parameters: Shape parameter distributions span a much wider range and look dissimilar between ImageNet and Letter, making a principled choice of κ unclear.Testing κ = 1 and κ = 2 on OLETTER produced very poor open set recognition performance.

3 EVM-SVM Analogy

The EVM resembles an SVM in using radial functions and selected representative vectors, but its probabilistic EVT-based objective differs fundamentally from SVM margin optimization. Its parameters therefore do not have equivalent meanings.

  • Kernel analogy: EVM Ψ-models are kernel-like radial basis functions, but values of κ > 2 violate Mercer-kernel interpretation, so the EVM is not a kernel machine.The cited parameter distributions indicate that κ > 2 occurs frequently.
  • Optimization objectives: EVMs select the smallest number of extreme vectors covering each class at a chosen probability, whereas SVMs select support vectors to maximize soft margin.SVM support vectors primarily encode decision-boundary structure, while EVMs encode class-wide inclusion probabilities.
  • Hyperparameters: ς controls EVM model size through the number of extreme vectors, unlike SVM C, which controls margin softness; τ is a closer but still imperfect analogy to C.Model size depends on both τ and ς because larger τ values increase coverage and can reduce the number of selected extreme vectors.
  • Comparison with W-SVM: Unlike W-SVM, which applies EVT post hoc to SVM scores, the EVM fits EVT models directly during optimization in feature space.W-SVM combines one-class and multiclass SVM models before score-level EVT fitting.
Loading 1506.06112v4…