The application we will build generates binary classifiers. At a high level the way the application works is that, given an object, it will classify the object into one of two categories. For example, the object could be a photograph, and the classifier could automatically label the photograph with a tag saying “there is a face in this picture” or “there is no face in this picture”. In general the approach can be used on any object and any classification scheme.
One important thing to note is that “teaching machines to learn” generally has two separate phases. The first is the training phase, which is typically very computationally expensive (months, lots of humans in the loop, thousands of processors). In this phase the system “learns by example”. We show it many instances of objects of the first category, and then many instances of the second category, and the system learns which is which. The second phase is the use of the classifier, where we show it a new object it has not seen yet and the classifier guesses which category it is in. This second phase consumes very little computing power or memory, and typically can be run on very limited devices such as cell phones. Where the quantum computer will be used here is in the first phase. Once the classifier is trained, it is just a small piece of software that can live anywhere.
A workhorse approach to building binary classifiers is boosting. A common form of boosting is adaptive boosting (adaboost). Our approach has the same objective and application space as boosting–the approach we’ll describe here can be used in any situation where boosting is used now. When we benchmark our approach, we will compare our performance directly to adaboost.
Our objective will be to beat adaboost in three different dimensions: (1) classification accuracy (less errors in classifying new objects); (2) compactness (less memory required to store the classifier); and (3) reduced time to complete training phase (we want to be faster than adaboost).