Метрические методы

Метрические методы прогнозирования - это методы, прогнозы которых определяются только расстояниями между целевым объектом, для которого строится прогноз, и некоторыми другими объектами $z_1,...z_K$, полученными из обучающей выборки. Таким образом, прогноз строится по общей формуле:

$$\hat{y}(\mathbf{x}) = G(\rho(\mathbf{x},\mathbf{z}_1),y_1, \rho(\mathbf{x},\mathbf{z}_2),y_2, ... \rho(\mathbf{x},\mathbf{z}_K),y_K),$$

где $\rho(\mathbf{x},\mathbf{z})$ - функция, вычисляющая расстояние (измеряющее степень непохожести) между объектами $\mathbf{x}$ и $\mathbf{z}$, а $y_1,y_2,...y_K$ - значения откликов на объектах $\mathbf{z}_1,\mathbf{z}_2,...\mathbf{z}_K$.

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

Базовое предположение метода

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

Недостатком метода является сложный способ вычисления прогноза, если используется большой набор референсных объектов $\mathbf{z}_1,\mathbf{z}_2,...\mathbf{z}_K$.

Достоинством метода является его обобщаемость на любую функцию расстояния. Варьируя способ вычисления расстояния между объектами $\rho(\mathbf{x},\mathbf{z})$, мы будем получать различные версии одного и того же метода!

Рассмотрим для примера две задачи с одинаковыми входными данными:

• по фото человека определить, кто именно на нём изображён (независимо от позы);

• по фото человека определить его позу (независимо от того, кого фотографировали).

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

Более того, функцию расстояния можно параметризовать некоторым вектором параметров $\mathbf{\theta}$:

$$\rho(\mathbf{x},\mathbf{z})\to\rho_\mathbf{\theta}(\mathbf{x},\mathbf{z}),$$

а дальше настраивать вид расстояния, который больше всего подходит под нашу задачу, что известно как обучение расстояния (metric learning). Существуют различные подходы обучения расстояний и даже специализированная python-бибилотека, которая их реализует [1].

Применимость методов

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

Если же мы определим функцию расстояния над исходным представлением объектов (а не сокращенным в виде вектора признаков), то сможем избежать потери информации, поскольку прогноз будет зависеть только от попарных расстояний между объектами. Например, мы можем определить расстояние между строками произвольной длины как минимальное число вставок/удалений и замен одного символа другим, необходимых для перевода одной строки в другую - так называемое редакторское расстояние или расстояние Левенштейна (edit distance, Levenstein distance - [2], [3]). Его можно определить и для графов произвольного размера, а также для других типов данных.

Литература

1. Документация metric-learn.

2. Wikipedia: Levenshtein distance.

3. Левенштейн В. И. Двоичные коды с исправлением выпадений, вставок и замещений символов //Доклады Академии наук. – Российская академия наук, 1965. – Т. 163. – №. 4. – С. 845-848.