www.wikidata.de-de.nina.az
Latent Semantic Indexing kurz LSI ist ein nicht mehr patentgeschutztes 1 Verfahren des Information Retrieval das 1990 zuerst von Deerwester et al 2 erwahnt wurde Verfahren wie das LSI sind insbesondere fur die Suche auf grossen 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 Mahre 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 erwahnt wird wie zum Beispiel bei Seiten auf denen ein Auto als Gewinn angepriesen wird Inhaltsverzeichnis 1 Mathematischer Hintergrund 2 Der Semantische Raum 3 Algorithmus 4 Vor und Nachteile des Verfahrens 5 Weblinks 6 EinzelnachweiseMathematischer Hintergrund BearbeitenDer Name LSI bedeutet dass die Termfrequenz Matrix im Folgenden TD Matrix durch die Singularwertzerlegung angenahert und so approximiert wird Dabei wird eine Dimensionsreduktion auf die Bedeutungseinheiten Konzepte eines Dokumentes durchgefuhrt welche die weitere Berechnung erleichtert LSI ist nur ein zusatzliches Verfahren das auf dem Vektorraum Retrieval aufsetzt Die von dorther bekannte TD Matrix wird durch das LSI zusatzlich bearbeitet um sie zu verkleinern Dies ist gerade fur grossere Dokumentenkollektionen sinnvoll da hier die TD Matrizen im Allgemeinen sehr gross werden Dazu wird die TD Matrix uber die Singularwertzerlegung zerlegt Danach werden unwichtige Teile der TD Matrix abgeschnitten Diese Verkleinerung hilft Komplexitat 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 Bearbeiten nbsp LSI Die Abbildung zeigt eine typische Term Dokument Matrix 1 in der fur jeden Term Wort angegeben wird in welchen Dokumenten er vorkommt Die ursprunglichen 5 7 Dimensionen konnen 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 uber die Singularwertzerlegung in Matrizen aus ihren Eigenvektoren und Eigenwerten aufgespalten Die Idee ist dass die TD Matrix Reprasentant des Dokumentes aus Hauptdimensionen fur die Bedeutung des Dokuments wichtige Worter und weniger wichtigen Dimensionen fur die Bedeutung des Dokuments relativ unwichtige Worter besteht Erstere sollen dabei erhalten bleiben wahrend letztere vernachlassigt werden konnen Auch konnen hier Konzepte das heisst von der Bedeutung her ahnliche Worter im Idealfalle Synonyme zusammengefasst werden LSI generalisiert also die Bedeutung von Wortern So kann die ubliche Dimensionsanzahl deutlich verringert werden indem nur die Konzepte verglichen werden Bestunden die untersuchten Dokumente Texte aus den vier Wortern Gaul Pferd Tur und Tor so wurden Gaul und Pferd zu einem Konzept zusammengefasst genauso wie Tur 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 grossen TD Matrizen die Einsparung in gunstigen Fallen enorm ist Diese dimensionsreduzierte approximierende TD Matrix wird als Semantischer Raum 3 bezeichnet Algorithmus BearbeitenDie Term Dokument Matrix wird berechnet und gegebenenfalls gewichtet z B mittels tf idf Die Term Dokument Matrix A displaystyle A nbsp wird nun in drei Komponenten zerlegt Singularwertzerlegung A U S V T displaystyle A U cdot S cdot V T nbsp Die beiden orthogonalen Matrizen U displaystyle U nbsp und V displaystyle V nbsp enthalten dabei Eigenvektoren von A A T displaystyle AA T nbsp bzw A T A displaystyle A T A nbsp S displaystyle S nbsp ist eine Diagonalmatrix mit den Wurzeln der Eigenwerte von A T A displaystyle A T A nbsp auch Singularwerte genannt Uber die Eigenwerte in der erzeugten Matrix S displaystyle S nbsp kann man nun die Dimensionsreduktion steuern Das geschieht durch sukzessives Weglassen des jeweils kleinsten Eigenwertes bis zu einer unbestimmten Grenze k displaystyle k nbsp Um eine Suchanfrage q displaystyle q nbsp fur Query zu bearbeiten wird sie in den Semantischen Raum abgebildet q displaystyle q nbsp wird dabei als Spezialfall eines Dokumentes der Grosse m 1 displaystyle m times 1 nbsp angesehen Mit folgender Formel wird der eventuell gewichtete Queryvektor q displaystyle q nbsp abgebildet Q q T U k d i a g S k displaystyle Q frac q T U k diag S k nbsp S k displaystyle S k nbsp sind die ersten k displaystyle k nbsp Diagonalelemente von S displaystyle S nbsp Jedes Dokument wird wie q displaystyle q nbsp in den Semantischen Raum abgebildet Danach kann q displaystyle q nbsp zum Beispiel uber die Kosinus Ahnlichkeit oder das Skalarprodukt mit dem Dokument verglichen werden Vor und Nachteile des Verfahrens BearbeitenDer Semantische Raum das heisst die auf die Bedeutungen reduzierte TD Matrix spiegelt die den Dokumenten unterliegende Struktur wider deren Semantik Die ungefahre Position im Vektorraum des Vektorraum Retrieval wird dabei beibehalten Die Projektion auf die Eigenwerte gibt dann die Zugehorigkeit zu einem Konzept an Schritte 4 und 5 des Algorithmus Das Latent Semantic Indexing lost elegant das Synonymproblem aber nur teilweise die Polysemie das heisst dass dasselbe Wort verschiedene Bedeutungen haben kann Der Algorithmus ist sehr rechenaufwendig Die Komplexitat betragt fur die Singularwertzerlegung O n 2 k 3 displaystyle O n 2 cdot k 3 nbsp wobei n displaystyle n nbsp die Anzahl der Dokumente Anzahl der Terme und k displaystyle k nbsp die Anzahl der Dimensionen ist Dieses Problem lasst sich umgehen indem zur okonomischen Berechnung einer von vorneherein reduzierten TD Matrix das Lanczos Verfahren verwendet wird Die Singularwertzerlegung 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 gross k displaystyle k nbsp ist Weblinks BearbeitenSemager deutsches Projekt zur Berechnung von Wortverwandtschaften Webbuch zum Information Retrieval SVDLIBC Programmbibliothek zur Singularwertzerlegung mittels des Lanczos Algorithmus lsa colorado eduEinzelnachweise Bearbeiten US4839853 und CA1306062 Patentschutz ist abgelaufen 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 E Leopold On Semantic Spaces In LDV Forum Zeitschrift fur Computerlinguistik und Sprachtechnologie Journal for Computational Linguistics and Language Technology Vol 20 Heft 1 2005 S 63 86 Abgerufen von https de wikipedia org w index php title Latent Semantic Analysis amp oldid 219249231