PaperlayerView exact revision on arXiv

Source-linked AI summary

Sparse Representation-based Open Set Recognition

He Zhang, Vishal M. Patel

arXiv:1705.02431v1cs.CV

TL;DR

Open set recognition must classify known classes while rejecting test samples from unseen classes, whereas standard SRC assumes a closed world. SROSR models matched and non-matched reconstruction-error tails with EVT and fuses confidence scores; experiments across image and object datasets show significantly better performance than many competitive methods.

  • Problem

    Open set recognition requires classifying known classes and rejecting samples from classes not seen during training, unlike SRC's closed-world assumption.

  • Method

    SROSR models the tails of matched and summed non-matched reconstruction-error distributions with EVT, formulates hypothesis tests, and fuses confidence scores.

  • Results

    Experiments on four publicly available image and object classification datasets show significantly better performance than many competitive open set recognition algorithms.

  • Takeaways & Limitations

    The method extends SRC for open set recognition by using EVT-modeled reconstruction-error distributions rather than closed-world classification alone.

  • Takeaways & Limitations

    SROSR can fail when extreme pose, illumination, or resolution variation violates SRC's self-expressiveness property, and it requires an extensive training set.

Abstract

from arXiv · show

We propose a generalized Sparse Representation- based Classification (SRC) algorithm for open set recognition where not all classes presented during testing are known during training. The SRC algorithm uses class reconstruction errors for classification. As most of the discriminative information for open set recognition is hidden in the tail part of the matched and sum of non-matched reconstruction error distributions, we model the tail of those two error distributions using the statistical Extreme Value Theory (EVT). Then we simplify the open set recognition problem into a set of hypothesis testing problems. The confidence scores corresponding to the tail distributions of a novel test sample are then fused to determine its identity. The effectiveness of the proposed method is demonstrated using four publicly available image and object classification datasets and it is shown that this method can perform significantly better than many competitive open set recognition algorithms. Code is public available: https://github.com/hezhangsprinter/SROSR

I. INTRODUCTION

The paper frames open set recognition as extending SRC beyond its closed-world assumption so known classes are classified while unseen classes are rejected. It proposes SROSR, which models reconstruction-error tails with EVT and fuses confidence scores for recognition.

  • Motivation: Standard SRC assumes every test sample belongs to one of the K training classes, limiting its use for open set recognition.SRC identifies classes through sparse representations of test samples using training data.
  • Motivation: Open set recognition requires classifying known samples while rejecting samples from classes absent during training.This combines classification with novelty detection.
  • Related Rejection Rules: SCI-based and projection-ratio rejection rules were designed for non-face rejection and do not work well on general open set recognition problems.The paper motivates using both matched and non-matched reconstruction errors instead.
  • Proposed Method: SROSR models the tails of matched and summed non-matched reconstruction-error distributions using EVT, converting recognition into two hypothesis tests.The matched error corresponds to a candidate class, while the summed non-matched error captures the remaining classes.
  • Proposed Method: For a novel test sample, SROSR computes confidence scores from both modeled tails and fuses them to determine the sample's identity.The method extends SRC by adding a training stage based on reconstruction-error distributions.
  • Sparse Representation-based Classification: SRC classifies a test sample by selecting the class with the smallest class-specific reconstruction error.The class residual is r_k = ∥y_t − Y_k x̂_k∥_2.

B. Extreme Value Theory

Extreme Value Theory models distributions of unusually high or low observations. The paper reviews GEV and threshold-exceedance modeling, while noting practical estimation issues for some parameter values.

  • EVT Background: Extreme Value Theory analyzes the distribution of abnormally high or low data values.The paper notes applications in finance, hydrology, and novelty detection.
  • Extreme-Value Limits: The Fisher-Tippett-Gnedenko theorem links normalized extremes to a non-degenerate distribution from the Fréchet, Weibull, or Gumbel families.These families can be represented using the Generalized Extreme Value distribution.
  • GEV Model: The GEV distribution uses location, scaling, and shape parameters, denoted by µ, σ, and ξ.The scale parameter is constrained to σ > 0.
  • Threshold Exceedances: Threshold-exceedance probabilities above a sufficiently large threshold can be approximated with a generalized Pareto distribution.The approximation is expressed for observations exceeding threshold u by z.
  • Modeling Challenges: Using GEV requires selecting a distribution family and segmenting data so maxima from each segment can be modeled.The paper identifies both choices as challenges before applying GEV tail modeling.
  • Estimation Caveat: Maximum-likelihood estimation may fail to converge or parameters may not exist when ξ > 1/2, although the paper describes these cases as extremely rare in practice.This caveat concerns estimation of generalized Pareto distribution parameters.

III. SPARSE REPRESENTATION-BASED OPEN-SET RECOGNITION (SROSR)

SROSR extends SRC to open set recognition by modeling the tails of matched and summed non-matched reconstruction-error distributions with EVT. It converts recognition into hypothesis tests and fuses tail-based confidence scores to identify or reject samples.

  • Motivation: SRC residuals distinguish a test sample’s matched class from non-matched classes because the correct class should have much lower reconstruction error.This creates separate matched and non-matched error distributions for open set recognition.
  • Matched-error testing: SROSR models the right tail of matched errors with a GPD because the underlying matched-error distribution is unknown.The tail is sufficient for the rejection hypothesis test described in the method.
  • Illustrations: Fig. 2 compares matched digit-9 reconstruction errors with non-matched errors generated by the other digits on MNIST.Training uses digits 0 to 9, while the test samples correspond to digit 9.
  • Non-matched-error testing: The method formulates a second hypothesis test using the sum of non-matched reconstruction errors and combines it with the matched-error test.The two tests use the informative tails of the respective distributions.

A. Training

SROSR training repeatedly partitions each class’s samples into cross-train and cross-test sets, runs SRC, and collects matched and summed non-matched errors. GPD parameters are then fitted to these collected tails.

  • Partitioning: Each training class is randomly ordered and partitioned into cross-train and cross-test sets during every iteration.The cross-train and cross-test sets contain 80% and 20% of each class’s training samples, respectively.
  • Error collection: The training procedure repeats this cross-partitioning and SRC evaluation for L iterations before fitting the distributions.The tail size is represented by ρ.
  • Partitioning: The cross-train samples and labels from all K classes are combined into global cross-train matrices and label sets.The corresponding cross-test samples and labels are combined similarly.
  • Error collection: Repeated SRC runs produce matched-error sets and summed non-matched-error sets for every class.These sets provide the samples used to fit the tail distributions.
  • Distribution fitting: Algorithm 2 outputs GPD scale and shape parameters for matched errors and for the negated summed non-matched errors.The fitted parameters are denoted σm, ξm, σnm, and ξnm.

B. Testing

During testing, SROSR computes SRC reconstruction errors, selects the minimum-error candidate class, and evaluates matched and summed non-matched tail scores. Their weighted combination determines whether to assign that class or reject the sample as open.

  • Score computation: For a novel sample, SROSR solves the SRC problem and computes K reconstruction errors before selecting the minimum-error candidate class.The candidate class is the class with the smallest reconstruction error.
  • Score computation: The matched candidate error and the sum of all non-matched errors are transformed into probability scores using their corresponding GPDs.The two raw reconstruction errors are normalized into probabilities.
  • Score fusion: The non-matched score’s weight decreases as openness grows and more unknown classes appear during testing.Openness equals zero in the completely closed classification setting.
  • Decision: The testing output is either one of the known classes {1, 2, …, K} or O, where O denotes the open class.Testing uses the learned matched and summed non-matched distribution parameters, threshold δt, and weight w.

IV. EXPERIMENTAL RESULTS

The experiments evaluate SROSR for open set recognition on four image and object datasets against established methods, using recognition accuracy and F-measure. The testing procedure uses empirically selected thresholds and cross-validated tail sizes.

  • Datasets and comparisons: SROSR is evaluated on MNIST, Extended YaleB, UIUC attribute, and Caltech-256 datasets.The experiments compare the method with existing open set recognition algorithms, including W-SVM as a benchmark.
  • Metrics: Recognition accuracy and F-measure are the reported performance measures for open set recognition.F-measure is defined as the harmonic mean of precision and recall.
  • Metrics: Precision is TP/(TP+FP), while recall is TP/(TP+FN).TP, FN, and FP denote true positive, false negative, and false positive, respectively.
  • Experimental settings: The rejection threshold δt is empirically set to 0.006·(1+w), 0.007·(1+w), 0.05·(1+w), and 0.1·(1+w) for MNIST, Extended YaleB, UIUC, and Caltech-256, respectively.The tail size ρ is selected by cross-validation.
  • Experimental settings: The tail sizes are ρ = 0.14, 0.10, 0.39, and 0.25 for MNIST, Extended YaleB, UIUC, and Caltech-256, respectively.The SRC noise level is set to ϵ = 0.001.

A. Results on the Extended YaleB Dataset

On Extended Yale B, the study evaluates open set recognition across varying openness and finds that combining matched and non-matched reconstruction-error distributions improves SROSR performance.

  • Experimental setup: The experiment selects 10 of 38 classes for training, uses the remaining classes as open-set data, and averages results over 50 repetitions.Each selected training class contributes 80% of its samples for training; the remaining 20% and all other classes form the test set.
  • Performance: SROSR outperforms the other compared methods on both F-measure and accuracy as openness varies.The face images are cropped, aligned, and captured against nearly identical backgrounds, producing high F-measures for all methods.
  • Ablation: Using only the matched reconstruction-error distribution significantly degrades performance, whereas fusing matched and summed non-matched errors greatly enhances SROSR.The experiment directly tests the contribution of the summed non-matched reconstruction-error distribution.

B. Results on the MNIST Dataset

On MNIST, the evaluation varies openness by holding out digit classes and shows that SROSR achieves the strongest F-measure and accuracy among the compared methods. The results also indicate that performance trends depend on the relative recognition and rejection accuracies of the dataset.

  • Experimental setup: Six of MNIST’s 10 digit classes are used for training, while openness varies across the remaining four classes over 50 repetitions.The study reports average F-measure and accuracy and plots both against openness.
  • Performance: SROSR achieves the highest F-measure and accuracy among the five methods as openness varies.It performs better than the Naive, W-SVM, SCI, and Ratio methods.
  • Interpretation: SROSR’s advantage comes from incorporating both matched and non-matched reconstruction errors rather than relying only on sparsity-based rejection.SCI may fail to reject an open-set sample when its sparsity pattern resembles that of a training sample.
  • Dataset-dependent trend: Accuracy increases with openness on Extended Yale B but decreases with openness on MNIST because rejection accuracy differs relative to recognition accuracy across the datasets.Rejection accuracy exceeds recognition accuracy on Extended Yale B, whereas the reverse holds on MNIST.

C. Results on the UIUC Attribute Dataset

On the UIUC attribute dataset, the experiment trains on a-Pascal classes and varies openness using a-Yahoo classes. SROSR outperforms the other methods, especially as openness increases.

  • Experimental setup: The experiment trains on 10 a-Pascal classes and varies openness by selecting 1 to 10 a-Yahoo classes as open-set classes.It uses 50 samples per training class, 20 per testing class, and averages results over 50 repetitions.
  • Performance: SROSR outperforms the other methods on the UIUC attribute dataset.Results are reported using F-measure and accuracy as openness varies.
  • Performance: As openness increases, SROSR achieves much better F-measure and accuracy than the compared methods.The reported comparison covers both evaluation measures.

D. Results on the Caltech-256 Dataset

On Caltech-256, SROSR achieves the best average F-measure and accuracy among the compared open set recognition methods while openness varies from 24.94% to 29.29%.

  • Experimental setup: The experiment uses 20 training categories and varies openness by selecting 31 to 40 of the other 237 categories.It samples 50 images per training class and 20 per testing class, averages results over 50 trials, and uses spatial pyramid features.
  • Experimental setup: 24.94% to 29.29%: the experiment’s openness range on Caltech-256.Caltech-256 contains 257 categories, including one background clutter class.
  • Performance: SROSR achieves the best F-measure and accuracy results compared with the other competitive open set recognition methods.The result is reported across the plotted openness conditions.

V. CONCLUSION

The paper adapts SRC for open set recognition by modeling reconstruction-error distributions with EVT and reports stronger performance than competitive methods. Its applicability is limited when data violate SRC’s self-expressiveness assumption or training coverage is insufficient.

  • Conclusion: The proposed training stage adapts SRC to open set recognition problems.It uses reconstruction-error distributions modeled by EVT.
  • Conclusion: Results on Caltech 256 report openness against both F-Measure and Accuracy.Figure 7 presents the two evaluation views in separate panels.
  • Conclusion: EVT models the tail distributions of matched and non-matched reconstruction errors for open set recognition.These models support hypothesis testing and confidence-score fusion for identity determination.
  • Conclusion: The method performs significantly better than many competitive open set recognition algorithms across image and object classification datasets.The reported conclusion is based on various experiments on popular datasets.
  • Conclusion: SROSR fails when extreme pose, illumination, or resolution variations invalidate SRC’s self-expressiveness property.The authors also require an extensive training set spanning conditions likely to occur at test time.
Loading 1705.02431v1…