62

For a quick simple explanation: In both gradient descent (GD) and stochastic gradient descent (SGD), you update a set of parameters in an iterative manner to minimize an error function. While in GD, you have to run through ALL the samples in your training set to do a single update for a parameter in a particular iteration, in SGD, on the other hand, you use ...


40

Gradient Descent is an algorithm which is designed to find the optimal points, but these optimal points are not necessarily global. And yes if it happens that it diverges from a local location it may converge to another optimal point but its probability is not too much. The reason is that the step size might be too large that prompts it recede one optimal ...


28

No. Gradient descent is used in optimization algorithms that use the gradient as the basis of its step movement. Adam, Adagrad, and RMSProp all use some form of gradient descent, however they do not make up every optimizer. Evolutionary algorithms such as Particle Swarm Optimization and Genetic Algorithms are inspired by natural phenomena do not use ...


24

The biggest advantage of ReLu is indeed non-saturation of its gradient, which greatly accelerates the convergence of stochastic gradient descent compared to the sigmoid / tanh functions (paper by Krizhevsky et al). But it's not the only advantage. Here is a discussion of sparsity effects of ReLu activations and induced regularization. Another nice property ...


23

The comments about iteration number are spot on. The default SGDClassifier n_iter is 5 meaning you do 5 * num_rows steps in weight space. The sklearn rule of thumb is ~ 1 million steps for typical data. For your example, just set it to 1000 and it might reach tolerance first. Your accuracy is lower with SGDClassifier because it's hitting iteration limit ...


16

Asides from the points you mentioned (convergence to non-global minimums, and large step sizes possibly leading to non-convergent algorithms), "inflection ranges" might be a problem too. Consider the following "recliner chair" type of function. Obviously, this can be constructed so that there is a range in the middle where the gradient is the 0 vector. In ...


12

One reason that ReL Units have been introduced is to circumvent the problem of vanishing gradients of sigmoidal units at -1 and 1. Another advantage of ReL Units is that they saturate at exactly 0 allowing for sparse representations, which can be helpful when hidden units are used as input for a classifier. The zero gradient can be problematic in cases ...


11

There is no technique that will eliminate the risk of overfitting entirely. The methods you've listed are all just different ways of fitting a linear model. A linear model will have a global minimum, and that minimum shouldn't change regardless of the flavor of gradient descent that you're using (unless you're using regularization), so all of the methods you'...


11

Welcome to SE:Data Science. SGD is a optimization method, while Logistic Regression (LR) is a machine learning algorithm/model. You can think of that a machine learning model defines a loss function, and the optimization method minimizes/maximizes it. Some machine learning libraries could make users confused about the two concepts. For instance, in scikit-...


10

First of all, word "sample" is normally used to describe subset of population, so I will refer to the same thing as "example". Your SGD implementation is slow because of this line: for each training example i: Here you explicitly use exactly one example for each update of model parameters. By definition, vectorization is a technique for converting ...


10

There are several issues I see with the implementation. Some are just unnecessarily complicated ways of doing it, but some are genuine errors. Primary takeaways A: Try to start from the math behind the model. The logistic regression is a relatively simple one. Find the two equations you need and stick to them, replicate them letter by letter. B: ...


10

The two slightly-smaller models will perform exactly the same, on average. There is no difference baked in to the different trees: "the last tree will be the best trained" is not true. The only difference among the trees is the random subsample they work with and random effects while building the tree (feature subsetting, e.g.). Gradient boosted ...


9

You might find Chapter 8 of Deep Learning helpful. In it, the authors discuss training of neural network models. It's very intricate, so I'm not surprised you're having difficulties. One possibility (besides user error) is that your problem is highly ill-conditioned. Gradient descent methods use only the first derivative (gradient) information when ...


9

Hmmm, I am little perplexed by your question. In gradient boosting, we do use the residuals. The residuals are the gradients. You can check my simple implementation of gradient boosting. This is where the magic happens: def fit(self, X, y): self.fs = [self.first_estimator] # step 0 f = self.first_estimator.fit(X, y) # step 1 for m in ...


8

Feature engineering that I would consider essential for even tree based algorithms are: Modular arithmetic calculations: e.g. converting a timestamp into day of the week, or time of day. If your model needs to know that something happens on the third Monday of every month, it will be nearly impossible to determine this from timestamps. On a similar vein, ...


8

Each training sample ends up in a distant, completely separate location on the error-surface That is not a correct visualisation of what is going on. The error surface plot is tied to the value of the network parameters, not to the values of the data inputs. During back-propagation of an individual item in a mini-batch or full batch, each example gives an ...


8

The inclusion of the word stochastic simply means the random samples from the training data are chosen in each run to update parameter during optimisation, within the framework of gradient descent. Doing so not only computed errors and updates weights in faster iterations (because we only process a small selection of samples in one go), it also often helps ...


8

According to the title: No. Only specific types of optimizers are based on Gradient Descent. A straightforward counterexample is when optimization is over a discrete space where gradient is undefined. According to the body: Yes. Adam, Adagrad, RMSProp and other similar optimizers (Nesterov, Nadam, etc.) are all trying to propose an adaptive step size (...


8

Momentum in neural networks is a variant of the stochastic gradient descent. It replaces the gradient with a momentum which is an aggregate of gradients as very well explained here. It is also the common name given to the momentum factor, as in your case. Maths The momentum factor is a coefficient that is applied to an extra term in the weights update: Note:...


7

Let us say that the output of one neural network given it's parameters is $$f(x;w)$$ Let us define the loss function as the squared L2 loss (in this case). $$L(X,y;w) = \frac{1}{2n}\sum_{i=0}^{n}[f(X_i;w)-y_i]^2$$ In this case the batchsize will be denoted as $n$. Essentially what this means is that we iterate over a finite subset of samples with the size of ...


7

Why is stochastic gradient descent so much worse then batch GD for MNIST task? It isn't inherently worse. Instead, by changing just one parameter on its own you have adjusted the example outside of where it has been "tuned" to work, because it is a simplified example for learning purposes, and it is missing some features that most users of NNs would ...


7

Generally, in tree-based models the scale of the features does not matter. This is because at each tree level, the score of a possible split will be equal whether the respective feature has been scaled or not. You can think of it like here: We're dealing with a binary classification problem and the feature we're splitting takes values from 0 to 1000. If you ...


7

What's the point? First, it is good to understand what we are doing that leads us to need these tools. When we are trying to apply machine learning we want to infer some meaning from data. This means that given an instance we want to put it through our model and then we can have some output that tell us something about this data. Let's look at the example ...


7

In Gradient Descent or Batch Gradient Descent, we use the whole training data per epoch whereas, in Stochastic Gradient Descent, we use only single training example per epoch and Mini-batch Gradient Descent lies in between of these two extremes, in which we can use a mini-batch(small portion) of training data per epoch, thumb rule for selecting the size of ...


7

First, remember that the derivative of a function gives the direction in which the function increases, and its negative, the direction in which the function decreases. Training a model is just minimising the loss function, and to minimise you want to move in the negative direction of the derivative. Back-propagation is the process of calculating the ...


7

In 'Efficient Backprop' by Lecun and others (http://yann.lecun.com/exdb/publis/pdf/lecun-98b.pdf), they explain why correlated variables are bad (§ 4.3 normalizing the inputs). Duplicated data is a special case of linear dependence, which is a special case of correlation. Say you have duplicated variables $X1 = X2$, so the network output is constant over ...


6

In dropout as described in here, weights are not masked. Instead, the neuron activations are masked, per example as it is presented for training (i.e. the mask is randomised for each run forward and gradient backprop, not ever repeated). The activations are masked during forward pass, and gradient calculations use the same mask during back-propagation of ...


6

With regard to resources: In my opinion, ADADELTA: An Adaptive Learning Rate Method (the original ADADELTA paper) explains (in sections 1-3) both ADAGRAD and ADADELTA in a quite accessible manner. I found Adaptive Subgradient Methods for Online Learning and Stochastic Optimization to be less accessible, but it is the original ADAGRAD paper, so it is ...


6

This blogpost gives a broad answer to your question. In short, Newton's method is not used to find a root of the loss, but a root of the gradient. If you find a root of the gradient, then you are either in a maximum, a minimum, or a saddle point (the three of them are critical points). When using the cross-entropy loss function in logistic regression, it can ...


6

Using only sign of gradient is a way to go, but might result in slow convergence. Nevertheless it is a valid variation of the method. The Geometry of Sign Gradient Descent Sign-based optimization methods have become popular in machine learning due to their favorable communication cost in distributed optimization and their surprisingly good performance in ...


Only top voted, non community-wiki answers of a minimum length are eligible