<?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 Eyyüb Sari on Medium]]></title>
        <description><![CDATA[Stories by Eyyüb Sari on Medium]]></description>
        <link>https://medium.com/@eyyubsari?source=rss-7612afea778b------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*bwUO6VTSmPoPIXigpA7nMw.jpeg</url>
            <title>Stories by Eyyüb Sari on Medium</title>
            <link>https://medium.com/@eyyubsari?source=rss-7612afea778b------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 15:33:50 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@eyyubsari/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[Meme search using pretrained word2vec]]></title>
            <link>https://medium.com/data-science/meme-search-using-pretrained-word2vec-9f8df0a1ade3?source=rss-7612afea778b------2</link>
            <guid isPermaLink="false">https://medium.com/p/9f8df0a1ade3</guid>
            <category><![CDATA[python]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[towards-data-science]]></category>
            <category><![CDATA[nlp]]></category>
            <category><![CDATA[memes]]></category>
            <dc:creator><![CDATA[Eyyüb Sari]]></dc:creator>
            <pubDate>Mon, 28 Aug 2017 22:03:32 GMT</pubDate>
            <atom:updated>2017-08-31T15:37:42.591Z</atom:updated>
            <content:encoded><![CDATA[<h4>Shab Dev Story #02</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/592/1*fYBD2iaaOzeXCX2G8mhNeg.png" /></figure><p>Memes are worth thousands of words. They are a cultural thing. My friends and I use to send a lot of those on Messenger using Giphy. The thing is that we have our own memes, and we are too lazy to upload them somewhere. In the meantime, when you start to have a lot of memes in a folder, it becomes quite hard to remember their filename.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/311/1*FOz2QjoIgt2PGI5A3EqDIA.gif" /><figcaption>Little UI for the search system.</figcaption></figure><p>Let’s try to quickly build a little tool to help us know which memes are more likely to correspond to an input sentence. We will have a list of pairs. Each pair is an image URL (instead of a local path, easier to test for you) and a description associated with it.</p><pre>url_descr = [<br>    (&#39;<a href="http://tny.im/a13">https://tny.im/a13</a><a href="https://giphy.com/embed/26uTr7qPYM4OHAwBW&#39;">&#39;</a>, &#39;we don\&#39;t care&#39;),   <br>    (&#39;<a href="http://tny.im/a0-">https://tny.im/a0-</a><a href="https://giphy.com/embed/3o6Zt6D0wctP0kpuwg&#39;">&#39;</a>, &#39;i love you&#39;),<br>    (&#39;<a href="http://tny.im/a12">https://tny.im/a12</a><a href="https://giphy.com/embed/aJlKIh8Kh0NLa&#39;">&#39;</a>, &#39;relax take it easy&#39;),<br>    (&#39;<a href="http://tny.im/a16">https://tny.im/a16</a><a href="https://giphy.com/embed/ohyNdetcfoJ9K&#39;">&#39;</a>, &#39;that is embarrassing&#39;),<br>    (&#39;<a href="http://tny.im/a10">https://tny.im/a10</a><a href="https://giphy.com/embed/lwrxYI7f2tNFS&#39;">&#39;</a>, &#39;screw you guys&#39;)<br>]</pre><p>I will not explain word embeddings in great details here; there already are good articles[1,2] on the subject, no point in reinventing the wheel. However, I will give an high-level overview so everyone can follow.</p><h4>Word embeddings and word2vec</h4><p>Words are discrete symbols, one of the naïve ways for representing them is one-hot vectors. Say we have a vocabulary of size 4, each word is represented by a list of 4 elements containing all zeros but a one at the current word’s index.</p><pre>vocabulary = [&#39;hello&#39;, &#39;sun&#39;, &#39;desert&#39;, &#39;hi&#39;]<br>hello = [1 0 0 0]<br>sun = [0 1 0 0]<br>desert = [0 0 1 0]<br>hi = [0 0 0 1]</pre><p>As you can see this representation is not the best one because if the vocabulary contains thousands of thousands of words, the list is increasing linearly. But the other important thing is that this representation gives us no clues about words’ meaning, or even how words relate to each other. In our vocabulary “hello” and “hi” have the same meaning, but we can’t see this relationship with one-hot vectors. Here comes a word embedding algorithm named <a href="https://en.wikipedia.org/wiki/Word2vec"><em>word2vec</em></a>.</p><p>The idea is to map our one-hot vectors to dense(more condensed) vectors so we can fix the size issue; ideally, we would like words that have a similar/related meaning to have vectors close to each other, as if the vector space has encoded a semantic/contextual representation of the words.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/485/1*NHCMFtAs1wNNd700gDbk4A.png" /><figcaption>Skip-gram word2vec, a neural network trained to predict a window of words given the focus word as input. The word embedding matrix is the resulting weight matrix after training.</figcaption></figure><p>Are we going to train a word2vec model? Nah. We said we wanted to build this tool quickly, for that we are going to use pretrained word2vec vectors, even if we wanted to train our own model we couldn’t because we don’t have enough data to do it anyway.</p><p>Now, let’s start coding, we will download pretrained w2v trained on Google News from <a href="https://drive.google.com/file/d/0B7XkCwpI5KDYNlNUTTlSS21pQmM/edit">this google drive</a>, then pip install gensim. Gensim is an awesome library that allows dealing with NLP in a high-level manner. Loading pretrained word2vec takes only one line.</p><pre>import gensim<br>model = gensim.models.KeyedVectors.load_word2vec_format(W2V_PATH, binary=True)</pre><p>Now the model is loaded, we can take a look to see how words are represented:</p><pre>&gt;&gt;&gt; model.wv[&#39;hello&#39;].shape<br>(300,)<br>&gt;&gt;&gt; model.wv[&#39;hello&#39;]<br>array([-0.05419922, 0.01708984, ..., -0.25], dtype=float32)</pre><p>The vectors have a size of 300 while the vocabulary size of google news is around 3 millions words! We said one particularity of word2vec is that words that occur in the same context will tend to have vectors close to each other regarding distance because they are likely to be close, semantically speaking.</p><pre>&gt;&gt;&gt; model.similar_by_word(&#39;hello&#39;, topn=5)<br>[(&#39;hi&#39;, 0.6548984050750732), (&#39;goodbye&#39;, 0.639905571937561), (&#39;howdy&#39;, 0.6310957074165344), (&#39;goodnight&#39;, 0.5920578241348267), (&#39;greeting&#39;, 0.5855877995491028)]</pre><p>You can see that “hi” is the closest word to “hello” according to cosine similarity(a commonly used distance metric). I’m always amazed by that; instead of having a large one-hot vector that teaches us nothing about the relationship between words, we now have a vector size much smaller in a vector space that seems to encode relationships.</p><pre>def cosine_sim(a, b):<br>    return np.dot(a, b) / (np.linalg.norm(a) * np.linalg.norm(b))</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/359/1*1tNcJbX13Bh1nLB_GDylDw.png" /><figcaption><a href="https://en.wikipedia.org/wiki/Cosine_similarity">Cosine similarity.</a> The closer to one the better</figcaption></figure><h4>What about sentences?</h4><p>So far we’ve been talking about words and similarity between them, but what we need is a way to measure the similarity between two sentences and it seems complicated. Of course, it is, but we are building a little tool, we want good results not perfect ones.</p><pre>def avg_sentence(sentence, wv):<br>  v = np.zeros(300)<br>  for w in sentence:<br>    if w in wv:<br>      v += wv[w]<br>  return v / len(sentence)</pre><p>Averaging words vectors is an easy way to compare two sentences, yes it is a noisy process because we are losing the word order in the phrase so two sentences having reverse word order will give the same averaged vector while often not meaning the same thing. Plus, all words have the same weights while words like “a” or “the” should ideally matter less. However, this trick works quite well, so we will stick with it to keep the whole thing simpler. The intuition behind this trick is that if the two sentences are similar, their averaged vector will end up in (almost) the same location.</p><pre>&gt;&gt;&gt; inputv = avg_sentence(&#39;i like you&#39;.split(), model.wv)<br>&gt;&gt;&gt; vec2 = avg_sentence(&#39;i love you&#39;.split(), model.wv)<br>&gt;&gt;&gt; vec3 = avg_sentence(&#39;screw you guys&#39;.split(), model.wv)<br>&gt;&gt;&gt; cosine_sim(inputv, vec2)<br>0.87972317862080773<br>&gt;&gt;&gt; cosine_sim(inputv, vec3)<br>0.66992365073780347</pre><p>So now that we have a way to know if two sentences are similar, the next steps are pretty straightforward. Remember that we have a list of pairs. Each pair is an image URL and a description associated with it.<br>In order:</p><ol><li>Average input query and memes’ description</li><li>Compute cosine similarity between the averaged input and the averaged descriptions</li><li>Sort the list by cosine similarity in descending order such that descriptions that are the most similar to the input sentence will appear first.</li></ol><pre>&gt;&gt;&gt; avgs = list(map(lambda p: p + (avg_sentence(p[1].split, model.wv),), url_descr))<br>&gt;&gt;&gt; sims = list(map(lambda p: p[:2] + (cosine_sim(inputv, p[2]),), avgs))<br>&gt;&gt;&gt; most_similar_meme = sorted(sims, key=lambda p: p[2], reverse=True)<br>&gt;&gt;&gt; most_similar_meme<br>[(&#39;<a href="https://tny.im/a0-&#39;">https://tny.im/a0-&#39;</a>, &#39;i love you&#39;, 0.87972317862080773), (&#39;<a href="https://tny.im/a10&#39;">https://tny.im/a10&#39;</a>, &#39;screw you guys&#39;, 0.66992365073780347), (&#39;<a href="http://tny.im/a13&#39;">http://tny.im/a13&#39;</a>, &quot;we don&#39;t care&quot;, 0.56639891559620026), (&#39;<a href="https://tny.im/a12&#39;">https://tny.im/a12&#39;</a>, &#39;relax take it easy&#39;, 0.40517121688823338), (&#39;<a href="https://tny.im/a16&#39;">https://tny.im/a16&#39;</a>, &#39;that is embarrassing&#39;, 0.2843743794717129)]</pre><h4>Conclusion</h4><p>We saw how to build a very basic, yet not bad, meme retrieval system using pretrained word embeddings. However, it is far from being perfect, for instance:</p><pre>&gt;&gt;&gt; inputv = avg_sentence(&#39;i like you&#39;.split(), model.wv)<br>&gt;&gt;&gt; vec2 = avg_sentence(&#39;i love you&#39;.split(), model.wv)<br>&gt;&gt;&gt; vec3 = avg_sentence(&#39;i hate you&#39;.split(), model.wv)<br>&gt;&gt;&gt; cosine_sim(inputv, vec2)<br>0.87972<br>&gt;&gt;&gt; cosine_sim(inputv, vec3)<br>0.87976</pre><p>According to the model, “hate” is more similar to “like” than “love”(the difference is very small though). This could be explained by the fact that “hate” and “like” appeared in the same contexts a little more than “love” and “like” did during training. However, there is a large room for improvements that could be used to correct these flaws, like sentence classification, term frequency weighting(tf-idf) etc…</p><p><em>I did my best to keep this article as simple as possible(eg., I assumed semantic and context to be the same thing while they aren’t), if you noticed any mistake please let me know on twitter </em><a href="http://twitter.com/eyyub_s"><em>@eyyub_s</em></a><em> or in the comments section. Big thanks to my shab </em><a href="https://twitter.com/ImLaaraj"><em>@ImLaaraj</em></a><em>.</em></p><h4>Gist</h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/dd3f973f733a23a9d5a3245194214196/href">https://medium.com/media/dd3f973f733a23a9d5a3245194214196/href</a></iframe><p>[1] <a href="http://mccormickml.com/2016/04/19/word2vec-tutorial-the-skip-gram-model/">http://mccormickml.com/2016/04/19/word2vec-tutorial-the-skip-gram-model/</a><br>[2] <a href="http://colah.github.io/posts/2014-07-NLP-RNNs-Representations/">http://colah.github.io/posts/2014-07-NLP-RNNs-Representations/</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9f8df0a1ade3" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/meme-search-using-pretrained-word2vec-9f8df0a1ade3">Meme search using pretrained word2vec</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[Shab Dev Story #01: Trying to find the matrix form of gradient descent via backprop]]></title>
            <link>https://medium.com/data-science/shab-dev-story-01-trying-to-find-the-matrix-form-of-gradient-descent-via-backprop-1c2bf7fdf5fe?source=rss-7612afea778b------2</link>
            <guid isPermaLink="false">https://medium.com/p/1c2bf7fdf5fe</guid>
            <category><![CDATA[python]]></category>
            <category><![CDATA[neural-networks]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[backpropagation]]></category>
            <dc:creator><![CDATA[Eyyüb Sari]]></dc:creator>
            <pubDate>Wed, 07 Jun 2017 23:18:25 GMT</pubDate>
            <atom:updated>2017-06-07T23:18:25.143Z</atom:updated>
            <content:encoded><![CDATA[<p><em>I apologize in advance if I did a wrong use of some math notions and invite you to tell me which ones in order to improve this article that I wrote primarily for myself.</em></p><p>Learning how to perform backpropagation is one of the early steps if we want to implement a neural network trained using gradient descent. Then if we want to be a little more serious in the game, we vectorize/matricize our forward pass because it makes the code clearer and more efficient. The reality catches up with us quickly because our chain rule in the backward pass no longer works thanks to matrices and matrix product. So we invoke our magic skills and fix the whole thing by making matrices’ dimensions match by reordering our expressions. At least, it’s what I did.</p><p>In this article, we try to see if the expressions we get for gradient descent in matrix form using a matrix calculus are the same that the ones we get when we do a kind of magic. It’s not an introduction to gradient descent via backprop, and I think it is mostly addressed to developers(with no math background) that also tried to understand the maths.</p><h4>What’s the issue?</h4><p>Let say we have a two layer net (one hidden, one output) and that we use matrices for representing its parameters(i.e. the weights) as for its inputs and that we use matrix-valued activation function:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/185/1*wZDl8zAWyC_QalGZs2IWZg.png" /></figure><p>Here, X is the matrix containing our mini-batch’s inputs (rows are instances and columns represent features). W1 and W2 are matrices containing respectively all the weights belonging to all the neurons in the hidden layer and the output layer (a column represents a neuron and the rows below are its weights). Lower sigma σ is our matrix-valued activation function(which for instance basically applies the sigmoid function to all input matrix’ elements). Now what if we would like to compute the updated value of W1 for a (mini-batch) gradient descent step?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/297/1*twTzCEy1Trz0MhD-X2jaIg.png" /></figure><p>What I did back then was trying to take the derivative of some loss function(MSE for instance) w.r.t to W1. I ended up with something like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/694/1*ox6s2RQqUzBo_PfRZ8Fb4w.png" /><figcaption>This chain rule is not sound.</figcaption></figure><p>This DOESN’T work at all, in fact, the matrices products can’t work because matrices don’t have the good dimensions, which was a thing I didn’t know at that time, almost a year ago 😕. I tried to reverse the expression, tried to add Hadamard products, but none of those things worked. Then I learned about matrix transpose operation and started doing magic things to make matrices shapes and products work while ensuring I would get an equivalent expression to the partial derivative of the loss function w.r.t W1’s weights in its scalar form. That gave me:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/465/1*OHFWOS8zCIwi1agWzUroJQ.png" /><figcaption>The delta of W1 given after backprop.</figcaption></figure><p>Months went by, then not so long ago I started working on a toy OCaml neural network library, even if my math level slightly leveled up within a year, I wasn’t able to find, by myself, a real mathematical justification using calculus for the expression above. Even when it comes to math, I think that a developer should not use something so fundamental without at least trying understanding it. Andrej Karpathy’s <a href="https://medium.com/@karpathy/yes-you-should-understand-backprop-e2f06eab496b">“Yes you should understand backprop”</a> made me decide that I should investigate a better justification to find peace.</p><h4>Looking for a way to express matrix derivatives</h4><p>The real issue we have here is, is there a way to take the partial derivative of a cost function w.r.t to W1, and more generally, is there a way to take the derivative of a matrix-valued function w.r.t to a matrix?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/103/1*h3ReXLEQUq_-_C22OB8jSg.png" /><figcaption>What’s the derivative?</figcaption></figure><p>We could say that the derivative of F(X) w.r.t to X is a matrix having the shape of X:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/217/1*ysUB76bTaQE0qrDRLA8gVA.png" /><figcaption><a href="https://en.wikipedia.org/wiki/Matrix_calculus#Other_matrix_derivatives">Matrix derivative (wikipedia)</a></figcaption></figure><p>This definition has something interesting; the matrix has the shape of X which means the update of our parameters would be straightforward. However, this formula has a flaw:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/395/1*ugypw9zoQa2WsJdh-w5PfQ.png" /></figure><p>Yes, it doesn’t allow for a chain rule, and no chain rule -&gt; no backprop.</p><p>We need a chain rule, and that’s what JR. Magnus and H. Neudecker offer us in <a href="http://www.janmagnus.nl/misc/mdc2007-3rdedition">Matrix Differential Calculus(ch9.3)</a>. They argument about some bad notations and a good notation for expressing matrix derivatives. They basically say that taking a derivative of a matrix-valued function w.r.t to a matrix is somewhat inconsistent and argue for a generalization of the Jacobian to matrices:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/176/1*PS8RKscrXND5RTXwg8yLsA.png" /><figcaption>Formula 1. vec is the <a href="https://en.wikipedia.org/wiki/Vectorization_(mathematics)">vec operator</a></figcaption></figure><p>If <em>F(X)</em> has the shape <strong>p</strong>x<strong>q</strong> and <em>X</em> has the shape <strong>m</strong>x<strong>n</strong>, <em>vec(F(X))</em> will be a column vector having the shape <strong>pq.</strong> <em>transpose(vec(X))</em> will be a row vector having the shape <strong>mn</strong>, thus the Jacobian will have the shape <strong>pq</strong>x<strong>mn</strong>. While the Jacobian is not exactly the partial derivative of <em>F(X)</em> w.r.t to X, it contains all information we need to obtain it, and above all, it allows for a chain rule:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/492/1*8U0iGU9UQiH9-YwDzhsTxQ.png" /><figcaption>Formula 2. Derivative of a composition</figcaption></figure><p><strong>Note</strong> that we also could say that the derivative we are looking for is a fourth-rank tensor (as pointed out by wikipedia), but I didn’t find any comprehensible resources for it.</p><h4>Unrolling the chain rule step-by-step</h4><p><strong>Warning /!\ </strong>This section almost only contains math and could be not very interesting.<br>Now that we have a way to express matrix derivatives, we can state what we are currently looking for:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/389/1*FfvHy0Lfgdcwgom6lUioaA.png" /></figure><p>This Jacobian will give us everything we need to update W1 for a gradient descent step. For now, let’s unroll the chain rule step-by-step:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/604/1*HmOGwpETSHfWIcP4NbliJQ.png" /><figcaption>Step 1.</figcaption></figure><p>For the first chunk, we can see we are looking for the derivative of an expression that only performs element-wise scalar multiplication against a matrix U(a placeholder name for the squared subtraction). We know that for scalars the derivative of <strong><em>ax</em></strong> w.r.t <strong><em>x</em></strong> is <strong><em>a </em></strong>(<strong><em>a</em></strong> being a constant), but for a matrix we have:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/419/1*Y8EEnmrsLvxfINU8696YSg.png" /><figcaption>Formula 3. The derivative of the identity function is the identity matrix(dim is dimension of a vector).</figcaption></figure><p>That is, the identity matrix. Thus we simply have:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/457/1*2biCclF9gCgpFqdKP1fOzQ.png" /></figure><p>Then, for the second chunk, we are looking for the derivative of a squared matrix V (squared in the sense of an element-wise product, not a matrix product):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/642/1*WW6nfMZMEHp8JAKLVgosSw.png" /><figcaption>Step 2.</figcaption></figure><p>In order to express the derivative of a vectorized Hadamard product, we’ll use the property that allows us to express it as a matrix product, so that we can use the well-known product rule derivative:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/314/1*u8Y8J17b_gJLJZ0ojtFlSg.png" /><figcaption>The Diag function takes a row vector and puts its elements along the diagonal of a square matrix full of zeros everywhere else.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/462/1*sf29qDqjXGaj0g5W-zW_KA.png" /><figcaption>Formula 3. Vectorized Hadamard product expressed as a matrix product.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/552/1*2DQRONMOo3EXYULbHe5KTA.png" /><figcaption>Formula 4. Derivative of vectorized Hadamard product using formula 3</figcaption></figure><p>As A, B and X are all equal to V in our case; the expression is thus reduced to:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/837/1*3eWIocUpCl0uM2d_ZLVVuA.png" /></figure><p>As you can see below, we could already start to simplify the expression, but let’s just do one thing at a time.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/770/1*x1RC0QUHH2ZISXJdUn6j_g.png" /><figcaption>Step 3.</figcaption></figure><p>For the first step, we can see here that we are taking derivative of a subtraction, here is the obvious formula we need:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/321/1*Ajep_bPlMuS4F8Bocbzs-w.png" /><figcaption>Formula 5. Derivative of subtraction</figcaption></figure><p>Then after a straightforward application, we obtain:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/533/1*g2Vxn8TXlnzqCJppjGMU9g.png" /></figure><p>Here is what our expression currently looks like after having unrolled the loss function part of the chain rule:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/704/1*WhC8FGDdI8yhDfIzGzNOUg.png" /></figure><p>The expression already starts to be pretty long, so let’s leave the unrolled part of the chain rule aside to focus on the feed-forward side and derive it step by step:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/656/1*Kb8HDuA2b-tbJ9et--OCTQ.png" /><figcaption>Step 4.</figcaption></figure><p>As σ(A) is an element-wise function application we have:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/519/1*J6cD0cnJ_IB-QFp1hWxeSA.png" /><figcaption>Formula 6. Derivative of element-wise function</figcaption></figure><p>Where σ’ is its derivative.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/626/1*FKQnvJ_4Blfpy6mrgeUCgA.png" /><figcaption>Step 5.</figcaption></figure><p>Here for the next step, we would like the derivatives of a vectorized matrix product, so how can we do this? First, let’s introduce some formula:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/228/1*CI70K2mqiaWGpmb7Xjo-6w.png" /><figcaption>Formula 7 &amp; 8. Vectorized product of 3 matrices and its derivative.</figcaption></figure><p>What is interesting with these formula is that they allow the use of known matrices. But how do we apply them to the current partial derivative we want as we only have a product between two matrices? Here are the two “tricks”:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/281/1*igKO12xOHupinu_gTn0VAw.png" /><figcaption><strong>nrow(X)</strong> is the number of rows in X</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/271/1*28V1LuXEYzclWR-dq4m3Yg.png" /><figcaption><strong>ncol(X)</strong> is the number of columns in X</figcaption></figure><p>We add a product with an identity matrix to the left of the expression, which allows us to use the formula above:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/479/1*3ttJK8hC5wA09nmTQh-eUw.png" /></figure><p>We could ask what prevented us from taking the partial derivative of a vectorized matrix product between two matrices? Well, the advantages are that derivatives are expressed with known matrices and also because we don’t have to derive it ourselves(= less work).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/739/1*h6uss9ixU4PMNVtzoJmGQQ.png" /><figcaption>Step 6.</figcaption></figure><p>This step is pretty straightforward, as we reuse the same formula that we already used (Formula 6). Now last step:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/812/1*-4LiNZo4j0d9N9bu28qHDg.png" /><figcaption>Step 7.</figcaption></figure><p>To use our formula (8) we need W1 to be in the middle, to do so this time we add a matrix product with the Identity matrix to the right. Now that we have unrolled all the feed-forward side, we can take a look at the overall expression:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*qMMOwfVvTkBiZuX0UkxAnQ.png" /></figure><p>This is pretty big, so let’s reduce it as much as we can:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*PTKAVENHSupqc52NoVOhEg.png" /><figcaption>Reducing the expression.</figcaption></figure><p>Note that we could continue to reduce, for instance the transpose of an identity matrix is itself, Diag can be merged etc…</p><h4>Updating the weights</h4><p>Okay now that we have unrolled the chain rule, we are left with a Jacobian matrix, how do we use it in order to update W1 (and our parameters in general)?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/375/1*VoVV2OX6oehsih03Q9ZG1w.png" /><figcaption><a href="https://en.wikipedia.org/wiki/Jacobian_matrix_and_determinant">A Jacobian matrix.</a></figcaption></figure><p>As you can see, each column involve derivatives w.r.t the one element of the vector so in order to get the “total” derivatives w.r.t to this element we need to sum up the rows, we can do it with a row vector full of ones that contains as many columns as the Jacobian contains rows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/280/1*dUWaY3OhJE-R4eZWOtqFLQ.png" /></figure><p>It gives us a row vector containing the summed derivative w.r.t to each element of W1.</p><p>In order to update W1 we need to get a matrix having the same shape, so what we need is a function that is the inverse of vec:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/373/1*EtHsePcfvhxhYGkpu9royw.png" /><figcaption>The <a href="https://math.stackexchange.com/a/1830212">inverse of vec</a> reshape a column vector into a matrix.</figcaption></figure><p>Now we have a matrix that has the same shape as W1 containing the derivative of the loss w.r.t to each matrix element. Note that we have transposed the row vector because <em>vec</em> outputs a column vector.</p><p>Finally, let’s see the final expression that updates W1:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/466/1*JjKmS4a8vJhnWnRX1Wi2_Q.png" /></figure><p>Let’s recall the expression we found by making the dimensions match:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/544/1*UNPB7SW520N420hGAroVoA.png" /></figure><p>We could derive the expressions and see that they are theoretically equivalent (which I did) but this article already contains a lot of math, and I’m not sure it will be worth it. However don’t worry, we will check numerically in the implementation that they are equivalent.</p><h4>Back to backprop</h4><p>Until now we focused on unrolling the chain rule, but unrolling the chain rule forever is not backpropagation, backpropagation is an algorithm, not a formula, in the sense that it is a computationally efficient incarnation of it. Backprop is about backpropagating “errors” through the layers and neurons to weights starting from the loss function error.</p><p>As a recall, here is the backprop form obtained by making the dimensions match:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/204/1*7SQqcauk8SvCD2kYGqq1Tw.png" /></figure><p>And the update statement:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/150/1*fSOZ3wfJJb_t_tR1MLxv_g.png" /></figure><p>The backprop form we found by using matrix calculus is:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/610/1*bb4AnGIMt6ExQU36rpH0fw.png" /></figure><p>The intuition behind backpropagating errors is that first, we have the error at the loss function level, that is, how much the loss varies w.r.t to change in <em>H(X). </em>Then starting from the output layer and moving back to the first hidden layer, we compute the error of the neurons in the current layer. It’s done by performing a matrix product between the error at the next layer(except for the output layer btw because the error comes from the loss function and not a layer) and the derivative of the activation function with respect to the inputs of this layer. Then for the weights of this layer, <em>Wl</em>, the total error w.r.t the weights is the product of the error in the current layer’s neurons and their input.</p><p>Here is the backprop steps for our two layer neural net:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/768/1*G3LNZDmnpYBaqGeqaNuStw.png" /></figure><p>Then to update the weights of a layer:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/302/1*ragg5wEJaw5XzIQucMjicQ.png" /></figure><h4>Implementation</h4><p>The following gist is a NumPy implementation of a neural networ trained using gradient descent via the two backprop forms on the XOR problem. The learning rate is 1 and we don’t divide deltas by 1/4 to make the neural network converge faster. <a href="https://docs.scipy.org/doc/numpy/reference/generated/numpy.kron.html">np.kron</a> is the Kronecker product, <a href="https://docs.scipy.org/doc/numpy/reference/generated/numpy.diag.html">np.diag</a> is the Diag function and <a href="https://docs.scipy.org/doc/numpy/reference/generated/numpy.eye.html">np.eye</a> returns an identity matrix.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d6502ddf18273a993cce8fc550de36f3/href">https://medium.com/media/d6502ddf18273a993cce8fc550de36f3/href</a></iframe><h4>Which backprop form should we use</h4><p>I found the vectorized derivative easier to use and more pedagogical; you can see that we never had to address a matrix element Aij, all we did was unrolling the chain rule. However, of course, we should use the form we found by making the shapes match, because it is more efficient regarding memory and perfs. The Diag matrices and the Kronecker products cost a lot.</p><h4>Conclusion</h4><p>A lot of people got concerns about AI and the fact it could be used to serve bad purposes, but I think we should not neglect the fact that developers using AI algorithms as a blackbox could also lead AI to do bad things, unintentionally. That is why I think us, developers, should at least try to understand how models work. No need to be a math guy, you can even read papers and ask help to your friend Google! Things done in the field right now are amazing (DRL, GANs… ❤). It is never too late to start, I personally found an interest in neural networks and ML stuff only last year after having watched the Iron Man movies 😅.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1c2bf7fdf5fe" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/shab-dev-story-01-trying-to-find-the-matrix-form-of-gradient-descent-via-backprop-1c2bf7fdf5fe">Shab Dev Story #01: Trying to find the matrix form of gradient descent via backprop</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>
    </channel>
</rss>