Transcript
so uh today we're going to talk about a few miracles of learning in the context of um the theme that we're developing here in in the class we uh started off with a discussion of some basic methods talked about nearest neighbors and we talked about identification trees and those are kind of basic things that have been around for a long time still useful still the right things to do when you're fac with a learning problem and you're not sure what method to try then we went on to talk about some naive biological mimicry we talked about uh neural Nets and we talked about uh genetic algorithms and you look at those things you think reflect back on what we talked about and you have to say to yourself are these nugatory ideas perhaps pisin or are they super regulatory ideas that deserve to be Center Stage does anybody know what those words mean ayine well Pine is a Spanish coin it was so small it was of little worth these ideas uh these ideas like uh neuron Nets genetic algorithms i c classify them as pisin because getting them to do something is uh rather like getting a dog to walk on its hind legs you can make it happen but they never do it very well and you have to think took a lot of trickery and training to uh make it happen so so uh not too uh not too personally high on on on those ideas but we teach it to you anyway because of course we're we only editorialize part of the time and part of the time we like to cover what's in the field today uh we're starting a couple of uh discussions of mechanisms or ideas or things to know about that are quite different because now we're going to focus on the problem rather than the mechanism and then a little later on we're talk going to talk about deep Theory F iio for its own sake but this week I want to talk about mechanisms that um that were devised I want to talk about research that was done let me not say mechanisms let me say research that was done to to uh to to attempt an account of some of the things that we humans do well sometimes uh without even knowing that we do it now chrishan here tells me his first language was telu telu I once had another student whose first language was telu I said to him that must be one of those obscure Indian languages and he said yes it's uh spoken by 56 million people French is spoken by 52 so uh he's going to be our experimental subject Krishna if uh I pluralize words you know what it means to pluralize a word so if I say for example um horse then if I ask you for the plural you'll say horses so if I say dog what's the plural dogs or in no no in English oh dogs and what about cat and he got it right is that a miracle when when did you start speaking English uh second grade second grade but he still got it right and he never learned that he's actually pluralizing those words differently but he is so when you pluralize dog what's the sound that comes after it's a z sound Z dog Z if you stick your fingers up here you can feel your vocal cords vibrating if you stick a piece of paper in front of your mouth you'll see it vibrate but when you say cats the pluralizing sound is s like that no vocalizing no no vibration of the vocal course and old chrishna here learned that role as as did all of the other non-native speakers of English effortlessly and without noticing it you learned it but you always get it right how can that possibly be well by the end of the hour you'll know how that might be and you'll uh experience a a case study in uh how questions of that sort can be approached with a sort of engineering point of view you can say what if God were an engineer or alternatively what if I were God and I am an engineer think about how it might happen that way so we want to understand um how it might be that the machine could learn uh rules like that phonological rules not just that one but all the phonological rules you'd acquire in a course on phonology that part of speaking that deals with with with those Sy syllabic and subsyllabic uh sounds the phones of the language so when Yip and susman undertook to uh solve this engineering problem both being dedicated Engineers the first thing they did was learn the science so they went to sit at the foot of Morris Holly who would develop was was largely responsible for uh the development of theories of so-called distinctive features and here's how that works you start off with a person who wants to say something and out that person's mouth from some sort of acoustic pressure wave and if I say hello George and you say hello George everybody will understand that we said the same thing but that acoustic waveform won't look anything alike it'll be very different for all of us so it's a miracle that uh that this that words can be understood any case it goes into an ear and it's processed and out comes a sequence of distinctive feature vectors A distinctive feature is a binary variable like is the is the is the phone voiced or not that is to say are your vocal cords vibrating when you say it if so then that's plus voiced if not it's minus voiced so according to the original distinctive feature Theory and consistent with most of the theories that have been derived since the original one there are on the order of 14 of these distinctive features that determine which phone you're saying so if you say a that's one combination of these binary features if you say t that's another combination of these binary features 14 of them so how many how many sounds does that mean that in principle there could be in a language and what's two to the 14th Sebastian well that would be about 16,00 th000 don't you think 2 to the 10th is a th000 2 to the 4th is 16 so there are about 16,000 possible combination but no language on Earth has more than 100 phones that's strange isn't it because some of those choices are probably excluded on physical grounds but most of them are not so we could have a lot more phones on our language than we actually do English has about 40 so the sequence of distinctive features could be viewed as then producing meaning after perhaps a long series of operations but in the end those operations feed back in here because many of the distinctive features are actually hallucinated we think we heard them but they're not there or they're there or not they're not even in the acoustic waveform they're there for the convenience of the phonologists who make rules out of them it's a remarkable how much um how much uh of this feedback there is and even injection from other modalities many of you may have heard about the murk effect here's how the murk effect works look at me while I say g g g g g g g okay I said GA now how about ba ba ba ba okay I said B like a sheep but if I take the sound I make when I say ba and play it while I'm while you're taking a video of me saying G what do you think you hear you don't hear ba some people report that they hear a DA sound like da when I look at it I don't I can't make any sense out of it it looks like the there's a disconnection between the speech uh and the video but it does not sound like ba but if I shut my eyes and say ba ba it's absolutely clear that it's ba so what you see has a large influence on uh what you what you hear it's also interesting although a side issue it's also interesting to note that it's very difficult to pronounce things correctly if you don't see the speaker so many people wonder when they learn foreign languages why they can't speak like a native and the answer is they're not watching the mouth of the speaker I was uh talking to a German friend once and said you know I just can't say the Damned uml's right and he said oh the trouble with you Americans is you don't realize that American Cows say Moo but German Cows say Moo and of course I got it instantly because I could see that the uml sounds are produced with protruding lips which we don't have any we don't have any sounds in English that require that H but back to back to what we know from the phology about all this stuff you talk to Morris Holly uh he will tell you that over here I like to think of it as a marionette there are five pieces of meat down here and the combination of distinctive features that you're trying to utter are like the control of a marionette on those five pieces of meat so if you want to say an a sound the marionette control goes into a position that produces that combination so let's see what is that distinctive feature sequence look like for a typical word well here's a word a e p l apples and we can talk about what distinctive features are arrayed in that particular combination of phones so one of the features that they like to talk about is cabic slabic that roughly means can that sound form the the sort of core of a syllable and the answer is a can but these can't so it's plus minus minus minus down here are little ways you'll run into the voiced feature and for the the voice feature well we can we can do the experiment ourselves ah sounds like it's voice to me p no that's not voiced yep Z we already said that was voiced so that's the combination you see when you utter apples for the voice feature then another one is the continuent one that roughly says is your vocal apparatus open is there any is there no obstruction and so a plus p is constricted open this is open so that one happens to run right along with voice in that particular word oh and they're 14 altogether but let me just write down one more the the strident one that says do you use your tongue to form a little jet of air so you don't on a p P but you do on Z so that gets a plus so that's a a glimpse through a soda straw of what it would be like to represent the word apples uh in U as as a set of distinctive features all arranged in a sequence so it's a matrix of features it's a going down in the columns uh we have our distinctive features and going across we have time so first thing assessment and and Yip did in their uh effort to understand how phonological rules could be learned is to design a machine that would uh interpret uh words and sounds and things that you see so as to uh produce uh the sounds of the language so they imagin the following kind of machine the machine has some kind of mystery apparatus over here that uh looks out into the word world and sees what's there so I'm looking out of the world and I see two apples so what this machine might do then is uh at some point decide that there are two apples out there then thinking in terms of these guys as computer Engineers they think in terms of a set of registers that hold values for Concepts like noun and verb and plural and we've not done anything with the machine yet we' provided no input so those so those uh registers are uh all empty then up in here we we have uh a set of words and there are all kinds of words apple is one of them and those uh those uh words up there uh know about how the concept is rendered as a set of as a sequence of of phones that is say a sequence of distinct features then over here most importantly they have a set of constraints so we'll talk about a particular constraint a plural con constraint PL plural constraint number one and it's going to reach around and connect itself to some other parts of the machine finally uh there's a buffer of phones to be uttered and if they're going to flow out this way to the speaker's mouth and get translated into a acoustic waveform so that's uh those are the elements of the Mach machine uh now how are the um how are the elements connected together well the uh the words are connected of course into the buffer that is used to generate the sound over here on the far left the plural register is connected to what you see in the world what you see in the world is connected not only to the plural register but to all of the objects in the word repertoire this plural constraint here uh deserves extra attention because it's going to be desirous of actuating itself in the event that the thing observed in the world is plural there are lots of them so that's it's going to be connected then to the plural Port there's going to be a z sound Port down here connecting to that final element in the buffer and finally uh over here is going to be a plus voiced Port which is going to be connected to the second phon of this the sequence that's how the machine is going to be going to be arranged and of course this is just one of many constraints but it's a constraint that has a very peculiar property information can flow through it in multiple ways so we think of most programs as having an input and an output but I tried to be careful to draw circles here instead of arrows because these are these are ports and information can flow in any direction along them what I want to do now is just show you how this machine would react if uh I suddenly present it with a pair of apples like so so the assumption is that the vision apparatus comes in and produces the notion the concept of two apples so once that uh has happened uh that's uh operation number one then information flows from that meaning register up here to the Apple word so that's part of stage number two another part of stage number two is information flows along this wire and marks that as plus plural so operation number one is the activity the vision system activity number two is the flow of information from that Vision system into the word lexicon and into this plural register so far so good uh here's activity number three this uh this word is also connected to the registers and information flows along those wires so as to indicate that it's a noun but not a verb that's part of part number three three at the same time part number three information flows down this wire and writes a p l into those elements of the buffer now this constraint up here this box says well I I can now see some stuff in that buffer that wasn't there before so it says do I see enough stuff on my ports to get excited about expressing values on other ports well let's see what has it got um it's got the elements from this buffer also up here in step three flow the plural thing so it knows that the word is plural so it says is this voiced um p is p that's not voiced is this a z sound no that's not a z sound so it sees what it likes on only one of its three three ports so it says I'm not going to do anything I'm out of I'm order Comba I'm not in this particular combat so far so good what happens next what happens next is that some time passes and the elements of the buffer flow to the left toward the speaker's mouth so we get an A P L same as we had before but shifted over now what happens now what happens is that the P or the L is now in the penultimate position so information flows up here item number four oh I guess that's item number five item number four is the leftward flow of the word so in in Phase number five the p is witnessed by this constraint p is well sorry L is witnessed by this constraint we've moved it over one L is L is L is voiced so we have some flow up here like that that's number five now we have voiced and we have plural and we have nothing here so there there's a great desire of this buffer to have something written into it so now there's a flow down in there of Z as item number six so that's how the machine would work in expressing the idea that there are apples and the field of view real apples not plastic imitations so that's how the machine works but all those connections are reversible so if I hear apples then I get the machine running backwards and my ual apparatus can imagine that there are apples out there that's how it works that's just by way of background the machine that they conceived for using the phonological rules once they're learned and all the phonological rules are expressed in these constraints but since these constraints are such that information can flow in any direction they deserve to be called propagators and in the good old days when everyone took 61 they learned about propagators as a kind of architecture for building complex systems any event there's the assessment yep machine and now comes the big question how do you how do you learn rules like that well what we need is we need some positive examples and some negative examples and for the simple classroom example I've chosen the same challenge that I presented to Krishna we're going to have cats and dogs so we're going to look at the distinctive features that are associated with those words slabic oist continuent and strided just a four of the 14 features that are associated with each of the sounds and those words could you close a laptop please to just just um for the uh distinctive features that are arrayed in those words by way of illustration so here we have k a t c phonetically spelled and if we work that out let's see what is syllabic that's not that is that is that's not voice C nope a yep T nope Z yes that can't be right cats I misspelled it CU cats s there's a hissing sound but there's no voicing so that's not a z sound it's an S sound so that's not plus voiced it's minus voiced continuent let's see is my mouth open when I say k no a yes t no s yes and strident minus minus minus plus it's only with a Z with the S sound that I have that kind of jet forming with my tongue now we can look at dogs and now we have the z sound as the pluralization we know that because when we say it dogs yep there it comes out as a as a uh we're only going to look at the last two columns cuz they're the only ones that are going to matter to us so that's plus and that's um minus that's a plus and that's plus they're both voiced is that right dog G is G sound voiced yeah I didn't think so um G sound is voice oh it is it is voice but it's not a continu it's like that yeah cat dog go yeah it is vo and it has to be for my example to work out and that's minus minus minus plus so what we're interested in is how come one word gets an S sound and how come the other word gets a z sound well it's a pretty sparse space out there we've already decided that there are 14,000 possible phone names and there are only 40 in the language so that's one thing we can consider the other way the other thing that we can think is that well maybe this is a logical problem like kind of problem you'd face if you were designing computer and so sesman you y got stuck for three months thinking about the problem that way couldn't make any progress whatsoever and that happens a lot where you're doing a search you think you've got a a way of approaching it try to make it work stay up all night stay up all night again still can't make it work eventually you abandon ship try something else so then they began to say well let's see all we care about is the stuff before the two ending sounds we care about that part of the Matrix and we care about that part of the Matrix and we can ask in what ways are those things different and they're different all over the place that's why they're different words we can ask the question a little bit differently and we can say what can we not care about and still retain enough of a understanding of how the words are different so as to put the proper PR ending on them and they worried about that for a long time couldn't find a solution the search space was too big and then they said maybe what we ought to do is we ought to think about General izing this guy here so that we don't care about it so now we don't care about that guy and then he went down on through here saying well let's see when we can when we have to stop generalizing because uh We've screwed up we've screwed everything up and we can no longer keep the z sound words separated from the S sound words so that eventually distilled itself down to the following algorithm first thing they did was to collect positive and negative examples and there there's a positive example and a negative example that's not enough to do it right but that's enough to illustrate the idea so then they next thing they did was something that's extremely common in learning anything and and that is to pick a positive example to start from it's actually not a bad idea in learning anything to start with a positive example so theyve picked a positive example and they call that a seed so in our particular case cats is going to be our seed and the question we're going to ask is what are the words that get pluralized like cat so we've got a positive and negative example we picked a seed and now the next step is to generalize and what I mean by generalize is you pick some places in the phony M Matrix that you just don't care about so when you may pick a positive example and you don't care about it so you change it to an ascaris or as demonstrated in the program I'm about to show you a ball or you pick one that's a NE negative and you turn it into a ball both so cats this seed becomes a pattern and in order to pluralize the word this way you have to match all the stuff in here but now what we're going to do is we're going to gradually turn some of those elements into don't care symbols until we get to a point where we've not cared about so much stuff that we think that we pluralize that one with an S sound too so we keep generalizing until we cover that is to say we admit or match a negative example so that's how it works so we generalize like crazy and as soon as we cover a negative example we quit otherwise we just go back up here and generalize some more and now we got to pick a search technique to decide which of these guys to actually generalize when we could pick a we could pick one at random and they tried that and didn't work but what they decided is that the thing that influences the pluralization most is is the adjacent phoning and if that isn't the thing that does that solves the problem it'll be the one next to that so in other words the closer you are the more likely you are to determine the outcome so these guys over here are least likely to matter and those are the ones that are generalized first right so if we do that what happens looks like we're going to come in here and see that there's a big difference between the nonvoice T and the voice G but that's only a guess because i'm want to show you a fraction of the 14 distinctive features that are involved so I suppose you like to see a demonstration yeah so there is our 14 features and that's our seed there sitting prominently in the display with pluses and minuses indicating the values of the distinctive features for all three of the phones involved that funny left bracket isn't a mistake that's just one convention for rendering the ass sound in cat so it's pretty hard to tell from just that Matrix what's going to be the determining feature that separates the positive examples from the negative examples you notice that there are actually two examples down here there's cat and duck is ducks got an S sound duck yep so Dog and Duck they both get pluralized with an S sound on the other hand Beach doesn't that's beaches dog we know that's a z gun Gunz so that's not not not in the group so we can run this experiment no here we go generalizing like crazy generalizing generalizing generalizing from left to right so nothing in the first two columns matters now we get to the T wow there it is so it looks like you pluralize with a s sound the S if and only if you're voiced you're not voiced and you're not strident in the second to the last in in the last in the last phone of the word that you're trying to uh PL I so that's one phological rule that the system has learned and guess what it's the same rule that's found in phological textbooks so now we can try another experiment so this time we're trying to deal with dog and gun and our negatives are the what was previously positive plus Beach which is still in there as a negative example so let's see how that one works nothing matters except to the last column the last phone and now we find out that if the if the last sound is voiced then the pluralization gets the z sound a voice Terminator I'm finally just to deal with beaches that's Beach and it's funny phonetic spelling so now it's if the second to the last if the if the final sound in the word is strident if it's got this Jetty Sound Beach beach then uh it gets the es sound so let's go back to experiment number one because I want to point out one small thing about the U way this works you'll notice that it talks about coverage excluded down here in the lower left hand corner excluded well there are three negative examples so they better all be excluded you don't want to cover any of the negatives but it says coverage two and two that's because it actually is doing and now we have the vocabulary to say it quickly it's doing a beam search through this space so it's not just doing a depth first search it's doing a beam search so as so as to reduce the possibility of overlooking a solution so it says oh the coverage both of the beam search elements cover both of the of the um of the positive examples and they in in fact have converged to the same solution so that's how the assessment and Yip thing worked and then the next question to ask is of course why did it work so the answer as articulated by susman and yep or rather more by susman rather more by Yip and a little bit less by susman YP thinks that it worked because it's a sparse space and when you have a high-dimensional sparse space it's easy to put a hyperplane into the space to separate one set of examples from another set of examples so let's consider the following situation suppose we have um a onedimensional situation and we have two white examples and we have two purple examples well too bad for us you can't separate them but now suppose that uh this is actually the projection of a two- dimensional space that looks like this here are the white examples down here and here are the purple examples up here now it's easy to see that you can separate them with a just a line that goes across like that let's take this one more step and suppose that this is actually a projection of a three dimensional space it looks like this this will be Dimension One this will be two going back there and this will be three up here and suppose that the positive examples are right here on this line let's say this is where we're going to draw a little little Cube like so suppose our purple examples are up there how many ways are there of partitioning the space along those axes well now they're they're not not even just two they're three so one way to separate the purple from the white is to draw a hyper plane or in this case it's just three dimensions so a plane through here uh on the on the on on the number three axis you could also put a plane in on that Axis or you could do both so in one case your dividing line would be um see on the first axis it would be one2 and then don't care don't care another solution would be don't care and then we divide on the number two axis with a PL at 1/2 and don't care or we could do it with uh2 one2 and don't care so the higher the dimension of the space the easier it is sometimes to put in a plane that separates the data that's why seson and Yip think that we use so little of possible phoning space because it makes the thing learnable that's one possibility so one explanation for a smart space learnability there's another interesting possibility and that is that if you have a sparse space High dimensional space with 14 dimensions and if the 40 points of your language are spread through evenly throughout that space no let me say it the other way if they're placed at random in that space then according to the central limit theorem they'll be about equally distant from each other so it ensures that the phones are highly separ easily separated when you speak but if you go to ask a linguist if that's true they don't know because they're not looking at it from a computational point of view but we can look at it from a computational point of view so I did that after susman you published their paper and here's the result this is a diagram that shows all of the phonemes that are separated by by exactly one distinctive feature so if you look over in the in this corner here you see that the constants W and X are separated by exactly one distinctive feature so they're not exactly distant from each other in the space on the other hand they are pretty easy to separate relative to the vowels which are up here in this part of the diagram which are all tangled up and the valves are all close to each other so guess what valves are much harder to separate than constants not surprisingly because they often because there are many pairs of them that are different in only one distinctive feature all right so now you back up and you say well gosh that's all been sort of interesting but what does it teach us about how to do science and stuff and what it teaches us is that that this is an example this is example which we can use to illuminate um some of the thoughts of David marah who I spoke of in previous lecture connection with vision but here is um here's Mars catechism I can't spell very well so I won't try to respell it but this is Mars catechism so what Mars said is when you're dealing with the an AI problem first thing to do is to specify the problem gee that sounds awfully normal and the next thing is to devise a representation so to the problem the third thing to do uh vocabulary varies but it's something like determine an approach sometimes I'm thought of is a method and then four pick a mechanism or devise an algorithm and then finally five experiment and of course it never goes linearly like that you start with a problem and then you go through a lot of Loops up here sometimes even changing the problem but that's just the scientific method right you start with the problem and you end up with the experiment but that's not what people in AI over the bulk of uh its existence have tended to do what they've tended to do is to fall in love with particular mechanisms and and then they attempt to apply those mechanisms to every problem so you might say well gee neural Nets are so cool I think all of human intelligence can be explained with suitable neural net and that's that's not the right way to do it because that's mechanism Envy you fall in love with a mechanism you try to apply it where it isn't the right thing this is an example starting with the problem and bringing to the problem the right representations C distinctive features once we've got the right representation then the constraints emerge which enable us to devise an approach write an algorithm and do an experiment as they did so the susman Yip thing is an example of doing AI stuff in a way that's congruent with Mar's catechism which I highly recommend they could have come in here and said well we're devotees of the idea of neural Nets let's see if we can make a machine that will properly plur pluralize words using a neural net that's a that's a loser because it doesn't match the problem to the mechanism it tries to force fit the the mechanism into some procrasti and bed where it doesn't actually work very well so what this leaves open of course is the question of uh well what is a good representation and here's the other half of Mars catechism characteristic number one is that it it makes the right things explicit so in this particular case it makes distinctive features explicit another thing that Mar was noted for was stereo Vision so in that particular world discontinuities uh in the image when you go across an edge with the things that were made explicit once you've got a representation that makes the right things explicit you can say does it also expose constraint and if you have a representation exposes constraint you're of and running because it's constraint that you need in order to do the processing that leads to a solution so you don't have the right representation if it doesn't expose constraints not you're not going to be able to make a very good model out of it and finally there was a kind of localness criteria if you have a representation in which you can see the right answer by looking at it descriptions through a soda straw that's probably better representation at one it's all spread out it's true with programs right if you can see how they work by looking through a soda straw you're much better situation to understand something if you have to look up here and there and on the next page and in the next file so all of this is basically common sense but this is the kind of common sense that makes you smarter as an engineer and scientist especially as a scientist because if you go into a problem with mechanism Envy you're apt to study mechanisms in a naive way and never reach a solution that will um be satisfactory