Introduction to Machine Learning, AI 305

Introduction to Machine Learning, AI 305

• Logistic Regression is a supervised learning technique for classification.
• Previous week's topics covered linear regression, including linear hypothesis models, cost functions, gradient descent, least mean square (LMS) and normal equations.
• This week's topics include binary classification, logistic regression, cost function, Newton's method and multiclass classification.

Binary Classification

• In classification, the target variable (y) represents a discrete class, such as apartment, studio or house.
• In binary classification, y can take only two values: 0 or 1.
  • Examples include email classification (spam/not spam) and tumor classification (malignant/benign).
• y ∈ {0, 1}
  • 0 represents the negative class.
  • 1 represents the positive class.

Linear Regression for Binary Classification

• Using linear regression for binary classification is problematic as outliers negatively impact predicted results.
• The hypothesis function should appropriately model probability within 0 and 1.
• Logistic function solutions address this.

Logistic Regression

• Logistic regression uses a logistic function or sigmoid function as the hypothesis for binary classification.
• The logistic function is: h_θ(x) = g(θ^Tx) = 1 / (1 + e^-θTx)
• where z = -θ^Tx
• and g(z) = 1 / (1 + e^-z)
• g(z) maps any real number to the interval (0, 1), representing the probability.

Logistic Regression - Derivatives

• The derivative of the logistic function is: g'(z) = g(z) (1 - g(z))

Logistic Regression - Probability

• h_θ(x) represents the probability that the output is 1.
• If h_θ(x) = 0.7, there's a 70% probability the output is 1.
• The probability of 0 is 1 - h_θ(x).

Logistic Regression - Likelihood Function

• The likelihood function, L(θ), is a function of y given x for fixed θ.
• L(θ) = L(θ; X, y) = p(y|X; θ).

Logistic Regression - Likelihood of Parameters

• Assuming independent training examples, the likelihood of parameters θ is:
  • L(θ) = ∏_i=1ⁿ p(y⁽ⁱ⁾|x⁽ⁱ⁾; θ) = ∏_i=1ⁿ (h_θ(x⁽ⁱ⁾))^y(i) (1 - h_θ(x⁽ⁱ⁾))^1-y(i)

Objective Function

• The objective is to choose θ to maximize the likelihood function (L(θ)) for the given data.
• The objective function maximizes the data likelihood as much as possible.

Objective Function - Maximization

• Maximizing L(θ) is equivalent to maximizing the log likelihood l(θ)=log L(θ) .
• Log likelihood functions use simpler derivations.

Gradient Ascent

• To maximize the likelihood, use gradient ascent similar to the linear regression method.
• θ_j:=θ_j+α∇l(θ)_j.
• The positive sign is used because we maximize the function.

Gradient Ascent - Stochastic

• Using gradient ascent with one training example (x, y) produces the stochastic gradient ascent rule.

Gradient Ascent - Vectorized

• A vectorized implementation is θ:=θ+αX^T(y-g(Xθ))

Newton's Method

• A different algorithm for maximizing l(θ)
• Newton's method was initially for finding roots f(θ)=0 where θ ∈ R .
• Using the update rule: θ: = θ –f(θ) / f'(θ)

Newton's Method - Linear Approximation

• Approximates a non-linear function, f, as a linear function tangent to f at current θ.
• Finds the next θ where the tangent line crosses the zero axis

Newton's Method - Example

• Illustrates using the update rule several times to converge towards f(θ) =0

Newton's Method - Maximization

• Maximizing l(θ) : let f(θ) = l(θ), and use the update rule to approach θ values where the first derivative l'(θ) = 0.

Newton's Method - Quadratic Approximation

• Approximates l(θ) by Taylor expansion around current θ value., then maximize.
• Finding the θ where gradients equal 0 completes the update

Newton's Method - Optimal Learning Rate

• Newton's method can be considered a method for finding the learning rate of gradient descent, a parameter of gradient descent.

Newton-Raphson Method

• Generalization of Newton's method to higher dimensions is Newton-Raphson method.

• Update θ by θ: = θ –H^-1∇l(θ)

  • ∇l(θ): vector of partial derivatives of l(θ) with respect to θ_j’s
  • H:d-by-d Hessian matrix
    • Hessian entries are given by H_ij = ∂²l(θ)/ ∂θ_iθ_j

Newton's Method Advantages

• Faster convergence than batch gradient descent.
• Fewer iterations to reach minimum

Newton's Method Disadvantages

• Requires a more extensive computation (finding and inverting a d-by-d Hessian).
• Still quite fast if dimensions are not too high.

Fisher Scoring Method

• When applying Newton's method to the logistic regression likelihood, resulting approach is Fisher scoring.