1
$\begingroup$

I encountered this approximation in an Information Retrieval textbook, where they approximated:

$$\log(\frac{1-u_t}{u_t})$$ to $$\log(\frac{1}{u_t})$$

where $u_t\in[0,1]$ (tending towards 1, aka the probability of a frequently occurring value).

I don't understand how they arrived at this value. I've tried pulling it apart into $\log(1-u_t) + \log(1/u_t)$, but $\log(1-u_t)$ approaches negative infinity when $u_t$ is large (~=1), which meant that term couldn't be ignored.

Does anyone have any idea?

approximation

$\endgroup$
5
  • 1
    $\begingroup$ The last formula clearly uses the fact that $u_t << 1$. I think the statement in the second bullet must have an error; it should not say $u_t$ is the probability of term occurrence in nonrelevant documents for a query. $\endgroup$
    – Hoc Ngo
    Apr 20 '17 at 6:50
  • $\begingroup$ I've thought about that, but it doesn't make sense. Because of the paragraph in the screenshot: assuming $relevance$ is a small % of N, then N can be used to approximate $irrelevance$. As $irrelevance = u_t$, we can assume $u_t$ should approach $1$. $\endgroup$
    – Cardin
    Apr 20 '17 at 6:51
  • $\begingroup$ @HocNgo I thought it doesn't make sense too, but I just wanted to confirm that either I was wrong, or the paragraph was wrong haha. I think I will just accept that the paragraph is wrong then. $\endgroup$
    – Cardin
    Apr 20 '17 at 6:53
  • $\begingroup$ This makes sense for small $u_t \approx 0$ because by their Puiseux series (at $0$) we have $$\log\left(\frac{1-u_t}{u_t}\right) = -\log(u_t) - u_t + O(u_t^2)$$ and $$\log\left(\frac{1}{u_t}\right) = -\log(u_t) + O(u_t^2)$$ hence for small $u_t$ they are both approximately $$\log\left(\frac{1-u_t}{u_t}\right) \approx \log\left(\frac{1}{u_t}\right)\approx- \log(u_t).$$ As for $u_t \to 1,$ the assertion makes no sense. $\endgroup$
    – David
    Apr 20 '17 at 7:03
  • $\begingroup$ $u_t$ is very small because it refers to "term occurrence in non-relevant documents", and relevant documents are very sparse $\endgroup$
    – Lazy Lee
    Apr 20 '17 at 7:04
2
$\begingroup$

I searched through Google and think you are talking about page 227 in this, so I'll base my response on the information there. Because relevant documents are a small percentage, the probability that you find a term you are looking for inside a non-relevant document is very small, so$$u_t = \frac{df_t}{N}\ \ \text{is very small}\implies \frac{N}{df_t} \ \ \text{is very large}$$ Hence, $$\log\frac{1-u_t}{u_t}=\log\frac{N-df_t}{df_t}=\log\left(\frac{N}{df_t}-1\right)\approx \log\frac{N}{df_t}$$

$\endgroup$
3
  • $\begingroup$ Ohhh I get it now. The way it was phrased tripped me up. But your explanation made more sense. It wasn't about "all" terms, but about terms that "you are looking for". Since relevant documents are sparse, the desired terms are sparse. So irrelevant documents naturally have fewer occurrences of an already sparse term, making $u_t$ really small. Your equation also made it v.clear how the approximation works. Thanks thanks! $\endgroup$
    – Cardin
    Apr 20 '17 at 7:24
  • 1
    $\begingroup$ Glad to help! I'm also interested in information retrieval so it was cool to read a bit about it :) $\endgroup$
    – Lazy Lee
    Apr 20 '17 at 7:26
  • $\begingroup$ Good work, Lazy Lee! $\endgroup$
    – Hoc Ngo
    Apr 20 '17 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.