Return-Path: Delivered-To: apmail-lucene-java-commits-archive@www.apache.org Received: (qmail 82965 invoked from network); 15 Sep 2009 17:45:10 -0000 Received: from hermes.apache.org (HELO mail.apache.org) (140.211.11.3) by minotaur.apache.org with SMTP; 15 Sep 2009 17:45:10 -0000 Received: (qmail 85153 invoked by uid 500); 15 Sep 2009 17:45:10 -0000 Delivered-To: apmail-lucene-java-commits-archive@lucene.apache.org Received: (qmail 85100 invoked by uid 500); 15 Sep 2009 17:45:10 -0000 Mailing-List: contact java-commits-help@lucene.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: java-dev@lucene.apache.org Delivered-To: mailing list java-commits@lucene.apache.org Received: (qmail 85091 invoked by uid 99); 15 Sep 2009 17:45:10 -0000 Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 15 Sep 2009 17:45:10 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=10.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 15 Sep 2009 17:44:57 +0000 Received: by eris.apache.org (Postfix, from userid 65534) id 9EAFA23888CB; Tue, 15 Sep 2009 17:44:35 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: svn commit: r815414 - in /lucene/java/trunk: CHANGES.txt src/java/org/apache/lucene/search/Similarity.java Date: Tue, 15 Sep 2009 17:44:35 -0000 To: java-commits@lucene.apache.org From: doronc@apache.org X-Mailer: svnmailer-1.0.8 Message-Id: <20090915174435.9EAFA23888CB@eris.apache.org> X-Virus-Checked: Checked by ClamAV on apache.org Author: doronc Date: Tue Sep 15 17:44:35 2009 New Revision: 815414 URL: http://svn.apache.org/viewvc?rev=815414&view=rev Log: LUCENE-1908: Scoring documentation imrovements in Similarity javadocs. Modified: lucene/java/trunk/CHANGES.txt lucene/java/trunk/src/java/org/apache/lucene/search/Similarity.java Modified: lucene/java/trunk/CHANGES.txt URL: http://svn.apache.org/viewvc/lucene/java/trunk/CHANGES.txt?rev=815414&r1=815413&r2=815414&view=diff ============================================================================== --- lucene/java/trunk/CHANGES.txt (original) +++ lucene/java/trunk/CHANGES.txt Tue Sep 15 17:44:35 2009 @@ -829,6 +829,9 @@ Documentation + * LUCENE-1908: Scoring documentation imrovements in Similarity javadocs. + (Mark Miller, Shai Erera, Ted Dunning, Jiri Kuhn, Marvin Humphrey, Doron Cohen) + * LUCENE-1872: NumericField javadoc improvements (Michael McCandless, Uwe Schindler) Modified: lucene/java/trunk/src/java/org/apache/lucene/search/Similarity.java URL: http://svn.apache.org/viewvc/lucene/java/trunk/src/java/org/apache/lucene/search/Similarity.java?rev=815414&r1=815413&r2=815414&view=diff ============================================================================== --- lucene/java/trunk/src/java/org/apache/lucene/search/Similarity.java (original) +++ lucene/java/trunk/src/java/org/apache/lucene/search/Similarity.java Tue Sep 15 17:44:35 2009 @@ -29,45 +29,266 @@ import java.util.IdentityHashMap; import java.util.Iterator; -/** Expert: Scoring API. - *

Subclasses implement search scoring. +/** + * Expert: Scoring API. * - *

The score of query q for document d correlates to the - * cosine-distance or dot-product between document and query vectors in a + *

Similarity defines the components of Lucene scoring. + * Overriding computation of these components is a convenient + * way to alter Lucene scoring. + * + *

Suggested reading: + * + * Introduction To Information Retrieval, Chapter 6. + * + *

The following describes how Lucene scoring evolves from + * underlying information retrieval models to (efficient) implementation. + * We first brief on VSM Score, + * then derive from it Lucene's Conceptual Scoring Formula, + * from which, finally, evolves Lucene's Practical Scoring Function + * (the latter is connected directly with Lucene classes and methods). + * + *

Lucene combines + * + * Boolean model (BM) of Information Retrieval + * with * - * Vector Space Model (VSM) of Information Retrieval. - * A document whose vector is closer to the query vector in that model is scored higher. + * Vector Space Model (VSM) of Information Retrieval - + * documents "approved" by BM are scored by VSM. * - * The score is computed as follows: + *

In VSM, documents and queries are represented as + * weighted vectors in a multi-dimensional space, + * where each distinct index term is a dimension, + * and weights are + * Tf-idf values. + * + *

VSM does not require weights to be Tf-idf values, + * but Tf-idf values are believed to produce search results of high quality, + * and so Lucene is using Tf-idf. + * Tf and Idf are described in more detail below, + * but for now, for completion, let's just say that + * for given term t and document (or query) x, + * Tf(t,x) varies with the number of occurrences of term t in x + * (when one increases so does the other) and + * idf(t) similarly varies with the inverse of the + * number of index documents containing term t. + * + *

VSM score of document d for query q is the + * + * Cosine Similarity + * of the weighted query vectors V(q) and V(d): + * + *

+ * + * + * + *
+ * + * + *
+ * + * + * + * + * + *
+ * cosine-similarity(q,d) = + * + * + * + * + * + *
V(q) · V(d)
–––––––––
|V(q)| |V(d)|
+ *
+ *
+ *
+ * VSM Score + *
+ *

+ * + * + * Where V(q) · V(d) is the + * dot product + * of the weighted vectors, + * and |V(q)| and |V(d)| are their + * Euclidean norms. + * + *

Note: the above equation can be viewed as the dot product of + * the normalized weighted vectors, in the sense that dividing + * V(q) by its euclidean norm is normalizing it to a unit vector. + * + *

Lucene refines VSM score for both search quality and usability: + *

Normalizing V(d) to the unit vector is known to be problematic in that + * it removes all document length information. + * For some documents removing this info is probably ok, + * e.g. a document made by duplicating a certain paragraph 10 times, + * especially if that paragraph is made of distinct terms. + * But for a document which contains no duplicated paragraphs, + * this might be wrong. + * To avoid this problem, a different document length normalization + * factor is used, which normalizes to a vector equal to or larger + * than the unit vector: doc-len-norm(d). + *
At indexing, users can specify that certain documents are more + * important than others, by assigning a document boost. + * For this, the score of each document is also multiplied by its boost value + * doc-boost(d). + *
Lucene is field based, hence each query term applies to a single + * field, document length normalization is by the length of the certain field, + * and in addition to document boost there are also document fields boosts. + *
The same field can be added to a document during indexing several times, + * and so the boost of that field is the multiplication of the boosts of + * the separate additions (or parts) of that field within the document. + *
At search time users can specify boosts to each query, sub-query, and + * each query term, hence the contribution of a query term to the score of + * a document is multiplied by the boost of that query term query-boost(q). + *
A document may match a multi term query without containing all + * the terms of that query (this is correct for some of the queries), + * and users can further reward documents matching more query terms + * through a coordination factor, which is usually larger when + * more terms are matched: coord-factor(q,d). + *

+ * + *

Under the simplifying assumption of a single field in the index, + * we get Lucene's Conceptual scoring formula: + * + *

+ * + * + * + *
+ * + * + *
+ * + * + * + * + * + * + *
+ * score(q,d) = + * coord-factor(q,d) · + * query-boost(q) · + * + * + * + * + * + *
V(q) · V(d)
–––––––––
|V(q)|
+ * + * · doc-len-norm(d) + * · doc-boost(d) + *
+ *
+ *
+ * Lucene Conceptual Scoring Formula + *
+ *

+ * + *

The conceptual formula is a simplification in the sense that (1) terms and documents + * are fielded and (2) boosts are usually per query term rather than per query. + * + *

We now describe how Lucene implements this conceptual scoring formula, and + * derive from it Lucene's Practical Scoring Function. + * + *

For efficient score computation some scoring components + * are computed and aggregated in advance: + * + *

Query-boost for the query (actually for each query term) + * is known when search starts. + *
Query Euclidean norm |V(q)| can be computed when search starts, + * as it is independent of the document being scored. + * From search optimization perspective, it is a valid question + * why bother to normalize the query at all, because all + * scored documents will be multiplied by the same |V(q)|, + * and hence documents ranks (their order by score) will not + * be affected by this normalization. + * There are two good reasons to keep this normalization: + *
- Recall that + * + * Cosine Similarity can be used find how similar + * two documents are. One can use Lucene for e.g. + * clustering, and use a document as a query to compute + * its similarity to other documents. + * In this use case it is important that the score of document d3 + * for query d1 is comparable to the score of document d3 + * for query d2. In other words, scores of a document for two + * distinct queries should be comparable. + * There are other applications that may require this. + * And this is exactly what normalizing the query vector V(q) + * provides: comparability (to a certain extent) of two or more queries. + *
- Applying query normalization on the scores helps to keep the + * scores around the unit vector, hence preventing loss of score data + * because of floating point precision limitations. + *
+ *
Document length norm doc-len-norm(d) and document + * boost doc-boost(d) are known at indexing time. + * They are computed in advance and their multiplication + * is saved as a single value in the index: norm(d). + * (In the equations below, norm(t in d) means norm(field(t) in doc d) + * where field(t) is the field associated with term t.) + *

+ * + *

Lucene's Practical Scoring Function is derived from the above. + * The color codes demonstrate how it relates + * to those of the conceptual formula: * *

- * + *
+ * * *
+ * + * + *
+ * + * + * + * + * + * + * + * + * + * + * + *
+ * score(q,d) = + * coord(q,d) · + * queryNorm(q) · + * + * ∑ + * + * ( + * tf(t in d) · + * idf(t)² · + * t.getBoost() · + * norm(t,d) + * ) + *
t in q
+ *
+ *
- * - * - * - * - * - * - * - * - * - * - * - *
- * score(q,d) = - * coord(q,d) · - * queryNorm(q) · - * - * ∑ - * - * ( - * tf(t in d) · - * idf(t)² · - * t.getBoost() · - * norm(t,d) - * ) - *
t in q
+ * Lucene Practical Scoring Function *
* @@ -75,10 +296,14 @@ *

* - * tf(t in d) + * tf(t in d) * correlates to the term's frequency, * defined as the number of times term t appears in the currently scored document d. * Documents that have more occurrences of a given term receive a higher score. + * Note that tf(t in q) is assumed to be 1 and therefore it does not appear in this equation, + * However if a query contains twice the same term, there will be + * two term-queries with that same term and hence the computation would still be correct (although + * not very efficient). * The default computation for tf(t in d) in * {@link org.apache.lucene.search.DefaultSimilarity#tf(float) DefaultSimilarity} is: * @@ -98,10 +323,12 @@ * *
* - * idf(t) stands for Inverse Document Frequency. This value + * idf(t) stands for Inverse Document Frequency. This value * correlates to the inverse of docFreq * (the number of documents in which the term t appears). * This means rarer terms give higher contribution to the total score. + * idf(t) appears for t in both the query and the document, + * hence it is squared in the equation. * The default computation for idf(t) in * {@link org.apache.lucene.search.DefaultSimilarity#idf(int, int) DefaultSimilarity} is: * @@ -131,7 +358,7 @@ * *
* - * coord(q,d) + * coord(q,d) * is a score factor based on how many of the query terms are found in the specified document. * Typically, a document that contains more of the query's terms will receive a higher score * than another document with fewer query terms. @@ -143,7 +370,7 @@ * *
* - * queryNorm(q) + * queryNorm(q) * * is a normalizing factor used to make scores between queries comparable. * This factor does not affect document ranking (since all ranked documents are multiplied by the same factor), @@ -152,7 +379,7 @@ * * The default computation in * {@link org.apache.lucene.search.DefaultSimilarity#queryNorm(float) DefaultSimilarity} - * is: + * produces a Euclidean norm: *

* * @@ -209,7 +436,7 @@ * *
* - * t.getBoost() + * t.getBoost() * is a search time boost of term t in the query q as * specified in the query text * (see query syntax), @@ -225,7 +452,7 @@ * *
* - * norm(t,d) encapsulates a few (indexing time) boost and length factors: + * norm(t,d) encapsulates a few (indexing time) boost and length factors: * *
- Document boost - set by calling @@ -277,9 +504,18 @@ * {@link org.apache.lucene.store.Directory directory} and * {@link #decodeNorm(byte) decoded} back to a float norm value. * This encoding/decoding, while reducing index size, comes with the price of - * precision loss - it is not guaranteed that decode(encode(x)) = x. - * For instance, decode(encode(0.89)) = 0.75. - * Also notice that search time is too late to modify this norm part of scoring, e.g. by + * precision loss - it is not guaranteed that decode(encode(x)) = x. + * For instance, decode(encode(0.89)) = 0.75. + *
  
  + * Compression of norm values to a single byte saves memory at search time, + * because once a field is referenced at search time, its norms - for + * all documents - are maintained in memory. + *
  
  + * The rationale supporting such lossy compression of norm values is that + * given the difficulty (and inaccuracy) of users to express their true information + * need by a query, only big differences matter. + *
  
  + * Last, note that search time is too late to modify this norm part of scoring, e.g. by * using a different {@link Similarity} for search. *
  
  *