{"id":1397,"date":"2019-02-15T10:32:07","date_gmt":"2019-02-15T10:32:07","guid":{"rendered":"http:\/\/kusuaks7\/?p=1002"},"modified":"2023-08-09T12:37:02","modified_gmt":"2023-08-09T12:37:02","slug":"how-the-good-old-sorting-algorithm-helps-a-great-machine-learning-technique","status":"publish","type":"post","link":"https:\/\/www.experfy.com\/blog\/ai-ml\/how-the-good-old-sorting-algorithm-helps-a-great-machine-learning-technique\/","title":{"rendered":"How the good old sorting algorithm helps a great machine learning technique"},"content":{"rendered":"

Ready to learn Machine Learning? Browse courses<\/a>\u00a0like\u00a0Machine Learning Foundations: Supervised Learning<\/a> developed by industry thought leaders and Experfy in Harvard Innovation Lab.<\/em><\/strong><\/p>\n

In this article, we showed that how the simple sorting algorithm is at the heart of solving an important problem in computational geometry and how that relates to a widely used machine learning technique.<\/h4>\n
<\/canvas><\/figure>\n

Machine learning (ML) is fast becoming one of most important computational techniques in the modern society. A branch of Artificial Intelligence (AI), it is being applied to everything from\u00a0natural language translation and processing<\/a>(think Siri or Alexa) to\u00a0medicine<\/a>,\u00a0autonomous driving<\/a>, or business strategy development. A dizzying array of clever algorithms are being developed continuously for solving ML problems to learn patterns from streams of data and build AI infrastructure.<\/p>\n

However, sometimes it feels good to step back and analyze how some of the elementary algorithms are also doing their part in this revolution and appreciate their impact. In this article, I am going to illustrate one such non-trivial case.<\/p><\/blockquote>\n

Support Vector\u00a0Machine<\/strong><\/h4>\n

Support vector machine or SVM<\/a>\u00a0in short, is one of the most important machine learning techniques, developed in past few decades. Given a set of training examples, each marked as belonging to one or the other of two categories, an SVM training algorithm builds a model that assigns new examples to one category or the other, making it a non-probabilistic<\/a>\u00a0binary<\/a>linear classifier<\/a>. It is widely used in industrial systems, text classifications, pattern recognition, biological ML applications, etc.<\/p>\n

The idea is illustrated in the following picture. Main goal is to classify the points in the 2-dimensional plane into one of two categories \u2014 red or blue. It can be done by creating a classifier boundary (by running a\u00a0classification algorithm<\/a>\u00a0and learning from the labeled data) between the two sets of points. Some of the possible classifiers are shown in the figure. All of them will classify the data points correctly but not all of them have the same \u2018margin<\/em>\u2019 (i.e. distance) from the sets of data points which are closest to the boundary. It can be shown that only one of them maximizes this \u2018margin<\/em>\u2019 between the set of blue and red points. That unique classifier is shown by the solid line whereas the other classifiers are shown as dotted lines. The utility of this margin maximization is that\u00a0larger the distance between two classes, lower the generalization error will be for the classification of a new point.<\/em><\/strong><\/p>\n

<\/canvas>
\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 <\/strong><\/figcaption><\/figure>\n

\u00a0FIG 1<\/strong>: SVM and Maximum-margin classifier<\/p>\n

The main differentiating feature of SVM algorithm is that the\u00a0classifier does not depend on all the data points\u00a0<\/em><\/strong>(unlike say logistic regression where each data point\u2019s features will be used in the construction of the classifier boundary function). In fact,\u00a0SVM classifier depend on a very small subset of data points, those which lie closest to the boundary<\/em><\/strong>\u00a0and whose position in the hyperplane can impact the classifier boundary line. The vectors formed by these points uniquely define the classifier function and they \u2018support<\/em>\u2019 the classifier, hence the name \u2018support vector machine\u2019. This concept is shown in the following figure.<\/p>\n

<\/canvas><\/figure>\n

Read more on this \u201cIdiot\u2019s guide to support vector machines<\/a>\u201d. A nice video tutorial on SVM can be found here.<\/p>\n

\n

https:\/\/youtu.be\/N1vOgolbjSc<\/a><\/p>\n

A geometric explanation of how the SVM works:\u00a0Convex\u00a0Hull<\/em><\/strong><\/h4>\n

The formal mathematics behind the SVM algorithm is fairly complex but intuitively it can be understood by considering a special geometric construct called\u00a0convex hull<\/a>.<\/p>\n

What is Convex Hull<\/em><\/strong>? Formally a\u00a0convex hull<\/strong>\u00a0or\u00a0convex envelope<\/strong>\u00a0or\u00a0convex closure<\/strong>\u00a0of a set\u00a0X<\/em>\u00a0of points in the\u00a0Euclidean plane<\/a>\u00a0or in a\u00a0Euclidean space<\/a>\u00a0is the smallest\u00a0convex set<\/a>\u00a0that contains\u00a0X<\/em><\/strong>. However it is easiest to visualize using the\u00a0rubber band analogy<\/em>. Imagine that a rubber band is stretched about the circumference of a set of pegs (our points of interest). If the rubber band is released, it becomes wrapped around the pegs resulting in a tight border defining the original set. The resulting shape is the\u00a0convex hull<\/em>, and can be described by the subset of pegs that touch the border created by the rubber band. The idea is shown below.<\/p>\n

<\/canvas><\/figure>\n

Now, it is easy to imagine that the SVM classifier is nothing but the linear separator that bisects the line joining these convex hulls exactly mid-point.<\/p>\n

Therefore, determining the SVM classifier reduces to the problem of finding the convex hull of a set of points.<\/p><\/blockquote>\n

<\/canvas><\/figure>\n

How to determine the convex\u00a0hull?<\/strong><\/h4>\n

Picture (an animated one) says a thousand words! Therefore, let me show the algorithm used to determine the convex hull of a set of points, in action. It is called\u00a0Graham\u2019s scan<\/a>. The algorithm finds all vertices of the convex hull ordered along its boundary. It uses a\u00a0stack<\/a>\u00a0to detect and remove concavities in the boundary efficiently.<\/p>\n

<\/canvas>
\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 FIG<\/strong>: Graham\u2019s scan to find convex\u00a0hull .<\/p>\n<\/figcaption><\/figure>\n

Now, the question is how efficient this algorithm is i.e. what is the time complexity of Graham\u2019s scan method?<\/p><\/blockquote>\n

It turns out that the time complexity of Graham\u2019s scan\u00a0depends on the underlying sort algorithm<\/em><\/strong>\u00a0that it needs to employ for finding the right set of points which constitute the convex hull.\u00a0But what is it sorting to begin with?<\/em><\/strong><\/p>\n

The fundamental idea of this scanning techniques comes from two properties of a convex hull,<\/p>\n