Text By the Bay 2015: Mike Tamir, Classifying Text without (many) Labels
Recording: Text By the Bay 2015: Mike Tamir, Classifying Text without (many) Labels
hello everyone welcome to uh galvaniz campus my name is Mike Tamir I actually um I run data Science Education and products here at galvaniz um what I'm going to talk to talk about today is efficient text classification with word Toc um this is coming out of some Project work that I did with personagraph on app text classification and web web page text classification um so I want to thank uh my partners at personagraph for providing the data and for uh working uh working on this project with us all right so what I'm going to go through today quick outline we're going to uh go through the basics of text classification what are the challenges what are the basic problems um some deep learning applica applications for text classification how to deal with the um the data challenges uh using Doc in particular using doc uh viewed under the opes of a um a compression algorithm uh benchmarking uh for different label sparsity and imbalance problems in particular against bag of words um and then talking a little bit about how these um experimental results impact uh out of sample um out of sample uh uh performance uh with drve engineering and then we will go through the conclusions so just a quick overview of you know what is the supervised Paradigm for document classification um you know you start with your standard pre-processing you do your stemming your uh punctuation um you alter capitalization there there are libraries out there that will do this that will not uh not reduce the a in apple when it's uh when it's the proper name Apple because that's confused with the fruit um then you go in through your feature engineering there is a whole grab bag of options that we can do here PCA sparcity filtering tfidf is a very popular one um transforming scaling uh turning into bag of words look at context uh the list goes on uh then you do your model training based on how the model training works you go into a loop uh with your feature selection regularizing feature importance uh looking at correlation modeling Etc um and then ultimately hopefully you have a very strong classifier the unsupervised case is a little bit simpler you uh don't have the option of checking and iterating on your results so it tends to fall under the you know the standards are LDA and document clustering um without much guidance or supervised the target features to uh help guide whether or not your clustering has been successful and um whether or not you're um whether or not you have something that you want to bring to Market market for performance um what are the major challenges uh in document classification is the data so number one your data quality usually has these standard challenges of the shape of the feature Matrix right you're usually going to have very wide U matrices um compared to how deep they are um you know data uh vocabularies even small ones are going to be order of the tens of thousands and so you need quite a quite a large number of uh examples for that that uh vocabulary if you're going to use just raw bag of words or um terms in the uh as your feature space uh so the shape is wrong so to speak is how we we look at it uh this deal this uh affects cursive dimensionality in particular because uh you're dealing with now a 50,000 say um feature uh uh Vector space and um that means you're going to need you know powers of that in order to really be able to CH to to fight the cursor dimensionality you also have data sparsity and what I mean here is that it's um not every document is going to have even a fraction of the total number of terms in your vocabulary so you deal with a bunch of zeros and then only a couple ones in in your rows and that's going to have all the effects and challenges that you see when you're dealing with a sparse feature set sparse data points in your feature set um and then there's lack of training example this is when you're in the supervised case if you want to um to train for uh nodes in your taxonomy that are you know let's say you have a taxonomy that's hundreds or thousands of nodes wide that means you're going to need training examples for each of those nodes in a supervised context at least in a traditional um applications and that could be very challenging usually you don't have that there are some open- Source uh data sets uh deos and Reuters but uh it can be very difficult to to get um enough training examples for every one of the um for every one of the uh the the nodes every one of the taxonomy class uh uh features that you want to sorry Target features that you want to uh classify for and then the last thing is uh just like you're going to have only a sparsity on the number of terms that exist in each document uh out of the whole vocabulary you're also going to have an imbalance in your data set itself you're going to have far fewer positive examples for any particular uh topic than you are going to have negative examples so you're going to have to deal with uh with this imbalanced data set do a lot of the challenges that that come from doing a super supervised learning uh Paradigm when you're doing this this supervised this imbalanced uh data set so let's talk about uh deep learning for a moment um I'm going to go through one example uh I know um Adam Gibson gave a gave a great talk earlier today on or was maybe it was yesterday actually um on uh on on deep learning so I'm not going to go into this too much but I'm going to be talking about word Toc as a kind of compression algorithm so I just want to go quickly through what Auto encoding is as a compression algorithm and why um how we can compare and contrast what's going on here versus WTOC so Auto encoding the simplest kind of autoencoder uh has this shape you have your input features X you squeeze it through the keyhole you have some sort of Matrix W it's going to be M byn where um where where um the N is less than n and then that's going to squeeze it down to this next feature set y um and then you reverse that process you uh you do a WT so that's a transpose it's going to reverse that process and get you through Z Now what's going to happen here is then you check how much of the information were you able to so to speak squeeze through the keyhole by mapping X down to Y and then back up to Z um and this is just going to be pick your favorite loss for how much you want for how you want to measure what would count as information loss going from the beginning of the process to the end of the process and you optimize for that you tune just like you would tune many neural network uh with back propagation uh now I guess a little over a decade ago um uh uh Jeffrey Hinton came up with a great idea that well we'd like to make this deeper we'd like to be able to squeeze it more um so why worry about all the problems of having many many layers all at once we're going to do the trick that we're going to clamp these outside W's and now we're going to do the process again but instead so we have that first W uh at stage one clamped and so also you have uh W uh W1 inverse clamped and now we do the whole process again and now we're really essentially just doing a three- layer um three layer tuning again for uh W2 and W2 uh transpose so you can iterate this process over and over and over again to get 2 n+ one different layers squeeze it through a keyhole y as small as you your heart desires and then you can just train it in order to make sure that you don't have too much loss in your compression when you're done you don't have to keep the right hand side of that bow tie shape you toss it you have you compress it down to the smallest uh layer that you want and then you feed it through your preferred algorithm this can be just another layer of tuning as an ear net it could you could throw it into you know pick your favorite classifier random Forest logistic progression gbms and and you have essentially a feature engineering where you've compressed High Dimensions down to low Dimensions that now hopefully ideally when things go well your classifier can bite into and can get can find the grooves in the data um so yeah you can find tune with back propop what are the downsides of this number one it can be very unstable uh number two it can be difficult to implement number three uh the cost scales with the order of the taxonomy node count and what this means is that it's going to be very very costly if you have tens of thousand or if you have if you have hundreds or thousands of different uh taxonomies that you want to compress for you've got to repeat this entire process without any uh savings every single time you do it so this suggests using a different method and that's why I'm going to talk about word to VC um continuous Vector representations for individual terms what that means is we take our um projection of each term so that's all zeros and then a one uh it's a say if your vocabulary size is 50,000 it's a 50,000 long Vector with a one in exactly one space each different term maps to a vector um a a b a axis Vector so to speak uh that is orthogonal from all the other axis vectors all the other words um and this is very long but uh what we're doing here is we're going to take a step to compress from say if we have 50,000 words down to usually on the order of 50 to a to a few hundred um dimensional Vector space this is a diagram of the actual algorithm word Toc actually came out as sort of a side effect of um a side effect of doing a skip gram or an engram uh model for you using neuron Nets so real quickly I'm going to walk us through this diagram we take our terms so this is I think the Constitution or something we take our terms we take the first uh J terms or um sorry the first n terms um and you get in this blue here um you map them with the projection uh mapping to each of these terms then you stack them together so if we have three terms and we have a 50,000 word vocabulary this is a 150,000 word long or 550,000 Dimension long Vector we then create a um a a matrix uh the word Toc Matrix that projects that um or squeezes that that um that Vector down to usually a few hundred long Vector which is the word to V embedding you didn't run it through a um an an activation function something that is nonlinear um and then you add in uh usually a accent um or um classifier out here to get a probability for WJ which is the jth word the next word that you expect to be so you see uh Jack and Jill ran up the blank this algorithm is trained to guess Hill most likely more likely than any other term in the vocabulary and um if you train it over over and over again with enough uh enough examples of text it will learn to do this pretty decent accuracy now um the fact that we are using this as a skip gram or an engram model skip gram is the same thing instead of saying Jack and Jill went up the blank it's Jack and blank went up the hill um the uh you know that's not really the the uh the you know warc is a side effect of that it's a very valuable side effect though because what we've done is we've compressed this High dimensional feature space down to a few hundred features and the few hundred features actually do more than just um give us a small dimensionality to work with it actually encapsulate or captures the structure that you see between different terms based on the frequency with which they come together so um this is a gif thanks to There's the link um it's a really good one though um so uh one of the classic or very uh uh you know nice examples of how this structure between our terms is captured is you know when we go into a vector space especially a vector space that's not just made up of the axes terms we have all this structure in Vector space we can add them we can subtract them we can scale them we can shrink them uh we can rotate vectors and all of this structure actually can get encoded in the algebraic structure of the terms as when they get embedded into the vector space so we have a king plus man minus woman so in other words what's a king plus the difference between a man and a woman you can yell it out Queen that's right it's a good guess and that's uh that's exactly right um so um so there's the difference between man and woman there's a difference between king and queen we look at the difference Vector there we take the king Vector we add the man minus woman vector and we get Epsilon close to the queen Vector um this is something that you actually see over and over again there is a set direction for with the word to V uh mapping and now we're just going to add them up to get the document vector and of course the document Vector is going to be much longer and I include a couple more words uh when we're doing um when we're doing uh uh the the the best of times worst of times but uh it's very uh you know you can do this you normalize it and then you get a a vector that's ostensibly pointing in the direction in this 300 dimensional Vector space uh that the that the word that the document tends to point in so to speak um so this aggregate Vector actually ends up the as as you add these terms over and over and over again most of the terms are just going to be kind of noise it's going to cancel out it's going to be kind of like a random walk but it's a random walk with drift and that drift is actually going to take the sum Vector the a aggregate Vector in the direction that the actual entire text the entire book maybe uh is pointing in and then so all the other things all that that go that go along with um you know with the random walk end up getting canceled out but in aggregate you end up getting this uh this total total topic uh Direction pointing so we might say oh this this book uh you is about tale two cities is about class struggle we take the vector we normalize it and it turns out that we are Epsilon close uh in the neighborhood of the vector class struggle um and now you can you can measure it in a lot of different ways taking the average is simple simple way you could take the cosine between the two uh whatever you want in order to see uh how close is this drift Vector to the taxonomy node or taxonomy directions that you do and another nice byproduct of WTOC is not only can you embed entire words you can sorry entire documents by taking these linear combinations you can also embed individual terms like the tonomy terms and compare them on an equal footing because you've embedded them into that Vector space as well all right so uh just another quick diagram you're going to take the word Toc um Matrix those of you who are paying really good attention uh word is actually uh in this [Music] diagram in this diagram actually we have like you know in this case three of these word Toc uh matrices stacked on top of each other because we're embedding three terms uh but then you can chop it if you have three an NR you can have n n word to grab word to VC uh matrices you stack them and uh or or you daack them and average them to get this uh this individual embedding V uh embedding Matrix um then you can use whatever classifier you want random fars gbms whatever it is that logistic regression whatever it is that that is your favorite or seems to be performing best um and you get your uh your classification whether or not it falls in that um in that term or sorry in that that uh class class or not it turns out that the dominant feature usually in these embeddings is proximity to the um the taxonomy term that you're actually talking about uh which is unsurprising and actually very beneficial um so what are some of the benefits uh Spar vectors are end up being made dense training time is restricted to the output layer only so it's only you instead of retraining and re autoencoding every single time the word Toc happens once no matter so it doesn't have to scale with the number of taxonomy nodes that you have um there's no expensive hyperparameter search uh in tuning this or sorry doing the fine-tuning and it's more effective in using sparse labels how much more effective this is a good graph of that um if you look on the x axis that's the number of positive training examples we have we are talking about dozens to hundreds here so incredibly incredibly SM small you even have deos data set uh number of positive examples at this order of magnitude um and then comparing it just a bag of words this is the percent across all of the taxonomy um that that in this use case we were using uh that were accurately um classified so it dominates all across the board all right another big value to this procedure is dealing with imbalanced text problems uh like as I said usually you have way more positive sorry way more negative examples than positive examples um um so this is an example with C Class struggle uh if you have one in 10,000 of your terms is um or sorry of your documents is a class struggle document uh and the model has say 95% uh Precision on a balanced test set then for every one true positive you're going to you're still going to have a 05 uh or 500 false positives of your total document Set uh which means your Precision gets knocked to 0 2% um this is something that happens even if you use traditional best practices with down sampling Etc um so because the imbalance of real model performance can be far worse than estimation based on balance testing re thresholding can help these models but now you have to figure out where to re threshold and that's something that um that if you're using a lot of features in your feature space if you're using a lot large volume feature is going to be very difficult to detect um this is just another way of saying that we have an uh an over problem um so just to make this very uh very uh um visual uh to illustrate what the point here is um we have on the left side a bag of words classic bag of words feature engineering with 300 features the top 300 most uh predictive features and now here we have with 10 features um how we read this graph the greens are the negatives the purples are the positives and these are the scores um that that we're getting so uh or sorry the amount that are that we are it's a hist of the ones that get that score so um you see maybe over so over here we have a histogram we have you know five or six examples that are getting or 80% uh score likelihood for a backwards classifier um so what that means is that we we have that's a true positive case but all these purples on the left side those are are um false negatives and the greens on the right side are false positives when we try to um feature select and find just our best terms maybe our top 10 it actually gets much worse um and you see that you've got with this um with this feature engineering you've got a lot of uh false negatives on the on the left hand side and the false positives Trail off to the right hand side the f1s are not so great either the it takes a significant hit from 0.93 to uh 0885 if you do it just with bag of sorry just with uh feature engineering on this bag of WS um you immediately get better results um first of all the hit to the F1 score is far smaller uh less than 02 um you also get that um the separation so you're already getting very good separation there there's a little bit of overlap in the uh 4 to0 five range um but when you knock it down there's a clear cutof Point here at the0 five a little bit higher than 05 range and this is something that gets this is an example of something that a phenomenon that you see over and over again with every taxonomy um so now it becomes very easy you just fit the distribution you look at the overlap for the um for where the these these have a kind of a beta distribution shape to them and then you chop it right there um so you get this unambiguous thresholding between the positive and the negative cases you get a confident semi-supervised estimate of the imbalance ratio so even though uh you only have maybe dozens to 100 examples that's really all it takes in order to be able to separate between the positives and negatives assuming that the imbalance ratios are not themselves very highly unrepresentative um and this is just an example with h songs of an actual distribution that you that you'll see across the entire taxonomy so in conclusion um pretaining word to VEC uh provides a low investment uh entry into deep text classification by circumventing the pre-training phrase uh that you would get with actual deep uh deep learning um text text classification or compress algorithms like uh uh D noising Auto encoders or rbms um results are competitive in the F1 for highly optimized w a bag of words and they severely dominate when you have small training sets and also when you have imbalanced training sets so uh feature selection and well uh feature and uh feature engineering for word Toc features avoids the wash out effects when you have these severely imbalanced one in 10,000 examples in your training features uh and it requires far less in investment in the training examples for the boundary cases last but not least um it enables more efficient scaling for large space of uh of text classifications taxonomy so in for business uses um you know often you need hundreds if not thousands of different taxonomy nodes and this is something that can be prohibitive if you need to do the investment of traditional text classification for every single one of those nodes so thank you very much uh and happy to take questions