# Imprecise Imputation as a Tool for Solving Classification Problems with Mean Values of Unobserved Features

Authors: Lev V. Utkin; Yulia A. Zhuk
Journal: Advances in Artificial Intelligence
 (2013)

---

## Abstract

A method for solving a classification problem when there is only partial information about some features is proposed. This partial information comprises the mean values of features for every class and the bounds of the features. In order to maximally exploit the available information, a set of probability distributions is constructed such that two distributions are selected from the set which define the minimax and minimin strategies. Random values of features are generated in accordance with the selected distributions by using the Monte Carlo technique. As a result, the classification problem is reduced to the standard model which is solved by means of the support vector machine. Numerical examples illustrate the proposed method.


---

## Body

## 1. Introduction

There are several major data mining techniques including classification, clustering, and novelty detection. We consider classification as a data mining technique used to predict an unobserved output valuey based on an observed input vector x. This requires us to estimate a predictor f from training data or a set of example pairs of (x,y). A special very important problem of the statistical machine learning is the binary classification problem which can be regarded as a task of classifying some objects into two classes (groups) in accordance with their properties or features. In other words, we have to classify each pattern x into one of the classes by means of a discriminant function f.A common assumption in supervised learning is that training and predicted data are drawn from the same (unknown) probability distribution; that is, training and predicted data come from the same statistical model. As a result, most machine learning algorithms and methods exploit this assumption which, unfortunately, does not often hold in practice. This may lead to a performance deterioration in the induced classifiers [1, 2]. This problem may arise if we have imbalanced data [3] or in case of rare events or observations [4]. The assumption does not hold also in case of partially known or observed features. For instance, it may take place when we know only some mean values of the features but cannot get their actual values during training.One of the approaches to handle the above problem and to cope with the imbalance and possible inconsistencies of training and predicted data is the minimax strategy for which the classification parameters are determined by minimizing the maximum possible risk of misclassification [1, 2]. This is an “extreme” strategy of decision making. As pointed out in [1], the minimax classifiers may be seen as overconservative since its goal is to optimize the performance under the least favorable conditions. Therefore, it is interesting to simultaneously study the so-called minimin or optimistic strategy for which the classification parameters are determined by minimizing the minimum possible risk of misclassification. This is another “extreme” strategy.By taking into account the above, we propose a classification model using the minimax and minimin strategies for situations when a part of features are observed and there are precise values of the features corresponding to different classified classes, but our initial information about other parts of features is restricted by mean values of the features for every class. In other words, we know only mean values (expectations) of some features and do not have any observations. This is a very restrictive piece of information which should be exploited. The features with this information will be called unobserved for simplicity. A typical example of the above situation is a mode of production of reinforced concrete beams whose quality and strength depend on a number of parameters such as the weight of reinforcement bars and concrete materials. If we have not observed or measured some of the parameters before, it is difficult to reject new beams or to classify them into two classes: defective (rejected) or of high quality, because we do not have the learning set of beams with the measured parameters. However, if we know, for instance, how much steel has been used up by manufacturingN beams, then we are able to evaluate the average weight of steel in a beam. The information can be elicited, for instance, from experts. Often, it is easy for experts to provide judgments about some average values of a feature for every class because this information is the most simple and understandable.One of the simplest ways to solve the classification problem with the partial information is to assume that the mean values are observed values. In fact, we replace in this case an unknown probability distribution of data of a feature by the deterministic variable which takes one value corresponding to the mean value of this feature. Of course, we accept here a very strong assumption which may lead to a significant performance deterioration especially if the underlying probability distribution is not symmetric. Another way is to find the mean values of every observed feature and use the simplest classification algorithm considered by many authors, for instance, by [5]. However, we lose some useful information in this case, which can be inferred from the observations.In order to maximally exploit the available information about features, we propose another approach whose underlying ideas can be formulated with a combination of multiple imputation [6] and imprecise models of features.As indicated in [7], imputation is a class of methods by which an estimation of the missing value or its distribution is used to generate predictions from a given model. In particular, either a missing value is replaced with an estimation of the value or alternatively the distribution of possible missing values is estimated, and corresponding model predictions are combined probabilistically. Various imputation treatments for missing values in training data are available that may be deployed at prediction time [8–13]. However, some treatments such as multiple imputation [6] are particularly suitable to induction. In particular, multiple imputation (or repeated imputation) is a Monte Carlo approach that generates multiple simulated versions of a dataset such that each is analyzed, and the results are combined to generate inference.We do not know the probability distributions of data for unobserved features. However, the mean values of features and their boundary values produce a set of probability distributions bounded by some lower and upper cumulative distribution functions (CDFs). This way leads to constructing the so-called p-boxes [14, 15] from data. It should be noted that the considered set of distributions is not the set of parametric distributions having the same parametric form as the bounding distributions, but it is the set of all possible distributions restricted by the lower and upper bounds. This is an important feature of the proposed approach in this paper. A probability distribution is selected from the p-box in order to make a pessimistic decision, which maximizes the risk function as a measure of the classification error. In other words, the well-known minimax strategy is applied for solving the classification problem, which appears as an insurance against the worst case [16]. Another probability distribution is selected from the p-box in order to make an optimistic or minimin decision. The similar idea applied to regression models has been considered in [17–19]. So, the first idea is to consider the lower and upper probability distributions of feature data produced by the corresponding mean values and bounds for the feature values.It should be noted that the obtained bounding probability distributions do not belong to standard types of probability distributions and their convolution for combining features and for computing parameters of the discriminant function is an extremely hard problem. Therefore, in order to cope with this problem, the second idea is proposed. We can apply the Monte Carlo technique for generating random values of features, which are governed by the probability distributions selected from the p-boxes in accordance with the minimax and minimin strategies [20, 21]. In a nutshell, for every example of the training set, we generate a (large) number of random values for unobserved features. It is a multiple imputation technique which has been applied to classification problems [7, 22, 23]. But the main distinction of the proposed approach from the available ones is that it is based on some partial information about unobserved features and uses the p-boxes for generating random values of features.After carrying out this procedure, the classification problem can be solved by means of standard methods, for instance, by means of the support vector machine (SVM). The Monte Carlo technique has also been applied to general classification problems [24, 25]. It has been successfully applied to reliability analysis problems in the framework of classification models [26, 27]. Of course, the Monte Carlo technique requires additional computation efforts. However, its main advantage is its simplicity. Moreover, we get the standard classification problem solved by standard available software tools.We have to stress that there is no sense in applying the proposed model when we have some missing values among the observed values of a feature. The model has to be used when we do not have observations for some features at all and only mean values of the features and their bounds are known.The paper is organized as follows. A statement of the well-known standard classification problem is given in Section2. This statement is extended on the case of a set of probability distributions of training data in Section 3. In this section, two strategies, minimax and minimin, are formally introduced. The classification problem with mean values for a part of unobserved features is considered in Section 4. A general method for constructing the classification model by partial information about some features with using the set of probability distributions is described in the same section. A question of the training data generation for realizing the Monte Carlo simulation is solved in Section 5. A way for reducing the classification problem with partial information about features to the standard problem and its solution by means of the SVM method is given in Section 6. Numerical examples with synthetic data and with the real datasets, including Iris, Pima Indian Diabetes, Mammographic Masses, Parkinsons, Indian Liver Patient, Breast Cancer Wisconsin (Original), Breast Cancer Wisconsin (Diagnostic), Musk, and Lung-Cancer datasets from UCI machine learning repository [28], are provided in Section 7.


## 2. The Standard Classification Problem

The binary-classification problem can be formulated as follows. There are predictor-response data with a binary responsey representing the observation of classes y=-1 and y=1. The binary-classification problem is to estimate a region in predictor space in which class 1 is observed with the greatest possible majority. Suppose we are given empirical data
(1)(x1,y1),(x2,y2),…,(xn,yn)∈ℝl×{-1,+1}.Here,{x1,x2,…,xn} is some nonempty set of the patterns or examples; y1,…,yn are labels or outputs taking the values -1 and +1; l is the number of features. It is supposed that the number of elements in the training set belonging to the class y is ny and their indices form the set of indices N(y); that is, we can write n-1+n1=n and N(y)={i:yi=y}.Classification problem is usually characterized by an unknown CDFF0(x,y) on ℝl×{-1,+1} defined by the training set or examples xi and their corresponding class labels yi.The main problem is to find a decision functiong(x), which predicts accurately the class label y of any example x that may or may not belong to the training set. In other words, we seek a function g that minimizes the classification error, which is given by the probability that g(x)≠y. One of the possible approaches for solving the problem is the discriminant function approach which uses a real valued function f(x) called the discriminant function whose sign determines the class label prediction: g(x)=sgn(f(x)). The discriminant function f(x) may be parametrized with some parameters w=(w0,w), w=(w1,…,wl), that are determined from the training examples by means of a learning algorithm. In particular, the function f(x) may be linear; that is, f(x)=〈w,x〉+w0. Introduce also the notation xi(k) for the ith element of the vector xk.Given the training data, the linear discriminant training problem is to minimize the following risk measure [29]:
(2)R(w)=∫ℝl×{-1,1}‍L(x,y)dF0(x,y).
Here, the loss function L(x,y) usually takes a nonzero value when the sign of the discriminant function (the class label prediction) does not coincide with the class label y. The minimization of the risk measure is carried out over the parametric class of functions f(x). In other words, the function f(x) provides the minimum of R(w) such that R(wopt)=minwR(w).


## 3. The Classification Problem under a Set of Probability Distributions

Let us represent the joint probability asF0(x,y)=F0(x∣y)·P(y). Here, P(y) is the prior probability that an example x belongs to the class y. Then, we can rewrite the risk measure taking into account two values of y(3)R(w)=P(-1)R-1(w)+P(1)R1(w).
Here,
(4)R-1(w)=∫ℝl‍L(x,-1)dF0(x∣-1),R1(w)=∫ℝl‍L(x,1)dF0(x∣1).By assuming that features are independent, we can rewrite the above risk measures as(5)Ry(w)=∫ℝl‍L(x,y)∏i=1l‍dFi(xi∣y),y=-1,1.Suppose that the distributionsFi are unknown. However, we assume that some lower and upper bounds for a set ℱi(y) of the CDFs Fi(x∣y) are known to be accurate to w and they are F_i(x∣y) and F¯i(x∣y), respectively. We can write
(6)ℱi(y)={Fi(x∣y)∣F_i(x∣y)≤Fi(x∣y)≤F¯i(x∣y)}.In other words, there is an unknown precise “true” CDFFi(x∣y)∈ℱi(y) for every y∈{-1,+1} and every i=1,…,l, but we do not know it and only know that it belongs to the set ℱi(y). It has been mentioned that the set ℱi(y) is not the set of parametric distributions having the same parametric form as the bounding distributions, but it is the set of all possible distributions restricted by the lower and upper bounds.


### 3.1. The Minimax Strategy

One of the possible strategies to derive an estimator is the minimax (pessimistic) strategy. According to the minimax strategy, we select a CDF from the setℱi(-1) and a CDF from the set ℱi(1) such that the risk measures R-1(w) and R1(w) achieve their maximum for every fixed w. The minimax strategy can be explained in a simple way. We do not know a precise CDF Fi, and every CDF from ℱi(y) can be selected. Therefore, we should take the “worst” distribution providing the largest value of the risk measure. The minimax criterion appears as an insurance against the worst case because it aims at minimizing the expected loss in the least favorable case [16].Denoteℱ(y)=ℱ1(y)×⋯×ℱl(y). Since the sets ℱ(-1) and ℱ(+1) are obtained independently for y=-1 and y=1, respectively, then
(7)R¯(w)=maxF(x∣y)∈ℱ(y)R(w)=∑y=-1,1‍P(y)maxF(x∣y)∈ℱ(y)Ry(w).The minimax risk functional with respect to the minimax strategy is now of the form:(8)R¯(wopt)=minwR¯(w).Let us consider in detail the first problemmaxF(x∣-1)∈ℱ(-1)R-1(w). Most loss functions L(x,-1) applied in classification are increasing with f. This implies that the upper bound for R-1(w), that is, the maximum of R-1(w) over all distributions from ℱ(-1), is achieved at the CDFs F_(x∣-1) (see, e.g., Walley’s paper [30]). Hence, there holds
(9)R¯-1(w)=∫ℝl‍L(x,-1)dF_(x∣-1).Here,(10)F_(x∣y)=∏i=1l‍F~i(xi∣y),
where
(11)F~i(xi∣y)={F_i(xi∣y),L(x,y)increaseswithxi,F¯i(xi∣y),L(x,y)decreaseswithxi.The above condition can be rewritten in terms of the functionf instead of L(12)F~i(xi∣-1)={F_i(xi∣-1),f(x)increaseswithxi,F¯i(xi∣-1),f(x)decreaseswithxi,F~i(xi∣1)={F_i(xi∣1),f(x)decreaseswithxi,F¯i(xi∣1),f(x)increaseswithxi.In the same way, we can consider the second problemmaxF(x∣1)∈ℱ(1)R1(w). Most of loss functions L(x,1) are decreasing with f. Therefore, the upper bound for R1(w) is achieved at the distribution F¯(x∣1). This implies that
(13)R¯1(w)=∫ℝl‍L(x,1)dF¯(x∣1).Finally, we get the upper bound for the risk measureR(w), which is of the form
(14)R¯(w)=∑y=-1,1‍P(y)∫ℝl‍L(x,y)∏i=1l‍dF~i(xi∣y).Now we have two tasks. First, we have to define CDFsF_i(x∣y) and F¯i(x∣y) from the available information for every y=-1,1 and for every i=1,…,l. Second, we have to define the prior probabilities of classes P(-1) and P(1).


### 3.2. The Minimin Strategy

The minimin strategy can be regarded as a direct opposite of the minimax strategy. According to the minimin strategy, the risk measureR is minimized over all probability distributions from the set ℱ as well as over all values of parameters. The strategy can be called optimistic because it selects the “best” probability distribution from the set ℱ. Of course, the minimin strategy is of little interest. Nevertheless, we study it in order to compare “extreme” cases (minimax and minimin strategies).Similarly to the minimax strategy, we can write(15)R_(w)=minF(x∣y)∈ℱ(y)R(w)=∑y=-1,1‍P(y)minF(x∣y)∈ℱ(y)Ry(w).Since loss functionsL(x,-1) applied in classification are increasing with f, then the lower bound for R-1(w), that is, the minimum of R-1(w) over all distributions from ℱ(-1), is achieved at the distribution F¯(x∣-1). The loss function L(x,1) is decreasing. Therefore, the lower bound for R1(w) is achieved at the distribution F_(x∣1). Hence, there holds
(16)R_(w)=∑y=-1,1‍P(y)∫ℝl‍L(x,y)∏i=1l‍dF^i(xi∣y),
where
(17)F^i(xi∣y)={F_i(xi∣y),L(x,y)decreaseswithxi,F¯i(xi∣y),L(x,y)increaseswithxi.The optimization problem for computing the optimal values of parametersw for the minimin strategy can be written as
(18)R_(wopt)=minwR_(w).


## 3.1. The Minimax Strategy

One of the possible strategies to derive an estimator is the minimax (pessimistic) strategy. According to the minimax strategy, we select a CDF from the setℱi(-1) and a CDF from the set ℱi(1) such that the risk measures R-1(w) and R1(w) achieve their maximum for every fixed w. The minimax strategy can be explained in a simple way. We do not know a precise CDF Fi, and every CDF from ℱi(y) can be selected. Therefore, we should take the “worst” distribution providing the largest value of the risk measure. The minimax criterion appears as an insurance against the worst case because it aims at minimizing the expected loss in the least favorable case [16].Denoteℱ(y)=ℱ1(y)×⋯×ℱl(y). Since the sets ℱ(-1) and ℱ(+1) are obtained independently for y=-1 and y=1, respectively, then
(7)R¯(w)=maxF(x∣y)∈ℱ(y)R(w)=∑y=-1,1‍P(y)maxF(x∣y)∈ℱ(y)Ry(w).The minimax risk functional with respect to the minimax strategy is now of the form:(8)R¯(wopt)=minwR¯(w).Let us consider in detail the first problemmaxF(x∣-1)∈ℱ(-1)R-1(w). Most loss functions L(x,-1) applied in classification are increasing with f. This implies that the upper bound for R-1(w), that is, the maximum of R-1(w) over all distributions from ℱ(-1), is achieved at the CDFs F_(x∣-1) (see, e.g., Walley’s paper [30]). Hence, there holds
(9)R¯-1(w)=∫ℝl‍L(x,-1)dF_(x∣-1).Here,(10)F_(x∣y)=∏i=1l‍F~i(xi∣y),
where
(11)F~i(xi∣y)={F_i(xi∣y),L(x,y)increaseswithxi,F¯i(xi∣y),L(x,y)decreaseswithxi.The above condition can be rewritten in terms of the functionf instead of L(12)F~i(xi∣-1)={F_i(xi∣-1),f(x)increaseswithxi,F¯i(xi∣-1),f(x)decreaseswithxi,F~i(xi∣1)={F_i(xi∣1),f(x)decreaseswithxi,F¯i(xi∣1),f(x)increaseswithxi.In the same way, we can consider the second problemmaxF(x∣1)∈ℱ(1)R1(w). Most of loss functions L(x,1) are decreasing with f. Therefore, the upper bound for R1(w) is achieved at the distribution F¯(x∣1). This implies that
(13)R¯1(w)=∫ℝl‍L(x,1)dF¯(x∣1).Finally, we get the upper bound for the risk measureR(w), which is of the form
(14)R¯(w)=∑y=-1,1‍P(y)∫ℝl‍L(x,y)∏i=1l‍dF~i(xi∣y).Now we have two tasks. First, we have to define CDFsF_i(x∣y) and F¯i(x∣y) from the available information for every y=-1,1 and for every i=1,…,l. Second, we have to define the prior probabilities of classes P(-1) and P(1).


## 3.2. The Minimin Strategy

The minimin strategy can be regarded as a direct opposite of the minimax strategy. According to the minimin strategy, the risk measureR is minimized over all probability distributions from the set ℱ as well as over all values of parameters. The strategy can be called optimistic because it selects the “best” probability distribution from the set ℱ. Of course, the minimin strategy is of little interest. Nevertheless, we study it in order to compare “extreme” cases (minimax and minimin strategies).Similarly to the minimax strategy, we can write(15)R_(w)=minF(x∣y)∈ℱ(y)R(w)=∑y=-1,1‍P(y)minF(x∣y)∈ℱ(y)Ry(w).Since loss functionsL(x,-1) applied in classification are increasing with f, then the lower bound for R-1(w), that is, the minimum of R-1(w) over all distributions from ℱ(-1), is achieved at the distribution F¯(x∣-1). The loss function L(x,1) is decreasing. Therefore, the lower bound for R1(w) is achieved at the distribution F_(x∣1). Hence, there holds
(16)R_(w)=∑y=-1,1‍P(y)∫ℝl‍L(x,y)∏i=1l‍dF^i(xi∣y),
where
(17)F^i(xi∣y)={F_i(xi∣y),L(x,y)decreaseswithxi,F¯i(xi∣y),L(x,y)increaseswithxi.The optimization problem for computing the optimal values of parametersw for the minimin strategy can be written as
(18)R_(wopt)=minwR_(w).


## 4. Mean Values of Features and a Method for Constructing the Model

Suppose that an object is characterized byl features. Moreover, we have the training set (1). Every observation xi contains the observed values of t features x1(i),…,xt(i). We assume that features with numbers 1,…,t are observed without loss of generality. However, other l-t features are unobserved, and we know only the conditional mean values mi(y) of the features for every class and their bounds ai and bi, i=t+1,…,l. How to classify the objects in this case?One of the simplest ways is to assume that the mean values are observed values. In other words, we can writexj(i)=mj(y), j=t+1,…,l, for all i=1,…,n, that is, for all observations. This way can be applied when there are a lot of observations. However, when the amount of statistical data is small, the above replacement of observations by mean values may lead to incorrect classification. Moreover, we do not take into account the information about bounds of feature values here, which might be useful.Another way is to find the mean values of every observed feature with the numberj=1,…,t, for every class as
(19)mj(-1)=1n-1∑i:yi=-1‍xj(i),mj(1)=1n1∑i:yi=1‍xj(i).
Then we can exploit the simplest classification algorithm considered by many authors, for instance, by [5]. The algorithm is based on analyzing the distances between a predicted vector x and two vectors of mean values of features. The smallest distance determines the class of x. It has been noted in [5] that the proposed decision is the best we can do if we have no prior information about the probabilities of the two classes. However, we lose some useful information in this case, which can be inferred from the observations.Therefore, we have to develop a classification method which maximally exploits the available information about features.The first important assumption we use below is that the values oft observed features are governed by the nonparametric or empirical distribution.By dealing with the unobserved features, we consider two cases or two important assumptions. The first one is that we have conditional expectationsmj(y) defined for every class. The second one is that we have unconditional expectation for every feature, which does not depend on the class. This case is less informative, but it is typical for many applications. It is reduced to the first case by accepting the equality mj(-1)=mj(1).Let us divide the discriminant function into two parts:(20)f(1)(x(1))=w0+∑i=1t‍wixi=w0+〈x(1),w(1)〉,f(2)(x(2))=∑i=t+1l‍wixi=〈x(2),w(2)〉.
Here, x(1)=(x1,…,xt), x(2)=(xt+1,…,xl), w(1)=(w1,…,wt), and w(2)=(wt+1,…,wl).The whole discriminant function is the sumf(1)(x(1))+f(2)(x(2)). We assume that every function f(1) and f(2) has some conditional CDFs F1(f(1)∣y) and F2(f(2)∣y) for every y=-1,1, respectively.Let us return to the risk measureRy(w) defined in (4). It can be rewritten as follows:
(21)Ry(w)=∫ℝ2‍L(f(1)+f(2),y)dF(1)(f(1)∣y)dF(2)(f(2)∣y)=∫ℝl-t+1‍L(f(1)+f(2),y)dF(1)(f(1)∣y)∏j=t+1l‍dF~j(xj∣y).
Here, Fj(xj∣y) is the conditional CDF of the jth feature for the class y.By assuming that the observed features are governed by the empirical distribution, we can conclude that the distribution of the functionf(1) is also empirical; that is, its PDF is the weighted sum of Dirac functions δ(f(1)-fi(1)) with weights 1/ny. Hence, we obtain
(22)Ry(w)=∫ℝl-t+1‍L(f,y)1ny×∑i∈N(y)‍δ(x-fi(1))dx∏j=t+1l‍dF~j(xj∣y)=1ny∑i∈N(y)‍∫ℝl-t‍L(fi(1)+f(2),y)×∏j=t+1l‍dF~j(xj∣y).The precise CDFsFj, j=t+1,…,l, are unknown. However, we know the mean values of every feature with numbers t+1,…,l for every class y and the bounds of their values. Therefore, we can construct a set of CDFs with some lower and upper bounds. Given the mean value mi(y) of the ith feature and its bounds ai, bi, the lower F_i(x∣y) and upper F¯i(x∣y) conditional CDFs of the ith feature values are
(23)F_i(x∣y)={0,x<ai,max(0,x-mi(y)x-ai),ai≤x<bi,1,x≥bi,F¯i(x∣y)={0,x<ai,min(1,bi-mi(y)bi-x),ai≤x<bi,1,x≥bi.It should be noted that the expression for the upper boundF¯i(x∣y) can be obtained by using the natural extension [31, 32] which can be represented as the following linear programming problem:
(24)F¯i(x∣y)=minc,d(c+d·mi(y)),
subject to c,d∈ℝ, c+d·z≥1{z≤x}, for all z∈[ai,bi].Here,1{z≤x} is the indicator function taking the value 1 if z≤x. The lower bound F_i(x∣y) can be obtained in the same way by solving the following programming problem:
(25)F_i(x∣y)=maxc,d(c+d·mi(y)),
subject to c,d∈ℝ,c+d·z≤1{z≤x}, for all z∈[ai,bi].The same bounds have been differently obtained in the work [33].The lower and upper CDFs are shown in Figure1, where M=m(y)=2, a=-1, and b=8. The resulting bounds are optimal in the sense that they could not be any tighter under the given information. However, this does not mean that any distribution whose CDF is inscribed within this bounded probability region would have the same expectations mi(y). The obtained set is more rich and produces the p-box. This leads to a more conservative and cautious solution of the classification problem.Figure 1
The lower and upper probability distributions.Now we have two problems. The first one is to determine the CDFsFj, j=t+1,…,l. The second problem is to solve an optimization problem for computing parameters w by using the above expressions for the risk measure.Since the functionL(f,-1) is increasing, then the upper bound for R-1(w) can be written as
(26)R¯-1(w)=1n-1∑i∈N(-1)‍∫ℝl-t‍L(fi(1)+f(2),-1)×∏j=t+1l‍dF~j(xj∣-1).
Here, the upper bound R¯-1(w) depends only on the bounds for CDFs F~j(xj∣-1). This is a very important property which will be used later.The functionL(f,1) is decreasing. This implies that the upper bound for R1(w) is
(27)R¯1(w)=1n1∑i∈N(1)‍∫ℝl-t‍L(fi(1)+f(2),1)×∏j=t+1l‍dF~j(xj∣1).
Here, the upper bound R¯1(w) depends also only on the bounds for CDFs F~j(xj∣1).It should be noted that it is difficult to integrate in (26)-(27) in an explicit form in order to get some functions of parameters w even for the simplest loss functions L. However, we can apply the standard Monte Carlo technique. By using this technique, random values of features with the indices j=t+1,…,l, are generated in accordance with the CDFs F~j(xj∣1) for the class y=1 and with the CDFs F~j(xj∣-1) for the class y=-1. By generating Ki random vectors of features xi,k(2)=(xt+1(i,k),…,xl(i,k)), k=1,…,Ki, for every i=1,…,N(y) and every y=-1,1 in accordance with the CDF F~j(xj∣-1) and the CDF F~j(xj∣1), we rewrite (26)-(27) as follows:
(28)R¯-1(w)=1n-1∑i∈N(-1)‍1Ki∑k=1Ki‍L(fi(1)+〈xi,k(2),w(2)〉,-1),R¯1(w)=1n1∑i∈N(1)‍1Ki∑k=1Ki‍L(fi(1)+〈xi,k(2),w(2)〉,1).Finally, we obtain the upper risk measure as a function of parametersw as
(29)R¯(w)=∑y=-1,1‍P(y)ny×∑i∈N(y)‍1Ki∑k=1Ki‍L(fi(1)+〈xi,k(2),w(2)〉,yi),
where xj(i,k)~F~j(xj∣-1) for i∈N(-1) and xj(i,k)~F~j(xj∣1) for i∈N(1).In fact, we extend the training set by generating the “missing” values of features. We reduce the learning problem with combined types of the training information to the standard problem when there are training data in the form of real and generated observations of all features. It is important to note that we do not replace here the “missing” features by their mean valuesmi(-1),i=t+1,…,l. The “missing” values are replaced by a set of random values of features generated in accordance with the corresponding lower and upper CDFs.The optimization problem for computing parametersw for the minimin strategy is of the same form as (29). However, the value xj(i,k) is governed by the CDF F^j(xj∣-1) for i∈N(-1), and xj(i,k) is governed by the CDF F^j(xj∣1) for i∈N(1). This is just one distinction of optimization problems by the minimax and minimin strategies.An important question is how to determine the functionsF~j and F^j or how to determine the type of dependence between L and xj. We can propose two possible ways for doing that. First, the dependence can be determined by experts or by a decision maker on the basis of a preliminary analysis of features and classes. Very often, we can evaluate how possible changes of the feature values impact on the output variable y on the basis of physical meaning of the analyzed classification problem. Of course, this way is simple, but, generally, it cannot be always applied to classification problems. Second, we can enumerate 2l-t+1 variants of the CDFs F~j and F^j by taking different lower and upper CDFs instead of F~j and F^j. In accordance with the minimax strategy, the optimal risk measure is the largest value of the risk measure R(w) by optimal parameters wopt. The same procedure can be applied to the minimin strategy. However, we search for the smallest value of the risk measure R(w) by optimal parameters wopt in this case.


## 5. A Procedure for Generation of Random Feature Values

Let us consider how to generate random feature values in accordance with the above CDFs. First, we analyze the lower CDF. It can be seen from its form that the corresponding random variable is concentrated on two subsets. The first subset is the interval frommi(y) till bi. The second is the point bi. The probability that the random variable is in the interval [mi(y),bi) is equal to (bi-mi(y))/(bi-ai). The probability of the point bi is (mi(y)-ai)/(bi-ai). Therefore, a random number is generated in two steps. First, a random variable r uniformly distributed in interval [0,1] is generated. If r is larger than (bi-mi(y))/(bi-ai), then x=bi; that is, the generated number at the second step is bi. If r is smaller than (bi-mi(y))/(bi-ai), then we use the well-known inverse transformation method. According to the method, the random number x is computed through the inverse lower CDF; that is,
(30)x=mi(y)-ai·r1-r.
The right side of the above equality is obtained by means of the inverse transformation of the lower CDF.The same simulation procedure can be provided for the upper probability distribution. A random variabler uniformly distributed in interval [0,1] is generated. If r is smaller than (bi-mi(y))/(bi-ai), then x=ai; that is, the generated number at the second step is ai. If r is larger than (bi-mi(y))/(bi-ai), then, according to the inverse transformation method, the random number x is computed through the inverse upper CDF; that is,
(31)x=mi(y)-bi·(1-r)r.


## 6. Hinge Loss Function and SVM

A procedure for computing optimal values of parametersw depends on the loss function L. We consider the so-called hinge loss function which is of the form L(f,y)=max(0,1-yf). This function is taken for the consideration in order to reduce the classification problem to the SVM method which gives the opportunity to construct nonlinear classification models in a rather simple way.After substituting the hinge loss function into the objective function (29), we get the following optimization problem:
(32)R¯(w)=∑y=-1,1‍P(y)ny×∑i∈N(y)‍1Ki×∑k=1Ki‍max(0,1-yi(〈(xi(1),xi,k(2)),w〉+w0)).
It can be rewritten in a more dense form:
(33)R¯(w)=∑i=1n‍P(yi)nyiKi×∑k=1Ki‍max(0,1-yi(〈(xi(1),xi,k(2)),w〉+w0)).Let us introduce a new optimization variable(34)Gi,k=max(0,1-yi(〈(xi(1),xi,k(2)),w〉+w0)).
Then we get the optimization problem
(35)R¯(wopt)=minw(∑i=1n‍P(yi)nyiKi∑k=1Ki‍Gi,k),
subject to
(36)Gi,k≥1-yi(〈(xi(1),xi,k(2)),w〉+w0),Gi,k≥0,∀i=1,…,n,k=1,…,Ki.So, we have the linear optimization problem having(l+1)+∑i=1n‍Ki optimization variables and 2∑i=1n‍Ki constraints.Let us add the standard Tikhonov regularization term(1/2)〈w,w〉 (the most popular penalty or smoothness term) [34] to the objective function (35) and the constant “cost” parameter C. The smoothness (Tikhonov) term can be regarded as a constraint which enforces uniqueness by penalizing functions with wild oscillation and effectively restricting the space of admissible solutions. The detailed analysis of regularization methods can be found also in the work [35]. Then we get the following quadratic programming problem:
(37)R¯(wopt)=min(12〈w,w〉+C∑i=1n‍P(yi)nyiKi∑k=1Ki‍Gi,k),
subject to (36).Instead of minimizing the primary objective function (37), a dual objective function, the so-called Lagrangian, can be formed of which the saddle point is the optimum. The Lagrangian is
(38)L=12〈w,w〉+C∑i=1n‍∑k=1Ki‍P(yi)nyiKiGi,k-∑i=1n‍∑k=1Ki‍ηi,kGi,k-∑i=1n‍∑k=1Ki‍φi,k(Gi,k-1+yi〈(xi(1),xi,k(2)),w〉+yiw0).
Here, ηi,k,φi,k,i=1,…,n,k=1,…,Ki are Lagrange multipliers. Hence, the dual variables have to satisfy positivity constraints ηi,k≥0,φi,k≥0 for all i,k.Hence, we get the simplified Lagrangian(39)L=12〈w,w〉-∑i=1n‍∑k=1Ki‍φi,k(yi〈(xi(1),xi,k(2)),w〉-1).Now we can divide all terms of the above objective function into two parts corresponding to the observed and unobserved features, respectively,(40)L=∑i=1n‍∑k=1Ki‍φi,k+12〈w(1),w(1)〉-∑i=1n‍∑k=1Ki‍φi,k(yi〈xi(1),w(1)〉)+12〈w(2),w(2)〉-∑i=1n‍∑k=1Ki‍φi,k(yi〈xi,k(2),w(2)〉).Hence, we obtain the dual optimization problem(41)maxφi,kL=∑i=1n‍∑k=1Ki‍φi,k-12∑i=1n‍∑j=1n‍yiyj〈xi(1),xj(1)〉∑k=1Ki‍∑u=1Kj‍φi,kφj,u-12∑i=1n‍∑j=1n‍yiyj∑k=1Ki‍∑u=1Kj‍φi,kφj,u〈xi,k(2),xj,u(2)〉,
subject to
(42)0≤φi,k≤C·P(yi)nyiKi,i=1,…,n,k=1,…,Ki.Any data point for whichφi,k>0 is called a support vector. Let S and NS denote the set of indices of the support vectors and their total number, respectively. Then one of the ways for computing the parameter w0 is
(43)w0=1NS∑s∈S‍(ys-∑i=1n‍∑k=1Ki‍yiφi,k〈(xi(1),xi,k(2)),(xs(1),xs(2))〉),
where (ys,xs) is one of the support vectors.If we assume thatKi=K for all i=1,…,n, the prior probabilities are defined as P(y)=ny/n, then we rewrite the optimization problem as
(44)maxφi,kL=∑i=1n‍∑k=1K‍φi,k-12∑i,j=1n‍∑k,u=1K‍yiyj〈(xi(1),xi,k(2)),(xj(1),xj,u(2))〉φi,kφj,u,
subject to
(45)0≤φi,k≤CnK,i=1,…,n,k=1,…,K.Finally, we can write the discriminant function(46)f(x)=∑i=1n‍∑k=1K‍yiφi,k〈(xi(1),xi,k(2)),(x(1),x(2))〉+w0.The main advantage of the SVM is the use of kernels which are functions that transform the input data to a high-dimensional space where the learning problem is solved. There are many types of kernel that may be used in an SVM. Acceptable kernels must satisfy Mercer’s condition. Commonly used forms of kernels are linearK(xi,xj)=〈xi,xj〉, polynomial K(xi,xj)=(γ〈xi,xj〉+r)d, γ>0, radial basis function (RBF) K(xi,xj)=exp(-γ∥xi-xj∥2), γ>0, and sigmoid K(xi,xj)=tanh(γ〈xi,xj〉+r). Here, γ, r, and d are kernel parameters. The kernel functions allow us to significantly extend the class of discriminant functions that can be used in this approach.


## 7. Experimental Design

We illustrate the method proposed in this paper via several examples; all computations have been performed using the statistical software R [36]. We investigate the performance of the proposed method and compare it with other methods dealing with missing data by considering the accuracy measure (ACC), which is the proportion of correctly classified cases on a sample of data; that is, ACC is an estimate of a classifier’s probability of a correct response. This measure is often used to quantify the predictive performance of classification methods, and it is an important statistical measure of the performance of a binary classification test. It can formally be written as ACC=NT/N. Here, NT is the number of test data for which the predicted class for an example coincides with its true class, and N is the total number of test data.First, we consider a numerical example with synthetic data. In this example, we generate instances with two features (l=2) such that the second feature is unobserved. We generate 500 normally distributed random values for every feature with the expectations m1(-1)=4, m1(1)=6, m2(-1)=5, and m2(1)=10 and the standard deviations σ1=1 and σ2=3, respectively. We take identical standard deviations for both classes in order to simplify the example. Moreover, we state the lower and upper bounds for values of the second feature a2=4 and b2=14. Then we randomly select n=10 points (instances) with identical numbers of points (5) for both classes and get three training sets. The first and the second training sets are obtained in the following way. We generate the values of the second feature K=20 times for every example. In sum, we have 200 examples. At that, the values for the first training set are generated in accordance with the CDFs F~j(xj∣1) for the class y=1 and with the CDFs F~j(xj|-1) for the class y=-1. This training set corresponds to the minimax strategy. The values for the second training set are generated in accordance with the CDFs F^j(xj∣-1) for the class y=-1 and with the CDFs F^j(xj∣1) for the class y=1. The second training set corresponds to the minimin strategy. For getting the third training set, we replace all values of the second feature in the set of n=10 examples by the expectations m2(y) for y=-1 and y=1. Here, we use the available mean values of the second feature as values of the feature. We will call this strategy as direct for short. The initially generated 500 normally distributed random values will be used for testing resulting discriminant functions.The ACC measures and the discriminant functions for the above three training sets will be indexed by numbers 1, 2, and 3 corresponding to the minimax, minimin, and direct strategies, respectively.We will use the linear and RBF kernels with the parameterγ=1/l. By applying the above initial data, we get three discriminant functions corresponding to three strategies (minimax, minimin, and direct):
(47)f1(x)=-1.18x1+0.445x2+2.24,f2(x)=0.009x1-0.49x2+3.91,f3(x)=-0.00004x1-0.5x2+4.The corresponding ACCs for linear and RBF kernels are shown in Table1. One can see from the table that the optimistic and direct strategies provide better results in comparison with the minimax strategy. This can be explained by exploiting the normal distribution (symmetric and unimodal) with rather small standard deviations for generating the random values of the second feature.Table 1
The ACC measures for linear and RBF kernels by normally distributed values of features.
Linear kernel
RBF kernel
n
ACC1
ACC2
ACC3
ACC1
ACC2
ACC3
10
0.41
0.85
0.85
0.59
0.87
0.82We replace the normal distribution of the second feature values by the truncated exponential distribution with the CDF1-exp((x-a2)/m2(y)) if x<b2 and 1 if x≥b2. This distribution is not symmetric, and its mean value cannot replace the corresponding random values. By taking the linear and RBF kernels, n=10 and K=20, we get the following discriminant functions:
(48)f1(x)=-1.96x1+0.2x2+7.91,f2(x)=-0.09x1-0.47x2+4.2,f3(x)=-0.5x2+4.The corresponding ACCs for linear and RBF kernels are shown in Table2. It can be seen from the table that the minimax strategy provides better results. It follows from the fact that the minimax strategy takes into account the worst cases of the probability distribution of feature values. Of course, the exploited exponential distribution is not the worst case, but it is not the best case too. We can immediately observe that change for the worse of the probability distribution leads to improving the minimax strategy in comparison with the minimin and direct strategies.Table 2
The ACC measures for linear and RBF kernels by exponentially distributed values of the second feature.
Linear kernel
RBF kernel
n
ACC1
ACC2
ACC3
ACC1
ACC2
ACC3
10
0.63
0.61
0.59
0.65
0.65
0.62The proposed method has been evaluated and investigated by the following publicly available datasets: Iris, Pima Indian Diabetes, Mammographic Masses, Parkinsons, Indian Liver Patient, Breast Cancer Wisconsin (Original), Breast Cancer Wisconsin (Diagnostic), Musk, and Lung-Cancer. All datasets are from the UCI machine learning repository [28]. Table 3 is a brief introduction about these datasets, while more detailed information can be found from, respectively, the data resources.Table 3
A brief introduction about datasets.
Dataset
N
l
n
-
1
n
+
1
Iris
150
4
50
150
Pima Indian Diabetes
768
8
268
500
Mammographic Masses
961
4
445
516
Parkinsons
195
23
48
147
Breast Cancer Wisconsin (Original)
699
9
458
241
Breast Cancer Wisconsin (Diagnostic)
569
32
212
357
Musk
476
166
207
269
Indian Liver Patients
583
10
167
416
Lung-Cancer
32
57
9
23For all data, we use the repeated random subsampling validation procedure; that is, we randomly split the dataset into two subsets. One of them (training set havingn instances) is used to train the model while the other (test set having N-n instances) is used to validate the model. The number of instances for training will be denoted as n. Moreover, we take n/2 instances from every class for training. They are randomly selected from the classes. The remaining instances in the dataset are used for validation. The parameter of the RBF kernel γ for every dataset is chosen in order to maximize the accuracy measure. It is carried out by means of the following procedure. It is well known that letting the C and γ grow exponentially is a practical method to identify good parameters. An r×r uniform grid in the logarithmic coordinate space (C′=log2C, γ′=log2γ) is usually used. The point in the grid represents a parameter pair (C′,γ′). However, we fix the value of C=100 in order to reduce the number of experiments because our main aim is to compare the proposed models with known models. So, we perform experiments on a 13 uniform grid where γ′ has a range of 2-6,…,26.From every dataset, we randomly select a feature corresponding to missing values and compute its mean values for negative and positive labels, respectively. Moreover, we find the smallest and largest values of the selected feature which will be used for determining the lower and upper cumulative distribution functions. Then we generate the random values of the selected featureK=20 times for every instance. In sum, we have nK instances. The above procedure is repeated N=50 times such that the selected feature with missing values is chosen randomly in every iteration. In addition to the minimin (ACC1), minimax (ACC2), and direct (ACC3) strategies, we generate random values of the “missing” feature in accordance with the normal distribution and compute the corresponding accuracy measure ACC4. By using the RBF kernels and the cost parameter C=100, we get the ACC measures for different values of n, whose values are shown in Table 4. These measures are mean values of the corresponding ACCs computed for every iteration.Table 4
The ACC measures for real datasets by different values ofn.
Dataset
n
ACC1
ACC2
ACC3
ACC4
Iris
20
0.961
0.982
0.977
0.998
40
0.944
0.963
0.986
0.998
Pima
20
0.501
0.598
0.502
0.573
Indian Diabetes
40
0.532
0.655
0.590
0.621
Mammographic Masses
20
0.642
0.769
0.750
0.722
40
0.654
0.781
0.778
0.739
Parkinsons
20
0.567
0.721
0.706
0.637
40
0.56
0.721
0.713
0.644
Breast Cancer Wisconsin (Original)
20
0.885
0.923
0.937
0.963
40
0.832
0.919
0.815
0.962
Breast Cancer Wisconsin (Diagnostic)
20
0.820
0.835
0.885
0.921
40
0.785
0.851
0.825
0.926
Musk
20
0.565
0.648
0.625
0.629
40
0.606
0.678
0.689
0.658
Indian Liver
20
0.508
0.674
0.666
0.614
Patients
40
0.519
0.682
0.660
0.621
Lung-Cancer
12
0.647
0.709
0.693
0.637
16
0.666
0.679
0.637
0.786One can see from Table4 that the proposed minimax strategy (ACC2) outperforms the direct strategy and the normal distribution imputation procedure for some real datasets. Of course, there are datasets for which the measures ACC3 or ACC4 are larger than ACC2. If we have seen from the experiments with synthetic data that the minimax strategy provides better results when the distribution of the feature values is not symmetric and its mean value cannot replace the corresponding random values, then it is difficult to determine clear conditions of using the proposed model with real data. We can say that these conditions directly depend on a probability distribution of the feature values in real data. When we do not have this information, the proposed method should be used jointly with other models dealing with missing data.


## 8. Conclusion

A classification problem under partial information about some features in the form of conditional expectations or mean values of features for every class has been studied in the paper. Its solution is based on the pessimistic (minimax) and optimistic (minimin) decision strategies.What are the main advantages of the proposed method? First, the classification algorithm totally exploits the available information in the form of mean values of some features and the bounds of these features. At the same time, it does not employ any additional information which may be unjustified and incorrect. It does not use also additional assumption which may lead to incorrect prediction results. Second, the proposed method has a strong probabilistic background, and this fact allows us to use it in arbitrary applications where the initial information is scarce. Third, the method exploits the well-known minimax and minimin strategies which have a strong explanation. A cautious decision strategy as an intermediate case between pessimistic and optimistic strategies with a predefined caution parameter can also be studied in the same way. However, this is a direction for further research. Fourth, the method is reduced to the SVM. This fact allows us to simply construct nonlinear classification models by using suitable kernels. Fifth, the method allows us to reduce the classification problem to the standard form. This implies that a standard software can be applied for its implementation. The algorithm for computing the optimal parameters of every classification model can be easily implemented with standard functions of the statistical software package R or by using the well-known software library LIBSVM (a library for support vector machines) [37].The numerical examples have illustrated that the minimax classifiers can provide more accurate results in many cases in spite of their over-conservative decisions. At the same time, the given experiments can be viewed as a preliminary study of the proposed framework for applying the imprecise models to classification problems with missing values. An additional study has to be carried out in order to totally figure out when the proposed classifiers outperform the available classification models.One can also see from the paper that the Monte Carlo technique is a versatile tool for dealing with partial information. Various classification problems under different types of partial and unreliable information could be solved in the same way. A detailed analysis of the corresponding classification models is another direction for further research.At the same time, it is well known that one possible limitation of the Monte Carlo methods is the strong dependence of computational effort (proportional to the number of samplings). This implies that the learning of large datasets may lead to a hard computational problem. However, first of all, the minimax strategy should be used when the number of instances in training sets is rather small in order to provide the robust classification. When the training set consists of a large number of instances, other models might give better results. Second, variance reduction techniques can be applied to the classification procedures to decrease the computational effort. This is also a topic of further research.The proposed method can be also extended on the case of interval-valued mean values of unobserved features. In this case, the lower and upper CDFs are determined by the lower and upper mean values of features.



---

*Source: 176890-2013-04-15.xml*