机器学习、自然语言理解、神经网络与 Agent

本节导读

本节讲人工智能原理大纲的第 6 到第 9 条：机器学习与数据挖掘（实例学习、统计学习与支持向量机、关联规则、Bayes 方法），自然语言理解（词切分和语法分析），神经网络与遗传、群蚁等优化算法，Agent 与多 Agent 合作求解。

这一节内容多、面广，但能出计算的地方比较集中：信息增益、支持度与置信度、最大匹配分词、感知器权值调整、轮盘赌选择概率。概念部分要分清各种方法「解决什么问题、靠什么思想」。

机器学习与实例学习

机器学习研究计算机怎样获取新的知识和技能、改进自身的性能。按学习方法可分为机械学习、示教学习、类比学习、归纳学习、解释学习等；按有无标注可分为有监督学习和无监督学习。

实例学习属于归纳学习：从给定的正例和反例中归纳出一般的概念或规则。变型空间法用一般边界 G 和特殊边界 S 表示所有与已知样本一致的假设：正例使 S 一般化，反例使 G 特殊化，两者重合时就得到所求的概念。决策树学习（ID3 算法）每次选信息增益最大的属性作为节点来划分样本：

$H(S) = -\sum_i p_i \log_2 p_i, \quad \text{Gain}(S, A) = H(S) - \sum_v \frac{\lvert S_v \rvert}{\lvert S \rvert} H(S_v)$H(S)=−∑i​pi​log2​pi​,Gain(S,A)=H(S)−∑v​∣S∣∣Sv​∣​H(Sv​)

其中 $p_i$pi​ 是第 $i$i 类样本所占的比例，$S_v$Sv​ 是属性 $A$A 取值为 $v$v 的样本子集。C4.5 算法改用信息增益率，以免偏向取值多的属性。

统计学习与支持向量机

统计学习理论研究有限样本下的学习问题，用 VC 维刻画学习机器的能力，提出结构风险最小化原则：同时控制训练误差和模型复杂度。支持向量机（SVM）就是在这一原则下发展起来的。

对线性可分的两类样本，SVM 寻找使分类间隔最大的分离超平面 $w \cdot x + b = 0$w⋅x+b=0，约束为 $y_i(w \cdot x_i + b) \ge 1$yi​(w⋅xi​+b)≥1，间隔为 $\dfrac{2}{\lVert w \rVert}$∥w∥2​。落在间隔边界上、决定超平面的样本叫支持向量。例如只有两个样本 $(1, 1)$(1,1)（负类）和 $(3, 3)$(3,3)（正类）时，它们都是支持向量，求得 $w = (0.5, 0.5)$w=(0.5,0.5)，$b = -2$b=−2，间隔为 $2\sqrt{2} \approx 2.83$22​≈2.83，正好等于两点间的距离。线性不可分时引入松弛变量和惩罚参数，允许少量样本越界；非线性问题用核函数（如多项式核、高斯径向基核）把样本映射到高维空间，再在那里求线性分离超平面。

数据挖掘、关联规则与 Bayes 分类

数据挖掘（知识发现）的过程一般是：数据清理、数据集成、数据选择、数据变换、数据挖掘、模式评估、知识表示。

关联规则 $X \Rightarrow Y$X⇒Y 有两个指标：支持度是同时包含 $X$X 和 $Y$Y 的事务占全部事务的比例；置信度是在包含 $X$X 的事务中，同时包含 $Y$Y 的比例，即 $\dfrac{\text{support}(X \cup Y)}{\text{support}(X)}$support(X)support(X∪Y)​。挖掘分两步：先找出支持度不低于最小支持度的频繁项集，再由频繁项集产生置信度不低于最小置信度的规则。Apriori 算法利用「频繁项集的子集一定频繁，非频繁项集的超集一定不频繁」逐层产生候选项集。

Bayes 分类按 $P(C \mid X) = \dfrac{P(X \mid C) P(C)}{P(X)}$P(C∣X)=P(X)P(X∣C)P(C)​ 把样本 $X$X 归到后验概率最大的类；朴素 Bayes 假设各属性在类别给定时相互独立，$P(X \mid C) = \prod_i P(x_i \mid C)$P(X∣C)=∏i​P(xi​∣C)。

自然语言理解

自然语言理解一般分几个层次：语音分析，词法分析（切分单词、确定词性），句法分析（确定句子的结构，得到句法树），语义分析（确定词语和句子的意义），语用分析（结合语境和说话人的意图理解语言）。

汉语没有词间空格，先要做词切分。正向最大匹配法从左往右，每次取词典中能匹配的最长词；逆向最大匹配法从右往左做同样的事；两者结合叫双向匹配。切分歧义有交集型（如「研究生命」中「研究生」「生命」交叉）和组合型（如「马上」可以是一个词，也可以拆成两个词）。句法分析常用短语结构文法（上下文无关文法），例如规则 S → NP VP，NP → A N 或 N，VP → V NP；较复杂的分析可用扩充转移网络（ATN）。

神经网络

人工神经元把各输入加权求和，减去阈值后经激活函数输出：$y = f\left(\sum_i w_i x_i - \theta\right)$y=f(∑i​wi​xi​−θ)，激活函数常用阶跃函数或 Sigmoid 函数 $f(x) = \dfrac{1}{1 + e^{-x}}$f(x)=1+e−x1​。例如输入 $(1, 0, 1)$(1,0,1)、权值 $(0.6, 0.4, -0.3)$(0.6,0.4,−0.3)、阈值 $0.2$0.2、阶跃激活时，加权和减阈值为 $0.1 \ge 0$0.1≥0，输出 1。

单层感知器的学习规则为 $w_i \leftarrow w_i + \eta(t - y)x_i$wi​←wi​+η(t−y)xi​（$t$t 为期望输出，$y$y 为实际输出，$\eta$η 为学习率），它只能解决线性可分问题，不能实现异或。BP 网络是多层前馈网络，用误差反向传播和梯度下降调整各层权值。Hopfield 网络是反馈型网络，可用于联想记忆和优化计算（如旅行商问题）。卷积神经网络等深度学习模型属于拓展，大纲未单列，了解即可。