Reproduce “Storage capacity of perceptron with variable selection” on OpenResearch

About this paper

Yingying Xu, Masayuki Ohzeki, Yoshiyuki Kabashima

Researchers from the University of Helsinki, Tohoku University, and The University of Tokyo quantitatively analyzed the storage capacity of a perceptron with optimal variable selection, demonstrating that intelligent feature selection significantly increases the number of random patterns a perceptron can classify beyond classical bounds established by Cover-Gardner theory. This work provides a theoretical criterion to distinguish genuine data structure from spurious regularities in high-dimensional settings.

Key insights

• Optimal variable selection significantly enhances a perceptron's storage capacity beyond the classical Cover-Gardner capacity (\alpha_CG = 2\rho), enabling classification of more patterns per selected feature.
• For pattern loads below \alpha_CG, any arbitrary selection of variables suffices for classification, whereas for loads above \alpha_CG, an exponentially large number of specific 'atypical clusters' of optimal variable selections become necessary.
• The work provides a quantitative criterion (\alpha_VS) for discerning genuine data structure from spurious regularities, suggesting that classification of real data beyond this bound offers stronger evidence of meaningful information.

Summary by alphaXiv.