1

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

Cardin
  • 113
  • 4
  • 1
    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. – Hoc Ngo Apr 20 '17 at 06:50
  • 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$. – Cardin Apr 20 '17 at 06:51
  • @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. – Cardin Apr 20 '17 at 06:53
  • 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. – David Apr 20 '17 at 07:03
  • $u_t$ is very small because it refers to "term occurrence in non-relevant documents", and relevant documents are very sparse – Lazy Lee Apr 20 '17 at 07:04

1 Answers1

2

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}$$

Lazy Lee
  • 3,631
  • 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! – Cardin Apr 20 '17 at 07:24
  • 1
    Glad to help! I'm also interested in information retrieval so it was cool to read a bit about it :) – Lazy Lee Apr 20 '17 at 07:26
  • Good work, Lazy Lee! – Hoc Ngo Apr 20 '17 at 08:07