北京大学 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{?L}{?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, \\ ?x_1,x_2,...,x_m\in \mathcal{X},?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)?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}$$