# A Robust Probability Classifier Based on the Modifiedχ

Authors: Yongzhi Wang; Yuli Zhang; Jining Yi; Honggang Qu; Jinli Miu
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

We propose a robust probability classifier model to address
classification problems with data uncertainty. A class-conditional probability
distributional set is constructed based on the modifiedχ
2-distance. Based on a “linear combination assumption” for the posterior class-conditional probabilities,
we consider a classification criterion using the weighted sum of the
posterior probabilities. An optimal robust minimax classifier is defined as the
one with the minimal worst-case absolute error loss function value over all
possible distributions belonging to the constructed distributional set. Based
on the conic duality theorem, we show that the resulted optimization problem
can be reformulated into a second order cone programming problem
which can be efficiently solved by interior algorithms. The robustness of the
proposed model can avoid the “overlearning” phenomenon on training sets
and thus keep a comparable accuracy on test sets. Numerical experiments
validate the effectiveness of the proposed model and further show that it also
provides promising results on multiple classification problems.


---

## Body

## 1. Introduction

Statistics classification has been extensively studied in the field of machine learning and statistics. A typical classification problem is to design a linear or nonlinear classifier based on a known training set such that a new observation can be assigned to one of the known classes. Many classification models have been proposed, such as the naive Bayes classifiers (NBC) [1, 2], artificial neural network [3], and support vector machines (SVM) [4].In real-world classification problems, it is often the case that the data of training set are imprecise due to unavoidable observational noises in the process of data collection or data approximation from incomplete samples. One way to handle the data uncertainty is to design a robust classifier in the sense that it has the minimal worst-case misclassification probability for the training sets. The idea of robustness has been widely applied in many traditional machine learning and statistics techniques, such as robust Bayes classifiers [5], robust support vector machines [6], and robust quadratic regressions [7]. Robust classifiers are highly related to the recently flourished research on robust optimization. For more recent developments on robust optimization, we refer the readers to the excellent book [8] and reviews [9, 10].Recently [11, 12] have proposed a robust minimax approach called the minimax probability machine to design a binary classifier. Unlike the traditional methods, they make no assumption on the class-conditional distributions, but only the mean and covariance matrix of each class are assumed to be known. Under this assumption, the designed classifier is determined by minimizing the worst-case probability of misclassification under all possible choices of class-conditional distributions with the given mean and covariance matrix. By reformulating the classifier design problem into second order cone programming, they show that the computational complexity of the proposed approach is similar to that of SVM. Because of its computational advantage and competitive performance with other current methods, this approach has been further extended to incorporating other features. El Ghaoui et al. [13] propose a robust classification model by minimizing the worst-case value of a given loss function over all possible choices of the data in a bounded hyperrectangles. Three loss functions from SVM, logistic regressions, and minimax probability machines are studied in [13]. Based on the same assumption of known mean and covariance matrix, [14, 15] propose the biased minimax probability machines to address the biased classification problem and further generalize it to obtain the minimum error minimax probability machines. Hoi and Lyu [16] study a quadratic classifier with positive definite covariance matrices and further consider the problem of finding a convex set to cover known sampled data in one class while minimizing the worst-case misclassification probability. The minimax probability machines have also been extended to solve multiple classification problems; see [17, 18].In this paper, we propose a robust probability classifier (RPC) based on the modifiedχ
2-distance. Specifically, for a given training set, we first estimate the probability of each sample belonging to each class based on a feature, which is called a nominal class-conditional distribution. Then a ϵ-confidence probability distributional set P
ϵ is constructed based on the nominal class-conditional distributions and the modified χ
2-distance, where parameter ϵ controls the size of the constructed set. Unlike the “conditional independence assumption” in NBC, we introduce a “linear combination assumption” for the posterior class-conditional probabilities, and the proposed classifier takes a linear combination form of these probabilities based on different features and it will assign the sample to the class with the maximal posterior probability. To get a robust classifier, we minimize the worst-case loss function value over all possible choices of class-conditional distributions over the distributional set P
ϵ. The underlying assumption is that, due to observational noises, we cannot obtain the true probability distribution of each class, but it can be well estimated by the nominal distribution such that it belongs to the distributional set P
ϵ.Our two major contributions are as follows. First in our model, the proposed distributional setP
ϵ is based on the nominal distribution and the modified χ
2-distance. As pointed in [19], such distributional set can make use of more information conveyed in the training set compared with traditional robust approaches which only use the information of mean and covariance matrix. To the best of our knowledge, this is among the first study of classification models considering complex distribution information. Although [20] considers a ϵ-contaminated robust support vector machine model, its distributional set is defined by easily handled linear constraints and its analysis is highly dependent on characterization of the extreme points of this set. Here our proposed distributional set is defined by nonlinear quadratic function and is analyzed by the conic duality theorem. Second by taking the absolute error function as the loss function, we show how to transform our robust minimax optimization problem into computable second order cone programming. The absolute error function in the objective function also distinguishes our model from other existing models, such as the soft-margin support vector machine which uses the Hinge loss function [21, 22] and the logistic regression which uses the negative log likelihood function [23]. Note that the absolute error function is essential in our model to obtain a tractable optimization problem for the proposed model. Numerical experiments on real-world application validate the effectiveness of the proposed classifier and further show that the proposed classifier also performs well for multiple classification problems.The paper proceeds as follows. Section2 introduces the proposed robust minimax probability classifier based on the modified χ
2-distance and discusses how to construct the desired distributional set P
ϵ. Section 3 provides an equivalent reformulation by handling the robust constraints and robust objective separately. Numerical experiments on real-world data set are carried out to validate the effectiveness of the proposed classifier in Section 4. Section 5 concludes this paper and gives future research directions.


## 2. Classifier Models

In this section, a simple probability classifier is first presented and then it is extended to handle data uncertainty by introducing a distributional setP
ϵ. We also discuss how to construct this distributional set based on training data set.Consider a multiclass multifeature classification problem in which each sample contains|
L
| features, and there are |
J
| classes and |
I
| samples. Specifically, given a training set (
X
,
Y
)
∈
ℝ
|
I
|
×
|
L
|
×
{
0,1
}
|
I
|
×
|
J
|, where x
i
,
l denotes the lth feature of the ith sample and y
i
,
j
=
1 if the ith sample belongs to jth class; otherwise, y
i
,
j
=
0. In the following context, we will also use the term x
i to denote the ith sample; that is, x
i
=
(
x
i
,
1
,
…
,
x
i
,
|
L
|
).


### 2.1. Probability Classifier

Bayes classifiers assign an observationx to the j
*
(
x
)th class which has the maximal posterior probability; that is,
(1)
j
*
(
x
)
=
arg
max
⁡
j
∈
J
P
(
j
∣
x
)
,
and P
(
j
∣
x
) is the posterior probability function, that is, the conditional probability that the sample belongs to the jth class, given that we know it has feature vector x.Using Bayes’ theorem, we have(2)
P
(
j
∣
x
)
=
P
(
j
)
P
(
x
∣
j
)
P
(
x
)
∝
P
(
j
)
P
(
x
∣
j
)
,
where P
(
j
) is the prior probability of the jth class, P
(
x
∣
j
) is the conditional probability for the ith class, and P
(
x
) is the probability that a sample has feature vector x. Note that P
(
x
) is a constant if the values of the feature variables are known and thus can be omitted. To design an effective Bayes classifier, the key issue is estimating the class-conditional probability P
(
x
∣
j
) or the joint probability P
(
x
,
j
). Theoretically, using the chain rule, we have
(3)
P
(
x
,
j
)
=
P
(
j
)
P
(
x
1
∣
j
)
P
(
x
2
∣
j
,
x
1
)
⋯
P
(
x
|
L
|
∣
j
,
x
1
,
…
,
x
|
L
-
1
|
)
.
However such estimating method leads to the problem of “dimension disaster.”To address this issue, the naive Bayes classifier makes the following “conditional independence assumption”:(4)
P
(
x
∣
j
)
=
∏
l
=
1
|
L
|
‍
p
j
l
(
x
)
,
where p
j
l
(
x
)
:
=
P
(
x
l
∣
j
) is the class-conditional probability that the observation x belongs to the jth class based on the lth feature. Here we introduce another “linear combination assumption” for the class-conditional probability:
(5)
P
(
x
∣
j
)
=
∑
l
=
1
|
L
|
‍
β
j
l
p
j
l
(
x
)
,
where β
j
l is a coefficient. Compared with the “conditional independence assumption,” which uses the probabilistic information in terms of multiplication, the proposed “linear combination assumption” uses the probabilistic information in terms of weighted sum. We will further discuss the rationality of this assumption at the end of this subsection.Under this assumption, we have(6)
P
(
j
∣
x
)
∝
P
(
j
)
P
(
x
∣
j
)
=
P
(
j
)
∑
l
=
1
|
L
|
‍
β
j
l
p
j
l
(
x
)
=
∑
l
=
1
|
L
|
‍
α
j
l
p
j
l
(
x
)
,
where α
j
l
:
=
P
(
j
)
β
j
l denotes the probability weight of the lth feature for the jth class.To obtain the optimal probability classifier based on the “linear combination assumption,” it is natural to consider the following optimization problem:(7)
min
⁡
α
∈
Θ
∑
j
∈
J
‍
∑
i
∈
I
‍
L
(
P
(
j
∣
x
i
)
,
y
i
,
j
)
,
where L
(
·
,
·
)
:
ℝ
×
ℝ
→
R
+ is a prespecified loss function. In the following context, we will take the absolute error function as our loss function; that is, L
(
x
,
y
)
=
|
x
-
y
|. In view of its probability property, it is straightforward to impose the following constraints on the posterior probability:
(8)
0
≤
f
(
j
∣
x
i
)
≤
1
,
∀
i
∈
I
,
j
∈
J
.
Under such constraints, we have that
(9)
∑
j
∈
J
‍
∑
i
∈
I
‍
L
(
f
(
j
∣
x
i
)
,
y
i
,
j
)
=
∑
j
∈
J
‍
∑
i
∈
I
‍
|
f
(
j
∣
x
i
)
-
y
i
,
j
|
=
∑
j
∈
J
‍
∑
i
∈
I
‍
{
y
i
,
j
(
1
-
f
(
j
∣
x
i
)
)
+
(
1
-
y
i
,
j
)
f
(
j
∣
x
i
)
}
=
∑
j
∈
J
‍
∑
i
∈
I
‍
(
1
-
2
y
i
,
j
)
f
(
j
∣
x
i
)
+
|
I
|
,
where |
I
|
=
∑
j
∈
J
‍
∑
i
∈
I
‍
y
i
,
j.Thus the optimal probability classifier (PC) problem can be formulated as follows:(10)
(
PC
)
min
⁡
∑
j
∈
J
‍
∑
i
∈
I
‍
(
1
-
2
y
i
,
j
)
∑
l
∈
L
‍
α
j
l
p
i
,
j
l
+
|
I
|
s
.
t
.
KK
0
≤
∑
l
∈
L
‍
α
j
l
p
i
,
j
l
≤
1
,
∀
i
∈
I
,
j
∈
J
.It is no doubt that the “linear combination assumption” may not work sometimes. However, we justify the proposed classifier by the following facts.(1)
As an intuitive interpretation, note thatp
j
l
(
x
) estimates the probability of the observation x belonging to the jth class only based on the lth feature; thus it provides partial probabilistic information of the sample. Hence we can interpret the weight α
j
l as certain degree of trust on the information, and in this sense, the “linear combination assumption” is a way of combining evidence from different sources. Similar ideas can also be found in the theory of evidence; see the Dempster-Shafer theory [24, 25].
(2)
In terms of the classification performance, in the worst case, the proposed classifier may put all weight on one feature; thus in such case, it is equivalent to a Bayes classifier based on a well-selected feature. If each class has its “typical” feature which can distinguish it from other classes, the proposed classifier has the ability to learn this property by putting different weights on different features for different classes and thus provides better classification performance. A real-life application on lithology classification problems also validates its classification performance by comparison with support vector machines and the naive Bayes classifier.
(3)
Another advantage of the proposed classifier is its high computability. As we show in Section3, the proposed classifier and its robust counterpart problems can be reformulated as second order cone programming problems and thus can be solved by interior algorithms in polynomial time.


### 2.2. Robust Probability Classifier

Due to observational noises, the true class-conditional probability distribution is often difficult to obtain. Instead we can construct a confidence distributional set which contains the true distribution. Unlike the traditional distributional sets in minimax probability machines, which only utilize mean and covariance matrix, we construct our class-conditional probability distributional set based on the modifiedχ
2-distance which uses more information from the samples.The modifiedχ
2-distance d
(
·
,
·
)
:
ℝ
m
×
ℝ
m
→
R is used to measure the distance between two discrete probability distribution vectors in statistics. For given p
=
(
p
1
,
…
,
p
m
)
T and q
=
(
q
1
,
…
,
q
m
)
T, it is defined as
(11)
d
(
q
,
p
)
=
∑
j
=
1
m
‍
(
q
j
-
p
j
)
2
p
j
.
Based on the modified χ
2-distance, we present the following class-conditional probability distributional set:
(12)
P
ϵ
=
{
q
i
,
j
l
:
∑
j
‍
q
i
,
j
l
=
1
,
q
i
,
j
l
≥
0
,
∑
j
∈
J
‍
(
q
i
,
j
l
-
p
i
,
j
l
)
2
p
i
,
j
l
≤
ϵ
,
KKKKK
∀
i
∈
I
,
l
∈
L
,
j
∈
J
∑
j
∈
J
‍
(
q
i
,
j
l
-
p
i
,
j
l
)
2
p
i
,
j
l
≤
ϵ
,
}
,
where p
i
,
j
l is the nominal class-conditional distribution probability for the ith sample belonging to the jth class based on the lth feature and the prespecified parameter ϵ is used to control the size of the set.To design a robust classifier, we need to consider the effect of data uncertainty on the objective function and constraints. The robust objective function is to minimize the worst-case loss function value over all the possible distributions in the distributional setP
ϵ; the robust constraints ensure that all the original constraints should also be satisfied for any distribution in P
ϵ. Thus the robust probability classifier problem is of the following form:
(13)
(
RPC
)
min
⁡
{
max
⁡
∑
j
∈
J
‍
∑
i
∈
I
‍
(
1
-
2
y
i
,
j
)
∑
l
∈
L
‍
α
j
l
q
i
,
j
l
KKKKiK
+
|
I
|
:
{
q
i
,
j
l
}
∈
P
ϵ
∑
j
∈
J
‍
}
s
.
t
.
KiK
0
≤
∑
l
∈
L
‍
α
j
l
q
i
,
j
l
≤
1
,
∀
{
q
i
,
j
l
}
∈
P
ϵ
∀
i
,
j
.Note that the above optimization problem has an infinite number of robust constraints and its objective function is also an embedded subproblem. We will show how to solve such minimax optimization problem in Section3.


### 2.3. Construct the Distributional Set

To get the distributional setP
ϵ, we need to define the parameter ϵ and the nominal probability p
i
,
j
l. The selection of parameter ϵ is application based and we will discuss this issue in the numerical experiment section; next we will provide a procedure to calculate p
i
,
j
l.For thelth feature, the following procedure takes an integer K
l indicating the number of data intervals as an input and will output the estimated probability p
i
,
j
l of the ith sample belonging to the jth class.(1)
Sort samples in the increased order and divide them intoK
l intervals such that each interval has at least ⌊
|
I
|
/
K
l
⌋ number of samples. Denote the kth interval by Δ
l
,
k.
(2)
Calculate the total number of samples in thej-class, N
j, the total number of samples in the kth interval, N
l
,
k, and the total number of samples belonging to the j-class in the kth interval, N
l
,
k
,
j.
(3)
For theith sample, if it falls into the kth interval, the class-conditional probability p
i
,
j
l is calculated by
(14)
p
i
,
j
l
=
Prob
(
i
∈
j
∣
x
i
,
l
∈
Δ
l
,
k
)
=
Prob
(
i
∈
j
,
x
i
,
l
∈
Δ
l
,
k
)
Prob
(
x
i
,
l
∈
Δ
l
,
k
)
=
Prob
(
i
∈
j
)
Prob
(
x
i
,
l
∈
Δ
l
,
k
∣
i
∈
j
)
∑
j
′
∈
J
‍
Prob
(
i
∈
j
′
)
Prob
(
x
i
,
l
∈
Δ
l
,
k
∣
i
∈
j
′
)
=
(
N
j
/
|
I
|
)
·
(
N
l
,
k
,
j
/
N
j
)
∑
j
′
∈
J
‍
(
N
j
′
/
|
I
|
)
·
(
N
l
,
k
,
j
′
/
N
j
′
)
=
N
l
,
k
,
j
N
l
,
k
.Note that from the definition of P
ϵ, we easily compute the upper bound q
¯
i
,
j
l and lower bound q
_
i
,
j
l for the true class-conditional probability q
i
,
j
l as follows:
(15)
q
¯
i
,
j
l
=
max
⁡
{
∑
s
∈
J
‍
(
q
i
,
s
l
-
p
i
,
s
l
)
2
p
i
,
s
l
q
i
,
j
l
:
∑
s
‍
q
i
,
s
l
=
1
,
KKKKKKKiK
∑
s
∈
J
‍
(
q
i
,
s
l
-
p
i
,
s
l
)
2
p
i
,
s
l
≤
ϵ
,
q
i
,
s
l
≥
0
,
∀
s
∈
J
}
,
(16)
q
_
i
,
j
l
=
min
⁡
{
∑
s
∈
J
‍
(
q
i
,
s
l
-
p
i
,
s
l
)
2
p
i
,
s
l
q
i
,
j
l
:
∑
s
‍
q
i
,
s
l
=
1
,
KKKKKKKii
∑
s
∈
J
‍
(
q
i
,
s
l
-
p
i
,
s
l
)
2
p
i
,
s
l
≤
ϵ
,
q
i
,
s
l
≥
0
,
∀
s
∈
J
}
.
The above problems can be efficiently solved by a second order cone solver such as SeDuMi [26] or SDPT3 [27].


## 2.1. Probability Classifier

Bayes classifiers assign an observationx to the j
*
(
x
)th class which has the maximal posterior probability; that is,
(1)
j
*
(
x
)
=
arg
max
⁡
j
∈
J
P
(
j
∣
x
)
,
and P
(
j
∣
x
) is the posterior probability function, that is, the conditional probability that the sample belongs to the jth class, given that we know it has feature vector x.Using Bayes’ theorem, we have(2)
P
(
j
∣
x
)
=
P
(
j
)
P
(
x
∣
j
)
P
(
x
)
∝
P
(
j
)
P
(
x
∣
j
)
,
where P
(
j
) is the prior probability of the jth class, P
(
x
∣
j
) is the conditional probability for the ith class, and P
(
x
) is the probability that a sample has feature vector x. Note that P
(
x
) is a constant if the values of the feature variables are known and thus can be omitted. To design an effective Bayes classifier, the key issue is estimating the class-conditional probability P
(
x
∣
j
) or the joint probability P
(
x
,
j
). Theoretically, using the chain rule, we have
(3)
P
(
x
,
j
)
=
P
(
j
)
P
(
x
1
∣
j
)
P
(
x
2
∣
j
,
x
1
)
⋯
P
(
x
|
L
|
∣
j
,
x
1
,
…
,
x
|
L
-
1
|
)
.
However such estimating method leads to the problem of “dimension disaster.”To address this issue, the naive Bayes classifier makes the following “conditional independence assumption”:(4)
P
(
x
∣
j
)
=
∏
l
=
1
|
L
|
‍
p
j
l
(
x
)
,
where p
j
l
(
x
)
:
=
P
(
x
l
∣
j
) is the class-conditional probability that the observation x belongs to the jth class based on the lth feature. Here we introduce another “linear combination assumption” for the class-conditional probability:
(5)
P
(
x
∣
j
)
=
∑
l
=
1
|
L
|
‍
β
j
l
p
j
l
(
x
)
,
where β
j
l is a coefficient. Compared with the “conditional independence assumption,” which uses the probabilistic information in terms of multiplication, the proposed “linear combination assumption” uses the probabilistic information in terms of weighted sum. We will further discuss the rationality of this assumption at the end of this subsection.Under this assumption, we have(6)
P
(
j
∣
x
)
∝
P
(
j
)
P
(
x
∣
j
)
=
P
(
j
)
∑
l
=
1
|
L
|
‍
β
j
l
p
j
l
(
x
)
=
∑
l
=
1
|
L
|
‍
α
j
l
p
j
l
(
x
)
,
where α
j
l
:
=
P
(
j
)
β
j
l denotes the probability weight of the lth feature for the jth class.To obtain the optimal probability classifier based on the “linear combination assumption,” it is natural to consider the following optimization problem:(7)
min
⁡
α
∈
Θ
∑
j
∈
J
‍
∑
i
∈
I
‍
L
(
P
(
j
∣
x
i
)
,
y
i
,
j
)
,
where L
(
·
,
·
)
:
ℝ
×
ℝ
→
R
+ is a prespecified loss function. In the following context, we will take the absolute error function as our loss function; that is, L
(
x
,
y
)
=
|
x
-
y
|. In view of its probability property, it is straightforward to impose the following constraints on the posterior probability:
(8)
0
≤
f
(
j
∣
x
i
)
≤
1
,
∀
i
∈
I
,
j
∈
J
.
Under such constraints, we have that
(9)
∑
j
∈
J
‍
∑
i
∈
I
‍
L
(
f
(
j
∣
x
i
)
,
y
i
,
j
)
=
∑
j
∈
J
‍
∑
i
∈
I
‍
|
f
(
j
∣
x
i
)
-
y
i
,
j
|
=
∑
j
∈
J
‍
∑
i
∈
I
‍
{
y
i
,
j
(
1
-
f
(
j
∣
x
i
)
)
+
(
1
-
y
i
,
j
)
f
(
j
∣
x
i
)
}
=
∑
j
∈
J
‍
∑
i
∈
I
‍
(
1
-
2
y
i
,
j
)
f
(
j
∣
x
i
)
+
|
I
|
,
where |
I
|
=
∑
j
∈
J
‍
∑
i
∈
I
‍
y
i
,
j.Thus the optimal probability classifier (PC) problem can be formulated as follows:(10)
(
PC
)
min
⁡
∑
j
∈
J
‍
∑
i
∈
I
‍
(
1
-
2
y
i
,
j
)
∑
l
∈
L
‍
α
j
l
p
i
,
j
l
+
|
I
|
s
.
t
.
KK
0
≤
∑
l
∈
L
‍
α
j
l
p
i
,
j
l
≤
1
,
∀
i
∈
I
,
j
∈
J
.It is no doubt that the “linear combination assumption” may not work sometimes. However, we justify the proposed classifier by the following facts.(1)
As an intuitive interpretation, note thatp
j
l
(
x
) estimates the probability of the observation x belonging to the jth class only based on the lth feature; thus it provides partial probabilistic information of the sample. Hence we can interpret the weight α
j
l as certain degree of trust on the information, and in this sense, the “linear combination assumption” is a way of combining evidence from different sources. Similar ideas can also be found in the theory of evidence; see the Dempster-Shafer theory [24, 25].
(2)
In terms of the classification performance, in the worst case, the proposed classifier may put all weight on one feature; thus in such case, it is equivalent to a Bayes classifier based on a well-selected feature. If each class has its “typical” feature which can distinguish it from other classes, the proposed classifier has the ability to learn this property by putting different weights on different features for different classes and thus provides better classification performance. A real-life application on lithology classification problems also validates its classification performance by comparison with support vector machines and the naive Bayes classifier.
(3)
Another advantage of the proposed classifier is its high computability. As we show in Section3, the proposed classifier and its robust counterpart problems can be reformulated as second order cone programming problems and thus can be solved by interior algorithms in polynomial time.


## 2.2. Robust Probability Classifier

Due to observational noises, the true class-conditional probability distribution is often difficult to obtain. Instead we can construct a confidence distributional set which contains the true distribution. Unlike the traditional distributional sets in minimax probability machines, which only utilize mean and covariance matrix, we construct our class-conditional probability distributional set based on the modifiedχ
2-distance which uses more information from the samples.The modifiedχ
2-distance d
(
·
,
·
)
:
ℝ
m
×
ℝ
m
→
R is used to measure the distance between two discrete probability distribution vectors in statistics. For given p
=
(
p
1
,
…
,
p
m
)
T and q
=
(
q
1
,
…
,
q
m
)
T, it is defined as
(11)
d
(
q
,
p
)
=
∑
j
=
1
m
‍
(
q
j
-
p
j
)
2
p
j
.
Based on the modified χ
2-distance, we present the following class-conditional probability distributional set:
(12)
P
ϵ
=
{
q
i
,
j
l
:
∑
j
‍
q
i
,
j
l
=
1
,
q
i
,
j
l
≥
0
,
∑
j
∈
J
‍
(
q
i
,
j
l
-
p
i
,
j
l
)
2
p
i
,
j
l
≤
ϵ
,
KKKKK
∀
i
∈
I
,
l
∈
L
,
j
∈
J
∑
j
∈
J
‍
(
q
i
,
j
l
-
p
i
,
j
l
)
2
p
i
,
j
l
≤
ϵ
,
}
,
where p
i
,
j
l is the nominal class-conditional distribution probability for the ith sample belonging to the jth class based on the lth feature and the prespecified parameter ϵ is used to control the size of the set.To design a robust classifier, we need to consider the effect of data uncertainty on the objective function and constraints. The robust objective function is to minimize the worst-case loss function value over all the possible distributions in the distributional setP
ϵ; the robust constraints ensure that all the original constraints should also be satisfied for any distribution in P
ϵ. Thus the robust probability classifier problem is of the following form:
(13)
(
RPC
)
min
⁡
{
max
⁡
∑
j
∈
J
‍
∑
i
∈
I
‍
(
1
-
2
y
i
,
j
)
∑
l
∈
L
‍
α
j
l
q
i
,
j
l
KKKKiK
+
|
I
|
:
{
q
i
,
j
l
}
∈
P
ϵ
∑
j
∈
J
‍
}
s
.
t
.
KiK
0
≤
∑
l
∈
L
‍
α
j
l
q
i
,
j
l
≤
1
,
∀
{
q
i
,
j
l
}
∈
P
ϵ
∀
i
,
j
.Note that the above optimization problem has an infinite number of robust constraints and its objective function is also an embedded subproblem. We will show how to solve such minimax optimization problem in Section3.


## 2.3. Construct the Distributional Set

To get the distributional setP
ϵ, we need to define the parameter ϵ and the nominal probability p
i
,
j
l. The selection of parameter ϵ is application based and we will discuss this issue in the numerical experiment section; next we will provide a procedure to calculate p
i
,
j
l.For thelth feature, the following procedure takes an integer K
l indicating the number of data intervals as an input and will output the estimated probability p
i
,
j
l of the ith sample belonging to the jth class.(1)
Sort samples in the increased order and divide them intoK
l intervals such that each interval has at least ⌊
|
I
|
/
K
l
⌋ number of samples. Denote the kth interval by Δ
l
,
k.
(2)
Calculate the total number of samples in thej-class, N
j, the total number of samples in the kth interval, N
l
,
k, and the total number of samples belonging to the j-class in the kth interval, N
l
,
k
,
j.
(3)
For theith sample, if it falls into the kth interval, the class-conditional probability p
i
,
j
l is calculated by
(14)
p
i
,
j
l
=
Prob
(
i
∈
j
∣
x
i
,
l
∈
Δ
l
,
k
)
=
Prob
(
i
∈
j
,
x
i
,
l
∈
Δ
l
,
k
)
Prob
(
x
i
,
l
∈
Δ
l
,
k
)
=
Prob
(
i
∈
j
)
Prob
(
x
i
,
l
∈
Δ
l
,
k
∣
i
∈
j
)
∑
j
′
∈
J
‍
Prob
(
i
∈
j
′
)
Prob
(
x
i
,
l
∈
Δ
l
,
k
∣
i
∈
j
′
)
=
(
N
j
/
|
I
|
)
·
(
N
l
,
k
,
j
/
N
j
)
∑
j
′
∈
J
‍
(
N
j
′
/
|
I
|
)
·
(
N
l
,
k
,
j
′
/
N
j
′
)
=
N
l
,
k
,
j
N
l
,
k
.Note that from the definition of P
ϵ, we easily compute the upper bound q
¯
i
,
j
l and lower bound q
_
i
,
j
l for the true class-conditional probability q
i
,
j
l as follows:
(15)
q
¯
i
,
j
l
=
max
⁡
{
∑
s
∈
J
‍
(
q
i
,
s
l
-
p
i
,
s
l
)
2
p
i
,
s
l
q
i
,
j
l
:
∑
s
‍
q
i
,
s
l
=
1
,
KKKKKKKiK
∑
s
∈
J
‍
(
q
i
,
s
l
-
p
i
,
s
l
)
2
p
i
,
s
l
≤
ϵ
,
q
i
,
s
l
≥
0
,
∀
s
∈
J
}
,
(16)
q
_
i
,
j
l
=
min
⁡
{
∑
s
∈
J
‍
(
q
i
,
s
l
-
p
i
,
s
l
)
2
p
i
,
s
l
q
i
,
j
l
:
∑
s
‍
q
i
,
s
l
=
1
,
KKKKKKKii
∑
s
∈
J
‍
(
q
i
,
s
l
-
p
i
,
s
l
)
2
p
i
,
s
l
≤
ϵ
,
q
i
,
s
l
≥
0
,
∀
s
∈
J
}
.
The above problems can be efficiently solved by a second order cone solver such as SeDuMi [26] or SDPT3 [27].


## 3. Solution Methods for RPC

In this section, we first reduce the infinite number of robust constraints to a finite set of linear constraints and then transform the inner robust objective function into a minimization problem by the conic duality theorem. At last, we obtain an equivalent computable second order cone programming for the RPC problem. The following analysis is based on the strong duality result in [8].Consider a conic program of the following form:(17)
(
CP
)
min
⁡
c
T
x
s
.
t
.
KK
A
i
x
-
b
i
∈
C
i
,
∀
i
=
1
,
…
,
m
,
KKiiK
A
x
=
b
,
and its dual problem
(18)
(
DP
)
max
⁡
b
T
z
+
∑
i
=
1
m
‍
b
i
T
y
i
s
.
t
.
KK
A
*
z
+
∑
i
=
1
m
‍
A
i
*
y
i
=
c
,
KKKK
y
i
∈
C
i
*
,
∀
i
=
1
,
…
,
m
,
where C
i is a cone in ℝ
n
i and C
i
* is its dual cone defined by
(19)
C
i
*
=
{
y
∈
ℝ
n
i
:
y
T
x
≥
,
∀
x
∈
C
i
}
.
A conic program is called strictly feasible if it admits a feasible solution x
¯ such that A
i
x
-
b
i
∈
int
⁡
C
i,  ∀
i
=
1
,
…
,
m, where int
⁡
C
i denotes the interior point set of C
i.Lemma 1 (see [8]).
If one of the problems (CP) and (DP) is strictly feasible and bounded, then the other problem is solvable, and (CP) = (DP) in the sense that both have the same optimal objective function value.


### 3.1. Robust Constraints

The following lemma provides an equivalent characterization for the infinite number of robust constraints in terms of a finite set of linear constraints which can be solved efficiently.Lemma 2.
For giveni
,
j, the robust constraint
(20)
0
≤
∑
l
∈
L
‍
α
j
l
p
i
,
j
l
≤
1
,
∀
{
q
i
,
j
l
}
∈
P
ϵ
is equal to the following constraints:
(21)
∑
l
∈
L
‍
(
q
_
i
,
j
l
u
i
,
j
l
,
0
-
q
¯
i
,
j
l
v
i
,
j
l
,
0
)
≥
0
,
α
i
,
j
l
-
u
i
,
j
l
,
0
+
v
i
,
j
l
,
0
≥
0
,
u
i
,
j
l
,
0
,
v
i
,
j
l
,
0
≥
0
,
∀
l
∈
L
,
1
+
∑
l
∈
L
‍
(
q
_
i
,
j
l
u
i
,
j
l
,
1
-
q
¯
i
,
j
l
v
i
,
j
l
,
1
)
≥
0
,
v
i
,
j
l
,
1
-
α
i
,
j
l
-
u
i
,
j
l
,
1
≥
0
,
u
i
,
j
l
,
1
,
v
i
,
j
l
,
1
≥
0
,
∀
l
∈
L
.Proof.
First note that the distributional setP
ϵ
,
i can be represented as the Cartesian product of a series of projected subsets
(22)
P
ϵ
=
∏
i
∈
I
‍
P
ϵ
,
i
,
where the projected subset on index i is defined by
(23)
P
ϵ
,
i
=
{
q
i
,
j
l
:
∑
j
‍
q
i
,
j
l
=
1
,
q
i
,
j
l
≥
0
,
K
∑
j
∈
J
‍
(
q
i
,
j
l
-
p
i
,
j
l
)
2
p
i
,
j
l
≤
ϵ
,
∀
l
∈
L
,
j
∈
J
}
.
Then for giveni
,
j, since the robust constraint is only associated with variables q
i
,
j
l
,
l
∈
L, we can further split the projected subset P
ϵ
,
i into |
J
| subsets
(24)
P
ϵ
,
i
=
∏
j
∈
J
‍
P
ϵ
,
i
,
j
=
∏
j
∈
J
‍
{
q
i
,
j
l
:
q
_
i
,
j
l
≤
q
i
,
j
l
≤
q
¯
i
,
j
l
,
∀
l
∈
L
}
,
where q
¯
i
,
j
l and q
_
i
,
j
l are computed by (15) and (16), respectively.
For constraint∑
l
∈
L
‍
α
j
l
p
i
,
j
l
≥
0
,
∀
{
q
i
,
j
l
}
∈
P
ϵ, it is equal to the following constraint:
(25)
∑
l
∈
L
‍
α
j
l
p
i
,
j
l
≥
0
,
∀
{
q
i
,
j
l
}
∈
P
ϵ
,
i
⟺
∑
l
∈
L
‍
α
j
l
p
i
,
j
l
≥
0
,
∀
{
q
i
,
j
l
}
∈
P
ϵ
,
i
,
j
⟺
min
⁡
{
∑
l
∈
L
‍
α
j
l
p
i
,
j
l
:
q
_
i
,
j
l
≤
q
i
,
j
l
≤
q
¯
i
,
j
l
,
∀
l
∈
L
}
≥
0
⟺
max
⁡
{
∑
l
∈
L
‍
(
q
_
i
,
j
l
u
i
,
j
l
,
0
-
q
¯
i
,
j
l
v
i
,
j
l
,
0
)
:
KKKKKiiK
α
i
,
j
l
-
u
i
,
j
l
,
0
+
v
i
,
j
l
,
0
≥
0
,
u
i
,
j
l
,
0
,
v
i
,
j
l
,
0
≥
0
,
∀
l
∈
L
∑
l
∈
L
‍
(
q
_
i
,
j
l
u
i
,
j
l
,
0
-
q
¯
i
,
j
l
v
i
,
j
l
,
0
)
}
≥
0
⟺
∑
l
∈
L
‍
(
q
_
i
,
j
l
u
i
,
j
l
,
0
-
q
¯
i
,
j
l
v
i
,
j
l
,
0
)
≥
0
,
KKK
α
i
,
j
l
-
u
i
,
j
l
,
0
+
v
i
,
j
l
,
0
≥
0
,
u
i
,
j
l
,
0
,
v
i
,
j
l
,
0
≥
0
,
∀
l
∈
L
,
where the last equivalence comes from the strong duality between these two linear programs.
For the constraint∑
l
∈
L
‍
α
j
l
p
i
,
j
l
≤
1
,
∀
{
q
i
,
j
l
}
∈
P
ϵ, the same technique applies; thus we complete the proof.


### 3.2. Robust Objective Function

In the RPC problem, the robust objective function is defined by an inner maximization problem. The following proposition shows that it can be transformed into a minimization problem over second order cones. To prove the following result, we utilize the concept of conjugate functiond
* of the modified χ
2-distance:
(26)
d
*
(
s
)
=
sup
⁡
t
≥
0
{
s
t
-
d
(
t
)
}
=
[
s
+
2
]
+
2
4
-
1
,
where the function  [
·
]
+ is defined as [
x
]
+
=
x if x
≥
0; otherwise [
x
]
+
=
0. For more details about conjugate functions, see [28].Proposition 3.
The following inner maximization problem(27)
max
⁡
∑
j
∈
J
‍
∑
i
∈
I
‍
(
1
-
2
y
i
,
j
)
∑
l
∈
L
‍
α
j
l
q
i
,
j
l
+
|
I
|
:
{
q
i
,
j
l
}
∈
P
ϵ
is equivalent to a second order cone programming
(28)
min
⁡
∑
i
∈
I
‍
∑
l
∈
L
‍
(
ϵ
λ
i
l
-
θ
i
l
)
+
∑
i
∈
I
‍
∑
l
∈
L
‍
∑
j
∈
J
‍
p
i
,
j
l
w
i
,
j
l
+
|
I
|
s
.
t
.
KK
(
w
i
,
j
l
z
i
,
j
l
2
λ
i
l
+
w
i
,
j
l
)
∈
L
3
,
∀
i
∈
I
,
j
∈
J
,
l
∈
L
,
K
K
K
K
K
u
i
,
j
l
=
α
j
l
(
1
-
2
I
i
,
j
)
+
θ
i
l
,
∀
i
∈
I
,
l
∈
L
,
j
∈
J
.
K
K
K
K
K
z
i
,
j
l

≥

r
i
,
j
l

+

2
λ
i
l
,
λ
i
,
j
l
,
z
i
,
j
l

≥

0
∀
i
∈
I
,
j
∈
J
,
l
∈
L
,
where a second order cone L
n
+
1 is defined as
(29)
L
n
+
1
=
{
x
∈
ℝ
n
+
1
:
x
n
+
1
≥
∑
i
=
1
n
‍
x
i
2
}
.Proof.
For given feasibleα satisfying the robust constraints, it is straightforward to show that the inner maximum problem is equal to the following minimization problem (MP):
(30)
(
MP
)
min
⁡
t
s
.
t
.
KiiK
t
≥
∑
j
∈
J
‍
∑
i
∈
I
‍
{
(
1
-
2
y
i
,
j
)
∑
l
∈
L
‍
α
j
l
q
i
,
j
l
}
+
|
I
|
,
KKKKKKKKKiKKKKKKKKKK
∀
{
q
i
,
j
l
}
∈
P
ϵ
.
The above constraint can be further reduced to the following constraint:
(31)
max
⁡
{
∑
j
∈
J
‍
∑
i
∈
I
‍
{
(
1
-
2
y
i
,
j
)
∑
l
∈
L
‍
α
j
l
q
i
,
j
l
}
+
|
I
|
-
t
:
∀
{
q
i
,
j
l
}
∈
P
ϵ
∑
i
∈
I
‍
{
(
1
-
2
y
i
,
j
)
∑
l
∈
L
‍
α
j
l
q
i
,
j
l
}
}
≤
0
.
By assigning Lagrange multipliersθ
i
l
∈
ℝ and λ
i
l
∈
ℝ
+ to the constraints in the left optimization problem, we obtain the following Lagrange function:
(32)
L
(
q
,
θ
,
λ
)
=
∑
i
∈
I
‍
∑
l
∈
L
‍
(
ϵ
λ
i
l
-
θ
i
l
)
+
∑
i
∈
I
‍
∑
l
∈
L
‍
∑
j
∈
J
‍
(
r
i
,
j
l
q
i
,
j
l
-
λ
i
l
(
q
i
,
j
l
-
p
i
,
j
l
)
2
p
i
,
j
l
)
+
|
I
|
-
t
,
where r
i
,
j
l
=
α
j
l
(
1
-
2
y
i
,
j
)
+
θ
i
l. Its dual function is given as
(33)
D
(
θ
,
λ
)
=
max
⁡
q
≥
0
L
(
t
,
q
,
θ
,
λ
)
=
∑
i
∈
I
‍
∑
l
∈
L
‍
(
ϵ
λ
i
l
-
θ
i
l
)
+
∑
i
∈
I
‍
∑
l
∈
L
‍
∑
j
∈
J
‍
max
⁡
q
i
,
j
l
≥
0
(
r
i
,
j
l
q
i
,
j
l
-
λ
i
l
p
i
,
j
l
(
q
i
,
j
l
-
p
i
,
j
l
p
i
,
j
l
)
2
)
+
|
I
|
-
t
,
=
∑
i
∈
I
‍
∑
l
∈
L
‍
(
ϵ
λ
i
l
-
θ
i
l
)
+
∑
i
∈
I
‍
∑
l
∈
L
‍
∑
j
∈
J
‍
p
i
,
j
l
max
⁡
t
≥
0
(
r
i
,
j
l
t
-
λ
i
l
(
t
-
1
)
2
)
+
|
I
|
-
t
,
=
∑
i
∈
I
‍
∑
l
∈
L
‍
(
ϵ
λ
i
l
-
θ
i
l
)
+
∑
i
∈
I
‍
∑
l
∈
L
‍
∑
j
∈
J
‍
p
i
,
j
l
λ
i
l
max
⁡
t
≥
0
(
r
i
,
j
l
λ
i
l
t
-
(
t
-
1
)
2
)
+
|
I
|
-
t
,
=
∑
i
∈
I
‍
∑
l
∈
L
‍
(
ϵ
λ
i
l
-
θ
i
l
)
+
∑
i
∈
I
‍
∑
l
∈
L
‍
∑
j
∈
J
‍
p
i
,
j
l
λ
i
l
d
*
(
r
i
,
j
l
λ
i
l
)
+
|
I
|
-
t
.
Note that, for any feasible α, the primal maximization problem (31) is bounded and has a strictly feasible solution {
p
i
,
j
l
}; thus there is no duality gap between (31) and the following dual problem:
(34)
min
⁡
{
D
(
θ
,
λ
)
:
θ
i
l
∈
ℝ
,
λ
i
l
∈
ℝ
+
,
∀
i
∈
I
,
l
∈
L
}
⟺
{
min
⁡
∑
i
∈
I
‍
∑
l
∈
L
‍
(
ϵ
λ
i
l
-
θ
i
l
)
+
∑
i
∈
I
‍
∑
l
∈
L
‍
∑
j
∈
J
‍
p
i
,
j
l
w
i
,
j
l
+
|
I
|
-
t
s.t.
w
i
,
j
l

≥

λ
i
l
d
*
(
r
i
,
j
l
λ
i
l
)
,
∀
i

∈

I
,
l

∈

L
,
j

∈

J
,
θ
i
l
∈
ℝ
,
λ
i
l
∈
ℝ
+
,
∀
i
∈
I
,
l
∈
L
}
.
Next we show that the constraint about the conjugate function can be represented by second order cone constraints:
(35)
λ
i
l
d
*
(
r
i
,
j
l
λ
i
l
)
≤
w
i
,
j
l
⟺
λ
i
l
(
-
1
+
1
4
[
r
i
,
j
l
λ
i
l
+
2
]
+
2
)
≤
w
i
,
j
l
⟺
4
λ
i
l
(
λ
i
l
+
w
i
,
j
l
)
≥
[
r
i
,
j
l
+
2
λ
i
l
]
+
2
⟺
4
λ
i
l
(
λ
i
l
+
w
i
,
j
l
)
≥
(
z
i
,
j
l
)
2
,
KiK
z
i
,
j
l
≥
0
,
z
i
,
j
l
≥
r
i
,
j
l
+
2
λ
i
l
,
⟺
(
w
i
,
j
l
z
i
,
j
l
2
λ
i
l
+
w
i
,
j
l
)
∈
L
3
,
iiiii
z
i
,
j
l
≥
0
,
z
i
,
j
l
≥
r
i
,
j
l
+
2
λ
i
l
.
By reinjecting the above constraints into (MP), the robust objective function is equivalent to the following problem:
(36)
min
⁡
t
s
.
t
.
KK
∑
i
∈
I
‍
∑
l
∈
L
‍
(
ϵ
λ
i
l
-
θ
i
l
)
+
∑
i
∈
I
‍
∑
l
∈
L
‍
∑
j
∈
J
‍
p
i
,
j
l
w
i
,
j
l
+
|
I
|
≤
t
,
s
.
t
.
KK
(
w
i
,
j
l
z
i
,
j
l
2
λ
i
l
+
w
i
,
j
l
)
∈
L
3
,
s
.
t
.
KK
z
i
,
j
l

≥

r
i
,
j
l

+

2
λ
i
l
,
z
i
,
j
l
,
λ
i
,
j
l

≥

0
,
∀
i
∈
I
,
j
∈
J
,
l
∈
L
,
s
.
t
.
KK
u
i
,
j
l
=
α
j
l
(
1
-
2
I
i
,
j
)
+
θ
i
l
,
∀
i
∈
I
,
l
∈
L
,
j
∈
J
.
By eliminating variable t, we complete the proof.Based on the Lemma2 and Proposition 3, we obtain our main result.Proposition 4.
The RPC problem can be solved as the following second order cone programming:(37)
min
⁡
∑
i
∈
I
‍
∑
l
∈
L
‍
(
ϵ
λ
i
l
-
θ
i
l
)
+
∑
i
∈
I
‍
∑
l
∈
L
‍
∑
j
∈
J
‍
p
i
,
j
l
w
i
,
j
l
+
|
I
|
s
.
t
.
KKk
(
w
i
,
j
l
z
i
,
j
l
2
λ
i
l
+
w
i
,
j
l
)
∈
L
3
,
∀
i
∈
I
,
j
∈
J
,
l
∈
L
,
K
K
K
K
r
i
,
j
l
=
α
j
l
(
1
-
2
I
i
,
j
)
+
θ
i
l
,
∀
i
∈
I
,
j
∈
J
,
l
∈
L
,
K
K
K
K
z
i
,
j
l
≥
r
i
,
j
l
+
2
λ
i
l
,
∀
i
∈
I
,
j
∈
J
,
l
∈
L
,
K
K
K
K
∑
l
∈
L
‍
(
q
_
i
,
j
l
u
i
,
j
l
,
0
-
q
¯
i
,
j
l
v
i
,
j
l
,
0
)
≥
0
,
∀
i
∈
I
,
j
∈
J
,
KKKK
1
+
∑
l
∈
L
‍
(
q
_
i
,
j
l
u
i
,
j
l
,
1
-
q
¯
i
,
j
l
v
i
,
j
l
,
1
)
≥
0
,
∀
i
∈
I
,
j
∈
J
,
K
K
K
K
α
i
,
j
l
-
u
i
,
j
l
,
0
+
v
i
,
j
l
,
0
≥
0
,
∀
i
∈
I
,
j
∈
J
,
l
∈
L
,
K
K
K
K
v
i
,
j
l
,
1
-
α
i
,
j
l
-
u
i
,
j
l
,
1
≥
0
,
∀
i
∈
I
,
j
∈
J
,
l
∈
L
,
K
K
K
K
λ
i
,
j
l
,
z
i
,
j
l
,
u
i
,
j
l
,
1
,
v
i
,
j
l
,
1
,
u
i
,
j
l
,
0
,
v
i
,
j
l
,
0
≥
0
,
∀
i
∈
I
,
j
∈
J
,
l
∈
L
,
K
K
K
K
r
i
,
j
l
,
θ
i
,
j
l
,
w
i
,
j
l
,
α
i
,
j
l
∈
ℝ
,
∀
i
∈
I
,
j
∈
J
,
l
∈
L
.


## 3.1. Robust Constraints

The following lemma provides an equivalent characterization for the infinite number of robust constraints in terms of a finite set of linear constraints which can be solved efficiently.Lemma 2.
For giveni
,
j, the robust constraint
(20)
0
≤
∑
l
∈
L
‍
α
j
l
p
i
,
j
l
≤
1
,
∀
{
q
i
,
j
l
}
∈
P
ϵ
is equal to the following constraints:
(21)
∑
l
∈
L
‍
(
q
_
i
,
j
l
u
i
,
j
l
,
0
-
q
¯
i
,
j
l
v
i
,
j
l
,
0
)
≥
0
,
α
i
,
j
l
-
u
i
,
j
l
,
0
+
v
i
,
j
l
,
0
≥
0
,
u
i
,
j
l
,
0
,
v
i
,
j
l
,
0
≥
0
,
∀
l
∈
L
,
1
+
∑
l
∈
L
‍
(
q
_
i
,
j
l
u
i
,
j
l
,
1
-
q
¯
i
,
j
l
v
i
,
j
l
,
1
)
≥
0
,
v
i
,
j
l
,
1
-
α
i
,
j
l
-
u
i
,
j
l
,
1
≥
0
,
u
i
,
j
l
,
1
,
v
i
,
j
l
,
1
≥
0
,
∀
l
∈
L
.Proof.
First note that the distributional setP
ϵ
,
i can be represented as the Cartesian product of a series of projected subsets
(22)
P
ϵ
=
∏
i
∈
I
‍
P
ϵ
,
i
,
where the projected subset on index i is defined by
(23)
P
ϵ
,
i
=
{
q
i
,
j
l
:
∑
j
‍
q
i
,
j
l
=
1
,
q
i
,
j
l
≥
0
,
K
∑
j
∈
J
‍
(
q
i
,
j
l
-
p
i
,
j
l
)
2
p
i
,
j
l
≤
ϵ
,
∀
l
∈
L
,
j
∈
J
}
.
Then for giveni
,
j, since the robust constraint is only associated with variables q
i
,
j
l
,
l
∈
L, we can further split the projected subset P
ϵ
,
i into |
J
| subsets
(24)
P
ϵ
,
i
=
∏
j
∈
J
‍
P
ϵ
,
i
,
j
=
∏
j
∈
J
‍
{
q
i
,
j
l
:
q
_
i
,
j
l
≤
q
i
,
j
l
≤
q
¯
i
,
j
l
,
∀
l
∈
L
}
,
where q
¯
i
,
j
l and q
_
i
,
j
l are computed by (15) and (16), respectively.
For constraint∑
l
∈
L
‍
α
j
l
p
i
,
j
l
≥
0
,
∀
{
q
i
,
j
l
}
∈
P
ϵ, it is equal to the following constraint:
(25)
∑
l
∈
L
‍
α
j
l
p
i
,
j
l
≥
0
,
∀
{
q
i
,
j
l
}
∈
P
ϵ
,
i
⟺
∑
l
∈
L
‍
α
j
l
p
i
,
j
l
≥
0
,
∀
{
q
i
,
j
l
}
∈
P
ϵ
,
i
,
j
⟺
min
⁡
{
∑
l
∈
L
‍
α
j
l
p
i
,
j
l
:
q
_
i
,
j
l
≤
q
i
,
j
l
≤
q
¯
i
,
j
l
,
∀
l
∈
L
}
≥
0
⟺
max
⁡
{
∑
l
∈
L
‍
(
q
_
i
,
j
l
u
i
,
j
l
,
0
-
q
¯
i
,
j
l
v
i
,
j
l
,
0
)
:
KKKKKiiK
α
i
,
j
l
-
u
i
,
j
l
,
0
+
v
i
,
j
l
,
0
≥
0
,
u
i
,
j
l
,
0
,
v
i
,
j
l
,
0
≥
0
,
∀
l
∈
L
∑
l
∈
L
‍
(
q
_
i
,
j
l
u
i
,
j
l
,
0
-
q
¯
i
,
j
l
v
i
,
j
l
,
0
)
}
≥
0
⟺
∑
l
∈
L
‍
(
q
_
i
,
j
l
u
i
,
j
l
,
0
-
q
¯
i
,
j
l
v
i
,
j
l
,
0
)
≥
0
,
KKK
α
i
,
j
l
-
u
i
,
j
l
,
0
+
v
i
,
j
l
,
0
≥
0
,
u
i
,
j
l
,
0
,
v
i
,
j
l
,
0
≥
0
,
∀
l
∈
L
,
where the last equivalence comes from the strong duality between these two linear programs.
For the constraint∑
l
∈
L
‍
α
j
l
p
i
,
j
l
≤
1
,
∀
{
q
i
,
j
l
}
∈
P
ϵ, the same technique applies; thus we complete the proof.


## 3.2. Robust Objective Function

In the RPC problem, the robust objective function is defined by an inner maximization problem. The following proposition shows that it can be transformed into a minimization problem over second order cones. To prove the following result, we utilize the concept of conjugate functiond
* of the modified χ
2-distance:
(26)
d
*
(
s
)
=
sup
⁡
t
≥
0
{
s
t
-
d
(
t
)
}
=
[
s
+
2
]
+
2
4
-
1
,
where the function  [
·
]
+ is defined as [
x
]
+
=
x if x
≥
0; otherwise [
x
]
+
=
0. For more details about conjugate functions, see [28].Proposition 3.
The following inner maximization problem(27)
max
⁡
∑
j
∈
J
‍
∑
i
∈
I
‍
(
1
-
2
y
i
,
j
)
∑
l
∈
L
‍
α
j
l
q
i
,
j
l
+
|
I
|
:
{
q
i
,
j
l
}
∈
P
ϵ
is equivalent to a second order cone programming
(28)
min
⁡
∑
i
∈
I
‍
∑
l
∈
L
‍
(
ϵ
λ
i
l
-
θ
i
l
)
+
∑
i
∈
I
‍
∑
l
∈
L
‍
∑
j
∈
J
‍
p
i
,
j
l
w
i
,
j
l
+
|
I
|
s
.
t
.
KK
(
w
i
,
j
l
z
i
,
j
l
2
λ
i
l
+
w
i
,
j
l
)
∈
L
3
,
∀
i
∈
I
,
j
∈
J
,
l
∈
L
,
K
K
K
K
K
u
i
,
j
l
=
α
j
l
(
1
-
2
I
i
,
j
)
+
θ
i
l
,
∀
i
∈
I
,
l
∈
L
,
j
∈
J
.
K
K
K
K
K
z
i
,
j
l

≥

r
i
,
j
l

+

2
λ
i
l
,
λ
i
,
j
l
,
z
i
,
j
l

≥

0
∀
i
∈
I
,
j
∈
J
,
l
∈
L
,
where a second order cone L
n
+
1 is defined as
(29)
L
n
+
1
=
{
x
∈
ℝ
n
+
1
:
x
n
+
1
≥
∑
i
=
1
n
‍
x
i
2
}
.Proof.
For given feasibleα satisfying the robust constraints, it is straightforward to show that the inner maximum problem is equal to the following minimization problem (MP):
(30)
(
MP
)
min
⁡
t
s
.
t
.
KiiK
t
≥
∑
j
∈
J
‍
∑
i
∈
I
‍
{
(
1
-
2
y
i
,
j
)
∑
l
∈
L
‍
α
j
l
q
i
,
j
l
}
+
|
I
|
,
KKKKKKKKKiKKKKKKKKKK
∀
{
q
i
,
j
l
}
∈
P
ϵ
.
The above constraint can be further reduced to the following constraint:
(31)
max
⁡
{
∑
j
∈
J
‍
∑
i
∈
I
‍
{
(
1
-
2
y
i
,
j
)
∑
l
∈
L
‍
α
j
l
q
i
,
j
l
}
+
|
I
|
-
t
:
∀
{
q
i
,
j
l
}
∈
P
ϵ
∑
i
∈
I
‍
{
(
1
-
2
y
i
,
j
)
∑
l
∈
L
‍
α
j
l
q
i
,
j
l
}
}
≤
0
.
By assigning Lagrange multipliersθ
i
l
∈
ℝ and λ
i
l
∈
ℝ
+ to the constraints in the left optimization problem, we obtain the following Lagrange function:
(32)
L
(
q
,
θ
,
λ
)
=
∑
i
∈
I
‍
∑
l
∈
L
‍
(
ϵ
λ
i
l
-
θ
i
l
)
+
∑
i
∈
I
‍
∑
l
∈
L
‍
∑
j
∈
J
‍
(
r
i
,
j
l
q
i
,
j
l
-
λ
i
l
(
q
i
,
j
l
-
p
i
,
j
l
)
2
p
i
,
j
l
)
+
|
I
|
-
t
,
where r
i
,
j
l
=
α
j
l
(
1
-
2
y
i
,
j
)
+
θ
i
l. Its dual function is given as
(33)
D
(
θ
,
λ
)
=
max
⁡
q
≥
0
L
(
t
,
q
,
θ
,
λ
)
=
∑
i
∈
I
‍
∑
l
∈
L
‍
(
ϵ
λ
i
l
-
θ
i
l
)
+
∑
i
∈
I
‍
∑
l
∈
L
‍
∑
j
∈
J
‍
max
⁡
q
i
,
j
l
≥
0
(
r
i
,
j
l
q
i
,
j
l
-
λ
i
l
p
i
,
j
l
(
q
i
,
j
l
-
p
i
,
j
l
p
i
,
j
l
)
2
)
+
|
I
|
-
t
,
=
∑
i
∈
I
‍
∑
l
∈
L
‍
(
ϵ
λ
i
l
-
θ
i
l
)
+
∑
i
∈
I
‍
∑
l
∈
L
‍
∑
j
∈
J
‍
p
i
,
j
l
max
⁡
t
≥
0
(
r
i
,
j
l
t
-
λ
i
l
(
t
-
1
)
2
)
+
|
I
|
-
t
,
=
∑
i
∈
I
‍
∑
l
∈
L
‍
(
ϵ
λ
i
l
-
θ
i
l
)
+
∑
i
∈
I
‍
∑
l
∈
L
‍
∑
j
∈
J
‍
p
i
,
j
l
λ
i
l
max
⁡
t
≥
0
(
r
i
,
j
l
λ
i
l
t
-
(
t
-
1
)
2
)
+
|
I
|
-
t
,
=
∑
i
∈
I
‍
∑
l
∈
L
‍
(
ϵ
λ
i
l
-
θ
i
l
)
+
∑
i
∈
I
‍
∑
l
∈
L
‍
∑
j
∈
J
‍
p
i
,
j
l
λ
i
l
d
*
(
r
i
,
j
l
λ
i
l
)
+
|
I
|
-
t
.
Note that, for any feasible α, the primal maximization problem (31) is bounded and has a strictly feasible solution {
p
i
,
j
l
}; thus there is no duality gap between (31) and the following dual problem:
(34)
min
⁡
{
D
(
θ
,
λ
)
:
θ
i
l
∈
ℝ
,
λ
i
l
∈
ℝ
+
,
∀
i
∈
I
,
l
∈
L
}
⟺
{
min
⁡
∑
i
∈
I
‍
∑
l
∈
L
‍
(
ϵ
λ
i
l
-
θ
i
l
)
+
∑
i
∈
I
‍
∑
l
∈
L
‍
∑
j
∈
J
‍
p
i
,
j
l
w
i
,
j
l
+
|
I
|
-
t
s.t.
w
i
,
j
l

≥

λ
i
l
d
*
(
r
i
,
j
l
λ
i
l
)
,
∀
i

∈

I
,
l

∈

L
,
j

∈

J
,
θ
i
l
∈
ℝ
,
λ
i
l
∈
ℝ
+
,
∀
i
∈
I
,
l
∈
L
}
.
Next we show that the constraint about the conjugate function can be represented by second order cone constraints:
(35)
λ
i
l
d
*
(
r
i
,
j
l
λ
i
l
)
≤
w
i
,
j
l
⟺
λ
i
l
(
-
1
+
1
4
[
r
i
,
j
l
λ
i
l
+
2
]
+
2
)
≤
w
i
,
j
l
⟺
4
λ
i
l
(
λ
i
l
+
w
i
,
j
l
)
≥
[
r
i
,
j
l
+
2
λ
i
l
]
+
2
⟺
4
λ
i
l
(
λ
i
l
+
w
i
,
j
l
)
≥
(
z
i
,
j
l
)
2
,
KiK
z
i
,
j
l
≥
0
,
z
i
,
j
l
≥
r
i
,
j
l
+
2
λ
i
l
,
⟺
(
w
i
,
j
l
z
i
,
j
l
2
λ
i
l
+
w
i
,
j
l
)
∈
L
3
,
iiiii
z
i
,
j
l
≥
0
,
z
i
,
j
l
≥
r
i
,
j
l
+
2
λ
i
l
.
By reinjecting the above constraints into (MP), the robust objective function is equivalent to the following problem:
(36)
min
⁡
t
s
.
t
.
KK
∑
i
∈
I
‍
∑
l
∈
L
‍
(
ϵ
λ
i
l
-
θ
i
l
)
+
∑
i
∈
I
‍
∑
l
∈
L
‍
∑
j
∈
J
‍
p
i
,
j
l
w
i
,
j
l
+
|
I
|
≤
t
,
s
.
t
.
KK
(
w
i
,
j
l
z
i
,
j
l
2
λ
i
l
+
w
i
,
j
l
)
∈
L
3
,
s
.
t
.
KK
z
i
,
j
l

≥

r
i
,
j
l

+

2
λ
i
l
,
z
i
,
j
l
,
λ
i
,
j
l

≥

0
,
∀
i
∈
I
,
j
∈
J
,
l
∈
L
,
s
.
t
.
KK
u
i
,
j
l
=
α
j
l
(
1
-
2
I
i
,
j
)
+
θ
i
l
,
∀
i
∈
I
,
l
∈
L
,
j
∈
J
.
By eliminating variable t, we complete the proof.Based on the Lemma2 and Proposition 3, we obtain our main result.Proposition 4.
The RPC problem can be solved as the following second order cone programming:(37)
min
⁡
∑
i
∈
I
‍
∑
l
∈
L
‍
(
ϵ
λ
i
l
-
θ
i
l
)
+
∑
i
∈
I
‍
∑
l
∈
L
‍
∑
j
∈
J
‍
p
i
,
j
l
w
i
,
j
l
+
|
I
|
s
.
t
.
KKk
(
w
i
,
j
l
z
i
,
j
l
2
λ
i
l
+
w
i
,
j
l
)
∈
L
3
,
∀
i
∈
I
,
j
∈
J
,
l
∈
L
,
K
K
K
K
r
i
,
j
l
=
α
j
l
(
1
-
2
I
i
,
j
)
+
θ
i
l
,
∀
i
∈
I
,
j
∈
J
,
l
∈
L
,
K
K
K
K
z
i
,
j
l
≥
r
i
,
j
l
+
2
λ
i
l
,
∀
i
∈
I
,
j
∈
J
,
l
∈
L
,
K
K
K
K
∑
l
∈
L
‍
(
q
_
i
,
j
l
u
i
,
j
l
,
0
-
q
¯
i
,
j
l
v
i
,
j
l
,
0
)
≥
0
,
∀
i
∈
I
,
j
∈
J
,
KKKK
1
+
∑
l
∈
L
‍
(
q
_
i
,
j
l
u
i
,
j
l
,
1
-
q
¯
i
,
j
l
v
i
,
j
l
,
1
)
≥
0
,
∀
i
∈
I
,
j
∈
J
,
K
K
K
K
α
i
,
j
l
-
u
i
,
j
l
,
0
+
v
i
,
j
l
,
0
≥
0
,
∀
i
∈
I
,
j
∈
J
,
l
∈
L
,
K
K
K
K
v
i
,
j
l
,
1
-
α
i
,
j
l
-
u
i
,
j
l
,
1
≥
0
,
∀
i
∈
I
,
j
∈
J
,
l
∈
L
,
K
K
K
K
λ
i
,
j
l
,
z
i
,
j
l
,
u
i
,
j
l
,
1
,
v
i
,
j
l
,
1
,
u
i
,
j
l
,
0
,
v
i
,
j
l
,
0
≥
0
,
∀
i
∈
I
,
j
∈
J
,
l
∈
L
,
K
K
K
K
r
i
,
j
l
,
θ
i
,
j
l
,
w
i
,
j
l
,
α
i
,
j
l
∈
ℝ
,
∀
i
∈
I
,
j
∈
J
,
l
∈
L
.


## 4. Numerical Experiments on Real-World Applications

In this section, numerical experiments on real-world applications are carried out to verify the effectiveness of the proposed robust probability classifier model. Specifically we consider lithology classification data sets from our practical application. We compare our model with the regularized SVM (RSVM) and the naive Bayes classifier (NBC) on both binary and multiple classification problems.All the numerical experiments are implemented in Matlab 7.7.0 and run on Intel(R) Core(TM) i5-4570 CPU. SDPT3 solver [27] is called to solve the second order cone programs in our proposed method and the regularized SVM.


### 4.1. Data Sets

Lithology classification is one of the basic tasks for geological investigation. To discriminate the lithology of the underground strata, various electromagnetic techniques are applied to the same strata to obtain different features, such as Gamma coefficients, acoustic wave, striation, density, and fusibility.Here numerical experiments are carried out on a series of data sets: the borehole T1, Y4, Y5, and Y6. All boreholes are located in Tarim Basin, China. In total, there are 12 data sets used for binary classification problems and 8 data sets used for multiple classification problems. For each data set, based on a prespecified training rateγ
∈
[
0,1
], it is randomly partitioned into two subsets: a training set and a test set, such that the size of training set accounts for γ of the total number of samples.


### 4.2. Experiment Design

The parameters in our models are chosen based on the size of data set. The parameterϵ depends on the number of the classes and defined as ϵ
=
δ
2
/
|
J
|, where δ
∈
(
0,1
). The choice of ϵ can be explained in this way: if there are |
J
| classes and the training data are uniformly distributed, then, for each probability p
i
,
j
l
=
1
/
|
J
|, its maximal variation range is between p
i
,
j
l
(
1
-
δ
) and p
i
,
j
l
(
1
+
δ
). The number of data intervals K
l is defined as K
l
=
|
I
|
/
(
|
J
|
×
K
) such that if the training data are uniformly distributed, then in each data interval there are K samples in each class. In the following context, we set δ
=
0.2 and K
=
8.We compare the performances of the proposed RPC model with the following regularized support vector machine model [6] (take the jth class for example):
(38)
(
RSVM
)
min
⁡
∑
i
∈
I
‍
ξ
i
,
j
+
λ
j
∥
w
j
∥
s
.
t
.
KKK
y
¯
i
,
j
(
∑
l
∈
L
‍
w
j
l
x
i
l
+
b
j
)
≥
1
-
ξ
i
,
j
,
i
∈
I
,
K
K
K
c
K
ξ
i
,
j
≥
0
,
i
∈
I
,
where y
¯
i
,
j
=
2
y
i
,
j
-
1 and λ
j
≥
0 is a regularization parameter. As pointed by [8], λ
j
≥
0 represents a trade-off between the number of training set errors and the amount of robustness with respect to spherical perturbations of the data points. To make a fair comparison, in the following experiments we will test a series of λ values and choose the one with best performance. Note that if λ
j
=
0, we refer to this model as the classic support vector machine (SVM). See also [6] for more details on RSVM and its applications to multiple classification problems.


### 4.3. Test on Binary Classification

In this subsection, RSVM, NBC, and RPC are implemented on 12 data sets for the binary classification problems using the cross-validation methods. To improve the performances of RSVM, we transform the original data by the popularly used polynomial kernels [6].Tables1 and 2 show the averaged classification performances of RSVM, NBC, and the proposed RPC (over 10 randomly generated instances) for binary classification problems on Y5 and T1 data sets, respectively. For each data set, we randomly partition it into a training set and a test set based on the parameter tr which varies from 0.5 to 0.9. The highest classification accuracy on a training set among these three methods is highlighted in bold while the best classification accuracy on a test set is marked with an asteriskTable 1
Performances of RSVM, NBC, and RPC for binary classification problems on Y5 data set.
tr (%)
RSVM
NBC
RPC
Train (%)
Test (%)
Train (%)
Test (%)
Train (%)
Test (%)
50
90.7
88.2
63.9
66.2
88.4
90.5*
55
89.9
88.6
69.1
72.8
89.5
89.9*
60
89.0
85.0
70.3
72.1
91.3
86.4*
65
86.3
85.9
72.1
72.8
88.0
92.5*
70
92.3
84.1
70.3
75.7
90.8
86.3*
75
88.8
87.9
74.2
74.6
88.7
91.6*
80
88.7
93.8*
90.0
87.5
88.3
93.3
85
89.5
89.3
93.4
89.6
89.2
91.0*
90
89.5
88.4
93.3
95.8*
89.2
92.6Table 2
Performances of RSVM, NBC, and RPC for binary classification problems on T1 data set.
tr (%)
RSVM
NBC
RPC
Train (%)
Test (%)
Train (%)
Test (%)
Train (%)
Test (%)
50
91.4
84.8
76.5
68.9
91.3
87.5*
55
92.5
86.6
68.0
77.0
92.0
90.3*
60
89.8
86.1
72.9
73.8
88.9
90.9*
65
91.0
82.3
80.5
81.6
89.8
92.9*
70
86.8
95.5*
83.4
89.8
88.4
93.7
75
89.4
85.2
85.9
79.5
89.7
93.5*
80
91.8
80.8
88.1
79.9
89.7
91.1*
85
88.3
89.9
89.9
92.8
90.8
97.1*
90
88.5
90.2
88.8
94.2
90.9
97.2*Tables1 and 2 validate the effectiveness of the proposed RPC for binary classification problems compared with NBC and RSVM. Specifically, for most of the cases, RSVM has the highest classification accuracy on training sets but its performance on test sets is unsatisfactory. For most of the cases, the proposed RPC provides the highest classification accuracy on test sets. NBC provides better performances on test sets as the training rate increases. The experimental results also show that for given training rate, PRC can provide better performances on test sets than that on training sets; thus it can avoid the “overlearning” phenomenon.To further validate the effectiveness of the proposed RPC, we test it on additional 10 data sets, that is, T41–T45 and T61–T65. Table3 reports the averaged performances of three methods over 10 randomly generated instances when the training rate is set to 70%. Except for data sets T45, T63, and T64, RPC provides the highest accuracy on the test sets, and, for all the data sets, its accuracy is higher than 80%. As shown in Tables 1 and 2, the robustness of the proposed RPC guarantees its scalability on the test sets.Table 3
Performances of RSVM, NBC, and RPC for binary classification problems on other data sets whentr
⁡
=
70
%.
Data set
RSVM
NBC
RPC
Train (%)
Test (%)
Train (%)
Test (%)
Train (%)
Test (%)
T41
62.0
59.7
82.4
78.5
77.9
83.5*
T42
87.0
82.2
84.1
83.1
80.5
85.3*
T43
68.0
61.2
80.2
75.4
85.5
86.9*
T44
91.3
83.9
77.9
86.8
88.8
90.5*
T45
86.5
87.0
93.2
91.0*
84.0
89.1
T61
80.6
79.0
80.5
83.0
83.6
87.8*
T62
71.4
66.5
86.9
85.4*
86.3
85.4*
T63
63.7
69.5
89.6
89.1*
82.2
84.4
T64
88.2
86.7
97.0
96.9*
93.4
95.5
T65
75.0
63.4
79.7
81.5
90.5
92.9*


### 4.4. Test on Multiple Classification

In this subsection, we test the performances of on multiple classification problems by comparison with RSVM and NBC. Since the performance of RSVM is determined by its regularization parameterλ, we run a set of RSVM with λ varying from 0 to a big enough number and select the one with the best performance on test sets.Figures1 and 3 plot the performances of three methods on Y5 and T1 training sets, respectively. Unlike the case of binary classification problems, we can see that RPC provides a competitive performance even on the training sets. One explanation is that RSVM can outperform the proposed RPC on training sets by finding the optimal separation hyperplane for binary classification problem S while RPC is more robust to extend to solve multiple classification problems since it uses the nonlinear probability information of the data sets. The accuracy of NBC on the training sets also improves as the training rate increases.Figure 1
Performances of RSVM, NBC, and RPC on Y5 training set.Figures2 and 4 show the performances of both methods on Y5 and T1 test sets, respectively. We can see that, for most of the cases, RPC provides the highest accuracy among three methods. The accuracy of RSVM outperforms that of NBC on Y5 test set while the latter outperforms the former on the T1 test set.Figure 2
Performances of RSVM, NBC, and RPC on Y5 test set.Figure 3
Performances of RSVM, NBC, and RPC on T1 training set.Figure 4
Performances of RSVM, NBC, and RPC on T1 test set.To further test the performance of PRC on multiple classification problems, we carry out more experiments on data sets M1–M6. Table4 reports the averaged performances of three methods on these data sets when the training rate is set to 70%. Except for the M5 data set, PRC always provides the highest classification performances among three methods, and even for the M5 data set, its accuracy (88.0%) is very close to the best one (88.1%).Table 4
Performances of RSVM, NBC, and RPC for multiple classification problems on T1 data set.
Data set
RSVM
NBC
RPC
Train (%)
Test (%)
Train (%)
Test (%)
Train (%)
Test (%)
M1
65.4
68.2
72.7
73.7
79.1
77.4*
M2
76.9
75.3
82.6
74.8
81.7
80.9*
M3
57.9
69.9
74.8
87.4
95.4
92.0*
M4
70.4
64.1
97.1
92.3
95.4
92.3*
M5
77.4
71.3
89.4
88.1*
92.0
88.0
M6
75.7
70.5
74.1
79.4
86.4
80.8*From the tested real-life application, we conclude that the proposed RPC has the robustness to provide better performance for both binary and multiple classification problems compared with RSVM and NBC. The robustness of PRC enables it to avoid the “overlearning” phenomenon, especially for the binary classification problems.


## 4.1. Data Sets

Lithology classification is one of the basic tasks for geological investigation. To discriminate the lithology of the underground strata, various electromagnetic techniques are applied to the same strata to obtain different features, such as Gamma coefficients, acoustic wave, striation, density, and fusibility.Here numerical experiments are carried out on a series of data sets: the borehole T1, Y4, Y5, and Y6. All boreholes are located in Tarim Basin, China. In total, there are 12 data sets used for binary classification problems and 8 data sets used for multiple classification problems. For each data set, based on a prespecified training rateγ
∈
[
0,1
], it is randomly partitioned into two subsets: a training set and a test set, such that the size of training set accounts for γ of the total number of samples.


## 4.2. Experiment Design

The parameters in our models are chosen based on the size of data set. The parameterϵ depends on the number of the classes and defined as ϵ
=
δ
2
/
|
J
|, where δ
∈
(
0,1
). The choice of ϵ can be explained in this way: if there are |
J
| classes and the training data are uniformly distributed, then, for each probability p
i
,
j
l
=
1
/
|
J
|, its maximal variation range is between p
i
,
j
l
(
1
-
δ
) and p
i
,
j
l
(
1
+
δ
). The number of data intervals K
l is defined as K
l
=
|
I
|
/
(
|
J
|
×
K
) such that if the training data are uniformly distributed, then in each data interval there are K samples in each class. In the following context, we set δ
=
0.2 and K
=
8.We compare the performances of the proposed RPC model with the following regularized support vector machine model [6] (take the jth class for example):
(38)
(
RSVM
)
min
⁡
∑
i
∈
I
‍
ξ
i
,
j
+
λ
j
∥
w
j
∥
s
.
t
.
KKK
y
¯
i
,
j
(
∑
l
∈
L
‍
w
j
l
x
i
l
+
b
j
)
≥
1
-
ξ
i
,
j
,
i
∈
I
,
K
K
K
c
K
ξ
i
,
j
≥
0
,
i
∈
I
,
where y
¯
i
,
j
=
2
y
i
,
j
-
1 and λ
j
≥
0 is a regularization parameter. As pointed by [8], λ
j
≥
0 represents a trade-off between the number of training set errors and the amount of robustness with respect to spherical perturbations of the data points. To make a fair comparison, in the following experiments we will test a series of λ values and choose the one with best performance. Note that if λ
j
=
0, we refer to this model as the classic support vector machine (SVM). See also [6] for more details on RSVM and its applications to multiple classification problems.


## 4.3. Test on Binary Classification

In this subsection, RSVM, NBC, and RPC are implemented on 12 data sets for the binary classification problems using the cross-validation methods. To improve the performances of RSVM, we transform the original data by the popularly used polynomial kernels [6].Tables1 and 2 show the averaged classification performances of RSVM, NBC, and the proposed RPC (over 10 randomly generated instances) for binary classification problems on Y5 and T1 data sets, respectively. For each data set, we randomly partition it into a training set and a test set based on the parameter tr which varies from 0.5 to 0.9. The highest classification accuracy on a training set among these three methods is highlighted in bold while the best classification accuracy on a test set is marked with an asteriskTable 1
Performances of RSVM, NBC, and RPC for binary classification problems on Y5 data set.
tr (%)
RSVM
NBC
RPC
Train (%)
Test (%)
Train (%)
Test (%)
Train (%)
Test (%)
50
90.7
88.2
63.9
66.2
88.4
90.5*
55
89.9
88.6
69.1
72.8
89.5
89.9*
60
89.0
85.0
70.3
72.1
91.3
86.4*
65
86.3
85.9
72.1
72.8
88.0
92.5*
70
92.3
84.1
70.3
75.7
90.8
86.3*
75
88.8
87.9
74.2
74.6
88.7
91.6*
80
88.7
93.8*
90.0
87.5
88.3
93.3
85
89.5
89.3
93.4
89.6
89.2
91.0*
90
89.5
88.4
93.3
95.8*
89.2
92.6Table 2
Performances of RSVM, NBC, and RPC for binary classification problems on T1 data set.
tr (%)
RSVM
NBC
RPC
Train (%)
Test (%)
Train (%)
Test (%)
Train (%)
Test (%)
50
91.4
84.8
76.5
68.9
91.3
87.5*
55
92.5
86.6
68.0
77.0
92.0
90.3*
60
89.8
86.1
72.9
73.8
88.9
90.9*
65
91.0
82.3
80.5
81.6
89.8
92.9*
70
86.8
95.5*
83.4
89.8
88.4
93.7
75
89.4
85.2
85.9
79.5
89.7
93.5*
80
91.8
80.8
88.1
79.9
89.7
91.1*
85
88.3
89.9
89.9
92.8
90.8
97.1*
90
88.5
90.2
88.8
94.2
90.9
97.2*Tables1 and 2 validate the effectiveness of the proposed RPC for binary classification problems compared with NBC and RSVM. Specifically, for most of the cases, RSVM has the highest classification accuracy on training sets but its performance on test sets is unsatisfactory. For most of the cases, the proposed RPC provides the highest classification accuracy on test sets. NBC provides better performances on test sets as the training rate increases. The experimental results also show that for given training rate, PRC can provide better performances on test sets than that on training sets; thus it can avoid the “overlearning” phenomenon.To further validate the effectiveness of the proposed RPC, we test it on additional 10 data sets, that is, T41–T45 and T61–T65. Table3 reports the averaged performances of three methods over 10 randomly generated instances when the training rate is set to 70%. Except for data sets T45, T63, and T64, RPC provides the highest accuracy on the test sets, and, for all the data sets, its accuracy is higher than 80%. As shown in Tables 1 and 2, the robustness of the proposed RPC guarantees its scalability on the test sets.Table 3
Performances of RSVM, NBC, and RPC for binary classification problems on other data sets whentr
⁡
=
70
%.
Data set
RSVM
NBC
RPC
Train (%)
Test (%)
Train (%)
Test (%)
Train (%)
Test (%)
T41
62.0
59.7
82.4
78.5
77.9
83.5*
T42
87.0
82.2
84.1
83.1
80.5
85.3*
T43
68.0
61.2
80.2
75.4
85.5
86.9*
T44
91.3
83.9
77.9
86.8
88.8
90.5*
T45
86.5
87.0
93.2
91.0*
84.0
89.1
T61
80.6
79.0
80.5
83.0
83.6
87.8*
T62
71.4
66.5
86.9
85.4*
86.3
85.4*
T63
63.7
69.5
89.6
89.1*
82.2
84.4
T64
88.2
86.7
97.0
96.9*
93.4
95.5
T65
75.0
63.4
79.7
81.5
90.5
92.9*


## 4.4. Test on Multiple Classification

In this subsection, we test the performances of on multiple classification problems by comparison with RSVM and NBC. Since the performance of RSVM is determined by its regularization parameterλ, we run a set of RSVM with λ varying from 0 to a big enough number and select the one with the best performance on test sets.Figures1 and 3 plot the performances of three methods on Y5 and T1 training sets, respectively. Unlike the case of binary classification problems, we can see that RPC provides a competitive performance even on the training sets. One explanation is that RSVM can outperform the proposed RPC on training sets by finding the optimal separation hyperplane for binary classification problem S while RPC is more robust to extend to solve multiple classification problems since it uses the nonlinear probability information of the data sets. The accuracy of NBC on the training sets also improves as the training rate increases.Figure 1
Performances of RSVM, NBC, and RPC on Y5 training set.Figures2 and 4 show the performances of both methods on Y5 and T1 test sets, respectively. We can see that, for most of the cases, RPC provides the highest accuracy among three methods. The accuracy of RSVM outperforms that of NBC on Y5 test set while the latter outperforms the former on the T1 test set.Figure 2
Performances of RSVM, NBC, and RPC on Y5 test set.Figure 3
Performances of RSVM, NBC, and RPC on T1 training set.Figure 4
Performances of RSVM, NBC, and RPC on T1 test set.To further test the performance of PRC on multiple classification problems, we carry out more experiments on data sets M1–M6. Table4 reports the averaged performances of three methods on these data sets when the training rate is set to 70%. Except for the M5 data set, PRC always provides the highest classification performances among three methods, and even for the M5 data set, its accuracy (88.0%) is very close to the best one (88.1%).Table 4
Performances of RSVM, NBC, and RPC for multiple classification problems on T1 data set.
Data set
RSVM
NBC
RPC
Train (%)
Test (%)
Train (%)
Test (%)
Train (%)
Test (%)
M1
65.4
68.2
72.7
73.7
79.1
77.4*
M2
76.9
75.3
82.6
74.8
81.7
80.9*
M3
57.9
69.9
74.8
87.4
95.4
92.0*
M4
70.4
64.1
97.1
92.3
95.4
92.3*
M5
77.4
71.3
89.4
88.1*
92.0
88.0
M6
75.7
70.5
74.1
79.4
86.4
80.8*From the tested real-life application, we conclude that the proposed RPC has the robustness to provide better performance for both binary and multiple classification problems compared with RSVM and NBC. The robustness of PRC enables it to avoid the “overlearning” phenomenon, especially for the binary classification problems.


## 5. Conclusion

In this paper, we propose a robust probability classifier model to address the data uncertainty in classification problems. To quantitatively describe the data uncertainty, a class-conditional distributional set is constructed based on the modifiedχ
2-distance. We assume that the true distribution lies in the constructed distributional set centered in the nominal probability distribution. Based on the “linear combination assumption” for the posterior class-conditional probabilities, we consider a classification criterion using the weighted sum of the posterior probabilities. The optimal robust probability classifier is determined by minimizing the worst-case absolute error value over all the possible distributions belonging to the distributional set.Our proposed model introduces the recently developed distributionally robust optimization method into the classifier design problems. To obtain a computable model, we transform the resulted optimization problem into an equivalent second order cone programming based on conic duality theorem. Thus our model has the same computational complexity as the classic support vector machine and numerical experiments on real-life application validate its effectiveness. On the one hand, the proposed robust probability classifier provides a higher accuracy compared with RSVM and NBC by avoiding overlearning on training sets for binary classification problems; on the other hand, it also has a promising performance for multiple classification problems.There are still many important extensions in our model. Other forms of loss function, such as the mean squared error function and Hinge loss functions, should be studied to obtain tractable reformulations and the resulted models may provide better performances. Probability models considering joint probability distribution information are also interesting research directions.



---

*Source: 621314-2014-04-30.xml*