Transcript Appendix_A

240-650
Principles of Pattern Recognition
Montri Karnjanadecha
[email protected]
http://fivedots.coe.psu.ac.th/~montri
240-572: Appendix A: Mathematical Foundations
1
Appendix A
Mathematical Foundations
240-572: Appendix A: Mathematical Foundations
2
Linear Algebra
•
•
•
•
•
•
•
Notation and Preliminaries
Inner Product
Outer Product
Derivatives of Matrices
Determinant and Trace
Matrix Inversion
Eigenvalues and Eigenvectors
240-572: Appendix A: Mathematical Foundations
3
Notation and Preliminaries
• A d-dimensional column vector x and its
transpose xt can be written as
 x1 
 
 x2 
x . 
 
 . 
x 
 d
and x t  x1
240-572: Appendix A: Mathematical Foundations
x2 . . xd 
4
Inner Product
• The inner product of two vectors having the
same dimensionality will be denoted as xty
and yields a scalar:
d
x t y   xi yi  y t x
i 1
240-572: Appendix A: Mathematical Foundations
5
Euclidian Norm (Length of vector)
x  xx
t
• We call a vector normalized if ||x|| = 1
• The angle  between two vectors
t
xy
cos  
x y
240-572: Appendix A: Mathematical Foundations
6
Cauchy-Schwarz Inequality
• If xty = 0 then the vectors are orthogonal
• If ||xty|| = ||x||||y| then the vectors are
colinear.
xy  x y
t
240-572: Appendix A: Mathematical Foundations
7
Linear Independence
• A set of vectors {x1, x2, x3, …, xn} is linearly
independent if no vector in the set can be
written as a linear combination of any of the
others.
• A set of d L.I. vectors spans a d-dimensional
vector space, i.e. any vector in that space can
be written as a linear combination of such
spanning vectors.
240-572: Appendix A: Mathematical Foundations
8
Outer Product
• The outer product of 2 vectors yields a matrix
 x1 
 
 x2 
t
M  xy    y1
:
 
x 
 n
y2
 x1 y1

 x2 y1
... ym    .

 .
x y
 n 1
240-572: Appendix A: Mathematical Foundations
x1 y2
.
.
.
.
.
.
.
.
.
. x1 ym 

.
. 
.
. 

.
. 
. xn ym 
9
Determinant and Trace
• Determinant of a matrix is a scalar
• It reveals properties of the matrix
• If columns are considered as vectors, and if
these vector are not L.I. then the determinant
vanishes.
• Trace is the sum of the matrix’s diagonal
elements
d
tr M    mii
i 1
240-572: Appendix A: Mathematical Foundations
10
Eigenvectors and Eigenvalues
• A very important class of linear equations is
of the form
Mx  x
or
M  Ix  0
for scalar 
• The solution vector x=ei and corresponding
scalar   i are called the eigenvector and
associated eigenvalue, respectively
• Eigenvalues can be obtained by solving the
characteristic equation: detM  I   0
240-572: Appendix A: Mathematical Foundations
11
Example
 3 1 
• Let M  


2

1


find eigenvalues and associated eigenvectors
Characteristic Eqn:
  3  
1 
0
det 



2

1




 3    1     2  0
2  4  5
240-572: Appendix A: Mathematical Foundations
0
12
Example (cont’d)
Solution:
  2  j
Eigenvalues are:
1  2  j,
2  2  j
Each eigenvector can be found by substituting
each eigenvalue into the equation Mx  x
then solving for x1 in term of x2 (or vice
versa)
240-572: Appendix A: Mathematical Foundations
13
Example (cont’d)
• The eigenvectors associated with both
eigenvalues are:
e1 :
 1
1 

e2 :
 1 
1  j


240-572: Appendix A: Mathematical Foundations

j 
14
Trace and Determinant
• Trace = sum of eigenvalues
• Determinant = product of eigenvalues
d
trM    i
i 1
d
M   i
i 1
240-572: Appendix A: Mathematical Foundations
15
Probability Theory
• Let x be a discrete RV that can assume any of
the finite number of m of different values in
the set X = {v1, v2, …, vm}. We denote pi the
probability that x assumes the value vi :
pi = Pr[x=vi], i = 1..m
• pi must satisfy 2 conditions
pi  0
240-572: Appendix A: Mathematical Foundations
m
and
p
i 1
i
1
16
Probability Mass Function
• Sometimes it is more convenient to express
the set of probabilities {p1, p2, …, pm} in
terms of the probability mass function P(x),
which must satisfy the following conditions:
Px   0
m
and
 Px   1
i 1
For Discrete x
240-572: Appendix A: Mathematical Foundations
17
Expected Value
• The expected value, mean or average of the
random variable x is defined by
 x     xPx   v p
m
xX
i 1
i
i
• If f(x) is any function of x, the expected value
of f is defined by
  f ( x)   f ( x) P x 
xX
240-572: Appendix A: Mathematical Foundations
18
Second Moment and Variance
• Second moment
 x    x Px
2
2
xX
• Variance
Varx   2 
 ( x   )    ( x   ) Px
2
2
xX
• Where  is the standard deviation of x
240-572: Appendix A: Mathematical Foundations
19
Variance and Standard Deviation
• Variance can be viewed as the moment of
inertia of the probability mass function. The
variance is never negative.
• Standard deviation tells us how far values of
x are likely to depart from the mean.
240-572: Appendix A: Mathematical Foundations
20
Pairs of Discrete Random Variables

• Joint probability pij  Pr x  vi , y  w j

• Joint probability mass function Px, y 
• Marginal distributions
Px ( x)   P( x, y )
yY
Py ( y )   P( x, y )
xX
240-572: Appendix A: Mathematical Foundations
21
Statistical Independence
• Variables x and y are said to be statistically
independent if and only if
P x, y   Px  x Py  y 
• Knowing the value of x did not give any
knowledge about the possible values of y
240-572: Appendix A: Mathematical Foundations
22
Expected Values of Functions of Two
Variables
• The expected value of a function f(x,y) of two
random variables x and y is defined by
240-572: Appendix A: Mathematical Foundations
23
Means and Variances
240-572: Appendix A: Mathematical Foundations
24
Covariance
• Using vector notation, the notations of mean
and covariance become
 x   xPx
 
Σ   x  μ x  μ  
μ
x XY
t
240-572: Appendix A: Mathematical Foundations
25
Uncorrelated
• The covariance is one measure of the degree
of statistical dependence between x and y.
• If x and y are statistically independent then
 xy  0
and The variables x and y are said to be
uncorrelated
240-572: Appendix A: Mathematical Foundations
26
Conditional Probability
• conditional probability of x given y
• In terms of mass functions
240-572: Appendix A: Mathematical Foundations
27
The Law of Total Probability
• If an event A can occur in m different ways,
A1, A2, …, Am, and if these m subevents are
mutually exclusive then the probability of A
occurring is the sum of the probabilities of
the subevents Ai.
240-572: Appendix A: Mathematical Foundations
28
Bayes Rule
P( y | x) P( x)
Px | y  
xX P( y | x) P( x)
• Likelihood = P(y|x)
• Prior probability = P(x)
X = cause
Y = effect
• Posterior distribution P(x|y)
240-572: Appendix A: Mathematical Foundations
29
Normal Distributions
1
1/ 2 (( x   ) 2 /  2 )
p( x) 
e
2 
240-572: Appendix A: Mathematical Foundations
30