Softmax
设 x ∈ R d , W ∈ R c × d , y ∈ R c x\in \R^d, W\in \R^{c\times d}, y\in \R^c x∈Rd,W∈Rc×d,y∈Rc ，满足 1 T y = 1 1^Ty=1 1Ty=1
若 J = ? y T log ? ( softmax ( W x ) ) J=-y^T\log(\text{softmax}(Wx)) J=?yTlog(softmax(Wx))
我们要求 ? J ? W i , j \frac{\partial J}{\partial W_{i,j}} ?Wi,j??J?
设 z = W x , y ^ = softmax ( z ) z=Wx, \hat{y}=\text{softmax}(z) z=Wx,y^?=softmax(z)
? J ? W i , j = ∑ k = 1 c ? J ? y ^ k ? y ^ k ? z i ? z i ? W i , j = ∑ k = 1 c ( ? y k y ^ k ) y k ^ ( δ k i ? y i ^ ) x j = ∑ k = 1 c y k ( y i ^ ? δ k i ) x j = ( ( 1 T y ) y ^ i ? y i ) x j = ( y ^ i ? y i ) x j \frac{\partial J}{\partial W_{i,j}}=\sum_{k=1}^c\frac{\partial J}{\partial \hat{y}_k}\frac{\partial \hat{y}_k}{\partial z_i}\frac{\partial z_i}{\partial W_{i,j}}\\=\sum_{k=1}^c(-\frac{y_k}{\hat{y}_k})\hat{y_k}(\delta_{ki}-\hat{y_i})x_j\\=\sum_{k=1}^cy_k(\hat{y_i}-\delta_{ki})x_j\\=((1^Ty)\hat{y}_i-y_i)x_j\\=(\hat{y}_i-y_i)x_j ?Wi,j??J?=∑k=1c??y^?k??J??zi??y^?k???Wi,j??zi??=∑k=1c?(?y^?k?yk??)yk?^?(δki??yi?^?)xj?=∑k=1c?yk?(yi?^??δki?)xj?=((1Ty)y^?i??yi?)xj?=(y^?i??yi?)xj?
? J ? W = ( y ^ ? y ) x T \frac{\partial J}{\partial W}=(\hat{y}-y)x^T ?W?J?=(y^??y)xT
结果是一个 1 × c × d 1\times c\times d 1×c×d 的张量，第一维省略了
偏置不需要特殊处理，将 x x x 加一个维度放 1 1 1 就行。
如果是一个 batch ，可以把向量外积直接扩张成矩阵乘法
SVM
目标
min ? w , b 1 2 ∣ ∣ w ∣ ∣ 2 \min_{w,b}\frac{1}{2}||w||^2 minw,b?21?∣∣w∣∣2
约束条件
1 ? y ( n ) ( w T x ( n ) + b ) ≤ 0 , ? n ∈ { 1 , 2 , . . . , N } 1-y^{(n)}(w^Tx^{(n)}+b)\le 0, \forall n\in \{1,2,...,N\} 1?y(n)(wTx(n)+b)≤0,?n∈{1,2,...,N}
Lagrange 函数
L ( w , b ; λ ) = 1 2 ∣ ∣ w ∣ ∣ 2 + ∑ n = 1 N λ n ( 1 ? y ( n ) ( w T x ( n ) + b ) ) L(w,b;\lambda)=\frac{1}{2}||w||^2+\sum_{n=1}^N\lambda_n(1-y^{(n)}(w^Tx^{(n)}+b)) L(w,b;λ)=21?∣∣w∣∣2+∑n=1N?λn?(1?y(n)(wTx(n)+b))
特别要求 λ ≥ 0 \lambda\ge 0 λ≥0
令 θ ( w , b ) = max ? λ ≥ 0 L ( w , b ; λ ) \theta(w,b)=\max_{\lambda\ge 0}L(w,b;\lambda) θ(w,b)=maxλ≥0?L(w,b;λ)
则 θ ( w , b ) = { 1 2 ∣ ∣ w ∣ ∣ 2 1 ? y ( n ) ( w T x ( n ) + b ) ≤ 0 , ? n ∈ { 1 , 2 , . . . , N } + ∞ 1 ? y ( n ) ( w T x ( n ) + b ) > 0 , ? n ∈ { 1 , 2 , . . . , N } \theta(w,b)=\begin{cases}\frac{1}{2}||w||^2&1-y^{(n)}(w^Tx^{(n)}+b)\le 0, \forall n\in \{1,2,...,N\}\\+\infty&1-y^{(n)}(w^Tx^{(n)}+b)>0, \exists n\in \{1,2,...,N\} \end{cases} θ(w,b)={21?∣∣w∣∣2+∞?1?y(n)(wTx(n)+b)≤0,?n∈{1,2,...,N}1?y(n)(wTx(n)+b)>0,?n∈{1,2,...,N}?
目标转化为求 min ? w , b max ? λ ≥ 0 L ( w , b ; λ ) \min_{w,b}\max_{\lambda\ge 0}L(w,b;\lambda) minw,b?maxλ≥0?L(w,b;λ)
而 min ? w , b max ? λ ≥ 0 L ( w , b ; λ ) ≥ max ? λ ≥ 0 min ? w , b L ( w , b ; λ ) \min_{w,b}\max_{\lambda\ge 0}L(w,b;\lambda)\ge \max_{\lambda\ge 0}\min_{w,b}L(w,b;\lambda) minw,b?maxλ≥0?L(w,b;λ)≥maxλ≥0?minw,b?L(w,b;λ)
令 ? w , b L = 0 \nabla_{w,b}L=0 ?w,b?L=0 得
{ w T ? ∑ n = 1 N λ n y ( n ) ( x ( n ) ) T = 0 ∑ n = 1 N λ n y ( n ) = 0 \begin{cases}w^T-\sum_{n=1}^N\lambda_ny^{(n)}(x^{(n)})^T=0\\\sum_{n=1}^N\lambda_ny^{(n)}=0\end{cases} {wT?∑n=1N?λn?y(n)(x(n))T=0∑n=1N?λn?y(n)=0?
得到对偶函数
Γ ( λ ) = ? 1 2 ∣ ∣ ∑ n = 1 N λ n y ( n ) x ( n ) ∣ ∣ 2 + ∑ n = 1 N λ n \Gamma(\lambda)=-\frac{1}{2}||\sum_{n=1}^N\lambda_ny^{(n)}x^{(n)}||^2+\sum_{n=1}^N\lambda_n Γ(λ)=?21?∣∣∑n=1N?λn?y(n)x(n)∣∣2+∑n=1N?λn?
对偶问题为 max ? λ ≥ 0 Γ ( λ ) \max_{\lambda\ge 0}\Gamma(\lambda) maxλ≥0?Γ(λ)
此时 max ? λ ≥ 0 Γ ( λ ) ≤ min ? w , b max ? λ ≥ 0 L ( w , b ; λ ) \max_{\lambda\ge 0}\Gamma(\lambda)\le \min_{w,b}\max_{\lambda\ge 0}L(w,b;\lambda) maxλ≥0?Γ(λ)≤minw,b?maxλ≥0?L(w,b;λ)
对于凸函数，有个 KKT 条件：
λ n ? ( 1 ? y ( n ) ( ( w ? ) T x ( n ) + b ? ) ) = 0 \lambda_n^*(1-y^{(n)}((w^*)^Tx^{(n)}+b^*))=0 λn??(1?y(n)((w?)Tx(n)+b?))=0
λ n ? > 0 \lambda_n^*>0 λn??>0 的称为支持向量，否则不在边界（约束失效）
满足该条件的解是原问题和对偶问题的最优解。
最终决策函数为 f ( x ) = sgn ( ( w ? ) T x + b ? ) f(x)=\text{sgn}((w^*)^Tx+b^*) f(x)=sgn((w?)Tx+b?)
