第13章 半监督学习

  • 13.1 试推导出式(13.5)~(13.8)。

高斯混合模型推导自混合专家(mixture of experts)模型,13.3推导了混合专家(mixture of experts)模型算法,所以这里直接从13.3结论推导出式(13.5)~(13.8)。

E步:

M步:

高斯混合模型的Q函数为

的求解公式对于所有的混合专家(mixture of experts)模型都是一样的:

将Q函数对求偏导后令其为0:

得到求解公式:

  • 13.2 试基于朴素贝叶斯模型推导出生成式半监督学习算法。

为了防止公式描述太过于混乱,我们首先整理一下需要用到的所有符号:

符号 说明
N 混合模型数量,也就是分类的数量
M 样本总数(既包含未标记样本,也包含已标记样本)
d 样本的维度(属性数目)
第k个属性的取值数目
第k个属性的第l种取值
第i混合模型中第k个属性为第l个取值

不难发现,朴素贝叶斯模型也是混合专家模型的一种:

其中

按照13.3的结论

E步:

M步:

首先写出Q函数公式

的求解公式对于所有的混合专家(mixture of experts)模型都是一样的:

求解的时候还需要考虑约束

因此采用拉格朗日乘数法

得到方程组

得到

  • 13.3 假设数据由混合专家(mixture of experts)模型生成,即数据是基于k个成分混合而得的概率密度生成:

其中是模型参数,是第i个混合成分的概率密度,混合系数。假设每个混合成分对应一个类别,但每个类别可包含多个混合成分。试推导相应的生成式半监督学习算法。

第一步:明确隐变量,写出完全数据的对数似然函数

定义隐变量为

那么,完全数据的似然函数为

因此,完全数据的对数似然函数为

第二步:EM算法的E步,写出Q函数

那么未标记样本属于混合成分i的概率为

对于标记过的变量,我们已经明确知道它来自哪个混合,所以

所以最终Q函数为

第三步:确定EM算法的M步

M步需要求函数Q的极大值,

将Q函数对求偏导后令其为0,求解得到

因为存在约束,所以求解需要借助拉格朗日乘数法

得到方程组

将(2)式代入(1)式,得到

所以

重复上面的计算,直到对数似然函数不再有明显的变化为止。

  • 13.4 从网上下载或自己编程实现TSVM算法,选择两个UCI数据集,将其中30%的样例用作测试样本,10%的样例用作有标记样本,60%的样例用作无标记样本,分别训练出利用无标记样本的TSVM以及仅利用有标记样本的SVM,并比较其性能。

传送门:机器学习:TSVM实现

  • 13.10 试为图13.7算法的第10行写出违约检测算法(用于检剖是否有约束未被满足)。
数据结构 说明
M[i] 第i个样本必连约束样本,数组的元素是数组
C[i] 第i个样本勿连约束样本,数组的元素是数组
Y[i] 第i个样本的分类,如果未分类,那么返回null
# 检测必连约束
for sample in M[i]:
	if Y[sample] != Y[i]:
		return False
# 检测勿连约束
for sample in C[i]:
  	if Y[sample] == Y[i]:
      	return False
# 约束满足
return True

第14章 概率图模型

  • 14.1 试用盘式记法表不条件随机场和朴素贝叶斯分类器。

素贝叶斯分类器

png

条件随机场

png

  • 14.2 试证明图模型中的局部马尔可夫性:给定某变量的邻接变量,则该变量条件独立于其他变量。

某变量的邻接变量可以作为分离集将该变量和其他变量分离,根据全局马尔可夫性,该变量条件独立于其他变量。

  • 14.3 试证明图模型中的成对马尔可夫性:给定其他所有变量,则两个非邻接变戴条件独立。

其他变量可以作为分离集将两个非邻接变量分离,根据全局马尔可夫性,两个非邻接变戴条件独立。

  • 14.6 试证明变虽消去法的计算复杂度随图模型中极大团规模的增长而呈指数增长,但随结点数的增长未必呈指数增长。

时间复杂度

首先分析一下(14.18)的时间复杂度

令n为其中规模最大的最大团的规模,图中极大团的最大规模都是2,一共进行了4次变量消去。每次在势函数上进行首次变量消去的时候,需要遍历变量组合的取值,令所有变量的取值数目都为,那么计算时间复杂度为

指数增长

如果增加某个极大团的规模,那么对应的势函数的参数数目同时会增加,假设图中最大极大团的势函数为

首次消去一个变量需要遍历所有的变量组合,根据一次消去操作计算时间复杂度,如果其他极大团的规模都小于n,那么它们的时间复杂度在高阶项后都可以忽略不计,全部计算时间复杂度,计算复杂度随图模型中极大团规模的增长而呈指数增长。

线性增长

如果在不增加最大最大团规模的条件下增加极大团的数目,例如

式子中需要n-1次消去操作,每次消去操作的时间复杂度都是,因此全部计算的时间复杂度为,这种情况下时间复杂度是线性增长的。

第15章 规则学习

  • 15.1 对西瓜数据集2.0,允许使用否定形式的文字,试基于自顶向下的策略学出命题规则集。

自顶向下策略的实现方法:从空规则开始,按照正确率做贪心策略选择,每次搜索到一个匹配的规则后,删除掉规则匹配的数据,然后重新开始搜索,直到没有正例为止。

  • 15.2 对西瓜数据集2.0,在学习过程中可通过删去文字、将常量替换为变量来进行规则泛化,试基于自底向上的策略学出命题规则集。

自底向上策略的实现方法:将每条数据作为规则,然后在满足数据集的前提下尽量删除其中的文字。

  • 15.4 规则学习也能对缺失数据进行学习。试模仿决策树的缺失值处理方法,基于序贯覆盖在西瓜数据集2.0a上学出命题规则集。

规则学习的缺失数据数据似乎更加方便,只需要使得缺失属性满足任何条件即可。

第16章 强化学习

  • 16.2 借鉴图16.7,试写出基于折扣奖赏函数的策略评估算法。

输入:MDP四元组;被评估的策略折扣累积奖赏参数;阈值

过程:

  • loop
    • if then
      • break
    • else
      • V = V’
    • end if
  • end for

输出:状态值函数V

  • 16.3 借鉴图16.8,试写出基千折扣奖赏函数的策略迭代算法。

输入:MDP四元组折扣累积奖赏参数;阈值

过程:

  • loop
    • loop
      • if then
        • break
      • else
        • V = V’
      • end if
    • end loop
    • if then
      • break
    • else
    • end if
  • end loop

输出:最优策略

  • 16.6 试借鉴图16.14给出线性值函数近似Q-学习算法。

输入:环境E;动作空间A;起始状态;奖赏折扣;更新步长

过程:

  • for t = 1, 2, … do
    • r, x’=在E中执行动作产生的奖赏与转移状态
    • x = x, a = a’
  • end for

输出:策略