Coursera台大机器学习基础课程学习笔记

成都嗡嗡文化传媒有限公司 Coursera台大机器学习基础课程学习笔记1 - 机器学习定义及PLA算法最近在跟台大的这个课程，觉得不错，想把学习笔记发出来跟大家分享下，有错误希望大家指正。一机器学习是什么？感觉和Tom M. Mitchell的定义几乎一致，A computer program is said to learn fromexperienceE with respect to some class of tasks T and performance measureP, if its performance at tasks in T, as measured by P, improves with experience E.简而言之，就是我们想要机器在某些方面有提高（如搜索排名的质量，即NDCG提高），就给机器一些数据（用户的点击数据等各种）然后让机器获得某些经验（Learning to rank的一种模型，也就是数学公式）。这里有点需要强调，那就是提高指标，必须要有某种指标可以量化这种提高，这点还是很关键的，工业界做机器学习，首先关注data，其次就是有无成型的measurement，可以使Precision/Recall，也可以是NDCG等。二什么时候可以用机器学习？其实就三要素：1. 有规律可以学习；2. 编程很难做到；3. 有能够学习到规律的数据；编程很难做到可以有多种，大部分原因是系统太复杂，很难用Rule-based的东西去解决，例如搜索排名，现在影响排名的因素有超多几百种，不可能去想出这些因素的规则，因此，这时候用机器学习就是恰到好处。特别是移动互联网的今天，用户更容易接触互联网，产生的数据越来越多，那么要找到某些不容易实现的规律，用机器学习就是很好的了，这也是为啥机器学习这么火，其实我学机器学习不仅仅是一种投资（肯定它未来的发展前途），我想做的事情还有一点，就是通过它更深刻的理解人脑的学习过程，提高自己的学习效率和思维能力。三具体如何用机器学习？输入是两个：1 data；2假设集合。Data如何使用？通过提取出feature vector来使用，也就是那个training examples，假设集合是用来选取最终f的。也就是说，输出就是f（或近似f）。四第一个机器学习算法：PLA（Perceptron Learning Algorithm）课程讲述这个算法的总体思路如下（典型的提出问题，分析问题以及解决问题）:1. 通过信用卡问题引入PLA；2. 对问题用数学抽象，并得到目标函数；3. 详细解释PLA迭代（学习）过程；4. 证明PLA学习的过程可以收敛并会得到最优解；5. 分析PLA优缺点，并提出克服缺点的一些方法；这个算法本质上是线性分类器，针对给定的feature vector给出Yes或者No的回答下面是用这个算法去解决信用卡问题的数学抽象：这里的思想在于朴素的把从用户信息抽出来的一些feature（年龄等）量化并组成vector，然后乘以一个权重向量，并设定一个阈值，大于这个阈值就表示好，小于表示不好，很明显这个式子的未知变量有两个（实际只有一个）：1. 权重向量wi, 1=i concrete data的过程。回顾下我们在哪？在回答何时可以用机器学习的时候，我确实需要知道机器学习有什么类型，其实这些类型正好是围绕最后这张图而来的，确定这些类型就是逐个确定机器学习算法各个要素应该选用哪种方法的过程，只有当每一个都确定了，我们才能知道这个问题是否可以用机器学习来解决（见下图1，2，3，4）：总结：目前用的最多的分类是按照yn去分，课程给了个详细的分类，觉得很不错，有了全局观，后面就好易于理解了。Coursera台大机器学习课程笔记3 机器学习的可能性提纲：机器学习为什么可能？1. 引入计算橙球概率问题2. 通过用Hoeffdings inequality解决上面的问题，并得出PAC的概念，证明采样数据学习到的h的错误率可以和全局一致是PAC的3. 将得到的理论应用到机器学习，证明实际机器是可以学习机器学习的大多数情况下是让机器通过现有的训练集（D）的学习以获得预测未知数据的能力，即选择一个最佳的h做为学习结果，那么这种预测是可能的么？为什么在采样数据上得到的h可以认为适用于全局，也就是说其泛化性的本质是什么？课程首先引入一个情景：如果有一个装有很多（数量很大以至于无法通过数数解决）橙色球和绿色球的罐子，我们能不能推断橙色球的比例？很明显的思路是利用统计中抽样的方法，既然我们无法穷尽数遍所有罐子中的球，不如随机取出几个球，算出其中两种颜色球的比例去近似得到我们要的答案，这样真的可以么？我们都知道小概率事件也会发生，假如罐子里面大部分都是橙色球，而我们恰巧取出的都是绿色，这样我们就判断错了，那么到底通过抽样得出的比例能够说明什么呢？似乎两者不能直接划等号。由此，课程中引入了一个非常重要的概念，PAC，要理解这个，先得理解一个超级重要的不等式：Hoeffdings inequality这个不等书说明了对于未知的那个概率，我们的抽样概率可以根它足够接近只要抽样的样本够大或者容忍的限制变松，这个和我们的直觉是相符的。式子最后给出了PAC的概念，即概率上几乎正确。所以，我们通过采用算出的橙球的概率和全局橙球的概率相等是PAC的。这些和机器学习有什么关系？其实前文中提到的例子可以和机器学习问题一一对应：映射中最关键的点是讲抽样中橙球的概率理解为样本数据集D上h(x)错误的概率，以此推算出在所有数据上h(x)错误的概率，这也是机器学习能够工作的本质，即我们为啥在采样数据上得到了一个假设，就可以推到全局呢？因为两者的错误率是PAC的，只要我们保证前者小，后者也就小了。 请注意，以上都是对某个特定的假设，其在全局的表现可以和其在DataSet的表现PAC，保证DataSet表现好，就能够推断其能泛化。可是我们往往有很多假设，我们实际上是从很多假设中挑一个表现最好（Ein最小）的作为最终的假设，那么这样挑的过程中，最小的Ein其泛化能力一定是最好么？肯定不是。 上面的例子很形象，每一个罐子都是一个假设集合，我们默认是挑表现最好的，也就是全绿色（错误率为0）的那个假设。但是当从众多假设选择时，得到全对的概率也在增加，就像丢硬币一样，当有个150个童鞋同时丢硬币5次，那么这些人中出现5面同时朝上的概率为99%，所以表现好的有可能是小概率事件发生（毕竟对于每个假设其泛化能力是PAC），其不一定就有好的泛化能力（Ein和Eout相同），我们称这次数据是坏数据（可以理解为选到了泛化能力差的假设），在坏数据上，Ein和Eout的表现是差别很大的，这就是那个小概率事件，Hoeffdings inequality告诉我们，每个h在采样数据上Ein和Eout差别很大的概率很低（坏数据）：由于有这个bound，那么我们每次选取Ein最小的h就是合理的，因为如果M小N大，出现表现好的坏数据的假设几率降低了，我们选择表现后就有信心认为其有良好的泛化能力。总结一下：1. M小，N足够大，可以使得假设具有良好的泛化能力；2. 如果同时，Ein很小，那么这个假设就是有效地。机