<?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 Arnab Sinha on Medium]]></title>
        <description><![CDATA[Stories by Arnab Sinha on Medium]]></description>
        <link>https://medium.com/@sarnab433?source=rss-68abfb18d394------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*Pj5hwRSmsJ8o8pAqq-TqbA.jpeg</url>
            <title>Stories by Arnab Sinha on Medium</title>
            <link>https://medium.com/@sarnab433?source=rss-68abfb18d394------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 15:14:45 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@sarnab433/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[News article virality prediction]]></title>
            <link>https://medium.com/analytics-vidhya/news-article-virality-prediction-c0c069de0c9c?source=rss-68abfb18d394------2</link>
            <guid isPermaLink="false">https://medium.com/p/c0c069de0c9c</guid>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[data-analysis]]></category>
            <category><![CDATA[information-retrieval]]></category>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Arnab Sinha]]></dc:creator>
            <pubDate>Wed, 29 Apr 2020 16:20:01 GMT</pubDate>
            <atom:updated>2020-04-29T16:20:01.169Z</atom:updated>
            <content:encoded><![CDATA[<p>The previous 2 articles explained about Information retrieval and some basic codes that would help you implement web scraping. This article focuses on extraction of news articles and prediction of their virality using various machine learning models. <strong>The virality is measured in terms of the “number of shares the article received”.</strong></p><p>Click the links below if you need prior reference regarding web scraping.</p><ol><li><a href="https://medium.com/analytics-vidhya/information-retrieval-part-1-extracting-webpages-a9d0b715535d">Information-retrieval Part-1 : Extracting webpages</a></li><li><a href="https://medium.com/analytics-vidhya/information-retrieval-part-2-simplifying-the-information-53880b930ebd">Information-retrieval Part-2 : Simplifying the Information</a></li></ol><h3><strong>1. Dataset:</strong></h3><p><a href="http://archive.ics.uci.edu/ml/datasets/Online+News+Popularity">Online News Popularity</a></p><h3><strong>2. Libraries used</strong>:</h3><p>newspaper3k, TextBlob, sklearn, numpy, requests, BeautifulSoup, nltk, pandas, seaborn, catboost, xgboost</p><pre>import numpy as np<br>import pandas as pd<br>import matplotlib.pyplot as plt<br>from sklearn import preprocessing<br>from sklearn.model_selection import train_test_split, GridSearchCV<br>from sklearn.ensemble import RandomForestRegressor<br>from catboost import CatBoostRegressor<br>from sklearn.linear_model import RidgeCV<br>from xgboost import XGBRegressor<br>from xgboost import plot_importance<br>from sklearn.metrics import mean_squared_error as RMSE<br>from sklearn.decomposition import PCA<br>import seaborn as sns<br>from newspaper import Article<br>import requests<br>from bs4 import BeautifulSoup<br>from textblob import TextBlob<br>from nltk.tokenize import word_tokenize <br>from nltk.corpus import stopwords</pre><h3>3. Working with the dataset</h3><ul><li>A few precautionary steps are taken initially . E.g. formatting the column names, dropping unnecessary columns</li><li>Extracting the important features ( below )</li></ul><p>The <strong>XGBoost</strong> library provides a method <strong><em>plot_importance()</em></strong> to calculate the importance of the features comprised within the dataset. Following is the plot created for the UCI dataset.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/750/0*F45_G3DU7FHloYHl.png" /><figcaption>plot_importance() plot for UCI Online News Popularity dataset</figcaption></figure><p>The <strong>top 20</strong> features are extracted, keeping a <strong>threshold of 600</strong>. I managed to calculate <strong>9</strong> of them as the rest of them were not described clear enough to formulate. Following are the feature calculated:</p><ul><li><strong>n_tokens_title</strong> : Number of words in the title</li><li><strong>n_tokens_content: </strong>Number of words in the content</li><li><strong>n_unique_tokens : </strong>Rate of unique words in the content ( #unique words / #words )</li><li><strong>average_token_length : </strong>Average length of the words in the content</li><li><strong>avg_positive_polarity : </strong>Average polarity of positive words</li><li><strong>n_non_stop_unique_tokens : </strong>Rate of unique non-stop words in the content</li><li><strong>num_hrefs :</strong> Number of links in the article</li><li><strong>global_subjectivity : </strong>subjectivity of article content</li><li><strong>global_sentiment_polarity</strong> : Text sentiment polarity</li></ul><p>Let us have a brief overview about the two libraries, <strong>newspaper3k and TextBlob</strong>, which are used to calculate the above features.</p><blockquote>Newspaper is an amazing python library for extracting &amp; curating articles.</blockquote><p>The following code focuses on extracting news from a news article URL and accessing various features like the <strong>title of the article, content text</strong> etc.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1e32585f74045202608e60254327fe3b/href">https://medium.com/media/1e32585f74045202608e60254327fe3b/href</a></iframe><blockquote>TextBlob is a Python library for processing textual data. It provides a simple API for diving into common natural language processing (NLP) tasks such as part-of-speech tagging, noun phrase extraction, sentiment analysis, classification, translation, and more.</blockquote><p>The TextBlob library helps us in calculating the <strong>polarity and subjectivity</strong> of words and sentences. It is used as follows:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/3ab68ea4c5eae61920462bb7ca3f9d22/href">https://medium.com/media/3ab68ea4c5eae61920462bb7ca3f9d22/href</a></iframe><p>Having done this, using <strong>nltk.tokenize</strong> and <strong>nltk.corpus.stopwords</strong>, the first 6 features can be easily calculated. ( Code in GitHub repository ).</p><p>Lastly,<strong> num_hrefs</strong> is computed with the method below:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1fe9835f59a8fe14d0056a3838fa3b9d/href">https://medium.com/media/1fe9835f59a8fe14d0056a3838fa3b9d/href</a></iframe><h3>4. Scraping news articles</h3><p>I have scraped articles from the British Broadcasting Corporation (BBC) website to collect news articles.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/3262906bfd3edd652b0490463b2a5e8d/href">https://medium.com/media/3262906bfd3edd652b0490463b2a5e8d/href</a></iframe><p>The articles links are then collected into a single list. Further, the articles are then scraped using the newspaper3k library.</p><p>Finally, the <strong>9 features</strong> described in the previous section are calculated for the article texts and a final dataset of news articles’ features is created.</p><p><strong>NOTE: The 9 features defined above are sliced from the original UCI dataset to match the features of the news articles’ dataset.</strong></p><h3>5. Testing on Machine Learning models</h3><p>The UCI dataset was split 4 different models are trained and tested, as follows:</p><ul><li>XGboost Regressor</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/647/1*QZcP0jpfSZN8r-622CqDgQ.png" /></figure><p>Two versions of XGBoost were used, one using <strong>gblinear</strong> as a booster and the other using <strong>gbtree</strong> as one.</p><p>The average result on multiple runs gave RMSE of ~10973 for gblinear and ~11430 for gbtree.</p><ul><li>RandomForestRegressor</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/604/1*l5ALJi1VxFpNWNh0nyjJng.png" /></figure><p>The average result on multiple runs gave RMSE of ~10973.</p><ul><li>RidgeCV Linear Regressor</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/642/1*NLmpgTm9klj0ML3E5JBQAQ.png" /></figure><p>The average result on multiple runs gave RMSE of ~10952.</p><ul><li>CatBoost</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*aQY4TvfAHEr71NdLdI9qWQ.png" /><figcaption>Zoom in for detail</figcaption></figure><p>The average result, with the parameters tested, was an RMSE~11200.</p><p>The final plot of the evaluations looks like this</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/418/1*bUs1qMXBm2dyB4Td3GyL_g.png" /></figure><p>Apparently, RidgeCV performed the best among all the models. The models are then used to predict the number of shares on the news articles extracted. The results of RidgeCV were, on an average, 10x that of the other models. Since the true number of shares were not available, I could not conclude which of them were accurate.</p><p>Thanks for your attention!</p><p>The link to the notebook is given below. Feel free to comment about any improvements which can be made! :-)</p><p><strong>Link to the GitHub repository : </strong><a href="https://github.com/arnabsinha99/MListheroxx/tree/master/Mini_Projects/News%20Virality%20Prediction"><strong>News Virality Prediction</strong></a></p><p><strong>Link to the Kaggle notebook : </strong><a href="https://www.kaggle.com/sherlocked99/news-virality-prediction?scriptVersionId=32865911#Converting-UCI-dataset"><strong>News Virality Prediction</strong></a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c0c069de0c9c" width="1" height="1" alt=""><hr><p><a href="https://medium.com/analytics-vidhya/news-article-virality-prediction-c0c069de0c9c">News article virality prediction</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>
        <item>
            <title><![CDATA[Information Retrieval (Part 2): Simplifying the Information]]></title>
            <link>https://medium.com/analytics-vidhya/information-retrieval-part-2-simplifying-the-information-53880b930ebd?source=rss-68abfb18d394------2</link>
            <guid isPermaLink="false">https://medium.com/p/53880b930ebd</guid>
            <category><![CDATA[text-analytics]]></category>
            <category><![CDATA[inverted-index]]></category>
            <category><![CDATA[information-retrieval]]></category>
            <category><![CDATA[data-science]]></category>
            <dc:creator><![CDATA[Arnab Sinha]]></dc:creator>
            <pubDate>Wed, 01 Jan 2020 12:56:57 GMT</pubDate>
            <atom:updated>2020-01-01T12:56:57.220Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/728/1*6ZLUgaqHQ_uet4GCM6L0jQ.png" /></figure><p>In the previous article, we explored a technique to extract the information. Let us now look at some of the key terms to understand before moving forward with the coding part.</p><h3><strong>Tokenization</strong></h3><p>Given a character sequence and a defined document unit, tokenization is the task of chopping it up into pieces, called <em>tokens</em> , perhaps at the same time throwing away certain characters, such as punctuation.</p><p>Tokenization can be of two types:</p><ol><li><em>Tokenizing paragraphs into sentences</em></li></ol><p>E.g. Assume a given a document with the following text : “Sam is a good student. He is kind and helpful in nature.”</p><p>The tokenized sentences would be the list : [“Sam is a good student.”, “He is kind and helpful in nature.”]</p><ol><li><em>Tokenizing sentences into individual words</em></li></ol><p>E.g. If we want to tokenize the first sentence of the above paragraph, the tokenized form would be the list: [“Sam”, “is”, “a”, “good”, “student”, “.”]</p><h3><strong>Stopwords</strong></h3><p>Stopwords are a list of most commonly used in any natural language. For the purpose of analyzing text data and building NLP models, these stopwords might not add much value to the meaning of the document and hence we exclude them from analysis.</p><p>If you want to view the list of stopwords in English, you can run the following code:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/0972807544f6f030ac2a7e7cfc6e1395/href">https://medium.com/media/0972807544f6f030ac2a7e7cfc6e1395/href</a></iframe><h3><strong>Lemmatization v/s Stemming</strong></h3><p>Defining the two terms,</p><blockquote>Stemming is a <strong>rudimentary rule-based process</strong> for text normalization technique that <strong>cuts off the end or beginning</strong> <strong>of a word</strong> by taking into account a list of <strong>common prefixes or suffixes</strong> that could be found in that word</blockquote><blockquote>Lemmatization is an organized method of obtaining the root form of the word. It <strong>makes use of vocabulary</strong> (dictionary importance of words) and <strong>morphological analysis</strong> (word structure and grammar relations).</blockquote><p>Stemming is a <strong>fast</strong> but <strong>dirty method</strong> of chopping up the words.</p><p>Lemmatization is an <strong>intelligent operation</strong> that uses dictionaries of a particular language.</p><p><strong>Hence, Lemmatization helps in forming better features.</strong></p><h3>Inverted Index</h3><p>The inverted index of a document collection is basically a data structure that attaches each distinctive term with a list of all documents that contains the term.</p><p>A modified version of it could be one in which we attach the frequency of the word in a particular document along with the document number. The image below would clarify the intuition.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/606/1*GEL4skRcT0DV9k4wdwJD3Q.png" /></figure><p>Now, we can move forward to building the inverted index.</p><p>Some useful libraries to import are:</p><pre>import nltk<br>from nltk.tokenize import word_tokenize<br>from nltk.corpus import stopwords<br>from nltk.stem import WordNetLemmatizer</pre><p>For every document, we first tokenize the document into individual words.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b8dfb7efa43484bb54ab7b85b08fc3b4/href">https://medium.com/media/b8dfb7efa43484bb54ab7b85b08fc3b4/href</a></iframe><p>We ignore the stopwords simultaneously for efficient tokenizing.</p><p>We then lemmatize the individual words using the nltk-imported library <strong>WordNetLemmatizer</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/80c1e41c0feef98c74cfe62eb9e1ccc7/href">https://medium.com/media/80c1e41c0feef98c74cfe62eb9e1ccc7/href</a></iframe><p>Finally, we create an inverted index. We maintain a secondary list called <strong>ispresent </strong>store the words that are already present in the inverted index. The variable <strong>invind</strong> stores the inverted index.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1f0cb9888f3998c0fd02ae41491999d2/href">https://medium.com/media/1f0cb9888f3998c0fd02ae41491999d2/href</a></iframe><p>As you can see, [y,1] means that we are storing a tuple of the document number and the term frequency of <strong>word </strong>in that document <strong>y</strong>.</p><p>We finally have the inverted index and can use this for further text analysis.</p><p>Inverted index has the following advantages:</p><ul><li>It allow for <strong>fast full text searches</strong>, at a cost of increased processing when a document is added to the database.</li><li>It is <strong>easy to develop</strong>.</li><li>It is the <strong>most popular data structure</strong> used in document retrieval systems, used on a large scale for example in search engines.</li></ul><p>A notable disadvantage is that it carries with it <strong>large storage overhead</strong> and <strong>high</strong> maintenance <strong>costs on update, delete and insert</strong>.</p><p>For the complete code including the web scraping, follow the link attached below.</p><p><a href="https://github.com/arnabsinha99/MListheroxx/blob/master/Mini_Projects/Information%20Retrieval/IR%20Assignment%201.ipynb">arnabsinha99/MListheroxx</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=53880b930ebd" width="1" height="1" alt=""><hr><p><a href="https://medium.com/analytics-vidhya/information-retrieval-part-2-simplifying-the-information-53880b930ebd">Information Retrieval (Part 2): Simplifying the Information</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>
        <item>
            <title><![CDATA[Information Retrieval (Part 1): Extracting webpages]]></title>
            <link>https://medium.com/analytics-vidhya/information-retrieval-part-1-extracting-webpages-a9d0b715535d?source=rss-68abfb18d394------2</link>
            <guid isPermaLink="false">https://medium.com/p/a9d0b715535d</guid>
            <category><![CDATA[information-retrieval]]></category>
            <category><![CDATA[beautifulsoup]]></category>
            <category><![CDATA[data-mining]]></category>
            <category><![CDATA[requests-library]]></category>
            <category><![CDATA[web-development]]></category>
            <dc:creator><![CDATA[Arnab Sinha]]></dc:creator>
            <pubDate>Tue, 24 Sep 2019 05:23:09 GMT</pubDate>
            <atom:updated>2020-08-07T15:36:57.961Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*j5PzJtbnc7ks75ng" /><figcaption>Photo by <a href="https://unsplash.com/@samuelzeller?utm_source=medium&amp;utm_medium=referral">Samuel Zeller</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><blockquote>Information retrieval is the activity of obtaining information system resources that are relevant to an information need from a collection of those resources.</blockquote><p>Before we move on to extracting relevant information from the data, let me provide a short tutorial on how to scrape information from the Internet.</p><p>Firstly, we have a look at the necessary libraries to be imported in Python:</p><p><strong>NOTE: I have used Python 3.6.5</strong></p><ul><li>requests</li><li>BeautifulSoup</li></ul><pre>import requests #for making HTTP requests in Python<br>from bs4 import BeautifulSoup # pulling data from HTML or XML files</pre><p>Next, we set up a query, which is our topic of interest for extracting the web pages.</p><pre>query = &quot;deep neural network&quot;</pre><p>Let us harness the power of <strong>requests</strong></p><pre>r = requests.get(&#39;<a href="https://www.google.com/search?q={}&#39;.format(query))">https://www.google.com/search?q={}&#39;.format(query))</a></pre><p>Now, we have a <a href="https://2.python-requests.org/en/master/api/#requests.Response">Response</a> object called r. We can get all the information we need from this object.</p><p><strong><em>NOTE: You might come up with an error as follows</em></strong></p><pre>IOPub data rate exceeded.<br>The notebook server will temporarily stop sending output<br>to the client in order to avoid crashing it.</pre><p>To solve this, refer this answer on<strong> stackoverflow:</strong></p><p><a href="https://stackoverflow.com/a/43420383/8385813"><strong>https://stackoverflow.com/a/43420383/8385813</strong></a></p><p>This is where <strong>BeautifulSoup </strong>comes in handy.</p><pre>soup = BeautifulSoup(r.text, &quot;html.parser&quot;)</pre><p>Before disclosing what <strong>soup </strong>stores, have a look at the image below</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/876/1*36mqdrJlNVlIcoD6_z438g.jpeg" /><figcaption>Top three results of searching “deep neural network” on Google</figcaption></figure><p>Moving on,<strong> soup </strong>variable stores the HTML code of the above web page.</p><pre>soup</pre><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5840944c62d74b0a6da8525e73273d74/href">https://medium.com/media/5840944c62d74b0a6da8525e73273d74/href</a></iframe><p>Pretty messed up, right? Let’s beautify this..</p><pre>print(soup.prettify())</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/871/1*cQCIEmMt2zwzeNA7EF7tAQ.jpeg" /></figure><p>In HTML, the &lt;a href&gt; attribute provides us with link for the web page. To obtain all such links, we run the following lines of code:</p><pre>links = []<br>for item in soup.find_all(&#39;a&#39;):<br>    links.append(item.get(&#39;href&#39;))</pre><p><strong>For this article, our aim would be to extract all the links for the first search page only.</strong></p><p>The links to third-party webpages, which appear similar to those in the image above, start with the following characters, “/url?q=”, so we need to filter out such strings.</p><p>Code for the above task is as shown below:</p><pre>final = []<br>for item in links:<br>    str = item[0:7]<br>    if str==&quot;/url?q=&quot;:<br>        final.append(item)</pre><p>This is what variable <strong>final </strong>stores:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/49ad658624f41b06c94d88f8c56ad6c9/href">https://medium.com/media/49ad658624f41b06c94d88f8c56ad6c9/href</a></iframe><p>Let’s assume we want to access all the &lt;p&gt; attributes from the first web page and concatenate them into one single string <strong>text</strong>. The following lines of code achieves it</p><pre>webpage1 = requests.get(&#39;<a href="https://www.google.com/&#39;">https://www.google.com/&#39;</a> + final[0]) #final[0] refers to the first web page link<br>webpagetext = BeautifulSoup(webpage1.text, &quot;html.parser&quot;)<br>all_p = webpagetext.find_all(&#39;p&#39;)<br>text = &quot;&quot;<br>for item in all_p:<br>    text = text + item.get_text()<br>print(text)</pre><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/38db404adc7d7189555a2b1abc650cd2/href">https://medium.com/media/38db404adc7d7189555a2b1abc650cd2/href</a></iframe><p>This text may contain a lot of unnecessary matter such as white spaces, special characters etc. which we may not need to extract any information. Techniques to handle them will be covered in the next tutorial.</p><p>Find the Part 2 of this tutorial below:</p><p><a href="https://medium.com/analytics-vidhya/information-retrieval-part-2-simplifying-the-information-53880b930ebd">Information Retrieval (Part 2): Simplifying the Information</a></p><p>The entire code for this article is published at the following link:</p><p><a href="https://github.com/arnabsinha99/MListheroxx/blob/master/Mini_Projects/WebPageExtraction/Extract.py">arnabsinha99/MListheroxx</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a9d0b715535d" width="1" height="1" alt=""><hr><p><a href="https://medium.com/analytics-vidhya/information-retrieval-part-1-extracting-webpages-a9d0b715535d">Information Retrieval (Part 1): Extracting webpages</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>
        <item>
            <title><![CDATA[Momentum: A simple, yet efficient optimizing technique]]></title>
            <link>https://medium.com/analytics-vidhya/momentum-a-simple-yet-efficient-optimizing-technique-ef76834e4423?source=rss-68abfb18d394------2</link>
            <guid isPermaLink="false">https://medium.com/p/ef76834e4423</guid>
            <category><![CDATA[neural-networks]]></category>
            <category><![CDATA[statistics]]></category>
            <category><![CDATA[gradient-descent]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[optimization]]></category>
            <dc:creator><![CDATA[Arnab Sinha]]></dc:creator>
            <pubDate>Sun, 23 Jun 2019 05:12:34 GMT</pubDate>
            <atom:updated>2019-07-18T08:04:33.980Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*jcyA66HdQsLDEswE" /></figure><p><strong>Prerequisites:</strong> Basic understanding of neural networks and loss functions</p><h4>INTRODUCTION</h4><p>In today’s world, a world that is advancing <strong>exponentially </strong><em>(mind this word, gonna come in handy ahead), </em>you definitely want to be updated with the latest activities, be it sports, news, technology, music, etc. However, current technologies would still not function if not for the basic components that made them possible. Smartphones without transistors.. eh?</p><p>A similar analogy can be made to one of the most popular optimization techniques that is used in quite many State Of The Art deep learning models. Before we dive into Momentum, we will have a brief look into a few other topics which you would need to understand before we study Momentum.</p><h4>1. GRADIENT DESCENT</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/411/1*MuNyVyxnhLZFJ6fxxMrKRw.jpeg" /><figcaption>Loss function for Mean Squared error</figcaption></figure><p>Let us say we have a training data set of <strong>n </strong>training examples and a given model which has to be trained. Let us assume a loss function L with parameters y and y with a hat. An example of a loss function is given above in the image, where mean squared error is used as a loss function. y is the result of the hypothesis function <em>h(W) </em>and represents the actual labels of the training data set and y with a hat represents the output that we obtain from the model when trained on the data set.</p><blockquote><strong>Loss function is pretty much the bread and butter in learning models. In statistics, typically a loss function is used for </strong><a href="https://en.wikipedia.org/wiki/Parameter_estimation"><strong>parameter estimation</strong></a><strong>, and the event in question is some function of the difference between estimated and true values for an instance of data.</strong></blockquote><p>Training a model usually begins by setting the weights ( parameters ) of the model to some random initial values. As and when iterations pass, the weights are updated and optimized so as to minimize the loss. The formula for gradient descent for any j-th parameter is as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/217/1*BahkeK4NyQ5KAcJOvfW-MQ.jpeg" /></figure><p>α<strong> </strong>represents the learning rate of the gradient descent algorithm. It’s there to control how big of a step we’re taking each iteration. It is the most important hyper-parameter to tune when training neural networks.</p><p>The loss function is differentiated with respect the respective weight so as to get the gradient value of the loss function w.r.t. that weight. This allows us to update the weights in the optimal direction.</p><p>The value of <strong>m </strong>in the image can be 1, in which case it is called Stochastic Gradient Descent ( updating the weights on each training example) or any number <strong>&gt;1 and ≤n</strong>, in which case it is called Batch Gradient Descent(training the weights once per set of m training examples).</p><h4>2. SIMPLE MOVING AVERAGE</h4><p>If we have a sequence <strong>V </strong>having <strong>n</strong> elements, then the simple moving average is defined as :</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/203/1*I25nL5wr7WBRO1hexW5rVQ.jpeg" /></figure><h4>3. EXPONENTIAL MOVING AVERAGE</h4><p>Now let us take another sequence <strong>S</strong> with <strong>n</strong> elements. The exponential moving average defines a new sequence <strong>V </strong>as :</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/261/1*YV-w1uOZGgzfh-5mvHg8kw.jpeg" /><figcaption>V — New sequence. S — original sequence.</figcaption></figure><p>Here β is called the <strong>smoothing constant</strong>. This is how the new sequences’ terms pan out:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/326/1*7ftz8UwKUvNUHKE3PJtZtQ.jpeg" /></figure><p>On solving a bit more,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/587/1*Lw1SnkwJM0M-l3ki6vQJuw.jpeg" /></figure><p>From this equation we see, that the value of <em>Tth </em>number of the new sequence is dependent on all the previous values <em>1..t</em> of the original sequence S. All of the values from S are assigned some weight. This weight is β to power of <em>i </em>multiplied by <em>(1- </em>β<em>)</em> for <em>(t — i)</em>th value of S. Because beta is less than 1, it becomes even smaller when we take β to the power of some positive number. So the <strong>older values of S get much smaller weight</strong> and therefore <strong>contribute less</strong> for overall value of the current point of V. The <strong>recent values of S get higher weight </strong>and<strong> contribute more</strong> to the current value of V.</p><h4>4. MOMENTUM</h4><p>We’ve defined a way to get ‘moving’ average of some sequence, which changes alongside with data. How can we apply this for training neural networks ?</p><p><strong>They can average over our gradient values. </strong>Let me explain about how momentum works and why it works.</p><p>So, gradient descent does not exactly provide us with the direction in which the loss function is headed i.e. the derivative of the loss function. Therefore, we might not always be headed in the optimal direction. This is primarily because the earlier derivatives of the loss function act as a noise in the later stages of the updating the weights. This causes slow training and convergence.</p><p>Momentum technique helps us solve this issue of slow convergence. Consider a situation where a ball on a hilly terrain is trying to reach the deepest valley. If the slope of the hill at some stage is very steep, then the ball gains a lot of momentum and is able to pass through slight hills in its way. As the slope decreases the momentum and speed of the ball decreases, eventually coming to rest in the deepest position of valley.</p><blockquote>Exponential! Remember the name??</blockquote><p>The momentum technique modifies the Gradient Descent method by introducing a new variable <em>V </em>representing the velocity and a friction coefficient/smoothing constant β which helps in controlling the value of <em>V </em>and avoids overshooting the minima and simultaneously allowing faster convergence.</p><p>Recall the equation for Exponential Moving Average we discussed earlier. We can apply that equation along with Gradient Descent updating steps to obtain the following momentum update rule:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/339/1*-hF7uTQL8_u29uMDlFV6Jw.jpeg" /></figure><p>Another way to do it is by neglecting the (1- β) term, which is a less intuitive.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/290/1*Rbtp8gEmPbCzf2_loSeL1A.jpeg" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/144/1*j86pdyrG-4JqKiI3_ckzVQ.jpeg" /></figure><p>This is pretty much identical to the first pair of equation, the only difference is that you need to scale learning rate by <em>(</em>1- β<em>)</em> factor.</p><p>There are two major reasons why momentum works with gradient descent:</p><ol><li>Exponential moving average helps us to give more importance to the most recent values of the derivatives of the loss functions and can provide us a better estimate which is closer to the actual derivative than our noisy calculations.</li><li>Sometimes, loss functions tend to have a structure like this</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/816/1*x0_9l2EDmWXxkqCNxKoWfA.png" /><figcaption>Pathological curve: Image source: <a href="https://bit.ly/2NkbnF9">https://bit.ly/2NkbnF9</a></figcaption></figure><p>The bluish area represents a ravine like structure.</p><blockquote>Ravine is an area, where the surface curves much more steeply in one dimension than in another. Ravines are common near local minimas in deep learning and Gradient Descent has troubles navigating them.</blockquote><p>If at any iteration we enter this ravine region, the loss function may keep bouncing off the walls of the ravine like below. This region below is knows as a <em>pathological curvature</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*JbNREzP23UDRtUyY4FrDIg.jpeg" /></figure><p>Some may say “Why don’t you just decrease the learning rate?”</p><p>Well, it makes sense when you are approaching a minima, but think of a case where you are in a pathological curvature and you have a whole lot of distance to cover to reach the minima. This is where some momentum helps.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*fqE8GYHh7qzWaOHQTwVdmw.jpeg" /></figure><p>When the Gradient Descent reaches a point towards the middle phase of the ravine, the momentum technique helps recognize the recent derivatives and hence boost the direction of gradient descent in that way. In the above image, notice that each gradient update has been resolved into components along <em>w1</em> and <em>w2</em> directions. If we will individually sum these vectors up, their components along the direction <em>w1</em> cancel out, while the component along the <em>w2</em> direction is reinforced. In an update, that counts as the direction of <em>w2</em> being enhanced whereas zeroing out the <em>w1</em> component, resulting in moving faster towards the minima.</p><p>In practice, the value of momentum is usually initialized at around 0.5 and is slowly annealed to 0.9 and closer to it. I will be posting articles about practical simulations of momentum also.</p><h4>CONCLUSION</h4><p>The basic idea behind momentum to decrease the convergence time by accelerating Gradient Descent in a relevant and optimal direction. This technique is used in various types of Deep Neural Network models where noisy data must be reduced. To refer more into the detailed math, I suggest you refer the following article</p><p><a href="https://distill.pub/2017/momentum/">Why Momentum Really Works</a></p><h4>REFERENCES FOR ARTICLE</h4><p>[1] <a href="https://towardsdatascience.com/stochastic-gradient-descent-with-momentum-a84097641a5d">https://towardsdatascience.com/stochastic-gradient-descent-with- momentum-a84097641a5d</a></p><p>[2] <a href="https://blog.paperspace.com/intro-to-optimization-momentum-rmsprop-adam/">https://blog.paperspace.com/intro-to-optimization-momentum-rmsprop-adam/</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ef76834e4423" width="1" height="1" alt=""><hr><p><a href="https://medium.com/analytics-vidhya/momentum-a-simple-yet-efficient-optimizing-technique-ef76834e4423">Momentum: A simple, yet efficient optimizing technique</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>