REVIEW 3 major objections 4 minor 40 references
Efficient computation of counterfactual explanations of LVQ models
T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read For LVQ classifiers, a counterfactual explanation is an exact LP or convex QP under a global metric and an efficiently approximated QCQP under prototype-specific metrics.
desk verdict Solid LP/QP encodings for LVQ counterfactuals; the LGMLVQ empirical claims need a feasibility report before they are fully trusted. 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 load-bearing object is Eq. (9), the per-target-prototype program: minimize $\theta(\vec x', \vec x)$ subject to $d(\vec x', \vec p_i)+\epsilon \le d(\vec x', \vec p_j)$ for every prototype $\vec p_j$ whose label differs from the requested label $y_c$. The small positive $\epsilon$ keeps the counterfactual off the decision boundary. Expanding the distance inequality gives linear constraints $\vec x'^\top \vec q_{ij} + r_{ij} + \epsilon \le 0$ when one global metric $\Omega$ is used, and quadratic constraints $\tfrac{1}{2}\vec x'^\top Q_{ij}\vec x' + \vec x'^\top \vec q_{ij} + r_{ij} + \epsilon \le 0$ with $Q_{ij}=\Omega_i-\Omega_j$ when metrics are prototype-specific. The indefinite difference matrix is what turns the localized-metric case into an NP-hard non-convex QCQP; the paper's approximate route splits each constraint into a difference of convex functions $f(\vec x')-g(\vec x')\le 0$, linearizes $g$ around the current iterate, and uses the penalty convex-concave procedure within the Suggest-Improve framework.
What would settle it
Run the approximate solver for the localized-metric counterfactual program on a test set, check constraint (9b) exactly for each returned point, and count violations; if a substantial fraction violate the constraint, the reported mean distances for the localized-metric case would not represent valid counterfactuals.
Extended reading notes
Core claim
The central claim is that because an LVQ model labels a point by its nearest prototype, a counterfactual for a desired label $y_c$ can be obtained by solving, for each prototype $\vec p_i$ with label $y_c$, the problem of minimizing the change $\theta(\vec x', \vec x)$ under the constraints $d(\vec x', \vec p_i) + \epsilon \le d(\vec x', \vec p_j)$ for every prototype $\vec p_j$ of a different label, then keeping the solution with the smallest change. When all prototypes share one metric, the constraints are linear in $\vec x'$, so the problem is a linear program (weighted Manhattan regularization) or a convex quadratic program (Euclidean regularization) and can be solved exactly and efficiently. When each prototype or class has its own metric, the constraints become quadratic with matrices $Q_{ij}=\Omega_i-\Omega_j$, which are symmetric but indefinite, making the problem a non-convex QCQP that the paper solves approximately by rewriting it as a difference of convex functions and applying the penalty convex-concave procedure. On breast cancer, handwritten digits, and house-price data, the method returns counterfactuals with smaller mean Manhattan distance than Downhill-Simplex or CMA-ES baselines and runs 1.5 to 158 times faster.
Load-bearing premise
For localized-metric LVQ, the paper relies on an approximate solver returning points that genuinely satisfy the nearest-prototype constraints, but it reports the failure rate of the baselines only, not its own solver's validity rate.
Editorial extensions
If this is right
- For any LVQ with a global metric, counterfactual computation becomes an off-the-shelf LP or convex QP, removing the need for expensive black-box search and giving exact or unique (up to equivalence) solutions.
- Because Eq. (9) has no regularization hyperparameter $C$, counterfactual selection no longer depends on tuning a loss-versus-change trade-off.
- Domain knowledge such as box constraints, frozen features, or linear inequalities between features can be added as convex constraints without changing the problem class or its complexity.
- The per-target-prototype loop parallelizes directly, so runtime scales with the number of prototypes carrying the requested label.
- Experiments report smaller mean Manhattan distances and speedups between 1.5 and 158 times over Downhill-Simplex and CMA-ES baselines, with the baselines failing to find any counterfactual in 5% to 60% of localized-metric cases.
Reading between the lines
- The same reduction should apply to any nearest-prototype classifier whose distance is a quadratic form, such as metric-based nearest-centroid classifiers; convexity depends only on whether each prototype has its own distance matrix.
- A reader extending the method should measure the fraction of approximate QCQP solutions that actually satisfy constraint (9b); the paper only reports failure rates for the baseline methods, so an invalid-solution count would clarify whether the localized-metric comparison is representative.
- Counterfactuals computed in a PCA-reduced space may not be minimal in the original feature space; an extension would enforce the constraints and measure the change directly in the original space.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper addresses efficient computation of counterfactual explanations for learning vector quantization (LVQ) classifiers. The authors formulate the search for a counterfactual x' with desired label yc as minimizing a change penalty theta(x', x) subject to d(x', p_i) + eps <= d(x', p_j) for a chosen target prototype p_i of label yc and every prototype p_j of another label. For global-metric LVQ (GLVQ/GMLVQ) the constraints are linear, yielding an LP for weighted Manhattan and a convex QP for Euclidean regularization. For localized matrix LVQ (LGMLVQ) the constraints form a non-convex QCQP, which the authors propose to solve approximately with the Suggest-Improve framework using penalty CCP. Experiments on three datasets compare mean Manhattan distances with Downhill-Simplex and CMA-ES baselines and report speed-ups of 1.5 to 158 times. The algebraic derivations in Section 6 are self-contained and the convex reductions are exact.
Significance. The central reduction is valuable and largely sound. The derivation of the linear constraints for global-metric LVQ is exact, the formulation is free of fitted parameters, and the release of code supports reproducibility. The identification of LGMLVQ counterfactuals as a difference-of-convex program is a useful observation. If the empirical gaps described below are closed, the paper would provide a practical improvement over black-box counterfactual search for prototype classifiers. The current experimental support is incomplete for the local-metric case, so the full strength of the claims is not yet established.
major comments (3)
- [Section 4.4, Table 1] The LGMLVQ comparison is not currently interpretable because the success rate of the proposed approximate solver is not reported. The caption only reports that DS/CMA-ES fail in 5% to 60% of cases for LGMLVQ; no analogous information is given for the 'Ours' column. Since the QCQP in Eq. (14) is NP-hard and the penalty CCP heuristic can return points violating the constraints in Eq. (9b), the reported mean Manhattan distances for LGMLVQ may be computed over a biased subset (if infeasible solutions were discarded) or may not correspond to valid counterfactuals (if constraint violations were accepted). Please report the fraction of runs in which the returned solution satisfies all constraints of Eq. (14), and either report means over all runs or explicitly separate feasible and infeasible outcomes.
- [Section 4.4, Table 1] The experimental comparison reports only mean Manhattan distances over 4-fold cross-validation, with no standard deviations, confidence intervals, or significance tests. Some differences are small (e.g., LGMLVQ digits: 8.12 vs 7.88 vs 7.53), and without variance information the claim that the proposed method yields counterfactuals that are closer is not statistically supported. Add error bars, per-fold values, or a statistical test.
- [Section 4.4] The efficiency claim that the method is between 1.5 and 158.0 times faster is stated without reporting actual runtime measurements or the experimental setup for timing. Since efficiency is one of the two main empirical contributions, please include a table of runtimes with variance and describe the hardware/software environment.
minor comments (4)
- [Section 4.1, Eq. (9)] The statement that the formulation 'does not include hyperparameters' is imprecise because the margin epsilon in Eq. (9b) is a user-chosen constant; rephrase to say there is no regularization-weight hyperparameter C as in Eq. (1).
- [Appendix 6.3, Eq. (24)] In the expansion of d(x', p_i) < d(x', p_j), the term p_j^T Omega_i p_j should read p_j^T Omega_j p_j; the subsequent definition of r_ij in Eq. (27) is consistent with the corrected version.
- [Appendix 6.3, Eq. (28) and Eq. (31)] The left-hand sides of these equivalences are written as d(x, p_i) < d(x, p_j) but should refer to x'; the constraints are about the counterfactual x'.
- [Section 4.1] The assertion that p_i is always feasible in Eq. (9) assumes the distance functions are positive definite; for PSD localized matrices another prototype could be at zero distance from p_i, making the epsilon margin infeasible. Please state the required positive-definiteness assumption or describe how ties are handled.
Circularity Check
No significant circularity: the counterfactual optimization is derived directly from the LVQ decision rule, with no fitted parameter renamed as a prediction.
full rationale
The derivation chain is self-contained. Eq. (9) is obtained directly from the LVQ winner-takes-all rule (Eq. 5): a counterfactual has label yc iff its nearest prototype has label yc, so for each target prototype p_i the constraints d(x',p_i)+eps <= d(x',p_j) for all p_j with other labels exactly characterize the desired classification. This is not a disguised restatement of the generic loss-based objective Eq. (1); Eq. (1) is only the starting point, while Eq. (9) is a model-specific exact reformulation that eliminates the loss term and the hyperparameter C. The algebraic reductions in Appendix 6.3 (Eqs. 24-33) convert the quadratic distance constraints into linear inequalities for a global metric (Q_ij=0) and into non-convex QCQP constraints for prototype-specific metrics, matching Eqs. (12)-(14). No parameter is fitted to the reported results: the weighted-Manhattan weights are defined by the standard inverse-median-absolute-deviation choice (Eq. 3), and the convex solvers (cvxpy, cvx-qcqp) are external. The empirical comparison uses external baselines (Downhill-Simplex, CMA-ES via ceml). Self-citations [23], [24], [33] define the LVQ model variants and the baseline toolbox; they do not carry the counterfactual derivation. Two non-circular weaknesses should be noted. First, the claim in Section 4.1 that the feasible region of Eq. (9) is 'always non-empty' is not generally true: if a prototype of another label lies within distance epsilon of p_i, then p_i itself violates the constraint, making that target-prototype subproblem infeasible; the paper does not discuss handling such cases. Second, Section 4.4 reports baseline failure rates for LGMLVQ ('in 5% to 60% of the cases no solution was found') but does not report the success or feasibility rate of its own cvx-qcqp Suggest-Improve solves for the non-convex QCQP, so the LGMLVQ 'Ours' entries could include invalid or discarded solutions; this is an empirical-validity gap, not circularity, and does not affect the exact convex global-metric claims.
Assumptions & free parameters
free parameters (1)
- epsilon margin in Eq. (9b)
assumptions (5)
- domain assumption LVQ classifiers assign the label of the nearest prototype (Eq. 5)
- domain assumption Distance matrices Omega_p are symmetric positive semidefinite, guaranteed by the factorization Omega_p = Omega~_p^T Omega~_p (Eq. 8)
- standard math Standard convex solvers (cvxpy) correctly solve the LP and QP problems
- ad hoc to paper The penalty CCP / Suggest-Improve heuristic returns a feasible point for the non-convex QCQP
- ad hoc to paper Replacing strict inequalities d(x',p_i) < d(x',p_j) by d(x',p_i)+epsilon <= d(x',p_j) does not materially change the closest counterfactual
Cite this review
Pith. "Pith review of Efficient computation of counterfactual explanations of LVQ models." pith.science (2026). https://pith.science/paper/GBRGIIVW
@misc{pith2026190800735,
author = {Pith},
title = {Pith review of: Efficient computation of counterfactual explanations of LVQ models},
year = {2026},
howpublished = {\url{https://pith.science/paper/GBRGIIVW}},
note = {Machine review of arXiv:1908.00735}
}
read the original abstract
The increasing use of machine learning in practice and legal regulations like EU's GDPR cause the necessity to be able to explain the prediction and behavior of machine learning models. A prominent example of particularly intuitive explanations of AI models in the context of decision making are counterfactual explanations. Yet, it is still an open research problem how to efficiently compute counterfactual explanations for many models. We investigate how to efficiently compute counterfactual explanations for an important class of models, prototype-based classifiers such as learning vector quantization models. In particular, we derive specific convex and non-convex programs depending on the used metric.
Reference graph
Works this paper leans on
-
[1]
Sharad Goel, Justin M. Rao, and Ravi Shroff. Precinct or pr ejudice? understanding racial disparities in new york city’s stop-and-frisk policy. 2016
work page 2016
-
[2]
How algorithms can bring down minorities ’ credit scores
Kaveh W addell. How algorithms can bring down minorities ’ credit scores. The Atlantic, 2016
work page 2016
-
[3]
Amir E. Khandani, Adlar J. Kim, and Andrew Lo. Consumer cr edit-risk models via machine-learning algorithms. Journal of Banking & Finance, 34(11):2767–2787, 2010
work page 2010
-
[4]
General data protecti on regulation
European parliament and council. General data protecti on regulation. https://eur-lex.europa.eu/eli/reg/2016/679/oj, 2016
work page 2016
-
[5]
Leilani H. Gilpin, David Bau, Ben Z. Yuan, Ayesha Bajwa, M ichael Specter, and Lalana Kagal. Explaining explanations: An overview of interpreta bility of machine learning. In 5th IEEE International Conference on Data Science and Advanced Analytics, DSAA 2018, Turin, Italy, October 1-3, 2018 , pages 80–89, 2018
work page 2018
-
[6]
A survey of methods for explaining black box models
Riccardo Guidotti, Anna Monreale, Salvatore Ruggieri, Franco Turini, Fosca Giannotti, and Dino Pedreschi. A survey of methods for explaining black box models. ACM Comput. Surv., 51(5):93:1–93:42, August 2018
work page 2018
-
[7]
A Survey on Explainable Artificial Intelligence (XAI): Towards Medical XAI
Erico Tjoa and Cuntai Guan. A survey on explainable artifi cial intelligence (XAI): towards medical XAI. CoRR, abs/1907.07374, 2019
work page Pith review arXiv 1907
-
[8]
W ojciech Samek, Thomas Wiegand, and Klaus-Robert M¨ ull er. Explainable artificial in- telligence: Understanding, visualizing and interpreting deep learning models. CoRR, abs/1708.08296, 2017
arXiv 2017
Show all 40 references
-
[9]
Interpretable Machine Learning
Christoph Molnar. Interpretable Machine Learning. 2019. https://christophm.github.io/interpretable-ml-book/
2019
-
[10]
Model-agnostic interpretability of machine learning
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin . Model-agnostic interpretability of machine learning. In ICML W orkshopon Human Interpretability in Machine Learning (WHI), 2016
2016
-
[11]
Greenwell, Bradley C
Brandon M. Greenwell, Bradley C. Boehmke, and Andrew J. McCarthy. A simple and effective model-based variable importance measure. CoRR, abs/1805.04755, 2018
2018 arXiv
-
[12]
A ll Models are W rong but many are Useful: Variable Importance for Black-Box, Proprietar y, or Misspecified Prediction Models, using Model Class Reliance
Aaron Fisher, Cynthia Rudin, and Francesca Dominici. A ll Models are W rong but many are Useful: Variable Importance for Black-Box, Proprietar y, or Misspecified Prediction Models, using Model Class Reliance. arXiv e-prints, page arXiv:1801.01489, Jan 2018
2018 arXiv
-
[13]
Causal interpretatio ns of black-box models
Qingyuan Zhao and Trevor Hastie. Causal interpretatio ns of black-box models. Journal of Business & Economic Statistics, 0(ja):1–19, 2019
2019
-
[14]
”why should i trust you?”: Explaining the predictions of any classifier
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin . ”why should i trust you?”: Explaining the predictions of any classifier. In Proceedings of the 22Nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’16, pages 1135–1144, New York, NY, USA, ...
2016
-
[15]
Local rule-based explanations of blac k box decision systems
Riccardo Guidotti, Anna Monreale, Salvatore Ruggieri , Dino Pedreschi, Franco Turini, and Fosca Giannotti. Local rule-based explanations of blac k box decision systems. CoRR, abs/1805.10820, 2018
2018 arXiv
-
[16]
Aamodt and E
A. Aamodt and E. Plaza. Case-based reasoning: Foundati onal issues, methodological variations, and systemapproaches. AI communications, 1994
1994
-
[17]
Example s are not enough, learn to criticize! criticism for interpretability
Been Kim, Oluwasanmi Koyejo, and Rajiv Khanna. Example s are not enough, learn to criticize! criticism for interpretability. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona...
2016
-
[18]
Understanding black-box p redictions via influence func- tions
Pang W ei Koh and Percy Liang. Understanding black-box p redictions via influence func- tions. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017 , pages 1885–1894, 2017
2017
-
[19]
Mittelstadt, and Chris Russel l
Sandra W achter, Brent D. Mittelstadt, and Chris Russel l. Counterfactual explana- tions without opening the black box: Automated decisions an d the GDPR. CoRR, abs/1711.00399, 2017
2017 arXiv
-
[20]
CE RTIF AI: counterfactual explanations for robustness, transparency, interpretabi lity, and fairness of artificial intel- ligence models
Shubham Sharma, Jette Henderson, and Joydeep Ghosh. CE RTIF AI: counterfactual explanations for robustness, transparency, interpretabi lity, and fairness of artificial intel- ligence models. CoRR, abs/1905.07857, 2019
1905 arXiv
-
[21]
Comparison-based inverse classification for i nterpretability in machine learn- ing
Thibault Laugel, Marie-Jeanne Lesot, Christophe Mars ala, Xavier Renard, and Marcin Detyniecki. Comparison-based inverse classification for i nterpretability in machine learn- ing. In Information Processing and Management of Uncertainty in Knowledge-Based Systems. Theory and Fo...
2018
-
[22]
Est´ evez
David Nova and Pablo A. Est´ evez. A review of learning ve ctor quantization classifiers. Neural Comput. Appl., 25(3-4):511–524, September 2014
2014
-
[23]
Ad aptive relevance matrices in learning vector quantization
Petra Schneider, Michael Biehl, and Barbara Hammer. Ad aptive relevance matrices in learning vector quantization. Neural Computation, 21(12):3532–3561, 2009. PMID: 19764875
2009
-
[24]
Di stance learning in discriminative vector quantization
Petra Schneider, Michael Biehl, and Barbara Hammer. Di stance learning in discriminative vector quantization. Neural Computation, 21(10):2942–2969, 2009. PMID: 19635012
2009
-
[25]
A life-long learning vector quantization approach for interactive lea rning of multiple categories
Stephan Kirstein, Heiko W ersing, Horst-Michael Gross , and Edgar K¨ orner. A life-long learning vector quantization approach for interactive lea rning of multiple categories. Neural networks : the official journal of the International Neural Network Society , 28:90– 105, 04 2012
2012
-
[26]
Interpretable co unterfactual explanations guided by prototypes
Arnaud Van Looveren and Janis Klaise. Interpretable co unterfactual explanations guided by prototypes. CoRR, abs/1907.02584, 2019
1907 arXiv
-
[27]
Rafael Poyiadzi, Kacper Sokol, Ra´ ul Santos-Rodrigue z, Tijl De Bie, and Peter A. Flach. F ACE: feasible and actionable counterfactual explanations. CoRR, abs/1909.09369, 2019
1909 arXiv
-
[28]
Convex Optimization
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, New York, NY, USA, 2004
2004
-
[29]
General heuristics for n onconvex quadratically con- strained quadratic programming
Jaehyun Park and Stephen Boyd. General heuristics for n onconvex quadratically con- strained quadratic programming. arXiv preprint arXiv:1703.07870, 2017
2017 arXiv
-
[30]
Mangasarian William H
Olvi L. Mangasarian William H. W olberg, W. Nick Street. Breast cancer wisconsin (diag- nostic) data set. https://archive.ics.uci.edu/ml/datasets/Breast+Cancer+Wisconsin+(Diagnostic), 1995
1995
-
[31]
Alpaydin and C
E. Alpaydin and C. Kaynak. Optical recognition of handw ritten digits data set. https://archive.ics.uci.edu/ml/datasets/Optical+Recognition+of+Handwritten+Digits , 1998
1998
-
[32]
Ames, iowa: Alternative to the boston hous ing data as an end of semester regression project
Dean De Cock. Ames, iowa: Alternative to the boston hous ing data as an end of semester regression project. Journal of Statistics Education, 19(3), 2011
2011
-
[33]
Ceml: Counterfactuals for explaining m achine learning models - a python toolbox
Andr´ e Artelt. Ceml: Counterfactuals for explaining m achine learning models - a python toolbox. https://www.github.com/andreArtelt/ceml, 2019
2019
-
[34]
Python tutorial
Guido Van Rossum and Fred L Drake Jr. Python tutorial. Centrum voor Wiskunde en Informatica Amsterdam, The Netherlands, 1995
1995
-
[35]
CVXPY: A Python-embed ded modeling language for convex optimization
Steven Diamond and Stephen Boyd. CVXPY: A Python-embed ded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1–5, 2016
2016
-
[36]
A cvxpy extension for han dling nonconvex qcqp via suggest-and-improve framework
Jaehyun Park and Stephen Boyd. A cvxpy extension for han dling nonconvex qcqp via suggest-and-improve framework. https://github.com/cvxgrp/qcqp, 2017
2017
-
[37]
sklearn-lvq
Joris Jensen. sklearn-lvq. https://github.com/MrNuggelz/sklearn-lvq, 2017
2017
-
[38]
Chris Colbert, and Ga¨ el Varoqu aux
St´ efan van der W alt, S. Chris Colbert, and Ga¨ el Varoqu aux. The numpy array: A structure for efficient numerical computation. Computing in Science and Engineering, 13(2):22–30, 2011
2011
-
[39]
Sci Py: Open source scientific tools for Python, 2001–
Eric Jones, Travis Oliphant, Pearu Peterson, et al. Sci Py: Open source scientific tools for Python, 2001–
2001
-
[40]
Pedregosa, G
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. T hirion, O. Grisel, M. Blon- del, P. Prettenhofer, R. W eiss, V. Dubourg, J. Vanderplas, A . Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Mach ine learning in Python. Journal of Machine Le...
2011
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.