Learning Boolean functions with concentrated spectra

Dustin G. Mixon; Jesse Peterson

doi:10.1117/12.2189112

24 August 2015 Learning Boolean functions with concentrated spectra

Dustin G. Mixon, Jesse Peterson

Proceedings Volume 9597, Wavelets and Sparsity XVI; 95970C (2015) https://doi.org/10.1117/12.2189112
Event: SPIE Optical Engineering + Applications, 2015, San Diego, California, United States

Abstract

This paper discusses the theory and application of learning Boolean functions that are concentrated in the Fourier domain. We first estimate the VC dimension of this function class in order to establish a small sample complexity of learning in this case. Next, we propose a computationally efficient method of empirical risk minimization, and we apply this method to the MNIST database of handwritten digits. These results demonstrate the effectiveness of our model for modern classification tasks. We conclude with a list of open problems for future investigation.

Citation Download Citation

Dustin G. Mixon and Jesse Peterson "Learning Boolean functions with concentrated spectra", Proc. SPIE 9597, Wavelets and Sparsity XVI, 95970C (24 August 2015); https://doi.org/10.1117/12.2189112

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available