Búsqueda máxima de productos internos

Problema de búsqueda

La búsqueda de producto interno máximo ( MIPS ) es un problema de búsqueda , con una clase correspondiente de algoritmos de búsqueda que intentan maximizar el producto interno entre una consulta y los elementos de datos que se van a recuperar. Los algoritmos MIPS se utilizan en una amplia variedad de aplicaciones de big data, incluidos algoritmos de recomendación y aprendizaje automático . ^[1]

Formalmente, para una base de datos de vectores definidos sobre un conjunto de etiquetas en un espacio de producto interno con un producto interno definido en él, la búsqueda MIPS se puede definir como el problema de determinar ${\displaystyle x_{i}}$ ${\displaystyle S}$ ${\displaystyle \langle \cdot ,\cdot \rangle }$

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

para una consulta determinada . ${\displaystyle q}$

Aunque existe una implementación lineal obvia , generalmente es demasiado lenta para ser utilizada en problemas prácticos. Sin embargo, existen algoritmos eficientes para acelerar la búsqueda MIPS. ^{[1] [2]}

Suponiendo que todos los vectores del conjunto tienen una norma constante, los MIPS pueden considerarse equivalentes a un problema de búsqueda del vecino más cercano (NNS) en el que maximizar el producto interno es equivalente a minimizar la métrica de distancia correspondiente en el problema NNS. ^[3] Al igual que otras formas de NNS, los algoritmos MIPS pueden ser aproximados o exactos. ^[4]

La búsqueda MIPS se utiliza como parte del algoritmo RETRO de DeepMind . ^[5]

Referencias

1. Abuzaid, Firas; Sethi, Geet; Bailis, Peter; Zaharia, Matei (14 de marzo de 2019). "Indexar o no indexar: optimización de la búsqueda interna de productos con la máxima exactitud". arXiv : 1706.01449 [cs.IR].
2. Steve Mussmann, Stefano Ermon. Aprendizaje e inferencia mediante búsqueda máxima de producto interno. En Proc. 33.ª Conferencia internacional sobre aprendizaje automático (ICML), 2016.
3. Shrivastava, Anshumali; Li, Ping (12 de julio de 2015). "Mejora del algoritmo hash asimétrico sensible a la localidad (ALSH) para la búsqueda máxima de producto interno (MIPS)". Actas de la 31.ª conferencia sobre incertidumbre en inteligencia artificial . UAI'15. Arlington, Virginia, EE. UU.: AUAI Press: 812–821. arXiv : 1410.5410 . ISBN. 978-0-9966431-0-8.
4. Keivani, Omid; Sinha, Kaushik; Ram, Parikshit (mayo de 2017). "Búsqueda de producto interno máximo mejorada con mejores garantías teóricas". Conferencia conjunta internacional sobre redes neuronales (IJCNN) de 2017. págs. 2927–2934. doi :10.1109/IJCNN.2017.7966218. ISBN 978-1-5090-6182-2.S2CID8352165  .​
5. "RETRO es increíblemente rápido". Mitchell A. Gordon . 2022-07-01 . Consultado el 2022-07-04 .

Véase también

• Búsqueda de vecino más cercano