ML基石_56_TheoryOfGeneralization

RECAP

机器学习是可行的,如果假设集H是有限的并且统计样本数据(statistical data)很大。

那么,问题来了,PLA算法中,假设集是二维空间中的直线,有无数条,不符合上面的条件,那么还可行么?

SOLUTION

m增长速度受限

将类似的假设集合并,如果是二分类问题,有N个点的话,理论上会有2^N个分类情况mHm_H,但实际上并不会这么多。

mHm_H: max number of dichotomies B(N,K)B(N,K):如果break point在第k个点上,N个数据点最大的dichotomies ∑k−1i=0C(N,k) \sum_{i=0}^{k-1} C(N,k):B(N,K)B(N,K)的上限,增长速度是O(Nk−1)O(N^{k-1})

mH<=B(N,K)<=∑i=0k−1C(N,k)<=2N

m_H<=B(N,K)<= \sum_{i=0}^{k-1} C(N,k) <=2^N

通过上面的公式,我们知道: 如果可以将mHm_H代替原不等式的M,那么多项式函数的增长速度小于指数函数的增长速度,所以误差率的上限是有保证的,也就是说学习是可行的。

注意: 对于converx图,mH=2Nm_H=2^N,这种情况很难比较。

将m带回原式中的M

通过一些数学变换,可以将m带回原式中的M,得到

这表明,随着数据集的增多,如果mHm_H的增长速度受限,或者说其有break point点,那么当N足够大的时候,学习是可行的。

这就是VC维理论。

例子

总结

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏菩提树下的杨过

SqlTransaction事务使用示例

using System; using System.Data; using System.Data.SqlClient; using System.Co...

1988
来自专栏码匠的流水账

聊聊EurekaRibbonClientConfiguration

spring-cloud-netflix-eureka-client-2.0.0.RELEASE-sources.jar!/org/springframewor...

1471
来自专栏闻道于事

商城项目整理(三)JDBC增删改查

商品表的增加,修改,删除,订单表的增加,确认,用户表的查看,日志表的增加,查看 商品表建表语句: 1 create table TEST.GOODS_TABL...

5885
来自专栏积累沉淀

Hive2.0.0操作HBase 1.2.1报错解决

首先看错  org.apache.hive.service.cli.HiveSQLException: Failed to open new session: ...

2549
来自专栏菩提树下的杨过

winform中linkLabel的用法(示例)

private void Form1_Load(object sender, EventArgs e)         {             this...

1965
来自专栏DT乱“码”

简单的考勤系统

连接数据库类 package com.lianrui.it; import java.sql.Connection; import java.sql.Driv...

3779
来自专栏跟着阿笨一起玩NET

[C#]工具类—FTP上传下载

  不错的文章:http://www.cnblogs.com/greatverve/archive/2012/03/03/csharp-ftp.html

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

windows程序设计-第四章 system1.c

/*---------------------------------------------------- SYSMETS1.C -- System M...

26810
来自专栏跟着阿笨一起玩NET

winform treeView 数据绑定

1102
来自专栏成长道路

JDBC动态SQL语句连接orcale数据库的工具类

import java.sql.Connection; import java.sql.DriverManager; import java.sql.P...

2700

扫码关注云+社区