TL;DR
This paper tackles the challenge of accurately tracking product prices from diverse online offers, even when some offers are misidentified. They propose a probabilistic model that accounts for incorrect matches, allowing for more robust price history generation than traditional methods. This approach leads to more reliable price trend analysis, crucial for consumer decision-making.
What Problem Does This Paper Address?
Consumers often rely on historical price data to decide when to buy a product. While e-commerce sites offer product information, they often fall short in providing reliable historical pricing. To construct this history, one needs to aggregate offers from various merchants. However, a significant challenge arises from "offer matching" – correctly associating an offer with its intended product. Errors in this matching process can lead to incorrect price histories, misleading consumers. This paper aims to address this by developing a method to aggregate web offers into representative product prices, even when the initial offer-to-product matching is imperfect.
Methods
The core of the paper is a probabilistic model that treats product prices as unobserved latent variables evolving according to a linear dynamical system (akin to a Kalman filter). Each offer is then modeled as either a "correct" match, with its price drawn from a Gaussian distribution centered on the true product price, or an "incorrect" match, drawing from a background price distribution.
Key methodological contributions include:
- Probabilistic Model: A generative model that explicitly models the probability of an offer being a correct match, allowing for robust inference even with erroneous data.
- Variational Inference: Due to the intractability of exact inference, the authors employ a variational approximation to decouple the latent product prices and offer statuses, enabling efficient computation.
- EM Algorithm: An Expectation-Maximization (EM) algorithm is used to learn the model parameters from the observed offer prices.
- Kalman Filter Speedup: A novel technique is presented to speed up the Kalman filter inference by exploiting matrix structure, achieving a quadratic speedup by avoiding explicit matrix inversions. This technique is presented as a general contribution.
Datasets
The authors evaluated their approach using merchant offers collected from a search engine over a six-month period (mid-July 2011 to mid-December 2011). They focused on products related to televisions and their accessories. For ground truth, they utilized Universal Product Codes (UPCs) to identify correctly matched offers, acknowledging the limitations of this approach (e.g., missing UPCs, incorrect UPCs). They filtered products with extreme price fluctuations or insufficient ground truth data, resulting in an evaluation set of 700 products.
Key Insights and Ideas
- Robustness to Mismatches is Crucial: Simple robust statistics like trimmed means or medians are insufficient because matching errors are often systematic (e.g., confusing similar products) rather than random. These methods can still produce misleading averages.
- Leveraging Temporal Structure: The sequential nature of price data is a powerful signal. By considering the entire price history of an offer, the model can better disambiguate correct from incorrect matches and identify outliers.
- Explicitly Modeling Match Correctness: Directly modeling the probability of an offer being a correct match is more effective than simply trying to filter out outliers post-hoc. This allows the model to down-weight or ignore offers that are consistently "off."
- "Match" vs. "Latent" Performance: A surprising finding was that using the learned probabilities of offers being correct ("Match") significantly outperformed using the inferred latent product prices ("Latent"). This suggests that directly using the "correctness" signal is more valuable than relying on the smoothed latent price trajectory, especially when true price dynamics are complex.
Key Results
The proposed "Match" algorithm, which uses the learned offer correctness probabilities, significantly outperformed several baselines and alternatives:
- Overall Performance: "Match" achieved the best results across all four metrics (Avg-MASE, Avg-MACD, Min-MASE, Min-MACD).
- Improvements over Baseline: "Match" showed statistically significant improvements over the "All" (using all matched offers) baseline, with the largest gains observed for minimum price history metrics (Min-MASE and Min-MACD). For example, Min-MACD showed a -26% difference compared to the baseline.
- Comparison to Alternatives: "Match" outperformed Trimmed Mean, Median, and Post-processing with Kalman Filter. These alternatives did not outperform the "All" baseline.
- Speedup: The Kalman filter speedup technique provides a quadratic speedup, making the learning algorithm more efficient.
Limitations and Future Work
- Ground Truth Limitations: The reliance on UPCs for ground truth has inherent limitations, as it might miss correct matches or include incorrect ones. The authors acknowledge that human judgment is costly and noisy.
- Hybrid Approaches: The analysis suggests that a hybrid approach, combining the proposed method with traditional UPC-based matching, could be beneficial. Specifically, when the fraction of offers with matched UPCs is high, traditional methods might suffice, while the proposed method excels when this fraction is lower.
- Grouping Similar Offers: The authors observed that when multiple distinct sets of offers (e.g., with/without accessories) are incorrectly mapped to the same product, their method struggles. They suggest that grouping these distinct offer sets and presenting separate price histories would be a more appropriate solution.
- Higher-Dimensional State-Space Models: The current model uses a single state for product prices. Exploring higher-dimensional state-space models could potentially improve performance.
- Merchant Pricing Strategies: The model could be enhanced to better account for merchant pricing strategies, such as keeping prices constant for extended periods before adjustments.
- Integration with Matching Algorithms: A key future direction is to integrate the probabilistic price model into the offer matching process itself, leveraging the sequential nature of prices to improve initial matching accuracy.
Summary updated