<?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[Nearist.ai - Medium]]></title>
        <description><![CDATA[Next Level Similarity Search - Medium]]></description>
        <link>https://medium.com/nearist-ai?source=rss----9df37f73a999---4</link>
        <image>
            <url>https://cdn-images-1.medium.com/proxy/1*TGH72Nnw24QL3iV9IOm4VA.png</url>
            <title>Nearist.ai - Medium</title>
            <link>https://medium.com/nearist-ai?source=rss----9df37f73a999---4</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 19:55:09 GMT</lastBuildDate>
        <atom:link href="https://medium.com/feed/nearist-ai" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Billion Scale Exhaustive Similarity Search]]></title>
            <link>https://medium.com/nearist-ai/billion-scale-exhaustive-similarity-search-c22a9690b6b0?source=rss----9df37f73a999---4</link>
            <guid isPermaLink="false">https://medium.com/p/c22a9690b6b0</guid>
            <category><![CDATA[similarity-search]]></category>
            <category><![CDATA[knn]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[recommender-systems]]></category>
            <category><![CDATA[nearest-neighbor-search]]></category>
            <dc:creator><![CDATA[Chris McCormick]]></dc:creator>
            <pubDate>Wed, 12 Sep 2018 01:35:10 GMT</pubDate>
            <atom:updated>2018-09-12T01:35:10.338Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*a5N4vokpfnlmUnnJMou9zw.jpeg" /></figure><p>Nearist has recently benchmarked exhaustive (or “brute force”) k-NN search on a dataset of 1 billion image descriptors (the deep1b dataset). A single server containing Nearist’s Vector Search Accelerator (VSX) cards was able to find the 100 nearest neighbors to a query vector in 698ms. To put this search task into perspective, it would require 21 Tesla K80 GPUs (each of which has 24GB of RAM) in order to store and search these 1 billion descriptors.</p><p>We at Nearist believe that the ability to easily perform exact, rather than approximate, nearest neighbor search at this scale has important implications for businesses with large search tasks.</p><h3><strong>Background</strong></h3><p>Similarity Search, or the more technical name “k-Nearest Neighbor Search”, is used in many industry applications. k-NN allows for comparing content based on its abstract qualities instead of just structured meta data. This is accomplished using machine learning techniques which create vector representations of the content, which can then be compared using a simple distance metric like the Euclidean distance.</p><p>As the amount of content managed by companies continues to grow, many of these similarity search applications require searching through tens to hundreds of millions of items. Examples include searching through <a href="https://medium.com/airbnb-engineering/listing-embeddings-for-similar-listing-recommendations-and-real-time-personalization-in-search-601172f7603e">4.5 million listings at Airbnb</a>, <a href="https://arxiv.org/pdf/1607.01869.pdf">comparing 126M unique search queries to 43M unique advertisements at Yahoo</a>, or <a href="https://techcrunch.com/2017/03/29/similarity-search/">searching billions of images at Facebook</a>.</p><h3>Approximation Techniques</h3><p>The industry-standard approach to handling k-NN search at this scale is to research, develop, and fine-tune an approximation technique which dramatically reduces search time with a modest drop in accuracy. Approximate Nearest Neighbor (ANN) techniques are very intellectually satisfying — they are clever in design and are very efficient at search time. However, they incur a number of costs to a business:</p><p><em>(1) Approximation techniques require valuable developer time to research and develop:</em></p><ul><li>Studying different approaches</li><li>Conducting experiments to compare their effectiveness</li><li>Fine-tuning parameters to optimize their speed vs. accuracy trade-off</li></ul><p>This is valuable time that the ML team could be spending on higher-value tasks, but ANN search is generally perceived as the only feasible solution.</p><p><em>(2) Approximation techniques require a time-consuming indexing step:</em></p><ul><li>Changes to the dataset cannot be made as frequently because the index may take hours to rebuild.</li></ul><p><em>(3) Approximation techniques sacrifice accuracy.</em></p><p>While a modest drop in accuracy may be acceptable in some applications, many other applications are tied closely to revenue, where improvements in accuracy translate to real dollars:</p><ul><li>Improved accuracy in ad targeting can measurably improve click through rate.</li><li>Improved accuracy in product recommendation can measurably increase conversion rates.</li><li>Improved content recommendations can measurably improve user retention.</li></ul><h3>Another Way</h3><p>Advances in GPU technology, as well as the release of Nearist’s own hardware and VSX cloud service, are enabling exact k-NN search at a much larger scale than has previously been feasible. If your team is building a feature requiring k-NN search, consider whether the opportunity cost, indexing time, and lost accuracy of an ANN technique might outweigh the cost of a simpler, hardware-accelerated, exact search solution.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*OlEz1Y2lS9IagYkfTlJHnA.jpeg" /><figcaption>Nearist’s VSX Card</figcaption></figure><figure><a href="https://nearist.typeform.com/to/kbnNLz"><img alt="" src="https://cdn-images-1.medium.com/max/200/1*zHZOG_mCa46rUnBJTAbTzA.png" /></a></figure><h4>Thanks for reading! We’d really appreciate it if you recommend this post (by clicking the ❤ button) so other people can find it.</h4><h4>P.S. If you enjoyed this article, please consider checking out <a href="https://nearist.ai/">Nearist.ai</a>, or <a href="https://nearist.typeform.com/to/kbnNLz">let’s talk</a> to discuss how can we help accelerate your machine learning efforts.</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XKBIxesP3y7DM2rYmhnhaQ.png" /></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c22a9690b6b0" width="1" height="1" alt=""><hr><p><a href="https://medium.com/nearist-ai/billion-scale-exhaustive-similarity-search-c22a9690b6b0">Billion Scale Exhaustive Similarity Search</a> was originally published in <a href="https://medium.com/nearist-ai">Nearist.ai</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[4 Production Examples of word2vec in Recommender Systems and Advertising]]></title>
            <link>https://medium.com/nearist-ai/4-production-examples-of-word2vec-in-recommender-systems-and-advertising-6dadf0cd4243?source=rss----9df37f73a999---4</link>
            <guid isPermaLink="false">https://medium.com/p/6dadf0cd4243</guid>
            <category><![CDATA[airbnb]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[recommender-systems]]></category>
            <category><![CDATA[spotify]]></category>
            <category><![CDATA[word2vec]]></category>
            <dc:creator><![CDATA[Chris McCormick]]></dc:creator>
            <pubDate>Thu, 05 Jul 2018 23:20:34 GMT</pubDate>
            <atom:updated>2018-07-05T23:20:33.932Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*u98adouc8-eKxM34eqi5Lw.jpeg" /></figure><p>In this article, I wanted to share about a trend that’s occurred over the past few years of using the word2vec model on not just natural language tasks, but on recommender systems as well.</p><p>The key principle behind word2vec is the notion that the meaning of a word can be inferred from it’s context — what words tend to be around it. To abstract that a bit, text is really just a sequence of words, and the meaning of a word can be extracted from what words tend to be just before and just after it in the sequence.</p><p>What researchers and companies are finding is that the time series of online user activity offers the same opportunity for inferring meaning from context. That is, as a user browses around and interacts with different content, the abstract qualities of a piece of content can be inferred from what content the user interacts with before and after. This allows ML teams to apply word vector models to learn good vector representations for products, content, and ads.</p><blockquote>Researchers from the Web Search, E-commerce and Marketplace domains have realized that just like one can train word embeddings by treating a sequence of words in a sentence as context, the same can be done for training embeddings of user actions by treating sequence of user actions as context.</blockquote><blockquote>— Mihajlo Grbovic, Airbnb</blockquote><figure><a href="https://nearist.typeform.com/to/kbnNLz"><img alt="" src="https://cdn-images-1.medium.com/max/200/1*zHZOG_mCa46rUnBJTAbTzA.png" /></a></figure><h3>So What?</h3><p>word2vec (and other word vector models) have revolutionized Natural Language Processing by providing much better vector representations for words than past approaches. In the same way that word embeddings revolutionized NLP, item embeddings are revolutionizing recommendations.</p><p>User activity around an item encodes many abstract qualities of that item which are difficult to capture by more direct means. For instance, how do you encode qualities like “architecture, style and feel” of an Airbnb listing?</p><p>The word2vec approach has proven successful in extracting these hidden insights, and being able to compare, search, and categorize items on these abstract dimensions opens up a lot of opportunities for smarter, better recommendations. Commercially, Yahoo saw a 9% lift in CTR when applying this technique to their advertisements, and AirBNB saw a 21% lift in CTR on their Similar Listing carousel, a product that drives 99% of bookings along with search ranking.</p><h3>Four Production Examples</h3><p>Every e-commerce, social media, or content sharing site has this kind of user activity, so this approach appears to have <em>very</em> wide applicability. In the following sections I’ll summarize four publicized use cases of this technique which have been put into production:</p><ul><li>Music recommendations at Spotify and Anghami</li><li>Listing recommendations at Airbnb</li><li>Product recommendations in Yahoo Mail</li><li>Matching advertisements to search queries on Yahoo Search.</li></ul><h3>1. Music Recommendations</h3><p>Erik Bernhardsson, who developed the approximate nearest neighbors library “Annoy” while at Spotify, has mentioned (in a meet up talk <a href="https://www.youtube.com/watch?v=QkCCyLW0ehU"><strong>here</strong></a> and in a blog post <a href="https://erikbern.com/2013/11/02/model-benchmarks.html"><strong>here</strong></a>) that Spotify experimented with this technique while he was there. The most informative discussion I’ve read of this technique, however, comes from <a href="https://medium.com/u/f0b042f4ac2d">Ramzi Karam</a> at Anghami, a popular music streaming service in the Middle East.</p><p>In his <a href="https://towardsdatascience.com/using-word2vec-for-music-recommendations-bb9649ac2484"><strong>well illustrated article</strong></a>, Ramzi explains how a user’s listening queue can be used to learn song vectors in the same way that a string of words in text is used to learn word vectors. The assumption is that users will tend to listen to similar tracks in sequence.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*z2U5Prbr3MxhWvkwTBB6dA.png" /></figure><p>Ramzi says Anghami streams over 700 million songs a month. Each song listen is like a single word in a text dataset, so Anghami’s listening data is comparable in scale to the billion-word Google News dataset that Google used to train their published word2vec model.</p><p>Ramzi also shares some helpful insights into how these song vectors are then used. One use is to create a kind of “music taste” vector for a user by averaging together the vectors for songs that a user likes to listen to. This taste vector can then become the query for a similarity search to find songs which are similar to the user’s taste vector. The article includes a <a href="https://cdn-images-1.medium.com/max/1400/1*xbNM_CnEIWQtGbsLmZtE-A.gif"><strong>nice animation</strong></a> to illustrate how this works.</p><h3>2. Listing Recommendations at Airbnb</h3><p>Another <a href="https://medium.com/airbnb-engineering/listing-embeddings-for-similar-listing-recommendations-and-real-time-personalization-in-search-601172f7603e"><strong>highly informative article</strong></a> on this subject comes from <a href="https://medium.com/u/a655fe1c6831">Mihajlo Grbovic</a> at Airbnb.</p><p>Imagine you are looking for an apartment to rent for your vacation to Paris. As you browse through the available homes, it’s likely that you will investigate a number of listings which fit your preferences and are comparable in features like amenities and design taste.</p><p>Here the user activity data takes the form of click data, specifically the sequence of listings that a user viewed. Airbnb is able to learn vector representations of their listings by applying the word2vec approach to this data.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/981/1*UzE0JMR1OHXYbPVFNZwgXg.png" /></figure><p>Airbnb made a few interesting adaptations to the general approach in order to apply it to their site.</p><p>An important piece of the word2vec training algorithm is that for each word that we train on, we select a random handful of words (which are not in the context of that word) to use as negative samples. Airbnb found that in order to learn vectors which could distinguish listings within Paris (and not just distinguish Paris listings from New York listings), it was important that the <em>negative</em> samples be drawn from <em>within</em> Paris.</p><p>Grbovic also explains their solution to the cold start problem (how to learn vectors for new listings for which there isn’t user activity data) — they simply averaged the vectors of the geographically closest three listings to the new listing to create an initial vector.</p><p>These listing vectors are used to identify homes to show in the “similar listings” panel on their site, which Grbovic says is an important driver of bookings on their site.</p><p>This was not the first time Grbovic has applied the word2vec model to recommendations — he worked on the next two examples as well while at Yahoo Labs.</p><h3>3. Product Recommendations in Yahoo Mail</h3><p>Yahoo <a href="https://arxiv.org/pdf/1606.07154.pdf"><strong>published a research paper</strong></a> detailing how they use purchase receipts in a user’s email inbox to form a purchase activity, allowing them in turn to learn product feature vectors which can be used to make product recommendations. Like the other applications presented here, it’s worth noting that this approach has gone into an actual production system.</p><p>Since online shoppers receive e-mail receipts for their purchases, mail clients are in a unique position to see user purchasing activity across many different e-commerce sites. Even without this advantage, though, Yahoo’s approach seems applicable and potentially valuable to online retailers as well.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/751/1*bc4vBu6wui1G_y730GuEoQ.png" /></figure><p>Here, the user activity is their sequence of product purchases extracted from the e-mail receipts. The word2vec approach is able to learn embeddings for the products based on the assumption that shoppers often buy related items in sequence. For instance, perhaps they are purchasing a number of items around the same time because they go together (like a camera and a lens), or because they are all part of a project they are working on, or because they are preparing for a trip they are taking. A user’s sequence of purchases may also reflect shopper taste — shoppers who like item A also tend to like item B and are interested in buying both.</p><p>This may seem a little strange given that the products we purchase aren’t always related. But remember that the model is governed by the statistics of user behavior — if two products are related, they are going to be purchased together by many users (thereby occurring together more in the training data, and having more influence on the model), while any two unrelated products will be purchased together much less often and have little influence on the model.</p><p>Yahoo augmented the word2vec approach with a few notable innovations. The most interesting to me was their use of clustering to promote diversity in their recommendations. After learning vectors for all the products in their database, they clustered these vectors into groups. When making recommendations for a user based on a product the user just purchased, they don’t recommend products from within the same cluster. Instead, they identify which other clusters users most often purchase from after purchasing from the current cluster, and they recommend products from those other clusters instead.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*vX0nQ6cpoo0NhEil7TjrRw.png" /></figure><p>After purchasing a product from the Nerf cluster, customers are most likely to purchase a product from either the Xbox, Pokemon, or LEGO clusters. (Note that the paper doesn’t provide example cluster contents, so the ones above are entirely fabricated).</p><p>I imagine this clustering technique helps eliminate the problem of recommending the equivalent of product “synonyms”. That is, imagine if the system only ever recommended different versions of the same item you just bought — “You just bought <em>Energizer</em> AA batteries? Check out these <em>Duracell</em> AA batteries!” Not very helpful.</p><h3>Justin Shanes on Twitter</h3><p>Amazon thinks my recent humidifier purchase was merely the inaugural move in a newfound hobby of humidifier collecting.</p><p>To choose specific products in those clusters to recommend, in each cluster they find the ‘k’ most similar products to the purchased product, and recommend all of these to the user. In their experiments, they identified 20 products to recommend to the user per day. Each time a user interacts with the Yahoo Mail client, the client displays another one of the product recommendations in the form of another ad.</p><p>The paper also describes a technique called “bagging” where they assign additional weight to products which appear on the same purchase receipt.</p><h3>4. Matching Ads to Search Queries</h3><p>In this application (published <a href="https://arxiv.org/pdf/1607.01869.pdf"><strong>here</strong></a>), the goal is to learn vector representations for search queries and for advertisements in the same “embedding space”, so that a given search query can be matched against available advertisements in order to find the most relevant ads to show the user.</p><p>This is a particularly fascinating application given the number of daunting challenges this problem poses (and yet they solved them and put this into production!). How do you learn vectors for queries and ads at the same time? How could you possibly learn a vector for search queries given the seemingly infinite number of possible queries out there? And how do you apply this when new queries and new ads are appearing daily?</p><p>The solution to learning vectors for queries and ads at the same time is fairly straightforward. The training data consists of user “search sessions” which consist of search queries entered, advertisements clicked, and search result links clicked. The sequence of these user actions is treated like the words in a sentence, and vectors are learned for each of them based on their context — the actions that tend to occur around them. If users often click a particular ad after entering a particular query, then we’ll learn similar vectors for the ad and the query. All three types of actions (searches entered, ads clicked, links clicked) are part of a single “vocabulary” for the model, such that the model doesn’t really distinguish these from one another.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/946/1*OZ_MI7CT0nbJxrRW4Ip-eQ.png" /></figure><p>Even though this application is focused on matching search queries and advertisements, the addition of the link clicks provides additional context to inform the other embeddings. (Though it’s not the subject of their research paper, you have to wonder whether they might use these link embeddings to help in ranking search results…)</p><p>What about the scale of this problem? Surely there are too many unique queries, links, and ads for this to be feasible? This is at least partially addressed by only keeping items in the vocabulary which occur more than 10 times in the training data; they imply that this filters out a large portion of unique searches. Still, the remaining vocabulary is massive — their training set consisted of “126.2 million unique queries, 42.9 million unique ads, and 131.7 million unique links”, a total of 300.8 million items.</p><p>They point out that, for 300-dimensional embeddings, a vocabulary of 200 million items would require 480GB of RAM, so training this model on a single server is out of the question. Instead, they detail a distributed approach that made this training feasible.</p><p>So they’ve tackled the scale problem, but what about the severe cold start problem caused by the daily addition of new search queries and ads? I found the details of their methods here difficult to follow, but the general strategy appears to be matching words in the new material to words in old material, and leveraging those existing embeddings to create an initial embedding for the new content.</p><p>This method was placed into production, but apparently not all advertisements are chosen this way — they say that their approach is “currently serving more than 30% of all broad matches”, where “broad matches” refers to attempts to match queries to ads based on the intent of the queries rather than on simple keyword matching.</p><h3>Similarity Search</h3><p>This approach of learning content vectors based on user activity data is an exciting development for <a href="http://www.nearist.ai/"><strong>Nearist</strong></a>, since the most common operation with these vectors is to perform a similarity search to make content recommendations.</p><p>Given the large amount of vectorized content and the large number of users for which recommendations need to be made, this similarity search becomes a challenging engineering problem. Companies like Spotify and Facebook have invested a great deal of effort into developing approximation techniques to make this search feasible at scale, but with a cost to accuracy and clearly a large cost in engineering effort. And when the quality of product recommendations directly affects revenue, accuracy matters!</p><blockquote>And when the quality of product recommendations directly affects revenue, accuracy matters!</blockquote><p>At Nearist, we believe the efforts of machine learning teams are better spent on improving the quality of your vector representations than on solving similarity search at scale, and we’ve made it our goal to provide as much search capability as you need with minimal engineering effort.</p><figure><a href="https://nearist.typeform.com/to/kbnNLz"><img alt="" src="https://cdn-images-1.medium.com/max/200/1*zHZOG_mCa46rUnBJTAbTzA.png" /></a></figure><h4>Thanks for reading! We’d really appreciate it if you recommend this post (by clicking the ❤ button) so other people can find it.</h4><h4>P.S. If you enjoyed this article, please consider checking out <a href="https://nearist.ai/">Nearist.ai</a>, or <a href="https://nearist.typeform.com/to/kbnNLz">let’s talk</a> to discuss how can we help accelerate your machine learning efforts.</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XKBIxesP3y7DM2rYmhnhaQ.png" /></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6dadf0cd4243" width="1" height="1" alt=""><hr><p><a href="https://medium.com/nearist-ai/4-production-examples-of-word2vec-in-recommender-systems-and-advertising-6dadf0cd4243">4 Production Examples of word2vec in Recommender Systems and Advertising</a> was originally published in <a href="https://medium.com/nearist-ai">Nearist.ai</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Word2Vec Tutorial Part 2 — Negative Sampling]]></title>
            <link>https://medium.com/nearist-ai/word2vec-tutorial-part-2-negative-sampling-fd99420a6dc?source=rss----9df37f73a999---4</link>
            <guid isPermaLink="false">https://medium.com/p/fd99420a6dc</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[word2vec]]></category>
            <category><![CDATA[nlp]]></category>
            <category><![CDATA[towards-data-science]]></category>
            <category><![CDATA[artificial-intelligence]]></category>
            <dc:creator><![CDATA[Chris McCormick]]></dc:creator>
            <pubDate>Thu, 05 Jul 2018 23:12:43 GMT</pubDate>
            <atom:updated>2018-07-05T23:12:42.656Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*q_9GcuoDUbWGTSFjdIkduA.jpeg" /></figure><p>In part 2 of the word2vec tutorial (Part I below), I’ll cover a few additional modifications to the basic skip-gram model which are important for actually making it feasible to train.</p><p><a href="https://medium.com/nearist-ai/word2vec-tutorial-the-skip-gram-model-c7926e1fdc09">Word2Vec Tutorial — The Skip-Gram Model</a></p><p>When you read the tutorial on the skip-gram model for Word2Vec, you may have noticed something–it’s a huge neural network!</p><p>In the example I gave, we had word vectors with 300 components, and a vocabulary of 10,000 words. Recall that the neural network had two weight matrices–a hidden layer and output layer. Both of these layers would have a weight matrix with 300 x 10,000 = 3 million weights each!</p><p>Running gradient descent on a neural network that large is going to be slow. And to make matters worse, you need a huge amount of training data in order to tune that many weights and avoid over-fitting. millions of weights times billions of training samples means that training this model is going to be a beast.</p><p>The authors of Word2Vec addressed these issues in their second <a href="http://arxiv.org/pdf/1310.4546.pdf">paper</a>.</p><p>There are three innovations in this second paper:</p><ol><li>Treating common word pairs or phrases as single “words” in their model.</li><li>Subsampling frequent words to decrease the number of training examples.</li><li>Modifying the optimization objective with a technique they called “Negative Sampling”, which causes each training sample to update only a small percentage of the model’s weights.</li></ol><p>It’s worth noting that subsampling frequent words and applying Negative Sampling not only reduced the compute burden of the training process, but also improved the quality of their resulting word vectors as well.</p><figure><a href="https://nearist.typeform.com/to/kbnNLz"><img alt="" src="https://cdn-images-1.medium.com/max/200/1*zHZOG_mCa46rUnBJTAbTzA.png" /></a></figure><h3>Word Pairs and “Phrases”</h3><p>The authors pointed out that a word pair like “Boston Globe” (a newspaper) has a much different meaning than the individual words “Boston” and “Globe”. So it makes sense to treat “Boston Globe”, wherever it occurs in the text, as a single word with its own word vector representation.</p><p>You can see the results in their published model, which was trained on 100 billion words from a Google News dataset. The addition of phrases to the model swelled the vocabulary size to 3 million words!</p><p>If you’re interested in their resulting vocabulary, I poked around it a bit and published a post on it <a href="http://mccormickml.com/2016/04/12/googles-pretrained-word2vec-model-in-python/">here</a>. You can also just browse their vocabulary <a href="https://github.com/chrisjmccormick/inspect_word2vec/tree/master/vocabulary">here</a>.</p><p>Phrase detection is covered in the “Learning Phrases” section of their <a href="http://arxiv.org/pdf/1310.4546.pdf">paper</a>. They shared their implementation in word2phrase.c–I’ve shared a commented (but otherwise unaltered) copy of this code <a href="https://github.com/chrisjmccormick/word2vec_commented/blob/master/word2phrase.c">here</a>.</p><p>I don’t think their phrase detection approach is a key contribution of their paper, but I’ll share a little about it anyway since it’s pretty straightforward.</p><p>Each pass of their tool only looks at combinations of 2 words, but you can run it multiple times to get longer phrases. So, the first pass will pick up the phrase “New_York”, and then running it again will pick up “New_York_City” as a combination of “New_York” and “City”.</p><p>The tool counts the number of times each combination of two words appears in the training text, and then these counts are used in an equation to determine which word combinations to turn into phrases. The equation is designed to make phrases out of words which occur together often relative to the number of individual occurrences. It also favors phrases made of infrequent words in order to avoid making phrases out of common words like “and the” or “this is”.</p><p>You can see more details about their equation in my code comments <a href="https://github.com/chrisjmccormick/word2vec_commented/blob/master/word2phrase.c#L389">here</a>.</p><p>One thought I had for an alternate phrase recognition strategy would be to use the titles of all Wikipedia articles as your vocabulary.</p><h3>Subsampling Frequent Words</h3><p>In part 1 of this tutorial, I showed how training samples were created from the source text, but I’ll repeat it here. The below example shows some of the training samples (word pairs) we would take from the sentence “The quick brown fox jumps over the lazy dog.” I’ve used a small window size of 2 just for the example. The word highlighted in blue is the input word.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/886/0*DMYRRp0WAzp2qVDU.png" /></figure><p>There are two “problems” with common words like “the”:</p><ol><li>When looking at word pairs, (“fox”, “the”) doesn’t tell us much about the meaning of “fox”. “the” appears in the context of pretty much every word.</li><li>We will have many more samples of (“the”, …) than we need to learn a good vector for “the”.</li></ol><p>Word2Vec implements a “subsampling” scheme to address this. For each word we encounter in our training text, there is a chance that we will effectively delete it from the text. The probability that we cut the word is related to the word’s frequency.</p><p>If we have a window size of 10, and we remove a specific instance of “the” from our text:</p><ol><li>As we train on the remaining words, “the” will not appear in any of their context windows.</li><li>We’ll have 10 fewer training samples where “the” is the input word.</li></ol><p>Note how these two effects help address the two problems stated above.</p><h3>Sampling rate</h3><p>The word2vec C code implements an equation for calculating a probability with which to keep a given word in the vocabulary.</p><p>wiwi is the word, z(wi)z(wi) is the fraction of the total words in the corpus that are that word. For example, if the word “peanut” occurs 1,000 times in a 1 billion word corpus, then z(‘peanut’) = 1E-6.</p><p>There is also a parameter in the code named ‘sample’ which controls how much subsampling occurs, and the default value is 0.001. Smaller values of ‘sample’ mean words are less likely to be kept.</p><p>P(wi)P(wi) is the probability of <em>keeping</em> the word:</p><p>P(wi)=(z(wi)0.001‾‾‾‾‾‾√+1)⋅0.001z(wi)P(wi)=(z(wi)0.001+1)⋅0.001z(wi)</p><p>You can plot this quickly in Google to see the shape.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/610/0*eQ24X7zAo4DukGvs.png" /></figure><p>No single word should be a very large percentage of the corpus, so we want to look at pretty small values on the x-axis.</p><p>Here are some interesting points in this function (again this is using the default sample value of 0.001).</p><ul><li>P(wi)=1.0P(wi)=1.0 (100% chance of being kept) when z(wi)&lt;=0.0026z(wi)&lt;=0.0026.</li><li>This means that only words which represent more than 0.26% of the total words will be subsampled.</li><li>P(wi)=0.5P(wi)=0.5 (50% chance of being kept) when z(wi)=0.00746z(wi)=0.00746.</li><li>P(wi)=0.033P(wi)=0.033 (3.3% chance of being kept) when z(wi)=1.0z(wi)=1.0.</li><li>That is, if the corpus consisted entirely of word wiwi, which of course is ridiculous.</li></ul><p>You may notice that the paper defines this function a little differently than what’s implemented in the C code, but I figure the C implementation is the more authoritative version.</p><h3>Negative Sampling</h3><p>Training a neural network means taking a training example and adjusting all of the neuron weights slightly so that it predicts that training sample more accurately. In other words, each training sample will tweak <em>all</em> of the weights in the neural network.</p><p>As we discussed above, the size of our word vocabulary means that our skip-gram neural network has a tremendous number of weights, all of which would be updated slightly by every one of our billions of training samples!</p><p>Negative sampling addresses this by having each training sample only modify a small percentage of the weights, rather than all of them. Here’s how it works.</p><p>When training the network on the word pair (“fox”, “quick”), recall that the “label” or “correct output” of the network is a one-hot vector. That is, for the output neuron corresponding to “quick” to output a 1, and for <em>all</em> of the other thousands of output neurons to output a 0.</p><p>With negative sampling, we are instead going to randomly select just a small number of “negative” words (let’s say 5) to update the weights for. (In this context, a “negative” word is one for which we want the network to output a 0 for). We will also still update the weights for our “positive” word (which is the word “quick” in our current example).</p><p>The paper says that selecting 5–20 words works well for smaller datasets, and you can get away with only 2–5 words for large datasets.</p><p>Recall that the output layer of our model has a weight matrix that’s 300 x 10,000. So we will just be updating the weights for our positive word (“quick”), plus the weights for 5 other words that we want to output 0. That’s a total of 6 output neurons, and 1,800 weight values total. That’s only 0.06% of the 3M weights in the output layer!</p><p>In the hidden layer, only the weights for the input word are updated (this is true whether you’re using Negative Sampling or not).</p><h3>Selecting Negative Samples</h3><p>The “negative samples” (that is, the 5 output words that we’ll train to output 0) are chosen using a “unigram distribution”.</p><p>Essentially, the probability for selecting a word as a negative sample is related to its frequency, with more frequent words being more likely to be selected as negative samples.</p><p>In the word2vec C implementation, you can see the equation for this probability. Each word is given a weight equal to it’s frequency (word count) raised to the 3/4 power. The probability for a selecting a word is just it’s weight divided by the sum of weights for all words.</p><p>P(wi)=f(wi)3/4∑nj=0(f(wj)3/4)P(wi)=f(wi)3/4∑j=0n(f(wj)3/4)</p><p>The decision to raise the frequency to the 3/4 power appears to be empirical; in their paper they say it outperformed other functions. You can look at the shape of the function–just type this into Google: “plot y = x^(3/4) and y = x” and then zoom in on the range x = [0, 1]. It has a slight curve that increases the value a little.</p><p>The way this selection is implemented in the C code is interesting. They have a large array with 100M elements (which they refer to as the unigram table). They fill this table with the index of each word in the vocabulary multiple times, and the number of times a word’s index appears in the table is given by P(wi)P(wi) * table_size. Then, to actually select a negative sample, you just generate a random integer between 0 and 100M, and use the word at that index in the table. Since the higher probability words occur more times in the table, you’re more likely to pick those.</p><h3>Other Resources</h3><p>For the most detailed and accurate explanation of word2vec, you should check out the C code. I’ve published an extensively commented (but otherwise unaltered) version of the code <a href="https://github.com/chrisjmccormick/word2vec_commented">here</a>.</p><p>I’ve also created a <a href="http://mccormickml.com/2016/04/27/word2vec-resources/">post</a> with links to and descriptions of other word2vec tutorials, papers, and implementations.</p><h3>Cite</h3><p>McCormick, C. (2017, January 11). <em>Word2Vec Tutorial Part 2 — Negative Sampling</em>. Retrieved from <a href="http://www.mccormickml.com/">http://www.mccormickml.com</a></p><h4>Thanks for reading! We’d really appreciate it if you recommend this post (by clicking the ❤ button) so other people can find it.</h4><h4>P.S. If you enjoyed this article, please consider checking out <a href="https://nearist.ai/">Nearist.ai</a>, or <a href="https://nearist.typeform.com/to/kbnNLz">let’s talk</a> to discuss how can we help accelerate your machine learning efforts.</h4><figure><a href="https://nearist.typeform.com/to/kbnNLz"><img alt="" src="https://cdn-images-1.medium.com/max/200/1*zHZOG_mCa46rUnBJTAbTzA.png" /></a></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XKBIxesP3y7DM2rYmhnhaQ.png" /></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=fd99420a6dc" width="1" height="1" alt=""><hr><p><a href="https://medium.com/nearist-ai/word2vec-tutorial-part-2-negative-sampling-fd99420a6dc">Word2Vec Tutorial Part 2 — Negative Sampling</a> was originally published in <a href="https://medium.com/nearist-ai">Nearist.ai</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Word2Vec Tutorial — The Skip-Gram Model]]></title>
            <link>https://medium.com/nearist-ai/word2vec-tutorial-the-skip-gram-model-c7926e1fdc09?source=rss----9df37f73a999---4</link>
            <guid isPermaLink="false">https://medium.com/p/c7926e1fdc09</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[artificial-intelligence]]></category>
            <category><![CDATA[towards-data-science]]></category>
            <category><![CDATA[word2vec]]></category>
            <category><![CDATA[nlp]]></category>
            <dc:creator><![CDATA[Chris McCormick]]></dc:creator>
            <pubDate>Thu, 05 Jul 2018 20:04:38 GMT</pubDate>
            <atom:updated>2018-07-05T20:04:37.589Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*J3BtJTlHKnx3152UKoTgYg.jpeg" /><figcaption>Photo by Hal Gatewood on Unsplash</figcaption></figure><p>This tutorial covers the skip gram neural network architecture for Word2Vec. My intention with this tutorial was to skip over the usual introductory and abstract insights about Word2Vec, and get into more of the details. Specifically here I’m diving into the skip gram neural network model.</p><figure><a href="https://nearist.typeform.com/to/kbnNLz"><img alt="" src="https://cdn-images-1.medium.com/max/200/1*zHZOG_mCa46rUnBJTAbTzA.png" /></a></figure><h3>The Model</h3><p>The skip-gram neural network model is actually surprisingly simple in its most basic form; I think it’s the all the little tweaks and enhancements that start to clutter the explanation.</p><p>Let’s start with a high-level insight about where we’re going. Word2Vec uses a trick you may have seen elsewhere in machine learning. We’re going to train a simple neural network with a single hidden layer to perform a certain task, but then we’re not actually going to use that neural network for the task we trained it on! Instead, the goal is actually just to learn the weights of the hidden layer–we’ll see that these weights are actually the “word vectors” that we’re trying to learn.</p><p>Another place you may have seen this trick is in unsupervised feature learning, where you train an auto-encoder to compress an input vector in the hidden layer, and decompress it back to the original in the output layer. After training it, you strip off the output layer (the decompression step) and just use the hidden layer — it’s a trick for learning good image features without having labeled training data.</p><h3>The Fake Task</h3><p>So now we need to talk about this “fake” task that we’re going to build the neural network to perform, and then we’ll come back later to how this indirectly gives us those word vectors that we are really after.</p><p>We’re going to train the neural network to do the following. Given a specific word in the middle of a sentence (the input word), look at the words nearby and pick one at random. The network is going to tell us the probability for every word in our vocabulary of being the “nearby word” that we chose.</p><p>When I say “nearby”, there is actually a “window size” parameter to the algorithm. A typical window size might be 5, meaning 5 words behind and 5 words ahead (10 in total).</p><p>The output probabilities are going to relate to how likely it is find each vocabulary word nearby our input word. For example, if you gave the trained network the input word “Soviet”, the output probabilities are going to be much higher for words like “Union” and “Russia” than for unrelated words like “watermelon” and “kangaroo”.</p><p>We’ll train the neural network to do this by feeding it word pairs found in our training documents. The below example shows some of the training samples (word pairs) we would take from the sentence “The quick brown fox jumps over the lazy dog.” I’ve used a small window size of 2 just for the example. The word highlighted in blue is the input word.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/886/0*Q7o7qvuJf7W6JNeY.png" /></figure><p>The network is going to learn the statistics from the number of times each pairing shows up. So, for example, the network is probably going to get many more training samples of (“Soviet”, “Union”) than it is of (“Soviet”, “Sasquatch”). When the training is finished, if you give it the word “Soviet” as input, then it will output a much higher probability for “Union” or “Russia” than it will for “Sasquatch”.</p><h3>Model Details</h3><p>So how is this all represented?</p><p>First of all, you know you can’t feed a word just as a text string to a neural network, so we need a way to represent the words to the network. To do this, we first build a vocabulary of words from our training documents–let’s say we have a vocabulary of 10,000 unique words.</p><p>We’re going to represent an input word like “ants” as a one-hot vector. This vector will have 10,000 components (one for every word in our vocabulary) and we’ll place a “1” in the position corresponding to the word “ants”, and 0s in all of the other positions.</p><p>The output of the network is a single vector (also with 10,000 components) containing, for every word in our vocabulary, the probability that a randomly selected nearby word is that vocabulary word.</p><p>Here’s the architecture of our neural network.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*rr0vu6HAl-eFR513.png" /></figure><p>There is no activation function on the hidden layer neurons, but the output neurons use softmax. We’ll come back to this later.</p><p>When <em>training</em> this network on word pairs, the input is a one-hot vector representing the input word and the training output <em>is also a one-hot vector</em>representing the output word. But when you evaluate the trained network on an input word, the output vector will actually be a probability distribution (i.e., a bunch of floating point values, <em>not</em> a one-hot vector).</p><h3>The Hidden Layer</h3><p>For our example, we’re going to say that we’re learning word vectors with 300 features. So the hidden layer is going to be represented by a weight matrix with 10,000 rows (one for every word in our vocabulary) and 300 columns (one for every hidden neuron).</p><p>300 features is what Google used in their published model trained on the Google news dataset (you can download it from <a href="https://code.google.com/archive/p/word2vec/">here</a>). The number of features is a “hyper parameter” that you would just have to tune to your application (that is, try different values and see what yields the best results).</p><p>If you look at the <em>rows</em> of this weight matrix, these are actually what will be our word vectors!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/782/0*2DTpaVeNKWPYWApT.png" /></figure><p>So the end goal of all of this is really just to learn this hidden layer weight matrix — the output layer we’ll just toss when we’re done!</p><p>Let’s get back, though, to working through the definition of this model that we’re going to train.</p><p>Now, you might be asking yourself–“That one-hot vector is almost all zeros… what’s the effect of that?” If you multiply a 1 x 10,000 one-hot vector by a 10,000 x 300 matrix, it will effectively just <em>select</em> the matrix row corresponding to the “1”. Here’s a small example to give you a visual.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/621/0*Uw0tvs_O7XrQltbn.png" /></figure><p>This means that the hidden layer of this model is really just operating as a lookup table. The output of the hidden layer is just the “word vector” for the input word.</p><h3>The Output Layer</h3><p>The 1 x 300 word vector for “ants” then gets fed to the output layer. The output layer is a softmax regression classifier. There’s an in-depth tutorial on Softmax Regression <a href="http://ufldl.stanford.edu/tutorial/supervised/SoftmaxRegression/">here</a>, but the gist of it is that each output neuron (one per word in our vocabulary!) will produce an output between 0 and 1, and the sum of all these output values will add up to 1.</p><p>Specifically, each output neuron has a weight vector which it multiplies against the word vector from the hidden layer, then it applies the function exp(x) to the result. Finally, in order to get the outputs to sum up to 1, we divide this result by the sum of the results from <em>all</em> 10,000 output nodes.</p><p>Here’s an illustration of calculating the output of the output neuron for the word “car”.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*owmVKZwdL8TOiPEM.png" /></figure><p>Note that neural network does not know anything about the offset of the output word relative to the input word. It <em>does not</em> learn a different set of probabilities for the word before the input versus the word after. To understand the implication, let’s say that in our training corpus, <em>every single occurrence</em> of the word ‘York’ is preceded by the word ‘New’. That is, at least according to the training data, there is a 100% probability that ‘New’ will be in the vicinity of ‘York’. However, if we take the 10 words in the vicinity of ‘York’ and randomly pick one of them, the probability of it being ‘New’ <em>is not</em>100%; you may have picked one of the other words in the vicinity.</p><h3>Intuition</h3><p>Ok, are you ready for an exciting bit of insight into this network?</p><p>If two different words have very similar “contexts” (that is, what words are likely to appear around them), then our model needs to output very similar results for these two words. And one way for the network to output similar context predictions for these two words is if <em>the word vectors are similar</em>. So, if two words have similar contexts, then our network is motivated to learn similar word vectors for these two words! Ta da!</p><p>And what does it mean for two words to have similar contexts? I think you could expect that synonyms like “intelligent” and “smart” would have very similar contexts. Or that words that are related, like “engine” and “transmission”, would probably have similar contexts as well.</p><p>This can also handle stemming for you — the network will likely learn similar word vectors for the words “ant” and “ants” because these should have similar contexts.</p><h3>Next Up</h3><p>You may have noticed that the skip-gram neural network contains a huge number of weights… For our example with 300 features and a vocab of 10,000 words, that’s 3M weights in the hidden layer and output layer each! Training this on a large dataset would be prohibitive, so the word2vec authors introduced a number of tweaks to make training feasible. These are covered in <a href="http://mccormickml.com/2017/01/11/word2vec-tutorial-part-2-negative-sampling/">part 2 of this tutorial</a>.</p><h3>Other Resources</h3><p>I’ve also created a <a href="http://mccormickml.com/2016/04/27/word2vec-resources/">post</a> with links to and descriptions of other word2vec tutorials, papers, and implementations.</p><h3>Cite</h3><p>McCormick, C. (2016, April 19). <em>Word2Vec Tutorial — The Skip-Gram Model</em>. Retrieved from <a href="http://www.mccormickml.com/">http://www.mccormickml.com</a></p><h4>Thanks for reading! We’d really appreciate it if you recommend this post (by clicking the ❤ button) so other people can find it.</h4><h4>P.S. If you enjoyed this article, please consider checking out <a href="https://nearist.ai/">Nearist.ai</a>, or <a href="https://nearist.typeform.com/to/kbnNLz">let’s talk</a> to discuss how can we help accelerate your machine learning efforts.</h4><figure><a href="https://nearist.typeform.com/to/kbnNLz"><img alt="" src="https://cdn-images-1.medium.com/max/200/1*zHZOG_mCa46rUnBJTAbTzA.png" /></a></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XKBIxesP3y7DM2rYmhnhaQ.png" /></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c7926e1fdc09" width="1" height="1" alt=""><hr><p><a href="https://medium.com/nearist-ai/word2vec-tutorial-the-skip-gram-model-c7926e1fdc09">Word2Vec Tutorial — The Skip-Gram Model</a> was originally published in <a href="https://medium.com/nearist-ai">Nearist.ai</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[DBSCAN Clustering Tutorial]]></title>
            <link>https://medium.com/nearist-ai/dbscan-clustering-tutorial-dd6a9b637a4b?source=rss----9df37f73a999---4</link>
            <guid isPermaLink="false">https://medium.com/p/dd6a9b637a4b</guid>
            <category><![CDATA[artificial-intelligence]]></category>
            <category><![CDATA[clustering]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[python]]></category>
            <dc:creator><![CDATA[Chris McCormick]]></dc:creator>
            <pubDate>Thu, 05 Jul 2018 19:23:04 GMT</pubDate>
            <atom:updated>2018-07-05T19:23:29.073Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*0j0I4JlZ2mQRbT6oIj4H3w.jpeg" /><figcaption>Photo by Tavin Dotson on Unsplash</figcaption></figure><p>DBSCAN is a popular clustering algorithm which is fundamentally very different from k-means.</p><ul><li>In k-means clustering, each cluster is represented by a centroid, and points are assigned to whichever centroid they are closest to. In DBSCAN, there are no centroids, and clusters are formed by linking nearby points to one another.</li><li>k-means requires specifying the number of clusters, ‘k’. DBSCAN does not, but does require specifying two parameters which influence the decision of whether two nearby points should be linked into the same cluster. These two parameters are a distance threshold, εε (epsilon), and “MinPts” (minimum number of points), to be explained.</li><li>k-means runs over many iterations to converge on a good set of clusters, and cluster assignments can change on each iteration. DBSCAN makes only a single pass through the data, and once a point has been assigned to a particular cluster, it never changes.</li></ul><p>I like the language of trees for describing cluster growth in DBSCAN. It starts with an arbitrary seed point which has at least MinPts points nearby within a distance (or “radius”) of εε. We do a breadth-first search along each of these nearby points. For a given nearby point, we check how many points <em>it</em> has within its radius. If it has fewer than MinPts neighbors, this point becomes a <em>leaf</em>–we don’t continue to grow the cluster from it. If it <em>does</em> have at least MinPts, however, then it’s a <em>branch</em>, and we add all of its neighbors to the FIFO queue of our breadth-first search.</p><p>Once the breadth-first search is complete, we’re done with that cluster, and we never revisit any of the points in it. We pick a new arbitrary seed point (which isn’t already part of another cluster), and grow the next cluster. This continues until all of the points have been assigned.</p><p>There is one other novel aspect of DBSCAN which affects the algorithm. If a point has fewer than MinPts neighbors, <em>AND it’s not a leaf node of another cluster</em>, then it’s labeled as a “Noise” point that doesn’t belong to any cluster.</p><p>Noise points are identified as part of the process of selecting a new seed–if a particular seed point doesn’t have enough neighbors, it’s labeled as a Noise point. This label is often temporary, however–these Noise points are often picked up by some cluster as a leaf node.</p><figure><a href="https://nearist.typeform.com/to/kbnNLz"><img alt="" src="https://cdn-images-1.medium.com/max/200/1*zHZOG_mCa46rUnBJTAbTzA.png" /></a></figure><h3>Visualization</h3><p>Naftali Harris has created a great web-based <a href="https://www.naftaliharris.com/blog/visualizing-dbscan-clustering/">visualization</a> of running DBSCAN on a 2-dimensional dataset. Try clicking on the “Smiley” dataset and hitting the GO button. (That’s where the image from this post came from). Very cool!</p><h3>Algorithm in Python</h3><p>To fully understand the algorithm, I think it’s best to just look at some code.</p><p>Below is a working implementation in Python. Note that the emphasis in this implementation is on illustrating the algorithm… the distance calculations, for example, could be optimized significantly.</p><p>You can also find this code (along with an example that validates it’s correctness) on GitHub <a href="https://github.com/chrisjmccormick/dbscan">here</a>.</p><pre>import numpy<br><br>def MyDBSCAN(D, eps, MinPts):<br>    &quot;&quot;&quot;<br>    Cluster the dataset `D` using the DBSCAN algorithm.<br>    <br>    MyDBSCAN takes a dataset `D` (a list of vectors), a threshold distance<br>    `eps`, and a required number of points `MinPts`.<br>    <br>    It will return a list of cluster labels. The label -1 means noise, and then<br>    the clusters are numbered starting from 1.<br>    &quot;&quot;&quot;<br> <br>    # This list will hold the final cluster assignment for each point in D.<br>    # There are two reserved values:<br>    #    -1 - Indicates a noise point<br>    #     0 - Means the point hasn&#39;t been considered yet.<br>    # Initially all labels are 0.    <br>    labels = [0]*len(D)<br><br>    # C is the ID of the current cluster.    <br>    C = 0<br>    <br>    # This outer loop is just responsible for picking new seed points--a point<br>    # from which to grow a new cluster.<br>    # Once a valid seed point is found, a new cluster is created, and the <br>    # cluster growth is all handled by the &#39;expandCluster&#39; routine.<br>    <br>    # For each point P in the Dataset D...<br>    # (&#39;P&#39; is the index of the datapoint, rather than the datapoint itself.)<br>    for P in range(0, len(D)):<br>    <br>        # Only points that have not already been claimed can be picked as new <br>        # seed points.    <br>        # If the point&#39;s label is not 0, continue to the next point.<br>        if not (labels[P] == 0):<br>           continue<br>        <br>        # Find all of P&#39;s neighboring points.<br>        NeighborPts = regionQuery(D, P, eps)<br>        <br>        # If the number is below MinPts, this point is noise. <br>        # This is the only condition under which a point is labeled <br>        # NOISE--when it&#39;s not a valid seed point. A NOISE point may later <br>        # be picked up by another cluster as a boundary point (this is the only<br>        # condition under which a cluster label can change--from NOISE to <br>        # something else).<br>        if len(NeighborPts) &lt; MinPts:<br>            labels[P] = -1<br>        # Otherwise, if there are at least MinPts nearby, use this point as the <br>        # seed for a new cluster.    <br>        else: <br>           # Get the next cluster label.<br>           C += 1<br>           <br>           # Assing the label to our seed point.<br>           labels[P] = C<br>           <br>           # Grow the cluster from the seed point.<br>           growCluster(D, labels, P, C, eps, MinPts)<br>    <br>    # All data has been clustered!<br>    return labels<br><br><br>def growCluster(D, labels, P, C, eps, MinPts):<br>    &quot;&quot;&quot;<br>    Grow a new cluster with label `C` from the seed point `P`.<br>    <br>    This function searches through the dataset to find all points that belong<br>    to this new cluster. When this function returns, cluster `C` is complete.<br>    <br>    Parameters:<br>      `D`      - The dataset (a list of vectors)<br>      `labels` - List storing the cluster labels for all dataset points<br>      `P`      - Index of the seed point for this new cluster<br>      `C`      - The label for this new cluster.  <br>      `eps`    - Threshold distance<br>      `MinPts` - Minimum required number of neighbors<br>    &quot;&quot;&quot;<br><br>    # SearchQueue is a FIFO queue of points to evaluate. It will only ever <br>    # contain points which belong to cluster C (and have already been labeled<br>    # as such).<br>    #<br>    # The points are represented by their index values (not the actual vector).<br>    #<br>    # The FIFO queue behavior is accomplished by appending new points to the<br>    # end of the list, and using a while-loop rather than a for-loop.<br>    SearchQueue = [P]<br><br>    # For each point in the queue:<br>    #   1. Determine whether it is a branch or a leaf<br>    #   2. For branch points, add their unclaimed neighbors to the search queue<br>    i = 0<br>    while i &lt; len(SearchQueue):    <br>        <br>        # Get the next point from the queue.        <br>        P = SearchQueue[i]<br><br>        # Find all the neighbors of P<br>        NeighborPts = regionQuery(D, P, eps)<br>        <br>        # If the number of neighbors is below the minimum, then this is a leaf<br>        # point and we move to the next point in the queue.<br>        if len(NeighborPts) &lt; MinPts:<br>            i += 1<br>            continue<br>        <br>        # Otherwise, we have the minimum number of neighbors, and this is a <br>        # branch point.<br>            <br>        # For each of the neighbors...<br>        for Pn in NeighborPts:<br>           <br>            # If Pn was labelled NOISE during the seed search, then we<br>            # know it&#39;s not a branch point (it doesn&#39;t have enough <br>            # neighbors), so make it a leaf point of cluster C and move on.<br>            if labels[Pn] == -1:<br>               labels[Pn] = C<br>            # Otherwise, if Pn isn&#39;t already claimed, claim it as part of<br>            # C and add it to the search queue.   <br>            elif labels[Pn] == 0:<br>                # Add Pn to cluster C.<br>                labels[Pn] = C<br>                <br>                # Add Pn to the SearchQueue.<br>                SearchQueue.append(Pn)<br>            <br>        # Advance to the next point in the FIFO queue.<br>        i += 1        <br>    <br>    # We&#39;ve finished growing cluster C!<br><br><br>def regionQuery(D, P, eps):<br>    &quot;&quot;&quot;<br>    Find all points in dataset `D` within distance `eps` of point `P`.<br>    <br>    This function calculates the distance between a point P and every other <br>    point in the dataset, and then returns only those points which are within a<br>    threshold distance `eps`.<br>    &quot;&quot;&quot;<br>    neighbors = []<br>    <br>    # For each point in the dataset...<br>    for Pn in range(0, len(D)):<br>        <br>        # If the distance is below the threshold, add it to the neighbors list.<br>        if numpy.linalg.norm(D[P] - D[Pn]) &lt; eps:<br>           neighbors.append(Pn)<br>            <br>    return neighbors</pre><h4>Thanks for reading! We’d really appreciate it if you recommend this post (by clicking the ❤ button) so other people can find it.</h4><h4>P.S. If you enjoyed this article, please consider checking out <a href="https://nearist.ai/">Nearist.ai</a>, or <a href="https://nearist.typeform.com/to/kbnNLz">let’s talk</a> to discuss how can we help accelerate your machine learning efforts.</h4><figure><a href="https://nearist.typeform.com/to/kbnNLz"><img alt="" src="https://cdn-images-1.medium.com/max/200/1*zHZOG_mCa46rUnBJTAbTzA.png" /></a></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XKBIxesP3y7DM2rYmhnhaQ.png" /></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=dd6a9b637a4b" width="1" height="1" alt=""><hr><p><a href="https://medium.com/nearist-ai/dbscan-clustering-tutorial-dd6a9b637a4b">DBSCAN Clustering Tutorial</a> was originally published in <a href="https://medium.com/nearist-ai">Nearist.ai</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[k-NN Benchmarks Part I — Wikipedia]]></title>
            <link>https://medium.com/nearist-ai/k-nn-benchmarks-part-i-wikipedia-3bda9aa535a?source=rss----9df37f73a999---4</link>
            <guid isPermaLink="false">https://medium.com/p/3bda9aa535a</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[gpu]]></category>
            <category><![CDATA[similarity-search]]></category>
            <category><![CDATA[knn]]></category>
            <dc:creator><![CDATA[Chris McCormick]]></dc:creator>
            <pubDate>Thu, 05 Jul 2018 18:46:44 GMT</pubDate>
            <atom:updated>2018-07-05T18:46:43.543Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*OyB8bi29G-ZHJOALL9NU7A.jpeg" /></figure><p>This article is the first in a series comparing different available methods for accelerating large-scale k-Nearest Neighbor searches on high-dimensional vectors (i.e., 100 components or more). The emphasis here is on practicality versus novelty–that is, we’re focusing on solutions which are readily available and can be used in production applications with minimal engineering effort.</p><p>At <a href="https://nearist.ai/">Nearist</a>, we have developed a product specifically for accelerating large-scale k-NN search, and have included its performance in these benchmarks to demonstrate it’s strengths. That said, we’ve tried to give each of the platforms a thorough evaluation, and hopefully you will find our results and experiences informative no matter what platform you choose.</p><p>This post currently contains the preliminary results of our experiments, and will be updated in the coming months with more data.</p><figure><a href="https://nearist.typeform.com/to/kbnNLz"><img alt="" src="https://cdn-images-1.medium.com/max/200/1*zHZOG_mCa46rUnBJTAbTzA.png" /></a></figure><ol><li><a href="http://mccormickml.com/2017/09/08/knn-benchmarks-part-1/#the-benchmark">The Benchmark</a></li></ol><ul><li><a href="http://mccormickml.com/2017/09/08/knn-benchmarks-part-1/#concept-search-on-wikipedia">Concept Search on Wikipedia</a></li><li><a href="http://mccormickml.com/2017/09/08/knn-benchmarks-part-1/#comparison-criteria">Comparison criteria</a></li></ul><p>2. <a href="http://mccormickml.com/2017/09/08/knn-benchmarks-part-1/#the-contenders">The Contenders</a></p><ul><li><a href="http://mccormickml.com/2017/09/08/knn-benchmarks-part-1/#desktop-cpu">Desktop CPU</a></li><li><a href="http://mccormickml.com/2017/09/08/knn-benchmarks-part-1/#nvidia-tesla-k80-gpu">Nvidia Tesla K80 GPU</a></li><li><a href="http://mccormickml.com/2017/09/08/knn-benchmarks-part-1/#knn-cuda-library">knn-cuda library</a></li><li><a href="http://mccormickml.com/2017/09/08/knn-benchmarks-part-1/#amazon-p2-instance">Amazon P2 instance</a></li><li><a href="http://mccormickml.com/2017/09/08/knn-benchmarks-part-1/#nearist-vector-search-accelerator-vsx">Nearist Vector Search Accelerator (VSX)</a></li></ul><p>3. <a href="http://mccormickml.com/2017/09/08/knn-benchmarks-part-1/#benchmark-results">Benchmark Results</a></p><ul><li><a href="http://mccormickml.com/2017/09/08/knn-benchmarks-part-1/#latency-measurements">Latency Measurements</a></li><li><a href="http://mccormickml.com/2017/09/08/knn-benchmarks-part-1/#throughput-measurements">Throughput Measurements</a></li><li><a href="http://mccormickml.com/2017/09/08/knn-benchmarks-part-1/#conclusions">Conclusions</a></li></ul><h3>1. The Benchmark</h3><h3>Concept Search on Wikipedia</h3><p>Each of our benchmark articles will look at performance on a different k-NN based task. In this article, we will be doing a k-NN search on roughly 4.2 million topic model vectors generated from all of the articles in English Wikipedia.</p><p>This is an example of a technique known as concept search–you take a document, generate a feature vector from it, and then compare it against the feature vectors for a repository of documents (in this case, Wikipedia articles) to find “conceptually similar” documents.</p><p>For example, if we use the Wikipedia article for <em>Personal computer</em> as our query for a k-NN search, we get back the results <em>Homebuilt computer</em>, <em>Desktop computer</em>, and <em>Macintosh 128k</em> (the original Macintosh).</p><p>Parsing all of Wikipedia and generating feature vectors for the text is a big project in its own right. Fortunately, <a href="https://radimrehurek.com/">Radim Řehůřek</a> has already done exactly this and shared his implementation in the <a href="https://radimrehurek.com/gensim/">gensim</a> package in Python. I previously <a href="http://mccormickml.com/2017/02/22/concept-search-on-wikipedia/">shared a post</a> on our experience with this, and also shared a modified and <a href="https://github.com/chrisjmccormick/wiki-sim-search">commented version of the code</a>.</p><p>The ‘gensim’ package supports multiple topic models for converting text into vectors. For these benchmarks, we chose to use Latent Dirichlet Analysis (LDA) with 128 topics (that is, 128 features in the feature vectors).</p><h3>Comparison criteria</h3><p>Over this series of benchmarks, there are multiple aspects to k-NN performance that we are interested in and will evaluate:</p><ul><li>Latency for a single search</li><li>Throughput for a batch of searches</li><li>Memory load time for the GPU and Nearist hardware.</li><li>Accuracy (as impacted by approximation techniques)</li><li>Engineering effort</li></ul><p>This first benchmarking post will focus on just the first two–latency and throughput.</p><h3>2. The Contenders</h3><p>We evaluated three different k-NN implementations:</p><ul><li>k-NN in scikit-learn on a desktop PC (as a baseline)</li><li>GPU acceleration with a Tesla K80</li><li>A prototype version of Nearist’s Vector Search Accelerator (VSX), which uses a custom hardware architecture.</li></ul><h3>Desktop CPU</h3><p>The first platform was simply a brute-force search using the k-NN implementation in scikit-learn in Python, running on a desktop PC, which has a 4th generation Intel i7 4770 (from around 2013) with 16GB of RAM. This was intended merely to serve as a baseline for comparison of the other two platforms.</p><h3>Nvidia Tesla K80 GPU</h3><h4>knn-cuda library</h4><p>There don’t appear to be many publicly available kNN GPU implementations; of those, knn-cuda appears to be the most established option.</p><p>Like the Nearist VSX, knn-cuda uses a brute-force method–that is, it calculates and sorts all of the distance values. It accelerates k-NN by leveraging the GPU’s ability to greatly accelerate the matrix-multiplication step at the center of the distance calculations. It also accelerates the sorting of the results.</p><p>A note on engineering effort with knn-cuda: While we were able to perform our experiments with the knn-cuda library as-is, the authors note that it “was written in the context of a Ph.D. thesis” and that it “should be adapted to the problem and to the specifications of the GPU used.” That is to say, knn-cuda doesn’t necessarily provide an off-the-shelf implementation of k-NN that is ready for a production application–some further work by a CUDA engineer is required to make best use of the GPU.</p><h4>Amazon P2 instance</h4><p>Amazon started offering the P2 instances containing Tesla K80s at the end of 2016. GPU users will note that the K80 is now several generations old, and newer Tesla cards would achieve higher performance in our benchmark. However, we wanted to choose the platform with the lowest barrier to entry, and Amazon instances are trusted and widely used in production applications. Amazon instances have the added benefit of scalability–the ability to increase or decrease the number of GPUs based on demand.</p><p>The Tesla K80 actually includes 2 GPU chips (two NVIDIA GK210s) on a single board. CUDA does not automatically divide the computation across the two GPUs for you, however. In order to leverage both GPUs on the K80, you must divide your task across them and then consolidate the results. For this article, we have chosen to simply use a single GK210. In future articles, we plan to publish results using multiple GK210s and even multiple K80 cards.</p><h3>Nearist Vector Search Accelerator (VSX)</h3><p>The VSX Orion is a rack-mounted server appliance that fits in a 4U space. Inside the server are PCIe cards which contain Nearist’s custom hardware accelerators.</p><p>The Orion hardware architecture takes advantage of the easy parallelism in k-NN and divides the search task across hundreds of Vector Comparison Units (VCUs) contained on the PCIe cards in the server. Each VCU operates on a different chunk of the dataset, and then results are aggregated and consolidated by a CPU.</p><p>The VSX appliance is still in development, and today we have a much smaller scale prototype. Our prototype consists of a single PCIe card with only about 1/10th of the VCUs that the production version will have. Even this limited prototype outperformed both the CPU and GPU in our benchmark, however.</p><h3>3. Benchmark Results</h3><h3>Latency Measurements</h3><p>The following table shows the time taken (in seconds) to perform a k-NN search against the 4.2 million wikipedia articles with only a single query vector. The measurements are all averaged over 5 runs.</p><p>Here again is a summary of the platforms:</p><ul><li>Scikit-learn — Python library running on an Intel i7 4770</li><li>GPU — A single GK210 GPU in a Tesla K80</li><li>Nearist — A 1/10th scale prototype Nearist board</li></ul><p>These results are preliminary, and we will update them in the coming months. Note that in these current results we are only using half of the compute power on the K80 (since we are only using one GK210 chip), and that the prototype Nearist board only has about 1/10th of the compute power of the production version.</p><p><em>Latency in seconds</em></p><p>scikit-learnGPUNearistK = 10.603.870.17K = 101.233.800.17K = 1001.853.860.17</p><p>Notice that the GPU is actually slower than the CPU when only presented with one query at a time. One reason is because GPUs are more efficient at performing matrix-matrix multiplication (multiple query vectors against the dataset) than they are at performing vector-matrix multiplication (a single query vector against the dataset).</p><p>Also notice how the GPU implementation is relatively unaffected by the value of <em>k</em>, whereas scikit-learn performance decreases with larger values of <em>k</em>. The scikit-learn behavior suggests that they might be optimizing the sorting technique based on the value of <em>k</em>.</p><p>The Nearist hardware also is relatively unaffected by the value of <em>k</em>; this is due to efficient parallelization of the sorting process in the Nearist architecture. Increasing <em>k</em> does increase the Nearist latency, but the effect is only on the order of a few milliseconds, and so it isn’t visible here.</p><h3>Throughput Measurements</h3><p>The next table shows the average throughput (in queries per second) achieved by each of the different platforms when presented with an input batch of 100 query vectors.</p><p>The throughput tends to be higher than just 1 / latency. This is because the PC, GPU, and Nearist hardware all have the ability to process multiple queries in parallel to varying degrees. The throughput is reported as the average number of queries per second (calculated as 100 queries / total processing time).</p><p>The measurements are all averaged over 5 runs.</p><p><em>Throughput in queries / second</em></p><p>scikit-learnGPUNearistK = 126.1525.7494.12K = 1010.5126.3294.12K = 1006.6120.4094.12</p><p>The throughput numbers show the same behaviors surrounding the value of <em>k</em>, with the CPU performance being the most impacted by the value of <em>k</em>.</p><p>This is also where we start to see the GPU outperforming the CPU, when it is able to operate on more query vectors simultaneously.</p><h3>Conclusions</h3><p>The Nearist prototype board only has 1/10th of the performance of the production version, but already shows a more than 10x improvement over the CPU in throughput and latency for k-NN with k=100. Against the GPU, the Nearist prototype board has more than 20x better latency, and more than 4x greater throughput at k=100.</p><p>In the coming months, we will update this post with GPU measurements using both chips on the Tesla K80 card (which should give a roughly 2x improvement), and we’ll also update the Nearist results using the full-performance production card (which should give roughly a 10x improvement).</p><p>In our next benchmarking post, we will look at a classification task which will allow us to compare accuracy in addition to the throughput and latency. We will also add results using the Annoy library in Python, which uses approximate nearest neighbor techniques.</p><h4>Thanks for reading! We’d really appreciate it if you recommend this post (by clicking the ❤ button) so other people can find it.</h4><h4>P.S. If you enjoyed this article, please consider checking out <a href="https://nearist.ai/">Nearist.ai</a>, or <a href="https://nearist.typeform.com/to/kbnNLz">let’s talk</a> to discuss how can we help accelerate your machine learning efforts.</h4><figure><a href="https://nearist.typeform.com/to/kbnNLz"><img alt="" src="https://cdn-images-1.medium.com/max/200/1*zHZOG_mCa46rUnBJTAbTzA.png" /></a></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XKBIxesP3y7DM2rYmhnhaQ.png" /></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3bda9aa535a" width="1" height="1" alt=""><hr><p><a href="https://medium.com/nearist-ai/k-nn-benchmarks-part-i-wikipedia-3bda9aa535a">k-NN Benchmarks Part I — Wikipedia</a> was originally published in <a href="https://medium.com/nearist-ai">Nearist.ai</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>