scale.bythebay.io: Vlad Patryshev, Functional Linear Algebra in Scala
Recording: scale.bythebay.io: Vlad Patryshev, Functional Linear Algebra in Scala
you so my name is Vlad and I'll share my experience with an attempt of doing linear algebra the right way so as an example I took this book probably some of you are familiar it's called Gone with the Wind so in this movie like 80 year old movie we see two main characters Scarlett O Hara and and Rhett Butler they meet here the first time so what I did actually after playing for some time with machine learning I figured that well that how machine learning code looks like that Fortran that's how it look in 1980 in 1970 maybe in nineteen okay 56 and that would people do now except that they call this code through like several jumps from their Java or Scala so I decided let's do it better so let's like get into the paradise we have to have everything in mutable strong types have maps not loops have filter not loops and have reduced not loops so that's like a good idea so that's what my like I do that's what the paradise I was trying to get into so more if you are dealing with linear spaces right you have a category you have a category of linear spaces every space is an object in that category and arrows in that category morphisms are linear transformations that are also called matrices they're slightly different but it doesn't matter now do we have a monoid in a category when the furnitures know it there's no monitor well I mean like in my talk so I applied the method known as brought to vêoc which consists of these operations read the text like gone with the wind like I'm going to have lots of money and when I do I'll never be hungry or cold again that's a famous phrase right we split the whole novel into words and kick out stop words so that after normalization we'll have money never hungry called again kind of preserve the meaning of it but it's not about Dominion I'm not getting into like the mean I'm trying to do linear algebra so the the algorithm next represents each word as a point on a unit sphere of code like multi-dimensional unit sphere maybe a hundred dimensional maybe 10 dimensional not two-dimensional but for the for the purpose of just demonstration I put them here like the world hungry damn read well these words like also are also famous in the in the novel but they don't encounter in this phrase right so we put them randomly so that's step one randomly throw all these words it's about 16,000 words in the novel and then do something about them name namely if the word if are close like hungry and never they're close so they a little bit like nudge together if they're not they could be like matched away but that's a variant of the algorithm actually in this case I don't do that so we have this word art imagine we have that stuff like hungry gets closer to never to call to money to again and Manya again never called are also getting closer to hungry why because in this Engram money never hungry called again these words are closed and if the two words are encountered like many times close so they getting closer of course if you have just two dimensional space they will be all in one dot but in multi dimension like hundred dimension they will move around randomly so we won't have that trivial solution now we are supposed to be like functional scallop programmers so how do we represent vectors I didn't lead something like this so nudging consists of taking like one vector well taking another vector and we move the move in that direction and coefficient with which like the rate with which we are moving and we return this vector with like some movement in that direction well the thing is that what do we keep inside we keep an array inside so Scala array Java it doesn't matter you have to check the dimensions and you do this loop right so that's okay this is how you do it but I was confused by dealing with those like dimension check-ins right so is it Python is it Java is it Fortran all the time when you add vectors you have to check like odd do we add the right stuff to the right stuff well otherwise we can like add two-dimensional vectors to three-dimensional the idea that they're like subtypes one is a subset a subtype of other this is the wrong idea because we are in a category different types so in real life in math these types are different and in this category we have to keep in mind that there are totally different things but not in Scala because not an array is just an array we don't have we don't have dependent types it not AG - okay we cannot have like a type of an array of length m but what we have is path dependent types so with one more trick we can make a vector not just like an individual container of an array but a vector in a linear space and that linear space is an instance in which vector is a type so that's how it is linear space vector space is kind of a synonym in this specific context in my talk so we define a case class vector space with a certain dimensionality so I can dimensional space and a hello oh you are right so we check that dimension is positive so not dealing with negative dimensions or fractional or irrational and we have this straight vector okay it's like it's an index sequence with pressure hold function meaning that given an index it returns the value right but the length of that vector is the specified dimension and you cannot mix vectors from different spaces because they belong to different instances so in reality I have two implementations of that vector of the trait one isn't function so given a function just this is the vector but it's in this space so we can only take this this specific like components 0 to n minus 1 or on an array so we have an array somewhere inside right and we take a value of that array like this if we are immutable so that's all you need right apply and you implement things like nagy and whatever having this apply method so we have an air we have vectors and we are safe we are good and now the dimensions cannot be mixed like this in an example that won't compile we have a vector from three dimensional space r3 and another vector from r3 and a vector from r2 we can like safely multiply vectors by by a scholar we can add vectors from the same space like the 3G but we cannot add vector of a two dimensional vector to three dimensional or three dimensional two dimensional so I feel happy and really when I switch to this I found a bunch of bugs in my code when I did mix vector from different spaces like ten dimension 100 dimensions it like people make mistakes but now my compiler won't allow it to me so what happens next if it store our vectors in that cloud I mean like first on the surface and then they're being matched together we'll have this kind of cloud so to reduce dimensionality and to be able to see what we have we do this thing called PCA principle honor we begin with the cloud but then when we do this some vectors like get closer some not so we have maybe not so many dimensional cloud and it will look something like this except that we have like hundred dimensions so what do we do with this we want to this cloud turn this galaxy the right way so that's what PCA principle component analysis does that's again a linear algebra trick that rotates our our galaxy and presents it in the right way how does it do it we need again vectors and eigen values eigen values are the sizes of our cloud in the biggest like in all the different dimensions where they're like specifically big like the biggest eigenvector is where our cloud is the longest then the second is where our clouded the widest then the next one is where our cloud is the tallest I believe like three is enough for human being right so that what we do the trick is to find these eigenvectors to find how big those eigenvalues but well that doesn't matter we have to find three eigen vectors or maybe two and rotate our cloud to rotate the cloud we need to do linear transformation but before that we need to find eigen vectors so PCA does it by multiplying matrices and eventually we do that but see yeah yeah yes it is I'll get there yeah well with vectors like they don't have so many vectors but later with matrices it will be really hard so I'll get there so but we need matrices now how do we represent matrices where kind of like you already have vector spaces what's a matrix a matrix is an arrow a morphism from n-dimensional space to M dimensional space so a matrix is declared as this so we have a domain that's where to which matrix is applied and we have a co domain and it extends what just a function from like a pair of indices to a double value so that's how it is we have this index like I and G and it's point to a value inside that matrix and it we also like the quirks of Scour so we pass the types but we also have to pass instances domain and codomain so inside the matrix you can multiply a matrix by a certain vector from domain but not generally speaking not from codomain unless they have the same dimensionality so that's how it is like we have a matrix a matrix has a method x vector meaning like multiply vector by matrix with matrix on the like matrix on the left so the vector is from the main the result would be a vector in codomain so we go from one linear space to another and how do we calculate the data well basically the same thing just add the components right so it like no magic here and I transform it to array and push it into the vector because vector one kind of a vector is when it's an instantiated from from an array it not necessarily because if you can have a function you can pass a function and nothing is instantiated so no big deal you can compose functions and basically keep keep just one reference but this way I have to know because I fall so I have to store the vector transpose in a matrix he is like it's very trivial because this is just a function that you pass we really don't even instantiate anything we take a general matrix which is like the main codomain and produce a matrix that has Kodama in domain and what we have it's a matrix on a function that's it zero memory taken well because we do just transpose so in real life when we do something bigger with matrices well we just take some space but if we do that and we flatten the whole picture all those words from that sphere Country dimensional sphere we can flatten and we have this two dimensional representation and let me show you here we have red Butler that guided to come Scarlett was married here Scarlett what's wrong Scarlett like love mother money except red is surrounded by Butler is his last name dead eyes world man Yankees and so on child by the way child is not close to Scarlett she I would say probably it means in the novel that she didn't care much but read did well he actually did so that's how it is in the they're not so close so they're not like very close as press analogous so you see just by analyzing by just like rotating matrices and analyzing so what you see in the picture so from this book if we extract this like chunk of knowledge so that's good if you have like pretty nice like well-formed cloud but what if the cloud is not that well formed what if we have like two flat clouds one on top of each other so they'll be flattened like this the work that are actually not that close they can be flattened projected and we wouldn't like that projection so to check that case I like created an example which is like this so this is a shape that I rotate it in 3d so it's a 3d shape and see in one of the projection this butterfly is just a cross and if you take this coordinate and instead of just rotating like take these coordinates and try to find eigenvectors and eigenvalues they will be you have the you'll find that the projection would be judged that cross so that's no good because see how far away are those like edges sides of the of those wings right so something should be done so that something is a nonlinear method is called salmon dimension reduction so basically that's what it does like we have this flat projection and it pulls apart the things on the on the wings that are close so that's what it does like we have what we do for every pair of points we know whether they're close in the original space or not even in the projection we have this original matrix of distances right so what we need to do we need to make sure that our representation our projection is kind of close to that representation in the original space except that here we had like three dimensional and we flatten it to two dimensional but even like in real life you'll have hundred dimensional and we have to produce two dimensional so what does it mean like hundred dimensional space and with all the points how many points like sixteen thousand points so we need to have a matrix sixteen thousand by sixteen thousand two hundred fifty six million so that like a gig right or 1/2 gig something like that well why half gig because we calculate only the distance whether the space original was hundred dimensional million dimensional doesn't matter all we have it just points and distances with them and what we need is to pull these points away to pull meaning that we have to have this gradient descent towards having better representation of our original distance matrix so that's what we do this is like what my program produces well because I'm not good with graphics so this is just alphanumeric output so some an algorithm I'll show you how some some an algorithm does does it like this first you have this like abstract cloud first you do PCA 50 steps meaning like 50 rotations of the matrices to find something like close to again vector and then 300 summon steps and from this from this projection we have that well it's not a projection anymore it's a representation it's mapping because it's definitely not linear but the thing is will have huge matrices like 1/2 gig or gig each and imagine you do it like in a functional way meaning like copyright so well copy is not good so again like this is the description what saman algorithm does so we build distance matrix we run PCA in the beginning so that we find like more or less good dimensions and take the first two or three they mentioned and then in this 70 like 16k dimensional space meaning the number of points right so we optimize it using gradient descent minimize addition between original vectors like the distance between the matrix of original vectors and current distance matrix in just two G so we try to approximate the original matrix as much as possible by moving we're moving points on our to G so the challenge was like well why is it 128 well because the matrix is distance matrix is symmetrical right so there's no need to keep like the lower triangle still like almost two gigs so we don't want to do like copy and paste so I sighed and you say that okay let it be mutable so nudging like nudging and addition will have this like plus equals and we keep the very vectors over there even for those small vectors that we have just six and thousand so it's not like quarter eighth of a million of a billion so we do this okay the trick with those algorithms is that all of them are parallelizable even with mutability salmon can be well because we're doing those Nigel's like Nige here Nige there they're totally unrelated so they're getting together so basically I run it on all the course I have even with this mutability just like a trace or like like a okay chase of algorithms even salmon okay so they like all those points are moved around like separately so that's cool the other thing is with performance of addition right so we're in Scala Scala is on top of Java so what happens like we take an i Java array like doing something in Java range every check the index returns a Java double a primitive type a primitive value that double is box into object double and it's given to Scala code another double is also returns from array and box into a double in the code when we do addition like both unboxed added boxed again and stored so I was wasting like tons of whatever time on these funny operations yeah you can ask me like can you do specialized yeah I can it just helps a little bit so excited decided the K let me create this like layer of Java below our like type safe code layer of Java that doesn't check anything I mean it does check but it doesn't check that the vectors are over the same size because they are called from a good code that knows all those dimensions right so nudge is written in Java like class volume to does all those false for any operation so all this like Scala product of two vectors is done here so that's how it is but I hide it so it's not supposed to be visible to use it because like if you are a user if designing an algorithm and do this like raw cold you can be confused easily I was so instead it's just hidden it's like another layer and on top it's a good good Scala so that's how magic works from Scala so if we are on air I mean that there is like a Java array inside so we call this array ops magic on the other hand if it's not an array meaning it just a function so something that multiplied by whatever like by X color so the same vector with no like is no value there so we do this separation and like multiplication and whatever and addition and this - like what's addition it's several times faster well of course if we tell it to Java people they would not care about that we could they'd like innocent they don't care much about text we do so it works it's it's fast but it's under the thick layer of good type safe code so what did we do it I tried to do la functionally yeah and I do a like functionally but on a certain level there are like layers below so the example was worth Tuvok and I applied PC a dimension dimension dimensionality reduction and summon dimensionality reduction but to be like Rio so have to keep stuff mutable and do do all this operation through Java and also when I started it I was just like a free whatever flying floating a guy that had time to do that now I'm in sales at Salesforce so here at the talk that our guys are given now so it's clean right now so I'm doing like machine learning and all this stuff at Salesforce now this was totally unrelated so any questions yeah to hear humility I stopped a job we could we could but calling natives is kind of just not something I am comfortable with but yes yes it that on one hand on the other hand if he ever saw natives Carla been compiled skala been compiled into like LLVM into native code in Runyon and well she well she let me fit let me finish she Scallon native compiler produces like a pretty efficient code these days right but I saw a competition like in Scala in our Scala meetup a while ago so one the same piece of code running in a native scale in Scala compiled to native so it's pretty efficient in the beginning and the same code running on JVM in the beginning it's like slow like starting but then it beats everything why does it beat everything because JIT does reoptimize the code so that a human probably cannot write this kind of code well some people say that yeah we are super humans and we can beat well I don't know that guy also like produce the pretty efficient code but so currently I kind of rather believe that JVM like eventually during this react amis react amazed ation may produce something that the human cannot produce so that's why I stopped here and I didn't go there but maybe well the other thing is like why not use a graphic it should be you right that would definitely be much faster but well I'll play with it maybe yeah any other questions are you saying skull is just not efficient for matrix operations you didn't try sparse matrix operations did did you try the sparks code as first we'll see in this case these are not sparse matrices like everything's fields all this like big distance matrix it's all smut sparse in this like PCA the rotation matrices right there are not sparse so that nothing to do with sparse matrices of course if they're totally a very sparse like you know they're mostly zeros and like values here and there yeah that could make sense but again it's it would be pretty dull well I did have it I was comparing like this code with with my code but with different version like Java version and like specialized version in Scala so basically specialized version is twice lower than this channel layer plain as Cal without like specialized it's like about eight times floor I didn't compare it to anything else basically well because like this PCA algorithm I wrote it myself it's not I don't need all I can vectors I need just two or three so why would I bother to use those algorithms it or rather not right thank you [Applause]