CS229机器学习 学习理论总结 |Vol9

在目前没有足够做的经验或者说是机器学习素养的情况下来看这种文章无疑是一种折磨,因此过一遍概念就over惹,同时记录一下文献管理中的一些经验

01 计算学习理论

计算学习理论希望回答

  1. 在什么样的条件下成功的学习是可能的
  2. 在什么条件下某个特定的学习算法可以保证成功运行

在可能近似正确(probably approximately correct,PAC)下,我们确定若干假设类别,判断它们能否从多项式数量的训练集中得到,同时对假设空间的自然度量来界定归纳学习所需的样例的训练数目

1.1 问题和错误率

我们具有数据集合$(x^{(i)},y^{(i)})$,以及做出的假设的集合H和学习算法L,在这个问题中,我们感兴趣的是刻画不同的学习器L的性能,这些学习器使用不同假设空间H来学习不同类别的C中的目标概念

为了描述学习器L输出的假设h对真实目标的逼近成句,我们定义真实错误率(true error),注意这里的真实错误率的定义是在整个实例的分布上,而不只是训练样例上,因为它是在实际应用此假设h后遇到的真实错误率

$error(h)=Pr[c(x)~=h(x)]$

img

image-20220403173130140

这个错误率的分布依赖于未知的概率分布,这个概率分布是和假设空间相关的;另外一方面h对于c的错误率不能直接由学习器观察到

我们的目的是刻画一个:能够从合理数量的随机抽样训练样例中通过合理的计算来得到一个可靠的假设,那我们如何来描述这种可学习性?我们当然希望所有的真实错误率都为0,但是这样是不现实的(思维辩证就知道不合适),因此我们可以从这两个角度看

  1. 将真实错误率限定在一个常数范围内,同时让这个常数可以任意小$\epsilon$
  2. 并不要求对所有的随机抽样序列都能成功,只要求其实拍的概率在某个常数$\sigma$

一些PAC的定义:

img

image-20220403175054274

img

image-20220403175125351

img

image-20220403175202889

在PAC学习定义之外,我们可以看出模型的可学习性很大程度由所需要的数据集数量确定,随着问题规模的增长所需要的训练样例的增长被称为该学习问题的样本复杂度(sample complexity)

对于一个假设空间如何确定和数据集之间的关系,可以用$\epsilon-exhousted$来刻画,表示于训练样例一致的所有假设的真实错误率都恰好小于$\epsilon$

img

image-20220403175841000

由此计算的得到需要的训练实际例子

$m>=1/(\epsilon)(In|H|+in(1/\sigma ))$

同样对于一个假设空间的复杂程度,可以使用Vapnik-Chervonenkis维度来证明模型的相关复杂程度

  • 常见模型的复杂程度
  • 神经网络的复杂程度

02 基于实例学习

一个很简单的思路,通过强大的计算能力,我们可以比较希望预测的值和数据集中所有实例,当从这些实例中泛化的工作被推迟到必须分类新的实例时,每当学习器遇到一个新的查询实例就分析这个实例与之前存储的的关系,来由此区分目标函数的值,这样的方法包括:

  1. 最近邻方法 nearest neighbor
  2. 局部加权回归 locally weighted regression

03 增强学习

大坑,不学,死都不学

04 文献管理

这里就是作为一个简单的记录,看文献中可能的应用场景

  1. 日常泛读来了解自己的研究现状(对于学术小白鼠不考虑555,所以没有这种需求)
  2. 文献综述
  3. 组会汇报的工作

因此需要对论文整理成一个一个项目来管理,同时需要对其做笔记,更重要的是可以方便引用,

第一部分查找:

  1. 单纯的找论文和管理的话,google scholar+sci-hub感觉就够了
  2. 在自己的google账号账图书馆中新建自己的文章档案库,这样可以方便管理

第二部分阅读:

可以在文档下载导入到zotero,再链接到notion,利用notion来做笔记和一些comment

作为一个文献管理的过程

第三部分引用:

可以利用zotero配合word的插件

也可以google scholar中导出apa格式

也可以使用latex中的texbib格式