Text By the Bay 2015: Seth Redmore, Transforming a Recommender Algorithm into a Multi-lingual Parser
so i'm seth redmore and i'm with a company called lexolytics and what i'm going to talk about is how we took an algorithm that was in process for doing online moving recommendations stuff that was developed around the time of the netflix challenge and how we turned that into a very efficient uh very scalable multilingual part syntax parser so what are we actually going to talk about um who we are who i am who we are um syntax semantics in context so we're going to start kind of high level um talk a little bit about syntax parsing and some of the ambiguities that we as humans just kind of naturally deal with but the machines are going to be way less good at dealing with how you can apply matrices to resolve some of these ambiguities based on large unsupervised training sets switch out a little bit and say okay let's talk about movie recommendations and matrix factorization and movie recommendations how that actually works uh and then say okay here's how we applied it to syntax parsing how we actually trained this and sort of where we're going with it and some of the high level results we got with us lexalytics founded in 2003 we've been around for a while we build the text analytics engine we provide it as on-premise software or a software as a service we are very popular in social listening platforms so a lot of the major you know if you pick the top ten probably six or seven of them use us uh for social listening for customer experience management then we've got one c2c customers and like pharmaceuticals business intelligence things like that we process a lot of content a lot of content so let's talk about syntax semantics in context so each of these is important for understanding the meaning of a sentence and so you know syntax is your actual structure semantics is the meaning of the individual words there's better definitions than this but bear with me on that uh and context is way fluffier so you know it could include the shared history between whoever is speaking and the person they're speaking to it could include you know if you just see a tweet that says i love the apple store okay prima facie just by itself all you can say is that that person loves the apple store but if you know that the last tweet was um i waited in three then hours for three uh waited in line for three hours and the genius was an idiot then that tweet means something very different so we've done a lot around semantics been a lot around syntax one of the things i think we're going to be seeing a lot more this is a side note over the coming years is involving a context because there's only there's certain problems that you really need the context in order to solve i believe that you know sarcasm and irony um are very context dependent problems and require that and so i think you'll see a lot more with tracking individual context or you know clustering users into contextual groups but we're going to focus on syntax today because that's the title of my talk um so syntax we've all done these it's it's funny my mom's an english teacher and i actually had her for english in high school and and it's um so sentence diagrams it's just like i'm looking at doing these and i'm like i'm never ever ever going to use this again in my entire life and so now my career depends on it and and it's just my mom finds it really really funny um so you have to be able to you have to be able to tear these sentences apart and associate things and um dependency parsing is expensive it's computationally expensive there are different ways to do it that are less computationally expensive and and we're going to be talking about one of those ways it's really important though so if you look at this sentence it's ambiguous towards tea positive towards coffee but if you were to parse this in correctly you know this this is the correct parts but if you don't want to have the not apply to prefer you don't want to just pull out don't like tea because it's the it's not that i don't like tea so these are all syntactical things that affect the overall meaning of the sentence and so you have to be able to to understand the structure of the whole sentence in order to understand what's going on so let's take another a little more ambiguous uh sentence so janet will be joining a team already with the search expert so so this tells us a couple things if we can understand the meaning of this it tells us um maybe there's a concern about the fact that there's a search you know a lot of search experience already on the team there's already a search expert there wise jane joining this team right so there's there's some stuff that's implicit to this this sentence that you get with the fact that they're saying already with a search expert um and so understand this gives us a meaning this is where we started to get into more ambiguity so jane is joining a team already with some search experience is is jane the one with some search experience or is the team with some search experience um and this is the sort of ambiguity that we we tend to deal with really well as humans and so we would just say okay you know jane is joining and she's got some search experience right if you look back this sentence is also equally ambiguous but we would tend to resolve it a lot faster um jane may be carrying around a search expert with her liking her back packet and that's an unlikely person we know that from from how the world looks to us that probably not carrying a search expert around with her maybe but machines don't know this and so that's what we're trying to solve or solved is the the problem with how can you figure out these linkages inside of the sentence and the dependencies so let's step back for a second and say how could we actually approach this problem so first we would take a sentence lots of them um part of speech tag them chunk em and so you know part of speech assigns an individual noun verb chunk designs what kind of phrase it is as well as okay these words belong together um and then we use certain rules to um to say okay well this one almost certainly isn't going to modify this other one so for example a conjunction uh is almost always going to is going to modify things of tune types you aren't going to say iran and bob so you can use these rules to kind of prune things a little bit and then you end up with um a tree of possible links so pause tag it chunk it and then the different chunks here jane will be joining will be joining a team a team already a search experience we'll be joining already a search experience jane already with search experience so these things you put together and you can use this as a training set across a sufficiently large corpus of content and so what you end up with is you end up with a matrix okay and so your matrix is is all of the chunks and how they relate to each other okay this is large and it's brittle but you can see how this could be used to resolve those questions about okay what are the proper links because over a large enough set of content you will start to see similar links emerge let's talk about kind of how big this problem is and trade-offs between size and performance much like a spork so the netflix data set uh was about 100 million triplets our training data set is about 40 gigs of um of english text about 500 million sentences once we do the pruning that i talked about before it makes the problem more tractable because you drop it down but you still end up with about 200 000 chunks and so you're looking at a matrix of 200 000 by 200 000 or or 40 billion cells in the matrix that's a lot to carry a memory and it's very brittle so the problem here is if you just look at the exact matches inside of the sentences then your matrix isn't going to be able to handle matches that aren't quite like that and so what you want to do is you want to extract some sort of latent factors among these that allow you to say okay these are similar to this and that's similar to that and so okay this is probably going to match right um and you also want to be you know so how can you compress it so it's not two hundred thousand by two hundred thousand and how can you extract these latent these latent factors um movie recommendations use collab so stepping back hold on a second sorry um and i even quit smoking a while ago so consider the problem of recommending movies and say okay here's my matrix of movies versus users so users and movies and some users are going to rate more movies than others and you want to be able to say okay for the user that hasn't rated a particular movie if they want to watch this movie what is the rating for that particular user for that movie there's a couple different ways to do this nearest neighbor approaches um we're sort of the start of this and kind of the most intuitive approach which is basically looking for somebody that looks like me the problem is these are very sparse matrices so you have 20 000 movies you have 100 000 users and each user is only say rating you know 200 it was actually this is true so they were only rating an average of 200 movies and then you have some users that rate two and then other there's this one user that rated 17 000 movies okay it's like okay um did you watch them um so using a nearest neighbor approach fails because of the sparseness here so what you want to be able to do is extract the latent features in the movies to to say okay this one is kind of like this one and so i can make some make some guesses about what's going to be inside of the inside of the blank columns so let's talk a little bit about what that means so for matrix factorization what you're trying to do is split this big matrix of users times movies into two separate matrices that are each size of say the users times the number of factors and the movies times the number of factors okay so the number of factors is going to be smaller than say the users and the movies so say you have you know 10 000 users and 10 000 movies if you can get it to like 10 000 users and 10 user factors and 10 000 user 10 000 movies and 10 movie factors you've really compressed the amount of space you have to worry about and you can find some similarities across these things and so basically what you're trying to do is find k number of latent features so that you have two separate matrices so that the dot product of these two matrices allows you to um give an approximation of what should be any any empty cell um so you want to find these matrices you have to you have to actually learn these factors and there's another i'll talk a bit about how we actually approached it um so what you want to do is minimize the error the least squares error on the cells that you know and so there's other things you want to do to prevent overfitting of your model so there's regularization and things like that that you want to do that i'll touch on briefly but if you sort of look at this as broadly speaking this is how you deal with matrices and then there's a couple papers i refer to that if you want to get really deep into it you can um so in our case we ended up doing uh 200 factors for ours and so it ended up going from 200 000 times 200 000 to 200 000 times 400. so we go from 40 billion to 80 million great okay so there's there's a certain amount of compression and we ended up at 200 because we tried 100 and we tried 400 and we tried you know and sort of worked our way experimentally up to that a lot of this is try it and see and try it and see and try it and see um there wasn't a particular law that we could follow that said okay it's going to be you know n minus 2 divided by x it just wasn't we just had to try it this is the really cool part um hashing so so this graph that isn't terribly readable it's right out of this paper so i think i'll post this up on up on our blog later so you can actually get to this this mit paper and it talks about um hashing and matrix factorization and um efficiency around it but what this did was so this this particular use case was um around each movie data set um it was a rating from one to five not one to four so it was one to five ratings and then the um the scale is uh the root means group mean square error or mse error for the amount of compression from hashing okay so by hashing basically you are randomly assigning any particular entry into one of the entries inside of the um inside of the hash table and so if you look on the left thousands of entries elements in u so the user matrix they go from about 1.2 million down to 60 million and then thousands of elements in the movie elements from 32 000 to 5000. so we're talking a factor of 20 compression on the left and you know a factor of something like seven or eight compression and they went from a one point two root mean squared error to a one point three three which is crazy right that you're getting a 20 to 1 compression you know times more than 20 to 1 compression and you're only losing that much in terms of your recall so um we actually did 50 compression of phrases and it cost us three three points on our f1 to do that we have a big trouble we have a lot of trade-offs we have to make because our customers are sensitive to how many cores they have to throw at a problem um if they're dealing with the twitter firehose if they're dealing with very large documents if they have latency requirements in terms of alerting and the big issue is it isn't sort of okay if i could spread all my content evenly like peanut butter over the bread during the day the problem is when they get this big burst because something happened and so they need to be able to chew down through those because they've got a 30 second window in which to alert their customers that something has happened so we have to make trade-offs all the time between accuracy and performance and this was a great trade-off for us so you know it really increases our number of cache hits all that sort of stuff just works better so how do we train this um there's a lot of this is where the embracing the noise comes in um we start out with extracting all those chunks and then we randomize we mix them up and so then we hash the input phrases so the first thing after we mix them up we hash everything and so you know we tried you know tried a couple different seeds and stuff so we optimized that a little bit um and then you randomly initialize both matrices so there's another bit of randomness um and then what we do what you do is apply a model-filled fitting algorithm so for matrix factorization there's a couple different model fitting algorithms that are popular stochastic gradient descent and alternating least squares are the two that you're going to see most commonly here in our reading and our research we decided to go with als there are some certain performance characteristics that are superior for us in our case some people prefer to go with stochastic gradient descent it's really kind of up to you um sometimes it will the als will diverge and so there's some exponential issues with it but we just throw it away if it diverges so does the model converge once you once you've actually gotten to it no if it's diverging okay great throw it away start again you know hash your input phrases randomly initialize both matrices and go did you get a better did we get a better f1 so we had um a set of content that we were scoring that we knew how it behaved and so we just scored the new matrix against it did we do better okay great um so we'll throw away the last one and keep this one and then are you bored with actually doing this process or are you getting limited returns and so it really came down to okay we just hit a point where we just really weren't getting anything worth spending the three or four days of computer time to run the model we had to run through this about 300 times before we actually got something that we felt was a good local minima of performa local minima in terms of the noise local maxima in terms of performance and this is really this is really an important part of this kind of factorization is you're starting out with a number of random things and sometimes the distribution is going to be a pathological distribution and it's not going to converge right and that's okay you know it's nobody died it just you throw it away and you do it again and you just keep doing it until you've reached the point where it's like okay i'm not getting any further there's a couple details about this i already talked about the als versus stochastic gradient um when you're looking at uh model fitting here there's a couple things that you need to consider and you know i'm not going to spend a bunch of time on this but feel free there's all kinds of literature about this how do you how do you change okay so there's a value in a cell and you you are your error is this far away how can you move closer to that without sort of overshooting it um how can you make big jumps in the beginning and then small jumps later as you get closer so these are so the loss functions um are all about how do you actually move closer to the value you're actually looking at based on your error from there and so we went with something called huber's robust loss there's other error functions you can use we tried them they didn't make a huge difference you know there were small small small differences and so this one just happened to have some good characteristics in terms of you know how it behaved early on and then and then closer on other things with matrix fitting is content that comes in earlier means more than content that comes in later so it's sort of the square of how far in you are and so big changes are going to happen early on and then smaller changes later on regularization is another concept you'll see so regularization is a way to kind of keep things from getting really weird inside of the the matrix and prevent overfitting because if you if you fit too hard to to the stuff that's there you could end up with something that's complete noise and it's just but it matches really great there but it's some really complicated fitting that's not going to predict anything in the future and so all the regular regularization parameters help prevent that so backing up um consider this problem do you want me to get anything else while i go to the store for milk pause tag it and chunk it so here's the possible links right and and the interesting um chunks inside of here that are are that i want to talk about to the store for milk so is it a milk store right and we can tell that it's not he's going for milk right i mean we know this and with a large enough corpus of content if there were milk stores you would see you know milk stores closed today in observance of this holiday and milk store robbed yesterday at 5 p.m and you know store for milk closes down and lays off all the employees so that's what the unsupervised learning across a large bunch of content does so we used for ours we use common crawl wikipedia um social and um a bunch of big news corpus and these things just pop up and it makes more sense so results uh we resist our polar opposite error these are errors where we see you know we we have a set of content that's really hard content we picked it hand curated it to make it really hard for ourselves um so the polar opposite errors inside there we've re-reduced by 50 percent so stuff that was scored positive should be scored negative um our worst case entity sentiment f1 so whenever people people talk about accuracy and text mining you always have to ask the question okay over what content set and how are you measuring you know how are you measuring against it what's your iterator agreement all that stuff but so i'm just talking worst case we got a 10 improvement in our f1 scores um these are the kind of things that we handle way better now cnn reports that indiana is facing an unplanned unpleasant backlash indiana negative cnn neutral um bob's house of donuts stopped making bad donuts well that's that actually is positive inside of here but rachel stop playing on time as neutral so that's what we did that's how we did it and now we're onto questions if you have them thank you for listening which numbers or which where uh back here so stop me when this one yeah yeah so this is um for a set of you know for a corpus of content we'll see the word team with you know is joining 22 times we'll be joining 10 times i mean it's it's a lot more complicated than that under the covers but that just gives you a general idea of if you process through stuff you're going to naturally see chunks occur with each other and chunks link to each other and if you look over a large enough corpus of content rare cases will get mushed out and the common cases will so you can say oh it's probably going to be linked with this so so so the the way to think about this is look at this i threw the ball right things that you throw relatively small you can hold it in your hand chair is probably starting to get to the upper limit of things you throw you don't throw a mountain so you're never going to see i threw the mountain or i threw the building unless you're talking about legos so so that's how these things line up so the properties of things that are throwable you'll start to see them kind of line up inside of the matrix through comes to things walk goes with certain things and stuff and it's not just non-verb relationships it's others but that's does that answer your question okay um so pause tagging makes the matrix in the first part in the first place so and then we use the matrix factorization to determine okay what are the things that are most likely to go with other things and then we use that to help us understand okay what are the what are the links inside of a sentence and so we pause tag first and then we chunk into the chunks and then we then we this is called the chunk parser and so then we use the chunks and then we use this syntax matrix to actually say oh okay that chunk probably goes with this other chunk and when we parse an individual sentence and we do the pause tagging the chunking will handle a big part of that it's the relationship between the chunks that we're worried about with us you