summaries: In this paper the authors propose a neural model that, given a logical formula as input, predicts whether the formula is a tautology or not. Showing that a formula is a tautology is important because if we can classify a formula A -> B as a tautology then we can say that B is a logical consequence of A. The structure of the formula is a feedforward neural network built in a top-down manner. The leaves of this network are vectors (each of them represents a particular occurrence of an atom) which, after the construction of the formula, are processed by some recurrent neural networks.

summaries: In this paper, the authors provide a new neural-net model of logical formulae. The key feature of the model is that it gathers information about a given formula by traversing its parse tree top-down. One neural net of the model traverses the parse tree of the formula from the root all the down toward the leaves, and generates vectors for the leaves of the tree. Then, another RNN-based neural net collects these generated vectors, and answers a query asked for the formula, such as logical entailment. When experimented with Evans et al.'s data set for logical entailment queries, the authors' model outperforms existing models that encode formulae by traversing their parse trees bottom-up.

abstractText: We present a simple neural model that given a formula and a property tries to answer the question whether the formula has the given property, for example whether a propositional formula is always true. The structure of the formula is captured by a feedforward neural network recursively built for the given formula in a topdown manner. The results of this network are then processed by two recurrent neural networks. One of the interesting aspects of our model is how propositional atoms are treated. For example, the model is insensitive to their names, it only matters whether they are the same or distinct.

authors:
Miltiadis Allamanis
Pankajan Chanthirasegaran
Pushmeet Kohli
Charles A. Sutton

title: Learning continuous semantic representations of symbolic expressions

venue: In Proceedings of the 34th International Conference on Machine Learning,

authors:
Richard Evans
David Saxton
David Amos
Pushmeet Kohli
Edward Grefenstette

title: Can neural networks understand logical entailment

venue: In International Conference on Learning Representations,

title: Thinking, Fast and Slow

venue: Farrar, Straus and Giroux,

authors:
John Alan Robinson
Andrei Voronkov (eds

title: Handbook of Automated Reasoning (in 2 volumes)

authors:
Tim Rocktäschel
Edward Grefenstette
Karl Moritz Hermann
Tomáš Kočiský
Phil Blunsom

title: Reasoning about entailment with neural attention

venue: In International Conference on Learning Representations (ICLR),

authors:
Richard Socher
Brody Huval
Christopher D. Manning
Andrew Y. Ng

title: Semantic compositionality through recursive matrix-vector spaces

venue: In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning,

authors:
Kai Sheng Tai
Richard Socher
Christopher D. Manning

title: Improved semantic representations from tree-structured Long Short-Term Memory networks. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 1556–1566

venue: Association for Computational Linguistics,

authors:
Mingzhe Wang
Yihe Tang
Jian Wang
Jia Deng

title: Premise selection for theorem proving by deep graph embedding

authors:
Shuohang Wang
Jing Jiang

title: Learning natural language inference with LSTM. In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 1442–1451

authors:
Wojciech Zaremba
Karol Kurach
Rob Fergus

title: Learning to discover efficient mathematical identities

venue: In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems

heading: 1 INTRODUCTION

text:
In real-world situations a very successful approach, popularized in Kahneman (2011), to problem solving is based on a clever combination of fast instinctive (heuristic) reasoning and slow logical reasoning. The latter is exemplified by abstract logical formulae where only structural properties matter. If computers are involved, a logical formula is traditionally a syntactic object which is a subject to simple but very fast syntactic manipulations Robinson & Voronkov (2001). Hence all but very basic decisions are postponed if possible. However, this viewpoint is rapidly changing as various AI methods are tested in the field of automated reasoning, in particular machine learning methods.
A fundamental problem in using machine learning in automated reasoning is a suitable representation of logical formulae. A formula as a solely syntactic object is no longer sufficient and we have to exploit its semantic properties. Various approaches have been proposed for different logical systems. In this paper we will concentrate on the simplest yet very powerful standard logical system—classical (Boolean) propositional logic.
This paper presents, as far as we know, a novel neural representation of propositional formulae that makes it possible to test whether a given formula has a given property, e.g., whether the formula is always true or not. Clearly, we try to solve a well-known CONP-complete problem. However, the fact that the problem is generally hard and requires a non-trivial search does not rule out the possibility that a decent heuristic can be learned, moreover, if only a specific subset of formulae is involved. In particular, our general goal is to obtain a useful heuristic that can help us in guiding a proof search, where we typically face numerous choice points.
Unlike in natural language processing, a parse tree for a formula is available for free. Although some approaches do not exploit this feature and try to learn the structure of a formula on their own, using usually various recurrent neural networks (RNN), it is more common to take advantage of this knowledge. Moreover, it seems that the later approach has a significant edge, see Evans et al. (2018). Usually propositional atoms, the basic building blocks of propositional formulae, are learned as embeddings and each logical connective is treated as a unique neural network that given the vector representation of its arguments produces a vector that represents an application of the connective on these arguments, e.g., a binary connective takes two vectors of length d, and produces a new one of length d, see Allamanis et al. (2017). This clearly leads to tree recursive neural networks Socher et al. (2012) where the structure of the network follows the parse tree. Such models are built bottomup and the meaning of the formula is usually the vector produced in the root of the tree.
Our model also uses the parse tree of the formula, but the knowledge is propagated in the opposite direction. We start with a vector (random or learned), representing a property we want to test, and
we propagate it from the root to leaves (propositional atoms). The knowledge propagated to atoms is then processed by recurrent neural networks and a decision is produced. This makes it possible to ignore completely the names of propositional atoms and concentrate more on structural properties of formulae.
The experimental results suggest that the model is more than competitive and beats other known approaches on some benchmarks. More importantly, our model seems to suffer less if bigger formulae are involved and could be more useful in real world scenarios.
The structure of this paper is as follows. In Section 2 we discuss the architecture of our model in full details and also a dataset on which we will experiment is introduced there. In Section 3 we discuss an implementation of building blocks of our network, present experimental data, and shortly describe possible interpretations of our model. Some potential future modifications are briefly mentioned in Section 4. Few relevant models are mentioned in Section 5 and the paper concludes with Section 6.

heading: 2 MODEL

text:
Our model tries to mimic the following approach sometimes used by humans to decide whether a propositional formula is always true (tautology). If we want to know whether, e.g., (p→ q)∨ (q → p) is a tautology1 we can suppose the contrary and try to produce a truth-value assignment such that the whole formula is false. It means both p → q and q → p are false under such an assignment2. It follows from the former that p is true and q is false, but from the latter we obtain that q is true and p is false. Because such an assignment is impossible, we showed that the formula cannot be false and hence it is always true.
In a nutshell, we try to propagate a truth value assigned to the whole formula, in our case the formula being false, to its subformulae and we repeat this process until we reach propositional atoms. This gives us a set of constraints on possible truth-value assignments to atoms. At this point we check whether a truth-value assignment satisfying these constraints exists and thus we answer the original question.
However, it is pretty clear that usually this approach is not so straightforward. For example, if we want a formula of the form A → B to be true, it means that the subformula A is false or the subformula B is true. Moreover, such choices easily accumulate with the increasing depth3 of a formula.
Still we will show that a neural model based on the above mentioned idea is competitive. Similarly to the standard recursive approach, we also represent a formula by a recursively built model based on the parse tree of the formula. However, unlike there we use a top-down approach. In our case, we start with a vector w ∈ Rd (random or learned), where d is a parameter of the model, that roughly represents a property of formulae we want to check.4 We continue by propagating this knowledge to subformulae in a top-down manner, e.g., a binary connective ◦ takes a vector v ∈ Rd (input) and produces two new vectors v1 ∈ Rd and v2 ∈ Rd (outputs), hence ◦ : Rn → Rn × Rn. Since all the vectors have the same length d, it is possible to connect individual building blocks together and produce a recursive neural network.
The basic building blocks of the tree part of our model are
w ∈ Rd an initial vector, ci : Rd → Rd × · · · × Rd︸ ︷︷ ︸
k-times
a neural network that represents a k-ary logical connective i,
for all logical connectives i in our language5.
1A formula that is true under any assignment of truth values to propositional atoms. 2For simplicity, from now on we assume that all the claims are under a given assignment. 3The depth of a formula is the depth of its parse tree. 4However, it does not mean that by simply changing w our model starts to test a different property, other
parts of the model have to be trained accordingly, see also footnote 8. 5Note that even nullary connectives, called constants, are allowed.
From these components, which are shared among all formulae in a given language, we dynamically build a recursive network for a particular formula that corresponds to the parse tree of the formula— the parse tree tells us how to connect individual components together. For example, in the left part of Figure 1 we see a model for F = (p → q) ∨ (q → p), which is directly obtained from the parse tree. The vector w is an input to the root of the tree and all the connectives in it are replaced by neural nets ci that represent them. Atoms contain propagated outputs (vectors) of this tree recursive model, here we obtain vectors p1, q1, q2,p2 ∈ Rd, where p1 is at the position of the first occurrence of p in F .
Note that each occurrence of the same atom in our tree model produces a unique vector. The fact that they correspond to the same atom is exploited by another level of our model. We take a recurrent neural network RNN-Var that has a sequence of all vectors corresponding to the same atom in the formula as an input and outputs a vector in Rd. In Figure 1 RNN-Var takes p1 and p2 and outputs p ∈ Rd and also the same RNN-Var takes q1 and q2 and outputs q ∈ Rd. One more recurrent neural network RNN-All takes a sequence of all output vectors produced by RNN-Var and outputs a vector in Rd that is input to a component Final : Rd → R2 which ends with a softmax layer and produces out ∈ R2 that makes it easy to decide whether the output of the whole network is true or false. It should be emphasized that our model completely ignores the names of atoms, we only check whether they are the same or distinct. Moreover, the number of distinct atoms that can occur in a formula is effectively only bounded by the ability of RNN-All to correctly process the outputs of RNN-Var. Hence the model can evaluate formulae that contain more atoms than formulae used for training.
The basic building blocks of the recurrent part of our model are
RNNVar : Rd × · · · × Rd → Rd a RNN aggregating vectors corresponding to the same atom, RNNAll : Rd × · · · × Rd → Rd a RNN aggregating the outputs of RNN-Var components, Final : Rd → R2 a final decision layer.
It should be emphasized again how the model is built. Given a property we want to test, e.g., whether a formula is always true, we train representations of w, ci, RNN-Var, RNN-All, and Final. These components are shared among all the formulae. For a single formula we produce a model (neural network) recursively from them as described above. For implementation details see Section 3.

heading: 2.1 DATASET

text:
To provide comparable results in Section 3 we use the dataset6 presented in Evans et al. (2018) and thoroughly described therein. For our purposes here it is essential that it contains triples of the form (A,B,A |= B) where A and B are propositinal formulae and A |= B indicates whether B follows from A. The dataset contains train (99876 triples), validation (5000), and various test sets with a different level of difficulty given by a number of atoms and connectives7 occurring in them.
From the deduction theorem we know that A |= B is equivalent to A → B being a tautology. We prefer the later form, because it fits nicely into our model and instead of learning the meaning of entailment (|=), we can use the connective→ directly. Note that although our model ignores the names of atoms this cannot be exploited directly, because validation and test sets do not contain pairs of formulae that would result from pairs in the training set by renaming atoms.

heading: 3 EXPERIMENTS

text:
Although our model is conceptually simple, each building block can be implemented in various ways. In this section we briefly discuss some possible variants and parameters. However, we have not tried to optimize over all the possible parameters discussed later and it is very likely that our results can be improved.
The following implementation of the model introduced in Section 2 is our standard experimental model, called TopDownNet:
• d = 128, • w ∈ Rd is a learned vector, • every ci is a sequence of linear, ReLU, linear, and ReLU layers, where the input size and
output size is always the same with the exception of binary connectives, where the last linear layer is Rd → R2d,
• RNN-Var is a gated recurrent unit (GRU) with 2 recurrent layers and the size of the input and hidden state is d,
• RNN-All is a GRU with 1 recurrent layer and the size of the input and hidden state is d, • Final is a sequence of linear (Rd → Rd/2), ReLU, linear (Rd/2 → R2), and log softmax
layers,
and we use the mean square error as a loss function and Adam as an optimizer with the learning rate 10−4.
A key parameter of our model is the dimension d, which is the length of the initial vector w and also the length of many other vectors occurring in our model. Even d = 8 produces reasonable results, as Figure 2 shows, but with increasing d the quality of the model grows, see Table 1.
Our various experiments suggest that whether w is chosen randomly or learned makes little to no difference.8 Similarly and more importantly, connectives ci composed of a single linear layer seem to perform almost equally, and sometimes even better, to more complicated versions containing non-linearities as in our standard TopDownNet.
In RNN-Var and RNN-All we use gated recurrent units (GRUs) which in our experiments perform similarly to long short-term memory (LSTM) RNNs. Similarly to results obtained in Evans et al. (2018), we have seen no real advantage of using their bidirectional variants for our model and in many cases they produce worse results. The order in which RNN-Var and RNN-All consume their inputs is random.
6It can be obtained from https://github.com/deepmind/logical-entailment-dataset. 7The dataset contains negations (¬), implications (→), conjunctions (∧), and disjunctions (∨). 8An obvious question is whether it makes sense to even consider a learned w. Generally, it could be useful, because we can be in a situation where we want to use more such vectors which are in relations that we want to learn.
Although it is conceptually nicer and fits to our original intuition, our combination of two RNNs and their functions clearly suggest a question whether they are in fact necessary. Either we can use the same RNN for RNN-Var and RNN-All, or we can use padding to separate the sequences of different atoms. Our preliminary experiments suggest that both new variants and our original approach perform quite similarly, see Figure 3.
It seems that if Final is just a combination of linear and log softmax layers the performance is slighly better than the one used in TopDownNet with an added non-linearity. However, the best performing models that we present in Table 1 use our standard parameters with different values of the dimension d.
In Table 1 is a comparison of our models and other approaches mentioned in the benchmark in Evans et al. (2018). The values for the first three models are taken from that paper. TreeNN follows Allamanis et al. (2017) and TreeLSTM follows Tai et al. (2015). PossibleWorldNet is developed in Evans et al. (2018). TopDownNets are our standard models from the beginning of Section 3 with the lowest losses on the validation set for different values of d.
The results in Table 1 show that our model is competitive with other approaches. It beats standard tree recursive models (TreeNet Encoders and TreeLSTM Encoders) and PossibleWorldNet, which performs similar to testing random truth-values, on the massive set and keeps pace on examples from textbooks. The good results on the massive set suggest that our model can do better than just random testing of truth-values. Moreover, it is interesting that the increase of d does not have such a significant role, as already mentioned before.

heading: 3.1 INTERPRETATION OF MODEL

text:
We present our model as an alternative to bottom-up approaches, where a possible interpretation of such models is that they combine (samples of) random assignments and produce the value of the whole formula. Similarly, we could argue that our model propagates a truth value top-down and makes (sampled) random choices when multiple options are available, e.g., when we want to make A → B true. However, this clearly does not explain better results of our model, because for example on the massive set from Table 1 random assignments are much more successful than random top-down propagations.
Our model therefore has to take advantage of something else, or it significantly improves the above mentioned random top-down propagations. Clearly, it uses training data more efficiently, because it is insensitive to the names of atoms, but this is not enough to explain our results. However, it is possible that the top-down propagation captures the overall structure of a formula better and enables a more efficient transfer of knowledge through formulae. Although it is hard to analyze our models completely, we can say something about what is commonly happening at the beginning; close to w.
All formulae in the dataset are of the form A → B, see Section 2.1, hence propagating w, which is supposed to mean false, through →, denoted c→(w), produces two vectors v→1 and v→2 that correspond to A and B, respectively. These two vectors are commonly very distinct and applying negation (c¬) on one of them almost exactly produces the other one. Moreover, this remains true even if we apply c¬ repeatedly, see Figure 4. If we now apply c∧ on v→1, assuming B is C∧D, then we not so surprisingly obtain two vectors very similar to each other and also similar to v→1; loosely speaking, they should all represent being true. More interesting is to apply c∧ on v→2, assuming B is E ∧ F , because we obtain two vectors that are similar, but not as similar as in the previous case and usually even less similar to v→2. This suggests that something more involved than a simple splitting of truth values according to possible choices can happen in the model.9 Nevertheless, it
9Loosely speaking, if we assume that v→2 is false, then there are three ways how to make the conjunction false {(0, 0), (0, 1), (1, 0)}, where 0 means false and 1 means true. Hence the first component of the conjunc-
seems that the model is able to transfer the piece of knowledge that something is (almost) true or false.
Unfortunately, it is very unclear what happens deeper in the model and how recurrent neural networks combine the vectors in the leaves. Moreover, RNN-Var and RNN-All consume their inputs in random order and this slightly influences the results. However, it is plausible, based on initial experiments with small formulae, that RNN-Var, loosely speaking, checks inconsistent assignments to the same atoms and RNN-All just aggregates these results. Moreover, it seems that our model is quite robust to changes in the order of arguments in commutative connectives (∧ and ∨) and to other simple transformations of subformulae—replacing A→ B by ¬B → ¬A, A ∧B by ¬(¬A ∨ ¬B) etc.
A possible explanation of very good performance could be that our model just exploits the given dataset in some unforeseen way. In fact, we want to learn regularities in the dataset. Although this is possible, we believe that this does not explain the performance of our model completely. We trained our model on the BOOL8 and BOOL10 datasets from Allamanis et al. (2017) adapted10 to our problem and tested it on unseen equivalence classes with the accuracy 98.3% and 80.5%, respectively. These numbers are not directly comparable to the results presented in the paper, however, they suggest that our model is able to perform reasonably even on other datasets. Similarly, if we use the dataset from Evans et al. (2018) to test satisfiability11, then we obtain results similar to the results on the original dataset.

heading: 4 POSSIBLE VARIANTS

text:
We aimed for a simple model and hence a plethora of modifications is possible; they can both improve the quality of produced models and their generality. Here we will discuss at least some of them.
Our model uses a feedforward neural network for representing a formula and only then two recurrent networks are used to process the results of the feedforward part. Clearly, more complicated versions can be produced that provide a better interplay between these two layers and/or the feedforward part can become more complicated, e.g., to allow a communication between different subformulae.12
tion could be represented by v1 = (0, 0, 1) and the second one by v2 = (0, 1, 0). If one naturally represents false in v→2 by (0, 0, 0), then v1 and v2 should be closer to v→2 than to each other.
10We produced randomly balanced sets containing pairs of equivalent and non-equivalent formulae. 11For every formula A → B we take ¬(A → B) and propagate negation through the formula. Hence we obtain, e.g., A ∧ ¬B and then continue by propagating negation through B. 12An example how a more complicated model can help is Peirce’s law ((p → q) → p) → p, a well-known tautology. Similarly as in Section 2 we try to produce a truth-value assignment such that Peirce’s law is false. It means that (p → q) → p is true and p is false. Now using that p is false, we know that p → q is also false and hence p is true and q is false, a contradiction thanks to p. However, without using the fact that p is false
For example, it is possible to propagate information also back in the bottom-up direction through the tree part of our model, or use an attention mechanism.
It should be also noted that although we use our model for deciding whether a formula is a tautology, we can try to enforce other properties by a similar process, e.g., we can test whether a formula is satisfiable, i.e., is true under some assignment of truth-values. Also learning more related properties, more vectors like w, with all the other components shared could be an interesting problem, and their interplay could even improve the performance on individual tasks.
Clearly, our presentation of the model suggests that it heavily relies on properties of classical (Boolean) propositional logic. Nevertheless, it can be used directly also in a non-classical (propositional) setting. Note that the semantics of a given logic is completely learned from examples and no a priory knowledge is provided, however, it is of course possible that our model is unable to reasonably capture the semantics of the given logic and some modifications, e.g., those mentioned above, are necessary. The question whether a more involved model based on our model can be successfully used also for more complex formulae (first-order or even higher-order) is a bit unclear, a clear goal for future research.

heading: 5 RELATED WORK

text:
A thorough recent comparison of related methods is in Evans et al. (2018) and therefore this section is only very brief. In Wang et al. (2017) authors also develop a model which is invariant to atoms (variables) renaming. However, a formula graph obtained from a parse tree is there translated into a vector using the embeddings of nodes given by their neighborhoods. Moreover, the problem they study is different (first-order and higher-order logics). In Zaremba et al. (2014), a pioneering paper on using recursive neural networks Socher et al. (2012) for mathematical expressions, they also do not deal with variables, because they allow at most one to occur in them.
In Allamanis et al. (2017) a bottom-up approach is presented, however, it also contains a restricted form of backward communication that proved to be useful. The problem studied there is learning vector representations of formulae and based on their similarity test their properties. In our case, we test the properties directly.
An approach based solely on recurrent neural networks has been used in natural language processing where textual entailment is an important topic. For LSTM models with an attention mechanism see Wang & Jiang (2016); Rocktäschel et al. (2016).
PossibleWorldNet developed in Evans et al. (2018) addresses the same problem as our model. It exploits a novel idea of learning various useful assignments and test them latter on. However, the results suggest that the method performs similarly to random assignments (a very powerful technique on its own). It could be because the standard bottom-up approach is used.

heading: 6 CONCLUSION

text: We have presented a novel top-down approach to represent formulae by neural networks and showed some preliminary experiments. They suggest that our approach is competitive with other known approaches and beats them on some benchmarks. More importantly, it seems that the presented model can deal better with the increasing size of formulae than other approaches. The model deals only with the structure of formulae and ignores completely for example names of individual atoms, only whether they are the same or distinct matters.

heading: ACKNOWLEDGMENTS

text:
This work was supported by the European Regional Development Fund under the project AI&Reasoning (reg. no. CZ.02.1.01/0.0/0.0/15 003/0000466).
(inaccessible to our model) in processing (p → q) → p we have to deal with more choices along this line of reasoning.

title: TOP-DOWN NEURAL MODEL FOR FORMULAE


summaries: This paper studies an interesting and meaningful topic that what is the potential of curriculum learning (CL) in training dnn.  The authors decompose CL into two main parts: scoring function and pacing function. Towards both parts, several candidate functions are proposed and verified.  The paper is presented quite clear and gives contribution to better understand CL in the literature of DNN.

summaries: This problem of interest in this paper is Curriculum Learning (CL), in the context of deep learning in particular. CL refers to learning a non-random order of presenting the training examples to the learner, typically with easier examples presented before difficult ones, to guide learning more effectively. This has been shown to both speed up learning and lead to better generalization, especially for more challenging problems. In this paper, they claim that their contribution is to decompose the problem of CL into learning two functions: the scoring function and the pacing function, with the role of the former being to estimate the difficulty of each training example and the latter to moderate the schedule of presenting increasingly more challenging examples throughout training.

abstractText: Training neural networks is traditionally done by sequentially providing random mini-batches sampled uniformly from the entire dataset. In our work, we show that sampling mini-batches non-uniformly can both enhance the speed of learning and improve the final accuracy of the trained network. Specifically, we decompose the problem using the principles of curriculum learning: first, we sort the data by some difficulty measure; second, we sample mini-batches with a gradually increasing level of difficulty. We focus on CNNs trained on image recognition. Initially, we define the difficulty of a training image using transfer learning from some competitive ”teacher” network trained on the Imagenet database, showing improvement in learning speed and final performance for both small and competitive networks, using the CIFAR-10 and the CIFAR-100 datasets. We then suggest a bootstrap alternative to evaluate the difficulty of points using the same network without relying on a ”teacher” network, thus increasing the applicability of our suggested method. We compare this approach to a related version of Self-Paced Learning, showing that our method benefits learning while SPL impairs it.

authors:
Yoshua Bengio
Jérôme Louradour
Ronan Collobert
Jason Weston

title: Curriculum learning

venue: In Proceedings of the 26th annual international conference on machine learning,

title: Learning many related tasks at the same time with backpropagation

venue: In Advances in neural information processing systems,

authors:
Haw-Shiuan Chang
Erik Learned-Miller
Andrew McCallum

title: Active bias: Training more accurate neural networks by emphasizing high variance samples

venue: In Advances in Neural Information Processing Systems,

authors:
Jia Deng
Wei Dong
Richard Socher
Li-Jia Li
Kai Li
Li Fei-Fei

title: Imagenet: A large-scale hierarchical image database

venue: In Computer Vision and Pattern Recognition,

authors:
Yang Fan
Fei Tian
Tao Qin
Xiang-Yang Li
Tie-Yan Liu

title: Learning to teach

venue: arXiv preprint arXiv:1805.03643,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Francis P Hunkins
Allan C Ornstein

title: Curriculum: Foundations, principles, and issues

venue: Pearson Education,

authors:
Andrew Jesson
Nicolas Guizard
Sina Hamidi Ghalehjegh
Damien Goblot
Florian Soudan
Nicolas Chapados

title: Cased: Curriculum adaptive sampling for extreme data imbalance

venue: In International Conference on Medical Image Computing and Computer-Assisted Intervention,

authors:
Lu Jiang
Zhengyuan Zhou
Thomas Leung
Li-Jia Li
Li Fei-Fei

title: Mentornet: Learning datadriven curriculum for very deep neural networks on corrupted labels

venue: In International Conference on Machine Learning,

authors:
Alex Krizhevsky
Geoffrey Hinton

title: Learning multiple layers of features from tiny images

venue: Technical report, Citeseer,

authors:
Kai A Krueger
Peter Dayan

title: Flexible shaping: How learning in small steps helps

authors:
M Pawan Kumar
Benjamin Packer
Daphne Koller

title: Self-paced learning for latent variable models

authors:
Shuying Liu
Weihong Deng

title: Very deep convolutional neural network based image classification using small training sample size

venue: In Pattern Recognition (ACPR),

title: Conditioned reflexes: an investigation of the physiological activity of the cerebral cortex

venue: Annals of neurosciences,

authors:
Andrew I Schein
Lyle H Ungar

title: Active learning for logistic regression: an evaluation

venue: Machine Learning,

authors:
Bernhard Scholkopf
Kah-Kay Sung
Christopher JC Burges
Federico Girosi
Partha Niyogi
Tomaso Poggio
Vladimir Vapnik

title: Comparing support vector machines with gaussian kernels to radial basis function classifiers

venue: IEEE transactions on Signal Processing,

authors:
Oliver G Selfridge
Richard S Sutton
Andrew G Barto

title: Training and tracking in robotics

venue: In IJCAI, pp

authors:
Shai Shalev-Shwartz
Shai Ben-David

title: Understanding machine learning: From theory to algorithms

venue: Cambridge university press,

authors:
Abhinav Shrivastava
Abhinav Gupta
Ross Girshick

title: Training region-based object detectors with online hard example mining

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Karen Simonyan
Andrew Zisserman

title: Very deep convolutional networks for large-scale image recognition

venue: arXiv preprint arXiv:1409.1556,

title: Cyclical learning rates for training neural networks

venue: In Applications of Computer Vision (WACV),

authors:
Christian Szegedy
Vincent Vanhoucke
Sergey Ioffe
Jon Shlens
Zbigniew Wojna

title: Rethinking the inception architecture for computer vision

authors:
Daphna Weinshall
Gad Cohen
Dan Amir

title: Curriculum learning by transfer learning: Theory and experiments with deep networks

venue: In International Conference on Machine Learning (ICML),

authors:
Dingwen Zhang
Le Yang
Deyu Meng
Dong Xu
Junwei Han

title: Spftn: A self-paced fine-tuning network for segmenting objects in weakly labelled videos

venue: In IEEE CVPR,

heading: 1 INTRODUCTION

text:
Teaching complex tasks to humans and animals can be difficult. Often such tasks cannot be grasped by the learners, or ”students”, immediately, and need to be broken down into simpler problems. Therefore, in order to teach complex tasks, teachers are often required to create a curriculum. The curriculum imposes some order on the learning task; it introduces different concepts at different times, hence exploiting previously learned concepts in order to ease the abstraction of new ones. Imposing a curriculum in order to speed up learning is widely used in the context of human learning, and also routinely used in animal training (Skinner, 1958; Pavlov, 2010; Krueger & Dayan, 2009).
In many traditional machine learning approaches, known as supervised learning, a target function is estimated by using a set of labeled examples. The examples can be thought of as given by a teacher while the learning algorithm can be thought of as a student. The field of curriculum learning (CL), which is motivated by the idea of a curriculum in human learning, attempts at imposing some structure on the labeled data. Such structure essentially relies on a notion of ”easy” and ”hard” examples and utilizes this distinction in order to teach the student how to generalize easier concepts before harder ones. Empirically, the use of CL has been shown to accelerate and improve the learning process (e.g. Selfridge et al., 1985; Bengio et al., 2009).
In this work, we aim at extending the understanding of CL in the context of deep neural learning. More specifically, we wish to understand to what extent curriculum can improve the accuracy and convergence rate of deep neural networks. The main challenge in making CL practical is, arguably, finding a way to construct a good curriculum for a newly unseen database. In order to do so, we investigate two ideas motivated by transfer learning and bootstrapping respectively.
When establishing a curriculum for human students, teachers need to arrange the material in a way that will present simple concepts before harder ones, so that the abstraction of simple ideas can help the student grasp more complex ones (Hunkins & Ornstein, 2016). However, sorting the concepts by difficulty is not sufficient. The teacher also needs to attend to the pace by which the material is presented – going over the simple ideas too fast may lead to more confusion than benefit, while moving along too slowly may lead to boredom and unproductive learning (Hunkins & Ornstein, 2016). These principles can also be beneficial when the learner is a neural network.
Specifically, formalizing and generalizing what was implicitly done in Weinshall et al. (2018), we decompose the problem of CL and define two separate - but closely related - functions. The first function, termed scoring function, determines the ”hardness” or ”complexity” of each example in the data. The scoring function enables us to sort the data by concept difficulty, allowing us to present to the network the easier (and presumably simpler) examples first. The underlying assumption is that generalization from the easier examples can simplify the learning of harder examples in the data. The second function, termed pacing function, determines the pace by which data is presented to the network. The pace depends on both the data itself and the learner.
In our work, we analyze several scoring and pacing functions, investigating their inter-dependency and presenting ways to combine them in order to achieve faster learning and better generalization. The main challenge is, arguably, how to obtain an effective scoring function without additional human supervision. To this end we investigate two approaches, each providing a different estimator for the ideal scoring function: (i) Knowledge transfer. The first scoring function is based on transfer learning from networks trained on the large and versatile Imagenet dataset (Deng et al., 2009; Weinshall et al., 2018). (ii) Bootstrapping. The second scoring function is based on self-tutoring - we train the network once without curriculum, then use the resulting classifier to rank the training data in order to train the same network again from scratch. Both scoring functions are shown in Section 3 to speed up learning and improve the generalization of neural networks.
In many approaches, including Self-Paced Learning (SPL), Active-Learning and hard example mining (Kumar et al., 2010; Schein & Ungar, 2007; Shrivastava et al., 2016), the mini-batches which presented to the learner model are as sampled dynamically, based at each time point on the current hypothesis of the model. While in some contexts these approaches are beneficial (Chang et al., 2017; Zhang et al., 2017), they are based on the knowledge of the student at a specific time point. While a student can report what is easy/hard for it right now, it might be oblivious to some aspects of the bigger problem at hand, ignoring concepts which if learned early, could prove helpful in a later time. In the context of linear regression loss, Weinshall et al. (2018) showed that such distinction indeed holds: while it is beneficial to prefer points with lower loss with respect to the target hypothesis as suggested by CL, it is on the other hand beneficial to prefer points with higher loss with respect to the current hypothesis in agreement with hard data mining (Shrivastava et al., 2016) and boosting, contrary to SPL.
To examine this somewhat confusing point, we have implemented a simplified version of the procedure described above, where the scoring function is based on the loss of the training points with respect to the current hypothesis, both in ascending and descending orders. These variants of SPL and hard example mining respectively learn slower and reach lower final accuracy when compared to self-taught, throughout all of our experiments.
We have also investigated three pacing functions. (i) Fixed exponential pacing presents the learner initially with a small percentage of the data, increasing the amount exponentially every fixed number of learning iterations. (ii) Varied exponential pacing allows the number of iterations in each step to vary as well. (iii) Single-step pacing is a simplified version of the first protocol, where mini-batches are initially sampled from a fixed fraction of the data that includes the easiest examples, after which mini-batches are sampled from the whole data as usual. We show that the three functions have comparable performance, and analyze the complexity of their use.
Previous work. While remaining in the fringes of machine learning, there has been some recent work on CL and its applications. Bengio et al. (2009) introduced the idea of CL for machine learning algorithms, showing simple examples where CL benefits learning. Weinshall et al. (2018) proved that CL boosts the speed of convergence in the convex case of linear regression. Otherwise most prior art is empirical, and almost always ranking by difficulty (i.e., the scoring function defined above) is provided by the user based on prior knowledge (in other words, supervision) as in Jesson et al. (2017).
In a closely related line of works, a pair of teacher and student networks are trained simultaneously, where mini-batches for the student network are sampled dynamically by the teacher, based on the student’s output in each time point (Jiang et al., 2018; Fan et al., 2018). As opposed to our method, these works base the curriculum on the current hypothesis of the students, and achieve better performance for corrupted (Jiang et al., 2018) or smaller (Fan et al., 2018) datasets, instead of improved generalization on the original dataset.
Our contribution, with respect to this previous work, is to provide a formal definition of CL algorithms by way of 2 functions for scoring and pacing, analyze and comparatively evaluate these functions, and show how CL can benefit learning in CNNs even without human supervision about the ranking of examples by difficulty and in a problem-free manner.

heading: 2 CURRICULUM LEARNING

text: Curriculum learning deals with the question of how to use prior knowledge about the difficulty of the training examples, in order to sample each mini-batch non-uniformly and thus boost the rate of learning and the accuracy of the final classifier. The paradigm of CL is based on the intuition that it helps the learning process when the learner is presented with simple concepts first.

heading: 2.1 NOTATIONS AND DEFINITIONS

text:
Let X = {(xi, yi)}Ni=1 denote the data, where xi ∈ Rd denotes a single data point and yi ∈ [K] its corresponding label. Let Fθ : Rd → [K] denote the target classifier (or learner), and mini-batch B ⊆ X denote a subset of X. In the most common training procedure, which is a robust variant of Stochastic Gradient Descent (SGD), Fθ is trained sequentially when given as input a sequence of mini-batches [B1, ...,BM ] (Shalev-Shwartz & Ben-David, 2014). The common approach – denoted vanilla in the following sections – samples each mini-batch Bi uniformly from X. Both in the common approach and in our work, the size of each mini-batch remains constant, to be considered as a hyper-parameter defining the learner.
We measure the difficulty of point xi by its minimal loss with respect to the set of optimal hypotheses under consideration. We define a scoring function (or a ”difficulty” function) to be any function f : X → R, and say that example (xi, yi) is more ”difficult” than example (xj , yj) if f (xi, yi) > f (xj , yj). Choosing f is the main challenge of CL, as it encodes the prior knowledge of the teacher.
We define a pacing function to be a function gFθ : [M ] → [N ], which may depend on the learner Fθ. The pacing function is used to determine a sequence of subsets X ′ 1, ...,X ′
M ⊆ X, of size |X′i| = gFθ (i), from which {Bi}Mi=1 are sampled uniformly. In CL the i-th subset X ′
i includes the first gFθ (i) elements of the training data when sorted by the scoring function f in an ascending order. Although the choice of the subset can be encoded in the distribution from which each Bi is sampled, adding a pacing function simplifies the exposition and analysis.

heading: 2.2 CURRICULUM LEARNING METHOD

text:
Together, each scoring function f and pacing function gFθ define a curriculum. Any learning algorithm which uses the ensuing sequence [Bi]Mi=1 is a curriculum learning algorithm. We note that in order to avoid bias when picking a subset of the N examples for some N , it is important to keep the sample balanced with the same number of examples from each class as in the training set. Pseudo-code for the CL algorithm is given in Alg. 1.
In order to narrow down the specific effects of using a scoring function based on ascending difficulty level, we examine two control conditions. Specifically, we define 2 additional scoring functions and corresponding algorithms: (i) The anti-curriculum algorithm uses the scoring function f ′ = −f , where the training examples are sorted in a descending order; that results in presenting the harder examples before the easier ones. (ii) The random-curriculum algorithm (henceforth denoted random) uses a scoring function where the training examples are randomly sorted.

heading: 2.3 SCORING AND PACING FUNCTIONS

text:
We evaluate two scoring functions: (i) Transfer scoring function, computed as follows: First, take the pre-trained Inception network (Szegedy et al., 2016) and run each training image through it, using the activation levels of its penultimate layer as a feature vector (Caruana, 1995). Second, use these
features to train a classifier and use its confidence score as the scoring function for each image1. (ii) Self-taught scoring function, computed as follows: First, train the network using uniformly sampled mini-batches (the vanilla method). Second, compute this network’s confidence score for each image to define a scoring function2.
Although the pacing function can be any function gFθ : [M ]→ [N ], we limit ourselves to monotonic increasing functions so that the likelihood of the easier examples can only decrease. For simplicity, gFθ is limited to staircase functions. Thus each pacing function is defined by the following hyper-parameters, where step denotes all the learning iterations during which gFθ remains constant: step length - the number of iterations in each step; increase - an exponential factor used to increase the size of the data used for sampling mini-batches in each step; starting percent - the fraction of the data in the initial step. An illustration of these parameters can be seen in Fig. 1.
We evaluate three pacing functions: (i) Fixed exponential pacing has a fixed step length, and exponentially increasing data size in each step. Formally, the pacing function is given by:
gFθ (i) = min ( starting percent · increaseb i step length c, 1 ) ·N
1Similar results can be obtained when using different confidence scores (e.g, the classifier’s margin), different classifiers (e.g, linear SVM), and different teacher networks (e.g, VGG-16 (Simonyan & Zisserman, 2014), Resnet (He et al., 2016)). For more details, see Appendix A.
2Theoretically we can use this method repeatedly, as discussed in Appendix B.
Algorithm 1: Curriculum learning method Input : pacing function gFθ , scoring function f , labeled data X. Output: sequence of mini-batches [ B′1, ...,B ′ M ] .
1 sort X according to f , in ascending order; 2 result← []; 3 for i = 1, ...,M do 4 size← gFθ (i); 5 X′i ← X [1, ..., size]; 6 uniformly sample B′i from X ′ ; 7 append B′i to result; 8 end 9 return result;
(ii) Varied exponential pacing, which allows step length to vary as well3: gFθ (i) = min ( starting percent · increase ∑#steps k=1 1[i>step lengthk], 1 ) ·N
The total number of steps can be calculated from starting percent and increase: #step = d− logincrease(starting percent)e
(iii) Single step pacing, which is a simplification of the staircase function into a step function:
gFθ (i) = starting percent 1[i<step length] ·N
This function has only 2 hyper-parameters, hence it is simpler to use than the previous two.

heading: 3 EMPIRICAL EVALUATION

text:
Methodology. All the code used in this work will be published upon acceptance. We define 4 empirical cases: Case 1 replicates the experimental design described in (Weinshall et al., 2018), by using the same dataset and network architecture. The dataset is the ”small mammals” superclass of CIFAR-100 (Krizhevsky & Hinton, 2009), containing a subset of 3000 images from CIFAR100, divided into 5 classes of small mammals (hamster, mouse, rabbit, shrew, squirrel). Each class contains 500 training images and 100 test images. The neural network is a moderate size handcrafted convolutional network, whose architecture details can be found in Appendix C. Cases 2 and 3 adopt the same architecture used above while being applied to the entire CIFAR-10 and CIFAR100 datasets, where the network’s output layer is adjusted to size 10 and 100 respectively. Case 4 uses a public-domain VGG-based architecture4, which achieves competitive results (Simonyan & Zisserman, 2014; Liu & Deng, 2015), to classify the CIFAR-100 dataset.
Hyper-parameter tuning. As in all empirical studies involving deep learning, the results are quite sensitive to the values of the hyper-parameters, hence parameter tuning is required. Issues related to how a fair comparison between the different conditions is achieved are discussed in Appendix B. In practice, in order to reduce the computation time of parameter tuning, we varied only the first 2 step length instances in the varied exponential pacing condition. Accordingly, fixed exponential pacing, varied exponential pacing and single step pacing define 3, 5 and 2 new hyper-parameters respectively, referred to henceforth as the pacing hyper-parameters.
In the CL framework, the use of a pacing function affects the optimal values of other hyperparameters, in particular, the learning rate. Specifically, since it significantly reduces the size of the data-set from which each mini-batch is sampled, this has the concomitant effect of increasing the effective learning rate. As a result, when using the fixed exponential or the single step pacing functions, the learning rate must be tuned separately for every test condition. As traditionally done (e.g Simonyan & Zisserman, 2014; Szegedy et al., 2016; He et al., 2016), we set an initial learning rate and decrease it exponentially every fixed number of iterations. This method gives rise to 3 learning rate hyper-parameters which require tuning: (i) the initial learning rate; (ii) the factor by which the learning rate is decreased; (iii) the length of each step with constant learning rate5.
When varied exponential pacing is used, varying step length has the opposite concomitant effect on the learning rate, as it determines the number of mini-batch samples in each step. Effective tuning of this parameter can make the additional tuning of parameters affecting the learning rate redundant. In practice, in order to reach the improvement achieved by the fixed exponential pacing, we decrease the corresponding learning rate parameters used in the vanilla condition by some small factor6.

heading: 3.1 RESULTS: CL BENEFITS LEARNING

text:
Case 1: A moderate size network is trained to distinguish 5 classes from CIFAR-100, which are members of the same super-class as defined in the original dataset. Results are shown in Fig. 2.
3In practice, to avoid an unfeasible need to tune too many hyper-parameters, we vary only the first two step length instances and fix the rest. As shown later on, this is reasonable as most of the power of the curriculum lies in the first few steps.
4The code for the VGG network is available at https://github.com/geifmany/cifar-vgg. 5For more details, see Appendix B. 6In the results reported below we used a reduction of 10%, with similar behavior for other nearby choices.
Curriculum learning is clearly and significantly beneficial - learning starts faster, and converges to a better solution. We observe that the performance of CL with a random scoring function is similar to vanilla, indicating that the main reason for the improvement achieved by CL is due to its beneficial transfer scoring function. In fact, although tuned separately, the learning rate hyper-parameters for both the random and the curriculum test conditions are very similar, confirming that the improved performance is due to the use of an effective transfer scoring function.
To check the robustness of these results, we repeated the same empirical evaluation using different super-classes of CIFAR-100, with similar results (see Appendix A). Interestingly, we note that the observed advantage of CL is more significant when the task is more difficult (i.e. lower vanilla test accuracy). The reason may be that in easier problems there is a sufficient number of easy examples in each mini-batch even without CL. Although the results reported here are based on transfer from the Inception network, we are able to obtain the same results using scoring functions based on transfer learning from other large networks, including VGG-16 and Resnet, as shown in Appendix A.
Cases 2 and 3: Similar empirical evaluation as in case 1, using the same moderate size network to classify two benchmark datasets. The results are shown in Fig. 3. Like before, the test accuracy in the curriculum test condition increases faster and achieves better final performance in both cases, as compared to the vanilla test condition. The beneficial effect of CL is larger when classifying the CIFAR-100 dataset, which is a harder dataset.
Case 4: Similar empirical evaluation as in case 1, using a competitive public-domain architecture. Specifically, we use the Inception-based transfer scoring function to train a VGG-based network
(Liu & Deng, 2015) to classify the CIFAR-100 dataset. Differently from the previous cases, here we use the varied exponential pacing function with a slightly reduced learning rate, as it has the fewest hyper-parameters to tune, an important factor when training such a big network. Results are shown in Fig. 4a (with no data augmentation), showing the same qualitative results as in the previous cases; CL gives a smaller benefit, but the benefit is still significant.
Case 5: Similar empirical evaluation as in case 1, using the same moderate size network to distinguish 7 classes of cats from the ImageNet dataset7. The results are shown in Fig. 5. Again, the test accuracy in the curriculum test condition increases faster and achieves better final performance in the curriculum case, as compared to the vanilla test condition.

heading: 3.2 SELF-TAUGHT CURRICULUM LEARNING VS. SELF-PACED LEARNING

text:
Curriculum learning is closely related to the idea of Self-Paced Learning (SPL), an iterative procedure where higher weights are given to training examples that have lower cost with respect to the current hypothesis. In fact, SPL may appear similar, or closely related, to the idea of self-taught learning. The main difference between the methods is that self-paced learning determines the scoring function according to the loss with respect to the current hypothesis (or network), while the self-taught scoring function is based on the loss with respect to the final hypothesis of a trained network. In accordance, we define the self-paced scoring function, where each point is scored by its
7For more details, see Appendix C
loss with respect to the current network. Note that when using CL to optimize the linear regression loss (see introduction), self-taught curriculum and self-paced learning are discordant.
To compare the self-taught scoring function and the self-paced scoring function, we investigate their effect on CL in the context of empirical case 1. Results are shown in Fig. 4b. As expected, we see that CL using the self-taught scoring function improves the test accuracy throughout the entire learning session. On the other hand, CL training using the self-paced scoring function decreases the test accuracy throughout. This decrease is more prominent at the beginning of the learning, where most of the beneficial effects of the curriculum are observed, suggesting that the self-paced scoring function can significantly delay learning.

heading: 3.3 THE SCORING FUNCTION: ANALYSIS AND EMPIRICAL EVALUATION

text:
In order to analyze the effects of transfer based scoring functions, we turn to analyze the gradients of the network’s weights w.r.t the empirical loss. We evaluate the gradients using a pre-trained vanilla network in the context of case 1. First, for each method and each scoring function, we collect the subset of points used to sample the first mini-batch according to the pacing function gFθ (1)
8. For comparison, we also consider the set of all training points, which are used to compute the exact gradient of the empirical loss in batch learning using GD. We then compute the corresponding set of gradients for the training points in each of these subsets of training points, treating each layer’s parameters as a single vector, and subsequently estimate the gradients’ mean and total variance9, used to evaluate the coherence of the gradients in the first mini-batch of each scoring function. The Euclidean distance between the mean gradient in the different conditions is used to estimate the similarity between the different scoring functions, based on the average preferred gradient.
We can now compare the set of gradients thus defined using three transfer scoring functions, which differ in the parent network used for scoring the points: ’VGG-16’, ’Resnet’, and ’Inception’. We include in the comparison the gradients of the random scoring function denoted ’Random’, and the gradients of the whole batch of training data denoted ’All’. Results are shown in Fig. 6.
We see in Fig. 6a - blue bars - that the average gradient vectors, computed based on the 3 transfer scoring functions, are quite similar to each other. This suggests that they are pointing towards nearby local minima in parameters space. We also see - green bar - that the average gradient vector computed using a random subset of examples resembles the exact empirical gradient computed using all the training data. This suggests that a random subset provides a reasonable estimate of the true empirical gradient. The picture changes completely when we compute - red bars - the distance between the average gradient corresponding to one of the 3 transfer scoring functions, and the average random gradient or the empirical gradient. Now the distances are rather large, which suggests that CL by transfer indeed stirs the weights towards different local minima in parameter space as compared to vanilla training.
8In this experiment gFθ (1) was set such that it corresponds to 10% of the data or 250 examples. This number was set arbitrarily, with similar qualitative results obtained for a large range of other choices.
9As customary, total variance denotes the trace of the covariance matrix.
We see in Fig. 6b that the total variance for the 3 transfer scoring functions is much smaller than the total variance of some random subset of the whole training set. This intuitive result demonstrates the difference between training with easier examples and training with random examples, and may – at least partially – explain the need for a different learning rate when training with easier examples.

heading: 3.4 ALTERNATIVE PACING FUNCTIONS

text:
Single step pacing. Curriculum learning can be costly, and it affects the entire learning protocol via the pacing function. At the same time, we note that the main effect of the procedure takes place at the beginning of training. This empirical observation may be due, in part, to the fact that the proposed scoring function f is based on transfer from another network trained on a different dataset, which only approximates the unknown ideal scoring function. Possibly, since the scoring function is based on one local minimum in a complex optimization landscape which contains many local minima, the score given by f is more reliable for low scoring (easy) examples than high scoring (difficult) examples, that may be in the vicinity of a different local minimum.
Once again we evaluate case 1, using the transfer scoring function and the single step pacing function. We see improvement in the test accuracy in the curriculum test condition which resembles the improvement achieved using the exponential pacing. Results are shown in Fig. 7a. It is important to note that this pacing function ignores most of the prior knowledge provided by the scoring function, as it only uses a small percent of the easiest examples, and yet it achieves competitive results. Thus we see that in our empirical setup, most of the power of CL lies at the beginning of training.
Varied exponential pacing. This pacing function allows us to run a CL procedure without the need for further tuning of learning rate. Once again we evaluate case 1, fixing the learning rate parameters to be the same as in the vanilla test condition, while tuning the remaining hyper-parameters as described in Section 2.3 using a grid search with cross-validation. We see improvement in the accuracy throughout the entire learning session, although smaller than the one observed with fixed exponential pacing. However, decreasing the learning rate of the vanilla by a small fraction and then tuning the curriculum parameters achieves results which are very similar to the fixed exponential pacing, suggesting that this method can almost completely nullify the indirect manipulation of the learning rate in the fixed exponential pacing function. These results are shown in Fig. 7b.

heading: 3.5 SUMMARY OF RESULTS

text:
Fig. 8 summarizes the main results presented in the paper, including: curriculum with an Inceptionbased scoring function for (i) fixed exponential pacing (denoted curriculum), (ii) varied exponential pacing, and (iii) single step pacing. It also shows curriculum with fixed exponential pacing for (iv) self-paced scoring, and (v) self-taught scoring. In addition, we plot the control conditions of vanilla, anti -curriculum, and random. In Fig. 8a we see the learning curves of the above conditions, with inset bars that depict the final accuracy of each condition, and error bars that represent the standard error after 50 repetitions. All the curriculum conditions seem to improve the learning accuracy throughout the entire learning session while converging to similar performance, excluding the selfpaced scoring function which impairs learning.
The learning curves shown in Fig. 8a were obtained by searching for the parameters that maximize the final accuracy. This procedure only takes into account a few data points, which makes it less robust. In Fig. 8b we plot the bars of the final accuracy of the learning curves obtained by searching for the parameters that maximize the Area Under the Learning Curve. AUC is positively correlated with high final performance while being more robust. Comparing the different conditions using this maximization criterion gives similar qualitative results - the performance in all the curriculum conditions is still significantly higher than the control conditions. However, now the curriculum based on the Inception-based scoring function with fixed exponential pacing achieves performance that is significantly higher than the other curriculum methods, in evidence that it is more robust.

heading: 4 SUMMARY AND DISCUSSION

text:
Above we formally defined a curriculum learning algorithm, decomposing it into two separate problems: (i) How to determine the difficulty of the training data (via the scoring function)? (ii) At which pace should the learner be shown the more advanced data (via the pacing function)? We defined a scoring function based on transfer learning from a large network, showing that it can both speed up the rate of learning and improve the final accuracy. This was shown using a number of test cases, including particularly challenging subsets of CIFAR 100 and ImageNet datasets, and the entire CIFAR-10 and CIFAR-100 datasets. We used both a relatively small hand-crafted CNN, and a large public-domain completive VGG-based network. We observed that most of the beneficial effect of CL was achieved at the beginning of the learning and that the benefits were more significant when using harder datasets. During our experiments, we saw that the quality of the teacher network also impacts curriculum learning by transfer. In order for the teacher network to differentiate between easier and harder examples, it should have reasonable generalization accuracy. A teacher with low performance will classify all points as hard, while a ”too good” teacher will classify all points as easy, results in a less efficient curriculum. Based on these observations, we investigated two alternative pacing functions that achieved CL with less overhead as compared to training without a curriculum.
In addition to the transfer scoring function, we introduced the self-taught scoring function. This function does not rely on transfer from a large network, and can therefore, presumably, better scale up to larger datasets. Self-Taught scoring is closely related to Self Paced Learning, yet it boils down to essentially the opposite scoring heuristics, since the self-taught scoring function relies on the final hypothesis of a pre-trained network while SPL relies on the current hypothesis. In agreement with the theory reviewed in the introduction, we showed that the self-paced scoring function impaired the learning, while the self-taught scoring function enhanced it. In other words, when choosing easier points to guide the learning, it is important to measure difficulty with respect to the final hypothesis, not the current hypothesis.

heading: A ADDITIONAL EMPIRICAL RESULTS

text:
CL with other CIFAR-100 super-classes. In Section 3 we present results when learning to discriminate the ”small mammals” superclass of CIFAR-100. Similar results can be obtained for other super-classes of CIFAR-100, including the super-classes of ”people”, ”insects” and ”aquatic mammals”. CL trained on these different super-classes shows the same qualitative results. We note once again that CL is more effective in the harder tasks, namely, the super-classes containing classes that are harder to discriminate (as seen by lower vanilla accuracy). As an example, Fig. 9 shows results using the ”aquatic mammals” dataset, which greatly resembles the results we’ve seen when discriminating the ”small mammals” dataset (cf. Fig.8).
Transfer based scoring function. In the experiments described in Section 3, when using the transfer scoring function defined in Section 2.3, we use the pre-trained Inception network available from https://github.com/Hvass-Labs/TensorFlow-Tutorials. We first normalized each training image to the range [−1, 1], resized it, and ran it through the Inception network. We then used the penultimate layer’s activations as features for each training image, resulting in 2048 features per
image. Using these features, we trained a Radial Basis Kernel (RBF) SVM (Scholkopf et al., 1997) and used its confidence score to determine the difficulty of each image. The confidence score of the SVM was provided by sklearn.svm.libsvm.predict proba from Python’s Sklearn library and is based on cross-validation.
Choosing Inception as the teacher and RBF SVM as the classifier was a reasonable arbitrary choice – the same qualitative results are obtained when using other large networks trained on ImageNet as teachers, and other classifiers to establish a confidence score. Specifically, we repeated the experiments with a transfer scoring function based on the pre-trained VGG-16 and Resnet networks, which are also trained on Imagenet. The curriculum method using the transfer scoring function and fixed exponential pacing function are shown in Fig. 10a, demonstrating the same qualitative results. Similarly, we used a linear SVM instead of the RBF kernel SVM with similar results, as shown in Fig. 10b. We note that the STE error bars are relatively large for the control conditions described above because we only repeated these conditions 5 times each, instead of 50 in the main experiments.

heading: B EXTENDED DISCUSSION

text:
Self-taught bootstrapping In principle, the self-taught scoring function can be used repeatedly to boost the performance of the network indefinitely: after training the network using a curriculum, we can use its confidence score to define a new scoring function and retrain the network from scratch. However, scoring functions created by repeating this procedure tend to accumulate errors: once an example is misclassified as being easy, this example will be shown more often in subsequent iterations, making it more likely to be considered easy. In practice, we did not observe any benefit to repeated bootstrapping, and even observed the impairment after a large number of repetitions.
FAIR COMPARISON IN PARAMETER TUNING
When using the moderate size hand-crafted network (cases 1, 2 and 3), learning rate tuning is done for the vanilla case as well. In these cases, for the curriculum, anti-curriculum and random test conditions, we perform a coarse grid search for the pacing hyper-parameters as well as the learning rate hyper-parameters, with an identical range of values for all conditions. For the vanilla condition, there are no pacing hyper-parameters. Therefore, we expand and refine the range of learning rate hyper-parameters in the grid search, such that the total number of parameter combinations for each condition is approximately the same.
When using a public domain competitive network (case 4), the published learning rate scheduling is used. Therefore we employ the varied exponential pacing function without additional learning rate tuning and perform a coarse grid search on the pacing hyper-parameters. To ensure a fair comparison, we repeat the experiment with the vanilla condition the same number of times as in the total number of experiments done during grid search, choosing the best results. The exact range of values that are used for each parameter is given below in Appendix C. All prototypical results were
confirmed with cross-validation, showing similar qualitative behavior as when using the coarse grid search.
LEARNING RATE TUNING
To control for the possibility that the results we report are an artifact of the way the learning rate is being scheduled, which is indeed the method in common use, we test other learning rate scheduling methods, and specifically the method proposed by Smith (2017) which dynamically changes the learning rate, increasing and decreasing it periodically in a cyclic manner. We have implemented and tested this method using cases 2 and 3. The final results of both the vanilla and curriculum conditions have improved, suggesting that this method is superior to the naı̈ve exponential decrease with grid search. Still, the main qualitative advantage of the CL algorithm holds now as well - CL improves the training accuracy during all stages of learning. As before, the improvement is more significant when the training dataset is harder. Results for case 3 (CIFAR-100) are shown in Fig. 11.

heading: C METHODOLOGY, ADDITIONAL DETAILS

text:
Exponential Pacing Throughout this work, we use pacing functions that increase the data size each step exponentially. This is done in line with the customary change of learning rate in an exponential manner.
Architecture Details The moderate-size neural network we used for cases 1,2,3, is a convolutional neural network, containing 8 convolutional layers with 32, 32, 64, 64, 128, 128, 256, 256 filters respectively. The first 6 layers have filters of size 3 × 3, and the last 2 layers have filters of size 2 × 2. Every second layer there is a 2 × 2 max-pooling layer and a 0.25 dropout layer. After the convolutional layers, the units are flattened, and there is a fully-connected layer with 512 units followed by 0.5 dropout layer. Batch size was 100. The output layer is a fully connected layer with 5 output units, followed by a softmax layer. We trained the network using the SGD optimizer, with cross-entropy loss. All the code will be published upon acceptance.
Grid-search hyper parameters When using grid search, identical ranges of values are used for the curriculum, anti-curriculum and random test conditions. Since vanilla contains fewer parameters to tune – as it has no pacing parameters – we used a finer and broader search range. The range of parameters was similar between different scoring functions and pacing functions and was determined by the architecture and dataset. The range of parameters for case 1: (i) initial learning rate: 0.1 ∼ 0.01; (ii) learning rate exponential decrease 2 ∼ 1.1; (iii) learning rate step size 200 ∼ 800; (iv) step size 20 ∼ 400, for both varied and fixed; (v) increase 1.1 ∼ 3; (vi) starting percent 4% ∼ 15% (note that 4% is in the size of a single mini-batch). For cases 2, 3 the ranges is wider since the dataset is larger: (i) initial learning rate: 0.2 ∼ 0.05; (ii) learning rate exponential decrease 2 ∼ 1.1; (iii) learning rate step size 200 ∼ 800; (iv) step size 100 ∼ 2000, for both varied
and fixed; (v) increase 1.1 ∼ 3; (vi) starting percent 0.4% ∼ 15%. For cases 4, the learning rate parameters are left as publicly determined, while the initial learning rate has been decreased by 10% from 0.1 to 0.09. The pacing parameter ranges are: (i) step size 50 ∼ 2500, for both varied and fixed; (ii) increase 1.1 ∼ 2; (iii) starting percent 2% ∼ 20%.
ImageNet Dataset Details In case 5, we used a subset of the ImageNet dataset ILSVRC 2012. We used 7 classes of cats, which obtained by picking all the hyponyms of the cat synset that appeared in the dataset. The 7 cat classes were: ’Egyptian cat’, ’Persian cat’, ’cougar, puma, catamount, mountain lion, painter, panther, Felis concolor’, ’tiger cat’, ’Siamese cat, Siamese’, ’tabby, tabby cat’, ’lynx, catamount’. All images were resized to size 56× 56 for faster performance. All classes contained 1300 train images and 50 test images.