Dnešní díl seriálu naváže na předchozí motivační články a bude jako první z řady celý o sémantické analýze. Technika, kterou si dnes představíme se nazývá latentní sémantická analýza.
V předchozích článcích jsme se seznámili s vektorovými prostory pro reprezentaci textových dokumentů a představili si různé způsoby jejich zobrazení do těchto prostorů. Dále jsme si ukázali nejjednodušší způsoby snížení dimenzionality a zdůvodnili, proč je její snížení důležité.
Doposud jednotlivé dimenze odpovídaly slovům nebo shlukům slov se stejným základním tvarem. I přesto však zůstal počet dimenzí příliš vysoký. Techniky, které budou představeny v tomto a následujících článcích, jdou se shlukováním ještě dále. Dimenze zde spíše než slovům odpovídají takzvaným konceptům. Konceptem můžeme rozumět nějakou tématickou oblast, například technika, sport, kultura a podobně. Tyto koncepty však většinou nejsou vybírány ručně (neboť by byl jejich ruční výběr subjektivní a nereprezentativní), ale spíše automatickými metodami tak, aby co nejlépe korespondovaly s trénovacími daty. Jednotlivá slova potom nemusí patřit právě do jednoho shluku, ale typicky patří do více shluků s různými vahami. Například slovo „fotbal“ bude převážně spadat do konceptu „sport“, ale „vstupenka“ může stejnou měrou odpovídat konceptu „sport“ i konceptu „kultura“.
U automatických metod identifikace konceptů je klíčové předem učit jejich počet. Díky tomu lze nastavit granularitu konceptů. Pokud budou trénovací množinou obecné texty z různých oblastí a konceptů bude málo (řekněme 100), budou i výsledné koncepty obecné. Pokud však zvolíme počet konceptů desetkrát vyšší, obecné koncepty se nám rozbijí do jemnějších kategorií a např. místo konceptu „sport“ nám vzniknou koncepty jako „fotbal“, „hokej“, „tenis“ apod. Samozřejmě pokud trénovacími daty budou pouze sportovní texty, pro takovéto jemné členění nám bude stačit i 100 konceptů.
Pro vysvětlení latentní sémantické analýzy (LSA) se vraťme k příkladu z prvního dílu seriálu. Mějme kolekci tří dokumentů (pro zjednodušení je v každém dokumentu právě jedna věta):
- the man walked the dog
- the man took the dog to the park
- the dog went to the park
Jestliže vybereme všechna použitá slova a abecedně je seřadíme, dostaneme následující vektor slov:
[dog, man, park, the, to, took, walked, went]
Reprezentace dokumentů ve vektorovém prostoru frekvencí slov potom bude vypadat následovně:
- [1, 1, 0, 2, 0, 0, 1, 0]
- [1, 1, 1, 3, 1, 1, 0, 0]
- [1, 0, 1, 2, 1, 0, 0, 1]
Takový model však počítá pouze výskyty jednotlivých slov nezávisle na sobě. Latentní sémantická analýza oproti tomu pracuje i s informací o takzvaném souvýskytu dvou nebo více slov v dokumentu. Pokud se dvě slova vyskytují spolu ve stejných dokumentech častěji, než by odpovídalo náhodnému rozložení, jsou tato slova považována za sémanticky podobná. Například slova „fotbal“ a „sport“ se budou spolu v jednom dokumentu vyskytovat určitě častěji, než slova „fotbal“ a „kultura“. To je však jen souvýskyt první úrovně. Je dost možné, že se slova „fotbal“ a „tenis“ spolu na jedné stránce příliš často vyskytovat nebudou. Obě slova se však budou často vyskytovat se slovem „sport“. Díky tomu budou za sémanticky podobná považována i slova „fotbal“ a „tenis“. Tomu se říká souvýskyt druhé úrovně. Takových úrovní může být samozřejmě více, míra sémantické příbuznosti se však se stoupající úrovní souvýskytu snižuje.
Nyní se vraťme k našemu příkladu tří dokumentů. Pokud by dotazem bylo jediné slovo „walked“, měřeno cosinovou mírou by měl nenulovou podobnost s dotazem pouze dokument 1. Pokud však využijeme informace o souvýskytu, je vidět, že „walked“ je ve stejném dokumentu s „man“ a „man“ se v dokumentu 2 vyskytuje se slovem „took“. Stejný souvýskyt druhé úrovně platí i pro „walked“ – „dog“ – „took“. Díky tomu můžeme usuzovat, že slova „walked“ a „took“ by mohla mít podobný význam a podobnost dotazu „walked“ s dokumentem 2 bude tedy nenulová.
Latentní sémantická analýza je technika, která zobrazuje dokumenty a dotazy do prostoru latentních sémantických dimenzí, přičemž. slova, která jsou sémanticky podobná (měřeno mírou souvýskytů v dokumentech) jsou zobrazována do stejných dimenzí a slova sémanticky odlišná do různých dimenzí. Díky tomu mohou mít velkou sémantickou podobnost i dokumenty (případně dotaz a dokument), které spolu nesdílejí žádná slova.
Latentní sémantické dimenze odpovídají výše zmiňovaným konceptům, jsou však obtížně interpretovatelné. Jednou z možností, jak získat vhled do významu jednotlivých automaticky identifikovaných konceptů, je podívat se na slova, která jsou do daného konceptu (dimenze) zobrazována. Slova v LSA patří do jednotlivých konceptů s určitou vahou, pokud si tedy pro daný koncept vypíšeme slova s největší vahou, můžeme odhadnout, čemu daný koncept odpovídá. Např. dimenzi, která je reprezentovaná jako:
(1.5*„sport“ + 0.8*„fotbal“ + 0.7*„hokej“ + 0.7*„tenis“ + …)
lze považovat za koncept odpovídající lidsky interpretovatelné nálepce sport. Pokud nás však zajímá pouze sémantická podobnost dokumentů a slov, jednotlivé koncepty vůbec interpretovat nepotřebujeme.
Pro nalezení konceptů, příslušností slov ke konceptům a míry příslušnosti konceptů k dokumentům se používá matematická metoda nazývaná singular value decomposition. Jediným potřebným vstupem je kolekce dokumentů a počet konceptů, které chceme identifikovat. Výhodou latentní sémantické analýzy je, že určuje i váhy konceptů pro celou kolekci trénovacích dokumentů. Tedy pro každý koncept vrací i reálné číslo, které udává, jak moc je daný koncept v poskytnuté kolekci dokumentů významný. Díky tomu je možné koncepty s nejnižší vahou ignorovat a díky tomu dále snižovat dimenzionalitu sémantického prostoru. Lze matematicky dokázat, že chyba, ke které dojde při zanedbání konceptu s minimální vahou, je nejmenší možná.
Teorii latentní sémantické analýzy ani algoritmus nalezení konceptů zde popisovat nebudu. Případní zájemci z řad čtenářů se základní znalostí lineární algebry se o tom mohou dočíst např. v knize Foundations of Statistical Natural Language Processing nebo na Wikipedii.
Na závěr se podívejme, jak budou vypadat naše dokumenty v dvoudimenzionálním latentním sémantickém prostoru, trénovaným pouze nad těmito třemi dokumenty. Do stejného prostoru je zobrazen i pseudodokument „the dog walked“, který se v trénovací množině nevyskytoval a slouží zde jako potenciální dotaz:
Je vidět, že pseudodokument je v našem sémantickém prostoru nejblíže dokumentu 1. Stejně by to dopadlo i v původním 8-dimenzionálním prostoru, zde nám ale stačily pouze 2 dimenze.
Latentní sémantická analýza řeší spoustu problémů, se kterými jsme se doposud v seriálu setkali. V první řadě významně snižuje dimenzi prostoru pro zobrazení dokumentů a dotazů. Pro většinu aplikací stačí dimenze do velikosti 1000. Další, již zmíněnou žádanou vlastností je, že dokáže pracovat se synonymy a významově podobnými slovy. V neposlední řadě, paradoxně díky nepřesnostem vzniklým redukcí dimenzionality, eliminuje šum a chyby v datech. Nevýhodou je však velká výpočetní náročnost a problém s víceznačností (v modelu latentní sémantické analýzy jsou považována všechna slova mající stejný zápis za stejnovýznamová).
V příštím dílu si představíme podobnou metodu redukce dimenzionality, která se nazývá Probabilistic Latent Semantic Analysis a je postavena na pravděpodobnostním přístupu.
[1]Tenhle článek vypadá jako úvod k použití gensimu (http://radimrehurek.com/gensim/ ) :), používáte ho?
[2]Radima Řehůřka i jeho Gensim dobře znám. Momentálně ho ale nepoužíváme. Máme vlastní implementaci LSA, která je rychlejší. Pro zájemce, kteří si s LSA chtějí pohrát je ale Gensim ideální. Díky za poznámku.
[3]Radim tady v Seznamu oddělení výzkumu zakládal.
[4]Já vím :)
[5]Jirko, jak vlastně zajišťujeme, že nám většina dokumentů spadne do malého množství konceptů (aneb že váhy skoro všech konceptů jsou v dokumentu skoro nulové a jenom málo jich je výrazně nenulových)? Je to přirozená vlastnost LSA, nebo si ještě nějak pomáháme, aby to pak šlo lépe komprimovat?
[6]Prislusnost ke konceptum se, protoze nebyvaji dobre reprezentovatelne, urcuji obecne spatne … o cem hovoris resi lda a zarucuje to dirichletovy apriorni ppst … ale to malicko predbihame …
[7][5] Je to přesně tak, jak píše Tomáš. V LSA to nijak ovlivnit nejde. O LDA, kde už to lze, bude přespříští článek.
[8]OT : Ach jo, co je to zase dneska za výsledky :-( Nechápu proč je seznam takhle moc nestabilní a proč na google, kerý to má rozhodně vymakanější jsou weby na prvních místech a u seznamu to lítá od 1 do 10 místa a dále sem a tam. Některé výsledky jsou lepší to ano, ale naopak někde hlavně u vysoce konkurenčních slov vyjely haluz weby a weby „rychlokvašky“ s minimem odkazů a kw spamem.
[9]ano, naprosta katastrofa, to co zase dnes vyjizdi na nejruznejsi dotazy je bez komentare, na prvnim miste web co ma vseho vsudy 256 backlinku a za nim nebo dokonce az dole weby s backlinky 25000 a vice, zrejme jako kazdy rok s tim zacali carovat pred vanocema, fakt no comment
[10]Zdravím, je super, že se maká a pracuje se SERP, nicméně je velká škoda, že dochází i k tomu, že jsme na frázi levné letenky vypadli s první desítky mimo první stovku… nějaká chyba v algoritmu, nebo nekvalita webu? www.letenky.cr [levné letenky] Hezký den!
[11]Zdravím, mohl by mi někdo prosím říct, jak je možné že ve čtvrtek byl posun výsledků a poté jste asi po 4 hodinách dali zpět starou DB? Je opravdu těžké vysvětlovat klientům pořád dokola, že seznam prostě výsledky řadí jak se jim chce.
[12]Dobry den, take bych rad vedel vic o tom posuvu vysledku co byly 19.10. a 20.10 – zda to byla nejaka testovaci verze databaze a vratila se zase stara…. pripadne zda se opet da tahle databaze do ostreho provozu… nebo to byla jen nejaka chyba
[13]Dobrý den, je krásný, že píšete články o tom, jak by to mělo fungovat, nicméně mi připadáte jako některá z většiny českých univerzit. Tam se na přednáškách také akademicky povídá co by a jak by, ale v praxi to nikdo z tamních přednášejících neumí aplikovat. Váš SERP je poslední dobou stále horší a horší, nic relevantního mnohdy nenajdete (relevantní weby se propadly) a předpokládám že většina lidí mi dá za pravdu, že podíl návštěv z googlu se dramaticky zvyšuje, protože seznam upřednostňuje nesmyslné weby bez přínosu a lidi to už zřejmě nebaví a začínají používat vyhledávač, který najde rozumné výsledky. Možná by bylo fajn pracovat víc s testovací DB a tu nasadit ve chvíli, kdy máte odzkoušeno, že dané věc fakt funguje, ale pokud testujete online a je to poslední 3 týdny horší a horší, to to možná zabalte stejně jako to udělalo centrum.
[14]to si opravdu myslíte, že tu dostanete na něco odpověď?
[15]Ahoj tak jste mě ta sémanticky zanalyzovali, že mé stránky s více jak 500 mnou osobně psanými články mají najednou dnes za indexovánu 1 stránku ve Vaší laboratoři s názvem fulltext. Zajímalo by mne, zda na Vašich mýtinkách se také občas zamyslíte, že řada lidí si dává se svými projekty práci a investuje do nich čas a peníze.
[16]Koho tady zajímá nějaká analýza textu. To už jsem nemáte co psát? Pojďte raději řešit vyhledávání. Rychlost a vyhledávací kvalita neroste, spíše padá. Na kw IT jsem se ze 4 pozice propadl na 6 stránku. Vypněte to vyhledávání, protože jen brzdíte český internet. Sláva Google!
[17]Jen dotaz na čtenáře. Pozorujete nějakou indexaci seznamu? Nějak se mi nemění jak náhled tak i obsah stránek. I co se týče indexování novejch webů. Dík za poznatky
[18][16] se Spíš koho tady zajímá, že ses zrovna TY propadl? Ty ses propadl, někdo jinej je zase nahoře, to je snad princip řazení. Mě třeba analýza textu zajímá, vyhledávač je především zajímavá technologie a jsem rád, že se tu o ní píše. Akorát mě dost rozčiluje, že pod každým článkem se objeví plno nářků nějakých přiblblých SEO ufňukánků. Vědí o tom kulový, k tématu nemaj co říct a akorát tady spamují.
[19][18] a k čemu je to dobré, když robot skoro nefunguje a změny zaznamená třeba až za půl roku
[20]Robot na stránky chodí, jen se jaksi nezobrazují nově přidané stránky :(
[21]Tak konečně vím na čem jsem viz.: Yuhů[3] jinými slovy fulltext seznamu je „něčí..“ výzkumná laboratoř a tudíž vše co není na Skliku jsou pokusní králící :D. V podsatě to samé jako centrum.cz jen místo google je na seznamu laboratoř
[22]Seznam spustil poslední chybějící službu. http://www.novinky.cz/internet-a-pc/250243-seznam-cz-spustil-posledni-chybejici-sluzbu.html A kdy se bude pouštět fulltextový vyhledávač? Nebo se výsledky už budou navždy losovat?
[23]Včera proběhla menší změna, ale dnes je již vše opět zpět. Problém je, že se i neindexují nové weby což je problém u novejch projektů :(
[24]18 – proč Tě zajímá analýza textu, když Seznam ten Tvůj text zaindexuje za sto let. Na novinky, které hýbou světem mě ze Seznamu chodí lidi za 3 měsíce. Proč z Google chodí 7x více lidí, než ze Seznamu? Protože je tam post téměř hned od vydání. Nebrečím, to je fakt.
[25][24]protože texty asi 18CKA krade takoví vždy dělají chytráky a sami sedí v pokaděných trenkách u 486 s klávesnicí kde CTL+C a CTRL + V už neni ani vidět. Že je to tak Tome?
[26]Tak mi tedy řekni, kdo v týhle době nekrade. Viz. super projekt Slevomat, který pak okopčila široká veřejnost. Nesedím přímo ve fabrice Applu, abych to mohl dát na internet jako první.
[27]Krade se jak za starý ery kdy se stala fronta na pomeranče jenže mě sere jedna věc. Píšeš dáváš si práci a pak ti to někdo ukradne a nemůžeš dělat nic. Navíc seznam.cz podporuje a upřednostnuje weby s kradenými(duplicit) texty případně weby bez obsahu. Viz fulltext. Pokud by snad měl měl někdo ze seznamu jiný názor můžu Vám sem napsat příkladů kolik chcete.
[28]Kotlín: Já bych se na nějaké příklady rád podíval, můžeš něco postnout? Jinak seznam indexuje naše změny velice rychle, do 24 hodin, to je velice chvályhodné. Ještě přijít na to, proč nějaké weby upřednostňuje (očividně bez důvodu) a nějaké postupně shazuje (zřejmě bez důvodu). Nebo že by „money talks?“
[29][28]opravdu jen z tisíce :http://search.seznam.cz/?aq=&oq=&sourceid=szn-HP&thru=&q=v%C3%BDlov+rybn%C3%ADku+vrko%C4%8D+ druhý výsledek a nyní site: http://search.seznam.cz/?q=site%3Awww.bof.cz&count=10&pId=ZKxi-eIowRJzw2mpypVn&from=10
[30]27+28+29: Hlavně je problém v tom, že když napíšete originální obsah a tento obsah vám o týden později někdo vykrade a dá ho na již zavedený web a vy pak zkusíte dát úryvek originálního textu do vyhledávání, tak vyjede na lepších pozicích ten, kdo ten text ukradl. Seznam prostě zavedený web bere jako důvěryhodnější. Myslím, že to má co dělat i s rychlostí indexace a frekvencí návštěv robota, který prokazatelně chodí na delší dobu existující stránky častěji než na nové. Mám pocit, že Google se snaží tomuto předejít a pokud pozvete robota na nový web, tak máte do 24 hodin komplet zaindexováno. Pak se nemůže stát, že Vám někdo obsah vykrade. Seznam by měl trochu upravit prioritu robota a rychleji reagovat na pozvánky.
[31]28: hmm, docela masakr :-))) 30: No, s touhle důvěryhodností zrovna u mě problém není… problém je, že nevím, kde je problém :-)))) Jináč, taky se vám rozsypal design Sblogu? Mám ho už od pátku takovej… jinej :)))
[32]28] 18.11.11 09:22:00 R3X to on indexuje rychle ja postnu a nez dohulim tak uz to tam je, ale pouze do té doby nez se splete na tvoji domene a pak ti zbyde ve fulltextu jen HP po týdnu. Jinak zase i kdyz to je vecne rozflákany tak podpora je ochotná a za mesíc a půl ti to opraví.%D
[33]Kdejaká čtečka Tě předběhne, někdy spadne ale někdy ne. Výsledky jen nahrávají starším doménám…
[34]Seznam je prostě TOP! Co dodat… http://search.seznam.cz/?q=site%3Ainzerce-prodej.info