#机器学习笔记 1

1 关于概念

1、模型:泛指从数据中学得的结果。有的文献中特指全局性结果,用“模式”指局部性结果

2、样本:数据集中关于一个事件或对象的描述,又称“示例”

3、属性/特征:反映事件或对象在某方面的表现或性质的事项

4、属性值:属性上的取值

5、属性空间/样本空间/输入空间:属性张成的空间

6、学习/训练:从数据中学得模型的过程

7、训练数据:训练过程中使用的数据

8、训练样本:训练数据中的每个样本

9、假设:学得的模型对应的关于数据的某种潜在的规律

10、真相/真实:潜在规律自身

11、标记:关于示例结果的信息

12、样例:拥有了标记信息的示例

13、标记空间/输出空间:所有标记的集合

14、分类:欲预测的是离散值的学习任务

15、回归:欲预测的是连续值的学习任务

16、正类、反类:对“二分类”问题,称其中一个类为正类,另一个类为反类

17、测试:学得模型后,试用其进行预测的过程

18、测试样本:被预测的样本

19、聚类:将训练集中的数据分为若干组,每一组称为一个“簇”

20、监督学习、无监督学习:根据训练数据是否有标记信息将学习任务划分为两类,有标记的是监督学习,无标记的是无监督学习

21、泛化能力:学得模型适用于新样本的能力

22、假设空间:由所有假设组成的空间

23、版本空间:假设空间中与训练集一致的所有假设组成的集合

24、归纳偏好:机器学习算法在学习过程中对某种假设类型的偏好,简称“偏好”

2 主要内容

1、任何一个有效的机器学习算法必有其归纳偏好,否则它将被假设空间中看似在训练集上“等效”的假设所迷惑,而无法产生学习的结果。如果在预测时随机抽选训练集上的等效假设,则模型给出的结果可能不唯一

2、“奥卡姆剃刀”原则:若有多个假设与观察一致,则选择最简单的那个。但是关于“简单”没有明确的定义,因此奥卡姆剃刀本身存在不同的诠释,使用奥卡姆剃刀原则不平凡

3、“没有免费的午餐”定理:总误差与学习用的算法无关,对于任意两个算法,期望性能都相同。对于一个学习算法  \mathfrak{L}_{a},若它在某些问题上比学习算法  \mathfrak{L}_{b} 好,则必然存在另一些问题,在那里  \mathfrak{L}_{b} \mathfrak{L}_{a} 好。为简单起见,假设样本空间  \mathcal{X} 和假设空间  \mathcal{H} 都是离散的,令  P(h|X,\mathfrak{L}_{a}) 代表算法  \mathfrak{L}_{a} 基于训练数据  X 产生假设  h 的概率,再令  f 代表我们希望学习的真实目标函数。  \mathfrak{L}_{a} 的“训练集外误差”,即  \mathfrak{L}_{a} 在训练集之外的所有样本上的误差为

    \[  E_{ote}(\mathfrak{L}_{a}|X,f)=\sum_{h} \sum_{\boldsymbol{x} \in \mathcal{X}-X} P(\boldsymbol{x}) \, \mathbb{I}(h(\boldsymbol{x}) \ne f(\boldsymbol{x})) \, P(h|X, \mathfrak{L}_{a} ) \]

其中 \mathbb{I}(\cdot)是指示函数,若 \cdot 为真则取值1,否则取值0。考虑二分类问题,且真实目标函数可以是任何函数  \mathcal{X} \mapsto \{0,1\},函数空间为 \{0,1\}^{|\mathcal{X}|}。对所有可能的  f 按均匀分布对误差求和,有

    \[\]

    \[   \begin{aligned} \sum_{f} E_{ote}(\mathfrak{L}_{a}|X,f) &= \sum_{f} \sum_{h} \sum_{\boldsymbol{x} \in \mathcal{X}-X} P(\boldsymbol{x}) \, \mathbb{I}(h(\boldsymbol{x}) \ne f(\boldsymbol{x})) \, P(h|X, \mathfrak{L}_{a} )\\ &= \sum_{\boldsymbol{x} \in \mathcal{X}-X} P(\boldsymbol{x}) \sum_{h} P(h|X, \mathfrak{L}_{a} ) \sum_{f} \mathbb{I}(h(\boldsymbol{x}) \ne f(\boldsymbol{x}))\\ &= \sum_{\boldsymbol{x} \in \mathcal{X}-X} P(\boldsymbol{x}) \sum_{h} P(h|X, \mathfrak{L}_{a} ) \frac{1}{2} 2^{|\mathcal{X}|}\\ &=  \frac{1}{2} 2^{|\mathcal{X}|} \sum_{\boldsymbol{x} \in \mathcal{X}-X} P(\boldsymbol{x}) \sum_{h} P(h|X, \mathfrak{L}_{a} )\\ &= 2^{|\mathcal{X}|-1} \sum_{\boldsymbol{x} \in \mathcal{X}-X} P(\boldsymbol{x}) \cdot 1\\ \end{aligned} \]

可见当所有“问题”出现的几率相等时,总误差与学习算法无关,所以我们在设计算法的时候,应该只关注自己正在试图解决的问题,使学习算法自身的归纳偏好与问题相配,若考虑所有潜在的问题,则所有算法的效果相同,脱离具体问题,空泛地谈论“什么学习算法更好”毫无意义

3、习题

留坑待填…

关于计算概论A期中考试之后的算法学习

0 引言

期中考试之前的计算概论课程,所讲的内容大概是C语言的基础语法,目的在于写出语法上正确的代码,熟练地进行各类型数据的读入输出,并且做一些简单的处理。期中考试的重难点,也在于对数据进行正确的读入与储存,而对于后续的计算,则基本上是处于“暴力即可”的一个标准。而期中考试之后,计算概论的学习上会进行从语法学习到简单算法学习的一个转变,表现在编写程序上,就是从“写一个正确的做法”到“写出一个优秀的算法”的转变。这就需要先去了解什么样的程序可以算得上是一个优秀的程序。

1 关于时空复杂度

1.1 时间复杂度

任何一个程序在运行的过程中,都需要消耗一定的时间,用来执行被一个步骤,也需要一定的空间,来进行数据的存储。对于程序运行的时间,是可以比较轻易地感受到的,就比如说在不同的搜索引擎中进行同一个问题的搜索,那么在不考虑搜索结果的情况下,给出结果更快的搜索引擎会更多地受到青睐;在一些前沿领域中,例如无人驾驶技术,一个更快的程序可以更快地完成对外界情况的判断,从而尽早作出反应,规避潜在的风险。我们以后的编写的程序,需要时刻考虑它运行时间的长短,也即程序的时间复杂度:

一般来说,复杂度是一个关于数据规模的函数。对于某些算法来说,相同数据规模的不同数据依然会造成算法的运行时间/空间的不同,因此我们通常使用算法的最坏时间复杂度,记为T(n)。 (OI-Wiki)

前面提到的时间频度T(n)中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律,为此我们引入时间复杂度的概念。一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数,记作T(n)=O(f(n)),它称为算法的渐进时间复杂度,简称时间复杂度。

1.2 时间复杂度举例

图片来自 sigongzi
O(n^2)
O(n^2)
O(n)
O(n^2)
O(nlogn)
O(sqrt(n))
图片来自 sigongzi

1.3 空间复杂度

空间复杂度就是程序运行所占用的内存。

我们不妨以 int 类型为例,在计算机中,一个 bit 是 8 个二进制位,而 int 类型数据是 32 个二进制位,所以一个 int 占 4 个 bit 。所以对于一个内存限制为 256M 的题,最多可以开 1024*1024*256/4 ≈ 64000000 个 int 。

大家做的题目中很难遇到卡内存的题,所以只需要计算好内存,正常开数组就不会爆,不太需要寻找内存更优的算法。

2 优化时空复杂度的算法

2.0 复杂问题中的暴力枚举方法

2.1 暴力枚举的局限性以及可能的改进方法

通过暴力穷举每一种可能状态得到答案是一种通用的解题方法,但是正如我们在解数学题过程中尽可能避免暴算一样,即便计算机拥有远超出人类的强大计算能力,在应付一个复杂度很高的做法的时候,也无法实现很大规模的问题的处理。因此我们可以通过去除掉一些不必要的枚举/对一些状态进行合并来简化,甚至可以通过将问题转化为更简单的问题的方法来提高运行的效率。

2.2 贪心算法