# Credit
+ 授课教师： [梁红瑾](hongjin-liang.github.io)
+ 上课时间：2025秋
+ 主要是分成`lambda calculus`和`semantics`两部分



# Lambda Calculus
之前就听说过不少，SICP课上还被Church Numeral折磨过

### 定义
$(Terms) M,N\ ::=\ x\ | \lambda x.M\ |\ M\ N$

### 规则
+ $\lambda$延伸到括号的最右方 $\lambda x.\ M\ N$意思是$\lambda x.\ (M\ N)$
+ 函数应用是左结合 $M\ N\ P$意思是$(M\ N)\ P$

### 自由和约束变量
+ $\lambda x.(x+y)$相等于$\lambda z.(z+y)$, $x$是绑定变量(bound variables)
+ 但自由变量的名字很重要
+ fv(M)是M中自由变量的集合
    + $fv(x) \overset{\mathrm{def}}{=} {x}$
    + $fv(\lambda x.M) \overset{\mathrm{def}}{=} fv(M)-{x}$
    + $fv(M\ N) \overset{\mathrm{def}}{=} fv(M) \cup fv(N) $
+ $\alpha$等价: $\lambda x.M=\lambda y.M[y/x]$ y是新变量

### 化简规则
+ $\beta$化简： $(\lambda x.M)N \rightarrow M[N/x]$
+ 替换规则
    + $x[N/x] \overset{\mathrm{def}}{=} N$
    + $y[N/x] \overset{\mathrm{def}}{=} y$
    + $(M P)[N/x] \overset{\mathrm{def}}{=} (M[N/x]) (P[N/x])$
    + $(λx.M)[N/x] \overset{\mathrm{def}}{=} λx.M$
    + $(λy.M)[N/x] \overset{\mathrm{def}}{=} λy.(M[N/x]), if\ y ∉ fv(N)$
    + $(λy.M)[N/x] \overset{\mathrm{def}}{=} λz.(M[z/y][N/x]), if\ y ∈ fv(N)\ and\ z\ fresh$
### 合流性
Terms可以以任何顺序化简，如果有最终结果的话，其唯一确定。
+ $\beta-redex$  类似$(\lambda x.M)N$形式的term
+ $\beta-normal\ form$ 不含$\beta-redex$的term
+ 合流性理论:
    + 对于所有的$M,M_1,M_2$,如果$M\rightarrow^*M_1$且$M\rightarrow^*M_2$,那么存在$M'$使得$M_1\rightarrow^*M'$且$M_2\rightarrow^*M'$
+ $Normal-order\ reduction:$最外层的最左边的redex(有点像lazy evaluation)
    + $(\lambda u.\lambda v.v)((\lambda x.x\ x)(\lambda x.x\ x))\rightarrow \lambda v.v$
+ $Applicative-order\ reduction:$最内层的最左边的redex(有点像eager evaluation)
    + $(\lambda u.\lambda v.v)((\lambda x.x\ x)(\lambda x.x\ x))\rightarrow (\lambda u.\lambda v.v)((\lambda x.x\ x)(\lambda x.x\ x)) ...$
### 求值和化简
+ 化简可以在lambda函数体内化简，但是求值不在lambda函数体内化简
+ 下图中evaluation会停在第三个后
![](https://ys.al/static/img/7df8299e4ae28b0a19ac5f0a74fbdaea.image.webp)
+ ![](https://ys.al/static/img/80566dcadcb54402e0454158a415ace7.image.webp)
+ 范式(canonical form)意思是不能再求值的form, 但可能范式内部（lambda内部）可以继续化简
### 对于常用值的编码
+ $True \overset{\mathrm{def}}{=} \lambda x.\lambda y.x$
+ $False \overset{\mathrm{def}}{=} \lambda x.\lambda y.y$
+ True是取第一个, False是取第二个，因此在此上面进行的运算也是根据这个性质进行的
+ $0 \overset{\mathrm{def}}{=} \lambda f.\lambda x.x$ 
+ $n \overset{\mathrm{def}}{=} \lambda f.\lambda x.f^n\ x$ 
+ n是运算n次
### 不动子
+ $F = \lambda f.\,\lambda n.\,\text{if }(n=0)\text{ then }1\text{ else } n \cdot f(n-1).$ 则$fact = F\ fact$
+ 图灵不动子
    + $A\ =\ \lambda x.\lambda y.y(x\ x\ y)$, $\Theta=A A$
+ Curry不动子
    + $Y=\lambda f.(\lambda x.f (x\ x)) (\lambda x.f (x\ x))$
 
# Simply-Typed Lambda Calculus
### 定义
+ $(\text{Types})\quad \tau, \sigma ::= T \mid \sigma \to \tau$
+ $\Gamma \vdash M : \tau$. $\Gamma$中有所有的自由变量定义
### Soundness
+ 对于任何$M,M',\tau$如果$· \vdash M:\tau$且$M\to^*M'$那么$· \vdash M':\tau$并且要么$M'\in Values$或者$\exist M''.M'\to M''$
+ Preservation: M,M' and $\tau$, 如果$·\vdash M:\tau$且$M\to M'$那么$·\vdash M':\tau$
+ Progress:如果$· \vdash M:\tau$那么要么$M\in Values$或者$\exist M'.M\to M'$
### Not Complete
+ 这个类型系统可能会拒绝不会出错的程序
+ 有完善类型的term永远会终止
### Curry-Howard同构
+ 如果把基础类型看成命题，函数类型看成蕴含，乘积类型看成and，那么构造性命题逻辑和类型系统同构！
+ 测试类型是否非空:(对应的term是否closed)
    + 看这个对应的命题是否能被证明
+ 排中律：在命题逻辑中，一个命题要么真要么假，因此命题$p\lor(p\to q)$永远为真。
    + 但是STLC不支持这一点，它要求必须确定或两边到底哪个为真。因此如果需要用到它，则必须把它作为一个明显的假设
# 操作语义
我们希望探寻语句究竟**怎么算**

### 定义
+ $(States)\quad \sigma \in Var \to Values$
+ $(IntExp)\quad e::=\textbf{n}|x|e+e|e-e|...$
+ $(Comm) c::=\textbf{skip}|x:=e|c;c|\textbf{if}\ b\ \textbf{then}\ c\ \textbf{else}\ c|\textbf{while}\ b\ \textbf{do}\ c$
+ 注意while的小步语义不要丢失b
### 小步语义的性质
+ 对于所有$c,\sigma,c',\sigma ',c'',\sigma ''$, 如果$(c,\sigma)\to(c',\sigma ')$并且$(c,\sigma)\to (c'',\sigma '')$, 那么$(c',\sigma ')=(c'',\sigma '')$ 确定性
+ 对于所有$c,\sigma,c',\sigma ',c'',\sigma ''$, 如果$(c,\sigma)\to^*(c',\sigma ')$并且$(c,\sigma)\to^* (c'',\sigma '')$, 那么存在$c''',\sigma'''$使得$(c',\sigma ')\to^*(c''',\sigma ''') and (c'',\sigma '')\to^*(c''',\sigma ''')$ 合流性
+ $(e,\sigma)$和$(b,\sigma)$是normalizing的（最终会到达一个normal form），但$(c,\sigma)$不一定
### 拓展
+ 直接对表达式求值
+ ![](https://ys.al/static/img/c4a19e539f90bf6164c8327a21ca13b4.image.webp)
+ 我们不希望把局部变量暴露给$\sigma$因此对于局部变量定义
    + ![](https://ys.al/static/img/7964ad5df14db26abf075fadfd14e364.image.webp)
    + 仍然包裹局部变量定义，但执行一步
+ 添加堆
+ Contextual Semantics
    + 我们考虑用`[]`指代下一步要算的`redex`即原子操作，
    + $\mathcal{E} ::= [\,]\mid \mathcal{E} + e\mid \mathcal{E} - e\mid n+\mathcal{E}\mid n - \mathcal{E}$
    + $x:=1+[\ ]\ NOT\ while\ false\ do\ x:=1+[\ ]$ (不该出现)
    + ![](/static/img/5743d755080786a1193fea567291639f.image.webp)
### 大步语义
+ 直接得知最后的结果
+ $(c,\sigma)\Downarrow \sigma';(e,\sigma)\Downarrow n$
+ For all $e,\sigma,n,n',$ 如果$(e,\sigma)\Downarrow n$且$(e,\sigma)\Downarrow n'$那么$n=n'$ 确定性
+ 对于所有$e,\sigma$存在$n$使得$(e,\sigma)\Downarrow n$ 整体性Totality
+ $(e,\sigma)\lfloor \textbf{n}\rfloor\ iff.\ (e,\sigma)\to^*(\textbf{n},\sigma)$和小步语义等价
# 霍尔逻辑
### 定义
+ 偏正确性定义: $\{p\}c\{q\}$
+ 全正确性定义: $[p]c[q]$ (偏正确性+一定终止)
### 核心规则
+ AS: $\{p[e/x]\}x:=e\{p\}$
+ 增强前条件、减弱后条件
+ 循环不变式:
    + $\{i\land b\}c\{i\}$
    + 有时候需要增强`loop invarient`来证明循环后的内容
+ 循环变量:
    + $[i\land b\land (e=x_0)]c[i\land(e<x_0)]$ $i\land b \Rightarrow e\ge0$
    + 递减且有界
+ 在应用顺序规则的时候，需要先标注出二者之间的条件(assertation)
### Soundness and completeness
+ 注意$|-$和$|=$的区别，$|-$是在某个公理系统中可以推导出来的,$|=$代表在某个配置下是真的
+ Soundness: 如果$|-p$那么$|=p$
+ Completeness: 如果$|=p$那么$|-p$
+ 我们可以证明Soundness: 如果$|-\{p\}c\{q\}$那么$|=\{p\}c\{q\}$
    + 先对于公理证明
    + 然后利用小步语义进行归纳法
+ 但是霍尔逻辑并不complete:
    + ![](https://ys.al/static/img/8ca7abe482b7de33f0e6a11d637764ce.image.webp)
    + 如果complete的话，那么任意语义为真的命题都能被证明(与哥德尔不完备定理冲突)
    + $|=\{\textbf{true}\}c\{\textbf{false}\}$ 当且仅当c不停止才成立，然而c是否停止是不可判定的
+ 因此提出`Relative Completeness`相对完备，如果我们把所有语义为真的命题作为已知条件，那么completeness成立

程序设计语言的形式语义笔记

# 事件起因:
我需要微调一个多模态大模型，为了压缩图片输入的token数量，防止上下文数量过长导致训练时间和效果变差，在多模态大模型的```Vision Encoder```后加入一个模块用于把每张图片的token数压缩至32个.



# 奇妙的bug
我加入的模块大概长这样:
```python
def apply_compress(self, features):
    """
    features: [image_size,original_token,hidden_dim]
    """
    new_image_feature = []
    for i in range(image_size):
        new_image_feature.append(compress(features[i]))
    
    return new_image_feature
```
省去了很多细节，在训练的时候，奇怪的事情发生了: 在单卡上训练速度很正常，但一旦我切换到双卡, 训练在第一个batch都没完成的情况下就卡死了(batch_size=1)

经过排查，我发现rank0和rank1都执行到了这个函数, rank0的image_size为47, rank1的image_size为24. 在rank1处理完所有的图片后, rank0和rank1一起卡死.

# 问题解决
我一开始以为是compress函数有问题(但其实它是一个库函数), 结果发现我对torch的多卡运算有误,下面直接贴出AI的解释:

您好！从您提供的详尽代码和问题描述来看，这是一个非常典型的分布式训练（DDP, Distributed Data Parallelism）中遇到的 **死锁（Deadlock）或挂起（Hang）** 问题。

根本原因在于：**在分布式训练中，每个进程（GPU/rank）的计算图和执行路径必须完全一致。而您当前的代码和数据加载方式破坏了这个核心原则。**

### 问题根源：执行路径不一致导致同步失败

在 PyTorch DDP 中，`forward` 传播过程会记录模型中每个参数参与的运算。在 `backward` 传播时，DDP 会为每个参数注册一个钩子（hook），当该参数的梯度计算完成后，DDP 会立即启动一个异步的 `AllReduce` 操作，将所有进程上的这个梯度进行求和平均，从而保证所有进程的梯度一致。

这个机制能正常工作的前提是：**所有进程必须以完全相同的顺序、对完全相同的参数集计算梯度**。如果任何一个进程的计算路径与其他进程不同，就会导致：

  * 某个进程期望收到一个它永远不会收到的梯度（因为它没有执行相应的计算）。
  * 或者，进程之间 `AllReduce` 的顺序错乱。

这两种情况都会导致某些进程无限期地等待其他进程，从而造成整个训练过程的挂起。

#### 1\. 罪魁祸首：不同数量的图像 (47 vs 24)

您描述的场景是问题的核心：

  * **Rank 0** 加载了包含 **47** 个图像的样本。
  * **Rank 1** 加载了包含 **24** 个图像的样本。

  * **执行次数不同**：Rank 0 的 `for` 循环会执行 47 次，而 Rank 1 只会执行 24 次。
  * **计算图不同**：这意味着 `self.compress` 这个模块（它是一个拥有独立参数的神经网络）在 Rank 0 上被调用了 47 次，而在 Rank 1 上只被调用了 24 次。
  * **DDP 崩溃**：当反向传播开始时，Rank 0 会计算 47 次 `compress` 的梯度，并准备进行 47 次相应的 `AllReduce` 同步。而 Rank 1 只会计算 24 次。当 Rank 1 完成它自己的 24 次计算和同步后，它就会进入等待状态。与此同时，Rank 0 在完成了 24 次同步后，会继续尝试发起第 25 次 `AllReduce`，但此时它永远等不到 Rank 1 的响应，因为 Rank 1 的计算图里已经没有这个操作了。于是，Rank 0 就被永久地卡住了。

您遇到的问题是 DDP 的经典陷阱。其核心是由于**数据不均匀（不同数量的图像）导致了模型中带参数模块（`PerceiverResampler`）的调用次数不一致**，破坏了 DDP 要求的“计算图一致性”原则，从而在梯度同步时发生死锁。

**最直接的解决方案是：修改您的数据加载和预处理流程，确保送入模型的每个 batch 在所有 GPU 上的结构（尤其是可变长度的元素，如图像数量）都是统一的，通常通过填充（Padding）来实现。**

# 后续的拓展
只有需要梯度的模块才要求计算图相同.

记录一次奇妙的debug流程

+ 计算集群通常分为登录节点和计算节点. 为了数据安全，通常只有登录节点有网，而计算节点没网。
+ 可以使用```module load xxx```来加载一些软件的环境包.
+ 使用sinfo查看可用的计算节点
![](https://ys.al/static/img/59cdf6b28f87354b4eed24112215dbf6.image.webp)
+ ssh连接上的一般是登录节点，可以使用sbatch或者srun提交作业. srun是交互性的命令, sbatch是批处理命令
+ 一个sbatch脚本案例:
```bash
#!/bin/bash
#SBATCH -o job.%j.out 
#SBATCH -p gpu
#SBATCH -J train_test
#SBATCH --nodes=1 
#SBATCH --ntasks-per-node=1
#SBATCH -G 1
#module load miniconda
#module load cuda/12.2
nvidia-smi
```
解释:
```bash
-p 即计算节点的分区
-o 计算作业的输出重定向到哪个文件
--nodes 一共需要几个节点
--ntasks-per-node 一个节点几个人物
--G 需要几张显卡
```
+ 也可以使用srun:
```bash
srun --gres=gpu:1 --pty xxx
```

高性能计算集群使用指北

# 强化学习基本组件
+ Actor 你的策略 (一般来说你只可以控制这个)
+ Environment 环境
+ Reward Function 奖励函数



# Policy Gradient 学习Actor
+ 策略Policy一般用$$\pi$$表示, 用$$\pi_\theta$$来表示参数为$\theta$的策略
+ 策略的输入通常是对环境的一个观察，输出是动作的概率分布
+ 我们可以这样建模一次完整的轨迹Trajectory(也许是你玩游戏的一次通关过程)
    + $s_i$ 第i次的环境状态
    + $a_i$ 第i次针对$s_i$采取的动作
    + $\tau=${$s_1$,$a_1$,$s_2$,$a_2$,...}就建模出了一个轨迹
    + $p_\theta(\tau) = p(s_1) p_\theta(a_1|s_1) p(s_2|s_1, a_1) p_\theta(a_2|s_2) p(s_3|s_2, a_2) \cdots = p(s_1) \prod_{t=1}^{T} p_\theta(a_t|s_t) p(s_{t+1}|s_t, a_t)$
+ 在轨迹的中间可能会有Reward, 我们将这条轨迹上的所有Reward相加就是这条轨迹的总Reward, 称为$R(\tau)$
+ 很显然，我们想优化参数$\theta$下的所有轨迹的期望Reward, $\overline{R}_\theta = \sum_{\tau} R(\tau) p_\theta(\tau) = \mathbb{E}_{\tau \sim p_\theta(\tau)} \left[ R(\tau) \right]$
+ 如果我们对$R_{\theta}$求梯度
$$
\nabla \overline{R}_\theta = \sum_{\tau} R(\tau) \nabla p_\theta(\tau)
= \sum_{\tau} R(\tau) p_\theta(\tau) \frac{\nabla p_\theta(\tau)}{p_\theta(\tau)}
$$

$$
= \sum_{\tau} R(\tau) p_\theta(\tau) \nabla \log p_\theta(\tau)
$$

$$
= \mathbb{E}_{\tau \sim p_\theta(\tau)} [R(\tau) \nabla \log p_\theta(\tau)]
\approx \frac{1}{N} \sum_{n=1}^N R(\tau^n) \nabla \log p_\theta(\tau^n)
$$

$$
= \frac{1}{N} \sum_{n=1}^N \sum_{t=1}^{T_n} R(\tau^n) \nabla \log p_\theta(a_t^n | s_t^n)
$$
+ 从而通过$log$的求导性质，我们将一个求和的期望变成了概率分布下的和，从而可以用蒙特卡洛等方法来获取奖励，而不用每次求Reward都遍历所有轨迹
+ 更新时我们就使用$\theta \leftarrow \theta + \eta \nabla \overline{R}_\theta$更新即可
# Policy Gradient的一些可能问题及解决方法
### 1
+ 假如所有的Reward都是正的, 那根据上述式子，我们会根据梯度增大所有采样到的$p_\theta$的值。 但是，没有采样到的动作的概率就会下降，但也许没有采样到的动作更好.
+ 所以我们可以对于Reward设立一个Baseline，采样到的Reward减去baseline再代入到式子中：
$$
\nabla \overline{R}_\theta \approx \frac{1}{N} \sum_{n=1}^{N} \sum_{t=1}^{T_n} \left( R(\tau^n) - b \right) \nabla \log p_\theta(a_t^n | s_t^n)
\qquad
b \approx \mathbb{E}[R(\tau)]
$$
这里的$R(\tau^n) - b$被称为优势,Advantage,用A表示
### 2
+ 如果以轨迹为单位来分配Reward，一条轨迹上的所有动作的Reward都相同, 不利于细粒度的优化. 实际上，通常一条轨迹上的不同动作的贡献都是不同的. 我们可以采用每个动作的奖励是这个动作的所有Reward之和.
![](https://ys.al/static/img/88d79c9a13a0b1d25d8661c4c53cffab.image.webp)
+ 当然, 第一个动作可能不会对最后一个奖励产生特别大的影响, 所以也可以在求和项之前加上指数衰减的权重，但这个权重还是得看实际情况.
# Off-Policy学习
+ 概念: On-Policy: 和环境互动的Agent和与训练的Agent相同; Off-Policy: 和环境互动的Agent与训练的Agent不同
+ 如果我们使用on-policy的话, 每次更新Agent的参数, 我们就要重新收集一遍数据。我们希望使用另一个Agent去收集数据并复用.
$$
\mathbb{E}_{x \sim p}[f(x)] 
= \int f(x) p(x) dx
= \int f(x) \frac{p(x)}{q(x)} q(x) dx
= \mathbb{E}_{x \sim q} \left[ f(x) \frac{p(x)}{q(x)} \right]
$$
这样就把服从q分布的数据迁移到p分布上了
+ 这样做有一个问题: 这样增大了f(x)的方差, 假如p和q分布有很大的不同，采样可能出现错误的结果

![image.png](/static/img/0ccaf79bf6e229c99ad2ac389c57955f.image.webp)
如图，本来是负的期望因为采样原因，如果根据q分布全部采样到了右边的点，可能误把期望变成正值
# PPO/TRPO

### KL散度
衡量的是“用分布Q去近似分布P时，所造成的信息损失。  
$$
D_{KL}(P \| Q) = \sum_{x} P(x) \log \frac{P(x)}{Q(x)}
$$
### PPO
$$
J^{\theta'}_{PPO}(\theta) = J^{\theta'}(\theta) - \beta KL(\theta, \theta')
$$
PPO2: 裁剪了比例，防止更新过大
$$
   L^{CLIP}(\theta) = \mathbb{E}_t \left[ \min(r_t(\theta) \hat{A}_t, \text{clip}(r_t(\theta), 1-\epsilon, 1+\epsilon) \hat{A}_t) \right]
$$
### TRPO
$$
J^{\theta'}_{TRPO}(\theta) = \mathbb{E}_{(s_t, a_t) \sim \pi_{\theta'}} \left[ \frac{p_{\theta}(a_t|s_t)}{p_{\theta'}(a_t|s_t)} A^{\theta'}(s_t, a_t) \right]， 
KL(\theta, \theta') < \delta
$$
PPO将KL散度作为惩罚项，而TRPO只计算KL散度较小部分区域.
# Q-Learning
Q值估计了一个Actor在某个状态后的表现会有多好.

暂时掠过

# RLHF
RLHF会有两阶段的训练: 第一阶段训练出一个奖励模型，用于奖励人类所偏好的答案; 第二阶段根据训练出的模型来后训练模型.

Reward Model

$$
\text{loss}(\theta) = -\frac{1}{\left(\frac{K}{2}\right)} \mathbb{E}_{(x, y_w, y_l) \sim D} \left[ \log \left( \sigma \left(r_{\theta}(x, y_w) - r_{\theta}(x, y_l) \right) \right) \right]
$$

Post-train(最好和原数据一起训练，防止灾难性遗忘)
$$
\begin{aligned}
\text{objective}(\phi) = & \; \mathbb{E}_{(x, y) \sim D_{\pi_\phi^{\text{RL}}}} \left[ r_{\theta}(x, y) - \beta \log \left(\pi_\phi^{\text{RL}}(y \mid x) / \pi^{\text{SFT}}(y \mid x)\right) \right] \\
& + \gamma \mathbb{E}_{x \sim D_{\text{pretrain}}} \left[ \log\left( \pi_\phi^{\text{RL}}(x) \right) \right]
\end{aligned}
$$
# DPO
具体原理没看懂，简单来说就是不训练Reward Model了，直接在原模型上SFT.

$$
\mathcal{L}_{\text{DPO}}(\pi_\theta; \pi_{\text{ref}})
= -\mathbb{E}_{(x, y_w, y_l) \sim \mathcal{D}}
\left[
    \log \sigma \left(
        \beta \log \frac{\pi_\theta(y_w \mid x)}{\pi_{\text{ref}}(y_w \mid x)}
        - \beta \log \frac{\pi_\theta(y_l \mid x)}{\pi_{\text{ref}}(y_l \mid x)}
    \right)
\right]
$$

# GRPO
让大模型生成多条回,用这几条回答的平均值作为baseline, 然后和PPO差不多

$$
\mathcal{J}_{\text{GRPO}}(\theta) = \mathbb{E}\Big[q \sim P(Q), \{o_i\}_{i=1}^G \sim \pi_{\theta_{\text{old}}}(O|q)\Big] \\
\frac{1}{G} \sum_{i=1}^G \frac{1}{|o_i|} \sum_{t=1}^{|o_i|} 
\left\{
    \min \left[
        \frac{\pi_\theta(o_{i,t}|q,o_{i,<t})}{\pi_{\theta_{\text{old}}}(o_{i,t}|q,o_{i,<t})} \hat{A}_{i,t},
        \operatorname{clip} \left(
            \frac{\pi_\theta(o_{i,t}|q,o_{i,<t})}{\pi_{\theta_{\text{old}}}(o_{i,t}|q,o_{i,<t})},
            1-\epsilon,\, 1+\epsilon
        \right) \hat{A}_{i,t}
    \right]
    - \beta \mathbb{D}_{\text{KL}} \left[ \pi_\theta \| \pi_{\text{ref}} \right]
\right\}
$$

$$
\hat{A}_{i,t} = \tilde{r}_i = \frac{r_i - \operatorname{mean}(\mathbf{r})}{\operatorname{std}(\mathbf{r})}
$$

$$
\mathbb{D}_{\text{KL}} \left[ \pi_\theta \| \pi_{\text{ref}} \right] = 
\frac{\pi_{\text{ref}}(o_{i,t}|q,o_{i,<t})}{\pi_\theta(o_{i,t}|q,o_{i,<t})}
- \log \frac{\pi_{\text{ref}}(o_{i,t}|q,o_{i,<t})}{\pi_\theta(o_{i,t}|q,o_{i,<t})} - 1
$$

强化学习入门

回忆版


# 1 
1. 什么是操作系统
2. 什么是文件描述符
3. 为什么说linux的管道是一种进程间通信的机制?
4. 为什么要避免数据竞争？
5. 什么是设备驱动程序
# 2 
1. 简述mmap的作用(无须写出定义)
2. 有人说1号进程是/usr/bin/systemd, 有人认为是/usr/bin/init, 怎么判断1号进程到底是哪一个二进制文件?
3. 除了用户定义的全局变量，libc维护了哪些全局变量? 
4. System V ABI规定进程的初始栈中有一些auxiliary vector entries. 根据你对操作系统的理解，可以有哪些辅助数据，又有什么作用?
# 3
readelf -a filename如下
```
rela.text:
记不得offset R_X86_64_PC32 x-8
记不得offset R_X86_64_PLT32 foo-4
```
1. 这个文件是什么ELF文件? R_X86_64_PC32和R_X86_64_PLT32各自是什么意思?
2. 写出main三参数的函数。解释每个参数的含义.
3. 动态链接的a.out执行到main函数之间的过程?
4. LD_PRELOAD可以指定预先加载的动态链接库，你可以想到一个用它做什么有意思的应用?
# 4 并发编程
有字符串a,b，并行地做Longest Common Sequence
```C
void Tlcs(int i, int j){
    if(i==0 || j==0) return;
    // TODO
    dp[i][j] = max3(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]+(a[i]==b[j]))
    // TODO
}

int main(){
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            spawn(Tlcs,i,j);
        }
    }
    join();
    printf("%d\n",dp[n][m]);
    return 0;
}
```
添加代码，使得可以正确同步. 允许添加初始化代码
# 5
1. 什么是RAID技术? 有什么应用
2. 如果要对一个文件进行保存，并希望在系统崩溃（断电等）之后数据仍然正确。进行的系统调用的顺序应该是怎样的?
3. Linux的inode存放着用户的uid,如果硬盘被偷走，则可以读取所有文件。如何保护高度机密的文件?
4. readdir函数可以遍历一个目录,在面对有上百万个文件的目录时，会遇到性能瓶颈。你觉得该如何添加新的API?