Venue: ICLR 2018 conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: [After rebuttal]: 
I appreciate the effort the authors have put into the rebuttal, but I do not see a paper revision or new results, so I keep my rating.

---

The paper proposes “Generative Markov Networks” - a deep-learning-based approach to modeling sequences and discovering order in datasets. The key ingredient of the model is a deep network playing the role of a transition operator in Markov chain, trained via Variational Bayes, similar to a variational autoencoder (but with non-identical input and output images). Given an unordered dataset, the authors maximize its likelihood under the model by alternating gradient ascent steps on the parameters of the network and greedy reordering of the dataset. The model learns to find reasonable order in unordered datasets, and achieves non-trivial performance on one-shot learning. 

Pros:
1) The one-shot learning results are promising. The method is conceptually more attractive than many competitors, because it does not involve specialized training on the one-shot classification task. The ability to perform unsupervised fine-tuning on the target test set is also appealing.
2) The idea of explicitly representing the neighborhood structure within a dataset is generally interesting and seems related to the concept of low-dimensional image manifold. It’s unclear why does this manifold have to be 1-dimensional, though.

Cons:
1) The motivation of the paper is not convincing. Why does one need to find order in unordered datasets? The authors do not really discuss this at all, even though this seems to be the key task in the paper, as reflected in the title. What does one do with this order? How does one even evaluate if a discovered order is good or not?
2) The one-shot classification results are to me the strongest part of the paper. However, they are rushed and not analyzed in detail. It is unclear which components of the system contribute to the performance. As I understand the method, the authors effectively select several neighbors of the labeled samples and then classify the remaining samples based on the average similarity to these. What if the same procedure is performed with a different similarity measure, not the one learned by GMN? I am not convinced that the proposed method is well tuned for the task. Why is it useful to discover one-dimensional structure, rather than learning a clustering or a metric? Could it be that with a different similarity measure (like the distance in the feature space of a network trained on classification) this procedure would work even better? Or is GMN especially good for this task? If so. why?
3) The experiments on dataset ordering are not convincing. What should one learn from those? There are no quantitative results, just a few examples (and more in the supplement). The authors even admit that “Comparing to the strong ordering baseline Nearest Neighbor sorting, one could hardly tell which one is better”. Nearest neighbor with Euclidean metric is not a strong baseline at all, and not being able to tell if the proposed method is better than that is not a good sign.
4) The authors call their method distance-metric-free. This is strange to me. The loss function used during training of the network is a measure of similarity between two samples (may or may not be a proper distance metric). So the authors do assume having some similarity measure between the data points. The distance-metric-free claim is similar to saying that negative log-likelihood of a Gaussian has nothing to do with Euclidean distance. 
5) The experiments on using the proposed model as a generative model are confusing. First, the authors do not generate the samples directly, but instead select them from the dataset - this is quite unconventional. Then, the NN baseline is obviously doomed to jump between two samples - the authors could come up with a better baseline, for instance linearly extrapolating based on two most recent samples, or learning the transition operator with a simple linear model. 
6) I am puzzled by the hyperparameter choices. It seems there was a lot of tuning behind the scenes, and it should be commented on. The parameters are very different between the datasets (top of page 7), why is that? Why do they have to differ so much - is the method very unstable w.r.t. the parameters? How can it be that b_{overlap} = b ? Also, in the one-shot classification results, the number of sampled neighbors is 1 without fine-tuning and 5 with fine-tuning - this is strange and not explained.
7) This work seems related to simultaneous clustering and representation learning, in that it combines discrete reordering and continuous deep network training. The authors should perhaps mention this line of work. See e.g. Yang et al. “Joint Unsupervised Learning of Deep Representations and Image Clusters”, CVPR 2016.

To conclude, the paper has some interesting ideas, but the presentation is not convincing, and the experiments are substandard. Therefore at this point I cannot recommend the paper for publication.
review_title: [updated] Reject - interesting ideas, but weak presentation and experiments

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper is about learning the order of an unordered data sample via learning a Markov chain. The paper is well written, and experiments are carefully performed. The math appears correct and the algorithms are clearly stated. However, it really is unclear how impactful are the results.

Given that finding order is important, A high level question is that given a markov chain's markov property, why is it needed to estimate the entire sequence \pi star at all? Given that the RHS of the first equation in section 3.2 factorizes, why not simply estimate the best next state for every data s_i?

In the related works section, there are past generative models which deserve mentions: Deep Boltzmann Machines, Deep Belief Nets, Restricted Boltzmann Machines,  and Neural Autoregressive Density Estimators.

Equation 1, why is P(\pi) being multiplied with the probability of the sequence p({s_i}) ? are there other loss formulations here?

Alg 1, line 7, are there typos with the subscripts?

Section 3.1 make sure to note that f(s,s') sums to 1.0, else it is not a proper transition operator.

Section 3.4, the Bernoulli transition operators very much similar to RBMs, where z is the hidden layer, and there are a lot of literature related to MCMC with RBM models.

Due the complexity of the full problem, a lot of simplification are made and coordinate descent is used. However there are no guarantees to finding the optimal order and a local minimum is probably always reached. Imagining a situation where there are two distinct clusters of s_i, the initial transition operator just happen to jump to the other cluster. This would produce a very different learned order \pi compared to a transition operator which happen to be very local. Therefore, initialization of the transition operator is very important, and without any regularization, it's not clear what is the point of learning a locally optimal ordering.

Most of the ordering results are qualitative, it would be nice if a dataset with a ground truth ordering can be obtained and we have some quantitative measure. (such as the human pose joint tracking example given by the authors)

In summary, there are some serious concerns on the impact of this paper. However, this paper is well written and interesting.




review_title: This paper is well written and experiments are carefully done. However it is unclear how impactful are the results.

final_score: rating: 4: Ok but not good enough - rejection
review_content: 
The authors deal with the problem of implicit ordering in a dataset and the challenge of recovering it, i.e. when given a random dataset with no explicit ordering in the samples, the model is able to recover an ordering. They propose to learn a distance-metric-free model that assumes a Markov chain as the generative mechanism of the data and learns not only the transition matrix but also the optimal ordering of the observations.


> Abstract
“Aiming to find such orders, we introduce a novel Generative Markov Network (GMN) which we use to extract the order of data instances automatically. ”
I am not sure what automatically refers here to. Do the authors mean that the GMN model does not explicitly assume any ordering in the observed dataset? This needs to be better stated here. 
“Aiming to find such orders, we introduce a novel Generative Markov Network (GMN) which we use to extract the order of data instances automatically; given an unordered dataset, it outputs the best -most possible- ordering.”

Most of the models assume an explicit ordering in the dataset and use it as an integral modelling assumption. Contrary to that they propose a model where no ordering assumption is made explicitly, but the model itself will recover it if any.

> Introduction
The introduction is fairly well structured and the example of the joint locations in different days helps the reader.  

In the last paragraph of page 1, “we argue that … a temporal model can generate it.”, the authors present very good examples where ordered observations (ballerina poses, video frames) can be shuffled and then the proposed model can recover a temporal ordering out of them. What I would like to think also here is about an example where the recovered ordering will also be useful as such. An example where the recovered ordering will increase the importance of the inferred solution would be more interesting..



2. Related work
This whole section is not clear how it relates to the proposed model GMN. Rewriting is strongly suggested. 
The authors mention Deep Generative models and One-shot learning methods as related work but the way this section is constructed makes it hard for the reader to see the relation. It is important that first the authors discuss the characteristics of GMN that makes it similar to Deep generative models and the one-shot learning models. They should briefly explain the characteristics of DGN and one-shot learning so that the readers see the relationship. 
Also, the authors never mention that the architecture they propose is deep.
 
Regarding the last paragraph of page 2, “Our approach can be categorised … can be computed efficiently.”:
Not sure why the authors assume that the samples can be sampled from an unmixed chain. An unmixed chain can also result in observing data that do not exhibit the real underlying relationships. Also the authors mention couple of characteristics of the GMN but without really explaining them.  What are the explicit and implicit models [1] … this needs more details. 

[1] P. J. Diggle and R. J. Gratton. Monte Carlo methods of inference for implicit statistical models. Journal of the Royal Statistical Society. Series B (Methodological), pages 193–227, 1984. 

“Second, prior approaches were proposed based on the notion of denoising models. In other words, their goal was generating high-quality images; on the other hand, we aim at discovering orders in datasets.” —>this bit is confusing. Do the authors mean that prior approaches were considering the observed ordering as part of the model assumptions and were just focusing on the denoising? 

3. Generative Markov models
First, I would like to draw the attention of the authors on the terminology they use. The states here are not the latent states usually referred in the literature of Markov chains. The states here are observed and should not be confused with the emissions also usually stated in the corresponding literature. There are as many states as the number of observations and not differentiation is made for ties. All these are based on my understanding of the model.

In  the Equation just before equation (1),  on the left hand side, shouldn’t \pi be after the `;’. It’s an average over the possible \pi.  We cannot  consider the average over \pi when we also want to find the optimal \pi.  The sum doesn’t need to be there. Shouldn’t it just be  max_{\theta, \pi} log P({s_i}^{n}_{i=1}; \pi, \theta) ?
Equation (1), same. The summation over the possible \pi is confusing. It’s an optimisation problem…

page 4, section 3.1: The discussion about the use of Neural Net for the construction of the transition matrix needs expansion. It is unclear how the matrix is constructed. Please add more details. E.g. use of soft-max non-linear transformation so that the output of the Neural Net can be interpreted as the probabilities of jumping to one of the possible states. In this fashion, we map the input (current state) and transform it to the probability gf occupying states at the next time step.

Why this needs expansion: The construction of the transition matrix is the one that actually plays the role of the distance metric in the related models. More specifically, the choice of the non-linear function that outputs the transition probability is crucial; e.g. a smooth function will output comparable transition probabilities to similar inputs (i.e. similar states). 

section 3.2: 
My concern about averaging over \pi applies on the equations here too. 

“However, without further assumption on the structure of the transitional operator..”—> I think the choice of the nonlinear function in the output node of the NN is actually related to the transition matrix and defines the probabilities. It is a confusing statement to make and authors need to discuss more about it. After all, what is the driving force of the inference? This is a problem/task where the observations are considered in a number of different permutations. As such, the ordering is not fixed and the main driving force regarding the best choice of ordering should come from the architecture of the transition matrix; what kind of transitions does the Neural Net architecture favour? Distance free metric but still assumptions are made that favour specific transitions over others. 

“At first, Alg. 1 enumerates all the possible states appearing in the first time step. For each of the following steps, it finds the next state by maximizing the transition probability at the current step, i.e., a local search to find the next state. ” —>  local search in the sense that the algorithm chooses as the next state the state with the biggest transition probability (to it) as defined in the Neural Net (transition operator) output? This is a deterministic step, right? 

4.1 DISCOVERING ORDERS IN DATASETS 
Nice description of the datasets. In the <MSR_SenseCam> the choice of one of the classes needs to be supported.  Why? What do the authors expect to happen if a number of instances from different classes are chosen? 

4.1.1 IMPLICIT ORDERS IN DATASETS 
The explanation of the inferred orderings for the GMN and Nearest Neighbour model is not clear. In figure 2, what forces the GMN to make distinguishable transitions as opposed to the Nearest neighbour approach that prefers to get stuck to similar states? Is it the transition matrix architecture as defined by the neural network? 

>> Figure 10: why use of X here? Why not keep being consistent by using s?

*** DO the authors test the model performance on a ordered dataset (after shuffling it…) ?  Is the model able of recovering the order? **

review_title: REVISED - still not convinced about the significance of the work. Substandard experiments and confusing. I leave my score as it is.     --  The proposed model has a very interesting motivation but the description is not clear. The authors do not explain the basics that strongly define the GMN. The experimental results are hard to follow since no intuition is provided. 

Meta-review: The problem of discovering ordering in an unordered dataset is quite interesting, and the authors have outlined a few potential applications. However, the reviewer consensus is that this draft is too preliminary for acceptance. The main issues were clarity, lack of quantitative results for the order discovery experiments, and missing references. The authors have not yet addressed these issues with a new draft, and therefore the reviewers have not changed their opinions.
Decision: Reject