Multiple Kernel Learning for Prediction on Unknown Graph Structures

The paper considers the problem of structured output learning when the output graph structure is not known and must be inferred during learning. Building on the work of [1] in which a random set of spanning trees is used to approximate the margin, the paper shows that there exists a unit L1-norm constrained combination of spanning trees that achieves the full margin of the unknown output graph. It is shown that optimising the margin under this constraint corresponds to a convex optimisation problem that combines structured output and multiple kernel learning. Inference of the maximum violators is achieved by a generalisation of the method of [1] that searches the K-best lists for the chosen trees. Structure is interpreted as the final weights attached to edges and it is shown that the exponentially large set of all possible spanning trees of the complete output graph can be efficiently explored using a simple implementation of the maximum spanning tree algorithm. Preliminary experiments with the method show encouraging results in agreement with the theoretical analysis.