INFORMATION RETRIEVAL USING STATISTICAL
`
`CLASSIFICATION
`
`a dissertation
`
`submitted to the department of statistics
`
`and the committee on graduate studies
`
`of stanford university
`
`in partial fulfillment of the requirements
`
`for the degree of
`
`doctor of philosophy
`
`By
`
`David A(cid:2) Hull
`
`November 
`
`Petitioner Google Ex-1038, 0001
`
`

`

`c(cid:0) Copyright  by David A(cid:5) Hull
`
`All Rights Reserved
`
`ii
`
`Petitioner Google Ex-1038, 0002
`
`

`

`I certify that I have read this dissertation and that in my
`
`opinion it is fully adequate(cid:6) in scope and in quality(cid:6) as a
`
`dissertation for the degree of Doctor of Philosophy(cid:2)
`
`Jerome Friedman
`(cid:7)Principal Adviser(cid:8)
`
`I certify that I have read this dissertation and that in my
`
`opinion it is fully adequate(cid:6) in scope and in quality(cid:6) as a
`
`dissertation for the degree of Doctor of Philosophy(cid:2)
`
`Arthur Owen
`
`I certify that I have read this dissertation and that in my
`
`opinion it is fully adequate(cid:6) in scope and in quality(cid:6) as a
`
`dissertation for the degree of Doctor of Philosophy(cid:2)
`
`Jan Pedersen
`Xerox Palo Alto Research Center
`
`Approved for the University Committee on Graduate
`
`Studies(cid:9)
`
`Dean of Graduate Studies
`
`iii
`
`Petitioner Google Ex-1038, 0003
`
`

`

`Acknowledgements
`
`Thanks to Jan for patiently sticking with me and keeping me directed towards the
`
`(cid:10)nal goal(cid:6) the completion of this work(cid:2)
`
`Thanks to Jerry for always being willing to help(cid:6) no matter when I appeared at
`
`his door(cid:2)
`
`Thanks to Hinrich(cid:6) Marti(cid:6) and all my other colleagues in ISTL(cid:11)QCA at Xerox PARC
`
`who have provided lots of inspiration and advice over the years(cid:2)
`
`Thanks to Natalie for all her love and support(cid:2)
`
`iv
`
`Petitioner Google Ex-1038, 0004
`
`

`

`Abstract
`
`In the classical information retrieval (cid:7)IR(cid:8) problem(cid:6) the system must (cid:10)nd all docu(cid:12)
`
`ments in a collection that are related to a topic de(cid:10)ned by a user(cid:13)s query(cid:2) A common
`
`approach to the IR problem is to represent documents and the query as vectors of
`
`term frequencies and rank the documents in the collection according to their inner
`
`product similarity with respect to the query(cid:2) When a sample of evaluated docu(cid:12)
`
`ments is available in addition to the query (cid:7)often called routing(cid:8)(cid:6) the problem can be
`
`attacked using techniques based on statistical classi(cid:10)cation(cid:2) In order for statistical
`
`classi(cid:10)cation to be a feasible approach(cid:6) the system must produce a relatively small
`
`set of high quality feature variables(cid:2) It turns out that individual words(cid:6) due to their
`
`quantity and ambiguity(cid:6) are not optimal features(cid:2) Previous work has focused on a
`
`technique known as Latent Semantic Indexing (cid:7)LSI(cid:8)(cid:6) which applies the singular value
`
`decomposition to a term(cid:12)document matrix and represents terms and documents by
`
`linear combinations of orthogonal indexing variables(cid:2)
`
`The research presented in this thesis accomplishes the following goals(cid:2) It provides
`
`a thorough discussion of evaluation in information retrieval experiments(cid:2) It intro(cid:12)
`
`duces the concept of a local LSI decomposition(cid:2) LSI is used separately on a set of
`
`documents in the local region surrounding each query(cid:6) creating query(cid:12)speci(cid:10)c feature
`
`variables and making the LSI technique feasible for very large document collections(cid:2)
`
`It applies the classi(cid:10)cation technique known as Discriminant Analysis to the routing
`
`problem and presents experimental results on two text collections(cid:2) It demonstrates
`
`that using a local LSI decomposition improves retrieval performance and represents
`
`documents using a relatively small number of feature variables(cid:2) It (cid:10)nds that Dis(cid:12)
`
`criminant Analysis sometimes leads to additional performance gains but that more
`
`research is needed to determine the optimal size and shape of the local region(cid:2)
`
`v
`
`Petitioner Google Ex-1038, 0005
`
`

`

`Contents
`
`Acknowledgements
`
`Abstract
`
` An Introduction to Information Retrieval
`
` (cid:2) The Information Access Spectrum (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
` (cid:2)
`
`Important De(cid:10)nitions in IR (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
` (cid:2) Forms of the Classical IR Problem (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
` (cid:2) Nature of IR Data
`
`(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
` (cid:2)
`
`IR as a Statistical Problem (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
` (cid:2) Goals of this Thesis (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`iv
`
`v
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` (cid:2) Outline of Subsequent Chapters (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`
`
` The Basics of the IR System
`
`(cid:2) The Inverted Index (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2) Lexical Analysis (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2)(cid:2) The Stop List (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2)(cid:2)
`
`Stemming Algorithms
`
`(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2) The Text Database System (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
` Search Strategies in Information Retrieval
`
` (cid:2) Boolean Retrieval (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
` (cid:2) (cid:2) Drawbacks of Boolean Model
`
`(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
` (cid:2) (cid:2)
`
`Improving the Boolean Model
`
`(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`
`
` 
`
` 
`
` 
`
` 
`
` 
`
`
`
`
`
`
`
`
`
`vi
`
`Petitioner Google Ex-1038, 0006
`
`

`

` (cid:2) The Vector Space Model
`
`(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
` (cid:2)(cid:2) Using the VSM for retrieval
`
`(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
` (cid:2)(cid:2) Term Weighting (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
` (cid:2)(cid:2)
`
`Subtopics and Passage Retrieval (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
` (cid:2) Relevance Feedback (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
` (cid:2) (cid:2) Feedback using the VSM (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
` (cid:2) (cid:2)
`
`Improving Feedback Performance (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
` (cid:2) (cid:2) Assumptions of Relevance Feedback (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
` (cid:2) (cid:2) Feedback using a Probabilistic Model (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
` (cid:2) The Routing Problem (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
` Feature Selection and Dimension Reduction
`
`(cid:2) Problems with the VSM (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2)
`
`Improving the VSM (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2)(cid:2) Query Expansion (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2)(cid:2) Word Sense Disambiguation (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2)(cid:2) Phrase Modelling (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2) Latent Semantic Indexing (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2) (cid:2) Description of LSI
`
`(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2) (cid:2) Bene(cid:10)ts of Using LSI (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2) (cid:2) Drawbacks of Using LSI
`
`(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2) (cid:2) Using LSI for Information Retrieval (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2) (cid:2) Performance of LSI in Retrieval Experiments (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
` Evaluation
`
`(cid:2) Test Collections (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2) (cid:2)
`
`Important Characteristics of the Test Collection (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2) (cid:2) Problems with Test Collections
`
`(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2) (cid:2) The Alternative (cid:12) User Studies (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2) Performance Measures
`
`(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2)(cid:2) Precision and Recall
`
`(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2)(cid:2) Averaging Methods (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` 
`
`
`
` 
`
` 
`
` 
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`vii
`
`Petitioner Google Ex-1038, 0007
`
`

`

`(cid:2) Assumptions in Evaluation (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2) (cid:2) Normalization (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2) (cid:2) Problems with the DCV (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2) (cid:2) Relevance Feedback and the P(cid:12)R curve (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2) Univariate Measures of Performance (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2)(cid:2) P(cid:12)R based (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2)(cid:2) Other Measures (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2) An Alternative Method of Evaluation (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2) Hypothesis Testing (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2)(cid:2) A Brief Introduction (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2)(cid:2) Comparisons between two methods (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2)(cid:2) The Signi(cid:10)cance Tests
`
`(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2)(cid:2) Optimal two(cid:12)sample tests in IR (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2)(cid:2) Comparisons between more than two methods (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2)(cid:2) General Comments (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
` Classi(cid:10)cation Methods
`
`(cid:2) Properties of the IR Problem (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2) Discriminant Analysis
`
`(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2)(cid:2) The Discriminant Rules
`
`(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2)(cid:2) Linear vs(cid:2) Quadratic (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2)(cid:2) Regularized Discriminant Analysis
`
`(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2) Logistic Regression (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2) Optimal Separating Hyperplanes
`
`(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2) Classi(cid:10)cation Trees (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
` Retrieval Experiments(cid:12) Cran(cid:10)eld
`
`(cid:2) The Cran(cid:10)eld Collection (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2) Baseline Experiments using the VSM (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2)(cid:2)
`
`Implementation of Vector Space Search (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2)(cid:2) Term Weighting and Basic Search (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` 
`
` 
`
` 
`
`
`
`(cid:2)(cid:2) Baseline(cid:9) Relevance Feedback (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`viii
`
`Petitioner Google Ex-1038, 0008
`
`

`

`(cid:2) Baseline(cid:9) Routing (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 
`
`(cid:2) LSI Experiments
`
`(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 
`
`(cid:2)(cid:2) Description of Method (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 
`
`(cid:2)(cid:2) Experimental Results (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2)(cid:2) Routing(cid:9) Detailed look at Evaluation (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2) Routing and Classi(cid:10)cation (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2)(cid:2)
`
`Initial Experiment
`
`(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 
`
`(cid:2)(cid:2) A Local LSI Representation (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 
`
`(cid:2)(cid:2) Experimental Results (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 
`
`(cid:2) Discussion (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 
`
` Retrieval Experiments(cid:12) Wall Street Journal
`
` 
`
`(cid:2) The Wall Street Journal
`
`(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 
`
`(cid:2)
`
`Initial Experiments (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 
`
`(cid:2)(cid:2) Baseline from the VSM (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 
`
`(cid:2)(cid:2) LSI on the WSJ (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 
`
`(cid:2) Query(cid:12)Speci(cid:10)c Screening of the Collection (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 
`
`(cid:2) (cid:2) The Screening Process (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2) (cid:2) Local LSI
`
`(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`(cid:2) Classi(cid:10)cation Experiments (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 
`
`(cid:2)(cid:2) LDA and Logistic Regression (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 
`
`(cid:2)(cid:2) Regularized Discriminant Analysis
`
`(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 
`
`(cid:2) Discussion (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 
`
` Conclusion
`
` 
`
` (cid:2) The Vector Space Model
`
`(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 
`
` (cid:2) Dimension Reduction and Classi(cid:10)cation (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 
`
` (cid:2) Evaluation and Retrieval Experiments
`
`(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 
`
` (cid:2) Extensions of this work (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 
`
`Bibliography
`
` 
`
`ix
`
`Petitioner Google Ex-1038, 0009
`
`

`

`Chapter
`
`An Introduction to Information
`
`Retrieval
`
`Information comes in many forms(cid:9) news(cid:6) (cid:10)nancial data(cid:6) scienti(cid:10)c research(cid:6) etc (cid:2)
`
`(cid:2)
`
`(cid:2) and represents one of the most important commodities in the modern world(cid:2)
`
`All major political(cid:6) economic(cid:6) and intellectual endeavors rely on the quick and easy
`
`(cid:21)ow of information through a variety of media(cid:6) such as books(cid:6) radio(cid:6) television(cid:6) and
`
`electronic networks(cid:2) Modern computing and networking technology make it possible
`
`to organize(cid:6) store(cid:6) and transport large bodies of data with minimal e(cid:22)ort anywhere
`
`in the world(cid:2) Without question(cid:6) we have moved into the information age(cid:2)
`
`With so much material so easily accessible(cid:6) many organizations and individuals
`
`have realized that the real issue is no longer getting enough information(cid:6) but sorting
`
`out what is useful to them from vast quantities of useless material(cid:2) Information re(cid:12)
`
`trieval systems(cid:6) computers and software designed to index(cid:6) store(cid:6) and provide easy
`
`access to data(cid:6) are rapidly developing to meet this need(cid:2) As one of their most impor(cid:12)
`
`tant features(cid:6) the systems provide search tools(cid:6) algorithms which map an expression
`
`of the user(cid:13)s information need into a mathematical form which is then used to identify
`
`relevant material in the database(cid:2)
`
`Developing accurate search methods requires solving several challenging problems
`
`and will represent the core of the work in this thesis(cid:2) While information can be
`
`stored and transmitted in many forms(cid:6) including speech(cid:6) images(cid:6) and video(cid:6) it is
`
`
`
`Petitioner Google Ex-1038, 0010
`
`

`

`CHAPTER (cid:3) AN INTRODUCTION TO INFORMATION RETRIEVAL
`
`
`
`written text that still predominates in most retrieval systems(cid:2) In this work(cid:6) we will
`
`focus on developing new and better search methods for text(cid:12)based systems(cid:2)
`
` (cid:2) The Information Access Spectrum
`
`People approach document collections with a broad range of di(cid:22)erent information
`
`needs(cid:2) There is an entire spectrum of goals for information access ranging from
`
`general to speci(cid:10)c requests(cid:2) Some examples of potential requests to a retrieval system(cid:6)
`
`moving from speci(cid:10)c to general are(cid:9)
`
` (cid:8) Find the answer to this speci(cid:10)c question(cid:2)
`
`(cid:8) Find the document with title A or all documents by author B(cid:2)
`
` (cid:8) Find all articles in the collection that refer to this topic(cid:2)
`
`(cid:8) Produce a summary of the contents of this collection on these topics(cid:2)
`
`(cid:8) Produce a summary of the contents of this collection(cid:2)
`
`All of these requests could be valid queries for a retrieval system(cid:6) although most
`
`fall outside the domain of classical information retrieval(cid:2) A traditional de(cid:10)nition for
`
`information retrieval (cid:7)IR(cid:8) is (cid:23)(cid:24)(cid:9) (cid:25)An information retrieval system informs (cid:23)the user
`
`of(cid:24) (cid:2)
`
`(cid:2)
`
`(cid:2) the existence and whereabouts of documents relating to his request(cid:2)
`
`(cid:23)It(cid:24)
`
`does not inform the user on the subject of his request(cid:2)(cid:26) Therefore(cid:6) the information
`
`retrieval task is best de(cid:10)ned by question (cid:7) (cid:8)(cid:6) and the remainder of this thesis will be
`
`devoted to (cid:10)nding a reasonable solution to this type of request(cid:2) In the years since
`
`this de(cid:10)nition was presented(cid:6) however(cid:6) researchers have broadened the (cid:10)eld of IR to
`
`address all of the questions given above and have applied a broad variety of statistical
`
`tools to the process(cid:2) While the work presented here will concentrate on the traditional
`
`IR problem(cid:6) approaches to the other questions will be brie(cid:21)y described below(cid:2)
`
`While question(cid:12)answering systems(cid:6) useful for (cid:7) (cid:8) above(cid:6) do not fall under the clas(cid:12)
`
`sical domain of IR(cid:6) there has been some work on such systems in the (cid:10)eld(cid:2) Kupiec
`
`(cid:23)(cid:24) has developed a system for answering closed(cid:12)class questions by doing a syntactic
`
`Petitioner Google Ex-1038, 0011
`
`

`

`CHAPTER (cid:3) AN INTRODUCTION TO INFORMATION RETRIEVAL
`
`
`
`analysis of the query to identify noun phrases and then using pattern matching com(cid:12)
`
`bined with other IR techniques to (cid:10)nd documents that may contain the answer(cid:2) The
`
`document collection used for this experiment is an on(cid:12)line encyclopedia(cid:2) Some of the
`
`linguistic tools applied in this system(cid:6) such as part(cid:12)of(cid:12)speech tagging(cid:6) boolean search
`
`with proximity constraints(cid:6) and syntactic analysis(cid:6) are often used in more general
`
`information retrieval systems(cid:2)
`
`The task of database retrieval(cid:6) described by question (cid:7)(cid:8) above(cid:6) requires a some(cid:12)
`
`what di(cid:22)erent approach(cid:2) Database queries are assumed to be precise(cid:6) and the task
`
`of (cid:10)nding the relevant documents boils down to looking up the records which share
`
`the attributes de(cid:10)ned in the query(cid:2) Much of the work on database retrieval in IR
`
`is concerned with performance issues(cid:6) since the retrieval task itself is well de(cid:10)ned
`
`and the problem comes in scaling it to the size of full(cid:12)text collections(cid:2) In contrast(cid:6)
`
`classical information retrieval (cid:7) (cid:8) is a much more approximate science(cid:6) since no sense
`
`of exact match exists between documents and queries in the IR setting(cid:2) The value of
`
`a document is measured by its relevance to the query(cid:6) which is often expressed in the
`
`framework of a probabilistic model(cid:2) Most retrieval strategies are designed to provide
`
`approximate solutions and thus are not suitable for the database retrieval task(cid:2) Work
`
`has be done by Fuhr (cid:23)(cid:24) on combining IR with database systems(cid:2)
`
`One approach to the task de(cid:10)ned by question (cid:7)(cid:8) is known as text categorization(cid:2)
`
`Assigning labels to documents from a group of prede(cid:10)ned categories is a useful method
`
`for organizing a large text collection(cid:2) Searchers can use these labels or key words
`
`to quickly focus their attention on the documents that relate to their questions(cid:2)
`
`Traditionally(cid:6) labels have been produced manually(cid:6) representing a huge investment in
`
`time and e(cid:22)ort(cid:2) Hence(cid:6) a system that automatically i