imported>Saehrimnir: /* Mathematischer Hintergrund */ BKL Fix

2025-07-29T10:54:23Z

Mathematischer Hintergrund: BKL Fix

Neue Seite

'''Latent Semantic Indexing''' (kurz '''LSI''') ist ein (nicht mehr [[patent]]geschütztes<ref>US4839853 und CA1306062, Patentschutz ist abgelaufen</ref>) Verfahren des [[Information Retrieval]], das 1990 zuerst von [[Scott Deerwester|Deerwester]] et al.<ref>Scott Deerwester, Susan Dumais, George Furnas, Thomas Landauer, Richard Harshman: [http://lsa.colorado.edu/papers/JASIS.lsi.90.pdf ''Indexing by Latent Semantic Analysis.''] (PDF; 109 kB) In: ''Journal of the American society for information science'', 1990.</ref> erwähnt wurde. Verfahren wie das ''LSI'' sind insbesondere für die Suche auf großen Datenmengen wie dem [[Internet]] von Interesse. Das Ziel von ''LSI'' ist es, [[Hauptkomponentenanalyse|Hauptkomponenten]] von [[Elektronisches Dokument|Dokumenten]] zu finden. Diese Hauptkomponenten (Konzepte) kann man sich als generelle Begriffe vorstellen. So ist ''Pferd'' zum Beispiel ein Konzept, das Begriffe wie ''[[Mähre]]'', ''Klepper'' oder ''Gaul'' umfasst. Somit ist dieses Verfahren zum Beispiel dazu geeignet, aus sehr vielen Dokumenten (wie sie sich beispielsweise im Internet finden lassen), diejenigen herauszufinden, die sich thematisch mit ‘Autos’ befassen, auch wenn in ihnen das Wort ''Auto'' nicht explizit vorkommt. Des Weiteren kann ''LSI'' dabei helfen, Artikel, in denen es wirklich um Autos geht, von denen zu unterscheiden, in denen nur das Wort ''Auto'' erwähnt wird (wie zum Beispiel bei Seiten, auf denen ein Auto als Gewinn angepriesen wird).

== Mathematischer Hintergrund ==

Der Name ''LSI'' bedeutet, dass die [[Termfrequenz]]-Matrix (im Folgenden TD-Matrix) durch die [[Singulärwertzerlegung]] angenähert und so [[Approximation|approximiert]] wird. Dabei wird eine [[Dimensionsreduktion]] auf die Bedeutungseinheiten ([[Begriff|Konzepte]]) eines Dokumentes durchgeführt, welche die weitere Berechnung erleichtert.

''LSI'' ist nur ein zusätzliches Verfahren, das auf dem [[Vektorraum-Retrieval]] aufsetzt. Die von dorther bekannte TD-Matrix wird durch das ''LSI'' zusätzlich bearbeitet, um sie zu verkleinern. Dies ist gerade für größere Dokumentenkollektionen sinnvoll, da hier die TD-Matrizen im Allgemeinen sehr groß werden. Dazu wird die TD-Matrix über die [[Singulärwertzerlegung]]  zerlegt. Danach werden „unwichtige“ Teile der TD-Matrix abgeschnitten. Diese Verkleinerung hilft, [[Komplexität (Informatik)|Komplexität]] und damit Rechenzeit beim Retrievalprozess (Vergleich der Dokumente oder Anfragen) zu sparen.

Am Ende des [[Algorithmus]] steht eine neue, kleinere TD-Matrix, in der die Terme der originalen TD-Matrix zu Konzepten generalisiert sind.

== Der Semantische Raum ==

[[Datei:LSI - WP.jpg|gerahmt|rechts|''LSI'' – Die Abbildung zeigt eine typische Term-Dokument-Matrix  (1), in der für jeden Term (Wort) angegeben wird, in welchen Dokumenten er vorkommt. Die ursprünglichen 5×7 Dimensionen können hier auf 2×7 reduziert werden (2). So werden ''brain'' und ''lung'' in einem Konzept zusammengefasst, ''data'', ''information'' und ''retrieval'' in einem anderen.]]
<span style="white-space:nowrap">Die TD-Matrix wird über die Singulärwertzerlegung</span> in Matrizen aus ihren [[Eigenvektor]]en und [[Eigenwert]]en aufgespalten. Die Idee ist, dass die TD-Matrix (Repräsentant des Dokumentes) aus Hauptdimensionen (für die Bedeutung des Dokuments wichtige Wörter) und weniger wichtigen Dimensionen (für die Bedeutung des Dokuments relativ unwichtige Wörter) besteht. Erstere sollen dabei erhalten bleiben, während letztere vernachlässigt werden können. Auch können hier Konzepte, das heißt von der Bedeutung her ähnliche Wörter (im Idealfalle [[Synonymie|Synonyme]]), zusammengefasst werden. ''LSI'' generalisiert also die Bedeutung von Wörtern. So kann die übliche Dimensionsanzahl deutlich verringert werden, indem nur die Konzepte verglichen werden. Bestünden die untersuchten Dokumente (Texte) aus den vier Wörtern Gaul, Pferd, Tür und Tor, so würden Gaul und Pferd zu einem Konzept zusammengefasst, genauso wie Tür und Tor zu einem anderen. Die Anzahl der Dimensionen wird hierbei von 4 (in der originalen TD-Matrix) auf 2 (in der generalisierten TD-Matrix) verringert. Man kann sich gut vorstellen, dass bei großen TD-Matrizen die Einsparung in günstigen Fällen enorm ist. Diese dimensionsreduzierte, [[Approximation|approximierende]] TD-Matrix wird als ''Semantischer Raum''<ref>E. Leopold: ''On Semantic Spaces.'' In: ''LDV-Forum. Zeitschrift für Computerlinguistik und Sprachtechnologie / Journal for Computational Linguistics and Language Technology'', Vol. 20, Heft 1, 2005, S. 63–86.</ref> bezeichnet.

== Algorithmus ==

* Die Term-Dokument-Matrix wird berechnet und gegebenenfalls gewichtet, z. B. mittels [[tf-idf]]
* Die Term-Dokument-Matrix <math>A</math> wird nun in drei Komponenten zerlegt (Singulärwertzerlegung):
*: <math>(A = U \cdot S \cdot V^T)</math>.
*: Die beiden orthogonalen Matrizen <math>U</math> und <math>V</math> enthalten dabei Eigenvektoren von <math>AA^T</math> bzw. <math>A^TA</math>, <math>S</math> ist eine [[Diagonalmatrix]] mit den Wurzeln der Eigenwerte von <math>A^T A</math>, auch Singulärwerte genannt.
* Über die Eigenwerte in der erzeugten Matrix <math>S</math> kann man nun die Dimensionsreduktion steuern. Das geschieht durch sukzessives Weglassen des jeweils kleinsten Eigenwertes bis zu einer unbestimmten Grenze <math>k</math>.
* Um eine Suchanfrage <math>q</math> (für Query) zu bearbeiten, wird sie in den Semantischen Raum abgebildet. <math>q</math> wird dabei als Spezialfall eines Dokumentes der Größe <math>(m \times 1)</math> angesehen. Mit folgender Formel wird der (eventuell gewichtete) Queryvektor <math>q</math> abgebildet:
*: <math>Q = \frac{q^T U_k}{diag(S_k)}</math>
*: <math>S_k</math> sind die ersten <math>k</math> [[Diagonalelement]]e von <math>S</math>.
* Jedes Dokument wird wie <math>q</math> in den Semantischen Raum abgebildet. Danach kann <math>q</math> zum Beispiel über die [[Kosinus-Ähnlichkeit]] oder das [[Skalarprodukt]] mit dem Dokument verglichen werden.

== Vor- und Nachteile des Verfahrens ==

Der Semantische Raum (das heißt die auf die Bedeutungen reduzierte TD-Matrix) spiegelt die den Dokumenten unterliegende Struktur wider, deren Semantik. Die ungefähre Position im Vektorraum des [[Vektorraum-Retrieval]] wird dabei beibehalten. Die Projektion auf die Eigenwerte gibt dann die Zugehörigkeit zu einem Konzept an (Schritte 4 und 5 des Algorithmus). Das Latent Semantic Indexing löst elegant das [[Synonymie|Synonymproblem]], aber nur teilweise die [[Polysemie]], das heißt, dass dasselbe Wort verschiedene Bedeutungen haben kann. Der Algorithmus ist sehr rechenaufwendig. Die [[Komplexität (Informatik)|Komplexität]] beträgt für die [[Singulärwertzerlegung]] <math>O(n^2 \cdot k^3)</math>, wobei <math>n</math> die Anzahl der Dokumente + Anzahl der Terme und <math>k</math> die Anzahl der Dimensionen ist. Dieses Problem lässt sich umgehen, indem zur ökonomischen Berechnung einer von vorneherein reduzierten TD-Matrix das [[Lanczos-Verfahren]] verwendet wird. Die Singulärwertzerlegung muss zudem stets wiederholt werden, wenn neue Terme oder Dokumente hinzukommen. Ein weiteres Problem ist das Dimensionsproblem: auf wie viele Dimensionen die Term-Dokument-Matrix verkleinert werden soll, also wie groß <math>k</math> ist.

== Weblinks ==
* [http://www.semager.de/ Semager] – deutsches Projekt zur Berechnung von Wortverwandtschaften
* [http://information-retrieval.de/ Webbuch zum Information Retrieval]
* [http://tedlab.mit.edu/~dr/SVDLIBC/ SVDLIBC] – [[Programmbibliothek]] zur Singulärwertzerlegung mittels des Lanczos-Algorithmus
* [http://lsa.colorado.edu/ lsa.colorado.edu]

== Einzelnachweise ==
<references />

[[Kategorie:Dokumentation]]
[[Kategorie:Business Intelligence]]
[[Kategorie:Multivariate Statistik]]
[[Kategorie:Information Retrieval]]

Latent Semantic Analysis - Versionsgeschichte

imported>Saehrimnir: /* Mathematischer Hintergrund */ BKL Fix