CS20c Project Proposal

Jia Mao, Howard Zhou

Title : Information Retrieval Using Singular Value Decomposition (SVD) Based Vector Space Model.

Description :

For this project, we will mainly focus on the paper
Matrices, vector spaces, and information retrieval
Michael W. Berry, Zlatko Drmavc, and Elizabeth R. Jessup, SIAM Review, 41(2):335-362, June 1999
This article has been pre-approved by Professor Arvo.

As additional support, we will also consult the other two papers, namely,
Two Purposes for Matrix Factorization: A Historical Appraisal*
Lawrence Hubert, Jacqueline Meulman, Willem Heiser, SIAM Review, 42(1):68-82, March 2000
Automatic Nonzero Structure Analysis
Aart J. C. Bik and Harry A. G. Wijshoff, SIAM Journal on Computing, 28(5):1576-1587, 1999.

Currently, there exist many disadvantages in retrieving information from large dynamic databases. Referring to Berry's paper, we will explore the automated Information Retrieval(IR) using vector space model to manage and index large text collections. In this model, each document is encoded as a vector and each vector component reflects the importance of a particular term in representing the semantics or meaning of that document. Then the vectors for all documents in a database are stored as the columns of a single matrix. A user's query of the database will be represented as a vector of numbers. Relevant documents in the database are then identified via simple vector operations.

An important concept in this paper, matrix factorization, was introduced in CS20. As QR factorization was discussed in detail in the class, Singular Value Decomposition(SVD), a more complicated extension of QR factorization, is entirely new to us. It is quite challenging to implement both algorithms so that they can handle relatively large matrices. Moreover, we will also familiarize ourselves with modern information retrieval techniques and try to address a practical implementation of this IR method so that it can manage real-world dynamic database systems.

We plan to use Matlab for the linear algebra intensive algorithms, and Perl or Tcl for web-based, real-world database applications. Matlab, Perl are new to both of us, so we will try our best to manage these tools.

Major Milestones

• Week 1:
  Read through Berry's paper carefully and take notes on new concepts and techniques. Track down at least two references (candidates: [9], [10], [11], [17], and [23]). Implement the translation from keywords and documents into vectors and matrices.
• Week 2:
  Gain an indepth Understanding of the key mechanisms presented in the paper and its referrences. Use Hubert's supporting paper for QR factorization, SVD, and how SVD is more powerful than QR. Use the above references for Low-Rank Approximation. Embeded QR factorization in our program to identify and remove redundant information in the matrix representatioin of the database.
• Week 3:
  To make SVD-based models work in practice is currently still under research and involves many details. We will examine the more advanced techniques necessary to make it pratical and understand them. Replace the QR factorization with SVD in our program and compare them.
• Week 4:
  Work on the more difficult indexing and managing tools and try to apply them to our SVD-based model. A dynamic database demonstration is tentative.
• Week 5:
  Summarize the progress and prepare for the in-class presentation. Write up a detailed final report.

Participants

Jia Mao
Howard Zhou
E-mail link to both persons

Alternate Project Ideas

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logrithms on a Quantum Computer
  Peter W. Shor, SIAM Review, 41(2):303-332, June 1999.
• Quantum Computability
  Leonard M. Adleman, SIAM Journal on Computing, 26(5):1524-1540, 1997.
• Approximate Complex Polynomial Evaluation in Near Constant Work Per Point
  Jonh H. Reif, SIAM Journal on Computing, 28(6):2059-2089, 1999.

Page created on 04-25-2000