Konstantin Vorontsov

Vector representations (embeddings) of texts and graphs: the distributional semantics hypothesis, syntagmatic and paradigmatic similarity of words, the CBOW and Skip-gram models of the word2vec program, hierarchical SoftMax on a Huffman tree, negative sampling (SGNS) and the connection of word2vec with the matrix factorisation of the PMI matrix, semantic analogies of words, the FastText model on character n-grams; texts as graphs; multidimensional scaling and the stress criterion, stochastic neighbour embedding SNE, perplexity, t-SNE; matrix factorisations of graphs, the random-walk models DeepWalk and node2vec; graph embedding methods as autoencoders, the generalised GraphEDM model, graph neural networks and message passing.

Kohonen networks: clustering as a two-layer neural network, the hard (WTA) and soft (WTM) competition rules, self-organising Kohonen maps and their interpretation; autoencoders: the formulation of the problem, the linear autoencoder and the principal component method, sparse, denoising, contractive, relational and variational autoencoders, reparametrisation, autoencoders for supervised learning, multilayer autoencoders; joint training of several models: pre-training and transfer learning, multi-task learning and few-shot learning, self-supervised learning, distillation and surrogate modelling, learning using privileged information (LUPI), generative adversarial networks (GAN).

Reminder: the neuron model, the multilayer network, stochastic gradient, momentum, vanishing and exploding gradients, ReLU, dropout, batch normalisation; depth matters more than width; feature generation and end-to-end learning; convolutional neural networks: convolution and pooling layers, the standard CNN scheme, AlexNet and ImageNet, residual networks ResNet and Highway Networks; convolutional networks for speech, texts and games; recurrent neural networks, training by BPTT, long short-term memory networks LSTM, the peephole variant, GRU.

A closing review of the first semester: empirical risk minimisation and gradient methods; underfitting, overfitting, multicollinearity and regularisation; optimisation formulations of supervised learning (regression, classification, ranking) and unsupervised learning (density, mixtures, clustering, one-class classification, semi-supervised learning, PU-learning, principal component analysis, autoencoders); the six scientific schools of machine learning — symbolism, evolutionism, analogism, Bayesianism, connectionism, compositionism — and their Soviet roots; estimate-calculating algorithms; practice: CRISP-DM, data preprocessing, model evaluation and selection, loss analysis, A/B testing, meta-learning and AutoML.

Anomaly and novelty detection; heuristic anomaly scores: local density, isolation forest, a mixture with a background component, robust principal component analysis; outlier removal in nonparametric regression, the LOWESS algorithm; anomaly as the value of the loss function; the theory of robust learning: slowly growing functions, iterative reweighting of objects with IRS and IRLS, robust loss functions, the median, the quantile and the censored mean, robust aggregation functions and their smoothing, the IR-ERM algorithm; one-class SVM, learning from positive and unlabeled objects (PU-learning), problems with new and unknown classes.

The clustering problem and its ill-posedness, the aims of clustering, types of cluster structure, sensitivity to the choice of metric; the problem of semi-supervised learning and transductive learning, why it reduces neither to classification nor to clustering; criteria of clustering quality, the silhouette coefficient, the BCubed measures of precision and recall; the k-means method (Lloyd's algorithm) as a simplification of the EM algorithm for a mixture of Gaussians; the DBSCAN algorithm; agglomerative hierarchical clustering, the Lance–Williams formula and its special cases, the dendrogram, monotonicity, contracting and dilating distances, Ward's distance; semi-supervised learning based on classification: self-training, co-training, co-learning, the transductive SVM, expectation regularisation (XR).

The probabilistic formulation of classification: prior and posterior class probabilities, class likelihood functions, the maximum a posteriori principle; the optimal Bayes classifier and losses from errors; empirical estimation of prior probabilities and class densities; the naive Bayes classifier, features with exponential-family densities and the linear naive Bayes classifier; a survey of Bayesian classifiers: the Parzen window method, the quadratic discriminant, Fisher's linear discriminant, Gaussian mixtures with diagonal covariance matrices, and the radial basis function network.

Estimating a probability density from a sample: the maximum likelihood principle, the multivariate Gaussian density and its geometric meaning, multicollinearity and regularisation of the covariance matrix; separating a mixture of distributions, the EM algorithm as a method of simple iterations, the Gaussian mixture (GMM); the nonparametric Parzen–Rosenblatt estimate, the choice of kernel and window width; Bayesian classification theory: the generative and discriminative approaches, the optimal Bayes classifier, the Parzen window method, the quadratic discriminant, Fisher's linear discriminant, the radial basis function network and its training by the EM algorithm.

Bias–variance analysis: the decomposition of the error into noise, bias and variance, the bias and variance of simple voting, why complex ensembles do not overfit; gradient boosting for an arbitrary loss function as a parametric approximation of a gradient step; stochastic gradient boosting; special cases: regression, AdaBoost, AnyBoost, variants of loss functions; XGBoost: the tree as a linear model, L0 and L2 regularisation, analytical leaf values and the splitting criterion; CatBoost: leakage in the gradients, ordered boosting on subsamples of doubling length, unbiased target statistics for categorical features.

Ensembles of models: base algorithms, the space of estimates, the decision rule and correcting functions; the problem of diversity of base algorithms; bagging, the random subspace method and a common pseudocode of stochastic ensembling; the unbiased out-of-bag estimate and estimating feature importance; converting simple voting into weighted voting; the random forest; boosting for binary classification with abstentions, the exponential approximation of the threshold loss function, the main theorem of AdaBoost with proof, convergence, classical AdaBoost and heuristics; why boosting does not overfit: experiments, bounding the probability of error through margins, the distribution of margins, comparison with bagging; the ComBoost algorithm.

The interpretability of models; decision trees and the greedy ID3 algorithm; the axioms of impurity, the entropy and Gini criteria; handling missing values; the merits and drawbacks of the greedy strategy; tree pruning (post-pruning); CART regression trees and Minimal Cost-Complexity Pruning; rule induction: logical regularities, families of rules (conjunctions, syndromes, half-planes, balls), search metaheuristics, a tree as a covering set of conjunctions; the Pareto front in (p,n) space, logical and statistical regularities, Fisher's exact test, informativeness criteria; building a classifier from regularities.

The problem of estimating generalization ability; the error matrix and the probability of overfitting; the case of a single algorithm and the hypergeometric distribution; the principle of uniform convergence of frequencies and Boole's inequality; the Vapnik–Chervonenkis bound, the growth function and the capacity of a family of algorithms; inverting the bound and the complexity penalty; structural risk minimization; the splitting and similarity effects; the Occam's razor bound and its link to regularization.