SF Scala, David Hall, ScalaNLP Epic

Recording: SF Scala, David Hall, ScalaNLP Epic

thanks hi everyone I'm David Hall I'm a PhD student at UC Berkley I work in natural language processing uh today I want to talk about um give you an introduction to natural language processing in schola um focusing on um the scholet NLP ecosystem so this is a set of Li that we've developed um uh starting from a l linear algebra Library Breeze um to a natural language processing epic to an extremely fast uh natural language parser called Puck um so Breeze um alfare linear algebra scientific Computing um and numerical optimization uh while epic is natural language processing and also structured prediction um and Puck offers um an incredibly fast parser for English that parses um over 4 sentences a second um at state-ofthe-art accuracy um if for those of you who are familiar with the python ecosystem um Breeze is kind of like uh numpy and scipi epic is kind of like um very Loosely p struct and nltk combined um and there's nothing like Puck okay so um I'm going to start with epic um just talked about it for a while and also try to dig down into not just how you would use the library but also how you can uh adapt the library in a way that can uh improve the uh libraries for your data um since often in natural language processing uh pre-built Al pre-built data models won't work particularly well for other domains okay so generally natural language processing uh particularly monolingual uh natural language processing we're interested in annotating uh senten or documents so it's a little bit small so I imagine a lot of you can't read it um so you have a sentence like some fruit Visionary say the Fuji could someday tumble the Red Delicious from the top of America's Apple Heap um this is from the 1980s when the Wall Street Journal was terrified that the Japanese would take over America and um they were scared that the uh Japanese were going to import this apple and take over America um anyway so they decided to uh denigrate it based on its looks um it certainly won't get there on looks um okay so natural language processing um one of the things we might want to do is identify all the noun phrases um but and more generally we might want to analyze the entire syntactic structure um another thing we might be interested in is what's called co- reference resolution um so if we see it certainly won't get there on looks um to you and I it's called co- reference resolution uh where we identifi that the Fuji apple uh is the uh anaphor of uh it an okay reference of it okay another thing you might be interested in is canonicalization or entity linking so you might want to know that the Fuji is an apple and not say Mount Fuji um or Fuji film um yeah okay so epic right now supports um a subset of this it supports the syntactic parsing part of it and it also supports um another task called named entity recognition which is recognizing um people plac and things so as an example uh if you have a tweet like uh shap penise Berkeley California a bowl of Churchill BR Orchard page mandarins and mle dates um we want to extract the people the places and the things um as well as sort of the other stuff uh like movies and books things like that um so Adam Goldberg is a person uh sha penice and Churchill ber orchards are um organizations uh Berkeley is of course a place um and there aren't any uh other things in there okay so epic um has a pre-built NE named in recognition model for um English um and it's pretty easy to use um first you just import uh the Neer selector tool which is in principle designed to let you select between multiple different languages um so for instance uh you can load the English model uh with just the simple line um you can then take some text and you have to tokenize it into a representation that we understand so if you have something like almost 20 years ago bill Waton walked away from Calvin and hubs um this would present some uh it would convert this input string into a canonical representation that's easy to process it would separate out all the punctuation from each other uh uh understand what are opening quotes and closed quotes and things like that um we then asked the Neer model for what's the best possible um sequence of Neer types and uh we get an output that looks like this so almost 20 years ago uh a person Bill Waton walked away from a location Calvin and Hobs um so obviously Calvin and Hobs is not a location um but you can understand why it might have made that error but still let's try to figure out why uh how we can maybe fix it one way you can fix it is by getting a bunch of uh data so since this was uh you can imagine this was from a tweet and so you might want to get even more tweets um you might annotate uh the people the places and the things and all your tweets you would get that Jane Austin told St Moses are people and Calvin and Hobs is a MK um once you get a bunch of data you can then ask uh uh epic to uh build a simple uh semic CRF and I'll talk about that a little bit later um and out comes a new system and uh you can then rerun the analysis and then maybe get out the right answer um if you don't want to annotate a bunch of data maybe because you don't have the budget for it or um you just don't feel like it um you could instead use what's called A gazeteer and A gazeteer is um a list of entities uh that's pre-built from some database Wikipedia is a great source of gazers people spend a lot of time listing every possible thing in existence um so one of the articles is a list of newspaper comic strips from a to f um um and sure enough Calvin and Hobs is sitting right there um and so you can imagine building some kind of regx extraction of this it's a very regular structure um and once you've done that you can pass the gazeteer um to the sem CRF model and again get out the right answer um there are some dangers if you use gazers um so the biggest one is that if you build it from the if you build your gazeteer from the training data um then the system will decide that the gazeteer is really good and everything else is a little bit noisy and so it'll only use the gazeteer to make predictions um and what this means is that if you end up with um new examples that are not from your training data you've seen an entity you've never seen before it'll say well it's not in the gazeteer so um we're not going to uh guess it um nevertheless if you're careful about how you use them they can be very useful U make sure you extract them from other data sources again Wikipedia is a great source okay um so let's talk about uh semic crfs just a little bit um it stands for semi Markov conditional random field don't worry too much about the name uh it's kind of technical but the basic idea is that if you have a um a string of text you want to break it up into a bunch of segments um some of the segments have uh meetings that we talked about like people places and things but some of them are just other or uh outside is how they're usually called um um and the way this ccrf works is it wants to pick the best sequence that maximizes the score of each of the individual segments of the sequence so we we'll have the score of shap penise plus Berkeley plus AOL of plus and so on and so forth okay the way we determine this uh score is what what's called a feature function um and the way a feature function works is we um typically is a sum of a bunch of weight so for instance for shape pise we might say uh well shap pise starts with sha that's a good indicator that it's an organization things that start with sha tend to be things um uh it starts with the capital uppercase C so um that's a good indicator that it's some kind of named entity um it ends with an uppercase P also important um it begins the sentence again beginning the sentence is a indicator that uh typically uh entities will come at the beginning of the sentence rather than later on um and then uh you might include something like the shape so this would say it's two capitalized words um something like that and then maybe even just that it's two words long um people places and things tend to be relatively short uh if you had a string that was 20 words long and you thought that was a person you're probably wrong um so okay and then finally of course we can have a feature that just is fires whenever it's in the gazit here okay so epic the way we represent this is with a domain specific language or DSL um so we build this DSL using um some word counts that are extracted from the data um we import the DSL and um we then start to build up a set of features that look a lot like what I just put on the previous page so we might say we want the first word um the last word uh the word that comes before so for instance with people uh you'll have titles that come before people a lot of the time so Mr chairman chairwoman so on um you might the word after the end can be important sometimes like for Esquire uh Governor things like that uh uh prefixes of the words so you might want to get you know the fact that sheay starts with capital c then Capital CH and so on um suffixes all of this stuff um and then finally maybe the length like I described before uh names seem to be relatively short and then again whether or not it's in the G here okay and this is exactly how you can write it in Epic and it will um do the right thing um and once you do that uh right okay um once you do that you can uh create your featuer and then pass it into the system in Li of or in addition to the gazeteer and it'll train and use the features that you designed okay so I want to talk a little bit about uh the theory behind machine about how features are used in machine learning just a little bit um we're going to talk about a very basic uh machine learning algorithm called the perceptron uh in internally in Epic we use a different algorithm but it in principle Works fairly similarly to this one um so in machine learning supervised machine learning we're typically given some training example X and a label y so in this case um a sentence uh X is going to be a sentence and Y is going to be some labeled version of that sentence uh broken into say named entities like I should and what we'd like to have happen is that the score for um the training example and the right answer is bigger than the score for the training example and any other answer okay um the score function uh usually takes the form of a DOT product uh if you may remember from uh uh does everyone remember what a DOT product is from high school math okay great um uh so Breeze uh so this is how youd write the do product in math um this is how you can write the dot product in Breeze which is a again that numerical linear algebra Library I talked about um you can also write it as this way um I prefer this format so I'll use this for the rest of the talk okay and so like I said we want the score for um the right answer to be bigger than the score for the wrong answer or all of the wrong answers um and so this turns into uh two dot products um let's coloriz colorize this just a little bit um and um schematically the way dot products work is that they measure the angle between to First approximation they me measure the angle between two vectors so in this case um the dot uh W uh is closer in terms of angle to um y Prime than it is to Y does that make sense okay um and so what this means is then that the score for um the Y prime example is bigger than y this isn't what we want so um what can we do about this um well what we can do is we can add the vector for fxy to W uh getting a new Vector W Prime and it'll happen that um just because of the properties of dot products that the dot product will be uh between W Prime which is W plus fxy um is bigger than the dotproduct of than than the dotproduct of just W and fxy okay so um get our feature index which I don't actually need um we get um an initial weight Vector um which tells us you know which is uh yeah just initial weight Vector W from before um and we go through the training data for some number of epics and we um compute the uh prob we compute the score for every possible label um by taking the dot product and uh once we have all those label scores we want to find the best label score and that's going to be y Prime um and if the it's not the right answer then we want to um in increment the weights by the features for the right answer and subtract out the answer that we guessed that was incorrect and so this will make it so that the angle gets closer to um uh to the right answer and further away from the wrong answer okay does that make sense okay um but in practice uh you can't do this in natural language processing there are too many possible wrong answers for you to uh sum over you to tabulate over all of them in particular um there's going to be L to the two n different ones where L is the number of labels and in is the number of words um and so the longer your sentences the worse this gets um it turns out that there are Dynamic programs that exist uh that can either compute this uh the maximum such sequence or uh the sum of over all possible sequences um and this assumes that the feature function has the same nice form that I just talked about where it breaks up into uh individual components for each of the segments okay um so how's the structure percepton work so it's just the same basic setup we have our initial weight vector and we go through the training data um and instead of getting all possible answers we have our Dynamic program extract the best possible answer um and we do the same update we did before and this is how you can build um a uh this is how you can train natural language processing systems with just this very simple algorithm uh like I said we do something slightly different but in practice this works kind of 80% % or 90% of what you can get even with really good methods often okay um we also have like I said constituency parsers um the uh constituency parsers we have I'm not going to go into how the algorithms work here it's kind of basically similar um our state-of-the-art algorithms um we uh the Berkeley parser even though I'm from Berkley is not my parser um uh oh I did something okay um okay the rickly parser is not ours epic is ours um and our parser is uh we have models for eight other languages um uh we don't have Arabic quite yet Basque French German uh Hebrew Hungarian Korean polish and Swedish and our system is consistently better uh than the system that's was previously the state-of-the-art system across all of these different languages we're also nearly as good on English um we are sometimes a little bit worse we're a little bit worse on French and German and Arabic um but for other languages like Korean and poish were way better okay so epic comes with a bunch of different models like I said uh models for a bunch of uh parsing models for a bunch of different languages as well as party speech uh tagging models for most of these languages and we have named IND recognition for English that's relatively close to state of the art um we also have sentence segment we can break up sentences into uh text into raw text into sentences and we also have tokenization just like I showed earlier on okay uh that's it for epic I'll talk next about Breeze but I wanted to see if there are any questions about epic first yeah what is why is such a dramatic Improvement in Polish uh it's a good question it's a mix of different reasons um oh yes sorry um the question was why uh such a big Improvement in Polish U the reason is that our algorithm uh a couple different reasons one is just that there's a bug in the Berkley parser and it uh outputs the wrong structures as a rule for um different kinds of structures um but it's also the case that um our model tends to work better on uh languages like polish and Korean that have um a lot more complex morphology um just from the way it's built yeah comp did you train your so the question was did we use more data uh actually no we use exactly the same training set um it's all um this is all on what's called in domain data meaning that it's uh the training data and the test data were both um from the same publication basically um and that means that they have the same level of editor editorialization and so on uh but yeah we it's all the same uh data question yeah what do you for let's say you were trying to adop Chinese where timing is contextual it's not part of the Lang from things are connected uh modu pH uh Sor uh what is what is contextual sorry I didn't quite hear you time time is contextual okay um so the question was what do you do when you're if you're trying to adapt a model to Chinese um especially because time is contextual and uh you have to infer it so um parsing is going to be very similar there's not a huge difference in the behavior of um past tense verbs and present tense verbs a lot of the time um even in English and so on and so you can kind of lose that tense information and do okay um we don't add we don't have support for uh things like Co reference resolution and um event extraction which where which is where that would become more of a problem um I'm actually not up to date on uh how people deal with that there is a pretty big literature on translating from Chinese to English um and so I'm sure that people have thought really hard about how it is that you go from Chinese to English but I'm not aware I'm not familiar with literature sorry okay okay I'm going to move on to Breeze then so Breeze isn't strictly a natural language processing toolkit um instead it's a um um uh linear algebra and scientific Computing toolkit um it provides um basic linear algebra like dense vectors matrices sparse M vectors sparse matrices and Matrix decompositions um it also um has nonlinear uh uh nonlinear optimization and probability distributions um and also linear optimization actually now um for those of you who uh I'll put the slides up later so that you can uh pull the dependencies um so the way you use it is it's designed to look a lot like mat lab or numpy for those of you who are used to num uh numpy or mat lab um we can import the linal package of Breeze which gives us access to all the linear algebra and we can create dense vectors um using the syntax um and D Matrix dense matrices and also um dense matrices that have random elements in them which is frequently useful for initializing machine learning algorithms uh we have a sort of a DSL for manipulating matrices so transpose is justt addition is um with the plus operator uh multiplication by Vector is just standard multiplication as with multiplication by scalar and matrices and we also have element wise multiplication so for those of you who are familiar with mat lab this is the same as dot times anywhere where you see a colon uh this the same as uh dot okay uh for the rest of this segment I'm going to use uh DV instead of dense vector or try to um using scola's built-in rename import feature okay so um one of the nice things about Breeze is that it can automatically choose the right return type for different kinds of vectors so if you want to add together a dense vector and a sparse Vector um the the right density is that it should be a dense Vector because it's not going to get any more sparse um but if you add together two sparse vectors it'll stay um sparse I guess that should have been zeros um okay uh and this actually happens even if uh this return type isn't known at compile time uh so we do Dynamic uh multimethod dispatch so that even if uh the compiler only knows that these are vectors it'll still pick out the right possible return type uh slices so uh we also support slicing uh just like mat lab or numpy so if we want to get say the column of a dense Matrix uh we can just uh say column number one we can do the same for rows um these are views of the uh underlying Matrix and so if you take a view update it and mutate it I know some of you don't like mutable data structures but too bad um you can see kind of hiding down here in the bottom that we've updated the last row um it's a little bit off the screen okay um slices we also support sort of rectangular slices of matrices and even kind of exotic slices where you take some columns multiple times and some not at all all just works we also have this function uh functionality called uh uh Universal functions and the idea here is that uh they're vectorized functions that will work on every uh data type in Breeze and also any data type that you want to add um so for instance we can take the log of a dense vector and it'll be give us the element wise log um we can also take the element wise X of a dense Matrix we ALS for those of you who are wondering we have a different thing that's the Matrix exponential which is a different thing um and we can take even the sign of an array and get uh the element wise application of sign we have tons and tons of other functions um all of them have the same syntax they work uniformly across all of bre um sometimes uh in tight inner Loops you don't want to create new objects and so we also support this syntax where uh we say log.in place and it mutates the underlying Vector um and uh just doesn't you know reuses memory we also have uun that are more reduction oriented so for instance uh we might be interested in taking the sum of a dense Vector um the sum of the and sums work for both U floating Point numbers and also integers and it can also work for any data type you want to add like complex numbers or quarians or something um we can do means and of course it works on matrices just like before um but sometimes with dense matrices we're not interested in the mean of the entire dense Matrix we're interested in the mean of uh say all we're interested in the mean of all the rows and so in Breeze we have this concept called uh broadcasting that's kind of like the broadcasting you see in r or numpy uh where we compute uh the mean for every uh row or every column using the star rather than a particular row or particular column um right okay um so the way this works uh this works more generally so for instance we might want to add um a a vector to every column and that works in exactly the same way just using broadcasting and we can also do um assignments and mutate everything in place as well so the way this this works um is using scola's implicit parameter infrastructure so the idea is that um a log extends this trait called uunk and then you can provide implementations by implementing an implicit that's a member type of uh the log object um so for instance here's how we could Implement log um and then as soon as we do that it'll work for Den vectors um Den matrices sparse vectors arrays everything else it just work automatically for um all the built-in types um so if you wanted to add your own add one also works same way very simple okay so uh Breeze offers a lot of flexibility you can do a lot of different things with Breeze in a very simple syntax um and you might expect that you're going to pay a lot for uh in terms of performance uh since this is a relatively expressive sytax but it turns out the breeze is actually about the fastest uh has about the fastest linear algebra library on the JPM so uh this is uh some benchmarks that were done by uh data bricks when they're evaluating adding uh Breeze as a dependency for their ml lib which is part of spark and you can see that we are much faster than um all the major components uh for uh uh on the jvm we're tied actually with mtj we use the same back end as mtj for dense uh linear algebra um but mtj is lgpl and so some people including spark didn't want to use it um on sparse Den multiply we um again are also the fastest we're much much much faster than mahoot um but even we're faster than Apache Commons and even libraries like J blast don't provide any sparse functionality at all um and again on sparse dense Edition um Apache commin is doing really poorly maho's doing great um but we're still just a little bit better okay um so here's an example of an algorithm that you might be interested in implementing uh this is called non- negative Matrix factorization the idea is that you have some Matrix that you're given called v um that has entries that are all positive and you want to decompose it into two matrices uh the product of two matrices uh W and H where W and H are also both both positive the idea being that W is um tall and skinny and is short and fat and so it's a lower rank approximation um there's this who no you're doing it wrong uh PowerPoints messing up but there's a series of updates that we can Implement to implement this algorithm uh this will Implement a non a non- negative Matrix factorization for you um and it works fairly quickly um here is the um uh the updates from the paper that I implemented uh and you can see that um the updates are actually fairly similar so for instance when we update H we're going to do an elementwise multiply of H with um WT * V here uh with the element wise division of WT wh Etc okay and so you can basically take um a full linear algebra uh you know an an algorithm that you might find in some back a paper and transcribe it without um having to think too hard about how you might uh change the syntax up it's just pretty straightforward mapping another thing that's really great is um this language uh this Library we're making called gust which is a GPU accelerated version of Breeze uh that runs on Nvidia Hardware um and so we wanted to the non- negative Matrix factorization wasn't quite fast enough uh for us in Breeze and so we wanted to Port it to the GPU um so this this was our non- negative Matrix factorization from before um and here's how we had to change it to turn it into a GPU algorithm um even on a very small amount of data on my laptop it was six times faster on a desktop it's closer to 50 or 100 times faster okay um I'll go really quickly through optimization sometimes in machine learning we want to optimize a nonlinear function um so here's a simple uh uh polinomial function um in Breeze we have this thing called a diff function which is a differentiable function function that has a method called calculate that Returns the uh value of the function as well as its derivative and it's generic in type T so that you can use um DSE vectors sparse vectors uh coup vectors from gust if you wanted to um and uh yeah you can implement this function um it's you can trust me that it's the right answer and um we can call the uh minimize function on breze which will automatically use a state-of-the-art optimization algorithm to find the minimum uh a local minimum and we can ask with compd if we got the right answer and sure enough um to eight or nine disable places we got the right answer um it's fully configurable so if you're used to this machine learning speak we have support for lbfgs which is what that stud art optimization algorithm was with uh L2 and L1 regularization uh which is machine learning stuff uh we also have stochastic gradient sent with L2 and L1 regularization specifically the Adaptive gradient algorithm which is this really awesome uh stochastic gradient method uh we also have truncated Newton if you're interested in uh doing second order methods um and we also have linear programs and all that fun stuff okay thanks okay uh question questions yeah sure you know is AOL Library fores I've SE some evidence that I'm yeah um yeah that's a great question so the question was um Spire is of course another bre another numeric library for Scola um that's focuses more on abstract algebra and things like that uh and there interested in integrating more tightly with Breeze that's something we're definitely interested in uh we actually have a Google summer of code uh student uh who working on doing some of that in addition to building um uh some kind of uh as astrophysics simulation that will sort of show off both uh spire and Breeze and then as he's building it sort of integrate them so it's something that I'm excited about I hope it comes out yeah uh next question yeah Distributing the GPU stuff um no uh so gust is actually very new um I wouldn't even call it 0.1 release even um it does the non- negative Matrix factorization really well and a couple other from Distributing it um it work it would work in exactly the same way as Distributing uh a breeze object which is just stere well that's not true um you would have to convert things to a in memory representation that's not on GPU memory and then send it across but there's nothing stopping you from doing that um but yeah uh another question yeah uh Breeze or EP epic epic so epic comes with a bunch of different train models um mostly in parsing and Pa tagging but we also have a pre-train model for um for uh English name dity recognition as well as a sentence segmentation I'm sorry uh yeah so everything all of these libraries are Apache licensed um and so you can use them however you want well subject to those licenses but pretty permissive yeah Bree uh with Breeze um we had a library that we started to build called Breeze viz um um I I'm I don't use a lot of visualization in my day-to-day job and so I just kind of don't up keep it up to date um it exists we're looking for maintainer so if that's something you're interested in doing we'd love to have you um but it kind of works you can use it for basic interactive plots and it works with Breeze fine but it's nothing like you know uh M plot lib or anything like that yeah things that you have to load into memory work um sorry this a little clattering can you say it again is it lied to work onu you have um so there's not a lot that's built in that's designed to work in a streaming fashion um but there's nothing stopping you from using it that way um but it's but I don't have anything that's that's specifically designed to for keeping things out of memory um you you know everything is all the stuff in Breeze is serializable so you can send it to dis if you want but I don't have anything spe specifically for streaming algorithms yeah so um it depends on what you're trying to do so one of the things I really like about Scala from a natural language processing researcher point of view is that Scola the language itself is very fast it's about 30 times faster than python um when you need to write your own code um and so I have this hybrid thing where I do some linear algebra numeric processing but a lot of what I do is writing tight in our Loops for dynamic programs and you can't do that in Python you have to switch to C or something horrible like that and so Scala is sort of a really great balance for that and that's my motivation for doing uh Scala I also really like static hping I think it makes for a better um uh easier development cycle um but you know your mileage may vary um any other questions how do you compare saddle how do I compare saddle um yeah so saddle is an interesting library that came out a couple years ago um it's it focus is more so we're more like mat lab and uh they're more like R I think is the right comparison um I'm interested in bringing in some of that functionality it looks like saddle is kind of dormant right now they kind of don't have any updates I haven't seen anything since March and it was just some minor P request merge um so it's uh I'm interested in sort of basically taking the interesting bits out of Saddle but I would say the big difference is we're more like mat lab and numpy and they're more like R uh any other questions okay great thank you very much I'm going to take this mic over