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

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

Введение в обучение без учителя

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

Неравенство Йенсена Пусть $f$ - выпуклая функция, а $X$ - случайная величина. $E$ - математическое ожидание. Имеем следующее неравенство:

\[\boxed{E[f(X)]\geqslant f(E[X])}\]

Кластеризация

Максимизация Ожидания

Скрытые величины это скрытые/ненаблюдаемые величины, которые затрудняют задачи оценки, и часто обозначаются буквой $z$. Вот наиболее распространенные ситуации, когда возникают скрытые величины:

Настройка	Latent variable $z$	$x\|z$	Комментарии
Смесь $k$ гауссиан	$\textrm{Multinomial}(\phi)$	$\mathcal{N}(\mu_j,\Sigma_j)$	$\mu_j\in\mathbb{R}^n, \phi\in\mathbb{R}^k$
Факторный анализ	$\mathcal{N}(0,I)$	$\mathcal{N}(\mu+\Lambda z,\psi)$	$\mu_j\in\mathbb{R}^n$

Алгоритм Алгоритм ожидания-максимизации (Expectation-Maximization, EM) дает эффективный метод оценки параметра $\theta$ посредством оценки максимального правдоподобия путем многократного построения нижней границы правдоподобия (E-шаг) и оптимизации этой нижней границы (M-шаг) следующим образом:

E-шаг: Оценить апостериорную вероятность $Q_{i}(z^{(i)})$ того, что каждая точка данных $x^{(i)}$ пришла из определенного кластера $z^{(i)}$ следующим образом:
\[\boxed{Q_i(z^{(i)})=P(z^{(i)}|x^{(i)};\theta)}\]
M-шаг: Использовать апостериорные вероятности $Q_i(z^{(i)})$ в качестве весовых коэффициентов для конкретных кластеров точек данных $x^{(i)}$, чтобы отдельно переоценить каждую модель кластера следующим образом:
\[\boxed{\theta_i=\underset{\theta}{\textrm{argmax }}\sum_i\int_{z^{(i)}}Q_i(z^{(i)})\log\left(\frac{P(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}\right)dz^{(i)}}\]

Метод $k$-средних

Мы обозначаем $c^{(i)}$ кластер точки данных $i$ и $\mu_j$ центр кластера $j$.

Алгоритм после случайной инициализации центроидов кластера $\mu_1,\mu_2,...,\mu_k\in\mathbb{R}^n$ алгоритм $k$-средних повторяет следующий шаг до сходимости:

\[\boxed{c^{(i)}=\underset{j}{\textrm{arg min}}||x^{(i)}-\mu_j||^2}\quad\textrm{и}\quad\boxed{\mu_j=\frac{\displaystyle\sum_{i=1}^m1_{\{c^{(i)}=j\}}x^{(i)}}{\displaystyle\sum_{i=1}^m1_{\{c^{(i)}=j\}}}}\]

Функция искажения Чтобы увидеть, сходится ли алгоритм, мы смотрим на функцию искажения, определенную следующим образом:

\[\boxed{J(c,\mu)=\sum_{i=1}^m||x^{(i)}-\mu_{c^{(i)}}||^2}\]

Иерархическая кластеризация

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

Типы Существуют различные виды алгоритмов иерархической кластеризации, которые направлены на оптимизацию различных целевых функций, которые приведены в таблице ниже:

Связь Уорда	Средняя связь	Полная связь
Минимизирует расстояние в пределах кластера	Минимизирует среднее расстояние между парами кластеров	Минимизирует максимальное расстояние между парами кластеров

Кластеризация показателей оценки

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

Коэффициент силуэта Обозначим $a$ и $b$ среднее расстояние между образцом и всеми другими точками в том же классе, а также между образцом и всеми другими точками в следующем ближайшем кластере, коэффициент силуэта $s$ для одного образца определяется следующим образом:

\[\boxed{s=\frac{b-a}{\max(a,b)}}\]

Индекс Калински-Харабаза Обозначим $k$ количество кластеров, $B_k$ и $W_k$ матрицы дисперсии между кластерами и внутри кластеров, соответственно определяемые как

\[B_k=\sum_{j=1}^kn_{c^{(i)}}(\mu_{c^{(i)}}-\mu)(\mu_{c^{(i)}}-\mu)^T,\quad\quad W_k=\sum_{i=1}^m(x^{(i)}-\mu_{c^{(i)}})(x^{(i)}-\mu_{c^{(i)}})^T\]

индекс Калински-Харабаза $s(k)$ показывает, насколько хорошо модель кластеризации определяет свои кластеры, так что чем выше оценка, тем более плотными и хорошо разделенными являются кластеры. Это определяется следующим образом:

\[\boxed{s(k)=\frac{\textrm{Tr}(B_k)}{\textrm{Tr}(W_k)}\times\frac{N-k}{k-1}}\]

Уменьшение размерности

Метод главных компонент

Это метод уменьшения размерности, который находит направления максимизации дисперсии для проецирования данных.

Собственное значение, собственный вектор Для матрицы $A\in\mathbb{R}^{n\times n}$ $\lambda$ называется собственным значением $A$, если существует вектор $z\in\mathbb{R}^n\backslash\{0\}$, называемый собственным вектором, так что у нас есть:

\[\boxed{Az=\lambda z}\]

Спектральная теорема Пусть $A\in\mathbb{R}^{n\times n}$. Если $A$ симметрична, то $A$ диагонализуема вещественной ортогональной матрицей $U\in\mathbb{R}^{n\times n}$. Обозначим $\Lambda=\textrm{diag}(\lambda_1,...,\lambda_n)$, у нас есть:

\[\boxed{\exists\Lambda\textrm{ diagonal},\quad A=U\Lambda U^T}\]

Примечание: собственный вектор, связанный с наибольшим собственным значением, называется главным собственным вектором матрицы $A$.

Алгоритм Principal Component Analysis (PCA) - это метод уменьшения размерности, который проецирует данные на $k$ измерений, максимизируя дисперсию данных следующим образом:

Шаг 1: Нормализовать данные, чтобы получить среднее значение 0 и стандартное отклонение 1.
\[\boxed{x_j^{(i)}\leftarrow\frac{x_j^{(i)}-\mu_j}{\sigma_j}}\quad\textrm{где}\quad\boxed{\mu_j = \frac{1}{m}\sum_{i=1}^mx_j^{(i)}}\quad\textrm{и}\quad\boxed{\sigma_j^2=\frac{1}{m}\sum_{i=1}^m(x_j^{(i)}-\mu_j)^2}\]
Шаг 2: Вычислить $\displaystyle\Sigma=\frac{1}{m}\sum_{i=1}^mx^{(i)}{x^{(i)}}^T\in\mathbb{R}^{n\times n}$, она симметричная с действительными собственными значениями.
Шаг 3: Вычислить $u_1, ..., u_k\in\mathbb{R}^n$ the $k$ ортогональных главных собственных векторов матрицы $\Sigma$, то есть ортогональных собственных векторов $k$ наибольших собственных значений.
Шаг 4: Спроецировать данные на $\textrm{span}_\mathbb{R}(u_1,...,u_k)$.

Эта процедура максимизирует дисперсию всех $k$-мерных пространств.

Метод независимых компонент

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

Предположения Мы предполагаем, что наши данные $x$ были сгенерированы $n$-мерным исходным вектором $s=(s_1,...,s_n)$, где $s_i$ - независимые случайные величины, посредством смешивающей и невырожденной матрицы $A$ следующим образом:

\[\boxed{x=As}\]

Цель состоит в том, чтобы найти матрицу разложения $W=A^{-1}$.

Алгоритм анализа независимых компонент Белла и Сейновского Bell and Sejnowski Independent Component Analysis, ICA - Этот алгоритм находит матрицу разложения $W$, выполнив следующие шаги:

Записать вероятность $x=As=W^{-1}s$ как:
\[p(x)=\prod_{i=1}^np_s(w_i^Tx)\cdot|W|\]
Записать логарифмическое правдоподобие с учетом наших обучающих данных $\{x^{(i)}, i\in[\![1,m]\!]\}$ и обозначенной $g$ сигмоидальной функции как:
\[l(W)=\sum_{i=1}^m\left(\sum_{j=1}^n\log\Big(g'(w_j^Tx^{(i)})\Big)+\log|W|\right)\]

Следовательно, правило обучения стохастическому градиентному восхождению таково, что для каждого обучающего примера $x^{(i)}$ мы обновляем $W$ следующим образом:

\[\boxed{W\longleftarrow W+\alpha\left(\begin{pmatrix}1-2g(w_1^Tx^{(i)})\\1-2g(w_2^Tx^{(i)})\\\vdots\\1-2g(w_n^Tx^{(i)})\end{pmatrix}{x^{(i)}}^T+(W^T)^{-1}\right)}\]

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