Utajona analiza semantyczna

Utajony analizy semantycznej ( LSA The English : utajone analiza semantyczna ) lub ukryte indeksowanie semantyczne (lub LSI , angielski: ukryte indeksowanie semantyczne ) jest procesem przetwarzania jzyka naturalnego , w ramach semantyki wektorowym . LSA zosta opatentowany w 1988 roku i opublikowany w 1990 roku .

Umoliwia ustalenie relacji midzy zbiorem dokumentów a zawartymi w nich terminami poprzez konstruowanie poj powizanych z dokumentami i terminami.

Macierz zdarze

LSA uywa macierzy opisujcej wystpowanie okrelonych terminów w dokumentach. Jest to rzadka macierz, której wiersze odpowiadaj terminom, a kolumny odpowiadaj dokumentom.

Terminy to na ogó sowa skrócone lub zredukowane do ich radykalnoci, wzite z caego korpusu. Dlatego mamy liczb wystpie sowa w kadym dokumencie i dla wszystkich sów. Liczb t normalizuje si za pomoc wagi tf-idf (z angielskiego : termin czsto - odwrotna czstotliwo dokumentu ), kombinacji dwóch technik: wspóczynnik macierzy jest tym wikszy, im wicej pojawia si w dokumencie, oraz e jest to rzadkie - aby je wysun.

Macierz ta jest powszechna w standardowych modelach semantycznych, takich jak model wektorowy , chocia jej forma macierzowa nie jest systematyczna, poniewa matematyczne waciwoci macierzy s rzadko uywane.

LSA przeksztaca macierz zdarze w zwizek midzy terminami i pojciami oraz zwizek midzy tymi pojciami a dokumentami. Dziki temu moemy czy dokumenty razem.

Aplikacje

Ta organizacja midzy terminami i pojciami jest zwykle uywana do:

porównanie dokumentów w przestrzeni pojciowej ( klasyfikacja i kategoryzacja dokumentów , podzia danych );
wyszukiwanie podobnych dokumentów w rónych jzykach dziki dostpowi do sownika dokumentów wielojzycznych;
poszukiwanie relacji midzy terminami (rozwizanie synonimii i polisemii );
po zapytaniu przetumaczy warunki zapytania w przestrzeni poj, aby znale semantycznie powizane dokumenty ( wyszukiwanie informacji );
znale najlepsze podobiestwo midzy maymi grupami terminów, semantycznie (tj. w kontekcie zbioru wiedzy), jak w modelowaniu odpowiedzi na kwestionariusze wielokrotnego wyboru (MCQ).

Rozwizanie synonimii i polisemii jest gównym problemem w automatycznym przetwarzaniu jzyka :

dwa synonimy opisuj ten sam pomys, wyszukiwarka mogaby zatem znale odpowiednie dokumenty, ale nie zawieraaby dokadnego terminu wyszukiwania;
polisemia zastosowanie rodków wyrazu, e ma kilka znacze w zalenoci od kontekstu - mona równie unikn dokumenty zawierajce wyszukiwane sowa, ale w akceptacji, która nie odpowiada temu, co kto chce lub pola rozpatrywane.

Redukcja rangi

Po skonstruowaniu macierzy zdarze LSA umoliwia znalezienie macierzy o niszym stopniu , co daje przyblienie tej macierzy zdarze. Moemy uzasadni to przyblienie kilkoma aspektami:

oryginalna macierz mogaby by zbyt dua na moliwoci obliczeniowe maszyny - to czyni proces wykonalnym i jest zem koniecznym -;
oryginalna matryca moe by zaszumiona: terminy pojawiaj si tylko anegdotycznie - matryca jest wic czyszczona, jest to operacja poprawiajca wyniki -;
mona zaoy, e oryginalna matryca jest zbyt rzadka: zawiera ona raczej sowa charakterystyczne dla kadego dokumentu ni terminy zwizane z kilkoma dokumentami - jest to równie problem synonimii.

Jednak zmniejszenie rangi macierzy wystpowania skutkuje poczeniem niektórych wymiarów, które mog nie mie znaczenia. Generalnie udaje nam si - o ile to moliwe - czy terminy o podobnych znaczeniach. Zatem redukcja rangi 3 do rangi 2 moe wpyn na transformacj:

{(Samochód), (Ciarówka), (Kwiat)} {(1.3452 × Samochód + 0,2828 × Ciarówka), (Kwiat)}

W ten sposób rozwizuje si synonimi. Ale czasami nie jest to moliwe. W takich przypadkach LSA moe wykona nastpujc transformacj:

{(Samochód), (Butelka), (Kwiat)} - {(1,3452 × Samochód + 0,2828 × Butelka), (Kwiat)}

To zgrupowanie jest znacznie trudniejsze do zinterpretowania - jest uzasadnione z matematycznego punktu widzenia, ale nie jest istotne dla osoby mówicej -.

Opis

Budowa macierzy wystpowania

Niech X bdzie matryc , w której element (i, j) opisuje wystpie pojcia w dokumencie j - na przykad czstotliwoci . Wtedy X bdzie wyglda tak:

${\ displaystyle {\ begin {matrix} i {\ 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}}}$

Wiersz tej macierzy jest wic wektorem, który odpowiada okreleniu, a którego skadniki okrelaj jego obecno (a raczej jego znaczenie) w kadym dokumencie:

${\ displaystyle {\ textbf {t}} _ {i} ^ {T} = {\ pocztek {pmatrix} x_ {ja, 1} i \ kropki i x_ {ja, n} \ koniec {pmatrix}}}$

Podobnie kolumna tej macierzy jest wektorem, który odpowiada dokumentowi, a którego skadniki maj znaczenie w treci kadego terminu.

${\ displaystyle {\ textbf {d}} _ {j} = {\ pocztek {pmatrix} x_ {1, j} \\\ vdots \\ x_ {m, j} \ koniec {pmatrix}}}$

Korelacje

Produkt kropka :

${\ Displaystyle {\ textbf {t}} _ {i} ^ {T} {\ textbf {t}} _ {p}}$

midzy dwoma wektorami terminów daje korelacj midzy dwoma wyrazami w caym korpusie. Iloczyn macierzy zawiera wszystkie iloczyn skalarny tej postaci: pozycja (i, p) - która jest tym samym co pozycja (p, i), poniewa macierz jest symetryczna - jest wic iloczynem skalarnym : ${\ displaystyle XX ^ {T}}$

${\ Displaystyle {\ textbf {t}} _ {i} ^ {T} {\ textbf {t}} _ {p}}$ ( ). ${\ displaystyle = {\ textbf {t}} _ {p} ^ {T} {\ textbf {t}} _ {i}}$

Podobnie iloczyn zawiera wszystkie iloczyny skalarne midzy wektorami dokumentu, które daj ich korelacje w caym leksykonie: ${\ displaystyle X ^ {T} X}$

${\ Displaystyle {\ textbf {d}} _ {j} ^ {T} {\ textbf {d}} _ {q} = {\ textbf {d}} _ {q} ^ {T} {\ textbf {d }} _ {j}}$ .

Rozkad wedug wartoci osobliwych

Nastpnie przeprowadza si rozkad na wartoci osobliwe na X , co daje dwie macierze ortonormalne U i V oraz macierz diagonaln . Mamy wtedy:

${\ Displaystyle {\ rozpocz {macierz} X = U \ Sigma V ^ {T} \ koniec {macierz}}}$

Produkty macierzowe, które daj korelacje midzy terminami z jednej strony i midzy dokumentami z drugiej strony, s nastpnie zapisywane:

${\ Displaystyle {\ rozpocz {macierz} 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}}}$

Poniewa matryce i s ukone, U jest wykonany z wektorów wasnych o i V jest wykonany z wektory wasne . Te dwa iloczyny maj wtedy takie same niezerowe wartoci wasne - które odpowiadaj niezerowym wspóczynnikom przektnej równoci . Dekompozycja jest nastpnie zapisywana: ${\ Displaystyle \ Sigma \ Sigma ^ {T}}$ ${\ displaystyle \ Sigma ^ {T} \ Sigma}$ ${\ displaystyle XX ^ {T}}$ ${\ displaystyle X ^ {T} X}$ ${\ Displaystyle \ Sigma \ Sigma ^ {T}}$

${\ displaystyle {\ begin {matrix} i X &&& U && \ Sigma && V ^ {T} \\ & ({\ textbf {d}} _ {j}) &&&&&&&&& ({\ hat {\ textbf {d}}) } _ {j}) \\ & \ downarrow &&&&&&& \ 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}} & = & ({\ 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}}}$

Wartoci s osobliwe wartoci X . Z drugiej strony wektory i s odpowiednio po lewej i po prawej stronie liczby pojedynczej. ${\ displaystyle \ sigma _ {1}, \ kropki, \ sigma _ {l}}$ ${\ displaystyle u_ {1}, \ kropki, u_ {l}}$ ${\ displaystyle v_ {1}, \ kropki, v_ {l}}$

Zauwa równie, e jedyn czci U, która si skada, jest i- ^ta linia. Teraz oznaczmy ten wektor . Podobnie jedyn czci, do której si przyczynia, jest j- ^ta kolumna, któr oznaczamy . ${\ displaystyle {\ textbf {t}} _ {i}}$ ${\ displaystyle {\ hat {\ textrm {t}}} _ {i}}$ ${\ displaystyle V ^ {T}}$ ${\ displaystyle {\ textbf {d}} _ {j}}$ ${\ displaystyle {\ hat {\ textrm {d}}} _ {j}}$

Przestrze koncepcyjna

Kiedy wybierzemy k najwikszych wartoci osobliwych, a take odpowiadajce im wektory osobliwe w U i V , otrzymamy przyblienie rzdu k macierzy zdarze.

Wan kwesti jest to, e dokonujc tego przyblienia, wektory terminy i dokumenty s tumaczone w przestrze poj.

Wektor ma wtedy k skadowych, z których kady nadaje znaczenie czonowi i w kadym z k rónych poj. Podobnie wektor okrela intensywno relacji midzy dokumentem j a kadym pojciem. Piszemy to przyblienie w nastpujcej formie: ${\ displaystyle {\ hat {\ textbf {t}}} _ {i}}$ ${\ displaystyle {\ hat {\ textbf {d}}} _ {j}}$

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

Nastpnie mona wykona nastpujce operacje:

zobacz, w jakim stopniu dokumenty j i q s powizane w przestrzeni pojciowej, porównujc wektory i . Moemy to zrobi, oceniajc podobiestwo cosinusowe . ${\ displaystyle \ Sigma _ {k} {\ hat {\ textbf {d}}} _ {j}}$ ${\ displaystyle \ Sigma _ {k} {\ hat {\ textbf {d}}} _ {q}}$

porównaj wyraenia i i p , porównujc wektory i t sam metod; ${\ displaystyle {\ hat {\ textbf {t}}} _ {i}}$ ${\ displaystyle {\ hat {\ textbf {t}}} _ {p}}$

po zadaniu zapytania moemy potraktowa je jako mini-dokument i porówna w przestrzeni koncepcyjnej z korpusem, aby zbudowa list najwaniejszych dokumentów. Aby to zrobi, musisz ju przetumaczy zapytanie na przestrze pojciow, przeksztacajc je w taki sam sposób, jak dokumenty. Jeli zapytaniem jest q , musimy obliczy:

${\ displaystyle {\ hat {\ textbf {q}}} = \ Sigma _ {k} ^ {- 1} U_ {k} ^ {T} {\ textbf {q}}}$ przed porównaniem tego wektora z korpusem.

Wdroenia

Dekompozycja na wartoci osobliwych s zazwyczaj obliczane metodami optymalizacji duych matryc - na przykad algorytm lanczos - programy iteracyjnych, a nawet sieci neuronowych , to ostatnie podejcie nie wymaga tylko caa matryca jest przechowywany w pamici.

Ograniczenia

Limity LSA obejmuj:

te z modelu worka sów , na którym jest oparty, gdzie tekst jest przedstawiany jako nieuporzdkowany zestaw sów;

niemono (w modelu podstawowym) uwzgldnienia polisemii (czyli wieloznacznoci sowa), poniewa sowo odpowiada tylko jednemu punktowi przestrzeni semantycznej.

Probabilistyczna utajona analiza semantyczna (PLSA)

Model statystyczny ukrytej analizy semantycznej nie odpowiada obserwowanym danym: zakada, e sowa i dokumenty razem tworz model Gaussa (jest to hipoteza ergodyczna ), podczas gdy obserwowany jest rozkad Poissona .

Zatem nowszym podejciem jest probabilistyczna utajona analiza semantyczna lub PLSA (z angielskiego: Probabilistic latent semantic analysis ), oparta na modelu wielomianowym .

Uwagi i odniesienia

(fr) Ten artyku jest czciowo lub w caoci zaczerpnity z artykuu Wikipedii w jzyku angielskim zatytuowanego Latent semantic analysis ( zobacz list autorów ) .

(w) Zgoszenie patentu Scott Deerwester, Susan Dumais, George Furnas, Richard Harshman, Thomas Landauer, Karen Lochbaum i Lynn Streeter.

(w :) Scott Deerwester, Susan Dumais, George W. Furnas, Thomas K. Landauer, Richard Harshman, Indexing by Latent Semantic Analysis , Journal of the Society for Information Science , vol. 41, n ^o 6,1990, s. 391-407 ( czytaj online ).

(w) Alain Lifshitz, Sandra Jhean-Larose, Guy Denhière, Efekt roku, w którym dostroilimy parametry na pytanie wielokrotnego wyboru w odpowiedzi na model LSA , Metody bada behawioralnych, metody bada behawioralnych, tom. 41, n ^o 4,2009, s. 1201-1209 ( PMID 19897829 , DOI 10.3758 / BRM.41.4.1201 , czytaj online ).

Moemy nawet wykaza, e jest to najlepsze przyblienie w sensie normy Frobeniusa. Dowód podano w artykule o rozkadzie na wartoci osobliwe .

(w) Genevieve Brandyn Gorrell i Webb (2005). Uogólniony algorytm hebrajski dla ukrytej analizy semantycznej Interspeech'2005 . .

Zaczniki

Bibliografia

(en) Strona domowa The Latent Semantic Indexing , University of Colorado;

(en) Thomas K. Landauer, Peter W. Foltz i Darrell Laham, Introduction to Latent Semantic Analysis , Discourse Processes , vol. 25,1998, s. 259-284 ( DOI 10.1080 / 01638539809545028 , czytaj online )

(en) Michael W. Berry, Susan T. Dumais, Gavin W. O'Brien, Using Linear Algebra for Intelligent Information Retrieval , SIAM Review , vol. 37, n ^o 4,Grudzie 1995, s. 573-595 ( czytaj online ) (PDF) .

(en) Ukryta analiza semantyczna , InfoVis

(en) Thomas Hofmann, Probabilistic Latent Semantic Analysis , Uncertainty in Artificial Intelligence, 1999.

(en) Fridolin Wild, An Open Source LSA Package for R , CRAN,2 lipca 2014(dostp 2 grudnia 2014 )

(en) Dimitrios Zeimpekis i E. Gallopoulos, » Zestaw narzdzi MATLAB do generowania macierzy termin-dokument ze zbiorów tekstów « ,11 wrzenia 2005(dostp 20 listopada 2006 )

Powizane artykuy

Semantyka wektorów

Rozkad wedug wartoci osobliwych

model tematyczny

Link zewntrzny

( fr ) The Semantic Indexing Project , projekt open source dotyczcy ukrytego indeksowania semantycznego.

[1] (w) Zgoszenie patentu Scott Deerwester, Susan Dumais, George Furnas, Richard Harshman, Thomas Landauer, Karen Lochbaum i Lynn Streeter.

[2] (w :) Scott Deerwester, Susan Dumais, George W. Furnas, Thomas K. Landauer, Richard Harshman, Indexing by Latent Semantic Analysis , Journal of the Society for Information Science , vol. 41, n ^o 6,1990, s. 391-407 ( czytaj online ).

[3] (w) Alain Lifshitz, Sandra Jhean-Larose, Guy Denhière, Efekt roku, w którym dostroilimy parametry na pytanie wielokrotnego wyboru w odpowiedzi na model LSA , Metody bada behawioralnych, metody bada behawioralnych, tom. 41, n ^o 4,2009, s. 1201-1209 ( PMID 19897829 , DOI 10.3758 / BRM.41.4.1201 , czytaj online ).

[4] Moemy nawet wykaza, e jest to najlepsze przyblienie w sensie normy Frobeniusa. Dowód podano w artykule o rozkadzie na wartoci osobliwe .

[5] (w) Genevieve Brandyn Gorrell i Webb (2005). Uogólniony algorytm hebrajski dla ukrytej analizy semantycznej Interspeech'2005 . .

Utajona analiza semantyczna

streszczenie

Macierz zdarze

Aplikacje

Redukcja rangi

Opis

Budowa macierzy wystpowania

Korelacje

Rozkad wedug wartoci osobliwych

Przestrze koncepcyjna

Wdroenia

Ograniczenia

Probabilistyczna utajona analiza semantyczna (PLSA)

Uwagi i odniesienia

Zaczniki

Bibliografia

Powizane artykuy

Link zewntrzny

Opiniones de nuestros usuarios

Krzysztof Maciejewski

Michael Nowacki

Lukas Dudek

Enciclo

Sapientia

Scientia

Boobota