02 Learning to Answer Yes/No

从最简单最基础的二分类问题出发,演示一个简单机器学习算法PLA的完整过程,见详细课件

回顾

The Learning Problem:

takes

and

to get

that approximate target function

.

这节课foucus在Hypothesis Set,用Perceptron(linear binary classifiers)演示如何解决二分类问题。如根据用户age/salary/等特征判定是否发放信用卡。

PLA算法

算法形式极其简洁,权重x特征,大于零正例;小于零负例。

算法迭代步骤,关键点是有错才改:

  • 初始化
  • 找一个误分类点
  • 更新权重
  • 直到没有误分类点,返回

最重要的是当发现误分类点时,更新权重:

Intuition

ml-foundations-pla-intuition

最直观的Intutiton,每一步更新如何使结果更好?

: 误分则

夹角大于90度,更新

后使其往

靠近,夹角变小

: 误分则

夹角小于90度,更新

后使其离

更远,夹角变大

收敛性证明

PLA算法有前提是数据集线性可分

线性可分: Exists perfect

such that

如果数据集线性可分,能保证算法收敛吗?如何证明?思路是

  • 假设目标

完美分开数据集

  • 证明每一轮

至少线性增加

  • 证明每一轮

长度无法达到线性增加

  • 其夹角会递减,有限迭代后,

会收敛到

Inner product of

and

grows fast; length of

grows slowly. PLA ‘lines’ are more and more aligned with

then halts.

因为

将每个数据都正确分类,所以:

利用归纳法容易得到:

证明每次迭代,其內积至少是线性增长。內积大一定程度上反映两个向量夹角更接近,当然还需要考虑其长度。

考虑向量长度:

其中:

可以看到,向量长度增加速度为

,达不到线性。且

长度固定,综合上面两个结论:

最后推论出

存在上界:

PLA改进

PLA只能处理线性可分数据集,Pocket PLA稍微改进:

If

makes fewer mistakes than

, replace

by

.

数据集不可分情况下也能保证找到较优的解。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人人都是极客

AI芯片之卷积神经网络原理

卷积神经网络(Convolutional Neural Network,CNN)是一种前馈神经网络,它的人工神经元可以响应一部分覆盖范围内的周围单元,对于大型图...

1313
来自专栏云时之间

深度学习与TensorFlow:实现卷积神经网络

在上一篇文章,我们介绍了CNN的一些基本概念和lenet神经网络的架构,今天这一篇文章我们就模仿lenet网络去微调,使其符合mnist数据集的要求,并且达到我...

1674
来自专栏机器学习养成记

聚类(三):KNN算法(R语言)

k最临近(KNN)算法是最简单的分类算法之一,属于有监督的机器学习算法。 算法流程 KNN的核心思想是:找出特征空间中距离待分类点最近的k个点,如果这k个点大多...

4137
来自专栏开心的学习之路

神经网络体系搭建(三)——卷积神经网络

本篇是神经网络体系搭建的第三篇,解决体系搭建的卷积神经网络相关问题,详见神经网络体系搭建(序) 卷积神经网络(CNN) ? CNN是什么 卷积神经网络是一种空间...

3968
来自专栏绿巨人专栏

神经网络学习笔记-03-循环神经网络-反向传播计算公式的证明

2866
来自专栏算法channel

深度学习|卷积神经网络(CNN)介绍(后篇)

01 — 回顾 昨天介绍了CNN的卷积操作,能减少权重参数的个数,卷积操作涉及到三个超参数: 深度(Depth) 步长(Stride) 零填充(Zero-pad...

5065
来自专栏机器学习算法工程师

深入浅出解读卷积神经网络

作者:石文华 编辑:田 旭 卷积神经网络 ? 图1 全连接神经网络结构图 ? 图2 卷积神经网络结构图 卷积神经网络和全连接的神经网络结构上的差异还是比较大的,...

2834
来自专栏SnailTyan

Single Shot MultiBox Detector论文翻译——中英文对照

SSD: Single Shot MultiBox Detector Abstract We present a method for detecting ob...

2710
来自专栏xingoo, 一个梦想做发明家的程序员

吴恩达机器学习笔记 —— 18 大规模机器学习

有的时候数据量会影响算法的结果,如果样本数据量很大,使用梯度下降优化参数时,一次调整参数需要计算全量的样本,非常耗时。

951
来自专栏超然的博客

MIT-线性代数笔记(1-6)

  对方程组中某个方程进行时的那个的数乘和加减,将某一未知系数变为零,来削弱未知数个数

1252

扫码关注云+社区

领取腾讯云代金券