Topic Tracking Model for Analyzing Consumer Purchase Behavior

1 Introduction

Modeling consumer purchase behavior in e-commerce is an important task, because it enables online stores to provide recommendations, personalized advertisements, and perform trend analyses. Recently there has been great interest in analyzing discrete data using topic models, where the discrete data are mainly text corpora but also include human behavior log data [Jin et al., 2004; Das et al., 2007]. A topic model is a hierarchical Bayesian model, in which a user (document) is modeled as a mixture of topics, where a trend in a topic is modeled as a purchase probability distribution over catalog items (words). However, traditional topic models do not fulfill two important requirements for modeling consumer behavior in online stores. The first is the adaptability to changes. Consumer interests and item trends change over time for a variety of reasons. The second is the ease with which incremental model updates can be achieved. Huge amounts of data are accumulated every day in real online stores.

In this paper, we propose a topic model, which we call the Topic Tracking Model (TTM), that satisfies the above two requirements. With TTM, interests for each consumer and trends for each topic are sequentially inferred using newly obtained data and previously estimated interests and trends. The computational cost and the memory requirement of TTM are low because past data are not required for the inference and need not be stored.

The persistency of interests differs among consumers. Some consumers significantly change their interests and some do not. Furthermore, it also differs according to periods. There may be periods during which a consumer's interests change greatly and there may also be long periods when these interests remain unchanged. Therefore, we need to infer the interest persistency for each consumer and for each time period. We also infer the trend persistency for each topic and for each time period because it differs among topics and over time according to new releases of items, seasons, and social and economic environments.

Probabilistic Latent Semantic Analysis (PLSA) [Hofmann, 1999] and Latent Dirichlet Allocation (LDA) [Blei et al., 2003] are two representative topic models. However, these models assume that samples are exchangeable, and therefore they cannot capture the dynamics. More recently, topic models with dynamics, such as the Dynamic Topic Model (DTM) [Blei and Lafferty, 2006], Dynamic Mixture Model (DMM) [Wei et al., 2007], and Topic over Time (ToT) [Wang and McCallum, 2006], have been proposed. TTM has an advantage over the other models in its adaptability to changes because TTM models dynamics of both interests and trends, and it infers their persistency for each time interval from the given data.

In the rest of this paper, we assume that the given data are purchase logs. However, our method is applicable to a wide range of human behavior data with timestamps, such as web access log, blog, e-mail and discourse data.

2 Preliminaries

The goal of this paper is to estimate the probability that user u purchases item i at time t, P(i|u, t), which represents the purchase behavior of user u, where u ∈ {1, · · · , U} is a user index, and i ∈ {1, · · · , I} is an item index. We assume that t is a discrete variable, and we can set the unit time interval arbitrarily at, for example, one day or one week.

In topic modeling, P(i|u, t) is obtained by the following equation with the assumption of the conditional independence of u and i given latent topic z,

where Z is the number of topics, φt,u,z = P(z|u, t) represents the interests of a user, which is the probability that user u is interested in topic z at time t, where φt,u,z ≥ 0, ∑z φt,u,z = 1, and θt,z,i = P(i|z, t) represents trends in a topic, which is the probability that item i is selected and purchased from topic z at time t, where θt,z,i ≥ 0, ∑i θt,z,i = 1.

In LDA, interests φt,u = {φt,u,z}Zz=1 are assumed to have a Dirichlet prior as follows:

where γ = {γz}Zz=1 , γz > 0, is a set of Dirichlet parameters. In this assumption, current interests are independent of the past interests, and their dynamics are not incorporated.

3 Topic Tracking Model

To model the dynamics of user interests, we assume that the mean of the user interests at the current time are the same as those at a previous time unless otherwise confirmed by the newly observed data. In particular, we use the following Dirichlet prior, in which the mean of the current interests is the same as the mean of the previous interests ˆφt-1,u, and the precision is αt,u,

where Dirichlet parameters in (2) are factorized into the mean and precision γt,u,z = αt,u ˆ φt-1,u,z. The precision αt,u represents the interest persistency, which is a measure of how consistently user u maintains her interests at time t compared with those at t - 1. We estimate αt,u for each time period and for each user because the variability of interests depends on both time and user. Since this is a conjugate prior, the inference is simple as in LDA, which is a topic model without dynamics [Griffiths and Steyvers, 2004].

To model the dynamics of trends, we use the following Dirichlet distribution for the prior of trends θt,z = {θt,z,i}Ii=1 in the same way as interests,

where the mean is the previous trends ˆθt-1,z, and the precision is βt,z. This prior is also conjugate.

Let xt,u = {xt,u,m}Mt,u m=1 be a set of items purchased by user u at time t, where xt,u,m is the mth item purchased by user u at time t, and Mt,u is the number of items purchased by user u at time t. TTM assumes the following generative process for Xt = {xt,u}Uu=1 , which is a set of all items purchased by U users at time t,

1. For each topic z = 1, · · · , Z:
2. (a) Draw trends θt,z ∼ Dirichlet(βt,z ˆθt-1,z )
3. For each user u = 1, · · · , U:
4. (a) Draw interests φt,u ∼ Dirichlet(αt,u ˆφt-1,u)
5. (b) For each purchasem= 1, · · · ,Mt,u:
6. Draw topic
7. zt,u,m ∼ Multinomial(φt,u)
8. Draw item

xt,u,m ∼ Multinomial(θt,zt,u,m ).

As in LDA, each item xt,u,m is sampled from a topic-specific multinomial distribution.

Figure 1 (a) shows a graphical model representation of TTM, where shaded and unshaded nodes indicate observed and latent variables, respectively.

4 Inference

We estimate the parameters in TTM based on stochastic EM algorithm, in which Gibbs sampling of latent topics and maximum joint likelihood estimation of parameters are alternately iterated [Wallach, 2006].

Let t be the current time. Suppose that we have purchase logs Xt at the current time t, the mean of the previous interests ˆΦt-1 = { ˆφt-1,u}Uu=1 , and the mean of the previous trends ˆΘt-1 = { ˆθt-1,z}Zz=1 . By using these data and parameters, we estimate current interests Φt = {φt,u}Uu=1 and trends Θt = {θt,z}Zz=1 as well as interest persistencies αt = {αt,u}Uu=1 and trend persistencies βt = {βt,z}Zz=1.

We infer latent topics based on the collapsed Gibbs sampling [Griffiths and Steyvers, 2004], in which the joint distribution of data and latent topics is required. Let Zt = {zt,u}Uu=1 be a set of latent topics of all users at time t, and zt,u = {zt,u,m}Mt,u m=1 . Since we use conjugate priors for parameters Φt and Θt, we can integrate out the parameters in the joint distribution as follows:

where nt,u,z is the number of items purchased by user u at time t that have been assigned to topic z, nt,z,i is the number of times item i has been assigned to topic z at time t, and Γ(x) is the gamma function.

The assignment of a latent topic is estimated using the following equation, which is calculated from (5),

where j = (t, u,m), and \j represents a count that does not include a purchase j.

The persistency parameters αt and βt are estimated by maximizing the joint distribution (5). The following updating rules for maximizing the joint distribution are derived by using the bounds in [Minka, 2000],

where At,u,z = Ψ(nt,u,z + αt,u ˆ φt-1,u,z ) - Ψ(αt,u ˆ φt-1,u,z ), and Ψ(·) is the digamma function defined by Ψ(x) = ∂ log Γ(x) ∂x , and,

where Bt,z,i = Ψ(nt,z,i +βt,z ˆ θt-1,z,i)-Ψ(βt,z ˆ θt-1,z,i). By iterating Gibbs sampling with (6), and maximum likelihood estimation with (7) and (8), we can estimate latent topics Zt, and parameters αt and βt.

After the iterations, the means of φt,u,z and θt,z,i are obtained as follows:

These estimates are used to estimate interests and trends at the next time period t + 1.

TTM uses only current data Xt (not past data) when inferring current interests Φt and trends Θt, Therefore, TTM can greatly reduce the computational cost compared with the conventional models that use past data. Moreover, TTM also reduces the memory requirement because past data need not be stored.

5 Capturing long term dependences

In the above discussion, we infer interests φt,u using an estimate of the previous interests ˆφt-1,u. However in practice, the interests of today may depend not only on the interests of yesterday but also on the interests of a week ago. Therefore, to capture the long term dependences, we modify the prior of interests φt,u so that it can depend on past L interests { ˆφt-l,u}Ll=1 as follows:

where the mean is proportional to the weighted sum of the past L interests of the user, and αt,u,l represents how the interests at t are related to the l-previous interests. The information loss is reduced by considering long term dependences. Furthermore, the bias of the inference is reduced by using multiple estimates. When we use only the previous interests, the inference might be biased because it depends on just one estimate.

In a similar fashion, we can also modify the prior of the trends θt,u so that it can depend on past L trends { ˆθt-l,u}Ll=1 in order to make the inference more robust as follows:

where the mean is proportional to the weighted sum of the past L trends of the topic, and βt,z,l represents how the trends at t are related to the l-previous trends. A graphical model of TTM with long term dependences is shown in Figure 1 (b).

Since the priors in (11) and (12) are still Dirichlet distributions and conjugate priors, the parameters Φt and Θt in the joint distribution can be integrated out as in (5). Therefore, the inference can be achieved by using a stochastic EM algorithm in the same way with the model described in the previous section. Each latent topic is sampled according to the following probability,

where αt,l = {αt,u,l}Uu=1 , and βt,l = {βt,z,l}Zz=1 . The update rule of weight αt,u,l is as follows:

where A′t,u,z = Ψ(nt,u,z + ∑l αt,u,l φt-l,u,z) - Ψ(∑l αt,u,l ˆ φt-l,u,z). The update rule of weight βt,z,l is as follows:

where B′t,z,i = Ψ(nt,z,i + ∑l βt,z,l ˆ θt-l,z,i) - Ψ(∑l βt,z,l ˆ θt-l,z,i). The means of φt,u,z and θt,z,i are obtained as follows:

These estimates are efficiently used for the inference from t + 1 to t + L.

6 Related work

Topic models with dynamics have been proposed recently. These include the Dynamic Topic Model (DTM) [Blei and Lafferty, 2006], Dynamic Mixture Model (DMM) [Wei et al., 2007], and Topic over Time (ToT) [Wang and McCallum, 2006]. A graphical model of DTM is shown in Figure 1 (c). DTM analyzes the time evolution of topics in document collections, in which a document is assumed to have only one timestamp. Therefore, DTM does not consider the dynamics in each document (user), and it cannot be used for modeling user behavior dynamics, which is the goal of this paper. Since DTM uses a Gaussian distribution for the dynamics, the inference is intractable owing to the nonconjugacy of the Gaussian and multinomial distributions, and it requires complicated variational approximations. In contrast to DTM, the inference of TTM is relatively simple because it uses Dirichlet distributions that are conjugate for multinomial distributions. A graphical model of DMM is shown in Figure 1 (d). DMM only considers a single dynamic sequence of documents, which corresponds to a single user over time. On the other hand, TTM considers multiple users with different dynamics as well as the dynamics of trends for multiple items in each topic, which is essential for analyzing consumer purchase behavior. Furthermore, DMM assumes that the interest persistency is fixed and known. Therefore, it is not appropriate for purchase logs, in which distributions sometimes change greatly, and are sometimes stable. ToT needs all the samples over time for the inference. Therefore, it cannot be updated sequentially, and is not appropriate for data that are continuously accumulated. Singular Value Decomposition (SVD) is also used for analyzing multiple timeseries [Papadimitriou et al., 2005] as well as topic models. However, since SVD implicitly assumes Gaussian noise, it is not appropriate for discrete data [Hofmann, 1999], such as text corpora and purchase logs.

TTM is related to the Kalman filter [Welch and Bishop, 1995] even though TTM deals with discrete variables and the Kalman filter deals with continuous variables. In the Kalman filter, since both the transition and emission distributions are Gaussian, and the conjugate distribution of the Gaussian is also Gaussian, the inference is tractable. On the other hand, with topic models, since the emission distribution is the multinomial, and the conjugate distribution of the multinomial is the Dirichlet, the inference in the same way is infeasible. DTM is inferred as with the Kalman filter by mapping the Gaussian to the multinomial using the softmax function. In contrast, TTM is inferred by assuming that the transition distribution is the Dirichlet, in which the mean is the previous mean of the multinomial, and the variance is adaptively estimated from the given data.

7 Experiments

We evaluated TTM using two real purchase log data sets consisting of movie and cartoon data. The movie data are the logs of a movie downloading service from May 14th to August 31st, 2007, in which the numbers of users, items, and transactions are 70,122, 7,469, and 11,243,935, respectively. The cartoon data are the logs of a cartoon downloading service for cell phones from January 1st to May 31st, 2006, in which the numbers of users, items, and transactions are 143,212, 206, and 12,642,505, respectively. We considered cartoons with different volumes to be the same item. We omitted items and users that appeared fewer than ten times. We set the unit time interval at one day.

For the evaluation measurement, we employed the N-best prediction accuracy of purchase items. We used data until the previous day t - 1 as training data to infer the model, and predicted purchase items at day t as test data. The probability that user u purchases item i at time t was calculated using the estimated parameters at the previous day, ˆΦt-1 and ˆΘt-1, as follows:

The N-best accuracy represents the percentage that the purchased items are contained in the set of N-highest P (x=i|u, t; ˆΦt-1 , ˆΘt-1) items.

In order to demonstrate the effectiveness of modeling the dynamics of interests and trends, we compared TTM with three topic models, LDAall, LDAonline, and LDAone, which are based on LDA. LDAall is an LDA that uses all the past data for inference. LDAonline is an online learning extension of LDA, in which the parameters are estimated using those of the previous day and the newly obtained data [Banerjee and Basu, 2007]. LDAone is an LDA that uses just the previous day data for inference. For a fair comparison, the hyper parameters in these LDAs were optimized using stochastic EM as described in [Wallach, 2006].

The N-best accuracies for movie and cartoon data sets averaged over time are shown in Table 1. TTM1 and TTM10

Table 1: Average N-best accuracies (%) over time. The digit in the bracket is the standard deviation.

(a) movie

represent the proposed topic tracking models, which use parameters of one- and ten-previous days, or L = 1 and L = 10, respectively. For both of the data sets, the highest accuracies are achieved by TTM10, and this result indicates that TTM10 can appropriately predict consumer behavior by considering dynamics and efficiently using information in the past data. The accuracies achieved by LDAall and LDAonline are low because they do not consider the dynamics. The reason for the low accuracy of LDAone is that it uses only current data and ignores the past information. The accuracies achieved by LDAall and LDAonline for the cartoon data are higher than that of LDAone because the cartoon data has smaller dynamics than the movie data. The high accuracies of TTM10 in both of the data sets that have different dynamics represent its high adaptability.

Figure 2 shows the average three-best accuracies of TTM with different dependent lengths L. The accuracy increased as L increased. This result implies that TTM became robust by using long term dependences. The accuracy saturated at around L = 7, and then slightly decreased possibly due to overfitting. Therefore, we can achieve high accuracy with these data sets by storing estimated parameters for a week. The three-best accuracies for movie and cartoon data sets for each day are shown in Figure 3. The accuracies varied with a period of seven days because new items are released every week, and the accuracies when new items were released were low.

Table 2 shows the daily average computational time when using a computer with a Xeon5355 2.66GHz CPU. The computational time for LDAonline, LDAone and TTM are roughly the same since they use the same number of samples for inference. The computational time for LDAall is long although its accuracy was the second highest for the cartoon data set since LDAall uses all samples for inference. Moreover, LDAall requires more memory than TTM. TTM10 processed data that consisted of over 100,000 transactions per day in about 12 minutes, and it can deal with the huge amounts of data that are observed in real online stores. Figure 4 shows the average computational time for TTM with different dependent lengths L. The computational time increases linearly with L. Note that the time for TTM is much smaller than that for LDAall even TTM with L = 10.

Figures 5 and 6, respectively, show the average α and β with different l values of TTM10. The sum of the values for each day and for each user or topic are normalized to one. The parameters decrease as l increases in the movie data set. This result implies that recent interests and trends are more informative as regards estimating current interests and trends, which is an intuitive result. In the cartoon data set, the parameters at l = 7 are high because the same cartoons with different volumes are released weekly.

Figure 7 shows some examples of estimated parameter β of TTM1 for each day with the movie data. The trends in a topic (red) have a high dependence on the previous trends, and the trends in a topic (green) have a low dependence on the previous trends. Even in a topic, the dependence changes day by day. For example, in a topic (red), the dependence on the day of a new release is low and those of the other days are high. In this way, TTM can adapt flexibly to changes.

8 Conclusion

In this paper, we proposed a probabilistic consumer purchase behavior model, called the Topic Tracking Model (TTM), for tracking the interests of individual consumers and trends in each topic. We confirmed experimentally that TTM could estimate purchase behavior appropriately and process large amounts of data.

In future work, we could determine the unit time interval and the length of dependence automatically from the given data. The number of topics would be automatically inferred by extending TTM to a nonparametric Bayesian model such as the Dirichlet process mixture model [Teh et al., 2006]. We will evaluate the proposed method further by comparing it with other methods for modeling dynamics, such as hidden Markov models, dynamic topic models, and dynamic mixture models.