50 • Machine Learning -------,-...--...

-_J~------- ---------
~ ' . . . he d the following row operations are
To facilitate the npplication of Gaussian chmmation met J '
applied:
1. Swapping the rows
. Iymg
2. M u Itip . J' ,1 1•0 \ "v l,y ' i const,rnt
. or l i'1v1urng •
.
f , ther row to 1t
. 01. su
3. Replacing a row by ,1dd111g " lJ t.1,1cting ,1 multiple o anu

These concepts ,m' ilh1str,1h·d in Ex,unph· 2·8·

. c· tuss,•..,n Elimination method.

Example 2.8: Solve till' following Sl'l of l'qt1,1 t'ions· usmg J< <•

21'1 I 4.\'2 = 6

4x, t 3x2 cc 7

Solution: Rewrite this in matrix form(: f!ll:wiJ

-(24 34II 76JR 1
= !S_
2

.. d. th by 2· There are no general guidelines of

1 th tr f Ormation by d1v1 mg e row. 1 ch 1 f rm The operator - means
App y e ans
row operations other than reducing the given matnx to row e . e on o .
reducing to. The above matrix can further be reduced as follows.

-(1 2I 3JR
4317 2
= R - 4R
2 1

-( 1 2 I 3 JR 2
= R1_52
0 -5 I -5

- (ol 21 J RI
3] = RI - 2R2

-(~ ~ I ;J
Therefore, in the reduced echelon form, it can be observed that:
.t2 = 1
x1 = 1

2.8.2 Matrix Decompositions

1t is often nC'cessary to fl'<lun· a m,1trix to its constituent parts so that complex matrix operations
can be• performed. ThPS(' nwthods an' also known as matrix factorization methods.
The most popular matrix <.kcomp1.)sition is Cc11led eigen decomposition. It is a way of reducing
the matrix into eigen valur>s and t•igt•n vectors.
Then, the matrix A can be decomposed as:
A=QAQT (2.23)
where, Q is the matrix of rigen vectors, A is the diagonal matrix and Qr is the transpose of matrix Q.
 -~ ~
/4~\, OP j°tr.'>.
/t.,'~ .) ------- ""½
- - - - - - - - - - - - - ~ ~ L.!J_t;_r.~~~~(t~\- Understanding Data • S1
-0
LCI oecomposition ,.~ .../ ~
. . . .. ~ \\o···· Q}¢ ~
one of the ~lffiplest matrix decompos1hc 1~ , Jt!-«ticomJ~oj~}m wh ~~e;he matrix A can be decom-
osed matrices: ri ~~'t
p • :-(i~t ~
Here, Lis the lower triangular matrix ,1 11 ~ L'i r~ up l,ri:t;liiar m;itrix. The decomposition
can be done using Gaussian climin,1tion nwth~c5~~'.di~~~g~d in the previous section. First,
an identity matrix is augmented to the given matrix. Tlwn, row operations and Gaussian elimination
is applied to reduce the given matrix to g<'l matrices r, and LI
Example 2.9 illustrates the application of Gaussian elimmation to get LU.

Example 2.9: Find LU decomposition of the given matrix:

A= 3 3 2
1 2 4]
342 (
Solution: · First, augment an identity matrix and apply Gaussian elimination. The steps are as
shown in:

01 o 0 3 32 4]
1 0][1 2 !Initial Matrix I

l
[
001 342

13 o
1 0][1 4
2 -10
0 0 -3
[

l
001 3 4 2

31 o
1 0][1 4
2 -10
0 0 -3
[
3 0 1 0 - 2 -10

l 0 0 l 2 4
3 l 0 0 -3 -10
2 - 10
1 0 0 -
3
3 3
Now it can be observed that the first matrix is L as it is the lower triangular matrix whose
values a;e the determiners used in the reduction of equations above such as 3, 3 and 2/3.
The second matrix is u, the upper triangular matrix whose values are the values of the reduced
matrix because of Gaussian elimination.

l 0 0 l 2 4
L= 'I
1 0 and U =
.::, 0 -3 -10
3 ~ l 0 0 - 10
3 3
 Component number
Figure 2.15: Scree Plot
From Figul'e 2.15, OnP can infer the relevance of the attributes. The scree plot indicates that
the first attribute is more important than all other attributes .
•
Example 2.12:
Let the data points be ( ~) and GJApply PCA and find the transformed data.
Again, apply the inverse and prove that PCA works.
Solution: One can con1bine two vectors into a matrix as follows:

l
The mean vector can be computed as Eq. (2.53) as follows:

2+
-2- - 1.5
· µ=
[
6 ; 7 - ( 6.5 J
 66 • Machine Learning ---------- ---------- ---=--..
As part of PCA, the mean must be subtrt1ctcd from the data to get the adjuSled data:

,\ I c (62-- 6.5 0.5)

[Link] : (- 0.5
·'2= (7 -
1.5) = (-0
I- <,.5 .SJ
0.5
, t t,1 t·•1 v ct• ·t<>rs· · 'J'hc •
··
One can tmd ·
tlw covan,Hll'l' tor t Iwst' · covariance can be obtain••d
.. using

Eq. (2.54): . .5J

-( O _ - ( 0.25 - 0.25J
111 1
0.5 (o.s o.s) . ' 025
025 .

- [Link] ( 0.25 - 0.25J

"'2 = ( 0.5 (-0.5 0.5) = - 0.25 0.25

The final co\·ariance matrix is obtained by adding these two matrices as:

C =( 0.5
-0.5
-[Link]
0.5

The eigenvalues and eigenvectors of matrix C can be obtained (left as an exercise) as ''-I= 1,
A, = 0. The eigen vectors are ( - : and J GJThe matrix A can be obtained b}' packing lhe

eigen vector of these eigen values (after sorting it) of matrix C. For this problem, A = (-I 1
)-

The transpose of A, Ar=(-: :Jis also the same matrix as it is an orthogonal matrix. The ~a~
can be normalized by diving each elements of the vector, by the norm of the vector to get:

1 1
A= - ✓2 ✓2
1 1
Ji. Ji.
One can check that the PCA matrix A is orthogonal. A matrix is orthogonal is A 1 = A and
M -1=1.
1 1 1 1
AA r = - Ji. Ji. - ✓2 Ji.
1 1 1 1
Ji. Ji_ Ji. Ji.
=(~ ~]
The transformed matrix y using Eq. (2.55) is given as:
y=Ax(x-m)
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Understanding Data • 67

Recollect that (x-m) is the adjusted matrix.

1 1
- ✓2 ~f2 -( 0.5 -0.5)
y = A(x - m) = 1 1 -0.5 0.5
✓2 ✓2

= -
1 1[ 21- 21]
✓2 ✓2 (tor convenience 0.5 = _!_)
1 1 1 1 2
✓2 ✓2 -2 2

~[-ri ~]
One can check the original matrix can be retrieved from this matrix as:

r__ ~j'rl-
{(AY x y} + m

x =Ary+- m ~
[
l
✓2 ✓2
_1__1_
1
✓2
O
Jzj +l
1,

O
([Link])
6.5
✓2 ✓2

-l 2 - 2J
( 1 1)
+ (1.s1 _ (2 11
- 1
--
1
-
l6.s) - l6 7J
2 2
Therefore, one can infer the original is obtained without any loss of information.

2.10.4 Linear Dis~inant Analysis

r DJscnminant Anal Sis LDA is also a f a
7
 4. Arrange the square root of the eigenvalues in diagonal. This matrix i5 di agr>na)
. . . . r11atr
5. Fmd e1gen values and eigenvectors for A TA. Fmd the e1gen value and pack the f' . '
as a matrix called V. -igen ,,
Thus, A = usvr. Here, LI and V are orthogonal matrices. The columns of U and v
ng _smgu 1ar values, respectively. SVD is useful in compression,
· ht · · a re left ar
as one can decide to retai
certam component instead of the origirrnl matrix A as: n {Jttly
n
n,I L " rAsk v 1,
A I
Based on the choke of n'fl'nfion, the compression can be controlled .
•
Example 2. 13: Find SVO of tJw m,1tr ix:

Solution: TJ ,c tirSf
· step is to compute:

AA r - ( 12J( 14J = ( 225 9722J

4 9 2 9
The eigen ,·alue and e·
this matrix are 0 0098 d igen vector of this matrix can be calculated to get U. The eigen , I
· · an 101.9902. ·a ues
 - - - - - - - - - - - - - - - - - - - - - - - - Understanding Data • 69
The eige· n vectors of this matrix me:

II -
0.2268)
I ( I

u = ( tl.'1086)
2 J
These vectors are t)<) . . . i .
· rm,1 1I/.Cl to get tlw Vl'c tors n•spc•c·t,v<'ly (is:

II -
0.2212)
I - ( 0.9752

u - ( 0.9752)
l 0.2212
The matrix U can be obt · d b .
.:unc y concatenating the above vector as:

U = [u , u = (0.2212 0.9752]
2
I ] 0.9752 0.2212

The matrix V can b e obt ame

· db y finding
. ATA. It is (17 38] . The eigenvalues are 0.0098 and
101.9902. The eigenvectors can be found as follows: 38 85

v1 =l( 0.4471
1
) when A = 101.99

( -2.2361
v2 =l ) when A = 0.0098
1
The above can be normalized as follows:

V = (0.4082]
1
0.9129

V = (-0.9129]
2
0.4082
The matrix V can be obtained by concatenating the above vector as:
0.4081 -0.9129]
V- V V -
- [ 1 2] - ( 0.9129 0.4082

The matrix S can be found as the diagonal matrix as:

S == ( ✓101.9902 J= (10.099
0 O J
o Jo.0098 o 0.099

Therefore, the matrix decomposition A= U svr is complete.

The main advantage of SYD is compression. A matrix, say an image, can be decomposed and selec-
tively only certain components can be retained by making all other elements zero. This reduces
the contents of image while retaining the quality of the image. SVD is useful in data reduction too.