Dual Decomposed Learning with Factorwise Oracles for Structural SVMs of Large Output Domain

Area of Science:

• Machine Learning
• Artificial Intelligence
• Computer Science

Background:

• Training machine learning models with large structured outputs often requires expensive inference oracles, hindering practical applications.
• Existing methods for Structural Support Vector Machines (SVMs) face computational challenges due to repetitive oracle calls.

Purpose of the Study:

• To develop a more efficient training method for Structural SVMs dealing with large output domains.
• To replace computationally expensive structured oracles with more efficient Factorwise Maximization Oracles (FMOs).

Main Methods:

• Decomposition of Structural SVM training into a series of interconnected multiclass SVM problems.
• Introduction of Factorwise Maximization Oracles (FMOs) for efficient message passing between subproblems.
• Proposal of a Greedy Direction Method of Multiplier (GDMM) algorithm for guaranteed convergence.

Main Results:

• The proposed method achieves sublinear complexity relative to the factor domain size.
• The GDMM algorithm ensures convergence to ε sub-optimality within O(log(1/ε)) passes.
• Experimental results demonstrate orders-of-magnitude speedup compared to state-of-the-art methods on large-scale problems.

Conclusions:

• The novel decomposition and FMO approach significantly enhances the efficiency of training Structural SVMs.
• This method offers a practical solution for machine learning applications involving complex structured outputs.