Pith. sign in

REVIEW 3 major objections 5 minor 35 references

LightMC: A Dynamic and Efficient Multiclass Decomposition Algorithm

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Pith's one-line read LightMC learns the error-correcting code and its decoder during training, beating fixed ECOC.

desk verdict A genuinely new differentiable ECOC training scheme with solid empirical gains, undermined by a proxy-gradient coding update and a missing ablation; worth refereeing. read the letter →

arxiv 1908.09362 v1 pith:MMZFBPH7 submitted 2019-08-25 cs.LG cs.AI

classification cs.LGcs.AI
keywords multiclassclassificationerror-correctingoutputcodesECOCcodingmatrixsoftmaxdecodingbackpropagationlarge-scaledynamicdecomposition
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

LightMC is a decomposition method for multiclass classification that tries to eliminate the most expensive and uncertain part of the error-correcting output code (ECOC) approach: the choice of a code matrix and a decoding rule before training. The paper's central claim is that both can be made differentiable and optimized by backpropagation together with the binary base learners, so that even a random initial code converges to an effective one. If true, this matters because ECOC's promise of encoding class correlations and using few base learners has been limited by the NP-hard difficulty of code design, especially on large-scale problems. The experiments compare LightMC against one-versus-all and a fixed ECOC baseline on datasets with up to about 14,000 classes and 5.5 million samples, reporting lower test error and shorter convergence time.

What carries the argument

The mechanism is the softmax decoding function $\hat y = \operatorname{softmax}(t_k)$ with $t_k = \frac{1}{2}(\theta_k^\top o + L)$, where $\theta_k$ is the $k$-th row of the trainable decoding matrix initialized from the coding matrix. It is a differentiable surrogate for the two non-differentiable operations in classic ECOC decoding, namely sign and argmin, turning the whole system into a softmax classifier whose input is the vector of base-learner outputs. That single-layer form carries the argument: the decoding parameters can be updated by ordinary gradient descent, and the coding matrix can then be updated by backpropagating the loss into the base-learner targets using class-averaged gradients. The paper alternates these updates with base-learner training, which is how the code adapts to class correlations during training.

What would settle it

A decisive check is to compare the class-averaged gradient used for the code update against a finite-difference gradient of the held-out loss with respect to each code entry $M_{kj}$ on a small dataset; if the two directions consistently disagree, the coding-matrix update can lower training loss while raising test error, and the central accuracy claim would fail.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that ECOC decoding can be rewritten as a single-layer softmax regression, which makes the entire decomposition trainable end-to-end. The original decoding chooses the class minimizing $\frac{1}{2}\sum_j |M_{kj} - \operatorname{sgn}(o_j)|$; removing the sign and replacing argmin with softmax gives $t_k = \frac{1}{2}\sum_j (1 + M_{kj}o_j)$, i.e. $\hat y = \operatorname{softmax}(\theta_k^\top o + b_k)$ with $\theta_k$ initialized to the class code. This differentiable decoder lets the paper backpropagate cross-entropy loss into the decoding parameters, and then into the code matrix itself by using the class-averaged output gradients $\frac{1}{|\Omega_k|}\sum_{i\in\Omega_k} G_{ij}$ as a proxy for $\partial J/\partial M_{kj}$. The algorithm alternates base-learner training with these decoding and coding updates, and the reported experiments show that the code matrix evolves so that similar classes move closer and dissimilar classes move apart.

Load-bearing premise

The load-bearing premise is that averaging the per-sample error signals within a class gives the right direction to adjust that class's code entry, even though the paper concedes this is exactly correct only when base learners are perfect.

Editorial extensions

If this is right

  • ECOC-based multiclass classification no longer needs a separate code-design phase; a random initial coding matrix can be refined during training to reach accuracy comparable to a deliberately designed one.
  • With code length logarithmic in the number of classes, the method scales to thousands of classes, where one-versus-all training time is prohibitive.
  • The learned code matrix gives a readable record of class correlations: distances between related classes shrink and distances between unrelated classes grow as training proceeds.
  • The extra computation per update is only that of a single-layer softmax, so the efficiency gain over fixed ECOC comes mainly from removing the pre-training code search.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the same code-matrix update should carry over to differentiable base learners such as neural networks, where the softmax decoder could replace the final output layer; the paper mentions this as future work, not as a tested result.
  • Editorial inference: running LightMC with the coding-matrix update disabled would isolate whether the accuracy gain comes from the learned code or from the trainable decoder alone.
  • Editorial inference: treating each label as a class suggests a natural extension to multilabel classification with a learned label code, though the paper only converts a multilabel dataset to multiclass by sampling one label per point.
  • Editorial inference: the alignment between the class-averaged proxy gradient and a validation-set gradient could be used to set the code learning rate $\gamma_2$ adaptively.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proposes LightMC, a multiclass decomposition algorithm that jointly trains base learners with a dynamically optimized ECOC coding matrix and a differentiable decoding strategy. The decoding step is rewritten as a softmax over a linear transformation of base-learner outputs, which is equivalent to a single-layer linear softmax classifier. The coding matrix is then updated using a class-averaged gradient of the loss with respect to the base-learner outputs. Experiments on five large-scale datasets compare LightMC against OVA and an evolutionary ECOC baseline, reporting lower test error and shorter convergence time, and also show that initializing from a random coding matrix is competitive.

Significance. If the central claim is substantiated, LightMC would be a practically useful contribution: it removes the expensive pre-training coding-matrix search of ECOC, scales to datasets with thousands of classes, and improves accuracy over fixed-code baselines. The paper deserves credit for the clean observation that the L1-distance decoding rule can be rewritten as a linear softmax, for evaluating on unusually large public benchmarks, and for reporting both accuracy and wall-clock convergence time. However, the paper's central technical step, the coding-matrix update of Sec. 3.3, is a heuristic proxy rather than a true gradient, and the experiments do not isolate the contribution of this update from the contribution of the learned decoding layer. The empirical results are suggestive but do not yet establish the claimed dynamic optimization of the coding matrix.

major comments (3)
  1. [Sec. 3.3, Eq. (4)] The update rule for the coding matrix is not a true gradient of the loss with respect to M. The derivation assumes perfect base learners satisfying o_i^j = M_{y_i,j}; the paper itself acknowledges that dJ/dM_kj is not equal to G_ij for imperfect learners. Averaging G_ij over i in Omega_k does not restore the missing chain-rule term do_i^j/dM_kj; for a LightGBM ensemble, changing a code entry changes subsequent boosting rounds and leaf values, so do_i^j/dM_kj is neither identity nor zero. Consequently, there is no descent guarantee, and the assertion in Sec. 3.3 that the coding matrix can be 'definitely refined to reduce the loss' is unsupported. Please either derive a valid gradient or a justified approximation, or explicitly present the rule as a heuristic and validate it with an ablation.
  2. [Sec. 4.2, Table 2] The experiments do not separate the two components of LightMC: the learned decoding parameters Theta and the dynamic coding-matrix update. Since Theta is a free linear softmax initialized at M, the reported accuracy gains over ECOC could in principle come entirely from TrainDecoding on a fixed coding matrix. To support the central claim that optimizing the coding matrix improves accuracy, the paper should add configurations with (i) fixed M and learned Theta, and (ii) dynamic M with fixed decoding. Without this ablation, the contribution of the coding-matrix update is not established.
  3. [Sec. 3.2, Eqs. (2)-(3)] The equivalence between Eq. (2) and Eq. (3) relies on the identity | -M_kj - o_j | = 1 + M_kj o_j, which holds only when the base-learner output o_j is in [-1,1] (or, for the binary-probability case, in [0,1]). This bounded-output assumption is not stated. The base learners used in the experiments, LightGBM trained with binary log loss, produce probability outputs in [0,1], so the assumption may hold in practice, but it should be stated explicitly and verified; otherwise the softmax decoding form in Eq. (3) is not equivalent to the distance-based decoding in Eq. (2) for out-of-range outputs.
minor comments (5)
  1. [Sec. 1] There is a repeated typo 'OV A and OV A' in the second paragraph; one of these should likely be 'OVO'.
  2. [Sec. 2.2] The phrase 'assigning deliberate weigmost of previoushts' appears garbled; it should be rewritten.
  3. [Tables 2 and 3] 'Domz' should be 'Dmoz' in both tables. Also, the last column of Table 3, 'Coding Matrix', should be labeled more clearly to indicate that it refers to the ECOC coding-matrix search time.
  4. [Sec. 4, Figure 2 and Table 4] Figure 2 and Table 4 are corrupted in the manuscript text, with unreadable escape sequences; they need to be regenerated so that the convergence curves and class-pair distances are legible.
  5. [Sec. 4.1] The experimental setup should state how many repeated runs were used to compute the reported standard deviations, and should specify the random seed or initialization procedure for the random coding matrix used by LightMC(R).

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the coding-matrix update is an acknowledged approximation, and all accuracy claims rest on held-out public benchmarks.

full rationale

The paper's derivation chain is self-contained. The differentiable decoding strategy in Eq. (2) is rewritten into Eq. (3) as a single-layer softmax model; this is an algebraic identity, not a result that presupposes the paper's conclusions. TrainDecoding uses standard gradient descent on a softmax cross-entropy loss, and TrainCodingMatrix uses Eq. (4), which the authors explicitly state is an approximation because perfect base learners do not exist in practice. The proxy-gradient update is heuristic, but it is not circular: the reported accuracy improvements come from test-error measurements on public datasets, not from re-inserting fitted values into the claim. The initial coding matrix is set equal to the ECOC baseline for comparability, and a random-initialization variant LightMC(R) is also evaluated, so the central results are not forced by construction. The self-citation to LightGBM is only a base-learner implementation used uniformly across all methods and is not load-bearing for the dynamic coding-matrix claim. The admitted limitation that training a fixed softmax layer can yield similar accuracy in some settings is an honest caveat rather than evidence of circularity. Overall, no prediction reduces to its own input by definition, and no self-citation chain carries the argument.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

No new particles, forces, or entities are introduced. The main load-bearing assumptions beyond standard ECOC are the softmax-as-argmax approximation and, most importantly, the per-class average-gradient proxy for the coding-matrix derivative, which the authors acknowledge is not the true gradient.

free parameters (4)
  • code length L = min(5*log2(K-1)+1, K/2)
    Chosen by the authors as a heuristic, not fitted to data but not derived from first principles. It directly controls the number of base learners and affects both accuracy and efficiency.
  • decoding learning rate gamma1 = 0.1
    Hand-picked hyperparameter for the softmax decoder update, used in all experiments without sensitivity analysis.
  • coding matrix learning rate gamma2 = 0.2
    Hand-picked hyperparameter for the coding-matrix update, used in all experiments without sensitivity analysis.
  • starting round i_s = 30
    Controls when coding/decoding optimization begins for boosting learners. The authors state this is an efficiency choice, but it is ad hoc and can affect final accuracy.
assumptions (4)
  • standard math ECOC framework: a coding matrix and a decoding strategy can represent multiclass classification as a set of binary problems.
    Standard background from Dietterich and Bakiri (1995) used throughout the paper.
  • domain assumption Softmax can approximate the argmax decoding step and preserves error-correcting properties.
    The paper follows Escalera et al. (2010) to justify replacing sgn and argmin with L1 distance and softmax. The authors acknowledge this is an approximation but assert it is differentiable while retaining the error-correcting property.
  • ad hoc to paper The average gradient over samples in a class is a valid proxy for the gradient of the loss with respect to the coding matrix.
    The paper explicitly notes that dJ/dM_kj is not equal to G_ij because base learners are imperfect, and then defines the update in Eq. 4 using per-class averages. This is an invention for this paper, not a standard result.
  • domain assumption Base learner outputs lie in [-1,1] so that |M_kj - o_j| can be expanded as 1 + M_kj o_j.
    The derivation of Eq. 3 requires o_j in [-1,1] (or at least bounded such that the absolute value signs can be removed as stated). The paper does not mention this restriction or normalize the outputs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of LightMC: A Dynamic and Efficient Multiclass Decomposition Algorithm." pith.science (2026). https://pith.science/paper/MMZFBPH7

@misc{pith2026190809362,
  author       = {Pith},
  title        = {Pith review of: LightMC: A Dynamic and Efficient Multiclass Decomposition Algorithm},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MMZFBPH7}},
  note         = {Machine review of arXiv:1908.09362}
}
read the original abstract

Multiclass decomposition splits a multiclass classification problem into a series of independent binary learners and recomposes them by combining their outputs to reconstruct the multiclass classification results. Three widely-used realizations of such decomposition methods are One-Versus-All (OVA), One-Versus-One (OVO), and Error-Correcting-Output-Code (ECOC). While OVA and OVO are quite simple, both of them assume all classes are orthogonal which neglect the latent correlation between classes in real-world. Error-Correcting-Output-Code (ECOC) based decomposition methods, on the other hand, are more preferable due to its integration of the correlation among classes. However, the performance of existing ECOC-based methods highly depends on the design of coding matrix and decoding strategy. Unfortunately, it is quite uncertain and time-consuming to discover an effective coding matrix with appropriate decoding strategy. To address this problem, we propose LightMC, an efficient dynamic multiclass decomposition algorithm. Instead of using fixed coding matrix and decoding strategy, LightMC uses a differentiable decoding strategy, which enables it to dynamically optimize the coding matrix and decoding strategy, toward increasing the overall accuracy of multiclass classification, via back propagation jointly with the training of base learners in an iterative way. Empirical experimental results on several public large-scale multiclass classification datasets have demonstrated the effectiveness of LightMC in terms of both good accuracy and high efficiency.

Figures

Figures reproduced from arXiv: 1908.09362 by the authors.

Figure 1
Figure 1. The general learning procedure of LightMC. [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Convergence curves on Aloi and LSHTC1 datasets. with ECOC, LightMC increases the accuracy by about 3% (relatively), and improves 5.88% at the best case on the LSHTC1 dataset. As for the speed, LightMC also uses less time than ECOC to converge. These results clearly indicate that LightMC can further reduce the overall loss by dynamically refining the coding and decoding strategy as expected. We can also find that, wh… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

35 extracted references · 34 canonical work pages

  1. [1]

    Multi-column deep neural networks for image classification

    Dan Ciregan, Ueli Meier, and Jürgen Schmidhuber. Multi-column deep neural networks for image classification. In Computer vision and pattern recognition (CVPR), 2012 IEEE conference on, pages 3642–3649. IEEE, 2012

  2. [2]

    Text classification from labeled and unlabeled documents using em

    Kamal Nigam, Andrew Kachites McCallum, Sebastian Thrun, and Tom Mitchell. Text classification from labeled and unlabeled documents using em. Machine learning, 39(2-3):103–134, 2000

  3. [3]

    The e-commerce product classification challenge

    Ellen Schulten, Hans Akkermans, Guy Botquin, Martin Dörr, Nicola Guarino, Nelson Lopes, and Norman Sadeh. The e-commerce product classification challenge. IEEE Intelligent systems, 16(4):86–89, 2001

  4. [4]

    Application of machine learning on brain cancer multiclass classification

    V Panca and Z Rustam. Application of machine learning on brain cancer multiclass classification. In AIP Conference Proceedings, volume 1862, page 030133. AIP Publishing, 2017

  5. [5]

    Multicategory classification by support vector machines

    Erin J Bredensteiner and Kristin P Bennett. Multicategory classification by support vector machines. In Computational Optimization, pages 53–79. Springer, 1999

  6. [6]

    Logarithmic time online multiclass prediction

    Anna E Choromanska and John Langford. Logarithmic time online multiclass prediction. In Advances in Neural Information Processing Systems, pages 55–63, 2015

  7. [7]

    Multiclass learning with simplex coding

    Youssef Mroueh, Tomaso Poggio, Lorenzo Rosasco, and Jean-Jeacques Slotine. Multiclass learning with simplex coding. In Advances in Neural Information Processing Systems, pages 2789–2797, 2012

  8. [8]

    Multi-class support vector machines

    Jason Weston and Chris Watkins. Multi-class support vector machines. Technical report, Citeseer, 1998

Show all 35 references
  1. [9]

    Multi-label prediction via compressed sensing

    Daniel J Hsu, Sham M Kakade, John Langford, and Tong Zhang. Multi-label prediction via compressed sensing. In Advances in neural information processing systems, pages 772–780, 2009

  2. [10]

    Fastxml: A fast, accurate and stable tree-classifier for extreme multi-label learning

    Yashoteja Prabhu and Manik Varma. Fastxml: A fast, accurate and stable tree-classifier for extreme multi-label learning. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 263–272. ACM, 2014

  3. [11]

    Gradient boosted decision trees for high dimensional sparse output

    Si Si, Huan Zhang, S Sathiya Keerthi, Dhruv Mahajan, Inderjit S Dhillon, and Cho-Jui Hsieh. Gradient boosted decision trees for high dimensional sparse output. In International Conference on Machine Learning , pages 3182–3190, 2017

  4. [12]

    Pd-sparse: A primal and dual sparse approach to extreme multiclass and multilabel classification

    Ian En-Hsu Yen, Xiangru Huang, Pradeep Ravikumar, Kai Zhong, and Inderjit Dhillon. Pd-sparse: A primal and dual sparse approach to extreme multiclass and multilabel classification. In International Conference on Machine Learning, pages 3069–3077, 2016

  5. [13]

    Learning machines

    Nils J Nilsson, Terrence J Sejnowski, and Halbert White. Learning machines. 1965

  6. [14]

    Classification by pairwise coupling

    Trevor Hastie and Robert Tibshirani. Classification by pairwise coupling. In Advances in neural information processing systems, pages 507–513, 1998

  7. [15]

    Solving multiclass learning problems via error-correcting output codes

    Thomas G Dietterich and Ghulum Bakiri. Solving multiclass learning problems via error-correcting output codes. Journal of artificial intelligence research, 2:263–286, 1995

  8. [16]

    On the learnability and design of output codes for multiclass problems

    Koby Crammer and Yoram Singer. On the learnability and design of output codes for multiclass problems. Machine learning, 47(2-3):201–233, 2002

  9. [17]

    Traffic sign recognition using evolution- ary adaboost detection and forest-ecoc classification

    Xavier Baró, Sergio Escalera, Jordi Vitrià, Oriol Pujol, and Petia Radeva. Traffic sign recognition using evolution- ary adaboost detection and forest-ecoc classification. IEEE Transactions on Intelligent Transportation Systems, 10(1):113–126, 2009

  10. [18]

    Discriminant ecoc: A heuristic method for application dependent design of error correcting output codes

    Oriol Pujol, Petia Radeva, and Jordi Vitria. Discriminant ecoc: A heuristic method for application dependent design of error correcting output codes. IEEE Transactions on Pattern Analysis and Machine Intelligence , 28(6):1007–1012, 2006

  11. [19]

    Evolving output codes for multiclass problems

    Nicolas Garcia-Pedrajas and Colin Fyfe. Evolving output codes for multiclass problems. IEEE Transactions on Evolutionary Computation, 12(1):93–106, 2008

  12. [20]

    Minimal design of error-correcting output codes

    Miguel Ángel Bautista, Sergio Escalera, Xavier Baró, Petia Radeva, Jordi Vitriá, and Oriol Pujol. Minimal design of error-correcting output codes. Pattern Recognition Letters, 33(6):693–702, 2012

  13. [21]

    A genetic-based subspace analysis method for improving error-correcting output coding

    Mohammad Ali Bagheri, Qigang Gao, and Sergio Escalera. A genetic-based subspace analysis method for improving error-correcting output coding. Pattern Recognition, 46(10):2830–2839, 2013

  14. [22]

    On the design of an ecoc-compliant genetic algorithm

    Miguel Ángel Bautista, Sergio Escalera, Xavier Baró, and Oriol Pujol. On the design of an ecoc-compliant genetic algorithm. Pattern Recognition, 47(2):865–884, 2014

  15. [23]

    Spectral error correcting output codes for efficient multiclass recognition

    Xiao Zhang, Lin Liang, and Heung-Yeung Shum. Spectral error correcting output codes for efficient multiclass recognition. In Computer Vision, 2009 IEEE 12th International Conference on, pages 1111–1118. IEEE, 2009. 9 A PREPRINT - AUGUST 27, 2019

  16. [24]

    Sparse output coding for large-scale visual recognition

    Bin Zhao and Eric P Xing. Sparse output coding for large-scale visual recognition. In Computer Vision and Pattern Recognition (CVPR), 2013 IEEE Conference on, pages 3350–3357. IEEE, 2013

  17. [25]

    Thinned-ecoc ensemble based on sequential code shrinking

    Nima Hatami. Thinned-ecoc ensemble based on sequential code shrinking. Expert Systems with Applications, 39(1):936–947, 2012

  18. [26]

    Multiclass from binary: Expanding one-versus-all, one-versus-one and ecoc-based approaches

    Anderson Rocha and Siome Klein Goldenstein. Multiclass from binary: Expanding one-versus-all, one-versus-one and ecoc-based approaches. IEEE Transactions on Neural Networks and Learning Systems, 25(2):289–302, 2014

  19. [27]

    Ecoc-one: A novel coding and decoding strategy

    Sergio Escalera and Oriol Pujol. Ecoc-one: A novel coding and decoding strategy. In Pattern Recognition, 2006. ICPR 2006. 18th International Conference on, volume 3, pages 578–581. IEEE, 2006

  20. [28]

    On the decoding process in ternary error-correcting output codes

    Sergio Escalera, Oriol Pujol, and Petia Radeva. On the decoding process in ternary error-correcting output codes. IEEE transactions on pattern analysis and machine intelligence, 32(1):120–134, 2010

  21. [29]

    Distributed representations of words and phrases and their compositionality

    Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. In Advances in neural information processing systems, pages 3111–3119, 2013

  22. [30]

    Fix your classifier: the marginal value of training the last weight layer

    Elad Hoffer, Itay Hubara, and Daniel Soudry. Fix your classifier: the marginal value of training the last weight layer. arXiv preprint arXiv:1801.04540, 2018

  23. [31]

    Libsvm: a library for support vector machines

    Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3):27, 2011

  24. [32]

    Inferring networks of substitutable and complementary products

    Julian McAuley, Rahul Pandey, and Jure Leskovec. Inferring networks of substitutable and complementary products. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 785–794. ACM, 2015

  25. [33]

    Image-based recommendations on styles and substitutes

    Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. Image-based recommendations on styles and substitutes. In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 43–52. ACM, 2015

  26. [34]

    Reducing multiclass to binary: A unifying approach for margin classifiers

    Erin L Allwein, Robert E Schapire, and Yoram Singer. Reducing multiclass to binary: A unifying approach for margin classifiers. Journal of machine learning research, 1(Dec):113–141, 2000

  27. [35]

    Lightgbm: A highly efficient gradient boosting decision tree

    Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie-Yan Liu. Lightgbm: A highly efficient gradient boosting decision tree. In Advances in Neural Information Processing Systems, pages 3149–3157, 2017. 10

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.