Logistic regression is a supervised machine learning model used for classification tasks. It works by learning an hyperplane defined by some coefficients (or weights) θ = [θ₀,…,θ_d] such that it can split the data into two subsets according to their labels. These coefficients θ are composed by a weights vector w = [w₁,…,w_d] plus a bias term b. For simplicity, we will consider a binary classification task but the algorithm can also generalized to deal with multi-labeled data simply by calculating a set of weights for each class.

Logistic regression is a probabilistic machine learning model, that is, its predictions are probability values ranging from 0 to 1. Thus, for a binary classification task we have that for a point x of the data, the probability of its label being y is equal to:

The above function is also as known as sigmoid function:

In our case, we have that z = wx+b represents the dot product between the weights vector times the point x of the data plus a scalar bias term b. By plotting the above formula, we can see that its values range from 0 to 1 excluded.

In order to simplify the notation, we will consider that θ = [b,w₁,…,w_d] is the coefficients vector, but we can also call it weights vector by considering the term b as an additional weight. Consequently, the input features vector will result to be x = [1,x₁,…x_d] with a 1 added in correspondence of the bias term of the coefficients vector θ. Hence, applying this new notation it results that:

Maximum Likelihood Estimation

Maximum likelihood estimation principle (MLE) is a method of estimating the parameters of a probability distribution by maximizing a likelihood function. Given a dataset X (n x d) and its labels y (n x 1), what we are trying to learn is a set of parameters θ such that:

L(θ) is the likelihood of the model given θ and according to the maximum likelihood estimation principle we have to pick the θ parameters that maximizes the likelihood of the data. In other words, we have to find the best coefficients such that the model would predict a probability value very close to 1 when predicting the primary class and a value very close to 0 for the secondary class.

So, the next step consists in estimating the probability P(y|x,θ). So far we know that when y = 1 we have that P(y|x,θ) = σ(xθ), equation (1), conversely, we will have that P(y|x,θ) = 1-σ(xθ), equation (2), when y = 0 since also in this case we would like to maximize the probability value. Finally, the below formula puts the two equations together:

From this equation we can clearly notice that when y = 1 we obtain equation (1) and we get equation (2) when y = 0. Next, we can calculate the likelihood over the whole dataset in the following way:

Next, we add the log to this expression either to avoid underflow when multiplying small numbers and mainly because logs can easily be converted into sums which are easier to be computed and derived respect to the products. Moreover, since log L(θ) is a monotonic function of L(θ), maximizing it is the same as maximizing L(θ) itself.

The resulting formula is also known as binary cross-entropy loss and represents the likelihood for the L(θ) function that we want to maximize. Unfortunately, this function doesn’t present any closed form solution but the good news is that L(θ) is a concave function of θ, thus, we can proceed to calculate its maximum using gradient ascent technique. Usually, we use gradient descent when we want to minimize an objective function and gradient ascent when we want to maximize it.

Training with gradient ascent

It is well known that a partial derivative is the derivative of a function along a single dimension, whereby the other dimensions are treated as constants. The gradient of a function f(θ) when θ is d-dimensional, is given by a vector of partial derivatives for each dimension:

The gradient expresses the direction of the fastest increase of the function f and its rate of increase in that direction. In this way we know how much we have to vary each of the θ parameters in order to maximize the value of L(θ), that is, maximize the total likelihood. Thus, by applying this definition to the logistic regression likelihood function we obtain the rule to update θ at each timestep t:

Where η is the learning rate which is a hyper-parameter that controls to what extent we are going to vary the weights of our model respect to the gradient. Having a low value of η means moving toward the maximum of the function with smaller steps, thus, requiring more iterations to convergence toward the optimal solution and presenting the risk to get stuck into a false local maximum. On the other hand, a high learning rate will converge faster but has the risk of jumping over the optimal solution becoming unstable and to diverge. Hence, a good strategy would be to begin with a high learning rate for the initial iterations in order to speed up the convergence and reducing it over the time when more precision is required to find the optimal solution. This procedure is also known as annealing of the learning rate.

After calculating the gradient of log L(θ) respect to the parameters θ, we obtain the following equation:

The steps needed to derive above equation have been omitted here but can be still checked on this link. Finally, replacing it back in the weights update formula we get that:

Therefore, to adjust the model’s parameters, these iterations are repeated until the change of the likelihood between t_i and t_i+1 doesn’t fall below a fixed threshold.

Gradient ascent is a simple and common method to optimize the weights of a model but, for the case of the logistic regression, a faster convergence can be obtained by using another more efficient method called Iterative Reweighted Least Squares.

Training with IRLS

Iterative Reweighted Least Squares is a method that exploits the Newton method to iteratively update the weights of a logistic regression model. In numerical analysis, the Newton method is an iterative method used to find an approximation of the root f(x) = 0.

Choosing an initial x₀ value, successive iterations will converge toward the root of f(x).

To maximize the likelihood L(θ) we have to find θ such that:

Here we can notice an analogy with the Newton method since what we want to find is still the root of a function L(θ). Thus, in the Newton formula we can replace x_t+1 and x_t with θ_t+1 and θ respectively, f(x_t) replaced with ∇L(θ_t) and f'(x_t) with ∇²L(θ_t) = H which is knows as the Hessian matrix. The Hessian is a square matrix of second-order partial derivatives of a scalar-valued function, therefore, a model having d parameters will result in a (d x 1) gradient vector and (d x d) Hessian matrix.

Finally, substituting the new terms in the Newton method formula we obtain that:

(3)

Previously, we had already calculated ∇log L(θ_t), so we can set the gradient of the new likelihood function as:

(4)

Note that for simplicity we have defined u_i = σ(x_iθ_t) and in the last part of the above equation, X is the matrix representing the input data (n x d), whereby y (n x 1) and u (n x 1) is a vector.

Using (4), we can compute the Hessian matrix which results to be:

(5)

Where R_ii = u_i(1 – u_i) is a (d x d) square matrix. The last step consists in replacing (4) and (5) in the Newton method formula (3) to get the final formula for the IRLS algorithm:

IRLS takes O(n + d³) per iteration, where n is the number of training instances and d is the feature dimension, but it converges in fewer iterations than gradient ascent method.

IRLS with L2 regularization

One of the drawbacks of the logistic regression is that its learning procedure might cause its weights w to become very large as the training goes on. This problem would lead to overfitting since the predicted probabilities y_i=σ(x_iθ_t) would end up being very close to 0 or to 1 most of the times. One way to prevent the weights from growing too much is penalizing them by applying L2 regularization, also known as rigde regularizarion. This result is achieved by adding the L2 norm of the weights ||θ||² to the likelihood function:

(6)

Where ||θ||² is the L2 norm of θ. Next we are going to calculate the new gradient and the new Hessian with L2 regularization applied to the new objective function:

(7)

(8)

Where I is the identity matrix (d x d).Putting (7) and (8) in (3), we get that the formula to update the weights with IRLS algorithm and L2 regularization is:

References

• https://thudm.github.io/Tsinghua-ML-Course/slides/3-Logistic%20Regression-final.pdf
• http://cs.wellesley.edu/~sravana/ml/logisticregression.pdf