《高级人工智能》笔记

绪论

图灵测试

定义:

图灵测试指测试者与被测试者(一个人和一台机器)隔开的情况下,通过一些装置(如键盘)向被测试者随意提问。进行多次测试后,如果有超过30%的测试者不能确定出被测试者是人还是机器,那么这台机器就通过了测试,并被认为具有人类智能。

意义:

图灵测试推动了计算机科学和人工智能的发展。人工智能大体分为弱人工智能和强人工智能,目前大部分的研究成果都属于弱人工智能,如果有机器能通过图灵测试,那将标志着强人工智能的出现。

Occam’s Razor

Occam’s Razor(奥卡姆剃刀),这个原理称为“如无必要,勿增实体”,即“简单有效原理”。强调简约主义,切勿浪费较多东西去做,用较少的东西,同样可以做好的事情。

智能Agent

理性Agent:

对每一个可能的感知序列,根据已知的感知序列提供的证据和Agent具有的先验知识,理性Agent应该选择能使其性能度量最大化的行动。

PEAS

  • Performance(性能)
  • Environment(环境)
  • Actuators(执行器)
  • Sensors(传感器)

简单反射Agent

基于模型的反射Agent

基于目标的Agent

基于效用的Agent

搜索算法

启发式搜索

A*算法的定义:

A*算法是一种静态路网中求解最短路径最有效的直接搜索方法,也是解决许多搜索问题的有效算法。

公式表示为: f(n)=g(n)+h(n)

f(n) 是从初始状态经由状态n到目标状态的代价估计,

g(n) 是[状态空间中从初始状态到状态n的实际代价,

h(n) 是从状态n到目标状态的最佳路径的估计代价。

可允许的启发式函数:

h(n)是一个可采纳的启发式,即h(n)从不会过高估计到达目标的耗散。可采纳启发式是最优的,因为其认为求解问题的耗散是低于实际耗散的。

如果$h^(n)$为从节点n到目标节点的实际最优路径,h是可允许的(admissible)当且仅当:$h(n) \leqslant h^(n)$

对抗搜索

MAX-MIN搜索

方法:

  • 执行深度优先搜索,产生完备的状态空间搜索树;
  • 使用效用函数评估每个节点的的分布;
  • 在MIN节点,从子节点选择得分最低的节点扩展;
  • 在MAX节点,从子节点选择得分最高的节点扩展。

特点:

  • 每一步的执行结果是确定的;
  • 两个游戏者轮流进行操作;
  • 游戏者之间进行零和博弈;
  • 所有状态空间可知。

alpha​-beta剪枝

定义:

$\alpha$-$\beta$剪枝用于裁剪搜索树中对决策没有影响的不需要搜索的分枝,以提高运算速度。

定义$\alpha$ := 目前为止路径上发现的MAX的最佳选择;$\beta$ := 目前为止路径上发现的MIN的最佳选择。

搜索过程中不断更新$\alpha$和$\beta$的值,且当某个结点的值分别比目前的MAX的$\alpha$或MIN的$\beta$的值更差时,则裁剪此此节点剩下的分支。

问题:

  • 在求解过程中,每个节点都要写明alpha和beta值?还是只要写出MAX节点的alpha值和MIN节点的beta值?

下棋和打牌的不同点:

下棋是公开明面的博弈,对于算法而言当前的状态都是已知的;而牌存在着许多未知的情况,即有不确定性,在这种情况下进行搜索会产生巨大的状态空间,难以求解。

约束满足问题

时序模型

概率公式

全概率公式:
$$
P(A|B) = \frac{P(A)P(B|A)}{P(B)}
$$
贝叶斯公式:
$$
P(A_i|B) = \frac{P(A_i)
P(B|A_i)}{\sum_{i=1}^nP(A_i)P(B|A_i)}
$$
$P(A)$和$P(B)$为先验概率,可以根据以往经验和分析得到的概!率,不考虑与其他事件的联系。

$P(A|B)$则称为B发生后A的后验概率,注意式中事件B往往被认为是“因”,是给定的,也就是说P(B)往往是一个常数,分母P(B)可以去掉,贝叶斯公式又可以被表示为:
$$
P(A|B) = \alpha P(A)*P(B|A)
$$
上式中的$\alpha$表示归一化处理,保证概率和是1。

一般时序模型

模型简介:

我们建立一个时序模型如下,包含了我们所要解决的所有问题。

2656792-85a9f55baf9abc32

这个模型包含两个序列:一个是状态序列,用X表示;一个是观测序列(证据序列)用Y表示。状态序列反应了系统的真实状态,一般不能被直接观测,即使被直接观测也会引进噪声;观测序列是通过测量得到的数据,它与状态序列之间有规律性的联系。

举个例子,假设有一个人待在屋子里不知道外边有没有下雨,他于是观察进屋子里的人是否带伞,这里有没有下雨就是状态,有没有带伞就是观测。

两个基本假设:

马尔科夫假设:假设当前状态只与上一个状态有关,而与上一个状态之前的所有状态无关。公式为:
$$
P(X_{t+1}|X_{1:t}) = P(X_{t+1}|X_{t})
$$
观测假设:假设当前观测值只依赖于当前状态,与其他时刻的状态无关。公式为:
$$
P(Y_{t}|X_{1:t}) = P(Y_{t}|X_{t})
$$

时序模型中的推理

时序模型所要解决的是以下几个问题:

(1)滤波
$$
P(X_t|Y_{1:t})
$$
即根据现在及以前的所有测量数据,估计当前的状态。在雨伞那个例子中,根据目前为止过去进屋的人携带雨伞的所有观察数据,计算今天下雨的概率,这就是滤波。

(2)预测
$$
P(X_{t+k}|Y_{1:t}), k> 0
$$
即根据现在及现在以前的所有测量数据,估计未来某个时刻的状态。在雨伞的例子中,根据目前为止过去进屋的人携带雨伞的所有观察数据,计算从今天开始若干天后下雨的概率,这就是预测。

(3)平滑
$$
P(X_k|Y_{1:t}), 0 < k < t
$$
即根据现在及现在以前的所有测量数据,估计过去某个时刻的状态。在雨伞的例子中,意味着给定目前为止过去进屋的人携带雨伞的所有观察数据,计算过去某一天的下雨概率。

(4)最可能解释
$$
arg \max_{x_{1:t}}P(X_{1:t}|Y_{1:t}))
$$
即给出现在及现在以前的所有测量数据,找到最能最可能生成这些测量数据的状态序列。例如,如果前三天每天都出现雨伞,但第四天没有出现,最有可能的解释就是前三天下雨了,而第四天没下雨。最可能解释也被称为解码问题,在语音识别、机器翻译等方面比较有用,最典型的方法是隐马尔可夫模型。

(5)评估
$$
P(Y_{1:t}|X_{1:t}, \lambda)
$$
这里面的$\lambda$是指模型。这个公式意味着在该模型下,给定到目前为止的状态序列,计算输出特定观测序列的可能性。这其实是个评估问题,可以评估模型的好坏,概率越高,意味着模型越能反映观测序列与状态序列之间的联系,模型就越好。

(6)学习

学习$\lambda $,也即状态转移概率和观测概率
$$
P(X_{t+1}|X_{t}), P(Y_t|X_t)
$$
学习的目的是根据历史数据得到合理的模型,一般是根据一个目标函数,对模型进行迭代更新,例如使(5)中要计算的值最大便可以作为一个目标。

推理算法

(1)前向递归算法

应用于滤波问题。

(2)前向-后向算法

屏幕快照 2018-11-18 下午2.18.58

应用于平滑问题。

(3)维特比算法
$$
m_{t+1} = P(e_{t+1}|X_{t+1})\max_{X_t}(P(X_{t+1}|X_t) m_{1:t})
$$
应用于最大可能解释问题。

隐马尔可夫模型

定义:

隐马尔可夫模型(Hidden Markov Model,HMM)是处理序列问题的统计模型,它用来描述一个含有隐含未知参数的马尔可夫过程。其目的是从可观察的参数中确定该过程的隐含参数,然后利用这些参数来作进一步的分析。

三个问题:

  1. 给定一个模型,如何计算某个特定的输出序列的概率?

    Forward-Backward算法(如何求解?)

  2. 给定一个模型和某个特定的输出序列,如何找到最可能产生这个输出的状态序列?

    维特比算法

  3. 给定足够量的观测数据,如何估计隐含马尔可夫模型的参数?

    训练隐含马尔可夫模型更实用的方式是仅仅通过大量观测到的信号O1,O2,O3,….就能推算模型参数的P(St|St-1)和P(Ot|St)的方法(无监督训练算法),其中主要使用鲍姆-韦尔奇算法

卡尔曼滤波

思想:

以K-1时刻的最优估计$x_{k-1}$为准,预测K时刻的状态变量$x_{k/k-1}$,同时又对该状态进行观测,得到观测变量$Z_k$,再在预测与观测之间进行分析,或则说是以观测量对预测量进行修正,从而得到K时刻的最优状态估计$x_k$。

Kalman滤波算法的本质就是利用两个正态分布的融合仍是正态分布这一特性进行迭代。

五个核心方程:

20150915154429365

20150915205233233


下述解答参考自[1]。上述的例子为一维情况,实际每个状态往往包含多个维度,此时对应的公式换成方差矩阵计算即可。

  • 预测偏差和观测偏差计算协方差的原理?

    假设预测结果满足正态分布$N_0$,观测结果满足正态分布$N_1$,然后当前状态的分布为$N_0$和$N_1$的结合,新的分布也满足正态分布。预测偏差和观测偏差结合计算的实际上是新的正态分布下的Kalman增益,Kalmen增益描述了原始分布在新的分布下所对应的权重。相关公式如下:

    5775813-a531ecece2319d4c

    5775813-00a72059d700c58f-2

    5775813-c2537e3f1e1ef638

  • 最优值偏差的计算原理?

    当前状态的最优值偏差,计算的即新分布下的方差,根据上述公式即可得到。同样,当前状态的位置即当前分布的均值,同样可由上述公式求得。

  • 预测误差的计算方法

动态贝叶斯网络

定义:

动态贝叶斯网络(Danymic Bayesian Networks, DBN)在任何时刻t,都可以具有任何数量的状态变量和证据变量。

优点:

如果把一个复杂系统的状态分解成几个变量,那么整个模型所需要的参数将会大大减少。假设DBN有20个Boolean型的变量,每个变量只和上一时刻的三个节点有关联。那么在DBN中,所需要的参数为$202^3= 160$个;而在HMM中,每个时刻的隐含状态数量为$2^{20}$,因此转移矩阵的参数量为$2^{20}2^{20}$。显然,DBN所需要的参数量大大减少。

参考

简单决策

效用理论

定义:

The utility function rates states and thus formalizes the desirability of a state by the agent.
U(S) denotes the utility of state S for the agent.

Expected Utility:
$$
EU(A | E) = \sum_i P (Result_i(A) | Do(A); E) × U(Result_i(A))
$$
The principle of maximum expected utility (MEU) says that a rational agent should choose an action that maximizes $EU(A | E).$

Lottery Scenario:

我们可以用Lottery方案来模拟MEU,假设有$L = [p1; C1; p2; C2; : : : ; pn; Cn] $,分别表示获得金钱C1、C2, … , Cn的概率,这等同于在某个状态下所做的一个决策。假设每个人有多种彩票L可以选择,那么他一定会选择能让自己最后能获得金钱最大的彩票。

The Axioms of utility theory:

  • Orderability
  • Transitivity
  • Continuity
  • Substitutability
  • Monotocicity
  • Decomposability

复杂决策

时间效用

有限期:在有限期条件N下,给定状态的最优行动会随时间变化。有限期的最优策略是非静态的,N之后的所有行动,对整体效用没用影响。

无限期:在无限期条件下,最优行动只依赖于当前状态,其最优策略是静态的。

奖励函数

累加回报:$U_h([s_0,s_1,s_2, …]) = R(s_0) + R(s_1) + R(s_2) + …$

折扣回报:$U_h([s_0,s_1,s_2, …]) = R(s_0) + \gamma R(s_1) + \gamma^2 R(s_2) + …$

奖励因子$\gamma$的解释:今天的一元钱在明天一般都会贬值。所以当某个状态s较晚到达时,要控制奖励因子使得获得的价值减少。

当环境不包含终止状态时,整个系统的效用值通常是无限大。可通过以下三种方法解决:

  • 使用折扣回报;
  • 环境包含终止状态;
  • 根据每个时间步所获得的平均回报进行比较。

Bellman方程

$$
U ( s ) = R ( s ) + \gamma \max _ { a \in A ( s ) } \sum _ { s ^ { \prime } } P \left( s ^ { \prime } | s , a \right) U \left( s ^ { \prime } \right)
$$

价值迭代

策略迭代

样例学习

学习策略

监督学习

无监督学习

半监督学习

协同训练(Co-Training)

假设数据有两种特征表达,比如图像特征(X-1, Y-1)和文本特征(X-2, Y-2)。对于未标注数据同样有两种View。协同训练(Co-Training)的过程如下:

  1. 从(X-1, Y-1),(X-2, Y-2)分别训练得到两个个分类模型F-1,F-2
  2. 分别使用F-1与F-2对未标注数据进行预测
  3. 将F-1所预测的前K个置信度最高的样本加入F-2的训练数据集
  4. 将F-2所预测的前K个置信度最高的样本加入F-1的训练数据集
  5. 回到第1步

直推式学习(transduction learning)

直推式学习可以看成是半监督学习的一个子问题,直推式学习假设未标记的数据就是最终要用来测试的数据,其目的是在这些有限的未标记数据上取得最佳泛化能力;而半监督学习并不知道未来的测试数据是哪些。

弱监督学习

深度学习

迁移学习

零样本学习

集成学习

参考

分类器组合方法Bootstrap, Boosting, Bagging, 随机森林(一)

分类器组合方法Bootstrap, Boosting, Bagging, 随机森林(二)

Bootstrapping

Bootstrapping是一种从给定训练集中有放回的均匀抽样,也就是说,每当选中一个样本,它等可能地被再次选中并被再次添加到训练集中。

过程:

  • 采用重复抽样的方法每次从n个原始样本中抽取m个样本(m自己设定);
  • 对于m个样本计算统计量;
  • 重复步骤(1)(2)N次(N一般大于1000),这样就可以算出N个统计量;
  • 计算这N个统计量的方差。

Bagging

Bagging是boostrap aggregation的缩写,是一种根据均匀概率分布从数据集中重复抽样(有放回的)的技术。子训练样本集的大小和原始数据集相同。在构造每一个子分类器的训练样本时,由于是对原始数据集的有放回抽样,因此同一个训练样本集中可能出现多次同一个样本数据。

过程:

  • 每次从原始数据集中有放回的随机抽样n个样本形成自助训练集,重复S次后得到S个新的训练集。
  • 对每个自助训练集应用弱分类器,这样就得到了S个弱分类器;
  • 将预测数据放在这S个弱分类器上计算,计算结果采用投票方式(分类问题)和简单求平均(回归问题)即可。

Boosting

Boosting是一个迭代的过程,用来自适应的改变训练样本的分布,使得分类器聚焦在那些很难分的样本上。

之前Bagging的过程,抽取自主样本集的时候是简单随机抽样,每个样本被抽到的概率是一样的,而Boosting算法中给每一个样本赋予一个权值,每一轮在抽取自助样本集、训练完基分类器之后会对原始样本集做一个分类,然后跟效果比对,然后对分错的训练样本,自动的调节该样本的权值(增大)。
权值可以用在以下方面:

  • 可以用作抽样分布,从原始数据集中选出自助样本集
  • 基分类器训练时更倾向于用用高权值的样本进行训练。

例如,有10个样本,开始时简单随机抽样,每个样本被抽到的概率是一样的,都是1/10,然后第一轮结束后用得到的模型对该轮数据集中的样本分类,发现样本4被分错了,就增加它的权值,这样,第二轮抽取的时候4被抽到的概率增加了,第三轮也是一样。这样做,就可以让基分类器聚焦于难被分类的样本4,增加4被正确分类的几率。

Adaboost

算法框架:

权重调整:

AdaBoost “focused on” the informative or “difficult” examples.

决策树

信息熵定义为:
$$
\mathrm { H } ( \mathrm { X } ) = - \sum _ { i = 1 } ^ { n } p _ { i } \log _ { 2 } p _ { i ^ { \prime } }
$$
注意:决策树的熵计算中,log以2为底。

概率模型

最大似然估计

定义:

最大似然估计提供了一种给定观察数据来评估模型参数的方法,即:“模型已定,参数未知”。最大似然估计中采样需满足一个很重要的假设,就是所有的采样都是独立同分布的。

应用场景:

在模型已经确定,但是模型的参数未知的时候,我们可以利用ML来评估模型参数。

最大后验估计

定义:

最大后验估计是根据经验数据获得对难以观察的量的点估计。与最大似然估计类似,但是最大的不同时,最大后验估计的融入了要估计量的先验分布在其中。故最大后验估计可以看做规则化的最大似然估计。

优点:

在评估模型参数的时候融入了模型的先验分布,使得结果更贴合实际情况,更为准确。

ML vs MAP

当模型的参数本身的概率是均匀的,即该概率为一个固定值的时候,MAP=MLE。

频率学派和统计学派的区别:

  • 这个区别说大也大,说小也小。往大里说,世界观就不同,频率派认为参数是客观存在,不会改变,虽然未知,但却是固定值;贝叶斯派则认为参数是随机值,因为没有观察到,那么和是一个随机数也没有什么区别,因此参数也可以有分布,个人认为这个和量子力学某些观点不谋而合。
  • 往小处说,频率派最常关心的是似然函数,而贝叶斯派最常关心的是后验分布。我们会发现,后验分布其实就是似然函数乘以先验分布再normalize一下使其积分到1。因此两者的很多方法都是相通的。贝叶斯派因为所有的参数都是随机变量,都有分布,因此可以使用一些基于采样的方法(如MCMC)使得我们更容易构建复杂模型。频率派的优点则是没有假设一个先验分布,因此更加客观,也更加无偏,在一些保守的领域(比如制药业、法律)比贝叶斯方法更受到信任。 

EM算法

朴素贝叶斯

朴素贝叶斯法是基于贝叶斯定理与特征条件独立假设的分类方法。

朴素贝叶斯分类器基于一个简单的假定:给定目标值时属性之间相互条件独立。

强化学习

状态空间的定义:

函数描述状态的utility的优点:

自然语言处理

文本特征抽取的向量空间模型(VSM)和TF/IDF方法

向量空间模型

向量空间模型(Vector Space Model, VSM),即将文档根据词袋模型等方法表达为一个向量,对文本内容的处理简化为向量空间中的向量运算,并且它以空间上的相似度表达语义的相似度。

词袋模型

词袋模型,即将文本内容看作一系列词的组合,将不同的词汇用不同的袋子装起来,袋子里统计的是对应词汇出现的次数。

TF*IDF

TF:词频,即一个词汇在一篇文档中出现的频率。

IDF:DF为文档频率,即一个词汇在整个文档集中出现的频率。IDF为DF的逆log函数。

公式为:
$$
\frac { - N _ { i } \log \left( D _ { i } \right) } { K } = \frac { N _ { i } } { K } \log \left( \frac { 1 } { D _ { i } } \right)
$$

参考

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×