<?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 Vedashree Patil on Medium]]></title>
        <description><![CDATA[Stories by Vedashree Patil on Medium]]></description>
        <link>https://medium.com/@vedaaa29296?source=rss-6cf03c573940------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/2*Iv8PwyUV0aOjxrmmGX20mg.jpeg</url>
            <title>Stories by Vedashree Patil on Medium</title>
            <link>https://medium.com/@vedaaa29296?source=rss-6cf03c573940------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Mon, 16 Nov 2026 21:01:12 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@vedaaa29296/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[Go, Neo4J, and AWS Lambda….]]></title>
            <link>https://medium.com/data-science/go-neo4j-and-aws-lambda-4cdd1af8886d?source=rss-6cf03c573940------2</link>
            <guid isPermaLink="false">https://medium.com/p/4cdd1af8886d</guid>
            <category><![CDATA[neo4j]]></category>
            <category><![CDATA[golang]]></category>
            <category><![CDATA[aws-lambda]]></category>
            <category><![CDATA[serverless]]></category>
            <category><![CDATA[go]]></category>
            <dc:creator><![CDATA[Vedashree Patil]]></dc:creator>
            <pubDate>Mon, 08 Jun 2020 12:24:11 GMT</pubDate>
            <atom:updated>2020-06-09T13:36:50.062Z</atom:updated>
            <content:encoded><![CDATA[<h4>And the nitty-gritty of making them work together</h4><p>I work with <a href="https://neo4j.com/">Neo4j</a> almost every day and being a Python developer, I mostly couple the both of them together for writing most of my logic. Over the past few days, however, since I started using Golang, I seem to have developed a strong affinity towards it.</p><p>I wanted to build a simple service using AWS Lambda that would execute simple queries against my Neo4j Database and decided to use Go for a change. Knowing that there are official Go drivers for Neo4j was an obvious relief. But the first few attempts turned out to be utter failures.</p><p>Don’t worry though, the good news is, you can definitely use AWS Lambda, Go and Neo4j together. There’s just a few extra steps that need to be carried out first.</p><h3>The Catch…</h3><blockquote>Yes, Neo4j has an <a href="https://github.com/neo4j/neo4j-go-driver"><strong>official driver for Golang</strong></a>.</blockquote><blockquote>No, it&#39;s not written in pure Go.</blockquote><p>What does this mean? The neo4j-go-driver depends on a C library called “<a href="https://github.com/neo4j-drivers/seabolt"><strong>Seabolt</strong></a>” for connecting to the database instance over the bolt protocol.</p><p>This means you’ll have to explicitly install the library before you can start executing the Go code for Neo4j. Moreover, seabolt in turn requires <strong>OpenSSL (TLS in case of Windows)</strong> to be installed on your local system for it to function well.</p><p>Installing OpenSSL and Seabolt on your local machine is pretty hassle-free. In fact, OpenSSL comes pre-installed in many Operating systems. (I used a Linux system which already had OpenSSL and all I had to do was install Seabolt after following <a href="https://github.com/neo4j-drivers/seabolt/blob/1.7/README.md">these <strong>instructions</strong></a>)</p><p>The challenge arises when we want to replicate the same thing using AWS Lambda. Go, being a <strong>statically typed language</strong> is first compiled into a binary file which is then made available as a handler for the Lambda function. Typically this won’t cause any problems if all the dependencies are Go-based or if you’re working on your local system.</p><p>However, In our case, the Go binary depends on external C object files and links them at runtime. But How do we make these C files available to the lambda functions?</p><h3>The Solution</h3><p>After spending a considerable amount of time scouring the internet for a possible solution, I couldn’t come across anything concrete, especially for Go. Most solutions are targeted towards python (since certain python libraries use C dependencies too) and I was almost tempted to go back to my old friend Python. But, even if the languages are different, the concept remains the same.</p><h4>Enter AWS Lambda Layers….</h4><p>In the simplest sense, a <a href="https://docs.aws.amazon.com/lambda/latest/dg/configuration-layers.html">Lambda Layer </a>is a piece of code that can be shared by different services. Typically, a layer will consist of a bunch of heavyweight dependencies that are required by most of the functions. In our case, we will package our C dependencies together and make them available to the lambda function using Layers.</p><h4>TL;DR</h4><p>The entire code including an example lambda function and instructions for setup is <a href="https://github.com/vedashree29296/neo4j-go-lambda-connector">available on my GitHub repository.</a></p><h4>Step 1: Packaging the C libraries</h4><p>Since AWS often uses <strong>CentOS-based</strong> containers for deploying lambda functions, <strong>Docker</strong> becomes an obvious choice to download and compile the C dependencies.</p><p>We create a custom docker image using <strong>lambci/lambda-base</strong> image as the base image and install all our dependencies on it.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/74993a1bf334b7d0a85b5670f69fc9fa/href">https://medium.com/media/74993a1bf334b7d0a85b5670f69fc9fa/href</a></iframe><p>The base image already has OpenSSL installed and configured. The only library needed now is Seabolt.</p><p>Seabolt is downloaded as a<strong> .tar package</strong> and extracted to the <strong>/usr/local/lib64</strong> directory within the docker image. To make it available to the Lambda functions, we move the contents to the <strong>/opt/lib</strong> directory which is one the directories that are searched during runtime linking. ( This is specified in an environment variable called <strong>LD_LIBRARY_PATH</strong>)</p><p>Once the image is built, we need to dump the contents of the <strong>/opt/lib</strong> folder to a folder on our local system that will be later converted to a layer</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/85f91954effd506a744807912e69358e/href">https://medium.com/media/85f91954effd506a744807912e69358e/href</a></iframe><p>Running this script will create a directory called <strong>layer</strong> which will contain the .so files specific to Seabolt within the <strong>layer/lib</strong> folder.</p><h4>Step 2: Create A Layer</h4><p>Now, all we have to do is create a Layer. There are two ways of doing this. First, we create a Layer using the AWS console or the CLI and upload the contents of the layer/ directory as a .zip file.</p><p>Another way is to use the <a href="https://www.serverless.com/"><strong>serverless framework</strong> </a>that will do all the work for you. All you need is a file call <strong>serverless.yml</strong> that specifies the details for your layer.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b4acff7b0feb7fee42274550d7ba2478/href">https://medium.com/media/b4acff7b0feb7fee42274550d7ba2478/href</a></iframe><p>And run simply run serverless deploy from your working directory.</p><p>You will get <strong>ARN URL</strong> for your newly created layer which you can easily attach to your lambda functions.</p><h4>Next Steps: Create your Own Go Handler Function</h4><p>Once the layer is successfully created, you can go ahead and create your custom handler functions that can communicate with Neo4J.</p><p>The<a href="https://github.com/vedashree29296/neo4j-go-lambda-connector/tree/master/neo4j-lambda-connector"> GitHub repository</a> includes a sample handler function that creates a simple node in Neo4j which is deployed using a serverless framework. For more reference on how to create Lambda functions using Go and serverless, this is a <a href="https://www.serverless.com/examples/aws-golang-http-get-post/">useful link to get started with</a>.</p><p>Thanks for reading!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4cdd1af8886d" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/go-neo4j-and-aws-lambda-4cdd1af8886d">Go, Neo4J, and AWS Lambda….</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[A Day described in Grakn]]></title>
            <link>https://medium.com/data-science/a-day-described-in-grakn-part-i-46bb7e3cd82a?source=rss-6cf03c573940------2</link>
            <guid isPermaLink="false">https://medium.com/p/46bb7e3cd82a</guid>
            <category><![CDATA[graph-database]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[graph]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[grakn]]></category>
            <dc:creator><![CDATA[Vedashree Patil]]></dc:creator>
            <pubDate>Thu, 05 Mar 2020 19:48:45 GMT</pubDate>
            <atom:updated>2020-03-06T07:38:47.302Z</atom:updated>
            <content:encoded><![CDATA[<h4>Graphbits: A Bunch of 5-minute Articles All about Graphs</h4><h4>The Grakn Schema</h4><p>Let’s talk about hypergraphs! Long story short, a Hypergraph can have edges that connect more than two nodes at a time. So there must be a database with the Hypergraph model right? Yes, there is and it’s <a href="https://grakn.ai/"><strong>Grakn</strong></a>…and that’s what this post (and a bunch of few others) is going to talk about.</p><h3>Grakn</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*nn4s30Civ3YaGdQugvh3hg.png" /><figcaption><a href="https://camo.githubusercontent.com/a4b2afa276e152da35ecbd6454755fc14182b891/68747470733a2f2f6772616b6e2e61692f6173736574732f696d672f6772616b6e2d6c6f676f2d6e616d652e706e67">source</a></figcaption></figure><p><a href="https://grakn.ai/"><strong>Grakn</strong></a> is quoted to be “an intelligent database” that allows you to model knowledge bases for different domains by extending the Entity-Relation approach (which was mostly used for SQL databases). Powered by an automated reasoning engine, it is capable of performing logical inference on large datasets. Grakn has its own declarative query language called Graql and also ships with its own <strong>visualization tool</strong> called the <strong>Grakn Workbase</strong>. (more on this later)</p><p>Enough talk…let’s get down to basics.</p><h4>The Grakn Schema</h4><p>Before any data is loaded into the database, a schema should be created.</p><p>Think of the schema as a blueprint of the database that gives you a coherent idea of how the data is going to be structured.</p><p>Mind you! Schema design is the first and the most crucial step while creating a database. Almost all the other operations depend upon how the schema is defined.</p><p>Let’s create a simple schema using an example.</p><p>Consider this scenario</p><blockquote>The city of Whatsville was hosting a concert by Gina Goodvoice on New Year’s Eve and the city was expecting a surge of visitors from the neighboring cities. Bobby was one of them. Wanting to explore the city, Bobby decided to arrive beforehand. He took the train from WhoTown and arrived in Whatsville that morning and met his friend Tim for breakfast at a nearby cafe. He then decided to visit the City Museum and bought a book along the way. For lunch, he bought a sandwich from a food truck and sat by the lakeside for a while. By evening, he headed towards the city stadium where the concert was going to be held. He had a great time at the concert, listening to the tunes of Gina Goodvoice. The concert went on till late night, post which, Bobby took the last train back home.</blockquote><p>Why am I digressing so much? The reason is simple.</p><p>Imagine Bobby’s world. Or rather, Bobby’s day. There were people he met; places he visited; things he bought etc. It’s just a series of events that took place throughout the day. Now, we’re going to model this same day in Grakn.</p><p>To create a schema, you first need to identify the entities, attributes, relations, and roles. Here’s a brief description of each of them</p><ul><li><strong>Entities</strong> exist independently. They’re something that&#39;s physically there.</li><li><strong>Relations </strong>usually represent some form of connection between the entities.</li><li>The characteristics of an entity or a relation can be specified using <strong>Attributes</strong>.</li><li>And finally, in any relation, the entities (or attributes) always play a certain <strong>Role</strong></li></ul><p>Confused? Let’s identify each of these for our example.</p><p>What are the things that can be called entities? A simple approach is to identify people, places, and things (and animals too if they’re there)</p><p>So we have Bobby, Tim, Gina Goodvoice, Whatsville, WhoTown, the train that Bobby took, the cafe he had breakfast in, the stadium where the concert was held, the sandwich he bought and much more. There! We have our basic <strong>entities: Person, Place, and Thing.</strong></p><p>Now, what can be the characteristics of these entities? So a person can have a <strong>name and an age,</strong> for example. A city (or any place) can have a <strong>name</strong>, a <strong>parent country/state, a latitude, a longitude</strong>, etc to identify it. Similarly, a thing can also have a name and other certain characteristics. These can be your attributes.</p><p>Next, if you think closely, what connects all these entities together? <strong>An</strong> <strong>event</strong>.</p><p>The concert by Gina Goodvoice is an event that links Bobby, Tim, Gina and takes place at the stadium on New Year’s Eve. That’s an event, and the relation in your schema that links a person, a place and a thing.</p><p>Further, a person plays the <strong>role</strong> of a <strong>participant</strong> in the event and the place plays the role of the event’s location. There, we assigned roles to the entities in the relationship.</p><h3>Down to the code</h3><p>Alright, it’s time to start tapping away. We’re going to create the schema that we earlier defined for Grakn.</p><p><strong>But first! Installations:</strong></p><p>Make sure you have got the Grakn server and the Workbase installed. If not, then take a <a href="https://grakn.ai/download">detour here</a> and come back.</p><h4>Creating the schema</h4><p>The schema can be defined in a file with a “.<strong>gql</strong>” extension.</p><p>The schema definition always starts with the keyword “<strong>define</strong>”.</p><p>Next, we define the entities. So we have a <strong>person, location and thing</strong> as our entities. Additionally, we can define the entity’s attributes and roles.</p><p>Like a <strong>person has an attribute name and plays the role of a participant</strong> in an event.</p><ul><li>The keyword<strong> “sub” </strong>is used to specify an <strong>entity, relation or attributes</strong>.</li><li><strong>Attributes</strong> for an entity or a relationship are defined using the “<strong>has” </strong>keyword.</li><li>The <strong>Roles</strong> are defined using the<strong> “plays” </strong>keyword.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/507/1*FpJwgqkWFOOhaqGzKosMYA.png" /><figcaption>Defining entities</figcaption></figure><p>Next, we need to define all the <strong>attributes</strong> that are mentioned in the schema. When defining each attribute, the datatype of the attribute must be specified. This can be done using the “<strong>datatype</strong>” keyword.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/685/1*RFpfzKHhOjSROpDlHmVvng.png" /><figcaption>Defining attributes</figcaption></figure><p>Finally, down to the relationships. Relationship<strong> </strong>definitions are similar to an entity definition. <strong>A relation can have attributes and even play roles</strong>.</p><p>The “<strong>relates</strong>” keyword is used in the definition to specify <strong>which roles the relationship connects. A relation can connect attributes, entities and even relations!</strong></p><p>For example, the event relationship relates to the roles “<strong>eventParticipant</strong>” and “<strong>eventLocation</strong>” which are played by the entities person and location respectively.</p><p>(Note that a relation can connect roles and not entities)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/581/1*wgabMr4xywxph3NckX9WRA.png" /><figcaption>Defining relations</figcaption></figure><p>Now that we’ve defined the schema. We need to load it into Grakn.</p><h4><strong>Loading the schema into Grakn</strong></h4><p>Head over to your terminal and start the Grakn server:</p><pre>grakn server start</pre><p>Now load the schema using:</p><pre>grakn console -k grakn_example -f schema.gql</pre><p>The<strong> -k </strong>argument<strong> </strong>here stands for the “<strong>keyspace</strong>”. Think of the keyspace as the name of your database. While the <strong>-f</strong> here is the “<strong>file path”</strong> to the schema file.</p><h4>Final checks</h4><p>If you get an output such as</p><pre>Successful commit: schema.gql</pre><p>Then that means your schema is loaded. Now you can head over to Grakn Workbase and see your schema. It should look somewhat like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*l2ggzbdBXb8nAzsCtHsjXQ.png" /><figcaption>The Grakn schema: (The arrows in yellow will tell you what each shape signifies)</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/631/1*LPIzRFo0jT-fRFpoF2JyqA.png" /><figcaption>A simple way of deciphering the schema diagram</figcaption></figure><p>And done! The next step is to load the data into a database…. and that deserves a whole post to itself. So all I can say is stay tuned! And happy reading!</p><p>Link to previous blogs:</p><ul><li><a href="https://towardsdatascience.com/the-graph-epiphany-4050e96ddcf6">The Graph Epiphany</a></li><li><a href="https://towardsdatascience.com/the-graph-models-656a0005aa21">The Graph Models</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=46bb7e3cd82a" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/a-day-described-in-grakn-part-i-46bb7e3cd82a">A Day described in Grakn</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[The Graph Models]]></title>
            <link>https://medium.com/data-science/the-graph-models-656a0005aa21?source=rss-6cf03c573940------2</link>
            <guid isPermaLink="false">https://medium.com/p/656a0005aa21</guid>
            <dc:creator><![CDATA[Vedashree Patil]]></dc:creator>
            <pubDate>Wed, 04 Mar 2020 02:43:57 GMT</pubDate>
            <atom:updated>2020-03-06T07:34:32.311Z</atom:updated>
            <content:encoded><![CDATA[<h4>Graphbits: A bunch of 5 min articles all about graphs</h4><p>The <a href="https://towardsdatascience.com/the-graph-epiphany-4050e96ddcf6">previous blog</a> was all about the applications of graphs. Time to dive deeper! Let’s talk about the graph data structure itself. I swear to keep the jargon to the bare minimum for this one.</p><h4>What’s a Graph again?</h4><p>So let me reiterate this one more time. You have two aspects to a graph data structure:</p><ul><li>The node</li><li>The relation</li></ul><p>Think of the Node to be any real-world entity. In the simplest sense, something you can see or something that physically exists. It can be a person, a place, a burger, a movie….I guess you get it.</p><p>A relationship is just some sort of interaction between nodes. More on an abstract level. Like a friendship between two people. Or a highway between two cities. Simple right?</p><p>Moving on, let&#39;s look at the data models for graphs. There are two main types of data models for any graph database:</p><h4>The Property Graph Model</h4><p>Once upon a time, there were two nodes. Each had a name and a handful of characteristics. And they were connected by one relationship. And that, my dear friends, is a property graph model.</p><p>In short, both, the nodes and relations have a generic label assigned to them. Additionally, the nodes and relationships can have certain properties that identify them.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/700/1*qvl0oEPDtvBf4OtH1cMwDg.png" /><figcaption>source: <a href="https://rubygarage.s3.amazonaws.com/uploads/article_image/file/1605/graph_data_model_1x.png">https://rubygarage.s3.amazonaws.com/uploads/article_image/file/1605/graph_data_model_1x.png</a></figcaption></figure><p>Note that every relation in a property graph model can only connect two nodes at a time.</p><p><a href="https://neo4j.com/"><strong>Neo4j</strong></a> is a popular choice amongst graph databases that follows the property graph model</p><h4>The Hypergraph Model</h4><p>The Hypergraph model takes it to the next level. Unlike the property graph model where a relationship can only connect two nodes, the Hypergraph model will allow multiple nodes to be connected by the same relationship. Well seems like you can have a third-wheeling node here!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/370/1*5Zl3puD1Bg86VWpMk2FcVQ.png" /><figcaption>source: <a href="https://i.stack.imgur.com/RImaq.png">https://i.stack.imgur.com/RImaq.png</a></figcaption></figure><p><a href="https://grakn.ai/"><strong>Grakn.ai</strong></a> is an example of a graph database that effectively implements the Hypergraph model. (More on that coming up)</p><p>The interesting thing about both these models is that they’re <strong>isomorphic</strong>. That simply means you can convert a Hypergraph to a property graph and vice versa. (Usually, Hypergraphs can be converted to a property graph by adding more nodes and the reverse applies for the property graph to hypergraph conversion).</p><p>All that’s about it!</p><p>In the upcoming articles, we take a closer look at implementing each of these models with the help of simple examples. Stay tuned till then!</p><p>Link to previous blog on graph applications:</p><p><a href="https://towardsdatascience.com/the-graph-epiphany-4050e96ddcf6">The Graph Epiphany</a></p><p>Link to the next set of blogs on graphs:</p><p><a href="https://towardsdatascience.com/a-day-described-in-grakn-part-i-46bb7e3cd82a">A Day described in Grakn</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=656a0005aa21" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/the-graph-models-656a0005aa21">The Graph Models</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[The Graph Epiphany]]></title>
            <link>https://medium.com/data-science/the-graph-epiphany-4050e96ddcf6?source=rss-6cf03c573940------2</link>
            <guid isPermaLink="false">https://medium.com/p/4050e96ddcf6</guid>
            <dc:creator><![CDATA[Vedashree Patil]]></dc:creator>
            <pubDate>Wed, 04 Mar 2020 02:37:42 GMT</pubDate>
            <atom:updated>2020-03-05T05:39:01.958Z</atom:updated>
            <content:encoded><![CDATA[<h4>Graphbits: A Bunch of 5-minute Articles: All About Graphs</h4><p>Maybe I am slowly descending into madness. Or maybe I am already paranoid. But I can’t seem to help it. And that’s why I am going to write this down. Beware though. You might just jump onto this bandwagon with me.</p><p>It started a few days ago. I started reading about graphs and now, it&#39;s all I see everywhere. No, not the serious-looking charts and bar plots. That’s not the graphs I am talking about. Let me tell you what I am talking about</p><p>There was a plaintive looking definition:</p><p>You got two dots ( or “nodes” as they called it). Give them specific names. Join the two nodes and the line is called a relationship (give it a name too if you want). Scale it up with multiple nodes and relationships. And you’ve got a graph! Simple. Plain. Easy.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/392/1*2UCbmPwDWA_F07vSBOZLRg.png" /><figcaption>The picture I was shown for a Graph structure</figcaption></figure><p>Looked like a spider’s web. It was one. The more I read, the more I was lured in and the more entangled I got.and now here’s how my day looks like. Let me tell you about yesterday.</p><p>I woke up feeling rather adventurous and decided to take the train to work. I rushed to the station and took a quick look at the train map sprawled on the wall, searching for the route I had to take. As I stared at the map, all I could see was a graph. Each location morphed into a node for me and the train lines joining any two locations looked like an edge that was assigned a distance.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/843/1*btJiuFuZPi-otA1sl7dVKw.png" /><figcaption>source: <a href="https://previews.123rf.com/images/axsimen/axsimen1812/axsimen181200019/115456759-fictional-subway-map-urban-metro-color-design.jpg">https://previews.123rf.com/images/axsimen/axsimen1812/axsimen181200019/115456759-fictional-subway-map-urban-metro-color-design.jpg</a></figcaption></figure><p>Shaking off those thoughts, I got into the train. Since I had almost an hour to kill, I adopted the most common means of distraction. Checking social media.</p><p>LinkedIn told me that Frank Fakename could be the next potential candidate for a connection request. Apparently the guy worked in the same company as my friend (who was already a connection) and also was in a similar role as mine … Dang! It was a graph!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/559/1*ZVBmSpvLKjvM_TzrwnTkIg.png" /></figure><p>That got me thinking. So it might not be just about LinkedIn but all social media. Because hey! Social media is about people. And people love networking. And well, networks totally look like graphs.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/586/1*ooL6ZkubiKjDO9-yqOd3jg.jpeg" /><figcaption>source: <a href="https://blog.soton.ac.uk/skillted/files/2015/04/social-network-grid.jpg">https://blog.soton.ac.uk/skillted/files/2015/04/social-network-grid.jpg</a></figcaption></figure><p>And that’s what I kept wondering about for the whole train ride.</p><p>I was still preoccupied with these thoughts as I reached work. I mechanically restarted my laptop and opened a web browser session. Following my everyday ritual of reading up on the latest news, I clicked on the link that took me to the news website. My mind wandered and fixated on the “www” part of the site address. www…World Wide Web….Web…web…..Oh, no….graph.</p><p>It then dawned on me that my “social media is a graph” was just puny part of a much larger scheme. The entire web was a graph! Each web page slowly morphed into a node and the links on the page were relations. And the picture that formed in my head looked something like this</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*SdaCOePsCkQRsuZnywPZ5Q.jpeg" /><figcaption>source: <a href="https://searchengineland.com/figz/wp-content/seloads/2015/04/links-graph-web-pages-22-1920-800x450.jpg">https://searchengineland.com/figz/wp-content/seloads/2015/04/links-graph-web-pages-22-1920-800x450.jpg</a></figcaption></figure><p>Enough.! Let’s get to work, I thought. I decided to be a bit more organized and started put together a list of “to do” action items in the “ mind map” representation of sorts. Halfway through the process, I backed up and had a look at my handiwork.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*6enOm6uMiKCZ3-mCZJCwUQ.png" /></figure><p>Hold on.. why was it looking like a graph again? Things were getting out of hand now.</p><p>This kept playing on my mind during lunch as I watched the lady in front of me prepare my salad. She put together all the ingredients that I chose and then added the dressing that I wanted. So maybe it was not just my to-do list. But I could actually show any sort of workflow as a graph with each step represented as a node, connected to the next step. And that proved to be food for my brain.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*DKreGA0EJX0FCQ8rmhI0wQ.png" /><figcaption>source: <a href="https://pbs.twimg.com/media/DkeAmEhUcAAYs5V.jpg:large">https://pbs.twimg.com/media/DkeAmEhUcAAYs5V.jpg:large</a></figcaption></figure><p>By mid-afternoon, my eyes were droopy and the only solution to that was a cup of coffee and a good blog to read. Being a machine learning enthusiast, I decided to read about neural networks. Maybe a new topic would do me good, I thought. Boy was I wrong. The first article I opened had a picture at the very top.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*HwcgsDAZfi_8WliL0sQrWA.png" /><figcaption>source : <a href="https://cdn-images-1.medium.com/max/800/1*FBXS211lj7zWEQZRAmDedQ.png">https://cdn-images-1.medium.com/max/800/1*FBXS211lj7zWEQZRAmDedQ.png</a></figcaption></figure><p>Now you know where I am going with this. And I seriously hope you’re seeing it too. (clue: it looks like a graph). So does that mean the field of deep learning and AI is using algorithms (neural networks) that are just complex graph-like structures? Well, the coffee was not needed anymore.</p><p>Finally, I decided to call it a day. Let’s just go home and “Netflix”. There was this new thriller/crime movie and seemed like a good watch. Everything was fine until this one particular scene appeared. The detective was trying to put together the events that led to the crime and the people involved. He was putting it all up on a pinboard. And….</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*F7IJW7jsZThNEjDewGG71A.jpeg" /><figcaption>source: <a href="https://thumbs.dreamstime.com/z/detective-wall-pins-evidence-crime-investigation-pinned-photos-newspapers-notes-cops-plan-solve-vector-155771857.jpg">https://thumbs.dreamstime.com/z/detective-wall-pins-evidence-crime-investigation-pinned-photos-newspapers-notes-cops-plan-solve-vector-155771857.jpg</a></figcaption></figure><p>I don’t really have to tell you about it anymore now. The picture is right there staring at you. All I will tell you is that I stopped the movie right there, shut my laptop and simply accepted the fact that graphs are an inescapable part of our lives as I slipped into a content slumber…..</p><h3>Ending Notes:</h3><p>Wait up! This was just a fictional narrative through which I hoped to elaborate on the fact that the graph data structure is a perfect fit to model many forms of real-world data. Whether it’s representing business workflows or decision making, they’re a perfect fit. Graphs form the basis for social and interaction networks, transport networks, molecular biology and much more. They’re used to provide product recommendations, to estimate travel times, discover new drugs, etc.</p><p>In the <a href="https://medium.com/@vedaaa29296/the-graph-models-656a0005aa21">following</a> series of blogs, I delve deeper into the topic starting from the basics. I do hope even you have a “graph epiphany” soon and if you already have; Welcome to the club!</p><p>If you’d like to keep on reading, head over to my next blog <a href="https://medium.com/@vedaaa29296/the-graph-models-656a0005aa21">here</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4050e96ddcf6" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/the-graph-epiphany-4050e96ddcf6">The Graph Epiphany</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Understanding FAISS : Part 2]]></title>
            <link>https://medium.com/dotstar/understanding-faiss-part-2-79d90b1e5388?source=rss-6cf03c573940------2</link>
            <guid isPermaLink="false">https://medium.com/p/79d90b1e5388</guid>
            <category><![CDATA[similarity-search]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[faiss]]></category>
            <dc:creator><![CDATA[Vedashree Patil]]></dc:creator>
            <pubDate>Sun, 11 Aug 2019 07:12:10 GMT</pubDate>
            <atom:updated>2019-08-11T07:12:10.551Z</atom:updated>
            <content:encoded><![CDATA[<h4>Compression Techniques and Product Quantization</h4><p>In my <a href="https://towardsdatascience.com/understanding-faiss-619bb6db2d1a">previous post</a>, we explored the FAISS library for similarity searching and took a quick look at its inverted index.</p><p>However, we used the “flat” inverted index for indexing our database vectors. This will work just fine if we have a handful of vectors with low dimensions. But the challenge arises when we are dealing with a millions of vectors having very high dimensions. This is because the “flat” index will store the entire vector in its raw form and FAISS will load the entire index in RAM when querying.</p><p>To handle such complexities, FAISS allows compressing the indexed vectors using a technique called as Product Quantization.</p><p>This post will walk you through the basics of product quantization followed by a quick example code.</p><h3>The General’s Approach</h3><p>General Smart had amassed a large army over time and now had a daunting task of systematically managing and maintaining information of a million soldiers. Smart, as his name suggested, the General soon came up with a solution for this dilemma;</p><p>All the soldiers were organized in a grid formation of 1000 rows, each consisting of 1000 men. Each row of 1000 soldiers was then divided into 10 different regiments with 100 soldiers in each regiment, making a total of 1000 X 10 regiments . All the regiments were then asked to elect 100 lieutenants who could lead and represent a group of regiments. Each regiment was then placed under the leadership of one elect lieutenant who could best represent the regiments interests. So, a row of 1000 soldiers was now reduced to a row of just 10 lieutenants and the General had to maintain information about the 100 lieutenants only.</p><p>But the General knew that not all regiments under a particular lieutenant would identify with their leader in the same way. So, additionally, he kept track of how closely a particular regiment’s interests matched its leaders ideals.</p><p>As the army grew in number, the rows in the formation kept increasing over time. Every new row of 1000 soldiers would undergo the same ritual; it would be divided into 10 new regiments and each regiment would be assigned to a lieutenant who was the best (or closest) fit to lead the regiment. Yet, the General’s task remained the same! All he had to know was which regiment was under which lieutenant! In that sense, his records never exploded in volume because the number of lieutenants remained the same!</p><h3>The Army Analogy</h3><p>So how does Product Quantization work ? Place yourself in the General’s shoes.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/639/1*Ubp1VS74BQMYG3pBvnvVYg.jpeg" /></figure><p>The 1000 X 1000 grid formation of the army can be considered to be 1000 vectors each of dimension size 1000. Dividing each row of 1000 soldiers into regiments corresponds to dividing one vector into 10 parts with each part having a dimension size 100. A clustering algorithm is then used (with k=100) to obtain 100 centroids and each chunk of a large vector is then assigned to the closest cluster centroid akin to assigning a regiment to one of the 100 elected lieutenants depending upon their mutual interests and ideals.</p><p>Hence, a “code book” is created that consists of the details about the cluster centroids where each centroid is called a code.(Remember how the General kept information about the lieutenants only!)</p><p>For all the regiments under one lieutenant, the General always kept track of how closely each regiment and the leader’s interests matched. Likewise, in FAISS, each chunk of a vector is replaced by its offset or distance from its assigned cluster centroid. This method is referred to as <strong>“Encoding Residuals” </strong>that reduces the variation in the data vectors by ensuring that all the data points in a cluster are centered around zero.</p><p>Finally, when a query vector of the same dimension comes in (a new row of soldiers), the vector is divided into sub vectors (regiments) and the “code book” is then used to find the distance of each sub vector with every cluster centroid.</p><p>To do this, a table-like data structure is constructed having 100 rows (one for each centroid) and 10 columns (one for each sub vector) and each entry corresponds to the partial distances between a sub vector and the centroid.</p><p>This table is then used as to lookup the partial distances for each of the data set vectors (Since, each of the database vectors are just a sequence of 10 centroid identifiers) and the distances are simply summed up to yield database vectors having the least distance.</p><h3>Product Quantization in FAISS</h3><p>Let’s look at a very simple implementation for product quantization:</p><pre># IMPORT LIBRARIES<br>import faiss<br>import numpy as np</pre><pre>dimension = 128    # dimensions of each vector                         <br>n = 100    # number of vectors                   <br>np.random.seed(1)             <br>db_vectors = np.random.random((n, dimension)).astype(&#39;float32&#39;)</pre><p>define the index</p><pre>m=8<br>nlist = 5  # number of clusters<br>quantizer = faiss.IndexFlatL2(dimension)  # coarse quantizer<br> <br>#define the inverted index </pre><pre>index = faiss.IndexIVFPQ(quantizer, dimension, nlist, m, 8)</pre><p>train index on the database vectors:</p><pre>index.train(db_vectors)<br>index.add(db_vectors)</pre><p>query the index for obtaining the most similar dataset vectors for given query vectors:</p><pre>nprobe = 2  # find 2 most similar clusters<br>n_query = 10  3 <br>k = 3  # return 3 nearest neighbours,<br>np.random.seed(0)   <br>query_vectors = np.random.random((n_query, dimension)).astype(&#39;float32&#39;)<br>distances, indices = index.search(query_vectors, k)<br>print(distances)<br>print(indices)</pre><p>output:</p><p><strong>Note</strong> : Never confuse vector compression with dimensionality reduction! Vector compression is symbolic while the latter reduces the vector to a lower dimension space</p><h3>Concluding thoughts:</h3><p>Product quantization is a great way to compress your large data set vectors to enable faster search results. However, this also affects the accuracy of the results returned. Hence the trade-off between accuracy and memory constraints(or speed) should be critically analyzed while choosing any index in FAISS.</p><p>That’s All !</p><p>Thanks for reading!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=79d90b1e5388" width="1" height="1" alt=""><hr><p><a href="https://medium.com/dotstar/understanding-faiss-part-2-79d90b1e5388">Understanding FAISS : Part 2</a> was originally published in <a href="https://medium.com/dotstar">dotStar</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Privacy and  Machine Learning]]></title>
            <link>https://medium.com/dotstar/privacy-and-machine-learning-a0effbbdc658?source=rss-6cf03c573940------2</link>
            <guid isPermaLink="false">https://medium.com/p/a0effbbdc658</guid>
            <category><![CDATA[federated-learning]]></category>
            <category><![CDATA[security]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[deep-learning]]></category>
            <category><![CDATA[differential-privacy]]></category>
            <dc:creator><![CDATA[Vedashree Patil]]></dc:creator>
            <pubDate>Fri, 21 Jun 2019 07:52:26 GMT</pubDate>
            <atom:updated>2019-08-27T03:07:49.445Z</atom:updated>
            <content:encoded><![CDATA[<h3>Privacy and Machine Learning</h3><p>In today’s world of technology, it can be undoubtedly presumed that data rules supreme! And with fields like Deep learning having a conspicuous presence in almost every industry, acquiring the right data, (both quality and quantity wise) becomes even more important for organisations. With this comes the paramount task of defining coherent policies related to privacy (Remember GDPR!)</p><p>In this post we will explore certain aspects of privacy in Deep Learning and making use of <strong>PySyft</strong> : A python library for secure deep learning, we will demonstrate a simple code to serve a model for making secure and private predictions.</p><h3>Privacy in Deep Learning</h3><p>A traditional Deep Learning pipeline follows the standard drill: Accumulate data on a server; Train the model on the server ; Make inferences using this model and Repeat. This may, however, set off alarm bells amongst all the data privacy crusaders especially if the data being sent is private or sensitive (like financial information or healthcare records)</p><p>PySyft is one such python library which uses a few principles like Differential Privacy, Federated Learning and Secure Multiparty Private Computation (SMPC) to ensure privacy. Let’s touch upon each briefly using an example</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1016/1*y0s5mUmNVB-Pp0T9RS2ENg.png" /></figure><h3>Federated Learning</h3><p>In analogy, FL is like ordering dinner instead going to the restaurant yourself (what?). So, for example , if Alice refuses to send her data to train Bob’s model on a sitting cloud server citing privacy issues, then a copy of Bob’s model server is sent to her instead! This model trains on Alice’s device and the weights are sent back to the server where the model is updated accordingly. This means that Alice still owns her data and can rest assured that her data has not been disclosed to/by Bob.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xraSBwqekhyvECijUN2JzA.png" /></figure><p>There’s a flaw here though! Even if Alice has sent just the weights to Bob’s server, Bob can easily recreate Alice’s data through reverse engineering (since the weights may reveal details about the data).</p><p>In another situation ,Evil Ed got a copy of the model on Bob’s server under the pretext of training on his own data but instead used this model for his own profits. So, in essence, Bob lost ownership of the model he had so painstakingly built!</p><p>A common approach here, is to encrypt both the data and the model and then train this encrypted model on the encrypted data</p><h3>Differential Privacy</h3><p>Say, if Bob’s model is predicting fraud using financial data, there should be no way of knowing if a particular data sample belongs to Alice. In simple terms, Bob’s model should learn what it needs to learn (to detect fraud throug data) and nothing else (like learning about Alice’s financial characteristics through her data). That means, the model, while training should not learn or disclose user specific features</p><h3>Secure Multiparty Private Computation (SMPC)</h3><p>Let’s say Ed, Ned and Eddie found a treasure map and tore it up into three pieces so that no one could get hold of the entire map at once. The map would make sense only when all the three pieces were put together. Likewise in MPC, multiple parties agree to carry out a computation and the input data and model weights are divided into shares and distributed among the parties. All the shares are required to reconstruct the original data thus making a share a private key of sorts.</p><h3>Serving a secure model using PySyft</h3><p>PySyft currently supports secure serving for Pytorch and Keras or Tensorflow models. Let’s create and securely serve a model using keras API. (PySyft uses TfEncrypted under the hood for tensorflow models)</p><p>Note: I have used the <a href="https://github.com/OpenMined/PySyft/tree/dev/examples/tutorials">mnist tutorial</a> given in the <a href="https://github.com/OpenMined/PySyft">PySyft github</a> repository as a reference.</p><p><strong>Step 1</strong>: Publicly train and save a simple CNN model for image classification on CIFAR10 dataset.</p><pre># import libraries<br>from tensorflow.keras.datasets import cifar10<br>from  tensorflow.keras.models import Sequential<br>from  tensorflow.keras.layers import Conv2D, MaxPooling2D<br>from  tensorflow.keras.layers import Dense, Flatten<br>from  tensorflow.keras.optimizers import SGD</pre><pre>num_classes = 10<br>input_shape = (1, 32, 32, 3)</pre><pre># Define model </pre><pre>model = Sequential()<br>model.add(Conv2D(32, (3, 3), activation=&#39;relu&#39;, kernel_initializer=&#39;he_uniform&#39;, padding=&#39;same&#39;, batch_input_shape=(1,32, 32, 3)))<br>model.add(Conv2D(32, (3, 3), activation=&#39;relu&#39;, kernel_initializer=&#39;he_uniform&#39;, padding=&#39;same&#39;))<br>model.add(MaxPooling2D((2, 2)))<br>model.add(Conv2D(64, (3, 3), activation=&#39;relu&#39;, kernel_initializer=&#39;he_uniform&#39;, padding=&#39;same&#39;))<br>model.add(Conv2D(64, (3, 3), activation=&#39;relu&#39;, kernel_initializer=&#39;he_uniform&#39;, padding=&#39;same&#39;))<br>model.add(MaxPooling2D((2, 2)))<br>model.add(Conv2D(128, (3, 3), activation=&#39;relu&#39;, kernel_initializer=&#39;he_uniform&#39;, padding=&#39;same&#39;))<br>model.add(Conv2D(128, (3, 3), activation=&#39;relu&#39;, kernel_initializer=&#39;he_uniform&#39;, padding=&#39;same&#39;))<br>model.add(MaxPooling2D((2, 2)))<br>model.add(Flatten())<br>model.add(Dense(128, activation=&#39;relu&#39;, kernel_initializer=&#39;he_uniform&#39;))<br>model.add(Dense(num_classes, name=&#39;logit&#39;))</pre><pre># We are assuming the model has already been trained and the weights # are saved in a .h5 file<br># load the pretrained weights</pre><pre>pre_trained_weights = &#39;cifar10.h5&#39;<br>model.load_weights(pre_trained_weights)</pre><p><strong>Step 2:</strong> Import PySyft and use the KerasHook() function.</p><pre>import syft as sy<br>hook = sy.KerasHook(tf.keras)</pre><p>This will make three functions available</p><ul><li><strong>share</strong>: This will allow secure sharing of the model among the workers and also enable predictions on encrypted data</li><li><strong>serve</strong>:this will start a queue that accepts prediction requests (you can put a limit on the number of requests using the num_requests parameter)</li><li><strong>shutdown_workers</strong> : shut down the model after serving requests</li></ul><p><strong>Step 3</strong>: Create three workers (TFEWorker) who will launch Tensorflow servers for performing private predictions. (The <strong>AUTO flag</strong> indicates whether these instances need to be managed manually or by the workers). Since we are using the same machine all the three workers will be on ‘localhost’. This can ofcourse be changed i distributed techniques are being used</p><pre>AUTO = True<br>worker_1 = sy.TFEWorker(host=&#39;localhost:5000&#39;, auto_managed=AUTO)<br>worker_2 = sy.TFEWorker(host=&#39;localhost:5001&#39;, auto_managed=AUTO)<br>worker_3 = sy.TFEWorker(host=&#39;localhost:5002&#39;, auto_managed=AUTO)</pre><p><strong>Step 4:</strong> Now, call the the <strong>share()</strong> which will convert the model into a keras encrypted model followed by the <strong>serve()</strong> method to serve prediction requests</p><pre>model.share(worker_1, worker_2, worker_3)<br>model.serve(num_requests=5) # limit the number of requests to 5 </pre><p>The server is all set to accept requests for making predictions using an encrypted model</p><h3>Make Private Predictions</h3><p>Next, create a client and connect to the model using <strong>connect_to_model()</strong> function. In addition, you need to define the same three workers we created earlier.</p><pre>#import libraries</pre><pre>import numpy as np<br>import tensorflow as tf<br>from tensorflow.keras.datasets import mnist<br>from keras.preprocessing.image import load_img,img_to_array<br>import syft as sy</pre><pre>#create a client</pre><pre>client = sy.TFEWorker()<br>worker_1 = sy.TFEWorker(host=&#39;localhost:5000&#39;)<br>worker_2 = sy.TFEWorker(host=&#39;localhost:5001&#39;)<br>worker_3 = sy.TFEWorker(host=&#39;localhost:5002&#39;)</pre><pre>#connect to the secure model</pre><pre>client.connect_to_model(input_shape, output_shape, worker_1, worker_2, worker_3)</pre><p>Now, you can easily query the model for obtaining predictions securely.</p><pre># prepare the image for prediction<br>def predict(filename):<br>    img = load_img(filename, target_size=(32, 32))<br>    img = img_to_array(img)<br>    img = img.reshape(1, 32, 32, 3)<br>    img = img.astype(&#39;float32&#39;)<br>    img = img / 255.0<br>    return img</pre><pre>filenames=[&#39;horse.jpg&#39;,&#39;bird.jpg&#39;,&#39;car.jpg&#39;]<br>actual_labels = [7,2,1]</pre><pre># Query the model for obtaining private predictions</pre><pre>for i,filename in enumerate(filenames):<br>    img = predict(filename)<br>    res = client.query_model(img)<br>    print(f&quot;predicted class for {filename}:{np.argmax(res)} and actual class : {actual_labels[i]}&quot;)</pre><p>The output obtained is :</p><pre>predicted class for horse.jpg:    7 and actual class : 7<br>predicted class for bird.jpg:    2  and actual class : 2<br>predicted class for car.jpg:    1  and actual class : 1</pre><p>Finally, the server can be shut down by calling the model.shutdown_workers()</p><p>There! our model seems to doing just fine! And moreover, these predictions are done securely. That is, neither did the model know what the actual data was nor did the client know what the model’s weights were. The inferences were made on encrypted data using an encrypted model!</p><p>Thanks for reading</p><h3><strong>References</strong>:</h3><p><a href="https://www.openmined.org/">OpenMined</a></p><p><a href="https://github.com/OpenMined/PySyft">https://github.com/OpenMined/PySyft</a></p><p><a href="https://blog.openmined.org/encrypted-deep-learning-classification-with-pysyft/">https://blog.openmined.org/encrypted-deep-learning-classification-with-pysyft/</a></p><p><a href="https://ai.googleblog.com/2017/04/federated-learning-collaborative.html">https://ai.googleblog.com/2017/04/federated-learning-collaborative.html</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a0effbbdc658" width="1" height="1" alt=""><hr><p><a href="https://medium.com/dotstar/privacy-and-machine-learning-a0effbbdc658">Privacy and  Machine Learning</a> was originally published in <a href="https://medium.com/dotstar">dotStar</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Understanding FAISS]]></title>
            <link>https://medium.com/data-science/understanding-faiss-619bb6db2d1a?source=rss-6cf03c573940------2</link>
            <guid isPermaLink="false">https://medium.com/p/619bb6db2d1a</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[similarity-search]]></category>
            <category><![CDATA[faiss]]></category>
            <dc:creator><![CDATA[Vedashree Patil]]></dc:creator>
            <pubDate>Sun, 19 May 2019 17:41:00 GMT</pubDate>
            <atom:updated>2019-08-14T10:03:33.017Z</atom:updated>
            <content:encoded><![CDATA[<h4><strong>….And the world of Similarity Searching</strong></h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/960/1*eiXyXG9e9xMJZG14nAGQjw.png" /><figcaption>FAISS: Facebook AI Similarity Search</figcaption></figure><p>A few weeks back, I stumbled upon FAISS — Facebook’s library for similarity search for very large datasets. My interest piqued, and a few hours of digging around on the internet led me to a treasure trove of knowledge. In this post, I hope to pen down (or rather type down) few basic concepts associated with the library. And in my <a href="https://medium.com/dotstar/understanding-faiss-part-2-79d90b1e5388">subsequent post</a>, I will dig a little deeper and explore some more advanced concepts.</p><h3>Similarity Searching and Machine Learning</h3><p>Usually in similarity searching, there is often a query record that is compared against a stored database of records (documents or images etc). The main aim is to retrieve a set of database records that are similar to the query record. So, if you have a picture of a dog, a similarity search should give you a list of pictures with dogs (not rainbows!) in them.</p><p>When Machine learning comes into picture, the database corresponds to a collection of vectors. Vectors can be seen as high dimensional representations of the input data generated by machine learning algorithms. Similarity searching in this context means searching for similar vectors for a given query vector based on some similarity or distance measure.</p><p>A naive way for searching based on similarity is to compare the query vector with every other vector in the database. But what if the database has more than a million vectors? Enter FAISS….</p><h3>The story of FAISS and its inverted index</h3><p>FAISS is a C++ library (with python bindings of course!) that assures faster similarity searching when the number of vectors may go up to millions or billions.</p><p>At its very heart lies the index. Mind you, the index is everywhere!(albeit in different forms and names). In this post, I’ll elaborate on one: “the inverted file index ” or “IVF”</p><p>Let me tell you a little story (Bear with me over here, I promise its important…)</p><p>The queen of Someland had just conquered a new territory and discovered that the natives of this land were segregated in three different tribes who simply couldn’t tolerate each other. So, to avoid feuds, she decided to build three separate cities for each of the tribes. Interestingly, each tribe had a distinctive set of skills that they practised. This helped the queen identify which tribe a person belonged to. The Greens, it seemed, were born with a green thumb and spent most of their time tending to plants. The Tinks were the smart, analytical bunch and mostly comprised of architects, builders and scientists. And finally there were the creative Whims, who were known for their proficiency in the fine arts. They were mostly poets, dancers or artists.</p><p>The cities were built and the tribe chiefs were appointed as the representatives for their respective tribes. For administrative purposes, the queen’s ministers maintained a “master-book” that recorded the name of the tribe chief along with names of the citizens for each city.</p><p>One day, a group of travellers arrived in the kingdom and asked for refuge. The queen now had a problem. She had to find suitable volunteers who would agree to accommodate the travellers in their homes. (Apparently there were no inns in the kingdom). She knew that the citizens were quite guarded and only warmed up to people who shared their interests.</p><p>Finally, a solution was found. For each traveller, the chiefs decided which tribe he or she would belong to depending on how closely the traveller’s characteristics matched the tribe’s characteristics. When the travellers arrived in their respective cities, a few citizens came forth and volunteered to accommodate one of the travellers since they felt that the traveller’s characteristics matched theirs. And well…. Problem solved! (The queen could now sleep in peace).</p><p>Viola! I just gave you a bird’s eye view of how the inverted index works.</p><h3>The technical nitty gritty…</h3><p>Let’s use the story above as an analogy.</p><p>All the citizens of the kingdom are the vectors in a database and the three tribes correspond to three separate “clusters” or “cells”. The vectors are then assigned to one of these three clusters depending upon a certain similarity measure .(Remember the tribes practised different set of skills that set them apart from each other?). Usually the L2 distance measure along with a clustering algorithm like K-means is used for this.</p><p>Like the tribe chiefs in our story, each cluster is represented by a cluster centroid or “code” . And just like the ministers’ “master book” , a separate “codebook” is maintained that keeps track of the code (or cluster centroid) and its corresponding vectors for each cluster. This is essentially the “Inverted File” or index.</p><p>A Quantiser is used to decide which cluster the vector belongs to (I guess this was primarily the queen’s job). So when a query vector comes in (like the travellers in our story), a suitable cluster (or clusters) is found for the query vector based on its similarity with the cluster centres (just like the tribe chiefs who selected the travellers based on their characteristics). Finally, a select number of similar vectors within the selected cluster(s) that are returned as the query result (like the citizens of the city who volunteered to house a traveller). This can be seen as a very basic working of the inverted index.</p><h3>And some code….</h3><p>Firstly, install the FAISS library with the python bindings. Just follow the instructions given at : <a href="https://github.com/facebookresearch/faiss/blob/master/INSTALL.md">https://github.com/facebookresearch/faiss/blob/master/INSTALL.md</a></p><p>Then, import the library and other dependencies in python using:</p><pre>import numpy as np </pre><pre>import faiss  # this will import the faiss library</pre><p>Now, let’s create some vectors for the database. FAISS requires the dimensions of the database vectors to be predefined. We create about 200 vectors with dimension size 128. This creates a (200 * 128) vector matrix. Note that all vector values are stored in the float 32 type.</p><pre>dimension = 128    # dimensions of each vector                         </pre><pre>n = 200    # number of vectors                   </pre><pre>np.random.seed(1)             </pre><pre>db_vectors = np.random.random((n, dimension)).astype(&#39;float32&#39;)</pre><p>We use the ‘IndexIVFFlat’ index type for our vectors. The ‘Flat’ here signifies that the vectors are stored as is without any compression or quantisation (more on that later). The IVF index takes two parameters:</p><ul><li>nlist : to specify the number of clusters to be formed</li><li>quantizer : to assign the vectors to a particular cluster. This is usually another index that uses the L2 distance metric (we use the FlatL2 index)</li></ul><pre>nlist = 5  # number of clusters</pre><pre>quantiser = faiss.IndexFlatL2(dimension)  </pre><pre>index = faiss.IndexIVFFlat(quantiser, dimension, nlist,   faiss.METRIC_L2)</pre><p>The index has to be trained initially to create ‘nlist’ number of clusters and then the vectors are added to these clusters. the ‘is_trained’ flag denotes whether the index is trained or not and the ‘ntotal’ attribute shows the total number of vectors added to the index.</p><pre>print(index.is_trained)   # False</pre><pre>index.train(db_vectors)  # train on the database vectors</pre><pre>print(index.ntotal)   # 0</pre><pre>index.add(db_vectors)   # add the vectors and update the index</pre><pre>print(index.is_trained)  # True</pre><pre>print(index.ntotal)   # 200</pre><p>Next, we perform a search on the index for 10 query vectors. The ‘nprobe’ parameter specifies the number of clusters to visit during the search operation. This can be seen as hyper-parameter which can be tuned to get different results. Note that ‘nprobe’ cannot exceed ‘nlist’.</p><p>‘k’ specifies the number of similar vectors to be returned from the visited clusters.</p><pre>nprobe = 2  # find 2 most similar clusters</pre><pre>n_query = 10  </pre><pre>k = 3  # return 3 nearest neighbours</pre><pre>np.random.seed(0)   </pre><pre>query_vectors = np.random.random((n_query, dimension)).astype(&#39;float32&#39;)</pre><pre>distances, indices = index.search(query_vectors, k)</pre><p>The search operation will return the ids (row numbers or index in the vector store) of the k most similar vectors for each query vector along with their respective distances.</p><pre>distances:</pre><pre> [[15.770459 16.773014 17.17131  17.439615 17.443993]</pre><pre> [16.476107 18.52229  18.811913 18.974785 19.02668 ]</pre><pre> [15.520995 16.500256 17.069542 17.483345 17.742079]</pre><pre> [16.842718 17.712341 17.828487 18.699772 19.345257]</pre><pre> [18.325392 18.495464 18.684456 18.70239  18.904179]</pre><pre> [17.531885 18.18179  18.331263 19.429993 19.700233]</pre><pre> [16.840158 17.03664  17.091755 17.34306  17.487806]</pre><pre> [15.984037 16.380917 17.270592 17.620832 17.663855]</pre><pre> [18.018503 18.0761   18.766172 18.956903 18.985767]</pre><pre> [17.113918 17.385284 17.65757  18.122086 18.170212]]</pre><pre>indices:</pre><pre> [[185  35  96  80  75]</pre><pre> [118  51 122 108  31]</pre><pre> [148 149 173  27  84]</pre><pre> [175 177  50  38  81]</pre><pre> [ 44 144 174 105  70]</pre><pre> [156  74 151 167 182]</pre><pre> [ 57 144  18 174  74]</pre><pre> [ 82  12  46  64 127]</pre><pre> [ 52  73  59 138 131]</pre><pre> [ 82  46  90  37 179]]</pre><p>The index can be saved on disk using the write_index() function and can be loaded later using the using the read_index() function</p><pre>faiss.write_index(index,&quot;vector.index&quot;)  # save the index to disk</pre><pre>index = faiss.read_index(&quot;vector.index&quot;)  # load the index</pre><p>There! A rudimentary code to understand faiss indexes!</p><h3>What else does FAISS offer ?</h3><p>FAISS has a handful of features including:</p><ul><li>GPU and multithreaded support for index operations</li><li>Dimensionality reduction: vectors with large dimensions can be reduced to smaller dimensions using PCA</li><li>Quantisation: FAISS emphasises on product quantisation for compressing and storing vectors of large dimensions</li><li>Batch processing i.e searching for multiple queries at a time</li></ul><h3>Where can this be used?</h3><p>Similarity searching and information retrieval are old pals! Image retrieval or document retrieval and even recommender systems use similarity searching. Say, for example, when you are shopping online for a watch of a particular brand, you see all kinds of watches similar in nature in your recommended list.</p><p>Another route to explore is classification. For example, if we take the cliched ‘cats and dogs’ image recognition example, we can actually predict if the given query image is of a cat or a dog, depending on the most similar images returned from a datastore of cat and dog images(hmm….definitely another post for this!)</p><h3>Final Thoughts</h3><p>I feel like I have barely scraped the surface! FAISS is an interesting library and theres definitely a lot more to explore. Squeezing everything in one post might make you scroll for ages! Hence, my <a href="https://medium.com/dotstar/understanding-faiss-part-2-79d90b1e5388">next pos</a>t further dives into the library and explains an advanced concept called product quantisation.</p><h3>References:</h3><p><a href="https://github.com/facebookresearch/faiss/wiki">facebookresearch/faiss</a></p><p>Thanks for reading!!!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=619bb6db2d1a" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/understanding-faiss-619bb6db2d1a">Understanding FAISS</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>