TL;DR
This paper tackles the problem of making better recommendations by incorporating the temporal order of user preferences, moving beyond traditional "bag-of-votes" approaches. They introduce two data transformation techniques that allow standard machine learning algorithms to leverage this temporal information, demonstrating improved recommendation accuracy.
What Problem Does This Paper Address?
Collaborative filtering (CF) systems aim to recommend items to users based on the preferences of similar users. Traditionally, CF algorithms treat user preferences as a collection of "votes" without considering the order in which these votes were cast. This "bag-of-votes" assumption ignores potentially valuable temporal information, such as how a user's tastes evolve over time or how sequential actions (like browsing a website) reveal underlying structures. The paper addresses this gap by proposing methods to explicitly encode temporal order into the data, enabling existing atemporal learning algorithms to exploit this information for more accurate recommendations.
Methods
The authors propose two primary data transformation techniques to incorporate temporal information into a format usable by standard machine learning algorithms:
- "Bag-of-votes" Transformation: This is the baseline approach, which explicitly disregards the order of votes, treating the entire history as an unordered set. This serves as the benchmark against which their novel methods are compared.
- Binning Transformation: This method addresses the idea that user preferences might change over time. Vote histories are divided into "bins" based on their length. For each bin, a separate model is trained using the "bag-of-votes" approach on the histories within that bin. When predicting for a new vote, the model corresponding to the current history length is used. A "prefix approach" is also discussed, where longer histories can contribute to multiple bins.
- Data Expansion: Inspired by language modeling, this technique transforms each vote into a separate "case." It creates target variables for predicting the next vote and includes lagged variables representing the previous
lvotes, as well as "cache variables" indicating if an item has appeared previously in the history. This allows models to directly learn from the sequence of recent actions.
Datasets
The paper uses two real-world datasets of Web user traces for evaluation:
- Microsoft Research (MSR) dataset: Session traces from
http://research.microsoft.com/. The training data included 110,587 page requests from 27,595 users, and test data had 54,843 requests from 13,563 users. Average session length was 4.007 votes. - MSNBC dataset: Session traces from
http://www.msnbc.com/, with an 80%/20% split. Training data had approximately 1.28 million requests from 475,769 users, and test data had 178,158 requests from 87,714 users. Average session length was 2.696 votes.
In both datasets, a "user" corresponds to a server session, and a page request is treated as an affirmative vote.
Key Insights and Ideas
- Temporal order matters: The core insight is that user preferences are not static and evolve over time. Ignoring this temporal aspect can lead to suboptimal recommendations.
- Leveraging existing tools: The proposed transformations allow researchers to use off-the-shelf machine learning algorithms (like decision trees) without needing to re-implement complex temporal modeling from scratch.
- Binning captures evolving tastes: The binning approach is motivated by the idea that a user's preferences might differ significantly depending on how experienced they are (i.e., how long their history is). This is particularly relevant for domains like TV viewing or website navigation.
- Data expansion captures local structure: The data expansion method, by explicitly encoding recent history, is effective at capturing immediate dependencies, such as link structures on websites where a user is likely to follow links from their current page.
- Sparsity is a challenge: The sparsity of user data, especially for longer histories, poses a significant challenge for accurate model estimation, particularly for the data expansion method.
Key Results
The experiments, primarily using probabilistic decision trees, yielded mixed but generally positive results:
- MSNBC Domain:
- CF Accuracy: Data expansion models (DE-1, DE-3, DE-5) significantly outperformed the baseline "bag-of-votes" model. Performance did not consistently increase with history length, suggesting that immediate links are more influential than longer-term history in this domain.
- Log-Probability Score: The binning models ("2 Bins", "4 Bins") outperformed both the baseline and data expansion models. Data expansion models improved with history length, but only the longest history (DE-5) was competitive with the baseline. This suggests that data sparsity hindered accurate parameter estimation for data expansion.
- MSR Domain:
- Results were qualitatively similar to the MSNBC domain. Data expansion models were superior for CF accuracy, while binning models were superior for log score. The authors hypothesize that MSR visitors might have longer page traces, mitigating some of the sparsity issues seen with MSNBC.
Limitations and Future Work
- Model Prior Parameter (K): The authors acknowledge that they used a single value of the model-prior parameter
kfor all data transformations. They suspect that tuning this parameter for each transformation, especially for data expansion, could have yielded better results. - Data Sparsity: The sparsity of user data, particularly for longer histories, is a significant limitation that impacts the accuracy of models, especially for data expansion.
- Future Work: The paper suggests that further exploration of n-gram language models and Hidden Markov Models (HMMs) could be beneficial. They also note that the binning approach could potentially improve atemporal domains by considering the number of votes. The authors also mention that the techniques could be applied to explicit voting systems.
Summary updated