Text By the Bay 2015: Marek Kolodziej, Unsupervised NLP Tutorial using Apache Spark
Recording: Text By the Bay 2015: Marek Kolodziej, Unsupervised NLP Tutorial using Apache Spark
and I'm gonna be talking about deep natural language processing using word to vac and spark actually more than just spark and more than just work to vac but this was the sort of got it had to compress the the content into a short snippet okay so I'm actually going to be talking about a bunch of different things that I hope will elucidate how word Tyvek works first of all I'm going to mention that traditional and LB challenges how how you normally do NOP explain the word vector intuition how it relates to what do you probably already know from linear algebra from machine learning then I'm gonna explain the word Tyvek algorithm in more and in general in more detail I'll mention that worked effect extensions because this is just the starting point for what word vectors essentially and then mentioned the applications because you've probably all seen that cute examples like manage the woman asking us to Queen but that is not particularly useful if you're actually trying to solve a business problem so hopefully I'll explain how that can can be used for feature learning and putting that into other models and then I'll do a quick spark demo although I have to say the best implementation so far is in Jensen I think the the SPARC version needs some more work so the emphasis of this talk is gonna be on the fact that first of all deep learning and work vectors aren't really new they're just natural progression and evolution of machine learning and an NLP and if we actually relate these concepts to what we already know from from other areas of machine learning and NLP then we'll be more empowered to actually integrate them into our existing pipelines so I'll show the relationship to prior art and that's really what's new because when when Thomas nickel of paper came out in 2013 it wasn't clear how that related to anything but this is actually the power that you can integrate back into what you already know then the other issue is of course what's new is fast draining now that we have GPUs and and clusters like spark cluster frameworks like spark it's actually possible to train on bigger data sets and these algorithms need that ton of data and in I'll mention how that this basically doesn't end with these these really simple analogy examples okay so what are your traditional NLP challenges if you look at pipelines right we started with cleaning up your text and if it's HTML you probably remove HTML tags you remove some H some boilerplate from the document there Java libraries like boiler pipe for that then you have to detect your language right because it like like we had nitro or dealing with documents in all kinds of languages and if you're doing an LP you cannot mix you know your Hindi documents with your you know English documents or German documents right so you have to do that first and that actually is generally an NLP problem doesn't matter what kind of a classification algorithm you use but basically it's it's it's already machine learning at this stage okay once you picked out I picked the language in you and you just filtered for a particular language like English you have to do some of this segmentation for English it's that that's fairly simple then you do word segmentation and English again it's really simple right because you just look at for white space but for languages like Mandarin that's actually not easy at all so this is a classic example where because Chinese doesn't have spaces between words you could separate the words differently and depending on the separation you'll have a completely different meaning of the same sentence right and that's actually a big problem so so the the word tokenization for chinese for example is a probabilistic problem it's in this case it was a way to the finite state transducer which could be really seen as a hidden Markov model essentially let's see I'm gonna do spell checking right because that there could have been spelling mistakes and the text itself and the quality of spell checking depends on the effort because if you do something like at a distance or noisy channel that's only based on the particular word if you if you're looking at the context then you have to do m grams and hmm and so on then in some cases you may want to do stemming or a limitation and again depending on the complexity you get different results like the porter stemmer may be really fast but it makes this universe with the university so you may want to remove your your stop words with the help of tf-idf do case folding etc lots and lots of free processing right before you get to any interesting stuff at a higher level right if we think of computational linguistics we might think about morphology for example and limit ization as being a problem of dealing with morphological features right such as inflectional order of a tional morphology and in english it's actually simple you can build you know finite state transducers for that but a language like Turkish which can be seen on the right has so many different components is not just a simple prefix or a suffix it's it's next to impossible to figure out what what is going on right the nobody I think achieved a good good model of Turkish because it's so complicated so then you may want to look at syntax depending depending on your problem right to do part of speech tagging or our grammatical parsing etc etc right but this is all busy work right I mean it's interesting for computational linguists if you're if I'm a computational linguist I care about part of speech tagging right but if I'm just doing you know named entity recognition or some or some prediction this is really just be processing for me right so at the end of the day these were not the end cuz the angles are things like named entity recognition that bill is a person in Seattle is a location or relation extraction that bill lives in Seattle and the action of living is related to you know the subject of Bill and so on and so forth core efference resolution I want to know that it relates to music or they rule it relates to the neighbors right because I'm trying to do two to basically get some semantics out of this analysis right may I mean want to do pragmatics if I'm actually generating language right I should be able to know that I should say I'm afraid I can't as a post I won't write if I'm is supposed to be proper discourse right so going back to the Space Odyssey example I'm sorry Dave like I'm afraid I can't let you do that that actually relates to open the pod bay doors which is from the previous sentence so again you have to have some notion of this continuation between of the semantics between one sentence and another and and basically things like named entity recognition summarization machine translation these are the end products right a lot of the other stuff may be interesting to computational linguist but it's really busy work for for me as someone who is trying to get to these end goals and if you actually look at how much feature is a ssin is needed for different algorithms sort of the classic example is that named entity recognizer from Stanford core NLB which is actually really really accurate but it required a lot of work to get implemented and so for example if you look at the features for this algorithm which uses conditional random fields as the algorithm itself if you look at the features it has a current word previous word next word and then it has the letter Engram of the current word and the current part of speech tag and the surrounding part of parts of speech and the word shape whether for example the letter is capitalized or not and how are you going to figure out all these features right depending on this is just one stay at this step in the pipeline if you have to do this kind of feature ization for every problem for every language that's really a lot of work so so yeah and you know if it's if it's machine learning have to do feature engineering if it's rule-based then you have to devise the rules for every language right it's a lot of work and and so you know this is definitely a lot of work and you also need label data right because because if it's a supervised learning algorithm for example then you have to have labels so okay enter word vectors they're supposed to solve a lot of problems here so we're the betting's as Adam Gibson said during his previous talk is is basically just a way to compress the word into a numeric vector of double numbers and that vector is supposed to be short up to 3 or 400 elements and it's supposed to be dense unlike you know all the sparse data in in language you have lots of lots of zeroes in the matrix right so I'll show you how to generate them in a second the two papers that were really influential in this area were by Tomas Miko of who I guess is at Google still he introduced word Tyvek I highly recommend them but if you look at a more broadly this is actually not a new concept and this is the point I'm trying to drive home that this is not some revolutionary technology that will replace all of machine learning and NLP you know despite all the you know media attention that has been generated around deep learning this is actually not new so for example Geoffrey Hinton introduced distributed text representation is back in 1986 also there has been research about this NLP from scratch back in 2011 you know if you think about word vectors that capture semantics and semantic and syntactic features you know engrams also capture semantic and syntactic features for example if you look at the verb phrase you know that is captured in this by Graham and and there's also semantic information such as eating British food actually having a very low probability so it captures semantics and cultural even cultural factors in a simple by ground so again nothing new really you know it's not just unique to word vectors you know again neural nets are not new in language yoshua bengio had a paper back in 2003 there was more research by Culbert and weston this is a classic that a lot of the neural embedding stuff refers to neural nets are not a new thing Frank Rosenblatt introduced him in 1957 representation learning is not a new thing Geoffrey Hinton worked on it back in 1986 recurrent neural Nets were introduced in 1990 convolutional neural nets were introduced in 1980 restricted Boltzmann machines were introduced in 1986 and so and so forth if you're interested this last paper actually is a good literature review of the history of neural networks but again it's nothing new really it goes back to the 50s in terms of the concepts themselves and Yamla Kuhn actually got a nice post on Facebook recently saying you know here's my message from the AI hi busting Department I've been working on convolutional neural nets in face recognition since 1993 so what has changed really is the computing power that we can do it faster and at a greater scale and that's actually the probably the most important thing because because these algorithms really benefit from a lot of data and so and so the fact that we can do it on GPUs and computing clusters really brings out the power but a lot of these algorithms have been around for decades essentially okay so what how do Ord vectors work right if we if we think about traditional encoding in NLP which is really sparse is is one hot encoding so hotel has one in one place and zeros everywhere else and motel has one at a different place right so this is a very sparse vector it could be like millions of elements and could have one in one particular place but there's no relationship between hotel and motel obviously in our minds there is a relationship between hotel and motel but not numerically between these two vectors so what you really want to do is to learn these real valued word vectors that are dense that are low dimensional and that capture these syntactic and semantic features these relationships between between the words and what would the ideal would be to basically be able to relate these words in some using some simple similarity measure like cosine distance or Euclidean distance or whatever and to be able to visualize them using PC itsme but several people mentioned t-sne today that was based on this 2008 paper as you might guess you may have seen I actually but all the literature links on this slide so hopefully that'll be useful if you want to revisit these papers okay so how can we relate to the word vectors to something we already know because they're really not nothing new and in reality you know if you were to look at it from the perspective of matrix factorization you can slide a window over the corpus get some immigrants essentially or back or this continuous bag of words and count the number of times the Center word co-occurs with neighboring words right so I have a Center word and I have five to ten words to the left and to the right and then I basically count how many times these things go occur in a matrix and and because this matrix will have high dimensionality and it'll be extremely sparse what we can do is either is sparse storage or like cache maps not actual matrices with lots of zeros or use dimensionality reduction we could do SVD PCA etc to get these dense vectors some research actually found that SVD is really good for that however it's not good to have actual counts because both SVD and PCA are sensitive to scaling so the best thing to do is actually to look at to convert this to a correlation matrix and then all the numbers are between one and zero and you know if you want to refresh your linear algebra basically you create two diagonal matrices and multiply it times the original covariance matrix and that's how you get correlations Pearson correlations anyway and this calls paper that I'll mention in a second basically implemented word vectors back in 2005 based on this matrix factorization so first you calculate the correlation is just to sort of normalize this matrix for these Co occurrences and then you and then you do SVD so I'm not sure whether people are interested in SVD but you have your eigenvectors in the matrix u and then another set of eigen vectors in the matrix v and eigen values in the matrix Sigma and basically if you look at the relationship between singular value decomposition and and principal component analysis it's it's very close because for for the you know basically if you generate SVD off of a covariance matrix like m transpose M or M M transpose depending in what direction you're going then taking the the the fact the eigen vector matrix U or the eigen vector matrix V and for example at the bottom if you do even transpose then you then you pick your eigen vector matrix U to get to get the principal components essentially so that's how we reduce dimensionality and this is the link to the paper and let me show you some visualizations because that's actually what seems most intuitive about this so by just doing this simple matrix calculation you can actually realize that the simple projection onto a two dimensional space will put all the body parts together like wrist and ankle and but not in the top left corner of this of this square and you know various creatures like mouse and oyster and lion are gonna be at the bottom left and cities like Tokyo and Montreal are gonna be on the right-hand side and so on so basically this simple projection actually shows you the word relationships and this is just based on counts and the counts can be converted to correlations so it's nothing fancy really but it's very powerful and if you do hierarchical clustering you can actually see that this these relationships I really find the grain like wrist is very closely related to ankle but it has some more distant relationship with some some other body part and you know the this this can go on and on so for example swim is related to swimmer the same way teach is related to teacher and marries related to bride and prays related to priest so this was back in 2005 so this is not too much Michael loves word Tyvek this is like basic matrix factorization but it works the same way in reality this is just pure linear algebra like linear algebra 101 okay but it's actually not perfect so for example if you look at this visualization you will see that showed let's see what would be a good example here so taken the present perfect form you know maybe maybe let's say closer to the bottom left then a for for this particular verb then then the past then the simple past form but if you look at some other verb the relationship is going to be reversed so you get the clustering in between but for different forms of the same verb but they don't have the same distance in a way so it's definitely not perfect but it's it's definitely it's definitely very appealing to see it as a pure matrix factorization if you look at a more recent paper from 2014 they actually look at the word defect stuff so the more recent version of what vector or presentation and they related back to imposition matrix factorization again although what's interesting is if if you transfer transform the word Tyvek model into a matrix factorization is actually the factorization of the point-wise mutual information matrix which you should know from NOP so it's it's it's very nice to actually know that what has been done before is actually just as useful today it's just a different representation of the same thing and sometimes actually doing small tweaks on top of what you already had could could boost your accuracy a lot or or generate new results but but it's still interesting that there's this continuation and accumulation of knowledge not just some revolutionary thing that obliterates everything else it's actually just the natural progression and there's another paper which relates word embeddings to principal component analysis so so this research on matrix factorization is going on so this is nothing really out of the ordinary but there is a problem with these matrix factorization is right so there's slow learning if you have if you have quadratic scaling with the number of documents that's pretty expensive especially for on a cluster that's not really a trivial cost and these word relationships are fragile so they clustered together as I mentioned but for example the relationship between one past tense and other past tense can be reversed for two verbs right and this is not great so it could be better for sure okay so that's where the word two fact model comes in and and it's there are two versions of it there's the continuous bag of words so you basically slide a window through the document and you have let's say five to ten words to the left and to the right of the center word and you're trying to use these words to the left and right to predict the center word so that's the the bag of words approach and if you use the skip gram then you basically are using the Center word to predict the words around the center word and the skip gram is actually more performant from an implementation point of view and and so essentially you're basically trying to optimize this cost function which is just based on the summing these log probabilities of the words surrounding the Center word condition on the Center word so that's the Skip Graham model which is actually easier to explain so that's what I mention you have the convenience bag of words where you predict the center word based on the context or you predict the context based on the Center word in the case of the Skip ground I'll probably get to the math a little bit later but let me just show you something real real quick here so first I'm gonna actually start with Jemison demo as opposed to the the SPARC demo because unfortunately SPARC doesn't have a lot of things implemented yet and I just didn't have the time to get to it but everybody probably has seen this example of manage to King as a woman is to Queen right and I'll actually explain why this tends to work there's there's a very simple mathematical reason behind this but you can see that Queen was the top choice in terms of the the greatest cosine similarity but there was monarch and princess and so on as runner-ups so it's so these analogies are one way to do you think of word tivac and this is sort of a nice way to dazzle VCS and stuff but it's not particularly useful for solving actual business problems I would say that the basically finding finding similar words and not exactly synonyms but similar words is probably more useful so you can find for example if you search for iPhone you're gonna find iPod and if you search for I don't know Java you're gonna find whatever what are you gonna find let's see oh that is weird okay that's the actual that's the actual geographic Java alright that's fine but here's but here's my favorite what do you find if you click on USA anybody want to guess has anybody seen this demo before okay check this out this is like how how great the semantic analysis is of word to vac trademark law suits awesome you also can do all the one out like what is not related here dinner cereal breakfast and lunch well cereal is not a meal type but I mean it's a meal type but it's not a meal per se right so it's gonna add one add one the cereal right this is actually really cute but you have to remember that this was learned on a hundred billion words so that's not a small data set and it really took a long time to train but Jennsen is actually really fast it's it may be Python under the hood so the Java people are probably gonna cringe but but the implement the internal implementation was using Blas which is a fortran library that's the fastest linear algebra you know system that exists and the python part is written insight on so it compiles to to machine code anyway so this is actually really fast and you know this can run on common crawl in a couple of days probably like two days or something it's it's actually on a single machine so you don't need to spark for everything and jetsam is a really nice library so let's go back to the presentation oh let me actually look at spark now because I think spark is next yeah so spark who doesn't know about spark dude do you want me to sort of briefly mention what spark is or it does everybody know I guess you probably got you probably know okay so so spark actually has an implementation of of where to vac but unfortunately that implementation is only limited to synonyms so the only thing you can do is strain the corpus and then basically find the synonym you cannot do these analogies like manage to King as a woman is to Queen you cannot do other one out and you also cannot just well you can use the word vectors directly you can get the numeric representation so you can actually feed them into other algorithms so if you for example do Java right you basically find that the top 10 you know related concepts are servlet and applet and whatnot actually if you think about this VNC and GCC and so on and the scripting probably shouldn't be related which just shows you that if you cannot control the semantics that you're getting out of it you can get some really weird stuff and and and you know that's actually part of the problem that if you have no control over what synonyms is generating it may actually learn some really weird weird stuff what would we get if we did buy thon just for the heck of it okay Monty Python nice oh yeah circus okay great the wrong Python for sure I wonder which sketch it is the dead parrot or something anyway not everybody is a Python Monty Python fan probably okay so okay so going back to the math right like people are dazzled by this idea that man is related to King as woman's related to Queen how the hell does that work well actually it's pretty simple if you think back to to this SVD perspective and matrix factorization perspective if it's all basically in your algebra then these relationships should be linear right and there's this Microsoft research paper another paper by Thomas Michael actually which basically shows that these are simple vector offsets so if you look at this vector space at this two-dimensional projection these vectors have the same basically a particular concept result results in a particular two-dimensional offset of the original vector so if you for example add the if you subtract the concept of man from King then you still still have this notion of being regal right and then you add the concept of woman so you get Queen because it's just a it's just a two-dimensional offset and this vector and this paper actually shows how how this works but essentially if you can believe that this linear algebra decomposition from the beginning is a good representation for the intuition behind the word defect and then simple vector offset should actually work and and this is not just for for semantics this is not just for semantics such as you know man being related to King but it's also a syntactic representation so King and Kings and king and queen and queens for example just briefly there was another really brilliant paper which basically says hey this is not just Auto magical and I have no control over this algorithm you can actually control what these vectors are representing so for example if you just used word Tyvek and you related Alan Turing to other things you would get finite state and deterministic and compute ability but if you wanted to relate Alan Turing to Linux Pauling and Harold Hotelling and other scientists then you could do that because if you control the the dependencies in your sentences then you can basically force the model to to learn different things this is really cool because this is an unsupervised learning algorithm so normally you would just have to deal with whatever it learns but if you can control what it learns and it's actually very powerful there's this glove paper which which basically again shows the relationship between between linear algebra and and neural networks and and and how it all fits together and this paper actually shows even faster ways to learn than word Tyvek although it makes a claim that it's more accurate than word to vacuum this was disproven by these folks in Israel who said look if you actually compare apples to oranges if you looked at the same window sizes and the same you know datasets and stuff you would actually realize that it's basically the same accuracy you might actually have a better intuition behind your model and it may learn faster than word 2 fact but it's not really super awesomely more accurate and let's see ok this is actually a really good paper because a lot of people complain about deep learning and about you know machine learning in general that hey I don't know how to tweak my hyper parameters and especially in deep learning because a bazillion you know parameters like window sizes and regularization and what then how do I actually figure it out like what how long should my word vector be should it be 300 elements or 5,000 elements like how do you tweak that right and these guys basically did showed some results with different hyper parameter settings to give you an intuition as to what the good starting values are and this was actually done for a lot of them deep learning algorithms so the point is that don't complain if you haven't read the literature because they actually how these people are helpful and and if you start with their settings and then tweak it based on your data said then you you can save yourself a lot of time so these guys for example did that forward to effect which is really really a big time saver there's paragraph 2 FAQ and dr. Vectis is implemented in Johnson there was this paper by Tomas Michael of encode clay from Google and this is actually really interesting because you can apply this notion to paragraphs or to hold documents if you do it at the word level then you get the semantic and syntactic relationship between that word in other words but if you do it at the document level then you're basically going back to latent semantic analysis or topic modeling but this this is just really for feature learning you know this called Queen and King and man and woman example is not really useful for everyday solving everyday business problem is just cute right but it's not really useful but if you use word Tyvek and apply it apply these weird vectors as features to your existing machine learning and natural language processing models then you can deal with morphological problems there was a paper about that there was of course this super famous paper by Richard soldier from last year about doing a very complex sentiment analysis that had several conflicting sentiments in one sentence and still getting the overall sentiment correctly there were papers about parsing semantics and even reasoning so so this this can be applied essentially to any NLP problem and the machine translation as well I I was hoping that I would be able to show the math but because I'm a lot of time you can actually look through the math it's basically just very simple calculus that derives how this hierarchical softmax works it's really simple actually unlike a lot of the machine learning algorithms that are really hard to understand so just to recap word vectors in deep learning aren't anything new they're just a natural progression understanding relationships to prior art actually helps you reuse word these word vectors in all your NLP problems that you have been already dealing with and just plugging into your existing systems and the real-world use cases ran the gamut of you know sentiment analysis and the identity recognition machine translation and so on so they're useful basically all over the place thank you and I hope I still have time for questions or do I not okay all right sorry so I catch me after I guess