One-shot learning by inverting a compositional causal process. Lake, Salakhutdinov, Tenenbaum. NIPS 2013

1. Deals with one-shot learning
2. “…a Hierarchical Bayesian model based on compositionality and causality that can learn a wide range of natural (although simple) visual concepts, generalizing in human-like ways from just one image.”
3. In 1-shot learning did about as well as people, and better than deep learning methods
4. People can learn a new concept from a tiny amount of data – can learn a class from one image (which is a very high dimensional piece of data)
5. Even MNIST, which is an old and small dataset, still has 6k samples/class, but people often only need 1 example
6. “Additionally, while classification has received most of the attention in machine learning, people can generalize in a variety of other ways after learning a new concept. Equipped with the concept “Segway” or a new handwritten character (Figure 1c), people can produce new examples, parse an object into its critical parts, and fill in a missing part of an image. While this flexibility highlights the richness of people’s concepts, suggesting they are much more than discriminative features or rules, there are reasons to suspect that such sophisticated concepts would be difficult if not impossible to learn from very sparse data. ”
   1. Looks like people both have a rich hypothesis space (because they can do all the above with a small amount of data), but also don’t overfit, which is the theoretical downside to having a large hypothesis class.  How do they do it?
7. Here, focus is on handwritten characters
   1. Idea is to use something more natural and complex than simple synthetic stimuli, but something less complex than natural images
8. Use a new omniglot dataset, which has 16k characters with 20 examples each
   1. Also has time data so the strokes are recorded as well
9. “… this paper also introduces Hierarchical Bayesian Program Learning (HBPL), a model that exploits the principles of compositionality and causality to learn a wide range of simple visual concepts from just a single example.”
10. Also use the method to generate new examples of a class, and then do a Turing test with it by asking other humans which was human generated and which was machine generated
11. The HBPL “…is compositional because characters are represented as stochastic motor programs where primitive structure is shared and re-used across characters at multiple levels, including strokes and sub-strokes.”
12. The model attempts to find a “structural description” that explains the image by breaking the character down into parts
13. A Character is made of:
    1. A set of strokes
       1. Each stroke is made of simple sub-strokes modeled by a “uniform cubic b-spline” and is built of primitive motor elements that are defined by a 1st order Markov Process
    2. Set of spatial relationships between strokes, can be:
       1. Independent: A stroke that has a location independent of other strokes
       2. Start/end: A stroke that starts at beginning/end of another stroke
       3. Along: A stroke that starts somewhere along a previous stroke
14. ” Each trajectory … is a deterministic function of a starting location … token-level control points … and token-level scale …. The control points and scale are noisy versions of their type-level counterparts…”
15. Used 30 most common alphabets for training, and another 20 for evaluation.  The training set was used to learn hyperparameters, a set of 1000 primitive motor elements, and stroke placement.  They attempted to do cross-validation within the training set
16. The full set of possible ways a stroke could be created is enormous, so they have a botto-up way of finding a set of the K most likely parses.  They approximate the posterior based on this finite, size-K sample based on their relative likelihoods
    1. They actually then use metropolis-hasting to get a number of samples of each parse with a little variance each to get a better estimate of the likelihoods
17. “Given an approximate posterior for a particular image, the model can evaluate the posterior predictive score of a new image by re-fitting the token-level variables…”
18. Results
19. For the 1-shot tasks, a letter from an alphabet was presented with 20 other letters from the same alphabet.  Each person did this 10 times, but each time was with a totally new alphabet, so no characters was ever seen twice
20. Get K=5 parses of each character presented (along with MCMC), and then run K gradient searches to reoptimize the token-level variables to fit the query image.
21. They can also, however, attempt to reoptimize the query image to fit the 20 options presented
22. Compare against:
    1. Affine model
    2. Deep Boltzmann Machines
    3. Hierarchical Deep Model
    4. Simple Strokes (a simplified HBPL)
    5. NN
23. Humans and HBPL ~4.5% error rate, affine model next at 18.2%
24. Then they did one-shot Turing test where people and algorithms had to copy a single query character
    1. <For what its worth, I think Affine looks better than both results from people and HBPL>
25. In the “Turing test” there was feedback after each 10 trials, for a total of 50 trials
    1. <Note that this test doesn’t ask which character looks best, it is which is most confusable with human writing (which is pretty sloppy from the images they show).  I’m curious if the affine model could be made more human just by adding noise to its output>
26. <Playing devil’s advocate, the images of characters were collected on mTurk, and look like they were probably drawn with a mouse — that is to say I feel they don’t look completely like natural handwriting.  I wonder how much of this program is picking up on those artifacts?  At least in terms of reproduction, the affine method looks best>

 

Science 2015

1. “Concepts are represented as simple probabilistic programs—that is, probabilistic generative models expressed as structured procedures in an abstract description language (…). Our framework brings together three key ideas—compositionality, causality, and learning to learn—that have been separately influential in cognitive science and machine learning over the past several decades (…). As programs, rich concepts can be built “compositionally” from simpler primitives
2. “In short, BPL can construct new programs by reusing the pieces of existing ones, capturing the causal and compositional properties of real-world generative processes operating on multiple scales.”
3. <Looks like exactly the same paper, just more brief.  The accuracies of both BPL and other methods seems improved here, though.  Convnets get 13.5% error; BPL gets 3.3%; people get 4.5%.  “A deep Siamese convolutional network optimized for this one-shot learning task achieved 8.0% errors”>
4. “BPL’s advantage points to the benefits of modeling the underlying causal process in learning concepts, a strategy different from the particular deep learning approaches examined here.”
   1. <Or equivalently you can just say BPL does better because it has a small and highly engineered hypothesis class>
5. Also run BPL with various “lesions” and gets error rates in the teens.  Also did more poorly in the “Turing test” part
6. Instead of training on 30 background alphabets, they also did with just 5, and there the error rates are about 4%; on the same set convnets did about 20% error

7. Supplementary Material

8. <I assumed that they would ask individuals who actually learned how to write the languages to do the recordings.  Instead, they just took pictures of characters and had people write them.  This seems like a problem to me because of inconsistencies in the way people would actually do the strokes of a letter in an alphabet they do not know.>
9. <Indeed, they were also drawn by mouse in a box on a screen, which is a very unnatural way to do things>
10. <From what I can tell the characters are recorded in pretty low resolution as well which looks like it can cause artifacts, looks like 105×105>
11. <This basically has the details that were included in the main part of the NIPS paper>
12. Some extra tricks like convolving with Gaussian filter, randomly flipping bits
13. Primitives are scale-selective
14. “For each image, the center of mass and range of the inked pixels was computed. Second, images were grouped by character, and a transformation (scaling and translation) was computed for each image so that its mean and range matched the group average.”
15. ” In principle, generic MCMC algorithms such as the one explored in (66) can be used, but we have found this approach to be slow, prone to local minima, and poor at switching between different parses. Instead, inspired by the speed of human perception and approaches for faster inference in probabilistic programs (67), we explored bottom-up methods to compute a fast structural analysis and propose values of the latent variables in BPL. This produces a large set of possible motor programs – each approximately fit to the image of interest. The most promising motor programs are chosen and refined with continuous optimization and MCMC.”
16. “A candidate parse is generated by taking a random walk on the character skeleton with a “pen,” visiting nodes until each edge has been traversed at least once. Since the parse space grows exponentially in the number of edges, biased random walks are necessary to explore the most interesting parts of the space for large characters. The random walker stochastically prefers actions A that minimize the local angle of the stroke trajectory around the decision point…”
17. For the ANN they used cafe, and took a network that works well on MNIST
    1. <But it seems like this system doesn’t have any of the special engineering that went into this that deals specifically with strokes as opposed to whole images>
    2. “The raw data was resized to 28 x 28 pixels and each image was centered based on its center of mass as in MNIST. We tried seven different architectures varying in depth and layer size, and we reported the model that performed best on the one-shot learning task.”
    3. <This may make the task easier, but MNIST deals with a small number of characters, many of which are much less complex than some of the characters used here.   It might be the case that some of the more complex characters can’t be accurately reduced to such a small size, so this may be hobbling performance>
    4. Also the network is not very deep – only 2 conv layers and a max-pooling
    5. “One-shot classification was performed by computing image similarity through the feature representation in the 3000 unit hidden layer and using cosine similarity.”
    6. They used a smaller net for the 1-shot classification with less data, <so that was nice of them>
18. The full “Siamese network” did work on the 105×105 image, had 4 conv layers and 1 standard hidden layer.  Parameters were optimized with Bayesian method
19. “The Hierarchical Deep model is more “compositional” than the deep convnet, since learning-to-learn endows it with a library of high-level object parts (29). However, the model lacks a abstract causal knowledge of strokes, and its internal representation is quite different than an explicit motor program. “
20. For data collection “The raw mouse trajectories contain jitter and discretization artifacts, and thus spline smoothing was applied.”
21. <Ok, skipping the rest>

Big-Ol-Bandit (BOB) implemented, tested

After discussing the idea with Sébastien Bubeck at ICML, I implemented the algorithm which I’ve been calling big-ol-bandit.  I’m pretty sure he was very aware that it can be used this way (very similar to Open-loop-optimistic planning), but since I don’t think anyone tried it, it was worth doing (especially since it was pretty trivial working from my existing code base).

Basically the way it works is that it is doing global stochastic optimization over the return of a sequence of actions, whereas HOOT is doing global stochastic optimization over the return from a single action at some state, depth.

Its really just HOO optimizing a high dimensional bandit problem; the only difference in implementation between this and vanilla HOO is that instead of splitting each action dimension sequentially, the action dimension is chosen at random with the probability of each action in the sequence being divided is proportional to its total potential contribution to the return.

If for example, we were only working at a horizon of 2, the probabilities of splitting the first and second depths are γ/(γ+γ^2), (γ^2)/(γ+γ^2), respectively.  If the MDP itself is a multi-dimensional action problem, once a depth is chosen one of the actions from that dimension is chosen to be cut uniformly at random.  Aside from this its just HOO.

One of the problems with HOOT is that its pretty difficult to come up with bounds for it due to nonstationarity.  Regardless, HOOT worked better than UCT in many cases; sparse sampling as we know is totally useless, even though it is the only one with real guarantees.

I was concerned that BOB was going to be similar to sparse sampling, which has bounds, but isn’t really practical.  I figured there wouldn’t be enough cutting in the action space in the first level, leading to too much randomness in the choices.  To my surprise, it actually seems to work quite nicely.

I ran BOB, HOOT and UCT in the swimmer domain with gamma=0.9 (so this is different from the experiment in the workshop because that used gamma=0.95, and the difference seems to matter).  In this setting UCT was just as bad as random for everything tested.  HOOT’s performance was better than random.  BOB did the best.  I called BOB HOLOP (Hierarchical open-loop optimistic planning, a mix of HOO and OLOP).

BOB (HOLOP), HOOT, and Random in Swimmer domain, gamma = 0.9

(plot looks a little noisy because less data points were used than for the workshop paper as it takes a while to run)

BOB (HOLOP), HOOT, and Random in Swimmer domain, gamma = 0.95

So that is quite positive.  I’d like to run more domains and get more data points so the plots are nicer, but there is pretty clear separation between BOB and HOOT.

---

Since this is just a planning algorithm, I was thinking of extending it for use in a learning algorithm.  Basically my thoughts are that we can do rollouts with BOB based on estimations of our learned model and we can use MRE to drive exploration during rollouts.

This is nice for a few reasons:

• It should have good exploration
• The algorithm operates entirely on-line (as long as the model building is done on-line)
• It would be a continuous state-action learner (which doesn’t really exist yet)
• Doesn’t do regression on the Q-function, which is both provably (in some cases) difficult, as well as practically tough

Since BOB is a trivial extension of HOO, and doesn’t break any of its assumptions, all the guarantees for HOO hold for BOB.  It will converge to the optimal policy based on the model that exists.  I think this in combination with the simulation lemma (which the MRE paper also discusses), we should be able to get good formal guarantees for the algorithm.