{'fraction_non_alphanumeric': 0.024393256345334405, 'fraction_numerical': 0.015747545235595628, 'mean_word_length': 4.684099684099684, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Deep Gradient Boosting

Stochastic gradient descent (SGD) has been the dominant optimization method for training deep neural networks due to its many desirable properties. One of the more remarkable and least understood quality of SGD is that it generalizes relatively well on unseen data even when the neural network has millions of parameters. In this work, we show that SGD is an extreme case of deep gradient boosting (DGB) and as such is intrinsically regularized. The key idea of DGB is that back-propagated gradients calculated using the chain rule can be viewed as pseudo-residual targets. Thus at each layer the weight update is calculated by solving the corresponding gradient boosting problem. We hypothesize that some learning tasks can benefit from a more lax regularization requirement and this approach provides a way to control that. We tested this hypothesis on a number of benchmark data sets and show that indeed in a subset of cases DGB outperforms SGD and under-performs on tasks that are more prone to over-fitting, such as image recognition.


Introduction
Boosting, along side deep learning, has been a very successful machine learning technique that consistently outperforms other methods on numerous data science challenges. In a nutshell, the basic idea of boosting is to sequentially combine many simple predictors in such a way that their combined performance is better than each individual predictor. Frequently, these so called weak learners are implemented as simple decision trees and one of the first successful embodiment of this idea was AdaBoost proposed by Freund and Schapire [1997]. No too long after this, Breiman et al. [1998] and Friedman [2001] made the important observation that AdaBoost performs in fact a gradient descent in functional space and re-derived it as such. Friedman [2001,2002] went on to define a general statistical framework for training boosting-like classifiers and regressors using arbitrary loss functions. Together with Mason et al. [2000] they showed that boosting minimizes a loss function by iteratively choosing a weak learner that approximately points in the negative gradient direction of a functional space.
Neural networks, in particular deep neural nets with many layers, are also trained using a form of gradient descent. Stochastic gradient descent (SGD) [Robbins and Monro, 1951] has been the main optimization method for deep neural nets due to its many desirable properties like good generalization error and ability to scale well with large data sets. At a basic level, neural networks are composed of stacked linear layers with differentiable non-linearities in between. The output of the last layer is then compared to a target value using a differentiable loss function. Training such a model using SGD involves updating the network parameters in the direction of the negative gradient of the loss function. The crucial step of this algorithm is calculating the parameter gradients and this efficiently done by the backpropagation algorithm [Rumelhart et al., 1988, Werbos, 1974.
Backpropagation has many variations that try to achieve either faster convergence or better generalization through some form of regularization. However, despite superior training outcomes, accelerated optimization methods such as Adam [Kingma and Ba, 2015], Adagrad [Duchi et al., 2011] or RM-Sprop [Graves, 2013] have been found to generalize poorly compared to stochastic gradient descent [Wilson et al., 2017]. Therefore even before using an explicit regularization method, like dropout [Srivastava et al., 2014] or batch normalization [Ioffe and Szegedy, 2015], SGD shows very good performance on validation data sets when compared to other methods. The prevalent explanation for this empirical observation has been that SGD prefers "flat" over "sharp" minima, which in turn makes these states robust to perturbations. Despite its intuitive appeal, recent work by [Dinh et al., 2017] cast doubt on this explanation. This work suggests an alternative explanation for why SGD generalizes so well when training neural networks. We show that each iteration of the backpropagation algorithm can be viewed as fitting a weak linear regressor to the gradients at the output of each layer, before non-linearity is applied. We call this approach deep gradient boosting (DGB), since it's effectively a layer-wise boosting approach where the typical decision trees are replaced by linear regressors. Under this model, SGD naturally emerges as an extreme case where the network weights are highly regularized, in the L2 norm sense. In addition, DGB takes into account the correlations between training samples (features), just like regular regression would, when calculating the weight updates while SGD does not. Intuitively, it makes sense to ignore the correlations between training samples considering that the most difficult test samples would be the ones that show low correlations with the training set.
We also hypothesize that for some learning problems, the regularization criteria doesn't need to be too strict. These could be cases where the data domain is more restricted or the learning task is posed as matrix decomposition or another coding problem.

Deep gradient boosting
The classic backpropagation algorithm minimizes an error function E of a multi-layer neural network using gradient descent and the chain rule. The resulting weight updates at a given layer are ∆w i,j = x i y j where x i is the output from the previous layer at node i while y j = ∂E/∂net j is the derivative with respect to the input at node j calculated using the chain rule from the last layer to the current one. Similar to gradient boosting methods Friedman [2001,2002] we can interpret y j as a pseudo-residual and infer the weight updates ∆w i,j = v i,j such that i x i v i,j = y j , ∀j. For the extreme case of a single sample update we need to use L2 regularization which leads to the following optimization problem: For a fixed j solving the Lagrangian: yields the solution: Note that if we assume a non-zero intercept b the solutions become: It is interesting to note that this solution is similar to the weight update of stochastic gradient descent (SGD) up to a normalization term. The minimization problem in Eq. 1 can be extended to the case where each iteration is presented with a mini-batch of size B out of a total of N training samples. In this case the equality conditions might not be fulfilled exactly so we will also introduce an additional term ξ to account for that. For simplicity we'll ignore subscript j and use subscript k for the sample number: The corresponding Lagrangian is: Using the matrix notation V = (v i,j ) ∈ R n×m , X = (x k,i ) ∈ R B×n and Y = (y k,j ) ∈ R B×m , the solution to Eq. 5 is: Of note is that for α = 0 the solution V = X T (XX T ) −1 Y differs from the solution to ordinary multiple linear regression (X T X) −1 X T Y . The Gram matrix XX T from Eq. 7 measures the relation between different input samples while X T X measures the relation between different features i.e. outputs at different activation nodes. The right pseudo-inverse solution in Eq. 7 is generally preferred over the left pseudo-inverse. The reasoning behind this is two fold: (1) in general batch size is smaller than the number of neurons in a dense layer which makes the gram matrix inverse faster to calculate and (2) small sample sizes can lead to large condition number of X T X matrix.
For large values of α the term XX T + αI can be approximated with a diagonal matrix which leads to the classic SGD solution V ∝ X T Y . This shows that back-propagation with SGD implicitly minimizes the magnitude of weight updates but also ignores correlations between training samples. It is reasonable to assume that the hardest test samples are the ones that are uncorrelated with the training samples, hence using the correlation information conveyed by the gram matrix when calculating gradient updates could lead to a bias towards the training domain. SGD, by ignoring the off diagonal values of XX T , doesn't suffer from this potential shortcoming.

Gradient normalization
Variations of SGD like RMSProp [Graves, 2013], Adagrad [Duchi et al., 2011], Adam [Kingma and Ba, 2015] and other use gradient normalization techniques that in practice show faster convergence on various learning tasks. These are first order methods that are easy to calculate and in general speed-up SGD by dampening oscillations, penalizing large gradients and emphasizing small ones. One common way to achieve this is by dividing the gradients of the network weights with the squared root of their second moment calculated across batches using exponential moving average. Similarly, in the case of DGB, the gradients Y from Eq. 7 can be divided by their squared root of the second moment calculated across the samples in a single batch. These values can be combined with previously calculated moments using momentum m ∈ [0, 1): We found that DGB with normalized gradients (NDGB) generates larger weight updates so in practice the learning rates that worked best were between 1e − 4 and 1e − 6 even for large momentum values up to 0.999.

Experiments
We used five data sets in our experiments. A summary of these data sets is given in Table 1. In the case of the Higgs data set [Baldi et al., 2014] we used a randomly chosen subset with 1 million samples out of 10 million for training, and 500 thousands samples for testing. This data comes from the field of high energy physics and was generated by Monte Carlo simulations. The second data set (Reuters-21578) is comprised of 11,228 english language news articles from Reuters international news agency, labeled over 46 topics. The third data set is the Human Resource (HR) data set [Stacker IV, 2015] which was put together by IBM to predict employee attrition based on 47 features and was randomly split into 1,029 training samples and 441 test samples. The forth data set is a regression problem for predicting a measure of air quality based on the outputs from an array of chemical sensors together with air temperature and humidity [De Vito et al., 2008]. The fifth data set is the MNIST database of handwritten digits [LeCun et al.] comprised of 60,000 28x28 grayscale images for training and 10,000 for testing.  [Nair and Hinton, 2010]; all gradient updates were calculated using a momentum of 0.9. The performance metrics used are accuracy for classification tasks and root mean squared error (RMSE) for regression tasks. In addition, standard deviations were calculated for all performance measures by repeating each experiment 10 times with different random seeds.

Higgs
Higgs data set was created using Monte Carlo simulations of particle collisions and has 11 mil samples with 28 features. This is a binary classification problem designed to distinguish between a signal process which produces Higgs bosons and a background process which does not. For this exercise we kept only 1 mil samples for training and 500k for testing. All 28 features were normalized to be between 0 and 1. We found that layers with 500 nodes perform well in practice so we kept this number fixed and varied the number of layers together with batch size. The number of epochs and learning rate schedule was optimized separately for the stochastic gradient descent models (SGD) and deep gradient boosting models (DGB & NDGB). In general, α value was kept the same for both DGB and NDGB experiments. As a simulated data set Higgs should be fairly homogeneous and with so few features and so many samples the challenge is more to properly fit the training set than to worry about over-fitting. Indeed, as seen in Table 2 both DGB and NDGB outperform SGD across a variety of hyper-parameter values.

Reuters
The Reuters data set was randomly divided into 8982 training and 2246 test samples and was processed using a binary tokenizer for top 1,000 words. This data was fed into a dense neural network with two hidden layers each with 500 ReLU nodes. We found that increasing the number of layers or batch size above 30 doesn't improve the results so we kept them fixed.  Table 3 shows the results for experiments run using the SGD optimizer, DGB with α = 0.0001 and NDGB with two momentum values m, 0.9 and 0.99. This is a relatively small data set with a large number of features that is usually more successfully addressed using more advanced approaches like recurrent neural networks of convolutional neural nets. In this case, the results are only marginally better for the DGB and NDGB optimizers.

HR
Similar to the other data sets, min-max normalization was used on all 47 features of the Human resource attrition data (HR). For this experiment we tested two neural network architectures: one with three neurons in a hidden layer and a second one with 100 neurons in a hidden layer. Adding more layers didn't improve the results in fact, just three neurons were enough to achieve a good performance around 87% accuracy. With only 1029 training samples and 441 test samples the error bars (i.e. standard deviation) are too big to make a claim that DGB outperforms SGD in this case.

Air
The Air data set is a regression problem and performance was measured using root mean squared error (rmse). This data set was randomly divided into 3788 training and 3788 test samples, and all the features were min-max normalized to be between 0 and 1. For these experiments we found that performance improves across the board when adding a new hidden layer with 100 ReLU neurons, especially for the gradient boosting approaches. Both DGB and NDGB outperform SGD while NDGB obtains the best result with mean rmse = 0.0006 for a two-layered neural network with 100 ReLU nodes each.

MNIST
For this experiment we found that the results are relatively invariant to network architecture passed a certain complexity, in consequence we chose a dense neural network with three hidden layers each with 500 ReLU nodes. The best performance for SGD was obtained for 0.1 learning rate while the learning rates for DGB had to be scaled down with smaller α values. In the case of DGB with normalized gradients (NDGB) increasing the moment value led to a decrease in performance so it was kept at zero.   As shown in Table 6 and Figure 1 deep gradient models converge much faster on the training set however, their performance is diminished on the test sets, although even here they show a faster convergence to a relative steady state when compared to SGD. As expected, the overfitting effect is diminished when a larger α value is used. Surprisingly, NDGB has a very similar performance on the test data set, approaching that of SGD.

Conclusions
In this paper we described a hybrid approach between boosting and backpropagation for training neural networks which we called deep gradient boosting (DGB). We showed how SGD is implicitly regularized as an extreme case of the DGB algorithm. Our experiments showed that in certain cases it outperforms SGD but under-performs when the generalization requirements are more strict, as is the case of image recognition problems.
Learning a linear model fit at each layer lies at the core of deep gradient boosting. This opens the door to criteria for assessing the quality of this fit using standard measures like mean squared error or adjusted R2. This in turn suggests that one could adaptively grow each layer in width based on the goodness-of-fit measure when adding or removing a node.
In this work, we have not explored the full range of possibilities that Deep Gradient Boosting potentially enables. Convolutional neural networks, recurrent neural networks and attention networks are some of the more challenging network architectures for which we plant to adapt DGB. This is especially hard considering that these network architectures are usually reserved for very hard problems with large dimensional space like speech and natural language processing. In addition, further theoretical analysis of the differences between gradient descent in the functional space versus the parameter space might allow us to better understand the generalization properties of backpropagation.