5 ms·

The next step is usually to use tf-idf or bm25 to rank the matches https://en.m.wikipedia.org/wiki/Tf%E2%80%93idf https://en.m.wikipedia.org/wiki/Tf%E2%80%93idf

by make3 6y ago

The next step is usually to use tf-idf or bm25 to rank the matches https://en.m.wikipedia.org/wiki/Tf%E2%80%93idf https://en.m.wikipedia.org/wiki/Tf%E2%80%93idf https://en.m.wikipedia.org/wiki/Okapi_BM25 https://en.m.wikipedia.org/wiki/Okapi_BM25

kristopolous 6y ago
I've always found these things push poor quality results to the top. The merits it ranks upon are redundancy and repetition. They are the "next thing taught" but they aren't useful
- boyter 6y ago
  What would you suggest then? Assuming you only have the term frequency values I cannot think of any other algorithm you can apply that gives reasonable results. Of course this breaks down as its easily gamed, but unless you are building a public search engine it should work. Heck tools like lucene/elasticsearch use tf/idf and bm25 although they can include vector space on top of the query as well.
  - kristopolous 6y ago
    The next thing should be talking about the different classes of documents and searches. Sometimes thesaurus searching is appropriate, sometimes it isn't. Sometimes removing logical modifiers (ex: not, excluding, etc) is appropriate and other times, not. Sometimes verbatim searching is right, sometimes not. Sometimes approximation searching is right, something it's not. For instance, I was on Amazon the other day and I was looking for bubble mailers, 8x12, 50 pcs ... I wasn't able to get amazon to exclude the other unit and lot sizes ... maybe that's the right answer sometimes. A "better" search system however, would see the numbers, know the frequency distribution of those values and present ranges for me to choose. Google has a focus ambiguity with a similar "one search" approach: it ignores more focused words to give you more generalized results. which might be the right answer sometimes ...and sometimes not. Here's another classification example: On Google books, when looking for say, "constitution" in older texts, OCR will sometimes misidentify it as "conftitution" because of the long-s in older typography. For this search, I shouldn't have to be manually searching both terms to get the results ... the search query in this case should do something different still, swap letters with common OCR missteps and then aggregate them into a single result. I ran my own OCR on documents and wrote a small python program to do this using Damerau–Levenshtein distance. It's not hard, could easily be taught to undergrads. Here's yet another example. let's say I have a garden and I found holes in say, my basil leaves and am trying to find bugs that may be causing that. In this search it would be fine to say "basil is an herb (that's the class of object to search), it finds that say, cabbage loopers eat mint, which is also an herb and returns those results" - this indirection is correct here, assuming these caterpillars eat both plants (they do). Now let's say I'm looking for a recipe with my basil plant and it uses the same indirection logic and returns mint recipes. Or I'm looking for songs by Toni Basil and I get Toni Thyme and Toni Lavender in the results ... now it's the wrong decision. Here's another example: suicide by tylenol overdose is common and prompt medical care is extremely important. Often people mix up the terms "aspirin" and "tylenol" and many use them interchangably, big mistake here. Pretend someone finds their friend passed out and incorrectly searches on the web, "aspirin overdose". It doesn't look like it is life-threatening meanwhile the time is ticking. The engine should be saying "yo, are you sure it isn't tylenol? that'll kill you". Getting that right (similar terms, far more common event, extremely dangerous) requires multiple of the above systems I spoke of combined together. Sometimes right, sometimes wrong. Anyway, multi-method classifications of documents and search intents, totally the next step.
    - boyter 6y ago
      Got any papers that go though this in terms of pros/cons and such? While I agree with you I have to wonder given what a lot of people have in terms of search problems are easily solve-able though the use of tf/idf or bm25 because it improves where they are starting to a level thats often good enough.
      - kristopolous 6y ago
        I don't have a doctorate and I'm not an academic. Let me try to be helpful. IDF is old, like 1950s-1970s for most of the work. You have to put things in context. Digital storage was for surveys and structured documents; things that could be computed upon. Wasting computers for literature and opinions wasn't part of the application space. Why would you be storing newspaper opinion columns on your univac? So if we are looking at say, demographic population surveys, essentially almanac data, then IDF serves you well. If I was searching "Duluth", then the document concerning the measurements taken in Duluth will have that word in it frequently. Academically there's something called a "Zipfian" distribution and some math to back it up, but I have very little confidence in my mathematical formalism skills (been working on it for 20 years, still not very good) so excuse me for skipping over it. The pros/cons appear in "application" sections when describing a technique. You can find these on wikipedia. Here's wikipedia's category on it: https://en.wikipedia.org/wiki/Category:Information_retrieval_techniques https://en.wikipedia.org/wiki/Category:Information_retrieval... I think, as a whole, we've understated the human interface problem in search. There's some technical tools that if are exposed and used can dramatically improve results. For instance, a swap operator. In some of my search systems I permit a syntax: "s(phrase[0]:...:phrase[n])" That's because sometimes you can have a phrase say "x y z" where "z y x" and "x z y" are common but have different meanings and you only want a subset. Then you have polysemy and homonomy ... so sometimes you want an exact terms, sometimes you want to fuzzy search, sometimes you want a collection of exact terms. So we can do exact with say "=", collection with a "|" and so on... 's(=x:y0|y1|y2:z)"' Now pretend you also want a range in there: 's(=x:y0|y1a..y1z|y2:z)' and so on. This syntax is also quite fast to process. You can permute all the elements without too much effort, look them up, and aggregate the results in very little time but we are really starting to get into a RegEx like query system which means a decent amount of technical knowledge is needed and that's where we have the interface problem. These systems are relatively easy to code and run on modest hardware (as in, something you can easily fit under a desk) but require more from the user - a level that frankly you just aren't going to get, let's be real here. I've found lots of otherwise competent programmers who struggle with say regex and bpf, I think I have some natural talent there that is not super common. This is an example of why I think search is maybe, 50% a human interface problem.
- chudi 6y ago
  the next next step is using something like learning to rank algorithms to try get better results!

by make3 6y ago

kristopolous 6y ago

I've always found these things push poor quality results to the top. The merits it ranks upon are redundancy and repetition. They are the "next thing taught" but they aren't useful

boyter 6y ago
What would you suggest then? Assuming you only have the term frequency values I cannot think of any other algorithm you can apply that gives reasonable results. Of course this breaks down as its easily gamed, but unless you are building a public search engine it should work. Heck tools like lucene/elasticsearch use tf/idf and bm25 although they can include vector space on top of the query as well.
- kristopolous 6y ago
  The next thing should be talking about the different classes of documents and searches. Sometimes thesaurus searching is appropriate, sometimes it isn't. Sometimes removing logical modifiers (ex: not, excluding, etc) is appropriate and other times, not. Sometimes verbatim searching is right, sometimes not. Sometimes approximation searching is right, something it's not. For instance, I was on Amazon the other day and I was looking for bubble mailers, 8x12, 50 pcs ... I wasn't able to get amazon to exclude the other unit and lot sizes ... maybe that's the right answer sometimes. A "better" search system however, would see the numbers, know the frequency distribution of those values and present ranges for me to choose. Google has a focus ambiguity with a similar "one search" approach: it ignores more focused words to give you more generalized results. which might be the right answer sometimes ...and sometimes not. Here's another classification example: On Google books, when looking for say, "constitution" in older texts, OCR will sometimes misidentify it as "conftitution" because of the long-s in older typography. For this search, I shouldn't have to be manually searching both terms to get the results ... the search query in this case should do something different still, swap letters with common OCR missteps and then aggregate them into a single result. I ran my own OCR on documents and wrote a small python program to do this using Damerau–Levenshtein distance. It's not hard, could easily be taught to undergrads. Here's yet another example. let's say I have a garden and I found holes in say, my basil leaves and am trying to find bugs that may be causing that. In this search it would be fine to say "basil is an herb (that's the class of object to search), it finds that say, cabbage loopers eat mint, which is also an herb and returns those results" - this indirection is correct here, assuming these caterpillars eat both plants (they do). Now let's say I'm looking for a recipe with my basil plant and it uses the same indirection logic and returns mint recipes. Or I'm looking for songs by Toni Basil and I get Toni Thyme and Toni Lavender in the results ... now it's the wrong decision. Here's another example: suicide by tylenol overdose is common and prompt medical care is extremely important. Often people mix up the terms "aspirin" and "tylenol" and many use them interchangably, big mistake here. Pretend someone finds their friend passed out and incorrectly searches on the web, "aspirin overdose". It doesn't look like it is life-threatening meanwhile the time is ticking. The engine should be saying "yo, are you sure it isn't tylenol? that'll kill you". Getting that right (similar terms, far more common event, extremely dangerous) requires multiple of the above systems I spoke of combined together. Sometimes right, sometimes wrong. Anyway, multi-method classifications of documents and search intents, totally the next step.
  - boyter 6y ago
    Got any papers that go though this in terms of pros/cons and such? While I agree with you I have to wonder given what a lot of people have in terms of search problems are easily solve-able though the use of tf/idf or bm25 because it improves where they are starting to a level thats often good enough.
    - kristopolous 6y ago
      I don't have a doctorate and I'm not an academic. Let me try to be helpful. IDF is old, like 1950s-1970s for most of the work. You have to put things in context. Digital storage was for surveys and structured documents; things that could be computed upon. Wasting computers for literature and opinions wasn't part of the application space. Why would you be storing newspaper opinion columns on your univac? So if we are looking at say, demographic population surveys, essentially almanac data, then IDF serves you well. If I was searching "Duluth", then the document concerning the measurements taken in Duluth will have that word in it frequently. Academically there's something called a "Zipfian" distribution and some math to back it up, but I have very little confidence in my mathematical formalism skills (been working on it for 20 years, still not very good) so excuse me for skipping over it. The pros/cons appear in "application" sections when describing a technique. You can find these on wikipedia. Here's wikipedia's category on it: https://en.wikipedia.org/wiki/Category:Information_retrieval_techniques https://en.wikipedia.org/wiki/Category:Information_retrieval... I think, as a whole, we've understated the human interface problem in search. There's some technical tools that if are exposed and used can dramatically improve results. For instance, a swap operator. In some of my search systems I permit a syntax: "s(phrase[0]:...:phrase[n])" That's because sometimes you can have a phrase say "x y z" where "z y x" and "x z y" are common but have different meanings and you only want a subset. Then you have polysemy and homonomy ... so sometimes you want an exact terms, sometimes you want to fuzzy search, sometimes you want a collection of exact terms. So we can do exact with say "=", collection with a "|" and so on... 's(=x:y0|y1|y2:z)"' Now pretend you also want a range in there: 's(=x:y0|y1a..y1z|y2:z)' and so on. This syntax is also quite fast to process. You can permute all the elements without too much effort, look them up, and aggregate the results in very little time but we are really starting to get into a RegEx like query system which means a decent amount of technical knowledge is needed and that's where we have the interface problem. These systems are relatively easy to code and run on modest hardware (as in, something you can easily fit under a desk) but require more from the user - a level that frankly you just aren't going to get, let's be real here. I've found lots of otherwise competent programmers who struggle with say regex and bpf, I think I have some natural talent there that is not super common. This is an example of why I think search is maybe, 50% a human interface problem.
chudi 6y ago
the next next step is using something like learning to rank algorithms to try get better results!