Contrastive estimation reveals topic posterior information to linear models
Authors: Christopher Tosh
Akshay Krishnamurthy
Daniel Hsu
Venue:  (2021)
Keywords: contrastive learning
self-supervised learning
representation learning
theory

Abstract: Contrastive learning is an approach to representation learning that utilizes naturally occurring similar and dissimilar pairs of data points to find useful embeddings of data. In the context of document classification under topic modeling assumptions, we prove that contrastive learning is capable of recovering a representation of documents that reveals their underlying topic posterior information to linear models. We apply this procedure in a semi-supervised setup and demonstrate empirically that linear classifiers with these representations perform well in document classification tasks with very few training examples.

Under review as a conference paper at ICLR 2021
CONTRASTIVE ESTIMATION REVEALS TOPIC POSTERIOR INFORMATION TO LINEAR MODELS
Anonymous authors
Paper under double-blind review
ABSTRACT
Contrastive learning is an approach to representation learning that utilizes natu- rally occurring similar and dissimilar pairs of data points to find useful embed- dings of data. In the context of document classification under topic modeling assumptions, we prove that contrastive learning is capable of recovering repre- sentation of documents that reveals their underlying topie posterior information linear models. We apply this procedure in a semi-supervised setup and demon- strate empirically that linear classifiers with these representations perform well document classification tasks with very few training examples.
INTRODUCTION
Using unlabeled data to find useful embeddings is a central challenge in representation learning. Classical approaches this task often start by fitting some type of structure the unlabeled data, such as a generative model or dictionary, and then embed future data via inference with the fit- ted structure (Blei et al.] [2003] Raina et al., (007). While principled, this approach is not without its drawbacks. One issue is that learning structures and performing inference is often hard in gen- eral (Sontag & Roy 2011 Arora et al. 2012). Another issue is that we must priori choose structure and method for fitting the unlabeled data, and unsupervised methods for learning these structures can be sensitive to model misspecification (Kulesza et al. 2014).
Contrastive learning (also called noise contrastive estimation, NCE) is an alternative represen- tation learning approach that tries to capture the latent structure in unlabeled data implicitly. At high level, these methods formulate classification problem in which the goal is to distinguish ex- amples that naturally occur in pairs, called positive samples, from randomly paired examples, called negative samples. The particular choice of positive samples depends on the setting. In image repre- sentation problems, for example, patches from the same image or neighboring frames from videos may serve as positive examples (Wang & Gupta [0015] Hjeelm et al.) 2018). In text modeling, the positive samples may be neighboring sentences (Logeswaran & Leel
| 2018 Devlin et al., 2018). The idea is that in the course of learning distinguish between semantically similar positive examples and randomly chosen negative examples, we will capture some of the latent semantic information.
In this work, look "under the hood" of contrastive learning and consider its application to docu- ment modeling, where the goal is to construct useful vector representations of text documents in a corpus. In this setting, there natural source of positive and negative examples: a positive exam- ple is simply document from the corpus, and a negative example is one formed by pasting together the first half of one document and the second half of another (independently chosen) document. We prove that when the corpus is generated by topic model, learning to distinguish between these two types of documents yields representations that are closely related to their underlying latent variables.
One potential application of contrastive learning is in semi-supervised setting, where there is small amount of labeled data as well as a much larger collection of unlabeled data. In these situa- tions, purely supervised methods that fit complicated models may have poor performance due to the limited amount of labeled data. On the other hand, when the labels are well-approximated by some function of the latent structure, results show that effective strategy is to fit linear functions, which may be learned with relatively little labeled data, on top of contrastive representations. In our experiments, verify empirically that this approach produces reasonable results.

---

Under review as a conference paper at ICLR 2021
Contributions. The primary goal of this work is to shed light on what contrastive learning tech- niques uncover in the presence of latent structure. To this end, we focus on the setting of document modeling where latent structure is induced by topic model. Here, our contrastive learning objec- tive is to distinguish true documents from 'fake" documents that are composed by randomly pasting together two document halves from the corpus. We consider two types of architectures or functional forms of solutions for this problem, both trained with logistic loss.
The first architecture, on which our theoretical analysis will focus, consists of general functions of the form ((--). Here, we have trained / so that f(xx, indicates the confidence of the model that x and x' are two halves of the same document. To embed a new document x using f. we propose a landmark embedding procedure: fix documents (1..... Lys (our so-called landmarks) and create the embedding ((x) using function of the predictions (t).,,)).... [(x,,x J.r). In Section 4 we show that the embedding ((x) is a linear transformation of the underlying topic posterior moments of x. Moreover, under certain conditions this linear relationship invertible, so that linear functions of Φ(x) correspond to polynomial functions of the topic posterior of document
In Section 5 we
show that errors in f on the contrastive learning objective transfer smoothly to errors in ((x) as a linear transformation of the topic posterior of zr Thus, as the quality of f improves, linear functions of ((x) more closely approximate polynomial functions of the topic posterior of document x.
Unfortunately, the landmark embedding can require quite a few landmarks before theoretical results kick in. Moreover, embedding a document requires M evaluations of f. which can be expen- sive. To circumvent this, in Section / we introduce direct embedding procedure that more closely matches what is done in practice. We use an architecture of the form fi (z)) (x') where fi, f2 are functions with d-dimensional outputs, and we train this architecture on the same contrastive learn- ing task as before. To embed a document x, we simply use the evaluation f1)). In Section 7 we evaluate this embedding on a semi superviee learning task, and we show that has reasonable performance. Indeed, the direct embedding method outperforms the landmark embedding method, which raises the question of whether or not anything can be theoretically proven about the direct embedding method, We leave this question to future work.
Related work. Reducing an unsupervised problem to a gynthetically-geeeraae supervised prob- lem is well-studied technique. In dynamical systems modeling, [angffrrd et al. (2009) showed that the solutions to a few forward prediction problems can be used to track the underlying state of a non- linear dynamical system. For linear dynamies, the idea is also seen in autoregressive models (Yule) 1927]. In anomaly/outlier detection, a useful technique is to learn a classifier that distinguishes between true samples from a distribution and fake samples from some synthetic distribution (Stein- wart et al. 2005 Abe et al. 2006). Similarly, estimating the parameters of probabilistic model can be reduced to learning to classify between true data and randomly generated noise (Gutmann &
Hyvärinen 2010).
In the context of natural language processing, methods such as skip-gram and continuous bag-of of- words turn the problem of finding word embeddings into prediction problem (Mikolov et al.) (0) Modern language representation training algorithms such as BERT and QT also use nat- urally occurring classification tasks such as predicting randomly masked elements of sentence or discriminating whether or not two sentences are adjacent (Devlin et al. 2018: Logeswaran & Leel 2018). Training these models often employs technique called negative sampling, in which softmax prediction probabilities are estimated by randomly sampling examples; this bears close resemblance to the way that negative examples are produced in contrastive learning.
Most relevant to the current paper, Arora et al. (2019) gave a theoretical analysis of contrastive learning. They considered the specific setting of trying to minimize the contrastive loss
L(f) = Er,z4... - (f(x) (f(x)))))))
where (x, 24) is positive pair and (H, is a negative pair. They showed that if there is an underlying collection of latent classes and positive examples are generated by draws from the same class, then minimizing the contrastive loss over embedding functions f yields good representations for the classification task of distinguishing latent classes.
The main difference between work and that of Arora et al. (209)) is that we adopt generative modeling perspective and induce the contrastive distribution naturally, while they do not make gen- erative assumptions but assume the contrastive distribution is directly induced by the downstream
2

---

Under review as a conference paper at ICLR 2021
Algorithm 1 Contrastive Estimation with Documents
Input: Corpus U of unlabeled documents. Initialize: S = 0. for: i = I....,n n do
Sample and ā independently from un su ((x00) ,000),{(1)) ,1) w.p. 1/2 (((x(1))=(0) ,0) w.p. 1/2
end for
Solve the optimization problem
f minimize
Σ
y ylog (1+ ((all) (1 log (1 (x0l))
Select landmark documents I,..., las and embed ((x) = (exxp(((() : :iE
classification task. In particular, our contrastive distribution and supervised learning problem are only indirectly related through the latent variables in the generative model, while AAooa al. as- sume explicit connection. The focus of our work is therefore complementary to theirs: we study the types of functions that can be succinetly expressed with the contrastive representation in our generative modeling setup. In addition, our results apply to semi-supervised regression, but it is un- clear how to define their contrastive distribution in this setting; this makes it difficult to apply their results here. Finally, Arora et al. point out the method they study has limitations that arise when the number of latent classes small and the probability of negative samples having the same class is high. In our setting, class collisions turn out not be problem since our embeddings explicitly utilize conditional probability information from the solution to our contrastive learning objective.
2 SETUP
Let V denote finite vocabulary. A topic is distribution over V. We will assume that have K such topics, and denote the corresponding distributions as O k)) for = 1.... K. To generate a length m document æ, one first draws a vector from A the K K-dimensional probability simplex, and then samples each of the m words .1, Xm by first sampling the latent variable 2; ~ w and drawing x; (-- 24). We note that documents are allowed take different lengths.
We will also be interested in the case where each document has an associated label e One natural restriction make on label is that is conditionally independent of the document given the topic distribution of the document. Thus, we will assume that there is a joint distribution D of triples (x,, w, E). where (Ir, w) are generated according to the topic model described above, and then l is drawn from some distribution conditioned on w. One of the goals of this paper is to characterize the functional forms of this conditional distribution that are most suited to contrastive learning.
In the representation learning approach to the semi-supervised setting, we are given large collection of documents with no labels, and small collection & of labeled documents. Using Ut we learn a feature map e that will form the basis of our predictions. Then, using L, we learn a simple predictor based on o such as a linear function, to predict the label given ((x)).
3 CONTRASTIVE LEARNING ALGORITHM
In contrastive learning, examples come in the form of similar and dissimilar pairs of points, where the exact definition of similar/dissimilarr depends on the task at hand. Our construction of similar pairs will take the form of randomly splitting document into documents, and our dissimilar pairs will consist of subsampled documents from two randomly chosen documents. In the generative modeling setup, since the words are i.i.d. conditional on the topic distribution, a natural way to split document into two is to call the first half of the words (!)) and the second half 2(2), In experiments, we split the documents by applying a random permutation to the word tokens and partitioning in half, thus effectively ignoring the word ordering (as is common in topic models).
3

---

Under review as a conference paper at ICLR 2021
The contrastive representation learning procedure is displayed in Algorithm It uses finite- sample
approximation to the contrastive distribution Doomraat described as follows: (a) sample a document
J and partition it into (x:(1, x22)), (b) with probability 1/2 output (ax(1), (,(1))=(1))) (2) ( 1), (c) with probability
_(2), (,02),0) 0). For (ar, x', y) ~ Doontrsts the parts and x' are the two halves of a (possibly synthetic) document, and is the binary label. Our
1/2, sample a second document (a(1), x(2) and output (x(1),5(2)
contrastive learning objective is to minimize the binary cross-entropy loss of discriminating between positive and negative examples:
Leontrast = B(z,x' Domont log (1+ e -e==/=xx)) + (1 y) log (1 ((te))o)))
(I)
In our algorithm, we approximate this expectation via sampling and optimize the empirical objective, which yields an approximate minimizer (chosen from some function class F).
To why optimizing this contrastive learning objective is useful, let f be the global minimizer of Eq. (T. By Bayes' theorem we have that g* := exp( satisfies the following:
P(y = x x, Ply 0 x. P(x (xx(2) = x')
((x = x. x(22 x(()== =2)
(0(,²² == exp(
Thus, x²) captures the ratio of the probability of x and x' co-occurring as the first and second halves of the same document and the product of their marginal probabilities.
In Eq. ( we have not imposed any constraints on the functions over which we are optimizing. Thus, we seek extract useful embedding from g* using only black box access g" Our approach to this problem is to select some set of fixed documents, which we call landmarks, and to embed by utilizing the predictions of g" on these landmarks.
Formally, we select documents l...., and represent document as
(xxx) = (x,4),,.... (x,,,,))
This yields the final document-level representation, which can be used for downstream tasks. As we shall see in Section 4 when the documents have an underlying topic structure, ø (x) is related to the posterior information of the topics by linear transformation and this linear transformation is invertible whenever the landmarks 4..... In are sufficiently diverse.
In practice, we only have access to an approximate minimizer ff of Eq. (I. Thus, our embedding in practice will be given by
((x) (xxp (f(z, ......
(f(e, cxp (f(u,tu))
In Section we will see that, under some mild assumptions, our claims about o* also hold true for i up to some small errors.
Finally, point out that there is nothing special about the binary cross-entropy loss. We may replace this loss in Eq. ① with any proper scoring rule (Shuford et al. [966] Buja et al.] (005), long as the appropriate non-linear transformation applied to the resulting predictions.
4 RECOVERING TOPIC STRUCTURE
In this section, we focus on expressivity of the contrastive representation, showing that polynomial functions of the topic posterior can be represented as linear functions of the representation. To do so, we ignore statistical issues and assume that we have access to the oracle representations g (z,.). In Seecton 5] we address statistical issues.
Recall the generative topic model process for document x. We first draw a topic vector w E A Then for each word i = 1..... length(x)), we draw z; Categorical( and a; O(- 21). We will show that when documents are generated according to the above model, the embedding of
document x in Eq. 22 closely related underlying topic vector w.
'Strittly speaking, we should first partition halves of documents, and embed z ++ (x(1), ....... . g" (1) 1),, lax )). For the sake of clarity, we will ignore this small technical issue here and in the remainder of the paper.
(1) ,2(2),, only use landmarks that occur as second-
4

---

Under review as a conference paper at ICLR 2021
4.1 THE SINGLE TOPIC CASE
To build intuition for the embedding in Eq. (2) we first consider the case where each document's probability vector w is supported single topic, i.e., w E ;el,-..,ek] where the 7thh standard basis element. Then we have the following lemma.
Lemma 1. For any documents x; x', we can write g", (x, x²) = (((()))(('') where 11 = F(w = eg (4) = r) is the topic posterior distribution and 1b(x)) == P(x = x/w = ex)/P((x( = x²).
Due to space constraints, all proofs are deferred to Appendix C
and Appendix D
The characterization from Lemma shows that g contains information about the posterior topic distribution vy)). recover it, we must make sure that the v-()) vectors for our landmark documents span RKK Formally, if 11,...,,M are the landmarks, and we define the matrix L E RKXM by
L = [v)(1)
(b(ar))
then representation satisfies (x) L' L'n(x). If our landmarks chosen so that L has rank K, then TT (x) = nTx), where i denotes the matrix pseudo-inverse. Thus, there is a linear transformation of σ² (a)) that recovers the posterior distribution of w given
There are two observations to be made here. The first is that this argument naturally generalizes beyond the single topic setting any setting where can take values in finite set S, which may include some mixtures of multiple topics, though the number of landmarks needed would grow at least linearly with [S]. The second that we have made no use of the structure of x11) and x(2), except for that they independent conditioned w. Thus, this argument applies to more exotic ways of partitioning a document beyond the bag-of- words approach.
4.2 THE GENERAL SETTING
In the general setting, we allow document vectors to be any probability vector in A K and we do not hope to recover the full posterior distribution over A K However, the intuition from the single topic case largely carries over, and we will show that we can still recover the posterior moments.
Let Mmax be the length of the longest landmark document. Let S fa E ZK Ex ag m} denote the of non-negative integer vectors that sum to and let SK Smmax
SK U.K m
Let (w)) denote the degree-mmax monomial vector in wt T(w) == (w] w : a E SK
mmanas
For positive integer and vector a S.K we let (Iml)) {a [K]m E 1[ kl
ag vk E [K]]- For a document z of length m, the degree-m polynomial vector ymm is defined by
(x)
Σ [ S
and let (a(x)) = for all d * m. The cumulative polynomial vector vb is given by
(() = (2) = x)) (Vo(x), 1 (x), ... Wmmaa (x)).
(4)
Given these definitions, we have the following general case analogue of Lemma Lemma 2. For any documents I, x's we may write g" (x,xx) (x=)T<(())) where nπ())
[[((w) (1) x² and vp is defined in Eq
Thus, again have (x) L'n(z),, but the columns of L are now vectors (44)) from Eq.
Our analysis, so far, shows that if we choose the landmarks such that LLT is invertible, then our representation captures all moments of the topic posterior up to degree mmmax. As the next the- orem shows, we can ensure that LL" is invertible whenever each topic has an associated anchor word (Arora al. 2012), i.e., word that occurs with positive probability only within that topic. In this case, there is a set of landmarks l,..., IM such that any polynomial of 77(z) can be expressed linear function of o² (x:).
5

---

Under review as a conference paper at ICLR 2021
Theorem 3. Suppose that (i) each topic has associated anchor word, and (ii) the marginal distribution of w has positive probability on the interior of A AK For any d, 2 1, there is a collection of M (K" landmark documents 1,.... ........M.... L.MM such that if Q(w) is degree-d, polynomial in w, then there is vector 0 E RRM such that (0,6* (x)) [[Q(w) [x(())
for all documents
Coupling Theorem 3 with the Stone- Weierstrass theorem (Stone 1948) shows that, in principle, the posterior mean of any continuous function of w can be approximated using our representation.
5 ERROR ANALYSIS
Given a finite amount of data, we cannot hope to solve Eq. ① exactly. Thus, our solution f will only be an approximation to f* Since f is the basis of our representation, one may worry that errors incurred in this approximation will cascade and cause the approximate representation ((x) to differ so wildly from (œ) that the results of Section do not even approximately hold.
In this section, we will show that, under certain conditions, such fears are unfounded. Specifically, we will show that there is an error transformation from the approximation error of to the approx- imation eπrrr of linear functions in Φ. That is, if the target function is 17(x)"0", then we will show that the best mean squared error achievable using our approximate representation é, given by
R( == min Ex (n)())00* x)²
is bounded in terms of the approximation quality of f as well as some other terms. Here, ((()) is the marginal distribution over first halves of documents drawn from D. Thus, for the specific setting of semi- supervupe learning, an approximate solution to Eq. ① is good enough.
There are number of reasonable ways to choose landmark documents. Here we consider simple method: randomly sample them from the marginal distribution p1 of x(2), We will assume that this distribution satisfies certain regularity properties.
Assumption 1. There is a constant min > 0 such that for any E (0, 1), there is number Mo such that for an i.i.d. sample li.....ly, IM from μ 22 with M 2 Mo. with probability - 8, the matrix L in Eq. 33 (with to as defined in Lemma or Eq. has minimum singular value at least J v M.
non-zero zero singular value 1 L is the square-root of the smallest eigenvalue of certain empirical recond-moment matrix. Hence, Assummtion hholds under appropriate condi- tions on the landmark distribution, for instance via tail bounds for sums random matrices (Tropp) 2012) combined with matrix perturbation analysis (e.g.. Weyl's inequality). In the single topic set- ting with anchor words, can be shown that for long enough documents, amin is lower-bounded by constant when Mo grows polynomially with K. We defer detailed proof of this to Appendix D
Note that the smallest non-
VM
We will also assume that the predictions of and fr bounded above by constant.
Assumption 2. There exists some 9max > O such that f(x, 4). (x 4) S log 9max for all docu- ments and landmarks 4,
Note that if Assumption 2 holds for f*, then it can be made to hold for f by clipping. Moreover, holds for f whenever the vocabulary and document sizes are constants:
((x(1) x, (2)) =x) log (() x' (111 = x) log P(x(2) x') (" x = log ((2(1) = (x) = x²)
1
((x = x¹)
Since landmarks are sampled, and the number of possible documents is finite, there exists a constant Pmiin such that (2) = l) 2 Pmin. Thus, Assumption 2 holds for Jmax S 1/Pmin-
Given these assumptions, we have the following error transformation guarantee.
Theorem 4. Fix any 8 E (0, 1), and suppose Assumption 1 and Assumption 2 hold (with Mo. Omins and fmax). Let f be the function returned by the contrastive learning algorithm, and let Tegontrus (f) Tecontrusa (f*) denote its excess contrastive loss. If M > Mo, then with probability

---

Under review as a conference paper at ICLR 2021
Topic Separation
Topic Recovery
Smmell NN
MN
6.00
Recsmale eate
12
Topic similarty (Dinchiet parametenn
Topic similartty (Diichiet parametery
1a0 amiirtty (0612h0n paramnter)
Accurscy
Figure 1: Topic modeling simulations. Left: Average total variation distance between topics. Right:
Topic recovery accuracy for contrastive models. Total number documents sampled = 6M x rate.
least 8 ô over the random sample of 11,....a .MM.
110-1 (max)* (6
log (2/0)
R( S
0 min
We make few observations here. First, 110-11 is measure of the complexity of the target function. Thus, if the target function is some reasonable function (e.g., low-degree polynomial) of the posterior document vector, then we can expect ||@* 112 to be small. Second, the dependence on Jmax is probably not very tight and can likely be improved. Third, note that M can grow and can shrink with the number of unlabeled documents; indeed, none of the terms in Theorem 4 deal with labeled data.
Finally, it is possible to establish guarantees in a semi-supervised setting using our analysis. we have n i.idd. labeled examples, and we learn a linear predictor with the representation using ERM (say), then the bias-variance decomposition grants
mse( () := Exseen (n(=)) - = R(O) + Empptrs (x(x)) -))),
where v² is the minimizer of mss(-). The final term Bawgen (b(x) is the excess risk in linear regression, which goes to zero as nz - 0o.
TOPIC MODELING SIMULATIONS
To test our theory, we ran simulation experiments with single-topic generative model where 20 topics are sampled from a symmetric Dirichlet(a) distribution over vocabulary of size 5k. The Dirichlet parameter a governs the sparsity the topic distributions, effectively determining the similarity of the topies: as increases the prior concentrates the interior of the simplex, forcing the topic distributions to be more similar. This is visualized in the left panel of Figure
In the experiments, generate dataset and solve the contrastive optimization problem, and then we construct the landmark embeddings ((x) for each document x using 1k landmark documents, following /eccioon 4 Using the true likelihood matrix for the landmarks. we infer the MAP topic estimate and measure accuracy as the fraction of test documents for which this prediction matches the generating topic. See Apppeddxx A for additional details.
The results are displayed in the center and right panel of Figure where we vary the network architecture and the amount of training data. The experiment identifies several interesting properties of the contrastive learning approach. First, as a sanity check, the algorithm does accurately predict the latent topies of the test documents in most experimental conditions and the accuracy is quite high when the problem is relatively easy (e.g., is small). Second, the performance degrades as increases, but this can be mitigated by increasing the model capacity (size the network) or the resampling rate (which exposes the model to more unlabeled data). Specifically, we consistently see that for a fixed model and a, increasing the resampling rate improves accuracy. A similar trend emerges when fix and rate and increase model capacity. These findings suggest that latent topics can be recovered by the contrastive learning approach, provided we have an expressive enough model and enough unlabeled data.

---

Under review as a conference paper at ICLR 2021
Methods
Depth Comparison
NCE 5
608
6.44
Wall
0.-
20M
0.00
10% 51
Tealere Oneed NC:
Orecaaee Stred
Traning
# of Landmarks Comparison
Contrastive error vs Supervised Acourady
word2vec 1:SNE
0.50
0.22
Lastraccee 20601
65
acurtey
Laskracera 31e3)
Eastraccre 316991
Welt
1000 1.00
2000
2000 3950 3950 4003
310
200
3013
Tra Traning examp
Figure 2: Experiments with AG news dataset. Top left: test accuracy of methods as we increase the number of supervised training examples. Bottom left: Landmark -NCC performance we vary number of landmarks. Top middle: Direct-NWe performance as we vary network depth. Bottom middle: Relationship between contrastive error and test accuracy for Direct- -CCE. Right: t-SNE visualizations of Direct-NCE and word2vec embeddings.
7 SEMI-SUPERVISED EXPERIMENTS
We also conducted experiments with our document-level contrastive representations in a semi- supervised setting. The goal of these experiments is to demonstrate that the contrastive representa- tions yield non-trivial performance, as consistent with the theory. Note that our intention is not to show state-of-the-ard performance using contrastive learning; that is beyond the scope of the paper.
We discuss the main findings here, with experimental details deferred to Appendix
A closely related representation. In the worst-case, the guarantees from Section 4 and Section 5 require the number landmarks to be quite large. To develop a more practical representation, and to more closely mirror what is done in practice, consider training models of the form fi, f2 X + Rd where x²) Y fa (x) fz(x"). Plugging this into Eq (I), we solve the following bivariate optimization problem:
minimize EDonn yolo (1 exp (-fi(a)(a((t))) (--f((())) + (1 log (1 (1+ exp (((x)(((()))) f1.J2
(5)
Given f2. we can embed a document x according to f1 We call the resulting scheme the direct embedding approach to distinguish it from the landmark embedding approach from (Section 3]
Methodology. We used the AG news topic classification dataset (Zang et al. 2015). which has 4 classes and 30k training examples per class. We reserve 1k examples per class as labeled train- ing data and use the remaining examples for representation learning. For all methods, we use f-- regularized logistic regression to fit linear classifier on the labeled data.
We compared the representations Handmark-NNC and Direct-NCE against the following baselines: (1) standard bag-of-words (BOW), (2) bag-of-words with dimensionality reduction
(BOW+SVD), (3) representations from LDA (LDA), and (4) skip-gram word embeddings (Mikolov)
al. 2013b) (word2vec). For the NCE methods, we experiment with different neural network architectures and numbers of landmarks but use standard settings for other training parameters. See Appendix B for details. We note that all of these methods all of these methods ignore word order in the final document-level representation, and all of them (with the exception of word2vec) ignore word order in their training.
In all line plots in Figure 2] the training examples axis refers to the number of randomly selected labeled examples used to train the linear classifier. The shaded regions denote 95% confidence intervals computed over 10 replicates of this random selection procedure.
Baseline comparison. In the left panel of Figure 2] we visualize the semi-supervised perfomance of NCE and the baselines. Dí rect NCE outperforms all the other methods, with dramatic improve-
8

---

Under review as a conference paper at ICLR 2021
ments over all except word2vec in the low labeled data regime. BOW is quite competitive when there is an abundance labeled data, but as the dimensionality of this representation is quite large, it performs poorly with limited samples. However, unsupervised dimensionality reduction on this representation appears to be unhelpful and actually degrades performance uniformly. Finally, we point out that word embedding representations (word2vec) perform quite well, but our document- level Birect-Nor procedure is slightly better, particularly when there are few labeled examples. This may reflect some advantage in learning document-level non-linear representations, opposed to averaging word-level ones.
Visualizing embeddings. For qualitative perspective, we visualize the embeddings from NCE us- ing t-SNE with the default scikit-learn parameters (van der Maaten & Hinton| 2008 Pedregosa al.) 2011]. To compare, we also used t-SNE to visualize the document- bocurent-averageed averaged word2 vec embed- dings. The right panels of Figure shows these visualizations on the 7,600 test documents colored according to their true label. While qualitiative, the visualization of the Direct -CCE embeddings appear to be more clearly separated into label-homogeneous regions than that of word2vec.
Other results. We investigated the effect of the number of landmarks on the performance of Bandmark-NCC by embedding with 500, 1k, 4k, 8k, and 16k landmarks. The bottom left panel of Figure 2 displays the results, which suggest that a larger number of landmarks is helpful, with diminishing returns at the higher end of the scale.
We also looked into the effect depth on the performance of Direct-N NCE by training networks with one, two, and three hidden layers. In each case, the first hidden layer has 300 nodes and the rest have 256 nodes. The top center panel of Figure 2 displays the results, which suggest that using deeper models for representation learning may improve downstream performance.
We also tracked the contrastive loss of the model on a holdout validation contrastive dataset. The bottom center panel of Figuree plots how this loss evolves over training epochs. Along with this contrastive loss, we checkpoint the model, train a linear classifier, and evaluate the supervised test accuracy. We see that test accuracy steadily improves as contrastive loss decreases, suggesting that in these settings, contrastive loss (which we can measure using an unlabeled validation set) is good surrogate for downstream performance (which may not be measurable until we have a task at hand).
REFERENCES
Naoki Abe, Bianca Zadrozny, and John Langford. Outlier detection by active learning. In Interna- fional Conference on Knowledge Discovery and Data Mining, 2006.
Sanjeev Arora, Rong Ge, and Ankur Moitra. Learning topic models-going beyond SVD. In Sym- posium on Foundations of Computer Science, 2012.
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saunshi. A theoretical analysis of contrastive unsupervised representation learning. In International Con- ference on Machine Learning, 2019.
David M Blei, Andrew Y Ng. and Michael Jordan. Latent dirichlet allocation. Journal of Machine Learning Research, 2003.
Andreas Buja, Werner Stuetzle, and Yi Shen. Loss functions for binary class probability estimation and classification: Structure and applications. Working draft, November, 3, 2005.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre- tre-training of deep bidirectional transformers for language understanding. arXiv:1810.04800 2018.
Thomas L Griffiths and Mark Steyvers. Finding scientific topics. Proceedings of the National
academy of Sciences, 101: 15:8 5235,,52552212 2004.
Michael Gutmann and Aapo Hyvärinen. Noise-contrastive estimation: A new estimation principle for unnormalized statistical models. In International Conference on Artificial Intelligence and Statisties, 2010.

---

Under review as a conference paper at ICLR 2021
R Devon Hjelm, Alex Fedorov, Samuel Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization, arXiv preprint arXiv: 06670, 2018.
Karan Grewal, Phil Bachman, Adam
Matthew Hoffman, Francis R Bach, and David M Blei. Online learning for latent dirichlet allocation. In Advances in Neural Information Processing Systems, 2010.
Alex Kulesza, N Raj Rao, and Satinder Singh. Low-rank spectral learning. In International Confer- ence on Artificial Intelligence and Statistics, 2014.
John Langford, Ruslan Salakhutdinov, and Tong Zhang. Learning nonlinear dynamic models. In International Conference on Machine Learning, 2009.
Lajanugen Logeswaran and Honglak Lee. An efficient framework for learning sentence representa- tions. In International Conference Learning Representations, 2018.
Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word represen- tations in vector space. 100.v:1301.378, 2013a.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean. Distributed repre- sentations of words and phrases and their compositionality. In Advances in Neural Information Processing Systems, 2013b.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary Vetito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems, 2019.
Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg. J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 2011.
Adiyyanarayanan Radhakrishnan, Mikhail Belkin, and Caroline Uhler. Overparameterizzed neural networks can implement associative memory. arXiv: 1909./239.. 2019.
Rajat Raina, Alexis Battle, Honglak Lee, Benjamin Packer, and Andrew Y Ng. Self-taught learning: transfer learning from unlabeled data. In International Conference on Machine Learning, 2007.
Emir H Shuford, Arthur Albert, and H Edward Massengill. Admissible probability measurement
procedures. Psychometrika, 31(2):125-145,, 1966.
David Sontag and Dan Roy. Complexity of inference in latent Dirichlet allocation. Advances in Neural Information Processing Systems, 2011.
Ingo Steinwart, Don Hush, and Clint Scovel. A classification framework for anomaly detection. Journal of Machine Learning Research, 2005.
Marshall H Stone. The generalized Weierstrass approximation theorem. Mathematics Magazine, 1948.
Joel A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Computa- tional Mathematics, 2012.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of Machine Learning Research, 2008
Xiaolong Wang and Abhinav Gupta. Unsupervised learning of visual representations using videos.
In International Conference on Computer Vision, 2015.
George Udny Yule. On a method of investigating periodicities disturbed series, with special refer- ence to Wolfer's sunspot numbers. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character, 1927.
10

---

Under review as a conference paper at ICLR 2021
Xiang Zhang. Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text clas- sification, In Advances in Neural Information Processing Systems, 2015.

---

Under review as a conference paper at ICLR 2021
A TOPIC MODELING SIMULATIONS
The results Seccion 4 show that if a model is trained to minimize the contrastive learning objective, then that model must also recover certain topic posterior information in the corpus. However, there a few practical questions that remain: can train such model, how much capacity should it have, and how much data is needed in order to train it? Our topic modeling simulations are designed to study these questions.
Simulation setup. We considered a single-topic generative model where the topics ......, 0x are sampled from a symmetric Dirichlet(a/ K) distribution over A and for each document, its length is drawn from Poisson(A) and its topic is sampled uniformly from [K]. This model can be thought
of as a limiting case of the LDA model (Blei et al. 2003; Griffiths & Steyvers 2004) when the document-leveè topic distribution is symmetric Dirichler(3) with /3 < 1. In our experiments, we set K = 20, |V] 5000, and À 30, and we varied a from 1 to 10. Notice that as a increases, the Dirichlet prior becomes more concentrated around the uniform distribution, so the topic distributions are more likely to be similar. Thus, we expect the contrastive learning problem to be more difficult with larger values of a.
We used contrastive models of the same form as Section 7, namely models of the form fi, f2 where the final prediction fi(x) f2(')) and fi and J2 are fully-connected neural networks with three hidden layers. To measure the effect of model capacity, we trained two models smaller model with 256 nodes per hidden layer and larger model with 512 nodes per hidden layer. Both models trained for 100 epochs. We used all of the same optimization parameters as in Section 7 with the exception of dropout, which we did not use.
To study the effect of training data, varied the rate at which we resampled entire contrastive training set from the ground truth topic model. Specifically, after every 1/ 1/r-th training epoch, we resampled 60,000 new documents and constructed contrastive dataset from these documents. We varied the resampling rate from 0.1 to 1.0, where larger values of r imply more training data. The total amount of training data varies from 600K documents 6M documents.
Using the results from Section 4 we constructed the embedding ((x) of a new document x using 1000 landmark documents, each sampled from the same generative model. We constructed the true likelihood matrix L of the landmark documents using the underlying topic model and recovered the model-based posterior L' d(z)). We measured accuracy as the fraction of testing documents for which the MAP topic under the testing documents and performed 5 replicates for each setting of parameters.
posterior matched the generating topic. We used 5000
B SEMI-SUPERVISED EXPERIMENT DETAILS
Methodology. We conducted semi supervupe experiments on the AG news topic classification dataset compiled by Zhang al. (0015). This dataset contains news articles that belong to of four categories: world, sports, business, and sci/tech. There are 30,000 examples from each class in the training set, and 1,900 examples from each class in the testing set. We minimally preprocessed the dataset by removing punctuation and words that occurred in fewer than 10 documents, resulting in vocabulary of approximately 16,700 words.
We randomly selected 1,000 examples from each class to remain as our labeled training dataset, and we used the remaining 1 116,000 examples as our unlabeled dataset for learning representations. After computing representations on the unlabeled dataset, we fit a linear classifier on the labeled training set using logistic regression with cross validation to choose the & regularization parameter (Nialas 3).
We compared our representations, Landma rC-NCE and Direct-NCER against several represen- tation baselines.
30X The standard bag-of-worde representation.
BOW+SVD A bag of words representation with dimensionality reduction. We first per- form SVD the bag-of-word. representation using the unsupervised dataset to compute
12

---

Under review as a conference paper at ICLR 2021
low dimensional subspace, and train a linear classifier on the projected bag-of-nn of-words representations with the labeled dataset.
LDA A representation derived from LDA. We fit LDA on the unsupervised dataset us- ing online variational Bayes (Hoffman et al. 2010), and our representation is the inferred posterior distribution over topics given training document.
word2vec Skip-gramn word embeddings (Mikolov et al. 2013b). We fit the skip-gram gram word embeddings model on the unsupervised dataset and then averaged the word embed- dings in each of the training documents to get their representation.
For our representation, to solve the optimization problem in Eq. (5). we considered neural network architectures of various depths. We used fully-connected layers with between 250 and 300 nodes per hidden layer. We used ReLU nonlinearities, dropout probability 1/2, batch normalization, and the default PyTorch initialization (Paszke et al., 2019). We optimized using RMSProp with momentum value 0.009 and weight decay 0.0001 as in Radhakrishnan et al. (2019). We started with learning rate 10-1 which halved after 250 epochs, and we trained for 600 epochs. Unless otherwise stated, La Landmark NCC and Di Prrect-NCC use a three-layer architecture, and Landmard rk-dmark-NNC.. uses 8000 landmarks.
To sample a contrastive dataset, we first randomly partitioned each unlabeled document in half to create the positive pairs. To create the negative pairs, we again randomly partitioned each unlabeled document in half, randomly permuted one set of half documents, and discarded collisions. This results in a contrastive dataset whose size is roughly twice the number of unlabeled documents. In the course of training our models for the contrastive task, we resampled a contrastive dataset every 3 epochs to prevent overfitting on any one particular dataset.
Additional discussions. In the left panel of Figure 2 we additionally remark that LDA performs quite poorly. This could be for several reasons, including that fitting a topic model directly could be challenging on the relatively short documents in the corpus or that the document category is not well-expressed by linear function of the topic proportions.
C PROOFS FROM SECTION 4
C.I PROOF OF SINGLE TOPIC REPRESENTATION LEMMA
Proof of Lemma |
Conditioned on the topic vector w, x(1) and (2) are independent. Thus,
((x = x2) = x')
0¹ (x,x')
P(z(1) (x)( x²)
P(w ex) (Px((()))))
x: -== | ex) = w ex)
P(z(1) = xx))(r(2) = x²)
K
P(w = Ex (1)) = (xx = x' w = c
(() = x')
k=1
()x) (2') ((x(2) x')
where the third equality follows from Bayes' rule.
C.2 PROOF OF GENERAL REPRESENTATION LEMMA
Fix a document & of length m and a document probability vector w. Conditioned on the assignment of each word in the document to topic, probability of document factorizes as
Proof of Lemma 2
PP(x w) Σ KE
II
W. O 12) =
Σ
II Wiz
II
o
2x)
=
=E[K]m
13

---

that each Under review as a conference paper at ICLR 2021
where the last line follows from collecting like terms. Using the form of g" from above, we have
IP(x(()) = 2, xx = x')
(z, x²)
PPx(11) x))((x12) x²)
IN P(x()))) = x () P(x( = () dP(w)
P(x(1) = 2 p))(21)) = =x')
Ju P(x(2) = x' w) (P xx(2) x)
((x(2) x²)
Ju [T)) dl ( x(1) x)
P(x(2) x²)
n(x)" (xx)) (( x²)
C.3 PROOF OF POLYNOMIAL REPRESENTATIO THEOREM
Proof of Theorem 3 By assumption (i), there exists an anchor word for each topic t: = 1.... K. By definition this means that O(as j) > if and only if k. For each vector a 2 such that Σ or I d,, create a landmark document consisting of og copies of ag for k = 1...., K. This will result in (* (K+do) landmark documents. Moreover, from assumption (ii), of these landmark documents has positive probability of occurring under the marginal distribution of (2) for (zx(1), ,x(())
Dommirast which implies g (ar, 1) is well-defined for all our landmark
documents 1.
Let I denote one of our landmark documents and let E Z be its associated vector. Since I only contains anchor words, ((), if and only if = B. see this, note that
m
K
(1)a
Σ
10 24) 2 O(as 1)aa > 0.
II
=E <m(lm))
On the other hand, if 3 + but Σx AA = Ex ake then there exists an index i such that 3g 2 au+1 Thus, for any z E (Imi)). there will more than ag words in / assigned topic k. Since every word in an anchor word and at most ag of them correspond topic ks we will have
m II
OOL 2.) 0.
Rebinding (b() (l)(),, ... shao (1)) and forming the matrix L. using this definition, that LT can be diagonalized and inverted.
For any target degree-d, polynomial Qw.,, there exists vector such that Q(w) (v, na. (w)), where Tu, (w) denotes the degree-do monomial vector. Thus, we may take 0 L L-ly and get that for any document s::
(0, g. g0(,,)a))) (L-'o)TIIn(() E[(e, Td, (w)) (1) x] E[Q(w) x01) z].
D PROOFS FROM SECTION 5
D.1 PROOF OF ERROR TRANSFORMATION GUARANTEE
We first recall and setup some notations. For (1) (x),, y) Doonmnst (our contrastive distribution defined in Section 3). we let μn denote the marginal distribution of x(() Furthermore, recall the
14

---

Under review as a conference paper at ICLR 2021
contrastive loss, conditional probability, odds ratio, and oracle representation functions:
1/ yog + e- =((x)))))) + (1 v) log (1 e
Lecontrst (f) = E(exx' ()), ())
Plu xx11] I. x,, x¹)
2x, log
P(y = xx11) = 2, x(2) = x²)
g (2x 2') = exp (f* (x, x²)) = P(x(1) = I, (2) x¹)
PPx(11) ())((x(()) x²) (M))
('(x) =
where la are landmark documents. The learned approximation f is and from it derive
g(x, x') exp (f(x,x'). ((x) = (). g(x,(,5))
Let 17(2), (z)) denote the posterior/ikellhood vectors from Lemma the posterior/ikelihood
polynomial vectors from Lemma 2 Say the length of this vector is N 2 1.
Our goal is to show that linear functions in the representation ((x) can provide a good approximation to the target function
17(==)
where E RVV is some fixed vector. To this end, define
R(Ø) min E Ex (17(x) à(z)'v)?
which is the best mean squared error achievable using the representation é.
By Lemma
Lemma 2 we know that for any x, x' we have
g² x') (xx)((bbx))))
Recall the matrix
L:=
((M))
This matrix is NNM If L has full row rank, then
(x)) n)xx)) LL 00 (x)
where
(x(x) = (x, ... 9" (x. lm))
and o- -'0*. Thus, R(t*) = We will show that R(Ø) can be bounded as well.
Theorem (Restatement of Theorem 4). Suppose the following assumptions hold.
(1) There constant amin such that for any 8 E (0,1), there is number Ma(ō) such that for an i..dd. sample .i.... las with M 2 Mo(8), with probability 1 - 8, the matrix
I. == [1)(1)
((ax))
has minimum singular value at least mmin v M.
(2) There exists a value Jmax > 0 such that for all documents x and landmarks 4
mf 14), f* (xxxx), S loo Jmaxx
Let j be the function returned by the contrastive learning algorithm, and let
E === Leguteast (f) - Leontrase (f* denote excess contrastive loss. For any 8 E (0, 1), if M 2 Mo(5/2), then with probability at least 1 - 8 over the random draw of hi....,, L.M we have
1 g
log 2log(2/0) (2/8)
R( <
s
0 min
M
15

---

Under review as a conference paper at ICLR 2021
Proof. We first condition two events based on the sample l1....,44 M. The first is the event that L has full row rank and smallest non-zero singular value at least Momi probability least 1 - 6/2. The second is the event that
O: this event has
2 2lgg(2/5) Ben (x,(zx))) )(a,,'))² Blaxranteee (p' b)),,,))
M
(6)
where make the definitions
((x,x') exp(f(xxx2))
x(x,x²) 1 + g(x; x²)
8(x,x') 1/(1 + t f-f(xz)))
(2,
px x'(x, c
+ 9 (x,
By Hoeffding's inequality and the fact that P and p" have range [0, 1], this event also has probability least 1 6/2. By the union bound, both events hold simultaneously with probability least 1 6. We henceforth condition on these two events for the remainder of the proof.
Since has full row rank, via Cauchy-Schwarn we have
R()) min E. m (-(=)00--0 -(x))))
B e (n -((())))-~((()))
E Ex ((0 (x) a(x)))
E Bxnalts 110 12 0 (z)) )(00 || 2
=1 Emmpii o 2(20)
We analyze the two factors on the right-hand side separately.
Analysis of v*. For v*, we have
| S T 10
110+1 2
Mo² min
where we have used the fact that L has smallest non-zero singular value at least v Momin-
Analysis of o= ô. For the other term, we first note that
(' = 1/(1+e = P(y = 1 11x(1) = (2) = =²))
Thus, have
Leguntrast
( (f)
Vecomraaal"")
(2((),z') + (1 log p(x,x²)
(1 (1-""(x,x')
Ex Domnnt
y log
1 p(1, x²)
(x,))'))
(1
p² (or, x.)
p' p' x') (22,z')ogg
+ (1 ac1-pple (x,,z²))) log
p(x,x')
p(x,,
Exx,"")> KL(p(æ, x'), p.p" (2,x'))
where KL(p,p' p²) denotes the KL-divergence between two Bernoulli distributions with biases p and p', respectively. Pinkser's inequality tells us that KL(p,p'), p') 2 2(p - p')?. Combining this with the
fact that D Doontrast is a mixture distribution that places half its probability mass in (1()) & 2x(2) implies
(x.""" ((((,,z') - p='(x, (x,xx')) E
( ((((,, p² (I, (x,x
16

---

Under review as a conference paper at ICLR 2021
Combining the above with Eq. O and the definitions of p.p", we have
M
Bx 100(s)) 3(x) 2 =
Σ E
as
(g" - 1,)
M Σ
+ Imax
(0 -(x,1,)))
E
/=1
2 log( (2/0)
M(1 + 9max)
Blaxeyy (1)( - =(x,,1)))
M
2 2l0g(2/0)
S M(1 + Imax)
E+
M
Wrapping up.
To conclude, have
R(O) I |10*12
E
(=) -Ō(x)
(2/((20)
110-11 222
M(1 + Imaxx) )a
Mo 2 min
M
|0
1/ + Imax )4
2 log(2/8) E
min
D.2 SATISFYING ASSUMPTION
Suppose we are in the single topic case where w E (x), Assume that ming Pr(w = ex) > Wmin- Further assumes that each topic k has anchor word dg., satisfying O ek)
amin- Then we will show that when M and m are large enough, the matrix L whose columns are (P))) will have large singular values.
First note that if document æ contains 0₃ then (x) is one sparse, and satisfies
P(rr w Ex)
if ag E . Therefore, the second moment matrix satisfies
(x)) Σx P(W= k)P((z w kk) CK P(w = k") Ck.
E [+<x)((=))]
P(w Px) E ex)E [+())(()) as E x, w en]
K Paa E x Ex)
A=1 P(w =x) exc..
Now, if the number of words per document is m 2 1/a mmi then
P(ay E x ex) = (1 - O(as | (x)) 2 1 - (sp(-mO(aa (x))
-xpeexxpaaa mopp-)ammn))
2 - 1/e.
Finally, using the fact that P(w ex) < 1, see that the second moment matrix satisfies
[x)))))))]] 2 (1-1/e)/
For the empirical matrix, we perform crude analysis and apply the Matrix-Hoeffding inequal-
ity (Tropp. 2012). We have [[<]))((<)]] S Kw-2 and so with probability at least 1 8, we have
1
M ((LoO)) - E [M()(() 2
8K log(K/6)
M
Mw²
we take M > Q(K (og(K/ ( then we will have that the minimum eigenvalue of the empirical second moment matrix will be least 1/2.
17


Reviews:
[{"review_id": "vbge2M9Qwt6", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nContrastive learning is applied in a semi-supervised setting with few training examples to provide features for a linear classifier. A theoretical analysis is provided to show that contrastive embeddings allow to predict using a linear transformation. The model allows to recover the topic structure of a corpus that is generated from a generative topic model.\n\nEvaluation:\n\nOverall, the paper provides a thorough theoretical analysis to prove that the approach allows to recover topic posterior information. However, I am not convinced of the impact of this analysis, and the experiments are not entirely convincing. Especially the chosen LDA baseline is weak and some parameter settings are not discussed. If the corpus is generated from an LDA generative model, LDA should be able to recover the topic information. A stronger Gibbs sampling variant would be more suitable in my opinion whereas other baselines like the BOW are not very informative. \n\nTo sum up, the objective of the paper is not entirely clear. While the theoretical analysis is interesting, I believe the presentation, clarity and writing of the paper should be improved. I suggest to provide a stronger motivation for the theoretical analysis with an outlook for future work where this analysis could be useful.\n\nStrong points:\n- Theoretical analysis\n- Detailed proofs\n\nWeak points:\n- The analysis rests on the assumption that the corpus is generated from a certain generative process. This is a strong assumption. In topic modeling, this assumption is usually justified in that the resulting topics turn out to be interpretable. However, the approach in this paper does not recover any topics specifically. It is applied for classification where generative approaches are often not the preferred choice. So it seems to me like the advantage of the generative model, the interpretability, is stripped away, and the model is repurposed for classification.\n- The experimental baselines are weak. Word2vec is not developed for the purpose of document classification, online VB does not have classification performance as a strong point and bare BOW is surely not suitable as a realistic baseline.\n- Hard to follow at times, structure could be improved\n\n\n\nDetailed comments:\n- Eq. on p. 2: l is not explained\n- Setup: A k-dimensional vector lies in the (k-1)-dimensional simplex, not the k-dimensional simplex\n- The notation is slightly confusing. I would suggest to use the commonly used $\\theta$ instead of $w$ for the topic distribution\n- \"By Bayes’ theorem we have that g^{\\star}:= \\exp(f^{\\star}) satisfies the following:\" Please give some more hints here about what you mean. Write that the Bayesian theorem is applied in the last equality and that the label y=0 makes the document parts independent. Also, why is y ommited in the last expression?\n- independent conditioned -> independently conditioned\n- all of these methods all of these methods -> all of these methods\n- I find it confusing that the parameter $\\alpha$ is divided by $K$ the number of topics. In FIgure 1 left, if this is the Dirichlet parameter $\\alpha$ then this means you vary it between 1/20 and 10/20 or is this $\\alpha/K$\n- Experiment with LDA: you write that you use online VB, but you do not report the parameters such as batch size. Online VB is extremely sensitive to the batch size. \n- If you compare classification performance I would suggest to rather compare to the Gibbs sampling version of LDA which usually will give better performance with enough samples. Scalability should not be an issue with the size of data sets that are used here.\n- The two variants Direct NCE and Landmark NCE should be more explicitly introduced. At the moment, the Direct NCE introduction is hidden and hard to find. In the beginning you say your approach is to use landmarks and the Direct variant is rather suddenly introduced in a later part without discussing the differences and implications in much detail.\n\nUpdate: \n\nThe authors have not fixed some of the errors I pointed out in my review. For example, they still refer to the k-dimensional probability simplex and did not address some of the other corrections. Since it is otherwise a promising paper, I suggest to carefully revise and resubmit. I will not however recommend a paper with errors for acceptance.", "extra_scores": {}, "extra_text": {}}, {"review_id": "v6AxUMV4iFr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThis paper tries to learn a document level representation from document level contrastive estimation. The training task is try to predict where two half of a document are from the same document. The author proved the contrastive estimation reveals topic posterior information given the topic modeling assumptions. And in experiments, linear models can get relatively good performance. \n\nReasons for score: \n\nOverall, I think it's a good paper. I like the idea of  using topic models as a way to represent the document level information, but it is disappointed to see that the proposed method doesn't provide as good performance as the simply averaging word embeddings. \n\nStrong points:\n1) Detailed proof and detailed experiments, compared with many baseline models. \n2) Using topic modeling as a tool to understand representation learning is interesting. \n\nWeak points:\n1) Author doesn't provide complexity analysis for inference. For a new document, the speed of inference seems depends on number of landmark documents, which could be slow.\n2) I don't understand why it's limited to linear models for the classification task. It seems we can use other models. If contrastive estimation can reveal topic posterior information to linear models, it can also reveal the information to non-linear models. \n3) In the experiments section, the paper proposes a Direct-NCE method that has best empirical performance , which can be confusing for readers.  ", "extra_scores": {}, "extra_text": {}}, {"review_id": "SEPSNhoO8E_", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\nThis paper presents a new contrastive learning algorithm for document representation. The main idea is to generate pseudo labeled two texts, whether the texts are coming from the same document. To learn the discriminating function between the two texts, the learning algorithm minimizes the cross-entropy loss function between them. With the function, the authors suggest the embedding function for a document with selected landmark documents. The authors also show the learned function can be represented by combining the topic posterior distribution and topic likelihood distribution. Experiments show that the suggested learning algorithm can identify hidden topics from a synthetic dataset. And the authors also show the usefulness of the representation in semi-supervised learning by classification performance and visualization.\n\nThe main strength of this paper is suggesting a sound and straightforward learning algorithm to construct document representation. And the authors explain the relatedness of the representation function and topics in a document. I really like to read this part and I think researchers can extend their ideas from these insights.\n\nWhat concerns me most is the lack of comparing existing document representations. The authors compare the suggested representation with models that do not explicitly make document representation (maybe except LDA). I think it is hard to say that this is a fair comparison. I agree that the authors do not need to show that the suggested one outperforms all other baselines. But there are several recent document representation algorithms (Logeswaran & Lee, 2018; Arora et al., 2019; Yurochkin et al., 2019). The authors explain why they do not show the results of them in the Related work section. But I think we can run the same experiments in Arora et al., 2019 with the suggested algorithm representation. I do not understand why their distributions are unclear for the experiment in this paper. Is it a semi-supervised regression not classification? I am interested in these questions, and please describe it in more detail.\n\nOverall, I admit that the suggested algorithm is a sound method to construct the document representation. But I have some questions that I want to listen to the author’s responses.\n\nQuestions\n- I think the landmark documents are important for constructing representation. What are the reasonable ways to choose landmark documents empirically? Does changing the size of the number of landmark documents affect the performance of downstream tasks?\n- In semi-supervised learning experiments, Direct-NCE outperforms Landmark-NCE. Can we say that the landmarks are not useful for the downstream tasks?\n- Can we recover topics that are word distributions from the representation?\n- Is it a errata in Lemma 1? $$\\psi(x)_k = P(x^{(1)} = x | w = e_k) / P(x^{(2)} = x') $$?\n\nReference\nYurochkin, Mikhail and Claici, Sebastian and Chien, Edward and Mirzazadeh, Farzaneh and Solomon, Justin M, Hierarchical Optimal Transport for Document Representation, NeurIPS 2019, http://papers.nips.cc/paper/8438-hierarchical-optimal-transport-for-document-representation ", "extra_scores": {}, "extra_text": {}}, {"review_id": "2rpJ-VjoSVL", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This submission considers contrastive learning approach to representation learning under topic modeling assumptions. It proves that the proposed procedure can recover a representation of documents that reveals their underlying topic posterior information in case of linear models. It is experimentally demonstrated that the proposed procedure performs well in a document classification task with very few training examples in a semi-supervised setting.\n\nThe idea behind the proposed procedure is to split randomly sampled documents into two parts and either keep them as is with the positive label or replace one of the parts with a randomly sampled document and assign the negative label. These data are then passed to the binary cross entropy loss which is optimised to find a transformation that assigns the probability of co-occurence of the two parts.\n\nThe main theoretical result comprises the population case, where infinite amount of data is sampled from the described generative model under an additional anchor word assumption, and proves that in such case the outcome of the proposed contrastive learning procedure is linearly related to all moments of the topic posterior up to a cerain degree. The finite sample case is futher analysed.\n\nSynthetic experiments illustrate performance of the proposed procedure when the data is sampled from a topic model with varying degree of sparsity. It is observed, as expected, that the quality of topic recovery is better when the degree of sparsity is higher.\n\nThe algorithm is further compared on the AG news topic classification dataset with standard benchmarks and it is observed that the performance of the proposed procedure is good and overall comparable with word2vec, being slightly better in the lower sample size setting. The authors thereofre conclude that the proposed procedure can be interesting in semi-supervised learning applications with low amount of data.\n\nOverall, the submission is a solide pice of work and well written. The results are theoretically sound and the observed improvement in the low sample size setting could be of interest in some challenging applications and might be worth further investigating. This line of research could be interesting to the theoretical topic modelling community.\n\ntypo p. 7: all of these methods all of these methods\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This promising work proves that the proposed contrastive learning approach to representation learning can recover the underlying topic posterior information given standard topic modelling assumptions. The work provides detailed proof and detailed experiments. The analysis is interesting and yields interesting insights. However, the experimental results are somewhat weak by lacking comparison with more recent document representation work.

Pros:
- Good detailed proofs and experiments.
- Interesting idea of using topic modelling to understand representation learning.

Cons:
- The description of DirectNCE is somewhat hidden and could be better introduced in the paper.
- Experimental baselines are weak lacking a comparison to recent document representation work such as Arora et al. 2019.
- Stronger classification baselines could be incorporated.
Decision: Reject