<?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 Saikat Kumar Dey on Medium]]></title>
        <description><![CDATA[Stories by Saikat Kumar Dey on Medium]]></description>
        <link>https://medium.com/@saikatkumardey?source=rss-41d92974c91------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/proxy/1*TGH72Nnw24QL3iV9IOm4VA.png</url>
            <title>Stories by Saikat Kumar Dey on Medium</title>
            <link>https://medium.com/@saikatkumardey?source=rss-41d92974c91------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Mon, 16 Nov 2026 17:43:41 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@saikatkumardey/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[Ensemble Modelling in Personalized Ranking]]></title>
            <link>https://medium.com/data-science-for-everyone/ensemble-modelling-in-personalized-ranking-87dca2a54a23?source=rss-41d92974c91------2</link>
            <guid isPermaLink="false">https://medium.com/p/87dca2a54a23</guid>
            <category><![CDATA[artificial-intelligence]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[recommendation-system]]></category>
            <dc:creator><![CDATA[Saikat Kumar Dey]]></dc:creator>
            <pubDate>Sun, 10 Mar 2019 16:23:15 GMT</pubDate>
            <atom:updated>2019-04-22T05:20:00.330Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*V1YqVr0JPpftgvHkavk2uA.png" /><figcaption>Amazon Prime Video Recommendations</figcaption></figure><p>Ranking = Recommendation presented as a list.</p><p>In my article <a href="https://medium.com/data-science-for-everyone/how-does-recommendation-systems-work-f3e1c96b14e8">How do Recommendation Systems work?</a> we learned different approaches to building recommendation systems. In this post, we’ll learn about stacking different models together to build an Ensemble Ranking Model.</p><p><strong>What’s an Ensemble?</strong></p><p>It’s a technique of combining multiple models in an intelligent way. We use this technique to improve model performance and/or reduce the chances of selecting a poor one.</p><p>Let’s say that you want to watch some movies over the weekend. You select a list of 10 movies and ask your friends to rank them. Your friends have their own ideas about your tastes/preferences. So, all of them gives you a ranked list of movies that you should watch next. You don’t have time to watch all of them. You want to watch only 3. So, how do you figure out the top 3 movies based on their lists?</p><p>Here’s a single algorithm. Pick a rank-list, give the top movie score of 1 and give the last movie a score of 0. Everything in between should be a linearly spaced number in decreasing order. Now, for every movie, find out its score from all of the rank-lists and average it. You get a combined score for every movie. Simply, order them in decreasing order of their score and pick top 3. I got this idea from <a href="https://stackoverflow.com/questions/6352212/how-to-merge-a-collection-of-ordered-preferences">Stack-Overflow</a>.</p><p>In our simple algorithm, we provide equal importance to the ranking of all of our friends. This is not true in real life. Some of our friends might know about our preferences better than others. So, their ranking should be given more weight/importance.</p><p>Now, map this scenario to our ML world.</p><blockquote>Friends = Individual Models<br>Ensemble = A technique to combine ranking of individual models<br>Weight = Importance to be given to each model in the ensemble.</blockquote><p>Let’s say that we want to build a recommendation system for our streaming service, WatchFlix. We have a list of users <strong>U</strong> and a list of movies <strong>M</strong>. We want to recommend k movies to the user so that the likelihood of the user watching one of them is high.</p><p>What kind of data do we have? We have implicit feedback from the user. This means that they have not rated any movie explicitly. So, we only know about the movies that they’ve watched on our platform.</p><p><strong>Data Available</strong></p><ul><li><strong>Interaction</strong>: Which movies were watched by the user in the past.</li><li><strong>Item Features</strong>: Information about the movie like Genre, Directory, Year Released, Actors, etc.</li><li><strong>User Features</strong>: Age,Gender,Country,Medium of consumption (mobile/website), Plan subscribed (Basic, Standard, Premium), etc.</li></ul><p>Given all of these pieces of information, we have a lot of different ways of building recommendation systems. We’ll quickly recap different approaches and then go on to building the ensemble.</p><h3><strong>Feature Representation</strong></h3><p>First things first, let’s create different matrices to represent our features.</p><h4>User Features Matrix</h4><p>It contains a user’s features. We should one-hot-encode it while modeling.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/896/1*QNu2ZipZGOSQwcDYztshvg.png" /></figure><h4>User Preferences Matrix</h4><p>It contains a user’s affinity for attributes of movies based on his watch history.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*LXsKiLZb4ONf8BMKov5_Zg.png" /></figure><h4>Item Features Matrix</h4><p>It contains movie-related attributes.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*4I5HM_H-xvTqFbA7sz-q-A.png" /></figure><h3>User-Item interaction Matrix</h3><p>Each cell contains a flag representing whether a user has watched a particular movie or not.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ZvxInApwyUYRlfZe38-mpg.png" /></figure><h3>Models</h3><p>Let’s quickly recap several approaches that we could use to build recommendation systems. Our ensemble model could use some or all of these approaches.</p><h3>Model 1: Popularity Based Recommendation System</h3><p>We just create a list of most watched movies of all time and show it to every user.</p><h3>Model 2: Classification Based Approach</h3><p>We train a classifier which takes user &amp; movie features as input and returns a score that tells us how likely is this user to watch this movie.</p><h3>Model 3: Similarity-Based Recommendation System</h3><p>We have a vector representation of each user and item as a vector. So we can simply compute the similarity between the vectors using something like cosine-similarity.</p><h3>3.1 user-user similarity</h3><p>For a given user, find other similar users. Recommend the movies that they watched, which haven’t been watched by the current user.</p><h3>3.2 item-item similarity</h3><p>For a given movie, find other similar movies. Recommend the movies which haven’t been watched by the current user.</p><h3>3.3 user-item similarity</h3><p>We compute the similarity between user-preferences and item-features. This means that we figure out movies similar to the user’s tastes.</p><h3>Model 4: Matrix Factorisation</h3><p>We figure out the latent embeddings for user and movies. Embeddings of a user represent latent user tastes in movies. Embeddings of a movie represent the attributes of a movie. Latent means “hidden”. The latent vectors/embeddings wouldn’t make much sense to us in isolation (just like the hidden layers of a neural-net doesn’t). However, the latent vectors are representations of what the model has learned about a particular user/item. We tune them by penalizing/rewarding the final outcome, ie, how good are the recommendations. These embeddings have been learned from the User-Item interaction matrix using matrix factorization algorithms.</p><p>While recommending new movies to the user, we multiply the latent vector of a user with all latent item vectors and display top-k items to the user based on the score.</p><h3>Model 5: Hybrid Models</h3><p>Along with the user-item interactions matrix, we could provide side-features (user &amp; item features) available to us during training. This might help in better embeddings of user &amp; items.</p><h3>Model 6: Ensemble</h3><p>This is what this article is about. We have different algorithms which model various aspects of user/item/interaction features while generating a rank-list. How do we combine the power of the individual models?</p><p>The different models described above return a score vector, using which we can rank the movies.</p><p>For example,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/980/1*NQbFjfY56s-C0glbUpR2jQ.png" /></figure><p>According to these models, the ranking of movies would be,</p><pre>Popularity : [Titanic, Avengers, Iron-Man, Spider-Man ]<br>Similarity : [Iron-Man, Spider-Man, Avengers, Titanic]<br>Matrix-Factorisation: [Avengers, Iron-Man, Spider-Man, Titanic]</pre><p>We want to combine these rank-lists into one.</p><p>Now, there can be different ways of <a href="https://en.wikipedia.org/wiki/Ensemble_learning">Ensemble learning</a>. In this article, we talk about Stacking. We formulate stacking as a supervised learning problem.</p><p>Let’s define a score function which we want to learn,</p><pre>score(u,v) = W1*M1(u,v) +.....+ Mi(u,v) + ..... + Wn * Mn(u,v)</pre><pre>where,</pre><pre>score(u,v) = probability that the user u will watch movie v.</pre><pre>wi = weight of model Mi</pre><pre>Mi(u,v) = score given to a (user,movie) combination given by model Mi.</pre><p>Great! So we want to learn this function <strong><em>score()</em></strong> using the predictions of the individual models. In order to do that, we need to create features and target from historical data. Then, we can train a machine learning model to optimize for a metric we care about.</p><p>Good, so how do we go about creating features? What are the targets that our model should predict? As you can see from the score() function, our features should be a vector <strong>[M1, M2, M3,…Mn]</strong> and our target should be 0/1 (0 = user didn’t watch the movie, 1 = user watched the movie). Now, we can treat this as a classification problem and train a model which will predict a probability that a user <strong>u</strong> will watch movie <strong>v</strong>.</p><p>Our features are predictions from individual models. For a (user, movie) combination we need to get predictions from each model in order to create the feature vector for the ensemble.</p><p><strong>How do we choose the (user, movie) combination?</strong> We use sampling techniques. For every user, we create a list of positive and negative examples. Positive examples are the movies watched by the user. Negative examples are the ones that weren’t. The number of movies watched by any given user is negligible compared to the total number of movies available on our platform. Hence, we need to limit the number of negative examples that we sample.<br>Now, for every (user,movie_sample) we make predictions using individual models Mi. This creates the feature vector <strong>[M1, M2, M3,…, Mi,…Mn]</strong> for our ensemble. What’s the target? It’s 1 since it’s a positive sample and 0 for a negative sample.</p><p>This is how our data-frame should look like:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*FZqIHxKvBhhRy5J1qfZKAQ.png" /><figcaption>DataFrame to be used in the ensemble model.</figcaption></figure><p>We can see that the scores for a (user, movie) combination by different models are not on the same scale. We need to normalize each column (using something like Min-Max scaler) to bring them between (0,1) range so that all columns are comparable. Another approach would be to normalize each score between 0 &amp; 1 using the algorithm mentioned at the beginning of the article, (reference: <a href="https://stackoverflow.com/questions/6352212/how-to-merge-a-collection-of-ordered-preferences">SO</a> ).</p><p>Now we can train a classification model that will tell us the likelihood that a user will watch a movie given the prediction of model Mi.</p><p>Think of each of these models Mi as experts. We wanted to learn the importance of each expert. Hence, we trained an ensemble to learn the weights that should be given to each expert. Let’s say that after training we learn the weights w1, w2, w3 to be 0.1, 0.5, 0.7. While making a prediction for a (user-i,movie-i) combination, we obtain model predictions m1, m2, m3 to be 0.5, 0.3, 0.1.</p><p>So, using our score() above we calculate</p><pre>score(u,v) = w1*m1 + w2*m2 + w3*m3 <br>           = 0.1 * 0.5 + 0.5 * 0.3 + 0.7 * 0.1 <br>           = 0.27</pre><p>If we have 10 movies available for prediction, we can calculate the <strong>score(u,v)</strong> for each user <strong>u</strong> &amp; movie <strong>v </strong>and<strong> </strong>rank them based on the score (higher is better). We can then choose top k movies and present them to the user.</p><p>We don’t need to extract the weights and calculate the score ourselves. Since we have trained a model, we could just call <strong><em>ensemble_model.predict() </em></strong>with the features (M1, M2, M3,….Mn) and get the likelihood.</p><p>That’s it, folks. I’ve shared these ideas with you, now go ahead and implement it on your favorite dataset. All feedbacks are welcome. Thank you for reading. :-)</p><h3>References:</h3><ol><li><a href="https://xamat.github.io/pubs/recsys12-tutorial.pdf">https://xamat.github.io/pubs/recsys12-tutorial.pdf</a></li><li><a href="http://www.scholarpedia.org/article/Ensemble_learning">http://www.scholarpedia.org/article/Ensemble_learning</a></li><li><a href="https://stackoverflow.com/questions/49896816/how-do-i-optimize-the-hyperparameters-of-lightfm">https://stackoverflow.com/questions/49896816/how-do-i-optimize-the-hyperparameters-of-lightfm</a></li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=87dca2a54a23" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science-for-everyone/ensemble-modelling-in-personalized-ranking-87dca2a54a23">Ensemble Modelling in Personalized Ranking</a> was originally published in <a href="https://medium.com/data-science-for-everyone">Data Science for Everyone</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[The Explore-Exploit dilemma]]></title>
            <link>https://medium.com/data-science-for-everyone/the-explore-exploit-dilemma-436cb1edff0d?source=rss-41d92974c91------2</link>
            <guid isPermaLink="false">https://medium.com/p/436cb1edff0d</guid>
            <category><![CDATA[learning]]></category>
            <category><![CDATA[probability]]></category>
            <category><![CDATA[reinforcement-learning]]></category>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Saikat Kumar Dey]]></dc:creator>
            <pubDate>Mon, 10 Dec 2018 15:54:37 GMT</pubDate>
            <atom:updated>2018-12-11T05:51:43.223Z</atom:updated>
            <content:encoded><![CDATA[<p>You want to learn about “Machine Learning”. You make a Google search. There are 10–15 results linking to the various sources of information. You open the links one by one. You take a one-shot look at them before deciding which ones among the lot you would invest time in reading. This way, you would get to know of some credible sources for reading about ML, which you will use the next time. We call the act of going through the links one by one, <strong>Exploration</strong>. We call the act of using the sources next time when you want to read about ML, <strong>Exploitation</strong>. <strong>Exploration</strong> gave you information about the sources (websites, blogs, youtube channels). Based on it, you create a mental note (or bookmarked) of which ones to use the next time (<strong>Exploitation</strong>).</p><p><strong>Exploration</strong> is a time-consuming process. It is necessary because you have no information about the source at hand. Exploitation is when you make use of the hard work done in exploration. But how long do you explore? When do you know you should exploit the information?</p><p>There’s a very interesting problem called <strong>Multi-armed bandit</strong> related to Explore-Exploit trade-off. So, imagine that you are in a casino playing a 3-armed slot machine. The slot machine has 3 levers. You pull one of them and you get some money in exchange. In the beginning, you have no knowledge about the machine. You do not know which lever will give you the most reward (or money in this case). Each one of the levers has a certain probability of reward associated with it. What would you do to maximize the reward for N trials (say 100)? Let’s see, we could take the following approaches :</p><ol><li><strong>Always Exploiting:</strong> You could always pull one of the levers (say, lever 1). The problem is that you wouldn’t know if you could earn more by pulling other levers.</li><li><strong>Always Exploring:</strong> You could pull a lever at random every time. The problem is that you wouldn’t learn anything from your previous actions. (Always exploring)</li><li><strong>Epsilon Greedy: </strong>You pull the best lever 70% (say) of the time (exploitation). You pull a lever 30% of the time at random (exploration). Let’s say that we have a coin with a probability that a head comes up is 0.3. So, we’ll toss a coin, if the probability is 0.3 or less, we’ll pull a lever at random. If the probability is more than 0.3, we’ll select the best lever so far. The value of epsilon is 0.3, which is also called exploration probability.</li><li><strong>Epsilon First strategy:</strong> You pull all levers for a fixed number of times (say, 20 times each). Observe which one gave you the most reward (say, lever 3). Then, keep pulling lever 3 every time.</li><li><strong>Epsilon Decreasing strategy: </strong>This is the same as the epsilon-greedy approach. But, the epsilon decreases with the number of trials in this case. This means, in the beginning, we’ll explore more (and exploit less). After good enough trials, we’ll exploit more (and explore less).</li></ol><p>These are not an exhaustive set of approaches that we could take. There are other approaches like <strong>Adaptive epsilon-greedy strategy based on value differences (VDBE) </strong>and <strong>Contextual-Epsilon-greedy strategy</strong>. Which approach is the best? We shouldn’t use approach 1 or 2 because of the obvious problems mentioned. Epsilon-Greedy is the simplest to implement and we could increase the sophistication of the algorithm.</p><h4>Where do we use the explore-exploit trade-off in the industry?</h4><p>This is the real question that you might have been wondering while reading this article. If you’ve come this far (exploitation phase for you), here’s your reward. We’ll discuss two approaches in this post.</p><ol><li><strong>An alternative to A/B testing: </strong>What is A/B testing? You are launching a new website and you have 2 designs for it with a call to action (click on “buy now” for example). You are not sure which one to use, so you show version A to 1000 users and version B to another 1000 users. The design which has the greatest conversion rate wins. What is the issue here? User tastes are volatile. Here, we are running a one-shot experiment and selecting the design. What if the taste of our user-base changes after a certain point? Should we run the experiment again? We could reduce this problem to a multi-armed bandit problem. We could use the strategies (epsilon-*) mentioned above. Let’s say that we use the epsilon-greedy approach. We choose an epsilon of 0.5. This means, we toss a coin and if it is HEADS, we select one of the versions at random. If it is TAILS, we select the best version over last N trials, (say A). We could either choose the epsilon probability manually or we could use other strategies like epsilon-decreasing or adaptive-epsilon strategy (where epsilon gets updated over time). This approach is robust since you always have an element of exploration and can reward the lesser-chosen version if the user taste changes.</li><li><strong>Ranking Algorithms: </strong>Let’s say you are building a “<em>People Also Search for</em>” feature for Google. [ The following approach is, of course, an oversimplified version. Google might not be using this. ;) ]</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*wuGclFmm0g4ztF_U3LiBLQ.png" /></figure><p>What do you want to optimize using this feature? You want to make sure that the user keeps on searching relevant items (so you could show ads and make money). People search a lot of stuff before or after searching titanic. You want to predict what items people might search for next and show it to them. This means that you are figuring out P(x/Titanic) = P(#clicks/search on movie x/# search for Titanic). This means the probability that user clicks on movie x given that the user has searched for Titanic. How do you solve this if you don’t have a lot of data? Sure, you could always use content-based recommendation algorithms. Show the movies which are like Titanic (genre, director, actors, synopsis, etc). But, in what order do we show them? Do we always show the most similar items at the top? Or do we change them depending on some signals?</p><p>Let’s formalize the problem as a contextual multi-armed bandit problem. You could rank the items based on P(x/Titanic) and the reward.</p><blockquote>1. Let’s say you have a set of movies [x1, x2, x3, ……, xN ] that are like Titanic.</blockquote><blockquote>2. You have to fill N slots.</blockquote><blockquote>3. For each slot, you perform steps 4–6 until all k slots are full.</blockquote><blockquote>4. Remove already selected items from the set.</blockquote><blockquote>5. You generate a random number between [0,1].</blockquote><blockquote>6. If it is less than epsilon, <strong>explore</strong> — you choose an item from the set at random and put it in the next available position.</blockquote><blockquote>If it is more than epsilon, <strong>exploit</strong> — you choose the item having the highest reward. This could be an expected value P(x/Titanic) * reward, depends on how you formulate the equation)</blockquote><blockquote>7. When the user clicks on item <strong>xi</strong>, update reward(Titanic, <strong>xi</strong>) by +r (say +5).</blockquote><p>Choose<strong> epsilon</strong> based on one of the strategies mentioned earlier.</p><p>The items will be in random order at first. The system learns the ranking of the items from the user-interactions.</p><p>The best part? This system is always going to learn. Let’s say Titanic III comes up next. And it excites a lot of people. So, the clicking/searching behavior should reflect on the ranking.</p><blockquote>You could use this approach to bubble up new users in the system (Users/Channels/Content-Creators/Artists).</blockquote><p>So, who learned something new? :)</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=436cb1edff0d" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science-for-everyone/the-explore-exploit-dilemma-436cb1edff0d">The Explore-Exploit dilemma</a> was originally published in <a href="https://medium.com/data-science-for-everyone">Data Science for Everyone</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Is Neymar Jr a selfish player?]]></title>
            <link>https://saikatkumardey.medium.com/is-neymar-jr-a-selfish-player-ed2a53c4a81?source=rss-41d92974c91------2</link>
            <guid isPermaLink="false">https://medium.com/p/ed2a53c4a81</guid>
            <category><![CDATA[soccer]]></category>
            <category><![CDATA[psg]]></category>
            <category><![CDATA[barcelona]]></category>
            <category><![CDATA[neymar]]></category>
            <category><![CDATA[football]]></category>
            <dc:creator><![CDATA[Saikat Kumar Dey]]></dc:creator>
            <pubDate>Sun, 02 Dec 2018 07:27:00 GMT</pubDate>
            <atom:updated>2018-12-02T07:43:33.193Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*60SY1aXfpzYC8RPOWLtpWQ.jpeg" /><figcaption>Image source: <a href="http://as01.epimg.net/en/imagenes/2018/08/17/football/1534508243_231921_noticia_normal.jpg">http://as01.epimg.net/en/imagenes/2018/08/17/football/1534508243_231921_noticia_normal.jpg</a></figcaption></figure><p>The hatred towards Neymar is insane! We read all over the internet how much of a selfish player he is! People’s opinions are formed from the subjective treatment that Neymar receives from the media. But, what does the data say?</p><p>Who is a selfish player, really? For the sake of the argument, let’s say that a selfish player is one who doesn’t think about the team &amp; plays for himself. Good, now that we have got the definition out of the way, let’s focus on Neymar’s career from 2013-present in this article.</p><p>Neymar joined Barcelona in 2013 as a Brazilian wonder-kid who was crushing the Brazilian league as the Santos’ talisman. We’ll take <strong>assists &amp; key-passes </strong>as a key parameter for player’s unselfishness.</p><h3>2013–2014 Barcelona LaLiga</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*0UUoiq1K8fUtZHBdWDHJIw.png" /><figcaption>Neymar had 8 assists in 19 games (he was used as a substitute in 7 matches).</figcaption></figure><h3>2013–2014 | Barcelona | UCL</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3xt7hQuDDBvh6_9U8-sJ_w.png" /><figcaption>Neymar had 3 assists in 9 matches. Messi had none.</figcaption></figure><h3>2014–2015 | Barcelona | La Liga</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cPHlkxkN3yma9vWGeb9-4g.png" /><figcaption>Neymar had 7 assists in 29 matches in this season.</figcaption></figure><h3>2014–2015 | Barcelona | UCL</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9mAg0UgxDhvZRjnudKWP_A.png" /><figcaption>Neymar had 10 goals in this tournament, joint highest scorer along with Messi and Christiano Ronaldo. Barcelona went on to win this tournament.</figcaption></figure><h3>2015–2016 | Barcelona | La Liga</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*fN5_PIn07QQ91jcIvskWtQ.png" /><figcaption>Neymar had 12 assists in this season</figcaption></figure><h3>2015–2016 | Barcelona | UCL</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ij98Mp775mg5TzORSX2Wdw.png" /><figcaption>Neymar had 4 assists in the tournament</figcaption></figure><h3>2016–2017| Barcelona | La Liga</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*suffd_DPehV31NIida6Itw.png" /><figcaption>Just observe Neymar at the top with 11 assists and the highest rating for the first time.</figcaption></figure><h3>2016–2017| Barcelona | UCL</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*I2sg68wIW82xh3kWCB3_BQ.png" /><figcaption>Neymar at the top again with 8 assists.</figcaption></figure><h3>2017–2018| PSG | Ligue 1</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*qwUiFAmp0bdIpUuYwW40Vw.png" /><figcaption>Neymar had 13 assists and 19 goals from 20 appearances. He had more assists than Messi &amp; Ronaldo in this season even though he missed half of the season due to injury!</figcaption></figure><h3>2017–2018 | PSG | UCL</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*RWmaiBRXnTL1f3EQnd5g_A.png" /><figcaption>3 assists from 7 appearances</figcaption></figure><p>Neymar is one of the top assisters at the highest levels for both Barcelona and PSG. He’s a great play-maker and has the most number of key-passes in almost all of the matches that he plays in. If you actually watch him play, you’ll notice that he’s the difference maker.</p><p>Let the data speak for the last couple of years:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ZM24XroBQKYunrRUFdXZ5g.png" /><figcaption>Neymar has 3.5 key passes per game. He also attempts 7.1 dribbles per game. On an average Neymar is dispossessed 2.9 times per game (Messi, 3 times per game but no one complains?)</figcaption></figure><p>People complain that he’s a ball-hogger and loses possession a lot. This is true. But he’s a generational player and one of the best dribblers of our time. His dribbles break oppositional defense, taking defenders out of their position allowing free space to his team-mates in attack. This is tactical. He takes a lot of risks in the field. Some work out, some don’t.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*v1scb8eJrU0PFcTErmfT9w.png" /><figcaption>Neymar- 3 key passes per game , Messi — 2.3. Neymar attempts 5.6 dribbles per game compared to Messi’s 3.7. Neymar gets dispossessed 2.8 times, Messi get dispossessed 2.6 times.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Md1ShKYsmN3FwLCdAKoikg.png" /><figcaption>More key passes / dribbles per game than Messi. Dispossessation rate is also similar.</figcaption></figure><p>Neymar is the most fouled player in the game, at the highest levels. Yes, his antics on the field might be a turnoff but guess what? He does it to protect himself and <strong>win fouls for the team</strong>. You know what happened in WC 2014 when <strong>Colombia’s Juan Zuniga </strong>broke<strong> Neymar’s </strong>back? Did the referee give a red card to Juan Zuniga? It was not even a tactical foul! Neymar exaggerates the fouls &amp; tries to convince the referees to punish the defenders so that they’ll be warned. That’s why he simulates the injuries on-field so that he doesn’t end up with a career-ending injury. Most players do that.</p><p>Look at this shameless tweet,</p><h3>SPORT English on Twitter</h3><p>Leboeuf: With me, Neymar would end up in the hospital https://t.co/71to6aJMH9</p><p>and the apt reply</p><h3>Sabine A. on Twitter</h3><p>@Sport_EN Admitting he would be a horrible ref and manager?! Very honest of him. He should take a look at the game, neymar wasn&#39;t the one diving. https://t.co/erP2e1Uva8</p><p>This is the heights of hatred towards one of the greatest footballers of this generation. People’s subjectivity knows no bounds when it comes to Neymar. People say that he was really bad at the world cup. Do you know that he’s directly joined the team after a mid-season injury? If you think that he was bad, please read the statistical analysis of each one of his world cup matches. https://statsbomb.com/2018/07/the-great-neymar-debate/.</p><p>Source of all statistical data: <a href="http://whoscored.com/">http://whoscored.com</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ed2a53c4a81" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How do machines really learn?]]></title>
            <link>https://medium.com/data-science-for-everyone/how-do-machines-really-learn-3c4f6d2f4cd8?source=rss-41d92974c91------2</link>
            <guid isPermaLink="false">https://medium.com/p/3c4f6d2f4cd8</guid>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Saikat Kumar Dey]]></dc:creator>
            <pubDate>Sun, 02 Dec 2018 06:00:08 GMT</pubDate>
            <atom:updated>2018-12-02T06:22:15.208Z</atom:updated>
            <content:encoded><![CDATA[<p>It’s just like how any of us learns.</p><p>There are 3 ways in which a machine learns:</p><ol><li>Show the machine some examples and it will learn to generalize based on the properties. For example, if you need to teach the machine to differentiate between cats and dogs, you gather a collection of images of dogs and cats and then show it to the machine. Internally, the features like size, shape, color, etc. are extracted from the images and used to learn the differentiation. This is also called <strong>Supervised learning</strong>.</li><li>Give it some examples without labels and ask it to group them based on its features. For example, if we get a set of t-shirts in different colors and give it to a kid and ask him to group them, how would he go about it? He might create different groups based on the colors only or size only (S, M, L, XL, etc.) or price or a combination of size/ color/price. Different kinds of grouping can give us different insights into the set of t-shirts. Like, the red t-shirts of size M generally cost higher than other colors. This is also called <strong>Unsupervised learning</strong>.</li><li>How do you learn to ride a bicycle? Do you see Youtube videos of other people riding bicycles (point 1)? No. You learn it by trial and error. Given enough trials, you figure out a way to keep yourself balanced. This is what the machine does too! It goes into an unknown territory and learns to perform an action (play a game, drive a car, etc.) through trial and error. Every good action is rewarded and a bad action is penalized. Gradually, the machine learns to take good actions and that’s when we say that the machine has learned by itself. This is also known as <strong>Reinforcement learning.</strong></li></ol><p>So, how does a machine really learn? Well, it needs incentives. The incentives, in this case, are the minimization of loss (loss function) or maximization of reward. Think about how we learn as a student. We learn by reading/writing/observing in the classroom and then take tests. The teacher grades the tests and gives us marks (rewards). Our objective is to minimize the errors in the tests (or in other words, maximize the marks). We know we have learned the topics properly when we get the maximum marks in the tests. Machines do it by a process called <strong>gradient descent</strong> where it intelligently takes the tests and fixes its errors until it minimizes the error on the tests (or maximizes the marks).</p><p>So that’s it. The process to teach a machine is simple:</p><p>1. Get data (or define a process to get data on the go)<br>2. Define an incentive (or loss function)<br>3. Take a step and calculate the error.<br>4. Learn from the mistake and adjust the next steps based on the previous error.<br>5. Repeat 3 &amp; 4 until the error is minimum.</p><p>So, who learned something new today? :)</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3c4f6d2f4cd8" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science-for-everyone/how-do-machines-really-learn-3c4f6d2f4cd8">How do machines really learn?</a> was originally published in <a href="https://medium.com/data-science-for-everyone">Data Science for Everyone</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Write better python using generators]]></title>
            <link>https://saikatkumardey.medium.com/advanced-python-generators-4e73d83561f2?source=rss-41d92974c91------2</link>
            <guid isPermaLink="false">https://medium.com/p/4e73d83561f2</guid>
            <category><![CDATA[scalability]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[tech]]></category>
            <category><![CDATA[design-patterns]]></category>
            <dc:creator><![CDATA[Saikat Kumar Dey]]></dc:creator>
            <pubDate>Sat, 13 Jan 2018 07:52:36 GMT</pubDate>
            <atom:updated>2018-01-13T09:26:34.772Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Ihp-FOxXw3zcR2O8K2BbxA.jpeg" /><figcaption>No, we won’t use this one ;)</figcaption></figure><p>Let’s say that we have a text file <em>student_records.txt . </em>Each line contains a student name and age. We want to parse student names and their ages.</p><pre>#student_records.txt</pre><pre>greg:15<br>matthew:14<br>ram:16<br>raju:14</pre><p>Our first approach would be to read the files and store the values in a list/dictionary.</p><pre>def read_student_records(path):<br>  records = []<br>  with open(path) as file:<br>    for line in file:<br>      name, age = line.split(&quot;:&quot;)<br>      records.append((name, age))<br>  return records</pre><pre>for record in read_student_records(path):<br>  print(record)  # do something with record</pre><p>This gets the job done. However, the function <strong><em>read_student_records()</em></strong> is messy. What if we have to read from multiple files?</p><p>Let’s clean up our code above and make it more modular.</p><pre>def lines_from_file(path):<br>  lines = []<br>  with open(path) as file:<br>    for line in file:<br>      lines.append(line)<br>  return lines</pre><pre>def student_records(lines):<br>  records = []<br>  for line in lines:<br>    name, age = line.split(&quot;:&quot;)<br>    records.append((name, age))<br>  return records</pre><pre>def student_records_from_file(path):<br>  lines = lines_from_file(path)  # 1<br>  records = student_records(lines)  # 2<br>  return records<br># read from multiple files and do something with it</pre><pre>def student_records_from_files(filenames):<br>  records = []<br>  for filename in filenames:<br>    records_from_file = student_records_from_file(filename)  # 3<br>    records.extend(records_from_file)<br>  return records</pre><pre>filenames = [&#39;r1.txt&#39;, &#39;r2.txt&#39;]<br>records = student_records_from_multiple_files(filenames)<br>for record in records:<br>  print(record)  # do something with record</pre><p>The above functions are pretty self-explanatory.</p><ul><li><strong><em>lines_from_file</em></strong> function reads a file line by line, stores it in a list and returns it.</li><li><strong><em>student_records</em></strong> reads in a list of lines, extracts name &amp; age from each line and stores it in a list.</li><li><strong><em>student_records_from_file </em></strong>combines <strong><em>lines_from_file </em></strong>and <strong><em>student_records</em></strong>.</li><li><strong><em>student_records_from_files </em></strong>calls <strong><em>student_records_from_file</em></strong> , stores the records and returns it.</li></ul><p>Everything seems alright? Could you find out some issues in the above code? I’ll wait.</p><p>In <strong><em>student_records_from_file</em></strong><em> </em>function</p><ul><li>#1 blocks until all the lines are read.</li><li>#2 blocks for parsing each records.</li><li>#3 blocks for reading all records from a file before moving on to the next one.</li></ul><p>In each of these functions, we store data and throw them away when we return the values to a different function.</p><p><strong>What if some of the files have 1 billion records or more?</strong></p><p>We don’t need to store all of the lines in memory before parsing them. It is desirable to iterate over each line and parse them, one line in memory at a time.</p><p>Generators help you do just that. It is very useful tool to create iterators. The way generators differ from regular python functions is that they <strong><em>yield </em></strong>instead of <strong><em>return.</em></strong></p><p>An iterator produces values in a sequence, one at a time. Calling a <strong><em>next() </em></strong>on an iterator returns the next value in the sequence.</p><p>Now, back to generators. There’s a difference between generator function and generator object. When you define a function which “yield” instead of “return” , it’s a generator function. When you call a generator function, a generator object is created. No execution happens until next() is called on a generator object.</p><p>Let’s re-write our code using generators now.</p><pre>def lines_from_file(path):<br>  with open(path) as file:<br>    for line in file:<br>      yield line</pre><pre>def student_records(lines):<br>  for line in lines:<br>    name, age = line.split(&quot;:&quot;)<br>    yield name, age</pre><pre>def student_records_from_file(path):<br>  lines = lines_from_file(path)<br>  yield from student_records(lines)</pre><pre>def student_records_from_files(filenames):<br>  for file in filenames:<br>    yield from student_records_from_file(file)  # 4</pre><p><strong><em>yield from</em></strong> is a shortcut for yielding data from another generator object:</p><pre>#4 can be also be written as<br>for record in student_records_from_file(file):<br>  yield record</pre><p>Now you can iterate over student records one by one and do something with it.</p><pre>for record in student_records_from_files(filenames):<br>    print(record) #do something with record</pre><p>This leads to a simple modular design. Each function is responsible for doing one task, hence it’s optimized for reusability. Also, it has a low memory footprint since we are having one student record in memory at a time.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4e73d83561f2" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How do Recommendation Systems work?]]></title>
            <link>https://medium.com/data-science-for-everyone/how-does-recommendation-systems-work-f3e1c96b14e8?source=rss-41d92974c91------2</link>
            <guid isPermaLink="false">https://medium.com/p/f3e1c96b14e8</guid>
            <category><![CDATA[collaborative-filtering]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[ai]]></category>
            <category><![CDATA[recommendation-system]]></category>
            <dc:creator><![CDATA[Saikat Kumar Dey]]></dc:creator>
            <pubDate>Sun, 06 Aug 2017 17:01:45 GMT</pubDate>
            <atom:updated>2017-08-06T17:04:10.963Z</atom:updated>
            <content:encoded><![CDATA[<p>If I ask you to tell me one application of Machine Learning that you use everyday, what comes to your mind? No points for guessing! Recommendation engines are common in many products that you use daily, so much so that you do not even consciously think about it. Be it YouTube’s next video suggestion to Amazon showing you “People who bought this also bought..” to Medium suggesting you which articles to read next to Netflix recommending which movie you should watch next. It’s everywhere! Let’s understand approaches to building recommendation systems.</p><p>Let’s take the example of Netflix recommendation system. The problem statement is simple: <strong>Recommend movies that your users might watch next.</strong></p><h4>Take 1: Recommend the most popular movies</h4><p>This could be observed in many news sites where they display the most read/most emailed/most shared stories segmented by different news categories. So, you could do the same here. Recommend the most watched/most reviewed/most starred movies across various genres.</p><p><strong>Pros: <br></strong>Very simple to implement.<br><a href="https://en.wikipedia.org/wiki/Cold_start">Cold start</a> problem is not encountered here.</p><p><strong>Cons: <br></strong>Lot of work. We might hate to admit this but we like things to be handed over to us on a plate don’t we? Imagine yourself having to decide every time about which movie to watch next after going through the synopsis, the reviews, the ratings, etc. Painful, isn’t it? No one likes browsing, not especially for entertainment. This is the era of personalization. People want to discover things that they haven’t even thought of or heard of.</p><h4>Take 2: Build a classifier based on user demographics and user actions</h4><p>Another approach could be to predict whether an user would like or dislike a movie. So, build a model using some or all of the following features:<br>+ user’s demographics(age,gender,country,etc.)<br>+ Features (genre,length,lead actor,etc) of the movie for which prediction is being made<br>+ Features (genre,length,lead actor) of recent movies watched<br>+ Frequency/Recency/Duration of movies watched</p><p><strong>Pros:</strong><br>Features are personalized. User’s history / habits of watching movies are captured in this approach.<br><strong>Cons:<br></strong>Enough features might not be available to predict accurately.</p><h4>Take 3: Recommend movies based on other people’s tastes</h4><p>Also seen as “People who watched X also watched..” or “People who purchased this also bought..”. This approach is also known as <a href="https://en.wikipedia.org/wiki/Collaborative_filtering">collaborative filtering</a>. Implementation is simple. Create a M x N matrix where rows &amp; columns represent movies available on Netflix. Each cell in the matrix would represent the number of users who watched both M &amp; N. The matrix created is also known as “Co-occurrence matrix”. Now, making recommendations is really simple. If a user has watched a movie <em>i</em>, just look up i-<em>th</em> row in the matrix and recommend top-k items in that row.</p><p>What if there are very popular movies ? For any row, say top-3 movies are always the same. Would you recommend the same list to everyone then? In that case, it won’t be any different than our popularity based approach. Any solutions?</p><p>Well, one of the approach would be to normalize the co-occurrence matrix. So what are we trying to do here? For a movie i, we are trying to find similar movies to it by looking at all the movies j across the column in the co-occurrence matrix. We could use a similarity metric called <a href="https://en.wikipedia.org/wiki/Jaccard_index">Jaccard Similarity</a>, to normalize the co-occurrences.</p><blockquote>So, for each i,j: <br>S[i,j] =<strong> (# of users who watched both movie i and j)/(# of users who watched i or j).</strong></blockquote><p>Here S is the similarity matrix computed by applying Jaccard similarity on the co-occurrence matrix. But..</p><p>Recommendations are only based on the current movie watched. In order to get more relevant suggestions, the history should be considered as well right? Alrighty, one way to solve this would be to take a weighted average of the similarity between all my recently watched movies and the candidate movies up for recommendation. So, let’s say I have watched 3 movies X,Y,Z recently and candidate movies for recommendation are i to n.</p><blockquote>Score(i) = 1/3(S[X,i] + S[Y,i] + S[Z,i])</blockquote><p>So, we calculate Score for all movies i to n and recommend the top-k movies. But..</p><ul><li>We do not consider the context (time of the day) , user-specific features or product-specific features (director, actor, genre, etc)</li><li>There’s the issue with cold start problem. What if a new user or a new movie arrives?</li></ul><p><strong>Take 4: Matrix Factorization</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/695/1*Qjsd_t1EFw1cZ4P7j80mtQ.jpeg" /><figcaption>Movie Dataset</figcaption></figure><p>Let’s say that we have a dataset of users,movies and ratings. So, for each user we know the rating s/he gave to a subset of movies. Now, we can create a m x n matrix <em>Rating</em> where <em>Rating</em>[u,v] would be the rating given by user <em>u</em> to movie <em>v. </em>Practically, the matrix <em>Rating</em> would be sparsely populated, since each user would have watched a small subset of movies available. The goal is to predict the ratings for all movies that a user hasn’t watched. How to do that?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/676/1*O_ZSBAT3VnokP32SMu7-8Q.jpeg" /><figcaption>Rating Matrix</figcaption></figure><p>We have to factorize the matrix <em>Rating</em> into two matrices L and R such that <br><strong>L is a m x k matrix<br>R is a k x n matrix</strong><br>L[u] consists of user-specific features like how much s/he likes action,drama,thriller,etc.<br>R[v] consists of movie-specific features like how much is it action,drama,thriller,etc.<br>So, Rating[u,v] is the product of vectors L and R.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*jCOLukNlTopEdsO1AreEDQ.jpeg" /></figure><p>Now, <strong><em>we could start making recommendations by sorting movies on the basis of Rating[u,v] for all the movies v that user u hasn’t watched</em>.</strong> But..</p><p>The catch is that we don’t really know L and R. How do we find that? Many <a href="https://en.wikipedia.org/wiki/Matrix_decomposition">algorithms</a> are already there that does this. Let’s understand it intuitively.</p><p><strong>Do you remember Linear regression?</strong> It’s nothing but fitting a curve through the points. Let’s take a simple example. We are given training data (x,y) where x is the independent variable and y is the dependent variable ( the variable we want to predict). So, what Linear regression does is to figure out the best line that fits the data points (x_i, y_i) . A line <strong>y = m.x+ c</strong>, is determined by it’s parameters (m,c). So, Linear regression would try to figure out the optimal parameters (m,c) so that the <a href="https://en.wikipedia.org/wiki/Residual_sum_of_squares">RSS</a> (residual sum of squared error ) is minimized i.e, the line fits as many points on it as possible or the points are as close to the line as possible. The RSS can is computed as Sum((y_i-y_predicted)²) for i=1 to n.</p><p>Let’s map the above intuition to our matrix factorization problem.</p><blockquote>(x,y) =&gt; (u,v,Rating[u,v]) here, u,v are the features and Rating[u,v] is the score.<br>(m,c) =&gt; (L,R) here, L &amp; R are the parameters of the Matrix Factorization model, just like m,c are the parameters of the Linear Regression model.</blockquote><p>So, the matrix factorization algorithms would try to estimate the Rating matrix for different values of L &amp; R and see if the RSS is minimized. Once we have optimal L &amp; R, we can make predictions for the ratings of movies not watched by the users and recommend them accordingly.</p><p>The cold-start problem still remains. The model wouldn’t be able to handle a new user or a movie on the system.</p><p>So, in this post you learnt various approaches to recommendation system. In the next one we’ll implement a recommendation system.</p><h4>References:</h4><p><a href="https://www.coursera.org/learn/ml-foundations/home/week/5">ML Foundations- Coursera</a></p><p>Thanks for reading. :)</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f3e1c96b14e8" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science-for-everyone/how-does-recommendation-systems-work-f3e1c96b14e8">How do Recommendation Systems work?</a> was originally published in <a href="https://medium.com/data-science-for-everyone">Data Science for Everyone</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[SPOJ: BITMAP]]></title>
            <link>https://saikatkumardey.medium.com/spoj-bitmap-71d7a12354b1?source=rss-41d92974c91------2</link>
            <guid isPermaLink="false">https://medium.com/p/71d7a12354b1</guid>
            <dc:creator><![CDATA[Saikat Kumar Dey]]></dc:creator>
            <pubDate>Mon, 22 Sep 2014 07:00:49 GMT</pubDate>
            <atom:updated>2017-08-06T18:50:24.907Z</atom:updated>
            <content:encoded><![CDATA[<p>Have a look at the problem statement first, <a href="http://www.spoj.com/problems/BITMAP/">http://www.spoj.com/problems/BITMAP/</a></p><p>Today, I solved a very interesting problem on SPOJ. In the initial stages I used Brute Force; judging from the complexity of the algorithm I knew it wouldn’t pass. I searched for some hints on Google. And after that I came up with a very elegant solution.</p><p>Anyway, here’s the straightforward problem description: You are given a 2 dimensional array of 0&#39;s and 1&#39;s. All you have to do is find the distance of each 0 from it’s nearest 1 and write it in its position. It’s given that you can find the distance between any two cells using the formula d= |i1 — i2 | + | j1 — j2 | where i1,j1 and i2, j2 are co-ordinates of the two cells respectively.</p><p>So, if the input is:</p><pre>1<br>3 4<br>0001<br>0011<br>0110</pre><p>The output should be:</p><pre>3 2 1 0<br>2 1 0 0<br>1 0 0 1</pre><h3>Brute Force Approach:</h3><ol><li>The 2-D array is a[m][n], say.</li><li>Store the co-ordinates of all the 1&#39;s in a list, say L.</li><li>for each i,j in a[ ][ ]:<br>{ dist= INF for each x,y in L: { dist= min(dist,|i-x|+|j-y|) } a[i][j]= dist<br>}</li><li>Print a[ ][ ].</li></ol><p>Complexity: O(m^2 * n^2) in the worst case when all the cells are filled with 1&#39;s. In the given problem, 1 &lt;= m &lt;=182 and 1&lt;= n &lt;=182. So, obviously, our solution would exceed the Time Limit which is 4 sec.</p><h3>Optimized Approach:</h3><p>In this approach we would use Breadth First Search(BFS) Technique on the 2-D array given ( mathematically, it is a graph. A graph is nothing but a connection( called edges) between some points called vertices and in the 2-D array, every cell is assumed to be connected to every cell to it’s left, right, up and down). For unweighted graph, BFS always gives the shortest path between any two nodes. As a matter of fact, Dijkstra’s algorithm is a rip-off of BFS for weighted graph.</p><p>Now, here’s the approach, First store the co-ordinates of all the 1&#39;s in the 2-D array into a list (say L) and mark all the 1&#39;s as INFINITY and all the 0&#39;s as -INFINITY in the original array itself. [We don’t need the 0&#39;s and 1&#39;s anymore. We have all the information we need.] Then, for each element in the list L, call the BFS() method.</p><blockquote>Here’s how a typical BFS() works, start from the root, visit it, remove it from queue and add all it’s neighbours to a queue. Then visit each element of the queue in FIFO fashion, (removing them one by one in the process) and keep adding their neighbours to the queue. Do it until the queue is empty which would mean that all elements have been visited. Note that, each element is added and deleted at most once in the queue. Hence, BFS() operation takes linear time (depends only on the number of vertices and edges).</blockquote><blockquote>Our BFS() is very similar except one change, <strong>we add a neighbor( up, down, left or right) of a node into the queue only when value(current node) +1 &lt; value( neighbor).</strong> What is the value() thingy here, you might ask? Good question! In the BFS(), we start traversing from a root-node (which is the cell that contained 1 in the original array) and assign it a value of 0. <strong><em>[ We need to find the nearest distance of all 0&#39;s to 1&#39;s, remember? So, nearest neighbor containing 1 from a cell (containing 1) is itself, hence its value is assigned 0]. </em></strong>Now, we need to add elements to the queue, right? Look to the left, right, up, down and add that node (or cell, whatever) to the queue only if <strong>value(current node) +1 &lt; value( neighbor). </strong>Keep doing this, until the queue is empty, which means that all the cells that could’ve been updated by starting from root has been updated.</blockquote><p>We call our modified BFS() for every cell in our list L (containing co-ordinates of 1&#39;s).</p><h4>Here’s the code:</h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/71df0ffa5a58394c873658e206f82552/href">https://medium.com/media/71df0ffa5a58394c873658e206f82552/href</a></iframe><p>Play with it! ☺</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=71d7a12354b1" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>