Как машины учатся?

Эта серия представляет собой краткое изложение курса «Основы машинного обучения», предлагаемого профессором Сюань-Тянь Линем с факультета информационной инженерии Тайваньского национального университета. Основное внимание уделяется уходу, а не подробным заметкам, поэтому некоторые детали могут быть опущены.

Курс состоит из 16 лекций, разделенных на 4 части:

1. Когда машины смогут учиться? (Когда машины смогут учиться?)
2. Почему машины могут учиться? (Почему машины могут учиться?)
3. Как машины учатся? (Как машины могут учиться?)
4. Как машины могут учиться лучше? (Как машины могут учиться лучше?)

Эта статья является частью 3, соответствующей лекциям 9-12 исходного курса.

Основное содержание этого раздела:

• Подробное объяснение алгоритма линейной регрессии, а также гарантии способности к обобщению, можно ли его использовать для задач бинарной классификации и т. д.;
• Подробно объясняется алгоритм логистической регрессии и вводится метод градиентного спуска;
• Описать взаимосвязь и различие между PLA, линейной регрессией и логистической регрессией в задачах классификации и представить метод стохастического градиентного спуска;
• методы OVA и OVO в задачах мультиклассификации;
• Нелинейное преобразование признаков и как управлять сложностью преобразования.

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

В первой части классификации машинного обучения, когда$\mathcal{Y}=\mathbb{R}$, это возврат.

1.1 Алгоритм линейной регрессии

линейная регрессиянабор гипотезочень простой,$h(\mathbf{x})=\mathbf{w}^T\mathbf{x}$, по сути, модель персептрона убирает символическую функцию.

Его точечная метрика ошибки может быть установлена ​​​​как$\text{err}(\hat{y}, y)=(\hat{y}-y)^2$, то ошибки внутри и вне выборки равны$E_{\text{in}}(\mathbf{w})=\dfrac{1}{N}\sum\limits_{n=1}^{N}(\mathbf{w}^T \mathbf{x}_n-y_n)^2$и$E_{\text{out}}(\mathbf{w})=\mathop{\mathcal{E}}\limits_{(\mathbf{x},y)\sim P}(\mathbf{w}^T \mathbf{x}-y)^2$свести к минимуму$E_{\text{in}}$Очень просто, когда оно сведено к минимуму, должно бытьградиентза$0$, поэтому сначала можно вычислить его градиент:

будь как будет$0$Вот и все. как показано на рисунке:

как$X^T X$обратимый (когда$N\gg d+1$в основном удовлетворен), его можно получить напрямую$\mathbf{w}_{\text{LIN}}=(X^T X)^{-1} X^T \mathbf{y}$

если$X^T X$Это странно? Сначала можно определить «псевдоинверсию».$X^\dagger$, после определения$\mathbf{w}_{\text{LIN}}=X^\dagger \mathbf{y}$

На практике рекомендуется использовать непосредственно$X^\dagger$, с одной стороны, чтобы избежать осуждения$X^T X$Независимо от того, обратимо оно или нет, с другой стороны, оно численно стабильно, даже если оно почти необратимо.

1.2 Обобщение линейной регрессии

Линейная регрессия, похоже, не имеет процесса «обучения», это одноэтапный процесс, так что это машинное обучение?

На самом деле, пока это может быть гарантировано$E_{\text{out}}(\mathbf{w}_\text{LIN})$Достаточно маленький, значит, обучение «случилось».

Здесь мы не начинаем с теории размерности ВК, а объясняем, почему с другой точки зрения.$E_{\text{out}}(\mathbf{w}_\text{LIN})$будет достаточно мал.

Сначала посмотрим на средний$E_{\text{in}}$Насколько велик:

$\overline{E_{\text{in}}}=\mathop{\mathcal{E}}\limits_{\mathcal{D}\sim P^N}\{E_{\text{in}}(\mathbf{w}_\text{LIN} \text{ w.r.t } \mathcal{D})\}$

в

возможно$H=XX^\dagger$называется шляпной матрицей, потому что она может$\mathbf{y}$сопоставить с$\hat{\mathbf{y}}$. Как видно из рисунка ниже, если$\mathbf{y}$идеалом$f(X)\in \text{span}$плюс шум$\mathbf{noise}$генерировать, затем$I-H$так же может быть$\mathbf{noise}$карты на$\mathbf{y}-\hat{\mathbf{y}}$:

и$\text{trace}(I-H)=N-(d+1)$, след можно понимать как «энергию», поэтому мы имеем

если правильно$E_{\text{in}}$Взяв среднее значение, его можно приблизительно понять как$\overline{E_{\text{in}}}=\mathbf{noise}\text{ level} \cdot (1-\dfrac{d+1}{N})$так же есть$\overline{E_{\text{out}}}=\mathbf{noise}\text{ level} \cdot (1+\dfrac{d+1}{N})$(Процесс доказательства опущен).

следовательно$\overline{E_{\text{in}}}$и$\overline{E_{\text{out}}}$Отношения показаны на рисунке:

как$N\to\infty$, то оба сходятся к$\sigma^2$($\mathbf{noise}\text{ level}$), ожидание ошибки обобщения равно$\dfrac{2(d+1)}{N}$. Поэтому обучение «случается»!

Теория размерности VC утверждает, что$E_{\text{in}}$и$E_{\text{out}}$Существует верхняя граница вероятностей, находящихся далеко друг от друга, и здесь утверждается, что их среднее несоответствие сходится. Ракурсы разные, но оба способа иллюстрируют силу обобщения.

1.3 Бинарная классификация с линейной регрессией

В линейной классификации$\mathcal{Y}=\{+1,-1\}$,$h(\mathbf{x})=\text{sign}({\mathbf{w}^T\mathbf{x}})$,$\text{err}(\hat{y},y)=\mathbf{1}_{[\hat{y}\ne y]}$, нахождение ее оптимального решения является NP-трудной задачей.

так как$\{+1,-1\}\subset \mathbb{R}$, то есть положительные и отрицательные категории выборок также могут быть представлены действительными числами, а в линейной регрессии$\mathcal{Y}=\mathbb{R}$, то непосредственно к линейной регрессии получаем$\mathbf{w}_\text{LIN}$, тогда пусть$g(\mathbf{x})=\text{sign}(\mathbf{w}_\text{LIN}^T\mathbf{x})$, Это возможно?

Обозначим меры ошибок для линейной классификации и линейной регрессии как$\text{err}_{0/1}=\mathbf{1}_{[\text{sign}(\mathbf{w}^T\mathbf{x})\ne y]}$и$\text{err}_\text{sqr}=({\mathbf{w}^T\mathbf{x}- y})^2$, а их соотношение следующее:

Отсюда ясно видно, что$\text{err}_{0/1} \le \text{err}_\text{sqr}$должны быть установлены. Следовательно, существует

То есть пусть возвращается$E_{\text{in}}$сделано достаточно хорошо, чтобы также сделать классифицированным$E_{\text{out}}$Он достаточно мал, но верхний предел более расслаблен. Делать этоПоменяйте тесноту на вычислительную эффективность.

в целом$\mathbf{w}_\text{LIN}$Может использоваться в качестве начального вектора для PLA или карманных алгоритмов.

2 Логистическая регрессия

2.1 Алгоритм логистической регрессии

В бинарной классификации нас интересует

Но во многих сценариях мы хотим сделать «мягкую» классификацию, то есть получить вероятность определенной классификации.На данный момент нас интересует следующее:

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

для всех характеристик образца$\mathbf{x}=(x_0, x_1, x_2, \cdots,x_d)$,сделать$s=\sum\limits_{i=0}^{d} w_i x_i$. Мы можем использовать логистическую функцию$\theta(s)$Преобразуйте его в оценочную вероятность. То есть логистическая регрессияПредположениеза$h(\mathbf{x})=\theta(\mathbf{w}^T\mathbf{x})$.

Наиболее часто используемые логические функции$\theta(s)=\dfrac{e^s}{1+e^s}=\dfrac{1}{1+e^{-s}}$

Изображение функции выглядит следующим образом:

Видно, что она гладкая, монотонная, S-образная (sigmoid)функция.

Далее, чтобы определить логистическую регрессию$E_\text{in}(\mathbf{w})$. сначала целевая функция$f(\mathbf{x})=P(+1|\mathbf{x})$обратно выражается как

Предположим, что набор данных в руке$\mathcal{D}=\{(\mathbf{x}_1,\circ),(\mathbf{x}_2,\times),\ldots, (\mathbf{x}_N,\times)\}$

Затем, по$f$генерировать$\mathcal{D}$Вероятность

по нашему предположению$h$генерировать$\mathcal{D}$вероятность (likelihood)за

если$h\approx f$,Так$h$генерировать$\mathcal{D}$Вероятность также должна быть близка к указанной$f$генерировать$\mathcal{D}$вероятность, а по$f$генерировать$\mathcal{D}$Вероятность должна быть большой (как раз по нашей выборке). Таким образом, алгоритмы машинного обучения могут

как$h(\mathbf{x})=\theta(\mathbf{w}^T\mathbf{x})$, согласно свойствам функции,$1-h(\mathbf{x})=h(-\mathbf{x})$,так

и$P(\mathbf{x}_1)$,$P(\mathbf{x}_2)$,……,$P(\mathbf{x}_N)$оба с$h$неактуально, так что есть

Теперь, чтобы максимизировать его, чтобы найти окончательный$h$. может сначала$\theta(s)$Подставляем, а затем логарифмируем (логарифмическая функция монотонна и не меняет точки максимизации значения), получается

Затем взять обратное число (максимум становится минимумом), разделить$N$(без изменения максимальной точки), его можно изменить на

будет$\theta(s)$расширить, чтобы получить

сделать$\text{err}(\mathbf{w},\mathbf{x},y)=\ln\left(1+\exp(-y\mathbf{w}\mathbf{x})\right)$

Это кросс-энтропийная ошибка (cross-entropy error),и$\sum\limits_{n=1}^N \text{err}(\mathbf{w},\mathbf{x}_n,y_n)$это$E_\text{in}(\mathbf{w})$.

2.2 Градиентный спуск

рядом с минимумом$E_\text{in}(\mathbf{w})$, она непрерывна, дифференцируема, квадратично дифференцируема, выпукла, поэтому постарайтесь сделать ее градиент как$0$. найти его градиент

Его градиент можно рассматривать как$\theta(\cdot)$для взвешенного$-y_n\mathbf{x}_n$средневзвешенное значение . Чтобы сделать его 0, есть два способа:

• пусть все$\theta(-y_n\mathbf{w}^T\mathbf{x}_n)$все равны 0, что означает, что все выборки удовлетворяют$y_n\mathbf{w}_n\mathbf{x}_n\gg 0$, это$\mathcal{D}$линейно отделим;
• как$\mathcal{D}$Оно не является линейно разделимым, пусть взвешенная сумма равна 0, это нелинейное уравнение, и решения в замкнутой форме нет.

Итерация может быть выполнена так же, как и в PLA, т.е.$\mathbf{w}_{t+1}\leftarrow\mathbf{w}_t+\eta\mathbf{v}$,в$\mathbf{v}$Направление обновления определяется,$\eta$Размер шага обновления определяется, как показано на рисунке:

Как повторить? Доступный жадный алгоритм, шаг за шагом$E_\text{in}$стать меньше. Предположим, что некий$\eta$, быть уверенным$\mathbf{v}$направление, проблема обновления на каждом шаге трансформируется в

Это кажется более сложным для понимания. но если$\eta$Достаточно маленький, мы можем расширить его с помощью локального линейного приближения (разложение Тейлора):

в формуле$E_\text{in}(\mathbf{w}_t)$и$\nabla E_\text{in}(\mathbf{w}_t)$известный,$\eta$дано, просто будьте уверены$\mathbf{v}$То есть отмечается, что второй член приведенной выше формулы по существу является скалярным произведением двух векторов. Когда два вектора направлены в противоположные стороны, значение является наименьшим. Поэтому, чтобы минимизировать приведенную выше формулу, можно брать

Затем итеративное обновление градиентного спуска становится: для заданного меньшего$\eta$,$\mathbf{w}_{t+1}\leftarrow\mathbf{w}_t-\eta\dfrac{\nabla E_\text{in}(\mathbf{w}_t)}{\Vert\nabla E_\text{in}(\mathbf{w}_t)\Vert}$

$\eta$Слишком маленькое приведет к очень медленному, слишком большое приведет к нестабильности, лучше всего использовать переменную$\eta$,Как показано ниже:

Так,$\eta$Как это может быть лучше? позволить этому быть$\Vert\nabla E_\text{in}(\mathbf{w}_t)\Vert$положительная корреляция, исходная фиксированная$\eta$ездить на$\Vert\nabla E_\text{in}(\mathbf{w}_t)\Vert$Вот и все. Таким образом, правило обновления становится

этот новый$\eta$фиксированныйскорость обучения(learning rate).

3 Линейные модели для классификации

3.1 Сравнение трех алгоритмов

Помните$s=\mathbf{w}^T\mathbf{x}$, ниже приводится сводка трех моделей (линейная классификация, линейная регрессия, логистическая регрессия):

здесь$ys$показатель точности классификацииcorrectnessscore), который измеряет, насколько верна классификация, и чем больше значение, тем более «правильной» является классификация.

Если кросс-энтропийная функция ошибки$\text{err}_\text{CE}(s,y)$масштабировать (кроме$\ln 2$),получить$\text{err}_\text{SCE}(s,y)=\log_2(1+\exp(-ys))$

Постройте их функции ошибок, чтобы получить следующий рисунок:

Как видно из рисунка, должно быть$\text{err}_{0/1} \le \text{err}_\text{SCE}(s,y) = \dfrac{1}{\ln 2}\text{err}_\text{CE}(s,y)$

Это можно доказать с помощью теории размерности VC, используя$\text{err}_\text{CE}$Вы также можете хорошо справиться с классификационными задачами, есть две идеи:

• С точки зрения классификации существуют

• С точки зрения кросс-энтропии мы имеем

В любом случае, просто убедитесь$E_\text{in}^\text{CE}$достаточно мал, чтобы гарантировать$E_\text{out}^{0/1}(\mathbf{w})$Он также достаточно мал, то есть линейную классификацию можно проводить либо с помощью логистической регрессии, либо с помощью линейной регрессии.

Используя PLA, линейную регрессию и логистическую регрессию для классификации, преимущества и недостатки трех методов заключаются в следующем:

3.2 Стохастический градиентный спуск

Временная сложность каждой итерации PLA составляет$O(1)$, но логистическая регрессия (или карманный алгоритм) требует каждой итерации$\mathcal{D}$Все пробы в операции выполняются один раз, а временная сложность составляет$O(N)$, может ли временная сложность каждой итерации также стать$O(1)$?

мы делаем обновление$\mathbf{w}_{t+1}\leftarrow\mathbf{w}_t+\eta\mathbf{v}$, взял

Видно, что вычисление градиента требует обхода всех выборок, а сложность слишком высока. внутри него$\dfrac{1}{N}\sum\limits_{n=1}^{N}$рассматривается как ожидание$\mathcal{E}$, что эквивалентно среднему результату, рассчитанному путем непрерывной случайной выборки выборки. Если необходимо провести случайную выборку$n$Вычисленный градиент называется стохастическим градиентом$\nabla_\mathbf{w}\text{err}(\mathbf{w},\mathbf{x}_n,y_n)$, то истинный градиент можно рассматривать как его ожидание:

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

В логистической регрессии шаг, обновленный с помощью SGD, становится

Это очень похоже на шаг обновления в PLA, который выглядит так:

Следовательно, логистическую регрессию с SGD можно рассматривать как «мягкую» PLA. Обратно, если мы возьмем$\eta=1$, то PLA находится в$\mathbf{w}_t^T \mathbf{x}_n$Когда он очень велик, его также можно рассматривать как логистическую регрессию с использованием SGD.

При использовании SGD есть два эмпирических правила:

• Когда это прекратится?$t$Это можно сделать, когда он достаточно велик (не судите, действительно ли градиент равен 0, иначе это усложнит вычисление градиента);
• когда$\mathbf{x}$В общем диапазоне взять$\eta=0.1$Бар.

4 проблемы мультиклассификации

4.1 Мультиклассификация с логистической регрессией

Предположение$\mathcal{Y}=\{\square, \diamondsuit,\triangle,\star\}$, распределение данных следующее:

Каждая категория может быть классифицирована один раз, как показано ниже:

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

Как это решить? Логистическую регрессию можно использовать как «мягкий» классификатор для каждой категории.$k$, с набором данных

Сделайте логистическую регрессию, чтобы получить классификатор$\mathbf{w}_{[k]}$:

Чтобы совместить их, когда сделано, желательно$g(\mathbf{x})=\arg\max_{k\in\mathcal{Y}}\theta(\mathbf{w}_{[k]}^T\mathbf{x})$, поэтому вы можете получить, к какому классу должна принадлежать точка:

Это называется декомпозицией OVA (один против всех).Преимущество заключается в том, что оно эффективно и может сочетаться с такими методами, как логистическая регрессия, но недостатком является то, что когда$K$большой, часто$\mathcal{D}_{[k]}$Очень несбалансировано, например, категорий 100, а распределение относительно равномерное, и количество двух типов данных, используемых OVA для каждой обучающей выборки, будет очень разным.

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

4.2 Мультиклассификация с бинарной классификацией

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

Выполните линейную бинарную классификацию:

Наконец, возьмите$g(\mathbf{x})=\text{tournament champion}\{\mathbf{w}_{[k,\ell]}^T\mathbf{x}\}$

Просто:

Такой метод называется декомпозицией OVO (One-Versus-One).Преимущество заключается в том, что он эффективен (поскольку объем данных, используемых для каждого обучения, меньше), и он стабилен и может быть объединен с любым методом бинарной классификации, но недостаток в том, что он постоянно вычисляется$\mathbf{w}_{[k,\ell]}$Общая сложность операции$O(K^2)$, что требует больше вычислительного пространства. когда$K$OVO часто используется, когда он не очень большой.

5 Нелинейное преобразование

Однако для некоторых наборов данных используются линейные модели.$E_{in}$Оба большие:

5.1 Набор квадратичных гипотез

Мы обнаружили, что если в качестве границы классификации используется окружность, то она на самом деле отделима:

Итак, мы собираемся перепроектировать циклический PLA, циклический регресс,  …? конечно, нет. мы можем поставить$\mathbf{x}\in\mathcal{X}$использовать преобразование$\Phi$сопоставить с$\mathbf{z}\in\mathcal{Z}$, так что в$\mathcal{X}$Данные, которые можно разделить в среднем круге, находятся в$\mathcal{Z}$Нейтрально разделяемый.

от$\Phi_2(\mathbf{x})=(1,x_1,x_2,x_1^2,x_1x_2,x^2_2)$сопоставлено с$\mathcal{Z}$пространство, которое может образовывать общее квадратичное множество гипотез:

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

Конкретные шаги заключаются в следующем:

1. Сначала с$\Phi$будет$\{(\mathbf{x}_n,y_n)\}$превратиться в$\{(\mathbf{z}_n=\Phi(\mathbf{x}_n),y_n)\}$;
2. использовать$\{(\mathbf{z}_n,y_n)\}$и алгоритмы линейной классификации$\mathcal{A}$обучить модель$\tilde{\mathbf{w}}$;
3. возвращение$g(\mathbf{x})=\text{sign}\left(\tilde{\mathbf{w}}^T \Phi(\mathbf{x})\right)$Вот и все.

5.2 Цена сложности

предполагается использовать$Q$Нелинейное преобразование времен:

количество членов в формуле$1+\tilde d$Сколько это стоит? если есть$d$Особенностью, после прибавления 1 можно считать, что каждый пункт после приведенной выше формулы$Q$второе, то есть$d+1$Каждому элементу присваивается степень, и сумма всех времен должна быть$Q$. Можно использовать метод вагонки: представьте себе обычную$Q+d+1$маленькие шарики, которые нужно разместить на своих местах$d$перегородки, разделенные на$d+1$Секция, количество шаров в каждой секции минус 1 представляет собой количество предметов в соответствующей позиции. Поскольку в каждой секции требуется как минимум 1 шар, перегородки нельзя размещать с обоих концов. Всего имеется$Q+d$перегородки могут быть размещены в каждой позиции, всего$\binom{Q+d}{d}$Метод помещения, то есть количество терминов справа от знака равенства выше

когда$Q$Когда большие, стоимость вычислений или хранения очень высока, с одной стороны, а с другой стороны.$1+\tilde d$да$d_\text{VC}(\mathcal{H}_{\Phi_Q})$верхняя граница ,$Q$слишком большой вызовет$d_\text{VC}$Если он слишком велик, модель теряет способность к обобщению.

5.3 $Q$выбор

как выбрать$Q$? Предположение$\Phi_0(\mathbf{x})=(1)$,$\Phi_1(\mathbf{x})=\left(\Phi_0(\mathbf{x}),x_1,x_2,\ldots,x_d,\right)$,……,$\Phi_Q(\mathbf{x})=\left(\Phi_{Q-1}(\mathbf{x}),x_1^Q,x_1^{Q-1}x_2,\ldots,x_d^Q,\right)$, и обозначим их наборы гипотез как$\mathcal{H}_0$,$\mathcal{H}_1$,……,$\mathcal{H}_Q$, у них есть вложенные отношения

как показано на рисунке:

Кроме того, их размерность VC удовлетворяет

Если вы возьмете$g_i=\arg\min_{h\in \mathcal{H}_i} E_\text{in}(h)$, то их$E_\text{in}$удовлетворить

как выбрать$Q$? Безопасный способ - посмотреть$E_\text{in}(g_1)$Достаточно ли он уже мал, если он достаточно мал, то все в порядке, в противном случае используйте чуть более сложную модель, которая должна двигаться вправо на следующем рисунке: