<?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 Krishna Kumar Mahto on Medium]]></title>
        <description><![CDATA[Stories by Krishna Kumar Mahto on Medium]]></description>
        <link>https://medium.com/@krish.thorcode?source=rss-e1dae62fc758------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*lEUHOmkBQlLEHhLjTdqqVg.jpeg</url>
            <title>Stories by Krishna Kumar Mahto on Medium</title>
            <link>https://medium.com/@krish.thorcode?source=rss-e1dae62fc758------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sun, 22 Nov 2026 10:01:22 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@krish.thorcode/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[Reading Markdown Should Feel Like Reading]]></title>
            <link>https://medium.com/@krish.thorcode/reading-markdown-should-feel-like-reading-0b8a12cd257a?source=rss-e1dae62fc758------2</link>
            <guid isPermaLink="false">https://medium.com/p/0b8a12cd257a</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[markdown]]></category>
            <category><![CDATA[frontend-development]]></category>
            <category><![CDATA[ux-design]]></category>
            <category><![CDATA[documentation]]></category>
            <dc:creator><![CDATA[Krishna Kumar Mahto]]></dc:creator>
            <pubDate>Mon, 20 Jul 2026 07:31:21 GMT</pubDate>
            <atom:updated>2026-07-20T07:31:21.137Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*jE_EgPR69WfcwVlcefEroQ.png" /></figure><p>Markdown has quietly become the language of technical communication.</p><p>Project READMEs. Design documents. API documentation. AI-generated documentation. Personal notes.</p><p>We spend hours reading Markdown.</p><p>So here’s a question:</p><p><strong>Why do we spend so much time optimizing how we write Markdown, but so little time thinking about how we read it?</strong></p><p>That question stayed with me while I was working on documentation every day.</p><p>I realized the problem wasn’t Markdown itself.</p><p>It was everything surrounding it.</p><p>When you’re trying to understand a document, there are dozens of small distractions competing for your attention.</p><p>A split source/preview layout makes your eyes jump between two versions of the same document.</p><p>A row of inactive tabs keeps reminding you of documents you’re not reading.</p><p>An IDE surrounds the document with project files, terminals, debuggers, and everything else that belongs to software development — not reading.</p><p>Switching between “reading mode” and “editing mode” interrupts your flow when all you wanted to do was fix a sentence.</p><p>None of these things are particularly annoying on their own.</p><p>Together, they make reading feel like operating an editor instead of simply reading a document.</p><p>That led me to a different question.</p><blockquote><strong><em>What would a Markdown editor look like if it were designed around reading instead of writing?</em></strong></blockquote><p>I wasn’t interested in adding more features.</p><p>I wanted a simple design principle that could guide every decision.</p><blockquote><strong><em>Every feature should reduce distractions while reading Markdown.</em></strong></blockquote><p>That idea eventually became <strong>Easy Markdown Editor</strong>.</p><p>Instead of asking, “What feature should I add next?”, I started asking, “Does this make reading more focused?”</p><p>That changed almost every design decision.</p><h3>Reading and editing shouldn’t feel like two different activities</h3><p>When you’re reading a paragraph and notice something you’d like to improve, you shouldn’t have to stop reading and switch contexts.</p><p>That’s why editing happens directly in the rendered document.</p><p>You stay where your attention already is.</p><h3>Only show what’s relevant</h3><p>Imagine you’re reading two Markdown documents.</p><p>Why should eight other inactive tabs compete for your attention?</p><p>Easy Markdown Editor automatically collapses inactive tabs into a stack.</p><p>They’re still there when you need them.</p><p>They just don’t stay visible when they don’t need to be.</p><p>The goal isn’t to save screen space.</p><p>It’s to reduce visual clutter.</p><h3>The interface should step back</h3><p>When you’re reading, the document should be the primary focus.</p><p>Not the Markdown syntax.</p><p>Not the project tree.</p><p>Not the split panes.</p><p>Not the tabs.</p><p>The interface should quietly disappear into the background so the document can take center stage.</p><h3>This isn’t trying to replace your IDE</h3><p>I still write code in IntelliJ.</p><p>I still use VS Code.</p><p>They’re fantastic tools for software development.</p><p>Easy Markdown Editor has a different purpose.</p><p>It’s for the moments when the document itself is the work.</p><p>Whether that’s a README, a design document, AI-generated documentation, or personal notes, the goal remains the same:</p><p><strong>Make reading Markdown feel effortless.</strong></p><h3>Looking ahead</h3><p>One thing I didn’t realize when I started this project is that I wasn’t really building a collection of features.</p><p>I was building around a philosophy.</p><p>Every new idea now has to answer a simple question:</p><blockquote><strong><em>Does this help someone stay focused on the document?</em></strong></blockquote><p>If the answer is yes, it’s worth exploring.</p><p>If not, it probably doesn’t belong.</p><p>If this philosophy resonates with the way you work, I’d love to hear your thoughts.</p><p>You can explore the project here:</p><p><strong>👉 </strong><a href="https://easymarkdowneditor.com/"><strong>Easy Markdown Editor</strong></a></p><p>I’m especially interested in hearing about the little distractions you’ve noticed while reading Markdown. They might shape the next feature.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=0b8a12cd257a" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[One-Hot-Encoding, Multicollinearity and the Dummy Variable Trap]]></title>
            <link>https://medium.com/data-science/one-hot-encoding-multicollinearity-and-the-dummy-variable-trap-b5840be3c41a?source=rss-e1dae62fc758------2</link>
            <guid isPermaLink="false">https://medium.com/p/b5840be3c41a</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[artificial-intelligence]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[technology]]></category>
            <dc:creator><![CDATA[Krishna Kumar Mahto]]></dc:creator>
            <pubDate>Mon, 08 Jul 2019 20:45:16 GMT</pubDate>
            <atom:updated>2019-07-20T04:03:10.070Z</atom:updated>
            <content:encoded><![CDATA[<h4>This article discusses about the Dummy Variable Trap stemming from the multicollinearity problem</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*SzGy893zEtLrELatB8lO0w.jpeg" /></figure><p>So far, every new topic in Machine Learning I picked up had something which I had never seen before. But it wasn’t only the unseen topics, but the topics which I had gone through once had something which had slipped my head. Dummy Variable Trap is one of such details that I had completely forgotten that it exists until I went back to making a classifier 3–4 months before.</p><p>Before starting with the exact content on Dummy Variable Trap, here are a few terms that we need to be familiar with. Formal definitions can be googled, so I shall put down an informal description which should be enough for the context of this article.</p><h4>Categorical Variables</h4><p>Categorical variables are those which can take values from a finite set. For such variables, the values that they take up can have an intrinsic ordering (for e.g., <em>speed: {low, medium, high}</em>). Such variables are called as <em>Ordinal Categorical Variables</em>. On the other hand, some categorical variables may not have any intrinsic ordering (for e.g., <em>Gender: {Male, Female}</em>). Such categorical variables are called as <em>Nominal Categorical Variables.</em></p><p>If you are aware of the common practice of encoding categorical variables into numbers, you know that often it is suggested to get them <em>One-hot-encoded. </em>There are two reasons for that:</p><ol><li>Most Machine Learning Algorithms cannot work with categorical variables directly, they need to be converted to numbers.</li><li>Even if we find a way to directly work with categorical variables without converting them to numbers, our model shall get biased towards the language we use. For eg, in an animal classification task, if the labels are {‘rat’, ‘dog’, ‘ant’}, then using such a labelling method would train our model to predict labels only in English, which would put a linguistic restriction upon the possible applications of the model.</li></ol><p>In order to get around these, we can encode the categorical variable values to numbers as below:</p><h4>Case 1:</h4><p>The ordinal categorical variable Speed (as quoted above) can be encoded as:</p><p>{‘Low’: 1, ‘Medium’: 2, ‘High’: 3}.</p><h4>Case 2:</h4><p>For the animal classification task (quoted above) the label variable, which is a nominal categorical variable can be encoded as:</p><p>{‘rat’: 1, ‘dog’: 2, ‘ant’: 3}.</p><blockquote>Let’s discuss case 2 first:</blockquote><p>There is one major issue with this- the labels in the animal classification problem should not be encoded to integers (like we have done above) since that would enforce an apparently incorrect natural ordering of: <em>‘rat’ &lt; ‘dog’ &lt; ‘ant’. </em>While we understand no such ordering really exists and that the numbers 1, 2 and 3 do not hold any numerical ordering in the labels we have encoded, our Machine Learning model will not be able to <em>intuitively understand </em>that. If we feed these numbers directly into a model, the cost/loss function is likely to get affected by these values. We need to model this understanding of ours mathematically. One-hot-encoding is how we do it.</p><blockquote>Case 1:</blockquote><p>Speed is an ordinal variable. We may argue that the relation: <em>‘low’&lt; ‘medium’&lt;‘high’ </em>makes sense and therefore, using labels 1, 2 and 3 should not be an issue. Unfortunately it is not so. Using labels as 100, 101 and 300000 in place of 1, 2 and 3 would still have the same relationship as ‘<em>low</em>’, ‘<em>medium</em>’ and ‘<em>high</em>’ have. There is nothing special about using 1, 2 and 3. In other words, we do not know how greater is a speed of <em>‘medium’ </em>than a speed of ‘<em>low’</em> and how small it is compared to a <em>‘high’</em> speed. Difference between these labels can potentially affect the model we train. So, we might want to one-hot-encode the variable <em>‘speed’</em> as well.</p><blockquote><strong>At this point, I hope we understand what categorical variables are all about, and why we would like to one-hot-encode them.</strong></blockquote><h4>Multicollinearity</h4><p>Multicollinearity occurs when two or more independent variables (a.k.a. features) in the dataset are correlated with each other. There are several methods using which we can measure the degree and direction of correlation for bivariate cases (<a href="https://www.statisticssolutions.com/correlation-pearson-kendall-spearman/">more information</a> on measures of correlation), while multicollinearity is generally measured using Variance Inflation Factor (<a href="https://ebrary.net/1025/economics/measuring_degree_multicollinearity">more information</a> on measures of multicollinearity). In a nutshell, multicollinearity is said to exist in a dataset when the independent variables are (nearly) linearly related to each other.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/533/1*QzntxP5CA_aA4ulhk47UrQ.png" /><figcaption>Fig. 1. Perfect Multicollinearity (perfect linear dependence between x_i and other independent variables)</figcaption></figure><p>Cases like as shown in Fig. 1. are called Perfect Multicollinearity. Likewise, we also have cases of Imperfect Multicollinearity, in which one or more highly linear relationships may be of our concern. These directly impact the linear regression analysis (refer to<a href="http://www.sfu.ca/~dsignori/buec333/lecture%2016.pdf"> these lecture notes</a> for more information on this). However, we shall be discussing their impact from the point of view of any general Machine Learning algorithm.</p><blockquote><strong>At this point, I hope we understand what multicollinearity is.</strong></blockquote><h4>OneHotEncoding in Python</h4><p>Before we move on to the final part of this article, let us have a look at how we can encode categorical variables.</p><p>One-hot-encoder returns a vector for each unique value of the categorical column. Each such vector contains only one ‘<em>1</em>’ while all other values in the vector are ‘0’ (find fig. 4 below), so the name <em>one-hot</em>-encoder.</p><p>Probably, there should be packages in the language of your choice as well, but since I have been using Python for all Machine Learning and Data Science related stuffs, I am including snippets from Python console only. In the following discussion, I shall quote Python’s <em>pandas </em>library<em> </em>by its popular nickname, <em>‘pd’ </em>and <em>numpy </em>as ‘<em>np’.</em></p><p>I am using a self-made <em>pd.DataFrame</em> object that looks like:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/220/1*vMj25ML52Zkw42fFd61wWQ.png" /><figcaption>Fig. 2. An example pandas.DataFrame object</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/211/1*ECq3bALKJKcjNzhkL3ohKQ.png" /><figcaption>Fig. 3. Datatypes of respective columns</figcaption></figure><p>‘<em>speed</em>’ is a categorical variable, while the ‘<em>numerical</em>’ column is a non-categorical column.</p><p>Let’s assume that we are working on a project and we decide to one-hot-encode the column ‘speed’.</p><p><strong>Method 1: pd.get_dummies</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/460/1*P1PnX99WypMhi4zllbLBoA.png" /><figcaption>Fig. 4. pd.get_dummies returns a dataframe with one-hot-encoded columns</figcaption></figure><p><em>pd.get_dummies </em>(<a href="https://pandas.pydata.org/pandas-docs/stable/reference/api/pandas.get_dummies.html">documentation</a>)<em> </em>returns a new dataframe that contains one-hot-encoded columns. We can observe that not all the columns were encoded. This is because, if no columns are passed to <em>pd.get_dummies</em> so as to tell which columns to one-hot-encode, by default it takes the columns with data-type <em>‘object’. </em>It then encodes them and returns a new dataframe with new columns that replace the old categorical column<em>. </em>In fig. 3, we can see that ‘speed’ column is of type ‘<em>object</em>’. Fig. 4. shows that this column does not exist anymore in the returned dataframe and has been replaced by new columns. We can also observe that ‘<em>low</em>’ has been mapped to a vector: <em>low -&gt;</em> <em>[0, 1, 0] , </em>and similarly,<em> medium -&gt; [0, 0, 1] </em>and <em>high -&gt; [1, 0, 0]</em>. Notice that each vector has only one ‘1’ in it. Also notice that each vector is 3-dimensional. This is because ‘<em>speed</em>’ has three unique values. In fact, the number of dimensions of the one-hot vectors is equal to the number of unique values that the categorical column takes up in the dataset. Here, encoding has been done so that 1 in the first place of a vector means ‘<em>speed=high</em>’, 1 in the second plae means ‘<em>speed=low</em>’ and so forth.</p><p><strong>Method 2: sklearn.preprocessing.OneHotEncoder</strong></p><p>I prefer using <em>sklearn.preprocessing.OneHotEncoder</em> instead of <em>pd.get_dummies </em>This is because <em>sklearn.preprocessing.OneHotEncoder </em>returns an object of <em>sklearn.preprocessing.OneHotEncoder </em>class. We can fit this object on the training set and then use the same object to transform the test set. On the other hand, <em>pd.get_dummies </em>returns a dataframe with encodings based on the values in the dataframe we pass to it. This might be good for a quick analysis, but for an extended model building project where you train on training set and will be later testing on a test set, I would suggest using <em>sklearn.preprocessing.OneHotEncoder</em>.</p><p>Using <em>sklearn.preprocessing.OneHotEncoder</em> is not as straightforward as using <em>pd.get_dummies</em>. We can see this in fig. 5 below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/585/1*K3swJ4ws6gnVest-8iDi6w.png" /><figcaption>Fig. 5. One-hot encoding using sklearn.preprocessing.OneHotEncoder</figcaption></figure><p>You may have observed that we first did integer-encoding of categorical column using the <em>LabelEncoder. </em>This is because the <em>OneHotEncoder</em> requires the categorical columns to contain numerical labels. The <em>fit </em>as well as <em>transform </em>methods require <em>np.array </em>objects with shape <em>(m, n)</em> to be passed. Finally, <em>fit </em>method returns a <em>OneHotEncoder</em> object that is fitted on the data passed to it. The process is lengthy, but you end up with a fitted object, which can be used later on the test set. Scikit-learn comes with a combined version for the methods <em>fit </em>and <em>transform</em>- <em>fit_transform </em>that helps reduce a line or two from your code (<a href="https://scikit-learn.org/stable/modules/generated/sklearn.preprocessing.OneHotEncoder.html">see</a> documentation).</p><h4>Dummy Variable Trap</h4><p>The dummy variable trap manifests itself directly from one-hot-encoding applied on categorical variables. As discussed earlier, size of one-hot vectors is equal to the number of unique values that a categorical column takes up and each such vector contains exactly one ‘1’ in it. This ingests multicollinearity into our dataset. From the encoded dataset in fig. 4 (which is equivalent to the encoded dataset in fig. 5), we can observe the following linear relationship (fig. 6):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/618/1*xkERrG6tP8Wv_YzYCNZNtA.png" /><figcaption>Fig. 6. Perfect Multicollinearity after one-hot encoding</figcaption></figure><p>Fig. 6 is a case of perfect multicollinearity. The vectors that we use to encode the categorical columns are called ‘<em>Dummy Variables</em>’. We intended to solve the problem of using categorical variables, but got <em>trapped </em>by the problem of Multicollinearity. This is called the <em>Dummy Variable Trap.</em></p><p>As mentioned earlier, this directly impacts the linear regression analysis because linear regression assumes non-existence of multicollinearity in the dataset. However, it also poses some other problems in Machine Learning tasks. Let us say, we train a logistic regression model on the dataset. We would expect our model to learn weights for the following equation:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/223/1*LVkk4_gKCOlVHNfw6C4RUA.png" /><figcaption>Fig. 7. Sigmoid function</figcaption></figure><p>In particular, for the features we have in our dataset, following are the weights that logistic regression would learn:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/570/1*ZHYWCFE6jTn7FJFdgv-nRw.png" /></figure><p>And the feature vector <strong>X</strong> is:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/501/1*XIR_sCBL0Aqc3ilMn7jB6g.png" /></figure><p>Clearly, it is the power on the exponential function in the denominator of the sigmoid function that actually affects the value of <em>y_hat </em>and contains trainable weights. This expression actually expands to:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/482/1*uimN_8A98hAciqF3NSduLQ.png" /><figcaption>Equation- 1: Expanding the power term in sigmoid function</figcaption></figure><p>From the relationship in fig. 6, we can express any one of the three independent variables in terms of the other two, let us take <em>speed_low</em> in LHS and express it in terms of <em>speed_medium</em> and <em>speed_high:</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/505/1*0CkqTWisO4IVRRT9Sx6BSg.png" /><figcaption>Equation-2: Expressing speed_low in terms of speed_medium and <em>speed_high</em></figcaption></figure><blockquote><strong>Why is it bad?</strong></blockquote><p>As we discussed earlier, this has a direct implication on a linear regression problem. What follows is, therefore, a summary of issues that is general to all algorithms.</p><ol><li>We can substitute <em>speed_low </em>in equation-1 with its value in equation-2. This actually means that (atleast) one of the features we are working with is redundant- that feature could be any one of the three, since equation-2 could be written with any one of them in the LHS. So, we are making our model learn an additional weight which is not really needed. This consumes computational power and time. This also gives an optimisation objective that might not be very reasonable and might also be difficult to work with. Too many independent variables may also lead to <a href="https://en.wikipedia.org/wiki/Curse_of_dimensionality">Curse of Dimensionalit</a>y. If multicollinearity also comes alongwith that, things become worse.</li><li>We not only want our model to predict well, but we also want it to be interpretable. For e.g., Logistic Regression is expected to learn relatively higher values for weights corresponding to relatively more important features. More important features have a greater impact on the final prediction. But if features are correlated, then it becomes hard to judge which feature has more “say” in the final decision because their values are actually dependent on one another. This affects the values of the weights. In other words, the weights not only get decided based on how an independent variable correlates to the dependent variable, they also get influenced by how independent variables correlate with one another. For e.g., if <em>speed_high </em>has higher values than others, then <em>speed_low</em> and <em>speed_medium</em> have to be lower so that the sum is always 1. Let’s assume that <em>importance(speed_high ) = importance(speed_medium) = importance(speed_low). </em>But since <em>speed_high </em>has higher values than the other independent variables, the learned weight corresponding to it will be much lower than the other two. In reality, we would want their respective weights to be (almost) equal.</li></ol><p>Since, one-hot-encoding directly induces perfect multicollinearity, we drop one of the columns from the encoded features. For e.g., we may choose to drop <em>speed_medium </em>in this case, but the choice is completely arbitrary.</p><p>Following is how we can handle this (dropping one of the encoded columns):</p><ol><li>When we use <em>pd.get_dummies</em>, we can pass an additional argument, <em>drop_first=True </em>(<a href="https://pandas.pydata.org/pandas-docs/stable/reference/api/pandas.get_dummies.html">documentation</a>) to drop the first new column that we get after encoding (a.k.a., the first dummy variable) (fig. 7):</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/368/1*CifsjXXH_gNR3TW-Hqci7w.png" /><figcaption>Fig. 7. drop_first=True</figcaption></figure><p>Compare the returned dataframe in fig. 7 with the output we got in fig. 4. We find that <em>speed_high</em> is dropped from the encoded dataframe. Not using <em>drop_first=True </em>will make sklearn use the default assignment for this parameter, which is <em>False</em>.</p><p>2. When we use <em>sklearn.preprocessing.OneHotEncoder </em>and want to drop one of the new columns, we pass the argument <em>drop=’first’ </em>constructor of <em>OneHotEncoder</em> class (<a href="https://scikit-learn.org/stable/modules/generated/sklearn.preprocessing.OneHotEncoder.html">documentation</a>).<strong><em> However this does not seem to support all the versions of sklearn (I got an error since my version of sklearn.preprocessing.OneHotEncoder does not support the ‘drop’ parameter), so you may have to update the python package before you can use it on your system</em></strong>. Although you can manually drop one of the dummy variables by manually writing one line or two (fig. 8), it may get difficult to keep track of the changes made to your dataframe in cases when you have more than one categorical columns and too many categories in each categorical column to work with.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/385/1*iMXiB8fmG5t8Y_nfoR_hcg.png" /><figcaption>Fig. 8. Manually dropping one of the dummy variables</figcaption></figure><p>The dataframe returned by <em>transform</em> (or, <em>fit_transform</em>) adds the new columns before all the other columns (fig. 8). So in order to drop the first column, we can use array-slicing as shown in fig. 8. However, doing this may become clumsy as already mentioned.</p><h4>Conclusion</h4><p>I hope this article was able to give a comprehensive description of Multicollinearity, One-Hot-Encoding and Dummy Variable Trap. The article is entirely based on my personal experience with facts taken from reliable sources (links already mentioned alongside each such concept). So, kindly comment below if you find any discrepancies in the article. Your feedback would help me write and describe better. Looking forward to hearing from you.</p><p>Thank you.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b5840be3c41a" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/one-hot-encoding-multicollinearity-and-the-dummy-variable-trap-b5840be3c41a">One-Hot-Encoding, Multicollinearity and the Dummy Variable Trap</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[Demystifying Maths of Gradient Boosting]]></title>
            <link>https://medium.com/data-science/demystifying-maths-of-gradient-boosting-bd5715e82b7c?source=rss-e1dae62fc758------2</link>
            <guid isPermaLink="false">https://medium.com/p/bd5715e82b7c</guid>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[gradient-boosting]]></category>
            <category><![CDATA[artificial-intelligence]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[mathematics]]></category>
            <dc:creator><![CDATA[Krishna Kumar Mahto]]></dc:creator>
            <pubDate>Mon, 25 Feb 2019 16:56:12 GMT</pubDate>
            <atom:updated>2022-07-20T08:01:00.339Z</atom:updated>
            <content:encoded><![CDATA[<h4>This article discusses the concepts behind the math of Gradient Boosting algorithm</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Lxa0ioMibcTreJNtKhtNDQ.jpeg" /></figure><h3>Introduction</h3><p>Boosting is an ensemble learning technique. Conceptually, these techniques involve: <strong>1. learning base learners; 2. using all of the models to come to a final prediction</strong>. Ensemble learning techniques are of different types and all differ from each other in terms of how they go about implementing the learning process for the base learners and then using their output to give out the final result. Techniques that are used in ensemble learning are Bootstrap Aggregation (a.k.a. Bagging), Boosting, Cascading models and Stacked Ensemble Models. In this article, we shall discuss briefly about Bagging and then move on to Gradient Boosting which is the focus of this article. There are a lot of sources which explain the steps in the algorithm of Gradient Boosting. But if you try finding a source that explains what does each step really do that makes the entire algorithm work, you probably will find articles which use <em>squared error </em>as an example to do so. Those explanations are very nice but the problem is that they focus so much on squared error that they almost fail to convey a <em>generalised</em> idea. Gradient Boosting is a generic model which works with any loss function which is differentialble, however, seeing it work with a <em>squared loss model</em> alone does not completely explain what it does during the learning process. In this article, I intend to explain the algorithm through a more generic approach.</p><blockquote><strong>Note: </strong>Base models are also referred to as base learners in literature. They are one and the same. However, I have used the term Base Learners for the base models and ‘Model’ for the function constituted by the base learners.</blockquote><h3>Bagging</h3><p>Bagging is a combination of two subsequent steps:</p><p>i. Bootstrap sampling of the dataset, into <em>M</em> subsets. Each one of these <em>M</em> subsets are then used to learn a model. These models are called as base learners/models.</p><p>ii. Taking a majority vote to declare the final prediction value.</p><p>Since in bagging, a subset of the dataset is used to train a base model, each of the base learners is likely to overfit (since each model has lesser examples to learn from, they may not generalise well). Taking majority vote is gives a model that has a variance which is the average of the variances of all base learners (figure 1).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/261/0*IbAEe3WKlDoIwX5a" /><figcaption>Fig. 1. Blue curve rerpesents the variance of the final model, all other curves are variances of the base learners (source: <a href="https://www.quora.com/What-does-Bagging-reduces-the-variance-while-retaining-the-bias-mean">https://www.quora.com/What-does-Bagging-reduces-the-variance-while-retaining-the-bias-mean</a>)</figcaption></figure><p>Boosting is quite different from Bagging in its approach of training base learners and using them to give final results. Bagging learns base learners from independently bootstrapped subsets of data, and hence we can train all the base learners simultaneously in a parallel environment. Boosting, on the other hand, trains the base learners sequentially- models are trained one after the other. Therefore, training base learners in parallel is impossible. Moreover, in a Boosting algorithm we start with a high bias model. The actual model is first initialised with a constant value. It is then progressively made less biased by adding base learners to it. We shall see how Gradient Boosting goes about learning a final model that has a much lower bias given an appropriate number of base learners.</p><h3>Gradient Boosting</h3><h4><strong>The idea of Additive modelling:</strong></h4><p>Additive modelling is at the foundation of Boosting algorithms. The idea is simple- form a complex function by adding together a bunch of simpler terms. In Gradient Boosting, a number of simpler models are added together to give a complex final model. As we shall see, gradient boosting learns a model by taking a weighted sum of a suitable number of base learners.</p><h4><strong>Gradient Boosting algorithm</strong></h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/889/1*3iojqS-gGsJ4XI6vajl69A.png" /><figcaption>Source: <a href="https://en.wikipedia.org/wiki/Gradient_boosting">https://en.wikipedia.org/wiki/Gradient_boosting</a></figcaption></figure><h4><strong>Pseudo-residuals</strong></h4><p>In the algorithm, step 2(1) mentions about computing ‘pseudo-residuals’. Although there is hardly any concrete conceptual definition of what a pseudo-residual is, but mathematically what is mentioned is how you define it. However, I feel the name is kind of borrowed from the difference <em>(y_actual - y_predicted) </em>which is often referred to as <em>residual error </em>which we get by taking a derivative of square loss function <strong><em>L </em></strong>w.r.t. the predicted value <strong><em>F(x_i) </em></strong>for <em>ith </em>example.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/338/1*Hnvlc-hCUdynYUjbEogrjw.png" /><figcaption>Fig.2. Negative of Derivative of squared loss w.r.t. hypothesis function gives the residual for ith example</figcaption></figure><p>In optimization problems, constants attached to objective functions do not affect the optimal points, so the factor of <em>‘2’ </em>as shown in figure 2 does not actually matter and can safely be dropped (only when we are solving for optimization). Probably no loss function differentiates to give residual, yet, in the case of squared loss, its differentiation gives a function that is closest to the <em>residual error ‘visually’</em>. May be the name has been borrowed from this. Nonetheless, <em>gradient boosting has nothing to do with the derivative of loss function w.r.t. hypothesis being equal to the residual error.</em></p><h4><strong>How the algorithm works</strong></h4><p>We may have got an idea of one of the things we do in gradient boosting - taking derivatives of the loss function w.r.t. the hypothesis function. Needless to say, the loss function has to be differentiable w.r.t. the hypothesis function. As the algorithm says, gradient boosting takes the training set and a loss function as inputs. We denote the final model that we shall get at the end of the algorithm by <strong><em>F_M(x)</em></strong>.</p><blockquote><strong>Notations</strong></blockquote><p>Some of the notations used in the algorithm taken from wikipedia (posted above) are somewhat inconsistent. So, I shall use my own notations for those variables.</p><p><em>F_M(x)</em>: Final model that will be learned by taking weighted sum of <em>M</em> base learners (additive modelling).</p><p><em>F_m(x)</em>: Model obtained by adding <em>m (=1, 2,…, m) </em>base learners and the initial constant value of <em>F_M(x)</em>.</p><blockquote><strong>Step 1.</strong> Initialise model with a constant value.</blockquote><p>We find a constant model <em>F_0 = γ </em>that fits to the actual y-values. Why a constant model? This is where the idea of boosting starts to manifest- going from a high bias to a low bias model. We start with a constant function (no other function can have more bias than a constant function, unless the dataset is so boring that even a constant model fits it) and then go on through a number steps finding a function that has a reasonably low bias. In some texts, you may find initialising the model with <em>0</em> (zero). That is also a constant function, but quite possibly we can start with a slightly better option. Let’s say the initial model is a constant function <em>γ. </em>The loss function for a constant function then is as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/153/1*YtQa-pT-P-InaOp-z9ffWg.png" /></figure><p>Therefore, <em>γ_optimal </em>is determined by the solving following optimization problem:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/399/1*s2B0a-4o5KKHGL8Da4m3fg.png" /></figure><p>This is for sure better than a model initialised with zero. Particularly for squared loss error, <em>F_0(x)</em> is equal to the mean of the actual <em>y-values</em>, i.e., <em>F_0(x) = y_mean </em>when<em> </em>squared loss is used<em>.</em></p><p>Often in texts, this model is not counted as one of the base learners although the final model is going to be an <em>additive model</em> obtained from base learners and this model will also be one of addends. There is one difference though- all the models that are called as base learners in the literature, are fitted on the pseudo-residuals and not on the <em>y-values </em>of the actual dataset (we shall see how it is done in step 2). Since <em>F_0(x)</em> is fitted on the <em>y-values</em>, probably that is why it is not considered as one of the base learners in the literature.</p><p>At this point <strong><em>F_M(x) = F_0(x). </em></strong><em>F_M(x), </em>however, is subject to updations until all the <em>M</em> base learners are added to it with suitable weights.</p><blockquote><strong>Step 2: </strong>This step is to be followed for each base learner from m = 1 to m=M. Note that gradient boosting adds one model at a time, one after the other.</blockquote><p>Gradient boosting algorithm has to be configured with a suitable value of hyperparameter <em>M (number of base learners) </em>prior to execution.</p><blockquote>Step 2.1. Compute pseudo-residuals:</blockquote><p>Pseudo-residuals are computed for each <em>ith </em>training example :</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/572/1*OS_oGwfScS97bi9XtY7SUw.png" /></figure><p>Note that <em>F_m-1(x)</em> is the model obtained by adding <em>m-1</em> weighted base learners and the initial constant function. The <em>m_th (m superscript th) base learner </em>has not yet been added. Each residual calculation <em>r_im </em>for <em>ith </em>training<em> </em>example corresponding to the current base learner <em>m </em>(which <strong>will be </strong>trained and added in step 2.2) is done on the weighted sum of base learners from <em>1 to m-1 </em><strong>and </strong>the initial constant function (step 1). Recall that after step 1, <em>F_0(x) = </em>γ does not include any term corresponding to any base learner (recall that <em>F_0(x) </em>is most often not called as a base learner in the literature. It is treated only as an initial value of the model).</p><p>At this point, we have computed the pseudo-residual values for each training example.</p><blockquote>Step 2.2. Fit <strong>base learners </strong>on the pseudo residuals</blockquote><p>For this step, a new dataset is derived from the given dataset. The dataset <em>D_modified </em>is defined as shown in figure 3.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/475/1*5GrC7HaskULAmbc73o2_Ag.png" /><figcaption>Fig. 3. Modified dataset</figcaption></figure><p>A base learner <em>h_m(x) </em>is trained and fitted on this dataset.</p><p>At this point, we have everything required to determine <em>F_m(x)</em>. We do it as following:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/467/1*3tf3bap74lsDXHZAgzomrQ.png" /></figure><p><strong>Why does doing this make sense?</strong></p><p>It is straightforward to see why this equation makes sense if we compare it with weight updations done in <em>Gradient Descent </em>(figure 4)<em>. </em>Weights in gradient descent are moved in the direction in which loss <em>L </em>decreases. How much the weights should be moved is governed by α (the learning rate). Similar to that, the function <em>h_m(x) </em>is fitted to the rate of change of loss <em>L </em>w.r.t. <em>F_m-1(x)</em>. The function <em>h_m(x) </em>(which is expected to approximate the behaviour of derivate of loss w.r.t. <em>F_m-1(x) </em>suitably) represents the direction in which the <em>loss function </em>decreases w.r.t. <em>F_m-1(x)</em>. γ corresponds to the hyperparameter α in terms of the utility (both determine by what amount update should be made). This is similar to the weight updation equation in Gradient Descent , except that γ is trainable while α is a hyperparameter. We shall see how an optimal value of γ is learned in step 2.3 .</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/169/1*WXi_GRASVILl02aGZfT74g.png" /><figcaption>Fig. 4. Weight updation in Gradient Descent</figcaption></figure><p>Note that γ is the only parameter w.r.t. which <em>F_m(x)</em> needs to be optimized on the original dataset. However, base learners learn more parameters on dataset <em>D_modified</em> since they are the actual functions which are added together to give the final model.</p><p>At this point, we have a model <em>F_m(x)</em> which will be used in the next step to compute <em>y_pred </em>values.</p><blockquote>Step 2.3. Find the optimum γ</blockquote><p>We shall take the the original dataset <em>D </em>(Figure 5)<em>.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/401/1*6mEPIzkxNlktXHFY6pzHJQ.png" /><figcaption>Fig. 5. Original dataset</figcaption></figure><p>We take the model <em>F_m(x) </em>on the original dataset<em> D, </em>then compute the loss <em>L. </em>Note that this loss is a function of <em>γ.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/189/1*8PhIBuDtt-WN0_HzR-AKdg.png" /></figure><p>We are supposed to find <em>γ_optimum</em>. This can be done by solving the following optimization problem that minimizes the :</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/670/1*gVT41gPIynmADLHzHm_0ew.png" /></figure><p>At this point we have the optimum value of <em>γ.</em></p><blockquote>Step 2.4. Model Updation</blockquote><p>The model <em>F_m(x)</em>, thus is obtained as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/455/1*TxGDAKlB344Fcvd5FmkIXQ.png" /></figure><p>At the end of each iteration number <em>m, F_M(x)</em> is updated to the value of <em>F_m(x)</em>.</p><p><strong>Step 3.</strong> Step 2 is run for each base model <em>m = 1 to M</em>. After <em>M</em> iterations of step 2, we obtain the final model <em>F_M(x).</em></p><h3>Why the name ‘Gradient Boosting’?</h3><p>We just saw the role ‘gradient’ plays in this algorithm- we always fit a base learner to the gradient of the loss function w.r.t. the model <em>F_m-1(x)</em>. The term ‘boosting’ refers to the fact that a high bias model, which performs really bad on the dataset, is boosted to finally become a reasonable classifier and possibly a strong classifier. In general, Boosting is a family of algorithms in which a number <em>‘weak classifier’ </em>(one which has an error rate of just under 0.5) base learners are combined to give a strong classifier (one which has an error rate close to 0). In gradient boosting, we start with a constant model (which maybe an extremely weak classifier depending on the dataset). At the end of an <em>m_th </em>iteration of learning a base learner, we end up with a weak learner, but relatively a better classifier <em>F_m(x) </em>which progressively moves towards becoming strong classifier.</p><h3>Footnotes</h3><p>I hope this article makes sense. My goal is not just to put down an algorithm, I intend to demystify the math (as title says) and bring forth what lies beyond the mathematical equations. So, if I failed to convey the conceptual ideas behind the math anywhere, kindly drop a comment, it would be really appreciable.</p><p>Thank you for reading!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=bd5715e82b7c" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/demystifying-maths-of-gradient-boosting-bd5715e82b7c">Demystifying Maths of Gradient Boosting</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[Demystifying Maths of SVM — Part 2]]></title>
            <link>https://medium.com/data-science/demystifying-maths-of-svm-part-2-30308a73e072?source=rss-e1dae62fc758------2</link>
            <guid isPermaLink="false">https://medium.com/p/30308a73e072</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[artificial-intelligence]]></category>
            <category><![CDATA[svm]]></category>
            <category><![CDATA[optimization]]></category>
            <dc:creator><![CDATA[Krishna Kumar Mahto]]></dc:creator>
            <pubDate>Wed, 06 Feb 2019 15:03:42 GMT</pubDate>
            <atom:updated>2019-02-06T15:19:31.598Z</atom:updated>
            <content:encoded><![CDATA[<h3>Demystifying Maths of SVM — Part 2</h3><h4>This article discusses why slack variables were introduced into the optimization objective of SVM</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*GBAal2Aeq8k2iAAH8Z2DQw.jpeg" /></figure><p>After paddling through K-NN, Naive Bayes’ Classifier, Logistic Regression and Linear Regression along a rather flat curve, SVM came and affected a sharp dip on it. Having derived the optimization objective of SVM for linearly-separable dataset (I have thoroughly described the derivation in my <a href="https://towardsdatascience.com/demystifying-maths-of-svm-13ccfe00091e">previous article</a>, which is the part-1 of this mini series), the next halt came with the ‘slacked’ SVM. In this article, we shall go through step-by-step derivation with detailed discourse about each step.</p><blockquote><strong>Note</strong>: This article is in continuation of my previous article- <a href="https://towardsdatascience.com/demystifying-maths-of-svm-13ccfe00091e">Demystifying Maths of SVM</a>. Reiterating all the terms and concepts that are fundamental blocks to both the linearly classifiable as well as non-linearly classifiable datasets would be redundant as the same have already been explored in the first part of this article. So, I would suggest that if some topics or terms feel unfamiliar, do have a look at that article as well.</blockquote><h3>Let’s begin …</h3><blockquote><strong>SVM hypothesis</strong></blockquote><p>Hypothesis, w.r.t. a machine learning model, is the model itself, which is the classifier (which, is a function) we intend the machine to learn.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/302/1*g_hK-9_x7OUBt6xlERkKmQ.png" /><figcaption>g(z) = 1 if z ≥ 0, -1 otherwise</figcaption></figure><blockquote><strong>Class labels</strong></blockquote><p>In SVM, the class labels are denoted as -1 for negative class and +1 for positive class.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/123/1*7fCpZ0RnHkZFODUPrwxuLA.png" /></figure><blockquote><strong>Optimization problem</strong></blockquote><p>The optimization problem that we shall have finally derived at the end of this article and what SVM solves to fit the best function is:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/581/1*aYRUVXZPSxqPsHJQS-NcpQ.png" /><figcaption>Expression 1: Optimization problem for SVM for dataset which is not linearly separable</figcaption></figure><blockquote><strong>Notations:</strong></blockquote><ol><li><em>(</em><strong><em>w</em></strong><em>, b)</em><strong><em> </em></strong>together notate a hyperplane- <strong><em>w </em></strong>is the vector normal to the hyperplane, and <em>b =</em> <strong><em>w</em></strong><em>_T * x0 (w_T is transpose(w)) </em>where <em>x0</em> is a point on the hyperplane.</li><li><em>C </em>is a constant. <em>ξ_i </em>(Greek symbol called <em>Xi, subscripted</em> with <em>i</em>) has been used to relax the condition.<em> </em>The article revolves around these two terms.</li><li><em>x(i)</em> (x <em>superscripted</em> with (i)) is <em>i</em>th training example. Throughout this article, we use <em>m </em>to denote the number of examples in the training set.</li></ol><p>For reference, here is how the optimization problem of SVM for linearly separable dataset looks like:</p><figure><img alt="" src="https://cdn-images-1.medium.com/proxy/0*5nbgaf6vF2GVAI4v.png" /><figcaption>Expression 2: SVM optimization objective when dataset is linearly separable</figcaption></figure><blockquote><strong>Terms that the readers are expected to be familiar with:</strong></blockquote><ul><li><strong>Functional margin</strong></li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/306/1*_eg1nU3usiIdg-mb_o6SIg.png" /><figcaption>Functional margin of a hyperplane w.r.t. ith example (denoting as gamma-hat superscripted with (i))</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/236/1*copyuwUxqFB1KGkLE0KkoQ.png" /><figcaption>Functional margin of a hyperplane w.r.t. the entire dataset</figcaption></figure><ul><li><strong>Geometric margin</strong></li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/371/1*-dePsCMUKmF6ZqOlCausFQ.png" /><figcaption>Geometric margin w.r.t. ith training example (denoted as gamma superscripted with (i))</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/228/1*hvIZSrg1JTak2BO_9Sp72w.png" /><figcaption>Geometric margin of hyperplane w.r.t. the entire dataset</figcaption></figure><p>Visit my <a href="https://towardsdatascience.com/demystifying-maths-of-svm-13ccfe00091e">previous article</a> to have a better context on these terms.</p><h4>Brief on how SVM algorithm works, what it aims at achieving (interpreting SVM conceptually)</h4><p>Just to make sure we are on the same page, lets discuss how SVM works. There are two ways SVM is interpreted:</p><p>First,</p><blockquote>SVM maximizes the margin (as drawn in fig. 1) by learning a suitable decision boundary/decision surface/separating hyperplane.</blockquote><p>Second,</p><blockquote>SVM maximizes the geometric margin (as already defined, and shown below in figure 2) by learning a suitable decision boundary/decision surface/separating hyperplane.</blockquote><h4>Is the current formulation of SVM good enough?</h4><p>In the <a href="https://towardsdatascience.com/demystifying-maths-of-svm-13ccfe00091e">previous article</a>, we had derived the optimization problem of SVM from scratch. We reached at the following expression:</p><figure><img alt="" src="https://cdn-images-1.medium.com/proxy/0*5nbgaf6vF2GVAI4v.png" /><figcaption>Optimization problem that the SVM algorithm solves</figcaption></figure><p>It turns out that this optimization problem can learn a <em>reasonable </em>hyperplane only when the dataset is (perfectly) linearly separable (fig. 1). This is because of the set of constraints that defines a feasible region mandating the hyperplane to have a functional margin of atleast 1 w.r.t. each point (values of <strong><em>w</em></strong> and <em>b </em>are to be learned such that functional margin becomes 1. Domain of any hyperplane which has a positive functional margin falls in the feasible region since <strong><em>w </em></strong>and <em>b</em> could simply be scaled to give a functional margin of 1 while still keeping the hyperplane unchanged. However, only some particular (<strong><em>w*</em></strong>, <em>b*</em>) hyperplane can optimize the objective function in the feasible region).</p><figure><img alt="" src="https://cdn-images-1.medium.com/proxy/1*SgXnNjy8aXR-6ZwaPek0xg.png" /><figcaption>Fig. 1. Dashed lines are the margins to the hyperplane (drawn in solid); dataset is linearly perfectly separable</figcaption></figure><p>Therefore, no such hyperplanes can ever be considered during optimization which have a negative functional margin (figure 2) with repsect to any example. A negative functional margin is still an extreme event that the current optimization problem avoids. Apart from this, a separating hyperplane like the dotted yellow one as shown in figure 3, is also not possible. As we can see (figure 3), the blue hyperplane stands more towards the red examples, and is far away from the collection of green examples because of a noise in the dataset. A hyperplane that looks more like the yellow one, although might appear to be doing a better job in forming a decision boundary, it does not fall in the feasible region of the current optimization problem.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/414/1*m2bvHKW8ooa413UqUYbe3w.png" /><figcaption>Fig 2. The thicker hyperplane in dark blue is learnt on the feasible region, although the thin, grey hyperplane is apparently better</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/471/1*fWqTc7-xWYMT2RtKA205Fg.png" /><figcaption>Fig 3. In the current setting, SVM may learn a hyperplane like the one shown in blue.</figcaption></figure><p>From this, we can also easily derive the fact that situations where points lie on the hyperplane itself are also not possible. Furthermore, the feasible region may be empty, in which case SVM completely fails to classify the examples. Figure 4 depics a situation where SVM cannot learn any separating hyperplane with the current set up.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/364/1*uknS66giCNri1oPvqStiRQ.png" /><figcaption>Fig 4. No separating hyperplane is possible</figcaption></figure><p>Seemingly, the current formulation of SVM is not robust, and any <em>natural </em>dataset is likely to make it of less to no use (because natural datasets are rarely linearly separable). This configuration of SVM is called as <strong><em>Hard-margin SVM</em></strong><em>, </em>signifying the fact that it has a very strict constraint.</p><p>Before starting with the next section, I would like to reiterate the fact that the name represents SVM’s stringency to learn a decision surface under a set of <em>strict </em>constraints giving off a feasible region that remains <em>invariable</em> w.r.t. the training examples. Recall that the constraints represent a feasible region wherein all hyperplanes have a positive functional margin w.r.t. all data points with emphasis on learning scaled values of <strong><em>w </em></strong>and <em>b </em>(for the same hyperplane) so that functional margin is 1.</p><h3>Introducing slack</h3><p>In order to become a better classifier, SVM has to have more lenient constraints so that in the feasible region hyperplanes can be allowed to have a functional margin less than 1. To allow this to happen, a slack variable is introduced to each of the constraints of the optimization problem:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/505/1*q-DhKyObd8fn2GkkDpyeHw.png" /></figure><p><strong><em>‘ξ’ </em></strong>is the slack variable vector of <em>ξi’s (ξ </em>subscripted with <em>i)</em>. We define <em>ξi </em>for each example in the dataset. Each of its elements has to be atleast zero to really allow some points to have a functional margin less than or equal to 1(the second inequality in the above expression). It has a different value for each example in the training dataset and therefore, a hyperplane may have different minimum requirement for the values of functional margin for different points. This also allows the hyperplane to have a functional margin of less than 1 w.r.t. some data points.</p><p>The optimization problem thus, has become:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/597/1*dRhz04nzeEYg04nfLhBG6Q.png" /></figure><p>This means, we can now be more hopeful to get a separating hyperplane as the one shown below as yellow dotted line in figure 2.</p><blockquote><strong>Does the new optimization problem we have arrived at express what we think it should?</strong></blockquote><p>In the <a href="https://towardsdatascience.com/demystifying-maths-of-svm-13ccfe00091e">previous part of this article</a>, we established that the optimization function corresponds to maximizing the geometric margin (Maximizing geometric margin in itself is a non-convex optimization problem, so we systematically reduced the maximization of geometric margin problem to an equivalent convex minimization problem). So, the optimization objective says “Maximize the geometric margin subject to the given constraints.” From the constraints, we can observe that since <em>ξi </em>can contain any non-negative values, it can take arbitrarily large, positive value for an example. This means functional margin of the hyperplane w.r.t. a point can be any value less than 1, and even negative. This means a hyperplane can make wrong classifications (in the <a href="https://towardsdatascience.com/demystifying-maths-of-svm-13ccfe00091e">first part</a> of this article, we discussed a negative functional margin w.r.t. a point implies the point has been wrongly classified). Therefore, a hyperplane can have arbitrarily large value of geometric margin as it is free to get pushed anywhere. This is not a guarantee to get us a separating hyperplane!</p><p>Doing this may expand the feasible region in a way that can make us end up with a separating hyperplane that is worse.</p><blockquote><strong>Enter new objective</strong></blockquote><p>It turns out that we do have a nice choice. We add a new objective to our optimization problem as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/585/1*56bhf9L-2QLNaikUZy_UNw.png" /></figure><h3>The idea of Pareto optimality</h3><p>With the introduction of the second objective, the very first thing that can be noticed is the fact that now the optimization problem will not end up with just any value of <em>ξ</em>. The solution is no more as straightforward as it would have been with one objective. Irrespective of the context for which we intend to solve an optimization problem, it does not very often happen that the same point optimizes two or more objectives simultaneously. The instances of this can be seen everywhere. For e.g., for cars with similar specifications, as we look for higher speeds the handling is likely to go down. It is unlikely that both the speed (objective-1) and handling (objective-2) will have their best values at the same point (i.e., simultaneously). In other words, if we choose a car with the highest speed, then it is quite probable that it shall not have the best possible handling at the same point in the design (feature) space. The converse is true as well(figure 5). In this example, speed and handling are related in a way that if you increase one, then without any additional adjustments the other is likely to decrease. More generally, two functions which may not be having a meaningful relationship also are unlikely to have the same point of optimum.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/483/1*PrOyeeOp9eDIAVXh261lzQ.png" /><figcaption>Fig. 5. In red is the car with the highest speed (corresponding handling is not the best, it is likely to be the lowest as it is here) and in green is the car with best handling (corresponding speed is not the best, likely to be the worst as it is here).</figcaption></figure><p>This type of Multi Objective Optimization (MOO) problem is not unheard of. Idea of Pareto optimality [1] was introduced to formally address this issue. Pareto optimality defines Pareto optimal points. These points define an envelope called as Pareto front [2]. These points are found to be the best candidates for choosing an optimal point from for a given MOO problem. However, there can be many Pareto solutions for a given MOO problem. “Which one is the best?”- “No one is.”. It is impossible to say one point to be better than the other. We can see this evidently in figure 5- if one objective attains an optimum, the other does not necessarily be at its best value.</p><blockquote>Therefore, it is a matter of preference. How high would you like the speed to be? How good the handling should be?</blockquote><p>If it is desired to have a car of speed 70, then the problem is solved. The optimal values of (speed, handling) would then be (70, 30) (figure 5). No individual Pareto solution is universally optimum. <strong><em>User prefernce </em></strong>is needed to pick one out of all possible Pareto solutions.</p><h3>The final formulation</h3><p>With the introduction of one more objective to our optimization problem, we have got into a situation identical to the cars example discussed above. Recall that the first objective maximizes the margin. Given the constraints, the margin could be a large value. However, this corresponds to increasing <em>ξ </em>indefinitely so as to allow indefintely large and negative functional margin values. Conversely, decreasing <em>ξ</em> corresponds to a decreasing margin (ideally, we would want <em>ξ </em>to be a suitable vector of <em>ξi’s </em>so that a reasonable separating hyperplane is learned).</p><p>Consequently, Pareto optimality is used to describe the solutions to this MOO problem.</p><blockquote><strong>SVM and Pareto optimality</strong></blockquote><p>One of the methods used to solve MOO problems is the <em>weighted-sum method. </em>This method allows to add user preference into the optimization objectives. For SVM, we would like to learn how can we include our preference for a hyperplane that correctly separates more points (a lower value of <em>ξ </em>is more desirable than a greater value of margin), or a hyperplane with greater margin (a greater value of margin is preferred over a lower value of <em>ξ</em>) in the form of weights.</p><p><em>Expression 1</em> is the final formulation of optimization problem of SVM. The constant <em>c≥0</em> is there to account for user preference to identify a single suitable solution from the many Pareto optimal solutions. A suitable value of <em>c </em>should be used if the preference is to learn a hyperplane that does the most reasonable separation on the training set. A relatively larger <em>c </em>would mean that we are incorporating more preference to the <em>sum_of_ξi </em>terms, which means we shall get a more optimal value for it and a less optimal value for the <em>||w||²</em>.</p><blockquote><strong>How do weights account for user preference, and how does it influence the optimal points?</strong></blockquote><p><strong><em>Part 1</em></strong><em>: How user preferences map to weights?</em></p><p>Let us now comprehend how do the weights describe preference for a particular objective function. For notation convenience, we shall write the two objective functions as given below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/192/1*gBdLh-EVeogt-GuNVJG8-A.png" /></figure><p>Our optimization problem is then (not writing the constraints, nonetheless they must hold),</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/297/1*pxSPHw46LTFZ8kIZ9yN0ug.png" /></figure><p>which translates to:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/97/1*KjlLgJHtsovQO4PksuYM4Q.png" /></figure><p>This optimization problem with multiple objectives can be restated as an optimization problem with single objective. The single objective is the weighted sum of the individual objective functions and is often called as <em>Utility function </em>[3]:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/304/1*yTmmwJL84UTlQkFbAFoatA.png" /><figcaption>Equation — 1</figcaption></figure><p>The weights <em>w1</em> and <em>w2</em> are always taken to be positive. At this point, it is still not clear how weights correspond to user preferences. Also, note that the user preferences are relative to each other and hold meaning only locally for the given problem.</p><blockquote>Note that <em>if the optimization problem is convex and the weights are positive</em>, then it is ensured that solving the weighted sum function gives a solution which is pareto optimal [3].</blockquote><p>We could represent user preferences for the objectives as a mathematical function. Needless to say, the preference function would be a function of <em>f1 </em>and <em>f2. </em>Let’s call it <em>P(f1, f2)</em>.<em> </em>The gradient of <em>P(f)</em> would then be:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/372/1*T_rsrstvj7PdepdCScNPtw.png" /><figcaption>Equation — 2</figcaption></figure><p>Equation-2 is the total derivative of Preference function (for more on total derivative I would suggest you read the first answer on this <a href="https://math.stackexchange.com/questions/174270/what-exactly-is-the-difference-between-a-derivative-and-a-total-derivative">stackexchange</a> post).</p><p>The gradient of the utility function (equation- 1) is:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/357/1*lczFDwxFNam1Akcyjae9TA.png" /><figcaption>Equation — 3</figcaption></figure><p>Each component of Equation-2 represents the rate of change of preference of a user with a change in design point value (on which functions <em>f1</em> and <em>f2 </em>are defined).</p><p>Comparing <em>Equation-2</em> and <em>Equation-3 </em>suggests that if <em>w1 </em>and <em>w2 </em>are selected properly, then the gradient of utility function can become parallel to the gradient of the preference function. Simply put, the rate of change of the utility function should approximate the rate of change of user preferences. As preferences are locally significant and are relative to each other, so talking about how preferences change w.r.t. design points makes sense while deliberating upon <em>w1</em> and <em>w2 </em>representing preferences in some absolute sense is immaterial (because preferences themselves are not defined absolutely/universally). <strong><em>A choice of appropriate weights can make the gradient of utility function parallel to that of the preference function.</em></strong></p><p><strong><em>Part 2</em></strong><em>- How the weights influence optimal points?</em></p><p>The utility function, <em>U</em> has an optimum value</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/261/1*__ofp9MSTFJSZWhsmTToGA.png" /></figure><p>If one of the weights say, <em>w2</em>, is significantly greater than <em>w1</em> then each partial derivative of <em>f1</em> will be much greater than partial derivative of <em>f2 </em>(since LHS = RHS ). For a convex function, this corresponds to points where <em>f1</em> has much higher values as compared to <em>f2</em>. Similar arguments explain how it would work out to be when <em>w1</em> is much greater than <em>w2</em>.</p><h3>Conclusion</h3><p>In SVM, a single constant <em>c </em>is used instead of two weights because of the same reason that the preference for a hyperplane is relative and will be local to a specific problem. So, <em>c </em>is used to represent how one objective (maximizing margin) is preferred over the other (minimizing <em>sum_of_ξi’s)</em>. Because a problem is likely to be different from all other problems, <em>hypertuning</em> the parameter <em>c</em> is required so that a suitable preference can be incorporated with the optimization problem to model our preference for a robust classifier. If <em>c </em>is set to be too high, the objective ||w||²/2 will also be high at the computed Pareto optimal point. This corresponds to a classifier with small margin and small values of <em>ξi’s, </em>i.e., we may end up with a hard margin SVM. Consequently, if the dataset is not linearly separable, we may get a less-desired hyperplane- something like shown in figure 3.</p><h3>Postscript</h3><p>I found it really difficult to make sense out of <em>Expression 1</em>. It is not that I could not find an answer- I read on quora, stackexchange and other platforms. Everyone had been maintaining the same statement “<em>c</em> balances the trade off between margin width and amount of misclassifications you want to avoid”. But just knowing this did not seem to be complete. But after referring to more sources and around 10 papers, I found a smooth passage that led to the quoted statement. I have cited only two most relevant papers here. In this article, I attempted to set down a smooth discussion of what I learned. I hope the article did not kink its way from one concept to another. If it felt so somewhere, do let me know in the comment section. The purpose with which I started to write was not just to explain a topic, it was to take a smooth journey- something which I personally like.</p><p>Thank you for reading. Looking forward to getting feedbacks and suggestions.</p><h4>References</h4><p>[1] Bui, L. T., &amp; Alam, S. (2008). An introduction to multi-objective optimization. In <em>Multi-Objective Optimization in Computational Intelligence: Theory and Practice</em> (pp. 1–19). IGI Global.</p><p>[2] <a href="https://www.igi-global.com/dictionary/pareto-front/21878">https://www.igi-global.com/dictionary/pareto-front/21878</a></p><p>[3] Marler, R. T., &amp; Arora, J. S. (2010). The weighted sum method for multi-objective optimization: new insights. <em>Structural and multidisciplinary optimization</em>, <em>41</em>(6), 853–862.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=30308a73e072" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/demystifying-maths-of-svm-part-2-30308a73e072">Demystifying Maths of SVM — Part 2</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[Demystifying Maths of SVM]]></title>
            <link>https://medium.com/data-science/demystifying-maths-of-svm-13ccfe00091e?source=rss-e1dae62fc758------2</link>
            <guid isPermaLink="false">https://medium.com/p/13ccfe00091e</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[supervised-learning]]></category>
            <category><![CDATA[cost-function]]></category>
            <category><![CDATA[classifcation-models]]></category>
            <category><![CDATA[svm]]></category>
            <dc:creator><![CDATA[Krishna Kumar Mahto]]></dc:creator>
            <pubDate>Sun, 06 Jan 2019 05:18:55 GMT</pubDate>
            <atom:updated>2019-04-18T10:10:46.670Z</atom:updated>
            <content:encoded><![CDATA[<h3>Demystifying Maths of SVM — Part 1</h3><h4>Deriving the optimization objective of the Support Vector Machine for a linearly separable dataset with a detailed discourse on each step</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*WOHe57SlKhzVkj24PEODZQ.jpeg" /></figure><p>So, three days into SVM, I was 40% frustrated, 30% restless, 20% irritated and 100% inefficient in terms of getting my work done. I was stuck with the Maths part of Support Vector Machine. I went through a number of YouTube videos, a number of documents, PPTs and PDFs of lecture notes, but everything seemed too indistinct for me. Out of all these, I found <a href="https://www.youtube.com/watch?v=s8B4A5ubw6c">Andrew Ng’s Stanford lectures</a> the most useful. Although he falls a little short in his ability to convey everything he intends to, his notes and derivations flow down very smoothly. Whatever I am going to discuss was inspired 50% by Andrew Ng’s lectures and his notes, 20% by one of the ML courses I am taking, and 29% by everything else and the rest of 1% comes from the little work which I put together into building this up. At the end, it turns out that it is not at all difficult to understand how SVM came up as all it takes is high school coordinate and vector geometry. For the most part, finding the right dots to make a sensible map was what I found difficult. With this article, I have tried to lay down the mathematical derivation which I came up with by affixing ideas from different sources, along with the thought process.</p><h3>Let’s begin …</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/566/1*SgXnNjy8aXR-6ZwaPek0xg.png" /><figcaption>Fig 1. Diagrammatic representation of SVM for linearly separable dataset (Source: <a href="https://www.researchgate.net/figure/Classification-of-data-by-support-vector-machine-SVM_fig8_304611323">https://www.researchgate.net/figure/Classification-of-data-by-support-vector-machine-SVM_fig8_304611323</a>)</figcaption></figure><p>The diagram does not look to be too worrying if you know SVM at a high conceptual level (the Optimal Margin Classifier stuff). Although the cases of linearly separable datasets are not seen in real life, discussion throughout this article on SVM will be for this context only. I might do a separate post for a more general version of SVM.</p><blockquote><strong>SVM hypothesis</strong></blockquote><p>Hypothesis, w.r.t. a machine learning model is the model itself, which is nothing but our classifier (which, is a function).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/289/1*rMSPK2eAf9AFUCDCgXIXXA.png" /><figcaption>g(z) = 1 if z ≥ 0, -1 otherwise</figcaption></figure><blockquote><strong>Class labels</strong></blockquote><p>Class labels are denoted as -1 for negative class and +1 for positive class in SVM.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/117/1*g9Mig-vT5gXLadWhf-8BBQ.png" /></figure><p>The final optimization problem that we shall have derived at the end of this article and what SVM solves to fit the best parameters is:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/239/0*5nbgaf6vF2GVAI4v.png" /><figcaption>Optimization problem that the SVM algorithm solves</figcaption></figure><p>This is a <em>convex optimization</em> problem, with a <em>convex optimization objective function </em>and a set of constraints that define a <em>convex set</em> as the <em>feasible region. </em>Convex functions look like a bowl placed right-side-up. Convex set is a set of points in which a line joining any two points lies entirely within the set. I would have loved to talk on these in more detail, but it would be more convenient to just google the terms in italics.</p><p>Before delving into the actual part, we should be familiar with two terms- <em>Functional margin and Geometric margin</em>.</p><h4>Functional margin and Geometric margin</h4><p>Following is how we are going to notate the hyperplane that separates the positive and negative examples throughout this article:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/315/1*SXKxN0q5XInK4bV9XovKJQ.png" /><figcaption>Equation of separating hyperplane; w is the normal to the hyperplane</figcaption></figure><p>Each training example is denoted as <em>x</em>, and superscript (<em>i)</em> denotes <strong><em>i</em></strong>th training example. In the following section <em>y</em> superscripted with (i) represents label corresponding to the <strong><em>i</em></strong><em>th training example.</em></p><blockquote>Functional margin <strong>of a hyperplane</strong><em> </em>w.r.t. <strong>i</strong><em>th taining example </em>is <em>defined</em> as:</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/297/1*lGtdFlxUXROiWzVTEEZVUw.png" /><figcaption>Functional margin of a hyperplane w.r.t. ith example (denoting as gamma-hat superscripted with (i))</figcaption></figure><p>Functional margin <strong><em>of a hyperplane</em></strong><em> </em>w.r.t. the entire dataset is defined as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/206/1*M0nnqPP-kOA01jvlouPEBA.png" /><figcaption>Functional margin of a hyperplane w.r.t. the entire dataset</figcaption></figure><blockquote>Geometric margin <strong>of a hyperplane</strong> w.r.t. <strong>i</strong>th training example is defined as functional margin normalized by norm(<strong>w</strong>):</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/333/1*gSHCG8zviEqSyfeu0UFRDQ.png" /><figcaption>Geometric margin w.r.t. ith training example (denoted as gamma superscripted with (i)).</figcaption></figure><p>Geometric margin for a hyperplane w.r.t. the entire dataset is defined as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/208/1*DC5fr7Azi6JIp9G0ss3B9A.png" /><figcaption>Geometric margin of hyperplane w.r.t. the entire dataset</figcaption></figure><blockquote><strong>Note</strong>: In the following discussion, if it is not specified whether the functional/geometric margin of a hyperplane is mentioned w.r.t. the entire dataset or some example, then it should be assumed to be in reference to the entire dataset, and not a single example.</blockquote><h4>Brief on how SVM algorithm works, what it wants to achieve (interpreting SVM conceptually)</h4><p>Just to make sure we are on the same page, lets discuss how SVM works. I have come across two interpretations of SVM (or more precisely, the goal that SVM aims at achieving). Both the interpretations as quoted below are just different ways of conveying the same thing as we shall see when we derive the optimization objective.</p><p>First,</p><blockquote>SVM maximizes the margin (as drawn in fig. 1) by learning a suitable decision boundary/decision surface/separating hyperplane.</blockquote><p>Second,</p><blockquote>SVM maximizes the geometric margin (as already defined, and shown below in figure 2) by learning a suitable decision boundary/decision surface/separating hyperplane.</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/310/1*8R09B7ZmN5fRqBESLX_Blg.png" /><figcaption>Fig. 2. A is ith training example, AB is the geometric margin of hyperplane w.r.t. A</figcaption></figure><p>The way I have derived the optimization objective starts with using the concepts of functional and geometric margin; and after establishing that the two interpretations of SVM coexist with each other, the final optimization objective is derived.</p><h4>The derivation</h4><p>As said, we shall start with functional and geometric margin interpretation, and then establish the coexistence of the two interpretations of SVM.</p><blockquote>Could we have gone the other way round?</blockquote><p>I tried doing that, but it turned out to be not a better way to proceed by starting with the first interpretation. We shall discuss why that would not have worked out this well once we have derived the formulation of the optimization objective.</p><p>As already discussed, SVM aims at maximizing the geometric margin and returns the corresponding hyperplane. What it means is that out of all possible hyperplanes (each hyperplane has a geometric margin w.r.t. the point closest to it which is the least of all other geometric margins defined w.r.t. all other points), SVM chooses that hyperplane which has the maximum geometric margin. In fig. 3, the red hyperplane is the best separating hyperplane.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/371/0*e64e2D_6YP3j9H5e.png" /><figcaption>Fig. 3. Which hyperplane is the best? — the one in red</figcaption></figure><p>This can be mathematically written as,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/775/1*hmk7AFwY33cXl9rYqxtz7w.png" /><figcaption>Initial optimization problem</figcaption></figure><p>Apparently, the objective function is the geometric margin of the hyperplane (<strong><em>w</em></strong><em>, b)</em>. The constraints represent the fact that the objective function is the minimum of the set of geometric margins of the hyperplane <em>(</em><strong><em>w</em></strong><em>, b) </em>w.r.t. all the training examples.</p><p>We can observe that the formulation of geometric margin ensures that for the optimal hyperplane, the value of the smallest of all geometric margins (computed w.r.t. all examples) is shared by atleast one pair of examples (one pair from +ve class and the other from -ve class). Such points are called as <strong><em>support vectors </em></strong>(fig.- 1).</p><p>Therefore, the optimization problem as defined above is equivalent to the problem of maximizing the <em>margin </em>value (not geometric/functional margin values). Margin is defined as the distance between two hyperplanes, each of which is parallel to the separating hyperplane and passes through support vectors of each class (i.e., one hyperplane passes through support vectors of +ve class, while the other hyperplane passes through support vectors of -ve class, and both are parallel to the separating hyperplanes).</p><blockquote>At this point, therefore, we can establish that both the interpretations of SVM actually coexist, although we started with the second interpretation to come to this conclusion. Towards the end, I shall discuss that while going the other way round, we carry some redundancy in our formulation and therefore, start off with less cleaner ideation of the problem.</blockquote><p>Let us denote the respective hyperplanes as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/344/1*mg8W-esTkb5C43w1W5JLLQ.png" /><figcaption>Hyperplane passing through positive support vectors</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/348/1*X3IyIvUFfAQyNvS8YE1A-Q.png" /><figcaption>Hyperplane passing through negative support vectors</figcaption></figure><p>Therefore, the optimization problem can be reformulated with the following objective function:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xYaTKu2kxTH64SUdVhj6jg.png" /><figcaption>Reformulated optimization objective (i)</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*SHdcGwF1jAqFetx1MvoB_Q.png" /><figcaption>Reformulated optimization objective (ii)</figcaption></figure><p>The simplification till now has been done only in terms of writing smaller notations and smaller expressions. We have not cut down anything in terms of the computations to be done in comparison to where we had started (actually, it would be nice to verify this on your own).</p><blockquote>The idea that will be executed as the next step in developing the final form of the optimization problem of the SVM, does not appear to be as straightforward to ideate.</blockquote><p>We have been doing vector geometry since the beginning of this article. It turns out that SVM is actually geometrically motivated algorithm at its core. What is done to further simplify the objective function is not difficult apply or understand, but out of many operations that you could possibly do on an expression, zeroing down on the following idea feels non-trivial.</p><blockquote>Here it is …</blockquote><p>One of the things about equation of a hyperplane is that scaling it does not change the hyperplane. It gives a new equation <em>(</em><strong><em>w’</em></strong><em>, b’)</em>, where <strong><em>w’</em></strong><em> = k . </em><strong><em>w</em></strong><em> and b’ = k . b</em> (<em>k</em> is the scaling factor) but the hyperplane remains the same in space and the geometric margin therefore, also does not change (but functional margin does change). Leveraging this factor, what we can do is we can scale the <strong><em>w </em></strong>and<em> b </em>in our optimization objective function <strong><em>such that functional margin becomes 1.</em></strong></p><p>This makes our optimization problem as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*dxRo5Uehik5GK5bOLkkC3g.png" /><figcaption>w and b have been scaled such that functional margin has become 1</figcaption></figure><p>This, in true sense, has reduced the optimization problem by reducing the number of computations to be performed!</p><blockquote>We have gone through almost the entire derivation, with the last part we just saw being the most crucial one.</blockquote><p>However, there is a problem with this formulation. The objective function is a non-convex function, which is preferred to be avoided (fig. 4).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/653/1*GGjusX1QiQ4A5Ogh7pk8Mw.png" /><figcaption>Fig 4. Geometic margin of hyperplane w = (w1, w2), b = 1; x(i) = (1, 1) (Plotter used: <a href="https://www.geogebra.org/">https://www.geogebra.org/</a>)</figcaption></figure><p>Since we apply gradient descent to optimize the function, non-convex functions may cause the algorithm to get stuck at a local minimum. But it turns out that squaring the <em>norm(</em><strong><em>w</em></strong><em>)</em> in the multiplicative inverse of the objective function gives a convex, differentiable function (inverse of the objective function is also convex, but is non-differentiable at <strong><em>w = 0</em></strong>, you can verify this by using an online plotting tool). We can use this as our objective function, with the optimization problem being a little modified now:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*VcI5AqGPDLniaPFdT4G25Q.png" /><figcaption>Making the objective function convex; this is also the final optimization problem of SVM</figcaption></figure><p>In fact, this is the final objective function which is perfectly convex also (fig. 5)! We love convex optimization problems.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/940/1*6ytouB1PULmH7PEtGX8U2g.png" /><figcaption>Fig. 5. The final objective function is perfectly convex (Plotter used: <a href="https://www.geogebra.org/">https://www.geogebra.org</a>)</figcaption></figure><p>Note that maximizing a function <em>f </em>is same as minimizing a function <em>g = 1/f</em>. That is why the optimization problem is now a minimization problem opposed to being a maximization problem as before.</p><blockquote>The end result feels satisfying.</blockquote><p>A few more points to conclude:</p><ol><li>We started with the problem of optimizing geometric margin, and not functional margin. This is because functional margin can be easily increased (or decreased) by simply scaling <strong><em>w </em></strong>and <em>b</em>. Recall that doing this does not change the hyperplane. So, this either would not converge to an optimal separating hyperplane or there would be too many iterations which essentially would be useless. It might be argued that constraining the magnitude of <strong><em>w</em></strong> may help the issue. But this is not at all a good idea, since ||<strong><em>w</em></strong>|| = <em>c</em> (<em>c</em> is some constant) is a non-convex constraint (as the feasible set is the surface of a hypersphere), making the optimization problem non-convex. We always want to avoid non-convex optimization problems.</li><li>We started with the second interpretation, and then established that both interpretations coexist. But we inferred the first interpretation from the second one. It turns out that starting out with the first interpretation might not be as convenient because then, we would be starting with two parallel hyperplanes, initially separated by some <em>|b1- b2|/||</em><strong><em>w</em></strong><em>|| </em>where b1 and b2 are initial constants of their respective equations. It is not difficult to see that the distance between the two hyperplanes may not change at all even if their <strong><em>w</em></strong> is changed (rotating the hyperplanes by same angle). Constraining the feasibility region would be important for this case as well because learning hyperplanes at max distance may simply mean learning those hyperplanes that are as far as possible. That does not serve the purpose. The constrained optimization problem would therefore be something like: “maximize the distance s.t. all -ve points are on one side of -ve hyperplane, and all +ve points are on one side of +ve hyperplane”. We could use functional margin for this, but then we can observe that all +ve points are on the same side of both +ve as well as -ve hyperplanes, the same holds for -ve points as well. So using two hyperplanes is a bit redundant. Also, without the definition of functional and geometric margin (which are defined in reference to a separating hyperplane) it would not be as easy, if not impossible, to derive the results we just did.</li></ol><h4>Footnotes</h4><p>Hopefully I have written something sensible with correct Maths. I used <a href="http://cs229.stanford.edu/notes/cs229-notes3.pdf">Andrew Ng’s lecture notes</a> and his <a href="https://www.youtube.com/watch?v=s8B4A5ubw6c">lecture series available on YouTube</a> (both from Stanford offline class notes, not Coursera), some ideas from a paid course that I am doing and a number of visits to stackoverflow.com, and then compiled them all into this. Hope you liked it.</p><p>Also, kindly pardon my handwriting. If what is written in those images are not clear, do let me know. I shall replace them with new pictures.</p><p>Thank you for reading.</p><h3>Update</h3><p>I have also written an article deriving the Soft-margin SVM. You can find it <a href="https://bit.ly/2BnYnpz">here</a>. Thank you.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=13ccfe00091e" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/demystifying-maths-of-svm-13ccfe00091e">Demystifying Maths of SVM</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[Beginner’s Guide to Machine Learning A-Z (udemy)]]></title>
            <link>https://medium.com/series/beginners-guide-to-machine-learning-a-z-udemy-3952f2b10c67?source=rss-e1dae62fc758------2</link>
            <guid isPermaLink="false">https://medium.com/p/3952f2b10c67</guid>
            <dc:creator><![CDATA[Krishna Kumar Mahto]]></dc:creator>
            <pubDate>Thu, 02 Aug 2018 07:39:28 GMT</pubDate>
            <atom:updated>2018-08-03T03:41:13.471Z</atom:updated>
            <content:encoded><![CDATA[<h4><strong>Part-1: Data Preprocessing- Categorical Data</strong></h4><p><strong>What is Categorical Data? What is the difference between LabelEncoder and OneHotEncoder?</strong></p><p>Those who are completely new to Data Science (like me), may have heard the term “Categorical Data” for the first time, or maybe the term seems new because it was just a definition for you in one of the Statistics classes you took ;) .</p><p>Data collected can be of two types- numeric, which are naturally expressible as numbers, and categorical which are non-numeric. Let me remind you that numeric data inherently is responsive to the arithmetic operations- addition, subtraction, etc. You may say, number of tee shirts that you have is 4; but you could also write it as ‘Four’! Is it still numeric or is it categorical now? You may then say, your favorite countries are ‘Democratic Republic of the Congo’ and ‘Czechoslovakia’ (I randomly chose these names!). You could then say that, since these names are too long to write, you randomly want to alias these names with numbers (rather than with any short name), ‘Democratic Republic of the Congo’ = 301 (some random number) and ‘Czechoslovakia’ = 3231 (random!). You then smirk and ask- “categorical or numeric?”.</p><p>The answer is simple, yet fundamental. We have defined numerical data to be something with which mathematics, as we know and have defined, works. So, you could say 4+4 = 8 or ‘Four’ + ‘Four’ = ‘Eight’, both are correct because these two expressions inherently are mathematically <em>sane</em>! Consider ‘Czechoslovakia’ = 3231 and ‘Democratic Republic of the Congo’ = 301. What is 3231+301 = ? ? If you would say “3532”. I would say..”yea, fine..but what did you consider 3231 and 301 when you added them?” Would you say numbers, or countries? Well, you could tell the sum only if you would have considered them numbers, numeric values. If you would have carried your assumption that these two numbers are countries, then the very expression of addition would not make sense at all! Hopefully this is an intuitively agreeable argument.</p><p>Conclusively, no matter what you do, numeric data will be numeric, and what is not numeric is categorical intrinsically. We call it categorical, instead of non-numeric because such data often belongs to a finite set, and can attain categorical values, eg- ‘countries’ can be ‘India’, ‘USA’, ‘Japan’, ‘pets’ could be ‘dogs’, ‘cats’, etc; here ‘countries’ and ‘dogs’ are called categorical variables.</p><p>For the next part of the question, the definition that should be understood is ‘ordinal relationship’. Integers, or numeric data have a natural ordering, 1&lt; 2&lt; 3&lt; 4 and so on which is harnessed by some ML algorithms while making computations. In the eg specified in the lecture, ‘Places’ are not numeric (which we just concluded in the discussion above) and hence bears no such ordinality. LabelEncoder encodes the data into numbers, which inherit this ordinality- which obviously is not the best choice to make for categorical variables like ‘Places’. One-hot encoder avoids this ordinality, so we end up using this after using LabelEncoder class for ‘Places’ categorical variable.</p><h4>Part-1: Data Preprocessing- Categorical Data</h4><p><strong>Why did the instructor use LabelEncoder object and OneHotEncoder object differently?</strong></p><p>Because the LabelEncoder_obj.fit_transform() operates on 1D array, ie, you can pass 1D array to the object as parameter, it can operate on strings labels and map them to integers. OneHotEncoder_obj.fit_transform() accepts a 2D array and the index to be mapped is given beforehand during object creation itself as keyword argument (categorical_features = [0] in the lecture code). If you pass the 2D array to OneHotEncoder_obj.fit_transform() without first converting the categorical data into integer, then the program will throw an error.</p><h4>Part-1: Data Preprocessing</h4><p><strong>Why do we use random_state parameter in train_test_split()?</strong></p><h4>Part-2: Regression</h4><p><strong>Why do we use p-value and why is it that we eliminate independent variable (aka feature) with p&gt;significance?</strong></p><p>During the lecture, Kirill should have told explicitly what the null hypothesis we were working with.</p><p>I assume you have read the explanations, links to which were given in the article and so, you know what p-value is. According to what I understood, p-value is the probability of us being wrong. Wrong in what? We would propose that the existing hypothesis (Null Hypothesis is wrong), ie, we stand with an opposing hypothesis which is called an Alternative Hypothesis. If this p-value is greater than some predetermined threshold value which is called as significance level (I shall call it simply significance in the text that follows), then the chances of us being wrong (and the null hypothesis being correct) is more and henceforth, we consider the null hypothesis continues to be held correct.</p><p>From the steps in Backward Elimination, I inferred:</p><ul><li>Null Hypothesis (the status quo I am trying to disprove): A particular feature (independent variable) is not useful for the predictive model.</li><li>Alternative Hypothesis: The feature is useful for our model.</li></ul><p>I inferred this on the basis of the fact that we are eliminating a feature when p&gt;significance. p&gt;significance implies that the probability that my alternative hypothesis has high probability to be wrong, and so in that case Null hypothesis succeeds in maintaining its status quo and therefore, the feature actually is not useful for the model. So we remove it.</p><p>Same set of hypothesis still hold for Forward Selection and the inference can then be deduced from the steps.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3952f2b10c67" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>