Что это?
Хеширование с учетом местоположения — это процесс распределения элементов (на практике точек данных) по разным корзинам. Элементы или точки данных, похожие друг на друга, помещаются в одно и то же ведро.
В контексте НЛП это делается с помощью встраивания слов или документов. Слова или документы, похожие друг на друга, будут иметь векторное представление, хэшированное до одного и того же значения.
Почему это полезно?
Хеширование с учетом местоположения полезно для повышения эффективности поиска слов или документов, похожих друг на друга.
Если мы хотим найти 5 слов, наиболее похожих на слово «кошка», хеширование с учетом местоположения может значительно ускорить этот поиск. Вместо того, чтобы сравнивать вложение каждого слова с вложением слова «кошка», хеширование с учетом местоположения можно использовать только для проверки подмножества вложений слов, которые имеют то же хеш-значение, что и вложение слова «кошка».
Как это делается?
Как определить сходство векторов?
Чтобы сгруппировать похожие векторы в одно и то же ведро, необходимо определить метрику подобия, чтобы получить оценку того, насколько два вектора похожи друг на друга. Общепринятой метрикой подобия является евклидово расстояние. Евклидово расстояние d — это кратчайший путь из одной точки векторного пространства в другую:
Вы можете вспомнить теорему Пифагора, которую можно использовать для вычисления евклидова расстояния между двумя точками: a2 + b2 = c2
Как эта метрика сходства/расстояния используется для хеширования с учетом местоположения?
Евклидово расстояние можно обобщить до векторной нормы L2, которая для любого вектора обеспечивает расстояние от начала координат. Норма L2 может быть рассчитана следующим образом для вектора любой длины/размерности.
Дан вектор длины n:
Норма L2 — это квадратный корень из суммы квадратов каждого элемента:
Чтобы хэшировать похожие векторы в одно и то же ведро, мы хотим объединить только те векторы, между которыми имеется относительно небольшое евклидово расстояние.
Для этого векторное пространство делится на произвольное количество областей путем создания ряда гиперплоскостей.
Затем векторы, лежащие в одной области, хэшируются в одно и то же ведро.
Как определить, что вектор находится в одной области по сравнению с другой?
Чтобы определить, в какой области находится вектор, для каждой сгенерированной гиперплоскости определяется, на какой стороне гиперплоскости лежит вектор. Для вектора это приводит к списку значений +1 или -1, которые указывают сторону каждой гиперплоскости, на которой лежит вектор. Любые векторы с одинаковой комбинацией значений +1 и -1 находятся в одной области.
Учитывая вектор и гиперплоскость, как определить, находится ли он на положительной (+1) или отрицательной (-1) стороне?
Каждая гиперплоскость может быть представлена одним вектором. Вычисляется скалярное произведение вектора и вектора, представляющего гиперплоскость. Если скалярное произведение положительное, мы присваиваем вектор стороне +1, если скалярное произведение отрицательное, мы присваиваем вектор стороне -1.
Как создаются гиперплоскости?
Поскольку гиперплоскости могут быть представлены в виде одного вектора, серия векторов генерируется и используется случайным образом. Обычно это делается много раз, и используются серии случайных векторов с лучшими результатами.
