Jak hledat podobné tweety moderně

+Josef Šlerka (mimochodem skvělý chlapík a Osobnost českého internetu) vydal před pár dny slajdy (http://www.slideshare.net/josefslerka/fingerprinting-42124415), jak fingerprintuje posty (zřejmě tweety a fb), aby našel ty "hodně podobné".
Já jsem se nechal na Twitteru slyšet (https://twitter.com/michalillich/status/538304531290157057), že tenhle způsob je zastaralý a lépe je to dělat pomocí slovních vektorů. A jelikož to vyvolalo dost vyhrocenou diskuzi, tak sepíšu rešení podrobně.

Problémem simhashe je zaměření na písmenka.

Co myslíte, je pro problém hledání podobných postů důležité, jak staří Římané seřadili písmenka v abecedě (a jak jsou v ASCII tabulce)? Podle simhashe je písmenko 'a' (01100001) mnohem podobnější 'c' (01100011) než třeba 'z' (01111010). Viz http://www.neurophys.wisc.edu/comp/docs/ascii/ascii-printable.html
A tahle pseudonáhodná písmenková podobnost se pak ještě znásobí na úrovni slov. Vznikne tak stav, že simhash některá slova považuje za podobná některým jiným stylem, který člověk vnímá jako náhodný.

Pokud vás právě napadlo, že "náhodnost je přece podstatou hashů!", tak máte pravdu. Obvykle hashujeme právě proto, abychom data rozprostřeli náhodně a například se tak vyhnuli kolizím. Ale pamatujete, že Josef chtěl najít posty, které jsou si "hodně podobné"? Dost zvláštní, že si jako první krok vybral metodu, která vytváří náhodnost.

Co ve skutečnosti potřebujeme

V prvém kroku potřebujeme pravý opak hashování! Chceme, aby se nám podobná slova dostala k sobě. A podobná myslím zejména na základě významu (a teprv sekundárně podle syntaxe či dokonce vnější podoby).
Naštěstí k tomu existují snadné metody. Tomáš Mikolov s kolegy představil před pár lety word2vec (http://papers.nips.cc/paper/5021-distributed-representations-of-words-and-phrases-and-their-compositionality.pdf), což je naprosto geniální věc.

Takže nejdřív si každé slovo převedete na jeho slovní vektor. Ty máte předpočítané, takže je to superrychlé. Slovní vektor je sada (obvykle stovek) čísel, která vyjadřují význam a syntaxi toho slova. Přičemž podobná slova mají podobné vektory.

Takže nejpodobnější ke slovu "cat" bude slovo "cats".
A ke slovu "pen" budou nejbližší postupně "pens", "pencil", "quill".
Pohrát si s vektory můžete zde:
http://radimrehurek.com/2014/02/word2vec-tutorial/

Mimochodem, potud jsme to ve Wikidi implementovali (pro tweety) a skutečně metody používající word2vec vyhrávaly v přesnosti (subjektivně i objektivně měřené) nad ostatními metodami (zaměřenými na vnější podobu jako u simhashe nebo používající třeba LDA).

Teď chceme navíc, aby to bylo rychlé. A možností máme hodně, uvedu dvě nejvýznamnější:

Rychlé hledání přes K-means clustering a index

Slova si předem podle slovních vektorů naclusterujeme do K clusterů (třeba 65536). Takže pak při hledání nepoužijeme jako reprezentaci slova jeho slovní vektor, ale jen krátký index, který má třeba 16 bitů.
Pak pro N-slovný tweet jen koukneme do N seznamů a spočítáme si, který post jsme v nich potkali nejvíckrát. Pokud máme v databázi M postů, tak je složitost O(N*(M*N/K)).
(a pomocí bloom filterů se to dá ještě zrychlit.)

Rychlé hledání pomocí bitového pole a ANN

Druhá možnost je převést si vektory na bity. Vytvoříme si vektor celého postu. Ideálně místo word2vec použijeme doc2vec (http://radimrehurek.com/gensim/models/doc2vec.html) nebo jestli chceme být punk, tak prostě zprůměrujeme vektory jednotlivých slov. To zní naprosto šíleně, ale z nějakého záhadného důvodu to funguje v praxi dost slušně.

Jak máme vektor postu, tak si jej můžeme kvůli snížení nákladů na uložení na disk zmenšit na bitové pole. Osobně bych asi dal dva bity na každou hodnotu (10 horní tercil, 00 prostřední tercil, 01 dolní tercil), ale jeden bit (nadprůměr/podprůměr) by mohl fungovat taky.

Pak použijeme approximate nearest neighbour search (například knihovnu https://github.com/spotify/annoy od Spotify), která bude pro tyhle data hledat odhadem stokrát rychleji než naivní lineární průchod.

Závěr

Všimněte si, že jsem nakonec hashování, indexování a podobné metody (které jsou součástí ANN) taky použil. Ale vtip je v tom, že je nepoužiju v první fázi (kde škodí), ale až v druhé fázi (kde pomáhají).
V prvé fázi naopak potřebuju prostředek, který mi podobná slova dostane k sobě a ne je hashováním rozstřelí pryč.

Výsledkem je postup, který je jednoduchý na implementaci (na vše výše zmíněné jsou kvalitní opensource knihovny), rychlý a usporný ve vyhledávání a věřím, že i mnohem přesnější.

Mimochodem, pokud jste to dočetli až sem, pojďte k nám pracovat:
http://www.jobs.cz/rpd/915013264/
Shared publiclyView activity