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 →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
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.
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 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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)
- [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.
- [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.
- [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)
- [Sec. 1] There is a repeated typo 'OV A and OV A' in the second paragraph; one of these should likely be 'OVO'.
- [Sec. 2.2] The phrase 'assigning deliberate weigmost of previoushts' appears garbled; it should be rewritten.
- [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.
- [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.
- [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
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
free parameters (4)
- code length L =
min(5*log2(K-1)+1, K/2)
- decoding learning rate gamma1 =
0.1
- coding matrix learning rate gamma2 =
0.2
- starting round i_s =
30
assumptions (4)
- standard math ECOC framework: a coding matrix and a decoding strategy can represent multiclass classification as a set of binary problems.
- domain assumption Softmax can approximate the argmax decoding step and preserves error-correcting properties.
- 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.
- domain assumption Base learner outputs lie in [-1,1] so that |M_kj - o_j| can be expanded as 1 + M_kj o_j.
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
Reference graph
Works this paper leans on
-
[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
work page 2012
-
[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
work page 2000
-
[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
work page 2001
-
[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
work page 2017
-
[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
work page 1999
-
[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
work page 2015
-
[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
work page 2012
-
[8]
Multi-class support vector machines
Jason Weston and Chris Watkins. Multi-class support vector machines. Technical report, Citeseer, 1998
work page 1998
Show all 35 references
-
[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
2009
-
[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
2014
-
[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
2017
-
[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
2016
-
[13]
Learning machines
Nils J Nilsson, Terrence J Sejnowski, and Halbert White. Learning machines. 1965
1965
-
[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
1998
-
[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
1995
-
[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
2002
-
[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
2009
-
[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
2006
-
[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
2008
-
[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
2012
-
[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
2013
-
[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
2014
-
[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
2009
-
[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
2013
-
[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
2012
-
[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
2014
-
[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
2006
-
[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
2010
-
[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
2013
-
[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
2018 arXiv
-
[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
2011
-
[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
2015
-
[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
2015
-
[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
2000
-
[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
2017
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.