Unsupervised Learning by Program Synthesis
We introduce an unsupervised learning algorithm that combines probabilistic modeling with solver-based techniques for program synthesis. We apply our techniques to both a visual learning domain and a language learning problem, showing that our algorithm can learn many visual concepts from only a few examples and that it can recover some English inflectional morphology. Taken together, these results give both a new approach to unsupervised learning of symbolic compositional structures, and a technique for applying program synthesis tools to noisy data.
This paper works on the idea of explaining a set of data points x_i i = 1..N in terms of finding a program (drawn from a prior over programs, and common for all i = 1..N), and specific inputs I_i (i=1..N) for each datapoint. The program is built up out of domain specific primitives, as shown in Tables 1 and 2. The method is appliedto visual concept learning and morphological rule learning tasks which have a cognitive science flavor.Of course this idea is quite similar to standard latent variable modelling. However, rather than say having a matrix of parameters (asin factor analysis) or cluster centers (as in clustering) which define the model, we are allowed here a more general program to map fromI to x, see e.g. Fig 1 (right). However, the program can make use ofexplicit domain-specific prior knowledge, as per Tables 1 and 2.For sec 2 see comments underClarity.In sec 3.1 the method is applied to data from the SVRT (Synthetic Visual Reasoning Task), as per Fig 1. The evaluation as per line 203 is quite hard to understand, but I made sense of if as comparing P_x(t|E_j) for models based on different sets of examples j = 1,2. The paper has an inadequate discussion of the results -- based on raw accuracy (dashed lines in Fig 3) it seems that the program synthesis not doing much better than "image features" (0.78 vs 0.75)? But was the "image features" method trained with far more examples? The r values quoted assess comparison with human accuracy, but what is the goal of the paper -- unsupervised learning, or cognitive modeling?In sec 3.2 the method is applied to morphological rule learning. Again the details are very compressed -- words are represented by sequences of phonemes.I have no idea from the description how features like VOICED are defined -- e.g. do they apply to phonemes, or the word as a whole? Clarity: I found the paper rather lacking in detail -- this is likely due to there being a lot of ideas that are brought together. It is clearly hard to fit these into a NIPS-length paper, but it would have been possible to use the supp mat to expand on various issues and make them intelligible.For example Alg 1 (SMT encoding of expressions) is impenetrable. K(N', N'' ..) is undefined. This whole thing needs much more explanation; it remains very unclear to me what the basic idea of SMT solving is here and how it works. A worked example (e.g. in supp mat) would help a lot. Minor: What is the meaning of the if() function used in Alg 1?See also comments above about level of detail in ecs 3.1 and 3.2. Given these issues I suggest that the authors write a long paper which they make available as supp mat -- in this case the NIPS paper would really be a summary of that long paper.The statements about key ideas in l 422-424 could usefully be moved up to the introduction.Originality: Wrt the key ideas mentioned in l 422-424, the point about a domain specific grammar seems to be a common idea, e.g."background knowledge" in ILP. The "encoding of soft probabilisticconstraints as hard constraints for symbolic search" may be more novel, but the brevity of sec 2.2 makes it hard to understand this in detail.Significance: This paper is tackling a hard and interesting problem, that of the unsupervised learning of programs; this generalizes unsupervised learning applied to vector data to other kinds of data (e.g. sequences). Overall: Part of the difficulty in understanding this paper is that it is actually covering a lot of ground, and it is hard to fit this into the NIPS format. I have no knowledge about SMT, but if theauthors' claim about novelty wrt "encoding of soft probabilisticconstraints as hard constraints for symbolic search" is correct, then it seems to me that the paper is making a useful advance in a hard area. But it would be really helpful if the authors could producea significantly longer version where there is actually space toexplain what is going on.Minor:l 098 \Sigma -> \tau -> \tau ??N in Alg 1 contradicts its defn in l 077.Fig 3 -- the different colors are unnecessary, and the use ofyellow makes the ConvNet plot hard to read. l 337 I happen to know about RANSAC, but many readers won't. It would be useful to explain that RANSAC uses a minimal set of examples to learn a model, and then evaluate it on all of the available examples.ADDED AFTER REBUTTAL: =====================The other reviews and the author response have been read. I retain my score of 7, but strongly encourage the authors to makeextensive supplementary material available; at the moment the paper is more like an "advert" (Donoho's phrase), and we need much more detail if others are able to reproduce the work. In para 1 of therebuttal the authoros say "we could include [...] an example of an unsupervised program synthesis problem being converted into an SMTformula". The "could" here is not enough -- we need to see more detail.