  How to sample high quality negative instances from unlabeled data, i.e.,
negative sampling, is important for training implicit collaborative filtering
and contrastive learning models. Although previous studies have proposed some
approaches to sample informative instances, few has been done to discriminating
false negative from true negative for unbiased negative sampling. On the basis
of our order relation analysis of negatives' scores, we first derive the class
conditional density of true negatives and that of false negatives. We next
design a Bayesian classifier for negative classification, from which we define
a model-agnostic posterior probability estimate of an instance being true
negative as a quantitative negative signal measure. We also propose a Bayesian
optimal sampling rule to sample high-quality negatives. The proposed Bayesian
Negative Sampling (BNS) algorithm has a linear time complexity. Experimental
studies validate the superiority of BNS over the peers in terms of better
sampling quality and better recommendation performance.
