CROSS REFERENCE TO RELATED APPLICATIONS

[0001] This application claims priority to copending U.S. provisional application entitled "CLASSIFICATION USING CORRENTROPY" having serial no. 61/366,662, filed July 22, 2010, which is entirely incorporated herein by reference.

STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT

[0002] This invention was made with Government support under Grant ECS -0601271 awarded by the National Science Foundation. The Government has certain rights in this invention.

BACKGROUND

[0003] Classification assigns labels to data based upon a decision rule. A convex surrogate loss function is used as the training loss function in many classification procedures. Within the statistical learning community, convex surrogates are preferred because of the virtues that convexity brings - unique optimum, efficient optimization using convex optimization tools, amenability to theoretical analysis of error bounds, etc. However, convex functions are poor approximations for a wide variety of problems. BRIEF DESCRIPTION OF THE DRAWINGS

[0004] Many aspects of the present disclosure can be better understood with reference to the following drawings. The components in the drawings are not necessarily to scale, emphasis instead being placed upon clearly illustrating the principles of the present disclosure. Moreover, in the drawings, like reference numerals designate corresponding parts throughout the several views.

[0005] FIG. 1 is a graph illustrating examples of surrogate loss functions in accordance with various embodiments of the present disclosure.

[0006] FIG. 2 is a graph illustrating examples of correntropy loss (c-loss) functions in accordance with various embodiments of the present disclosure.

[0007] FIG. 3 is an example of an empirical risk function in a 2D space of errors in accordance with various embodiments of the present disclosure.

[0008] FIGS. 4 and 6 are graphical representations of examples of systems for robust classification using c-loss functions of FIG. 2 in accordance with various embodiments of the present disclosure.

[0009] FIG. 5 is a graph illustrating an example of derivatives of a c-loss function versus kernel width in accordance with various embodiments of the present disclosure.

[0010] FIG. 7 is a flow chart illustrating an example of robust classification using the systems of FIGS. 4 and 6 in accordance with various embodiments of the present disclosure.

[0011] FIGS. 8A-8F, 9A-9C, and 10A-10C are graphs of examples of classification results based at least in part upon a c-loss function module using the systems of FIGS. 4 and 6 in accordance with various embodiments of the present disclosure.

[0012] FIG. 11 is a graphical representation of an example of a processing device used to implement at least a portion of the systems of FIGS. 4 and 6 in accordance with various embodiments of the present disclosure.

DESCRIPTION

[0013] Embodiments disclosed herein include systems and methods for robust classification using correntropy. For example, this application describes a loss function for classification that is induced by correntropy, referred to as the c-loss function. A discriminant function is obtained by optimizing the c-loss function using a neural network that is substantially insensitive to outliers and resilient to overfitting and overtraining. This potentially leads to better generalization performance when compared to a squared loss function, which is common in neural network classifiers. The described methods of training classifiers may provide a practical way of obtaining better results on real world classification problems, and an exemplary embodiment uses a simple gradient-based online training procedure for reducing the empirical risk.

[0014] Classification aims at assigning class labels to data (patterns) using an Optimal' decision rule that is learned using a set of pre-labeled training samples. This 'optimal' decision rule or discriminant function / is learned by minimizing an empirical risk, which is a sample average of a loss function. The loss (a function of the prediction f(x) and the true label y ) may be thought of as the price paid for predicting the label to be /(x) , instead of y . The procedure for learning the discriminant function / is called empirical risk minimization.

[0015] A natural loss function for classification is the misclassification error rate (or the 0-1 loss) stated in:

where (.) ₊ denotes the positive part and || . || ₀ denotes the L ₀ norm. The misclassification error rate may be thought of as a count of the number of incorrect classifications made by the discriminant function / . Therefore, a

0-1 loss function directly relates to the probability of misclassification.

[0016] Optimization of the risk based on such a loss function, however, is computationally intractable due to its non-continuity and non-convexity. Therefore, a surrogate loss function is used as the training loss function. Correntropy between two random variables is a generalized correlation function or a robust measure of statistical similarity, that makes use of higher order statistics. In a classification setting, maximizing the similarity between the prediction /(x) and the target y in the correntropy sense effectively induces a non-convex, smooth loss function (or c-loss) that may be used to train the classifier using an online gradient based technique. This loss function is used to train a neural network classifier using backpropagation without an increase in computational complexity.

[0017] Given a sample set of observations D _n = {(x„ >,·), = 1, 2, n} , assumed to be independent and identically distributed (i.i.d.) realizations of a random pair (X, Y), the goal of classification is to select a function / from a class of functions ⁷ , such that the sign of /(x) is an accurate prediction of Y under an unknown joint distribution P(X, Y). Here, X e X is the input vector and Y {-1 , 1 } is the class label. In other words, select / <≡ T that minimizes the risk R{f) given by:

R(f) = (Yf(X))] = (Y≠ sign(f(X))) . EQN. 2

[0018] The product is called the margin (denoted by a ) and can be treated as a measure of correctness of the decision for the sample X . Given the sample set D _n of realizations, an empirical risk (e.g., the sample average of the 0-1 loss) is as expressed by:

[0019] Optimization of the empirical risk as expressed above, however, is computationally intractable primarily because of the discontinuity of the 0-1 loss function. Due to the discontinuity of the 0-1 loss function, the optimization procedure involves choosing a surrogate φ(α) = φ(γ/(χ)) as the loss function. What results is the minimization of the -risk and empirical φ- risk defined by:

R _≠ (f) = E[^Yf(X))] EQN. 4

1 "

ήφ(Ι) = -∑ <>(y (*,)) EQN. 5

[0020] Referring to FIG. 1 , shown is a graph 100 of two commonly used surrogate loss functions φ versus a margin a . The first surrogate loss function φ (103) is a hinge loss function used in support vector machines (SVMs). The SVM uses the hinge loss, [\ - yf(x)] ₊ . The second surrogate loss function φ (106) is a square loss function used in training neural networks, radial basis function networks, etc. The loss function for training the weights of a neural network or a radial basis function network is typically the square loss function, (y - f(x)) ² , or .

[0021] Within the statistical learning community, convex surrogates of the 0-1 loss function are preferred because of the virtues that convexity brings: unique optima, efficient optimization using convex optimization tools, amenability to theoretical analysis of error bounds, etc. However, convex surrogates are poor approximations to the 0-1 loss function. Convex surrogates tend to be boundless and offer poor robustness to outliers. Another important limitation is that the complexity of convex optimization algorithms grows quickly as the amount of data increases.

[0022] There is a large class of problems where optimization cannot be done using convex programming techniques. For example, the training of deep networks for large scale artificial intelligence (Al) problems primarily relies on online, gradient-based methods. Such neural network based classification machines can benefit from non-convex surrogates, as they can potentially be closer approximations to the 0-1 loss function. Additionally, non-convex surrogates can have better scalability, robustness, and generalization performance. Although non-convex surrogates do not offer many theoretical guarantees, the empirical evidence that they work better in practical engineering applications is overwhelming.

[0023] An example of a loss function for classification that utilizes a statistical measure called correntropy is described. Correntropy is a generalized correlation function or a robust measure of statistical similarity between two random variables that makes use of second and higher order statistics. In a classification setting, maximizing the similarity between the prediction /(x) and the target y in the correntropy sense, effectively generates (i.e., induces) a non-convex, smooth loss function (referred to as a c-loss function) that can be used to train the classifier using an online gradient-based technique. The c-loss function is used to train a neural network classifier using backpropagation. Without any increase in computational complexity, a better generalization performance on real world datasets may be obtained using the c-loss function when compared to the traditional squared loss function in neural network classifiers.

[0024] Cross correntropy, or simply correntropy, between two random variables X and Y is a generalized similarity measure defined as: ν(Χ, Υ = Ε[κ _σ (Χ - Υ)] , EQN. 6 where κ _σ is a Gaussian kernel with width parameter σ . In practice, given only a finite number of realizations of the random variables, correntropy between the random variables is computed as:

[0025] Correntropy is a measure of how similar two random variables are, within a small neighborhood determined by the kernel width σ . In contrast, metrics like mean squared error (MSE) provide a global measure. The localization provided by the kernel width proves to be very useful in reducing the detrimental effects of outliers and impulsive noise.

[0026] In a classification setting, the similarity between the classifier output and the true label is maximized, in the correntropy sense. Therefore, the loss function should be chosen such that minimization of the expected risk is equivalent to maximization of correntropy. The correntropy induced loss function or the c-loss function is defined as:

[0027] The c-loss function can also be expressed in terms of the classification margin a = yf(x) as:

1 ₍ ,{α) = β[\ - κ _σ {\ - α)] , EQN. 9

where β is a positive scaling constant chosen such that l ₍ .(a = 0) = \ .

Therefore, β =

[0028] Referring next to FIG. 2, shown is a graph 200 of the c-loss function for different values of the kernel width parameter σ plotted against the margin a . The 0-1 loss is also shown. As can be seen in FIG. 2, the c- loss function is a better approximation of the 0-1 loss function as compared to the squared or hinge loss functions, which are illustrated in FIG. 1.

[0029] The expected risk associated with the c-loss function is expressed by:

R {f) = β (\ - Ε[κ _σ (\ - γβ{χ))]) EQN. 11

= /?(l -v(r,/(X))) EQN. 13

[0030] Minimizing the expected risk is equivalent to maximizing the similarity (in the correntropy sense) between the predicted label f(x) and the true label y . Upon changing variables based on s = Y - f(X) , the estimator of correntropy can be written as: v(e) = -f _i K _a (e _l ) EQN. 14

[0031] From the Parzen density estimation principle, it can be seen that EQN. 14 is an estimator of the probability density function ( pdf ) of ε , evaluated at 0. Therefore, maximizing the correntropy of the errors ε of a classifier, essentially maximizes ρ(ε = 0) . This is a more natural quantity to optimize for a classifier, as compared with quantities such as the sum of squared errors.

[0032] In the space of the errors e = y - fix), the empirical risk obtained using the c-loss function behaves like the L ₂ norm for small errors (i.e., samples correctly classified with high confidence). As the errors increase, it behaves like the L _\ norm and approaches the L ₀ norm for very large errors (i.e. , misclassified samples). The kernel size (or, equivalently, the distance from the origin in the space of errors) dictates the rate at which the empirical risk transitions from L ₂ to L ₀ behavior in the error space. FIG. 3 depicts an example of the transition from an L ₂ norm like behavior close to the origin, to Lo behavior far away, with an L _\ like region in between. The empirical risk function in the 2D space of errors e = y - fix) of FIG. 3 was obtained using the c-loss function with σ = 0.5.

[0033] The c-loss function is a non-convex function of the margin. Therefore, it is difficult to optimize the c-loss function using sophisticated convex optimization techniques in order to obtain the optimal discriminant function / . However, since the c-loss function is a smooth function, it is possible to optimize the c-loss function using, for example, a first order (steepest descent) or a second order (e.g., Newton's method) gradient-based procedure, or a combination thereof (e.g., a conjugate gradient, a Hessian approximation method (e.g., a Levenberg-Marquardt algorithm)). The c-loss function is used to train a neural network classifier by backpropagating the errors using any of the gradient-based methods discussed above.

[0034] From the equations involved in backpropagation, it can be observed that the magnitude of the derivative of the loss function, with respect to the current value of the error, controls the size of the steps in the weight update equation. In other words, the derivative of the loss evaluated at the current value of the error, controls how much the discriminant function (weights) are influenced by the input sample that produced the error.

[0035] FIG. 4 is a block diagram illustrating a nonlimiting embodiment of a system for robust classification using correntropy. The system 400a includes a classifier 403, a c-loss function module 406, a gradient-based module 409, and a weight update module 412. The classifier 403 classifies a value of x by predicting the label to be . The c-loss function module 406 determines a statistical similarity between the predicted label and the true label y using correntropy as described in EQN. 7 above. The c-loss function module 406 outputs a c-loss value described by EQNS. 9 and 10 above.

[0036] The gradient-based module 409 calculates a change in the c-loss values, which minimizes the expected risk as described in EQN. 14 above, for example. In various embodiments, the gradient-based module 409 is a first, second, or mixed order gradient-based module, for example. The gradient- based module 409 outputs the change to the weight update module 412, which updates the weights for the classifier based at least in part on a c-loss value and the change in c-loss values calculated by the gradient-based module 409.

[0037] The c-loss function is a non-convex function of the margin. Therefore it is difficult to optimize it using sophisticated convex optimization techniques, in order to obtain the optimal discriminant function / . However, since it is a smooth function, it is possible to optimize it using gradient based procedures. We therefore use the c-loss function to train a neural network classifier by backpropagating the errors using gradient descent.

[0038] Before deriving the backpropagation equations, the notation used to denote the variables in a neural network is summarized below for convenience. w"k ^' ■ The weight between the processing element (PE) k and the PE j th

of the previous layer, at the n iteration. y j : Output of the PE j of the previous layer, at the n iteration. n \ ¹ n ⁿ n

net k - 7 , J , w : Weighted sum of all outputs y , of the previous th

layer, at the n iteration. g( ): Sigmoidal squashing function in each PE, g\ ^z ) = : EQN. 15 l+e ^' y" _k = S(netk) : Output of the PE k of the current layer, at the n ^th iteration. y" e {±1} : The true label (or desired signal), for the n ^th sample.

[0039] The weights of a multilayer perceptron (MLP) may be updated by moving opposite to the gradient of the empirical risk computed using the c- loss function:

„ dRc (e)

Wjk - Wjk - M „ . EQN. 16

OWjk

Using the chain rule, the above equation can be written as:

oe _n

Since this is an online procedure, the derivative of the risk with respect to the

th

error at n iteration, e„, is essentially the derivative of the c-loss function, evaluated at e _n . Therefore, n+\ _ n lc { ^e ) _. η _Λ ^η

wjk - Wjk + g xnethWj EQN 18 oe _n

The above equation is the general rule for updating all the weights of the MLP, and it is called the Delta rule, written simply as:

Wjk = Wjk + Md _k y _j , EQN. 19 where,

O k - g ynetk) . EQN. 20 oe _n

[0040] Depending on the cost function, and the type of weights (belonging to output layer or hidden layer), the computation of Si in the above equation differs. For the output layer weights, the computation is as follows: dlc (e)

O k - d o - g'ineto) EQN. 21 de _n

A

where ?, = β/σ ² ■ For the previous (hidden) layer, the 'deltas' are computed as:

where N ₀ is the number of output layer PEs.

[0041] EQNS. 22 and 23 can be used to update or train the weights of a neural network classifier using the c-loss function. The computational complexity of the weight updates remains the same as in the case of the conventional square loss function.

[0042] From EQNS. 19 and 20, it can be seen that the magnitude of the derivative of the loss function, with respect to the current value of the error, essentially controls the size of the steps in the weight update equation. In other words, the derivative of the loss evaluated at the current value of the error, controls how much the discriminant function (weights) are influenced by the input sample that produced the error.

[0043] Referring to FIG. 5, shown is a graph 500 illustrating an example of derivatives of the c-loss function versus kernel width σ . For comparison purposes, the derivative of the square loss function (which results in a linear function) is also shown. The derivatives are plotted as a function of the error th

e _n produced by the n input sample. Therefore, if 1 <| e _n \< 2 , the sample is misclassified, and if 0 <| e _n |< 1 , the sample is correctly classified. As can be seen in FIG. 4, if the square loss function is used, the samples which produce high errors (i.e. , samples which are badly misclassified) yield a high derivative. This means that the weights or the decision boundary of the classifier is highly affected by outliers or impulsive input samples. In contrast, the derivative of the c-loss function attenuates the influence of highly erroneous samples while computing the weights or the discriminant function. Since the discriminant function is insensitive to these outliers, better generalization can be obtained in real world datasets which are often plagued with noisy samples.

[0044] Also, for a kernel size like σ = 0.5, the effect of samples near the decision boundary (e = 1) is also attenuated. This means that 'confusing' samples which lie near the decision boundary are not given much importance while learning the classifier. This results in a more regularized solution that is less prone to overfitting due to overtraining.

[0045] The localization provided by the kernel in the c-loss function makes the gradient descent algorithm susceptible to getting stuck in local minima. Therefore, the c-loss function may be useful primarily in the vicinity of the optimal solution. One approach is to first allow convergence using the traditional square loss function and then switch to the c-loss function. Another approach using a weighted combination of the two loss functions instead is described by: Combined loss function = « * (C - loss) + (1 - a)* (Square - loss) EQN. 15

[0046] The value of a is linearly increased from 0 to 1 , over the total number of training epochs. Therefore, for the i ^th epoch, a _t = i/N , where N is the total number of training epochs. Such an approach means that the square loss function is used in the beginning of training, and there is a smooth switch over to the c-loss function towards the end of training.

[0047] Referring to FIG. 6, shown is a block diagram illustrating another nonlimiting embodiment of a system for robust classification using correntropy. Similar to the system 400a illustrated in FIG. 4, the system 400b in FIG. 6 includes a classifier 403, a gradient-based module 409, and a weight update module 412. However, the system 400b includes a combined loss function module 606 instead of merely a c-loss function module 406. The combined loss function module 606 determines a statistical similarity using a weighted combination of the c-loss function and the square loss function. The combined loss function module 606 outputs a combined loss function based at least in part on EQN. 15 above.

[0048] FIG. 7 is a flow chart illustrating a nonlimiting embodiment of a method of robust classification using correntropy. The method 700 includes boxes 703, 706, 709, and 712. In box 703, a data value is classified by predicting a label for the data value using a discriminant function including a plurality of weights. In box 706 a statistical similarity between the predicted label and an actual label is determined based at least in part on a correntropy loss function. In some embodiments, the statistical similarity is also based at least in part on a square loss function. Further, the statistical similarity may be based at least in part on a weighted combination of the correntropy loss function and the square loss function (referred to herein as a combined loss function). In box 709, the expected risk associated with the predicted label is minimized based at least in part on the statistical similarity. The minimization of the expected risk includes calculating a gradient of (i.e., change in) the statistical similarity. In box 712, the weights of the discriminant function are updated based at least in part on the minimized expected risk.

[0049] For purposes of comparison, the performance of neural network classifiers trained with the c-loss function and the traditional square loss function were used in classifying the Pima Indians Diabetes dataset. This data includes eight physiological measurements (features) from 768 subjects. The objective was to classify a test subject into either the diabetic or non- diabetic group, based on these physiological measurements. Out of the 768 samples, 400 samples were used to train the classifier, and the remaining samples were used to test for generalization.

[0050] Networks having a single hidden layer and a sigmoidal non- linearity are used in each of the PEs. The datasets used are normalized to have unit variance along each feature. The networks were trained with 10 epochs of the training dataset. The kernel size σ in the c-loss function was set to be 0.5. Other values of kernel size such as 0.6 and 0.7 were also tried, with little change in performance. The generalization performance for both the methods was obtained by testing on a separate test dataset.

[0051] FIGS. 8A-8F are graphs of percentage of correct classification for a system 400 including a c-loss function module and a system including a square loss function, versus number of training epochs, for the Pima Indians Diabetes dataset. The total number of training epochs varies in each figure such that the total number of training epochs is respectively 200, 100, 50, 30, 15, and 5 in FIGS. 8A, 8B, 8C, 8D, 8E, and 8F. In these evaluations, the c- loss function was implemented using the combined loss function as described by EQN. 15, in order to avoid local minima. FIGS. 8A-8F illustrate how the c- loss function improves the classification performance compared to the square loss function, over the training epochs. These plots were obtained after averaging over 100 Monte Carlo simulations with random initial weights of the network and random selection of training samples from the datasets.

[0052] In addition, the effect of the number of PEs on the classification results was examined using the Pima Indians Diabetes dataset. The evaluation was repeated with 5, 10 and 20 PEs in the hidden layer of the MLP using the two loss functions. Referring to FIGS. 9A-9C, shown are the graphs of examples of the percentage of correct classification for 5, 10 and 20 PEs in the hidden layer, respectively. The average classification performance (on the test set) computed from 100 Monte Carlo trials is shown for different training durations (epochs). The tables in FIGS. 9A, 9B, and 9C illustrate the evaluation results for 5, 10 and 20 PEs, respectively. In each of the three tables, the best performance of c-loss function is better than that obtained by the square loss. In these evaluations, in order to avoid local optima, training was carried out by first training with the square loss function and then switching over to the c-loss function. Since the switch to the c-loss function is made only after the 5th epoch, the first 5 values for the c-loss results are not shown. As indicated in the graphs of FIGS. 9A-9C, generalization performance improves with use of the c-loss function. [0053] Comparison of the classification using a c-loss function module and using a square loss function was also performed using a Wisconsin Breast Cancer dataset. This dataset consists of nine-dimensional samples, belonging to two classes. Out of the 683 samples, 300 were used to train the classifiers. Referring to FIGS. 10A-10C, shown are the graphs of examples of the percentage of correct classification for 5, 10 and 20 PEs in the hidden layer, respectively. Along the same lines as the examination of FIGS. 9A-9C, the mean classification performance is tabulated for both the loss function, for various training epochs. The c-loss function again outperforms the square loss function in terms of generalization. As indicated in the graphs of FIGS. 10A-9C, the use of the c-loss function after the 5th epoch provides an improvement in classification performance.

[0054] The systems and methods provided herein can be implemented in hardware, software, firmware, or a combination thereof. In one embodiment, the method can be implemented in software or firmware that is stored in a memory and that is executed by a suitable instruction execution system. If implemented in hardware, as in an alternative embodiment, the system can be implemented with any or a combination of the following technologies, which are all well known in the art: a discrete logic circuit(s) having logic gates for implementing logic functions upon data signals, an application specific integrated circuit (ASIC) having appropriate combinational logic gates, a programmable gate array(s) (PGA), a field programmable gate array (FPGA), digital signal processor (DSP), etc.

[0055] In some embodiments, the adaptive systems described above may be implemented in a processing device 1 100 such as the one illustrated in FIG. 1 1 . The signal processing device 1 100 includes a receiver 1 103, transmitter 1 106, processing unit 1 109, a bus 1 1 12 and a memory 1 1 15. The memory 1 1 15 stores an application specific software 1 1 18 including modules that include instructions that when executed by the processing unit 1 109 perform various operations. In the embodiment illustrated in FIG. 1 1 , the modules include, for example, classifier 1 121 , a c-loss module 1 24, a gradient-based module 1 127, and weight update module 1 130. In other embodiments, the application software includes a combination loss function module configured to apply a combination of a c-loss function and a square loss function to an input predicted label and an actual label.

[0056] The application specific software 1 1 18 can also be stored on a variety of computer-readable media for use by, or in connection with, a variety of computer-related systems or methods. In the context of this disclosure, a "computer-readable medium" stores, communicates, propagates, or transports the program for use by or in connection with the instruction execution system, apparatus, or device. The computer readable medium can be, for example, but not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device. More specific examples (a non-exhaustive list) of the computer-readable medium may include the following: an electrical connection (electronic) having one or more wires, a portable computer diskette (magnetic), a random access memory (RAM) (electronic), a read-only memory (ROM) (electronic), an erasable programmable read-only memory (EPROM, EEPROM, or Flash memory) (electronic), an optical fiber (optical), a portable compact disc read- only memory (CDROM) (optical), a digital versatile disc (optical), a high definition digital versatile disc (optical), and a Blu-ray Disc (optical).

[0057] Any process descriptions or blocks should be understood as representing modules, segments, or portions of code which include one or more executable instructions for implementing specific logical functions or steps in the process, and alternate implementations are included within the scope of the embodiments described in the present disclosure in which functions may be executed out of order from that shown or discussed, including substantially concurrently or in reverse order, depending on the functionality involved, as would be understood by those reasonably skilled in the art of the present disclosure.

[0058] It should be emphasized that the above-described embodiments in the present disclosure are merely possible examples of implementations, merely set forth for a clear understanding of the principles of the disclosure. Many variations and modifications may be made to the above-described embodiment(s) of the disclosure without departing substantially from the spirit and principles of the disclosure. All such modifications and variations are intended to be included herein within the scope of this disclosure and the present disclosure and protected by the following claims.