林轩田机器学习基石2:学习回答Yes/No(Learning to Answer Yes/No)

2024-08-21 07:48

本文主要是介绍林轩田机器学习基石2:学习回答Yes/No(Learning to Answer Yes/No),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

欢迎关注公众号-AI圈终身学习。
公众号首页回复“机器学习”查看所有系列文章。


上节林老师讲了机器学习的定义与流程:

总结就是:训练数据D在演算法A的观察学习下,从假设集合H中,选择出最好的一个假设h得到最终的模型函数g。

本节笔记Lecture 2-Learning to Answer Yes/No包含内容如下:

  • When Can Machines Learn?(什么时候用机器学习)
    • 感知器假设集(Perceptron Hypothesis Set)
    • 感知器演算法(Perceptron Learning Algorithm(PLA))
    • PLA保证(Guarantee of PLA)
    • 线性不可分数据(Non-Separable Data)

一、感知器假设集(Perceptron Hypothesis Set)

1.1 例子

本节依旧使用上文的信用卡例子,即银行需要根据用户数据来判断是否给其发信用卡。假设用户有性别、年龄、薪水、负债、工龄等属性:

我们有许多人这样的数据,这些数据组成数据集,记为D。现在的问题就变成根据D,用演算法A从假设集合H取选出最好的一个假设h,得到h对应的模型函数g,如下图:

那么什么假设集我们可以用呢?本文讲解一个简单但是重要的假设集:感知器(Perceptron)。

1.2 感知器假设集

我们记用户数据的属性集合为 X = ( x 1 , x 2 , . . . , x d ) X=(x_1,x_2,...,x_d) X=(x1,x2,...,xd),他有对应的权重集合 W = ( w 1 , w 2 , . . . , w d ) W=(w_1,w_2,...,w_d) W=(w1,w2,...,wd)(这就是一个假设集)表示属性的重要程度,越重要的属性x,其对应的权重w越大。通过特征的加权求和得分结果 W T X W^TX WTX,比较得分结果与阈值大小:

  • 得分结果>阈值,发信用卡。
  • 得分结果<阈值,不发信用卡。

最终的感知器假设集就是h(x),公式如下:

通常我们不会专门写一个门槛值,为了表述方便,通常会用 w 0 = − t h r e s h o l d w_0=-threshold w0=threshold表示阈值,引入 x 0 = 1 与 w 0 x_0=1与w_0 x0=1w0相乘,最终可以简化成如下写法:

1.3 感知器的形状

在二维平面上,感知器公式展开为 h ( x ) = s i g n ( w 0 + w 1 x 1 + w 2 x 2 ) h(x)=sign(w_0+w_1x_1+w_2x_2) h(x)=sign(w0+w1x1+w2x2),可以看到下面的图有圈(表示+1)和叉(表示-1),中间将他们分开的线就是感知器划分线,这条线为 w 0 + w 1 x 1 + w 2 x 2 = 0 w_0+w_1x_1+w_2x_2=0 w0+w1x1+w2x2=0

感知器又将线性分类器(linear classifiers),它不一定局限于二维平面,所有满足 W T X = 0 W^TX=0 WTX=0形式的模型,都可以叫线性分类器。

我们的假设集合H就表示二维平面所有的线,那么我们的演算法A就需要从所有的H中选择出最好的一个假设。如果我们细心会发现上图中经过演算法更新后,右边的线分类效果明显优于左边的线。

二、感知器演算法(Perceptron Learning Algorithm(PLA))

2.1 PLA原理

我们已经知道,在二维平面里,感知器演算法的核心目的就是从无数条线中找出最合适的一条线,把数据分开。一开始我们随机初始化一条分割线,演算法的步骤只有两步:

  1. 遍历找出犯错的点
  2. 用犯错的点做修正

找出犯错的点比较容易,如果感知机计算出来的值和标签不一致即为犯错点。

修正过程林老师用图进行了讲解:

  • 若正例识别成负,此时 y n W T x n ≤ 0 y_{n}W^{T}x_{n} \leq 0 ynWTxn0 ,推出 W T x n ≤ 0 W^{T}x_{n} \leq 0 WTxn0。根据高中数学可知,向量W和向量 x n x_n xn的夹角大于90°,我们通过 W = W + x n W=W+x_n W=W+xn旋转修正这个W,使得 W 和 x n W和x_n Wxn夹角小于90°,如下图,紫色线表示修正后的结果:

  • 若负例识别成正,此时 y n W T x n ≤ 0 y_{n}W^{T}x_{n} \leq 0 ynWTxn0,推出 W T x n ≥ 0 W^{T}x_{n} \geq 0 WTxn0。根据高中数学可知,向量W和向量 x n x_n xn的夹角小于90°,我们通过 W = W − x n W=W-x_n W=Wxn旋转修正W,使得 W 和 x n W和x_n Wxn夹角大于90°,如下图,紫色线表示修正后的结果:

这里需要注意W表示感知器分割线 W T X = 0 W^TX=0 WTX=0的法向量,法向量所指的方向即为正。

通常我们要遍历所有的点进行修正,所以具体实现的算法又叫Cyclic PLA(Perceptron Learning Algorithm)算法,记不住我也觉得不重要。

2.2 PLA过程可视化

林老师讲解了一个动态更新的过程,假设初始化 W = 0 W=0 W=0,这个时候感知器就在原点:

这个时候它看哪个点都是错的,所以根据图中第一个黑点 x 1 x_1 x1更新W,紫色的线为法向量W,当前时刻为t,t+1就表示更新后的权重:

根据法向量W可以画出一条垂直于W的分割线 W T X = 0 W^TX=0 WTX=0,发现第九个点正类分到了负类,旋转更新红色的W(t)为紫色的W(t+1):

然后不断循环:




最后更新完成,这是一条完美的分割线。

2.3 思考为什么PLA有效

根据PLA的更新规则:

请思考下面哪条公式一定是对的:

答案是第③条,我们只要在更新公式 W t + 1 = W t + y n x n W_{t+1}=W_{t}+y_nx_n Wt+1=Wt+ynxn两边同时乘以 y n x n y_nx_n ynxn即可得到③式。这个式子一定程度上说明了PLA的有效性。下面给出两个例子:

假设我们一条正例被识别成了负例,此时有:

  • y n = 1 y_n = 1 yn=1

所以有:

  • w t T x n w^T_{t}x_n wtTxn < 0
  • w t + 1 T x n ≥ w t T x n w^T_{t+1}x_n \geq w^T_{t}x_n wt+1TxnwtTxn

也就是它每次更新尝试把感知器的得分和,从负修改为正,说明它在努力修改错误。

同理假设我们一条负例被识别成了正例,此时有:

  • y n = − 1 y_n = -1 yn=1

所以有:

  • w t T x n w^T_{t}x_n wtTxn > 0
  • w t + 1 T x n ≤ w t T x n w^T_{t+1}x_n \leq w^T_{t}x_n wt+1TxnwtTxn

也就是它每次更新尝试把感知器的得分和,从正修改为负,说明它也在努力修改错误。

三、PLA数学保证(Guarantee of PLA)

现在我们关心两个问题:

  • PLA总是可停的吗?
  • PLA何时才停?
3.1 PLA总是可停的吗?

PLA可停需要对数据集有要求。

如果PLA停止了,则对于感知器来说,所有点都没有错误了,这样的数据集我们叫线性可分的,比如下图:

对于左边的图是线性可分的。但是中间的图有一个圆圈在红叉的区域,右边的图是一个圆,PLA都没法停止。

3.2 PLA何时才停?

本节主要讲PLA的两点:收敛性和有效性。

对于线性可分的数据集,一定存在一个完美但是我们不可知的 W f W_f Wf,使得这条线完美的划分所有数据
y n = s i g n ( W f T x n ) y_n=sign(W_f^Tx_n) yn=sign(WfTxn)

那么对于所有的点一定满足:

  • 所有的点被划分在正确的区域
  • 到这点线的距离一定是大于0的

因此有:

PLA每次是通过错误的点 ( x n , y n ) (x_n, y_n) (xn,yn)来修正 W t W_t Wt,如果 W t 离 W f W_t离W_f WtWf越来越接近,那么就证明了PLA的有效性,数学上可以用内积表示两个向量的相似性:

通过推导可以发现每一次更新他们的内积越来越大,但是并不一定他们越来越相近,因为这可能有两种情况:

  • 向量夹角变小
  • 向量模长变大

实际上,每次PLA修正都是因为出现了错误的点,可以证明 W t W_t Wt的模长增长不会太快。对于错误的点有:

根据PLA的增长公式 W t + 1 = W t + y n x n W_{t+1}=W_t+y_nx_n Wt+1=Wt+ynxn,两边平方有:

也就是说 ∣ ∣ W t ∣ ∣ ||W_t|| Wt的增长项只有 max ⁡ n ∣ ∣ x n ∣ ∣ \underset{n}{\operatorname{max}}||x_n|| nmaxxn,每次变化有所限制。

作业:初始化 W 0 = 0 W_0=0 W0=0,PLA修正T次后,可以证明:

w f T ∣ ∣ w f ∣ ∣ w T T ∣ ∣ w T ∣ ∣ ≥ T c o n s t a n t \cfrac{w_f^T}{||w_f||}\cfrac{w_T^T}{||w_T||}\geq \sqrt{T}constant wfwfTwTwTTT constant

请计算constant是什么。

证明如下:

所以 c o n s t a n t = min ⁡ n y n w f T x n ∣ ∣ w f ∣ ∣ max ⁡ n ∣ ∣ x n ∣ ∣ constant=\cfrac{\underset{n}{\operatorname{min}}y_nw^T_fx_n}{||w_f||\underset{n}{\operatorname{max}}||x_n||} constant=wfnmaxxnnminynwfTxn
又因为 1 ≥ w f T ∣ ∣ w f ∣ ∣ w T T ∣ ∣ w T ∣ ∣ ≥ T c o n s t a n t 1 \geq \cfrac{w_f^T}{||w_f||}\cfrac{w_T^T}{||w_T||}\geq \sqrt{T}constant 1wfwfTwTwTTT constant

T ≤ 1 c o n s t a n t 2 T\leq \cfrac{1}{constant^2} Tconstant21

因此我们知道PLA一定会在 1 c o n s t a n t 2 \cfrac{1}{constant^2} constant21次内收敛,且随着PLA修改次数t的增加, W t 越 来 越 接 近 W f W_t越来越接近W_f WtWf,证明了PLA有效性和收敛性。

四、线性不可分数据(Non-Separable Data)

现在我们有两个问题:

  • 虽然我们证明了PLA会收敛,但是它取决于我们不知道的参数 W f W_f Wf,因此我们不知道它何时会收敛。
  • 如果数据并不完全的线性可分, W f W_f Wf根本不存在,此时该怎么办?

在现实中,几乎不可能出现理想的线性可分数据,比如对于这样的数据:

我们可以把它看成线性可分数据中混入了一些噪音数据。我们知道PLA最终的划分完全无误,因此解决这个问题一个很好的思路就是通过演算法获得错误点最少的一条线,如上图所示,公式表示如下:


但是这是一个NP-hard问题,现在的技术无法求解。因此引出了一种PLA的贪心算法Pocket PLA:每次更新确保错误点更少

模型保存的假设参数我们放在口袋(Pocket)里,记为 w ^ \widehat{w} w ,其对应的错误点个数为 n t n_t nt;如果更新后的线 w t + 1 w_{t+1} wt+1划分的错误点个数小于 n t n_t nt,则更新 w ^ = w t + 1 \widehat{w}=w_{t+1} w =wt+1

五、总结

本节主要介绍了感知器的假设集、演算法和收敛性有效性相关的数学知识;针对非线性可分数据,可以使用PLA修正算法Pocket Algorithm进行处理。

这篇关于林轩田机器学习基石2:学习回答Yes/No(Learning to Answer Yes/No)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1092555

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

引言 高斯过程(Gaussian Process,简称GP)是一种概率模型,用于描述一组随机变量的联合概率分布,其中任何一个有限维度的子集都具有高斯分布 文章目录 引言一、高斯过程1.1 基本定义1.1.1 随机过程1.1.2 高斯分布 1.2 高斯过程的特性1.2.1 联合高斯性1.2.2 均值函数1.2.3 协方差函数(或核函数) 1.3 核函数1.4 高斯过程回归(Gauss

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络(1)sklearn

系列文章目录 监督学习:参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归(SAheart.csv) 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

线性代数|机器学习-P36在图中找聚类

文章目录 1. 常见图结构2. 谱聚类 感觉后面几节课的内容跨越太大,需要补充太多的知识点,教授讲得内容跨越较大,一般一节课的内容是书本上的一章节内容,所以看视频比较吃力,需要先预习课本内容后才能够很好的理解教授讲解的知识点。 1. 常见图结构 假设我们有如下图结构: Adjacency Matrix:行和列表示的是节点的位置,A[i,j]表示的第 i 个节点和第 j 个

Node.js学习记录(二)

目录 一、express 1、初识express 2、安装express 3、创建并启动web服务器 4、监听 GET&POST 请求、响应内容给客户端 5、获取URL中携带的查询参数 6、获取URL中动态参数 7、静态资源托管 二、工具nodemon 三、express路由 1、express中路由 2、路由的匹配 3、路由模块化 4、路由模块添加前缀 四、中间件