title: A Simple and Debiased Sampling Method for Personalized Ranking
abstract: Pairwise ranking models have been widely used to address  various problems, such as recommendation. The basic idea is to learn the rank of users' preferred items through  separating items into positive samples if user-item interactions exist, and negative samples otherwise. Due to the limited number of observed interactions, pairwise ranking models face  serious class-imbalance issue. Our theoretical analysis shows that current sampling-based methods cause the vertex-level imbalance problem, which makes the norm of  learned item embeddings towards infinite after a certain training iterations, and consequently results in vanishing gradient and affects the model performance. To this end, we propose VINS, an efficient \emph{\underline{Vi}tal \underline{N}egative \underline{S}ampler}, to alleviate the class-imbalance issue for pairwise ranking models optimized by gradient methods. The core of VINS is a bias sampler with reject probability that will tend to accept a negative candidate with a larger popularity than the given positive item. Evaluation results on several real datasets demonstrate that the proposed sampling method speeds up the training procedure 30\% to 50\% for ranking models ranging from shallow to deep, while maintaining and even improving the quality of ranking results in top-N item recommendation. 
authors: Lu Yu Shichao Pei Chuxu Zhang Xiangliang Zhang
hIndex: None 0