Bridging performance gap between minimal and maximal SVM models
Authors: Ondrej Such
René Fabricius
Venue: Accepted by TMLR ()

Abstract: Multi-class support vector machine (SVM) models are typically built using all possible pairs of binary SVM in a one-against-one fashion. This requires too much computation for datasets with hundreds or thousands of classes,  which motivates the search for multi-class models that do not use all pairwise SVM.  Our models correspond to the choice of the model graph, whose vertices correspond to classes and edges represent which pairwise SVMs are trained. We conduct experiments to uncover metrical and topological properties that impact the accuracy of a multi-class SVM model. Based on their results we propose a way to construct intermediate multi-class SVM models. The key insight is that for model graphs of diameter two, we can estimate missing pairwise probabilities from the known ones thus transforming the computation of posteriors to the usual complete (maximal) case. Our proposed algorithm allows one to reduce computational effort by 50-80% while keeping accuracy near, or even above that of a softmax classifier. In our work we use convolutional data sets, which have multiple advantages for benchmarking multi-class SVM models.

Published in Transactions on Machine Learning Research (March/200)
Bridging performance gap between minimal and maximal SVM models
Ondrej Such
ondrejs@savbb.kk
Mathematical institute of Slovak Academy of Sciences Dumbierska Bonská Bystrica, 974 01, Slovakia
René Fabricius
rene.fabriciussjfr..o uniza..
Paculty of Management and Informatics Zilinská Universita Ziine
Univerzilnd 8215/1 Zilina, 010 26, Slovakia
Reviewed on OpenReview:
openneevee.. net/ forum? id= SNIBkjGePT
Abstract
Multi-class support vector machine (SVM) models are typically built using all possible pairs of binary SVM in one-against-one fashion. This requires too much computation for datasets with hundreds class models that do not use all pairwise SVM. Our models correspond to the choice of the model graph, whose verlices correspond to classes and edges represent which pairwise SVMs are trained. We conduct experiments to uncover metrical and topological properties that impact the accuracy of multi-class SVM model. Based on their results we propose a way construct intermediate multi-class SVM models. The key insight that for model graphs of diameter two, ones thus transforming the computation of posteriors to the usual complete (maximal) case. Our proposed algorithm allows one to reduce computational effort by 50-80% while keeping accuracy near, or even above that of softmax classifier. In our work we use convolutional data sets, which have multiple advantages for benchmarking multi-class SVM models.
thousands of classes, which motivates the search for multi-
estimate missing pairwise probabilities from the known
1 Introduction
With ever-increasing computational capacity requirements needed for training deep neural networks, transfer learning has emerged cost-effective alternative for constructing classification models for computer vision and related application areas (Bengio) 2012 Niu et al. 2020). One method and the one that motivates work, to prepare transfer learning model to start with neural network pre-trained
computer vision dataset D such as Imagenet (Huh et al. 2016 extract activations of neurons from the penultimate layer on the target dataset D' and use these features to train a classifier model M' for D'.
If it. reasonable assume that the boundaries among classes are linear, then one may opt build M' by training a multinomial regression (softmax) model. The main potential drawback softmax classifiers is that location of class boundaries may be skewed by the presence of outliers in the dataset. This drawback could be addressed by instead choosing support vector machine model (SVM) for building classifier M', For SVM the presence of outliers does not affect the learned boundary since outliers do not contribute to the loss function of SVM (Cortes & Vapnik 1995). Moreover, while vanilla SVM learns linear class boundaries, more general kernel SVM is capable of learning a diversity of nonlinear class boundaries.
The underlying goometric concept of SVM, the division of space by a hyperplanc into two halfspaces, is a natural fit for two-class classification problens. To apply SVM to multi-class classification problems one usually constructs ensemble of SVM for multiple two--lass problems and classifies by combining the

---

Published in Transactions on Machine Learning Research MMrchh20223
predictions of the ensemble's elements. For smaller datasets with a few tens of classes, SVM is a suitable alternative to softmax for building M' (see e.g. Maitra et al. 2015 Raghu et al. (2020)) )
It is increasingly common to have datasets with hundreds or thousands of different classes. For such datasets, building an SVM model using common SVM software libraries may become prohibitively expensive in terms of computational cost. The focus of our work is to investigate the possibility to reduce the computational cost to build an SVM model for a dataset where the number of classes C' is large (say C C2 50). Although motivated by transfer learning, we are seeking a general method applicable to datasets unrelated to neural networks, and more general SVM kernels, notably the popular radial (RBF) kernel. Also, aim to build probabilistic models which are more flexible in applications, and were shown to perform better than voting ensembles (Wu et al. 2004 Duan & Keerthi 2005).
Previous works successfully investigated the more specialized problem of coopting SVM with a neural net- work (Tang] 2013 Passricha & Aggarwal 2019). Thousand class Imagenet classification using an SVM modification on 2048 features from convolutions nelwork was achieved by Do (2021). Speeding up of SVM training by finding an approximate solution was proposed by Cao & Boley (2006). For linear kernels, the work of Fan et al. (2008) specifically aims for large datasets SVM classification.
1.1 Complexity of building SVM models
The computational cost of multiclass SVM for larger datasets is driven by two factors. The first is the nunber of individual SVM problems that need to be solved. For some approaches, the number of required models grows quadratically with the number of classes, The second factor is the cost to train each SVM. The training time of binary SVM scales superlinearly with the number of training samples (Rifkin & Klautan 2004). Therefore it may well be beneficial to train a larger number of binary SVM for smaller datasets than to train a smaller number of binary SVM for larger datasets. Let us briefly examine this tradeoff by comparing the complexity of four popular approaches implemented in libraries LIBSVM (Chang & Lin 2011), scikit-lcarn (Pedregosa et al.] 2011), LIBLINEAR (Fan et al.) 2008). and cvx-opt (Andersen et al. 2020 In the discussion below we will use the estimated time complexity of training a single SVM with the radial kernel as reported in Table 2
A very common approach to train SVM classifiers for all pairs of classes, which entails building C(C- 1)/2 models. This approach is called one-vs-one (OVO), or sometimes all-vs-all (AVA). This yields an ensemble of classifiers, and proposed methods to combine its clements into final classification include voting, building Directed Acyclic Graph (Hsu & Lin 2002), or pairwise coupling (Chang & Lin 2011 Hastie & Tibshirani
1998).
Another common approach is to train SVM classifiers soparating each class from the rest of the training dataset, which requires training C SVM classifiers. This approach is called one-vs-all (OVA), or one-vs-rest. It yields models of similar accuracy to OVO (Rifkin & Klautau 2004 Galar et al. 2011 For the 50 class subset of Imagenet studied in this paper, we found that the training complexity of each SVM for radial kernel may be approximated as ~ C1.5, which makes this method asymptotically slower (complexity ~ 2255) than the one-vs-one model, which has complexity ~ C². A similar conclusion was reported by Fürnkranz (2022)
A method by Crammer and Singer (Crammer & Singer 2001) modifies SVM to directly solve the multiclass problem without resorting to an ensemble. Documentation of the scikit-learn library notes however "while crammer-singer is interesting from a theoretical perspective as it is consistent, is seldom used practice as it rarcly leads to better accuracy and more expensive to compute [than OVA]" (scikit-lcarn, 2023).
Finally, let us mention error-correctng output codes (ECOC) which is method inspired by coding theory DDetterrcch & Bakiri 1994). It chooses fixed-length code of length L and assigns codeword to each class. A binary classifier is then trained for cach bit, resulting in the need to train L classifiers. ECOC models encompass a wide range of models depending on the code chosen, including the OVA model for L = C. We will analyze one variant of ECOC for the code achieving the lower bound on L which is [log, C7. Suppose C C= 24. A decision by a single ECOC SVM provides at most one bit of information. It provides exactly one bit of information, if and only if the number of classes for both negative and positive samples is C/2. For the 50 class Imagenet dataset, we model that. the complexity of building such an SVM model is 2
2

---

Published in Transactions on Machine Learning Research MMarch/2023
which translates to the overall complexity of ~ C log(C), thus being approximately equal to the quadratic cost of the OVO model. Given that training SVM for this ECOC model involves many more samples than the OVO model, on computers or graphic cards with limited memory, the OVO method will likely be much faster.
Despite OVO being asymptotically the fastest algorithm, quadratic complexity makes impractical for larger values of C. To make it faster, we propose construct a multi-class SVM model by training only subset of all possible pairwise SVMs. We will refer to the subset as the model graph with vertices corresponding to the classes.
1.2 Minimal, maximal, and intermediate models
The starting point of our investigation is the observation (see Section 2.5 that an SVM model can be built by training just C - 1 binary SVMs, each trained in a one-vs-one fashion, and then converted to a probabilistic model using Platt's method (Platt al.) 1999). We refer to these models as minimal models. There are many minimal models since minimal models are one-to-one correspondence with spanning trees C vertices. Minimal models are faster to train than other multi-class SVM algorithms. The training time advantage comes cost of decreased accuracy of minimal models, benchmark, we compare the minimal models with a commonly used coupling methodology that requires all (2) pairwise binary SVMs trained in a one-vs-one fashion. We refer to the latter as mazimal models.
show in Section 3.. As a
Guided by the Pareto principle, we investigate the possibility to increase the accuracy of minimal models by incrementally adding moderate amount of additional binary SVMs to capture most of the accuracy advantage of the maximal model. We will answer the following key questions needed to formulate viable algorithm to construct such intermediate models:
Q1. how to choose the initial set of C' - 1 binary SVMs,
Q2. how to make a multi-class prediction using a non-complete set of probabilistic binary SVMs trained in a one-vs-one fashion,
Q3. how to choose which binary SVM to incrementally train and add to the multi-class model.
2
Experimental methodology
2.1 Software used for experiments and analysis
For computations of SVM, we use R package c1071 R Core Team 2021 Meyer et al. 2020 For data processing, we use tidyverse (Wickham et al. 2019) and for visualizations package ggplot2 Wiikham 2016
The source repository can be found on http:://gttaab..cm/mneeee-aaao /vvm3
2.2 Datasets
In this work, we use datasets for classilying images based input features to the final softmax layer of a convolutional neural network. This class of problems has several compelling attributes for benchmarking SVM algorithms, namely
the set of classes is well definod (o.g. in comparison with much less clear phoneme classes speech processing),
benchmark image datasets have been thoroughly examined for the correctness of annotation; more- over, the correctness of annotation can be easily assessed by a layperson,
convolutional neural networks are trained with the softmax layer high classification accuracy, which suggests that. inter-class boundaries are close to linear,
3

---

Published in Transactions on Machine Learning Research (March/200) /2023)
Datasct name
Classes
# samples when training
# samples when training SVM (per class)
# samples the testing dataset (per class)
Image resolution
# of SVM features
neural network (per class)
CIFAR-10
10
6000
10000
1000
32x32
512
Imagenette
10
2 1000
10000
50
variable
512
Imagewoof
10
2 1000
10000
50
variable
512
Imagenet-50
50
1000
10000
variable
512
Table 1: Summary datasets used in the experiments. Train samples for SVM include augmented data samples.
digital image classification has widespread applications, and any potential improvements would be quite valuable.
An overview of the datasets used throughout the paper is summarized in Table The number of classes was selected to balance the requirements of being able to run multiple experiments to get error bounds and to represent a large-class SVM problem while being within our computational capacity.
In sections and 4 we have used three datasets each having ten classes: CLFAR-10 (Krizhevsky et al. 2009
Imagenette, and Imagewoof (Howard, 2022), the latter two being subsets of the well-known Imagenet 2012 al., 2015). In section
dataset (Russakovsky classes at random among the thousand classos in ImageNet 2012. We refer the set Imagenct-50. Its classes are listed in the subdirectory imagenet. subsets of the code repository. We have tried to model the time complexity T of fitting single radial SVM depending on the number of classes C' encompassing two binary classes. We use the simple linear regression model
have used a subset of Imagenet created by choosing 50
log(T)) = a + 3 log(()) +
Values of C were taken at random between 10 and 21, and we tried two kinds of groupings of C' classes into positive and negative samples OVA and ECOC. For the latter, only even values C were considered. The results are summarized in Table
Grouping OVA ECOC
# of positive classes
# of negative classes
Std. error of
Adjusted R²
C-1
1.5
0.1
0.94
C/2
C/2
2.1
0.08
0.99
Table 2: Parameters of lincar models
fitted to timing data.
2.3
Neural networks
For CIFAR-10 we have used custom architecture by David C. Page, which can be quickly trained to 94% accuracy PPge 2019 For Imagenette and Imagewoof datasets, we used the Resnet-18 network (He et al. 2016 This architecture was designed to solve the Imagenet classification problem, which has 1000 classes. We have trained 20 instances of each architecture on CIFAR-10 and Imagenet respectively. From the networks, extracted convolutional features in experiments in this paper (the exception being the experiment in section 3.5)
2.4 Pairwise models for convolutional data sets
Given a convolutional neural network trained, we proceed by extracting the activations of the penultimate layer chosen dataset. All network architectures in this paper 512 neurons in this layer. These 512

---

Published in Transactions on Machine Learning Research (March/20P)
activations constitute features of our convolutional data sets. Each training matrix had 10000 entries per class, which included all training samples and also augmented data samples.
The next step is the computation of pairwise likelihoods for each pair of classes One could do this by simply training an SVM model and applying Platt's method to estimate the likelihoods on the test data. However, we employ a slight modification akin to the procedure used in the foundational study of Wu et al. (2004). Namely, we divide 10000 samples into four equal-sized subsets and train an SVM for each subset. We apply Platt's method to derive pairwise likelihoods for each of the four models and then average resulting probabilities using geometric mean. An immediate advantage is the reduction of training time, since the training time of SVM scales superlinearly with training size (Abdiansah & Wardoyo, 2015 Morcover, by averaging, one may expect to arrive at more precise likelihoods.
We used default parameters for the svm function from the e1071 library. In particular, data were scaled, and we used default kernel and cost parameters.
2.5 Probabilistic prediction for minimal and maximal models
Consider a general multi-class classification problem of assigning to a given sample a probabilistic distribution p = (PI,...PPc) among classes. For simplicity, we will index the C classes by integers from one C.
Suppose pairwise SVM models are trained for some subset E' of edges of the complete graph on C vertices 1.2...., C. We assume that for any edge (f,j) in E the corresponding model M.j gives probabilistic prediction i.e. predicts that with probability rig the sample belongs to class i, and with probability raj it belongs to the class j. We note that throughout this paper Tty will always be positive which allows us to avoid dogenerate cases.
If the model MA, were the Bayesian classifier then the so-called Bradley-Tery equation would hold (Hastie & Tibshirani 1998):
P:
rij
(2)
Pi + Pj
which we can rewrite as
Túj P
Pj
(3)
Tsj
The last equation shows that if any ps is known, then we can deduce the value of any other Py for j's that are connected to i by path in E.
If E. forms spanning tree then, then all probabilities pæ are uniquely determined by the total probability requirement
Σ 11
1=1
The case when E forms spanning tree is the mánimal subset of SVM models required to deduce multi-class probability distribution (pt).
It is more common to consider the mazimal case when E corresponds to all edges of the complete graph on C vertices. Since pairwise models Ms,j will be only approximations to Bayesian classifiers, one may expect that Bradley-Terry equations will not consistent and thus the complete set of Bradley-Terry equations will be over-determined.
There are multiple ways to solve the equations, but the most common is (the second) method of Wu-Lin Weng Wu et al. 2004), which we abbreviate as WLW2. It estimates p by minimizing the quadratic form
min Σ p
Σ
(rrip: p2
5

---

Published in Transactions on Machine Learning Research (March/200)
3 Comparisons of methods to construct SVM models
In this section, present the results of targeted experiments that compare different methods to construct SVM models to discern the optimal one. We start by confirming that there is indeed performance gap between the minimal and maximal models and proceed with experiments that suggest answers to the three questions Q1 Q3 from the introduction: which model graph to start with, how to combine predictions in a non-complete model graph, and which edges to add to a graph. We will use 3-6 class subsets of ten class subsets CTF,R-10, Imagenette, and Imagewoof, mainly because using smaller datasets allows to repeat experiments. All results reported in this section are averaged over 20 different networks.
3.1 The performance gap between minimal and maximal models
We start by comparing minimal and maximal models three class problems. Our hypothesis is that
maximal models perform better than minimal ones.
Suppose there are classes C1. C2, and C3 that we want to classify. We can train three pairwise SVM models: M12 discriminaling C₁ from C2 and similarly M13 and M23- From these we can construct three minimal models: the first MM, by combining {M1,, M13), the second M M2 by combining (M12, M23), and the third MM, by combining (M1s, M23). Finally, method which combines predictions of M12, M13, and M23- Denote the test error rate of model MM, by m. and the test error rate of the maximal model by w. Finally, set.
construct the maximal model by using the WLW2 coupling
m m1 m2 + m3
(4)
3 min(m1, m2, ms)
(5)
We evaluated mean values and standard errors of m, and b for each ten class dataset when C1, C22 and Cg varied over all (2) possible triples of classes. The results are shown in Table
Dataset
Kernel
m
W
cifar10 cifar10
linear
2.1 (1.5)
1.9 (1.4)
1.9 (1.4)
radial
2.0 (1.4)
2.0 (1.4)
2.0 (1.4)
imagenette linear
1.0 (0.8)
0.6 (0.6)
0.5 (0.6)
imagenette radial
0.6 (0.6)
0.6 (0.6)
0.5 (0.5)
imagewoof linear
3.2 (3.5)
2.5 (3.3)
2.3 (3.3)
imagewool radial
2.7 (3.2)
2.5 (3.2)
2.3 (3.1)
Table 3: Comparison of test. errors for average minimal, maximal models, and the best minimal models trained on triplets of classes. The mean values are reported before parentheses, the standard errors are inside parentheses.
The results confirm our hypothesis, since the maximal model outperforms the mean minimal models four out of six times, with the other two cases being tied (both for radial kernel). Somewhat surprisingly, the best minimal model is better that the maximal model four out of six times, with the other two cases (cifar-10) being tied. This indicates that there are cases when the maximal model may be inferior not only due to the expensive quadratic complexity with respect to the number of classes but also in terms of the accuracy of the resulting classifier.
3.2 Selecting the best initial minimal model
We will now investigate the answer to question Q1, namely what is the best minimal model to start. building larger ones.
The model graphs of minimal models correspond to spanning trees on the of vertices. With a growing number of classes the number of spanning trees grows quickly. Tn fact, for C classes there CC-2 different

---

Published in Transactions on Machine Learning Research (larch/2023)
trees. It is infeasible to try every out of them even for moderate values of C, even though the final result of the previous section indicated it may yield performance superior to the maximal model.
Our intuition is that deduction of likelihoods along longer paths using 3 compounds errors, and therefore it would be better to have a spanning tree where paths are as short as possible. Based on this intuition we formulate the hypothesis that best to use a spanning tree of diameter two. To verify this hypothesis we consider five class classification problems. For five classes there are three isomorphism classes of spanning trees as shown in Figure 1
G2
G3
Figure 1: Troes on five vertices
In Table 4 we report on average errors made by the various models for 200 randomly selected 5-class subsets of ten classes datasets.
Dataset cifar10
Kernel
G4
G3
G2
linear
4.7 (2.4)
4.4 (2.1)
4.1 (1.6)
cifar10
radial
3.6 (1.4)
3.6 (1.3)
3.5 (1.3)
imagenette lincar
2.9 (2.2)
2.5 (2.0)
2.2 (1.6)
imagenette
radial
1.2 (0.7)
1.2 (0.7)
1.1 (0.7)
imagewoof
linear
7.4 (4.1)
6.9 (3.9)
6.4 (3.8)
imagcwoof radial
5.2 (3.2)
5.1 (3.2)
5.0 (3.1)
Table 4: Comparison of error rates of minimal and maximal models on five class subsets. Mean values are reported before parentheses, standard errors inside parentheses.
Among the minimal models, the corresponding to a star on five vertices (G2) is the most accurate in all six cases. Graph G3 was more accurate than G4 in four out of six cases, with the remaining two (both for radial kernel) being tied.
This experiment indicates that it advantageous use spanning tree diameter two. There is up to isomrrphism only one such tree for any value of C, namely the star. Therefore we propose use the star graph (with randomly chosen center) as the starting point for building incremental SVM models.
3.3 How to make predictions for non-complete model graphs
Now we turn to the second question from the introduction, namely suppose we are given a non-complete set of SVM trained a onc-vs-one fashion, how build from them a classification model. Our solution is the most direct one, namely, manufacturng pairwise likelihood for the missing pairs and using a standard WLW2 coupling method to deduce predicted distribution over the classes. The key insight is that if we have

---

Published in Transactions on Machine Learning Research (larch/2023)
estimate Oi of Ps/Pk and estimate okj of pk/Ps then estimate
pi pi/ps Ock
(6)
Pk/Ps okj
Now if, we start building an incremental model with a star centered at K, then when a model discriminating class and j is missing we can always use (6) with k K' to get an estimate of p:/Py- There may be however other values of k for which both pi/ps and pk /Pj are known from binary SVM models. The question is how to combine them. We provide evidence that simple averaging is sufficient with two experiments.
In the first experiment, we select four classes C1, C2 C3, and C4 from ten-class dataset and use four pairwise SVM: the one discriminating C₁ from C2, the one discriminating C₂ from C3, the one discriminating C3 from C4 and the one discriminating C4 from C₁. Then we compute the correlation of estimates of log(p1/ /Pa) using = 2 and = 4, as well as the correlation of estimates of (og(p2/p) using k = and k 3. We repeat this 200 times for each dataset and kernel. The results are shown Table
Dataset
Kernel
Mean correlation Standard deviation
cifar10 linear
0.986
0.009
cifar10
radial
0.992
0.004
imagenette
linear
0.973
0.017
imagenette
radial
0.994
0.005
imagewoof linear
0.963
0.029
imagewoof
radial
0.992
0.005
Table 5: Correlation between estimates of log odds of pairwise likelihoods using different in 6
We can see that estimates highly correlated, which means fitting even simple linear model would be unstable. This suggests using the average of log odds to combine predictions. Another alternative, possibly more robust, would be the median, and we evaluate it in our second experiment. For this experiment, we choose a six-class subset of ten class dataset and assume the model graph is the complete bipartite graph K3.3- For each missing SVM, we can estimate using three different choices of We repeat 200 times for each dataset and kernel. The results are shown in Table
Dataset Kernel cifar10
median
mean
linear
4.3 (1.3)
4.2 (1.3)
cifar10 radial
4.1 (1.2)
4.1 (1.2)
imagenette
lincar
1.5 (0.6)
1.4 (0.6)
imagenette
radial
1.2 (0.5)
1.2 (0.5)
imagewoof
linear radial
5.9 (3.1)
5.8 (3.0)
imagewoof
5.6 (2.8)
5.6 (2.8)
Table 6: Comparison of error rates of models on six class subsets of ten class datascts when mean versus median are used for aggregation of estimates using Mean values are reported before parentheses, standard errors inside parentheses.
We can see that the results are very close, with the mean edging the median by minimal margin in the case of the linear kernel. We conclude that averaging of predictions appears to be suitable way of aggregating multiple estimates using (). Explicitly we will use the estimate
1/10Gt
Pi
II KEO
Osk
Pi
Okj
where Oz the set of classes l for which estimates of both ps/ Ps/pi and pk/ are known from pairwise model.
8

---

Published in Transactions on Machine Learning Research (March/200 /2023)
3.4 Choosing which model to incrementally add
In this section we tackle the third question Q3 posed in the introduction, that is which models to incrementally add to maximize accuracy. Our intuition that it is most valuable to add the SVM corresponding to the hardest unsolved one-vs-one classification problem. We conducted experiment four-class subsets of ten class datasets aiming to confirm this hypothesis.
We started with a star graph on four vertices which has 3 edges. We selected 200 samples from the training set for each class. We computed the confusion matrix X corresponding to the star graph for the chosen samples and let = x be the symmetrized confusion matrix. Then we measured accuracy after adding each of the remaining three edges in the complete graph on 4 vertices. We named the three possible models A1, A2, and A3, with Al corresponding to adding edge having the smallest entry in Y, while A3 having the largest entry in Y. We did this for all possible arrangements and computed averages and error rates which are shown in Table 7 In five out of six cases, model A3 turned out to be best, with the remaining case tied. We conclude that our hypothesis turned out to be true in these cases.
Dataset cifar10
Kernel
A1
A2
A3
linear
3.1 (1.6)
3.0 (1.6)
2.8 (1.4)
cifar10
radial
2.8 (1.4)
2.8 (1.4)
2.8 (1.4)
imagenette
lincar
1.6 (1.3)
1.4 (1.2)
1.0 (0.7)
imagenette
radial
0.9 (0.7)
0.9 (0.6)
0.8 (0.6)
imagewoof
linear
4.8 (3.7)
4.6 (3.7)
3.8 (3.3)
imagewoof
radial
3.9 (3.2)
3.8 (3.2)
3.6 (3.2)
Table 7: Comparison of error rates of intermediate SVM model depending on which edge was added to the minimal one. Mean values reported before parentheses, standard errors are inside parentheses.
3.5 Proposed algorithm
Let explicate proposed algorithm based on the experiments in the previous section.
Algorithm Incremental multi-class SVM model creation
1: procedure GROw SVM(T, V)
# Argument 7 is training dataset with N classes
3: # Argument V is a validation dataset (possibly V CT)
4:
Choose a spanning tree with star topology random. Denote by E the set of its edges.
for e (i,j) E E do Train the probabilistic pairwise SVM model distinguishing classes i and
8: Set step +-1
Set F to be the complement E the set of edges of the complete graph on N vertices.
10:
while F nonempty do
11:
yield(tuple(step= i, model graph E))
12:
Compute confusion matrix X on V using 7 to fill missing pairwise odds
13:
Set Y X + X'
14:
Choose an edge f= (i,j) in F such Yú = max Ymn Train probabilistic pairwise SVM model on S distinguishing classes and j
15:
16:
Set F F {f}
17:
Sct E Eu-EUp
One possible concern about the algorithm the need for a validation datasct. In the previous scction, we used subset of the train set. We devised an experiment verify that the choice does not have a significant. impact the accuracy of the model. For the imagenette dataset, we trained 20 networks, but
9

---

Published in Transactions on Machine Learning Research (larch/2023)
linear
0.89
model
accuracy
Trasgened
max1-edge
0.88
max3
max2
0.87
10
20
30
40
number of edges
Figure 2: Comparison of mean accuracy of GROW _VM algorithm depending on the choice of validation dataset. The dotted line indicates the accuracy of the neural network.
before training, we set aside 200 extra samples for each class from the train dataset. Then we compared three different choices of validation dataset V:
maxl-edge uses for V samples data from the training dalaset without extra samples, namely 200 samples per class,
max2-edge uses for V the test dataset,
max9-edge uses for V used the extra samples omitted from the training datasct.
Figure 2 shows that the accuracy of the first and the third algorithm is very close. This bodes well for applications, which often cannot set aside special validation dataset. Although algorithm max2-edge performed best, one should note that this is not valid choice, because using test dalaset in model building represents a form of test leakage.
4 Evaluation of intermediate SVM models
In this section, we will evaluate the performance of intermediate models based on accuracy and robustness. Accuracy evaluation will investigate the following questions:
how does an intermediate model compare the accuracy of the neural network,
how does the expected accuracy increase (or possibly decrease) with the increasing mumber edges, how does an the accuracy of maxl-edge model compare to the alternatives.
For the third point, we considered the following alternatives:
random-edge We start with a random star graph, and each step add a random edge.
random-star We start with a random star graph and at each step add a randomly chosen star.
vertex-transitive graphs of diameter 2: complete bipartite graph Kn, on 2n vertices, Petersen graph on 10 vertices, and Hoffman-Singleton graph on vertices (Hofmma & Singleton 1960).
All of these alternatives yield model graphs diameter 2, which means we can apply 7 estimate missing pairwise likelihoods. Compared to the maxl-edge algorithm, these alternatives do not require validation dataset, although the resulting speed-up is inconsequential.
10

---

Published in Transactions on Machine Learning Research (March/200)
For ten-class datasets, averaged over 20 different networks and ten possible centers of the initial star. For Imagenet-50 we used a single network, but tried all 50 possible centers of the initial star.
4.1 Discussion
The plots of average accuracy versus the number of edges in the model graph are shown in Figure 3
Neural networks are more accurate than SVM except for the imagewoof dataset. For Imagenet-50, the performance of neural networks and SVM models is very similar.
Dependence on the number of edges in the experiments turned out monotonic, mcaning maximal models showed the best performance. For 10 class datasets, most of the accuracy was achieved by including about half of all possible edges. For Imagenet-50 only about 250 edges sufficed to capture most of the accuracy of the maximal model, which is about 20% of the total.
Compared to alternative intermediate models, maxl-edge outranked the rest. The second best the random-star algorithm, but with the increasing number of edges its performance suffered and approached that of random-edge algorithm. Among vertex transitive graphs only K5,5 showed performance above the random-edge algorithm, but still well below maxl-edge.
For the radial kernel, the accuracy gap between minimal and maximal models much smaller compared the linear kernel mirroring results in section 3.1
We have plotted the standard deviation of predictions Imagenet-50 for the various methods in figure 1 The key point is that maxl-edge was again the best, and the error stabilized with ~ 250 edges, which is about the same number of edges as when its accuracy reached the plateau. Remarkably, the Hoffman-SSinletonn graph showed very stable behavior on par with maxl-edge. This is surprising since its accuracy was lagging.
5 Conclusion
We exhibited variety of intermediate multi-class SVM models trading accuracy for training time complexity. Our experiments uncovered key properties improving their accuracy. The maxl-edge variant of the proposed GROW __MMSSSMMMM-- algorithm showed superior accuracy across diverse datasets. achieved near-optimal accuracy while requiring only 20-50% of the computational cost of maximal models. This improvement meaningful for large values of C, when model construction can take hours or days. The method crucially uses a confusion matrix in the training phase, rather than relegating it mere tool for model evaluation. The algorithm is quite general; it is neither restricted to problems arising from neural networks to specific kernel. The efficacy of the method will vary according to dataset, but the incremental approach allows for monitoring of model-building progress and early stopping when incremental accuracy gains stall.
Our investigation reaffirms the efficacy of established methods. Softmax outperformed SVM models except for the challenging imagewoof datasct. This shows the benefit of whole model optimization employed training neural networks which contrasts the bottom-up approach of SVM. We also confirmed that commonly used maximal SVM models are very accurate. In our experiments, they were on average more accurate than models with smaller model graphs. Finally, the radial kernel proved surprisingly versatile, since it achieved near optimal accuracy on tasks, for which interclass boundaries were expected to be very close to lincar.
Our work underscores the crucial choice of model graph for intermediate probabilistic SVM. One may hy- pothesize that special classes of graphs, such as Cayley graphs or expander graphs (Hoory et al. 2006), could be useful for building multi-class SVM models. For that to happen, we would need new way conduct multi-class inference using intermediate graphs, unlike the one we used in the paper, which limited to graphs of diameter two.
6 Acknowledgments
The first author was supported by VEGA grant 2/0172/22 'Classification using ensembles of neural networks" and by the Operational Programme Integrated Infrastructure (OPIT) for the project 31301 1BWH2: "TnoCHF
11

---

Published in Transactions on Machine Learning Research (larch/2023)
linear
radial
0.940
0.935
01ar10
0.930
0.925
model
0.99
Petersen
accuracy
0.98
K5-5
max1-edge
0.97
random-edge
random-star
0.92
joowaBeut
0.90
0.89
0.88
0.87
number of edges
0.92
model
Hof-Sing
0.88
accuracy
OS aee-auaaeee.
K25-25
0.84
max1-edge
random-edge
random-star
250
500
750
1000
1250 0
250
500
750
1000
1250
number of edges
Figure 3: Average accuracy plotted against the size of the model graph for Imagenet-50. Hof-Sing denotes results for the Hoffnan-Singletor graph, K5-5 stands for the complete bipartite graph K5,3 and K25-25 stands for K25.25- The dotted horizontal line indicates the mean accuracy of neural networks.
Research and development in the field of innovative technologies in the management of patients with CHF', co-financed by the European Regional Development Fund.
12

---

Published in Transactions on Machine Learning Research (larch/2023)
linear
radial
model
0.06
Hof-Sing
std. deviation
09 mmmemao
K25-25
0.04
max1-edge
random-edge
random-star
0.00
250
500
750
1000
1250
500
750
1000
1250
number of edges
Figure 4: Mean standard deviation of the accuracy of intermediate models plotted against the size of the model graph for Imagenet-50. Hof-Sing denotes results for Hoffman-Singleton graph, and K25-25 stands for K25.25.
The second author was supported by Operational Program "Integrated Infrastructure' of the project 'Inte- grated strategy in the development of personalized medicine of selected malignant turnor diseases and its impact on life quality', ITMS code: 313011V446, co-financed by resources of European Regional Develop- ment Fund.
Authors would like to thank anonymous reviewers for their valuable suggestions.
References
Abdiansah Abdiansah and Retantyo Wardoyo. Time complexity analysis of support vector machines (SVM) in LibSVM. International Journal of Computer Applications, 128:975 8887, 10 2015. URL https://doi.
0Tg/10.5522//jcca21550000
Martin Andersen, Joachim Dahl, and Lieven Vandenberghe. CVXOPT: Convex optimization. Astrophysics Source Code Library, pp. ascl-20 2008, 2020. URL https: adsabs harvard, edu/abs/2020asc1.
soft08
Yoshua Bengio. Deep learning of representations for unsupervised and transfer lcarning. In Proceedings of ICML workshop on unsupervised and Irunsfer learning, pp. 17 17-36. JMLR Workshop and Conference Proceedings, 2012. URL httpss:/proceedngs..ll/ http://poceeraaa.....pppp/////// wwtppp/eeeeseeeeeeeeeeeee //wpg/iii///
Dongwei Cao and Daniel Boley. On approximate solutions to support vector machines. In Proceedings of the 2006 SIAM International Conference Data Mining, pp. 534-538. SIAM, 2006. URL https: //doi.
Chih-Chung Chang and Chih-Jen Lin. LIBSVM: a library for support vector machines. ACM transactions intelligent systems and technology (TIST), 2(3):1 27, 2011. URL https://doi. org/10..u 1145//991111.8
1961199
Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine Learning, 20:273-299 297, 1995. URL http://///o....110..000/////////
Koby Crammer and Yoram Singer. On the algorithmic implementation of multiclass kernel-basod vector machines. Journal of machine learning research, 2(Dec):265-29)) 2001. URL https://wwx jaijj.rlrrrg.... org/
13

---

Published in Transactions on Machine Learning Research (March/20P)
Thomas G Dietterich and Ghulum Bakiri. Solving multiclass learning problems via error-correcting output codes. Journal of artificial intelligence research, 1-263-280) 1994. URI. 105.
Thanh-Nghi Do. Multi-class bagged proximal support vector machines for the ImageNet challenging problem. In International Conference Future Data and Security Engineering, pp. 99-112. Springer, 2021. URL
https://doi.. org/ 10.//10.20 1007/97088888 3-00--88---------0 11880-9-187-817
Kai-Bo Duan and S Sathiya Keerthi. Which is the best multiclass SVM method? An empirical study, In International workshop on mulliple classifter systems, pp. 278 285. Springer, 2005. URL, httpps://doi
10. oTg/10..000//1144688322 28
Rong- En Fan, Kai- Wei Chang, Cho-Jui Hsieh, Xiang- Baang-Rui Wang, and Chih-Jen Lin. LIBLINEAR: A library for large linear classification. the Journal of machine Learning research, 9:1871 1874, 2008. URL https:
7/www. jmlr. jwww.j.lr... org wwwpoo/wggg/..ooooooooo http://paaa/oooooee/aaaaa///aaaa
pdf
Johannes Fürnkranz. Round robin classification. The Journal of Machine Learning Research, 2:721-747, http:/pppe///oonnoo/////oaaaaaaa
2002. URL http::///sw.w......
pdf
Mikel Galar, Alberto Fernández, Edurne Barrenechea, Humberto Bustince, and Francisco Herrera. An overview of ensemble methods for binary classifiers in multi-class problems: Experimental study on one- vs-one and one-vs-all schemes. Pultern Recognition, 44(8):1761 1776, 2011. URL ftttp:://do..rg////
patcoo. 2011.01.00
Trevor Hastie and Robert Tibshirani. Classification by pairwise coupling. Annals of Statistics, pp. 451-477 1998. URL http::htts///oo /ttp:::://ooi.r//11...0 1ttp://..1211///010011444444
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770- 778, 2016. URL https://openaccess: tchecvf.com/oonteeee crapntenttcvp___116666 2011///apee//////// Deee_eeeep______ee Learning_CVii Liia_2216__PPP__ 1a116__aper.pdl
Alan J Hoffman and Robert R. Singleton. On Moore graphs with diameters 2 and 3. IBM Journal of Research and Development, 4(5):497-504, 1960. URL http:::///ob...rrr/1111////////
0497
Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bul-
letin of the American Mathematical Society, 4344)4439- 2006. URL http::///01...r/1..11100
50271-0977--6--01226-8
Jeremy Howard. Imagenette, 2022. URL
Chih-Wei Hsu and Chih-Jen Lin. A comparison of methods for multiclass support vector machines. IEEE Transactions on Neural Networks, 13(2):415 -4255 2002. URL htttp:://boi.org/1101110/////// 721.779999919 991427
Minyoung Huh, Pulkit Agrawal, and Alexei A Efros. What makes ImageNet good for transfer learning?
arXiv preprint arXi::1608.0888 08614, 2016. URL
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, cs.utoronto.ca, 2009. URL http:://ww.wc. www..utooooooooooooooooo paarratto.ca/-rriis/eaaaaag.g http:///llaaannnn-atuueeee feattne---aauuuuu-220000 TR.
pdf.
Durjoy Sen Maitra, Ujjwal Bhattacharya, and Swapan K Parui. CNN based common approach to handwrit- ten character recognition of multiple scripts. In 2015 13th International Conference on Documend Analysis and Recognition (ICDAR), pp. 1021-10221 IEEE, 2015. URL httpp:://oi..rgg//// wttp:////....../////a.....oo 1109:111199110000000
7333916
David Meyer, Evgenia Dimitriadou, Kurt Hornik, Andreas Weingessel, and Friedrich Leisch. e1071: Misc Functions of the Deportment of Statistics, Probability Theory Group (Formerly: E1071), TU Wien, 2020. URL https::/ccAA http:/CRANN--PPoojje R-projectt.....mo httpr///ecctorr/ppccageeeeeoo R package version 1.7-4.
14

---

Published in Transactions on Machine Learning Research (March/200 /2023)
Shuteng Niu, Yongxin Liu, Jian Wang, and Houbing Song. A decade survey of transfer learning (2010-2020)
IEFE Transactions on Arlificial Intelligence, 1(2):151-10) 2020. URL https::////:::oorrr 1100011111TAAAA
30546999
David Page. cifar10-fast, 2019. URL httppp///ggggttoc.ooo//////a/aaa
Vishal Passricha and Rajesh Kumar Aggarwal. Convolutional support vector machines for speech recogni- tion. International Journal of Speech Technology, 22(3):601 609, 2019. URL
610772-018-09664-4
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825 2833,, 2011.
URL https: jmlr http://ppppreeeceommm//eeeeeeeaa
John Platt et al. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. Advances in large margin classifiers, 10(3):61 74, 1999. URL https::/www.eesearchgge. net/
publication/25880 25994015
R Core Team. R: A Language and Environment for Statistical Compuling. R. Foundation for Statistical Computing, Vienna, Austria, 2021. URL httph:ttt:////t R project org/
Shivarudhrappa Raghu, Natarajan Sriraam, Yasin Temel, Shyam Vasudeva Rao, and Pieter Kubben. EEG based multi-class seizure type classification using convolutional neural network and transfer learning. Newral Networks, 124:202 212, 2020. URL htttps://dbi.orgg//// 1016/ neunet. 2020. 011.111011
Ryan Rifkin and Aldebaro Klautau. In defense one classificaation The Journal of Machine Learning Research, 5:101-141, 2004. URL http:///////a//a.ooo////////////
pdf
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 115(3):211-25)) 2015. URL httpp:://o...orr org/ wtt.://///11111///..... 0010000011111223------8866611
scikit-learn. scikit-learn linearsve documentation, 2023. URL https:/bcckiitleamm.oom http://aaan.gggg.a/e//.e/ee http///eeeerrtteeaeeerarasoa//aa
html
Yichuan Tang. Deep learning using support vector machines. CoRR, abs/1306.08 0239, 2:1, 2013. URL
0239
Hadley Wickham. ggplot2: Elegant Graphics for Data Analysis. Springer-Veriee Verlag New York, 2016. URL
https:/ https://ggploss: wiw.yerse..edeeoer
Hadley Wickham, Mara Averick, Jennifer Bryan, Winston Chang, Lucy D' D'Aosttino McGowan, Romain François, Garrett Grolemund, Alex Hayes, Lionel Henry, Jim Hester, Max Kuhn, Thomas Lin Pedersen, Evan Miller, Stephan Milton Bache, Kirill Müller, Jeroen Ooms, David Robinson, Dana Paige Scidel, Vitalie Spinu, Kohske Takahashi, Davis Vaughan, Claus Wilke, Kara Woo, and Hiroaki Yutani. Welcome to the veryeerse Journal of Open Source Software, 4(43):1686, 2019. URL htttps://doi.orr//1... joss. 01686
Ting-Fan Wu, Chih-Jen Lin, and Ruby C. Weng. Probability estimates for multi-class classification by pairwise coupling. Journal of Machine Learning Research, 5:975 1005, Dec 2004. URL https://www. jmlr. http//ppperssrooomm///aaaaaaaaa
15


Reviews:
[{"review_id": "LpNSwDhILU", "reviewer": "Reviewer_ev2n", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written and easy to follow in general, but I still have some concerns on the current manuscript.\n\nSome concerns:\n\n- It seems that the related work section is missing. I encourage the author(s) to carefully describe some related works so readers can better understand the position of this work in the literature.\n- I understand that the focus of this paper is one-versus-one strategy, but I think it is still necessary to include some discussion on one-versus-all method such as softmax, e.g., when should we use one-versus-one and when one-versus-all is preferred?\n- It is better to include the time complexity of the proposed method (the time complexity to build the graph and the time complexity of solving those one-versus-one subproblems). I also suggest the author to compare the time complexity to the softmax method.\n- The number of classes is actually not large for the experimental datasets. I encourage the author(s) to include some datasets from the extreme classification repo (http://manikvarma.org/downloads/XC/XMLRepository.html). These datasets have a larger number of classes and seem to be suitable for the evaluation of the proposed method.\n\nMinor concerns:\n- page 4, inthe work -> in the work\n- page 4, then, then -> then", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studied the one-versus-one classification strategy used in multi-class SVM. The author(s) proposed two methods to build the one-versus-one comparison graph. Experiments on Image classification tasks are conducted to support the effectiveness of the proposed method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Add a related work section and clearly describe the position of this work in the literature.\n- Add some discussion on the one-versus-all method and compare it with one-versus-one.\n- Add some analysis on the time complexity of the proposed method.\n- Add some new experiments with some datasets from the extreme classification repo.", "broader_impact_concerns": "I do not have any concerns on the ethical implications of this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Y8ZsrAp2C9", "reviewer": "Reviewer_Gmnt", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strong aspects\n\nI could not find any strong aspects.\n\n\n### Weak aspects\n\nThis paper has several fatal weaknesses, as follows.\n\n**Weakness1: The research questions as well as the contributions are not clear.**\n\nIntroduction merely states that \"The primary aim of this work is to study the performance implications of the choice of model’s graph.\", without explaining why and how this is an important research topic.\nThis lack of research background is fatal for evaluating the contribution of the paper.\nThe lack also makes difficult to assess the appropriateness of the experimental setups (see Weakenss2 below as well).\n\n**Weakness2: The appropriateness of the experimental setups are not described.**\n\nMost parts of the paper focus on the detailed procedures of the experiments.\nHowever, the purposes of each experiment are not described in the paper.\nFor example, in Section 3, the authors compared minimal and maximal SMVs.\nThere, the authors merely stated that \"We study the performance gap between minimal and maximal SVM models, showing that there is a measurable gap.\"\nFrom the no free lunch theorem, we know that no single algorithm can dominate the others.\nHence, the comparisons of the algorithms cannot be independent from the choice of the datasets.\nAlthough the authors insisted that their choice of the datasets has \"several compelling attributes\" in page 2, there are no discussions on how the choice of the datasets are relevant to the comparisons under consideration.\nWithout such a discussion, what implications should we find from the comparisons on these datasets?\nApparently, the results on these datasets do not guarantee that the findings reported in the paper to hold on *any* datasets.\nFor what purposes or in which contexts, the comparisons on these datasets are relevant?\nThe same questions also arise in Section 4 as well.\n\n**Weakness3: The related studies are not reviewed appropriately.**\n\nOnly a few related studies are mentioned in the paper; the authors contrasted the current study with LIBSVM in Table 1, and the resemblance of the found results to (Šuch et al. (2015)) and (Šuch & Barreda (2016)) are pointed out in Section 5.5.\nIt is highly questionable if they are the only studies conducting similar comparisons as in the current paper.\nThis question leads to fundamental concerns.\nIs the finding reported in the paper truly novel?\nAre there anyone reported similar findings before?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper reports the results of experimental comparisons of a few aggregation methods for multiclass SVM that aggregates several one-vs-one SVMs.\nThe experiments are conducted on some image datasets where images are transformed to feature vectors using CNNs.\nThe authors reported that aggregations of one-vs-one SVMs for all class pairs (called *maximal*) attained the smallest classification errors.\nThe authors then considered graphs representing the pairwise relationships between the classes.\nThe authors then reported that, by adding edges to the graph randomly or by some strategies (i.e., selecting one-vs-one SVM to be added for aggregation), we can obtain aggregated multiclass SVM with almost the same accuracy as the maximal aggregation when we added around the half of the all possible pairs.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "**Request 1.**\nPlease describe the detailed background, research question, and the contribution of this research.\nWhy and how the research topics under considerations are important?\nWhat is the research question addressed in this study?\nWhat is the answer to the research question?\n\n**Request 2.**\nPlease describe the appropriateness of the experimental setups with respect to the underlying research questions.\nWhat are the questions addressed in each experiment?\nAre the choice of the experimental setups (such as the choice of the datasets) appropriate to answer the questions of interest?\nFor what purposes or in which contexts, the experimental setups are relevant?\n\n**Request 3.**\nPlease review related studies more exhaustively.\nIt is highly questionable if there are only a few studies conducting similar comparisons as in the current paper.\nIs the finding reported in the paper truly novel?\nAre there anyone reported similar findings before?", "broader_impact_concerns": "There is no ethical concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "eP6d4mRPYg", "reviewer": "Reviewer_3QF9", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strong points:\n\n1) (Trying to) improve the SVM multi-class classification model effectively and efficiently.\n\n2) Empirical experiments are performed to validate the discussion in this paper.\n\n---\n\n## Weak points:\n\nAlthough the work of this paper looks interesting, there are some points in this paper that are not so clear to me, I hope the author(s) could explain/detail them. Thanks.\n\n\n1) The technical details of empirical experiments are not described clearly, for example, how to calculate the averaged errors; the analysis of the empirical results is not thorough, for instance, why the error rates are opposite on datasets imagenette and imagewoof for different methods whole and fresh (Please see Section \"Requested Changes\" below for details).\n\n2) There are some issues that need to be clarified, such as how to calculate the distances between classes (Please see Section \"Requested Changes\" below for details).\n\nIn addition, this paper has some empirical experiments, but I am not sure the empirical description/experiments would be enough to reproduce because no code of this paper seems to be provided.\n\n---\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Support vector machine (SVM) is a commonly used traditional machine learning method for effectively handling binary classification. SVM itself does not support multi-class classification and requires meta-strategies, which may lead to a large increase in computation. An interesting question is whether there is a model that requires less training time but still maintains good accuracy. In this paper, the author(s) opened an interesting exploration of this from the perspective of metrical and topological properties, and proposed two ways to build smaller multi-class SVM models. \n\n", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Detailedly, I have the following comments/questions:\n\n1. For the datasets used in this paper, it is suggested to give a table with headings such as the name of datasets, number of samples, number of features, and so on. This will make it clear to the reader(s). And for Table 2 in the paper, please give the titles of columns; also, the caption width setting seems too narrow.\n\n2. On Page 4, Section 2.3, Paragraph 2, Lines 3-4, the author(s) mentioned that \"where we divide the training data into four folds and train four SVM models\", so, is 4-fold cross-validation used? Then for the results in the paper, for example, in Table 3, is it averaged over  $\\tbinom{10}{3}$ * 4 calculations?\n\n3. For the results in the paper (for example, Tables 3-5), it is better to give the average with the standard error. Since many results in the paper are actually close in terms of the average, maybe the fluctuations of the models can be better observed by using standard errors. \n\n4. In Tables 3-5, why are the error rates opposite on datasets imagenette and imagewoof for different methods whole and fresh? Could you please explain it? In addition, in Tables 3 and 4, maybe the accuracy results of neural networks can also be given as a reference.\n\n5. On page 8, Line 3 below Table 5, the author(s) mentioned that \"the neural network is more accurate than the maximal models\", I think that their results appear to be close (?).\n\n6. In Figure 3, how to calculate the distances between classes.\n\n7. On Page 1, Section 1, the last sentence in the 2nd Paragraph, the author(s) mentioned that \"...have drawbacks e.g. how to resolve tied votes...\", is this really a drawback of voting ensembles? I think it might be easily fixed by requiring an odd number of people/models to vote.\n\n8. Some other tiny issues/typos:\n\n(1) Regarding the word \"SVM\" in the Abstract, when the abbreviation appears for the first time, please give its full name. Similar to the first sentence in the Introduction.\n\n(2) In Abstract, Line 4, \"metricàl\" should be \"metrical\"?\n\n(3) On Page 3, Section 2.2, Line 2, what does \"(Page)\" mean?\n\n(4) On Page 4, Section 2.3, Paragraph 2, Lines 2-3, \"testing test\" should be \"test set\"; the word \"inthe\" should be \"in the\"?\n\n(5) In Tables 3-5, maybe there is no need to repeat the names of datasets and models so many times.\n\n(6) In Figures 7 and 9, some of the text on the picture is obscured\n\nIn addition, the format of the references is quite inconsistent. Please check carefully and correct it.\n\nI look forward to hearing from the author(s). Also, there is not a lot of overlap between my research and the work of this paper, please correct me if I am wrong. Thanks.\n\n\n\n", "broader_impact_concerns": "No.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studied the one-versus-one classification strategy used in multi-class SVM. Two new methods were proposed to build the one-versus-one comparison graph. Experiments on image classification tasks are conducted to validate the effectiveness of the proposed method.  Two reviewers recommended acceptance since they agreed that the revised version has addressed their concerns.  Reviewer ev2n recommended "rejection" because the reviewer thought that the authors did not provide the revised version. However, the authors did provide a revised version which was delayed for a couple of weeks.  The revised version did address Reviewer ev2n's main concern in Section 1.1 on the complexity analysis of the methods which I found is sufficient.  

Based on the above reasons, I recommend its acceptance but not Featured Certification. 
Decision: Accept (poster)