data.bythebay.io: Malcolm Greaves, Functional Programming for Machine Learning and Data Pipelines
morning everybody think with a lovely introduction I'm Malcolm and I work at nitro and today I'm going to talk to you guys about something I'm passionate about which is functional marrying the ideas of functional programming with ideas of machine learning so first I'd like to I was like to start off with giving a really clear sort of indication of what I want to be talking about today what I want to communicate and I have a strongly held belief that I want to communicate today and that is using functional programming makes it easier to correctly implement machine learning algorithms everyone to emphasize this this correctly implement idea because with its it's very easy to write programs that are fast and gets you the wrong answer the call to send exit and it's very hard to implement difficult algorithms and a lot of machine learning algorithms are mathematically complicated they have a lot of subtleties and you can spend lots of time trying to implement an oven to be incredibly efficient especially if it's a machine learning and let's say it's a back prop I've algorithm for training a deep like a convolutional neural network you can spend a lot of time making it a deficient and it's incredibly hard to make sure that it's absolutely correct and gets the right answer a lot of times especially if you're moving fast it's really important to make sure what you have is a program that works and i believe i have is that functional programming makes it easier to make it correct then say using another paradigm like imperative programming so who am i some computer science of sheen living practitioner as was introduced earlier i got my bachelor's and master's of science in computer science at Carnegie Mellon University it did research there was an undergrad and grad student currently now research engineer nitro where they pay me the youth Scala and work on natural language processing machine learning problems as well as a dash of computer vision pretty great I get paid to do it and I'm a big functional programming addict I haven't gone to FP anonymous yet but they tell me it's okay and I really like being outside a little bit about me kind of a gym rat I sort of like like I'm not a gym mouse that was too big to qualify for that title it's a little bit about me so as an outline just to give you guys sort of a an idea of where I'm going here today I'm going to talk so a little bit more of a motivation around why should you care about correctly implementing a sort of primer just to get up to speed with some ideas and functional programming as well as the machine learning some useful for machine learning ideas in functional programming a couple of classic machine learning problems as well as so often code that actually influence these ideas so first some acronyms if in case it wasn't are just clear CS is computer science machine learning is ml NLP is natural language processing CVS computer vision and FP is functional programming I mean also for anybody asks about slides yes they will be on the interwebs actually I finalized and I posted them on my Twitter already so you can actually access them it also be on the data by the base site and if you follow me I'm out malkriss my twitter handle is already a link up there where you can download a PDF version of them so moving on to why should you care about correctly implementing so here's an assertion correctness is the most important aspect of any program now my intuition for this assertion is that if the program produces the wrong value it has no purpose for example so let's go over some ideas to ideas here what's most important in code does it speed this most important aspect sometimes it's make or break if you have a real time application for example and you don't do let's say a stock trade within 50 milliseconds or you don't buy that make that purchase order to add in 50 milliseconds it's over you don't have the ability to make it at 51 milliseconds done so there are some cases where speed you can get the correct answer but if it's too late it doesn't matter at all but we don't always have a strict deadline most of times in applications we have to write it's okay for a couple milliseconds late or maybe it's okay for even half as secondly and this is this little joke ahead before right is there any program that's faster than startup and exit right but do you ever really want something that's this fast right if somebody just had make the fastest program the world you should say great i can do that one line the program ends the very first thing it does and that would be you know fast program that you could ply to anything that would always get you the wrong answer so intuitively it would be complete useless and so there's this point right that being fastening correct is still being incorrect and so speed is something that's always important in the applications context if you have a responsive user interface for humans speed is an important factor if you have microsoft micro second stock transactions speed is a very important factor or if you handling lots of requests then you have to make sure your high throughput you don't spend too much time in each request but in general speed is important for a particular application context and fast programs are preferred to slow ones but I assert that speed is not king so another idea is readability maintainability these are talked about a lot any kind of software application everybody knows you know you shouldn't have unreadable code you should try to write codes that as if the next person reading it or maintaining it knows where you live and it's also you know a murdering psychopath you know all the usual mantra on that and you know a big reason to that is because a lot of times programs are written not for machines understand for people to understand so if people if a person cannot understand the program's behavior then it's automatically less valuable than a program that could be understood as you can't gain insight and understanding there's a great example if there's this generalized linear models package and are used a lot very fast great code for making different kinds of linear models actually once looked at the Fortran source code because I had a problem with it and it's about five five six thousand lines of Fortran I don't read Fortran it's really hard to understand and I gave up after about half a day be like well clearly not going to solve this problem we got to find a workaround but that's an example of like I thought I could get some information from this great library turned out not to be the case because the code was completely unmaintained a bowl and as the code was unreadable understandable I was less usable there's no way from united tix tend that code or just in general the idea of extending code you don't understand is very difficult and fixes of course or a nightmare i mean probably everybody in this room has either been there or if not we'll be in the situation where you have to go fix something you don't understand that's very fun but you know the reality is though we all notice that there's lots of software in the rural world that really nobody understands and it still works and it still can be useful that you know that glm net package and our is still incredibly useful people use it a lot people don't really understand how it works on the internal level there's only maybe a handful of people the world that do that do but it doesn't mean it's not totally useless so readability and maintainability is and very important as a general rule but it doesn't make or break a program so this is again going back all the way there's a search and I have that correctness is king so hopefully I've convinced everybody is why it's important to care about correctly implementing and so now I want to talk about some just some functional programming ideas and machine learning idea is to make sure everybody has a nice background as we go along so in a nutshell here's how I characterize functional programming everything in funchal program is an expression every every expression evaluates to a particular value so there's no delineation beauty of statement that has some side effect and something that has that value there's always every statement always is an expression that you can evaluate to something and this is slightly controversial point but I really feel strongly that functional program is highly guided by having at least practical functional programming is guided by having a strong type system so that doesn't necessarily mean statically compiled so like python is a great example of a language with a strong type system that's dynamically evaluated you can't do an operation of Python between two types that don't make sense it'll stop you from valuing that at runtime contrast to a language like java script which is weakly typed and also dynamically evaluated if you're trying to add you know everything that that there's a great video with like called like wet but Java scripts like a duck in it yet somebody's nodding in the front he knows it's hilarious it's great the guy shows the presenter in that video shows you can add an empty object to an array in JavaScript and you get something that's not a number and that's technically correct right and you can flip it around you don't get something totally different so that's an example of you're adding stuff that the type stone makes sense and you shouldn't be able to do that operation but JavaScript's our language that's weakly typed so just attempt to try to interpret that but not every programming language there's some like untyped lambda calculus that's not typed but it's still functional programming but that's something people could disagree with me on buttocks think that's my strong typing point I'm sticking to it another important aspect of functional programming is that this is actually this is not controversial that our functions are values so there's no difference in how you use say an integer versus a function that goes from one integer to another integer they have different applications but you can still reason with them in the same abstract sense that you would a single value because in function program they are essentially a value so you can pass it around you can reason with in like any other variable this is other concept called referential transparency which really what it means that if something evaluate sex it's equivalent to X so if you have a definition of something that's more complicated and it evaluates to five that's the same thing as a variable with the value five right how you computed them as different but essentially they are the exact same thing there's just different ways to get there so this is important because if you ever have a function definition and an input and you evaluate it to an output that's always going to be the exact same output and a purely functional programming sense there's no difference between a function applied to an input and the resulting output so and I just wanted to get this out there if anybody in the audience is wondering you know what do I mean program with functions I mean something sort of more like this so in an example in Scala if you want to make a function at 12 its input not very interesting but simple you would simply declare a function add 1 it has it goes from into int and then you'd use it you apply 10 to the function and you get the value 11 if you're doing the same thing with Python you would make a variable called add one you'd make an anonymous function in the same sense that adds one to its input and then you can apply 10 do it and get 11 as well what I mean don't do this better use make function just use them directly instead of sort of a more object-oriented approach where I'm going to use Java as an example where you could make you know you make a singleton a class it has a method at one it takes that number and add ones it returns it and you when you want to use it you have to make a new instance of that object and then call the method on it as well and I argued right this is you could you can make the argument well this objects method is a function in Scala kind of does it behind scenes of how it implements it but really from a kind of language use case perspective and how you use a language these are slightly different concepts and slightly different writing this in the object-oriented sense you're making objects within calling methods on them in the function case there's really no distinction just have functions you can apply them so it's a lot simpler machinery a lot easier to reason with in your own head so moving on to just sort of machine learning in a nutshell some of the ideas I just want to get out there before start talking more in depth is that everything a machine that he needs data so then the effectiveness of any machine that a algorithm is completely directly dependent on your data quality there's a lot of it that happens with your album you're using but if you have garbage data in you're going to get garbage data out no matter what so the reason why that everything in machine that needs data is that everything is pretty interesting in machine learning uses statistics and if you have any machine learning algorithm any ingest state at the output that algorithm is always a model and these models view the world through features and the features are things like this attributes or properties or if you look at you know like a matrix respective instances might be rose and then columns might be features so it's kind of like a database record right where columns of features and this is just sort of a very kind of broad 30,000 foot view of just machine learning and machine learning has one really big aspect of our class of machine learning algorithms are called supervised learning algorithms and I kind of like to kind of coin this term as the AI of machine learning why because it's really supervised learning really has the most interesting applications of machine learning for example driving a car translating from one language to another language recognizing objects and pictures searching for images in text you know all these really interesting things that we like to think of as intelligent or smart behaving programs really I think the day will you supervised machine learning and in the supervisor machine learning sense the objective is that first you assume that there's some function that exists in the universe that goes from your input to your output so if it's driving a car it might go from the input here's a picture of the road to the output is what angle should you turn the steering wheel how much do you apply the gas how much you'd apply the brake and you assume that that function exists and you say well we know the function must exist because I can drive a car and you can drive a car and so you know we all sort of have a sense of how we can drive a vehicle and you know there must be some you know Universal function that tells us how to compute this and so now given that we assume that that function exists what we're trying to do is with a list of input and output pairs find a function that approximates this special function f the one true function for driving right or the one true function that you assume exists for your specific task at hand and this by the way this is just sort of a theoretical academic setup it's important in sort of your line of rigorous thinking it's not something you say okay where's this function but it's just how to set up the problem in your head so you could think about it there's other types of supervised learning in the probably broader sense that people know there's classification so you have an input and your output is one element from a discrete category so it might be binary classification where the categories are too yes no might be a multi-class classification it might be like a tag on an image you know is this a picture of a room is this a picture of a house is picture of a cat it'll be classification the example I've here right everybody probably uses Gmail or at least its knows what it's all about knows about the priority in boxes and that's a great example of classification when you get an email message how should you categorize it should be spammed should be priority messages should it be family and what's nice about classification is that lets you have a model that's able to make a decision which is very useful another type of supervised learning I'm not going to talk a lot about in this talk but I want to point out is that there's thing called regression so you guys probably heard of linear aggression similar set up with the ideas that you're not predicting a discrete category you're predicting a continuous value so if you have an apartment listing could you predict what the estimated rental prices that's not you know 10 20 30 that's a real value number that could go anywhere technically an infinite number of possibilities so classic alguns linear regression right but another type of supervised learning is called structure prediction so this is similar to classification except the output is significantly more complex so for example if you had a sentence and you say given the sentence what's the syntactic dependency parse was basically the the tree structure describing the grammatical relations between every single word in the sentence to every other word there's a lot of different kinds of structures there to predict so because it's a tree there's lots of different trees it's significantly harder than just trying to predict you know what sort of label the outcome is and it's very very interesting not going to talk about a lot here I just want to kind of give everybody a primer on that there's nothing a big kind of machine learning called unsupervised learning so when on supervised learning its pattern recognition through and through out it's not doing anything like supervised learning it's not you don't have a training set of labels and unlabeled stuff and the output is not a model the output is a set of patterns that are expressed in the data so for example if you're doing something like k-means clustering the output of that unsupervised learning algorithm isn't here's a model to do classification it's here are the Centers of 20 clusters I found or 10 clusters or how many clusters you asked me to find by themselves the output of unsupervised learning doesn't do classification regression or structure prediction as a human being it's your responsibility to interpret those patterns output and then figure out a way to make them useful for your problem so if it doesn't give you a nice thing to use at the end today why would you ever use on supervised learning well that you know reality of the world that the overwhelming majority of data is not labeled you don't have nice pairs of input and output you just have the input so in this sense if you don't have pairs of input and output you can't do supervised learning full stop so that's where the supervised learning would be helpful additionally unsupervised learning is helpful for trying to understand the data so if you're just a human being maybe it's your first approach of the data sets your first day on a new job you just want to get a sense of the data digging this i'm applying some unsupervised learning out as well might be useful for you to get intuition of what's actually there it's also very useful for search a lot of problems searching problems can be sort of formed it as an unsupervised learning problem and I just think the last kind of point is once you find these patterns if you as a human do some additional manual work on top of this often times you can engineer an okay solution possibly good but some sort of solution for some source of classification problems for example if you had a program that output clusters and you could figure out how to get one of those your inputs to match up to a cluster you might then look at those clashes as a human and manually assign semantics to them you might say well this cluster I'm I'm declaring this cluster represents a certain category so that's an example you can kind of sort of bootstrap a classification problem on top of an unsupervised problem but it requires human input at some stage in order to go from unsupervised as supervised so now moving on here I'm going to track a little more quickly because I think you guys are interested in seeing some code or some useful for machine learning ideas on functional programming so first is just this concept of just using the type system so a large part of practical functional programming is to use types of guide the program's logic so it eliminates lots but not every single logical error so for example the biggest part of using having a statically evaluated type system or a strong type system is that you can't make a program that applies a function for example to go from one type to another type B to value of type z that just doesn't work that doesn't make any sense that's like trying to add an integer to a string it makes no sense what does it mean to add 5 to the word in practice if you come from a Java world this means you don't have to have any more as instance of or casting in order to circumvent the compiler and say no no trust me this type is actually this type or in Python all right this is my little jab at the Python community they're nice people though is that you know a lot of time in Python code you'll see you'll get an input in the very first thing it does it checks the type of the input and it says you know if it's this tight run this thing if it's this type run this thing if it's not any of those types and throw an exception that's basically trying to do static like bolting on static type evaluation into a dynamic language and so the big part of why would use a type system why would you have a statically type system is it lets you eliminate a whole class of bugs from a program namely type errors you won't run a pro you won't run a program that has a type error in it if you statically valuate them I mean that's very nice especially if you're developing fast you can you know save a lot of times wasting time kind of doing some more kind of boilerplate e type checking stuff so probably a lot of people here use scala to show hands real quick yeah see you guys all know the hello world of ska funk collections right we got some data you can map over it you can filter over it you can flat map and each time you do this right it evaluates a whole new value that sequence so scala crowd in here so you guys know a lot of these ideas probably about using kind of higher kinda types so for example if you have some that could evaluate nothing then you want to use this type an option to encompass that idea that this might not be whatever you want if something's going to take some time you don't know if it's going to come back immediately we'd use a future to indicate that that whole concept if something is going to fail you might use the built-in scholar try type or we might use the scholars the disjunction type which is very similar if anybody's not familiar scholars you did the disjunction type that little character I agree the little V is a little weird but essentially you can always say this you have try of tea it's exactly equivalent more or less to a disjunction of a throwable as the air condition and a tea as the correct no air condition and these are example of higher kinda types so higher kind of type is a type that has a hole in it so it's an incomplete type you once you fill in the hole with another type you get a whole complete type so example an option is a higher kind of type because without that specific inner type it's not complete yet so and I like to look at how are kind of types is have a value some value T within a context and you'd indicate this as K of T so moving on to this other idea called type classes just kind of quick want to make sure just a brief intro here so start with a tale of two types x and y all you know that x is able to do actions a B and C Y is able to do actions a B and C and your poses the question are x and y the same type if you use subtyping you have to add ask the questions well are they subtypes of one another are the children of the same parent type and are you trying to see if they're the same by looking at the same parent type the type classes the the way you answer this question are they the same as you say is there evidence that says x behaves is why or vice versa and so type classes the ideas that you you put a constraint on a certain type you say with me as the type class I can show you how any instance of type T adheres to this interface and why would this idea be useful for machine learning a lot of times you want to do stuff with numerical vectors you don't really care if it's a dense vector of doubles or if it's a sparse vector vintage errs you just sort of want to be able to encode the idea hey I've got something that can do vector operations let me do vector operations on them or arithmetic operations I don't really care it's a double or an integer I just want to know if I can add them divide them or subtract them from one another or fir kind of other algebra ideas for example from the breeze library spire library you want to just know hey I have something that you can combine together okay that's great now i know i can do reduce on them and also idea for data right a lot of time Scala collections you know it's very nice the higher-order functions map flatmap filter and such are very useful and you just want to be able say I don't really care what kind of piece of data this is I just want to know if I can map over it and there's this idea that I kind of sort of came across like the coin in my head is this type class or date of all sizes and so this is a great kind of I'm talking about right when we have data we sort of just care about these higher-order functions to transform the data so we can operate on it we don't really care if it's a scala sequence or if it's a wrapped sequence around array or if it's reversible or integrated like really just care if we can do these things on them or if it's a spark rdd we don't really care we just want to be able to describe our algorithm in terms operations so in the same sense as before instead of saying I don't really care about the type is I just want to know that I can do these operations on this type we want to be able to say all I want to know is that I can do a map flatmap filter on some type D and so there's this this thing I created called the data type class as a quick short definition is actually not the whole of it but this is exactly what you would what it would look like for map and reduce you would say you would define something saying okay well I have this trait data the specific type of the collection is d has a hole in it so you know it's not totally complete and you're saying okay well I can map over it if you give me an instance of it of type a a function from A to B and i'll tell you how to turn it into a collection of type be similar to things for reduce if you give me an example of it for type b and a function and combine two values i'll tell you how to combine them and just a quick note here this little type class sanitation comes from the CELAC room project which is really great it's a macro that allows you to get access to sort of make this syntax a little nicer so instead of having to say you know map of the collection essentially allows you to say the collection dot map which is a more sort of functional are more approachable object-oriented syntax and you can get access to that for example in this case by saying import data ops underscore because the macro makes an object that has some implicit sin it under this thing called ops and if you import that you'll be able to get this syntax just a nice thing if you guys are using this on your own so here's an example of kind of injured implementing them for two different things here's for implementing this really this simple data type class for a sequence it's pretty boilerplate e you know you just sort of kind of plug and chug similar thing for an RTD if you have an RDD of type a and if function may to be simply call map on it and these look almost the exact same of plantation wise and that's kind of the point is that these are examples of two kinds of totally different collections that have the same almost the same behavior so our implementations for them are basically the same but it allows us something we'll see later that we won't have to really worry about trying to say okay well I got to re-implement my whole them for a spark I DD I just did it for a scholar collection like why do I have to do this it doesn't really make a lot of sense but that is sort of the the big way of using these these type class ideas so just an example of using a type class idea in scholars type class and scholar let's say we're going to use the data type class let's say we're going to make a function to sum over some collection of doubles so it will be simple right you can take a reduce first and just add every single number together and you'll get the wholesome out and this is great because this you could use it on if you go online you can see there's implementation for rtd there's implementations for different scala collections you could use this code right now and you know have a generic summing function for doubles you know but wife stop there wouldn't be nice if you could have just a generic summing function for anything that's it that's a number of type so there's a built-in type class and scholar called numeric and you could say well now I have a data collection of numbers I don't know what kind of number they are but there's some specific number type and now I could do the same thing and say well take out reduce and I have two values how do i how do I reduce them together well I would get the evidence saying that n is a numeric type and that numeric type has a function called plus and that adds to two instances of end together to get another instance of end where they're summed so in this case right now we have a whole algorithm that is very generic it can operate on any kind of data collection as long as you ever do some math and any kind of number type and you can add them so it work for an RDD of int or a sequence of doubles and this is kind of the level of abstraction we want we don't really especially want to try to implement machine learning algorithms correctly we really don't want to have to be dealing with we want it as much as we can not deal with the low level concepts such as what's the specific number type what's the specific collection type we sort of want to make sure Aldens correct and then sort of his used as many tools as we can to help us extend that and apply that correct algorithm to different problems in a quick note on numeric so numeric is this type classes Scala has plus x minus there's another one called fractional so the same thing but it also has a divide operation so if you if you were specifically working with and floats and you want to be able to divide be a little bit better to use fractional so as a quick thing here this type glasha director operations essentially is there's another one i use in some of the code here and the big idea is that I just you want to be able to say I've got two numerical vectors and I want to be able to add them together and multiply them and do the dot product so in the code if you see a thing called math vector ops that's a type class for supporting the source of operations or anything that behaves like a numerical vector alrighty so I've got ten minutes left as I've been informed so I want to talk about some of these classic machine learning problems term or older school problems not deep learning but I think they're really great for illustrating these points I'm talk about three problems two of the mountain supervise the searching and clustering and the classification is a supervised problem so the suite of learning problems clustering classification and search and we're going to do clustering with k-means i'm going to show that algorithm with in some code for it searching with nearest neighbors as well as classification with k-nearest neighbors then a sharp little blurb about vectors because I've been kind of talking about them without really giving them Elias slide in their own so if you hear me interchange the word vector for input or an item what I mean is by vector I mean a numerical vector from linear algebra I don't mean like a scholar vector collection where it's like an array or a nap n double array I mean something that you know has lives in a vector space can you can do dot products on matrices that kind of sort of jazz and in machine learning basically you can think of every single algorithm as input always takes a feature vector and by feature vector I mean it's a special kind of numerical vector it has there's always a sort of context of a map around which says you give me a feature I'll tell you how to go to a numerical index from 0 to n minus 1 for n features so that if you give me a vector we can use integer index so you can go in this vector integer or index 500 or 525 right what's the feature for that okay I can go to my map and find that again and I can also then find the feature value for that that's just sort of the general approach for every single machine learning algorithm so if you ever in a talk and somebody talks about talking about items and inputs and switches to vectors don't worry you can think of them as the same thing at least conceptually so now I want to talk about some of the this question with k-means problem here so k-means is an unsupervised algorithm its input is just a list of vectors no labels and a number of desired clusters to be discovered and the output is the K vectors each one is a center for one of these clusters and the immediate question is great kula clusters what can I use this for so you can use clustering with k-means as the canonical waves you can once you find these clusters you can then assign any old vector to a cluster you can also do something soft k-means where you say well this vector isn't necessarily a sign to a cluster it has membership a partial membership between clusters and why would you want to do this right well the utility is if you as a human being observe what these clusters are look at the examples close to the clusters then you can and you go and you find the original inputs for these clothes vectors you can then manually understand what these clusters are representing if you put some thought into it and you could impose meaning on these clusters by looking at the representative items and saying this cluster means this so you might have for example let's say you're doing document categorization you should have a bunch of documents determine two vectors you cluster them and you look at the you know for each cluster the ten closest documents for that are assigned to the cluster and you look at them and say well these these documents look they're kind of about legal stuff so I'm going to just say this is now my cluster representing legal stuff and these documents over here in this cluster look like they're kind of more about tech company recruiting posters right our tech company recruiting emails or something so that's what i mean by sort of imposing meaning on these representative items so switching over to nearest neighbors search so nearest neighbors is also in supervised its input is also just a list of vectors its output is a program that has ability to list items that are similar to another one so if you have it so it's a general purpose search algorithm there's no training of learning pretty easy to paralyse implement and it's easy to experiment with different features different distance measures and you could use it to answer the question fivesome x what other ones are similar what are the you know five closest or five most similar thanks to this input because your documents dating profiles literally anything you can be turned into a future vector you can use nearest neighbor search on this is sort of an adaption to Kenya to nearest neighbor search called k-nearest neighbors for classification it's really similar the idea is to make it work wealth label data and now we're to get something that you can use at the other day for doing classification which is a supervised problem so let's input is a list of items with labels and your output is a classifier the grocery item to label we can you classify us for so therefore decision-making primarily smart so-called smart programs specifically k-nearest neighbors wired you use this and something else its main is it really just any training time so it's great for if you just accumulate data you can just really look a big corpus of data you can paralyze our classification parts same logic as four nearest neighbors searching and its keys it's really easy to implement and it's easy to test on completely new problems so it's not something you might want to use in production it's something you might want to use right at the beginning of sort of an exploration okay so now i have five minutes left for code which is great so busy slides are online so i'm just going to go through all these links here or just show them so there's some links with the type class the data type of class i was talking about that type class for math vector operations an album for k-means clustering 14 nearest neighbor search 14 k nearest neighbors and also linked this this classic old school 20 newsgroups data set so first one cake clean means clustering how does this algorithm work SI algún is you first you initialize the center's randomly just choose waits for the you just randomly initialize the vectors using a Gaussian weights or uniformly and random and you say while these centers are not converged for each vector in your data set you assign that vector to the clusters nearest and then after you've done the assignments Yuri complete the cluster centers by averaging to all the vectors that are assigned to it so you move those centers to where they're now the average of the things assigned to it and you repeat and converge here means that the you usually define this is saying well they've converged if that the center's haven't moved by more than a small margin between iterations so they start slowing down and moving from one center from one iteration to another one once that sort of slowed down then you say that's converged and that's a parameter you can kind of play with and nearest neighbor search the algorithm is for each new item converted to a vector and then when you're given a new item you convert to vector as well you calculate distance between that item and all the other vectors and then you sort that you can think of it as you show at the resulting list they take the shortest distance at the top and then you return the closest k k is a small number like 5 10 20 100 vectors and you return those vectors for the new item and that you're let your end of the day output k-nearest neighbors is really similar each item and Row 2 vector given a new item promoter vector calculus and searchable in this blah blah blah but then the difference is once you get those K vectors they also have little labels assigned to them so then you say ok out of those closest K vectors what's the most frequent label that appears that's the majority label return that as the label you're going to classify the item as so right everything up to the very last point is the same thing as nearest neighbors and only the new part is that the sort of logic to deal with the labels so with my last two minutes here i'm going to frantically try to show you something sort of cool so I do have IntelliJ window open which is yeah nobody can see this anymore I don't it down but so this is oops okay so this is a little program i have i wrote sort of quickly what it's really doing is it's sort of reading this B strain newsgroups data file you can think of each file is it belongs to a certain news group like computer politics or science or different are different kinds of groups and their message board so it's sort of you know old school for message boards people posting back and forth and the this first promo just loads data up and I then want to do is I say okay after a load up all the data I'm going to get make a new canaan classifier and i say it's going to work on the thing is going to classify as a document we're saying a document is just a string the labels are string the number types of float and the vector type is a sparse vector and a little thing to turn this turns strings documents into sparse vectors and i set up the train and test things right here than i do is a great i'm going to go build mackanin model on this data i'm gonna take the top 25 and I'm gonna go classify and see how this this rolls so we're going to go and run this life because that's always fun especially the demo on stage so okay so it's really simple I have the data already like loaded on a computer so it's going through all the news group stuff getting all those documents and each one's train them into vectors I then it's going to go split over to just ones that the pain and classify uses and then a separate two thousand documents that it's going to use testing from and it's not taking random documents trying to predict so this first one for example are predicted that the category the broader categories from science it actually was been a Salinas category it got that wrong so it's got a terrible twelve percent accuracy so kan right it's not always the greatest the most accurate algorithm but it's easy to implement and it's easy to kind of get working and it's very very very extendable it's very adjustable there's a lot of things I could do to make this better I just wanted to kind of show you guys with this stuff work a little more time I'd love to show you some of the code if you want to talk with me afterwards I could everything's also online and the slides are up and you can link to go through the links on there I'm out of time it was thank you for being a wonderful audience