Меню
Публикации
2025
2024
2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
Главный редактор
НИКИФОРОВ
Владимир Олегович
д.т.н., профессор
Партнеры
doi: 10.17586/2226-1494-2025-25-1-61-67
УДК 004.89
Эффективный разреженный поиск с помощью построения инвертированного индекса на основе эмбеддингов
Читать статью полностью
Язык статьи - английский
Ссылка для цитирования:
Аннотация
Ссылка для цитирования:
Добрынин В.Ю., Абрамович Р.К., Платонов А.В. Эффективный разреженный поиск с помощью построения инвертированного индекса на основе эмбеддингов // Научно-технический вестник информационных технологий, механики и оптики. 2025. Т. 25, № 1. С. 61–67 (на англ. яз.). doi: 10.17586/2226-1494-2025-25-1-61-67
Аннотация
Введение. Современные поисковые системы используют двухэтапную архитектуру для эффективного и качественного поиска по большим объемам данных. На первом этапе применяются простые и быстрые алгоритмы, такие как BM25, а на втором — более точные, но ресурсоемкие методы, например глубокие нейронные сети. Несмотря на то, что такой подход показывает хорошие результаты, он фундаментально ограничен по качеству из-за проблемы несовпадения словарей, что присуще простым алгоритмам первого этапа. Метод. Для решения проблемы ограничений качества поиска, в настоящей работе предлагается алгоритм построения инвертированного индекса с использованием векторных представлений. Представленный подход объединяет преимущества обоих этапов: эффективность инвертированного индекса и высокое качество поиска при использовании векторных моделей. Предложено создание векторного индекса, сохраняющего различные семантические значения токенов словаря. Для каждого токена определяются документы, в которых он используется, после чего его контекстуализированные эмбеддинги кластеризуются. Центроиды полученных кластеров представляют различные семантические значения токенов. Таким образом, формируется расширенный словарь, который применяется для построения инвертированного индекса. При построении индекса вычисляются оценки близости между каждым семантическим значением токена и документами, что затем используется в процессе поиска. Это позволяет сократить количество вычислений для оценки близости в режиме реального времени. Поиск по инвертированному индексу требует нахождения ключей в векторном индексе, что позволяет решить проблему несовпадения словарей. Основные результаты. Работа алгоритма продемонстрирована на задаче поиска в наборе данных SciFact. Показано, что предлагаемый метод обеспечивает высокое качество поиска при низких требованиях к объему памяти. Обсуждение. Разработанный алгоритм демонстрирует высокое качество поиска, при этом он поддерживает компактный векторный индекс, размер которого остается неизменным и определяется исключительно размерами словаря. Основным недостатком алгоритма является необходимость использования глубокой нейронной сети для генерации векторных представлений запроса в процессе поиска, что замедляет этот этап. Поиск путей для решения данной проблемы и сокращения времени поиска представляет собой направление дальнейших исследований.
Ключевые слова: инвертированный индекс, проблема несоответствия словарей, нейронные сети, векторные представления, кластеризация
Список литературы
Список литературы
- Khattab O., Zaharia M. ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT // Proc. of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval. 2020. P. 39–48. https://doi.org/10.1145/3397271.3401075
- Zamani H., Dehghani M., Croft W.B., Learned-Miller E., Kamps J. From neural re-ranking to neural ranking: Learning a sparse representation for inverted indexing // Proc. of the 27th ACM International Conference on Information and Knowledge Management. 2018. P. 497–506. https://doi.org/10.1145/3269206.3271800
- Bai Y., Li X., Wang G., Zhang C., Shang L., Xu J., Wang Z., Wang F., Liu Q. SparTerm: Learning term-based sparse representation for fast text retrieval // arXiv. 2020. arXiv:2010.00768. https://doi.org/10.48550/arXiv.2010.00768
- Devlin J., Chang M.W., Lee K., Toutanova K. BERT: Pre-training of deep bidirectional transformers for language understanding // arXiv. 2018. arXiv:1810.04805v2. https://doi.org/10.48550/arXiv.1810.04805
- Formal T., Piwowarski B., Clinchant S. SPLADE: Sparse lexical and expansion model for first stage ranking // Proc. of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval. 2021. P. 2288–2292. https://doi.org/10.1145/3404835.3463098
- Santhanam K., Khattab O., Saad-Falcon J., Potts C., Zaharia M. ColBERTv2: Effective and efficient retrieval via lightweight late interaction // Proc. of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. 2022. P. 3715–3734. https://doi.org/10.18653/v1/2022.naacl-main.272
- Johnson J., Douze M., Jégou H. Billion-scale similarity search with GPUs // IEEE Transactions on Big Data. 2021. V. 7. N 3. P. 535–547. https://doi.org/10.1109/tbdata.2019.2921572
- Jégou H., Douze M., Schmid C. Product quantization for nearest neighbor search // IEEE Transactions on Pattern Analysis and Machine Intelligence. 2011. V. 33. N 1. P. 117–128. https://doi.org/10.1109/tpami.2010.57
- Kong W., Dudek J.M., Li C., Zhang M., Bendersky M. SparseEmbed: Learning sparse lexical representations with contextual embeddings for retrieval // Proc. of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval. 2023. P. 2399–2403. https://doi.org/10.1145/3539618.3592065
- Tiancheng Z., Lu X., Lee K. SPARTA: Efficient Open-Domain Question Answering via Sparse Transformer Matching Retrieval // Proc. of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. 2021. P. 565–575. https://doi.org/10.18653/v1/2021.naacl-main.47
- Dobrynin V., Abramovich R., Platonov A. Building a full-text search index using ”Transformer” neural network // Proc. of the 2023 IEEE 17th International Conference on Application of Information and Communication Technologies (AICT). 2023. P. 1–5. https://doi.org/10.1109/aict59525.2023.10313200
- Malkov Y.A., Yashunin D.A. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs // IEEE Transactions on Pattern Analysis and Machine Intelligence. 2020. V. 42. N 4. P. 824–836. https://doi.org/10.1109/tpami.2018.2889473
- Arthur D., Vassilvitskii S. k-means++: the advantages of careful seeding // Proc. of the 18th ACM-SIAM Symposium on Discrete Algorithms Mathematics. 2007. P. 1027–1035.
- Bajaj P., Campos D., Craswell N., Deng L., Gao J., Liu X., Majumder R., McNamara A., Mitra B., Nguyen T., Rosenberg M., Song X., Stoica A, Tiwary S., Wang T. MS MARCO: a human generated MAchine Reading COmprehension dataset // arXiv. 2016. arXiv:1611.09268. https://doi.org/10.48550/arXiv.1611.09268
- Thakur N., Nils R., Rücklé A., Srivastava A., Gurevych I. BEIR: A heterogenous benchmark for zero-shot evaluation of information retrieval models // arXiv. 2021. arXiv:2104.08663. https://doi.org/10.48550/arXiv.2104.08663
