Word Mover’s Distance (WMD) предлагается для измерения расстояния между двумя документами (или предложениями). Он использует возможности Word Embeddings для преодоления этих основных ограничений измерения расстояния.

ОМП [1] был представлен Kusner et al. в 2015 году. Вместо использования Евклидова расстояния и другого набора слов для измерения расстояния они предложили использовать вложения слов для вычисления сходства. Если быть точным, он использует нормализованные Пакет слов и Вложения слов для вычисления расстояния между документами.

Прочитав эту статью, вы поймете:

  • Дальность перемещения земли (EMD)
  • Расстояние переносчика слов (WMD)
  • Расслабленное расстояние перемещения слова (RWMD)
  • Внедрение ОМУ
  • Забрать

Дальность перемещения земли (EMD)

Прежде чем представить ОМУ, я должен сначала поделиться идеей Дистанции движения Земли (EMD), потому что основная часть ОМУ - это EMD.

EMD [2] решает транспортную задачу. Например, у нас есть m и n, а m и n обозначают набор поставщиков и складов. Задача состоит в том, чтобы минимизировать транспортные расходы, чтобы все товары были доставлены от m до n. Учитывая, что есть ограничения:

  • Только разрешить транспорт от m до n. Запрещается транспорт от п до м
  • Общее количество отправляемых грузов не может превышать общую вместимость м.
  • Общее количество принимаемых грузов не может превышать общую вместимость n.
  • Максимальное количество перевозок - это минимум между общим количеством грузов в m и общим количеством грузов в n.

Обозначения:

  • p: набор происхождения
  • q: набор пункта назначения
  • f (i, j): поток от i к j
  • m: Номер происхождения
  • n: номер пункта назначения
  • w (i, j): Количество грузовых транспортных средств от i до j.

Для оптимального потока F линейная формула имеет вид

Расстояние переносчика слов (WMD)

В предыдущем блоге я поделился, как можно простым способом найти сходство между двумя документами (или предложениями). В то время вводятся евклидово расстояние, косинусное расстояние и подобие Жаккара, но они имеют некоторые ограничения. ОМУ предназначено для решения проблемы синонимов.

Типичный пример:

  • Приговор 1: Обама разговаривает со СМИ в Иллинойсе
  • Приговор 2: Президент приветствует прессу в Чикаго

За исключением стоп-слов, в двух предложениях нет общих слов, но оба они относятся к одной и той же теме (в то время).

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

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

  • Приговор 1: Обама говорит СМИ Иллинойс
  • Приговор 2: президент приветствует прессу чикаго

Извлекайте векторы из любых предварительно обученных моделей встраивания слов. Это может быть GloVe, word2vec, fasttext или пользовательские векторы. После этого он использует нормализованный набор слов (nBOW) для представления веса или важности. Предполагается, что более высокая частота означает, что она более важна.

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

Расслабленное расстояние перемещения слова (RWMD)

Лучшее среднее время решения WMD составляет около O (p³ log p), а p - это номер уникального слова. Это немного медленнее, поэтому есть два подхода к сокращению времени вычислений. Первый - Word Centroid Distance (WCD), который суммирует расстояние до нижней границы между ними. Второй подход - это Расслабленное расстояние перемещения слов (RWMD), которое использует расстояние до шкафа без учета того, что несколько слов преобразуются в отдельные слова.

Возьмем для примера предыдущее предложение. Предполагая, что самым коротким словом в предложении из всех слов в предложении 1 является «президент», он будет использовать суммировать эти баллы вместо того, чтобы объединять их по одному. Так что временная сложность уменьшится до O (p²).

Внедрение ОМУ

Используя gensim, нам нужно предоставить только два списка токенов, после чего потребуется остальная часть вычислений.

subject_headline = news_headlines[0]
subject_token = headline_tokens[0]
print('Headline: ', subject_headline)
print('=' * 50)
print()
for token, headline in zip(headline_tokens, news_headlines):
    print('-' * 50)
    print('Comparing to:', headline)
    distance = glove_model.wmdistance(subject_token, token)
    print('distance = %.4f' % distance)

Выход

Headline:  Elon Musk's Boring Co to build high-speed airport link in Chicago
==================================================

--------------------------------------------------
Comparing to: Elon Musk's Boring Co to build high-speed airport link in Chicago
distance = 0.0000
--------------------------------------------------
Comparing to: Elon Musk's Boring Company to build high-speed Chicago airport link
distance = 0.3589
--------------------------------------------------
Comparing to: Elon Musk’s Boring Company approved to build high-speed transit between downtown Chicago and O’Hare Airport
distance = 1.9456
--------------------------------------------------
Comparing to: Both apple and orange are fruit
distance = 5.4350

В реализации gensim OOV будет удален, поэтому он не будет генерировать исключение или использовать случайный вектор.

Забрать

Исходный код можно найти в моем репозитории github.

  • Преимущество WMD - отсутствие гиперпараметров и преодоление проблемы синонимов.
  • Как и эти простые подходы, WMD не рассматривает заказы.
  • Временная сложность - это проблема. Исходная версия - O (p³ log p), а расширенная версия - O (p²).
  • Предварительно подготовленные векторы могут применяться не ко всем сценариям.

Обо мне

Я специалист по анализу данных в Bay Area. Сосредоточение внимания на новейших достижениях науки о данных, искусственного интеллекта, особенно в области НЛП и связанных с платформами. Вы можете связаться со мной из Medium Blog, LinkedIn или Github.

Ссылка

[1] Куснер Мэтт Дж., Сунь Ю., Колкин Николас И., Вайнбергер Килиан К. От вкраплений слов к расстоянию до документов. 2015. http://proceedings.mlr.press/v37/kusnerb15.pdf

[2] Теория EMD: https://en.wikipedia.org/wiki/Earth_mover%27s_distance