Fourier analysis in machine learning

An ICML/COLT '97 Tutorial

Since Linial, Mansour, and Nisan introduced the use of discrete Fourier analysis in machine learning in 1989, it has been a powerful tool for proving both positive and negative theoretical learnability results and has also helped to spawn fruitful applied machine learning research. In fact, to understand some of the strongest known results on the well-studied question of DNF learnability, at least some familiarity with Fourier analysis is required. Several other well-known learning-theoretic results also rely on this technique, such as the Kushilevitz-Mansour algorithm for learning (parity) decision trees. At least one applied learning algorithm has also been inspired by Fourier analysis.

This tutorial will provide a grounding in the basics of the Fourier transform and then survey major results already obtained using Fourier analysis. We will also go into somewhat more detail on specific ideas and algorithmic techniques that have proved particularly useful to the machine learning community. Finally, some open learning problems that seem particularly amenable to Fourier techniques will be discussed.

Goals

This tutorial will:

• Define the Walsh transform---the multidimensional discrete Fourier transform which has been particularly useful in machine learning--- relate it to more familiar versions of the Fourier transform, and provide simple proofs of and intuitions about several properties of the transform, such as Parseval's identity.
• Survey several theoretical learnability results based on Fourier techniques in order to give a sense of the broad set of possible applications of these methods in machine learning. Results include DNF learnability (both positive and negative results), quasi-efficient learnability of constant-depth circuits, and monotone circuit learnability.
• Present some key algorithmic ideas based on Fourier analysis, such as the membership-query algorithm for finding weak-approximating parities and use of Fourier coefficients to estimate the influence of a variable. The emphasis will be on developing an understanding of these Fourier results at a conceptual level so that they can be potentially applied in other learning situations.
• Explore some implications of theoretical results based on Fourier analysis for applied machine learning, including discussion of a Fourier-inspired practical learning algorithm for non-linear perceptrons. Fourier analysis of well-studied functional representations such as decision trees and Boolean Decision Diagrams and implications of these results for learning will also be presented.
• Discuss some open problems, such as learning monotone functions with respect to the uniform distribution from examples alone, and present Fourier-based observations which may prove useful in solving these problems.

Organizers

Jeff Jackson's primary research background is in theoretical machine learning, although he has also done some joint applied learning work which was inspired in part by his experience with the Fourier transform. Fourier analysis plays a key role in his Harmonic Sieve algorithm, which solves the well-studied problem of PAC+query learnability of DNF with respect to the uniform distribution. He also has a number of other published Fourier-based results. Jeff has given lectures on Fourier analysis in machine learning at the University of Calgary and Dortmund University. He received the PhD from Carnegie Mellon in 1995.

Christino Tamon has worked on theoretical problems in machine learning such as learning via Fourier transform, learning decision trees of concepts, and learning bounded-width branching programs and automata over rings. Christino Tamon received his Ph.D. degree from the University of Calgary in 1996.