Text By the Bay 2015: Malcolm Greaves, Relation Extraction using Distant Supervision and SVMs
good afternoon everybody so it's about four o'clock so I think you should let's get started here today I'm going to talk about the process of relation extraction and as a kind of subtext this is gonna be sort of motivated by this desire to automatically find facts so we can populate knowledge bases that we can use in our applications tomorrow my name is Malcolm Greaves I'm a research engineer at nitro we do some pretty cool stuff you should probably see all the nitro stuff everywhere you know you just grab somebody and ask him and you know see uh see what we're doing so first of all I could start with some kind of fundamental vocabulary I would first want to make sure we're really clear and what do we mean when I say a relation so relation is a semantic property that exists between two entities and identity is a thing with a distinct and independent existence this can range from people like Bill Murray superheroes concepts like music or ethics or something as mundane as a burrito and an example of relation is something like a person has a title so in this case the person wanted to know under McDonald has the title House Representative and these relations and entities exist in text for example here's a sentence that I pulled from a news article Juanita millander McDonald seven-year term house representative from Southern California died early Sunday of cancer she was 68 when we find these examples of relations or entities and text would calm a relation mention so from a programmatic kind of schematic I'll review relation extraction is the process of your input is unstructured text and your output is structured data so if you look at if you have a sentence like the one we had before on the output what we want is a fact like this person has this title you know we're you know most people here are engineers or programmers and lifts a scale up to Big Data so in a larger sense relation extraction lots of data is you have you know hundreds of millions of documents and you want to extract from those documents you know hundreds of millions of facts a so a knowledge base then is a organized collection of factual information James O Douglas is talking earlier about knowledge bases occurring over them this is the exact same kind of concept they're talking about here you can actually kind of think of this as a way to sort of populate your knowledge bases automatically the concepts of knowledge base can range from you know uh Turei abstract like philosophy to mundane and detailed like this like this is a specific form of long grain brown rice usually we express these facts as entities and relations between these entities an implementation of a knowledge base is a database so you can use you know graph databases are very popular kind of natural formation but a key value store works just as well I'm just gonna briefly go over some existing databases a wiki data is a great one from the Wikimedia Foundation another example is dbpedia Yago is another one which is stands for yet again a great or yet another great ontology it's kind of like that one freebase is an example of another knowledge base the know-it-all group from the University of Washington in Seattle does a lot this kind of work so does the reader web project at Carnegie Mellon University and Google's knowledge graph project is a example of a knowledge base which a little bit user and dive some more to the meat of the talk before I do that though I want to make sure I don't plagiarize myself a lot of this content is from my master's thesis that advised at Carnegie Mellon University so the new stuff that's kind of related to all this work is that I sort of rewrote this craze caffeinated a graduate student codebase that was a tangled mess of Bosch and Python Scala and random notes you have to do this before you do that and I rewrote most of it into a pure Scottish project that's working that you can use locally and you can also use on spark kind of very effortlessly and I want to point out you know the science and the architecture and the purpose all the stuff I'm going to talk about in the talk are the exact same but the implementation is new to focus on being of the scale the larger data this open source right is ongoing but it's made substantial progress and you can look at it at my github page it's called Rex for a relation extraction and I welcome any PRS you know love to continue and you know make this a you know one of the great relation attraction open-source projects out there so this is a want to now give an overview of this presentation I'm gonna talk about the process of distance supervision which is how we can make easily make training data to use in our relation attraction system let's talk about the pipeline at a high level some of the text processing things that we need to use in that and you know how we can use create feature vectors we can plug them into our machine learning algorithms but also going to talk about some experiments some conclusions from this experiments that I did in my master's research I want to point out already in the open source rewrite is sort of all the stuff in the middle the you know the process going from text to feature vectors you can use in your learning algorithms so let's start in the distance supervision process here the overall approach in machine learning is to we don't want to manually create extraction rules because it's a very complicated task and also you know we are people and we're not very good at doing tedious repetitive tasks so the idea is we're gonna have deterministic algorithms that'll track features from sentences and documents I'm going to feed these features into a learning algorithm well we'll give it an example of this is a good example of a relation this is not an example of not a relation and that's kind of how we're gonna go through this whole process you know we now we have a very first problem here where are we gonna get training data for let's assume you have a whole pipeline that can make these feature vectors how we can get training data and to get this I want to sort of get a little bit of intuition from kind of how we can approach this sort of problem so here's an example of a document you know at first we're talking about some multinational corporations from different countries and you know as we sort of read through this we're kind of wondering you know what is this what is what do we see here what are the kind of key sort of aspects that sort of pop out at us and if you look we can look at different sorts of noun phrases that are sort of interesting here you know we have multinationals United States Europe Asia New Delhi Bombay vehicles buses roads and so the idea here the question we want to ask ourselves is Kimmy somehow match these words to concepts that we already understand so that it can make it easier for us to make training data for detractors sir summarizing this idea but one is we want to be able to answer this question of Kimmy bootstrap from existing structured data sources to help us make this training data and this is exactly the idea of just in supervision so one hand you have these knowledge bases like wiki data dbpedia they have all these nice structured facts and we're going to use some very very simple sort of pattern matching to apply these facts to texts as we see them and we're going to use this process to create training data so let's go with an example here let's say we have a knowledge base that has an example of persons title so we have Jimmy Carter as a president and we're gonna look at the sentence President Jimmy Carter pardoned Jefferson Davis so we do very simple pattern matching and say well look President and Jimmy Carter appears in the sentence and so great that's an example of a positive example of Jimmy Carter being a president is in this sentence so want to make you know one way clear there's one of the assumptions the big assumption is the distance supervision if we have some sentence s and has two entities we identified their Q a and we have a record in our knowledge base for a relation R that exists between Q a then we're just going to assume that s is a positive example of this relation and entity pair um now there's some disagreement this is the best assumption you know for one example you could have a sentence that says you know Jimmy Carter is not a president and this simple very very simple rule would say yes that's a positive example for Jimmy Carter being a president president that's obviously wrong there's some alternate sumption sphere that can kind of get around that and you can base different distance supervisions algorithms off of that like one of them is you can assume that throughout all the text there's at least one example that has it instead of every single time you see it that's a positive example so just in supervision you can think of it as a mixture as a semi supervised learning algorithm our method it's a mixture of you have a mixture of labeled and unlabeled data or you have some access to knowledge we have you know Wikipedia info boxes wiki data dbpedia that we can use and the approaches we're gonna use these knowledge bases to heuristic ly generate label training data then plug in our supervisor algorithms and go so takeaway here is that to do this in labeling you need a knowledge base a heuristic labeling process that can have errors and this is different assumptions behind that process but importantly you don't they do any costly manual labeling you can use supervised learning algorithms at the end of the day and in practice it works pretty well so now I want to talk about the pipeline is for math 50,000 foot perspective there's two phases in this pipeline the first one is you want to make training data from documents and the second phase is you want to learn and evaluate different learning algorithms from this training data so in the first phase the the kind of idea is you have text processing we have candidate generation supervision then you have that feature ization the second phase you in this case we use support vector machines but you could use any supervised learning algorithm and then you evaluate the performance of these models on the hell that data set and see how well they do so this is a schematic overview the first phase so the input is you know have a whole corpus of documents you know or maybe you could use a smaller targeted set of those documents you get from a search maybe like a in this the research I did I'd use the blue scene but at any rate you have documents as you push into a text processing function this text processing function and feeds into a Kandak generation and distant labeling function which then flows into your future ization function which produces your training data just to kind of get a sense of the scale of this if you have a whole corpus right you might have millions of documents versus tens of thousands of documents in your search which will lead to having tens of millions of features if you have a whole corpus or millions of features if you have search and then the day you might have tens of millions of training examples that you could use so the second phase is a lot kind of simpler diagram it's just sort of you have your training day that you feed into sort of a loop where you just sort of in parallel can test many different sorts of learning algorithms tweak parameters and see how well they do evaluate it and output the performance so at the end of day you as a human can look at this and say well which you know a set of hyper parameters does the best job here so now I'll talk about the text processing stuff that kind of first stage and this I'm going to kind of go over a bunch of natural language processing methods and each one of them could be a whole talk or a whole course and I just want to kind of for each one of them give a quick intuition and you know explain the kind of implementation to be used in the source project so you know first if you look at this kind of first and foremost a document is just plain text as you store it we look at it so here's an example of a document is a big old block of text and there's a lot of questions we have we're trying to build a program that can understand this block of text such as where did the sentences start where the words are we gonna use whitespace to find words you know what about word classes are part of speech tags what about kind of coreference information where the pronouns refer to you know if I find he do I know exactly who he is so to summarize this is right we have a document that's plain text and we want to get more structure out of the document and to do this right we're gonna take our text feed it in our document processing engine and now we're gonna have an intermediate representation of that structure of this text and so I'm going to talk about these five different kinds of stages that we use tokenization part speech tagging and yard noun phrase chunking co-reference resolution and to do this we actually use the Great Library from Stanford Cornell P group and also the University of Arizona assistive project which is a scholar wrapper around this so let's go back to our little little short sentence here so tokenization is the process of you know a sentence like this and you want to turn into a sequence of individual words in the sentence so to do this tokenization will find sentence boundaries and group characters in the words and the tokens excuse me and you know in general tokenization is kind of a russell the easy problem is kind of considered solved in the Coronel P Coronel P uses a deterministic algorithm is a finite state automaton it's very efficient it's fast and you know overall it's a pretty good algorithm so going on now the part of speech tagging you know the question I want to want to get never his head's here is why do you even want it use part of speech and to illustrate this I found a little funny little kind of joke from a boy's Life magazine from 1930 as a wise old Scoutmaster and he's trying to give some advice to his younger scout and he says you know time flies this March Scout says you know you can't they go too fast how am I gonna time flies you know of course the smart Scouts thing well time is a verb here obviously right you want me to time the flies you know in this guy there's some ambiguity cuz the Scoutmaster is actually saying no no no time is a noun you know time flies by you know don't don't let time go too fast so you know this is just everything that I think people know right but there's a lot of ambiguity in language so part of speech tagging allows us to disambiguate word meanings and it does this by assigning different parts of speech to each token and in the Cornell P library the implementation is a probabilistic model it's a maximum entry model so it has this log-linear sort of parameterization which is nice because you can sort of plug in different features like any other linear algorithm and specifically the part of speech tagger has different local and kind of non-local features that are kind of handcrafted by linguists so that's another advantage of using linear models you can have people with domain knowledge put these features into your model that you could use so moving on from our speech tagging we want to talk about a little bit about named entity recognition so if we look at this sentence right we have a lot of questions regarding the entities that might occur in this sentence you know first off are there any entities in the sentence if there are what are the types of entities so they'd people are they things are they abstract concepts you know if they are if they are and here where are they where do they occur do they are they individual tokens do they span more than one token so and we know if we look at the sentence we won't ask a question okay well are there any tokens in here that refer to people or different person entities and so if you had an output of in any our system you would look at this and it would give you sort of a schematic where it assigns a certain entity tag to each token so in general right named entity recognition is allows you to identify entity mentions and texts from a list of predefined entity types it will assign a little label each token in your sequence with one of these I mean usually you also kind of consider you have like an other tag which is sort of I don't know what entity this is or maybe it's not vanity in Cornell PD implementation is also probabilistic it's a conditional random field which is a very good discriminate discriminative learning algorithm for doing structure prediction in this case sequence labeling has this graphical structure that's sort of nice that you can encode different features like linear features as well as different constraints like if you if you sign a tag that's a person and one insisted then you move on to the next token you don't want to assign you don't want to have you want to make sure that you sort of keep that previous token as a person you know when I have anything changing like that and so from this from named entity recognition I want to talk about a little bit about this idea of noun phrase chunking we're now sprays is a is a phrase of or a word that acts as some noun and so you know I want to point out why is this important at all if you have a word like New York and you just tokenize it naively you're going to correctly get two tokens new and york however this is not that useful from an entity kind of perspective because we know that New York should really be one whole chunk right it's sort of an atomic indivisible thing and this is where name that's due tagging comes in handy so most entities that were gonna be interested in are going to align with these names that to do tags or if they're not oftentimes they could be a single word like president so there's a very simple deterministic u rule that you can use to recover a lot of these sorts of to do this noun phrase chunking you can just sort of follow then named entity tags and ensure that they all have the same part of speech tag so if you ran an entity chunker on this on text that had New York you probably assign a location entity tag to new and New York and so you could say well that's pretty simple you can just merge those together so moving on what to talk about coreference resolution a little bit co-reference resolution allows you to answer the question who did what so here's a little story I made up it's pretty silly so John goes he went to the store he buy some milk he meets up with Jeffrey and Sally they have a two-percent party then after a while he goes home so if we're gonna look at the different kinds of you know people that occur in this you have John if he so you know yeah pretty sure he refers to John then you know he again refers to John and they met up with Jeffrey and Sally so they all have a two-percent party so we're pretty sure that you know everybody's having some fun drinking some milk and then after a while he goes home so this is this pretty ambiguous ambiguous because we want to ask yourself the question who goes home here is that John is it Jeffrey or reasonably certain that's not Sally because of the gender of the pronoun and in general you know this little story here just it illustrates that coreference resolution is hard because you really can't be certain who that pronoun at the end actually refers to so in general like coreference resolutions this process of linking entities with their mentions in texts so you know John goes to the store he bought some milk in Cornell P the implementation was rule-based so it's not probabilistic it's not machine learning has the sort of kind of course define ordering of different modules that incorporate lexical and semantic rules crafted by linguists you know in every sort of step they sort of iteratively refine the scope of which possible tokens code refer to other tokens and in general actually it works pretty well this is from a couple like 2011 they published a paper on this co-reference resolution engine it was doing a lot better than machine than the algorithm so go figure so that's all the sort of text processing stuff this is giving you nice structure you can use to make different algorithms from this text and important to this to relation extraction you need to be able to generate candidates that you can classify as belonging to a certain relation or not and this is the process of going from text to relation mentions so asked our schematic overview right for candidate generation input is your structured text representation and your output is your intermediate representation of these candidates where I'm going to define a candidate here as a pair of entities that exist in text I'm going to use the symbols Q and a to represent these these candidates might belong to some relation or they might not belong to some relation but the point of candidate generations you just want to develop you just want to produce things that might be in these two cat it might be a relation or might not be relation and let your learning algorithm decide whether or not they actually are the kind of baseline method that's used a lot for candidate generation is based upon the like naive distant supervision assumption which is if you have a sentence every single pair of noun phrases that occur in the sentence are going to be a possible candidate so if you go back to our president jimmy carter sentence right you're gonna have President Jimmy Carter as a possible noun phrase or possible candidate you have Jimmy Carter and Jefferson Davis you also can have Jefferson Davis and president so this problems with this basic kind of approach the first one that's kind of glaring is you can't generate pairs from documents so it's only sentence based and also as you can I saw it generates a lot of pairs but I want to focus a little bit on this first problem that you can't generate pairs from documents and this is problematic in a lot of cases so this format this problem as a question here how do we generate candidates for relation mentions from a whole document you know and it would be really nice if we could just build upon this simple sentence based idea so you can do this candidate generation for a whole document and the kind of interesting question here is you know what if you had an in from one sentence to another sentence so let's look at these two sentences I uh build these from a Wikipedia page on Bill Gates so the first sentence is gates originally established his reputation as the co-founder of Microsoft while at Microsoft he held the positions of chairman CEO and chief Software Architect so if we wanted to find out the different job titles that Bill Gates had we wouldn't be able to figure out that he was a chairman and CEO and a chief Software Architect because he doesn't actually mention if him does not occur in that second sentence directly but what is co-reference resolution give us it gives us this little link that gates and he are related to one another so you know what if we just did a little substitution and we had this sentence instead well if we did then we can just use this nice you know very simple sent single sentence can date generation method and we can get gates as a chairman gates as a CEO etc so the idea is that we can cross this sentence boundary by conceptually substituting a single word or a noun phrase across sentences so if we have a kind of formulate this more concretely if you have a candidate in a document where your candidate your first times use Q and your second exit a Q is going to be in a sentence called a sentence Q and a is gonna be in a sentence let's just call it sentence little a and there's two cases where we can use this co-reference idea to make candidate from a document the first case is that we have some other entity QF and sentence a so it's in the same sentence where big a is and we know from running our co-reference resolution that is co referent with q right and the other cases the mirror image of this there's a an entity a ref that's in sentence Q and we know this Co referent with a okay so that's this whole kind of idea that candidate generation idea using Co reference resolution so now I want to go into the feature ization process this is where you have candidates your intermediate representation of candidates and you want to generate nice feature vectors so you can use you know a whole host of learning algorithms so the motivating idea for the feature ization is you know let's not do anything fancy why don't we just use the text where the candidates come from and to this end so we're gonna do is we're gonna have if we have a candidate we're gonna take Engram surrounding each entity we're also going to take skip engrams that between for the the tokens are between both of these entities so here's a sense that I made up totally it's not real at all but it could it sounds kind of real so in a recent interview Obama talked about his plans after his term ends he said he would enjoy playing basketball spending time with his children and enjoying the company of Michelle the president's wife so if you look at our our entities entities here let's say that Obama's Q and Michelle is a there's a CO referent link between Obama and he so if you look at the Engram surrounding each Q a is going to be these tokens in red and the Skip engrams in between these Q a are going to be these words these tokens in blue so if you know these kind of cross sentence candidates you take whichever you you're gonna have one sentence where you're gonna have either a or Q and I'm gonna have a reference to the other one in that sentence so you look at that sentence that has a referent you just take the inside tokens between that referent and the other entity if you have a single sense it's easy canonical reference you just have those those two entities so I'm pretty sure a lot of people here know engrams are just want to give a quick overview so an Engram is a contiguous sequence of n2 you know oftentimes you want to admit punctuation and if you take this sentence you know insurgents killed an ongoing fighting the you know grams or one grams are going to be each individual token the by grams are going to be things like insurgents killed kill then trigrams are going to be insurgents killed in killed an ongoing etc and so skip and grams are like in grams but individual tokens can have at most K tokens that you kind of skip in between and the length though of the actual number of tokens you include in your skip Engram is exactly n so if we go back to this sentence all the one skip diagrams are going to include all the by grams because you can think as a generalization they're just skip and grams and skip equals zero you're to skip by grams are going to contain all your by grams all your ones get by grams and as well as you know things like insurgents ongoing because you're gonna skip killed in kill the fighting and you can generalize this to kind of any way any number of K or any number of n but in general they're a pretty good way to deal with data sparsity in a sense that you know they allow you to have to skip over certain tokens so that in that sense you can sort of capture a long longer distance information from a perspective of tokens if you had you know two entities are very far away and you wanted to kind of create features that capture the information and used engrams the higher your n is you're going to have you know an exponential increase the number of features you have and you know doing natural language processing we already have too many features so you want to make sure we kind of keep a lid on that beast excuse me so going don't out from feature ization we're sort of you know at the point now where we can you know learn revelation extractors and I want to kind of just a little point there about costs of we're learning I'm going to bring up in its in an interesting part that I kind of learned in this research we look back to where we're on the pipeline right we've just done all the first first stage and now we're at this point we have train data and we're gonna put it in this you know it's pretty standard train test and evaluate loop so when we're learning relation extractors this this comes up a lot in natural language processing and it certainly did when I was doing this research we have this really big class imbalance problems so a lot of times we'll have you know very very small number of positive examples for each relation and will be greatly outweighed three of those little less than symbols by the number of negative or just non related examples that we have I mean this is really this is a really really really big problem we have to ask ourselves questions that we need two good answers for like how should we construct our train data so we just use a standard cross-validation should we just do a random eighty twenty percent split and also when we do our learning how should we adjust our learning algorithm to account for this really really big bias in our dataset I'd answer the first question we're gonna use this idea of stratified cross-validation so just like cross-validation you have a number of folds so if you do three fold cross validation right you take your data you partition it into three different segments each one of those segments is has elements of the Train did it distribute uniformly and random and the difference is in stratified cross-validation you want to make sure that each partition is balanced so it hasn't the same proportion of positive to negative examples you know if you only have 28 positive examples and 1,000 negative examples and you just do a standard cross-validation it's it's likely that you might have a fold that only could have one or two positive examples and it's going to be pretty hard to learn when you only have two correct answers so we're now going to formulate relation extraction as a learning problem so this is a standard classification problem you're gonna have a relation candidate and your determine if it belongs to this one relation R so this is a binary classification problem and we're gonna have one classifier per relation so this is also known as like one versus all classification and this we're gonna use support vector machines we're gonna have a linear kernel I'm going to use a soft SVM formulation they're gonna be cost documented so I'm gonna use linear kernel because we're gonna have tens of millions of features and softness to them because this is not visited hard problems it's definitely not gonna be linearly separable and we're gonna use a cost Augmented a notion here because we're gonna try to counter the class and balance problem and so I want to focus a little bit on this cost Augmented idea and I'm gonna give everybody here a little largest margin based classifier crash course here's a little simple example we're gonna try to separate the filled in circles from the not filled in circles so we have a nice separating hyperplane here this black line W and it has a nice little margin around it I'm gonna fill in blue here and so we can see in this this the idea of support vector machines we're only gonna need a couple of data points that can help us define this margin so here we have a little filled in circle on one margin and two other sitacles in the other margin this is a hard formulation of so in the soft formulation we're gonna allow a few of these points to kind of infringe and invade this margin we're going to keep track of how much each one infringes with a little parameter I think it's ADA I think my Greek is really bad but you know this is the soft SVM formulation is an optimization problem the we have our hyperplane and we want to make sure that that's small we also want to make sure that the cost of making an incorrect classification for this is these these little guys are the little line that I have there so we have one for each one of the points and those are going to be nonzero if they're gonna actually be in this margin and so this is this cost documented formulation here right we have we have these two different cost parameters C plus and C minus and so we're gonna have a cost for misclassifying positively labeled examples and a separate cost for misclassifying negative examples and importantly you know since the overwhelming majority of the generated candidates don't have a relation label we want to make sure that we increase the positiveness classification cloth cost so the little C plus parameter we're going to make sure that that's high so that if the learning algorithm makes a mistake on a positive example we're gonna really punish it so now what I get in some of the experimental results that we have here that I actually went through so I just want to make a note that this is all from my master's thesis that I did so since the open source stuff is not toad ready at this point this is not that code but the code in architecture and everything is the exact same so the data that we use in this experiment as two sets one is a very large corpus of newswire articles so these across all these years a little almost 8 million sentences across almost 6 million documents and interestingly enough 78% of these documents were single sentence excuse me the other set of data that we have is this targeted search over this corpus using a different queries that I had from this this tack kbv challenge from 2012 so KBB is this knowledge-based population just kind of like academic sort of challenge to see the like hey let's push the city of the art of relation extraction and this data set there's almost 200,000 sentences across 10,000 documents and interestingly it was one difference is that only 4% of these documents have a single sentence so definitely bigger contrast to the corpus and so one idea here is that you know if we only had a sentence based candidate generation we might lose a lot of information and also so this is kind of a little tidbit so a lot of times there's sort of errors in the data about you know maybe sentences run on maybe your sentence or tokenization algorithm fails and it doesn't it fails to tokenize a certain sentence so it's a kind of heuristic we're just gonna ignore documents that have lots of sentences and and also going to nor sentences that are really really long so you have a 300 you know 300 token sentence that's probably an error or it's a run-on sentence and somebody should go punish the writer but so the relation says we're gonna use this from this challenge and there's about about a little bit less than 4,000 facts that we can use from the different assessments for the knowledge bases in this challenge so the different kind of relationship we have go from people to organizations to people to people so an example person a person might be this person has a sibling or this person might have a spouse people the locations and people the dates like this person was born on this day and we also have a similar set of relations from different organizations to people and different or Asians and locations and dates and you might notice that these lined up really well with our named entity tags that we have and that's a very good thing because this allow us to easily identify named entities in our text so just kind of give us more sense of some of the examples we actually use so an organization might have alternate names like the American Bar Association is also known as ABA the International Crisis Group is headquartered in Brussels Jennifer Dunn is an employee of IBM you know Irene kicked her kid daily is from gloutch Chester I get that right hopefully and to do a valuation on these we're going to use some standard metrics of precision recall an f1 yeah pretty sure people here are probably familiar with them but I just want to give a sort of intuition what these mean it's a precision you can think of as out of all candidate relations that your classifier said we're positive how many did you get correct we're recall is out of all the positive possible positive examples in your training data how many did you're learning out of them find and say we're true and f1 is a harmonic average of precision and recall and this is this sort of slightly skewed a little graphic here but you can think of this also in terms of set intersections and think of you know all the correct mentions you have and you intersect that set with all the extracted mentions you take the size of that set and divide it by the size of all the extracted mentions you'll get precision and similar idea for recall and f1 is then just a very simple you know multiplication and addition to calculate so the first experiment we use is this large-scale relation extraction across the entire corpus for this we use the 27 relations and there's about approximately 3 terabytes of text and we we all use the baseline sort of within sentence candidate generation method because I tried to run coreference resolution on this and it just didn't run is too much data so some results from this experiment are I'm going to show precision recall and half 1 micro average so this is you take of true positives and false positives for each relation and sum them all together to get this number versus micro average which is you take each precision and recall from each relation than average those numbers directly together so you know what we find here is that basically you know half the time when our when our we use this sort of setup when we say that a certain relation candidate is an example of half the time we're correcting we say that and a little bit less than 4/10 at the time we're able to find everything that's correct so if we look at this kind of breaking down by different relations it as I feared the text on the bottom is way too small but it goes from organization to date organizational location and it kind of goes right to people and sort of right where it says aggregate is where person to date starts so we can see that for things like person to location and person to like miscellaneous a different object we do we do really well but there's an interesting thing here that this data is kind of not show data is showing that we don't really do well uniformly across all these relations and you know part of the problem is is this kind of problem of not having enough labeled training data so at a lot of these cases I sort of dug into this and the problem is among our poorly performing we have some specific relations we will have only maybe 5 or 10 positive labeled examples and we'll have you know a thousand or five thousand negatively labeled examples who are training over so this is hard for any kind of learning out and overcome and actually a lot of these individual relations will have only had like maybe zero or two different positive label examples so it will end up with you'll have some relations that had zero percent precision right versus some that had ninety or a hundred percent precision so one of the kind of problems you if you're making a relation extraction system you have to make sure of course you have good training data but also have good coverage across in the second experiment this is a sort of is is a search right so we have actually a larger set of relations on there's approximately 10 gigabytes of text in this set since it's a little bit smaller we're gonna be able to run coreference resolution on this and we're gonna compare the different kind of candidate generation methods so one where we just run only the sentence based can a generation one we only run the document based candidate generation and a third one where we combine both methods so two high-level you know we can see that this is not performing as well as the other one it's not like you know we're not getting 50% precision on this set but we do see something interesting here so just the within sentence and just the document rules kind of based candidate generation are pretty competitive with it one another you know only to put like less than 2% difference in precision and recall even smaller difference in f1 but interestingly if we combine them both together we can do much better than either one of them and that kind of makes sense which is good right if you you know if you're generating cations from sentence there are some that you're gonna miss from documents and vice versa so you know it's at least promising that this idea kind of works well in practice so getting them to give a kind of sort of you know f1 is micro average f1 is plotted on the left and the different kinds of relation types of plot on the right and so that D here we see again you know we have the same problem but we don't have enough positive label examples that we have a lot of variation in here and actually to go so some of these for like if you see the really small one there above verses relation aggregate relation type just personal location you know we're doing pretty poorly we have about you know 11% micro average def one across those different relations that qualify for that but you know if you look at person to date we're doing really well you know we're up and around maybe like 55 percent f1 so again you know this this kind of method it can work well but you know one of the problems is that you have to make sure you have enough good label training data and that's kind of always a hard part or a task to do so to conclude the within sentence can take generation method is pretty good for large scale extraction it's very confrontational tractable it's very easy to parallelize you know you can have a job that runs on everything individual sentence and you know this kind of reaffirms an idea of big data that you know oftentimes civil methods can work pretty well but also you know this co-reference based candidate generation idea is pretty is pretty competitive with the baseline within sentence and but a problem is you know we're gonna as I said before we suffer from coverage so if we don't have enough training to positively positively label a training data we're gonna get a lot of variance and our results you know and also you know it's a good idea to build off of other good text processing libraries Stanford Cornell P is an excellent one you know you can use simple simple feature ization techniques is like emigrants skip engrams and nothing really new there but crucially you have to make sure if you use a learning algorithm has to be cost documented you have to make sure that you sort of you're learning out them knows about this class unbalanced problem this is a kind of a side I actually ran this the first time when I was a master's student I didn't have this cost Augmented learning I had a f-1 of 0.02 and I almost cried because I was like I'm not gonna graduate but then I thought a little parameter and I went back on my notes it's like oh you know maybe I could do this and I got a first round thing it got like that like 21% Mike reverse f1 and then I was like okay good I'm gonna make it and also you know there's this co-reference resolution based candidate generation method worked pretty well and it's you know it's a nice little interesting kind of combination of you know some standard text processing tools with you know a little bit of intuition you know together you know you can use these kind of methods to make pretty you know competitive state of the art relation extraction system you know the little caveat this is back in you know May of 2014 you know I think I am sure things got better since then but that is everything and I'd like to open up the questions I know I'm basically at the end here but you can maybe grab me later thank you very much