In recent years, softmax together with its fast approximations has become the de-facto loss function for deep neural networks with multiclass predictions. However, softmax is used in many problems that do not fully fit the multiclass framework and where the softmax assumption of mutually exclusive outcomes can lead to biased results. This is often the case for applications such as language modeling, next event prediction and matrix factorization, where many of the potential outcomes are not mutually exclusive, but are more likely to be independent conditionally on the state. To this end, for the set of problems with positive and unlabeled data, we propose a relaxation of the original softmax formulation, where, given the observed state, each of the outcomes are conditionally independent but share a common set of negatives. Since we operate in a regime where explicit negatives are missing, we create an adversarially-trained model of negatives and derive a new negative sampling and weighting scheme which we denote as Cooperative Importance Sampling (CIS). We show empirically the advantages of our newly introduced negative sampling scheme by pluging it in the Word2Vec algorithm and benching it extensively against other negative sampling schemes on both language modeling and matrix factorization tasks and show large lifts in performance. Learning from positive and unlabeled data is a well-defined task in machine learning, known as positive-unlabeled (PU) learning BID6 ; BID14 ; BID13 ; BID22 ; BID19 ). The applications of PU learning are numerous, as in many fields negative data is either too expensive to obtain or too hard to define. This is the case in language modeling, where one only observes examples of valid sentences and documents, and tries to learn a generative process. Similarly, in computer vision, with the recent work on Generative Adversarial Networks (GANs), one tries to learn the underlying generative process that produces meaningful images. In both cases, the space of negatives (e.g., non-sentences or non-images) is not clear. Similarly, in matrix factorization, most of the matrices contain pairs of observed interactions, and there are no available explicit negatives.In all of the applications enumerated above, it is quite common to encounter solutions that are based on a softmax loss function. In language modeling, and more recently in matrix factorization, the Word2Vec algorithm (see BID15 ) models the conditional probability of observing all possible items in the vicinity of a context item as a categorical distribution using the softmax loss.However, modeling the probability of co-occurrence as a categorical distribution is a very biased assumption that is clearly refuted by the data, since for all context words there are multiple words that co-occur at the same time.In our paper we propose Partially Mutual Exclusive Softmax (PMES), a new model that relaxes the mutual exclusivity constraint over the outcomes. PMES relaxes this constraint by splitting the set of all outcomes into a set of possible outcomes that are conditionally independent given the context, and a set of impossible outcomes which become negative examples.The context-dependent negative set is hypothesized but not known, so in our method we introduce a model for negatives that is used to weight the sampled candidate negatives. The training algorithm is based on the simultaneous training of two neural networks. The first network is a generator that fits the positives and the sampled negatives. The second network is the discriminator, which is trained to separate the true positive pairs from generated pairs, and is used as the model of the probability that an example would receive a negative label.The resulting solution has many similarities with other recent negative sampling methods for approximating full softmax. However, unlike most of the previous methods, our method is not trying to faithfully approximate the full softmax formulation, but to fix some of its over-simplifying assumptions. Furthermore, we believe that the observed lift in performance of some of the negative sampling work over the full softmax can be explained through the prism of Partially Mutual Exclusive Softmax.Our hypothesis is further confirmed by experiments on language modeling and matrix factorization, where we show a big lift in performance over previous work on negative sampling and full softmax. We validate some of our intuitions on the advantages of our sampling procedure on an artificial dataset where the support sets are known, and show that our sampling scheme correctly approximates the support, which is not the case for other softmax variants.Overall, the main contributions of this paper are the following:• We propose Partially Mutual Exclusive (PME) Softmax, a modified version of the softmax loss that is a better fit for problems with positive and unlabeled data.• We derive a new negative sampling scheme based on an cooperatively-trained models of negatives which we denote as Cooperative Importance Sampling (CIS)• We show empirically the validity of our proposed approach by plugging our new loss into the Word2Vec model, and evaluating this enhanced Word2Vec model against classical sampling schemes for Word2Vec on language modeling and matrix factorization tasks across six real-world datasets.We discuss related work on Word2Vec, negative sampling schemes for softmax and GANs in Section 2 of this paper. In Section 3 we formally introduce our PME-Softmax loss and the associated CIS negative sampling scheme, and describe the training algorithm. We highlight the performance of our method in Section 4, and conclude with ideas and directions for future work in Section 5. In this paper, we have proposed Partially Mutual Exclusive Softmax, a relaxed version of the full softmax that is more suited in cases with no explicit negatives, e.g., in cases with positive and unlabeled data. In order to model the new softmax we proposed a cooperative negative sampling algorithm. Based on recent progress made on GANs in discrete data settings, our cooperative training approach can be easily applied to models that use standard sampled softmax training, where the generator and discriminator can be of the same family of models. In future work we will investigate the effectiveness of this training procedure on more complex models, and also try to make our mutually exclusive set model more contextual and dependent on both objects i and j within a pair. For example, for a given pair context/target, one might want to use the closest neighbors of the target in the embedding space as negatives. This could enable us to obtain a negative distribution that fits both the context and the target.
Defining a partially mutual exclusive softmax loss for postive data and implementing a cooperative based sampling scheme This paper presents Cooperative Importance Sampling towards resolving the problem of the mutually exclusive assumption of traditional softmax being biased when negative samples are not explicitly defined This paper proposes PMES methods to relax the exclusive outcome assumption in softmax loss, demonstrating empirical merit in improving word2vec type of embedding models.