A robust approach to the design of machine learning algorithms, based on minimising finite sums of the parametrised functions is considered. This method implies using robust finite-sum differentiable aggregating functions that are resistant to outliers.
1. Introduction parametrised functions: The majority of machine learning problems can be reduced to problem of minimising finite sums of (w) =
∑ ℓ (w), where ℓ1(), … , ℓ () ∈ ⊆ ℝ , 1, … , – are non-negative basis functions,
– is the vector of unknown parameters, ≥ 0 – is nonnegative weights. Most often = const, for example, 1 (arithmetic sum) or 1/ (arithmetic mean). target function is minimised by the optimal set of parameters ∗ : ( ∗ ) = min ( ).
∈ Most of algorithms for neural networks (NN) learning are based on this principle. In particular back propagation (BP) algorithm is based on minimisation of arithmetic mean squared errors. ()
However, if the distribution of the basic functions values contains outliers, the minimization of , as a rule, leads to a distortion of ∗. This is due to the fact that the arithmetic sum and the arithmetic mean are not resistant to the outliers.
Of course, the problem of outliers could be solved by choosing the values of the weights 1, … , , which, on the one hand, would suppress the values of outliers, and on the other hand, leave the rest left unchanged. However, the selection of such weights is difficult task and is essentially equivalent by the complexity to identifying the outliers in the empirical distribution {ℓ1( ∗), … , ℓ ( ∗)}.
One of the effective way of dealing with this problem is to use robust aggregation functions to calculate the sum or average. Thus, we get definitions for the function : for robust estimation of a mean () = med =1,…
ℓ () − =1 ( ) =
∑ ℓ( ) ( )
with ℓ () = ((
Squares) [
2 there have been proposed LMedS and LTS (Least Trimmed Last sum could be rewritten as trimmed arithmetical mean: () =
1 − − =1 ∑ ℓ() () Minimizing the above estimates on data with outliers (up to 50%) allows finding adequate estimates for ∗. However, minimization algorithms for LTS and LMS include a combinatorial component form of ∗ search through subsets, since their gradients are singular. It makes application of gradient based algorithms almost impossible. This also reduces the scalability of such algorithms and their application in training neural networks and in problems with big data.
Another way of robust estimation of ∗ is using a winsorized sum or an average =1 1
=1 () =
∑ max {ℓ (), ℓ ()}
∑ max {ℓ ( ), ℓ( )}, where ℓ()
is threshold value for the empirical distribution {ℓ1(), … , ℓ ()} .
In this paper, we consider general approach where for estimation of average empirical losses it will
be used -averaging aggregation functions ( -averages). This approach generalises -regression
method [
{ 1, … , } = argmin ∑ ( − ), where – is the nonnegative strictly convex function, (0) = 0 .
Here are some examples of -averages:
Collection of symmetrical averages: where 0 ≤ ≤ 1 ( 0 is median, 1 is arithmetical mean).
Collection of non-symmetrical averages: { 1, … , } = argmin ∑ | − | 1+ , { 1, … , } = argmin ∑ | − |
1+ , =1 =1 =1 where || 1+ = ( − [ > 0])||
, 0 ≤ ≤ 1 ( 0 is -quantile, 1 is -expectile). Besides, ≥ 0 and ∑ =1 is convex, ′′() is continouous function, > 0 is value of distortion,̃ ∈ [ , + ], ̃ = { 1, … , −1 ̃,} . Let be some -averaging function. We define empirical risk based on -averaging function , as follows:
( ) = {ℓ1( ), … , ℓ ( )}.
The classical empirical risk is a special case when is arithmetical mean. The best set of the parameters for ∗ have to minimize the function with respect to the minimization principle: ( ∗
) = min {ℓ1( ), … , ℓ ( )}.
Since the median and quantile are not continuously differentiable, the gradient procedures for minimisation of the risk functional are not practical. However, instead of median we can use continuously differentiable parametric family of -average functions based on the dissimilarity function ( − ) that satisfy the following requirements:
′′(̃ − ̃ ) ∑ =1 −1 ′′ ( − ̃ ) + ′′(̃ − ̃ ) < ′′(̃ − ̃ ) , →0 →0 →0 1. lim ( − ) = | − | 2. lim ′ ( − ) = sign( − ) 3. lim ′′( − ) = ( − )
; can be used: () = √ 2 + 2 − ; () = || − ln( + ||) −
ln .
; (Dirac’s -function).
We demonstrate, for example, that for the role of "approximate" median the following functions Such -averages are continuously differentiable and robust with sufficiently small . This implies that they are resistant to outliers (in some cases up to 50%).
To approximate the -quantile, one can use the function
(1 − )
(),
(),
if < 0
if > 0.
, () =
{ (+0) + (1 − ) (−0), if = 0
(1)
The ∗ search algorithm is an IR-ERM (Iteratively Re-weighted Empirical Risk Minimization) [
) =1
At the heart of IR-ERM is the process of iterative re-weighting, as well as in the IRLS [
To demonstrate the possibility of empirical risk minimisation [
But the arithmetic summation features the following important property: { 1, … , } =
( + − ( − )).
=1 1 2 1
∑ 3.1. Least Winsorized Sum and Mean In the Least Winsorized Sum (LWS) method before summing, all values that are greater than the specified threshold value are replaced by , i.e.
{ 1, … , } =
( + − | − |).
Let’s call it WS (Winsorized Sum). It has the following property: if is the arithmetic mean of 1, … , , then
{ 1, … , } = 1 + ⋯ + .
The WM (Winsorized Mean) averaging method is defined as { 1, … , } = { 1, … , }.
We generalize the WS summing method as follows. Let be -average on the basis of a twice differentiable strictly convex function . Denote = { 1, … , }. Define then
Since, by definition, = 1 (1 − ′( − )) + 2
. ∑ = . =1 to find the optimal set of parameters ∗ . Now write down the gradient: 1 2 ( ) = (1 − ′(ℓ ( ) − ( ))) + 1 2
For numerical calculation, we can apply the algorithm IR-SWSM (Iteratively Re-weighted Smoothly Winsorized Sum Minimization) the next version of the IR-SWSM algorithm: layer:
end where softplus( ) = ln(1 + ). NN was trained with the Boston data set.
= 0 + 1 1 + ⋯ +
= softplus( 0 + 1 1 + ⋯ + ),
To illustrate the IR-SWSM algorithm capacity, we consider a neural network with single hidden
For training, error back propagation has been applied, where the mean square error (ER) and mean value of the Huber function with the small parameter (0.001) are minimised, for it to be a continuously differentiable approximation of the module error. IR-SWSM learning algorithm has also been used, where the robust estimate of the error sum WS of squares (WS) are minimised using the function , type (1), where ( ) = √ 2 + 2 − , = 0.90.
The Fig. 2 shows the of mean absolute error distribution across the entire dataset. This clearly demonstrate that training neural networks (40 and 80 neurons in the hidden layer) with IR- SWSM algorithm reduce error values to more than 80% of the data.
There is also another experiment with only 7 neurons in the hidden layer. The Fig. 3 shows the of mean absolute error distribution across the entire dataset.
In this paper, we propose a method and algorithms for minimizing robust differentiable estimate of means and sums that are potentially resistant to outliers and errors that can lead to a shift in the parameters of the trainees. It is based on minimization of differentiable robust analogs of median, quantiles and winsorized sums of loss functions.
The above approaches are preferable in the cases when application of gradient based minimisation
procedures are preferable. For example, these approaches made possible application of weighted
variants of back propagation algorithms for NN robust learning. Construction of robust learning
algorithms of NN are important in a sense of many applications [
In these procedures at each step a weighted variant of back propagation algorithm is used. Examples presented above clearly show that proposed approaches and algorithms can be resistant to a large amount of outliers.
The work was supported by a grant from the Russian Foundation for Basic Research 18–01–00050.