Методы машинного обучения

 Шестаков Андрей (avshestakov@hse.ru)

Методы сжатия признаков

Введение в NLP

Методы понижения размерности признаков

Для чего можно понижать размерность признаков?

  • Cмотреть на 2-3 признака удобнее чем на 100
  • Потенциально может улучшить качество моделей
  • Удаление лишних коррелирующих признаков
  • Ускоряет обучение
  • Данные занимают меньше места
  • Меньше признаков - легче интерпретировать модели

Способы понижения размерности

Избавляться от размерности можно методами отбора признаков (Feature Selection) и методами уменьшения размерности (Feature Reduction)

Глобальная разница

  • Feature Selection: не используем часть признаков
  • Feature Reduction: исходные признаки проходят через некоторое преобразование $f(\cdot)$, и на выходе признаков становится меньше

Principal Component Analysis

Метод Главных Компонент

Интерпретация

  • Интерпретация 1: находит такие ортогональные оси, вдоль которых дисперсия данных максимальна

Интерпретация

  • Интерпретация 2: Найти такое подпространство меньшей размерности $L$ Такое что различие между точками и их проекциями минимальна

В двух словах:

  • Совершаем переход к новым осям, так что:
    • Новые переменные являются линейной комбинацией старых переменных
    • Новые оси ортогональны друг другу
    • Дисперсия вдоль новых осей максимальная

Что значит "перейти к новым координатам"?

  • Пусть у нас есть объект $x$ с тремя признаками: $x=(-0.343, -0.754, 0.241)$
  • Можно сказать, что он представлен в пространстве, натянутом на 3 стандартных базистых вектора: $$ e_1 = \left( \begin{array}{c} 1 \\ 0 \\ 0 \end{array} \right) \quad e_2 = \left( \begin{array}{c} 0 \\ 1 \\ 0 \end{array} \right) \quad e_3 = \left( \begin{array}{c} 0 \\ 0 \\ 1 \end{array} \right) \quad$$
$$ x = -0.343 e_1 + -0.754 e_2 + 0.241 e_3 $$
  • Предположими мы хотим перейти к другому базису, например:
$$ w_1 = \left( \begin{array}{c} -0.390 \\ 0.089 \\ -0.916 \end{array} \right) \quad w_2 = \left( \begin{array}{c} -0.639 \\ -0.742 \\ 0.200 \end{array} \right) \quad w_3 = \left( \begin{array}{c} -0.663 \\ 0.664 \\ 0.346 \end{array} \right) \quad$$
  • Как спроицировать наш объект $x$ из исходного базиса в данный?

Проецируем

$$ w_1 = \left( \begin{array}{c} -0.390 \\ 0.089 \\ -0.916 \end{array} \right) \quad w_2 = \left( \begin{array}{c} -0.639 \\ -0.742 \\ 0.200 \end{array} \right) \quad w_3 = \left( \begin{array}{c} -0.663 \\ 0.664 \\ 0.346 \end{array} \right) \quad$$$$ z = W^\top x = \left( \begin{array}{ccc} -0.390 & 0.089 & -0.916\\ -0.639 & -0.742 & 0.200 \\ -0.663 & 0.664 & 0.346 \end{array} \right) \left( \begin{array}{c} -0.343 \\ -0.754 \\ 0.241 \end{array} \right) = \left( \begin{array}{c} -1.154 \\ 0.828 \\ 0.190 \end{array} \right)$$

То есть: $$ x = -1.154 w_1 + 0.828 w_2 + 0.190 w_3$$

(Пример взят из Mohammed J. Zaki, Ch7 )

  • Проецировать научились, осталось только понять как же находить эти самые $w$?
    • Новые оси ортогональны друг другу
    • Дисперсия вдоль новых осей максимальна

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

  • Новые оси ортогональны друг другу: $$\langle w_{i},w_{j}\rangle=\begin{cases} 1, & i=j\\ 0 & i\ne j \end{cases}$$

  • Дисперсия вдоль новых осей максимальна

    • Предполагаем, что исходные признаки центрированы (и шкалированы) $$ \begin{align} \sigma^2_w & = \frac{1}{n}\sum\limits_{i=1}^n(z_i - \mu_z)^2 \\ & = \frac{1}{n}\sum\limits_{i=1}^n(w^\top x_i)^2 \\ & = \frac{1}{n}\sum\limits_{i=1}^n w^\top( x_i x_i^\top) w \\ & = w^\top \left(\frac{1}{n}\sum\limits_{i=1}^n x_i x_i^\top \right) w \\ & = w^\top C w \rightarrow \\ & = w^\top X^\top X w \rightarrow \max_w \\ \end{align} $$

  • $C = X^\top X$ - ковариационная матрица

  • Interpreting Covariance Matrix

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

То есть, чтобы найти первую главную компоненту, надо решить такую задачу: $$ \begin{equation} \begin{cases} w_1^\top X^\top X w_1 \rightarrow \max_{w_1} \\ w_1^\top w_1 = 1 \end{cases} \end{equation} $$

Решение для первой компоненты

Изначально было так $$ w_1^\top X^\top X w_1 \rightarrow \max_{w_1}$$

  • Строим лагранжиан $$ \mathcal{L}(w_1, \nu) = w_1^\top X^\top X w_1 - \nu (w_1^\top w_1 - 1) \rightarrow max_{w_1, \nu}$$
  • Считем производную по $w_1$ $$ \frac{\partial\mathcal{L}}{\partial w_1} = X^\top X w_1 - \nu w_1 = 0 \Leftrightarrow X^\top X w_1 = \nu w_1$$

Подставим одно в другое: $$ w_1^\top X^\top X w_1 = \nu w_1^\top w_1 = \nu \rightarrow \max$$

Задача о собственном векторе, собственном числе матрицы

Пусть для матрицы  $A$ существует ненулевой вектор $v$ и число $\lambda$ такие, что $$Av=\lambda v$$ Тогда вектор $v$ называют собственным вектором оператора $A$, а число $\lambda$ - соответствующим собственным числом оператора $A$.

Оказывается, что у матрицы ковариций $X^\top X$:

  • Все собственные числа $\lambda_i \in \mathbb{R}, \lambda_i \geq 0$ (упорядочим индексы по возрастанию так, что $\lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_d $)
  • Собственные вектора при $\lambda_i \neq \lambda_j $ ортогональны: $v_i^\top v_j = 0$
  • Для уникальных $\lambda_i$ уникальны и $v_i$

Решение для первой компоненты

Изначально было так $$ w_1^\top X^\top X w_1 \rightarrow \max_{w_1}$$

  • Строим лагранжиан $$ \mathcal{L}(w_1, \nu) = w_1^\top X^\top X w_1 - \nu (w_1^\top w_1 - 1) \rightarrow max_{w_1, \nu}$$
  • Считем производную по $w_1$ $$ \frac{\partial\mathcal{L}}{\partial w_1} = X^\top X w_1 - \nu w_1 = 0 \Leftrightarrow X^\top X w_1 = \nu w_1$$

Подставим одно в другое: $$ w_1^\top X^\top X w_1 = \nu w_1^\top w_1 = \nu \rightarrow \max$$

Что значит, что:

  • $\nu$ - наибольшее собственное число матрицы $X^\top X$, а именно - $\lambda_1$
  • $w_1$ - собственный вектор при $\lambda_1$

Задача и решение для второй компоненты

$$ \begin{equation} \begin{cases} w_2^\top X^\top X w_2 \rightarrow \max_{w_2} \\ w_2^\top w_2 = 1 \\ w_2^\top w_1 = 0 \end{cases} \end{equation} $$

Аналогичными операциями мы прийдем к тому, что $w_2$ - собственный вектор при втором по величине собственном числе матрицы $X^\top X$.

То есть поиск главных компонент сводится к поиску собственных векторов и собственных чисел матрицы $X^\top X$!

Алгоритм

  1. Центрируем и шкалируем исходные признаки
  2. Считаем матрицу ковариаций $X^\top X$
  3. Находим $k$ главных компонент и собственных чисел $$W = \left[ \begin{array}{cccc} \mid & \mid & & \mid\\ w_{1} & w_{2} & \ldots & w_{k} \\ \mid & \mid & & \mid \end{array} \right] $$
  4. Проецируем на них: $$ Z = XW $$

Сколько компонент брать или зачем нужны $\lambda$?

  • Из предыдущих слайдов мы помним, что $$w_1^\top X^\top X w_1 = \lambda_1$$ То есть $\lambda_1$ равна дисперсии точек, спроецированных на первую базовую компоненту
  • Величина $$ \frac{\lambda_{i}}{\sum_{d=1}^{D}\lambda_{d}} $$ Показывает долю объясненной дисперии компоненты $i$

MNIST, DIGITS

MNIST PCA

Резюме

  • PCA понижает размерность признакового пространства
  • Новые компоненты являются линейной комбинацией исходных признаков
  • Новые компоненты (не признаки) - ортогональны
  • Можно применять в моделях и для визуализации
  • Tutorial 1
  • PCA SVD туториал

Многомерное шкалирование

Идея

  • Перейти в пространство меньшей размерности так, чтобы расстояния между объектами в новом пространстве были подобны расстояниям в исходном пространстве.
  • Дано $X = [x_1,\dots, x_n]\in \mathbb{R}^{N \times D}$ и/или $\delta_{ij}$ - мера близости между $(x_i,x_j)$
  • Надо найти $Y = [y_1,\dots,y_n] \in \mathbb{R}^{N \times d}$ такие, что $\delta_{ij} \approx d(y_i, y_j) = \|y_i-y_j\|^2$

Понятно, что точно воспроизвести расстояния получится не всегда

Подходы

  • Классический (cMDS)
  • Метрический (metric MDS)
  • Неметрический (non-metric MDS)

t-SNE

t-distributed stochastic neighbor embedding

  • t-SNE - практически многомерное шкалирование
  • Вместо этого мы будем пытаться перенести "окрестность" точек из исходного пространства в пространоство меньшей размерности
  • Полученные расстояния скорее всего не будут соотносится с исходными
  • Схожесть между объектами в исходном пространстве $\mathbb{R}^m$ $$ p(i, j) = \frac{p(i | j) + p(j | i)}{2n}, \quad p(j | i) = \frac{\exp(-\|\mathbf{x}_j-\mathbf{x}_i\|^2/{2 \sigma_i^2})}{\sum_{k \neq i}\exp(-\|\mathbf{x}_k-\mathbf{x}_i\|^2/{2 \sigma_i^2})} $$ $\sigma_i$ неявно задается пользователем
  • Схожесть между объектами в целевом пространстве $\mathbb{R}^k, k << m$ $$ q(i, j) = \frac{g(|\mathbf{y}_i - \mathbf{y}_j|)}{\sum_{k \neq l} g(|\mathbf{y}_i - \mathbf{y}_j|)} $$ где $g(z) = \frac{1}{1 + z^2}$ - распределение Коши (t-распределение Стьюдента с 1 степенью свободы)
  • Критерий $$ J_{t-SNE}(y) = KL(P \| Q) = \sum_i \sum_j p(i, j) \log \frac{p(i, j)}{q(i, j)} \rightarrow \min\limits_{\mathbf{y}} $$

Дивергенция Кульбака-Лейблера

  • Насколько распределение $P$ отличается от распределения $Q$? $$ KL(P \| Q) = \sum_z P(z) \log \frac{P(z)}{Q(z)} $$

Оптимизация

  • Оптимизируем $J_{t-SNE}(y)$ с помощью градиентного спуска
$$\frac{\partial J_{t-SNE}}{\partial y_i}=4 \sum_j(p(i,j)−q(i,j))(y_i−y_j)g(|y_i−y_j|)$$
  • Статья
  • Примеры
  • Демо и советы
    • t-SNE может быть нестабильным
    • Размеры полученных сгустков могут ничего не значить
    • Расстояния между кластерами могут ничего не значить
    • Полностью шумовые данные могут выдать структуру

Литература

Введение в Natural Language Processing

Компьютерная Лингвистика

  • Компьютерная лингвистика (КЛ) — междисциплинарная область, которая возникла на стыке таких наук, как лингвистика, математика, информатика (Computer Science), прикладная статистика (Applied Statistics).

  • Несколько упрощенно задача компьютерной лингвистики может быть сформулирована как "разработка методов и средств построения лингвистических процессоров для различных прикладных задач по автоматической обработке текстов на ЕЯ (Естественном Языке)"

Приложения

  • Машинный перевод
  • Информационный поиск
  • Реферирование текстов
  • Классификация текстов
    • Фильтрация спама
    • По тональности (семантический анализ)
    • По теме или жанру (multilabel classification)
  • Кластеризация (категоризация) текстов
  • Извлечение именованных сущностей (Named-entity recognition)
  • Вопросно-ответные системы и ассистенты
  • Генерация текстов
  • Проверка правописания

Машинный перевод

NER

Вопросо-ответные системы и ассистенты

Генерация текстов

АОТ - это очень сложно

  • Целый ряд лингвистических неоднозначностей
    • Морфологические: "мой", "три", "стекло"
    • Фонетические: "Надо ждать" - "Надо ж дать"
    • Лексические: "кран", "ключ"
    • Синтаксическая: "мужу изменять нельзя"
  • Язык - динамическая система