lucene-java-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From dor...@apache.org
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 GMT
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>&nbsp;<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) &nbsp; = &nbsp;
+ *          </td>
+ *          <td valign="middle" align="center">
+ *            <table>
+ *               <tr><td align="center"><small>V(q)&nbsp;&middot;&nbsp;V(d)</small></td></tr>
+ *               <tr><td align="center">&ndash;&ndash;&ndash;&ndash;&ndash;&ndash;&ndash;&ndash;&ndash;</td></tr>
+ *               <tr><td align="center"><small>|V(q)|&nbsp;|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>&nbsp;<br>
+ *   
+ *
+ * Where <i>V(q)</i> &middot; <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>&nbsp;<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) &nbsp; = &nbsp;
+ *            <font color="#FF9933">coord-factor(q,d)</font> &middot; &nbsp;
+ *            <font color="#CCCC00">query-boost(q)</font> &middot; &nbsp;
+ *          </td>
+ *          <td valign="middle" align="center">
+ *            <table>
+ *               <tr><td align="center"><small><font color="#993399">V(q)&nbsp;&middot;&nbsp;V(d)</font></small></td></tr>
+ *               <tr><td align="center">&ndash;&ndash;&ndash;&ndash;&ndash;&ndash;&ndash;&ndash;&ndash;</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">
+ *            &nbsp; &middot; &nbsp; <font color="#3399FF">doc-len-norm(d)</font>
+ *            &nbsp; &middot; &nbsp; <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>&nbsp;<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) &nbsp; = &nbsp;
+ *       <A HREF="#formula_coord"><font color="#FF9933">coord(q,d)</font></A>
&nbsp;&middot;&nbsp;
+ *       <A HREF="#formula_queryNorm"><font color="#FF33CC">queryNorm(q)</font></A>
&nbsp;&middot;&nbsp;
+ *     </td>
+ *     <td valign="bottom" align="center" rowspan="1">
+ *       <big><big><big>&sum;</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>
&nbsp;&middot;&nbsp;
+ *       <A HREF="#formula_idf"><font color="#993399">idf(t)</font></A><sup>2</sup>
&nbsp;&middot;&nbsp;
+ *       <A HREF="#formula_termBoost"><font color="#CCCC00">t.getBoost()</font></A>&nbsp;&middot;&nbsp;
+ *       <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) &nbsp; = &nbsp;
- *      <A HREF="#formula_coord">coord(q,d)</A> &nbsp;&middot;&nbsp;
- *      <A HREF="#formula_queryNorm">queryNorm(q)</A> &nbsp;&middot;&nbsp;
- *    </td>
- *    <td valign="bottom" align="center" rowspan="1">
- *      <big><big><big>&sum;</big></big></big>
- *    </td>
- *    <td valign="middle" align="right" rowspan="1">
- *      <big><big>(</big></big>
- *      <A HREF="#formula_tf">tf(t in d)</A> &nbsp;&middot;&nbsp;
- *      <A HREF="#formula_idf">idf(t)</A><sup>2</sup> &nbsp;&middot;&nbsp;
- *      <A HREF="#formula_termBoost">t.getBoost()</A>&nbsp;&middot;&nbsp;
- *      <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>&nbsp;<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>&nbsp;<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>&nbsp;<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>&nbsp;<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>&nbsp;<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 



Mime
View raw message