<?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 Edwin Tai on Medium]]></title>
        <description><![CDATA[Stories by Edwin Tai on Medium]]></description>
        <link>https://medium.com/@AnHungTai?source=rss-3b3e197d3873------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/2*UFUegmlymrFMaNGDW1ByIA.jpeg</url>
            <title>Stories by Edwin Tai on Medium</title>
            <link>https://medium.com/@AnHungTai?source=rss-3b3e197d3873------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 21:49:10 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@AnHungTai/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[Kernel Functions in Non-linear Classification]]></title>
            <link>https://medium.com/data-science/kernel-functions-in-non-linear-classification-91a6c9ab14d6?source=rss-3b3e197d3873------2</link>
            <guid isPermaLink="false">https://medium.com/p/91a6c9ab14d6</guid>
            <category><![CDATA[binary-classification]]></category>
            <category><![CDATA[mapping]]></category>
            <category><![CDATA[kernel]]></category>
            <category><![CDATA[non-linear]]></category>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Edwin Tai]]></dc:creator>
            <pubDate>Sun, 25 Aug 2019 15:15:53 GMT</pubDate>
            <atom:updated>2019-08-28T03:03:34.293Z</atom:updated>
            <content:encoded><![CDATA[<h4>Learn how kernel functions map features into higher dimensions.</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*fuYHjgQmXfNi34fW8sRyhw.png" /></figure><p>Once the data points are non-linear separable in their original feature space, the linear classifier may be failed to determine where the decision boundary is. However, mapping the original feature space (<em>x</em> ∈ ℝᵈ) into the higher dimensional feature space (<em>ϕ</em>(<em>x</em>) ∈ ℝᵉ , e&gt;d) can help to resurrect the linear classifier to do the job correctly.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/326/1*TfUSC60rUOZAmYZ5QOOGUw.png" /></figure><p>Figure 1. illustrates the concepts of classifying data points through feature mapping. Originally, the data points with the feature vectors <em>x</em> = [<em>x</em>₁, <em>x</em>₂] in the 2-D space have the concentrically circular distribution (not a strictly mathematical description here). It is impossible to use a linear classifier to distinguish the decision boundary.</p><p>Nonetheless, by incorporating a certain mapping function <em>ϕ</em>(<em>x</em>), the feature vectors can be transformed into 3-D feature space. The new data points with 3-D feature vectors <em>ϕ</em>(<em>x</em>) = [<em>x</em>₁, <em>x</em>₂,(<em>x</em>₁²+<em>x</em>₂²)] can now be using the linear classifier to determine the decision boundary hyperplane. This is the power of feature mapping that can allow us to deal with the more complex data distribution pattern with more expressive ability.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*YHelTqNV7MyOJrsZgWoiOw.png" /><figcaption>Figure 1. Mapping data points with 2-D feature vectors into 3-D feature vectors</figcaption></figure><p>However, the drawbacks of using <em>ϕ</em>(<em>x</em>) directly are that</p><ol><li>It is sometimes hard to explicitly construct a <em>ϕ</em>(<em>x</em>) directly.</li><li>Increase computational power quickly with the increased feature dimensions.</li></ol><p>But the kernel functions can provide an efficient way to solve this.</p><h3>Kernel Functions</h3><p>The idea of kernel functions is to take the inner products between two feature vectors, and evaluate inner products is not computationally costly. We can then exploit only the result of the inner products in our algorithms. For example, if we want to have the <em>ϕ</em>(<em>x</em>) as follows,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/366/1*Ry5zanqAcAuUdA6A55--WA.png" /></figure><p>The kernel function is take the inner products between two feature vectors as follows,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/326/1*1btyG-vQRonGHspi9v-sbw.png" /></figure><p>As a result, the form of the kernel functions will be easier for us to construct than directly use the mapping functions in the higher feature dimensions.</p><h3>Kernel Composition Rules</h3><p>There are several kernel composition rules that can be used to construct more complex kernel functions.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/560/1*_K91RAdMLmj5qJJ5yB9NSQ.png" /></figure><h3>Radial Basis Kernel</h3><p>The kernel functions can even empower the feature vectors to be infinite dimensional. One of the common kernel functions is the radial basis kernel. The definition is as follows.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/217/1*2TrrPfzuAeTHJiNhFG-ppg.png" /></figure><p>Because the exponential can be expanded to the infinite power series, the radial basis kernel gives much more expressiveness to the feature mapping. The following is the proof of the radial basis kernel that is a kernel function.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/306/1*ncu1MN8R9mpVg9N8uupAHA.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*brM22oD-XOy44yf0eLBu6A.png" /></figure><h3>Kernel Perceptron Algorithm</h3><p>Recalling the perceptron algorithm <a href="https://towardsdatascience.com/perceptron-algorithms-for-linear-classification-e1bb3dcc7602">here</a>, the perceptron algorithm updates <em>θ = θ + </em>y⁽ ʲ<em> </em>⁾ <em>x</em>⁽ ʲ<em> </em>⁾ once a data point is misclassified. In the other word, the <em>θ </em>can be expressed alternatively as follows.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/164/1*Nc9LQTLHEDGouTGYKqfkXg.png" /></figure><p>where α<strong>ⱼ</strong> is the number of mistakes the perceptron made on the <em>j</em>-th data point. If it is in the mapping feature space, the <em>θ </em>can be expressed as follows.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/340/1*eMArI8mhitnpmOa70og-Ug.png" /></figure><p>Utilizing the kernel form of the <em>θ, </em>the pseudocode of the kernel perceptron algorithm can be described as follows.</p><pre><em># Kernel Perceptron Algorithm</em></pre><pre><em># initialize </em>α<strong>ⱼ</strong><br><em># totally m data points<br></em>for i = 1 .. m do<br>    αᵢ = 0</pre><pre><em># totally T epoches to iterate</em><br>for t = 1 .. T do                     <br>   <em> # totally m data points</em>    <br>    for i = 1 .. m do<br>        <em># misclassify data points</em>                 <br>        if y⁽ⁱ⁾<strong><em>∑</em>ⱼ(</strong>α<strong>ⱼ</strong>y⁽ʲ⁾<em>K</em>(x⁽ʲ⁾,x⁽ⁱ⁾)<strong>)</strong> ≦ 0     <br>        then<br>            αᵢ = αᵢ + 1</pre><pre>θ<em>ϕ</em>(x⁽ⁱ⁾)= <strong><em>∑</em>ⱼ(</strong>α<strong>ⱼ</strong>y⁽ʲ⁾<em>K</em>(x⁽ʲ⁾,x⁽ⁱ⁾)<strong>)</strong></pre><h3>Kernel in Action</h3><p>Figure 2. visualizes the updating of the decision boundary by the radial basis kernel perceptron algorithm. Note that the decision boundary drawn by the radial basis kernel perceptron algorithm can converge in 2 epoches with this kind of data distribution. The γ for the radial basis kernel uses 0.3 here.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/480/1*t28AsbPCYUwHDaL9o0gkwg.gif" /><figcaption>Figure 2. Updating the decision boundaries by the RBK perceptron algorithm. May take time to load.</figcaption></figure><h3>Sample Code</h3><p>The sample code written in Jupyter notebook for the perceptron algorithms can be found <a href="https://github.com/AnHungTai/Medium-SampleCode/blob/master/Kernel%20Functions%20in%20Nonlinear%20Classification/Visualizing%20Kernel.ipynb">here</a>. You can play with the data and the hyperparameters yourself to see how the kernel perceptron algorithm performs.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=91a6c9ab14d6" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/kernel-functions-in-non-linear-classification-91a6c9ab14d6">Kernel Functions in Non-linear Classification</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[Perceptron Algorithms for Linear Classification]]></title>
            <link>https://medium.com/data-science/perceptron-algorithms-for-linear-classification-e1bb3dcc7602?source=rss-3b3e197d3873------2</link>
            <guid isPermaLink="false">https://medium.com/p/e1bb3dcc7602</guid>
            <category><![CDATA[supervised-learning]]></category>
            <category><![CDATA[decision-boundary]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[perceptron]]></category>
            <category><![CDATA[binary-classification]]></category>
            <dc:creator><![CDATA[Edwin Tai]]></dc:creator>
            <pubDate>Tue, 20 Aug 2019 17:48:07 GMT</pubDate>
            <atom:updated>2019-08-20T17:48:07.225Z</atom:updated>
            <content:encoded><![CDATA[<h4>Learn how the perceptron algorithms work and the intuition behind them.</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*8zQW3SanV2FQr5iYPY-2Gg.png" /></figure><p>The basic perceptron algorithm was first introduced by <a href="#6b44">Ref 1</a> in the late 1950s. It is a binary linear classifier for supervised learning. The idea behind the binary linear classifier can be described as follows.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/294/1*LMHHvqD0SIjycr335cvFfQ.png" /></figure><p>where <em>x</em> is the feature vector, <em>θ</em><strong> </strong>is the weight vector, and <em>θ</em>₀ is the bias. The sign function is used to distinguish<strong> </strong><em>x</em> as either a positive (+1) or a negative (-1) label. There is the decision boundary to separate the data with different labels, which occurs at</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/138/1*gFWVNAig4uitRsUXW7S_Jg.png" /></figure><p>The decision boundary separates the hyperplane into two regions. The data will be labeled as positive in the region that<strong> </strong><em>θ⋅ x</em> + <em>θ</em>₀ &gt; 0,<strong><em> </em></strong>and be labeled as negative in the region that <em>θ⋅ x</em> + <em>θ</em>₀ &lt; 0. If all the instances in a given data are <strong>linearly separable</strong>, there exists a <em>θ </em>and a <em>θ</em>₀ such that y⁽<em>ⁱ </em>⁾ (<em>θ⋅ x</em>⁽<em>ⁱ </em>⁾ + <em>θ</em>₀) &gt; 0 for every <em>i</em>-th data point, where y⁽<em>ⁱ </em>⁾ is the label.</p><p>Figure 1 illustrates the aforementioned concepts with the 2-D case where the <em>x</em> = [<em>x</em>₁ <em>x</em>₂]ᵀ, <em>θ</em> = [<em>θ</em>₁ <em>θ</em>₂] and <em>θ</em>₀ is a offset scalar. Note that the margin boundaries are related to the regularization to prevent overfitting of the data, which is beyond the scope discussed here.</p><figure><img alt="Figure 1. The concepts of binary linear classifier with the 2-D case." src="https://cdn-images-1.medium.com/max/865/1*sfqR-rZSYaITJ5_PbXU_9w.png" /><figcaption>Figure 1. The concepts of binary linear classifier with the 2-D case.</figcaption></figure><h3>Perceptron</h3><p>One way to find the decision boundary is using the perceptron algorithm. The perceptron algorithm updates <em>θ </em>and <em>θ</em>₀ only when the decision boundary misclassifies the data points. The pseudocode of the algorithm is described as follows.</p><pre><em># Perceptron Algorithm</em></pre><pre><em># initialize θ and θ₀ with 0</em><br>θ = 0  (vector)<br>θ₀ = 0 (scalar)</pre><pre><em># totally T epoches to iterate</em><br>for t = 1 .. T do                     <br>   <em> # totally m data points</em>    <br>    for i = 1 .. m do<br>        <em># misclassify data points</em>                 <br>        if y⁽ⁱ⁾(θ ⋅ x⁽ⁱ⁾ + θ₀) ≦ 0     <br>        then<br>            θ  = θ + y⁽ⁱ⁾ ⋅ x⁽ⁱ⁾<br>            θ₀ = θ₀ + y⁽ⁱ⁾</pre><pre>return θ, θ₀</pre><p>The perceptron algorithm iterates through all the data points with labels and updating <em>θ </em>and <em>θ</em>₀ correspondingly. The intuition behind the updating rule is to push the y⁽<em>ⁱ </em>⁾ (<em>θ⋅ x</em>⁽<em>ⁱ </em>⁾ + <em>θ</em>₀) closer to a positive value if y⁽<em>ⁱ </em>⁾ (<em>θ⋅ x</em>⁽<em>ⁱ </em>⁾ + <em>θ</em>₀) ≦ 0 since y⁽<em>ⁱ </em>⁾ (<em>θ⋅ x</em>⁽<em>ⁱ </em>⁾ + <em>θ</em>₀) &gt; 0 represents classifying the<em> i-</em>th<em> </em>data point correctly.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/437/1*O5zcE07P-gG6tpDezROULQ.png" /></figure><h3>Perceptron Convergence</h3><p>The factors that constitute the bound on the number of mistakes made by the perceptron algorithm are maximum norm of data points and maximum margin between positive and negative data points. The theorems of the perceptron convergence has been proven in <a href="#cbb7">Ref 2.</a> Given a set of data points that are linearly separable through the origin, the initialization of <em>θ</em> does not impact the perceptron algorithm’s ability to eventually converge.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/536/1*6hO_dGP8iQY6DWDgr7duQg.png" /></figure><p>The number of the iteration <em>k</em> has a finite value implies that once the data points are linearly separable through the origin, the perceptron algorithm converges eventually no matter what the initial value of <em>θ </em>is. The concepts also stand for the presence of <em>θ</em>₀.</p><p>However, this perceptron algorithm may encounter convergence problems once the data points are linearly non-separable. There are two perceptron algorithm variations introduced to deal with the problems. One is the average perceptron algorithm, and the other is the pegasos algorithm.</p><h3>Average Perceptron</h3><p>Similar to the perceptron algorithm, the average perceptron algorithm uses the same rule to update parameters. The final returning values of <em>θ </em>and <em>θ</em>₀ however take the average of all the values of <em>θ </em>and <em>θ</em>₀ in each iteration. The pseudocode of the algorithm is described as follows.</p><pre><em># Average Perceptron Algorithm</em></pre><pre><em># initialize θ, θ₀, sum_θ, sum_θ₀, and counter with 0</em><br>θ = 0  (vector)<br>θ₀ = 0 (scalar)<br>sum_θ = 0  (vector)<br>sum_θ₀ = 0 (scalar)<br>counter = 0</pre><pre><em># totally T epoches to iterate</em><br>for t = 1 .. T do                     <br>    <em># totally m data points </em>   <br>    for i = 1 .. m do  <br>        <em># misclassify data points   </em>            <br>        if y⁽ⁱ⁾(θ ⋅ x⁽ⁱ⁾ + θ₀) ≦ 0     <br>        then<br>            θ  = θ + y⁽ⁱ⁾ ⋅ x⁽ⁱ⁾<br>            θ₀ = θ₀ + y⁽ⁱ⁾</pre><pre>        sum_θ = sum_θ + θ<br>        sum_θ₀ = sum_θ₀ + θ₀<br>        counter = counter + 1</pre><pre>return (sum_θ/counter), (sum_θ₀/counter)</pre><h3>Pegasos</h3><p>The pegasos algorithm has the hyperparameter <em>λ</em>, giving more flexibility to the model to be adjusted. The <em>θ </em>are updated whether the data points are misclassified or not. The details are discussed in <a href="#c12e">Ref 3.</a> The pseudocode of the algorithm is described as follows.</p><pre><em># Pegasos Algorithm</em></pre><pre><em># initialize θ, θ₀, and counter with 0</em><br>θ = 0  (vector)<br>θ₀ = 0 (scalar)<br>counter = 0</pre><pre><em># totally T epoches to iterate</em><br>for t = 1 .. T do <br>   <em> # totally m data points </em>                   <br>    for i = 1 .. m do                 <br>        counter = counter + 1<br>        η = 1/√counter <br>         <br>        if y⁽ⁱ⁾(θ⋅x⁽ⁱ⁾ + θ₀) ≦ 1    <br>        then<br>            θ  = (1 - ηλ)θ + ηy⁽ⁱ⁾⋅x⁽ⁱ⁾<br>            θ₀ = θ₀ + ηy⁽ⁱ⁾<br>        else<br>        then<br>            θ  = (1 - ηλ)θ<br>            θ₀ = θ₀</pre><pre>return θ,  θ₀</pre><h3>Visualizing Perceptron Algorithms</h3><p>Figure 2. visualizes the updating of the decision boundary by the different perceptron algorithms. Note that the given data are linearly non-separable so that the decision boundary drawn by the perceptron algorithm diverges. Both the average perceptron algorithm and the pegasos algorithm quickly reach convergence. The <em>λ</em> for the pegasos algorithm uses 0.2 here.</p><figure><img alt="Figure 2. Updating the decision boundary lines by the different perceptron algorithms." src="https://cdn-images-1.medium.com/max/480/1*Pwp3CYKLspEqjDKjDYX5YA.gif" /><figcaption>Figure 2. Updating the decision boundaries by the different perceptron algorithms. May take time to load.</figcaption></figure><h3>Sample Code</h3><p>The sample code written in Jupyter notebook for the perceptron algorithms can be found <a href="https://github.com/AnHungTai/Medium-SampleCode/blob/master/Perceptron%20Algorithms%20for%20Linear%20Classification/Visualizing%20Perceptron%20Algorithm.ipynb">here</a>. You can play with the data and the hyperparameters yourself to see how the different perceptron algorithms perform.</p><h3>Reference</h3><p>[1]</p><p>F. Rosenblatt,” The perceptron: A probabilistic model for information storage and organization in the brain,” <em>Psychological Review, 1958</em>. doi: <a href="http://doi.org/10.1037/h0042519">10.1037/h0042519</a></p><p>[2]</p><p>M. Mohri, and A. Rostamizadeh,” Perceptron Mistake Bounds,” <em>arxiv</em>, 2013. <a href="https://arxiv.org/pdf/1305.0208.pdf">https://arxiv.org/pdf/1305.0208.pdf</a></p><p>[3]</p><p>S. S.-Shwartz, Y. Singer, N. Srebro, and A. Cotter,” Pegasos: primal estimated sub-gradient solver for SVM,” <em>Mathematical Programming</em>, 2010. doi: <a href="https://doi.org/10.1007/s10107-010-0420-4">10.1007/s10107–010–0420–4</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e1bb3dcc7602" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/perceptron-algorithms-for-linear-classification-e1bb3dcc7602">Perceptron Algorithms for Linear Classification</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>