Part of Advances in Neural Information Processing Systems 8 (NIPS 1995)
Yishay Mansour, Sigal Sahar
The Fourier transform of boolean functions has come to play an important role in proving many important learnability results. We aim to demonstrate that the Fourier transform techniques are also a useful and practical algorithm in addition to being a powerful theoretical tool. We describe the more prominent changes we have introduced to the algorithm, ones that were crucial and without which the performance of the algorithm would severely deterio(cid:173) rate. One of the benefits we present is the confidence level for each prediction which measures the likelihood the prediction is correct.