Шпаргалка по обучению с учителем
Star

Afshine Amidi и Shervine Amidi; Alexandr Parkhomenko и Труш Георгий (Georgy Trush)

Введение в обучение с учителем

Задан набор точек данных $\{x^{(1)}, ..., x^{(m)}\}$ связанный с набором результатов $\{y^{(1)}, ..., y^{(m)}\}$, мы хотим создать классификатор, который научится предсказывать $y$ по $x$.

Тип предсказания Различные типы прогнозных моделей перечислены в таблице ниже:

	Регрессия	Классификация
Результат	Непрерывный	Класс
Примеры	Линейная регрессия	Логистическая регрессия, SVM, Наивный Байес

Тип модели Различные модели перечислены в таблице ниже:

	Дискриминационная модель	Генеративная модель
Цель	Прямо оценить $P(y\|x)$	Оценить $P(x\|y)$ затем Вывести $P(y\|x)$
Что изучено	Граница решения	Распределения вероятностей данных
Иллюстрация
Примеры	Регрессии, SVMs	GDA, Наивный Байес

Обозначения и основные понятия

Гипотеза Гипотеза обозначена $h_\theta$ и является выбранной нами моделью. Для заданных входных данных $x^{(i)}$ предсказанный результат модели обозначен $h_\theta(x^{(i)})$.

Функция потерь это функция $L:(z,y)\in\mathbb{R}\times Y\longmapsto L(z,y)\in\mathbb{R}$ которая принимает в качестве входных данных прогнозируемое значение $z$, соответствующее значению реальных данных $y$, и выводит, насколько они различны. Общие функции потерь приведены в таблице ниже:

Метод наименьших квадратов (LSE)	Логистическая функция потерь	Hinge loss	Перекрёстная энтропия
$\displaystyle\frac{1}{2}(y-z)^2$	$\displaystyle\log(1+\exp(-yz))$	$\displaystyle\max(0,1-yz)$	$\displaystyle-\Big[y\log(z)+(1-y)\log(1-z)\Big]$

Линейная регрессия	Логистическая регрессия	SVM	Нейронная сеть

Функция стоимости функция стоимости $J$ обычно используется для оценки предсказательной способности модели и определяется функцией потерь $L$ следующим образом:

\[\boxed{J(\theta)=\sum_{i=1}^mL(h_\theta(x^{(i)}), y^{(i)})}\]

Градиентный спуск правило обновления для градиентного спуска выражается скоростью обучения $\alpha\in\mathbb{R}$ и функцией стоимости $J$ следующим образом:

\[\boxed{\theta\longleftarrow\theta-\alpha\nabla J(\theta)}\]

Примечание: Стохастический градиентный спуск (SGD) обновляет параметры на основе случайного обучающего примера, а пакетный градиентный спуск обновляет параметры используя пакет обучающих примеров.

Правдоподобие модели Likelihood $L(\theta)$ при заданных параметрах $\theta$ используется для поиска оптимальных параметров $\theta$ посредством максимизации правдоподобия.

\[\boxed{\theta^{\textrm{opt}}=\underset{\theta}{\textrm{arg max }}L(\theta)}\]

Примечание: На практике мы используем логарифмическую вероятность $\ell(\theta)=\log(L(\theta))$, которую легче оптимизировать. У нас есть:

Алгоритм Ньютона это численный метод, который находит такое $\theta$, что $\ell'(\theta)=0$. Его правила обновления следующие:

\[\boxed{\theta\leftarrow\theta-\frac{\ell'(\theta)}{\ell''(\theta)}}\]

Примечание: многомерное обобщение, также известное как метод Ньютона-Рафсона, имеет следующее правило обновления:

\[\theta\leftarrow\theta-\left(\nabla_\theta^2\ell(\theta)\right)^{-1}\nabla_\theta\ell(\theta)\]

Линейные модели

Линейная регрессия

Мы предполагаем здесь что $y|x;\theta\sim\mathcal{N}(\mu,\sigma^2)$

Нормальные уравнения Обозначим $X$ как матрицу данных (объекты-признаки), значение $\theta$, которое минимизирует функцию стоимости, является решением в аналитическом виде, так что:

\[\boxed{\theta=(X^TX)^{-1}X^Ty}\]

Алгоритм LMS обозначим $\alpha$ скорость обучения, правило обновления алгоритма наименьших средних квадратов (LMS) для обучающего набора из $m$ точек данных, которое также известно как правило обучения Уидроу-Хоффа, выглядит следующим образом:

\[\boxed{\forall j,\quad \theta_j \leftarrow \theta_j+\alpha\sum_{i=1}^m\left[y^{(i)}-h_\theta(x^{(i)})\right]x_j^{(i)}}\]

Примечание: правило обновления - это частный случай градиентного подъема.

LWR Locally Weighted Regression - Локально взвешенная регрессия, представляет собой вариант линейной регрессии, который взвешивает каждый обучающий пример в его функции стоимости по $w^{(i)}(x)$, которая определяется параметром $\tau\in\mathbb{R}$ как:

\[\boxed{w^{(i)}(x)=\exp\left(-\frac{(x^{(i)}-x)^2}{2\tau^2}\right)}\]

Классификация и логистическая регрессия

Сигмоидальная функция сигмовидная функция $g$, также известная как логистическая функция, определяется следующим образом:

\[\forall z\in\mathbb{R},\quad\boxed{g(z)=\frac{1}{1+e^{-z}}\in]0,1[}\]

Логистическая регрессия Мы предполагаем здесь $y|x;\theta\sim\textrm{Bernoulli}(\phi)$. Имеем следующий вид:

\[\boxed{\phi=p(y=1|x;\theta)=\frac{1}{1+\exp(-\theta^Tx)}=g(\theta^Tx)}\]

Remark: logistic regressions do not have closed form solutions.

Регрессия Softmax Регрессия softmax, также называемая многоклассовой логистической регрессией, используется для обобщения логистической регрессии, когда существует более двух классов результатов. По соглашению мы полагаем $\theta_K=0$, что делает параметр Бернулли $\phi_i$ каждого класса $i$ равным:

\[\boxed{\displaystyle\phi_i=\frac{\exp(\theta_i^Tx)}{\displaystyle\sum_{j=1}^K\exp(\theta_j^Tx)}}\]

Обобщенные линейные модели

Экспоненциальное семейство класс распределений называется экспоненциальным семейством, если его можно записать в терминах естественного параметра, также называемого каноническим параметром или функцией связи, $\eta$, достаточной статистикой $T(y)$ и лог-статистическую сумму $a(\eta)$ следующим образом:

\[\boxed{p(y;\eta)=b(y)\exp(\eta T(y)-a(\eta))}\]

Примечание: у нас будет часто $T(y)=y$. Также, $\exp(-a(\eta))$ можно рассматривать как параметр нормализации, который гарантирует, что сумма вероятностей равна единице.

Наиболее распространенные экспоненциальные распределения приведенны в следующей таблице:

Распределения	$\eta$	$T(y)$	$a(\eta)$	$b(y)$
Бернулли	$\log\left(\frac{\phi}{1-\phi}\right)$	$y$	$\log(1+\exp(\eta))$	$1$
Гаусса	$\mu$	$y$	$\frac{\eta^2}{2}$	$\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{y^2}{2}\right)$
Пуассона	$\log(\lambda)$	$y$	$e^{\eta}$	$\displaystyle\frac{1}{y!}$
Геометрическое	$\log(1-\phi)$	$y$	$\log\left(\frac{e^\eta}{1-e^\eta}\right)$	$1$

Предположения GLM Обобщенные линейные модели (GLM) нацелены на предсказание случайной величины $y$ как функции от $x\in\mathbb{R}^{n+1}$ и основываются на следующих трех предположениях:

$(1)\quad\boxed{y|x;\theta\sim\textrm{ExpFamily}(\eta)}$

$(2)\quad\boxed{h_\theta(x)=E[y|x;\theta]}$

$(3)\quad\boxed{\eta=\theta^Tx}$

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

Метод Опорных Векторов

Задача метода опорных векторов - найти линию, которая максимизирует минимальное расстояние до линии.

Оптимальный классификатор с зазором $h$ таков, что:

\[\boxed{h(x)=\textrm{sign}(w^Tx-b)}\]

где $(w, b)\in\mathbb{R}^n\times\mathbb{R}$ является решением следующей задачи оптимизации:

\[\boxed{\min\frac{1}{2}||w||^2}\quad\quad\textrm{так что }\quad \boxed{y^{(i)}(w^Tx^{(i)}-b)\geqslant1}\]

Примечание: граница решения определяется как $\boxed{w^Tx-b=0}$.

Hinge loss используется в качестве функции потерь SVM и определяются следующим образом:

\[\boxed{L(z,y)=[1-yz]_+=\max(0,1-yz)}\]

Kernel Учитывая отображение признаков $\phi$, мы определяем ядро $K$ как:

\[\boxed{K(x,z)=\phi(x)^T\phi(z)}\]

На практике ядро $K$ определяется как $K(x,z)=\exp\left(-\frac{||x-z||^2}{2\sigma^2}\right)$ называется ядром Гаусса и чаще всего используется.

Примечание: мы говорим, что используем "трюк с ядром" для вычисления функции стоимости с использованием ядра, потому что нам фактически не нужно знать явное отображение $\phi$, которое часто бывает очень сложным. Вместо этого нужны только значения $K(x,z)$.

Лагранжиан Определим лагранжиан $\mathcal{L}(w,b)$ следующим образом:

\[\boxed{\mathcal{L}(w,b)=f(w)+\sum_{i=1}^l\beta_ih_i(w)}\]

Примечание: коэффициенты $\beta_i$ называются множителями Лагранжа.

Генеративное обучение

Генеративная модель сначала пытается узнать, как генерируются данные, оценивая $P(x|y)$, которое мы затем можем использовать для оценки $P(y|x)$ с помощью правила Байеса.

Гауссовский дискриминантный анализ

Настройка Гауссовский дискриминантный анализ предполагает, что $y$ и $x|y=0$ и $x|y=1$ таковы, что:

$(1)\quad\boxed{y\sim\textrm{Bernoulli}(\phi)}$

$(2)\quad\boxed{x|y=0\sim\mathcal{N}(\mu_0,\Sigma)}$

$(3)\quad\boxed{x|y=1\sim\mathcal{N}(\mu_1,\Sigma)}$

Оценка В следующей таблице суммированы оценки, которые мы находим при максимизации правдоподобия:

$\widehat{\phi}$	$\widehat{\mu_j}\quad{\small(j=0,1)}$	$\widehat{\Sigma}$
$\displaystyle\frac{1}{m}\sum_{i=1}^m1_{\{y^{(i)}=1\}}$	$\displaystyle\frac{\sum_{i=1}^m1_{\{y^{(i)}=j\}}x^{(i)}}{\sum_{i=1}^m1_{\{y^{(i)}=j\}}}$	$\displaystyle\frac{1}{m}\sum_{i=1}^m(x^{(i)}-\mu_{y^{(i)}})(x^{(i)}-\mu_{y^{(i)}})^T$

Наивный Байес

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

\[\boxed{P(x|y)=P(x_1,x_2,...|y)=P(x_1|y)P(x_2|y)...=\prod_{i=1}^nP(x_i|y)}\]

Решения Максимизация логарифмического правдоподобия дает следующие решения:

\[\boxed{P(y=k)=\frac{1}{m}\times\#\{j|y^{(j)}=k\}}\quad\textrm{ and }\quad\boxed{P(x_i=l|y=k)=\frac{\#\{j|y^{(j)}=k\textrm{ and }x_i^{(j)}=l\}}{\#\{j|y^{(j)}=k\}}}\]

с $k\in\{0,1\}$ and $l\in[\![1,L]\!]$

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

Древовидные и ансамблевые методы

Эти методы можно использовать как для регрессионных, так и для классификационных задач.

Classification and Regression Trees (CART) Деревья классификации и регрессии, широко известные как деревья решений, могут быть представлены как двоичные деревья. Их преимущество в том, что они легко интерпретируемы.

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

Примечание: случайные леса - это разновидность ансамблевых методов.

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

Адаптивный бустинг	Градиентный бустинг
• Ошибкам уделяется большое внимание, чтобы их можно было исправить на следующем этапе усиления • Известный как Adaboost	• Слабые ученики обучаются на разнице • Примеры включают XGBoost

Другие непараметрические подходы

$k$-ближайшие соседи Алгоритм $k$-ближайших соседей, широко известный как $k$-NN, представляет собой непараметрический подход, в котором ответ точки данных определяется природой её $k$ соседей из обучающего набора. Его можно использовать как для классификации, так и для настройки регрессии.

Примечание: Чем выше параметр $k$, тем выше смещение, а чем ниже параметр $k$, тем выше дисперсия.

Теория вычислительного обучения

Связанный союз Пусть $A_1, ..., A_k$ есть $k$ событий. Мы имеем:

\[\boxed{P(A_1\cup ...\cup A_k)\leqslant P(A_1)+...+P(A_k)}\]

Неравенство Хёфдинга Пусть $Z_1, .., Z_m$ - $m$ независимых и одинаково распределенных переменных, взятых из распределения Бернулли для параметра $\phi$. Пусть $\widehat{\phi}$ их выборочное среднее, а $\gamma>0$ фиксированное. У нас есть:

\[\boxed{P(|\phi-\widehat{\phi}|>\gamma)\leqslant2\exp(-2\gamma^2m)}\]

Примечание: это неравенство также известно как граница Чернова.

Ошибка тренировки Для данного классификатора $h$ мы определяем ошибку обучения $\widehat{\epsilon}(h)$, также известную как эмпирический риск или эмпирическая ошибка, следующим образом:

\[\boxed{\widehat{\epsilon}(h)=\frac{1}{m}\sum_{i=1}^m1_{\{h(x^{(i)})\neq y^{(i)}\}}}\]

Probably Approximately Correct (PAC) Вероятно приближённо корректное обучение - эта схема, в рамках которой были доказаны многочисленные результаты по теории обучения, и имеет следующий набор предположений:

наборы для обучения и тестирования имеют одинаковое распределение
обучающие примеры строятся независимо

Разрушение (Shattering) Для набора $S=\{x^{(1)},...,x^{(d)}\}$ и набора классификаторов $\mathcal{H}$ мы говорим, что $\mathcal{H}$ разрушает $S$, если для любого набора меток $\{y^{(1)}, ..., y^{(d)}\}$, у нас есть:

\[\boxed{\exists h\in\mathcal{H}, \quad \forall i\in[\![1,d]\!],\quad h(x^{(i)})=y^{(i)}}\]

Теорема о верхней оценке Пусть $\mathcal{H}$ - конечный класс гипотез, такой что $|\mathcal{H}|=k$, и пусть $\delta$ и размер выборки $m$ фиксированы. Тогда с вероятностью не менее $1-\delta$, у нас есть:

\[\boxed{\epsilon(\widehat{h})\leqslant\left(\min_{h\in\mathcal{H}}\epsilon(h)\right)+2\sqrt{\frac{1}{2m}\log\left(\frac{2k}{\delta}\right)}}\]

VC размерность Размерность Вапника-Червоненкиса (VC) данного бесконечного класса гипотез $\mathcal{H}$, обозначается как $\textrm{VC}(\mathcal{H})$, - это размер самого большого множества, которое разрушается $\mathcal{H}$.

Примечание: VC размерность ${\small\mathcal{H}=\{\textrm{набор линейных классификаторов в 2-х измерениях}\}}$ это 3.

Теорема (Вапника) Пусть задано $\mathcal{H}$, $\textrm{VC}(\mathcal{H})=d$ и $m$ - количество обучающих примеров. По крайней мере, с вероятностью $1-\delta$, у нас есть:

\[\boxed{\epsilon(\widehat{h})\leqslant \left(\min_{h\in\mathcal{H}}\epsilon(h)\right) + O\left(\sqrt{\frac{d}{m}\log\left(\frac{m}{d}\right)+\frac{1}{m}\log\left(\frac{1}{\delta}\right)}\right)}\]

Шпаргалка по обучению с учителем Star