In recent years softmax, together with its fast approximations, has become the defacto 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, nextevent prediction, and matrix factorization, where many of the potential outcomes are not mutually exclusive, but are more likely to be conditionally independent given the state. To this end, for the set of problems with positive and unlabeled data, we propose Partially Mutual Exclusive Softmax (PMES), 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 a cooperatively-trained model of negatives, and derive a new negative sampling and weighting scheme which we call Cooperative Importance Sampling (CIS). We show empirically the advantages of our newly introduced negative sampling scheme by plugging it into the Word2Vec algorithm and evaluating it extensively against other negative sampling schemes on both language modeling and matrix factorization tasks, where we show large lifts in performance.
This paper presents Partially Mutual Exclusive Softmax (PMES), a relaxation of the full softmax that is commonly used for multi-class data. PMES is designed for positive-unlabeled learning, e.g., language modeling, recommender systems (implicit feedback), where we only get to observe positive examples. The basic idea behind PMES is that rather than considering all the non-positive examples as negative in a regular full softmax, it instead only considers a "relevant" subset of negatives. Since we actually don't know which of the negatives are more relevant, the authors propose to incorporate a discriminator which attempts to rate each negative by how hard it is to distinguish it from positives, and weight them by the predicted score from the discriminator when computing the normalizing constant for the multinomial probability. The motivation is that the negatives with higher weights are the ones that are closer to the decision boundary, hence will provide more informative gradient comparing to the negatives that are further away from the decision boundary. On both real-world and synthetic data, the authors demonstrate the PMES improves over some other negative sampling strategies used in the literature. 
Overall the idea of PMES is interesting and the solution makes intuitive sense. However, the writing of the paper at the current stage is rather subpar, to the extend that makes me decide to vote for rejection. In details:
 
1. The motivation of PMES from the perspective of mutual exclusivity is quite confusing. First of all, it is not clear to me what exactly the authors mean by claiming categorical distribution assumes mutual exclusivity -- does it mean given a context word, only one word can be generated from it? Some further explanation will definitely help. Further more, no matter what mutual exclusive means in this context, I can hardly see that PSME being fundamentally different given it's still a categorical distribution (albeit over a subset).
The way I see PMES from a positive-unlabeled perspective seems much more straight-forward -- in PU learning, how to interpret negatives is the most crucial part. Naively doing full softmax or uniform negative sampling carry the assumption that all the negatives are equal, which is clearly not the right assumption for language modeling and recommender systems. Hence we want to weight negatives differently (see Liang et al., Modeling user exposure in recommendation, 2016 for a similar treatment for RecSys setting). From an optimization perspective, it is observed that for negative sampling, the gradient can easily saturate if the negative examples are not "hard" enough. Hence it is important to sample negatives more selectively -- which is equivalent to weighting them differently based on their relevance. A similar approach has also been explored in RecSys setting (Rendle, Improving pairwise learning for item recommendation from implicit feedback, 2014). Both of these perspectives seem to offer more clear motivation than the mutual exclusivity argument currently presented in the paper.
That being said, I like the idea of incorporating a discriminator, which is something not explored in the previous work.  
2. The rigor in the writing can be improved. In details:
* Section 3.3, "Multivariate Bernoulli" -> what is presented here is clearly not multivariate Bernoulli
* Section 3.3, the conditional independence argument in "Intuition" section seems no difference from what word2vec (or similar models) assumes. The entire "Intuition" section is quite hand-wavy.
* Section 3.3, Equation 4, 5, it seems that i and j are referred both as binary Bernoulli random variables and categorical random variables. The notation here about i and j can be made more clear. Overall, there are ambiguously defined notations throughout the paper. 
* Section 4, the details about the baselines are quite lacking. It is worth including a short description for each one of them. For example, is PopS based on popularity or some attenuated version of it? As demonstrated from word2vec, a attenuated version of the unigram (raised to certain power < 1) works better than both uniform random, as well as plain unigram. Hence, it is important to make the description clear. In addition, the details about matrix factorization experiments are also rather lacking. 
3. On a related note, the connection to GAN seems forced. As mentioned in the paper, the discriminator here is more on the "cooperative" rather than the "adversarial" side. 
Minor:
1. There are some minor grammatical errors throughout. 
2. Below equation 3, "\sigma is the sigmoid function" seems out of the context.
3. Matt Mohaney -> Matt Mahoney