Utajona analiza semantyczna - Latent semantic analysis

Utajona analiza semantyczna ( LSA ) to technika przetwarzania języka naturalnego , w szczególności semantyki dystrybucyjnej , polegająca na analizowaniu relacji między zbiorem dokumentów a zawartymi w nich terminami poprzez tworzenie zbioru pojęć związanych z dokumentami i terminami. LSA zakłada, że słowa o zbliżonym znaczeniu wystąpią w podobnych fragmentach tekstu ( hipoteza dystrybucyjna ). Macierz zawierająca liczbę słów na dokument (wiersze reprezentują unikalne słowa, a kolumny reprezentują każdy dokument) jest zbudowana z dużego fragmentu tekstu, a do zmniejszenia liczby wierszy przy zachowaniu struktury podobieństwa używana jest technika matematyczna zwana rozkładem według wartości pojedynczych (SVD). wśród kolumn. Dokumenty są następnie porównywane przez pobranie cosinusa kąta między dwoma wektorami (lub iloczynu skalarnego między normalizacjami dwóch wektorów) utworzonego przez dowolne dwie kolumny. Wartości bliskie 1 reprezentują bardzo podobne dokumenty, a wartości bliskie 0 reprezentują bardzo różne dokumenty.

Technika wyszukiwania informacji wykorzystująca ukrytą strukturę semantyczną została opatentowana w 1988 r. ( Patent US 4,839,853 , obecnie nieważny) przez Scotta Deerwestera , Susan Dumais , George'a Furnasa , Richarda Harshmana , Thomasa Landauera , Karen Lochbaum i Lynn Streeter . W kontekście jego zastosowania do wyszukiwania informacji , jest to czasami nazywane ukrytym indeksowaniem semantycznym ( LSI ).

Przegląd

Animacja procesu wykrywania tematu w macierzy dokument-słowo. Każda kolumna odpowiada dokumentowi, każdy wiersz słowu. Komórka przechowuje wagę słowa w dokumencie (np. przez tf-idf ), ciemne komórki oznaczają wysokie wagi. LSA grupuje zarówno dokumenty zawierające podobne słowa, jak i słowa występujące w podobnym zestawie dokumentów. Powstałe wzory są wykorzystywane do wykrywania ukrytych komponentów.

Macierz występowania

LSA może używać matrycy terminów dokumentu, która opisuje występowanie terminów w dokumentach; jest to macierz rzadka, której wiersze odpowiadają terminom, a kolumny odpowiadają dokumentom. Typowym przykładem ważenia elementów macierzy jest tf-idf (częstotliwość terminów – odwrotna częstotliwość dokumentów): waga elementu macierzy jest proporcjonalna do liczby wystąpień terminów w każdym dokumencie, przy czym terminy rzadkie są ważone w celu odzwierciedlenia ich względnego znaczenia.

Ta macierz jest również wspólna dla standardowych modeli semantycznych, chociaż niekoniecznie jest wyraźnie wyrażona jako macierz, ponieważ matematyczne właściwości macierzy nie zawsze są używane.

Obniżenie rangi

Po zbudowaniu macierzy występowania LSA znajduje aproksymację niskiego rzędu do macierzy term-document . Przyczyny tych przybliżeń mogą być różne:

Zakłada się, że oryginalna macierz dokumentów terminów jest zbyt duża dla zasobów obliczeniowych; w tym przypadku przybliżona macierz niskiego rzędu jest interpretowana jako aproksymacja („najmniejsze i konieczne zło”).
Zakłada się, że pierwotna macierz terminów-dokumentu jest zaszumiona : na przykład anegdotyczne przypadki terminów mają zostać wyeliminowane. Z tego punktu widzenia macierz aproksymowana jest interpretowana jako macierz odszumiona (lepsza macierz niż pierwotna).
Zakłada się, że oryginalna macierz term-dokumentu jest zbyt rzadka w stosunku do „prawdziwej” macierzy term-dokumentu. Oznacza to, że oryginalna macierz zawiera tylko słowa faktycznie w każdym dokumencie, podczas gdy możemy być zainteresowani wszystkimi słowami związanymi z każdym dokumentem — na ogół znacznie większym zbiorem ze względu na synonimię .

Konsekwencją obniżenia rangi jest to, że niektóre wymiary są łączone i zależą od więcej niż jednego terminu:

{(samochód), (ciężarówka), (kwiat)} --> {(1,3452 * samochód + 0,2828 * ciężarówka), (kwiat)}

Zmniejsza to problem identyfikacji synonimii, ponieważ oczekuje się, że obniżenie rangi połączy wymiary związane z terminami o podobnym znaczeniu. Częściowo łagodzi również problem polisemii , ponieważ składowe słów polisemicznych , które wskazują we „właściwym” kierunku, są dodawane do składowych słów o podobnym znaczeniu. Odwrotnie, elementy wskazujące w innych kierunkach mają tendencję do albo po prostu znoszenia się, albo, w najgorszym przypadku, do bycia mniejszymi niż elementy w kierunkach odpowiadających zamierzonemu sensowi.

Pochodzenie

Niech będzie macierzą, w której element opisuje wystąpienie terminu w dokumencie (może to być np. częstotliwość). będzie wyglądać tak: ${\ Displaystyle X}$ ${\ Displaystyle (i, j)}$ $i$ $j$ ${\ Displaystyle X}$

{\ Displaystyle {\ zacząć {macierz} i {\ textbf {d}} _ {j} \ \ & \ downarrow \ \ {\ textbf {t}} _ {i} ^ {T} \ rightarrow i {\ zacząć { bmatrix}x_{1,1}&\dots &x_{1,j}&\dots &x_{1,n}\\\vdots &\ddots &\vdots &\ddots &\vdots \\x_{i,1} &\dots &x_{i,j}&\dots &x_{i,n}\\\vdots &\ddots &\vdots &\ddots &\vdots \\x_{m,1}&\dots &x_{m,j }&\dots &x_{m,n}\\\end{bmatryca}}\end{macierz}}}

Teraz wiersz w tej macierzy będzie wektorem odpowiadającym terminowi, podając jego związek z każdym dokumentem:

{\ Displaystyle {\ textbf {t}} _ {i} ^ {T} = {\ zacząć {bmatrix} x_ {i, 1} i \ kropki & x_ {i, j} i \ kropki & x_ {i, n} \ koniec{bmatryca}}}

Podobnie kolumna w tej macierzy będzie wektorem odpowiadającym dokumentowi, podając jego związek z każdym terminem:

{\ Displaystyle {\ textbf {d}} _ {j} = {\ zacząć {bmatrix} x_ {1, j} \ \ \ vdots \ \ x_ {i, j} \ \ \ vdots \ \ x_ {m, j }\\\koniec{bmatrycy}}}

Teraz iloczyn skalarny między dwoma wektorami terminów daje korelację między terminami w zestawie dokumentów. Produkt matryca zawiera wszystkie te produkty kropka. Element (który jest równy elementowi ) zawiera iloczyn skalarny ( ). Podobnie macierz zawiera iloczyny skalarne między wszystkimi wektorami dokumentu, podając ich korelację z terminami: . ${\ Displaystyle {\ textbf {t}} _ {i} ^ {T} {\ textbf {t}} _ {p}}$ ${\ Displaystyle XX ^ {T}}$ $(i,p)$ $(p,i)$ ${\ Displaystyle {\ textbf {t}} _ {i} ^ {T} {\ textbf {t}} _ {p}}$ ${\ Displaystyle = {\ textbf {t}} _ {p} ^ {T} {\ textbf {t}} _ {i}}$ ${\ Displaystyle X ^ {T} X}$ ${\ Displaystyle {\ textbf {d}} _ {j} ^ {T} {\ textbf {d}} _ {q} = {\ textbf {d}} _ {q} ^ {T} {\ textbf {d }}_{J}}$

Teraz, z teorii algebry liniowej, istnieje rozkład takich, że i są macierzami ortogonalnymi i jest macierzą diagonalną . Nazywa się to rozkładem według wartości osobliwych (SVD): ${\ Displaystyle X}$ ${\ Displaystyle U}$ ${\ Displaystyle V}$ ${\ Displaystyle \ Sigma}$

{\ Displaystyle {\ zacząć {macierz} X = U \ Sigma V ^ {T} \ koniec {macierz}}}

Produkty macierzowe dające nam korelacje terminów i dokumentów stają się:

{\ Displaystyle {\ zacząć {macierz} XX ^ {T} i = (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{macierz}}}

Ponieważ i to przekątna widzimy, że musi zawierać wektorów własnych o , natomiast musi być wektory własne . Oba produkty mają te same niezerowe wartości własne, podane przez niezerowe wpisy w , lub w równym stopniu przez niezerowe wpisy w . Teraz rozkład wygląda tak: ${\ Displaystyle \ Sigma \ Sigma ^ {T}}$ ${\ Displaystyle \ Sigma ^ {T} \ Sigma}$ ${\ Displaystyle U}$ ${\ Displaystyle XX ^ {T}}$ ${\ Displaystyle V}$ ${\ Displaystyle X ^ {T} X}$ ${\ Displaystyle \ Sigma \ Sigma ^ {T}}$ ${\ Displaystyle \ Sigma ^ {T} \ Sigma}$

{\ Displaystyle {\ zacząć {macierz} & X & & & & U & \ Sigma & & V ^ {T} \ \ & ({\ textbf {d}} _ {j}) & & & & & & & & & ({\ kapelusz {\ textbf {d}}} _ {j} )\\&\downarrow &&&&&&&\downarrow \\({\textbf {t}}_{i}^{T})\rightarrow &{\begin{bmatrix}x_{1,1}&\dots &x_{1, j}&\dots &x_{1,n}\\\vdots &\ddots &\vdots &\ddots &\vdots \\x_{i,1}&\dots &x_{i,j}&\dots &x_{i ,n}\\\vdots &\ddots &\vdots &\ddots &\vdots \\x_{m,1}&\dots &x_{m,j}&\dots &x_{m,n}\\\end{ bmatrix}}&=&({\hat {\textbf {t}}}_{i}^{T})\rightarrow &{\begin{bmatrix}{\begin{bmatrix}\,\\\,\\ {\textbf {u}}_{1}\\\,\\\,\end{bmatrix}}\dots {\begin{bmatrix}\,\\\,\\{\textbf {u}}_{ l}\\\,\\\,\end{bmatrix}}\end{bmatrix}}&\cdot &{\begin{bmatrix}\sigma _{1}&\dots &0\\\vdots &\ddots & \vdots \\0&\dots &\sigma _{l}\\\end{bmatrix}}&\cdot &{\begin{bmatrix}{\begin{bmatrix}&&{\textbf {v}}_{1} &&\end{bmatrix}}\\\vdots \\{\begin{bmatrix}&&{\textbf {v}}_{l}&&\end{bmatrix}}\end{bmatrix}}\end{matrix}} }

Wartości są nazywane wartościami osobliwymi oraz lewym i prawym wektorem osobliwym. Zauważ, że jedyną częścią, do której się przyczynia, jest wiersz. Niech ten wektor wierszowy zostanie nazwany . Podobnie jedyną częścią, która się do tego przyczynia, jest kolumna . To nie są wektory własne, ale zależą od wszystkich wektorów własnych. $\sigma_{1},\kropki,\sigma_{l}$ $u_{1},\kropki,u_{l}$ $v_{1},\kropki,v_{l}$ ${\ Displaystyle U}$ ${\ Displaystyle {\ textbf {t}} _ {i}}$ $i{\textrm {'th}}$ ${\ Displaystyle {\ kapelusz {\ textrm {t}}} _ {i} ^ {T}}$ ${\ Displaystyle V ^ {T}}$ ${\ Displaystyle {\ textbf {d}} _ {j}}$ $j{\textrm {'th}}$ ${\ Displaystyle {\ kapelusz {\ textrm {d}}} _ {j}}$

Okazuje się, że wybierając największe wartości osobliwe i odpowiadające im wektory osobliwe z i , otrzymujemy przybliżenie rzędu do z najmniejszym błędem ( norma Frobeniusa ). To przybliżenie ma minimalny błąd. Ale co ważniejsze, możemy teraz traktować wektory terminów i dokumentów jako „przestrzeń semantyczną”. Wierszowy wektor „term” ma następnie wpisy mapujące go do wymiarów przestrzeni o niższym wymiarze. Te nowe wymiary nie odnoszą się do żadnych zrozumiałych pojęć. Są one niskowymiarowym przybliżeniem przestrzeni wyższego wymiaru. Podobnie wektor „dokumentu” jest przybliżeniem w tej przestrzeni o niższych wymiarach. Piszemy to przybliżenie jako $k$ ${\ Displaystyle U}$ ${\ Displaystyle V}$ $k$ ${\ Displaystyle X}$ ${\ Displaystyle {\ kapelusz {\ textbf {t}}} _ {i} ^ {T}}$ $k$ ${\kapelusz {\textbf {d}}}_{j}$

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

Możesz teraz wykonać następujące czynności:

Zobacz, jak powiązane dokumenty i są w przestrzeni niskowymiarowej, porównując wektory i (zazwyczaj przez podobieństwo cosinus ). $j$ $q$ ${\ Displaystyle \ Sigma _ {k} \ cdot {\ kapelusz {\ textbf {d}}} _ {j}}$ ${\ Displaystyle \ Sigma _ {k} \ cdot {\ kapelusz {\ textbf {d}}} _ {q}}$
Porównywanie terminów i porównywanie wektorów i . Zauważ, że jest to teraz wektor kolumnowy. $i$ $p$ ${\ Displaystyle \ Sigma _ {k} \ cdot {\ kapelusz {\ textbf {t}}} _ {i}}$ ${\ Displaystyle \ Sigma _ {k} \ cdot {\ kapelusz {\ textbf {t}}} _ {p}}$ ${\kapelusz {\textbf {t}}}$
Dokumenty i reprezentacje wektorów terminów można grupować przy użyciu tradycyjnych algorytmów grupowania, takich jak k-średnich, przy użyciu miar podobieństwa, takich jak cosinus.
Po otrzymaniu zapytania wyświetl go jako minidokument i porównaj go z dokumentami w przestrzeni niskowymiarowej.

Aby zrobić to drugie, musisz najpierw przetłumaczyć swoje zapytanie na przestrzeń niskowymiarową. Intuicyjne jest wtedy, że musisz użyć tej samej transformacji, której używasz w swoich dokumentach:

{\ Displaystyle {\ kapelusz {\ textbf {d}}} _ {j} = \ Sigma _ {k} ^ {-1} U_ {k} ^ {T} {\ textbf {d}} _ {j}}

Zauważ, że odwrotność macierzy diagonalnej można znaleźć odwracając każdą niezerową wartość w macierzy. ${\ Displaystyle \ Sigma _ {k}}$

Oznacza to, że jeśli masz wektor zapytania , musisz wykonać translację przed porównaniem go z wektorami dokumentu w przestrzeni niskowymiarowej. Możesz zrobić to samo dla wektorów pseudoterminowych: $q$ ${\ Displaystyle {\ kapelusz {\ textbf {q}}} = \ Sigma _ {k} ^ {-1} U_ {k} ^ {T} {\ textbf {q}}}$

{\ Displaystyle {\ textbf {t}} _ {i} ^ {T} = {\ kapelusz {\ textbf {t}}} _ {i} ^ {T} \ Sigma _ {k} V_ {k} ^ { T}}

{\ Displaystyle {\ kapelusz {\ textbf {t}}} _ {i} ^ {T} = {\ textbf {t}} _ {i} ^ {T} V_ {k} ^ {-T} \ Sigma _ {k}^{-1}={\textbf {t}}_{i}^{T}V_{k}\Sigma _{k}^{-1}}

{\ Displaystyle {\ kapelusz {\ textbf {t}}}_ {i} = \ Sigma _ {k} ^ {-1} V_ {k} ^ {T} {\ textbf {t}} _ {i}}

Aplikacje

Nową, niskowymiarową przestrzeń można zazwyczaj wykorzystać do:

Porównaj dokumenty w przestrzeni niskowymiarowej ( grupowanie danych , klasyfikacja dokumentów ).
Znajdź podobne dokumenty w różnych językach po przeanalizowaniu podstawowego zestawu przetłumaczonych dokumentów ( pobieranie informacji z wielu języków ).
Znajdź relacje między terminami ( synonimia i polisemia ).
Mając dane zapytanie o terminy, przetłumacz je na przestrzeń niskowymiarową i znajdź pasujące dokumenty ( wyszukiwanie informacji ).
Znajdź najlepsze podobieństwo między małymi grupami terminów, w sposób semantyczny (np. w kontekście korpusu wiedzy), jak na przykład w modelu odpowiedzi na pytania wielokrotnego wyboru MCQ .
Rozszerzenie przestrzeni funkcji systemów uczenia maszynowego / eksploracji tekstu
Analizuj skojarzenia słów w korpusie tekstu

Synonimia i polisemia to podstawowe problemy w przetwarzaniu języka naturalnego :

Synonimia to zjawisko, w którym różne słowa opisują tę samą ideę. W ten sposób zapytanie w wyszukiwarce może nie znaleźć odpowiedniego dokumentu, który nie zawiera słów, które pojawiły się w zapytaniu. Na przykład wyszukiwanie hasła „lekarze” może nie zwrócić dokumentu zawierającego słowo „ lekarze ”, mimo że słowa te mają to samo znaczenie.
Polisemia to zjawisko, w którym to samo słowo ma wiele znaczeń. Tak więc wyszukiwanie może znaleźć nieistotne dokumenty zawierające żądane słowa w niewłaściwym znaczeniu. Na przykład botanik i informatyk poszukujący słowa „drzewo” prawdopodobnie pragną różnych zestawów dokumentów.

Aplikacje komercyjne

LSA zostało wykorzystane do pomocy w wyszukiwaniu patentów w stanie techniki .

Aplikacje w ludzkiej pamięci

Wykorzystanie utajonej analizy semantycznej jest powszechne w badaniu ludzkiej pamięci, zwłaszcza w obszarach swobodnego przypominania i wyszukiwania pamięci. Istnieje pozytywna korelacja między semantycznym podobieństwem dwóch słów (mierzonym za pomocą LSA) a prawdopodobieństwem, że słowa zostaną przywołane jedno po drugim w zadaniach swobodnego przypominania przy użyciu list do nauki losowych rzeczowników pospolitych. Zauważyli również, że w takich sytuacjach czas odpowiedzi między podobnymi słowami był znacznie krótszy niż między słowami niepodobnymi. Te odkrycia są określane jako efekt bliskości semantycznej .

Kiedy uczestnicy popełniali błędy przy przypominaniu badanych pozycji, błędy te zwykle były pozycjami, które były bardziej semantycznie powiązane z pożądaną pozycją i znajdowały się na wcześniej przestudiowanej liście. Te włamania z wcześniejszej listy, jak zaczęto je nazywać, wydają się konkurować z pozycjami z aktualnej listy o przypomnienie.

Inny model, określany jako Word Association Spaces (WAS), jest również używany w badaniach pamięci poprzez zbieranie danych o swobodnych skojarzeniach z serii eksperymentów, który obejmuje pomiary pokrewieństwa między słowami dla ponad 72 000 różnych par słów.

Realizacja

SVD zwykle obliczane przy użyciu dużych metody matrycy (na przykład metody lanczos ), ale może być także obliczana stopniowo i o znacznie obniżonych zasobów za pomocą sieci neuronowej, -jak podejściu, które nie wymagają dużej, matrycy pełnego rzędu odbędzie się w pamięć. Niedawno opracowano szybki, przyrostowy algorytm SVD o małej pamięci i dużej macierzy. Dostępne są implementacje tych szybkich algorytmów w MATLAB i Python . W przeciwieństwie do aproksymacji stochastycznej Gorrella i Webba (2005) algorytm Branda (2003) dostarcza dokładnego rozwiązania. W ostatnich latach poczyniono postępy w zmniejszaniu złożoności obliczeniowej choroby wenerycznej; na przykład, używając równoległego algorytmu ARPACK do wykonywania równoległej dekompozycji wartości własnych, możliwe jest przyspieszenie kosztu obliczeń SVD przy jednoczesnym zapewnieniu porównywalnej jakości predykcji.

Ograniczenia

Niektóre wady LSA obejmują:

Uzyskane wymiary mogą być trudne do interpretacji. Na przykład w

{(samochód), (ciężarówka), (kwiat)} ↦ {(1,3452 * samochód + 0,2828 * ciężarówka), (kwiat)}

komponent (1,3452 * samochód + 0,2828 * ciężarówka) można interpretować jako „pojazd”. Jednak jest bardzo prawdopodobne, że przypadki bliskie

{(samochód), (butelka), (kwiat)} ↦ {(1,3452 * samochód + 0,2828 * butelka ), (kwiat)}

wystąpi. Prowadzi to do wyników, które można uzasadnić na poziomie matematycznym, ale nie mają znaczenia w języku naturalnym.

LSA może tylko częściowo uchwycić polisemię (tj. wiele znaczeń słowa), ponieważ każde wystąpienie słowa jest traktowane jako mające to samo znaczenie, ponieważ słowo jest reprezentowane jako pojedynczy punkt w przestrzeni. Na przykład wystąpienie słowa „przewodniczący” w dokumencie zawierającym słowo „przewodniczący zarządu” oraz w osobnym dokumencie zawierającym słowo „wytwórca krzeseł” jest uważane za to samo. To zachowanie powoduje, że reprezentacja wektorowa jest średnią wszystkich różnych znaczeń słowa w korpusie, co może utrudniać porównanie. Jednak efekt jest często słabszy, ponieważ słowa mają dominujący sens w całym korpusie (tj. nie wszystkie znaczenia są jednakowo prawdopodobne).
Ograniczenia modelu worka słów (BOW), w którym tekst jest reprezentowany jako nieuporządkowany zbiór słów. Aby rozwiązać niektóre ograniczenia modelu worka słów (BOW), słownik wielogramowy może być użyty do znalezienia bezpośrednich i pośrednich skojarzeń, a także współwystępowania wyższego rzędu między terminami.
Model probabilistyczny LSA nie pasuje do zaobserwowanych danych: LSA zakłada, że słowa i dokumenty tworzą wspólny model Gaussa ( hipoteza ergodyczna ), podczas gdy zaobserwowano rozkład Poissona . Tak więc nowszą alternatywą jest probabilistyczna utajona analiza semantyczna , oparta na modelu wielomianowym , która daje lepsze wyniki niż standardowe LSA.

Metody alternatywne

Haszowanie semantyczne

W semantycznym haszowaniu dokumenty są mapowane na adresy pamięci za pomocą sieci neuronowej w taki sposób, że semantycznie podobne dokumenty znajdują się pod pobliskimi adresami. Głęboka sieć neuronowa zasadniczo buduje graficzny model wektorów liczby słów uzyskanych z dużego zestawu dokumentów. Dokumenty podobne do dokumentu zapytania można następnie znaleźć, po prostu uzyskując dostęp do wszystkich adresów, które różnią się tylko o kilka bitów od adresu dokumentu zapytania. Ten sposób rozszerzenia wydajności kodowania haszującego na przybliżone dopasowanie jest znacznie szybszy niż hashowanie zależne od lokalizacji , które jest najszybszą obecnie metodą.

Utajone indeksowanie semantyczne

Utajone indeksowanie semantyczne ( LSI ) to metoda indeksowania i wyszukiwania, która wykorzystuje technikę matematyczną zwaną dekompozycją według wartości singularnych (SVD) do identyfikowania wzorców w relacjach między terminami i pojęciami zawartymi w nieustrukturyzowanym zbiorze tekstu. LSI opiera się na zasadzie, że słowa użyte w tym samym kontekście mają zwykle podobne znaczenie. Kluczową cechą LSI jest jego zdolność do wyodrębniania treści pojęciowej z tekstu poprzez ustalanie skojarzeń między tymi terminami, które występują w podobnych kontekstach .

LSI to także aplikacja analizy korespondencji , wielowymiarowej techniki statystycznej opracowanej przez Jean-Paula Benzécri na początku lat 70., do tabeli kontyngencji zbudowanej na podstawie liczby słów w dokumentach.

Nazywany „ utajonym indeksowaniem semantycznym ” ze względu na jego zdolność do korelowania powiązanych semantycznie terminów, które są ukryte w zbiorze tekstu, po raz pierwszy zastosowano go do tekstu w firmie Bellcore pod koniec lat osiemdziesiątych. Metoda ta, zwana również utajoną analizą semantyczną (LSA), odkrywa ukrytą strukturę semantyczną w użyciu słów w treści tekstu oraz sposób, w jaki można jej użyć do wyodrębnienia znaczenia tekstu w odpowiedzi na zapytania użytkownika, powszechnie określane jako jako wyszukiwania koncepcji. Zapytania lub wyszukiwania pojęć w zestawie dokumentów, które zostały poddane LSI, zwrócą wyniki, które są koncepcyjnie podobne w znaczeniu do kryteriów wyszukiwania, nawet jeśli wyniki nie współdzielą określonego słowa lub słów z kryteriami wyszukiwania.

Korzyści z LSI

LSI pomaga przezwyciężyć synonimię, zwiększając zapamiętywanie , jedno z najbardziej problematycznych ograniczeń logicznych zapytań słów kluczowych i modeli przestrzeni wektorowej. Synonimia jest często przyczyną niedopasowania słownictwa używanego przez autorów dokumentów i użytkowników systemów wyszukiwania informacji . W rezultacie zapytania logiczne lub słowa kluczowe często zwracają nietrafne wyniki i pomijają istotne informacje.

LSI służy również do przeprowadzania automatycznej kategoryzacji dokumentów . W rzeczywistości kilka eksperymentów wykazało, że istnieje szereg korelacji między sposobem, w jaki LSI i ludzie przetwarzają i kategoryzują tekst. Kategoryzacja dokumentów to przypisanie dokumentów do jednej lub kilku predefiniowanych kategorii na podstawie ich podobieństwa do koncepcyjnej zawartości kategorii. LSI wykorzystuje przykładowe dokumenty do ustalenia podstaw koncepcyjnych dla każdej kategorii. Podczas przetwarzania kategoryzacji pojęcia zawarte w dokumentach podlegających kategoryzacji są porównywane z pojęciami zawartymi w przykładowych pozycjach, a kategoria (lub kategorie) jest przypisywana do dokumentów na podstawie podobieństw między pojęciami, które zawierają, a pojęciami, które są zawarte w przykładowych dokumentach.

Dynamiczne grupowanie oparte na treści koncepcyjnej dokumentów można również zrealizować za pomocą LSI. Grupowanie to sposób grupowania dokumentów na podstawie ich koncepcyjnego podobieństwa do siebie bez używania przykładowych dokumentów w celu ustalenia koncepcyjnej podstawy dla każdego klastra. Jest to bardzo przydatne, gdy mamy do czynienia z nieznanym zbiorem nieustrukturyzowanego tekstu.

Ponieważ używa ściśle matematycznego podejścia, LSI jest z natury niezależne od języka. Dzięki temu LSI może wydobyć semantyczną treść informacji napisanych w dowolnym języku bez konieczności korzystania ze struktur pomocniczych, takich jak słowniki i tezaurusy. LSI może również przeprowadzać wielojęzyczne wyszukiwanie pojęć i kategoryzację opartą na przykładach. Na przykład zapytania mogą być tworzone w jednym języku, takim jak angielski, i zostaną zwrócone podobne koncepcyjnie wyniki, nawet jeśli składają się z zupełnie innego języka lub wielu języków.

LSI nie ogranicza się tylko do pracy ze słowami. Może również przetwarzać dowolne ciągi znaków. Każdy obiekt, który można wyrazić jako tekst, może być reprezentowany w przestrzeni wektorowej LSI. Na przykład testy z abstraktami MEDLINE wykazały, że LSI jest w stanie skutecznie klasyfikować geny w oparciu o konceptualne modelowanie informacji biologicznych zawartych w tytułach i streszczeniach cytowań MEDLINE.

LSI automatycznie dostosowuje się do nowej i zmieniającej się terminologii i okazał się bardzo tolerancyjny na zakłócenia (tj. błędnie napisane słowa, błędy typograficzne, nieczytelne znaki itp.). Jest to szczególnie ważne w przypadku aplikacji korzystających z tekstu pochodzącego z optycznego rozpoznawania znaków (OCR) i konwersji mowy na tekst. LSI skutecznie radzi sobie również z rzadkimi, niejednoznacznymi i sprzecznymi danymi.

Aby LSI było skuteczne, tekst nie musi być w formie zdania. Może pracować z listami, notatkami w dowolnej formie, wiadomościami e-mail, treściami internetowymi itp. Dopóki zbiór tekstu zawiera wiele terminów, LSI może być używany do identyfikowania wzorców w relacjach między ważnymi terminami i pojęciami zawartymi w tekst.

LSI okazał się użytecznym rozwiązaniem wielu problemów związanych z dopasowaniem pojęciowym. Wykazano, że technika ta umożliwia przechwytywanie kluczowych informacji o relacjach, w tym informacji przyczynowych, zorientowanych na cel i taksonomicznych.

Oś czasu LSI

Połowa lat 60. – po raz pierwszy opisana i przetestowana technika analizy czynnikowej (H. Borko i M. Bernick)
1988 – opublikowano przełomowy artykuł na temat techniki LSI
1989 – Udzielenie oryginalnego patentu
1992 – Pierwsze użycie LSI do przypisywania artykułów recenzentom
1994 – przyznanie patentu na wielojęzyczne stosowanie LSI (Landauer i in.)
1995 – Pierwsze użycie LSI do oceniania esejów (Foltz i in., Landauer i in.)
1999 – Pierwsze wdrożenie technologii LSI dla społeczności wywiadowczej do analizy tekstu nieustrukturyzowanego ( SAIC ).
2002 – oferta produktów opartych na LSI dla agencji rządowych opartych na danych wywiadowczych (SAIC)

Matematyka LSI

LSI wykorzystuje popularne techniki algebry liniowej, aby poznać korelacje pojęciowe w zbiorze tekstu. Ogólnie rzecz biorąc, proces obejmuje skonstruowanie ważonej macierzy terminów-dokumentu, wykonanie dekompozycji według wartości osobliwych na macierzy i użycie macierzy do zidentyfikowania pojęć zawartych w tekście.

Matryca terminów-dokumentów

LSI rozpoczyna się od skonstruowania macierzy terminów-dokumentów , w celu zidentyfikowania występowania unikalnych terminów w zbiorze dokumentów. W macierzy termin-dokument, każdy termin jest reprezentowany przez wiersz, a każdy dokument jest reprezentowany przez kolumnę, przy czym każda komórka macierzy, , początkowo reprezentuje liczbę wystąpień powiązanego terminu we wskazanym dokumencie, . Ta macierz jest zwykle bardzo duża i bardzo rzadka. ${\ Displaystyle A}$ ${\ Displaystyle m}$ ${\ Displaystyle n}$ $a_{ij}$ $\mathrm {tf_{ij}}$

Po zbudowaniu macierzy term-dokumentu można zastosować do niej lokalne i globalne funkcje wagowe w celu warunkowania danych. Funkcje o masie przekształcić każdą komórkę, z , być produktem lokalnym wagi określony, , który opisuje względną częstotliwość terminu w dokumencie, a waga globalne , które opisuje względną częstotliwość terminu w całej kolekcji dokumentów. $a_{ij}$ ${\ Displaystyle A}$ $l_{ij}$ $g_{i}$

W poniższej tabeli zdefiniowano niektóre typowe lokalne funkcje wagowe.

Dwójkowy		$l_{ij}=1$ jeśli termin istnieje w dokumencie, lub inaczej
TerminCzęstotliwość		${\ Displaystyle l_ {ij} = \ operatorname {tf} _ {ij}}$ , liczba wystąpień terminu w dokumencie $i$ $j$
Dziennik		${\ Displaystyle l_ {ij} = \ log (\ operatorname {tf} _ {ij} + 1)}$
Augnorm		${\ Displaystyle l_ {ij} = {\ Frac {{\ duży (}{\ Frac {\ operatorname {tf} _ {ij}}} {\ max _ {i} (\ operatorname {TF} _ {ij})} }{\Duży )}+1}{2}}}$

W poniższej tabeli zdefiniowano niektóre typowe globalne funkcje wagowe.

Dwójkowy		${\ Displaystyle g_ {i} = 1}$
Normalna		${\ Displaystyle g_ {i} = {\ Frac {1} {\ sqrt {\ suma _ {j} \ operatorname {TF} _ {ij} ^ {2}}}}}$
GfIdf		${\ Displaystyle g_ {i} = \ operatorname {gf} _ {i} / \ operatorname {df} _ {i}}$ , gdzie oznacza całkowitą liczbę wystąpień terminu w całej kolekcji, a jest liczbą dokumentów, w których występuje termin . ${\ Displaystyle \ operatorname {gf} _ {i}}$ $i$ ${\ Displaystyle \ operatorname {df} _ {i}}$ $i$
Idf (odwrotna częstotliwość dokumentów)		${\ Displaystyle g_ {i} = \ log _ {2} {\ Frac {n} {1 + \ operatorname {df} _ {i}}}}$
Entropia		${\ Displaystyle g_ {i} = 1 + \ suma _ {j} \ Frac {p_ {ij} \ log p_ {ij}} {\ log n}}}$ , gdzie ${\ Displaystyle p_ {ij} = {\ Frac {\ operatorname {TF} _ {ij}}{\ operatorname {GF} _ {i}}}}$

Badania empiryczne z LSI wykazują, że funkcje ważenia Log i Entropy działają dobrze w praktyce z wieloma zestawami danych. Innymi słowy, każdy wpis z obliczany jest jako: $a_{ij}$ ${\ Displaystyle A}$

{\ Displaystyle g_ {i} = 1 + \ suma _ {j} \ Frac {p_ {ij} \ log p_ {ij}} {\ log n}}}

{\ Displaystyle a_ {ij} = g_ {i} \ \ log (\ operatorname {tf} _ {ij} + 1)}

Rozkład według wartości osobliwych z redukcją rang

W macierzy przeprowadzana jest dekompozycja według wartości osobliwych o zredukowanej randze w celu określenia wzorców w relacjach między terminami i pojęciami zawartymi w tekście. SVD stanowi podstawę LSI. Oblicza termin i wektor dokument przestrzenie poprzez zbliżenie pojedynczą matrycę określenie częstotliwości, na trzy klasy drugiej matrices- m o r Określenie-koncepcji matrycy wektora An r o r wartości singularnych macierzy , a n o r koncepcji, dokument wektora macierz, , które spełniają następujące zależności: ${\ Displaystyle A}$ ${\ Displaystyle T}$ $S$ ${\ Displaystyle D}$

${\ Displaystyle A \ około TSD ^ {T}}$

${\ Displaystyle T ^ {T} T = I_ {R} \ Quad D ^ {T} D = I_ {R}}$

${\ Displaystyle S_ {1,1} \ geq S_ {2,2} \ geq \ ldots \ geq S_ {r, r}> 0 \ quad S_ {i, j} = 0 \; {\ tekst {gdzie}} \;i\neq j}$

We wzorze A jest dostarczoną m przez n macierzą ważoną częstości terminów w zbiorze tekstu, gdzie m to liczba unikalnych terminów, a n to liczba dokumentów. T jest obliczoną macierzą m przez r wektorów terminowych, gdzie r jest rządem A — miarą jego unikalnych wymiarów ≤ min( m,n ) . S jest obliczoną ukośną macierzą r przez r o malejących wartościach osobliwych, a D jest obliczoną macierzą n przez r wektorów dokumentu.

SVD następnie obcinane , aby zmniejszyć stopień utrzymując tylko największy k « r ukośne wpisy w pojedynczej matrycy wartość S , gdzie K jest zwykle rzędu 100 do 300 wymiarach. To skutecznie zmniejsza rozmiary macierzy wektorów terminów i dokumentów do odpowiednio m na k i n na k . Operacja SVD, wraz z tą redukcją, skutkuje zachowaniem najważniejszych informacji semantycznych w tekście przy jednoczesnej redukcji szumu i innych niepożądanych artefaktów oryginalnej przestrzeni A . Ten zredukowany zestaw macierzy jest często oznaczany zmodyfikowanym wzorem, takim jak:

A ≈ A _k = T _k S _k D _k^T

Wydajne algorytmy LSI obliczają tylko pierwsze k wartości osobliwych oraz wektory terminów i dokumentów, w przeciwieństwie do obliczania pełnego SVD, a następnie obcinania go.

Należy zauważyć, że ta redukcja rang jest zasadniczo taka sama jak w przypadku analizy głównych składowych (PCA) na macierzy A , z wyjątkiem tego, że PCA odejmuje średnie. PCA traci rzadkość macierzy A , co może czynić ją niewykonalną dla dużych leksykonów.

Odpytywanie i rozszerzanie przestrzeni wektorowych LSI

Obliczone macierze T _k i D _k definiują przestrzenie wektorowe terminów i dokumentów, które wraz z obliczonymi wartościami osobliwymi S _k zawierają informacje pojęciowe pochodzące ze zbioru dokumentów. Podobieństwo terminów lub dokumentów w tych przestrzeniach jest czynnikiem tego, jak blisko siebie znajdują się w tych przestrzeniach, zwykle obliczane jako funkcja kąta między odpowiednimi wektorami.

Te same kroki są używane do lokalizowania wektorów reprezentujących tekst zapytań i nowych dokumentów w przestrzeni dokumentów istniejącego indeksu LSI. Poprzez proste przekształcenie równania A = TSD ^T w równoważne równanie D = A ^T TS ^-1 , nowy wektor d dla zapytania lub dla nowego dokumentu może zostać utworzony poprzez obliczenie nowej kolumny w A, a następnie pomnożenie nowa kolumna przez TS ^-1 . Nowa kolumna w A jest obliczana przy użyciu pierwotnie uzyskanych globalnych wag terminów i przy zastosowaniu tej samej lokalnej funkcji ważenia do terminów w zapytaniu lub w nowym dokumencie.

Wadą obliczania wektorów w ten sposób podczas dodawania nowych dokumentów z możliwością wyszukiwania jest to, że ignorowane są terminy, które nie były znane w fazie SVD dla oryginalnego indeksu. Terminy te nie będą miały wpływu na globalne wagi i wyuczone korelacje pochodzące z oryginalnego zbioru tekstu. Jednak obliczone wektory nowego tekstu są nadal bardzo przydatne do porównywania podobieństwa ze wszystkimi innymi wektorami dokumentów.

Proces powiększania przestrzeni wektorowych dokumentu dla indeksu LSI o nowe dokumenty w ten sposób nazywa się składaniem . Chociaż proces składania nie uwzględnia nowej treści semantycznej nowego tekstu, dodanie w ten sposób znacznej liczby dokumentów nadal zapewni dobre wyniki dla zapytań, o ile zawarte w nich terminy i pojęcia są dobrze reprezentowane w LSI indeks, do którego są dodawane. Gdy terminy i koncepcje nowego zestawu dokumentów muszą zostać uwzględnione w indeksie LSI, należy ponownie obliczyć macierz dokumentów terminów i SVD lub potrzebna jest metoda aktualizacji przyrostowej (taka jak opisana w ).

Dodatkowe zastosowania LSI

Powszechnie uznaje się, że umiejętność pracy z tekstem na podstawie semantycznej jest niezbędna dla nowoczesnych systemów wyszukiwania informacji. W rezultacie wykorzystanie LSI znacznie się rozszerzyło w ostatnich latach, ponieważ przezwyciężono wcześniejsze wyzwania związane ze skalowalnością i wydajnością.

LSI jest używany w różnych aplikacjach do wyszukiwania informacji i przetwarzania tekstu, chociaż jego głównym zastosowaniem było wyszukiwanie koncepcji i zautomatyzowana kategoryzacja dokumentów. Poniżej przedstawiamy kilka innych sposobów wykorzystania LSI:

Wykrywanie informacji ( eDiscovery , społeczność rządowa/wywiadowcza, publikowanie)
Zautomatyzowana klasyfikacja dokumentów (eDiscovery, społeczność rządowa/wywiadowcza, publikowanie)
Podsumowanie tekstu (eDiscovery, publikowanie)
Odkrywanie relacji (rząd, społeczność wywiadowcza, sieci społecznościowe)
Automatyczne generowanie wykresów powiązań osób i organizacji (rząd, społeczność wywiadowcza)
kojarzenie artykułów technicznych i grantów z recenzentami (rząd)
Obsługa klienta online (zarządzanie klientami)
Ustalanie autorstwa dokumentu (Edukacja)
Automatyczna adnotacja słów kluczowych do obrazów
Zrozumienie kodu źródłowego oprogramowania (inżynieria oprogramowania)
Filtrowanie spamu (Administracja systemu)
Wizualizacja informacji
Punktacja eseju (Edukacja)
Odkrywanie oparte na literaturze
Przewidywanie zwrotów akcji
Analiza treści snów (psychologia)

LSI jest coraz częściej wykorzystywane do wykrywania dokumentów elektronicznych (eDiscovery), aby pomóc przedsiębiorstwom przygotować się do postępowania sądowego. W przypadku zbierania elektronicznych materiałów dowodowych niezbędna jest możliwość grupowania, kategoryzowania i przeszukiwania dużych zbiorów nieustrukturyzowanego tekstu na podstawie koncepcji. Wyszukiwanie oparte na koncepcji przy użyciu LSI zostało zastosowane w procesie eDiscovery przez wiodących dostawców już w 2003 roku.

Wyzwania dla LSI

Wczesne wyzwania dla LSI koncentrowały się na skalowalności i wydajności. LSI wymaga stosunkowo wysokiej wydajności obliczeniowej i pamięci w porównaniu z innymi technikami wyszukiwania informacji. Jednak dzięki wdrożeniu nowoczesnych szybkich procesorów i dostępności niedrogiej pamięci, kwestie te zostały w dużej mierze przezwyciężone. Rzeczywiste aplikacje obejmujące ponad 30 milionów dokumentów, które zostały w pełni przetworzone za pomocą obliczeń macierzy i SVD, są powszechne w niektórych aplikacjach LSI. W pełni skalowalna (nieograniczona liczba dokumentów, szkolenia online) implementacja LSI zawarta jest w pakiecie oprogramowania open source gensim .

Innym wyzwaniem dla LSI była rzekoma trudność w określeniu optymalnej liczby wymiarów do wykorzystania do przeprowadzenia SVD. Zasadniczo mniejsza liczba wymiarów umożliwia szersze porównania pojęć zawartych w zbiorze tekstu, podczas gdy większa liczba wymiarów umożliwia bardziej szczegółowe (lub trafniejsze) porównania pojęć. Rzeczywista liczba wymiarów, które można wykorzystać, jest ograniczona liczbą dokumentów w kolekcji. Badania wykazały, że około 300 wymiarów zwykle zapewnia najlepsze wyniki w przypadku zbiorów dokumentów o średniej wielkości (setki tysięcy dokumentów) i być może 400 wymiarów w przypadku większych zbiorów dokumentów (miliony dokumentów). Jednak ostatnie badania wskazują, że 50-1000 wymiarów jest odpowiednich w zależności od wielkości i charakteru kolekcji dokumentów. Sprawdzanie proporcji zachowanej wariancji, podobnie jak w przypadku PCA lub analizy czynnikowej , w celu określenia optymalnej wymiarowości nie jest odpowiednie dla LSI. Użycie testu synonimów lub przewidywanie brakujących słów to dwie możliwe metody znalezienia prawidłowej wymiarowości. Gdy tematy LSI są używane jako funkcje w nadzorowanych metodach uczenia się, można użyć pomiarów błędów predykcji, aby znaleźć idealną wymiarowość.

Zobacz też

Bibliografia

Dalsza lektura

Landauera, Thomasa ; Foltz, Peter W.; Lahama, Darrella (1998). „Wprowadzenie do utajonej analizy semantycznej” (PDF) . Procesy dyskursu . 25 (2-3): 259-284. CiteSeerX 10.1.1.125.109 . doi : 10.1080/01638539809545028 .
Zachód jelenia, Scott ; Dumais, Susan T .; Furnas, George W. ; Landauer, Thomas K. ; Harshman, Richard (1990). „Indeksowanie przez utajoną analizę semantyczną” (PDF) . Journal of the American Society for Information Science . 41 (6): 391–407. CiteSeerX 10.1.1.33.2447 . doi : 10.1002/(SICI)1097-4571(199009)41:6<391::AID-ASI1>3.0.CO;2-9 . Zarchiwizowane z oryginału (PDF) w dniu 17.07.2012. Oryginalny artykuł, w którym model został po raz pierwszy wyeksponowany.
Jagoda, Michał ; Dumais, Susan T.; O'Brien, Gavin W. (1995). „Używanie algebry liniowej do inteligentnego wyszukiwania informacji” . Cytowanie dziennika wymaga |journal=( pomoc ) (PDF) . Ilustracja zastosowania LSA do pobierania dokumentów.
„Utajona analiza semantyczna” . InfoVis.
Fridolin Wild (23 listopada 2005). „Pakiet Open Source LSA dla R” . CRAN . Źródło 20 listopada 2006 .
Thomas Landauer , Susan T. Dumais . „Rozwiązanie problemu Platona: ukryta teoria analizy semantycznej nabywania, indukcji i reprezentacji wiedzy” . Źródło 2007-07-02 .

Zewnętrzne linki

Artykuły o LSA

Latent Semantic Analysis , artykuł naukowy o LSA napisany przez Toma Landauera, jednego z twórców LSA.

Rozmowy i pokazy

Przegląd LSA , wykład prof. Thomasa Hofmanna opisujący LSA, jego zastosowania w wyszukiwaniu informacji i jego powiązania z probabilistyczną ukrytą analizą semantyczną .
Kompletny przykładowy kod LSA w C# dla Windows . Kod demo zawiera wyliczanie plików tekstowych, filtrowanie słów stop, stemming, tworzenie matrycy dokument-term oraz SVD.

Realizacje

Ze względu na zastosowania międzydomenowe w wyszukiwaniu informacji , przetwarzaniu języka naturalnego (NLP), kognitywistyce i lingwistyce komputerowej , LSA zostało zaimplementowane do obsługi wielu różnych rodzajów aplikacji.

Sense Clusters , implementacja LSA zorientowana na wyszukiwanie informacji
Pakiet S-Space , implementacja LSA zorientowana na lingwistykę obliczeniową i kognitywistykę
Semantic Vectors stosuje losową projekcję, LSA i refleksyjne indeksowanie losowe w macierzach dokumentów terminów Lucene
Projekt Infomap , implementacja LSA zorientowana na NLP w języku C (zastąpiona przez projekt semanticvectors)
Text to Matrix Generator , MATLAB Toolbox do generowania macierzy termin-dokumentów z kolekcji tekstów, z obsługą LSA
Gensim zawiera implementację LSA w Pythonie dla macierzy większych niż RAM.

Languages

In other projects