专业数学基础

\[ \newcommand{\vec}{\mathbf} \newcommand{\eps}{\varepsilon} \]

===更新中 ===

线性代数

线性变换

对空间中的每个点作变换后，轴保持平行等距，原点不变。

upd：更广义的说法是线性映射（离散数学中的映射）：空间 \(V\) 变换到空间 \(W\) （这里的空间可以是任何广义的空间）后，保持加法和数乘运算。

线性映射本身也具有加法、数乘和乘法性质： \[ \begin{gather*} S,T均为空间V到W的线性映射，K为U到V的映射 \\ (S+T)(v) = S(v) +T(v) \\ (\lambda T)(v) = \lambda(T(v)) \\ SK(u) = S(K(u)) \end{gather*} \] （线性映射不具有交换律，一定将零元映射到零元）

线性映射可能降维，但不可能升维。

线性映射 \(T\) 可能将一些向量映射到0 \(T(v) = 0\)，这些向量被称为 \(T\) 的零空间 \(\mathrm{null} T\)。

线性映射若不降维（等价于 \(\mathrm{null} T = \{0\}\)），则它必定是单射、满射、可逆（即线性变换），我们称之为同构

单射+满射 = 可逆 = 满秩 = 同构

我们说”从空间 \(V\) 到 \(W\) 的线性映射 \(T\) “时，并不意味着 \(W\) 中的每个元素都能被映射到。能被映射到的部分称为值域 \(\mathrm{range}T\)，它是 \(W\) 的一个子空间。 \[ dim(V) = dim(\mathrm{range}T) + dim(\mathrm{null}T) \]

线性泛函

空间 \(V\rightarrow \mathbf F\) 的线性映射称之为 \(V\) 的线性泛函，这可以是任意广义的空间上的线性映射，例如 \(\varphi(p) = \int p(x)dx\) 是多项式空间 \(\mathcal{P}\) 上的线性泛函。

对偶基

由 \(n\) 维线性空间 \(V\) 到一维数域 \(F\) 的映射称为线性泛函，它可以用一个 \(n\) 维向量表示。所有的线性泛函构成了 \(n\) 维空间 \(V'\)，它是 \(V\) 的对偶空间。

设 \(v_1,..v_n\) 是 \(V\) 的一组基（不必正交），\(\phi_1,..\phi_n\) 是 \(V'\) 中的向量组，满足 \(\phi_i(v_j) = \delta_{ij}\)，则 \(\phi_1,..\phi_n\) 是 \(v_1,..v_n\) 的对偶基。对偶基是对偶空间的基。

矩阵分解

LU分解

对于可逆方阵 \(\vec A\)，我们进行高斯消元，将其表示为若干个初等矩阵和一个上三角矩阵的乘积，\(\vec A = \vec E_1 \vec E_2..\vec U = \vec L \vec U\)

高斯消元的过程如果始终是自上而下递推的，则显然 \(\vec L\) 是一个下三角矩阵。这就是矩阵的LU分解。我们可以进行额外的缩放变换，使得 \(\vec L\) 的对角线元素都为1。

消元时可能无法避免行交换，那么可以先对 \(\vec A\) 进行行交换再分解： \[ \begin{gather*} \vec P\vec A = \vec L \vec U \\ \vec A = \vec P^{-1}\vec L \vec U \\ \end{gather*} \]

Cholesky分解

（TOBE UPDATED）

正定矩阵必然可以分解为 \(\vec A = \vec L \vec L^T\)，\(\vec L\) 是一个下三角矩阵，对角线上元素均大于0。

不难发现 \(\vec A_{uv} = \sum_{k=1}^{n} \vec L_{uk}\vec L_{vk}\)

我们可以从左到右、从上到下地计算 \(L\) \[ \begin{gather*} L_{vv}^2 =A_{vv} - \sum_{k=1}^{v-1} L_{vk} \\ L_{vv}L_{uv} = A_{vv} - \sum_{k=1}^{v-1} L_{uk} L_{vk},(u\ge v) \end{gather*} \]

QR分解

QR分解有完全QR分解和约化QR分解，如图所示。

约化形式：\(\vec A_{m\times n} = \vec Q_{m\times n} \vec R_{n\times n}\)，\(\vec Q\) 为列正交矩阵，\(\vec R\) 为上三角矩阵。

完全形式即约化形式在 \(\vec Q\) 上扩充正交基。

任意列满秩矩阵 \(\vec A\) 一定存在上述两种QR分解。

对于任意秩为 \(r\) 的矩阵 \(\vec A\)，也存在一种QR分解（暂略）。

Gram-Schmidt正交化

将 \(\vec A\) 的 \(n\) 个列向量 \(\vec a_1,..\vec a_n\) 投影到正交基 \(\pmb\eps_1,..\pmb\eps_n\) 上。首先令 \(\pmb\eps_1 = \frac{\vec a_1}{||\vec a_1||}\)，然后令后续所有 \(\vec a\) 减去与 \(\pmb\eps_1\) 平行的分量 \[ \vec a_i \leftarrow \vec a_i - (\vec a_i^T\pmb\eps_i)\pmb\eps_i \] 随后 \(\pmb\eps_2 = \frac{\vec a_2}{||\vec a_2||}\)，以此类推。

最终 \(\vec Q = [\pmb\eps_1,...\pmb\eps_n]\)，\(\vec R = \vec Q^T\vec A\)。

上式实际上可以看做对 \(\vec A\) 的一系列初等变换，每一步都是先归一化第 \(i\) 列（等价于整列除 \(||\vec a_i||\) ），再令右侧每一列减去 \((\vec a_j^T\pmb\eps_i)\) 倍的第 \(i\) 列。这一系列初等变换构成的是一个上三角矩阵。（注意列变换的初等矩阵应该乘在右边） \[ \vec A (\vec E_1...\vec E_k) = \vec Q \] \(\vec R\) 即为这个初等变换的逆矩阵，仍然是上三角矩阵。

Householder变换

Householder矩阵：\(\vec H = \vec I - 2\vec u\vec u^T\)，这个矩阵表示的是沿“以单位向量 \(\vec u\) 为法线的 \(n-1\) 维超平面”的镜像变换矩阵，代入 \(\vec x\) 计算一下 \(\vec H\vec x\) 容易理解。

\(\vec H\) 有许多性质，都比较容易理解：\(\vec H = \vec H^{-1}\)，\(\vec H\) 是正交的，特征值为 \(1,-1\)。

对于任意向量 \(\vec x\)，一定存在某个Householder变化将其映射到 \(\pm||\vec x|| \vec e_1\)，\(\vec e_1\) 为标准单位向量（易得）

以 \(\vec x_1 > 0\) 为例，我们会选取 \(\vec u = \vec x + ||\vec x|| \vec e_1\) 对应的变换，这实际上是将其映射到了 \(-\vec e_1\) 方向上，这样反着映射能让 \(\vec u\) 尽可能大，保证数值稳定。

利用Householder进行QR分解

对于任意方阵 \(\vec A = (\vec a_1, ..\vec a_n)\)，首先取 \(\vec H_1\vec a_1 = k_1 \vec e_1\)，这里的 \(k_1 = \pm||\vec a_1||\)，依据上述原则取正负。

\(\vec A \vec H_1\) 得到的结果第一列为 \(k_1\vec e_1\)，再取其右下角 \(n-1\) 阶子式作为 \(\vec A_2\)，进行下一步。

下一步同理，得到 \(\vec{\hat H_2}\)（\(n-1\) 阶），再令 \[ \vec H_2 = \left[ \begin{gather*} \vec I &0 \\ 0 &\vec{\hat H_2} \end{gather*} \right] \] 得到 \(n\) 阶的 \(\vec H_2\)，这个 \(\vec H_2\) 同样是一个householder矩阵。

如此这般，最终得到 \(\vec H_{n-1} ..\vec H_1\vec A = \vec R\)，形成了一个上三角矩阵。

\(\vec Q = (\vec H_{n-1} ..\vec H_1)^{-1}\)

奇异值分解

对于列满秩矩阵 \(\vec A_{m\times n}\)，它将 \(n\) 维空间的单位球投影到 \(m\) 维超椭球上，其中，单位球上的正交轴 \(\vec v_1,..\vec v_n\) 分别投影到椭球上的正交主轴 \(\sigma_1 \vec u_1,..\sigma_n\vec u_n\)，即 \(\vec A \vec v_i = \sigma_i \vec u_i\)

\(\vec v_i\) 称为右奇异向量，\(\vec u_i\) 为左奇异向量，\(\sigma_i\) 为奇异值 \[ \begin{align*} 设 \quad &\pmb\Sigma = diag(\sigma_1,.. \sigma_n) \\ & \vec V = (\vec v_1,..\vec v_n) \\ & \vec U = (\vec u_1,..\vec u_n) \\ 则 \quad &\vec A\vec V = \vec U \pmb\Sigma \\ &\vec A_{m\times n} = \vec U_{m\times n} \pmb\Sigma_{n\times n} \vec V^{T}_{n\times n} \end{align*} \] 这是约化奇异值分解，我们也可以将其扩充成完全奇异值分解： \[ \vec A_{m\times n} = \vec U_{m\times m} \pmb\Sigma_{m\times n} \vec V^{T}_{n\times n} \]

如何计算 \(\vec U\) 和 \(\vec V\)？ \[ \vec A^T\vec A = (\vec V \pmb\Sigma^T \vec U^{T}) (\vec U \pmb\Sigma \vec V^{T}) = \vec V \pmb\Sigma^2 \vec V^T \] 这个式子很熟悉，我们可以发现 \(\vec A^T \vec A\) 的特征向量组即为 \(\vec V\)，特征值即为 \(\pmb\Sigma^2\)。同理我们可以得出 \(\vec A\vec A^T\) 的特征向量组即为 \(\vec U\)。

由于 \(\pmb\Sigma\) 实际上是一堆特征值，我们可以随便改它们的顺序；将其从大到小排序后，往往前面少数几个奇异值就占据了99%以上的比例，这就可以来做压缩。

• 最大奇异值表示了矩阵的能够放大向量的最大倍数，这也是矩阵的2-范数，\(||\vec A||_2 = \sigma_1\)；

• 矩阵的F-范数类似向量的长度，为所有元素平方和开根， \[ ||\vec A||^2_F = \sum_{i=1}^m(\vec A \vec A^T)_{i,i} = tr(\vec A \vec A^T) = \sum_{i=1}^n\sigma^2_{i} \] 这里用到了：对角线之和 = 迹 = 特征值之和 = \(\pmb\Sigma^2\) 元素和。

非满秩情况

对于非列满秩的矩阵，也可以进行SVD，会得到一些零奇异向量，

（特征值分解时，零特征值也会对应若干组线性不相关的特征向量？TOBE CHECK）

设有 \(r\) 个非零奇异向量（等价于 \(\vec A\vec A^T\) 有 \(r\) 个非零特征值）：

图中可以看出，实际上有用的部分就只有 \(\vec V, \vec U\) 的前 \(r\) 列，因此有： \[ \vec A_{m\times n} = \vec U'_{m\times r} \Sigma'_{r\times r} \vec V'^T_{r\times n} \] 这里我们用 \('\) 表示矩阵中起作用的子式。

• \(\vec A\) 的列空间等于 \(\vec U'_{m\times r}\) 张成的空间；$A $ 的零空间等于 \(\vec V\) 的 \(r+1,..n\) 列张成的空间。

多元统计分析

协方差

复习一下：

协方差表达了两个随机变量的线性相关性： \[ \begin{gather*} Cov(X, Y) = E((X-\overline X)(Y-\overline Y)) \\ Cov(X, X) = D(X) \end{gather*} \] 协方差可以为正或者负，两变量线性不相关时，协方差为0（注意不相关不等于独立，它们还可以有非线性的相关性）

协方差矩阵，即对于 \(n\) 个随机变量 \(X_1,..X_n\)，\(\Sigma_{i,j} = Cov(X_i, X_j)\)，包含了所有随机变量的两两协方差，显然，协方差矩阵是一个实对称矩阵，它的特征向量彼此正交。

协方差矩阵的特征值和特征向量有重要的几何意义，考虑 \(m\) 个 \(n\) 维样本（每一维对应一个随机变量 \(X_i\)）构成 \(m\times n\) 的样本矩阵 \(\vec A\)，不失一般性地，假设所有样本均值为0。

于是 \(\Sigma = \frac{1}{m} \vec A^T\vec A\)，考虑它的特征向量： \[ \begin{gather*} \Sigma x = \lambda x \\ \vec A^T \vec A x = m \lambda x \\ (\vec Ax)^T(\vec Ax) = m\lambda x^Tx = m\lambda \end{gather*} \] \(\vec Ax\) 实际上是所有样本点与 \(x\) 作点乘，\((\vec Ax)^T(\vec Ax)\) 表示所有点在 \(x\) 方向的投影的平方之和，\(\lambda\) 也就是在 \(x\) 方向上的方差。

结论：协方差矩阵的最大特征值对应的特征向量即为点集分布方差最大的方向（点云朝向）；最小的方向即为法向。

多元随机向量

设 \(\vec X\) 为随机向量组 \([\vec x_1,..\vec x_p]^T\)

它的期望也是 \(p\times 1\) 的向量组，方差是协方差矩阵： \[ \begin{gather*} D(\vec X) = E((\vec X - \vec{\overline X})(\vec X - \vec{\overline X})^T) \\ D(\vec X)_{i,j} = Cov(\vec X_i, \vec X_j) \end{gather*} \] 这里方差的定义和单随机变量的定义类似，只不过用 \(\vec A\vec A^T\) 的形式代替了平方。

两个随机向量之间的协方差也可以构成协方差矩阵，但需注意这种矩阵并不对称。 \[ \begin{gather*} Cov(\vec X, \vec Y) = E((\vec X - \vec{\overline X})(\vec Y - \vec{\overline Y})^T) \\ Cov(\vec X, \vec Y)_{i,j} = Cov(\vec X_i, \vec Y_j) \end{gather*} \] 两个随机向量 \(\vec X, \vec Y\) 组合成一个新随机向量，其协方差矩阵为： \[ \Sigma = \left[ \begin{align*} Cov(\vec X, \vec X), Cov(\vec X, \vec Y) \\ Cov(\vec Y, \vec X), Cov(\vec Y, \vec Y) \\ \end{align*} \right] \\ \]

可以看出随机变量的性质可以很好地扩展到多元，并且仍然符合原有的定义。

一些性质： \[ \begin{gather*} E(\vec A\vec X) = \vec A E(\vec X) \\ D(\vec A\vec X) = \vec A D(\vec X) \vec A^T \\ Cov(\vec A\vec X, \vec B\vec Y) = \vec A Cov(\vec X, \vec Y) \vec B^T \end{gather*} \] 运用原始定义比较容易证明。

协方差矩阵是实对称、半正定的（将 \(\vec y^T \Sigma \vec y\) 代入原始定义易证）。那么 \(\Sigma\) 可相似对角化，并且有任意特征值 \(\ge 0\)： $$ \[\begin{gather*} \Sigma = \vec U^T\Lambda \vec U = (\vec U^T \sqrt \Lambda\vec U)^2 = \vec L \vec L^T, \quad (\vec L = \vec L^T)\\ \end{gather*}\] $$

这说明了协方差矩阵可以”开根“，在 \(\Sigma\) 正定时，\(\vec L\) 必定是满秩的。

多元正态分布

一个 \(p\) 维的多元正态分布 \(\vec X\) 是由 \(q\) 个相互独立的标准正态分布 \(U_1,..U_q \sim N(0, 1)\) 线性组合而成的： \[ \vec A_{p\times q} \vec U_{q\times 1} + \pmb\mu_{p \times 1} = \vec X_{p\times 1} \sim N_p(\pmb\mu, \vec A\vec A^T) \] 这是多元正态分布的定义，注意在这之中，\(U_{1..q}\) 是相互独立的标准正态分布，它们按照 \(\vec A\) 线性组合形成了 \(\vec X\) 中的 \(p\) 个随机变量，它们之间是有关联的，协方差为 \(\vec A \vec A^T\)（容易证明）。

这说明，多元正态分布的各个变量虽然相互有关，但它们的关系是很简单的，只是一批独立标准正态分布的不同组合。

多元正态分布重新进行任意线性组合，得到的仍为多元正态分布。 \[ \begin{gather*} \vec X \sim N_p(\pmb\mu, \Sigma) \\ \vec B_{s\times p} \vec X + \vec d \sim N_s(\pmb B\pmb\mu+\vec d, \vec B\Sigma \vec B^T) \end{gather*} \] 多元正态分布的任意边缘分布也是正态分布。但一个分布的任意边缘分布为正态分布，不能导出该分布是多元正态分布；一个随机向量的任意线性组合都为一元正态分布，可以推出该随机向量是正态随机向量。

多元正态分布的联合概率密度函数： $$ \[\begin{gather*} \vec X \sim N_p(\pmb\mu, \Sigma) \\ f(\vec X) = \frac{1}{(2\pi)^{p/2}|\Sigma|^{1/2}} \exp(-\frac{1}{2}(\vec X - \pmb\mu)^T\Sigma^{-1}(\vec X - \pmb\mu)) \end{gather*}\] $$ 符合这种概率密度函数 \(\leftrightarrow\) 是多元正态分布。

随机矩阵

从 \(p\) 元随机向量 \(\vec X\) 中取 \(n\) 个样本，构成 \(n\times p\) 的样本矩阵，称为随机矩阵 \(\vec X'\)。

我们先不将样本确定化，随机矩阵仍然视为一个 \(n\times p\) 维的长随机向量，可以把它拉直来看：

拉直后的随机向量的均值和协方差矩阵如图所示，注意两次不同采样之间是独立的，因此两个样本间的协方差为0。

若 \(\vec X \sim N_p(\pmb\mu, \Sigma)\)，则随机阵拉直后的随机向量 \(Vec(\vec X')\) 也是一个多元正态分布： \[ Vec(\vec X') \sim N_{n\times p}(\vec 1_{n} \otimes \pmb\mu, \vec I_{n} \otimes \Sigma) \] 图示见上，也可以把 \(\pmb\mu\) 也罗列成一个矩阵 \(\vec M\)： \[ \vec X_{n\times p}' \sim N_{n\times p}(\vec M_{n\times p}, \vec I_n\otimes \Sigma) \] 称随机阵 \(\vec X'\) 服从矩阵正态分布。

• Kronecker积，直积：由 \(\vec A\) 中的每一个元素乘以 \(\vec B\)，再罗列成一个大矩阵：\(\vec A_{n\times p}\otimes\vec B_{m\times q} = \vec C_{nm\times pq}\)
• \(\vec 1_n\) 为长度为 \(n\) 的列向量，值全为1；\(\vec I_n\) 为 \(n\) 阶单位矩阵。

样本矩阵

现在将样本确定下来，已有一个 \(n\times p\) 的样本矩阵 \(\vec X\)（确定值），如何从中估计参数？

均值 \(\vec{\overline X}_{p\times 1} = \frac{1}{n}\vec X^T \vec 1_n\)

样本离差矩阵：\(\vec A = \vec{\tilde X^T} \vec{\tilde X}\)，其中 \(\vec{\tilde X}\) 为减去均值后的样本矩阵

协方差矩阵：\(\vec S = \frac{1}{n-1} \vec A\)

相关系数矩阵：按相关系数定义计算即可 \(\rho(X, Y) = \frac{COV(X, Y)}{\sigma_X \sigma_Y}\)，嫌麻烦就不写成矩阵形式了）

可以通过样本矩阵，对多元正态总体的 \(\pmb \mu, \Sigma\) 进行最大似然估计（用到多元正态总体的联合概率密度，略）。

回归分析

标准线性回归模型：有样本矩阵 \(\vec X_{n\times m}\)，每个样本对应一个标签（因变量），标签矩阵 \(\vec Y_{n\times 1}\)，要求样本与标签的线性关系（或尽可能近似的线性关系） \[ \begin{gather*} \vec Y = \vec C \pmb\beta + \pmb\eps \\ \vec C = [\vec 1_n, \vec X], \quad \pmb\beta = [\beta_0,..\beta_m]^T \end{gather*} \] 其中 \(\pmb\eps\) 衡量误差。对于不同的样本，误差也不尽相同，因此我们认为 \(\pmb\eps\) 是一个不可观测的随机变量，\(\pmb\eps \sim N_n(0, \sigma^2\vec I_n)\)。（这个式子说的是general的情况，代入样本矩阵后，每一个样本对应的误差是确定值）

可以认为 \(\vec{\hat Y} = \vec C \pmb\beta\) 为预测值， \(\vec Y\) 为真实值，该模型假设误差符合正态分布。

在给定样本阵和标签阵下，要使误差 \(\vec Y - \vec C\pmb\beta\) 尽可能小，按照最小二乘法 \(Q(\pmb\beta) = (\vec Y - \vec C\pmb\beta)^T(\vec Y - \vec C\pmb\beta)\)，使 \(Q(\pmb\beta)\) 的一阶导为0： \[ \begin{gather*} \frac{\part Q}{\part \pmb\beta} = -2(\vec Y - \vec C\pmb\beta)^T\vec C = 0\\ \pmb\beta = (\vec C^T\vec C)^{-1}\vec C^T\vec Y \end{gather*} \] 设 \(\vec b = (\vec C^T\vec C)^{-1}\vec C^T\vec Y\) 为 \(\pmb\beta\) 的最小二乘估计量。

由 \(\vec Y \sim N_n(\vec C\pmb\beta, \sigma^2\vec I_n)\)，得 \(\vec b \sim N_{m+1}(\pmb\beta, \sigma^2(\vec C^T\vec C)^{-1})\)，可以得知 \(\vec b\) 是 \(\pmb\beta\) 的无偏估计量，还是方差最小的无偏估计（这一点不会证明）

方差 \(\sigma^2\) 估计：残差平方和为 \(Q(\vec b)\)，在这之中，有 \(n\) 个样本，但 \(\vec b\) 中已有 \(m+1\) 个参数，因此自由度为 \(n - m - 1\)

\(\sigma^2\) 的无偏估计量为 \(s^2 = \frac{Q(\vec b)}{n - m - 1}\) （这边还没彻底理解），这也就是常说的MSE。

如何衡量一个回归的好坏？ \[ \begin{gather*} SSE = (\vec Y - \vec{\hat Y})^T(\vec Y - \vec{\hat Y}) = Q(\vec b) \\ SSM = (\vec{\hat Y} - \overline Y)^T(\vec Y - \overline Y) \\ SST = (\vec Y - \overline Y)^T(\vec Y - \overline Y) \\ SST = SSM + SSE \end{gather*} \] 这里的 \(SSE\) 衡量了无法被回归方程解释的误差平方和，\(SST\) 为总方差，决定系数 \(R^2 = SSM / SST\) 衡量了线性回归拟合的好坏，这是一个比例，其中 \(R\) 为复相关系数。

为了简便上面简写成了广播的形式，向量减去 \(\overline Y\) 时应逐位操作。

距离判别

设有 \(m\) 维总体 \(G\)，已知其均值向量 \(\pmb\mu\) 和协方差矩阵 \(\Sigma\)，则样本 \(\vec X_{m\times 1}\) 到该总体的马氏距离为： \[ d^2(\vec X, G) = (\vec X - \pmb\mu)^T\Sigma^{-1} (\vec X - \pmb\mu) \] 一维情况下的马氏距离为简单的“距离平方比方差”：\(d^2 = \frac{(x-\mu)^2}{\sigma^2}\)

若不知道精确的 \(\pmb\mu\) 和 \(\Sigma\)，而是给出了总体 \(G\) 的 \(n\) 个训练样本，则可以先估计 \(\pmb\mu\) 和 \(\Sigma\)，再计算马氏距离。

给定多个总体 \(G_1,..G_k\) 时，可以分别计算待测样本到他们的马氏距离。

给定 \(k\) 个总体各自的样本，样本总数为 \(n\)，假设各个总体的真实协方差相同，则合并样本协方差矩阵的估计为： \[ \vec S = \frac{1}{n-k} \sum_{i=1}^k \vec A_i \] 这个式子等价于简单地将样本合并再计算，但更加简单。因为使用了 \(k\) 个均值，所以计算方差时自由度需要减 \(k\)；若合并样本后只计算一个均值，就是经典公式 \(\vec S = \frac{1}{n-1} \vec A\)。 \[ \begin{gather*} d^2(\vec X, G_i) &=& (\vec X - \pmb\mu_i)^T \vec S^{-1} (\vec X - \pmb\mu_i) \\ &=& \vec X^T \vec S^{-1}\vec X - 2(\vec X^T\vec S^{-1}\pmb\mu_i - \frac{1}{2}\pmb\mu_i^T\vec S^{-1}\pmb\mu_i) \\ Y_i(\vec X) &=& 2(\vec X^T\vec S^{-1}\pmb\mu_i - \frac{1}{2}\pmb\mu_i^T\vec S^{-1}\pmb\mu_i) \end{gather*} \] 进行分类时，只需要对比 \(Y\) 即可（虽然感觉这个 \(Y\) 明明更复杂了...）。这里的 \(\pmb\mu_i\) 指的是估计量。

进行二分类（例如 \(G_1,G_2\)），考虑两个距离之差： \[ W(\vec X) = Y_1(\vec X) - Y_2(\vec X) = (\vec X - \frac{1}{2}(\pmb\mu_1 +\pmb\mu_2))^T\vec S^{-1} (\pmb\mu_1 - \pmb\mu_2) \] 这个 \(W(\vec X)\) 即为一条划分直线。注意 \(Y\) 与距离是反相关的，\(W > 0\) 说明 \(G_1\) 距离更近。

广义距离判别

在原先的马氏距离 \(d^2\) 基础上，额外加上：

• 一个修正损失 \(g_1(G_i) = log(|\vec S_i|)\)，这是对各组协方差不等的情况做的一个修正，不太懂有啥用。
• 先验损失 \(g_2(G_i) = -2log(|q_i|)\)，其中 \(q_i\) 为第 \(i\) 类出现的先验概率（可以是经验值或者所有样本中第 \(i\) 类出现的频率）

聚类分析

有 \(n\) 个 \(m\) 维样本，但并没有分类，需要将它们根据相似性归为几类。

样本间距离的度量有很多种：

• 闵可夫斯基距离（包括欧氏距离，曼哈顿距离等等）

• 马氏距离，样本间的马氏距离和样本到总体的马氏距离类似： \[ d^2(\vec X_i, \vec X_j) = (\vec X_i - \vec X_j)^T\vec S^{-1} (\vec X_i - \vec X_j) \] 其中 \(\vec S\) 是通过所有样本估计得到的协方差矩阵。马氏距离不会受到各个维度的量纲影响，且考虑了方差。

• 斜交空间距离： \[ d^2_{i,j} = \frac{1}{m^2}\sum_{k=1}^m \sum_{l=1}^m (x_{i,k} - x_{i,k})(x_{i,l} - x_{j,l})r_{k,l} \] 其中 \(r_{k,l}\) 为两个维度的相关系数。

• 定性样本间的距离：\(\frac{不匹配项目数}{总项目数}\)，也可以对1-1配对和0-0配对赋予不同的权重。

• 余弦相似度：\(\frac{\vec A \cdot \vec B}{||\vec A||\times ||\vec B||}\)，等等

系统聚类法：先将 \(n\) 个样本视为 \(n\) 个不同类，再不断合并最近的两类。每次合并后，需要更新合并类到其他类的距离（样本集距离）

两个样本集之间的距离也有很多度量，如最小样本距离、最大样本距离、类平均（两两距离的平方的均值）等；这三种距离度量都具有单调性，即每次合并后，下一次合并时的距离不会更小。

线性规划

一个带约束的优化问题的基本形式： \[ \left\{ \begin{aligned} min \quad &f(\vec x) \\ s.t. \quad &h_i(\vec x) = 0 \\ &g_j(\vec x) \ge 0 \end{aligned} \right. \] 目标可以是最大或最小值，约束可以有等式约束和不等式约束。目标函数和约束都是线性函数的规划问题称为线性规划（LP）

消去等式约束

等式约束通过转换去掉，添加额外的优化变量 \(\pmb\lambda > 0\)，新的优化目标为： \[ L(\vec x, \pmb\lambda) = f(\vec x) + \sum \pmb\lambda_i h_i(\vec x) \] 通过这种转换，原先的最优解在新的域下也一定是最优解

线性规划标准化

线性规划的标准型： \[ \left\{ \begin{aligned} min \quad &z = \sum_{j=1}^n c_j x_j \\ s.t. \quad &\sum_{j=1}^n a_{ij} x_j = b_i, &\forall i=1,..m &(共m条约束)\\ &x_j \ge 0, &\forall j=1,..n & \end{aligned} \right. \] 一般的线性规划问题可以标准化，通过下面几种方式：

• 对于目标函数是 \(max\) 的，转化求 \(min \quad f = -z\)
• 将约束 \(x_j \ge h\) 转化为 \(y_j = x_j - h_j \ge 0\)，用 \(y_j\) 替换原变量 \(x_j\)
• 将不受限的变量 \(x_j\) 替换为 \(x_j = y_j' - y_j'', \quad y_j',y_j'' \ge 0\)
• 将约束 \(\sum_{j=1}^n a_{ij} x_j \le b_i\) 转化为 \(\sum_{j=1}^n a_{ij} x_j +x_i' = b_i, \quad x_i' \ge 0\)
• 将约束 \(\sum_{j=1}^n a_{ij} x_j \ge b_i\) 转化为 \(\sum_{j=1}^n a_{ij} x_j - x_i' = b_i, \quad x_i' \ge 0\)

线性规划标准型可以写成线性方程组： \[ \left\{ \begin{aligned} min \quad &z = \vec c^T \vec x\\ s.t. \quad &\vec A_{m\times n}\vec x_{n\times 1} = \vec B_{m\times 1}\\ &\vec x \ge 0, \end{aligned} \right. \] 线性方程组 \(\vec A\vec x = \vec B\) 的非负解为基本可行解。

单纯型法

寻找一个标准型的线性规划的最优解。

设矩阵 \(\vec A\) 的秩为 \(m\)，即 \(m\) 条约束线性无关，且 \(n\ge m\)，则方程 \(\vec A\vec x = \vec B\) 的解系中会有 \(n-m\) 个自由变量。

首先先选择 \(m\) 个变量作为基变量，\(n-m\) 个作为自由变量，不失一般性地，假设 \(x_{j=1,..m}\) 是基变量，剩下的是自由变量。

基变量可以由自由变量表示，自然，目标函数也可以用自由变量表示，经过一通变换，可以弄成这种形式：

这里 \(x_1, x_2,x_3\)（前三列）为基向量，最后一行为目标函数，都仅用自由变量表示。当自由变量全为0时，有 \(z = -d\)；

若最后一行的 \(s_1, s_2..\)（即目标函数用自由变量表示时的系数）全为正，则 \(z=-d\) 是最优解（无法再小，因为任意 \(x\ge 0\)）。

当 \(s\) 中存在负数时，可以更换基变量；具体来说，可以选择最小的 \(s\)（例如 \(s_j\)）所在的列作为新的基变量。替换原有哪一个基变量 \(i\)，则取决于替换谁能使 \(d\) 更大（通常是比较 \(\frac{b_i}{a_{ij}}\)）；倒腾后可能会变成这样：

经过若干轮，直到 \(s\) 全为正为止，说明找到了最优解。

凸集和凸函数

凸集：集合 $D R^n $ 对于任意集合内元素 \(\vec x, \vec y\in D\)，对于任意 \(\lambda \in[0, 1]\)，有 \(\lambda\vec x+(1-\lambda)\vec y\in D\)，则 \(D\) 为凸集（集合内任意两点连线的不会离开集合）。

凸函数：定义域 \(D\) 是凸集，并且对于任意 \(\vec x,\vec y\) 和 \(\lambda \in [0, 1]\)，有 \(\lambda f(\vec x)+(1-\lambda)f(\vec y) \ge f(\lambda \vec x+(1-\lambda)\vec y)\)；即函数在任意方向上都是一维凸函数（两点连线永远高于函数曲线，这里的凸是指向下凸，比如 \(y=x^2\)）。

导数定义：函数 \(f(\vec x)\) 在凸集上可微，对于任意 \(\vec x,\vec y\)，有 \(f(\vec y) \ge f(\vec x) + \nabla f(\vec x)^T(\vec y - \vec x)\)；式子右半边的部分其实就是方向导数乘上距离，可以类比一维情况。

二阶导定义：函数 \(f(\vec x)\) 在任意位置的Hessian矩阵半正定（即任意方向二阶导大于0），也是凸函数的充要条件。

凸函数的线性组合仍然是凸函数；对凸函数进行截断 \(\{ \vec x| f(\vec x) <\beta\}\) 是凸集。

线性规划（LP）往往有一些很好的性质。