❶ 200分求动态规划详解!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
嗯···我学动归不是很久,同样是迷惘过,估计两个月前刚刚开窍……
你看他写的什么无后效性什么最优子结构的就头大,我也头大%…………
动态规划一般解决两类问题,一类是最优化问题,就是问你最大价值最小数什么的,另一类是方案总数问题。
细分的话类型很多,
我见得多的(我是高二学生,目前在筹备NOIP)
(你那题多我就只说名字了)
背包,楼上连9讲都放上来了我就不多说了……
最长不上升不下降子序列问题(比如说潘帕斯雄鹰生日模拟赛的飞翔,就是很经典的不下降的变形)
资源分配问题(比如说橱窗布置,马棚问题,机器分配问题)
区间动归(乘积最大,能量项链等等)
最长公共子序列问题(有个遗传编码好像);
解决方案树的比如说爬楼梯问题……………………
动态规划的类型很多很多,因为他很灵活的,我们老师曾经给我们找了100个DP方程,但是那都没有用,强记根本记不住,关键是理解。
深入一点的就有DP的优化,时间空间的降维(就是用别的方法去做,或者比如说背包本来是二维的空间优化过该成一维的了),树形DP(这个我也不会)。
(优化里面有个很经典的题《过河》)
我对DP是属于那种突然就开了窍的……别看说“动态规划”什么的唬人,其实就是一个比较一个计算,知道他干什么了题上来就有头绪,方程啊思想啊就有了……
主要也是多看题吧,从简单的开始,理解他的思想……自己写动归的时候注意下面几个问题:
1、大前提是确定你做的是动归题……看得多了也就知道自己面对的是什么类型的题了
2、次前提是想法要对(我做题的时候先想这道题时间空间的维度,然后根据这个去想方程),方程正确,
实在想不起来可以先看题解,去理解人家的思想之后,不要看标程把程序做出来……
3、注意数组不要开的过小,一般都是左右都开大一点,比如他的数据范围是1~100 ,数组就开0~101.这个是防越界的,因为很多DP赋初值的时候会用到F[0],F[0,0]
4、初始值要正确,因为很多DP其他地方都是正确的因为初始值赋错了而全部过不了的情况是很常见的……(比如说USACO里面的货币系统)
5、DP循环的范围要正确,一般根据题来判断范围写多少的(比如说橱窗问题,今天下午写这个题因为循环写错了一直AC不了)
USACO里也有很多DP题,可以做……
以上全部手打,希望能对你有所帮助。
我也是正在学习的人,上面的东西不一定全部正确,但是对我而言很受用,也算是我的经验了。希望日后能一起学习交流外加进步喽
QQ:340131980
1. 资源问题1
-----机器分配问题
F[I,j]:=max(f[i-1,k]+w[i,j-k])
2. 资源问题2
------01背包问题
F[I,j]:=max(f[i-1,j-v]+w,f[i-1,j]);
3. 线性动态规划1
-----朴素最长非降子序列
F:=max{f[j]+1}
4. 剖分问题1
-----石子合并
F[i,j]:=min(f[i,k]+f[k+1,j]+sum[i,j]);
5. 剖分问题2
-----多边形剖分
F[I,j]:=min(f[i,k]+f[k,j]+a[k]*a[j]*a);
6. 剖分问题3
------乘积最大
f[i,j]:=max(f[k,j-1]*mult[k,i]);
7. 资源问题3
-----系统可靠性(完全背包)
F[i,j]:=max{f[i-1,j-c*k]*P[I,x]}
8. 贪心的动态规划1
-----快餐问题
F[i,j,k]:=max{f[i-1,j',k']+(T-(j-j')*p1-(k-k')*p2) div p3}
9. 贪心的动态规划2
-----过河 f=min{{f(i-k)} (not stone)
{f(i-k)}+1} (stone); +贪心压缩状态
10. 剖分问题4
-----多边形-讨论的动态规划
F[i,j]:=max{正正 f[I,k]*f[k+1,j];
负负 g[I,k]*f[k+1,j];
正负 g[I,k]*f[k+1,j];
负正 f[I,k]*g[k+1,j];} g为min
11. 树型动态规划1
-----加分二叉树 (从两侧到根结点模型)
F[I,j]:=max{f[I,k-1]*f[k+1,j]+c[k]}
12. 树型动态规划2
-----选课 (多叉树转二叉树,自顶向下模型)
F[I,j]表示以i为根节点选j门功课得到的最大学分
f[i,j]:=max{f[t.l,k]+f[t.r,j-k-1]+c}
13. 计数问题1
-----砝码称重
f[f[0]+1]=f[j]+k*w[j];
(1<=i<=n; 1<=j<=f[0]; 1<=k<=a;)
14. 递推天地1
------核电站问题
f[-1]:=1; f[0]:=1;
f:=2*f[i-1]-f[i-1-m]
15. 递推天地2
------数的划分
f[i,j]:=f[i-j,j]+f[i-1,j-1];
16. 最大子矩阵1
-----一最大01子矩阵
f[i,j]:=min(f[i-1,j],v[i,j-1],v[i-1,j-1])+1;
ans:=maxvalue(f);
17. 判定性问题1
-----能否被4整除
g[1,0]:=true; g[1,1]:=false; g[1,2]:=false; g[1,3]:=false;
g[i,j]:=g[i-1,k] and ((k+a[i,p]) mod 4 = j)
18. 判定性问题2
-----能否被k整除
f[I,j±n mod k]:=f[i-1,j]; -k<=j<=k; 1<=i<=n
20. 线型动态规划2
-----方块消除游戏
f[i,i-1,0]:=0
f[i,j,k]:=max{f[i,j-1,0]+sqr(len(j)+k),
f[i,p,k+len[j]]+f[p+1,j-1,0]}
ans:=f[1,m,0]
21. 线型动态规划3
-----最长公共子串,LCS问题
f[i,j]={0(i=0)&(j=0);
f[i-1,j-1]+1 (i>0,j>0,x=y[j]);
max{f[i,j-1]+f[i-1,j]}} (i>0,j>0,x<>y[j]);
22. 最大子矩阵2
-----最大带权01子矩阵O(n^2*m)
枚举行的起始,压缩进数列,求最大字段和,遇0则清零
23. 资源问题4
-----装箱问题(判定性01背包)
f[j]:=(f[j] or f[j-v]);
24. 数字三角形1
-----朴素の数字三角形
f[i,j]:=max(f[i+1,j]+a[I,j],f[i+1,j+1]+a[i,j]);
25. 数字三角形2
-----晴天小猪历险记之Hill
同一阶段上暴力动态规划
if[i,j]:=min(f[i,j-1],f[I,j+1],f[i-1,j],f[i-1,j-1])+a[i,j]
26. 双向动态规划1
数字三角形3
-----小胖办证
f[i,j]:=max(f[i-1,j]+a[i,j],f[i,j-1]+a[i,j],f[i,j+1]+a[i,j])
27. 数字三角形4
-----过河卒
//边界初始化
f[i,j]:=f[i-1,j]+f[i,j-1];
28. 数字三角形5
-----朴素的打砖块
f[i,j,k]:=max(f[i-1,j-k,p]+sum[i,k],f[i,j,k]);
29. 数字三角形6
-----优化的打砖块
f[I,j,k]:=max{g[i-1,j-k,k-1]+sum[I,k]}
30. 线性动态规划3
-----打鼹鼠’
f:=f[j]+1;(abs(x-x[j])+abs(y-y[j])<=t-t[j])
31. 树形动态规划3
-----贪吃的九头龙
32. 状态压缩动态规划1
-----炮兵阵地
Max(f[Q*(r+1)+k],g[j]+num[k])
If (map and plan[k]=0) and
((plan[P] or plan[q]) and plan[k]=0)
33. 递推天地3
-----情书抄写员
f:=f[i-1]+k*f[i-2]
34. 递推天地4
-----错位排列
f:=(i-1)(f[i-2]+f[i-1]);
f[n]:=n*f[n-1]+(-1)^(n-2);
35. 递推天地5
-----直线分平面最大区域数
f[n]:=f[n-1]+n
:=n*(n+1) div 2 + 1;
36. 递推天地6
-----折线分平面最大区域数
f[n]:=(n-1)(2*n-1)+2*n;
37. 递推天地7
-----封闭曲线分平面最大区域数
f[n]:=f[n-1]+2*(n-1)
:=sqr(n)-n+2;
38 递推天地8
-----凸多边形分三角形方法数
f[n]:=C(2*n-2,n-1) div n;
对于k边形
f[k]:=C(2*k-4,k-2) div (k-1); //(k>=3)
39 递推天地9
-----Catalan数列一般形式
1,1,2,5,14,42,132
f[n]:=C(2k,k) div (k+1);
40 递推天地10
-----彩灯布置
排列组合中的环形染色问题
f[n]:=f[n-1]*(m-2)+f[n-2]*(m-1); (f[1]:=m; f[2]:=m(m-1);
41 线性动态规划4
-----找数
线性扫描
sum:=f+g[j];
(if sum=Aim then getout; if sum<Aim then inc(i) else inc(j);)
42 线性动态规划5
-----隐形的翅膀
min:=min{abs(w/w[j]-gold)};
if w/w[j]<gold then inc(i) else inc(j);
43 剖分问题5
-----最大奖励
f:=max(f,f[j]+(sum[j]-sum)*i-t
44 最短路1
-----Floyd
f[i,j]:=max(f[i,j],f[i,k]+f[k,j]);
ans[q[i,j,k]]:=ans[q[i,j,k]]+s[i,q[i,j,k]]*s[q[i,j,k],j]/s[i,j];
45 剖分问题6
-----小H的小屋
F[l,m,n]:=f[l-x,m-1,n-k]+S(x,k);
46 计数问题2
-----陨石的秘密(排列组合中的计数问题)
Ans[l1,l2,l3,D]:=f[l1+1,l2,l3,D+1]-f[l1+1,l2,l3,D];
F[l1,l2,l3,D]:=Sigma(f[o,p,q,d-1]*f[l1-o,l2-p,l3-q,d]);
47 线性动态规划
------合唱队形
两次F:=max{f[j]+1}+枚举中央结点
48 资源问题
------明明的预算方案:加花的动态规划
f[i,j]:=max(f[i,j],f[l,j-v-v[fb]-v[fa]]+v*p+v[fb]*p[fb]+v[fa]*p[fa]);
49 资源问题
-----化工场装箱员
50 树形动态规划
-----聚会的快乐
f[i,2]:=max(f[i,0],f[i,1]);
f[i,1]:=sigma(f[t^.son,0]);
f[i,0]:=sigma(f[t^.son,3]);
51 树形动态规划
-----皇宫看守
f[i,2]:=max(f[i,0],f[i,1]);
f[i,1]:=sigma(f[t^.son,0]);
f[i,0]:=sigma(f[t^.son,3]);
52 递推天地
-----盒子与球
f[i,1]:=1;
f[i,j]:=j*(f[i-1,j-1]+f[i-1,j]);
53 双重动态规划
-----有限的基因序列
f:=min{f[j]+1}
g[c,i,j]:=(g[a,i,j] and g[b,i,j]) or (g[c,i,j])
54 最大子矩阵问题
-----居住空间
f[i,j,k]:=min(min(min(f[i-1,j,k],f[i,j-1,k]),
min(f[i,j,k-1],f[i-1,j-1,k])),
min(min(f[i-1,j,k-1],f[i,j-1,k-1]),
f[i-1,j-1,k-1]))+1;
55 线性动态规划
------日程安排
f:=max{f[j]}+P[I]; (e[j]<s)
56 递推天地
------组合数
C[I,j]:=C[i-1,j]+C[I-1,j-1]
C[I,0]:=1
57 树形动态规划
-----有向树k中值问题
F[I,r,k]:=max{max{f[l,I,j]+f[r,I,k-j-1]},f[f[l,r,j]+f[r,r,k-j]+w[I,r]]}
58 树形动态规划
-----CTSC 2001选课
F[I,j]:=w(if i∈P)+f[l,k]+f[r,m-k](0≤k≤m)(if l<>0)
59 线性动态规划
-----多重历史
f[i,j]:=sigma{f[i-k,j-1]}(if checked)
60 背包问题(+-1背包问题+回溯)
-----CEOI1998 Substract
f[i,j]:=f[i-1,j-a] or f[i-1,j+a]
61 线性动态规划(字符串)
-----NOI 2000 古城之谜
f[i,1,1]:=min{f[i+length(s),2,1], f[i+length(s),1,1]+1}f[i,1,2]:=min{f[i+length(s),1,2]+words[s],f[i+length(s),1,2]+words[s]}
62 线性动态规划
-----最少单词个数
f[i,j]:=max{f[I,j],f[u-1,j-1]+l}
63 线型动态规划
-----APIO2007 数据备份
状态压缩+剪掉每个阶段j前j*2个状态和j*2+200后的状态贪心动态规划
f:=min(g[i-2]+s,f[i-1]);
64 树形动态规划
-----APIO2007 风铃
f:=f[l]+f[r]+{1 (if c[l]<c[r])}
g:=1(d[l]<>d[r]) 0(d[l]=d[r])
g[l]=g[r]=1 then Halt;
65 地图动态规划
-----NOI 2005 adv19910
F[t,i,j]:=max{f[t-1,i-dx[d[[t]],j-dy[d[k]]]+1],f[t-1,i,j];
66 地图动态规划
-----优化的NOI 2005 adv19910
F[k,i,j]:=max{f[k-1,i,p]+1} j-b[k]<=p<=j;
67 目标动态规划
-----CEOI98 subtra
F[I,j]:=f[I-1,j+a] or f[i-1,j-a]
68 目标动态规划
----- Vijos 1037搭建双塔问题
F[value,delta]:=g[value+a,delta+a] or g[value,delta-a]
69 树形动态规划
-----有线电视网
f[i,p]:=max(f[i,p],f[i,p-q]+f[j,q]-map[i,j])
leaves>=p>=l, 1<=q<=p;
70 地图动态规划
-----vijos某题
F[I,j]:=min(f[i-1,j-1],f[I,j-1],f[i-1,j]);
71 最大子矩阵问题
-----最大字段和问题
f:=max(f[i-1]+b,b); f[1]:=b[1]
72 最大子矩阵问题
-----最大子立方体问题
枚举一组边i的起始,压缩进矩阵 B[I,j]+=a[x,I,j]
枚举另外一组边的其实,做最大子矩阵
73 括号序列
-----线型动态规划
f[I,j]:=min(f[I,j],f[i+1,j-1](ss[j]=”()”or(”[]”)),
f[I+1,j+1]+1 (s[j]=”(”or”[” ] , f[I,j-1]+1(s[j]=”)”or”]” )
74 棋盘切割
-----线型动态规划
f[k,x1,y1,x2,y2]=min{min{f[k-1,x1,y1,a,y2]+s[a+1,y1,x2,y2],
f[k-1,a+1,y1,x2,y2]+s[x1,y1,a,y2]
min{}}
75 概率动态规划
-----聪聪和可可(NOI2005)
x:=p[p[i,j],j]
f[I,j]:=(f[x,b[j,k]]+f[x,j])/(l[j]+1)+1
f[I,i]=0
f[x,j]=1
76 概率动态规划
-----血缘关系
F[A, B]=(f[A0, B]+P[A1, B])/2
f[I,i]=1
f[I,j]=0(I,j无相同基因)
77 线性动态规划
-----决斗
F[I,j]=(f[I,j] and f[k,j]) and (e[I,k] or e[j,k]),i<k<j
78 线性动态规划
-----舞蹈家
F[x,y,k]=min(f[a[k],y,k+1]+w[x,a[k]],f[x,a[k],k+1]+w[y,a[k]])
79 线性动态规划
-----积木游戏
F[I,a,b,k]=max(f[I,a+1,b,k],f[i+1,a+1,a+1,k’],f[I,a+1,a+1,k’])
80 树形动态规划(双次记录)
-----NOI2003 逃学的小孩
朴素的话枚举节点i和离其最远的两个节点 j,k O(n^2)
每个节点记录最大的两个值,并记录这最大值分别是从哪个相邻节点传过来的。当遍历到某个孩子节点的时候,只需检查最大值是否是从该孩子节点传递来的。如果是,就取次大,否则取最大值
81 树形动态规划(完全二叉树)
-----NOI2006 网络收费
F[I,j,k]表示在点i所管辖的所有用户中,有j个用户为A,在I的每个祖先u上,如果N[a]>N则标0否则标1,用二进制状态压缩进k中,在这种情况下的最小花费
F[I,j,k]:=min{f[l,u,k and (s<<(i-1))]+w1,f[r,j-u,k and(s<<(i-1))]}
82 树形动态规划
-----IOI2005 河流
F:=max
83 记忆化搜索
-----Vijos某题,忘了
F[pre,h,m]:=sigma{SDP(I,h+1,M+i)} (pre<=i<=M+1)
84 状态压缩动态规划
-----APIO 2007 动物园
f[I,k]:=f[i-1,k and not (1<<4)] + NewAddVal
85 树形动态规划
-----访问术馆
f[i,j-c×2]:= max ( f[l,k], f[r,j-c×2-k] )
86 字符串动态规划
-----Ural 1002 Phone
if exist((s,j,i-j)) then f:=min(f,f[j]+1);
87 多进程动态规划
-----CEOI 2005 service
Min( f[i,j,k], f[i-1,j,k] + c[t[i-1],t] )
Min( f[i,t[i-1],k], f[i-1,j,k] + c[j,t] )
Min( f[i,j,t[i-1]], f[i-1,j,k] + c[k,t] )
88 多进程动态规划
-----Vijos1143 三取方格数
max(f[i,j,k,l],f[i-1,j-R[m,1],k-R[m,2],l-R[m,3]]);
if (j=k) and (k=l) then inc(f[i,j,k,l],a[j,i-j]) else
if (j=k) then inc(f[i,j,k,l],a[j,i-j]+a[l,i-l]) else
if (k=l) then inc(f[i,j,k,l],a[j,i-j]+a[k,i-k]) else
if (j=l) then inc(f[i,j,k,l],a[j,i-j]+a[k,i-k]) else
inc(f[i,j,k,l],a[j,i-j]+a[k,i-k]+a[l,i-l]);
89 线型动态规划
-----IOI 2000 邮局问题
f[i,j]:=min(f[I,j],f[k,j-1]+d[k+1,i]);
90 线型动态规划
-----Vijos 1198 最佳课题选择
if j-k>=0 then Min(f[i,j],f[i-1,j-k]+time(i,k));
91 背包问题
----- USACO Raucous Rockers
多个背包,不可以重复放物品,但放物品的顺序有限制。
F[I,j,k]表示决策到第i个物品、第j个背包,此背包花费了k的空间。
f[I,j,k]:=max(f[I-1,j,k],f[I-1,j,k-t]+p,f[i-1,j-1,maxtime-t])
92 多进程动态规划
-----巡游加拿大(IOI95、USACO)
d[i,j]=max{d[k,j]+1(a[k,i] & j<k<i),d[j,k]+1(a[I,j] & (k<j))}。
f[i,j]表示从起点出发,一个人到达i,另一个人到达j时经过的城市数。d[i,j]=d[j,i],所以我们限制i>j
分析状态(i,j),它可能是(k,j)(j<k<i)中k到达i得到(方式1),也可能是(j,k)(k<j)中k超过j到达i得到(方式2)。但它不能是(i,k)(k<j)中k到达j得到,因为这样可能会出现重复路径。即使不会出现重复路径,那么它由(j,k)通过方式2同样可以得到,所以不会遗漏解 时间复杂度O(n3)
93 动态规划
-----ZOJ cheese
f[i,j]:=f[i-kk*zl[u,1],j-kk*zl[u,2]]+a[i-kk*zl[u,1],j-kk*zl[u,2]]
94 动态规划
-----NOI 2004 berry 线性
F[I,1]:=s
F[I,j]:=max{min{s-s[l-1]},f[l-1,j-1]} (2≤j≤k, j≤l≤i)
95 动态规划
-----NOI 2004 berry 完全无向图
F[I,j]:=f[i-1,j] or (j≥w) and (f[i-1,j-w])
96 动态规划
-----石子合并 四边形不等式优化
m[i,j]=max{m[i+1,j], m[i,j-1]}+t[i,j]
97 动态规划
-----CEOI 2005 service
(k≥long,i≥1)g[i, j, k]=max{g[i-1,j,k-long]+1,g[i-1,j,k]}
(k<long,i≥1) g[i, j, k]=max{g[i-1,j-1,t-long]+1,g[i-1,j,k]}
(0≤j≤m, 0≤k<t) g[0,j,k]=0;
ans:=g[n,m,0]。
状态优化:g[i, j]=min{g[i-1,j],g[i-1,j-1]+long}
其中(a, b)+long=(a’, b’)的计算方法为:
当b+long ≤t时: a’=a; b’=b+long;
当b+long >t时: a’=a+1; b’=long;
规划的边界条件:
当0≤i≤n时,g[i,0]=(0,0)
98 动态规划
-----AHOI 2006宝库通道
f[k]:=max{f[k-1]+x[k,j]-x[k,i-1], x[k,j]-x[k,i-1]}
99 动态规划
-----Travel
A) 费用最少的旅行计划。
设f表示从起点到第i个旅店住宿一天的最小费用;g表示从起点到第i个旅店住宿一天,在满足最小费用的前提下所需要的最少天数。那么:
f=f[x]+v, g=g[x]+1
x满足:
1、 x<i,且d – d[x] <= 800(一天的最大行程)。
2、 对于所有的t < i, d – d[t] <= 800,都必须满足:
A. g[x] < g[t](f[x] = f[t]时) B. f[x] < f[t] (其他情况)
f[0] = 0,g[0] = 0。 Ans:=f[n + 1],g[n+1]。
B). 天数最少的旅行计划。
方法其实和第一问十分类似。
设g’表示从起点到第i个旅店住宿一天的最少天数;f’表示从起点到第i个旅店住宿一天,在满足最小天数前提下所需要的最少费用。那么:
g’ = g’[x] + 1, f’ = f’[x] + v
x满足:
1、 x<i,且d – d[x] <= 800(一天的最大行程)。
2、 对于所有的t < i, d – d[t] <= 800,都必须满足:
f’[x] < f’[t] g’[x] = g’[t]时
g’[x] < g’[t] 其他情况
f’[0] = 0,g’[0] = 0。 Ans:=f’[n + 1],g’[n+1]。
100 动态规划
-----NOI 2007 cash
y:=f[j]/(a[j]*c[j]+b[j]);
g:=c[j]*y*a+y*b;
f:=max(f,g)
❷ 论图形组织器 图形组织器的分类包括
[摘 要] 图形组织器是一种可由学习者自由控制、功能强大的可视化学习工具。本文从学习工具的应用角度讨论了图形组织器的内涵、功能、理论基础、类型、选用和创建原则等基本问题,以期对图形组织器有一个基本认识。
[关键词] 图形组织器;功能;类型;选用框架;创建原则
[中图分类号] G43 [文献标识码] A [文章编号] 1672―0008(2009)06-0061-06
一、图形组织器的内涵
简单说来,图形组织器(Graphic Organizers)是一种用于表现学习过程和结果的图形结构形式。作为一种学习工具,图形是形式,是载体,对学习的组织是目的,是关键。目前,国外对图形组织器的理解主要有两种视角。
1.外形特点的视角
图形组织器是指知识图、概念图、故事图、认知组织器、先行组织者或概念图示等[1]。如图形组织器是一种图解书面或口头陈述的图形方式,是表征信息的可视化方式[2],等等。
2.应用功能的视角
图形组织器具有广泛的应用领域和强大的功能。国外许多研究结合图形组织器的外形和内涵从多方面阐述了图形组织器的功能作用:(1)图形组织器是知识、概念或观点的可视化表征。它有助于学习者提高学习兴趣、激发动机、减低或释放厌倦感、提高回忆率、阐明信息、组织思维和促进理解[3] 。(2)图形组织器是用可视化方式表征信息的图形结构,可用于各种学习活动中,如头脑风暴、观点生成、分析信息、组织信息和表达发现等等[4]。(3)图形组织器是建构知识和组织信息的视图化方式。它有助于学习者将许多杂乱或弥散的信息转换或精炼为一种结构化的、便于阅读的图形化方式,其目的就是用易于理解的方式表达复杂信息[5]。(4)图形组织器是一种视觉化和图形化的表现方式,用以描述某一学习任务中事实之间、术语之间或观点之间的关系,具有系列的工具作用,如使学习者思维可视化,使学习者通过探索理解复杂内容的意义,用可视化的方式表征不同部分之间的连接和关系,如相似性、差异性、序列性等[6]。
对图形组织器内涵的理解关键要把握两大要义,其一,图形组织器是一种视图化或可视化的形式,如各种各样的图形或表格结构形式;其二,图形组织器的目的或功能是促进学习效果或效率,如分类、分析、比较、概念辨析、概括特点、头脑风暴或提高记忆或检索。
二、图形组织器的功能
图形组织器具有多方面的功能或作用,对不同类型的学习者来说都是一种理想的学习工具。俗话说,一幅图画胜过千言万语。
从学习者角度而言,有研究认为,图形组织器作为学习工具有助于使之成为一个投入型的学习者,增进学习动力、讲究学习策略、习惯交流协作和提高学习的责任感[7]。运用图形组织器,学习者通过精简归纳、聚焦强调、解释演绎等方式,有助于使复杂的、杂乱的信息变为有意义的表现形式;有助于引导信息搜集、目标锁定、展现所得、表现所缺的方式,保持探究学习活动的方向;通过聚焦思维或活动目标、识别相关站点或领域,起到思维导图的作用;通过创建图形组织器,可增进对学习内容的理解、促进对话协作、汇聚观点和提高决策力,等等[8]。
从促进学习者认知或思维活动发展的角度而言,有研究总结了图形组织器的10大功能:①总括文本内容(勾勒要点);②确定或阐释信息(运用图形辅助或图解);③表达理解(运用自己的语言复述);④确认和解释与文本相关的关键词汇;⑤考察分析文本(如要点、人物行为、问题解决、因果关系、事实/意见或观点);⑥文本推理(如完形阅读);⑦比较/对比(如人物、场景、事件);⑧对文本的感受(与个体经验或感情相关联);⑨选择(从目标出发选择恰当的参考资源);⑩验证对文本的理解(如通过预测结果或行为)[9]。
从学习工具的角度来理解,更有助于从实用的角度完整地把握图形组织器的功能。总括起来,图形组织器可作为如下系列学习工具:
(1)结构化或网络化工具。图形组织器有助于学习者结构化地展现事件、要素或观点的关联、模式和关系;有助于学习者围绕某一主题或论点组织素材或整合知识;有助于勾画所学内容的基本结构(基本概念以及概念之间的关系);描述与学习主题相关的已有知识结构,并在现有的知识结构加入新概念、新观点或新知识。按布鲁纳的结构教学理论来看,掌握学习内容的基本结构是有效学习的主要标志。
(2)记忆、储存与检索工具。好的图形组织器是知识的记忆、储存和检索方式,可以充当知识的寄居地或附带有效的线索提示;可以促进知识的长期记忆。记忆发生时,首先是编码,如能成为长时记忆,就可持久地储存,编码转换为事件或信息能成为持久的形式[10]。图形化的呈现方式能刺激学生大脑建立意义并与记忆建立联系。
(3)知识凝练与聚合工具。图形组织器高度浓缩大量的知识,提炼知识的核心内容,可以使学习者聚集相关研究以快速分辨哪些是他们更需要的信息,如,学习者可以带一个准备好的纲要或大纲去图书馆或上网查找资料[11]。
(4)内化与建构工具。当学习者把大量的数据、信息转换或凝练成某种图形组织器时,可以帮助理解和阐释,实现新旧知识的联系,促进同化与顺应,实现知识的综合或拓展,从而形成自己的观点或知识组块等。因为创建图形组织器的过程,实际上是一个知识的理解、组织、阐释、反思和修正的过程,是一个与所学内容对象不断对话的过程。
(5)问题求解工具。图形组织器有助于学习者分解问题目标,围绕目标,促进学习者或学习者之间实现头脑风暴、观点发散,集聚问题求解的方法、程序、过程或步骤,筛选或优化问题求解的方案,并在问题求解的过程中不断产生新知识、新问题或新方法,从而培养学习者解决问题的能力。
(6)创造工具。图形组织器有助于学习者运行发散和聚合思维,实践创新思维。比如,与线性的文本不同,图形里的观点要素或图解可以任意编排,学习者可以通过反复不断地调整图解形式来增添新的想法。
(7)交流与协作工具。知识的学习离不开社会性建构,即社会性交流与协作。一个组织良好的图形能简洁明了地表达想法和理解,吸引他人的注意力,且对关键内容的记忆也比纯语言交流要长久。个体学习者所创建的图形代表了一种可能的信息或观念,可用于与他人分享和交流,并为他人增删信息提供了一种方便的载体。群体学习者所创建的图形则代表了群组的信息或观念,图形组织器充当了发散和聚合群组观点的有力工具,因为可视化的形式可以及时将分散在个人脑中的灵感组合成一个整体性的结构。在小组学习、项目学习、问题求解等学习活动中,图形组织器通常是学习者就某一问题展开讨论,集合众人想法的有效工具。
(8)评价工具。图形组织器有助于学习者检验知识获取过程和结果的质量。一般来说,只有想不清楚,没有画不清楚的图形。如果学习者对所学内容不理解或无法抽象概括,那么就不可能运用图形组织器来表示所学内容。通过图形组织器,不仅可以检视学习者对所学内容的把握程度,考量学习者的逻辑思维过程和知识面,而且可以诊断学习者在哪些方面存在思维和知识的残缺。
此外,学习者可以运用图形组织器充当过程性评价工具,比如,一个图形组织器作品反映了学习者在某一特定领域内对知识的理解程度,包括知识相互联系的多样化程度,学习者可以在创建作品的过程中反思自己对知识的掌握程度,并且实施及时有效的修订。
三、图形组织器的理论基础
图形组织器为何能有效地促进学习?其学理何在?相关的理论研究揭示了这一问题。概括地说,图形组织器的理论基础主要包括双重编码理论、脑科学、经验之塔、学习理论和知识管理。
1.双重编码理论
加拿大心理学家佩维奥(Dual Coding Theory,A. Paivio,1984)认为,人类存在着两个认知子系统,一个是专用于对非语词事物、事件(即映像)的表征与处理,另一个则用于语言的处理。由此也就存在两种不同的表征单元,即适用于心理映像的“图像单元”和适用于语言实体的“语言单元”。前者是根据部分与整体的关系组织的,后者是根据联想与层级组织的。双重编码理论可用于许多认知学习,如记忆、问题求解、概念学习和语言习得。而且说明了吉尔福特智力理论中空间能力的重要性,因为大量通过视觉获得的映像所涉及的正是空间领域的信息。因此,在信息的储存、加工与提取中,语言与非语言的信息加工过程是同样重要的。人类可同时运用视觉和语言的形式呈现信息,以增强信息的回忆与识别。
2.脑科学
研究表明,人的大脑分左右两个半球,其结构几乎完全一样,但功能却不相同。左脑主司语言表达、逻辑思维、数理演绎、字词记忆、计算和顺序、分类、智力和科学;右脑主司非语言表达、创新思维、形象性感知、具体事物记忆、视觉空间观察、音乐、感觉力和艺术。正是大脑两半球分工合作的和谐统一,才使大脑发挥高度复杂的整体功能。人类天生就有运用图像的能力。据研究,大多数的人脑活动涉及到视觉图像的处理和分析过程,视觉表征在不同的任务中优于语言表征。根据现代脑科学的研究,右脑的视觉思维围绕左脑逻辑思维所求解的难题进行新旧知觉信息的同构活动是复杂的,甚至是无意识的。在无意识活动中,大脑处于一种高度的自由开放态,使新输入的知觉信息和积淀知觉信息的同构活动十分活跃,容易获得一个全新的“知觉形象”,反馈给左脑进行逻辑鉴别,如不符合要求,则以新的“目的意象”送给右脑的视觉思维,如此反复多次直至获得一个符合目的的推论结果。
3.经验之塔
该理论的提出者是美国视听教育家戴尔(Cone of Experience,E.Dale,1946;1964)。经验之塔是一种关于学习经验分类的理论模型,其表现的学习经验分为三大类:一是做的“做”的学习经验,包括有目的的、直接的经验,设计的经验和演戏的经验。二是“观察”的学习经验,包括演示、校外学习旅行、展览、电视电影、广播、录音、静画。三是“使用符号”的学习经验,包括视觉符号和言语符号。各类学习经验是相互联系、相互渗透。该理论对教学(包括学习者)如何有效处理直接经验与间接经验的联系,解决具体经验和抽象经验的矛盾,防止“言语主义”――从概念到概念的现象等问题具有现实意义。图形组织器具有隶属或贯穿三类学习经验的特点,在“做、观察和使用符号”的学习经验类别中具有相应的作用。
4.学习理论
图形组织器的功用可从诸多学习理论中找到强力的支撑。比如,行为主义关注可观察和测量的外显学习行为,强调学习是刺激与反应的联结,注重强化;认知主义认为学习在于内部认知的变化,学习过程是信息加工过程,是认知结构的组织与再组织,强调同化与顺应和对学习任务的整体理解,强调直觉思维的作用(直觉思维通常采取图像方式进行);建构主义认为,学习是学习者在原有认知结构基础上主动建构的过程或结果,每个人都能生成自己的认知模式和个性化理解。知识是意义建构的结果,知识的建构需要对所学内容进行阐释、交流、表达或展现,这是建构知识的必要方式,也是检测知识建构水平的有效方式,知识建构需要运用多样化的知识外部表征(包括图形组织器),需要运用各种学习工具和学习资源展开问题求解活动。
5.知识管理
知识管理是指组织或个人运用相关工具和方法来获取、存储、共享、应用和创新知识的过程。每个学习者都是知识管理者,知识管理的效率直接决定学习的效率。从知识获取到创新的整个过程涉及到显性与隐性知识的相互转换,在这些转换过程中,知识可视化是一种重要的形式和手段。比如,野中郁次郎(Nonaka,1991)认为,将隐性知识显性化意味着用某种方式来表达只可意会不可言传的东西,其最有力的工具之一就是知识可视化。知识可视化能使知识更好地被获取和讨论,也有益于更普遍地管理知识。
此外,知识可视化有助于解决组织中一系列与知识有关的重要问题,如知识传播中的不对称性,利用启发性的草图和丰富的图像隐喻促进群体知识创新,通过精简压缩的方式减轻学习者的信息负荷,等等[12]。
四、图形组织器的类型
图形组织器存在许多类型。由于每个图形组织器都有显见的外在形式,因此,掌握图形组织器类型最为直接简单的方式就是按其外形特征来划分。根据相关研究,按照外形特征,可将图形组织器划分为五种,每一种类型都有其主要的功能或用途。如表1所示[13]。
五、图形组织器的选用
图形组织器种类繁多,功能多样,每一种图形组织器都可以用来支持多种学习或思维发展。选用图形组织器的关键是:一要掌握图形组织器的类别、功能或主要用途;二要理解学习或思维发展的目的,从而使手段和目的之间建立起映射关系。那么,图形组织器可以有效地促进哪些类型的学习或思维发展呢?我们认为,学习者在选用图形组织器时,可以灵活地运用如下参照框架。
1.以认知目标为选用参照框架
认知目标分类以美国布卢姆的研究最为着名,他们在半个世纪的研究中,先后在推出两个版本的认知目标分类(1956,2001)。在第一个版本(1956)中,他们把认知目标分为知道、领会、应用、分析、综合和评价。在第二个版本(2001)中,他们强调了学习者在有意义学习中的主动、认知和建构过程,强调了学习者是如何获取知识和如何思考的。与第一版的单向分类维度不同,第二版采用了“知识”和“认知过程”二维分类。知识是指学习时涉及的相关内容,从具体到抽象分为四类:事实性知识、概念知识、程序知识和元认知知识;认知过程包含学习时要掌握的学业行为表现,依据认知复杂度由低到高排列包括六个层级:记忆、理解、应用、分析、评价和创造[14]。这两个版本的认知目标分类均可以作为学习选用图形组织器的参照框架。如表2所示。
第二版的认知目标的“知识维”和“认知过程维”更可以作为学习者选用图形组织器的参照框架。比如,就实现知识维来说,学习者可以运用图形组织器促进事实性知识(术语、具体细节和要素)、概念性知识(类别与分类、原理与概括、理论/模式与结构)、程序性知识(具体学科技能和算法、技巧和方法知识、确定何时运用适当程序知识)、元认知知识(包括策略、认知任务的知识如情境性和条件性知识、自我知识)。
就认知过程维来说,学习者可运用图形组织器来展开各种思维活动,促进各种认知目标层级的实现。如,通过识别(确认)、回忆(提取)的图形组织器工具来促进记忆方面的认知目标实现;通过解释(转换、释义、表征、澄清)、举例(例证、例示)、分类(归类)、总结(概括、抽象)、推断(外推、添加、预测、断定)、比较(对照、匹配、映射)、说明(建构一个模型)的图形组织器工具来促进理解方面的认知目标实现;通过执行(完成)、实施(使用)的图形组织器工具来促进应用方面的认知目标实现;通过区分(辨别、选择、区别、聚焦)、组织(形成结构、整合内容、寻求一致、明确要义、语义分析)、归属(解构)的图形组织器工具来促进分析方面的认知目标实现;通过核查(检验、查明、监控、协调)、评判(判断)的图形组织器工具来促进评价方面的认知目标实现;通过生成(提出假设)、计划(设计)、实施/产出(构建)的图形组织器工具来促进创造方面的认知目标实现,等等。
2.以学习维度发展为选用参照框架
学习维度(Dimensions of Learning, DOL)是美国课程改革专家马扎诺(R. Marzano)提出的一种应用性学习理论。学习维度包括五个维度:维度一是学习者的态度与感受、维度二是获取与整合知识、维度三是扩展与精练知识、维度四是有意义地运用知识、维度五是生产性的思维习惯[15]。在五个维度中,所有的学习都发生于学习者的态度与感受(维度1)以及运用生产性的思维习惯中(维度5),任何学习过程都带有情感和态度特征。另外三个维度则是学习之中进行思考所必需的。在扩展与精练知识时,学习者也在获取与整合知识;在运用知识时,学习者也在扩展知识。思维技能和思维过程并不是互相割裂和线性作用的,而是一个互动循环、彼此影响的过程。学习的五个维度从总体上实现了认知与情感的相互作用,决定着学习的成效。合理地选用图形组织器工具能有效地促进学习者获取与整合知识、扩展与精炼知识和有意义地运用知识。如表3所示。
3.以理性思维发展为选用参照框架
“理性思维”(rational thinking)是美国教育学家坎贝尔(Campbell, 2003)提出的学习能力目标指向[16]。所谓“理性思维”,通常是指深层次理解知识与运用(迁移)知识时的心理活动状态和信息加工方式。学习或教学应当重视发展“理性思维”能力。以坎贝尔提出的20种理性思维的分类和以提问促进理性思维发展的方式为参照,学习者可以有效地选用图形组织器。如表4所示。
4.以日常思维发展为选用参照框架
在日常的学习中,会涉及系列常用的思维活动,这些思维活动的特点与图形组织器存在一种对应的关系。学习者可以运用相应的图形组织器来促进日常思维活动的发展。如表5所示。
六、图形组织器的创建原则
1.目标导向
图形组织器是用来实现一定的认知目标或促进思维能力发展的,否则必将成为一种流于形式的、花里胡哨的装饰,颠倒手段和目标的关系。目标导向将决定图形组织器的形式选择、认知活动展开和图形组织器的应用成效。为此,学习者要明确学习任务和学习目标,理解图形组织器选用的参照框架。
2.相互匹配
任何一种图形组织器都有其特定的形式和功用,学习者面临的学习内容也有其特定性,比如事实性知识和程序性知识学习的差异。为此,学习者要把握图形组织器的类型,理解学习内容的特点,实现图形组织器的形式表现性和学习内容特定性的有机统合。
3.自由开放
图形组织器有一定的类型和表现形式,但不是僵硬固定的。学习者不要拘泥形式,可以根据自己的喜好、学习任务和目标的特点,在基本匹配的基础上,自由选用甚至是创新图形组织器,用于信手涂鸦、头脑风暴,追求最多样化的观点,实现观点的不断增删和图形的不断变化。
4.整体结构
不论选用何种图形组织器,都要高度重视图形所表现的主题、各个要素及其相互联系,使图形化或可视化的对象内容形成一个整体的结构。
5.简洁有效
使用和创建图形组织器的目的是化繁为简、化抽象为具体、化隐性为显性,一目了然,以提高表现力和传播效果,切忌形式重于内容,丧失图形组织器的本原意义。
6.视觉设计
图形组织器是一种视觉信息传播方式,其效果受影响于相关的设计原则。在视觉设计方面,汤普森(M.Thompson,1994)提出了11条基本要义:简洁、清晰、平衡、协调、组织性、重点突出、易辨性、统一性、透视性、观点明确和构架合理。在知识可视化方面,尤德尔曼(G.Judelman,2004)提出了5条基本原则:图形化(重模型而非无结构的信息)、最优化(注重信息表现力以提高认知效率)、稳定性(注意信息表现和操作的情境)、适应性(注重图形界面和应用的聚合性)、数字化(以数字化方式来处理复杂性)[17]。这些原则对于使用和创建图形组织器来说都富有启示和指导意义。
此外,在创建图形组织器时离不开创建工具。一般说来,创建图形组织器的工具主要分为两种,徒手绘制和数字化方式。徒手绘制的特点是设备简单、不受场所限制、使用比较灵活和适宜表现瞬间的灵感,但作品较随意,不易改动和转移。
数字化的方式就是使用计算机技术,其特点是易于修改、动态链接、转换方便、简洁美观、易于储存、交换和传播,等等。一般来说,平常的办公软件如Office、Wps自带的绘图工具就可以用于创建图形组织器,满足基本要求。但这种附带的绘图工具在图形模板、色彩等方面可选择性小,对学习者的构图能力要求比较高,创建复杂图形比较费时,也不适合表达复杂信息或思维的要求。因此,学习者可以选用专门的图形组织器创建工具主要有Inspiration, Mind Manager, Mind Mapper, Brain, Axon Idea Processor, Cmap, Decision Explorer, Kmap, SemNet, Research Group, CoCo Systems, Activity Map, TextVision / TekstNet, SMART Ideas, EGLE Magic等等。这些软件提供了丰富的图形模板,界面友好,操作简单,功能多样,而且菜单设置、编辑功能等都大同小异,只是对于图形的绘制有所侧重。学习者只要学会一到两种这类软件,就可以触类旁通。
[参考文献]
[1]Tracey Hall & Nicole. Strangman.Graphic Organizers :A Report Prepared by for the National Center on Accessing the General Curriculum at CAST.[EB/OL].https://www.省略/publications/ncac/ncac_go.html 2009-01-12.
[2][6]Aziz Bin Mohamed Amin.Using Graphic Organizers[J]. ITE TEACHERS’ CONFERENCE 2004 Reflective Practitioners In Action Singapore.2004.10.1.sg/ite_conf/e_tech/tc04et02.pdf
[3]Definition of Graphic organizer.[EB/OL]. https://dictionary.省略/graphic%20organizer 2009-07-10.
[4]what are they. [EB/OL]..ca/priscillatheroux/graphicorganizers.html 2007-09-1.
[5]Graphic Organizers. [EB/OL] .https://www.省略/graphicorganizers/ 2008-06-5.
[7]Jamie McKenzie .Graphical Organizers as Thinking Technology. [EB/OL] .省略/oct97/picture.html 2007-08-7.
[8]Why Graphical Organizers? [EB/OL] .省略/oct97/picture.html;Increasing Understanding by Creating Graphic Organizers,[EB/OL] .https://www.省略/graphicorganizers/star/,2008-08-1.
[9]How and Why Graphic Organizers Work. [EB/OL] .https://www.省略/procts/usareads_info.htm,2008-09-12.
[10]Judy Willis Research-Based Strategies to Ignite Student Learning:Insights from a Neurologist and Classroom Teacher[M]. Association for Supervision & Curriculum Deve 2006.
[11]Wormeli, R. Summarization in Any Subject : 50 Techniques to Improve Student Learning[M]. Alexandria, VA: ASCD 2005.
[12]邱婷,知识可视化作为学习工具的应用研究[D],江西师范大学课程与教学研究所,2006:9-14.
[13]Graphic Organizers. [EB/OL]. https://www.省略/organizers/ 2009-09-1.
[14]钟志贤,大学教学模式革新: 教学设计 视域[M].北京:教育科学出版社,2007:151-152.
[15]MCREL. What is Dimensions of Learning and How is it Used? [EB/OL] . /whathow.asp,2006-11-10.
[16]CAMPBELL L. Mindful Learning:101 Proven Strategies for Student and Teacher Success[M]. Thousand Oaks, CA: Gorwin Press,Inc, 2003: 77, 64-65.
[17]Gregory Brian Judelman(2004).Knowledge Visualization:Problems and Principles for Mapping the Knowledge Space.[EB/OL]. https://www.省略/media/judelmanThesis2004.pdf,2009-08-20.省略);钟志贤,博士,教授,江西师范大学课程与教学研究所所长,主要从事教育技术学、课程与教学论研究。
On Graphic Organizers
Qiu TingZhong Zhixian
(Institute of Curriculum and Instruction, Jiangxi Normal University,Jiangxi Nanchang 330027)
【Abstract】 Graphic Organizers can be used as a powerful visualized learning tool, be controlled freely by the learner. This paper discusses the meaning, functions, theoretical foundations, types, some frameworks for selection and application(FSA) and some principles of creating graphic organizers, in an attempt to get the basic knowledge about the graphic organizer.
【Keywords】 Graphic organizers; Functions; Types; FSA; Principles of creation
本文责编:孙爱萍
❸ 机器学习的常用方法有哪些
梯度下降是非常常用的优化算法。作为机器学习的基础知识,这是一个必须要掌握的算法。借助本文,让我们来一起详细了解一下这个算法。
前言
本文的代码可以到我的Github上获取:
https://github.com/paulQuei/gradient_descent
本文的算法示例通过Python语言实现,在实现中使用到了numpy和matplotlib。如果你不熟悉这两个工具,请自行在网上搜索教程。
关于优化
大多数学习算法都涉及某种形式的优化。优化指的是改变x以最小化或者最大化某个函数的任务。
我们通常以最小化指代大多数最优化问题。最大化可经由最小化来实现。
我们把要最小化或最大化的函数成为目标函数(objective function)或准则(criterion)。
我们通常使用一个上标*表示最小化或最大化函数的x值,记做这样:
[x^* = arg; min; f(x)]
优化本身是一个非常大的话题。如果有兴趣,可以通过《数值优化》和《运筹学》的书籍进行学习。
模型与假设函数
所有的模型都是错误的,但其中有些是有用的。– George Edward Pelham Box
模型是我们对要分析的数据的一种假设,它是为解决某个具体问题从老洞数据中学习到的,因此它是机器学习最核心的概念。
针对一个问题,通常有大量的模型可以选择。
本文不会深入讨论这方面的内容,关于各种模型请参阅机器学习的相关书籍。本文仅以最简单的线性模型为基础来讨论梯度下降算法。
这里我们先介绍一下在监督学习(supervised learning)中常见的三个符号:
m,描述训练样本的数量
x,描述输入变量或特征
y,描述输出变量或者叫目标值
训练集会包含很多的样本,我们用 表示其中第i个样本。
x是数据样本的特征,y是其目标值。例如,在预测房价的模型中,x是房子的各种信息,例如:面积,楼层,位置等等,y是房子的价格。在图像识别的任务中,x是图形的所有像素点数据,y是图像中包含的目标对象。
我们是希望寻找一个函数,将x映射到y,这个函数要足够的好,以至于能够预测对应的y。由于历史原因,这个函数叫做假设函数(hypothesis function)。
学习的过程如下图所示。即:首先根据已有的数据(称之为训练集)训练我们的算法模型,然后根据模型的假设函数来进行新数据的预测。
线性模型(linear model)正如其名称那样:是希望通过一个直线的形式来描述模式。线性模型的假设函数如下所示:
[h_{ heta}(x) = heta_{0} + heta_{1} * x]
这个公式对于大家来说应该都是非常简单的。如果把它绘制出来,其实就是一条直线。
下图是一个具体的例子,即: 的图形:
在实际的机器学习工程中碰含伍,你会拥有大量的数据。这些数据会来自于某个数据源。它们存储在csv文件中,或者以其他的形式打包。
但是本文作为演示使用,我们通过一些简单的代码自动生成了需要的数据。为了便于计算,演示的数据量也很小。
import numpy as np
max_x = 10
data_size = 10
theta_0 = 5
theta_1 = 2
def get_data:
x = np.linspace(1, max_x, data_size)
noise = np.random.normal(0, 0.2, len(x))
y = theta_0 + theta_1 * x + noise
return x, y
这段代码很简单,我们生成了x范围是 [1, 10] 整数的10条数据。对应的y是以线性模型的形式计算得到,其函数是:。现实中的数据常常受到各种因素的干扰,所以对于y我们故意加上了一些高斯噪声。因此最终的y值为比原先会有轻微的偏离。
最后我们的数据如下所示:
x = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
y = [6.66, 9.11, 11.08, 12.67, 15.12, 16.76, 18.75, 21.35, 22.77, 24.56]
我们可以把这10条数据绘制出来这样就有一个直观的了解了,如下图所示:
虽然演示用的数据是我们通过公式计算得到的。但在实际的工程中,模型的参数是需要我们通过数据学习到的。所以下文我们假设我们不知道这里线性模式的两个参数是什么,而是通过算法的形式求得。
最后再跟已知的参数进行对比以验证我们的算法是否正确。
有了上面的数据,我们可以尝试画一条直线来描述我们的模型。
例如,像下面这样画一条水平的直线:
很显然,这条水平线离数据太远了,非常的不匹配。
那我们可以再画一条斜线。
我们初次画的斜线可能也不贴切,它可能像下面这样:
最后我们通过不断尝试,找到了最终最合适的那条,如下所示:
梯度下降算法的计算过程,就和这种本能式的试探是类似的,它就是不停的迭代,一步步的接近最终的结果。
代价函数
上面我们尝试了几次通过一条直线来拟合(fitting)已有的数据。
二维平面上的一条直线可以通过两个参数唯一的确定,两个参数的确定也即模型的确定。那如何描述模型与数据的拟合程度呢?答案就是代价函数。
代价函数(cost function)描述了学习到的模型与实际结果的偏差程度。以上面的三幅图为例,最后一幅图中的红线相比第一条水平的绿线,其偏离程度(代价)应该是更小的。
很显然,我们希望我们的假设函数与数据尽可能的贴近,也就是说:希望代价函数的结果尽可能的小。这就涉及到结果的优化,而梯度下降就是寻找最小值的方法之一。
对于每一个样本,假设函数会依据计算出一个估算值,我们常常用来表示。即 。
很自然的,我们会想到,通过下面这个公式来描述我们的模型与实际值的偏差程度:
[(h_ heta(x^i) - y^i)^2 = (widehat{y}^{i} - y^i)^2 = ( heta_{0} + heta_{1} * x^{i} - y^{i})^2]
请注意, 是实际数据的值, 是我们的模型的估算值。前者对应了上图中的离散点的y坐标,后者对应了离散点在直线上投影点的y坐标。
每一条数据都会存在一个偏差值,而代价函数就是对所有样本的偏差求平均值,其计算公式如下所示:
[L( heta) = frac {1}{m} sum_{i=1}^{m}(h_ heta(x^i) - y^i)^2 = frac {1}{m} sum_{i=1}^{m}( heta_{0} + heta_{1} * x^{i} - y^{i})^2]
当损失函数的结果越小,则意味着通过我们的假设函数估算出的结果与真实值越接近。这也就是为什么我们要最小化损失函数的原因。
借助上面这个公式,我们可以写一个函数来实现代价函数:
def cost_function(x, y, t0, t1):
cost_sum = 0
for i in range(len(x)):
cost_item = np.power(t0 + t1 * x[i] - y[i], 2)
cost_sum += cost_item
return cost_sum / len(x)
这个函数的代码应该不用多做解释,它就是根据上面的完成计算。
我们可以尝试选取不同的 和 组合来计算代价函数的值,然后将结果绘制出来:
import numpy as np
import matplotlib.pyplot as plt
from matplotlib import cm
from mpl_toolkits.mplot3d import Axes3D
theta_0 = 5
theta_1 = 2
def draw_cost(x, y):
fig = plt.figure(figsize=(10, 8))
ax = fig.gca(projection='3d')
scatter_count = 100
radius = 1
t0_range = np.linspace(theta_0 - radius, theta_0 + radius, scatter_count)
t1_range = np.linspace(theta_1 - radius, theta_1 + radius, scatter_count)
cost = np.zeros((len(t0_range), len(t1_range)))
for a in range(len(t0_range)):
for b in range(len(t1_range)):
cost[a][b] = cost_function(x, y, t0_range[a], t1_range[b])
t0, t1 = np.meshgrid(t0_range, t1_range)
ax.set_xlabel('theta_0')
ax.set_ylabel('theta_1')
ax.plot_surface(t0, t1, cost, cmap=cm.hsv)
在这段代码中,我们对 和 各自指定了一个范围进行100次的采样,然后以不同的 组合对来计算代价函数的值。
如果我们将所有点的代价函数值绘制出来,其结果如下图所示:
从这个图形中我们可以看出,当 越接近 [5, 2]时其结果(偏差)越小。相反,离得越远,结果越大。
直观解释
从上面这幅图中我们可以看出,代价函数在不同的位置结果大小不同。
从三维的角度来看,这就和地面的高低起伏一样。最高的地方就好像是山顶。
而我们的目标就是:从任意一点作为起点,能够快速寻找到一条路径并以此到达图形最低点(代价值最小)的位置。
而梯度下降的算法过程就和我们从山顶想要快速下山的做法是一样的。
在生活中,我们很自然会想到沿着最陡峭的路往下行是下山速度最快的。如下面这幅图所示:
针对这幅图,细心的读者可能很快就会有很多的疑问,例如:
对于一个函数,怎么确定下行的方向?
每一步该往前走多远?
有没有可能停留在半山腰的平台上?
这些问题也就是本文接下来要讨论的内容。
算法描述
梯度下降算法最开始的一点就是需要确定下降的方向,即:梯度。
我们常常用 来表示梯度。
对于一个二维空间的曲线来说,梯度就是其切线的方向。如下图所示:
而对于更高维空间的函数来说,梯度由所有变量的偏导数决定。
其表达式如下所示:
[ abla f({ heta}) = ( frac{partial f({ heta})}{partial heta_1} , frac{partial f({ heta})}{partial heta_2} , ... , frac{partial f({ heta})}{partial heta_n} )]
在机器学习中,我们主要是用梯度下降算法来最小化代价函数,记做:
[ heta ^* = arg min L( heta)]
其中,L是代价函数,是参数。
梯度下降算法的主体逻辑很简单,就是沿着梯度的方向一直下降,直到参数收敛为止。
记做:
[ heta ^{k + 1}_i = heta^{k}_i - lambda abla f( heta^{k})]
这里有几点需要说明:
收敛是指函数的变化率很小。具体选择多少合适需要根据具体的项目来确定。在演示项目中我们可以选择0.01或者0.001这样的值。不同的值将影响算法的迭代次数,因为在梯度下降的最后,我们会越来越接近平坦的地方,这个时候函数的变化率也越来越小。如果选择一个很小的值,将可能导致算法迭代次数暴增。
公式中的 称作步长,也称作学习率(learning rate)。它决定了每一步往前走多远,关于这个值我们会在下文中详细讲解。你可以暂时人为它是一个类似0.01或0.001的固定值。
在具体的项目,我们不会让算法无休止的运行下去,所以通常会设置一个迭代次数的最大上限。
线性回归的梯度下降
有了上面的知识,我们可以回到线性模型代价函数的梯度下降算法实现了。
首先,根据代价函数我们可以得到梯度向量如下:
[ abla f({ heta}) = (frac{partial L( heta)}{ partial heta_{0}}, frac{ partial L( heta)}{ partial heta_{1}}) = (frac {2}{m} sum_{i=1}^{m}( heta_{0} + heta_{1} * x^{i} - y^{i}) , frac {2}{m} sum_{i=1}^{m}( heta_{0} + heta_{1} * x^{i} - y^{i}) x^{i})]
接着,将每个偏导数带入迭代的公式中,得到:
[ heta_{0} := heta_{0} - lambda frac{partial L( heta_{0})}{ partial heta_{0}} = heta_{0} - frac {2 lambda }{m} sum_{i=1}^{m}( heta_{0} + heta_{1} * x^{i} - y^{i}) heta_{1} := heta_{1} - lambda frac{partial L( heta_{1})}{ partial heta_{1}} = heta_{1} - frac {2 lambda }{m} sum_{i=1}^{m}( heta_{0} + heta_{1} * x^{i} - y^{i}) x^{i}]
由此就可以通过代码实现我们的梯度下降算法了,算法逻辑并不复杂:
learning_rate = 0.01
def gradient_descent(x, y):
t0 = 10
t1 = 10
delta = 0.001
for times in range(1000):
sum1 = 0
sum2 = 0
for i in range(len(x)):
sum1 += (t0 + t1 * x[i] - y[i])
sum2 += (t0 + t1 * x[i] - y[i]) * x[i]
t0_ = t0 - 2 * learning_rate * sum1 / len(x)
t1_ = t1 - 2 * learning_rate * sum2 / len(x)
print('Times: {}, gradient: [{}, {}]'.format(times, t0_, t1_))
if (abs(t0 - t0_) < delta and abs(t1 - t1_) < delta):
print('Gradient descent finish')
return t0_, t1_
t0 = t0_
t1 = t1_
print('Gradient descent too many times')
return t0, t1
这段代码说明如下:
我们随机选择了 都为10作为起点
设置最多迭代1000次
收敛的范围设为0.001
学习步长设为0.01
如果我们将算法迭代过程中求得的线性模式绘制出来,可以得到下面这幅动态图:
最后算法得到的结果如下:
Times: 657, gradient: [5.196562662718697, 1.952931052920264]
Times: 658, gradient: [5.195558390180733, 1.9530753071808193]
Times: 659, gradient: [5.194558335124868, 1.9532189556399233]
Times: 660, gradient: [5.193562479839619, 1.9533620008416623]
Gradient descent finish
从输出中可以看出,算法迭代了660次就收敛了。这时的结果[5.193562479839619, 1.9533620008416623],这已经比较接近目标值 [5, 2]了。如果需要更高的精度,可以将delta的值调的更小,当然,此时会需要更多的迭代次数。
高维扩展
虽然我们举的例子是二维的,但是对于更高维的情况也是类似的。同样是根据迭代的公式进行运算即可:
[ heta_{i} = heta_{i} - lambda frac {partial L( heta)}{partial heta_i} = heta_{i} - frac{2lambda}{m} sum_{i=1}^{m}(h_ heta(x^{k})-y^k)x_i^k]
这里的下标i表示第i个参数,上标k表示第k个数据。
梯度下降家族BGD
在上面的内容中我们看到,算法的每一次迭代都需要把所有样本进行遍历处理。这种做法称为之Batch Gradient Descent,简称BGD。作为演示示例只有10条数据,这是没有问题的。
但在实际的项目中,数据集的数量可能是几百万几千万条,这时候每一步迭代的计算量就会非常的大了。
于是就有了下面两个变种。
SGD
Stochastic Gradient Descent,简称SGD,这种算法是每次从样本集中仅仅选择一个样本来进行计算。很显然,这样做算法在每一步的计算量一下就少了很多。
其算法公式如下:
[ heta_{i} = heta_{i} - lambda frac {partial L( heta)}{partial heta_i} = heta_{i} - lambda(h_ heta(x^k)-y^k)x_i^k]
当然,减少算法计算量也是有代价的,那就是:算法结果会强依赖于随机取到的数据情况,这可能会导致算法的最终结果不太令人满意。
MBGD
以上两种做法其实是两个极端,一个是每次用到了所有数据,另一个是每次只用一个数据。
我们自然就会想到两者取其中的方法:每次选择一小部分数据进行迭代。这样既避免了数据集过大导致每次迭代计算量过大的问题,也避免了单个数据对算法的影响。
这种算法称之为Mini-batch Gradient Descent,简称MBGD。
其算法公式如下:
[ heta_{i} = heta_{i} - lambda frac {partial L( heta)}{partial heta_i} = heta_{i} - frac{2lambda}{m} sum_{i=a}^{a + b}(h_ heta(x^k)-y^k)x_i^k]
当然,我们可以认为SGD是Mini-batch为1的特例。
针对上面提到的算法变种,该如何选择呢?
下面是Andrew Ng给出的建议:
如果样本数量较小(例如小于等于2000),选择BGD即可。
如果样本数量很大,选择 来进行MBGD,例如:64,128,256,512。
下表是 Optimization for Deep Learning 中对三种算法的对比
方法准确性更新速度内存占用在线学习BGD好慢高否SGD好(with annealing)快低是MBGD好中等中等是
算法优化
式7是算法的基本形式,在这个基础上有很多人进行了更多的研究。接下来我们介绍几种梯度下降算法的优化方法。
Momentum
Momentum是动量的意思。这个算法的思想就是借助了动力学的模型:每次算法的迭代会使用到上一次的速度作为依据。
算法的公式如下:
[v^t = gamma v^{t - 1} + lambda abla f( heta) heta = heta - v_t]
对比式7可以看出,这个算法的主要区别就是引入了,并且,每个时刻的受前一个时刻的影响。
从形式上看,动量算法引入了变量 v 充当速度角色——它代表参数在参数空间移动的方向和速率。速度被设为负梯度的指数衰减平均。名称动量来自物理类比,根据牛顿运动定律,负梯度是移动参数空间中粒子的力。动量在物理学上定义为质量乘以速度。在动量学习算法中,我们假设是单位质量,因此速度向量 v 也可以看作是粒子的动量。
对于可以取值0,而是一个常量,设为0.9是一个比较好的选择。
下图是momentum算法的效果对比:
对原来的算法稍加修改就可以增加动量效果:
def gradient_descent_with_momentum(x, y):
t0 = 10
t1 = 10
delta = 0.001
v0 = 0
v1 = 0
gamma = 0.9
for times in range(1000):
sum1 = 0
sum2 = 0
for i in range(len(x)):
sum1 += (t0 + t1 * x[i] - y[i])
sum2 += (t0 + t1 * x[i] - y[i]) * x[i]
v0 = gamma * v0 + 2 * learning_rate * sum1 / len(x)
v1 = gamma * v1 + 2 * learning_rate * sum2 / len(x)
t0_ = t0 - v0
t1_ = t1 - v1
print('Times: {}, gradient: [{}, {}]'.format(times, t0_, t1_))
if (abs(t0 - t0_) < delta and abs(t1 - t1_) < delta):
print('Gradient descent finish')
return t0_, t1_
t0 = t0_
t1 = t1_
print('Gradient descent too many times')
return t0, t1
以下是该算法的输出:
Times: 125, gradient: [4.955453758569991, 2.000005017897775]
Times: 126, gradient: [4.955309381126545, 1.9956928964532015]
Times: 127, gradient: [4.9542964317327005, 1.9855674828684156]
Times: 128, gradient: [4.9536358220657, 1.9781180992510465]
Times: 129, gradient: [4.95412496254411, 1.9788858350530971]
Gradient descent finish
从结果可以看出,改进的算法只用了129次迭代就收敛了。速度比原来660次快了很多。
同样的,我们可以把算法计算的过程做成动态图:
对比原始的算法过程可以看出,改进算法最大的区别是:在寻找目标值时会在最终结果上下跳动,但是越往后跳动的幅度越小,这也就是动量所产生的效果。
Learning Rate 优化
至此,你可能还是好奇该如何设定学习率的值。
事实上,这个值的选取需要一定的经验或者反复尝试才能确定。
关键在于,这个值的选取不能过大也不能过小。
如果这个值过小,会导致每一次迭代的步长很小,其结果就是算法需要迭代非常多的次数。
那么,如果这个值过大会怎么样呢?其结果就是:算法可能在结果的周围来回震荡,却落不到目标的点上。下面这幅图描述了这个现象:
事实上,学习率的取值未必一定要是一个常数,关于这个值的设定有很多的研究。
下面是比较常见的一些改进算法。
AdaGrad
AdaGrad是Adaptive Gradient的简写,该算法会为每个参数设定不同的学习率。它使用历史梯度的平方和作为基础来进行计算。
其算法公式如下:
[ heta_i = heta_i - frac{lambda}{sqrt{G_t + epsilon}} abla f( heta)]
对比式7,这里的改动就在于分号下面的根号。
根号中有两个符号,第二个符号比较好理解,它就是为了避免除0而人为引入的一个很小的常数,例如可以设为:0.001。
第一个符号的表达式展开如下:
[G_t = sum_{i = 1}^{t} abla f( heta){i} abla f( heta){i}^{T}]
这个值其实是历史中每次梯度的平方的累加和。
AdaGrad算法能够在训练中自动的对learning rate进行调整,对于出现频率较低参数采用较大的学习率;相反,对于出现频率较高的参数采用较小的学习率。因此,Adagrad非常适合处理稀疏数据。
但该算法的缺点是它可能导致学习率非常小以至于算法收敛非常的慢。
关于这个算法的直观解释可以看李宏毅教授的视频课程:ML Lecture 3-1: Gradient Descent。
RMSProp
RMS是Root Mean Square的简写。RMSProp是AI教父Geoff Hinton提出的一种自适应学习率方法。AdaGrad会累加之前所有的梯度平方,而RMSProp仅仅是计算对应的平均值,因此可缓解Adagrad算法学习率下降较快的问题。
该算法的公式如下:
[E[ abla f( heta_{i})^2]^{t} = gamma E[ abla f( heta_{i})^2]^{t - 1} + (1-gamma)( abla f( heta_{i})^{t})^{2} heta_i = heta_i - frac{lambda}{sqrt{E[g^2]^{t+1} + epsilon}} abla f( heta_{i})]
类似的,是为了避免除0而引入。 是衰退参数,通常设为0.9。
这里的 是t时刻梯度平方的平均值。
Adam
Adam是Adaptive Moment Estimation的简写。它利用梯度的一阶矩估计和二阶矩估计动态调整每个参数的学习率。
Adam的优点主要在于经过偏置校正后,每一次迭代学习率都有个确定范围,使得参数比较平稳。
该算法公式如下:
[m^{t} = eta_{1} m^{t-1} + (1-eta_{1}) abla f( heta) v^{t} = eta_{2} v^{t-1} + (1-eta_{2}) abla f( heta)^2 widehat{m}^{t} = frac{m^{t}}{1 - eta^{t}_1} widehat{v}^{t} = frac{v^{t}}{1 - eta^{t}_2} heta = heta - frac{lambda}{sqrt{widehat{v}^{t}} + epsilon}widehat{m}^{t}]
,分别是对梯度的一阶矩估计和二阶矩估计。, 是对,的校正,这样可以近似为对期望的无偏估计。
Adam算法的提出者建议 默认值为0.9,默认值为0.999,默认值为 。
在实际应用中 ,Adam较为常用,它可以比较快地得到一个预估结果。
优化小结
这里我们列举了几种优化算法。它们很难说哪种最好,不同的算法适合于不同的场景。在实际的工程中,可能需要逐个尝试一下才能确定选择哪一个,这个过程也是目前现阶段AI项目要经历的工序之一。
实际上,该方面的研究远不止于此,如果有兴趣,可以继续阅读 《Sebastian Ruder: An overview of gradient descent optimization algorithms》 这篇论文或者 Optimization for Deep Learning 这个Slides进行更多的研究。
由于篇幅所限,这里不再继续展开了。
算法限制
梯度下降算法存在一定的限制。首先,它要求函数必须是可微分的,对于不可微的函数,无法使用这种方法。
除此之外,在某些情况下,使用梯度下降算法在接近极值点的时候可能收敛速度很慢,或者产生Z字形的震荡。这一点需要通过调整学习率来回避。
另外,梯度下降还会遇到下面两类问题。
局部最小值
局部最小值(Local Minima)指的是,我们找到的最小值仅仅是一个区域内的最小值,而并非全局的。由于算法的起点是随意取的,以下面这个图形为例,我们很容易落到局部最小值的点里面。
这就是好像你从上顶往下走,你第一次走到的平台未必是山脚,它有可能只是半山腰的一个平台的而已。
算法的起点决定了算法收敛的速度以及是否会落到局部最小值上。
坏消息是,目前似乎没有特别好的方法来确定选取那个点作为起点是比较好的,这就有一点看运气的成分了。多次尝试不同的随机点或许是一个比较好的方法,这也就是为什么做算法的优化这项工作是特别消耗时间的了。
但好消息是:
对于凸函数或者凹函数来说,不存在局部极值的问题。其局部极值一定是全局极值。
最近的一些研究表明,某些局部极值并没有想象中的那么糟糕,它们已经非常的接近全局极值所带来的结果了。
鞍点
除了Local Minima,在梯度下降的过程中,还有可能遇到另外一种情况,即:鞍点(Saddle Point)。鞍点指的是我们找到点某个点确实是梯度为0,但它却不是函数的极值,它的周围既有比它小的值,也有比它大的值。这就好像马鞍一样。
如下图所示:
多类随机函数表现出以下性质:在低维空间中,局部极值很普遍。但在高维空间中,局部极值比较少见,而鞍点则很常见。
不过对于鞍点,可以通过数学方法Hessian矩阵来确定。关于这点,这里就不再展开了,有兴趣的读者可以以这里提供的几个链接继续探索。
参考资料与推荐读物
Wikipeida: Gradient descent
Sebastian Ruder: An overview of gradient descent optimization algorithms
吴恩达:机器学习
吴恩达:深度学习
Peter Flach:机器学习
李宏毅 - ML Lecture 3-1: Gradient Descent
PDF: 李宏毅 - Gradient Descent
Intro to optimization in deep learning: Gradient Descent
Intro to optimization in deep learning: Momentum, RMSProp and Adam
Stochastic Gradient Descent – Mini-batch and more
刘建平Pinard - 梯度下降(Gradient Descent)小结
多元函数的偏导数、方向导数、梯度以及微分之间的关系思考
[Machine Learning] 梯度下降法的三种形式BGD、SGD以及MBGD
❹ 根号a-+5的最小值和a的值
梯度下降是非常常用的优化算法。作为机器学习的基础知识,这是一个必须要掌握的算法。借助本文,让我们来一起详细了解一下这个算法。
前言
本文的代码可以到我的Github上获取:
https://github.com/paulQuei/gradient_descent
本文的算法示例通过Python语言实现,在实现中使用到了numpy和matplotlib。如果你不熟悉这两个工具,请自行在网上搜索教程。
关于优化
大多数学习算法都涉及某种形式的优化。优化指的是改变x以最小化或者最大化某个函数的任务。
我们通常以最小化指代大多数最优化问题。最大化可经由最小化来实现。
我们把要最小化或最大化的函数成为目标函数(objective function)或准则(criterion)。
我们通常使用一个上标*表示最小化或最大化函数的x值,记做这样:
[x^* = arg; min; f(x)]
优化本身是一个非常大的话题。如果有兴趣,可以通过《数值优化》和《运筹学》的书籍进行学习。
模型与假设函数
所有的模型都是错误的,但其中有些是有用的。– George Edward Pelham Box
模型是我们对要分析的数据的一种假设,它是为解决某个具体问题从数据中学习到的,因此它是机器学习最核心的概念。
针对一个问题,通常有大量的模型可以选择。
本文不会深入讨论这方面的内容,关于各种模型请参阅机器学习的相关书籍。本文仅以最简单的线性模型为基础来讨论梯度下降算法。
这里我们先介绍一下在监督学习(supervised learning)中常见的三个符号:
m,描述训练样本的数量
x,描述输入变量或特征
y,描述输出变量或者叫目标值
训练集会包含很多的样本,我们用 表示其中第i个样本。
x是数据样本的特征,y是其目标值。例如,在预测房价的模型中,x是房子的各种信息,例如:面积,楼层,位置等等,y是房子的价格。在图像识别的任务中,x是图形的所有像素点数据,y是图像中包含的目标对象。
我们是希望寻找一个函数,将x映射到y,这个函数要足够的好,以至于能够预测对应的y。由于历史原因,这个函数叫做假设函数(hypothesis function)。
学习的过程如下图所示。即:首先根据已有的数据(称之为训练集)训练我们的算法模型,然后根据模型的假设函数来进行新数据的预测。
线性模型(linear model)正如其名称那样:是希望通过一个直线的形式来描述模式。线性模型的假设函数如下所示:
[h_{ heta}(x) = heta_{0} + heta_{1} * x]
这个公式对于大家来说应该都是非常简单的。如果把它绘制出来,其实就是一条直线。
下图是一个具体的例子,即: 的图形:
在实际的机器学习工程中,你会拥有大量的数据。这些数据会来自于某个数据源。它们存储在csv文件中,或者以其他的形式打包。
但是本文作为演示使用,我们通过一些简单的代码自动生成了需要的数据。为了便于计算,演示的数据量也很小。
import numpy as np
max_x = 10
data_size = 10
theta_0 = 5
theta_1 = 2
def get_data:
x = np.linspace(1, max_x, data_size)
noise = np.random.normal(0, 0.2, len(x))
y = theta_0 + theta_1 * x + noise
return x, y
这段代码很简单,我们生成了x范围是 [1, 10] 整数的10条数据。对应的y是以线性模型的形式计算得到,其函数是:。现实中的数据常常受到各种因素的干扰,所以对于y我们故意加上了一些高斯噪声。因此最终的y值为比原先会有轻微的偏离。
最后我们的数据如下所示:
x = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
y = [6.66, 9.11, 11.08, 12.67, 15.12, 16.76, 18.75, 21.35, 22.77, 24.56]
我们可以把这10条数据绘制出来这样就有一个直观的了解了,如下图所示:
虽然演示用的数据是我们通过公式计算得到的。但在实际的工程中,模型的参数是需要我们通过数据学习到的。所以下文我们假设我们不知道这里线性模式的两个参数是什么,而是通过算法的形式求得。
最后再跟已知的参数进行对比以验证我们的算法是否正确。
有了上面的数据,我们可以尝试画一条直线来描述我们的模型。
例如,像下面这样画一条水平的直线:
很显然,这条水平线离数据太远了,非常的不匹配。
那我们可以再画一条斜线。
我们初次画的斜线可能也不贴切,它可能像下面这样:
最后我们通过不断尝试,找到了最终最合适的那条,如下所示:
梯度下降算法的计算过程,就和这种本能式的试探是类似的,它就是不停的迭代,一步步的接近最终的结果。
代价函数
上面我们尝试了几次通过一条直线来拟合(fitting)已有的数据。
二维平面上的一条直线可以通过两个参数唯一的确定,两个参数的确定也即模型的确定。那如何描述模型与数据的拟合程度呢?答案就是代价函数。
代价函数(cost function)描述了学习到的模型与实际结果的偏差程度。以上面的三幅图为例,最后一幅图中的红线相比第一条水平的绿线,其偏离程度(代价)应该是更小的。
很显然,我们希望我们的假设函数与数据尽可能的贴近,也就是说:希望代价函数的结果尽可能的小。这就涉及到结果的优化,而梯度下降就是寻找最小值的方法之一。
对于每一个样本,假设函数会依据计算出一个估算值,我们常常用来表示。即 。
很自然的,我们会想到,通过下面这个公式来描述我们的模型与实际值的偏差程度:
[(h_ heta(x^i) - y^i)^2 = (widehat{y}^{i} - y^i)^2 = ( heta_{0} + heta_{1} * x^{i} - y^{i})^2]
请注意, 是实际数据的值, 是我们的模型的估算值。前者对应了上图中的离散点的y坐标,后者对应了离散点在直线上投影点的y坐标。
每一条数据都会存在一个偏差值,而代价函数就是对所有样本的偏差求平均值,其计算公式如下所示:
[L( heta) = frac {1}{m} sum_{i=1}^{m}(h_ heta(x^i) - y^i)^2 = frac {1}{m} sum_{i=1}^{m}( heta_{0} + heta_{1} * x^{i} - y^{i})^2]
当损失函数的结果越小,则意味着通过我们的假设函数估算出的结果与真实值越接近。这也就是为什么我们要最小化损失函数的原因。
借助上面这个公式,我们可以写一个函数来实现代价函数:
def cost_function(x, y, t0, t1):
cost_sum = 0
for i in range(len(x)):
cost_item = np.power(t0 + t1 * x[i] - y[i], 2)
cost_sum += cost_item
return cost_sum / len(x)
这个函数的代码应该不用多做解释,它就是根据上面的完成计算。
我们可以尝试选取不同的 和 组合来计算代价函数的值,然后将结果绘制出来:
import numpy as np
import matplotlib.pyplot as plt
from matplotlib import cm
from mpl_toolkits.mplot3d import Axes3D
theta_0 = 5
theta_1 = 2
def draw_cost(x, y):
fig = plt.figure(figsize=(10, 8))
ax = fig.gca(projection='3d')
scatter_count = 100
radius = 1
t0_range = np.linspace(theta_0 - radius, theta_0 + radius, scatter_count)
t1_range = np.linspace(theta_1 - radius, theta_1 + radius, scatter_count)
cost = np.zeros((len(t0_range), len(t1_range)))
for a in range(len(t0_range)):
for b in range(len(t1_range)):
cost[a][b] = cost_function(x, y, t0_range[a], t1_range[b])
t0, t1 = np.meshgrid(t0_range, t1_range)
ax.set_xlabel('theta_0')
ax.set_ylabel('theta_1')
ax.plot_surface(t0, t1, cost, cmap=cm.hsv)
在这段代码中,我们对 和 各自指定了一个范围进行100次的采样,然后以不同的 组合对来计算代价函数的值。
如果我们将所有点的代价函数值绘制出来,其结果如下图所示:
从这个图形中我们可以看出,当 越接近 [5, 2]时其结果(偏差)越小。相反,离得越远,结果越大。
直观解释
从上面这幅图中我们可以看出,代价函数在不同的位置结果大小不同。
从三维的角度来看,这就和地面的高低起伏一样。最高的地方就好像是山顶。
而我们的目标就是:从任意一点作为起点,能够快速寻找到一条路径并以此到达图形最低点(代价值最小)的位置。
而梯度下降的算法过程就和我们从山顶想要快速下山的做法是一样的。
在生活中,我们很自然会想到沿着最陡峭的路往下行是下山速度最快的。如下面这幅图所示:
针对这幅图,细心的读者可能很快就会有很多的疑问,例如:
对于一个函数,怎么确定下行的方向?
每一步该往前走多远?
有没有可能停留在半山腰的平台上?
这些问题也就是本文接下来要讨论的内容。
算法描述
梯度下降算法最开始的一点就是需要确定下降的方向,即:梯度。
我们常常用 来表示梯度。
对于一个二维空间的曲线来说,梯度就是其切线的方向。如下图所示:
而对于更高维空间的函数来说,梯度由所有变量的偏导数决定。
其表达式如下所示:
[ abla f({ heta}) = ( frac{partial f({ heta})}{partial heta_1} , frac{partial f({ heta})}{partial heta_2} , ... , frac{partial f({ heta})}{partial heta_n} )]
在机器学习中,我们主要是用梯度下降算法来最小化代价函数,记做:
[ heta ^* = arg min L( heta)]
其中,L是代价函数,是参数。
梯度下降算法的主体逻辑很简单,就是沿着梯度的方向一直下降,直到参数收敛为止。
记做:
[ heta ^{k + 1}_i = heta^{k}_i - lambda abla f( heta^{k})]
这里有几点需要说明:
收敛是指函数的变化率很小。具体选择多少合适需要根据具体的项目来确定。在演示项目中我们可以选择0.01或者0.001这样的值。不同的值将影响算法的迭代次数,因为在梯度下降的最后,我们会越来越接近平坦的地方,这个时候函数的变化率也越来越小。如果选择一个很小的值,将可能导致算法迭代次数暴增。
公式中的 称作步长,也称作学习率(learning rate)。它决定了每一步往前走多远,关于这个值我们会在下文中详细讲解。你可以暂时人为它是一个类似0.01或0.001的固定值。
在具体的项目,我们不会让算法无休止的运行下去,所以通常会设置一个迭代次数的最大上限。
线性回归的梯度下降
有了上面的知识,我们可以回到线性模型代价函数的梯度下降算法实现了。
首先,根据代价函数我们可以得到梯度向量如下:
[ abla f({ heta}) = (frac{partial L( heta)}{ partial heta_{0}}, frac{ partial L( heta)}{ partial heta_{1}}) = (frac {2}{m} sum_{i=1}^{m}( heta_{0} + heta_{1} * x^{i} - y^{i}) , frac {2}{m} sum_{i=1}^{m}( heta_{0} + heta_{1} * x^{i} - y^{i}) x^{i})]
接着,将每个偏导数带入迭代的公式中,得到:
[ heta_{0} := heta_{0} - lambda frac{partial L( heta_{0})}{ partial heta_{0}} = heta_{0} - frac {2 lambda }{m} sum_{i=1}^{m}( heta_{0} + heta_{1} * x^{i} - y^{i}) heta_{1} := heta_{1} - lambda frac{partial L( heta_{1})}{ partial heta_{1}} = heta_{1} - frac {2 lambda }{m} sum_{i=1}^{m}( heta_{0} + heta_{1} * x^{i} - y^{i}) x^{i}]
由此就可以通过代码实现我们的梯度下降算法了,算法逻辑并不复杂:
learning_rate = 0.01
def gradient_descent(x, y):
t0 = 10
t1 = 10
delta = 0.001
for times in range(1000):
sum1 = 0
sum2 = 0
for i in range(len(x)):
sum1 += (t0 + t1 * x[i] - y[i])
sum2 += (t0 + t1 * x[i] - y[i]) * x[i]
t0_ = t0 - 2 * learning_rate * sum1 / len(x)
t1_ = t1 - 2 * learning_rate * sum2 / len(x)
print('Times: {}, gradient: [{}, {}]'.format(times, t0_, t1_))
if (abs(t0 - t0_) < delta and abs(t1 - t1_) < delta):
print('Gradient descent finish')
return t0_, t1_
t0 = t0_
t1 = t1_
print('Gradient descent too many times')
return t0, t1
这段代码说明如下:
我们随机选择了 都为10作为起点
设置最多迭代1000次
收敛的范围设为0.001
学习步长设为0.01
如果我们将算法迭代过程中求得的线性模式绘制出来,可以得到下面这幅动态图:
最后算法得到的结果如下:
Times: 657, gradient: [5.196562662718697, 1.952931052920264]
Times: 658, gradient: [5.195558390180733, 1.9530753071808193]
Times: 659, gradient: [5.194558335124868, 1.9532189556399233]
Times: 660, gradient: [5.193562479839619, 1.9533620008416623]
Gradient descent finish
从输出中可以看出,算法迭代了660次就收敛了。这时的结果[5.193562479839619, 1.9533620008416623],这已经比较接近目标值 [5, 2]了。如果需要更高的精度,可以将delta的值调的更小,当然,此时会需要更多的迭代次数。
高维扩展
虽然我们举的例子是二维的,但是对于更高维的情况也是类似的。同样是根据迭代的公式进行运算即可:
[ heta_{i} = heta_{i} - lambda frac {partial L( heta)}{partial heta_i} = heta_{i} - frac{2lambda}{m} sum_{i=1}^{m}(h_ heta(x^{k})-y^k)x_i^k]
这里的下标i表示第i个参数,上标k表示第k个数据。
梯度下降家族BGD
在上面的内容中我们看到,算法的每一次迭代都需要把所有样本进行遍历处理。这种做法称为之Batch Gradient Descent,简称BGD。作为演示示例只有10条数据,这是没有问题的。
但在实际的项目中,数据集的数量可能是几百万几千万条,这时候每一步迭代的计算量就会非常的大了。
于是就有了下面两个变种。
SGD
Stochastic Gradient Descent,简称SGD,这种算法是每次从样本集中仅仅选择一个样本来进行计算。很显然,这样做算法在每一步的计算量一下就少了很多。
其算法公式如下:
[ heta_{i} = heta_{i} - lambda frac {partial L( heta)}{partial heta_i} = heta_{i} - lambda(h_ heta(x^k)-y^k)x_i^k]
当然,减少算法计算量也是有代价的,那就是:算法结果会强依赖于随机取到的数据情况,这可能会导致算法的最终结果不太令人满意。
MBGD
以上两种做法其实是两个极端,一个是每次用到了所有数据,另一个是每次只用一个数据。
我们自然就会想到两者取其中的方法:每次选择一小部分数据进行迭代。这样既避免了数据集过大导致每次迭代计算量过大的问题,也避免了单个数据对算法的影响。
这种算法称之为Mini-batch Gradient Descent,简称MBGD。
其算法公式如下:
[ heta_{i} = heta_{i} - lambda frac {partial L( heta)}{partial heta_i} = heta_{i} - frac{2lambda}{m} sum_{i=a}^{a + b}(h_ heta(x^k)-y^k)x_i^k]
当然,我们可以认为SGD是Mini-batch为1的特例。
针对上面提到的算法变种,该如何选择呢?
下面是Andrew Ng给出的建议:
如果样本数量较小(例如小于等于2000),选择BGD即可。
如果样本数量很大,选择 来进行MBGD,例如:64,128,256,512。
下表是 Optimization for Deep Learning 中对三种算法的对比
方法准确性更新速度内存占用在线学习BGD好慢高否SGD好(with annealing)快低是MBGD好中等中等是
算法优化
式7是算法的基本形式,在这个基础上有很多人进行了更多的研究。接下来我们介绍几种梯度下降算法的优化方法。
Momentum
Momentum是动量的意思。这个算法的思想就是借助了动力学的模型:每次算法的迭代会使用到上一次的速度作为依据。
算法的公式如下:
[v^t = gamma v^{t - 1} + lambda abla f( heta) heta = heta - v_t]
对比式7可以看出,这个算法的主要区别就是引入了,并且,每个时刻的受前一个时刻的影响。
从形式上看,动量算法引入了变量 v 充当速度角色——它代表参数在参数空间移动的方向和速率。速度被设为负梯度的指数衰减平均。名称动量来自物理类比,根据牛顿运动定律,负梯度是移动参数空间中粒子的力。动量在物理学上定义为质量乘以速度。在动量学习算法中,我们假设是单位质量,因此速度向量 v 也可以看作是粒子的动量。
对于可以取值0,而是一个常量,设为0.9是一个比较好的选择。
下图是momentum算法的效果对比:
对原来的算法稍加修改就可以增加动量效果:
def gradient_descent_with_momentum(x, y):
t0 = 10
t1 = 10
delta = 0.001
v0 = 0
v1 = 0
gamma = 0.9
for times in range(1000):
sum1 = 0
sum2 = 0
for i in range(len(x)):
sum1 += (t0 + t1 * x[i] - y[i])
sum2 += (t0 + t1 * x[i] - y[i]) * x[i]
v0 = gamma * v0 + 2 * learning_rate * sum1 / len(x)
v1 = gamma * v1 + 2 * learning_rate * sum2 / len(x)
t0_ = t0 - v0
t1_ = t1 - v1
print('Times: {}, gradient: [{}, {}]'.format(times, t0_, t1_))
if (abs(t0 - t0_) < delta and abs(t1 - t1_) < delta):
print('Gradient descent finish')
return t0_, t1_
t0 = t0_
t1 = t1_
print('Gradient descent too many times')
return t0, t1
以下是该算法的输出:
Times: 125, gradient: [4.955453758569991, 2.000005017897775]
Times: 126, gradient: [4.955309381126545, 1.9956928964532015]
Times: 127, gradient: [4.9542964317327005, 1.9855674828684156]
Times: 128, gradient: [4.9536358220657, 1.9781180992510465]
Times: 129, gradient: [4.95412496254411, 1.9788858350530971]
Gradient descent finish
从结果可以看出,改进的算法只用了129次迭代就收敛了。速度比原来660次快了很多。
同样的,我们可以把算法计算的过程做成动态图:
对比原始的算法过程可以看出,改进算法最大的区别是:在寻找目标值时会在最终结果上下跳动,但是越往后跳动的幅度越小,这也就是动量所产生的效果。
Learning Rate 优化
至此,你可能还是好奇该如何设定学习率的值。
事实上,这个值的选取需要一定的经验或者反复尝试才能确定。
关键在于,这个值的选取不能过大也不能过小。
如果这个值过小,会导致每一次迭代的步长很小,其结果就是算法需要迭代非常多的次数。
那么,如果这个值过大会怎么样呢?其结果就是:算法可能在结果的周围来回震荡,却落不到目标的点上。下面这幅图描述了这个现象:
事实上,学习率的取值未必一定要是一个常数,关于这个值的设定有很多的研究。
下面是比较常见的一些改进算法。
AdaGrad
AdaGrad是Adaptive Gradient的简写,该算法会为每个参数设定不同的学习率。它使用历史梯度的平方和作为基础来进行计算。
其算法公式如下:
[ heta_i = heta_i - frac{lambda}{sqrt{G_t + epsilon}} abla f( heta)]
对比式7,这里的改动就在于分号下面的根号。
根号中有两个符号,第二个符号比较好理解,它就是为了避免除0而人为引入的一个很小的常数,例如可以设为:0.001。
第一个符号的表达式展开如下:
[G_t = sum_{i = 1}^{t} abla f( heta){i} abla f( heta){i}^{T}]
这个值其实是历史中每次梯度的平方的累加和。
AdaGrad算法能够在训练中自动的对learning rate进行调整,对于出现频率较低参数采用较大的学习率;相反,对于出现频率较高的参数采用较小的学习率。因此,Adagrad非常适合处理稀疏数据。
但该算法的缺点是它可能导致学习率非常小以至于算法收敛非常的慢。
关于这个算法的直观解释可以看李宏毅教授的视频课程:ML Lecture 3-1: Gradient Descent。
RMSProp
RMS是Root Mean Square的简写。RMSProp是AI教父Geoff Hinton提出的一种自适应学习率方法。AdaGrad会累加之前所有的梯度平方,而RMSProp仅仅是计算对应的平均值,因此可缓解Adagrad算法学习率下降较快的问题。
该算法的公式如下:
[E[ abla f( heta_{i})^2]^{t} = gamma E[ abla f( heta_{i})^2]^{t - 1} + (1-gamma)( abla f( heta_{i})^{t})^{2} heta_i = heta_i - frac{lambda}{sqrt{E[g^2]^{t+1} + epsilon}} abla f( heta_{i})]
类似的,是为了避免除0而引入。 是衰退参数,通常设为0.9。
这里的 是t时刻梯度平方的平均值。
Adam
Adam是Adaptive Moment Estimation的简写。它利用梯度的一阶矩估计和二阶矩估计动态调整每个参数的学习率。
Adam的优点主要在于经过偏置校正后,每一次迭代学习率都有个确定范围,使得参数比较平稳。
该算法公式如下:
[m^{t} = eta_{1} m^{t-1} + (1-eta_{1}) abla f( heta) v^{t} = eta_{2} v^{t-1} + (1-eta_{2}) abla f( heta)^2 widehat{m}^{t} = frac{m^{t}}{1 - eta^{t}_1} widehat{v}^{t} = frac{v^{t}}{1 - eta^{t}_2} heta = heta - frac{lambda}{sqrt{widehat{v}^{t}} + epsilon}widehat{m}^{t}]
,分别是对梯度的一阶矩估计和二阶矩估计。, 是对,的校正,这样可以近似为对期望的无偏估计。
Adam算法的提出者建议 默认值为0.9,默认值为0.999,默认值为 。
在实际应用中 ,Adam较为常用,它可以比较快地得到一个预估结果。
优化小结
这里我们列举了几种优化算法。它们很难说哪种最好,不同的算法适合于不同的场景。在实际的工程中,可能需要逐个尝试一下才能确定选择哪一个,这个过程也是目前现阶段AI项目要经历的工序之一。
实际上,该方面的研究远不止于此,如果有兴趣,可以继续阅读 《Sebastian Ruder: An overview of gradient descent optimization algorithms》 这篇论文或者 Optimization for Deep Learning 这个Slides进行更多的研究。
由于篇幅所限,这里不再继续展开了。
算法限制
梯度下降算法存在一定的限制。首先,它要求函数必须是可微分的,对于不可微的函数,无法使用这种方法。
除此之外,在某些情况下,使用梯度下降算法在接近极值点的时候可能收敛速度很慢,或者产生Z字形的震荡。这一点需要通过调整学习率来回避。
另外,梯度下降还会遇到下面两类问题。
局部最小值
局部最小值(Local Minima)指的是,我们找到的最小值仅仅是一个区域内的最小值,而并非全局的。由于算法的起点是随意取的,以下面这个图形为例,我们很容易落到局部最小值的点里面。
这就是好像你从上顶往下走,你第一次走到的平台未必是山脚,它有可能只是半山腰的一个平台的而已。
算法的起点决定了算法收敛的速度以及是否会落到局部最小值上。
坏消息是,目前似乎没有特别好的方法来确定选取那个点作为起点是比较好的,这就有一点看运气的成分了。多次尝试不同的随机点或许是一个比较好的方法,这也就是为什么做算法的优化这项工作是特别消耗时间的了。
但好消息是:
对于凸函数或者凹函数来说,不存在局部极值的问题。其局部极值一定是全局极值。
最近的一些研究表明,某些局部极值并没有想象中的那么糟糕,它们已经非常的接近全局极值所带来的结果了。
鞍点
除了Local Minima,在梯度下降的过程中,还有可能遇到另外一种情况,即:鞍点(Saddle Point)。鞍点指的是我们找到点某个点确实是梯度为0,但它却不是函数的极值,它的周围既有比它小的值,也有比它大的值。这就好像马鞍一样。
如下图所示:
多类随机函数表现出以下性质:在低维空间中,局部极值很普遍。但在高维空间中,局部极值比较少见,而鞍点则很常见。
不过对于鞍点,可以通过数学方法Hessian矩阵来确定。关于这点,这里就不再展开了,有兴趣的读者可以以这里提供的几个链接继续探索。
参考资料与推荐读物
Wikipeida: Gradient descent
Sebastian Ruder: An overview of gradient descent optimization algorithms
吴恩达:机器学习
吴恩达:深度学习
Peter Flach:机器学习
李宏毅 - ML Lecture 3-1: Gradient Descent
PDF: 李宏毅 - Gradient Descent
Intro to optimization in deep learning: Gradient Descent
Intro to optimization in deep learning: Momentum, RMSProp and Adam
Stochastic Gradient Descent – Mini-batch and more
刘建平Pinard - 梯度下降(Gradient Descent)小结
多元函数的偏导数、方向导数、梯度以及微分之间的关系思考
[Machine Learning] 梯度下降法的三种形式BGD、SGD以及MBGD
❺ e的x减一次方的导数
e的x减一次方的导数是e^(x-1)。
具体解法如下:
e的x减一次方,即为e^(x-1)
e的x减一次方的导数,即为e^(x-1)的导数
e^(x-1)'=e^(x-1)*(1)=e^(x-1)
所以e的x减一次方的导数是e^(x-1)。
(5)组合最优化与算法pdf扩展阅读
导数的求解注意点:
1、理解并牢记导数定义。导数定义中一定要出现这一点的函数值,如果已知告诉等于零,那极限表达式中就可以不出现,否就不能推出在这一点可导。
2、导数定义相关计算。这里有几种题型:1)已知某点处导数存在,计算极限,这需要掌握导数的广义化形式,还要注意是在这一点处导数存在的前提下,否则是不一定成立的。
3、导数、可微与连续的关系。函数在一点处可导与可微是等价的,可以推出在这一点处是连续的,反过来则是不成立的。
4、导数的计算。导数的计算可以说在每一年的考研数学中都会涉及到,而且形式不一,考查的方法也不同。
5、高阶导数计算。需要同学们记住几个常见的高阶导数公式,将其他函数都转化成我们这几种常见的函数,代入公式就可以了,也有通过求一阶导数,二阶,三阶的方法来找出他们之间关系的。