I'm a bit tired, but want to finish this off tonight.
Do you notice how defensive S. is getting about his quizzes? Some of the criticism hit home.
Finally, we have some technology to animate the algorithms. That should really help.
"for the sake of this class, let's just care about it." That one made me laugh.
I'm excited about Expectation Maximization It's a cool algorithm, but generally pretty hard to understand. I wonder if he'll just give the gaussian version... yep.
That gaussian looks like it crosses the x axis. Be careful, the tails approach but do not cross the x axis.
Anyway, if you don't already know about gaussians, I would recommend just hitting the I believe button regarding the formula (but do pay attention to the derivative).
It should be noted that what he's showing and calling EM, is not the general EM algorithm, but a special version just for these "mixtures of gaussians." There are many other versions, depending on the underlying distribution you use.
I'm stopping here because I'm not paying very good attention. I'll finish in the morning.
Monday, October 31, 2011
Homework #3
Jumped to the homework because I'm running out of time. Mostly pretty straightforward, but measuring distances for knn was a royal pain on a video screen.
One tip on regression: when I went back to the lecture, I thought the denominator for \(w_1\) was \(M \sum y_i^2 - (\sum x_i)^2\) It is of course \(M \sum x_i^2 - (\sum x_i)^2\).
One tip on regression: when I went back to the lecture, I thought the denominator for \(w_1\) was \(M \sum y_i^2 - (\sum x_i)^2\) It is of course \(M \sum x_i^2 - (\sum x_i)^2\).
Machine Learning 10-37
Life caught up to me and I had several other deadlines pop up over this week. Let's see if I can jam through the material before the homework is due. This means I probably won't have time to work out the quizzes, sorry.
Laplace smoothing: Smoothing is a funny word for it, no? The idea is that when we have no data for a particular word, the distribution looks "sharp" because we have this sudden drop to 0. By hallucinating some data, we get some probability in that case, and the distribution looks smooth.
The question in 15 shows us why the denominator has \(+ k |x|\) in it. Recall that the \(P(M)\) must sum up to 1. \(|x|\) is the number of things we're summing, and the \(k\) is what we add to each of them, so this way, after smoothing the distribution still sums to 1.
Naive Bayes: Sort of odd to tell us NOW that what we're doing is Naive Bayes. What makes this approach naive? The key is the shape of the network. See how y is the parent of all the x's? That is great because then we know \(x_i \bot x_j | y\) and we can use Bayes rule easily. This is the natural characterization for spam, which is why it doesn't look naive, but take a more complex example. Let's say we want to determine the value for a hidden variable \(y_0\). Now this variable affects our observed x's as before, but there are other hidden variables \(y_{1...n}\) that also affect our x's. Now, when we try to compute \(P(x_{1...m}|y)\) those x's are no longer conditionally independent! (draw the picture, I promise) Naive Bayes is simply the assumption that there is only 1 hidden variable so we can use the conditional independence.
Cross validation: interesting conversation about experimental technique. I wish someone sat me down and told me that when I started graduate school. You may wonder what the deal is with 10-fold cross validation is. The problem is that if you get unlucky, your cv set might be misleading, so by trying multiple cv sets, we might get better value for our parameters.
Loss: Why squared? There are a few reasons, but one practical one is that we want loss to always be positive, because it should measure a distance between a point and a function. Otherwise 3-5 would be different from 5-3, even though they're the same distance apart. Why not absolute value? Because you can't differentiate it, but square is easy to differentiate.
Wow, we're going awfully fast here, essentially just mentioning other techniques like logistic regression, or regularization. There's no way you could implement logistic from that discussion. When he talks about sparsity in L1 vs. L2, the basic idea is that L1 works better when there are fewer data samples.ICML 2004.
No time to go in to it now, but the point of the question at the end of perceptions is about a very powerful technique called Support Vector Machines. They try (among other things) to find the best separating line as opposed to just some separating line in perceptrons.
wow, that's confusing: non-parametric techniques have a growing number of parameters? What he means is we save examples from the data, and those act like parameters in our model. I prefer not to call the saved data "parameters".
Not looking forward to the homework. I only have an hour and a half left.
Laplace smoothing: Smoothing is a funny word for it, no? The idea is that when we have no data for a particular word, the distribution looks "sharp" because we have this sudden drop to 0. By hallucinating some data, we get some probability in that case, and the distribution looks smooth.
The question in 15 shows us why the denominator has \(+ k |x|\) in it. Recall that the \(P(M)\) must sum up to 1. \(|x|\) is the number of things we're summing, and the \(k\) is what we add to each of them, so this way, after smoothing the distribution still sums to 1.
Naive Bayes: Sort of odd to tell us NOW that what we're doing is Naive Bayes. What makes this approach naive? The key is the shape of the network. See how y is the parent of all the x's? That is great because then we know \(x_i \bot x_j | y\) and we can use Bayes rule easily. This is the natural characterization for spam, which is why it doesn't look naive, but take a more complex example. Let's say we want to determine the value for a hidden variable \(y_0\). Now this variable affects our observed x's as before, but there are other hidden variables \(y_{1...n}\) that also affect our x's. Now, when we try to compute \(P(x_{1...m}|y)\) those x's are no longer conditionally independent! (draw the picture, I promise) Naive Bayes is simply the assumption that there is only 1 hidden variable so we can use the conditional independence.
Cross validation: interesting conversation about experimental technique. I wish someone sat me down and told me that when I started graduate school. You may wonder what the deal is with 10-fold cross validation is. The problem is that if you get unlucky, your cv set might be misleading, so by trying multiple cv sets, we might get better value for our parameters.
Loss: Why squared? There are a few reasons, but one practical one is that we want loss to always be positive, because it should measure a distance between a point and a function. Otherwise 3-5 would be different from 5-3, even though they're the same distance apart. Why not absolute value? Because you can't differentiate it, but square is easy to differentiate.
Wow, we're going awfully fast here, essentially just mentioning other techniques like logistic regression, or regularization. There's no way you could implement logistic from that discussion. When he talks about sparsity in L1 vs. L2, the basic idea is that L1 works better when there are fewer data samples.ICML 2004.
No time to go in to it now, but the point of the question at the end of perceptions is about a very powerful technique called Support Vector Machines. They try (among other things) to find the best separating line as opposed to just some separating line in perceptrons.
wow, that's confusing: non-parametric techniques have a growing number of parameters? What he means is we save examples from the data, and those act like parameters in our model. I prefer not to call the saved data "parameters".
Not looking forward to the homework. I only have an hour and a half left.
Wednesday, October 26, 2011
Machine Learning 1- 9
ML is a reasonable place to go from probability, but I'm still a bit weirded out by having it so soon.
Someone else complained to me that Sebastian bobs his head too much when he talks. I hadn't noticed it, but now that he mentioned it, I can't not. Now I have passed on this little gift to you.
What is: yes it is building models from data, but not just diagnostic models. We can also learn models that tell us consequences of actions that we use in search.
Let me guess, this question will be "all of the above." Yep.
Stanley: This actually a good example of something that bothered me about robots in the mid-90s to early 2000s: A lot of times what it seemed like we were doing was coming up with algorithms whose main objective was to overcome crappy sensors. Look at the image from Stanley's camera- I can barely tell where the road is, so of course the robot is going to have a hard time. The solution of overlaying with the laser data is great, until the cameras improve and we can find the road based just on that. That is why I've always preferred working in simulation.
Taxonomy: That is a really good list, and a good point at that end, that this list encompasses a great deal and it would take years to fully understand all of what's written on that page.
Supervised learning: Interesting, he gave us a warning this time that we haven't seen the answer to the question, but he wants to check our intuition. I wonder if he received a lot of negative feedback about that.
SPAM: Something that should have been made clear from the outset. you pick your dictionary first, and process all messages with that same dictionary. This leaves you with very long, mostly 0 input vectors. Notice the caveat at the bottom where he says "sport" and "sports". That's very common. It's called stemming: reducing all variations of a single word to a single word. The idea being that since sport and sports and sporting and sporty all have similar meanings, it is useful to count them the same in the input vector.
Maximum Likelihood: I know what maximum likelihood is, and I have no idea what he's talking about, entirely because he keeps changing his notation and his meanings of symbols. Let's see if we can figure it out:
\(P(S) = \pi\) means for \(\forall_i P(y_i = S) = \pi\)
The next bit means:
\(\forall_i P(y_i=S) = \pi \wedge P(y_i=H) = 1- \pi\)
I have never seen his notation to say this before.
The next line is a funny way to restate the previous one. How can we use the value or \(y_i\) to compute the \(P(y_i)\)? If we know the value of \(y_i\), then the distribution is 0s and 1s for a particular i. What he's trying to do is use \(y_i\) as a switch, so he doesn't have to say =S or =H. That is,:
if \(y_i=S, P(y_i=S) = \pi\) and if \(y_i=H, P(y_i=H) = 1-\pi\). This notation is drifting to perversion.
Now, the next line can be derived from the previous line, but it also can be derived from basic probability. The probability of a set of independent trials is the product of the probability of the outcomes of the individual trials.
"we can also maximize the logarithm of this expression." True statement, not actually obvious how that works. It is true because log is always increasing, so the in the existing function f(), if \(f(a)>f(b)\) then \(\log f(a) > \log f(b)\). This is handy because dealing with logs is easier to take derivative.
I think I'll publish this post now to get it out.
Someone else complained to me that Sebastian bobs his head too much when he talks. I hadn't noticed it, but now that he mentioned it, I can't not. Now I have passed on this little gift to you.
What is: yes it is building models from data, but not just diagnostic models. We can also learn models that tell us consequences of actions that we use in search.
Let me guess, this question will be "all of the above." Yep.
Stanley: This actually a good example of something that bothered me about robots in the mid-90s to early 2000s: A lot of times what it seemed like we were doing was coming up with algorithms whose main objective was to overcome crappy sensors. Look at the image from Stanley's camera- I can barely tell where the road is, so of course the robot is going to have a hard time. The solution of overlaying with the laser data is great, until the cameras improve and we can find the road based just on that. That is why I've always preferred working in simulation.
Taxonomy: That is a really good list, and a good point at that end, that this list encompasses a great deal and it would take years to fully understand all of what's written on that page.
Supervised learning: Interesting, he gave us a warning this time that we haven't seen the answer to the question, but he wants to check our intuition. I wonder if he received a lot of negative feedback about that.
SPAM: Something that should have been made clear from the outset. you pick your dictionary first, and process all messages with that same dictionary. This leaves you with very long, mostly 0 input vectors. Notice the caveat at the bottom where he says "sport" and "sports". That's very common. It's called stemming: reducing all variations of a single word to a single word. The idea being that since sport and sports and sporting and sporty all have similar meanings, it is useful to count them the same in the input vector.
Maximum Likelihood: I know what maximum likelihood is, and I have no idea what he's talking about, entirely because he keeps changing his notation and his meanings of symbols. Let's see if we can figure it out:
\(P(S) = \pi\) means for \(\forall_i P(y_i = S) = \pi\)
The next bit means:
\(\forall_i P(y_i=S) = \pi \wedge P(y_i=H) = 1- \pi\)
I have never seen his notation to say this before.
The next line is a funny way to restate the previous one. How can we use the value or \(y_i\) to compute the \(P(y_i)\)? If we know the value of \(y_i\), then the distribution is 0s and 1s for a particular i. What he's trying to do is use \(y_i\) as a switch, so he doesn't have to say =S or =H. That is,:
if \(y_i=S, P(y_i=S) = \pi\) and if \(y_i=H, P(y_i=H) = 1-\pi\). This notation is drifting to perversion.
Now, the next line can be derived from the previous line, but it also can be derived from basic probability. The probability of a set of independent trials is the product of the probability of the outcomes of the individual trials.
"we can also maximize the logarithm of this expression." True statement, not actually obvious how that works. It is true because log is always increasing, so the in the existing function f(), if \(f(a)>f(b)\) then \(\log f(a) > \log f(b)\). This is handy because dealing with logs is easier to take derivative.
I think I'll publish this post now to get it out.
Wednesday, October 19, 2011
Homework #2
- Much easier than the in class quizzes were.
- Much clearer questions than last homework, most likely because they are numeric.
- Weird things happen when the priors are 0.5.
- Big problem with this model of evaluation: no partial credit. It's easy to have a small error in knowledge but get the problem wrong. Usually this is made up for in automatically graded exams by asking lots of questions, so if you know 80% of the material you get 80% of the questions right. But with few questions, you need to look at them more closely to evaluate the level of knowledge.
Probabilistic Inference
Peter, that network is only familiar if you've read your or Judea Pearl's book. The presentation doesn't really explain what's going on. What do you mean by John or Mary "calls"? For the record, the idea is that these are neighbors who call you at work when your home alarm goes off. This alarm could be caused either by a burglary or by an earthquake.
I don't understand this first question. You just told us which were which, and you've even labeled them in the picture! Obviously, you've just changed your definition of what these things mean and haven't told us.
Oh great, he's using different notation from Sebastian. It would nice to be consistent.
Wait! that's an outright error!
He says \(P(+b,+j,+m) = \sum_e \sum_a P(+b,+j,+m)\) What he means is
\(P(+b,+j,+m) = \sum_e \sum_a P(+b,+j,+m,E,A)\)
After the last module being so much better, I'm really disappointed that this module is just as sloppy as the earlier ones.
ha ha! moving around slips of paper? Couldn't we use technology there?
What do you mean by "put the nodes together in a different order?" There has been nothing so far that refers to the order of things in construction. Sebastian just assumed it was causal. The idea of iterative construction of the network is rather non-intuitive. We naturally want to build the network causally, so what we're doing here is showing that putting the network in a way that we didn't want to in the first place, results in a bad network structure. And notice that through all that we didn't speed out our example in the slightest because it was already the best structure.
Quiz 9 is broken. 1 - 0.134 = 0.866 not 0.886.
So sampling will give us an estimate of a joint, but what does that have to do with a Bayes net? It's presented as if sampling is a way to perform inference on a Bayes net fast, but what he showed was using sampling instead of a Bayes net to answer the same question.
"Sampling has an advantage over inference in that we know a procedure for coming up with at least an approximate value for the joint probability distribution, as opposed to exact inference where the computation may be very complex." What? Isn't a complex computation still a known procedure? He means that sampling get get us an approximate answer in a reasonable amount of time, whereas inference may not return in our lifetime.
In rejection sampling, why don't we just not generate the samples we don't want, rather than generate them and reject them? That would actually work in the P(W|C) example he has there because C has no parents. If C had parents, then its value would depend on them, so we can't just generate samples with -w. See liklihood weighting coming up.
That Gibbs sampling discussion was really cursory. He describes the process correctly, but doesn't tell us how to use it to answer these conditional questions we're talking about. The key is if we want to know P(C|+r,+s), S and R are the "evidence" variables, so we don't vary them, and vary only C and W over time. But wait, don't we have the same likelihood weighting problem that sampling C only reveals the prior? No, that's what he left out. We compute a new value for C based on its Markov blanket, in this case P(C|+r,+s). But wait, that's what we're trying to compute! yep, Gibbs sampling is no help here. Not really much of an example is it?
I'm always a little bothered with the Monty Hall problem. Not because I don't understand it, but because it just isn't related to anything else in the section. We always present it because it's neat, not because it gives us any insight into AI. I question our motives. At least Peter tells us this up front.
As I said before, I'm a bit disappointed with this unit- it was too sloppy, and some important things were glossed over.
I don't understand this first question. You just told us which were which, and you've even labeled them in the picture! Obviously, you've just changed your definition of what these things mean and haven't told us.
Oh great, he's using different notation from Sebastian. It would nice to be consistent.
Wait! that's an outright error!
He says \(P(+b,+j,+m) = \sum_e \sum_a P(+b,+j,+m)\) What he means is
\(P(+b,+j,+m) = \sum_e \sum_a P(+b,+j,+m,E,A)\)
After the last module being so much better, I'm really disappointed that this module is just as sloppy as the earlier ones.
ha ha! moving around slips of paper? Couldn't we use technology there?
What do you mean by "put the nodes together in a different order?" There has been nothing so far that refers to the order of things in construction. Sebastian just assumed it was causal. The idea of iterative construction of the network is rather non-intuitive. We naturally want to build the network causally, so what we're doing here is showing that putting the network in a way that we didn't want to in the first place, results in a bad network structure. And notice that through all that we didn't speed out our example in the slightest because it was already the best structure.
Quiz 9 is broken. 1 - 0.134 = 0.866 not 0.886.
So sampling will give us an estimate of a joint, but what does that have to do with a Bayes net? It's presented as if sampling is a way to perform inference on a Bayes net fast, but what he showed was using sampling instead of a Bayes net to answer the same question.
"Sampling has an advantage over inference in that we know a procedure for coming up with at least an approximate value for the joint probability distribution, as opposed to exact inference where the computation may be very complex." What? Isn't a complex computation still a known procedure? He means that sampling get get us an approximate answer in a reasonable amount of time, whereas inference may not return in our lifetime.
In rejection sampling, why don't we just not generate the samples we don't want, rather than generate them and reject them? That would actually work in the P(W|C) example he has there because C has no parents. If C had parents, then its value would depend on them, so we can't just generate samples with -w. See liklihood weighting coming up.
That Gibbs sampling discussion was really cursory. He describes the process correctly, but doesn't tell us how to use it to answer these conditional questions we're talking about. The key is if we want to know P(C|+r,+s), S and R are the "evidence" variables, so we don't vary them, and vary only C and W over time. But wait, don't we have the same likelihood weighting problem that sampling C only reveals the prior? No, that's what he left out. We compute a new value for C based on its Markov blanket, in this case P(C|+r,+s). But wait, that's what we're trying to compute! yep, Gibbs sampling is no help here. Not really much of an example is it?
I'm always a little bothered with the Monty Hall problem. Not because I don't understand it, but because it just isn't related to anything else in the section. We always present it because it's neat, not because it gives us any insight into AI. I question our motives. At least Peter tells us this up front.
As I said before, I'm a bit disappointed with this unit- it was too sloppy, and some important things were glossed over.
Tuesday, October 18, 2011
how AI parts are related (or: avoiding Bayes net whiplash)
I mentioned in today's post that it's hard to see how we get from search to Bayes nets, and the student can feel a little lost. This post tries to explain AI as I see it.
Fundamentally, I see top-level AI as all Search. We have a world state, actions that can be taken, a possible goal, and possible heuristics. So where do diagnostic-style things, like Bayes nets fit in? Bayes nets are all about figuring out what state we're in. In the 'travel Romania' example, we know what out start state is, so we can begin searching immediately. But what if we didn't? We would need to figure out where we were before we could start to search.
Or to turn this upside-down, look at the car starting network. Sure, the network tells us what is wrong (or at least what is most likely wrong) but it doesn't tell us what to do about it. That's where search comes in. Now that we know it's the alternator, we can start to search the actions we can take to formulate a plan of action. Often in applications of Bayes nets, the only part of the system is the network itself, how is that related to search? State space search is still being done, it's just by the humans involved, not the computer. When we use a medical diagnosis system, it spits out a diagnosis, and then the doctor and patient think about various options for care (sort of an AI cyborg: intelligent decisions made part by humans, part by machines). We could have let the treatment plan also be computer generated, and that would likely require good old state-space search.
So diagnosis is a tool so we know where we are in our state-space search.
(Warning: not all AI people agree with me on this, but they're wrong.)
Fundamentally, I see top-level AI as all Search. We have a world state, actions that can be taken, a possible goal, and possible heuristics. So where do diagnostic-style things, like Bayes nets fit in? Bayes nets are all about figuring out what state we're in. In the 'travel Romania' example, we know what out start state is, so we can begin searching immediately. But what if we didn't? We would need to figure out where we were before we could start to search.
Or to turn this upside-down, look at the car starting network. Sure, the network tells us what is wrong (or at least what is most likely wrong) but it doesn't tell us what to do about it. That's where search comes in. Now that we know it's the alternator, we can start to search the actions we can take to formulate a plan of action. Often in applications of Bayes nets, the only part of the system is the network itself, how is that related to search? State space search is still being done, it's just by the humans involved, not the computer. When we use a medical diagnosis system, it spits out a diagnosis, and then the doctor and patient think about various options for care (sort of an AI cyborg: intelligent decisions made part by humans, part by machines). We could have let the treatment plan also be computer generated, and that would likely require good old state-space search.
So diagnosis is a tool so we know where we are in our state-space search.
(Warning: not all AI people agree with me on this, but they're wrong.)
Subscribe to:
Posts (Atom)