-- Общий вид $a(x) = sign(f(x))$, где $f(x)$- дискриминантная функция. При $a(x) = sign(<w, x> + w_0)$, $f(x) = <w,x> + w_0$ - линейная.
-- Отступ на объекте -- величина $M_i = y_i \cdot f(x_i)$. При $a(x_i) \neq y_i \Leftrightarrow M_i \leq 0$
-- Добавляют $x_0 = 1$ к вектору $x$, как еще одну координату, к вектору весов соответственно $w_0$.
--$Q(a, X^l) = \frac{1}{l}\cdot \sum_{i=1}^{n}[a(x_i) \neq y_i] = \frac{1}{l} \cdot \sum_{i=1}^{n}[M_i \leq 0]$ , равен $0$ для наилучшего алгоритма классификации (все точки классифицированы правильно, т.е. каждый отстут отрицательный).
--$w=0$
--$Q(a, X^l) = \frac{1}{l}\cdot \sum_{i=1}^{l}L(M)$
--Функция потерь $L(a, x)$ = величине ошибки алгоритма $a$ на объекте $x$. L - неотрицательна, для линейной классификации - ($L(M)$) - невозрастающая. Обычно выпукла, для хорошего решения оптимизации.
--$L(M) = [M\leq 0]$ - функция Хевисайда - пороговая функция потерь.
-- Регуляризатор - величина штрафа за сложность модели. Позволяет бороться с переобучением, не давая модели быть слишком сложной( например высокая степень полинома в задаче интерполяции). В случае линейных моделей при переобучение наблюдаются большие веса, поэтому регуляризатор - штраф за большие веса, ограничивает дискриминантную функцию. Примеры: $$l_0-регуляризатор -- \lambda \cdot \sum_{i=1}^{n}[w_i \neq 0]$$ $$l_1-регуляризатор -- \lambda \cdot \sum_{i=1}^{n} \mid w_i \mid$$, $$l_2-регуляризатор -- \lambda \cdot \sum_{i=1}^{n} w_i^2$$
--Обобщающая способность алгоритма $a$ = $Q(a(X^l), X^k)$, $X^l, X^k$ - непересекающиеся выборки. При переобучении это значение будет большим (возможно из-за увеличения одного из весов). Регуляризация борется с переобучением, а значит и ограничивает значение этого функционала.
--Выход из минимума приводит к сильному возрастанию функционала аппроксимированного эмпирического риска, что приводит к большому весу и переобучению.
--Увеличивает при приближении параметров алгоритма к недопустимым границам.
--С регуляризацией, так как она увеличивает значение функционала риска.
-- Бывает по-разному. Если без регуляризации алгоритм сильно переобучался, то и на тестовой выборке даст плохие результаты и большое значение функицонала риска. С другой стороны, если переобучение без регуляризации не превосходит вес от регуляризации, то может быть большой значение с регуляризацией.
-- Допустим метки классов +1 и -1.
TP - True Positive - предсказан +1, правильно +1,
FN - False Negative - предсказан -1, правильно +1,
TN - True Negative - предсказан -1, правильно -1,
FP - False Positive - предсказан +1, правильно -1
P - Positive = размер класса +1,
N - Negative = размер класса -1
Тогда $$Accuracy = \frac{TP+TN}{P+N}$$ - доля правильных ответов $$Precision = \frac{TP}{TP+FP}$$ - точность - сколько из предсказанно правильно $$Recall = \frac{TP}{P}$$ - полнота - сколько из правильных предсказали
--$$False Positive Rate = FPR = \frac{FP}{N}$$ $$True Positive Rate = TPR = \frac{TP}{P}$$. ROC-кривая - график зависимости TPR(FPR). ROC-AUC - метрика качества - площадь под ROC-кривой.
--По ответам получим множество точек $\{(FPR_i, TPR_i)\}_{i=0}^{l}$, по которой строится ROC-кривая.
1) (FPR_0, TPR_0) = (0, 0)
2) P - число фамилий в выборке, N - не фамилий
3) Отсортием выборку по значениям f(x_i)
4) for i in range(1, l):
5) if y_i == 1:
6) (FPR_i, TPR_i) = (FPR_{i-1}, TPR_{i-1} + 1/P)
7) else:
8) (FPR_i, TPR_i) = (FPR_{i-1} + 1/N, TPR_{i-1})--Решение
Допустим, множество $X\times Y$ является вероятностным пространством, и заданы плотности распределения объектов и классов $p(x, y|w)$. Введем параметрическое семейство априорных распределений $p(w; \gamma)$, где $\gamma$ — параметр. Логарифм функции правдоподобия: $$L_{\gamma}(X^l, w) = \ln p(X^l, w; \gamma) = \sum_{i=1}^{l} p(x_i, y_i | w) + \ln p(w; \gamma) \rightarrow max$$ Ищем максимум этой функции. Последнее слагаемое представляет собой регуляризатор. Так как принцип максимального праводопобия эквивалентен принципу минимизации аппроксимированного эмпирического риска $$ Q(X^l, w) = \sum_{i=1}^{l} L(y_i \cdot f(x_i, w)) + \gamma \cdot V(w) \rightarrow min$$
Сопоставляя принципы и формулы получаем $$-\ln p(x_i, y_i|w) = L(y_i \cdot f(x_i, w))$$ $$\ln p(w;\gamma) = \gamma \cdot V(w)$$
Таким образом, получаем, что регуляризатор $V(w)$ соответствует параметрическому семейству априорных распределений плотностей $p(w; \gamma)$ — параметров моделей.
Для $l_1$-регуляризатора Пусть $w \in R$ имеет $n$-мерное распределение Лапласа: $$p(w; C) = \frac{1}{(2C)^n} e^{-\frac{\|w\|_1}{C}}, \|w\|_1 = \sum_{i=1}^{n} |w_j|$$
т.е. все веса независимы, имеют нулевое матожидание и равные дисперсии; C — гиперпараметр. Логарифмируя, получаем регуляризатор по $l_1$ -норме: $$-\ln p(w; C) = \frac{1}{C} \sum_{i=1}^{n} |w_j| + const(w) $$
Для $l_2$-регуляризаторa Пусть $w \in R$ имеет $n$-мерное гауссовское распределение: $$ p(w; \sigma) = \frac{1}{(2 \pi \sigma)^\frac{n}{2}} e^{-\frac{\|w\|^2}{2\sigma^2}}, \|w\|^2 = \sum_{i=1}^{n} w_i^2$$
т.е. все веса независимы, имеют нулевое матожидание и равные дисперсии $\sigma$; $\sigma$ — гиперпараметр. Логарифмируя, получаем регуляризатор по $l_2$ -норме: $$−\ln p(w; \sigma) = \frac{1}{2\sigma^2} \|w\|^2 + const(w)$$
--Решение
Рассмотрим задачу классификации на два непересекающихся класса, в которой объекты опи- сываются $n$-мерными вещественными векторами: $X \in R^n, Y = \{−1, +1\}$. Будем строить линейный пороговый классификатор: $$a(x) = sign(<w, x> - w_0)$$
Для начала предположим, что выборка линейна разделима: найдутся $w$, $w_0$ , задающие разде- ляющую гиперплоскость $⟨w, x⟩ = w_0$ , при которых функционал числа ошибок $$Q(w, w_0) = \sum_{i=1}^{l} [y_i \cdot (⟨w, x_i⟩ − w_0 ) \leq 0] = 0 $$ Найдем, как оптимальнее расположить разделяющую гиперплоскость. Для простоты выполним нормировку параметров алгоритма: домножим $w$ и $w_0$ на такую константу, что $$min (y_i \cdot (⟨w, x_i⟩ − w_0)) = 1, i \in \overline{1, l}$$ Хочется максимизировать ширину разделяющей полосы. Тогда на границе разделяющей поло- сы будут лежать точки из обучающей выборки: $x_{−},x_{+}$ , принадлежащие соответственно классам -1, +1. Ширина полосы $$ \left< (x_{+} - x_{-}), \frac{w}{\|w\|} \right> = \frac{<w, x_{+}> - <w, x_{-}>}{\|w\|} = \frac{(w_0+1)-(w_0-1)}{\|w\|} = \frac{2}{\|w\|}$$, тут мы использовали условие минимума.
Получаем, что ширина полосы максимальна, когда норма вектора w минимальна. Значит, мож- но сформулировать следующую задачу оптимизации: \begin{equation*} \begin{cases} & \frac{1}{2}\cdot \|w\|^2 \rightarrow min \\ & y_i \cdot (<w, x_i> - w_0) \geq 1, i \in \overline{1, l} \end{cases} \end{equation*}
Если работать с линейно неразделимой выборкой, $y_i \cdot (⟨w, x_i⟩ − w_0)$ не обязательно будет не меньше 1. Ослабим эти ограничения и введем в минимизируемый функционал штраф за суммарную ошибку: \begin{equation*} \begin{cases} & \frac{1}{2}\cdot \|w\|^2 + C \sum_{i=1}^{l} \xi_i \rightarrow min \\ & M_i = y_i \cdot (<w, x_i> - w_0) \geq 1 - \xi_i, i \in \overline{1, l} \\ & \xi_i \geq 0 \end{cases} \end{equation*} Где $\xi_i$ - величина ошибки на $x_i$ Из 2 и 3 условий: \begin{equation*} \begin{cases} & \xi_i \geq 1 - M_i\\ & \xi_i \geq 0 \end{cases} \end{equation*} Тогда $\xi_i$ минимальна при $\xi_i = (1 - M_i)_{+}$
Исходная задача тогда имеет вид: $$\frac{1}{2}\cdot \|w\|^2 + C\cdot \sum_{i=1}^{n}(1-M_i)_{+} \rightarrow min$$
--Решение
Возьмем квадратичное ядро: $$K(x, y) = ⟨x, y⟩^2 = (x_1 \cdot y_1 + x_2 \cdot y_2)^2 = x_1^2 \cdot y_1^2 + 2 x_1 y_1 x_2 y_2 + x_2^2 \cdot y_2^2 = ⟨(x_1^2, x_2^2, \sqrt{2}x_1 x_2), (y_1^2, y_2^2, \sqrt{2}y_1 y_2)⟩$$ Получим отображение в спрямляющее пространство $H = R^3$: $$ \psi(x_1, x_2) \rightarrow (x_1^2, x_2^2, \sqrt{2}x_1 x_2)$$ Тогда линейная поверхность в $H$ будет иметь вид: $$⟨(x_1^2, x_2^2, \sqrt{2} x_1 x_2), (w_1, w_2, w_3)⟩ + w_0 = w_1 x_1^2 + w_2 x_2^2 + w_3 \sqrt{2} x_1 x_2 + w_0 = x_1^2 + 2 x_2^2 - 3 = 0, w=(1, 2, 0), w_0 = -3$$ Размерность 3.
--Решение
Покажите с помощью теоремы Куна-Таккера, что LASSO Тибширани и l1-регуляризация ли- нейной регрессии приводят к построению одного и того же алгоритма. Решение Лассо Тибширани: \begin{equation*} \begin{cases} & Q(\alpha) = \|F\alpha - y\|^2 \rightarrow min(\alpha) \\ & \sum_{i=1}^{n} |\alpha_j| \leq \kappa \end{cases} \end{equation*} По теореме Куна-Таккера: \begin{equation*} \begin{cases} & Q(\alpha) = \|F\alpha - y\|^2 + \lambda \cdot \left(\sum_{i=1}^{n} |\alpha_j| - \kappa \right) = \|F\alpha - y\|^2 + \lambda \cdot \sum_{i=1}^{n} |\alpha_j| + const \rightarrow min(\alpha) \\ & \lambda \geq 0\\ & \lambda \cdot \left(\sum_{i=1}^{n} |\alpha_i| - \kappa \right) = 0 \Leftrightarrow \lambda = 0 \text{или} \sum_{i=1}^{n} |\alpha_i| = \kappa \end{cases} \end{equation*}
Допустим метки классов +1 и -1.
TP - True Positive - предсказан +1, правильно +1,
FN - False Negative - предсказан -1, правильно +1,
TN - True Negative - предсказан -1, правильно -1,
FP - False Positive - предсказан +1, правильно -1
P - Positive = размер класса +1,
N - Negative = размер класса -1
Тогда $$Accuracy = \frac{TP+TN}{P+N}$$ - доля правильных ответов $$Precision = \frac{TP}{TP+FP}$$ - точность - сколько из предсказанно правильно $$Recall = \frac{TP}{P}$$ - полнота - сколько из правильных предсказали
. ROC-кривая - график зависимости TPR(FPR). ROC-AUC - метрика качества - площадь под ROC-кривой.
По ответам получим множество точек $\{(FPR_i, TPR_i)\}_{i=0}^{l}$, по которой строится ROC-кривая.
1) (FPR_0, TPR_0) = (0, 0)
2) P - число фамилий в выборке, N - не фамилий
3) Отсортием выборку по значениям f(x_i)
4) for i in range(1, l):
5) if y_i == 1:
6) (FPR_i, TPR_i) = (FPR_{i-1}, TPR_{i-1} + 1/P)
7) else:
8) (FPR_i, TPR_i) = (FPR_{i-1} + 1/N, TPR_{i-1})
In [ ]: