Abstract

标准的policy gradietn每一次更新需要一个样本，本文提出的PPO能够使用minibatch更新。PPO有着TRPO的优势，但是更容易实现，更普遍，更好的采样复杂度。

Introduction

Policy Gradient

目标函数：
$$ L^{PG} (\theta) = \hat{\mathbb{E}}_t \left[\log \pi_{\theta}(a_t|s_t)\hat{A}_t \right] \tag{1}$$
约束条件：
$$\vert d\theta\vert^2 \le \delta \tag{2}$$

Natural Policy Gradient

目标函数：
$$ L^{NPG} (\theta) = \hat{\mathbb{E}}_t \left[\log \pi_{\theta}(a_t|s_t)\hat{A}_t \right]\tag{3}$$
约束条件：
$$\hat{\mathbb{E}}_t\left[\text{KL}\left[\pi_{old}(\cdot|s_t), \pi_{\theta}(\cdot|s_t)\right] \right] \tag{4}$$
等价于
$$\frac{1}{2} d\theta^T \text{H} d\theta \le \delta \tag{5}$$

Trust Region Policy Optimization

目标函数：
$$ L^{PG} (\theta) = \hat{\mathbb{E}}_t \left[\frac{\pi_{\theta}(a_t|s_t)}{\pi_{old}(a_t|s_t)}\hat{A}_t \right]\tag{6}$$
约束条件：
$$\hat{\mathbb{E}}_t\left[\text{KL}\left[\pi_{old}(\cdot|s_t), \pi_{\theta}(\cdot|s_t)\right] \right] \tag{7}$$

Proximal Policy Optimization

目标函数：
$$L^{PPO}(\theta) =\hat{\mathbb{E}}_t \left[L_t^{CLIP+VF+S}(\theta) - \beta\text{KL}\left[\pi_{old}(\cdot|s_t), \pi_{\theta}(\cdot|s_t) \right] \right] \tag{8}$$
其中$S$表示entropy bonus。
$$L_t^{CLIP}(\theta) = \hat{\mathbb{E}}_t \left[\min(\frac{\pi_{\theta}(\cdot|s_t)}{\pi_{old}(\cdot|s_t)},\ clip(\frac{\pi_{\theta}(\cdot|s_t)}{\pi_{old}(\cdot|s_t)}, 1-\epsilon, 1+\epsilon) \hat{A}_t) \right]\tag{9}$$
$$L_t^{VF} = (V_{\theta}(s_t) - V_t^{targ} )^2 \tag{10}$$

参考文献

1.https://arxiv.org/pdf/1707.06347.pdf
2.https://medium.com/@jonathan_hui/rl-proximal-policy-optimization-ppo-explained-77f014ec3f12

简介

共轭梯度(conjugate method)方法是一种迭代法。
共轭梯度收敛的快慢取决于系数矩阵谱分解的情况。特征集集中，系数矩阵的条件数很小，收敛的就快。

核心

解线性对称正定方程组（$A$是对称正定矩阵）：
$$Ax=b$$
可以转化为
$$\min_x f(x) = \frac{1}{2} x^T Ax - b^T x$$
因为：
$$f’(x) = Ax-b$$

和其他迭代法的对比

参考文献

1.https://tangxman.github.io/2015/11/18/optimize-gradient/
2.https://www.zhihu.com/question/27157047
3.https://www.zhihu.com/question/27157047/answer/121950241
4.https://www.zhihu.com/question/27157047/answer/171336970
5.https://blog.csdn.net/lusongno1/article/details/78550803
6.https://medium.com/@jonathan_hui/rl-conjugate-gradient-5a644459137a

无偏估计的方差下界 cramer-rao bound

理论上可以证明，任何无偏估计的方差都有一个下界，这个下界叫做cramer-rao bound。具体的证明好复杂，这里只是简单说一下。如果证明算法无偏估计量的方差的下界是cramer-rao bound，说明这个算法的下界已经没有优化了。。。这个下界其实很多时候不知道什么时候能取到，到时能给我们一定的信息，就像期望一样。

它的最简单形式是：任何无偏估计的方差至少大于fisher information的倒数。

Efficient

Efficient说的是在所有的无偏估计方法中，如果某种方法中无偏估计的方差等于cramer-rao bound，那么这个方法就是efficient。（应该是这样子吧。。。）

Asymptotically

在样本有效的情况下，统计量的方差不好计算。但是当样本不断增大时，方差会逐渐接近一个定值。用asymptotically修饰不断增大趋向于无穷的样本数量。

Asymptotically Efficient

Asymptotically efficient指得是某种方法在小样本时可能不是efficient的，但是随着样本数量不断增加，变成了efficient的，这种方式就是asymptotically efficient的。

参考文献

渐进有效性
1.https://www.zhihu.com/question/285834087/answer/446120288
2.https://bbs.pinggu.org/thread-2139008-1-1.html
3.https://www.zhihu.com/question/28908532/answer/254617423
4.https://en.wikipedia.org/wiki/Efficiency_(statistics)#Asymptotic_efficiency
5.https://cs.stackexchange.com/questions/69819/what-does-it-mean-by-saying-asymptotically-more-efficient
cramer-rao bound
6.https://www.zhihu.com/question/24710773/answer/117796031
7.http://www2.math.ou.edu/~kmartin/stats/cramer-rao.pdf
8.https://www.zhihu.com/question/311561435/answer/607730638
9.https://zhuanlan.zhihu.com/p/27644403

获得数组长度

1
2

int a[] = {1, 2, 3, 4};
l = sizeof(a)/sizeof(int);

printf输出格式

%d 有符号十进制整数(int)
%ld, %Ld 长整形数据(long)
%i 有符号十进制数，和%d一样
%u 无符号十进制整数(unsigned int)
%lu, %Lu 无符号十进制长整形数据(unsigned long)
%f 单精度浮点数(float)
%c 单字符(char)
%o 无符号八进制整数
%x(%X) 十六进制无符号整数

c类型字符串数组

1. 导包

1

#include <string.h>

2. 完整字符串复制

1

strcpy(des, src);

3. 部分字符串复制

1

strncpy(des, src+n, len);

4. 结束符

1

sub[len] = '\0';

5. new字符串数组

1

char *str = new char[100];

6. delete字符串数组

1

delete []str;

生成随机数

1
2
3
4
5

#include <time.h>
#include <stdlib.h>

srand(time(NULL));   // Initialization, should only be called once.
int r = rand();      // Returns a pseudo-random integer between 0 and RAND_MAX.

计算函数运行时间

计算实际运行时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include<cstdlib>
#include<cstdio>
#include<ctime>
#include<sys/time.h>
#include<unistd.h>


//struct timeval
//{
//     long tv_sec;//秒域
//     long tv_usec;//微秒域
//}
//int getimeofday(struct timeval* tv,NULL);

int main()
{

    struct timeval  tv1, tv2;
    gettimeofday(&tv1, NULL);
    sleep(2);
    gettimeofday(&tv2, NULL);

    printf ("Total time = %f seconds\n",
         (double) (tv2.tv_usec - tv1.tv_usec) / 1000000 +
         (double) (tv2.tv_sec - tv1.tv_sec));
    return 0;
}

计算cpu运行时间

clock()返回的是OS花了多少时间运行当前的进程。

1
2
3
4
5
6
7
8
9
10
11

#include<ctime>

int main()
{

    clock_t start, end;
    start = clock();
    time.sleep(10);
    end = clock()
    print("%f", (double)(end-start)/CLOCK_PER_SEC);
}

参考文献

1.https://stackoverflow.com/questions/822323/how-to-generate-a-random-int-in-c
2.https://blog.csdn.net/zhangwei_zone/article/details/11219757
3.https://stackoverflow.com/questions/5248915/execution-time-of-c-program

score function

最大似然估计

根据最大似然估计，有似然对数：
$$l = \log p(x|\theta)$$

score function

根据似然对数，定义一个score function：
$$s(\theta) = \nabla_{\theta} \log p(x|\theta) $$
即score是似然对数的一阶导（梯度），似然对数是标量，score function是似然对数对$\theta$的导数。

Fisher information

当$\theta$是标量的时候。

score function的期望

定理 score function的期望是$0$
证明：
\begin{align*}
\mathbb{E}_{p(x|\theta)}\left[s(\theta)\right] & = \mathbb{E}_{p(x|\theta)}\left[\nabla \log p(x|\theta)\right]\\
&=\int \nabla \log p(x|\theta) p(x|\theta) dx\\
&=\int \frac{\nabla p(x|\theta)}{p(x|\theta)} p(x|\theta) dx\\
&=\int \nabla p(x|\theta) dx\\
&=\nabla \int p(x|\theta) dx\\
&=\nabla 1\\
&= 0
\end{align*}
即似然对数梯度向量的期望为是$0$。

第一种意义：score function的方差

用$I(\theta)$表示fisher information，它的定义就是score function（似然对数的一阶导）的方差：
$$I(\theta) = \mathbb{E} \left[ \left(\frac{\partial}{\partial \theta} \log f(\mathbf{X}; \theta) \right)^2 |\theta \right] = \int \left( \frac{\partial}{\partial \theta} \log f(\mathbf{X}; \theta) \right)^2 f(x;\theta)dx$$

随机变量的Fisher information总是大于等于$0$的，Fisher information不是某一个observation的函数。

第二种意义：参数真实值处似然对数二阶导期望的相反数

$$I(\theta) = - \mathbb{E}\left[ \frac{\partial^2 }{\partial \theta^2 } \log f(\mathbf{X}; \theta) |\theta \right] $$
Fisher informaction可以看成似然对数对参数估计的能力，在最大似然的估计值附近，fisher信息大代表着图像陡而尖，参数估计能力好；fisher信息小代表着图像宽而平，参数估计能力差。

第三种意义：Cramer-Rao bound的不正式推导

Fisher informaction的导数是$\theta$无偏估计值方差的下界。换句话说，$\theta$的精确度被似然对数的fisher information限制了。

Fisher information Matirx

当$\theta$是多维变量的时候。

Preliminary

1.雅克比矩阵和海塞矩阵

第一种意义：协方差矩阵

$$I(\theta) = \mathbb{E}\left[s(\theta) s(\theta)^T\right]$$
根据协方差矩阵的定义：
$$\Sigma = \mathbb{E}\left[(X-\mathbb{E}(X))(X-\mathbb{E}(X))^T \right]$$
所以$s(\theta)$的协方差矩阵为：
$$\Sigma = \mathbb{E}_{p(x|\theta)} \left[(s(\theta)-0)(s(\theta) - 0)^T \right] = \mathbb{E}_{p(x|\theta)} \left[(s(\theta)s(\theta)^T \right] $$

第二种意义：Fisher information matrix和Hessian matrix

Fisher information matrix $F$等于似然对数的二阶导数（海塞矩阵），也是score function的一阶导，期望的负数。
$$I(\theta) = - \mathbb{E}\left[ \frac{\partial^2 }{\partial \theta^2 } \log f(\mathbf{X}; \theta) |\theta \right] $$

证明：
\begin{align*}
\text{H}_{\log p(x \vert \theta)} &= \text{J} \left( \nabla \log p(x \vert \theta) \right) \\
&= \text{J} \left( \frac{\nabla p(x \vert \theta)}{p(x \vert \theta)} \right) \tag{log-derivative-trick}\\
&= \frac{ \text{H}_{p(x \vert \theta)} , p(x \vert \theta) - \nabla p(x \vert \theta) , \nabla p(x \vert \theta)^{\text{T}}}{p(x \vert \theta) , p(x \vert \theta)} \tag{分数求导}\\
&= \frac{\text{H}_{p(x \vert \theta)} , p(x \vert \theta)}{p(x \vert \theta) , p(x \vert \theta)} - \frac{\nabla p(x \vert \theta) , \nabla p(x \vert \theta)^{\text{T}}}{p(x \vert \theta) , p(x \vert \theta)} \\
&= \frac{\text{H}_{p(x \vert \theta)}}{p(x \vert \theta)} - \left( \frac{\nabla p(x \vert \theta)}{p(x \vert \theta)} \right) \left( \frac{\nabla p(x \vert \theta)}{p(x \vert \theta)}\right)^{\text{T}} \\
\end{align*}
第一个等号是$\log p$的海塞矩阵（二阶导）等于$\nabla \log p$（一阶导）的雅克比矩阵。
对上式取期望，得到：
\begin{align*}
\mathop{\mathbb{E}}_{p(x \vert \theta)} \left[ \text{H}_{\log p(x \vert \theta)} \right] &= \mathop{\mathbb{E}}_{p(x \vert \theta)} \left[ \frac{\text{H}_{p(x \vert \theta)}}{p(x \vert \theta)} - \left( \frac{\nabla p(x \vert \theta)}{p(x \vert \theta)} \right) \left( \frac{\nabla p(x \vert \theta)}{p(x \vert \theta)} \right)^{\text{T}} \right] \\
&= \mathop{\mathbb{E}}_{p(x \vert \theta)} \left[ \frac{\text{H}_{p(x \vert \theta)}}{p(x \vert \theta)} \right] - \mathop{\mathbb{E}}_{p(x \vert \theta)} \left[ \left( \frac{\nabla p(x \vert \theta)}{p(x \vert \theta)} \right) \left( \frac{\nabla p(x \vert \theta)}{p(x \vert \theta)}\right)^{\text{T}} \right] \\
&= \int \frac{\text{H}_{p(x \vert \theta)}}{p(x \vert \theta)} p(x \vert \theta) , \text{d}x , - \mathop{\mathbb{E}}_{p(x \vert \theta)} \left[ \nabla \log p(x \vert \theta) , \nabla \log p(x \vert \theta)^{\text{T}} \right] \\
&= \text{H}_{\int p(x \vert \theta) , \text{d}x} , - \text{F} \\
&= \text{H}_{1} - \text{F} \\
&= -\text{F} \\
\end{align*}
最后得到：$\mathbf{F} = - \mathop{\mathbb{E}}_{p(x \vert \theta)} \left[ \mathbf{H}_{\log p(x|\theta)}\right] $

Fisher information matrix和KL散度

两个分布$p(x|\theta)$和$p(x|\theta’)$在$\theta’=\theta$处，KL散度的海塞矩阵等于fisher information matrix。
证明：
$$\text{KL}\left[p(x|\theta)||p(x|\theta’)\right] = \int_x p(x|\theta)\log p(x|\theta)dx - \int_x p(x|\theta)\log p(x|\theta’)dx$$
关于$\theta’$的一阶导为：
\begin{align*}
\nabla_{\theta’} \text{KL}\left[p(x|\theta)||p(x|\theta’)\right] & = \nabla_{\theta’}\int_x p(x|\theta)\log p(x|\theta)dx - \nabla_{\theta’}\int_x p(x|\theta)\log p(x|\theta’)dx\\
& = - \int_x p(x|\theta) \nabla_{\theta’} \log p(x|\theta’)dx\\
\end{align*}
关于$\theta’$的二阶导为：
\begin{align*}
\nabla_{\theta’}^2 \text{KL}\left[p(x|\theta)||p(x|\theta’)\right] &=- \int_x p(x|\theta) \nabla_{\theta’} \log p(x|\theta’)dx \\
&= - \int \nabla_{\theta’} p(x|\theta)\nabla_{\theta’} \log p(x|\theta’) - \int p(x|\theta)\nabla_{\theta’}^2 \log p(x|\theta’) dx\\
&= - \int p(x|\theta)\nabla_{\theta’}^2 \log p(x|\theta’) dx\\
\end{align*}
当$\theta’ = \theta$时：
\begin{align*}
\text{H}_{KL\left[ p(x|\theta)||p(x|\theta’)\right]} & = - \int p(x|\theta)\nabla_{\theta’}^2 \log p(x|\theta’)|_{\theta’=\theta} dx\\
& = - \int p(x|\theta) H_{\log p(x|\theta)} dx\\
& = - \mathbb{E}_{p(x|\theta)}\left[H_{\log p(x|\theta)} \right]\\
& = \text{F}\\
\end{align*}

参考文献

1.https://en.wikipedia.org/wiki/Fisher_information
2.https://math.stackexchange.com/a/265933
3.https://www.zhihu.com/question/26561604/answer/33275982
4.https://wiseodd.github.io/techblog/2018/03/11/fisher-information/
5.https://wiseodd.github.io/techblog/2018/03/14/natural-gradient/
6.https://math.stackexchange.com/questions/2239040/show-that-fisher-information-matrix-is-the-second-order-gradient-of-kl-divergenc

Gym Retro

什么是Gym Retro？

将不同平台的video games都转换成gym environments。Gym-retro包括了RLE和ALE两个环境，可以使用统一的gym接口进行管理，更灵活，更容易扩展。

创建gym retro的目的

此前transfer learning in RL，有两种通用的evaluation：

• 在人工合成的task上进行evaluation
• 在ALE环境上进行evaluation
  这两种方式都有缺陷：前者的话不同的算法之间很难比较，后者的话，效果很差，因为不同的游戏之间差异可能很大。
  本文的提出的gym-retro可以：

1. 作为few-shot RL的benchmark，从一个single task distribution中sampling许多simlar tasks。
2. 作为transfer learning的benchmark，提供cross-task的dataset。划分train/test让agent学会在some levels进行explore，迁移到其他levels。

包含哪些平台

• Atari
• NEC
• Nintndo
• Sega

包含哪些ROMs

• the 128 sine-dot by Anthrox
• Sega Tween by Ben Ryves
• Happy 10! by Blind IO
• 512-Colour Test Demo by Chris Covell
• Dekadrive by Dekadence
• Automaton by Derek Ledbetter
• Fire by dox
• FamiCON intro by dr88
• Airstriker by Electrokinesis
• Lost Marbles by Vantage

Sonic benchmark

Gym Retro

Sonich benchmark的底层实现是Gym Retro，它可以提供接口给诸如RLE game将其封装成gym environment。
每个game由ROM, 一个或者多个save states，一个或者多个scenarios，还有一个data file。

• ROM：组成game的代码和数据。
• Save state：console’s state的截图。
• Data file：描述各种各样的information在console memory的哪个地方存着。
• Scenario：描述done conditions和reward functions。

Sonic game

Sonic benchmark中有三个相似的游戏：$Sonic The Hedgehog^{TM} $, $Sonic The Hedgehog^{T} 2$, $Sonic 3 Knuckles$，这些游戏具有相似的规则，可能有一些差别，但是不大。
每个Sonic game都有zones，每个zone又被划分成acts。每个zone有独特的纹理和物体；每个zone中的act有相同的问题，但是布局不同。一个(ROM, zone, act)被称为一个level。

Games and Levels

Sonic benchmark中所有的games总共有$58$个save states，每一个save state对应一个不同的level。
选取test set的时候随机选取超过$1$个act的zones，然后从中随机选取一个act。这样子，test set中巨大部分的纹理和物体都在training set中出现过，只不过layouts不同。所有的test levels如下：

Frame skip

step()方法的调用频率是$60$hz，dqn中经常使用的frames skip为$4$，Sonic benchmark也用了，用timestep表示使用了frame skip之后一步的时长，也就是$\frac{4}{60}$。
Sonic benmeark对frame skip做了一些改变，叫做stick frame skip。对于agent的action加了一些随机性：每隔$n$帧之后的那一帧，有$0.25$的概率继续应用之前的那个action。

Episode boundaries

游戏中的experience划分为episodes，大概对应有几条命。每一个episode结束，重置到相应的save state。每个episodes结束的条件有以下几种：

• 通关，去掉了boss，通过水平方向上一个特定的偏移量就算通关。
• 少了一条命
• 当前episode累计玩了$4500$个timesteps，大概是$5$分钟。

Observations

24位RBG图像，Sonic是$320 \times 224 $

Actions

所有的Sega Genesis游戏的action space包含：
B, A, MODE, START, UP, DOWN, LEFT, RIGHT, C, Y, X, Z
Sonic game中有八个很重要的buttion combinations:
{ {}, {LEFT}, {RIGHT}, {LEFT, DOWN}, {RIGHT, DOWN}, {DOWN}, {DOWN, B}, {B} }

Rewards

在一个episode中，cumulative reward和玩家的初始位置到当前位置的偏移是成正比的。也就是说往右走产生正的reward，往左走产生负的reward。
Reward由horimontal offset和completion bonus构成。Completion bonus是$1000$，在$4500$个timesteps内线性降为$0$。
但是imediate reward可能是有欺骗性的，有时候为了获得更大的reward往回走是必须的。

Evaluation

使用test set中所有levels的mean score作为metric。步骤入如下：

1. 训练时候，使用任意数量的训练集（你喜欢多少就用多少）训练
2. 测试的时候，每一个test levels执行$100$万个timesteps。在test每一个level的时候都是分开的。
3. 对每个level的$100$万个timesteps中所有episode的total rewards进行平均。
4. 对所有test level的scores进行平均。

这个$100$万是怎么选出来的？在无限个timestep的场景下，没有证明meta-learning或者transfer-learning是必要的，但是在有限个timestep的场景下，transfer learning对于得到好的performance是很必要的。

Baselines

• Humans：四个玩家，每个玩家在training levels上训练两个小时。然后在每个test level玩一个小时。
• RainBow：设置$V_{max} = 200$，replay buffer从$1M$改成了$0.5$M，直接使用Rainbow的初值。Action space：{ {LEFT}, {RIGHT}, {LEFT, DOWN}, {RIGHT, DOWN}, {DOWN}, {DOWN, B}, {B} }。Agent的reward是基于agent到过的最大$x$，这样子不会惩罚它往回走。
• JERK：并没有使用depp learning，叫JERK(Just Enough Retained Knowledge)。使用一个简单的算法进行explore，然后回放训练过程中的best action。因为环境是stochasitc，不知道哪个action是最好的，因此次他仅仅是一个mean。
• PPO：在每个test levels上，单独的调用PPO。和Rainbow的action，observation spaces一样，CNN架构和ppo论文中一样。超参数：
  Hyper-parameter|Value
  :-😐:-:
  Workers|1
  Horizon|8192
  Epochs|4
  Minibatch size|8192
  Discount ($\gamma$) | 0.99
  GAE parameter ($\lambda$) | 0.95
  Clipping parameter ($\epsilon$)|0.2
  Entropy coeff.|0.001
  Reward scale|0.005
• Joint PPO：从training levels迁移到test levels，在training levels上训练一个policy，然后用它作为test levels的初始化。
  在meta-learning过程中，训练一个single-policy玩training set中的每一个level。具体的，运行$188$个parallel works，每个worker运行training set中的一个level。在每一个gradient step，对所有workers的gradients进行平均，确保policy在整个training set上的训练是平稳的。整个过程需要几百个millions timesteps才会收敛。参数设置和PPO一样。
  在所有training sets上完成训练以后，使用这个网络在作为test set中网络的初始化，除了使用meta-learning的结果进行初始化，所有的其他过程和PPO一样。
• Joint Rainbow：和Joint PPO的训练过程一样。
  没有joint training的Rainbow超过了PPO，但是joint Rainbow没有超过joint PPO。在整个训练集上训练单个Rainbow的时候，使用了$32$个GPUs。每一个GPU对应一个单个的worker，每一个worker有自己的replay buffer和$8$个环境。环境也是joint environments，在每一个episode开始的时候采样一个新的tranining level。
  除了batch size和distributed worker，其他的超参数和常规的Rainbow一样。

示例

安装gym retro

1

pip3 install gym-retro

创建Gym Env

下面代码创建一个gym环境

1
2

import retro
env = retro.make(game='Airstriker-Genesis')

retro中的environment是从gym.Env类继承而来的。

默认ROM

Airstriker-Genesis的ROM是默认包含在gym-retro之中的，其他的一些ROMs需要手动添加。

所有的games

1
2

import retro
retro.data.list_games()

上述代码会列出所有的游戏，包含那些默认没有集成的ROMS中的。

手动添加ROMs

1

python3 -m retor.import /path/to/your/ROMs/directory

上述代码将存放在某个路径下的ROMs拷贝到Gym Retro的集成目录中去。

参考文献

1.https://retro.readthedocs.io/en/latest/
2.https://arxiv.org/pdf/1804.03720.pdf

导数

导数表示函数在该点的变化率。
$$f’(x) = lim_{\Delta x\rightarrow 0}\frac{\Delta y}{\Delta x} = lim_{\Delta x\rightarrow 0} \frac{f(x+\Delta x) - f(x)}{ \Delta x}$$
更直接的来说，导数表示自变量无穷小时，函数值的变化与自变量变化的比值，几何意义是该点的切线。物理意义表示该时刻的瞬时变化率。

偏导数

偏导数是多元函数沿着坐标轴的变化率。
在一元函数中，只有一个自变量，也就是只存在一个方向上的变化率，叫做导数。对于多元函数，有两个及以上的自变量。从导数到偏导数，相当于从曲线到了曲面，曲线上的一点只有一条切线，而曲面上的一点有无数条切线。我们把沿着坐标轴上的切线的斜率叫做偏导数。

方向导数

多元函数沿着任意向量的变化率。

梯度

多元函数取最大变化率时的方向向量。
对于三元函数，计算公式：
$$\nabla f = \frac{\partial f}{\partial x}i+\frac{\partial f}{\partial y}j + \frac{\partial f}{\partial z}j$$
梯度到底是行向量还是列向量？取决于使用什么layout。
梯度的公式是$\frac{\partial{y}}{\partial\mathbf{x}}$，
如果使用numerator layout，梯度是行向量；
如果使用denominator layout，梯度是列向量。

全微分

函数从$A$点到离它无穷近的$B$点的变化量。
对于二元函数，定义为
$$dz = \frac{\partial f}{\partial x}dx+\frac{\partial f}{\partial y}dy$$

区别和联系

导数，偏导数和方向导数都是个向量，它们其实都是一个概念。偏导数和导数都是方向导数的特殊情况。
梯度是个向量，它指向最陡峭的上升方向，这个时候方向导数最大。

参考文献

1.https://www.zhihu.com/question/36301367/answer/142096153
2.https://math.stackexchange.com/questions/661195/what-is-the-difference-between-the-gradient-and-the-directional-derivative

按位与

定义

两个运算对象，相同为$0$，不同为$1$。

示例

十进制的
$0, 1, 2, 3, 4, 5, 6, 7, 8$
对应的二进制为
$0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000$
判断十进制数中每一个二进制位是否是$1$。
$1$分别左移$i=0,1,2,3$位，然后与要判断的二进制数进行按位与，如果不是$0$，则说明第$i$位为$1$。

应用

1. 判断一个数是不是$2$的幂，再进一步就是统计一个数二进制位为$1$的个数。
   $2$的幂有一个特征，就是只有一个二进制是$1$，其余的所有位都是$0$。
   而$2$的幂减去$1$会得到所有的二进制位都是$1$，他们按位与，得到所有的二进制位是$0$，即$(2$ ^ $n)$&$(2$ ^ $n-1) = 0$，实际上，这个公式会消去二进制位最右边的一个$1$。
2. 按位与实现掩码运算。

按位异或

定义

两个运算对象，相同为$0$，不同为$1$。

规则

只要谨记这两条规则就好。

• 任意两个相等的数亦或都为$0$。
• $0$与任何数亦或都等于那个数。
• 两个有符号数异或，如果符号相同，结果大于$0$，否则小于$0$。

交换律

$a$^$b$ = $b$^$a$

结合律

$a$ ^ $b$ ^ $c$ = $a$ ^ ($b$ ^ $c$)

示例

$12 ^{} 7 = 11$

$12 = 1100$
$7 = 0111$
按位异或得到
$1011 = 11$

$1$ ^ $2$ ^ $3$ ^ $4$ ^ $1$ ^ $2$ ^ $3$ ^ $4$ ^ $5$ = $1$ ^ $1$ ^ $2$ ^ $2$ ^ $3$ ^ $3$ ^ $4$ ^ $4$ ^ $5$
分别对每一位异或，对于每一位来说，其实他们都是没有顺序的，只需要统计每一位有多少个$0$和$1$即可了，重复偶数次的值都相互抵消了，剩下的就是没有抵消的那些。

移位

左移位

$1 \ll 2 $
相当于
$0001 \ll 2 = 0100 = 4$

右移位

$8 \gg 2$
相当于
$1000 \gg 2 = 0010 = 2$

移位和与

移位和与结合起来判断某一位二进制位是否是$1$。

示例

判断$13$从右数的的第$3$个二进制位是否为$1$。

1
2
3
4

if(13 >> 1 & 1)
{
    printf("true\n");
}

什么是log derivative trick

$$\nabla_{\theta} log p(\mathbf{x}; \theta) = \frac{\nabla_{\theta} p(\mathbf{x}; \theta)}{ p(\mathbf{x}; \theta)}$$

为什么？

导数公式：
$$(log_a x)’ = \frac{1}{x ln\ a}$$
$$(ln\ x)’ = \frac{1}{x}$$
所以：
$$(ln\ p(\mathbf{x};\theta))’ = \frac{1}{p(\mathbf{x}; \theta)}$$
\begin{align*}
\nabla_{\theta} ln\ p(\mathbf{x};\theta) &=\left[\frac{\partial ln\ p(\mathbf{x}; \theta)}{\partial \theta} \right]^T \\
&= \left[\frac{\partial ln\ p(\mathbf{x}; \theta)}{\partial p(\mathbf{x};\theta)}\frac{\partial p(\mathbf{x};\theta)}{\partial \theta} \right]^T \\
&= \left[\frac{1}{ p(\mathbf{x};\theta)}\frac{\partial p(\mathbf{x};\theta)}{\partial \theta} \right]^T \\
&= \frac{1}{ p(\mathbf{x};\theta)}\left[\frac{\partial p(\mathbf{x};\theta)}{\partial \theta} \right]^T \\
&=\frac{\nabla_{\theta}p(\mathbf{x}; \theta)}{p(\mathbf{x}; \theta)}\\
\end{align*}

其实就是$\nabla log\ p = \frac{\nabla p}{p}$。

参考文献

1.https://math.stackexchange.com/questions/2554749/whats-the-trick-in-log-derivative-trick

符号声明

小写字母$x,y$是标量，小写加粗字母$\mathbf{x},\mathbf{y}$是向量，大写加粗$\mathbf{X},\mathbf{Y}$是矩阵。标量和向量都可以看成是矩阵，将vector看成$1\times n$或者$m\times 1$的矩阵，将scalar看成$1\times 1$的矩阵。$\mathbf{X}^T $表示矩阵$\mathbf{X}$的转置，$tr(\mathbf{X})$表示迹，即对角线元素之和。$det(\mathbf{X})$或者$\vert \mathbf{X}\vert$表示行列式。

基础

迹

$$ tr(\mathbf{A}) = tr(\mathbf{A}^T )$$
$$ tr(\mathbf{A}\mathbf{B}) = tr(\mathbf{B}\mathbf{A})$$
$$ tr(\mathbf{A}+\mathbf{B}) = tr(\mathbf{B})+tr(\mathbf{A})$$

行列式

…

简介

矩阵微积分值得是使用矩阵或者向量表示因变量中每一个元素相对于自变量中每一个元素的导数。一般来说，自变量和因变量都可以是标量，向量和矩阵。

示例

考虑向量梯度，给定三个自变量，一个因变量的函数：$f(x_1, x_2, x_3)$，向量的梯度是：
$$\nabla f= \frac{\partial f}{\partial x_1}\mathbf{i} + \frac{\partial f}{\partial x_2}\mathbf{j} + \frac{\partial f}{\partial x_3}\mathbf{k}$$
其中$\mathbf{i,j,k}$表示坐标轴正方向上的单位向量。这类问题可以看成标量$f$对向量$x$求导数，结果依然是一个向量（梯度）：
$$\nabla f=(\frac{\partial f }{\partial \mathbf{x}})^T = \left[\frac{\partial f}{\partial x_1} + \frac{\partial f}{\partial x_2} + \frac{\partial f}{\partial x_3}\right]^T $$

更复杂的情况是标量$f$对矩阵$\mathbf{X}$求导，叫做矩阵梯度(gradient matrix)。标量，向量，矩阵的组合总共有$9$中情况，其中六种情况可以用以下方式表示出来：

用途

Matrix calculus通常用于优化，常常用在拉格朗日乘子法中。包括Kalman滤波，高斯混合分布的EM算法，梯度下降法的的导数。

向量导数

向量可以看成只有一列的矩阵，最简单的矩阵导数应该是标量导数，然后是向量导数。这一节使用的是numerator layout（分子布局）。

向量对标量求导

标量对向量求导

向量对向量求导

矩阵导数

矩阵对标量求导

标量对矩阵求导

Layout

事实上，有两种定义矩阵导数的方式，这两种方法刚好差一个转置。这也是我们平常矩阵求导最容易迷惑的地方。
求向量对向量的导数时，即$\frac{\partial \mathbf{y}}{\partial \mathbf{x}}, \partial \mathbf{x} \in \mathbb{R}^n , \partial \mathbf{y} \in \mathbb{R}^m $，有两种方式表示，一种结果是$m\times n$的矩阵，一种是$n\times m$的矩阵。这就有以下的layout：

1. Numetator layout，根据$\partial \mathbf{y}$和$\partial \mathbf{x}^T $进行布局。也叫Jacobian 公式，最后是一个$m\times n$的矩阵。
2. Denominator layout，根据$\partial \mathbf{y}^T $和$\partial \mathbf{x}$进行布局。也叫Hessian公式，最后是一个$n\times m$的矩阵，是numetator layout的转置。也有人把它叫做梯度，但是梯度通常指的是$\frac{\partial y}{\partial \mathbf{x}}$，即标量对向量求导，不需要考虑layout。

在计算梯度$\frac{\partial y}{\partial \mathbf{x}}$和$\frac{\partial\mathbf{y}}{\partial x}$的时候，也会有冲突。

1. 采用分子layout，$\frac{\partial y}{\partial \mathbf{x}}$是行向量和$\frac{\partial\mathbf{y}}{\partial x}$是列向量。
2. 采用分母layout，$\frac{\partial y}{\partial \mathbf{x}}$是列向量和$\frac{\partial\mathbf{y}}{\partial x}$是行向量。

最后计算标量对矩阵求导$\frac{\partial y}{\partial \mathbf{X}}$和矩阵对标量求导$\frac{\partial\mathbf{Y}}{\partial x}$。

1. 采用分子layout，$\frac{\partial y}{\partial \mathbf{X}}$和$\mathbf{Y}$的shape一样，$\frac{\partial\mathbf{Y}}{\partial x}$和$\mathbf{X}^T $的shape一样。
2. 采用分母layout，$\frac{\partial y}{\partial \mathbf{X}}$和$\mathbf{Y}$的shape一样，这里不用转置这是因为这样子好看。$\frac{\partial\mathbf{Y}}{\partial x}$和$\mathbf{X} $的shape一样。

接下来的公式主要对$\frac{\partial \mathbf{y}}{\partial x}, \frac{\partial y}{\partial \mathbf{x}}, \frac{\partial \mathbf{y}}{\partial \mathbf{x}}, \frac{\partial \mathbf{Y}}{\partial x},\frac{\partial y}{\partial \mathbf{X}}$这种组合分别考虑。

numerator layout

标量对向量求导：
$\frac{\partial y}{\partial \mathbf{x}} = \begin{bmatrix}\frac{\partial y}{\partial x_1} & \cdots &\frac{\partial y}{\partial x_n}\end{bmatrix}$
向量对标量求导：
$\frac{\partial \mathbf{y}}{\partial x} = \begin{bmatrix}\frac{\partial y_1}{\partial x} \\ \vdots \\ \frac{\partial y_m}{\partial x}\end{bmatrix}$
向量对向量求导：
$\frac{\partial \mathbf{y}}{\partial \mathbf{x}} = \begin{bmatrix}\frac{\partial y_1}{\partial x_1} & \cdots & \frac{\partial y_1}{\partial x_n} \\ \vdots \\ \frac{\partial y_m}{\partial x_1} & \cdots & \frac{\partial y_m}{\partial x_n}\end{bmatrix}$
标量对矩阵求导：
$\frac{\partial y}{\partial \mathbf{X}} = \begin{bmatrix}\frac{\partial y}{\partial x_{11}} & \cdots & \frac{\partial y}{\partial x_{p1}} \\ \vdots \\ \frac{\partial y}{\partial x_{1q}} & \cdots &\frac{\partial y}{\partial x_{pq}}\end{bmatrix}$

下列公式只有numerator layout，没有denominator-layout：
矩阵对标量求导：
$\frac{\partial \mathbf{Y}}{\partial x} = \begin{bmatrix}\frac{\partial y_{11}}{\partial x}&\cdots \frac{\partial y_{1n}}{\partial x} \\ \vdots \\ \frac{\partial y_{m1}}{\partial x} & \cdots & \frac{\partial y_{mn}}{\partial x}\end{bmatrix}$
矩阵微分：
$dx = \begin{bmatrix}dx_{11} & \cdots & dx_{1n} \\ \vdots \\ dx_{m1} & \cdots & dx_{mn}\end{bmatrix}$

denominator layout

标量对向量求导：
$\frac{\partial y}{\partial \mathbf{x}} = \begin{bmatrix}\frac{\partial y}{\partial x_1} & \cdots &\frac{\partial y}{\partial x_n}\end{bmatrix}$
$\frac{\partial y}{\partial \mathbf{x}} = \begin{bmatrix}\frac{\partial y}{\partial x_1} \\ \cdots \\ \frac{\partial y}{\partial x_n}\end{bmatrix}$
向量对标量求导：
$\frac{\partial \mathbf{y}}{\partial x} = \begin{bmatrix}\frac{\partial y_1}{\partial x} & \vdots & \frac{\partial y_m}{\partial x}\end{bmatrix}$
向量对向量求导：
$\frac{\partial \mathbf{y}}{\partial \mathbf{x}} = \begin{bmatrix}\frac{\partial y_1}{\partial x_1} & \cdots & \frac{\partial y_m}{\partial x_1} \\ \vdots \\ \frac{\partial y_1}{\partial x_n} & \cdots & \frac{\partial y_m}{\partial x_n}\end{bmatrix}$
标量对矩阵求导：
$\frac{\partial y}{\partial \mathbf{X}} = \begin{bmatrix}\frac{\partial y}{\partial x_{11}} &\cdots & \frac{\partial y}{\partial x_{1q}} \\ \vdots \\ \frac{\partial y}{\partial x_{p1}} & \cdots & \frac{\partial y}{\partial x_{pq}}\end{bmatrix}$

公式

向量对向量求导公式

标量对向量求导公式

向量对标量求导公式

标量对矩阵求导公式

矩阵对标量求导公式

标量对标量求导公式

微分形式的公式

通常来说使用微分形式然后转换成导数更简单。但是只有在使用numerator layout才起作用。

其中$\mathbf{A}$不是$\mathbf{X}$的函数，$a$不是$\mathbf{X}$的函数，上面的公式可以根据链式法则迭代使用。
上面的绝大部分公式可以使用$\mathbf{F}(\mathbf{X} + d\mathbf{X}) - \mathbf{F}(\mathbf{X})$计算，取线性部分可以得到，例如：
$$(\mathbf{X} + d\mathbf{X}) (\mathbf{Y} + d\mathbf{Y}) = \mathbf{X}\mathbf{Y} + (d\mathbf{X})\mathbf{Y} + \mathbf{X}d\mathbf{Y} + (d\mathbf{X})(d\mathbf{Y})$$
然后得到$d(\mathbf{X}\mathbf{Y})= (d\mathbf{X})\mathbf{Y}+\mathbf{X}(d\mathbf{Y})$。
计算$d\mathbf{X}^{-1} $，有
$$0 = d\mathbf{I} = d(\mathbf{X}^{-1} \mathbf{X}) = (d(\mathbf{X}^{-1}) \mathbf{X} + \mathbf{X}^{-1} d(\mathbf{X})$$
移项得$d(\mathbf{X}^{-1} ) = - \mathbf{X}^{-1} (d\mathbf{X}) \mathbf{X}^{-1} $
关于迹的公式，有：
$$tr(\mathbf{X} + d\mathbf{X}) - tr(\mathbf{X}) = tr(d\mathbf{X})$$

下面给出导数和微分之间转换的标准公式，我们的目标就是使用上面的公式将一些复杂的公式转换成下面的标准公式。

微分和导数的转换

有一个很重要的公式是：
$$tr(\mathbf{A}\mathbf{B}) = tr(\mathbf{B}\mathbf{A})$$

示例

$$\frac{d}{d\mathbf{X}} tr(\mathbf{A}\mathbf{X}\mathbf{B}) = tr(\mathbf{A}\mathbf{B})$$
因为：
$$d tr(\mathbf{A}\mathbf{X}\mathbf{B}) = tr(d(\mathbf{A}\mathbf{X}\mathbf{B})) = tr(\mathbf{A}d(\mathbf{X})\mathbf{B}) = tr(\mathbf{B}\mathbf{A}d(\mathbf{X})) $$
对应$\frac{d\mathbf{Y}}{dx} = \mathbf{A}$。

二次型

计算二次型$\mathbf{x}^T \mathbf{A}\mathbf{x}$的导数，因为$\mathbf{x}^T \mathbf{A}\mathbf{x}$是一个标量，所以可以套上一个$tr$操作：
$$\frac{d(\mathbf{x}^T \mathbf{A}\mathbf{x})}{d\mathbf{x}}= \mathbf{x}^T (\mathbf{A}^T + \mathbf{A})$$
推导：
\begin{align*}
d(\mathbf{x}^T \mathbf{A}\mathbf{x}) &= tr(d(\mathbf{x}^T \mathbf{A}\mathbf{x})) \\
&= tr(d(\mathbf{x}^T) \mathbf{A}\mathbf{x} + \mathbf{x}^T d(\mathbf{A}) \mathbf{x} + \mathbf{x}^T \mathbf{A}d(\mathbf{x})) \\
&= tr(\mathbf{x}^T \mathbf{A}^T d(\mathbf{x}) + \mathbf{x}^T \mathbf{A}d(\mathbf{x})) \\
&= tr(\mathbf{x}^T (\mathbf{A}^T + \mathbf{A})d(\mathbf{x}))\\
\end{align*}
满足$dy = \mathbf{a}d\mathbf{x}$。所以$\mathbf{x}^T \mathbf{A}\mathbf{x}$的导数是$\mathbf{x}^T (\mathbf{A}^T +\mathbf{A})$。

参考文献

1.https://en.wikipedia.org/wiki/Matrix_calculus
2.https://zhuanlan.zhihu.com/p/24709748
3.https://zhuanlan.zhihu.com/p/24863977
4.math.uwaterloo.ca/~hwolkowi/matrixcookbook.pdf
5.http://www.iro.umontreal.ca/~pift6266/A06/refs/minka-matrix.pdf