Томилов Никита Андреевич — аспирант.
Санкт-Петербург, 197101, sc 57225127284
Nikita A. Tomilov — PhD Student.
Saint Petersburg, 197101, sc 57225127284
Туров Владимир Павлович — аспирант.Санкт-Петербург, 197101, sc 58910796700
Vladimir P. Turov — PhD Student.
Saint Petersburg, 197101, sc 58910796700
Бабаянц Александр Амаякович — аспирант.Санкт-Петербург, 197101, sc 58910002300
Alexander A. Babayants — PhD Student.
Saint Petersburg, 197101, sc 58910002300
Платонов Алексей Владимирович — кандидат технических наук, доцент, доцент.Санкт-Петербург, 197101, sc 57197736275
Alexey V. Platonov — PhD, Associate Professor, Associate Professor.
Saint Petersburg, 197101, sc 57197736275
Введение. Информационный поиск с использованием алгоритмов машинного обучения основывается на преобразовании исходных мультимодальных документов в векторные представления, далее строится индекс векторных представлений и производится поиск внутри индекса. Популярным способом построения индекса является кластеризация векторных представлений, например с помощью k-ближайших соседей. В работе предложен метод кластеризации с помощью ансамбля небрежных решающих деревьев, а также алгоритм векторного поиска на основе этого метода. Разработанный метод кластеризации является детерминированным и предоставляет возможность сериализации параметров ансамбля.
Метод. Сущность метода состоит в обучении ансамбля двоичных или троичных небрежных решающих деревьев. Этот ансамбль используется для вычисления хэша для каждого из исходных векторных представлений. Векторные представления, имеющие одинаковый хэш, считаются принадлежащими к одному кластеру. Для поиска выбирается несколько кластеров, центроиды которых наиболее приближены к векторному представлению поискового запроса, после чего производится полный перебор векторных представлений выбранных кластеров. Основные результаты. Представленный метод показывает качество поиска, сравнимое с широко используемыми в индустрии библиотеками векторного поиска Faiss, Annoy и HNSWlib. Для протестированного набора данных с евклидовой метрикой расстояния предложенный метод поиска медленнее, чем существующие решения, но для протестированного набора данных с угловой метрикой расстояния результат сравним или лучше.
Обсуждение. Разработанный метод может быть применен для улучшения качества поиска при создании мультимодальных поисковых систем. Возможность сериализации позволяет кластеризовать данные на одном вычислительном узле и передавать параметры ансамбля на другой вычислительный узел, что дает возможность использовать предложенный алгоритм в распределенных системах.
Information retrieval using machine learning algorithms is based on transforming the original multimodal documents into vector representations. These vectors are then indexed, and the search is performed within this index. A popular method for indexing is vector clustering such as with k-nearest neighbors. We propose a clustering method based on an ensemble of Oblivious Decision Trees and introduce a vector search algorithm built on this method. The proposed clustering method is deterministic and supports parameter serialization for the ensemble. The essence of the method involves training an ensemble of binary or ternary Oblivious Trees. This ensemble is then used to compute a hash for each of the original vectors. Vectors with the same hash are considered to belong to the same cluster. For searching, several clusters are selected whose centroids are closest to the vector representation of the search query followed by a full search of the vector representations within the selected clusters. The proposed method demonstrates search quality comparable to widely used industry-standard vector search libraries, such as Faiss, Annoy, and HNSWlib. For datasets with an angular distance metric, the proposed search method achieves accuracy equal to or better than existing solutions. For datasets with a Euclidean distance metric, the search quality is on par with existing solutions. The developed method can be applied to improve search quality in the development of multimodal search systems. The ability to serialize enables clustering data on one computational node and transferring ensemble parameters to another, allowing the proposed algorithm to be utilized in distributed systems.
The authors declare that there are no conflicts of interest present.