of the current state to estimate parameters of the next state. In particular, each next-state parameter is sampled from the posterior distribution of that parameter given all other parameters in the previous state. The sampling process is done sequentially until sampled parameters approach the target posterior distributions. Recently, this approach was demonstrated to be simple to implement, yet competitively efficient, and to yield relatively good performance on the topic extraction task [Griffiths and Steyvers 2004; Rosen-Zvi et al. 2004].

Since we use Dirichlet priors, it is straightforward to integrate out ψ, φ and θ. Thus, we only need to sample hidden variables x and z and later on estimate ψ, φ and θ once x and z approach their target posterior distribution. To derive Gibbs sampling formula for sampling x and z, we first assume that all bookmarks are broken into NK tuples. Each tuple is indexed by i and we refer to the observable variables, resource, user and tag, of the tuple i as ri, ui, ti. We refer to the hidden variables, topic and interest, for this tuple as zi and xi respectively, with x and z representing the vector of interests and topics over all tuples.

We define Nri,z−i as the number of all tuples having r = ri and z but excluding the present tuple i. In words, if z = zi, Nri,z−i = Nri,zi − 1; otherwise, Nri,z−i = Nri,zi
.

Similarly, Nz−i,xi,ti is a number of all tuples having x = xi, t = ti and z but excluding the present tuple i; z−i represents all topic assignments except that of the tuple i. The Gibbs sampling formulas for sampling z and x, whose derivation we provide in the Appendix, are as follows.

$$p(z_{i}|\mathbf{z}_{-i},\mathbf{x},\mathbf{t})=\frac{N_{r_{i},z_{-i}}+\alpha/N_{Z}}{N_{r_{i}}+\alpha-1}.\frac{N_{z_{-i},x_{i},t_{i}}+\eta/N_{T}}{N_{z_{-i},x_{i}}+\eta}\tag{1}$$  $$p(x_{i}|\mathbf{x}_{-i},\mathbf{z},\mathbf{t})=\frac{N_{u_{i},x_{-i}}+\beta/N_{X}}{N_{u_{i}}+\beta-1}\cdot\frac{N_{x_{-i},z_{i},t_{i}}+\eta/N_{T}}{N_{x_{-i},z_{i}}+\eta}\tag{2}$$

Consider Eq. (1), which computes a probability of a certain topic for the present tuple.

This equation is composed of 2 factors. Suppose that we are currently determining the probability that the topic of the present tuple i is j (zi = j). The left factor determines the probability of topic j to which the resource ri belongs according to the present topic distribution of ri. Meanwhile, the right factor determines the probability of tag ti under the topic j of the users who have interest xi. If resource ri assigned to the topic j has many tags, and the present tag tiis "very important" to the topic j according to the users with interest xi, there is a higher chance that tuple i will be assigned to topic j. A similar insight is also applicable to Eq. (2). In particular, suppose that we are currently determining the probability that the interest of the present tuple i is k (xi = k). If user ui assigned to the interest k has many tags, and tag tiis "very important" to the topic zi according to users with interest k, the tuple i will be assigned to interest k with higher probability.

In the model training process, we sample topic z and interest x in the current iteration using their assignments from the previous iteration. By sampling z and x using Eq. (1)
and Eq. (2) for each tuple, the posterior distribution of topics and interests is expected to converge to the true posterior distribution after enough iterations. Although it is difficult to assess convergence of Gibbs sampler in some cases as mentioned in [Sahu and Roberts 1999], we simply monitor it through the likelihood of data given the model, which measures how well the estimated parameters fit to the data. Once the likelihood reaches the ACM Journal Name, Vol. x, No. y, zz 2010.