lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Kelvin Tan <kelvin-li...@relevanz.com>
Subject Re: Normalized Scoring -- was RE: idf and explain(), was Re: Search and Scoring
Date Sat, 05 Feb 2005 23:32:20 GMT
Hi Otis, I was re-reading this whole theoretical thread about idf, scoring, normalization,
etc from last Oct and couldn't help laughing out loud when I read your post, coz it summed
up what I was thinking the whole time. I think its really great to have people like Chuck
and Paul (Eshlot) around. I'm learning so much.

k

On Thu, 21 Oct 2004 10:05:51 -0700 (PDT), Otis Gospodnetic wrote:
> Hi Chuck,
>
> The relative lack of responses is not because there is no interest,
> but probably because there are only a few people on lucene-dev who
> can follow/understand every detail of your proposal.  I understand
> and hear you, but I have a hard time 'visualizing' some of the
> formulas in your proposal.  What you are saying sounds right to me,
> but I don't have enough theoretical knowledge to go one way or the
> other.
>
> Otis
>
>
> --- Chuck Williams <chuck@manawiz.com> wrote:
>
>> Hi everybody,
>>
>> Although there doesn't seem to be much interest in this I have
>> one significant improvement to the below and a couple
>> observations that clarify the situation.
>>
>> To illustrate the problem better normalization is intended to
>> address,
>> in my current application for BooleanQuery's of two terms, I
>> frequently
>> get a top score of 1.0 when only one of the terms is matched.
>> 1.0 should indicate a "perfect match".  I'd like set my UI up to
>> present the
>> results differently depending on how good the different results
>> are (e.g., showing a visual indication of result quality,
>> dropping the really bad results entirely, and segregating the
>> good results from other
>> only vaguely relevant results).  To build this kind of
>> "intelligence" into the UI, I certainly need to know whether my
>> top result matched all
>> query terms, or only half of them.  I'd like to have the score
>> tell me
>> directly how good the matches are.  The current normalization
>> does not achieve this.
>>
>> The intent of a new normalization scheme is to preserve the
>> current scoring in the following sense:  the ratio of the nth
>> result's score to
>> the best result's score remains the same.  Therefore, the only
>> question
>> is what normalization factor to apply to all scores.  This
>> reduces to a
>> very specific question that determines the entire normalization --
>>  what should the score of the best matching result be?
>>
>> The mechanism below has this property, i.e. it keeps the current
>> score
>> ratios, except that I removed one idf term for reasons covered
>> earlier
>> (this better reflects the current empirically best scoring
>> algorithms).
>> However, removing an idf is a completely separate issue.  The
>> improved
>> normalization is independent of whether or not that change is
>> made.
>>
>> For the central question of what the top score should be, upon
>> reflection, I don't like the definition below.  It defined the
>> top score
>> as (approximately) the percentage of query terms matched by the
>> top scoring result.  A better conceptual definition is to use a
>> weighted average based on the boosts.  I.e., downward propagate
>> all boosts to the
>> underlying terms (or phrases).  Secifically, the "net boost" of a
>> term
>> is the product of the direct boost of the term and all boosts
>> applied to
>> encompassing clauses.  Then the score of the top result becomes
>> the sum
>> of the net boosts of its matching terms divided by the sum of the
>> net boosts of all query terms.
>>
>> This definition is a refinement of the original proposal below,
>> and it
>> could probably be further refined if some impact of the tf, idf
>> and/or
>> lengthNorm was desired in determining the top score.  These other
>> factors seems to be harder to normalize for, although I've
>> thought of some simple approaches; e.g., assume the unmatched
>> terms in the top result have values for these three factors that
>> are the average of the
>> values of the matched terms, then apply exactly the same concept
>> of actual score divided by theorectical maximum score.  That
>> would eliminate any need to maintain maximum value statistics in
>> the index.
>>
>> As an example of the simple boost-based normalization, for the
>> query ((a^2 b)^3 (c d^2)) the net boosts are: a --> 6 b --> 3 c --
>> > 1 d --> 2
>>
>> So if a and b matched, but not c and d, in the top scoring
>> result, its
>> score would be 0.75.  The normalizer would be 0.75/(current score
>> except
>> for the current normalization).  This normalizer would be applied
>> to all
>> current scores (minus normalization) to create the normalized
>> scores.
>>
>> For simple query (a b), if only one of the terms matched in the
>> top result, then its score would be 0.5, vs. 1.0 or many other
>> possible scores today.
>>
>> In addition to enabling more "intelligent" UI's that communicate
>> the quality of results to end-users, the proposal below also
>> extends the explain() mechanism to fully explain the final
>> normalized score. However, that change is also independent -- it
>> could be done with the current scoring.
>>
>> Am I the only one who would like to see better normalization in
>> Lucene? Does anybody have a better approach?
>>
>> If you've read this far, thanks for indulging me on this.  I
>> would love
>> to see this or something with similar properties in Lucene.  I
>> really just want to build my app, but as stated below would write
>> and contribute this if there is interest in putting it in, and
>> nobody else
>> wants to write it.  Please let me know what you think one way or
>> the other.
>>
>> Thanks,
>>
>> Chuck
>>
>>
>>> -----Original Message-----
>>> From: Chuck Williams
>>> Sent: Monday, October 18, 2004 7:04 PM
>>> To: 'Lucene Developers List'
>>> Subject: RE: idf and explain(), was Re: Search and Scoring
>>>
>>> Doug Cutting wrote:
>>>> If this is a big issue for you, as it seems it is, please
>>>>
>> submit
>> a
>>> patch
>>>> to optionally disable score normalization in Hits.java.
>>>>
>>> and:
>>>> The quantity 'sum(t) weight(t,d)^2' must be recomputed for
>>>>
>> each
>>> document
>>>> each time a document is added to the collection, since
>>>>
>> 'weight(t,d)'
>>> is
>>>> dependent on global term statistics.  This is prohibitivly
>>>>
>> expensive.
>>>> Research has also demonstrated that such cosine normalization
>>>>
>> gives
>>>> somewhat inferior results (e.g., Singhal's pivoted length
>>>>
>>> normalization).
>>>
>>> I'm willing to write, test and contribute code to address the
>>> normalization issue, i.e. to yield scores in [0, 1] that are
>>>
>> meaningful
>>> across searches.  Unfortunately, this is considerably more
>>>
>> involved
>> that
>>> just optionally eliminating the current normalization in Hits.
>>>
>> Before
>>> undertaking this, I'd like to see if there is agreement in
>>>
>> principle
>>> that this is a good idea, and that my specific proposal below is
>>>
>> the
>>> right way to go.  Also, I'd like to make sure I've correctly
>>>
>> inferred
>>> the constraints on writing code to be incorporated into Lucene.
>>>
>>> After looking at this in more detail I agree that the cosine
>>> normalization is not the way to go, because of both efficiency
>>>
>> and
>>> effectiveness considerations.  A conceptual approach that would
>>>
>> be
>>> efficient, relatively easy to implement, and seems to have at
>>>
>> least
>>> reasonable behavior would be to define the top scoring match to
>>>
>> have
>> a
>>> score roughly equal to the percentage of query terms it matches
>>>
>> (its
>>> "netCoord").  Scores below the top hit would be reduced based on
>>>
>> the
>>> ratio of their raw scores to the raw score of the top hit
>>>
>> (considering
>>> all of the current score factors, except that I'd like to remove
>>>
>> one
>> of
>>> the idf factors, as discussed earlier).
>>>
>>> For a couple simple cases:
>>> a) the top match for a single term query would always have a
>>>
>> score
>> of
>>> 1.0,
>>> b) the top scoring match for a BooleanQuery using
>>>
>> DefaultSimilarity
>>> with all non-prohibited TermQuery clauses would have a score of
>>>
>> m/n,
>>> where the hit matches m of the n terms.
>>>
>>> This isn't optimal, but seems much better than the current
>>>
>> situation.
>>> Consider two single-term queries, s and t.  If s matches more
>>>
>> strongly
>>> than t in its top hit (e.g., a higher tf in a shorter field), it
>>>
>> would
>>> be best if the top score of s was greater score than top score
>>> of
>>>
>> t.
>>> But this kind of normalization would require keeping additional
>>> statistics that so far as I know are not currently in the index,
>>>
>> like
>>> the maximum tf for terms and the minimum length for fields.
>>>
>> These
>> could
>>> be expensive to update on deletes.  Also, normalizing by such
>>>
>> factors
>>> could yield lower than subjectively reasonable scores in most
>>>
>> cases,
>> so
>>> it's not clear it would be better.
>>>
>>> The semantics above are at least clean, easy to understand, and
>>>
>> support
>>> what seems to me is the most important motivation to do this:
>>>
>> allowing
>>> an application to use simple thresholding to segregate
>>>
>> likely-to-be-
>>> relevant hits from likely-to-be-irrelevant hits.
>>>
>>> More specifically, for a BooleanQuery of TermQuery's the
>>>
>> resulting
>> score
>>> functions would be:
>>>
>>> BooleanQuery of TermQuery's sbq = (tq1 ... tqn)
>>>
>>> baseScore(sbq, doc) =
>>> sum(tqi) boost(tqi)*idf(tqi.term)*tf(tqi.term, doc)*
>>> lengthNorm(tqi.term.field, doc)
>>>
>>> rawScore(sbq, doc) = coord(sbq, doc) * baseScore
>>>
>>> norm(sbq, hits) = 1 / max(hit in hits) baseScore(sbq, hit)
>>>
>>> score(sbq, doc) = rawScore * norm
>>>
>>> rawScore's can be computed in the Scorer.score() methods and
>>>
>> therefore
>>> used to sort the hits (e.g., in the instance method for
>>> collect()
>>>
>> in
>> the
>>> HitCollector in IndexSearcher.search()).  If the top scoring hit
>>>
>> does
>>> not have the highest baseScore, then its score could be less
>>> that
>>>
>> its
>>> coord; this seems desirable.  These formulas imply that no
>>> result
>>>
>> score
>>> can be larger than its coord, so if coord is well-defined
>>> (always between 0 and 1) then all results will be normalized
>>> between 0
>>>
>> and
>> 1.
>>
>>> In general, the netCoord, which takes the place of coord in the
>>>
>> simple
>>> case above, needs to be defined for any query.  Conceptually,
>>>
>> this
>>> should be the total percentage of query terms matched by the
>>>
>> document.
>>> It must be recursively computable from the subquery structure
>>> and overridable for specific Query types (e.g., to support
>>>
>> specialized
>>> coords, like one that is always 1.0 as is useful in multi-field
>>> searching).  Suitable default definitions for TermQuery and
>>>
>> BooleanQuery
>>> are:
>>>
>>> TermQuery.netCoord = 1.0 if term matches, 0.0 otherwise
>>>
>>> BooleanQuery(c1 ... cn).netCoord = sum(ci) coord(1, n) *
>>>
>> ci.netCoord
>>
>>> This is not quite percentage of terms matched; e.g., consider a
>>> BooleanQuery with two clauses, one of which is a BooleanQuery of
>>>
>> 3
>> terms
>>> and the other which is just a term.  However, it doesn't seem to
>>>
>> be
>>> unreasonable for a BooleanQuery to state that its clauses are
>>>
>> equally
>>> important, and this is consistent with the current coord
>>>
>> behavior.
>>> BooleanQuery.netCoord could be overridden for special cases,
>>> like
>>>
>> the
>>> pure disjunction I use in my app for field expansions:
>>> MaxDisjunctionQuery(c1 .. cn).netCoord = max(ci) ci.netCoord
>>>
>>> Implementing this would proceed along these lines: 1.  For
>>> backwards compatibility, add some kind of newScoring
>>>
>> boolean
>>> setting.
>>> 2.  Update all of these places to behave as indicated if
>>>
>> newScoring:
>>> a.  Change Query.weight() to not do any normalization (no
>>>
>> call
>> to
>>> sumOfSquaredWeights(), Similarity.queryNorm() or normalize()).
>>> b.  Update all Query.weight classes to set their value
>>>
>> according
>> to
>>> the terms in the score formula above that don't involve the
>>>
>> document
>>> (e.g., boost*idf for TermQuery).
>>> c.  Add suitable netCoord definitions to all Scorer classes. d.
>>>  Update all Scorer.score() methods to compute the rawScore
>>>
>> as
>>> above.
>>> e.  Add the maximum baseScore as a field kept on TopDocs,
>>>
>> computed
>>> in the HitCollector's.
>>> f.  Change the normalization in Hits to always divide every
>>>
>> raw
>>> score by the maximum baseScore.
>>> g.  Update all of the current explain() methods to be
>>>
>> consistent
>>> with this scoring, and to either report the rawScore, or to
>>>
>> report
>> the
>>> final score if the normalization factor is provided. h.  Add
>>> Hits.explain() (or better extend Searcher so that it
>>>
>> keeps
>>> the Hits for use in Searcher.explain()) to call the new explain
>>> variation with the normalization factor so that final scores are
>>>
>> fully
>>> explained.
>>>
>>> If this seems like a good idea, please let me know.  I'm sure
>>>
>> there
>> are
>>> details I've missed that would come out during coding and
>>>
>> testing.
>> Also,
>>> the value of this is dependent on how reasonable the final
>>> scores
>>>
>> look,
>>> which is hard to tell for sure until it is working.
>>>
>>> The coding standards for Lucene seem reasonably clear from the
>>>
>> source
>>> code I've read.  I could use just simple Java so there shouldn't
>>>
>> be
>> any
>>> significant JVM dependencies.  The above should be fully
>>> backward compatible due to the newScoring flag.
>>>
>>> On another note, I had to remove the German analyzer in my
>>>
>> current
>> 1.4.2
>>> source configuration because GermanStemmer failed to compile due
>>>
>> to
>> what
>>> are apparently Unicode character constants that I've now got as
>>>
>> illegal
>>> two-character character constants.  This is presumably an
>>>
>> encoding
>>> problem somewhere that I could track down.  It's not important,
>>>
>> but
>> if
>>> the answer is obvious to any of you, I'd appreciate the quick
>>>
>> tip.
>>
>>> Thanks,
>>>
>>> Chuck
>>>
>>>> -----Original Message-----
>>>> From: Doug Cutting [mailto:cutting@apache.org] Sent: Monday,
>>>> October 18, 2004 9:44 AM To: Lucene Developers List
>>>> Subject: Re: idf and explain(), was Re: Search and Scoring
>>>>
>>>> Chuck Williams wrote:
>>>>> That's a good point on how the standard vector space inner
>>>>>
>> product
>>>>> similarity measure does imply that the idf is squared
>>>>>
>> relative
>> to
>>> the
>>>>> document tf.  Even having been aware of this formula for a
>>>>>
>> long
>>> time,
>>>>> this particular implication never occurred to me.  Do you
>>>>>
>> know
>> if
>>>>> anybody has done precision/recall or other relevancy
>>>>>
>> empirical
>>>>> measurements comparing this vs. a model that does not
>>>>>
>> square
>> idf?
>>
>>>> No, not that I know of.
>>>>
>>>>> Regarding normalization, the normalization in Hits does not
>>>>>
>> have
>>> very
>>>>> nice properties.  Due to the > 1.0 threshold check, it
>>>>>
>> loses
>>>>> information, and it arbitrarily defines the highest scoring
>>>>>
>> result
>>> in
>>>>> any list that generates scores above 1.0 as a perfect
>>>>>
>> match.
>> It
>>> would
>>>>> be nice if score values were meaningful independent of
>>>>>
>> searches,
>>> e.g.,
>>>>> if "0.6" meant the same quality of retrieval independent of
>>>>>
>> what
>>>> search
>>>>> was done.  This would allow, for example, sites to use a a
>>>>>
>> simple
>>>>> quality threshold to only show results that were "good
>>>>>
>> enough".
>>> At my
>>>>> last company (I was President and head of engineering for
>>>>>
>> InQuira),
>>> we
>>>>> found this to be important to many customers.
>>>>>
>>>> If this is a big issue for you, as it seems it is, please
>>>>
>> submit
>> a
>>> patch
>>>> to optionally disable score normalization in Hits.java.
>>>>
>>>>> The standard vector space similarity measure includes
>>>>>
>>> normalization by
>>>>> the product of the norms of the vectors, i.e.:
>>>>>
>>>>> score(d,q) =  sum over t of ( weight(t,q) * weight(t,d) )
>>>>>
>> /
>>>>> sqrt [ (sum(t) weight(t,q)^2) * (sum(t)
>>>>>
>>>> weight(t,d)^2) ]
>>>>
>>>>> This makes the score a cosine, which since the values are
>>>>>
>> all
>>> positive,
>>>>> forces it to be in [0, 1].  The sumOfSquares()
>>>>>
>> normalization
>> in
>>> Lucene
>>>>> does not fully implement this.  Is there a specific reason
>>>>>
>> for
>>> that?
>>>
>>>> The quantity 'sum(t) weight(t,d)^2' must be recomputed for
>>>>
>> each
>>> document
>>>> each time a document is added to the collection, since
>>>>
>> 'weight(t,d)'
>>> is
>>>> dependent on global term statistics.  This is prohibitivly
>>>>
>> expensive.
>>>> Research has also demonstrated that such cosine normalization
>>>>
>> gives
>>>> somewhat inferior results (e.g., Singhal's pivoted length
>>>>
>>> normalization).
>>>
>>>>> Re. explain(), I don't see a downside to extending it show
>>>>>
>> the
>>> final
>>>>> normalization in Hits.  It could still show the raw score
>>>>>
>> just
>>> prior
>>>> to
>>>>> that normalization.
>>>>>
>>>> In order to normalize scores to 1.0 one must know the maximum
>>>>
>> score.
>>>> Explain only computes the score for a single document, and
>>>>
>> the
>>> maximum
>>>> score is not known.
>>>>
>>>>> Although I think it would be best to have a normalization
>>>>> that would render scores comparable across
>>>>>
>> searches.
>>
>>>> Then please submit a patch.  Lucene doesn't change on its
>>>>
>> own.
>>
>>>> Doug
>>>>
>>>>
>> ------------------------------------------------------------------
>> --
>>
>>> -
>>>> To unsubscribe, e-mail:
>> lucene-dev-unsubscribe@jakarta.apache.org
>>>> For additional commands, e-mail:
>> lucene-dev-help@jakarta.apache.org
>>
>>
>> ------------------------------------------------------------------
>> --- To unsubscribe, e-mail: lucene-dev-
>> unsubscribe@jakarta.apache.org For additional commands, e-mail:
>> lucene-dev-help@jakarta.apache.org
>
>
> --------------------------------------------------------------------
> - To unsubscribe, e-mail: lucene-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: lucene-dev-help@jakarta.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: lucene-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: lucene-dev-help@jakarta.apache.org


Mime
View raw message