Latente semantische Analyse

Latente semantische Analyse (LSA) ist eine Technik in Verarbeitung natürlicher Sprache, im Speziellen Verteilungssemantikmit der Analyse von Beziehungen zwischen einer Reihe von Dokumenten und den Begriffen, die sie enthalten, indem sie eine Reihe von Konzepten im Zusammenhang mit den Dokumenten und Begriffen erstellen. LSA geht davon aus Verteilungshypothese). Eine Matrix, die Wortzählungen pro Dokument enthält (Zeilen repräsentieren eindeutige Wörter und Spalten jedes Dokument Einzelwertzerlegung (SVD) wird verwendet, um die Anzahl der Zeilen zu reduzieren und gleichzeitig die Ähnlichkeitsstruktur zwischen den Spalten zu erhalten. Dokumente werden dann verglichen, indem der Cosinus des Winkels zwischen den beiden Vektoren (oder dem Skalarprodukt zwischen den Normalisierungen der beiden Vektoren), die durch zwei Spalten gebildet wurden. Werte in der Nähe von 1 stellen sehr ähnliche Dokumente dar, während Werte nahe 0 sehr unterschiedliche Dokumente darstellen.^[1]

Eine Informationsabruftechnik unter Verwendung einer latenten semantischen Struktur wurde 1988 patentiert (US -Patent 4.839.853, jetzt abgelaufen) von Scott Deerwester, Susan Dumais, George Furnas, Richard Harshman, Thomas Landauer, Karen Lochbaum und Lynn Streeter. Im Kontext seiner Anwendung auf Informationsrückgewinnung, es wird manchmal genannt Latente semantische Indexierung (Lsi).^[2]

Überblick

Vorkommensmatrix

LSA kann a verwenden Dokumentenmatrix das beschreibt das Vorkommen von Begriffen in Dokumenten; es ist ein spärliche Matrix deren Zeilen entsprechen Bedingungen und deren Spalten Dokumenten entsprechen. Ein typisches Beispiel für die Gewichtung der Elemente der Matrix ist tf-idf (Term Frequenz -inverses Dokumentfrequenz): Das Gewicht eines Elements der Matrix ist proportional zu der Häufigkeit, mit der die Begriffe in jedem Dokument angezeigt werden, wo seltene Begriffe hochgezogen werden, um ihre relative Bedeutung widerzuspiegeln.

Diese Matrix ist auch semantischen Standardmodellen üblich, obwohl sie nicht unbedingt explizit als Matrix ausgedrückt wird, da die mathematischen Eigenschaften von Matrizen nicht immer verwendet werden.

Rangabsenkung

Nach dem Bau der Vorkommensmatrix findet LSA a Niedrige Annäherung^[4] zum Termdokumentmatrix. Für diese Annäherungen könnte es verschiedene Gründe geben:

• Die ursprüngliche Term-Document-Matrix wird für die Rechenressourcen als zu groß angesehen. In diesem Fall wird die angenäherte Matrix mit niedrigem Rang als interpretiert als Annäherung (ein "am wenigsten und notwendiges Übel").
• Die ursprüngliche Term-Document-Matrix wird vermutet laut: Zum Beispiel sind anekdotische Fälle von Begriffen zu beseitigen. Aus dieser Sicht wird die angenähte Matrix als interpretiert als de-noiSified Matrix (Eine bessere Matrix als das Original).
• Die ursprüngliche Term-Dokumentmatrix wird übermäßig angenommen spärlich relativ zur "wahren" Term-Dokumentmatrix. Das heißt, die ursprüngliche Matrix listet nur die Wörter auf in Jedes Dokument, während wir uns an allen Wörtern interessieren könnten im Zusammenhang mit Jedes Dokument - im Allgemeinen ein viel größerer Satz aufgrund Synonymie.

Die Folge der Rangsenkung ist, dass einige Dimensionen kombiniert werden und von mehr als einem Begriff abhängen:

{(Auto), (LKW), (Blume)} -> {(1.3452 * Auto + 0,2828 * Truck), (Blume)}}}

Dies mildert das Problem der Identifizierung von Synonymie, da die Rangabsenkung die mit Begriffen verbundenen Dimensionen mit ähnlichen Bedeutungen zusammenführen soll. Es mildert auch teilweise das Problem mit PolysemieDa Komponenten polysemous Wörter, die in die "rechte" Richtung zeigen, zu den Komponenten von Wörtern hinzugefügt werden, die eine ähnliche Bedeutung haben. Umgekehrt neigen Komponenten, die in andere Richtungen zeigen, entweder einfach aus oder im schlimmsten Fall kleiner als Komponenten in den Richtungen, die dem beabsichtigten Sinn entsprechen.

Ableitung

Lassen ${\ displayStyle x}$ Sei eine Matrix, wo Element ${\ displayStyle (i, j)}$ beschreibt das Auftreten des Begriffs ${\ displayStyle i}$ im Dokument ${\ displayStyle j}$ (Dies kann beispielsweise die Frequenz sein). ${\ displayStyle x}$ wird so aussehen:

${\ displayStyle {\ begin {matrix} & {\ textbf {d}} _ {j} \\ & \ downarrow \\ {\ textbf {t}} _ {i}^{t} \ rightarrow & {{\ begin {{begin {{begin {{begin {{begin {{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{i), 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 j j J. J. } & \ dots & x_ {m, n} \\\ end {bmatrix}} \ end {matrix}}}$

Jetzt ist eine Zeile in dieser Matrix ein Vektor, der einem Begriff entspricht, der sich zu jedem Dokument in Beziehung setzt:

$oder Ende {BMatrix}}}$

Ebenso ist eine Spalte in dieser Matrix ein Vektor, der einem Dokument entspricht, der ihre Beziehung zu jedem Begriff enthält:

$oder } \\\ end {bmatrix}}}$

Jetzt die Skalarprodukt ${\ displaystyle {\ textbf {t}} _ {i}^{t} {\ textbf {t} _ {p}}$ Zwischen zwei Begriffsvektoren gibt die Korrelation zwischen den Begriffen über den Satz von Dokumenten. Das Matrixprodukt ${\ displayStyle xx^{t}}$ Enthält all diese Punktprodukte. Element ${\ displayStyle (i, p)}$ (Das ist gleich Element ${\ displayStyle (p, i)}$) Enthält das Punktprodukt ${\ displaystyle {\ textbf {t}} _ {i}^{t} {\ textbf {t} _ {p}}$ ($oder$). Ebenso die Matrix ${\ displayStyle x^{t} x}$ Enthält die Punktprodukte zwischen allen Dokumentvektoren, die ihre Korrelation über die Begriffe geben: $oder }}_{j}}$.

Nun, aus der Theorie der linearen Algebra gibt es eine Zersetzung von ${\ displayStyle x}$ so dass ${\ displayStyle u}$ und ${\ displayStyle v}$ sind Orthogonale Matrizen und ${\ displayStyle \ sigma}$ ist ein diagonale Matrix. Dies wird a genannt Einzelwertzerlegung (SVD):

${\ displaystyle {\ begin {matrix} x = u \ sigma v^{t} \ end {matrix}}}$

Die Matrixprodukte, die uns den Begriff und die Dokumentkorrelationen geben, werden dann

$oder }) (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}}}$

Seit ${\ displaystyle \ sigma \ sigma ^{t}}$ und ${\ displaystyle \ sigma ^{t} \ sigma}$ sind diagonal wir sehen das ${\ displayStyle u}$ muss die enthalten Eigenvektoren von ${\ displayStyle xx^{t}}$, während ${\ displayStyle v}$ Muss die Eigenvektoren von sein ${\ displayStyle x^{t} x}$. Beide Produkte haben die gleichen Eigenwerte ungleich Null, die durch die Einträge ungleich Null angegeben werden ${\ displaystyle \ sigma \ sigma ^{t}}$oder gleichermaßen durch die ungleich Nulleinträge von ${\ displaystyle \ sigma ^{t} \ sigma}$. Jetzt sieht die Zersetzung so aus:

$oder ) \\ & \ 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 {end Bmatrix}} & = & ({\ Hat {\ textbf {t}}} _ {i}^{t}) \ rightarrow & {\ begin {bMatrix} {\ begin {bmatrix} \, \\\, \\, \\, \\, \\, \\, \\, \\, \\, \\, \\, \\, \\, \\, \\, \\, \\, oder l} \\\, \\\, \ end {bmatrix}} \ end {bmatrix}} & \ cdot & {\ begin {bmatrix} \ sigma _ {1} & \ dots & 0 \\ vdots & \ ddots & & \ ddots & & \ ddots & & \ ddots & & \ \ vdots \\ 0 & \ dots & \ sigma _ {l} \\\ end {bmatrix}} & \ cdot & {\ begin {bmatrix} {\ begin {bmatrix} && {\ textb {v}} {1} &&\end{bmatrix}}\\\vdots \\{\begin{bmatrix}&&{\textbf {v}}_{l}&&\end{bmatrix}}\end{bmatrix}}\end{matrix}} }$

Die Werte ${\ displaystyle \ sigma _ {1}, \ dots, \ sigma _ {l}}$ werden die einzigartigen Werte und genannt, und ${\ displayStyle u_ {1}, \ dots, u_ {l}}$ und ${\ displayStyle v_ {1}, \ dots, v_ {l}}$ die linken und rechten Singularvektoren. Beachten Sie den einzigen Teil von ${\ displayStyle u}$ das trägt zu ${\ displayStyle {\ textbf {t}} _ {i}}$ ist der ${\ displayStyle i {\ textrm {'th}}}$ die Zeile. Lassen Sie diesen Zeilenvektor aufrufen ${\ displaystyle {\ Hat {\ textrm {t}} _ {i}^{t}}$. Ebenso der einzige Teil von ${\ displayStyle v^{t}}$ das trägt zu ${\ displayStyle {\ textbf {d}} _ {j}}$ ist der ${\ displayStyle j {\ textrm {'th}}}$ Säule, ${\ displaystyle {\ Hat {\ textrm {d}} _ {j}}$. Diese sind nicht die Eigenvektoren, aber abhängen an alle die Eigenvektoren.

Es stellt sich heraus, dass wenn Sie die auswählen ${\ displayStyle K}$ größte singuläre Werte und ihre entsprechenden singulären Vektoren von ${\ displayStyle u}$ und ${\ displayStyle v}$, du bekommst den Rang ${\ displayStyle K}$ Annäherung an ${\ displayStyle x}$ mit dem kleinsten Fehler (FROBENIUS NORM). Diese Näherung hat einen minimalen Fehler. Noch wichtiger ist jedoch, dass wir jetzt den Begriff behandeln und Vektoren als "semantischer Raum" dokumentieren können. Die Reihe "Begriff" Vektor ${\ displayStyle {\ Hat {\ textbf {t}}} _ {i}^{t}}$ dann hat ${\ displayStyle K}$ Entries, es in eine niedrigerdimensionale Raumabmessungen zuzuordnen. Diese neuen Dimensionen beziehen sich nicht auf verständliche Konzepte. Sie sind eine niedrigerdimensionale Näherung des höherdimensionalen Raums. Ebenso der "Dokument" -Vektor ${\ displayStyle {\ Hat {\ textbf {d}}} _ {j}}$ ist eine Annäherung in diesem niedrigerdimensionalen Raum. Wir schreiben diese Näherung als

${\ displaystyle x_ {k} = u_ {k} \ sigma _ {k} v_ {k}^{t}}$

Sie können jetzt Folgendes tun:

• Sehen Sie, wie verwandte Dokumente ${\ displayStyle j}$ und ${\ displayStyle q}$ sind im niedrigdimensionalen Raum durch Vergleich der Vektoren ${\ displaystyle \ sigma _ {k} \ cdot {\ Hat {\ textbf {d}} _ {j}}$ und ${\ displaystyle \ sigma _ {k} \ cdot {\ Hat {\ textbf {d}} _ {q}}$ (Normalerweise von Kosinusähnlichkeit).
• Begriffe vergleichen ${\ displayStyle i}$ und ${\ displayStyle p}$ Durch Vergleich der Vektoren ${\ displaystyle \ sigma _ {k} \ cdot {\ Hat {\ textbf {t}} _ {i}}$ und ${\ displaystyle \ sigma _ {k} \ cdot {\ Hat {\ textbf {t}} _ {p}}$. Beachten Sie, dass ${\ displayStyle {\ Hat {\ textbf {t}}}}$ ist jetzt ein Spaltenvektor.
• Dokumente und Term Vector-Darstellungen können mit herkömmlichen Clustering-Algorithmen wie K-Means unter Verwendung von Ähnlichkeitsmaßnahmen wie Cosinus geklustert werden.
• Betrachten Sie dies als Mini-Dokument an und vergleichen Sie es mit Ihren Dokumenten im niedrigdimensionalen Raum.

Um zu tun, müssen Sie zuerst Ihre Abfrage in den niedrigdimensionalen Raum übersetzen. Es ist dann intuitiv, dass Sie dieselbe Transformation verwenden müssen, die Sie in Ihren Dokumenten verwenden:

$oder$

Beachten Sie hier, dass die Umkehrung der diagonalen Matrix ${\ displayStyle \ sigma _ {k}}$ kann gefunden werden, indem jeder Wert ungleich Null innerhalb der Matrix invertiert wird.

Dies bedeutet, dass wenn Sie einen Abfragebericht haben ${\ displayStyle q}$Sie müssen die Übersetzung durchführen $oder$ Bevor Sie es mit den Dokumentvektoren im niedrigdimensionalen Raum vergleichen. Sie können dasselbe für Pseudo -Begriff Vektoren tun:

$oder T}}$

${\ displaystyle {\ Hat {\ textbf {t}} _ {i}^{t} = {\ textbf {t} _ {i}^{t} v_ {k}^{-t} \ sigma _ {k}^{-1} = {\ textbf {t}} _ {i}^{t} v_ {k} \ sigma _ {k}^{-1}}$

$oder$

Anwendungen

Der neue niedrigdimensionale Raum kann normalerweise verwendet werden, um:

• Vergleichen Sie die Dokumente im niedrigdimensionalen Raum (Datenclustering, Dokumentklassifizierung).
• Finden Sie ähnliche Dokumente über Sprachen hinweg, nachdem Sie einen Basissatz von übersetzten Dokumenten analysiert haben (Cross-Language Information Abruf).
• Beziehungen zwischen Begriffen finden (Synonymie und Polysemie).
• Übersetzen Sie es bei einer Abfrage der Begriffe in den niedrigdimensionalen Raum und finden Sie passende Dokumente (Informationsrückgewinnung).
• Finden Sie die beste Ähnlichkeit zwischen kleinen Gruppen von Begriffen auf semantische Weise (d. H. In einem Kontext eines Wissenskorpus), wie zum Beispiel in Multi -Choice -Fragen MCQ Antwortmodell.^[5]
• Erweitern Sie den Merkmalsraum von maschinellem Lern- / Text -Mining -Systemen ^[6]
• Analysieren Sie die Wortvereinigung im Textkorpus ^[7]

Synonymie und Polysemie sind grundlegende Probleme in Verarbeitung natürlicher Sprache:

• Synonymie ist das Phänomen, bei dem verschiedene Wörter dieselbe Idee beschreiben. Somit kann eine Abfrage in einer Suchmaschine ein relevantes Dokument nicht abrufen, das nicht die Wörter enthält, die in der Abfrage erscheinen. Beispielsweise kann eine Suche nach "Ärzten" ein Dokument mit dem Wort nicht zurückgeben. "Ärzte", obwohl die Wörter die gleiche Bedeutung haben.
• Polysemie ist das Phänomen, bei dem das gleiche Wort mehrere Bedeutungen hat. Eine Suche kann also irrelevante Dokumente abrufen, die die gewünschten Wörter in der falschen Bedeutung enthalten. Zum Beispiel wünschen sich ein Botaniker und ein Informatiker, der nach dem Wort "Baum" sucht, wahrscheinlich verschiedene Dokumente.

Kommerzielle Anwendungen

LSA wurde verwendet, um die Ausführung zu unterstützen vorherige Kunst Suche nach Patente.^[8]

Anwendungen im menschlichen Gedächtnis

Die Verwendung einer latenten semantischen Analyse war in der Untersuchung des menschlichen Gedächtnisses weit verbreitet, insbesondere in Bereichen von freier Rückruf und Speichersuche. Es besteht eine positive Korrelation zwischen der semantischen Ähnlichkeit von zwei Wörtern (gemessen anhand von LSA) und der Wahrscheinlichkeit, dass die Wörter nacheinander in freien Rückrufaufgaben unter Verwendung von Studienlisten von zufälligen gemeinsamen Substantiven nacheinander zurückgerufen werden. Sie stellten auch fest, dass in diesen Situationen die Inter-Antwort-Zeit zwischen den ähnlichen Wörtern viel schneller war als zwischen unterschiedlichen Wörtern. Diese Ergebnisse werden als semantischer Proximity -Effekt bezeichnet.^[9]

Als die Teilnehmer Fehler beim Rückruf untersuchten Gegenstände machten, waren diese Fehler tendenziell Artikel, die semantischer mit dem gewünschten Element verwandt waren und in einer zuvor untersuchten Liste gefunden wurden. Diese Vorlisten-Eindringungen, wie sie genannt wurden, scheinen mit Elementen auf der aktuellen Liste für den Rückruf zu konkurrieren.^[10]

Ein weiteres Modell, das als Word Association Spaces (wurde) (wurde) bezeichnet, wird ebenfalls in Gedächtnisstudien verwendet, indem freie Assoziationsdaten aus einer Reihe von Experimenten gesammelt werden und die Messungen der Wortbeziehung für über 72.000 verschiedene Wortpaare enthält.^[11]

Implementierung

Das SVD wird typischerweise mit großen Matrixmethoden berechnet (zum Beispiel, zum Beispiel, Lanczos -Methoden) kann aber auch schrittweise und mit stark reduzierten Ressourcen über a berechnet werden neurales Netzwerk-ähnlich, der nicht erforderlich ist, dass die große Vollrang-Matrix im Gedächtnis gehalten wird.^[12] Ein schneller, inkrementeller SVD-Algorithmus mit großem Matrix wurde kürzlich entwickelt.^[13] Matlab und Python Implementierungen dieser schnellen Algorithmen sind verfügbar. Im Gegensatz zu Gorrell und Webbs (2005) stochastischer Approximation bietet der Markenalgorithmus (2003) eine genaue Lösung. In den letzten Jahren wurden Fortschritte erzielt, um die rechnerische Komplexität von SVD zu verringern. Zum Beispiel ist durch Verwendung eines parallelen Arpackalgorithmus zur Durchführung einer parallele Eigenwert -Zersetzung möglich, die SVD -Berechnungskosten zu beschleunigen und gleichzeitig eine vergleichbare Vorhersagequalität bereitzustellen.^[14]

Einschränkungen

Einige der Nachteile von LSA umfassen:

• Die daraus resultierenden Dimensionen könnten schwer zu interpretieren sein. Zum Beispiel in

{(Auto), (LKW), (Blume)} ↦ {(1,3452 * Auto + 0,2828 * Truck), (Blume)}}}

Die (1,3452 * Auto + 0,2828 * LKW) -Komponente könnte als "Fahrzeug" interpretiert werden. Es ist jedoch sehr wahrscheinlich, dass Fälle in der Nähe

{(Auto), (Flasche), (Blume)} ↦ {(1,3452 * Auto + 0,2828 * Flasche), (Blume)}

wird passieren. Dies führt zu Ergebnissen, die auf mathematischer Ebene gerechtfertigt werden können, aber in der natürlichen Sprache keine unmittelbar offensichtliche Bedeutung haben. Die Komponente (1,3452 * Auto + 0,2828 * Flasche) könnte jedoch aufgrund der Tatsache gerechtfertigt sein, dass sowohl Flaschen als auch Autos transparente und undurchsichtige Teile haben, männlich gemacht und mit hoher Wahrscheinlichkeit Logos/Wörter auf ihrer Oberfläche enthalten; In vielerlei Hinsicht teilen diese beiden Konzepte "Semantik". Das heißt, innerhalb einer fraglichen Sprache gibt es möglicherweise kein leicht verfügbares Wort zum Zuweisen, und die Erklärung wird zu einer Analyseaufgabe im Gegensatz zu einfacher Aufgabe von Word/Class/Concept -Zuweisung.

• LSA kann nur teilweise erfassen Polysemie (d. H. Mehrere Bedeutungen eines Wortes), weil jedes Auftreten eines Wortes als die gleiche Bedeutung behandelt wird, da das Wort als einzelner Punkt im Raum dargestellt wird. Zum Beispiel wird das Auftreten von "Stuhl" in einem Dokument, das "Vorsitzender des Verwaltungsrats" und in einem separaten Dokument mit "Der Vorsitzendemacher" enthält, als gleich angesehen. Das Verhalten führt dazu, dass die Vektorrepräsentation eine ist Durchschnitt Von allen unterschiedlichen Bedeutungen des Wortes im Korpus, was es für den Vergleich schwer machen kann.^[15] Der Effekt wird jedoch oft aufgrund von Wörtern mit a verringert vorherrschender Sinn In einem Korpus (d. H. Nicht alle Bedeutungen sind gleich wahrscheinlich).
• Einschränkungen von Tasche mit Wörtern Modell (Bogen), wo ein Text als ungeordnete Wörtersammlung dargestellt wird. Einen Teil der Einschränkung von ansprechen Tasche mit Wörtern Modell (VERNEIGUNG), Multi-Gram Wörterbuch kann verwendet werden, um sowohl direkte und indirekte Assoziation als auch zu finden Auftrag von oben Auftreten Unter den Begriffen.^[16]
• Das Probabilistisches Modell von LSA entspricht nicht beobachtete Daten: LSA geht davon aus, dass Wörter und Dokumente eine Verbindung bilden Gaußscher Modell (Ergodische Hypothese), während ein Poisson-Verteilung wurde beobachtet. Eine neuere Alternative ist also Probabilistische latente semantische Analysebasierend auf einem multinomial Das Modell, das berichtet wird, dass es bessere Ergebnisse liefert als Standard -LSA.^[17]

Alternative Methoden

Semantisches Hashing

Im semantischen Hashing ^[18] Dokumente werden mit a auf Speicheradressen zugeordnet neurales Netzwerk so, dass sich semantisch ähnliche Dokumente in nahe gelegenen Adressen befinden. Tiefes neuronales Netzwerk im Wesentlichen baut a Grafisches Modell der Wortzählvektoren, die aus einem großen Satz von Dokumenten erhalten wurden. Dokumente, die einem Abfragendokument ähnlich sind, können dann einfach auf alle Adressen zugreifen, die nur wenige Bits von der Adresse des Abfragendokuments unterscheiden. Diese Art der Ausweitung der Effizienz des Hash-Coding auf ungefähre Übereinstimmung ist viel schneller als Lokalität sensibler Hashing, was die schnellste aktuelle Methode ist.^{[Klarstellung erforderlich]}

Latente semantische Indexierung

Latente semantische Indexierung (Lsi) ist eine Indexierungs- und Abrufmethode, die eine mathematische Technik verwendet Einzelwertzerlegung (SVD), um Muster in den Beziehungen zwischen den zu identifizieren Bedingungen und Konzepte enthalten in einer unstrukturierten Textsammlung. LSI basiert auf dem Prinzip, dass Wörter, die in denselben Kontexten verwendet werden, tendenziell ähnliche Bedeutungen haben. Ein wesentliches Merkmal von LSI ist die Fähigkeit, den konzeptionellen Inhalt von a zu extrahieren Textkörper Durch die Festlegung von Assoziationen zwischen den Begriffen, die in ähnlicher Weise auftreten Kontexte.^[19]

LSI ist auch eine Anwendung von Korrespondenzanalyse, eine multivariate statistische Technik, die von entwickelt wurde von Jean-Paul Benzécri^[20] In den frühen 1970er Jahren zu a Kontingenztabelle aus Wortzählungen in Dokumenten erstellt.

Genannt "latente Semantik Indexierung "wegen seiner Fähigkeit zu korrelieren semantisch Verwandte Begriffe, die sind latent In einer Textsammlung wurde es zunächst auf Text bei angewendet Bellcore In den späten 1980er Jahren. Die Methode, auch Latent Semantic Analysis (LSA) genannt als Konzeptsuche. Abfragen oder Konzeptensuche gegen eine Reihe von Dokumenten, die LSI unterzogen wurden, gibt die Ergebnisse zurück, die in Bezug auf die Suchkriterien konzeptionell ähnlich sind, auch wenn die Ergebnisse kein bestimmtes Wort oder Wörter mit den Suchkriterien teilen.

Vorteile von LSI

LSI hilft, Synonymie zu überwinden, indem er zunimmt abrufen, eine der problematischsten Einschränkungen von Boolesche Keyword -Abfragen und Vektorraummodelle.^[15] Synonymie ist häufig die Ursache für Fehlanpassungen im Vokabular, das von den Autoren von Dokumenten und den Benutzern von verwendet wird Informationsrückgewinnung Systeme.^[21] Infolgedessen geben Boolesche oder Keyword -Abfragen häufig irrelevante Ergebnisse zurück und verpassen Informationen, die relevant sind.

LSI wird auch zur automatisierten Durchführung verwendet Dokumentenkategorisierung. Tatsächlich haben mehrere Experimente gezeigt, dass es eine Reihe von Korrelationen zwischen der Art und Weise gibt, wie LSI und Menschen Text verarbeiten und kategorisieren.^[22] Die Kategorisierung von Dokumenten ist die Zuordnung von Dokumenten zu einer oder mehreren vordefinierten Kategorien, die auf ihrer Ähnlichkeit mit dem konzeptionellen Inhalt der Kategorien basieren.^[23] LSI verwendet Beispiel Dokumente, um die konzeptionelle Grundlage für jede Kategorie festzulegen. Während der Kategorisierungsverarbeitung werden die Konzepte, die in den zu kategorisierten Dokumenten enthalten sind In den Beispieldokumenten.

Dynamisches Clustering basierend auf dem konzeptionellen Inhalt von Dokumenten kann auch mit LSI erreicht werden. Clustering ist eine Möglichkeit, Dokumente zu gruppieren, die auf ihrer konzeptionellen Ähnlichkeit miteinander basieren, ohne Beispieldokumente zu verwenden, um die konzeptionelle Grundlage für jeden Cluster zu ermitteln. Dies ist sehr nützlich, wenn es sich um eine unbekannte Sammlung unstrukturierter Text handelt.

Da es einen streng mathematischen Ansatz verwendet, ist LSI von Natur aus unabhängig von der Sprache. Dies ermöglicht LSI, den semantischen Inhalt von Informationen in einer Sprache zu ermitteln, ohne die Verwendung von Hilfsstrukturen wie Wörterbüchern und Thesauri zu verwenden. LSI kann auch kreuzklinisch durchführen Konzeptsuche und Beispielbasierte Kategorisierung. Beispielsweise können Abfragen in einer Sprache wie Englisch durchgeführt werden, und konzeptionell ähnliche Ergebnisse werden zurückgegeben, selbst wenn sie aus einer völlig anderen Sprache oder mehreren Sprachen bestehen.

LSI ist nicht darauf beschränkt, nur mit Worten zu arbeiten. Es kann auch willkürliche Zeichenketten verarbeiten. Jedes Objekt, das als Text ausgedrückt werden kann, kann in einem LSI -Vektorraum dargestellt werden. Beispielsweise haben Tests mit Medline -Abstracts gezeigt, dass LSI Gene effektiv klassifizieren kann, basierend auf der konzeptionellen Modellierung der in den Titeln und Abstracts der Medline -Zitate enthaltenen biologischen Informationen.^[24]

LSI passt automatisch an neue und sich ändernde Terminologie an und hat sich als sehr tolerant gegenüber Rauschen (d. H. Wörter, typografische Fehler, unlesbare Zeichen usw.) erwiesen.^[25] Dies ist besonders wichtig für Anwendungen, die von Text aus der optischen Charaktererkennung (OCR) und Sprach-Text-Konvertierung abgeleitet wurden. LSI befasst sich auch effektiv mit spärlichen, mehrdeutigen und widersprüchlichen Daten.

Der Text muss nicht in Satzform sein, damit LSI wirksam ist. Es kann mit Listen, Freiform-Notizen, E-Mails, webbasiertem Inhalt usw. funktionieren. Solange eine Sammlung von Text mehrere Begriffe enthält, kann LSI verwendet werden, um Muster in den Beziehungen zwischen den wichtigen Begriffen und Konzepten zu identifizieren, die in der enthalten sind Text.

LSI hat sich als nützliche Lösung für eine Reihe von konzeptionellen Übereinstimmungen erwiesen.^[26][27] Es wurde gezeigt, dass die Technik wichtige Beziehungsinformationen erfasst, einschließlich kausaler, zielorientierter und taxonomischer Informationen.^[28]

LSI -Zeitleiste

• Mitte der 1960er Jahre - Faktoranalyse -Technik, die erstmals beschrieben und getestet wurde (H. Borko und M. Bernick)
• 1988 - Samenpapier über die LSI -Technik veröffentlicht ^[19]
• 1989 - Originalpatent gewährt ^[19]
• 1992 - Erste Verwendung von LSI, um den Rezensenten Artikel zuzuweisen^[29]
• 1994 -Patent für die Kreuzungsanwendung von LSI (Landauer et al.) Gewährt
• 1995 - Erste Verwendung von LSI zur Bewertung von Aufsätzen (Foltz et al., Landauer et al.)
• 1999 - Erste Implementierung der LSI -Technologie für Intelligence Community zur Analyse unstrukturierter Text (SAIC).
• 2002 -LSI-basiertes Produktangebot für intelligente Regierungsbehörden (SAIC)

Mathematik von LSI

LSI verwendet gemeinsame lineare Algebra -Techniken, um die konzeptionellen Korrelationen in einer Textsammlung zu lernen. Im Allgemeinen beinhaltet der Prozess die Konstruktion einer gewichteten Term-Dokumentmatrix, die a Einzelwertzerlegung Auf der Matrix und Verwendung der Matrix, um die im Text enthaltenen Konzepte zu identifizieren.

Termdokumentmatrix

LSI beginnt mit dem Bau einer Term-Document-Matrix, ${\ displayStyle a}$, um das Ereignis der Ereignisse zu identifizieren ${\ displayStyle m}$ Einzigartige Begriffe innerhalb einer Sammlung von ${\ displayStyle n}$ Unterlagen. In einer Term-Document-Matrix wird jeder Begriff durch eine Zeile dargestellt, und jedes Dokument wird durch eine Spalte mit jeder Matrixzelle dargestellt. ${\ displayStyle a_ {ij}}$zunächst die Häufigkeit, mit der der zugehörige Term im angegebenen Dokument angezeigt wird, dargestellt. ${\ displayStyle \ mathrm {tf_ {ij}}}$. Diese Matrix ist normalerweise sehr groß und sehr spärlich.

Sobald eine Term-Document-Matrix konstruiert ist, können lokale und globale Gewichtungsfunktionen darauf angewendet werden, um die Daten zu konditionieren. Die Gewichtungsfunktionen transformieren jede Zelle, ${\ displayStyle a_ {ij}}$ von ${\ displayStyle a}$, um das Produkt eines lokalen Begriffs Gewicht zu sein, ${\ displayStyle l_ {ij}}$, was die relative Häufigkeit eines Begriffs in einem Dokument und eines globalen Gewichts beschreibt. ${\ displayStyle g_ {i}}$, die die relative Häufigkeit des Begriffs innerhalb der gesamten Sammlung von Dokumenten beschreibt.

Einige häufige lokale Gewichtungsfunktionen^[30] werden in der folgenden Tabelle definiert.

Binär		${\ displayStyle l_ {ij} = 1}$ Wenn der Begriff im Dokument oder sonst vorhanden ist, oder sonst ${\ displayStyle 0}$
TermFrequenz		${\ displayStyle l_ {ij} = \ mathrm {tf} _ {ij}}$, die Anzahl der Vorkommen des Terms ${\ displayStyle i}$ im Dokument ${\ displayStyle j}$
Protokoll		${\ displayStyle l_ {ij} = \ log (\ mathrm {tf} _ {ij} +1)}$
Augnorm		$oder } {\ Big)}+1} {2}}}$

Einige häufige globale Gewichtungsfunktionen sind in der folgenden Tabelle definiert.

Binär		${\ displayStyle g_ {i} = 1}$
Normal		$oder$
Gfidf		$oder$, wo ${\ displayStyle \ mathrm {gf} _ {i}}$ ist die Gesamtzahl der Laufzeit ${\ displayStyle i}$ tritt in der gesamten Sammlung auf und kommt ${\ displayStyle \ mathrm {df} _ {i}}$ ist die Anzahl der Dokumente, in welcher Begriff ${\ displayStyle i}$ tritt ein.
IDF (inverse Dokumentfrequenz)		$oder$
Entropie		$oder$, wo $oder$

Empirische Studien mit LSI berichten, dass die Gewichtungsfunktionen der Protokoll- und Entropie in der Praxis gut funktionieren, mit vielen Datensätzen.^[31] Mit anderen Worten, jeder Eintrag ${\ displayStyle a_ {ij}}$ von ${\ displayStyle a}$ wird berechnet als:

$oder$

${\ displayStyle a_ {ij} = g_ {i} \ \ log (\ mathrm {tf} _ {ij} +1)}$

Rangreduzierte Singularwertabbauung

Ein Rangreduzierter, Einzelwertzerlegung wird auf der Matrix durchgeführt, um Muster in den Beziehungen zwischen den im Text enthaltenen Begriffen und Konzepten zu bestimmen. Die SVD bildet die Grundlage für LSI.^[32] Es berechnet den Begriff und die Dokumentvektorräume, indem die einzelnen Termfrequenzmatrix angenähert wird. ${\ displayStyle a}$, in drei andere Matrizen - und m durch r Term-Konzept-Vektormatrix ${\ displayStyle t}$, ein r durch r Singularwerte Matrix ${\ displayStyle S}$, und ein n durch r Concept-Dokument-Vektormatrix, ${\ displayStyle d}$, die die folgenden Beziehungen erfüllen:

${\ displayStyle a \ ca. tsd^{t}}$

${\ displaystyle t^{t} t = i_ {r} \ quad d^{t} d = i_ {r}}$

$oder \; i \ neq j}$

In der Formel, A ist der gelieferte m durch n gewichtete Matrix der Termfrequenzen in einer Textsammlung, wo m ist die Anzahl der eindeutigen Begriffe und n ist die Anzahl der Dokumente. T ist ein berechnet m durch r Matrix der Begriffsvektoren wo r ist der Rang von A- Ein Maß für seine einzigartigen Dimensionen ≤ min (m, n). S ist ein berechnet r durch r diagonale Matrix abnehmender einzigartiger Werte und D ist ein berechnet n durch r Matrix der Dokumentvektoren.

Die SVD ist dann gekürzt um den Rang zu reduzieren, indem nur die größten behalten k «r Diagonale Einträge in der Singular Value Matrix S, wo k ist normalerweise auf der Reihenfolge 100 bis 300 Dimensionen. Dies reduziert effektiv den Begriff und die Dokumentvektormatrixgrößen auf m durch k und n durch k beziehungsweise. Die SVD -Operation zusammen mit dieser Reduzierung hat den Einfluss, die wichtigsten semantischen Informationen im Text zu erhalten und gleich A. Dieser reduzierte Satz von Matrizen wird häufig mit einer modifizierten Formel bezeichnet, wie z. B.:

A ≈ a_k = T_k S_k D_k^T

Effiziente LSI -Algorithmen berechnen nur den ersten k Singularwerte und Term- und Dokumentvektoren im Gegensatz zum Berechnen einer vollständigen SVD und dann abschneiden.

Beachten Sie, dass diese Rangreduzierung im Wesentlichen gleich ist wie Hauptkomponentenanalyse (PCA) auf der Matrix A, außer dass PCA die Mittel abnimmt. PCA verliert die Spärlichkeit der A Matrix, die es für große Lexikaner unmöglich machen kann.

Abfragen und Erweiterung von LSI -Vektorräumen

Das berechnete T_k und D_k Matrizen definieren den Begriff und die Dokumentvektorräume, die mit den berechneten Singularwerten, S_kverkörpern die konzeptionellen Informationen, die aus der Dokumentsammlung abgeleitet wurden. Die Ähnlichkeit der Begriffe oder Dokumente in diesen Räumen ist ein Faktor dafür, wie nahe sie in diesen Räumen sind, typischerweise als Funktion des Winkels zwischen den entsprechenden Vektoren berechnet.

Dieselben Schritte werden verwendet, um die Vektoren zu lokalisieren, die den Text von Abfragen und neuen Dokumenten im Dokumentraum eines vorhandenen LSI -Index darstellen. Durch eine einfache Transformation der A = t s d^T Gleichung in das Äquivalent D = a^T T s^–1 Gleichung, ein neuer Vektor, dFür eine Abfrage oder für ein neues Dokument kann durch Berechnung einer neuen Spalte in erstellt werden A und dann die neue Spalte mit multiplizieren T s^–1. Die neue Spalte in A wird unter Verwendung der ursprünglich abgeleiteten globalen Termgewichte berechnet und die gleiche lokale Gewichtungsfunktion auf die Begriffe in der Abfrage oder im neuen Dokument angewendet.

Ein Nachteil beim Berechnen von Vektoren auf diese Weise, wenn neue durchsuchbare Dokumente hinzugefügt werden, sind die Begriffe, die während der SVD -Phase für den ursprünglichen Index nicht bekannt waren, ignoriert. Diese Begriffe werden keinen Einfluss auf die globalen Gewichte und erlernten Korrelationen haben, die aus der ursprünglichen Textsammlung abgeleitet werden. Die berechneten Vektoren für den neuen Text sind jedoch für Ähnlichkeitsvergleiche mit allen anderen Dokumentvektoren immer noch sehr relevant.

Der Prozess der Erweiterung der Dokumentvektorräume für einen LSI -Index mit neuen Dokumenten auf diese Weise wird genannt Einklappung. Obwohl der Zusammenfassungsprozess den neuen semantischen Inhalt des neuen Textes nicht berücksichtigt, liefert das Hinzufügen einer beträchtlichen Anzahl von Dokumenten auf diese Weise weiterhin gute Ergebnisse für Abfragen, solange die von ihnen enthaltenen Begriffe und Konzepte innerhalb des LSI gut dargestellt sind Index, zu dem sie hinzugefügt werden. Wenn die Begriffe und Konzepte eines neuen Satzes von Dokumenten in einen LSI-Index enthalten sein müssen, müssen entweder die Term-Document-Matrix und die SVD neu berechnet werden oder eine inkrementelle Aktualisierungsmethode (wie die in beschriebene in beschrieben ^[13]) wird gebraucht.

Zusätzliche Verwendungen von LSI

Es wird allgemein anerkannt, dass die Fähigkeit, semantisch mit Text zu arbeiten, für moderne Informationsabrufsysteme von wesentlicher Bedeutung ist. Infolgedessen hat sich die Verwendung von LSI in den letzten Jahren erheblich erweitert, da frühere Herausforderungen bei Skalierbarkeit und Leistung überwunden wurden.

LSI wird in einer Vielzahl von Informationsabruf- und Textverarbeitungsanwendungen verwendet, obwohl seine primäre Anwendung für die Konzeptsuche und die automatisierte Dokumentenkategorisierung bestimmt wurde.^[33] Im Folgenden finden Sie einige andere Möglichkeiten, wie LSI verwendet wird:

• Informationsentdeckung^[34] (Ediscovery, Regierungs-/Geheimdienstgemeinschaft, Veröffentlichung)
• Automatisierte Dokumentklassifizierung (Ediscovery, Regierungs-/Geheimdienstgemeinschaft, Veröffentlichung)^[35]
• Textübersicht^[36] (Ediscovery, Veröffentlichung)
• Beziehungsentdeckung^[37] (Regierung, Geheimdienstgemeinschaft, soziale Netzwerke)
• Automatische Generierung von Link -Diagrammen von Einzelpersonen und Organisationen^[38] (Regierung, Geheimdienstgemeinschaft)
• Übereinstimmende technische Papiere und Zuschüsse mit Rezensenten^[39] (Regierung)
• Online -Kundensupport^[40] (Kundenmanagement)
• Bestimmung der Urheberschaft von Dokumenten^[41] (Ausbildung)
• Automatische Keyword -Annotation von Bildern^[42]
• Software -Quellcode verstehen^[43] (Softwareentwicklung)
• Filterung Spam^[44] (Systemadministration)
• Informationsvisualisierung^[45]
• Aufsatz Tor^[46] (Ausbildung)
• Literaturbasierte Entdeckung^[47]
• Vorhersage der Aktienrenditen^[6]
• Trauminhaltsanalyse (Psychologie) ^[7]

LSI wird zunehmend für die Entdeckung des elektronischen Dokuments (EDIScovery) verwendet, um Unternehmen bei der Vorbereitung auf Rechtsstreitigkeiten zu unterstützen. In der Ediscovery ist die Fähigkeit, große Sammlungen unstrukturierter Text auf konzeptioneller Basis zu kategorisieren, zu kategorisieren und zu durchsuchen. Die konzeptbasierte Suche mit LSI wurde bereits 2003 auf den EDIScovery-Prozess angewendet.^[48]

Herausforderungen an LSI

Frühe Herausforderungen für LSI konzentrierten sich auf Skalierbarkeit und Leistung. LSI erfordert relativ hohe Rechenleistung und Speicher im Vergleich zu anderen Informationsabruftechniken.^[49] Mit der Implementierung moderner Hochgeschwindigkeitsprozessoren und der Verfügbarkeit des kostengünstigen Gedächtnisses wurden diese Überlegungen jedoch weitgehend überwunden. In einigen LSI-Anwendungen sind reale Anwendungen mit mehr als 30 Millionen Dokumenten, die vollständig über die Matrix- und SVD-Berechnungen verarbeitet wurden. Eine vollständig skalierbare (unbegrenzte Anzahl von Dokumenten, Online -Schulungen) Implementierung von LSI ist in der Open Source enthalten Gensim Softwarepaket.^[50]

Eine weitere Herausforderung für LSI war die angebliche Schwierigkeit, die optimale Anzahl von Dimensionen für die Durchführung der SVD zu bestimmen. In der Regel ermöglichen weniger Dimensionen breitere Vergleiche der Konzepte, die in einer Textsammlung enthalten sind, während eine höhere Anzahl von Dimensionen spezifischere (oder relevantere) Vergleiche von Konzepten ermöglicht. Die tatsächliche Anzahl von Dimensionen, die verwendet werden können, ist durch die Anzahl der Dokumente in der Sammlung begrenzt. Untersuchungen haben gezeigt, dass rund 300 Dimensionen normalerweise die besten Ergebnisse mit mittelgroßen Dokumentsammlungen (Hunderttausende von Dokumenten) und möglicherweise 400 Dimensionen für größere Dokumentsammlungen (Millionen von Dokumenten) liefern.^[51] Jüngste Studien zeigen jedoch, dass 50-1000 Dimensionen je nach Größe und Art der Dokumentsammlung geeignet sind.^[52] Überprüfen Sie den Anteil der beibehaltenen Varianz, ähnlich wie PCA oder Faktorenanalyse, um die optimale Dimensionalität zu bestimmen, ist für LSI nicht geeignet. Unter Verwendung eines Synonym -Tests oder Vorhersage fehlender Wörter sind zwei mögliche Methoden, um die korrekte Dimensionalität zu finden.^[53] Wenn LSI -Themen als Merkmale in beaufsichtigten Lernmethoden verwendet werden, kann man Vorhersagefehlermessungen verwenden, um die ideale Dimensionalität zu finden.

Siehe auch

• Coh-metrix
• Zusammengesetzte Term Processing
• Verteilungssemantik
• Explizite semantische Analyse
• Latente semantische Zuordnung
• Latente semantische Strukturindexierung
• Hauptkomponentenanalyse
• Probabilistische latente semantische Analyse
• Spamdexing
• Wortvektor
• Themenmodell
  • Latent Dirichlet Allocation

Verweise

Weitere Lektüre

• Landauer, Thomas; Foltz, Peter W.; Laham, Darrell (1998). "Einführung in die latente semantische Analyse" (PDF). Diskursprozesse. 25 (2–3): 259–284. Citeseerx 10.1.1.125.109. doi:10.1080/01638539809545028.
• Deerwester, Scott; Dumais, Susan T.; Furnas, George W.; Landauer, Thomas K.; Harshman, Richard (1990). "Indexierung durch latente semantische Analyse" (PDF). Zeitschrift der 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. Archiviert von das Original (PDF) am 07.07.2012. Originalartikel, in dem das Modell zum ersten Mal freigelegt wurde.
• Berry, Michael; Dumais, Susan T.; O'Brien, Gavin W. (1995). "Verwenden linearer Algebra für intelligente Informationsabruf". {{}}: Journal zitieren erfordert |journal= (Hilfe) (PDF). Illustration der Anwendung von LSA auf das Dokumentieren von Abrufen.
• Chicco, D; Masseroli, M (2015). "Software -Suite für Gene- und Protein -Annotation -Vorhersage und Ähnlichkeitssuche". IEEE/ACM -Transaktionen zur Computerbiologie und Bioinformatik. 12 (4): 837–843. doi:10.1109/tcbb.2014.2382127. PMID 26357324. S2CID 14714823.
• "Latente semantische Analyse". Infovis.
• Fridolin Wild (23. November 2005). "Ein Open -Source -LSA -Paket für R". Kran. Abgerufen 20. November, 2006.
• Thomas Landauer, Susan T. Dumais. "Eine Lösung für Platons Problem: Die latente semantische Analysetheorie des Erwerbs, Induktion und Repräsentation von Wissen". Abgerufen 2007-07-02.

Externe Links

Artikel über LSA

• Latente semantische Analyse, ein Scholarpedia -Artikel über LSA von Tom Landauer, einem der Schöpfer der LSA.

Gespräche und Demonstrationen

• LSA -Übersicht, Rede von Prof. Thomas Hofmann Beschreibung von LSA, ihren Anwendungen im Informationsabruf und deren Verbindungen zu Probabilistische latente semantische Analyse.
• Vervollständigen Sie den LSA -Beispielcode in C# für Windows. Der Demo-Code enthält die Aufzählung von Textdateien, Filterstoppswörter, Stamm, eine dokumentfristige Matrix und SVD.

Implementierungen

Aufgrund seiner Cross-Domain-Anwendungen in Informationsrückgewinnung, Verarbeitung natürlicher Sprache (NLP), Kognitionswissenschaft und ComputerlinguistikLSA wurde implementiert, um viele verschiedene Arten von Anwendungen zu unterstützen.

• Sense Cluster, eine Informations-Abruf-orientierte Perl-Implementierung von LSA
• S-Raum-Paket, eine rechnerische Linguistik und kognitive wissenschaftsorientierte Java-Implementierung von LSA
• Semantische Vektoren Anwendet zufällige Projektion, LSA und reflektierende zufällige Indexierung zu Lucene Termdokumentmatrizen
• Infomap -Projekt, eine NLP-orientierte C-Implementierung von LSA (abgelöst von SemanticVectors Project)
• Text an Matrixgenerator, Eine Matlab-Toolbox zum Generieren von Term-Document-Matrizen aus Textsammlungen mit Unterstützung für LSA
• Gensim Enthält eine Python -Implementierung von LSA für Matrizen, die größer als RAM sind.