线性代数|机器学习-P20鞍点和极值

1 . 瑞利商的思考

1.1 瑞利商的定义

假设A是n阶实对称矩阵，x是n维非零列向量，那么瑞利商表示如下：
R ( A , x ) = x T A x x T x

$$\begin{equation} R(A,x)=\frac{x^TAx}{x^Tx} \end{equation}$$ R(A,x)=xTxxTAx​​​

• 在看到上面式子时候，感觉很奇怪，为什么瑞利商就能够计算出鞍点和极值点的位置？我发现瑞利商的形式就像投影公式样。。。

1.2 投影向量

假设我们有两个向量$x,a_1$，我们想求向量$a_1$在向量x方向上的投影向量$p_1$

• 求$|p_1|$
  $$\begin{array}{c}|p_1|=|a_1|\cos (\theta ),x^T{a}_1=|a_1|\cos (\theta )\cdot |x|\to |p_1|=\frac{x^T{a}_1}{|x|}\end{array}$$
• $p_1$的单位向量为：
  $$\begin{array}{c}{e}_1=\frac{x}{|x|}\end{array}$$
• $p$向量为：
  $$\begin{array}{c}{p}_1=|p_1|\cdot e_1=\frac{x^{T}a}{|x|}\frac{x}{|x|}=\frac{x^T{a}_{1}x}{x^{T}x}\end{array}$$
• 小结：
  当我们对一个向量$a_1$进行瑞利商时，得到了居然是这个向量$a_1$在给定$x_1$向量上的投影向量，我们发现投影向量中只需要知道$x$向量的方向，跟$x$的大小无关，这点很重要，
• 转换：
  -那么我们有一个矩阵实对称A，它可以由如下组成：
  $$\begin{array}{c}A=\left[\begin{array}{cccc}{a}_1& a_2& \cdots & a_n\end{array}\right]\end{array}$$
• 那么瑞利商可以表示为：
  $$\begin{array}{c}R(A,x)=\frac{x^T\left[\begin{array}{cccc}{a}_1& a_2& \cdots & a_n\end{array}\right]x}{x^{T}x}=\left[\begin{array}{cccc}\frac{x^T{a}_{1}x}{x^{T}x}& \frac{x^T{a}_{2}x}{x^{T}x}& \cdots & \frac{x^T{a}_{n}x}{x^{T}x}\end{array}\right]\end{array}$$
• 小结 ： 瑞利商表示的是实对称矩阵A在给定x向量的投影向量组合。这里x的大小不影响投影向量的值。所以为了后续计算，我们可以定义$x^{T}x=1$，这样瑞利商问题可以变成如下：
  $$\begin{array}{c}R(A,x)=\frac{x^{T}Ax}{x^{T}x}\to R(A,x)=x^{T}Ax,st:x^{T}x=1\end{array}$$
• 那么瑞利商的极值问题就变成了一个二次型$x^{T}Ax$在约束条件下的$x^{T}x=1$的最优化问题。一般我们解决最优化问题，会引入拉格朗日乘子法：

2. 拉格朗日乘子法

我们的目标是要求实对称矩阵S的二次型$x^{T}Sx$在$x^{T}x=1$的约束情况下的最优化问题：这里为了方便，一般用S来表示实对称矩阵来代替上面的A，不影响后续理解和计算。纯粹为了方便。
L ( S , λ ) = x T S x − λ ( x T x − 1 )

$$\begin{equation} L(S,\lambda)=x^TSx-\lambda(x^Tx-1) \end{equation}$$ L(S,λ)=xTSx−λ(xTx−1)​​

• 求偏导可得：
  $$\begin{array}{c}\frac{\partial L(S,\lambda )}{\partial x}=2Sx-\lambda \cdot 2x=0\to Sx=\lambda x\end{array}$$
• 说明了瑞利商的偏导数为0的值一定在矩阵S的特征值$\lambda$上和其对应的特征向量x上。
  $$\begin{array}{c}\frac{\partial L(S,\lambda )}{\partial \lambda }=-x^{T}x+1=0\to x^{T}x=1\end{array}$$
  本来都是约束条件。
• 那问题就简单了，瑞利商的极值问题的点分别为特征值${\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_n$,其对应的特征向量$x_1,x_2,\cdots ,x_n$
• 那么我们代入到瑞利商原来式子中，可得极值特解方程，注意不是一般式：
  $$\begin{array}{c}R(S,x)=\frac{x^{T}Sx}{x^{T}x}=\frac{x^T\lambda x}{x^{T}x}=\lambda \end{array}$$
• 由于${\lambda }_n\le {\lambda }_{n-1}\le \cdots \le {\lambda }_2\le {\lambda }_1$
  $$\begin{array}{c}\underset{min}{\arg }R(S,x_n)={\lambda }_n;\underset{max}{\arg }R(S,x_1)={\lambda }_1;\end{array}$$
• 那么其他的特征值${\lambda }_2,{\lambda }_3,\cdots ,{\lambda }_{n-1}$对应的就是鞍点！！！这样我们就可以通过瑞利商来快速的找到鞍点。

3. 鞍点

在深度学习中，我们希望快速的找到极值点，一般就对损失函数求一次偏导后得到所有的极值点，但是有一种鞍点，其偏导数也为0，但是它既不是极大值点，又不是极小值点，但它的一阶偏导为0,所以我们需要排除鞍点的干扰，。如图所示：

• 鸡头法，先求最小值，再求最大值
  为了求得几何上的鞍点，我们需要先求最小值，在求最大值，数学表达式如下：
  λ = max ⁡ y min ⁡ x , z x T S x

  $$\begin{equation} \lambda=\max\limits_{y}\min\limits_{x,z}x^TSx \end{equation}$$ λ=ymax​x,zmin​xTSx​​
  

• 凤尾法，先求最大值，再求最小值
  λ = min ⁡ x max ⁡ y , z x T S x

  $$\begin{equation} \lambda=\min\limits_{x}\max\limits_{y,z}x^TSx \end{equation}$$ λ=xmin​y,zmax​xTSx​​
  

• 我们可以简单理解，鸡头不如凤尾，那么我们一般是使用鸡头法，这样求得的鞍点值更小。
  λ = max ⁡ y min ⁡ x , z x T S x

  $$\begin{equation} \lambda=\max\limits_{y}\min\limits_{x,z}x^TSx \end{equation}$$ λ=ymax​x,zmin​xTSx​​

• 我们就把一个鞍点问题转换成对偶问题，通过瑞利商和拉格朗日乘子法结合求得鞍点。

4. 线性拟合

4.1 范德蒙矩阵线性拟合

假设我们二维平面上有 6 个点，根据多项式拟合条件来说，6个点可以用一个五次方函数进行拟合。比如说我们平面上如果需要确定一条直线$(y=kx+b)$，一般需要两个点，确定一个抛物线$(y=a{x}^2+bx+c)$，一般需要三个点，所以6个点可以用
y = c 5 x 5 + c 4 x 4 + c 3 x 3 + c 2 x 2 + c 1 x + c 0

$$\begin{equation} y=c_5x^5+c_4x^4+c_3x^3+c_2x^2+c_1x+c_0 \end{equation}$$ y=c5​x5+c4​x4+c3​x3+c2​x2+c1​x+c0​​​

• 这里我们可以用范德蒙矩阵进行表示：
  $$\begin{array}{c}AC=b\end{array}$$
• A为范德蒙矩阵，C为相关系数。
  

4.2 python 代码

• jupyter 下运行

import numpy as np
import matplotlib.pyplot as plt

# 生成6个随机点
np.random.seed(42)  # 固定随机种子以获得可重复的结果
x = np.random.rand(6)
y = np.random.rand(6)

# 构造范德蒙矩阵
V = np.vander(x, increasing=True)

# 求解系数向量
a = np.linalg.solve(V, y)

# 生成用于绘制拟合曲线的x值
x_fit = np.linspace(0, 1, 100)
y_fit = np.polyval(a[::-1], x_fit)

# 绘制原始点和拟合曲线
plt.scatter(x, y, color='red', label='Original Points')
plt.plot(x_fit, y_fit, color='blue', label='Fitted Polynomial')
plt.xlabel('x')
plt.ylabel('y')
plt.title('Vandermonde Matrix Polynomial Fitting')
plt.legend()
plt.grid(True)
plt.show()

# 输出结果
print("随机生成的点:")
for xi, yi in zip(x, y):
    print(f"({xi:.4f}, {yi:.4f})")

print("\n范德蒙矩阵:")
print(V)

print("\n多项式系数:")
print(a)

# 打印多项式表达式
poly_str = "P(x) = " + " + ".join([f"{a[i]:.4f}x^{i}" for i in range(len(a))])
print("\n多项式:")
print(poly_str.replace("x^0", "").replace(" + -", " - ").replace("x^1", "x"))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

• 结果：
  
  

4.3 范德蒙矩阵缺点

我们之前在P18快速奇异值那章节学过，范德蒙矩阵的缺点是其矩阵的逆的秩特别大，不好求，导致计算范德蒙矩阵的逆是巨复杂的。还有就是希尔伯特矩阵。

5. 均值和方差

5.1 样本均值和方差

假设我们有N个样本$x_1,x_2,\cdots ,x_n$,那么样本$\bar{X}$均值为
X ˉ = 1 N ( x 1 + x 2 + ⋯ + x n )

$$\begin{equation} \bar{X}=\frac{1}{N}(x_1+x_2+\cdots+x_n) \end{equation}$$ Xˉ=N1​(x1​+x2​+⋯+xn​)​​

• 那么样本方差$S^2$由公式可得：
  $$\begin{array}{c}{S}^2=\frac{1}{n-1}\sum _{i=1}^n(x_i-\bar{X})\end{array}$$

5.2 总体期望 $\mu$,总体方差 ${\sigma }^2$

• 总体期望
  假设有无穷个样本$x_i$,每个样本对应的概率为$p_i$,那么可得：
  $$\begin{array}{c}\sum _{i=1}^{\infty }{p}_i=1,\mu =E(x)=\sum _{i=1}^{\infty }{p}_i{x}_i\end{array}$$
• 总体方差
  $$\begin{array}{c}D(X)=E(X^2)-[E(X){]}^2\end{array}$$
  $$\begin{array}{c}{\sigma }^2=\sum _{i=1}^{\infty }{p}_i(x_i-\mu {)}^2\end{array}$$