<?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 Paul Tay on Medium]]></title>
        <description><![CDATA[Stories by Paul Tay on Medium]]></description>
        <link>https://medium.com/@paultay?source=rss-22f03e6c19f------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*gFxIDzpSXgnMa5HFyb-lpQ@2x.jpeg</url>
            <title>Stories by Paul Tay on Medium</title>
            <link>https://medium.com/@paultay?source=rss-22f03e6c19f------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 23:47:06 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@paultay/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[Using Machine Learning to boost Click Through Rate for your Ads]]></title>
            <link>https://medium.com/@paultay/using-machine-learning-to-boost-click-through-rate-for-your-ads-8c08db34714b?source=rss-22f03e6c19f------2</link>
            <guid isPermaLink="false">https://medium.com/p/8c08db34714b</guid>
            <category><![CDATA[adtech]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[advertisement]]></category>
            <category><![CDATA[digital-marketing]]></category>
            <category><![CDATA[reinforcement-learning]]></category>
            <dc:creator><![CDATA[Paul Tay]]></dc:creator>
            <pubDate>Wed, 16 Mar 2022 08:39:56 GMT</pubDate>
            <atom:updated>2022-03-16T08:39:56.044Z</atom:updated>
            <content:encoded><![CDATA[<h3>Intro</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*hKwBEQ84NCAU9WInjr0Zug.jpeg" /></figure><p>If you’re an entrepreneur using online ads to sell your product, or if you’re in the marketing department and getting hounded by your boss to increase your ad’s Click Through Rate (“CTR”), this post is FOR YOU.</p><p>We all know that finding the right ad is never easy. While you’re struggling to push your CTR up by 1%, why do other firms make achieving kick-ass CTRs look so easy? The answer is in MACHINE LEARNING.</p><h3>Case study</h3><p>Let’s say we are tasked to launch a new campaign and have received 5 different ad designs from the creative department. We reach a dilemma because they all look impressive! So, we decide to test them all out.</p><p>Just like any marketing campaign, we begin with the traditional A/B test to determine which ad is the best. We start to run all 5 ads, 2000 times per ad on 5,000 people. At the end of the test, we select the ad that has the highest CTR. However, this is all very inefficient. Running the other 4 ads drove up our marketing expenses. Also, performing the A/B test on an optimal number of persons (in theory) is impractical due to the cost incurred by stopping the test halfway just to analyze the result before deciding on the next step.</p><p>Fret no more, there is a model within the field of machine learning called REINFORCEMENT LEARNING that helps you select the perfect ad! There are tons of research papers on this subject, but the logic is pretty simple. Let me break it all down for you.</p><h3>Let’s Get Started!</h3><p>People react to ads differently. If we give 1 point every time an ad gets clicked and 0 points every time it does not, we will get a CTR per ad. This CTR is calculated by the total number of people who clicked the ad divided by the total number of people who have seen the ad. From the above case study, if 300 out of 5000 people clicked on the ad, the CTR is 6% (300/5000). Your viewers reacts to ads differently, hence, a different distribution curve per ad, some ad will be left or right skewed, some will have a higher peak (higher kurtosis) and they will all have different mean and standard deviation. When we run an A/B test, the CTR results that you’ll get would be based on the distribution curve.</p><p>Assuming the CTR for each ad is as such:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-3FYmm39olWAy1VF4cX85A.jpeg" /></figure><p>Now this is something we would not know before hand, hence the reason for A/B testing. From these graphs, you can tell that after you’re done with the A/B test, AD 5 will be selected because it has the highest mean and it is right skewed. The problem we are trying to solve today is, is there a faster way to reach this result of Ad 5 without having to run through the test on so many people before coming to a conclusion.</p><h3>Traditional A/B Testing Approach</h3><p>This is how the traditional A/B test is done.</p><p>In phase 1, we randomly select an Ad based on a uniform distribution and test it out on individual viewers. After you’re done with it, you see the results, select the best Ad and move on to phase 2, which is launching the actual campaign.</p><p>In phase 2, you run the best Ad on all your viewers.</p><p>This is not the best way to do it. Firstly, you would have wasted a lot of money by not showing the best Ad on many viewers during the A/B testing phase. Also, you would need resources to stop phase 1 before you can proceed to phase 2.</p><p>With reinforce learning, you can just run it all in one phase with zero human intervention. This is where I’m going to start talking about reinforcement learning! If you’re still here, well done! Good things come to those with patience.</p><h3>What is Reinforcement Learning?</h3><p><strong>Reinforcement learning</strong> is an area of machine learning inspired by behaviorist psychology, concerned with how software agents ought to take actions in an environment so as to maximize some notion of cumulative reward.</p><p>Imagine you have a robot and you’re teaching it to walk. What is done in the past is that a developer will give the robot a specific instruction. Example, “First, move left foot forward. Next, move right foot forward. Next, move left foot forward…” If you think about it, this is not how we train our kid to walk. We don’t tell our baby to move his leg forward one at a time to walk.</p><p>What we do is we put the baby down, and walk a short distance away from him and encourage him to walk towards you. He will fall down multiple times, but each time he falls, he will learn that this is not the right way to walk and slowly adjust accordingly until he learns how to walk. When he falls, he will feel pain (-1 point). When he reaches you, you will give him a hug and he will feel loved (+1 point). This is the main concept of how reinforcement learning works. By awarding scores to “reinforce” a certain behavior, we are training the machine to reach a desired result by giving it the flexibility to do it in any way it can and then using a scoring system to tell it what is good and what is not.</p><p>To use reinforcement learning, the developer tells the robot everything that he can do. Example, “You can move both your feet forward, backwards, sideways and the objective is to walk towards a goal in one hour. Every time you reach your goal, you will be rewarded points based on how fast you take to reach the goal”. What happens next is that the robot will try and move forward, backwards and sideways. On the first few attempts, it will not know what he is doing and might just walk around aimlessly. After awhile, he starts to “accidentally” reach the goal after walking back and forth multiple times. This is when he starts getting points. Eventually, he will realize that the way to get the most number of points (reach the goal in the shortest amount of time) is to just walk straight.</p><p>In summary, reinforcement learning is about trying to let the robot learn in the same way a human learns.</p><h3>Upper Confidence Bound</h3><p>Upper Confidence Bound is one of the reinforcement learning models that I’ll be using today to improve our CTR at the onset. Upper Confidence Bound refers to the idea that the Ad selected for the next user will be chosen based on the highest Upper Confidence Level of all the Ads.</p><p><strong>At the start (no. of viewers tested = 0)</strong></p><p>At the start, since we have not tested anything, the observed mean, standard deviation and confidence level for each Ad type will start off the same.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-3FYmm39olWAy1VF4cX85A.jpeg" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*G5YHEr70YHnAHOYlUzhhkQ.jpeg" /></figure><p><strong>1st test (no. of viewers tested = 1)</strong></p><p>Since the confidence level for each Ad Type is the same, the model will randomly select one Ad to show to the user. After the user sees the Ad, he will either click it or ignore it. This will impact the CTR of that Ad and thus, shift the distribution curve of that Ad. Assuming the user was shown Ad 2 and chose to ignore the Ad, the distribution curve of Ad 2 shifts down and the confidence band becomes smaller. The reason why the distribution curve shifts down is because the expected mean decreases. The reason why the confidence band decreases is because there is now more entries concentrated nearer the mean, hence, the standard deviation decrease, causing the confidence interval to shrink.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*YaZaS_ZKkKiOQlHc2K40kw.png" /></figure><p><strong>2nd test (no. of viewers tested = 2)</strong></p><p>Assuming the next user was shown Ad 4 and chose to click the Ad, the distribution curve of Ad 4 shifts up and the confidence band becomes smaller</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Psuz7X38dZ0-uIZxQuRkLQ.png" /></figure><p><strong>3rd test (no. of viewers tested = 3)</strong></p><p>What happens now is that the model will select either Ad 1, 3 or 5 to show next since it has the highest Upper Confidence Level. Although the distribution curve of Ad 4 moves up, the confidence level shrinks, hence, the Upper Confidence Level is lower than the other 3 untested Ad.</p><p>Assuming the next user was shown Ad 5 and chose to click the Ad, the distribution curve of Ad 5 shifts up and the confidence band becomes smaller.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*HfSIaB9cElR8-XT1GCnLyA.png" /></figure><p>This same logic goes on and on for every new user. Due to the law of large numbers, with more and more tests, the observed mean will move towards the expected mean and the confidence interval shrinks even more as the distribution curve starts to take shape.</p><p><strong>5000th test (no. of viewers tested = 5000)</strong></p><p>By now, the distribution curve is more or less formed and the Observed Mean is very close to the Expected Mean. For this round, the model selects the highest Upper Confidence Level. Since most viewers that sees Ad 5 will click the ad (due to the high mean expected CTR), the distribution curve of Ad 5 will move closer and closer towards the mean and the confidence level will continue shrinking. Since the Upper Confidence Level for Ad 5 will be the highest on most of the rounds after this, the model will select Ad 5 on many more occasions compared to the other Ads. There will be a few instances where the confidence level of Ad 5 becomes so small until the highest Upper Confidence level comes from Ad 4, but when Ad 4 is being tested, it’s confidence level shrinks too. This goes on and on until you have run out of marketing budget.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*w1AlBjHIgiqTiKY0azr3yw.png" /></figure><p>Now that you understand the concept behind Upper Confidence Bound, let’s put it to the test! No point just knowing the theory without learning how to code this out! This is where it gets interesting!</p><h3>Creating an Upper Confidence Bound model using Python</h3><p>I’ll be using python for this example but you can build this on R, Mathlab, etc.</p><h4>Defining the Problem</h4><ul><li>We have d number of Ads. These are the Ads that will be displayed to viewers.</li><li>Each time a user sees an Ad, it will be marked as one round.</li><li>At each round <em>n</em>, we will choose one Ad to display to that user.</li><li>At each round <em>n</em>, ad <em>x</em>, will give a reward of either yes (1), or no (0). ri (<em>n</em>) ∈ {0,1}: ri (<em>n</em>) =1 if the user clicks on ad x and 0 if he does not.</li><li>Our goal is to maximize the total reward we get over the total number of rounds</li></ul><h4>Solution</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*jVUfPt5mJRlJyMh8Nuk1WQ.jpeg" /></figure><h3>Writing the Python Script</h3><pre>&#39;&#39;&#39;Step 1&#39;&#39;&#39;<br>#Importing the libraries<br> <br>import numpy as np<br>import matplotlib.pyplot as plt<br>import pandas as pd<br>import math<br> <br>&#39;&#39;&#39;Step 2&#39;&#39;&#39;<br>#Importing the dataset <br>&#39;&#39;&#39;﻿<br>(If you plan to operationalize this, your dataset can be pulled straight <br>﻿from your database once every few minutes or once after every new viewer sees the ad. <br>So that we can constantly update the model. <br>For this example, I’ll be using a csv file with test results generated from a pre-defined distribution curve. <br>Of course my model will not know this pre-defined distribution curve to simulate a real life scenario)<br>&#39;&#39;&#39;<br>﻿ <br>dataset = pd.read_csv(&#39;Marketing_ads.csv&#39;) <br> <br>&#39;&#39;&#39;Step 3&#39;&#39;&#39;<br>#Implementing the Upper Confidence Bound Model<br> <br>N = 10000           #Total number of Test<br>d = 5                    # Number of ads<br>Selected_Ad = [0]<br>no_of_selections = [0] * d<br>Sum_rewards = [0]*d<br>Total_rewards = 0<br>for n in range(0,N):<br>    ad = 0<br>    max_upper_bound = 0<br>    for i in range(0,d):<br>        if (no_of_selections[i]&gt;0):<br>            average_reward = Sum_rewards[i]/no_of_selections[i]<br>            delta_i = math.sqrt(3/2 * math.log(n+1)/no_of_selections[i])<br>            upper_bound = average_reward + delta_i<br>        else:<br>            upper_bound =1e400<br>        if upper_bound &gt; max_upper_bound:<br>            max_upper_bound = upper_bound<br>            ad = i<br>    Selected_Ad.append(ad)<br>    no_of_selections[ad] = no_of_selections[ad] + 1<br>    reward = dataset.values[n,ad]<br>    Sum_rewards[ad] = Sum_rewards[ad] + reward<br>Total_rewards = Total_rewards + reward<br> <br> <br>&#39;&#39;&#39;Step 4&#39;&#39;&#39;<br>#Seeing the results<br> <br>plt.hist(Selected_Ad, bins=5)<br>plt.title(&#39;Histogram of ads selected&#39;)<br>plt.xlabel(&#39;Ads&#39;)<br>plt.ylabel(&#39;Number of times Ad was selected&#39;)<br>plt.show()</pre><h3>Comparing the Results of A/B testing VS Upper Confidence Bound method</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*A81PHro7ycYBxH4iMP8UZw.jpeg" /></figure><p>When we do the traditional A/B testing approach, you can see that the 5 different ads are showing roughly the same number of times, whereas the Upper Confidence Bound model shows Ad 5 the most number of times. This is because it learns from past user inputs and make amendments on its own while the traditional A/B testing model does not. By doing so, Ad 5 gets shown much more than the rest because it has the highest probability of getting clicked given its distribution. This explains why the CTR of the Upper Confidence Bound is higher than the traditional A/B testing.</p><p>The difference is minimal because the pre-set distribution curves that I’ve used are not drastically different. But in the real world, the distribution curves might be extremely different and the difference in CTR between these 2 models might be very different and thus, costing you a lot of wasted marketing expenses if you continue using the traditional A/B testing method.</p><h3>Thanks for Reading</h3><p>I hope you’ve enjoyed this article. Boosting CTR is just one of the many ways machine learning models can be used. If you’re interested to view my 2 models (UCB and Traditional A/B testing) in python and R, as well as the data set I’ve used to create the test set, please feel free to leave your email in the comments section and I’ll send it to you.</p><p>This is the first of many more articles to come! If you’d like me to write an article on how you can apply machine learning for your work, state your business or industry in the comments section and I’ll try my best to do so for as many industries as possible. I’d also appreciate it if you could share this post with your friends!</p><p>P.S. Follow this link to see how reinforcement learning was used to create a Dota 2 bot that can beat top professional players ( <a href="https://www.youtube.com/watch?v=92tn67YDXg0)">https://www.youtube.com/watch?v=92tn67YDXg0)</a>.</p><p>Yes, I’m a huge Dota fan!</p><p>Machine learning is gradually getting popular and becoming mainstream in all kinds of industries. The value of these models will only become stronger as we start to collect more and more data. The introduction of Internet of Things will lead to an exponential increase in data collected and the one who owns and knows how to use these data will be King. As the saying goes, “Data is the new Oil”.</p><p><em>Originally published at </em><a href="https://www.linkedin.com/pulse/using-machine-learning-boost-click-through-rate-your-ads-tay/"><em>https://www.linkedin.com</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8c08db34714b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[The Math behind Match Making]]></title>
            <link>https://medium.com/@paultay/the-math-behind-match-making-69a845503f91?source=rss-22f03e6c19f------2</link>
            <guid isPermaLink="false">https://medium.com/p/69a845503f91</guid>
            <category><![CDATA[optimization]]></category>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[algo]]></category>
            <dc:creator><![CDATA[Paul Tay]]></dc:creator>
            <pubDate>Wed, 16 Mar 2022 08:00:52 GMT</pubDate>
            <atom:updated>2022-03-16T08:00:52.471Z</atom:updated>
            <content:encoded><![CDATA[<h3>Overview</h3><p>It’s New Year’s Eve, you’re out partying with your Bros. In the club, you see a group of girls strutting their stuff on the dance floor. It’s the festive season, and there’s no guys around them. There can only be one conclusion, THEY ARE ALL SINGLE! Ready to mingle, and finding the “Love worth dying for”. You glanced at your bros, they wink back at you. 4 of them, 4 of you. It’s perfect!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*sy5ZKrxSlAczpXT500hpxA.gif" /></figure><p>But Wait… so who should talk to which girl? What are the chances that each of you like a different girl, and they’ll be no conflict? FAT HOPE! Everybody wants to hit on the hottest girl in the group. Does this situation sounds familiar? How do you ensure that each guy is matched to a girl so that everybody leaves the club happy. In fact, this situation was even highlighted in the movie, A Beautiful Mind, which documents the life of John Nash, the famous Nobel Price Economist who created the Nash Equilibrium. Here’s a clip from youtube explaining this problem.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FLJS7Igvk6ZM%3Ffeature%3Doembed&amp;display_name=YouTube&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DLJS7Igvk6ZM&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FLJS7Igvk6ZM%2Fhqdefault.jpg&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/f0e44f0186606f18b69e32bae4808b35/href">https://medium.com/media/f0e44f0186606f18b69e32bae4808b35/href</a></iframe><p>Yes, the theory makes sense, but it does not teach us how to operationalise this idea. I’m sure many guys out there face this problem as well. If you don’t, you are either a bad bro or a clueless one.</p><p>Instinctively, we have assigned a “Likeness” score for each girl. If you’re head over heels for “Girl 1”, you’ll give her a “Likeness” score of 10. If you’re just interested in her, you’ll give her a “Likeness” score of 7, if you’re grossed out by her, you’ll give her a “Likeness” score of 1. The problem we’re trying to solve is, how do we pair a guy to a girl so as to maximise the overall “Likeness” score of the group. This article will be touching on:</p><ol><li>The concept of Bipartite Graph Matching</li><li>Using the Hungarian Algorithm, an integer programming algorithm, to solve the match making problem efficiently</li></ol><h3>Case Study</h3><p>You’re now in the club, there’s 4 single girls and 4 single guys. The easiest way to create pairs would be an uncoordinated free-for-all, where each guy will just hit on the girl he likes the most. However, this is actually not a very efficient way of doing so. Here are some reasons why:</p><ul><li>If 2 guys like the same girl, they will be a fight, and both will end the night alone, with a bleeding nose.</li><li>Assume “Guy A” likes “Girl 1” and “Girl 2”, while “Guy B” only likes “Girl 2”. If “Guy A” hits on “Girl 2”, then “Guy B” will be left with “Girl 1” which is not who he likes. Instead, if “Guy A” hits on “Girl 1”, then “Guy B” would be able to hit on “Girl 2”, and they’ll both end up dancing with the girl they like.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/576/1*I_IybBQJOwdUtPqw3EvHTw.png" /></figure><ul><li>Assume “Guy A” assigns a “Likeness” score of 10 to “Girl 1” and 9 to “Girl 2”. “Guy B” assigns a “Likeness” score of 10 to “Girl 1” and 7 to “Girl 2”. If “Guy A” hits on “Girl 1”, and as a result “Guy B” would have to hit on “Girl 2”, this will give the group a maximum score of 17 (10+7), which is not the highest possible score. With a bit of planning, “Guy A” hits on “Girl 2” and “Guy B” hits on “Girl 1”, then the maximum score would be increase to 19 (10+9). The 2nd result is better for the group.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/700/1*OiSqj1NPLXVwQpm9f2Xa8Q.png" /></figure><p>Hence, the objective is to create pairs in a way that maximises the overall “Likeness” Score of the group.</p><p>Let’s say we have collected some data on each guy, and we now know the “Likeness” score they have assigned to each girl.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/575/1*4yCLqsm596rHrZJ8NCxpHg.png" /></figure><p>From the data, we can tell that:</p><p><strong>The Guys</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Fu9AQUS2urCnhsGPg1s8uQ.png" /></figure><ul><li>“Guy A”, “Guy B”and “Guy C” are typical guys, where they have some preferences, and would not mind dating <strong>1 or 2 girls</strong>, but definitely, not <strong>ALL</strong> the girls.</li><li>“Guy D” is the typical playboy, who don’t really have a preference and would like to hit on <strong>ALL </strong>the girls.</li></ul><p><strong>The Girls</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*HWhilB3zkhJzo4bZX2AcAw.png" /></figure><ul><li>“Girl 1” is the popular girl, where all the guys would want to date her.</li><li>“Girl 2” is the plain Jane where nobody hates her, but not many would go all out to date her as well.</li><li>“Girl 3” is the type of girl that only attracts a particular kind of guy. You either love her or hate her.</li><li>“Girl 4” is the average girl that will not be the first choice for most guys, but won’t be their last choice either</li></ul><p>Based on this, you want to create an algorithm that satisfy 2 criteria:</p><ol><li>Correctness — It needs to maximise the overall “Likeness” Score of the group.</li><li>Efficiency — The algorithm needs to be efficient. If your algorithm is inefficient and takes too long to run, by the time the results are out, the night has ended, and all the girls are gone.</li></ol><p>The easiest method to solve this is to use “Brute Force” algorithm, where you find all possible permutations and calculate the overall score for each permutation. eg.</p><ol><li>Permutation 1: “Guy A” — “Girl 1”, “Guy B” — “Girl 2”, “Guy C” — “Girl 3”, “Guy D” — “Girl 4”. Giving a total score of 10+5+2+9 = 26</li><li>Permutation 2: “Guy A” — “Girl 2”, “Guy B” — “Girl 3”, “Guy C” — “Girl 4”, “Guy D” — “Girl 1”. Giving a total score of 7+9+7+9 = 32. etc</li></ol><p>The problem with doing it this way is that it is very inefficient where if the number of guys and girls increases, the algorithm running time increases exponentially, in more precise terms, the time complexity of this Brute Force algorithm is O(V!), where V is the number of vertices, ie. number of guys/girls, which is pretty bad. That means, if there’s 4 pairs, you’ll need to generate 24 (4!) permutations. If there’s 10 pairs, you’ll need to generate 3628800 (10!) permutations.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*O1Rq-sCdhvi3fnx6SLnrTA.png" /></figure><p>Although the “Brute Force” method will give a correct result, it is not a scalable solution as the time needed for the algorithm to run will be extremely large if there are many guys/girls. Is there a way to create a more efficient algorithm that runs on Polynomial Time, ie. an algorithm that does not increase exponentially with an additional of a guy/girl, without compromising on the correctness of the algorithm? OF COZ! This is where the Hungarian Algorithm comes in.</p><p>However, before I explain what the Hungarian Algorithm is, I’ll need to first explain the concept of a Bipartite Graph, which will be used in the Hungarian Algorithm.</p><h3>Bipartite Graph</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/311/1*tagJgzTQ75nwOSnwtpyTnw.png" /></figure><p>A <strong>bipartite graph</strong> also called a <strong>bi-graph</strong>, is a set of graph vertices, i.e, points where multiple lines meet, decomposed into two disjoint sets, meaning they have no element in common, such that no two graph vertices within the same set are adjacent.</p><p>In lay man terms, no 2 purple nodes and no 2 blue nodes are connected to each other. Every pair consists of 1 purple node joined to 1 blue node.</p><h3>Hungarian Algorithm</h3><h4>Overview</h4><p>The <strong>Hungarian matching algorithm</strong>, also called the <strong>Kuhn-Munkres algorithm</strong>, is an algorithm that can be used to find maximum-weight matchings in bipartite graphs, which is sometimes called the assignment problem. A bipartite graph can easily be represented by an adjacency matrix, where the weights of edges are the entries. Interestingly, the Mathematician that published this paper is Harold W. Kuhn, a graduate student of John Nash, the guy who created the Nash Equilibrium. Economics, Mathematics and Computer Science are pretty complementary fields.</p><h4>The Math behind it with proof</h4><p>The Hungarian algorithm can also be executed by manipulating the weights of the bipartite graph in order to find a stable, maximum (or minimum) weight matching. This can be done by finding a feasible labelling of a graph that is perfectly matched, where a perfect matching is denoted as every vertex having exactly one edge of the matching.</p><p>Here’s the proof.</p><p><strong>A feasible labelling on a perfect match returns a maximum-weighted matching.</strong></p><p>Suppose each edge e in the graph G connects two vertices, and every vertex v is covered exactly once. With this, we have the following inequality:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/367/1*nQp5QZlVh_UbPaQP2Yiu1Q.png" /></figure><p>Where M’ is any perfect matching in G created by a random assignment of vertices, and l(x) is a numeric label to node x.</p><p>So w(M’) ≤ w(M) and M is optimal.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/530/1*8HJ0abdO52Di9zig53b0fw.png" /></figure><h3>Implementing this Algorithm</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/543/1*aaOma1HEtg_RPktS0mgkPg.png" /></figure><p><strong>Augmenting the matching</strong></p><ol><li>A path is <strong>augmenting</strong> for M in G­_l if it alternates between edges in the matching and edges not in the matching, and the first and last vertices are free vertices, or unmatched, in M. We will keep track of a candidate augmenting path starting at the vertex u.</li><li>If the algorithm finds an unmatched vertex v, add on to the existing augmenting path p by adding the u to v segment.</li><li>Flip the matching by replacing the edges in M with the edges in the augmenting path that are not in M (in other words, the edges in E_l — M).</li></ol><p><strong>Improving the labelling</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/598/1*P7PWW-amL6PLrtGVuvCBBQ.png" /></figure><p><strong>Putting it all together</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/587/1*GLu_qxDd2M7qZ7X8JLp_mw.png" /></figure><h3>Operationalising it in Python</h3><ul><li>Create and Visualise the Bipartite Graph based on the table we have collected earlier on.</li></ul><pre># Importing the libraries<br>import math<br>import networkx as nx<br>import matplotlib.pyplot as plt<br><br># Create the bipartite graph, matching Guy - A,B,C,D with Girl -1,2,3,4, and assigning the score to each pair<br>bipar_edges = [<br>    (&#39;A&#39;, 1, 10), (&#39;A&#39;, 2, 7), (&#39;A&#39;, 3, 1), (&#39;A&#39;, 4, 5),<br>    (&#39;B&#39;, 1, 9), (&#39;B&#39;, 2, 5), (&#39;B&#39;, 3, 9), (&#39;B&#39;, 4, 4),<br>    (&#39;C&#39;, 1, 10), (&#39;C&#39;, 2, 5), (&#39;C&#39;, 3, 2), (&#39;C&#39;, 4, 7),<br>    (&#39;D&#39;, 1, 9), (&#39;D&#39;, 2, 8), (&#39;D&#39;, 3, 8), (&#39;D&#39;, 4, 9)]<br><br><br># Visualizing the bipartite graph<br>node_left = []<br>node_right = []<br>node_pos = {}<br>node_pos_alt = {}<br>range_length = int(math.sqrt(len(bipar_edges)))<br>for i in range(1, 1+range_length):<br>    node_left.append(chr(ord(&#39;A&#39;) + i - 1))<br>    node_right.append(i)<br>    node_pos[chr(ord(&#39;A&#39;) + i - 1)] = (0, 4 - i)<br>    node_pos[i] = (1, 4 - i)<br>    node_pos_alt[chr(ord(&#39;A&#39;) + i - 1)] = (-0.15, 4 - i)<br>    node_pos_alt[i] = (1.15, 4 - i)<br><br><br>wbg = nx.DiGraph()<br>wbg.add_weighted_edges_from(bipar_edges)<br><br><br>plt.figure(figsize = (4, 6))<br>nx.draw_networkx(wbg, pos = node_pos)<br>nx.draw_networkx_edge_labels(wbg, pos = node_pos, edge_labels = nx.get_edge_attributes(wbg, &#39;weight&#39;), label_pos = 0.2)<br>plt.show()</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/264/1*MLnBv5K9vW08SiTmloU0jA.png" /></figure><p>From the graph, you can see the Vertices (Red Nodes) and the Edges (Black Lines), with a weight (The number assigned to each Edge). This is the graphical representation of the table. Which will be the format we’ll be using for the algorithm</p><ul><li>Implement the Hungarian Algorithm</li></ul><pre>node_weight = {}<br>for i in node_left:<br>    node_weight[i] = 0<br><br><br>for i in node_right:<br>    node_weight[i] = 0<br><br><br>edge_weight = {}<br>for i in bipar_edges:<br>    edge_weight[(i[0], i[1])] = i[2]<br><br><br>for u in node_left:<br>    row_max = - math.inf<br>    for v in node_right:<br>        row_max = max(row_max, edge_weight[(u, v)])<br>    node_weight[u] = row_max<br>    for v in node_right:<br>        edge_weight[(u,v)] -= row_max<br><br><br>for v in node_right:<br>    col_max = - math.inf<br>    for u in node_left:<br>        col_max = max(col_max, edge_weight[(u,v)])<br>    node_weight[v] = col_max<br>    for u in node_left:<br>        edge_weight[(u,v)] -= col_max<br><br><br>ecolor = []<br>for e in wbg.edges():<br>    if edge_weight[(e[0], e[1])] == 0:<br>        ecolor.append(&#39;r&#39;)<br>    else:<br>        ecolor.append(&#39;k&#39;)</pre><ul><li>Plot the Bipartite Graph</li></ul><pre>plt.figure(figsize = (4, 6))<br>plt.xlim((-0.25, 1.25))<br>nx.draw_networkx(wbg, pos = node_pos, edge_color = ecolor)<br>nx.draw_networkx_labels(wbg, pos = node_pos_alt, labels = node_weight)<br>nx.draw_networkx_edge_labels(wbg, pos = node_pos, edge_labels = edge_weight, label_pos = 0.2)<br>plt.show()</pre><ul><li>Create the Match Function</li></ul><pre>def match(g, u, reachable):<br>    if u in path:<br>        return False<br>    path.append(u)<br>    for v in g.neighbors(u):<br>        if partner[v] == 0 or match(g, partner[v], reachable):<br>            partner[u] = v<br>            partner[v] = u<br>            return True<br>    path.pop()<br>    reachable.add(u)<br>    if partner[u] != 0:<br>        reachable.add(partner[u])<br>    return False</pre><ul><li>Running the Iterations</li></ul><pre>while True:<br>    tmpg = nx.Graph()<br>    tmpg.add_nodes_from(wbg.nodes())<br>    for k, v in edge_weight.items():<br>        if v == 0:<br>            tmpg.add_edge(k[0], k[1])<br>    partner = {}<br>    for u in tmpg.nodes():<br>        partner[u] = 0<br>    num_matching = 0<br>    reachable = set()<br>    for u in node_left:<br>        path = []<br>        num_matching += match(tmpg, u, reachable)<br>    if num_matching == len(node_left):<br>        for u in node_left:<br>            print(u, &#39;is assigned to&#39;, partner[u])<br>        break<br>    vcover_left = []<br>    for u in node_left:<br>        if u not in reachable:<br>            vcover_left.append(u)<br>    vcover_right = []<br>    for v in node_right:<br>        if v in reachable:<br>            vcover_right.append(v)<br>    print(&#39;vcover_left:&#39;, vcover_left)<br>    print(&#39;vcover_right:&#39;, vcover_right)<br>    res_max = - math.inf<br>    for e, v in edge_weight.items():<br>        if e[0] not in vcover_left and e[1] not in vcover_right:<br>            res_max = max(res_max, v)<br>    for u in node_left:<br>        if u not in vcover_left:<br>            node_weight[u] += res_max<br>            for v in node_right:<br>                edge_weight[(u, v)] -= res_max<br>    for v in vcover_right:<br>        node_weight[v] -= res_max<br>        for u in node_left:<br>            edge_weight[(u, v)] += res_max<br>    ecolor = []<br>    for e in wbg.edges():<br>        if edge_weight[(e[0], e[1])] == 0:<br>            ecolor.append(&#39;r&#39;)<br>        else:<br>            ecolor.append(&#39;k&#39;)<br>    plt.figure(figsize = (4, 6))<br>    plt.xlim((-0.25, 1.25))<br>    nx.draw_networkx(wbg, pos = node_pos, edge_color = ecolor)<br>    nx.draw_networkx_labels(wbg, pos = node_pos_alt, labels = node_weight)<br>    nx.draw_networkx_edge_labels(wbg, pos = node_pos, edge_labels =   edge_weight, label_pos = 0.2)<br>    plt.show()</pre><h3>The result</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/279/1*HGe6jFekcUqkTKpUFDimGg.png" /></figure><p>From the graph you can see that the best outcome is seen from the red lines. To further explain what the graph means, this algorithm is trying to find pairs (1 guy connected to 1 girl). Focusing only on the red lines, if we start with “A”, it points to “1” and “2”. Let’s try to pair “A” to “1” and see where we end up. So if we create a sub-graph, we’ll get “A-1-C”, which is an invalid pair as we have 2 guys and 1 girl. If we try the other combination, we have a sub-graph of “A-2-D-4”. This is a valid combination as we have 2 pairs, consisting of “A-2” and “D-4”.</p><p>Next, we move to “B” there’s only 1 red line pointing out, so the pair is “B-3”. The next pair is “C-1”.</p><p>Thus, the solution will be:</p><p>1) Guy A to Girl 2, score of 7</p><p>2) Guy B to Girl 3, score of 9</p><p>3) Guy C to Girl 1, score of 10</p><p>4) Guy D to Girl 4, score of 9</p><p>If you sum up all the scores, you’ll get an overall score of 35. Don’t believe that this is the best possible score, try to run each permutation, you should get a highest total score of 35 as well.</p><p>Based on the aforementioned pairs, there is value in matching the right guy to the right girl so as to maximise the total “Likeness” score across the group. Doing so will ensure most guys will get the girl they desire the most, and for those that have to compromise, they know that they’re doing it for the greater good, and that’s the best possible combination for the group.</p><h3>Evaluating the Time Complexity of the Hungarian Algorithm</h3><p>Now that we understand how the Hungarian Algorithm works, i’ll try to prove mathematically that it is in fact more efficient than the “Brute Force” method.</p><ul><li>At each a or b step, the algorithm adds an edge to the matching and this happen O(|V|) times.</li><li>It takes O(|V|) time to find the right vertex for the augmenting (if there is one at all), and it is O(|V|) time to flip the matching.</li><li>Improving the labelling takes O(|V|) time to find d_l and to update the labelling accordingly.</li><li>We might have to improve the labelling up to O(|V|) times if there is no augmenting path. This makes for a total of O(|V| squared ) time.</li><li>In all, there are O(|V|) iterations each taking O(|V|) work, leading to a total running time of O(|V| power 3)</li></ul><p><strong>We have increased the efficiency from a “Brute Force” method of O(V!) to the “Hungarian Algorithm” method of O(|V| power 3)</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/966/1*lplNiQIueyoN4yhZcXAJ4g.png" /></figure><h3>Conclusion</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/556/1*JXl_M9HcLqj96TB_j1FEHQ.png" /></figure><p>Viola! We now have 4 happy couples dancing the night away! Matched to the right person and in a short amount of time, with much left over time for some confidence boosting Tequila shots before hitting on the girl. All thanks to the Hungarian Algorithm!</p><p>For your next boys night out, try implementing this solution, and hopefully, you’ll have a more enjoyable evening with your bros.</p><p>This algorithm has many other use cases apart from just satisfying a group of desperate guys ;) It can be used for job assignment problems. 1) A project manager that needs to assign people to different jobs, 2) Ride Hailing company, needing to assign drivers to passengers, 3) a tuition agency, assigning tutors to students, etc.</p><p>With that, i hope you enjoy this article as much as i enjoyed writing it, and I wish you a Merry Christmas and a Happy New Year!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/930/1*BJQVAOphpE86MYOElnKpKw.png" /></figure><p><em>Originally published at </em><a href="https://www.linkedin.com/pulse/math-behind-match-making-paul-hong-tay-cfa/"><em>https://www.linkedin.com</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=69a845503f91" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>