Principal Component Analysis (PCA)

Learning Representations.
Dimensionality Reduction.
 Big & High-Dimensional Data
• High-Dimensions = Lot of Features

Document classification Features per

document =
thousands of words/unigrams
millions of bigrams, contextual
information

Surveys - Netflix
480189 users x 17770 movies
 Big & High-Dimensional Data
• High-Dimensions = Lot of Features

MEG Brain Imaging

120 locations x 500 time points
x 20 objects

Or any high-dimensional image data

 Continuous Latent Variables
• Explore models in which some, or all of
the latent variables are continuous
• Motivation is in many data sets
– dimensionality of the original data space is
very high
– the data points all lie close to a manifold of
much lower dimensionality

4
 Example
• data set: 100x100 pixel grey-level images
• dimensionality of the original data space
is 100x100
• digit 3 is embedded, the location and
orientation of the digit is varied at random
• 3 degrees of freedom of variability
– vertical translation
– horizontal translation
– rotation

5
• Principal components analysis (PCA; also called
the Karhunen-Loeve, or K-L, method) searches for
k n-dimensional orthogonal vectors that can best
be used to represent the data, where k < n.
• The original data are thus projected onto a much
smaller space, resulting in dimensionality
reduction.
• Unlike attribute subset selection, which reduces
the attribute set size by retaining a subset of the
initial set of attributes, PCA

“combines” theessence of attributesby

creating an alternative, smaller set of
variables.
• The initial data can then be projected
onto this smaller set.
• PCA often reveals relationships that
were not previously suspected and
thereby allows interpretations that
would not ordinarily result.
 PCA-maximum
variance
formulation
• PCA can be defined as
– the orthogonal projection of the data onto a
lower dimensional linear space-principal
subspace
– s.t. the variance of the projected data is
maximized
goal

8
PCA-maximum
variance
formulation

red dots: data points

purple line: principal subspace 9
green dots: projected points
 Procedure
• Normalization - Each attribute falls within
the same range. Attributes with large
domains will not dominate attributes with
smaller domains.
• Computes k orthonormal vectors provide a
basis for the normalized input data.
• These are unit vectors that each point in a
direction perpendicular to the others.
• These vectors are referred to as the
principal components.
• The principal components are sorted in
order of decreasing “significance” or
strength.
• The principal components essentially serve
as a new set of axes for the data, providing
important information about variance.
• Components are arranged in sorted order
– descending
• The data size can be reduced by eliminating
the weaker components, that is, those with
low variance.
 PCA-maximum
variance
formulation
• data set: {xn}n=1,2,…N
• xn: D dimensions
• goal:
– project the data onto a space having
dimensionality M < D
– maximize the variance of the projected
data

12
 PCA-maximum
variance
•M=1 formulation
• D-dimension unit vector u1: the
direction
u1T1u
Tx
• xn uproject =1
1n
• mean of the projected data:
• variance of the projected data:

13
covariance
matrix
 PCA-maximum variance formulation
• goal: maximize variance of projected data
• maximize variance u 1TSu
1 1 with respect to u
• introduce a Lagrange multiplier λ1

□
– a constrained maximization to prevent |u1|| ∞
– constraint comes from u T1 u1 =1
• set derivative equal to zero
u1: an eigenvector of S
max variance: largest λ1
u1
14
 Application
• PCA can be applied to ordered and
unordered attributes, and can handle
sparse data and skewed data
• Multidimensional data of more than two
dimensions can be handled by reducing the
problem to two dimensions
• Principal components may be used as
inputs to multiple regression and cluster
analysis
 PCA-example
Step 1: get data set
D=2 N=10

16
 PCA-example
Step 2: subtract the mean

17
 PCA-example
Step 3: calculate the covariance matrix S
S: 2x2

18
 PCA-example
• Step 4: Calculate the eigenvectors and
eigenvalues of the covariance matrix S

• the eigenvector with the highest eigenvalue is

the first principle component of the data set

19
PCA-example
• two eigenvectors
• go through the
middle of the
points, like drawing
a line of best fit
• extract lines to
characterize the
data

20
 PCA-example
• In general, once eigenvectors are found the
next step is to order them by eigenvalues,
highest to lowest this gives us the PCs in
order of significance decide to ignore the less
significant components here is where the
notion of data compression and reduced
dimensionality comes

21
 PCA-example
• Step 5: derive the new data set
newDataT=eigenvectorsT x
originalDataAdjustT

originalDataAdjustT=

newData: 10x1 22
 PCA-example
• newData

23
PCA-example

• newData: 10x2

2
4
 PCA-example
• Step 6: get back old data data
compression

• took all the eigenvectors in

transformation, get exactly the original
data back
• otherwise, lose some information

25
 PCA-example
• newDataT=eigenvectorsT x
originalDataAdjustT
• newDataT=eigenvectors-1 x
originalDataAdjustT
take all the eigenvectors
•
inverse of the eigenvectors
•
matrix is equal to the
transpose of it
unit vectors
•

26
PCA-example
• newData: 10x1

27
 Learning Representations
PCA, Kernel PCA, ICA: Powerful unsupervised learning
techniques for extracting hidden (potentially lower
dimensional) structure from high dimensional datasets.
Useful for:
• Visualization
• More efficient use of resources (e.g., time, memory,
communication)

• Statistical: fewer dimensions □ better generalization

• Noise removal (improving data quality)
• Further processing by machine learning algorithms
 Principal Component Analysis (PCA)

What is PCA: Unsupervised technique for extracting

variance structure from high dimensional datasets.

• PCAis an orthogonal projection or transformationof the data into a

(possibly lower dimensional) subspace so that the variance of the
projected data is maximized.
 Principal Component Analysis (PCA)
If we rotate data, again only one
Intrinsically lower dimensional than the coordinate is more important.
dimension of the ambient space.

Only one relevant feature Both features are relevant

Question: Can we transform the features so that we only need to

preserve one latent feature?
 Principal Component Analysis (PCA)

In case where data lies on or near a low d-dimensional linear

subspace, axes of this subspace are an effective representation of the
data.

Identifying the axes is known as Principal Components Analysis, and

can be obtained by using classic matrix computation tools (Eigen or
Singular Value Decomposition).
 Principal Component Analysis (PCA)
Principal Components (PC) are orthogonal directions
that capture most of the variance in the data.
• First PC – direction of greatest variability in data.

• Projection of data points along first PC discriminates data

st
most along any one direction

PC
1
(pts are the most spread out when we project the data on that direction
compared to any other directions).

Quick reminder:

v
 Principal Component Analysis (PCA)
Principal Components (PC) are orthogonal directions
that capture most of the variance in the data.
• 1st PC – direction of greatest variability in data.

2
nd
PC

st
PC
1
• 2nd PC – Next orthogonal (uncorrelated) direction of greatest
variability
(remove all variability in first direction, then find next direction of
greatest variability)

• And so on …
 Kernel
• Kernel function

mapping of x into a feature space

• inner product in feature space

• feature space M ≥ input space N
• feature space mapping is implicit 34
 PCA-linear

• maximum variance formulation

– the orthogonal projection of the data onto
a lower dimensional linear space
– s.t. the variance of the projected data is
maximized linear

• minimum error formulation

– the linear projection
– minimizes the average projection
distance 35
 Kernel PCA
• data set: {xn}n=1,2,…N
• xn: D dimensions
• assume: the mean has been subtracted
from xn (zero mean)

• PCs are defined by the eigenvectors ui of S

i=1,…,D

36
 Kernel PCA
• a nonlinear transformation into an M-
dimensional feature space
• xn project
• perform standard PCA in the feature
space
• implicitly defines a nonlinear PC in the
original data space

37
 original data space feature space

green lines: linear projection onto the first PC

□ nonlinear projection in the original data
space 38
 Kernel PCA
• assume: the projected data has zero
mea
n MxM

i=1,…,M

give , vi is a linear combination of

n

39
 Kernel PCA
express this in terms of kernel function

in matrix i=1,…,N ai: column vector

notation

the solutions of these two eigenvector equations differ only

by eigenvectors of K having zero eigenvalues

40
 Kernel PCA
• normalization condition for ai

41
 K e r n e l P C
• in feature sp a ce : w h at i s
Athe projected data points after PCA

42
 Kernel PCA
• original data space
– dimensionality: D
– D eigenvectors
– at most D linear PCs
• feature space
– dimensionality: MM>>D (even infinite)
– M eigenvectors
– a number of nonlinear PCs then can exceed D
• the number of nonzero eigenvalues can
not exceed N
43
 Kernel PCA

• assume: the projected data has zero

mean
• nonzero mean
– cannot simply compute and then subtract
off the mean
– avoid working directly in feature space
• formulate the algorithm purely in terms
of kernel function
44
Kernel PCA

Gram
matri
in matrix
x
notation

1N: NxN matrix 1/N 45

 Kernel PCA
• linear kernel: standard
PCA
• Gaussian kernel:

• example: kernel PCA

46
47
• contours:
K e r n e l P C A
lin es a l on g w h ic h the
projection onto the corresponding PC is
constant

48
 Kernel PCA
disadvantage:
• determine the eigenvectors of , NxN
• for large data sets, approximations are
used

49