Title: A PROPOSED HIERARCHY OF DEEP LEARNING TASKS Anonymous authors Paper under double-blind review

Abstract: As the pace of deep learning innovation accelerates, it becomes increasingly important to organize the space of problems by relative difficultly. Looking to other fields for inspiration, we see analogies to the Chomsky Hierarchy in computational linguistics and time and space complexity in theoretical computer science. As a complement to prior theoretical work on the data and computational requirements of learning, this paper presents an empirical approach. We introduce a methodology for measuring validation error scaling with data and model size and test tasks in natural language, vision, and speech domains. We find that power-law validation error scaling exists across a breadth of factors and that model size scales sublinearly with data size, suggesting that simple learning theoretic models offer insights into the scaling behavior of realistic deep learning settings, and providing a new perspective on how to organize the space of problems. We measure the power-law exponent-the "steepness" of the learning curve-and propose using this metric to sort problems by degree of difficulty. There is no data like more data, but some tasks are more effective at taking advantage of more data. Those that are more effective are easier on the proposed scale. Using this approach, we can observe that studied tasks in speech and vision domains scale faster than those in the natural language domain, offering insight into the observation that progress in these areas has proceeded more rapidly than in natural language.

1. INTRODUCTION:

There are so many new exciting deep learning results published every day that it is hard to see the big picture. Many of these papers report exciting performance on a particular solution to a particular task, but it is hard to know how well those results are likely to generalize beyond the particulars in a particular paper. In undergraduate classes on Algorithms, we are taught how to reduce one problem to another, so we can make claims about time and space complexity that generalize across a wide range of problems.

It would be much easier to make sense of the deep learning literature if we could find ways to generalize more effectively across problems. What can nets do, and what can't they do? Which tasks are relatively easy and which are relatively hard? Which problems require more resources? Is it possible to come up with an organization of the deep learning literature that is somewhat similar to the Chomsky Hierarchy, Chomsky (1957) , in Table 1 ? The Chomsky Hierarchy makes it clear what can (and cannot) be done within broad classes of computational resources. Finite state machines can do many things, but they can't solve the Halting Problem (because nothing can solve the Halting Problem). Finite state machines also can't solve problems that take more than constant space and linear time such as sorting large vectors, multiplying large matrices, and more.

We would like to come up with statements about deep nets that generalize across topics. In particular, it might be useful to view certain exciting deep nets like convolutional neural nets as (large) finite state machines, and therefore, some of the statements mentioned above may apply to these nets. Obviously, there are well-known ways to go beyond finite-state, such as (Sun et al. (2017b) ), but doing so is not necessarily a good thing (because doing so tends to lead to increases in computational costs). Much of the excitement in neural nets is focused on recent progress in speech and vision, where it may not be necessary (and even desirable) to go beyond finite state. That said, it may not be all that helpful to focus too much on time and space, since training data appears to be more of a limiting factor on progress than time and space complexity. This paper will propose an organization of the deep nets literature based on training data, as opposed to time and space. The ranking of problems is intended to make it easier to generalize across tasks. If we have a new problem, can we compare it to a bunch of known problems in a meaningful way? Can this ranking help us estimate how easy or hard the new problem is? How do we estimate requirements on computational resources for a new problem?

This paper will suggest a particular proposal for ranking deep net problems based on learning curves. In general, there is no data like more data, but we find that some deep net tasks are more effective than others in taking advantage of more data. We suggest fitting learning curves to a power law, and then sorting tasks by empirical estimates of exponents. That is, we assume that loss, E(m), can be modeled as a function of training set size, m, with: E(m) = αm βg . We propose sorting problems by the exponent: β g .

Dimensionless quantities (like β g ) are convenient for making comparisons across different problems.

In general, different problems use different units. For example, in computational linguistics, it makes sense to measure the size of the training set in terms of words and/or characters, and to measure loss in terms of perplexity, but these metrics generally do not generalize well to other problems such as speech and vision. Since β g is dimensionless, it is more suitable for comparisons across problems than alternatives such as m, E(m), α, where the units tend to vary from one problem to another.

β g can depend on a number of factors including task and metric. We not only see important differences in β g across tasks, but we also see differences across metrics. As we will see in Section 4.1, β g for top-1 classification can be different from β g for top-5 classification, even on the same task.

It isn't easy to measure β g over lots of solutions to lots of problems. It took about 50 GPU years to estimate the β g s in this paper. We not only considered a range of different problems, but also a range of different models (with more or less capacity), optimizers, regularizers and loss functions. We will show examples where different solutions improve the constants, α, but we are more interested in improvements in β g .

An interesting question for future work is why β g is different in different cases. Our estimates of β g are similar to estimates of cross-entropy. It is common practice with cross-entropy to try a number of different models, and return the best of those attempts. Cross-entropy is bounded by the true entropy of the task. There is a gap between the two because there may be a better solution than the ones that we considered. So too, with estimates of β g , it is hard to separate fundamental properties of the problems from concerns that there may be a better solution than the ones we considered.

The main point of this paper is to start a discussion in search of a big picture that will eventually lead to agreement on how to generalize beyond the particulars in a particular deep net paper. It would be nice if our particular proposal is adopted, but it is more important to us that the field agree on a satisfactory solution than that they adopt our particular proposal.

This paper is organized as follows: We begin with a review of related work measuring relationships between data set size, model size, and error in Section 2. Section 3 describes our methodology, and Section 4 shows learning curve results from the five tasks. Section 5 applies our proposed organization to these tasks. The left panel is borrowed with permission from Banko and Brill (2001) . Brill has suggested firing everyone to fund data collection (personal communication), perhaps in jest, though that comment is not in the published paper.

2. RELATED WORK:

Empirical Studies: Figure 1 compares a well known result from (Banko and Brill (2001) ) (left) with a cartoon sketch of a power law (right). Banko and Brill (2001) test a language modeling problem (confusion set disambiguation) trained using subsets of a billion-word corpus of text. Their results show that there is no data like more data. Performance on this disambiguation task improves with the size of the training set, roughly consistent with a power law. They note that some learning methods are slightly better at one operating point, and others are slight better at another operating point. But those small differences are dominated by a more important trend. A rising tide lifts all boats; more data improves performance for all methods. More data is more important than relatively small differences between methods.

Power-law-like learning curves have been reported by a number of researchers for a number of applications. Jelinek refers to Banko and Brill (2001) and Lamel et al. (2002) in his speech accepting the Zampolli prize at LREC-2004. 1 Amodei et al. (2016) show an improvement in WER (word error rate) for a Deep Speech 2 model with more and more training data; Sun et al. (2017a) report similar improvements for object detection and semantic segmentation tasks.

The cartoon on the right of Figure 1 shows a similar power-law pattern for loss (as opposed to accuracy). More training data improves performance (left) and reduces loss (right). The cartoon on the right splits the learning curve into three regions. We are most interested in the middle region where the power-law assumption is more appropriate. Theoretical Analysis: There is a considerable literature deriving theoretical bounds on the generalization gap between expected and empirical error. At least five lines of work derive bounds that follow power laws on the number of training samples:

1. Hypothesis space bounds in PAC learning (Haussler (1988) ) using Vapnik-Chervonenkis (VC) dimension (Ehrenfeucht et al. (1989) ; Blumer et al. (1989) ; Haussler et al. (1996) ), 2. Rademacher complexity in (Bartlett and Mendelson (2002) and Mohri et al. (2012) ), 3. the stability approach in (Bousquet and Elisseeff (2002) ) considers the dependence of the learned model on the training dataset, as well as how much individual changes to the training dataset can affect the learned model, 4. the robustness approach in (Xu and Mannor (2012) ) measures how much the error can vary with the input space, 5. (Amari et al. (1992) and Amari (1993) ) derive bounds using statistical mechanics. Kawaguchi et al. (2017) provides a clear survey of much of this prior work.

We follow the tradition in much of this literature of introducing a power law assumption. In spite of the complex nature of real tasks, the reliable observation of power-law learning curves in our experiments suggests that deep learning exhibits the same scaling phenomena as those that are simple to analyze theoretically.

Model Capacity Required to Fit Data: This work will assume that both loss and model capacity obey power laws. Prior studies propose various measures of model capacity based on a model's organization and parameterization, and these measures hint at the model size required to fit a training set. Vapnik and Chervonenkis defined the VC dimension of a model as the cardinality of the largest set of data points that a model can shatter (Vapnik (1998) ). Follow-on work uses data complexity measures to estimate the structure of model families that might fit the data (Bartlett and Mendelson (2002) ). Recent work explores applying these concepts to deep nets (Harvey et al. (2017) ; Dziugaite and Roy (2017); Collins et al. (2017) ).

Prior work to empirically estimate model scaling with training set size is very sparse. In our experiments, we find power-laws produce good fits, i.e. s(m) ∝ αm βp , where s(m) is the required model size to fit a training set of size m, and β p ∈ [0.5, 1]. When applying this approach to the data in Banko and Brill (2001) , we find that the Winnow and memory-based models grow with the same power-law exponent to larger data sets, β p ≈ 0.72.

3. METHODOLOGY:

Ideally we are interested in learning curves that depict the relationship between the expected error of models in the wild and the amount of training data. However, expected error in a real setting cannot be measured. So we follow the common practice of approximating it with empirical error computed on a held-out validation set (this choice explained further in Appendix B), and plot this instead. We divide a training set into independent shards of different sizes, perform a hyper-parameter grid search over optimizer parameters and model sizes to find the best model for each shard, and plot the validation error of that model.

We ensure that the training set is randomly shuffled so that shards will have a similar data distribution. We use the same validation set for all models, and size it empirically such that measurements have low variance. Depending the task, error metrics include cross-entropy, L p norms, and classification error (see Appendix A for more details). We search over different model sizes by varying the hidden dimension, but do not make other changes to the architecture except where noted. We use early stopping for regularization in all cases.

4. LEARNING CURVE RESULTS:

We present empirical results characterizing learning curves for machine translation, language modeling, image classification, and speech recognition tasks. We focus our discussion on image recognition and word language modeling to highlight example tasks that learn relatively fast and slow with data. The other tasks and experiments are described in more detail in Appendix C.

4.1. IMAGE CLASSIFICATION:

We begin with image classification, a well-studied task that aims to identify objects in highdimensional image data. Image classification is used in applications such as object recognition, image captioning, and tagging video content. Image classification shows clear power-law learning curves and model size scaling relationships. We also show that accuracy plateaus near random guessing on very small training sets.

We test ResNets (He et al. (2016) ; Wu et al. (2016) ), which are popular architectures for ImageNet classification (Russakovsky et al. (2015) ). ResNets are deep networks built from blocks containing convolutions, nonlinearities, and pooling layers. They have residual connections from the inputs to outputs of most blocks that permit the network to bypass layers. We train and validate ResNets on various shard sizes of ImageNet, ranging from 1 image per class (0.08% of images) up to 800 images per class (62%). ImageNet has 1,000 different object classes as outputs.

We start with five known variants of ResNets with depths 18, 34, 50, 101, and 152 layers. We first scale the model sizes by changing the number of layers ranging from 10 to 200. To provide even finer-grained model size control, we also change the number of convolution filters using a scaling factor. We scale filter counts proportionally across all convolution blocks with scaling factors 0.0625 to 1.5. We test models with parameter counts ranging from 89K to 121M. We use a Nesterov Momentum optimizer targeting classification cross-entropy loss. We remove weight regularization.

Figure 2 (left) shows that various loss calculations follow the power-law learning curves. We report average validation cross-entropy, top-1, and top-5 classification errors. For small training setsless than roughly 25 images per class-these error metrics are roughly equal to the model random guessing (i.e., greater than -log(1/1, 000) ≈ 6.9 for cross-entropy, and near 1 -(1/1, 000) = 99.9% classification error for top-1 and top-5). Models are unable to extract enough information from these small training sets to make many accurate classifications on the validation set. This is an example of the "small data region" explained in Section 1.

As long as the training set is large enough, we observe that generalization improves on a power-law, but the power-law exponent is different for each of the reported metrics, as mentioned in Section 1. The top-1 classification error exponent is β g = -0.309, the exponent for top-5 classification error is β g = -0.522, and the validation cross-entropy exponent is β g = -0.35. Figure 2 (right) shows that model size growth is well fit by a power-law. The best-fit ResNet models grow following a sublinear curve with exponent β p = 0.573.

4.2. LANGUAGE MODELING:

Language models (LMs) aim to predict probability distributions for the next character, word, or other textual grams conditioned on a previous sequence of input text. LMs are very important model features for domains such as speech recognition and machine translation, helping to identify most probable sequences of grams. LMs have low-dimensional input and output spaces, and can be trained with very large labeled sets.

LM learning curves and model size scaling relationships are very robust, and the power-law exponents tend to be small (β g ∈ [-0.09, -0.06]). These small exponents indicate that current language models will require significantly more data to significantly improve accuracy. The models that give the best validation error grow sublinearly in the training set size (β p ≈ 0.7). Note that all models exhibit the same β g regardless of depth or cell type (LSTM vs RHN).

4.2.1. WORD LANGUAGE MODELS:

We train LSTM-based word LMs as described in Jozefowicz et al. (2016) with some small changes. To reduce the computational requirements of the models, we restrict the vocabulary to the top 10,000 most frequent words in the Billion Word Dataset (Chelba et al. (2013) ). The networks are 2-or 4layer LSTMs with the same number of hidden weights in each layer, and we scale the number of layer weights to modulate the model size and find the best fit model for each training shard size. We also compare LSTMs against Recurrent Highway Networks (RHNs) described in Zilly et al. (2017) . Specifically, we train single-layer, depth 5 RHNs to see if the different network organizations show different generalization trends. We use a stochastic gradient descent optimizer (SGD) with persequence cross-entropy loss, and we report per-predicted-word average cross-entropy loss. We do not use dropout. We train the models on shards ranging from 0.1% up to 40% of the Billion Word Dataset.

Figure 3 shows the learning curve and model size results for LSTM and RHN word language models. First, the loss scaling relationships are smooth power-law functions of the data set size with almost exactly the same exponents: β g = -0.0656 ± 1%. Larger models are more computationally expensive, and we have more difficulty optimizing to fit the larger training sets given our compute resources. The best tuned models settle at or just above the power-law trend, and we believe that further hyperparameter search is likely to yield a model on the trend.

Strikingly, although these model architectures differ appreciably, they all show the same learning curve profile characterized by the power-law exponent. Increasing the LSTMs depth from 2 to 4 layers decreases the networks' accuracy by about 1.5%, but both model architectures see the same relative loss improvement as we increase training set size. RHNs have significantly different recurrence structure than LSTMs, but show nearly identical learning curves.

Model size results show that best-fit models grow sublinearly in the training shard size. Specifically, the best-fit 2-layer LSTM and depth-5 RHNs model sizes grow roughly with β p = 0.69. The 4layer LSTMs show slightly worse scaling with β p = 0.89, suggesting they make less effective use of extra parameters on larger data sets. Despite the model size scaling differences, for a given model architecture, we can accurately predict the model size that will best fit increasingly larger data sets.

These results underscore the importance of continued data and computational scaling for the natural language domain. Note that overall the variance is small relative to the reduction in validation error, and that the variance is reduced with more training data and also with larger models.

4.3. SENSITIVITY OF RESULTS:

Given that we present empirical measurements of scaling, it would be valuable to estimate the basic statistics of our scaling model parameters (α g , β g , γ g , α p , β p ). However, our experiments collectively used about 50 years of GPU time, so generating each sample is extremely expensive. For example, computing confidence intervals for each parameter using 30 samples would require 1500 GPU years of compute time, and we don't have that many resources. In this section, we perform additional experiments requiring about two months of training time to study the repeatably of our results for one domain.

Figure 4 uses a violin plot to show the distribution of validation errors across 30 repetitions of the machine translation experiment with 8M and 67M parameters with different seeds for weight initialization and shard creation, for each training data shard size. We find that overall the variance is small relative to the reduction in validation error for each shard, and that the variance is reduced with more training data and also with larger models (similar to the observations in Choromanska et al. (2014) ). This suggests that our results are repeatable and will become even more stable for larger datasets.

4.4. SUMMARY OF RESULTS:

Our results are summarized in Table 2 , illustrating how β g (and β p ) can be used to make comparisons across a wide range of diverse tasks. Less is more. Smaller β g s are better. In general, there is no data like more data, but some tasks are more effective than others in taking advantage of more data. Note that speech and vision have better β g s than other tasks mentioned in Table 2 . It is probably not an accident that the field is relatively excited about the tasks with better β g s.

The tasks with better β g s also tend to have better β p s. That is, there appears to be a relationship between parameter requirements (β p ) and generalization/effectiveness in taking advantage of more data (β g ). β p is particularly worrisome for Language Modeling on characters; ideally, nets ought to be learning models that are considerably smaller than the training set (β p 1), but with β p = 0.89, there are almost as many parameters as training samples. Table 2 : The proposed hierarchy: a ranking of deep learning tasks sorted by β g . In general, there is no data like more data, but some tasks are more effective than others in taking advantage of more data. Note that speech & vision have better β g s than language modeling. This may help explain why there is relatively more excitement about deep nets in speech and vision (vs. language modeling).

5. DISCUSSION:

It is interesting that the order produced by sorting applications by β g is aligned with the observation that progress in computer vision and speech recognition has proceeded relatively quickly. We note that both of these tasks use relatively high dimensional input data. Studied speech and vision tasks learn faster with additional training data. Clearly, there appears to be scope for all of these tasks to further improve accuracy by training on more data, but these results suggest that the computational and data requirements for language modeling in particular will be more challenging.

We are left with the open question of whether or not it is possible for learning algorithms to improve β g or β p . In our results we noted that β g appeared stable across changes in neural network architecture, regularization method, and optimization algorithm. It changed between tasks such as language modeling vs. image classification and between metrics such as top-1 vs. top-5 classification error. We hypothesize that it is bounded by properties of the task setup and data distribution, and challenge future work to precisely determine the factors that affect it. Regarding β p , simply memorizing the dataset would yield β p = 1.0, and it is interesting to note that all studied algorithms improve on this.

There may be scope in future work to further improve on it beyond the models that we have studied.

There is also clearly scope for a more detailed organization of tasks within important domains. We can already see that machine translation has a smaller β g than language modeling in spite of both working with low dimensional natural language data. We expect future work to use this methodology to guide efforts on the most valuable tasks that can be improved the most quickly.

6. CONCLUSION:

The Chomsky Hierarchy in computational linguistics and time and space complexity in theoretical computer science have been instrumental in guiding work on open problems. We have measured the power-law exponent (β g ) -the "steepness" of the learning curve-and propose using this metric to rank problems by degree of difficulty. There is no data like more data, but some tasks are more effective at taking advantage of more data. We find that the problems that the field is most excited about in speech and vision have better β g s than problems that the field is less excited about (such as language modeling). When applied to an even wider set of problems, we hope that such a hierarchy can serve as a guide to the data and computational requirements of open problems.

A.4.2 ATTENTION MODEL:

Similar to the DS2 model, the attention model uses a stack of recurrent layers with GRU cells as the encoder. The decoder consists of an attention layer followed by a recurrent layer. The attention mechanism aligns the input sequence to the output sequence. The attention mechanism removes the conditional independence assumption in output sequence that the DS2 model makes. More model, attention mechanism, and loss function details can be found in Battenberg et al. (2017) .

B USING VALIDATION ERROR:

This section provides intuition about why learning curves that plot validation error against training data set size are relevant for deep learning.

Let X be an input space and Y be an output space. Let Loss be a loss function.

Let m be the number of training samples. Let T m = ((x 1 , y 1 ), ..., (x m , y m )) ∼ P be a sequence of training samples that is drawn independently from true distribution P , and V ∼ P be a validation set drawn independently from the same distribution P .

Let M = DL_ALG(S m ), where DL_ALG is a learning algorithm that yields a trained model M DL_ALG(Sm) : X → Y , such as a deep neural network trained with stochastic gradient descent on training set S m .

EQUATION

Let E(M ) be the expected risk, i.e. the expectation of evaluating the trained model M DL_ALG(Sm) on the true distribution P .

EQUATION

Let Ê(M ) be the empirical risk.

In an empirical risk minimization setting, we are concerned with the generalization gap, i.e. E(M DL_ALG(Sm) ) -ÊSm (M DL_ALG(Sm) ).

ÊV (M:

EQUATION

Let ÊV be the empirical risk on a held out validation set.

In practical deep learning settings, it is common to use ÊV to approximate E(M DL_ALG(Sm) ). This is a good approximation for sufficiently large validation sets if M is independent of V.

We use hyperparameter search including early stopping and model size selection to find models with the best validation error ÊV for each S m . We assume that the limited number of evaluations performed does not introduce a significant dependence on V, which is aligned with best practices.

In some cases, we use a completely different V for hyperparameter search.

In this setting, we rely on ÊV being a good approximation of E(M DL_ALG(Sm) ).

However, we still may need to contend with error due to optimization or error due to approximation.

Regarding these errors, it is well known that deep neural networks have sufficient capacity to overfit on many natural datasets, and reduce training error to zero, e.g. as studied in Zhang et al. (2017) . Indeed for all of our studied tasks, we find that it is possible to train deep neural network models to reduce the training error below the validation error, resulting in overfitting. 

C OTHER TASKS:

C.1 NEURAL MACHINE TRANSLATION One of our studied tasks is neural machine translation (NMT). Translation converts text input in one natural language to output text in another language. Relative to other tasks, NMT has lowdimensional input and output spaces, and can be trained with large labeled data sets. Our results show learning curve character similar to theoretical predictions, with a moderate exponent (i.e., β g ≈ -0.128).

To test NMT, we train a sequence-to-sequence model with global attention (Luong et al. (2015) ) on the 2016 Conference on Machine Translation (WMT'16) German-to-English data set. We use a publicly available implementation of this architecture in OpenNMT (Klein et al. (2017) ). The encoder contains two layers of bidirectional LSTMs, and the decoder contains the attention layer and stack of LSTM layers. To simplify training this model, we remove ensembling and data augmentation techniques (Sennrich et al. (2016b) ).

To scale model sizes, we tie LSTM input and hidden state sizes together, and change them so that the total parameter count varies roughly linearly with a single scale factor parameter. We use Adam to optimize per-sequence cross-entropy loss and report the per-token classification error. We select models using the newstest2015 validation set, and we use the other newstest development sets from 2009 to 2013 for evaluation. Results presented here are with dropout rate of 0.2, though we tested without dropout and found similar learning curve exponents.

We clean and tokenize the data set using Moses (Koehn et al. (2007) ) as described by Luong et al. (2017) . We use the byte-pair encoding (BPE) method described by Sennrich et al. (2016a) to build a shared word-piece vocabulary between English and German. After preprocessing, the training set includes 4.5 million training sequences with roughly 130 million tokens in each language. We uniformly randomly shuffle the training data and sample training shards as described in Section 3.

Prior work predicts that as a model runs out of capacity on larger data sets, the error should plateau, resulting in a power-law + constant, E(m) ∼ αm βg + γ, where γ is the error when the model family has exhausted its capacity. Note the addition γ term compared to the model used in other experiments.

Indeed, we find that learning curves for a single model family can be closely represented by a powerlaw + constant. We start by training fixed size models on each of the training shards. The left plot in Figure 5 shows the learning curves for two different model sizes with 208 or 512 hidden nodes per LSTM layer (17M and 48M parameters, respectively). Learning curves with β g = -0.360 and -0.300, respectively, fit the empirical results with less than 0.6% relative root mean square error.

The right plot in Figure 5 shows the composite learning curve for the best model at each shard size. Note the lack of a γ term in this model. The best-fit results form a longer power-law region. We find that β g is even smaller than the single-model learning curves; if we project forward, β g would be approximately -0.128.

We also note that as training set sizes grow, optimization becomes more difficult and computational requirements limit the turn around time for experiments, so the empirical error tends away from the power-law trend. This divergence is common across domains, and we expect to need a more exhaustive hyperparameter search to find results closer to the existing power-law.

C.2 CHARACTER LANGUAGE MODELS:

To test character-level language modeling, we train RHNs of depth 10, which we found to achieve high accuracy on the Billion Word data set. We scale the number of layer weights to modulate the model size and find the best fit model for each training shard size. We use SGD, optimizing for per-predicted-character cross-entropy loss, which we report on the validation set. We also compare SGD against the Adam optimizer to test their effects. The input and output vocabulary includes all alphanumeric characters and common symbols for total size 98. We train the models on shards of 0.01% up to 4% of the Billion Word data set.

Results for character LMs appear substantially similar to word LMs. Figure 6 plots the validation and model size scaling results for character LMs. As with word LMs, validation error improves on a power-law as training data size increases, though the exponent is β g = -0.0936 for the SGD optimizer and β g = -0.0954 for the Adam optimizer. These power-law exponents are very similar despite the significant optimizer differences-Adam appears to just shift the learning curve down by ∼ 5% relative.

Like word LMs, character LMs also learn significantly more slowly than predicted by theoretical results. Though word and character LMs have some major differences, their learning curve exponent differences indicate that character LMs are able to learn relationships between characters with successively fewer samples than word LMs are able to learn relationships between words.

Character LMs also show sublinear model size growth as data set size increases. Specifically, β p = 0.78 for SGD optimized models and β p = 0.92 for Adam optimized. Character LMs with the SGD optimizer see similar improvements from increased model size as word LMs, while the Adam optimized models see poorer scaling and require significantly more parameters (∼ 8-11×). Still, their learning and model size curves appear predictable. 2016)). Speech input data is medium-dimensionality timeseries data.

To test trends in speech recognition, we train two recent models: a variant of Deep Speech 2 (DS2) and an attention-based model. Our DS2 model (Amodei et al. (2016) ) consists of two 2D convolution layers followed by four bidirectional LSTM recurrent layers. We use Adam to optimize connectionist temporal classification loss (CTC, Graves et al. (2006) ). We compare DS2 against a hybrid attention model similar to those described by Battenberg et al. (2017) . The model has an encoder comprised of three bidirectional LSTM layers with two intermediate max-pooling layers, and a hybrid attention decoder. We use Adam to optimize output sequence average cross-entropy loss. For both models, we remove regularization (weight decay and noise).

The inputs to these models are a sequence of log-spectrograms of power normalized audio clips, calculated on 20 ms windows. Outputs are the English alphabet along with the blank symbol. We do not include language models for output sequence beam search, and we report per-predicted-output character error rate on the validation set. We train on shards of labeled data set comprising 11,940 hours of speech containing 8 million utterances Amodei et al. (2016) .

To vary the number of parameters in both the DS2 and attention models, we vary the number of weights in all LSTM layers, so that separate layers have the same number of weights. In the attention model, we also proportionally scale number of weights in the attention LSTM and decoder cells. For the DS2 model, model sizes range between 300K to 193M parameters, and for the attention based models, sizes range from 95K to 156M parameters.

Figure 7 (left) shows that both DS2 and attention based speech models experience the same powerlaw learning curve improvements. Although these models have significantly different encoders and decoders, they see the same relative improvements in character error rate as training set size increases with β g = -0.299 ± 0.7%. Consistent with prior work (Bahdanau et al. (2016) ; Battenberg et al. (2017) ), larger attention models trained on larger data sets tend to be easier to optimize than DS2 models, whose validation error tends away from the power-law trend on larger data sets.

:

http://www.lrec-conf.org/lrec2004/doc/jelinek.pdf

clean-up and byte pair encoding uses Tensorflow NMT WMT scripts

Training and data augmentation is performed using ResNet implementation in TensorPack

Figures and Tables:

Figure1: There is no data like more data. More training data improves performance (left) and reduces loss (right). The left panel is borrowed with permission fromBanko and Brill (2001). Brill has suggested firing everyone to fund data collection (personal communication), perhaps in jest, though that comment is not in the published paper.

ε xentropy (m) = 14.0 m -0.35 ε top-1 (m) = 2.24 m -0.31 ε top-5 (m) = 3.29 m -0

Figure 2: Learning curve (left) and model size (right) results and trends for ResNet image classification. Note the transition from the small data regime dominated by best guessing to the power-law scaling around 32,000 training images.

Figure 3: Learning curve (left) and model size (right) results and trends for word language models.Note that all models exhibit the same β g regardless of depth or cell type (LSTM vs RHN).

Figure 4: Violin plots of learning curves for neural machine translation. For each training data shard size, the violin plot shows the distribution of validation errors for 30 repetitions of the experiment.Note that overall the variance is small relative to the reduction in validation error, and that the variance is reduced with more training data and also with larger models.

ε(m) = 3.87 m -0.13

Figure 5: Neural machine translation learning curves. Left: the learning curves for separate models follow E(m) = αm βg + γ. Right: composite learning curve of best-fit model at each data set size.

Figure 6: Learning curve (left) and model size (right) results and trends for character language models. Note the difference in absolute accuracy and model size, but same β g and β p between SGD and Adam optimizers.

Figure 7: Learning curves for DS2 and attention speech models (left), and learning curves for various DS2 model sizes, 1.7M to 87M parameters (right). Note the similar β g despite of significant difference in training loss (CTC vs CE) and model architecture (CNN+RNN vs RNN+Attention).

Chomsky Hierarchy

Table content: <table><tr><td>Automata</td><td>Languages</td><td>Time</td><td>Space</td></tr><tr><td>Finite State (FSA)</td><td>Regular</td><td>O(n)</td><td>O(1)</td></tr><tr><td>Push Down (PDA)</td><td>Context Free (CF)</td><td colspan="2">Matrix Multiply Matrix Multiply</td></tr><tr><td>Linear Bounded</td><td>Context Sensitive (CS)</td><td>Worse</td><td>Worse</td></tr><tr><td>Turing Machines</td><td colspan="2">Recursively Enumerable Beyond Worse</td><td/></tr></table>

Peer review (iclr2019):
 The paper provides empirical evidence that the generalization error scales inversely proportional to the log of number of training samples. The motivation of the paper is well explained. A large amount of effort is put into experiments. The conclusion is consistent throughout. It is a little unclear about the definition of s(m). From the definition at the end of Section 2, it is unclear what it means to fit the training data. It can mean reaching zero on the task loss (e.g., the zero-one loss) or reaching zero on the surrogate loss (e.g., the cross entropy). I assume models larger than a certain size should have no trouble fitting the training set, so I*m not sure if the curve, say in Figure 2., is really plotting the smallest model that can reach zero training error or something else. Varying the size of the network is also tricky. Most papers, including this one, seem to be confined by the concept of layers. Increasing the number of filters and increasing the number of hidden units are actually two very structured operations. We seldom investigate cases to break the symmetry. For example, what if the number of hidden units is increased in one layer while the number is decreased in another layer? What if the number of hidden units is increased for the forward LSTM but not the backward? Once we break the symmetry, it becomes unclear whether the size of the network is really the right measure. Suppose we agree on the measure of network size that the paper uses. It is nice to have a consistent theory about the network size and the generalization error. However, it does not provide any reason, or at least rule out any reason, as to why this is the case. For example, say if I have a newly proposed model, the paper does not tell me much about the potential curve I might get. The paper spends most of the time discussing the relationship between the network size and the generalization error, but it does not have experiments supporting the hypothesis that harder problems are more difficult to fit or to generalize (in the paper*s terminology, large beta_g and large beta_p). For example, a counter argument would be that the community hasn*t found a good enough inductive bias for the tasks with large beta_g and beta_p. It is very hard to prove or disprove these statements from the results presented in the paper. This paper also sends a dangerous message that image classification and speech recognition are inherently simpler than language modeling and machine translation. A counter argument for this might be that the speech and vision community has spent too much optimizing models on these popular data sets to the point that the models overfit to the data sets. Again these statements can be argued either way. It is hard to a scientific conclusion. As a final note, here are the quotes from the first two paragraphs. "In undergraduate classes on Algorithms, we are taught how to reduce one problem to another, so we can make claims about time and space complexity that generalize across a wide range of problems." "It would be much easier to make sense of the deep learning literature if we could find ways to generalize more effectively across problems." After reading the paper, I still cannot see the relationships among language modeling, machine translation, speech recognition, and image classification.