Question

Regression

“迴归”就是找一个函数，尽量符合手边的一堆数据。此函数称作“迴归函数”。

这裡谈的是用函数符合数据们，主角是函数，所以会把数据对应到函数的格式。

也许读者很好奇，为什麽主角是函数呢？私以为函数有著优美的性质，函数也是众人从小到大接触、非常熟悉的数学元件，因此大家第一个直觉就是使用函数。另一方面，使用函数，就能多少发现一些输入、输出之间的关係，例如成正比、成反比等等。

也许读者很好奇，能不能用随意曲线、随意几何图形符合数据们呢？也许是可以的。我想这是个新学问，该由读者们来开创。在图形辨识领域，已经存在一些方法，有志者不妨先从这裡下手。

Error

强硬地用函数符合数据们，就会有“误差”。

单一数据的误差，有许多种衡量方式，一般是用数据与函数值的差的平方（平方误差），其他还有数据与函数值的差的绝对值（绝对值误差）、数据与函数曲线的最短距离等等。

Optimization

人脑考虑的“最符合”，放到了电脑就被设定成“所有数据的误差总和最小”。把所有数据的误差总和写成一个函数，迴归问题就变成了最佳化问题！

例如用函数 f(x) = ax² + bx + c

符合数据 (2,3) ... (7,8)
用代数符号标记成 (x₁,y₁) ... (xN,yN)

每个数据的平方误差分别是
[f(2) - 3]² ... [f(7) - 8]²
[(a⋅2² + b⋅2 + c) - 3]² ... [(a⋅7² + b⋅7 + c) - 8]²
用代数符号标记成
[f(x₁) - y₁]² ... [f(xN) - yN]²
[(ax₁² + bx₁ + c) - y₁]² ... [(axN² + bxN + c) - yN]²

所有数据的误差总和是
[f(2) - 3]² + ... + [f(7) - 8]²
[(a⋅2² + b⋅2 + c) - 3]² + ... + [(a⋅7² + b⋅7 + c) - 8]²
用代数符号标记成 
e(a,b,c) = [(ax₁² + bx₁ + c) - y₁]² + ... + [(axN² + bxN + c) - yN]²
           N
         = ∑ [(axᵢ² + bxᵢ + c) - yᵢ]²
          i=1
         = ∑ (f(xᵢ) - yᵢ)²
         = ∑ (ŷᵢ - yᵢ)²
         = ∑ ‖ŷᵢ - yᵢ‖

目标是令 e(a,b,c) 越小越好。
选定一个最佳化演算法，求出 e(a,b,c) 的最小值，求出此时 abc 的数值，
就得到迴归函数 f(x)。

Linear Regression

Linear Regression

“线性迴归”。迴归函数採用线性函数。误差採用平方误差。

二维数据，迴归函数是直线。三维数据，迴归函数是平面。推广到多维数据，迴归函数是数据维度减少一维（hyperplane）。

线性迴归性质特殊，不需要最佳化演算法。写成线性方程组，套用“ Normal Equation ”。

直线函数 f(x) = ax + b
符合二维数据 (2,3) (5,6) (7,8)
[ 2  1 ] [ a ]   [ 3 ]
[ 5  1 ] [ b ] = [ 6 ]
[ 7  1 ]         [ 8 ]

平面函数 f(x,y) = ax + by + c  
符合三维数据 (2,3,4) (5,6,7) (7,8,9) (3,3,3) (4,4,4)
[ 2  3  1 ]         [ 4 ]
[ 5  6  1 ] [ a ]   [ 7 ]
[ 7  8  1 ] [ b ] = [ 9 ]
[ 3  3  1 ] [ c ]   [ 3 ]
[ 4  4  1 ]         [ 4 ]

另外提供二维数据的公式解。

http://mathworld.wolfram.com/LeastSquaresFitting.html

Inlier / Outlier

真实世界的数据并非完美，常有例外。

无弹性的定义：全部数据分为 inlier 和 outlier；inlier 是位在迴归函数上面的数据，outlier 是不在迴归函数上面的数据。

有弹性的定义：全部数据分为 inlier 和 outlier；inlier 是距离迴归函数够近的数据，outlier 是距离迴归函数太远的数据。

outlier 导致迴归函数易位。感觉类似：有人成绩特别低，大幅拉低平均，无法正确反映大家的成绩。

我们必须预先剔除 outlier，再进行迴归。

演算法（RANSAC）（Random Sample Consensus）

区分 inlier 和 outlier 的演算法非常简单。

一、设定弹性宽度 D。
二、随机挑出 K 笔数据，只用这 K 笔数据迴归，得到迴归函数。
　　K 可以自由设定，不必很大。
　　如果迴归函数是直线，1 笔不够形成直线，可以设定成 2 笔。
　　如果迴归函数是複杂曲线，就多几笔。
三、根据此迴归函数，计算共有多少个 inlier 和 outlier。
四、重複上述步骤 T 次。
　　从中找到 inlier 最多、outlier 最少的情况，推定为正解。
　　T 可以自由设定。

inlier 通常较多、outlier 通常较少。随机挑出数据，容易挑到 inlier，容易形成符合 inlier 的迴归函数──此即 RANSAC 的精髓。

RANSAC 儘管缺乏理论根据，儘管名字怪异，却非常实用。

RANSAC 只可用于区分 inlier 和 outlier，不可用于求得迴归函数（除非弹性宽度是零）。RANSAC 只挑出少数数据，误差总和不对，迴归函数不对。正确的流程是：实施 RANSAC，删除 outlier，保留 inlier，重新实施迴归，更加符合数据！

演算法（Theil-Sen Estimator）

《Optimal slope selection via expanders》

找到所有两点连线的斜率的中位数。点线对偶，所有直线的所有交点的 X 座标中位数。时间複杂度 O(NlogN)。

Line Fitting

Line Fitting / Plane Fitting

“直线拟合”与“平面拟合”。迴归标的採用直线、平面。误差採用最短距离（垂直距离）的平方和。

每笔数据，套用“点与直线距离公式”求得最短距离，累计最短距离的平方和。不失一般性，令分母等于 1。首先解出常数项，其馀变数改写成线性方程组，套用“ Homogeneous Linear Equations ”，计算维度的共变异矩阵，答案是最小的特徵值的特徵向量。

直线 ax + by + c = 0
符合二维数据 (2,3) (5,6) (7,8)

计算每笔数据与直线的最短距离，统计平方和，越小越好。
不失一般性，令 a² + b² = 1。

           (axᵢ + byᵢ + c)²
minimize ∑ ――――――――――――――――
               a² + b²    

minimize ∑ (axᵢ + byᵢ + c)² subject to a² + b² = 1
   ______________________________________________________
  | 错误的分岐路线：
  | 改写成线性方程组 min ‖Xₕᵀwₕ‖²，但是解不了
  | [ 2  3  1 ] [ a ]      
  | [ 5  6  1 ] [ b ]
  | [ 7  8  1 ] [ c ]
  |     Xₕᵀ       wₕ 
   ‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾
先尝试解出其中一部分变数。首先解 c。
极值出现在一次微分等于零的地方。

2 ∑ (axᵢ + byᵢ + c) = 0

      ∑ axᵢ + ∑ byᵢ
c = - ————————————— = - ax̄ - bȳ
            n

    ∑xᵢ   2+5+7       ∑yᵢ   3+6+8
x̄ = ——— = ————— , ȳ = ——— = —————
     n      3          n      3  
   ______________________________________________________
  | 错误的分岐路线：
  | 解出 c 之后，代入微分式子得到
  | ax + by - ax̄ - bȳ = a(x-x̄) + b(y-ȳ) = 0
  |
  | 改写成线性方程组 X̂ᵀw = 0，但是解不了！
  | [ 2-x̄  3-ȳ ] [ a ]   [ 0 ]
  | [ 5-x̄  6-ȳ ] [ b ] = [ 0 ]
  | [ 7-x̄  8-ȳ ]         [ 0 ]
  |      X̂ᵀ       w
   ‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾
解出 c 之后，代入原本的最佳化式子。
数据预先减去平均值，再做最佳化！
minimize ∑ (axᵢ + byᵢ - ax̄ - bȳ)² subject to a² + b² = 1
minimize ∑ [a(xᵢ-x̄) + b(yᵢ-ȳ)]²   subject to a² + b² = 1

改写成线性方程组 min ‖X̂ᵀw‖² subject to ‖w‖² = 1
欲求 w，就将 X̂X̂ᵀ实施特徵分解，w 是最小的特徵值的特徵向量。
其中 X̂X̂ᵀ称做维度的共变异矩阵，又刚好是每笔数据的二次动差矩阵的总和。

另外提供二维数据的公式解。

http://mathworld.wolfram.com/LeastSquaresFittingPerpendicularOffsets.html

Polynomial Regression

Polynomial Regression

“多项式迴归”。迴归函数採用多项式函数。误差採用平方误差。

演算法仍是 Normal Equation。

例如用函数 f(x) = ax + b
符合数据 (2,3) (5,6) (7,8)
[ 2  1 ] [ a ]   [ 3 ]
[ 5  1 ] [ b ] = [ 6 ]
[ 7  1 ]         [ 8 ]

例如用函数 f(x) = ax² + bx + c
符合数据 (2,3) (5,6) (7,8)
[  4  2  1 ] [ a ]   [ 3 ]
[ 25  5  1 ] [ b ] = [ 6 ]
[ 49  7  1 ] [ c ]   [ 8 ]

例如用函数 f(x,y) = ax² + bxy + cy² + dx + ey + f
符合数据 (2,3,4) (5,6,7) (7,8,9)
                         [ a ]
[ 2²  2×3  3²  2  3  1 ] [ b ]   [ 4 ]
[ 5²  5×6  6²  5  6  1 ] [ c ] = [ 7 ]
[ 7²  7×8  8²  7  8  1 ] [ d ]   [ 9 ]
                         [ e ]
                         [ f ]

Underfitting / Overfitting

用单纯的函数去符合複杂的数据们，显然符合的不太完美。

用複杂的函数去符合单纯的数据们，显然事情被搞複杂了。

如果我们不清楚数据的性质，也就无法抉择函数了。那麽，该如何了解数据的性质呢？这属于统计学的范畴，就此打住。

Curve Fitting

Curve Fitting / Surface Fitting

“曲线拟合”与“曲面拟合”。迴归标的採用曲线、曲面。误差採用最短距离（垂直距离）的平方和。

Plot3D[x*x + y*y + x*y + x - y, {x, -2, 2}, {y, -2, 2}, PlotRange -> {-15, 15}, Boxed -> False, Axes -> False, Mesh-> None, ColorFunction -> (ColorData["CherryTones"][Rescale[#3, {-3, 3}]] &) ]

古代有一种做法叫做 Principal Curve。我没有研究。

Isotonic Regression

Isotonic Regression

“保序迴归”。迴归函数採用递增函数。

http://stackoverflow.com/questions/10460861/

採用绝对值误差，时间複杂度 O(NlogN)。

採用平方误差，时间複杂度 O(N)。

迴归函数的前后项差距在一定范围内

http://www.careercup.com/question?id=5207197178920960