You are viewing a plain text version of this content. The canonical link for it is here.
Posted to java-commits@lucene.apache.org by do...@apache.org on 2009/09/15 19:44:35 UTC
svn commit: r815414 - in /lucene/java/trunk: CHANGES.txt
src/java/org/apache/lucene/search/Similarity.java
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.
- * <p>Subclasses implement search scoring.
+/**
+ * Expert: Scoring API.
*
- * <p>The score of query <code>q</code> for document <code>d</code> correlates to the
- * cosine-distance or dot-product between document and query vectors in a
+ * <p>Similarity defines the components of Lucene scoring.
+ * Overriding computation of these components is a convenient
+ * way to alter Lucene scoring.
+ *
+ * <p>Suggested reading:
+ * <a href="http://nlp.stanford.edu/IR-book/html/htmledition/queries-as-vectors-1.html">
+ * Introduction To Information Retrieval, Chapter 6</a>.
+ *
+ * <p>The following describes how Lucene scoring evolves from
+ * underlying information retrieval models to (efficient) implementation.
+ * We first brief on <i>VSM Score</i>,
+ * then derive from it <i>Lucene's Conceptual Scoring Formula</i>,
+ * from which, finally, evolves <i>Lucene's Practical Scoring Function</i>
+ * (the latter is connected directly with Lucene classes and methods).
+ *
+ * <p>Lucene combines
+ * <a href="http://en.wikipedia.org/wiki/Standard_Boolean_model">
+ * Boolean model (BM) of Information Retrieval</a>
+ * with
* <a href="http://en.wikipedia.org/wiki/Vector_Space_Model">
- * Vector Space Model (VSM) of Information Retrieval</a>.
- * A document whose vector is closer to the query vector in that model is scored higher.
+ * Vector Space Model (VSM) of Information Retrieval</a> -
+ * documents "approved" by BM are scored by VSM.
*
- * The score is computed as follows:
+ * <p>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
+ * <a href="http://en.wikipedia.org/wiki/Tfidf">Tf-idf</a> values.
+ *
+ * <p>VSM does not require weights to be <i>Tf-idf</i> values,
+ * but <i>Tf-idf</i> values are believed to produce search results of high quality,
+ * and so Lucene is using <i>Tf-idf</i>.
+ * <i>Tf</i> and <i>Idf</i> are described in more detail below,
+ * but for now, for completion, let's just say that
+ * for given term <i>t</i> and document (or query) <i>x</i>,
+ * <i>Tf(t,x)</i> varies with the number of occurrences of term <i>t</i> in <i>x</i>
+ * (when one increases so does the other) and
+ * <i>idf(t)</i> similarly varies with the inverse of the
+ * number of index documents containing term <i>t</i>.
+ *
+ * <p><i>VSM score</i> of document <i>d</i> for query <i>q</i> is the
+ * <a href="http://en.wikipedia.org/wiki/Cosine_similarity">
+ * Cosine Similarity</a>
+ * of the weighted query vectors <i>V(q)</i> and <i>V(d)</i>:
+ *
+ * <br> <br>
+ * <table cellpadding="2" cellspacing="2" border="0" align="center">
+ * <tr><td>
+ * <table cellpadding="1" cellspacing="0" border="1" align="center">
+ * <tr><td>
+ * <table cellpadding="2" cellspacing="2" border="0" align="center">
+ * <tr>
+ * <td valign="middle" align="right" rowspan="1">
+ * cosine-similarity(q,d) =
+ * </td>
+ * <td valign="middle" align="center">
+ * <table>
+ * <tr><td align="center"><small>V(q) · V(d)</small></td></tr>
+ * <tr><td align="center">–––––––––</td></tr>
+ * <tr><td align="center"><small>|V(q)| |V(d)|</small></td></tr>
+ * </table>
+ * </td>
+ * </tr>
+ * </table>
+ * </td></tr>
+ * </table>
+ * </td></tr>
+ * <tr><td>
+ * <center><font=-1><u>VSM Score</u></font></center>
+ * </td></tr>
+ * </table>
+ * <br> <br>
+ *
+ *
+ * Where <i>V(q)</i> · <i>V(d)</i> is the
+ * <a href="http://en.wikipedia.org/wiki/Dot_product">dot product</a>
+ * of the weighted vectors,
+ * and <i>|V(q)|</i> and <i>|V(d)|</i> are their
+ * <a href="http://en.wikipedia.org/wiki/Euclidean_norm#Euclidean_norm">Euclidean norms</a>.
+ *
+ * <p>Note: the above equation can be viewed as the dot product of
+ * the normalized weighted vectors, in the sense that dividing
+ * <i>V(q)</i> by its euclidean norm is normalizing it to a unit vector.
+ *
+ * <p>Lucene refines <i>VSM score</i> for both search quality and usability:
+ * <ul>
+ * <li>Normalizing <i>V(d)</i> 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 <i>10</i> 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: <i>doc-len-norm(d)</i>.
+ * </li>
+ *
+ * <li>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
+ * <i>doc-boost(d)</i>.
+ * </li>
+ *
+ * <li>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.
+ * </li>
+ *
+ * <li>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.
+ * </li>
+ *
+ * <li>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 <i>query-boost(q)</i>.
+ * </li>
+ *
+ * <li>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: <i>coord-factor(q,d)</i>.
+ * </li>
+ * </ul>
+ *
+ * <p>Under the simplifying assumption of a single field in the index,
+ * we get <i>Lucene's Conceptual scoring formula</i>:
+ *
+ * <br> <br>
+ * <table cellpadding="2" cellspacing="2" border="0" align="center">
+ * <tr><td>
+ * <table cellpadding="1" cellspacing="0" border="1" align="center">
+ * <tr><td>
+ * <table cellpadding="2" cellspacing="2" border="0" align="center">
+ * <tr>
+ * <td valign="middle" align="right" rowspan="1">
+ * score(q,d) =
+ * <font color="#FF9933">coord-factor(q,d)</font> ·
+ * <font color="#CCCC00">query-boost(q)</font> ·
+ * </td>
+ * <td valign="middle" align="center">
+ * <table>
+ * <tr><td align="center"><small><font color="#993399">V(q) · V(d)</font></small></td></tr>
+ * <tr><td align="center">–––––––––</td></tr>
+ * <tr><td align="center"><small><font color="#FF33CC">|V(q)|</font></small></td></tr>
+ * </table>
+ * </td>
+ * <td valign="middle" align="right" rowspan="1">
+ * · <font color="#3399FF">doc-len-norm(d)</font>
+ * · <font color="#3399FF">doc-boost(d)</font>
+ * </td>
+ * </tr>
+ * </table>
+ * </td></tr>
+ * </table>
+ * </td></tr>
+ * <tr><td>
+ * <center><font=-1><u>Lucene Conceptual Scoring Formula</u></font></center>
+ * </td></tr>
+ * </table>
+ * <br> <br>
+ *
+ * <p>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.
+ *
+ * <p>We now describe how Lucene implements this conceptual scoring formula, and
+ * derive from it <i>Lucene's Practical Scoring Function</i>.
+ *
+ * <p>For efficient score computation some scoring components
+ * are computed and aggregated in advance:
+ *
+ * <ul>
+ * <li><i>Query-boost</i> for the query (actually for each query term)
+ * is known when search starts.
+ * </li>
+ *
+ * <li>Query Euclidean norm <i>|V(q)|</i> 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 <i>|V(q)|</i>,
+ * and hence documents ranks (their order by score) will not
+ * be affected by this normalization.
+ * There are two good reasons to keep this normalization:
+ * <ul>
+ * <li>Recall that
+ * <a href="http://en.wikipedia.org/wiki/Cosine_similarity">
+ * Cosine Similarity</a> 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 <i>d3</i>
+ * for query <i>d1</i> is comparable to the score of document <i>d3</i>
+ * for query <i>d2</i>. 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 <i>V(q)</i>
+ * provides: comparability (to a certain extent) of two or more queries.
+ * </li>
+ *
+ * <li>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.
+ * </li>
+ * </ul>
+ * </li>
+ *
+ * <li>Document length norm <i>doc-len-norm(d)</i> and document
+ * boost <i>doc-boost(d)</i> are known at indexing time.
+ * They are computed in advance and their multiplication
+ * is saved as a single value in the index: <i>norm(d)</i>.
+ * (In the equations below, <i>norm(t in d)</i> means <i>norm(field(t) in doc d)</i>
+ * where <i>field(t)</i> is the field associated with term <i>t</i>.)
+ * </li>
+ * </ul>
+ *
+ * <p><i>Lucene's Practical Scoring Function</i> is derived from the above.
+ * The color codes demonstrate how it relates
+ * to those of the <i>conceptual</i> formula:
*
* <P>
- * <table cellpadding="1" cellspacing="0" border="1" align="center">
+ * <table cellpadding="2" cellspacing="2" border="0" align="center">
+ * <tr><td>
+ * <table cellpadding="" cellspacing="2" border="2" align="center">
+ * <tr><td>
+ * <table cellpadding="2" cellspacing="2" border="0" align="center">
+ * <tr>
+ * <td valign="middle" align="right" rowspan="1">
+ * score(q,d) =
+ * <A HREF="#formula_coord"><font color="#FF9933">coord(q,d)</font></A> ·
+ * <A HREF="#formula_queryNorm"><font color="#FF33CC">queryNorm(q)</font></A> ·
+ * </td>
+ * <td valign="bottom" align="center" rowspan="1">
+ * <big><big><big>∑</big></big></big>
+ * </td>
+ * <td valign="middle" align="right" rowspan="1">
+ * <big><big>(</big></big>
+ * <A HREF="#formula_tf"><font color="#993399">tf(t in d)</font></A> ·
+ * <A HREF="#formula_idf"><font color="#993399">idf(t)</font></A><sup>2</sup> ·
+ * <A HREF="#formula_termBoost"><font color="#CCCC00">t.getBoost()</font></A> ·
+ * <A HREF="#formula_norm"><font color="#3399FF">norm(t,d)</font></A>
+ * <big><big>)</big></big>
+ * </td>
+ * </tr>
+ * <tr valigh="top">
+ * <td></td>
+ * <td align="center"><small>t in q</small></td>
+ * <td></td>
+ * </tr>
+ * </table>
+ * </td></tr>
+ * </table>
+ * </td></tr>
* <tr><td>
- * <table cellpadding="1" cellspacing="0" border="0" align="center">
- * <tr>
- * <td valign="middle" align="right" rowspan="1">
- * score(q,d) =
- * <A HREF="#formula_coord">coord(q,d)</A> ·
- * <A HREF="#formula_queryNorm">queryNorm(q)</A> ·
- * </td>
- * <td valign="bottom" align="center" rowspan="1">
- * <big><big><big>∑</big></big></big>
- * </td>
- * <td valign="middle" align="right" rowspan="1">
- * <big><big>(</big></big>
- * <A HREF="#formula_tf">tf(t in d)</A> ·
- * <A HREF="#formula_idf">idf(t)</A><sup>2</sup> ·
- * <A HREF="#formula_termBoost">t.getBoost()</A> ·
- * <A HREF="#formula_norm">norm(t,d)</A>
- * <big><big>)</big></big>
- * </td>
- * </tr>
- * <tr valigh="top">
- * <td></td>
- * <td align="center"><small>t in q</small></td>
- * <td></td>
- * </tr>
- * </table>
+ * <center><font=-1><u>Lucene Practical Scoring Function</u></font></center>
* </td></tr>
* </table>
*
@@ -75,10 +296,14 @@
* <ol>
* <li>
* <A NAME="formula_tf"></A>
- * <b>tf(t in d)</b>
+ * <b><i>tf(t in d)</i></b>
* correlates to the term's <i>frequency</i>,
* defined as the number of times term <i>t</i> appears in the currently scored document <i>d</i>.
* Documents that have more occurrences of a given term receive a higher score.
+ * Note that <i>tf(t in q)</i> is assumed to be <i>1</i> 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 <i>tf(t in d)</i> in
* {@link org.apache.lucene.search.DefaultSimilarity#tf(float) DefaultSimilarity} is:
*
@@ -98,10 +323,12 @@
*
* <li>
* <A NAME="formula_idf"></A>
- * <b>idf(t)</b> stands for Inverse Document Frequency. This value
+ * <b><i>idf(t)</i></b> stands for Inverse Document Frequency. This value
* correlates to the inverse of <i>docFreq</i>
* (the number of documents in which the term <i>t</i> appears).
* This means rarer terms give higher contribution to the total score.
+ * <i>idf(t)</i> appears for <i>t</i> in both the query and the document,
+ * hence it is squared in the equation.
* The default computation for <i>idf(t)</i> in
* {@link org.apache.lucene.search.DefaultSimilarity#idf(int, int) DefaultSimilarity} is:
*
@@ -131,7 +358,7 @@
*
* <li>
* <A NAME="formula_coord"></A>
- * <b>coord(q,d)</b>
+ * <b><i>coord(q,d)</i></b>
* 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 @@
*
* <li><b>
* <A NAME="formula_queryNorm"></A>
- * queryNorm(q)
+ * <i>queryNorm(q)</i>
* </b>
* 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 <a href="http://en.wikipedia.org/wiki/Euclidean_norm#Euclidean_norm">Euclidean norm</a>:
* <br> <br>
* <table cellpadding="1" cellspacing="0" border="0" align="center">
* <tr>
@@ -209,7 +436,7 @@
*
* <li>
* <A NAME="formula_termBoost"></A>
- * <b>t.getBoost()</b>
+ * <b><i>t.getBoost()</i></b>
* is a search time boost of term <i>t</i> in the query <i>q</i> as
* specified in the query text
* (see <A HREF="../../../../../../queryparsersyntax.html#Boosting a Term">query syntax</A>),
@@ -225,7 +452,7 @@
*
* <li>
* <A NAME="formula_norm"></A>
- * <b>norm(t,d)</b> encapsulates a few (indexing time) boost and length factors:
+ * <b><i>norm(t,d)</i></b> encapsulates a few (indexing time) boost and length factors:
*
* <ul>
* <li><b>Document boost</b> - set by calling
@@ -277,9 +504,18 @@
* {@link org.apache.lucene.store.Directory directory} and
* {@link #decodeNorm(byte) decoded} back to a float <i>norm</i> 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 <i>norm</i> part of scoring, e.g. by
+ * precision loss - it is not guaranteed that <i>decode(encode(x)) = x</i>.
+ * For instance, <i>decode(encode(0.89)) = 0.75</i>.
+ * <br> <br>
+ * 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.
+ * <br> <br>
+ * 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.
+ * <br> <br>
+ * Last, note that search time is too late to modify this <i>norm</i> part of scoring, e.g. by
* using a different {@link Similarity} for search.
* <br> <br>
* </li>
@@ -475,9 +711,10 @@
* </pre>
*
* Note that {@link Searcher#maxDoc()} is used instead of
- * {@link org.apache.lucene.index.IndexReader#numDocs()} because it is proportional to
- * {@link Searcher#docFreq(Term)} , i.e., when one is inaccurate,
- * so is the other, and in the same direction.
+ * {@link org.apache.lucene.index.IndexReader#numDocs() IndexReader#numDocs()} because also
+ * {@link Searcher#docFreq(Term)} is used, and when the latter
+ * is inaccurate, so is {@link Searcher#maxDoc()}, and in the same direction.
+ * In addition, {@link Searcher#maxDoc()} is more efficient to compute
*
* @param term the term in question
* @param searcher the document collection being searched
@@ -500,10 +737,11 @@
* </pre>
*
* Note that {@link Searcher#maxDoc()} is used instead of
- * {@link org.apache.lucene.index.IndexReader#numDocs()} because it is
- * proportional to {@link Searcher#docFreq(Term)} , i.e., when one is
- * inaccurate, so is the other, and in the same direction.
- *
+ * {@link org.apache.lucene.index.IndexReader#numDocs() IndexReader#numDocs()} because also
+ * {@link Searcher#docFreq(Term)} is used, and when the latter
+ * is inaccurate, so is {@link Searcher#maxDoc()}, and in the same direction.
+ * In addition, {@link Searcher#maxDoc()} is more efficient to compute
+ *
* @param term the term in question
* @param searcher the document collection being searched
* @return an IDFExplain object that includes both an idf score factor