Soft Cosine Measure: Capturing Term Similarity in the Bag of Words VSM

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F19%3A00109518" target="_blank" >RIV/00216224:14330/19:00109518 - isvavai.cz</a>

Výsledek na webu

<a href="https://mir.fi.muni.cz/ml-prague-2019/#soft-cosine-measure" target="_blank" >https://mir.fi.muni.cz/ml-prague-2019/#soft-cosine-measure</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Soft Cosine Measure: Capturing Term Similarity in the Bag of Words VSM

Popis výsledku v původním jazyce

<p>Our work is a scientific poster that was presented at the ML Prague 2019 conference during February 22–24, 2019.</p> <p>The standard bag-of-words vector space model (VSM) is efficient, and ubiquitous in information retrieval, but it underestimates the similarity of documents with the same meaning, but different terminology. To overcome this limitation, <a href="http://www.scielo.org.mx/pdf/cys/v18n3/v18n3a7.pdf">Sidorov et al. (2014)</a> proposed the Soft Cosine Measure (SCM) that incorporates term similarity relations. <a href="http://www.aclweb.org/anthology/S17-2051">Charlet and Damnati (2017)</a> showed that the SCM using word embedding similarity is highly effective in question answering systems. However, the orthonormalization algorithm proposed by Sidorov et al. has an impractical time complexity of O(n^4), where n is the size of the vocabulary. </p> <p>In our work, we prove a tighter lower worst-case time complexity bound of O(n^3). We also present an algorithm for computing the similarity between documents and we show that its worst-case time complexity is O(1) given realistic conditions. Lastly, we describe implementation in general-purpose vector databases such as Annoy, and Faiss and in the inverted indices of text search engines such as Apache Lucene, and ElasticSearch. Our results enable the deployment of the SCM in real-world information retrieval systems.</p>

Název v anglickém jazyce

Soft Cosine Measure: Capturing Term Similarity in the Bag of Words VSM

Popis výsledku anglicky

<p>Our work is a scientific poster that was presented at the ML Prague 2019 conference during February 22–24, 2019.</p> <p>The standard bag-of-words vector space model (VSM) is efficient, and ubiquitous in information retrieval, but it underestimates the similarity of documents with the same meaning, but different terminology. To overcome this limitation, <a href="http://www.scielo.org.mx/pdf/cys/v18n3/v18n3a7.pdf">Sidorov et al. (2014)</a> proposed the Soft Cosine Measure (SCM) that incorporates term similarity relations. <a href="http://www.aclweb.org/anthology/S17-2051">Charlet and Damnati (2017)</a> showed that the SCM using word embedding similarity is highly effective in question answering systems. However, the orthonormalization algorithm proposed by Sidorov et al. has an impractical time complexity of O(n^4), where n is the size of the vocabulary. </p> <p>In our work, we prove a tighter lower worst-case time complexity bound of O(n^3). We also present an algorithm for computing the similarity between documents and we show that its worst-case time complexity is O(1) given realistic conditions. Lastly, we describe implementation in general-purpose vector databases such as Annoy, and Faiss and in the inverted indices of text search engines such as Apache Lucene, and ElasticSearch. Our results enable the deployment of the SCM in real-world information retrieval systems.</p>

Druh

O - Ostatní výsledky

CEP obor

—

OECD FORD obor

10200 - Computer and information sciences

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2019

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů