Back

Probability Estimates for Multi-class Classification by Pairwise Coupling

Tingyao WuChih-Jen LinRuby C. Weng

article2003JMLR2,026 citations
Department of Computer ScienceNational Chengchi UniversityNational Taiwan UniversityUniversity of California, Berkeleyclassification modelsmulti-class classificationprobabilitypairwise couplingmulti-class classificationmulti-class probability estimates
Wu et al (2003).pdf
  • Paper: Transforming classifier scores into accurate multiclass probability estimates, Bianca Zadrozny et al. (2002). This paper establishes foundational techniques for converting binary classifier scores into calibrated probabilities and coupling them for multiclass settings, which the source directly aims to improve upon with stable linear system formulations.
  • Paper: Solving Multiclass Learning Problems via Error-Correcting Output Codes, Thomas G. Dietterich et al. (1994). This work introduces output-coding decomposition schemes that provide the fundamental framework for reducing multiclass classification into collections of binary problems.
  • Paper: On Combining Classifiers, Josef Kittler et al. (1998). This study analyzes standard Bayesian and voting fusion rules for combining multiple classifiers, setting the theoretical stage for the source's investigation into stable pairwise probability coupling.
  • Paper: The foundations of cost-sensitive learning, Charles Elkan (2001). This paper examines the theoretical foundations of decision-making under cost sensitivity, motivating the necessity of obtaining accurate, well-calibrated class probability estimates.
  • Paper: Predicting good probabilities with supervised learning, Alexandru Niculescu-Mizil et al. (2005). This work comprehensively benchmarks and evaluates probability calibration methods across modern learning algorithms, extending the practical application of estimated probabilities.
  • Paper: In Defense of One-Vs-All Classification, Ryan Rifkin et al. (2004). This paper critically evaluates the performance of one-versus-all versus all-pairs multiclass decomposition schemes, contextualizing when pairwise coupling strategies are truly beneficial.
  • Paper: An empirical comparison of supervised learning algorithms, Rich Caruana et al. (2006). This study extends the comparative evaluation of supervised learning algorithms to include calibration quality alongside multi-metric performance.
  • Paper: Classifier chains for multi-label classification, Jesse Read et al. (2009). This paper builds on binary decomposition concepts to develop classifier chains for multi-label problems, bridging single-label multiclass reductions to complex multi-output tasks.
Cover for Probability Estimates for Multi-class Classification by Pairwise Coupling

Abstract

Pairwise coupling is a popular multi-class classification method that combines all comparisons for each pair of classes. This paper presents two approaches for obtaining class probabilities. Both methods can be reduced to linear systems and are easy to implement. We show conceptually and experimentally that the proposed approaches are more stable than the two existing popular methods: voting and the method by Hastie and Tibshirani (1998).

Topics

classification modelsmulti-class classificationprobability

Keywords

pairwise couplingmulti-class classificationmulti-class probability estimatespairwise class probabilitiesBradley-Terry modelssupport vector machinesmargin classifiersprobabilistic outputsbinary classifier

Table of Contents

  • 1. Introduction
  • 2. Survey of Existing Methods
  • 2.1 Voting
  • 2.2 Method by Refregier and Vallet
  • 2.3 Method by Price, Knerr, Personnaz, and Dreyfus
  • 2.4 Method by Hastie and Tibshirani
  • 3. Our First Approach
  • 3.1 Solving (14)
  • 3.2 Another Look at (14)
  • 4. Our Second Approach
  • 4.1 A Linear System from (19)
  • 4.2 Solving (23)
  • 5. Relations Between Different Methods
  • 6. Experiments on Synthetic Data
  • 7. Experiments on Real Data
  • 7.1 SVM as the Binary Classifier
  • 7.2 Random Forest as the Binary Classifier
  • 7.3 Miscellaneous Observations and Discussion
  • Acknowledgments
  • Appendix A. Proof of Theorem 2
  • Appendix B. Proof of Theorem 3
  • Appendix C. Proof of Theorem 4
  • Appendix D. Implementation Notes of Algorithm 2
  • Appendix E. Derivation of (32)
  • References

Knowls

  1. Knowl 1 — Multi-Class Probability Estimation via Markov Chain Coupling

    model/method

    Let kk be the number of classes, and let rijo[0,1]r_{ij} o [0, 1] denote the estimated pairwise conditional probability rij extapproxP(y=i∣y=i or j,x)r_{ij} \ ext{approx} P(y = i \mid y = i \text{ or } j, x) satisfying rij+rji=1r_{ij} + r_{ji} = 1 and rij>0r_{ij} > 0 for all i≠ji \neq j. The objective is to estimate the multi-class posterior class probabilities p=(p1,…,pk)Tp = (p_1, \dots, p_k)^T where pi=P(y=i∣x)p_i = P(y = i \mid x), ∑i=1kpi=1\sum_{i=1}^k p_i = 1, and pi≥0p_i \ge 0.

    Using the identity pi=∑j:j≠i(pi+pjk−1)P(y=i∣y=i or j,x)p_i = \sum_{j:j \neq i} \left(\frac{p_i + p_j}{k - 1}\right) P(y = i \mid y = i \text{ or } j, x), the first proposed approach (Method 1) computes pp as the solution to the system:

    pi=∑j:j≠i(pi+pjk−1)rij,∀i=1,…,k,subject to∑i=1kpi=1,pi≥0,  ∀i.p_i = \sum_{j:j \neq i} \left(\frac{p_i + p_j}{k - 1}\right) r_{ij}, \quad \forall i = 1, \dots, k, \quad \text{subject to} \quad \sum_{i=1}^k p_i = 1, \quad p_i \ge 0, \; \forall i.

    This system is equivalent to finding the stationary distribution of a finite Markov chain:

    Qp=p,∑i=1kpi=1,pi≥0,  ∀i,Qp = p, \quad \sum_{i=1}^k p_i = 1, \quad p_i \ge 0, \; \forall i,

    where the transition matrix Q∈Rk×kQ \in \mathbb{R}^{k \times k} is defined entrywise by:

    Qij={rijk−1if i≠j,∑s:s≠irisk−1if i=j.Q_{ij} = \begin{cases} \frac{r_{ij}}{k - 1} & \text{if } i \neq j, \\[6pt] \frac{\sum_{s:s \neq i} r_{is}}{k - 1} & \text{if } i = j. \end{cases}

    Because ∑i=1kQij=1\sum_{i=1}^k Q_{ij} = 1 for each column jj and Qij>0Q_{ij} > 0 whenever rij>0r_{ij} > 0, QQ represents an irreducible and aperiodic Markov chain. By Markov chain theory, there exists a unique solution pp with strictly positive entries (0<pi<10 < p_i < 1 for all ii).

    The solution can be computed by replacing any one equation of Qp=pQp = p with ∑i=1kpi=1\sum_{i=1}^k p_i = 1 and solving the resulting non-singular k×kk \times k square linear system via Gaussian elimination, or by power iteration (Qnp0Q^n p_0). This solution also uniquely minimizes the convex objective:

    min⁡p∑i=1k(∑j:j≠irjipi−∑j:j≠irijpj)2subject to∑i=1kpi=1,pi≥0,  ∀i.\min_p \sum_{i=1}^k \left(\sum_{j:j \neq i} r_{ji} p_i - \sum_{j:j \neq i} r_{ij} p_j\right)^2 \quad \text{subject to} \quad \sum_{i=1}^k p_i = 1, \quad p_i \ge 0, \; \forall i.

  2. Knowl 2 — Multi-Class Probability Estimation via Pairwise Quadratic Minimization

    model/method

    Let rij≈P(y=i∣y=i or j,x)r_{ij} \approx P(y = i \mid y = i \text{ or } j, x) be estimated pairwise probabilities with rij+rji=1r_{ij} + r_{ji} = 1 and rij>0r_{ij} > 0 for all i≠j∈{1,…,k}i \neq j \in \{1, \dots, k\}. The second proposed approach (Method 2) estimates the multi-class probability vector p=(p1,…,pk)Tp = (p_1, \dots, p_k)^T by minimizing the sum of squared differences over all class pairs:

    min⁡p∑i=1k∑j:j≠i(rjipi−rijpj)2subject to∑i=1kpi=1,pi≥0,  ∀i=1,…,k.\min_p \sum_{i=1}^k \sum_{j:j \neq i} (r_{ji} p_i - r_{ij} p_j)^2 \quad \text{subject to} \quad \sum_{i=1}^k p_i = 1, \quad p_i \ge 0, \; \forall i = 1, \dots, k.

    This is formulated as an equality-constrained convex quadratic program:

    min⁡p12pTQpsubject to∑i=1kpi=1,\min_p \frac{1}{2} p^T Q p \quad \text{subject to} \quad \sum_{i=1}^k p_i = 1,

    where the symmetric matrix Q∈Rk×kQ \in \mathbb{R}^{k \times k} is defined by:

    Qij={∑s:s≠irsi2if i=j,−rjirijif i≠j.Q_{ij} = \begin{cases} \sum_{s:s \neq i} r_{si}^2 & \text{if } i = j, \\[6pt] -r_{ji} r_{ij} & \text{if } i \neq j. \end{cases}

    Because vTQv=12∑i=1k∑j=1k(rjivi−rijvj)2≥0v^T Q v = \frac{1}{2} \sum_{i=1}^k \sum_{j=1}^k (r_{ji} v_i - r_{ij} v_j)^2 \ge 0 for any v∈Rkv \in \mathbb{R}^k, QQ is positive semi-definite. The global minimizer satisfies the linear KKT optimality system:

    [QeeT0][pb]=[01],\begin{bmatrix} Q & e \\ e^T & 0 \end{bmatrix} \begin{bmatrix} p \\ b \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \end{bmatrix},

    where e=(1,…,1)T∈Rke = (1, \dots, 1)^T \in \mathbb{R}^k, 00 is the k×1k \times 1 zero vector (and scalar zero in the bottom-right entry), and bb is the Lagrange multiplier associated with the constraint eTp=1e^T p = 1.

  3. Knowl 3 — Solvability and Non-negativity Properties of Method 2 Quadratic Formulation

    theoretical result

    Let Q∈Rk×kQ \in \mathbb{R}^{k \times k} have entries Qii=∑s:s≠irsi2Q_{ii} = \sum_{s:s \neq i} r_{si}^2 and Qij=−rjirijQ_{ij} = -r_{ji} r_{ij} for i≠ji \neq j, where rij>0r_{ij} > 0 and rij+rji=1r_{ij} + r_{ji} = 1 for all i≠ji \neq j.

    1. Redundancy of Non-negativity Constraints: The non-negativity constraints pi≥0p_i \ge 0 in min⁡p∑i=1k∑j:j≠i(rjipi−rijpj)2\min_p \sum_{i=1}^k \sum_{j:j \neq i} (r_{ji} p_i - r_{ij} p_j)^2 subject to ∑i=1kpi=1,pi≥0\sum_{i=1}^k p_i = 1, p_i \ge 0 are redundant. Any optimal solution to the equality-constrained problem min⁡p12pTQp\min_p \frac{1}{2} p^T Q p subject to eTp=1e^T p = 1 automatically satisfies pi≥0p_i \ge 0 for all i=1,…,ki = 1, \dots, k.

    2. Invertibility and Regularization: For any constant Δ>0\Delta > 0, the matrix Q+ΔeeTQ + \Delta e e^T is symmetric positive definite. Furthermore, the bordered saddle-point matrix:

    [QeeT0]\begin{bmatrix} Q & e \\ e^T & 0 \end{bmatrix}

    is invertible. Consequently, the linear system has a unique solution (p,b)(p, b).

    1. Strict Positive Definiteness of QQ: If for every i∈{1,…,k}i \in \{1, \dots, k\} there exist distinct indices s,j≠is, j \neq i such that:

    rsirsjris≠rjirjsrij,\frac{r_{si} r_{sj}}{r_{is}} \neq \frac{r_{ji} r_{js}}{r_{ij}},

    then QQ is strictly positive definite. When QQ is positive definite (or by replacing QQ with Q+ΔeeTQ + \Delta e e^T), Cholesky factorization can be applied directly to solve b=−1/(eTQ−1e)b = -1 / (e^T Q^{-1} e) and p=−bQ−1ep = -b Q^{-1} e.

  4. Knowl 4 — Iterative Coordinate Descent Algorithm for Method 2 Probability Estimation

    algorithm

    An iterative coordinate descent procedure solves the linear optimality system for Method 2 probability estimation, globally converging to the unique minimum of min⁡p12pTQp\min_p \frac{1}{2} p^T Q p subject to ∑i=1kpi=1,pi≥0\sum_{i=1}^k p_i = 1, p_i \ge 0.

    Input: Pairwise probabilities rij>0r_{ij} > 0 for all i≠j∈{1,…,k}i \neq j \in \{1, \dots, k\} with rij+rji=1r_{ij} + r_{ji} = 1, convergence tolerance ϵ>0\epsilon > 0.
    Output: Probability vector p=(p1,…,pk)Tp = (p_1, \dots, p_k)^T.
    Compute matrix Q∈Rk×kQ \in \mathbb{R}^{k \times k}:
      for i=1i = 1 to kk:
        Qii←∑s:s≠irsi2Q_{ii} \leftarrow \sum_{s:s \neq i} r_{si}^2
        for j=1j = 1 to k,j≠ik, j \neq i:
          Qij←−rjirijQ_{ij} \leftarrow -r_{ji} r_{ij}
    Initialize p←(1/k,…,1/k)Tp \leftarrow (1/k, \dots, 1/k)^T
    v←Qpv \leftarrow Q p
    S←pTQpS \leftarrow p^T Q p
    repeat
      for t=1t = 1 to kk:
        Δ←−vt+SQtt\Delta \leftarrow \frac{-v_t + S}{Q_{tt}}
        pt←pt+Δp_t \leftarrow p_t + \Delta
        S←S+2Δ∑j=1kvj+QttΔ2(1+Δ)2S \leftarrow \frac{S + 2\Delta \sum_{j=1}^k v_j + Q_{tt}\Delta^2}{(1 + \Delta)^2}
        for j=1j = 1 to kk:
          vj←vj+QjtΔ1+Δv_j \leftarrow \frac{v_j + Q_{jt}\Delta}{1 + \Delta}
          pj←pj1+Δp_j \leftarrow \frac{p_j}{1 + \Delta}
    until max⁡t∣vt−S∣≤ϵ\max_{t} |v_t - S| \le \epsilon
    return pp

    Each coordinate update costs O(k)O(k) operations by incrementally maintaining v=Qpv = Qp and S=pTQpS = p^T Q p rather than recomputing them in O(k2)O(k^2). Periodic recalculation of QpQp and pTQpp^T Q p (e.g., every kk iterations) prevents numerical error accumulation while preserving O(k)O(k) amortized cost per update.

  5. Knowl 5 — Unified Least-Squares Optimization Framework for Pairwise Coupling Methods

    model/method

    Four multi-class classification decision rules δ∗=arg⁡max⁡ipi\delta_* = \arg\max_i p_i based on pairwise probabilities rijr_{ij} can be unified as constrained least-squares minimization problems over pp subject to ∑i=1kpi=1\sum_{i=1}^k p_i = 1 and pi≥0p_i \ge 0 for all i=1,…,ki = 1, \dots, k:

    1. Hastie-Tibshirani Rule (δHT\delta_{HT}):

    min⁡p∑i=1k[∑j:j≠i(rij1k−12pi)]2\min_p \sum_{i=1}^k \left[ \sum_{j:j \neq i} \left( r_{ij} \frac{1}{k} - \frac{1}{2} p_i \right) \right]^2

    This formulation approximates pj≈1/kp_j \approx 1/k and rji≈1/2r_{ji} \approx 1/2 inside the sum, which ignores the differences between individual pip_i and tends to underestimate them.

    1. Method 1 (δ1\delta_1 lock-step sum balance):

    min⁡p∑i=1k[∑j:j≠i(rijpj−rjipi)]2\min_p \sum_{i=1}^k \left[ \sum_{j:j \neq i} (r_{ij} p_j - r_{ji} p_i) \right]^2

    Differences between rijpjr_{ij} p_j and rjipir_{ji} p_i cancel out within each class sum before squaring, causing it to slightly underestimate differences between pip_i.

    1. Method 2 (δ2\delta_2 pairwise sum of squares):

    min⁡p∑i=1k∑j:j≠i(rijpj−rjipi)2\min_p \sum_{i=1}^k \sum_{j:j \neq i} (r_{ij} p_j - r_{ji} p_i)^2

    1. Voting Rule (δV\delta_V):

    min⁡p∑i=1k∑j:j≠i(I{rij>rji}pj−I{rji>rij}pi)2\min_p \sum_{i=1}^k \sum_{j:j \neq i} \left( I_{\{r_{ij} > r_{ji}\}} p_j - I_{\{r_{ji} > r_{ij}\}} p_i \right)^2

    Replacing continuous probabilities rijr_{ij} with binary indicator functions I{rij>rji}I_{\{r_{ij} > r_{ji}\}} enlarges differences between classes, causing δV\delta_V to overestimate the differences between pip_i. The exact closed-form minimizer of this objective is pi=c/∑j:j≠iI{rji>rij}p_i = c / \sum_{j:j \neq i} I_{\{r_{ji} > r_{ij}\}}, whose argmax is identical to standard majority voting arg⁡max⁡i∑j:j≠iI{rij>rji}.\arg\max_i \sum_{j:j \neq i} I_{\{r_{ij} > r_{ji}\}}.

  6. Knowl 6 — Instability of Hastie-Tibshirani Coupling and Voting under Class Imbalance

    empirical result

    The performance of pairwise coupling methods was evaluated on synthetic data across varying numbers of classes k∈{4,…,128}k \in \{4, \dots, 128\} with pairwise probabilities generated as rij=pipi+pj+0.1zijr_{ij} = \frac{p_i}{p_i + p_j} + 0.1 z_{ij} (truncated to [10−7,1−10−7][10^{-7}, 1 - 10^{-7}] with standard normal zij=−zjiz_{ij} = -z_{ji}) across three true probability profiles:

    1. Balanced profile: p1=1.5/kp_1 = 1.5/k, pj=(1−p1)/(k−1)p_j = (1 - p_1)/(k - 1) for j≥2j \ge 2.
    2. Moderate imbalance: k1=⌈k/2⌉k_1 = \lceil k/2 \rceil, p1=0.95×1.5/k1p_1 = 0.95 \times 1.5/k_1, pi=(0.95−p1)/(k1−1)p_i = (0.95 - p_1)/(k_1 - 1) for i=2,…,k1i = 2, \dots, k_1, and pi=0.05/(k−k1)p_i = 0.05/(k - k_1) for i>k1i > k_1.
    3. Severe imbalance: p1=0.95×1.5/2p_1 = 0.95 \times 1.5/2, p2=0.95−p1p_2 = 0.95 - p_1, and pi=0.05/(k−2)p_i = 0.05/(k - 2) for i≥3i \ge 3.

    Empirical Findings:

    • In the balanced scenario, δHT\delta_{HT}, δ1\delta_1, δ2\delta_2, and δPKPD\delta_{PKPD} all achieve near 100% accuracy as kk increases, whereas voting (δV\delta_V) performs poorly due to tie-breaking and binary quantization when rij≈0.5r_{ij} \approx 0.5.
    • In the severely imbalanced scenario, the accuracy of δHT\delta_{HT} deteriorates drastically as kk increases (dropping toward 50% for k=128k=128). Because δHT\delta_{HT} relies on the assumption pi+pj≈2/kp_i + p_j \approx 2/k, its decision reduces to comparing ∑j≠1r1j\sum_{j \neq 1} r_{1j} and ∑j≠2r2j\sum_{j \neq 2} r_{2j}, where the signal difference is 0.50.5 while the noise term 0.1(∑z1j−∑z2j)0.1(\sum z_{1j} - \sum z_{2j}) has variance growing linearly with kk.
    • Method 1 (δ1\delta_1) and Method 2 (δ2\delta_2) remain robust against class probability imbalance, maintaining high accuracy rates (>95%>95\%) across all kk.
    • In terms of Mean Squared Error MSE=11000∑j=110001k∑i=1k(p^ij−pi)2\text{MSE} = \frac{1}{1000} \sum_{j=1}^{1000} \frac{1}{k} \sum_{i=1}^k (\hat{p}_i^j - p_i)^2, δ1\delta_1 and δ2\delta_2 achieve consistently lower MSE than δHT\delta_{HT} and δV\delta_V.

  7. Knowl 7 — Multi-Class Probability Estimation Accuracy and Stability on Real-World Datasets

    empirical result

    Pairwise coupling methods (deltaHT,δ1,δ2,δV,δPKPD\\delta_{HT}, \delta_1, \delta_2, \delta_V, \delta_{PKPD}) were evaluated using pairwise binary Support Vector Machines (with RBF kernel and Platt posterior probability calibration via nested cross-validation) and pairwise binary Random Forests (500 trees per pair) across seven benchmarks: dna (k=3k=3), waveform (k=3k=3), satimage (k=6k=6), segment (k=7k=7), USPS (k=10k=10), MNIST (k=10k=10), and letter (k=26k=26), on small (300 train / 500 test) and large (800 train / 1000 test) splits averaged over 20 runs.

    Key Observations:

    1. Classification Error: For small kk (k≤7k \le 7), test errors across all coupling methods are nearly identical. For large kk (k=10,26k = 10, 26), δ2\delta_2 and δV\delta_V systematically achieve lower error rates than δHT\delta_{HT} and δ1\delta_1. On letter (k=26k=26), δ2\delta_2 and δV\delta_V outperform δHT\delta_{HT} by over 4% classification accuracy with SVMs.
    2. Brier Score / MSE: Measuring MSE=1l∑j=1l1k∑i=1k(pij−yij)2\text{MSE} = \frac{1}{l} \sum_{j=1}^l \frac{1}{k} \sum_{i=1}^k (p_i^j - y_i^j)^2 (where yij=1y_i^j = 1 if instance jj is class ii and 0 otherwise), Method 1 (δ1\delta_1) and Method 2 (δ2\delta_2) achieve the lowest and most stable MSE values across all datasets. Voting (δV\delta_V) yields substantially worse MSE due to extreme 0/1 probability estimates, and δHT\delta_{HT} exhibits higher MSE as kk grows.
    3. Log-Likelihood: Evaluated by normalized test log-likelihood 1l∑j=1llog⁡pyjj\frac{1}{l} \sum_{j=1}^l \log p_{y_j}^j, Method 2 (δ2\delta_2) and Method 1 (δ1\delta_1) consistently yield higher likelihood values than δHT\delta_{HT}, matching the performance trends observed in MSE and accuracy.

  8. Knowl 8 — Test Errors for Exponential Loss-Based Decoding in Pairwise Multi-Class Classification

    data/table

    Exponential loss-based decoding predicts the multi-class label according to:

    predicted label=arg⁡min⁡i(∑j:j<ief^ji+∑j:j>ie−f^ij),\text{predicted label} = \arg\min_i \left( \sum_{j:j < i} e^{\hat{f}_{ji}} + \sum_{j:j > i} e^{-\hat{f}_{ij}} \right),

    where f^ij\hat{f}_{ij} is either the raw SVM pairwise decision value or the probability-centered value rij−1/2∈[−0.5,0.5]r_{ij} - 1/2 \in [-0.5, 0.5].

    Training / Testing (f^ij\hat{f}_{ij}) dna waveform satimage segment USPS MNIST letter
    300 / 500 (decision values) 10.47 16.23 14.12 6.21 11.57 14.99 38.59
    300 / 500 (rij−1/2r_{ij} - 1/2) 10.47 15.11 14.45 6.03 11.08 13.58 38.27
    800 / 1000 (decision values) 6.36 14.20 11.55 3.35 8.47 8.97 22.54
    800 / 1000 (rij−1/2r_{ij} - 1/2) 6.22 13.45 11.60 3.19 7.71 7.95 20.29

    The table reports average test error percentages across 20 random splits. Using centered probabilities rij−1/2r_{ij} - 1/2 consistently outperforms raw decision values on problems with larger numbers of classes (USPS, MNIST, letter), because the bounded range [−0.5,0.5][-0.5, 0.5] prevents exponential loss terms from being dominated by extreme decision values.

Coverage note — None was omitted; all key contributed formulations, algorithms, theoretical properties, comparative analyses, and experimental findings are covered. Proof derivations in Appendices A-C are omitted in accordance with the rule against intermediate proof steps.

References

  1. 1.E. L. Allwein, R. E. Schapire, and Y. Singer. Reducing multiclass to binary: a unifying approach for margin classifiers. Journal of Machine Learning Research, 1:113–141, 2001. ISSN 1533-7928.
  2. 2.C. L. Blake and C. J. Merz. UCI repository of machine learning databases. Technical report, University of California, Department of Information and Computer Science, Irvine, CA, 1998. Available at http://www.ics.uci.edu/~mlearn/MLRepository.html.
  3. 3.B. Boser, I. Guyon, and V. Vapnik. A training algorithm for optimal margin classifiers. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory, 1992.
  4. 4.L. Breiman. Random forests. Machine Learning, 45(1):5–32, 2001. URL citeseer.nj.nec.com/breiman01random.html.
  5. 5.G. W. Brier. Verification of forecasts expressed in probabilities. Monthly Weather Review, 78:1–3, 1950.
  6. 6.C.-C. Chang and C.-J. Lin. LIBSVM: a library for support vector machines, 2001. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.
  7. 7.C. Cortes and V. Vapnik. Support-vector network. Machine Learning, 20:273–297, 1995.
  8. 8.K. Duan and S. S. Keerthi. Which is the best multiclass SVM method? An empirical study. Technical Report CD-03-12, Control Division, Department of Mechanical Engineering, National University of Singapore, 2003.
  9. 9.J. Friedman. Another approach to polychotomous classification. Technical report, Department of Statistics, Stanford University, 1996. Available at http://www-stat.stanford.edu/reports/friedman/poly.ps.Z.
  10. 10.T. Hastie and R. Tibshirani. Classification by pairwise coupling. The Annals of Statistics, 26(1):451–471, 1998.
  11. 11.J. J. Hull. A database for handwritten text recognition research. IEEE Transactions on Pattern Analysis and Machine Intelligence, 16(5):550–554, May 1994.
  12. 12.D. R. Hunter. MM algorithms for generalized Bradley-Terry models. The Annals of Statistics, 32:386–408, 2004.
  13. 13.S. Knerr, L. Personnaz, and G. Dreyfus. Single-layer learning revisited: a stepwise procedure for building and training a neural network. In J. Fogelman, editor, Neurocomputing: Algorithms, Architectures and Applications. Springer-Verlag, 1990.
  14. 14.Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278–2324, November 1998. MNIST database available at http://yann.lecun.com/exdb/mnist/.
  15. 15.A. Liaw and M. Wiener. Classification and regression by randomForest. R News, 2/3:18–22, December 2002. URL http://cran.r-project.org/doc/Rnews/Rnews_2002-3.pdf.
  16. 16.H.-T. Lin, C.-J. Lin, and R. C. Weng. A note on Platt's probabilistic outputs for support vector machines. Technical report, Department of Computer Science, National Taiwan University, 2003. URL http://www.csie.ntu.edu.tw/~cjlin/papers/plattprob.ps.
  17. 17.D. Michie, D. J. Spiegelhalter, and C. C. Taylor. Machine Learning, Neural and Statistical Classification. Prentice Hall, Englewood Cliffs, N.J., 1994. Data available at http://www.ncc.up.pt/liacc/ML/statlog/datasets.html.
  18. 18.J. Platt. Probabilistic outputs for support vector machines and comparison to regularized likelihood methods. In A. J. Smola, P. L. Bartlett, B. Schölkopf, and D. Schuurmans, editors, Advances in Large Margin Classifiers, Cambridge, MA, 2000. MIT Press. URL citeseer.nj.nec.com/platt99probabilistic.html.
  19. 19.D. Price, S. Knerr, L. Personnaz, and G. Dreyfus. Pairwise nerual network classifiers with probabilistic outputs. In G. Tesauro, D. Touretzky, and T. Leen, editors, Neural Information Processing Systems, volume 7, pages 1109–1116. The MIT Press, 1995.
  20. 20.P. Refregier and F. Vallet. Probabilistic approach for multiclass classification with neural networks. In Proceedings of International Conference on Artificial Networks, pages 1003–1007, 1991.
  21. 21.S. Ross. Stochastic Processes. John Wiley & Sons, Inc., second edition, 1996.
  22. 22.V. Sventnik, A. Liaw, C. Tong, J. C. Culberson, R. P. Sheridan, and B. P. Feuston. Random forest: a tool for classification and regression in compound classification and QSAR modeling. Journal of Chemical Information and Computer Science, 43(6):1947–1958, 2003.
  23. 23.T.-F. Wu, C.-J. Lin, and R. C. Weng. Probability estimates for multi-class classification by pairwise coupling. In S. Thrun, L. Saul, and B. Schölkopf, editors, Advances in Neural Information Processing Systems 16. MIT Press, Cambridge, MA, 2004. URL http://www.csie.ntu.edu.tw/~cjlin/papers/svmprob.pdf.
  24. 24.E. Zermelo. Die berechnung der turnier-ergebnisse als ein maximumproblem der wahrscheinlichkeitsrechnung. Mathematische Zeitschrift, 29:436–460, 1929.
  25. 25.T. Zhang. Statistical behavior and consistency of classification methods based on convex risk minimization. The Annals of Statistics, 32(1):56–134, 2004.

Citation

MLA
Wu, T., et al. “Probability Estimates for Multi-class Classification by Pairwise Coupling”. 2003, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.5389.
APA
Wu, T., Lin, C., Weng, R. C., & Singer, Y. (2003). Probability Estimates for Multi-class Classification by Pairwise Coupling. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.5389
Chicago
Wu, T., C. Lin, R. C. Weng, and Y. Singer. 2003. “Probability Estimates for Multi-class Classification by Pairwise Coupling”. Preprint. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.5389.
Harvard
Wu, T. et al. (2003) “Probability Estimates for Multi-class Classification by Pairwise Coupling”. Available at: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.5389.
Vancouver
1. Wu T, Lin C, Weng RC, Singer Y (2003) Probability Estimates for Multi-class Classification by Pairwise Coupling.

BibTeX

@article{wu2003probability,
  title = {Probability Estimates for Multi-class Classification by Pairwise Coupling},
  author = {Wu, Tingfan and Lin, Chih‐Jen and Weng, Ruby C. and Singer, Yoram},
  year = {2003},
  url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.5389}
}
Metadata:DOI registry

Access the Paper

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

Open PDF

License: https://creativecommons.org/licenses/by/4.0/