3.1 基本形式
线性模型（linear model）试图学得一个通过属性的线性组合来进行预测的函数，即：
f
(
x
i
)
=
w
1
x
1
+
.
.
.
w
d
x
d
+
b
f(x_i)=w_1x_1+...w_dx_d+b
f(xi)=w1x1+...wdxd+b
线性模型的优势：形式简单、易于建模、可解释性好（通过w直观地表达了各属性在预测中的重要性）
从线性模型到非线性模型可以通过引入层级结构/高维映射的方式来实现
3.2 线性回归（最小二乘法）
给定数据集:
D
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
.
.
.
(
x
m
,
y
m
)
}
其
中
x
i
=
(
x
i
1
,
x
i
2
,
.
.
.
x
i
d
)
,
y
i
∈
R
D=\left\{(x_1,y_1),(x_2,y_2),...(x_m,y_m)\right\} 其中x_i=(x_{i1},x_{i2},...x_{id}) ,y_i∈R
D={(x1,y1),(x2,y2),...(xm,ym)}其中xi=(xi1,xi2,...xid),yi∈R
线性回归试图学得一个模型准确地预测实值输出标记，即：
f
(
x
i
)
=
w
T
x
i
+
b
≈
y
i
f(x_i)=w^Tx_i+b\approx{y_i}
f(xi)=wTxi+b≈yi
3.2.1 输出属性为1个
为方便讨论，先忽略属性下标，即xi表示第i个样例的第一个属性值（唯一一个属性值），对于离散属性，若属性间存在“序”关系，则通过连续化将其转化为连续值（例如高矮转化为{1.0，0.0}），若不存在序关系，若存在k个属性值，则转化为k维向量（例如属性瓜类中“西瓜”“南瓜”“黄瓜”转化为(1,0,0)(0,1,0)(0,0,1)
线性回归中常用的性能度量为均方误差（MSE），于是我们学习的目标即为使得均方误差最小化。（但一味的选择最小会引入过拟合，需要引入正则项，暂时先不考虑）
于是：
(
w
∗
,
b
∗
)
=
a
r
g
m
i
n
∑
i
=
1
m
(
f
(
x
i
)
−
y
i
)
2
=
a
r
g
m
i
n
∑
i
=
1
m
(
y
i
−
w
x
i
−
b
)
2
(w^*,b^*) = argmin\sum_{i=1}^m\ (f(x_i)-y_i)^2 =argmin\sum_{i=1}^m\ (y_i-wx_i-b)^2
(w∗,b∗)=argmini=1∑m (f(xi)−yi)2=argmini=1∑m (yi−wxi−b)2
基于均方误差最小化进行模型求解的方法称为“最小二乘法”
求解(w,b)使MSE最小的过程称为线性回归模型的最小二乘参数估计
将
E
(
w
,
b
)
=
∑
i
=
1
(
y
i
−
w
x
i
−
b
)
2
对
参
数
w
，
b
求
导
将 E(w,b) = \sum_{i=1}^\ (y_i-wx_i-b)^2 对参数w，b求导
将E(w,b)=i=1∑ (yi−wxi−b)2对参数w，b求导
于是可以得到w和b的最优解的闭式解
w
=
∑
i
=
1
m
y
i
(
x
i
−
x
ˉ
)
∑
i
=
1
m
x
i
2
−
1
m
(
∑
i
=
1
m
x
i
2
)
2
w=\frac{\sum_{i=1}^m\ y_i(x_i-\bar{x}) }{\sum_{i=1}^m x_i^2 -\frac{1}{m}(\sum_{i=1}^m x_i^2)^2}
w=∑i=1mxi2−m1(∑i=1mxi2)2∑i=1m yi(xi−xˉ)
b
=
1
m
∑
i
=
1
m
(
y
i
−
w
x
i
)
b=\frac{1}{m}\sum_{i=1}^m (y_i-wx_i)
b=m1i=1∑m(yi−wxi)
3.2.2 输入属性为多个
当样本由d个属性描述，此时我们的学习目标为：
f
(
x
i
)
=
w
T
x
i
+
b
≈
y
i
f(x_i)=w^Tx_i+b\approx{y_i}
f(xi)=wTxi+b≈yi
为便于讨论，我们作如下标记：
记
w
^
=
(
w
;
b
)
,
记\hat{w}=(w;b),
记w^=(w;b),
X
=
[
x
11
x
12
.
.
.
x
1
d
1
x
21
x
22
.
.
.
x
2
d
1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
x
m
1
x
m
2
.
.
.
x
m
d
1
]
=
[
x
1
T
1
x
2
T
1
.
.
.
.
.
.
x
m
T
1
]
X=\left[ \begin{matrix} x_{11} & x_{12} & ...&x_{1d}&1 \\ x_{21} & x_{22} & ...&x_{2d}&1 \\ ... & ... & ...&...&... \\ x_{m1} & x_{m2} & ...&x_{md}&1 \end{matrix} \right] = \left[ \begin{matrix} x_1^T&1 \\ x_2^T&1 \\ ... & ...\\ x_m^T&1 \end{matrix} \right]
X=⎣⎢⎢⎡x11x21...xm1x12x22...xm2............x1dx2d...xmd11...1⎦⎥⎥⎤=⎣⎢⎢⎡x1Tx2T...xmT11...1⎦⎥⎥⎤
y
=
(
y
1
,
y
2
,
.
.
.
,
y
m
)
y=(y_1,y_2,...,y_m)
y=(y1,y2,...,ym)
则最优化问题转化为：
w
^
∗
=
a
r
g
min
w
^
(
y
−
X
w
^
)
T
(
y
−
X
w
^
)
\hat{w}^*=arg\min_{\hat{w}}(y-X\hat{w})^T(y-X\hat{w})
w^∗=argminw^(y−Xw^)T(y−Xw^)
令
E
w
^
=
(
y
−
X
w
^
)
T
(
y
−
X
w
^
)
,
对
w
^
求
导
得
：
令E_{\hat{w}}=(y-X\hat{w})^T(y-X\hat{w}),对\hat{w}求导得：
令Ew^=(y−Xw^)T(y−Xw^),对w^求导得：
X
T
X
满
秩
：
w
^
∗
=
(
X
T
X
)
−
1
X
T
y
X^TX满秩：\hat{w}^*=(X^TX)^{-1}X^Ty
XTX满秩：w^∗=(XTX)−1XTy
此时线性回归模型为：
f
(
x
i
)
=
x
i
^
T
(
X
T
X
)
−
1
X
T
y
f(x_i)=\hat{x_i}^T(X^TX)^{-1}X^Ty
f(xi)=xi^T(XTX)−1XTy
若
X
T
X
X^TX
XTX不满秩，则有多个解，选择解的问题即为归纳偏好的问题（参见第一章），常用做法为引入正则项。
3.2.3 线性模型的衍生物
线性模型不一定逼近y的真实值，可以是真实值的衍生物，例如对数：
y
=
w
T
+
b
−
−
>
l
n
y
=
w
T
+
b
y=w^T+b -->lny=w^T+b
y=wT+b−−>lny=wT+b
这就是对数线性回归，即试图让
e
w
T
x
+
b
e^{w^Tx+b}
ewTx+b逼近y
更一般的，考虑单调可微函数
g
(
.
)
g(.)
g(.)
令
y
=
g
−
1
(
w
T
x
+
b
)
y=g^{-1}(w^Tx+b)
y=g−1(wTx+b)
这样的模型称为广义线性模型，
g
(
.
)
g(.)
g(.)称为联系函数
3.3 对数几率回归(logistic regression）（极大似然法）
考虑二分类任务，其输出标记
y
∈
{
0
,
1
}
y∈\left\{0,1\right\}
y∈{0,1}而线性回归返回的预测值z为实值，我们需要将其与y对应，最理想的函数为单位阶跃函数
y
=
{
0
,
z
<
0
;
0.5
,
z
=
0
;
1
,
z
>
0
y=\left\{ \begin{aligned} 0,z<0; \\ 0.5,z=0; \\ 1,z>0 \end{aligned} \right.
y=⎩⎪⎨⎪⎧0,z<0;0.5,z=0;1,z>0
但由于单位阶跃函数不连续，所以不能直接作为联系函数，于是我们需要找到函数近似单位阶跃函数。
对数几率函数就是这样的函数
y
=
1
1
+
e
−
z
y=\frac{1}{1+e^{-z}}
y=1+e−z1
如图所示：
于是可得：
y
=
1
1
+
e
−
(
w
T
x
+
b
)
y=\frac{1}{1+e^{-(w^Tx+b)}}
y=1+e−(wTx+b)1
即：
l
n
y
1
−
y
=
w
T
x
+
b
ln\frac{y}{1-y}=w^Tx+b
ln1−yy=wTx+b
若将y视为样本取正例的可能性，则1-y为样本取负例的可能性，两者的比值：
y
1
−
y
\frac{y}{1-y}
1−yy称为几率（odds)，几率取对数得：
l
n
y
1
−
y
ln\frac{y}{1-y}
ln1−yy称为对数几率（log odds/logit)
注：对数几率回归是一种分类学习方法，模型学得的即为近似概率预测此外，对率函数是任意阶可导的凸函数，有很好的数学性质，可以用数值优化算法直接求解最优解。
3.3.1 最优解的推导（极大似然法）
下推导如何确定式：
l
n
y
1
−
y
=
w
T
x
+
b
ln\frac{y}{1-y}=w^Tx+b
ln1−yy=wTx+b 中w和b的值
将y视为类后验概率估计
p
(
y
=
1
∣
x
)
p(y=1|x)
p(y=1∣x),则原式变为：
l
n
p
(
y
=
1
∣
x
)
p
(
y
=
0
∣
x
)
=
w
T
x
+
b
ln\frac{p(y=1|x)}{p(y=0|x)}=w^Tx+b
lnp(y=0∣x)p(y=1∣x)=wTx+b
显然有：
p
(
y
=
1
∣
x
)
=
e
w
T
x
+
b
1
+
e
w
T
x
+
b
p(y=1|x)=\frac{e^{w^Tx+b}}{1+e^{w^Tx+b}}
p(y=1∣x)=1+ewTx+bewTx+b
p
(
y
=
0
∣
x
)
=
1
1
+
e
w
T
x
+
b
p(y=0|x)=\frac{1}{1+e^{w^Tx+b}}
p(y=0∣x)=1+ewTx+b1
通过极大似然法来估计w和b，则对于数据集
{
(
x
i
,
y
i
)
}
i
=
1
m
\left\{(x_i,y_i)\right\}_{i=1}^m
{(xi,yi)}i=1m 对数回归模型最大化对数似然
l
(
w
,
b
)
=
∑
i
=
1
m
l
n
p
(
y
i
∣
x
i
;
w
,
b
)
l(w,b)=\sum_{i=1}^mln p(y_i|x_i;w,b)
l(w,b)=∑i=1mlnp(yi∣xi;w,b)
令
β
=
(
w
;
b
)
,
x
^
=
(
x
;
1
)
,
则
w
T
x
+
b
=
β
T
x
^
\beta=(w;b),\hat{x}=(x;1),则w^Tx+b=\beta^T\hat{x}
β=(w;b),x^=(x;1),则wTx+b=βTx^
再令
p
1
(
x
^
;
β
)
=
p
(
y
=
1
∣
x
;
β
)
p_1(\hat{x};\beta)=p(y=1|x;\beta)
p1(x^;β)=p(y=1∣x;β)
p
0
(
x
^
;
β
)
=
p
(
y
=
0
∣
x
;
β
)
p_0(\hat{x};\beta)=p(y=0|x;\beta)
p0(x^;β)=p(y=0∣x;β)
带入对数似然得
l
(
w
,
b
)
=
∑
i
=
1
m
(
y
i
β
T
x
^
i
−
l
n
(
1
+
e
β
T
x
^
i
)
)
l(w,b)=\sum_{i=1}^m (y_i\beta^T\hat{x}_i-ln(1+e^{\beta^T\hat{x}_i}))
l(w,b)=∑i=1m(yiβTx^i−ln(1+eβTx^i))
所以最大化l(w,b)等价于最小化
l
(
β
)
=
∑
i
=
1
m
(
−
y
i
β
T
x
^
i
+
l
n
(
1
+
e
β
T
x
^
i
)
)
l(\beta)=\sum_{i=1}^m (-y_i\beta^T\hat{x}_i+ln(1+e^{\beta^T\hat{x}_i}))
l(β)=∑i=1m(−yiβTx^i+ln(1+eβTx^i))
#########推导如下：
l
(
β
)
=
∑
i
=
1
m
(
−
y
i
β
T
x
^
i
+
l
n
(
1
+
e
β
T
x
^
i
)
)
l(\beta)=\sum_{i=1}^m (-y_i\beta^T\hat{x}_i+ln(1+e^{\beta^T\hat{x}_i}))
l(β)=∑i=1m(−yiβTx^i+ln(1+eβTx^i))是关于
β
\beta
β的高阶可导连续凸函数，根据凸优化理论可用经典优化算法如梯度下降法、牛顿法求得其最优解。
3.4 线性判别分析 LDA
LDA的思想：给定训练样例集，将其投影到一条直线上，使得同类样例投影点尽可能近，异类样例投影点尽可能远，对新样本的分类时，先将其投影到这条直线上，再根据投影点的位置来确定新样本的类别，如图所示：
二分类LDA
给定数据集：
D
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
.
.
.
(
x
m
,
y
m
)
}
D=\left\{(x_1,y_1),(x_2,y_2),...(x_m,y_m)\right\}
D={(x1,y1),(x2,y2),...(xm,ym)}
y
i
∈
{
0
,
1
}
y_i∈\left\{0,1\right\}
yi∈{0,1}令
X
i
,
μ
i
,
∑
i
X_i,\mu_i,\sum_{i}
Xi,μi,∑i表示第i类示例的集合、均值向量、协方差矩阵，将数据投影到直线
w
w
w上，则两类样本的中心在直线上的投影为
w
T
μ
0
,
w
T
μ
1
w^T\mu_0,w^T\mu_1
wTμ0,wTμ1,两类样本的协方差在投影到直线上后分别为
w
T
∑
0
w
,
w
T
∑
1
w
w^T\sum_{0}w,w^T\sum_{1}w
wT∑0w,wT∑1w
易得：
w
T
μ
0
,
w
T
μ
1
,
w
T
∑
0
w
,
w
T
∑
1
w
w^T\mu_0,w^T\mu_1,w^T\sum_{0}w,w^T\sum_{1}w
wTμ0,wTμ1,wT∑0w,wT∑1w 均为常数
#######推导如下：
根据LDA的思想，如何定义同类之间距离近、类间距离远，有许多种不同的做法。比较常用的即使同类协方差尽可能小，即
w
T
∑
0
w
+
w
T
∑
1
w
w^T\sum_{0}w+w^T\sum_{1}w
wT∑0w+wT∑1w尽可能小，而类中心之间距离尽可能大（这里用欧氏距离来进行度量）即
∣
∣
w
T
μ
0
−
w
T
μ
1
∣
∣
2
2
||w^T\mu_0-w^T\mu_1||_2^2
∣∣wTμ0−wTμ1∣∣22尽可能大，同时考虑两者，则得到最大化目标：
J
=
∣
∣
w
T
μ
0
−
w
T
μ
1
∣
∣
2
2
w
T
∑
0
w
+
w
T
∑
1
w
=
w
T
(
μ
0
−
μ
1
)
(
μ
0
−
μ
1
)
T
w
w
T
(
∑
0
+
∑
1
)
w
J=\frac{||w^T\mu_0-w^T\mu_1||_2^2}{w^T\sum_{0}w+w^T\sum_{1}w} =\frac{w^T(\mu_0-\mu_1)(\mu_0-\mu_1)^Tw}{w^T(\sum_{0}+\sum_{1})w}
J=wT∑0w+wT∑1w∣∣wTμ0−wTμ1∣∣22=wT(∑0+∑1)wwT(μ0−μ1)(μ0−μ1)Tw
定义类内散度矩阵：
S
w
=
∑
0
+
∑
1
=
∑
x
∈
X
0
(
x
−
μ
0
)
(
x
−
μ
0
)
T
+
∑
x
∈
X
1
(
x
−
μ
1
)
(
x
−
μ
1
)
T
S_w=\sum_{0}+\sum_{1}=\sum_{x∈X_0}(x-\mu_0)(x-\mu_0)^T+\sum_{x∈X_1}(x-\mu_1)(x-\mu_1)^T
Sw=∑0+∑1=∑x∈X0(x−μ0)(x−μ0)T+∑x∈X1(x−μ1)(x−μ1)T
类间散度矩阵：
S
b
=
(
μ
0
−
μ
1
)
(
μ
0
−
μ
1
)
T
S_b=(\mu_0-\mu_1)(\mu_0-\mu_1)^T
Sb=(μ0−μ1)(μ0−μ1)T
则有：
J
=
w
T
S
b
w
w
T
S
w
w
J=\frac{w^TS_bw}{w^TS_ww}
J=wTSwwwTSbw
J称为：广义瑞利商，即LDA最大化的目标
由于J分子分母都是w的二次方，所以J的大小与ｗ的长度无关，不失一般性，令
w
T
S
w
w
=
1
w^TS_ww=1
wTSww=1则最大化瑞利商等价于最优化问题：
min
w
−
w
T
S
b
w
s
.
t
.
w
T
S
w
w
=
1
\min_w -w^TS_bw \\ s.t.w^TS_ww=1
wmin−wTSbws.t.wTSww=1
运用拉格朗日乘子法 上式等价于：
S
b
w
=
λ
S
w
w
S_bw=\lambda S_ww
Sbw=λSww
注意到
S
b
w
S_bw
Sbw方向为
μ
0
−
μ
1
\mu_0-\mu_1
μ0−μ1
(
S
b
w
=
(
μ
0
−
μ
1
)
(
μ
0
−
μ
1
)
T
w
=
(
(
μ
0
−
μ
1
)
T
w
)
(
μ
0
−
μ
1
)
=
λ
(
μ
0
−
μ
1
)
S_bw=(\mu_0-\mu_1)(\mu_0-\mu_1)^Tw\\=((\mu_0-\mu_1)^Tw)(\mu_0-\mu_1)=\lambda (\mu_0-\mu_1)
Sbw=(μ0−μ1)(μ0−μ1)Tw=((μ0−μ1)Tw)(μ0−μ1)=λ(μ0−μ1)由于最后的结果我们只需要算出来
w
w
w的方向，所以我们可以适当的改变
S
b
w
S_bw
Sbw大小，使其满足该式。
所以
λ
(
μ
0
−
μ
1
)
=
λ
S
w
w
\lambda (\mu_0-\mu_1)=\lambda S_ww
λ(μ0−μ1)=λSww
w
=
S
w
−
1
(
μ
0
−
μ
1
)
w=S_w^{-1}(\mu_0-\mu_1)
w=Sw−1(μ0−μ1)
这里
S
w
−
1
S_w^{-1}
Sw−1一般通过奇异值分解：
S
w
=
U
∑
V
T
S_w=U\sum V^T
Sw=U∑VT,
∑
\sum
∑为实对称矩阵，U,V为单位正交矩阵（
U
T
U
=
I
,
V
T
V
=
I
U^TU=I,V^TV=I
UTU=I,VTV=I）
于是
S
w
−
1
=
V
∑
−
1
U
T
S_w^{-1}=V\sum^{-1}U^T
Sw−1=V∑−1UT
推广LDA 多分类任务
定义全局散度矩阵：
S
t
=
S
b
+
S
w
=
∑
i
=
1
m
(
x
i
−
μ
)
(
x
i
−
μ
)
T
S_t=S_b+S_w=\sum_{i=1}^m(x_i-\mu)(x_i-\mu)^T
St=Sb+Sw=∑i=1m(xi−μ)(xi−μ)T
μ
\mu
μ为所有示例的均值向量
类内散度矩阵为每个类别散度矩阵之和：
S
w
=
∑
i
=
1
N
S
w
i
,
S
w
i
=
∑
x
∈
X
i
(
x
−
μ
i
)
(
x
−
μ
i
)
T
S_w=\sum_{i=1}^NS_{w_i} ,S_{w_i}=\sum_{x∈X_i}(x-\mu_i)(x-\mu_i)^T
Sw=∑i=1NSwi,Swi=∑x∈Xi(x−μi)(x−μi)T
由
S
t
,
S
w
S_t,S_w
St,Sw有
S
b
=
S
t
−
S
w
=
∑
i
=
1
N
m
i
(
μ
i
−
μ
)
(
μ
i
−
μ
)
T
S_b=S_t-S_w=\sum_{i=1}^N m_i(\mu_i-\mu)(\mu_i-\mu)^T
Sb=St−Sw=∑i=1Nmi(μi−μ)(μi−μ)T
同样的可以对学习目标有许多选择，常见选择：
max
W
t
r
(
W
T
S
b
W
)
t
r
(
W
T
S
w
W
)
\max_W\frac{tr(W^TS_bW)}{tr(W^TS_wW)}
Wmaxtr(WTSwW)tr(WTSbW)
3.5 多分类学习
多分类问题可以利用二分类学习器来解决，即将多分类任务拆为若干个二分类任务求解。
常见拆分策略：“一对一OvO”“一对其余OvR”“多对多MvM”
3.5.1 OvO and OvR
OvO：给定数据集
D
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
.
.
.
(
x
m
,
y
m
)
}
y
i
∈
{
C
1
,
C
2
,
.
.
.
C
m
}
)
D=\left\{(x_1,y_1),(x_2,y_2),...(x_m,y_m)\right\} \\y_i∈\left\{C_1,C_2,...C_m\right\})
D={(x1,y1),(x2,y2),...(xm,ym)}yi∈{C1,C2,...Cm})
将N个类别两两配对，从而产生
N
(
N
−
1
)
2
\frac{N(N-1)}{2}
2N(N−1)个二分类任务
OvR：每次将一个类作为正例，其他类作为反例，若有多个分类器预测为正类，则考虑预测置信度。
比较：OvO需要
N
(
N
−
1
)
2
\frac{N(N-1)}{2}
2N(N−1)个分类器，而OvR只需要N个
但是OvO每个分类器用到两个类的样例，而OvR需要所有样例。
3.5.2 MvM
MvM 是每次将若干个类作为正类，若干个其他类作为反类，选择必须有特殊的设计。常用的MvM：纠错输入码 ECOC
工作原理如图所示：
二元码将类别分为正类和反类，三元码则增加一个停用类。
对于同一个学习任务，ECOC编码越长，纠错能力越强，但是也意味着计算、存储开销增大。而且对于有限类别，组合数目有限，码长超过一定范围就失去意义。
对同等长度编码，任意两个类别距离越远，纠错能力越强。
3.6 类别不平衡问题
当分类任务中不同类别的训练样例数目差别很大时，会出现类别不平衡问题。（假定正例较少）
常用处理手段：三种做法：1、对反例进行欠采样，即去除一些反例使之与正例数目接近。2、过采样，增加一些正例个数（不可直接重复样本 会导致过拟合）3、阙值移动：
y
1
−
y
>
1
−
−
>
y
1
−
y
>
m
+
m
−
\frac{y}{1-y}>1-->\frac{y}{1-y}> \frac{m_+}{m_-}
1−yy>1−−>1−yy>m−m+ 这是一种处理类别不平衡学习的基本策略：再缩放，其中
m
+
,
m
−
m_+,m_-
m+,m−分别表示正例、反例个数。