北京大学 wlw机器学习2022春季期末试题分析

前言

你好！ 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章，了解一下Markdown的基本语法知识。

新的开始

第一题

利用Lagrange Dueling，即可计算。
$$\begin{gathered} L(x,{\lambda }_1,{\lambda }_2)=b^{T}x+{\lambda }_1^T(c-Ax)-{\lambda }_2^{T}x \\ \frac{\partial L}{\partial x}=b^T-{\lambda }_1^{T}A-{\lambda }_2^T=0 \end{gathered}$$
故最终对偶形式为：
$$\begin{gathered} ma{x}_{{\lambda }_1,{\lambda }_2}-{\lambda }_1^{T}c \\ s.t.b^T-{\lambda }_1^{T}A-{\lambda }_2^T=0 \\ {\lambda }_1^T\ge 0 \\ {\lambda }_2^T\ge 0 \end{gathered}$$

第二题

这里我个人认为要利用定义，还有就是要注意，这里提到的$c_1$,$c_2$是存在，而不是任意。
$$\begin{gathered} Let{\mathcal{M}}_d(\mathcal{X},ϵ)=m, \\ \exists x_1,x_2,...,x_m\in \mathcal{X},\forall i,j\in [m],i\ne j,d(x_i,x_j)\ge ϵ \\ Get{x}_{m+1}\in \mathcal{X},d(x_i,x_{m+1})<ϵ \\ So{c}_2\ge 1,{\mathcal{N}}_d(\mathcal{X},ϵ/c_2)={\mathcal{M}}_d(\mathcal{X},ϵ/c_2)\ge {\mathcal{M}}_d(\mathcal{X},ϵ) \end{gathered}$$
对左半部分证明同理。

第三题

（1）思路，根据题目描述，要想证明两个分类器不同，由于不知道算法A，故只能通过比较误差进行，题目中提到了弱学习性假设，故考虑证明加权误差：
$$\begin{gathered} {\hat{R}}_{t+1}(h_t)=\sum D_{t+1}(i)I(y_i\ne h_t(x_i)) \\ =\sum \frac{D_t(i)\ast exp(-y_i{\alpha }_t{h}_t(x_i))}{Z_t}I(y_i\ne h_t(x_i)) \\ =\sum D_t(i)I(y_i\ne h_t(x_i))\frac{exp(-y_i{\alpha }_t{h}_t(x_i))}{Z_t} \end{gathered}$$