Vector and Matrix Calculus

Vector and Matrix Calculus Note on notation: Functions in this section of the course are sometimes described as mapping general topological spaces X to other topological spaces. Rn is an example of a topological space; any vector space with an inner product is as well. Therefore, all these definitions and theorems apply to functions on the vector spaces we worked with in the previous section. 1 Extrema As in one-dimensional calculus (by which is meant calculus on functions in one variable), vector calculus is concerned with the rate of change of functions. Recall that in one-dimensional calculus, critical points are points at which the rate of change of the function is 0, which are either local/global minima, local/global maxima, or saddle points. Of these, the minima and maxima are labeled extrema. Our primary application of vector calculus will be solving optimization problems. For example, we seek the weights w which minimize the value ||Xw − y||22 ; in other words, the global minimum of the function f (w) = ||Xw − y||22 . To solve this optimization problem, we could attempt to find all the extrema of f (w), and determine which of these is the global minimum. We will later build more sophisticated methods to do this more efficiently; nonetheless, the goal of all of these methods will be to locate extrema. For a function f : X → R, we define a vector x ∈ X to be a local minimum of f if f (x) ≤ f (y) for all y in some open set N ⊆ X such that x ∈ N .1 If N = X and the conditions hold, i.e. ∀y ∈ X f (x) ≤ f (y), then x is a global minimum of f in X . A global/local minimum is strict if the same conditions hold, except f (x) < f (y) (the extrema is unique). The definitions of local/global maximum proceed similarly, although we generally only consider minima in optimization. This is because maximizing a function f is the same as minimizing −f , so all maximization problems can be (and are) rewritten as minimization problems. 2 2.1 Gradients, Jacobians, Hessians Gradients We start by generalizing derivatives to vector calculus. The gradient of a function f : Rd → R is given by  ∂f  ∂x1   ∇f (x) =  ...  ∂f ∂xd Therefore, ∇f (x) ∈ Rd ; in fact, ∇f (x) points in the direction of steepest ascent along f from x, and so −∇f (x) points in the direction of steepest descent. Additionally, ∇f (x) = 0 if x is a critical point. Proofs of these theorems will be covered in Note 9. 1 An open set is loosely a shaded circle on the input space, and an open set containing a particular vector v is known as a ”neighborhood about v”. 1 2.2 Jacobians We can do the same for derivatives in matrix calculus. Our function f : Rn → Rm is now a more general linear map (described by a matrix) and its derivative, known as the Jacobian, is, too, a matrix:  ∂f1 ∂x1  Jf (x) =  ... ∂fm ∂x1 ... .. . ... ∂f1 ∂xn  ..  .  ∂fm ∂xn In the case that m = 1, then Jf = ∇f > . 2.3 Hessians The Hessian generalizes second-order derivatives to vector calculus.2 It is the matrix of second-order partial derivatives:  2  ∂ f ∂2f . . . ∂x1 ∂xd  ∂x1.∂x1 . ..   . . ∇2 f (x) =  . .   . 2 2 f ∂ f . . . ∂x∂d ∂x ∂xd ∂x1 d If the partial derivatives are continuous, the order of differentiation can be interchanged, as in one-dimensional calculus. Therefore, in this case, the Hessian is symmetric. 2.4 Differentiation Rules We introduce the following useful rules for differentiation around vectors and matrices: ∇x (a> x) = a ∇x (A> x) = A and if A is square, ∇x (x> Ax) = (A + A> )x These identities are not valid if the values of a or A depend on x. However, the chain rule still holds. If we have f : Rm → Rk and g : Rn → Rm , then f ◦ g : Rn → Rk and Jf ◦g (X) = Jf (g(x))Jg (x) If k = 1 then ∇(f ◦ g)(x) = Jg (x)> ∇f (g(x)) The proofs follow easily from the chain rule on partial derivatives. 2 The second derivative in matrix calculus must be represented as a tensor, the higher-dimensional generalization of a matrix, and is not covered in this class. 2 Applications: Gradient Descent All of our models so far have been linear regression models, i.e. they find weights w such that the output y can be expressed as a linear combination of the input x. This has been the case even when working with non-linear features, as we augmented the features prior to finding the weights. As we will prove in the next note, linear models have particular nice properties which allow us to find closed-form solutions (i.e. w = (X> X)−1 X> y). However, we are not always able to find closed-form solutions for non-linear models. It would be nice to have a method which could approximate solutions for functions for which no closed-form solutions exist. Furthermore, in some applications, we don’t even know what type of function we are trying to approximate – we instead use a universal function approximator capable of approximating arbitrary functions. Neural networks, mathematical objects loosely based on the brain’s neural structures, are one such universal function approximator which use large quantities of weights as well as non-linear functions to learn arbitrary function. Because no closed-form solution exists to find the correct weights, we instead turn to the gradient descent algorithm, which attempts to find local minima in the objective function of the model. Recall from section 2.1 that the gradient of a function points in the direction of steepest ascent. Therefore, like a ball rolling down a hill, the gradient descent algorithm repeatedly takes steps along the negative of the gradient in an attempt to find nearby local minima. However, note that at critical points, the gradient is 0. Therefore, this algorithm cannot find the global minima of functions, as it will stop taking further steps once it reaches a local minima (or saddle point, although this rarely happens in practice). Nonetheless, its strength is in the fact that it works for any objective function, even when no closed-form solution exists.3 Recall from Note 1 that the objective function of ordinary least squares is L(w) = n X (yi − w> xi )2 = ||y − Xw||22 i=1 and we wish to find w∗ which minimizes L(w). In general, our objective function is n X (yi − f (xi ; w))2 L(w) = i=1 where f is some arbitrary function parameterized by w.4 In the case of linear regression, f (xi ; w) = w> xi . Note that X and y are treated as constants, and so L is only in terms of w. L is often referred to as the loss/cost function, as we seek to minimize loss/cost. The gradient descent algorithm works by taking the gradient of the loss function with respect to the current weights, ∇L(w), and moving the weights in the direction of steepest descent, −∇L. So, the steps of gradient descent are as follows: 1. Initialize w(0) randomly 2. While L(w(t) ) has not converged: (a) Update weights: w(t+1) = w(t) − αt ∇Lw (w(t) ) On each step, we update the weights by moving down the gradient as scaled by some factor αt , often referred to as the learning rate. Like λ in ridge regression, the learning rate is a hyperparameter which is not learned by the algorithm and must be set by the user. The learning rate can be constant or can change with the number of iterations – high learning rates may take steps which are too large and never converge, whereas low learning rates may fail to reach minima because the steps they take are too small. The best method for a particular problem must be determined by validation, in which different methods are compared by their loss on unseen data not used in gradient descent. 3 We will discuss other such methods in Note 9; however, gradient descent is the most widely used, so we’re introducing it a bit ahead of schedule. 4 For example, a cubic polynomial ax3 + bx2 + cx + d is parameterized by the vector [a, b, c, d]. A function f (x) parameterized by a vector w is expressed notationally as f (x; w). 3 The gradient descent algorithm stops when the value of L(w(t) ) converges. If L(w(t) ) has converged, then ∇L(w(t) ) = 0; therefore, gradient descent is an algorithm for finding critical points, as expected. Gradient descent will certainly not converge to a maxima (unless it starts at one), as it lowers the value of L(w(t) ) at each step; additionally, it will almost certainly avoid saddle points unless the gradient around them is very small in all directions, as usually the steps will overshoot saddle points. (The magnitude of the gradient is not necessarily the distance to a critical point; we are only given the direction of steepest descent.) So we expect that gradient descent will mostly return minima – even if it initially overshoots a local minimum, the direction of steepest descent will reverse, and the algorithm will head back in the right direction. However, once gradient descent finds a local minimum, it will likely get stuck; it will not explore further to find potentially better local minima. Therefore, the quality of the solution returned depends on the initial starting point of the algorithm: Source: Towards Data Science Only one of the initializations shown finds the true global minimum, although some are better than others. Nonetheless, gradient descent is very successful at training neural networks, and there are extensions to the algorithm which have better practical performance. However, for a special class of functions, we can show that all local minima are equal to the global minimum. These functions are known as convex functions, and we will discuss them in the next note. 4