Artificial Neural Networks Merge Algorithm

devilogic

---

反向传播网络

反向传播算法可用来学习这个网络的权值。它采用剃度下降方法试图最小化网络输出值和目标值之间的误差平方。我们来重新定义$E$。

$$E(\overrightarrow{w}) \equiv \frac{1}{2}\sum_{d \in D}\sum_{k \in output}(t_{kd} - o_{kd})^2$$ 因为是多个单元，而不是像以前只考虑单个单元，所有这里的输出有个多个。
反向传播算法面临的学习问题是搜索一个巨大的假设空间，这个空间由网络中所有单元的所有可能的权值定义。在多层网络中，误差曲面可能有多个局部极小值。

• 网络中每个结点被赋予一个序号（例如一个整数），这里的“结点”要么是网络的输入，要么是网络中某个单元的输出。
• $x_{ji}$表示结点$i$到结点$j$的输入，$w_{ji}$表示对应的权值。
• $\delta_{n}$表示与单元$n$相关联的误差项。它的角色与前面讨论的$delta$训练法则中的$(t-o)$相似。其中$\delta_n=-\frac{\delta E}{\delta net_n}$

包含两层sigmoid单元的前馈网络的反向传播算法

BACKPROPAGATION($training\_examples$, $\eta$, $n_{in}$, $n_{out}$, $n_{hidden}$)
$training\_examples$中每一个训练样例是形式为$\langle \overrightarrow{x}, \overrightarrow{t} \rangle$的序偶，其中$\overrightarrow{x}$是网络输入值向量，$\overrightarrow{t}$是目标输出值。$\eta$是学习速率(例如：$0.05$)。$n_{in}$是网络输入的数量，$n_{hidden}$是隐藏层数量，$n_{out}$是输出单元数量。从单元$i$到单元$j$的输入表示为$x_{ji}$，单元$i$到单元$j$的权值表示为$w_{ji}$。

• 创建具有$n_{in}$个输入，$n_{hidden}$个隐藏单元，$n_{out}$个输出单元的网络
• 初始化所有的网络权值为小的随机值（例如$-0.05$和$0.05$之间的数）
• 在遇到终止条件前：
• 对于训练样例$training\_examples$中每个$\langle \overrightarrow{x}, \overrightarrow{t} \rangle$：把输入向前传播。
  
  1. 把实例$\overrightarrow{x}$输入网络，并计算网络中每个单元$u$的输出$o_u$使误差沿网络反向传播
  2. 对于网络的每个输出单元$k$，计算它的误差项$\delta_k$。 $$\delta_k \leftarrow o_k(1-o_k)(t_k-o_k)$$
  3. 对于网络中每个隐藏单元$h$，计算它的误差项$\delta_h$ $$\delta_h \leftarrow o_h(1-o_h)\sum_{k \in outputs} w_{kh}\delta_k$$
  4. 更新每个网络权值$w_{ji}$ $$w_{ji} \leftarrow w_{ji} + \Delta w_{ji}$$ 其中 $$\Delta w_{ji} = \eta \delta_j x_{ji}$$

MapReduce模型

融合原理

两个矩阵$A,B$(同样的行数与列数)融合成$C$，取出两个矩阵的同行同列的对应值$a_1,b_1$。如果做均值$c_1 = \frac{a_1 + b_1}{2}$。这样融合不能反应两个值的比重问题。我们在值前面取一个比率$\alpha，\beta$。其中$\alpha + \beta = 1$。则$c_1 = \alpha a_1 + \beta b_1$。如果$\alpha$越小则输出结果越偏向$a_1$，如果$\beta$越小则输出越偏向$b_1$。则$\alpha,\beta$的取值又与其偏差权值矩阵中值相关。由于采用的是相同的算法，所以取这两个值的归一化$\alpha = 1 - \frac{\delta_A}{\delta_A + \delta_B}$，$\beta =1 - \frac{\delta_B}{\delta_A + \delta_B}$。则

$$c_1 = (1-\frac{\delta_a}{\delta_a + \delta_b})a_1 + (1-\frac{\delta_b}{\delta_a + \delta_b})b_1$$

永远让新计算出的量更偏向于误差小的一方。

因为是两个值做归一化操作，所以这里其实是做了交换偏差操作，误差小的一方所占比重要在新值中大，误差大的一方所占比重要在新值中小。

所以最终等式为:

$$c_1 = \beta a_1 + \alpha b_1$$

证明

首先让我们看一下正常的情况怎样的？

设四个权值矩阵$W_0,W_1,W_2,W_3$，其中后一个的值依赖前一个的值。则$W_1 = f(W_0)$，而$W_2 = f(W_1) = f(f(W_0))$。而$W_3 = f(f(f(W_0)))$这样如果存在$n$个训练样例，函数$f(x)$的下标对应了使用第几个训练样例，它表示了权值调整函数。一般对于每个训练样例的目标值$T_n$与输出$O_n$，它的主要任务是负责计算误差$\Delta w = T_n - O_n$，而$O_n$是一个关于输入样本$i$的连续函数，$T_n$是一个常数值，所以$\Delta w$是关于输入向量$i$的连续函数。随后在原始权值矩阵的基础上$W_{new} = W_{old} + \Delta w$。
那么最终的训练结果为

$$W_n = \begin{cases} f_1(W_0) & n=1 \\ f_n(f_{n-1}(W_{n-2})) & n > 1 \end{cases}$$

而我们的想要解决的问题是

$$W_n^{'} = \begin{cases} W_1^{'} = f_1(W_0) & n=1 \\ W_n^{'} = g_n(f_{n}(W_0),W_{n-1}^{'}) & n > 1 \end{cases}$$

这里的$f(W)=W+\Delta w$，其中$\Delta w$是一个有符号的实数。
$g(W_1, W_2) = \beta W_1 + \alpha W_2$，其中$0 \le \alpha \le 1$，$0 \le \beta \le 1$。
则上述可以替换为：

$$W_n = \begin{cases} W_1=W_0+\Delta w_1 & n=1 \\ W_n = W_0+\Delta w_1 + \Delta w_2 + \cdots + \Delta w_n & n > 1 \end{cases}$$

$$W_n^{'} = \begin{cases} W_1^{'} = W_0+\Delta w_1 & n=1 \\ W_n^{'} = \beta_n (W_0 + \Delta w^{'}_n) + \alpha_n W^{'}_{n-1}& n > 1 \end{cases}$$

当$i=1$时，$W_1 = f_1(W_0) = W_1^{'}$。
当$i=2$时，$W_2 = f_2(f_1(W_2))=W_0+\Delta w_1+\Delta w_2$。
$W_2^{'}=g_2(f_2(W_0), f_1(W_0))$。
其中，我们设等于$\Delta_n$其下标对应样本索引为串行化运算的权值偏差。而$\Delta_n^{'}$表示采用并行化运算的权值偏差

$$\begin{align}W_2^{'} &= \beta f_1(W_0)+ \alpha f_2(W_0)\\ &= \beta W_0 + \beta \Delta w_1 + \alpha W_0 + \alpha \Delta w^{'}_2 \\ &= (\beta+\alpha)W_0+\beta\Delta w_1 + \alpha\Delta w^{'}_2 \end{align}$$
又因为$\beta+\alpha = 1$，所以
$$W_2^{'} = W_0+\beta\Delta w_1 + \alpha\Delta w^{'}_2$$
而
$$W_2 = W_0 + \Delta w_1 + \Delta w_2$$
当$i=n$时，进行扩展
$$\begin{align}W^{'}_n &= W_0 + \beta_n \Delta w^{'}_n + \alpha_n \beta_{n-1} \Delta w^{'}_{n-1} + \\ & \alpha_n \alpha_{n-1} \beta_{n-2} \Delta w_{n-2} + \cdots + \\ & \alpha_n \alpha_{n-1} \ldots \beta_i \Delta w^{'}_i + \cdots + \\ & \alpha_n \alpha_{n-1} \ldots \alpha_2 \Delta w_2^{'} + \alpha_n \alpha_{n-1} \ldots \beta_2 \Delta w_1 \end{align}$$
其中$2 \lt i \le n-1$
整理上式得并行化公式得：
$$W^{'}_n = W_0 + \beta_n \Delta w^{'}_n + \cdots + \Pi_{j=i+1}^{n}\alpha_j\beta_i\Delta w^{'}_{i} + \cdots + \\ \Pi_{i=2}^{n}\alpha_i\Delta w^{'}_2 + \Pi_{i=3}^{n}\alpha_i\beta_2\Delta w_1$$
而串行化公式得：
$$W_n = W_0 + \sum_{i=1}^{n}\Delta w_i$$

从上式可以看出，$W^{'}_n$的最终值最后一次送入样本后的融合的关系最大。样本越靠后的，影响关系越大。而之前的样本训练越小。犹豫都取每次偏差的一定比率，所以如果在总样本数量上$\Delta w_i^{'}$比$0$小，则最终$W^{'}_n$比$W_n$大，反之小。如果样本无误差则相等。但是这个等式太忽略最初的训练样本，太依赖靠后的训练样本。如果训练样本过大的话，将可以直接忽略之前的训练。而这也是假定$\Delta w^{'}_n$与$\Delta w_n$相等的情况下。但真实的情况是$\Delta w^{'}_n$与$\Delta w_n$一个是依赖$W_0$，一个是依赖$W_{n-1}$。$W_{n-1}$是经过修订的后的权值，而$W_0$是一直没有修订过的，所以对应的误差偏差$\Delta w^{'}_n \gt \Delta w_n$。