Good afternoon, CS109.
And welcome to the first day of fall quarter.
Hey.
[APPLAUSE]
I have not gotten to--
I was studying abroad in spring, which
means I haven't gotten to start a class in person
since pre pandemic.
And boy, does it feel good.
I am so happy to see you guys.
Oh, welcome, welcome, welcome to CS109.
If you didn't expect me to say CS109,
this is your time to find that CS103 class or that CS131 class
that you might be looking for.
But if you're looking for CS109, this is the place.
Come on in.
Grab a seat.
I'm Chris.
And we're going to be learning about probability
for computer scientists.
OK.
Shall we jump in?
Gather round.
I have such a story to tell you guys today.
And it's a story that computer scientists know.
It's a story that mathematicians should know.
But certainly, it's probably also a story
that all people should to some extent.
But before I get into that, I think
I should introduce myself.
Hi.
I'm Chris.
I'm a professor here in the computer science department.
I'm also in the School of Education.
I'm in both places.
I teach, and I research, and I have a good time.
I have a research lab.
It's AI for Social Good.
We mostly do education and some medical work as well.
I love to teach.
I teach 109, I teach 106A.
I'll teach CS398.
I'll teach anything that I can-- that I'm equipped to teach.
Small detail, but I've been here for a while.
I actually originally was born in Kenya.
I was 12, I moved to Malaysia.
And then I came here when I was 18.
And I liked it so much that I just decided to stay.
And because I've been here for so long,
I was actually here as an undergraduate.
And after undergraduate, I stayed for my PhD.
After my PhD, they're like, you want to be a teacher?
I'm like, yeah, that sounds cool.
So here I am.
And when I was an undergraduate, I actually
had the honor of being in the world's very first CS109 class.
It was a brand new class when I was an undergraduate.
I got to take the very first one.
And look, I was so young.
Anyways.
And I've been teaching for quite a long time.
Wow, 2014.
It's been a great, great run.
So I love teaching.
And a lot of my research actually
involves teaching because I love it so much.
One of the things that I did during the pandemic is we
taught 20,000 students Intro CS around the world.
And we got the world's--
the class with the most teachers in the world.
We got trained 2,000 people up to teach.
And they taught 20,000 students.
And it was a good vibe.
It was just like a little bit of community service and then time
pandemic.
That also gives me a chance to tell you a little about some
of the research I do.
We taught these 20,000 people how to program.
But one of the things that I'm intellectually curious about
is how can we understand humans who are learning.
And so one of the things we try to do
is said, OK, if students are learning how to code,
can we look at their code and use
some AI to analyze it and give feedback?
And we had this nice little result for the first time
ever for something as complicated as open ended code,
we were able to give feedback that students
preferred TA feedback.
It showed up in the New York Times amongst other places.
I love lots of problems.
I'm also really interested in how
AI can help teachers teach better,
and give feedback to teachers, and how
they can improve their craft.
We tried all this stuff in code in place.
And we found ways that we could make teachers
even better at what they do.
And that just scratches the surface
of how many cool problems there are in the world.
I'm into things like measuring how well people can see.
I'm into things like, can we figure out fairness
in artificial intelligence?
The world is so full of things to be curious about.
And one of the joys of being at Stanford
is I get to think about all these wonderful diverse things.
Outside of academics, there's a whole bunch
of things I love to do.
I love music.
I love playing guitar.
Kenya and Malaysia have some of the best food in the world.
And I will argue with anybody that our cuisine is better.
I'm just joking.
I love food.
I love cooking.
And I just love science.
Last winter, I went into the forest.
And I found this wood covered with this ice that
was in the shape of hares.
And our world is such a beautiful, beautiful place.
This is a big deal in my life.
I do a lot of research.
I do a lot of teaching.
And then I've got this little baby.
And so this summer was like research half day,
teach half day, and then make airplanes out of cardboard,
which is like a total joy, I'll tell you all about her.
OK.
That's a little bit about me.
But I'm just one of the people who's
going to be teaching you CS109.
CS1 is an--
109 is an incredible course.
And one of the things that makes it so amazing,
we have such an awesome team of TAs
who are going to be helping us through this journey
of learning probability.
Are there any here today?
Hey, we got a corner of TAs.
Everybody, round of applause.
These guys are the heart and soul of the class.
[APPLAUSE]
Thank you, guys, for what you do.
OK.
I really wanted to get into content,
but I do want to give you the most important pieces of course
mechanics.
But the number one thing to take away from today
is we have a course web page.
It's cs109.stanford.edu.
All the course mechanics that I mentioned,
you can go find on that course website,
and you can go look at the nitty gritty details for things
that you're curious about.
Though, we should talk about some of the things.
One of the things we might be curious about,
am I in the right place?
There's a lot of questions about prerequisites.
And I just want to give you an idea of what we actually
are going to be basing CS109 on top of.
We really, really assume that you know CS106B coding.
We are going to talk about things
like recursion, hash tables, binary trees.
And also, we're just going to assume a certain maturity
in coding.
Some people have managed to take CS106B
alongside CS109, that's fine.
But it's just a really, really important prerequisite.
A less important prerequisite is CS103.
We just use some light bits of CS103.
And they mostly show up at the beginning of class.
In fact, one day, I was curious.
I-- there's all this card of data.
And I was wondering, how do people do in CS109 if they've
never had CS103 before?
And how do people do if they hadn't?
And I found this surprising result
that if you didn't have CS103, you
did slightly better in CS109.
Now--
[LAUGHTER]
--as we'll talk about causality later in this class--
certainly, not causal, it's probably
just people who are willing to skip CS103 might be coming
from a different population.
But long story short, we really don't rely too much
on the material from CS103.
We do rely heavily on material from Math 51 or CME 100.
You're going to want to know what a partial derivative is.
We are going to teach you multivariate integration.
If you haven't seen it before, you'll see it in CS109.
A lot of stuff.
If you get there and you're rusty on it,
we're going to help you.
But this is just what we're assuming coming in.
And certainly, just some notation
we hope you're a little bit familiar with.
If you just really, really want to take CS109
and you don't feel like you're completely
mastered all the prerequisites, just come talk to us.
We're happy to have that conversation.
So yeah, you're in the right place.
CS109 is a math course.
But we discovered a while ago that math can really
bloom when you can create things using math,
not just solve problem sets, but make real things.
And to that end, we are going to use the math that you learn
in this class to make stuff.
And Python is going to be the language that you
use to make things in CS109.
Some of you have probably seen Python before.
Some of you haven't.
If you haven't seen Python, that's absolutely fine.
We're going to have a review sessions to catch up
on what you need.
It's a beautiful language, certainly,
something you should know by the time you graduate.
Worth it.
Come to the review sessions.
As long as you've seen some programming,
Python is one of the kindest and gentlest programming languages
that you could learn.
OK.
This is a very small thing.
You know that there is a unit choice and access.
There really shouldn't be because there's not really
a choice.
It's a deterministic decision, mostly.
Start here.
Are you an undergraduate?
Yes.
Very simple, five units.
If you register for access for less than five units,
I get an email per student, which is a lot of emails.
Let's say you're not an undergraduate then.
Do you want to take CS109 for fewer units?
No?
Guess what, five units.
But if you did want to take CS109 for fewer units,
I'm here to let you know that you can
if you're a graduate student.
If you take it for three units or four units,
the workload doesn't change.
It's the same amount of work for fewer units.
That's just life in grad school.
Welcome to adulting.
Anyways, really quick note on units.
So it's a five unit class.
The way Stanford units works is about three hours per unit.
So you can imagine, we're going to be spending
about 15 hours per week on CS109,
and a large, large, large majority of that
will be you guys doing your own work.
So 10 hours for assignments, a few hours for lecture,
and a few hours for section.
Speaking of which, what are the components
of this wonderful class?
Well, as I mentioned, one of the biggest components
is assignments.
You guys will make things.
You'll derive things.
You'll practice your art form of understanding probability.
And that will be done in your assignments.
And that's a good chunk of CS109 and a good chunk of your grade.
We do have exams.
We have a midterm and a final exam.
You should show up.
They're both going to be a good time.
We put a lot of love to try and make it
an educational uplifting experience.
I'm not really here to judge people.
I want you guys to grow and improve
as-- and hit your potentials.
But anyways, the final exam, we were told by the university,
do it then.
And it's very, very, very, very, very, very, very, very, very
close impossible to change, only if you're
like a senior who's graduating this quarter are there-- does
the university make exceptions.
The midterm, we have a lot more leeway on.
If you can't make this time, you just let us close to the date,
and we'll figure out something for you.
So anyways, we have these exams.
If you're in a class that's at this exact same time,
your exam is probably at the exact same time.
And you definitely want to solve the problem now,
not at the end of the quarter.
OK.
And then one of my favorite things about CS109,
it's fun to come to lecture.
You guys should come to lecture.
We were going to have a good time.
We're going to do demos.
We're going to tell jokes.
We're going to laugh, hold hands, sing kumbaya now.
We're not going to do that last part,
but we are going to learn a lot of probability.
But one of the best parts of the class
is then you get to meet in small groups
with one of our excellent world expert TAs who will walk you
through the concepts, so you can practice it before you go off
on your own into problem sets.
It's a beautiful lecture, then section, then do your work.
I get this question a lot.
Is this class online?
It's recorded.
These wonderful cameras.
And we have an amazing, amazing, amazing SCPD team
that's doing professional recording of these classes.
They'll be released about 24 hours later.
So there's a few things to say about that.
I love that we're recording.
You get sick, you can watch it later.
You didn't catch something, you can watch it later.
Realistically, though, some people are going to be like,
oh, man, my club really needs me to do XYZ.
And I'll just catch up on lecture later.
And we've all fallen into that trap.
So I want to talk a little bit about that query
we did about people who had or hadn't done 103.
We can do the same thing based on how
people are watching lectures.
And we know that coming to lectures,
people do about a grade point higher.
Again, not causal.
But come to lecture, it's a good time
it'll help you stay on top.
Having said that, I do think of you guys as adults.
You're adults.
Of course, I think of you as adults.
And to that extent, you're in charge
of making sure you know this material.
Find your way.
It's just coming to lecture.
We know it's one of the best ways to do that.
And-- but I will leave it to your own devices
to how you're going to get to the end of this quarter.
OK.
You guys probably have questions.
In fact, somebody might have a question right now.
If you have a question in lecture,
you just raise your hand and we'll get amongst it.
There are other ways.
Oh, yeah.
The grading breakdown in the slide
was slightly different than the syllabus.
Which one is like--
Oh, definitely the one in syllabus.
What did I get wrong here?
40?
[INAUDIBLE]
Oh, yeah.
I was going to reveal that on Wednesday.
Oh, sorry.
No, no, no, no, no, no, that's great.
That's great.
OK.
Well, OK, the reveal is going to come today.
[LAUGHS] So I was thinking about this slide.
And I was like, well, I want you guys
to make your own decisions.
I don't want to penalize people.
I don't want to put in something to force
you to come to lecture.
But I do know that coming to lecture
is generally good for you guys learning the material better.
So I was like, how could I incentivize
this in a nice and healthy way?
So what I was going to do is I was
going to put a really chill code on the board.
And you can record if you came to class.
And if you come to most of the classes,
then I'll just slightly decrease how much your final weighs
into your grade.
And I'll just give you full points for that.
So just a small way to encourage participation.
If you don't do it, can you still get 100% in the class?
Absolutely.
If you never show up to lecture, but you show up
to all your sections, that is important.
And then you come to the final, and you just rock it,
you're like, yeah, I can do all this probability.
You can get 100% in CS109.
But we know that the more reasonable path to that,
coming to lecture, participating.
So we're going to incentivize that.
And I'll give you a little bit more details
about that on Wednesday.
But very, very, very good question.
OK.
You might have other good questions.
Where are you going to ask your good questions?
Well, you guys know Q&A forums by now.
We use ed.
Instead of sending us an email often,
it's better to post at ed.
A lot of people will read that and get back to you
as soon as possible.
One of the great places to go ask questions is in person.
We do working office hours in CS109.
So you don't even have to have a question.
You just go with your problem set and be like,
I'm going to work on my problem set.
And then when you have a question, you're already there.
What a time to be alive.
So you do this working office hours.
They're going to start on Thursday.
And we have a lot.
All of our TAs are doing four office hours.
We've got so many office hours for you guys
because we want you to get the help when you need it.
So working office hours, one of the great places to get help.
And you can also always email that email address.
And that goes to me and all the TAs.
And we can get you any help.
If you have anything private that comes up,
that's going to happen to some people,
you can email me and the head TA, Will, directly.
And I also have one on one office
hours as opposed to group office hours,
so you can come and ask me just questions there.
OK.
Questions on questions?
How meta.
Oh, this is so cool.
I first started writing lecture notes for all my classes,
like, OK, what did I talk about today?
And then over time, I became an entire reader.
So now I'm an entire reader for you.
I finally finished it last year.
But now there's a CS109 reader.
It goes over a lot of the concepts
we talk about in class, but just in a written form, if you like.
There's this thing called an ACE Companion Course.
It's fantastic.
If you want to take more units to cover this material
and get some more examples, you can take the ACE class.
There's application form.
And you can learn more about it by following the link.
It's both in the slides and on the home page of CS109.
You guys want to see our home page?
It's really not that beautiful.
But I designed it.
I'm not a designer.
And I feel really good about some of the small details.
It's not that important right now.
What is important, though, is that link is right over here.
So if you want to apply to ACE, there it is.
OK.
And then I didn't go over all the details,
but for all the details, the way you
get all this information is on the course website.
Under the Course, there's the Syllabus.
And you can read, oh, our wonderful TAs.
And you read all about the details
about the course structure.
And we go into all the nitty gritty.
OK.
How exciting.
Any other questions?
Shall we?
Let's do it.
I want to tell you guys a story.
And I would like to tell you the story of modern AI.
And boy, has it become interesting in the last year.
So modern AI has this really interesting story.
But if I had to give it a subtitle,
it would be, how we learn to combine probability
and programming together to do very interesting things.
But I think I should give some historical context.
People thought AI would be a very easy problem.
And AI, I'm going to speak about broadly,
just computers doing human level intelligent things.
We thought this would be simple.
In the 1950s, computers started to do some awesome things.
We got computers that could beat any human in checkers.
And then we got computers that could do automatic proofs.
Imagine the proofs you would do in CS103.
You had computers that could start to do automatic theorem
proving.
And we're like, yeah, we're awesome.
AI, going to be super simple.
And it led to ridiculousness.
For example, Herbert Simon, one of the leading AI researchers
in 1952, said this ridiculous thing on a grant
that he won that was worth the equivalent of like half
a billion dollars today.
He said, machines will be capable,
within 20 years, of doing any work a man can do,
which is ridiculous for two years--
or two reasons, like, 1952, all the work a man can do?
Jeez, get with the times.
And then the other thing is like, imagine, 1972.
We're getting machines able to do this?
No, they're basically like big calculators by 1972.
Completely wrong.
You just thought the world was pretty simple.
His grant was like, first, I will solve language.
And then once I have solved language,
then I will solve free thought.
This is ridiculousness.
Anyways, he didn't get past language.
He started with translation.
And he made this thing that could translate from English
to Russian.
And one of the funny examples was
you could put in something like, the spirit is willing,
but the flesh is weak.
And you could translate it to Russian.
I didn't understand Russian so I didn't include it here.
But then you can take that Russian
and put it back to English, and see if it did a good job.
It's like, the vodka is good, but the meat
is rotten, which is funny but not at all the input sentence.
And you know what had happened?
The world is just too complex.
What did he try and do?
He tried to write all the rules of English to Russian.
He's like, I'm just going to spend this money.
We're getting a lot of people will write all these rules.
And once you've written all the rules,
then we'll have a translation system.
But it turns out the world is so complex.
And we don't understand it, because we
have these beautiful probability machines called brains.
And these beautiful probability machines have so much power,
and they're so good about thinking about uncertainty
that we think uncertain problems are easy.
But they are not, as exemplified by Herbert Simon.
And then we called--
we got what we called the AI Winter.
And for decades, no one would fund anybody, not just
Herbert Simon.
Anybody who's had their AI, they'd be like, oh.
But obviously, the AI Winter is over.
And something's going on.
And you guys probably know a lot about it.
A lot of its history started here.
For example, this is a picture of Stanley,
a car made at Stanford, which was one of the very
first self-driving cars.
So 1997, we started to win at chess.
In 2005, we got cars that could drive themselves.
In 2011, we had computers that could play Jeopardy.
Something had started to change.
And obviously, we know that that was just the beginning.
You know when I was in your seats, crazy thing.
Someone told me there's this problem called Speech.
The problem is, you get an audio recording of someone's voice,
and then you have to write the transcription of what
they said.
That's the problem of speech.
When I was in your seats, someone told me,
this problem will not be solved in your academic lifetime.
I was like, whoa, what a hard problem.
But of course, it has been solved.
We're very, very, very good at that.
In fact, my phone right now can do transcription from my voice
into written text.
Something really big had changed between when
I was in your seats and now.
Board games.
Yeah, we're done with board games.
In fact, the people who got so good at board games were like,
let's do something real with this technology.
And they started protein folding.
If you don't know what protein folding is,
it's this very hard task of taking an amino acid sequence
and then figuring out the 3D structure.
And if you could do that, you could develop drugs faster,
you could understand our bodies faster.
It is a very interesting and wild world.
But it's such a hard problem to figure out
how amino acid would become a 3D structure that we thought
we won't be able to do it.
But as of a couple of years ago, not only are we good,
but we've come up with a 3D structure
for every single known amino acid
sequence in some popular database, which
I can't remember the name of.
But AI is not just those flashy things.
AI is also in our day to day lives, like when you say,
I want to go from San Francisco to Mexico City,
and you get this route, it's a little bit
of artificial intelligence that's
helping you figure out your path.
And translations got a whole bunch
better than when Herbert Simon was working on it.
If you're in Silicon Valley, our self-driving cars--
actually, I have no idea how they're doing.
They haven't hit me yet.
OK.
And it's always been an exciting time.
But then this year, everything seemed to change once again.
This is just like a timeline since May.
And all of a sudden, we've started
to get these huge results in artificial intelligence
in a world that people are starting
to call large language models.
But basically, they're these half billion dollar AI systems
that people have started to make public for other people to use.
I was playing with my eight--
now 20-month-old daughter a little while ago.
And we opened up one of these AI systems.
These AI systems can do different things.
The one we use would take text.
And when you wrote text, it would infer
the distribution of that text.
It would then go figure out, what
is the probability distribution of all the images
that relate to this text, conditioned
on what was written.
And then it can sample you a few different images
from that probability distribution.
And it's insanity.
But for my 20-month-old daughter,
it's just like, she writes three birdies happy.
And she gets this picture.
Or she writes, robot Messiah.
And she gets this picture out.
In fact, have you guys seen this?
Is there anyone who has not seen this live?
Do you guys want to see it?
I need a prompt, though.
Let's say, a rabbit and a giraffe in an airplane.
So this is one AI model called DALL-E. It's
going to take that sentence.
It's going to try and sample from the probability
distribution of images related to that sentence.
And this is something that came out about six months ago.
We can also-- oh, there you go.
And it constructed these images-- oh, that's so cute.
Look.
It's got like a little heart there.
Oh.
OK.
And these aren't pictures found on the internet.
It just constructed those pictures from scratch.
It's thinking about probability distributions over images.
What a time.
So much is happening so fast.
And every problem that gets solved
seems to open up a whole bunch of open new problems.
So hopefully, at this point, I've
convinced you that stuff's happening.
But you might be curious like, Chris, what's
really going on under the hood?
Well, I'm going to start telling you that story now.
But really, CS109 is a class where
we're going to understand this story more deeply.
Oh, a little bit of suspense.
This is so fun.
I haven't started a class in person for so long.
OK.
Let's focus on one problem.
This is the fun problem called chihuahua or muffin.
[LAUGHTER]
You may think it's easy, but originally,
when I was working on AI, this would have
seemed like an impossible task.
First of all, let's just take a moment
to appreciate how smart we are as humans,
and feel better than the machines for a moment.
OK.
Just yell it out loud.
Chihuahua.
You guys are good.
Muffin.
A little tricky because the blueberries
are arranged like eyes.
But you're right, it is, in fact, a muffin.
OK, how about now?
[INAUDIBLE]
[LAUGHTER]
That was very impressive.
OK.
Humans are getting smarter too.
Why is this problem so hard?
It's like, when you're seeing this,
it's hard to separate the fact that you
have billions of neurons, which are activating.
And they're lighting up in response to your retina.
You're having this experience of chihuahua.
But that's a huge amount of processing
that leads to the experience of chihuahua.
For both your eyes and for computers, it starts like this.
You either have retina responses,
or in the case of a computer vision, you have pixel values.
And you have to understand what's
in an image just from pixel values.
And you just look at those raw numbers,
it is very hard to tell.
We have this thing called a visual cortex.
And about 30% of your brain is dedicated to seeing.
So when you perceive the world, you
have a huge, huge mechanism that is behind that.
What seems easy to you is actually
using one of the world's most powerful computers.
OK.
I'm going to show you this example using numbers.
This is going to be my hard example.
What digit is this?
8 or 0.
Oh, no.
It's supposed to be a 0.
I really did choose a hard one.
And how about this one?
1.
OK.
It's a little bit easier for--
instead of chihuahuas and muffins,
I'm going to use 0s and 1s, a little bit
more straightforward.
You can imagine one, of the AI tasks
that you can do is to build an algorithm which
can detect chihuahua or muffin.
Or you can check for 1 or a 0 that's hand-drawn.
It's a classification algorithm.
It looks at a picture.
And it classifies it as either group A
or group B. Or in this group, group 1 or group 0.
So we're going to make this AI algorithm.
We want it to look at a picture and say something like,
this is a picture of 1.
And look at this picture and say something
like, this is a picture of a zero.
That's our goal.
This particular AI algorithm task is called classification.
It's not always perfect.
AI doesn't have to always be perfect,
but we want it to be fair, and we also
want it to be about as accurate as possible.
OK.
So how could we do this?
We're not going to go down the Herbert Simon approach.
We're not going to try and write all the rules of what
makes for a 1 or a 0.
We're not going to try to write all the rules of what makes
for a chihuahua or muffin.
It just turns out this approach doesn't work
the world is too complicated.
So instead, let's use some insights.
I'm going to tell you two great ideas.
One is artificial intelligence-- artificial neurons
as simple probability machines.
And then this idea of learning by example.
Shall we?
Let's do it.
OK.
Our brains are smart.
We have neurons.
So can we make a cartoon model of that?
Here is a cartoon model of how your brain works.
You've got billions of these things called neurons.
Neurons get inputs.
Those inputs lead to a buildup of charge
in the nucleus of the neuron.
And if that charge gets big enough,
the neuron starts firing.
Those inputs get weighted differently.
So your brain can decide to pay attention to some neurons more
than other neurons.
And that's your cartoon model.
We can build a cartoon version of this.
And in fact, we have done that.
We build these cartoon models.
They have inputs.
Each input can be weighted.
And then we're going to start firing or not firing.
In fact, when we build these cartoon models,
we built probability theory into it from first principle.
So we interpret the output as a probability of firing
or a probability of not firing.
This was a great idea.
And this idea changed the world, not
because you can get intelligence from one neuron,
but because you can start to put them together.
Just to walk you through this metaphor really quickly,
these cartoon neurons that have inputs,
those are like the inputs to a human neuron.
And those can have different values.
Every value, we're going to weight.
And then we're going to sum up all the weighted values.
And once we sum up all the weighted values,
you can imagine, it's like this little-- nice
little mathematical foundation.
We can then put it through a squashing function
that gives an output that looks a little bit
like a probability.
I said a whole bunch, but at the end of the day,
this is a very digestible model.
If you spent 10 minutes looking at it,
you would start to feel a little bit comfortable.
A little cartoon model.
Inputs get weighted, summed, squashed.
Think of the output as a probability.
That was our cartoon model of a neuron.
But the beautiful thing about these
is you don't get a lot of intelligence from one neuron.
You get a lot of intelligence from putting a bunch of neurons
together.
And so people started taking these little probability LEGO
blocks, and putting them on top of each other.
And you could put a bunch of them together in a computer.
And you can end up with a bigger probability machine.
Sometimes, we'll represent it in layers,
like you have your input layers, and then
layers of hidden neurons, and then a final layer.
And people would build these probability machines.
They would make the inputs equal to the pixel values.
And then they would try and get neurons in the middle
to fire or not fire.
And eventually, they would have a very final neuron.
And that very final neuron would end up
with a probability output.
And we would interpret that as a probability
of a classification.
It was a good idea.
And people would make these bigger and bigger and bigger.
I won't go--
I won't go into-- oh, let's take a look.
Do you guys want to see one?
Yeah.
Yeah, blocked.
[LAUGHS] OK.
That's OK, the picture captures it.
And again, so people would build these huge neural networks.
This is a visualization of one, where
you have hand-drawn digit here.
And then you just have these layers
of those tiny little LEGO blocks that I described.
They're tiny little probability units
stacked on top of each other.
And they would each be computing some probability
on top of previously computed probabilities.
And at the end, we would have a bunch
of neurons, which would represent
either this as a 0 or 1, 2, 3, 4, 5, 6, 7, 8, or 9.
It was a simple model.
But I've told you about this model.
I've given you no reason to believe that it's intelligent.
You can make this model.
You guys can code it up.
But where does the intelligence come from?
The intelligence is embodied in this model.
Where does it live?
And the answer is, it's in these weights.
How you set these weights can make--
you can construct this whole LEGO structure
of these probability units.
And the intelligence will come from having well set weights.
If you have well set weights, you
can have good probabilities which have meaning.
Well, if you could get perfect weights,
you'd have intelligence.
Do we hire grad students to go and just fiddle around
with those weights?
No.
It'd be great if we could get those weights
in a more automatic way, which leads to our second great idea,
learning by example.
Humans have beautiful brains.
But we also have this experience of learning by trying things.
We're not always just given rules on how the world work.
We go experience the world.
And we get smarter through experiencing.
And so there was this great idea in probability
in the '90s, which was, let's learn from example.
So imagine a single neuron.
You have these weights.
If they were the perfect weights,
it could be a smart neuron.
If they're random weights, it's not a smart neuron.
And we want to get those weights to be really smart.
You know what people did?
They would take examples.
Take the 0.
Turn on your neuron.
Have it fire.
And then if it was wrong, like this case,
it predicts it's a 1, when really, it's
a 0, what we would do is we would say, hey, algorithm,
could you adjust your weights so that you
would be a little less wrong?
And the algorithm is like, you know what?
I can.
You know why?
Because I'm based on probability theory.
Because I'm based on probability theory,
I can formulate that request mathematically.
And since I can formulate that request mathematically,
as a computer, I can do that.
I can take this input, this example.
And I can change my weights so that I could have been smarter.
And if you do this a little bit over and over again, and just
get a little smarter every time you see an example,
eventually, these models become intelligent over time.
And it really starts with this.
The neural network at its end makes a probability claim.
It says, the probability that this is a 0
is something like 0.9.
And you say, but it's actually a 1.
And so we're going to give you some loss.
And then it says, OK, how could I update myself?
And it says, well, that was my probability.
That's my claim.
I can understand these from my probability basis.
And then I can ask, how could I change so
that I could have been better?
How could-- what is my change in weights
that would improve or minimize my loss as much as possible?
And there you go, you can just write it as a formula.
And some of you guys are going to be like,
what do you mean you can just write formula?
That looks incredibly scary.
Here's the beautiful thing about CS109.
This looks scary right now.
This is something every single person in this class
is going to master and feel very comfortable with.
And you will understand that mathematics,
that is the basis of this huge revolution in AI.
And it's not just the basis of this revolution in AI,
it's math that will continue to change the world.
It is math absolutely worth knowing.
You will walk out of the class knowing what all of this means.
Of course, we're not there yet.
You're not supposed to look at that
and be like, yeah, obviously, it's
the derivative of loss with respect to each of the weights.
That's where we're going to get to.
In CS109, we're going to get there.
And not only are you going to be able to derive these,
we're going to derive all this work.
And then we're going to use it to start
to solve some problems.
We're going to solve some interesting problems
like detecting heart disease, figuring out
what movies people like, and doing some DNA analysis.
And I've told this story through chihuahuas and muffins.
But one of the interesting things happening in AI right
now is we have these tools.
When you learn how to use these, and you
learn how to use them appropriately,
then the next question is, what problems do you want to solve?
And we all have different answers for that.
But I would love to see these tools in your hands,
because I bet you guys would think of the coolest, most
useful things to do with this.
For example, instead of detecting chihuahuas
versus muffins, one of the things
that somebody here at Stanford figured out was,
can we take a photo of somebody's skin and detect,
is this cancer or not cancer?
And there's a lot of interesting things to say about this.
But one of the things I'd like to point out
is, this is somebody who was just a few years older
than most of you guys in this class.
And this was only a few years ago.
| at Stanford took some of these models
that we're going to learn about, and did
something really worthwhile.
OK.
So what's the story so far?
AI is going through a huge change.
And so far in its history, not once, but twice.
AI was revolution by people who understood their probability
theory really well.
End of story.
[APPLAUSE]
Except-- no.
[LAUGHS] Sorry.
Too much suspense.
Except, it obviously isn't the end of the story.
It just keeps changing.
And there's not the end of the story for a bunch of reasons.
We're going to learn core probability theory in CS109.
It'll be driven by application.
It'll be driven by our desire to understand this world.
But you're going to learn this fundamental theory that
explains a lot of natural phenomena.
And it's going to be much more useful than just learning.
There's an abundance of important problems.
And I'm going to just show you one open problem that computers
are really not that good at.
So this is a problem of one shot learning.
I'm going to show you an example of a single symbol.
And can you recognize which of these is an--
another instance of that symbol?
So that's your single training.
And I want you to figure out which
of these is another example.
Is this it?
No.
Is this it?
No.
Is this it?
No.
Is this it?
Yes.
Oh, fantastic.
You guys are so smart.
You just need one example to understand that.
And it's amazing.
Humans are brilliant in that way.
But typical machine learning often
needs to see millions and millions of examples.
And this is an example of, we really have a lot
left to do in the world of AI.
If you learn your probability, it's not
just good for machine learning.
If you're really into algorithms,
you just want to go into 161.
You want to understand how all these different algorithms that
have allowed us to use computers in such effective ways work.
You want to understand your probability.
So many modern algorithms use probabilistic analysis
for telling the story of how they work so well.
And they use probabilistic analysis for great ideas
in how to make cool ideas much faster.
We've all lived outside of the university
and had experiences where probability could
help us make good decisions.
There is this other part of CS109.
I'll teach you fundamental probability.
And there's going to be times in your life
when you will really appreciate that when somebody gives you
a probabilistic claim, that you can understand what that means.
If somebody gives you a probabilistic claim
and you get more information, you
could understand how to incorporate that more
information to improve your probabilistic understanding.
And it just makes us better understand the world around us.
And if you understand the world around us,
you can start to build things for that world.
A couple of other cool examples.
Some things aren't traditional AI with deep learning,
but maybe you want to be using some interesting conditional
probability, like Recommender Systems are
some examples of that.
What a time.
My God, with so much moving, we need
people to be building useful and important things
with technology.
But we also need people who understand
it very well to figure out how it could be used wrong,
and to be able to figure out when other people are doing
things that we don't like.
Ethics has become more and more important.
And it's not just ethics, it's the codification
of ethics into things like law.
There's huge fields and careers to be
made if you care about intersections beyond just
making the next cool DALL-E image generator.
But image generators are cool too.
Maybe you want to understand how it
made this picture of this giraffe and this bunny
on this airplane.
Sorry.
This is the image of image generation
from like two years ago.
And this is where it is now.
It's changed a lot.
I had to update my slides.
OK.
But there's a few stories.
I hope you guys are just excited to learn
this for the pure joy of understanding how
the world works, the pure joy of learning tools that
will allow you to build things that other people can't build.
But there is this practical side too.
It turns out, this is the concept
that is one of the most demand in industry and also
in academia.
They did this survey for PhD students coming in,
and they said, what do you wish you knew better
upon graduation?
And the most common answer was better understanding
of probability.
It's a cool thing to learn.
It's going to enrich us as people.
We'll walk out just being a little bit more enlightened
into the complexity of this world.
And we'll be able to do some cool stuff.
Speaking of cool stuff, here's just one story
to tell you about how we try and incorporate
the real world into CS109.
Spring 2017.
What innocent days.
Anyways, Spring '17, people in CS109 came in for their final.
And there was this problem.
And the problem says, hey, you've
been learning a lot of probability theory.
Let's use it to make a really smart eye exam.
Have you guys ever been to the eye doctor,
and they have close one eye and they're
like, that's an E, that's an A. And they're
like, that's not an A, that's a B. What are you talking about?
You know that one?
It's not the best exam.
And so on their midterm in spring 2017,
their job was using probability to come up with a better exam.
I just thought this was a neat problem
because I was trying to write my exam while at the eye doctors.
I'm like, this is boring.
This is boring.
I'm like, oh, my God, midterm problem.
This is awesome.
And when you think about this probabilistically,
you can take information like, what questions people
have gotten right or wrong?
And you can develop a belief distribution
over how well somebody can see.
And that's interesting because if you have a belief
distribution over how well somebody can see,
you can make an intelligent decision
under uncertainty for what to show next as a letter.
And then based on this, you can make an algorithm
which can dynamically give people different prompts
for what they could answer.
And this is a plot of how long an exam is.
And this is a plot of how crappy it is.
You want to be low because crappy is bad.
That is the exam that you get at the doctor's, the blue one.
Can be short or long, but generally, not very good.
The black one is the research exam.
So if you want to end up in a paper,
you have to study people's eyes using that black dot.
But using the CS109 algorithm, we
get way more accurate for much, much shorter exams,
which is exciting.
And we can tell that story in lots
of these beautiful probability plots, which we'll
get into later in the class.
It started in CS109.
It was just a midterm problem.
And then it got published in Science, in The Lancet.
And we had this Stanford acuity test,
which started in art class.
And it just tells the story of all these open problems.
You might feel like probability is solved.
It is not solved.
There's so many intersections.
Think about something you love.
Think about something you love that maybe not everybody loves.
There's a good chance, there is a meaty interesting problem
in the intersection of probability, computer science,
and that thing that you love.
We'll try and explore different ones.
Like for example, on last year's final,
we did things like taking chess.com puzzles,
and figuring out how good people are.
P-Hacking, Supply Chain Decision Making, Algorithmic Art,
like how can you use probability to just make
some beautiful images.
And on exams, people made images like this.
So beautiful.
You're like, exams are stressful, man.
People are not looking for beauty on exams.
But that's a philosophy we can get into later.
OK.
It's a foundation for your future, but not always
the most intuitive thing.
I'm going to tell you honestly, when I learned probability
in high school, I'm like, well, thank God,
I'm never going to need this in my life
because I want to study other fields of math.
And I was completely wrong.
I just found it rather unintuitive.
I didn't understand how much it was
going to change the world when I was in high school.
To give you an example of what I mean when I say probability
isn't always intuitive, let me give you
this canonical example.
Imagine a patient has a positive Zika test.
And this is something that we can probably
relate to from the two years of thinking
about probability on testing.
So if somebody has a positive Zika test,
how could you reason about the probability
that they actually have Zika?
I'm separating the idea that they had a test that
says they have Zika.
Zika from the underlying truth that they actually
have the disease.
We need some more information to answer this question.
So I'll give you some more information.
Very few people actually have Zika.
And then this test is not perfect.
So if people have Zika, 95% of the time, you'll say,
you have Zika.
If people don't have Zika, 7% of the time,
you'll say you have Zika.
How could it say you have Zika if you don't have it?
Well, we know tests aren't perfect.
So if you don't have Zika, there's
a chance that it'll still say you have it.
So now you have enough information
to answer this question.
What's the probability that you have Zika?
You just got a positive test.
But the right answer turns out to be only 9%.
Do you guys find that unintuitive?
You just had a test that says you have Zika.
It's a pretty good test.
Those aren't bad numbers.
Yet, you're probability of having
Zika is still very, very low.
And what's going on here?
Well, one certainly influencing factors
is the fact that not many people actually have Zika.
But if you want to understand this deeply,
you need to know your probability theory.
And certainly, the probability theory
would help you get to this answer.
But the one thing people don't often appreciate
is, you will then get more information.
The next day, you'll feel a little bit better,
you'll feel a little bit worse.
And probably, theory gives you a clean way
to update beliefs over evidence.
So the more information you gather,
you can keep updating your chance of anything
you care about inferring.
In this case, whether or not you have a disease.
Do you guys find that unintuitive?
Whoa.
Small number.
So here, we end up with this story.
Probability, super exciting, super important,
and something that needs study.
It's something hard to learn on your own
if you're not in a classroom.
So OK, here's my view of probability in CS109.
I'm going to teach you some beautiful theory.
And the beautiful theory that you
need to do the math that most people are not
able to do so that you can build and create
things that will bring some wonder
into some people's lives.
I want to get you through this wonderful journey.
It's not just about AI.
It's also about this uncertainty theory
and understanding probabilistic models
that we're going to get to.
But in order to get there, we need
to build a foundation first.
You need to understand your basics inside and out
because when you get to this stuff,
it will get a little more complicated.
And so our job is to build this solid foundation upon which
you can then improve.
And 109 is just the start of your journey.
You're going to take further classes in CS.
And they're going to build upon this even further.
So let's really make this foundation rock solid.
How does that sound?
Your future selves are going to love you.
They're like, thank you for making my foundation so
rock solid.
No problem.
Past me is into that sort of stuff.
OK.
So I'm excited.
You can tell, I'm excited.
But at this point, it'd be really fun to dive in.
So I'd like to get us to this point of understanding
the deep philosophy behind things
like artificial intelligence and algorithms
that make decisions under uncertainty.
But we got to build that foundation.
You want to start right now, we don't have to wait.
We can just do it now.
Let's do it.
OK.
I do this thing.
These classes are long.
And they're long because it turns out,
probability foundation has to be pretty hefty.
But I want you guys to be able to take things in.
I've talked about lot of things.
What I'm going to do now is going to give you
a two minute pedagogical pause.
I want you to meet the person next to you.
If you already know them, great.
Get to know them a little bit better.
If you don't know them, get to know them a little bit better,
because we're going to be on this journey together.
Two minute pedagogical pause.
Just talk to somebody.
Then we'll talk about some material.
[INDISTINCT CHATTER]
Let's bring it on back.
OK.
Let's do this.
Let's build ourselves a foundation.
Some people are like, foundations
are just not that exciting.
But houses are exciting.
Foundation is a thing a house goes on.
And you're like, I just want to make a house.
I want to make a tower.
I want to make a beautiful castle.
I want to make something exciting.
Have you ever tried to make a house without a foundation?
Not so exciting.
You got to build-- it's like-- it just
feels like hole in a ground filled with concrete,
but like, no, this is where it all starts.
This is the bedrock.
And the foundation of probability theory
is hilariously in counting.
And you might think like, Chris, I'm pretty good at counting.
I've been counting since I was two.
Well, today, you're going to learn how to really count.
Probability gets its Genesis from counting theory.
And it turns out, when people are
trying to understand how probability related
to the world of mathematics is through counting,
that we were able to deeply understand it.
If you can understand counting, it
will provide that foundation for you.
But it also turns out, it's a nice intuitive direction
into probability theory.
It's an easier space to reason about.
And it will give you a lot of the same insights that
show up in probability theory.
Counting is also useful as a computer scientist
because a lot of times, you're trying to decide,
am I writing an algorithm that will eventually stop?
And a lot of times, that's like, how many iterations
do I have to do?
And I actually have to count it.
And so counting, really, is that process
of counting how many elements there are.
In probability theory, we have a slight formalization,
but it's no more complicated than you imagine.
We think of an experiment.
So you're going to do something.
And that doing something can have outcomes.
And we're going to think about how many unique outcomes there
are.
So let me give you an example.
I've got a dice here.
And I can roll that dice.
And you can imagine, rolling the dice is the experiment.
And the outcome is just which side of the dice we see.
So if we think about it, how many outcomes
can you get from rolling a single dice?
Well, there's six outcomes.
You get 1, 2, 3, 4, 5, 6.
There's these nice discrete outcomes
to rolling a single dice.
What about, how many ways could you roll a dice that--
where you have only evens?
Well, you could imagine, my experiment is rolling the dice.
There's still six outcomes, but only three of those outcomes
satisfy the idea that you have an even outcome on your dice.
This is just a little bit of terminology.
So counting.
We're going to think about experiments.
And we're going to think about counting events.
And what we're going to think about counting
the outcomes that satisfy the idea behind those events.
So rolling a single dice, how many ways can get evens?
There's just three ways, 2, 4, or 6.
And you can bump this up a notch.
Rolling two dice isn't it that bumped up.
But we can really take this to a very interesting places.
And if you roll two dice, you can
imagine thinking about all the different outcomes
of rolling two dice.
You can have a 1 and a 1.
And you have a 1 and a 2, and 1 and a 3.
And you could sit there and go through every possible
combination, write them all down,
and eventually get that there's 36 different outcomes.
And we can write them all out here.
Here's the 1 and the 1.
Here's the 1 and the 2, the 2, the 2 and the 1, and so
on and so forth.
So here's a little bit of a first rule
to start thinking about this.
You could have counted 36 for the number of outcomes in dice.
But it turns out, we're going to learn the very first rule
to make counting a little bit easier.
This is one of the two core ideas to counting.
Turns out, if you know two ideas in counting,
how to count with steps and how to count with
or, you could derive all the higher level
counting that you could ever want.
So if you can really master these two,
everything falls from them.
The first idea is, if I want to count that there's
36 outcomes to these two dice, here's
one of the rules you can do.
You can break down this experiment into steps.
And any time you can break down an experiment into steps,
you can use one of your major pathways to counting,
called the step rule of counting.
OK.
I told you there's a little bit of reliance on 106-- oh, sorry,
103.
And this is what it looks like.
We assume that you've heard of sets before.
And we've assumed that you've seen notation like this.
Those vertical lines meaning the size of a set.
But if you've not seen that before, study this notation.
And that's the prerequisite that you would need to know.
You'd need to feel comfortable with some of this set notation.
So we're going to say the outcomes to an experiment,
if you break it down to steps, could be thought of using
the step rule of counting.
So when I say breaking it down to steps,
let's say the outcome of the experiment
comes from two steps, step A and step B.
And step A will have its own set of outcomes.
And step B will have its own set of outcomes.
And let's say, there's some number of outcomes in step A,
and some number of outcomes in step B.
The step rule of counting says, if it is such
that the first step doesn't affect how many options there
are in the second step, so your first choice
isn't changing how many choices you
have in the step, second choice, you
can just figure out the number of outcomes
using multiplication.
So if you have a--
so if you have a two-step process,
where you have step 1 has A outcomes
and step 2 has B outcomes, if after step 1,
there's always the same number of outcomes in step 2,
the total number of steps in your two-step process
is just going to be the size of the number of outcomes
in A times the size of number outcomes in B.
You could have named the number of outcomes in A, M.
And you could have named the number of outcomes in B, N.
And then it would just be M times N.
This is a really, really fancy way of saying,
if you can figure out an experiment
and break it down into steps, you can just use multiplication
to do your counting.
I love this example.
There's so many beautiful things to be
said about counting, why it's interesting, just
from the single example.
Not too long ago, there was this art project.
They took 12 pixels.
And they were going to try and generate every possible image
that you could with 12 pixels.
So you can imagine, first, they start with these pixels.
Then you could slightly tweak this pixel.
And they're going to try and generate
every single possible image.
So my question for you is, how many unique images can you
get from 12 pixels?
And this will give us an idea--
if you're a computer scientist, you
might want to care how much work there is in this task.
But also, it's going to be good practice in this first most
important rule of counting, the step rule of counting.
So see if you can use a step rule of counting
to answer the question, how many unique images are there
for 12 pixels.
I'm going to give you an important fact.
And I can derive it for you later.
There's this idea of how many colors can each pixel be.
And it's about 17 million.
There is 256 options for red, 256 options for blue,
and 256 options for green, in how computers represent colors.
And so if you multiply 256 times 256 times 256,
because you think of the process of choosing color
as choose your red, then choose your green,
then choose your blue.
Put that together, you have a color.
Three steps.
No step changes.
How many options you have in the other ones?
256 times 256 times 256 gives you 17 million.
There's about 17 million out of--
17 million different colors that a computer
can represent for every pixel.
So if you have 12, how many different unique images
were they going to generate in this piece of artwork?
Talk to the person next to you.
Get to know them.
Try and solve this interesting math problem.
Try and talk about it in the terms
of the step rule of counting.
And think about what your steps are.
I'll give you a moment to think about it.
[INDISTINCT CHATTER]
Oh, this is great.
It is so wonderful just to hear people thinking.
We're all going on this journey together.
We're going to spend 10 weeks.
And we're going to be synchronously trying
to learn the beauty of probability together as a team.
What a beautiful thing.
This cacophony of people thinking about a problem just
really exemplifies that for me.
Thank you.
Thank you for that.
OK.
Let's do it together, though.
How did people think about how many unique images are?
How could you break this into steps?
Did somebody come up with a series of steps
that they want to share with people?
Yeah.
I thought of each pixel having some stage, right?
Each of the pixels can be 1 of 256 cubed million--
just like 256 cubed colors.
And so if each of them are independent
and they're not influencing the number of outcomes
the other pixels have, then what you could do
is just multiply the number of outcomes of each pixel.
Where are your steps?
This is exactly right.
But I just want to use the language of steps.
What are the steps?
How many steps are there?
And what's your first step?
Right.
The first step is determining the color of the first pixel.
So we got pixel 1.
Step 1, choose that color.
Does that change how many colors you're
allowed to choose for pixel 2?
No.
It doesn't affect at all.
So step 2.
What's step 2?
You determine the color of that pixel.
So-- and how many steps we have?
12.
Yeah, 12 steps.
And no choice for any one step changes, how many choices
you have for the other one.
That's why we can just multiply.
And how many choices you have for step 1?
You said 256 cubed, that's 17 million.
So 17 million times, how many steps for 2?
17 million.
You're like, that's a lot.
Two pixels is all we need.
But no, no, there are more.
17 million times 17 million times 17 million.
Because I want to see what that looks like,
I put up a lot of these questions.
You guys, I love programming.
So I made this thing called the P Set
app, so you guys can do stuff in this super cool app.
And I put all the problems from today's lecture there too.
So you can try them out, get your answer,
and put them in here.
This is how many unique images-- can you guys see that number?
Oh.
OK.
Well, that is the number, which is how many unique images there
are from 12 freaking pixels.
That's 20-- sorry, 17 million times by itself
12 different times.
This is what that looks like.
And 12 to the power--
or sorry, 17 million to the power of 12.
And why is it 17 million to the power of 12
and not the other way around?
It is because you have 17 million
times 17 million times 17 million
times itself 12 different times.
That's how you can get 17 million to the power of 12
as being the number of unique images.
5.8 times 10 to the power of 77 doesn't look that large.
You're like, that looks pretty large.
And it really looks large when you look at it in terms
of just this raw number.
That is what that-- that's how many unique images you
can get from 12 pixels.
I did want to just review.
I said that there is 17 million.
It's because every single pixel has
a red channel, which has 256, and blue, which has 256,
and green, which has 256 options.
So you can imagine, every single pixel,
you think of it as three steps.
Choose your red.
Choose your blue.
Choose your green.
Do you know why 256?
Step rule of counting again.
There's actually eight bits to represent the red channel.
So there's eight different places where
you can choose a 0 or a 1.
So if you have eight bits and this could be 0, 1,
there's two choices here.
Two choices for 0, 1 here.
Two choices, two choices, two--
two choices, two choices.
If you have eight binary values, how many unique numbers
can you make?
2 to the power of 8 equals to 56.
Step rule of counting is just all over.
OK.
So if 17 million to the power of 12
is how many images you get from picture C,
how many unique images are there from picture B?
Just yell it out loud.
[INAUDIBLE]
17 million to the power of 300.
Do you know how big that is?
OK.
To give you a sense, that--
people have estimated how many atoms there
are in the known universe.
If you went and counted every atoms--
you need better things to do.
But if you went and counted every atom,
we think you would get to about 10 to the power of 80.
Do you remember how big this number was?
It was 10 to the power of 77.
There is almost as many unique images
in these bloody 12 pixels as there are
atoms in the known universe.
17 million to the power of 300 isn't more than
the number of atoms in the universe.
It's so much more.
And if you get to something like 12 million pixels, which
is small compared to what your phone can do,
it makes the number of atoms in the universe
look like an infinitesimally small number.
In fact, you would have to have a whole universe
inside of every single atom to even
get remotely close to how many unique images there are.
This matters.
This explains why some things are
hard for computers, why computations
can be hard to compute.
Being able to count and being able to avoid the step
rule of counting in some of your algorithms
is key to being a computer scientist.
But there's also some deep philosophy here.
Can I just aside for a moment?
Have you guys ever wondered, how are we going to, as a species,
keep trying to grow in a world with finite resources?
We have a whole society based off of infinite growth,
but we have a world that only has finite things.
That seems like a problem, right?
And it is true.
There are finite atoms.
And there's finite things in this world.
But once you get into the world of counting and combinatorics,
there are so many infinities of combinations of things.
We live in a world where there might be finite things,
but there's infinite combinations of those things.
It's not infinite, but just the step rule of counting
leads to so many unique combinations
so fast that our world of combinations
is incredibly large.
And I just find this some nice little philosophy
for your first day of class.
Anyways, long story short, the answer is 17 million
to the power of n, where n is the number of unique pixels.
And when we think about the number of unique images,
we're now talking about way more than the number
of atoms in the known universe.
How cool is that?
OK.
So here is your numbers, 72 million to the power of n.
Oh, well, slightly off.
But incredibly, incredibly large numbers.
So I told you that the step rule of counting
was one of two fundamental rules.
And if you can master these two fundamental rules,
you could derive basically all of the mathematical field
of combinatorics, which is the ancestor of probability theory.
What's that other rule then?
The other rule, man, I feel almost shy telling it to you,
but I have to because you have to know its name.
It's called the sum rule of counting.
We're going to think about a different way of counting.
Previously, we were counting by steps.
You would take an experiment and try and split it
up into step A or B, or 12 different sub-steps.
This other way of counting is we're going to say,
we're going to count by ors.
We're going to say, my outcomes can either come from set A
or from set B.
So if you can have outcomes which are either from A or B,
and you want to count how many outcomes there are,
you could use the sum rule of counting.
If you have a very special case, where
there is no element that's in both of these sets,
then it turns out the total number of outcomes
is just going to be the total outcomes in A
plus the total outcomes of B. You could imagine,
steps leads to multiplication and/or leads to addition.
That's a very special case where there's
no element that's in both.
We call these sets mutually exclusive.
So there is no element that is both in set A and in set B.
And I want to give you just the intuitive idea to realize
how obvious a statement what I made is.
So we're going to count my daughter's toys.
And we're going to live in a world
where she only has balls or plush animals.
But oh, my God, we could talk about capitalism
and how many toys there are for kids.
It drives me crazy.
But I wish we only had these toys, but we have more.
Anyways, that's not important right now.
What is important right now, imagine my daughter only
has balls or plush animals.
What I'm saying is, you can think
of the number of toys she has as either coming from set A
or set B. And there's no toy that's in both sets.
So you can say, there's two toys in this set.
And there's three toys in this set.
So I'm saying the total number of sets,
you can-- total number of toys, you can just get by adding.
You're like, Chris, are you really teaching me this
at Stanford?
In a college level class?
Yes.
Yes, I am.
So how many toys are there?
Just humor me.
Five.
You're like, yes.
Yes, there are five.
There are, in fact, five, because there
is two from set A, and there's three from set B.
Because they're mutually exclusive,
you can just add them.
[LAUGHS] Good times.
OK.
But this isn't the end of the story
because this really relies on a very important rule.
This is only if there is no element in A and B.
So they're mutually exclusive.
Let's play with this a little bit.
Here's a more interesting problem.
And this problem is going to make us think a little bit more
deeply.
And it's going to think about both counting with
or and counting with steps in the same time.
You've got these two tools.
We're going to try and bring them together.
OK.
Here's my problem for you.
A six-bit string.
So that's six 0s and 1s.
So for example, here is a valid six-bit string, 001100.
It's six bits.
Everything is a 1 or 0.
We're going to send them over the network.
But the receiver is only going to recognize
as valid bit strings that start with a 0, 1,
or end with a 1, 0.
Is this valid or invalid?
Invalid.
Invalid, because it neither starts with 0, 1,
nor does it end with a 1, 0.
Our question is-- let's just practice our counting.
And let's count how many valid strings there are.
And you're like, whoa, how did you break this apart?
Well, we have two rules.
We have-- you can take your problem
and try and break things into sets.
Or if you have a problem, you can try and break things
into steps.
Two mechanism for taking a big problem
and breaking it into smaller pieces.
There is an or in the question because valid strings either
start with 0, 1, or they start with 1, 0.
And when I see that or in the question,
my mind immediately goes to the step rule of counting.
So we can say, why don't we count
how many strings start with 0, 1,
and how many strings end with 1, 0.
We can split that up and we can just do one at a time.
So with the person next to you, count
how many valid strings are there that start with a 0, 1.
Talk to the person next to you, see
if you can use one of these two rules
to break that down, and figure out
how many valid strings start with 0, 1.
[INDISTINCT CHATTER]
OK.
Let's do it together.
OK.
So just to be clear, we were given a gargantuan problem.
And our job-- our strategy is to use these two things to break
it into smaller pieces.
We did the first step together, which
we're going to split it into counting how many strings
start with 0, 1, and counting how many strings end with 1, 0.
And then the task I gave you was,
can you count how many bit strings start with 0, 1?
Anyone have an idea?
And really, if you could appeal to either the step
rule of counting or the or rule of counting,
that'd be very helpful.
Yes.
16, because you know that your first two numbers
have to be 0 and 1.
And then you have four more steps that you need to take.
Yes.
And so you take your first step, it's
either 1 or 0, so that's two.
Repeat choices for your first step.
Repeat choices for your second step and so on until you
have four steps.
OK.
And actually, you can say that there's a fifth step.
You can take that putting a 0, 1 is step 1.
There's just one choice for that.
You must put 0, 1.
And then you have two choices for the next bit,
two choices for this one, two choices for this one,
two choices for this one.
That's fantastic.
You guys know, I like to make things physical.
It makes things more interesting for understanding.
So I've got here Coke 0s and Coke 1s.
And you're like--
[LAUGHTER]
OK.
Let me just say something that's on my mind.
This is not a Coke Zero, this is a Diet Coke.
Because I went to the bookstore and I was like,
do you have Coke Zero.
She's like, no, we have Diet Coke.
I'm like, no.
I need a Coke Zero for my demo.
And they're like not at all understanding.
They're like, it's the same number of calories, basically.
But anyways, this is my 0.
This is my 1.
Step 1, start your string.
Has to be 0, 1.
There's only one choice for those first two.
But then you get four more choices.
You could either put a 0 or a 1 for your next string.
This step has two options.
Then you have one more choice for the next bit-- two choices,
sorry.
A 0 or a 1.
Two choices, you have to choose one of them.
And then we've got 1, 2, 3, 4.
We've got two more steps left.
Choose one of these two.
And then for your very final choice,
you have two more choices left.
So if there's 1 times 2 times 2 times 2 times
2, 2 to the squared, to the third, to the fourth.
16.
Thank you very much.
That was exactly right.
So there's 2 to the fourth strings that start with 0, 1.
Do you guys want to see them all?
Maybe, you don't believe me.
There they are.
There are all the strings that starts with 0, 1.
And this is what it looks like to enumerate all of those.
In fact, any time you find counting hard, use your ability
to write awesome programs.
And you could enumerate every single possibility
and really convince yourself that you counted right.
How many strings end with 1, 0?
[INAUDIBLE]
It's the same thing, just backwards.
There still are going to be the same number of sets.
OK.
This is 1-- no, it has to end in 1, 0.
So this is my Coke 0, obviously.
This is my Coke 1.
So step 1 is to put them at the end of the string.
And then there's four places that can either be or 0 or 1.
And there's two choices for each of those four steps.
So two choices for this one, two choices for this one,
two choices for this one, two choices for this one.
So you can think about it as step 1,
fix these last two to be 1, 0.
And then you have four steps left to construct your string.
You have two choices for this step,
two choices for this step, two choices for this step,
two choices for this step.
Very importantly, when you choose or 1 or 0 here,
it doesn't change whether or not you can choose a 1 or 0
here, right?
If you chose a 1, this can still be a 1.
If you chose a 0, this can still be a 0.
So the number of choices in one step
doesn't affect the number of choices in another step.
OK.
Hey, we use both of the rules in one problem.
We use the step rule of counting to figure out
how many strings end in 0, 1.
And we use a step rule of counting to figure out
how many strings end in 1, 0.
Now we've got an or of two sets.
We have set A and set B. And our results
can come from either of them.
So we can just add them.
And you're like, 16 plus 16, I'm done.
Wohoo.
And you're like, take your answer,
and you go to your PSET app, your fun little PSET app,
what a good time.
And you go over, what's 16 plus 16 real fast?
32.
And you put in your 32.
And you hit Check Answer.
And it's checking answer.
And I hope I have internet, enough to get to my server.
Oh, it's a little optimistic.
It's like, keep trying.
Like, you jerk.
Just tell me I'm right.
What?
Did Chris lie?
I don't lie.
I try not to lie.
But did he lie?
Something's wrong.
Somebody knows.
Yeah, that little box, only they're not--
yeah, there's [INAUDIBLE] fours.
You got to get rid of that.
OK.
The step rule of counting is very useful.
As long as step A doesn't change how many elements there
are in step B, we can use it.
The or rule of counting has this very hard constraint.
You can't have elements that are in both sets.
This is what that looks like.
There is this element here.
And that exact same bit string is right over there.
We've counted it twice.
It's not two different unique strings.
It's just one string, but we've counted it twice.
So if this was a midterm, and you guys were like,
I want to get my partial credit.
I want to get the right answer.
How would you just hack this together really quickly?
Substract 4.
Yeah, you just subtract 4 because it double counted them.
And you get doo, doo, doo, doo, doo, 28.
And you're like, 28.
Doo, doo, doo, doo, doo, come on.
Yeah.
Woo hoo.
So that felt hacky.
We were just like, OK, we want to subtract off 4.
But it turns out, subtracting off
4 is, in fact, a very elegant thing to do.
If you want to count by ors, in the case where
this condition doesn't hold, there is a very simple fix.
You just need to count how many elements are in this overlap.
How many elements are in both?
If you can count how many elements are in both,
you just subtract off that number.
So it leads to this more general rule of counting with
or, which is if you want to drop this box,
then the total number of outcomes
is going to be the size of elements in set A
plus the size of elements in set B.
But then you have to subtract off
all of your double counting.
And you have to say, let's subtract off all the elements
that are in both sets.
Can people on that side see this?
I know it gets a little bit close to the screen.
OK.
And that leads to the outcome that is correct.
And also, just the final rule to learn today.
It has a fancy name.
It's called Inclusion/Exclusion.
And it is one of the fundamental ideas of counting.
In fact, it's very close to one of the axioms
upon which all of probability theory is based.
But it's a pretty simple, easy to understand idea.
We can count either or or by steps.
And when you count by or, you've got this very general rule.
If your outcomes are either coming from set A or set B,
you can just use this formula.
And this is the summary.
Core counting really comes down to counting with steps
or counting with or.
Counting with steps, we can just use multiplication
as long as this constraint holds that step A doesn't
affect step B.
And when you're counting with or, so outcomes either
come from A or B, you can use this formula.
And now you've got two great formulas.
And this counting with or, if you subtract off the overlap,
has no limits.
You can use it any case you're counting with or.
OK.
Have a challenge for you guys.
This is my little brain teaser to end the day.
So Boba, we all love it.
Imagine the letters B, O, B, A. That's funny,
This image is huge, but the letters are tiny.
My question for you is, how many unique orderings are there
of the letters B, O, B, A.
And we can start writing them out.
There is one unique ordering.
You could do B, B, O, A. They don't have to be valid words.
I just want to know, how many unique ways could you
order all the letters in Boba?
And this is our final challenge for today.
And you can think if you can figure out
how many unique ways there are of doing Boba,
and you want to bump it up, you can say, how many unique ways
are there doing Mississippi?
I'm going to give you guys some time to talk about it.
This isn't the answer, is it?
Maybe it is the answer.
I'm going to give everyone a chance to think about it.
So think about it.
How could you figure out-- how many unique orderings
are there of the word Boba?
And we're going to be taking our counting up to the next level.
If you want an easier one to start with,
if you're finding this hard, think
about how many unique orderings are there of something where
all the letters are unique.
And that would be an easier problem to solve on your way
to the answer.
Talk to-- talk about this with the person next to you.
Let's see where we can get to.
[INDISTINCT CHATTER]
OK.
You guys are awesome.
I'm so looking forward to the rest of this quarter.
This is going to be such a good ride.
OK.
I don't want to talk about the answer to this harder problem.
I want to talk about the answer to this easier problem, where
all the letters are unique.
And I want to think about orderings for these number
of unique letters.
So how can we think about the number of unique ways
of ordering A, B, C, or D?
going to give you a four-step process.
Step 1, choose letter 1.
How many choices are there?
Four.
And let's say you chose A. And there's four choices here.
How about for step 2?
My claim is that your step 2 is you're going
to choose the second letter.
But are there four choices anymore?
Oh-oh, is that breaking a rule?
The step rule says that after you make your first choice,
it can affect how many choices there are in the second one.
Does your choice in the first step change how many choices
you have in the second one?
Yes.
Oh, it's tricky.
Well, if you choose A, there's three things left.
If you choose B, there's three things left.
If you choose C, there's three things left.
If you choose D, there's three things left.
It turns out, no matter what you choose for the first letter,
there's still three things left.
So that allows us to use a step rule of counting.
So there's three things left.
And let's say, we choose C. No matter
what you chose for the first two letters,
there's still going to be just two letters left.
So your third step is to choose that next letter.
And there's two choices.
So that could be B.
And then finally, your last one will be determined.
Because you've chosen three of the letters, that last one,
there's not really a choice.
There's only one option left, no matter what you chose.
Your first step changes the options for your second step.
But your first step doesn't change
how many options there are.
And it's the second thing that needs
to be true to use a step rule of counting.
And since the second thing is true, then
the total number of ways of organizing A,
B, C, D is 4 times 3 times 2 times 1.
That is easier than thinking about the orderings of this.
Why is it easier than thinking about the orderings
of this word?
The silly Bs, oh, my God, make our lives so much-- darn you,
Bs.
So I'm not going to tell you the answer to this.
I'm going to leave this as a little bit of a tease for you
guys to try and think about on your own.
Can you figure out how many orderings are there?
If you do figure it out, what you can do
is you can go to the website, go find lecture 1.
Here's these optional problems where I just write up
the things we talked about.
And you can go try.
And if you get your right answer, you can put it in here.
And you can see if you got the answer right.
Have a wonderful rest of the first day of the quarter.
Come back on Wednesday.
And we'll continue this wonderful journey of CS109.
[APPLAUSE]