Latent Semantic Indexing

Latent Semantic Indexing

Latent Semantic Indexing (kurz LSI, englisch für schwache Bedeutungseinordnung) ist ein (patentgeschütztes) Verfahren des Information Retrieval, das 1990 zuerst von Deerwester et al.[1] 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 beispielsweise im Internet stehen), diejenigen herauszufinden, in denen es um Autos geht, 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).

Inhaltsverzeichnis

Mathematischer Hintergrund

Der Name LSI meint, dass die Term-Dokument-Matrix (im Folgenden TD-Matrix) durch die Singulärwertzerlegung angenähert und so approximiert wird. Dabei wird eine Dimensionreduktion auf die Bedeutungseinheiten (Konzepte) eines Dokumentes durchgeführt, die 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

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 5x7 Dimensionen können hier auf 2x7 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 die, 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 bezeichnet.

Algorithmus

  • Die Term-Dokument-Matrix wird berechnet und gegebenenfalls gewichtet, z.B. mittels tf-idf
  • Die Term-Dokument-Matrix A wird nun in drei Komponenten zerlegt (Singulärwertzerlegung):
(A = U \cdot S \cdot V).
Die beiden orthogonalen Matrizen U und V enthalten dabei Eigenvektoren von ATA bzw. AAT, S ist eine Diagonalmatrix mit den Wurzeln der Eigenwerte von ATA, auch Singulärwerte genannt.
  • Über die Eigenwerte in der erzeugten Matrix S kann man nun die Dimensionsreduktion steuern. Das geschieht durch sukzessives Weglassen des jeweils kleinsten Eigenwertes bis zu einer unbestimmten Grenze k.
  • Um eine Suchanfrage q (für Query) zu bearbeiten, wird sie in den Semantischen Raum abgebildet. q wird dabei als Spezialfall eines Dokumentes der Größe (m \times 1) angesehen. Mit folgender Formel wird der (eventuell gewichtete) Queryvektor q abgebildet:
Q = \frac{q^T U_k}{diag(S_k)}
Sk sind die ersten k Diagonalelemente von S.
  • Jedes Dokument wird wie q in den Semantischen Raum abgebildet. Danach kann q 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 rechenaufwändig. Die Komplexität beträgt für die Singulärwertzerlegung O(n^2 \cdot k^3), wobei n die Anzahl der Dokumente + Anzahl der Terme und 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 wieviele Dimensionen soll die Term-Dokument-Matrix verkleinert werden, also wie groß ist k.

Siehe auch

Weblinks

Quellen

  1. Indexing by Latent Semantic Analysis, Scott Deerwester, Susan Dumais, George Furnas, Thomas Landauer und Richard Harshman (pdf)

Wikimedia Foundation.

Игры ⚽ Поможем написать курсовую

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Latent semantic analysis — (LSA) is a technique in natural language processing, in particular in vectorial semantics, of analyzing relationships between a set of documents and the terms they contain by producing a set of concepts related to the documents and terms. LSA was …   Wikipedia

  • Latent Semantic Analysis — Latent Semantic Indexing (kurz LSI) ist ein (patentgeschütztes) Verfahren des Information Retrieval, das 1990 zuerst von Deerwester et al.[1] erwähnt wurde. Verfahren wie das LSI sind insbesondere für die Suche auf großen Datenmengen wie dem… …   Deutsch Wikipedia

  • Latent Semantic Analysis — Analyse sémantique latente L’analyse sémantique latente (LSA, de l anglais : Latent semantic analysis) ou indexation sémantique latente (ou LSI, de l anglais : Latent semantic indexation) est un procédé de traitement des langues… …   Wikipédia en Français

  • Latent Semantic Structure Indexing — (LaSSI) is a technique for calculating chemical similarity derived from Latent semantic analysis (LSA).LaSSI was developed at Merck Co. and patented in 2007 [http://patft.uspto.gov/netacgi/nph Parser?patentnumber=7219020] by Richard Hull, Eugene… …   Wikipedia

  • Probabilistic latent semantic analysis — (PLSA), also known as probabilistic latent semantic indexing (PLSI, especially in information retrieval circles) is a statistical technique for the analysis of two mode and co occurrence data. PLSA evolved from Latent semantic analysis, adding a… …   Wikipedia

  • Latent Semantisches Indizieren — Die Latent semantische Indizierung, kurz LSI genannt, ist eine Methode, um Dokumente automatisch zu klassifizieren. Mit dieser Methode kann eine Suchmaschine feststellen, um was es bei einem Text oder einer Internetseite geht. Man nimmt einfach… …   Deutsch Wikipedia

  • Latent semantische Indizierung — Die Latent semantische Indizierung, kurz LSI genannt, ist eine Methode, um Dokumente automatisch zu klassifizieren. Mit dieser Methode kann eine Suchmaschine feststellen, um was es bei einem Text oder einer Internetseite geht. Man nimmt einfach… …   Deutsch Wikipedia

  • Latent semantisches Indizieren — Die Latent semantische Indizierung, kurz LSI genannt, ist eine Methode, um Dokumente automatisch zu klassifizieren. Mit dieser Methode kann eine Suchmaschine feststellen, um was es bei einem Text oder einer Internetseite geht. Man nimmt einfach… …   Deutsch Wikipedia

  • Semantic mapping (statistics) — The semantic mapping (SM) is a dimensionality reduction method that extracts new features by clustering the original features in semantic clusters and combining features mapped in the same cluster to generate an extracted feature. Given a data… …   Wikipedia

  • Latent Dirichlet allocation — In statistics, latent Dirichlet allocation (LDA) is a generative model that allows sets of observations to be explained by unobserved groups which explain why some parts of the data are similar. For example, if observations are words collected… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”