机器学习第二章课件

Machine Learning(机器学习)回顾讲义 2:预测/分类的学习感知器假设集超平面/线性分类器感知器学习算法(PLA)迭代修正与改善感知器算的质量保证不可分数据口袋中保留最好的权值回到信用批准问题我们能使用什么假设集？假设集 H（候选公式集）训练实例D：(x1,y1),(xn,yn)（银行历史记录）学习算法 A未知目的函数f：xy(理想的信用批准公式）最终假设g f（“学习过的”公式的使用）年龄年龄23性别女年收入新台币 1,000,000居住年份1 年工作年份0.5 年短息债务新台币 200,000简单假设集：“感知器”x=(x1,x2,xd)表示“客户的特征”，计算一个加权“分数”并且 批准信用，如果 拒绝信用，如果y：+1(好),-1(坏),0 忽略线性公式 hH 是历史上被称之为“感知器”的假设年龄23年收入新台币 1,000,000工作年份0.5 年短息债务新台币 200,000感知器假设的矢量形式h(x)每个长序列 w 代表了一个假设 h()与长序列 x 相乘 使用长序列版本来简化符号感知器 h 看起来像什么？超平面/线性分类器客户特征 x：平面上的点（或Rd中的点）分类 y：(+1),(-1)假设 h：直线（或Rd中的超平面）在一面的影响是正面的，在另一面就是负面的不同的直线分类不同的客户感知器线性（二元）分类器a11wa01p b 0wT超平面/线性分类器T1.每个感知器都有一个判定边界 iw p+bi=02.一个感知器仅能实现一个二元分类3.多充感知器(S)能将数据分为 2S 个簇.从 H 中选择 gH=一切可能的感知器，g=?期望：g f（当 f 未知时很难）几乎必要的：g f on D，理想的 g(xn)=f(xn)=yn困难：H 有无限的规模思路：从一些g0开始，并“修正”它在D上的错误将用 g0 的权值矢量 w0 来代表 g0感知器学习算法从一些 w0（例如0）开始，并修正它在 D 上的错误t=0,1（1）找出 wt 的一个错误称之为（2）尝试改正错误，通过直到没有更多错误返回最后的 w（称之为 wpla）作为 g就是这样！承认错误等于改了一半PLA的实际实现从一些 w0（例如0）开始，并修正它在 D 上的错误t=0,1（1）找出 wt 的下一个错误称之为（2）尝试改正错误，通过直到完成一个没有遇到错误的完整周期接下来可以遵循朴素周期（1,N）或预先计算的随机周期示例1wOR0.50.51w =wT10.5 0.500.5p+b=+b =0.25+b=0b=0.25p1,t1 p2,t2 pQ,tQ121 t=1p1=122 t=0p2 =01p3 =t3=0 a=阶跃(n)=阶跃(w wp p)示例121.00.81w=a=阶跃 0.6)=0初始化:1w3第一个输入样本：示例1w1321w 取-p1，感知器不稳定因此用 1w+p1 取而代之 0.821.0+12.01.21wnew=1wold p2 =学习规则：学习规则：如果 t=1 且 a =0，那么 1wnew=1wold+p示例1w132a=阶跃0.4=1(不正确不正确)2.011.2 23.00.81wnew=1wold p2 =第二个输入样本：示例学习规则：学习规则：如果 t=0 且 a =1，那么 1wnew=1wold-p1w132正确正确(不正确不正确)ne wol d3.00.8013.00.21w=1 w p3 =如果 t=a，那么 1wnew=1wold第三个输入样本：示例a=阶跃0.8=1a=阶跃(WTp+b)a=阶跃(3.4)=1121 t=1p1=122 t=0p2 =01p3 =t3 =0 a=阶跃(-2.6)=0a=阶跃(-0.2)=0示例目录讲义 2:预测/分类的学习感知器假设集超平面/线性分类器感知器算法(PLA)迭代修正与改善感知器算法的质量保证不可分数据在口袋中保留最好的权值感知器算法的一些遗留问题修正 D 上的错误直至没有错误算法的：停止（没有任何错误）？（1）朴素周期的：？（2）随机周期的：？（3）其它不同的：？学习的：g f？（1）在 D 上，如果停止，是的（没有错误）（2）在 D 外：？（3）如果不停止：？【资料表明】如果有约束条件（），在足够的修正后，任何感知器算法都能有多样的停止方式线性分离性如果感知器算法停止（例如：没有足够错误），（必要条件）D 能让一些 w 完全无错称这样的 D 具有线性分离性线性分离性无线性分离性无线性分离性假设 D 具有线性分离性，感知器算法总会停止吗？输出输出：使使:前提前提：p1,t1,p2,t2,.,pQ,tQ 感知器算法的质量保证xnew xoldezx(k)x(k 1)z(k 1)12Q1 2Qz,z,.,z,z,z,.,z z(k 1)：qqqq 0 0 x*T zIf t 1,If t 0,x*T z感知器算法的质量保证k 次迭代后次迭代后,x(k)z(0)z(1).z(k 1)然后然后,x*Tx(k)x*Tz(0)x*Tz(1).x*Tz(k 1)x*T z(i),x*T x(k)k感知器算法的质量保证22(x*T x(k)2 x*x(k)22222(k)*T(xx(k)x(k)x*x*下边界下边界感知器算法的质量保证上边界上边界2x(k)xT(k)x(k)x(k 1)z(k 1)Tx(k 1)z(k 1)xT(k 1)x(k 1)2xT(k 1)z(k 1)zT(k 1)z(k 1)因为因为 xT(k 1)z(k 1)0222x(k)x(k 1)z(k 1)感知器算法的质量保证222x(k)z(0).z(k 1)感知器算法的质量保证使使 II=max|z(i)|2|x(k)|2 kII kII|x(k)|2 k 趣味时间让我们来取感知器算法修正错误数量的最大值 T。我们希望 T ，用上面两组公式表达最大值。（1）R/p（2）R2/p2（3）R/p2（4）p2/R2参考答案：2wfTwf /|wf|wf|的最大值是1，由于错误修正数 T 通过公式(T)x 常数 增加了内积，错误修正数的最大值为1/常数2感知器算法实质:wt 更一致于 wf具有线性分离性的 D 存在完美的 wf 使 yn=sign(wfTxn)wf 完美，因此每个 xn 正确地远离直线：wfTwt 增加，通过更新任何(xn(t),yn(t)：更新后wt 与 wf 显得更一致（真的？）感知器算法实质:wt 不能成长太快wf 仅在错误时改变 sign(wtTxn(t)yn yn wtTxn(t)0错误限制|wt|2 成长，即使是更新“最长的”xn 的时候从 W0=0 开始，T 次错误修正后，更多关于感知器算法质量保证只要具有线性分离性并能修正错误 wf 与 wt 的内积成长快速；wt 的长度成长缓慢 感知器算法的分界线越来越一致于 wf 停止正面意见易于实施，快速，适用于任何维度反面意见需要假设 D 具有线性分离性来停止 特征不能提前知道（已知 wf 的感知器算法中不需要）不能完全确定停止花费的时间（p 取决于 wf）尽管实际上很快假如 D 不具有线性分离性会怎样呢？不可分数据不可分数据多层感知器网络分界线分界线 1:12示例分界线分界线 2:36子网络 1与与示例输入输入分界线分界线34边界线边界线 3:边界线边界线 4:示例An example子网络 2输入输入与与分界线分界线1100 -11001W=10.50.751.50.25b=W21 1 0 00 0 1 1=b21.51.5=W31 1=30.5输入输入分界线分界线与与b=或或An example课后作业P1=1 1;P2=1 2;P3=2-1;P4=2 0;P5=-1 2;P6=-2 1;P7=-1-1;P8=-2-2