Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
They 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).
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.

Extensions to richer generative models beyond HMMs, or without the k <= d constraint, could make the work more impactful.
questions: A few questions:

- 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?

- 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.

- what would break down if you drop the k <= d constraint?

- 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.

minor typos:
- L160/161: $r \to R$
- L258 increase -> increasing?
- L289: end sentence before "the second and third"?
limitations: see weaknesses
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
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.
The 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". 
On 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.
questions: Can you outline what is needed to turn this work into insights relevant to practical SSL uses? What is the pathway to impact?
How can the formal setup you use (HMMs, masked prediction tasks) be extended to sequence prediction models, neural seq2seq models?
limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: 
This 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). 

This paper looks at identifiability guarantees of parametric generative models when training self-supervised learning tasks. In particular, the paper focuses on:
- 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.
- 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.

The contributions of the paper are the following:
- gives identifiability results for G-HMM
- gives identifiability results for discrete HMM for multi-sequence predictions tasks using the uniqueness of tensor rank decomposition and Kruskal's identifiability theorem.
strengths_and_weaknesses: Strengths: 
- 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. 
- 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).
- 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.

Weaknesses:
- as briefly mentioned below, the considered setup is restricted to simple latent variable models which might not hold in practical settings 
- 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.  



questions: Questions related to limitations were added to the limitations section. 


Typos:
- line 252
- line 255 
- line 206
- line 52
- 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. 

The 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?

Disclaimer: 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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:

- First effort of analyzing self supervised learning by model identifiability 

- Formulated and proved the theorems that could be a foundation of the identifiability analysis of SSL

Weaknesses:
- It could be easier to follow the analysis if some additional examples were added that 

questions: I think it a typo in line 117: O_{x,j} should be O_{j, x} according to the definition in line 96

limitations: The limitation are discussed properly both in conclusion and paper body (e.g. Assumption 5)
review_title: null

Meta-review: metareview: This work investigates a theoretical way to analyze self-supervised learning. The identifiability of latent stochastic generative parameters in the context of masking self-supervised prediction tasks is investigated, where HMM and Gaussian HMM models are assumed for latent space sequences. The 3 main claims are proved by theorems. The paper does not provide experimental results in the main paper on how well the findings hold in practice, but experimental simulations are provided in the appendix. 

I suggest accepting the paper, as it deals with an important topic in understanding SSL and it is of significant and timely interest to the community by presenting novel results on the identifiability of masked prediction tasks in discrete and Gaussian HMMs. Although the setup is a little narrow and strongly simplified, the paper is original enough. Further, the paper is well written and provides thorough comparisons to related literature. In future work, addressing practical impact would be a nice addition. 

confidence: Certain
Decision: Accept