A graphical approach for multiclass classification and for correcting the labeling errors in mislabeled training data

Abstract

Multiclass data classification, where the goal is to segment data into classes, is an important task in machine learning. However, the task is challenging due to reasons including the scarcity of labeled training data; in fact, most machine learning algorithms require a large amount of labeled examples to perform well. Moreover, the accuracy of a classifier can be dependent on the accuracy of the training labels which can be corrupted. In this paper, we present an efficient and unconditionally stable semi-supervised graph-based method for multiclass data classification which requires considerably less labeled training data to accurately classify a data set compared to current techniques, due to properties such as the embedding of data into a similarity graph. In particular, it performs very well and more accurately than current approaches in the common scenario of few labeled training elements. Morever, we show that the algorithm performs with good accuracy even with a large number of mislabeled examples and is also able to incorporate class size information. The proposed method uses a modified auction dynamics technique. Extensive experiments on benchmark datasets are performed and the results are compared to other methods.

Keywords

Data classification graphical setting optimization auction dynamics mislabeled data

1. Introduction

Data classification, where the goal is to divide unlabeled examples into several classes with the aid of labeled data, is an important task in machine learning. However, data classification is challenging for many reasons, including the scarcity of labeled training data. In fact, one of the key limitations of most current approaches for the classification task is their reliance on large labeled training sets for good performance. In particular, many modern machine learning techniques, such as neural networks and support vector machines (e.g. [1, 2, 3]), require large amounts of labeled data to perform well [4]. The state-of-the-art deep learning techniques, such as convolutional neural networks (e.g. [5, 6, 7]), have millions of free parameters and thus require even more labeled training data. However, obtaining labeled data is time-consuming and expensive, especially in domains where only experts can determine labels.

Moreover, data classification can be challenging since the labels of the training data can be corrupted, affecting the classification accuracy. This can occur in practice for many reasons. For example, a data-entry error can be made. Moreover, there might not be enough information to label each instance. In addition, subjectivity in labeling can arise in domains in which experts disagree. Thus, it is crucial to use a classifier which tolerates label noise well and to find a way to identify or correct the errors in labels.

In this paper, we present an efficient and unconditionally stable semi-supervised graph-based algorithm for data classification, derived using upper and lower bound auction dynamics. The method requires considerably less labeled training data to accurately classify a data set compared to current techniques; in particular, it performs very well and more accurately than current approaches in the common scenario of few labeled training elements. The approach can also incorporate class size information, which can increase the classification accuracy. Moreover, the method handles label noise in the training data well and is able to perform with good accuracy even with many errors in the labels of the training data. It is important to note that while noise in the training data can occur in the attribute (feature) information of the data as well as the training labels, in this paper, we focus on the noise in the training labels. The case of noise in the attribute information is the subject of another paper; however, in Section 4.5, we include two experiments where noise is introduced in the attribute (feature) information.

The ability of the proposed algorithm to perform well with small labeled training sets will be due to several properties: (i) The embedding of data into a weighted similarity graph, which provides information about the extent of similarity between elements of data (including unlabeled data) and also about the overall structure of the data. (ii) The in-depth construction of the weights in the graph; for example, in the case of text classification, we use a pairwise document similarity measure based on present term set. (iii) The usage of both the unlabeled data and scarce labeled data to construct the graph; this allows one to leverage important structural information of the unlabeled data. (iv) The incorporation of random fluctuations of variables for reaching even lower energies. (v) The ability to incorporate class size information, in the form of upper and lower bounds on the class sizes, which improves accuracy even further.

Main contributions

(1)
We present a multiclass data classification method, Algorithm 1, with several advantages:

–
The method is very efficient and unconditionally stable.
–
The algorithm requires considerably less labeled training data to accurately classify a data set compared to current machine learning techniques; in particular, it performs very well and more accurately than current approaches in the common scenario of few labeled training elements.
–
Moreover, the method handles mislabeled training data well and performs with good accuracy even in the case of a lot of mislabeled training instances.
–
Our algorithm is able to incorporate class size information in form of upper and lower bounds on the class sizes. The latter property is favorable since this kind of information is often available.

(2)
We elaborate on the stability of the proposed algorithm with respect to mislabeled training data. There are several properties of the method, discussed in Section 3.3, which allow the algorithm to perform well even with large amounts of mislabeled training data. We also perform extensive numerical experiments to show that the proposed algorithm can still perform with good accuracy even with many mislabeled training examples. Moreover, we present a technique, based on the market mechanism and detailed as Algorithm 2, to identify and correct mislabeled training elements.
(3)
A detailed discussion of the upper and lower bound auction technique for class-size constrained multiclass data classification is presented.
(4)
We perform extensive experiments on eight benchmark data sets:

–
The $1^{\text{rst}}$ set of experiments consists of varying the number of labeled examples.
–
The $2^{\text{nd}}$ set of experiments consists of corrupting the labels of varying amounts of training data.
–
The $3^{\text{rd}}$ set of experiments includes applying the proposed technique in point (2) to identify and correct mislabeled training data.

The paper is organized as follows. In Section 2, we review background and previous work. In Section 3, we present the proposed method and theory on the auction dynamics technique for class-size constrained multiclass data classification, as well as elaborate on the stability of the proposed method with respect to mislabeled training data. We also introduce a procedure for identifying and correcting mislabeled training data. Section 4 presents extensive numerical experiments. We conclude in Section 5.

This work further extends our paper [8]. Specifically, we provide much more details of the theory of auction dynamics technique for class-size constrained multiclass data classification; in particular, we include proofs for several unjustified statements in [8]. Moreover, we perform extensive experiments over many more data sets, including images and text/webpage data, to validate the proposed method. In addition, we provide a thorough comparison of our algorithm to some of the best recent methods. We also elaborate on the stability of the proposed method with respect to mislabeled training data, and perform extensive experiments where different amounts of the training labels are corrupted. Lastly, we propose a technique to identify and correct the corrupted labels of the training data using a market mechanism.
2. Background and previous work

2.1 Graphical framework

Our method involves the graphical framework, where we consider a weighted graph $G=(V,E)$ , consisting of vertices $V$ and edges $E$ , with vertices representing the elements of the data. The edges are weighted by a weight function $w:V\times V\rightarrow\mathbb{R}$ , a symmetric function where the entry $w(x,y)$ measures the degree of similarity of $x$ and $y$ ; a small weight is assigned to edges connecting dissimilar vertices.

The use of the graphical framework offers many advantages. First, it provides information about the extent of similarity between elements of data and the overall structure of the data. It also provides a way to handle nonlinearly separable classes and affords the flexibility to incorporate diverse types of data.

The weight function is computed using the attribute information for each instance in the data set. For example, for image data sets, the attributes contain information about the pixel intensity. For classifying text data, the weight function can be computed using a pairwise document similarity measure [9].

In this paper, we begin by constructing the weight function by connecting each data instance to its $l$ nearest neighbors using a distance measure; therefore, the weight $w(x,y)$ is 0 unless $x$ and $y$ are $l$ nearest neighbors. The non-zero weight values are computed using the Zelnik-Manor and Perona weight function [10], a scaled Gaussian function with values in (0, 1]. The diagonal elements of $W$ are set to 1. Since this does not guarantee that the weight matrix $W=\{w(x,y)\}$ is positive semi-definite, one can consider the weight matrix $W^{t}W$ , where $W^{t}$ indicates the transpose of $W$ . Since the parameter $l$ used is small compared to the size of the matrix, $W^{t}W$ still results in a matrix with many zero entries, although it has more nonzero entries in general than $W$ . Even though the diagonal entries of $W^{t}W$ are in general larger than those of $W$ , there are more nonzero entries in the former matrix in general, which allows for the auction coefficients in our auction dynamics to accurately depict the structure in our data set.

The value of parameter $l$ used depends on the data set. Experimentally, we found that using $15\leqslant l\leqslant 40$ usually works best, with a slight decrease in accuracy for higher or lower $l$ .

2.2 Previous work

2.2.1 Data classification methods

Since our method is graph-based, we first briefly review some recent graph-based multiclass data classification approaches; a broad survey of such algorithms is provided in [11]. In [12], the authors introduce several algorithms derived from variational models for semi-supervised clustering of high-dimensional data, posed as a minimization of a convex functional of the labeling function. The work [13] presents a transductive version of the $l$ nearest-neighbor classifier. In addition, the papers [14, 15, 16, 17] describe classification methods formulated using the Ginzburg-Landau functional. While [18, 19] involve relaxations of the Cheeger cut problem, [20, 21] present efficient approaches to multiclass total variation clustering. Moreover, in [22], the authors propose a general regularization framework with applications to classification, ranking and link prediction problems, and [23] introduces a method to obtain a smooth solution of a classifying function for semi-supervised learning. We conclude with [24], which describes a propagation algorithm for minimizing a cost function and a binary label matrix.

Many other data classification algorithms have been proposed. Among the most popular approaches are associated with deep learning. Some examples include convolutional neural networks (CNN), described in works such as [25], which explores network structure optimization, and [26], which details a weighted pooling approach for image recognition using deep convolutional neural networks. Another example is LeNet-5 [27], which is a CNN designed for handwritten and machine-printed character recognition. The work [28] explores the applicability of deep learning approaches to medical imaging.

Neural networks and support vector machines have also been widely used for classification purposes. Examples of neural network approaches include [29], which details shallow, two-layer networks that are trained to reconstruct linguistic contexts of words and use Word2Vec. The work [30] compares the accuracy of the two neural networks with respect to training data set size. Examples of support vector machines used for text classification include [31, 32].

Other approaches include successive subspace learning [33], scattering operators [34], semi-supervised classification trees [35], continual learning [36]. The work [37] details an algorithm that exploits only the titles and categories of Wikipedia articles for classification purposes.

The experiment section of this paper will compare the classification accuracy of the proposed approach with many of the aforementioned approaches using different kinds of data sets, such as images and text, and different amounts of labeled training data and training label noise.

2.2.2 Approaches for handling mislabeled training data

We now describe previous studies about handling mislabeled training data divided into: local learning-based methods, ensemble learning-based techniques and single learning-based algorithms [38].

Local learning-based methods are algorithms which consider an instance as mislabeled if the class of that instance differs from the classes of the neighbors of the node. In other words, local learning-based techniques make the assumption that instances that are close to each other tend to be assigned to the same class. Of course, defining the neighborhood and the distance function is a challenge for these kinds of methods. One example of a local learning-based technique is edited nearest neighbor (ENN) [39, 40], which eliminates all entries from the training data that are misclassified by the $l$ nearest neighbor algorithm. The ANN technique [41] uses aspects of ENN, but increases $l$ after each iteration. The multiedit algorithm [42] utilizes the holdout. Other examples of local learning-based methods include the modified ENN [43], the nearest centroid neighbor [44] and the relative neighborhood graph [45].

Ensemble learning-based approaches use independent classifiers to tag mislabeled data. Specifically, they consider a training example as mislabeled if it is defined so by several independent classifiers. Two ensemble approaches are majority vote and consensus vote classifiers [46, 47]. In the case of a majority vote ensemble approach, a training example needs to be considered mislabeled by a majority of the classifiers for it to be eliminated from the training data. Consensus vote ensemble techniques differ from majority vote ones, because they require that the instance be considered mislabeled by all the classifiers for it to be eliminated. Another type of ensemble learning-based methods are data variation techniques which do not use multiple various learning classifiers and instead apply multiple training sets to the same algorithm. Some examples include cross-validated committees [48], bagging [49, 50] and boosting [51].

Single learning-based methods employ the use of a single classifier to detect mislabeled data. Two popular single learning-based algorithms are based on decision trees and neural networks [38]. The robust-C4.5 algorithm [52] detects mislabeled training data based on the conventional C4.5 method [53], which is one of the most popular decision tree algorithms. The method successively builds trees, prunes the trees and then removes training examples if they are misclassified by the pruned trees. The process stops when no more training instances are removed. Another single learning-based approach is based on a framework of multi-layer artificial neural networks. Automatic noise reduction [54] assigns each training example a class probability vector. The vector is updated based on its difference from the network output. After enough training, the mislabeled training element’s label will be changed to the correct one. The training data whose classes have been changed is then removed.

Some specific algorithms we will be comparing our proposed method to in terms of robustness towards noisy labels include neural networks with bootstrapping [55], stream-based active learning [56], an adversarial regularization scheme based on the Wasserstein distance [57], Credal C4.5 model [58], regularized root-quartic mixture of experts model [59], an anti-noise multi-task multi-view algorithm AN-MTMVCSF [60] and a method using a bandit framework [61].

3. Modified auction dynamics for multiclass classification

In this section, we provide details about our auction dynamics approach to multiclass data classification. This extends our previous work [8], and we include much more details and proofs about the theory for applying auction dynamics to class-size constrained multiclass data classification. In particular, we prove several unjustified statements in [8]. Moreover, extensive experiments on many more different types of data sets are performed, including data sets comprised of text and webpage data as well as images. In addition, a thorough comparison to some of the best recent methods is presented. We also elaborate on the stability of our method with respect to mislabeled training data, and perform extensive experiments where certain portions of the training labels are corrupted. Moreover, we propose and apply a technique to identify and correct the mislabeled labels of the training data using a market mechanism.

3.1 Notation

The classification problem of our paper is: given a data set $V$ of $n$ elements, consisting of unlabeled testing data $T$ and labeled training data $R=\cup R_{i}$ , where $R_{i}$ is the set of labeled examples for class $i$ , the goal is to correctly assign the points in the testing data into one of the $N$ classes. At the end, one obtains a partition $\mathbf{\Sigma}=(\Sigma_{1},\ldots,\Sigma_{N})$ of $V=R\cup T$ , where $\Sigma_{i}$ is the set of points assigned to class $i$ .

To incorporate class size information, we impose constraints in our procedure. In particular, let $L_{i}$ and $U_{i}$ be the upper and lower bounds on class $i$ of $T$ .

3.2 Derivation of the algorithm

We start the derivation of our algorithm by considering the problem of minimizing the graph cut with class size constraints and labeled data constraints, with $\{w(x,y)\}$ indicating the graph weights:

$\displaystyle\text{argmin}_{\Sigma}\frac{1}{2}\sum_{i=1}^{N}\sum_{x\in\Sigma_{% i}}\sum_{y\notin\Sigma_{i}}w(x,y)\quad\text{s.t.}\quad R_{i}\subset\Sigma_{i},% \quad L_{i}\leqslant|\Sigma_{i}|\leqslant U_{i}\quad\forall i,$ (1)

which penalizes partitions of the data that place strongly connected points in different classes.

Equation (1) is difficult as it is NP-hard, so we consider a convex relaxation of the graph cut Eq. (1) called the graph heat content (GHC):

$\displaystyle\text{argmin}_{\bm{u}\in\mathcal{K}_{N}}\left\{\textrm{GHC}=\sum_% {i=1}^{N}\sum_{x,y\in V}w(x,y)u_{i}(x)(1-u_{i}(y))\right\}\quad\text{s.t.}% \quad\forall i,$ (2) $\displaystyle L_{i}\leqslant\sum_{x\in T}u_{i}(x)\leqslant U_{i}\quad\text{and% }\quad u(x)=e_{i}\quad\forall x\in R_{i},$

where $\@setsize{\small}{11pt}{\xpt}{\@xpt}\mathcal{K}_{N}=\{\bm{u}:V\to[0,1]^{N}:% \sum_{i=1}^{N}u_{i}(x)=1\}$ and $e_{i}$ is an indicator vector of size $N$ . Here, the label information is included in the last constraint, and the optimal $u_{i}(x)$ represents the probability that $x$ belongs to class $i$ . After an optimal $\bm{u}$ has been obtained, a partition $\@setsize{\small}{11pt}{\xpt}{\@xpt}\Sigma=\{\Sigma_{1},\Sigma_{2},\ldots,% \Sigma_{N}\}$ of $V$ can be derived from $\bm{u}$ by: $\@setsize{\small}{11pt}{\xpt}{\@xpt}\Sigma_{i}=\{x\,\textrm{s.t.}\,\text{% argmax}_{j}u_{j}(x)=i\}$ .

It turns out that if the weight matrix $W=\{w(x,y)\}$ is positive semi-definite, GHC Eq. (3.2) is concave, which is a property that will be useful for later propositions. We prove this property:

.

If the matrix $W=\{w(x,y)\}$ is positive semi-definite, GHC Eq. (3.2) is concave.

Proof..

We need to show that, if $W=\{w(x,y)\}$ is a positive semi-definite matrix (i.e. satisfies the property that $zWz^{t}\geqslant 0$ for any vector $z$ , where $z^{t}$ indicates the transpose of $z$ ), for any $\bm{u},\bm{v}:\mathcal{V}\to\mathcal{K}_{N}$ and $0\leqslant\lambda\leqslant 1$ ,

$\displaystyle\lambda\textrm{GHC}(\bm{u},W)+(1-\lambda)\textrm{GHC}(\bm{v},W)% \leqslant\textrm{GHC}(\lambda\bm{u}+(1-\lambda)\bm{v},W).$ (3)

The positive semi-definite condition of $W$ is equivalent to the following property for any $z$ :

$\displaystyle\sum_{x,y}z(x)w(x,y)z(y)\geqslant 0,$ (4)

where $z(x)$ denotes the value of the $x^{\text{th}}$ coordinate of $z$ .

The left side of Eq. (3) can be expressed as:

$\displaystyle\lambda\textrm{GHC}(\bm{u},W)+(1-\lambda)\textrm{GHC}(\bm{v},W)=% \lambda\sum_{i}\sum_{x,y}w(x,y)u_{i}(x)(1-u_{i}(y))$ $\displaystyle\quad{}+(1-\lambda)\sum_{i}\sum_{x,y}w(x,y)v_{i}(x)(1-v_{i}(y))$ (5) $\displaystyle=\sum_{i}\sum_{x,y}w(x,y)[\lambda u_{i}(x)-\lambda u_{i}(x)u_{i}(% y)+(1-\lambda)v_{i}(x)-(1-\lambda)v_{i}(x)v_{i}(y)].$

The right side of Eq. (3) can be expressed as:

$\displaystyle\textrm{GHC}(\lambda\bm{u}+(1-\lambda)\bm{v},W)=\sum_{i}\sum_{x,y% }w(x,y)[\lambda u_{i}(x)+(1-\lambda)v_{i}(x)][1-\lambda u_{i}(y)-(1-\lambda)$ $\displaystyle v_{i}(y)]=\sum_{i}\sum_{x,y}w(x,y)[\lambda u_{i}(x)+(1-\lambda)v% _{i}(x)-\lambda^{2}u_{i}(x)u_{i}(y)-\lambda(1-\lambda)u_{i}(y)v_{i}(x)$ (6) $\displaystyle-\lambda(1-\lambda)u_{i}(x)v_{i}(y)-(1-\lambda)^{2}v_{i}(x)v_{i}(% y)].$

Therefore,

$\displaystyle\textrm{GHC}(\lambda\bm{u}+(1-\lambda)\bm{v},W)-\lambda\textrm{% GHC}(\bm{u},W)-(1-\lambda)\textrm{GHC}(\bm{v},W)$ $\displaystyle=\sum_{i}\sum_{x,y}w(x,y)[\lambda u_{i}(x)u_{i}(y)+(1-\lambda)v_{% i}(x)v_{i}(y)-\lambda^{2}u_{i}(x)u_{i}(y)-\lambda(1-\lambda)u_{i}(y)v_{i}(x)-$ $\displaystyle-\lambda(1-\lambda)u_{i}(x)v_{i}(y)-(1-\lambda)^{2}v_{i}(x)v_{i}(% y)]=\sum_{i}\sum_{x,y}w(x,y)\lambda(1-\lambda)[u_{i}(x)u_{i}(y)$ (7) $\displaystyle+v_{i}(x)v_{i}(y)-u_{i}(y)v_{i}(x)-u_{i}(x)v_{i}(y)]=\lambda(1-% \lambda)\sum_{i}\sum_{x,y}w(x,y)[(u_{i}(x)-v_{i}(x))$ $\displaystyle(u_{i}(y)-v_{i}(y))]\geqslant 0,$

where the last inequality uses the fact that $W$ is positive semi-definite and $z=u-v$ in Eq. (4).

Since Eq. (3.2) shows that

$\displaystyle\textrm{GHC}(\lambda\bm{u}+(1-\lambda)\bm{v},W)-\lambda\textrm{% GHC}(\bm{u},W)-(1-\lambda)\textrm{GHC}(\bm{v},W)\geqslant 0,$ (8)

we have proven Eq. (3). ∎

Since the GHC in Eq. (3.2) is concave if the weight matrix $W$ is a positive semi-definite matrix, successively minimizing linearizations of Eq. (3.2) will dissipate the energy. Therefore, our approach to the graph-based classification Eq. (3.2) with class size constraints is to obtain a graph Merriman-Bence-Osher (MBO)-like scheme Eq. [62], in the spirit of Eq. [63] in a continuous setting, by successively minimizing linearizations of GHC Eq. (3.2), with the additional constraint that the size of each class must stay between upper and lower bounds.1

The scheme resembles the one introduced by Merriman, Bence and Osher in [62], which generates an approximation to mean curvature motion by alternating between two simple steps: convolution with a kernel and pointwise thresholding. Since the original paper, threshold dynamics and mean curvature motion have been studied extensively in [64, 65, 66, 67, 68, 69, 70, 71, 72]. A generalization to curvature motion of a multiphase network is described in [63, 73, 74, 75].

This results in the following optimization scheme we consider for obtaining a sequence of partitions

\{\Sigma^{1},\Sigma^{2},\ldots\}

of the data set

V

, converging to a partition that is optimal:

$\displaystyle\begin{cases}\bm{u}^{k+1}=\text{argmin}_{\bm{u}\in\mathcal{K}_{N}% }\mathcal{L}(\bm{u},\bm{u}^{k})\quad\text{s.t.}\quad\forall i,\quad L_{i}% \leqslant\sum_{x\in T}u_{i}(x)\leqslant U_{i},\\ \quad\text{and}\quad u(x)=e_{i}\quad\forall x\in R_{i},\\ \Sigma_{i}^{k+1}=\{x\,\textrm{s.t.}\text{argmax}_{j}u_{j}^{k+1}(x)=i\},\end{cases}$ (9)

where $\@setsize{\small}{11pt}{\xpt}{\@xpt}\mathcal{K}_{N}=\{\bm{u}:V\to[0,1]^{N}:% \sum_{i=1}^{N}u_{i}(x)=1\quad\forall x\}$ and $\mathcal{L}(\bm{u},\bm{u}^{k})$ is the linearization of the graph heat content Eq. (3.2) at $\bm{u}^{k}$ . A stopping criterion for the scheme can be $||E_{k}-E_{k+1}||/E_{k+1}<\delta,$ for some $\delta$ , where $E_{k}$ is the energy Eq. (3.2) at iteration $k$ .

Note that the first part of Eq. (9) is a bounded and feasible linear programming problem, whose solution always includes a vertex of the feasible polytope. Therefore, an optimal $\bf{u}$ in Eq. (9) is a binary vector with the following property: for each $x$ , $u_{j}(x)=1$ for some $j$ and $u_{i}(x)=0$ for $i\neq j$ . Therefore, the optimal $\bf{u}$ in Eq. (9) is trivially associated with a partition of $V$ .

Therefore, the precise form of the linearization $\mathcal{L}$ in Eq. (9) is given by the following:

.

Let $\Sigma=\{\Sigma_{1},\ldots,\Sigma_{N}\}$ be a partition of $V$ and $\bm{u}_{\Sigma}$ be a function where $u_{i}(x)=1$ if $x\in\Sigma_{i}$ and 0 otherwise. Up to a constant, the linearization of GHC Eq. (3.2) at $\bm{u}=\bm{u}_{\Sigma}$ is given by

$\displaystyle\mathcal{L}(\bm{u},\bm{u}_{\Sigma})=\sum_{i=1}^{N}\sum_{x\in V}u_% {i}(x)\left[\sum_{y\notin\Sigma_{i}}w(x,y)-\sum_{y\in\Sigma_{i}}w(x,y)\right].$ (10)

Proof..

First, we compute the derivative of Eq. (3.2) with respect to $u_{i}(x^{\star})$ , where $x^{\star}$ is a particular instance of the data set. The terms of Eq. (3.2) depending on $u_{i}(x^{\star})$ are

$\displaystyle w(x^{\star},x^{\star})u_{i}(x^{\star})(1-u_{i}(x^{\star}))+u_{i}% (x^{\star})\sum_{y\neq x^{\star}}w(x^{\star},y)(1-u_{i}(y))$ (11) $\displaystyle{}+(1-u_{i}(x^{\star}))\sum_{y\neq x^{\star}}w(y,x^{\star})u_{i}(% y).$

Taking the derivative of Eq. (3.2) with respect to $x^{\star}$ , one obtains:

$\displaystyle w(x^{\star},x^{\star})-2w(x^{\star},x^{\star})u_{i}(x^{\star})+% \sum_{y\neq x^{\star}}w(x^{\star},y)(1-u_{i}(y))-\sum_{y\neq x^{\star}}w(y,x^{% \star})u_{i}(y)$ (12) $\displaystyle=\sum_{y}w(x^{\star},y)(1-2u_{i}(y)),$

since the weight matrix we use is symmetric. At partition $\Sigma=\{\Sigma_{1},\ldots,\Sigma_{N}\}$ , $u_{i}(x)=1$ if $x\in\Sigma_{i}$ and 0 otherwise. Therefore, using Eq. (3.2), the derivative of Eq. (3.2) with respect to $u_{i}(x^{\star})$ evaluated at $\bm{u}_{\Sigma}$ is

$\displaystyle\sum_{y\notin\Sigma_{i}}w(x^{\star},y)-\sum_{y\in\Sigma_{i}}w(x^{% \star},y).$ (13)

∎

It turns out that the optimization problem in Eq. (9) is equivalent to a modified assignment problem; in particular, iteration $k$ of Eq. (9) consists of tackling

$\displaystyle\text{argmax}_{\bm{u}:T\rightarrow\mathbb{R^{N}},\bm{u}\geqslant% \bm{0}}\sum_{i=1}^{N}\sum_{x\in T}a^{k}_{i}(x)u_{i}(x)\quad\textrm{s.t.}\;\sum% _{i=1}^{N}u_{i}(x)=1,$ (14) $\displaystyle\text{and}\quad\forall i,\quad L_{i}\leqslant\sum_{x\in T}u_{i}(x% )\leqslant U_{i},$

where

$\displaystyle a^{k}_{i}(x)=1-\sum_{y\notin\Sigma^{k}_{i}}w(x,y)+\sum_{y\in% \Sigma^{k}_{i}}w(x,y),$ (15)

and forming the partition of the data set at iteration $k$ using $\Sigma_{i}^{k}=\{x\,\textrm{s.t.}\,\text{argmax}_{j}u_{j}^{k}(x)=i\}$ . Note that points $x\in R$ must have their labels fixed (i.e. $u=e_{i}\forall x\in R_{i}$ ) at all iterations, so we only need to minimize the linearizations over $x\in T$ . Note also that Eq. (3.2) involves inequality constraints, instead of equality constraints of the original assignment problem [76].

Note that, for all $k$ , partition $\Sigma^{k}$ is used only in the calculation of $a^{k}_{i}(x)$ for all $i$ . Thus, the labels of the training data are only used in the calculation of the assignment problem coefficients $\{a^{k}_{i}(x)\}$ , for all $k$ , before each modified assignment problem is solved.

To interpret the modified assignment Eq. (3.2) in a practical way, let the coefficients $\{a^{k}_{i}(x)\}$ represent how much data element $x$ wants to become a member of class $i$ at iteration $k$ . However, each class has a constraint on the number of memberships available, due to the class size constraints in the problem. While one can attempt to assign each data element its most desired class, this might not be possible due to the class size constraints. Overall, the solution to the modified assignment Eq. (3.2) is the matching of data elements and classes that maximizes the satisfaction of the data elements.

Our approach to solving each iteration of Eq. (9), the first step of which is equivalent to the modified assignment Eq. (3.2), is to assign the memberships according to a market mechanism, motivated by [76]. Let each class $i$ have a membership price $p_{i}$ ; this can help to resolve conflicts by making popular classes more expensive. Moreover, suppose that class $i$ can offer an incentive $t_{i}$ if it is having trouble attracting the necessary number of members (i.e. lower bound on the class size). Overall, it turns out that there exists an equilibrium price vector $\bf{p}^{*}$ and an equilibrium incentive vector $\bf{t}^{*}$ such that assigning memberships, so that each data element gets assigned to the class offering the “best value”, i.e. a class in $\text{argmax}_{1\leqslant i\leqslant N}a_{i}(x)-p^{*}_{i}+t^{*}_{i}$ , produces a partition that satisfies class size constraints. In fact, the equilibrium vectors form an optimal solution to the dual of the modified assignment Eq. (3.2).

.

The dual of the modified assignment Eq. (3.2), which is

$\displaystyle\max_{\bm{u}\geqslant\bm{0}}\sum_{i=1}^{N}\sum_{x\in T}a^{k}_{i}(% x)u_{i}(x)\quad\textrm{s.t.}\,\sum_{i=1}^{N}u_{i}(x)=1\quad\forall x\in T,L_{i% }\leqslant\sum_{x\in T}u_{i}(x)\leqslant U_{i},\quad\forall i.$

where $a^{k}_{i}(x)$ is computed using Eq, (15), and which is equivalent to the optimization problem in Eq. (9), is

$\displaystyle\min_{\bm{p}\geqslant\bm{0},\bm{t}\geqslant\bm{0},\bm{\pi}\in% \mathbb{R}^{n}}\sum_{i=1}^{N}(p_{i}U_{i}-t_{i}L_{i})+\sum_{x\in T}\pi(x)\quad% \textit{s.t.}\quad p_{i}-t_{i}+\pi(x)\geqslant a^{k}_{i}(x)\quad\forall i,$ (16)

where $p_{i}$ and $t_{i}$ are the $i^{\text{th}}$ values of vectors $\bm{p}$ and $\bm{t}$ , respectively, and $\pi(x)$ is the $x^{\text{th}}$ value of vector $\bm{\pi}$ .

Proof..

To incorporate the class size constraints, we introduce new vectors $\bm{p},\bm{t}$ and $\bm{\pi}$ . Therefore, the Lagrange dual function for the problem is the following:

$\displaystyle L(\bm{p},\bm{t},\bm{\pi})=\max_{\bm{u}\geqslant\bm{0}}\left\{% \sum_{i=1}^{N}\sum_{x\in T}a^{k}_{i}(x)u_{i}(x)+\sum_{x\in T}\pi(x)\left(1-% \sum_{i=1}^{N}u_{i}(x)\right)\right.$ (17) $\displaystyle{}+\left.\sum_{i=1}^{N}p_{i}\left(U_{i}-\sum_{x\in T}u_{i}(x)% \right)+\sum_{i=1}^{N}t_{i}\left(\sum_{x\in T}u_{i}(x)-L_{i}\right)\right\}.$

Rearranging the terms, one obtains

$\displaystyle L(\bm{p},\bm{t},\bm{\pi})\!=\!\max_{\bm{u}\geqslant\bm{0}}\left% \{\sum_{i=1}^{N}\sum_{x\in T}(a^{k}_{i}(x)-\pi(x)-p_{i}+t_{i})u_{i}(x)+\!\sum_% {i=1}^{N}(p_{i}U_{i}-t_{i}L_{i})+\!\sum_{x\in T}\pi(x)\right\}.$ (18)

The dual problem is calculated as

$\displaystyle\min_{\bm{p}\geqslant\bm{0},\bm{t}\geqslant\bm{0},\bm{\pi}\in% \mathbb{R}^{n}}L(\bm{p},\bm{t},\bm{\pi}).$ (19)

Since $(a^{k}_{i}(x)-\pi(x)-p_{i}+t_{i})u_{i}(x)$ can be arbitrarily large under fixed $a^{k}_{i}(x),\pi(x),p_{i}$ and $t_{i}$ such that $p_{i}-t_{i}+\pi(x)<a^{k}_{i}(x)$ and $\bm{u}\geqslant 0$ , the dual of the modified assignment problem is

$\displaystyle\min_{\bm{p}\geqslant\bm{0},\bm{t}\geqslant\bm{0},\bm{\pi}\in% \mathbb{R}^{n}}L(\bm{p},\bm{t},\bm{\pi})=\min_{\bm{p}\geqslant\bm{0},\bm{t}% \geqslant\bm{0},\bm{\pi}\in\mathbb{R}^{n}}\sum_{i=1}^{N}p_{i}U_{i}-t_{i}L_{i}+% \sum_{x\in T}\pi(x)$ (20) $\displaystyle\textrm{such that}\quad p_{i}-t_{i}+\pi(x)\geqslant a^{k}_{i}(x)% \quad\forall i.$

Here, the variable $\bm{p}$ corresponds to the price variable, and $\bm{t}$ corresponds to the incentive variable. ∎

Using the dual of the modified assignment Eq. (3.2) from Proposition 3.3:

$\displaystyle\min_{\bm{p}\geqslant\bm{0},\bm{t}\geqslant\bm{0},\bm{\pi}\in% \mathbb{R}^{n}}\sum_{i=1}^{N}(p_{i}U_{i}-t_{i}L_{i})+\sum_{x\in T}\pi(x)\quad% \textrm{s.t.}\quad p_{i}-t_{i}+\pi(x)\geqslant a^{k}_{i}(x)\quad\forall i,$ (21)

we see that $\bm{\pi}$ is determined by $\bm{p}$ and $\bm{t}$ and is given by

$\displaystyle\pi(x)=\max_{1\leqslant i\leqslant N}a^{k}_{i}(x)+t_{i}-p_{i}.$ (22)

Therefore, $\pi(x)$ is the value of the best deal offered to instance $x$ by any class.

The complementary slackness condition for Eqs (3.2) and (21) states that an assignment $\bm{u}$ and dual variables $(\bm{p},\bm{t},\bm{\pi})$ are optimal for their respective Eqs (3.2) and (21) if and only if

$\displaystyle\sum_{i=1}^{N}\sum_{x\in T}u_{i}(x)(a^{k}_{i}(x)-p_{i}+t_{i}-\pi(% x))+\sum_{i=1}^{N}p_{i}\left(U_{i}-\sum_{x\in T}u_{i}(x)\right)$ (23) $\displaystyle+\sum_{i=1}^{N}t_{i}\left(\sum_{x\in T}u_{i}(x)-L_{i}\right)=0.$

It can be difficult compute a solution $\bf{u}$ which satifies Eq. (3.2) and the class size constraints. Moreover, the values of equilibrium price and incentive vectors need to be computed. However, one can turn to the upper and lower bound auction of [8]. Not only does the upper and lower bound auction procedure compute the equilibrium price and incentive vectors, but it also finds an (at least nearly) optimal solution to Eq. (3.2) by producing a matching of data elements and classes such that the class size constraints are satisfied as well as the $\epsilon$ -complementary slackness condition: at iteration $k$ , if $x$ is matched with class $i$ ,

$\displaystyle a^{k}_{i}(x)-p^{*}_{i}+t^{*}_{i}+\epsilon\geqslant\text{argmax}_% {1\leqslant i\leqslant N}a^{k}_{j}(x)-p^{*}_{j}+t^{*}_{j},$ (24)

where $\bm{p}^{*}$ and $\bm{t}^{*}$ are the optimal price and incentive vectors, respectively. The matching can be used to obtain a solution $\bf{u}$ of Eq. (3.2) using: $u_{i}(x)=1$ if $x$ is matched to class $i$ and 0 otherwise. Overall, the upper and lower bound auction ensures that the solution $\bf{u}$ is at least nearly optimal. For the special case of integer $\{a_{i}^{k}(x)\}$ , the solution will be optimal for epsilon that is small enough.

A summary of what occurs during the auctions is:

•

Step 1 (Upper Bound Auction): In this auction, the elements of the data set compete for memberships to the class of their choice and place their bids. Each class accepts the people with the highest bids, but it cannot accept more than declared by the upper bound on its class size. Moreover, each class tailors its price and incentive according to demand during each iteration. Overall, the upper bounds on class sizes fit nicely into this perspective, but the lower bounds might not be fulfilled. They are instead taken care of during Step 2.

•

Step 2 (Lower Bound Auction): In this auction, the result of Step 1 is inputted into a reverse auction, during which the classes which have not yet reached the necessary number of members (i.e. lower bound on class sizes) compete for the data elements and provide incentives to attract the customers.

Our method is Algorithm 1 and the upper and lower bound auctions are outlined in the Appendix. The algorithm incorporates $\epsilon$ -scaling [77], which runs the upper and lower bound auction several times, each with a smaller value of $\epsilon$ , a variable in the $\epsilon$ -complementary slackness condition Eq. (24). Overall, the prices and incentives of the previous auction are used as an input in the next auction.

In Algorithm 1, iteration $k$ begins with the computation of the assignment problem coefficients $\{a_{i}^{k}(x)\}$ for solving Eq. (3.2), which is equivalent to the optimization problem in iteration $k$ of our scheme in Eq. (9). Then, the While loop involves the upper and lower bound auction for solving the modified assignment Eq. (3.2) and obtaining the equilibrium price and incentive vectors. Here, $\epsilon$ -scaling is used for efficiency. We note that, for all iterations, the labels of the training data are only used in the calculation of $\{a^{k}_{i}(x)\}$ .

Overall, the energy in Eq. (3.2) is decreased after each iteration of Algorithm 1; this fact is proved in the next proposition. Moreover, the class-size constrained graph heat content energy is a Lyapunov functional for our scheme; thus, we can guarantee unconditional gradient stability.

.

Every iteration of Algorithm 1, derived using the scheme Eq. (9), which successively minimizes linearizations of GHC in Eq. (3.2), will dissipate the energy of GHC.

Proof..

From Proposition 1, we know that GHC is concave whenever $W$ is a positive semi-definite matrix. Therefore, the following inequality is satisfied for all $u$ and $v$ :

$\displaystyle\textrm{GHC}(\bm{u},W)\leqslant\textrm{GHC}(\bm{v},W)+\nabla% \textrm{GHC}(\bm{v},W)\cdot(\bm{u}-\bm{v}),$ (25)

where $\nabla$ denotes the gradient. Let $u^{k}$ and $u^{k+1}$ be the outputs of the algorithm at iteration $k$ and $k+1$ . We must show that

$\displaystyle\textrm{GHC}(\bm{u}^{k+1},W)\leqslant\textrm{GHC}(\bm{u}^{k},W).$ (26)

According to our algorithm in Eq. (9), $u^{k+1}$ is obtained from $u^{k}$ by minimizing the linearization of the graph heat content at $u^{k}$ :

$\displaystyle\bm{u}^{k+1}=\text{argmin}_{u\in\mathcal{K}_{N}}\nabla\textrm{GHC% }(\bm{u}^{k},W)\cdot(\bm{u}-\bm{u}^{k})\quad\textrm{s.t.}\quad\sum_{i=1}^{N}u_% {i}(x)=1\quad\forall x\in T,$ (27) $\displaystyle L_{i}\leqslant\sum_{x\in T}u_{i}(x)\leqslant U_{i}.$

By evaluating the objective function at $u=u^{k}$ , one can see that

$\displaystyle\nabla\textrm{GHC}(\bm{u}^{k},W)\cdot(\bm{u}^{k+1}-\bm{u}^{k})% \leqslant 0.$ (28)

Due to Eq. (25), the following holds:

$\displaystyle\textrm{GHC}(\bm{u}^{k+1},W)\leqslant\textrm{GHC}(\bm{u}^{k},W)+% \nabla\textrm{GHC}(\bm{u}^{k},W)\cdot(\bm{u}^{k+1}-\bm{u}^{k}).$ (29)

Using Eqs (28) and (29), $\@setsize{\small}{11pt}{\xpt}{\@xpt}\textrm{GHC}(\bm{u}^{k+1},W)\leqslant% \textrm{GHC}(\bm{u}^{k},W)\@setsize{\normalsize}{13pt}{\xipt}{\@xipt}$ , so the energy is dissipated each iteration. ∎

[h] InputInput Data set $V$ consisting of labeled examples $R$ and unlabeled data $T$ , number of classes $N$ , total number $n$ elements of combined training and testing data, weight function $w$ , upper and lower bounds $\bm{U}$ and $\bm{L}$ on the sizes of the classes of testing data $T$ , maximum number of iterations $m$ , error tolerance $\epsilon_{\textit{min}}$ , scaling factor $\alpha$ , initial epsilon $\epsilon_{0}$ , stopping criterion $\delta$ . Final configuration $\bm{\Sigma}_{\textit{final}}$ , i.e. partition of data set $V$ into $N$ classes Initialization: Compute $\bm{\Sigma}^{0}$ using Voronoi initialization, $\bar{\epsilon}=\frac{\epsilon_{\textit{min}}}{n}$ $k$ from $0$ to $m-1$ Calculate the assignment problem coefficients $\forall k$ and $\forall i$ : $a^{k}_{i}(x)=1-\sum_{y\notin\Sigma^{k}_{i}}w(x,y)+\sum_{y\in\Sigma^{k}_{i}}w(x% ,y)$ Initially, prices $\bm{p}=\bm{0}$ , incentives $\bm{t}=\bm{0}$ , and $\epsilon=\epsilon_{0}$ $\epsilon\geqslant\bar{\epsilon}$ Run Algorithm 3 in the appendix (Upper Bound Auction): $(\bm{\Sigma}_{\textrm{out1}},\bm{p}_{\textrm{out1}},\bm{t}_{\textrm{out1}})=% \textrm{Upper Bound Auction}(\epsilon,\bm{L},\bm{U},\bm{a}^{k+1},\bm{p},\bm{t}% ,V)$ Run Algorithm 4 in the appendix (Lower Bound Auction): $(\bm{\Sigma}_{\textrm{out2}},\bm{p}_{\textrm{out2}},\bm{t}_{\textrm{out2}})=% \textrm{Lower Bound Auction}(\epsilon,\bm{L},\bm{U},\bm{a}^{k+1},\bm{p}_{% \textrm{out1}},\bm{t}_{\textrm{out1}},\bm{\Sigma}_{\textrm{out1}})$ Divide $\epsilon$ by $\alpha$ $\epsilon<\bar{\epsilon}$ Set $\bm{\Sigma}^{k+1}=\bm{\Sigma}_{\textrm{out2}}$ Set $(\bm{p},\bm{t})=(\bm{p}_{\textrm{out2}},\bm{t}_{\textrm{out2}})$

Compute the energy in Eq. (3.2) of the current iteration, $e_{c}$ , and that of the previous iteration, $e_{p}$ $||e_{c}-e_{p}||/e_{c}\leqslant\delta$ Set $\bm{\Sigma}_{\textit{final}}=\bm{\Sigma}^{k+1}$ and end algorithm

$\bm{\Sigma}_{\textit{final}}$ A Multiclass Data Classification Algorithm

3.3 Stability with respect to mislabeled training data

This subsection discusses the stability of Algorithm 1 with respect to mislabeled training data. In fact, the procedure of Algorithm 1 is equipped with several properties which allow the algorithm to still perform well even in the presence of a large number of mislabeled training nodes.

Here, we assume that the mislabeled data only contains noise in the label and not in the attribute information. Then, the weight matrix $W=\{w(x,y)\}$ , whose calculation does not involve the labels of the training data and involves only the attribute information, has the following property ( $\star$ ): if $x$ and $y$ are not similar, $w(x,y)$ is small. Thus, if $w(x,y)$ is large, it is likely that $x$ and $y$ are in the same class.

Moreover, we construct the weight matrix using a graph that connects each point only to its $l$ nearest neighbors. Therefore, many entries of the weight matrix are zero. Let this be property $(\star\star)$ .

We now note that, as mentioned in Section 3.2, our algorithm uses the labels from the training data only in the calculation of the variables $\{a^{k}_{i}(x)\}\forall i$ and $\forall x$ in the modified assignment problem; the labels are not used for any other purpose. Let this be property $(\star\star\star)$ .

Suppose that, at iteration $k$ , training node $y^{\star}$ is mislabeled to class $j$ instead of true class $p$ . Since

$\displaystyle a^{k}_{i}(x)=1-\sum_{y\notin\Sigma^{k}_{i}}w(x,y)+\sum_{y\in% \Sigma^{k}_{i}}w(x,y),$ (30)

due to properties $(\star)$ and $(\star\star)$ , the value of $a^{k}_{i}(x)$ is only affected in a non-negligible way in the very unlikely case that $x$ and $y^{\star}$ are $l$ nearest neighbors, in the same class, and $i=j$ or $i=p$ . If $x$ and $y^{\star}$ are $l$ nearest neighbors, in the same class and $i=j$ , $w(x,y^{\star})$ is large and $a^{k}_{i}(x)$ is smaller than it should be. If $x$ and $y^{\star}$ are $l$ nearest neighbors, in the same class and $i=p$ , $w(x,y^{\star})$ is large and $a^{k}_{i}(x)$ is bigger than it should be. Otherwise, it is extremely likely that $w(x,y^{\star})$ is either 0 or close to 0, so $a^{k}_{i}(x)$ is either negligibly affected or not at all.

We now see that all but extremely few of the assignment problem coefficients $\{a^{k}_{i}(x)\}$ are either completely unaffected or negligibly affected if $y^{\star}$ is mislabeled. Due to this, property $(\star\star\star)$ , which states that, in Algorithm 1, the labels from the training data are only used in the calculation of the variables $\{a^{k}_{i}(x)\}$ , allows our algorithm to perform well in the presence of even large amounts of mislabeled training data. We perform extensive experiments, described in Section 4, to validate the statement.

3.4 Correcting the mislabeled training data

In this section, we present a modified version of Algorithm 1 which corrects mislabeled training data during its procedure. Specifically, one can consider a variation of Algorithm 1 where we relabel certain training instances each iteration before each modified assignment problem is solved. Our approach to relabeling involves using the equilibrium price $\bm{p}$ and incentive vector $\bm{t}$ from the previous iteration, i.e. from the solution of the previous assignment problem. Moreover, we calculate the energy in Eq. (3.2) to determine if it would decrease should the label of the node in question be changed to a particularvalue.

Our relabeling procedure is the following: at iteration $k$ of Algorithm 1, before Eq. (3.2) is solved, we consider a training instance $x$ as mislabeled if both of the following are fulfilled:

•
$\@setsize{\small}{11pt}{\xpt}{\@xpt}j=\text{argmax}_{1\leqslant i\leqslant N}a% ^{k}_{i}(x)+t_{i}-p_{i}$ is different from the class currently assigned to $x$ .
•
Energy Eq. (3.2) is decreased when training node $x$ is assigned class $j$ instead of its current class.

If $x$ is classified as mislabeled, its label is changed to $j$ . This step is chosen since it corresponds to the market strategy Eq. (22) for matching elements with classes. Moreover, at iteration $k$ , if some training labels are changed, the coefficients $\{a_{i}^{k}(x)\}$ are recomputed according to Eq. (15).

Overall, our procedure for identifying and correcting mislabeled training data is detailed as Algorithm 2. Moreover, the time complexity of the procedure is easy to compute. Let $l$ be the number of nearest neighbors used to compute the weights $w$ , and $|R|$ be the number of elements of labeled training data. Our modified procedure adds the following steps to Algorithm 1:

•
Relabeling training data requires at most $O(nl|R|)$ operations. For every training element, the calculations include (i) computing $j$ , requiring $O(N)$ operations, (ii) calculating $e_{c}$ and $e_{f}$ , which takes $O(nl)$ operations each using the assignment problem coefficients, and (iii) computing the comparison between the energies. Note that computing energy Eq. (3.2) when $u$ represents a partition $\mathbf{\Sigma^{k}}=(\Sigma^{k}_{1},\ldots,\Sigma^{k}_{N})$ involves calculating $\@setsize{\small}{11pt}{\xpt}{\@xpt}\sum_{i=1}^{N}\sum_{x\in\Sigma^{k}_{i}}% \sum_{y\notin\Sigma^{k}_{i}}w(x,y)$ . Computing the energy can be done in $O(nl)$ operations, once the coefficients $\{a_{i}^{k}(x)\}$ are calculated. This is because it is enough to consider $l$ nearest neighbors of nodes and

$\displaystyle\sum_{i=1}^{N}\sum_{x\in\Sigma^{k}_{i}}\sum_{y\notin\Sigma^{k}_{i% }}w(x,y)=\sum_{x\in V}\left(1-a^{k}_{\textit{label}(x)}(x)+\sum_{y\in\Sigma^{k% }_{\textit{label}(x)}}w(x,y)\right).$ (31)
•
Recomputing assignment problem coefficients $\{a_{i}^{k}(x)\}$ using an update list of changed labels takes at most $O(|R|l)$ calculations. This is because there are at most $|R|$ elements of training data whose labels change each iteration (and likely much smaller), and the fact that it is enough to only consider the $l$ nearest neighbors for each training node whose label has changed.

[h] Let the Input, Result and Initialization be the same as in Algorithm 1, $k$ be the iteration number and $c$ be a number whose default value is $n$ . Perform the steps outlined as Algorithm 1, while executing the following commands (to correct mislabeled training data) before each While loop:

$k\neq 0$ and $c\neq 0$ all $x\in R$ Let $\{a^{k}_{i}(x))\}$ be the coefficients of the current modified assignment problem, and $\{p_{i}\}$ and $\{t_{i}\}$ be the prices and the incentives of the previous upper and lower bound auction. Compute $j=\text{argmax}_{1\leqslant i\leqslant N}a^{k}_{i}(x)+t_{i}-p_{i}$ . If $j$ is different from the class currently assigned to instance $x$ :

•
Compute $e_{c}$ = energy Eq. (3.2) of the current configuration of labels.
•
Compute $e_{f}$ = energy Eq. (3.2) when the training instance $x$ is assigned to class $j$ instead.
•
If $e_{f}<e_{c}$ , change the label of the training instance $x$ to $j$ .

$c$ = $\#$ of training labels changed during this iteration Recalculate $\{a^{k}_{i}(x)\}$ if any labels of the labeled training examples $R$ were changed Procedure for Correcting Mislabeled Training Data
4. Experiments

To validate our algorithm, we perform extensive experiments on eight benchmark datasets:

•
The first set of experiments consists of varying the number of labeled examples.
•
The second set of experiments consists of corrupting the labels of different amounts of the training data as an input to the algorithm. To corrupt the labels, we replace the correct label of a training data element with a randomly chosen incorrect one. For example, a training element of class 3 might be assigned an incorrect label of class 1 as an input into the algorithm.
•
The last set of experiments includes applying the proposed technique in point Eq. (2) to identify and correct mislabeled training data.

For each data set, we randomly select a certain percentage of it to use as labeled training data, and this set is used to label the unlabeled testing data. Regarding initialization, the labels of the unlabeled points are initialized by creating a Voronoi diagram with the labels of the training points as the seed points; every point is assigned the label of the training point in its Voronoi cell. Regarding parameters, we use $\delta=$ 0.0001, $\epsilon_{\textit{min}}=$ 0.0000001, epsilon scaling factor $\alpha=$ 4, maximum number of iterations $m=$ 100, and initial epsilon $\epsilon_{0}$ =1.

In our experiments, when the labeled training set is small, we incorporate random fluctuations of variables to help our algorithm reach even lower energies, thus increasing the classification accuracy even further. Random fluctuations can also help avoid degenerate auction coefficients which can impact the speed of the method. Although there are several ways to introduce the fluctuations into our procedure, we choose to perturb $a_{i}(x)$ by an independent sample of a normal random variable (with mean zero) before the upper and lower bound auction. In the case of experiments with random fluctuations of variables, a fixed number of iterations is run, and the partition corresponding to the lowest energy is chosen.

All experiments were run using C code on 2.2 GHz Intel Core i7 computer. The $l$ nearest neighbors were calculated using the $k d$ -tree code in the VLFeat library.
4.1 Data sets

•
MNIST. MNIST is a data set of 70,000 grayscale $28\times 28$ images of handwritten digits; the set has 10 classes and can be downloaded at [78]. The weight matrix $W=\{w(x,y)\}$ is constructed using $l=15$ without any preprocessing of the images. At the end, we average the accuracy over 500 experiments, each with a different set of labeled nodes.
•
Fashion MNIST. Fashion-MNIST is a dataset of 70,000 $28\times 28$ grayscale images of clothing items; the set has 10 classes and can be downloaded at [79]. The weight matrix is constructed using $l=15$ without any preprocessing of the images. At the end, we average the accuracy over 500 experiments, each with a different set of labeled nodes.
•
Opt-Digits. The Opt-Digits is a set of images of 5620 handwritten digits; it has 10 classes and can be downloaded at [80]. The dimension reduction performed on the data produced a 64-dimensional feature vector for each image, where each value is an integer in the range of 0 to 16. The weight matrix is constructed using $l=20$ . At the end, we average the accuracy over 10000 experiments, each with a different set of labeled nodes.
•
WebKB. The WebKB data set [81] is a set of 4199 webpages from Cornell, Texas, Washington and Wisconsin universities, and other miscellaneous pages. The webpages are to be divided into four classes: project, course, faculty and student. The data set is preprocessed as in [82], and tfidf term weighting [82] is used to represent the feature vectors, which are then normalized to unitary length. To construct the weights, we use a pairwise document similarity measure [9] as a distance measure and $l=30$ . At the end, we average the accuracy over 5000 experiments, each with a different set of labeled nodes.
•
Reuters. The Reuters (R8) data set [83] is a collection of 7674 documents to be divided into 8 classes: ‘acq’, ‘crude’, ‘earn’, ‘grain’, ‘interest’, ‘money-fx’, ‘ship’ and ‘trade’. Tfidf term weighting [82] is used to represent the website feature vectors, which are then normalized to unitary length. To construct the weight matrix, we use a pairwise document similarity measure [9] as a distance measure and $l=30$ . At the end, we average the accuracy over 1000 experiments, each with a different set of labeled nodes.
•
20 Newsgroups. The 20 Newsgroups data set [84] is a set of approximately 20,000 newsgroup documents, to be partitioned across 20 classes. Tfidf term weighting [82] is used to represent the feature vectors, which were then normalized to unitary length. To construct the weights, we use cosine similarity as a distance measure and $l=30$ . We average the accuracy over 1000 experiments, each with a different set of labeled nodes.
•
Landsat. The Landsat data set [85], is a set of multi-spectral values of pixels in $3\times 3$ neighbourhoods in a satellite image, and the classification is associated with the central pixel. There are 6 classes. Each of the 6435 elements of the data contains the pixel values in the four spectral bands of each pixel in the $3\times 3$ neighbourhood; therefore each feature vector consists of 36 values. The weights are constructed using $l=20$ . We average the accuracy over 10000 experiments, each with a different set of labeled nodes.
•
Pendigits. The Pendigits is a data set of 10992 images of handwritten digits; the set has 10 classes and can be downloaded at the UCI Machine Learning Repository at [86]. Each image is represented by a feature vector consisting of 16 values, each between 0 and 100. The weight matrix is constructed using $l=30$ . At the end, we average the accuracy over 5000 experiments, each with a different set of labeled nodes.

Figure 1.
Comparison of proposed Algorithm 1 and other methods using different amounts of labeled examples.

Figure 2.
Comparison of proposed Algorithm 1 and other methods using different amounts of corrupted training labels.

Figure 3.
Accuracy of proposed Algorithm 1 using different amounts of labeled examples and corrupted training labels.

4.2 Experiments with different numbers of labeled examples

To validate our proposed Algorithm 1, we perform experiments with different numbers of labeled examples, and compare the results to those of some of the best recent algorithms. The results of the experiments are displayed in Fig. 1 for all the data sets, where our proposed Algorithm 1 is indicated by the red line. The numerical data is presented in Tables 4–11 for all the data sets.

The results show that the proposed method performs extremely well compared to other algorithms, especially in the case of few labeled elements, when the proposed method is often able to obtain much higher accuracies than other methods. This is especially important due to the scarcity of labeled training data. For example, our method is able to obtain around 97.37% on the MNIST data set with just 140 labeled training examples, which corresponds to only 0.2% of the overall data set. Moreover, our method is able to obtain around 98.22% on the Optdigits data set and 94.93% on the Pendigits data set with just 56 and 110 labeled training examples, respectively. In addition, text classification results show that with just 38 labeled training examples, the algorithm is able to obtain a 91.32% accuracy on the Reuters set.

4.3 Experiments with different amounts of corrupted training labels

To show that our proposed Algorithm 1 still performs with good accuracy even with high amounts of mislabeled examples, we perform experiments where we corrupt the labels of different amounts of training examples. In particular, we corrupt the labels of 5%, 10%, 15%, 20%, 30% and 40% of the training data. The quantitative results are displayed in Tables 4–11. A comparison to other methods is displayed in Fig. 2. Figure 3 shows the results of our method using different amounts of corrupted training labels and labeled training data.

Table 1
Timing results for Algorithm 1 (not including weight matrix $W$ construction)

Data set	# of elements	Timing	Data set	# of elements	Timing
	in the data set	in seconds		in the data set	in seconds
MNIST	70000	0.2986	Pendigits	10992	0.0555
Opt-Digits	5620	0.0249	WebKB	4199	0.0419
Fashion MNIST	70000	0.5385	Landsat	6435	0.6035
Reuters	7674	0.0263	20 Newsgroups	18820	0.1481

Table 2

Comparison of timing to other algorithms (weight matrix $W$ construction and training time)

Method	MNIST	Fashion MNIST	Other data sets from Section 4.1
Construction of $W$ for Algorithm 1 (Proposed)	$\sim$ 2 min	$\sim$ 2 min	0.03 min–1 min for all but 20 Newsgroups
Training time for LeNet-5 [27]	$\sim$ 25 min	$\sim$ 25 min	Not included in paper
Training time for PixelHop [33]	$\sim$ 15 min	$\sim$ 15 min	Not included in paper

Table 3

Comparison of total timing to support vector machines (computed using LIBSVM)

Data set	Number of elements	Total time for Algorithm 1 (including weight matrix $W$ construction) for all amounts of labeled data	Total time for SVM (LIBSVM) (including training) for 30% labeled elements
WebKB	4199	4 seconds	9 seconds
Reuters	7674	29 seconds	36 seconds
MNIST	70000	121 seconds	401 seconds
Fashion MNIST	70000	123 seconds	634 seconds
OptDigits	5620	2 seconds	2 seconds
Landsat	6435	3 seconds	78 seconds
Pendigits	10992	18 seconds	0.02 seconds
20 Newsgroups	18820	776 seconds	5204 seconds

Table 4

MNIST results (accuracy) – Algorithm 1

% of	0.2%	1%	5%	10%	20%
% of data used as
labeled examples
labels corrupted
0%	97.37	97.47	97.57	97.70	97.88
5%	97.35	97.45	97.54	97.67	97.82
10%	97.32	97.44	97.51	97.64	97.78
15%	97.28	97.42	97.50	97.60	97.74
20%	97.25	97.40	97.46	97.57	97.69
30%	97.23	97.39	97.44	97.50	97.59
40%	97.20	97.38	97.40	97.43	97.49

Table 5

OptDigits results (accuracy) – Algorithm 1

% of	1%	2.5%	5%	10%	20%
% of data used as
labeled examples
labels corrupted
0%	98.22	98.63	98.73	98.81	98.89
5%	97.96	98.51	98.62	98.69	98.75
10%	97.47	98.44	98.52	98.60	98.61
15%	96.84	98.27	98.38	98.41	98.45
20%	95.60	98.10	98.25	98.33	98.39
30%	92.83	97.79	97.94	98.22	98.26
40%	86.90	96.72	97.55	97.94	98.08

Table 6

Fashion MNIST results (accuracy) – Algorithm 1

% of	1%	2.5%	5%	10%	20%
% of data used as
labeled examples
labels corrupted
0%	80.18	82.18	83.80	84.93	86.01
5%	79.69	81.85	83.49	84.78	85.73
10%	79.47	81.44	83.21	84.56	85.44
15%	78.69	81.26	82.86	84.19	85.14
20%	78.25	80.75	82.58	83.93	84.91
30%	77.30	80.45	82.54	83.66	84.74
40%	75.91	79.56	81.73	83.04	84.15

Table 7

Reuters results (accuracy) – Algorithm 1

% of	0.5%	1%	5%	10%	20%
% of data used as
labeled examples
labels corrupted
0%	91.32	92.71	95.07	95.35	95.59
5%	90.13	92.44	94.86	95.16	95.31
10%	89.25	91.94	94.61	94.88	95.04
15%	88.12	91.04	94.35	94.53	94.77
20%	86.67	90.85	94.10	94.20	94.51
30%	85.71	88.73	93.55	93.78	94.15
40%	81.39	86.98	92.85	93.08	93.53

Table 8

Pendigits results (accuracy) – Algorithm 1

% of	1%	2.5%	5%	10%	20%
% of data used as
labeled examples
labels corrupted
0%	94.93	97.69	98.63	99.11	99.32
5%	94.70	97.44	98.23	98.94	99.21
10%	93.28	96.90	97.88	98.70	99.12
15%	91.65	96.31	97.48	98.59	98.96
20%	90.15	95.86	96.80	98.18	98.76
30%	88.28	94.45	95.40	97.85	98.31
40%	80.64	92.74	93.07	96.57	97.80

Table 9

WebKB results (accuracy) – Algorithm 1

% of	5%	10%	15%	20%	40%
% of data used as
labeled examples
labels corrupted
0%	78.47	80.56	81.75	82.70	84.77
5%	78.00	80.40	81.73	82.51	84.59
10%	77.12	80.11	81.51	82.41	84.41
15%	76.62	79.72	81.17	82.17	84.14
20%	75.34	79.12	80.85	81.89	83.74
30%	73.53	77.52	79.78	80.97	82.80
40%	71.62	75.22	77.54	79.11	80.71

Table 10

Landsat results (accuracy) – Algorithm 1

% of	1%	2.5%	5%	10%	20%
% of data used as
labeled examples
labels corrupted
0%	84.72	86.34	87.74	88.78	90.34
5%	84.20	86.09	87.02	88.54	90.03
10%	83.86	85.45	86.60	87.73	89.53
15%	82.88	85.05	85.93	87.58	88.79
20%	81.97	84.28	85.36	86.94	88.18
30%	79.45	83.37	84.30	86.34	86.87
40%	75.07	81.82	83.23	84.71	85.30

Table 11

20 Newsgroups results (accuracy) – Algorithm 1

% of	1%	5%	10%	15%	20%
% of data used as
labeled examples
labels corrupted
0%	72.57	78.25	81.46	83.70	84.93
5%	72.21	77.83	80.60	83.07	84.24
10%	71.66	77.29	79.71	82.44	83.45
15%	70.67	76.61	78.89	81.66	82.55
20%	69.74	76.03	77.88	80.75	81.66
30%	67.40	74.57	75.76	78.86	79.52
40%	65.12	72.33	73.30	76.50	77.18

Table 12

Correcting mislabeled training data (using Algorithm 2) – MNIST data set

Average # of mislabeled training examples going from incorrect to correct label
% of data used as labeled
examples	0.2%	1%	5%	10%	20%
% of labels corrupted
out of initially incorrectly labeled training examples
5%	6.21 of 7	33.76 of 35	170.03 of 175	340.56 of 350	681.98 of 700
10%	12.19 of 14	67.38 of 70	340.03 of 350	680.83 of 700	1363.08 of 1400
15%	18.46 of 21	100.93 of 105	509.44 of 525	1021.21 of 1050	2046.95 of 2100
20%	24.14 of 28	134.56 of 140	678.91 of 700	1360.03 of 1400	2727.96 of 2800
30%	35.34 of 42	201.30 of 210	1017.30 of 1050	2039.32 of 2100	4086.66 of 4200
40%	44.16 of 56	267.05 of 280	1355.89 of 1400	2719.01 of 2800	5446.65 of 5600
Average # of training examples going from correct to incorrect label
out of initially correctly labeled training examples
5%	2.15 of 133	10.92 of 665	58.44 of 3325	117.96 of 6650	238.84 of 13300
10%	2.01 of 126	10.63 of 630	55.83 of 3150	112.02 of 6300	223.11 of 12600
15%	1.93 of 119	9.90 of 595	53.18 of 2975	107.62 of 5950	215.93 of 11900
20%	1.90 of 112	9.64 of 560	49.94 of 2800	100.53 of 5600	203.52 of 11200
30%	1.78 of 98	8.69 of 490	43.90 of 2450	90.30 of 4900	180.58 of 9800
40%	1.89 of 84	7.46 of 420	39.11 of 2100	78.81 of 4200	154.07 of 8400

Table 13

Correcting mislabeled training data (using Algorithm 2) – opt-digits data set

Average # of mislabeled training examples going from incorrect to correct label
% of data used as labeled
examples	1%	2.5%	5%	10%	20%
% of labels corrupted
out of initially incorrectly labeled training examples
5%	1.60 of 2	6.30 of 7	13.27 of 14	27.19 of 28	54.96 of 56
10%	3.91 of 5	12.50 of 14	26.46 of 28	54.23 of 56	109.85 of 112
15%	6.13 of 8	18.48 of 21	39.56 of 42	81.17 of 84	164.56 of 168
20%	8.13 of 11	24.36 of 28	52.56 of 56	108.00 of 112	219.23 of 224
30%	11.18 of 17	35.70 of 42	78.08 of 84	161.02 of 168	328.72 of 337
40%	12.29 of 22	44.80 of 56	102.85 of 112	213.00 of 224	435.84 of 449
Average # of training examples going from correct to incorrect label
out of initially correctly labeled training examples
5%	0.34 of 55	1.00 of 134	2.18 of 267	4.79 of 534	10.04 of 1068
10%	0.34 of 52	1.01 of 127	2.16 of 253	4.67 of 506	9.60 of 1012
15%	0.41 of 49	1.03 of 120	2.10 of 239	4.53 of 478	9.27 of 956
20%	0.47 of 46	1.07 of 113	2.10 of 225	4.44 of 450	8.88 of 900
30%	0.73 of 40	1.18 of 99	2.10 of 197	4.25 of 394	8.27 of 787
40%	1.14 of 35	1.53 of 85	2.23 of 169	4.34 of 338	7.96 of 675

The results indicate that our algorithm obtains a high accuracy on the testing data even when a large part of the training data is mislabeled and the number of labeled training nodes is small. For example, from the MNIST data set results in Table 5, even when 40% of the training data is mislabeled and there are only 140 labeled images (out of 70000 total) as part of the training data, the method still obtains a 97.20% accuracy on the testing data! Moreover, from the Opt-Digits data set results in Table 6, even when 40% of the training data is mislabeled and there are only 281 labeled training images, the algorithm still obtains a 97.55% accuracy on the testing data. In addition, even when 40% of the training data is mislabeled, the proposed algorithm still obtains 92.74% and 81.82% accuracy on the testing data of the Pendigits and Landsat data sets, respectively, using only 275 and 161 labeled training examples, respectively. For the Reuters data set, using only 383 labeled training examples, even when 40% of the training data is mislabeled, the method still obtains 92.85% accuracy on the testing set.

4.4 Experiments where the mislabeled training data is corrected

To test the procedure in Section 3.4, detailed as Algorithm 2, for correcting mislabeled training data, we perform experiments using that technique. The results are shown in Tables 12 and 13; to be concise, we include results for two data sets. The tables show that the procedure is able to correct almost all of the labels of the mislabeled training data. For example, for MNIST, when the training data consists of only 700 labeled images and when 20% of the labels are incorrect, over 500 experiments, an average of 134.56 out of 140 incorrect training labels are corrected.

The chance of turning a correct label of the training data into an incorrect label is very small, as shown in Tables 12 and 13. For example, for the Opt-Digits data set, when the training data consists of 281 labeled images (out of 5620 total) and 20% of the labels are incorrect, on average, only around 2 out of 225 correctly labeled training points are classified incorrectly at the end.

4.5 Experiments with noise in attribute information

Even though this paper focuses on noise in the training labels, and the case of noise in the attribute (feature) information of the training data is the subject of another work, in this subsection, we include two experiments where noise is added to the attributes/features of the training data. In particular, we consider two of the data sets in Section 4.1: Pendigits and Landsat. For each experiment, we add Gaussian noise with mean 0 and standard deviation $\eta$ to each element of the data.

The experiments indicate that the accuracy of the proposed algorithm reduces only by a little amount even with Gaussian noise with standard deviation $\eta=5$ or $\eta=7.5$ added to the attribute or feature information. In particular, for the Pendigits data set, the accuracy of the algorithm only reduces by 0.01%–0.2% with $\eta=1$ , by 0.1%–0.35% with $\eta=2.5$ , by 0.5%–1% with $\eta=5$ and by 1.1%–1.9% with $\eta=7.5$ . For the Landsat data set, the accuracy of the algorithm only reduces by 0.04%–0.06% with $\eta=1$ , by 0.06%–0.5% with $\eta=2.5$ and by 0.5%–1.5% with $\eta=5$ .

4.6 Timing

The timing results for Algorithm 1 are included in Tables 1–3. All experiments were performed on a 2.2 GHz Intel Core i7 computer. Table 1 includes the timing needed for everything but the construction of the weight matrix $W$ . Table 2 includes the timing needed to construct the weight matrix $W$ for Algorithm 1. For all but the 20 Newsgroups data set, the time to construct the weight matrix is only 0.03–2 minutes; for the 20 Newsgroups data set, around 12 minutes are needed to compute the nearest neighbors graph.

We also include a comparison to the timing of convolutional neural networks and support vector machines in Tables 2 and 3.

5. Conclusion

We have detailed a semi-supervised graph-based method for multiclass data classification. The algorithm involves upper and lower bound auction dynamics. Among its advantages is the fact that the proposed method requires considerably less labeled training data to accurately classify a data set compared to current machine learning techniques. In particular, it performs very well and more accurately than current approaches in the common scenario of few labeled training elements. This is important due to the scarcity of labeled training data and the fact that obtaining labeled data is time-consuming and expensive. In addition, the method is very efficient and unconditionally stable. The algorithm also handles mislabeled examples well and performs with good accuracy even with a large number of mislabeled examples. Lastly, the proposed method is able to incorporate class size information.

Footnotes

Appendix

Upper and lower bound auctions

[H] InputInput $\epsilon>0$ , bounds $\bm{L},\bm{U}$ on class sizes of the testing data, coefficients $\bm{a}$ , initial prices $\bm{p}^{0}$ , initial incentives $\bm{t}^{0}$ and people $x\in V$ . a partition $\bm{\Sigma}$ of data set $V$ consisting of training and testing data, admissible prices $\bm{p}$ , and admissible incentives $\bm{t}$ . Initialization: Mark all $x\in T$ as unassigned, set $\bm{d}=\bm{p}^{0}-\bm{t}^{0}$ , $\bm{\Sigma}=\varnothing$ and $\bm{b}=\infty$ . Notation: $T_{i}$ = the subset of testing data currently in classified as class $i$ . some $x$ is marked as unassigned each unassigned $x\in V$ Choose some $i^{*}\in i_{cs}(x,\bm{d})=\text{argmax}_{1\leqslant i\leqslant N}a_{i}(x)-d_{i}$ Calculate $i_{\textrm{next}}\in\text{argmax}_{j\not\in i_{cs}(x,\bm{d})}a_{j}(x)-d_{j}$ Set $b(x)=d_{i^{*}}+\epsilon+(a_{i^{*}}(x)-d_{i^{*}})-(a_{i_{\textrm{next}}}(x)-d_{% i_{\textrm{next}}})$ $|T_{i^{*}}|=U_{i^{*}}$ Find $y=\text{argmin}_{z\in T_{i^{*}}}b(z)$ Remove $y$ from $\Sigma_{i^{*}}$ and add $x$ to $\Sigma_{i^{*}}$ Mark $y$ as unassigned and mark $x$ as assigned Set $d_{i^{*}}=\min_{z\in T_{i^{*}}}b(z)$ $|T_{i^{*}}|=L_{i}$ and $d_{i}<0$ Find $y=\text{argmin}_{z\in T_{i^{*}}}b(z)$ Remove $y$ from $\Sigma_{i^{*}}$ and add $x$ to $\Sigma_{i^{*}}$ Mark $y$ as unassigned and mark $x$ as assigned Set $d_{i^{*}}=\min(\min_{z\in T_{i^{*}}}b(z),0)$ Mark $x$ as assigned and add $x$ to $\Sigma_{i^{*}}$ Set $\bm{p}=\max(\bm{d},\bm{0})$ , set $\bm{t}=\max(-\bm{d},\bm{0})$ $(\bm{\Sigma},\bm{p},\bm{t})$ Upper Bound Auction [8]

[H] InputInput $\epsilon>0$ , bounds $\bm{L},\bm{U}$ on class sizes of the testing data, coefficients $\bm{a}$ , initial prices $\bm{p}^{0}$ , initial admissible incentives $\bm{t}^{0}$ , and a partition $\bm{\Sigma^{0}}$ of $V$ . a partition $\bm{\Sigma}$ of data set $V$ consisting of training and testing data, admissible prices $\bm{p}$ , and admissible incentives $\bm{t}$ . Initialization: Set $\bm{d}=\bm{p}^{0}-\bm{t}^{0}$ , set $\bm{\Sigma}=\bm{\Sigma}^{0}$ . Notation: $T_{i}$ = the subset of testing data currently in classified as class $i$ . there exists some $i$ with ( $|T_{i}|<U_{i}$ and $d_{i}>0$ ) or ( $|T_{i}|<L_{i}$ ) each $i^{*}$ with ( $|T_{i^{*}}|<U_{i^{*}}$ and $d_{i^{*}}>0$ ) or ( $|T_{i^{*}}|<L_{i^{*}}$ ) each $x\in T\setminus{T_{i^{*}}}$ Let $j$ be $x$ ’s current phase Calculate $\Delta(x)=(a_{j}(x)-d_{j})-(a_{i^{*}}(x)-d_{i^{*}})$ ( $|T_{i^{*}}|<U_{i^{*}}$ and $d_{i^{*}}>0$ ) or ( $|T_{i^{*}}|<L_{i^{*}}$ ) Find $x\in\text{argmin}_{y\in T\setminus{T_{i^{*}}}}\Delta(y)$ $|T_{i^{*}}|<L_{i^{*}}$ Remove $x$ from its current phase and add $x$ to $\Sigma_{i^{*}}$ $|T_{i^{*}}|=L_{i^{*}}$ and $\Delta(x)\geqslant 0$ Subtract $\Delta(x)+\epsilon$ from $d_{i^{*}}$ $\Delta(x)+\epsilon\geqslant d_{i^{*}}$ Set $d_{i^{*}}=0$ Remove $x$ from its current phase and add $x$ to $\Sigma_{i^{*}}$ $|T_{i^{*}}|=U_{i^{*}}$ and $\Delta(x)\geqslant 0$ Subtract $\Delta(x)+\epsilon$ from $d_{i^{*}}$

Set $\bm{p}=\max(\bm{d},\bm{0})$ , set $\bm{t}=\max(-\bm{d},\bm{0})$ $(\bm{\Sigma},\bm{p},\bm{t})$ Lower Bound Auction [8]

References

Joachims

, Text categorization with support vector machines: learning with many relevant features, in: European Conference on Machine Learning, 1998, pp. 137–142.

Chang

C.-C.

and Lin

C.-J.

, LIBSVM: A library for support vector machines, ACM Transactions on Intelligent Systems and Technology 2(3) (2011), 27.

Burges

, A tutorial on support vector machines for pattern recognition, Data Mining and Knowledge Discovery 2(2) (1998), 121–167.

Konyushkova

Sznitman

and Fua

, Learning active learning from data, Advances in Neural Information Processing Systems (2017), 4225–4235.

LeCun

and Bengio

, Convolutional networks for images, speech, and time series, The Handbook of Brain Theory and Neural Networks 3361(10) (1995), 1995.

Krizhevsky

Sutskever

and Hinton

G.E.

, Imagenet classification with deep convolutional neural networks, Advances in Neural Information Processing Systems (2012), 1097–1105.

Karpathy

Toderici

Shetty

Leung

Sukthankar

and Fei-Fei

, Large-scale video classification with convolutional neural networks, in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2014, pp. 1725–1732.

Jacobs

Merkurjev

and Esedoḡlu

, Auction dynamics: A volume constrained MBO scheme, Journal of Computational Physics 354 (2018), 288–310.

Oghbaie

and Zanjireh

M.M.

, Pairwise document similarity measure based on present term set, Journal of Big Data 5(1) (2018), 52.

10.

Zelnik-Manor

and Perona

, Self-tuning spectral clustering, Advances in Neural Information Processing Systems (2004), 1601–1608.

11.

Zhu

, Semi-supervised learning literature survey, Computer Science, University of Wisconsin-Madison 2(3) (2006), 4.

12.

Yin

Tai

X.-C.

and Osher

S.J.

, An effective region force for some variational models for learning and clustering, Journal of Scientific Computing 74(1) (2018), 175–196.

13.

Joachims

, Transductive learning via spectral graph partitioning, International Conference on Machine Learning 20(1) (2003), 290.

14.

Bertozzi

A.L.

and Flenner

, Diffuse interface models on graphs for classification of high dimensional data, Multiscale Modeling & Simulation 10(3) (2012), 1090–1118.

15.

Merkurjev

Kostic

and Bertozzi

A.L.

, An MBO Scheme on Graphs for Classification and Image Processing, SIAM Journal on Imaging Sciences 6(4) (2013), 1903–1930.

16.

Merkurjev

Garcia-Cardona

Bertozzi

A.L.

Flenner

and Percus

A.G.

, Diffuse interface methods for multiclass segmentation of high-dimensional data, Applied Mathematics Letters 33 (2014), 29–34.

17.

Merkurjev

Sunu

and Bertozzi

A.L.

, Graph MBO method for multiclass segmentation of hyperspectral stand-off detection video, in: 2014 IEEE International Conference on Image Processing, 2014, pp. 689–693.

18.

Szlam

and Bresson

, A total variation-based graph clustering algorithm for Cheeger ratio cuts, in: Proceedings of the 27th International Conference on Machine Learning, 2010, pp. 1039–1046.

19.

Bresson

Tai

X.-C.

Chan

T.F.

and Szlam

, Multi-class transductive learning based on ℓ1 relaxations of cheeger cut and mumford-shah-potts model, Journal of Mathematical Imaging and Vision 49(1) (2014), 191–201.

20.

Bresson

Laurent

Uminsky

and von Brecht

, Multiclass total variation clustering, Advances in Neural Information Processing Systems (2013), 1421–1429.

21.

Merkurjev

Bae

Bertozzi

A.L.

and Tai

X.-C.

, Global binary optimization on graphs for classification of high-dimensional data, Journal of Mathematical Imaging and Vision 52(3) (2015), 414–435.

22.

Zhou

and Schölkopf

, A Regularization Framework for Learning from Graph Data, in: International Conference on Machine Learning, 2004, pp. 132–137.

23.

Zhou

Bousquet

Lal

T.N.

Weston

and Schölkopf

, Learning with local and global consistency, Advances in Neural Information Processing Systems 16 (2004), 321–328.

24.

Wang

Jebara

and Chang

S.F.

, Graph transduction via alternating minimization, in: Proceedings of the 25th International Conference on Machine Learning, 2008, pp. 1144–1151.

25.

D’souza

R.N.

Huang

P.-Y.

and Yeh

F.-C.

, Small data challenge: structural analysis and optimization of convolutional neural networks with a small sample size, Scientific Reports 10(1) (2020), 834.

26.

Zhu

Meng

Ding

and Yang

, Weighted pooling for image recognition of deep convolutional neural networks, Cluster Computing 22(4) (2019), 9371–9383.

27.

LeNet-5 in 9 lines of code using Keras. https://medium.com/@mgazar/lenet-5-in-9-lines-of-code-using-keras-ac99294c8086.

28.

Dutta

and Gros

, Evaluation of the impact of deep learning architectural components selection and dataset size on a medical imaging task, Medical Imaging 2018: Imaging Informatics for Healthcare, Research, and Applications 10579 (2018), 1057911.

29.

Text Classification With Word2Vec. http://nadbordrozd.github.io/blog/2016/05/20/text-classification-with-word2vec/.

30.

Sug

, The effect of training set size for the performance of neural networks of classification, WSEAS Transactions on Computers 9(9) (2010), 1297–1306.

31.

Zubiaga

Fresno

and Martinez

, Is unlabeled data suitable for multiclass SVM-based web page classification? in: Proceedings of the 2009 Workshop on Semi-Supervised Learning for Natural Language Processing, 2009, pp. 28–36.

32.

Lanquillon

, Enhancing text classification to improve information filtering, PhD thesis, DaimlerChrysler AG, Research and Technology, 2001.

33.

Chen

and Kuo

C.J.

, PixelHop: A Successive Subspace Learning (SSL) Method for Object Recognition, Journal of Visual Communication and Image Representation (2020), 102749.

34.

Bruna

and Mallat

, Classification with invariant scattering representations, in: 2011 IEEE 10th IVMSP Workshop: Perception and Visual Signal Analysis, 2011, pp. 99–104.

35.

Levatić

Ceci

Kocev

and Džeroski

, Semi-supervised classification trees, Journal of Intelligent Information Systems 49(3) (2017), 461–486.

36.

Lesort

Caselles-Dupré

Garcia-Ortiz

Stoian

and Filliat

, Generative models from the perspective of continual learning, in: 2019 International Joint Conference on Neural Networks, 2019, pp. 1–8.

37.

Schönhofen

, Identifying document topics using the Wikipedia category network, Web Intelligence and Agent Systems: An International Journal 7(2) (2009), 195–207.

38.

Guan

and Yuan

, A survey of mislabeled training data detection techniques for pattern classification, IETE Technical Review 30(6) (2013), 524–530.

39.

Wilson

D.L.

, Asymptotic properties of nearest neighbor rules using edited data, IEEE Transactions on Systems, Man, and Cybernetics (1972), 408–421.

40.

Penrod

C.S.

and Wagner

T.J.

, Another look at the edited nearest neighbor rule., Technical Report, Texas University at Austin, Department of Electrical Engineering, 1976.

41.

Tomek

, An experiment with the edited nearest-neighbor rule, IEEE Transactions on Systems, Man, and Cybernetics (1976), 448–452.

42.

Ferri

F.J.

Albert

J.V.

and Vidal

, Considerations about sample-size sensitivity of a family of edited nearest-neighbor rules, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 29(5) (1999), 667–672.

43.

Hattori

and Takahashi

, A new edited k-nearest neighbor rule in the pattern classification problem, Pattern Recognition 33(3) (2000), 521–528.

44.

Sánchez

J.S.

Barandela

Marqués

A.I.

Alejo

and Badenas

, Analysis of new techniques to obtain quality training sets, Pattern Recognition Letters 24(7) (2003), 1015–1022.

45.

Sánchez

J.S.

Pla

and Ferri

F.J.

, Prototype selection for the nearest neighbour rule through proximity graphs, Pattern Recognition Letters 18(6) (1997), 507–513.

46.

Brodley

C.E.

and Friedl

M.A.

, Improving automated land cover mapping by identifying and eliminating mislabeled observations from training data, International Geoscience and Remote Sensing Symposium 2 (1996), 1382–1384.

47.

Brodley

C.E.

and Friedl

M.A.

, Identifying mislabeled training data, Journal of Artificial Intelligence Research 11 (1999), 131–167.

48.

Verbaeten

and Van Assche

, Ensemble methods for noise elimination in classification problems, in: International Workshop on Multiple Classifier Systems, 2003, pp. 317–325.

49.

Breiman

, Bagging predictors, Machine Learning 24(2) (1996), 123–140.

50.

Quinlan

J.R.

, Bagging, boosting, and C4. 5, Proceedings of the Thirteenth National Conference on Artificial Intelligence 1 (1996), 725–730.

51.

Freund

and Schapire

R.E.

, Experiments with a new boosting algorithm, Proceedings of the Thirteenth International Conference on International Conference on Machine Learning 96 (1996), 148–156.

52.

John

G.H.

, Robust Decision Trees: Removing Outliers from Databases, in: KDD, Vol. 95, 1995, pp. 174–179.

53.

Quinlan

J.R.

, C4. 5: programs for machine learning, Elsevier, 2014.

54.

Zeng

and Martinez

, A noise filtering method using neural networks, in: IEEE International Workshop on Soft Computing Techniques in Instrumentation, Measurement and Related Applications, 2003, pp. 26–31.

55.

Reed

Lee

Anguelov

Szegedy

Erhan

and Rabinovich

, Training deep neural networks on noisy labels with bootstrapping, in: International Conference on Learning Representations, 2015.

56.

Bouguelia

M.-R.

Belaïd

and Belaïd

, Stream-based active learning in the presence of label noise, in: 4th International Conference on Pattern Recognition Applications and Methods, 2015.

57.

Damodaran

B.B.

Fatras

Lobry

Flamary

Tuia

and Courty

, Wasserstein adversarial regularization (WAR) on label noise, arXiv preprint arXiv:1904.03936, 2019.

58.

Abellán

Castellano

J.G.

and Mantas

C.J.

, A new robust classifier on noise domains: bagging of Credal C4. 5 trees, Complexity, 2017.

59.

Abbasi

Shiri

M.E.

and Ghatee

, A regularized root-quartic mixture of experts for complex classification problems, Knowledge-Based Systems 110 (2016), 98–109.

60.

Liu

Lian

and Zuo

, Multi-view representation learning in multi-task scene, Neural Computing and Applications (2019), 1–20.

61.

Crammer

and Gentile

, Multiclass classification with bandit feedback using adaptive regularization, Machine Learning 90(3) (2013), 347–383.

62.

Merriman

Bence

J.K.

and Osher

, Diffusion generated motion by mean curvature, AMS Selected Lectures in Mathematics Series: Computational Crystal Growers Workshop 8966 (1992), 73–83.

63.

Esedoḡlu

and Otto

, Threshold dynamics for networks with arbitrary surface tensions, Communications on Pure and Applied Mathematics 68(5) (2015), 808–864.

64.

Ruuth

S.J.

, A diffusion generated approach to multiphase motion, Journal of Computational Physics 145 (1998), 166–192.

65.

Ruuth

S.J.

, Efficient algorithms for diffusion-generated motion by mean curvature, Journal of Computational Physics 144 (1998), 603–625.

66.

Ruuth

S.J.

and Wetton

, A simple scheme for volume-preserving motion by mean curvature, Journal of Scientific Computing 19(1) (2003), 373–384.

67.

Ruuth

S.J.

and Merriman

, Convolution generated motion and generalized Huygens’ principles for interface motion, SIAM Journal on Applied Mathematics 60 (2000), 868–890.

68.

Osher

and Sethian

, Fronts propagating with curvature-dependent speed: algorithms based on hamilton-jacobi formulation, Journal of Computational Physics 79 (1988), 12–49.

69.

Peng

Merriman

Osher

Zhao

H.-K.

and Kang

M.J.

, A PDE-based fast local level set method, Journal of Computational Physics 155(2) (1999), 410–438.

70.

Saye

R.I.

and Sethian

J.A.

, The Voronoi implicit interface method for computing multiphase physics, Proceedings of the National Academy of Sciences 108 (2011), 19498–19503.

71.

Wang

and Wang

, An efficient threshold dynamics method for wetting on rough surfaces, Journal of Computational Physics 330 (2017), 510–528.

72.

Zhao

H.-K.

Merriman

Osher

and Wang

, Capturing the behavior of bubbles and drops using the variational level set approach, Journal of Computational Physics 143 (1998), 495–512.

73.

Elsey

and Esedoḡlu

, Threshold dynamics for anisotropic surface energies, AMS Mathematics of Computation 87 (2018), 1721–1756.

74.

Esedoḡlu

and Jacobs

, Convolution kernels, and stability of threshold dynamics methods, SIAM Journal on Numerical Analysis 55(5) (2017), 2123–2150.

75.

Esedoḡlu

Jacobs

and Zhang

, Kernels with prescribed surface tension and mobility for threshold dynamics schemes, Journal of Computational Physics 337 (2017), 62–83.

76.

Bertsekas

D.P.

, A Distributed Algorithm for the Assignment Problem, Laboratory for Information and Decision Systems, 1979.

77.

Bertsekas

, Network Optimization: Continuous and Discrete Models, Athena Scientific, 1998.

78.

LeCun

and Cortes

, The MNIST Database of Handwritten Digits. http://yann.lecun.com/exdb/mnist/.

79.

Fashion MNIST Data Set. https://github.com/zalandoresearch/fashion-mnist.

80.

Optical Recognition of Handwritten Digits Data Set. https://archive.ics.uci.edu/ml/datasets/optical+recognition+of+handwritten+digits.

81.

WebKB data set. http://www.cs.cmu.edu/afs/cs.cmu.edu/project/theo-20/www/data/.

82.

Cardoso-Cachopo

, Improving Methods for Single-label Text Categorization, PhD thesis, Universidade Tecnica de Lisboa, 2007.

83.

Reuters Data Set. https://www.cs.umb.edu/∼smimarog/textmining/datasets/.

84.

20 Newsgroups Data Set. http://qwone.com/∼jason/20Newsgroups/.

85.

Statlog (Landsat Satellite) Data Set. https://archive.ics.uci.edu/ml/datasets/Statlog+(Landsat+Satellite).

86.

Pen-Based Recognition of Handwritten Digits Data Set. https://archive.ics.uci.edu/ml/datasets/Pen-Based+Recognition+of+Handwritten+Digits.

87.

LIBSVM – A Library for Support Vector Machines. https://www.csie.ntu.edu.tw/∼cjlin/libsvm/.

88.

Quinlan

J.R.

, C4. 5: Programs for machine learning, Morgan Kaufmann Publishers, Inc., 1993.

89.

Ramos

, Using tf-idf to determine word relevance in document queries, Proceedings of the First Instructional Conference on Machine Learning 242 (2003), 133–142.

A graphical approach for multiclass classification and for correcting the labeling errors in mislabeled training data

Abstract

Keywords

1. Introduction

Main contributions

2.1 Graphical framework

2.2 Previous work

2.2.1 Data classification methods

2.2.2 Approaches for handling mislabeled training data

3. Modified auction dynamics for multiclass classification

3.1 Notation

3.2 Derivation of the algorithm

.

Proof..

.

Proof..

.

Proof..

.

Proof..

4.3 Experiments with different amounts of corrupted training labels

Table 1 Timing results for Algorithm 1 (not including weight matrix W construction)

4.5 Experiments with noise in attribute information

4.6 Timing

5. Conclusion

Footnotes

Appendix

Upper and lower bound auctions

References

Table 1
Timing results for Algorithm 1 (not including weight matrix $W$ construction)