Learning hierarchies at two-class complexity

It is assumed that to learn discriminative identification function when the output space is a labelled hierarchy is a much more complex problem than binary classification. In this presentation we show the complexity of this kind of problem can be detached from the optimisation model and can be expressed by an embedding into a Hilbert space. This allows a universal optimisation model processing Hilbertian inputs and outputs to be used to solve the optimisation task without tackling with the underlying structural complexity. The optimisation model is an implementation of a certain type of maximum margin regression, an algebraic generalisation of the well-known Support Vector Machine. The computational complexity of the optimisation scales only with the number of input-output pairs and it is independent from the dimensions of both spaces. Furthermore its overall complexity is equal to binary classification. Our approach can be easily be extended towards other structural learning problems with the same optimisation framework. We demonstrate the high performance of the proposed method on the WIPO and the Reuters datasets, where our task is to predict a complete classification hierarchy for each example.