Data as the Killer App for Functional Programming

SBTB 2014, Vitaly Gordon: Data as the Killer App for Functional Programming

Recording: SBTB 2014, Vitaly Gordon: Data as the Killer App for Functional Programming

hi everyone my name is battalion and my data scientist at at LinkedIn you might have no us as the company that you know let's your neighbors and family endorse you for stuff they know nothing about and i'll be talking today about what's close you know it kind of i tried to pick a generic name enough that just a data analysis and kind of the applications functional programming towards it kind of before i started just a small kind of raise of hands how many of you are data scientists data analysis data whatever but people kind of work with data well that's actually much more than expected okay that's great so kind of a one thing about me unlike i guess many of the previous speakers i'm not a scholar guy i'm not sure i'm even a data guy but still going to share my thoughts with you about the subject and kind of the driver behind this presentation is some frustration i had with some of my colleagues and more of a junior members that you know are doing some analysis and whatsoever you know and they're using okay I'll maybe use the terms even though I hate them big data or small data but just because they're short not because I actually think we should use them and they're doing it and they're doing it by you know Excel or sequel or whatever and then they realize okay well there is so much you can do with you know Excel or sequel and then they say okay well I need to probably code something in order to get to the next level of analysis and you know they asked me what should I use and say hey why won't you use Scala and they say oh my god no it's a functional language and I said well what do you think excel and sequel are and I said yeah no I think I'll use Java because it's you know so easy or whatever and I guess I come to meetings like this to be among peers so this is not a talk that is about a song functional programming because hopefully I'm preaching to the choir everyone here I guess understand and I realizes what are the benefits of functional programming and you do understand you know it's probably why is better than the other alternatives but i will still speak about a specific subject which is for me data analysis or as we can see here this is the name of the talk and just for this talk and you know without kind of a debating it for too much time so for this specific talk when I talk about data I talk basically about random facts whether it's some sort of logs or some Internet of Things thing or whatever but basically it's a set of facts and here by me using the word fact it wasn't accidentally chosen we can pretty much all agree that facts are a most cases immutable and in most the system that we data scientists use they actually are also stored in kind of immutable storage system one example might be Hadoop and that when i say analysis I mostly mean math and when I say math I really don't mean this complicated machine learning statistical modeling blah blah blah I really mean what most data people do ninety-nine percent of their time and it's just counting filtering aggregating and utter other things we do this you know I would love that most of my day will be you know at one giant Kaggle computations where I can the data set is prepared for me and all I can do is you know try different models and see you know plot nice graphs about how the models are able to predict but again honestly most of my day is writing code that just process gets data in one form and a kind of transform it into another form and this transformation is kind of pure mathematical transformation kind of as the way we know it and the last thing is functional programming so this is kind of something I took from Wikipedia which is a program paradigm that avoids state mutable data in side effects and here is where I can I am find it a little bit funny about special when I talk to my math colleagues is trying to understand trying to understand that put a program paradigm that avoids state immutable data is kind of a you know you are under the assumption that will vary state mutable data in side effects but if he talked with any mathematician there the concept of side effects is totally strange for them I don't know how many of you ever you know did any math class were suddenly you know solve an equation and that equation had side effects so when and again it's kind of hard to understand it's like I said I found pretty funny where in wikipedia defines functional programming is something that avoids something else where why do we even assume that the something else is the basis that we should be compared against so this is kind of my talk about this functional data analysis or is it what it really is is just basic math and I kid you not it will get very basic here are five apples and here if let's say you know our brains are kind of you know neurologically wired the fact that we act the way we know that our five apples there we don't actually count them one by one we just see the picture and worry cognize the pattern we see five days and things and we're don't you have to sum them up or like my my two-year-old daughter she actually even though she can see the respite things because she cannot remember all the numbers all the time then she actually goes and counts but this war for her to remember what the sequence of the integers are and not actually because she needs help with recognizing there's five elements there but if we're talking to a computer now any computer you know any data structure you will store it in no matter what it is we'll probably in order to get the sum will you will have to kind of somewhat sequentially go through it and count and all the apples however there are different ways of doing this evening the same result and here's another way still again nothing mind-blowing so far it's just we can actually try and separate and you know assume there we have free people that you know count these five apples and we tell them well you count this part I'll key on this bar in the third person will count that part and we actually can separate our work among these people and the question is interestingly so why is that possible why can we actually when we are kind of doing the task of counting apples why can we just easily separate it into a you know into the several people counting and then we and somehow agry their partial results anyone can care to take a guess yes exactly because counting is associative so this is a why we can do it in case someone again doesn't remember basic math and what associate means it means that we can basically and here i use the kind of the curly braces as parentheses but it doesn't really matter where you put the parentheses the and kind of what will be the order of the execution of discount we will always get the same exact answer there will always be five apples there unless we have very bad counters which can also be okay but the question is how does it help us and when I mean us as me as a data scientists this associative property and we kind of mention it briefly what's so easy and when some of the operations or transformations or aggregations I need to do have this wonderful associative property is we can easily paralyze them and when we and yeah forgive me for using the b-word when we're dealing with big data or should I say just very very large amounts of data that you know cannot be stored on a single machine it's actually very important that we can do some operations in a parallel way so how's it all relates to this functional programming it's a one thing I forgot to mention is I'm also besides my job of antenna also contribute the aim to project that rsr by Twitter one of them is scouting which is this scala dsl for running MapReduce jobs don't of cascading which is a java one and also but scalding very much depends on another one which is kind of less known but also reading Scala a cold algebra which is an in Twitter everyone every project has to have some bird in it so algebra diz que sea right it's an algebra library a built by Twitter and back to the parallelism part is okay so we said we have this wonderful associative property we can paralyze things so how can we can generalize it besides just counting and you know one of the most basic thing and you know Here I just have to commit myself I actually did not use the word mono it so if anyone is actually playing the mono drinking game it's not a mono it it's a semigroup and the reason why it's a semigroup because for our specific purposes at least and how the scowling is implemented we only am we don't actually need a zero element and here we go into like another kind of funny definition that I think most like functional programmers but I guess math people will get it another way the best way way to explain a semigroup to a functional programmer is to say it's a mono it without the zero element because apparently that is and I've tried different explanation but yes so the and I think this is the one that yeah people can understand the best so it's the kind of simple simplest trade that we can think of it defines one function it's a plus it has two elements in unfortunately there is no good way at least in Scala to define it in code but in order for a semigroup to be in real semigroup the operation has to be associative just in case again the word associative is far and distant memory for some of you some operations are not associative an example of one can be median so the medians of media other medians is not necessarily the median of the original group in case i guess that is still not a great example we can think about it and kind of realize so this semi group in our case is the very basic integer semigroup that defines plus as well surprise surprise as the very basic plus operation that we know from you know basically elementary math but yeah in order to make it kind of interesting let's not stop this one hopefully we can get to a better stuff than explaining after I guess 15 minutes of talking that we can in you know after a PhD in computer science we know how to sum two integers let's try another one so another example is finally large here in my example I used to but it's finding large K elements in a data set and this is again an operation that is fairly fairly a common in you know in data analysis so here are kind of six elements and one way that people approach this problem okay so how do we find the largest two elements is let's sort all of our elements tracery forward and let's take the top two and here we have the top two elements the pro is that this method is not very scalable especially when we're talking about again large amounts of data it gets pretty hard to sort all of them especially aim when we consider it least at some of the systems and I think still the kind of common big data processing tool even though we had a spark talk before and spark is kind of amazing but if we take Hadoop for example the way that Hadoop soirée the wake added to soar things in Hadoop if you want a consistent sore it is to get it all into one machine and then sword it becomes a big big mess and just not a very scalable way but the funny thing is what would happen if I ask you the same question but instead of finding the largest two elements i would ask you to find the largest one element and here's the cognitive dissonance for me and it's also kind of funny observation is no one here would suggest that i should sort all the elements first is that correct but suddenly when it becomes two elements then yes a lot of people of course not not none of you guys but a lot of other people suggest that we should sort all our ailments first to get a second so why is that and I guess because we're very much train and I guess that goes for our kind of imperative programming background that you know the way to find one element is to set some element to be this whatever minimum integer or whatever language we use and traverse every element and the sign and you know we find this one largest element but when it's two then it's gonna get a little bit more complicated how can we do in this kind of single a pass how we can find a large two elements well we can say okay then we can say instead of using just and kind of one variable we can use two variables but again of course if we're talking about k then it's not the best so in case we can say let's use in here again so let's use a list and algae just say get back to it but Lisa's not the way by settlement em and I'll just show how to be specifically it simple in Scala but there is again no there is no kind of huge math behind it but we another thing that we would like to do is also to be able and that we cannot do if we do the sword we want to do it on separate machines very similar to how we done before so we kind of break it and as you can alway guess guess it's take a kind of a log not a number of steps instead of taking the actual you know going through the sequences so how does that work so there are two things here that we need to realize one is again i use the curly braces but to represent the things we're doing on let's say a single machine and if it were talking it kind of Hadoop then let's say it's at the map map stage Madhu but we want in a single pass get our largest two elements and one of the ways to do it is to use a priority queue and you just initialize a priority queue of size K and then you pat reverse through the elements with your priority hue and get the largest and two elements we can do the same thing on the other machine and get the largest illness and then we can merge it is so in algebra there is a trade that's called aggregator that is exactly to kind of do as such a kind of transformation so the aggregator trade has free steps so the first step is called prepared the second is reduced and the third one is present prepare is basically we have data and let's say you know in one form and we want to transform it into a another form a different one it's any as you can see we want to transform it to something that we reduce a plie the reduce function will be applied on so the reduce function also you can kind of guess from the name and if you're somewhat even slightly familiar with the MapReduce paradigm the prepare is we'll probably a kind of map side operation that reduces ok send all the things that have the same key to the same reducer and form and reduce operations or this operation on on it and present is take the final in just in case we want it in some different form we can transform it yet again it's another kind of map stage it's not really in our maps ages just it's happens in the reducer after it's done but what's nice about this you can see that the reduce operation is some has a very familiar signature and that signature is exactly the same signature the plus operation had of the same group and there is actually a I think in most when you will write a code you will find that him most of the operations when we actually want to use this a aggregator pattern the we will use it using a monoid and the MA the reduced operation will be basically calling the plot so usually how it goes using the prepare we map our data into some form of that mono it that we want to use the reduced operation will just be the plus operation of that mono it then represent us whatever however we want our input back ok so let's just look at the example of how and how this say might be yes and another well let's first look at it ok so there is it just something called a prayer eq aggregator it's also part algebra and this is the implementation of if in scalding and sorry for not elaborating a lot about scalding but in scalding whence a kind of there is a solid take method which is basically take the top K element according to some ordering and what it does underneath is basically calling this a priority queue and aggregator and of course it has slightly more code than that but on a very very basic level and I had a kind of hide a lot of code here but the preparer is take whatever your input is create a priority queue that accepts that type added to the priority queue as just a single element and return the cube back so after applying this on all of our data or the circles kind of I showed before instead of each line being let's say the circle each line will be a prairie queue of size one that has the circle but of size one and sorry but they also i forgot the prayer req also needs to take in a maximum number of elements but this is in the code that kind of i just decided to look at out of here but you if you go to algebra then just look at the Prairie q aggregator code you will see it but again the Prairie cube will have just a single element in it so the reduce operation that is just the plus operation and there is also a kind of in in algebra the nice implicit which again I don't know if it's a bad word in this kind of conference but there is an implicit that whenever you use the plus side it actually goes and checks whether there is a semigroup define on the types that you kind of you just define sorry you're using the plaza Parisian on and if there is a semigroup defined and intact we will use the semi-group operation of that specific type so this is actually a how the code is written and you can see that on this L plus R so the question is how this plus operation works so we can just look at our a fine example here if you if you look at it let's see if it works yes so so we have a we need to somehow combine now to priority queues one it has these two elements and one has these two elements so one way is just to okay define a new priority queue of size 2 that is what we're interesting and to basically add all the four elements into that single prayer eq and that is what we will have at the end another thing is you know there is just a slow aight optimization but it's not extremely important that we start with the larger larger q if they're some a sometimes they're not the same size after some operation but we start with the larger one and then we add all the elements from the smaller one and again at the end we have the exact right answer so back to the code and so the reduce operation is that's just the plus the plot that is the fine on the Prairie cues that I just define and the present is basically I don't want my results as a cue I want the massive list so I can and usually what people do is actually flat in that list so so I can have all my elements kind of in an I sequential way another kind of a very neat thing to notice about this kind of trick is if you yeah if you don't know what I'm about to think and you never use a different one alive then just ignore what I'm about to say but if you use the if you ever use Hadoop then may Hadoop also has this optimization everyone is talking about let's say all my you know as much as you can use combiners so combiners is this reduced stage that happens that happens in the mappers themselves instead of the reducers so in there you know their infamous a word count examples instead of you know going for our code and in meeting the word dog and sending it to the reducer every time we see it we can actually count how much how many times we saw the word the dog on a single on a single mapper and then send send it just once with the count hopefully I'm also if you just know what I talked about the thing with combiners understand is that we cannot always use combiners because in order for the combiners to function properly as well the operation has to be associative because if the operation is not associated we cannot actually use the combiners again median a it could be an example but guess what we are working in a functional language and we are using a functional programming and we actually define reduced to be a mono it so hence it's a a great thing that well again as long as we followed a constraint that reduces actually is a associative operation it means that scalding will always use combiners by default and hence if you just benchmark it versus a trap other applications that do not have this concept a again like pig or a just had remorse even a Java one like crunch work skating they don't they have no way to know from the code that this operation is actually a mono it and since they have no way no there you have to explicitly each time say hey you know what I want to use combiners in scholarly that's not necessarily that's not necessary so it actually gains a very nice productivity gain in terms of how many things we can do am but I should kind of speed up so mono is mono is we all heard the word but at least four R's dance on it's not about just counting summing in min max there is a very very basic metal and mono it but are some mono is that are actually are fairly sophisticated and here are just a few examples on the left side you can see that this kind of moms are actually fairly simple but on the right side so I mentioned priority queues a moment's again no answer there's the four and the four or five moments is which is like this every standard deviation and the skewness kurtosis and I think I forgot one but sorry yeah count is one it's actually all of them are associative / accuse i mentioned bloom filters if you don't know it's like the same statistical statistical filtering think where you can say whether an element exists in a set or not when you or where you only have one type of error but you don't have on the other hand but bloom filters if you go to their underlines kind of a bit arrays that also are associated we can actually take to bloom filters and combine so if now we can we want to create a bloom filter out of our entire data set we can actually create many many bloom filters of size one for each each of our element in our data set and then just combine them using em using the plus it's not trivial but it's also not very very complicated so it's actually not complicated all about how you I combine blue filters and have a correct result mean hash and hyper log logs is again the sore variant that also a bloom filter checks of an element is an asset hyper log log also answers how many unique elements we have in our data set also a completely associative operation and count mean sketch also tell us so how many times every element is in a set also in kind of statistical with a very we can with a very small amount of bits we can get a very pretty accurate results and stochastic gradient descent but anyway all these are mono it's and I as a data scientist it tremendously enjoy the fact that this operations are associated because then I can do all of it in in a parallel manner and I I don't need to worry about getting the wrong result or the operation taking a lot of time so here's an army mano it's mono is everywhere which I guess some can sum up the entire conference not just my talk but our just mano it's omana this is awesome and again not mono is actually a semigroup and it has a plus but as we all were in an elementary math there in more operations than just a plus so here is another example and i'll go pre facile it so we have a matrices and matrix multiplication a k dot product again this is a reminder for people who just don't remember and it's completely okay not to remember it the way we multiply two matrices is we take every row element and we multiply it by every so every element of the row and multiply by every element of the corresponding column and then we sum all them up one way to think about the same matrix operation we can define another trait and I will give you a spoiler in case well you know your category fury probably most of you know it better in mind that is also known as a ring but for our demands demonstrative purposes is rink is basically like a group which group is a mono it with the negation wrinkles as multiplication on it but for the sake of matrix we actually care about two operations we have an element wise operation and we have the final reduction that's just how we are call it so element wise is x 1 x 72 x 9 3 x 11 and the final reduction is just aggregate all these partial products so again it's very simple and in the matrix proud if we can define a matrix and we can define a matrix product to be anything you like as long as you know and we can just give it a ring and the ring defines the ring of just a linear algebra defines the element-wise operation as multiplication and the final reduction as summation and there is a wonderful matrix API in scalding that if a lot of time we actually it's very convenient for us to hold our data as a matrix and if we want to kind of multiply these matrices we just this is the very simple ring with that we can provide to the matrix and that will work however that is not the interesting part is ok it's fairly clear what we can do the with the kind of trivial integer ring or any numerical ring can we think about something else so another case in in data analysis where we use matrices a lot is in graph analysis and this is a you can see on the left is another way to represent a graph as this adjacency matrix and then the number one is let's say we have edges of basically of size one they're all have the same length and we can define a different ring for our matrix operation what if we define the element-wise operation could be a plus and the final reduction to be a minimum as you can see there is a huge spoiler there on the name of the object that what we what we will get so again we have this matrix and you can really see when we take the matrix and multiply it by itself we take all the elements and we say okay what we want to do is to sum up the the row in the column so if we have now basically a central node that it takes one step to reach it and it takes one step to reach from that node our target node then it will take us now to so we will perform a summation on all the possible ways to reach a certain to reach a certain node in the graph and when we do the phone and when our final reduction step is the minimum then we'll take the minimum out of all the ways that we have to reach that specific node and we'll get the surest path actually in a graph and you can check my results so after a singular iteration of multiplying the matrix by itself we will actually get a new matrix that looks like that the point of this example is not to say okay this is how you should implement shortest path algorithm in a graph using matrices and like this rings but just to show that by changing two very simple functions and by saying okay and matrix we can always think about a matrix as this thing that holds somewhere numbers in it but what if our our matrix was a matrix of something else would it work well the answer is it would work if we only define the the plus and the product operation and that matrix and if we define it we can define it in in different ways in one of the ways is even though the in the matrix was still in the integer but you can think of a matrix of some random objects that you also have this operation define on them it's actually will produce interesting results and the only abstraction kind of math takes care of everything as long as you give it the basic building block of ok how do what do i do when i take two elements of the matrix okay you do what i call here the element-wise operation so that is hopefully i know if it completely convince you but functional programming or in my version of functional programming is not you no promises futures it's more very very basic math it's just whatever we you we think about integers we can do the same about things that are not necessarily integers and it is the correct way to find a kind of the correct way to think about data analysis problems and kind of speaking from now experience when we actually tried it and we introduce new members to skull and this framework that Albert we actually gained a huge gain productivity and just the quality of code people produce so does have its benefits and I suggest everyone to try it thank