Improved Text Scoring with BM25

Today the default scoring algorithm in Elasticsearch is TF/IDF. This default will change to BM25 once Elasticsearch switches to Lucene 6. In this talk, Britta will tell you all about BM25 – what it is, how it differs from TF/IDF and other scoring techniques, and why it might be the better default going forward.

Transcript

1. ‹#› Britta Weber 5/11/2016 BM25 Demystified
2. 2 What is BM25? “Oh! BM25 is that probabilistic approach to scoring!”
3. 3 What is BM25?
4. 4 What is BM25?
5. 5 What is BM25?
6. Why is this so complicated? 6
7. Usually when you use elasticsearch you will have clear search criteria • categories • timestamps • age • ids … 7 Searching in natural language text "_source": { "oder-nr": 1234, "items": [3,5,7], "price": 30.85, "customer": "Jon Doe", "date": "2015-01-01" }
8. Tweets mails, articles,… are fuzzy • language is ambivalent, verbose and many topics in one doc • no clear way to formulate your query 8 Searching in natural language text "_source": { "titles": "guru of everything", "programming_languages": [ "java", "python", "FORTRAN" ], "age": 32, "name": "Jon Doe", "date": "2015-01-01", "self-description": "I am a hard-working self-motivated expert in everything. High performance is not just an empty word for me..." }
9. 9 A free text search is a very inaccurate description of our information need What you want: • quick learner • works hard • reliable • enduring • … "_source": { "titles": "guru of everything", "programming_languages": [ "java", "python", "FORTRAN" ], "age": 32, "name": "Jon Doe", "date": "2015-01-01", "self-description": "I am a hard-working self-motivated expert in everything. High performance is not just an empty word for me..." }
10. 10 A free text search is a very inaccurate description of our information need What you want: • quick learner • works hard • reliable • enduring • … But you type : “hard-working, self-motivated, masochist” "_source": { "titles": "guru of everything", "programming_languages": [ "java", "python", "FORTRAN" ], "age": 32, "name": "Jon Doe", "date": "2015-01-01", "self-description": "I am a hard-working self-motivated expert in everything. High performance is not just an empty word for me..." }
11. By the end of this talk you should • know the monster, understand what the parameters of BM25 do 11 The purpose of this talk
12. 12 The purpose of this talk By the end of this talk you should • know the monster, understand what the parameters of BM25 do • know why it has the label “probabilistic”
13. 13 The purpose of this talk By the end of this talk you should • know the monster, understand what the parameters of BM25 do • know why it has the label “probabilistic” • be convinced that switching to BM25 is the right thing to do
14. 14 The purpose of this talk By the end of this talk you should • know the monster, understand what the parameters of BM25 do • know why it has the label “probabilistic” • be convinced that switching to BM25 is the right thing to do • be able to impress people with you in depth knowledge of probabilistic scoring
15. The current default - TF/IDF 15
16. 16 Example: we are looking for an intern Search in self-description of applications for these words: • self-motivated • hard-working • masochist We want to order applications by their relevance to the query.
17. 17 Evidence for relevance - term frequencies Use term frequencies in description, title etc. “I got my PhD in Semiotics at the University of ….but I am still hard-working! … It takes a masochist to go through a PhD…”
18. 18 Major tweaks • term frequency: more is better
19. 19 Major tweaks • term frequency: more is better • inverse document frequency: common words are less important
20. 20 Major tweaks • term frequency: more is better • inverse document frequency: common words are less important • long documents with same tf are less important: norm
21. 21 Bool query and the coord- factor Query: holiday, china “Blog: My holiday in Bejing” term frequencies: holiday: 4 china: 5 “Economic development of Sichuan from 1920-1930” term frequencies: holiday: 0 china: 15 Coord factor: reward document 1 because both terms matched
22. 22 TF/IDF • Successful since the beginning of Lucene • Well studied • Easy to understand • One size fits most
23. 23 What is wrong with TF/IDF? It is a heuristic that makes sense intuitively but it is somewhat a guess. (Ad hoc.) So…can we do better?
24. Probabilistic ranking and how it led to BM25 24
25. 25 The root of BM25: Probability ranking principle (abridged) “If retrieved documents are ordered by decreasing probability of relevance on the data available, then the system’s effectiveness is the best that can be obtained for the data.” K. Sparck Jones, S. Walker, and S. E. Robertson, “A probabilistic model of information retrieval: Development and comparative experiments. Part 1,”
26. • simplification: relevance is binary! • get a dataset queries - relevant/ irrelevant documents • use that to estimate relevancy 26 Estimate relevancy
27. 27 Estimate relevancy
28. get a dataset queries - relevant/irrelevant documents and use that to estimate relevancy 28 Estimate relevancy relevant all documents
29. 29 In math For each document, query pair - what is the probability that the document is relevant? Order by that!
30. 30 In math q1 q2 … d1 0.1 0.4 … d2 0.2 0.1 … d3 0.2 0.5 … … … … …
31. 31 In math No way we can ever get a list of that, no matter how many interns we hire…. q1 q2 … d1 0.1 0.4 … d2 0.2 0.1 … d3 0.2 0.5 … … … … …
32. …here be math… 32
34. 34 …and we get to…
35. 35 …and we get to… …but at least we know we only need two distributions! P(tf of “hard-working” = 1| R=1) = 0.1 P(tf of “hard-working” = 1| R=0) = 0.12 P(tf of “hard-working” = 2| R=1) = 0.3 … P(“hard-working” does not occur in document| R=1) = 0.1 P(“hard-working” does not occur in document| R=0) = 0.4
36. How to estimate all these probabilities 36
37. query term occurs in a document or doesn’t - we don’t care how often 37 The binary independence model - a dramatic but useful simplification relevant documents (R) relevant documents contain query term (r) documents contain query term (n) all documents (N)
38. 38 Use actual counts to estimate! Plug this into our weight equation relevant documents (R) relevant documents contain query term (r) documents contain query term (n) all documents (N) Stephen Robertson and Karen Spark Jones, Relevance Weighting of Search Terms
39. 39 Use actual counts to estimate! Plug this into our weight equation relevant documents (R) relevant documents contain query term (r) documents contain query term (n) all documents (N) Stephen Robertson and Karen Spark Jones, Relevance Weighting of Search Terms
40. 40 Robertson/Sparck Jones weight These are really just counts
41. 41 So, you have an unlimited supply of interns… relevant relevant documents contain query term (r) documents contain query term (n) all documents (N) weight motivated 0.1 working 0.6 experienced 0.23 … …
42. 42 …but you probably don’t have that Still use Robertson/Sparck Jones weight but assume that the number of relevant documents is negligible (R=0, r=0):
43. IDF comparison 43 BM25
44. IDF comparison 44 BM25 TF/IDF
45. BM25 - We are here… 45
46. BM25 - We are here… 46 idf - how popular is the term in the corpus?
47. 47 Now, consider term frequency! What does the number of occurrence of a term tell us about relevancy? • In TF/IDF: The more often the term occurs the better • But…is a document about a term just because it occurs a certain number of times? • This property is called “eliteness”
48. 48 Example for “eliteness” • “tourism” • Look at wikipedia: Many documents are about tourism • Many documents contain the word tourism - but are about something completely different, like for example just a country Can we use prior knowledge on the distribution of term frequency for getting a better estimate on the influence of tf?
49. Two cases: • document is not about the term 49 Eliteness as Poisson Distribution Stephen P. Harter, A probabilistic approach to automatic keyword indexing. Part I. On the Distribution of Specialty Words in a Technical Literature term frequency Probability for this term frequency documents that are not about term (E=0)
50. Two cases: • document is not about the term • document is about the term 50 Eliteness as Poisson Distribution Stephen P. Harter, A probabilistic approach to automatic keyword indexing. Part I. On the Distribution of Specialty Words in a Technical Literature term frequency Probability for this term frequency documents that actually are about term (E=1) documents that are not about term (E=0)
51. Two cases: • document is not about the term • document is about the term 51 Eliteness as Poisson Distribution Stephen P. Harter, A probabilistic approach to automatic keyword indexing. Part I. On the Distribution of Specialty Words in a Technical Literature term frequency Probability for this term frequency documents that actually are about term (E=1) documents that are not about term (E=0)
52. 52 How to estimate this? • gather data on eliteness for term • many term frequencies -> do for many documents
53. 53 We need even more interns!
54. Suppose we knew the relationship of frequency and eliteness. We need: relationship of frequency and relevancy! 54 How relevance ties into that
55. Suppose we knew the relationship of frequency and eliteness. We need: relationship of frequency and relevancy! • Have yet another distribution: • make eliteness depend on relevancy • estimate from data 55 How relevance ties into that elite documents elite and relevant documents relevant documents
56. 56 We need even more interns for the relevance too!
57. 57 elite elite and relevant documents relevant documents combine the two… …plug into here…
58. …here be math… 58
59. 59 …and we get to….
60. 60 …and we get to….
61. Stephen Robertson and Hugo Zaragoza, The Probabilistic Relevance Framework: BM25 and Beyond 61 “This is a somewhat messy formula, and furthermore we do not in general know the values of these three parameters, or have any easy way of estimating them.”
62. 62 “…they took a leap of faith…” Victor Lavrenko, Probabilistic model 9: BM25 and 2-poisson, youtube
63. 63 What is the shape? If we actually had all these interns and could get the exact shape then the curve… • would start at 0 • increase monotonically • approach a maximum asymptotically • maximum would be the IDF we computed before!
64. 64 What is the shape? If we actually had all these interns and could get the exact shape then the curve… • would start at 0 • increase monotonically • approach a maximum asymptotically • maximum would be the IDF we computed before! Just use something similar!
65. 65 Tf saturation curve • limits influence of tf • allows to tune influence by tweaking k bm25 - approaches limit ft,d = frequency of term in document k = saturation parameter
66. 66 Tf saturation curve • limits influence of tf • allows to tune influence by tweaking k bm25 - approaches limit tf/idf - keeps growing ft,d = frequency of term in document k = saturation parameter
67. BM25 - We are here… 67 idf - how popular is the term in the corpus?
68. BM25 - We are here… 68 idf - how popular is the term in the corpus? saturation curve - limit influence of tf on the score
69. • Poisson distribution: Assumes a fixed length of documents • But they don’t have that (most of the time) • We have to incorporate this too! • scale tf by it like so: 69 So…we assume all documents have same length? Interpolation between 1 and document length/average document length
70. 70 Influence of b • tweak influence of document length ft,d = frequency of term in document k = saturation parameter b = length parameter l ( d ) = number of tokens in document avgdl = average document length in corpus
71. 71 Influence of b • tweak influence of document length ft,d = frequency of term in document k = saturation parameter b = length parameter l ( d ) = number of tokens in document avgdl = average document length in corpus
72. BM25 - We are here… 72 idf - how popular is the term in the corpus? saturation curve - limit influence of tf on the score
73. BM25 - We are done! 73 idf - how popular is the term in the corpus? saturation curve - limit influence of tf on the score length weighing - tweak influence of document length
74. 74 Is BM25 probabilistic? • many approximations • really hard to get the probabilities right even with unlimited data BM25 is “inspired” by probabilistic ranking.
75. A short history of BM25 75 Probability ranking principle TREC-3 BM25 final! Poisson distribution for terms 1970 1980 1990 2000 2010 1975 1994 1977 TREC-2 Leap of faith 1993 1976 Robertson/Sparck Jones weight Pluggable similarities + BM25 in Lucene (GSoC, David Nemeskey) BM25 becomes default! elasticsearch 5.0 Lucene 6.0 First Lucene release (TF/IDF) 1999 2011 We are here ? 2016
76. So…will I get a better scoring with BM25? 76
77. 77 Pros with the frequency cutoff TF/IDF: common words can still influence the score! BM25: limits influence of term frequency • less influence of common words • no more coord factor! • check if you should disable coord for bool queries? index.similarity.default.type: BM25 bm25 - approaches limit tf/idf - keeps growing
78. 78 Other benefits parameters can be tweaked. To update: • close index • update mapping (or settings) • re-open index Mathematical framework to include non-textual features
79. 79 A warning: Lower automatic boost for short fields With TF/IDF: short fields (title,…) are automatically scored higher BM25: Scales field length with average • field length treatment does not automatically boost short fields (you have to explicitly boost) • might need to adjust boost
80. 80 Is BM25 better? • Literature suggests so • Challenges suggest so (TREC,…) • Users say so • Lucene developers say so • Konrad Beiske says so: Blog “BM25 vs Lucene Default Similarity” But: It depends on the features of your corpus. Finally: You can try it out now! Lucene stores everything necessary already.
81. 81 Useful literature • Manning et al., Introduction to Information retrieval • Robertson and Zaragoza, The Probabilistic Relevance Framework: BM25 and Beyond • Robertson et al., Okapi at TREC-3 • https://github.com/apache/lucene-solr/blob/master/lucene/core/src/java/org/ apache/lucene/search/similarities/BM25Similarity.java
82. 82 Thank you!