PDF《习题二》

习题二 学号, 作者姓名, 邮箱

2017 年4月2日1[10pts] Lagrange Multiplier Methods 请通过拉格朗日乘子法(可参见教材附录B.

1)证明《机器学习》教材中式(3.36)与式(3.37)等价.即下面公式(1.1)与(1.2)等价. min w ? wT Sbw s.t. wT Sww =

1 (1.1) Sbw = λSww (1.2) Proof. 此处用于写证明(中英文均可)

2 [20pts] Multi-Class Logistic Regression 教材的章节3.3介绍了对数几率回归解决二分类问题的具体做法.假定现在的任务不再 是二分类问题,而是多分类问题,其中y ∈ {1,

2 . . . , K}.请将对数几率回归算法拓展到该 多分类问题. (1) [10pts] 给出该对率回归模型的"对数似然"(log-likelihood);

(2) [10pts] 计算出该"对数似然"的梯度. 提示1:假设该多分类问题满足如下K ? 1个对数几率, ln p(y = 1|x) p(y = K|x) = wT

1 x + b1 ln p(y = 2|x) p(y = K|x) = wT

2 x + b2 . . . ln p(y = K ? 1|x) p(y = K|x) = wT K?1x + bK?1

1 提示2:定义指示函数I(・), I(y = j) = ? ? ?

1 若y等于j

0 若y不等于j Solution. 此处用于写解答(中英文均可)

3 [35pts] Logistic Regression in Practice 对数几率回归(Logistic Regression, 简称LR)是实际应用中非常常用的分类学习算法. (1) [30pts] 请编程实现二分类的LR, 要求采用牛顿法进行优化求解, 其更新公式可参 考《机器学习》教材公式(3.29).详细编程题指南请参见链接:http://lamda.nju.edu. cn/ml2017/PS2/ML2_programming.html (2) [5pts] 请简要谈谈你对本次编程实践的感想(如过程中遇到哪些障碍以及如何解决, 对编程实践作业的建议与意见等). Solution. 此处用于写解答(中英文均可)

4 [35pts] Linear Regression with Regularization Term 给定数据集D = {(x1, y1), (x2, y2)xm, ym)}, 其中xi = (xi1;

xi2;

xid) ∈ Rd , yi ∈ R, 当我们采用线性回归模型求解时, 实际上是在求解下述优化问题: ? w? LS = arg min w

1 2 y ? Xw

2 2, (4.1) 其中, y = [y1,ym]T ∈ Rm , X = [xT

1 ;

xT

2 xT m] ∈ Rm*d , 下面的问题中, 为简化求解过 程, 我们暂不考虑线性回归中的截距(intercept). 在实际问题中, 我们常常不会直接利用线性回归对数据进行拟合, 这是因为当样本特征 很多, 而样本数相对较少时, 直接线性回归很容易陷入过拟合.为缓解过拟合问题, 常对公 式(4.1)引入正则化项, 通常形式如下: ? w? reg = arg min w

1 2 y ? Xw

2 2 + λ?(w), (4.2)

2 其中, λ > 0为正则化参数, ?(w)是正则化项, 根据模型偏好选择不同的?. 下面, 假设样本特征矩阵X满足列正交性质, 即XT X = I, 其中I ∈ Rd*d 是单位矩阵, 请 回答下面的问题(需要给出详细的求解过程): (1) [5pts] 考虑线性回归问题, 即对应于公式(4.1), 请给出最优解 ? w? LS的闭式解表达式;

(2) [10pts] 考虑岭回归(ridge regression)问题, 即对应于公式(4.2)中?(w) = w

2 2 = d i=1 w2 i 时, 请给出最优解 ? w? Ridge的闭式解表达式;

(3) [10pts] 考虑LASSO问题, 即对应于公式(4.2)中?(w) = w

1 = d i=1 |wi|时, 请给 出最优解 ? w? LASSO的闭式解表达式;

(4) [10pts] 考虑 0-范数正则化问题, ? w?

0 = arg min w

1 2 y ? Xw

2 2 + λ w 0, (4.3) 其中, w

0 = d i=1 I[wi = 0],即w0表示w中非零项的个数.通常来说, 上述问题是NP- Hard问题, 且是非凸问题, 很难进行有效地优化得到最优解.实际上, 问题(3)中的LASSO可 以视为是近些年研究者求解 0-范数正则化的凸松弛问题. 但当假设样本特征矩阵X满足列正交性质, 即XT X = I时, 0-范数正则化问题存在闭式 解.请给出最优解 ? w?