# <center>ML exam</center>

## **Теоретический минимум**
### 1. Принцип минимизации эмпирического риска.
**Эмпирический риск** (Empirical Risk) — это средняя величина ошибки алгоритма на обучающей выборке.

#### Задача обучения
Пусть $X$ — множество описаний объектов, $Y$ — множество допустимых ответов. Предполагается, что существует неизвестная целевая зависимость — отображение $y^{*}:\: X\to Y$, значения которой известны только на объектах конечной обучающей выборки $X^m = \{(x_1,y_1),\ldots,(x_m,y_m)\}$.

Задача обучения состоит в том, чтобы построить алгоритм $a:\: X\to Y$, который приближал бы неизвестную целевую зависимость как на элементах выборки, так и на всём множестве $X$.

#### Функция потерь и эмпирический риск
Вводится ***функция потерь*** ${\mathcal L}(y,y')$, характеризующая величину отклонения ответа $y=a(x)$ от правильного ответа $y'=y^{*}(x)$ на произвольном объекте $x\in X$.

Вводится ***модель алгоритмов*** $A= \{a:\: X\to Y\}$, в рамках которой будет вестись поиск отображения, приближающего неизвестную целевую зависимость.

**Эмпирический риск** — это функционал качества, характеризующий среднюю ошибку алгоритма a на выборке $X^m$:

$$Q(a,X^m) = \frac{1}{m} \sum_{i=1}^m {\mathcal L}(a(x_i),y^{*}(x_i)).$$
**Метод минимизация эмпирического риска** заключается в том, чтобы в заданной модели алгоритмов $A$ найти алгоритм, доставляющий минимальное значение функционалу эмпирического риска:

$$a = \mathrm{arg}\min_{a\in A} Q(a,X^m).$$

$f_\theta(x)$ -- прогноз модели
$y$ -- истинное значение отклика
${\mathcal L}(f_\theta(x),y)$ -- функция потерь
$p(x,y)$-- плотность объектов в пространстве.
Минимизируем ожидаемые потери. Найдем $\theta$ т.o., чтобы **минимизировать матожидание потерь**(критерий оптимизации параметров модели). Мы не можем оценить теоретический риск, т к неизвестна плотность объектов. Если известна плотность, то могли бы предсказывать по объекту максимально вероятный $y$. Но т к маленькая выборка мы не можем оценить плотность. Что делаем?
Как делают в статистике: есть величина $L$ и мы не пожем взять честно ее матожидание, то заменяем ее на эмпирическое среднее $\overline {\mathcal L}$ т е $E\mathcal L\rightarrow \overline {\mathcal L}$.
**Теоретический риск** -- то, к чему стремимся в теории, а эмпирический риск -- то, что можем посчитать на практике (выборочное среднее).

### 2. Классификация с помощью дискриминантных функций.

Любой классификатор описывается некоторым набором дискриминантных функций.
***Дискриминантная функция*** на вход принимает объект $x$ и она определена своя для каждого класса, считает рейтинг насколько вероятно, что объект принадлежит соответсвующему классу.


**Граница** -- множество точек, на котором нельзя однозначно определить класс. **Отступ** по сути показывает, насколько близко мы приблизились к корректной классификации; знак отступа показывает, правильная классификация (+) или нет (-).

У линейного классификатора граница будет линейная, т. к. его задает множество {первая дискриминантная функция равна второй}, а его дискр. функции линейные.

### 3. Преобразование категориальных признаков: через частоту встречаемости категорий, one-hot encoding и mean-value encoding

***Нормализация признаков*** -- масштабирование с целью избежать подстраивания модели под отдельные признаки с большими масштабами.
Диапазонное шкалирование применяют к разреженным данным (много нулей), т.к. оно сохраняет свойство разреженности (0 -> 0).

***One-hot кодирование*** -- каждой категории сопоставляем бинарный вектор, чтобы можно было однозначно восстановить категорию. *Недостаток:* если категорий много то матрица объекты-признаки сильно быстро разрастается. Другой вариант: кодировать двоичной записью, тогда понадобится $k$ столбцов, где $2^k >= C$ -- способ one hot encoding с меньшими размером матрицы.

***Mean-value encoding*** -- кодирование средней величиной target'а по классу. Видно, что иногда неоднозначная восстанавливаемость исходной категории, но для больших данных будет редко возникать такая проблема. При таком кодировании фактически происходит подглядывание в таргеты. Чем больше категорий и чем меньше объектов на каждую категорию, тем сильнее переобучение. Для этого нужно делать кодирование на валидационной выборке, а использовать на оставшейся. Еще один вариант избежать переобучения -- кодировать исходя не из таргета, а какой-то другой величины.

Для временных рядов: хотим посчитать евклидово расстояние между рядами, и для этого пытаемся максимально сблизить структуру этих двух рядов.

### 4. Определение линейного классификатора (бинарный/многоклассовый).
### 5. Отступ для классификатора (бинарного/многоклассового).
***Margin (оступ)*** – характеризует качество классификации, от рейтинга корректного класса вычитаем максимальный рейтинг среди всех некорректных классов. Относительная величина, показывающая, с каким запасом побеждает правильный класс. Если отступ положительный, то корректный класс, иначе некорректный. Отступ непрерывная величина.

### 6. Типичные функции потерь для регрессии и бинарной классификации (среди выпуклых).


Здесь $F(.)$ -- монотонное убывающее преобразование.


### 7. Метод градиентного спуска, метод стохастического градиентного спуска. Выбор шага обучения.

### 8. Матрица ошибок. Точность, полнота (с обобщением на многоклассовый случай), F-мера.
### 9. Понятие калибровки вероятностей, шкалирование Платта.

Шкалирование Платта -- параметрический метод найти функцию, которая будет переводить дискр. ф-ю в вероятность. Находится с помощью подбора параметров методом макс. правдоподобия для сигмоиды.
Изотоническая регрессия позволяет получить монотонно неубывающую кривую. Мы апроксимируем $y$ кусочно-постоянной функцией, которая неубывает с ростом $x$.

### 10. Логистическая регрессия в бинарном и многоклассовом случае.


### 11. Принцип максимизации условного правдоподобия.

В статистике выбираем параметр так чтобы максимизировать правдоподобие. Т е это метод оценивания неизвестного параметра путём максимизации функции правдоподобия (это совместное распределение выборки из параметрического распределения, рассматриваемое как функция параметра. При этом используется совместная функция плотности (в случае выборки из непрерывного распределения) либо совместная вероятность (в случае выборки из дискретного распределения), вычисленные для данных выборочных значений.)
Считаем, что наблюдения $X$ фиксированные, а случайными величинами считаем $Y$, поэтому можем считать правдоподобие при условии константного $X$:
Здесь используется то, что $p(y|x) = \sigma(y \langle w,x \rangle)$ (в лог регрессии).

### 12. ROC кривая, значения по осям, AUC - два определения.
### 13. Обобщение методов через ядра. Типичные ядра: линейное, полиномиальное, Гауссово (RBF).
### 14. Решающие правила в дереве CART и алгоритм их выбора. Возможные критерии информативности для регрессии и классификации.
### 15. L1 и L2 регуляризаторы, какая из них может отбирать признаки и почему?
### 16. Определение логистической регрессии (бинарный и многоклассовый случай).
### 17. Построение многоклассового классификатора через бинарные: схемы one-vs-all, one-vs-one.
### 18. Метод опорных векторов (классификация). Оптимизационная задача (прямая). Геометрическая интуиция подхода.
### 19. Стэкинг моделей. Почему нельзя обучать базовые и агрегирующую модель на одной и той же выборке?

Нельзя потому что будет переобучение

### 20. Алгоритм случайного леса (RandomForest) и особо случайных деревьев (ExtraRandomTrees).
### 21. Алгоритм градиентного бустинга. Его обоснование через разложение потерь 1го порядка. Shrinkage и subsampling, их мотивация.
### 22. Подпространство наилучшей аппроксимации в методе главных компонент. Оценка качества аппроксимации в методе главных компонент.
### 23. Расчет важности признаков через решающие деревья и permutation feature importance.
### 24. Алгоритм последовательного включения в отборе признаков. Лучевой поиск (beam search).

## Билеты
### 1. Виды обучения: с учителем (supervised), без учителя (unsupervized), частичное (semi-supervised), трансдуктивное. Типы признаков и типы откликов. Принцип минимизации эмпирического риска. Переобучение, ее зависимость от размера обучающей выборки и сложности модели. Дискриминантные функции.

Обучение с учителем (регрессия, классификация)
Пример трансдуктивного обучения: у нас есть библиотека, полная книг, и мы хотим эти книги разбить на классы.
Обучение без учителя (кластеризация, снижение размерности, обнаружение аномалий, поиск ассоциативных правил)

***Переобучение*** происходит, когда алгоритм слишком сильно подстраивается под обучающую выборку. При этом модель получается слишком сложной, что уменьшает ошибку на обучающей выборке, но при этом увеличивает ошибку на тесте.

### 2. Метод ближайших центроидов и K ближайших соседей. Взвешенный учет объектов. Пример весов. Функции близости и расстояния (косинусная, Махаланобиса и др.).

***Метод ближайших центроидов*** решает задачу классификации. Суть: объекты каждого класса в обучающей выборке группируются и усредняются, таким образом в соответствие каждой группе ставится усредненный представитель -- *центроид*. Для классификации объекта находится ближайший к нему центроид, и назначается преобладающий в центроиде класс.

*Дискриминантные функции*: $1 / r(\mu_c), -r(\mu_c)$, где $r(\mu_c)$ -- расстояние до центроида.
*Вычислительная сложность эффективной реализации:* $O(ND)$. (N количество элементов при суммировании, D количество классов)
*Вычислительная сложность предсказания для одного объекта:* $O(CD)$. (С количество центроид, D количество классов)

***Метод K ближайших соседей*** решает задачи классификации и регрессии. $K$ -- заранее фиксируемый гиперпараметр. Базовое предположение: близким объектам соответствуют похожие отклики. Суть: рассматривается K ближайших к объекту соседей и присваивается наиболее часто встречающийся среди них класс (классиф.) или их средний отклик (регр.).

*Дискриминантные функции*: количество объектов класса $c$ среди ближайших соседей.
*Вычислительная сложность обучения:* $O(ND)$ (просто занесение объектов в память).
*Вычислительная сложность предсказания для одного объекта методом одного ближ. соседа:* $O(ND)$ ($O(NDK)$ для K соседей).
P.S. с увеличением К метод становится более простым, т.к. пропадают тонкие различия.
Параметры метода: число ближайших соседей $K$ и функция расстояния $\rho(x, x')$ .
Прогнозы методом $KNN$ зависят от масштабирования признаков (увеличение масштаба отдельного признака повышает его значимость), поэтому нужна нормализация.

***Взвешенный учет объектов.*** Идея: хочется, чтобы в случае спорных ситуаций предпочтение отдавалось не случайному классу, а более подходящему по каким-то критериям -- например, с меньшим расстоянием до объекта.
Стандартный метод:
Взвешенное голосование:

Применение косинусной меры близости к текстам. Допустим, текст кодируется некоторым вектором, каждый элемент которого представляет собой количество раз, которое это слово встретилось в тексте. Если мы хотим по некоторой фразе искать подходящий текст с помощью такой кодировки, то евклидовые расстояния между запросом и текстами будут очень большие, а косинусная мера близости, не зависящая от норм, выдаст нормальный результат для близких по смыслу текстов.

Будем вводить **расстояние Махаланобиса** постепенно. Пусть у нас признаки зависимы друг от друга. Тогда даже если евклидово расстояние между парами объектов будет одинаковым, объекты внутри пар могут быть как очень похожими, так и совсем разными, и нам хочется это учитывать.
Давайте перед началом работы с признаками их декоррелируем. Здесь $F$ -- распределение $x$, $\mu$ - среднее, $\Sigma$ - матрица ковариаций. На выходе вектор $z$ линейно и монотонно связан с исходным вектором, и при этом новые признаки нескоррелированы, $Ez = 0, cov(z, z) = I$.
Для вычисления расстояния между двумя бинарными векторами можно применять ***расстояние Хемминга*** -- кол-во отличающихся бит в бинарных последовательностях.
Если нужно искать расстояние между множествами $A$ и $B$ (например, примерную одинаковость товаров в двух чеках), подойдет ***расстояние Жаккарда***: $sim(A, B) = \frac{|A \cap B|}{|A \cup B|}$.

### 3. Нормализация признаков. Преобразование категориальных признаков: через частоту встречаемости категорий, one-hot encoding и mean-value encoding. Функции расстояния для строк (редакторское и максимально общая подстрока), алгоритм динамической трансформации временной шкалы.

***Нормализация признаков*** -- масштабирование с целью избежать подстраивания модели под отдельные признаки с большими масштабами.
Диапазонное шкалирование применяют к разреженным данным (много нулей), т.к. оно сохраняет свойство разреженности (0 -> 0).

***One-hot кодирование*** -- каждой категории сопоставляем бинарный вектор, чтобы можно было однозначно восстановить категорию. *Недостаток:* если категорий много то матрица объекты-признаки сильно быстро разрастается. Другой вариант: кодировать двоичной записью, тогда понадобится $k$ столбцов, где $2^k >= C$ -- способ one hot encoding с меньшими размером матрицы.

***Mean-value encoding*** -- кодирование средней величиной target'а по классу. Видно, что иногда неоднозначная восстанавливаемость исходной категории, но для больших данных будет редко возникать такая проблема. При таком кодировании фактически происходит подглядывание в таргеты. Чем больше категорий и чем меньше объектов на каждую категорию, тем сильнее переобучение. Для этого нужно делать кодирование на валидационной выборке, а использовать на оставшейся. Еще один вариант избежать переобучения -- кодировать исходя не из таргета, а какой-то другой величины.

Для временных рядов: хотим посчитать евклидово расстояние между рядами, и для этого пытаемся максимально сблизить структуру этих двух рядов.

### 4. Локально константная регрессия (Надарая-Ватсона) и локально линейная регрессия. Параметр ширины окна. Виды ядер.

Пусть мы хотим моделировать некоторую нелинейную зависимость. На первом шаге будем моделировать константную зависимость -- найдем оптимальный константный прогноз, минимизируя квадратическую ошибку.
***Регрессия Надарая-Ватсона*** -- локальный константный прогноз. Идея: мы сохраняем методологию константного прогноза, но объекты учитываем с разными весами: чем объекты ближе к тому, для которого делаем прогноз, тем их вес больше. Локальным оптимальным константным прогнозом получится взвешенное среднее.

***Функция ядра $K$*** нужна для моделирования возрастания и убывания весов в зависимости от расстояния.
***Ширина окна $h$*** -- гиперпараметр, нужный для масштабирования расстояния.

Виды ядер:

Немного о модели:
При выборе $h(x)$ = расстояние до $k$-го ближайшего соседа с top-hat ядром регрессия Н-В превращается в KNN.

***Локально линейная регрессия*** получается из локально константной подстановкой линейного прогноза $x^T\beta$ вместо $\hat{y}$.
Локальная линейная зависимость, в отличие от константной, умеет пролонгировать зависимости вверх (константная на краях пошла бы горизонтально), в разреженных местах тоже будет работать лучше. Но вычислительно этот метод сложнее, т.к. каждый раз надо будет перенастраивать веса.

### 5. Вывод оптимального коэффициента для линейной и гребневой регрессии. Предобработка признаков.

Еще одна возможная проблема -- наличие нелинейных зависимостей между признаками. Но ее можно решить, не выходя за рамки линейной модели, если применить к признакам нелинейное преобразование. В терминах новых признаках модель будет линейна, а в исходных -- нет. При этом, если преобразования несложные, частично удается сохранить интерпретируемость. Также сохраняется аналитическое решение и оно остается глобально лучшим.

***Гребневая регрессия*** -- линейная регрессия с $L_2$ регуляризацией.

### 6. Взвешенный учет наблюдений. Робастная регрессия. Регрессия опорных векторов, orthogonal matching pursuit.

Ошибки на объектах можно учитывать с разными весами. Это, в том числе, один из способов борьбы с выбросами.

***Робастная регрессия*** -- альтернативный способ строить устойчивые к выбросам модели (альтернатива выбору абсолютной функции потерь).
(на текущих весах получаем $\beta$ -> прогнозируем -> оцениваем ошибки -> для объектов с большой ошибкой занижаем веса, для объектов с большой -- повышаем -> на новых весах получаем $\beta$ -> ...)
Алгоритм обобщается на любой метод прогнозирования, не только линейную регрессию.

***Регрессия опорных векторов*** использует $\varepsilon$-нечувствительную ошибку, то есть не штрафует при величине ошибки в пределах $\varepsilon$, затем штраф растет линейно.

***Orthogonal matching pursuit*** решает задачу минимизации MSE при условии, число ненулевых весов не больше некоторого порога (то есть при ограничении сложности).
Метод:
(считаем ошибки прогнозирования -> выбираем максимально коррелирующий с ошибками признак (на первой итерации ошибки = откликам), добавляем его в модель -> перенастраиваем линейную регрессию на отобранных признаках -> считаем ошибки прогнозирования -> ...)

### 7. Направление локально максимального уменьшения функции. Метод градиентного и стохастического градиентного спуска. Экспоненциальное сглаживание. Обобщение инерции и инерции Нестерова.

***Градиент*** функции $f(x, y)$ по $x$ это вектор частных производных это функции по этой переменной. Вектор градиента указывает на направление максимального роста функции в данной точке -- докажем.

***Метод градиентного спуска*** заключается в том, что мы стартуем из какого-то начального приближения $x$, смотрим во все стороны, выбираем направление максимального уменьшения функции потерь (направление антиградиента), сдвигаемся туда и повторяем.
Проблема: сложность расчета градиента на каждом шаге $O(N)$ (т.к. это усредненный по всем объектам градиент ошибки на каждом объекте). Хочется это как-то оптимизировать. Кажется, что на начальных итерациях нам точность не очень важна, главное, сдвигаться в правильном направлении. Еще, если объектов много, они могут нести дублирующуюся информацию, и тогда можно было бы усреднять градиент не по всем объектам, а только по подвыборке. Таким образом мы упрощаем оценку эмпирического риска. Такие модификации приводят нас к ***стохастическому градиентному спуску (SGD)***.

Нужно следить, чтобы функция потерь уменьшалась. На практике все сильно колеблется и хочется для визуализации сгладить ряд значений оценки. Для этого подойдет экпоненциальное сглажвание.

При уменьшении параметра $K$ оценка градиента становится зашумленной. Если на каждом шаге мы усредняем градиент на разных $K$ объектах, то на текущем шаге мы можем усреднить несколько последних оценок и получить усреднение по нескольким подвыборкам, получив таким образом более надежную оценку. Это и является ключевой идеей метода SGD ***с инерцией***.

### 8. Регуляризация в линейных методах: L1 и L2 и ElasticNet. Влияние перемасштабирования отдельных признаков. Влияние L1 и L2 регуляризации на пересчет весов модели.

Мотивация: минимизируя ошибку, мы оцениваем качество на обучающей выборке. Но при этом модель может переобучиться под обучающую выборку, а на тесте очень плохо себя показать. Поэтому надо ввести ограничение на простоту модели и штрафовать ее за излишнюю сложность. Для этого в критерий оптимизации вводится дополнительный параметр -- регуляризатор, который тем выше, чем сложнее модель, и наоборот. Таким образом будем искать компромисс между точностью и простотой модели.
Чем выше $\lambda$, тем сильнее влияет регуляризация, и тем меньше получаются коэффициенты.
Отличие между регуляризациями в том, что $L_1$ позволяет занулять коэффициенты, таким образом модель избавляется от лишних признаков.

Если мы хотим, чтобы признак сильнее влиял на модель, берем $\alpha < 1$ (потому что тогда $\beta$ уменьшится и будет меньше попадать под регуляризацию). Если наоборот, уменьшить масштаб признака, то модель просто не сможет подобрать ему слишком большой коэффициент. Таким образом можно управлять вкладом признаков в прогноз.

Посмотрим, как регуляризации влияют на градиенты.

### 9. Линейный и линейный бинарный классификатор. Отступ (margin) для многоклассового случая и случая 2х классов. Оптимизационная задача по настройке весов бинарного классификатора. Основные функции потерь.


Рассмотрим геометрическую интерпретацию (если надо).
Таким образом, линейный бинарный классификатор линейной гиперплоскостью разделяет пространство на два полупространства, с одной стороны от которой положительный класс, а с другой - отрицательный. При этом значение дискриминантной функции пропорционально расстоянию до гиперплоскости. Знак отступа указывает, правильная классификация или нет.
Сложность построения прогноза линейным бинарным классификатором: $O(CD)$


### 10. Определение логистической регрессии через вероятности классов. Какой функции потерь она будет соответствовать? Многомерная логистическая регрессия. Функция soft-max.

Логистическая регрессия метод классификации, который может дополнительно предсказывать вероятность положительного класса. Линейный классификатор зависит от $w^Tx.$ Чем больше, тем более почтитетлен положительный класс и ничего не говорит о вероятности. Логрег дополнительно предполагает, что вероятность положительного класса связана с относительным рейтингом положительного класса через сигмоидную функцию. Принцип заключается в том, что мы переводим предсказания обычной линейной модели из **R в [0,1]** с помощью сигмоидной функции. Если лин классификатор дает значение 0, то сигмоида выдает 1/2, что логично, т е веростность положительного класса равновероятна с отрицательным.

Заметим что есть связь вероятности и относительной дискримнантной функции. Для этого используя свойство сигмоиды $\sigma(-x) = 1-\sigma(x)$ мы находим, что вероятность $y$ при условии $x$ это сигмоида от скалярного произведения $w$ на $x$.
Знаем как оценивать вероятность. Не знаем параметр $w$. Т к не знаем параметр, в статистике выбираем параметр так чтобы максимизировать правдоподобие, то будем максимизровать условное правдоподобие. x фиксированные, y предсказываем. Т к объекты независимы, то факторизуется вероятность в произведения вероятностей для каждого объекта.

Подставляем сигмоиду, берем за основу свойство что аргмин функции равен аргмину композиции монотонной функции и исходной функции. в качестве понотонной функции берем логарифм. Теперь минимизируем **логистическую функцию потерь**.
Проучается, свели задачу к минимизации эмпирического риска для логистической функции потерь.

#### Многоклассовый логрег

Есть задача многоклассовой классификации, Нужны вероятности, т е функция перевода отклика по какому то классу в вероятность $g(x) \rightarrow P$.
Возьмем экспоненту от отклика($w_1^Tx$), чтобы сделать положительным значение. Нужно чтобы отклики суммировались в 1, для этого нормируем на сумму всех экспонент от откликов. Т о мы использовали softmax преобразование
Контрастность вероятностей -- управляет степенью контрастности выходных вероятностей(для более контрастных вероятностей уменьшаем коэффициент тау, т к в пределе тау получаем равномерное распределение).

> тут хз нужно это или нет

### 11. Обобщение бинарных классификаторов на многоклассовые - методы один против всех, один против одного и основанный на кодах, исправляющих ошибки.

Один против всех -- после проведения трех ганиц в треугольнике в центре может быть неоднозначность (там на помощь приходят отступы). Получается $C$ бинарных классификаторов.
Один против одного -- мб 1 лучше 2, 2 лучше 3, 1 хуже 3. Тут тоже придется отступы использовать. Получается $C(C-1)/2$ бинарных классификаторов (но при этом они настраиваются не на всей выборке, а на подмножествах, поэтому это не обязательно медленнее).
Коды. Каждый класс кодируем бинарным вектором, в итоге получаем матрицу из 0 и 1. Тогда, если у нас $B$ измерений (длина закодированного вектора), достаточно обучить $B$ бинарных классификаторов предсказывать бит соответствующего столбца. Применяем классификаторы к $X$, получаем $B$ бинарных прогнозов -- бинарный код. Выигрывает класс, чье закодированное представление наиболее похоже на получившийся код.
Можно повысить точность такого подхода, если кодировать кодами, исправляющими ошибки -- они используют избыточное количество бит, чтобы можно было корректно передавать информацию даже с шумами. Также используются другие эвристики (на скрине)

### 12. Метод опорных векторов в линейно разделимом и линейно неразделимом случае. Его геометрическое обоснование. Какой оптимизационной задаче (достаточно только прямой задачи, не двойственной)? Классификация типов объектов в методе опорных векторов.


Наилучший вариант с максимальным расстоянием элементов выборки до разделяющий плоскости является верным так как рядом с элементами выборки в тесте могут появиться новые примеры.

положительный класс ограничен прямой $x^Tw +w_0=b$
отрицательный $x^Tw +w_0=-b$, посередине наша разделяющая прямая $x^Tw +w_0=0$, тогда нам нужно максимизировать расстояние между верхней и нижней прямой. Причем расстояние от точки до находим как $$\rho(x,H) = \frac{x^Tw +w_0}{||w||}$$.
Получаем что расстояние между двумя прямыми равно $$\rho(H_1,H_2) = \frac{b - (-b)}{||w||} =\frac{2b}{||w||}$$
Получаем систему, из которой, можно понять интуитивное понимание оптимизационной задачи (для бинарного классфикатора), хотим чтобы объекты классифицировались так, чтобы отступ был >=1 (т е более уверенно), и среди всех решений, находим наиболее простую модель, для этого минимизурем $L_2$ норму.

Все объекты можно разделить на 2 категории:

**Неинформативные объекты** -- классифицирующиеся с высоким отступом объекты не влияют на ограничение множества решений, полученное решение после включения никак не изменится.

Опорные вектора(опорные объекты) -- ограничивают пространство выбора для $w,w_0$, определяют наше решение, лежат на расстоянии от гиперплоскости равном $\frac{1}{||w||}$



Бывает что у нас объекты находятся так что нельзя линейно явно разделить, поэтому разрешаем некторым объектам на кси выходить дальше границы.
При решении оптимизационной задачи минимазация в первом выражении $w^Tw$ контроллирует сложность модели, а минимазация $C\sum_i\xi_i$ контроллирует точность, кол-во ошибок, С имеет смысл коэффициента регуляризации.


Здесь добавляютя **объекты нарушители**. Если они будут переходить пограничную (отступ=1) черту и отступ для них в интервале (0;1) то они все еще будут корректно классфицироваться. Если они перейдут разделяющую гиперплосскость т е < 0, то будут некорректно классфицироваться.

Получается, метод опорных векторов это метод линейной бинарной классификации, когда мы находим веса, минимизируя функцию потерь Хинча и используя $L_2$-регуляризацию.

>это не нужно но на всякий двойственная задача через ККТ и ее решение)))

### 13. Обобщение методов машинного обучения через ядра. Теорема Мерсера. Операции, не выводящие из класса ядер. Линейное, полиномиальное и RBF ядро.
>cм билет выше если непонятно

>Отступ это зазор, с которым побеждает корректный класс.
>Если С классов то каждому классу соответсвует своя дискриминантная функция. Хочется чтобы корректный класс в многоклассовом случае побеждал с зазором больше 1 некорректный отклик

>Вычислительно более дорогой, чем решать, чем решать С раз задачу бинарной классфикации (методом один против всех или один против одного). В бин классификации надо найти $w,w_0$ d+1 параметр, в один против всех (d+1) параметров C раз, т е (d+1)С параметров. В SVM сразу для (d+1)С параметров оптимизационная задача, что вычислительно сложнее. Но иногда работает намного лучше.
>

>#### НЕ Дописал

Kernel trick
Функция ядра -- ф-я, которая соответствует скалярному произведению некоторого преобразования признаков.
Трюк с ядрами используется, когда
* исходные признаки не могут описать необходимую зависимость
* скалярное произведение преобразованных признаков сложно считать, а ядро вычисляется просто (когда $\phi(x)$ имеет большую степень (полином или rbf))
* есть естественная мера скалярного произведения в объектах сложной природы (строки, графы, картинки) -- не хотелось бы эти объекты кодировать в векторы, просто задаем функцию ядра для сравнения объектов и все
***Полиномиальное ядро***: $K(x, z) = (\alpha \langle x,z \rangle + \beta) ^ k$

Второе условие очень сложное. Но есть функции, про которые мы точно знаем, что они ядра + преобразования, не выводящие из класса ядер

### 14. Оценка классификаторов. Матрица ошибок. Точность, полнота (с обобщением на многоклассовый случай), F-мера. ROC-кривая, мера AUC.


Точность -- какая доля релевантных объектов среди предск. положительных. Полнота -- доля покрытых положительных объектов. F-мера (среднее гармоническое) учитывает выраженные случаи (не дает сильно занижать одну из метрик). Взвешенная F-мера нужна, если нам какая-то из метрик важнее.
TPR - с какой вероятностью мы положит. объект отнесем к положит. классу. FPR - с какой вероятностью мы отриц. объект отнесем к положительному.

Это мы оценивали предсказание меток классов, но предсказание вероятностей тоже хочется оценивать.
Условное правдоподобие -- насколько правдоподобно наше предсказание при такой выборке. Оценка Бриера -- насколько отклоняется вектор предсказанных вероятностей от фактических вероятностей.

Насколько хорошо наш объект ранжирует объекты по $g(x)$? Для этого нужны ROC, AUC.
Иногда мы больше хотим предсказывать один класс, иногда другой. Тогда надо ввести параметр, контролирующий предпочтение между классами -- некоторый трешхолд, исходя из которого мы будем выбирать класс, не переобучивая модель.
Площадь под кривой можно использовать, если мы знаем стоимость ошибок и можем выбирать интересующую нас область на графике.

### 15. Эквивалентность площади под ROC кривой доле корректно упорядоченных пар объектов. Методы калибровки вероятностей. Меры оценки качества предсказания вероятностей.

Упорядочиваем объекты по рейтингу. $g(x)$ сравниваем с разными $g(x_k) = \alpha$, таким образом перебирая все случаи. Считаем $TPR$ (в числителе все, что мы отнесем к положит. классу из хвоста -- того, что выше текущего $\alpha$) и $FPR$ на $k$-м шаге. Считаем площадь под кривой по формуле трапеции на участках от $k$ до $k+1$. Двойная сумма, которая там получается, это количество верно упорядоченных пар (т.к. объект с меньшим индексом равен -1, а с большим равен +1).

Предсказание вероятностей тоже хочется оценивать.
Условное правдоподобие -- насколько правдоподобно наше предсказание при такой выборке. Оценка Бриера -- насколько отклоняется вектор предсказанных вероятностей от фактических вероятностей.

Если наш классификатор хорошо предсказывает метки, можем научить его предсказывать вероятность. Для этого пропускаем дискр. функцию через $f(x)$, которая переведет его в $[0, 1]$. Для поиска подходящей функции существуют графики калибровки. Ось x -- $g(x)$ (соответствующие объекты), ось y -- доля объектов положит. класса среди выбранных. Максимально хорошо предсказываются вероятности на прямой $y = x$.
Как находить нужную функцию? Вот варианты.
Изотоническая регрессия позволяет получить монотонно неубывающую кривую. Мы апроксимируем $y$ кусочно-постоянной функцией, которая неубывает с ростом $x$.

### 16. Определение решающего дерева CART. Выбор решающего правила в каждом узле для случая классификации/регрессии, назначение прогнозов узлам дерева в случае регрессии/классификации, симметричных/несимметричных потерь.

Правильная система прогнозирования вырабатывает систему правил, при соответствии которым объект будет относиться к опр.классу. Решающее дерево строит такие правила.
$K_t$ -- кол во потомков в узле t
$Q_t(x)$ -- функция, область значений которой делим на K_t непересекающихся множества (S_t(1) ... S_t(K_t)) и по которой определяем в како множество попадаем.
**Правила ветвления:**
- Ветвление **по уникальному признаку**, не применим к вещественным признакам. Т е берем какой то признак (пол) и делим по уникальным значениям (М,Ж)
- **По трешхолду**
- **По набору трешхолдов**
- Можно смотреть
- ветвление по вычислению скалярноего произведения всего вектора x на некий вектор
- по норме и т д

CART самый популярный типдеревьев -- ветвление на только два потомка.

Преимущества: Работает на разных типах признаков. Прогноз инвариантен к монотонным преобразованиям признака.

Недостаток:Плохо экстраполирует данные, наклонные границы требуют большую глубину

Настраиваем решающее дерево:
для каждый вершины

>есть еще с прошлого года

### 17. Определение решающего дерева CART. Правиловые критерии остановки наращивания дерева. Понятие обрезки (pruning) для решающих деревьев. Важность признаков в решающем дереве.

Алгоритм обрезки CART. Мы для каждой вершины сравниваем -- что произойдет, если мы будем прогнозировать только этой вершиной или всем поддеревом. Приравниваем штраф за вершину к штрафу за поддерево и находим равновесную $\alpha$. Если $\alpha$ получилась равная 0, то нам неважно, оставлять дерево или вершину. А если альфа высокая, получается поддерево настолько точное получилось, что нам надо сильно штрафовать модель за сложность, а значит, стоит заменить вершину на поддерево.

>это мб не надо

Деревья позволяют считать важность признаков. Для каждой вершины можем посмотреть изменение неопределенности после разбиения. Суммируем по всем вершинам, которые используют этот признак, изменение неопределенности, умнож. на кол-во объектов, которые проходят через вершину. Эта сумма определяет значимость признака.
Еще можно перемешать значения признака и посмотреть на валидации, потеряли ли мы что-то от такого.

### 18. Разложение на смещение и разброс(bias-variance decomposition).Разложение неоднозначности(ambiguity decomposition). Интерпретация компонент и вывод.

Считаем среднекв. откл-е прогноза от реального значения (усредняя по $\varepsilon$ и всевозможным обучающим выборкам), получаем bias (среднее значение прогноза при усреднении по всевозможным прогностическим моделям по всевозможным обучающим выборкам), variance (квадрат отклонения частной реализации прогностической модели для фикс. выборки от средней реализации прог. модели на всевозм. выборках, усредненный по всем выборкам) и шума.


***Ambuguity decomposition*** -- разложение, которое показывает, насколько выгодно использовать ансамбли. Р-м задачу регрессии, в которой мы усредняем прогнозы $M$ моделей с весами $w_m$, наш прогноз это будет $G(x)$. Зафиксируем $(x, y)$. Тогда квадрат ошибки ансамбля разложится на две компоненты. Первая -- взвешенная сумма квадратов ошибок каждой базовой модели (***base learner error***). Вторая, неотрицательная, позволяющая компенсировать ошибки базовых моделей -- неоднозначность (***ambuguity***). Это взвешенная сумма квадратов отклонений предсказаний каждой базовой модели от предсказания ансамбля. Эта компонента имеет смысл рассогласованности прогнозов ансамбля. Она будет большой, когда модели для одного и того же $x$ строят сильно разные прогнозы. То есть ансамблю выгодно комбинировать сильно не согласующиеся модели.

### 19. Фиксированные схемы агрегации классификаторов, выдающих метки, рейтинги и вероятности классов. Стэкинг, бэггинг, метод случайных подпространств.

Рассмотрим стратегии для борьбы с переобучением.
Взвешенное усреднение в случае регрессии. Веса при этом надо настраивать на валидационной выборке.
В классификации есть три случая.
В случае рейтингов они могут быть несравнимы (находиться в разных диапазонах), поэтому надо их приводить к одной шкале с помощью Brier scores:
$s^m_y$ это количество классов, которые отранжированы ниже, чем текущий класс $y$

Стэкинг позволяет бороться и с переобученностью, и с недообученностью -- смотря какую агр. ф-ю выберем.

Рассмотрим композиции на разных обучающих подвыборках для борьбы с переобучением. Усреднение по выборкам не меняет смещение, но уменьшает разброс.
>доказательство, наверное не нужно

Рассмотрим алгоритмы, основанные на данном методе. Поскольку выборка нам дана одна, будем генерировать бутстраповские подвыборки (из случайных объектов исходной выборки) и настраивать наши модели (из какого-то заранее выбранного семейства) на этих подвыборках, после чего будем усреднять прогноз по этим моделям.

### 20. Методы случайного леса (RandomForest) и особо случайных деревьев (ExtraRandomTrees). Вневыборочная оценка (out-of-bag) оценка.

Формализуем, как устроен процесс оптимизации узла в каждом дереве.
$I(t)$ -- степень неопределенности в узле t. При настройке решающего правила мы выбирали признак и границу для него путем максимизации изменения степени неопределенности в узле (неопр-сть хотим уменьшить).

RandomForest и ExtraRandomTrees это две модификации бэгинга над случайными деревьями (с использованием метода случайных подпространств).
В **RandomForest** на этапе настройки базового алгоритма вносится некоторая рандомизация: когда выбираем признак для решающего правила в узле, мы выбираем его из *случайного подножества* признаков. Таким образом в узле производится лишь частичная оптимизация. В итоге мы ограничиваем гибкость дерева, уменьшая разброс ценой смещения.
Случайный лес можно применять как в композиции с бэггингом, так и на одной выборке.

В **ExtraRandomTrees** при настройке решающего правила мы перебираем признаки из некоторого случайного подмножества и при этом границу $h$ тоже случайно сэмплируем из множества значений признаков. В итоге мы тоже ограничиваем гибкость дерева, уменьшая разброс ценой смещения.

Степень размена разброса на смещение можно варьировать, меняя объем выборки, из которой сэмплируем (параметр $\alpha$). Альфа близкое к 1 это максимально гибкая модель, к 0 -- максимально урезанная.

После обучения модели с помощью бэггинга мы можем для каждого объекта из выборки получить усреднённое предсказание тех алгоритмов, в обучающую подвыборку которых этот объект не попал. Получив подобное предсказание для каждого объекта можно посчитать метрику качества, которая будет как-то оценивать финальное качество модели. Такой подход называется ***Out-of-bag estimation***. Он помогает оценить модель без валидационной выборки.

### 21. Алгоритм бустинга. Алгоритм AdaBoost - без вывода. Использование shrinkage и subsampling.

В бустинге применяется линейный ансамбль. Есть начальный алгоритм, дальше каждая последующая модель последовательно улучшает предыдущую модель. Настраиваем каждую последующую модель с неким коэффициентом. $F_M(x)$ -- относительная дискириминантная функция. Итеративно настравиаем каждую последующую модель и улучшаем качество $F_M(x)$

- обучаем $f_0$ минимизируя ошибку
- дальше обучаем новый алгоритм так, чтобы он давал новую поправку на функцию ошибки так, чтобы композиция моделей давала минимальный лосс, учитываем новую модель с коэффицинтом, который вычисляем при обучении


**Adaboost**
- рассматривается задача бинарной классификации
- каждая базовая модель возвращает метку класса (+1, -1)
- можно обучать на взвешенной выборке (объекты учитываются с весами)
- решаем классификацию по ансамблю (представляем в виде взвешенной суммы базовые модели и берем знак от суммы откликов моделей)
- в качестве убывающей функции для ф-ии потерь берем убывающую экспоненту (для нелинейности)


- сначала веса для каждого объекта берется равномерно
- для каждого базового алгоритма итеративно настраиваем параметры алгоритма и коэффициент при нем
- обучаем на той же самой обучающей выборке, но меняются веса объектов
- смотрим на взвешенную частоту ошибок (суммируем с весами количество несовпадений базового алгоритма и нормируем на сумму весов)
-если частота ошибок $E_m$> 1/2 то досрочно выходим из цикла(можно не делать, можем инвертировать классификатор), и если $E_m = 0$ заканчиваем (нет смысла дальше обучаться)
- $c_m$ коэффицент учета алгоритма алгоритма будет > 0 (исходя из того что $E_m < 0.5$)
- обновляем веса у тех объектов, на которых совершена ошибка (увеличиваем на коэффициент $e^{2c_m}$)

Т е там где все плохо бы говорим модели учитывать эти объекты с большим весом, чтобы лучше под них обучаться, все остальные веса не трогаем

>
>
> нужно проминимизировать величину полученную ниже, вклад в минимизацию дает только правая сумма
>
>
>

### 22. Алгоритм градиентного бустинга. Его обоснование для разложения потерь 1го и 2го порядка.

Вспомним градиентный спуск:
- Стандартный град спуск
- Град спуск с настраиваемым шагом (вычисляем градиент, при этом смещаемся на коэффициент, который мы постоянно на каждом шаге вычисляем, те берем всевозможные положительные смещения и смотреть на минимизацию ошибки)

$F(.)$ -- модель

1е приближение

### 23. Задача снижения размерности. Подпространства наилучшей аппроксимации - 2 определения (через проекции и отклонения), их эквивалентность. Связь с методом главных компонент. Оценка разброса распределения по матрице ковариации.

Немного о скалярном произведении
Собственные векторы и собственные значения
Симметричные матрицы
Спектральное разложение
Неотрицательная определенность

Некоторые обозначения
Оценим разброс распределения по матрице ковариаций.
Т.к. матрица ковариаций неотр. опр., сущ. сингулярное разложение -- раскладываем. Хотим вращать единичный вектор $\alpha$ и смотреть, какая будет дисперсия у величины $\alpha ^T x$. Расписали дисперсию, используя спектральное разложение, и получили квадрат нормы. Это значит, что мы переводим альфу в ОНБ, образованный собственными векторами $\Sigma$ и умножаем на $\Lambda^{1/2}$.
Способы посчитать величину разброса:

***Задача снижения размерности***
Если у нас много признаков, то некоторые могут коррелировать друг с другом, некоторые вообще будут зависимыми, также методы будут считаться медленно, дорого хранить множество данных, модель сложно интерпретировать -- куча проблем. Хочется уменьшить число признаков, либо отбирая важные, либо снижая размерность (применяя некоторую функцию к признакам, которая извлекает из них информацию).

Как можно проводить снижение размерности:
- с учителем -- стараемся минимально потерять в качестве прогнозов
- без учителя -- просто из каких-то общих соображений снижаем размерность

Для введения подпространства наилучшей аппроксимации нужны некоторые определения.
Подпространство наилучшей аппроксимации -- некоторое $K$-мерное подпространство, которое в нек. смысле будет наилучшим образом приближать наши данные после проецирования на данное подпространство. В качестве величины ошибки аппроксимации можно рассматривать сумму квадратов отклонений проекций от исходных иксов. В качестве оценки качества аппроксимации можно рассматривать сумму квадратов длин проекций.

Докажем, что эти определения эквивалентны. Разложим $x_n = p_n + h_n$. Распишем скалярный квадрат $x_n$ и просуммируем по всем $n$. Поскольку выборка фиксированная, то слева получается константа, а значит суммы квадратов длин проекций и ортог. дополнений меняются одновременно, причем если минимизируется одно, то максимизируется другое, и наоборот.

Связь с методом главных компонент заключается в том, что ОНБ в подпр-ве наилучшей аппроксимации это и есть главные компоненты.

### 24. Метод главных компонент - итеративный алгоритм их построения, решение. Доказательство, что главные компоненты образуют подпространство наилучшей аппроксимации.

**Итеративный алгоритм.**
- ищем подпр-во наилучшей аппр. размерности 1 -- его базисный вектор это и ей 1-я компонента
- фиксируем первый вектор, тогда 2-я компонента -- второй базисный вектор, который нужен для подпр-ва наил. аппр. размерности 2 и т.д.

**Решение метода главных компонент.**
- Центрируем наши признаки, чтобы они обладали нулевым средним
- Шкалируем признаки, чтобы они обладали одинак. дисперсией
- Формируем матрицу объекты-признаки $X$
- Вычисляем эмпирическую ковариационную матрицу
- Упорядочим собств. значения матрицы $\hat \Sigma$ по убывынию и найдем соотв. собств. векторы
- Первые k собств. векторов будут первыми k главными компонентами
- Величина качества (сколько информаци содержит каждая главная компонента) $E(a_i)$ определяется собств. значениями
Зная гл. компоненты, мы знаем подпр-во наилучшей аппроксимации любого порядка и проецируем туда наши данные, и $x -> (p_1, ..., p_k), K < D$.

**Построение главных компонент.**
- первую компоненту ищем, максимизируя сумму квадратов длин проекций на эту компоненту при условии, что ее норма = 1
- вторую ищем так же, но при условии, что она ортогональна первой
- т.д.

**Доказательство, что главные компоненты образуют подпространство наилучшей аппроксимации.**
Для доказательства для $K=1$ распишем, что $Xa_1$ это вектор, элементы которого это координаты проекций объектов на $a_1$, то есть скалярные произведения. Получается, максимизируя квадрат нормы $Xa_1$, мы максимизируем сумму квадратов проекций на него, тогда по определению вектор $a_1$ будет задавать подпр-во наилучш. аппр. размерности 1. Дальше по индукции

### 25. Оценка качества аппроксимации отдельной главной компонентой и первыми K компонентами в методе главных компонент. Нахождение по объекту его проекции на подпространство лучшей аппроксимации.

$h^K$ показывает ошибку аппроксимации.
Мы можем оценить, как хорошо первые K компонент описывают наши данные с помощью относительной ошибки $L(K)$ и относительного качества $S(K)$.
Аналогичные критерии мы можем посчитать для каждой отдельной главной компоненты. Компонента важна, если проекции на нее получаются большие. Предлагается смотреть на сумму квадратов длин каждого объекта на соотв. главную компоненту. Эту величину нормируем на сумму квадратов длин объектов исходной выборки и получаем $E(a_k)$, которая будет показывать важность компоненты.

>этого не было в лекции
Нахождение по объекту его проекции на подпространство лучшей аппроксимации.

### 26. Расчет важности признаков. Методы расчета важности признаков, основанные на обычной корреляции, корреляции Спирмена и Кендалла, а также с помощью взаимной информации. Расстояние Кульбака-Лейблера.


**Расчет важности признаков.**
Оценим значимость каждого признака, а далее можем либо отбирать признаки по значимости, либо учитывать признаки в разной степени в отличие от их значимости. Отбирать признаки по значимости можно просто какой-то топ $m$ штук, либо по порогу значимости, либо выбирать лучший набор из всех комбинаций признаков. Это легко реализовать, но при этом будет включено много слабо релевантных зависимых признаков.

Рассмотрим внешние оценки значимости признаков.
**Корреляция.**
$f$ - признак, $f_i$ - признак на i-м объекте, $y$ - отклик, $y_i$ - отклик на i-и объекте. Вычисляем выборочную корреляцию по определению. В многоклассовом случае применяем one-hot кодирование для $y$ и вычисляем корреляцию признака с каждым бинарным столбцом. Дальше можно делать макро-усреднение, микро-усреднение или брать максимум.

**Корреляция Спирмена.**
Заменим значения признаков и откликов на их ранги (порядковые номера в отсортированном виде). Ранговое кодирование позволяет выделить монотонную взаимосвязь.

**Корреляция Кендалла.**

**Через взаимную информацию.**
Расстояние Кульбака-Лейблера позволяет определить, насколько два распределения непохожи друг на друга. Если оно равно 0, то распрделения равны, елси > 0, то есть отличия.

Взаимная информация это расстояние Кульбака-Лейблера между распределением истинных пар $(x, y)$ и распределением на парах. Если гипотеза $H_0:$ $X$ и $Y$ независимы, тогда распределения будут равны. Взаимная информация измеряет степень отклонения от $H_0$.

### 27. Методы расчета важности признаков, основанные на relief-критерии, решающих деревьях и используя permutation feature importance.

Самый простой способ посчитать важность признака это настроить решающее дерево или их композицию и по нему определить важность функцией из sklearn.
Возьмем признак f и рассмотрим вершину, в которой этот признак фигурирует. Признак важен, если в вершине t сильное изменение неопределенности (умножаем на число объектов, прошедших через эту вершину).

permutation feature importance работает на всех моделях, не только на деревьях.

relief-критерий -- метрический метод оценки взаимосвязи признака и отклика. Применим только для классификации. Он судит о значимости признака по тому, насколько сильно он меняется вдоль оси при изменении класса.
Будем считать значимость среди ближайших соседей.

### 28. Алгоритм последовательного включения в отоборе признаков и его модификации. Лучевой поиск (beam search).

Признаки могут терять и иметь актуальность только в контексте других признаков, поэтому нужны еще методы, учитывающие значимость в контексте.


Хотим отобрать K наиболее хороших признаков.
$F$ - все признаки, $S$ - лучшие отобранные. Находим признак, максимизирующий критерий качества вместе с уже добавленными.

Жадный поиск в дереве решений
Оптимальный набор при этом мог содержать другие признаки.

### 29. Алгоритм генетического отбора признаков.

Генетический алгоритм позволяет делать более полный перебор признаков. В основе генетического алгоритма лежит гипотеза базовых блоков: если мы нашли какие-то хорошие базовые решения, то оптимальное решение скорее всего будет композицией из хороших базовых решений.

Используются бинарные вектора $b$, которые характеризуют, какой признак берем, а какой нет. Комбинации для получения хороших решений -- скрещивание и мутация.
Мутация: сэмплируем случайную позицию и инвертируем бит.
Скрещивание по ед. точке разрыва: сэмплируем точку разрыва, меняем местами разрезанные части между двумя решениями.
Равномерное скрещиваение: на каждую позицию равновероятно выбираем элемент из двух решений.

### 30. Сингулярное разложение и его сокращенная версия (truncated SVD), его оптимальность. Выбор ранга аппроксимации. Связь с методом главных компонент. Применения.

Часто имеем дело с большими матрицами маленького ранга, и SVD позволяет компактно представить такую матрицу.
Сингулярные числа показывают значимость строки/столбца для восстановелния матрицы.