Remove k1+1 from the numerator of BM25Similarity [LUCENE-8563]

[asfimport]

Our current implementation of BM25 does

boost * IDF * (k1+1) * tf / (tf + norm)

As (k1+1) is a constant, it is the same for every term and doesn't modify ordering. It is often omitted and I found out that the "The Probabilistic Relevance Framework: BM25 and Beyond" paper by Robertson (BM25's author) and Zaragova even describes adding (k1+1) to the numerator as a variant whose benefit is to be more comparable with Robertson/Sparck-Jones weighting, which we don't care about.

A common variant is to add a (k1 + 1) component to the
numerator of the saturation function. This is the same for all
terms, and therefore does not affect the ranking produced.
The reason for including it was to make the final formula
more compatible with the RSJ weight used on its own

Should we remove it from BM25Similarity as well?

A side-effect that I'm interested in is that integrating other score contributions (eg. via oal.document.FeatureField) would be a bit easier to reason about. For instance a weight of 3 in FeatureField#newSaturationQuery would have a similar impact as a term whose IDF is 3 (and thus docFreq ~= 5%) rather than a term whose IDF is 3/(k1 + 1).

---

Migrated from LUCENE-8563 by Adrien Grand (@jpountz), 1 vote, resolved Nov 30 2018
Linked issues:

• SOLR-13025

Pull requests: apache/lucene-solr#511

[asfimport]

Elizabeth Haubert (migrated from JIRA)

Mathematically, it changes the ratio of
{code:java}
tf * idf / ( tf + norm)
{/code}

which determines the relative importance of the norms parameter. It seems like that should affect ranking, at least for low values of tf. Why not just set the parameter to 0 for the cases you are looking at?

[asfimport]

Adrien Grand (@jpountz) (migrated from JIRA)

Elizabeth Haubert The change I'm suggesting would divide every BM25 score by (k1+1), which doesn't affect ranking. Setting k1 to 0 would have the undesirable side-effect of disabling the impact of term frequency and document length: the formula that I wrote was a bit simplified as norm actually depends on k1, it looks like below when expanding norm:

boost * IDF * (k1+1) * tf / (tf + k1 * (1 - b + b * len / avgLen))

[asfimport]

Robert Muir (@rmuir) (migrated from JIRA)

+1 to nuke it. Currently the explain() goes out of its way to try to separate out this scaling factor to make it easier to see. Its unnecessary.

[asfimport]

Elizabeth Haubert (migrated from JIRA)

The boost*IDF is not particularly important, this is about the handling of the TF component relative to the norms.

Pull that out as

(tf + k1*tf) / (tf + k1*length_norms)

Removing it only from the numerator produces

 tf / (tf +k1* length norms) 

At a minimum, that will need a new empirical default for k1.

Changing k1 in the numerator is the knob to adjust the ratio of tf and norms. In the case where document length does not follow standard models, it can be helpful to damp down b. This is not the standard use case, but is not unusual, either. At the extreme, b=0 then this component reduces to

(tf * (k1 +1)) / (tf + k1)

Removing the (k1 +1) from the numerator only produces

tf / (tf + k1)

There will be cases where this affects relative scoring and ranking, and I don't understand the statement that it doesn't modify ordering.

If there is a need to remove it in the normal case, then perhaps the numerator and denominator should be split into two distinct constants.

[asfimport]

Adrien Grand (@jpountz) (migrated from JIRA)

There will be cases where this affects relative scoring and ranking

I don't think this is correct. All scores would be divided by the same constant, so ordering would be preserved.

[asfimport]

Doug Turnbull (@softwaredoug) (migrated from JIRA)

It would modify ordering when dealing with multiple fields. Consider one field with a different k1 than another because the impact of term frequency is calibrated differently. If one calibrates one field to saturate term freq faster, and another slower, then ordering would be impacted

[asfimport]

Doug Turnbull (@softwaredoug) (migrated from JIRA)

For the sake of this discussion, here's a desmos graph with BM25 with/without k1 in the numerator 

https://www.desmos.com/calculator/cklb27fcn9 

[asfimport]

Adrien Grand (@jpountz) (migrated from JIRA)

Agreed @softwaredoug I was assuming a single similarity. This would also change ordering if other fields use different similarities.

[asfimport]

Luca Cavanna (@javanna) (migrated from JIRA)

Hi folks, I would like to work on this issue.

[asfimport]

Adrien Grand (@jpountz) (migrated from JIRA)

That would be great @javanna. I suspect most of the work is going to be about fixing tests that rely on absolute score values.

[asfimport]

Michael Gibney (@magibney) (migrated from JIRA)

"assuming a single similarity" – is this something that we want to assume? If every field similarity uses the same k1 param, then sure, relative ordering among fields is maintained. But if we're using these scores outside of the context of single-similarity, and intend to preserve the ability to adjust the k1 param, it's worth noting that this change fundamentally alters the effect of the k1 param on absolute scores (and thus also on relative scores across similarities).

Namely, removing k1 from the numerator places a hard cap on the score, regardless of TF or k1 setting. The concept of saturation is preserved, but with no numerator k1, saturation is implemented strictly by depressing scores (with respect to the hard cap, by varying amounts according to TF) as k1 increases. The model with k1 in the numerator strikes me as being more flexible, both depressing scores for lower TF and increasing scores for higher TF, around an inflection point determined by length norms and the value of b.

I'm sure this change would be appropriate for some scenarios, but it's a fundamental change that could in some cases have significant downstream consequences, with no easy way (as far as I can tell) to maintain existing behavior.

[asfimport]

Adrien Grand (@jpountz) (migrated from JIRA)

"assuming a single similarity" – is this something that we want to assume?

We can't indeed, even though this is the most common case. That said if you are searching multiple fields at once today, the I'm afraid that relevance isn't very good anyway as we don't support something like BM25F (#9263) to merge index and document statistics (BlendedTermQuery merges index statistics, but not norms and term frequencies). By the way BM25F doesn't allow to configure the value of k1 on a per-field basis, only b may have different per-field values.

I'm sure this change would be appropriate for some scenarios, but it's a fundamental change that could in some cases have significant downstream consequences, with no easy way (as far as I can tell) to maintain existing behavior.

Users could multiply their per-field boosts by (k1+1)?

[asfimport]

Doug Turnbull (@softwaredoug) (migrated from JIRA)

I feel perhaps one way forward is to create a second (default?) similarity - FastBM25Similarity? ConstantCeilingBM25Similarity? and leave in place the current BM25 similarity as an optional similarity to configure. There may be existing practices around tuning BM25 similarity at many places where writing a similarity plugin is not an option

[asfimport]

Michael Gibney (@magibney) (migrated from JIRA)

@jpountz, thanks for pointing out the work on BM25F. I'm interested to take a closer look at that.
"Users could multiply their per-field boosts by (k1+1)?" ... thanks, yes! That should work in a pinch, though I was so focused on the Similarity that I missed the possibility of scaling it externally in this way.

Having k1's presence in the numerator be configurable (either as an extra boolean parameter to the (modified) existing BM25Similarity, or something along the lines of what @softwaredoug suggests) would make sense to me, regardless of the benefits of the change (performance or otherwise).

[asfimport]

Robert Muir (@rmuir) (migrated from JIRA)

No, we shouldn't clutter up BM25Similarity because some users have bad behavior.

If they did the wrong thing and rely on the exact absolute magnitude of the old similarity, well that's why the mechanism is extensible.