Курс Машинное обучение. 1 семестр

Литература | 2 семестр

Введение (intro)🔗

• Основные термины и задачи машинного обучения.
• Признаки, их виды и свойства. Переход между категориальными и численными признаками.
• Функция потерь. Оптимизация.
• Ошибки первого и второго рода. Метрики качества: accuracy, precision, recall, F1-score.
• Случайный поиск. Перебор по сетке.
• Проблемы работы с данными высокой размерности.

Градиентный спуск (gradient descent)🔗

• Производная, частные производные, градиент. Методы оценки градиента.
• Градиентный спуск, проблема выбора шага.
• Стохастический градиентный спуск.
• Использование момента. Метод Нестерова.
• Метод отжига.
• Adagrad, Adadelta, RMSProp, Adam.
• AMSGrad, AdamW, YellowFin, AggMo, Quasi-Hyperbolic Momentum, Demon.*

Литература: Ruder S., An overview of gradient descent optimization algorithms

Линейная регрессия (linear regression)🔗

• Постановка задачи линейной регрессии. Вероятностная интерпретация.
• Метод наименьших квадратов. Алгебраическое и оптимизационное решения.
• Ковариация, корреляция.text
• Коэффициент деретминации (критерий R²).
• Анализ остатков. Гомоскедастичность. Квартет Анскомба.
• Решение для неквадратных и плохо обусловненных матриц.
• Регуляризация LASSO, Ridge, Elastic.
• Обобщённые аддитивные модели (generalized additive models)*.
• Partial Least Squares*.

Литература: Дьяконов А.

Логистическая регрессия (logistic regression)🔗

• Сигмоид.
• Метод наибольшего правдоподобия.
• Логистическая регрессия. Вариант для меток  − 1, 1.
• Пробит-регрессия (probit regression)*.
• Обобщённые линейные модели (generalized linear models)*.

Глобальная оптимизация. Генетический алгоритм (genetic algorithm)🔗

• Многопараметрическая оптимизация.
• Доминация и оптимальность по Парето.
• Функция качества (fitness). Аппроксимация качества.
• Общая идея генетического алгоритма.
• Представление генома.
• Методы селекции: пропорционально качеству, универсальная выборка (stochastic universal sampling), с наследием (reward-based), турнир. Стратегия элитизма.
• Методы кроссовера. Двух и много-точечный, равномерный (по подмножествам), для перестановок.
• Мутация. Влияние на скорость обучения.
• Управление популяцией. Сегрегация, старение, распараллеливание.
• Генетическое программирование*.

Деревья решений (decision trees)🔗

• Понятие энтропии, определение информации по Шеннону.
• Понятие дерева решений.
• Метрики: примеси Джини (Gini impurity), добавленная информация (information gain).
• Алгоритмы ID3, CART.
• Борьба с оверфиттингом: bagging, выборки признаков (random subspace method).
• Ансамбли, случайный лес (Random Forest).
• Деревья регрессии. Метрика вариации.
• Непрерывные признаки. Использование главных компонент вместо признаков.
• Сокращение дерева (pruning).
• Другие алгоритмы вывода правил: 1-rule, RIPPER, bayesian rule lists*.
• Комбинация с линейной регрессией (RuleFit)*.

Литература: Olah C., Visual Information Theory

Композиция классификаторов. Бустинг (boosting)🔗

• Понятие бустинга. Бустинг для бинарной классификации, регрессии.
• Градиентный бустинг.
• AdaBoost. Алгоритм Виолы-Джонса.
• Извлечение признаков. Признаки Хаара (Haar).
• Бустинг деревьев решений. XGBoost.
• CatBoost
• LPBoost, BrownBoost, ComBoost*.

Метрики и метрическая кластеризация (metrics)🔗

• Понятие и свойства метрики. Ослабление требования к неравенству треугольника.
• Метрики L₁, L₂, Хемминга, Левенштейна, косинусное расстояние.
• Потеря точности нормы в высоких размерностях.
• Нормализация координат. Предварительная трансформация пространства признаков.
• Метрика Махаланобиса.
• Понятие центроида и представителя класса.
• Центроидные алгоритмы: k-means, k-medoid. Алгоритм Ллойда.

Метод ближайших соседей (k-NN)🔗

• Базовый алгоритм классификации методом 1-NN и k-NN. Преимущества и недостатки.
• Кросс-валидация методом "без одного" (leave one out).
• Определение границ, показатель пограничности (border ratio).
• Сжатие по данным. Понятия выброса, прототипа, усвоенной точки. Алгоритм Харта (Hart).
• Регрессия методом k-NN.
• Взвешенные соседи.
• Связь с градиентным спуском. Стохастическая формулировка, softmax.
• Метод соседних компонент (neighbour component analysis)*.
• Связь с выпуклой оптимизацией. Метод большого запаса (Large margin NN)*.
• Оптимизация классификатора, k-d деревья, Hierarchical Navigable Small World*.
• Хеши чувствительные к локальности, хеши сохраняющие локальность*.

Кластеризация (clustering)🔗

• Задача обучения без учителя, применения при эксплораторном анализе.
• Иерархическая кластеризация: методы снизу вверх и сверху вниз.
• Алгоритмы, основанные на связности: функция схожести, компоненты связности и остовные деревья, критерии связности.
• Алгоритм BIRCH*.
• Алгоритмы, основанные на плотности: DBSCAN, OPTICS.
• Алгоритмы, основанные на распределении: сумма гауссиан.
• Нечёткая кластеризация, алгоритм c-means.
• Поиск моды (Mean-Shift)*.
• Внутренние оценки качества: leave-one-out, силуэт, индекс Дэвиса-Болдина (Davies-Bouldin), индекс Данна (Dunn).
• Внешние оценки качества.

Снижение размерности (dimensionality reduction)🔗

• Постановка задачи, причины и цели снижения размерности.
• Выбор и извлечение признаков.
• Подходы к выбору признаков: filtering, wrapping, embedding.
• Расстояние между распределениями. Расстояние Кульбака-Лейблера. Взаимная информация.
• Алгоритмы выбора признаков: на основе корреляции (CFS), взаимной информации, Relief.
• Метод главных компонент (PCA).
• Многомерное шкалирование (multidimensional scaling). Isomap.
• Стохастическое вложение соседей с t-распределением (t-SNE).
• Нелинейные обобщения метода главных компонент. Kernel PCA.*
• Неотрицательное матричное разложение (NMF).*
• Анализ независимых компонент (ICA).*

Наивный байесов классификатор (naive Bayes)🔗

• Условная вероятность. Байесово решающее правило. Обновление вероятностей.
• Наивный классификатор, предположение о независимости признаков.
• Оценка плотности распределения для числовых признаков.
• Эффективные алгоритмы наивного классификатора.
• Мультиномиальный и комплементный классификатор, сглаживание оценок.
• Варианты для числовых, категориальных, бинарных признаков.
• Байесова оптимизация*.
• Алгоритм EM*.

Работа с текстом (text)🔗

• Задачи обработки текста: извлечение (extraction), поиск, классификация (тематическая, эмоциональная), перевод
• Разбиение на слова, пунктуация, лексический и морфологический анализ
• Определение частей речи, имён, основ слов
• Частотный анализ, представление bag-of-words, TF-IDF и его варианты
• N-грамы, byte-pair encoding.
• Векторные представления, семантическая интерпретация алгебраических операций
• Унитарный код (One-hot encoding).
• Алгоритмы Word2Vec и FastText.
• Алгоритм GloVe.
• Вероятностный латентно-семантический анализ (pLSA)*.
• Латентное размещение Дирихле (Latent Dirichlet allocation)*.

Работа с изображениями (image)🔗

• Дискретизация аналогового сигнала, теорема Котельникова.
• Понятие спектра.
• Преобразование Фурье. Дискретное косинусное преобразование (DCT).*
• Сверточные фильтры, непрерывное и дискретное определение свёртки.
• Сглаживающие фильтры. Фильтр Гаусса.
• Дифференцирующие фильтры: Roberts cross, Sobel, Prewitt, Scharr.
• Поиск границ. Алгоритм Кенни (Canny). Адаптивное сглаживание. Определение порога методом Отцу (Otsu).
• Преобразование Хафа (Hough). Оптимизация с учётом направления градиента. Обобщения на многопараметрический и многомерный случай.

Интерпретация (interpretation)🔗

• Визуализация вклада признаков: partial dependency plot, individual conditional expectation, accumulated local effects.