Nagoya University, Fall 2022

Lecture 1
Course information & overview, Minimax,and introduction to Google colab & Python

https://www.henrikbachmann.com/mml2022.html

Who is teaching?
Lecturer

Henrik Bachmannwww.henrikbachmann.com
henrik.bachmann@math.nagoya-u.ac.jp
Teaching Assistants

Risan

Chino

Vic

Yasin
TadashiWhat where?
Homepagehttps://www.henrikbachmann.com/mml2022.html
Contains schedule & course materials•

Discord server

https://discord.gg/MmWH7aCafr

Will be used for discussions and small announcements

NUCT

https://ct.nagoya-u.ac.jp/portal/site/2022_0061621

Will be used for Homework submission & importantannouncements

For who is this lecture?
•G30 Students of year >= 2.
(For first year students: Consider taking this course in your second year)••

NUPACE Students.
Japanese students who want to attend English lectures.

Basic knowledge in Linear Algebra and Calculus is helpful(and sometimes necessary to understand everything in detail)If you are Japanese student, please register at the NUEMI project for this lecture:
http://labguide.bio.nagoya-u.ac.jp/NUEMI/registration/

Free extra support & Study sessions

What is this course? References••••

This course is a “Special Mathematics Lecture” (Introduced by Prof. Richard)
Can give 2 credit points for ”Optional Courses”.
Does not count for your final grade.
You need to be registered in the NU Portal if you want these credits.

“Just for fun” Lecture

Learn together. Try to participate. Help others•••

This course is based on “CS229: Machine Learning” from Stanford university(http://cs229.stanford.edu/)
I will always provide the slides and code I use during the lectures
We are trying to create lectures notes.

Goal of this lecture:•••

Get an overview of algorithms used in machine learning
Understand the mathematics used in these algorithms
Learn how to implement (simple version of) them in Python

overview of machine learning libraries
Not goal of this lecture: Give(tensorflow etc.) and learn how to use them

Homework
Your grade will be based on programming & math assignments.
We will use NUCT for the submission.

Content of the assignments
Don’t worry if you have no experience at all in programming!
Don’t worry if you have a lot of experience in programming!
(We try to include some challenging bonus questions)• We will try to do a mix of programming exercises (Python) andmaybe some math exercises.
• Try to make basic programming exercises, which can be madefancy by the more experienced students, but which can also besolved by students with not so much experience.
• We did not decide on an exact grading model, but grading will not
be strict!
• Roughly: 20 points each Homework and there might be around 5-6
Homework assignments.

Tutorial
Time: Thursday at 18:15
Place: Same room (A250, Science Bld. A)• Organized by the TAs.
• Talk again about the content of the lecture.
• Do the Assignments with the help of TAs &other students.

There will be two tutorials before Lecture 2
Goal: Do Homework 1 together with the TAs

What is machine learning
Common definition:
Machine Learning is the study of computer algorithms
that improve automatically through experience
Found its way in a lot of daily life applications, e.g.
• Self driving/flying cars/trains/planes/rockets• Computer games• Image & Video & Sound processing• Speech recognition (Siri, Alexa,…)• Translation (Google translate)• Weather forecast• Data analysis• Email spam
• Robotics• and much much more…

Not machine learning:“Classical machines / programs”
Programmer understands theproblem and can implement an
explicit algorithm, which turns an
input into an output.

Example: Determinant of a matrix
detWhat do you see?

Want: Cat & Dog detection machine
C&D“This is a dog!”
Cat & Dog detector

Of course, I know how cats and dogs
look like. But I do not know how todescribe it with a formula or algorithm!
Smart person

How do we know?
This is a dog because…
•

I saw a lot of dogs & cats in my life.

•Whenever I saw a cat I was told by my parents„This is a cat!“. When I saw a dog they told me“This is a dog.”.

•

I learned to distinguish between dogs and cats.

•But it is hard for me to explain the exact
difference.

Machine learning
We can create machines/programs which we can teachCatDog

After Training

Training

DogDog!
… with 95% certainty!

Cat & Dog detector

Machine learning overview

Supervised learningClassification (discrete output)

Output = category (e.g. “dog”, “cat” or “1”,”2”,…,”9”)”2”
Handwriting recognition

Regression (continuous output)

Output = real number (like “price”, “weight”,…)
Size: 70𝑚!
Rooms: 3

Learning by using some trainingsdata

90.000 Yen
Apartment price prediction

Unsupervised learning

k-means clusteringReinforcement learning

Examples of AI in Chess, Go & Computer games••••

1996: Deep blue (not machine learning)
2016: Alpha Go
2017: Alpha Zero (plays chess, shōgi & go)
2019: AlphaStar (Starcraft 2)
rningaeltncemerofni
Re
1996: Garri Kasparow (Chess worldchampion) loses against Deep blue.

2016: Lee Sedol loses against Alpha Go.
2019: AlphaStar beats Starcraft 2 pro gamers.

Over of the topics in this course
1. Introduction to programming in Python
2. Supervised learning: Linear & logistic regression
3. Generative Learning algorithms: Naive Bayes
4. Reinforcement Learning: Q-Learning
5. Unsupervised learning: k-means clustering
6. Neural networks

Let us have a look at Google colab andHomework 1Minimax algorithm•A algorithm which can be used to solve, for example, perfect knowledge zero sum
games (if one gains, another loses) of two players taking alternate moves.
(E.g. chess, tic-tac-toe, etc.)•

Goal: Assign an evaluation (number) to a game state.

•

Usually: This evaluation is real number with the following intepretation• Positive: Player 1 has a higher chance to win• Negative: Player 2 has higher chance to win•

Player 1 wants to maximize this evaluation and Player 2 tries to minimize it.
White moves

Black moves

Minimax algorithm example (Tic-Tac-Toe)
Let us evaluate the following board state

Evaluations:
X wins: 1
O wins: -1
Draw: 0

Minimax algorithm example (Tic-Tac-Toe)
Evaluations:
X wins: 1
O wins: -1
Draw: 0

Minimax (Pseudocode)
function minimax( board, is_maximizing )if board is in endstate (game over) thenreturn evaluation of the board (who won?)
if is_maximizing thenvalue := −∞for each possible move donewboard = do the move on the board
value := max( value, minimax(newboard, FALSE ) )return valueelse (* minimizing player *)value := +∞for each possible move donewboard = do the move on the board
value := min( value, minimax(newboard, TRUE ) )return value

Minimax (up to a fixed depth)
function minimax( board, depth, is_maximizing )if board is in endstate (game over) or depth=0 thenreturn evaluation of the board
if is_maximizing thenvalue := −∞for each possible move donewboard = do the move on the board
value := max( value, minimax(newboard, depth-1, FALSE ) )return value
else (* minimizing player *)value := +∞for each possible move donewboard = do the move on the board
value := min( value, minimax(newboard, depth-1, TRUE ) )return value