I'm investigating a problem I bet some of you have hit before, and exploring
several options to address it. I suspect that this specific IDF scenario is
common enough that it even has a name, though I'm not what it would be
called.
The scenario:
Suppose you have a search application focused on the products that you sell:
* You initially launch with just one product area for your "widget".
* You add a stop words list for really common words, say "a", "the", "and",
etc.
Looking at the search logs you discover:
* Other common English words being used, such as "i", "how" and "can".
These are automatically getting low IDF scores, since they are also common
in your documents, so normally you wouldn't worry.
* But you also notice that the words "widget" is getting a very low score,
since it is mentioned in virtually every document. In fact, since widget is
more common than the word "can", it is actually getting a *lower* IDF score
than the word "can", giving some very unsatisfying search results.
Some queries include other "good" words like "replace" and "battery", so
those searches are doing OK; those terms are relatively rare, so they
properly get the most weight.
But some searches have nothing but "bad" words, for example "how can I get a
widget ?"
* The word "a" is stopped out.
* The words "how", "can", "i" and "get" are common English words, so they
get a low score.
* And the word "widget", your flagship product, is also getting a low score,
since it's in every document.
So some queries are ENTIRELY composed of "low quality" words, and the search
engine gives somewhat random results.
Some ideas to address this:
Idea 1: Do nothing to IDF and just deploy the content for OTHER products
ASAP; the IDF logic will automatically fix the problem.
With content only about widgets, 100% of the docs have that score.
But if you deploy content for 9 more products, giving a total of 10
products, then only 1/10th of them will tend to have the word "widget". But
common English words will continue, on average, to appear in almost all
documents, across all product areas. Therefore they will continue to get
low scores. So relative to the words "i" and "can", the word "widget" will
automatically rise up out of the IDF muck.
And when content for all 100 of your products are deployed, "widget" will
again have been boosted even further, compared to other common English
words.
Though long term I have faith in this strategy, suppose I only had content
ready for two other products, say "cogs" and "hookas", so the term "widget"
will get a bit of a boost, but not by as much as I'd like.
Idea 2: Compare terms in product "slices" and artificially boost them.
In the Widget content there's references to related accessories like the
wBracket and wCase.
Whereas in the Hooka content, I rarely see mention of Widgets or wCases, but
I do still see the English terms "i" and "can", and lots of stuff about
Hookas.
2a: So I do a histogram for each of the 3 products, and look for terms that
are common in one but not in the others.
2b: Or I do a histogram of all terms, and then a histogram of terms for each
of the 3 product slices. And I compare those lists.
Of course we don't want to go overboard. If somebody is in the Widget forum
and asks "how do I change the widget battery?" then, although the term
Widget is more important than "how" or "do", it is NOT as important as
"battery" or "change", so I would not want to boost "widget" too much.
BTW, Solr facets makes this term info relatively easy to gather, thanks for
the pointer Yonik! 1.4 also speeds up Facets.
Idea 3: (possibly in conjunction with 2) Compare terms by product slice, and
do "complementary" IDF boosting.
In other words, it's very common for content on the Widget forum to have the
terms "widget", "wBracket" and "wcase".
But if a document in the "Cog" forum mentions "widget", that's actually
rather interesting. Mentions of "widgets" in the Cog and Hooka content
should be treated as "important", regardless of how common "widget" is in
the Widget forum.
So we compare the common terms in the Widget, Hooka and Cog areas. Terms
that are specific to Widgets get a bigger boost in the Cog and Hooka areas.
Cog terms get bigger boosts in Hooka and Widget areas, and Hooka terms get
extra credit in Cogs and Widgets.
This extra boosting could be done in addition to the minor boosting widget
terms get in the Widget area, just to keep them above the common English
terms.
Implementation of ideas 2 and 3:
This "diffing" of IDF by product slices would seem to be a good idea, though
a bit of coding to implement. I'd think somebody would have done this
already looked into this more formally?
In terms of implementation, you could do an arbitrary cutoff at 100 terms
for each product area, and then just do a Boolean for whether it appears in
the other lists or not. But after running some tests, common terms are
likely to mentioned in many lists, and it's more a question of where on the
list they were. For example, if you can interface Cogs and Widgets, then
Widget content will occasionally mention Cogs, and vice versa.
To me this seems like more of a Bayesian or Contingency Table issue, with
some weight given to the actual number of occurrences or the relative
position on lists. Any of you Brainiacs have specific insights?
There's also a question of scaling the Histogram. If I compare
term-in-document counts in the Widget area to the entire corpus, then since
there are fewer documents in the Widget area (it's a subset of the total),
then by definition the number of documents with the word "i" in that area
will be lower. You'd think the relative order wouldn't be affected, on
average, but any calculation using the occurrence counts would need to take
that into account. In other words, if the word "can" appears more times in
the overall documents than it does in the Widget documents, well is that
just because there are more documents in the overall set, or because "can"
is really more dense. Simple scaling can probably handle this issue...
Even if I compare Widget to Cog documents, both of which are subsets of the
total, there's likely to be a different number of documents in each area,
and therefore the counts would be different. So I'll get differences in
"how" and "can", in addition to "widget" and "cog", just because the sample
sizes are different. Again, scaling or limiting the sample size might fix
that too. Presumably the ranking of the words "i" and "can", which one is
more popular than the other, would stay the same regardless of sample size
and absolute counts, if I were looking at random English text. If those
terms change position, then that would be more interesting.
However, I think randomness also plays a role here. If I do a histogram of
100 Widget documents and only 5 Cog documents, and I notice that the
relative positions of "i" and "can" have changed places, I might be
skeptical that it's a random fluctuation because I only had 5 Cog
documents. If I added 50 more, would the difference still be there?
Sample size it certainly a well established topic in statistics, though I
haven't see it applied to histograms.
And another odd thing about histograms taken from different sample sizes are
the low frequency terms. In all search engine histograms you'll see terms
that appear only 1 time, and there'll be a bunch of them. But presumably if
I doubled the number of documents in the sample, some of those terms might
then appear twice, whereas others would still only appear once. There are
other breaks in histogram counts, like when it does from 2 to 1, that would
presumably also shift around a bit. But I'm not sure you can reliably use
sample size ration to scale these things with confidence. This feels like
Poisson distribution territory...
I suspect all of these questions have also been examined in detail before; I
need to dig up my copy of that "Long Tail" book... Wondering if anybody has
specific links or verbiage / author names to suggest?
There are certainly other ideas for indirectly addressing IDF problem by
using other methods to compensate:
4: You could overlay user reviews / popularity or click-through rates or
other social factors
5: Use flexible proximity searches, in addition to phrase matching, to boost
certain matches. Verity used to call this the "near" operator, Lucene/Solr
talk about span queries and "phrase slop".
So in a question containing "how can I", documents with that exact phrase
get a substantial boost. But documents where "how", "can" and "I" appear
within 5 words of each other in any order get also get a small boost. It's
been suggested that this can help with Q&A type applications.
6: FAST's doc mentions that verbs can be more important in question and
answer type applications. Normally nouns are said to contain 60-70% of the
relevance of a query (reference?), but their linguistics guide suggests
verbs are more important in Q and A apps.
7: Another idea would be to boost word pairs using composite N-Gram tokens,
what Lucene and Solr call "shingles".
Using my previous examples:
Question: "How can I get a widget ?"
Normal index: "how", "can", "i", "get", "widget"
Shingles: "how_can", "can_i", "i_get", "get_widget"
Question: "How do I change the widget battery?"
Normal index: "how", "do", "i", "change", "widget", "battery"
Shingles: "how_do", "do_i", "i_change", "change_widget",
"widget_battery"
And both sets of tokens would be added to the index, in different fields,
and with possibly different boosts.
The idea being that tokens like "can_i" might be somewhat more statistically
significant than "can" and "i" by themselves. So at least in the first
question, which has all low quality words, the "can_i" might help a bit.
I'd appreciate any comments on these ideas from y'all, or perhaps names of
specific algorithms / authors.
--
Mark Bennett / New Idea Engineering, Inc. / mbenn...@ideaeng.com
Direct: 408-733-0387 / Main: 866-IDEA-ENG / Cell: 408-829-6513
