Approximation Techniques for Scaling up Permanental Classification

The overarching theme of this thesis is reducing the time and space complexities of the permanental approach to multi class classification. Approximate permanental classification can be achieved via a hierarchy of increasingly accurate cyclic approximations to the permanent ratio. The computational complexities of these approximations also increase with the accuracy however, with rate O(N^(#cycles-1)) for training time and O(N^2) for training and prediction memory. In this thesis three approximation techniques are investigated for speeding up the training and prediction times for cyclic approximations up to order four. The methods used are random Fourier features, data binning, and basis function approximation. Basis functions with weights chosen using integrals square error minimization perform best empirically. Finally, a pseudo likelihood is developed and used for variable selection.