textbot

При работе с векторными представлениями (ВП) часто возникают проблемы с вычислительной и емкостной сложность выполения базовых операций в пространстве ВП, в частности поиска ближайших соседей. Использование классических подходов требует сравнить искомый вектор с каждым из известных векторов, мощность множества которых весьма велика (в нашем случае 1 млн.). Использование косинусной метрики или евклидова расстояния позволяют нам довольно-таки быстро осуществлять поиск ближайших соседей, однако объем затрачиваемой при этом памяти крайне велик, что приводит к зависанию обычных клиентских машин, будь-то персональных компьютеров или мобильных устройств. Так, координаты 1 млн. точек в 300-мерном пространстве занимают по крайней мере 1.2GB памяти. На выручку приходят алгоритмы сжатия ВП, позволяющие уменьшить данный объем по крайней мере в 16 раз (т.е. до 75MB). Однако классический поиск ближайших соседей на сжатых векторах не предоставляется возможным, так как для этого нам потребуется последовательно разжать каждый из 1 млн. известных векторов и сравнить его с искомым. Для разрешения данной проблемы мы воспользуемся так называемыми ячейками Вороного, позволяющими проиндексировать пространство ВП последовательным разделением его на области поиска.

В основу алгоритма индексации пространства ВП положен классический метод k-средних, используемый нами в том числе для сжатия ВП. Алгоритм предполагает использование двух гиперпараметров: мощности множества кластеров (областей поиска) ListClusterSize и коэффициента повторной кластеризации Parameter. При использовании метода быстрого поиска k-средних (MiniBatchKMeans) добавляется третий гиперпараметр: размер бетча (BatchSize). Отметим, что, пожалуй, это редкий случай, когда использование метода MiniBatchKMeans может существенно понизить качество кластеризации ввиду того, что мы переходим от 300-мерного пространства к 1-мерному. Однако, некоторым преимуществом использования данного метода является его скорость. Получив необходимое число кластеров (в нашем случае 100), мы разбили пространство ВП на 100 областей, каждая из которых обладает собственным центроидом. Тогда множество векторов каждой области является ячейкой Вороного относительно своего центроида. Нам бы хотелось, чтобы в каждую область попало по 10000 ВП или что-то около того, однако, в каждой из областей было от 100 до 66000 ВП. Именно здесь нам понадобится коэффициент повторной кластеризации.

Коэффициент повторной кластеризации позволяет оценить, насколько большое число векторов попало в тот или иной кластер (область поиска). Если число векторов в кластере превышает произведение ListClusterSize на Parameter, то данному кластеру предстоит повторное разбиение на ListClusterSize подкластеров. Кластеры с меньшим числом векторов останутся как есть. Именно поэтому такую кластеризацию назвали асимметрической. Проведя разбиение “больших” кластеров на подкластеры, мы получили по центроиду для каждого из них и, соответственно сформировали подобласти поиска и алгоритм индексации пространства ВП завершен. Стоит добавить, что, в случае необходимости, т.е. если и в подкластере окажется слишком мног точек, каждый подкластер можно вновь разбить на подподкластеры и т.д.

Поскольку индексация завершена, можно переходить непосредственно к алгоритму быстрого поиска. Если при классическом поиске вычислительная сложность расчитывалась исходя их мощности множества векторов в пространстве ВП (1 млн. в нашем случае), то теперь при быстром поиске она в целом зависит только от значения ListClusterSize. Покажем это. Итак, пусть у нас есть некоторый вектор CurrentWE, для которого необходимо найти ближайших соседей.

Шаг 1. Сравним CurrentWE с каждым из ListClusterSize центроидов. (Итого: 100 сравнений.)

Шаг 2. Выберем 2 наиболее близких центроида.

Шаг 3. Для каждого из 2-х выбранных центроидов посмотрим, есть ли у его кластера подкластеры. Если нет, то выберем 2 наиболее близких вектора к CurrentWE. Если да, то сравним CurrentWE с каждым из ListClusterSize центроидов его подкластеров. И так далее Шаг 3. (Итого: в худшем случае (если есть подкластеры у обоих кластеров) 200 сравнений. Плюс в каждом из выбранных подкластеров в среднем по 100 сравнений (всего 400). Итого имеем 700 сравнений вместо 1000000.)