The Fourier transform of Boolean functions has received considerable attent
ion in the last few years in the computational learning theory community, a
nd has come to play an important role in proving many important learnabilit
y results. The aim of this work is to demonstrate that the Fourier transfor
m techniques are also a useful and practical algorithm, in addition to havi
ng many interesting theoretical properties. In fact, this work was prompted
by a genuine problem that was brought to our attention; researchers at a c
ompany were trying to come by a method to reverse-engineer a state-free con
troller. They had the capability of querying the controller on any input, t
hus setting them in the membership query model, in which the Fourier transf
orm algorithm is set.
In order to keep the algorithm run-time reasonable and still produce accura
te hypotheses, we had to perform many optimizations. In the paper we discus
s the more prominent optimizations, ones that were crucial and without whic
h the performance of the algorithm would severely deteriorate. One of the b
enefits we present is the confidence level the algorithm produces in additi
on to the predictions. The confidence level measures the likelihood that th
e prediction is correct.