Максимальный поиск внутреннего продукта

Поиск максимального внутреннего продукта ( MIPS ) — это задача поиска с соответствующим классом алгоритмов поиска , которые пытаются максимизировать внутренний продукт между запросом и элементами данных, которые необходимо получить. Алгоритмы MIPS используются в самых разных приложениях для работы с большими данными, включая алгоритмы рекомендаций и машинное обучение . ^{[ 1 ]}

Формально для базы данных векторов $x_{i}$ определяется набором меток $S$ во внутреннем пространстве продукта с внутренним продуктом $\langle \cdot ,\cdot \rangle$ определенный на нем, MIPS-поиск можно определить как задачу определения

{\underset {i\in S}{\operatorname {arg\,max} }}\ \langle x_{i},q\rangle

по заданному запросу $q$ .

Хотя существует очевидная реализация с линейным временем , она, как правило, слишком медленна, чтобы ее можно было использовать для решения практических задач. Однако существуют эффективные алгоритмы для ускорения поиска MIPS. ^{[ 1 ]}^{[ 2 ]}

При предположении, что все векторы в наборе имеют постоянную норму, MIPS можно рассматривать как эквивалент задачи поиска ближайшего соседа (NNS), в которой максимизация внутреннего продукта эквивалентна минимизации соответствующей метрики расстояния в задаче NNS. ^{[ 3 ]} Как и другие формы NNS, алгоритмы MIPS могут быть приблизительными или точными. ^{[ 4 ]}

Поиск MIPS используется как часть DeepMind компании алгоритма RETRO . ^{[ 5 ]}

Ссылки

^ Перейти обратно: ^а ^б Абузейд, Фирас; Сетхи, Гит; Бейлис, Питер; Захария, Матей (14 марта 2019 г.). «Индексировать или не индексировать: точная максимальная оптимизация поиска внутреннего продукта». arXiv : 1706.01449 [ cs.IR ].
^ Стив Муссманн, Стефано Эрмон. Обучение и вывод посредством максимального поиска внутреннего продукта. В Proc. 33-я Международная конференция по машинному обучению (ICML), 2016 г.
^ Шривастава, Аншумали; Ли, Пин (12 июля 2015 г.). «Улучшенное асимметричное хеширование с учетом местоположения (ALSH) для максимального внутреннего поиска продукта (MIPS)» . Материалы тридцать первой конференции по неопределенности в искусственном интеллекте . УАИ'15. Арлингтон, Вирджиния, США: AUAI Press: 812–821. arXiv : 1410.5410 . ISBN 978-0-9966431-0-8 .
^ Кейвани, Омид; Синха, Кошик; Рам, Парикшит (май 2017 г.). «Улучшенный поиск максимального внутреннего продукта с лучшими теоретическими гарантиями» . Международная совместная конференция по нейронным сетям 2017 (IJCNN) . стр. 2927–2934. doi : 10.1109/IJCNN.2017.7966218 . ISBN 978-1-5090-6182-2 . S2CID 8352165 .
^ «РЕТРО невероятно быстро» . Митчелл А. Гордон . 01.07.2022 . Проверено 4 июля 2022 г.

См. также

Поиск ближайшего соседа

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

[Abuzaid-1] Перейти обратно: ^а ^б Абузейд, Фирас; Сетхи, Гит; Бейлис, Питер; Захария, Матей (14 марта 2019 г.). «Индексировать или не индексировать: точная максимальная оптимизация поиска внутреннего продукта». arXiv : 1706.01449 [ cs.IR ].

[2] Стив Муссманн, Стефано Эрмон. Обучение и вывод посредством максимального поиска внутреннего продукта. В Proc. 33-я Международная конференция по машинному обучению (ICML), 2016 г.

[3] Шривастава, Аншумали; Ли, Пин (12 июля 2015 г.). «Улучшенное асимметричное хеширование с учетом местоположения (ALSH) для максимального внутреннего поиска продукта (MIPS)» . Материалы тридцать первой конференции по неопределенности в искусственном интеллекте . УАИ'15. Арлингтон, Вирджиния, США: AUAI Press: 812–821. arXiv : 1410.5410 . ISBN 978-0-9966431-0-8 .

[4] Кейвани, Омид; Синха, Кошик; Рам, Парикшит (май 2017 г.). «Улучшенный поиск максимального внутреннего продукта с лучшими теоретическими гарантиями» . Международная совместная конференция по нейронным сетям 2017 (IJCNN) . стр. 2927–2934. doi : 10.1109/IJCNN.2017.7966218 . ISBN 978-1-5090-6182-2 . S2CID 8352165 .

[5] «РЕТРО невероятно быстро» . Митчелл А. Гордон . 01.07.2022 . Проверено 4 июля 2022 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]