一、Logistic回归简介
Logistic回归是解决二分类问题的分类算法。假设有mmm个训练样本{(x(1),y(1)),(x(2),y(2)),⋯,(x(m),y(m))}{(x(1),y(1)),(x(2),y(2)),⋯,(x(m),y(m))}left { left ( mathbf{x}^{(1)},y^{(1)} right ),left ( mathbf{x}^{(2)},y^{(2)} right ),cdots ,left ( mathbf{x}^{(m)},y^{(m)} right ) right }，对于Logistic回归，其输入特征为：x(i)∈ℜn 1x(i)∈ℜn 1mathbf{x}^{(i)}in Re ^{n 1}，类标记为：y(i)∈{0,1}y(i)∈{0,1}y^{(i)}in left { 0,1 right }，假设函数为Sigmoid函数：
hθ(x)=11 e−θTxhθ(x)=11 e−θTx
h_theta left ( x right )=frac{1}{1 e^{-theta ^Tx}}
其中，模型的参数为θθtheta ，需要通过最小化损失函数得到，模型的损失函数为：
J(θ)=−1m∑i=1my(i)loghθ(x(i)) (1−y(i))log(1−hθ(x(i)))J(θ)=−1m∑i=1my(i)loghθ(x(i)) (1−y(i))log(1−hθ(x(i)))
Jleft ( theta right )=-frac{1}{m}sum_{i=1}^{m}left y^{(i)}logh_theta left ( mathbf{x}^{(i)} right ) left ( 1-y^{(i)} right )logleft ( 1-h_theta left ( mathbf{x}^{(i)} right ) right ) right
此时，可以通过梯度下降法对其进行求解，其梯度为：
▿θjJ(θ)=−1m∑mi=1y(i)hθ(x(i))⋅▿θjhθ(x(i)) 1−y(i)1−hθ(x(i))⋅▿θj(1−hθ(x(i)))=−1m∑mi=1y(i)hθ(x(i))⋅▿θjhθ(x(i))−1−y(i)1−hθ(x(i))⋅▿θjhθ(x(i))=−1m∑mi=1(y(i)hθ(x(i))−1−y(i)1−hθ(x(i)))⋅▿θjhθ(x(i))▽θjJ(θ)=−1m∑i=1my(i)hθ(x(i))⋅▽θjhθ(x(i)) 1−y(i)1−hθ(x(i))⋅▽θj(1−hθ(x(i)))=−1m∑i=1my(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))
begin{matrix} triangledown _{theta _j}Jleft ( theta right )=-frac{1}{m}sum_{i=1}^{m}left frac{y^{(i)}}{h_theta left ( mathbf{x}^{(i)} right )}cdot triangledown _{theta _j}h_theta left ( mathbf{x}^{(i)} right ) frac{1-y^{(i)}}{1-h_theta left ( mathbf{x}^{(i)} right )}cdot triangledown _{theta _j}left ( 1-h_theta left ( mathbf{x}^{(i)} right ) right )right =-frac{1}{m}sum_{i=1}^{m}left frac{y^{(i)}}{h_theta left ( mathbf{x}^{(i)} right )}cdot triangledown _{theta _j}h_theta left ( mathbf{x}^{(i)} right )-frac{1-y^{(i)}}{1-h_theta left ( mathbf{x}^{(i)} right )}cdot triangledown _{theta _j}h_theta left ( mathbf{x}^{(i)} right ) right =-frac{1}{m}sum_{i=1}^{m}left left ( frac{y^{(i)}}{h_theta left ( mathbf{x}^{(i)} right )}-frac{1-y^{(i)}}{1-h_theta left ( mathbf{x}^{(i)} right )} right )cdot triangledown _{theta _j}h_theta left ( mathbf{x}^{(i)} right ) right end{matrix}
=−1m∑mi=1y(i)−hθ(x(i))hθ(x(i))(1−hθ(x(i)))⋅▿θjhθ(x(i))=−1m∑mi=1y(i)−hθ(x(i))hθ(x(i))(1−hθ(x(i)))⋅▿θTx(i)hθ(x(i))⋅▿θj(θTx(i))=−1m∑i=1my(i)−hθ(x(i))hθ(x(i))(1−hθ(x(i)))⋅▽θjhθ(x(i))=−1m∑i=1my(i)−hθ(x(i))hθ(x(i))(1−hθ(x(i)))⋅▽θTx(i)hθ(x(i))⋅▽θj(θTx(i))
begin{matrix} =-frac{1}{m}sum_{i=1}^{m}left frac{y^{(i)}-h_theta left ( mathbf{x}^{(i)} right )}{h_theta left ( mathbf{x}^{(i)} right )left ( 1-h_theta left ( mathbf{x}^{(i)} right ) right )}cdot triangledown _{theta _j}h_theta left ( mathbf{x}^{(i)} right ) right =-frac{1}{m}sum_{i=1}^{m}left frac{y^{(i)}-h_theta left ( mathbf{x}^{(i)} right )}{h_theta left ( mathbf{x}^{(i)} right )left ( 1-h_theta left ( mathbf{x}^{(i)} right ) right )}cdot triangledown _{theta ^Tmathbf{x}^{(i)}}h_theta left ( mathbf{x}^{(i)} right )cdot triangledown _{theta _j}left ( theta ^Tmathbf{x}^{(i)} right ) right end{matrix}
而：
▿θTx(i)hθ(x(i))=hθ(x(i))(1−hθ(x(i)))▽θTx(i)hθ(x(i))=hθ(x(i))(1−hθ(x(i)))
triangledown _{theta ^Tmathbf{x}^{(i)}}h_theta left ( mathbf{x}^{(i)} right )=h_theta left ( mathbf{x}^{(i)} right )left ( 1-h_theta left ( mathbf{x}^{(i)} right ) right )
▿θj(θTx(i))=x(i)j▽θj(θTx(i))=xj(i)
triangledown _{theta _j}left ( theta ^Tmathbf{x}^{(i)} right )=x^{(i)}_j
因此，梯度的公式为：
▿θjJ(θ)=−1m∑i=1m(y(i)−hθ(x(i)))⋅x(i)j▽θjJ(θ)=−1m∑i=1m(y(i)−hθ(x(i)))⋅xj(i)
triangledown _{theta _j}Jleft ( theta right )=-frac{1}{m}sum_{i=1}^{m}left left ( y^{(i)}-h_theta left ( mathbf{x}^{(i)} right ) right )cdot x^{(i)}_j right
根据梯度下降法，得到如下的更新公式：
θj:=θj−α▿θjJ(θ)θj:=θj−α▽θjJ(θ)
theta _j:=theta _j-alpha triangledown _{theta _j}Jleft ( theta right )
二、Softmax回归
2.1、Softmax回归简介
Softmax是Logistic回归在多分类上的推广，即类标签yyy的取值大于等于222。假设有mmm个训练样本{(x(1),y(1)),(x(2),y(2)),⋯,(x(m),y(m))}{(x(1),y(1)),(x(2),y(2)),⋯,(x(m),y(m))}left { left ( mathbf{x}^{(1)},y^{(1)} right ),left ( mathbf{x}^{(2)},y^{(2)} right ),cdots ,left ( mathbf{x}^{(m)},y^{(m)} right ) right }，对于Softmax回归，其输入特征为：x(i)∈ℜn 1x(i)∈ℜn 1mathbf{x}^{(i)}in Re ^{n 1}，类标记为：y(i)∈{0,1,⋯k}y(i)∈{0,1,⋯k}y^{(i)}in left { 0,1,cdots k right }。假设函数为对于每一个样本估计其所属的类别的概率p(y=j∣x)p(y=j∣x)pleft ( y=jmid mathbf{x} right )，具体的假设函数为：
hθ(x(i))=⎡⎣⎢⎢⎢⎢⎢p(y(i)=1∣x(i);θ)p(y(i)=2∣x(i);θ)⋮p(y(i)=k∣x(i);θ)⎤⎦⎥⎥⎥⎥⎥=1∑kj=1eθTjx(i)⎡⎣⎢⎢⎢⎢⎢eθT1x(i)eθT2x(i)⋮eθTkx(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)
h_theta left ( mathbf{x}^{(i)} right )=begin{bmatrix} pleft ( y^{(i)}=1mid mathbf{x}^{(i)};theta right ) pleft ( y^{(i)}=2mid mathbf{x}^{(i)};theta right ) vdots pleft ( y^{(i)}=kmid mathbf{x}^{(i)};theta right ) end{bmatrix}=frac{1}{sum_{j=1}^{k}e^{theta ^T_jmathbf{x}^{(i)}}}begin{bmatrix} e^{theta ^T_1mathbf{x}^{(i)}} e^{theta ^T_2mathbf{x}^{(i)}} vdots e^{theta ^T_kmathbf{x}^{(i)}} end{bmatrix}
其中θθtheta 表示的向量，且θi∈ℜn 1θi∈ℜn 1theta _iin Re ^{n 1}。则对于每一个样本估计其所属的类别的概率为：
p(y(i)=j∣x(i);θ)=eθTjx(i)∑kl=1eθTlx(i)p(y(i)=j∣x(i);θ)=eθjTx(i)∑l=1keθlTx(i)
pleft ( y^{(i)}=jmid mathbf{x}^{(i)};theta right )=frac{e^{theta ^T_jmathbf{x}^{(i)}}}{sum_{l=1}^{k}e^{theta ^T_lmathbf{x}^{(i)}}}
2.2、Softmax回归的代价函数
类似于Logistic回归，在Softmax的代价函数中引入指示函数I{⋅}I{⋅}Ileft { cdot right }，其具体形式为：
I{expression}={01 if expression=false if expression=trueI{expression}={0 if expression=false1 if expression=true
Ileft { expression right }=begin{cases} 0 & text{ if } expression=false 1 & text{ if } expression=true end{cases}
那么，对于Softmax回归的代价函数为：
J(θ)=−1m∑i=1m∑j=1kI{y(i)=j}logeθTjx(i)∑kl=1eθTlx(i)J(θ)=−1m∑i=1m∑j=1kI{y(i)=j}logeθjTx(i)∑l=1keθlTx(i)
Jleft ( theta right )=-frac{1}{m}left sum_{i=1}^{m}sum_{j=1}^{k}Ileft { y^{(i)}=j right }logfrac{e^{theta ^T_jmathbf{x}^{(i)}}}{sum_{l=1}^{k}e^{theta ^T_lmathbf{x}^{(i)}}} right
2.3、Softmax回归的求解
对于上述的代价函数，可以使用梯度下降法对其进行求解，首先对其进行求梯度：
▿θjJ(θ)=−1m∑i=1m▿θj∑j=1kI{y(i)=j}logeθTjx(i)∑kl=1eθTlx(i)▽θjJ(θ)=−1m∑i=1m▽θj∑j=1kI{y(i)=j}logeθjTx(i)∑l=1keθlTx(i)
triangledown _{theta _j}Jleft ( theta right )=-frac{1}{m}sum_{i=1}^{m}left triangledown _{theta _j}sum_{j=1}^{k}Ileft { y^{(i)}=j right }logfrac{e^{theta ^T_jmathbf{x}^{(i)}}}{sum_{l=1}^{k}e^{theta ^T_lmathbf{x}^{(i)}}} right
已知，对于一个样本只会属于一个类别：
- 若y(i)=jy(i)=j y^{(i)}=j，则I{y(i)=j}=1I{y(i)=j}=1Ileft { y^{(i)}=j right }=1
▿θjJ(θ)=−1m∑mi=1▿θjlogeθTjx(i)∑kl=1eθTlx(i)=−1m∑mi=1∑kl=1eθTlx(i)eθTjx(i)⋅eθTjx(i)⋅x(i)⋅∑kl=1eθTlx(i)−eθTjx(i)⋅x(i)⋅eθTjx(i)(∑kl=1eθTlx(i))2=−1m∑mi=1∑kl=1eθTlx(i)−eθTjx(i)∑kl=1eθTlx(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)
begin{matrix} triangledown _{theta _j}Jleft ( theta right )=-frac{1}{m}sum_{i=1}^{m}left triangledown _{theta _j}logfrac{e^{theta ^T_jmathbf{x}^{(i)}}}{sum_{l=1}^{k}e^{theta ^T_lmathbf{x}^{(i)}}} right =-frac{1}{m}sum_{i=1}^{m}left frac{sum_{l=1}^{k}e^{theta ^T_lmathbf{x}^{(i)}}}{e^{theta ^T_jmathbf{x}^{(i)}}}cdot frac{e^{theta ^T_jmathbf{x}^{(i)}}cdot mathbf{x}^{(i)}cdot sum_{l=1}^{k}e^{theta ^T_lmathbf{x}^{(i)}}-e^{theta ^T_jmathbf{x}^{(i)}}cdot mathbf{x}^{(i)}cdot e^{theta ^T_jmathbf{x}^{(i)}}}{left ( sum_{l=1}^{k}e^{theta ^T_lmathbf{x}^{(i)}} right )^2} right =-frac{1}{m}sum_{i=1}^{m}left frac{sum_{l=1}^{k}e^{theta ^T_lmathbf{x}^{(i)}}-e^{theta ^T_jmathbf{x}^{(i)}}}{sum_{l=1}^{k}e^{theta ^T_lmathbf{x}^{(i)}}}cdot mathbf{x}^{(i)} right end{matrix}
- 若y(i)≠jy(i)≠j y^{(i)}neq j，假设y(i)≠j′y(i)≠j′y^{(i)}neq {j}'，则I{y(i)=j}=0I{y(i)=j}=0Ileft { y^{(i)}=j right }=0，I{y(i)=j′}=1I{y(i)=j′}=1Ileft { y^{(i)}={j}' right }=1
▿θjJ(θ)=−1m∑mi=1▿θjlogeθTj′x(i)∑kl=1eθTlx(i)=−1m∑mi=1∑kl=1eθTlx(i)eθTj′x(i)⋅−eθTj′x(i)⋅x(i)⋅eθTjx(i)(∑kl=1eθTlx(i))2=−1m∑mi=1−eθTjx(i)∑kl=1eθTlx(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)
begin{matrix} triangledown _{theta _j}Jleft ( theta right )=-frac{1}{m}sum_{i=1}^{m}left triangledown _{theta _j}logfrac{e^{theta ^T_{{j}'}mathbf{x}^{(i)}}}{sum_{l=1}^{k}e^{theta ^T_lmathbf{x}^{(i)}}} right =-frac{1}{m}sum_{i=1}^{m}left frac{sum_{l=1}^{k}e^{theta ^T_lmathbf{x}^{(i)}}}{e^{theta ^T_{{j}'}mathbf{x}^{(i)}}}cdot frac{-e^{theta ^T_{{j}'}mathbf{x}^{(i)}}cdot mathbf{x}^{(i)}cdot e^{theta ^T_jmathbf{x}^{(i)}}}{left ( sum_{l=1}^{k}e^{theta ^T_lmathbf{x}^{(i)}} right )^2} right =-frac{1}{m}sum_{i=1}^{m}left -frac{e^{theta ^T_jmathbf{x}^{(i)}}}{sum_{l=1}^{k}e^{theta ^T_lmathbf{x}^{(i)}}}cdot mathbf{x}^{(i)} right end{matrix}
最终的结果为：
−1m∑i=1mx(i)(I{y(i)=j}−p(y(i)=j∣x(i);θ))−1m∑i=1mx(i)(I{y(i)=j}−p(y(i)=j∣x(i);θ))
-frac{1}{m}sum_{i=1}^{m}left mathbf{x}^{(i)}left ( Ileft { y^{(i)}=j right }-pleft ( y^{(i)}=jmid mathbf{x}^{(i)};theta right ) right ) right
注意，此处的θjθjtheta_j表示的是一个向量。通过梯度下降法的公式可以更新：
θj:=θj−α▿θjJ(θ)θj:=θj−α▽θjJ(θ)
theta _j:=theta _j-alpha triangledown _{theta _j}Jleft ( theta right )
5、Softmax回归中的参数特点
在Softmax回归中存在着参数冗余的问题。简单来讲就是参数中有些参数是没有任何用的，为了证明这点，假设从参数向量θjθjtheta _j中减去向量ψψpsi ，假设函数为：
p(y(i)=j∣x(i);θ)=e(θj−ψ)Tx(i)∑kl=1e(θl−ψ)Tx(i)=eθTjx(i)⋅e−ψTx(i)∑kl=1eθTlx(i)⋅e−ψTx(i)=eθTjx(i)∑kl=1eθTlx(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)
begin{matrix} pleft ( y^{(i)}=jmid mathbf{x}^{(i)};theta right )=frac{e^{(theta _j-psi )^Tmathbf{x}^{(i)}}}{sum_{l=1}^{k}e^{(theta _l-psi )^Tmathbf{x}^{(i)}}} =frac{e^{theta ^T_jmathbf{x}^{(i)}}cdot e^{-psi ^Tmathbf{x}^{(i)}}}{sum_{l=1}^{k}e^{theta ^T_lmathbf{x}^{(i)}}cdot e^{-psi ^Tmathbf{x}^{(i)}}} =frac{e^{theta ^T_jmathbf{x}^{(i)}}}{sum_{l=1}^{k}e^{theta ^T_lmathbf{x}^{(i)}}} end{matrix}
从上面可以看出从参数向量θjθjtheta _j中减去向量ψψpsi 对预测结果并没有任何的影响，也就是说在模型中，存在着多组的最优解。
为了是算法能够尽可能简单，保留所有的参数，但是对代价函数加入权重衰减来解决参数冗余的问题，权重衰减即对参数进行正则化。
如对参数进行L2正则约束，L2正则为：
λ2∑i=1k∑j=0nθ2ijλ2∑i=1k∑j=0nθij2
frac{lambda }{2}sum_{i=1}^{k}sum_{j=0}^{n}theta ^2_{ij}
此时，代价函数为：
J(θ)=−1m∑i=1m∑j=1kI{y(i)=j}logeθTjx(i)∑kl=1eθTlx(i) λ2∑i=1k∑j=0nθ2ijJ(θ)=−1m∑i=1m∑j=1kI{y(i)=j}logeθjTx(i)∑l=1keθlTx(i) λ2∑i=1k∑j=0nθij2
Jleft ( theta right )=-frac{1}{m}left sum_{i=1}^{m}sum_{j=1}^{k}Ileft { y^{(i)}=j right }logfrac{e^{theta ^T_jmathbf{x}^{(i)}}}{sum_{l=1}^{k}e^{theta ^T_lmathbf{x}^{(i)}}} right frac{lambda }{2}sum_{i=1}^{k}sum_{j=0}^{n}theta ^2_{ij}
其中，λ>0λ>0lambda >0，此时代价函数是一个严格的凸函数。
对该函数的导数为：
▿θjJ(θ)=−1m∑i=1mx(i)(I{y(i)=j}−p(y(i)=j∣x(i);θ)) λθj▽θjJ(θ)=−1m∑i=1mx(i)(I{y(i)=j}−p(y(i)=j∣x(i);θ)) λθj
triangledown {theta _j}Jleft ( theta right )=-frac{1}{m}sum_{i=1}^{m}left mathbf{x}^{(i)}left ( Ileft { y^{(i)}=j right }-pleft ( y^{(i)}=jmid mathbf{x}^{(i)};theta right ) right ) right lambda theta _j
5、Softmax与Logistic回归的关系
Logistic回归算法是Softmax回归的特征情况，即k=2k=2k=2时的情况，当
k=2k=2k=2时，Softmax回归为：
hθ(x)=1eθT1x eθT2xeθT1xeθT2xhθ(x)=1eθ1Tx eθ2Txeθ1Txeθ2Tx
h_theta left ( x right )=frac{1}{e^{theta _1^Tx} e^{theta _2^Tx}}begin{bmatrix} e^{theta _1^Tx} e^{theta _2^Tx} end{bmatrix}
利用Softmax回归参数冗余的特点，令ψ=θ1ψ=θ1psi =theta _1，从两个向量中都减去这个向量，得到：
hθ(x)=1e(θ1−ψ)Tx e(θ2−ψ)Txe(θ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⎤⎦⎥⎥hθ(x)=1e(θ1−ψ)Tx e(θ2−ψ)Txe(θ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
begin{matrix} h_theta left ( mathbf{x} right )=frac{1}{e^{(theta _1-psi )^Tmathbf{x}} e^{(theta _2-psi )^Tmathbf{x}}}begin{bmatrix} e^{(theta _1-psi )^Tmathbf{x}} e^{(theta _2-psi )^Tmathbf{x}} end{bmatrix} =begin{bmatrix} frac{1}{1 e^{(theta _2-theta _1 )^Tmathbf{x}}} frac{e^{(theta _2-theta _1 )^Tmathbf{x}}}{1 e^{(theta _2-theta _1 )^Tmathbf{x}}} end{bmatrix} =begin{bmatrix} frac{1}{1 e^{(theta _2-theta _1 )^Tmathbf{x}}} 1-frac{1}{1 e^{(theta _2-theta _1 )^Tmathbf{x}}} end{bmatrix} end{matrix}
上述的表达形式与Logistic回归是一致的。
6、多分类算法和二分类算法的选择
有人会觉得对于一个多分类问题，可以使用多个二分类来完成，对于多分类问题是直接选择多分类的分类器还是选择多个二分类的分类器进行叠加，在UFLDL中，作者给出了这样的解释：取决于类别之间是否互斥。
对于一个多分类的问题，是直接选择多分类器直接计算还是选择多个二分类器进行计算取决于问题中类别之间是否互斥。
- 是互斥的 –> Softmax回归
- 不是互斥的 –> 多个独立的Logistic回归
对于Softmax回归更多内容，包括实验可见博客简单易学的机器学习算法——Softmax Regression
参考文献
- 英文版：UFLDL Tutorial
- 中文版：UFLDL教程
- 《Python机器学习算法》第2章 Softmax Regression
