<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by David Stéphane on Medium]]></title>
        <description><![CDATA[Stories by David Stéphane on Medium]]></description>
        <link>https://medium.com/@steph1793?source=rss-840493a14b7------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/2*VxwncoH9hR_kF8IynpsTAg.png</url>
            <title>Stories by David Stéphane on Medium</title>
            <link>https://medium.com/@steph1793?source=rss-840493a14b7------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 16:56:30 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@steph1793/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[HSIC bottleneck: An alternative to Back-Propagation]]></title>
            <link>https://medium.com/data-science/hsic-bottleneck-an-alternative-to-back-propagation-36e951d4582c?source=rss-840493a14b7------2</link>
            <guid isPermaLink="false">https://medium.com/p/36e951d4582c</guid>
            <category><![CDATA[deep-learning]]></category>
            <category><![CDATA[optimization]]></category>
            <category><![CDATA[information-theory]]></category>
            <category><![CDATA[backpropagation]]></category>
            <dc:creator><![CDATA[David Stéphane]]></dc:creator>
            <pubDate>Tue, 12 May 2020 23:19:26 GMT</pubDate>
            <atom:updated>2020-05-13T13:47:52.549Z</atom:updated>
            <content:encoded><![CDATA[<h4>How the Information Theory brings us other techniques for Deep Learning model training</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*BYz0tG27ZDjNCdq9" /><figcaption>Photo by <a href="https://unsplash.com/@herfrenchness?utm_source=medium&amp;utm_medium=referral">Clarisse Croset</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>Deep learning models learn using gradient descent based methods. This is achieved thanks to a particular algorithm , back-propagation, that allows us to retro-propagate the training error through the entire model parameters, by computing the partial derivatives, for the parameters update.<br>This algorithm is very costly since it requires a backward operation through the entire model to compute the partial derivatives, after a forward pass.</p><p>But what if we could avoid that? What if there was no need for us to compute a global loss at the very end of the model and then retro-propagate this error through the entire model? What if we could estimate directly during the forward pass the “training objective” of each hidden layer of our models and then compute directly the gradients of the parameters involved with no need of back-propagation?</p><p>Well, I came across a very interesting paper [1] that investigates this: <em>The HSIC Bottleneck: Deep Learning without Back-Propagation</em> by<em> </em><strong>Wan-Duo Kurt Ma, J.P. Lewis, W. Bastiaan Kleijn</strong>. They use Information Theory in order to achieve such a task.</p><h3>Backpropagation</h3><p>Back-propagation is an algorithm based on chain rule, that enables the computation of the partial derivatives of a loss function with respect to all the parameters in a feed-forward neural network. In this algorithm, the partial derivatives are computed in a backward pass from the last layer to the first one, thus the name back-propagation, with no possibility of parallelization.</p><p>I will not be extending any further on back-propagation. Interested in an in-depth analysis of this algorithm, have a look at this amazing blog [<a href="http://neuralnetworksanddeeplearning.com/chap2.html">2</a>] by <a href="http://michaelnielsen.org/">Michael Nielsen</a>.</p><h3>Information Theory</h3><p>Before attacking the core of this article, let us first introduce some quick notions in Information Theory.</p><p>Information theory gives us tools to measure some quantities of information one can hold about the distribution of a given random variable. For example with Information Theory, we can compute the entropy or the uncertainty of a random variable X.</p><h4>Entropy</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/487/1*OpBoSl_FYPW-5YpiIUvC-A.png" /><figcaption>Entropy measure for a discrete random variable</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/336/1*27KbI0-SM51yf9bLey9ypw.png" /><figcaption>Continuous variable entropy</figcaption></figure><p>Let us consider a set of events A, B, C, D, E, F and a probability distribution over these events, regarding their occurrence likelihood. Let A be a very likely event to occur (with a probability near 1), while B, C, D, E, F are very unlikely.</p><p>It clearly appears that the entropy of our variable here (which can take values A, B, C, D, E or F) is near 0, regarding the entropy formula.</p><p>If we consider a second scenario with the same variable and the same set of events, but this time a uniform probability distribution over our set of events, we end up with an entropy of <strong>0.77</strong>.</p><p>Is this surprising? Not really. In the first scenario, we are very certain about which event is likely to occur resulting in a low measure of uncertainty (entropy). On the other hand, the uniform distribution over our set of events in the second scenario increases the uncertainty about the information we hold, we are not sure anymore about which event will occur.</p><h4>Mutual Information (MI)</h4><p>Another interesting tool from Information Theory is the mutual information (MI). MI measures the dependence between two random variables.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/396/1*JUw_pKPB4YOKwE-49_0gwA.png" /><figcaption>MI as a Kullback Leibler divergence measure between the real joint probability of X and Y, and the joint distribution if they were independent.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/439/1*VQpSi3tXBId-joLGVBtyFg.png" /><figcaption>Discrete case</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/453/1*xwI7b1GCm0sHU674pWMq0A.png" /><figcaption>Continuous case</figcaption></figure><p>As we can see, MI measures the <a href="https://www.countbayesie.com/blog/2017/5/9/kullback-leibler-divergence-explained">Kullback Leibler divergence</a> [2] between the joint probability of two random variables and the product of the probability of both variables, as if they were independent. With two independent variables, we have p(X,Y) = p(X).p(Y), resulting in a null KL divergence and then a null MI. The opposite is observed when the two variables are strongly dependent : exploding KL divergence .</p><p>Well, that was interesting! But what does it have to do with our topic today? Keep holding on, we are coming to it ;) .</p><h3>Deep Learning without Back-Propagation</h3><p>Let’s take a moment first to think about what our deep learning models actually do. Roughly speaking, when building and training a neural network for a given task like classification, we are just learning a model that can take a complicated input , transform it successively into something much simpler (the hidden layers or internal representations), still highly “correlated” with a target variable. The complicated input is whether a text, an image, or a sound signal etc — yet readable by humans, but complicated for our computers.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*mjyKMPkj40K86GmlhiI11w.jpeg" /><figcaption><a href="https://www.mdpi.com/2624-6511/2/2/9">Source</a></figcaption></figure><p>Those internal representations capture only a part of the signal of the input X. An intuitive way to understand this is to think of convolution neural nets. After a convolutional and a max pooling layers, we get a smaller figure which could not be readable, but has kept the tiny sufficient signal it needed from the source image to still be “associated” with the target corresponding value.</p><p>With that in mind, we know that our neural nets learn to produce hidden representations (throughout all the layers) that are less “correlated” with the input by keeping only the relevant information, and as much correlated with the target output as possible. We want to train our neural nets to learn doing this without back propagation, therefore estimate an objective function to optimize for each hidden layer.</p><p>I am absolutly sure that, at this point, you have a little hint :).<br>I can almost hear you saying :</p><blockquote>“Stéphane, we just need to quantify and minimize the dependence between hidden representations produced by the neural network and the corresponding input but also quantify and maximize the dependence between the same hidden representations and the output variable. And we can quantify those informations with the Mutual Information measure.”</blockquote><p>You are absolutely right, regarding what the authors of the paper proposed anyway : ). Bravo!</p><p>This method is not new at all. In fact it comes from the Information Theory : the Information Bottleneck principle.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/364/1*9OtJxBavGdjlYG_G8QCfQg.png" /><figcaption>I is actually the Mutual Information, and beta a hyper-parameter.</figcaption></figure><p>The authors found the objective function they needed for each hidden layer of the neural network.</p><h4>Information Bottleneck (IB)</h4><p>IB is a method introduced by <a href="https://en.wikipedia.org/wiki/Naftali_Tishby">Naftali Tishby</a>, Fernando C. Pereira, and <a href="https://en.wikipedia.org/wiki/William_Bialek">William Bialek</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/850/1*RsBOFFKgGxNazTqQvmizpQ.png" /><figcaption><a href="https://www.researchgate.net/publication/265497360_Computational_Intelligence_Techniques_for_Missing_Data_Imputation">Source</a></figcaption></figure><p>Optimizing IB is equivalent to minimizing the mutual information (dependence) between X and the new variable T while maximizing the MI between T and the target variable Y.</p><p>In other words, IB allows us to learn to produce a new variable T which is the least dependent on the source input X (compression) and dependent as much as possible on the target Y.</p><p>Here T can be any of the hidden representations of X, in the neural network.</p><h4>What in practice?</h4><p>The authors introduced an objective function that can be used for each hidden layer. But there is still a remaining problem.</p><p>Let us suppose that you use continuous differentiable activation functions like the sigmoid or the leaky-relu. Also, let’s assume that your input X is a continuous variable (it is generally the case- eg. : your 32x32 image at the entry of your model takes continuous values lying in [0,1]³²*³²).</p><p>The first assumption leaves us with a deterministic neural network. Consequently, with the second assumption, the hidden representations are just continuous variables absolutely dependent on X. More precisely, <em>Tᵢ=fᵢ(X), </em>where fᵢ is a deterministic function and Tᵢ, the i-th hidden representation of X. We then en up with MI(X, Tᵢ) = ∞ almost always, no matter the initial weights of the neural net.</p><p><strong>How can we optimize a function that is infinite almost always? </strong><br>The problem is ill-posed, MI is not a convenient measure for the actual purpose.</p><p>The authors proposed then to replace MI with another dependence measure tool: HSIC for Hilbert Schmidt Independence Criterion.</p><h3>HSIC bottleneck</h3><p>HSIC is just the norm of the cross-covariance matrix between two sets of variables.</p><p>In our case, let’s consider a batch of input data X = (X₁, X₂, …, Xₘ). Every Xᵢ is a random variable since it could be any input sample from the dataset. Also, let’s consider the kᵗʰ hidden layer obtained from X with our neural net, Zᵏ = (Zᵏ₁, Zᵏ₂, …, Zᵏm). The cross covariance will just measure the covariance between each variable from X and each variable from Zᵏ.</p><p>HSIC can be re-written as the trace of a matrix.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/538/1*TxgcJr747ydQ1DrwfUL3og.png" /></figure><p>Let’s break this formula down. K_x or K_z are similarity matrices where each row is the distance vector from an individual to the other individuals of the same variable. Those distances can be computed using a Gaussian kernel parameterized by a length scale σ.<br>When computing K_x.H or K_z.H, we just center the distance vectors of each individual in each variable by subtracting the mean distance of each individual to the others. For example, K_X₁ (distance vector from individual 1 to all the others) is substracted from its mean.<br>We finally get a sort of encoding vector representing each element in the two variables. This vector encodes the relation of each individual to the others in the same variable. Computing the above trace is equivalent to summing the inner product between the encodings of the individuals from X and the corresponding individuals from Y.</p><blockquote>This inner product will be large when the relation between each point i of X and all other points of X is similar to the relation between the corresponding point i of Y and all other points of Y , summed over all i, and where similarity is measured through the Gaussian kernel.</blockquote><p>With HSIC we can empirically estimate some dependency between two variables. Despite MI, HSIC won’t explode or be likely to exhibit infinite values. Thus, it can be used as a replacement in our objective function.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/439/1*_MHjaZqYJuCQ8ejJ724YhQ.png" /><figcaption>HSIC Bottleneck</figcaption></figure><h3>Proposed Algorithm</h3><p>In this section, I am going to introduce the overall method, and how it all comes together.</p><p>The initial goal is to find an alternative to back-propagation. For that, the authors proposed a robust objective method for each hidden layer of the neural network : HSIC Bottleneck.</p><p>The hidden representations Z are parameterized by our neural net weights. Then, when the authors say that we are seeking for the hidden representations (Z) that are less dependent on X and as much dependent on Y as possible, they meant looking for the parameters weights that produce Z given the input X. And since we have an objective function for each hidden layer, we can compute directly the gradients of the weights involved in each layer, with no need of back-propagation.</p><p>Here is the algorithm:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/592/1*vJHX0_YjL0jYFI2zs6JG9g.png" /><figcaption><a href="https://arxiv.org/pdf/1908.01580.pdf">Source</a></figcaption></figure><p>We iterate over the training dataset by sampling m input examples along with their targets. Be aware, Tᵢ-1 represents here the weights at layer i-1 of our model; in the previous paragraphs we referred to T as a hidden variable, the output of a hidden layer; it is not the same here. Also, (Xⱼ, Yⱼ) in the algorithm above refers to the j-th batch data.</p><p>The following lines describe the forward pass in our model:</p><ul><li>We compute the output of a given layer by applying Tᵢ₋₁ to the previous batch hidden representations.</li><li>We compute our objective function and the gradients with respect to the weights of the current layer.</li><li>We directly update the weights of the current layer with an update rule like SGD.</li></ul><p>As we can see, with just a forward pass we have been able to compute an objective function to minimize and directly update the weights with no need of a backward pass.</p><p>In the case of a classification, the last hidden representation dimension will equal the number of classes. The maximum value at a given position will serve to predict the corresponding class. This is the unformatted model.<br>In the formatted model, the authors appended a fully connected and a softmax activation output at the end of the neural network and train this single layer with SGD and no back-propagation. They use a cross-entropy loss to train this layer.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/649/1*snE3VptaO75JYyPzXwlZfg.png" /><figcaption>Formatted model. <a href="https://arxiv.org/pdf/1908.01580.pdf">Source</a></figcaption></figure><p>As we’ve seen before HSIC bottleneck will depend on a hyper-parameter σ. The authors found that the results are really impacted by the choice of this hyper-parameter. To overcome this, concurrent neural nets are learned using HSIC bottleneck with different length scales σ. The final hidden representations of each network are then aggregated (averaging or summation). They further train a single fully connected layer with a softmax output using SGD and a cross entropy loss.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/735/1*Qg8DKg9AEoIpTWeEz_XZ5Q.png" /><figcaption>Multiple scale network. <a href="https://arxiv.org/pdf/1908.01580.pdf">Source</a></figcaption></figure><p>That’s it! Here is your deep learning framework with no backpropagation for training.</p><h3>Experiments</h3><p>The authors run a lot of experiments to support the framework they introduced.</p><p>First, they empirically prove that neural networks actually follow the Information Bottleneck principle: neural networks learn to produce hidden representations that are less dependent on the input X by keeping the relevant information and very dependent on the target Y. For that matter, they compute the HSIC between the hidden layers learned and X, and the HSIC between the hidden layers and Y, for a numerous number of neural networks.<br>Here is an example for fully connected neural networks, trained on MNIST dataset.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/557/1*C3UoT1i7FCQHcMDOfhW20w.png" /><figcaption>HSIC between the last hidden layer, the input X and the target Y for deep networks with different depths (number of layers). <a href="https://arxiv.org/pdf/1908.01580.pdf">Source</a></figcaption></figure><p>As we can see, the further we train our neural network, the more it tends to follow the Information Bottleneck Principle.</p><p>They also experimented unformatted fully connected models, where the last layers are trained with HSIC bottleneck. They experimented such models on CIFAR dataset.</p><p>They finally tested the formatted models with an additional fully connected layer trained using SGD and a cross entropy loss. They found out that those models were converging faster than models trained using back-propagation.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/558/1*Oszvq3MqH29fTkFbM-311Q.png" /><figcaption>HSIC formatted models vs models trained with back-propagation. <a href="https://arxiv.org/pdf/1908.01580.pdf">Source</a></figcaption></figure><h3>Conclusion</h3><p>Is there any deep learning model that is trained nowadays without back-propagation? If it exists, it must be rare. Back-propagation is practically an unavoidable algorithm to compute partial derivatives in a deep neural network. However, this algorithm is costly, often suffers from gradient vanishing, offers no possibility of parallelization. It is in this context that the authors of the paper we studied, propose HSIC-Bottleneck, an alternative to back-propagation. This algorithm relies on the Information Bottleneck principle from the Information Theory. Using this method, the authors were able to propose a robust objective function for each hidden layer of our deep network, consequently the ability to compute the gradients with respect to all the parameters during the forward pass, with no need of propagating the error in a backward pass, with chain rule.</p><p>I found the solution absolutely elegant, and can’t wait for the subsequent works in this direction.</p><h3>References</h3><p>[1] Wan-Duo Kurt Ma, J.P. Lewis, W. Bastiaan Kleijn, <a href="https://arxiv.org/abs/1908.01580v3">The HSIC Bottleneck: Deep Learning without Back-Propagation</a> (2019), arxiv 2019</p><p>[2] Michael Nielsen, <a href="http://neuralnetworksanddeeplearning.com/chap2.html">How the backpropagation algorithm works</a> (Dec 2019)</p><p>[3] Arthur Gretton , Kenji Fukumizu, Choon Hui Teo , Le Song, Bernhard Scholkopf, Alexander J. Smola, <a href="https://papers.nips.cc/paper/3201-a-kernel-statistical-test-of-independence.pdf">A Kernel Statistical Test of Independence</a> 2008, NeurIPS 2008</p><p>[4] Alexander A. Alemi, Ian Fischer, Joshua V. Dillon, Kevin Murphy <a href="https://arxiv.org/abs/1612.00410">Deep variational information bottleneck</a> 2017, ICLR 2017</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=36e951d4582c" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/hsic-bottleneck-an-alternative-to-back-propagation-36e951d4582c">HSIC bottleneck: An alternative to Back-Propagation</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[ENTROPY-SGD: BIASING GRADIENT DESCENT INTO WIDE VALLEYS]]></title>
            <link>https://medium.com/analytics-vidhya/entropy-sgd-biasing-gradient-descent-into-wide-valleys-af3c9df03ac6?source=rss-840493a14b7------2</link>
            <guid isPermaLink="false">https://medium.com/p/af3c9df03ac6</guid>
            <category><![CDATA[deep-learning]]></category>
            <category><![CDATA[optimization]]></category>
            <dc:creator><![CDATA[David Stéphane]]></dc:creator>
            <pubDate>Thu, 23 Apr 2020 02:25:35 GMT</pubDate>
            <atom:updated>2020-05-01T17:48:28.070Z</atom:updated>
            <content:encoded><![CDATA[<p>How is your deep learning model able to learn and even generalize? Theorizing the behavior of our deep learning models, bounding their generalization error with reasonable assumptions has always been challenging.</p><blockquote>In that sense, a lot of work has been done to try to understand the generalization in deep learning like [1a], [1b], or more recently [1c] that I may cover on one of my next posts.</blockquote><p>In this article, I will be talking about a paper [2], that I found really interesting : “ENTROPY-SGD: BIASING GRADIENT DESCENT INTO WIDE VALLEYS” wrote by <a href="https://arxiv.org/search/cs?searchtype=author&amp;query=Chaudhari%2C+P">Pratik Chaudhari</a>, <a href="https://arxiv.org/search/cs?searchtype=author&amp;query=Choromanska%2C+A">Anna Choromanska</a>, <a href="https://arxiv.org/search/cs?searchtype=author&amp;query=Soatto%2C+S">Stefano Soatto</a>, <a href="https://arxiv.org/search/cs?searchtype=author&amp;query=LeCun%2C+Y">Yann LeCun</a>, <a href="https://arxiv.org/search/cs?searchtype=author&amp;query=Baldassi%2C+C">Carlo Baldassi</a>, <a href="https://arxiv.org/search/cs?searchtype=author&amp;query=Borgs%2C+C">Christian Borgs</a>, <a href="https://arxiv.org/search/cs?searchtype=author&amp;query=Chayes%2C+J">Jennifer Chayes</a>, <a href="https://arxiv.org/search/cs?searchtype=author&amp;query=Sagun%2C+L">Levent Sagun</a>, <a href="https://arxiv.org/search/cs?searchtype=author&amp;query=Zecchina%2C+R">Riccardo Zecchina</a>, in 2016. The authors led some experiments that prove, empirically anyway, that optimal solutions in deep learning that generalize well have a specific local geometry : wide valleys. From this assumption, they tried to build a new optimizer that will actively look for the best solution that minimizes the training error, but also lies in a wide valley (flat minima), and then will be more likely to generalize better.</p><h3>Flat vs Sharp minimas</h3><p>When training a deep learning model, we are seeking for a solution <em>x </em>that minimizes a loss function on a given training set. This solution lies in a very high dimensional space (thousands, millions or even billions of parameters to learn) called parameter space. When we analyze the local geometry of this solution, it either lies on a wide valley or a sharp one. For those new to those terms, you can think of a second order polynomial <em>a.x². </em>When <em>a</em> gets closer to 0, the graph flattens and <em>x=0</em> lies in a wide valley. The figure below illustrates this. This is what the local geometry of some deep learning models solutions look like but in very high dimensional space.</p><p>In [1] the authors noticed that on a variety of neural networks architectures, the solution found by the optimizer tends to be flat minimas. It is like the optimizers implicitly understands that those solutions tends to generalize better than sharp minimas and converges towards those points.</p><p>For example, when analyzing a convolutional neural network trained on MNIST dataset, the optimal solution hessian has about 94% of its eigenvalues that are near 0. This just means that most of the directions of the hessian are near the null vector, which means that the local geometry of our solution is wide in almost every direction.</p><p>Those observations comforts the idea that the wider the solution’s local geometry the better the generalization. But watch out, this is not a sufficient condition. It is not even a condition, but an assumption. Today, we are just studying one of the assumptions that try to explain the generalization in deep learning.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/336/1*btpeA8Lq6l7V9Y4yO254DQ.png" /><figcaption>Eigenvalues histogram of an Hessian at local minium</figcaption></figure><p>Despite all those empirical results, this assumption may not still be really intuitive. Let us look at the problem from a different perspective.</p><p>When evaluating a deep learning model, the input features may not always be perfectly identical to those of the training set : there is generally a shift between both distributions. This is perfectly understandable since the training set is just a sample from the real set. What that reveals is that the loss function evaluated on a training set, may not really cover the one on the validation set, in a way that we can observe a shift of the loss function in the parameter space : the optimal solution found on the training set may be a shift of the real optimal solution, the one that generalizes the best.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/793/1*1KYzFdGbaXz0KT6cfrTtgg.png" /><figcaption>Left : Sharp minima vs Right : Flat minima</figcaption></figure><p>That being said, what do we observe when our solution lies on a sharp valley : the generalization gap explodes as we can clearly see in the figure above. In a Bayesian learning setting, sharp minimas have posteriors that are highly concentrated around them, meaning that we have solutions that are very specialized on the training set and may not be robust to data perturbations (over-fitting).</p><p>With the previous empirical results, we have seen that the optimizers like SGD, Adam, etc implicitly and passively converge towards wide valleys solutions. But there is no guarantee that this will always be the case. This has motivated the creation of an algorithm that will actively look for flat minimas : Entropy SGD.</p><h3>Entropy Stochastic Gradient Descent</h3><p>In this section, we are going to build step by step an algorithm that allows us to train a deep learning model converging towards wide valleys local minimas.</p><p>Given a training set, our goal is to optimize an objective function (loss function)<em> f(x)</em> where<em> x</em> is the model parameters.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/395/1*wV7JdzqauTk9RXZhaKavVw.png" /></figure><p>A very common algorithm that can be used for this task is SGD (Stochastic Gradient Descent) where we iteratively update <em>x</em> with the following rule until “convergence”:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/426/1*sJ8x8aXJ69U27YBWBSfmCw.png" /></figure><p>But remember this will only optimize the loss function on our training set without any ACTIVE research for a wide valley solution. We are then going to build a different loss function for that matter.</p><h4>Negative Local Entropy</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/438/1*SMk5shO0Vq_o81wIIwN1dw.png" /></figure><p>In a Bayesian learning setting, solving the optimization problem described above is equivalent to sampling parameters from the Gibbs distribution below cons.</p><p>In fact, when β → ∞, this probability distribution concentrates around the optimal solution <em>x</em>, the one that minimizes<em> f</em>, thus the link with our problem.</p><p>We can then think of modifying this probability distribution so that it does not concentrate around any optimal solution like before but around wide valleys solutions that are more robust. We introduce a new variable <em>x’</em>, and for the rest of the article, let <em>β = 1</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/648/1*yGBBPRMpfNjdX9eJVGqEXA.png" /></figure><p>Well, a lot of things have changed. Our Gibbs distribution is set on our new variable<em> x’ </em>(x remains the parameter we want to optimize), there is a new term in the exponential that computes the distance of our new variable to our actual parameters <em>x</em>. The normalizing constant (with respect to x’) will be denoted <em>Z(x)</em> : it is a function called partition function(with respect to β) that has a dependency on x. Why would we do all of this?</p><p>We want to converge towards wide valley solutions, which means that we are not only interested just in the optimal solution, but in its neighborhood too. When <em>x’=x</em>, we find our initial Gibbs distribution.</p><p>Roughly speaking <em>P(x’)</em> is a conditional probability, conditioned on the current parameters weights x we are optimising, over the neighborhood of <em>x</em> : in fact when<em> x’</em> goes further from <em>x</em> the <em>P(x’)</em> tends to 0. This probability exhibits interesting properties. Consider two different points <em>x1</em> and <em>x2</em>. Let <em>x1</em> be a sharp minima and <em>x2</em> a flat minima.</p><p>In this setting, we are more likely to observe that the probability <em>P(x’)</em> conditioned on <em>x1</em> or <em>x2</em> will be a very narrow distribution concentrated around <em>x1</em> and a wide distribution around<em> x2</em>.</p><p>In fact, when we consider the neighborhood of a sharp minima <em>x1</em>, just a tiny little move from <em>x1</em> makes <em>f(x’)</em> explode meaning that <em>-f(x’)</em> is very quickly overshadowed by <em>γ||x1-x’||²</em>, for most of the points <em>x’</em> in the neighborhood; making the probability of the neighbors low, even the closer ones. But , -<em>f(x’)</em> remains high even if we go much more further from <em>x2</em>, for most of the points in the neighborhood and then takes a little longer before shrinking, if <em>x2</em> lies in a wide valley; the probability of the further neighbors remains high.</p><p>Note that the parameter γ, allows us to play with how wide we want our valley to be : lower γ implies wider valleys. Despite the original Gibbs distribution which only focuses on the global minima (whatsoever ), we also take into account the neighborhood now and its wideness.</p><p>If we look closer at our partition function (normalizing constant parameterized on <em>x</em>),</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/634/1*lVLYwaUWsi608-LUbckGdA.png" /></figure><p>it appears that this function is maximal for the point <em>x,</em> such that its furthest neighbors possible, “minimizes” the training loss <em>f</em> , (<em>x</em> itself included) : clearly the definition of a flat minima. Bingo !!!</p><p>We can then just think of taking the opposite of this function parameterized on <em>x</em> as a new loss function. But for the easyness of the derivatives computation sake, we will rather use the log trick and consider the negative log of our partition function (negative log-partition function).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/406/1*jOeIUgdPDv6KMYMsih9ESQ.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/397/1*M1a7gh9K5DHFuQ_snu3Vfw.png" /></figure><p>That’s it! We just built our new loss function : ).</p><p>Now we can optimize this new function using an algorithm like SGD, Adam etc, as before. For that matter let us differentiate our new loss.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/661/1*d1j-0SJKXNXPuR9-KvT9Gg.png" /></figure><p>Our gradient ends up on a simple expression OUTWARDLY. But this is not the case at all. We will need to compute the expectation of <em>x’</em> (expectation conditioned on the training dataset).</p><p><em>x’</em> follows a Gibbs distribution over a very high dimensional space which is not tractable and it’s litteraly impossible to compute analytically the expectation of this distribution. To avoid this issue, we will rather sample a certain number of points from this distribution and take the average of the samples. We can use SGLD (a Monte Carlo Sampling method)for that matter. You may need to read [3] for more details about SGLD.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/410/1*gnltmJCyLvmX8YwFC7zENA.png" /></figure><p>μ is the estimation of the expectation. Generally in Monte Carlo sampling methods, the samples we draw tends to be better and follow the actual distribution when we go further in the sampling process steps. The authors used then an exponential averaging instead of just taking the mean, to put more weights on the last samples. It is also an optimization method, then converging towards better points than the initial ones, thus the use of an exponential averaging.</p><p>Finally, if we re-consider our SGD algorithm, with the SGLD sampling step, and the computed gradients, here is the final algorithm we get.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/659/1*tazk8-TofEzMNZnXAW0ggQ.png" /></figure><p>We just built our Entropy SGD algorithm. A very important thing to notice is that we can base our Entropy SGD algorithm on other algorithms like Adam, Nesterov Momentum etc.</p><h4>Experiments</h4><p>The new optimizer (Entropy SGD) has been tested on a wide range of neural networks, with different sizes etc in [2]; it has been tested on fully connected based nets trained on MNIST, convolutional nets also trained on MNIST, reccurent neural nets trained on PenTree Bank for word level prediction, and for character level prediction. Here are the results.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/637/1*fKgkUuJE_TzwYV7x5hxgQw.png" /></figure><h4>Conclusion</h4><p>Entropy SGD yields similar results as SGD or Adam in terms of generalization performances. This is not surprising since Entropy SGD just does more explicitly and actively what SGD and Adam do in an underlying way : look for wide valleys minimas. However during the experiments the authors noticed a lower training error for Entropy SGD.</p><p>Despite the minor improvements in terms of generalization error, this paper is really interesting in a lot of ways : the experiments led to explore and understand the local geometry of optimal solutions in deep learning, the process by which the authors built this new architecture, the attempt to understand and theorize about generalization in deep learning.</p><p>I really enjoyed it!</p><p>Any interest in this method? Have a look at the keras version of the optimizer I built : <a href="https://pypi.org/project/EntropySGD/">https://pypi.org/project/EntropySGD/</a></p><h4>References</h4><p>[1a]Sepp Hochreiter, Jurgen Schmidhuber,<a href="https://www.bioinf.jku.at/publications/older/3304.pdf"> FLAT MINIMA</a> (1997), Neural Computation 9(1):1{42 (1997)</p><p>[1b] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, Oriol Vinyals, <a href="https://arxiv.org/abs/1611.03530">Understanding deep learning requires rethinking generalization</a> (2016), arxiv</p><p>[1c] Haowei He, Gao Huang, Yang Yuan, A<a href="https://papers.nips.cc/paper/8524-asymmetric-valleys-beyond-sharp-and-flat-local-minima.pdf">symmetric Valleys: Beyond Sharp and Flat Local Minima</a> (2019), NeurIPS 2019</p><p>[2] Pratik Chaudhari, Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Christian Borgs, Jennifer Chayes, Levent Sagun, Riccardo Zecchina, <a href="https://arxiv.org/abs/1611.01838">Entropy-SGD: Biasing Gradient Descent Into Wide Valleys</a> (2016), arxiv</p><p>[3] Max Welling, Yee Whye Teh, <a href="https://www.ics.uci.edu/~welling/publications/papers/stoclangevin_v6.pdf">Bayesian Learning via Stochastic Gradient Langevin Dynamics</a> (2011) , ICML’11: Proceedings of the 28th International Conference on International Conference on Machine Learning (June 2011) Pages 681–688</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=af3c9df03ac6" width="1" height="1" alt=""><hr><p><a href="https://medium.com/analytics-vidhya/entropy-sgd-biasing-gradient-descent-into-wide-valleys-af3c9df03ac6">ENTROPY-SGD: BIASING GRADIENT DESCENT INTO WIDE VALLEYS</a> was originally published in <a href="https://medium.com/analytics-vidhya">Analytics Vidhya</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>