Spectral learning algorithms, which learn an unknown function by learning a spectral representation of the function, have been widely used in computational learning theory to prove many interesting learnability results. These algorithms have also been successfully used in real-world applications. However, previous work has left open many questions about how to best use these methods in real-world learning scenarios. This dissertation presents several significant advances in real-world spectral learning. It presents new algorithms for finding large spectral coefficients (a key sub-problem in spectral learning) that allow spectral learning methods to be applied to much larger problems and to a wider range of problems than was possible with previous approaches. It presents an empirical comparison of new and existing spectral learning methods, showing among other things that the most common approach seems to be the least effective in typical real-world settings. It also presents a multi-spectrum learning approach in which a learner makes use of multiple representations when training. Empirical results show that a multi-spectrum learner can usually match or exceed the performance of the best single-spectrum learner. Finally, this dissertation shows how a particular application, sentiment analysis, can benefit from a spectral approach, as the standard approach to the problem is significantly improved by incorporating spectral features into the learning process.



College and Department

Physical and Mathematical Sciences; Computer Science



Date Submitted


Document Type





spectral learning, Fourier-based learning, Fourier transform, machine learning, search algorithms, sentiment analysis