# Efficient Optimization ofF-Measure with Cost-Sensitive SVM

Authors: Fan Cheng; Yuan Zhou; Jian Gao; Shuangqiu Zheng
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

F-measure is one of the most commonly used performance metrics in classification, particularly when the classes are highly imbalanced. Direct optimization of this measure is often challenging, since no closed form solution exists. Current algorithms design the classifiers by using the approximations to the F-measure. These algorithms are not efficient and do not scale well to the large datasets. To fill the gap, in this paper, we propose a novel algorithm, which can efficiently optimize F-measure with cost-sensitive SVM. First of all, we present an explicit transformation from the optimization of F-measure to cost-sensitive SVM. Then we adopt bundle method to solve the inner optimization. For the problem where the existing bundle method may have the fluctuations in the primal objective during iterations, an additional line search procedure is involved, which can alleviate the fluctuations problem and make our algorithm more efficient. Empirical studies on the large-scale datasets demonstrate that our algorithm can provide significant speedups over current state-of-the-art F-measure based learners, while obtaining better (or comparable) precise solutions.


---

## Body

## 1. Introduction

SVM (Support Vector Machine) as a powerful classification tool is well known for its strong theoretical foundation and good generalization ability. In the binary setting, it is often evaluated by accuracy (the rate of correct classification). However, accuracy is not always a good measure and may be misleading, when the setting is imbalanced. In this situation, utility function such asF-measure provides a better way for the classifier evaluation, since it is a trade-off between precision and recall [1]. As a popular performance metric, F-measure has been widely used in diverse applications such as information retrieval [2, 3], biometrics [4, 5], and natural language processing [6, 7].Owing to its importance, it has been well studied in machine learning area, and many works have been focused on designing theF-measure based classifiers. However, directly optimizing F-measure is often difficult as the resulting optimization problem is nonconvex, and no closed form solution exists. Therefore, various approximation algorithms have been proposed, which mainly fall into two paradigms [8]. The Empirical Utility Maximization (EUM) approach learns a classifier having optimal performance on training data [9–16], while the decision-theoretic (DT) approach learns a probabilistic model and then predicts labels with maximum expected F-measure [17–20]. Since, in this paper, our aim is to design an efficient classifier for maximizing F-measure, and DT approach possibly needs high computational complexity for the prediction step [8], in the following, we are focused on the Empirical Utility Maximization approach.As theF-measure is a nonconvex metric, EUM approach often designs convex surrogates for optimizing F-measure and results in the development of two types of methods. The first type belongs to the “direct method,” which directly defines different surrogate objective functions for maximizing F-measure [9–15]. One representative work is SVMperf, which adopts structural SVM as surrogate framework, and uses cutting plane algorithm to solve the inner optimization [11]. This algorithm has many virtues (such as good generalization performance and rapid convergence speed) and is viewed as the most important and successful algorithm in EUM approach. Suzuki et al., Cheng et al., and Chinta et al. extended the work of SVMperf and applied it into different areas [12–15]. The second type belongs to the “indirect method” and is recently proposed by Parambath et al. [16]. It is a novel method, which solves the problem by transforming it into a cost-sensitive classification.Although those two methods are effective and are known to work fairly well in many different areas, there is still one disadvantage with those methods, where both of them are not very efficient, which may prohibit them from the large-scale applications. Moreover, for the novel “indirect method,” its key contribution is the theoretical part, and the authors presented a theoretical analysis that the optimalF-measure classifier can be obtained by the reduction to cost-sensitive classification. But how to convert the procedure of maximizing F-measure into a cost-sensitive problem, that paper does not give an explicit solution.To fill the gap, in this paper we focus on binary classification and propose a novel algorithm, which can efficiently optimizeF-measure with cost-sensitive SVM. It seems that our algorithm belongs to the “indirect method”; however, it uses similar optimization technique like SVMperf, which means our algorithm can be viewed as the combination of the “direct method” and the “indirect method.” More specifically, this paper makes the following contributions:(1)
Different from Parambath’s work, which only gives a theoretical analysis, we present an explicit transformation from maximizingF-measure to cost-sensitive SVM.(2)
For the new cost-sensitive problem, we propose to solve it with bundle method, which is similar to the cutting plane algorithm used in SVMperf and hasO(1/ε) rate of convergence.(3)
Different from SVMperf, which is bothered with the fluctuations in primal objective, an additional line search procedure is introduced to the bundle method, which can avoid this undesirable effect and make our algorithm more efficient.(4)
Empirical evaluations on the large-scale imbalanced datasets demonstrate that when compared with currently existingF-measure based classifiers, the learner we proposed can greatly reduce the training time, while obtaining better (or comparable) accuracy of the model.The remainder of the paper is organized as follows. In Section2, the related work is presented. Section 3 discusses the details of our proposed algorithm and the empirical results on the benchmark datasets are reported in Section 4. Section 5 concludes the paper and discusses the future work.


## 2. Related Work

### 2.1. Problem Setup and Notations

As discussed in the introduction, in this paper, we only consider the binary classification problem. Given a training datasetD={(xi,yi)}i=1n, where xi∈Rd is ith example and yi∈{+1,-1} is the corresponding class label. For simplicity, we assume that positive instances are ahead of negative ones, which means i∈{1,2,3,…,#pos}︸#pos are the indexes of positive instances and the rest i∈{#pos+1,…,n}︸#neg are those of the negatives. #pos and #neg denote the number of positive instances and the negative ones, respectively. Binary classification problem is to construct a classifier function fx, which gives good generalization performance. In this paper, we assume the classifier is of the form fx=w·x and the decision function y¯=sign(f(x)) is used to find the label of an unseen example. Note that we have not included the bias term in the classifier function for notational convenience. However, it can be incorporated in a straightforward way.In machine learning area, a common way to find the linear parameterw∈Rd is to minimize a regularized risk function:(1)w=argminw∈Rd12w2+C∑i=1nlxi,yi,w,where C>0 is a constant that controls the trade-off between training error minimization and margin maximization. l is a suitable loss function which measures the discrepancy between a true label yi and a predicted value from using parameter w. Different loss functions yield different learners. One of the most famous loss functions is the hinge loss in SVM, which has the form of lhinge(xi,yi,w)=max⁡(0,1-yiwxi).


### 2.2. Relevant Background

When given a SVM classifierf, its performance can be evaluated by Table 1.Table 1
Confusion matrix.
y
=
1
y
=
-
1
sign
⁡
(
f
(
x
)
)
=
1
TP
FP
sign
⁡
(
f
(
x
)
)
=
-
1
FN
TNTP, TN, FP, and FN in Table1 denote true positive, true negative, false positive, and false negative, respectively, and(2)TP=yi=1:signfxi=1,TN=yi=-1:signfxi=-1,FP=#neg-TN,FN=#pos-TP.By using the confusion matrix in Table1, precision and recall can be expressed as(3)PRE=TPTP+FP,REC=TPTP+FN.In the imbalanced learning, people often use weighted harmonic mean of precision and recall, which is namedF-measure to evaluate the performance of a classifier [1], and it can be formally defined as (4)F-measure=β2+1·PRE·RECβ2·PRE+REC,where β≥0. It is obvious that if β=0, F-measure is the precision and if β→+∞, F-measure turns to the recall. In practice, the most widely used F-measure is F1, which means β=1.Because of its popular usage in the imbalanced classification, various approaches have been proposed for maximizingF-measure. One main paradigm is Empirical Utility Maximization, which learns a classifier having optimal F-measure on the training data. However, direct optimization of F-measure is difficult as the resulting optimization problem is nonconvex. Thus, approximation techniques are often used instead (since these algorithms directly design approximation objective functions oriented to F-measure, they are termed as “direct method” [8]). For example, Musicant et al., Liu et al., and Joachims et al. have designed different surrogate algorithms for optimizing the F-measure [9–11]. Among them, the work of Joachims et al. (which referred to SVMperf) is the most important, since not only their work provides a general framework for optimizing any imbalanced measure, but also their inner optimization technique is efficient. This algorithm makes use of a cutting plane solver along the lines of the structural SVM and has O(1/ε) rate of convergence for any desired precision ε. Based on this work, Suzuki et al. and Cheng et al. applied SVMperf to the CRF and topical classification [12, 13], while Chinta et al. and Dembczynski et al. further extended it to the sparse learning and multilabel learning [14, 15]. Recently, an “indirect method” for optimizing F-measure which used cost-sensitive technology has been proposed by Parambath et al. [16]. The authors took the advantage of the pseudolinearity of F-measure and presented a theoretical analysis that the optimal classifier for F-measure can be obtained by solving a cost-sensitive problem. Both “direct method” and “indirect method” are effective and are suitable for many various applications. However, those two methods have a common limitation that they are not very efficient, which may prohibit them from being used in the large-scale datasets. For the “direct method,” we take the SVMperf as an example, which is one of the most efficient algorithms in EUM. Although it has rapid convergence speed, its inner optimization can only guarantee the dual objective function increases monotonically and does not guarantee the primal objective decreases monotonically [21]. These fluctuations in primal objectives may slow down the practical convergence speed and make the SVMperf inefficient. Similar problem occurs on the “indirect method,” because this method should be implemented with other existing SVMs, which may also have these undesirable fluctuations during the iterations. Furthermore, for the recently proposed “indirect method,” the main contribution of it is the theoretical part, and the authors only present a theoretical analysis that maximizing F-measure can be reduced to a cost-sensitive classification. However, they do not give an explicit transformation from the optimization of F-measure to cost-sensitive SVM.So in the following, by giving an explicit transformation, we will present a novel cost-sensitive SVM based algorithm that can maximizeF-measure. The algorithm uses the bundle method as the inner optimizer and avoids the fluctuations in primal objective by adding a line search procedure, which means our algorithm can be more efficient than the existing algorithms such as [8, 11, 16].


## 2.1. Problem Setup and Notations

As discussed in the introduction, in this paper, we only consider the binary classification problem. Given a training datasetD={(xi,yi)}i=1n, where xi∈Rd is ith example and yi∈{+1,-1} is the corresponding class label. For simplicity, we assume that positive instances are ahead of negative ones, which means i∈{1,2,3,…,#pos}︸#pos are the indexes of positive instances and the rest i∈{#pos+1,…,n}︸#neg are those of the negatives. #pos and #neg denote the number of positive instances and the negative ones, respectively. Binary classification problem is to construct a classifier function fx, which gives good generalization performance. In this paper, we assume the classifier is of the form fx=w·x and the decision function y¯=sign(f(x)) is used to find the label of an unseen example. Note that we have not included the bias term in the classifier function for notational convenience. However, it can be incorporated in a straightforward way.In machine learning area, a common way to find the linear parameterw∈Rd is to minimize a regularized risk function:(1)w=argminw∈Rd12w2+C∑i=1nlxi,yi,w,where C>0 is a constant that controls the trade-off between training error minimization and margin maximization. l is a suitable loss function which measures the discrepancy between a true label yi and a predicted value from using parameter w. Different loss functions yield different learners. One of the most famous loss functions is the hinge loss in SVM, which has the form of lhinge(xi,yi,w)=max⁡(0,1-yiwxi).


## 2.2. Relevant Background

When given a SVM classifierf, its performance can be evaluated by Table 1.Table 1
Confusion matrix.
y
=
1
y
=
-
1
sign
⁡
(
f
(
x
)
)
=
1
TP
FP
sign
⁡
(
f
(
x
)
)
=
-
1
FN
TNTP, TN, FP, and FN in Table1 denote true positive, true negative, false positive, and false negative, respectively, and(2)TP=yi=1:signfxi=1,TN=yi=-1:signfxi=-1,FP=#neg-TN,FN=#pos-TP.By using the confusion matrix in Table1, precision and recall can be expressed as(3)PRE=TPTP+FP,REC=TPTP+FN.In the imbalanced learning, people often use weighted harmonic mean of precision and recall, which is namedF-measure to evaluate the performance of a classifier [1], and it can be formally defined as (4)F-measure=β2+1·PRE·RECβ2·PRE+REC,where β≥0. It is obvious that if β=0, F-measure is the precision and if β→+∞, F-measure turns to the recall. In practice, the most widely used F-measure is F1, which means β=1.Because of its popular usage in the imbalanced classification, various approaches have been proposed for maximizingF-measure. One main paradigm is Empirical Utility Maximization, which learns a classifier having optimal F-measure on the training data. However, direct optimization of F-measure is difficult as the resulting optimization problem is nonconvex. Thus, approximation techniques are often used instead (since these algorithms directly design approximation objective functions oriented to F-measure, they are termed as “direct method” [8]). For example, Musicant et al., Liu et al., and Joachims et al. have designed different surrogate algorithms for optimizing the F-measure [9–11]. Among them, the work of Joachims et al. (which referred to SVMperf) is the most important, since not only their work provides a general framework for optimizing any imbalanced measure, but also their inner optimization technique is efficient. This algorithm makes use of a cutting plane solver along the lines of the structural SVM and has O(1/ε) rate of convergence for any desired precision ε. Based on this work, Suzuki et al. and Cheng et al. applied SVMperf to the CRF and topical classification [12, 13], while Chinta et al. and Dembczynski et al. further extended it to the sparse learning and multilabel learning [14, 15]. Recently, an “indirect method” for optimizing F-measure which used cost-sensitive technology has been proposed by Parambath et al. [16]. The authors took the advantage of the pseudolinearity of F-measure and presented a theoretical analysis that the optimal classifier for F-measure can be obtained by solving a cost-sensitive problem. Both “direct method” and “indirect method” are effective and are suitable for many various applications. However, those two methods have a common limitation that they are not very efficient, which may prohibit them from being used in the large-scale datasets. For the “direct method,” we take the SVMperf as an example, which is one of the most efficient algorithms in EUM. Although it has rapid convergence speed, its inner optimization can only guarantee the dual objective function increases monotonically and does not guarantee the primal objective decreases monotonically [21]. These fluctuations in primal objectives may slow down the practical convergence speed and make the SVMperf inefficient. Similar problem occurs on the “indirect method,” because this method should be implemented with other existing SVMs, which may also have these undesirable fluctuations during the iterations. Furthermore, for the recently proposed “indirect method,” the main contribution of it is the theoretical part, and the authors only present a theoretical analysis that maximizing F-measure can be reduced to a cost-sensitive classification. However, they do not give an explicit transformation from the optimization of F-measure to cost-sensitive SVM.So in the following, by giving an explicit transformation, we will present a novel cost-sensitive SVM based algorithm that can maximizeF-measure. The algorithm uses the bundle method as the inner optimizer and avoids the fluctuations in primal objective by adding a line search procedure, which means our algorithm can be more efficient than the existing algorithms such as [8, 11, 16].


## 3. Efficient Algorithm for OptimizingF-Measure with Cost-Sensitive SVM

### 3.1. From MaximizingF-Measure to the Cost-Sensitive Classification

Based on the definition of formula (4), F-measure can be further expressed as(5)F-measure=β2+1·PRE·RECβ2·PRE+REC=β2+1·TP/TP+FP·TP/TP+FNβ2·TP/TP+FP+TP/TP+FN=β2+1·TP·TPβ2·TP·TP+FN+TP·TP+FP=β2+1·TPβ2·TP+FN+TP+FP=β2+1·#pos-FNβ2·#pos-FN+FN+#pos-FN+FP=#pos-FNβ2/β2+1·#pos+#pos-FN+FP/β2+1=1β2/β2+1·#pos/#pos-FN+#pos-FN+FP/β2+1·#pos-FN.By assuming#pos≠FN, we can find that maximizing F-measure is equivalent to minimizing the following problem:(6)minw∈Rd⁡β2β2+1·#pos#pos-FN+1+FP/#pos-FNβ2+1⟺minw∈Rd⁡β2β2+1·#pos#pos-FN+FPβ2+1#pos-FN⟺minw∈Rd⁡β2#pos+FPβ2+1·#pos-FN⟺minw∈Rd⁡β2#pos+FP-ϑβ2+1·#pos-FN,where ϑ is a positive constant. Since β and #pos are both constants, formula (6) can be simplified as(7)minw∈Rd⁡FP+ϑβ2+1·FN⟺minw∈Rd⁡FP+ϑ^·FN,where ϑ^=ϑ(β2+1) is a positive constant. Based on the definitions of FP and FN, formula (7) can be rewritten as(8)minw∈Rd⁡∑i=#pos+1nIyi≠signfxi+ϑ^·∑i=1#posIyi≠signfxi⟺minw∈Rd⁡Cp·∑i=1#posIyi≠signfxi+Cn·∑i=#pos+1nIyi≠signfxi,where Cp+Cn=1 and 0≤Cp, Cn≤1 are the misclassification cost parameters for positive and negative classes, respectively. It is obvious that formula (8) is a cost-sensitive problem, and the lower the total cost, the better the classification performance.


### 3.2. Efficient Algorithm for the Cost-Sensitive SVM

Based on formula (8), we can transform the maximization of F-measure problem to a cost-sensitive SVM, which is demonstrated as(9)w=argminw∈Rd12w2+C·Cp·∑i=1#poslhingeyi≠signfxi+Cn·∑i=#pos+1nlhingeyi≠signfxi.Formula (9) is equivalent toOP1:(10)
w
=
a
r
g
m
i
n
w
∈
R
d
δ
2
w
2
+
C
p
·
∑
i
=
1
#
p
o
s
l
h
i
n
g
e
y
i
≠
s
i
g
n
f
x
i
+
C
n
·
∑
i
=
#
p
o
s
+
1
n
l
h
i
n
g
e
y
i
≠
s
i
g
n
f
x
i
︸
R
e
m
p
c
s
w
︷
J
w
,where δ=1/C is a constant that controls the trade-off between training error minimization and margin maximization. For the OP1 above, we regard it as a regularized risk minimization problem and adopt the bundle method to solve it. Bundle method uses subgradients of the empirical risk function to approximate its piecewise linear lower bound, which is similar to the cutting plane algorithm (CPA) used in SVMperf. In contrast to CPA, the linear lower bound of bundle method is augmented with a stabilization term, which can guarantee a good quality solution [22]. By taking the first-order Taylor approximation to the empirical risk function, the lower bounder is tightened iteratively until the difference gap between the approximated lower bound and the real risk function is smaller than a predefined threshold ε. The whole algorithm can be described as shown in Algorithm 1.Algorithm 1:Bundle method for solving OP1 within tolerance ε.
(1)Input: convergence threshold ε>0;
(2)Initialize: weight vector w0 and iteration index t=0;
(3)repeat
(4)t=t+1;
(5) Computeαt=∂wRempcs(wt-1);
(6) Compute biasbt=Rempcs(wt-1)-wt-1αt;
(7) Update the lower boundRtBM(w)=max1≤i≤t⁡{w⋅αi+bi};
(8)wt=argminw∈Rd⁡((δ/2)w2+RtBMw)︸Jt(w);
(9) Compute current gapεt=min0≤i≤t⁡(J(wi)-Jt(wt));
(10)untilεt≤ε;
(11)Output:  wt as the w∗ of OP1.It has been proved that the bundle method in Algorithm1 had O(1/ε) rate of convergence for any desired precision ε [22]. Although the bundle method is effective, it also has the fluctuations in primal objective, which also occurred on the CPA of SVMperf. More specifically, when solving the subproblem of step (8), it always selects a new cutting plane such that the dual objective monotonically increases. However, this selection does not guarantee that the primal problem monotonically decreases, which means that the primal objective values can heavily fluctuate between iterations, and it may slow down the practical convergence speed of the algorithm.To solve this problem and speed up the convergence, in the following, we will present an additional line search algorithm for step(8), which can guarantee that the primal objective function monotonically decreases and make our algorithm more efficient.


### 3.3. Efficient Line Search Algorithm

First of all, we introduce an intermediate variablewtc maintaining the best-so-best solution during the first t iterations, which means Jw1c,…,J(wtc) is a monotonically decrease sequence.Secondly, the newwtc is found by searching a line along the previous wt-1c and the origin solution wt, which gives the following:OP2:(11)wtc=minl≥0⁡Jwt-1c1-l+wtl.Finally, the new cutting plane is computed to approximate the primal objectiveJ at a point wtd, which lies in a vicinity of the wtc. More specifically, the variable wtd is obtained by(12)wtd=wtc1-λ+wtλ,where λ∈(0,1] is a predefined parameter. With the point wtd, the new cutting plane is given by αt+1∈∂wRempcs(wtd), and bt+1=Rempcs(wtd)-wtdαt+1.Similar to step(9) of Algorithm 1, a nature stopping condition for our improved algorithm is (13)Jwtc-Jtwt≤ε.With those changes to bundle method, we can generate a monotonically decrease sequence of primal objective and achieve faster convergence. However, in practice, there is still one problem with our improved algorithm, which is how to compute the OP2 efficiently. So in the following, we will give an efficient algorithm for solving this problem, which only needsO(nlog⁡n) time.Firstly, combining formulas (10) and (11), we can obtain(14)Jwt-1c1-l+wtl=δ2wt-1c1-l+wtl2+Cp·∑i=1#poslhingewt-1c1-l+wtl+Cn·∑i=#pos+1nlhingewt-1c1-l+wtl.We abbreviate j(l)≡J(wt-1c(1-l)+wtl) and get(15)jl=δ2wt-1c+wt-wt-1cl2+∑i=1#posCp·lhingewt-1c1-l+wtl+∑i=#pos+1nCn·lhingewt-1c1-l+wtl=12δwt-wt-1c2︸A0l2+δwt-1c,wt-wt-1c︸B0l+δ2wt-1c2︸Z0+∑i=1#posCp·max⁡0,1-yixiwt-1c1-l+wtl︸gposl+∑i=#pos+1nCn·max⁡0,1-yixiwt-1c1-l+wtl︸gnegl.That is,(16)jl=12l2A0+lB0+Z0+gposl+gnegl=12l2A0+lB0+Z0+∑i=1#posgposil+∑i=#pos+1ngnegil,where (17)gposil=max⁡0,Cp1-yixiwt-1c+Cpyixiwt-1c-wtlgnegil=max⁡0,Cn1-yixiwt-1c+Cnyixiwt-1c-wtl.The OP2 is equivalent to solvingl∗=argminl≥0⁡j(l). Since j(l) is a convex function, its minimum is attained at the point l∗, where the subdifferential ∂j(l) contains zero, which means 0∈∂j(l) hold. The subdifferential ∂j(l) can be expressed as(18)∂jl=A0l+B0+∑i=1#pos∂gposil+∑i=#pos+1n∂gnegil,where(19)∂gposil=0ifCp1-yixiwt-1c+Cpyixiwt-1c-wtl<0Cpyixiwt-1c-wtifCp1-yixiwt-1c+Cpyixiwt-1c-wtl>00,Cpyixiwt-1c-wtifCp1-yixiwt-1c+Cpyixiwt-1c-wtl=0∂gnegil=0ifCn1-yixiwt-1c+Cnyixiwt-1c-wtl<0Cnyixiwt-1c-wtifCn1-yixiwt-1c+Cnyixiwt-1c-wtl>00,Cnyixiwt-1c-wtifCn1-yixiwt-1c+Cnyixiwt-1c-wtl=0.For formula (18), the first two terms constitute an ascending linear function A0l+B0, since A0=δwt-wt-1c2≥0. Note A0=0 means that wt=wt-1c, which indicates that our algorithm has converged to the optimum w∗. The latter two terms ∂gposi(l) and ∂gnegi(l) are either constants or step functions by the definitions of formula (19). Hence, ∂j(l) is a monotonically increasing function, which can be depicted as in Figure 1.Figure 1
The step function of∂j(l).
(a)
Case 1. l∗ lies in the slash area
(b)
Case 2. l∗ lies in the vertical areaFrom Figure1, we can begin with l=0 to find the best solution of l∗=argminl≥0⁡j(l): (20)∂j0=B0+∑i=1#pos∂gposi0+∑i=#pos+1n∂gnegi0,where (21)∂gposi0=0ifCp1-yixiwt-1c<0Cpyixiwt-1c-wtifCp1-yixiwt-1c>00,Cpyixiwt-1c-wtelseCp1-yixiwt-1c=0,∂gnegi0=0ifCn1-yixiwt-1c<0Cnyixiwt-1c-wtifCn1-yixiwt-1c>00,Cnyixiwt-1c-wtelseCn1-yixiwt-1c=0.Based on equalities (20) and (21), we can find that if max⁡(∂j(0))≥0, the minimum j(l) is attained at the point equal to 0, which means l∗=0. While if max⁡(∂j(0))<0, the optimum l∗ is obtained by finding an intersection between ∂j(l) and the x-axis (as Figure 1 shows). This can be done efficiently by sorting every step points. The whole algorithm is described as shown in Algorithm 2.Algorithm 2:Efficient line search for solving OP2.
(1)Input: wt,wt-1c,A0,B0,Z0,Cp,Cn,xi,yi
(2)Compute max(∂j(0)) with formula (20) and (21)
(3)if  max(∂j(0))≥0  then
(4)l∗=0
(5)else
(6)L←{li∣li=(1-yixiwt-1c)/yixi(wt-wt-1c)>0} // find the step point sets with li>0
(7)  SortL in ascending order →{l1,…,lK} where K=|L|
(8)l0=0 // begin with zero point
(9)for  k=1,…,K  do
(10)∂j(lk)=∂j(lk-1)+A0(lk-lk-1)
(11)if  ∂j(lk)>0  then
(12)l∗=(-∑i=0k-1Bi)/A0 // Case 1  l∗ lies in the slash area
whereBi=B0ifi=0Cpyixi(wt-1c-wt)ifi≠0,yi=+1Cnyixi(wt-1c-wt)elsei≠0,yi=-1
(13)else
(14)∂j(lk)=∂j(lk)+Bk
(15)if  ∂j(lk)≥0  then
(16)l∗=lk // Case 2  l∗ lies in the vertical area
(17)end if
(18)end if
(19)end for
(20)end if
(21)Output: l∗.For Algorithm2, the theorem below guarantees that it only requires O(nlog⁡n) time.Theorem 1.
The total running time of Algorithm2 is O(nlog⁡n).Proof.
From the pseudo code of Algorithm2, we can find that the time of step (1) to step (4) is O(1), and step (6) needs at most O(n) time. Step (7) is sorting, which can be implemented in O(Klog⁡K) time. Step (9) to step (19) take O(K) time, and other steps all require O(1) time. Therefore, Algorithm 2 has the complexity of O(n+Klog⁡K). Since in practice K≤n, which means that even in the worst case the total running time of Algorithm 2 is O(nlog⁡n).


## 3.1. From MaximizingF-Measure to the Cost-Sensitive Classification

Based on the definition of formula (4), F-measure can be further expressed as(5)F-measure=β2+1·PRE·RECβ2·PRE+REC=β2+1·TP/TP+FP·TP/TP+FNβ2·TP/TP+FP+TP/TP+FN=β2+1·TP·TPβ2·TP·TP+FN+TP·TP+FP=β2+1·TPβ2·TP+FN+TP+FP=β2+1·#pos-FNβ2·#pos-FN+FN+#pos-FN+FP=#pos-FNβ2/β2+1·#pos+#pos-FN+FP/β2+1=1β2/β2+1·#pos/#pos-FN+#pos-FN+FP/β2+1·#pos-FN.By assuming#pos≠FN, we can find that maximizing F-measure is equivalent to minimizing the following problem:(6)minw∈Rd⁡β2β2+1·#pos#pos-FN+1+FP/#pos-FNβ2+1⟺minw∈Rd⁡β2β2+1·#pos#pos-FN+FPβ2+1#pos-FN⟺minw∈Rd⁡β2#pos+FPβ2+1·#pos-FN⟺minw∈Rd⁡β2#pos+FP-ϑβ2+1·#pos-FN,where ϑ is a positive constant. Since β and #pos are both constants, formula (6) can be simplified as(7)minw∈Rd⁡FP+ϑβ2+1·FN⟺minw∈Rd⁡FP+ϑ^·FN,where ϑ^=ϑ(β2+1) is a positive constant. Based on the definitions of FP and FN, formula (7) can be rewritten as(8)minw∈Rd⁡∑i=#pos+1nIyi≠signfxi+ϑ^·∑i=1#posIyi≠signfxi⟺minw∈Rd⁡Cp·∑i=1#posIyi≠signfxi+Cn·∑i=#pos+1nIyi≠signfxi,where Cp+Cn=1 and 0≤Cp, Cn≤1 are the misclassification cost parameters for positive and negative classes, respectively. It is obvious that formula (8) is a cost-sensitive problem, and the lower the total cost, the better the classification performance.


## 3.2. Efficient Algorithm for the Cost-Sensitive SVM

Based on formula (8), we can transform the maximization of F-measure problem to a cost-sensitive SVM, which is demonstrated as(9)w=argminw∈Rd12w2+C·Cp·∑i=1#poslhingeyi≠signfxi+Cn·∑i=#pos+1nlhingeyi≠signfxi.Formula (9) is equivalent toOP1:(10)
w
=
a
r
g
m
i
n
w
∈
R
d
δ
2
w
2
+
C
p
·
∑
i
=
1
#
p
o
s
l
h
i
n
g
e
y
i
≠
s
i
g
n
f
x
i
+
C
n
·
∑
i
=
#
p
o
s
+
1
n
l
h
i
n
g
e
y
i
≠
s
i
g
n
f
x
i
︸
R
e
m
p
c
s
w
︷
J
w
,where δ=1/C is a constant that controls the trade-off between training error minimization and margin maximization. For the OP1 above, we regard it as a regularized risk minimization problem and adopt the bundle method to solve it. Bundle method uses subgradients of the empirical risk function to approximate its piecewise linear lower bound, which is similar to the cutting plane algorithm (CPA) used in SVMperf. In contrast to CPA, the linear lower bound of bundle method is augmented with a stabilization term, which can guarantee a good quality solution [22]. By taking the first-order Taylor approximation to the empirical risk function, the lower bounder is tightened iteratively until the difference gap between the approximated lower bound and the real risk function is smaller than a predefined threshold ε. The whole algorithm can be described as shown in Algorithm 1.Algorithm 1:Bundle method for solving OP1 within tolerance ε.
(1)Input: convergence threshold ε>0;
(2)Initialize: weight vector w0 and iteration index t=0;
(3)repeat
(4)t=t+1;
(5) Computeαt=∂wRempcs(wt-1);
(6) Compute biasbt=Rempcs(wt-1)-wt-1αt;
(7) Update the lower boundRtBM(w)=max1≤i≤t⁡{w⋅αi+bi};
(8)wt=argminw∈Rd⁡((δ/2)w2+RtBMw)︸Jt(w);
(9) Compute current gapεt=min0≤i≤t⁡(J(wi)-Jt(wt));
(10)untilεt≤ε;
(11)Output:  wt as the w∗ of OP1.It has been proved that the bundle method in Algorithm1 had O(1/ε) rate of convergence for any desired precision ε [22]. Although the bundle method is effective, it also has the fluctuations in primal objective, which also occurred on the CPA of SVMperf. More specifically, when solving the subproblem of step (8), it always selects a new cutting plane such that the dual objective monotonically increases. However, this selection does not guarantee that the primal problem monotonically decreases, which means that the primal objective values can heavily fluctuate between iterations, and it may slow down the practical convergence speed of the algorithm.To solve this problem and speed up the convergence, in the following, we will present an additional line search algorithm for step(8), which can guarantee that the primal objective function monotonically decreases and make our algorithm more efficient.


## 3.3. Efficient Line Search Algorithm

First of all, we introduce an intermediate variablewtc maintaining the best-so-best solution during the first t iterations, which means Jw1c,…,J(wtc) is a monotonically decrease sequence.Secondly, the newwtc is found by searching a line along the previous wt-1c and the origin solution wt, which gives the following:OP2:(11)wtc=minl≥0⁡Jwt-1c1-l+wtl.Finally, the new cutting plane is computed to approximate the primal objectiveJ at a point wtd, which lies in a vicinity of the wtc. More specifically, the variable wtd is obtained by(12)wtd=wtc1-λ+wtλ,where λ∈(0,1] is a predefined parameter. With the point wtd, the new cutting plane is given by αt+1∈∂wRempcs(wtd), and bt+1=Rempcs(wtd)-wtdαt+1.Similar to step(9) of Algorithm 1, a nature stopping condition for our improved algorithm is (13)Jwtc-Jtwt≤ε.With those changes to bundle method, we can generate a monotonically decrease sequence of primal objective and achieve faster convergence. However, in practice, there is still one problem with our improved algorithm, which is how to compute the OP2 efficiently. So in the following, we will give an efficient algorithm for solving this problem, which only needsO(nlog⁡n) time.Firstly, combining formulas (10) and (11), we can obtain(14)Jwt-1c1-l+wtl=δ2wt-1c1-l+wtl2+Cp·∑i=1#poslhingewt-1c1-l+wtl+Cn·∑i=#pos+1nlhingewt-1c1-l+wtl.We abbreviate j(l)≡J(wt-1c(1-l)+wtl) and get(15)jl=δ2wt-1c+wt-wt-1cl2+∑i=1#posCp·lhingewt-1c1-l+wtl+∑i=#pos+1nCn·lhingewt-1c1-l+wtl=12δwt-wt-1c2︸A0l2+δwt-1c,wt-wt-1c︸B0l+δ2wt-1c2︸Z0+∑i=1#posCp·max⁡0,1-yixiwt-1c1-l+wtl︸gposl+∑i=#pos+1nCn·max⁡0,1-yixiwt-1c1-l+wtl︸gnegl.That is,(16)jl=12l2A0+lB0+Z0+gposl+gnegl=12l2A0+lB0+Z0+∑i=1#posgposil+∑i=#pos+1ngnegil,where (17)gposil=max⁡0,Cp1-yixiwt-1c+Cpyixiwt-1c-wtlgnegil=max⁡0,Cn1-yixiwt-1c+Cnyixiwt-1c-wtl.The OP2 is equivalent to solvingl∗=argminl≥0⁡j(l). Since j(l) is a convex function, its minimum is attained at the point l∗, where the subdifferential ∂j(l) contains zero, which means 0∈∂j(l) hold. The subdifferential ∂j(l) can be expressed as(18)∂jl=A0l+B0+∑i=1#pos∂gposil+∑i=#pos+1n∂gnegil,where(19)∂gposil=0ifCp1-yixiwt-1c+Cpyixiwt-1c-wtl<0Cpyixiwt-1c-wtifCp1-yixiwt-1c+Cpyixiwt-1c-wtl>00,Cpyixiwt-1c-wtifCp1-yixiwt-1c+Cpyixiwt-1c-wtl=0∂gnegil=0ifCn1-yixiwt-1c+Cnyixiwt-1c-wtl<0Cnyixiwt-1c-wtifCn1-yixiwt-1c+Cnyixiwt-1c-wtl>00,Cnyixiwt-1c-wtifCn1-yixiwt-1c+Cnyixiwt-1c-wtl=0.For formula (18), the first two terms constitute an ascending linear function A0l+B0, since A0=δwt-wt-1c2≥0. Note A0=0 means that wt=wt-1c, which indicates that our algorithm has converged to the optimum w∗. The latter two terms ∂gposi(l) and ∂gnegi(l) are either constants or step functions by the definitions of formula (19). Hence, ∂j(l) is a monotonically increasing function, which can be depicted as in Figure 1.Figure 1
The step function of∂j(l).
(a)
Case 1. l∗ lies in the slash area
(b)
Case 2. l∗ lies in the vertical areaFrom Figure1, we can begin with l=0 to find the best solution of l∗=argminl≥0⁡j(l): (20)∂j0=B0+∑i=1#pos∂gposi0+∑i=#pos+1n∂gnegi0,where (21)∂gposi0=0ifCp1-yixiwt-1c<0Cpyixiwt-1c-wtifCp1-yixiwt-1c>00,Cpyixiwt-1c-wtelseCp1-yixiwt-1c=0,∂gnegi0=0ifCn1-yixiwt-1c<0Cnyixiwt-1c-wtifCn1-yixiwt-1c>00,Cnyixiwt-1c-wtelseCn1-yixiwt-1c=0.Based on equalities (20) and (21), we can find that if max⁡(∂j(0))≥0, the minimum j(l) is attained at the point equal to 0, which means l∗=0. While if max⁡(∂j(0))<0, the optimum l∗ is obtained by finding an intersection between ∂j(l) and the x-axis (as Figure 1 shows). This can be done efficiently by sorting every step points. The whole algorithm is described as shown in Algorithm 2.Algorithm 2:Efficient line search for solving OP2.
(1)Input: wt,wt-1c,A0,B0,Z0,Cp,Cn,xi,yi
(2)Compute max(∂j(0)) with formula (20) and (21)
(3)if  max(∂j(0))≥0  then
(4)l∗=0
(5)else
(6)L←{li∣li=(1-yixiwt-1c)/yixi(wt-wt-1c)>0} // find the step point sets with li>0
(7)  SortL in ascending order →{l1,…,lK} where K=|L|
(8)l0=0 // begin with zero point
(9)for  k=1,…,K  do
(10)∂j(lk)=∂j(lk-1)+A0(lk-lk-1)
(11)if  ∂j(lk)>0  then
(12)l∗=(-∑i=0k-1Bi)/A0 // Case 1  l∗ lies in the slash area
whereBi=B0ifi=0Cpyixi(wt-1c-wt)ifi≠0,yi=+1Cnyixi(wt-1c-wt)elsei≠0,yi=-1
(13)else
(14)∂j(lk)=∂j(lk)+Bk
(15)if  ∂j(lk)≥0  then
(16)l∗=lk // Case 2  l∗ lies in the vertical area
(17)end if
(18)end if
(19)end for
(20)end if
(21)Output: l∗.For Algorithm2, the theorem below guarantees that it only requires O(nlog⁡n) time.Theorem 1.
The total running time of Algorithm2 is O(nlog⁡n).Proof.
From the pseudo code of Algorithm2, we can find that the time of step (1) to step (4) is O(1), and step (6) needs at most O(n) time. Step (7) is sorting, which can be implemented in O(Klog⁡K) time. Step (9) to step (19) take O(K) time, and other steps all require O(1) time. Therefore, Algorithm 2 has the complexity of O(n+Klog⁡K). Since in practice K≤n, which means that even in the worst case the total running time of Algorithm 2 is O(nlog⁡n).


## 4. Experiments

In this section, we will compare our classifier with other existing learners for maximizingF-measure and give details about results on the benchmark datasets.


### 4.1. Baselines and Datasets

We evaluate the performance of our algorithm (termed as BM-ls-CS) with SVMperf [11], SVM-CS [16], BM-nls-CS, and LR-MLE [8], which are all F-measure based learners. The first three baselines follow EUM approach, while the last one falls into DT approach. More specifically, the first one, SVMperf, uses direct method and is the most popular imbalanced classifier for EUM approach. It adopts the structured SVM to maximize F-measure and applies the cutting plane algorithm for inner optimization, which is similar to ours. The second one, SVM-CS, is a recently proposed classifier, and as mentioned before, it belongs to indirect method. Same as our BM-ls-CS, it is a cost-based algorithm. The main difference between SVM-CS and ours is the inner solver. The third comparison algorithm BM-nls-CS uses bundle method without line search as the optimizer. We include it in evaluations to see whether the line search technology we proposed can improve the speed of convergence. In addition, we also compare our algorithm with a decision-theoretic method named LR-MLE, which is recently proposed by Ye et al. We select it as the fourth baseline, since it is an efficient algorithm and only needs O(n2) time for computing the optimal predictions. Finally, it should be noted that, in our experiments, we do not implement the F-measure based learners with “approximative solver” (such as SGD). Although these learners may have a low per-iteration cost and low total training time, their approximations to the optimal solution are crude and often fail to achieve a precise solution.All the comparison algorithms adopt the same experimental setup and are carried out on a Linux machine with 3.4 GHz Intel Core and 8 GB of RAM. The penalty parameterC for SVMperf is selected from set 2-4,…,28 by cross-validation, and the corresponding parameters for SVM-CS and LR-MLE are determined from set n·2-4,…,n·28 (the parameters C in SVMperf and C in SVM-CS and LR-MLE satisfy the following relation: Cperf=n·Ccs=n·CLR-MLE), while for BM-ls-CS and BM-nls-CS, the regularization parameter δ∈2-8/100,…,24/100 (the parameters C in SVMperf and δ in bundle method satisfy the following relation: C=1/100δ) and the parameter λ in formula (12) are selected from {0.1,0.2,…,1}. For all the cost-sensitive algorithms (BM-ls-CS, SVM-CS, and BM-nls-CS), we set Cp=1-t/2 and Cn=t/2. The proper t is chosen from t∈{0.1,0.2,…,0.9}, which is suggested by Proposition 6 in Parambath’s paper. The approximation gap ε is set as ε=10-3 for each EUM algorithm.With the algorithms above (SVMperf, SVM-CS, BM-nls-CS,LR-MLE, and BM-ls-CS), we perform experiments on six datasets, which are a3a, acoustic, ijcnn1, letter, news20, and satimage. We choose them as the experimental sets, since they are all imbalanced datasets with large sample sizes. These datasets can be downloaded from LIBSVM website (https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/), and their characteristics are summarized in Table 2.Table 2
Characteristics of the experimental datasets.
Dataset
#Examples
#Features
Min (%)
a3a
32561
123
0.2396
acoustic
98528
50
0.2324
jcnn1
141691
22
0.0971
letter
20000
16
0.0396
news20
19928
62061
0.0500
satimage
6435
36
0.2417In Table2, the “#Examples” and “#Features” denote the number of examples and features, respectively. “Min” represents the proportion of examples in the minority class. For each dataset, we use the same split as in LIBSVM repository and report the results from the following two aspects.


### 4.2. Experimental Results

#### 4.2.1. The Performance Behaviors of Different Learners (F1 Value and Running Time)

Since the main goal of this paper is to produce an efficientF-measure learner, in the first part of experiments, we are concerned about the performance behaviors of different algorithms, and the comparison results are depicted in Table 3.Table 3
TheF1 value and running time of different algorithms.
a3a
acoustic
ijcnn1
letter
news20
satimage
SVMperf
67.08
60.88
47.16
52.38
98.04
95.58
81.81 s
86.81 s
75.89 s
1.53 s
71.95 s
4.30 s
SVM-CS
67.55
63.26
55.97
63.12
81.67
95.78
3.22 s
0.97 s
0.84 s
0.68 s
0.21 s
0.02 s
BM-nls-CS
67.38
64.34
56.13
63.37
98.70
96.57
0.64 s
1.13 s
0.26 s
0.11 s
41.04 s
0.04 s
LR-ML
E
67.36
60.22
52.84
52.57
88.65
97.39
6.97 s
38.84 s
5.12 s
0.19 s
18.12 s
0.02 s
BM-ls-CS
67.38
64.02
56.19
63.38
98.70
96.61
0.19 s
0.49 s
0.14 s
0.03 s
12.64 s
0.01 sNote that, in Table3, there are two values in each blank, the top one denotes the objective value measured by F1, and the bottom one is the running time in seconds. Higher value and lower time are better.From Table3, we can find that when measured by F1, the performances of EUM algorithms (SVMperf, SVM-CS, BM-nls-CS, and BM-ls-CS) and DT algorithm (LR-MLE) vary from one dataset to another, and there is no one algorithm that can outperform other algorithms on all the datasets. For example, on news20 set, EUM algorithms are almost better than DT algorithm, while, on satimage set, DT algorithm is superior to EUM algorithms. This is coherent with the result of Ye et al., according to which both two approaches are effective, and it is difficult to say which one is better on the large datasets [8]. Meanwhile, statistics show that, for the EUM approach, three cost-sensitive algorithms (SVM-CS, BM-nls-CS, and BM-ls-CS) are better than (or comparable to) SVMperf, which once again indicate that we can produce a good F-measure based classifier by transforming it into a cost-sensitive problem.Moreover, Table3 also shows that if measured by running time, our BM-ls-CS consistently outperforms SVMperf, BM-nls-CS, and LR-MLE on all benchmark datasets. For example, when compared with SVMperf, BM-ls-CS performs better in terms of both F1 value and CPU time. Especially for CPU time, BM-ls-CS can gain speedups of hundreds orders of magnitude over SVMperf on several experimental datasets. Similar comparison results appear with BM-nls-CS and LR-MLE. Statistics show that our algorithm with line search is significantly faster than those two baselines, while obtaining better (or comparable) F1 values. However, for SVM-CS which is implemented by Liblinear, it is a bit different. Experimental results show that our algorithm is faster than SVM-CS on five out of the six datasets (a3a, acoustic, ijcnn1, letter, and satimage) and is only slower than SVM-CS on news20. Statistics demonstrate that BM-ls-CS performs better than SVM-CS in terms of F1 value (98.70 versus 81.67), while SVM-CS can achieve speedups of several orders of magnitude over BM-ls-CS (0.21 s versus 12.64 s). The reason maybe lies in their different inner optimizers. SVM-CS adopts Liblinear, which is specially designed for the dataset with large features, while the bundle method we use does not give special consideration of this situation (note that the cutting plane algorithm which SVMperf uses also does not consider this situation).All the statistical data above proves that as anF-measure based learner, our BM-ls-CS is both efficient and effective, when compared with other existing baselines.Finally, from Table3 we can observe that, although BM-nls-CS and SVMperf solve the same equivalent problem with similar optimization technique, their performances are quite different. Experimental results show that BM-nls-CS is faster than SVMperf on all the datasets, and it is largely due to their different implementations (e.g., QP solver). Therefore, in order to see whether our line search technology can enhance the convergence speed, in the following we will only compare the BM-ls-CS with BM-nls-CS for fair play.


#### 4.2.2. The Comparison between BM-ls-CS and BM-nls-CS

In the second part of experiments, we are interested in the convergence speed between our algorithm and BM-nls-CS, which uses the same inner solver without line search. Thus, we consider the number of iterations used in reducing the primal objective value, and Figure2 gives the objective value as a function of training iterations for the two algorithms on various datasets.Figure 2
Convergence behaviors of the BM-ls-CS and BM-nls-CS.
(a)
a3a
(b)
acoustic
(c)
ijcnn1
(d)
letter
(e)
news20
(f)
satimageFrom Figure2, we can find that even though the BM-nls-CS ultimately converges to the minimum, its values heavily fluctuate during the iterations. The reason for these fluctuations lies in the fact that, during the iterations, the cutting plane selected by BM-nls-CS only guarantees that dual value monotonically increases. However, there is no guarantee that such a cutting plane will lead the primal value to monotonically decrease, as the figure depicts that F(wt+1)>F(wt) often occurs. On the contrary, it is clear from the figure that our algorithm enjoys progression with “strictly” decreasing objective values and achieves speedups of more than one order of magnitude over BM-nls-CS. This fact implies that our line search technology can help to avoid the “stalling” steps and accelerate the convergence speed of algorithm.


## 4.1. Baselines and Datasets

We evaluate the performance of our algorithm (termed as BM-ls-CS) with SVMperf [11], SVM-CS [16], BM-nls-CS, and LR-MLE [8], which are all F-measure based learners. The first three baselines follow EUM approach, while the last one falls into DT approach. More specifically, the first one, SVMperf, uses direct method and is the most popular imbalanced classifier for EUM approach. It adopts the structured SVM to maximize F-measure and applies the cutting plane algorithm for inner optimization, which is similar to ours. The second one, SVM-CS, is a recently proposed classifier, and as mentioned before, it belongs to indirect method. Same as our BM-ls-CS, it is a cost-based algorithm. The main difference between SVM-CS and ours is the inner solver. The third comparison algorithm BM-nls-CS uses bundle method without line search as the optimizer. We include it in evaluations to see whether the line search technology we proposed can improve the speed of convergence. In addition, we also compare our algorithm with a decision-theoretic method named LR-MLE, which is recently proposed by Ye et al. We select it as the fourth baseline, since it is an efficient algorithm and only needs O(n2) time for computing the optimal predictions. Finally, it should be noted that, in our experiments, we do not implement the F-measure based learners with “approximative solver” (such as SGD). Although these learners may have a low per-iteration cost and low total training time, their approximations to the optimal solution are crude and often fail to achieve a precise solution.All the comparison algorithms adopt the same experimental setup and are carried out on a Linux machine with 3.4 GHz Intel Core and 8 GB of RAM. The penalty parameterC for SVMperf is selected from set 2-4,…,28 by cross-validation, and the corresponding parameters for SVM-CS and LR-MLE are determined from set n·2-4,…,n·28 (the parameters C in SVMperf and C in SVM-CS and LR-MLE satisfy the following relation: Cperf=n·Ccs=n·CLR-MLE), while for BM-ls-CS and BM-nls-CS, the regularization parameter δ∈2-8/100,…,24/100 (the parameters C in SVMperf and δ in bundle method satisfy the following relation: C=1/100δ) and the parameter λ in formula (12) are selected from {0.1,0.2,…,1}. For all the cost-sensitive algorithms (BM-ls-CS, SVM-CS, and BM-nls-CS), we set Cp=1-t/2 and Cn=t/2. The proper t is chosen from t∈{0.1,0.2,…,0.9}, which is suggested by Proposition 6 in Parambath’s paper. The approximation gap ε is set as ε=10-3 for each EUM algorithm.With the algorithms above (SVMperf, SVM-CS, BM-nls-CS,LR-MLE, and BM-ls-CS), we perform experiments on six datasets, which are a3a, acoustic, ijcnn1, letter, news20, and satimage. We choose them as the experimental sets, since they are all imbalanced datasets with large sample sizes. These datasets can be downloaded from LIBSVM website (https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/), and their characteristics are summarized in Table 2.Table 2
Characteristics of the experimental datasets.
Dataset
#Examples
#Features
Min (%)
a3a
32561
123
0.2396
acoustic
98528
50
0.2324
jcnn1
141691
22
0.0971
letter
20000
16
0.0396
news20
19928
62061
0.0500
satimage
6435
36
0.2417In Table2, the “#Examples” and “#Features” denote the number of examples and features, respectively. “Min” represents the proportion of examples in the minority class. For each dataset, we use the same split as in LIBSVM repository and report the results from the following two aspects.


## 4.2. Experimental Results

### 4.2.1. The Performance Behaviors of Different Learners (F1 Value and Running Time)

Since the main goal of this paper is to produce an efficientF-measure learner, in the first part of experiments, we are concerned about the performance behaviors of different algorithms, and the comparison results are depicted in Table 3.Table 3
TheF1 value and running time of different algorithms.
a3a
acoustic
ijcnn1
letter
news20
satimage
SVMperf
67.08
60.88
47.16
52.38
98.04
95.58
81.81 s
86.81 s
75.89 s
1.53 s
71.95 s
4.30 s
SVM-CS
67.55
63.26
55.97
63.12
81.67
95.78
3.22 s
0.97 s
0.84 s
0.68 s
0.21 s
0.02 s
BM-nls-CS
67.38
64.34
56.13
63.37
98.70
96.57
0.64 s
1.13 s
0.26 s
0.11 s
41.04 s
0.04 s
LR-ML
E
67.36
60.22
52.84
52.57
88.65
97.39
6.97 s
38.84 s
5.12 s
0.19 s
18.12 s
0.02 s
BM-ls-CS
67.38
64.02
56.19
63.38
98.70
96.61
0.19 s
0.49 s
0.14 s
0.03 s
12.64 s
0.01 sNote that, in Table3, there are two values in each blank, the top one denotes the objective value measured by F1, and the bottom one is the running time in seconds. Higher value and lower time are better.From Table3, we can find that when measured by F1, the performances of EUM algorithms (SVMperf, SVM-CS, BM-nls-CS, and BM-ls-CS) and DT algorithm (LR-MLE) vary from one dataset to another, and there is no one algorithm that can outperform other algorithms on all the datasets. For example, on news20 set, EUM algorithms are almost better than DT algorithm, while, on satimage set, DT algorithm is superior to EUM algorithms. This is coherent with the result of Ye et al., according to which both two approaches are effective, and it is difficult to say which one is better on the large datasets [8]. Meanwhile, statistics show that, for the EUM approach, three cost-sensitive algorithms (SVM-CS, BM-nls-CS, and BM-ls-CS) are better than (or comparable to) SVMperf, which once again indicate that we can produce a good F-measure based classifier by transforming it into a cost-sensitive problem.Moreover, Table3 also shows that if measured by running time, our BM-ls-CS consistently outperforms SVMperf, BM-nls-CS, and LR-MLE on all benchmark datasets. For example, when compared with SVMperf, BM-ls-CS performs better in terms of both F1 value and CPU time. Especially for CPU time, BM-ls-CS can gain speedups of hundreds orders of magnitude over SVMperf on several experimental datasets. Similar comparison results appear with BM-nls-CS and LR-MLE. Statistics show that our algorithm with line search is significantly faster than those two baselines, while obtaining better (or comparable) F1 values. However, for SVM-CS which is implemented by Liblinear, it is a bit different. Experimental results show that our algorithm is faster than SVM-CS on five out of the six datasets (a3a, acoustic, ijcnn1, letter, and satimage) and is only slower than SVM-CS on news20. Statistics demonstrate that BM-ls-CS performs better than SVM-CS in terms of F1 value (98.70 versus 81.67), while SVM-CS can achieve speedups of several orders of magnitude over BM-ls-CS (0.21 s versus 12.64 s). The reason maybe lies in their different inner optimizers. SVM-CS adopts Liblinear, which is specially designed for the dataset with large features, while the bundle method we use does not give special consideration of this situation (note that the cutting plane algorithm which SVMperf uses also does not consider this situation).All the statistical data above proves that as anF-measure based learner, our BM-ls-CS is both efficient and effective, when compared with other existing baselines.Finally, from Table3 we can observe that, although BM-nls-CS and SVMperf solve the same equivalent problem with similar optimization technique, their performances are quite different. Experimental results show that BM-nls-CS is faster than SVMperf on all the datasets, and it is largely due to their different implementations (e.g., QP solver). Therefore, in order to see whether our line search technology can enhance the convergence speed, in the following we will only compare the BM-ls-CS with BM-nls-CS for fair play.


### 4.2.2. The Comparison between BM-ls-CS and BM-nls-CS

In the second part of experiments, we are interested in the convergence speed between our algorithm and BM-nls-CS, which uses the same inner solver without line search. Thus, we consider the number of iterations used in reducing the primal objective value, and Figure2 gives the objective value as a function of training iterations for the two algorithms on various datasets.Figure 2
Convergence behaviors of the BM-ls-CS and BM-nls-CS.
(a)
a3a
(b)
acoustic
(c)
ijcnn1
(d)
letter
(e)
news20
(f)
satimageFrom Figure2, we can find that even though the BM-nls-CS ultimately converges to the minimum, its values heavily fluctuate during the iterations. The reason for these fluctuations lies in the fact that, during the iterations, the cutting plane selected by BM-nls-CS only guarantees that dual value monotonically increases. However, there is no guarantee that such a cutting plane will lead the primal value to monotonically decrease, as the figure depicts that F(wt+1)>F(wt) often occurs. On the contrary, it is clear from the figure that our algorithm enjoys progression with “strictly” decreasing objective values and achieves speedups of more than one order of magnitude over BM-nls-CS. This fact implies that our line search technology can help to avoid the “stalling” steps and accelerate the convergence speed of algorithm.


## 4.2.1. The Performance Behaviors of Different Learners (F1 Value and Running Time)

Since the main goal of this paper is to produce an efficientF-measure learner, in the first part of experiments, we are concerned about the performance behaviors of different algorithms, and the comparison results are depicted in Table 3.Table 3
TheF1 value and running time of different algorithms.
a3a
acoustic
ijcnn1
letter
news20
satimage
SVMperf
67.08
60.88
47.16
52.38
98.04
95.58
81.81 s
86.81 s
75.89 s
1.53 s
71.95 s
4.30 s
SVM-CS
67.55
63.26
55.97
63.12
81.67
95.78
3.22 s
0.97 s
0.84 s
0.68 s
0.21 s
0.02 s
BM-nls-CS
67.38
64.34
56.13
63.37
98.70
96.57
0.64 s
1.13 s
0.26 s
0.11 s
41.04 s
0.04 s
LR-ML
E
67.36
60.22
52.84
52.57
88.65
97.39
6.97 s
38.84 s
5.12 s
0.19 s
18.12 s
0.02 s
BM-ls-CS
67.38
64.02
56.19
63.38
98.70
96.61
0.19 s
0.49 s
0.14 s
0.03 s
12.64 s
0.01 sNote that, in Table3, there are two values in each blank, the top one denotes the objective value measured by F1, and the bottom one is the running time in seconds. Higher value and lower time are better.From Table3, we can find that when measured by F1, the performances of EUM algorithms (SVMperf, SVM-CS, BM-nls-CS, and BM-ls-CS) and DT algorithm (LR-MLE) vary from one dataset to another, and there is no one algorithm that can outperform other algorithms on all the datasets. For example, on news20 set, EUM algorithms are almost better than DT algorithm, while, on satimage set, DT algorithm is superior to EUM algorithms. This is coherent with the result of Ye et al., according to which both two approaches are effective, and it is difficult to say which one is better on the large datasets [8]. Meanwhile, statistics show that, for the EUM approach, three cost-sensitive algorithms (SVM-CS, BM-nls-CS, and BM-ls-CS) are better than (or comparable to) SVMperf, which once again indicate that we can produce a good F-measure based classifier by transforming it into a cost-sensitive problem.Moreover, Table3 also shows that if measured by running time, our BM-ls-CS consistently outperforms SVMperf, BM-nls-CS, and LR-MLE on all benchmark datasets. For example, when compared with SVMperf, BM-ls-CS performs better in terms of both F1 value and CPU time. Especially for CPU time, BM-ls-CS can gain speedups of hundreds orders of magnitude over SVMperf on several experimental datasets. Similar comparison results appear with BM-nls-CS and LR-MLE. Statistics show that our algorithm with line search is significantly faster than those two baselines, while obtaining better (or comparable) F1 values. However, for SVM-CS which is implemented by Liblinear, it is a bit different. Experimental results show that our algorithm is faster than SVM-CS on five out of the six datasets (a3a, acoustic, ijcnn1, letter, and satimage) and is only slower than SVM-CS on news20. Statistics demonstrate that BM-ls-CS performs better than SVM-CS in terms of F1 value (98.70 versus 81.67), while SVM-CS can achieve speedups of several orders of magnitude over BM-ls-CS (0.21 s versus 12.64 s). The reason maybe lies in their different inner optimizers. SVM-CS adopts Liblinear, which is specially designed for the dataset with large features, while the bundle method we use does not give special consideration of this situation (note that the cutting plane algorithm which SVMperf uses also does not consider this situation).All the statistical data above proves that as anF-measure based learner, our BM-ls-CS is both efficient and effective, when compared with other existing baselines.Finally, from Table3 we can observe that, although BM-nls-CS and SVMperf solve the same equivalent problem with similar optimization technique, their performances are quite different. Experimental results show that BM-nls-CS is faster than SVMperf on all the datasets, and it is largely due to their different implementations (e.g., QP solver). Therefore, in order to see whether our line search technology can enhance the convergence speed, in the following we will only compare the BM-ls-CS with BM-nls-CS for fair play.


## 4.2.2. The Comparison between BM-ls-CS and BM-nls-CS

In the second part of experiments, we are interested in the convergence speed between our algorithm and BM-nls-CS, which uses the same inner solver without line search. Thus, we consider the number of iterations used in reducing the primal objective value, and Figure2 gives the objective value as a function of training iterations for the two algorithms on various datasets.Figure 2
Convergence behaviors of the BM-ls-CS and BM-nls-CS.
(a)
a3a
(b)
acoustic
(c)
ijcnn1
(d)
letter
(e)
news20
(f)
satimageFrom Figure2, we can find that even though the BM-nls-CS ultimately converges to the minimum, its values heavily fluctuate during the iterations. The reason for these fluctuations lies in the fact that, during the iterations, the cutting plane selected by BM-nls-CS only guarantees that dual value monotonically increases. However, there is no guarantee that such a cutting plane will lead the primal value to monotonically decrease, as the figure depicts that F(wt+1)>F(wt) often occurs. On the contrary, it is clear from the figure that our algorithm enjoys progression with “strictly” decreasing objective values and achieves speedups of more than one order of magnitude over BM-nls-CS. This fact implies that our line search technology can help to avoid the “stalling” steps and accelerate the convergence speed of algorithm.


## 5. Conclusion

In this paper, we have presented a novel cost-sensitive SVM algorithm that can optimizeF-measure efficiently. We began our work with an explicit transformation from maximizing F-measure to cost-sensitive classification and then proposed to use the bundle method for the inner optimization, which had O(1/ε) rate of convergence. For the problem where the existing bundle method only guaranteed that the dual objective increases monotonically and did not guarantee that the primal objective decreases monotonically, an efficient line search algorithm has been proposed, which can avoid this undesirable effect, and accelerated the practical convergence speed of our BM-ls-CS algorithm. Experiments on the benchmark datasets showed that when compared with other existing F-measure based learners, BM-ls-CS we proposed not only gave better generalization performance, but also provided significant speedups during the training. There are two issues that are worthy of further investigations in the future. The first topic is to extend our approach to other imbalanced measures such as PAUC [23] or SAUC [24] and design the efficient algorithms for optimizing these metrics. The second one is to solve our problem from the view of Multiobjective Optimization, since recent works on MOO [25, 26] show that a cost-sensitive problem can be regarded as a multiobjective problem. In the future, we plan to produce an efficient F-measure classifier through the Multiobjective Optimization.



---

*Source: 5873769-2016-05-10.xml*