Newton Method Optimization in Logistic Regression

Thomas the Tank Engine

Overview of Logistic Regression:

Logistic regression is a part of supervised learning method in which models are trained on labeled datasets to generate desired outputs. Logistic Regression is very often used as a classifier. But in reality, it is implemented as a regression problem.

There are three types of logistic regression:

1. Binomial Logistic Regression:

• Purpose: Used when the dependent variable has two possible outcomes or classes (binary classification).
• Example: Classifying emails as “spam” or “not spam,” predicting whether a patient has a disease or not (yes/no).

2. Multinomial Logistic Regression:

• Purpose: Used when the dependent variable has more than two possible unordered categories (multiclass classification).
• Example: Classifying a flower as “setosa,” “versicolor,” or “virginica,” predicting a person’s favorite color from a set of options.

3. Ordinal Logistic Regression:

• Purpose: Used when the dependent variable has more than two categories, but these categories have an inherent order (ordinal classification).
• Example: Rating a product as “poor,” “fair,” or “excellent,” or classifying students’ grades as “A,” “B,” “C,” etc.

Understanding Logistic regression:

Now, linear regression estimates the linear relationship between variables using the linear combination of its inputs. Whereas logistic regression uses an Inverse Logit Function or Logistic Function.

Inverse Logit Function

Here x is the linear combination of inputs along with the weights (parameters). Hence we can rewrite the equation as :

Logistic Function with input & parameters

This function simply maps the input to a value between [0,1] , i.e probability of the input variable belonging to a particular class. The function traces an s-shaped curve which is smoother and better equipped to estimate the relationship between input variables.

It restricts the output between 0 to 1. To use this algorithm as a classifier, we can set a threshold of 0.5 and simply classify inputs into two or more classes.

Example of a Logistic Regression Curve

If we stick to our regression problem then we need to have quantitative outputs instead of probabilities. To obtain this we pass the probability p into a logit function which will undo the effect of the inverse logit function and give us a output ranging between [−∞,∞]

Inverse Logit Function → p ∈[0,1] → Logit Function → [−∞,∞]

Logit Function

Here p is the probability that we obtained after applying logistic function. Unlike linear regression which uses Mean-Squared-Error as the loss function , logistic regression uses log-loss or binary cross entropy. We need an algorithm which minimizes the loss function (cost function) and updates the parameters accordingly.

Log Loss (Loss Function)

Gradient Descent vs Newton’s Method:

Gradient descent is a first order derivative function . It uses a slope to determine the direction of descent, but it has several pitfalls. Some of these are overcome by the Newton Method.

The Newton method is a second order optimization technique. It fits a parabola to the curvature of the objective function (loss function) and minimizes the quadratic function of the parabola. This helps in faster convergence and precise updates compared to gradient descent.

A gradient descent step (left) and a Newton step (right) on the same function.

A comparison of gradient descent (green) and Newton’s method (red) for minimizing a function is shown below.

Convergence path of both algorithms

Newton’s method uses curvature information (i.e. the second derivative) to take a more direct route. The gradient step moves the point downwards along the linear approximation of the function. The Newton step moves the point to the minimum of the parabola, which is used to approximate the function.

The newton method formula for parameter updates is similar to that of gradient descent only with a small change. We use inverse of hessian matrix to compute the parameter updates.

Parameter update formula

Hessian Matrix and Its Inversion:

The Hessian matrix H is a square matrix of second-order partial derivatives that represents the curvature of the objective function. It provides valuable information about how the function behaves around a given point.

Example of an Hessian Matrix

Now you might think, why use an inverse hessian instead of a normal hessian?

Inverting the Hessian: By multiplying the gradient by inverse of H, the step size in each direction is scaled in proportion to the curvature of the function. This effectively adjusts the step size along each coordinate axis based on how steep or flat the function is in that direction.

• When the Hessian is large (indicating steep curvature), the step size is small because the inverse of a large value is small.
• When the Hessian is small (indicating flat curvature), the step size is larger.

If you are still not convinced or if you believe I’m brewing random mathematical equations out of the blue , hang in there ! We are going derive the parameter update rule together!

If you go down the memory lane to your boring calculus lectures in college you might recall something known as **Taylor series**.

Newton’s method attempts to solve the minimization problem by constructing a sequence from an initial guess (starting point) that converges towards a minima of the function by using second-order Taylor approximations. The second-order Taylor expansion is given by:

We want the minima of the quadratic approximation , hence we will solve the derivative of this function by equating it to zero.

Now you can compare the weight update formula and the final equation we derived . We can easily understand how we got the inverse hessian matrix there. All is well and good , but wait there is a catch!

• The Hessian matrix may not be invertible if it is singular.
• Calculating the inverse of the Hessian is computationally expensive and is typically an O(n³) operation.
• Storing and manipulating the Hessian matrix requires significant memory and computational resources.
• The Hessian matrix may not always be positive definite, which means the quadratic function may not be convex (parabola-like).
• In some cases, the optimization algorithm might still get stuck in local minima.

To overcome the problem of calculating the hessian inverse we try to approximate the hessian inverse matrix instead of computing it. Quasi-Newton methods like LBFGS, DFS are used.

Scikit-learn implementation:

In Scikit Learn the function of logistic regression is implemented as follows :

class sklearn.linear_model.LogisticRegression(penalty='l2', *, 
dual=False, tol=0.0001, C=1.0, fit_intercept=True, intercept_scaling=1, 
class_weight=None, random_state=None, 
solver='lbfgs', max_iter=100, multi_class='deprecated', 
verbose=0, warm_start=False, n_jobs=None,l1_ratio=None)

Here ‘solver’ refers to the algorithm used for optimization. LBFGS (Limited Broyden Fletcher Goldfarb Shanno algorithm) is the default solver which is implemented. The hyperparameter ‘tol’ is the stopping criteria or convergence threshold.

Due to the problems discussed above pure newton methods are not used as solvers. Instead ‘newton-cg’ & ‘newton-cholesky’ are the two variants of newton’s method implemented in Scikit Learn. Also remember L1 and L2 regularization parameters are included in some of these solvers.

Solvers provided by Scikit Learn

Conclusion:

Newton’s method offers faster convergence compared to gradient descent by incorporating second-order information. While the Hessian matrix poses computational challenges, methods like newton-cg efficiently approximate it for large datasets. Depending on the problem’s complexity and size, choosing the right solver can significantly improve optimization performance.

Sources:

[embed]1.1. Linear Models The following are a set of methods intended for regression in which the target value is expected to be a linear…scikit-learn.org

[embed]Optimization in Neural Networks and Newton's Method - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and…www.geeksforgeeks.org

[embed]Logistic regression - Wikipedia In statistics, the logistic model (or logit model) is a statistical model that models the log-odds of an event as a…en.wikipedia.org

[embed]Newton's method in optimization - Wikipedia In calculus, Newton's method (also called Newton-Raphson) is an iterative method for finding the roots of a…en.wikipedia.org

[embed]Lecture 7: Gradient Descent (and Beyond) We want to minimize a convex, continuous and differentiable loss function $\ell(w)$. In this section we discuss two of…www.cs.cornell.edu

If you liked the article leave a like & comment :)