50 %
50 %
Information about svd

Published on December 3, 2007

Author: Talya


The Mathematics of Information Retrieval:  The Mathematics of Information Retrieval 11/21/2005 Presented by Jeremy Chapman, Grant Gelven and Ben Lakin Acknowledgments:  Acknowledgments This presentation is based on the following paper: “Matrices, Vector Spaces, and Information Retrieval.” by Michael W. Barry, Zlatko Drmat, and Elizabeth R.Jessup. Indexing of Scientific Works:  Indexing of Scientific Works Indexing primarily done by using the title, author list, abstract, key word list, and subject classification These are created in large part to allow them to be found in a search of scientific documents The use of automated information retrieval (IR) has improved consistency and speed Vector Space Model for IR:  Vector Space Model for IR The basic mechanism for this model is the encoding of a document as a vector All documents’ vectors are stored in a single matrix Latent Semantic Indexing (LSI) replaces the original matrix by a matrix of a smaller rank while maintaining similar information by use of Rank Reduction Creating the Database Matrix :  Creating the Database Matrix Each document is defined in a column of the matrix (d is the number of documents) Each term is defined as a row (t is the number of terms) This gives us a t x d matrix The document vectors span the content Simple Example:  Simple Example Let the six terms as follows: T1: bak(e, ing) T2: recipes T3: bread T4: cake T5: pastr(y, ies) T6: pie The following are the d=5 documents D1: How to Bake Bread Without Recipes D2: The Classical Art of Viennese Pastry D3: Numerical Recipes: The Art of Scientific Computing D4: Breads, Pastries, Pies, and Cakes: Quantity Baking Recipes D5:Pastry: A Book of Best French Recipes Thus the document matrix becomes: A = The matrix A after Normalization:  The matrix A after Normalization Thus after the normalization of the columns of A we get the following: Making a Query:  Making a Query Next we will use the document matrix to ease our search for related documents. Referring to our example we will make the following query: Baking Bread We will now format a query using our terms definitions given before: q= (1 0 1 0 0 0)T Matching the Document to the Query:  Matching the Document to the Query Matching the documents to a given query is typically done by using the cosine of the angle between the query and document vectors The cosine is given as follows: A Query:  A Query By using the cosine formula we would get: We will set our lower limit on our cosine at .5. Thus by conducting a query “baking bread” we get the following two articles: D1: How to Bake Bread Without Recipes D4: Breads, Pastries, Pies, and Cakes: Quantity Baking Recipes Singular Value Decomposition:  Singular Value Decomposition The Singular Value Decomposition (SVD) is used to reduce the rank of the matrix, while also giving a good approximation of the information stored in it The decomposition is written in the following manner: Where U spans the column space of A, is the matrix with singular values of A along the main diagonal, and V spans the row space of A. U and V are also orthogonal. SVD continued:  SVD continued Unlike the QR Factorization, SVD provides us with a lower rank representation of the column and row spaces We know Ak is the best rank-k approximation to A by Eckert and Young’s Theorem that states: Thus the rank-k approximation of A is given as follows: Ak= Uk kVkT Where Uk=the first k columns of U k=a k x k matrix whose diagonal is a set of decreasing values, call them: VkT=is the k x d matrix whose rows are the first k rows of V SVD Factorization :  SVD Factorization Interpretation:  Interpretation From the matrix given on the slide before we notice that if we take the rank-4 matrix has only four non-zero singular values Also the two non-zero columns in tell us that the first four columns of U give us the basis for the column space of A Analysis of the Rank-k Approximations:  Analysis of the Rank-k Approximations Using the following formula we can calculate the relative error from the original matrix to its rank-k approximation: ||A-Ak||F= Thus only a 19% relative error is needed to change from a rank-4 to a rank-3 matrix, however a 42% relative error is necessary to move to a rank-2 approximation from a rank-4 approximation As expected these values are less than the rank-k approximations for the QR factorization Using the SVD for Query Matching:  Using the SVD for Query Matching Using the following formula we can calculate the cosine of the angles between the query and the columns of our rank-k approximation of A. Using the rank-3 approximation we return the first and fourth books again using the cutoff of .5 Term-Term Comparison:  Term-Term Comparison It is possible to modify the vector space model for comparing queries with documents in order to compare terms with terms. When this is added to a search engine it can act as a tool to refine the result First we run our search as before and retrieve a certain number of documents in the following example we will have five documents retrieved. We will then create another document matrix with the remaining information, call it G. Another Example:  Another Example T1:Run(ning) T2:Bike T3:Endurance T4:Training T5:Band T6:Music T7:Fishes D1:Complete Triathlon Endurance Training Manual:Swim, Bike, Run D2:Lake, River, and Sea-Run Fishes of Canada D3:Middle Distance Running, Training and Competition D4:Music Law: How to Run your Band’s Business D5:Running: Learning, Training Competing Terms Documents Analysis of the Term-Term Comparison:  Analysis of the Term-Term Comparison For this we use the following formula: Clustering:  Clustering Clustering is the process by which terms are grouped if they are related such as bike, endurance and training First the terms are split into groups which are related The terms in each group are placed such that their vectors are almost parallel Clusters:  Clusters In this example the first cluster is running The second cluster is bike, endurance and training The third is band and music And the fourth is fishes Analyzing the term-term Comparison:  Analyzing the term-term Comparison We will again use the SVD rank-k approximation Thus the cosine of the angles becomes: Conclusion:  Conclusion Through the use of this model many libraries and smaller collections can index their documents However, as the next presentation will show a different approach is used in large collections such as the internet

Add a comment

Related presentations

Related pages

SvD | Sveriges kvalitetssajt för nyheter

Sveriges ledande mediesajt - Svenska Dagbladets nyhetssajt låter läsarna ta plats och fördjupar nyheterna.
Read more


Offizielle Internetseite des SV Darmstadt 98: News, Teams, Verein, Fanabteilung, Fans, Partner, Tickets, Online-Fanshop und mehr.
Read more

Dragunow-Scharfschützengewehr – Wikipedia

WaffenHQ: Dragunov SWD. In: Abgerufen am 26. Juni 2015. Dragunov sniper rifle SVD. In: Abgerufen am 26. Juni 2015 ...
Read more

Singular value decomposition - Wikipedia

In linear algebra, the singular value decomposition (SVD) is a factorization of a real or complex matrix. It is the generalization of the ...
Read more

Svenska Dagbladet – Wikipedia

Svenska Dagbladet (SvD) ist eine Tageszeitung in Schweden. Sie wird in Stockholm herausgegeben und erscheint im ganzen Land. Die Auflage ist die ...
Read more

Snowboard Germany • Homepage

Nadja Flemming startet mit Platz drei in Europa Cup-Saison Nach den starken Auftritten der Raceboarder vor ein paar Tagen, hat das Freestyle-Team gestern ...
Read more

SVD Verpackungen GmbH I Ahaus, Qualität, Schutz, Liner ...

Die SVD-Verpackungen GmbH hat sich die Natur zum Vorbild genommen und bietet seinen Kunden ein Verpackungssortiment, das auf die Anforderungen ihrer ...
Read more

SVD GBB Softair Gewehre - Kotte & ZellerShop

SVD Softair Gewehre Gas: Airsoft Fans ab 18 Jahren können hier eine Replika der zuverlässigen russischen SV Dragunov Sniper Gewehre online bestellen.
Read more

Dragunov sniper rifle - Wikipedia

Russian-made SVD (top) and SVDS (shortened variant with folding stock) rifles featuring modern synthetic furniture
Read more