Jacobi BP整理

1 方向导数

在自变量空间的某个位置\(w\)处，选择一个方向\(d\)（单位向量），在该方向的倒数为： \[ \nabla_df(\mathbf{w})=\lim_{\alpha \to 0}\frac{f(\mathbf{w}+\alpha \mathbf{d}) - f(\mathbf{w})}{\alpha} \] \(\alpha\)趋于0时，\(\alpha \mathbf{d}\)也趋于0，平均变化率变为瞬时变化率，即导数数。 \[ \nabla_df(\mathbf{w})=\lim_{\alpha \mathbf{d} \to 0}\frac{f(\mathbf{w}+\alpha \mathbf{d}) - f(\mathbf{w})}{\alpha \mathbf{d}} \] 方向导数就是多元函数在某位置，沿着某方向的瞬时变化率。

优化目标函数（最小化为例），就是要找到方向导数为负数且最小的方向，函数值在此方向下降最快。

下面就是使用梯度，快速找到方向导数为负数且最小的方向。

多元函数，分别优化每一个元，每个变量单独分析其偏导数。因为运动方向可以分解为多个分量的和。偏导数形式下的多元函数的函数值变化写成（二元为例）： \[ \Delta f=\frac{\partial f}{\partial w_1}\Delta w_1 + \frac{\partial f}{\partial w_2}\Delta w_2 \] 运动的距离（二维）变为： \[ \sqrt {(\Delta w_1)^2 + (\Delta w_2)^2} \] 那么，函数值在运动方向上的偏导数就是： \[ \frac {\frac{\partial f}{\partial w_1}\Delta w_1 + \frac{\partial f}{\partial w_2}\Delta w_2}{\sqrt {(\Delta w_1)^2 + (\Delta w_2)^2}} = \begin{pmatrix} \frac{\partial f}{\partial w_1}, \frac{\partial f}{\partial w_2} \end{pmatrix} \begin{pmatrix} \frac{\Delta w_1}{\sqrt {(\Delta w_1)^2 + (\Delta w_2)^2}} \\ \frac{\Delta w_2}{\sqrt {(\Delta w_1)^2 + (\Delta w_2)^2}} \end{pmatrix} \] 其中第一个向量就是函数在\(\mathbf{w}\)处的梯度，第二个向量就是\(\Delta \mathbf{w}\)的变化方向上的单位向量。

所以，多元函数的方向导数，就是该位置梯度与自变量变化方向向量的内积。也即，梯度向量在自变量变化方向向量上的投影。

那么，最优的最小化方向为，\(cos(\theta)\)为-1的自变量变化方向。即自变量变化为负梯度方向。

垂直于梯度方向时，函数值不变化。

当然梯度下降，需要设置一个较小的学习率，因为，梯度反映的是函数瞬时的变化率，只保证在当前位置的较小领域内的变化规律。

2 Jacobi

有n维向量 \(\mathbf{w}\)，经过一层网络，得到 m 维 \(f(\mathbf w)\)。 \[ \mathbf f(\mathbf w)=\begin{pmatrix} f_1(\mathbf w) \\ f_2(\mathbf w) \\ ... \\ f_m(\mathbf w) \end{pmatrix} \] 每一维为一个标量函数，可以对 n维向量 \(\mathbf{w}\)进行求偏导操作，求得梯度。得到 \[ \begin{bmatrix} \frac{\partial f_1}{\partial w_1} & ... & \frac{\partial f_1}{\partial w_n} \\ ... & ... & ... \\ \frac{\partial f_m}{\partial w_1} & ... & \frac{\partial f_m}{\partial w_n} \end{bmatrix} \] 这就是函数在 \(\mathbf{w}\) 处的Jacobi matrix。每一行是 \(\mathbf f(\mathbf w)\)的分量在\(\mathbf{w}\) 处的梯度向量。

线性近似（理解为函数在某一位置处的一阶泰勒展开并忽略高阶无穷小）的误差，是自变量变化值趋于0时，相对自变量变化值的高阶无穷小。也就是说，线性近似是用一个高阶的函数来近似低阶的原函数，而其误差可以趋于无穷小。

在多元函数中，近似关系可写为： \[ \mathbf f(\mathbf w) \approx \mathbf f(\mathbf w^*) + \mathbf J_f(\mathbf w) \cdot (\mathbf w - \mathbf w^*) \] Jacobi matrix每一行是原函数一个分量的梯度，每一维分量的近似组合成了对原函数整体的近似。

3 Back propagation with Jacobi

计算图中，一对父子节点就是一个多对多的映射，都可以求一个Jacobi matrix。

在chain rule之下，一个复合映射的Jacobi是容易求的。 \[ f(g(h(\mathbf w))) \] 其Jacobi表示为 \(\mathbf J_f(g(h(\mathbf w))) \cdot \mathbf J_g(h(\mathbf w)) \cdot \mathbf J_h(\mathbf w)\)。其中输入输出维度是相对应的。

计算图中，每个节点将结果通过，对自己的Jacobi（单位矩阵）乘上对父节点的Jacobi，将信息传递给上一层。

那么最终结果对一个节点的Jacobi，可以计算： \[ \mathbf J_f = \sum_s \mathbf J_{rs} \mathbf J_{sf} \] \(\mathbf J_{rs}\)是最终结果对s节点的Jacobi（表示累计误差BP到s的梯度），\(\mathbf J_{sf}\)是节点s对f节点的Jacobi。

class Node(object):
    """
    计算图节点基类
    """

    def __init__(self, *parents, **kargs):
        self.kargs = kargs
        self.graph = kargs.get('graph', default_graph)
        self.need_save = kargs.get('need_save', True)

        self.parents = list(parents)  # 父节点列表
        self.children = []  # 子节点列表
        self.value = None  # 本节点的值
        self.jacobi = None  # 结果节点对本节点的雅可比矩阵

        # 将本节点添加到父节点的子节点列表中
        for parent in self.parents:
            parent.children.append(self)

        # 将本节点添加到计算图中
        self.graph.add_node(self)
    
    ...
    def forward(self):
        """
        前向传播计算本节点的值，若父节点的值未被计算，则递归调用父节点的forward方法
        """
        for node in self.parents:
            if node.value is None:
                node.forward()

        self.compute()
        
    def backward(self, result):
        """
        反向传播，计算结果节点对本节点的雅可比矩阵
        """
        if self.jacobi is None:
            if self is result:  # 对自己的Jacobi
                # self.dimension()表示节点值向量的维度
                self.jacobi = np.mat(np.eye(self.dimension()))
            else:
                self.jacobi = np.mat(
                    np.zeros((result.dimension(), self.dimension())))

                for child in self.get_children():
                    if child.value is not None:  # 为None时，表示不在当前计算路径上
                        # 即为上文中的计算公式 10
                        self.jacobi += child.backward(result) * child.get_jacobi(self)

        return self.jacobi
    
    def dimension(self):
        """
        返回本节点的值展平成向量后的维数
        """
        return self.value.shape[0] * self.value.shape[1]
    
    ...

调用结果节点forworad，得到所有value属性，缓存在每个节点。调用某个节点backworad，将计算该节点的梯度保存在jacobi属性（梯度的转置，若规定梯度为列向量）中。

同时，实现Jacobi的乘法关系下的计算，可以进行推导。过程比较繁琐但是不难，直接写结果了：

矩阵 \(\mathbf C=\mathbf A \mathbf B\)，A为(m,n)维，B为(n,k)维。将三个矩阵全部展开，拼接为一个列向量。

那么C对A的Jacobi为（mk, mn） \[ \begin{bmatrix} B^T & 0 & ... & 0 \\ 0 & B^T & ... & 0 \\ ... & ... & ... & ... \\ 0 & 0 & ... & B^T \end{bmatrix} \] C对B的Jacobi为（mk, nk）的 \[ \begin{bmatrix} diagonal(a_{1,1}) & diagonal(a_{1,2}) & ... & diagonal(a_{1,n}) \\ diagonal(a_{2,1}) & diagonal(a_{2,2}) & ... & diagonal(a_{2,n}) \\ ... & ... & ... & ... \\ diagonal(a_{m,1}) & diagonal(a_{m,2}) & ... & diagonal(a_{m,n}) \end{bmatrix} \]

到此，基于Jacobi的BP计算方式，就基本没有问题了。