PaperlayerView exact revision on arXiv

Source-linked AI summary

Random-projection ensemble classification

Timothy I. Cannings, Richard J. Samworth

arXiv:1504.04595v2stat.ME

TL;DR

High-dimensional classification is challenging when p is comparable to or larger than n, motivating methods that avoid dependence on the original dimension. This paper builds an ensemble from arbitrary base classifiers applied to selected low-dimensional random projections, with data-driven voting and theoretical risk analysis. Under a sufficient-dimension-reduction-related condition, the risk is controlled by projected-data performance and a term that vanishes with more projections, while experiments show strong finite-sample performance.

  • Problem

    High-dimensional settings can make classical classifiers perform poorly or become intractable when p is comparable to or larger than n.

  • Method

    The method applies an arbitrary base classifier to random low-dimensional projections, selects low-estimated-error projections within groups, and aggregates them using a data-driven voting threshold.

  • Results

    An RP ensemble attains the lowest misclassification error in 23 of 36 simulated and real-data settings and ranks in the top three in 8 of the 13 remaining cases.

  • Takeaways & Limitations

    The framework is flexible across base classifiers and achieves encouraging finite-sample performance across varied high-dimensional classification settings.

  • Takeaways & Limitations

    The theoretical boundary condition requires that the Bayes decision rule depend on a d-dimensional projection, as implied by sufficient dimension reduction.

Abstract

from arXiv · show

We introduce a very general method for high-dimensional classification, based on careful combination of the results of applying an arbitrary base classifier to random projections of the feature vectors into a lower-dimensional space. In one special case that we study in detail, the random projections are divided into disjoint groups, and within each group we select the projection yielding the smallest estimate of the test error. Our random projection ensemble classifier then aggregates the results of applying the base classifier on the selected projections, with a data-driven voting threshold to determine the final assignment. Our theoretical results elucidate the effect on performance of increasing the number of projections. Moreover, under a boundary condition implied by the sufficient dimension reduction assumption, we show that the test excess risk of the random projection ensemble classifier can be controlled by terms that do not depend on the original data dimension and a term that becomes negligible as the number of projections increases. The classifier is also compared empirically with several other popular high-dimensional classifiers via an extensive simulation study, which reveals its excellent finite-sample performance.

1. Introduction

High-dimensional classification becomes difficult when feature dimension rivals or exceeds sample size. The paper addresses this by combining carefully selected low-dimensional random projections with flexible base classifiers and aggregation.

  • When p ≥ n, classical classifiers such as LDA may perform poorly because the sample covariance matrix is not invertible.
  • Random projections reduce the working dimension while preserving relevant geometric information under Johnson–Lindenstrauss-type conditions.The lower bound on projected dimension does not depend on the original dimension p.
  • Aggregating all random projections can be ineffective because many projections destroy class structure.The method therefore selects the lowest-estimated-error projection within each disjoint group.
  • The ensemble combines selected projections through aggregation and a data-driven voting threshold rather than a necessarily optimal simple majority vote.
  • The theory analyzes generic projection ensembles, selected Haar projections, sufficient-dimension-reduction conditions, and specific LDA and k-nearest-neighbour base classifiers.The resulting bounds include terms depending on projected dimension rather than the original data dimension, plus a term that vanishes as the number of projections increases.
  • Extensive simulated and real-data comparisons suggest excellent finite-sample performance across varied high-dimensional classification settings.

2. A generic random projection ensemble classifier

The generic ensemble applies an arbitrary base classifier to independently generated low-dimensional projections, aggregates their outputs at a chosen threshold, and analyzes how projection count affects risk. The theory connects finite ensembles to an infinite-simulation classifier and controls excess risk under broad conditions.

  • A classifier trained on projected data depends on each feature vector only through its d-dimensional projection.
  • The generic ensemble uses B1 independent random projections and leaves their distribution unspecified because the proposed method can choose it using the training data.
  • The ensemble assigns a class using a voting threshold α, which need not be fixed at 1/2.
  • Under smoothness of the class-conditional voting distributions at α, the expected test error is asymptotically approximated by the infinite-simulation ensemble's test error.
  • A numerical example reports rapidly stabilizing Monte Carlo error as B1 increases, consistent with the theoretical projection-count analysis.The experiment varies B1 from 2 to 500 using LDA, QDA, and k-nearest neighbours with B2 = 50.
  • The excess-risk bound compares the ensemble with a single-random-projection classifier and requires no assumptions on the training configuration, test distribution, or individual projection distribution.

3. Choosing good random projections

The paper selects promising random projections by screening independent candidates within disjoint groups, then aggregates classifiers trained on the selected projections. Under sufficient dimension reduction and an overfitting-control condition, the resulting excess-risk bound separates projection quality, estimation, and finite-projection effects.

  • Projection screening: The special-case classifier screens random projections by estimating each projected classifier’s test error and retaining the lowest-error projection within each group.The groups contain independent Haar-distributed projections, and the selected projection is defined using the smallest-index tie break.
  • Projection screening: The selected projections are used as independent inputs to the random projection ensemble classifier.After selection, the method constructs the ensemble from the retained projections A1, ..., AB1.
  • Screening assumption: The screening analysis assumes a positive chance that a projection selected from each group is within |εn| of the optimal projected test-error value.Here εn depends on the number of screened candidates and can be interpreted as an overfitting measure.
  • Risk control: Theorem 3 bounds ensemble test excess risk using the excess risk of a d-dimensional projected classifier, an error-estimation term, and a term depending on the number of projections.The result holds for every pair of projection counts B1 and B2 and every base classifier in the considered class.
  • Risk control: The finite-projection term can become negligible as B2 increases, but εn may increase because screening more candidates can increase overfitting.The first two terms can be bounded independently of the original dimension p under suitable conditions on the base classifier.
  • Dimension reduction condition: Sufficient dimension reduction implies the boundary condition that the Bayes class-1 region depends only on a d-dimensional projection.The paper states that conditional independence of Y and X given A*X implies this assumption, supporting projected classifiers that can approach Bayes risk.

4. Possible choices of the base classifier

The paper develops theoretical guarantees for random-projection ensembles using several base classifiers, including LDA, QDA, k-nearest neighbours, and sample splitting. The bounds can avoid dependence on the original dimension p, but their assumptions and rates vary by classifier.

  • Linear Discriminant Analysis: LDA can serve as the projected base classifier when d<n, even though direct LDA fails for p≥n because the sample covariance matrix is singular.Under the Gaussian model, the paper derives excess-risk bounds for projected LDA.
  • Linear Discriminant Analysis: The LDA bounds do not depend on the original data dimension p, but increasing B2 trades a higher chance of selecting a good projection against possible overfitting.The overfitting penalty is reflected in the bound associated with projection selection.
  • Quadratic Discriminant Analysis: QDA can be used after projection when d<min(n0,n1), but analogous theoretical results are unavailable because its risk lacks a closed form.The paper instead uses leave-one-out error estimates and reports strong practical performance in simulations.
  • The k-nearest neighbour classifier: For k-nearest neighbours, projection-based bounds avoid dependence on p, while the unprojected method has a high-dimensional curse-of-dimensionality rate O(n−4/(p+4)).Under regularity conditions, the projected classifier has excess risk O(n−4/(d+4)).
  • Sample splitting: Sample splitting yields bounds for any base classifier, typically sharper through Hoeffding’s inequality but with a larger first term because of reduced effective sample size.These guarantees require no assumptions on the data-generating mechanism.

5. Practical considerations

The method selects projections using estimated test error, aggregates the selected classifiers, and tunes the voting threshold from the data. Practical performance depends on projection counts and dimension, but the authors report robust defaults and threshold estimation that works even for small samples.

  • Projection selection: The classifier evaluates B1B2 projected base classifiers and uses the B1 projections with the smallest within-block error estimates for prediction.This implements selection from disjoint projection groups before aggregation.
  • Computational cost: Haar-distributed projections cost O(pd^2) operations to generate, while Gaussian projection matrices provide an approximately orthonormal lower-cost alternative for large p.For affine-invariant base classifiers such as LDA and QDA, the alternative gives the same relevant result.
  • Voting threshold: For QDA, the estimated voting-threshold objective improves as n increases, while the estimated threshold remains an excellent estimator of the oracle threshold even for small samples.It can substantially improve on α̂=1/2, which may assign every point to one class.
  • Number of projections: The authors recommend B1=500 and B2=50 as sensible defaults after finding the ensemble robust to their choice.These values were used in the reported experiments.
  • Projected dimension: The projected dimension d should be small for tighter bounds and lower cost, but large enough for the sufficient-dimension condition to hold approximately.The method is reported to be robust to the choice of d, with cross-validation available when needed.

6. Empirical analysis

The empirical study evaluates random-projection ensembles across simulated and real high-dimensional classification settings. The method performs strongly across diverse distributions, while sparse data can undermine standard random projections.

  • Experimental design: The experiments use LDA, QDA, and k-nearest-neighbour base classifiers within random-projection ensembles, alongside original-space and state-of-the-art competitors.The simulations vary n, p, and class prior probabilities, using Gaussian projections with B1 = 500 and B2 = 50.
  • Simulated models: In Model 1, the RP-QDA ensemble performs very well, whereas sparse-classification comparators can be no better than random guessing.The sufficient-dimension-reduction condition holds with d = 2 in this model.
  • Simulated models: In Model 2, RP ensembles classify well with projection dimensions d = 2 and d = 5, although the sufficient-dimension-reduction condition holds with d = 3.This indicates good performance despite using projection dimensions below or above the condition’s dimension.
  • Simulated models: In Model 3, RP-QDA5 has the smallest misclassification rate among implemented methods and handles nonlinear class boundaries better than RP-LDA.The sufficient-dimension-reduction condition is not satisfied for any d < p in this model.
  • Simulated models: In Model 4, RP-knn performs very well, while RP-LDA and RP-QDA are less effective because heavy-tailed distributions make mean and covariance estimates poor.The model includes heavy tails and feature correlation, with no finite second and first moments for the relevant class-conditional distributions.
  • Overall findings: Across 36 simulated and real-data settings, an RP ensemble has the lowest misclassification error in 23 and ranks among the top three in 8 of the remaining 13.The framework’s ability to use any base classifier supports adaptation across varied problems, but Gaussian or Haar projections are ineffective for very sparse Gisette data.

7. Discussion and extensions

The discussion presents random-projection ensembles as a flexible framework with extensions to multiclass problems, alternative projection designs, and variable-importance analysis. It also identifies computational and interpretability boundaries.

  • Framework: The framework combines base-classifier outputs from selected low-dimensional random projections and can be used with any base classifier.The paper studies one aggregation scheme in detail because it facilitates rigorous statistical analysis.
  • Multiclass extension: For K > 2 classes, the main extension challenge is defining the multiclass analogue of the classification rule and its voting threshold.The proposed multiclass formulation uses class-specific positive weights and chooses the smallest maximizer in ties.
  • Alternative projections: In ultrahigh dimensions, generating enough random projections to explore the projection space adequately may be too time-consuming.The paper discusses exhaustive searches over axis-aligned projections as one possible alternative when the projected dimension is small.
  • Alternative projections: Obtaining theory for axis-aligned projections requires an axis-aligned sufficient-dimension-reduction projection, which is a much stronger assumption.The discussion suggests that greater structural assumptions may be unavoidable in such settings.
  • Interpretability: The selected projections provide weights indicating relative variable importance, but the paper focuses on classification performance rather than interpretability.Understanding the induced variable ranking is proposed as a direction for future work.
  • Interpretation: Random projections can be viewed as perturbations of the data, with effects recurring across perturbations interpreted as stable effects sought by statisticians.This connects the framework conceptually to subsampling and bootstrap-based stability ideas.

8. Appendix

The appendix supplies technical proofs for the classifier’s risk results and supporting approximation results. Its arguments use fixed training data, independent projections, conditional binomial structure, and Edgeworth expansions.

  • Proof setup: The proof framework fixes the training data while treating the random projections as independent and identically distributed, independently of the test pair.This setup yields a representation of the ensemble classifier’s test error.
  • Probabilistic analysis: The appendix applies conditional binomial calculations because projection-level classification indicators are independent Bernoulli variables given the ensemble’s conditional success probability.This structure underlies the analysis of the voting procedure.
  • Approximation: Proposition 3 uniformly bounds the error of a one-term Edgeworth expansion for the relevant binomial distribution function.The theorem is then used to control the dominant contribution to the risk integral as the number of projections grows.
  • Proof strategy: The technical proof decomposes the relevant integrals into dominant regions and remainder terms, which are controlled using continuity, differentiability, Taylor expansions, and mean-value arguments.The appendix tracks these terms as the projection count B1 tends to infinity.
  • Theoretical consequences: The appendix establishes the stated results by combining the intermediate bounds with assumptions governing the projection-induced distributions and risk expressions.Several propositions connect the sufficient-dimension-reduction condition to the conditional distribution of X given A*X.

Random-projection ensemble classification: supplementary material

The supplementary material is identified as a companion to the main text by Cannings and Samworth (2017).

  • Supplementary material: The supplementary material provides additional technical content for the main paper.It is explicitly described as the supplementary material for Cannings and Samworth (2017).

9. A bound on the Monte Carlo variance of R(CRP

This section establishes a bound on the asymptotic Monte Carlo variance of the random projection ensemble risk, complementing the corresponding expectation result. The proof proceeds under Assumption 1 using binomial approximations, Taylor expansion, and differentiability arguments.

  • The variance result complements the paper’s preceding theorem on the Monte Carlo expectation of R(CRP_n).
  • Proposition 4 bounds the asymptotic Monte Carlo variance of R(CRP_n) under Assumption 1.
  • The proof treats the training data as fixed and decomposes the variance through pairwise probabilities involving ν_n(x) and ν_n(x′).
  • The argument controls binomial approximation terms for large B1 and applies Taylor expansion around ζ = α.
  • Continuous differentiability of G_n,r at α supplies a uniform approximation over θ′ ∈ [α − ϵ1, α + ϵ1].

10. Further discussion of assumptions

The paper empirically examines assumptions governing the ensemble’s theoretical results and estimates how Monte Carlo error and projection-selection behavior vary across classifiers and dimensions. The reported simulations support the practical choices of B1 = 500, B2 = 50, and low projected dimension.

  • The empirical section investigates Assumptions 1 and 2, which depend on the configuration of the training data pairs.
  • Assumption 1: For p = 100, γ_n(α̂) is bounded by 1 with high probability, making the test-error approximation within 0.002 of the infinite-simulation ensemble.
  • Assumption 1: For p = 1000, γ_n(α̂) is at most 8 with high probability, so γ_n(α̂)/500 < 0.02.
  • Assumption 2: With n = 50, d = 5, B1 = 500, B2 = 50, and B3 = 1000, Assumption 2 holds with β > 3/10 for LDA and β > 0.05 with high probability for QDA and knn.
  • Assumption 2: Although the theoretical bound suggests choosing B2 slightly above 50, experiments found B2 = 50 sufficient, with little gained by increasing it further.

11. Choice of B1 and B2

The supplementary analysis studies how the ensemble’s risk changes with the numbers of projection groups and projections per group. Risk decreases as both B1 and B2 increase, with B1 having the larger effect.

  • Risk decreases as B1 and B2 increase for LDA, QDA, and knn base classifiers.
  • Increasing B1 has a greater effect on risk than increasing B2, motivating the practical emphasis on B1.

12. Further simulation results

The remaining simulations examine additional prior-probability and high-dimensional settings. Results for unbalanced priors and p = 1000 remain consistent with the main text’s conclusions across projected dimensions d = 5 and d = 10.

  • Tables 7 and 8 evaluate unbalanced class priors with π1 = 0.66.
  • Tables 9 and 10 evaluate p = 1000 with projections into d = 5 or d = 10 dimensions.
  • These additional results are consistent with the conclusions reported in Section 6.3 of the main text.

13. Computational timings

The random projection ensemble classifier can be computationally accelerated through parallel processing and scales moderately with both sample size and feature dimension.

  • Parallelization: Parallel computing can significantly speed up the random projection ensemble classifier.The authors discuss incorporating multiple processors and report average run times as processor count varies.
  • Experimental setup: The reported timing comparisons use B1 = 500 and B2 = 50 for the ensemble, with parallelized code on four-CPU machines.Comparator timings use one such machine, although some comparator methods could also be parallelized.
  • Scaling: The classifier is typically slower for small sample sizes and dimensions but scales well as n and p increase.This comparison concerns the alternative methods evaluated on Model 2.
  • Scaling: When n increases from 50 to 1000 with p = 100, LDA and QDA computational cost increases by about a factor of 3.
  • Scaling: When n = 200 and p increases from 100 to 1000, runtime increases by a factor of less than 5.
Loading 1504.04595v2…