Bayesian tags

Door: Thijs Zumbrink
11-01-2012 00:35

Ik heb onlangs een tag-recommendation systeem gemaakt, dat mij voorstelt welke tags ik aan artikelen zal geven op basis van de inhoud. De werking is afgeleid van Bayesiaanse spamfilters.

Direct afgeleid van Bayes' theorem is deze vergelijking:

Deze simpele vergelijking stelt ons in staat om te achterhalen wat we willen weten, P(T|W), in termen van informatie die we al weten. De kansen voor bepaalde tags hebben we nu per woord, en worden samengevoegd tot de kans dat het hele bericht een bepaalde tag T behoeft. Als die kans boven 50% is dan wordt het voorgesteld aan de gebruiker, waarbij de hoogste kansen eerder genoemd worden.

Oppassen

Er zijn nog wel een aantal haken en ogen. Allereerst werkt dit systeem beter wanneer je woorden gaat negeren die weinig uitmaken voor een tagtoewijzing. Hele unieke woorden zullen tag-kansen van richting de 0% of 100% hebben, dus ik neem alleen de woorden waarbij de tag-kans zo ver mogelijk van 50% afligt. Bijvoorbeeld: in games artikelen komt het woord 'game-over' wellicht vaak voor. In niet-games artikelen komt het woord vrijwel nooit voor, dan gaat de kans P(T|W) richting de 100%. Andersom zal het woord 'duiken' minder voorkomen in artikelen over games dus dan gaat de kans richting 0%. Beide woorden dragen dus sterk bij aan de tagbepaling voor de games-tag. Kansen voor minder unieke woorden zullen dichter rond de 50% liggen en worden daarom genegeerd.

Verder kan de kans makkelijk 0% worden wanneer je nieuwe artikel een woord bevat dat nog nooit voorgekomen is in artikelen bij die tag. Neem gebruikelijke woordjes zoals 'omdat', die heel normaal zijn maar niet altijd gebruikt worden. P(W|T) is dan 0, en daarom wordt P(T|W) ook 0. Dat schopt de boel in de war omdat het programma dan overtuigd is dat het woord absoluut geen tag T verdient. Bij het combineren van alle kansen tot een samengestelde kans voor het hele artikel levert dat problemen. Daarom negeer ik die woorden tenzij ze heel erg vaak voorkomen in artikelen zonder tag T.

Daarnaast heb je voor dit systeem een hele grote verzameling artikelen nodig. Het aantal tags en woorden op deze blog zijn lang niet voldoende om het systeem heel vloeiend werkend te krijgen, maar het gaat natuurlijk om te spelen met de techniek! En met wat gesleutel aan de details kan ik de boel misschien zo manipuleren dat het op kleine schaal wel beter gaat werken.

Running time

Het indexeren van alle voorkomens van woorden in artikelen kost wel even. Elk artikel wordt ontleed en voor elke tag wordt elk woord geteld. Ik heb een beetje een naïeve implementatie waardoor het eigenlijk wel een stuk sneller kan, maar de tijd om dit te doen is momenteel rond de 3 seconden. Daarom doe ik dit allemaal eenmalig en sla ik al die data op in een bestand, de zogeheten TRDB: Tag Recommender DataBase. Het bestand is 1.6MiB groot momenteel. Het queryen van die database (tagkans bepalen voor een bepaald artikel) kost in de orde van tientallen milliseconden. De TRDB wordt simpelweg herbouwd na het publiceren van een artikel, hoewel ik het ook gewoon zou kunnen updaten met de nieuwe woordtellingen. Wederom, dat is een gevolg van mijn naïeve implementatie en is niet moeilijk te veranderen.

De grootte van de TRDB is O(|Woorden| * |Tags|) of ietwat simpeler: O(|Artikelen| * |Tags|) als we even aannemen dat alle artikelen ongeveer even lang zijn. De tijd om de TRDB te herbouwen zal daarom toenemen met het aantal artikelen en met het aantal tags, en op een gegeven moment wordt het wel nodig dat ik van mijn naïeve herbouw-manier afstap en met de update-manier verder ga. Maar dat stel ik voor nu nog even uit. :)