深度学习算法原理——Softmax Regression
yyHaker 2018-08-21
一、Logistic回归简介
Logistic回归是解决二分类问题的分类算法。假设有m
m个训练样本{(x
(1)
,y
(1)
),(x
(2)
,y
(2)
),⋯,(x
(m)
,y
(m)
)}
{(x(1),y(1)),(x(2),y(2)),⋯,(x(m),y(m))}，对于Logistic回归，其输入特征为：x
(i)
∈R
n+1
x(i)∈ℜn+1，类标记为：y
(i)
∈{0,1}
y(i)∈{0,1}，假设函数为Sigmoid函数：
h
θ
(x)=1
1+e
−θ
T
x
hθ(x)=11+e−θTx
其中，模型的参数为θ
θ，需要通过最小化损失函数得到，模型的损失函数为：
J(θ)=−1
m
∑
i=1
m
[y
(i)
logh
θ
(x
(i)
)+(1−y
(i)
)log(1−h
θ
(x
(i)
))]
J(θ)=−1m∑i=1m[y(i)loghθ(x(i))+(1−y(i))log(1−hθ(x(i)))]
此时，可以通过梯度下降法对其进行求解，其梯度为：
▽
θ
j
J(θ)=−1
m
∑
m
i=1
[y
(i)
h
θ
(x
(i)
)
⋅▽
θ
j
h
θ
(x
(i)
)+1−y
(i)
1−h
θ
(x
(i)
)
⋅▽
θ
j
(1−h
θ
(x
(i)
))]
=−1
m
∑
m
i=1
[y
(i)
h
θ
(x
(i)
)
⋅▽
θ
j
h
θ
(x
(i)
)−1−y
(i)
1−h
θ
(x
(i)
)
⋅▽
θ
j
h
θ
(x
(i)
)]
=−1
m
∑
m
i=1
[(y
(i)
h
θ
(x
(i)
)
−1−y
(i)
1−h
θ
(x
(i)
)
)⋅▽
θ
j
h
θ
(x
(i)
)]
▽θjJ(θ)=−1m∑i=1m[y(i)hθ(x(i))⋅▽θjhθ(x(i))+1−y(i)1−hθ(x(i))⋅▽θj(1−hθ(x(i)))]=−1m∑i=1m[y(i)hθ(x(i))⋅▽θjhθ(x(i))−1−y(i)1−hθ(x(i))⋅▽θjhθ(x(i))]=−1m∑i=1m[(y(i)hθ(x(i))−1−y(i)1−hθ(x(i)))⋅▽θjhθ(x(i))]
=−1
m
∑
m
i=1
[y
(i)
−h
θ
(x
(i)
)
h
θ
(x
(i)
)(1−h
θ
(x
(i)
))
⋅▽
θ
j
h
θ
(x
(i)
)]
=−1
m
∑
m
i=1
[y
(i)
−h
θ
(x
(i)
)
h
θ
(x
(i)
)(1−h
θ
(x
(i)
))
⋅▽
θ
T
x
(i)
h
θ
(x
(i)
)⋅▽
θ
j
(θ
T
x
(i)
)]
=−1m∑i=1m[y(i)−hθ(x(i))hθ(x(i))(1−hθ(x(i)))⋅▽θjhθ(x(i))]=−1m∑i=1m[y(i)−hθ(x(i))hθ(x(i))(1−hθ(x(i)))⋅▽θTx(i)hθ(x(i))⋅▽θj(θTx(i))]
而：
▽
θ
T
x
(i)
h
θ
(x
(i)
)=h
θ
(x
(i)
)(1−h
θ
(x
(i)
))
▽θTx(i)hθ(x(i))=hθ(x(i))(1−hθ(x(i)))
▽
θ
j
(θ
T
x
(i)
)=x
(i)
j
▽θj(θTx(i))=xj(i)
因此，梯度的公式为：
▽
θ
j
J(θ)=−1
m
∑
i=1
m
[(y
(i)
−h
θ
(x
(i)
))⋅x
(i)
j
]
▽θjJ(θ)=−1m∑i=1m[(y(i)−hθ(x(i)))⋅xj(i)]
根据梯度下降法，得到如下的更新公式：
θ
j
:=θ
j
−α▽
θ
j
J(θ)
θj:=θj−α▽θjJ(θ)
二、Softmax回归
2.1、Softmax回归简介
Softmax是Logistic回归在多分类上的推广，即类标签y
y的取值大于等于2
2。假设有m
m个训练样本{(x
(1)
,y
(1)
),(x
(2)
,y
(2)
),⋯,(x
(m)
,y
(m)
)}
{(x(1),y(1)),(x(2),y(2)),⋯,(x(m),y(m))}，对于Softmax回归，其输入特征为：x
(i)
∈R
n+1
x(i)∈ℜn+1，类标记为：y
(i)
∈{0,1,⋯k}
y(i)∈{0,1,⋯k}。假设函数为对于每一个样本估计其所属的类别的概率p(y=j∣x)
p(y=j∣x)，具体的假设函数为：
h
θ
(x
(i)
)=⎡
⎣
⎢
⎢
⎢
⎢
⎢
⎢
p(y
(i)
=1∣x
(i)
;θ)
p(y
(i)
=2∣x
(i)
;θ)
⋮
p(y
(i)
=k∣x
(i)
;θ)
⎤
⎦
⎥
⎥
⎥
⎥
⎥
⎥
=1
∑
k
j=1
e
θ
T
j
x
(i)
⎡
⎣
⎢
⎢
⎢
⎢
⎢
e
θ
T
1
x
(i)
e
θ
T
2
x
(i)
⋮
e
θ
T
k
x
(i)
⎤
⎦
⎥
⎥
⎥
⎥
⎥
hθ(x(i))=[p(y(i)=1∣x(i);θ)p(y(i)=2∣x(i);θ)⋮p(y(i)=k∣x(i);θ)]=1∑j=1keθjTx(i)[eθ1Tx(i)eθ2Tx(i)⋮eθkTx(i)]
其中θ
θ表示的向量，且θ
i
∈R
n+1
θi∈ℜn+1。则对于每一个样本估计其所属的类别的概率为：
p(y
(i)
=j∣x
(i)
;θ)=e
θ
T
j
x
(i)
∑
k
l=1
e
θ
T
l
x
(i)
p(y(i)=j∣x(i);θ)=eθjTx(i)∑l=1keθlTx(i)
2.2、Softmax回归的代价函数
类似于Logistic回归，在Softmax的代价函数中引入指示函数I{⋅}
I{⋅}，其具体形式为：
I{expression}={0
1
if expression=false
if expression=true
I{expression}={0 if expression=false1 if expression=true
那么，对于Softmax回归的代价函数为：
J(θ)=−1
m
[∑
i=1
m
∑
j=1
k
I{y
(i)
=j}loge
θ
T
j
x
(i)
∑
k
l=1
e
θ
T
l
x
(i)
]
J(θ)=−1m[∑i=1m∑j=1kI{y(i)=j}logeθjTx(i)∑l=1keθlTx(i)]
2.3、Softmax回归的求解
对于上述的代价函数，可以使用梯度下降法对其进行求解，首先对其进行求梯度：
▽
θ
j
J(θ)=−1
m
∑
i=1
m
[▽
θ
j
∑
j=1
k
I{y
(i)
=j}loge
θ
T
j
x
(i)
∑
k
l=1
e
θ
T
l
x
(i)
]
▽θjJ(θ)=−1m∑i=1m[▽θj∑j=1kI{y(i)=j}logeθjTx(i)∑l=1keθlTx(i)]
已知，对于一个样本只会属于一个类别：
- 若y
- (i)
- =j
- y(i)=j，则I{y
- (i)
- =j}=1
- I{y(i)=j}=1
▽
θ
j
J(θ)=−1
m
∑
m
i=1
[▽
θ
j
loge
θ
T
j
x
(i)
∑
k
l=1
e
θ
T
l
x
(i)
]
=−1
m
∑
m
i=1
⎡
⎣
⎢
∑
k
l=1
e
θ
T
l
x
(i)
e
θ
T
j
x
(i)
⋅e
θ
T
j
x
(i)
⋅x
(i)
⋅∑
k
l=1
e
θ
T
l
x
(i)
−e
θ
T
j
x
(i)
⋅x
(i)
⋅e
θ
T
j
x
(i)
(∑
k
l=1
e
θ
T
l
x
(i)
)
2
⎤
⎦
⎥
=−1
m
∑
m
i=1
[∑
k
l=1
e
θ
T
l
x
(i)
−e
θ
T
j
x
(i)
∑
k
l=1
e
θ
T
l
x
(i)
⋅x
(i)
]
▽θjJ(θ)=−1m∑i=1m[▽θjlogeθjTx(i)∑l=1keθlTx(i)]=−1m∑i=1m[∑l=1keθlTx(i)eθjTx(i)⋅eθjTx(i)⋅x(i)⋅∑l=1keθlTx(i)−eθjTx(i)⋅x(i)⋅eθjTx(i)(∑l=1keθlTx(i))2]=−1m∑i=1m[∑l=1keθlTx(i)−eθjTx(i)∑l=1keθlTx(i)⋅x(i)]
- 若y
- (i)
- ≠j
- y(i)≠j，假设y
- (i)
- ≠j
- ′
- y(i)≠j′，则I{y
- (i)
- =j}=0
- I{y(i)=j}=0，I{y
- (i)
- =j
- ′
- }=1
- I{y(i)=j′}=1
▽
θ
j
J(θ)=−1
m
∑
m
i=1
[▽
θ
j
loge
θ
T
j
′
x
(i)
∑
k
l=1
e
θ
T
l
x
(i)
]
=−1
m
∑
m
i=1
⎡
⎣
⎢
∑
k
l=1
e
θ
T
l
x
(i)
e
θ
T
j
′
x
(i)
⋅−e
θ
T
j
′
x
(i)
⋅x
(i)
⋅e
θ
T
j
x
(i)
(∑
k
l=1
e
θ
T
l
x
(i)
)
2
⎤
⎦
⎥
=−1
m
∑
m
i=1
[−e
θ
T
j
x
(i)
∑
k
l=1
e
θ
T
l
x
(i)
⋅x
(i)
]
▽θjJ(θ)=−1m∑i=1m[▽θjlogeθj′Tx(i)∑l=1keθlTx(i)]=−1m∑i=1m[∑l=1keθlTx(i)eθj′Tx(i)⋅−eθj′Tx(i)⋅x(i)⋅eθjTx(i)(∑l=1keθlTx(i))2]=−1m∑i=1m[−eθjTx(i)∑l=1keθlTx(i)⋅x(i)]
最终的结果为：
−1
m
∑
i=1
m
[x
(i)
(I{y
(i)
=j}−p(y
(i)
=j∣x
(i)
;θ))]
−1m∑i=1m[x(i)(I{y(i)=j}−p(y(i)=j∣x(i);θ))]
注意，此处的θ
j
θj表示的是一个向量。通过梯度下降法的公式可以更新：
θ
j
:=θ
j
−α▽
θ
j
J(θ)
θj:=θj−α▽θjJ(θ)
5、Softmax回归中的参数特点
在Softmax回归中存在着参数冗余的问题。简单来讲就是参数中有些参数是没有任何用的，为了证明这点，假设从参数向量θ
j
θj中减去向量ψ
ψ，假设函数为：
p(y
(i)
=j∣x
(i)
;θ)=e
(θ
j
−ψ)
T
x
(i)
∑
k
l=1
e
(θ
l
−ψ)
T
x
(i)
=e
θ
T
j
x
(i)
⋅e
−ψ
T
x
(i)
∑
k
l=1
e
θ
T
l
x
(i)
⋅e
−ψ
T
x
(i)
=e
θ
T
j
x
(i)
∑
k
l=1
e
θ
T
l
x
(i)
p(y(i)=j∣x(i);θ)=e(θj−ψ)Tx(i)∑l=1ke(θl−ψ)Tx(i)=eθjTx(i)⋅e−ψTx(i)∑l=1keθlTx(i)⋅e−ψTx(i)=eθjTx(i)∑l=1keθlTx(i)
从上面可以看出从参数向量θ
j
θj中减去向量ψ
ψ对预测结果并没有任何的影响，也就是说在模型中，存在着多组的最优解。
为了是算法能够尽可能简单，保留所有的参数，但是对代价函数加入权重衰减来解决参数冗余的问题，权重衰减即对参数进行正则化。
如对参数进行L2正则约束，L2正则为：
λ
2
∑
i=1
k
∑
j=0
n
θ
2
ij
λ2∑i=1k∑j=0nθij2
此时，代价函数为：
J(θ)=−1
m
[∑
i=1
m
∑
j=1
k
I{y
(i)
=j}loge
θ
T
j
x
(i)
∑
k
l=1
e
θ
T
l
x
(i)
]+λ
2
∑
i=1
k
∑
j=0
n
θ
2
ij
J(θ)=−1m[∑i=1m∑j=1kI{y(i)=j}logeθjTx(i)∑l=1keθlTx(i)]+λ2∑i=1k∑j=0nθij2
其中，λ>0
λ>0，此时代价函数是一个严格的凸函数。
对该函数的导数为：
▽θ
j
J(θ)=−1
m
∑
i=1
m
[x
(i)
(I{y
(i)
=j}−p(y
(i)
=j∣x
(i)
;θ))]+λθ
j
▽θjJ(θ)=−1m∑i=1m[x(i)(I{y(i)=j}−p(y(i)=j∣x(i);θ))]+λθj
5、Softmax与Logistic回归的关系
Logistic回归算法是Softmax回归的特征情况，即k=2
k=2时的情况，当
k=2
k=2时，Softmax回归为：
h
θ
(x)=1
e
θ
T
1
x
+e
θ
T
2
x
[e
θ
T
1
x
e
θ
T
2
x
]
hθ(x)=1eθ1Tx+eθ2Tx[eθ1Txeθ2Tx]
利用Softmax回归参数冗余的特点，令ψ=θ
1
ψ=θ1，从两个向量中都减去这个向量，得到：
h
θ
(x)=1
e
(θ
1
−ψ)
T
x
+e
(θ
2
−ψ)
T
x
[e
(θ
1
−ψ)
T
x
e
(θ
2
−ψ)
T
x
]
=⎡
⎣
⎢
1
1+e
(θ
2
−θ
1
)
T
x
e
(θ
2
−θ
1
)
T
x
1+e
(θ
2
−θ
1
)
T
x
⎤
⎦
⎥
=⎡
⎣
⎢
1
1+e
(θ
2
−θ
1
)
T
x
1−1
1+e
(θ
2
−θ
1
)
T
x
⎤
⎦
⎥
hθ(x)=1e(θ1−ψ)Tx+e(θ2−ψ)Tx[e(θ1−ψ)Txe(θ2−ψ)Tx]=[11+e(θ2−θ1)Txe(θ2−θ1)Tx1+e(θ2−θ1)Tx]=[11+e(θ2−θ1)Tx1−11+e(θ2−θ1)Tx]
上述的表达形式与Logistic回归是一致的。
6、多分类算法和二分类算法的选择
有人会觉得对于一个多分类问题，可以使用多个二分类来完成，对于多分类问题是直接选择多分类的分类器还是选择多个二分类的分类器进行叠加，在UFLDL中，作者给出了这样的解释：取决于类别之间是否互斥。
对于一个多分类的问题，是直接选择多分类器直接计算还是选择多个二分类器进行计算取决于问题中类别之间是否互斥。
- 是互斥的 –> Softmax回归
- 不是互斥的 –> 多个独立的Logistic回归
