Встраивания в машинное обучение: упрощение сложных данных

Работа с нечисловыми данными может быть сложной даже для опытных специалистов по данным. Типичная модель машинного обучения предполагает, что ее функциями будут числа, а не слова, электронные письма, страницы веб-сайтов, списки, графики или распределения вероятностей. Чтобы быть полезными, данные должны быть сначала преобразованы в векторное пространство. Но как?

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

Другим подходом может быть определение расстояния между выборками данных , функция, которая сообщает нам, насколько близки любые две выборки. Или мы могли бы определить меру сходства , которая дала бы нам ту же информацию, за исключением того, что расстояние между двумя близкими образцами мало, а сходство велико. Вычисление расстояния (сходства) между всеми образцами данных даст нам матрицу расстояния (или сходства). Это числовые данные, которые мы могли бы использовать.

Тем не менее, эти данные будут иметь столько измерений, сколько существует выборок, что обычно не очень хорошо, если мы хотим использовать их в качестве функции (см. Проклятие размерности) или визуализировать их (хотя один график может обрабатывать даже 6D, я еще чтобы увидеть график 100D). Можем ли мы уменьшить количество измерений до разумного?

Ответ - да! Для этого у нас есть вложения .

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

Вложение — это низкоразмерное представление многомерных данных. Как правило, встраивание не захватывает всю информацию, содержащуюся в исходных данных. Однако хорошее встраивание захватит достаточно, чтобы решить проблему.

Существует множество вложений, адаптированных для конкретной структуры данных. Например, вы могли слышать о word2vec для текстовых данных или о дескрипторах Фурье для данных изображения формы. Вместо этого мы обсудим, как применять вложения к любым данным, где мы можем определить расстояние или меру сходства. Пока мы можем вычислить матрицу расстояний, природа данных совершенно не имеет значения. Он будет работать одинаково, будь то электронная почта, списки, деревья или веб-страницы.

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

Давайте начнем.

Как работают вложения

Все вложения пытаются уменьшить размерность данных, сохраняя при этом «существенную» информацию в данных, но каждое встраивание делает это по-своему. Здесь мы рассмотрим несколько популярных вложений, которые можно применить к матрице расстояния или сходства.

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

Если вы хотите посмотреть, какие еще существуют вложения, вы можете начать здесь:

• Руководство пользователя Scikit-learn
• Элементы статистического обучения (второе издание), глава 14

Матрица расстояний

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

Вы также должны помнить о некоторых технических деталях. Многие алгоритмы встраивания предполагают, что матрица расстояний (или несходства ) $\textbf{D}$ имеет нули по диагонали и является симметричной. Если это не симметрично, мы можем вместо этого использовать $(\textbf{D} + \textbf{D}^T) / 2$. Алгоритмы, использующие трюк с ядром, также будут предполагать, что расстояние является метрикой, а это означает, что выполняется неравенство треугольника:

\[\для всех a, b, c \;\; d(a,c) \leq d(a,b) + d(b,c)\]

Кроме того, если алгоритму вместо этого требуется матрица подобия, мы можем применить любую монотонно убывающую функцию для преобразования матрицы расстояний в матрицу подобия: например, $\exp -x$.

Анализ главных компонентов (PCA)

Анализ главных компонентов, или PCA, вероятно, является наиболее широко используемым методом встраивания на сегодняшний день. Идея проста: найти линейное преобразование признаков, которое максимизирует захваченную дисперсию или (что эквивалентно) минимизирует квадратичную ошибку реконструкции .

В частности, пусть признаки представляют собой выборочную матрицу $\textbf{X} \in \mathbb{R}^{n \times p}$, имеющую $n$ признаков и $p$ размерностей. Для простоты предположим, что среднее значение выборки данных равно нулю. Мы можем уменьшить количество измерений с $p$ до $q$, умножив $\textbf{X}$ на ортонормированную матрицу $\textbf{V}_q \in \mathbb{R}^{p \times q}$ :

\[\шляпа{\textbf{X}} = \textbf{X} \textbf{V}_q\]

Тогда $\hat{\textbf{X}} \in\mathbb{R}^{n \times q}$ будет новым набором признаков. Чтобы отобразить новые функции обратно в исходное пространство (эта операция называется реконструкцией ), нам просто нужно снова умножить ее на $\textbf{V}_q^T$.

Теперь нам нужно найти матрицу $\textbf{V}_q$, минимизирующую ошибку восстановления:

\[\min_{\textbf{V}_q} ||\textbf{X}\textbf{V}_q\textbf{V}_q^T - \textbf{X}||^2\]

Столбцы матрицы $\textbf{V}_q$ называются направлениями главных компонент, а столбцы матрицы $\hat{\textbf{X}}$ называются главными компонентами. Численно мы можем найти $\textbf{V}_q$, применив SVD-разложение к $\textbf{X}$, хотя есть и другие не менее действенные способы сделать это.

PCA можно применять непосредственно к числовым признакам. Или, если наши функции не являются числовыми, мы можем применить их к матрице расстояний или подобия.

Если вы используете Python, PCA реализован в scikit-learn.

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

Недостатком будет то, что он может фиксировать только линейные структуры, поэтому нелинейная информация, содержащаяся в исходных данных, может быть потеряна.

Ядро PCA

Kernel PCA — это нелинейная версия PCA. Идея состоит в том, чтобы использовать трюк ядра , о котором вы, вероятно, слышали, если знакомы с SVM Support Vector Machines.

В частности, существует несколько различных способов вычисления PCA. Один из них заключается в вычислении собственного разложения двухцентровой версии грамм-матрицы $\textbf{X} \textbf{X}^T \in \mathbb{R}^{n \times n}$. Теперь, если мы вычислим матрицу ядра $\textbf{K} \in \mathbb{R}^{n \times n}$ для наших данных, Kernel PCA будет рассматривать ее как матрицу граммов, чтобы найти главные компоненты.

Пусть $x_i$, $i \in {1,..,n}$ — выборки признаков. Матрица ядра определяется функцией ядра $K(x_i,x_j)=\langle \phi(x_i),\phi(x_j) \rangle$.

Популярным выбором является радиальное ядро:

\[K(x_i,x_j)=\exp -\gamma \cdot d(x_i,x_j)\]

где $d$ — функция расстояния.

Ядро PCA потребовало от нас указать расстояние. Например, для числовых признаков мы могли бы использовать евклидово расстояние: $d(x_i,x_j)=\vert\vert x_i-x_j \vert \vert ^2$.

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

Если вы используете Python, Kernel PCA реализован в scikit-learn.

Преимущество метода Kernel PCA заключается в том, что он может захватывать нелинейные структуры данных.

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

Многомерное масштабирование (MDS)

Многомерное масштабирование (MDS) пытается сохранить расстояния между выборками в глобальном масштабе. Идея интуитивно понятна и хорошо работает с матрицами расстояний.

В частности, учитывая образцы признаков $x_i$, $i \in {1,..,n}$ и функцию расстояния $d$, мы вычисляем новые образцы признаков $z_i \in \mathbb{R}^{q}$, $i \in {1,..,n}$ путем минимизации функции напряжения :

\[\min_{z_1,..,z_n} \sum_{1 \leq i < j \leq n} (d(x_i, x_j) - ||z_i - z_j||)^2\]

Если вы используете Python, MDS реализован в scikit-learn. Однако scikit-learn не поддерживает преобразование точек вне выборки, что может быть неудобно, если мы хотим использовать вложение в сочетании с регрессионной или классификационной моделью. Однако в принципе это возможно.

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

Недостатком является то, что его реализация в scikit-learn довольно медленная и не поддерживает преобразование вне выборки.

Пример использования: отслеживание доставки

Несколько поселений на небольшом тропическом острове разработали услуги по доставке посылок для обслуживания местной туристической индустрии. Торговец в одном из этих поселений решил действовать, чтобы получить преимущество над конкурентами, поэтому он установил систему спутникового наблюдения, отслеживающую все посылки на острове. Как только данные были собраны, продавец позвонил специалисту по данным (это мы!), чтобы помочь ему ответить на следующий вопрос: можем ли мы предсказать место назначения посылки, которая в данный момент находится в пути?

Набор данных содержит информацию о 200 отслеживаемых отправлениях. Для каждой отслеживаемой посылки существует список (x,y)-координат всех мест, где была обнаружена посылка, который обычно составляет от 20 до 50 наблюдений. На графике ниже показано, как выглядят эти данные.

Эти данные выглядят как проблемы — на самом деле это два разных вида проблем.

Первая проблема заключается в том, что данные, с которыми мы имеем дело, являются многомерными. Например, если бы каждая посылка была обнаружена в 50 местах, наши данные содержали бы 100 измерений — звучит много по сравнению с 200 образцами, имеющимися в вашем распоряжении.

Вторая проблема: разные маршруты доставки на самом деле имеют разное количество наблюдений, поэтому мы не можем просто складывать списки с координатами для представления данных в табличном виде (а даже если бы они и были, это все равно не имело бы особого смысла).

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

Здесь пригодятся матрицы расстояний и вложения. Нам просто нужно найти способ сравнить два маршрута доставки. Расстояние Фреше кажется разумным выбором. С расстоянием мы можем вычислить матрицу расстояний.

Примечание. Этот шаг может занять некоторое время. Нам нужно вычислить $O(n^2)$ расстояний, каждое из которых имеет $O(k^2)$ итераций, где $n$ — количество выборок, а $k$ — количество наблюдений в одной выборке. Ключевым моментом является эффективное написание функции расстояния. Например, в Python вы можете использовать numba для многократного ускорения этих вычислений.

Визуализация вложений

Теперь мы можем использовать вложение, чтобы уменьшить количество измерений с 200 до нескольких. Мы ясно видим, что существует всего несколько торговых путей, поэтому мы можем надеяться найти хорошее представление данных даже в двух или трех измерениях. Мы будем использовать вложения, которые обсуждались ранее: PCA, Kernel PCA и MDS.

На графиках ниже вы можете увидеть размеченные данные маршрута (приведены для демонстрации) и их представление встраиванием в 2D и 3D (слева направо). Размеченные данные отмечают четыре торговых поста, соединенных шестью торговыми путями. Два из шести торговых маршрутов являются двунаправленными, что в сумме составляет восемь групп перевозок (6+2). Как видите, мы получили довольно четкое разделение всех восьми групп поставок с 3D-встраиваниями.

Это хорошее начало.

Вложения в модельный конвейер

Теперь мы готовы обучить встраивание. Хотя MDS показал лучшие результаты, он довольно медленный; Кроме того, реализация scikit-learn не поддерживает преобразование вне выборки. Это не проблема для исследований, но может быть проблемой для производства, поэтому вместо этого мы будем использовать Kernel PCA. Для Kernel PCA не следует забывать предварительно применить радиальное ядро ​​к матрице расстояний.

Как выбрать количество выходных измерений? Анализ показал, что даже 3D работает нормально. Просто чтобы быть в безопасности и не пропустить какую-либо важную информацию, давайте установим вывод встраивания на 10D. Для наилучшей производительности количество выходных измерений можно задать в качестве гиперпараметра модели, а затем настроить с помощью перекрестной проверки.

Итак, у нас будет 10 числовых признаков, которые мы можем использовать в качестве входных данных практически для любой модели классификации. Как насчет одной линейной и одной нелинейной модели: скажем, логистической регрессии и повышения градиента? Для сравнения также используем эти две модели с матрицей полного расстояния в качестве входных данных. Кроме того, давайте также протестируем SVM (SVM предназначен для работы напрямую с матрицей расстояний, поэтому встраивание не потребуется).

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

• Gradient Boosting в паре с встраиванием (KernelPCA+GB) получает первое место. Он превзошел Gradient Boosting без встраивания (GB). Здесь Kernel PCA оказался полезным.
• Логистическая регрессия справилась. Что интересно, логистическая регрессия без встраивания (LR) работала лучше, чем с встраиванием (KernelPCA+LR). Это не совсем неожиданно. Линейные модели не очень гибкие, но их относительно трудно подгонять. Здесь потеря информации, вызванная встраиванием, кажется, перевешивает преимущество меньшей входной размерности.
• И последнее, но не менее важное: SVM также показала хорошие результаты, хотя дисперсия этой модели довольно значительна.

Точность модели

Код Python для этого варианта использования доступен на GitHub.

Заключение

Мы объяснили, что такое вложения, и продемонстрировали, как их можно использовать в сочетании с матрицами расстояний для решения реальных задач. Время приговора:

Являются ли вложения тем, что должен использовать специалист по данным? Давайте посмотрим на обе стороны этой истории.

Плюсы и минусы использования вложений

Плюсы:

• Этот подход позволяет нам работать с необычными или сложными структурами данных до тех пор, пока вы можете определить расстояние, которое — при определенной степени знаний, воображения и удачи — вы обычно можете сделать.
  
• На выходе получаются низкоразмерные числовые данные, которые можно легко анализировать, группировать или использовать в качестве признаков модели практически для любой модели машинного обучения.

Минусы:

• При таком подходе мы обязательно потеряем часть информации:

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

Альтернативы: почему бы не использовать…?

• Почему бы просто не использовать встраивание непосредственно в данные, а не в матрицу расстояний?
  Если вы знаете вложение, которое может эффективно кодировать ваши данные напрямую, во что бы то ни стало, используйте его. Проблема в том, что он не всегда существует.
  
• Почему бы просто не использовать кластеризацию на матрице расстояний?
  Если ваша единственная цель — сегментировать набор данных, то это вполне нормально. Некоторые методы кластеризации также используют встраивания (например, Spectral Clustering). Если вы хотите узнать больше, вот руководство по кластеризации.
  
• Почему бы просто не использовать матрицу расстояний в качестве признаков?
  Размер матрицы расстояний равен $(n_{samples}, n_{samples})$. Не все модели могут справиться с этим эффективно — некоторые могут перестраиваться, некоторые могут подходить медленно, а некоторые могут вообще не подходить. Здесь хорошим выбором будут модели с низкой дисперсией, такие как линейные и/или регуляризованные модели.
  
• Почему бы просто не использовать SVM с матрицей расстояний?
  SVM — отличная модель, которая хорошо зарекомендовала себя в нашем случае. Однако есть некоторые предостережения. Во-первых, если мы захотим добавить другие функции (могут быть просто числовые числа), мы не сможем сделать это напрямую. Нам пришлось бы включить их в нашу матрицу подобия и потенциально потерять некоторую ценную информацию. Во-вторых, как бы ни была хороша SVM, другая модель может лучше подойти для решения вашей конкретной задачи.
  
• Почему бы просто не использовать глубокое обучение?
  Правда, для любой задачи можно найти подходящую нейросеть, если поискать достаточно долго. Имейте в виду, однако, что процесс поиска, обучения, проверки и развертывания этой нейронной сети не обязательно будет простым. Так что, как всегда, используйте свой здравый смысл.

В одном предложении

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