0
$\begingroup$

I probably should post this to comsci/cstheory, but since the part I am stuck at is mostly about deriving the probability term, so I am posting this here.

Given

$$\begin{align} query, \vec{q} & = \langle x_1, x_2, \ldots, x_t\rangle\\ document, \vec{x} & = \langle x_1, x_2, \ldots, x_t\rangle\\ \\ p_t & = P(x_t=1|R=1,\vec{q})\\ u_t & = P(x_t=1|R=0,\vec{q})\\ \end{align}$$

So I have this (is this called Naive Bayes conditional independence assumption?)

$$O(R|\vec{x}, \vec{q}) = O(R|\vec{q}) \cdot \prod\limits_{t:x_t=q_t=1} \frac{p_t}{u_t} \cdot \prod\limits_{t:x_t=0,q_t=1}\frac{1-p_t}{1-u_t}$$

and in the next step, it becomes this

(quoted from Introduction to Information Retrieval, by Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze)

We can manipulate this expression by including the query terms found in the document into the right product, but simultaneously dividing through by them in the left product, so the value is unchanged. Then we have:

$$O(R|\vec{x}, \vec{q}) = O(R|\vec{q}) \cdot \prod\limits_{t:x_t=q_t=1} \frac{p_t(1-u_t)}{u_t(1-p_t)} \cdot \prod\limits_{t:q_t=1}\frac{1-p_t}{1-u_t}$$

So the question is how do I transform the part from

$$\prod\limits_{t:x_t=0,q_t=1}\frac{1-p_t}{1-u_t}$$

to

$$\prod\limits_{t:q_t=1}\frac{1-p_t}{1-u_t} \cdot X$$

and what is the $X$ so that it has to be divided in another term to maintain equality?

$$\prod\limits_{t:x_t=q_t=1} \frac{p_t(1-u_t)}{u_t(1-p_t)}$$

$\endgroup$
1
$\begingroup$

I assume that $x_t$ can only get the values 0 and 1.

You have the expression:

$$\prod_{t: x_t=q_t=1}\frac{p_t}{u_t}\prod_{t:x_t=0,q_t=1}\frac{1-p_t}{1-u_t}$$

And you want to find out how is it transformed to

$$\prod_{t: x_t=q_t=1}\frac{p_t}{u_t}\frac{1-u_t}{1-p_t}\prod_{t:q_t=1}\frac{1-p_t}{1-u_t}.$$

The answer is quite simple. Take term

$$\prod_{x_t=q_t=1}\frac{1-u_t}{1-p_t}\frac{1-p_t}{1-u_t}.$$

It is equal to 1. Split it into two parts:

$$\prod_{x_t=q_t=1}\frac{1-u_t}{1-p_t}\prod_{x_t=q_t=1}\frac{1-p_t}{1-u_t}.$$

Since it is equal to one, you can multiply the first expression by it without changing it:

\begin{align} &\prod_{t: x_t=q_t=1}\frac{p_t}{u_t}\prod_{t:x_t=0,q_t=1}\frac{1-p_t}{1-u_t}=\\ &\prod_{t: x_t=q_t=1}\frac{p_t}{u_t}\prod_{t:x_t=0,q_t=1}\frac{1-p_t}{1-u_t} \prod_{x_t=q_t=1}\frac{1-u_t}{1-p_t}\prod_{x_t=q_t=1}\frac{1-p_t}{1-u_t}=\\ &\prod_{t: x_t=q_t=1}\frac{p_t}{u_t}\prod_{x_t=q_t=1}\frac{1-u_t}{1-p_t}\prod_{t:x_t=0,q_t=1}\frac{1-p_t}{1-u_t}\prod_{x_t=q_t=1}\frac{1-p_t}{1-u_t}=\\ &\prod_{t: x_t=q_t=1}\frac{p_t}{u_t}\frac{1-u_t}{1-p_t}\prod_{t:q_t=1}\frac{1-p_t}{1-u_t}. \end{align}

Here I used the following two properties of multiplication:

$$\prod_{i\in I}a_i\prod_{i\in I}b_i=\prod_{i\in I}a_ib_i,$$

and

$$\prod_{i\in I}a_i\prod_{i\in J}a_i=\prod_{i\in I\cup J}a_i,$$

where $I$ and $J$ are disjoint index sets and $a_i, b_i$ are objects which can be multiplied and multiplication is associative and commutative.

$\endgroup$
  • $\begingroup$ erm, how do u get the second part? how $\prod\limits_{x_t=0,q_t=1}\frac{1-p_t}{1-u_t}$ becomes $\prod\limits_{x_t=q_t=1}\frac{1-p_t}{1-u_t}$? yea, $x_t$ can be either 0 or 1 $\endgroup$ – Jeffrey04 Sep 24 '15 at 6:32
  • 1
    $\begingroup$ $x_t=0, q_t=1$ does not become $x_t=q_t,q=1$. They both become $q_t=1$. $\endgroup$ – mpiktas Sep 24 '15 at 6:34
  • $\begingroup$ thx for the prompt reply, still need some time to really get the idea. $\endgroup$ – Jeffrey04 Sep 24 '15 at 6:37
  • 1
    $\begingroup$ Suppose there are only two indexes $t=1,2$, with $x_1=0, q_1=1$ and $x_2=1, q_1=1$. Then condition $q_t=1$ captures both indexes $1$ and $2$, since $x$ can be only zero and one. $\endgroup$ – mpiktas Sep 24 '15 at 6:49

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.