Random Projection, Margins, Kernels, and Feature-Selection

By Avrim Blum. 2005

134 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Statistical Learning Theory

Citations in the corpus

Kernel Mean Embedding of Distributions: A Review and Beyonds (2016, background): “If elements of W are drawn from an appropriate distribution p(w), the Johnson-Lindenstrauss Lemma (Dasgupta and Gupta 2003, Blum 2005) ensures that this transformation will preserve similarity between data points.”
Simple and Principled Uncertainty Estimation with Deterministic Deep Learning via Distance Awareness (2020, background): “Finally, it is worth noting that preserving such approximate isometry in a neural network is possible even after significant dimensionality reduction (Blum, 2006; Hauser and Ray, 2017; Perrault-Joncas, 2017; Rousseau et al., 2020).”
FastMMD: Ensemble of Circular Discrepancy for Efficient Two-Sample Test (2014, methodology): “In this section, we give a geometric explanation for our methods by using random projection (Blum, 2006) on a circle and circular discrepancy.”
Stronger generalization bounds for deep nets via a compression approach (2018, methodology): “Similar approach was discussed by Blum [2006] for linear classiﬁers.”
Top Accuracy and Fast Dependency Parsing is not a Contradiction (2010, methodology): “This procedure is similar to randomization of weights (features), which aims to save space by sharing values in the weight vector (Blum., 2006; Rahimi and Recht, 2008).”
Compressed Least-Squares Regression (2009, background): “In [6, 17], the authors show how to map a kernel k(x, y) = φ(x) · φ(y) into a low-dimensional space, while still approximately preserving the inner products.”
Adaptive Affinity Field for Semantic Segmentation (2018, background): “One example of projections is the random projection [29].”
Robust Domain Generalisation by Enforcing Distribution Invariance (2016, methodology): “A more recent trend explores the use of randomisation, such as linear random projection [Blum, 2006] as a substitute for the computationally expensive step of kernel matrix construction.”
Improper Deep Kernels (2016, unknown): “Consider for example, Theorem 5 in [3].”
TRAK: Attributing Model Behavior at Scale (2023, unknown): “Our application of random projections to improve computational efficiency of kernel approximation is a widely used idea in kernel methods (Blum, 2006; Rahimi & Recht, 2007).”
Compact Random Feature Maps (2013, background): “To solve this challenge, several schemes have been proposed to explicitly approximate the kernel matrix, including low-rank approximations (Blum, 2006) (Bach & Jordan, 2005), sampling individual entries (Achliop-tas et al., 2002), or discarding entire rows (Drineas & Mahoney, 2005).”
Bayesian Nonparametric Kernel-Learning (2015, methodology): “Other approaches for summarizing the Gram matrix by the removal of elements or rows have been explored in [21, 5, 9, 22].”