LibreTimes

Search results for “k-средних”

120 results

Machine Learning 1. Lecture 13. Clustering and Semi-Supervised Learning

2026LectureКонстантин Вячеславович Воронцов

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).
0
280

Machine Learning. Additional Lecture 1. The Theory of Overfitting

2026LectureКонстантин Вячеславович Воронцов

The combinatorial theory of overfitting: the probability of overfitting and why the Vapnik–Chervonenkis bounds are loose; experiments with overfitting — a monotone chain of algorithms, the effect of splitting and connectivity of the family on the probability of overfitting and on the complete cross-validation estimate, overfitting of chains, the exact formula for the probability of overfitting when choosing between two algorithms; the splitting–connectivity graph of a family of algorithms, examples for linear classifiers, a monotone chain and a two-dimensional net; generating and forbidden sets, upper connectivity and inferiority of an algorithm; the splitting–connectivity upper bound, the idea of its proof and its properties.
1
220

Machine Learning 2. Lecture 3. Vector Representations of Texts and Graphs

2026LectureКонстантин Вячеславович Воронцов

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.
0
250

Vector calculus. Stokes' theorem. Circulation

2026Problem sheetSergey

Circulation of a field as the flux of its curl: computing the curl, matching the orientation of the contour and the normal, circulation computed two ways.
0
310

Machine Learning 1. Lecture 4. Metric Methods of Classification and Regression

2026LectureКонстантин Вячеславович Воронцов

The continuity and compactness hypotheses; the Minkowski metric and feature-free distances; the generalized metric classifier, the k nearest neighbours method, the Parzen window and the method of potential functions as a linear classifier; complete cross-validation, the compactness profile and the exact CCV formula for the nearest neighbour method; prototype selection; Nadaraya–Watson kernel smoothing, the choice of kernel and bandwidth.
0
150

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

2026LectureКонстантин Вячеславович Воронцов

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.
0
480

Алгебра 1. Лекция 4. Формальные степенные ряды и производящие функции

2026LectureAlexey Ilyin

В этой лекции рассматриваются формальные степенные ряды как алгебраический объект. Вводятся операции сложения, умножения, а также аналоги производной и интеграла. Ключевая идея лекции — применение этого аппарата для решения линейно-рекуррентных соотношений с помощью производящих функций, что демонстрируется на классическом примере чисел Фибоначчи.
2
240

Machine Learning 1. Generalization Theory

2026LectureКонстантин Вячеславович Воронцов

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.
0
140

Machine Learning 2. Lecture 2. Neural Networks for Unsupervised Learning

2026LectureКонстантин Вячеславович Воронцов

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).
0
210

Algebra 1. Lecture 2

2026LectureАртём Авилов

The order of an element and of a group, the order of a permutation as the lcm of its cycle lengths; generators and cyclic groups; homomorphisms and isomorphisms of groups, the classification of cyclic groups; examples — the sign of a permutation, inversion in an abelian group, the exponential, the determinant, S3S_3 and D3D_3; subgroups, kernel and image, the injectivity criterion; left and right cosets and the partition into them; normal subgroups and conjugation, the index, Lagrange's theorem, subgroups of index 2; the quotient group; the homomorphism theorem with examples; conjugate elements, the centre, a group action on a set.

0
150

Combinatorial probability and the tightness of generalization bounds

2008Journal articleK. V. Vorontsov

Pattern Recognition and Image Analysis

Accurate prediction of the generalization ability of a learning algorithm is an important problem in computational learning theory. The classical Vapnik-Chervonenkis (VC) generalization bounds are too general and therefore overestimate the expected error. Recently obtained data-dependent bounds are still overestimated. To find out why the bounds are loose, we reject the uniform convergence principle and apply a purely combinatorial approach that is free of any probabilistic assumptions, makes no approximations, and provides an empirical control of looseness. We introduce new data-dependent complexity measures: a local shatter coefficient and a nonscalar local shatter profile , which can give much tighter bounds than the classical VC shatter coefficient . An experiment on real datasets shows that the effective local measures may take very small values; thus, the effective local VC dimension takes values in [0, 1] and therefore is not related to the dimension of the space.

0
7

Exact combinatorial bounds on the probability of overfitting for empirical risk minimization

2010Journal articleK. V. Vorontsov

Pattern Recognition and Image Analysis

Three general methods for obtaining exact bounds on the probability of overfitting are proposed within statistical learning theory: a method of generating and destroying sets, a recurrent method, and a blockwise method. Six particular cases are considered to illustrate the application of these methods. These are the following model sets of predictors: a pair of predictors, a layer of a Boolean cube, an interval of a Boolean cube, a monotonic chain, a unimodal chain, and a unit neighborhood of the best predictor. For the interval and the unimodal chain, the results of numerical experiments are presented that demonstrate the effects of splitting and similarity on the probability of overfitting.
0
9

Splitting and similarity phenomena in the sets of classifiers and their effect on the probability of overfitting

2009Journal articleK. V. Vorontsov

Pattern Recognition and Image Analysis

It is shown that computationally tight bounds for the probability of overfitting can be obtained only by simultaneous consideration of the following two properties of classifier sets: splitting into error levels and similarity of classifiers. For a set consisting of only two classifiers, an exact bound is obtained for the probability of overfitting. This is the simplest learning task that exhibits overfitting and the effects of splitting and similarity, which reduce the probability of overfitting. For a more complex case—a chain of classifiers—an experiment is carried out in which the effects of splitting and similarity are estimated separately. It is shown that reasonably low probabilities of overfitting can be obtained only for the sets that possess both properties.
0
4