CS231N 解题报告
本文不包含任何代码！
Assignment 1
1 K-Nearest Neighbor
将所有数据表示为\(p\)维向量，用向量之间的欧氏距离表示数据之间的距离。对于任意测试数据，取距离最近的\(k\)个训练数据，将其中最多的那一类作为该测试数据的类别。
假设存在\(m\)个训练数据\(Train_{m\times p}\)，测试数据\(Test_{n\times p}\)，计算每个测试数据和每个训练数据之间的距离：
\[dist_{ij}=\sqrt{\sum_{k\in p}{(Test_{ik}-Train_{jk})^2}}\]1.1 直接计算
距离公式中的每一项都单独计算，二重循环。
1.2 广播
- 行广播：假设numpy数组\(M_1\)拥有形状\(r_1\times r_2\times...\times r_n\)、\(M_2\)拥有形状\(r_k\times r_{k+1}\times...\times r_n\)（\(k\in[1,n]\)），那么\(M_1\)和\(M_2\)的任何操作相当于\(M_1\)的前\(k-1\)维中的每一项都和\(M_2\)进行运算。
- 列广播：假设numpy数组\(M_1\)拥有形状\(r_1\times r_2\times...\times r_n\)、\(M_2\)拥有形状\(r_1\times r_2\times...\times r_{n-1}\times 1\)，那么\(M_1\)和\(M_2\)的任何操作相当于\(M_1\)的最后一维中的每一项都和\(M_2\)进行运算。
因而上述距离公式可以改写为：
\[dist_{i}=\sqrt{\sum_{k\in p}{(Test_{ik}-Train_{\#k})^2}}\]\(\#k\)代表矩阵第\(k\)列的列向量
循环减少为一重，但是实际上变慢了
1.3 无循环
进一步利用广播，将最后一重循环也去掉。改写原距离公式：
\[\begin{align} dist_{ij}&=\sqrt{\sum_{k}{(Test_{ik}-Train_{jk})^2}}\\ &=\sqrt{\sum_{k}{Test_{ik}^2}+\sum_{k}{Train_{jk}^2}-2\sum_{k}{Test_{ik}Train_{jk}}} \end{align}\]根号中：第一项与\(j\)无关，对\(Test\)可以列广播；第二项与\(i\)无关，对\(Train\)可以行广播；第三项正好是矩阵乘法。所以有：
\[\begin{align} dist&=\sqrt{-2\langle Test,Train^T\rangle+Te_{n\times 1}+Tr_{1\times m}} \end{align}\]其中\(Te_i=\sum_{k}{Test_{ik}^2}\)，\(Tr_j=\sum_{k}{Train_{jk}^2}\)
2 Linear SVM
One vs. All SVM，即每一类都训练一个线性SVM。二分类中得分为正则判定为正样本，多分类中得分最高的SVM对应的类别即样本所属类别。
齐次空间可统一偏移项：
\[\begin{align} Train_{n\times p}&\rightarrow TrainEx_{n\times (p+1)}=\begin{bmatrix}Train&1\end{bmatrix}\\ score=Train_{n\times p}\times W_{p\times m}+b_{m}&\rightarrow score=TrainEx_{n\times (p+1)}\times W_{(p+1)\times m} \end{align}\]取margin为1，即正确分类的得分至少应该比其它得分高1以上，采用hinge loss：
\[\begin{align} loss&=\frac{1}{n}\sum_i^n\sum_j^mmargin_{ij}\\ margin_{ij}&=\begin{cases}max(0,\langle X,W\rangle_{ij}-\langle X,W\rangle_{iy_i}+1)&j\ne y_i\\0&j=y_i\\\end{cases} \end{align}\]这里的参数只有\(W\)，并且因为只有\(margin_{ij}\neq 0\)的情况下才会对损失和梯度有贡献，因而：
\[\begin{align} \frac{\partial loss}{\partial W_{ij}}&=\frac{1}{n}\sum_k^n\sum_l^m({\nabla \langle X,W\rangle_{kl}}_ {ij} -{\nabla \langle X,W\rangle_{ky(k)}}_{ij})\\ &=\frac{1}{n}\sum_{k,margin_{kj}\gt 0}^n{X_{ki}}-\frac{1}{n}\sum_{k,y(k)=j}^n\sum_{l,margin_{kl}\gt 0}^m{X_{ki}}\\ \frac{\partial loss}{\partial W}&=\frac{1}{n}\langle X^T,M1\rangle-\frac{1}{n}\langle X^T,M2\rangle\\ &=\frac{1}{n}\langle X^T,C\rangle\\ M1_{ij}&= \begin{cases} 1&margin_{ij}>0\\ 0&otherwise \end{cases}\\ M2_{ij}&= \begin{cases} \sum_{k,margin_{ik}\gt 0}^m{1}&j=y(i)\\ 0&otherwise \end{cases}\\ C_{ij}&=M1-M2\\ &= \begin{cases} 1&margin_{ij}>0\\ -\sum_{k,margin_{ik}\gt 0}^m{1}&j=y(i)\\ 0&otherwise \end{cases} \end{align}\]3 Softmax
输入\(X_{n\times d}\)，参数\(W_{d\times c}\)，标签\(y_{n}\)
首先是线性层：
\[Score=\langle X,W\rangle\]\(Softmax\)值：
\[Softmax_{ij}=\frac{e^{Score_{ij}}}{\sum_k^c{e^{Score_{ik}}}}\]损失函数：
\[loss=-\frac{1}{n}\sum_i^n{ln(Softmax_{iy(i)})}\]梯度（参数只有\(W\)）：
\[\begin{align} \frac{\partial loss}{\partial W_{kl}}&=\sum_{i,j}\frac{\partial loss}{\partial Score_{ij}}\frac{\partial Score_{ij}}{\partial W_{kl}}\\ &=\sum_{i}\frac{\partial loss}{\partial Score_{il}}X_{ik}\\ &=\sum_{i}\frac{\partial -\frac{1}{n}\sum_j{ln(Softmax_{jy(j)})}}{\partial Score_{il}}X_{ik}\\ &=-\frac{1}{n}\sum_{i}\frac{\partial ln(Softmax_{iy(i)})}{\partial Score_{il}}X_{ik}\\ &=-\frac{1}{n}\sum_{i}\frac{\partial (Score_{iy(i)}-ln(\sum_j{e^{Score_{ij}}}))}{\partial Score_{il}}X_{ik}\\ &=-\frac{1}{n}\sum_{i}(\frac{\partial Score_{iy(i)}}{\partial Score_{il}}-Softmax_{il})X_{ik}\\ &=\frac{1}{n}\sum_{i}(Softmax_{il}-C_{il})X_{ik},C_{il}= \begin{cases} 1&l=y(i)\\ 0&l\ne y(i) \end{cases}\\ \frac{\partial loss}{\partial W}&=\frac{1}{n}\langle X^T,Softmax-C\rangle\\ \end{align}\]4 Neural Network
两层全连接神经网络，输入\(X_{N\times D}\),标签\(y_{N\times 1}\)，隐藏层\(Hidden_{N\times H}\)，输出层\(Score_{N\times C}\)
隐藏层需要加入\(ReLU\)作为激活函数
隐藏层:
\[Hidden=ReLU(\langle X,W1\rangle+b1)\]输出层：
\[Score=\langle Hidden,W2\rangle+b2\]\(Softmax\)层：
\[Softmax_{ij}=\frac{e^{Score_{ij}}}{\sum_k^C{e^{Score_{ik}}}}\]损失函数：
\[loss=\frac{1}{N}\sum_i{-ln(Softmax_{iy(i)})}\]梯度（\(W1\)，\(b1\)，\(W2\)，\(b2\)）：
\[\frac{\partial loss}{\partial W2}=\frac{1}{N}\langle Hidden^T,Softmax-C\rangle,C_{ij}= \begin{cases} 1&j=y(i)\\ 0&j\ne y(i) \end{cases}\\\] \[\begin{align} \frac{\partial loss}{\partial b2_{l}}&=\frac{1}{N}\sum_{i,j}{\frac{\partial loss}{\partial Score_{ij}} \frac{\partial Score_{ij}}{\partial b2_{l}}}\\ &=\frac{1}{N}\sum_{i,j}{(Softmax_{ij}-C_{ij})\frac{\partial Score_{ij}}{\partial b2_{l}}}\\ &=\frac{1}{N}\sum_{i}{(Softmax_{il}-C_{il})} \end{align}\] \[\begin{align} \frac{\partial loss}{\partial W1_{kl}}&=\frac{1}{N}\sum_{i,j}{\frac{\partial loss}{\partial Score_{ij}} \frac{\partial Score_{ij}}{\partial W1_{kl}}}\\ &=\frac{1}{N}\sum_{i,j}{(Softmax_{ij}-C_{ij})\frac{\partial Score_{ij}}{\partial W1_{kl}}}\\ &=\frac{1}{N}\sum_{i,j}{(Softmax_{ij}-C_{ij})\sum_{i^1j^1}\frac{\partial Score_{ij}}{\partial Hidden_{i^1j^1}} \frac{\partial Hidden_{i^1j^1}}{\partial W1_{kl}}}\\ &=\frac{1}{N}\sum_{i,j}{(Softmax_{ij}-C_{ij})\sum_{j^1}W2_{j^1j}\frac{\partial Hidden_{ij^1}}{\partial W1_{kl}}}\\ &=\frac{1}{N}\sum_{i,j}{(Softmax_{ij}-C_{ij})W2_{lj}D_{il}X_{ik}},D_{il}= \begin{cases} 1&Hidden_{il}\ge 0\\ 0&Hidden_{il}\lt 0 \end{cases}\\ \frac{\partial loss}{\partial W1}&=\frac{1}{N}\langle X^T,\langle Softmax-C,W2^T\rangle\circ D\rangle \end{align}\] \[\begin{align} \frac{\partial loss}{\partial b1_{l}}&=\frac{1}{N}\sum_{i,j}{\frac{\partial loss}{\partial Score_{ij}} \frac{\partial Score_{ij}}{\partial b1_{l}}}\\ &=\frac{1}{N}\sum_{i,j}{(Softmax_{ij}-C_{ij})\frac{\partial Score_{ij}}{\partial b1_{l}}}\\ &=\frac{1}{N}\sum_{i,j}{(Softmax_{ij}-C_{ij})\sum_{j^1}W2_{j^1j}D_{ij^1}\frac{\partial Layer1_{ij^1}}{\partial b1_{l}}}\\ &=\frac{1}{N}\sum_{i,j}{(Softmax_{ij}-C_{ij})W2_{lj}D_{il}}\\ &=\frac{1}{N}\sum_{i}(\langle Softmax-C,W2^T\rangle\circ D)_{il} \end{align}\]预测:
\[{pred_i}=argmax(Score_i)\]Assignment 2
1 Fully Connected Network
相当于Neural Network的细化版，具体到每一子层的正向与反向
1.1 仿射
\[\begin{align} y&=\langle x,w\rangle+b\\ dx&=\langle dy,w^T\rangle\\ dw&=\langle x^T,dy\rangle\\ db&=\sum_i{dy_i} \end{align}\]1.2 ReLU
\[\begin{align} y&=max(0,x)\\ dx&= \begin{cases} dy&x\ge 0\\ 0&x\lt 0\\ \end{cases} \end{align}\]用这个网络训练时L2项的系数为0.5
1.3 SGD+Momentum
梯度下降时带上“惯性”，将每次梯度的变化量看作动量，动量会按一定比例保留到下一次迭代中去
\[\begin{align} p&=\lambda p-lr\cdot dw\\ w&=w+p \end{align}\]其中\(-lr\cdot dw\)为实际的梯度，\(\lambda\)为动量保留比例，\(p\)为动量即参数的增量
1.4 RMSProp
\[\begin{align} l&=\lambda l+(1-\lambda)\cdot dw^2\\ w&=w-\frac{lr\cdot dw}{\sqrt{l}+\epsilon} \end{align}\]其中\(l\)代表过去梯度的L2范数的滑动平均值，\(\epsilon\)用于防止除以\(0\)的出现
1.5 Adam
\[\begin{align} m&=\beta_1\cdot m+(1-\beta_1)\cdot dw\\ m_t&=\frac{m}{1-\beta_1^t}\\ v&=\beta_2\cdot v+(1-\beta_2)\cdot dw^2\\ v_t&=\frac{v}{1-\beta_2^t}\\ w&=w-\frac{lr\cdot m_t}{\sqrt{v_t}+\epsilon} \end{align}\]2 Batch Normalization
训练时计算每个batch的均值与方差，归一化至\(0\)均值、\(1\)方差，新增参数\(\gamma\)作为新标准差，\(\beta\)作为新均值，将batch反归一化
测试时由于没有batch的概念，所以需要训练时将均值和方差用滑动平均的方式记录下来：
\[\begin{align} mean&=p\cdot mean+(1-p)\cdot batch\_mean\\ variance&=p\cdot variance+(1-p)\cdot batch\_variance \end{align}\]测试时用\(mean\)和\(variance\)分别代替训练时的\(batch\_mean\)和\(batch\_variance\)
Batch Normalization层一般加在线性层之后激活层之前，所以全连接层的顺序应该是Affine->BatchNorm->ReLU
2.1 BatchNorm
均值与方差：
\[\begin{align} u&=\frac{1}{n}\sum_i^nX_i\\ \sigma^2&=\frac{1}{n}\sum_i^n(X_i-u)^2+\epsilon\\ \end{align}\]归一化与输出层：
\[y_i=\gamma\frac{X_i-u}{\sigma}+\beta\]梯度（\(X\)，\(\gamma\)，\(\beta\)）：
\[\begin{align} dX_{ij}&=\sum_k{dy_{kj}\frac{\partial y_{kj}}{\partial X_{ij}}}\\ &=\gamma_j\sum_k{dy_{kj}\frac{\partial \frac{X_{kj}-u_j}{\sigma_j}}{\partial X_{ij}}}\\ &=\gamma_j\sum_k{dy_{kj}\frac{\sigma_j \frac{\partial(X_{kj}-u_j)}{\partial X_{kj}}-(X_{kj}-u_j)\frac{\partial \sigma_j}{\partial X_{kj}}}{\sigma_j^2}}\\ &=\frac{\gamma_j dy_{ij}}{\sigma_j}-\frac{1}{n}\sum_k{\frac{\gamma_j dy_{kj}}{\sigma_j}}-\frac{\gamma_j}{\sigma_j^2}\sum_k{dy_{kj}(X_{kj}-u_j)\frac{\partial \sigma_j}{\partial X_{ij}}}\\ &=\frac{\gamma_j dy_{ij}}{\sigma_j}-\frac{1}{n}\sum_k{\frac{\gamma_j dy_{kj}}{\sigma_j}}-\frac{\gamma_j}{2n\sigma_j^3}\sum_k{dy_{kj}(X_{kj}-u_j)\sum_l{\frac{\partial (X_{lj}-u_j)^2}{\partial X_{ij}}}}\\ &=\frac{\gamma_j dy_{ij}}{\sigma_j}-\frac{1}{n}\sum_k{\frac{\gamma_j dy_{kj}}{\sigma_j}}-\frac{\gamma_j}{n\sigma_j^3}\sum_k{dy_{kj}(X_{kj}-u_j)\sum_l{(X_{lj}-u_j)\frac{\partial (X_{lj}-u_j)}{\partial X_{ij}}}}\\ &=\frac{\gamma_j dy_{ij}}{\sigma_j}-\frac{1}{n}\sum_k{\frac{\gamma_j dy_{kj}}{\sigma_j}}-\frac{\gamma_j}{n\sigma_j^3}\sum_k{dy_{kj}(X_{kj}-u_j)(X_{ij}-u_j)}\\ &=\frac{\gamma_j dy_{ij}}{\sigma_j}-\frac{1}{n}\sum_k{\frac{\gamma_j dy_{kj}}{\sigma_j}}-\frac{(X_{ij}-u_j)}{n}\sum_k{\frac{\gamma_j dy_{kj}}{\sigma_j^3}(X_{kj}-u_j)}\\ dX_i&=\frac{\gamma dy_{i}}{\sigma}-\frac{1}{n}\sum_k{\frac{\gamma dy_{k}}{\sigma}}-\frac{(X_{i}-u)}{n}\sum_k{\frac{\gamma dy_{k}}{\sigma^3}(X_{k}-u)}\\ dX&=\frac{\gamma dy}{\sigma}-\frac{\gamma}{n\sigma}\sum_i{dy_{i}}-\frac{\gamma(X-u)}{n\sigma^3}\sum_i{dy_i(X_{i}-u)} \end{align}\] \[\begin{align} d\gamma&=\frac{1}{\sigma}\sum_i{dy_{i}(X_i-u)}\\ d\beta&=\sum_i{dy_{i}} \end{align}\]2.2 LayerNorm
TODO
3 Dropout
TODO
4 CNN
TODO