Principal Component Analysis Neural Networks

Principal Component Analysis (PCA)
Independent Component Analysis (ICA)



Asst. Prof.
Dr. Mohammed Najm Abdullah

Application domains of ICA
Blind source separation
Image denoising
Medical signal processing – fMRI, ECG, EEG
Modelling of the hippocampus and visual cortex
Feature extraction, face recognition
Compression, redundancy reduction
Watermarking
Clustering
Time series analysis (stock market, microarray data)
Topic extraction
Econometrics: Finding hidden factors in financial data

Recovered signals
ICA Solution and Applicability
ICA is a statistical method, the goal of which is to decompose given multivariate data into a linear sum of statistically independent components.
For example, given two-dimensional vector , x = [ x1 x2 ] T , ICA aims at finding the following decomposition
where a1, a2 are basis vectors and s1, s2 are basis coefficients.

Constraint: Basis coefficients s1 and s2 are statistically independent.
BSS
If we knew the mixing parameters aij then we would just need to solve a linear system of equations.
We know neither aij nor si.
ICA was initially developed to deal with problems closely related to the cocktail party problem
Later it became evident that ICA has many other applications
e.g. from electrical recordings of brain activity from different locations of the scalp (EEG signals) recover underlying components of brain activity

Problem: Determine the source signals s, given only the mixtures x.
This is recorded by the microphones: a linear mixture of the sources
xi(t) = ai1*s1(t) + ai2*s2(t) + ai3*s3(t) + ai4*s4(t)
The ICA model




s1
s2
s3
s4
x1
x2
x3
x4
a11
a12
a13
a14
xi(t) = ai1*s1(t) +
ai2*s2(t) +
ai3*s3(t) +
ai4*s4(t)
Here, i=1:4.
In vector-matrix notation, and dropping index t, this is
x = A * s
Original signals (hidden sources) s1(t), s2(t), s3(t), s4(t), t=1:T
Source Separation Using ICA
W11
W21
W12
W22
+
+
Microphone 1
Microphone 2
Separation 1
Separation 2





Cocktail party or Blind Source Separation (BSS) problem
Ill posed problem, unless assumptions are made!
Most common assumption is that source signals are statistically independent. This means knowing value of one of them gives no information about the other.
Methods based on this assumption are called Independent Component Analysis methods
statistical techniques for decomposing a complex data set into independent parts.
It can be shown that under some reasonable conditions, if the ICA assumption holds, then the source signals can be recovered up to permutation and scaling.




BSS and ICA
Image denoising
Wiener filtering
ICA filtering
Noisy image
Original image
Principal Components Analysis (PCA)
Principle
Linear projection method to reduce the number of parameters
Transfer a set of correlated variables into a new set of uncorrelated variables
Map the data into a space of lower dimensionality
Form of unsupervised learning

Properties
It can be viewed as a rotation of the existing axes to new positions in the space defined by original variables
New axes are orthogonal and represent the directions with maximum variability


Feature Extraction in ECG data
(Raw Data)
Principal Components
First principal component is the direction of greatest variability (covariance) in the data
Second is the next orthogonal (uncorrelated) direction of greatest variability
So first remove all the variability along the first component, and then find the next direction of greatest variability
And so on …
Feature Extraction in ECG data
(flexible ICA)
Feature Extraction in ECG data (Extended ICA)
Feature Extraction in ECG data
(PCA)
Cocktail-party Problem
Multiple sound sources in room (independent)
Multiple sensors receiving signals which are mixture of original signals
Estimate original source signals from mixture of received signals
Can be viewed as Blind-Source Separation as mixing parameters are not known
Approaches to ICA
Unsupervised Learning
Factorial coding (Minimum entropy coding, Redundancy reduction)
Maximum likelihood learning
Nonlinear information maximization (entropy maximization)
Negentropy maximization
Bayesian learning

Statistical Signal Processing
Higher-order moments or cumulants
Joint approximate diagonalization
Maximum likelihood estimation
Eigenvectors of a Correlation Matrix
Dimensionality Reduction
Can ignore the components of lesser significance.










You do lose some information, but if the eigenvalues are small, you don't lose much
n dimensions in original data
calculate n eigenvectors and eigenvalues
choose only the first p eigenvectors, based on their eigenvalues
final data set has only p dimensions
How Many PCs?
For n original dimensions, correlation matrix is nxn, and has up to n eigenvectors. So n PCs.
Where does dimensionality reduction come from?
PCs, Variance and Least-Squares
The first PC retains the greatest amount of variation in the sample
The kth PC retains the kth greatest fraction of the variation in the sample
The kth largest eigenvalue of the correlation matrix C is the variance in the sample along the kth PC


The least-squares view: PCs are a series of linear least squares fits to a sample, each orthogonal to all previous ones







Computing the Components
Similarly for the next axis, etc.
So, the new axes are the eigenvectors of the matrix of correlations of the original variables, which captures the similarities of the original variables based on how data samples project to them
Geometrically: centering followed by rotation
Linear transformation
Singular Value Decomposition
The first root is called the prinicipal eigenvalue which has an associated orthonormal (uTu = 1) eigenvector u
Subsequent roots are ordered such that λ1> λ2 >… > λM with rank(D) non-zero values.
Eigenvectors form an orthonormal basis i.e. uiTuj = δij
The eigenvalue decomposition of xxT = UΣUT
where U = [u1, u2, …, uM] and Σ = diag[λ 1, λ 2, …, λ M]
Similarly the eigenvalue decomposition of xTx = VΣVT
The SVD is closely related to the above x=U Σ1/2 VT
The left eigenvectors U, right eigenvectors V,
singular values = square root of eigenvalues.
Independent Component Analysis (ICA)
PCA
(orthogonal coordinate)
ICA
(non-orthogonal coordinate)
Computing the Components
E((u.x)2) = E ((u.x) (u.x)T) = E (u.x.x T.uT)
The matrix C = x.xT contains the correlations (similarities) of the original axes based on how the data values project onto them
So we are looking for w that maximizes uCuT, subject to u being unit-length
It is maximized when w is the principal eigenvector of the matrix C, in which case
uCuT = uluT = l if u is unit-length, where l is the principal eigenvalue of the correlation matrix C
The eigenvalue denotes the amount of variability captured along that dimension
Computing the Components
Data points are vectors in a multidimensional space
Projection of vector x onto an axis (dimension) u is u.x
Direction of greatest variability is that in which the average square of the projection is greatest
I.e. u such that E((u.x)2) over all x is maximized
(we subtract the mean along each dimension, and center the original axis system at the centroid of all data points, for simplicity)
This direction of u is the direction of the first Principal Component







PCA's Relation to Neural Networks: Hebbian-Based
Maximum Eigenfilter
Why the Eigenvectors?
Maximise uTxxTu s.t uTu = 1
Construct Langrangian uTxxTu – λuTu
Vector of partial derivatives set to zero
xxTu – λu = (xxT – λI) u = 0
As u 0 then u must be an eigenvector of xxT with eigenvalue λ

Matrix Formulation of the Algorithm
Eigenfaces
Experiment and Results
Data used here are from the ORL database of faces. Facial images of 16 persons each with 10 views are used. - Training set contains 16×7 images.
- Test set contains 16×3 images.

First three eigenfaces :
Eigenfaces – Face Recognition
When properly weighted, eigenfaces can be summed together to create an approximate gray-scale rendering of a human face.
Remarkably few eigenvector terms are needed to give a fair likeness of most people's faces
Hence eigenfaces provide a means of applying data compression to faces for identification purposes.
Similarly, Expert Object Recognition in Video
PCA applications -Eigenfaces
the principal eigenface looks like a bland androgynous average human face
http://en.wikipedia.org/wiki/Image:Eigenfaces.png

PCA applications -Eigenfaces
To generate a set of eigenfaces:

Large set of digitized images of human faces is taken under the same lighting conditions.
The images are normalized to line up the eyes and mouths.
The eigenvectors of the covariance matrix of the statistical distribution of face image vectors are then extracted.
These eigenvectors are called eigenfaces.
PCA applications -Eigenfaces
Eigenfaces are
the eigenvectors of
the covariance matrix of
the probability distribution of
the vector space of
human faces
Eigenfaces are the 'standardized face ingredients' derived from the statistical analysis of many pictures of human faces
A human face may be considered to be a combination of these standard faces
35

37

36

40

39

Click to edit Master title style
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
6/7/2013

#
44

43

42

41

38

34
a_ji are parameters that depend on the distance of microphones from the sound sources.
9

8

7

6

5

10

11

12

14

13

Click to edit Master title style
Click to edit Master text styles
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
Click to edit Master text styles
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
6/7/2013

#
Click to edit Master title style
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
6/7/2013

#
Click to edit Master title style
Click to edit Master text styles
6/7/2013

#
Click to edit Master title style
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
6/7/2013

#
Click to edit Master title style
Click to edit Master subtitle style
6/7/2013

#
Click to edit Master title style
6/7/2013

#
6/7/2013

#
Click to edit Master title style
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
Click to edit Master text styles
6/7/2013

#
Click to edit Master title style
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
6/7/2013

#
Click to edit Master title style
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
6/7/2013

#
Click to edit Master title style

Click to edit Master text styles
6/7/2013

#
15

30

29

28

31

33

32

21

20

22

23

25


6/7/2013

Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level

#