使用Mitchell近似构造加法神经网络.

• paper：Deep Neural Network Training without Multiplications
• arXiv：link

本文通过Mitchell近似算法将乘法运算转变为加法运算，从而降低了神经网络中的乘法的运算量。

1. Mitchell近似

Mitchell近似是一种在二进制下近似的快速对数和指数计算方法。对于一个十进制的非负数$p$，其二进制表示为：

其中$z_n=1$，\(z_i \in \{0,1\}\)。根据进制转换，$p$可以表示为：

若记$x=\sum_{i=-m}^{n-1}z_i2^{i-n}$，在计算$p$的对数$\log_2p$时，根据$p$的展开式可得：

Mitchell近似假设$\log_2(1+x)≈x$，则上式近似为：

注意到$n$是整数，其二进制表示也是整数；$x$的二进制表示为小数：

注意到$x$可以由$p$的二进制表示的移位操作得到。

因此通过Mitchell近似进行快速对数运算的步骤如下：

1. 输入十进制的$p$；
2. 将$p$转换为二进制数$z_nz_{n-1}\cdot\cdot\cdot z_{1}z_0.z_{-1}z_{-2}\cdot\cdot\cdot z_{-(m-1)}z_{-m}$；
3. $\log_2p$的整数部分：将$n$转换为二进制数$y_ky_{k-1}\cdot\cdot\cdot y_{1}y_0$；
4. $\log_2p$的小数部分：$0.z_{n-1}\cdot\cdot\cdot z_{1}z_0z_{-1}z_{-2}\cdot\cdot\cdot z_{-(m-1)}z_{-m}$
5. 则$\log_2p$的二进制表示为：

将上述过程逆过来，就得到Mitchell近似的快速指数运算：

1. 输入十进制的$p$；
2. 将$p$转换为二进制数$z_nz_{n-1}\cdot\cdot\cdot z_{1}z_0.z_{-1}z_{-2}\cdot\cdot\cdot z_{-(m-1)}z_{-m}$；
3. 将$z_nz_{n-1}\cdot\cdot\cdot z_{1}z_0$转换为十进制数$n$；
4. 则$2^p$的二进制表示为：

2. 将Mitchell近似应用于乘法

将二进制下的乘法运算转变成加法运算，可以通过对数和指数转换：

因此计算$p$和$q$的乘积，可以先通过Mitchell近似计算快速对数$\log_2p$和$\log_2q$，将其相加后得到$s$；再通过Mitchell近似计算快速指数$2^s$。

一个简单的例子如下：

3. 误差分析

若记$x=\sum_{i=-m}^{n-1}z_i2^{i-n}$，Mitchell近似假设$\log_2(1+x)≈x$，在计算$p$的对数$\log_2p$时近似为：

因此Mitchell近似就是将十进制下的数$p=2^n(1+x)$的对数表示为$\log_2p≈n+x$；或者将十进制下的数$p=n+x$的指数表示为$2^p≈2^n(1+x)$。注意到$n$是整数部分，$x$是小数部分。

对于两个数$p=2^{n_p}(1+x_p)$和$q=2^{n_q}(1+x_q)$，直接相乘的结果为$2^{n_p}(1+x_p)\times 2^{n_q}(1+x_q)$。通过Mitchell近似可以计算$\log_2p+\log_2q=n_p+n_q+x_p+x_q$，分两种情况讨论：

• 当$x_p+x_q<1$时，$n_p+n_q+x_p+x_q$的指数近似为$2^{n_p+n_q}(1+x_p+x_q)$，则乘法运算$pq$的近似程度为：

• 当$x_p+x_q>1$时，$n_p+n_q+x_p+x_q$的指数近似为$2^{n_p+n_q+1}(1+x_p+x_q-1)$，则乘法运算$pq$的近似程度为：

上面两式均在$n_p=n_q=0.5$处取得最小值$\frac{8}{9}$，因此Mitchell近似的最大误差不超过$\frac{1}{9}$。

Mitchell近似的误差是由公式$\log_2(1+x)≈x$引入的，而$x$是自然对数的一阶泰勒展开$\log_e(1+x)≈x$，因此Mitchell近似的误差包括泰勒展开的高阶误差和$2$与$e$的相似度误差。