【概述】

无论是基于 VC 维还是 Rademacher 复杂度来推导泛化误差界，所得到的结果均与具体学习算法无关，对所有学习算法都适用，这使得人们能够脱离具体学习算法的设计来考虑学习问题本身的性质，但在另一方面，若希望获得与算法有关的分析结果，则需另辟蹊径，稳定性分析（Stability Analysis）就是这方面中的一个方向

【基本定义】

【概述】

对于线性链条件随机场的预测问题，即：已知线性链条件随机场 $P(Y|X)$ 和输入序列 $x$，求条件概率最大的输出序列 $y^{*}$，即对输入序列进行标注

条件随机场的预测算法与隐马尔可夫模型的预测算法相似，采用 Viterbi 算法，即采用动态规划求概率最大路径，一条路径对应一条状态

【概述】

对于线性链条件随机场的学习问题，即：已知线性链条件随机场 $P(Y|X)$，估计 $P(Y|X)$ 的参数，该问题本质上是无监督学习中的概率估计问题

其学习方法有改进的迭代尺度法 IIS、梯度下降法、拟牛顿法等，这里仅介绍使用改进的迭代尺度法 IIS 和拟牛顿法对线性链条件随机场的学习

【概述】

在 PAC 学习理论概述 中，介绍了 PAC 学习理论，由于恰 PAC 学习并不实际，因此更重要的是研究假设空间 $\mathcal{H}$ 与概念类 $\mathcal{C}$ 不同的情景，即在给定 $n$ 个样本的训练集 $D$ 时，找出满足误差参数 $\epsilon$ 的假设

在 $|\mathcal{H}|$ 无限时，称假设空间 $\mathcal{H}$ 为无限假设空间，现实学习任务所面临的通常都是无限假设空间，例如实数域中的所有空间、$\mathbb{R}^{d}$​ 空间中的所有线性超平面等，要想对该种情形的可学习性进行研究，就需要度量假设空间的复杂度，最常见的方法就是考虑假设空间的 VC 维（Vapnik-Chervonenkis Dimension）

【基本概念】

数据、信号

数据，是传送信息的实体，是有意义的符号序列

【概述】

在 PAC 学习理论概述 中，介绍了 PAC 学习理论，由于恰 PAC 学习并不实际，因此更重要的是研究假设空间 $\mathcal{H}$ 与概念类 $\mathcal{C}$ 不同的情景，即在给定 $n$ 个样本的训练集 $D$ 时，找出满足误差参数 $\epsilon$ 的假设

在 $|\mathcal{H}|$ 有限时，称假设空间 $\mathcal{H}$ 为有限假设空间，其可分为两种情形：

【概述】

对于线性链条件随机场的概率计算问题，即：给定线性链条件随机场 $P(Y|X)$，输入序列 $x$ 和输出序列 $y$，计算条件概率 $P(Y_i=y_i|x)$ 和 $P(Y_{i-1}=y_{i-1},Y_i=y_i|x)$，以及相应的数学期望

与隐马尔可夫模型类似，引入前向向量与后向向量，递推的计算条件概率以及期望值，这样的算法称为前向-后向算法（Forward-backward Algorithm）

【概述】

计算学习理论（Computational Learning Theory）是研究关于通过计算来进行学习的理论，即机器学习的理论基础，其目的是分析学习任务的困难本质，为学习算法提供理论保证，并根据分析结果指导算法设计

计算学习理论中最基本的就是概率近似正确（Probably Approximately Correct，PAC）学习理论，其给出了一个抽象地刻画机器学习能力的框架，基于这个框架能够对很多重要问题进行理论探讨，例如研究某任务在什么样的条件下可习得较好的模型、某算法在什么样的条件下可进行有效的学习、需要多少训练样本才能得到较好的模型等

【概述】

条件随机场（Conditional Random Field）是给定随机变量 $X$ 的条件下，随机变量 $Y$ 的马尔可夫随机场

这里仅介绍定义在线性链上的特殊的条件随机场，即线性随机场（Linear Chain Conditional Random Field），其在机器学习中常用于标注问题

【TCP/IP 模型】

ARPA 在研究 ARPAnet 时提出了 TCP/IP 模型，其由于得到广泛应用而成为事实上的国际标准

TCP/IP 模型从低到高依次为：网络接口层、网际层、传输层、应用层