The Neural Network its Techniques and Applications

The Neural Network, its Techniques and Applications April 12, 2016 1 Contents 1 Introduction 3 2 Linear Algebra Terminology and Background 2.1 Linear Independence and Spanning . . . . . . . 2.2 Basis . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Example: Too Many Columns . . . . . . . . . . 2.4 Example: Too Many Rows . . . . . . . . . . . . 2.5 Reconstructions . . . . . . . . . . . . . . . . . . 2.6 Change of Basis Theorem . . . . . . . . . . . . 2.7 Example: Changing a Basis . . . . . . . . . . . . . . . . . . 3 3 4 4 5 5 6 7 3 Singular Value Decomposition 3.1 The Symmetric Matrix . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Singular Value Decomposition . . . . . . . . . . . . . . . . . . . . 3.3 Example: SVD in Action . . . . . . . . . . . . . . . . . . . . . . 8 9 10 12 4 Applications of the SVD 4.1 The Psuedoinverse . . . . . . . . 4.2 The Covariance Matrix . . . . . . 4.3 The Best Basis . . . . . . . . . . 4.4 Example: Finding the Best Basis 4.5 SV-Spectral Decomposition . . . 4.6 Practical Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 13 14 15 17 19 20 5 Neural Networks 5.1 Example: Cancer . . . . . . . 5.2 Neural Network Theory . . . 5.3 Build up to Gradient Descent 5.4 Gradient Descent . . . . . . . 5.5 Example: Cancer Revisited . 5.6 Example: Function Fitting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 24 25 28 29 31 34 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Conclusion 36 Alphabetical Index 37 2 1 Introduction A neural network is a powerful mathematical model combining linear algebra, biology and statistics to solve a problem in a unique way. The network takes a given amount of inputs and then calculates a specified number of outputs aimed at targeting the actual result. Problems such as pattern recognition, linear classification, data fitting and more can all be conquered with a neural network. This paper will aim to answer these questions: what is a neural network, what is its mathematical background, and how can we use a neural network in application? My paper will be split roughly into two parts. The first entails a host of linear algebra including sections on bases, symmetric matrices, the singular value decomposition, the covariance matrix and the psuedoinverse. All these concepts tie together to form an amazingly simple way to solve a pertinent problem. The second part will consist of extensive talk on neural networks, an often more powerful way to solve the same problem. In the end we will see the benefits and drawbacks of both methods and realize that it is important to know everything in this paper so as to tackle any problem thrown at us. The paper will start with many key concepts from linear algebra. A typical linear algebra student will have seen some, but not all, of these ideas. 2 Linear Algebra Terminology and Background Although I cannot go over all of linear algebra in this paper, I would like to go over a few concepts that are imperative to understand. Linear algebra is essentially the study of matrices. Throughout this paper I will refer to a matrix, A, of size m × n, which is interpreted as having m rows and n columns.   a1,1 a1,2 . . . a1,n  a2,1 a2,2 . . . a2,n     .. .. ..  ..  . . . .  am,1 am,2 . . . am,n We would say this matrix maps a vector x in IRn to a vector Ax in IRm . A column vector, normally just called a vector, is simply a matrix of size m × 1. We would normally say an m × n matrix is comprised of n different vectors, which we would denote {v1 , v2 , . . . , vn }. Two notable concepts related to the columns of a matrix are linear independence and spanning. 2.1 Linear Independence and Spanning If a column of a matrix can be written as the sum of scalar multiples of other columns then we say the columns of this matrix are linearly dependent. Formally, a set of columns are said to be linearly dependent if the equation, 0 = c1 v1 + c2 v2 + . . . + cn vn , 3 has a solution where not all constants, ci , are equal to 0. Note that if we put one of the terms, ci vi , on the left side and divide by −ci , assuming ci 6= 0, we are saying that we can write the vector vi as the sum of constant multiples of the other vectors. If all ci ’s are equal to 0, we cannot divide by any ci and thus cannot write one vector as the sum of constant multiples of the others. When this happens, we call the set of vectors linearly independent and formally say the equation 0 = c1 v1 + c2 v2 + . . . + cn vn , has only the solution where all ci ’s are equal to zero [1]. Linear independence is a useful property columns of a matrix can have. Essentially it is the most efficient matrix possible, as each vector contributes something new. Another property is the span of the columns of a matrix. The span of a set of vectors {v1 , v2 , . . . , vn } is the set of all linear combinations of the vectors, or the collection of vectors of the form: c1 v1 + c2 v2 + . . . + cn vn [1]. While linear independence might be an indicator of efficiency, the span tells us how much total data our vectors can represent. An ideal matrix would have columns with a large span and linear independence, both explaining a lot of data and doing so without any unnecessary vectors. This brings us to the idea of a basis. 2.2 Basis A basis of a subspace H of IRm is a linearly independent set of vectors in H that spans H [1]. Essentially this means that any vector in H can be written as a linear combination of the vectors from the basis and that it is the smallest such set. Let’s look at a few examples to understand the concepts of linear independence, spanning and a basis. 2.3 Example: Too Many Columns  1 . We could also think of this matrix as a collection of three 1       0 1 1 column vectors a1 = , a2 = , and a3 = . 1 0 1 2 Clearly we can write any point in IR using the first two vectors as such:   x = c1 a1 + c2 a2 . y Let A =  0 1 1 0 Therefore this matrix spans IR2 . However notice we can write a3 = a1 + a2 . The third vector can be written as a combination of the first two and so we have linear dependence. This matrix, while spanning IR2 is not a basis of IR2 . If we 4 took only the first two columns where a1 and a2 are in fact linearly independent we would have a basis for IR2 . 2.4 Example: Too Many Rows   0 1 Here’s another matrix, B = 1 0. Notice it is the transpose of A, denoted 1 1 AT , meaning the rows and columns are swapped. To test linear independence,we could try writing one vector as a scalar multiple of the other. But notice the presence of 0 in one of the columns and the absence of 0 in the other column for the same row. Thus there is no way to do this, so these columns are linearly independent. What this matrix lacks is a spanning of IR3 . Last time we wanted a span of IR2 because there were 2 rows. Now since there are three rows we want a span of IR3 . However try writing a point like (2, 3, 4) as a combination of the two vectors. The 2 in the first row and the fact that v1 has a 0 in the first row would require v2 ’s constant to be 2. Similarly the second row indicates v1 ’s constant is 3. With those already set, we are unable to get 4 in the last row (but we could get 5). We found a point in IR3 that couldn’t be expressed as a linear combination of our vectors, therefore B does not span IR3 and again there is no basis for IR3 . However we do have a basis for a subspace similar to IR2 . We cannot write a point from IR2 given as (x, y, 0) as a collection of these vectors. However there is a plane in IR3 that contains points of the form (x, y, x + y) and these two vectors would suffice to explain any point on this plane. This space is in fact isomorphic to IR2 , a useful fact, but for the non-mathematical readers we will just say that this space exhibits properties very similar but not identical to IR2 . In these two examples something was slightly off. In the first we had an additional vector that prevented us from a basis. In the second we could not form a basis for all of IR3 . An astute mind might be able to guess that the reasons for these problems was because we had too many columns in the first example and too many rows in the second. This observation led to part of the invertible matrix theorem that says: if the columns of a square matrix (a matrix with the same number of rows and columns, n) are linearly independent and span IRn then those columns form a basis for IRn . This is not directly tied to my project, but it is a nice theorem to know regardless. What is pertinent to this project is the takeaway that square matrices are nicer to work with than their non square counterparts. When a matrix is not square we usually have to sacrifice something, either linear independence as in the first example or the ability to span IRm as in the second example. And because matrices in the real world are often not square, these sacrifices are often a necessity. 2.5 Reconstructions When we have a basis of a space, there are specific vectors that determine the entire space, call these {v1 , v2 , . . . , vn }. These are known as the basis vectors 5 for a space. If we want to write any point x in our space as a combination of these vectors, we would use a set of coordinates, {c1 , c2 , . . . , cn }, and write: x = c1 v1 + c2 v2 + . . . + cn vn Whether you know it or not, you have seen this before. Think about IR3 . Any point can be expressed as a linear combination of the three basis vectors,  T  T  T 1 0 0 , 0 1 0 , and 0 0 1 . Similarly the basis vectors for IR2  T  T are 1 0 and 0 1 . However often we are able to write a point typically found in one coordinate system using a different coordinate system with different basis vectors. The point (2, 3, 5) could be written as such in IR3 , or could be written using coordinate system defined by the basis vectors in the previous   the   0 1 example, 1, 0, as 2v1 +3v2 . The coordinates using these new basis vectors 1 1 would now be (2, 3). What is the point of this? Notice we can now express a point in IR3 using only 2 coordinates instead of 3. That might not seem like a big deal, but as our matrices get bigger the opportunity to express the same point using less values will be crucial. The down side? We can only explain a select few points in IR3 ; (2, 3, 4) for instance will never be able to be fully explained with this coordinate system. This is a fundamental point in my project: we want to explain as much data as possible but we don’t want to use a ridiculously sized coordinate system to do so. Often we will ‘go down’ in coordinate systems to express the data using less points, losing a little of what we can explain in the process. This is wrapped up nicely using the Change of Basis Theorem. 2.6 Change of Basis Theorem First we need a few more definitions. Look at the basis vectors for IR2 that we used previously. These vectors have two special properties. The first is that each vector is a unit, or has length 1. The length, or norm, of a vector is given using the distance formula, the square root of sum of squares of each term. When a vector’s length is 1, it is a unit vector like the basis vectors in IR2 , IR3 and beyond. Luckily any vector can be made into a unit vector by dividing each term by the vector’s length. The basis vectors for IR2 are also orthogonal, that is perpendicular, which happens when the dot product of the two is equal to 0. The dot product is just the sum of the product of each term in a vector with its corresponding term in the other vector. Putting these two concepts together, a set of vectors form an orthonormal set if each vector is a unit vector and is orthogonal to every other vector in the set. The basis vectors for IR2 would then be orthonormal basis vectors. This leads us to the Change of Basis Theorem. This theorem is hugely important to this project. Essentially it allows, given certain circumstances, a vector normally in one basis to be written in another, often using fewer points. 6 After the theorem we will see an example that demonstrates the benefits of the Change of Basis Theorem. Change of Basis Theorem. Let U be an m × n matrix with m ≥ n that has n orthonormal basis vectors for H, a subspace of IRm . Then for x ∈ H, the low dimensional representation of x is the coordinate vector c ∈ IRn where c = UT x The reconstruction of x given the coordinates is x = Uc Another way we could write the latter formula is x = U U T x. It might not seem useful to write x as a function of itself, but the matrix U U T projects x into the column space of U if it does not already exist there. The column space of a matrix is simply the set of all linear combinations of its columns [1]. While it might not be clear what this means, a couple examples will hopefully illuminate the use of this formula and in particular the matrix U U T . 2.7 Example: Changing a Basis    √1  0 3 2 Let x1 = 2 and U =  0 1 √1 3 0 2 Let’s make sure this fulfills the requirements of the Change of Basis Theorem. U is a 3 × 2 matrix, so m = 3 and n = 2 and indeed m ≥ n. We could separate    √1  0 2 U into vectors, u1 =  0  and u2 = 1. The first vector in U has length √1 0 2 q d = ( √12 )2 + ( √12 )2 = 1 and the second clearly does too, so they are both unit vectors. Their dot product is u1 · u2 = ( √12 )(0) + (0)(1) + ( √12 )(0) = 0, so they are orthogonal. Because of this and the fact that they are basis vectors for a subspace H of IR3 , then the columns of U are n = 2 orthonormal basis vectors for H. The vector x1 is also in this subspace, although that may not be obvious yet. With this out of the way, we can safely use the Change of Basis Theorem to find a low dimensional representation of x1 in the coordinate system given by the columns of U . To find the coordinates of x1 in a space isomorphic to IR2 , we just need to compute U T x1 .    1 h i 1  3 √ √ 0 2 2 2 = √6 2 c = U T x1 = 2 0 1 0 3 Thus the coordinates of x1 in the basis given by u1 and u2 are ( √62 , 2). We can write x1 = √62 u1 + 2u2 . As mentioned previously, the reason for finding a 7 lower dimensional representation such as this is to express x1 using less points, which we did. To confirm that this is the same x1 we had before, we can find the reconstruction of x1 in our original basis (the basis vectors of IR3 ) by computing U c:  √1 2 x1 = U c =  0 √1 2  0 h 1 √62 0   3 i 2 = 2 3 The reconstruction of x1 is the same as the x1 we started with, as expected. This example was meant to show how a vector can be expressed as the combination of basis vectors and how, in this case, no data was lost switching between IR3 and a subspace of IR3 isomorphic to IR2 [2]. But remember that the downside is that we lose some data when we go down in the size of our basis. What does that mean?  T Well take a different point, say x2 = 1 2 3 . Using the same method i h we calculate c = √42 2 . However when we go back to reconstruct x2 , we  T get x2 = 2 2 2 . That’s not right! When we went to a lower dimensional basis we lost some of the data. This is because x2 was not in the subspace H, spanned by the columns of U , a prerequisite for the Change of Basis Theorem. When this happens, we look back to the matrix U U T and the column space of U . Notice u1 has the first and third elements the same, whereas u2 has 0’s in those places. That means no matter what constant we put in front of u1 , the set of linear combinations of u1 and u2 , c1 u1 + c2 u2 (by definition the column space of U ), will as well have the first and third elements the same. The only points that can be perfectly reconstructed are the ones in the column space of U , like x1 , which have the first and third elements the same. All other points will be projected onto this space losing a little bit of data along the way. Notice that x2 started out with distinct first and third elements but ended up with identical elements in those spots during the reconstruction. As said before, this is because multiplying by the matrix U U T projects a vector so that it is in the column space of U . Sometimes this is a necessary sacrifice to make. Usually if we have a large set of data we find it easier to work with in a lower dimensional basis. Often we will choose the size of the basis that we want to work with, perhaps saying ‘I would like my data to be represented using k coordinates’. Then the next question is how do we find the best lower dimensional basis, that is the basis that loses the least amount of data, in a space isomorphic to IRk . Well, that is what much of this paper is about after all. 3 Singular Value Decomposition The path to the best basis is a long and arduous one. It starts with more linear algebra, except this time we will be exploring concepts that the typical linear algebra student has not seen yet. Singular value decomposition is at the 8 forefront, but as always there are terms and concepts that need to be understood before we can talk about the SVD. 3.1 The Symmetric Matrix Recall that a square matrix has an equal number of rows and columns. When a square matrix is invertible, it has several nice properties given by the Invertible Matrix Theorem. A special kind of square matrix is a symmetric matrix , a square matrix, A, such that A = AT . Symmetric matrices are invertible square matrices and so have all the properties from the Invertible Matrix Theorem as well as many more. These are given by the very handy Spectral Theorem, which will appear shortly. First there are a few definitions to go over. Eigenvalues and eigenvectors are important terms. An eigenvalue, λ, is a constant value with a corresponding eigenvector, v, such that Av = λv for some matrix A [2]. Notice that for an eigenvector of size n × 1, the matrix A must necessarily be square of size n × n. The eigenspace would be the span of the eigenvectors. We also say that a matrix is diagonalizable if it can be written as A = P DP −1 , where P is a square matrix composed of the eigenvectors of A and D is a diagonal matrix with the corresponding eigenvalues on the main diagonal. Diagonal implies that there are 0’s in all other spots other than the main diagonal. A matrix is orthogonally diagonalizable if P −1 = P T . We are now ready for the Spectral Theorem. This theorem provides many useful properties that any symmetric matrix will have. The Spectral Theorem. An n × n symmetric matrix A has the following properties: a) A has n real eigenvalues, counting multiplicities. b) The dimension of the eigenspace for each eigenvalue λ equals the multiplicity of λ as a root of the characteristic equation. c) The eigenspaces are mutually orthogonal, in the sense that eigenvectors corresponding to different eigenvalues are orthogonal. d) A is orthogonally diagonalizable [1]. An n × n invertible matrix need not have n real eigenvalues, so part a) is useful to know. Part c) gives us that the eigenvectors of a symmetric matrix are orthogonal with each other, therefore if we also make them unit vectors we could have an orthonormal basis, a prerequisite for the Change of Basis Theorem. Part d), is also quite nice, as we can now write any symmetric matrix A as P DP T as in the definition of an orthogonally diagonalizable matrix. The Spectral Theorem also leads to a nice property known as spectral decomposition. From part d) we know any symmetric matrix, A, can be written as P DP T . Since we know there are n real eigenvalues and corresponding eigenvectors from part a), we let the eigenvectors of A be {u1 , u2 , . . . , un } and the eigenvalues of A be {λ1 , λ2 , . . . , λn }. Then: 9 A = U ΛU T  = u1 ...  λ1  un  0 0 .. .  T u1   ..   . . λn uTn Noting that the front product is the same as multiplying each eigenvector in P by its corresponding eigenvalue we get:  T u    .1  = λ1 u1 . . . λn un  ..  . uTn Then from a theorem known as the column-row expansion theorem we can write A as follows: A = λ1 u1 uT1 + λ2 u2 uT2 + . . . + λn un uTn . This is called the spectral decomposition of a matrix A [1]. It can often be useful to write out a matrix using only its eigenvalues and eigenvectors. This is only possible for a symmetric matrix, as a matrix is symmetric if it is orthogonally diagonalizable (the converse of part d, resulting in double implication). The Spectral Theorem and spectral decomposition are excellent properties for symmetric matrices, but rarely is anything in the real world so nicely laid out for us. Often times the matrices we use are not even square, much less symmetric. What we need is to generalize the concepts of eigenvalues, eigenvectors, diagonalization and spectral decomposition to matrices of any size. Enter singular value decomposition . . . 3.2 Singular Value Decomposition Singular value decomposition is a process similar to diagonalizability that can be used on any matrix, regardless of its size. Start with an m × n matrix, A, where m 6= n. Note that AT A is square and size n × n. Furthermore it is symmetric since (AT A)T = AT AT T = AT A. Similarly AAT is symmetric and size m × m since (AAT )T = AT T AT = AAT . The matrix AT A is then an n × n square matrix with eigenvalues {λ1 , ...λn } and eigenvectors {v1 , ...vn } guaranteed by the Spectral Theorem and AAT has eigenvalues {ζ1 , ...ζm } and eigenvectors {u1 , ...um }. Also because of the Spectral Theorem, both these matrices can be diagonalized, so AT A = V ΛV T and AAT = U ZU T . First let us note that AT Avi = λi vi , since vi and λi are an eigenvector and eigenvalue respectively for AT A. Front multiplying by A leaves (AAT )Avi = λi Avi . Thus Avi is an eigenvector for AAT with the same nonzero eigenvalues as AT A, λi . We called those eigenvectors ui , so now we have the relationship Avi = ui . Almost. If we assume vi and ui are unit vectors then we must divide by the magnitude ||Avi || to maintain the unit vector property. Let’s note something interesting about ||Avi ||2 : 10 ||Avi ||2 = (Avi )T Avi = vTi AT Avi . The first equality is how we represent squares in matrix form and the second equality is how multiple terms transposed is evaluated. Noting that since vi is an eigenvector of AT A, then AT Avi = λi vi by definition of eigenvectors and eigenvalues. Thus we are left with: ||Avi ||2 = vTi λi vi . The constant eigenvalue can be pulled to the front leaving vTi vi = ||vi ||2 , the reverse of what we did to Avi initially. But since vi is a unit, ||vi ||2 = 1. We are left with ||Avi ||2 = λi or p ||Avi || = λi . The singular values, denoted σi , of A are defined as the square roots of √ the eigenvalues of AT A, σi = λi , also equivalent to ||Avi ||. This means that i ui = Av σi and ui is a unit vector as desired. The entire U matrix is then constructed using ui ’s as the columns. U = [u1 , . . . , um ]. V is done similarly using vi ’s as the columns: V = [v1 , . . . , vn ].     Notice now that AV = Av1 . . . Avm = σ1 u1 . . . σm um . If we introduce another matrix, Σ, with the singular values on the diagonal then suddenly we get AV = U Σ. Note that to make the matrix multiplication work we have to expand Σ to size m × n and so we fill in 0’s elsewhere. Finally noting that V is orthogonal we get V V T = I (where I is the identity matrix). Then AV V T = A = U ΣV T . We have reached singular value decomposition. Singular Value Decomposition. Any matrix A can be decomposed as U ΣV T where: U = [u1 , . . . , um ] V = [v1 , . . . , vn ]   D 0 ...   Σ =  0 0 . . . .. .. . . . . .  σ1  D= 0 0 ..   . . σm One important thing to note is that when there are not m nonzero eigenvalues, D will be a smaller size. Since Σ is constructed with 0’s around D this does not matter in practice, but does raise a question of what we want to include as 11 part of the SVD. Above is what is known as full singluar value decomposition, where we take all possible eigenvalues and eigenvectors. In this case Σ is the same size as A, m × n, and U and V are square with all eigenvectors included. Sometimes we get eigenvalues of 0, which are not helpful and so we do not want to include them nor their eigenvectors. A reduced singular value decomposition, if there are r nonzero eigenvalues, would have U be m × r, V be n × r and Σ be r × r, getting rid of all the excess 0’s. It should be noted in either case that r, the number of nonzero eigenvalues, will never exceed the minimum of n and m, as both U and V have the same nonzero eigenvalues despite their different sizes. Singular value decomposition is an immensely powerful and useful tool. The main takeaway should be that any matrix can be singular value decomposed regardless of its size. We will see how techniques such as the covariance matrix and the psuedoinverse use the SVD to great effect. But before we start talking about its applications, let’s go through an example to see how any given matrix would be constructed [1]. 3.3 Example: SVD in Action   11 14 . The first thing to do is calculate AT A and find its 7 −2   80 100 40 eigenvalues and eigenvectors. AT A turns out to be 100 170 140 and the 40 140 200 eigenvalues turn out to be λ = 360, λ = 90 and λ = 0. The singular values 1 2 3 √ √ 10, σ2= 3 10 and = 0. The eigenvectors are then are then  σ1 = 6   σ3  1/3 −2/3 2/3 v1 = 2/3, v2 = −1/3 and v3 = −2/3. Notice these eigenvectors form 2/3 2/3 1/3 an orthonormal set and their collection forms the matrix V T :   1/3 2/3 2/3 V T = −2/3 −1/3 2/3 . 2/3 −2/3 1/3 Let A = 4 8 Calculating D with this information is also quite trivial. We have two nonzero singular values so those go in our diagonal matrix, D:  √  6 10 √0 D= 0 3 10 Σ is always the same size as our initial matrix in the full SVD case, so it would be:  √  6 10 0 √0 Σ= 0 3 10 0 12   18 and u2 = So u1 = 6√110 6 √   √ 3/√10 1/ √10 U= . 1/ 10 −3/ 10 Finally U is comprised of Avi σ1 . √1 3 10   3 . −9 Putting all the pieces together we get: A = U ΣV T √ 3/√10 = 1/ 10  √  √ 1/√10 6 10 −3/ 10 0  1/3 0  √0 −2/3 3 10 0 2/3   2/3 2/3 −1/3 2/3 . −2/3 1/3 Note that since the final singular value is 0, we leave it out as we do not want to divide by 0 when finding U . In general we only focus on the nonzero singular values, as those are the ones shared by AAT and AT A. Now that the theory behind singular value decomposition has been explored, it is now time to move onto some of its applications. This starts with the psuedoinverse before jumping into the covariance matrix. 4 4.1 Applications of the SVD The Psuedoinverse A pertinent application of singular value decomposition to our talk on neural networks is the psuedoinverse. This involves finding a solution to the equation Ax = b for x. If A is an invertible matrix then we can easily say x = A−1 b, however this rarely happens. Just like singular value decomposition generalized the idea of diagonalization to matrices of any size, so too does the psuedoinverse generalize the idea of an inverse. To see this, the equation Ax = b can be written using the SVD of A U ΣV T x = b. It is important to note that in this case we are using the reduced SVD where Σ has all the nonzero singular values on the diagonal and no additional 0’s. This allows Σ to have an inverse. To go further, we must show U T U = I. This comes straight from the fact that the columns of U form an orthonormal set by construction.  T u1   ..    .  u1 . . . ur . uTr Notice that uTi · ui = ||ui ||2 = 1 because ui is a unit vector. That 1 would go in the ith row, ith column spot, forming 1’s on the diagonal. Also notice that ui · uj = 0, because the columns are orthogonal. Therefore everywhere besides 13 the diagonal is filled with 0’s and we are left with the identity matrix. Note this would also work for V T V . With that being proved we can left multiply both sides by U T to get: ΣV T x = U T b. Σ has all nonzero eigenvalues of A on the diagonal and so has an inverse, which we can multiply both sides by to get: V T x = Σ−1 U T b. Lastly, since V V T 6= I, we cannot simply do as we did with U and have a clean solution for x. However, remember that multiplying a vector by a matrix of the form V V T is the same as projecting that vector onto the column space of V . Therefore if we project x onto the column space of V , we get: x̂ = V Σ−1 U T b. The pseudoinverse is the term V Σ−1 U T . We throw a hat on x to show that it is just a projection of x, and not the actual value we were looking for. This is a case where we had to use a lower dimensional basis representation to get a close estimation of x in terms of V ’s column space. The problem with this is that we do not know how good the column space of V is at explaining the data in x. It could be when representing x in this new basis that we lose a lot of information. What we really want is the basis that loses the least amount of information about x, and a little look at the covariance matrix shows us that what we are looking for is indeed the matrix V used in the psuedoinverse. 4.2 The Covariance Matrix Now we come to the covariance matrix, a hugely important topic involving singular value decomposition. For an m × n matrix, A, the covariance matrix, C, can be written as: C= 1 AAT . n−1 1 term comes from the definition of a sample covariance when data The n−1 is sampled from a population and is used to give an unbiased estimation of the population covariance. However this is not extremely important to this paper, so we can think of it as a row wise average. This formula assumes that the matrix is mean subtracted, that is the sum across any row i is equal to 0: n 1X ai,k = 0. n k=1 Unsurprisingly, to make sure a matrix is mean subtracted we calculate the mean of a row and literally subtract the mean from each value in the row. 14 The covariance matrix measures how correlated two rows in A are. Since A has m row vectors, there are m2 combinations of two vectors to test correlation between, including testing a vector against itself. This gives an intuitive reason for why C is an m×m matrix: the value in ci,j measures the correlation between the ith and jth row vector in A. Since this correlation will be independent of which vector comes first, this also gives an intuitive reason for why C is symmetric, which it clearly is because AAT is symmetric as shown previously. The covariance matrix can also be written as: 1 AT A, n−1 to measure the correlation between column vectors. These formulas can be used more or less interchangeably with the same properties for each. Depending on the situation, it can be beneficial to use one equation or the other but in this paper we will use the former. Plugging the singular value decomposition of A into the original equation for C results in: C= C = U( 1 Σ2 )U T . n−1 A few things to note: since C is symmetric it can be written as P DP T by the Spectral Theorem, where P is orthonormal and D is diagonal with the 1 eigenvalues of C. The matrix U is orthonormal and n−1 Σ2 is diagonal, and so its diagonal consists of the eigenvalues of C. Since Σ is calculated by the singular value decomposition of A, an important realization occurs: we can calculate the eigenvalues and eigenvectors of a covariance matrix using the singular value decomposition of its original matrix. In fact if we let λi be an eigenvalue of the covariance matrix and remember σi is the singular value of A, the relationship is quite simple: 1 σ2 . n−1 i Since the singular values are in fact the square root of the eigenvalues, the relationship is even simpler: the eigenvalues of the covariance matrix are 1 the same as the eigenvalues of its original matrix with an additional n−1 term added in [2]. We now have a handy way to calculate the eigenvalues of a covariance matrix, which can often be helpful to do especially when m is much larger than n. The next question is, why do we care about the covariance matrix and its eigenvalues? The answer has to do with the search for a best basis. λi = 4.3 The Best Basis Continuing with our talk on the covariance matrix, our goal in this section is to find the best projection onto a one dimensional subspace. Suppose A is a set of 15 n vectors in IRm and the data is mean subtracted. If we project the data onto any unit vector, u, then the variance, Su2 , is given as: Su2 = uT Cu, where C is of course the covariance matrix. When u is the first eigenvector of C, v1 , then vT1 Cv1 = vT1 λ1 v1 by the definition of eigenvectors and eigenvalues. This in turn equals λ1 , because v1 is just a unit, so vT1 v1 = 1. The conclusion here is that the variance of data projected to an eigenvector is the corresponding eiegenvalue of C. Next we want to estimate a vector x using parts of an orthonormal basis, {u1 , . . . , un }. First we can write the equation: x = c1 u1 + . . . + cn un . The constant vector, c can then be written as U T x using the change of basis theorem to get: x = uT1 xu1 + . . . + uTn xun . We can dot both sides with x to find the magnitude, noting that since we have an orthonormal basis, all terms combining two different vectors of U will be 0. We are left with: ||x||2 = (uT1 x)(xT u1 ) + . . . + (uTn x)(xT un ). The parentheses are not relevant, but do show how we got this mess from the simple equation a2 = aaT . We can choose to drop all but one term and add an error in place. The reason we do this is because our goal from the start of this section was to find any given point using just one basis vector. We are left with: ||x||2 = uTi xxT ui + ||xerr ||2 . 1 xxT all we have to do is Noting that the covariance matrix is equal to n−1 divide everything by n − 1 to get the following equivalent equation: 1 1 ||x||2 = uTi Cui + ||xerr ||2 , n−1 n−1 where C is the covariance matrix for x. Of the three terms (one on the left of the equal sign, two on the right), the middle term should look familiar. It’s the variance of x projected onto a unit vector, which u1 clearly is coming from the orthonormal set. Finding the best projection obviously involves minimizing the error term. However since x is given, the left most term is a constant whereas the other two terms depend on which vector, ui , is picked. Therefore minimizing the error is equivalent to maximizing the variance. Let’s do that. Since C is symmetric, its eigenvectors form an orthonormal basis for IRn from the Spectral Theorem and we can write any vector as a combination of 16 these vectors using the Change of Basis Theorem. Therefore u = V c where c is just a vector of constants and V is a matrix with the eigenvectors of C in the columns. Furthermore C = V DV T from the Spectral Theorem. Then we get: uT Cu = (V c)T (V DV T )(V c) = cT (V T V )D(V T V )c = cT Dc. Then noting that D is just a diagonal matrix with the eigenvalues of C we get: = c21 λ1 + c22 λ2 + . . . + c2n λn . We also want this whole term to be a unit vector, Pso we can say that this quantity is equal to p1 λ1 + p2 λ2 + . . . + pn λn where pi = 1. This is because the whole term is a unit vector, and all pi are nonnegative because all the ci ’s are squared. Interestingly this turns out to be like a probability function. From here it is pretty easy to see that maximizing this function is solved by finding the biggest eigenvalue, λj , and letting pj = 1 while all other pi = 0. If we note that the eigenvalues are listed in decreasing order in D by construction of the covariance matrix, then we know λ1 is the biggest eigenvalue. What did we do this all for? We were trying to find the vector that maximized the variance term to find the best 1 dimensional basis for IRn . This best basis turned out to be created by the eigenvector corresponding to the first (and largest) eigenvalue of the covariance matrix, and generally the best k-dimensional basis is found by taking the first k eigenvectors of the covariance matrix [2]. This fact, coupled with our earlier discovery on the covariance matrix, is hugely important. Not only do we know the best k-dimensional basis comes from the first k eigenvalues of C, an extremely helpful fact for representing data using far fewer points, but also the eigenvalues of C come straight from the singular value decomposition of the original matrix. So far this paper has looked at the Change of Basis Theorem, singular value decomposition, the psuedoinverse and the covariance matrix as main points of interest. How does they all tie together? Well the V term from the SVD allows the psuedoinverse to project a matrix X onto the column space of V using the Change of Basis Theorem. The matrix V consists of the eigenvectors of AAT , which we said could be used to calculate the eigenvectors of the covariance matrix. We also said when changing to a different basis that the first k eigenvectors of the covariance matrix were the best basis to change to in order to minimize the error lost. Therefore the psuedoinverse is more powerful than we thought. Since V is the best basis, the projection of X is actually the best we can get. We will use the psuedoinverse later to solve the same problem a neural network would be used for, but in a different way. Because of this, it is nice to know the psuedoinverse is mathematically the best we can do. 4.4 Example: Finding the Best Basis Before heading into bigger examples it is beneficial to understand how these concepts work. Suppose we have a matrix: 17  4 3  A= 4 1 3 1 5 2 1 3  1 1  6 . 1 6 The covariance matrix assumes that A is mean subtracted, so we can calculate the mean row-wise and subtract it from each term in the row. Now we get:   2 −1 −1  0 2 −2   0 −2 2 A= .   0 0 0 −1 −1 2 Here we have 3 vectors in IR5 . Let’s say we want to find a 1-dimensional representation of our data. Firstly, of course, we must find the eigenvalues of the covariance matrix. We could do that by calculating the covariance matrix,   3 0 0 0 −3/2  0 4 −4 0 −3   0 −4 4 0 3 C= ,   0 0 0 0 0 −3/2 −3 3 0 3 and then solving for its eigenvalues. But notice that involves dealing with a 5 × 5 matrix. Instead we could calculate the singular values of A by first finding AT A:   5 −1 −4 AT A = −1 10 −9 . −4 −9 13 The benefit is that we now only have to calculate the eigenvalues for a 3 × 3 matrix. It should be clear how useful this becomes when the number of rows greatly exceeds the number of columns. The eigenvalues for AT A are 21, 7 and 0. Now all we must do is divide by 7 n − 1 = 2 to find the eigenvalues for C. These are 21 2 , 2 and 0. The best basis is then constructed by the eigenvector associated with the largest eigenvalue, in this case: r −1/2 21  −2 , v1 = 2 5/2 after normalizing the vector. However this is the eigenvector of V in the singular value decomposition of A, and since we want our vectors in IR5 we i must multiply by A to get to the U in the SVD, by the equation ui = Av σi : 18   7/2 r  1  41   −1 . u1 =   2  0 5/2 Using the Change of Basis Theorem, let’s see what happens when we try to represent a column of A using our low dimensional representation. The coordinate for a1 in the space spanned by v1 would be:   2 r  0   19 41  0 7/2 1 −1 0 −5/2  = q . c1 = uT1 a1 =   2  0 2 41 2 −1 Reconstructing a1 , denoted â1 results in:   1.62  .46    â1 =   −.46 .  0 −1.16  T This is fairly close to the original a1 = 2 0 0 0 −1 , a minor miracle considering we only have one vector with which to explain it and the other two vectors. The other vectors, â2 and â3 , are a little further off from their  T  T original vectors, a2 = −1 2 −2 0 −1 and a3 = −1 −2 2 0 2 respectively, but still decent considering the circumstances:     −2.13 .51  −.61  .15      , â3 =  .61 . −.15 â2 =        0 0 1.52 −.37 Not bad at all considering the restraints given by the one vector. Keep in mind this v1 is the best one dimensional basis for the data residing in A. Hopefully this small example provided clarity to the power of the best basis. 4.5 SV-Spectral Decomposition The idea of the best k-dimensional basis given by the first k eigenvalues of the covariance matrix is tied to something we have already seen. One nice fallout from the Spectral Theorem we saw earlier was spectral decomposition, where any symmetric matrix could be written as a sum of products: A = λ1 u1 uT1 + λ2 u2 uT2 + . . . + λn un uTn . 19 Like we saw with the psuedoinverse, the SVD can be used to generalize this idea to matrices of any size. The following formula allows us to write a matrix of any size as a sum of its singular values and eigenvectors from its singular value decomposition. This allows us to easily and immediately find the best estimation of a matrix in any k-dimensional space by taking the first k terms of the sum. Singular Value Decomposition Theorem. A = σ1 u1 vT1 + σ2 u2 vT2 + . . . + σr ur vTr . where the σ’s are the singular values of A and the u’s and v’s come from the singular value decomposition [1]. One thing to note is that the terms are arranged in decreasing order with σ1 the largest singular value. From our discussion on the covariance matrix we know the first k eigenvalues best describe the data. Therefore we could represent a matrix using the first k terms in the previous decomposition. 4.6 Practical Applications Here we now switch gears away from the theoretical linear algebra to applications of what has been covered so far. Take this picture of a mandrill for instance: This image is a 480 x 500 matrix, where each entry is an integer in [0, 220] representing a color. We can use the previous formula to estimate the image using the first k terms. Below are the estimations of the mandrill for k = 3, 6, 10, 50, 150 and 450 respectively. 20 At k = 50 we can very clearly make out the mandrill. The amazing thing is that we used 1/10th the information of the original matrix. It may not be quite as pretty, but it gets the job done and saves a lot of effort in the process. This is a larger, visual example of how powerful the best basis can be. However when going down in dimension, some data is lost. The following image represents the error - the data left out - for each of the previous estimations in the same order. At k = 50 and above the error is essentially just noise. Clearly after a certain 21 point it becomes more and more difficult to extract data that really adds a lot. This realization is of use to us: if we can estimate a matrix of any data using far less dimension while keeping the general meaning of the data in tact, that will save time, memory and effort. Another example of an application of the best basis is in a video. Here is a data set representing a short video, 109 frames long, of Professor Hundley. With each frame being 120 x 160 pixels, or 19200 pixels total, this data set is a matrix of size 19200 x 109, again of integers representing a color (but this time) in grayscale. We can think of this as a matrix,X, in IR19200 . One of the 109 frames is shown below: We can also look at the mean of the data, interestingly just the background Like the example of the mandrill, we want to find a lower dimensional basis of the data but instead we will look at how a different number of eigenvalues affects the quality of the data. Below is a graph of the eigenvalues by their order. 22 Since this data set has been mean subtracted and the eigenvalues have been normalized, these eigenvalues actually represent the percentage of the data represented if taking just that eigenvalue as a lower dimensional basis. For example, the first five eigenvalues of X T X are: .3436, .1129, .0847, .0566, .0407 Therefore using the first eigenvalue would explain 34.36% of the data while using the first two would keep 34.36 + 11.27 = 45.63% of the data. This is the same as estimating our 109 points in IR19200 using only two vectors. We would need 22 eigenvalues to explain 90% of the data, not bad at all considering we have 109 nonzero eigenvalues in the full set of data. Hopefully this example once again showed the use of the singular value decomposition theorem as a tool to approximate large data sets using far less time and effort. 5 Neural Networks With much of the background material behind us, we can now focus on the topic of this paper: neural networks. The neural network is a powerful tool that finds relationships between complex data held in variables and observations. It is used for a variety of tasks such as pattern recognition, line fitting, data clustering and more. Unsurprisingly the network is rooted in linear algebra, including much of what we have just seen. An important thing to know is that a neural network is based heavily off the biological processes of the brain. In the brain there are neurons that receive data from other neurons through connected strings called axons. Certain neurons are more connected than others, and the brain as a whole is made up 23 of impossibly complex arrays of neurons and axons. The neural network was created to simulate how the brain works. Instead of neurons we have nodes, a collection of data for one variable for multiple observations. Nodes are classified into layers: the input layer and the output layer are necessities while a hidden layer is also often included. In the case of deep learning, there exist multiple hidden layers. To start, let’s understand the data we are looking at and what we are trying to glean from it. There are two instances of a neural network. In a supervised neural network (or supervised learning) we are given a collection of input data and a collection of output data. This differs from unsupervised learning where we do not have output. This paper will focus on the supervised case. The goal of the neural network is to predict the output given just the input. Since we have the output in the supervised version, we can figure out how accurate the neural network is, and then update it to make it better. This is an example of adaptive learning, something the neural network thrives at; as more points are added to the network, it learns from itself to produce an even better prediction of the output. To make things easier, we put the input data in an m × p matrix, X, and the output in an n×p matrix, T (where T stands for target). The numbers m and n represent the different variables for X and T respectively, whereas p represents the different observations. For X, each of the p vectors can be thought of as all the variables for one observation. Throughout our talk on neural networks there will be an ongoing example involving cancer. To better understand the basic concepts of neural networks this example will now be presented. 5.1 Example: Cancer With this example we are given a 9 × 699 matrix of input values, X, with 9 variables for each of the 699 observations. An observation in this case is a different patient we have data on. We are also given a 2 × 699 matrix of target values. The 9 variables from the input describe the tumor of a patient: clump thickness, uniformity of cell size, uniformity of cell shape, marginal adhesion, single epithelial cell size, bare nuclei, bland chromatin, normal nucleoli and mitoses. Congratulations if you understood over half those words. These 9 variables will be used to predict T . There are two rows in T , one for if the tumor was benign (harmless) and one for if the tumor was   malignant (cancerous). A 1 1 is placed in the row of what actually occurred, so would represent benign and 0   0 would represent malignant for a given observation. Using all 699 patients, 1 the neural network will find a relationship between the 9 predictor variables and if the patient has cancer. This is the benefit of a supervised network, as we know exactly what output corresponds to the inputs. With a large amount of data feeding into the network, we can then use the finished product to predict the type of tumor for a patient whom we do not have an output value for, given that we have the 9 predictor variables for them. This example should show how 24 important a neural network can be in application. Now we will see how it works in theory. 5.2 Neural Network Theory Without further ado, let’s look at a visual representation of a neural network. x1 y x2 Here is the most basic neural network, a perceptron, where there is one layer of inputs and one layer of outputs. A layer in picture form is a series of nodes on the same vertical. Layers are represented by vectors for one observa T tion, so the vector x is simply x1 x2 . If we account for all observations, each layer represents a matrix. The matrix for the input layer would then be a 2 × p matrix, X, where p is the number of observations. For the output we see a new variable, y. The matrix Y , generally n × p but in this case almost trivially 1 × p, is the output predicted by the neural network. Note the distinction between Y and T ; T is known in supervised learning whereas Y is a prediction of T based on the inputs. The most successful network will be the one that minimizes the difference between T and Y . Otherwise put, the most successful network will be the one that is best able to predict T using just the inputs. To do this we need a weight matrix, W . To map from X to Y , the weight matrix will in general be an n × m matrix, independent of the number of observations. The goal of neural networks can be reduced to finding W such that: T = W X + b, where b is just the resting state for each node. This is known as an affine function, meaning almost linear. To make it a linear function, we can augment the matrix W with b, as [W |b] and add a row of 1’s to X. Then we get the same thing as above written as a linear function:     X T = W |b . 1 We can then write this as: T = W X, if we note that W is now n × m + 1 and X is now m + 1 × p with a row of 1’s at the bottom. We do not need a neural network to ‘solve’ this equation for W , rather we can just compute the psuedoinverse of X. Therefore: 25 Ŵ = T V Σ−1 U T . Notice that we throw a hat on W to indicate that this is only a projection of the real W onto the column space of X, as this is a necessary sacrifice that happens when we use the psuedoinverse. This new matrix Ŵ can then be used to compute Y : Y = Ŵ X. The predicted output Y will be equal to the target output T only when T is in the column space of X, a rare occurrence. Otherwise Y will be as close to T as possible using the best basis previously talked about. This is one way to solve this problem, which we call the linear algebra method. It is concise and useful, but also limited. This will work the best if the relationship between X and T is linear, also a rare occurrence. To take more complex functions into account, we will use a neural network. The pereceptron is not a very interesting case of a neural network as we can accomplish the same thing with the linear algebra method. What makes them more interesting is the addition of a hidden layer: s1 x1 s2 y x2 s3 Note in this case we are still mapping from IR2 to IR1 , except this time there is a middle layer of nodes that requires a transformation from IR2 to IR3 before going from IR3 to IR1 . The point of a hidden layer, in this case S, is to add complexity to the type of relationship between X and Y . When we think X and T are complexly related then we should include a hidden layer with more nodes, whereas less nodes will indicate a simpler relationship. As in the linear algebra method, we can calculate the product W X. Unlike last time where we found a projection of W , we will be calculating W from past iterations of itself. This goes back to the idea of adaptive learning. Once we have a pretty good W , we do not want to scrap it entirely when going through the network again. Instead we will gently change it to reflect the new data. However this method also requires that we have a W to start with, so for simplicity we initialize W to be, in this case, a 3 × 2 matrix of random values. 26 Let P = W X. Another thing we can do to increase the complexity is add a function in the hidden layer, applied componentwise to P . This can be extremely beneficial for linear classification problems as we will see with the cancer example. We apply the function from IR to IR to every element in P to get S, which will then become the input matrix for the next layer: P = W X, S = σ(P ), Y = W̄ S = W̄ σ(W X), where W̄ is the second weight matrix. We could also choose to include a function after the hidden layer, but don’t in this case as it generally doesn’t add as much complexity as the first function. So what is this mysterious function, σ? Well it could be any function, but typically the function we choose is a Logistic Sigmoid function (also called logsig). The logsig function is as follows: σ= 1 , 1 + e−βx and looks like this: [5] This function is special because it is asymptotically bounded below by 0 and above by 1 and is very close to one of them in most places. Furthermore, it is a strictly increasing function. This first property should remind you of a probability function. This can be very useful for figuring out the desired output for a linear classification problem. For instance a large input will result in a number very close to 1, which we can interpret as the probability that the  1 function output is actually 1. Recall in the cancer example how benign was 0   0 and malignant was . The predicted output elements of Y will very rarely 1 be exactly 1 or exactly 0. However by using the logsig function we can find the probability that any given value in Y really should be a 1 or 0. 27 With the function taken care of, let’s look back at our predicted output matrix, Y : Y = W̄ S = W̄ σ(W X). We have Y , now what? Recall that we wish Y to be as close to T as possible. To do this we must train the network. There are different ways to do this, but the method this paper will focus on is known as Hebbian learning. Unlike other types of training, Hebbian or on-line learning modifies W and W̄ after looking at observations one at a time. This type of training is also dependent on the fact that we are working with a supervised network. When we know the actual value for the output, we can calculate the error term for the kth observation by subtracting the predicted value from the actual value: E(W, W̄ ) = tk − yk . Given that some errors may be positive and some may be negative, we calculate the total error term of the function by squaring the norms of the individual errors and summing over all observations. We square the terms instead of applying the absolute value function so that we can take the derivative. In totality the error function can be given by: E(W, W̄ ) = p X ||tk − yk ||2 . i=1 The neural network is at its best when this error term is minimized. However minimizing the function is not so simple as taking a derivative in the traditional sense. Notice that the error is a function of two matrices, each of those having multiple entries. To solve this problem, we will turn to the multivariable calculus technique of gradient descent. 5.3 Build up to Gradient Descent Let’s take a look at our example neural network again: s1 x1 s2 x2 s3 28 y Notice that there are 6 lines going from the input layer to the hidden layer. These represent the 6 entries in the 3 × 2 weight matrix, W . Similarly the three lines going from the hidden layer to the output layer represent the 3 entries in the 1 × 3 matrix, W̄ . Although I have used matrix form to express the equations, I would now like to write out the problem in all its gory detail to stress the relationship between different variables. First we start with S = σ(P ) = σ(W X), where it is important to remember that σ is applied componentwise, not to the whole matrix:     ! s1,k w1,1 w1,2  x 1,k s2,k  = σ w2,1 w2,2  , x2,k s3,k w3,1 w3,2 which in turn is equal to:    ! s1,k w1,1 x1,k + w1,2 x2,k s2,k  = σ w2,1 x1,k + w2,2 x2,k  . s3,k w3,1 x1,k + w3,2 x2,k Don’t let the numerous subscripts scare you. The first subscript for each variable is the ith row, the second entry for the weight matrix is the jth column and the k just means we are looking at the kth observation. Notice then how all these terms are just single 1 dimensional values, not vectors or matrices as we’ve seen before. Now it should be much clearer how each hidden layer node, si,k , is a function of each entry in W . Instead of one big problem involving a nasty matrix we have 3 problems each with 2 unknowns, m equations with n unknowns generally. We’re only halfway through the network though. The back half written out is: yk = w̄1 s1,k + w̄2 s2,k + w̄3 s3,k . Then plugging in for si,k we get: yk = w¯1 σ(w1,1 x1,k +w1,2 x2,k )+w¯2 σ(w2,1 x1,k +w2,2 x2,k )+w¯3 σ(w3,1 x1,k +w3,2 x2,k ). A mess, to say the least, which is why we usually write it in matrix form. However this formula explicitly shows the relationship between yk and the 9 variables (6 from W , 3 from W̄ ) we want to change. The error function would be a little more complicated but would still only include these 9 variables. Now we can use multivariable calculus to find the w’s and w̄’s that minimize the error function. 5.4 Gradient Descent The whole point of gradient descent is to find the W and W̄ that minimize the error function. Recall the error term for the kth observation is E(W, W̄ ) = ||tk −yk ||2 , though in this example each of these vectors is just 1 point, so we can 29 say E(W, W̄ ) = (tk − yk )2 . Unsurprisingly, gradient descent involves computing the gradient, a vector that points in the direction of largest increase, though we would negate the gradient to find the direction of largest decrease. The gradient is found by taking the partial derivative of each variable in the equation. In our case we have 9 variables. We start by taking the partial derivative of E with respect to something that y is a function of (the dummy variable h) for the kth observation: ∂yk ∂E = 2(tk − yk )(− ) ∂h ∂h k With that in mind, we can now calculate ∂y ∂h in the two cases where h = wi,j and h = w̄i . The second case is a little easier. Earlier we said: yk = w̄1 s1,k + w̄2 s2,k + w̄3 s3,k . Then clearly we have: ∂yk = si,k , ∂ w̄i and in totality we get: ∂E = 2(tk − yk )(−si,k ). ∂ w̄i This accounts for 3 of the variables, since there are 3 entries in W̄ . ∂y . Notice that the same formula for yk as above Next we want to find ∂w i,j and the fact that si,k is a function of W implies that: ∂yk ∂si,k = w̄i ∂wi,j ∂wi,j = w̄i ∂σ(pi,k ) , ∂wi,j using our definition of p from before. Using the chain rule we can deconstruct the partial even further. Therefore we have: ∂pi,k ∂yk = w̄i σ 0 (pi,k ) . ∂wi,j ∂wi,j The answer to the partial on the right is hidden in our equation for pk :     p1,k w1,1 x1,k + w1,2 x2,k p2,k  = w2,1 x1,k + w2,2 x2,k  . p3,k w3,1 x1,k + w3,2 x2,k Simply the partial on the right is just equal to xj . Then using the logsig function for σ: σ= 1 , 1 + e−x 30 the derivative of this function conveniently turns out to be: e−x = σ(x)(1 − σ(x)). (1 + e−x )2 When evaluated at pi,k , we are able to put it back in terms of s: σ(pi,k )(1 − σ(pi,k )) = si,k (1 − si,k ). The whole partial is: ∂y = w̄i si,k (1 − si,k )xj,k , ∂wi,j and going up one more step we finally get: ∂E = 2(tk − yk )(−w̄i si,k (1 − si,k )xj,k ). ∂wi,j This gives us the final six partial derivatives for the six entries in W . The gradient in all its glory then is:  =  ∂E ∂E ∂E ∂E ∂E ∂E ∂E ∂E ∂E , , , , , , , , . ∂w1,1 ∂w1,2 ∂w2,1 ∂w2,2 ∂w3,1 ∂w3,2 ∂ w¯1 ∂ w¯2 ∂ w¯3 But that’s not the end. Since Hebbian learning involves calculating the gradient for each observation we would then have to update the weight matrices based on this new observation. The update equation is like this: wi,j,new = wi,j,old − α ∂E , ∂wi,j,old and similarly: w̄i,new = w̄i,old − α ∂E . ∂ w̄i,old The constant α is the learning rate, controlling how drastic the change in weights are, where a large α would indicate a larger change of the weights. After all that we would add a new observation to the network and retrace our steps. Now aren’t you glad the computer does this for us? 5.5 Example: Cancer Revisited Recall the cancer example. Using both the linear algebra method and the neural network method we can try to predict the type of cancer based on the 9 inputs. First we will use a neural network. Since we have 699 observations, we can divvy up the observations to train the network as just described and to test how our network performed. Generally we want more observations for training, though we can choose what percentages 31 to use. In this case we chose to give 489 (or 70%) of the 699 samples into the network to train it. Of the remaining samples, 15% are used during the validation stage, similar to training except it halts when the accuracy of the network has stopped improving, protecting against overfitting. The rest of the samples are then used to test our model. The accuracy will be different for every trial and will depend on which samples were included in each stage. The hidden layer contains 10 nodes, a choice by us since we expect a certain level of complexity from the relationship. Using a program called MatLab to run the network, the results can be visualized using a confusion matrix (no, it is not named for how confused you feel looking at it). The four squares reveal the accuracy of our network at each stage (training, validation and testing) as well as overall. The target class is what actually happened where the output class is predicted by the neural network, T and Y respectively. Class 1 corresponds to benign and class 2 corresponds to malignant, so the four top left squares in each bigger square show how many points and the percentage of said points that fall into each combination of output and target. For instance when a patient’s tumor is malignant (target = 2), the network correctly predicted this every single time during the testing stage. This is good; if you have cancer, you would want to know this and this network would 32 accurately tell you (at least with this data). If a patient did have a malignant tumor and the network predicted otherwise, this error would be known as a false negative. The alternative error, a false positive would occur when malignant is predicted but is not the truth. This happened 4.1% of the time in the test stage, although one could argue that it is not as grievous of an error as the false negative. Perhaps surprising to some, the network performs very well overall, even when it’s in the process of training. The blue square in the bottom right of each larger square is the total accuracy, over 97% for all. Clearly this example shows how powerful a neural network can be in predicting outcomes. How does the linear algebra method fare compared to the neural network? As explained previously, we first calculate the psuedoinverse of X̂ then multiply it by T , which is given, to find Ŵ . Multiplying Ŵ by X̂ gets us the predicted matrix Y . Here are the first eight columns of Y ’s 699 total using this method:  1.0187 −0.0203 1.0135 0.9341 0.4624 0.8169 0.9683 0.1173 −0.0062 0.0773 0.5725 0.1625 0.0120 0.9284 −0.0468 1.1300  Notice there are two rows. Why is this the case? For a linear classification problem with k classes we set the target value as each of the elementary basis vectors in IRk . In this case, there are two classes and malignant) and  (benign  1 0 so the values for any target value is either or . Since the eight columns 0 1 above are from the matrix Y , the values are not exactly either of these two vectors, but there are certain places where you can see it is close to one or the other. Graphing all 699 values in Y shows us how close they are to the two points we want. 33 The blue points are when the actual value was malignant while the red corresponds to benign. We would use the perpindicular line through (.5, .5) as a cutoff for determining the prediction: left of the line we classify as malignant and right of the line we classify as benign. Some predictions from Y are well off the mark but when taken as a whole this is fairly accurate. It is also interesting    0 1 to note that the points are all very close to or on the line going from to . 1 0 This shows that this problem is almost linear, and so the linear algebra method should perform similarly to the neural network. We can check a confusion matrix, Co, to see how well it performed:   449 18 Co = , 9 223   98.03% 7.47% Co = . 1.97% 92.53% MatLab comes with a neural network toolbox that created the last confusion matrix automatically, the reason why this one might not be as visually appealing. However it still gets the job done. Just like the last confusion matrix the columns represent what the actual value was (benign and malignant respectively) while the rows represent what was predicted. The percentages indicate the accuracy keeping target constant (the two left boxes on the bottom row in the previous confusion matrix). So the 98% could be interpreted as the percentage of the time the algorithm correctly predicted a benign tumor, whereas the 7% is the percentage the algorithm predicted benign when the tumor was actually malignant. This is not a bad method for predicting, as it produced a correct output 96% of the time. However a neural network blows it out of the water, especially when it comes to the false negative case. The 7.47% error in this case is far inferior to the 0% from the neural network, especially for something as morbidly awful as telling a patient they do not have cancer when they really do. Although the linear algebra method was fairly successful for this data set, for this and more complicated relationships a neural network is the way to go. 5.6 Example: Function Fitting Here is another example of what a neural network can accomplish. The cancer example showed a neural network performing linear classification, designating output into one of two categories, but a neural network can also perform function fitting. In this example, a data set was generated using 25 random points from [0, 2π] to be the input vector x. The output matrix was given by the function t1 = cos(x) and t2 = sin(x) where t1 and t2 are the first and second rows of the target matrix T . In this case and unlike most other cases, there is a specific function between the inputs and outputs. We know this function, but the neural network does not. This data set then is a good test for the neural network to see how accurate it can be. To see the difference between different hidden layers, 34 we can use different amount of nodes in our network and compare the output. First we will try a three node hidden layer, then a ten node hidden layer. What we can see here is that the three neuron fit has far more error, but it’s line is much smoother giving a better general fit for the data. The ten neuron fit is far better at reducing the error but may have overfit the data, as we know the actual relationship between input and output is not nearly as complicated as the fit it gives us. This is a good example of how the different number of neurons can affect the results of the network. 35 6 Conclusion Alas, I have reached the end of what I covered this semester on neural networks. There is so much information regarding the networks, singular value decomposition, best bases and more yet there was only so much time to cover them. A more complete report would have covered back propagation of error, a technique used at the end of the neural network. There are also many different types of neural networks to explore, including different uses (data clustering for instance) and different training methods (taking all observations at once). It would also have been interesting to see the difference over many samples between the linear algebra method and the neural network, as well as exploring mathematically how the different number of nodes in the hidden layer affect the conclusions. Neural networks are a fairly new field, yet it would still be interesting to research the history of them. Certainly there is so much more about neural networks to learn and discover, yet this paper gives the basics that are essential to understand. I would like to acknowledge the help of Dylan Zukin, Professor Balof and especially Professor Hundley for editing and general teaching throughout the learning proccess. References David C. Lay. Linear Algebra and its Applications Fourth Edition. AddisonWesley, Boston, Massachusetts, 2012. Douglas Hundley http://people.whitman.edu/ hundledr/courses/index.html Dolhansky, Brian. “Artificial Neural Networks: Linear Classification (Part 2).” RSS. N.p., 23 Sept. 2013. Web. 29 Mar. 2016. Stansbury, Dustin. “A Gentle Introduction to Artificial Neural Networks.” The Clever Machine. N.p., 11 Sept. 2014. Web. 29 Mar. 2016. “Logistic Function.” Wikipedia. Wikimedia Foundation, n.d. Web. 02 May 2016. 36 Alphabetical Index Adaptive Learning, 24 Basis, 4 Basis Vectors, 6 Column Space, 7 Coordinates, 6 Covariance Matrix, 14 Eigenvalue, Eigenvector, 9 False Negative, 33 False Positive, 33 Full Singular Value Decomposition, 12 Gradient, 30 Gradient Descent, 29 Hebbian Learning, 28 Hidden Layer, 26 Learning Rate, 31 Linear Classification, 34 Linear Combination, 4 Linear Independence, 4 Logistic Sigmoid Function, 27 Mean Subtracted, 14 Neural Network, 3, 23 Orthogonally Diagonalizable, 9 Orthonormal, 7 Orthonormal Set, 6 Perceptron, 25 Psuedoinverse, 14, 25 Reconstruction, 7, 8 Reduced Singular Value Decomposition, 12 Singular Value Decomposition, 10 Spectral Decomposition, 10, 19 Supervised Network, 24, 28 Symmetric Matrix, 9 Unit Vector, 6 37