Page cover image

#4: Logistic Regression & Gradient Descent

  • 5 min

#4: Logistic Regression & Gradient Descent content

Created
Topics

❓ Why Not Linear Regression

hθ(x)=θTxh_\theta(x)=\theta^Tx
Poor performance w/ classification problems
  • Need to set an arbitrary threshold
  • Outliers significantly reduce power of model
  • Hypothesis' output value can be > 1 or < 0

📈 Logistic Regression Model

Usage: Classification
  • predict the probability that an observation belongs to one of two possible classes
💡
Similar to Linear Regression, but gives probability or True/False

Properties

Classification algorithm: 0≤hθ(x)≤10\leq h_\theta (x)\leq1

Hypothesis Representation

💡
Maps linear regression to {0, 1} by nesting inside a Sigmoid function
hw(x)=g(wTx) Hypothesis mapped to {0,1}z=wTx Linear Regressionσ(z)=11+e−z Sigmoid Function\begin{aligned}&h_{w}(x)=g\left(w^{T} x\right) && \text{ Hypothesis mapped to \{0,1\}} \\&z=w^{T} x && \text{ Linear Regression} \\&\sigma(z)=\frac{1}{1+e^{-z}}&& \text{ Sigmoid Function} \end{aligned}⇒hw(x)=σ(wTx)=11+e−wTx\Rightarrow h_w(x)=\sigma(w^Tx)=\frac{1}{1+e^{-w^Tx}}

Logistic (Sigmoid) Function σ\sigma

σ(z)=11+e−z\sigma(z)=\frac{1}{1+e^{-z}}
notion image

Soft Threshold (Conversion to {0,1}\{0,1\} from signal)

notion image
σ(s)=es1+es\sigma(s)=\frac{e^{s}}{1+e^{s}}Given h(x)=σ(wTxj), Signal  s=∑i=0pwixi=wTx\text{Given}\> h(x)=\sigma\left(w^{T} x^{j}\right) , \> \text{Signal}\>\> s=\sum_{i=0}^{p} w_{i} x_{i}=w^{T} x

Why Sigmoid

  • Smooth
    • Easy to compute derivative / gradient
  • Non linear: can model more complex relations

Interpretation of Hypothesis Output

hθ(x)=h_\theta(x)= estimated % that y=1y=1 on input xx

Target Function

Probability that y=1y = 1 given xx; parametrized by ww
f(x)=P⁡[y=1∣x;w]f(x)=\operatorname{P}[y=1\mid x;w]
  • The data does not give us explicit probabilities
  • Only provides samples generated
  • Pick h(x)h(x)
As a binary classification problem (probability sums to 1):
P⁡[y=0∣x;w]+P⁡[y=1∣x;w]=1⇒{P⁡[y=1∣x;w]=hw(x)P⁡[y=0∣x;w]=1−hw(x)\begin{align*} \operatorname{P}[y=0 \mid x;w]+\operatorname{P}[y=1\mid x;w]=1\\\\ \Rightarrow \begin{cases} &\operatorname{P}[y=1\mid x;w] = h_w(x)\\ &\operatorname{P}[y=0\mid x;w] = 1 - h_w(x)\\ \end{cases} \end{align*}

Decision Boundary

A property of the hypothesis function & parameters hθ(x)h_\theta(x)
  • Predict y=1y=1 if hθ(x)≥0.5h_\theta(x)\geq 0.5
  • Predict y=0y=0 if hθ(x)<0.5h_\theta(x)< 0.5
Logistic Function: Input ≥ 0 ⇒ Output ≥ 0.5
z=0,e0=1⇒g(z)=1/2z→∞,e−∞→0⇒g(z)=1z→−∞,e∞→∞⇒g(z)=0\begin{array}{r} z=0, e^{0}=1 \Rightarrow g(z)=1 / 2 \\ z \rightarrow \infty, e^{-\infty} \rightarrow 0 \Rightarrow g(z)=1 \\ z \rightarrow-\infty, e^{\infty} \rightarrow \infty \Rightarrow g(z)=0 \end{array}
Therefore,
θTx≥0⇒y=1θTx<0⇒y=0\begin{aligned} &\theta^{T} x \geq 0 \Rightarrow y=1 \\ &\theta^{T} x<0 \Rightarrow y=0 \end{aligned}

Non-Linear Decision Boundaries

💡
Use higher-order polynomials to classify data with complex geometric shapes

Example from Intro2ML

notion image
Apply Transformation
notion image
Then we can create a hyper-plane to separate the data for classification

Example from Andrew Ng

notion image
⚠️
Difficulty: need to come up w/ transformation b4 inspecting data

Method to Find Best-Fit Line

Calculates maximum likelihood
  1. Pick a probability scaled by xx
  1. Calculate the % of

Loss Function

% that the predicted value is correct
P(y∣x)=σ(ywTx) P(y \mid x)=\sigma\left(y w^{T} x\right) 
Compute the likelihood of IID Training data D={(x1,y1),(x2,y2),…,(xN,yN)}D=\left\{\left(x^{1}, y^{1}\right),\left(x^{2}, y^{2}\right), \ldots,\left(x^{N}, y^{N}\right)\right\}

Goal: Maximum Likelihood Estimation

P(Y∣X)=∏i=1NP(yi∣xi)=∏i=1Nσ(yiwTxi)P(Y \mid X)=\prod_{i=1}^{N} P\left(y^{i} \mid x^{i}\right)=\prod_{i=1}^{N} \sigma\left(y^{i} w^{T} x^{i}\right)
Adjust parameter ww to maximize likelihood

In Practice

Take −log(∗)/N-log(*)/N of the likelihood to minimize
  • Equivalent since the function is monotonically decreasing
Ein(w)=−1Nln⁡(∏i=1NP(yi∣xi))=1N∑i=1Nln⁡(1P(yi∣xi))=1N∑i=1Nln⁡(1σ(yiwTxi))E_{i n}(w)=-\frac{1}{N} \ln \left(\prod_{i=1}^{N} P\left(y^{i} \mid x^{i}\right)\right)=\frac{1}{N} \sum_{i=1}^{N} \ln \left(\frac{1}{P\left(y^{i} \mid x^{i}\right)}\right)=\frac{1}{N} \sum_{i=1}^{N} \ln \left(\frac{1}{\sigma\left(y^{i} w^{T} x^{i}\right)}\right)

Cross-Entropy Loss

Ein(w)=1N∑i=1Nln⁡(1+e−yiwTxi)Ein(w)=−∑i=1N[yi⋅log⁡σ(wTxi)+(1−yi)⋅log⁡(1−σ(wTxi))]E_{i n}(w)=\frac{1}{N} \sum_{i=1}^{N} \ln \left(1+e^{-y^{i} w^{T} x^{i}}\right)\\ E_{i n}(w)=-\sum_{i=1}^{N}\left[y^{i} \cdot \log \sigma\left(w^{T} x^{i}\right)+\left(1-y^{i}\right) \cdot \log \left(1-\sigma\left(w^{T} x^{i}\right)\right)\right]
This error measure is small when yiwTxiy^{i} w^{T} x^{i} is large and positive
  • pushes ww to classify each xix^i correctly
 

Logistic Regression Algorithm w/ Gradient Descent

notion image

⌛ Iterative Optimization

Minimize the loss function → make the model more useful

📦Batch Gradient Descent

An optimization technique to compute logistic regression & other learning algorithms
💡
Sliding Down Hill: progressively modifies parameter ww in a way that decreases error
  • Computing 2nd derivative is almost impossible in most cases
  • Gradient descent provides a close estimate
    notion image

Procedure

  1. Start with an initial value of parameters ww
  1. Compute the direction at which weight decreases
  1. Update the parameters in that direction
    w(1)←w(0)+ηv^w(1) ← w(0) + ηv̂
    • η=η = learning rate (how big the step we take)

Formula

Ein(w)=1N∑i=1Nln⁡(1+e−yiwTxi)E_{i n}(w)=\frac{1}{N} \sum_{i=1}^{N} \ln \left(1+e^{-y^{i} w^{T} x^{i}}\right)

Insights

  • Take a step in the direction of steepest descent to gain the biggest decrease of E
Using first order Taylor expansion we compute the change in EinE_{i n}
ΔEin=Ein(w(0)+ηv^)−Ein(w(0))=η∇Ein(w(0))Tv^+O(η2)≥−η∣∣∇Ein(w(0))∣∣\begin{aligned} \Delta E_{i n} &=E_{i n}(w(0)+\eta \hat{v})-E_{i n}(w(0)) \\ &=\eta \nabla E_{i n}(w(0))^{T} \hat{v}+O\left(\eta^{2}\right) \\ & \geq-\eta|| \nabla E_{i n}(w(0))|| \end{aligned}
Since v^\hat{v} is a unit vector, this equality holds iff
v^=−∇Ein(w(0))∥∇Ein(w(0))∣∣= Direction of steepest descent\hat{v}=-\frac{\nabla E_{i n}(w(0))}{\| \nabla E_{i n}(w(0))||} = \text{ Direction of steepest descent}

Choosing Step Size η\eta

notion image
💡
Large step size when far away from local minima Small step size when close to the local minima
Simple Heuristic:
⇒ Learning rate algorithm Δw=−η∇Ein(w(0))\Delta w=-\eta \nabla E_{i n}(w(0))
 

🥚 Stochastic Gradient Descent

gt=−1N∑n=1Nynxn1+eynwT(t)xng_{t}=-\frac{1}{N} \sum_{n=1}^{N} \frac{y^{n} x^{n}}{1+e^{y^{n} w^{T}(t) x^{n}}}
💡
Perform gradient descent for each batch, not the entire training set
  1. Randomly pick ONE training sample (xi,yi)(x^i, y^i)
  1. Compute the gradient of loss function w/ this sample∇ei(w)=−yixi1+eyiwTxi \nabla e_{i}(w)=\frac{-y^{i} x^{i}}{1+e^{y^{i} w^{T} x^{i}}} 
  1. Update the weights w(t+1)←w(t)−η∇ei(w)w(t+1) \leftarrow w(t)-\eta \nabla e_{i}(w)

🧺 Mini-Batch Gradient Descent

💡
in between batch and stochastic
  1. Randomly pick MM training samples B=(xi,yi),…,(xi+M,yi+M)B=\left(x^{i}, y^{i}\right), \ldots,\left(x^{i+M}, y^{i+M}\right)
  1. Compute the gradient of the loss associated with this mini-batchgB=−1M∑(xj,yi)∈B−yjxj1+eyjwTxjg_{B}=-\frac{1}{M} \sum_{\left(x^{j}, y^{i}\right) \in B} \frac{-y^{j} x^{j}}{1+e^{y^{j} w^{T} x^{j}}}
  1. Update the weights w(t+1)←w(t)−ηgBw(t+1) \leftarrow w(t)-\eta g_B

Comparing Gradient Descent Variants

notion image
 

🤔 Questions

  1. How gradient descent deals with local maxima / saddle points

Resources

🧬
The Ultimate Guide to Logistic Regression for Machine Learning