【基本概念】

数据、信号

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

【概述】

在 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 模型从低到高依次为：网络接口层、网际层、传输层、应用层

【概述】

国际标准化组织 ISO 提出的网络体系结构模型称为开放系统互连参考模型（OSI/RM），通常简称为 OSI 参考模型，其有七层，从下到上依次为物理层、数据链路层、网络层、传输层、会话层、表示层、应用层

对于前三层来说，统称为通信子网，其是为了联网而附加的通信设备，用于完成数据的传输功能；对于高三层来说，统称为资源子网，其相当于计算机系统，完成数据的处理功能；传输层承上启下，将通信子网与资源子网连接起来

【概述】

对于隐马尔可夫模型的预测问题，即：已知模型 $\lambda=(A,B,\pi)$ 和观测序列 $O=(o_1,o_2,\cdots,o_T)$，求对给定观测序列条件概率 $P(I|O)$ 最大的状态序列 $I=(i_1,i_2,\cdots,i_T)$

有两种预测算法：

【概述】

对于隐马尔可夫模型的学习问题，即：已知观测序列 $O=(o_1,o_2,\cdots,o_T)$，估计模型 $\lambda(A,B,\pi)$ 的参数，使得在该模型下观测序列概率 $P(O|\lambda)$ 最大，该问题本质上是无监督学习中的概率估计问题

根据训练数据包括观测序列和对应的状态序列，还是只有观测序列，可以分别由极大似然估计和 EM 算法来实现

【概述】

对于隐马尔可夫模型的概率计算问题，即：给定隐马尔可夫模型 $\lambda=(A,B,\pi)$ 和观测序列 $O=(o_1,o_2,\cdots,o_T)$，计算在模型 $\lambda$ 下观测序列 $O$ 出现的概率 $P(O|\lambda)$

有以下两种概率计算方法：