Machine Learning 1. Lecture 14. Anomaly Detection and…

What this lecture is about

Training data are almost never clean: they contain measurement errors, typos, objects the model describes poorly, and objects unlike anything seen before. The lecture has three parts. The first covers the problems of detecting anomalous objects and simple heuristics for scoring anomaly. The second is the theory of robust, that is, noise-resistant, learning: robust loss functions, robust aggregation functions and methods of iterative reweighting of objects, which make it possible to train a model so that outliers hardly affect it. The third covers problems with anomalous or new classes: one-class classification, learning from a sample of a single class, and problems in which the set of classes is not fixed in advance.

Detecting anomalous objects

Anomaly detection problems

Definition (Anomaly detection problems). Outlier detection:

errors in the data of a training or test object;
the model is inadequate on some objects.

Novelty detection:

nothing like it was in the training sample.

Applications:

fraud detection;
intrusion detection;
detecting insider trading on an exchange;
detecting faults from sensor readings;
medical diagnosis.

Two settings are distinguished. An outlier is an object of the training or test sample that does not fit the general pattern: either its data contain an error, or the model is inadequate on it. Novelty is an object unlike anything in the training sample. In detecting fraud, intrusions into computer networks or equipment faults, the anomalous objects are precisely what is of main interest; in training models, on the contrary, they get in the way, and one wants to find and neutralise them.

Heuristics for scoring anomaly

Most methods assign each object a number, its anomaly score: the larger it is, the less the object resembles the others. There are many ways to define such a number, and each rests on its own idea of how normal data are arranged.

Definition (The metric approach (Breunig, Kriegel, Ng, Sander, 2000)). The anomaly score of an object is the distance to its $k$ -th nearest neighbour: the larger it is, the lower the local density of the sample.

M. M. Breunig, H.-P. Kriegel, R. T. Ng, J. Sander. LOF: identifying density-based local outliers. 2000.

If there are few other objects around an object, the distance to its $k$ -th neighbour is large, and the object lies in a region of low density. This is the same principle as in the nearest neighbours method and in Parzen density estimates, except that what is estimated is the density, not the class.

Definition (Random isolation forest (Isolation Forest; Liu, Ting, Zhou, 2008)).

A random forest of trees is built.
Each split: a random feature and a random threshold.
Each leaf holds only one object.
The anomaly score of an object is the mean depth of the leaves it falls into: the smaller it is, the more isolated the object.

Fei Tony Liu, Kai Ming Ting, Zhi-Hua Zhou. Isolation Forest. 2008.

The idea of the isolation forest: random splits quickly separate an object lying far from the others — a few thresholds suffice — while an object in the thick of the sample takes a long time to isolate. So a small mean leaf depth indicates an anomaly. The trees are built without any quality criterion, which makes the method very fast.

Definition (Separating a mixture of distributions with a background component). The generative model of a mixture of distributions:

p (x) = w_{0} φ_{0} (x) + j = 1 \sum k w_{j} φ (x, θ_{j}), j = 0 \sum k w_{j} = 1, w_{j} ⩾ 0.

Ways to specify the background distribution $φ_{0} (x)$ :

a spherical Gaussian with a large variance;
a radial distribution with a heavy tail (Laplace, Student's $t$ ).

The problem of maximising the log-likelihood:

L (w, θ) = ln i = 1 \prod ℓ p (x_{i}) = i = 1 \sum ℓ ln (w_{0} φ_{0} (x_{i}) + j = 1 \sum k w_{j} φ (x_{i}, θ_{j})) \to w, θ max .

The anomaly score of an object $x_{i}$ is the probability $P (j = 0 ∣ x_{i})$ that it belongs to the background; it is estimated at the E-step of the EM algorithm.

This generalises the mixture of distributions that was solved by the EM algorithm in the lecture on density estimation. One more component is added to the usual ones, a wide "background" one, which has to describe everything the others do not. The E-step itself computes the posterior probability that the object was generated by the background, and that is its anomaly score.

Definition (Robust principal component analysis (Robust PCA; Candès, Li, Ma, Wright, 2009)). $f_{1} (x), \dots, f_{n} (x)$ are the original numerical features of an object $x$ ; $g_{1} (x), \dots, g_{m} (x)$ are new numerical features, $m ⩽ n$ ;

$f^_{j} (x) = \sum_{s = 1}^{m} g_{s} (x) u_{j s}$ is the reconstruction of the old features from the new ones.

Find both the new features $G$ and the transformation $U$ at once:

i = 1 \sum ℓ j = 1 \sum n (f^_{j} (x_{i}) - f_{j} (x_{i}))^{2} = G U^{T} - F^{2} \to G, U min .

The anomaly score of an object is an unknown sparse noise $(ε_{i})_{i = 1}^{ℓ}$ :

G U^{T} - F - E^{2} + λ ∥ E ∥_{1} \to G, U, E min,

where $G U^{T}$ is a low-rank matrix and $E$ is a sparse matrix.

Principal component analysis approximates the object–feature matrix $F$ by a low-rank matrix. If the data contain isolated corrupted values, ordinary principal component analysis tries to explain them too, and is distorted. The robust variant allows part of the data not to be explained by the model: the residual is collected in the matrix $E$ , and the $L_{1}$ penalty makes it sparse. The nonzero entries of $E$ show which objects, and which of their features, are anomalous.

Removing outliers in nonparametric regression

Recall kernel smoothing from the lecture on metric methods.

Definition (Reminder. Nonparametric regression). The regression model is a constant $f (x, α) = α$ in a neighbourhood of $x$ :

Q (α; X^{ℓ}) = i = 1 \sum ℓ w_{i} (x) (α - y_{i})^{2} \to α \in R min,

where $w_{i} (x) = K (\frac{ρ ( x , x _{i} )}{h})$ are the weights of the objects $x_{i}$ relative to $x$ ; $K (r)$ is a kernel, non-increasing, bounded and smooth; $h$ is the width of the smoothing window.

The Nadaraya–Watson kernel smoothing formula:

a_{h} (x; X^{ℓ}) = \frac{\sum _{i = 1}^{ℓ} y _{i} w _{i} ( x )}{\sum _{i = 1}^{ℓ} w _{i} ( x )} = \frac{\sum _{i = 1}^{ℓ} y _{i} K ( \frac{ρ ( x , x _{i} )}{h} )}{\sum _{i = 1}^{ℓ} K ( \frac{ρ ( x , x _{i} )}{h} )} .

The Nadaraya–Watson estimate is a weighted mean of the responses $y_{i}$ of neighbouring objects. The mean is unstable under large outliers: one object with a huge $y_{i}$ distorts the estimate throughout its neighbourhood. The natural idea is to reduce the weights of the objects on which the error is large. But the error can only be estimated by building a model, and the model depends on the weights. There is no vicious circle here: it is a reason for an iterative process.

Definition (The LOWESS algorithm (LOcally WEighted Scatter plot Smoothing)). Input: $X^{ℓ}$ , the training sample. Output: coefficients $γ_{i}$ , $i = 1, \dots, ℓ$ .

initialisation: $γ_{i} := 1$ , $i = 1, \dots, ℓ$ ;
repeat
leave-one-out estimates at each object:

a_{i} := a_{h} (x_{i}; X^{ℓ} ∖ {x_{i}}) = \frac{\sum _{j = 1, j \neq = i}^{ℓ} y _{j} γ _{j} K ( \frac{ρ ( x _{i} , x _{j} )}{h ( x _{i} )} )}{\sum _{j = 1, j \neq = i}^{ℓ} γ _{j} K ( \frac{ρ ( x _{i} , x _{j} )}{h ( x _{i} )} )}, i = 1, \dots, ℓ;

$γ_{i} := K ~ (∣ a_{i} - y_{i} ∣)$ , $i = 1, \dots, ℓ$ ;
until the coefficients $γ_{i}$ stabilise.

Gary W. Moran. Locally-Weighted-Regression Scatter-Plot Smoothing (LOWESS): a graphical exploratory data analysis technique. 1984.

At each iteration, for each object, an estimate of its response is built from all the other objects — a leave-one-out estimate in which the object itself takes no part, otherwise an outlier would "explain" itself. The error $∣ a_{i} - y_{i} ∣$ is converted into the object's weight by one more kernel $K ~$ : the larger the error, the smaller the weight $γ_{i}$ with which the object enters the estimates for its neighbours. The kernel $K ~$ can be chosen in different ways. Hard filtering: build the order statistics of the errors $ε^{(1)} ⩽ \dots ⩽ ε^{(ℓ)}$ and discard the $t$ objects with the largest error, which corresponds to $K ~ (ε) = [ε ⩽ ε^{(ℓ - t)}]$ . Soft filtering: take the quartic kernel with a width proportional to the median error, $K ~ (ε) = K_{Q} (\frac{ε}{6 med { ε _{i} }})$ .

One hundred points on the interval from −5 to 5 around a smooth curve; a pale pink curve deviates sharply upward near x = −2 and downward near x = 3, while the red and blue curves follow the points

The example shows how badly two outliers spoil ordinary kernel smoothing: each of them pulls the curve towards itself over a distance of the order of the window width. After a few LOWESS iterations their weights become practically zero, and the curve follows the bulk of the points.

Putting the approaches together

Definition (Reminder: the least absolute deviations method). A loss function $L (ε_{i})$ , where $ε_{i} = a (x_{i}) - y_{i}$ is the error; $Q = \sum_{i = 1}^{ℓ} L (ε_{i}) \to min_{a}$ is the criterion for training the model on the sample.

The least squares method, $L (ε) = ε^{2}$ :

Q = i = 1 \sum ℓ (a - y_{i})^{2} \to a min \Rightarrow a = mean {y_{1}, \dots, y_{ℓ}} = \frac{1}{ℓ} i = 1 \sum ℓ y_{i} .

The least absolute deviations method, $L (ε) = ∣ ε ∣$ :

Q = i = 1 \sum ℓ ∣ a - y_{i} ∣ \to a min \Rightarrow a = median {y_{1}, \dots, y_{ℓ}} = y^{(ℓ /2)},

where $y^{(1)} ⩽ \dots ⩽ y^{(ℓ)}$ are the order statistics of the values $y_{i}$ . The median is more robust to rare large outliers $y_{i}$ .

The simplest model, a constant, shows the essence of the matter. The minimum of the sum of squares gives the mean, and a single object with a huge $y_{i}$ shifts it arbitrarily far. The minimum of the sum of absolute values gives the median, which does not depend on the size of an outlier at all, as long as fewer than half of the objects are outliers.

Definition (Reminder: SVM regression is also robust regression). The regression model: $a (x) = ⟨ x, w ⟩ - w_{0}$ , $w \in R^{n}$ , $w_{0} \in R$ . The loss function is piecewise linear: $L (ε) = (∣ ε ∣ - δ)_{+}$ .

The problem:

Q (w, w_{0}) = i = 1 \sum ℓ (⟨ w, x_{i} ⟩ - w_{0} - y_{i} - δ)_{+} + \frac{1}{2 C} ∥ w ∥^{2} \to w, w_{0} min .

The problem is solved by a change of variables and a reduction to a quadratic programming problem.

The SVM regression loss grows linearly rather than quadratically, so it too is insensitive to large errors, in the same sense as the least absolute deviations method.

Definition (Novelty detection and other problems). The anomaly score of an object (anomaly / novelty / surprise score) is the value of the loss function $L (a (x_{i}), y_{i})$ on that object.

Ways of scoring anomaly:

the anomaly is scored for an object of the training sample (outlier) or for a new object (novelty);
the loss depends on $y_{i}$ (supervised) or not (unsupervised);
when the anomaly of a training object is scored, the object is excluded from the sample, $a (x_{i}; X^{ℓ} ∖ x_{i})$ , or not, $a (x_{i}; X^{ℓ})$ ;
the loss function is the same as in the training criterion, or not.

Ways of using anomaly scores:

hard removal of anomalous objects from the sample;
soft reweighting of objects.

M. Salehi et al. A unified survey on anomaly, novelty, open-set, and out-of-distribution detection: solutions and future challenges. 2021.

All the heuristics considered fit one scheme: the anomaly score is the model's loss on the object. In the metric approach the model is the local density, in the mixture it is the likelihood, in robust PCA the reconstruction error, in LOWESS the leave-one-out error. The schemes differ in whether there are responses $y_{i}$ , whether the object itself takes part in training the model by which its anomaly is scored, and in what is done with the anomalies found: they are removed, or their weights are reduced.

The theory of robust learning

Slowly growing functions

Definition (Optimisation problems of machine learning). The problems of regression, classification, clustering, density estimation, dimensionality reduction and others differ in their loss functions $L_{i} (α)$ and regularisers $τ R (α)$ :

Q (α) = i = 1 \sum ℓ w_{i} L_{i} (α) + τ R (α) \to α min .

The problem: outliers can distort $L_{i} (α)$ and the criterion $Q (α)$ .

The idea: reduce the weight $w_{i}$ of outliers with large $L_{i} (α)$ by introducing slowly growing functions $μ (L)$ :

Q (α) = i = 1 \sum ℓ μ (L_{i} (α)) + τ R (α) \to α min;

\nabla Q (α) = i = 1 \sum ℓ w_{i} μ^{'} (L_{i} (α)) \nabla L_{i} (α) + τ \nabla R (α) = 0.

Almost all the learning problems in the course have this form: a sum of losses over objects plus a regulariser. If the loss on an outlier is large, that object determines the solution. A slowly growing function $μ$ "flattens" large losses. The condition for an extremum shows that this is equivalent to weighting the objects: each object enters the gradient with weight $w_{i} = μ^{'} (L_{i} (α))$ , and if $μ^{'}$ decreases, objects with large losses get small weights.

Iterative reweighting of objects

Definition (Iterative Reweighting Scheme (IRS)). Let $μ (r)$ be a slowly growing function: $μ (r) ⩾ 0$ , $μ^{'} (r) ⩾ 0$ , $μ^{'} (r)$ decreases, $μ^{'} (r) \to 0$ as $r \to + \infty$ .

Input: $L_{i} (α)$ , the loss function on the training sample. Output: the model parameters $α$ , the object weights $w_{i}$ .

initialisation: $w_{i} := \frac{1}{ℓ}$ , $i = 1, \dots, ℓ$ ;
repeat
$α := ar g min_{α} \sum_{i = 1}^{ℓ} w_{i} L_{i} (α) + τ R (α)$ ;
$w_{i} := norm_{i} (μ^{'} (L_{i} (α)))$ , $i = 1, \dots, ℓ$ ;
until the weights $w_{i}$ stabilise;

where $norm_{i} (v_{i}) = \frac{v _{i}}{\sum _{j} v _{j}}$ is the normalisation of a vector.

Drawback: everything goes badly when the outliers are large or numerous.

The condition for an extremum cannot be solved at once, because the weights depend on $α$ . But if the weights are fixed, what remains is an ordinary learning problem with weighted objects, which we know how to solve. Hence the iterative scheme: train the model with the current weights, recompute the weights from the losses, repeat. This is the same device as in LOWESS, only in general form, for any model and any loss function.

Definition (Iteratively Reweighted Least Squares (IRLS)). Robust regression: $L_{i} (α) = f (x_{i}, α) - y_{i}$ .

Input: $(x_{i}, y_{i})_{i = 1}^{ℓ}$ , the training sample. Output: the model parameters $α$ , the object weights $w_{i}$ .

initialisation: $w_{i} := \frac{1}{ℓ}$ , $i = 1, \dots, ℓ$ ;
repeat
$α := ar g min_{α} \sum_{i = 1}^{ℓ} w_{i} L_{i}^{2} (α) (f (x_{i}, α) - y_{i})^{2} + τ R (α)$ ;
$w_{i} := norm_{i} \frac{μ ^{'} ( L _{i} ( α ))}{L _{i} ( α )}$ , $i = 1, \dots, ℓ$ ;
until the weights $w_{i}$ stabilise.

Drawback: everything goes badly when the outliers are large or numerous.

In regression it is more convenient for each iteration to solve a least squares problem, for which fast methods exist. To that end the loss is written through the squared error: $\nabla μ (∣ r_{i} ∣) = \frac{μ ^{'} ( ∣ r _{i} ∣ )}{∣ r _{i} ∣} r_{i} \nabla r_{i}$ , and $r_{i} \nabla r_{i} = \frac{1}{2} \nabla r_{i}^{2}$ . So the weight of an object in the least squares problem is $μ^{'} (L_{i}) / L_{i}$ . With $μ (r) = r$ this gives the least absolute deviations method, solved by a sequence of weighted least squares problems with weights $1/∣ r_{i} ∣$ .

Robust loss functions

Definition (Loss functions for robust regression). The loss $L_{i} (α) = μ (r)$ is a function $μ$ of the error $r = f (x_{i}, α) - y_{i}$ . The quadratic loss $μ (r) = r^{2}$ is not robust.

Robust loss functions $μ (r)$ with a parameter $c$ :

$∣ r ∣$ — piecewise linear (Least Absolute Regression);
$max (0, ∣ r ∣ - c)$ — piecewise linear (SVM Regression);
$c (1 - exp (- \frac{r ^{2}}{2 c}))$ — Meshalkin's;
${\frac{1}{2 c} r^{2}, ∣ r ∣ - \frac{c}{2}, ∣ r ∣ < c; ∣ r ∣ ⩾ c$ — Huber's;
$\frac{c ^{2}}{6} (1 - [∣ r ∣ < c] (1 - (\frac{r}{c})^{2})^{3})$ — Tukey's;
${1 - cos \frac{π r}{c}, 2, ∣ r ∣ < c; ∣ r ∣ ⩾ c$ — Andrews'.

Barron's family of functions with a parameter $p$ :

μ_{p} (r) = \frac{∣ p - 2∣}{p} ((\frac{r ^{2}}{∣ p - 2∣} + 1)^{p /2} - 1) .

Jonathan T. Barron. A General and Adaptive Robust Loss Function. 2019.

Robust loss functions are of two types. In some the branches grow linearly (absolute value, SVM regression, Huber): large errors are taken into account, but not as strongly as with a square. In others the branches approach a horizontal asymptote or become constant (Meshalkin, Tukey, Andrews): beyond some size of error the object stops affecting the solution altogether. Huber's function is a compromise: near zero it is quadratic and smooth, and further out it is linear.

TikZ diagram — The quadratic loss (black) and robust ones: absolute value (grey), Huber's (blue), Meshalkin's (red), Tukey's (green), all with $c = 2$ .

Barron's family brings many of these functions under one parametrisation. At $p = 2$ (as a limit) it gives the quadratic function $\frac{r ^{2}}{2}$ , at $p = 1$ a smooth analogue of the absolute value $r^{2} + 1 - 1$ , at $p = 0$ (as a limit) the logarithmic function $ln (\frac{r ^{2}}{2} + 1)$ , and as $p \to - \infty$ a function with a horizontal asymptote, $1 - exp (- \frac{r ^{2}}{2})$ , which up to scale is Meshalkin's function. By decreasing $p$ one can continuously change the model's attitude to large errors, from full trust in the data to ignoring them; the parameter $p$ can even be tuned together with the model.

Experiments with robust regression on synthetic data show a typical picture. While there are no outliers, all loss functions give almost the same lines. With 10% outliers the quadratic loss already distorts the solution noticeably, while Huber's does not. With 30% and 50% outliers the robust loss functions, Huber's and Tukey's, give in too: the line turns towards the outliers. The iterative reweighting scheme works poorly when the outliers are large or numerous.

Robust aggregation functions

Another view of the same problem: the training criterion is a sum, that is, up to a factor, the arithmetic mean of the losses over the objects. And the arithmetic mean is the least stable way of aggregating. It can be replaced by a stable one.

Definition (Robust (outlier-resistant) ways of averaging). The arithmetic mean (not robust to large outliers):

\frac{1}{ℓ} i = 1 \sum ℓ z_{i} = ar g u min i = 1 \sum ℓ (z_{i} - u)^{2} .

Robust ways of averaging, defined through the order statistics $z^{(1)} ⩽ \dots ⩽ z^{(ℓ)}$ of the values $z_{1}, \dots, z_{ℓ}$ :

the median:

\frac{1}{2} (z^{(⌊ \frac{ℓ + 1}{2} ⌋)} + z^{(⌈ \frac{ℓ + 1}{2} ⌉)}) = ar g u min i = 1 \sum ℓ ∣ z_{i} - u ∣;

the $γ$ -quantile:

z^{(⌊ γ ℓ ⌋)} = ar g u min i = 1 \sum ℓ ∣ z_{i} - u ∣ \cdot {γ, 1 - γ, z_{i} ⩾ u; z_{i} < u;

the censored mean: $\frac{1}{ℓ} \sum_{i = 1}^{ℓ} min (z_{i}, z^{(m)})$ .

Drawback: these averaging functions are not differentiable.

The median of the losses, their quantile or their censored mean (large losses are replaced by the $m$ -th largest value) hardly react to a few huge values. But if we substitute the losses $z_{i} = L_{i} (α)$ and minimise such an aggregation function over the model parameters, we run into non-differentiability: the order statistics rearrange in jumps as $α$ changes. The way out lies in two ideas.

Definition (The general form and properties of aggregation functions). Idea 1: replace the mean by a one-dimensional minimisation over $u$ .

Idea 2: then replace the absolute value by a smooth approximation of it.

Q (α) = M (z_{1} L_{1} (α), \dots, z_{ℓ} L_{ℓ} (α)) = ar g u min i = 1 \sum ℓ d (z_{i} - u) .

Properties of the dissimilarity function $d (r)$ : strictly convex, $d (r) ⩾ 0$ , $d (0) = 0$ .

Properties of the aggregation function $M (z_{1}, \dots, z_{ℓ})$ :

$M (z_{1}) = z_{1}$ ;
monotonicity: $z_{i} ⩽ z_{i}^{'} \Rightarrow M (z_{1}, \dots, z_{ℓ}) ⩽ M (z_{1}^{'}, \dots, z_{ℓ}^{'})$ ;
symmetry: $M (z_{1}, \dots, z_{ℓ}) = M (z_{π (1)}, \dots, z_{π (ℓ)})$ for any permutation $π$ ;
Cauchy mean: $min_{i} {z_{i}} ⩽ M (z_{1}, \dots, z_{ℓ}) ⩽ max_{i} {z_{i}}$ .

All three ways of averaging — and the arithmetic mean itself — are written as the solution of a one-dimensional problem: find the point $u$ least dissimilar to all the $z_{i}$ . The squared dissimilarity gives the mean, the absolute value the median, the asymmetric absolute value the quantile. It remains to replace the absolute value by a smooth strictly convex function, and the aggregation function becomes smooth in its arguments.

Definition (Examples of smoothed dissimilarity functions). The smoothed absolute value (to approximate the median):

d_{ε} (r) = ε^{2} + r^{2} - ε ε \to 0 ∣ r ∣.

The smoothed asymmetric absolute value (for the $γ$ -quantile):

d_{γ ε} (r) = {2 γ d_{ε} (r), 2 (1 - γ) d_{ε} (r), r ⩾ 0; r < 0 ε \to 0 ∣ r ∣_{γ} = {2 γ ∣ r ∣, 2 (1 - γ) ∣ r ∣, r ⩾ 0; r < 0.

Definition (One more example: the smoothed censored mean). We use the identity $min (z_{i}, u) = \frac{1}{2} (z_{i} + u) - \frac{1}{2} ∣ z_{i} - u ∣$ :

M (z_{1}, \dots, z_{ℓ}) = \frac{1}{2 ℓ} i = 1 \sum ℓ (z_{i} + z_{γ ε} - d_{ε} (z_{i} - z_{γ ε})) ε \to 0 \frac{1}{ℓ} i = 1 \sum ℓ min (z_{i}, z^{(m)}),

z_{γ ε} = ar g u min i = 1 \sum ℓ d_{γ ε} (z_{i} - u) ε \to 0 z^{(m)}, m = γ ℓ .

The censored mean is smoothed in two steps: the threshold $z^{(m)}$ is replaced by the smoothed $γ$ -quantile $z_{γ ε}$ , and the minimum of two numbers is expressed through the absolute value, which is also replaced by a smoothed one.

Iterative reweighting for an aggregation function

Now empirical risk minimisation can be generalised: what is minimised is not the sum of the losses but an aggregation function of them.

Definition (Generalised empirical risk minimisation (ERM)).

Q (α) = M (L_{1} (α), \dots, L_{ℓ} (α)) + τ R (α) \to α min;

\nabla Q (α) = i = 1 \sum ℓ w_{i} \frac{\partial M}{\partial L _{i}} (L_{1} (α), \dots, L_{ℓ} (α)) \nabla L_{i} (α) + τ \nabla R (α) = 0.

The iterative reweighting algorithm (IR-ERM):

repeat
$α := ar g min_{α} \sum_{i = 1}^{ℓ} w_{i} L_{i} (α) + τ R (α)$ ;
$w_{i} := \frac{\partial M}{\partial L _{i}} (L_{1} (α), \dots, L_{ℓ} (α))$ , $i = 1, \dots, ℓ$ ;
until the weights $w_{i}$ stabilise.

Once again the condition for an extremum shows that minimising an aggregation function is equivalent to weighting the objects: the weights are the partial derivatives of the aggregation function with respect to the losses. For the arithmetic mean all the derivatives equal $\frac{1}{ℓ}$ , and ordinary empirical risk minimisation results. It remains to see how to compute the derivatives $\frac{\partial M}{\partial z _{i}}$ when $M$ is given implicitly, as the solution of a minimisation problem.

Theorem (Partial derivatives of an aggregation function). Let $M (z_{1}, \dots, z_{ℓ}) = ar g min_{u} \sum_{i = 1}^{ℓ} d (z_{i} - u)$ with $d$ twice differentiable. Then

\frac{\partial M}{\partial z _{k}} = \frac{d ^{''} ( z _{k} - M )}{\sum _{i = 1}^{ℓ} d ^{''} ( z _{i} - M )} = norm_{k} d^{''} (z_{k} - M) .

Proof. Write the necessary condition for an extremum in $u \equiv M$ as an equation for $M$ :

i = 1 \sum ℓ d^{'} (z_{i} - M) = 0.

Differentiate it with respect to $z_{k}$ :

i = 1 \sum ℓ d^{''} (z_{i} - M) \frac{\partial}{\partial z _{k}} (z_{i} - M) = 0 \Rightarrow d^{''} (z_{k} - M) = \frac{\partial M}{\partial z _{k}} i = 1 \sum ℓ d^{''} (z_{i} - M),

which gives the formula.

The weight of an object is proportional to the second derivative of the dissimilarity function at the point $z_{k} - M$ . For the smoothed absolute value the second derivative $d_{ε}^{''} (r) = \frac{ε ^{2}}{( ε ^{2} + r ^{2} ) ^{3/2}}$ decreases quickly as $∣ r ∣$ grows, so objects whose losses are far from the "typical" value $M$ get small weights.

It remains to learn how to compute $M$ itself.

Definition (A one-dimensional optimisation problem for). To solve the equation $\sum_{i = 1}^{ℓ} d^{'} (z_{i} - M) = 0$ for $M$ by fixed-point iteration, we write it in the form $M = f (M)$ :

i = 1 \sum ℓ \frac{d ^{'} ( z _{i} - M )}{z _{i} - M} (z_{i} - M) = 0 \Rightarrow i = 1 \sum ℓ z_{i} \frac{d ^{'} ( z _{i} - M )}{z _{i} - M} = M i = 1 \sum ℓ \frac{d ^{'} ( z _{i} - M )}{z _{i} - M};

M = \frac{\sum _{i = 1}^{ℓ} z _{i} φ ( z _{i} - M )}{\sum _{i = 1}^{ℓ} φ ( z _{i} - M )} = i = 1 \sum ℓ z_{i} norm_{i} φ (z_{i} - M), where φ (r) = \frac{d ^{'} ( r )}{r} .

Interestingly, $M$ is a weighted mean of ${z_{i}}$ .

Theorem (A sufficient condition for the convergence of fixed-point iteration). The process $M_{t + 1} = f (M_{t})$ converges if $∣ f^{'} (M) ∣ < 1$ in a neighbourhood of the fixed point $M = f (M)$ :

\frac{\partial}{\partial M} \frac{\sum _{i} z _{i} φ ( z _{i} - M )}{\sum _{i} φ ( z _{i} - M )} < 1.

After taking the derivative with respect to $M$ at the fixed point:

\frac{\sum _{i} ( z _{i} - M ) φ ^{'} ( z _{i} - M )}{\sum _{i} φ ( z _{i} - M )} < 1.

This condition is easy to check for each particular function $d (r)$ , and for most useful $d$ it holds.

G. Beliakov, H. Bustince Sola, T. Calvo. A practical guide to averaging functions. 2016. Z. M. Shibzukhov. Minimisation of robust estimates of sums of parametrised functions. 2019.

Everything comes together in one algorithm with two nested iterative processes: the outer one reweights the objects and retrains the model, the inner one computes the aggregation function of the current losses.

Definition (The IR-ERM algorithm). Input: $L_{i} (α)$ , the loss function on the training sample. Output: the model parameters $α$ , the object weights $w_{i}$ .

initialisation: $w_{i} := \frac{1}{ℓ}$ , $i = 1, \dots, ℓ$ ;
repeat
$α := ar g min_{α} \sum_{i = 1}^{ℓ} w_{i} L_{i} (α) + τ R (α)$ ;
$z_{i} := L_{i} (α)$ ; initialisation $M := \sum_{i = 1}^{ℓ} w_{i} z_{i}$ ;
repeat
$M := \sum_{i = 1}^{ℓ} z_{i} norm_{i} φ (z_{i} - M)$ , where $φ (r) = \frac{d ^{'} ( r )}{r}$ ;
until the value of $M$ converges;
$w_{i} := norm_{i} d^{''} (z_{i} - M)$ , $i = 1, \dots, ℓ$ ;
until the weights $w_{i}$ stabilise.

Examples

Experiments on synthetic data show that aggregation functions are considerably more robust than robust loss functions.

Robust linear regression. The aggregation function copes even with 49% outliers, where the robust loss functions of the previous example gave in already at 30%.
Robust classification (SVM). With 23%, 33% and 44% outliers, an ordinary SVM builds a separating line distorted by the outliers, while a robust SVM with an aggregation function (with quantile parameter $γ = 0.68$ , $0.49$ , $0.19$ respectively) builds the right one; the aggregation function copes even with 44% outliers.
Robust clustering. If several dependencies are mixed in the data, then instead of a compromise "stretching" of one model over all the data, robust methods model the main one and ignore the rest. The slide shows robust clustering of synthetic data into 2, 3, …, 7 clusters for values of $γ$ from $0.15$ to $0.40$ .

Problems with anomalous or new classes

One-class classification

Definition (One-class SVM (OSVM)). Given: a training sample ${x_{i} \in R^{n} : i = 1, \dots, ℓ}$ .

Find: the centre $c \in R^{n}$ and the radius $r$ of a ball enclosing the whole sample except the anomalous outlier objects.

Criterion: minimise the radius of the ball and the sum of penalties for leaving the ball:

ν r^{2} + i = 1 \sum ℓ L (ζ_{i} = margin (c, r) r^{2} - ∥ x_{i} - c ∥^{2}) \to c, r min .

With $L (ζ) = (- ζ)_{+}$ the properties of the solution are similar to SVM:

a convex quadratic programming problem;
the solution is sparse: it depends only on the support objects;
generalisation to nonlinear models: $⟨ x_{i}, x_{j} ⟩ \to K (x_{i}, x_{j})$ .

One-class classification is a problem in which training objects exist for only one, "normal", class, while objects of the other class, the anomalies, cannot be collected or are too few. Then the region where the normal objects lie is described: here it is a ball of minimal radius. The coefficient $ν$ sets the trade-off: the larger it is, the smaller the ball and the more objects end up outside. The penalties work as in SVM, piecewise linearly, so the properties of the solution are the same too, including the possibility of replacing the inner product by a kernel to obtain a region of complex shape.

Learning from a sample of one class

Definition (A special case of SSL: PU-learning (Positive and Unlabeled)). Examples of problems where objects of only one class are known:

detecting fraudulent transactions;
recommender systems, ad personalisation;
automatically extending a knowledge base with facts.

A two-class classification model $a (x_{i}, w)$ . Unlabeled objects are treated as negative with weight $C_{-} ≪ C_{+}$ :

i = 1 \sum k \frac{C _{+}}{k} L (a (x_{i}, w), + 1) + i = k + 1 \sum ℓ \frac{C _{-}}{ℓ - k} L (a (x_{i}, w), - 1) + τ R (w) \to w min .

One of the successful methods is Biased SVM.

Gang Li. A Survey on Positive and Unlabelled Learning. 2013. J. Bekker, J. Davis. Learning From Positive and Unlabeled Data: A Survey. 2020.

In PU-learning only the positive objects $x_{1}, \dots, x_{k}$ are labeled, and the rest, $x_{k + 1}, \dots, x_{ℓ}$ , are not: among them there are both positive and negative ones. In a recommender system, for example, we know what the user bought, but not what they disliked: an item not bought might simply have gone unnoticed. The simplest approach is to treat all unlabeled objects as negative, but with a small weight, so that errors on them are penalised less than on the reliably labeled positive ones. This is a special case of semi-supervised learning: the same principle of a sum of two criteria with a common model.

Problems with new or unknown classes

Definition (Classification problems with a non-fixed set of classes).

Ordinary multiclass classification.
Further training of the model on each new class.
Detecting the objects of one class (one-class classification).
Detecting objects of new classes in the test sample (open-set recognition).
Automatically extending the set of classes with further training of the model (open-world recognition).

Walter J. Scheirer, https://www.wjscheirer.com/projects/openset-recognition

In ordinary classification the set of classes $Y$ is fixed, and every object belongs to one of them. In practice classes appear over time: new people in a face recognition system, new topics in a document classification system. The problems line up by degree of "openness": from closed multiclass classification to open-set recognition, where the classifier must be able to say "this is none of the known classes", and further to the open world, where the new class must also be added to the model and the model retrained.

Summary

Remark (Summary).

The nature of anomalous objects: noise (errors, interference, dirt) in the source data; the model describes admixtures of extraneous phenomena poorly; something fundamentally new appears regularly.
A simple way to weed out the grossest outliers is to exclude the objects with the largest losses.
A rare case for machine learning: what is minimised is not the sum of losses $L_{1} + \dots + L_{ℓ}$ but a generalised mean $M (L_{1}, \dots, L_{ℓ})$ .
The nature of anomalous classes: training objects of a class cannot be collected; the number of classes grows dynamically.
There is no ideal way to define anomalies. A "model of the anomaly" is assumed, explicitly or implicitly.

Machine Learning 1. Lecture 14. Anomaly Detection and Robust Methods