机器学习---计算学习理论

   <p>如果你不是数学系的，就不要看这个了。</p>    <p> </p>    <p>因为以下内容全都在证明机器学习的方法是有效的，你可以用机器学习来得到你想要的结果。然而对于编程或者使用这个方法的人来说，你只要放心大胆地用就行了。就像你知道1+1=2，你并不需要知道它为什么等于，反正你可以用。</p>    <p><span style="color:rgb(54,46,43)">以下使用到的图片来自上海交大杨旸老师的课件，网址如下：http://bcmi.sjtu.edu.cn/~yangyang/ml/</span></p>    <p><span style="color:#ff6666">写在前边，这课我只听懂了一部分，后来知道这个其实并不需要了解，就没再细细研究，可能到后边会突然就没有内容了，强迫症患者慎阅。</span></p>    <p>首先我们来看几个概念：</p>    <p><img alt="" src="https://simg.open-open.com/show/bec9896ab12e3794da74af3514eb5084.png"></p>    <p>m：训练数据</p>    <p>H：假设空间，比如我们的映射函数是线性的，那么这个空间就包括满足假设条件的所有线性函数（可能是这样的）</p>    <p>e(就用它代替吧)：准确率，编程的时候输出的准确率就是它</p>    <p>（这符号真...）：我们使用不同的训练数据集产生的准确率会有不同，这个就是代表我们选的数据集是好的概率（比较模糊）</p>    <p><img alt="" src="https://simg.open-open.com/show/b666b43608f0b3b1c4cd9b2570b5e885.png"></p>    <p>PAC framework：假设所有的训练数据都是分类准确的，没有噪声的。但是这在现实中基本不可能达到的</p>    <p>Agnostic framework：训练数据是有噪声的。符合实际情况</p>    <p><img alt="" src="https://simg.open-open.com/show/b88a8671f296cb479f3dd678e4767302.png">t</p>    <p>图中的c是完全分类准确的空间，h是我们的假设空间，有部分没有圈到的就是说明我们预测的不准。</p>    <p>D表示理想状态中全部的数据，下边那个符号就是表示分类错误的概率（就是C和H不相交的那部分，我以为只有右边那个月牙）</p>    <p><img alt="" src="https://simg.open-open.com/show/b16e1eb41db3dc934dd6c7a3f9f8c9e3.png"></p>    <p>下边这个公式和上一页一样，解释一下上边那个公式</p>    <p>S是训练用的数据集（也就是理想完整数据集D的一部分），那么我们计算错误率的方法就是，找到所有使用训练得到的映射函数分类错误的结果，用错误的个数除以总训练个数就是错误率~</p>    <p>上边求和里边的（一普斯龙）就是一个脉冲函数，表示，如果C和H不相等就取1，相等就取0</p>    <p><img alt="" src="https://simg.open-open.com/show/4d56ebd7ef0a4361b9645b2bf12ffedc.png"></p>    <p>这就是一个定理，所有事件并起来的概率小于等于它们分别的概率相加</p>    <p><img alt="" src="https://simg.open-open.com/show/da8d94b690399e57e236d5761b57c707.png"></p>    <p>这也是一个定理公式，记住就行了，叫做Hoeffding不等式</p>    <p>r就是你指定的一个常数。</p>    <p>Zi等于1和等于0的概率已经知道了，就是（fai）和1-（fai），我们训练好的模型估计出来的值就是（fai估），但是这个公式中的（fai估）是需要求所有估计值的平均的，然和前边那个概率就小于等于后边这个式子咯。m代表样本的个数</p>    <p><img alt="" src="https://simg.open-open.com/show/fa2f1e87f1ca12e8636f13697466405e.png"></p>    <p>Version Space：之前说的那个很大的假设空间里边，和训练数据完全匹配的那些个映射关系</p>    <p>我们已经知道了这么多的概念，然后我们到底需要证明的是什么呢？就是下图中的两个式子</p>    <p><img alt="" src="https://simg.open-open.com/show/b30d9df8c5d94d75af8540c0cc24746f.png"></p>    <p>只要证明上边这两个式子成立，那么我们就可以说我们的学习方法是正确的可行的。</p>    <p>就是我们训练得到的映射关系用在理想的完整的数据上的错误率约等于0（也就是我们使用部分训练数据是OK的）</p>    <p>并且要让错误率约等于0的概率约等于1（也就是说我们无论取什么样的训练数据都没有影响）</p>    <p>证明了这两个内容，那么我们就可以说学习的方法是正确可行的。</p>    <p>怎么证明约等于0呢？其实只要证明它有上界和下界就OK</p>    <p>至于具体的证明步骤，嘿嘿，没懂。</p>    <p>来自： <a href="/misc/goto?guid=4959670825793545029" rel="nofollow">http://blog.csdn.net/sun7_she/article/details/51163128</a></p>