模式识别 Pattern Recognition

Presentation on theme: "模式识别 Pattern Recognition"— Presentation transcript:

1 模式识别 Pattern Recognition
IPL 武汉大学电子信息学院 模式识别 Pattern Recognition 线性代数与概率统计基础 补充 材料

2 模式识别导论 行列式与线性方程组 矩阵 向量 矩阵的特征值与特征向量 二次型 多元随机变量的统计特征 多元随机变量协方差矩阵的性质
补充 材料 行列式与线性方程组 矩阵 向量 矩阵的特征值与特征向量 二次型 多元随机变量的统计特征 多元随机变量协方差矩阵的性质 二次型化为标准形 梯度（下降）法 线性代数与概率统计基础

3 行列式与线性方程组 补充 材料 行列式： 行列式的计算： 化为三角行列式计算： 按行（列）展开计算： 线性代数与概率统计基础

4 解线性方程组的克莱姆法则 对于线性方程组： 如果行列式 D=|aii|≠0，则方程组存在唯一解
补充 材料 对于线性方程组： 如果行列式 D=|aii|≠0，则方程组存在唯一解 齐次线性方程组(即b=0)，有非零解的充要条件是D=|aii|=0 线性代数与概率统计基础

5 矩阵 Matrix: 由m*n个数aij排列成的m行n列的数表：Am*n=[aij]m*n 方阵：m=n
补充 材料 Matrix: 由m*n个数aij排列成的m行n列的数表：Am*n=[aij]m*n 方阵：m=n 对角阵：∧=diag(a11,a22,…,ann) 单位阵：E= diag(1,1,…,1) 上三角阵与上三角阵 线性代数与概率统计基础

6 矩阵的运算 矩阵的乘法：C=AB 矩阵的转置：A=(aij), A’=AT=(aji) 对称方阵：A’=A， 即 aij= aji
补充 材料 矩阵的乘法：C=AB noc(A) = nor(B) noc(C) = noc(B) nor(C) = nor(A) 矩阵的转置：A=(aij), A’=AT=(aji) 对称方阵：A’=A， 即 aij= aji 方阵的行列式： 如果|A|≠0，A称为非奇异阵，否则为奇异阵 |A’|= |A|， |AB|= |A||B| 逆矩阵：如果AB=BA=E, 则称A可逆，B为A的逆 方阵A可逆可逆的充要条件： |A|≠0 线性代数与概率统计基础

7 分块矩阵及其运算 分块矩阵：用横线和竖线把矩阵分成若干小块，每个小块为一个矩阵，它可以作为一个元素参加运算。 分块对角阵：
补充 材料 分块矩阵：用横线和竖线把矩阵分成若干小块，每个小块为一个矩阵，它可以作为一个元素参加运算。 分块对角阵： |A|=|A11||A11|…|A11| 线性代数与概率统计基础

8 向量 n维向量：x=(x1,x2,…,xn)T 线性相关与线性无关：
补充 材料 n维向量：x=(x1,x2,…,xn)T 线性相关与线性无关： 设有n维向量组： x1, x2,…, xm，如果只有当k1= k2=…=km=0时，才能使下式成立，则称该向量组线性无关。否则为线性相关。 m个n维向量的矩阵表示：A=(a1, a2,…, am) n个n维向量：ai=(ai1,ai2,…,ain)T线性无关的充要条件是|A|≠0 线性代数与概率统计基础

9 向量(二) 如果向量组A = (a1, a2,…, am) = (b1, b2,…, bm)C = BC，称A可由向量组B线性表示。
补充 材料 如果向量组A = (a1, a2,…, am) = (b1, b2,…, bm)C = BC，称A可由向量组B线性表示。 rank(A)=nov(A的最大线性无关组) 向量的内积: 向量的模（范数/长度）： 两点的距离： 两向量的夹角： 线性代数与概率统计基础

10 向量(三) 两向量正交：(x,y)=0, cos(θ)=0 若非零的n维向量x1, x2,…, xm两两正交，则称为正交向量组。
补充 材料 两向量正交：(x,y)=0, cos(θ)=0 若非零的n维向量x1, x2,…, xm两两正交，则称为正交向量组。 正交向量组线性无关。 若n维向量y可由正交向量组x1, x2,…, xm线性表示，则： 线性代数与概率统计基础

11 矩阵的特征值与特征向量 方阵A的特征值λ与特征向量α: Aα=λα 方阵A的特征多项式：|A-λE| 方阵A的特征方程： |A-λE|=0
补充 材料 方阵A的特征值λ与特征向量α: Aα=λα 方阵A的特征多项式：|A-λE| 方阵A的特征方程： |A-λE|=0 特征方程的解λ为特征值，方程 (A-λE)x=0的非零解向量就是方阵A的属于特征值λ的特征向量。 如果存在可逆方阵P，使P-1AP=B，则称A与B相似，记作A~B。 相似关系具有反身、对称、传递性。 相似矩阵有相同的行列式，即|A|=|B| 相似矩阵有相同的特征多项式及特征值 线性代数与概率统计基础

12 相似矩阵 n阶方阵A与对角矩阵∧相似的充要条件是A有n个线性无关的特征向量。
补充 材料 n阶方阵A与对角矩阵∧相似的充要条件是A有n个线性无关的特征向量。 如果A~∧，即有 P-1AP= ∧=diag(d1,d2,…,dn)，则d1, d2, …, dn是A的n个特征值。 实对称矩阵： 特征值为实数 两个相异的特征值对应的特征向量正交 n阶实对称方阵A有n个线性无关的特征向量 n阶实对称方阵A与对角矩阵相似 线性代数与概率统计基础

13 正交矩阵 正交矩阵A，有AA’=E，即A-1=A’ 正交矩阵A的行(列)向量组为正交单位向量组，即：
补充 材料 正交矩阵A，有AA’=E，即A-1=A’ 正交矩阵A与B的乘积AB仍为正交矩阵 正交矩阵A的行列式|A|=1 正交矩阵A的行(列)向量组为正交单位向量组，即： 若A为实对称矩阵，则必存在正交矩阵P，使P-1AP=∧， ∧是以A的特征值为对角元素的对角矩阵。 线性代数与概率统计基础

14 二次型 二次齐次函数： 记x=(x1, x2, … xn)T，A=(aij)n*n ，则有：
补充 材料 二次齐次函数： 记x=(x1, x2, … xn)T，A=(aij)n*n ，则有： 二次型f与对称矩阵A存在一一对应：A为二次型f的矩阵， f为矩阵A的二次型。 线性代数与概率统计基础

15 标准二次型 补充 材料 A=∧时为标准二次型(只含平方项) 对于任何二次型： 总可找到正交变换将f化为标准形 线性代数与概率统计基础

16 正定二次型和正定矩阵 补充 材料 二次型f(x1, x2, …, xn)，如果对于任何 x12 + x22 +…+ xn2 ≠0，都有f > 0，则称f为正定二次型。其矩阵A为正定矩阵(A>0)。 n阶方阵A正定的充要条件是：A的n个特征值全为正的。 n阶方阵A，若存在可逆矩阵B，使A=B’B，则A为正定矩阵。 线性代数与概率统计基础

17 多元随机变量的统计特征 n维随机变量：x=[x1,x2,…,xn]T n维随机变量的（总体）均值： n维随机变量的（样本）均值：
补充 材料 n维随机变量：x=[x1,x2,…,xn]T n维随机变量的（总体）均值： n维随机变量的（样本）均值： n维随机变量的（总体）相关函数矩阵： n维随机变量的（样本）相关函数矩阵： n维随机变量的（总体）协方差矩阵： n维随机变量的（样本）协方差矩阵： 线性代数与概率统计基础

18 n维随机变量协方差矩阵的性质 n维随机变量协方差矩阵C是实对称矩阵 协方差矩阵C的特征值为实数 C有n个线性无关的特征向量
补充 材料 n维随机变量协方差矩阵C是实对称矩阵 协方差矩阵C的特征值为实数 C有n个线性无关的特征向量 存在正交矩阵U，使U-1CU= UTCU=∧， ∧是以C的特征值为对角元素的对角矩阵，U=[u1,u2,…,un]，C ui=λi ui 任何二次型总可找到正交变换化为标准形，即： 线性代数与概率统计基础

19 二次型化为标准形 补充 材料 线性代数与概率统计基础

20 梯度（下降）法 补充 材料 ak ak+1 ▽J(a) 线性代数与概率统计基础

21 梯度（下降）法 选择初始点a0，给定容许误差ε，设定学习率η。设k=0； 计算梯度▽J(ak)；
补充 材料 选择初始点a0，给定容许误差ε，设定学习率η。设k=0； 计算梯度▽J(ak)； 修改ak： ak+1 = ak -η▽J(ak) 计算J(ak+1)，并检验|J(ak+1)- J(ak)|<ε，若满足则转6 k=k+1，转2 输出结果，结束 线性代数与概率统计基础

22 概率统计相关定义 Random experiment Outcome Sample space Event
An experiment whose result is not certain in advance (e.g., throwing a die) Outcome The result of a random experiment Sample space The set of all possible outcomes (e.g., {1,2,3,4,5,6}) Event A subset of the sample space (e.g., obtain an odd number in the experiment of throwing a die = {1,3,5}) 线性代数与概率统计基础

23 概率直观定义 Intuitively, the probability of an event a could be defined as:
Assumes that all outcomes in the sample space are equally likely (Laplacian definition) 线性代数与概率统计基础

24 先验概率 This is the probability of an event prior to arrival of any evidence. P(Cavity)=0.1 means that “in the absence of any other information, there is a 10% chance that the patient is having a cavity”. 线性代数与概率统计基础

25 后验概率 This is the probability of an event given some evidence.
P(Cavity/Toothache)=0.8 means that “there is an 80% chance that the patient is having a cavity given that he is having a toothache” 线性代数与概率统计基础

26 后验概率(C) Conditional probabilities can be defined in terms of unconditional probabilities: Conditional probabilities lead to the chain rule: P(A,B)=P(A/B)P(B)=P(B/A)P(A) 线性代数与概率统计基础

27 全概率 If A1, A2, …, An is a partition of mutually exclusive events and B is any event, then Special case : Using the chain rule, we can rewrite the law of total probability using conditional probabilities: 线性代数与概率统计基础

28 全概率：例子 My mood can take one of two values
Happy, Sad The weather can take one of three values Rainy, Sunny, Cloudy We can compute P(Happy) and P(Sad) as follows: P(Happy)=P(Happy/Rainy)+P(Happy/Sunny)+P(Happy/Cloudy) P(Sad)=P(Sad/Rainy)+P(Sad/Sunny)+P(Sad/Cloudy) 线性代数与概率统计基础

29 Bayes 公式 Conditional probabilities lead to the Bayes’ rule: Where
Example: consider the probability of Disease given Symptom: where 线性代数与概率统计基础

30 Bayes 公式一般形式 If A1, A2, …, An is a partition of mutually exclusive events and B is any event, then the Bayes’ rule is given by: where 线性代数与概率统计基础

31 独立性 Two events A and B are independent iff:
P(A,B)=P(A)P(B) From the above formula, we can show: P(A/B)=P(A) and P(B/A)=P(B) A and B are conditionally independent given C iff: P(A/B,C)=P(A/C) 线性代数与概率统计基础

32 随机变量 A random variable (r.v.) is the value we assign to the outcome of a random experiment (i.e., a function that assigns a real number to each event). X(j) 线性代数与概率统计基础

33 随机变量 How is the probability function of the random variable is being defined from the probability function of the original sample space? Suppose the sample space is S=<s1, s2, …, sn> Suppose the range of the random variable X is <x1,x2,…,xm> We observe X=xj iff the outcome of the random experiment is an such that X(sj)=xj P(X=xj)=P( : X(sj)=xj) 线性代数与概率统计基础

34 概率密度函数 (pdf) The pmf /pdf of a r.v. X assigns a probability for each possible value of X. Warning: given two r.v.'s, X and Y, their pmf/pdf are denoted as pX(x) and pY(y); for convenience, we will drop the subscripts and denote them as p(x) and p(y), however, keep in mind that these functions are different ! 线性代数与概率统计基础

35 概率密度函数 (pdf) Some properties of the pmf and pdf: 线性代数与概率统计基础

36 概率分布函数 (PDF) With every r.v., we associate a function called probability distribution function (PDF) which is defined as follows: Some properties of the PDF are: (1) (2) F(x) is a non-decreasing function of x If X is discrete, its PDF can be computed as follows: 线性代数与概率统计基础

37 多元随机变量的概率密度函数 For n random variables, the joint pmf assigns a probability for each possible combination of values: p(x1,x2,…,xn)=P(X1=x1, X2=x2, …, Xn=xn) 线性代数与概率统计基础

38 离散随机变量的联合分布 P(Cavity, Toothache) is a 2 x 2 matrix
Specifying the joint pmf requires an enormous number of values kn assuming n random variables where each one can assume one of k discrete values. things much simpler if we assume independence or conditional independence … P(Cavity, Toothache) is a 2 x 2 matrix Joint Probability Toothache Not Toothache Cavity 0.04 0.06 Not Cavity 0.01 0.89 Sum of probabilities = 1.0 线性代数与概率统计基础

39 联合分布的性质 The conditional pdf can be derived from the joint pdf:
Conditional pdfs lead to the chain rule (general form): 线性代数与概率统计基础

40 联合分布的性质(C) Knowledge about independence between r.v.'s is very powerful since it simplifies things a lot, e.g., if X and Y are independent, then: The law of total probability: 线性代数与概率统计基础

41 边缘分布(Marginalization)
From a joint probability, we can compute the probability of any subset of the variables by marginalization: Example - case of joint pmf : Examples - case of joint pdf : 线性代数与概率统计基础

42 联合分布的作用 线性代数与概率统计基础

43 联合分布的作用 线性代数与概率统计基础

44 正态分布(Normal (Gaussian) Distribution)
线性代数与概率统计基础

45 正态分布 Shape and parameters of Gaussian distribution
number of parameters is shape determined by Σ 线性代数与概率统计基础

46 数学期望 线性代数与概率统计基础

47 方差(Variance)和均方差 线性代数与概率统计基础

48 协方差(Covariance) 线性代数与概率统计基础

49 协方差矩阵 线性代数与概率统计基础

50 独立随机变量的协方差 线性代数与概率统计基础

51 数学期望 线性代数与概率统计基础

52 协方差矩阵的性质 线性代数与概率统计基础

53 协方差矩阵的分解 Φ-1= ΦT 线性代数与概率统计基础