Latent Semantic Analysis

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Latent Semantic Indexing)

Latent Semantic Indexing (kurz LSI) ist ein (nicht mehr patentgeschütztes[1]) Verfahren des Information Retrieval, das 1990 zuerst von Deerwester et al.[2] 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, Hauptkomponenten von 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 approximiert wird. Dabei wird eine Dimensionsreduktion auf die Bedeutungseinheiten (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 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
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.

Die TD-Matrix wird über die Singulärwertzerlegung in Matrizen aus ihren Eigenvektoren und Eigenwerten 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 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, approximierende TD-Matrix wird als Semantischer Raum[3] bezeichnet.

Algorithmus

  • Die Term-Dokument-Matrix wird berechnet und gegebenenfalls gewichtet, z. B. mittels tf-idf
  • Die Term-Dokument-Matrix wird nun in drei Komponenten zerlegt (Singulärwertzerlegung):
    Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle (A=U\cdot S\cdot V^{T})} .
    Die beiden orthogonalen Matrizen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle U} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V} enthalten dabei Eigenvektoren von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle AA^T} bzw. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A^TA} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S} ist eine Diagonalmatrix mit den Wurzeln der Eigenwerte von , auch Singulärwerte genannt.
  • Über die Eigenwerte in der erzeugten Matrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S} kann man nun die Dimensionsreduktion steuern. Das geschieht durch sukzessives Weglassen des jeweils kleinsten Eigenwertes bis zu einer unbestimmten Grenze .
  • Um eine Suchanfrage Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} (für Query) zu bearbeiten, wird sie in den Semantischen Raum abgebildet. wird dabei als Spezialfall eines Dokumentes der Größe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (m \times 1)} angesehen. Mit folgender Formel wird der (eventuell gewichtete) Queryvektor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} abgebildet:
    Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q = \frac{q^T U_k}{diag(S_k)}}
    Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_k} sind die ersten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} Diagonalelemente von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S} .
  • Jedes Dokument wird wie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} in den Semantischen Raum abgebildet. Danach kann 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 Synonymproblem, aber nur teilweise die Polysemie, das heißt, dass dasselbe Wort verschiedene Bedeutungen haben kann. Der Algorithmus ist sehr rechenaufwendig. Die Komplexität beträgt für die Singulärwertzerlegung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle O(n^2 \cdot k^3)} , wobei die Anzahl der Dokumente + Anzahl der Terme und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} 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ß Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} ist.

Weblinks

Einzelnachweise

  1. ↑ US4839853 und CA1306062, Patentschutz ist abgelaufen
  2. ↑ Scott Deerwester, Susan Dumais, George Furnas, Thomas Landauer, Richard Harshman: Indexing by Latent Semantic Analysis. (PDF; 109 kB) In: Journal of the American society for information science, 1990.
  3. ↑ 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.
Abgerufen von „https://de.wikiup.org/index.php?title=Latent_Semantic_Analysis&oldid=219249231“