Efficient Decomposed Learning for Structured Prediction
This addresses efficiency bottlenecks for researchers and practitioners in machine learning applications relying on structured prediction, though it appears incremental as it builds on existing methods.
The paper tackles the intractability of exact inference-based learning in structured prediction with expressive interactions by introducing Decomposed Learning (DecL), which restricts inference to limited parts of the structured spaces, showing it is significantly more efficient and as accurate as exact learning in real-world settings.
Structured prediction is the cornerstone of several machine learning applications. Unfortunately, in structured prediction settings with expressive inter-variable interactions, exact inference-based learning algorithms, e.g. Structural SVM, are often intractable. We present a new way, Decomposed Learning (DecL), which performs efficient learning by restricting the inference step to a limited part of the structured spaces. We provide characterizations based on the structure, target parameters, and gold labels, under which DecL is equivalent to exact learning. We then show that in real world settings, where our theoretical assumptions may not completely hold, DecL-based algorithms are significantly more efficient and as accurate as exact learning.