Learning Compositionality with Scala

Text By the Bay 2015: Ignacio Cases, Learning Compositionality with Scala

Recording: Text By the Bay 2015: Ignacio Cases, Learning Compositionality with Scala

so my name is ignacio cases i'm a phd student at stanford working i'm a member of the natural language processing group by the way some somebody yesterday asked me about the code we have a github repo so you can please check it out and we are happy having you taking an use in all the current lp tools set of tools that we have for natural language processing so at the stanford i'm mainly working with professor dan yourofsky on the task of predicting the future and with professor christopher potts i'm very interested in many of the challenges of natural language understanding and actually what i'm going to present to you today is part of this background knowledge that we need in our research for uh creating systems that actually understand uh better people which is something yesterday mark lieberman his wonderful talk uh mentioned this period of the you you all know probably the ai winter after the by the end of the 60s after the infamous salpak report natural language understanding it happened the same more or less the same thing in the 70s with as you mentioned before with lots of good promising ideas but none of them realized but i have to say that we are right now in a very exciting moment where we are starting to see many of those things actually realized so it's a very very very exciting moment for natural language understanding so i encourage you to to work on it if in case you are not already doing it so understanding is needed part of it is because there are a growing proportion of queries in many companies that require semantic interpretation so users expect this kind of understanding from from a system this is true from this is actually adapted from bill mccartney he's a researcher one of my professors and researcher at google and they have continuously this need for a semantic interpretation because in many cases conventional approaches information retrieval to keyword-based approaches that are not sufficient to satisfy especially as tijuana was mentioned before yesterday with those natural language interfaces and this is a growing aspect we need this kind of understanding one of the reasons is that for example we have a very good systems that understand or have some kind of understanding of natural language and they perform they perform well in some tasks uh in this case wolfram alpha uh is able to for this arithmetic fragment of english that we are going to see a little bit uh later uh it it i mean the result is great it interprets uh the input very nicely so it's doing the the translation and it gets the denotation the result correctly right which states border california so we get oregon nevada arizona probably as some of you remember in the early 80s this was a major breakthrough with the work for by fernando pereira and the the subsequent jquery staff so this is actually is understanding however we have also examples where uh with and this is the point is not to criticize wolf from alpha but is to to actually make the point that this is difficult even for simple questions which u.s u.s states are islands so the interpretation notable islands no results so i i was guessing uh this morning with jonathan if actually we would hope to not have here rhode island for example right that would be uh terrible but we have other simple questions which u.s states border no u.s states and the closest world from alpha interpretation is which u.s states border so this is a difficult task even for simple questions the way as a computational semanticist the way by the way how many of you are actually working on natural language understanding systems so uh some of you so this is going to be familiar for you the way us computational semantics is we we consider we represent uh meaning is actually by a two pole three a triple of values composed essentially by messages which are typical uteruses in a natural language as english for example with those uteruses which are the first element of this tuple by a non-deterministic and i'm going to explain why it is the case a non-deterministic semantic parsing approach we get a semantic representation which can be in a query language like sql or using lambda calculate or any other kind of programming language it used to be prolog in this the examples i'm going to show you here is we are using scala which is a type strongly type a language that runs on the jvm and with which we can do functional programming these are by the way discrete semantic representations we are going to just have a glimpse at the end of the of the talk to non-discrete so distributed word representations which are right now at the center of the of the is our hot topic in research so once we have this semantic parsing we are going to see some examples but it's not deterministic we have this semantic representation and we can derive by an execution step that is deterministic in principle a denotation which can be constructed in a model or a query to a database or knowledge base or if you are interested in cognitive science the mental status of the speaker or even any other kind of grounding in semantic grounding in the world the reason i'm saying that this is mostly deterministic is because there are some approaches now uh which separates the concern um they consider some cases of stochastic uh what they call the stochastic annotations where you actually have a denotation is a probability distribution so those are pragmatic models that are some of them are very interesting work done by dan lassiter and noah goodman at stanford but essentially for our purposes here those this is an execution step that is deterministic once we have the semantic representation so examples for the messages the in the fragment of arithmetic fragments for english one plus two the semantic representation in scala could be there are many more but one of them could be add one and two and the notation is is three uh um but as i mentioned before this is a non-determinate non-deterministic step uh one of the reasons is that in language we have uh ambiguities natural language are ambiguous in several senses one of them one of the those senses is ambiguity at the syntactic level so in this case we can have either a semantic representation which is a valid semantic representation add a negative 2 and 3 as you can see from here and the denotation would be 1 or another semantic representation negative at 2 and 3 and the notation as you can see here is is very different is -5 and both are perfectly valid semantic representations another source of ambiguity is lexical ambiguity where we have one word we would need to disambiguate it crane can be either a bird or a machine and we have to get some um we have to disambiguate in some way while we are doing the semantic parts and decide that we have one possible kind of bird or the machine more examples two is less than three we can use this operator but the main idea here is that the notation can be a true value so the notations are very different objects in in principle as well as we have semantic representations which can be operators with complex operations in the semantic representation with this is the notation the main idea is for this 2.3 composite out of a message a semantic representation and our denotation is that we can derive from a given sentence the notation right meaning but the the way we actually do this we model this in uh in linguistics is by using a principle that we consider that is underlying almost every possible field in linguistics which is the compositionality principle this is um stated um attributed originally to freyja although there has been some dispute if frege would actually consider this to be right but in any case in one of the modern there are several modern formulations one of them is that of barabra party which is a mathematical linguist in university of massachusetts um importantly the meaning of a sentence is a function of the meanings of the parts so the meaning of the words but very importantly and the way they are syntactically combined so it is important to realize that the meaning of a sentence is not only the meaning of the individual words but also we have to take into account the modes of composition because that's crucial to uh to be able to generate models in a simple example to illustrate this is the case of all linguists and engineers which is equivalent to minus two plus three in our arithmetic fragment we can have two possible parties we are going to focus on all so we can have either all linguists and engineers we can construct these semantic trees with type annotation the meaning of this sentence is that of a group of people where the linguists are old and then the engineers can be their young or old which is equivalent to this one here or could be their old linguists and engineers this is a problem of a well-known problem of scope one of the interesting ideas is actually in linguistics to use this kind of approaches to understand the scope and scope ambiguity structural ambiguity like in this case that's it so is there any resolvers because like you normally would sue for world knowledge you know more older linguists than engineers right the engineers generally very young i mean is this something would you use more knowledge for this implication that's that's a possibility yeah definitely that's a possibility you would need we always need to separate concerns in this case the as much as context as we can use the better it would have abs disambiguating but if you if you don't have i would say that the key idea is that if you don't have context available you couldn't discern which one of those are actually exactly yeah but that's a very good question that is going to be related to what we see um if we have time in the in the continuous representations uh as fairth was making a point related to that so um if we want to actually learn how to derive meaning from utterances um this is a important problem in natural language understanding and very recently perciliang and chris potts have been proposing a framework that synthesizes approaches they it's very interesting to me this quotation where they consider that composing compositionality characterizes the recursive nature of our linguistic ability required to generalize to a creative capacity so uh confessionality they consider that is essential for us to to be creative using language and they separate concerns and consider that learning details the condition and the which sustainability can be acquired from data and they propose several possible a framework that considers several possible varieties we are going to see actually one of them so essentially they are this they are proposing that we have a learning challenge of learning compositionality there are several possible ways but to me one of the crucial aspects in the last few years has been this proposal by perciliang learning in this paper learning dependency based compositional semantics where percy was proposing that if you remember the 2.3 we have with utterances and answers the traditional approaches to these problems have been learning from utterances and logical forms that are in the in in a form of annotated data which is extremely useful is the way we actually got uh parsing working with help of course of all the work done by by mark liberman in pennsylvania uh because having having this annotated corp disantected banks is very important and we can we can actually learn but especially for logical forms these are extremely extremely difficult to construct and very difficult to maintain uh so is actually a problem to have a large data set of logical forms is is just um very difficult so one of the uh main ideas by uh percilian and his collaborators in that paper is that actually we can learn these logical forms these semantic representations as hidden variables using utterances and answers so pairs of messages and and denotations uh as our training example so if we have uh questions like state which is the state with the largest area in the u.s and the answer alaska we have lots of them what are the movies where brad pitt is the main character and the list of movies here as an answer their proposal is that we can learn from these pairs the logical forms as hidden variables and that's actually something i'm going to to show you here and a very simple example that how how we can do this which is actually a structure prediction problems we can separate this in into four pieces essentially initial grammar that we have to refine during the learning these are very large initially and the reason for this is that in our arithmetic example with one plus two we all know what one is what plus is and what two is but actually if we want the machine to learn when the machine is initially seen is something like this this is any of you recognize this is yeah yeah this is a actually imagine writing from uh southern mexico and guatemala uh so this is basically um uh what um a machine would say if uh is trying to learn uh actually to decipher these these glyphs is exactly the same problem uh so i'm telling you that uh some of those uh heads uh these are logograms are numbers and one of them is a function just to to make the the problem easy under the notation i can tell you these five uh the question is that we initially have to guess that uh this head is uh that's the help i'm giving you a little bit right is either add soup or subtraction or multiplication this head can be either one two three the idea is that and this one also right one two three we have to we have to actually learn what are these values from pairs of sentences like this and the notations like this so if we have different examples in this case we are changing this one for this one and the denotation is different we still need to to propose some values right we have another example where we have the same head as uh initially but this one is different to to this one but the same operation and the notation is now different by using this method we actually can end up learning the possible values in fact this logogram is to be a red shock in imagine which is to to count to uh to add actually numbers this one is chan which is four hun which is one this is cha two and this is whack six so the system is able to to learn these things but it has to learn them so it is it would not i wouldn't consider that this learning if we actually inject uh these uh values as if we provide the system with this mapping which uh it has been a common case until 2005 i i think with some proposals from seattle modern and collins how we can learn this lexicon which is one of the problems we have but the idea is that we end up learning so this initial grammar is refined during the learning process we need also a feature representation of the data which i'm going to to focus a little bit and then an objective function and an algorithm for optimizing the objective function which are actually these are actually solve problems right now in machine learning for this specific task the question is how we can we could propose a feature representation of the data and in order to filter efficiently initial grammars so for example in scala we can use in order to represent the initial grammar we can use this gl parcel combinator library from daniel spiwak we generate from every possible in a given message we parse and we generate every possible function every possible class here for every number we generate all the possible denotations for those numbers and then for that parts that is this parsing algorithm is able to handle ambiguity so we generate a stream of success of successes every every possible tree i'm going to show you later that we have lots of trees and we have to actually prune them the k in the classes that we are using here interestingly can be considered and this is one of the nice features of using scala can be considered to be an algebraic data types so these are a combination of some or co-product types and every one of those actually is a product type resulting from from combining these types and this is very interesting because if we use algebraic data types those are defining an algebra an initial algebra and we can consider that we can calculate the denotation from this initial algebra by deconstructing by breaking the tree using just a single function which is the catamorphism over that uh the carrier of this initial algebra so by applying just a generic operation we fold that tree and we get the denotation at the end so and this is interesting to me because it's somewhat related to this idea of compositionally building the denotation from this semantic representation as perciliang and chris potts mentioned compositionality outlines our recursive interpretation process and with the lexical items in in this algebraic data type in our case are listed as base cases and the recursive clauses define the modes of combination in our case again we are capturing this with a full generic transform form with a folding as a generic transfer for any algebraic data type so this is just the fall function for that tree and with that we are able given a parse for that tree we just fold it and we get the notation but we have lots of trees right the question is that as we mentioned before for minus two plus three with the notation of one we have lots of trees uh because we need to uh actually provide every possible combination so in this three here two is is one of the possibilities and three is there but this you if you look at this three two is mapped initially to three and three is mapped initially to four um we calculate by folding these threes the notations we are going that to see that some of the trees uh they actually have correct denotations like these three here but not those ones right so we are going to actually the algorithm is going to prune them it's going to filter them because they don't have the same denotation as we we expect the notation for these sentences is one so those are going to uh we are going to get rid of them but as you see here we still need if we only would have this a simple example we would end up having different possible in principle correct trees right so this is to say that we need data and uh especially uh as much data as we have for these algorithms to learn well from pairs of utterances and the notation so they are able so the main idea maybe for you is that they are able to learn the semantic representations but we need data uh because precisely of this reason right to avoid uh to be able to learn this mapping because the mapping is highly ambiguous if we can implement a polymorphic stochastic subgradient descent in scala and the interesting thing here is using this transformation the denotation function as we were mentioning is just the this fall and we just predict and it is very straightforward implementation of the gradient descent for the perceptron is an extra structure perceptron algorithm would actually we are seeing here so we have some results with a very small training data set like one plus one one plus two one plus three and many others and more complex the interesting thing is that we are able to learn like minus three three plus two is able to learn more complex things like like minus two um plus three times four let's say but interestingly uh what we provided initially was um we um we wanted to to have some um let's say how to say this we didn't provide a four initially in the training data set so you are able to so you can see that the prediction of the algorithm he the algorithm makes the best guess it can but it didn't see that for in the training data so it's not able to uh to actually uh good at a prediction right so it's it's not correct but in general i mean if you have enough data uh these algorithms are working extremely nicely and is really this is a very promising avenue uh for actually doing semantic parsing for getting those systems that understand us and avoiding problems like we saw before in in the wolfram alpha case so these are up to this moment uh discrete representations of data you have a question i was just wondering about like interpolation versus extrapolation like what happens if it doesn't know that four is a part of its ecosystem like how did like i mean if you're extending this beyond just numbers and some kind of concepts it could probably guess a location between a concept but how does that know how to go outside of that uh absolutely absolutely so these are discreet representations they have a great value my perspective is that we should be able to to use discrete representations as maybe as a case limit as we maybe we can talk about this later but this is very interesting this one actually one of the uh limitations we need to learn those um uh mappings to those grindings to to the lexical items right that's a very complex that's actually a research question how we can do better and you you made this this great point because again this is the next step is actually uh that we are working very hard right now is how we can actually use continuous uh representations so distributed uh word representations to actually elevate this kind of problems and do better in semantic parsing so this is what we are working right now i don't have code for this part of the of the um i would love to have the the code already right this is part of my research for my qualifying paper um but we are working very hard on this so i'm going to give you a glimpse of the ideas that we are considering uh to be able to learn compositional semantics in distribute distributional approaches how many of you went actually yesterday to marek's talk so okay and and how many of you know what were vector representations or distributed yeah so most of you in any case i just uh very briefly the distributional hypothesis and and all the goodies that we are having from the deep learning come essentially from several assumptions in or several hypotheses stated in the 30s 40s and 50s essentially by sally harvey some fierce ferg was making this famous quote you shall know a word by the company it keeps right the idea is that the complete meaning of a word is contextual and that if we know that context we have to take into account the context but if we know it as harris was also making pointing out we we actually are a we can encode the meaning of the of the word using this distributional approach harris mentioned that distributional statements can cover actually all of the material of a language which is something is kind of controversial and i would love maybe later to know mark your opinion on this it's controversial it's very interesting i would say some people say or consider that with work they are able to learn most of it but this is a controversial uh aspect right we are considering this is this for maybe not for granted but as a assumption general assumption in distributional semantics um antonio pantel mentioned that if units of text have similar vectors in a text frequency matrix then they tend to have similar meanings which is which are to me three of the pillars of this distributional approach so very in a very succinct way um if we consider these nouns which are represented as vectors here the first element of the vector is a concreteness in this very simple example the second one is so this is concreteness i guess that this is concreteness this is another semantic feature let's say a different semantic feature that we have for for is is not that relevant at all uh initially i'm very interested in those things but uh not for this problem and the last element is bias there are if we consider the adjective unpredictable to be represented by this matrix we can formulate rules like adjective noun composition as a matrix vector multiplication right and if we feed nouns in a neural network we can consider that the adjective multiplications in in in the weight learning and we apply the sigmoid and we get in in this initial layer um a function that is interestingly of the same semantic type uh a vector that or in our case a number but in in general can be a vector that importantly is of the same semantic type as the uh the other one so in this case we have a noun adjective composition to give a noun phrase this would be of the same semantic type and this is important because they can compose we can we can then use these systems initially to to learn compositional semantics but this is the research question so it is interesting by itself because by doing this for example we can understand this very nice phenomenon that are unpredictable it's not the same to say we are not it has not the same meaning when we say an unpredictable uh movie or even an unpredictable rollercoaster which are aligned along this axis which could be considered to be good aspects of a movie or a roller coaster but definitely i wouldn't like to use an unpredictable website or an unpredictable plane right and they are aligned along this axis so by doing this matrix vector multiplication this model is able to actually learn this kind of difference in meanings for uh an objective that the surface form is the same but the uh the end meanings are very different so that's one of the reasons why these approaches are extremely uh promising there are different architectures for composing distributed representations one of them is algebraic composition where we have the ways we combine vectors can be either following a general addition law or an addition or a general addition or multiplicative tensor people have been using many or proposals proposing many different operations for these compositional functions there are also other models the parameterized composition or lexical function composition and especially this model the mathematical foundations proposed by cook itol using a category theoretical approach basically they are able to me the interesting aspect of their proposal is that they are able to using one category they can project montagobian semantics in a discrete basis or they can also get distributional semantics by projecting the same the same underlying vectors in a different basis so this is very promising the problem is that it's very complex and we don't have implementations so to give you an example for the word for it has to be considered as a five a tensor of order five in this model which enables um if we we want to implement a model of a very simple sentence the vector representations that we end up having are extremely extremely large i mean the um a number of dimensions is extremely large and it's not computable there are a third approach in from this architecture perspective which are the recursive composition uh that brings up all the neural networks uh families like the recursive neural networks the current lstms or convolutional neural networks and i have to say that to me again this is a very this is some this is the research that we are doing in uh right now uh which models uh which architectures do we need what kind of compositionality we can learn from these models to me convolutional neural networks are extremely promising because of the fact that they are able to model non non-linearities even if the convolution in principle is a linear operation in in the transform space but to me dynamic convolutional neural networks which are non-linear are very promising extremely promising but i have to say that the the the hero in in uh all this is actually um sam bowman is one of my colleagues at stanford and he has been able to show that we that we are actually able to learn logical semantics using recursive neural networks so this is to me actually a huge success because it's one of the very very first results applying deep learning techniques um distributed world representations to actually learn uh some aspects still some aspects of compositional semantics again this is that i would say one of the hottest topics of research in natural language understanding right now because if we are able to get good results we will be able again to model compositionality and from a quantitative perspective and therefore we would be closer one step closer maybe this one percent you were mentioning yesterday uh mark um to this promise of having better understanding systems that's all thank you i think we have one minute for questions um have you have you had like have you uh this is the guy that has seen me who did uh semantic compositionalities and uh categorical combinatory grammars uh-huh is that something like what would be a difference like a quick difference between like using a recurrent neural network or uh learning semantic compositionality versus something like the ccg course yeah i mean that's a good question ccgs are a formalism with which you can actually propose discrete representations uh so for example if you use lambda calculus which um an extension of which um basically you you can you can use lambda calculus in combination with categorical combinatoric category grammars you can create these distributed representations at these uh discrete representations and you can use any kind of uh um algorithm that we talked in the first part of the of the talk right like settle modern collins for example actually they use in 2005 they use a probabilistic part series incoming categorial combinatory combinatoric categorial grammars ccgs with very good results because they were actually the first ones being able to as far as i know to learn the lexical items this mapping this instant mapping in the initial grammar that we were mentioning in the beginning so i guess that they are not they are not orthogonal approaches the group so both cook and collaborators the people from oxford they are using this they are proposing this framework category theoretical framework which actually when you want to model the relations and the syntactic relations between in a sentence they use categorical grammars or some kind of so i guess that they are not orthogonal approaches thanks oh uh so could you elaborate more on the scaling like how like as you're adding additional representations how is this how does it scale like in kind of big o style and then are these representations dense or sparse is that you mean in the in the distributional um in this distributional approach no i mean i i don't know if you mean in the distributional approach or in the discrete in the in the discrete uh well um i would need to look for the theo and of the i mean the order of uh the complexity of the of the algorithm um scalability is one of the of the issues that we we actually have this is something i discuss a lot with people that are working in some companies in in the bay area because they wanted to use these approaches but this uh is i would say a technical concern the problem so the gll algorithm for example the complexity is thank you right the problem is not the the uh per se the that complexity but the the huge number of possible parses that you generate depending on on the on your task that depends on your task because you are defining the number of lexical items right so i would say just maybe to to give you a short answer the complexity is always the same problem that we have but in addition to that we have the a combinatorial explosion of possible parses which is the catalan number of more than you know is the number of lexical items times the catalan number which is more than exponential so that's that's why we we need to do like good job trying to refine the the size of the initial grammar that's a good point yeah can you briefly describe the training research like is that supervised or supervised is unsupervised as far as i i know uh isn't supervised in the in the case of uh that i showed here yeah the the the so it's not actually sentiment it's um that's a good point i would be because this is actually a example right um you get basically a value yeah zero to one where um um that's a good point i wouldn't say this is sentiment yeah yeah no that's that's a good point i'm going to to ask chris spots what is his opinion but yeah no i yeah i wouldn't say sentiment oh so we have okay the composability the example that you use for a tree and couples do you see that its compressibility may work do you see more like a more flexible data structure more like some graphic background instead of trees and couples well that's a that's extremely good question i would say that if we are able to model um i mean the reason for trees is because of our tradition in montagobian approaches where we are able to explain a big amount of the semantics of many languages by composing using semantic trees right um i would say that i i would be totally open to any other kind of graph that is uh able to capture uh the same amount of information like in some of those models we would end up having maybe none three structure if they we may discover that they perform better so that would be actually very uh very interesting obviously a more flexible data structure by adding to the works and some semantics that a tree find difficulty yeah i mean um actually one of the the very symbolistic graphical models uh to model semantics and pragmatics also right so these are the case of some uh other kind of graphs to that have this ability so i wouldn't be surprised if that would be the case but our initial approach is to to model in the traditional way but that's a good point thank you