Mathematics for Machine Learning - GitHub Pages

1 Mathematics for Machine LearningGarrett ThomasDepartment of Electrical engineering and Computer SciencesUniversity of California, BerkeleyJanuary 11, 20181 AboutMachine Learning uses tools from a variety of mathematical fields. This document is an attempt toprovide a summary of the mathematical background needed for an introductory class in machinelearning, which at UC Berkeley is known as CS 189 assumption is that the reader is already familiar with the basic concepts of multivariable calculusand linear algebra (at the level of UCB Math 53/54). We emphasize that this document isnotareplacement for the prerequisite classes.

2 Most subjects presented here are covered rather minimally;we intend to give an overview and point the interested reader to more comprehensive treatments forfurther that this document concerns math background for Machine Learning , not Machine learningitself. We will not discuss specific Machine Learning models or algorithms except possibly in passingto highlight the relevance of a mathematical versions of this document did not include proofs. We have begun adding in proofs wherethey are reasonably short and aid in understanding. These proofs are not necessary background forCS 189 but can be used to deepen the reader s are free to distribute this document as you wish.

3 The latest version can be found Please report any mistakes About12 Notation53 Linear Vector spaces .. space .. Linear maps .. matrix of a linear map .. , range .. Metric spaces .. Normed spaces .. Inner product spaces .. Theorem .. inequality .. complements and projections .. Eigenthings .. Trace .. Determinant .. Orthogonal matrices .. Symmetric matrices .. Rayleigh quotients .. Positive (semi-)definite matrices .. The geometry of positive definite quadratic forms .. Singular value decomposition.

4 Fundamental Theorem of Linear Algebra .. Operator and matrix norms .. Low-rank approximation .. Pseudoinverses .. Some useful matrix identities .. Matrix-vector product as linear combination of matrix columns .. Sum of outer products as matrix-matrix product .. Quadratic forms ..264 Calculus and Extrema .. Gradients .. The Jacobian .. The Hessian .. Matrix calculus .. chain rule .. Taylor s theorem .. Conditions for local minima .. Convexity .. sets .. of convex functions .. of convexity .. that a function is convex.

5 365 Basics .. probability .. rule .. rule .. Random variables .. cumulative distribution function .. random variables .. random variables .. kinds of random variables .. Joint distributions .. of random variables .. distributions .. Great Expectations .. of expected value .. Variance .. of variance .. deviation .. Covariance .. Random vectors .. Estimation of Parameters .. likelihood estimation .. a posteriori estimation .. The Gaussian distribution .. geometry of multivariate Gaussians ..45 References4742 NotationNotationMeaningRset of real numbersRnset (vector space) ofn-tuples of real numbers, endowed with the usual inner productRm nset (vector space) ofm-by-nmatrices ijKronecker delta, ij= 1 ifi=j, 0 otherwise f(x)gradient of the functionfatx 2f(x)Hessian of the functionfatxA>transpose of the matrixA sample spaceP(A)probability of eventAp(X)distribution of random variableXp(x)probability density/mass function evaluated atxAccomplement of eventAA Bunion ofAandB, with the extra requirement thatA B= E[X]expected value of random variableXVar(X)

6 Variance of random variableXCov(X,Y)covariance of random variablesXandYOther notes: Vectors and matrices are in bold ( ,A). This is true for vectors inRnas well as forvectors in general vector spaces. We generally use Greek letters for scalars and capital Romanletters for matrices and random variables. To stay focused at an appropriate level of abstraction, we restrict ourselves to real values. Inmany places in this document, it is entirely possible to generalize to the complex case, but wewill simply state the version that applies to the reals. We assume that vectors are column vectors, that a vector inRncan be interpreted as ann-by-1 matrix.

7 As such, taking the transpose of a vector is well-defined (and produces a rowvector, which is a 1-by-nmatrix).53 Linear AlgebraIn this section we present important classes of spaces in which our data will live and our operationswill take place: vector spaces, metric spaces, normed spaces, and inner product spaces. Generallyspeaking, these are defined in such a way as to capture one or more important properties of Euclideanspace but in a more general Vector spacesVector spacesare the basic setting in which linear algebra happens. A vector spaceVis a set (theelements of which are calledvectors) on which two operations are defined: vectors can be addedtogether, and vectors can be multiplied by real satisfy(i) There exists an additive identity (written0) inVsuch thatx+0=xfor allx V(ii) For eachx V, there exists an additive inverse (written x) such thatx+ ( x) =0(iii) There exists a multiplicative identity (written 1) inRsuch that 1x=xfor allx V(iv) Commutativity:x+y=y+xfor allx,y V(v) Associativity: (x+y) +z=x+ (y+z) and ( x) = ( )xfor allx,y,z Vand , R(vi) Distributivity.

8 (x+y) = x+ yand ( + )x= x+ xfor allx,y Vand , RA set of vectorsv1,..,vn Vis said to belinearly independentif 1v1+ + nvn=0implies 1= = n= ,..,vn Vis the set of all vectors that can be expressed of a linear combinationof them:span{v1,..,vn}={v V: 1,.., nsuch that 1v1+ + nvn=v}If a set of vectors is linearly independent and its span is the whole ofV, those vectors are said tobe abasisforV. In fact, every linearly independent set of vectors forms a basis for its a vector space is spanned by a finite number of vectors, it is said to it isinfinite-dimensional.

9 The number of vectors in a basis for a finite-dimensionalvector spaceVis called thedimensionofVand denoted Euclidean spaceThe quintessential vector space isEuclidean space, which we denoteRn. The vectors in this spaceconsist ofn-tuples of real numbers:x= (x1,x2,..,xn)For our purposes, it will be useful to think of them asn 1 matrices, orcolumn vectors:x= 1 More generally, vector spaces can be defined over anyfieldF. We takeF=Rin this document to avoid anunnecessary diversion into abstract and scalar multiplication are defined component-wise on vectors inRn:x+y= x1+ +yn , x= xn Euclidean space is used to mathematically represent physical space, with notions such as distance,length, and angles.

10 Although it becomes hard to visualize forn >3, these concepts generalizemathematically in obvious ways. Even when you re working in more general settings thanRn, it isoften useful to visualize vector addition and scalar multiplication in terms of 2D vectors in the planeor 3D vectors in SubspacesVector spaces can contain other vector spaces. IfVis a vector space, thenS Vis said to be asubspaceofVif(i)0 S(ii)Sis closed under addition:x,y Simpliesx+y S(iii)Sis closed under scalar multiplication:x S, Rimplies x SNote thatVis always a subspace ofV, as is the trivial vector space which contains a concrete example, a line passing through the origin is a subspace of Euclidean subspaces ofV, then their sum is defined asU+W={u+w|u U,w W}It is straightforward to verify that this set is also a subspace ofV.