I cannot continue reading after this following “declaration”… Author should take a look at the Wikipedia page for TF-IDF.
> As someone who has a Ph.D. in Human-computer Interaction ;-), I feel like I am entitled to define a condition of "good" in relevance here. I hereby declare that:
>> A good top-K algorithm should rank a document containing more user query terms higher than a document containing less number of user query terms.
> This makes perfect sense. Right?
Also, “most search engines” don’t use vector space model as the only way to rank result, for example, page rank.
Edit: in some search scenarios finding the documents with the most query terms make sense, but Lucene can also rank using this metric. Still, applaud the author's effort in digging into research literature. Search relevance is very hard and standard off the shelf metrics like TF-IDF and page rank are often not enough. Good search usually requires deep understanding of the specific subject domain and hand-tuning tons of signals, many of which aren't even strictly based on search terms (e.g., previously purchased products on a store's website, geographic location, trending results).
A Ph.D means a lot for many people. It's years of work to make the science progress a tiny little bit on a topic you enjoy (supposedly). I think it's a lot harder and meaningful than writing scalable and reliable code as a team in a software company, just to give one example to compare with.
Exactly this. I have a PHD in CS and am a world class expert in multi-omic data integration and analysis. I'm happy to throw my weight around in that area, but I'd never point to my PhD to pontificate on Neural nets or systems or queuing theory or 99 percent of CS. If getting a PhD doesn't teach you how much you don't know and how hard it is to develop real expertise in any area, I think you wasted your PhD. Note, my PhD isn't on the value of PhDs so take it as you will.
I think I am pretty qualified to make my declaration, since it is about user experience.
I also do know a lot about IR, because I taught Information Retrieval class for 3 years when I was teaching in university, I read research papers, and I just come up with a new search algorithm.
It's just that some people cannot accept that there are people who can cross fields with ease, make contributions quickly, and move on to the next field that pit their interests.
Yes, I am one of those people. In addition to HCI, I also published in the following areas: VR, DB, NLP, IR and Psychology. Sorry to hurt your feelings, but it is what it is. Accept it and move on.
That's not a new search algorithm. It's about the second one people have come up with. First version: all documents containing all search terms. Second version: counting frequency in document. Since you taught IR for three years, I'm surprised there's no mention of other relevant heuristics, or measuring against benchmarks.
Again, you miss the novelty of the algorithm due to your smugness. I have updated the article to point out explicitly where the novelty is at. You completely ignored that. In fact, I believe you didn't even read that far before your jumping out to write this dismissal.
I wrote a blog post for lay people to read. I am under no obligation to do an extensive literature review, I only need to mention the essentials.
You just cannot seem to swallow the fact that someone who does not have a Ph.D in IR or computational linguistics can come in to contribute quickly then move on to something else. It hurts your feelings deeply, does it? Heed my advice, just get over it, don't take your degree or your specialization too seriously. It does not matter.
Of course it doesn't and the author doesn't try to make that claim. The author jokes that their HCI PhD is only good enough to give them the authority to make obvious statementd about what a "good" search experience should be for a user.
Well yeah, but it shouldn't make you smug. A Ph.D, while not the beginning, is definitely not the end, and the people we look up to as Really Smart never sat on their laurels and quit learning, never considered themselves above others.
It's fascinating seeing what hacker news thinks is smug. There are plenty of actually smug comments that go without being called out but for some reason this guy does.
The PhD flex in jest by the blog post's author is a bit awkward but I don't know that I would characterize it as smug.
Any insight into why the author is perceived as smug would be appreciated.
In the eyes of racists, Chinese Americans are supposed to be timid and does not make any noises, but I do make noises, so I am perceived as a smug today because I said I am a Ph.D, something else next time I said something else.
It's good for you that you are not a racist (it's sad that such a normal thing has to be a compliment, but it is a compliment. Good for you.), but racists do look for these cues and make their judgement based on these.
It's an unfortunate current state of affairs that we have to live with. Ignoring it does not make it going away though. If you don't like it, you got to call it out whenever you see it, which I hope you do, instead of being taken back by it, as you seems to be.
The benchmark is fine. Your so-called "fundamental" flaws are just superficial things, such as using a different time measure, using a different benchmark library, passing in a thread pool, and so on. These are immaterial to relative comparison, unless proven otherwise.
I have repeated asked you to send the code that does things properly in your mind, and you refused to do so.
So you are just trolling. Please stop hinder the progress of the industry through pointless trolling. Makes some positive contributions instead, and I have pointed out repeatedly how to make a positive contribution in this case. Please do.
You are a university student, I am a seasoned computer scientist, past researcher and professor, I am busying running a startup. This will be the last time I will say this to you: please consider contributing something positive to the world.
As author of Relevant Search and contriburor of AI powered search I endorse this :)
Relevance is really subjective, domain specific, requires intense amount of measurement and testing and many different ranking signals. Lucene is a toolbox for crafting many of these signals.
On second read-thru, I think the author is maybe(?) describing assumptions behind WAND and relevance algos that benefit from it? Maybe not some overarching statement about relevance per-se? But it's mixed in with statements about relevance / what Lucene does that are mostly incorrect...
For example, he says
> However, as you can see, this vector space model does not explicitly require a higher ranking document to contain more query terms than a lower ranking one.
Well the way you get a higher similarity in a vector-space model is matching more terms. The caveat being that IDF and field length makes you also consider a term's specificity. So if you search for 'luke skywalker' you care more about the 'skywalker' match than the 'luke' match. But a match on BOTH 'luke skywalker' would score higher (field lengths being constant)
There's no guarantee in pure vector space model that it is the case. Your understanding is way off. This is a caveat that Lucene prominently put on their Web page.
"Lucene scoring is the heart of why we all love Lucene. It is blazingly fast and it hides almost all of the complexity from the user. In a nutshell, it works. At least, that is, until it doesn't work, or doesn't work as one would expect it to work. Then we are left digging into Lucene internals or asking for help on java-user@lucene.apache.org to figure out why a document with five of our query terms scores lower than a different document with only one of the query terms."
See? Lucene people know about it but they just do not think it is a problem.
But I do.
T-Wand, though also uses vector space model, makes sure it is the case.
No there’s no guarantee. A very strong bias, but no absolute guarantee. Most people use AND queries by default or set a high enough min should match.
Those settings aside, arguably there are cases where fewer term matches could be more relevant.
For the search “Luke skywalker”
A tweet for example mentioning the term “Skywalker” once has much higher “Star Wars” aboutness than a move that uses skywalker one page and Luke pages apart.
That is the information density of Star Wars type content is far higher in the tweet, whereas eventually a book ends up using most English somewhere.
You either has or has no guarantee, that's what the word "guarantee" means. Don't mince words.
You had a wrong understanding. Now you are corrected. Let's move on.
Nobody said anything about "fewer term matches could not be more relevant". You are just making up straw men here. That's not the discussion we are having.
What I said is this, from a user point of view, it's not good to have a document containing fewer query terms to rank higher. This is a fact that even Lucene acknowledge (at least when they were version 3.5.0.). You have nothing to counter this fact.
But you’re arguing that such a guarantee ALWAYS is most relevant. When that’s not always the case.
There’s been extensive research justification behind the vector-space model. BM25 is the 25th iteration of a model and well tuned BM25 holds the highest non nueral performance on many tasks including question answering[1]. Research has long found including factors other than total term matches matters. Such as IDF[2] and field length[3].
Have you benchmarked your relevance assumptions similarly? If so I’d love to see them and learn more!
You are making up straw man again. Did I make that claim?
I was simply motivate my work, pointing out it's a problem that the current generation of search engine does not address.
What is "relevance", it is of course a context sensitive question.
You talk as if BM25 is the gold standard when it is not.
The research on this is all over the place. I just read an article that says that BM25 is way worse than alternative language models. You don't have to look far, for example this one that talks about Wand:
You know why I quit academia? It is useless arguments and virtual signalings like these.
I'd rather go out and build a damn thing that people like to use.
I merely pointed out that there's a problem, and I have a solution. I did not claim that my problem and my solution solve all problems. Isn't this obvious?
In my problem, my solution beats Lucene. It's as simple as that.
So if Lucene wants to be this infinitely configurable search library, it would be advisable to offer my solution as an option, or offer an better one that does something similar.
and I am simply saying, arguably, you can't make that claim without evidence.
(That said, I do find much to like about the article and the WAND / T-WAND explanation. I'm only pointing out you can't claim 'better relevance' without a benchmark to go with it.)
You are mincing words again. It's a blog post we are talking about here.
In order to motive the work, I have to say what benefits it will bring. Agree?
It's my problem, and I get to define what is better relevance for me. In addition, this is also a well known problem acknowledge by Lucene documentation. So it is not an isolated problem. Some of the users voiced their agreement right here in comments. That's enough evidence for a blog post?
If you were writing this, how would you write it? You probably do worse.
I see that you work in Shopify Search, I hope that your attitude towards your users are not as hostile as this. It's the users who decide what are relevant to them, not you. I hope you remember that. Your manager will also probably agree.
Pardon my intrusion, but I think there's the necessity of toning down the discussion a bit.
To be fair it is irrelevant where user A or user B works and I don't see any hostility in this discussion except the one from the blog's author.
If the aim is doing Science, let's do this peacefully!
I think the main problem that generated this discussion is the form of some sentences of the blog "As someone who has a Ph.D. in Human-computer Interaction ;-), I feel like I am entitled to define a condition of "good" in relevance here. I hereby declare that:
A good top-K algorithm should rank a document containing more user query terms higher than a document containing less number of user query terms.
This makes perfect sense. Right?"
This should have been changed in:
"For the sake of this blog post I am interested in a simplified relevance concept: more query terms matched -> more relevance"
In this way the blog would have not caused the outburst of (correct) indignation of the Information Retrieval community, that has been working for years on the topic, and knows very well how much complex is relevance.
Yes for sure! I agree. I mean no disrespect myself, the algorithm seems useful and I wish the author all the best. I know, from personal experience, having your work commented on can be stressful.
I'm just trying to understand what the author meant and their intention for anyone that might revisit this thread later. I think what you're saying sounds plausible as an interpretation.
That's the problem right there. The so called "Information Retrieval Community" does not seem to care about what users want, and they treat their users in a condescending way, ignoring an obvious problem for years, as clearly demonstrated here and elsewhere.
Why should I care about what they think? In the end of the day, they are serving the users. They are either going to be left behind, or they have to change.
For example, the newer search engines, such us, https://github.com/meilisearch/MeiliSearch, also do what T-Wand does. Users are going to vote by their feet. The "information retrieval community" be damned. It's as simple as that. Got it?
And change they will. What "information retrieval community" are you talking about? Just a bunch of fresh graduates who just got their PH.D, and some college students. That's about it. I don't see any IR professors coming out defending them.
The "hostility" I referred to was the one towards the users. Basically, he's demanding users to show evidence that whatever they want is better than BM25.
That's just wrong. Period. This is the reason I mention his job, because his job requires him to listen to the users, instead of taking something he learned in school and use that to talk condescendingly to his users. That's not gonna fly.
Given this context, I think whatever I said it is entirely appropriate.
It is actually smug, to suggest the author, in this case, me, a computer scientist and a past professor who taught Information Retrieval class for more than 3 years, and who just came up with a new search algorithm, to "take a look at Wikipedia page for TF-IDF".
In case you have not read the article due to your smugness, my search algorithm also uses TF-IDF and vector space model.
Please do not dis-understand what is going on here: I am running a startup, and I am also old enough to not care about publications as much as people who are younger or in academia.
That's why I chose to reveal this in a blog post instead of hiding it until after my paper is published. Understood?
Thank you. I am glad that you learned something from the article. I wrote the article for people like you, who are seeking knowledge and self improvement.
I'm not sure if this is a troll. It seems the author did not spend much time learning Lucene, it already does everything he needs and better. Of course Lucene does tf-idf! If you are not getting the results you want, you must not be indexing right or must have something misconfigured. Lucene lets you tweak relevance, speed, index space efficiency, etc in a million ways.
I meant as in "beating Lucene" without trying to use Lucene properly. It's like trying to use a spoon to cut a steak and then saying that you can beat silverware with your teeth.
I think you are almost be definition trolling when you write beating X (millions lines of code) with 600 lines.
because when you say 'beating' the implication is it does what X does better - as opposed to just matching my use case with 600 lines and not big dependency import.
this usage of beating is going to rile up (i.e troll) everyone familiar with the subject who can see thousands of ways you did not beat it.
Interesting. I can't say Lucene gives great results for relevance on a large database, eg. Confluence.
However there is a large space between algorithmic assumptions and what "relevance" actually is to the user. This article may improve, but my feeling is -- both for search and for the article -- that more context is needed.
Lucene has the concept of "minimum match," [1] which is what you're playing with. You can implement your algorithm on top of this relatively trivially, by re-querying with min_match=n, min_match=n-1, etc until you get results. If you wrote a Lucene plugin to do this, it would also be small (<600 lines) and fast.
People have chosen not to do this because (1) it adds complexity, and (2) the bold declaration you made (A good top-K algorithm should rank a document containing more user query terms higher than a document containing less number of user query terms) turns out to be only somewhat true in practice. It's pretty common for pagerank and other non-linguistic ranking signals etc to trump linguistic preciseness.
That said, everything is a tradeoff, and the industry has clearly chosen to return more candidates than strictly necessary, then prune them after the fact with better ML & relevance, rather than trying to construct the perfectly minimal candidate set while missing some possible results.
The industry has not "chosen" to not do what T-Wand does, the industry did not have that option because T-Wand just comes out. Now with T-Wand, the industry has that choice to make.
It is easy to implement T-Wand in the existing Lucene code base, and I would hope so. Otherwise, it would be a shame.
> Most search engines use something called a vector space model, where both user queries and documents are reduced to vectors (i.e. a fixed number of numbers). That is to say, the search engines are not looking at the meanings of the queries or the documents. Instead, they turned them both into some numbers. The search problem, is reduced to a problem of finding the similarity between the numbers representing the query and the numbers representing the documents.
I don't see how this is true for concordance-like searches (Trados-like, which seems to be what the article is concerned with - preferring the documents with all query words present in it, otherwise the documents with the most query words present in it, etc.). This sounds more like description of similarity useful for metric space indices or something like that.
Technically the author's description of how Lucene's ranking works is accurate.
But the catch is that Lucene's default "vector space model" treats each document as a very high-dimensional vector, where the components are the words in the document (scaled using tf-idf). Under this definition, "similarity" reduces to a normalized dot-product of the query vector and the document vector. So in practice, it does roughly what you want: documents that match more query words end up getting more non-zero terms in their similarity score, which leads to a higher ranking.
Hmm. I'll have to think about it but I don't quite see yet how this ensures that for example all documents containing all four words of a four-word query will be ranked ahead of documents containing three or fewer words of the query. Mere angle between two vectors would for example mean that a "document" consisting of three words of the query could be ranked higher than a document with thousands of words containing all four words of a query, even if the document vectors had tf-idf weighs as components. That clearly is a viable notion of similarity, but that's also clearly not what the type of search alluded to in the article is attempting to do.
Plus, your description definitely isn't something I would have been able to divine from the description from the article. Thanks for rephrasing it in comprehensible English.
That is because it doesn't ensure that all documents containing all query terms are ranked above with those with a subset (though it can be tuned such that it does).
The author deeply misunderstands how WAND works, and "T-WAND" is just WAND. Once a pivot is found, you don't have to advance all the iterators that precede it, but just enough to disprove the current document, at which point a new pivot is chosen (this is equivalent to the heuristic described in the article).
The order in which iterators are tested against the pivot can be term cardinality ordering (which is one of the heuristics described in the original paper AFAIR). Then, the pivot documents are a subset of what the article calls the current "tier" (union of the k rarest terms).
You fundamentally misunderstand both Wand and T-Wand.
I suggest you to read my article and the papers again.
The novelty of T-Wand, is not in sorting the rows on idf, which T-Wand actually does NOT do, but in adding some filtering conditions that are not previously reported in the literature.
You missed that, so you missed the whole point. Smugness hurts.
I see that you work on Facebook Search and I know you are one of the authors in this field, I can see why your feelings are hurt.
It's okay. There are always people smarter than you are, who can come into a completely new field, spend a few weeks, and come up with something new that you could not come up with when you have spent your whole career on.
It's OK. When you are older, you will learn to accept that. You can only work with what life gives you.
Please take my ideas and put that in Faceook Search, because it presently sucks.
BTW, you should have put the PDF of your paper on the Web, then I would have read it, instead of only recognizing your name, put it on arxiv like everyone else, if you want people to read it.
Also, that's why I post it on hacker news instead of publishing first in a conference. Because there will be more people reading it. Not many people read papers.
I would appreciate if you also send a PR to address these issues, since clearly you know more about benchmarking than me.
Contributing to open source project is good, right?
BTW, Lucene is an open source project, Datalevin is also an open source project. Contributing to either would be equally good.
Even if you only want to contribute to Lucene for some reasons, a better contribution would be to integrate T-Wand in Lucene, rather than trying to talk down Datalevin. Would you agree?
I never had the interest to "talk down Datalevin", I criticized the results because the title was quite misleading in the tones and the benchmarks were not rigorous enough to express conclusive statements.
The critics are all Lucene developers or deeply invested in that. The criticism boils down to well "Simply just know Lucene and handle the million lines of code by writing plugins and configurations to get the same result as OP", except with worse performance.
That's not true. The real problem is that he is implying that his software is faster than Lucene showing data from a benchmark that has substantial flaws.
The reason why the majority of criticism comes from Lucene users is because they generally have a higher knownledge about this field than the people that read this article without having the basic knowledge to form any kind of criticism
Incorrect. The benchmark is fine. Your so-called "fundamental" flaws are just superficial things, such as using a different time measure, using a different benchmark library, passing in a thread pool, and so on. These are immaterial for relative comparison, unless proven otherwise.
I have repeated asked you to send the code that does things properly in your mind, and you refused to do so.
So you are just trolling. Please stop hinder the progress of the industry through pointless trolling. Makes some positive contributions instead, and I have pointed out repeatedly how to make a positive contribution in this case. Please do.
You are a university student, I am a seasoned computer scientist, past researcher and professor, I am busying running a startup. This will be the last time I will say this to you: please consider contributing something positive to the world.
I already explained to you why I didn't open more than one PR to the project, I'm not trolling anyone:
without knowing Clojure the only contribution that I could do without spending literally days of work is just the use of System.nanoTime() instead of System.currentTimeMillis().
The reason why I don't write the other benchmarks in Java is because reimplementing anything from zero costs precious time, that I don't have.
If you don't have time too, instead of closing the issues and calling me a troll, you can just say that; you are taking some valid critiques as a personal attack.
It's true that I'm just an university student and you are a scientist, a researcher, a professor, and an enterpreneur, but it doesn't mean that I can't be knowledged as you in very narrow fields. I'm currently running a personal project that uses Lucene since four years ago, with about 8 billion messages and 340 million chats stored in a distributed lucene index, so I'm not the regular troll or a person that just talks without knowing anything. I surely can't critique your T-WAND algorithm, that it seems to be good in your use case, but with all the humilty in the world I can say to have the minimum knowledge required to spot some weird usages of Lucene APIs.
As I have repeated suggested, since you obviously know Lucene, it does not take much for you to write a few lines of Java code to say, "here, this is how it is supposed to be done".
Instead, you keeps giving all kind of excuses. You said you do not have time, but somehow you have time to write long wall of text like this. If you are not trolling, what you are doing then?
I pointed out to you why your suggestions will not make differences, some I have already tried. For example, initializing a query parser only once, but that would crash Lucene. Clearly, you do not know about this, so your knowledge of Lucene is not as good as you think you know.
So if someone created a document consisting of just these search terms (and nothing else) in the search order, that's always going to be the highest ranked item, right, despite a lack of any added information, right?
Forgive me if this is a dumb question, Clojure isn't a language I know at all so it was a little hard to parse the code, I couldn't figure out if there was something that indicated a minimum levenshtein distance threshold for documents, but I feel like only looking at documents which are longer than the search query would also be a reasonable optimization.
As a user, when I write a search query as a space-separated list of n words, I expect to see documents which contain all of those words (or synonyms). I absolutely don't want to see documents which contain only n-1 of the specified words. I know exactly what I want, and the reason I've added the last word to the query is that there were too many generic, boring, irrelevant results without it.
You completely misunderstood what this project does.
This kind of libraries do not force you to return results in a specific way.
Generally they allow the programmer to customize how the results are scored and chosen.
There's the kind of library Lucene wants to be, a configurable library. But there are other libraries do not want that.
In this case, Datalevin is a database system, full-text search is just but a feature, I do not want users to configure full-text search in Datalevin as much as they like in Lucene. I want the default to be good, which Lucene's is not.
Every single document “page” humans index has three “interesting” dimensions: the height and width of the page the words appear on, plus another for the font size.
So, what is a document anyway? Is a file handle just another type of dimension? Or, is a picture on the page part of the page document, or is it its own document?
Humans use arbitrary dimensions to tokenize the document’s bits, so to speak.
My dad could read a book (a big document) in blocks or chunks. In thinking of it that way it become apparent that groups and positions of data may constitute their own document boundaries and that info may be used in both the indexing and search pipelines to build relevance and relatedness.
I would appreciate people who claims that "the author does not know Lucene enough" to send a Pull Request, where Lucene is configured to do the same thing that T-Wand does, that is to guarantee documents containing more query terms to rank higher than those containing less query terms.
To those who says "I like Lucene because it does Tf-idf", please be assured that T-Wand also does tf-idf and uses vector space model.
To those who say "T-Wand is just Wand", please be reminded that you are just repeating what the article was saying. Of course T-Wand is Wand, but you miss the technical contribution of T-Wand, which is clearly laid out in "What's new in T-Wand" section of the article. Of course, it is understandable if you are not able to judge the merit of that contribution, for that's the job of the peer review panel, which I do not expect Hacker News readers to be. This work will be submitted to a peer reviewed conference with more experiments added and all trade-offs discussed.
This may come as a disappointment to some, but the paper will not have a comparison with Lucene, for it would be scientifically unsound.
However, it should be easy for Lucene to add T-Wand as an option, and I do hope so.
I opened a PR to use the more precise timers. This would not improve the performance of any of the tests, but it will improve their time accuracy.
I highlighted some other problems related to the Lucene benchmark, but since I can't program in Clojure I can't fix them with a PR: I opened 3 issues to describe what can be done to address them.
Merged your PR. Thank you! If you do not know Clojure, that's fine, just outline what you want to do in Java, I can translate that into Clojure. Thanks.
To be honest, all your proposed changes would not make material difference, for algorithmic differences cannot be made up by implementation details.
As has already been demonstrated, T-Wand is implemented in a much slower language, Clojure. Clojure is implemented on top of JVM, it cannot possibly beat the same algorithm written in optimized Java. The only way to make a difference is to change the algorithm. So all your suggestions would not make a difference.
For what its worth, a final advise for those fresh graduates and college students. Don't take too seriously what your learned from books in school. They are not the gold standard the society measures things by. You got the wrong impression if you think your professors taught you that. They knew better. Don't take too much pride in your degree or in your specializations. They are nothing.
If you do not learn this now, your managers who maybe only has an associate degree from a community college, or from a school you look down on, will make you learn that soon enough.
These are not important things. An important thing is to keep an open mind and keep learning, so you are continuously employable. You can congratulate yourself when you are as old as me and can still do new things.
One observation I have to make: this community of information retrieval seems to be very thin-faced and cannot seem to accept outside contributions. I hope I am wrong.
This is not an isolated case. They rejected some industry changing contributions when they first came out.
For example, I remember that Google PageRank paper was outright rejected by SiGIR. Lucky for us, that paper was rejected, shattering the dream of an easy academia career for the two Google founders. Otherwise, we would probably still be searching with hotbots (remember that?).
The WAND paper was published in CIKM, a lowly conference in some people's eyes, I guess that's not the first venue they tried to publish that work in, because I worked at IBM Research before, I knew for a fact that CIKM was not in the first tier of the venues to publish, definitely not for the IR PIC.
Very interesting. I wonder what have caused this. My wild guess is that this may has something to do with early mistreatment the pioneering IR people received from the wider CS community, because their field was probably considered "soft" and not hard enough. For instance, even today, IR papers are not full of theorems and proofs, unlike some other CS fields, such as database. Their revengeful attitude got passed down to their students, as we can see here. And their reasons for dismissing other people's work are all the same: this is not new, we have done this before. But you have not, because the proof is in the systems you build and the papers you publish.
It does not have to be this way. HCI is even softer, but HCI is the most open field in CS, anyone can publish, you can prove theorems, or you can present user studies, anything goes. Funding? Not a problem. Because it is so open, HCI can work with anyone and on any projects. I remember that my advisor had so much funding, he basically paid me to whatever I wanted when I was in school. I am deeply in gratitude for that openness.
95 comments
[ 3.1 ms ] story [ 198 ms ] thread> As someone who has a Ph.D. in Human-computer Interaction ;-), I feel like I am entitled to define a condition of "good" in relevance here. I hereby declare that:
>> A good top-K algorithm should rank a document containing more user query terms higher than a document containing less number of user query terms.
> This makes perfect sense. Right?
Also, “most search engines” don’t use vector space model as the only way to rank result, for example, page rank.
Edit: in some search scenarios finding the documents with the most query terms make sense, but Lucene can also rank using this metric. Still, applaud the author's effort in digging into research literature. Search relevance is very hard and standard off the shelf metrics like TF-IDF and page rank are often not enough. Good search usually requires deep understanding of the specific subject domain and hand-tuning tons of signals, many of which aren't even strictly based on search terms (e.g., previously purchased products on a store's website, geographic location, trending results).
I also do know a lot about IR, because I taught Information Retrieval class for 3 years when I was teaching in university, I read research papers, and I just come up with a new search algorithm.
It's just that some people cannot accept that there are people who can cross fields with ease, make contributions quickly, and move on to the next field that pit their interests.
Yes, I am one of those people. In addition to HCI, I also published in the following areas: VR, DB, NLP, IR and Psychology. Sorry to hurt your feelings, but it is what it is. Accept it and move on.
I wrote a blog post for lay people to read. I am under no obligation to do an extensive literature review, I only need to mention the essentials.
You just cannot seem to swallow the fact that someone who does not have a Ph.D in IR or computational linguistics can come in to contribute quickly then move on to something else. It hurts your feelings deeply, does it? Heed my advice, just get over it, don't take your degree or your specialization too seriously. It does not matter.
What did I miss?
The PhD flex in jest by the blog post's author is a bit awkward but I don't know that I would characterize it as smug.
Any insight into why the author is perceived as smug would be appreciated.
I could see calling it audacious. But, our industry advances on audacity.
What's wrong with people? I think a lot of them are probably just university students who have nothing better to do than to troll on Internet.
I am obviously a Chinese.
In the eyes of racists, Chinese Americans are supposed to be timid and does not make any noises, but I do make noises, so I am perceived as a smug today because I said I am a Ph.D, something else next time I said something else.
It's not complicated.
OK, re-reading it, there are a few hints (a Chinese proverb, your nickname, etc.). But nothing "obvious".
Probably not the explanation we are looking for here.
It's good for you that you are not a racist (it's sad that such a normal thing has to be a compliment, but it is a compliment. Good for you.), but racists do look for these cues and make their judgement based on these.
It's an unfortunate current state of affairs that we have to live with. Ignoring it does not make it going away though. If you don't like it, you got to call it out whenever you see it, which I hope you do, instead of being taken back by it, as you seems to be.
Why do you have to use a throwaway account to say this, I am curious.
I have repeated asked you to send the code that does things properly in your mind, and you refused to do so.
So you are just trolling. Please stop hinder the progress of the industry through pointless trolling. Makes some positive contributions instead, and I have pointed out repeatedly how to make a positive contribution in this case. Please do.
You are a university student, I am a seasoned computer scientist, past researcher and professor, I am busying running a startup. This will be the last time I will say this to you: please consider contributing something positive to the world.
Relevance is really subjective, domain specific, requires intense amount of measurement and testing and many different ranking signals. Lucene is a toolbox for crafting many of these signals.
For example, he says
> However, as you can see, this vector space model does not explicitly require a higher ranking document to contain more query terms than a lower ranking one.
Well the way you get a higher similarity in a vector-space model is matching more terms. The caveat being that IDF and field length makes you also consider a term's specificity. So if you search for 'luke skywalker' you care more about the 'skywalker' match than the 'luke' match. But a match on BOTH 'luke skywalker' would score higher (field lengths being constant)
https://lucene.apache.org/core/3_5_0/scoring.html
"Lucene scoring is the heart of why we all love Lucene. It is blazingly fast and it hides almost all of the complexity from the user. In a nutshell, it works. At least, that is, until it doesn't work, or doesn't work as one would expect it to work. Then we are left digging into Lucene internals or asking for help on java-user@lucene.apache.org to figure out why a document with five of our query terms scores lower than a different document with only one of the query terms."
See? Lucene people know about it but they just do not think it is a problem.
But I do.
T-Wand, though also uses vector space model, makes sure it is the case.
Those settings aside, arguably there are cases where fewer term matches could be more relevant.
For the search “Luke skywalker”
A tweet for example mentioning the term “Skywalker” once has much higher “Star Wars” aboutness than a move that uses skywalker one page and Luke pages apart.
That is the information density of Star Wars type content is far higher in the tweet, whereas eventually a book ends up using most English somewhere.
You had a wrong understanding. Now you are corrected. Let's move on.
Nobody said anything about "fewer term matches could not be more relevant". You are just making up straw men here. That's not the discussion we are having.
What I said is this, from a user point of view, it's not good to have a document containing fewer query terms to rank higher. This is a fact that even Lucene acknowledge (at least when they were version 3.5.0.). You have nothing to counter this fact.
There’s been extensive research justification behind the vector-space model. BM25 is the 25th iteration of a model and well tuned BM25 holds the highest non nueral performance on many tasks including question answering[1]. Research has long found including factors other than total term matches matters. Such as IDF[2] and field length[3].
Have you benchmarked your relevance assumptions similarly? If so I’d love to see them and learn more!
1 - https://www.elastic.co/blog/improving-search-relevance-with-...
2- https://www.researchgate.net/publication/238123710_Understan...
3 - http://sifaka.cs.uiuc.edu/course/410s12/mir.pdf
I was simply motivate my work, pointing out it's a problem that the current generation of search engine does not address.
What is "relevance", it is of course a context sensitive question.
You talk as if BM25 is the gold standard when it is not.
The research on this is all over the place. I just read an article that says that BM25 is way worse than alternative language models. You don't have to look far, for example this one that talks about Wand:
https://dl.acm.org/doi/10.1145/2537734.2537744
You know why I quit academia? It is useless arguments and virtual signalings like these.
I'd rather go out and build a damn thing that people like to use.
I merely pointed out that there's a problem, and I have a solution. I did not claim that my problem and my solution solve all problems. Isn't this obvious?
In my problem, my solution beats Lucene. It's as simple as that.
So if Lucene wants to be this infinitely configurable search library, it would be advisable to offer my solution as an option, or offer an better one that does something similar.
So far I have not seen any takers, only excuses.
"Better Relevance"
and I am simply saying, arguably, you can't make that claim without evidence.
(That said, I do find much to like about the article and the WAND / T-WAND explanation. I'm only pointing out you can't claim 'better relevance' without a benchmark to go with it.)
In order to motive the work, I have to say what benefits it will bring. Agree?
It's my problem, and I get to define what is better relevance for me. In addition, this is also a well known problem acknowledge by Lucene documentation. So it is not an isolated problem. Some of the users voiced their agreement right here in comments. That's enough evidence for a blog post?
If you were writing this, how would you write it? You probably do worse.
I see that you work in Shopify Search, I hope that your attitude towards your users are not as hostile as this. It's the users who decide what are relevant to them, not you. I hope you remember that. Your manager will also probably agree.
A good top-K algorithm should rank a document containing more user query terms higher than a document containing less number of user query terms. This makes perfect sense. Right?" This should have been changed in: "For the sake of this blog post I am interested in a simplified relevance concept: more query terms matched -> more relevance" In this way the blog would have not caused the outburst of (correct) indignation of the Information Retrieval community, that has been working for years on the topic, and knows very well how much complex is relevance.
I'm just trying to understand what the author meant and their intention for anyone that might revisit this thread later. I think what you're saying sounds plausible as an interpretation.
Why should I care about what they think? In the end of the day, they are serving the users. They are either going to be left behind, or they have to change.
For example, the newer search engines, such us, https://github.com/meilisearch/MeiliSearch, also do what T-Wand does. Users are going to vote by their feet. The "information retrieval community" be damned. It's as simple as that. Got it?
And change they will. What "information retrieval community" are you talking about? Just a bunch of fresh graduates who just got their PH.D, and some college students. That's about it. I don't see any IR professors coming out defending them.
That's just wrong. Period. This is the reason I mention his job, because his job requires him to listen to the users, instead of taking something he learned in school and use that to talk condescendingly to his users. That's not gonna fly.
Given this context, I think whatever I said it is entirely appropriate.
It is actually smug, to suggest the author, in this case, me, a computer scientist and a past professor who taught Information Retrieval class for more than 3 years, and who just came up with a new search algorithm, to "take a look at Wikipedia page for TF-IDF".
In case you have not read the article due to your smugness, my search algorithm also uses TF-IDF and vector space model.
Please do not dis-understand what is going on here: I am running a startup, and I am also old enough to not care about publications as much as people who are younger or in academia.
That's why I chose to reveal this in a blog post instead of hiding it until after my paper is published. Understood?
I do not understand why rejecting a million-lines-of-code dependency implies the person is a troll?
because when you say 'beating' the implication is it does what X does better - as opposed to just matching my use case with 600 lines and not big dependency import.
this usage of beating is going to rile up (i.e troll) everyone familiar with the subject who can see thousands of ways you did not beat it.
Any additional features that a product has but which you don’t need for a particular purpose is a downside, not an upside.
They’re not claiming to beat Lucene for the general case of everything Lucene is capable of.
He didn't use any benchmarking library, and he used System.currentTimeMillis instead of the high precision timer available with System.nanoTime.
He also instantiated the IndexSearcher without specifying any executor and he instantiated the legacy query parser on every lucene search
I am writing a database, full-text search is just a *minor* feature.
Why should I bringing in a huge dependency for a minor feature when my whole code base is orders magnitude smaller than that?
However there is a large space between algorithmic assumptions and what "relevance" actually is to the user. This article may improve, but my feeling is -- both for search and for the article -- that more context is needed.
People have chosen not to do this because (1) it adds complexity, and (2) the bold declaration you made (A good top-K algorithm should rank a document containing more user query terms higher than a document containing less number of user query terms) turns out to be only somewhat true in practice. It's pretty common for pagerank and other non-linguistic ranking signals etc to trump linguistic preciseness.
That said, everything is a tradeoff, and the industry has clearly chosen to return more candidates than strictly necessary, then prune them after the fact with better ML & relevance, rather than trying to construct the perfectly minimal candidate set while missing some possible results.
[1] See https://www.elastic.co/guide/en/elasticsearch/reference/curr...
It is easy to implement T-Wand in the existing Lucene code base, and I would hope so. Otherwise, it would be a shame.
I don't see how this is true for concordance-like searches (Trados-like, which seems to be what the article is concerned with - preferring the documents with all query words present in it, otherwise the documents with the most query words present in it, etc.). This sounds more like description of similarity useful for metric space indices or something like that.
But the catch is that Lucene's default "vector space model" treats each document as a very high-dimensional vector, where the components are the words in the document (scaled using tf-idf). Under this definition, "similarity" reduces to a normalized dot-product of the query vector and the document vector. So in practice, it does roughly what you want: documents that match more query words end up getting more non-zero terms in their similarity score, which leads to a higher ranking.
Plus, your description definitely isn't something I would have been able to divine from the description from the article. Thanks for rephrasing it in comprehensible English.
The order in which iterators are tested against the pivot can be term cardinality ordering (which is one of the heuristics described in the original paper AFAIR). Then, the pivot documents are a subset of what the article calls the current "tier" (union of the k rarest terms).
You fundamentally misunderstand both Wand and T-Wand.
I suggest you to read my article and the papers again.
The novelty of T-Wand, is not in sorting the rows on idf, which T-Wand actually does NOT do, but in adding some filtering conditions that are not previously reported in the literature.
You missed that, so you missed the whole point. Smugness hurts.
I see that you work on Facebook Search and I know you are one of the authors in this field, I can see why your feelings are hurt.
It's okay. There are always people smarter than you are, who can come into a completely new field, spend a few weeks, and come up with something new that you could not come up with when you have spent your whole career on.
It's OK. When you are older, you will learn to accept that. You can only work with what life gives you.
Please take my ideas and put that in Faceook Search, because it presently sucks.
BTW, you should have put the PDF of your paper on the Web, then I would have read it, instead of only recognizing your name, put it on arxiv like everyone else, if you want people to read it.
Also, that's why I post it on hacker news instead of publishing first in a conference. Because there will be more people reading it. Not many people read papers.
https://github.com/juji-io/datalevin/issues/created_by/caval...
Contributing to open source project is good, right?
BTW, Lucene is an open source project, Datalevin is also an open source project. Contributing to either would be equally good.
Even if you only want to contribute to Lucene for some reasons, a better contribution would be to integrate T-Wand in Lucene, rather than trying to talk down Datalevin. Would you agree?
tf-idf and phrase search alone make lucene 10x better, not speaking of the compression, fuzzy search, advanced query features etc.
I love new search engines like tantivy etc, but this is, due to the tone, a sad joke.
Besides, the said technology does do tf-idf and fuzzy search, and will soon have phrase search, and other features, if enough people request them.
Datalevin is an open source project, not unlike Lucene. What's the difference? Not like the tone?
I have repeated asked you to send the code that does things properly in your mind, and you refused to do so.
So you are just trolling. Please stop hinder the progress of the industry through pointless trolling. Makes some positive contributions instead, and I have pointed out repeatedly how to make a positive contribution in this case. Please do.
You are a university student, I am a seasoned computer scientist, past researcher and professor, I am busying running a startup. This will be the last time I will say this to you: please consider contributing something positive to the world.
It's true that I'm just an university student and you are a scientist, a researcher, a professor, and an enterpreneur, but it doesn't mean that I can't be knowledged as you in very narrow fields. I'm currently running a personal project that uses Lucene since four years ago, with about 8 billion messages and 340 million chats stored in a distributed lucene index, so I'm not the regular troll or a person that just talks without knowing anything. I surely can't critique your T-WAND algorithm, that it seems to be good in your use case, but with all the humilty in the world I can say to have the minimum knowledge required to spot some weird usages of Lucene APIs.
Instead, you keeps giving all kind of excuses. You said you do not have time, but somehow you have time to write long wall of text like this. If you are not trolling, what you are doing then?
I pointed out to you why your suggestions will not make differences, some I have already tried. For example, initializing a query parser only once, but that would crash Lucene. Clearly, you do not know about this, so your knowledge of Lucene is not as good as you think you know.
Fair?
Forgive me if this is a dumb question, Clojure isn't a language I know at all so it was a little hard to parse the code, I couldn't figure out if there was something that indicated a minimum levenshtein distance threshold for documents, but I feel like only looking at documents which are longer than the search query would also be a reasonable optimization.
There's the kind of library Lucene wants to be, a configurable library. But there are other libraries do not want that.
In this case, Datalevin is a database system, full-text search is just but a feature, I do not want users to configure full-text search in Datalevin as much as they like in Lucene. I want the default to be good, which Lucene's is not.
> If the problem is too big to be solved by this, you are probably ready for Lucene.
https://www.gnu.org/software/parallel/parallel.html?highligh...
So, what is a document anyway? Is a file handle just another type of dimension? Or, is a picture on the page part of the page document, or is it its own document?
Humans use arbitrary dimensions to tokenize the document’s bits, so to speak.
My dad could read a book (a big document) in blocks or chunks. In thinking of it that way it become apparent that groups and positions of data may constitute their own document boundaries and that info may be used in both the indexing and search pipelines to build relevance and relatedness.
To those who says "I like Lucene because it does Tf-idf", please be assured that T-Wand also does tf-idf and uses vector space model.
To those who say "T-Wand is just Wand", please be reminded that you are just repeating what the article was saying. Of course T-Wand is Wand, but you miss the technical contribution of T-Wand, which is clearly laid out in "What's new in T-Wand" section of the article. Of course, it is understandable if you are not able to judge the merit of that contribution, for that's the job of the peer review panel, which I do not expect Hacker News readers to be. This work will be submitted to a peer reviewed conference with more experiments added and all trade-offs discussed.
This may come as a disappointment to some, but the paper will not have a comparison with Lucene, for it would be scientifically unsound.
However, it should be easy for Lucene to add T-Wand as an option, and I do hope so.
I highlighted some other problems related to the Lucene benchmark, but since I can't program in Clojure I can't fix them with a PR: I opened 3 issues to describe what can be done to address them.
To be honest, all your proposed changes would not make material difference, for algorithmic differences cannot be made up by implementation details.
As has already been demonstrated, T-Wand is implemented in a much slower language, Clojure. Clojure is implemented on top of JVM, it cannot possibly beat the same algorithm written in optimized Java. The only way to make a difference is to change the algorithm. So all your suggestions would not make a difference.
If you do not learn this now, your managers who maybe only has an associate degree from a community college, or from a school you look down on, will make you learn that soon enough.
These are not important things. An important thing is to keep an open mind and keep learning, so you are continuously employable. You can congratulate yourself when you are as old as me and can still do new things.
This is not an isolated case. They rejected some industry changing contributions when they first came out.
For example, I remember that Google PageRank paper was outright rejected by SiGIR. Lucky for us, that paper was rejected, shattering the dream of an easy academia career for the two Google founders. Otherwise, we would probably still be searching with hotbots (remember that?).
The WAND paper was published in CIKM, a lowly conference in some people's eyes, I guess that's not the first venue they tried to publish that work in, because I worked at IBM Research before, I knew for a fact that CIKM was not in the first tier of the venues to publish, definitely not for the IR PIC.
Very interesting. I wonder what have caused this. My wild guess is that this may has something to do with early mistreatment the pioneering IR people received from the wider CS community, because their field was probably considered "soft" and not hard enough. For instance, even today, IR papers are not full of theorems and proofs, unlike some other CS fields, such as database. Their revengeful attitude got passed down to their students, as we can see here. And their reasons for dismissing other people's work are all the same: this is not new, we have done this before. But you have not, because the proof is in the systems you build and the papers you publish.
It does not have to be this way. HCI is even softer, but HCI is the most open field in CS, anyone can publish, you can prove theorems, or you can present user studies, anything goes. Funding? Not a problem. Because it is so open, HCI can work with anyone and on any projects. I remember that my advisor had so much funding, he basically paid me to whatever I wanted when I was in school. I am deeply in gratitude for that openness.