Många informationssystem använder taggar och nyckelord för att beskriva och kommentera innehåll. Dessa möjliggör effektiv organisation och kategorisering av objekt, samt underlättar relevanta sökningar. Som sådan kan den valda uppsättningen taggar för ett objekt ha en betydande effekt på den trafikvolym som så småningom når ett objekt. I inställningar där taggar väljs av ett objekts skapare, som i sin tur är intresserad av att maximera trafiken, kan ett principfast tillvägagångssätt för att välja taggar visa sig värdefullt. I det här dokumentet introducerar vi problemet med optimal taggning, där uppgiften är att välja en undergrupp av taggar för ett nytt objekt så att sannolikheten för att en surfare når det objektet maximeras. Vi formulerar problemet genom att modellera trafiken med hjälp av en Markov kedja, och frågar hur övergångar i denna kedja bör ändras för att maximera trafiken till ett visst läge av intresse. Det resulterande optimeringsproblemet innebär att maximera en viss funktion över undergrupper, under en kardinalitet begränsning. Vi visar att optimeringsproblemet är NP-hård, men ändå har en enkel (1 − 1 e )-uppskattning via en enkel girig algoritm. Dessutom möjliggör problemets struktur ett effektivt genomförande av det giriga steget. För att visa hur effektiv vår metod är utför vi experiment på tre taggade datauppsättningar, och visar att den giriga algoritmen överträffar andra baslinjer.
Arbetet mest relaterade till vårt är den optimala taggning problem REF, där målet är att välja en delmängd av taggar för ett objekt så att sannolikheten för att en användare når objektet maximeras.
Optimal Tagging with Markov Chain Optimization
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}