人工智能引论课

阅读须知

此文档以浙江大学大二春夏开设的《人工智能引论》的内容为基础，撰写.

参考书籍《人工智能导论：模型与算法》：作者：吴飞

知识表达与推理

命题逻辑是数理逻辑的基础

命题逻辑

• 命题逻辑（proposition logic）是应用一套形式化规则对以符号表示的描述性陈述（称为命题）进行推理的系统.

原子命题：指不包含其他命题作为其组成部分的命题

通过命题联结词（connectives）对已有命题进行组合，得到新命题，称为复合命题（compound proposition）

命题的运算逻辑等价推理规则范式（normal form）

命题的运算有以下几种

• 命题合取 conjunction. \(p \land q\)
• 命题析取 disjunction. \(p \lor q\)
• 命题否定 negation. \(\lnot p\)
• 命题蕴含 implication. \(p \to q.\quad p为前件, \quad q为后件\)
• 命题双向蕴含 bi-implication. \(p \leftrightarrow q\)

在所有情况下都具有相同真假结果

• 逆否命题：\((\alpha \to \beta) \equiv \lnot \beta \to \lnot \alpha\)
• 蕴含消除：\((\alpha \to \beta) \equiv \lnot \alpha \lor \beta\)
• 双向消除：\((\alpha \leftrightarrow \beta) \equiv (\alpha \to \beta) \land(\beta \to \alpha)\)
• ...

按照某种策略从前提出发推出结论的过程。常见推理规则：

• 假言推理 Modus Ponens：\(\frac{\alpha \Rightarrow \beta,\quad \alpha}{\beta}\)
• 与消解 And-Elimination：\(\frac{\alpha_1 \land \alpha_2 \land \dots \land \alpha_n}{\alpha_i(q \leq i \leq n)}\)
• 与导入 And-Introduction：\(\frac{\alpha_1,\alpha_2,\dots,\alpha_n}{\alpha_1 \land \alpha_2, \land \dots, \land \alpha_n}\)
• 双重否定 Double-Negation Elimination：\(\frac{\lnot \lnot \alpha}{\alpha}\)
• 单项消解或单项归结 Unit Resolution：\(\frac{\alpha \lor \beta, \lnot \beta}{\alpha}\)
• 消解或归结 Resolution：\(\frac{\alpha \lor \beta, \lnot \beta \lor \gamma}{\alpha \lor \gamma}，\frac{\alpha_1 \lor \alpha_2 \lor \dots \lor \alpha_m, \lnot \beta}{\alpha_1 \lor \alpha_2 \lor \dots \lor \alpha_{k-1}\lor \alpha_{k+1}\lor \dots \lor \alpha_m}(\lnot \alpha_k = \lnot \beta)\)

是把命题公式化为一种标准的形式，作用是可以进行两个命题的等价判断

• 析取范式 disjunctive normal form (DNF)：有限个简单合取式构成的析取式称为析取范式
• 合取范式 conjunctive normal form (CNF)：有限个简单析取式构成的合取式称为合取范式
• 命题公式的 DNF 和 CNF 都是不唯一的

谓词逻辑

命题逻辑无法表达局部与整体、一般与个别的关系，因此我们需要谓词逻辑来丰富我们的表达.

• 将原子命题进一步细化，分解出三个核心概念：个体、谓词和量词，来表达个体与总体的内在联系和数量关系，就是谓词逻辑（predicate logic）的研究内容

个体谓词量词

个体是指所研究领域中可以独立存在的具体或抽象的概念

• 规定：用小写字母\(a\)至\(w\)表示个体常量（\(x,y,z\)表示个体变量）
• 个体的取值范围称为个体域

谓词是用来刻画个体属性或者描述个体之间的关系存在性的元素，其值为真或假

• 包含一个参数的谓词称为一元谓词，表示一元关系
• 包含多个参数的谓词称为多元谓词，表示个体间的多元关系
• 规定：用\(A(\cdots)至Z(\cdots)\)表示谓词

全称量词和存在量词统称为量词

• 全称量词：符号\(\forall\)
• 存在量词：符号\(\exists\)
• 全称量词的描述性是可以用相应的存在量词的藐视形式替换
• 约束变量：在全称量词或存在量词约束条件下的变量符号
• 自由变量：不受全称量词或存在量词约束的变量符号
• 定理：自由变元既可以存在于量词的约束范围之内，也可以存在于量词约束范围之外，即：
  • \((\forall x)(A(x) \lor B) \equiv (\forall x)A(x) \lor B\)
  • \((\forall x)(A(x) \land B) \equiv (\forall x)A(x)\land B\)
  • \((\exists x)(A(x) \lor B) \equiv (\exists x)A(x) \lor B\)
  • \((\exists x)(A(x) \land B)\equiv (\exists x)A(x) \land B\)
• 定理：在约束变元相同的条件下，量词的运算满足分配律
• 定理：当公式中存在多个量词时，若多个量词都是全称量词或者都是存在量词，则量词位置可以互换；若多个量词中既有全称量词又有存在量词，则量词位置不可以随意互换

• 项：项是描述对象的逻辑表达式，递归定义：

  • 常量符号和变量符号是项
  • 若\(f(x_1,x_2,\cdots,x_n )\)是n元函数符号，\(t_1,t_2,\cdots,t_n\) 是项，则\(f(t_1,t_2,\cdots,t_n)\)是项
  • 有限次数地使用上述规则产生的符号串是项

• 原子谓词公式： 若\(P(x_1,x_2,\cdots,x_n)\)是n元谓词，\(t_1,t_2,\cdots,t_n\)是项，则称\(P(t_1,t_2,\cdots,t_n)\)是原子谓词公式，简称原子公式

• 合式公式：由逻辑联结词和原子公式构成地用于陈述事实地复杂语句，又称谓词公式：

  • 命题常项，命题变项，原子谓词公式都是合式公式
  • 通过逻辑联结词联结合式公式得到的也是合式公式
  • 如果\(A\)是合式公式，\(x\)是个体变项,则\((\exists x)A(x),(\forall x) A(x)\)也是合式公式
  • 有限次数地使用上述规则

• 推理规则（\(A(x)\)是谓词公式，\(x\)和\(y\)是变元，\(a\)是常量符号）

  • 全称量词消去 universal instantiation (UI)：\((\forall x) A(x) \Rightarrow A(y)\)
  • 全称量词引入 universal generalization (UG)：\(A(y) \Rightarrow (\forall x)A(x)\)
  • 存在量词小区 existential instantiation (EI)：\((\exists x)A(x) \Rightarrow A(a)\)
  • 存在量词引入 existential generalization （EG)：\(A(a) \Rightarrow (\exists x)A(x)\)

概率图谱推理

贝叶斯网络

• 用一个有向无环图（directed acyclic graph）来表示，其用有向边来表示节点与节点之间的单向概率依赖

局部马尔可夫性（local Markov property）,即在给定一个节点的父节点的情况下，该父亲节点有条件地独立于它的非后代节点。 W

马尔可夫网络

• 表示成一个无向图的结构，其用无向边来表示节点和节点之间的相互概率依赖

给定一个由若干规则构成的集合，集合中每条推理规则赋予一定权重，则可如下计算某个断言x成立的概率

\[P(X=x)=\frac{1}{Z}exp(\sum_iw_in_i(x)=\frac{1}{Z}\prod_i\phi_i(x_{\{i\}})^{n_i(x)}\]

其中\(n_i(x)\)式在推导\(x\)中所涉及第\(i\)条规则的逻辑取值（为1或0）,\(w_i\)是该规则对应的权重，\(Z\)是一个固定的常量，可由下式计算：

\[Z=\sum_{x\in X}exp(\sum_iw_in_i(x))\]

知识图谱推理

• 知识图谱（knowledge graph）由有向图（directed graph）构成，被用来描述现实世界中实体及实体之间的关系
  • 每个节点是一个实体，边表示关系
  • 两个节点和连接边可表示为形如 <left_node, relation, right_node >的三元组形式，也可表示为一阶逻辑（first order logic, FOL）的形式

知识图谱推理中有两个具有代表性的方法：

归纳逻辑程序设计（inductive logic programming, ILP）

• ILP使用一阶谓词逻辑进行知识表示，通过修改和扩充逻辑表达式对现有知识进行归纳，完成推理内容

• FOIL(First Order Inductive Learner)算法是ILP的代表性算法，通过序贯覆盖学习推理规则

• 只能在已知两个实体的关系且确定其关系与目标谓词相悖时，才能将这两个实体用于构建目标谓词的反例.

在进行推理之前我们首先要定义信息增益值(information gain)

\[FOIL_Gain=\widehat{m_+}\cdot(log_2\frac{\widehat{m_+}}{\widehat{m_+}+\widehat{m_-}}-log_2\frac{m_+}{m_++m_-})\]

Picture

路径排序算法（path ranking algorithm, GRA）

• 将实体之间的关联路径作为特征来学习目标关系的分类器
• 特征提取：生成并选择路径特征集合。（随机游走、广度优先搜索、深度优先搜索）
• 特征计算：计算每个训练样例的特征值\(P(s\to t;\pi_j)\)。该特征值可以表示从实体节点s出发，通过关系路径\(\pi_j\)到达实体节点\(t\)的概率；也可以表示为布尔值，表示实体\(s\)到实体\(t\)之间是否存在路径\(\pi_j\)；还可以是实体\(s\)和实体\(t\)之间路径出现频次、频率等。
• 分类器训练：根据训练样例的特征值，为目标关系训练分类器。当训练好分类器后，即可将分类器用于推理两个实体之间是否存在目标关系

因果推理

• 辛普森悖论：在某个条件下的两组数据，分别讨论时都会满足某种趋势，可是一旦合并考虑，却可能导致相反的结论。（引入了混杂因素）

搜索求解

搜索算法的基础

• 评价指标

  • 完备性：当问题存在解时，算法能否保证找到一个解
  • 最优性：能否保证找到的第一个解是最优解
  • 时间复杂度
  • 空间复杂度

• 搜索算法框架

  F <- {根节点}
  while F ≠ ∅ do
      n <- pick_from(F)
      F <- F - {n}
      if goal_test(n) then
          return n.path
      end
      F <- F ∪ successor_nodes(n)
  end
  

• pick_from决定扩展结点的顺序, successor_nodes 决定哪些节点可被放入边缘集合（fringe set, 所有候选结点集合，也称开表, open list）以在后面扩展

• 每次从边缘集合中取出最上层（最浅）的节点时是广度优先搜索（breadth first search, BFS）
• 每次从边缘集合中取出最下层（最深）的节点时是深度优先搜索（depth first search, DFS）
• 放弃扩展部分节点的做法称为剪枝（pruning）
• 图搜索：不允许存在环路

搜索算法的分类

无信息搜索

• 广度优先搜索
• 深度优先搜索

有信息搜索

• 贪心最佳优先搜索
• A*搜索
• 最大最小搜索
• Alpha-Beta剪枝搜索
• 蒙特卡洛树搜索

搜索算法的形式化描述

• 状态(state)（影响下一步决策的信息）
• 动作(action) (状态转移所采取的行为)
• 状态转移(state transition)（将状态发生变化）
• 路径(path) (状态转移的序列)
• 代价(cost) (状态转移的开销)
• 目标测试(goal test) (算法的终止条件)

符号	含义
b	分支因子，搜索树中每个节点最大的分支数目
d	根节点到最浅的目标节点的路径长度
m	搜索树中路径的最大可能长度
n	状态空间中状态的数量

搜索算法的优化

• 优先扩展哪些结点
• 放弃扩展哪些结点
• 求解近似最优解

启发式搜索

利用一些功能辅助算法做出决策的额外信息的搜索算法被称为启发搜索（heuristic search），或有信息搜索（informed search）

辅助信息	用途
评价函数(evaluation function) f(n)	选择后继结点,评价函数值越小，被挑选的优先级越高
启发函数(heuristic function)	用于估计结点\(n\)距离达到目标还需要付出多少代价

贪婪最佳优先搜索（greedy best-first search, GBFS）

• 优先扩展距离目标近的结点，即令\(f(n) = h(n)\)
• 不排除环路的贪婪最佳优先搜索算法是不完备的
• 排除环路的贪婪最佳优先搜索算法是完备的，但不一定最优
• 最坏情况下的事件复杂度和空间复杂度均为\(O(b^m)\)

A*算法

对启发函数的要求

• 可容性（admissible）：对于任意结点n，有\(ℎ(n)≤ℎ^∗(n)\)，如果n是目标结点，则有\(ℎ(n)=0\)。如表3.3所示， \(ℎ^∗(n)\)是从结点n出发到达终止结点所付出的（实际）最小代价。可以这样理解满足可容性的启发函数，启发函数不会过高估计（over-estimate）从结点𝑛到终止结点所应该付出的代价（即估计代价小于等于实际代价）。

• 一致性（consistency）：启发函数的一致性指满足条件\(ℎ(n)≤c(n, a, n^′)+ℎ(n′)\)，这里\(c(n, a, n^′)\)表示结点n通过动作a到达其相应的后继结点\(n′\)的代价(三角不等式原则)。

• 满足一致性则一定满足可容性

若启发函数是可容的，A*算法是最优的

假设\(A*\)算法找到的第一个终止结点为\(𝑛\)。对于此时边缘集合中任意结点\(𝑛′\)，根据算法每次扩展时的策略，即选择评价函数取值最小的边缘结点进行扩展，有\(𝑓(𝑛)≤𝑓(𝑛^′ )\)。由于\(A*\)算法对评价函数定义为\(𝑓(𝑛)=𝑔(𝑛)+ℎ(𝑛)\)，且\(ℎ(𝑛)=0\)，有\(𝑓(𝑛)=𝑔(𝑛)+ℎ(𝑛)=𝑔(𝑛)，𝑓(𝑛^′ )=𝑔(𝑛^′ )+ℎ(𝑛^′)\)，综合可得

\[𝑔(𝑛)≤𝑔(𝑛^′ )+ℎ(𝑛^′ )≤𝑔(𝑛^′ )+ℎ^∗ (𝑛^′)\]

其中\(𝑔(𝑛)\)为从起始结点到结点𝑛所对应路径的代价，\(𝑔(𝑛^′ )+ℎ^∗ (𝑛^′)\)表示从初始结点出发经过结点𝑛′到达终止结点的最小代价。也就是说此时扩展其他任何一个边缘结点都不可能找到比结点\(𝑛\)所对应路径代价更小的路径，因此结点𝑛对应的是一条最短路径，即算法满足最优性。

对抗搜索

智能体不唯一，解决信息确定、全局可观察、轮流行动、输赢收益零和的博弈问题，求解这样问题的算法称为对抗搜索（adversarial search）或博弈搜索（game search）

最大最小搜索

• 最大最小搜索（minmax search）是求解对抗搜索问题的基本算法
• 该算法假设两名玩家在决策时总是理性地倾向于最大化自己的得分（最小化对方得分）

完备性	√	时间复杂度	\(O(b^m)\)
最优性	√	空间复杂度	\(O(bm)\)

优点

• 在对手也尽力的情况下，可获得最优
• 简单有效

缺点

• 若搜索树极大，无法在有效时间内返回结果

Alpha-Beta剪枝搜索

蒙特卡洛搜索

赌博机问题

先来看一个赌博机问题: 假设现在有K个赌博机，每个赌博机有一个摇臂。每次拉动一个赌博机的摇臂，赌博机会随机吐出一些硬币或不吐出硬币，将所吐出的硬币的币值用收益分数来表示。现在有τ(τ>K)次拉动摇臂的机会，那么该如何选择赌博机、拉动τ次赌博机摇臂，能够获得更多的收益分数呢？

求解方法

最简单的想法便是将K个赌博机的摇臂都拉动一遍，再依次选择收益分数最高的赌博机。但这会有问题，由于每个赌博机给出硬币的概率是随机的，因此，下一次的拉动不一定伴随可观的收益分数.

为了解决这个问题，我们先作一些定义:

• 状态: 每个被摇动的摇臂为一个状态，记K个状态分别为\(\{s_1,s_2,\cdots,s_K\}\),初始状态记为\(s_0\).
• 动作: 对应着摇动一个赌博机的摇臂.\(\{a_1,a_2,\cdots,a_K\}\)
• 状态转移: 选择动作\(a_i(1\leq i\leq K)\)后，将状态改变为\(s_i\).
• 奖励(reward): 假设从第i个赌博机获得收益分数的分布为\(D_i\),其均值为\(\mu_i\).因此第t次的收益分数\(\widehat{r_t}\)服从分布\(D_{l_t}\)
• 悔值（regret）函数: 根据前T次动作，定义如下函数:

\[ρ_T=T\mu^*-\sum^T_{t=1}\widehat{r_t}\]

其中\(\mu^* = max_{i=1,\cdots,K}\mu_i\).

这时，问题求解的目标就转化为最小化悔值函数的期望.

贪心算法策略

记，在过去\(t-1\)次行动中，摇动第\(i\)个赌博机的次数为\(T_{(i,t-1)}\).则可以得到其在过去\(T_{(i,t-1)}\)次摇动中的收益分数平均值为\(\hat{x_{i,T_{(i,t-1)}}}\).于是，在第\(t\)步，只需要选择平均值最大的赌博机就行.

• 缺点：只是利用已知结果，而缺少探索.

根据霍夫丁不等式,我们可以得到以下策略：

\[ l_{t} = \text{argmax}_{i} \overline{X}_{i,T_{(i,t-1)}} + C\sqrt{\frac{2lnt}{T_{(i,t-1)}}} \]

由于这个算法利用蒙特卡洛法通过采样来估计每个动作优劣，因此它被称为蒙特卡洛树搜索（Monte-Carlo Tree Search）算法

想要说清楚蒙特卡洛算法，我们还需要定义几个概念

• 选择(selection): 选择指算法从搜索树的根节点开始，向下递归选择子节点，直至到达叶子节点或者到达具有还未被扩展过的子节点的节点L。这个向下递归选择过程可由UCB1算法来实现，在递归选择过程中记录下每个节点被选择次数和每个节点得到的奖励均值。
• 扩展（expansion）：如果节点 L 不是一个终止节点（或对抗搜索的终局节点），则随机扩展它的一个未被扩展过的后继边缘节点M。
• 模拟（simulation）：从节点M出发，模拟扩展搜索树，直到找到一个终止节点。模拟过程使用的策略和采用UCB1算法实现的选择过程并不相同，前者通常会使用比较简单的策略，例如使用随机策略。
• 反向传播（Back Propagation）：用模拟所得结果（终止节点的代价或游戏终局分数）回溯更新模拟路径中M以上（含M）节点的奖励均值和被访问次数。

机器学习

• 机器学习的目标是从原始数据中提取特征，学习一个映射函数\(f\)将上述特征（或原始数据）映射到语义空间，寻找数据和任务目标之间的关系

机器学习种类

• 监督学习(supervised learning)
  • 数据有标签、一般为回归或分类等任务
• 无监督学习(un-supervised learning)
  • 数据无标签、为聚一般类或若干降维任务
  • 半监督学习则是依赖于部分被标注的数据
• 强化学习(reinforcement learning)
  • 序列数据决策学习，一般为与从环境交互中学习

监督学习

对于识别任务：从已知数据分布推出标准.

• 在训练过程中希望映射函数在训练数据集上得到所有样本的”损失和“最小
• 主要的监督学习方法：
  • 判别方法（discriminative approach）
    • 直接学习判别函数\(f(x)\)或者脚尖概率分布\(P(Y|X)\)作为预测的模型
    • 典型判别模型包括回归模型、神经网络、支持向量机和Ada boosting
  • 生成方法（generative approach）
    • 从数据中学习联合概率分布\(P(X,Y)\)（通过似然概率\(P(X|Y)\)和类概率\(P(Y)\)乘积来求）
    • 生成模型典型方法为贝叶斯方法、隐马尔可夫链
    • 难点在于联合分布概率或似然概率很难求

回归分析

一元线性回归

符号表示

• m: 训练集样本数
• x：输入变量/特征
• y：输出变量/目标变量
• （x，y）：一个训练样本
• \((x^{(i)},y^{(i)})\):第i个训练样本
• h:代表学习算法的解决方案或函数也称为假设

代价函数

• 损失函数在整个训练集上的平均

单变量线性回归

\[\frac{1}{2m}\sum^m_{i=1}(h_\theta (x^{(i)})-y^{(i)})^2\]

梯度下降

\[\theta_j:= \theta_j - \alpha \frac{\partial}{\partial \theta_j}J(\theta_0,\theta_1)\]

类型

• 批量梯度下降(Batch Gradient Descent, BGD) ^e0f401
  • 每一步使用整个训练集的全部样本
• 随机梯度下降(Stochastic Gradient Descent,SGD)
  • 每次只用一个样本，收敛快，但可能出现目标函数震荡不稳定线性
• 小批量梯度下降(Mini-batch Gradient Descent, MBGD)
  • 使用一部分样本，最常用

多元线性回归

• 有\(m\)个训练数据\(\{(x_i,y_i)\}^m_{i=1}\).要找到参数\(\textbf{a}\),使线性函数\(f(x_i) = a_0 + \textbf{a}^Tx_i\)最小化

均方误差函数

最小化均方误差函数

\[J_m=\frac{1}{m}\sum^m_{i=1}(y_i-f(x_i))^2=(\textbf{y}-\textbf{X}^T\textbf{a})^T(\textbf{y-}\textbf{X}^T\textbf{a})\]

矩阵来表示所有训练数据和数据标签

\[X=[x_1,\cdots,x_m], \textbf{y} = [y_1,\cdots,y_m]\]

均方误差函数可以表示为:

\[J_m(a)=(\textbf{y}-X^Ta)^T(\textbf{y}-X^Ta)\]

对所有参数\(a\)求导可得：

\[\nabla J(a)=-2X(y-X^Ta)\]

从而推得

\[a=(XX^T)^{-1}X\textbf{y}\]

逻辑回归 / 对数几率回归

• 线性回归对离群点非常敏感，导致模型不稳定，为了缓解这个问题可以考虑逻辑斯蒂回归（logistic regression）

• 研究某一事件发生得概率\(P=P(y=1)\)与若干因素之间的关系

  \[p=\beta_0+\beta_1x_1+\cdots+\beta_q x_q\]

  logit函数(逻辑变换)

  \[f(p)=ln\frac{\pi(x)}{1-\pi(x)}=ln\frac{p}{1-p}\]
  • 当概率在0-1取值时,Logit可以取任意实数，避免了线性概率模型的结构缺陷 logistic变换
  \[ln\frac{p}{1-p}\in(-\infty,+\infty)\]

  logistic回归模型

  • 在回归模型中引入sigmoid函数的一种非线性回归模型
  \[ln\frac{p}{1-p}=\beta_0+\beta_1x_1+\cdots+\beta_qx_q\]

  优势比(Odds Ratio)——事件发生与不发生的概率比

  \[OR=\frac{p}{1-p}=e^{\beta_0+\beta_1x_1+\cdots+\beta_qx_q}\]

• 在回归模型中引入 sigmoid 函数，逻辑斯蒂回归模型

\[y=\frac{1}{1+e^{-Z}}=\frac{1}{1+e^{-(w^Tx+b)}}\]

其中\(\frac{1}{1+e^{-Z}}\)是sigmoid函数. \(\frac{p}{1-p}\)被称为几率(odds)，反应了输入数据被作为正例的相对可能性.

• 逻辑斯蒂回归函数的输出具有概率意义，一般用于二分类问题
• 逻辑斯蒂回归是一个线性模型，在预测时可以计算线性函数\(\textbf{w}^T\textbf{x} + \textbf{b}\)取值是否大于 0 来判断输入数据的类别归属
• 求解参数的典型做法是最大化对数似然（log likelihood）函数 似然函数：假设每一个样本数据是独立同分布

\[ {\cal L}(\theta|\mathcal{D})=\mathfrak{p}(\mathcal{D}|\theta)=\prod_{i=1}^{n} \mathfrak{p}(y_{i}|x,\theta)=\prod_{i=1}^{n}\left(h_{\theta}(x_{i})\right)^{y_ {i}}\left(1-h_{\theta}(x_{i})\right)^{1-y_{i}} \]

\[ l(\theta)=\log\left(L(\theta|\mathcal{D})\right)=\sum_{i}^{n}y_{i}\log\left(h_ {\theta}(x_{i})\right)+(1-y_{i})\log(1-h_{\theta}(x_{i})) \]

最大似然估计目的是计算似然函数的最大值，而分类过程是需要损失函数最小化。因此在上式前加一个负号得到损失函数(cross entropy, 交叉熵)

\[ {\cal T}(\theta)=-1(\theta)=-\log\big{(}L(\theta|\mathcal{D})\big{)} \]

\[ =-\big{(}\sum_{i=1}^{n}y_{i}\log\big{(}h_{\theta}(x_{i})\big{)}+( 1-y_{i})\log(1-h_{\theta}(x_{i}))\big{)} \]

• 多分类可以将其推广为多项逻辑斯蒂回归模型，即 softmax 函数

CART（Classification And Regression Tree）

实例划分 - 通过树形结构进行分类的方法 - 每个非叶子结点表示对分类目标在某个属性上的一个判断，每个分支代表基于该属性做出的一个判断，每个叶子结点代表一种分类结果 - 决策树将分类问题分解为若干个基于单个信息的推理任务，采用树状结构来逐步完成决策判断 - 建立决策树的过程，就是不断选择属性值对样本集进行划分、直至每个子样本为同一个类别 - 对于较大数据集，需要理论和方法来评价不同属性值划分的子样本集的好坏程度

• 决策树的构建

  • 性能好的决策树随着划分不断进行，决策树分支结点样本集的纯度会越来越高，即所包含样本尽可能属于相同类别
  • 信息熵（entropy） 可以用来衡量样本集和纯度，越大说明不确定性越大纯度越低
    • 划分样本集前后信息熵的减少量被称为信息增益（information gain） 用来衡量样本复杂度减少的程度
  • 设置分类停止条件：如果划分后的不同子样本集都只存在同类样本，那么停止划分

• 一般而言，信息增益偏向选择分支多的树，一些场合容易导致模型过拟合

  • 一个直接的想法是对分支过多进行惩罚，即另一个纯度衡量指标

• 收集待分类的数据（所有属性完全标注）

• 设计分类原则

• 分类原则选择

逐层使熵减小

给定有关某概念的正例和负例的集合S.对此BOOLEAN分类的熵为：

\[Entropy(S)= -pos \log_2(pos)-neg\log_2(neg)\]

其中"pos"和"neg"分别表示S中正例和负例的比例。并定义:\(0\log_2(0)=0\)

如果分类器有c个不同的输出，则：

\[Entropy(S)=-\sum^c_{i=1}p_i\log_2{(p_i)}\]

\(p_i\)表示S中属于类i的比例

实例集合S中属性A的信息增益为:

\[Gain(S,A) =Entropy(S)-\sum(|S_V|/|S|) Entropy(S_V)\quad v\in values\quad of\quad A\]

\(S_V\)表示S的子集，其属性A的值为V

• 选择具有最高的增益的属性，作为分裂属性.

经典的属性划分方法： - 信息增益 - 信息增益对可取值数目较多的属性有所偏好 - 增益率（Gain-ratio）

\[info=-\sum^n_{i=1}\frac{|D_i|}{|D|}\log_2\frac{|D_i|}{|D|}\]

\[Gain-raio=Gain(D,A)/info\]

- 启发式：先找信息增益高于平均水平的属性，再从中选取增益率最高的.

• 基尼指数(Gini指数) \(\(Gini(D)=1-\sum^K_{k=1}p_k^2\)\)

连续属性离散化（二分法）

第一步：假定连续属性α在样本集D上出现n个不同的取值，从小到大排列，记为 \(a^1,a^2,...a^n\)，基于划分点 \(t\)，可将D分为子集 \(D_i\) 和 \(D_i^{+}\)，其中 \(D_i\) 包含那些在属性α上取值不大于t的样本，\(D_i^{+}\) 包含那些在属性α上取值大于t的样本。考虑包含 \(n-1\) 个元素的候选划分点集合

\[ T_{a}\,=\,\left\{\frac{a^{i}+a^{i+1}}{2}\,\mid\,1\leq i\leq n-1\right\} \]

即把区间 \([a^{i},a^{i-1})\) 的中位点 \(\frac{a^{i}+a^{i+1}}{2}\) 作为候选划分点

第二步：采用离散属性值方法，考察这些划分点，选取最优的划分点进行样本集合的划分

\[Gain(D,a)=max_{t\in T_a}Gain(D,a,t)=max_{t\in T_a}Ent(D)-\sum_{\lambda\in\{-,+\}}\frac{|D^\lambda_t|}{|D|}Ent(D^\lambda_t)\]

决策树-剪枝处理

• 用“剪枝”来对付“过拟合” 基本策略

• 预剪枝

  • 降低过拟合风险
  • 显著减少训练时间和测试时间开销
  • 欠拟合风险

• 后剪枝

  • 先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点
  • 时间开销大

判断决策树泛化性能是否提升的方法

• 留出法：预留一部分数据用作“验证集”以进行性能评估

线性判别分析

• 线性判别分析（linear discriminant analysis, LDA）是一种基于监督学习的降维方法，也称为 Fisher 线性判别分析 （FDA）
• 对于一组具有标签信息的高位数据样本，LDA 利用其类别信息将其线性投影到一个低维空间熵，在低维空间中同一类别样本尽可能靠近，不同类样本尽可能彼此原理
  • 投影后类内方差最小，类间方差最大
• LDA 与主成分分析（PCA）紧密相关，都在寻找最佳解释数据的变量线性组合
• 对线性判别分析的降维步骤描述
  • 计算数据样本集中每个类别样本的均值
  • 计算以下两个矩阵：类内散度矩阵\(S_w\)(\(m_i\)为第i个类别中包含样本数据的均值):\(\(S_w = \sum^K_{i=1}\sum_{x\in class_i}(x-m_i)(x-m_I)^T\)\)类间散度矩阵\(S_b\):\(\(S_b=\sum^K_{i=1}\frac{N_i}{N}(m_i-m)(m_I-m)^T\)\)
  • 根据\(S_w^{-1}S_bW=\lambda W\)来求解\(S_w^{-1}S_b\)所对应前r个最大特征值所对应特征向量\((w_1,w_2,\cdots,w_r)\)，构成矩阵\(W\)
  • 通过矩阵\(W\)将每个样本映射到低维空间，实现特征降维
• PCA 是一种无监督学习的降维方法，LDA是监督学习
  • PCA 和 LDA 均是优化寻找特征向量\(\textbf{w}\)来实现降维
  • PCA 寻找投影后数据间方法最大的投影方向， LDA 寻找类内方差小、类间间隔大的投影方向
  • PCA 可以将 d 维数据降至小于 d 的任意维度
  • LDA 降维后得到维度与数据样本类别个数 K 有关， d维数据有K个类别，则降维维度小于或都等于\(min(K-1,d)\)