Speeding up large-scale learning with a social prior

Deepayan Chakrabarti, Ralf HerbrichKDD 2013 · OpenReview

Abstract

Slow convergence and poor initial accuracy are two problems that plague efforts to use very large feature sets in online learning. This is especially true when only a few features are "active" in any training example, and the frequency of activations of different features is skewed. We show how these problems can be mitigated if a graph of relationships between features is known. We study this problem in a fully Bayesian setting, focusing on the problem of using Facebook user-IDs as features, with the social network giving the relationship structure. Our analysis uncovers significant problems with the obvious regularizations, and motivates a two-component mixture-model "social prior" that is provably better. Empirical results on large-scale click prediction problems show that our algorithm can learn as well as the baseline with 12M fewer training examples, and continuously outperforms it for over 60M examples. On a second problem using binned features, our model outperforms the baseline even after the latter sees 5x as much data.
BibTeX
@inproceedings{chakrabarti2013speeding,
  author = {Deepayan Chakrabarti and Ralf Herbrich},
  title = {{Speeding up large-scale learning with a social prior}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2013},
  url = {https://openreview.net/forum?id=Hk-VTN-dZr},
}

Loading related content...

Figure