Thanks to everyone who came to the last lecture! We had a nice discussion of the projects that you guys are considering for next term. Lots of interesting ideas! And then we did a little review quiz covering the big ideas from throughout the term. You all did really well, so it seems like many of the topics we covered will stick with you for a little while...
As I said in class, I really hope that you all can fill out the TQFRs. I'm particularly interested in hearing comments about whether the class should be 9 or 12 units next year, and whether the blog posts were a valuable part of the course.
Thanks for all the hard work everyone!
Showing posts with label Lectures. Show all posts
Showing posts with label Lectures. Show all posts
Thursday, March 8, 2012
Tuesday, March 6, 2012
Final two lectures
Well, we finally got around to talking about data centers on Monday in class. After giving an overview of what goes into a data center, we spent most of the time talking about 2 issues: energy usage and programming with MapReduce. You'll get a lot of practice with MapReduce on the HW, so hopefully by the end of the week you'll be comfortable.
And now we only have one lecture left. I hope everyone can try to come. We'll spend the time on two things: 1) letting you guys tell each other about the projects you're planning for 145, and 2) doing a little review of the material in the course. I really hope people come for the review. It's your chance to convince me that I'm making the right decision in not having a final!
And now we only have one lecture left. I hope everyone can try to come. We'll spend the time on two things: 1) letting you guys tell each other about the projects you're planning for 145, and 2) doing a little review of the material in the course. I really hope people come for the review. It's your chance to convince me that I'm making the right decision in not having a final!
Monday, February 13, 2012
Lecture 9
Today we started to discuss computational advertising (ad auctions). I gave you a little overview, and then started with auction basics. We discussed first price, second price, ascending bid, and descending bid auctions. We started to look at a simple version of the "revenue equivalence theorem", but got a little hung up on the "revelation principle". I'll start from there on Wednesday and try to clarify things. Then we'll move on to understanding how ad auctions work in practice.
Thursday, February 9, 2012
Lecture 9
Yesterday in class we talked about "cascades/epidemics". You all have already made some interesting blog posts on the topic, so it wasn't really something new... But, hopefully you got a feel for the area from the lecture. We looked at a few "toy" models that I hope gave you a flavor for what cascades are and how network structure (specifically clustering) affects their growth. We really only touched the tip of the iceberg however, and so there are lots of related questions that would make great project ideas on this topic. I hope to see a bunch of ideas here when you turn in your project proposals.
Tuesday, February 7, 2012
Lecture 8
Yesterday in class we finished up out discussion of Pagerank. You guys were great, and came up with nearly all of the issues & fixes on your own! You kept me on my toes...
After finishing up the discussion of Pagerank, I gave you an overview of some of the projects in previous years of the course. Hopefully that got you thinking about your own ideas. The slides from that are up on the course webpage, and the webpage from 145 has all the final reports from past projects.
After finishing up the discussion of Pagerank, I gave you an overview of some of the projects in previous years of the course. Hopefully that got you thinking about your own ideas. The slides from that are up on the course webpage, and the webpage from 145 has all the final reports from past projects.
Wednesday, February 1, 2012
Introduction to Game Theory
Today, (most of) you were introduced to game theory, which is a theory that tries to explain the behavior of rational agents when they interact with one another. We saw the basic definition of a simple, finite game, and several examples of 2-player games in strategic/normal form. We saw that rational agents might be modeled as playing their best-response to other players' actions, and we defined the corresponding equilibrium concept - Nash equilibrium. We also defined dominant and dominated strategies, and saw that in certain situations, we could obtain the Nash equilibrium by iterated removal of dominated strategies. A recurring theme that we observed in the examples is that (selfish) rationality can hurt (the society)! We'll attempt to quantify and formalize this in later lectures.
We then looked at mixed strategies, where agents' strategies are now probability distributions over their action sets. For finite games, while pure-strategy Nash equilibrium might not always exist, mixed Nash equilibrium always exists. (Note that Nash's existence theorem is more general than this.)
Finally, we looked at extensive form games, which could capture additional aspects like timing/sequence as well as probabilistic payoffs. We saw how we could convert any extensive form game into an equivalent normal form payoff-matrix and study the Nash equilibria. We barely touched on backward induction and subgame-perfection (as equilibrium refinement concepts).
In the end, game theory is still a theory - and we briefly discussed a few ways in which the rationality assumptions made in the ideal world might differ from reality. There is a whole sub-field of experimental economics that deals with validating these assumptions in different real-world settings.
This lecture was just meant to be a primer. Later in the course, we'll explore more advanced concepts, as well as different kinds of games such as games with continuous players (routing games) and games with continuous action sets (ad auctions).
The concepts I tried to introduce are important, so if you have any questions or doubts, please feel free to post them as comments to this post (or email me personally) and I will clarify them. I encourage you to do this soon - this is foundation material for upcoming homeworks (HW5, HW6 and perhaps HW7 as well)!
Lecture slides will be up on the course website (here) in a couple of days.
We then looked at mixed strategies, where agents' strategies are now probability distributions over their action sets. For finite games, while pure-strategy Nash equilibrium might not always exist, mixed Nash equilibrium always exists. (Note that Nash's existence theorem is more general than this.)
Finally, we looked at extensive form games, which could capture additional aspects like timing/sequence as well as probabilistic payoffs. We saw how we could convert any extensive form game into an equivalent normal form payoff-matrix and study the Nash equilibria. We barely touched on backward induction and subgame-perfection (as equilibrium refinement concepts).
In the end, game theory is still a theory - and we briefly discussed a few ways in which the rationality assumptions made in the ideal world might differ from reality. There is a whole sub-field of experimental economics that deals with validating these assumptions in different real-world settings.
This lecture was just meant to be a primer. Later in the course, we'll explore more advanced concepts, as well as different kinds of games such as games with continuous players (routing games) and games with continuous action sets (ad auctions).
The concepts I tried to introduce are important, so if you have any questions or doubts, please feel free to post them as comments to this post (or email me personally) and I will clarify them. I encourage you to do this soon - this is foundation material for upcoming homeworks (HW5, HW6 and perhaps HW7 as well)!
Lecture slides will be up on the course website (here) in a couple of days.
Monday, January 30, 2012
Lecture 7
(I'll be busy after class, so I'm posting this now...)
Today we made our first venture into "exploiting" network structure instead of just trying to understand it. Our first example of a case where using network structure makes a huge difference is "search" -- the big idea of google back in 1998 was to use network structure to identify important pages, and feed this information into their search engine. In particular, they defined a notion called "pagerank", which we explored over the two classes. Be sure to take a look at the original papers by Brin & Page on Google...it's quite interesting to read now in the context of what google has become.
Note -- understanding pagerank and the other aspects of search engines that we discuss will be very important for you in "Rankmaniac Reloaded" on HW 4!
Today we made our first venture into "exploiting" network structure instead of just trying to understand it. Our first example of a case where using network structure makes a huge difference is "search" -- the big idea of google back in 1998 was to use network structure to identify important pages, and feed this information into their search engine. In particular, they defined a notion called "pagerank", which we explored over the two classes. Be sure to take a look at the original papers by Brin & Page on Google...it's quite interesting to read now in the context of what google has become.
Note -- understanding pagerank and the other aspects of search engines that we discuss will be very important for you in "Rankmaniac Reloaded" on HW 4!
Thursday, January 26, 2012
Lecture 6
Today we focused on the remaining two universal properties of networks -- small diameter and high clustering. Remember that, in isolation, neither small diameter or high clustering coefficient is particularly "surprising" or difficult to explain. It is only the combination that is "surprising"... and this is what is termed "small world".
We saw that one possible explanation for small world properties is a combination of local correlation with long-range random links. However, this combination only explains the existence of short paths, it doesn't explain why we can find them so easily.
To explain this second observation (and to me the more interesting observation) we saw that the long range links have to be proportional to the distance in a very precise manner. So, it is in some sense much more rare that we can find short paths with myopic algorithms than it is for the short paths to exist in the first place.
Remember though that the models we have discussed for small world graphs DO NOT have heavy-tailed degree distributions! So, we really haven't given a "natural" mechanism that explains all four of our "universal" properties, we've just given mechanisms for each individually. Can you think of how to combine our heavy-tailed degree distribution ideas with the small world ideas?
We saw that one possible explanation for small world properties is a combination of local correlation with long-range random links. However, this combination only explains the existence of short paths, it doesn't explain why we can find them so easily.
To explain this second observation (and to me the more interesting observation) we saw that the long range links have to be proportional to the distance in a very precise manner. So, it is in some sense much more rare that we can find short paths with myopic algorithms than it is for the short paths to exist in the first place.
Remember though that the models we have discussed for small world graphs DO NOT have heavy-tailed degree distributions! So, we really haven't given a "natural" mechanism that explains all four of our "universal" properties, we've just given mechanisms for each individually. Can you think of how to combine our heavy-tailed degree distribution ideas with the small world ideas?
Monday, January 23, 2012
Lecture 5
Today we talked a LOT about heavy-tails...and we managed to finish it off, despite the fire alarm!
The details of what we covered could fill a whole probability course, so don't worry if you don't feel that you could prove all the results -- focus on understanding the intuition behind what I told you. (And if you want to learn more, ask me and I'll point you in the right direction.)
In my mind the key things to take away about heavy-tails are the following:
1) Know some examples of heavy-tailed distributions (Pareto, Weibull, and LogNormal)
2) Know some generic processes that create heavy-tails -- additive process (generalized CLT), extremal processes, and multiplicative processes.
3) Know how to apply these ideas to networks in order to get a heavy-tailed degree distribution. (And be sure to look at the details of the proof for Preferential attachment, since that'll be useful on the HW.)
Like I said in class, I could go on-and-on about heavy-tails... So, I probably tried to pack too much into one lecture. You'll likely need to go back and look at the notes in order to really process everything we talked about.
The details of what we covered could fill a whole probability course, so don't worry if you don't feel that you could prove all the results -- focus on understanding the intuition behind what I told you. (And if you want to learn more, ask me and I'll point you in the right direction.)
In my mind the key things to take away about heavy-tails are the following:
1) Know some examples of heavy-tailed distributions (Pareto, Weibull, and LogNormal)
2) Know some generic processes that create heavy-tails -- additive process (generalized CLT), extremal processes, and multiplicative processes.
3) Know how to apply these ideas to networks in order to get a heavy-tailed degree distribution. (And be sure to look at the details of the proof for Preferential attachment, since that'll be useful on the HW.)
Like I said in class, I could go on-and-on about heavy-tails... So, I probably tried to pack too much into one lecture. You'll likely need to go back and look at the notes in order to really process everything we talked about.
Wednesday, January 18, 2012
Lecture 4
Today we finished up talking about G(n,p) and then started our discussion of heavy-tails.
With respect to G(n,p), the main point today was to give you an example of how to use concentration inequalities (e.g., Markov's and Chebychev's) to prove strong threshold results, i.e., threshold results about the probability of an event occurring rather than just about the expectation of an event. Hopefully, you followed along because you'll have to do it for yourself on HW2.
With respect to heavy-tails, we just got started. We're going to talk a lot about heavy-tails next time. This time, we really only talked about what they are, mainly through giving examples. Next time, we'll talk about where they come from. I'll try to give you a glimpse at what is really a whole advanced course in applied probability....
With respect to G(n,p), the main point today was to give you an example of how to use concentration inequalities (e.g., Markov's and Chebychev's) to prove strong threshold results, i.e., threshold results about the probability of an event occurring rather than just about the expectation of an event. Hopefully, you followed along because you'll have to do it for yourself on HW2.
With respect to heavy-tails, we just got started. We're going to talk a lot about heavy-tails next time. This time, we really only talked about what they are, mainly through giving examples. Next time, we'll talk about where they come from. I'll try to give you a glimpse at what is really a whole advanced course in applied probability....
Wednesday, January 11, 2012
Lecture 3
Well it seems like we found a new home for lectures. The room was big enough, and we weren't kicked out halfway through!
Today we moved from studying the web graph to looking at a bunch of examples of other complex networks besides the web. My goal was to illustrate that the properties we saw in the web graph aren't special to the web -- they happen in most of these other networks too. So, they are in some sense "universal".
This motivates two natural directions, which we'll spend the next few weeks studying:
1) Trying to understand what causes these properties to emerge
2) Figuring out how to exploit these properties.
We'll to 1 and then 2, spending about 3-4 lectures on each.
We started on 1 today by exploring Erdos-Renyi random graphs. We saw that this simple model won't give us all the properties we want, but that it seems promising in terms of connectivity. We'll finish up that discussion next time, and then move on to trying to understand what causes some of the other "universal" properties to emerge.
Don't forget to come to office hours tonight & tomorrow night...and of course, don't forget that HW1 is due Friday.
Today we moved from studying the web graph to looking at a bunch of examples of other complex networks besides the web. My goal was to illustrate that the properties we saw in the web graph aren't special to the web -- they happen in most of these other networks too. So, they are in some sense "universal".
This motivates two natural directions, which we'll spend the next few weeks studying:
1) Trying to understand what causes these properties to emerge
2) Figuring out how to exploit these properties.
We'll to 1 and then 2, spending about 3-4 lectures on each.
We started on 1 today by exploring Erdos-Renyi random graphs. We saw that this simple model won't give us all the properties we want, but that it seems promising in terms of connectivity. We'll finish up that discussion next time, and then move on to trying to understand what causes some of the other "universal" properties to emerge.
Don't forget to come to office hours tonight & tomorrow night...and of course, don't forget that HW1 is due Friday.
Monday, January 9, 2012
Lecture 2
Since I'll be busy after the lecture I'm posting this beforehand...
The notes and slides for lecture 2 are now up on the course website. The key take-aways from today's lecture are the following 4 interesting properties:
1) Connectivity: The web has one "giant" connected component and all other connected components are tiny.
2) Diameter: The distance between nodes is quite small (~6 avg. distance between noes in the SCC) and, for at least the beginning decade of the web, grow logarithmically with the size of the graph.
3) Degrees: The degree distribution is not Normal... Instead it's heavy-tailed. This means we should expect a few nodes with really "huge" degree and "lots" of nodes with small degree.
4) Clustering: The web exhibits strong "homophilly", i.e., if A is connected to B and C it is significantly more likely than random for B to be connected to C.
Over the next few lectures we'll see that these properties are "universal", and we'll try to explain why they are so common.
(By the way, I'm excited to see that someone already made their first blog post!)
The notes and slides for lecture 2 are now up on the course website. The key take-aways from today's lecture are the following 4 interesting properties:
1) Connectivity: The web has one "giant" connected component and all other connected components are tiny.
2) Diameter: The distance between nodes is quite small (~6 avg. distance between noes in the SCC) and, for at least the beginning decade of the web, grow logarithmically with the size of the graph.
3) Degrees: The degree distribution is not Normal... Instead it's heavy-tailed. This means we should expect a few nodes with really "huge" degree and "lots" of nodes with small degree.
4) Clustering: The web exhibits strong "homophilly", i.e., if A is connected to B and C it is significantly more likely than random for B to be connected to C.
Over the next few lectures we'll see that these properties are "universal", and we'll try to explain why they are so common.
(By the way, I'm excited to see that someone already made their first blog post!)
Friday, January 6, 2012
Probability Refresher
Don't forget to attend JKs probability refresher today at 1-2:30 in Ann 213 if you have any worries of being prepared for the course.
We will post his notes to the website afterwards, but if you have any questions about what he covers, post them as comments here.
We will post his notes to the website afterwards, but if you have any questions about what he covers, post them as comments here.
Thursday, January 5, 2012
Lecture 1
Glad to see so many faces at the first lecture... I'm working on getting a new room still, so be sure to check back before Monday to find out where the next lecture will be.
If you still have any questions about what the course is about or about the procedural details of the course, please post them as comments here or ask me at the beginning of the next class. Also, I really recommend reading through the V. Bush and T. Berners-Lee papers that I talked about in class there are links to them at the course website.
Also, be sure to remember that JK will be giving a probability refresher on Friday at 1-2pm in Annenberg 213. If you haven't had any probability since Math 2, I highly recommend attending, as being comfortable with it will be key to the first half of the course.
If you still have any questions about what the course is about or about the procedural details of the course, please post them as comments here or ask me at the beginning of the next class. Also, I really recommend reading through the V. Bush and T. Berners-Lee papers that I talked about in class there are links to them at the course website.
Also, be sure to remember that JK will be giving a probability refresher on Friday at 1-2pm in Annenberg 213. If you haven't had any probability since Math 2, I highly recommend attending, as being comfortable with it will be key to the first half of the course.
Subscribe to:
Posts (Atom)