Machine Learning 1. Lecture 15. A Short Review of the…

What this lecture is about

The closing review gathers the semester's material into three pictures. The first is the optimisation picture: almost any machine learning problem is posed as empirical risk minimisation with regularisation, and problems differ in their loss functions and models. The second is historical and methodological: the models of machine learning grew out of several scientific schools, each with its own heuristic about how data are arranged. The third is practical: what the process of data analysis looks like from understanding the problem to deployment, and what in it gets automated.

Types of optimisation problems in machine learning

Empirical risk minimisation

Definition (The general formulation of most machine learning problems). Given: $X$ , the object space; $X^{ℓ} = {x_{1}, \dots, x_{ℓ}} \subset X$ , the training sample, the precedents; $a (x, w)$ , $a : X \times W \to Y$ , a parametric model, the hypothesis.

Find: $w \in W \subseteq R^{N}$ , the parameter vector of the model $a (x, w)$ .

The criterion of empirical risk minimisation (ERM):

Q (w) = \frac{1}{ℓ} i = 1 \sum ℓ L (w, x_{i}) + τ R (w) \to w min,

where $L (w, x)$ is the loss function, the larger the worse the model's answer $a (x, w)$ on the object $x$ ; $R (w)$ is the regulariser, requirements on the model that do not come from the precedents; $τ$ is the regularisation coefficient that balances the criteria.

This is the "DNA" of a problem — given, find, criterion — with which the solution of any problem begins. The loss function expresses what is known from the precedents; the regulariser, requirements on the model that do not follow from the precedents: smoothness, sparsity, small weights.

Definition (The gradient method of empirical risk minimisation). Gradient descent (GD):

w^{(0)} := initial approximation; w^{(t + 1)} := w^{(t)} - h \nabla Q (w^{(t)}),

where $\nabla Q (w) = (\frac{\partial Q ( w )}{\partial w _{j}})_{j = 1}^{N}$ is the gradient vector and $h$ is the gradient step, also called the learning rate:

w^{(t + 1)} := w^{(t)} - h (\frac{1}{ℓ} i = 1 \sum ℓ \nabla L (w^{(t)}, x_{i}) + τ \nabla R (w^{(t)})) .

Stochastic gradient (Stochastic Gradient, SGD):

w^{(t + 1)} := w^{(t)} - h (\nabla L (w^{(t)}, x_{i}) + τ \nabla R (w^{(t)})) .

In the stochastic gradient each step takes one random object $x_{i}$ (or a small batch of objects) instead of the whole sample. A step becomes $ℓ$ times cheaper, and its direction coincides with the gradient only on average; on large samples this pays off. This method is the main training tool, from linear models to deep neural networks.

Underfitting, overfitting and regularisation

TikZ diagram — Underfitting (too simple a model), the right complexity, and overfitting (the model passes through every point but describes the dependency poorly).

Remark (The fundamental problems: underfitting and overfitting).

Underfitting: there is plenty of data, too few parameters, the model is simple and inflexible.
Overfitting: there are many parameters, too little data, the model is complex and excessively flexible.

As the complexity of a model grows, the error on the training sample falls monotonically, while the error on new data first falls and then grows. Between underfitting and overfitting lies a model of the right complexity; finding it, limiting complexity, and training complex models so that they do not overfit is a theme running through the whole course.

Definition (Multicollinearity and overfitting in linear models). Multicollinearity is a linear dependence between features:

a linear regression or classification model $⟨ w, x ⟩$ ;
multicollinearity: $\exists u \in R^{n} : \forall x \in X ⟨ u, x ⟩ = 0$ ;
the solution is not unique: $\forall γ \in R ⟨ w, x ⟩ = ⟨ w + γ u, x ⟩$ .

Multicollinearity leads to overfitting:

instability: weights $∣ w_{j} ∣$ that are too large and of different signs;
the weight $w_{j}$ cannot be interpreted as the importance of the feature $f_{j}$ ;
overfitting: $Q (w^{*}, X^{ℓ}) ≪ Q (w^{*}, X^{k})$ .

How to reduce overfitting:

regularisation $∥ w ∥ \to min$ (weight decay);
feature selection: $f_{1}, \dots, f_{n} \to f_{j_{1}}, \dots, f_{j_{m}}$ , $m ≪ n$ ;
feature transformation: $f_{1}, \dots, f_{n} \to g_{1}, \dots, g_{m}$ , $m ≪ n$ .

If the features are linearly dependent, any multiple of the vector $u$ can be added to the weight vector without changing the model's answers on the training objects. The solution is no longer unique, and a numerical method can drift into a region of huge weights of different signs that cancel each other on the training sample but not on new data. The three remedies correspond to three lectures of the course: regularisation, feature selection, feature transformation (principal component analysis).

Definition (A penalty on model complexity reduces overfitting). A regulariser is an additive term to the main criterion, where $τ$ is the regularisation coefficient, a control parameter:

i = 1 \sum ℓ L (w, x_{i}) + τ penalty (w) \to w min .

$L_{p}$ regularisation of linear models $⟨ w, x_{i} ⟩ = \sum_{j = 1}^{n} w_{j} f_{j} (x_{i})$ :

penalty (w) = ∥ w ∥_{p}^{p} = j = 1 \sum n ∣ w_{j} ∣^{p} .

$L_{2}$ (Ridge, SVM) stabilises $w$ under multicollinearity;
$L_{1}$ (LASSO) and $L_{0}$ lead to the selection of informative features.

Probabilistic regularisation (Maximum a Posteriori Probability):

- i = 1 \sum ℓ ln p (x_{i} ∣ w) - regulariser ln p (w; γ) \to w min .

Definition (Non-smooth regularisers for feature selection and grouping). The general form of the regularisers ( $μ$ is the selectivity parameter):

i = 1 \sum ℓ L (w, x_{i}) + j = 1 \sum n R_{μ} (w_{j}) \to w min .

Regularisers with feature selection and grouping effects:

LASSO ( $L_{1}$ ): $R_{μ} (w) = μ ∣ w ∣$ ;
Elastic Net: $R_{μ} (w) = μ ∣ w ∣ + τ w^{2}$ ;
Support Feature Machine (SFM): $R_{μ} (w) = {2 μ ∣ w ∣, μ^{2} + w^{2}, ∣ w ∣ ⩽ μ; ∣ w ∣ ⩾ μ;$
Relevance Feature Machine (RFM): $R_{μ} (w) = ln (μ w^{2} + 1)$ .

Non-smoothness at zero is what gives feature selection: with a regulariser that has a kink at zero, the minimum of the criterion is often attained exactly at $w_{j} = 0$ , and the corresponding feature drops out of the model. Elastic Net and SFM combine the kink at zero with quadratic growth away from zero, which makes it possible to select whole groups of correlated features rather than one random member of each.

Supervised learning

Definition (Training a regression model). Given: a training sample $(x_{i}, y_{i})_{i = 1}^{ℓ}$ with responses $y_{i} \in R$ .

Find: the parameter vector $w$ of a regression model $a (x, w)$ .

Criterion: minimum empirical risk

i = 1 \sum ℓ L (a (x_{i}, w) - y_{i}) \to w min,

with a unimodal loss function $L (ε)$ of the residual $ε = a (x, w) - y$ .

Two plots of loss functions of the residual on the interval from −5 to 5: on the left the quadratic loss and two robust ones, one of which approaches a horizontal asymptote; on the right the absolute loss, the asymmetric quantile loss, and the SVM loss with a zero segment on the interval from −1 to 1

The quadratic loss corresponds to the least squares method and Gaussian noise; the absolute loss to the least absolute deviations method and the median; the quantile loss to quantile regression; the SVM loss does not penalise small residuals; robust functions limit the influence of large residuals, that is, of outliers.

Definition (Training a binary classifier). Given: a training sample $(x_{i}, y_{i})_{i = 1}^{ℓ}$ , $y_{i} \in {- 1, + 1}$ .

Find: the vector $w$ of a classification model $a (x, w) = sign g (x, w)$ .

Criterion: minimum approximated empirical risk

i = 1 \sum ℓ [g (x_{i}, w) y_{i} < 0] ⩽ i = 1 \sum ℓ L (g (x_{i}, w) y_{i}) \to w min,

with a decreasing loss function $L (M)$ of the margin $M = g (x, w) y$ .

Slide

Two plots of loss functions of the margin on the interval from −5 to 5, all passing through the point (0, 1): on the left the sigmoid, logistic and piecewise linear SVM hinge losses; on the right the exponential, quadratic and robust ones

TikZ

The threshold loss — the number of errors — is piecewise constant and cannot be minimised by gradient methods. It is replaced by a continuous upper bound as a function of the margin; the choice of that bound is what produces the different methods: logistic regression, SVM, boosting (the exponential function) and others.

Definition (Training a multiclass classifier). Given: a training sample $(x_{i}, y_{i})_{i = 1}^{ℓ}$ , $y_{i} \in Y$ , $∣ Y ∣ < \infty$ .

Find: the vector $w = (w_{y} : y \in Y)$ of a classification model $a (x, w) = ar g max_{y \in Y} g_{y} (x, w_{y})$ .

The "one against one" criterion:

i = 1 \sum ℓ y \neq = y_{i} \sum [M_{i y} (w) g_{y_{i}} (x_{i}, w_{y_{i}}) - g_{y} (x_{i}, w_{y}) < 0] ⩽ i = 1 \sum ℓ y \neq = y_{i} \sum L (M_{i y} (w)) \to w min .

The "one against all" criterion:

i = 1 \sum ℓ L (y \neq = y_{i} min M_{i y} (w)) \to w min,

where $M_{i y} (w)$ is the margin of the object $x_{i}$ with respect to the class $y$ .

Definition (Learning to rank, maximising AUC-ROC). Given: a training sample $(x_{1}, \dots, x_{ℓ})$ ; $i ≺ j$ , the relation " $x_{j}$ is better than $x_{i}$ " between objects of $X^{ℓ}$ .

Find: the parameters $w$ of a ranking model $a (x, w)$ that recovers the correct order relation: $i ≺ j \Rightarrow a (x_{i}, w) < a (x_{j}, w)$ .

Criterion: the number of wrongly ranked pairs of objects

i ≺ j \sum [M_{ij} (w) a (x_{j}, w) - a (x_{i}, w) < 0] ⩽ i ≺ j \sum L (a (x_{j}, w) - a (x_{i}, w)) \to w min,

where $L (M)$ is a decreasing function of the pairwise margin $M_{ij} (w)$ .

Multiclass classification and ranking follow the same pattern: instead of the margin of an object there is the margin with respect to each other class, or the margin of a pair of objects, and the same decreasing loss function bounds the number of errors from above. The share of correctly ordered "positive–negative" pairs is AUC-ROC, so minimising such a criterion is a gradient method for maximising AUC.

Unsupervised learning

Definition (The density estimation problem). Given: $X^{ℓ} = {x_{1}, \dots, x_{ℓ}} \sim i.i.d. p (x)$ , the training sample.

Find: the parameter vector $θ$ of a generative model $p (x ∣ θ)$ .

Criterion: maximum likelihood (MLE)

ln p (X^{ℓ} ∣ θ) = ln i = 1 \prod ℓ p (x_{i} ∣ θ) = i = 1 \sum ℓ ln p (x_{i} ∣ θ) \to θ max

or maximum a posteriori probability — the joint likelihood of the data and the model with a prior density $p (θ ∣ γ)$ (MAP):

ln p (X^{ℓ}, θ) = ln p (X^{ℓ} ∣ θ) p (θ ∣ γ) = i = 1 \sum ℓ ln p (x_{i} ∣ θ) + regulariser ln p (θ ∣ γ) \to θ max,

where $γ$ is the vector of hyperparameters of the prior distribution.

Definition (The problem of estimating a mixture of densities). Given: $X^{ℓ} = {x_{1}, \dots, x_{ℓ}} \sim i.i.d. p (x)$ , the training sample.

Find: the parameters $w_{j}$ , $θ_{j}$ of a mixture model of $K$ probability distributions

p (x ∣ θ, w) = j = 1 \sum K w_{j} p (x ∣ θ_{j}), j = 1 \sum K w_{j} = 1, w_{j} ⩾ 0.

Criterion: maximum likelihood $\sum_{i = 1}^{ℓ} ln p (x_{i} ∣ θ, w) \to max_{θ, w}$ or maximum a posteriori probability (MAP):

i = 1 \sum ℓ ln p (x_{i} ∣ θ, w) + regulariser ln p (θ, w ∣ γ) \to θ, w max .

Minus the log-likelihood of an object is the same loss function, and the log of the prior distribution is the same regulariser: probabilistic formulations fit into the general scheme of empirical risk minimisation. Mixtures of distributions are solved by the EM algorithm.

Definition (The clustering problem). Given: $X^{ℓ} = {x_{1}, \dots, x_{ℓ}}$ , the training sample, $x_{i} \in R^{n}$ .

Find: the cluster centres — parameters $μ_{j} \in R^{n}$ , $j = 1, \dots, K$ — and a cluster $a_{i} \in {1, \dots, K}$ for each object $x_{i} \in X^{ℓ}$ .

Criterion: minimum sum of within-cluster distances

i = 1 \sum ℓ ∥ x_{i} - μ_{a_{i}} ∥^{2} \to {a_{i}}, {μ_{j}} min;

the metric is usually Euclidean (but may be another): $∥ x - μ_{j} ∥^{2} = \sum_{d = 1}^{n} (f_{d} (x) - μ_{j d})^{2}$ .

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 and depends only on the support objects; generalisation to nonlinear models: $⟨ x_{i}, x_{j} ⟩ \to K (x_{i}, x_{j})$ .

Definition (The semi-supervised learning problem (SSL)). Given: $X^{k} = {x_{1}, \dots, x_{k}}$ , the labeled objects (labeled data) with labels ${y_{1}, \dots, y_{k}}$ , $y_{i} \in Y$ ; $U = {x_{k + 1}, \dots, x_{ℓ}}$ , the unlabeled objects (unlabeled data).

Find: a classification model $a (x, w)$ .

The criterion of simultaneous classification and clustering:

classification i = 1 \sum k L (a (x_{i}, w), y_{i}) + λ clustering i = 1 \sum ℓ L_{U} (a (x_{i}, w)) \to w min,

where $L (a, y)$ is the classification loss function and $L_{U} (a)$ is the loss function for unlabeled data. The essence of SSL is the common parametrisation $w$ in the two criteria.

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 can take only part of the unlabeled objects (negative sampling). 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.

Definition (Principal Component Analysis (PCA)). Given: a sample of objects ${x_{1}, \dots, x_{ℓ}}$ ; $f_{1} (x), \dots, f_{n} (x)$ , numerical features of the objects.

Find a feature transformation: $g_{1} (x), \dots, g_{m} (x)$ , new numerical features, $m ⩽ n$ , and a linear reconstruction of the old features $f_{j} (x)$ from the new ones:

f^_{j} (x) = t = 1 \sum m g_{t} (x) u_{j t}, j = 1, \dots, n, \forall x \in X .

Criterion: the accuracy of reconstructing $f_{j}$ on the training sample:

Q = 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,

where $G = (g_{t} (x_{i}))_{ℓ \times m}$ , $U = (u_{j t})_{n \times m}$ .

Definition (The autoencoder: learned vectorisation). Given: $X^{ℓ} = {x_{1}, \dots, x_{ℓ}}$ , the training sample.

Find a vectorisation model that preserves information: $f : X \to Z$ , the encoder, with code vector $z = f (x, α)$ ; $g : Z \to X$ , the decoder, with reconstruction $x^= g (z, β)$ .

The criterion of the quality of reconstructing the objects, $g (f (x_{i})) = x^_{i} \approx x_{i}$ :

i = 1 \sum ℓ L (g (f (x_{i}, α), β), x_{i}) \to α, β min .

The loss function may be quadratic: $L (x^, x) = ∥ x^- x ∥^{2}$ .

Example. PCA is a linear autoencoder: $x \in R^{n}$ , $z \in R^{m}$ , $f (x, A) = m \times n A x$ , $g (z, B) = n \times m B z$ . With $m ≪ n$ the data about the objects are compressed.

Principal component analysis is a special, linear case of the autoencoder. If the encoder and the decoder are neural networks, the result is a nonlinear learned vectorisation, one of the central mechanisms of deep learning, to which the second half of the course is devoted.

Definition (The autoencoder: learned vectorisation for SSL). Data: labeled $(x_{i}, y_{i})_{i = 1}^{k}$ , unlabeled $(x_{i})_{i = k + 1}^{ℓ}$ .

Find: $z_{i} = f (x_{i}, α)$ , the encoder; $x^_{i} = g (z_{i}, β)$ , the decoder; $y^_{i} = y^(z_{i}, γ)$ , the predictor.

Loss functions are given: $L (x^_{i}, x_{i})$ for reconstruction; $L ~ (y^_{i}, y_{i})$ for prediction.

Criterion: joint training of the autoencoder and the predictive model (classification, regression or other):

i = 1 \sum ℓ L (g (f (x_{i}, α), β), x_{i}) + λ i = 1 \sum k L ~ (y^(f (x_{i}, α), γ), y_{i}) \to α, β, γ min .

Dor Bank, Noam Koenigstein, Raja Giryes. Autoencoders. 2020.

Here again the principle of semi-supervised learning is at work: two criteria, on all the data and on the labeled data, with a common part of the parameters, the encoder $α$ . The unlabeled data train the vectorisation; the labeled data train prediction from the vector representations.

Constructing models: six scientific schools

The main scientific schools

Definition (The main scientific schools of machine learning).

Symbolism: searching for logical regularities: Decision Tree, Rule Induction.
Evolutionism: self-development of complex models: Genetic Algorithms, Genetic Programming, Symbolic Regression.
Analogism: "close objects have close answers": kNN, RBF, SVM, Kernel Smoothing.
Bayesianism: estimating the distributions of parameters: Naive Bayes, Bayesian Networks, Graphical Models.
Connectionism: training neural networks: BackPropagation, Deep Belief Nets, Deep Learning.
Compositionism: cooperation of models: Weighted Voting, Boosting, Bagging, Stacking, Random Forest, CatBoost.

Pedro Domingos. The Master Algorithm. 2015.

Pedro Domingos identified five schools in his book "The Master Algorithm"; the sixth, compositionism, is added to them because ensembles of models form an independent direction. Each school rests on its own heuristic about how data are arranged, and many of the schools have strong Soviet roots.

Symbolism

Definition (Symbolism. The scientific school of M. M. Bongard).

1958: the program "Discover the Law" recovered a dependency by exhaustive combinatorial search over formulas.
1959: the program "Arithmetic" used informativeness estimates to cut the search.
1961: the program "KoRa" searched over informative triples of features.

"KoRa-3" was the first application of the recognition of non-visual patterns: recognising the oil–water boundary in a well. It introduced the principles of voting and cross-validation, and the notions of informativeness and of prejudice (overfitting).

M. M. Bongard, M. N. Vaintsvaig, Sh. A. Guberman, M. L. Izvekova, M. S. Smirnov. The use of a learning program for detecting oil-bearing strata. 1966 (in Russian).

Definition (The notion of an informative logical regularity). The classification model is a weighted vote of rules:

a (x, w) = ar g y \in Y max k = 1 \sum n_{y} w_{y k} R_{y k} (x) .

A rule is a conjunction of elementary threshold conditions:

R (x) = j \in ω ⋀ [a_{j} ⩽ f_{j} (x) ⩽ b_{j}] .

A syndrome: at least $d$ conditions of the set $ω$ hold:

R (x) = [j \in ω \sum [a_{j} ⩽ f_{j} (x) ⩽ b_{j}] ⩾ d] .

A rule $R$ is a regularity of the class $y \in Y$ if

{p_{y} (R) = # {x_{i} : R (x_{i}) = 1 and y_{i} = y} \to max; n_{y} (R) = # {x_{i} : R (x_{i}) = 1 and y_{i} \neq = y} \to min .

Symbolism means the logical methods of classification: decision trees, decision lists and rule sets. A regularity must pick out many objects of its own class and few of the others; the two-criterion nature of this requirement produces the various informativeness criteria.

Evolutionism

Definition (Evolutionism. Algorithms that search over model structures). Discrete optimisation based on Darwinian evolution:

an individual is a structural formula of a model;
a population is a set of different formulas;
fitness is an external criterion, an evaluation of the model;
natural selection of the best models in the population;
crossover and mutation are the operations that produce offspring.

Particular machine learning problems solved by evolutionary algorithms:

feature selection;
searching for informative logical regularities;
searching for the architecture of a deep neural network;
symbolic regression: a search over structural formulas, genetic programming.

Definition (Evolutionism. The scientific school of A. G. Ivakhnenko). The group method of data handling (GMDH) is based on the self-organisation of models, a search-based optimisation of the model structure:

selection of features or of the model structure;
during the search the quality of the models is assessed by many external criteria: cross-validation, noise immunity of the modelling, balance (consistency) of forecasts, and others;
the first 8-layer deep neural network (1965);
hundreds of applications, about 300 dissertations.

A. G. Ivakhnenko, V. G. Lapa. Cybernetic Predicting Devices. 1965. A. G. Ivakhnenko, Yu. P. Zaichenko, V. D. Dimitrov. Decision Making Based on Self-Organisation. 1976. A. G. Ivakhnenko. An Inductive Method of Self-Organisation of Models of Complex Systems. 1982 (all in Russian).

The key idea of GMDH is external criteria: a model is evaluated not on the sample it was trained on but on a control one, and this makes it possible to search over model structures without overfitting at the selection stage. The same idea underlies cross-validation and the model selection methods of the lecture on quality.

Analogism

Definition (Analogism. The scientific school of M. A. Aizerman).

The compactness hypothesis: similar objects as a rule lie in the same class.
The method of potential functions: the idea is borrowed from physics.
A linear classification model: a weighted vote of the similarity functions $f_{i} (x) = K (x, x_{i})$ between $x$ and $x_{i}$ :

a (x) = ar g y \in Y max i : y_{i} = y \sum α_{y i} K (x, x_{i}) .

M. A. Aizerman, E. M. Braverman, L. I. Rozonoer. Theoretical foundations of the potential function method in the problem of teaching automata to classify input situations. 1964. M. A. Aizerman, E. M. Braverman, L. I. Rozonoer. The Method of Potential Functions in the Theory of Machine Learning. 1970. A. G. Arkadiev, E. M. Braverman. Teaching Machines to Recognise Patterns. 1964 (all in Russian).

The method of potential functions is already a linear classifier in the space of similarity functions to the objects of the sample, that is, in essence, a kernel method: thirty years later the same construction appeared in SVM with kernels.

Definition (Analogism. Metric (nonparametric) methods). Density estimation. The Parzen–Rosenblatt method:

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

Classification. Potential functions, the Parzen window:

a_{h} (x; X^{ℓ}, Y^{ℓ}) = ar g y \in Y max i = 1 \sum ℓ [y_{i} = y] K (\frac{ρ ( x , x _{i} )}{h}) .

Regression. Nadaraya–Watson kernel smoothing:

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

One and the same construction — a kernel of the distance divided by the window width — gives a method for three different problems: density estimation, classification and regression.

Definition (The principles of learnability, complexity limitation, separability). A family of classifiers $A$ is learnable if

P {a \in A sup P (a) - ν (a, X^{ℓ}) > ε} ⩽ η,

where $P (a)$ is the error probability of the classifier and $ν (a, X^{ℓ})$ is the empirical risk, the error rate of the classifier $a$ on the sample.

The main results of VC theory:

a justification for limiting the complexity of $A$ ;
the notion of the capacity of a family, VCdim;
the method of structural risk minimisation;
the support vector machine, SVM.

V. N. Vapnik, A. Ya. Chervonenkis. Theory of Pattern Recognition. Moscow: Nauka, 1974 (in Russian).

The Vapnik–Chervonenkis theory gave a mathematical justification for the principle of limiting model complexity: if the capacity of the family is small compared with the sample length, the error rate in training is uniformly close to the error probability. Structural risk minimisation and the support vector machine grew out of it.

Bayesianism

Definition (Discriminative and generative classification models). Given: a simple sample $X^{ℓ} = (x_{i}, y_{i})_{i = 1}^{ℓ} \sim p (x, y)$ .

The discriminative approach: find a model $p (x, y) = P (y ∣ x; w_{y}) p (x)$ (examples: LR, GLM, SVM, RBF). The maximum likelihood criterion:

i = 1 \sum ℓ ln p (x_{i}, y_{i}) = i = 1 \sum ℓ ln P (y_{i} ∣ x_{i}; w_{y}) + const \to {w_{y}} max .

The generative approach: find a model $p (x, y) = P (y) p (x ∣ y; w_{y})$ (examples: NB, PW, FLD, RBF). The maximum likelihood criterion:

i = 1 \sum ℓ ln p (x_{i}, y_{i}) = i = 1 \sum ℓ ln P (y_{i}) + y \in Y \sum x_{i} \in X_{y} \sum ln p (x_{i} ∣ y; w_{y}) \to {P (y), w_{y}} max .

The discriminative approach models only what classification needs, the conditional probability of the class. The generative one recovers the distribution of objects within each class and obtains a classifier through Bayes' formula; it needs more assumptions, but it makes it possible, for example, to generate objects and to detect atypical ones. The RBF network appears in both lists: it can be trained both as an SVM with a radial kernel and by the EM algorithm as a mixture of Gaussians.

Definition (Bayesian learning, MAP and regularisation). Bayesian inference of the posterior distribution $p (w ∣ X)$ and a point estimate:

Posterior (w ∣ X, γ) = \frac{p ( X ∣ w ) Prior ( w ∣ γ )}{\int p ( X ∣ w ) Prior ( w ∣ γ ) d w}; Posterior (w ∣ X, γ) \to w max or w, γ max .

Maximising the posterior probability (MAP) gives a point estimate of $w$ directly, without inferring the Posterior:

ln p (X ∣ w) + ln Prior (w ∣ γ) \to w max or γ max w max .

Regularisation, not necessarily probabilistic:

ln p (X ∣ w) + γ R (w) \to w max or γ max w max .

Three levels of rigour: full Bayesian inference of the posterior distribution, a point estimate of its maximum, and regularisation, which may have no probabilistic interpretation at all. A Gaussian prior gives the $L_{2}$ regulariser, a Laplace prior the $L_{1}$ one.

Connectionism

Definition (Connectionism. The linear model of a neuron (1943)).

a (x, w) = σ (j = 1 \sum n w_{j} f_{j} (x) - w_{0}),

where $f_{j} (x)$ are the features of the object $x$ ; $w_{j}$ are the feature weights; $w_{0}$ is the activation threshold; $σ (z)$ is the activation function.

The neuron model of Warren McCulloch and Walter Pitts (1943) is a linear classifier with an activation function. Multilayer networks are built from such neurons.

Remark (Rosenblatt's perceptron (1957) and milestones in the development of neural networks).

F. Rosenblatt's perceptron (1957): a two-layer network trained by error correction; Mark-1, the first neurocomputer (1960), for recognising digits and shapes. F. Rosenblatt. Principles of Neurodynamics: Perceptrons and the Theory of Brain Mechanisms. 1962.
M. Minsky, S. Papert. Perceptrons. 1969.
A. G. Ivakhnenko, V. G. Lapa. Cybernetic Predicting Devices. 1965 (in Russian).
A. I. Galushkin. Synthesis of Multilayer Pattern Recognition Systems. 1974 (in Russian).
Rumelhart D. et al. Learning internal representations by error propagation. 1986.
Krizhevsky A. et al. ImageNet classification with deep convolutional neural networks. 2012.
Vaswani A. et al. Attention is all you need. 2017.

The history of neural networks knows periods of rapid development and "winters" (AI winters). The book by Minsky and Papert showed the limitations of the single-layer perceptron and cooled interest in neural networks for years; multilayer networks and the backpropagation method (in the Soviet literature, A. I. Galushkin, 1974; widely known from the work of Rumelhart and co-authors, 1986) brought it back; the deep convolutional networks of 2012 and the transformer architecture of 2017 opened the present stage.

Remark (Deep convolutional networks for image classification). The ImageNet competition started in 2009; the human error level of 5% was passed in 2015. Convolutional neural networks: AlexNet (2012), ResNet (2015).

Li Fei-Fei et al. ImageNet: A large-scale hierarchical image database. 2009. Krizhevsky A. et al. ImageNet classification with deep convolutional neural networks. 2012. Kaiming He et al. Deep residual learning for image recognition. 2015.

The development of machine and deep learning is conveniently described in three stages, by the type of a model's input and output.

Diagram: rows of features of training objects with arrows to small squares of answers; below, a new object with an arrow to a question mark

Definition (Stage 1: vector → scalar). Predictive modelling of vector data. Input: vector feature descriptions of objects. Output: scalar answers (predictions, forecasts).

Applications: medical diagnosis, geological forecasting, credit scoring…

Models: SVM, LR, MVR, RBF, MLP, ID3, CART, RF, GBM…

Diagram: the "raw data" of training objects as small clouds with arrows to rows of features, and from them to small squares of answers

Definition (Stage 2: structure → vector → scalar). Learned vectorisation of complexly structured data. Input: the complexly structured "raw" data of objects. Output: vector representations of objects, then answers.

Applications: classification of images, texts, signals, voice commands, biometric identification of persons…

Models: CNN, AlexNet, ResNet, word2vec, FastText, BERT…

Diagram: clouds of "raw data" with arrows to rows of features, and from them back to clouds — complexly structured answers

Definition (Stage 3: structure → vector → structure). Learned generation of complexly structured data. Input: complexly structured objects. Output: complexly structured answers.

Applications: image captioning and synthesis, style transfer, speech recognition, machine translation, text summarisation, chatbots with emergent abilities…

Models: seq2seq, RNN, LSTM, GAN, VAE, GPT…

At the first stage a person built the features, and the model mapped the feature vector to an answer. At the second, the vectorisation of complex objects — images, texts, signals — became a learned part of the model. At the third, the model also learned to generate complexly structured objects from their vector representations.

Compositionism

Definition (The problem of training an ensemble (composition) of models). Given: $X^{ℓ} = (x_{i}, y_{i})_{i = 1}^{ℓ} \subset X \times Y$ , the training sample; $a_{t} (x, w) = C (b_{t} (x, w))$ , "weak" trainable base models; $b_{t} : X \to R$ , algorithmic operators with parameters $w$ ; $C : R \to Y$ , a decision rule of a simple form (without parameters); $R$ , a convenient space of estimates.

Find: an ensemble $a (x) = C (F (b_{1} (x, w_{1}), \dots, b_{T} (x, w_{T}), x, α))$ , where $F : R^{T} \times X \to R$ is a correcting function with parameters $α$ .

The criterion for training a "strong" algorithm as an ensemble of $T$ base algorithms that are "weak" taken separately:

Q (a, X^{ℓ}) = i = 1 \sum ℓ L (a (x_{i}), y_{i}) \to w_{1}, \dots, w_{T}, α min .

Yu. I. Zhuravlev. On an algebraic approach to solving recognition or classification problems. Problemy Kibernetiki, 1978 (in Russian). M. Kearns, L. G. Valiant. Cryptographic limitations on learning Boolean formulae and finite automata. 1989.

Definition (Examples of correcting (aggregating) functions).

Simple voting: $F (b_{1}, \dots, b_{T}) = \frac{1}{T} \sum_{t = 1}^{T} b_{t}$ .
Weighted voting: $F (b_{1}, \dots, b_{T}, α) = \sum_{t = 1}^{T} α_{t} b_{t}$ , $\sum_{t = 1}^{T} α_{t} = 1$ , $α_{t} ⩾ 0$ .
Feature-weighted linear stacking: $F (b_{1}, \dots, b_{T}, x, v) = \sum_{t = 1}^{T} α_{t} (x) b_{t}$ , $α_{t} (x) = \sum_{j = 1}^{n} v_{t j} f_{j} (x)$ .
A mixture of experts with competence functions (gating functions) $g_{t} : X \to R$ : $F (b_{1}, \dots, b_{T}, x, α) = \sum_{t = 1}^{T} g_{t} (x, α_{t}) b_{t} (x)$ .

Definition (Training predictive models and their ensembles). $L (b, x_{i})$ is the loss function of the model $b (x_{i}, w)$ given the answer $y_{i}$ .

Empirical risk minimisation for the base algorithms:

i = 1 \sum ℓ L (b_{t} (x_{i}, w), y_{i}) \to w min .

Empirical risk minimisation for adding a base algorithm $b_{T}$ to the ensemble, with the previous ones fixed:

i = 1 \sum ℓ L (t = 1 \sum T - 1 α_{t} b_{t} (x_{i}, w_{t}) + α_{T} b_{T} (x_{i}, w_{T}), y_{i}) \to α_{T}, w_{T} min .

Yu. I. Zhuravlev. Correct algebras over sets of incorrect (heuristic) algorithms (I, II, III). Kibernetika, Kiev, 1977–1978 (in Russian). Y. Freund, R. E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. 1995. K. V. Rudakov, K. V. Vorontsov. On methods of optimisation and monotone correction in the algebraic approach to the recognition problem. Doklady RAN, 1999 (in Russian).

Adding base algorithms one at a time, with the previous ones fixed, is the scheme of boosting; in the simplest case each base algorithm is trained separately and then combined by voting, as in bagging and random forests. Yu. I. Zhuravlev's algebraic approach to building correct algorithms out of incorrect heuristic ones was more than a decade ahead of Kearns and Valiant's notion of weak learning and of Freund and Schapire's boosting.

Definition (Estimate-calculating algorithms, ECA (Yu. I. Zhuravlev)). A union of the main non-rigorous (heuristic) principles of the time:

symbolism (deriving rules from data);
evolutionism (selecting the best rules);
analogism (estimates of the similarity of objects);
Bayesianism (classes are mixtures of densities);
connectionism (weighted voting).

a (x) = ar g y \in Y max i : y_{i} = y \sum ω \in Ω \sum w_{ω i} B_{ω i} (x, x_{i}),

where $B_{ω i}$ are binary similarity functions over feature subsets $ω$ :

B_{ω i} (x, x_{i}) = j \in ω ⋀ [∣ f_{j} (x) - f_{j} (x_{i}) ∣ < ε] .

Yu. I. Zhuravlev, V. V. Nikiforov. Recognition algorithms based on the calculation of estimates. 1971 (in Russian).

Network diagram: the inputs f1(x)…fn(x) are connected to blocks of similarity functions B1,1(x, x1)…B|Ω|,ℓ(x, xℓ), those to blocks that sum by class, and the sums with weights λ1…λ|Y| go into an arg max block, with a(x) at the output

Remark (ECA unites many heuristic principles).

$\approx$ a three-layer RBF (radial basis function) neural network;
$\approx$ the method of potential functions: $B_{ω i} (x, x_{i}) = K (\frac{1}{h _{ω i}} ρ_{ω i} (x, x_{i}))$ ;
$\approx$ a linear SVM classifier with a radial kernel;
$\approx$ a Bayesian classifier with mixture densities $p (x ∣ y)$ ;
$\approx$ prototype selection: $w_{ω i} = 0$ for non-prototypes $x_{i}$ ;
$\approx$ feature selection in spherical logical regularities.

Estimate-calculating algorithms are an example of a model that as early as 1971 united the approaches of almost all the schools: estimates of similarity to prototypes over subsets of features, their voting, selection of prototypes and of features.

Definition (The principles of informativeness, consistency, irreducibility).

The informativeness of a predicate $R (x)$ for a class $y \in Y$ :

{p_{y} (R) = # {x_{i} : R (x_{i}) = 1 and y_{i} = y} \to max; n_{y} (R) = # {x_{i} : R (x_{i}) = 1 and y_{i} \neq = y} \to min .

The informativeness of a similarity function $B (x, x^{'})$ :

{p (B) = # {(x_{i}, x_{j}) : B (x_{i}, x_{j}) = 1 and y_{i} = y_{j}} \to max; n (B) = # {(x_{i}, x_{j}) : B (x_{i}, x_{j}) = 1 and y_{i} \neq = y_{j}} \to min .

Consistency: $n_{y} (R) = 0$ , $n (B) = 0$ :
- a test $ω$ : $B_{ω} (x_{i}, x_{j}) = 0$ for all $i, j$ such that $y_{i} \neq = y_{j}$ ;
- a representative set $(ω, i)$ : $B_{ω} (x_{i}, x_{j}) = 0$ for all $j$ such that $y_{i} \neq = y_{j}$ .
Irreducibility: no subset of features $ω^{'} \subset ω$ is a test (or a representative set).

A. N. Dmitriev, Yu. I. Zhuravlev, F. P. Krendelev. On a principle of classification and forecasting of geological objects and phenomena. 1968. Yu. I. Zhuravlev, V. V. Nikiforov. Recognition algorithms based on the calculation of estimates. 1971 (both in Russian).

Example (Problems on small data). Features of geological data in the search for deposits of a rare type (gold, uranium, diamonds, etc.):

few objects ( $7 + 11$ ), many features (more than a hundred);
there is no reliable geophysical model;
the data have gaps, unmeasured values.

F. P. Krendelev, A. N. Dmitriev, Yu. I. Zhuravlev. A comparison of the geological structure of foreign deposits of Precambrian conglomerates by means of discrete mathematics. Doklady AN SSSR. 1967. A. N. Dmitriev, Yu. I. Zhuravlev, F. P. Krendelev. On a principle of classification and forecasting of geological objects and phenomena. 1968 (both in Russian).

Tests and irreducible representative sets were born of such problems: with eighteen objects and a hundred features, statistical methods are powerless, and classification has to be built on combinatorial principles, by searching for minimal consistent feature sets that distinguish objects of different classes.

The practice of machine learning

CRISP-DM: a standard for the data analysis process

Definition (A cross-industry standard for data mining). CRISP-DM (CRoss Industry Standard Process for Data Mining, 1999). Initiating companies: SPSS, Teradata, Daimler AG, NCR Corp., OHRA.

Steps of the process:

business understanding;
data understanding;
data preprocessing and feature engineering;
model development and parameter tuning;
quality evaluation;
deployment.

Definition (The evolution of AI as the automation of CRISP-DM steps).

Expert Systems: rigid rule-based models.
Machine Learning: parametric models trained on data.
Deep Learning: models with learned vectorisation of the data.
AutoML: automatic selection of models and of their structure.
Lifelong Learning: seamless integration into the business process.

Each stage in the development of artificial intelligence automates the next step of the process: machine learning replaced the manual construction of rules by experts with modelling from data; deep learning joined feature preparation to modelling; AutoML automates model selection and evaluation; lifelong learning builds all of this into deployment.

Preprocessing and vectorising data

Definition (Features of the data and of the formulations of applied problems). Data can be:

heterogeneous (features measured on different scales);
incomplete (not everything was measured, there are gaps);
inaccurate (measured with errors);
contradictory (identical objects, different answers);
excessive (very large, does not fit in memory);
insufficient (fewer objects than features);
complexly structured (no feature descriptions).

Risks associated with the problem formulation:

"dirty" data (the customer does not ensure data quality);
unclear criteria of model quality (the customer has not settled on goals or criteria).

Definition (Data preprocessing methods).

Feature transformation: strengthening or weakening the measurement scale of a feature; normalisation, standardisation; transforming the distribution function of a feature.
Feature extraction from raw data, feature engineering.
Representation learning, learned vectorisation of data.
Missing values imputation.
Outlier / anomaly detection.
Dimensionality reduction.
Feature selection, choosing the informative features.

Postprocessing and quality evaluation

Definition (Model evaluation and selection problems). Given: $X^{ℓ} = (x_{1}, \dots, x_{ℓ})$ , the training sample; $A_{t} = {a : X \times W_{t} \to Y}$ , parametric models, $t \in T$ ; $W_{t}$ , the parameter space of the model $A_{t}$ ; $μ_{t} : (X \times Y)^{ℓ} \to W_{t}$ , learning methods, $t \in T$ .

Find: the method $μ_{t}$ with the best generalisation ability.

Special cases:

choosing the best model $A_{t}$ (model selection);
choosing the learning method $μ_{t}$ for a given model $A$ (in particular, hyperparameter optimisation);
feature selection: $F = {f_{j} : X \to D_{j} : j = 1, \dots, n}$ is the set of features; the learning method $μ_{G}$ uses only the features $G \subseteq F$ .

Definition (The methodology of error (or loss) analysis). $L (w, x_{i})$ is the loss function (the smaller the better). The mean loss on a sample $U$ and its empirical distribution:

Q (w, U) = \frac{1}{∣ U ∣} x_{i} \in U \sum L (w, x_{i}); F (λ; w, U) = \frac{1}{∣ U ∣} x_{i} \in U \sum [L (w, x_{i}) ⩽ λ] .

Analysing losses on the training sample:

rank the objects by decreasing loss $L_{i} = L (w, x_{i})$ ;
are the objects with extremely large losses outliers?
if not, how can the model be improved on these objects?

Comparing losses in training and on test:

do the loss distributions differ much?
if they do, how can overfitting be eliminated?

One number, the average quality, is not enough. The distribution of losses over objects shows where the model errs: on a few outliers, or systematically on a whole group of objects; and comparing the distributions in training and on test shows whether there is overfitting and on which objects it shows up.

Definition (A/B testing (split testing)). Two models, "baseline A" and "improved B", built from historical data $X^{ℓ}$ , are tested by a quality metric $Q$ on new data $X^{k}$ .

How does A/B testing differ from an ordinary hold-out?

$X^{k}$ is genuinely future data (out-of-time), not part of the past data excluded from training (out-of-sample);
more realism: the properties of the data stream may change over this time, real data need not be i.i.d.;
a one-off choice of model hardly overfits;
accumulating the data $X^{k}$ may take a long time;
the model's operation may affect how the data stream is formed (in recommender systems, for example).

Definition (Meta-learning (learning to learn)). The problem: too many methods, too long to run.

Given: a sample of "problem, method" → quality criteria.

Find: a multiclass classification model that predicts which method to solve a problem with.

Criterion: the accuracy of predicting the optimal method.

Features: the size characteristics of the problem; characteristics of the feature space — types, outliers, gaps, correlations; the results of fast low-dimensional methods.

Joaquin Vanschoren. Meta-learning Architectures: Collecting, Organizing and Exploiting Meta-knowledge. 2009. Joaquin Vanschoren. Meta-Learning: A Survey. 2018.

Definition (Automatic selection of models and hyperparameters (AutoML)). The problem: choosing the model structure (the architecture of a neural network) and the hyperparameters takes too many resources.

Given: a sample of "problem, structure" → quality criteria.

Find: which experiment to run next with the model.

Criterion: minimise the resources spent on an automatic search for an optimal model comparable in quality to models built by professional researchers.

A close classical problem is experiment design.

Xin He et al. AutoML: A Survey of the State-of-the-Art. 2019.

Meta-learning and AutoML are machine learning applied to the process of machine learning itself: the objects become problems and experiments, and the answers the quality of the methods on them.

The bottom line

Remark (The bottom line).

We start with the problem formulation: the DNA (given, find, criterion).
P. Domingos (2015) was wrong that the "master algorithm" (AGI) would appear as a union of the approaches of the main scientific schools.
Yu. I. Zhuravlev had already done that in the estimate-calculating algorithms (1971), but it did not lead to AGI.
It is now clear that the ingredients of success are quite different:
1. learned vectorisation of data → deep learning;
2. big data + big models + neural processors;
3. high dimensions + optimisation without overfitting;
4. large language models → emergence.

Literature

K. V. Vorontsov. Lectures on Machine Learning (in Russian).
S. Nikolenko. Machine Learning: Foundations. 2025 (in Russian).
K. P. Murphy. Probabilistic Machine Learning: An Introduction. 2022; Probabilistic Machine Learning: Advanced Topics. 2023.
M. P. Deisenroth, A. A. Faisal, C. S. Ong. Mathematics for Machine Learning. 2020.
Christopher Bishop, Hugh Bishop. Deep Learning: Foundations and Concepts. 2024.
S. Markov. Hunting Electric Sheep: The Big Book of Artificial Intelligence. 2024 (in Russian).
P. Domingos. The Master Algorithm: How the Quest for the Ultimate Learning Machine Will Remake Our World. 2015.

Machine Learning 1. Lecture 15. A Short Review of the Semester