Masked Prediction: A Parameter Identifiability View
Authors: Bingbin Liu
Daniel Hsu
Pradeep Kumar Ravikumar
Andrej Risteski
Venue: NeurIPS 2022 Accept (2022)
Keywords: masked prediction
self-supervised learning
parameter identifiability
tensor decomposition

Abstract: The vast majority of work in self-supervised learning have focused on assessing recovered features by a chosen set of downstream tasks. While there are several commonly used benchmark datasets, this lens of feature learning requires assumptions on the downstream tasks which are not inherent to the data distribution itself. In this paper, we present an alternative lens, one of parameter identifiability: assuming data comes from a parametric probabilistic model, we train a self-supervised learning predictor with a suitable parametric form, and ask whether the parameters of the optimal predictor can be used to extract the parameters of the ground truth generative model.

Specifically, we focus on latent-variable models capturing sequential structures, namely Hidden Markov Models with both discrete and conditionally Gaussian observations. We focus on masked prediction as the self-supervised learning task and study the optimal masked predictor. We show that parameter identifiability is governed by the task difficulty, which is determined by the choice of data model and the amount of tokens to predict. Technique-wise, we uncover close connections with the uniqueness of tensor rank decompositions, a widely used tool in studying identifiability through the lens of the method of moments.

Masked Prediction: A Parameter Identifiability View
Bingbin Liu
Daniel Hsu
Carnegie Mellon University bingbinl @cs. cmu.
Columbia University
djhsuêcs. co columbia kumbia.cc. edu
Pradeep Ravikumar
Andrej Risteski
Carnegie Mellon University pradeeprecs cmu. edu
Carnegie Mellon University aristesk (anddere cmu edu
Abstract
The vast majority of work in self- sulf-supe learning have focused assessing recovered features by a chosen set of downstream tasks. While there are several commonly used benchmark datasets, this lens of feature learning requires assump- tions on the downstream tasks which are not inherent to the data distribution itself. In this paper, we present alternative lens, one of parameter identifiability: assum- ing data comes from a parametric probabilistic model, we train self-supervised learning predictor with suitable parametric form, and ask whether the parameters of the optimal predictor can be used to extract the parameters of the ground truth generative model.
Specifically, we focus on latent-variable models capturing sequential structures, namely Hidden Markov Models with both discrete and conditionally Gaussian observations. We focus on masked prediction as the self-supervised learning task and study the optimal masked predictor. We show that parameter identifiability is governed by the task difficulty, which is determined by the choice of data model uncover close connections
and the amount of tokens predict. Technique-wist with the uniqueness of tensor rank decompositions, a widely used tool in studying identifiability through the lens of the method of moments.
Introduction
Self-supervised learning (SSL) is relatively new approach to unsupervised learning, where the learning algorithm learns to predict auxiliary labels generated automatically from the data without human annotators. The hope is that with a properly designed prediction task, successfully learned predictor would capture some knowledge about the underlying data. While SSL has been enjoying a rapid growth the empirical front, theoretical understanding of why and when SSL works is still nascent. In no small part, this is because formalizing the desired guarantees seems challenging. For instance, the focus of SSL has largely been learning good features, which in practice has been quantified by downstream performance on various benchmark datasets [Wang et al. 2018 2019 Deng al. 2009 Zhai al. 2019 Tamkin al. 2021]. To provide theoretical underpinning this, one needs to make extra assumptions on the relationship between the self-supervised prediction task
and the downstream tasks AAora et al. 2019 Saunshi al. 2020 HaoChen al. 2021 Lee et
2021a Wang et al. 2021 Wei et al. 202 Wen and 2021].
While associating SSL with downstream supervised tasks is useful perspective and has led to several very interesting theoretical results, we take a step back and revisit a more general goal of SSL,, which
to learn some informative functionals of the data distribution. Naturally, the key question here is
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

what functionals should be considered informative. While downstream performance is notable valid choice, in this work, we choose an alternative criterion that is meaningful even without referencing any downstream tasks.
The alternative lens we are interested in is whether the functionals of the data distribution extracted by the SSL predictors can be simply stitched together to obtain the data distribution itself, given additional inde-information about the family from which the data distribution is drawn. While this might seem like a tall order, masked prediction based SSL algorithms (which is essentially what meeudolikellhooe corresponds to) have classically been used for learning parametric graphical models such as Ising models [Ravikumar et al. 2010 Bresler 2015 Vuffray et al. 2016]. But can this be done for broader classes of parametric models?
In this paper, take a preliminary step towards this and ask the question of parameter identifiaiiltyy assuming the data comes from a ground truth parametric probabilistic model, can common self- supervised tasks uniquely identify the parameters of the ground truth model? More precisely, are the parameters of the model uniquely determined by the optimal predictor for the SSL task (Definition ? An appeal of this identifiability perspective is that when SSL task is sufficient for parameter identifiability, the model parameters can then be recovered straightforwardly from the parameters from the optimal SSL predictor. Parameter identification also has the desirable property of being independent of any downstream task.
A priori, it is unclear whether we can achieve such model parameter identifiability via self self-supervised tasks, since requires recovering the full (parametric) generative model which is arguably more difficult than learning generic latent representations. This work provides positive answer for broad
classes of HMMs: we show that the commonly-used masked prediction task (Pathak et al.] (0166]
Devlin et al. 2018 He et al., 1 Lee et al., 2021a], wherein model is trained to predict masked-out part of a sample given the rest of the sample, can identify the parameters of a HMM. As noted earlier, while such masked prediction for parameter learning has been applied in classical settings such as Ising models [Ravikumar et al.] 2010) (resser 2015) Vuffray et al. 2016). the HMM setup in this work is more challenging due to the presence of latent variables. HMMs are also more
suitable for modeling practical sequential data, and have been commonly adopted in theoretical analyses clean proxy for languages (Wi et al. 2021 Xie al. 2021].
Concretely, the two HMM models we consider in this work are 1) the classic HMM with discrete latent and discrete observables, and 2) HMM variant with discrete latents and continuous observables that are conditionally Gaussian given the latent, which we abbreviate as G-HMMs. We show that:
Parameter identifiability is governed by the difficulty of the masked prediction task. The task difficulty is related to the amount of information provided by the combination of the model and the prediction whheee the difficulty can be increased by using more complicated model, or by predicting more tokens. For instance, predicting the conditional mean of one token given another does not yield identifiability for discrete HMM (Theorem 2). but does so when data comes from a G-HMM (Theorem 33.. Moreover, the identifiability in the latter case quite strongly leverages structural properties of the posterior of the latent variables (Section 3.1).
Tools for characterizing the uniqueness of tensor decompositions (e.g.. Kruskal's Theorem [ruskal 1977 Allman et al. (009)) ) can be leveraged to prove identifiability: For both HMM (Theorem and G-HMM (Theorem 6). if we have predictors of the tensor product of tokens (e.g., E[ [r] we can use the predictor output to construct a 3-tensor whose rank-1 components are uniquely determined and reveal the parameters of the model.
The rest of the paper is structured as follows. Section[]provicee relevant definitions, preliminaries and assumptions. Section 3 states the main results of this work. Main proofs, including the identifiability proof via tensor decomposition, We then discuss related works in Section[3] Finally, we emphasize that this work a first-cut study on this lens of parameter recovery for analyzing SSL tasks based on masked prediction, and our encouraging results suggest interesting open directions in this thread of analyzing self-supervised learning via parameter recovery, which are discussed briefly in the conclusion.
provided in Section 4 with the rest deferred to the appendix.

---

2 Setup
This work focuses two classes of latent- variible sequence models. The first are fully discrete hidden Markov models (HMMs), and the second are HMMs whose observables marginally follow mixtures of Gaussians with identity covariance. We denote the observations and hidden states respectively by { he21 and (h+)22 for both classes The hidden states h1 + h2 > ... form Markov chain, and conditional on he, the observable H; independent of all other variables. Throughout, we refer to {It h221 as tokens, following the nomenclature from language models.
2.1 Models
Discrete Hidden Markov Model with discrete latents and observations. Let X' (1, , ,.. [d] denote the observation space, and let H = [k] be the state space The parameters of interest are the transition matrix T <R and
We first describe the parameterization of the standard HMMs
the emission matrix O E Rdxk defined in the standard way
P(h = i he = j) = Tip.
P(x₂ = i 11 j) = O
Conditionally-Gann Gaausssinn HMM (G-HMM) We next describe the parameterization of conditionally-Gasse Gaussian HMMs (G-HMMs). The state space H == [k] is the same as in the pre- vious case, while the observation space is now continuous with X == Rd. The parameters of interest are T E [ the transition matrix, and {Mihiej C RR, the means of the k identity-covariance Gaussians. Precisely,
P(h+1 i he j) Tij.
P(#, = h4 (2x) exp (- || 11l13/22 /2)-
We use M = jui...., us] E Rddk to denote the matrix whose columns are the Gaussian means.
2.2 Masked prediction tasks
We are interested in the (regression) task of predicting one or more "masked out" tokens as a function of another observed token, with the goal of minimizing expected squared loss under distribution given by an HMM or G-HMM (equation [ In the case the discrete HMMs, we will specifically be predicting the one-hot encoding vectors of the observations. Thus, both for HMM and G-HMM, predicting single token will correspond to predicting a vector. For notational convenience, we will simply associate the discrete states observations via their one-hot vectors fei, ..,...) in the appropriate space and interchangeably write = or = G₁, and similarly for x. For the task of predicting the tensor product of (one-hot encoding vectors of) tokens 8reT I, from another token t, (where T is some index set and I. & T), the optimal predictor with respect to the squared loss calculates the conditional expectation:
f(xx) = arg min Egarlrer //ve -.) B
vec(f(x:))11 = E[ Hr [x]] (RdysITI, (1)
where "vec" returns the vectorized form of a tensor.
We use the shorthand " |z," to refer to this prediction task. For instance, consider the case of predicting 22 given Φ under the HMM with parameters (0, (O, The optimal predictor, denoted by f211, can be written in terms of (O,T) as
f (z)
B B[r
I1 = x|
Eizz h2 P) = 21 x)
6E
On.j EiEM On!
Σ jE(k
Σ
E[22| 122 = i h1 = j) P(h =
Σ
OTT
SE(K)
[o(x))s
:=(0(x)1
OOur results will assume d 2 l;; see Section "The computation here relies on Assumption given in Section 2.3
3

---

Here Φ : F + R denotes the posterior distribution of a hidden state hy given the corresponding observation Fy, ie.. (xx) [h, xy]
Our goal is to study the parameter identifiability from the prediction tasks, when the predictors have the correct parametric form. Formally, we define identifiability from prediction task as follows:
Definition (Ideniiiiability from a prediction task, HMM), A prediction task suffices for identifiability if. for any two HMMs with parameters (O, and (Ō, .), equality of their optimal predictors for this task implies that there is a permutation matrix II such that O = ÔT and T == II III.
In other words, the mapping from (the natural equivalence classes of) HMM distributions optimal predictors for a task is injective, up to a permutation of the hidden state labels. By identifiability from a collection of prediction tasks, we refer to the injectiveness of the mapping from HMM distributions to the collections of optimal predictors for the tasks. Identifiability for G-HMMs is defined analogously with O, Ô changed to M, M.
2.3 Assumptions
We now state the assumptions used in our results. The first assumption is that the transition matrices of the HMMs are doubly stochastic.
Assumption (Doubly stochastic transitions). The transition matrix T is doubly stochastic, and the marginal distribution of the initial hidden state h1 is stationary with respect to T.
This assumption guarantees that the stationary distribution of the latent distribution is uniform for any and the transition matrix for the reversed chain simply T Moreover, this assumption reduces the parameter space and hence will make the con-identifiability results stronger.
We require the following conditions on the parameters for the discrete HMM:
Assumption 2 (Non-redundancy, discrete HMM). Every row of O is non-zero.
Assumption 2 can be interpreted as requiring each token to have non-zero probability of being observed, which is a mild assumption. We also require the following non-degeneracy condition: Assumption 3 (Non-degeneracy, discrete HMM). rank(T") rank(O) (O) = k < d.
Note that Assumption only requires the parameters to non-degenerate, rather than have singular values bounded away from O. The reason is that this work will focus on population level quantities and make no claims on finite sample behaviors or robustness.
For G-HMM, we similarly require the parameters to be non-degenerate: Assumption (Non-degeneracy, G-HMM). rank(T)) = rank(M) s d.
Moreover, we assume that the norms of the means are known and equal: Assumption 5 (Equal norms of the means). For each i [k], μ4 is unit vector
Assumptions are fairly standard [see, .ng.dkaraduumar et al. 2012]; in particular, Assumption 3 4 are required to enable efficient learning, since learning degenerate HMMs can be computationally hard Mossel and Roch 2005). Assumption 5 may be an artifact of our proofs, and it would be interesting to relax future work.
Our notion of identifiability from a prediction task (or a collection of prediction tasks) will restrict attention to HMMs satisfying Assumptions and and G-HMMs satisfying Assumptions
2.4 Uniqueness of tensor rank decompositions
Some of our identifiability results rely on the uniqueness of tensor rank-1 decompositions [Hitchcock] 1927]. An order-t tensor (or t-tensor) is an t-way multidimensional array; a matrix is a 2-tensor.
The tensor rank of a tensor W is the minimum number R such that W can be written as a sum of R
For discrete HMMs, ((x.) = O z1
For GHMMs, [d(ax)]; =
Vi E [R].
10 xel
Eys exp
does not need to indexed by due to stationarity assumption Section 2.3 Assumption 5 can be changed to |illa for all i [ks], for any other fixed number >> 0.

---

rank-1 tensors. That is, if I-tensor W has ank-RR, it means that W = EiE(R 8 for some matrices UG) E RR where U.Y) denotes the 7th column of matrix U0)
In this work, we only need work with 3-tensors of the form W = EiERR 4 B, @ C for some matrices A E IR x B E T C E R as 3-tensors will suffice for identifiability in all of our settings of interest classic work by Kruskal 1977] gives a sufficient condition under which permutation and scaling. The condition is stated in
A, B, C can be recovered up to column-wis terms of the Kruskal rank, which the maximum number r such that every r columns of the matrix are linearly independent. Let k denote the Kruskal rank of matrix A, then:
Proposition 1 (Kruskal's theorem, Kruskal (1977). The components A, C of 3-tensor W == EiERR) A, & B, @ C₁ are identifiable up to a shared column-wise permutation and column-wite scaling if A + kB + kc 2 2R +2
We note that this work focuses on identifiability results rather than providing an algorithm or sample complexity bounds. though the proofs can be adapted into algorithms [see, e-g.. "g..|maahmman [970] under slightly more restrictive conditions (which will be satisfied by all of our identifiability results).
3 Identifiability from masked prediction tasks
We now present the main tion-)idenifiiabiiity results, and show that the combination of the data generative models and the prediction task directly impacts the sufficiency of identifiability.
3.1 Pairwise prediction
We begin with the simplest prediction task: namely predicting one token from another. We refer to such tasks as pairwise prediction tasks. For HMMs, this task fails to provide parameter identifiability:
Theorem (Nonidentifiabiiiiyy of HMM from predicting Te (e(2x)). For any t Z, 2, there exists
pair of HMM distributions with parameters (O, I') and (Ö, T), each satisfying Assumptions 1 and
3 such that the optimal predictors for the task x I are the same under each distribution, but there
is no permutation matrix II E k such that Ô OII and T = II TII are both satisfied.
Theorem 2 follows from the fact that the optimal predictor has the form of a product of (stochastic) matrices, and generally, one cannot uniquely recover matrices from their product sans additional conditions [Donoho and Elad| 2003 Candes al. 2006, Spielman et al. 2012 Arora al. 2014
Georgiev et al. 2005 Aharon et al. 2006]]Cohen CCohen and Gillis, 2019). Specitically, by equation I the OT (z1)) (where ((x1) == E/ [22] is the posterior). When & = 2, we can find non- non-permutation matrix R such that Ô OR, t = RTR give the same predictor as O,T. T. For t 2, even if Ô O, show that the matrix power 7 is not identifiable:
optimal predictor is (111 = 21
Claim (Nonidentifiability of matrix powers). For any t E Z, t > 2, there exist stochastic matrices T, í satisfying Assumption such that T + T and T = Tt.
On the other hand, pairwise prediction actually does suffice for identifiability for G-HMM:
Theorem 3 (Identifiability of G-HMM from predicting x22 12) Under Assumption 7 4 and if the optimal predictors for the task 222 under the G-HMM distributions with parameters (M, and (M,T) are the same, then (M,T) = (M, T) up to permutation of the hidden state labels.
Comparing Theorem and 3 shows that the specific parametric form of the generative model matters. Note that HMM and G-HMM have similar form when conditioning on the latent variable; that is, with 2, the predictor conditioned on the hidden variable h2 is P' ha = i) OT, for HMM, and P(rz/he i) = MT, for G-HMM. The salient difference between these two setups lies in the posterior function: while the posterior function for HMM is linear in the observable, the posterior function for G-HMM is more complicated and "reveals" more information about the parameter.
STo apply our results higher order tensors, consider an order-3 slice of the higher order tensor.
5

---

To formalize the above intuition, first recall that the GHMM posterior has entries [o(x)]]
1= )
oxp
Vi [k:. We will show that for G-HMM, even matching the posterior
Eye()) exp
function nearly suffices to identify M: if M, . parameterize two posterior functions &, ø where Φ. then up to a permutation, MM must be equal to either M or a unique (and somewhat special) transformation of M. The next step is to further exclude the (special) transformation, which is achieved using the constraint that T, T are stochastic matrices. The first step of the proof sketch is captured by following lemma:
Lemma 1. For d 2 k 2 2, under Assumption 4 5 Ø = ã implies M = M or M = HM, where H
a Householder transformation of the form H La 260 BRdxd with é VI (A
(M")
To provide some geometric intuition about how H acts on M, note that ē is a unit vector in the column space of M and perpendicular to the affine hull of A := {14 [k]]. which means ê μu is the same for all E [k.] As result, M/ [ū,,.... ju.,....pu.. [xx] [H, Hp M 2 p1) 6] is translation of M along the direction of é, such that the translated points {icher lie on the opposite side of the origin.
non-trivial to argue that HM is the only solution (other than M itself) that preserves Ø, and we defer the proof to Appendix A.1.2 It is, however, easy to see that HM indeed results in matching posterior, whose sufficient conditions are 1) M is translation of M, and 2) || - || is the same for all i E [k]. M == HM indeed satisfies both conditions.
Proof sketch for Theorem 3 We first show that if M, T and M produce the same predictor, then their posterior function must be equal up to permutation (Lemma We can then apply Lemma to recover M up to a permutation and a Householder transformation H. Then, we show that M =
HM, then the corresponding T must have negative entries and thus would not be a valid stochastic matrix. Hence it must be that M, MM are equal up to permutation.
Finally, by way of remarks, another way to think of the difference between the two setups is that for HMM, 11 is mixture of categorical distributions, which itself is also a categorical distribution. This also implies that the nonidentifiability from pairwise prediction in the HMM case cannot be resolved by changing the squared loss another proper loss function. On the other hand, for G-HMM, the conditional distribution P( is a mixture of Gaussians, which is well known to be identifiable. In fact. if we were given access to the entire conditional distribution P (x1) (instead of just the conditional mean), it is even easier to prove identifiability for G-HMM. Though this is already implied from identifiability from the conditional means, we provided a (much simpler) proof in Appendix A.3 assuming access to the full conditional distribution.
3.2 Beyond pairwise prediction
The conclusion from Theorem Dis is that single pairwise prediction task does not suffice for identifia- bility on HMMs. The next question is then: can we modify the task obtain identifiability? A natural idea is to force the model to "predict more", and one straightforward way to do so is to combine multiple pairwise prediction tasks. It turns out that this does not resolve the nonidentifiability issue, as we can show that the parameters are not identifiable even when considering all possible pairwise tasks involved 3 (adjacent) tokens:
Theorem (Nonidentifiability of HMM from all pairwise predictions on 3 tokens). There exists pair of HMM distributions with parameters (O,T) and (Ó, TT, each satisfying Assumptions i and 3 and also Ô + O, such that, for each of the tasks 22|ø11 Iı [22, 23 [1, and x 113, the optimal predictors are the same under each distribution! 0
We briefly remark that the reason for only considering adjacent time steps is that when the tokens are at least two time steps apart, matching predictors only matches powers of the transition matrices, which in general does not ensure the transition matrices themselves are matched as shown in Claim
"These pairwise tasks cover all possible pairwise tasks on 3 adjacent tokens. In particular, there is no need consider 22/23 or æ3 222 since they are the same æ1 21|22 and 22 2r.

---

For the intuition of the nomidentifiability result in Theorem 4 recall that the limitation of pairwise predictions on HMMs comes from non-uniqunn non-uniqueness of matrix factorization. While adding additional pairwise prediction tasks introduces more equations on the product of matrices, these equations are highly dependent, and the proof works by providing counterexamples that can simultaneously satisfy all these equations.
The above intuition leads to another way of forcing the model to "predict more", that is, to increase the number of predicted tokens. The hope is that doing so results in equations on tensors- as opposed to matrices for which there is lot of classical machinery delineating tensors for which the rank- I decomposition is unique, as discussed in Section 2.4 This intuition proves to be true and we show that increasing the number from to 2 already suffices for identifiability:
Theorem (Identifiability from masked prediction on three tokens, HMM). Let (t1, t22 tx) be any
permutation of 2,3,, and consider the prediction task 21, Itg L Under Assumption 7 2 3
the optimal predictors under the HMM distributions with parameters (O,T) and (0, T) are the
same, then (O,T) = (Ö, T) up to a permutation of the hidden state labels.
Compared to prior results on identifiability from third order moments [Allman et al., 2009 Anand
kumar et al. 2012 2014], the difficulty in our setup is that we only have access to the conditional 2-tensors (i.e. matrices) given by the predictors. The proof idea is to construct a third-order tensor by linearly combining the conditional 2-tensors for each possible value of the token being conditioned on, such that Kruskal's 's theorem applies and gives identifiability. Note, importantly, that the weights for the linear combination cannot depend on the marginal probabilities of the token being conditioned on, since we do not have access to these marginals, and it is unclear whether we could extract unique marginals given the conditional probabilities we predicting. Thus, the above theorem cannot be simply derived from results showing parameter identifiability from the 3rd order moments.
It can be show that this tensor decomposition argument can also be applied to G-HMM, with the help of Lemma We leave the details to Theorem G Appendix
Proofs
We now discuss proofs for some of the main results. Section 4.1
proves the identifiability of HMM parameters from the task of predicting two tokens (Theorem(5) using ideas from tensor decomposition, and Section 4.2 shows the identifiability proof of pairwise prediction on G-HMM. The rest of the proofs are deferred to the appendix.
4.1 Proof of Theorem 5: identifiability of predicting two tokens for HMM
There are three cases for the two-token prediction task, i.c. 1) 22 @ #1, 2) #1 @ Ig Ø2, and 3) Ii & 12 We will prove for the first two cases, as the third case is proved the same way as the first case by symmetry. In all cases, the idea is to use the predictor to construct a 3-tensor whose components are each of rank-k, so that applying Kruskal's 's theorem gives identifiability.
Case 1, x2 8 wa l O,T and Ô, T. producing the same predictor means 128811(x) = E[x² @ 1g|æ1] = E[zz @ [1/ææ1] := (283))(11), where E,, E are parameterized by the corresponding parame- ters. Let X == {er E [d]] and consider the following 3-tensor:
W Σ
xi & E[12 0glmn)
Σ SIE
.i Eagla
E[pz @0 235 h2]
Σ P( 1111) @ E[zz/h2
E/2
KETA] E
(2)
Σ
Σ (TŌ(Z)))
22 (0T);
KE(M]
ZIEX
1

---

where O, denotes the th column of O, and similarly for (OT); Note that W can also be written as
W = Σ 2 8 0 = Σ *E|A
Σ 2IE2'
(Tó(z1)) e x1 @ Ō @ (ÔT),
ZIEZ
We want to apply Kruskal's theorem for identifiability. In particular, will show that each component in equation forms a matrix of Kruskal rank k. The second and third components clearly satisfy this condition by Assumption For the first component, recall that <(x))
O z and write a;
T (K) ei o diag (1ic))) TOl Lee OT (8) 0; = Σ (T((E)
(4)
jELd
Putting d, into matrix form, we get A (,,, un] diag (1//I(( Tolll)sta))
which
of rank 1: by Assumption 3 Hence components W are all of Kruskal rank k. and columns of OT, O are identified up to column-wise permutation and scaling by Kruskal's theorem. The indeterminacy in scaling is further removed noting that columns of O, need to up Lastly, T is recovered as T O'O..
Case 2, @ x2: The optimal predictor for the task of predicting æ 2a given 2g takes the form
(5) Similarly as the previous case, would like to construct 3-tensor whose components can be uniquely determined by Kruskal's theorem. Let X the same as before, and consider the 3-tensor
E[ wy [12] (OT (d)ag(
W Σ
22
23
Σ 2EE
D2 & Englaz (E(ri|ha)
E E[z (b2))
xEE
Σ
Σ
(0(2)))
(k) 22
3E x ha] [b2
Σ a @ (OT"), (OT), KE[M]
(6)
(E(A)
where the first component can be simplified
(c) )o
a: Σ Ie (ee 0
(k) ee, (ddigg(( (allset)) "'ee := D=
g000
(7)
jEId
The matrix A = (ai,..., ax) D-11--1- is of rank k, hence we identify (up to permutation) columns of each component of W by Kruskal's 's theorem. This means if O,T and Ô, Ö,T produce the same predictor, then have OT Öf, OT ÖT and that O, Ô are matched up to scaling of rows (i.e. D-1). Next, to determine D. note that T, T are doubly stochastic by Assumption 1 which means the all-one vector
Ø* satisfies 7'1 T1 1. Hence ÔT1 OT1 O1 [[[O, [| We can then compute D D diag OOTT), and recover O O DA. Finally, T also recovered since ÔT OT = OT TT 4 + =T
4.2 Proof of Theorem
3 identifiability of predicting 22 given Tj for G-HMM
For G-HMM, the predictor for 22 given 21 is parameterized as f2))(x]) E[x2|11] MT If M, T and M, T produce the same predictor, then
f MTd(z)= = MTT(x) = fx) Vo e Rd.
Let R = (MT) R then δ(x) Rő(x). The following lemma (proof deferred to Appendix A.1) says that o, Ø must then be equal up permutation of coordinates:
Lemma 2. If there exists non-singular matrix R k such that (xx) RŌ(x), Vr Rd. then R must be permutation matrix.
We use jasleetd to denote d-dimensional vector whose hhh entry is as.

---

Combined with Lemma we have M is equal to (up to a permutation) either M or HM, where H the Householder reflection given in Lemma
The remaining step is to show that HM can be ruled out by requiring 7 to be stochastic matrix. Note that matching both the predictor and the posterior function means we also have MT = MT, or T = (M M)T. Recall that H == Is 200 for i V (ATMIT
(M')
When M = HM, the
column sum of M M is
1 M'M M = 1 M= 11 (I 2000 JM = 1' (1 - 2M T M)
=1 2.1 ( 111 M =1- - [M(( 1 =1
1 -2 = -11
1 (MMM
1 MM
This means the column sum of T is 1 = IT = which violates the constraint that 7 should be a stochastic matrix with positive entries and column sum 1. Hence it must be that M M and hence also T = 7 (up to permutation), proving the theorem statement.
5 Related works
Self-supervised learning On the empirical side, self-supervised methods have gained a great
amount of popularity across many domains, including language understanding Miikolov et al.; 2013
Vaswani et al. 2017 Devlin et al.] 2018]. visual understanding [Doersch et al.
|015||athaa Pathak et al.
2016), and distribution learning [Gutmann and Hyvärinen 2010 Gao et al. 2020 Classic ideas such
contrastive learning (Hadsell et al.) 2006 Gutmann and Hyvärinen 2010 Dosovitskiy al.) 2014
and masked prediction [Mikolov et al. | [2013] remain powerful in their modern realizations Hénnff
al. 2019 Chen et al. 2020b Devlin al. 2018 Radford et al.) 2019 Chen al.
2020a He et al.
2021 pushing the state of the art performance and even surpassing supervised pretraining in various
aspects
[Lee al. 2021b Liu al. 2021]
On the theoretical front, there have been analyses on both masked predictions [Lee et al. 202 a Zhang and Hashimoto [021]] and contrastive methods [Arora et al.) 2019 Tosh et al.) 2020a b
Wang and Isola| 2020, HaoChen et al., 202T, Wen and 2021]. with a focus on characterizing the quality of the learned features for downstream tasks (Saunshi et al. 2020, Wei et al. 202T]. These approaches usually rely on quite strong assumptions to tie the self-supervised learning objective to the downstream tasks of interest. In contrast, our work takes the view of parameter identifiability, for which there is no need for downstream assumptions but instead the specific parametric form is key. Note also that while the parameter recovery lens is a new contribution of our work, Wen and Li [02T]] argue (as a side-product of their analysis) that some aspects of a generative model are recovered in their setup. Their data model, however, is substantially different from ours and has very different identifiability properties (owing to its basis in sparse coding).
Latent variable models and tensor methods Latent variable models have been widely studied in the literature. One important area of research is independent component analysis (ICA), where the data is assumed be given as transformation (mixing) of unknown independent sources which ICA aims to identify. In nonlinear ICA data models, both the sources and the mixing function are generally not identifiable. However, identifiability of the sources can be shown under some additional assumptions (e.g. on the dependency structure of different time steps) [Hyvarinen and Morioka| [0066] 2017 Hälvä and Hyvarinen] 2020). Similar ideas have also been applied in the self-supervised setting, where the latent variables can be identified under suitable assumptions on the conditional distribution of the latent (Zimmermann et al. 2021] or on data augmentations (Von Kügelgen et al. 2021). Unlike our setup though, the mixing function in these models is deterministic and not the object of recovery.
More related to this work is the line of work on learning latent variable models with tensor methods. Specific to learning HMMs, Mossel and Roch (2005) and Anandkumar et al. [001 2014) provide algorithms based on third-order moments. A major difference between these prior works on tensor methods and ours is that previous results operate on joint moments, while the results in this work are based on conditional moments given by the optimal predictors for the masked tokens.

---

Conclusion
In this work, we take model parameter identifiability view of self-supervised learning, which offers a complementary perspective to the current foeus of feature learning for downstream performance. By analyzing the masked prediction task in the setup of HMMs and its conditionally-Gauseee Gaussian variant G-HMM, we showed that parameter recovery is determined by the task difficulty, which can be tuned by both changing the parametric form of the data generative model, and by changing the masked prediction task.
We emphasize that this a first-cut effort in the research program of analyzing SSL through the lens of model identifiability; aim to build on this foundation extend analyses from HMMs to more complicated latent sequence and latent variable models. We also note that we have focused here on population analyses, and model identifiability. It would be of interest build off this to develop and analyze the corresponding finite-sample learning algorithms for parametric generative models given SSL tasks, with sample complexity results, both in the realizable case, well in the agnostic case where we have model mis mii-speciiiicttin. Given the use of conditional MLEs and regressions in SSL, and the natural robustness of these model siiisspeifiiaations we conjecture that these approaches will be much more robust when compared to say spectral methods.
Overall, we hope this work on alternative lens analyze SSL inspires further research.
Acknowledgement
The authors would like to thank Elan Rosenfeld for insightful discussions and comments. We acknowledge the support of ONR via N000141812861, NSF via I1S-1909811 16, IIS-1955532, IIS- 2211907, 156775,, a JP Morgan Faculty Award, and the CMU/PwC DT&I Center.
References
M. Aharon, M. Elad, and A. M. Bruckstein. On the uniqueness of overcomplete dictionaries, and a practical way to retrieve them. Linear algebra and its applications, 416(1):48-6) 2006.
E. S. Allman, Matias, and J. A. Rhodes. Identifiability of parameters latent structure models with many observed variables. The Annals of Statistics, 37(6A):3099-3111 -1322 2009.
A. Anandkumar, D. Hsu, and S. M. Kakade. A method of moments for mixture models and hidden markov models. In Conference on Learning Theory, pages 33-1. JMLR Workshop and Conference Proceedings, 2012.
A. Anandkumar, R. Ge, D. Hsu, M. Kakade, and M. Telgarsky. Tensor decompositions for learning latent variable models. Journal of machine learning research, 15:2773-2832, 2014.
S. Arora, R. Ge, and A. Moitra. New algorithms for learning incoherent and overcomplete dictionaries. In Conference Learning Theory, pages 779-806. PMLR, 2014.
S. Arora, H. Khandeparkar, M. Khodak, O. Plevrakis, and N. Saunshi. A theoretical analysis of contrastive unsupervised representation learning, arXiv preprint (rXiv:1902.09229, 2019.
G. Bresler. Efficiently learning ising models on arbitrary graphs. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 771 2015.
E. J. Candes, J. K. Romberg, and T. Tao. Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 59(8):1207-13 2006.
M. Chen, A. Radford, R. Child, J. Wu, H. Jun, D. Luan, and Sutskever. Generative pretraining from pixels. In International Conference Machine Learning, pages 1691-1703. PMLR, 2020a.
Chen, Kornblith, M. Norouzi, and Hinton. simple framework for contrastive learning of visual representations. arXiy preprint arXiv:2002.05709, 2020b.
10

---

J. E. Cohen and N. Gillis. Identifiability of complete dictionary learning. SIAM Journal on Mathe- matics of Data Science, 1(3):518-5333 536, 2019.
Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference computer vision and paltern recognition, pages leee, 2009.
J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: 04805, 2018.
C. Doersch, A. Gupta, and A. A. Efros. Unsupervised visual representation learning by context prediction. In Proceedings of the IEEE International Conference on Computer Vision, pages 1430-143,, 2015.
D. L.. Donoho and M. Elad. Optimally sparse representation general (nonorthogonal) dictionaries via ll minimization. Proceedings of the National Academy of Sciences, 100(5):2177-2202 2003.
A. Dosovitskiy, J. Т. Springenberg, M. Riedmiller, and T. Brox. Discriminative unsupervised feature learning with convolutional neural networks. Advances in neural information processing systems, 27, 2014.
R. Gao, E. Nijkamp, D. Kingma, Z. Xu, A. M. Dai, and Y. N. Wu. Flow contrastive estimation of emergy-based models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7518-7528, 2020.
Georgiev, F. Theis, and A. Cichocki. Sparse component analysis and blind source separation of underdetermined mixtures. IEEE transactions neural networks, 16(4):992-996 2005.
M. Gutmann and A. Hyvärinen. Noise-contrastive estimation: A new estimation principle for unnormalized statistical models. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pages 297-304. 2010.
R. Hadsell, S. Chopra, and Y. LeCun. Dimensionality reduction by learning invariant mapping. In 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'06) volume 2, pages 1735-1742. IEEE, 2006.
H. Hälvä and Hyvarinen. Hidden markov nonlinear ica: Unsupervised learning from nonstationary time series. In Conference on Uncertainty in Artificial Intelligence, pages 939-948. PMLR, 2020.
J. Z. HaoChen, C. Wei, A. Gaidon, and T. Ma. Provable guarantees for self-supervised deep learning with spectral contrastive loss. Advances in Neural Information Processing Systems, 34, 2021.
R. Harshman. Foundations of the parafac procedure: Model and conditions for an explanatory factor analysis. Technical Report UCLA Working Papers Phonetics 16, University of California, Los Angeles, Los Angeles, CA, 1970.
K. He, X. Chen, S. Xie, Y. Li, P. Dollár, and R. Girshick. Masked autoencoders are scalable vision learners. arXiv preprint arXiv:2111.06377 2021.
O. Hénaff, A. Srinivas, De Fauw, Razavi, C. Doersch, Eslami, and A. v. Oord. Data- efficient image recognition with contrastive predictive coding. arXiv preprint arXiv: 12X.::905..0922. 2019.
L. Hitchcock. The expression of tensor or a polyadic as sum of products. Journal of Mathematics and Physics, 6(1-4):164-188 1927.
A. Hyvarinen and H. Morioka. Unsupervised feature extraction by time-contrastive learning and nonlinear ica. In Advances in Neural Information Processing Systems, pages 3765-3773, 2016.
A. Hyvarinen and H. Morioka. Nonlinear ICA of Temporally Dependent Stationary Sources. In A. Singh and Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 460-469 PMLR, 20-22 Apr 2017. URL http:s::/pprccceeee ml r. w.w.pres/see. v54/
hyvarinen aateenl7a..ae

---

J. B. Kruskal. Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics. Linear algebra and its applications, 18(2):95-138, 1977.
J. D. Lee, Q. Lei, N. Saunshi, and J. Zhuo. Predicting what you already know helps: Provable sulf-supervised learning. Advances in Neural Information Processing Systems. 34, 2021a.
K.-H. Lee, A. Arna,, S. Guadarrama, J. Canny, and I. Fischer. Compressive visual representations. Advances in Neural Information Processing Systems, 34, 2021b.
B. G. Lindsay and P. Basak. Multivariate normal mixtures: a fast consistent method of moments. Journal of the American Statistical Association, 88(422):468 476, 1993.
H. Liu, J. Z. HaoChen, A. Gaidon, and T. Ma. Self-supervised learning is more robust to dataset imbalance. arXiv preprint arXiv:2110.05025, 2021.
T. Mikolov, K. Chen, G. Corrado, and J. Dean. Efficient estimation of word representations vector space. arXiv preprint arXiv: 2013.
E. Mossel and S. Roch, Learning nonsingular phylogenies and hidden markov models. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 366-375, 2005.
D. Pathak, P. Krahenbuhl. Donahue, T. Darrell, and A. A. Efros. Context encoders: Feature learning by inpainting. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2536 2544, 2016.
A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, I. Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
P. Ravikumar, M. J. Wainwright, and J. D. Lafferty. High-dimensionall ising model selection using I1-regularized logistic regression. The Annals of Statistics, 38(3): 2010.
N. Saunshi, S. Malladi, and S. Arora. A mathematical exploration of why language models help solve downstream tasks. In International Conference Learning Representations, 2020.
D. A. Spielman, H. Wang, and Wright. Exact recovery of sparsely-used dictionaries. In Conference on Learning Theory, pages 37-1. JMLR Workshop and Conference Proceedings, 2012.
A. Tamkin, Liu, R. Lu, D. Fein, C. Schultz, and N. Goodman. Dabs: A domain-agnostic benchmark for self-supervised learning. arXiv preprint arXiv:2/ 12202,, 2021.
C. Tosh, A. Krishnamurthy, and D. Hsu. Contrastive learning, multi-view redundancy, and linear models, 2020a.
C. Tosh, A. Krishnamurthy, and D. Hsu. Contrastive estimation reveals topic posterior information to linear models. arXiv preprint arXiv:2003.0223 2020b.
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, t.. Kaiser, and I. Polosukhin. Attention is all you need. In Advances in neural information processing systems, pages 5998-6008, 2017.
J. Von Kügelgen, Y. Sharma, L. Gresele, W. Brendel, B. Schölkopf, M. Besserve, and F. Locatello. supf-supe learning with data augmentations provably isolates content from style. Advances in neural information processing systems, 34: 14411-16666 2021.
M. Vuffray, S. Misra, A. Lokhov, and M. Chertkov. Interaction screening: Efficient and sample- optimal learning of ising models. Advances in neural information processing systems, 29, 2016.
A. Wang, A. Singh, J. Michael, F. Hill, O. Levy, and S. R. Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. arXiv preprint arXiv:1804.00 0.04111, 2018
A. Wang, Y. Pruksachatkun, N. Nangia, A. Singh, J. Michael, F. Hill, O. Levy, and S. Bowman. Superglue: stickier benchmark for general-purpose language understanding systems. Advances in neural information processing systems, 32, 2019.
12

---

T. Wang and P. Isola. Understanding contrastive representation learning through alignment and uniformity on the hypersphere. arXiv preprint arXiv:2005.10242 2020.
X. Wang, X. Chen, S. S. Du, and Y. Tian. Towards demystifying representation learning with non-contrastive self supfrvuue arXiv preprint arXiv:2110.04947, 2021.
C. Wei, S. M. Xie, and Ma. Why do pretrained language models help in downstream tasks? an analysis of head and prompt tuning, Advances in Neural Information Processing Systems, 34, 2021.
Z. Wen and Li. Toward understanding the feature learning process of self-supervised contrastive learning. International Conference on Machine Learning, page 11112-11122 2021.
S. M. Xie, A. Raghunathan, Liang, and T. Ma. An explanation of in-context learning as implicit bayesian inference. arXiv preprint ar Sediv:2/11.02000 1.02080, 2021.
X. Zhai, J. Puigcerver, A. Kolesnikov, P. Ruyssen, C. Riquelme, M. Lucie, J. Djolonga, A. S. Pinto, M. Neumann, Dosovitskiy, et large-scale study of representation learning with the visual task adaptation benchmark. arXiv preprint arXiv: 1910.04867, 2019.
T. Zhang and T. Hashimoto. On the inductive bias of masked language modeling: From statistical to syntactic dependencies. arXiv preprint arXiv: 104.05694, 2021.
R. S. Zimmermann, Y. Sharma, S. Schneider, M. Bethge, and W. Brendel. Contrastive learning inverts the data generating process. In International Conference on Machine Learning, pages 12979-12990. PMLR, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] The limitations and future directions are discussed in the conclusion section.
(c) Did you discuss ctions any potential negative societal impacts of your work? [N/A] This work is purely theoretical.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Assumptions are listed in Section 2.3 together with a discussion on their implications.
(b) Did you include complete proofs of all theoretical results? [Yes] Proofs for Theorem and are presented in Section 4 Missing proofs provided in Appendix A for GHMMs, and Appendix for HMMs.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
13

---

(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you' ro using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "wmpw2iycNYN", "reviewer": "Reviewer_gc3R", "summary": "The paper studies \"masked prediction\" tasks where some tokens in a sequence are predicted from another token, akin to the popular masked language models. The authors study identifiability under two data-generating processes: an HMM with discrete states and observations, and a \"G-HMM\" with discrete states and continuous observations with isotropic Gaussian emissions.\nThey show that pairwise predictions (e.g. x_2 | x_1) do not suffice to identify parameters in the discrete HMM, while they do suffice in the G-HMM. In the discrete case, they then consider predicting 2 tokens from another token, and show that identifiability is possible in this case, by using results from identifiability of certain tensor decompositions (Kruskal, 1977).", "questions": "A few questions:\n\n- it is stated that changing the loss wouldn't change the nonidentifiability result. What is the role of the loss for the identifiability results? e.g. would the softmax/cross-entropy loss also work for the discrete case?\n\n- a related three-token setting could be to predict one token from two other tokens. Would this also provide identifiability? More generally, can anything be said about generic masking, e.g. masking 40% of a sentence? It would be helpful to comment on what could make this useful, e.g. a richer latent structure than HMMs.\n\n- what would break down if you drop the k <= d constraint?\n\n- regarding links to ICA in the related work, this more recent [paper](https://arxiv.org/abs/2006.12107) also seems relevant for the HMM model.\n\nminor typos:\n- L160/161: $r \\to R$\n- L258 increase -> increasing?\n- L289: end sentence before \"the second and third\"?", "limitations": "see weaknesses", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Given the increasing success of self-supervised pre-training tasks, and particularly of those based on masked prediction, this work is of significant and timely interest to the community, and presents novel results on identifiability of such masked prediction tasks in discrete and Gaussian HMMs, an interesting step towards understanding such tasks. The paper is also well written and provides thorough comparisons to related literature.\n\nExtensions to richer generative models beyond HMMs, or without the k <= d constraint, could make the work more impactful.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "t7WUHoyLfcW", "reviewer": "Reviewer_wW1j", "summary": "The traditional way to assess self-supervised learning algorithms is by designing downstream tasks which, if learning is to be deemed successful, will be solved with high accuracy; this way relies on features being learnt which will be useful to solving the downstream task. In contrast, this work provides a theoretical contribution to the understanding of SSL by assessing performance on the task of identifying the parameters of a realizable model (i.e. a model from a class assumed to contain the data-generating model). It does so on discrete- and Gaussian-valued HMMs, working out formal conditions for the identifiability from different types of training observations, such as predicting the mean of a token conditional on another one.", "questions": "Can you outline what is needed to turn this work into insights relevant to practical SSL uses? What is the pathway to impact?\nHow can the formal setup you use (HMMs, masked prediction tasks) be extended to sequence prediction models, neural seq2seq models?", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is very clear, the formalization has no unnecessary complications and the notation is clear and explained well. All arguments and proofs which I could check are correct and relevant. As such the paper provides, within its scope, a definitive answer to those questions it addresses.\nThe paper is relatively significant: understanding SSL is important because it is used so widely, yet understood so little. This paper is also original, as only little work takes an investigative approach different from \"assess SSL on downstream task performance\". \nOn the other hand, the setup under study is narrow and strongly simplified to support a formal investigation. Practical impact seems distant. The paper is limited to a theoretical investigation, which it solves well from an applied maths point of view, but does not venture into experimental work.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "fQzn3qBJTHD", "reviewer": "Reviewer_TcPc", "summary": "The authors propose a novel theoretical way of analyzing self supervised learning by model identifiability. HMM and Gaussian HMM models are assumed for latent space sequences. The proved theorems provide 3 main claims: non-identifiability in pair-wise prediction under HHM model on 2 and 3 tokens, identifiability of pair-wise predictions under G-HHM model, identifiability of masked pair-wise predictions on 3 tokens under HMM.", "questions": "I think it a typo in line 117: O_{x,j} should be O_{j, x} according to the definition in line 96\n", "limitations": "The limitation are discussed properly both in conclusion and paper body (e.g. Assumption 5)", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- First effort of analyzing self supervised learning by model identifiability \n\n- Formulated and proved the theorems that could be a foundation of the identifiability analysis of SSL\n\nWeaknesses:\n- It could be easier to follow the analysis if some additional examples were added that \n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "BoIvl_tpOhB", "reviewer": "Reviewer_RbEr", "summary": "\nThis paper investigates the identifiability of latent stochastic generative parameters in the context of masking self-supervised prediction tasks. This is a theoretical contribution; this work does not provide experimental results on how well these findings hold in practice when training masking prediction tasks but shows under what conditions an optimal predictor allows the identification of latent parameters (experimental simulations in the appendix). \n\nThis paper looks at identifiability guarantees of parametric generative models when training self-supervised learning tasks. In particular, the paper focuses on:\n- Hidden Markov models: sequential stochastic generative models of two types a) discrete HMM where both hidden states and observations are discrete b) Gaussian HMM where hidden states are discrete and observations follow a conditional Gaussian distribution. In addition, a set of assumptions (stochasticity of transitions, non-redundancy & non-degeneracy of transitions and emissions, equality of norms of observation means) on the HMMs are defined.\n- Masking Prediction tasks: the paper focuses on the self-supervised learning task of using part of a sequence of observations to predict the missing part of the sequence.\n\nThe contributions of the paper are the following:\n- gives identifiability results for G-HMM\n- gives identifiability results for discrete HMM for multi-sequence predictions tasks using the uniqueness of tensor rank decomposition and Kruskal's identifiability theorem.", "questions": "Questions related to limitations were added to the limitations section. \n\n\nTypos:\n- line 252\n- line 255 \n- line 206\n- line 52\n- line 114", "limitations": "The authors briefly mention that extending to more complex latent variable models and trying to relax assumption 5 are potential extensions of this work that would address some of the limitations. \n\nThe authors focus on the predictive tasks where one input observation/token is used to predict one output observation/token. In practice, masking prediction tasks often consider multiple time steps sequence predictions (multiple time-steps in the input & output). Would this setup be a limiting case for this work? Do the authors have some intuition on whether the identifiability results presented in this paper can be extended to this practical setup?\n\nDisclaimer: I would like to mention that I do not have a theoretical background, I did go through most of the proofs and based on my knowledge tried to assess the soundness of the approach.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n- as mentioned by the authors, identifiability allows for reducing the assumptions under which performance of the (self-supervised) method holds, in particular assumptions on the downstream performance. Better understanding under which conditions the underlying generative parameters are identifiable is valuable to the field; This work contributes to answering these questions for the case of masked predictive tasks which are commonly used tasks in the field when working with sequential data. \n- linked to the previous comment, this work is well motivated and put into context. The motivation behind why identifiability guarantees are valuable is well stated/written. The contributions in comparison to prior art in the field of self-supervised learning and non-linear ICA are also clearly stated (see comment below regarding completeness of the literature review).\n- the parametric models considered in this work are quite simplistic setups but remain relevant/realistic and the majority of the set of assumptions (set aside the equality of norms of means - assumption 5) are mild.\n\nWeaknesses:\n- as briefly mentioned below, the considered setup is restricted to simple latent variable models which might not hold in practical settings \n- the authors claim that one contribution of this work is to propose an alternative parameter identifiability lens for evaluating self-supervised settings. Whilst the specific models and tasks considered in this paper might be novel, the identifiability of generative models in self-supervised learning setups have been investigated in the past and well-motivated. In the case of contrastive learning & non-linear ICA it is worth mentioning the works of Zimmermann et al. 2020 and von Kügelen et al. 2021 which are not present in the references.  \n\n\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept