数值分析15(最小二乘法1)

1、1/4610:56超定方程组超定方程组最小二乘拟合最小二乘拟合模型综述模型综述数值分析 152/4610:56引子引子: 行星运动定律行星运动定律(开普勒第三定律开普勒第三定律)绕以太阳为焦点的椭圆轨道运行的所有行星绕以太阳为焦点的椭圆轨道运行的所有行星, 其各自其各自椭圆轨道半长轴的立方与周期的平方之比是一个常量。椭圆轨道半长轴的立方与周期的平方之比是一个常量。3/4610:56 行星行星 半长轴半长轴 (a) 周期周期 (T) T2/a3 海王星海王星 450 165 天王星天王星 287 84 2.99 2.98323245016528784c 行星运动定律行星运动定律 绕以太阳为焦点的

2、椭圆轨道运行的所有行星绕以太阳为焦点的椭圆轨道运行的所有行星, 其各自其各自椭圆轨道半长轴的立方与周期的平方之比是一个常量。椭圆轨道半长轴的立方与周期的平方之比是一个常量。4/4610:56 不相容方程组不相容方程组(inconsistent equation)1212122,1,3.xxxxxx 一个无解的方程组称为不相容。许多情况下方程一个无解的方程组称为不相容。许多情况下方程个数大于未知量个数使解不大可能满足所有的方程。个数大于未知量个数使解不大可能满足所有的方程。定义定义: 一个方程组若至少存在一个解能够严格满足该方一个方程组若至少存在一个解能够严格满足该方程组程组,则称为相容方程则称

3、为相容方程(consistent equation)。Axb 定理定理: 线性方程线性方程Ax=b是相容的当且仅当是相容的当且仅当 rank(A,b)=rank(A) 。5/4610:56 不相容方程组不相容方程组(inconsistent equation) 当方程组不相容时当方程组不相容时, 如何寻求如何寻求次佳次佳(next-best)解。解。0rAxb2222minmin( )xxAxbr x 即即 Axb 我们希望残差我们希望残差r尽可能小尽可能小,这里小的标准是什么呢？这里小的标准是什么呢？2221 squares()niilreastr 6/4610:56112211211211

4、1111113113xxxx 等等价价于于12?bvv如如果果 不不属属于于 和和 张张成成的的平平面面7/4610:561212211222,222121212, argargminmin ( )argmin(-2)(-1)(-3)xxxxxxbument of theimumxxxxxx多变量函数极值点多变量函数极值点:00( ) grad ()0 xf xf x 设设是是的的一一个个极极值值点点的的必必要要条条件件是是。111222()0TTxxb TTA AxA b 最小二乘解最小二乘解(Least Squares Solution):8/4610:56():TTnormal equa

5、A AxAnbtio 正正规规方方程程 121122()0TTnnTnxxxb 9/4610:5612112111113xx 1111131111111311TA A 21116111143TA b 12316134xx 例例11230.5()00.5rresiduals rbAxrr 残残差差22221232( )least squrrrrares10/4610:56,m nAxbARmn 超超定定方方程程其其中中 回顾回顾:22 argmin|xAxb 最最小小二二乘乘解解1,()TTTA AxA AA b 进进一一步步地地如如果果可可逆逆 则则 Axb TTA AxA b 正正规规方方程

6、程11/4610:56大数据环境下的数据挖掘大数据环境下的数据挖掘12/4610:56引子引子: 行星运动定律行星运动定律(开普勒第三定律开普勒第三定律)绕以太阳为焦点的椭圆轨道运行的所有行星绕以太阳为焦点的椭圆轨道运行的所有行星, 其各自其各自椭圆轨道半长轴的立方与周期的平方之比是一个常量。椭圆轨道半长轴的立方与周期的平方之比是一个常量。13/4610:56例例2: 研究弹簧伸长的长度跟引起形变的外力的关系。研究弹簧伸长的长度跟引起形变的外力的关系。load Hooke.matu=0.08:.0001:0.35; v=interp1(x,y,u,spline);plot(x,y,o,u,v,

7、-)Hookes Law14/4610:56 x 0.0861 0.1720 0.2598 0.2701 0.3015 0.3225 f(x) 0.0197 0.0398 0.0597 0.0647 0.0697 0.0746求拟合函数求拟合函数:110221111mmyxcxycxy Ac=b01( )f xcc x0111cc xy0122cc xy01mmcc xy112111 mmiiiiTTmmmiiiiiiimxyA AcA bxxx y15/4610:56例例3. 美国人口统计数据美国人口统计数据(censusgui) load census研究美国人口增长的规律并预测研究美国人

8、口增长的规律并预测2010年的人口。年的人口。求拟合函数求拟合函数:230123( )f xcc xc xc x16/4610:56 x x1 x2 xm f(x) y1 y2 ym离散数据的多项式拟合离散数据的多项式拟合求拟合函数求拟合函数:1011211nnmmnmycxxyxxcy 01( )nnf xcc xc x11101121111 mkmmknkkmkkkkTTkmmmnnnnkkkmkkknkkkymxxcx yA AcA bcxxxx y 17/4610:56例例4. 求最小二乘拟合数据点求最小二乘拟合数据点(-1,1),(0,0),(1,0),(2,-2)的的直线模型和抛物

9、线模型直线模型和抛物线模型。,yabxab首首先先选选取取模模型型目目标标是是寻寻求求最最佳佳的的 和和 。1-1110042-10.20.911026-512-2aaytbb 2,yabxcxa bc选选取取模模型型目目标标是是寻寻求求最最佳佳的的和和 。21-111426-110002680.450.65 -0.25-511106818-7124-2aayxxbbcc 18/4610:56例例5. 线性分类线性分类(Machine Learning) 年龄年龄 相貌相貌 才华才华 财富财富 品德品德 http:/ wwyc 或或19/4610:56 x x1 x2 xm f(x) y1 y

10、2 ym离散数据的最小二乘线性拟合离散数据的最小二乘线性拟合求拟合函数求拟合函数:1001111201()()()()()()nmmnmnmycxxxyxxxcy 0011( )( )( )( )nnf xcxcxcx01000110110111()()()()()()()()()()()mkkmmkkkknkmkkkkTTkmmnnkknknkmkknkkkxyxxxxcxyA AcA bcxxxxxy 20/4610:56压缩的概念压缩的概念: 最小二乘拟合是数据压缩的典型例子最小二乘拟合是数据压缩的典型例子, 输输入大量的噪声观测数据入大量的噪声观测数据, 而输出是尽可能好地而输出是尽可

11、能好地拟合数据的模型拟合数据的模型(相对少的模型参数相对少的模型参数)。最小二。最小二乘用合理的模型来代替乘用合理的模型来代替大量的噪声数据大量的噪声数据。21/4610:56最小二乘数据拟合最小二乘数据拟合: 残差残差(residuals)是指观测值与模型预测值之间的差是指观测值与模型预测值之间的差:我们希望残差尽可能小我们希望残差尽可能小, 这里小的标准是什么呢？这里小的标准是什么呢？1. .残差为零残差为零(插值方法插值方法)2. .最小化残差的平方和最小化残差的平方和(最小二乘解最小二乘解)0()niikkikrycxryAc 或或0120011,1argmin()()()nmiiin

12、niccciycxcxcx 22/4610:563. .最小化残差的绝对值之和最小化残差的绝对值之和4. .最小化残差绝对值的最大分量最小化残差绝对值的最大分量010011,argminmax()()()niiinniicccycxcxcx010011,1argmin()()()nmiiinniccciycxcxcx 23/4610:56最小二乘拟合的步骤最小二乘拟合的步骤:给定的观测数据给定的观测数据(x1,y1), (xm,ym)1. 选取模型选取模型: 确定的模型类型确定的模型类型, 如如y=a+bx。2. 使模型使模型拟合数据拟合数据:将数据代入模型将数据代入模型, 每个观测每个观测数

13、据对应一个参数作为未知数的方程。数据对应一个参数作为未知数的方程。3. 求解最小二乘解求解最小二乘解(模型的参数模型的参数)。 24/4610:56最小二乘拟合问题研究包括最小二乘拟合问题研究包括: :模型的选取模型的选取存在唯一性存在唯一性最小二乘解的计算最小二乘解的计算25/4610:56 The Law Dominants Our World (ten most important formulas on stamps issued by Nicaragua in 1971)26/4610:56The Law Dominants Our World27/4610:56The Law Do

14、minants Our World28/4610:56模型综述模型综述01: ( ) y xaa x直直线线常用模型包括常用模型包括: :01: ( )+nny xaa xa x多多项项式式21: ( )c xy xc e 指指数数函函数数2(): ( )exy x 高高斯斯函函数数: ( )cos( )siny xxy xx三三角角函函数数或或所有的现象背后都有一个规律所有的现象背后都有一个规律(函数函数)吗？吗？12: ( )lny xcc x 对对数数函函数数29/4610:56例例6. . 线性规律线性规律 Linear Law牛顿第二定律牛顿第二定律胡克定律胡克定律 (Hookes

15、law) 线性思维线性思维(linear thinking)30/4610:56周期数据周期数据31/4610:56周期数据周期数据32/4610:56例例7. . 人体的周期预测人体的周期预测t0=datenum(Dec.20,1983)t1=fix(now);t=(t1-28):1:(t1+28);y=100*sin(2*pi*(t-t0)/23); sin(2*pi*(t-t0)/28); sin(2*pi*(t-t0)/33)plot(t,y)legend(生理周期生理周期,情绪周期情绪周期,智力周期智力周期)33/4610:56例例8. . 外部气温在不同时间尺度下服从周期循环。外部

16、气温在不同时间尺度下服从周期循环。123: ( )cos2sin2y xccxcx选选择择模模型型34/4610:56442233445544332277441cos0sin02.21cossin2.81cossin6.11cossin3.9,1cossin01cossin1.11cossin0.61cossin1.1Ab 12380015.60402.977800410.2376TTcA AcA bcc : ( )-1.95-0.7445cos2-2.559sin2y xxx 最最佳佳模模型型load temperature.matplot(x,y);u=0:0.01:1;v=-1.95-0

17、.7445*cos(2*pi*u)-2.5594*sin(2*pi*u);hold on,plot(u,v,r)35/4610:56例例9. . 指数函数指数函数( (刻画增长或衰减的数据规律刻画增长或衰减的数据规律,如如放射性原子核的衰变规律和放射性原子核的衰变规律和Moore定律定律) )我们总是高估在一年或者两年中能够做到的我们总是高估在一年或者两年中能够做到的,而低估五年或者十年中能够做到的。而低估五年或者十年中能够做到的。36/4610:5611ln225012ln2500,14ln5000133ln410000000Ab21: ( )cc xy xe 选选择择模模型型12:ln (

18、 )ln+y xcc x 线线性性化化技技术术22 13235176.9023559273793.23TTkA AA bckc 0.3596: ( )1335.3xy xe 最最佳佳模模型型Moore 1.9276ln2/ 0.3596 定定律律2122,i=11argmin(e)imxicc ccy 122l,2n=1arg min(ln)miicikckxcy 37/4610:56线性化改变了原最小二乘问题。线性化改变了原最小二乘问题。2122,11argmin(e)imxicic ccy 122l2n,1arg min(ln)kmiiiccyxkc 对于原非线性最小二乘问题可以考虑对于原

19、非线性最小二乘问题可以考虑Gradient Descent和和 Gauss-Newton等优化等优化方法。方法。38/4610:56摩尔定律已经成为工业界一切呈指数型增长事摩尔定律已经成为工业界一切呈指数型增长事物的代名词。下一个十年物的代名词。下一个十年, 摩尔定律可能还将摩尔定律可能还将有效有效。可以肯定的是可以肯定的是, 创新无止境。创新无止境。 戈登戈登. .摩尔摩尔( (英特尔创始人英特尔创始人) )39/4610:56例例10. . 幂函数幂函数( (power law) )21: ( )ccy xx 选选择择模模型型40/4610:56例例11. .生物界的牛顿定律生物界的牛顿定

20、律 1998年年Nature的一篇文章的一篇文章Common rules for animals and plants揭示了生物体的一些常见计揭示了生物体的一些常见计量值与其质量的关系量值与其质量的关系, 被被Nature编辑喻为生物编辑喻为生物界的牛顿定律。简单的说就是发现了界的牛顿定律。简单的说就是发现了Y= =Y0Mb ,其中其中M为质量为质量, Y为生物体的一些计量值为生物体的一些计量值, Y0为为常数关系中常数关系中b值的大小和原因值的大小和原因, 且这一规律在横且这一规律在横跨质量的跨质量的21个数量级都满足。个数量级都满足。41/4610:56例例12. . 计算机视觉中计算机视觉中Gamma校正校正42/4610:56例例13. . 血液中药物的衰减规律血液中药物的衰减规律21: ( )ccy xx 选选择择模