最小二乘法

什么是最小二乘法

嗯,通俗的讲,就是让一些数据进行线性的拟合,使得我们找到数据间的线性关系,从而实现预测数据。很多大数据的算法都是基于最小二乘法。

通过最小二乘法,我们就能从上方的数据(红色)中拟合出一条直线(蓝色)。


一些先修知识

在线性代数中,一个矩阵A的列秩是A的线性独立的纵列的极大数目。类似地,行秩是A的线性独立的横行的极大数目。
矩阵的列秩和行秩总是相等的,因此它们可以简单地称作矩阵A的秩。

范数

对一个向量$(x_1,x_2,\cdots ,x_n)$在空间中赋予长度的函数叫做范数。如我们熟悉的欧几里德距离就是二范数,写作:
$$|| \vec{x} ||_2=\sqrt{x_1^2+x_2^2+\cdots +x_n^2}$$

相容方程

什么是相容方程呢,简单说就是有解(不一定唯一)的方程,例如:
$$\begin{cases}
2x_1+3x_2=8 \\
-x_1+9x_2=17
\end{cases}$$
容易得到存在一组解$x_1=1,x_2=2$,满足上方程。这样的方程就是相容的。
或者这样的方程:
$$\begin{cases}
2x_1+3x_2=8 \\
4x_1+6x_2=16
\end{cases}$$
就能得到无数组解,这也是相容的。

一个方程$Ax=b$是相容的,当且仅当增广矩阵的秩$rand[A,b]$等于系数矩阵的秩$rank[A]$。

费马引理

相比很多同学高中都学过这个引理,只是不知道它的名字。
对于函数$f(x_1,x_2,\cdots ,x_n)$,如果函数在点$\vec{x_0}$的领域内有定义,且在$\vec{x_0}$处可导,如果对于任意$\vec{x}\in U(\vec{x_0})$有$f(\vec{x_0})\le f(\vec{x})$或者$f(\vec{x_0})\ge f(\vec{x})$,那么$\frac{\partial f}{\partial x_i}=0$,其中$x_i$是$\vec{x_0}$的每个分量。
用简单的话讲,上述定理表明,一个函数如果在某个点可导并且取得极值,那么此处的导数等于零。


不相容方程怎样找到一个比较好的解?

对于这样一个问题,我们需要先定义什么是比较好,然后再来寻找解。

比较好?

对于下面这种方程:
$$\begin{cases}
2x_1+3x_2=8 \\
-x_1+9x_2=15 \\
x_1-2x_2=1
\end{cases}$$
我们是得不到解的,那我们尝试着寻找一个近似的解,使得左边算出来的值和右边算出来的值的差的平方尽量小。即:
$$\underset{x}{argmin}||Ax-b||_2^2$$
这样我们就定义了足够好的解是怎样的。

怎么得到这样的解?

令$f(x)=\underset{x}{argmin}||Ax-b||_2^2$,那么我们可以通过费马引理去求得极小值是$x$的值。
可以证明这样的解是唯一的。
为了计算方便,一般采用$QR$分解的方式来计算最小二乘的解。戳这里


应用

实际应用中往往是给出大量的二元组,寻找一个合适的线性方程来拟合,即寻找$y=kx+b$中的$k$和$b$。只需要将$k$和$b$当作未知数进行最小二乘即可。

销售问题

根据经验,我们通常能够得出售价与销售量是线性的关系。现在给出若干的销量和售价的数据,我们希望通过这些数据得到较好的拟合关系,并且通过这样的关系来确定合适的售出价,以获得最多的利润。

使用matlab的函数polyfit能进行多项式的拟合,其中polyfit(x,y,1)既是进行线性拟合。

1
2
3
4
5
6
7
8
load price;
load sales;
P=polyfit(price,sales,1);
x=0.3:0.0001:1.3;
y=P(1)*x+P(2);
plot(price,sales,'o');
hold on;
plot(x,y);

得到这样的图像:

其中点表示原始数据,其中的直线表示拟合的关系。
用一个高中的知识,我们能够知道,若要取得最大利润,既是二次函数的极值问题。令$W$为最后的利润,$a$为成本,则$W=y(x-a)=(kx+b)(x-a)=kx^2+(b-ak)x-ab$,当$x=(-b+ak)/(2k)$的时候,取得最大值。
由给出的数据我们知道$a=0.23$,通过上面的程序求得的$k,b$,我们得出在$x=0.6869$时,取得最大值$W=1735.7$。