SW4428: 컴퓨터비전
Lecture 3: Linear Regression and Logistic Regression
Sunok Kim
Department of Software Engineering
sunok.kim@kau.ac.kr
Today’s Topic
• Linear Regression
• What is Regression?
• Regression Function
• Linear Regression
• Cost Function for Linear Regression
• Gradient Descent
• Logistic Regression
• What is Classification?
• Logistic Regression
• Cost Function for Logistic Regression
9
Supervised Learning vs Unsupervised Learning
Supervised Learning Unsupervised Learning
10
Linear Regression
11
What is Regression?
• Regression vs. Classification (in CV)
• Examples:
12
What is Regression?
• Examples of Regression 500
• Housing Prices 400
Price
(Portland, OR) 300
(in 1000’s
200
of dollars)
100
0
0 500 1000 1500 2000 2500 3000
Size (feet2)
• Training Set of Housing Prices Size in feet2 (x) Price ($) in 1000's (y)
2,104 460
1,416 232
1,534 315
852 178
… … 13
What is Regression?
• Regression is to relate input variables to the output variable,
to either predict outputs for new inputs, and/or to understand
the effect of the input on the output.
$! ∈ ℝ
“output”
!! ∈ ℝ"
“input”
14
What is Regression?
• Dataset for Regression
• In regression, dataset consists of pairs { "! , $! $
!"# },
where $! is the &-th output and "! is a vector of ' input.
• The number of pairs ( is the dataset size.
• ' is the dimensionality.
* Machine Learning Term for Regression
• Input variables are also known as features, covariates, independent
variables, predictors, etc.
• Output variables are also known as target, label, response, outcome,
dependent variable, measured variable, etc.
15
What is Regression?
• Two Goals of Regression
• In prediction, we wish to predict the output for a new input vector,
e.g., what is the weight of a person who is 170 cm tall?
• In interpretation, we wish to understand the effect of inputs on output,
e.g., are taller people heavier too?
• Examples:
• What is the life-expectancy of a person who has been smoking for 10
years?
• Does smoking cause cancer?
• A massive scale earthquake will occur in California within next 30 years.
16
The Regression Function (Hypothesis)
• We need to find a mapping function that approximates
the output “well enough” given inputs.
$! ≈ &(!! ), for all )
Training set
Learning Algorithm
!! Mapping Function $! ≈ &(!! )
17
Linear Regression
• Linear regression is a model that assumes a linear relationship
between input and output.
“Weight”
“Height”
• Why learn about linear regression?
• Plenty of reasons: simple, easy to understand, most widely used, easily
generalized to non-linear models.
Most importantly, you can learn almost all fundamental concepts of
machine learning with single regression alone.
18
Simple Linear Regression
• With one-dimensional input, we get a simple linear regression.
$! ≈ & !! = &# !! = +$ + +% !!
• Here, w = (+$ , +% ) are the two parameters of the model.
They describe &# ! .
$! ∈ ℝ &# !
)#
“Weight”
)% 1
“Height”
!! ∈ ℝ 19
Learning or Estimation or Fitting
• Given data, we would like to find the parameter w ∗ .
• This is called learning or estimating the parameters or fitting
the model.
• To do so, we need an optimization algorithm.
20
Cost Function
• Training Set of Housing Prices Size in feet2 (x) Price ($) in 1000's (y)
&0 = 2,104 -0 = 460
&$ = 1,416 -$ = 232
&: = 1,534 -: = 315
&; = 852 -; = 178
… …
• Consider the following model: $! ≈ &# !! = +$ + +% !!
• How can we estimate (or guess) values of w = (+$ , +% ) given
the data?
21
Cost Function
• Consider the following model: $! ≈ &# !! = +$ + +% !!
3 3 3
2 2 2
1 1 1
0 0 0
0 1 2 3 0 1 2 3 0 1 2 3
)% = 1.5 )% = 0 )% = 1
)# = 0 )# = 0.5 )# = 0.5
22
Cost Function
• Idea: Choose w = (+$ , +% ) so that &# ! is close to $ for
training dataset { !! , $! (
!'% }.
(
1
$ min 6 (&# !! − $! ))
# 5
(!! , $! ) !'%
(
1
8 w = 6 9 (&# !! , $! )
5
! !'%
w ∗ = argmin 8 w
#
23
Cost Function
• A cost function (or energy, loss, training objective) is used to
learn the parameters (w) that explain the data well.
• The cost function quantifies
how well our model explains the data or
how costly our mistakes are.
24
Cost Function
• Model: • Model:
&# ! = +% ! &# ! = +$ + +% !
• Parameters: • Parameters:
+% w = (+$ , +% )
• Cost function: • Cost function:
( (
1 1
8 w = 6 (&# !! − $! )) 8 w = 6 (&# !! − $! ))
5 5
!'% !'%
• Goal: • Goal:
w ∗ = argmin 8 w w ∗ = argmin 8 w
# #
25
Cost Function
&# ! 8 +%
(for fixed )# , this is a function of ") (function of the parameter )# )
$ 3
/ )# 3
2 2
1 1
0 0
0 1 2 3 -0.5 0 0.5 1 1.5 2 2.5
" )#
26
Cost Function
• Model:
&# ! = +$ + +% !
• Parameters:
w = (+$ , +% )
• Cost function:
(
1
8 w = 6 (&# !! − $! ))
5
!'%
• Goal:
w ∗ = argmin 8 w
#
27
Cost Function
&# ! 8 w
(for fixed w, this is a function of ") (function of the parameter w)
500
400
Price ($)
E F., F0
300
in 1000’s
200 ." = 50
100
.# = 0.06
&! ' = 50 + 0.06'
0
0 1000 2000 3000
Size in feet2 (x) F. F0
“Contour Plots” or “Contour Figures”
28
Cost Function
&# ! 8 w
(for fixed w, this is a function of ") (function of the parameter w)
500
400
Price ($) 300
in 1000’s <"
200
100
0
0 1000 2000 3000
Size in feet2 (x) <!
29
Cost Function
• Examples
• Mean Square Error (MSE): one of the most popular cost function.
$
1
MSE w = 4 (6/ "! − $! )0
(
!"#
• Mean Absolut Error (MAE)
$
1
MAE w = 4 6/ "! − $!
(
!"#
30
Cost Function
• Desirable Properties of Cost Functions
• When the target $ is real-valued, it is often desirable that the
cost is symmetric around :, since both positive and negative
errors should be penalized equally.
• Also, the cost function should penalize “large” mistakes and
“very-large” mistakes similarly.
9(=! ) $
=! ! 31
Cost Function
• Desirable Properties of Cost Functions
• Statistical vs.
Computational Trade-off
• If we want better statistical properties,
then we have to give up good
computational properties.
• So which loss function is the best?
[Figure taken from Patrick Breheny’s slides] 32
Gradient Descent
• Have some function 8 w , want w ∗ = argmin 8 w .
#
• Grid search is one of the simplest optimization algorithms.
We compute the cost over all values w in a grid,
and pick the best.
• This is brute-force, but extremely simple.
• But, it has too many “for loops”, resulting in an exponential
computational complexity.
33
Gradient Descent
• Have some function 8 w , want w ∗ = argmin 8 w .
#
34
Gradient Descent
• Have some function 8 w , want w ∗ = argmin 8 w .
#
• Follow the Gradient: A gradient (at a point) is the slope of the
tangent to the function (at the point). It points to the direction
of largest increase of the function.
• The direction of gradient descent is the negative gradient.
Negative gradient
1 ← Original w
direction: − 12 / ) →
35
Gradient Descent
• Have some function 8 w , want w ∗ = argmin 8 w .
#
• Follow the Gradient: A gradient (at a point) is the slope of the
tangent to the function (at the point). It points to the direction
of largest increase of the function.
• Outline:
• Start with some w = (+$ , +% ) (e.g., +$ = 0, +% = 1).
• Keep changing w = (+$ , +% ) to reduce 8 w
until we hopefully end up at a minimum.
36
Gradient Descent
Q: Where start?
Q: Which direction?
Q: How much move?
← Initial state
/ )% , )#
)#
)%
37
Gradient Descent
• Gradient Descent Algorithm
• Repeat until convergence
{
A
+$ ← +$ − @ 8 +$ , +%
A+$
A
+% ← +% − @ 8 +$ , +%
A+%
}
38
Gradient Descent
A
+% ← +% − @ 8 +$ , +%
A+%
+% ← +% − @(BCDEFEGH number)
+%
+% ← +% − @(LHMNFEGH number)
+%
39
Gradient Descent
A
+% ← +% − @ 8 +$ , +%
A+%
• If @ is too small, gradient descent can
be slow.
+%
• If @ is too large, gradient descent
can overshoot the minimum. It may
fail to converge, or even diverge.
+% 40
Gradient Descent
• Limitation of Gradient Descent
A
+% ← +% − @ 8 +$ , +%
A+%
+% ← +% − @(0)
+%
41
Multivariate Linear Regression
• Remind) Single Variable
• Housing Prices 500
400
(Portland, OR) Price 300
(in 1000’s 200
of dollars)
100
0
0 500 1000 1500 2000 2500 3000
Size (feet2)
• Training Set of Housing Prices
Size in feet2 (x) Price ($) in 1000's (y)
2104 460
1416 232
1534 315
852 178
… …
42
Multivariate Linear Regression
• Multiple Variables
Number of Number of Age of home Price
Size (feet2)
bedrooms floors (years) ($1000)
2,104 5 1 45 460
1,416 3 2 40 232
1,534 3 2 30 315
852 2 1 36 178
… … … … …
"! = ["!# , "!0 , … , "!6 ]7 $!
• Input (features) of &34 training example: "!
• Value of features = in &34 training example: "!5
43
Multivariate Linear Regression
• Mapping Function for Multiple Variables
Previously: &# !! = +$ + +% !!
44
Multivariate Linear Regression
• Mapping Function for Multiple Variables
&# x! = +$ + +% !!% + +) !!) + +* !!* + ⋯ + +" !!"
• For convenience of notation, define !!$ = 1
x! = [!!$ , !!% , … , !!" ]+ ∈ ℝ",% , w = [+$ , +% , … , +" ]+ ∈ ℝ",%
&# x! = w + x!
• It is called “Multivariate Linear Regression”
45
Multivariate Linear Regression
• Mapping Function
&# x = w + x
• Parameters w = [+$ , +% , … , +" ]+ ∈ ℝ",%
• Cost function:
(
1
8 w = 6 (&# x! − $! ))
5
!'%
46
Gradient Descent for Multiple Variables
• Single variable: • Multiple variables:
Repeat{ Repeat{
B B
)% ← )% − A / )% , )# )5 ← )5 − A / w
B)% B)5
B $
)# ← )# − A / )% , )# B 1 0
B)# ← )5 − A 4 6/ x! − $!
B)5 (
} $
!"#
2
← )5 − A 4 (6/ x! − $! )"!5
(
!"#
}
47
Logistic Regression
48
What is Classification?
• Similar to regression,
classification relates the input variable ! to the output variable $,
but $ can only take on discrete values.
We say that $ is a categorical variable.
• Examples:
• Email: Spam / Not Spam?
• Online Transactions: Fraudulent (Yes / No)?
• Tumor: Malignant / Benign?
$ ∈ {0,1} 0: “Negative Class” (e.g., benign tumor)
1: “Positive Class” (e.g., malignant tumor)
49
What is Classification?
• Examples of Classification
(Yes) 1
Malignant?
(No) 0
Tumor Size
• Solution? Normalize the output of mapping function
&# x = w + x between 0 and 1, and threshold at 0.5:
• If 6/ x ≥ 0.5, predict $ = 1
• If 6/ x < 0.5, predict $ = 0
50
The Classification Function (Hypothesis)
• Want 0 ≤ &# x ≤ 1
&# x = U(w + x) where U V = 1/(1 + exp(−V))
1 1
→ &# x =
1 + exp(−w + x)
0.5
→ Sigmoid Function / Logistic Function 0
• Predict $ = 1 if &# x ≥ 0.5, w + x ≥ 0
• Predict $ = 0 if &# x < 0.5, w + x < 0
51
The Classification Function (Hypothesis)
• &# x : Estimated probability that $ = 1 on input x
• &# x = P($ = 1|x; w)
“Probability that $ = 1, given x, parameterized by w”
• P $ = 0 x; w + P $ = 1 x; w = 1
• P $ = 0 x; w = 1 − P $ = 1 x; w
• Example: If x = [!$ , !% ]+ = [1, TumorSize]+ , &# x = 0.7
• Tell patient that 70% chance of tumor being malignant
• Tell patient that 30% chance of tumor being non-malignant
52
Decision Boundary
&# x = U w + x = U +$ + +% !% + +) !)
1 "0
3
&# x =
1 + exp(−w + x) 2
1 1
&# x =
1 + exp(−+$ − +% !% − +) !) ) 1 2 3 "#
• Predict $ = 1 if −3 + !% + !) ≥ 0
• Predict $ = 0 if −3 + !% + !) < 0
53
Non-linear Decision Boundary
&# x = U w + x = U(+$ + +% !% + +) !) "0
++* !%) + +- !)) ) 1
-1 1
"#
• Predict $ = 1 if −1 + !%) + !)) ≥0 -1
• Predict $ = 0 if −1 + !%) + !)) <0
54
Logistic Regression
• Training set: { x% , $% , x) , $) , … , x( , $( }
• )-th example: x! = [!!$ , !!% , … , !!" ]+ ∈ ℝ",% , !!$ = 1,
$! ∈ {0,1}
• The mapping function:
1
&# x =
1 + exp(−w + x)
• How to choose the parameter w?
55
Cost Function
• Simple possible cost function: e.g., Mean Square Error (MSE)
(
1
8 w = 6 (&# x! − $! ))
5
!'%
“non-convex” “convex”
/ w / w
w w
56
Cost Function for Logistic Regression
− log &# x! if $! = 1
• 9 &# x! , $! = h
−log 1 − &# x! if $! = 0
If $ = 1 H 6/ x! , $! = 0 if $! = 1, 6/ x! = 1
But as 6/ x! → 0, H 6/ x! , $! → ∞
If 6/ x! = 0 (predict P $ = 1 x; w = 0),
but $! = 1,
we’ll penalize learning algorithm
6/ x by a very large cost.
57
Cost Function for Logistic Regression
− log &# x! if $! = 1
• 9 &# x! , $! = h
−log 1 − &# x! if $! = 0
If $ = 0
6/ x
58
Cost Function for Logistic Regression
(
1
8 w = 6 9 &# x! , $!
5
!'%
− log &# x! if $! = 1
9 &# x! , $! = h
−log 1 − &# x! if $! = 0
Note: $! = 0 or $! = 1 always
9 &# x! , $! = −$! log &# x! − (1 − $! )log 1 − &# x!
59
Cost Function for Logistic Regression
(
1
8 w = 6 9 &# x! , $!
5
!'%(
1
8 w = − 6 $! log &# x! + (1 − $! )log 1 − &# x!
5
!'%
To fit parameters w ∗ = argmin 8 w
#
To make a prediction given a new x:
1
&# x =
1 + exp(−w + x)
60
Gradient Descent for Logistic Regression
(
1
8 w = − 6 $! log &# x! + (1 − $! )log 1 − &# x!
5
!'%
Want w ∗ = argmin 8 w
#
Repeat{
A
+. ← +. − @ 8 w
A+.
(
1
← +. − @ 6 (&# x! − $! )!!.
5
!'%
}
61
Multi-Class Classification: One vs. All
• E-mail Foldering/Tagging: Work, Friends, Family, Hobby
• Medical Diagram: Not ill, Cold, Flu
• Weather: Sunny, Cloudy, Rain, Snow
62
Multi-Class Classification: One vs. All
Binary Classification Multi-Class Classification
"0 "0
"# "#
63
Multi-Class Classification: One vs. All
"0 &$
&0
&$
"# &0
Class 1: &$
Class 2:
Class 3: &0
(9)
6/ x = L($ = M|x; w) (M = 1,2,3)
64
Multi-Class Classification: One vs. All
(0)
• Training a logistic regression classifier &# x for each class m
to predict the probability that $ = m
• On a new input x, to make a prediction, pick the class m that
∗ (0)
maximizes: m = argmax &# x
0
65
Up Next:
• Neural Network and Back-propagation
66
Thank you!
67
