第一课：学习的问题

机器学习三个条件：有潜在的模式可以学习，潜在的模式无法用规则来表达出来，有数据
定义符号：

符号	含义
$\vec x \in \mathcal X, y \in \mathcal Y$x∈X,y∈Y	输入和输出
$f:\mathcal X \to \mathcal Y$f:X→Y	未知的真实函数，需要学习的结果尽可能拟合这个函数
$\mathcal D = \{(\vec x_1, y_1),(\vec x_2, y_2), ..., (\vec x_n,y_n)\}$D={(x1​,y1​),(x2​,y2​),...,(xn​,yn​)}	数据集、训练集
$\mathcal g: \mathcal X\to\mathcal Y$g:X→Y	学习到的假设
$\mathcal H =\{h_k\}$H={hk​}	所有假设的集合，$\mathcal g\in \mathcal H$g∈H

第二课

简单的学习算法：PLA
在有噪声的情况下：pochet algorithm

第三课

classification、regression、structured
supervised、un/semi-supervised、reinforcement
batch、online、active
concrete、raw、abstract

第四课

no free lunch定理：如果没有具体问题，就学不到东西

罐子中抽小球的问题：假设罐子中有无限的黄球和绿球，抽出来一批样本，黄色比例是$\nu$ν，罐子中黄球的真实比例是$\mu$μ，可不可以用$\nu$ν估计$\mu$μ
hoeffdings’s inequality：$\mathbb P[|\nu-\mu|>\epsilon]\le2exp(-2\epsilon^2N)$P[∣ν−μ∣>ϵ]≤2exp(−2ϵ2N)
由hoeffdings不等式可以得到“$\nu=\mu$ν=μ”是probably approximately correct（PAC），当样本量N足够大的时候，可以认为$\mu=\nu$μ=ν

将罐子里抽小球的问题对应到机器学习问题：

$\mu$μ	fixed hupothesis $h(x) \overset{?}{=}f(x)$h(x)=?f(x)
罐子中的小球	样本$\vec x\in\mathcal X$x∈X
黄球	KaTeX parse error: Undefined control sequence: \nef at position 5: h(x)\̲n̲e̲f̲(x)
绿球	$h(x)=f(x)$h(x)=f(x)
N个iid抽样	在数据集$\mathcal D=\{(\vec x_n,y_n)\}$D={(xn​,yn​)}上检查$h$h，满足iid

对于确定的h，可以概率上通过已知的$E_{in}(h)=\frac{1}{N}\sum_{n=1}^N\llbracket h(x)\ne f(x) \rrbracket$Ein​(h)=N1​∑n=1N​[[h(x)​=f(x)]]去推断unknown $E_{out}(h)=\overset{\epsilon}{x\sim P}\llbracket h(x)\ne f(x)\rrbracket$Eout​(h)=x∼Pϵ[[h(x)​=f(x)]]，$E_{in}$Ein​就是抽样得到的小球，即训练样本，$E_{out}$Eout​是罐子中的小球，即真实的$f$f

根据hoeffding不等式，可以得到$\mathbb P[|E_{in}-E_{out}|>\epsilon]\le2exp(-2\epsilon^2N)$P[∣Ein​−Eout​∣>ϵ]≤2exp(−2ϵ2N)
也就是把hoeffdin不等式里面$\nu$ν和$\mu$μ替换掉了

再来看一个扔硬币的问题，如果让150个学生扔硬币，每个人扔5次，这150个人中，由一个得到5次头像的概率是$1-(\frac {31} {32})^{150}>99\%$1−(3231​)150>99%，但是一个硬币正反面的概率应该都是0.5的。在使用机器学习算法的时候，我们通常会选择在$E_{in}$Ein​上表现较好的模型。那么也就有很大可能会选到$E_{in}$Ein​和$E_{out}$Eout​差很远的$h$h。这里人头像对应的是在训练集上跑正确，五个正面就是在训练集上全对。这5个正面的数据就是一次不好的抽样。

对于一个假设$h$h，抽到不好的抽样的概率是$\mathbb P[$P[BAD $\mathcal D]=\sum_{all\ possible\ \mathcal D}\mathbb P(\mathcal D)\cdot\llbracket$D]=∑all possible D​P(D)⋅[[BAD $\mathcal D\rrbracket$D]]，对于一个假设$h$h，取到坏样本的概率可以用hoeffding不等式来算上界

对于M个假设，只要其中一个$h$h对应的$\mathcal D$D是不好的，这个$\mathcal D$D就认为是不好的，那么不小心得到这样的抽样的概率是$\mathbb P_{\mathcal D}[BAD\ \mathcal D]=\\ \mathbb P_{\mathcal D}[{\color{red} BAD}\ \mathcal D\ for\ h_1\ {\bf OR}\ {\color{red} BAD}\ \mathcal D\ for\ h_2...\ {\bf OR}\ {\color{red} BAD}\ \mathcal D\ for\ h_M]\\ \le2exp(-2\epsilon^2N)+2exp(-2\epsilon^2N)+...+2exp(-2\epsilon^2N)\\ =2Mexp(-2\epsilon^2N)$PD​[BAD D]=PD​[BAD D for h1​ OR BAD D for h2​... OR BAD D for hM​]≤2exp(−2ϵ2N)+2exp(−2ϵ2N)+...+2exp(−2ϵ2N)=2Mexp(−2ϵ2N)
这个值也就是对于一个假设的集合，$E_{in}\ne E_{out}$Ein​​=Eout​的上界。

但是这里就留了一个问题，这里将M当作了一个有限值，但是实际上，比如PLA算法，画线的数量可以是无限大的，那么对无限的M这个仍然可以bound住这个值吗？

第五课

这几节课主要就围绕第四课里面M无限的问题。

第四课得到了一个不等式：$\mathbb P[|E_{in}-E_{out}|>\epsilon]\le2\cdot M\cdot exp(-2\epsilon^2N)$P[∣Ein​−Eout​∣>ϵ]≤2⋅M⋅exp(−2ϵ2N)
对于较小的M，可以得到训练集测试集结果很接近的概率很大，但是算法的选择就很少，很难将$E_{in}$Ein​减小，对于较大的M，可以降低$E_{in}$Ein​，但是很难保证训练和测试的结果接近
对于一个固定的假设集合$\mathcal H$H，尝试使用$m_{\mathcal H}$mH​来代替M，因此就得到了$\mathbb P[|E_{in}-E_{out}|>\epsilon]\overset{?}{\le}2\cdot m_{\mathcal H}\cdot exp(-2\epsilon^2N)$P[∣Ein​−Eout​∣>ϵ]≤?​2⋅mH​⋅exp(−2ϵ2N)

$\mathscr B$BAD evend$\mathscr B_m:|E_{in}(h_m)-E_{out}(h_m)|>\epsilon$Bm​:∣Ein​(hm​)−Eout​(hm​)∣>ϵ
引入M的过程是将所有的$\mathcal H$H中取union，使用了直接加和，这里就假设了所有的$\mathscr B$B全部没有重叠

如果将类似的hypotheses聚合起来，也就是将重叠删掉，有没有可能得到稍微紧一些的upper bound？

在PLA算法中，一个平面上的直线数量是无限大的，但是对于一个样本点，这些线能够划分的结果只是让这个点等于⚪或者×。也就是hypotheses set大小只有2。在一个平面上的两个点，可能有4中情况，3个点有8中情况，到了4个点的时候，就只有14中情况而不是16种了。这里所有情况有多少种都代表了hypothesis set的大小。
以$effective(N)$effective(N)代替上面的$m_{\mathcal H}$mH​，得到$\mathbb P[|E_{in}(g)-E_{out}(g)|>\epsilon]\le 2\cdot effective(N)\cdot exp(-2\epsilon^2N)$P[∣Ein​(g)−Eout​(g)∣>ϵ]≤2⋅effective(N)⋅exp(−2ϵ2N)
如果$effective(N) << 2^N$effective(N)<<2N，在不等式的右边一个远小于指数的函数除以一个指数函数，就可以得到bound了。
先来看几个简单例子

1. positive rays：这是一条射线，取一个阈值a，大于a的取正号，小于1的取负号。即$h(x)=sign(x-a)$h(x)=sign(x−a)。这个例子中$m_{\mathcal H}(N)=N+1$mH​(N)=N+1
2. Positive intervals在一个区间内是正号，以外是负号。$h(x)=\begin{cases} +1& \text{iff}\ x\in [\mathscr l,r) \\ -1& \text{otherwise} \end{cases}$h(x)={+1−1​iff x∈[l,r)otherwise​。这里$m_{\mathcal H}=\frac 1 2 n^2 + \frac 12 N + 1$mH​=21​n2+21​N+1
3. convex sets：一种情况是N个点在一个圆上面，这时可以有$m_\mathcal H(N) =2^N$mH​(N)=2N

引入break point的概念，就是在某一个k的时候，保证$m_{\mathcal H}(k)<2^k$mH​(k)<2k最小的k

第六课

首先探讨break point的一些性质。如果break point为2时，一个点的时候应该有两种可能；两个点的时候应该有小于4种可能；在3个点时，应该保证任意两个点都不能有4种可能（因为如果有其中两个点有4种可能，那么去掉一个点，就一定有其中k>2了）

定义一个Bounding Function $B(N,K)$B(N,K)，在break point为k时最大可能的$m_{\mathcal H}(N)$mH​(N)
那么首先可以确定的是，k=1的时候，$B(N,K)$B(N,K)一定等于1，这是根据定义得到的。当$N<k$N<k时，一定有$B(N,k)=2^k$B(N,k)=2k，这也是根据定义得到的。在$N=k$N=k的时候，由于要保证$m_{\mathcal H}(N)<2^k$mH​(N)<2k，那么简单地-1即可，也就是从所有地组合中删除一种情况，就可以保证不回出现所有情况地组合了。剩下的内容就是填写当$N>k$N>k时候的表中的内容。

视频中推导的Bounding Function最终的表格是这样的：

这个bounding function也就是$m_{\mathcal H}(N)$mH​(N)的上界

在使用hoefding不等式的时候，有$\mathbb P[\exists h \in \mathcal H s.t.\ |E_{in}(h)-E_{out}(h)|>\epsilon]\le 2 {\color{orange} m_{\mathcal H}(N)}\cdot exp(-2\epsilon^2N)$P[∃h∈Hs.t. ∣Ein​(h)−Eout​(h)∣>ϵ]≤2mH​(N)⋅exp(−2ϵ2N)
这里$E_{out}(h)$Eout​(h)是一个样本无限的值，因为在前面的假设中罐子中球的数量是无限的。需要使用一个有限量$E'_{in}$Ein′​代替。$E'_{in}$Ein′​就相当于验证集。就是ppt 22页的step1。这里具体的理由没有看太懂。
因为在使用验证集的时候，默认验证集也有N个样本，就把hoefding不等式中的N变成了2N，就是step 2
step 3中代入hoeffding不等式中，就得到了$\mathbb P[\exists h\in \mathcal\ H s.t.\ |E_{in}(h)-E_{out}(h)|>\epsilon]\le4m_{\mathcal H}(2N)exp(-\frac 1 8 \epsilon^2N)$P[∃h∈ Hs.t. ∣Ein​(h)−Eout​(h)∣>ϵ]≤4mH​(2N)exp(−81​ϵ2N)
这个就是VC bound
（实际上这三步没怎么看懂）

第七课

在第六课中得到了一个不等式
$m_{\mathcal H}(N)\le B(N,k)=\sum_{i=0}^{k-1}\tbinom{N}{i}\le N^{k-1}$mH​(N)≤B(N,k)=i=0∑k−1​(iN​)≤Nk−1
hoeffding不等式中的$m_{\mathcal H}(2N)$mH​(2N)就可以替换成$(2N)^{k-1}$(2N)k−1
$\mathbb P_{\mathcal D}[|E_{in}(g)-E_{out}(g)|>\epsilon]\\ \le \mathbb P_{\mathbb D}[\exists h\in \mathcal H\ s.t.\ |E_{in}(h)-E{out}(h)|>\epsilon]\\ \le4m_{\mathcal H}(2N)exp(-\frac 1 8\epsilon^2N)\\ \overset{\text{\color{orange}if k exists}}{\le}4(2N)^{k-1}exp(-\frac 1 8 \epsilon^2 N)$PD​[∣Ein​(g)−Eout​(g)∣>ϵ]≤PD​[∃h∈H s.t. ∣Ein​(h)−Eout(h)∣>ϵ]≤4mH​(2N)exp(−81​ϵ2N)≤if k exists​4(2N)k−1exp(−81​ϵ2N)
根据这个公式，可以得到如果

1. $m_{\mathcal H}(N)$mH​(N)有break point k，
2. 并且N足够大保证$E_{in}$Ein​和$E_{out}$Eout​大致相等，
3. 学习算法$\mathcal A$A能够让$E_{in}$Ein​足够小，

就有可能学到东西。

然后引入VC Dimension的概念。$\mathcal H$H的VC dimension用$d_{vc}(\mathcal H)$dvc​(H)表示，代表使$m_{\mathcal H}(N)=2^N$mH​(N)=2N最大的N。
从定义来看，$d_{vc}= (minimum\ k) -1$dvc​=(minimum k)−1

之前的四种hypothesis set的VC dimension是下图

这个VC dimension和学习算法无关，和数据分布无关，和最终得不到的那个目标函数无关，因此可以当作generalization过程中的最宽泛的bound

在2D perceptrons中，$d_{vc}=3$dvc​=3，那在更高维度的感知机里面VC dimension是多少呢？
一个猜想是$d_{vc}\overset{?}{=}d+1$dvc​=?d+1，要证明这个东西，可以分成两步，先证明$d_{vc}\ge d+1$dvc​≥d+1，再证明$d_{vc}\le d+1$dvc​≤d+1。

要证明$d_{vc}\ge d+1$dvc​≥d+1只需要证明存在d+1个输入，能够找到$2^{d+1}$2d+1种情况

要证明$d_{vc}\le d+1$dvc​≤d+1，需要证明d+2个样本时所有的情况都不可以shatter。

因为在构造的这个X里面，行数大于列数了，所以$x_{d+2}$xd+2​一定可以由其他的向量线性表示，假设线性表示时每个向量前面乘的系数就是$\alpha_i$αi​。然后等式两边同时乘以$w^T$wT，一样应该成立。等式的右边就一定大于0。所以在这种情况下，如果满足了前d+1个样本，最后一个样本一定没法是×，也就无法构成$2^{d+2}$2d+2种可能性。

这里的d+1实际上就是perceptron的维度。一个perceptron的权重向量w有d+1个维度，也就可以理解成模型中可以调节的变量的数量。vc dimension大致就可以认为是hypothesis中的*度。大部分情况下，$d_{vc}\approx \text{\#free parameters}$dvc​≈#free parameters，但是并不总对。
这里就可以使用$d_{vc}$dvc​代替第五节课中的M。
$\mathbb P_{\mathcal D}[|E_{in}(g)-E_{out}(g)|>\epsilon]\le4(2N)^{d_{vc}}exp(-\frac 1 8 \epsilon^2 N)$PD​[∣Ein​(g)−Eout​(g)∣>ϵ]≤4(2N)dvc​exp(−81​ϵ2N)
把不等式右边设为$\delta$δ，可以得到$\sqrt{\frac 8 N ln(\frac {4(2N)^{d_{vc}}} \delta)}=\epsilon$N8​ln(δ4(2N)dvc​​)​=ϵ
即$E_{in}(g)-\epsilon\le E_{out}(g) \le E_{in}(g)+\epsilon$Ein​(g)−ϵ≤Eout​(g)≤Ein​(g)+ϵ，$\epsilon$ϵ也可以看作是对model complexity的惩罚，和N，$\mathcal H$H以及$\delta$δ有关

在理论上，大致需要10000倍的$d_{vc}$dvc​才行，但是实际上会发现只需要10倍左右就够了。
造成这种差距的原因是在求VC Bound的时候采取了很多loosen的方法，首先hoeffding是针对任何分布，任何target function；使用成长函数$m_{\mathcal H}(N)$mH​(N)代替$|\mathcal H(x_1,...,x_N)|$∣H(x1​,...,xN​)∣，确保任何数据都可以覆盖；使用多项式$N^{d_{vc}}$Ndvc​代替$m_{\mathcal H}(N)$mH​(N)来做上限的上限的上限，来保证任何$d_{vc}$dvc​的hypothesis都可以覆盖；使用union bound来保证算法$\mathcal A$A产生的任何选择都可以覆盖。

第八课

这一课主要是用来处理noise的情况。前面讨论中，全部都是线性可分且没有噪声。
之前有target function $f$f，由于引入了噪声，可以认为$y\overset {i.i.d}{\sim} P(y|\vec x)$y∼i.i.dP(y∣x)在这种情况下VC仍然是对的。

再后面讲了一些关于不同情况下对于错误处理的问题，比如CIA的门禁应当对false accept的惩罚大于false reject。
不同权重的惩罚可以通过将这种错误的样本重复很多次来达到目的。

总结

这门课主要介绍了机器学习的理论保证。
几个比较重要的符号、概念：$m_{\mathcal H}$mH​，break point，VC，hoeffding不等式，Bounding Function $B(N,k)$B(N,k)。

第八课作业超详细解答：
https://www.dazhuanlan.com/2019/12/20/5dfc1dec84521/