Harter's 2-Poisson model of Information Retrieval is a univariate model of the raw term frequencies, that does not condition the probabilities on document length [2]. A bivariate stochastic model is thus introduced to extend Harter's 2-Poisson model, by conditioning the term frequencies of the document to the document length. We assume Harter's hypothesis: the higher the probability f (X = xjL = l) of the term frequency X = x is in a document of length l, the more relevant that document is. The new generalization of the 2-Poisson model has 5 parameters that are learned term by term through the EM algorithm over term frequencies data.
We explore the following frameworks: p^
In order to define the bivariate 2-Poisson model we need first to remind the definition of a bivariate Poisson model, that can be introduced in several ways, for example as limit of a bivariate binomial, as a convolution of three univariate Poisson distributions, as a compounding of a Poisson with a bivariate binomial. We find that the trivariate reduction method of the convolution more convenient to easily extend Harter’s 2-Poisson model to the bivariate case. Let us consider the random variables Z1; Z2; Z3 distributed according to Poisson distributions P ( i), that is: p(Zi = xj i) = e
x i i
x! and the random variables X = Z1 + Z3 e Y = Z2 + Z3 distributed according to a bivariate Poisson distribution, BP ( ), where = ( 1; 2; 3):
x y min(x;y) p(X = x; Y = yj ) = e ( 1+ 2+ 3) 1 2 X x! y! x i y i i!
3 with covariance Cov(X; Y ) = 3.
Let us now consider the mixture 2BP ( 1; 2; ), where ( 21; 22; 32), of two bivariate Poisson distributions p(x; yj 1; 2; ) =
BP(
) BP(
P( 11 + 13) + (1
P( 12 + 13) + (
Moreover, we want x to be distributed as a 2-Poisson and L to be distributed as a Poisson. By assuming 12 = 22 = 2 and 13 = 23 = 3 we obtain p(xj 1; 2; ) = p(L j 1; 2; ) =
P( 11 + 3) + (1
) P( 21 + 3) = 2P( 11 + 3; 12 + 3)
P( 2 + 3) + (
) p2(x; L j 12; 2; 3) =
BP( 11; 2; 3) + (
Given a set of observations X = fx1; : : : ; xng, with xi = (xi; li), we wish to apply maximum likelihood to estimate the set of parameters of a bivariate Poisson distribution p(xj ) fitting such data. We wish to derive the value of by maximizing the log-likelihood, that is computing n = arg max log L( jX ) = arg max log Y p(xij ) i=1 and the set of parameters is
2. 3.1
In our case (see also [1]), we are interested to a mixture of 2 Bivariate Poisson with latent variables Z1; Z12; Z2; Z3, since with respect to the general case we have now Z21 = Z22 = Z2 1 and Z31 = Z32 = Z3. Then, for each observed pair of values xi = (xi; li), wi = 1 if xi is generated by the first component, and wi = 2 if generated by the second one. Accordingly: zi = (zi11; zi21; zi2; zi3) are such that xi = zi11 + zi3 if wi = 1 zi21 + zi3 if wi = 2 and li = zi2 + zi3 EM algorithm requires, in our case, to consider the complete dataset (X ; Z ) = f(x1; z1; w1) ; : : : ; (xn; zn; wn)g = (k) = n1 Xn pi(k 1) where pi(k 1) = (k 1)p(xij 1k 1) (k 1)) + (1 (k 1)p(xij 1
(k 1)) (k 1))p(xij 2 and p is the Bivariate Poisson with parameters 1(k) = 1
Pin=1 b11i(k 1)pi(k 1)
Pn (k 1)
i=1 pi (2k) = n1 Xn b2i(k 1) 2(k) = 1 (3k) = n1 Xn b3i(k 1)
i=1 Pn 2 (k 1)(1 i=1 b1i
Pn i=1(1
pi(k 1)) pi(k 1)) 3.2
We can show that the expectations bj1i(k) and bhi(k) are: min (xi;li)
X b3i(k) = =
r=0 min (xi;li)
X
(1 r r=0 r p(Z3 = rjxi; ) where (k) = )p(Z3 = r; xijW = 2; (k)) + p(xij (k)) p(Z3 = r; xijW = 1; (k)) 1 (k) = E[X1jW = 1; xi] b1i 2 (k) = E[X jW = 2; xi; (k)] b1i
E[Z3jW = 1; xi] = xi b3i 1 (k) E[Z3jW = 2; xi; (k)] = xi p(Z3 = r; xijW = j; (k)) = P0(rj 3(k)) P0(x j (k) rj 1 and P0 is the univariate Poisson, p(xij (k)) is the mixture of the bivariate Poisson. Efficient implementation of the bivariate Poisson through recursion can be found in [4]. 4
We have implemented the EM algorithm for the univariate 2-Poisson and we are currently extending the implementation to the bivariate case.
The implementation will be soon available together with the results of the experimentation at the web site http://tinyurl.com/cfcm8ma.