Bay Area AI: From Logic to English via Chart Parsing, Darryl McAdams

Bay Area AI: From Logic to English via Chart Parsing, Darryl McAdams

Recording: Bay Area AI: From Logic to English via Chart Parsing, Darryl McAdams

so if you want to follow along on the with the slides on your computer on your phone or whatever that's where they are ok so the slides are there this is going to be a slightly more technical talk so the slides are there so that you can pause on your own and you know check stuff in case it's not clear or in case I'm going too fast or whatever so this talk is not going to be at all about any sort of machine learning stuff though it would be interesting to see how machine learning techniques could be applied to this I imagine that there are some fun ways so real quick that's me in case you're curious but I'm not going to tell you anything about me I'm just going to tell you about this this is kind of an old-school technique for generating natural language sentences from logical inputs for from logical representations of meeting it's very popular these days to use fancy fancy versions of what ultimately are finite state machines only instead you do it with you know neural representations and you call it deep learning and it's much more magical that way this is a very different sort of technique this talk is not going to be about implementations so I'm not going to show you any code I'm not going to show you how to actually build this stuff because you know if your favorite language is Haskell like it is like Haskell's my favorite language your implementations are going to be very different than if you're writing this in Java or something like this and I want to force you to think about this in one particular way this is just going to be about the high level design of these kinds of algorithms ok at any point if you have any questions please stop and ask me especially if they're clarification questions because no guarantees that anything I say here is going to make any sense immediately ok so let's talk about some tricky aspects of generating natural languages or natural language sentences so one issue is that you know given any particular meaning there could be many different ways of representing this so for example you know you could say Brutus stab Caesar you could also say Caesar was stabbed by Brutus and these basically mean the same thing or you could say Caesar died in Rome during the Ides of March or Caesar died during the Ides of March and Rome still the same basic thing or the tall man stab Caesar or the man that is tall stab Caesar and so there is this kind of non-determinism in how meanings map two sentences there's also this problem of locality which is discontinuous parts of meaning can map to contiguous parts of the expression that you're generating so for example quantification can wrap around the rest of the meaning of your sentence so for example Brutus stabbed someone well what it really means is something like you know for someone x Brutus was that Brutus stabbed X all right so you can see that the the meaning of someone sort of corresponds to something that is around the meaning of the brutish stabbed part right this is kind of very weird it's not as if you know you have a meaning here and it's part of a bigger meaning therefore the meaning here must also be part of the bigger meaning the meaning is can sort of interleave in very strange ways also you get things like tents where meanings the meaning of something like Brutus stab Caesar you know you have this little morpheme that's past tense but actually what you're really saying is here's a whole thing that's past tense Brutus stab Caesar and so the meanings are in this sort of weird inside-out fashion so these are these pose some tricky problems for generating if we were just generating things where the meanings of the parts combine to form the meanings of the whole in very obvious straightforward part-whole ways then it would be much easier so what we're going to do is we're going to the problem not going to tell you initially about natural language because natural language is big and hairy and nasty I'm going to tell you about a slightly simplified kind of language in particular we're going to talk about arithmetic expressions very simple ones there's going to be two versions but for the first one to talk about to talk about non determinism we're just going to have this incredibly simple language where the meanings consist of the predicate plus or the the let's say the function plus apply to some numbers one two and three and however many you want okay this is just a nice simple toy language that helps to clarify the ideas and so the sentences that we're going to generate are defined by this kind of grammar and in particular we're going to generate things that just look like normal arithmetic expressions with plus ok unfortunately that representation is not so useful that's an abstract syntax tree and so instead what we're going to use bum so let's see why this is not very useful in this particular kind of meaning representation we have we don't have the ability to really express that the meaning of 1 plus 2 is the same as the meaning of 2 plus 1 right without adding some laws about commutativity of addition or whatever ok maybe that's something that we want to actually not incorporate in our grammar but in this case we are going to say that the meaning of 1 plus 2 in the meaning of two plus one should in fact be the same ok and additionally you know the meaning of 1 + 2 + 3 should be the same as the meaning of 1 + 2 + 3 again this is just for the example to help illustrate the NAM non-determinism so instead what we're going to do is we're going to use abstracts and text graphs instead of abstracts and syntax trees will use graphs and this should be a relatively easy transition to make because after all trees are a special kind of graph so instead of plus 12 we're going to have an edge and no label to graph this nasty bit here or hopefully it's more easy to read this so we're going to have three nodes p a that should be be down there sorry this one I'm trying to get the shadow work and so p is the plus node and that corresponds to the entire expression the a node corresponds to the one sub tree and the B node which is mislabeled as a here corresponds to the two sub tree and a is the argument of B of p and b is the argument of p all right this is just a relatively simple translation of the abstract syntax tree into a graph like representation okay is that sorry say that again so this is a tree yeah this differs from it only in how we're sort of representing the information and the representational difference is actually going to be very important if we represented this as an actual tree like a tree data structure what ends up happening is we're preserving this hierarchical structure whereas representing it as a graph sort of flattens out all the structure so the structure is there implicitly because of the edges but now everything is sort of on equal terms there is no top or inside and outside it's all flat right right this is just a graph right so because we're just using argh this makes it manifestly clear that the meaning of one plus two should be the same as 2 plus 1 right it's manifestly the same thing they're the exact same graph and if we have multiple arguments well we'll just have more edges labeled argh pointing to more nodes okay and so again it makes it manifestly clear that the meanings of multiple things are going to be the same despite the the ordering of the parentheses and also it makes it clear that the meaning of 1 plus 2 is a part of the meaning of the whole in a very easy way right it's just a sub graph in this case so let's talk about how we can use these to generate so I I said this is chart generation this is a slightly different kind of chart generation than you might find if you are looking for chart parsing it's the same it's its generation as chart parsing but the charts are slightly different so let me tell you what the charts here are going to consist of charts are just a bunch of nodes a bunch of edges and a chart over a node an edge labeled graph G is just a set of charred edges where a chart edge is either a terminal edge which consists of just a single node or edge in that original graph or consists of non terminal edges which are sub graphs together with a focal node in that sub graph a syntactic category because remember we are generating to some kind of relative to some kind of grammar and whatever the output of the generation for that part of the of the graph is ok so the whole graph G constitutes an initial chart because well it does have a bunch of terminal edges all right it just doesn't have anything bigger that corresponds to the meanings of larger parts of the graph it just has the meanings of the little the small parts of the graph so in particular here is an example chart this is not a full chart this is just an example so you can see we have all of the original edges from the graph but then we also have some other non terminal edges so for instance one a can form a non-terminal edge with a is its root node or a is its focal mode the kind of expression that it is is the e all right let's let me go back a little bit to the grammar so that you can see right X expressions II can be ones twos threes etc and the output of the generation for that part is just one similarly for the node be the output for that would be maybe two and for this big sub graph in orange we can have two different non terminal node non terminal edges in this chart namely the edge that has p as its focal node it's an expression and the output of generating that little part would be 1 plus 2 an alternatively we could also generate two plus one for that part okay now I haven't told you yet how we're going to actually generate those this is just an idea of what the graph would look like okay of what the chart would look like for this graph okay any questions about this peony right okay so the the first element of this triple is just the focal node for this non terminal chart edge and E is just the syntactic category that that this is right so in this case we're generating an expression e according to that little arithmetic expression grammar earlier and so we want to know it is in fact an expression rather than a number or something else like that right and the output of generating that sub graph is one plus two maybe or two plus one depending on which choice we make there was a question back there yet charts can be seen as a kind of graph what sorry the question was what's the difference between charts and graphs how was asking yeah yet chart in this case is just a particular kind of data structure that's relevant for chart parsing you could implement it as a graph it's useful I think to just keep them conceptually different with your to keep them conceptually different because a chart in this concept and in this context serves a role in the generation or parsing process okay so the the chart here is just going to be a bunch of information about sub graphs and how they can be generated in to textual representations or parse trees or whatever okay so that's an example of a chart with some but not necessarily all of the non-terminal chart edges that we would use during that we would produce during generation this is just one chart so this chart includes many many edges it includes all of the black edges right the node the nodes and the the chart and the graph edges underneath it those are individual charred edges but also these color ones correspond to non terminal edges they're sort of phrases in a sense right whereas the the individual so this and this would be terminal edges that corresponds to labeled nodes and this is a terminal edge that corresponds to a labeled edge in the original graph and that original graph is the meaning so what we're doing is we're laying on this extra information that represents how parts of the meaning relate to parts of the sentence that has that meaning right so this part of the meaning corresponds to this part of the sentence or the the arithmetic expression again okay so in order to parse you need some grammar rules right because well that's what parsing is you take a grammar in some input and you produce some some parse output yes there's a question here SG over yes so these so these are just toy examples you wouldn't you probably wouldn't actually want to do this sort of thing with plus this is just a toy example to simplify because if i gave you example with natural language then i have to tell you a whole lot more than just the techniques that are relevant what this buys you though over adjust the abstract syntax trees is that you can look at parts of the graph without having to basically dig down into a tree find things that are non local and then wrap those up so we'll see perhaps the perhaps the the second example will make it even clearer mmm I don't want to say that but look with it it's okay let me tell you now what the what the parse rules are going to be rule is either a lexical rule that takes some graph some sub graph pattern and produces a chart edge from that or it's a phrasal rule which takes a sub graph pattern but also some other chart edges and produces a chart edge all right so I call these lexical rules because they're basically making words right they don't have any sort of sub phrases and then the phrasal rules take things that have already been produced and combine them together into larger pieces okay so for example this is an example of a parsing rule okay we can take a node X whatever that note is doesn't matter it's a pattern all right a node X that's labeled one and we could add an edge to the graph that is focused at X has the type has the syntactic category ii it's an expression and has the generation output one right that's what we we would expect that you know the meaning one should map to on the output when we generate some arithmetic expression and so here's what that looks like applied to a chart we start with a chart we pick X to be a and we apply this rule and we get this new edge that has a as the focal node he is the syntactic category and the output is one another kind another kind of parsing role is the phrasal rules and so this says if we have some part of the graph that has that says that p is a plus and that x is an rfp and y is an RFP and also we've generated some stuff for x and y right we've generated some representations we can add a new edge that represents p as just L plus our right we have the representation of the left part and the representation of the right part and we can put those together with the plus and make a representation for the whole thing okay and so here's how we might apply that to a partial graph we let's say we already have this and this well so we know that if we pick P to be little p x to be a and y tu bebe well we know that little p is a plus according to this chart we know that a is an rdp and b is an argue p okay so the first three pieces are there and we also have these these partial generations for the sub pieces and so we can add a new edge that says oh well guess what I can represent that whole thing as 1 plus 2 okay any questions about that so one thing you might sort of wonder is well is it okay to like reuse parts of the graph especially the edges because we wouldn't want to take this and this and combine them to produce one plus two plus two plus three that's not the right thing right because now we're adding things together too many times so in this case well we probably don't want to use we probably don't want to reuse parts of the graph ok so in certain contexts such as this it might make sense to say that any time we combine two edges they have to have completely non overlapping sub graphs that they're associated with ok for natural language this might not be true or it might be it depends that's something that you'd have to look at so what we've done here is we've basically generated some outputs just by applying parse rules to a graph rather than to a string as input ok and the way that we did this or the way that we would do this fully because really i just gave you some some rough ideas of how to do this with the parse rules in the graph the way you do this fully is you keep applying rules until there's nothing left to add and then at the end if you have some charred edge that is sufficiently large and has the right category in this case the category is east since we were generating arithmetic expressions then you successfully parsed the graph input you successfully generated something ok in this particular case what i mean by sufficiently large is that it covers the whole graph more or less right so all of the meaning that you put in is relevant to your output and the reason i say more or less is we'll see later there might be some cases where that's not entirely true ok so let's talk about nonlocality hopefully this will answer the question regarding why not just use trees you might be able to use trees but this is a different take on this so in this case we're going to use a simplified language that is instead of you know pluses and numbers we're going to have two kinds of meanings we're going to have an atomic proposition that says some number is less than some other number and these numbers can be variables or they can be number literals and we'll also have some kind of quantified expression in particular there exists an X in some specified set of numbers such that some proposition holds hanging that proposition of course can use the variable from the quantifier so for example 1 is less than three perfectly good proposition there exists some X in one and three such that two is lex less than it that's another perfectly good proposition and a third example would be there is there's an X in 1 and 3 and the y into and for such that X is less than Y and it's also a perfectly good proposition those are the meanings and so the kinds of things that we will generate with these will look kind of similar in particular we'll have numbers and we'll also have so we'll have numbers and then we'll also have statements about less than stuff right about ordering but we're going to add this sort of weird kind of number here it's really strange right and what this means what this means basically is this means one of these numbers right and that will give a sentences like this one is less than 2 2 is less than some elements of 1 and 3 and some elements of 1 and 3 is less than some elements of two and four okay so these are the sentences that corresponds to those meetings okay this is very similar to stuff that happens in natural language so let's look at the ASDs for this we will represent numbers the same variables that occur in these sorts of propositions will just be nodes that happen to be tagged as being variables and we'll just keep the name on there as a subscript just as like a little parameter of the of the label because you know you never know you might want to go back from your graph representation from your to your tree representation and so it's good to keep that information around but and propositions of the forum for example 1 is less than X will just become little graphs like that so that's basically the same stuff as before right this should not be enormously different but quantified propositions we have to do something interesting so what we'll do is we'll have a new new kind of label exists sub s we'll just store the set the range that the quantification quantifies over and we'll also have two new kinds of edges scope QP which says that the scope of the quantification is some other proposition rooted at P and we'll also say that Q binds be just to let us know which variable is being bound by that quantifier okay so for example oh yeah note by the way that the numbers from the quantifier the set that we're ranging over restoring those in the in the node so for example there exists an X in one and three such that 2 is less than that number will correspond to this kind of breath okay we have this is the the correspondence of two this is the correspondence of X this part corresponds to this part of the meeting and then the quantifier just has a node for the whole quantification and then it says what the scope is namely this part here and also what variable were binding ok any questions about that no question it's okay so this will hopefully make it easy to see why you want to use grass instead of trees because there is a direct connection between the thing being bound the variable here and the quantifier that is on the same footing as all of the other relationships between parts of the meaning right there's no there's no special relationship here whereas for this kind of meaning to know that this is bound by that particular quantifier you have to look over like the whole tree right and digging around inside trees is kind of not fun okay so let's generate some sentences from this so we'll have rules that are exactly the same kinds of rules as before okay so for example if X is a 1 then just maps the one or if we have a less than thing and it maps to a less than its standard stuff is from before the interesting stuff comes from quantification now okay so here what we're going to say is if we have a quantifier node q that binds a variable X will add a new edge to the graph that's focused on X not on cue it's focused on X and it has the type ends the number and the way that we represent it is some s where s is just whatever those numbers were that we had before okay and so what's happening here right is we have some stuff like the quantifier that would have been really far outside of where the variable is it's all the way on the outside of the of the meaning but we're using it to represent the variable that it binds which is going to show up on the inside of the meeting and so for something like this proposition which corresponds to this graph when we parse we'll add in a representation for this by using one of the parse rules will add in a representation for this which is our rule for the quantifier right and here we're representing a queer representing be as just this some elements of 12 of 13 and then we'll apply this rule that says look if you have a less than such that one of the args is represented by L namely to and the other arg is represented by our namely now the other arg is be and it is represented by some 13 then you can add an edge that says l is less than R right namely l is less than R okay this is kind of strange from a normal pretty printing perspective right if you think about generating some sentences pretty printing this is a little bit weird right because we have like this inside part that actually represents something that wraps around it and it's kind of strange but because we have a graph there is no sort of notion of inside and outside they're just all sort of flat and they're just where parts are related to one another by these edges okay now you might be wondering well what the hell happened to scope right because I said earlier that you know we're done parsing if we've got an edge that covers the whole graph and we haven't used scope at all right well scope here is really not relevant for generating at least in when we're talking about natural language right because if we're going to be stuffing these quantifiers down into the position of arguments like this is this is an argument of the of the predicate right so if we're going to be stuffing these quantified expressions down into the argument physicians we don't actually care where the scope is so you know what we can just like pre-process that out of existence you know turn it turn our meanings into these graphs get rid of the stuff that actually doesn't matter for the outputs of the generation and now hey presto we have a sub graph that is in fact the whole graph and it generates something so it's fine okay so now what about natural language because that was not natural language well natural language meanings are usually represented like this if you go and you know look up a semantics book or something like that but over the history of semantics a number of developments have taken place so one of them was that Davidson said let's introduce event variables will have variables that represent you know the event of doing something not just we won't just have predicates will actually think about like things taking places being their own variables and then cast Anita came along and said what if like what if we actually separate out the arguments into their own little predicates right so we don't just have stabbed ebru to sex we'll have stabby and also the subject of e by the way that was Brutus and the object by the way that was X this is looking a little bit more like the graphs that we had there have been various other proposals that pull out things like proper names into predicates like this now we're really looking like those graph representations and so the only thing left is to make the quantifiers themselves conform to that representation as well right and there we have a perfectly good representation of the meaning British stab someone and all we would need is some parcels like this right so if something is a Brutus then we can represent it as a noun phrase that has the string brutus as output and if there is some quantification that's an existential quantification and it binds some variable well we can represent that as a noun phrase that has the output someone and you know if we have some event of stabbing we can represent it as the transitive verb stabbed and you know if we have some event that's the trend that's represented as a transitive verb and some thing x which is represented as a noun phrase and guess what the the thing represented as a noun phrase is the object of the thing represented as the transitive verb well we can form a verb phrase and if we have a verb phrase and something that is kenrick that is the subject of the event that is represented by the verb phrase and that thing by the way happens to be a noun phrase we can stick them together to form a sentence and if we apply these rules well will just magically or hopefully not magically generate sentences like Brutus stab someone and the scales to whatever sort of thing you want to parse parse in this case generate whatever kinds of meanings you want to generate from ok so are there any questions about the big picture of this yes staring back okay so the question was these rules are handcrafted is there an open source is there an open source version of these rules or do you have to make them all yourself some of these rules you can get from things like the grammars that you find at Stanford so the Stanford parser for instance it has rules like this at least it has the syntactic components the semantic components as far as I know there's no open source stuff for this may be the categorial grammar the combinatory categorial grammar people have something that can be transformed into this that i don't know about unfortunately semantics is one of these domains where there's no good open source resources that's just an unfortunate fact about NLP part of it is that most NLP tasks don't actually need semantics of this sort some tasks do but some don't and the tasks that do usually people just write everything by hand that's an unfortunate fact about the world of NLP I mean if you're doing spam detection right you don't need this if you're doing spam detection that kind of NLP you might be able to get away with almost nothing like some of the early spam stuff was just word counts you know and there's more advanced stuff that has been done lately but you don't need full semantic representations necessarily Jason yeah so for a chat bot so what I didn't what I didn't mention previously is that these representations can sort of the meaning representations can sort of be well whatever you want right so you don't necessarily have to use linguistically informed semantic representations you can pick something that is specific to your task and then that's then it's going to be much easier for you to map from you know your representations to the rules because you know exactly how these things correspond but again for like open source stuff it would be really nice if these existed and but nothing does to my knowledge I really wish it did and if you want to help make such a thing let me know questions yes back to the sentence the fish is right and take your aquarium where you're looking at it in context maybe shifts in that context be models based on welcome to describe it we gave the variables themselves so fortunately because we're generating rather than horsing we might not need to disambiguate those where presumably we're going to start with a meeting that is only one of those meetings and then we're going to have to pick a sentence that represents that meeting and if the sentence happens to be a sentence that you can use to represent some other meaning well that's okay because we didn't ask to we didn't ask to generate a unique thing we just asked to generate some particular sentence that represents it but context can indeed be very important and so you can you can make your semantic representations as rich as you'd like to represent whatever information you'd like and so if you wanted to represent things like you know what objects have I referred to previously that are in the discourse that that I could refer to by pronouns instead of by you know the fish I could say it's ready to eat right that sort of context actually is really really useful for generation because you don't necessarily want to always say the fish is ready to eat the fish the fish the fish you want to say it in the subsequent times and you might want to add that sort of thing into your meaning representations and that's entirely doable but getting these collisions is actually not really a huge problem because I mean after all that sentence is a sentence of English and so it ought to be possible to generate that sentence even though it's ambiguous you started with a definite meaning and you generated something that can at least on one interpretation represent that meaning so because the direction is different there is less of an issue questions no questions okay so you're all gonna go out and implement this right away right awesome you should do it in Haskell too by the way high school will make your life much easier okay thank you for listening Wow look at that right on time