最小二乘法理论、推导、算法
author@jason_ql
http://blog.csdn.net/lql0716
1、引言
假定
x
<script type="math/tex" id="MathJax-Element-1">x</script>, y<script type="math/tex" id="MathJax-Element-2">y</script>有如下数值：
y | 1.00 | 0.90 | 0.90 | 0.81 | 0.60 | 0.56 | 0.35
x | 3.60 | 3.70 | 3.80 | 3.90 | 4.00 | 4.10 | 4.20
解：将这些数值画图可以看出接近一条直线，故用
y=ax+b
<script type="math/tex" id="MathJax-Element-3">y = ax + b</script>表示，故将上面的数值代入表达式有：
3.6a+b−1.00=03.7a+b−0.90=03.8a+b−0.90=03.9a+b−0.81=04.0a+b−0.60=04.1a+b−0.56=04.2a+b−0.35=0
<script type="math/tex; mode=display" id="MathJax-Element-4">3.6a + b - 1.00 = 0 \\
3.7a + b - 0.90 = 0 \\
3.8a + b - 0.90 = 0 \\
3.9a + b - 0.81 = 0 \\
4.0a + b - 0.60 = 0 \\
4.1a + b - 0.56 = 0 \\
4.2a + b - 0.35 = 0 \\
</script>
由于直线只有两个未知数
a
<script type="math/tex" id="MathJax-Element-5">a</script>, b<script type="math/tex" id="MathJax-Element-6">b</script>，理论上只需要两个方程就能求得，但是实际上是不可能的，因为所有点并没有真正的在同一条直线上，即不可能所有的数值都满足
ax+b−y＝0
<script type="math/tex; mode=display" id="MathJax-Element-7">ax + b - y＝0</script>，故只需找到一对儿
a
<script type="math/tex" id="MathJax-Element-8">a</script>、
b<script type="math/tex" id="MathJax-Element-9">b</script>，使得误差平方和
∑(axi+b−yi)2=(ax0+b−y0)2+(ax1+b−y1)2+......+(axn+b−yn)2
<script type="math/tex; mode=display" id="MathJax-Element-10">\sum(ax_i + b - y_i)^2
=(ax_0 + b - y_0)^2 + (ax_1 + b - y_1)^2 + ...... + (ax_n + b - y_n)^2</script>最小即可。
误差的平方即二乘方，故成为最小二乘法。
2、最小二乘法理论（使得平方和最小）
2.1 数学理论推导
⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪a11x1+a12x2+...+a1sxs−b1=0,a21x1+a22x2+...+a2sxs−b2=0,......an1x1+an2x2+...+ansxs−bn=0, (1)
<script type="math/tex; mode=display" id="MathJax-Element-11"> \left\{
\begin{aligned}
a_{11}x_1 + a_{12}x_2 + ... + a_{1s}x_s - b_1 = 0, \\
a_{21}x_1 + a_{22}x_2 + ... + a_{2s}x_s - b_2 = 0, \\
...... \\
a_{n1}x_1 + a_{n2}x_2 + ... + a_{ns}x_s - b_n = 0,
\end{aligned}
\right. \tag{1}</script>
该方程组可能无解，即任何一组
x1,x2,...,xs
<script type="math/tex" id="MathJax-Element-12">x_1, x_2, ... , x_s</script>（这里为系数）都可能使得
∑i=1n(ai1x1+ai2x2+...+aisxs−bi)2(2)
<script type="math/tex; mode=display" id="MathJax-Element-13">\sum_{i=1}^{n} (a_{i1}x_1 + a_{i2}x_2 + ... + a_{is}x_s - b_i)^2 \tag{2}</script>
不等于零。所以找到一组
x1,x2,...,xs
<script type="math/tex" id="MathJax-Element-14">x_1, x_2, ... , x_s</script>使得(2)式最小，称这样的解为最小二乘解，这种问题就叫最小二乘方问题。
对于（１）式，我们可以用矩阵来表示，
自变量矩阵
A
<script type="math/tex" id="MathJax-Element-15">\boldsymbol{A}</script>:
A=⎡⎣⎢⎢⎢a11a21.an1a12a22.an2..........a1sa2s.ans⎤⎦⎥⎥⎥(3)
<script type="math/tex; mode=display" id="MathJax-Element-16">
\boldsymbol{A}=\left[
\begin{matrix}
a_{11} & a_{12} & ... & a_{1s} \\
a_{21} & a_{22} & ... & a_{2s} \\
. & . & . & . \\
a_{n1} & a_{n2} & ... & a_{ns}
\end{matrix}
\right]
\tag{3}</script>
函数值
B
<script type="math/tex" id="MathJax-Element-17">\boldsymbol{B}</script>:
B=⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢b1b2...bn⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥(4)
<script type="math/tex; mode=display" id="MathJax-Element-18">\boldsymbol{B}=\left[
\begin{matrix}
b_{1} \\
b_{2} \\
. \\
. \\
. \\
b_{n}
\end{matrix}
\right]
\tag{4}</script>
系数
X
<script type="math/tex" id="MathJax-Element-19">\boldsymbol{X}</script>:
X=⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢x1x2...xs⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥(5)
<script type="math/tex; mode=display" id="MathJax-Element-20">\boldsymbol{X}=\left[
\begin{matrix}
x_{1} \\
x_{2} \\
. \\
. \\
. \\
x_{s}
\end{matrix}
\right]
\tag{5}</script>
函数值
Y
<script type="math/tex" id="MathJax-Element-21">\boldsymbol{Y}</script>:
Y=⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢∑j=1sa1jxj∑j=1sa2jxj...∑j=1sanjxj⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥=AX(4)
<script type="math/tex; mode=display" id="MathJax-Element-22">\boldsymbol{Y}=\left[
\begin{matrix}
\sum_{j=1}^{s} a_{1j}x_j \\
\sum_{j=1}^{s} a_{2j}x_j \\
. \\
. \\
. \\
\sum_{j=1}^{s} a_{nj}x_j
\end{matrix}
\right] = \boldsymbol{AX}
\tag{4}</script>
故（２）式等价于：
|Y−B|2=|AX−B|2=∑i=1n(ai1x1+ai2x2+...+aisxs−bi)2
<script type="math/tex; mode=display" id="MathJax-Element-23">|\boldsymbol{Y-B}|^2 = |\boldsymbol{AX-B}|^2 = \sum_{i=1}^{n} (a_{i1}x_1 + a_{i2}x_2 + ... + a_{is}x_s - b_i)^2</script>
也就是说，最小二乘法就是找
x1,x2,...,xs
<script type="math/tex" id="MathJax-Element-24">x_1, x_2, ... , x_s</script>使得
Y
<script type="math/tex" id="MathJax-Element-25">\boldsymbol{Y}</script>与
B
<script type="math/tex" id="MathJax-Element-26">\boldsymbol{B}</script>的距离最短。
对于（4）式
Y
<script type="math/tex" id="MathJax-Element-27">\boldsymbol{Y}</script>，可以写为如下形式：
Y=x1⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢a11a21...an1⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥+x2⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢a12a22...an2⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥+...+xs⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢a1sa2s...ans⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥=x1α1+x2α2+...+xsαs(5)
<script type="math/tex; mode=display" id="MathJax-Element-28">\boldsymbol{Y}=x_1\left[
\begin{matrix}
a_{11} \\
a_{21} \\
. \\
. \\
. \\
a_{n1}
\end{matrix}
\right] +
x_2\left[
\begin{matrix}
a_{12} \\
a_{22} \\
. \\
. \\
. \\
a_{n2}
\end{matrix}
\right] + ... +
x_s\left[
\begin{matrix}
a_{1s} \\
a_{2s} \\
. \\
. \\
. \\
a_{ns}
\end{matrix}
\right]
= x_1 \boldsymbol{\alpha}_1 + x_2 \boldsymbol{\alpha}_2 + ... + x_s\boldsymbol{\alpha}_s
\tag{5}</script>
其中
αi
<script type="math/tex" id="MathJax-Element-29">\boldsymbol{\alpha}_i</script>为对应的列向量，由
αi
<script type="math/tex" id="MathJax-Element-30">\boldsymbol{\alpha}_i</script>生成的子空间为
L(α1,α2,...,αs)
<script type="math/tex" id="MathJax-Element-31">\boldsymbol{L}(\boldsymbol{\alpha}_1, \boldsymbol{\alpha}_2, ... , \boldsymbol{\alpha}_s)</script>,那么
Y
<script type="math/tex" id="MathJax-Element-32">\boldsymbol{Y}</script>就是
L(α1,α2,...,αs)
<script type="math/tex" id="MathJax-Element-33">\boldsymbol{L}(\boldsymbol{\alpha}_1, \boldsymbol{\alpha}_2, ... , \boldsymbol{\alpha}_s)</script>中的向量，故最小二乘法问题可叙述成：
找
X
<script type="math/tex" id="MathJax-Element-34">\boldsymbol{X}</script>使得（2）式最小，就是在
L(α1,α2,...,αs)
<script type="math/tex" id="MathJax-Element-35">\boldsymbol{L}(\boldsymbol{\alpha}_1, \boldsymbol{\alpha}_2, ... , \boldsymbol{\alpha}_s)</script>中找一向量
Y
<script type="math/tex" id="MathJax-Element-36">Y</script>使得B<script type="math/tex" id="MathJax-Element-37">B</script>到它的距离比到子空间
L(α1,α2,...,αs)
<script type="math/tex" id="MathJax-Element-38">\boldsymbol{L}(\boldsymbol{\alpha}_1, \boldsymbol{\alpha}_2, ... , \boldsymbol{\alpha}_s)</script>中其它向量的距离都短。
设
Y=AX=x1α1+x2α2+...+xsαs
<script type="math/tex" id="MathJax-Element-39">\boldsymbol{Y} = \boldsymbol{AX} = x_1 \boldsymbol{\alpha}_1 + x_2 \boldsymbol{\alpha}_2 + ... + x_s\boldsymbol{\alpha}_s</script>，则
C=B−Y=B−AX
<script type="math/tex; mode=display" id="MathJax-Element-40">\boldsymbol{C} = \boldsymbol{B} - \boldsymbol{Y} = \boldsymbol{B} - \boldsymbol{AX}</script>
必须垂直于子空间
L(α1,α2,...,αs)
<script type="math/tex" id="MathJax-Element-41">\boldsymbol{L}(\boldsymbol{\alpha}_1, \boldsymbol{\alpha}_2, ... , \boldsymbol{\alpha}_s)</script>，故有
(C,α1)=(C,α2)=...=(C,αs)=0
<script type="math/tex; mode=display" id="MathJax-Element-42">(\boldsymbol{C}, \boldsymbol{\alpha}_1) = (\boldsymbol{C}, \boldsymbol{\alpha}_2) = ... = (\boldsymbol{C}, \boldsymbol{\alpha}_s) = 0</script>
由向量内积的定义可知：
α′1C=0,α′2C=0,...,α′sC=0(6)
<script type="math/tex; mode=display" id="MathJax-Element-43">\boldsymbol{\alpha}_1^{'} C = 0, \boldsymbol{\alpha}_2^{'} C = 0, ... , \boldsymbol{\alpha}_s^{'} C = 0 \tag{6}</script>
向量的内积：
α=(a1,a2,...,an)
<script type="math/tex" id="MathJax-Element-44"> \boldsymbol{\alpha} = (a_1, a_2, ..., a_n)</script>,
β=(b1,b2,...,bn)
<script type="math/tex" id="MathJax-Element-45"> \boldsymbol{\beta} = (b_1, b_2, ..., b_n)</script>,
则
α
<script type="math/tex" id="MathJax-Element-46"> \boldsymbol{\alpha}</script>和
β
<script type="math/tex" id="MathJax-Element-47">\boldsymbol{\beta}</script>的内积为：
(α,β)=a1b1+a2b2+...+anbn
<script type="math/tex" id="MathJax-Element-48">(\boldsymbol{\alpha}, \boldsymbol{\beta})=a_1b_1 + a_2b_2 + ... + a_nb_n</script>
由（6）式可得：
A′C=0
<script type="math/tex; mode=display" id="MathJax-Element-49">\boldsymbol{A^{'}C}=0</script>
即：
A′C=A′(B−Y)=A′(B−AX)=0
<script type="math/tex; mode=display" id="MathJax-Element-50">\boldsymbol{A^{'}C}=\boldsymbol{A^{'}(B-Y)}=\boldsymbol{A^{'}(B-AX)}=0</script>
从而有：
A′B−A′AX=0
<script type="math/tex; mode=display" id="MathJax-Element-51">\boldsymbol{A^{'}B-A^{'}AX}=0</script>
A′B=A′AX
<script type="math/tex; mode=display" id="MathJax-Element-52">\boldsymbol{A^{'}B=A^{'}AX}</script>
X=(A′A)−1A′B
<script type="math/tex; mode=display" id="MathJax-Element-53">\boldsymbol{X=(A^{'}A)^{-1}A^{'}B}</script>
其中
|A′A|≠0
<script type="math/tex" id="MathJax-Element-54">\boldsymbol{|A^{'}A|} \neq 0</script>
2.2 常见形式
2.2.1 理论
根据2.1节，可以得出以下形式(
s+1≤n
<script type="math/tex" id="MathJax-Element-55">s+1 \leq n</script>):
⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪a1x11+a2x12+...+asx1s+b−y1=0,a1x21+a2x22+...+asx2s+b−y2=0,......a1xn1+a2xn2+...+asxns+b−yn=0, (2.2.1)
<script type="math/tex; mode=display" id="MathJax-Element-56"> \left\{
\begin{aligned}
a_1x_{11} + a_2x_{12} + ... + a_sx_{1s} + b - y_1= 0, \\
a_1x_{21} + a_2x_{22} + ... + a_sx_{2s} + b - y_2= 0, \\
...... \\
a_1x_{n1} + a_2x_{n2} + ... + a_sx_{ns} + b - y_n= 0,
\end{aligned}
\right. \tag{2.2.1}</script>
这里是常见的方程表示形式
aj
<script type="math/tex" id="MathJax-Element-57">a_j</script>为系数，
b
<script type="math/tex" id="MathJax-Element-58">b</script>为常数项,xij<script type="math/tex" id="MathJax-Element-59">x_{ij}</script>为自变量，
yi
<script type="math/tex" id="MathJax-Element-60">y_i</script>为函数值。一般我们解方程都是根据
aj
<script type="math/tex" id="MathJax-Element-61">a_j</script>和
b
<script type="math/tex" id="MathJax-Element-62">b</script>求得yi=a1xi1+a2xi2+...+asxis+b<script type="math/tex" id="MathJax-Element-63">y_i=a_1x_{i1} + a_2x_{i2} + ... + a_s x_{is} + b</script>，但在解决实际问题时，一般我们都是知道
xij
<script type="math/tex" id="MathJax-Element-64">x_{ij}</script>和
yi
<script type="math/tex" id="MathJax-Element-65">y_i</script>，需要反过来求解
aj
<script type="math/tex" id="MathJax-Element-66">a_j</script>和
b
<script type="math/tex" id="MathJax-Element-67">b</script>。
根据（2.2.1）式，设：
X=⎡⎣⎢⎢⎢x11x21.xn1x12x22.xn2..........x1sx2s.xns1111⎤⎦⎥⎥⎥
<script type="math/tex; mode=display" id="MathJax-Element-68"> \boldsymbol{X}=\left[
\begin{matrix}
x_{11} & x_{12} & ... & x_{1s} & 1\\
x_{21} & x_{22} & ... & x_{2s} & 1\\
. & . & . & . & 1\\
x_{n1} & x_{n2} & ... & x_{ns} & 1
\end{matrix}
\right]</script>
a=⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢a1a2...asb⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥
<script type="math/tex; mode=display" id="MathJax-Element-69">\boldsymbol{a}=\left[ \begin{matrix} a_1 \\ a_2 \\ . \\ . \\. \\ a_s \\ b \end{matrix} \right]</script>
y=⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢y1y2...yn⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥
<script type="math/tex; mode=display" id="MathJax-Element-70">\boldsymbol{y}=\left[ \begin{matrix} y_1 \\ y_2 \\ . \\ . \\. \\ y_n \end{matrix} \right]</script>
那么：
Xa=y
<script type="math/tex; mode=display" id="MathJax-Element-71">\boldsymbol{X a=y}</script>
X′Xa=X′y
<script type="math/tex; mode=display" id="MathJax-Element-72">\boldsymbol{X^{'}X a=X^{'}y}</script>
a=(X′X)−1X′y
<script type="math/tex; mode=display" id="MathJax-Element-73">\boldsymbol{ a=(X^{'}X)^{-1}X^{'}y}</script>
2.2.2 算法
1、输入
X
<script type="math/tex" id="MathJax-Element-74">\boldsymbol{X}</script>，
y
<script type="math/tex" id="MathJax-Element-75">\boldsymbol{y}</script>
2、求
a=(X′X)−1X′y
<script type="math/tex" id="MathJax-Element-76">\boldsymbol{a=(X^{'}X)^{-1}X^{'}y}</script>
参考
《高等代数》北大三版
干货分享
24
0
已为社区贡献2条内容
所有评论(0)