[K-MOOC]  Introductory Mathematics for Artificial Intelligence

                Translated by

  Sang-Gu LEE with Youngju NIELSEN, Yoonmee HAM

         from the original Korean text written by

      Sang-Gu LEE with Jae Hwa LEE, Yoonmee HAM, Kyung-Eun PARK

    Part Ⅴ. PCA and ANN

12. Principal Component Analysis    

  12.1 Dimensional reduction

  12.2 Principal Components Analysis (PCA)

  12.3 Finding principal component

  12.4 Examples of principal component analysis

  *12.5 Principal component analysis and covariance matrix

  *12.6 Principal component analysis and linear regression

12.1 Dimension reduction

<Principal Components Analysis (PCA)> is the most important part of this book. Large or high-dimensional data is difficult to analyze

because it is difficult to compute and visualize. Therefore, it is necessary to reduce the dimension of the data while maintaining the distribution

of the original data as much as possible. It is called a dimension reduction. Principal component analysis is one of the most widely used

dimension reduction techniques. It converts data in high-dimensional space into data that can be handled in a low-dimensional space

while preserving the original data's distribution as much as possible. It is why the PCA is one of the most fundamental and essential part in AI.

In 1974, <MOTOR TREND MAGAZINE> published some data that characterize and quantify cars released during the year 1973-74.

Given below are some of the data on the 11 variables from that publication:

	mpg	cyl	disp	hp	drat	wt	qsec	vs	am	gear	carb
Mazda RX4	21.0	6	160	110	3.90	2.620	16.46	0	1	4	4
Mazda RX4 Wag	21.0	6	160	110	3.90	2.875	17.02	0	1	4	4
Datsun 710	22.8	4	108	93	3.85	2.320	18.61	1	1	4	1
Hornet 4 Drive	21.4	6	258	110	3.08	3.215	19.44	1	0	3	1
Hornet Sportabout	18.7	8	360	175	3.15	3.440	17.02	0	0	3	2
Valiant	18.1	6	225	105	2.76	3.460	20.22	1	0	3	1
...

[Source] Robert Reris and J. Paul Brooks, Principal Component Analysis and Optimization: A Tutorial, 14th INFORMS Computing Society Conference, Richmond, Virginia, January 11–13, 2015, pp. 212–225.

http://www.people.vcu.edu/~jpbrooks/pcatutorial/ 

As we can see in this table, each car's data is presented as an 11-dimensional vector. Such multidimensional data is difficult to analyze

because it is not easy to visualize and compute. Therefore, it is necessary to reduce the dimension of the data while preserving the distribution of

the original data as much as possible. This process is called a dimension reduction. It is possible to extract and only use the data of

some essential variables(feature selection), but it is impossible to know in advance what a close relationship exists between the variables.

So even if we select and analyze only the weight and displacement (engine/piston/cylinder) in this way, we may not be sure that

it properly reflects the distribution of the initially sufficiently investigated data. Therefore, an analysis of the choice of the principal component

is necessary to determine which function or element to analyze. This process is called the Principal Component Analysis (PCA).

12.2 Principal Component Analysis (PCA)

The Principal Component Analysis (PCA) is one of the most widely used dimension reduction techniques. Basically, PCA converts

a data set from high-dimensional space into low-dimensional, easy-to-handle spaces while preserving the distribution of the original data

as much as possible. The PCA combines existing variables to find new variables that are not related to each other, namely, principal components.

The first principal component PC1 preserves the original data distribution as much as possible, the second principal component PC2

preserves the distribution of the next original data as much as possible too, and so on.

In the case of 11-dimensional data, the 11 principal components can be created by combining existing variables.

For example, let us assume that PC1, PC2, and PC3 preserve about 90% of the distribution (property) of the original data.

Then, we still can perform a rational analysis and capture majority of the insights even though 10% of the information is lost

when we do the analysis with only PC1, PC2, and PC3. So we can simply reduce the dimension of our analysis to 3D data

by selecting only PC1, PC2, and PC3 for the next level of analysis. In this case, it is much easier to compute and visualize,

and it allows us to analyze the data without much difficulty.

◆ To find the principal component, we need to find a new axis, which is called <the principal axes or principal direction>.

The first axis sets the largest distribution of data obtained by projecting the original data onto this axis. Below is a picture of the given 2D data (left picture)

orthogonal to the first axis (right picture). At this time, the projected data constitutes PC1.

[Source] High school grades (GPA) and university grades (GPA) data of 105 computer science students (centered) are available at the following links.

      http://onlinestatbook.com/2/regression/intro.html

      http://onlinestatbook.com/2/case_studies/sat.html

How to find the new axis? When the data are given, the orthogonal projection should be used to find the new axis

where the error is relatively small. We take  the first axis, whose distribution is the largest, and call it PC1. And we continue to do this

for PC2 and PC3, etc., in the same way. For the second axis, when the original data is projected onto the PC1 axis, the obtained data distribution

is the largest after PC1. Again, using the concept of projection, we consider the size of the sum of the errors. And so on, then PC1 and PC2

are not related to each other, which means the second axis is not related to the first axis. This is the reason that we studied

the orthogonal projection and Gram-Schmidt orthonormalization process was for this.

In order to implement process, a principal component analysis is needed to set the axis so that essential variables are collected as each principal component,

and that each principal components are not related to each other and are (if possible) linearly independent. It is a concept related to

the diagonalization of matrices. This is why it is necessary to ensure the orthogonality of the different principal axes.

The process of finding axes that are linearly independent of each other in the orthogonalization method is used for principal component analysis.

We could say that it was to be able to do this that we studied Linear Algebra, particularly about the matrix diagonalization (or SVD).

The picture on the left below is a projection of the given 2D data by finding the second axis. Here, the projected data forms PC2.

And if we let the first main axis as the -axis, the second main axis as -axis and do the orthogonal projection of the data,

it will be looked like a picture on the right. Hold the - and -axes like below. From this, we can intuitively understand that the distribution

of the orthogonal data along the first principal axis is much larger. The -axis distribution is longer and the -axis distribution is shorter.

12.3 How to Compute principal component

Let's do the principal component analysis. is called an data matrix. Suppose that is the number of samples, and is the number

of random variables {, , } representing the features of the data. In statistics, in general, we simply use lowercase notation {, , }

instead of uppercase notation {, , } for random variables to distinguish it from the data matrix . So, here we will use random variables

in the lower case of as {, , }. Let's say that the component of the data matrix means one data set for the th random variable

in the -th sample. And , the column of , means all the data set of the random variable .

Let be the matrix that is centered ("centering, adjust the mean of the random variable to zero") from the data matrix as above,

so the mean of the random variable in any mean centered matrix are all zero. There are a number of reasons for this.

It makes all the computations become simple, and the analysis becomes straight forward and easy.

① [Define the centered matrix as (tilda)]. Given a matrix named , we define a centered matrix , so that the mean of the random variables are all zero.

② To do this, find averages of each column in (each random variable). The mean of the random variable is denoted by . 

       , ,  .

We now have  the centered matrix after subtract the mean (of the column) from the data for each column of as following.

This centered matrix is called a mean-centered matrix because it is made for that purpose. From now on, we will assume that a given data matrix

is ​​simply a mean-centered matrix = already for an easy subsequent analysis when we develop the theory.

③ Find the Singular Value Decomposition (SVD) of a mean-centered matrix .

Here, and are orthogonal matrices, and is the diagonal matrix with  singular values

as the main diagonal component arranged in order of magnitude. The interesting thing here is that only (rank of the matrix ) singular values

are greater than 0 and the rest are 0. Hence, after the multiplication, the result is , which means that only the first columns

were used in the orthogonal matrix , and only columns were used in the orthogonal matrix .

④ In the Singular Value Decomposition of , the column vector of becomes the principal axes.

⑤ If the product of and is expressed as , the column vectors of , obtained by the original data's orthogonal projection

to the principal axis, become <principal component scores (PC scores)>.

⑥ After that, computed with singular values becomes the variance of -th principal components, and becomes the ratio at which the -th principal component preserves the distribution of the original data.

By computing the proportion that preserves the distribution of the original data for each PC(principal component), we can decide the reduced dimension

that we like to use.

⑦ If we decide the reduced dimension as () from the original dimension , we only select the first column vectors () of

and the -th leading principal submatrix () of , then becomes an matrix containing the first PC (principal components).

                .

◩ Open Problem 1

Explain how a singular value decomposition (SVD) is used in the principal component analysis.

12.4 Examples of PCA                                                

In this section, we introduce one example of principal component analysis using a numerical data set. Specifically, using this dat set,

we will perform a PCA as a practice example. We create an example so that we can check the data implemented with the real Sage and R code.

A 4-item Likert survey with a scale of 7 was conducted on 16 people on what people are interested in when choosing a new computer.

               (1: strongly disagree – 7: strongly agree)

     Price          Price value

     Software       Compatibility with user's OS

     Aesthetics      Design value

     Brand         Brand value

Using the data (price, software, design, brand preference) obtained from a survey of 16 people, a “Data matrix” is formed

and the PCA is conducted using the Sage code given below. This data comes from the following open source. 

[Source]  http://yatani.jp/teaching/doku.php?id=hcistats:PCA 

# Hence, from here it can be understood that PC1 and PC2 retain about 85% of the original data variance.                                                  ■

# In this case, the original data was four-dimensional, but even if we reduced it to two-dimensional and analyzed, it also retains about 85% of

the original data's properties. So, in general, they are useful for decision-making. It means that we can cut the time in half, or at least more than a quarter.

We got such a result because we reduced the 4 dimension problem to a 2 the dimension problem. From this simple example,

one can easily envision the benefit of large dimensional reduction. For example, if we are able to reduce the data of dimension 1,000,000-

to a data of dimension 1,000, then we can significantly reduce the amount of economic costs and computing time.

Through the use of this theory and computer programming code, we can immediately analyze the result.

# For the principal components' eigenvalue below, we can see the process of deciding how many principal components to select

when we reduce the dimension of the data using the following line plot. Eigenvalues are sorted in the order of magnitude from the largest component

to the component to the left of the “elbow point”, usually where the slope is bent. Therefore, even if we lose about 15% of the information,

we can reduce the dimension 2 by selecting only PC1 and PC2. If we look at these figures, we can see it is enough to have two axes

to understand about 85% of the overall distribution. More details can be found in http://math1.skku.ac.kr/home/pub/212/. 

◩ Open Problem 2

Take a data matrix from sources related to your major, then use the code above to apply a Principal Component Analysis (PCA)

algorithm to this matrix, and then, post the results on the QnA Board for discussion. This will help you to understand the topic.

*12.5 PCA and Covariance matrix 

The principal component analysis is a technique that converts data from high-dimensional space to low-dimensional space.

However, the information about the distribution of the raw (original) data is also contained in the covariance matrix.

So, there is a very close relationship between principal components analysis and covariance matrices. This is another reason that

motivates us to learned Linear Algebra. To do principal component analysis, we need to be able to apply SVD on the covariance matrix.

From now on, we assume that we always start with a mean-centered data matrix , and we create a covariance matrix

based on the given data, and since this covariance matrix is a symmetric matrix, it is also diagonalizable,

which means that its eigenvalues are always real numbers.

The goal of the principal component analysis is to "Find the smallest number of new variables" that can "preserve the information

from the covariance matrix as much as possible". Our goal is to use this method to reduce the rank to (MAKE) a much smaller size () matrix.

Thus, the covariance matrix can be expressed with the orthogonal matrix used in SVD. [rank-p reduction, dimension reduction]

Let's have a SVD of .

Then we have

If we look closely at this relationship, we will see that it is like =, which means the eigenvalue-eigenvector relation. That is,

         , that menas ().

Now is an eigenvalue of , and is an eigenvector of corresponding to . This means the variance of the -th PC,

and means the th principal axis.

☞ Note  eigenvalue-eigenvector relation: http://matrix.skku.ac.kr/math4ai/part1/

◩ Open Problem 3

Discuss what you understand on the process of dimension reduction by PC’s on the covariance matrix.

*12.6 PCA and Linear Regression

In linear regression, and were determined to minimize the distance between the data and the computed points from

(i.e., distance on -axis) (left figure). But in PCA, and were determined to minimize the perpendicular distance between the data

and (right figure). That is, the straight line obtained using principal component analysis is closer to the data.

The figure below shows the straight-line obtained by linear regression and principal component analysis together.

(Because principal component analysis is sensitive to the scale of the data, centering and normalization should be assumed.

Refer to the relevant literature for details.)

                    ■

◩ Open Problem 4

Discuss what you understand about the similarity and difference between the least squares line and the linear regression.

 [Lecture on PCA]    https://youtu.be/ukIttphmM_4 

Copyright @ 2021 SKKU Matrix Lab. All rights reserved.
Made by Manager: Prof. Sang-Gu Lee and Dr. Jae Hwa Lee