机器学习基本概念（未完待补）

Nearest Neighbors

无监督最近邻：
- 返回每个数据样本点的$k$近邻节点或者距离，无训练集
- **应用：**流行学习(manifold learning)、谱聚类(spectral clustering)
有监督最近邻
- 返回训练集中的$k$近邻
- **应用：**数据分类/回归

VC-Dimension

VC-Dimension用来量化分类器能够分类的训练样本的最大数目，是模型容量量化的一种方法。

参数模型&非参数模型

参数模型在观测到新数据前，参数向量的分量个数是有限且固定的，如线性回归/分类^[1]。
非参数模型仅是一些不能实际实现的理论抽象（比如搜索所有可能概率分布的算法）。非参数模型有最近邻回归、K近邻、SVM等。

频率学派&贝叶斯学派

对于参数估计，存在两个学派的不同解决方案。一是频率学派解决方案：通过某些优化准则（比如似然函数）来选择特定参数值；二是贝叶斯学派解决方案：假定参数服从一个先验分布，通过观测到的数据，使用贝叶斯理论计算对应的后验分布。先验和后验的选择满足共轭，这些分布都是指数簇分布的例子。

频率派最常关心的是似然函数，而贝叶斯派最常关心的是后验分布。我们会发现，后验分布其实就是似然函数乘以先验分布再 normalize一下使其积分到1。因此两者的很多方法都是相通的。
贝叶斯派因为所有的参数都是随机变量，都有分布，因此可以使用一些基于采样的方法（如MCMC）使得我们更容易构建复杂模型。频率派的优点则是没有假设一个先验分布，因此更加客观，也更加无偏，在一些保守的领域（比如制药业、法律）比贝叶斯方法更受到信任。^[2]^[3]

降维方法

线性降维
- PCA
- SVD, NMF
非线性降维
- KPCA(Kernel Method+PCA)
- 流行学习
  - 全局嵌入: 多维缩放MDS, ISOMAP
  - 局部嵌入: Laplacian Eigenmap

Laplace 矩阵与谱聚类^{沈, 网络数据挖掘-图聚类}

">[4]

定义矩阵$A$为$n$个顶点的无向图的邻接矩阵/边权非负矩阵，矩阵$D$是对角矩阵，且$D_{ii}=\sum_{j}A_{ij}$表示节点$i$的度数/边权和。
定义$L=D-A$，矩阵$L$就是矩阵$A$的对应的Laplace 矩阵。
Laplace 矩阵的性质:

对于任意向量$x$，都有$x^{TLx=\frac{1}{2}\sum_{i,j}A_{ij}(x_{i}-x_{j})}2$
半正定，即$0=\lambda_1\le\lambda_{2}\le\dots\le\lambda_{n}$

证明：
$$
\begin{align}
x^TLx &= x^T(D-A)x=xTDx-x^TAx\
&= \sum_{ij}x_ix_jD_{ij}-\sum_{ij}x_ix_jA_{ij}\
&= \sum_{i}x_i^2D_{ii}-\sum_{ij}x_ix_jA_{ij}\
&= \sum_{i}x_i^2\sum_jA_{ij}-\sum_{ij}x_ix_jA_{ij}\
&= \sum_{ij}(x_i^2-x_ix_j)A_{ij}\
&= \frac{1}{2}\sum_{ij}(x_i^2+x_j2-2x_ix_j)A_{ij}\
&= \frac{1}{2}\sum_{ij}(x_i-x_j)^2A_{ij}
&\ge 0
\end{align}
$$
显然，当$x_{1}=x_{2}=\dots=x_{n}=\frac{1}{\sqrt{n}}$时，$x$是$L$的一个特征向量，且对应的特征值为$0$。

谱聚类算法的一般步骤：

通过$n$个数据点构造无向图。无向图中的节点对应数据点，按照数据点的近邻+相似度规则构造出邻接矩阵$A$；
计算无向图的度矩阵$D$，$D$是对角矩阵，对角元素的值为邻接矩阵$A$对应行的行和;
计算Laplace矩阵$L=D-A$;
对Laplace矩阵$L$进行特征值分解，取前$k$小的特征值及其对应的特征向量$(k
将数据点映射到$k$维空间中，在$k$维空间中，对所有变换之后的样本点采用K-Means聚类，聚类结果就是谱聚类之后的结果。

谱聚类的基本思想便是利用样本数据之间的相似矩阵（拉普拉斯矩阵）进行特征分解（通过Laplacian Eigenmap 的降维方式降维），然后将得到的特征向量进行 K-means聚类。
此外，谱聚类和传统的聚类方法（例如 K-means）相比，谱聚类只需要数据之间的相似度矩阵就可以了，而不必像K-means那样要求数据必须是 N 维欧氏空间中的向量。

spectral-clustering
spectral-clustering