Summary
Notes
Transcript
First of all, In your... Intuition is doing anything context for you when it comesUm... A good way to do it. Go. Shadding the content. More often than not, we were just going to... You missed some information, right? Indeed, you will not do a perfect job here. I see a simple I look at Google. I expand that symbol. What's the difference? What's the other problem that you can see? Possibly here. I see a symbol.
Thank you. production rules, the ways to expand it. The white shoe, which one is it? That's a problem, but we'll address that later. So does it make sense with context-free you're breaking down your sentence into little grammatical components without any regard for the whole thing. Oh, I matched that sequence of two words or whatever to something. Okay. Go. Yes.
I was just wondering if this bar, if we can identify parts of speech using the bars that we can see over here, verb, nouns, pronouns. Basically, how would this... This thing, how will this be used?
Given what we've seen about getting marco models for partial speech study, Okay, so this is the next step after the part of speech tracking. This is when we are talking about the pipeline at the beginning of the semester. Things are happening in sequence. You're kind of extracting pieces of information. So to get here, you do have to doWord of speech tagging first. Many will have a And now here I These will be already assigned to your...
The parsing does not do the tagging itself. Tagging is already done. Or better or worse, right? So imagine what happens when part of the speech patent fails and you do a good job. The following task will probably be... Incorrect either, right? So, let's do some mathematical addition. Sigma, a set of terminal symbols, these. Sir. About the same. A set of rules. Productions of a form A produces a beta.
Where A is a known terminal symbol and beta is a string of symbolsThat comes from, An infinite set of-strings that are Some combination of what comes from a variable and a sub-variable. What comes from a terminal? Long story short, This, the left side of your production will always be a non-terminal symbol. You can't replace it with something. What's on the right will be a combination of any length.
Made of terminal and non-terminal sets of goals. Does that make sense? And there is a special S symbol designated start symbol. This is where you start the breakdown. This usually will mean the sentence as a whole. As you can see, the S is always on top, and then we try to break it down. We have a little more. A little more there. Right in here. The derivation. What is a derivation? I can turn one stone-into another using a production rule.
The direct derivation is what I canAnd go from one side. Spring. Whatever spring. By applying one specific form. Think about it this way, OK? I have x and b is some standard for a digit, right? you I can divide xEight. Y out of it. That's a direct derivation. I can change this string into that. I replace it with B with... Thanks. I don't have to replace x and y. I could possibly do it. What is a derivation altogether?
It's a sequence ofDerivations. In other words, converting one string into some nth string. Multiple direct interventions. The law. Derivation is used to-Decide whether I can derive a specificSix sentence from the other one. Now if this isConfusing and a little too much. Matthew, think about it this way.
This is an open sentence, right?
If you look at the parser, you have this input sentence at the bottom as terminal leave nodes of that parser, correct? This is where I start. This is a strength. with just one symbol. Through multiple Derivations. I moved. S. That's how it goes. That is the problem. This is a. This right here It's a direct derivation from "ask" to a combination of a noun phrase and a verb phrase. The NP MPAnd repeat.
In that role. are derived from x. This is a string of symbols. Nothing more, nothing less. Can we further? Use downstream to derive something else from it. All right. Now here's a, Thank you. Let's test your mathematical notation understanding. What is a language then? Would you agree, so we've been talking about languages here, syntax, semantics, right? More or less formal way. What is a language mathematically speaking?
Can someone read that for me?
It's a screaming of a super-historian. Just once, three.
Many should. So a language is all possible legal things derived from the grammar. The grammar is confined to a list of terminal symbols and non-terminal symbols and production. So any sequence, any string that can be a collection, a set of all possible strings that can be generated by this grammar is called a language. In this case. All right, let's be, specific. Those strings that we generated from the normal arc are all wind strings.
based on the terminal symbols. I have a grammar, I'm using those NPs, VPs, and what not, but ultimately I'm Getting that Final. sequence of terminals in the work. That drummer cannot produce a simpleprefer I flight morning F, right? That grammar will not produce a sentence on F. That is not part of the language. Does that make sense? That sentence is not part of our English language, though. For entertainment, you can just be playful and...
Say it's like this, I'm just waiting on it. From a mathematical perspective, this is not part of the language becauseMy grandma cannot any sort of that derivation to create that central sentence. I know it's a little informal, Ask me if I will ask you about that formula on the exam. All right, so now that kind of leads us to a grammatical version of grammatical sentences. It should be pretty easy to understand.
Grammatical sentence can be derived using the grammar rules. I can create a parse to get it. Generate a certain sentence. The sentences that I cannot generate from using that grammar are illegal. Okay. How would you use that information? So let's say that you did all the part of speech hacking, blah, blah, blah, you were ready, and I'm giving you the grammar. Formal grammar, just like the one I was describing before.
Okay, and you are capable of telling me that a sentence that you're looking at is ungrammatical or grammatical. How could you use that information downstream? You have a little block. That takes in sentences with part of speech hacking. That block has a grammar built in. Does the little dot that tells you yes or no mean you're enough? Yearly. Pro-medical or pro-medical? How could you use that in front of me?
Sound director, perhaps? That's a very dumb use of that, but you could do that, right? Now this terminal symbol is going to be... The misspelled word would not be a terminal symbol, right? Reject. Grammatical ordering. Don't worry. We're dead. Bless. Translation. You just produced a translated sentence, right? And you have a grammar in this other language. You run that translated sentence to the grammar.
Wait a minute. This is not grammatically correct in English. That means that your translator is not Is arson clear?
Right now?
Specifically, it does. Syntactic parsing. In grammar, in a sentence, that is part of speech that, I can't perform the following-Any family who could do that? means that that sentence is grammatically correct according to my grammar. All right, but now... Let's try to find a way to do it efficiently. What are the relationships between you and me? Thank you. Components of your sentence. By the way, are you familiar with-BNF or Bacchus and Allen.
Warm. It's a special way of writing. But if you look at this grammar right here, does it remind you of something from CS4A? Proposition with no logic actually has C in that form. This is a set of perpetual rules for How about using a grammar for10 minutes. This is a groundwork. We'll call our medic. You have an arithmetic expression. You can turn it into another arithmetic expression. Separated by an odd.
What is an odd? Plus minus times. Goodbye, buddy. or a number and so on and so forth. Does that make sense? Um. Given theFrom the naming convention that I used before, what are those? Grammars are made up of rules and lexicons. This is a lexicon. These are your possible words that you could use. Our Plus minus multiplication and division symbols. Ordo lexica. Lexicon or terminal symbols, I think you can't really place them by hand, so...
Your math understanding, are these Two good parse trees for the same expression, one plus two. Minus three. Well, can you break it down? 1 plus 2 minus 3, and you will get the same thing. The same outcome. 3 minus 3, right?
Different ways. Correct? That's three and 0. So. What you see right here are two parse trees corresponding to the same sequence of, same sentence if you please. The relationships between different parts of that string are different in those clusters. Partly bold, grammatically correct. Yes, they are, because I was able to use grammar rules to get from the ride business and the economy. Thank you. What?
I managed to do that in two different ways. That means that my drummer is beat. I'm giving it one input. And it could possibly give me more Am I going to be happy with multiple parts? No, why not? Right. I have to do an extra work on my hand, okay? The parser, well, there's four options for you. Pick and choose. That's not helping in efficient computation, right? By the way, how would you resolve possibly, I'll show you, how would you possibly resolve an MDB label?
Another thing to think about is go beyond the arithmetic skills that we may be looking at That's two parse trees working in one parse tree. One is a verb, and the other part of the parseThree of one is a noun. Right? If we look at worse It's not the case, hypothetically, that could happen. The streets were the same, The terminal symbol is identified as a different part of speech. And I told you, That's some kind of gold, right?
If I have part of the speech assigned to every token and then I do some later, I'll be able to use that to resolve ambiguities. Apparently. You will not be a face. Just a minute. All right, so any thoughts how you go about Deciding, well, I prefer this over that.
You could fix that by perhaps, you know, forcing the groundwork to include current disease and whatnot. This is an example specifically designed to show you that a leak is a problem. This is an important concept of grammar equivalence. You could have Equivalent. What does it mean? We can have two drummers that Produce the same.
Equivalent grammar will produce the same terms. Now there's two levels to it. Leap equivalence means that Yes, they will generate the same strain, but that's-Yeah. You could generate that swing, it can be a tree, it can be different. Okay, good. and you iterate the same strings to the same derivations. How is that used to? Here is an example of two grammars that are equivalent. And they both will produce any sequence of A's and B's.
Very simple, just--One production role, no actually two alternative production roles, three alternative production roles. Which one would you use? A one, right? Because it seems simple. Or learn about-which structures are more frequent than the others.
So in other words, you would have a sentence and then a correspondingOur street that comes with it. Just like, you know,Award isPart of speech. I'll take it with a pat. One more time. That tree guy would have sent this. This is Sarah.
So let's talk about something that is called a constituent decision. Award grouping. That goes together essentially. It could be a phrase, but it could be something more. You've seen one already. some hints of that or phrases, don't phrases, you know, all these Thank you. All posted to us. Uh, can have a head and dependents.
-So ParseP is helping us find those things. The problems with Ambiguity are a little more complex than just having to use remarking of production sense. You can have a little kind of nuances to ambiguity. Structural This is an example of a strict rule on the Mr. Attorney, There's something called an attachment. We were. You're using the same part school, right? Or something that is attached in different ways.
Coordination ambiguity. Remember, we are looking at constituents. Which means cooking is not work. To give you an idea how How important that is.
Thank you. Right, keep that on. Two different constituents.
You will have to have the conference. So. We're talking about Parsley, right? Your parts are-One seeing a sentence like this. Either will produce a varsity that groups men and women in one year, or it will produce another varsity where there's two branches. I'll set the tape. Without any extra context, it will not be a capable cloud. Solving that mystery. I will show you later how You can make a guess, and if you did a guess on which one, Here's a new doubt contest.
So now you can resolve that problem. And again, this is where your engineering skills come in. you Do you realize that you're-application You have to build something on top of it. possibly allow the parser to give you multiple parse trees? Like, okay, I don't know, right? These are your two options I'm not picking. Does that make sense? And then you have something else built on top of it that will look at both of our strings.
So how do you So, how do we do the parsing mechanically, algorithmically? There's two approaches and sets of algorithms that go with both. You could do a bottom-up parsing, which means that you actually start with Terminal symbols, both words. And you try to map them. Rules until you get to them. Start symbol, before you start the list, start symbol and then you have like the rules to get here on the list.
String. Mr. Trump is back. Before I will show you one specific upbringing for doingCourse A. Talk about some invention of Mr. Chomsky. A Chomsky normal boy. Chomsky Normal Form is a way of converting grammars. I told you about What was it? Equivalent parameters?
Applies to Chomsky-Lobo. Mr. Chomsky came up with an idea and a procedure to take any context free grammar Turn it into a very specific form. This is The former. Any rule in China I'm speaking normal form. Will be... What does it mean? There's a rule that is definitely not an introspective rule. Whoa. This is an equivalent dollar, so that's one roll is broken down into three. -What's the difference?
Brown or sorry, equivalent? Rules that they will produce. Same strength, same sentences. You can replace one grammar with another without loss of anything. You can see immediately that this was just a single rule. Here we have three corresponding rules to actually make that happen. So it seems like I'm going for something more complex. Right. I'm moving from the last complex, However, there will be a benefit to you.
Let's not go into language specific. The difference right hereAnd you can see his category. Every section of the book of this classroom branches out with a branching factor up to at most. So it's either 1-Or two. Here you have three. You could possibly have five or whatever.
Okay, let's see, in a moment. It simplifies certain things. Any? One year. This is not something Just full disclosure, I will not ask you to do that. Should have been asked to becomeThe process of conversion, I don't care about. If you're interested, curious how you do it, there's an actual process to determine any rule that has more than twoSymbols. On the right side. Did you say what, one? We created using But The bottom line is, you are-Convert your ground.
Every those two symbols on the left. You will pay for it. No more rules. your grammar will become slightly more complex more around it. However,It is sort of a Precondition for circum-parsing of algorithms. Do you remember the other CNF form from Smith-Brady? Proposition of a law abjecting a various specific form of why we do it, because a certain algorithm would work with it otherwise. This is probably a key aspect.
Any strain of the length MWill require 2n minus 1 production formula, which says if you have a C in a formula. severeYou can predict. How many steps do you require?
That's one thing. And that too, and... There's also a tap. All right, that leads me to a parsing algorithm, a bottom-up parsing algorithm called CKY, so R-C-Y-K after three names that doesn't do that. Thank you. It's a dynamic programming algorithm. The only words under the essential area grammar is in French. Let me show you how it works, okay? And then we'll move back to... Further discussion. Errors and input.
It's a bottom up. which means that we started with words and we're trying to map The rules.
Going up and eventually get to the S symbol.
If I had more than two symbols at every level, At the brand new Have some 3D or-for the structure of the area.
Does that make sense? There is no constant UN that is made out of these two. According to my grammar, I cannot. There is nothing that connects them. What about this? It's soft. So what you see hereThere are possible ways of joining everyEvery pairMy sentence. Take care of words. What is the next diagonal from the Grouping of threes, grouping of fours, and then this will be, should be our final Now, this is where things will become tricky.
I think it's paraphrasing the third way to explain it, and actually not always to go with it. And finally, the last one. This cell right here is the most important of all. This is where all comes together. This is it. Bye Paul. If I'm not ableYeah. Yes, in that right corner. I am able to do it. One. There's one possible way. If I'm not able to do it at all, that means that that's, Thank you. I'm not able to go far enough from here.
Words and me. But there is one possibility that Does that make sense? Okay. So, number one, The fact that I arrived Yes. It means that there's at least one way to cause that. Tree, there's a little bit of ground, part of that sentence is in the ground. Just one way or multiple ways?
Two ways to get it. That means two different powerful subtrees. Confusing?
I have three possible options. Map it. AndYou couldn't have done this. So, uh, Q1. A probabilistic complex pre-grammar has... We have multiple production rules that correspond to the same. Symbol. the total of one probability, a sum probability of one. Does that make sense? Okay, so say that I gave you thisHow do we actually calculate probability of a tree. This is how a tree played in. How many want to?
Well, estimate friendly. And this is going to be probably the simplest The way of contemplating any probability Now take a look at this pre-broken down to every individual rule of law. Cold Earth, right? Every time a rule is being used It's a part of the truth. Does that make sense? Is that true? Every sub-tree. Now, we'll have its own probability. I use this One, I use that. 2, 2, 0, 2, okay? 1. This one goes here and this one goes here.
That's your probability. That works? Of course. If I asked you that kind of question on the exam, I would expect you to write a little more than just numbers. Does that make sense? What else would be right? Well, let's see. Let's say you gave me this answer to a question, what's the probability of a--Right, you gave me the exact answer, final answer. Here. I understand what you're doing, but... You're given two Point three.
Okay. Which one is it? So we're gonna break out the... This one would be probability of-You catch my drift. Everything has to be x point, otherwise-That works. Great, so that's basically what How about ballistic? Grammar, context-to-meat grammar, or with, C-A-Y-S First, the B&E, the ground level has probability values to it. Are you getting those probabilities from the corn goose studies? has been aided specifically.
And instead of just building this probability CKY matrix with Rules, right? They're also adding probabilities. And then when you're done with your matrix, you're able to resolve ambiguities just by looking at different... Probabilities of making the highest probability structure. By doing It's very hard to do that in a sort of two-degree way like that. But I'm pretty sure that you realize that Let's say for this.
Cell right here, I have multiple values. I'm showing you only one way. but there's really multiple values multiple ways to break down. Okay, that works. Should I pull it up? Ballistics again, we put the ballistics on the ground. That burn rule has a probability. Probability of a tree, break it down into individual rules that you use. Look at the probabilities, multiply them. Done. Any questions? How's that?
How's all this probability business going? Working out for you. How do you like that? Overwhelmingly, not so much. All right, so let's close it. For today. And this will not be on the exam.
We'll talk about two topics. Sentimental analysis. Analysis and then we'll talk about You've already got a page on sectoralPresentations and weddings.
Have we done anything that could possibly pass-What was that? Or maybe, can you explain? The probability of the center. How about context classification? Whatever we did last time,Filtering. your classes, your tags, your labels, or something else while they're negative. Sentiment analysis, but we can do a bit more. Just a quick quick recap You could use a naive Bayes classifierWe'll stay up. labeling our sentences for That's a negative or positive.
So here's the percentage. Again, you would have a training set where you have a set danceIt says it's a label. Watch out those. So I have the test set on. Set aside for that same idea. So far so good. Of course, your labels could be something completely different. -You know how to build that one. A model is based on a collection of probabilities. And then every-conditional even in class with the problemThat'll be a little circle of water.
You build those and you have your wall. Is it clear? Does everyone want a side? That's smoothing. Why are we using a smoother? Two point zero, bro. What is this? The size of the dictionary, of your dictionary, of your vocabulary. Okay, good. All right, so, I've been here, an idea, we can apply this name, approach, technically speaking. But, what could we do, what more could we do to improve our sentiment analysis rather than just counting all the words?
I do understand the problem. Human review, Yelp, whatever it is, right? If you want to go beyond justBack and forwards. Approach woods.
Empirically speaking, The fact that an objective appears in the index and is immoralHow many times do you have to do something like that? Binary could be Just enough. Okay, so binary tells could suffice for the The process, by the way, if you're interested. of reducing the counts to binary combinations Now. Here's challenge number one. We're counting words, right? Yes.
기본적인 NLP 처리는 다음과 같은 단계로 구성됨.
CFG는 **규칙(Rules)**과 **어휘(Lexicon)**로 구성됨.