Latentní sémantická analýza

Latentní sémantická analýza ( LSA je anglicky : Latentní sémantická analýza ), nebo latentní sémantické indexování (nebo LSI , anglicky: latentní sémantické indexování ) je proces zpracování přirozeného jazyka , jako součást sémantiky Vector . LSA byl patentován v roce 1988 a publikován v roce 1990 .

Umožňuje vytvořit vztahy mezi sadou dokumentů a pojmy, které obsahují, vytvořením „konceptů“ souvisejících s dokumenty a pojmy.

Matice výskytů

LSA používá matici, která popisuje výskyt určitých termínů v dokumentech. Jedná se o řídkou matici, jejíž řádky odpovídají „výrazům“ a jejichž sloupce odpovídají „dokumentům“.

„Termíny“ jsou obecně slova zkrácená nebo zredukovaná na jejich radikál převzatá z celého korpusu. Proto máme v každém dokumentu počet výskytů slova a pro všechna slova. Toto číslo je normalizováno pomocí vážení tf-idf (z angličtiny : termín frekvence - inverzní frekvence dokumentu ), kombinace dvou technik: koeficient matice je tím větší, čím více se v dokumentu objeví, a že je vzácné - předložit je.

Tato matice je běžná ve standardních sémantických modelech, jako je vektorový model , i když její maticová forma není systematická, protože matematické vlastnosti matic se používají jen zřídka.

LSA transformuje matici výskytů na „vztah“ mezi pojmy a „koncepty“ a vztah mezi těmito pojmy a dokumenty. Můžeme tedy dokumenty propojit.

Aplikace

Tato organizace mezi pojmy a koncepty se obecně používá pro:

komparace dokumentů v koncepčním prostoru ( klasifikace a kategorizace dokumentů , rozdělení dat );
vyhledávání podobných dokumentů mezi různými jazyky tím, že má přístup ke slovníku vícejazyčných dokumentů;
hledání vztahů mezi pojmy (rozlišení synonymie a polysémie );
zadaný dotaz, přeložit pojmy dotazu v koncepčním prostoru, najít sémanticky propojené dokumenty ( vyhledávání informací );
najít nejlepší podobnost mezi malými skupinami termínů, sémanticky (tj. v kontextu souboru znalostí), jako při modelování odpovědí na dotazníky s výběrem odpovědí (MCQ).

Rozlišení synonymie a polysémie je hlavním problémem automatického zpracování jazyka :

dvě synonyma popisují stejnou myšlenku, vyhledávač by tak mohl najít relevantní dokumenty, ale neobsahující přesný termín vyhledávání;
polysémie slova znamená, že má několik významů v závislosti na kontextu - by bylo možné vyhnout se rovněž dokumenty, které obsahují hledané slovo, ale v akceptaci, které neodpovídá co jeden přání nebo na pole v úvahu.

Snížení hodnosti

Po zkonstruování matice výskytů umožňuje LSA najít matici nižšího řádu , která poskytuje aproximaci této matice výskytů. Tuto aproximaci můžeme ospravedlnit několika aspekty:

původní matice může být příliš velká pro výpočetní kapacitu stroje - díky tomu je proces proveditelný a je to „nutné zlo“ -;
původní matice může být „hlučná“: výrazy, které se objevují pouze anekdoticky - matice je tedy „vyčištěna“, jedná se o operaci, která zlepšuje výsledky -;
lze předpokládat, že původní matice je „příliš řídká“: obsahuje spíše slova specifická pro každý dokument než výrazy spojené s několika dokumenty - to je také problém synonymie.

Snížení pořadí matice výskytu má však účinek kombinace některých dimenzí, které nemusí být relevantní. Obecně se nám podaří - pokud je to možné - sloučit termíny s podobným významem. Snížení z pozice 3 na pozici 2 tedy může ovlivnit transformaci:

{(Car), (Truck), (Flower)} → {(1.3452 × Car + 0.2828 × Truck), (Flower)}

Synonymie je vyřešena tímto způsobem. Ale někdy to není možné. V těchto případech může LSA provést následující transformaci:

{(Auto), (Láhev), (Květina)} - → {(1,3452 × Auto + 0,2828 × Láhev), (Květ)}

Toto seskupení je mnohem obtížnější interpretovat - je to oprávněné z matematického hlediska, ale není relevantní pro lidského mluvčího -.

Popis

Konstrukce matice výskytu

Nechť X je matice, kde prvek (i, j) popisuje výskyty termínu i v dokumentu j - například frekvenci . Pak X bude vypadat takto:

{\ displaystyle {\ begin {matrix} & {\ textbf {d}} _ {j} \\ & \ downarrow \\ {\ textbf {t}} _ {i} ^ {T} \ rightarrow & {\ begin { pmatrix} x_ {1,1} & \ dots & x_ {1, n} \\\ vdots & \ ddots & \ vdots \\ x_ {m, 1} & \ dots & x_ {m, n} \\\ end {pmatrix}} \ end {matrix}}}

Řádek této matice je tedy vektor, který odpovídá pojmu a jehož komponenty dávají jeho přítomnost (nebo spíše jeho důležitost) v každém dokumentu:

{\ displaystyle {\ textbf {t}} _ {i} ^ {T} = {\ begin {pmatrix} x_ {i, 1} & \ dots & x_ {i, n} \ end {pmatrix}}}

Podobně sloupec této matice je vektor, který odpovídá dokumentu a jehož komponenty jsou důležité v jeho vlastním obsahu každého výrazu.

{\ displaystyle {\ textbf {d}} _ {j} = {\ begin {pmatrix} x_ {1, j} \\\ vdots \\ x_ {m, j} \ end {pmatrix}}}

Korelace

Skalární součin :

{\ displaystyle {\ textbf {t}} _ {i} ^ {T} {\ textbf {t}} _ {p}}

mezi dvěma „ členy “ vektory dává korelaci mezi dvěma členy v celém korpusu. Maticový produkt obsahuje všechny tečkové produkty této formy: položka (i, p) - která je stejná jako položka (p, i), protože matice je symetrická - je tedy bodový produkt: ${\ displaystyle XX ^ {T}}$

{\ displaystyle {\ textbf {t}} _ {i} ^ {T} {\ textbf {t}} _ {p}}

( ).

{\ displaystyle = {\ textbf {t}} _ {p} ^ {T} {\ textbf {t}} _ {i}}

Podobně produkt obsahuje všechny skalární produkty mezi vektory „dokumentu“, které dávají své korelace v celé lexikonu: ${\ displaystyle X ^ {T} X}$

{\ displaystyle {\ textbf {d}} _ {j} ^ {T} {\ textbf {d}} _ {q} = {\ textbf {d}} _ {q} ^ {T} {\ textbf {d }} _ {j}}

Rozklad singulární hodnoty

Jeden pak provede rozklad v singulárních hodnotách na X , což dá dvě ortonormální matice U a V a diagonální matici Σ . Pak máme:

{\ displaystyle {\ begin {matrix} X = U \ Sigma V ^ {T} \ end {matrix}}}

Potom se zapíší maticové produkty, které dávají korelace mezi pojmy na jedné straně a mezi dokumenty na straně druhé:

{\ displaystyle {\ begin {matrix} XX ^ {T} & = & (U \ Sigma V ^ {T}) (U \ Sigma V ^ {T}) ^ {T} = (U \ Sigma V ^ {T }) (V ^ {T ^ {T}} \ Sigma ^ {T} U ^ {T}) = U \ Sigma V ^ {T} V \ Sigma ^ {T} U ^ {T} = U \ Sigma \ Sigma ^ {T} U ^ {T} \\ X ^ {T} X & = & (U \ Sigma V ^ {T}) ^ {T} (U \ Sigma V ^ {T}) = (V ^ { T ^ {T}} \ Sigma ^ {T} U ^ {T}) (U \ Sigma V ^ {T}) = V \ Sigma ^ {T} U ^ {T} U \ Sigma V ^ {T} = V \ Sigma ^ {T} \ Sigma V ^ {T} \ end {matrix}}}

Vzhledem k tomu, že matice a jsou diagonální, U je vyroben z vektorů v , a V je vyrobena z charakteristických vektorů . Oba produkty pak mají stejné nenulové vlastní hodnoty - což odpovídá nenulovým diagonálním koeficientům . Rozklad se pak zapíše: ${\ displaystyle \ Sigma \ Sigma ^ {T}}$ ${\ displaystyle \ Sigma ^ {T} \ Sigma}$ ${\ displaystyle XX ^ {T}}$ ${\ displaystyle X ^ {T} X}$ ${\ displaystyle \ Sigma \ Sigma ^ {T}}$

{\ displaystyle {\ begin {matrix} & X &&& U && \ Sigma && V ^ {T} \\ & ({\ textbf {d}} _ {j}) &&&&&&&& ({\ hat {\ textbf {d}} } _ {j}) \\ & \ downarrow &&&&&&&& \ downarrow \\ ({\ textbf {t}} _ {i} ^ {T}) \ rightarrow & {\ begin {pmatrix} x_ {1,1} & \ tečky & x_ {1, n} \\\\\ vdots & \ ddots & \ vdots \\\\ x_ {m, 1} & \ dots & x_ {m, n} \\\ end {pmatrix}} & = & ({\ hat {\ textbf {t}}} _ {i} ^ {T}) \ rightarrow & {\ begin {pmatrix} {\ begin {pmatrix} \, \\\, \\ {\ textbf {u }} _ {1} \ \\, \\\, \ end {pmatrix}} \ dots {\ begin {pmatrix} \, \\\, \\ {\ textbf {u}} _ {l} \\\ , \\\, \ end {pmatrix}} \ end {pmatrix}} & \ cdot & {\ begin {pmatrix} \ sigma _ {1} & \ dots & 0 \\\ vdots & \ ddots & \ vdots \\ 0 & \ dots & \ sigma _ {l} \\\ end {pmatrix}} & \ cdot & {\ begin {pmatrix} {\ begin {pmatrix} && {\ textbf {v}} _ {1} && \ end {pmatrix}} \\\ vdots \ \ {\ begin {pmatrix} && {\ textbf {vb}} _ {l} && \ end {pmatrix}} \ end {pmatrix}} \ end {matrix}}}

Hodnoty jsou singulární hodnoty X . Na druhou stranu, vektory a jsou respektive levý a pravý singulární. $\ sigma _ {1}, \ dots, \ sigma _ {l}$ ${\ displaystyle u_ {1}, \ tečky, u_ {l}}$ ${\ displaystyle v_ {1}, \ tečky, v_ {l}}$

Všimněte si také, že jedinou částí U, která přispívá, je i- tý řádek. Nyní označujeme tento vektor . Podobně jediná část, ke které přispívá, je j- tý sloupec, který označujeme . ${\ displaystyle {\ textbf {t}} _ {i}}$ ${\ displaystyle {\ hat {\ textrm {t}}} _ {i}}$ ${\ displaystyle V ^ {T}}$ ${\ displaystyle {\ textbf {d}} _ {j}}$ ${\ displaystyle {\ hat {\ textrm {d}}} _ {j}}$

Koncept prostor

Když vybereme k největší singulární hodnoty, stejně jako odpovídající singulární vektory v U a V , získáme aproximaci hodnosti k matice výskytů.

Důležité je, že touto aproximací se vektory „pojmy“ a „dokumenty“ převedou do prostoru „pojmů“.

Vektor má potom k komponent, z nichž každá dává důležitost termínu i v každém z k různých „konceptů“. Podobně vektor udává intenzitu vztahů mezi dokumentem j a každým konceptem. Tuto aproximaci píšeme v následující podobě: ${\ displaystyle {\ hat {\ textbf {t}}} _ {i}}$ ${\ displaystyle {\ hat {\ textbf {d}}} _ {j}}$

{\ displaystyle X_ {k} = U_ {k} \ Sigma _ {k} V_ {k} ^ {T}}

Poté lze provést následující operace:

porovnejte vektory a, abyste zjistili, do jaké míry jsou dokumenty j a q v koncepčním prostoru příbuzné . Můžeme to udělat vyhodnocením kosinové podobnosti . ${\ displaystyle \ Sigma _ {k} {\ hat {\ textbf {d}}} _ {j}}$ ${\ displaystyle \ Sigma _ {k} {\ hat {\ textbf {d}}} _ {q}}$

porovnat pojmy i a p porovnáním vektorů a stejnou metodou; ${\ displaystyle {\ hat {\ textbf {t}}} _ {i}}$ ${\ displaystyle {\ hat {\ textbf {t}}} _ {p}}$
zadaný dotaz, můžeme s ním zacházet jako s „mini-dokumentem“ a porovnat jej v konceptuálním prostoru s korpusem, abychom vytvořili seznam nejdůležitějších dokumentů. Chcete-li to provést, musíte již přeložit dotaz do konceptuálního prostoru a transformovat jej stejným způsobem jako dokumenty. Pokud je dotaz q , musíme vypočítat:

{\ displaystyle {\ hat {\ textbf {q}}} = \ Sigma _ {k} ^ {- 1} U_ {k} ^ {T} {\ textbf {q}}}

před porovnáním tohoto vektoru s korpusem.

Implementace

Rozklad na singulární hodnoty se obvykle počítá metodami optimalizovanými pro velké matice - například na algoritmu lanczos - iteračními programy, nebo dokonce neuronových sítí , druhý přístup nevyžaduje pouze celá matrice se udržuje v paměti.

Omezení

Limity LSA zahrnují:

ty modelu slovního vaku , na kterém je založen, kde je text reprezentován jako neuspořádaná sada slov;
nemožnost (v základním modelu) zohlednění polysémie (tj. více významů slova), protože slovo odpovídá pouze jedinému bodu v sémantickém prostoru.

Pravděpodobnostní latentní sémantická analýza (PLSA)

Statistický model latentní sémantické analýzy neodpovídá pozorovaným údajům: předpokládá, že slova a dokumenty společně tvoří Gaussův model (jedná se o ergodickou hypotézu ), zatímco je pozorováno Poissonovo rozdělení .

Novějším přístupem je tedy pravděpodobnostní latentní sémantická analýza neboli PLSA (z angličtiny: Probabilistic latent semantic analysis ) založená na multinomálním modelu .

Poznámky a odkazy

(fr) Tento článek je částečně nebo zcela převzat z článku Wikipedie v angličtině s názvem „ Latentní sémantická analýza “ ( viz seznam autorů ) .

(in) Podání patentu Scott Deerwester, Susan Dumais, George Furnas, Richard Harshman, Thomas Landauer, Karen Lochbaum a Lynn Streeter.
(in) Scott Deerwester, Susan Dumais, George W. Furnas, Thomas K. Landauer, Richard Harshman, „ Indexing by Latent Semantic Analysis “ , Journal of the Society for Information Science , sv. 41, n O 6,1990, str. 391-407 ( číst online ).
(in) Alain Lifshitz, Sandra Jhean-Larose, Guy Denhière, „ Effect of the year we tuned parameters multiple choice question answering LSA model “ , Behavior Research Methods , Behavior Research Methods, vol. 41, n O 4,2009, str. 1201-1209 ( PMID 19897829 , DOI 10,3758 / BRM.41.4.1201 , číst online ).
Můžeme dokonce ukázat, že je to nejlepší aproximace ve smyslu Frobeniovy normy. Důkaz je uveden v článku o rozkladu singulární hodnoty .
(in) Genevieve Brandyn Gorrell and Webb (2005). „ Zobecněný hebobský algoritmus pro latentní sémantickou analýzu “ Interspeech'2005 . .

Dodatky

Bibliografie

(en) Domovská stránka latentního sémantického indexování , University of Colorado;
(en) Thomas K. Landauer, Peter W. Foltz a Darrell Laham, „ Úvod do latentní sémantické analýzy “ , Discourse Processes , sv. 25,1998, str. 259-284 ( DOI 10.1080 / 01638539809545028 , číst online )
(en) Michael W. Berry, Susan T. Dumais, Gavin W. O'Brien, „ Používání lineární algebry pro inteligentní získávání informací “ , SIAM Review , sv. 37, n O 4,Prosince 1995, str. 573-595 ( číst online ) (PDF) .
(en) „ Latentní sémantická analýza “ , InfoVis
(en) Thomas Hofmann, Pravděpodobnostní latentní sémantická analýza , Nejistota v umělé inteligenci, 1999.
(en) Fridolin Wild, „ Open Source LSA Package for R “ , CRAN,2. července 2014(zpřístupněno 2. prosince 2014 )
(en) Dimitrios Zeimpekis a E. Gallopoulos, „ Sada nástrojů MATLAB pro generování matic termínových dokumentů z textových sbírek “ ,11. září 2005(zpřístupněno 20. listopadu 2006 )

Související články

Externí odkaz

( fr ) Projekt sémantického indexování, projekt sémantického indexování s otevřeným zdrojem .