问题 假设空间的样本复杂度(sample complexity):随着问题规模的增长导致所需训练样本的增长称为sample complexity. 实际情况中,最有可能限制学习器成功的因素是训练数据的有限性. 在使用学习器的过程中,我们希望得到与训练数据拟合程度高的假设(hypothesis).(在前面文章中提到,这样的假设我们称之为g). 这就要求训练错误率为0.而实际上,大部分情况下,我们找不到这样的hypothesis(通过学习机得到的hypothesis)在训练集上有错误率为0. 所以退

提纲: 机器学习为什么可能? 引入计算橙球概率问题 通过用Hoeffding's inequality解决上面的问题,并得出PAC的概念,证明采样数据学习到的h的错误率可以和全局一致是PAC的 将得到的理论应用到机器学习,证明实际机器是可以学习 机器学习的大多数情况下是让机器通过现有的训练集(D)的学习以获得预测未知数据的能力,即选择一个最佳的h做为学习结果,那么这种预测是可能的么?为什么在采样数据上得到的h可以认为适用于全局,也就是说其泛化性的本质是什么? 课程首先引入一个情景: 如果有一个装

第四讲 机器学习的可行性 一.Hoeffding's Inequality \(P[\left | \nu -\mu  \right |>\epsilon ] \leq 2exp(-2\epsilon^{2}N)\) (1) in-sample error, 也就是在样本里出现的error,\(E_{in}\) is probably close to out-of-sample error \(E_{out}\) (within \(\epsilon\)) 推出一个类似的公式: \(P[\le

机器学习基石 4 Feasibility of Learning Learning is Impossible? 机器学习:通过现有的训练集 \(D\) 学习,得到预测函数 \(h(x)\) 使得它接近于目标函数 \(f(x)\). 问题:这种预测是可能的么?其泛化性的本质是什么?是什么保证了 \(h(x) \approx f(x)\) ? Probability to the Rescue 情景:有一个装有很多很多珠子的罐子,珠子的颜色是橙色和绿色,那么我们可以通过抽样的方法来估计橙色珠子的比

这一节讲述的是机器学习的核心.根本性问题——学习的可行性.学过机器学习的我们都知道,要衡量一个机器学习算法是否具有学习能力,看的不是这个模型在已有的训练数据集上的表现如何,而是这个模型在训练数据外的数据(一般我们称为测试数据)上性能的好坏,我们把这个性能称为泛化能力(generalization ability),机器学习中,我们的目标是寻找高泛化能力的模型:有些模型虽然在训练数据集上分类效果很好,甚至正确率达到100%,但是在测试数据集上效果很差,这样的模型泛化能力很差,这种现象也叫过拟合(O

(注:由于之前进行了吴恩达机器学习课程的学习,其中有部分内容与机器学习基石的内容重叠,所以以下该系列的笔记只记录新的知识) <机器学习基石>课程围绕着下面这四个问题而展开: 主要内容: 一.什么时候适合用机器学习? 二.该课程所采用的一套符号表示 三.机器学习的流程 四.感知机算法 五.学习的类型 六.机器学习的无效性 七.机器学习的可行性(在无效性的前提下加一些条件限制) 一.什么时候适合用机器学习? 对于第一点:我们学习的对象必须要存在某些显式的或者潜在的规律,否则,如果学习对象都毫无规律

上节课介绍了机器学习可以分为不同的类型.其中,监督式学习中的二元分类和回归分析是最常见的也是最重要的机器学习问题.本节课,我们将介绍机器学习的可行性,讨论问题是否可以使用机器学习来解决. 一.Learning is Impossible 首先,考虑这样一个例子,如下图所示,有3个label为-1的九宫格和3个label为+1的九宫格.根据这6个样本,提取相应label下的特征,预测右边九宫格是属于-1还是+1?结果是,如果依据对称性,我们会把它归为+1:如果依据九宫格左上角是否是黑色,我们会把它

Empiricial Risk Minimization 统计学习理论是整个机器学习到框架.试想我们学习的目的是什么呢?当然是为了具备用合理的方式处理问题的能力.统计学习理论要解决的问题就是基于数据找到一个预测函数.经验风险最小化(Empiricial Risk Minimization,ERM)[2]是统计学习理论中准则之一,常用于给出学习算法(learning algorithms)性能的理论边界. 假定给定两个数据空间\(X\)和\(Y\), 我们想学习到一个假设函数(hypothesis

最近一直在处理samtools freebayes gatk 产生的snp数据, 结果文件都是vcf,于是自己就写了相应的类,但是总是不够完善. 海宝推荐这个模块,他都推荐了 我还抱着我那烂代码不放干啥 之前写的就当练习类了 安装: sudo pip install pyvcf 然后报错说没有counter模块,于是: sudo pip install counter 然后就安装好了 简单实用: import vcf myvcf = vcf.Reader(open('testpyvcf', 'r

Foundations of Machine Learning: The PAC Learning Framework(2) (一)假设集有限在一致性下的学习界. 在上一篇文章中我们介绍了PAC-learnable的定义,以及证明了一个例子是PAC-learnable. 这一节我们介绍当hypothesis set是有限时,且算法$\mathcal{A}$相对与样本S满足一致性条件下的PAC问题.下一节介绍不一致条件下的PAC问题. 一致性(consistent):如果一个算法产生的假设$h_s

统计学场景: 一个罐子中有红球和绿球,红球比例$v$未知,数量未知,如何得到红球比例?方法---随机抽样N个球,在其中红球占比为$u$ 由hoeffding可以知道:$P(|u-v|>\epsilon)\leq 2e^{-2\epsilon^2N}$ 对应到机器学习分类问题:目标函数为$f(x)$,现要估计$h(x)$的错误率假设在罐子中,将$[f(x_i)\neq h(x_i)]$的x标成红色将$[f(x_i)= h(x_i)]$的x标成绿色此时红色比例$v$即为$E_{out}$ 此时数据集

Hoeffding公式为 \epsilon]\leq{2e^{-2\epsilon^2N}}"> 如果把Training error和Test error分别看成和的话，Hoeffding告诉我们，取样出来的v和总的u大部分是比较接近的，很小的概率是差很远的，即Ein和Eout差很远，这种情况称为Bad sample. 本来只有一个coin，丢5次，5次head的概率就是1/32。现在有150个coin，可以选择出现5次的那个coin，这时概率会大大增加，变成了1-(31/32)^150

Hoeffding霍夫丁不等式 在<>第八章"集成学习"部分, 考虑二分类问题\(y \in \{-1, +1\}\) 和真实函数\(f\), 假定基分类器的错误率为\(\epsilon\), 即对每个基分类器\(h_{i}\)有 \[ \begin{equation} P(h_{i}(x) \neq f(x)) = \epsilon \end{equation} \] 假设集成通过简单投票法结合\(T\)个基分类器, 若有超过半数的基分类器正确, 则集成分类就正确: \[

网易公开课,第9,10课 notes,http://cs229.stanford.edu/notes/cs229-notes4.pdf 这章要讨论的问题是,如何去评价和选择学习算法   Bias/variance tradeoff 还是用这组图,学习算法追求的是generalization error(对未知数据的预测误差),而不是training error(只是对训练集) 最左边,underfit,我们说这种学习算法有较大的bias Informally, we define the bia

[1] ML Introduction a. supervised learning & unsupervised learning 监督学习:从给定的训练数据集中学习出一个函数(模型参数),当新的数据到来时,可以根据这个函数预测结果.监督学习的训练集要求包括输入输出,也可以说是特征和目标.训练集中的目标是由人标注的.常用于:训练神经网络.决策树.回归分析.统计分类 无监督学习:输入数据没有被标记,也没有确定的结果.样本数据类别未知,需要根据样本间的相似性对样本集进行分类,试图使类内差距最小化,

第六讲 第五讲主要讲了机器学习可能性,两个问题,(1)\(E_{in} 要和 E_{out}\) 有很接近,(2)\(E_{in}\)要足够小. 对于第一个假设,根据Hoefding's Inequality 可以得到,\( P[|E_{in} - E_{out}| > \epsilon] < 2Mexp(-2\epsilon^2N)\) 对于上述的\(M\)来说,如果 \(M < \infty\),则当\(N\)足够大时,\(P\)会比较小,也就是坏事情出现的概率比较小,机器学习是可能

本文结构: 什么是集成学习? 为什么集成的效果就会好于单个学习器? 如何生成个体学习器? 什么是 Boosting? Adaboost 算法? 什么是集成学习 集成学习就是将多个弱的学习器结合起来组成一个强的学习器. 这就涉及到,先产生一组‘个体学习器’,再用一个策略将它们结合起来. 个体学习器可以选择:决策树,神经网络.集成时可以所有个体学习器属于同一类算法:全是决策树,或全是神经网络:也可以来自不同的算法.结合策略:例如分类问题,可以用投票法,少数服从多数. 之所以用这种集成的思想,是因为单

斯坦福大学机器学习,EM算法求解高斯混合模型.一种高斯混合模型算法的改进方法---将聚类算法与传统高斯混合模型结合起来的建模方法, 并同时提出的运用距离加权的矢量量化方法获取初始值,并采用衡量相似度的方法来融合高斯分量.从对比结果可以看出,基于聚类的高斯混合模型的说话人识别相对于传统的高斯混合模型在识别率上有所提高. ------------------------------ 高斯模型有单高斯模型(SGM)和混合高斯模型(GMM)两种. (1)单高斯模型: 为简单起见,阈值t的选取一般靠经验值

紧接上一讲的Break Point of H.有一个非常intuition的结论,如果break point在k取到了,那么k+1, k+2,... 都是break point. 那么除此之外,我们还能获得那些讯息? 这里举了一些例子,核心就是说下面的事情 简言之,如果H有Break Point k,那么当N大于k的时候,mH(N)会大大地缩减(对于binary classification来说是pow(2, N) ). 按照这个思路,自然就想知道,既然mH(N)会大大缩减,能缩减到啥程度?(如

这一节的核心内容在于如何由hoeffding不等式 关联到机器学习的可行性. 这个PAC很形象又准确,描述了“当前的可能性大概是正确的”,即某个概率的上届. hoeffding在机器学习上的关联就是: 如果样本数量足够大,那么在训练集上获得的学习效果是可以平移到测试集上的.即如下, 这里保证的仅仅是“训练集的效果平移到测试集”,平移的仅仅是效果,没说效果好坏:如果训练效果是垃圾的,那么测试效果也基本是垃圾的. 如果假设空间是有限的,那么结果又如何呢?如下, 如果假设空间是有限的,根据公式推导:当