Max-Margin Markov Networks

article2003NeurIPS1,514 citationsBest Paper Award

Introduces Maximum Margin Markov networks, unifying kernel-based margin maximization with probabilistic graphical models to enable structured classification in high-dimensional feature spaces through an efficient, polynomial-size quadratic program.

Listen

Many critical machine learning tasks involve complex, structured data where multiple interrelated labels must be predicted simultaneously, such as text recognition, image segmentation, and webpage categorization. Practitioners traditionally faced an unsatisfying trade-off between two approaches: kernel-based methods like support vector machines (SVMs), which offer strong generalization guarantees and handle high-dimensional features but treat each label independently, and probabilistic graphical models like Markov networks, which capture correlations among labels but struggle with high-dimensional feature spaces and lack strong theoretical guarantees.

The article introduces and evaluates Maximum Margin Markov (M3) networks, a novel machine learning framework designed to combine the strengths of both approaches. The main objective is to demonstrate that M3 networks can capture dependencies in structured data while simultaneously utilizing high-dimensional kernel features and margin-maximization principles to achieve superior predictive accuracy and computational efficiency.

To achieve this, the authors formulated a convex quadratic optimization problem based on a margin scaled by per-label loss. By reparameterizing the dual optimization problem in terms of localized node and edge marginals rather than whole configurations, they reduced the problem size from exponential to polynomial. For tractable networks such as sequences, this provides an exact and compact solution, while for complex topologies, an approximate relaxation analogous to belief propagation is applied. The researchers implemented a scalable coordinate descent learning algorithm inspired by sequential minimal optimization (SMO), established new generalization error bounds, and tested the framework on optical character recognition (OCR) and collective hypertext classification datasets.

The empirical findings demonstrate dramatic performance gains over existing baseline methods. On the OCR sequence task, M3 networks with cubic kernels cut character error rates by 45% compared to conditional random fields (CRFs) and by approximately 33% compared to standard multiclass SVMs; even linear M3 networks reduced error rates by 16% relative to CRFs. In collective hypertext classification across four university computer science departments, M3 networks achieved a 40% lower error rate than relational Markov networks (RMNs) and a 51% reduction compared to standard multiclass SVMs. Theoretically, the authors proved a generalization bound that scales logarithmically with the number of labels, significantly improving upon prior linear bounds.

These results establish that combining structural correlation modeling with maximum-margin kernel methods produces substantial gains in predictive accuracy without prohibitive computational costs. Organizations deploying models for sequence labeling, spatial segmentation, or network classification can achieve significantly lower error rates without sacrificing theoretical reliability, directly reducing the risks and costs associated with misclassification in automated systems.

Decision-makers and engineering teams should adopt M3 networks as a high-performance alternative to standard CRFs and independent SVMs in structured prediction pipelines. When implementing this framework, teams should use exact factorizations for tree-structured or sequence data, and apply relaxed marginal optimizations with loopy belief propagation for highly interconnected relational networks.

While the results demonstrate strong performance across evaluated benchmarks, limitations remain when applying the method to non-tree graph structures, where the relaxed formulation lacks exact theoretical optimality guarantees despite solid practical accuracy. Additionally, scaling the kernel matrix in extremely large datasets requires efficient optimization techniques like SMO. Overall, confidence in the framework's effectiveness is high for structured sequence and network tasks, though pilot testing is recommended when adapting the method to domain-specific, highly cyclic graphs.

Stanford University markov chains network architecture Max-Margin Markov Networks M3 networks probabilistic graphical models

Taskar et al (2003).pdf

Paper: Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data, John D. Lafferty et al. (2001). It introduces Conditional Random Fields for sequence segmentation and labeling, providing the core discriminative probabilistic graphical model framework that Max-Margin Markov Networks adapt into a maximum-margin setting.
Paper: Support-vector networks, Corinna Cortes et al. (1995). It establishes the foundational support vector machine quadratic programming formulation and kernel trick that the source paper scales to structured output spaces.
Paper: On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines, Koby Crammer et al. (2002). It details the direct multiclass margin formulation and dual optimization routines that serve as an algorithmic precursor to structured large-margin classifiers.
Paper: Maximum Entropy Markov Models for Information Extraction and Segmentation, A. McCallum et al. (2000). It demonstrates discriminative sequence labeling with maximum entropy Markov models, highlighting the structural context and label dependence that motivated max-margin graphical models.
Paper: A training algorithm for optimal margin classifiers, Bernhard E. Boser et al. (1992). It introduces the fundamental dual optimization and margin-maximization principles for kernel classifiers upon which structured max-margin networks are built.
Paper: Reducing Multiclass to Binary: A Unifying Approach for Margin Classifiers, Erin L. Allwein et al. (2000). It develops the unifying theoretical analysis of margin-based multiclass classification that informed the extension of margin bounds to complex structured outputs.
Paper: A kernel method for multi-labelled classification, A. Elisseeff et al. (2001). It presents a large-margin ranking formulation for multi-labeled data, addressing label correlation via support vector methods before general graphical models were integrated.
Paper: Exploiting Generative Models in Discriminative Classifiers, T. Jaakkola et al. (1998). It demonstrates how to combine generative models and discriminative kernel classifiers via Fisher kernels, laying ground for hybrid structured-kernel representations.

Paper: Large Margin Methods for Structured and Interdependent Output Variables, Ioannis Tsochantaridis et al. (2005). It generalizes large-margin estimation to arbitrary interdependent output structures and custom task-loss functions using an efficient cutting-plane algorithm.
Paper: Training linear SVMs in linear time, Thorsten Joachims (2006). It introduces the cutting-plane optimization method (SVM-Perf) that builds upon structural large-margin formulations to achieve linear-time training.
Paper: Markov logic networks, Matthew Richardson et al. (2006). It combines first-order logic with Markov networks to handle relational structure and uncertainty in complex relational domains.
Paper: A Review on Multi-Label Learning Algorithms, Min-Ling Zhang et al. (2014). It provides a comprehensive survey of modern multi-label algorithms, contextualizing max-margin and high-order correlation models within broader structured learning paradigms.
Paper: Efficient Inference in Fully Connected CRFs with Gaussian Edge Potentials, Philipp Krähenbühl et al. (2011). It advances dense structured inference in graphical models by developing fast mean-field inference with Gaussian edge potentials for dense pixel-level labeling.

Abstract

In typical classification tasks, we seek a function which assigns a label to a single object. Kernel-based approaches, such as support vector machines (SVMs), which maximize the margin of confidence of the classifier, are the method of choice for many such tasks. Their popularity stems both from the ability to use high-dimensional feature spaces, and from their strong theoretical guarantees. However, many real-world tasks involve sequential, spatial, or structured data, where multiple labels must be assigned. Existing kernel-based methods ignore structure in the problem, assigning labels independently to each object, losing much useful information. Conversely, probabilistic graphical models, such as Markov networks, can represent correlations between labels, by exploiting problem structure, but cannot handle high-dimensional feature spaces, and lack strong theoretical generalization guarantees. In this paper, we present a new framework that combines the advantages of both approaches: Maximum margin Markov (M^3) networks incorporate both kernels, which efficiently deal with high-dimensional features, and the ability to capture correlations in structured data. We present an efficient algorithm for learning M^3 networks based on a compact quadratic program formulation. We provide a new theoretical bound for generalization in structured domains. Experiments on the task of handwritten character recognition and collective hypertext classification demonstrate very significant gains over previous approaches.

Topics

markov chains network architecture

Keywords

Max-Margin Markov Networks M3 networks probabilistic graphical models support vector machines belief propagation collective hypertext classification marginal polytope multi-class SVMs generalization bounds dual QP

1 Introduction
2 Structure in classification problems
3 Margin-based structured classification
4 Exploiting structure in M3 networks
5 SMO learning of M3 networks
6 Generalization bound
7 Experiments
8 Discussion
References

Knowls

Knowl 1 — Global Primal and Dual Maximum-Margin Formulations for Structured Prediction
model/method
In structured classification, given training instances $S = \{(\mathbf{x}^{(i)}, \mathbf{y}^{(i)} = \mathbf{t}(\mathbf{x}^{(i)}))\}_{i=1}^m$ where each label is a composite vector $\mathbf{y} = (y_1, \dots, y_l) \in \mathcal{Y}_1 \times \dots \times \mathcal{Y}_l$ , hypotheses take the linear form $h_{\mathbf{w}}(\mathbf{x}) = \arg\max_{\mathbf{y}} \mathbf{w}^\top \mathbf{f}(\mathbf{x}, \mathbf{y})$ . Rather than 0-1 loss, the margin is required to scale linearly with the per-label (Hamming) loss $\Delta_{\mathbf{t}(\mathbf{x})}(\mathbf{y}) = \sum_{i=1}^l I(y_i \neq (\mathbf{t}(\mathbf{x}))_i)$ .

The soft-margin primal quadratic program (QP) is: $\min_{\mathbf{w}, \boldsymbol{\xi}} \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{\mathbf{x} \in S} \xi_{\mathbf{x}}$ $\text{subject to } \mathbf{w}^\top \Delta \mathbf{f}_{\mathbf{x}}(\mathbf{y}) \ge \Delta_{\mathbf{t}(\mathbf{x})}(\mathbf{y}) - \xi_{\mathbf{x}}, \quad \forall \mathbf{x} \in S, \forall \mathbf{y} \in \mathcal{Y}$ where $\Delta \mathbf{f}_{\mathbf{x}}(\mathbf{y}) = \mathbf{f}(\mathbf{x}, \mathbf{t}(\mathbf{x})) - \mathbf{f}(\mathbf{x}, \mathbf{y})$ , $\xi_{\mathbf{x}} \ge 0$ are slack variables, and $C > 0$ is the regularization parameter.

The corresponding dual QP is: $\max_{\boldsymbol{\alpha}} \sum_{\mathbf{x} \in S} \sum_{\mathbf{y} \in \mathcal{Y}} \alpha_{\mathbf{x}}(\mathbf{y}) \Delta_{\mathbf{t}(\mathbf{x})}(\mathbf{y}) - \frac{1}{2} \left\| \sum_{\mathbf{x} \in S} \sum_{\mathbf{y} \in \mathcal{Y}} \alpha_{\mathbf{x}}(\mathbf{y}) \Delta \mathbf{f}_{\mathbf{x}}(\mathbf{y}) \right\|^2$ $\text{subject to } \sum_{\mathbf{y} \in \mathcal{Y}} \alpha_{\mathbf{x}}(\mathbf{y}) = C, \quad \forall \mathbf{x} \in S; \qquad \alpha_{\mathbf{x}}(\mathbf{y}) \ge 0, \quad \forall \mathbf{x} \in S, \forall \mathbf{y} \in \mathcal{Y}$
Knowl 2 — Factored Dual Quadratic Program for Forest-Structured Markov Networks
model/method
When the joint feature mapping and target loss decompose over the edges $E$ and nodes of a pairwise Markov network $G = (\mathcal{Y}, E)$ as $\mathbf{f}(\mathbf{x}, \mathbf{y}) = \sum_{(i,j) \in E} \mathbf{f}(\mathbf{x}, y_i, y_j)$ and $\Delta_{\mathbf{t}(\mathbf{x})}(\mathbf{y}) = \sum_{i=1}^l \Delta_{\mathbf{t}(\mathbf{x})}(y_i)$ , the dual variables $\alpha_{\mathbf{x}}(\mathbf{y})$ act as unnormalized joint probability densities. They can be replaced by polynomial-sized marginal dual variables: $\mu_{\mathbf{x}}(y_i, y_j) = \sum_{\mathbf{y} \sim [y_i, y_j]} \alpha_{\mathbf{x}}(\mathbf{y}), \quad \forall (i, j) \in E, y_i, y_j, \mathbf{x}$ $\mu_{\mathbf{x}}(y_i) = \sum_{\mathbf{y} \sim [y_i]} \alpha_{\mathbf{x}}(\mathbf{y}), \quad \forall i, y_i, \mathbf{x}$ where $\mathbf{y} \sim [y_i, y_j]$ denotes full labelings consistent with partial assignment $(y_i, y_j)$ .

For singly connected graphs (forests), enforcing consistency between node and edge marginals guarantees that $\boldsymbol{\mu}$ lies in the marginal polytope. The resulting factored dual QP is: $\max_{\boldsymbol{\mu}} \sum_{\mathbf{x} \in S} \sum_{i, y_i} \mu_{\mathbf{x}}(y_i) \Delta_{\mathbf{t}(\mathbf{x})}(y_i) - \frac{1}{2} \sum_{\mathbf{x}, \hat{\mathbf{x}} \in S} \sum_{\substack{(i,j) \in E \\ y_i, y_j}} \sum_{\substack{(r,s) \in E \\ y_r, y_s}} \mu_{\mathbf{x}}(y_i, y_j) \mu_{\hat{\mathbf{x}}}(y_r, y_s) \Delta \mathbf{f}_{\mathbf{x}}(y_i, y_j)^\top \Delta \mathbf{f}_{\hat{\mathbf{x}}}(y_r, y_s)$ $\text{subject to } \sum_{y_i} \mu_{\mathbf{x}}(y_i, y_j) = \mu_{\mathbf{x}}(y_j), \quad \forall y_j, \forall (i, j) \in E, \forall \mathbf{x} \in S$ $\sum_{y_i} \mu_{\mathbf{x}}(y_i) = C, \quad \forall \mathbf{x} \in S$ $\mu_{\mathbf{x}}(y_i, y_j) \ge 0, \quad \forall (i, j) \in E, y_i, y_j, \forall \mathbf{x} \in S$ where $\Delta \mathbf{f}_{\mathbf{x}}(y_i, y_j) = \mathbf{f}(\mathbf{x}, (\mathbf{t}(\mathbf{x}))_i, (\mathbf{t}(\mathbf{x}))_j) - \mathbf{f}(\mathbf{x}, y_i, y_j)$ . The optimal weight vector is given by: $\mathbf{w} = \sum_{\mathbf{x} \in S} \sum_{(i,j) \in E} \sum_{y_i, y_j} \mu_{\mathbf{x}}(y_i, y_j) \Delta \mathbf{f}_{\mathbf{x}}(y_i, y_j)$
Knowl 3 — Factored Primal Quadratic Program for Structured Prediction
equation
The compact factored primal quadratic program corresponding to the factored dual is formulated by introducing auxiliary variables $m_{\mathbf{x}, j}(y_i)$ (Lagrange multipliers for the marginal consistency constraints) and decomposing slack variables over nodes and edges:

$\min_{\mathbf{w}, \boldsymbol{\xi}, \mathbf{m}} \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{\mathbf{x} \in S} \sum_{i=1}^l \xi_{\mathbf{x}, i} + C \sum_{\mathbf{x} \in S} \sum_{(i,j) \in E} \xi_{\mathbf{x}, ij}$ $\text{subject to } \mathbf{w}^\top \Delta \mathbf{f}_{\mathbf{x}}(y_i, y_j) + \sum_{(i', j) \in E: i' \neq i} m_{\mathbf{x}, i'}(y_j) + \sum_{(j', i) \in E: j' \neq j} m_{\mathbf{x}, j'}(y_i) \ge -\xi_{\mathbf{x}, ij}, \quad \forall \mathbf{x} \in S, \forall (i,j) \in E, \forall y_i, y_j$ $\sum_{(i,j) \in E} m_{\mathbf{x}, j}(y_i) \ge \Delta_{\mathbf{t}(\mathbf{x})}(y_i) - \xi_{\mathbf{x}, i}, \quad \forall \mathbf{x} \in S, \forall i, \forall y_i$ $\xi_{\mathbf{x}, ij} \ge 0, \quad \xi_{\mathbf{x}, i} \ge 0, \quad \forall \mathbf{x}, i, (i,j)$ where $\Delta \mathbf{f}_{\mathbf{x}}(y_i, y_j) = \mathbf{f}(\mathbf{x}, (\mathbf{t}(\mathbf{x}))_i, (\mathbf{t}(\mathbf{x}))_j) - \mathbf{f}(\mathbf{x}, y_i, y_j)$ , $\Delta_{\mathbf{t}(\mathbf{x})}(y_i) = I(y_i \neq (\mathbf{t}(\mathbf{x}))_i)$ , and $C > 0$ is the regularization parameter.
Knowl 4 — Optimality Equivalence Theorem for Forest-Structured Markov Networks
theoretical result
Let $S = \{(\mathbf{x}, \mathbf{t}(\mathbf{x}))\}$ be a training set and let $G = (\mathcal{Y}, E)$ be a pairwise Markov network defined over label variables $\mathcal{Y} = \mathcal{Y}_1 \times \dots \times \mathcal{Y}_l$ .

If for each instance $\mathbf{x}$ the edge set $E$ forms a forest (a set of singly connected trees), then a weight vector $\mathbf{w}$ is optimal for the global primal quadratic program with an exponential number of constraints: $\min_{\mathbf{w}, \boldsymbol{\xi}} \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{\mathbf{x}} \xi_{\mathbf{x}} \quad \text{s.t.} \quad \mathbf{w}^\top \Delta \mathbf{f}_{\mathbf{x}}(\mathbf{y}) \ge \Delta_{\mathbf{t}(\mathbf{x})}(\mathbf{y}) - \xi_{\mathbf{x}}, \quad \forall \mathbf{x} \in S, \forall \mathbf{y} \in \mathcal{Y}$ if and only if $\mathbf{w}$ is optimal for the polynomial-sized factored primal quadratic program with auxiliary variables $m_{\mathbf{x}, j}(y_i)$ and factored slacks $\xi_{\mathbf{x}, i}, \xi_{\mathbf{x}, ij}$ .
Knowl 5 — Generalization Bound for Multi-Label Margin Classifiers
theoretical result
Let $\mathcal{L}(\mathbf{w}, \mathbf{x}) = \frac{1}{l} \Delta_{\mathbf{t}(\mathbf{x})}(\arg\max_{\mathbf{y}} \mathbf{w}^\top \mathbf{f}_{\mathbf{x}}(\mathbf{y}))$ be the per-label classification error, and define the $\gamma$ -margin per-label loss as: $\mathcal{L}^\gamma(\mathbf{w}, \mathbf{x}) = \sup_{\mathbf{z}: |\mathbf{z}(\mathbf{y}) - \mathbf{w}^\top \mathbf{f}_{\mathbf{x}}(\mathbf{y})| \le \gamma \Delta_{\mathbf{t}(\mathbf{x})}(\mathbf{y}), \forall \mathbf{y}} \frac{1}{l} \Delta_{\mathbf{t}(\mathbf{x})}(\arg\max_{\mathbf{y}} \mathbf{z}(\mathbf{y}))$

If the edge basis functions have bounded 2-norm, $\max_{(i,j), y_i, y_j} \|\mathbf{f}_{\mathbf{x}}(y_i, y_j)\|_2 \le R_{\text{edge}}$ , then for a family of hyperplanes parameterized by $\mathbf{w}$ , any $\delta > 0$ , any margin $\gamma > 0$ , and sample size $m > 1$ , there exists a constant $K$ such that with probability at least $1 - \delta$ : $\mathbb{E}_{\mathbf{x}}[\mathcal{L}(\mathbf{w}, \mathbf{x})] \le \mathbb{E}_S[\mathcal{L}^\gamma(\mathbf{w}, \mathbf{x})] + \sqrt{\frac{K}{m} \left[ \frac{R_{\text{edge}}^2 \|\mathbf{w}\|_2^2 q^2}{\gamma^2} (\ln m + \ln l + \ln q + \ln k) + \ln \frac{1}{\delta} \right]}$ where:
- $q = \max_i |\{(i,j) \in E\}|$ is the maximum node degree in the network,
- $k$ is the number of label classes per variable ( $|\mathcal{Y}_i| = k$ ),
- $l$ is the number of label variables in the network,
- $\mathbb{E}_S[\mathcal{L}^\gamma(\mathbf{w}, \mathbf{x})] = \frac{1}{m} \sum_{i=1}^m \mathcal{L}^\gamma(\mathbf{w}, \mathbf{x}^{(i)})$ is the empirical $\gamma$ -margin loss on sample $S$ .
The bound depends logarithmically on the sequence length $l$ (via $\ln l$ ) and scales with the per-edge norm $R_{\text{edge}}$ . If $l/m = O(1)$ , the bound becomes asymptotically independent of $l$ .
Knowl 6 — Kernelized Formulations for Structured Markov Networks
model/method
In Maximum Margin Markov ( $M^3$ ) networks, the factored dual quadratic program relies exclusively on inner products between basis functions. Edge basis functions can be defined as: $\mathbf{f}_{\mathbf{x}}(y_i, y_j) = \rho(y_i, y_j) \boldsymbol{\phi}^{ij}(\mathbf{x})$ where $\rho(y_i, y_j)$ is an indicator/selector vector over discrete label assignments to variables $i$ and $j$ , and $\boldsymbol{\phi}^{ij}(\mathbf{x})$ is an input feature vector (potentially high- or infinite-dimensional).

The inner product between basis functions evaluated in the factored dual QP becomes: $\mathbf{f}_{\mathbf{x}}(y_i, y_j)^\top \mathbf{f}_{\hat{\mathbf{x}}}(y_r, y_s) = \rho(y_i, y_j)^\top \rho(y_r, y_s) K_\phi(\mathbf{x}, i, j, \hat{\mathbf{x}}, r, s)$ where $K_\phi(\mathbf{x}, i, j, \hat{\mathbf{x}}, r, s) = \boldsymbol{\phi}^{ij}(\mathbf{x}) \cdot \boldsymbol{\phi}^{rs}(\hat{\mathbf{x}})$ is a Mercer kernel function (such as a polynomial or RBF kernel computed over inputs). This allows structured graphical models to incorporate non-linear kernel feature spaces while retaining compact quadratic program optimization.
Knowl 7 — Graph Triangulation and Marginal Polytope Relaxation for Loopy Networks
model/method
For Markov networks that are not forests, local pairwise consistency constraints do not fully restrict marginal variables $\boldsymbol{\mu}$ to the true marginal polytope. Two extensions resolve general graphs:
1. Triangulation for low tree-width graphs: Adding chordal edges triangulates the network into cliques. New LP variables $\eta$ are defined over joint assignments of maximal cliques, and linear equalities constrain the original $\mu$ variables to match $\eta$ marginals. This enforces exact marginal polytope membership without modifying the objective function or basis functions. The number of constraints is exponential only in the clique size (tree-width), permitting tractable exact solutions for low tree-width graphs.
2. Relaxation for high tree-width / loopy graphs: When triangulation is intractable, the factored dual QP is solved directly on the untriangulated graph enforcing only local pairwise consistency constraints. This optimizes the exact maximum-margin objective over a pseudomarginal relaxation of the marginal polytope, analogous to the domain relaxation in loopy belief propagation.
Knowl 8 — Sequential Minimal Optimization for Factored Dual Markov Networks
algorithm
To handle large kernel matrices in the factored dual QP, optimization is performed via coordinate descent on pairs of joint labelings $(\mathbf{y}^1, \mathbf{y}^2)$ for a given instance $\mathbf{x}$ . Shifting weight $\lambda = \alpha'_\mathbf{x}(\mathbf{y}^1) - \alpha_\mathbf{x}(\mathbf{y}^1) = \alpha_\mathbf{x}(\mathbf{y}^2) - \alpha'_\mathbf{x}(\mathbf{y}^2)$ updates the marginal dual variables according to: $\mu'_\mathbf{x}(y_i, y_j) = \mu_\mathbf{x}(y_i, y_j) + \lambda I(y_i = y_i^1, y_j = y_j^1) - \lambda I(y_i = y_i^2, y_j = y_j^2)$ $\mu'_\mathbf{x}(y_i) = \mu_\mathbf{x}(y_i) + \lambda I(y_i = y_i^1) - \lambda I(y_i = y_i^2)$
Input: Training set $S = \{(\mathbf{x}, \mathbf{t}(\mathbf{x}))\}$ , regularization parameter $C$ , tolerance $\epsilon$
Output: Marginal dual variables $\boldsymbol{\mu}$ and model weights $\mathbf{w}$
Initialize $\mu_{\mathbf{x}}(y_i, y_j)$ for all $\mathbf{x} \in S, (i,j) \in E, y_i, y_j$ such that $\sum_{y_i} \mu_{\mathbf{x}}(y_i) = C$ and consistency holds
while KKT optimality conditions are violated beyond tolerance $\epsilon$ do
    for each instance $\mathbf{x} \in S$ do
        Perform inference on network $G$ to find worst-violating label pair $(\mathbf{y}^1, \mathbf{y}^2)$
        if KKT violation for $(\mathbf{y}^1, \mathbf{y}^2)$ exceeds $\epsilon$ then
            Solve the 1D quadratic subproblem analytically for step size $\lambda$
            for each edge $(i,j) \in E$ do
                 $\mu_{\mathbf{x}}(y_i, y_j) \leftarrow \mu_{\mathbf{x}}(y_i, y_j) + \lambda I(y_i = y_i^1, y_j = y_j^1) - \lambda I(y_i = y_i^2, y_j = y_j^2)$
            for each node $i$ do
                 $\mu_{\mathbf{x}}(y_i) \leftarrow \mu_{\mathbf{x}}(y_i) + \lambda I(y_i = y_i^1) - \lambda I(y_i = y_i^2)$
return $\mathbf{w} = \sum_{\mathbf{x} \in S} \sum_{(i,j) \in E} \sum_{y_i, y_j} \mu_{\mathbf{x}}(y_i, y_j) \Delta \mathbf{f}_{\mathbf{x}}(y_i, y_j)$
Knowl 9 — Handwriting Recognition Performance on the Kassel OCR Dataset
empirical result
Experiments were conducted on the Kassel handwritten character dataset consisting of approximately 6,100 handwritten words (average word length ~8 characters, 150 human subjects), where each character was rasterized into a $16 \times 8$ binary pixel image with 26 possible character classes ( $a$ through $z$ ). The dataset was partitioned into 10 folds of ~600 training and ~5,500 testing examples.

Models compared:
- Independent classifiers: Logistic Regression, Multi-class SVMs (mSVM), One-against-all SVMs.
- Sequence models: Conditional Random Fields (CRFs) trained via conditional likelihood with Gaussian priors, Maximum Margin Markov Networks ( $M^3\text{N}$ ).
- Kernels tested: linear, quadratic, and cubic polynomial kernels.
Key results:
- Linear $M^3\text{N}$ achieved a per-character test error rate 16% lower than linear CRFs, matching the performance of multi-class SVMs equipped with cubic kernels.
- $M^3\text{N}$ with cubic kernels achieved a per-character test error rate 45% lower than linear CRFs and 33% lower than cubic multi-class SVMs.
Knowl 10 — Collective Hypertext Classification Performance on the WebKB Dataset
empirical result
Experiments on collective webpage classification used the WebKB dataset across four Computer Science departments (Cornell, Texas, Washington, Wisconsin). Webpages were classified into five categories (course, faculty, student, project, other) using a leave-one-school-out protocol (training on three departments and testing on the remaining department). Features comprised binary indicators of words in page text and hyperlink anchor text.

Models compared:
- Linear multi-class SVM (mSVM): independent page classification based only on text and anchor words.
- Relational Markov Network (RMN): pairwise Markov network over hyperlinked page labels, trained discriminatively by maximizing conditional likelihood.
- Maximum Margin Markov Network ( $M^3\text{N}$ ): same graph topology and features as RMN, trained with the factored dual QP relaxation and loopy belief propagation.
Key results:
- Exploiting hyperlink structure via RMNs reduced test error compared to independent multi-class SVMs across all departments.
- $M^3\text{N}$ achieved an average per-page test error 40% lower than RMNs and 51% lower than multi-class SVMs.

Coverage note — No substantial contributed material was omitted.

References

1.Y. Altun, I. Tsochantaridis, and T. Hofmann. Hidden markov support vector machines. In Proc. ICML, 2003.
2.D. Bertsekas. Nonlinear Programming. Athena Scientific, Belmont, MA, 1999.
3.M. Collins. Parameter estimation for statistical parsing models: Theory and practice of distribution-free methods. In IWPT, 2001.
4.R.G. Cowell, A.P. Dawid, S.L. Lauritzen, and D.J. Spiegelhalter. Probabilistic Networks and Expert Systems. Springer, New York, 1999.
5.K. Crammer and Y. Singer. On the algorithmic implementation of multiclass kernelbased vector machines. Journal of Machine Learning Research, 2(5):265–292, 2001.
6.R. Kassel. A Comparison of Approaches to On-line Handwritten Character Recognition. PhD thesis, MIT Spoken Language Systems Group, 1995.
7.J. Lafferty, A. McCallum, and F. Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proc. ICML01, 2001.
8.J. Pearl. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, 1988.
9.J. Platt. Using sparseness and analytic QP to speed training of support vector machines. In NIPS, 1999.
10.B. Taskar, P. Abbeel, and D. Koller. Discriminative probabilistic models for relational data. In Proc. UAI02, Edmonton, Canada, 2002.
11.V.N. Vapnik. The Nature of Statistical Learning Theory. Springer-Verlag, New York, 1995.
12.J. Yedidia, W. Freeman, and Y. Weiss. Generalized belief propagation. In NIPS, 2000.
13.T. Zhang. Covering number bounds of certain regularized linear function classes. Journal of Machine Learning Research, 2:527–550, 2002.

Citation

MLA

Taskar, B., et al. “Max-Margin Markov Networks”. Advances in Neural Information Processing Systems, vol. 16, 2003, https://proceedings.neurips.cc/paper_files/paper/2003/file/878d5691c824ee2aaf770f7d36c151d6-Paper.pdf.

APA

Taskar, B., Guestrin, C., & Koller, D. (2003). Max-Margin Markov Networks. Advances in Neural Information Processing Systems, 16. https://proceedings.neurips.cc/paper_files/paper/2003/file/878d5691c824ee2aaf770f7d36c151d6-Paper.pdf

Chicago

Taskar, B., C. Guestrin, and D. Koller. 2003. “Max-Margin Markov Networks”. Advances in Neural Information Processing Systems 16. https://proceedings.neurips.cc/paper_files/paper/2003/file/878d5691c824ee2aaf770f7d36c151d6-Paper.pdf.

Harvard

Taskar, B., Guestrin, C. and Koller, D. (2003) “Max-Margin Markov Networks”, Advances in Neural Information Processing Systems. Curran Associates, Inc. Available at: https://proceedings.neurips.cc/paper_files/paper/2003/file/878d5691c824ee2aaf770f7d36c151d6-Paper.pdf.

Vancouver

1. Taskar B, Guestrin C, Koller D (2003) Max-Margin Markov Networks. Advances in Neural Information Processing Systems 16:

BibTeX

@inproceedings{taskar2003max,
  title = {Max-Margin Markov Networks},
  author = {Taskar, Ben and Guestrin, Carlos and Koller, Daphne},
  year = {2003},
  booktitle = {Advances in Neural Information Processing Systems},
  publisher = {Curran Associates, Inc.},
  volume = {16},
  url = {https://proceedings.neurips.cc/paper_files/paper/2003/file/878d5691c824ee2aaf770f7d36c151d6-Paper.pdf}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Authors

Max-Margin Markov Networks

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Global Primal and Dual Maximum-Margin Formulations for Structured Prediction

Knowl 2 — Factored Dual Quadratic Program for Forest-Structured Markov Networks

Knowl 3 — Factored Primal Quadratic Program for Structured Prediction

Knowl 4 — Optimality Equivalence Theorem for Forest-Structured Markov Networks

Knowl 5 — Generalization Bound for Multi-Label Margin Classifiers

Knowl 6 — Kernelized Formulations for Structured Markov Networks

Knowl 7 — Graph Triangulation and Marginal Polytope Relaxation for Loopy Networks

Knowl 8 — Sequential Minimal Optimization for Factored Dual Markov Networks

Knowl 9 — Handwriting Recognition Performance on the Kassel OCR Dataset

Knowl 10 — Collective Hypertext Classification Performance on the WebKB Dataset

References

Citation

BibTeX

Access the Paper