Okay, hi, everyone. So today I�fm going to go through in some detail some of the ideas that I started on last week of how you can actually go about building a compositional semantic representation to provide some kind of handle on how you can start with meanings of words and some tactic structure, and actually put together a meaning for a complex sentence. And so most of the work that�fs gonna be talked about here is how can we have enough mathematical machinery and essentially what we�fre gonna using is lambda calculus to glue things together, and first order star predicate logic is the output form, so that you can actually have a complex meaning being built compositionally out of the parts. And so that�fll be today, and then for the last two lectures next week, on Monday we�fll then talk about well, how can we learn about and represent the meanings of words, so that�fll be the lexical semantics part. And then the last lecture, I�fll talk about some applications like question answering and textural inference. [Inaudible] say a sentence about quizzes. So again, have precisely one more quiz and sort of shifting the schedule between having had the holiday on this Monday and lectures ending next Wednesday, our goal is to hand out the final quiz by the end of this week, Friday, and then for it to be due on the Wednesday midnight, the day of the last lecture. Okay. Okay, so first of all, for the first couple of slides, essentially I�fm gonna be kept in a slightly more formal way with the kind of material that we talked about last time, and then go on and talk about how that we can get further than this. So this sort of bout looks familiar from last time. And so we have two people, �gKathy�h and �gFong,�h we have a verb �grespects�h which we�fre representing with lambda calculus taking two arguments, and inference of the verb �grun.�h And then here is our grammar, and so I�fm stop writing ? stopping writing definite clause grammars, so our grammars are just effectively being written before the colon and just like a contextually grammar before, and after the colon is writing how meanings are combined to represent the whole sentence. 

And the form of what happens with the semantics in our grammar rules is always gonna be incredibly simple, so what we�fre doing here is we�fre saying our composition rule is, �gTake the meaning of both halves and do function application.�h Do function application [inaudible] only one thing a verb phrase rewrites as a verb, and so you just pass the meaning up. So essentially, we�fre always going to be either just doing function application or passing the meaning up. And so the action then comes into well, how can we have lexical representations of meanings that�fll allow the right kind of combination? Okay. So having this is then enough that we can do the same kind of example that I showed last time, so we have, �gKathy respects Fong.�h We write down the meanings of the words next to their base categories, we ? and then build a verb phrase where we do function application lambda calculus just like this. So we�fve got the meaning of �grespects,�h the meaning of �gFong.�h When we do function application we say, �gOkay, �gFong�h substitutes in for the value of y, and therefore the return value is lambda x respects x Fong.�h And then we do the same again at the top node. We say, �gOkay, here�fs the meaning of the verb phrase.�h We apply it to the argument of the subject �gKathy,�h and so we get out, �gKathy respects Fong.�h And so note in particular we kind of do that swapping here, so that internally the verb is taking its object first. So the outside argument here is representing the object argument, not the subject argument, and then it�fs kinda swapped around inside. So we do get out the right meaning of, �gKathy respects Fong,�h and not the other way around that Fong respects Kathy. Okay, so the general scenario that I�fve kinda used as my main motivating example at the moment is that essentially, what we�fre going to be doing is building a database interface. There are other things that you could imagine. You could imagine that these are meant to be commands that your pet robot understands or something like that, but as a kind of a concrete way to have a semantics that we can map onto, I�fm going to assume that we�fve got databases. Now, I�fm not actually going to really spend any time on talking precisely about the mapping onto SQL, I�fm just gonna to sort of show random motivate ? show bits of SQL that you could imagine mapping it onto and take that as motivational. So I�fm really going to show the mapping for first order logic, but for those of you who�fve seen databases, I mean following the kind of data along tradition of databases, it should be fairly straightforward to see how that if we can represent things first order logic, we can then do a further tetonistic transformation into an SQL query. 

Okay, so in particular what I�fm going to assume essentially is that we�fve got database tables that represent our predicates of interest, so in that previous example we had a respectralation between people. And so when we have a respectralation in our predicate logic, I�fm going to assume that we have a respect table, and the respect table is going to have two columns. It�fs going to have the IDs of people who respect other people, the respecter column, and the respected column. So that if we have Kathy and Fong as our two IDs for people in the database, we could then ? if we take, �gKathy respects Fong,�h as kind of a new information statement, we can that as, �gOkay, what we wanna do is insert into our respects table a pair of respecter/respected, where Kathy is the respecter and Fong is the respected.�h Alternatively, in PEP�fs slightly more interestingly we could also look at the goal of then answering the question, so we all want to be able to answer the question of, �gDoes Kathy respect Fong?�h And so then we�fll be wanting to do a query of the database and work out whether it holds a particular row. So the little ? this point we use the teeta little SQL trick where we say, �gSelect �gyes�h from respects where respects dot respecter equals k, and respects dot respecter equals f.�h So we�fre wanting to ask �gyes/no�h questions like, �gDoes Kathy respect Fong?�h And we kind of fake that up in SQL by saying, �gSo select �gyes.�h And so then if this relation is in the database SQL will return �gyes,�h and if it isn�ft in the database SQL will return �gno rows returned,�h and we interpret �gno rows returned�h as just meaning �gno.�h Okay. Okay, so that�fll be our goal to be able to build that kind of interface. And one other note I should�fve said ? I mean just like last ? I mean in the examples I show there, and the semantics I make, I�fm assuming that for every predicate in the semantic form, we exactly have a relation that in the database for this database table that exactly matches that relation. That kind of makes it convenient and easy. I mean in practice that may not be true, and the example that you could think of there is equivalent to the example from last time with chat AD, so that chat AD actually only has one database table for countries. It has all the information about countries, but what it has is predicates, which you could think of as equivalent to database views where it has a capital predicate, which is taking just then two columns out of the countries table of country name and capital name. And so I�fm assuming in the same sort of way that I�fve got database views where I ? that map precisely onto the predicates of interest. Okay, so let me go through a little bit more formally the kind of representational base that we�fre gonna use for this inference. So the model I�fm gonna use here is going to be using the higher order lambda calculus, so the higher order is meaning that you can have variables that aren�ft only individuals, but the variables themselves will be functions like last time. And in particular the version of things that I�fm going to present is then assuming that we�fve got a type lambda calculus. So traditionally when you�fre presented a lot of things in either the lambda calculus world or the logic world, things are completely untyped. You just have variables x and y, and do things with them, but there�fs absolutely no reason that that has to be the case. And just like most people have decided that programming languages tend to work better when you have types on variables, you can also put types on variables into logical systems. 

And I think there are good reasons of both convenience and foundationally that once you�fre working with higher order logics, I ? it can be very convenient to have type logics, and I�fm not gonna go off on ? about that for a long time, but we�fre gonna assume that all of our variables have types. So we�fre going to have Booleans, zeron 1, we�fre going to have individuals, who are people and things in our model. And then we�fre going to have functional types where we can talk about properties of individuals. So the basic property is something that takes an individual and says whether something is true or false about them, and then we have more interesting ones like binary relations, or ternary relations. So in terms of the kind of model we have in mind, this picture that I put on the blackboard is the kind of picture of our model. So we have an oval world, which is the outer circle, and inside the world we have various individuals, which I�fve denoted with x�fs, and some of them have names, and here�fs Kathy and here�fs Fong, and here�fs some other individuals in our world. And particular individuals can be objects; they don�ft have to be people. Okay, so then if we have properties of an individual, properties can be represented as subsets effectively. The subset where that the property is true, so this is the car property, and the things inside of the car, so A and B are cars, and the other six things ? the other four things in my world aren�ft cars. Similarly, this thing here is in Palo Alto, and that thing there is in Palo Alto, so I�fve got this [inaudible] in Palo Alto property. Red things [inaudible], so those are my various properties I can have in my models as effectively my model of the world that I can do inference on ? with in a model theoretic way. It�fs a little bit more complex when you then have predicates that have more than one argument because then I can�ft draw the same convenient circles in the same way. But you can think of a two-place predicate like �glikes,�h or �grespects�h is like this. So it takes a first argument, which I�fve only partially represented it here, so you can read it. So the first argument should be able to be any individual, but I�fve only showed two of them. And what it then does is returns another function, so the function it returns is then a property. So the property is then saying whether the �glikes Kathy�h property holds of these ? I�fm sorry ? you know what? I drew this the wrong way around for some ? I was wanting ? let me just quickly change this. This whole point was it was meant to take the objects first, and then take the people second, is what I just illustrated with my previous example. Let me just quickly change this. A, B, C, [inaudible]. Okay, sorry. Okay. This is one [inaudible]. So the first argument it takes is the object, so if you have the predicate, so if you have �glikes,�h and its object is A, you�fre then what�fs returned is a property, a function that takes a single individual argument and returns a Boolean. 

So this property here is the set of people that like object A. And so that set there is �gKathy�h as I represented it here. And here�fs the property of individuals that like object B, and the set that for which that is true is �gKathy and Fong.�h Okay, and you can apply in that same general way if you want to have functions that take three arguments that you�fre building these higher order functions, or return lower order functions until they ground it in either individuals or Booleans. Okay. Okay. Something to note that I will use sometimes though tends to confuse people, so I won�ft use all of the time, once you have types in your ? so the conventional way of writing untyped lambda calculus is things like this, lambda y, lambda x, respect xy where here shows that this is something that takes two arguments. Now once you have a typed lambda calculus, that all functions inherently have a type. So it�fs just like java that if you have a method that it has a particular type that is its signature, and you can know that a function has a particular type. So you kind of actually don�ft have to write all these lambda arguments, you can just write �grespect�h because it�fs just a fact about respect that respect is a function that takes two individual arguments and returns a Boolean, that that�fs just the nature of the function. And so because of that we can then write things in the shorter form, which I will just show. So this is referred to as the long form where you�fre showing lambda abstractions of all the arguments and then how they�fre being applied, but the short form is just to write the function without excessive lambdas. 

And so I mentioned very briefly and I�fll come back to in a minute, the idea of having quantifiers. So that when you have a quantifier like �gevery�h ? it�fs a relationship between two properties, so this is, �gEvery kid runs.�h And so you�fre evaluating the property of being a kid and the property of things that run, and what you�fre asking is whether for everything that this property is told, whether this property also holds. So this is writing out a generalized quantifier in the form of the long form. But actually, we can just write it out in the short form like this because �gkid�h is a property of functions of individuals to Booleans. �gRun�h is a function from individuals to Boolean and the generalized term in �gevery�h is then a function that takes two properties and returns a Boolean as to whether it holds. And so we can write it out in the shorter form. And so though these kind of general rules for lambda calculus, which I�fm not gonna spend a lot of detailed time on the fine points of, but the general things that are for lambda calculus that you can do lambda extractions, so you can always pull out lambdas if you want to like this if it�fs useful to. You can do function application, which gets called beta reduction, so you can learn from this that Alonzo Church was really fond of Greek letters and named absolutely everything with a different Greek letter just to keep things complex. In those eta reductions, so eta reduction just let�fs you do the reverse of lambda extraction, and then alpha reduction is used for renaming of variables, so you don�ft get chance collisions between variable names. Okay. And so the central idea is that we can effectively come up with good semantic types that correspond to syntactic categories, or at least common pieces of syntactic categories. We�fll see that there are various complications in various places. So in general when you have nouns or verb phrases that they will be properties. So something like being a car is a property, so that there�fs a certain set of things that are cars. But also a verb phrase, so the �gliking A�h is also a property because then you�fre picking out the set of subjects for which liking A is true. The simplest case of noun phrases are individuals, so when we have things like the, �gKathy respects Fong,�h example, Kathy and Fong we both represent as individuals. That kind of very quickly stops working when you want to deal with more complex cases like, �gEvery car is red,�h and so I�fll come back to how people deal with that in a moment. What about if you want to sort of be building a meaning of �gred car?�h Well, the prop ? it seems fine to say that red is a property at the end of the day, the set of things that are red things, but we have this kind of idea that we want to be able to build up the meanings of words by doing function application. And so if we simply have the meaning of car is a property and the meaning of red is a property, well, we kind of can�ft combine them by function application any more. And at this point there�fs actually a choice as to how you go about designing your system. One way you could go about designing your system is to say, �gYep, G�fs function application isn�ft going to work,�h so what instead we�fre going to do is say, �gEvery time we write a syntax rule down, we�fre then going to write special rules as to how to generate the meaning according to that syntax rule.�h So for example I could say that car�fs a property and red�fs a property. And if I have the syntax rule �gnoun phrase goes to adjective noun,�h what I say is the way you translate that is if the adjective meaning is the property p, and the noun meaning is the property q, you translate that as lambda z, p of z, nq of z. So I�fm kind of building up in my syntax rule a translation rule. And that�fs referred to in logic as using a syncategoremic translation where you�fre introducing extra stuff in your syntax rule. 

The general trend that people have used when doing computational semantics has been to really avoid doing that because you get a lot more simplicity and power if you can just have automatic translation by function application. But the cost of that is you then have to encode the extra complexity down in the lexicon, and so that�fs what�fs then shown on this slide. So if we just want to be able to make a meaning for �gred car�h by function application, then what we have to do is say that one word is a function that takes the other one as an argument. And so we say it�fs the adjective that does that. So we say that well, red takes the meaning of car as an argument and returns something. Well, what does that mean that red should be? Well, the meaning of car as a property, it�fs something from individuals to Boolean, and when we have a red car, that�fs also a property, so this set here is the set of red cars, and that�fs also a property. And so therefore, the meaning of red should be something that takes a property and returns a property, and so its type is what you see here. It takes a property individual to Boolean, and returns another property. Okay, and once you start going down that route, you just kind of keep on heading down that route and you get into higher and higher order functions. So if you want to have a adverb like �gvery�h in �gvery happy,�h you say, �gWell, what does �gvery happy�h do?�h It takes an adjective like �ghappy�h and it returns something that has a meaning that�fs kind of like an adjective, right? �gVery happy�h is sort of like an adjective meaning apart from it�fs describing a more extreme adjective meaning. Okay, so if that means the type that we�fre going to give to adverbs that modify adjectives at least is it takes as its argument the adjective�fs type, and it returns something that is of an adjective type. So it�fs intebol to intebol, to intebol to intebol, which is just about incomprehensible, but in practice, these things are fairly straightforward. If you kind of just think of them in terms of higher-level notions. So you ? once you think that these are properties, and adjective is something that maps from one property to another, and this is something that maps from adjective meaning to another, that then things sort of fall into place in sort of straightforward enough way. Okay, so here is my grammar fragment that I�fm going to start off doing some examples for the grammar fragment, and I�fll add to it a bit more so I can answer questions. So this is a very straightforward PCFG grammar ? I should say CFG grammar ? I mean the only way it�fs different from the kind of ones that we�fve seen in the Pentree Bank, is if you look at the noun phrase structure, I�fm actually kind of producing a binary noun phrase structure rather than flat noun phrase structure. If you want to build up semantics of noun phrases, it really helps to have a binary noun phrase structure, different reason than making parsing going fast. So a noun phrase goes to a determiner and then an N-Bar. An N-Bar can have any number adjectival PP modifiers and then goes to a noun. 

But apart from that, note that the semantics is in all cases trivial, so the semantics of our rules is simply function application that you have something be the head, and it�fs going to be the head [inaudible], and if there are other things, they just become arguments of it that I�fm denoting there. And that means that all the interesting stuff then happens in the lexicon. And so this shows some of the lexicon, and I�fll go through some of this with examples, but just go through a couple of things at the start. So we have �gKathy,�h �gFong,�h and �gPalo Alto,�h and so they�fre things that are individuals. I guess when I did this I didn�ft actually put �gPalo Alto�h in as an individual, but we could have somewhere here �gPalo Alto�h also represented as an individual. Okay, then you have things like �gcar�h where �gcar�h is a property, so it�fs something from individuals to Booleans just like here. For �gred,�h red is a little bit more complex since what I�fve represented here as a property is actually then �gred prime.�h So �gred prime�h is the property of things that are red. So the red here is then this red that�fs of the intebol to intebol tied, where what it does is it takes a property �gp,�h so this is the higher order part of our lambda calculus. And inside its lexical inferri, it does the meaning combination. So it says, �gOkay, if you�fre gonna make up something like �gred car,�h I take as an argument the property and then I build as my lexical inferri to return the property in which p is true of it, and the red property is true of it. And so we kind of do the clever bits of meaning combination down in the lexical entries. Okay. And then maybe more straightforwardly down at the bottom we then have the verbs, which are much like before. So �grun�h is taking individual and returning a Boolean. �gRespects�h is taking two individuals and then saying whether it�fs true or not, similarly for �glikes.�h So �glikes�h is just like here, and an example like �gruns�h is effectively another property here, so there�fs the things that run, and so maybe this runs or that car doesn�ft run. Okay. 

Okay, so these are the ones in large print, when I get on to the more complex sentences, the print gets even smaller. And I think to some extent they�fll sort of work through some of the details of this, you have to kind of look more carefully and see that it all makes sense more than I can do in lecture, but nevertheless I want to try and point out some of our high level points of what�fs going on. So what we wanna do is make a meaning for �gred car Palo Alto.�h And I mean first of all, to think about it conceptually, well, what should the meaning of �gred car in Palo Alto�h be? The meaning of �gred car in Palo Alto,�h well, that seem like that should still be a property. It should still be something that picks out a set of individuals that satisfy the property �gred car in Palo Alto.�h I mean in particular, in terms of my model that I have right here, what I�fm wanting it to do is pick out precisely this set here as this is the �gred car in Palo Alto�h set of individuals. So the end result of the semantics that we make should be that we�fre getting out a property. So how do we actually get that all out? This is the bit that I�fve talked about already. So �gcar�h is a property from individuals to Booleans, so �gred�h has this more complex meaning where it takes a property and returns a bigger property. So we can combine in here �gcar�h as p, and what we get back is lambda x, car x and red prime x. So that�fs already created a property, which corresponds to the things that are cars and red, so that�fs that sort of bigger property up here. Okay, and then we wanna do combining in Palo Alto. And so in ? at that kind of scary lexical entry I�fve written next to it, which I didn�ft stop to dwell on in the time. But while in principle you can kind of reason through in first principles what kind of types you have to put on words to be able to get things to work and then essentially to build those types. So if you think about �gin Palo Alto�h ? �gin Palo Alto�h it should itself be a property, right. That that seems like it�fs something that can be true or false of individuals there. At least at a certain point it time, they�fre either in Palo Alto or they�fre not in Palo Alto. So here I have this property of things that are inside Palo Alto. Okay, so that means that when we build this pp up here of in Palo Alto, its meaning should be a property. Well ? should complexify that once more. The idea of �gin Palo Alto�h should be a property, but just like an adjective we�fre then going to want to have the pp modifying the meaning of �gred car�h just like an adjective, so I�fll explain that in a moment. Okay, so we have ? we wanna build up a property meaning, but what we actually have is an individual �gPalo Alto,�h and we have the word �gin.�h So that suggests that we want to have something that takes an individual and is returning something. So the prepositions meaning starts off by taking an individual y. 

And so well, what�fs it gonna return? It�fs gonna return for �gin Palo Alto�h something that�fs then an adjective meaning, something that will take a property and build a more complex property where it satisfies the previous property and �gin Palo Alto.�h And so that means at the very end of the day, that what you get for some ? a word like �gin�h is it�fs taking an individual, which is the object of the preposition, and then it�fs returning one of these adjective meanings. You can have �gin�h as having that kind of type. Okay, so it takes �gPalo Alto�h as an argument, so �gPalo Alto�h becomes y and substitutes into �gin�h to give this meaning, okay. And so now this is something that works just like an adjective, that it�fll take a property as an argument and return a more complex property. And so here it takes as it�fs argument things that are �gred cars,�h and so all of this becomes lambda p, and so you substitute �gin,�h so then you get lambda x, car of x, and red prime of x, and in prime Palo Alto x, which is then the meaning of the whole thing. Does that sort of make sense? I know there�fs a lot of notation stuff, but the basic idea is we can take these things of various functional types, we can write them so that they take arguments of the appropriate functional type, and then they return an argument of the appropriate functional type. And so in this sort of way if we model all noun phrase modifiers as properties, that as things that map from properties of properties, we can then have successive noun phrase modifiers kind of combine together and the resulting meaning would be still a property. So by extending this we can have sort of the large leather green couch in my bedroom, which my uncle sold me, and we can kind of have each of those modifiers be something that maps from a property to another property, and we can combine it together and make up the meaning of the whole. It�fs worth noting finally, the way I�fve wrote the grammar ? if I go back a few slides ? but when you�fre at this N-Bar level ? at the N-Bar level you can just take modifiers. So you could take adjectives on the left, or you could take prepositional phrases on the right, and if I have other things like relative clauses, you could take them on the right as well, so you can just take any number of modifiers. And so that actually means that the grammar has a syntactic ambiguity where you can take the modifiers in either order. So here I built �gred car�h first, and here I built �gcar in Palo Alto�h first. And interestingly, that�fs then what people call a spurious ambiguity, whether things that are licensed by the syntax that don�ft actually make any difference to the meaning that�fs generated for the sentence. So regardless of which one I combine with first, I get the same meaning of lambda x, car x, in Palo Alto x, and red x. Okay. 

And precisely the reason why I get an ambiguity that�fs spurious there is that the meanings of the different modifiers I�fm putting on are actually just turning into extra conjoined terms. So things that are just turn into extra-conjoined terms are referred to as intersective modifiers in linguistics, and so that�fs exactly what I was doing here. I was having the set of cars, I was intersecting it with the set of red things, and then I�fm intersecting that with the set of in Palo Alto things, and I�fm coming down to this intersection and that gives me intersective semantics. So if you�fre in that world ? and so what�fs of the things that we think of as modifiers have intersective semantics? So �ggreen leather couch.�h You have the set of couches, you have the set of green things, you have the set of leather things, you can intersect them, and you have the set of green leather couches. And providing we�fre in that world of intersective semantics, it�fs very easy to see how to do this with database queries because effectively you can have a table for each one of these properties, and then you can just join the tables and find out the individuals, the database IDs for ? which are in all three of these tables. So that�fs kind of the easy case and the case that we can actually practically work with most of the time. And sort of important to note though, that there actually are ? and this is something that�fs talked about quite a bit in linguistics ? there are nonintersective modifiers where you get a meaning from the whole thing, which you can�ft kind of represent as an intersection of terms. So I mean the most famous example is of words like �galleged.�h So if you say that someone is an alleged murderer, that doesn�ft mean that they satisfy the property of being a murderer and that they satisfy the property of being alleged. It means that they satisfy the property of being an alleged murderer where alleged murderers somehow a property meaning that you can put together out of the meanings of the parts. And so somehow if you wanna be able to deal with alleged murderer, you wanna be able to deal with that, but it�fs kind of not so straightforward as to how to do that because effectively you want to be sort of working out a sort of a new functional form out of an old functional form. I mean here�fs the other example of this that I had here, which isn�ft quite so convincing, but I think illustrates the same point. So this example here is �goverpriced house in Palo Alto.�h And so although it�fs not quite as dramatic as �galleged,�h I mean I think it�fs reasonable to say that overpriced isn�ft a term that has absolute reference. 

So you can have one semantics for an overpriced house and it�fs in Palo Alto, and that�fs a kind of a global scale of what�fs an overpriced house, so using these semantics, well, every house in Palo Alto qualifies as an overpriced house by global standards. But if you make the modification the other way, you then have the set of houses that are in Palo Alto, and then you�fre saying overpriced out of houses that are in Palo Alto, and so that seems to have a different semantics of houses that are overpriced even relative to the standards of Palo Alto. Okay, so you can get tricky things with nonintersective adjectives, but I�fm not gonna deal with that further today, and I�fm just gonna stick with the intersective adjectives. Okay. So all�fs good until now, but unfortunately natural languages just get a bit more complex that what we�fve done so far. Okay. So I don�ft know if this ever troubled any of you guys when you did a baby logic class, but when you think about how people translate English into a baby logic class, something fundamentally weird happens, right? So if you wanna translate �gKathy runs,�h you translate it into �gruns Kathy.�f That�fs easy. But if someone then tells you to then translate into predicate logic �gno kid runs,�h well then, you kind of have to know to do this really funny thing where you write down �gnot there exist x, kid x, and run x.�h So run ? here the noun phrase subject was an argument of the verb, just like it seems to be in the syntax of the sentence, �gKathy runs.�h Kathy is an argument of running. Syntactically this example doesn�ft seem any different. �gNo kid�h is now the subject of �gruns.�h Runs, a predicate, has taken a subject, that�fs his argument, but the translation is kinda completely different. We found this really funny thing where we�fve wrapped some weird logical structure around the outside of the whole thing, and �gruns�h is buried down here somewhere. So that looks kind of awkward, and so the question is how can we produce those kind of translations in our system. Well, here�fs another example of how things go wrong. So we have, �gNothing is better than a life of peace and prosperity. A cold egg-salad sandwich is better than nothing,�h and if you don�ft look too closely it seems that you should be able to deduce from that that a cold egg-salad sandwich is better than a life of peace and prosperity. 

Why is that? Well, it seems like �gis better than�h should be a transitive relationship, right. That if you have that whatever ? a Blackberry Pearl is better than a Motorola Razor, and an iPhone is better than a Blackberry Pearl, you should be able to conclude that an iPhone is better than a Motorola Razor, right. �gIs better than�h is a transitive relation. And so that�fs what I�fm attempting to do here, I�fm trying to do inference using the fact that �gis better than�h is the transitive relation. But with sentences like this, it just goes totally wrong, and well, why does it go wrong? Well, the reason is again, �gnothing�h is a quantifier. It�fs just like this �gno kid runs,�h here when you have �gno kid,�h that as soon as you have things that are quantifiers, it kind of just doesn�ft work if you�fre treating them as arguments to relation, and you seem to do something special and different. Okay, so somehow we need to be able to model in our system how we represent the meaning of these quantifiers and deal with them. And so well, how can we do that? Well, we�fve done pretty well with things that are properties. We have �gred car�h and �gPalo Alto,�h and things like that. So we could build everything about noun phrases as complex properties, except when they have a determiner out the front of them like �gthe,�h or �gevery,�h or �gno,�h and things like that. Once we see that, it seems like we have to do something very special. So what are we gonna do from the meaning of �gthe red car in Palo Alto,�h or �gevery red car in Palo Alto?�h Well, first of all, mention what we gonna do with �gthe.�h What ? for �gthe�h what the easiest thing to do is say, well, we want to then map down to an individual. Just like we had Kathy and Fong as individuals. �gThe red car in Palo Alto,�h that should be an individual. It should be this guy right here, that that�fs the meaning of the �gthe red car in Palo Alto.�h An so a possible semantics for �gthe,�h and this is actually precisely the semantics for �gthe�h that was proposed by Bertram Russell, is to say that �gthe,�h the meaning of �gthe�h can be represented as the iota function. So iota is the semantics of �gthe,�h which was back in the lexicon if you look back ten slides. The meaning of �gthe�h is that this is a partial function. So if there�fs precisely one thing in the model for which p of x is true, then the function returns that thing. So if I ask for �gthe red car in Palo Alto,�h the meaning ? what�fs returned is the individual b. If there are multiple things for which a certain property is true, so for example if I just say, �gThe car,�h then this is only a partial function, and the return value is undefined. So if the function doesn�ft apply, it�fs got no return value. So that�fs our meaning of �gthe.�h It will return an individual if one is uniquely specified, and if there ? one isn�ft uniquely specified, you don�ft get any value in return. 

Now, in ? now I mean that�fs kind of true. I mean in practice though, it�fs not quite that simple. So when I ? I mean basically we use �gthe�h when we�fre talking about things that we can identify. So we talk about �gthe president of Stanford University�h because there�fs only one of them, and so it can be uniquely identified, but we don�ft say �gthe department chair of Stanford University�h because that kind of ? it sort of feels wrong because it doesn�ft identify an individual, and that�fs Bertram Russell�fs core inside. I mean in practice it�fs a little bit more complex than that because in practice people will interpret the meaning of �gthe�h as relative to some situationally defined context, so if you say something like, �gPass me the phone,�h you�fre not making a claim there�fs only one telephone in the world. What you�fre making a claim is in this situationally defined context of the room that we�fre sitting in, there�fs one phone, and that�fs the one that you�fre meant to pass me. Okay, so that gives us a semantics for �gthe�h nevertheless, so I mean now we could actually say a sentence like ? work out a semantics for a sentence like, �gKim likes the red car in Palo Alto,�h because the meaning of �gthe red car in Palo Alto�h would just be this individual b, and then we can look across and say, okay, �glikes b�h returns this function, and if we evaluate it with respect to �gKim,�h we get �gtrue�h as the answer, and so we can evaluate that kind of sentence. Okay. And so we can then translate that kind of sentence into our SQL database form, so �gred car in Palo Alto,�h properties where we make a query of a database, and we return the set of objects that satisfy it, just like in a regular database query. So this�fll be select cars dot odge ? for properties I�fm just assuming that it�fs a one-column table where the field that�fs called odge. Select cars dot odge from cars locations �gred,�h so I�fve joined my tables where cars dot odge equals location dot odge, and locations dot place equals Palo Alto, and cars dot odge equals red dot odge. Okay, so then if I want to do �gthe red car in Palo Alto,�h what I�fm wanting to say is the return set from that database query is a single row, and I can actually write that in my SQL by being a little bit clever and writing a having clause, and I can say, �gSelect all of the same stuff, having count equals one.�h And so this having clause will precisely implement my Bertram Russell semantics of �gthe.�h If there�fs a single thing that satisfies it, I will get returned that one row of the database, and otherwise I don�ft get a return. Okay. Well, that�fs good up to there. If I could just say, �gFor the red car in Palo Alto,�h well, it turns into this individual, and we know how to evaluate individuals with respect to something like �glikes,�h but what if I want to say, �gEvery red car in Palo Alto?�h Well, then it seems like we have to do this fundamentally ? change things around where with words like �gevery,�h these determiners, they have this quantificational force where they take other things as their arguments, and so that�fs the thing that we�fre going to represent. So what we�fre gonna take as the type of a generalized determiner, a word like �gevery�h and �gno,�h is to say, �gThis is something that takes one property.�h So for �gevery car�h it�fll take the property of being a car. For �gevery red car in Palo Alto�h it�fll take the property of �gred car in Palo Alto,�h and then what it�fs going to return is something that maps from properties to truth-values. 

Okay, and so I can have semantics for generalized determiners in terms of these what I�fll call generalized quantifiers that take a single argument. So �gsome kid�h will take two ? �gsome kid runs,�h you take the two properties as arguments, you can join them together and then the �gsome�h predicate says is there at least one individual for which this property is true? And the �gevery�h predicate says is it the case that this is true for all individuals? Okay. Just what�fs expressed there. Okay, so now I�fm kind of just about in business in the following sense. Okay, here�fs kind of how I want to do �gevery student likes the red car.�h Okay, so I have �gcar,�h I build up the bigger property of �gred car,�h and then I combine it with the determiner �gthe red car,�h so this is this iota operator here. And when we evaluate the iota operator of �gthe red car,�h its value is just an individual. It�fs the individual b in our model over here. Okay, so because its value as an individual I can apply the predicate �glikes�h to it, and then I get something that is a property of �gliking the red car.�h In particular the property that I get out is precisely this property here of �gliking the red car.�h Okay. And so then what I want to say is that, �gEvery student likes the red car.�h And so well, I�fd really be in business at this point if I could do the following trick. Up until now I�fve treated the verb as the head of the sentence and say, �gDo function application.�h That�fs how I handled �gKathy likes Fong.�h But �glikes�h took two arguments, �gKathy�h and �gFong,�h and it works, but it seems like that�fs not gonna work for me for �gevery student.�h But what if I just changed my mind and said, �gWell, let�fs take �gevery student�h as the head in the semantics, and have it take �glikes the red car�h as an argument.�h How would things work out then? Well, �gevery�h is something that takes two properties and then returns a truth-value, so it combines with one property here to give us �gevery student.�h And well, look, the meaning of the verb phrase is a property. We�fve made precisely this property that I put a box around on the board, so �gevery student�h could take that as an argument, and then we�fd precisely get the �gevery�h predicate evaluating those two properties. And so it would be saying, �gIs this property true of every individual?�h And at least for the partial representation I�fve shown over here, it is true of every individual, and so I�fd get x my answer �gyes.�h Okay, that looks really cool apart from the one problem that I played this mucky trick whereas before the verb phrase was the head of the sentence, I now made the subject noun phrase the head of the sentence, and that might then get you worried as to well, kind of what happens after that. Like what if I put a quantifier in object position? What if I said, �gEvery student likes every car?�h Well then, I sort of am in worse trouble then because then if the meaning of �gevery car�h is something that takes a property and returns a truth-value, it sort of seems like I can�ft combine that with �glikes�h at all. So I need to sort of build some more technology to be able to deal with quantifiers. So the person who sort of initiated this enterprise was Richard Montague. So Richard Montague was a philosopher in the late 60s and early 1970s. He actually committed suicide, which is a long story I will not digress into for ? too much detail at the moment. But based ? the central idea of his work was to notice the fact that modern logic had developed all of these rather nice tools that had completely abandoned the goal of actually trying to provide semantic representations for human languages, whereas the original goal of logic as I mentioned before, was actually to help assess human arguments. The ancient Greeks actually believed that logic was a tool, so that when you listened to George Bush say something on television you could evaluate whether what he was saying was sensible or not. 

So Richard Montague had the idea that maybe now that there are all of these good formal logical tools, maybe there actually could be applied vector natural language if we have the right technology for doing it. And so he introduced these kind of techniques of using higher order logics and lambda calculus. And so the idea that Montague came up with to solve the problem of how to incorporate quantifiers into things, was to say, �gWell, it just doesn�ft work to say that noun phrases refer to individuals because we wanna be able to say things like, �gEvery student likes every car,�h or, �gEvery student likes some car,�h or something like that. And these quantifiers we have to represent differently. So in his model all noun phrases got turned into these higher order things. So any noun phrase meaning got turned into something that took a property and then returned a Boolean. And so the meaning of �gKathy�h is then no longer an individual �gKathy.�h The meaning of it is this thing that takes a property and returns that property evaluated with respect to Kathy. Slightly confusing, but sort of makes sense, but once you have this, if you want to have the semantics of �gKathy runs,�h or you�fve got the property of running things, and you stick that in as p, and you�fre evaluating whether Kathy is true of it. So you�fve fundamentally changed around one of the functions and arguments. A lot of modern work has sort of seen that as rather ugly and unnecessary, and so has instead gone in this direction that essentially follows Montague, that essentially says you want to allow flexible shifting between types. So Kathy is just an individual, but if you want to for semantic combination, you can certainly turn it into something that takes properties and evaluates whether it�fs true of that property. We had properties like �gman�h and �gcar,�h and well, it proved handy for �gthe�h to have this iota operator, which could map from a property to an individual that satisfies it as a partial function, which is what those dots are meant to show. And so noun phrases are commonly these days represented by allowing these kind of flexible type shifting operations. Okay. Now this point time is getting short, and I�fm gonna skip a little bit, but earlier on we talked about how there are quantifiers scope ambiguities, and I will assure you if you read the handout that goes with this class really carefully, it explains this beautiful way in which you can model quantifier scope ambiguities in terms of doing different amounts of type shifting, but I�fm not gonna go through it right now. But believe me, here are the two different representations for �gsome kid broke every toy.�h And if you look very carefully as I flip them back and forth, you see in one that the �gsome�h quantifier is on the outside, and in the other the �gevery�h quantifier is on the outside. 

Okay, let me just for a couple of minutes sort of show a couple of more examples of how you can then start to do questions like this. Okay, so we want to have ? we want to be able to do �gyes/no�h questions, so we wanna check on a database something like �gis Kathy running? What things are true of the world?�h And perhaps more interestingly, we might want to do content questions like, �gWho likes Kathy?�h What is the right semantics for questions is something people still write papers about in philosophy and linguistics. The model I�fve got here is that a question is just going to itself be a property. So a question is I say a property like �gred�h and �gin Palo Alto,�h that the meaning of the question is just that property, and that�fs going to be interpreted as what is the set of things for which that property is true, and that�fs the answer to the question. Okay. So is how I then extend my grammar to deal with questions. And there�fs one kind of tricky bit here, which is I use this idea of �gget threading�h for questions. The complex thing about questions is that they ? in English ? is that they have these long distance dependency. So if you have something like, �gWho did Bill report that John said Sue likes?�h The �gwho�h at the front is actually the object of the liking, and somehow you have to connect those two positions together. And there are various ways that it could be done, but a common way in some formal grammars, and the method that I use here, is this idea of �ggap threading�h where you can introduce a variable as an empty node, and then kind of shift it up through the syntax until you discharge it. So here I will have an empty introduced with a meaning of a variable z, and then I will allow rules to pass up that z until I have my whole sentence, and then I will discharge the z as being an argument for that predicate. I will show an example. And then here are my syntax and semantics for question words. So the question ? for a question word like �gwhat�h it kind of doesn�ft have any meaning in this model, it just takes a property and returns that property. So if we have something like �gwhat is running,�h we have the property of �gis running,�h and what will take it as an argument and just return it does nothing to it. But some of the other �gw-h�h words do more interesting things, so for �gwho is running,�h it takes the same property as an argument, but it makes a more complex property, which says the argument property has to be true, and the thing has to be human. And if I asked, �gHow many birds are running?�h Then I�fm taking a property of being a bird, and then I�fm going to be taking a property of �gis running,�h and then what I�fm going to be returning is the count of the individuals for which that combined property is true. 

Okay. So if I take that and put it all together, I can actually now make quite interesting queries and translate them into something that can be evaluated over a database. And again, I�fll probably go through this a little quickly, but you can peer closely at the examples and see that it really does work. So here�fs an easy case, which I�fll use to illustrate this gap threading idea. So, �gWhat does Kathy like?�h So the idea is we actually have empties in our grammar now, so there�fs a missing object of like, which is introduced with this variable z, an individual meaning, so this is the ? has a meaning of kind of �glike z,�h but we don�ft actually know who z is yet. So here�fs �glike z�h as the meaning, then we get �gKathy likes z,�h which has the meaning of �glike z, Kathy.�h And then what we can do ? we kinda pass up a gap as the splash categories, so this is a verb phrase, which had supplied inside it an empty noun phrase whose meaning was z. And so now here we have a sentence, which has inside it an empty noun phrase whose meaning was z. So at any point we want to we can then discharge our gap thread at empty and say, �gOkay, this sentence�fs meaning is actually �glambda z, likes z, Kathy.�h So that we�fve turned back into a property the thing that wasn�ft actually present, that was missing. So this is kind of like in predicate calculus if you do natural deduction where you assume something and then you later discharge the thing that you assumed. Okay, so now I have a property of �glambda z, likes z, Kathy,�h and so for, �gWhat does Kathy like,�h �gwhat�h introduces no new semantics of it�fs own, and so the meaning of the whole thing is just �glambda z, likes z, Kathy,�h i.e. here�fs a property and the set of rules that are returned from the database for that property is the answer to the question. So I get select liked from likes, were likes dot liker equals Kathy. Cool. Okay, but we can go on from that and do much more complex examples. So, �gWho does Kathy like,�h works essentially the same, apart from �gwho�h has this more complex semantic form, so that the result is that you�fve got this property of �gKathy likes the thing and the thing is human.�h So now we have select like from likes humans where likes dot likes equals Kathy, and humans dot odge equals likes dot likes, so we�fre restricting it to being a human thing. Okay, but we can put in more complex question words like, �gWhich cars did Kathy like?�h So now �gwhich cars�h is saying so �gwhich�h is taking the property of a car, and it�fs taking the property of �gKathy like,�h and asking if both of them be true at the top, which gives us this database translation. 

And at that point we can just keep on using all the stuff that I�fve tried to present today, and it really does all fit together and work right, so I can ask, �gWhich cars did every student like?�h And so we have the same empty z. We can make a meaning for �gevery student likes.�h So now we have the set of ? this property is the set of z such that every student likes z. And then we can combine that with something like �gwhich car,�h and make a much more complex meaning. And we can keep on going through examples like this. �gHow many red cars in Palo Alto does Kathy like?�h Or, �gDid Kathy see the red car in Palo Alto?�h So at this point I�fm starting to be in the space that the trees that you have to build are too large to fit in my narrow margin, so you�fll just have to believe me that the proofs work out okay, but they do ? or the derivations work out okay. So this is, �gHow many cars in Palo Alto does Kathy like?�h So we kinda make up the �gdoes Kathy like�h part here. And then for the, �gHow many red cars in Palo Alto,�h we make this property of red cars in Palo Alto just like before, and then how many takes first this property, and then it takes the �glikes Kathy�h property, and so it�fs returning the count of how many things satisfy this big composite property, and then we could translate into our piece of SQL where we�fre then doing a count operation on the things that are satisfied. Now, [inaudible]. So I thought then just for the last few minutes I�fd mention just a little bit about some work that�fs been happening recently that could actually connect these things together. I mean I think it�fs fair to say that for ? until about 2005 I guess, 2004, 2005 ? that there was really kind of a complete disconnect between work that was using statistical probabilistic machine learning methods and OP, and logically oriented deeper meaning representation work on NOP, that that was something that there�fd been a lot of work on in the 70s and 80s, and there was still an occasional little bits of work going on in the 1990s, but effectively the two didn�ft have anything to do with each other. That by and large people were doing probabilistic machine learning stuff, were doing more surface work, so they were doing things like building part of speech [inaudible] recognizes and statistical parsers, all the things that you guys have been doing, but really were doing nothing significant in the way of doing full sentence meaning representations. They were doing some meaning tasks, but low-level meaning tasks like doing name density recognition, or extracting particular semantic relations. 

But just in the last couple of years, there�fs actually then started to be some nice threads of work where people are actually starting to return to how can you learn and use much deeper semantics while still fitting into using probabilistic and machine learning ideas, and I thought that I�fd just mention a couple of things of this sort. So one question is, �gWell, could we possibly learn representations of this sort?�h And that�fs something that a couple of groups have been working on recently. So Luke Zettlemoyer and Michael Collins at MIT have been doing a couple of papers on that, and then also Ray Mooney and students at Texas have been doing this sort of work. And I can�ft really go through the details here, but this is in one very short slide the outline of the Zettlemoyer and Collins approach. So that they assume that they have some stuff at the beginning. They assume that they have an initial lexicon. The initial lexicon is mainly knowing about some function word, so for things like prepositions you have a meaning of what does this preposition mean? They also though assume that they know a few specific ? the main specific words, so that they might assume that they know the meaning of �gTexas�h for example. They then start off with category templates, and so category templates is effectively possible semantic forms words could have. And so that�fs kind of like I was saying that there are these dominant patters that we have properties and two-argument things and things like that. They have a set of category templates. So they start off with a little bit of stuff, not nothing, but primarily then beyond that, what they assume that they have is pairs of sentences and meaning representations. That may seem like a fair bit, and in some sense it is a fair bit, but I mean a prominent belief of how human language acquisition works is that humans don�ft actually acquire stuff about sentences until they understand what they mean, right. That basically people are working out the meaning of things from situational inference, so that after the first ten days when mommy is holding the orange juice and saying, �gDo you want juice?�h That you start to understand what that means, and then you map between the words and semantics. So you have a set of examples like this, and so the goal of the ? the goal of their papers is that you want to do combined learning of both lexicon and syntactic structure. So although you have a kind of a bootstrap for the lexicon, most words you don�ft know what they mean, and you have no information whatsoever of syntactic structure and semantic combination rules. So this isn�ft like the Pentree Bank where you�fre given all of the trees, you�fve been given no trees whatsoever, and no basis for which to put together compositional semantics. And so what they do is that it�fs built as a kind of an introvert bootstrapping process where you�fre postulating possible lexical forms, so that�fs where you�fre using these category templates, and you�fre trying to use them in a parser, and the parser is a maxent parsing model. And effectively you�fre then learning lexical representations for words that seem to work in terms of the fact that they�fre able to combine together with words that are in your initial lexicon, and work to be producing the final semantics for sentences that you�fd like to see, and effectively through each iteration through the bootstrap, what you hope to do is figure out a successful semantic representation for some more words, and then start building up your lexicon so it grows over time. But it�fs ? it is a kind of a cool joint learning task because I mean at the start there�fs absolutely no parsing model whatsoever, so that they�fre simultaneously trying to postulate possible lexical entries, and then optimize the parameters of a maxent parser to try to parse things in a particular way as it goes along. 

There�fs then also been work on reasoning with such representations. Now in particular domains, one possibility is just to go with logical reasoning. And I mean I think that can actually be quite successful in certain domains of business rules, laws, and things like that that you can do logical reasoning. But I think in general it is the case that just like all kind of probabilistic argument in general goes, that knowledge of the world is in general so incomplete and uncertain that we just can�ft get very far with strict probabilistic inference. In particular a lot of the time things only go through assuming various plausible assumptions. That all the time we�fre assuming sort of plausible things will happen in the world, and that allows our inferences to go through where they�fre not actually kind of the climates that�fll happen. Most of the time we just assume that a really big earthquake won�ft happen in the next ten seconds, and so therefore it�fs reasonable to make assumptions about what the world will be like in ten seconds time. So that then leads us into the work on doing probabilistic models and knowledge representation reasoning. And so that�fs also been an area that�fs been actively pursued. I mean it�fs the case that all the current work on doing probabilistic inference still assumes restricted ? something more restricted than first order logic. So first order logic is in general very difficult to deal with because you have this open domain of individuals that perform [inaudible] is in the first order logic, is that you have an infinite space of individuals and you can quantify arbitrarily over them, whereas all of the existing models are probabilistic knowledge representation and inference in some way uses somewhat more restricted model where you can still do certain kinds of quantification that is not quite open [inaudible] like in first order logic. And so one thread of that is definitely Collins work here on probabilistic relational models. Another thread of work that�fs been going on recently is Pedro Domingo and colleagues have been doing Markov logic, and they differ in various ways. Part of how they differ is the Daphne�fs model was a basing net directed graphical model whereas this is then an undirected Markov network star model. 

Actually just the last week ? I know someone who�fs been doing undergrad honors with me has been trying to apply some of the Markov logic ideas to doing mappings of sentences into Markov logic and then doing inference on that with at least reasonable success on range of sentences, it�fs not that it�fs a full coverage system. So I think that this is an area where it�fs now possible and it�fs starting to be a lot of exciting ideas where you can kind of start to combine machine learning statistical methods with using these richer representations and then you have to do richer semantic inference. Okay. And that�fs the end for today.