Training of Binary Classifiers with Quantum Optimization

September 17, 2012
Hartmut Neven | Google

Modern machine learning theory formulates training of a classifier as minimization of an objective function which is the sum of two terms: the empirical risk which characterizes how well the classifier performs on a training data set and the regularization which controls the classifier complexity. I will discuss the advantages that can be obtained if either of these terms are chosen to be non-convex. A non-convex risk allows the training to cope with a significant amount of label noise while retaining the ability to learn a Bayes optimal classifier. This reduces the quality requirements for the training data, a major bottleneck for machine learning applications, increasing the autonomy of the learner. Non-convex regularization can achieve very sparse classifiers leading to increased execution speed and classifiers suitable for power constrained environments. I will describe our efforts to map the training problems onto quadratic binary optimization, the native input format of the D-Wave quantum optimization processors. The talk will discuss the evidence that the processors behave quantumly and the challenge to perform the mapping such that only a sufficiently small number of ancillary qubits are required.

Speaker Details

Education:
Hartmut Neven studied Physics and Economics in Köln, Paris, Tübingen, Aachen, Jerusalem and Brazil. He wrote his Master thesis on a neuronal model of object recognition at the Max Planck Institute for Biological Cybernetics under Valentino Braitenberg. In 1996 he received his Ph.D. from the Institute for Neuroinformatics at the Ruhr University in Bochum, Germany, for a thesis on “Dynamics for vision-guided autonomous mobile robots” written under the tutelage of Christoph von der Malsburg.

Work:
Neven was assistant professor of computer science at the University of Southern California at the Laboratory for Biological and Computational Vision. Later he returned as the head of the Laboratory for Human-Machine Interfaces at USC’s Information Sciences Institute.

Neven co-founded two companies, Eyematic for which he served as CTO at Neven Vision which he initially led as CEO. At Eyematic he developed real-time facial feature analysis for avatar animation. Neven Vision pioneered mobile visual search for camera phones and was acquired by Google in 2006. Today he manages a team responsible for advancing Google’s visual search technologies and is the engineering manager for Google Goggles.

Teams led by Neven have repeatedly won top scores in government sponsored tests designed to determine the most accurate face recognition software.

In 2006 Neven started to explore the application of quantum computing to hard combinatorial problems arising in machine learning. In collaboration with D-Wave Systems he developed the first image recognition system based on quantum algorithms. It was demonstrated at SuperComputing07. At NIPS 2009 his team demonstrated the first binary classifier trained on a quantum processor.