作业四

截止时间：2019年12月1日 23:59

作业模版请上传到jupyter平台运行

内容

一、支持向量机 SVM

利用SVM算法来对iris数据集进行分类处理

根据定理7.3与定理7.4，下述三种线性SVM模型互相等价：

• primal model: (7.32-7.34)
• primal model with hinge loss: (7.63)
• dual model: (7.37-7.39)

同时利用核技巧，可以实现非线性SVM模型（7.95-7.97），其中多项式核函数(7.88)与高斯核函数(7.90)是常用的两种非线性核

• dual model with non-liniear kernel: (7.88), (7.90)

另一方面，SVM的预测算法由算法1-4描述

• primal model: 算法1
• dual model: 算法2、3
• dual model with non-linear kernel: 算法4

算法1-4中SVM模型的求解，即凸二次规划问题的求解也存在多种方法：

• 一阶方法：梯度下降法
• 7.4节中描述的SMO算法 – dual problem

利用梯度下降法求解有约束问题一般来说也有几种方式，例如：

• 惩罚函数法：将约束问题转换为无约束问题，然后再利用梯度下降法求解
• 梯度投影法：将梯度下降后的结果再投影到可行域中

你需要做的事情是：

• 选取任意一个SVM模型
• 利用任意一种算法来求解其对应的凸二次规划问题
• 并选择对应的算法来预测结果
• 请在提交结果里注明你采用的SVM模型以及求解方法

例如，一些可能的选择是：

• 利用算法1和梯度下降法求解7.63
• 利用算法1和梯度下降法求解7.32-7.34
• 利用算法2/3和梯度下降法求解7.37-7.39
• 利用算法2/3和梯度下降法求解7.95-7.97 – 1 bonus
• 利用SMO算法求解7.37-7.39 – 2 bonus
• 利用SMO算法求解7.95-7.97 – 3 bonus
• 或者采用其他任意可行的求解方式…

关于代码结构：

• 仿造HW3 – Bayes代码模版
• 或者仿造HW3 – Logistic代码模版
• 或者根据需求自行设计 – 若自行设计，代码结构的可读性会考虑在评分内

总分：3

难度估计：> 4 小时

二、AdaBoost

代码模版

利用算法8.1对iris数据集进行分类

• 利用sklearn提供的DecisionTreeClassifier构造单层决策树作为基本分类器
• 调整式(8.7)以适用于多分类的情况

总分：3

难度估计：0.5-3 hours

三、EM方法

完成习题9.3

总分：2

四、隐马尔可夫模型

完成习题10.1

总分：2

五、条件随机场 （Bonus 2）

完成习题11.2

提交

提交内容

将所有文件打包成zip并以你的学号命名，例如51160601160.zip:

• 编程题提供.ipynb
• 推导题提供.pdf

提交方式

1. 提交到FTP服务器的AI_homework/Graduate/HW4文件夹下
2. (可选)你可以多次上传，以最后一次上传的结果为准

具体提交方式见作业提交系统

参考材料

[1] 李航. 统计学习方法第二版[M]. 清华大学出版社, 2019.