L0 norm稀疏性: hard concrete门变量

统计， DL

Learning Sparse Neural Networks through L0 Regularization_ICLR 2018

---

Uniform分布

X $\sim$ Uniform(0,1): X在（0，1）这个范围内取值，取各个点的概率是相同的。

Sigmoid函数, logistic函数

$${\rm sigmoid}(x)=\frac{1}{1+e^{-x}}$$
自变量x的取值范围是R，
函数值sigmoid(x)的取值范围是(0,1)。 函数值的范围和概率值的范围正好一致，可以把一个属于R的量x映射为概率值sigmoid(x)，数值越大概率值越大。

softmax函数

把$R^K$空间的K维向量，映射到simplex--K维向量，每一维取值在(0,1)范围且K维取值之和等于1。

$$[\pi_1,...,\pi_K]=\rm{softmax}([o_1,...,o_K]=[\frac{e^{o_1}}{\sum_k e^{o_k}},...,\frac{e^{o_K}}{\sum_k e^{o_k}}]$$
函数值的范围正好是 离散概率分布。。。。该怎么说？

Logistic 分布

X $\sim$ Logistic(0,1): X在R上取值，但是其cdf是logistic函数，S形状， pdf像高斯的倒钟形但是是厚尾。
cdf是

$$\frac{1}{1+e^{-x}}$$

$U \sim {\rm Uniform}(0,1)$ 则 $\ln U-\ln(1-U)$ 是Logistic分布的。

Gumbel 分布

用来建模某些分布的采样的最大值/最小值的分布。例如，已知某条河流过去十年里的最大水位值，则今年该条河流的最大水位x的分布可能是Gumbel分布。
X $\sim$ Gumbel(0,1) ：X的 CDF是

$$e^{-e^{-x}}$$

U $\sim$ Uniform(0,1), 则 $-\ln(-\ln U)$ 是Gumbel分布的。

两个Gumbel分布的随机变量的差服从logistic分布:
$G_1-G_2 \sim {\rm Logistic}$

Categorical分布，Gumbel-max分布

X $\sim$ Categorical($\pi_1$,...,$\pi_K$): X取整数1...K，其中取整数j的概率是$p_j$.

在神经网络中，输出实数向量 $o\in R^K$, 通过softmax函数，

$$p_j=\frac{e^{o_j}}{\sum_i e^{o_i}}$$ 得到该输出属于第j类的概率。

1. $U \sim {\rm Uniform}(0,1)$采样K个均匀分布的变量$u_1,...,u_K$
2. $Z=-\ln(-\ln U))$ 得到Gumbel分布的变量的K个采样$\{ z_i=-\ln(-\ln u_i) \}_{i=1}^K$
3. 则对K个Gumbel分布变量组成的向量取argmax 得到$arg \max_i( o +z)$是一个1...K的整数，是服从${\rm Categorical} (\pi_1,...,\pi_K)$分布的, 其中$\pi_i=\frac{e^{o_i}}{\sum_j e^{o_j}}$。

已知$o$进而采样可以判定得到的变量是Categorical分布的。
已知分布的参数$\pi$，求采样的参数$o$怎么求呢？？？ 不会求还是不会采样呢。

考虑向量形式的Categorical分布，
X $\sim$ Categorical($\pi_1$,...,$\pi_K$)则X是一个K维的one-hot向量，即某一个向量维取值为1，其它向量维都取值为0。也即K-1维simplex的某一个顶点。

Bernoulli分布，二元Categorical变量

X $\sim$ Bernoulli(p): X取0/1，其中取1的概率是p

$$(X,{\bar X}) \sim \rm{Categorical}(p,1-p)$$

按照Gumbel max技巧采样Categorical分布的变量的方法采样Bernoullli分布的变量：
1. $U \sim {\rm Uniform}(0,1)$采样2个均匀分布的变量$u_1,u_2$
2. $Z=-\ln(-\ln U))$ 得到Gumbel分布的变量的2个采样 $z_1=-\ln(-\ln u_1)$, $z_2$
3. X=1 当且仅当 $O_1+z_1>O_2+z_2$, 其中

$$p=\frac{e^{o_1}}{e^{o_1}+e^{o_2}}, 1-p=\frac{e^{o_2}}{e^{o_1}+e^{o_2}}$$ 。
也就是当且仅当$z_1-z_2>O_2-O_1=\ln(\frac{1}{p}-1)$
$z_1-z_2$是两个Gumbel分布的变量，两者之差为logistic分布，故只用采样一个logistic分布的变量$z_1-z_2$，采样大于$O_2-O_1$则Bernoulli分布的变量取1，否则取0.

通过采样logistic分布的变量采样Bernoulli分布的变量：
$U \sim {\rm Uniform}(0,1)$ 采样u
$\ln U-\ln(1-U)> \ln (\frac{1}{p}-1)$ 则采样得到Bernoulli变量X=1，否则采样得到X=0.

concrete分布， Gumbel-Softmax分布, Categorical分布的扩展

X $\sim$ Concrete($(\alpha_1,...,\alpha_k),\tau$)： 是一个K维向量，每维取值(0,1)之间，所有K维之和等于1。

该分布是对Categorical分布的连续放松，不是只能取K-1维simplex的某一个顶点，而是取K-1维simplex的内部某一个点。

1. $U \sim {\rm Uniform}(0,1)$采样K个均匀分布的变量$u_1,...,u_K$
2. $Z=-\ln(-\ln U))$ 得到Gumbel分布的变量的K个采样$\{ z_i=-\ln(-\ln u_i) \}_{i=1}^K$
3. 则对K个Gumbel分布变量组成的向量取softmax 得到的向量

$$[\frac{e^{(z_1+\ln \alpha_1)/\tau}}{\sum_j e^{(z_j+\ln \alpha_j)/\tau}},...,\frac{e^{(z_K+\ln \alpha_K)/\tau}}{\sum_j e^{(z_j+\ln \alpha_K)/\tau}}]$$ 是$\rm{Concrete}((\alpha_1,...,\alpha_k),\tau)$分布的。

当$\tau \to 0$,Concrete分布的向量趋于onehot向量，即Categorical分布。
$\tau \to 0$，$\vec{y} \to \rm{onehot} (y_{\max})$，$\vec{y} \sim \rm{Concrete}((\alpha1,...,\alpha_K),\tau) \to \rm{Categorical}(\pi_1,...,\pi_K)$,其中

$$\pi_i=\frac{\alpha_i}{\sum_j \alpha_j}$$
$x_i$比其它维度的取值大的概率是$\pi_i=\frac{\alpha_i}{\sum_j \alpha_j}$。

二元Concrete分布

因为Concrete分布的变量 $X=(x_1,x_2)\sim \rm{Concrete}((\alpha_1,\alpha_2),\tau)$有$x_1+x_2=1$

根据Gumbel-softmax技巧采样得到的Concrete变量为

$$[\frac{e^{(z_1+\ln \alpha_1)/\tau}}{ e^{(z_1+\ln \alpha_1)/\tau}+ e^{(z_2+\ln \alpha_2)/\tau}}, \frac{e^{(z_1+\ln \alpha_1)/\tau}}{ e^{(z_1+\ln \alpha_1)/\tau}+ e^{(z_2+\ln \alpha_2)/\tau}}]$$

$$x_1=\frac{e^{(z_1+\ln \alpha_1)/\tau}}{ e^{(z_1+\ln \alpha_1)/\tau}+ e^{(z_2+\ln \alpha_2)/\tau}}=\frac{1}{ 1+ e^{(z_2-z_1+\ln \alpha_2-\ln \alpha_1)/\tau}}={\rm sigmoid}(\frac{z_1-z_2+\ln \alpha_1-\ln\alpha_2}{\tau})$$
$z_1-z_2$是两个Gumbel分布的变量，两者之差为logistic分布，故只用采样一个logistic分布的变量即可得到二元concrete分布的变量$X=($x_1,1-x_1)$。

通过采样logistic分布的变量采样二元Concrete分布的变量：
$U \sim {\rm Uniform}(0,1)$ 采样u
$x_1=\rm{sigmoid}(\frac{\ln U-\ln(1-U)+\ln\alpha_1-\ln\alpha_2}{\tau})$, $x_2=1-x_1$。

二元的只需要一个$\alpha$参数了
$(x_1,x_2)=\rm{Concrete}((\alpha,1),\tau)$,
当$\tau \to 0$, $p(x_1=1)=\frac{\alpha}{\alpha+1}$，
即$\alpha$越大则第一个数取值比第二个数取值大的概率越大；$\tau$越小两个数的差别越大。
$x_1=\rm{sigmoid}(\frac{\ln U-\ln(1-U)+\ln\alpha}{\tau})$, $x_2=1-x_1$。

$(X,1-X)=\rm{Concrete}((\alpha,1),\tau)$的CDF为

$$p(X<x)= \rm{Sigmoid}(\tau(\log x-\log(1-x))-\log \alpha)$$

---

L0 norm惩罚

• 目标函数中添加惩罚项L0norm=非0取值的参数的个数。
• 每个参数设置一个binary门z, 则惩罚项变为所有z的和。
• 以上n维参数，则有$2^n$种取0的可能性。
• 将每个参数的binary门看成随机变量z，其服从一个Bernouli分布，取1的概率为$\pi$。则优化的目标函数变为对z变量求期望，即 从Bernouli$(\pi)$中采样得到各种z的取值组合，计算预测损失，关于z平均；惩罚项变为 各个参数的门变量z取1的概率的和。
• 从Bernouli$(\pi)$采样离散的z不容易计算梯度
  
  • reinforce梯度估计：高variance
  • ST估计：biased梯度
  • 把z改成concrete分布: z不能取到0不能真正地稀疏参数。

• 为每个参数设置的门变量z是 0，(0,1]取值的随机变量。损失关于z的采样平均，惩罚项变为z不等于0的概率。

  • hard-sigmoid rectification函数:
    

    $$z=\min(1,\max(0,s))$$
    • s是连续变量，取值可以任意属于R。
    • s在(-,0]时候z=0，
    • s在[0,1]时候z=s;
    • s在（1，+）时候z=1。
      z不等于0的概率即为s>0的概率。

  • 二元concrete变量 $[\bar{s},1-\bar s] \sim \rm{Concrete}((\alpha,1),\tau)$，$\bar s$的采样方法为 $\bar s={\rm Sigmoid}(\frac{\ln U-\ln(1-U)+\ln \alpha}{\tau}) \in (0,1)$

hard concrete门变量

• hard concrete变量门z：二元concrete + 扩展到(a,b)其中$a<0<1<b$+ hard-sigmoid rectification函数
  - $\bar s={\rm Sigmoid}(\frac{\ln U-\ln(1-U)+\ln \alpha}{\tau}) \in (0,1)$
  - $s=a+(b-a)\bar s \in (a,b)$
  - $\bar s=\frac{-a}{b-a}$时候s=0,
  - $\bar s=\frac{1-a}{b-a}$时候s=1.
  - z=min(1,max(0,s)) 也即
  - 原来的二元concrete变量$(0，\frac{-a}{b-a})$时候门变量$z=0$;
  - 原来的二元concrete变量$(\frac{-a}{b-a}，\frac{1-a}{b-a})$时候门变量$z=\bar s$;
  - 原来的二元concrete变量$(\frac{1-a}{b-a},1)$时候门变量$z=1$;
  - $z\neq 0$的概率为 原来的二元concrete变量大于$\bar s_0=\frac{-a}{b-a}$
  惩罚项$p(z\neq 0)=p(\bar s> \bar s_0)=1-\rm{binaryConcreteCDF}(s_0)$=
  

  $$1-\rm{Sigmoid}(\tau(\log \frac{-a}{b-a}-\log(1-\frac{-a}{b-a}))-\log \alpha)=\rm{Sigmoid}(\ln \alpha-\tau\ln \frac{-a}{b})$$

• 把二元concrete变量的参数$\log \alpha$作为要学习的复杂度参数

• reparameterization:
  
  • 训练时候非local采样：一个batch的多个输入共用一组门变量z，z乘在theta上。x(zw)+b
  • local采样: 一个batch的多个输入采样不同的门变量z。 (xz)w+b
• 测试的时候 让u=0.5即中间值得到门z的取值。
• 组稀疏性：全连接网络，一个输入节点对应的weight变量的列共用一个z，有自己的参数$\log \alpha$; 不同的列对应不同的z要学习不同的$\log \alpha$。
• 与L2norm结合让权重值平滑
  
  • L2norm= $0.5 \lambda_2 w^2 p(z\neq 0)$
  • L0norm+L2norm= $(0.5 \lambda_2 w^2+\lambda_0) p(z\neq 0)$
• 需要的期望的浮点数计算次数FLOPs：
  
  • 全连接层:
    
    • 期望剩下 $\sum_i p(z\neq 0)$个输入节点;
    • 一个输入节点与o个输出节点连接，需要o次乘法$w_jx_j$，然后这o个数加一起o-1次加法
    • o个输出节点需要o次加法+b
    • 每一个输入到输出的全连接层 期望需要 $o+(2o-1)\sum_i p(z_i\neq 0)$次加乘法