Binary classification with ambiguous training data

Let $x\in\mathcal{X}$ be an input point and $y\in\mathcal{Y}=\{1,-1\}$ denote a binary label, which corresponds to the positive and negative classes, respectively. Suppose that we are given a set of positive and negative samples $\{(x_{i},y_{i})\}_{i=1}^{N}$ drawn independently from the probability distribution with density $p(x,y)$ defined on $\mathcal{X}\times\mathcal{Y}$. Let $h:\mathcal{X}\rightarrow\mathbb{R}$ denote a discriminant function, with which a class label is predicted for test input point $x$ as $\hat{y}=\mathop{\rm sign}\limits(h(x))$.

The goal is to train the discriminant function $h$ so that the expected misclassification rate is minimized. Let us define the 0-1 loss as

where $1_{A}$ is the indicator function that takes 1 if statement $A$ is true and 0 otherwise. Then, we can express this problem as

where $h^{*}$ denotes the optimal discriminant function and $\mathbb{E}_{p(x,y)}$ denotes the expectation over $p(x,y)$. In practice, since we do not know the true density $p(x,y)$, we usually use the empirical distribution to approximate the expectation:

Based on Eqs. (1) and (2), we can formulate various classification methods depending on loss functions (Sugiyama, 2015). In the rest of this section, we introduce the support vector machine (SVM) (Vapnik, 1995), which is one of the most basic algorithms of binary classification.

Because optimization with $L_{01}(h,x,y)$ is computationally intractable, it is not practical to optimize the empirical risk $\hat{R}(h)$ directly. To overcome this problem, the hinge loss, an upper bound of $L_{01}(h,x,y)$ called the hinge loss, defined by

has been introduced as its surrogate. Since the hinge loss is convex, optimization can be reduced to a convex program. Further introducing the L2 regularization, basis functions $\phi_{1}(x),\ldots,\phi_{N}(x)$, and slack variables $\xi=(\xi_{1},\ldots,\xi_{N})^{\top}$ with ^⊤ being the transpose, the following quadratic program can be obtained as a dual optimization problem:

where $w=(w_{1},\ldots,w_{N})^{\top}$ are the coefficients of the discriminant function, $\lambda>0$ is the L2 regularization parameter, and $h_{i}$ is the value of the discriminant function at sample point $x_{i}$ given by $h_{i}=\sum_{j=1}^{N}w_{j}\phi_{j}(x_{i})$. The resulting discriminant function is given by $h(x;\hat{w})=\sum_{j=1}^{N}\hat{w}_{j}\phi_{j}(x)$.

We consider three class labels, i.e,. positive, ambiguous, and negative: $y\in\mathcal{Y}_{0}=\{1,0,-1\}$. Suppose that we are given a set of positive, ambiguous, and negative samples $\{(x_{i},y_{i})\}_{i=1}^{N}$ drawn independently from the probability distribution with density $p_{0}(x,y)$ defined on $\mathcal{X}\times\mathcal{Y}_{0}$. Our goal is still to learn a discriminant function that classifies test samples into either the positive or negative class (not in the ambiguous class). Our key question in this scenario is if we can utilize the ambiguous training data to improve the classification accuracy of the discriminant function.

In this section, we develop a new method based on a method of classification with reject option (CRO) (Cortes et al., 2016). For this reason, before deriving the new method, we first review the CRO method.

Cortes et al. (2016) introduced a rejection function $r:\mathcal{X}\rightarrow\mathbb{R}$ to identify the regions with high risk for misclassification, in addition to discriminating the positive and negative classes. When the rejection function takes a positive value, the corresponding sample is accepted and is classified into the positive or negative class by classifier $h$; otherwise, the sample is rejected and is not classified. When a sample is rejected, the rejection cost $c$ is incurred, which trades off the risk of misclassification and the cost of rejection. To realize this idea, the 0-1-c loss was introduced:

When $c=0$, all samples are rejected because the loss function does not incur any cost. On the other hand, when $c\geq 0.5$, no samples are rejected because the expectation of the 0-1 loss is less than $0.5$; in that case, the 0-1-$c$ loss is reduced to the 0-1 loss. Therefore, effectively, we only consider $c$ such that $0<c<0.5$. The rejection function and the discriminant function are simultaneously learned from training data.

Similarly to the 0-1 loss, the 0-1-$c$ loss has discrete nature and thus its direct optimization is computationally intractable. To avoid the discontinuity, the following surrogate loss called the max-hinge (MH) loss was introduced:

where $\alpha,\beta>0$ are the hyperparameters to control the shape of the surrogate loss.

In the same manner as the original SVM, introducing the L2 regularization, basis functions, and slack variables yields the following quadratic program:

where $w=(w_{1},\ldots,w_{N})^{\top}$ are the coefficients of the discriminant function, $u=(u_{1},\ldots,u_{N})^{\top}$ are the coefficients of the rejection function, $\lambda,\lambda^{\prime}>0$ are the L2 regularization parameters, and $h_{i}$ and $r_{i}$ denote the values of the discriminant function and rejection function at sample point $x_{i}$ given by $h_{i}=\sum_{j=1}^{N}w_{j}\phi_{j}(x_{i})$ and $r_{i}=\sum_{j=1}^{N}u_{j}\phi_{j}(x_{i})$, respectively. The resulting discriminant function and rejection function are given by $h(x;\hat{w})=\sum_{j=1}^{N}\hat{w}_{j}\phi_{j}(x)$ and $r(x;\hat{u})=\sum_{j=1}^{N}\hat{u}_{j}\phi_{j}(x)$.

We refer to this method as CRO-SVM.

To handle ambiguous training data in the SVM formulation, we extend the 0-1-$c$ loss to the 0-1-c-d loss defined as

Table 3 and Table 3 compare the behavior of the 0-1-$c$ loss and the 0-1-$c$-$d$ loss. For positive and negative samples, the 0-1-$c$-$d$ loss behaves the same as the 0-1-$c$ loss. On the other hand, for ambiguous samples, the 0-1-$c$-$d$ loss incurs penalty $d$ when they are classified into the positive or negative class. Therefore, ambiguous samples tend to be classified into the ambiguous class if we employ the 0-1-$c$-$d$ loss. Compared to the CRO formulation, where a rejector cannot be learned explicitly from positive and negative samples, the CAD utilizes ambiguous samples to learn a rejector explicitly.

The above discussion may mislead us as if we are just solving a 3-class problem with the positive, ambiguous, and negative classes. However, we do not classify test samples into the ambiguous class, but only into the positive and negative classes. To solve the CAD problem, we utilize a binary discriminant function $h$ and a rejection function $r$, as in the CRO formulation reviewed above. More specifically, we train $h$ and $r$ under the 0-1-$c$-$d$ loss, and we only use $h$ in the test phase to classify test samples into the positive and negative classes. Thanks to the interplay between $h$ and $r$ in the 0-1-$c$-$d$ loss, we can utilize ambiguous data to train $h$ through $r$.

Similarly to the 0-1-$c$ loss, we consider the following convex upper bound of the 0-1-$c$-$d$ loss called the max-hinge-ambiguous (MHA) loss as a surrogate to avoid its discrete nature:

where $\eta\geq 1$ is the hyperparameter to control the shape of the surrogate loss. See Figure 1 for its visualization.

Then, in the same way as the CRO-SVM, we have the following quadratic program:

This is our proposed method called CAD-SVM. The computational complexity of the CAD-SVM depends on implementation of the quadratic program. It naively costs $O(N^{3})$, but if we use a fixed number of basis functions, the complexity reduces to $O(N)$.

The MHA loss depends on the choice of hyperparameters $(\alpha,\beta,\eta)$. To find good hyperparameter values, let us analyze the 0-1-$c$-$d$ loss first.

For each $x\in\mathcal{X}$, let $\pi_{+}(x)=p_{0}(y=1|x)$, $\pi_{0}(x)=p_{0}(y=0|x)$, and $\pi_{-}(x)=p_{0}(y=-1|x)$, where $\pi_{+}(x)+\pi_{0}(x)+\pi_{-}(x)=1$. Then the following lemma shows how $c$ and $d$ are related to $\pi_{+}(x)$ and $\pi_{-}(x)$ for the optimal classifier and rejector (its proof is available in Appendix A):

Figure 2 illustrates the above results. This shows that when $\pi_{+}$ (or $\pi_{-}$) is large (i.e., imbalanced classification), the rejector accepts the sample and the classifier classifies that sample into the positive (or negative) class. On the other hand, when both $\pi_{+}$ and $\pi_{-}$ are not so large, the rejector rejects the sample.

Next, based on the above lemma, we have the following theorem for the MHA loss (its proof is given in Appendix B):

Based on the above theorem, we use Eq. (22) as hyperparameter values in our experiments in the next section and demonstrate that they work well in practice. Nevertheless, given that the above theorem is valid only for the optimal solutions, we may cross-validate better hyperparameter values around Eq. (22) to further improve the classification performance. Note that Eq. (22) does not include $d$.

For experiments, we use a toy dataset, a public dataset, and an in-house dataset.

Using the above datasets, we compared the classification performance of the SVM, the SVM-RL (random label), the LapSVM (Belkin et al., 2006), the two-step SVM, the CRO-SVM, the CRO-SVM-RL, and the CAD-SVM. The SVM-RL employs the SVM algorithm, but ambiguous samples are randomly relabeled as positive or negative, which effectively utilizes information of the ambiguous samples. The LapSVM is a semi-supervised learning method based on the SVM, which employs a regularization term defined by the graph Laplacian. Ambiguous samples are treated as unlabeled samples in the LapSVM. The two-step SVM is the method which learns the rejection function and the discriminant function sequentially—first the rejection function is learned to judges whether the sample is ambiguous or not, and then the discriminant function is learned only using the samples which are not rejected by the rejection function. When the rejection function is learned, class weights $c$ and $d$ are applied to non-ambiguous (i.e., positive and negative) and ambiguous samples, respectively. The CRO-SVM-RL is the CRO-SVM with random labels for ambiguous samples in the same manner as SVM-RL.

For each method, 500 test runs were performed by changing the training and test datasets which were randomly divided from the original dataset. The dividing ratio of the training and test dataset was 4:1 for the ID dataset and 1:2 for the other datasets. For each test run, 5-fold cross validation was performed to determine the parameters below. For validation and in the test phase, only positive and negative samples were applied to the discriminant function, thus we were able to evaluate the binary classification accuracy.

Note that our goal was to maximize the binary classification accuracy in the test phase, and that was equivalent to minimizing the expected 0-1 loss. Though we trained the models using various loss functions such as the hinge loss, the MH loss, and the MHA loss, the 0-1 loss was minimized by cross validation.

In total, we had 10 hyperparameters $(\lambda,\lambda^{\prime},\sigma,\sigma^{\prime},\tau,c,d,\alpha,\beta,\eta)$, where $(\lambda,\lambda^{\prime})$ were the L2 regularization parameters, $\sigma$ was the width of the Gaussian radial basis function in the basis functions $\phi_{i}(x)=\exp\left(-\frac{\|x-x_{i}\|^{2}}{2\sigma^{2}}\right)$, $\sigma^{\prime}$ was the hyperparameter of the weight matrix $W$ of the graph Laplacian as $W_{ij}=\exp\left(-\frac{\|x_{i}-x_{j}\|^{2}}{2\sigma^{\prime 2}}\right)$ (only in the LapSVM), $\tau$ was the coefficient of the graph Laplacian regularization (only in the LapSVM), $(c,d)$ were the hyperparameters of the 0-1-$c$ loss (in the CRO-SVM and CRO-SVM-RL), the 0-1-$c$-$d$ loss (in the CAD-SVM) or the class weights (in the two-step SVM), and $(\alpha,\beta,\eta)$ were the hyperparameters of the MH and MHA loss functions (in the CRO-SVM, CRO-SVM-RL and CAD-SVM). We used 5-fold cross validation in terms of the classification accuracy to choose the hyperparameters from $(\lambda,\lambda^{\prime})\in\{10^{-3},10^{-5},10^{-7}\}$, $(\sigma,\sigma^{\prime})\in\{10^{0.5},10^{0.75},10^{1}\}$, $\tau\in\{10^{-1},10^{-2},10^{-3}\}$, $c\in\{0.03,0.06,0.20,0.45\}$, and $d\in\{0.03,0.06,0.20,0.50\}$. The other hyperparameters $(\alpha,\beta,\eta)$ were determined by Eq. (22). Quadratic programming problems were solved using cvxopt (Andersen et al., 2018).

Figure 5 shows an example of the discriminant results for the toy dataset with $r=0.5$. The upper half of the domain was the mixed region of positive and negative samples and samples in that region were expected to be classified into the ambiguous class. On the other hand, the lower half of the domain was perfectly separable into the positive and negative regions and samples in those regions were expected to be discriminated accurately (see Figure 3). The SVM made some misclassifications in the lower half of the domain, which were caused by the mixed region. The SVM-RL and LapSVM could not reduce the number of misclassifications, though they utilized information of ambiguous samples. This suggests that ambiguous samples should not be simply relabeled to positive or negative samples or should not be treated as unlabeled samples. The two-step SVM could not also reduce the number of misclassifications and it could not learn the ambiguous region. Thus, it would be disadvantageous to learn the ambiguous region by combining positive and negative classes. The CRO-SVM and CRO-SVM-RL successfully learned the ambiguous region but that did not lead to learning more accurate discriminant functions. The CAD-SVM also successfully learned the ambiguous region and then it was able to learn a more accurate discriminant function. Overall, the CAD-SVM was shown to be the most appropriate method in this toy experiment.

Tables 4 shows the test accuracy of the toy dataset by changing the parameters $r$ which are the propotion of ambiguous samples in the mixed region. When the proportion of the ambiguous samples was small, the proposed method did not work effectively since the number of ambiguous samples was too small. On the other hand, when the proportion of the ambiguous samples was large, it also did not show better performance. This was because, under this condition, only small numbers of positive and negative samples existed in the mixed region. Therefore, methods which do not utilize ambiguous samples showed reasonably good enough performance. However, when the proportion of ambiguous samples was $r=0.5$, the CAD-SVM achieved a better score than the other methods.

Table 5 summarizes the test accuracy of each method for the PD1, PD2, PD3, and ID datasets, respectively. For the PD1 dataset, the CAD-SVM was not superior to other methods since this condition was similar to the toy dataset with higher $r$. For the PD2 dataset, though the dataset had a mixed region, the CAD-SVM also did not show good performance. However, for the PD3 dataset, which had a mixed region and a separable region, the CAD-SVM achieved the best performance among the compared methods. It is suggested that our proposed method, the CAD-SVM, works effectively when the dataset has both of a mixed region and a separable boundary between the positive and negative classes. The CAD-SVM utilizes ambiguous samples to learn a rejector which rejects mixed regions, thus it would be able to focus on learning a separable region. The CRO-SVM and the CRO-SVM-RL also learn a rejector from positive and negative samples, but the CAD-SVM would be superior since the CAD-SVM can explicitly learn a rejector using ambiguous samples. For the ID dataset, the CAD-SVM performed better than the other method, except for the CRO-SVM-RL. Overall, ambiguous samples can improve the binary classification accuracy under some conditions, and the CAD-SVM is one of the solutions that can utilize such ambiguous samples.

Through all the experiments, the CRO-SVM-RL gave as good performance as the CAD-SVM. As detailed in Appendix C, we can show the following relations between the CRO-SVM-RL and the CAD-SVM:

1. 1.

   The 0-1-$c$ loss function for the randomly labeled (RL) dataset, in which we randomly relabeled ambiguous samples as positive or negative, reduces to the 0-1-$c$-$d$ loss with $d=\frac{1}{2}-c$.

2. 2.

   For the RL dataset, the MH loss can be regarded as a surrogate loss of the 0-1-$c$-$d$ loss with $d=\frac{1}{2}-c$, and it is calibrated under the conditions of Eq. (22).

Thus, though it is a simple heuristic, the CRO-SVM-RL is essentially equivalent to the CAD-SVM except for that the hyperparameter $d$ is fixed to $\frac{1}{2}-c$. In practice, the CRO-SVM-RL is easier to implement and thus it may be used as an alternative to the CAD-SVM. However, we note that the CRO-SVM-RL alone does not provide rich theoretical insights that we have shown in Section 3.

Our goal for each experiment was minimizing the expected 0-1 loss in the test phase. Therefore, the SVM was naively an appropriate method since the hinge loss was calibrated to the 0-1 loss. Nevertheless, though the CRO-SVM-RL and the CAD-SVM minimized a surrogate of the 0-1-$c$-$d$ loss in the training phase, they were able to achieve the better accuracy than the SVM in the test phase. It is suggested that the providing a reject option and incorporating ambiguous training samples could work as a kind of regularization, but further studies will be needed to clarify its mathematical properties.

We note that ambiguous samples are intrinsically hard-to-label samples even by experts, so they usually contain little information for classifying positive and negative samples, and thus we cannot expect large improvement to the binary classification accuracy. Nevertheless, our proposed method achieved statistically significant improvements for some cases.