对于某些序列数据，后面的数据依赖于前面的数据，因此独立同分布假设不能成立
马尔科夫链
一阶马尔科夫属性：最简单的类型，\(t+1\)时刻的状态\(s_{t+1}\)仅由\(t\)时刻的状态\(s_t\)决定。可以用一个矩阵来描述一个过程所有状态转换的完整集合，称为转移矩阵\(M\)。其中\(M_{ij}\)是当当前状态为\(i\)时下一个状态为\(j\)的概率。形式化定义如下：
令\(s\in \{1,\ldots, S\}\)，序列\((s_1, \ldots, s_t)\)是一阶马尔科夫链，如果 \[ p(s_1,\ldots, s_t) \mathop{=}^{(a)} p(s_1)\prod_{u=2}^\mathsf{T} p(s_u|s_1, \ldots, s_{u-1}) \mathop{=}^{(b)} p(s_1)\prod_{u=2}^\mathsf{T} p(s_u|s_{u-1}) \] 注意上式与独立同分布有本质不同 \[ \begin{align*} p(s_1, \ldots , s_t) = \begin{cases} p(s_1)\prod_{u=2}^\mathsf{T} p(s_u|s_{u-1}) & {\rm Markov\ assumption} \\ \prod_{u=1}^\mathsf{T} p(s_u) & {\rm i.i.d.\ assumption} \end{cases} \end{align*} \]
其对应的转移矩阵\(M\)满足 \[ M_{ij} = p(s_t = j | s_{t-1} = i) \] 因此给定初始状态\(s_0\)以后，可以通过以下分布生成序列\((s_1, \ldots, s_t)\) \[ s_t | s_{t-1} \sim {\rm Discrete}(M_{s_{t-1}}, :) \] 相反地，给出一个序列，也可以使用最大似然估计去学习转移矩阵 \[ M_{\rm ML} = {\rm arg}\max_M p(s_1, \ldots, s_t|M) = {\rm arg}\max_M \sum_{u=1}^{t-1} \sum_{i,j}^s 1(s_u = i, s_{u+1} = j)\ln M_{ij} \] 由于\(M\)的每行都是一个概率分布，所以有 \[ M_{\rm ML}(i,j) = \frac{\sum_{u=1}^{t-1}1(s_u = i, s_{u+1} = j)}{\sum_{u=1}^{t-1}1(s_u = i)} \] 即实际观察到\(i\rightarrow j\)的转移数除以从\(i\)发生的转移总数
从另外一个角度可以分析出，给定初始状态的情况下，第\(t+1\)步会落在什么状态。首先，假设在第\(t\)步我们有一个所在状态的概率分布\(p(s_t=u)\)，那么\(s_{t+1}\)的分布为 \[ p(s_{t+1}=j) = \sum_{u=1}^s \underbrace{p(s_{t+1}=j|s_t=u)p(s_t=u)}_{p(s_{t+1}=j, s_t=u)} \] 如果用行向量\(w_t\)来表示\(p(s_t=u)\)（即状态的分布），那么有 \[ \underbrace{p(s_{t+1}=j)}_{w_{t+1}(j)} = \sum_{u=1}^s \underbrace{p(s_{t+1}=j|s_t=u)}_{M_{uj}}\underbrace{p(s_t=u)}_{w_t(u)} \] 即\(w_{t+1} = w_tM = \ldots = w_1M^\mathsf{T}\)
那么，在经历了无穷多次这样的步骤以后，整个系统会落在什么状态上？这就引出了稳定分布的概念，即令\(w_\infty = \lim _{t\rightarrow \infty} w_t\)，则\(w_\infty\)成为稳定分布。如果以下两个条件都满足，则对所有\(w_0\)最后的稳态\(w_\infty\)都相同
- 从任意一个状态开始，经过转化最后都能到达另一个状态
- 序列不会以某个预定好的模式进入死循环
\(w_\infty\)可以如下求得 \[ M^\mathsf{T}q_1 = \lambda_1q_1 \Longrightarrow \lambda_1 = 1, w_\infty = \frac{q_1}{\sum_{u=1}^S q_1(u)} \]
半监督学习
核心思想：使用部分有标记的数据来做分类，即大部分数据都没有标签\(y_i\)，但是仍然想学习\(x_1,\ldots,x_n\)的内在结构。做法是构建一个随机游走分类器，从一个点随机移动到周围的一个点。其中，周边点越临近，跳到该点的概率越大。如果游走到一个有标记的点，则结束游走。游走终点的标签就是起始点的标记
考虑到高斯核函数的性质，可以用它来构建转移矩阵，即 \[ \hat{M}_{ij} = \exp\left\{-\frac{|\!|x_i-x_j|\!|^2}{b}\right\} \] 将这个矩阵逐行归一化，就可以得到真正的转移矩阵\(M\)。如果\(x_i\)有标签，则将\(M_{ii}\)重新设置为1
假设有\(s\)个状态，如果\(p(s_t = i|s_{t-1} = i) = 1\)，那么第\(i\)个状态称为吸收态，因为永远不会从该状态离开。给定\(t=0\)时的初始状态\(s_0\)和一系列吸收态，可以计算经过随机游走以后落在各个吸收态的概率。由于每个吸收态都对应一个分类标签，因此这个状态也可以看作是样本属于对应标签的概率，对应的也就是计算\(w_\infty = w_0M^\infty\)的结果，其中\(w_0\)是除了\(w_{0j}=1\)以外的全0向量
不失一般性地，可以将状态进行重组，将转移矩阵重新变化为如下形式的矩阵 \[ M = \left[\begin{matrix} A & B \\ 0 & I\end{matrix}\right] \] 该矩阵的n次幂有如下形式 \[ M^n = \left[\begin{matrix}A^n & (A^{n-1} + \ldots + I)B \\ 0 & I\end{matrix}\right] = \left[\begin{matrix}A^n & \left(\sum_{u=0}^{n-1}A^u\right) \\ 0 & I\end{matrix}\right] \]
由于 \[ A^\infty = 0, \sum_{u=0}^\infty A^\mathsf{T} = (I-A)^{-1} \]
因此从\(x_j\)开始的随机游走最终在第\(i\)个吸收状态的概率是\([(I-A)^{-1}B]_{ji}\)
