Využití SVD pro indexování latentní sémantiky Michal Krátký1 Department of Computer Science, VŠB-Technical University of Ostrava, Czech Republic
[email protected] Abstrakt Zpracováváním velkého množství informací (např. novinových článků, textů knih a časopisů v knihovně atd.) se zabývá oblast počítačových věd zvaná Information Retrieval. Systémy pro údržbu a vyhledávání takovýchto textů se nazývají Dokumentografické informační systémy (DIS ). Rozmanité metody a modely vyvinuté v oblasti IR našly široké uplatnění v mnoha oblastech současného života. Jedním ze široce používaných modelů je model vektorový, ve kterém je dokument reprezentován jako vektor ve vícerozměrném vektorovém prostoru. Sada dokumentů je pak modelována jako matice termů v dokumentech. Lineární algebra poskytuje celou řadu metod redukujících tuto reálně velkou a řídkou matici pro výpočetně snadné nalezení dokumentů relevantních k dotazu uživatele. Jednou z takovýchto metod je singulární rozklad (Singular Value Decomposition - SVD), kterou se zabývá i tento článek. Aplikaci metody SVD v oblasti Information Retrieval nazýváme indexování latentní sémantiky (Latent Semantic Indexing - LSI ).
Key words: Information Retrieval, Dokumentografické informační systémy (DIS), vektorový model, singulární rozklad (Singular Value Decomposition SVD), indexování latentní sémantiky (Latent Semantic Indexing - LSI)
1
Úvod
Zpracováváním velkého množství informací se zabývá oblast počítačových věd zvaná Information Retrieval (IR) ([FB92], [SM83], [Kor97], [Kow97], [Rij79], [PSH98]). Takovými informacemi mohou být např. novinové články či články v časopisech, texty knih, obrázky či dokonce zvukové a video záznamy. Ucelený blok informací nazýváme dokument. Jelikož se ne vždy musí jednat pouze o dokument textový, bylo by vhodné používat spíše označení multimediální dokument. Systémy pro údržbu a vyhledávání takovýchto dokumentů se nazývají Dokumentografické informační systémy (DIS ). Ukládání a vyhledávání informací (Storage and Information Retrieval ) je oblast, která byla po staletí doménou knihovnictví. Pro zpracování velkého množství informací za účelem jejich efektivního dotazování je ovšem nutno využít znalostí počítačových věd jako jsou např. algoritmy či datové struktury.
Kořeny IR sahají až do počátku 60. let. Rozmanité metody a modelování vyvinuté v oblasti IR ([PSH98]) našly široké uplatnění v mnoha oblastech současného života. Příkladem může být vyhledávání knih a časopisů v knihovně dle klíčových slov, autorů apod, vyhledávání relevantních stránek v internetových vyhledávačích atd. Z pohledu uživatele je DIS prostředek, který je po zadání dotazu schopen zobrazit seznam relevantních dokumentů. Např. zadáli uživatel v prohlížeči pojem UB-tree, očekává od vyhledávacího stroje relevantní dokumenty ke svému dotazu, tedy dokumenty o této datové struktuře. Zpracovávané dokumenty mohou mít různou popř. žádnou vnitřní strukturu, přesto je nutné hledat metody pro ukládání a vyhledávání takovýchto dokumentů. Pro uložení a vyhledávání dokumentů je nutné použít celou řadu metod a proto se architektura DIS skládá z několika komponent. Pokud máme za úkol zpracovat nějakou sadu dokumentů, pak musíme nejprve provést výběr pojmů charakterizující jednotlivé dokumenty. Výstupem takového výběru nemusí být pouze slovo z abecedy jazyka, ale obecně term (též klíčové slovo, pojem, výraz, termín) jako dále nedělitelná jazyková jednotka. Výběr může být ruční nebo automatizovaný. Pokud automatizovaně vybíráme pojmy charakterizující dokument, pak musíme nejprve provést syntaktickou analýzu textu (tzn. konverzi vstupní posloupnosti znaků na posloupnost slov nebo termů), dále je nutné odstranit frekventovaná slova (pokud je nějaké slovo obsaženo ve velkém množství dokumentů, pak je jeho význam pro vyhledávání nulový) a dále je nutné provést lemmatizaci. Pro indexování je vhodné nepoužívat morfologické tvary slov, ale jejich tvary základní (kořen, angl. stem). Pokud uživatel např. hledá dokumenty relevantní k pojmu stroj, pak jej zajímají i dokumenty s pojmy stroji, strojů atd. Hledáním kořenů slov se zabývá právě lemmatizace. Architektura DIS může dále obsahovat celou řadu komponent. Při jejich implementaci nevystačíme pouze se znalostmi z oblasti počítačových věd, ale je nutné využít dalších oborů jako je např. lingvistika, což je, vhledem ke zpracování textu přirozených jazyků, zcela přirozené. V oblasti IR byla vyvinuta celá řada modelů pro podporu ukládání a vyhledávání dokumentů. Pro změření kvality daného přístupu k vyhledávání dokumentů může být důležitá celá řada faktorů, např. rychlost zpracování dotazů nebo schopnost poskytnout uživateli informaci o relevantních dokumentech atd. Míra schopnosti poskytnout uživateli informaci o relevantních dokumentech se vyjadřuje pomocí dvou koeficientů, koeficientu přesnosti (precision), někdy také koeficientu relevance, a koeficientu úplnosti (recall ). Koeficient přesnosti můžeme chápat jako pravděpodobnost, že vybraný dokument je relevantní, koeficient úplnosti jako pravděpodobnost s jakou byly vybrány všechny relevantní dokument. V ideálním případě by koeficienty přesnosti a úplnosti měly být rovny 1. Tohoto stavu dnes ovšem nelze dosáhnout, navíc se ukazuje, že koeficienty jsou na sobě závislé - se vzrůstají přesností klesá úplnost a opačně. Zejména pro Booleovský model (viz dále) platí, že přesnost a úplnost jsou nepřímo úměrné. Uživatelé často volí jako výhodnější vyšší hodnotu přesnosti, při které nejsou zavaleni množstvím nerelevantních dokumentů.
Jedním z modelů IR je Booleovský model, který vyhledává dokumenty dle toho zda lexikálně obsahují termy z booleovské výrazu zadaného uživatelem (tzv. word matching). Kořeny tohoto modelu sahají až do 60. let minulého století a přes své nedostatky je v současné době nejrozšířenější, patrně i pro svou jednoduchost. Problémem tohoto modelu je mimo jiné i to, že relevantní dokumenty jsou pouze takové, které lexikálně obsahují zadané pojmy. Ovšem pro uživatele nemusí být takové výsledky příliš uspokojivé. Není navíc jasné, zda hledaný dokument má obsahovat současně všechny nebo jen některé pojmy. V přirozených jazycích lze stejný pojem vyjádřit různými způsoby (synonyma) a rovněž jediné slovo může mít více významů (polysemy). Vyhledávání dokumentů dle toho, které pojmy obsahují, nevystihuje dostatečně dobře sémantiku dokumentů. Pokud např. uživatel hledá dokumenty, které jsou relevantní k pojmům tree a data structures je jasné, že dokumenty o šlechtění jabloní nejsou ty, které ho zajímají. Pro uživatele je rovněž výhodné, když relevantní dokumenty jsou na výstupu seřazeny dle míry relevance (podobnosti ) a on má možnost procházet dokumenty od nejvíce relevantních k těm nejméně podobným. Dále je vhodné, aby jednotlivé pojmy byly váženy dle stupně, v jakém charakterizují daný dokument. Je jasné, že ne všechny pojmy charakterizují stejně nějaký dokument. Ukazuje se tedy, že vyhledávání dokumentů obsahujících lexikálně dané termy není příliš vhodné, protože uživatel často nehledá dokumenty obsahující přesně daný pojem, ale spíše dokumenty, které jsou nějakým způsobem sémanticky (významově) podobné (relevantní) jeho dotazu. Modelem vyhovujícím těmto požadavkům je model vektorový. Ve vektorovém modelu je dokument reprezentován jako vektor ve vícerozměrném prostoru. Sada dokumentů je pak modelována jako matice termů v dokumentech. Tento model navíc umožňuje využívat širokého aparátu lineární algebry, poskytující např. metody pro aproximaci této reálně velké a řídké matice pro výpočetně méně náročné získávání dokumentů relevantních k dotazu uživatele. Takovouto metodou je i singulární rozklad (Singular Value Decomposition - SVD). Aplikaci této metody v IR nazýváme indexováním latentní sémantiky (Latent Semantic Indexing - LSI ), protože umožňuje reprezentovat vazby mezi termy a dokumenty, které nejsou na první pohled v dokumentech patrné. Uživatel často zadává termy a na výstupu očekává dokumenty relevantní k těmto pojmům, aniž by relevantní dokumenty musely některé ze zadaných termů obsahovat. Uživatel chce často vyhledat dokumenty s podobnou sémantikou jako jeho dotaz a ne ty, které lexikálně obsahují termy z jeho dotazu. Metodou umožňující takové vyhledávání dokumentů je právě LSI. Některé rysy LSI nám poskytují kvalitativně lepší přínos než klasický vektorový model (jak dále uvidíme na příkladech v následujících kapitolách). V kapitole 2 je popsán vektorový model s ukázkami aplikace lineární algebry pro vyhledávání relevantních dokumentů. Kapitola 3 popisuje indexování latentní sémantiky jako aplikaci SVD v oblasti IR. V závěru jsou pak shrnuty nabyté poznatky.
2
Vektorový model
Ve vektorovém modelu je každý dokument Dj z kolekce n dokumentů reprezentován vektorem Dj v m-rozměrném vektorovém prostoru, kde 1 ≤ j ≤ n a m je celkový počet pojmů. Každý term tak reprezentuje dimenzi j takového prostoru. i-tý prvek vektoru Dj , 1 ≤ i ≤ m, obsahuje váhu termu i (též frekvence termu) v dokumentu Dj . Váhování termů má za cíl zlepšit přesnost a úplnost. Pro váhování termů se používá celá řada přístupů ([BB99]), které jsou podpořeny experimenty. V tomto článku budeme používat pouze hodnot 1 a 0, pokud term charakterizuje resp. necharakterizuje dokument. Příklad 1. Mějme kolekci čtyř dokumentů (D1 - D2 ) a tří termů (T1 - T3 ), jednotlivé dokumenty jsou charakterizovány jednotlivými termy takto: D1 : T1 , T2
D2 : T1 , T3
D3 : T2 , T3
D4 : T2
Dokumenty D1 -D4 jsou reprezentovány 4 vektory ve 3-rozměrném prostoru D1 − D4 . Na obrázku 1 vidíme geometrickou interpretaci těchto vektorů. Na tomto obrázku jsou vektory zobrazeny jako body ve 3-rozměrném prostoru, jejichž souřadnice jsou rovny souřadnicím vektorů (vektory jsou tedy umístěny v počátku). Vidíme, že v našem případě se tyto body nachází v rozích jednotkové krychle. Získané vektory dokumentů: D1 = (1, 1, 0)
D2 = (1, 0, 1)
D3 = (0, 1, 1)
D4 = (0, 1, 0)
D3 dimenze 2 (term 2)
1
D1
D4 dimenze 3 (term 3)
1 D2
1
dimenze 1 (term 1)
Obrázek 1. 3-rozměrný prostor dokumentů.
V oblasti IR je velmi často používána m × n matice termů v dokumentech (term-by-document matrix ). Matice termů v dokumentech je v literatuře vždy označena jako A. Tato matice obsahuje jako sloupcové vektory cA j transponované vektory dokumentů DjT , 1 ≤ j ≤ n, a řádkové vektory riA vektory termů Ti , 1 ≤ i ≤ m (tedy vektory příslušnosti termu i k dokumentu j). Každý term je tedy rovněž reprezentován jako vektor, tentokrát v n-rozměrném prostoru. Příklad 2. Na obrázku 2a) vidíme tabulku výskytů termů v dokumentech z příkladu 1. Matice 3 × 4 termů v dokumentech vidíme na obrázku 2b). Tato matice obsahuje A A A jako sloupcové vektory transponované vektory dokumentů cA 1 , c2 , c3 a c4 , kde A T A A A A cj = Dj , 1 ≤ j ≤ 4 a řádkové vektory vektory termů r1 , r2 a r3 , kde ri = Ti , 1 ≤ i ≤ 3. Vektory termů jsou vektory ve 4-rozměrném prostoru: T1 = (1, 1, 0, 0)
D1 T1 1 T2 1 T3 0
D2 1 0 1 a)
D3 0 1 1
T 2 = (1, 0, 1, 1)
D4 0 1 0
T 3 = (0, 1, 1, 0)
" A=
1100 1011 0110
#
b)
Obrázek 2. a) Tabulka výskytů termů v dokumentech. b) Matice 3 × 4 termů v dokumentech.
Příklad 3. Mějme kolekci sedmi dokumentů (článků z oblasti Computer Science), které jsou charakterizovány celkem 9 termy T1 -T9 : XML, indexing XML data, HTML, distribution applications, data structures, OO methods, WWW, C++ a Java. Na obrázku 3a) vidíme, kterými termy jsou charakterizovány jednotlivé dokumenty. Z takovéto sady dokumentů můžeme vytvořit matici 9 × 7 termů v dokumentech (viz obrázek 3b).
Sémantický obsah dokumentu je obyčejně určen relativní vahou termů, vektory dokumentů (sloupcové vektory matice termů v dokumentech) jsou tedy obyčejně normovány tak, že Euklidovská norma každého vektoru dokumentu Dj je rovna 1. Euklidovská norma ||Dj ||2 je definována:
D1 : D2 : D3 : D4 :
OO methods, Java XML, indexing XML data, data structures indexing XML data, data structures, C++ XML, distribution applications, OO methods, C++, Java D5 : XML, WWW D6 : HTML, WWW D7 : XML, HTML
A=
a)
0 0 0 0 0 1 0 0 1
1 1 0 0 1 0 0 0 0
0 1 0 0 1 0 0 1 0
1 0 0 1 0 1 0 1 1
1 0 0 0 0 0 1 0 0
0 0 1 0 0 0 1 0 0
1 0 1 0 0 0 0 0 0
b)
Obrázek 3. a) Výskyty termů v dokumentech. b) Matice 9 × 7 termů v dokumentech.
v um q uX 2 ||Dj ||2 = DjT Dj = t Dij
(1)
i=1
Euklidovská norma je rovna velikosti vektoru a je možné ji definovat pomocí skalárního součinu vektorů: ||Dj ||2 =
q (Dj , Dj )
(2)
Pokud chceme, aby vektor dokumentů byl vektor jednotkový (tedy ||Dj || = 1), je nutné podělit každou složku vektoru Euklidovskou normou:
Dˆj =
m X
Dij /||Dj ||2
(3)
i=1
Příklad 4. Vezměme √vektor dokumentu √ D1 = (1, 1, 0) z příkladu 1. Euklidovská√ norma √ ||D√1 ||2 = 12 + 12 + 02 = 2 = 1.4142, normalizovaný vektor Dˆ1 = (1/ 2, 1/ 2, 0/ 2) = (0.7071, 0.7071, 0). Koncové body takto normovaných vektorů dokumentů leží na povrchu jednotkové koule, obecně na povrchu hyperkoule.
Příklad 5. Vezměme matici A termů v dokumentech z příkladu 3. Matici Aˆ s jednotkovými sloupcovými vektory (vektory dokumentů) vidíme na obrázku 4.
0 0 0 0 Aˆ = 0 0.7071 0 0 0.7071
0.5774 0.5774 0 0 0.5774 0 0 0 0
0 0.5774 0 0 0.5774 0 0 0.5774 0
0.4472 0 0 0.4472 0 0.4472 0 0.4472 0.4472
0.7071 0 0 0 0 0 0.7071 0 0
0 0 0.7071 0 0 0 0.7071 0 0
0.7071 0 0.7071 0 0 0 0 0 0
Obrázek 4. Matice termů v dokumentech s jednotkovými sloupcovými vektory.
2.1
Dotazování dokumentů
Uživatel zadává dotaz jako množinu pojmů, na výstupu očekává množinu relevantních dokumentů. Dotaz uživatele musí být předzpracován stejně jako kolekce dokumentů při indexaci, musí tedy projít syntaktickou analýzou, odstraněním frekventovaných slov, lemmatizací atd. Dotaz je tedy opět dokument, pro který hledáme podobné dokumenty, tedy dokumenty relevantní k dotazu uživatele. Co je to ovšem podobnost, jak ji můžeme měřit a jak ji aplikovat na oblast IR? Podobnost ve vektorovém modelu můžeme chápat jako vzdálenost jednotlivých vektorů dokumentů ve vektorovém prostoru. Definice 1. Označme δ funkci přiřazující každým dvěma vektorům dokumentů reálné číslo (vzdálenost), které se zmenšuje (zvětšuje) s podobností dokumentů. Množina dokumentů R relevantních k dotazu jsou všechny dokumenty z kolekce Dj , 1 ≤ j ≤ n, které mají vzdálenost δ vektoru dokumentu Dj a vektoru dotazu q ≤ (≥) zvolená prahová hodnota t ( threshold). R = {Dj ; δ(q, Dj ) ≤ (≥) t, 1 ≤ j ≤ n}
(4)
Zde vidíme výhody vektorového modelu. Uživatel dostane na výstupu setříděné relevantní dokumenty dle jejich vzdálenosti od dotazovacího vektoru. Otázkou je jakou vzdálenost ve vektorovém prostoru použít. Mohli bychom např. interpretovat dokumenty a dotaz jako body v m-rozměrném prostoru a jako vzdálenost použít klasickou Euklidovskou vzdálenost. Z experimentů bylo zjištěno, že poměrně nejlépe charakterizuje podobnost dokumentů tzv. kosinová vzdálenost, tedy úhel dvou vektorů vyjádřený pomocí skalárního součinu vektorů u a v: (u, v) p (u, u) (v, v)
cos θ = p
(5)
V tomto případě je −1 ≤ cos θ ≤ 1 a kosinová vzdálenost se s podobností vektoru dokumentů zvětšuje (úhel vektorů se zmenšuje). Množina dokumentů R relevantních k dotazu uživatele obsahuje takové dokumenty, jejichž kosinová vzdálenost od dotazovacího vektoru q je ≥ cos θt :
R = {Dj ; cos θj ≥ cos θt , 1 ≤ j ≤ n}
(6)
(q, Dj ) p ,1 ≤ j ≤ n (q, q) (Dj , Dj )
(7)
kde cos θj = p
Pokud znormujeme dotazovací vektor a vektory dokumentů Euklidovskou normou (tzn. jejich velikost je 1), vidíme z této rovnice, že jmenovatel je vždy 1 a pro výpočet vzdálenosti je tudíž nutné počítat vždy jen skalární součin vektorů, což je výpočetně výhodné. Na obrázku 5 vidíme význam kosinové vzdálenosti pro podobnost vektorů dokumentů ve 2-rozměrném prostoru. Vektory dokumentů jsou zobrazeny jako body se souřadnicemi jejich koncových bodů. Dokumenty relevantní k dotazu uživatele jsou všechny dokumenty, které svírají s dotazovacím vektorem q úhel ≤ θ. V tomto případě jsou to dokumenty D2 , D3 a D4 .
D3
0
D1 D2
q 0
D4 D5
D6
Obrázek 5. Geometrický význam kosinové vzdálenosti dotazovacího vektoru a vektoru dokumentů ve 2-rozměrném prostoru.
Příklad 6. Vezměme kolekci dokumentů z příkladu 3 a příslušnou matici termů v dokumentech (viz příklad 5) a uživatelský dotaz, který obsahuje dva termy XML a WWW. Uživatel chce získat dokumenty, které jsou podobné dotazovacímu dokumentu charakterizovanému těmito pojmy. Dotazovací vektor q bude mít složky q = (1, 0, 0, 0, 0, 0, 1, 0, 0), normalizovaný vektor qˆ = (0.7071, 0, 0, 0, 0, 0, 0.7071, 0, 0). Kosinové vzdálenosti dotazovacího vektoru a vektorů dokumentů cos θj , pro 1 ≤ j ≤ 7: cos θ1 = 0 cos θ5 = 1
cos θ2 = 0.4083 cos θ6 = 0.5
cos θ3 = 0 cos θ7 = 0.5
cos θ4 = 0.3162
Podobné dokumenty budou v tomto případě ty, jejichž kosinová vzdálenost ≥ 0.5 (cos θt = 0.5). Uživateli jsou tedy vráceny jako relevantní dokumenty D5 , D6 , D7 .
Příklad 7. Vezměme v úvahu dotaz uživatele, který obsahuje jediný pojem XML. Dotazovací vektor q = (1, 0, 0, 0, 0, 0, 0, 0, 0). Kosinové vzdálenosti cos θj , pro 1 ≤ j ≤ 7: cos θ1 = 0 cos θ5 = 0.7071
cos θ2 = 0.5774 cos θ6 = 0
cos θ3 = 0 cos θ7 = 0.7071
cos θ4 = 0.4472
Zvolili jsme cos θt = 0.5 a uživateli jsou vráceny jako relevantní dokumenty D2 , D5 , D7 . Otázkou je, zda relevantní není i dokument D4 , který se určitě nějakým způsobem zabývá tématem XML. Dokument D4 získáme jako relevantní snížením prahové hodnoty cos θt na 0.4.
Zdálo by se, že nic nebrání použití vektorového modelu a výše popsaného matematického aparátu pro získávání relevantních dokumentů k dotazu uživatele. Je nutné si uvědomit, že reálné kolekce dokumentů mohou mít řádově až miliony dokumentů a sta tisíce termů. Pokud bereme v úvahu algoritmus výpočtu kosinové vzdálenosti mezi dotazovacím vektorem a n dokumenty v m-rozměrném prostoru (m je celkový počet pojmů) s časovou složitostí O(n ∗ m), bylo by pro vyhledání relevantních dokumentů potřeba n ∗ m násobení a stejný počet sčítání1 . Vezměme nějaké reálně možné hodnoty počtu dokumentů a termů, např. n = 107 a m = 105 , pak počet násobení a sčítání bude 1012 , což je počet operací jdoucí mimo rámec současného hardwarového vybavení. Nabízí se možnost využít některou z metod aparátu lineární algebry jako je např. Singular Value Decomposition (SVD), který umožňuje snížit dimenzi prostoru dokumentů. Navíc příklad 7 odhaluje určitý nedostatek vektorového modelu. Vezměme dokument D6 charakterizovaný pojmy HTML a WWW a dotaz s jediným pojmem XML. Tento dokument je určitým způsobem sémanticky podobný dotazu pomocí vazeb mezi termy WWW, HTML a dokumenty D5 , D7 , přesto výpočtem kosinové vzdálenosti jsme dostali hodnotu 0 (tzn. tento dokument není vůbec relevantní k dotazu). Není možné automatizovaně zachytit tyto skryté (latentní) vazby mezi termy a dokumenty? Takovéto možnosti nám dává právě metoda indexování latentní sémantiky (LSI ) jakožto aplikace SVD v oblasti Information Retrieval, která je popsána v následující kapitole.
1
Ve skutečnosti bude počet operací mnohem nižší, protože matice termů v dokumentech je přirozeně řídká, přesto je práce s takto vysoce-dimenzionálním prostorem výpočetně náročná.
3
Indexování latentní sémantiky
Vzhledem k možnému velkému počtu dokumentů a termů charakterizující dokumenty, je nutno využít některé z metod nabízených lineární algebrou pro snížení dimenze prostoru dokumentů. Singulární rozklad (Singular Value Decomposition - SVD) popsaný např. v [Dos01], nám umožňuje provést tuto redukci dimenze prostoru dokumentů při zachování shluků podobných si dokumentů (tedy prostorově blízkých). Navíc se ukazuje, že pomocí singulárního rozkladu je možné odhalit jakési skryté (latentní) vazby mezi termy a dokumenty, jejichž zachycení nám poskytuje novou kvalitu v oblasti IR. Vektorový model nás zbavil v praxi nevhodného získávání dokumentů dle lexikálního obsahování termů dotazu, ovšem žádným způsobem neumožňuje zachytit tyto skryté vazby. Jelikož singulární rozklad matice termů v dokumentech tyto vazby zachycuje (i při redukci prostoru), nazýváme tuto metodu indexováním latentní sémantiky (Latent Semantic Index - LSI ) ([BB99], [BDL95]). 3.1
Singulární rozklad
... ... . .. ...
Věta 1 (Singulární rozklad). Nechť A je libovolná čtvercová matice. Pak existují ortogonální matice U a V a diagonální matice σ1 0 . . . 0 0 σ3 . . . 0 Σ= , 0 0 . . . σn √ na jejíž diagonále jsou vlastní čísla matice AT A tak, že A = U ΣV T .
(8) √
Rozklad (8) se nazývá singulární rozklad a vlastní čísla matice nazývají singulární čísla matice A.
AT A se
...
...
... ... . .. ...
... ...
... ...
... ... ...
... ... ... ... ... ...
... ... ...
... ... ... ... ... ...
Singulární rozklad je obecná metoda lineární algebry s rozsáhlým využitím v různých odvětvích, tento text se zabývá využitím SVD v Information Retrieval. Jelikož matice termů v dokumentech není čtvercová, ale obecně řádu m × n, m 6= n, singulární rozklad můžeme schématicky znázornit: m>n: ∗ ∗ ... ∗ ∗ ∗ . . . . . . . . . ∗ σ1 0 . . . 0 ∗ ∗ . . . ∗ ∗ ∗ . . . . . . . . . ∗ 0 σ2 . . . 0 ∗ ∗ ... ∗ ∗ ∗ ... ∗ = 0 0 . . . σn ∗ ∗ ... ∗ 0 0 ... 0 ∗ ∗ ... ∗ ∗ ∗ ... ... ... ∗
m
=
U m×m
Σ m×n
... ...
... ... ... ...
...
...
... ...
...
... ...
...
... ...
VT n×n
U je ortogonální matice m × m jejíž sloupce definují levé singulární rozklady matice A a v našem případě reprezentuje matici vektorů, V je ortogonální matice n × n, jejíž sloupce definují pravé singulární vektory A a reprezentuje matici dokumentů. Σ je diagonální matice m × n obsahující singulární čísla σ1 , σ2 , . . . , σmin(m,n) uspořádané sestupně na hlavní diagonále, σ1 ≥ σ2 ≥ . . . ≥ σmin(m,n) . Singulární rozklad umožňuje redukci hodnosti matice termů v dokumentech. Hodnost matice rA je počet nenulových diagonálních prvků matice A. Prvních rA sloupců matice U určuje bázi sloupcového prostoru A a prvních rA řádků matice V T určuje bázi řádkového prostoru A. SVD umožňuje aproximaci matice A s přihlédnutím ke sloupcovým (vektory dokumentů) i řádkovým vektorům (vektory termů). Výpočet singulárního rozkladu je náročný, ale provádí se pouze při indexaci a při vyhledávání je využito již vypočteného rozkladu (často je takto zaindexovaná kolekce dokumentů označována jako LSI databáze). Algoritmus výpočtu vlastních čísel dle naivního algoritmu vede na faktoriálovou časovou složitost, proto jej nelze pro velké matice použít. K výpočtu se používá numerických metod, které však nejsou obsahem tohoto článku a lze je nalézt např. v [GL96].
Příklad 8. Mějme matici termů v dokumentech z příkladu 5, matice singulárního rozkladu matice A:
0.6977 0.2619 0.3527 0.1121 U = 0.2619 0.1874 0.3527 0.2104 0.1874
0.0931 −0.2966 0.4491 −0.1410 −0.2966 −0.3747 0.4491 −0.3337 −0.3747
−0.0175 −0.4681 0.1017 0.1478 −0.4681 0.5049 0.1017 −0.0954 0.5049
0.6951 −0.1969 −0.4013 0.0733 −0.1969 −0.1270 −0.4013 −0.2820 −0.1270
0 0 −0.7071 −0.0000 0 0 0.7071 0 0
−0.0157 0.2468 0.0066 −0.4842 0.2468 0.2287 0.0066 −0.7340 0.2287
−0.1441 0.1570 0.0493 0.8402 0.1570 −0.0338 0.0493 −0.4657 −0.0338
0 −0.6356 0 0 0.6356 −0.3099 0 0 0.3099
0 0.3099 0 0 −0.3099 −0.6356 0 0 0.6356
1.5777 0 0 0 Σ= 0 0 0 0 0
0 1.2664 0 0 0 0 0 0 0
0 0 1.1890 0 0 0 0 0 0
0 0 0 0.7962 0 0 0 0 0
0 0 0 0 0.7071 0 0 0 0
0.1680 −0.4184 0.6005 −0.2256 0.4471 −0.2280 −0.4631 0.2185 0.2687 −0.4226 −0.5009 −0.4900 V = 0.3954 −0.3994 0.3929 0.1305 0.4708 0.3028 0.0501 0.2609 0.3162 0.5015 0.4708 0.3028
0 0 0 0 0 0.5664 0 0 0
0 0 0 0 0.7071 0.1210 −0.7128 0 0.0501 0.2609 −0.7071
0 0 0 0 0 0 0.1968 0 0
0.5710 0.4872 −0.2451 −0.6132 −0.0113 0.0166 −0.0113
−0.2432 0.4986 −0.4451 0.3697 −0.3405 0.3542 −0.3405
Jedním z velmi výhodných rysů singulárního rozkladu je sestupné uspořádání singulárních čísel na hlavní diagonále matice Σ. Důsledkem je, že pro ”rozumné” výsledky nám stačí vypočítat k nejvyšších singulárních čísel. k-aproximace hodnosti matice (rank-k approximation) A (Ak ), je získána přibráním pouze k prvních singulárních čísel matice Σ, přičemž ostatní jsou ignorovány. Vhodný počet singulárních čísel je nutné stanovit na základě experimentů. Pro velké kolekce dokumentů se zpravidla uvádí počet mezi 200 až 300. Metoda SVD redukuje mnoho-dimenzionální prostor na prostor s dimenzí k, při zachování prostorových shluků podobných si dokumentů a tak koeficienty přesnosti a úplnosti nejsou degradovány. k-redukovaný singulární rozklad je definován Ak = Uk Σk VkT
(9)
kde Uk je matice m×k získaná z matice U přibráním k prvních sloupců matice U , Σk je diagonální matice k × k obsahující na diagonále prvních k singulárních čísel a Vk je matice n × k (VkT je tedy typu k × n) vzniklá přibráním prvních k sloupců matice V . Matice Ak je potom matice typu m × n. Na obrázku 6 je schématicky zobrazena k-redukce singulárního rozkladu. Chybu aproximace A maticí Ak lze (dle věty Eckarta a Younga ([BDL95])) vypočítat takto
||A − Ak ||F =
min rank(B)≤k
||A − B||F =
q 2 2 σk+1 + σk+2 + . . . + σr2A
(10)
Aproximací nižšími hodnostmi Ak se do sloupcových vektorů (vektory dokumentů) promítají hodnoty z jiných sloupců dle vazeb mezi nimi. Tato vlastnost nám umožňuje zachytit skryté vazby mezi dokumenty a termy. Např. pokud
Vektory termu k
k *
{
k =
Ak
Uk
mxn
*
* k
mxk
Vektory dokumentu
{
k
kxk
VkT
kxn
Obrázek 6. Znázornění k-redukce singulární rozkladu.
rA = 7 a k = 3, pak matice A3 není úplně podobná matici A, ale zato zachycuje ony skryté vazby a umožňuje tak získávat relevantní dokumenty dle jejich významu (srovnejme matici A s maticí A3 z obrázku 4 resp. 8). Příklad 9. Vezměme v úvahu matici termů v dokumentech z obrázku 4 a její 3-aproximační maticí A3 z obrázku 8. Dle rovnice (10) spočítáme chybu této aproximace ||A − A3 ||F =
p 0.79622 + 0.70712 + 0.56642 + 0.19682 = 1.222
Zajímá nás poměr této chyby vůči hodnotě ||A||F ||A − Ak ||F /||A||F ,
(11)
kde ||A||F =
q
σ12 + σ22 + . . . + σr2A
V tomto případě získáme ||A||F =
p
1.5772 + 1.26642 + . . . + 0.19682 = 2.6458
||A − A3 ||F /||A||F = 1.2221/2.6458 = 0.462 To tedy znamená, že aproximací matice A maticí A3 vzniká chyba 46%, aproximační matice A3 obsahuje 46% změn oproti matici A. Je jasné, že se zvyšujícím se k chyba klesá (např. pro k = 6 je chyba 7%) a obráceně. Při
aproximacích maticemi nízkých hodností, ale získáváme onu vlastnost metody LSI - zachytit skryté vazby mezi termy a dokumenty. Optimální výkon LSI (tedy volba vhodného k) zůstává stále otevřenou otázkou. V původním vektorovém prostoru dokumentů jsou dokumenty reprezentovány m-rozměrnými vektory. Pomocí k-redukce singulárního rozkladu je tento prostor redukován na k-rozměrný. Redukovanou matici dokumentů získáme: Dk = Vk Σk
(12)
výsledkem je matice n×k, kde j-tý řádkový vektor je redukovaný k-rozměrný vektor j-tého sloupcového vektoru matice A, tedy j-tého vektoru dokumentů. Vektory pojmů jsou reprezentovány jako body v n-rozměrném prostoru. Původní n-rozměrný prostor je redukován na k-rozměrný. Redukovaná matice termů je získána: Tk = Uk Σk
(13)
výsledkem je matice m×k, kde i-tý řádkový vektor je redukovaný k-rozměrný vektor i-tého řádkového vektoru matice A, tedy i-tého vektoru termů. Příklad 10. Vezměme singulární rozklad matice termů v dokumentech z příkladu 5, 2-redukované matice dokumentů resp. pojmů: 1.1008 0.1179 0.4132 −0.3756 0.2651 −0.5299 0.5565 0.7054 −0.2887 0.5687 0.4240 −0.5352 0.1769 −0.1786 T2 = U2 Σ2 = D2 = V2 Σ2 = 0.4132 −0.3756 0.6238 −0.5058 0.7428 0.3835 0.2957 −0.4745 0.4989 0.5687 0.6351 0.5565 0.3320 −0.4226 0.7428 0.3835 0.2957 −0.4745 Takto získané 2-rozměrné body zobrazené ve 2-rozměrném prostoru vidíme na obrázku 7. Všimněme si, že shluky podobných dokumentů a příslušných termů zůstaly zachovány.
3.2
Dotazování
Po výpočtu singulárního rozkladu se získávání relevantních dokumentů pomocí uložené LSI databáze provádí výpočtem kosinové vzdálenosti mezi dotazovací vektorem q (tentokrát sloupcovým) a sloupcovými vektory redukované matice Ak .
1 D6 T3 (HTML) T7 (WWW) D5 D7 T1 XML
0 T4 (dist. app.)
1
D2 T8(C++) T2 (index. XML) T9(Java) T5(data struct.) T6(OO meth.) D1 D3 D4
-1
Obrázek 7. 2-rozměrný redukovaný prostor termů a dokumentů.
cos θj =
(Ak ej )T q ||Ak ej ||2 ||q||2
(14)
kde ej označuje j-tý kanonický vektor dimenze j (tzn. j-tý sloupec jednotkové matice n×n In ). Sloupcový vektor Ak ej je tedy j-tý sloupec matice Ak s hodností k. Výraz můžeme dále upravit na cos θj =
(Uk Σk VkT ej )T q ||Uk Σk VkT ej ||2 ||q||2
(15)
platí (Uk Σk VkT ej )T = (eTj (VkT )T ΣkT UkT ) = (AT )T = A, pro diagonální čtvercovou matici D platí: DT = D = (eTj Vk Σk UkT ) Rovnici (15) můžeme tedy upravit na cos θj =
eTj Vk Σk (UkT q) , j = 1, 2, . . . , n ||eTj Vk Σk ||2 ||UkT q||2
(16)
Označme sj k-redukovaný vektor dokumentu j, sj = eTj Vk Σk , pak můžeme psát
cos θj =
sj (UkT q) , j = 1, 2, . . . , n ||sj ||2 ||UkT q||2
(17)
Měříme tedy kosinovou vzdálenost mezi vektorem UkT q, což je promítnutí dotazovacího vektoru q do sloupcového prostoru Ak (hledáme tedy souřadnice dotazovacího vektoru ve sloupcovém prostoru Ak s bází Uk ) a n k-redukovanými vektory dokumentů. Příklad 11. Vezměme uživatelský dotaz z příkladu 6. Uživatel chce získat dokumenty relevantní k dotazovacímu dokumentu obsahujícímu pojmy XML a WWW. Nejprve vypočteme souřadnice dotazovacího vektoru ve sloupcovém prostoru A2 s bází U2 (promítneme dotazovací vektor do sloupcového prostoru matice A2 ): U2T q = [0.7428, 0.3834]T Kosinové vzdálenosti mezi dotazovacím vektorem U2T q a vektory dokumentů cos θj , pro 1 ≤ j ≤ 7: cos θ1 = −0.0063 cos θ5 = 0.6987
cos θ2 = 0.4132 cos θ6 = 0.6140
cos θ3 = 0.1097 cos θ7 = 0.6987
cos θ4 = 0.2694
Zvolením prahové hodnoty cos θt = 0.5 získáme relevantní dokumenty D5 , D6 a D7 .
Příklad 12. Nyní vezměme dotaz z příkladu 7. Uživatel chce získat dokumenty relevantní k dotazovacímu dokumentu obsahujícímu jediný term XML. Kosinové vzdálenosti mezi dotazovacím vektorem U2T q a vektory dokumentů cos θj , pro 1 ≤ j ≤ 7: cos θ1 = 0.1356 cos θ5 = 0.5539
cos θ2 = 0.4653 cos θ6 = 0.4072
cos θ3 = 0.2460 cos θ7 = 0.5539
cos θ4 = 0.3882
Pokud zvolíme cos θt = 0.4 získáme relevantní dokumenty D2 , D5 , D6 , D7 . Všimněme si zejména dokumentu D6 , který byl vybrán, přestože není charakterizován pojmem XML. Bezpochyby, pokud je charakterizován termy HTML a WWW je to, pro uživatele hledajícího dokumenty na téma XML, relevantní dokument.
Podívejme se nyní na matici Ak s hodností k, která aproximuje původní matici A. Na obrázku 8 vidíme aproximační matici s hodností 3 (A3 ) matice A z
obrázku 4. Vezměme dokument D6 a dotaz z příkladu 12, tedy dotaz obsahující jediný termín XML. Dokument D6 je charakterizován pojmy HTML a WWW. Pokud se podrobně podíváme na dokument D5 , který je charakterizován pojmy XML a WWW, a dokument D7 , charakterizovaný termy XML a HTML, vidíme, že mezi termy a dokumenty existují skryté vazby. Konkrétně z této vazby může vyplývat: pokud nás zajímají dokumenty o XML, pak může být relevantní i dokument D6 , který má s dokumenty D5 a D7 charakterizovanými pojmem XML společný pojem WWW resp. HTML. Zatímco v původním vektoru dokumentu D6 byla souřadnice určená pro term XML nulová, v tomto případě má hodnotu 0.4047 a tak pomocí kosinové vzdálenosti můžeme získat dokument D6 jako relevantní s dotazem charakterizovaným pojmem XML (srovnejme výsledky dotazů příkladů 7 a 12). Singulární rozklad poskytuje tuto zajímavou schopnost, schopnost zachytit takové skryté vazby mezi termy a dokumenty a umožňuje indexovat latentní (skrytou) sémantiku při redukci prostoru dokumentů.
0.1231 −0.1077 −0.0719 0.2100 = −0.1077 0.6087 −0.0719 0.1645 0.6087
A3 = U3 Σ3 V3T
0.4749 0.5281 0.0631 0.0384 0.5281 −0.0376 0.0631 0.2973 −0.0376
0.2563 0.5486 −0.1514 0.0350 0.5486 −0.0207 −0.1514 0.3246 −0.0207
0.3800 0.0947 0.0404 0.2103 0.0947 0.5423 0.0404 0.2555 0.5423
0.5529 0.0530 0.4403 0.0380 0.0529 0.0256 0.4403 0.0226 0.0257
0.4047 −0.1250 0.4758 −0.0124 −0.1251 −0.0718 0.4758 −0.12070 −0.07184
0.55290 0.05291 0.44025 0.03800 0.05291 0.02559 0.44025 0.02264 0.02559
Obrázek 8. Matice A3 s hodností 3 aproximující matici A.
3.3
Aktualizace
Předpokládejme, že máme existující LSI databázi. Tedy ze zadané kolekce dokumentů byla vytvořena matice klíčových slov v dokumentech a vypočten singulární rozklad této matice. Pokud nyní budeme chtít k takovéto existující LSI databázi přidat další dokumenty s možnými novými termy existují tři možnosti: nový výpočet SVD nové matice termů v dokumentech, SVD-updating a foldingin (tedy vkládání nových dokumentů a pojmů). Nový výpočet singulárního rozkladu se nedá považovat za metodu aktualizace. Zde si musíme uvědomit výpočetní náročnost singulárního rozkladu, zejména při reálně možných velikostech matice termů v dokumentech. Proto hledáme metody, které by se vyhnuly výpočtu celého singulárního rozkladu při vložení nových dokumentů a termů. Jednou z těchto metod je SVD-updating, což je poměrně nová metoda popsána v [Obr94] a [BDL95].
Vkládání Folding-in dokumentů nebo pojmů je mnohem jednodušší alternativa využití existující LSI databáze. Tato metoda je popsána v [BDL95]. Tato jednoduchost není ovšem samozřejmě zadarmo. Nové vektory dokumentů a pojmů jsou před přidáním do matic VkT resp. Uk promítnuty do prostoru redukovaných dokumentů resp. termů, čímž se promítne stav existující LSI databáze do těchto nových sloupcových resp. řádkových vektorů. Naopak to ovšem neplatí, tedy stav těchto nových vektorů není promítnut do existující LSI databáze, takže je jasné, že při takovéto změně LSI databáze vzniká určitá chyba. Použití této metody závisí zejména na počtu změn vůči velikosti existující databáze.
4
Testy a výsledky experimentů
Pro příklady použité v tomto článku a experimenty uvedené v této kapitole byla použita vlastní implementace vytvořená v programovacím jazyku C++. Pro implementaci výpočtu singulárních čísel byl použit balík SVDPACK ([Ber93]). Měření výkonu bylo provedeno na dvou testech. V prvním testu zjišťujeme, jaké relevantní dokumenty jsou vráceny pro různé hodnosti k aproximačních matic Ak , ve druhém testu bude měřen čas výpočtu singulárních čísel. 4.1
Relevantní dokumenty pro různé hodnosti matice Ak
Vezměme dotazy z příkladů 11 (dotaz obsahuje pojmy XML a WWW ) a 12 (dotaz obsahuje jediný pojem XML). Tabulka 1 obsahuje dokumenty relevantní k dotazu při použití různých aproximačních matic Ak , 2 ≤ k ≤ 7, prahová hodnota cos θt byla stanovena na 0.4. k 2 3 4 5 6 7
Dotaz 1 D2 , D 5 , D 6 , D5 , D 6 , D 7 D2 , D 5 , D 6 , D2 , D 5 , D 6 , D2 , D 5 , D 6 , D2 , D 5 , D 6 ,
D7 D7 D7 D7 D7
Dotaz 2 D2 , D5 , D6 , D2 , D5 , D6 , D2 , D 4 , D 5 , D2 , D 4 , D 5 , D2 , D 4 , D 5 , D2 , D 4 , D 5 ,
D7 D7 D7 D7 D7 D7
Tabulka 1. Dokumenty relevantní pro různé hodnoty k.
Vidíme, že pro všechny hodnoty k jsou relevantní dokumenty téměř totožné a že i pro velké redukce prostoru dokumentů dává metoda LSI uspokojivé výsledky. 4.2
Měření doby výpočtu singulárních čísel
V tomto testu bude měřena doba výpočtu singulárních čísel. Vstupem byla kolekce 82 dokumentů s celkově 384 termy (kolekce Bellcore ADI Linguistics Data).
Singulární čísla byla počítána pro matici termů v dokumentech 384 × 82. Měření bylo prováděno na počítači s procesorem AMD K6-II 430 MHz, 392MB paměti s operačním systémem Linux, jako překladač byl použit g++ 2.96. Singulární čísla byla počítána numerickou metodou Lanczos. Na obrázku 9 vidíme graf závislosti doby výpočtu singulárních čísel na počtu počítaných singulárních čísel. Maximální počet singulárních čísel pro tuto matici termů v dokumentech je min{384, 82} tedy 82. Vidíme, že výpočet 5 singulárních čísel trvá 1.22 s, výpočet 81 singulárních čísel 11.6 s.
time [s]
14
12
10
8
6
4
2 0
10
20
30
40
50
60 70 80 90 number of singular values
Obrázek 9. Doba výpočtu singulárních čísel metodou Lancozs.
Z testů vyplývá, že metoda LSI dává uspokojivé výsledky i pro poměrně nízké hodnosti k aproximační matice Ak . Výpočet singulárního rozkladu se provádí pouze při indexaci sady dokumentů a tak se výpočetní náročnost výpočtu rozkladu při výhodách poskytovaných touto metodou neukazuje jako nepřekonatelná překážka.
5
Závěr
V tomto článku byla popsána aplikace aparátu lineární algebry v oblasti Information Retrieval. Byl popsán vektorový model a singulární rozklad jako metoda indexování latentní sémantiky. Metoda SVD je schopna zachytit skryté vazby mezi termy a dokumenty při redukci vysoce-dimenzionálního prostoru, takže je schopna uživateli nabídnout dokumenty dle významu a ne pouze dle lexikálního obsahu, čímž přináší nový přístup do oblasti Information Retrieval. Metoda SVD se přímo nabízí pro další metody zpracovávání textů zejména pro svou schopnost redukovat možný vysoce-dimenzionální prostor. Je ovšem nutné podpořit nadějné výsledky drobných experimentů na skutečných a velkých kolekcích dokumentů.
Reference [Ber93] [BB99] [BDL95]
[Dos01]
[FB92] [GL96] [Kor97] [Kow97] [Obr94]
[PSH98] [Rij79] [SM83]
Berry M.W. et al: SVDPACKC: Version 1.0 User’s Guide. Tech. Rep. CS 93 194, University of Tennessee, Knoxville, TN, October 1993. Berry M.W., Browne M.: Understanding Search Engines, Mathematical Modeling and Text Retrieval. Siam, 1999. Berry M.W., Dumais S.T., Letsche T.A.: Computation Methods for Intelligent Information Access. Proceedings of the 1995 ACM/IEEE Supercomputing Conference, San Diego, California, USA, 1995, http://www.supercomp.org/sc95/proceedings/473_MBER/SC95.HTM, (červen 2002) Dostál Z.: Lineární algebra. Skriptum pro posluchače předmětu Lineární algebra. Fakulta elektrotechniky a informatiky, VŠB-Technická Univerzita Ostrava, ISBN 80–7078–832–1, Ostrava, 2001. Frakes W.B., Baeza-Yates R.: Information Retrieval: Data Structures & Algorithms. Prentice-Hall, Englewood Cliffs, NJ, 1992. Golub G., Loan Van C.: Matrix computations. third ed., Johns Hopkins University Press, Baltimore, 1996. Korfhage R.R.: Information Storage and Retrieval. John Wiley & Sons, Inc., New York, 1997. Kowalski G.: Information Retrieval Systems: Theory and Implementation. Kluwer Academic Publishers, Boston, MA, 1997. O’Brien G.W.: Information Management Tools for Updating an SVDEncoded Indexing Scheme. Master’s thesis, The University of Knoxville, Tennesse, Knoxville, TN, 1994. Pokorný J., Snášel V., Húsek D.: Dokumentografické informační systémy. Karolinum, Praha, 1998. van Rijsbergen C.: Information Retrieval, second ed., Butterworths, London, 1979. Salton G., McGill M.: Introduction to Modern Information Retrieval., McGraw-ill, New York, 1983.
