HW1

• 问题一为实现基本运算的前向计算，基本调用numpy的api较为容易实现；

• 问题二为实现基本运算的梯度计算，需要注意reshape, transpose, broadcast_to, summation 等操作的梯度计算。

• 问题三为实现拓扑排序。

• 问题四为实现计算图的反向传播过程。

• 问题五位实现softmax损失函数的设计；

• 问题六为实现两层神经网络的设计。

问题一

Transpose_forward

• 当axes 为空时，ndl是想交换最后两个轴，因传入numpy api的参数axes=list(range(len(a.shape)))[:-2] + list(range(len(a.shape)))[-2::-1]，即一段不变，最后两个轴交换位置。

• 当axes不为空的时候，其中必定有两个数值，代表需要交换的两个轴。因此，首先令 axes=list(range(len(a.shape)))，然后令其中对应两个数值的位置交换一下即可。

def compute(self, a):
        ### BEGIN YOUR SOLUTION
        _axes = list(range(len(a.shape)))
        if self.axes:
            _axes[self.axes[0]], _axes[self.axes[1]] = _axes[self.axes[1]], _axes[self.axes[0]]
        else:
            # 默认交换的是最后两个轴
            _axes = _axes[:-2] + _axes[-2:][::-1]
        return array_api.transpose(a, _axes)
        ### END YOUR SOLUTION

问题二

reshape_backward

transpose_backward

broadcast_to_backward

• ndim 不变的，仅仅改变 tensor 的shape，如shape 从(10, 1) 到(10, 5) 。且第二维只能从 1到5，不可能从 2到5。

• ndim也改变的，如 shape从 (10, 2)到(5, 10, 2)

• broadcast 后，如果没有改变ndim，那么 shape 改变的那部分，只能是从1到别的数值。

• broadcast 后，如果改变了ndim，那么 多出来的轴一定在前面。例如 (10, 2)到(5, 10, 2) 多出来轴在最开始。

def gradient(self, out_grad, node):
        ### BEGIN YOUR SOLUTION
        ori_shape = node.inputs[0].shape

        # 存储待压缩的轴
        axes_ = []
        # 1. 处理 ndim 的 broadcast, 这里 broadcast 增加的dim 必定是在 较低的轴，所以计算出来增加了几个，然后从0到几就是了
        axes_ += list(range(len(self.shape)-len(ori_shape)))        
        # 2, 处理形状的 broadcast,倒着往回检查不一样的
        for i in range(-1, -len(ori_shape)-1, -1):
            # 不相同，必定是 broadcast了
            if ori_shape[i] != self.shape[i]:
                assert ori_shape[i] == 1
                axes_.append(i)

        axes_ = tuple(axes_)
        return reshape(summation(out_grad, axes=axes_), ori_shape)

summation_backward

def gradient(self, out_grad, node):
        ### BEGIN YOUR SOLUTION
        ori_shape = node.inputs[0].shape
        # temp_shape 用来保存 做了sum但是keepdim住的shape, 因为要利用该shape做广播
        # 如果 self.axes 不存在，则最后的维度为(1,),此时keepdim住的shape： temp_shape = [1] * len(sum之前的dims)
        # 如果 self.axes 存在，那么此时keepdim住的shape: 初始shape中 self.axes对应轴变为 1
        temp_shape = list(ori_shape)
        if self.axes:
            for i in self.axes:
                temp_shape[i] = 1
        else:
            for i in range(len(temp_shape)):
                temp_shape[i] = 1
        # 不涉及 out_grad.size 的改变
        temp_node = reshape(out_grad, temp_shape)
        # 2.booadcast: 涉及到 out_grad.size 的改变
        return broadcast_to(temp_node, ori_shape)
        ### END YOUR SOLUTION

matmul_backward

def gradient(self, out_grad, node):
        ### BEGIN YOUR SOLUTION
        lhs, rhs = node.inputs
        l_grad = matmul(out_grad, transpose(rhs))
        r_grad = matmul(transpose(lhs), out_grad)

        # 如果 ndim 不一样，把多出来的 dim 对应的轴sum起来 ,多出来的轴一定是前面的
        # Tensor没有实现 .ndim 函数，因此只能通过 len(a.shape) 来得到 ndim
        l_grad_ndim, r_grad_ndim = len(l_grad.shape), len(r_grad.shape)
        lhs_ndim, rhs_ndim = len(lhs.shape), len(rhs.shape)
        if l_grad_ndim > lhs_ndim:
            axes = tuple(range(l_grad_ndim - lhs_ndim))
            l_grad = summation(l_grad, axes)
        if r_grad_ndim > rhs_ndim:
            axes = tuple(range(r_grad_ndim - rhs_ndim))
            r_grad = summation(r_grad, axes)

        return l_grad, r_grad
        ### END YOUR SOLUTION

问题三

def find_topo_sort(node_list: List[Value]) -> List[Value]:
    """Given a list of nodes, return a topological sort list of nodes ending in them.

    A simple algorithm is to do a post-order DFS traversal on the given nodes,
    going backwards based on input edges. Since a node is added to the ordering
    after all its predecessors are traversed due to post-order DFS, we get a topological
    sort.
    """
    ### BEGIN YOUR SOLUTION
    topo_order = []
    visited = set()
    for cur_node in node_list:
        topo_sort_dfs(cur_node, visited, topo_order)
    return topo_order
    ### END YOUR SOLUTION


def topo_sort_dfs(node, visited, topo_order):
    """Post-order DFS"""
    ### BEGIN YOUR SOLUTION
    if node in visited:
        return
    for in_node in node.inputs:
        topo_sort_dfs(in_node, visited, topo_order)
    topo_order.append(node)
    visited.add(node)
    ### END YOUR SOLUTION

问题四 Implementing reverse mode differentiation

for node in reverse_topo_order:
        # 先计算当前节点 v_i 的梯度 = sum(node_to_output_grads_list[node])
        node.grad = sum(node_to_output_grads_list[node])
        # 叶子节点不再继续回传了
        if node.is_leaf():
            continue
        # 再计算 v_{j->i} 的梯度
        in_nodes_grads = node.op.gradient_as_tuple(node.grad, node)
        # 最后 分别把 v_{j->i} 赋给 node_to_output_grads_list[v_j]
        for in_node, grad in zip(node.inputs, in_nodes_grads): # The gradient of an operation
            node_to_output_grads_list[in_node].append(grad)
    ### END YOUR SOLUTION

问题五 Softmax loss

l = ndl.log(ndl.summation(ndl.exp(Z), axes=(1,)))
r = ndl.summation(ndl.multiply(Z, y_one_hot), axes=(1,))
return ndl.divide_scalar(ndl.summation(l - r), l.shape[0])

问题六 SGD for a two-layer neural network

• 需要把 类别标签转为 onehot 矩阵。

• 参数更新的时候，要么只更新 Tensor里面的 data，要么直接换一个Tensor，不必要对参数的Tensor 进行 -= 操作，因为 Tensor的运算会创建出来计算图。

for i in range(0, X.shape[0], batch):
        X_ = X[i: i+batch]
        y_ = y[i: i+batch]

        X_ = ndl.Tensor(X_, dtype="float32")
        Z = ndl.matmul(ndl.relu(ndl.matmul(X_, W1)), W2)

        y_one_hot = np.zeros(Z.shape)
        y_one_hot[np.arange(y_.shape[0]), y_] = 1.
        y_one_hot = ndl.Tensor(y_one_hot, dtype='int8')

        loss = softmax_loss(Z, y_one_hot)
        loss.backward()
        
        W1 = ndl.Tensor(W1.realize_cached_data() - lr * W1.grad.realize_cached_data(), dtype="float32")
        W2 = ndl.Tensor(W2.realize_cached_data() - lr * W2.grad.realize_cached_data(), dtype="float32")

    return W1, W2

注意事项

• 在读取数据parse_mnist函数中，数据类型只能的B，不能是b。B表示 unsigned char, b 表示 signed char。如下代码

struct.unpack(f'>{row_num * cols_num}B', img_file.read(row_num * cols_num))

• Tensor 类 没有实现 ndim 方法，需要手动 通过 len(a.shape) 来计算ndim

知识点

• sum() 这个 python 内置的方法，参数为一个可迭代容器，会遍历相加，具体相加的方法 是由容器内 数据类型决定的。例如，容器内为numpy.ndarray 类型，那么就会执行 numpy中的 ndarray 对象加法函数。

• 每个节点的inputs的长度 一定是和 该节点 gradient返回的节点数量相同的。

• 在 某个节点 输入为 tensor和ndarray 的运算中，计算完成后，存储下来的输入只有tenosr，回传梯度的时候，也只返回一项。

• 在 和标量的计算中，标量的数据类型其实是 ndarray。这类标量不会被存储在计算图中。

• 在 多个（大于2）Tensor的计算中，永远是两两计算的，即先计算两个tenosr的结果，然后得到一个 节点，再用这个得到的节点来和另外的 计算。