本文介绍随机变量样本均值方差和整体均值方差的关系，同时还介绍样本和均值的方差和总体方差的关系

• 其他参考链接：在统计学里如何理解样本均值的方差等于总体方差➗n? - 蘇雲的回答 - 知乎

样本均值的方差与总体方差的关系

• 其他证明方式：
  • 上式中，如果总体方差未知，想要用样本方差来作为总体方差的无偏估计，则样本方差的定义是应该是 \(S^2 = \frac{1}{n-1}\sum_i^n(X_i-\bar{X})^2\)，（此时样本方差是总体方差的无偏估计）

样本方差为什么要除以n-1?

• 样本方差的定义：
  $$
  \sigma^2 \approx S^2 = \frac{1}{n-1}\sum_i^n(X_i-\bar{X})^2
  $$
• 为什么样本方差是乘以 \(\frac{1}{n-1}\) 而不是 \(\frac{1}{n}\) ？
  • 因为这样使用 \(\frac{1}{n}\) 会低估总体方差，此时样本方差不是总体方差的无偏估计
  • 样本方差低估了总体方差的原因是因为从总体里面抽出来的数据会更倾向于集中，极端情况下，一个样本对应的方差为0
• 换个视角想，是因为我们不知道总体的均值，所以计算方差时使用的均值也是从样本中求平均得到的，这使得我们基于该均值得到的方差不够离散（因为使用了样本均值，所以自由度需要减一），也就是低估了总体方差
  • 怎么理解自由度？
    • 采样一个样本以后无法计算方差，此时方差为0，因为此时均值就等于样本本身，此时自由度为0
    • 采样两个样本以后得到的方差只根第二个样本到第一个样本的距离有关（样本均值与这两个样本强相关），此时自由度为1
    • 当采样的样本数非常多（假设为n）时，实际上单个样本与均值的关系很小了，此时自由度为n-1
• 当已知总体均值 \(\mu\) 时（个人理解：这里的 \(\mu\) 可以是其他采样方式下获得的近似均值，只要不跟当前用于计算方差的样本相关即可），样本方差可以使用：
  $$
  \sigma^2 \approx S^2 = \frac{1}{n-1}\sum_i^n(X_i-\mu)^2
  $$
• 样本方差经过 \(\frac{1}{n-1}\) 修正以后可以用来估计总体方差（修正以后是总体方差的无偏估计）
  • 这个修正叫做贝塞尔修正

证明 from ：Bilibili-样本方差为什么除以n-1?

单样本均值和多样本均值的关系

问题定义

• 考虑以下采样方式
  • 集合X ：每次采样 B个样本 得到的样本集合
  • 集合Y ：每次采样 1个样本 得到的样本集合
• 问：多次采样时，集合X和B的均值和方差关系是什么？
  • 即：如果我们重复多次进行这样的采样（每次采B个或1个），那么：这两种采样方式得到的样本均值的期望（即平均值的平均值）和样本均值的方差（即平均值的波动程度）之间有什么关系？

假设与符号定义

• 假设我们从一个总体中采样，总体的均值为 \(\mu\)，方差为 \(\sigma^2\)
• 集合X ：
  • 每次采样 B个样本 ：\(X_1, X_2, \dots, X_B\)
  • 计算这B个样本的均值：\(\bar{X}_A = \frac{1}{B}\sum_{i=1}^B X_i\)
• 集合Y ：
  • 每次采样 1个样本 ：\(Y_1\)
  • 其“均值”就是它自己：\(\bar{X}_B = Y_1\)
• 我们重复多次这样的采样过程，得到一系列的 \(\bar{X}_A\) 和 \(\bar{X}_B\)

均值关系

• 集合X 的样本均值的期望：
  $$
  E[\bar{X}_A] = E\left[\frac{1}{B}\sum_{i=1}^B X_i\right] = \frac{1}{B} \sum_{i=1}^B E[X_i] = \frac{1}{B} \cdot B \mu = \mu
  $$
• 集合Y 的样本均值的期望：
  $$
  E[\bar{X}_B] = E[Y_1] = \mu
  $$
• 结论：两种采样方式得到的样本均值的期望是相同的 ，都等于总体均值 \(\mu\)

方差关系

• 集合X 的样本均值的方差：
  $$
  \text{Var}(\bar{X}_A) = \text{Var}\left(\frac{1}{B}\sum_{i=1}^B X_i\right) = \frac{1}{B^2} \sum_{i=1}^B \text{Var}(X_i) = \frac{1}{B^2} \cdot B \sigma^2 = \frac{\sigma^2}{B}
  $$
• 集合Y 的样本均值的方差：
  $$
  \text{Var}(\bar{X}_B) = \text{Var}(Y_1) = \sigma^2
  $$
• 结论：集合X 的样本均值的方差是 \(\frac{\sigma^2}{B}\)，集合Y 的样本均值的方差是 \(\sigma^2\)
  • 也就是说，集合X 的样本均值的方差更小，是集合Y 的 \(\frac{1}{B}\)
• 直观理解
  • 均值方面：无论你是采1个还是采B个，平均来看，它们的中心位置（期望）都是一样的，都是总体的均值
  • 方差方面：采B个样本求平均，相当于把单个样本的“噪声”给“平均掉”了，因此波动更小，方差更小；而采1个样本，没有“平均”的过程，波动就更大，方差也就更大

解析解（Analytical Solution）

• 解析解指的是通过标准的数学操作（如代数运算、积分、微分等）得到的精确表达式，该表达式可以是有限项的公式或无限级数的形式。解析解通常意味着我们能够以明确的数学形式写出问题的解答，而不需要进行数值逼近

闭式解（Closed-form Solution）

• 闭式解是一种特殊的解析解 ，它指的是一类可以用有限数量的标准数学操作和已知函数（如指数函数、对数函数、三角函数等基本初等函数及其组合）表达的解析解。换句话说，闭式解是可以直接计算出来的，而不是需要迭代过程或者近似方法来获得的结果

解析解和闭式解的区别

• 所有的闭式解都是解析解，但并非所有解析解都是闭式解。解析解可以包含无限级数或者其他非闭式的表达形式
• 当我们说一个问题是可解析求解（或有解析解）时，意味着存在一个理论上精确的数学表达式作为答案；而当我们提到闭式解时，则进一步强调了这个解可以由有限次的基本数学运算得出。

调和级数的和是发散的,并不收敛,但是这又是一个非常常用的级数,本文总结了调和级数的和的求法

一个事实

• 调和级数的和与 n 的自然对数的差值收敛到欧拉-马歇罗尼常数
  $$
  \begin{align}
  lim_{n \to \infty}(\sum_{i=1}^{n}\frac{1}{i} - ln(n)) = \gamma
  \end{align}
  $$
  • \(\gamma\) 为欧拉-马歇罗尼常数
    • (欧拉常数又称欧拉-马斯克若尼常数，近似值为γ≈0.57721 56649 01532 86060 65120 90082 40243 10421 59335)

证明

• 事实上,调和级数的和为
  $$
  \begin{align}
  \sum_{i=1}^{n}\frac{1}{i} = ln(n) + \gamma + \epsilon_{n}
  \end{align}
  $$
  • \(\gamma\) 为欧拉-马歇罗尼常数
  • \(\epsilon_{n}\) 约等于 \(\frac{1}{2n}\)，随着n的不断增大, \(\epsilon_{n}\) 趋于0

补充

• 两个不同的调和数之间的差值永远不是整数
• 除了n=1时以外,没有任何一个调和数是整数

本文介绍辛普森悖论

辛普森悖论

• 辛普森悖论指的是在分组比较中占优的一方，在合并数据后反而处于劣势的现象

药物效果示例

• 场景场景 ：比较两种药物（A 和 B）对轻症和重症患者的治愈率

• 分组数据 ：

  • 轻症患者组 ：
    • 药 A：治疗 10 人 ，治愈 9 人 -> 治愈率 90%
    • 药 B：治疗 100 人 ，治愈 80 人 -> 治愈率 80%
  • 重症患者组 ：
    • 药 A：治疗 100 人 ，治愈 30 人 -> 治愈率 30%
    • 药 B：治疗 10 人 ，治愈 2 人 -> 治愈率 20%

• 分组结论 ：

  • 轻症组：药 A 的治愈率（90%）> 药 B（80%）
  • 重症组：药 A 的治愈率（30%）> 药 B（20%）

• 合并数据 ：

  • 药 A：总治愈 39 人（9 + 30），总治疗 110 人 -> 治愈率 35.5%
  • 药 B：总治愈 82 人（80 + 2），总治疗 110 人 -> 治愈率 74.5%

• 悖论出现 ：

• 尽管药 A 在每个分组的治愈率都更高，但合并后药 B 的总治愈率却显著优于药 A。这是因为药 B 主要用于治愈率高的轻症患者（样本量 100 vs. 10），而药 A 更多用于治愈率低的重症患者（样本量 100 vs. 10），导致整体结果反转

核心原因 ：

• 数据分组中存在混杂变量（此处为病情严重程度），且各组样本量差异巨大，合并时权重不同引发悖论

什么药是真正优秀的？

• 药 A才是真正疗效更好的，因为在任何场景下（不论轻症还是重症下），都是药 A 效果更好，之所以合并到一起统计出现悖论，是因为医生开药时存在刻意倾向导致的，给轻症患者更多的开了药 B，这相当于强行提高了药 B 的治愈率
• 其他类似问题也出现在不同学院男女录取率上

本文包含对线性规划的直观理解，不严谨，后续有新的问题/理解持续更新

• 参考链接：
  • 运筹学中应该如何理解互补松弛性。这条性质又该如何运用?
  • 第4章 对偶理论和敏感度分析
  • 线性规划对偶问题的定义，有什么直觉上的解释吗？：原始问题到对偶问题最好的一种很简洁的解释
  • 互联网广告算法漫谈——浅谈广告中的出价技术。注意：该参考链接中没有把预算约束相关的互补松弛定理写出来，且2.3中存在一些较为明显的小bug，但整体求解思路和结论没问题

原始问题

• 问题描述：
  • 假设你是一个木匠有200单位的木头和90单位的时间
  • 木匠可以制作桌子或者椅子
    • 桌子成本为5单位木头+2单位时间，售价10元
    • 椅子成本为2单位木头+1单位时间，售价3元
• 目标：在已有资源情况下，最大化收入，应该生产多少桌子和椅子？
• 问题形式化描述:
  • 假设应该生产 \(x_1\) 把桌子和 \(x_1\) 把椅子
    $$
    \begin{align}
    \max \ \ 10x_1 &+ 3x_2 \\
    5x_1 + 2x_2 &<= 200 \\
    3x_1 + \ \ x_2 &<= 90 \\
    x_1,x_2 &>= 0 \\
    \end{align}
    $$
• 作图法可求得最优解为 \(x_1^* = 30, x_2^*=0\)，此时最大收益为300
  • 在二维坐标轴上先画出可行域，然后按照目标直线斜率找到最优点

对偶问题

• 对偶问题描述：
  • 上述原始问题可以换一个视角看
  • 假设现在你是一个原材料收购商（想要以最低价格收购木匠的原材料）
  • 目标：对单位木头和单位时间进行出价，以最低的价格买完木匠的资源（假设木匠愿意卖出的前提是收购上出价的最小值不小于木匠原始问题中收益的最大值）
    • 实际上最好是刚好等于木匠原始问题的最大收益
• 对偶问题形式化描述
  $$
  \begin{align}
  \min \ \ 200p_1 &+ 90p_2 \quad – 总付款 \\
  5p_1 + 3p_2 &>= 10 \quad – 一张桌子的资源售价不低于一张桌子的收益 \\
  2p_1 + \ \ p_2 &>= 3 \quad – 一张椅子的资源售价不低于一张椅子的收益 \\
  p_1,p_2 &>= 0 \quad – 售价不为负数 \\
  \end{align}
  $$
• 其中 \(p_1, p_2\) 分别称为单位木头和单位时间的影子价格
• 作图法可求得最优解为 \(p_1^* = 0, p_2^* = 3.3\)，此时最小支付金额为300

互补松弛定理的理解

从原始问题的约束视角出发

等价于从对偶问题的解出发

• 对偶问题中，最优解是 \(p_1^* = 0, p_2^* = 3.3\)
  • \(p_1^* = 0\) 意味着我们的木材过量了，其实不需要这么多木材，原始问题中，最优解对应的木材约束是松的（ \(5x_1^* + 2x_2^*=150 < 200\) ）
  • \(p_2^* = 3.3\) 说明时间资源非常紧俏，原始问题中，最优解对应的时间约束是紧的（ \(3x_1^* + \ \ x_2^* = 90\) ）
• 对应互补松弛的含义：
  • 如果在最优条件下一个约束不等式是松的（木材），那么这个约束对应的影子价格为0
  • 反过来说，如果某个约束对应的影子价格严格大于0，那么这个约束不等式一定是紧的
  • 总的来说，原始问题的约束和对偶问题变量(影子价格)总有一个要为0

从对偶问题的约束视角出发

等价于从原始问题的解出发

• 原始问题中，最优解是 \(x_1^* = 30, x_2^*=0\)
  • \(x_1^* = 30\) 意味着桌子非常合算，应该多生产桌子，对偶问题中，桌子约束是紧的（ \(5p_1^* + 3p_2^* = 10\) ）
  • \(x_2^*=0\) 以为这椅子不合算，不应该生产椅子，对偶问题中，椅子的约束是松的（ \(2p_1^* + \ \ p_2^* = 3.3 > 3\) ）
• 补充互补松弛的含义：
  • 如果在对偶最优条件下一个约束不等式是松的（椅子），那么这个约束对应的原始问题变量最优解（ \(x_2^*\) ）为0
  • 反过来说，如果某个原始问题变量（桌子）对应的解（ \(x_1^*\) ）严格大于0，那么对偶问题中这个约束不等式一定是紧的
  • 总的来说，对偶问题的约束和对应原始问题变量总有一个要为0

互补松弛定理的公式化

$$
(5p_1^* + 3p_2^* - 10)x_1^* = 0 \\
(2p_1^* + p_2^* - 3)x_2^* = 0 \\
(5x_1^* + 2x_2^* - 200)p_1^* = 0 \\
(3x_1^* + x_2^* - 90)p_2^* = 0 \\
$$

附录：USCB推导

• 《A Unified Solution to Constrained Bidding in Online Display Advertising》——论文阅读
  • 这篇文章的约束很多，每个商家都有自己的约束
  • 推导时用到的对偶变换和互补松弛定理均可由论文推导得出【有时间再详细推导】

附录：BCB推导（单约束）

• 《Budget Constrained Bidding by Model-free Reinforcement Learning in Display Advertising》——论文原文
  • 这篇文章中的问题定义比较简单，整体只有一个预算约束
  • 上述结果详细的推导可以参考：
    • 智能出价——BCB求解
    • 互联网广告算法漫谈——浅谈广告中的出价技术。注意：该参考链接中没有把预算约束相关的互补松弛定理写出来，且2.3中存在一些较为明显的小bug，但整体求解思路和结论没问题
  • 推导结果 \(bid = \frac{v_i}{\lambda}\) 与常用的方法(RL-MPCA)结果不一致，但可以证明本质是等价的

附录：CPC约束推导（单约束）

• 问题描述：单位置、二价拍卖，且CPM计费场景，CPC约束下最大化商家点击量
• 推导过程可参考论文Bid Optimization by Multivariable Control in Display Advertising
• 基本推导思路：先通过拉格朗日乘子法得到最优解的形式（这里先忽略边际条件 \(0\le x_i \le 1\) ），再将原始问题转换成对偶问题，进一步分情况讨论得到最终解
• 问题定义
  $$
  \begin{align}
  &\max \sum_i x_i \cdot ctr_i \\
  \text{s.t.} &\quad \frac{\sum_i x_i \cdot wp_i}{\sum_i x_i \cdot ctr_i} \le cpc \\
  &\quad 0 \le x_i \le 1, \forall i
  \end{align}
  $$
• 第一步：推导最优出价形式：
  • 写出拉格朗日函数并求导：
    $$\mathcal{L}(x, \lambda, \mu) = - \sum_i x_i \cdot ctr_i + \lambda \left(\sum_i x_i \cdot wp_i - \sum_i x_i \cdot ctr_i \cdot cpc\right) + \sum_i \mu_i (x_i - 1)$$
  • 对任意的 \(x_i\) 求导有：
    $$ \frac{\partial \mathcal{L}(x, \lambda, \mu)}{\partial x_i} = - \sum_i ctr_i + \lambda \sum_i wp_i - \lambda \sum_i ctr_i \cdot cpc + \sum_i \mu_i $$
  • 令上述导数为0有（\(\mu_i\) 来自边界条件 \(0\le x_i \le 1\)，为了得到最优解形式，接下来先忽略边界条件，最后会证明在满足边界条件下，该形式也是最优的）：
    $$
    \begin{align}
    wp_i &= \frac{ctr_i + \lambda \cdot cpc \cdot ctr_i}{\lambda} \\
    &= \frac{1 + \lambda \cdot cpc}{\lambda} \cdot ctr_i
    \end{align}
    $$
    • 所以我们令出价等于下面的形式：
      $$bid_i = \frac{1 + \lambda \cdot cpc}{\lambda} \cdot ctr_i$$
• 第二步：验证最优出价形式：
  • 原始问题对应的对偶问题为：
    $$
    \begin{align}
    &\mathop{\min}_{\lambda, r_i} \sum_i r_i \\
    \text{s.t.} &\quad \lambda(wp_i - cpc\cdot ctr_i) + r_i \ge ctr_i \quad \text(1)\\
    &\quad \lambda \ge 0 \\
    &\quad r_i \ge 0, \forall i
    \end{align}
    $$
  • 互补松弛条件:
    $$
    \begin{align}
    x_i(\lambda(wp_i - cpc\cdot ctr_i) + r_i - ctr_i) = 0 \quad &\text{(2)} \\
    r_i(x_i - 1) = 0, \forall i \quad &\text{(3)}
    \end{align}
    $$
  • 将最优出价公式 \(bid_i = \frac{ctr_i + \lambda \cdot cpc \cdot ctr_i}{\lambda}\) 带入公式(2)可得：
    $$ x_i(\lambda(wp_i - bid_i) + r_i) = 0$$
    • 当 \(x_i \gt 0\) 时，有 \(wp_i - bid_i = -\frac{r_i}{\lambda} \lt 0\)，进一步推得 \(bid_i \ge wp_i\)
    • 当 \(x_i = 0\) 时，由公式(3)有 \(r_i = 0\)；将最优出价公式 \(wp_i = \frac{ctr_i + \lambda \cdot cpc \cdot ctr_i}{\lambda}\) 带入公式(1)可得 \(\lambda(wp_i - bid_i) + r_i \ge 0\)，进一步推得 \(wp_i - bid_i \ge 0\)，即\(bid_i \le wp_i\)
  • 证毕
• 如何理解最优出价形式？
  $$
  \begin{align}
  bid_i = \frac{1 + \lambda \cdot cpc}{\lambda} \cdot ctr_i = \color{red}{(\frac{1}{\lambda \cdot cpc} + 1)} \cdot cpc \cdot ctr_i
  \end{align}
  $$
  • 二价计费场景中 ，计费比未知，所以引入了一个大于 1 的出价系数:
    $$ k = \color{red}{\frac{1}{\lambda \cdot cpc} + 1} $$
    • 用来提升出价以做到目标CPC达成（可以证明，在整个周期内流量足够多的情况下，如果实际CPC小于目标CPC，则此时一定不是点击最大化的出价策略）
    • 实际使用中，由于 \(1\) 是全局固定值，商家的 \(cpc\) 是商家粒度的固定值，\(\lambda\) 是商家粒度的变量，可以合并成一个变量即可（\(\lambda\) 和 \(k\) 是一一对应的），最终可以忽略 \(k\) 值的具体形式，只需要直接调节 \(k\) 即可，此时最优公式为：
      $$ bid_i = \color{red}{k} \cdot cpc \cdot ctr_i $$
  • 如果竞争环境非常激烈，计费比趋近于1（同时考虑预估值准确），此时每次出价都按照 \(\color{red}{bid_i = cpc \cdot ctr_i} \)，可保证投放周期内实际CPC的期望刚好等于目标CPC，\(\color{red}{k=1}\) 就是最优的出价策略
  • 调控系数的其他功能 ：从推导来看，系数 \(k\) 可以用于补足二价计费的Gap；在实际应用中，这个 k 值还可以解决 CTR 均值预估值不准确的问题，比如CTR预估过高 ，\(k\) 会小于1 ，从而保证不超成本
    • 可以注意到：在这个假设下有矛盾点，\(k < 1\) 时对应的 \(\lambda < 0\)，并不满足对拉格朗日乘子的要求，但不用担心，这里实际上 \(k = k_1 \cdot k_2\)，其中，由 \(\lambda\) 导出的 \(k_1\) 依然是大于1的，用来调平CTR预估值 \(k_2\) 是小于1的，实际上，\(\lambda \geq 0\) 始终成立

附录：oCPC场景约束推导（单约束）

• 问题描述1：单位置、二价拍卖，且CPC计费场景，CPS约束下最大化商家订单量
• 实际上，本问题中与上文单位置拍卖的CPM计费场景，CPC约束下最大化商家点击量非常相似，仅需把对应的参数替换一下即可（\(ctr_i \rightarrow cvr_i\)，\(cpc \rightarrow cps\)），于是有最优出价形式是：
  $$
  \begin{align}
  wp_i = \frac{1 + \lambda \cdot cps}{\lambda} \cdot cvr_i = \color{red}{(\frac{1}{\lambda \cdot cps} + 1)} \cdot cps \cdot cvr_i
  \end{align}
  $$
  • 出价系数：
    $$ k = \color{red}{\frac{1}{\lambda \cdot cps} + 1} $$
  • 注：实际使用中，同上描述，最终可以忽略 \(k\) 值的具体形式，只需要直接调节 \(k\) 即可，此时最优公式为：
    $$ bid_i = \color{red}{k} \cdot cps \cdot cvr_i $$
• 问题描述2：单位置、二价拍卖，且CPC计费场景，ROI约束下最大化商家Revenue
• 此时可以进一步表达为如下形式（\(cvr_i \rightarrow cvr_i\cdot rev_i\)，\(cps \rightarrow rate = \frac{1}{ROI}\)， ）：
  $$
  \begin{align}
  wp_i &= \frac{1 + \lambda \cdot 1/ROI}{\lambda} \cdot cvr_i \cdot rev_i \\
  &= \frac{ROI + \lambda}{\lambda \cdot ROI} \cdot rev_i \cdot cvr_i \\
  &= \frac{ROI + \lambda}{\lambda} \cdot \frac{rev_i \cdot cvr_i}{ROI} \\
  &= \color{red}{(\frac{ROI}{\lambda} + 1)} \cdot \frac{rev_i \cdot cvr_i}{ROI} \\
  \end{align}
  $$
  • 出价系数：
    $$ k = \color{red}{\frac{ROI}{\lambda} + 1}$$
  • 注：实际使用中，同上描述，最终可以忽略 \(k\) 值的具体形式，只需要直接调节 \(k\) 即可，此时最优公式为：
    $$ bid_i = \color{red}{k} \cdot \frac{rev_i \cdot cvr_i}{ROI} $$

附录：紧约束和松约束

• 紧约束（Tight Constraint）和松约束（Slack Constraint）是描述约束条件对可行解集影响的两个概念
• 紧约束指的是那些在其边界上限制了最优解的约束条件。换句话说，如果改变某个约束条件会直接影响到最优解的位置或值，那么这个约束条件就是紧的。例如，在线性规划问题中，如果一个不等式约束以“=”的形式满足于最优解处，那么这个约束就是紧约束。紧约束对于确定最优解至关重要，因为它们直接定义了最优解所在的位置
• 松约束则指的是那些在最优解处并没有起到实际限制作用的约束条件。也就是说，即使这些约束不存在，也不会改变问题的最优解。这类约束条件提供了额外的空间，但在这个空间内的点并不会比边界上的点更优。因此，松约束的存在不会影响最终的优化结果，但在某些情况下，它们可能为寻找最优解提供便利或增加灵活性。

核心定义

• 一句话定义：平稳分布在马尔可夫链长期演化后系统达到的稳态概率分布
• 对于一个离散时间马尔可夫链（Markov Chain） ，若存在一个概率分布 \(\pi\) 满足以下方程：
  $$
  \pi = \pi P
  $$
  • \(P\) 是转移概率矩阵（\(P_{ij}\) 表示从状态 \(i\) 转移到状态 \(j\) 的概率）
  • \(\pi\) 是行向量，表示每个状态的概率
• 则称 \(\pi\) 为该马尔可夫链的平稳分布（Stationary Distribution）。直观上，这意味着系统达到 \(\pi\) 后，状态分布不再随时间改变

关键性质

• 存在性与唯一性 ：

  • 若马尔可夫链是不可约马尔可夫链（Irreducible Markov Chain）（不可约马尔可夫链的所有状态互通），且满足正常返（Positive Recurrent）特性（即每个状态会被无限次访问），则平稳分布存在且唯一
  • 对于有限状态的不可约链，平稳分布一定存在

• 长期行为 ：

  • 无论初始分布如何，若链满足一定条件（如非周期性），长期后的状态分布会收敛到平稳分布：
    $$
    \lim_{n \to \infty} \mu P^n = \pi
    $$
    其中 \(\mu\) 是初始分布

• 细致平衡条件（Detailed Balance）：

  • 若分布 \(\pi\) 满足 \(\pi_i P_{ij} = \pi_j P_{ji}\)（对所有 \(i,j\)），则 \(\pi\) 是平稳分布。满足此条件的链称为可逆马尔可夫链

计算方法

• 解线性方程组 ：
  • 通过 \(\pi = \pi P\) 和 \(\sum_i \pi_i = 1\) 联立求解
  • 例如，对两状态链：
    $$
    \begin{cases}
    \pi_1 = \pi_1 P_{11} + \pi_2 P_{21} \\
    \pi_2 = \pi_1 P_{12} + \pi_2 P_{22} \\
    \pi_1 + \pi_2 = 1
    \end{cases}
    $$
• 其他求解方法：特征向量法

例子

• 假设天气模型（晴/雨）的转移矩阵，描述了晴雨天转换的概率：
  $$
  P = \begin{bmatrix}
  0.9 & 0.1 \\
  0.5 & 0.5
  \end{bmatrix}
  $$
• 解 \(\pi P = \pi\) 得 \(\pi = [\frac{5}{6}, \frac{1}{6}]\)，即长期下有5/6概率为晴天，1/6为雨天

范数的定义

• 在数学中，范数 (Norm) 是一个函数，它将向量空间中的每个非零向量映射为一个正实数 ，直观上可以理解为向量的“长度”或“大小”
  • 注：常规聊的范数都是针对向量空间的，谱范数(Spectral Norm) 是针对矩阵空间的
• 对于零向量，范数映射为零
• 范数需要满足以下三个性质：
  • 1）非负性 (Non-negativity) ：对于所有向量 \( x \)，有\(|x| \ge 0\)，且当且仅当 \(x = 0\) 时，\(|x| = 0\)
  • 2）齐次性 (Homogeneity) ：对于所有标量 \( \alpha \) 和向量 \( x \)，有 \(|\alpha x| = |\alpha| |x|\)
  • 3）三角不等式 (Triangle Inequality) ：对于所有向量 \( x \) 和 \(y\)，有 \(|x + y| \le |x| + |y|\)

常见的范数——\(L_p\) 范数

• \(L_p\) 范数，也称为 Minkowski 范数，定义为：
  $$|x|_p = \left( \sum_{i=1}^n |x_i|^p \right)^{\frac{1}{p} }$$
  • \(x = [x_1, x_2, \dots, x_n]^T\) 是一个 \(n\) 维向量
  • \(p \ge 1\) 是一个实数

\(L_1\) 范数 (Manhattan Norm / Taxicab Norm)

• 当 \(p=1\) 时，称为 \(L_1\) 范数，表示向量中所有元素的绝对值之和
• \(L_1\) 范数衡量的是向量元素到原点的曼哈顿距离
  $$|x|_1 = \sum_{i=1}^n |x_i|$$
• 在机器学习中，常用于稀疏表示和特征选择（如 Lasso 回归），因为它倾向于产生稀疏解

\(L_2\) 范数 (Euclidean Norm)

• 当 \(p=2\) 时，称为 \(L_2\) 范数，表示向量的欧几里得长度，即从原点到向量的欧几里得距离
  $$|x|_2 = \sqrt{\sum_{i=1}^n |x_i|^2}$$
• \(L_2\) 范数是最常见的范数，广泛应用于各种领域，如机器学习中的岭回归 (Ridge Regression)、深度学习中的权重衰减 (Weight Decay) 以及距离计算

\(L_\infty\) 范数 (Maximum Norm / Chebyshev Norm)

• 当 \(p \to \infty\) 时，称为 \(L_\infty\) 范数，表示向量中所有元素的绝对值的最大值
  $$|x|_\infty = \max_{i} |x_i|$$
• 在一些优化问题中，当需要限制向量中最大分量的大小时会使用到

矩阵范数

• 矩阵范数是定义在矩阵空间上的范数，除了满足向量范数的三个性质外，对于矩阵乘法还需满足：
  $$
  |AB| \leq |A| |B|
  $$

诱导范数（算子范数）

• 对于矩阵 \( A \in \mathbb{C}^{m \times n} \)，由向量范数 \( |\cdot|_p \) 诱导的矩阵范数定义为：
  $$
  |A|_p = \sup_{x \neq 0} \frac{|Ax|_p}{|x|_p} = \sup_{|x|_p=1} |Ax|_p
  $$
• 特殊情况下，有以下范数：
  • 1）列和范数（诱导自 \(L_1\) 范数） ：
    $$
    |A|_1 = \max_{1 \leq j \leq n} \sum_{i=1}^m |a_{ij}|
    $$
    • 按列求和，再取最大者
  • 2）谱范数（诱导自 \(L_2\) 范数） ：
    $$
    |A|_2 = \sqrt{\lambda_{\max}(A^* A)}
    $$
    • 其中 \( \lambda_{\max} \) 表示最大特征值，\( A^* \) 是 \( A \) 的共轭转置
  • 3）行和范数（诱导自 \(L_\infty\) 范数） ：
    $$
    |A|_\infty = \max_{1 \leq i \leq m} \sum_{j=1}^n |a_{ij}|
    $$
    • 按行求和，再取最大者

常用的矩阵范数——谱范数

• 谱范数(Spectral Norm) 是矩阵范数的一种，它通常特指矩阵的 \(L_2\) 范数，即诱导 \(L_2\) 范数
• 谱范数是矩阵分析中最重要的范数之一，具有许多优良性质

谱范数定义

• 对于矩阵 \( A \in \mathbb{C}^{m \times n} \)，其谱范数定义为：
  $$
  |A|_2 = \sup_{x \neq 0} \frac{|Ax|_2}{|x|_2} = \sigma_{\max}(A)
  $$
  • 其中 \( \sigma_{\max}(A) \) 是 \( A \) 的最大奇异值
• 谱范数的更容易理解的另一个形式为：
  $$|A|_2 = \max_{x \ne 0} \frac{|Ax|_2}{|x|_2}$$
  • 这个定义表明，谱范数是矩阵 \(A\) 对向量 \(x\) 进行线性变换后 ，最大可能的“放大倍数”
  • 换句话说，它衡量了矩阵 \(A\) 在将单位向量 \(x\) 映射到 \(Ax\) 时，所能达到的最大长度

谱范数计算方法

• 1） 计算 \( A^* A \)（实矩阵时计算 \( A^T A \) 即可）
  • 注：\( A^* \) 是共轭转置 ，对于实矩阵为普通转置 \( A^T\)
• 2） 求 \( A^* A \) 的最大特征值 \( \lambda_{\max} \)
• 3） 谱范数为 \( \sqrt{\lambda_{\max} } \)

谱范数性质

• 1） 次乘性 ：\( |AB|_2 \leq |A|_2 |B|_2 \)
• 2） 酉不变性 ：对于任意酉矩阵 \( U \) 和 \( V \)，有 \( |UAV|_2 = |A|_2 \)
  • 注：酉矩阵（Unitary Matrix）的共轭转置（即 Hermitian 转置）等于其逆矩阵：
    $$ U^*U = UU^* = I$$
• 3） 与Frobenius范数的关系 ：\( |A|_2 \leq |A|_F \leq \sqrt{\operatorname{rank}(A)} |A|_2 \)
• 4） 与特征值的关系 ：对于正规矩阵，谱范数等于谱半径 \( \rho(A) = \max |\lambda_i| \)

谱范数的应用

• 矩阵近似 ：在低秩近似中，谱范数度量了近似误差

附录：谱范数与奇异值

• 谱范数有一个非常重要的性质，它等于矩阵 \(A\) 的最大奇异值
• 矩阵 \(A\) 的奇异值是其正定半定矩阵 \(A^T A\)（或 \(A A^T\)）的特征值的平方根
• 令 \(\sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_r > 0\) 为矩阵 \(A\) 的非零奇异值，其中 \(r = \text{rank}(A)\)。那么，谱范数可以表示为：
  $$|A|_2 = \sigma_{\max}(A) = \sqrt{\lambda_{\max}(A^T A)}$$
  • \(\sigma_{\max}(A)\) 表示矩阵 \(A\) 的最大奇异值
  • \(\lambda_{\max}(A^T A)\) 表示矩阵 \(A^T A\) 的最大特征值
• 推导简述 ：
  • 考虑 \(A^T A\) 是一个对称半正定矩阵，它的特征值都是非负的
  • 对于任意非零向量 \(x\)，我们有：
    $$\frac{|Ax|_2^2}{|x|_2^2} = \frac{(Ax)^T (Ax)}{x^T x} = \frac{x^T A^T A x}{x^T x}$$
  • 根据瑞利商 (Rayleigh Quotient) 的性质，\(\max_{x \ne 0} \frac{x^T M x}{x^T x} = \lambda_{\max}(M)\)，其中 \(M\) 是对称矩阵
  • 因此：
    $$\max_{x \ne 0} \frac{|Ax|_2^2}{|x|_2^2} = \lambda_{\max}(A^T A)$$
  • 取平方根后即可得到 \(|A|_2 = \sqrt{\lambda_{\max}(A^T A)} = \sigma_{\max}(A)\)
• 谱范数用于正则化 ：在机器学习中，谱范数可以用于限制模型的复杂度，例如在深度学习中，限制神经网络层的权重矩阵的谱范数可以帮助防止过拟合

附录：共轭转置

• 共轭转置（Conjugate Transpose），也称为Hermitian转置 ，是线性代数中对矩阵的一种操作，记作 \( A^* \)、\( A^H \) 或 \( A^\dagger \)
• 共轭转置 对矩阵 \( A \) 进行以下两步运算：
  • 1） 共轭 ：将矩阵 \( A \) 的每个元素取复共轭（即实部不变，虚部取反）
  • 2） 转置 ：将矩阵的行列互换（即第 \( i \) 行第 \( j \) 列元素变为第 \( j \) 行第 \( i \) 列）

与普通转置对比

• 普通转置（\( A^T \)） ：仅行列互换，不取共轭
• 实矩阵的共轭转置 ：退化为普通转置（因虚部为零）

附录：Schatten-\( p \) 范数是什么？

• Schatten-\( p \) 范数（Schatten-\( p \) norm）是矩阵空间中一类重要的范数，常用于描述矩阵的“大小”或“强度”
• Schatten-\( p \) 范数 基于矩阵的奇异值（singular values）定义，适用于更广泛的矩阵分析场景（如紧算子、核范数等）

Schatten-\( p \) 范数的定义

• 设矩阵 \( A \in \mathbb{C}^{m \times n} \) 的奇异值为 \( \sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r > 0 \)（其中 \( r = \min(m, n) \)），则其 Schatten-\( p \) 范数定义为：
  $$
  |A|_{S_p} = \left( \sum_{i=1}^r \sigma_i^p \right)^{1/p}, \quad p \in [1, \infty).
  $$

Schatten-\( p \) 范数的特例

• 1） \( p = 1 \)（核范数，Nuclear norm）
  $$ |A|_{S_1} = \sum_{i=1}^r \sigma_i $$
  • 用于矩阵低秩恢复、压缩感知等
• 2） \( p = 2 \)（Frobenius 范数，也称 F 范数）
  $$ |A|_{S_2} = \left( \sum_{i=1}^r \sigma_i^2 \right)^{1/2} = \sqrt{\text{tr}(A^* A)} $$
  • 即矩阵元素的平方和开根号
• 3） \( p = \infty \)（谱范数，Spectral norm）
  $$ |A|_{S_\infty} = \sigma_1 $$
  • 等于矩阵的最大奇异值，也是算子范数的一种

附录：Frobenius 范数的更多说明

• Frobenius范数（F 范数）是矩阵的一种常用范数，用于衡量矩阵的“大小”
• 它将矩阵视为一个向量，计算其所有元素的平方和的平方根
• 对于一个 \( m \times n \) 的矩阵 \( A = (a_{ij}) \)，其Frobenius范数定义为：
  $$
  |A|_F = \sqrt{\sum_{i=1}^{m} \sum_{j=1}^{n} |a_{ij}|^2}
  $$
  • 等价于矩阵所有元素的平方和再开平方
  • 在 PyTorch 中的实现为 A.norm()

本文介绍各种运筹优化开源求解器-GLPK的使用

• GLPK是一款完全开源免费的运筹优化求解器，可以任意商用

Ubuntu安装GLPK

• 据说Ubuntu安装较为方便，所以建议首选Ubuntu

• 在网站下载文件：https://ftp.gnu.org/gnu/glpk/

  • 可以下载任意版本，建议选最新

• 安装命令

  1 2 3 4

  tar -xzvf glpk-xxx.tar.gz ./configure make sudo make install

• 安装后直接执行可能出现错误

  1	error while loading shared libraries: libglpk.so.36:...

• 解决方案（原始解决方案地址）：

  1	https://github.com/rstudio/renv/issues/1881

Ubuntu下GLPK的使用

• 下列式子参考了：线性规划工具　GLPK 的安装及基本使用

• 创建问题描述文件glpkDemo.mod

  1 2 3 4 5 6 7 8 9 10 11 12 13 14

  /* Variables */ var x1 >= 0; var x2 >= 0; var x3 >= 0; /* Object function */ maximize z: 3*x1 + x2 +2*x3; /* Constrains */ s.t. con1: x1 + x2 + 3*x3 <= 30; s.t. con2: 2*x1 +2*x2 + 5*x3 <= 24; s.t. con3: 4*x1 + x2 + 2*x3 <= 36; end;

• 执行命令解决问题

  1	glpsol -m glpkDemo.mod -o ./output/glpkDemo.sol

• 输出文件

  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 28 29 30 31 32 33 34 35 36 37 38 39

  Problem: glpkDemo Rows: 4 Columns: 3 Non-zeros: 12 Status: OPTIMAL Objective: z = 28 (MAXimum) No. Row name St Activity Lower bound Upper bound Marginal ------ ------------ -- ------------- ------------- ------------- ------------- 1 z B 28 2 a B 12 30 3 b NU 24 24 0.166667 4 c NU 36 36 0.666667 No. Column name St Activity Lower bound Upper bound Marginal ------ ------------ -- ------------- ------------- ------------- ------------- 1 x1 B 8 0 2 x2 B 4 0 3 x3 NL 0 0 -0.166667 Karush-Kuhn-Tucker optimality conditions: KKT.PE: max.abs.err = 0.00e+00 on row 0 max.rel.err = 0.00e+00 on row 0 High quality KKT.PB: max.abs.err = 0.00e+00 on row 0 max.rel.err = 0.00e+00 on row 0 High quality KKT.DE: max.abs.err = 2.22e-16 on column 1 max.rel.err = 3.17e-17 on column 1 High quality KKT.DB: max.abs.err = 0.00e+00 on row 0 max.rel.err = 0.00e+00 on row 0 High quality End of output

• Activity这一列就是想要的解

• 其他输出项如何理解？

自动化生成问题

• 使用shell或者Python自动生成.mod文件，然后自然解析.sol文件，实现自动化测试参数

Parquet 整体说明

• Parquet（Apache Parquet）是一种列式存储的二进制文件格式，专为大数据处理场景设计，具有高效压缩和编码特性
• Parquet 尤其适合分析型工作负载，能显著提升查询速度并降低存储成本

Parquet 文件结构

• Parquet文件由多个行组（Row Groups）组成，每个行组包含：
• 列块（Column Chunks） ：存储实际列数据
• 元数据 ：记录统计信息（如min/max），用于加速查询

Parquet 文件读取示例

• Spark ：df.write.parquet("path") / spark.read.parquet("path")
• Pandas ：pd.read_parquet("file.parquet", engine="pyarrow")
• Hive ：CREATE TABLE ... STORED AS PARQUET

附录：文件读取和分析示例

• 使用 Python 代码读取并解析文件格式

  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 28 29 30 31 32 33 34

  import pandas as pd def read_and_inspect_parquet(file_path): try: # 读取Parquet文件 df = pd.read_parquet(file_path) print("成功读取Parquet文件！") print("\n===== 数据基本信息 =====") df.info() # 显示数据框的基本信息，包括列名、数据类型、非空值数量等 for col in df.columns: print("col:", col) print(df[col][0]) print("\n===== 前5行数据 =====") print(df.head()) # 显示前5行数据，查看数据格式 print("\n===== 数据统计信息 =====") print(df.describe()) # 显示数值型列的统计信息 return df except FileNotFoundError: print(f"错误: 找不到文件 '{file_path}'") except Exception as e: print(f"读取Parquet文件时发生错误: {str(e)}") return None if __name__ == "__main__": parquet_file_path = "./gsm8k/test.parquet" # 读取并查看Parquet文件 dataframe = read_and_inspect_parquet(parquet_file_path)

附录：列式存储 vs 行式存储

• 行式存储（如CSV、JSON）：按行存储数据，适合整行读取的场景（如单条记录查询）
• 列式存储（如Parquet）：按列存储数据，适合只读取部分列或聚合分析的场景（如计算某列的平均值）

PID相关笔记

PID相关参考

• 一个简短的PID描述：PID控制原理，看了开头，你就会看到结尾！
  • 包含修改参数带来的系统输出变化可视化示例
• 非常详细的讲解：从不懂到会用！PID从理论到实践~

位置式PID

• 位置式PID在 \(k\) 时刻的直接输出为控制量 \( u(k) \)，其离散形式为：
  $$
  u(k) = K_p \color{blue}{e(k)} + K_i \color{blue}{\sum_{j=0}^{k} e(j)} + K_d \color{blue}{\left[ e(k) - e(k-1) \right]}
  $$
• 其中：
  • \( K_p, K_i, K_d \) 分别为比例、积分、微分系数；
  • \( e(k) \) 为当前时刻误差；
  • \( \sum_{j=0}^{k} e(j) \) 为历史误差累加（积分项）
• 进阶：
  • \( K_i = K_p \frac{T}{T_i} \)：积分系数（\( T_i \)为积分时间常数，\( T \)为采样时间）
  • \( K_d = K_p \frac{T_d}{T} \)：微分系数（\( T_d \)为微分时间常数）

增量式PID

• 增量式PID的输出是控制量的增量
  $$ \Delta u(k) = u(k) - u(k-1) $$
• 类似位置式PID ，增量式PID在 \(k\) 时刻的 \(u(k)\) 可定义为如下：
  $$
  \begin{align}
  u(k) &= u(k-1) + \color{red}{\Delta u(k)} \\
  u(k) &= u(k-1) + (K_p + K_i + K_d) \color{red}{e(k)} - (K_p + 2K_d) \color{red}{e(k-1)} + K_d \color{red}{e(k-2)} \\
  u(k) &= u(k-1) + A \color{red}{e(k)} + B \color{red}{e(k-1)} + C \color{red}{e(k-2)}
  \end{align}
  $$
• 注：一般提到增量式PID ，我们一般认为输出是 控制量的增量 \(\Delta u(k)\)

位置式PID到增量式PID的推导

• 位置式PID和增量式PID完全等价，只是形式不同，通过对位置式PID做一阶差分 ，即可得到增量式PID
• 位置式在 \( k-1 \) 时刻的输出 \( u(k-1) \) 为：
  $$
  u(k-1) = K_p e(k-1) + K_i \sum_{j=0}^{k-1} e(j) + K_d \left[ e(k-1) - e(k-2) \right]
  $$
• 将 \( u(k) \) 和 \( u(k-1) \) 相减等到增量 \( \Delta u(k) = u(k) - u(k-1) \)：
  $$
  \Delta u(k) = K_p \left[ e(k) - e(k-1) \right] + K_i e(k) + K_d \left[ e(k) - 2e(k-1) + e(k-2) \right]
  $$
• 整理后得到增量式PID公式：
  $$
  \Delta u(k) = (K_p + K_i + K_d) e(k) - (K_p + 2K_d) e(k-1) + K_d e(k-2)
  $$

增量式PID到位置式PID的推导

• 已知增量式PID的参数为A、B、C，其增量输出公式为：
  $$\Delta u(k) = A \color{red}{e(k)} + B \color{red}{e(k-1)} + C \color{red}{e(k-2)}$$
• 通过对比位置式PID的差分形式，可以推导出位置式PID参数（Kp、Ki、Kd）与增量式参数的关系如下：
• 位置式PID的输出为：
  $$u(k) = K_p \color{blue}{e(k)} + K_i \color{blue}{\sum_{j=0}^{k} e(j)} + K_d \color{blue}{\left[ e(k) - e(k-1) \right]}$$
• 增量式PID的输出是位置式的差分：
  $$\Delta u(k) = u(k) - u(k-1).$$
  • 将位置式公式代入差分表达式并整理，得到：
    $$\Delta u(k) = \left(K_p + K_i + K_d\right)e(k) + \left(-K_p - 2K_d\right)e(k-1) + K_d e(k-2).$$
• 对比系数 ，得到方程组：
  $$
  \begin{align}
  A &= K_p + K_i + K_d,\\
  B &= -K_p - 2K_d,\\
  C &= K_d
  \end{align}
  $$
• 解方程组得位置式PID的参数为：
  $$
  \begin{align}
  \color{red}{K_p} &= -B - 2C,\\
  \color{red}{K_i} &= A + B + C,\\
  \color{red}{K_d} &= C
  \end{align}
  $$

增量式PID和位置式PID简单对比

附录：现实场景中的一些trick

常用形式一：使用了 \( \lambda(k-1) \)的位置式PID

• 适用场景：在一些场景中，控制变量 \( \lambda \) 需要平滑调整 ，而非完全重新计算（比如oCPX出价中）
• 常用位置式PID来输出某个变量的增量（直接计算全量 \( \lambda(k) \) 可能导致相邻时间片的出价跳跃，而基于前一时刻的 \( \lambda(k-1) \) 进行增量调整，可以保证控制量的连续性），工程师可能会将位置式PID改写为以下形式：
  $$
  \begin{align}
  \lambda(k) &= \lambda(k-1) + \color{red}{\Delta \lambda(k)} \\
  \lambda(k) &= \lambda(k-1) + \color{red}{u(k)} \\
  \lambda(k) &= \lambda(k-1) + \color{red}{\left[ K_p e(k) + K_i \sum e(k) + K_d (e(k)-e(k-1)) \right]} \\
  \end{align}
  $$
  • 理解：这是一个位置式PID ，其中 \(\lambda\) 与PID无关，属于被控对象的一部分，其中PID输出为该变量的增量：
    $$ u(k) = \color{red}{\Delta \lambda(k)} = \color{red}{\left[ K_p e(k) + K_i \sum e(k) + K_d (e(k)-e(k-1)) \right]} $$
  • 问题：当 \(e(t)\) 为0时，由于积分项的存在，\(\color{red}{\Delta \lambda(k)}\) 可能不为0，\(u(k)\) 还会持续变化，这个是否符合预期？这个问题的简单理解如下：
    • 对于系统需要 \(u(k)\) 持续增加的场景，比如系统是一个压力越来越大的弹簧，\(u(k)\) 是施加的反向力，需要逐步增大，则这种情况天然适配这种设计，持续增加的 \(u(k)\) 能与系统逐步增加的压力抵消，保持稳态
    • 对于系统不需要 \(u(k)\) 持续增加的场景，假设 \(\color{red}{\Delta \lambda(k)} > 0\)，则 \(u(k)\) 会继续增大，超调以后，积分项会逐步减少，同时 \(e(t) \neq 0\)，也会开始减小 \(\color{red}{\Delta \lambda(k)} \)，逐步地，\(\color{red}{\Delta \lambda(k)} = 0\)，然后逐步变成负值，直到 \(e(t)\) 再次为0时，此时的积分项比上一轮更小了，\(\color{red}{\Delta \lambda(k)}\) 也更小了，甚至为负，也就是说，对于积分项逐步地应该也会收敛到0
• 注：由于\(\lambda(k-1)\)中其实包含了累计误差的信息，可以进一步不考虑积分项（微分项一般不用考虑，这里顺便消除了），甚至可以简化为下面的公式形式：
  $$\lambda(k) = \lambda(k-1) + \color{blue}{K_p} \color{red}{e(k)}$$
  • 这种形式的优点：一定程度上，\(\lambda(k-1)\)中其实包含了累计误差的信息，可以在不包含 \(K_i\)的情况下实现类似积分项效果，存储和更新 \( \lambda(k-1) \) 比维护全局积分项 \( \sum e(k) \) 更简单（后者需持久化历史状态）
  • 此时也可以用增量式PID来理解这种公式，本文下面会聊到增量式PID下这种形式的含义

附录：增量式PID的实际使用简化

• 增量式PID可能简化为只保留 \(e_t\) 相关的项，即：
  $$u(k) = u(k-1) + \color{blue}{A} \color{red}{e(k)}$$
• 对照增量式PID的公式：
  $$
  \begin{align}
  u(k) &= u(k-1) + \color{red}{\Delta u(k)} \\
  u(k) &= u(k-1) + (K_p + K_i + K_d) \color{red}{e(k)} - (K_p + 2K_d) \color{red}{e(k-1)} + K_d \color{red}{e(k-2)} \\
  u(k) &= u(k-1) + A \color{red}{e(k)} + B \color{red}{e(k-1)} + C \color{red}{e(k-2)}
  \end{align}
  $$
• 可以看出此时相当于没有 \(C = K_d = 0\)，结合 \(B = - (K_p + 2K_d) = 0\)，进一步有 \(K_p = 0\)，最终可得：
  $$ \color{blue}{A} = K_i $$
• 也就是说，此时相当于只包含 \(K_i\) 项的位置式PID
  • 进一步理解：其实只包含 \(K_i\) 项的位置式PID ，本质上可以等价于包含 \(K_i,K_p\) 项的位置式PID（但需要 \(K_i,K_p\) 系数服从某种关系）

附录：oCPX下PID的理想设计方式

• oCPX的真正目标 ：oCPX的最终目标是保整个投放周期内的ROI满足约束
• 应该如何设计误差项 \(e(t)\)？
  • 如果 \(e(t)\) 表示时间片 \(t\) 的达成情况 ，则其值是根据时间片 \(t\) 内的消耗和收入计算出来的，则难以真正满足全天的ROI达成；此外，实际场景中，单个时间片的数据可能会非常稀疏 ，特别是oCPX的场景计算ROI需要用到订单数据，中小广告主的订单数据往往是非常稀疏的
    • 存在稀疏的情况。解决思路：一个思路改进是可以考虑用预估值去代替真实值，从而缓解稀疏问题
    • 难以达成全站ROI目标。解决思路：在原有PID基础上，引入累计偏差补偿项 \(\gamma \cdot \text{Global}_\text{Error}\)，确保全天ROI收敛
  • 如果 \(e(t)\) 表示截止到时间片 \(t\) 的达成情况 ，值是根据投放周期开始到 \(t\) 时间片的消耗和收入计算出来的，则 \(e(t)\) 直接表达了截止到时间片 \(t\) 的ROI达成情况，这种设计下 \(e(t)=0\) 时说明全天刚好达成
    • 可以缓解稀疏问题
    • 更贴近oCPX产品的目标
  • 结论：
    • 订单稠密的场景可以考虑使用时间片 \(t\) 的达成情况 ，再增加引入累计偏差补偿项 \(\gamma \cdot \text{Global}_\text{Error}\)，确保全天ROI收敛
    • 订单稀疏的场景使用截止到时间片 \(t\) 的达成情况 ，可以缓解稀疏问题
• 对于无法获取分时间特征（无法计算位置式PID的积分项），且无法存储上一时间片的PID输出（无法用增量式PID）的情况，如何设计PID？
  • 一个思路是使用截止到时间片 \(t\) 的达成情况 ，且仅使用 \(K_p\) 参数，这样至少目标是达成全天的ROI目标，这种方法可能导致商家存在稳态误差（因为没有积分项）
• 其他优化点：
  • 可以对 \(e(t)\) 做一个量纲映射，比如除以目标ROI以保证误差在指定范围内（特别是对于保CPS的场景，不同商家的CPS甚至不在统一量纲，想用相同的 \(K_p,K_i,K_d\) 参数来控制所有商家是困难的）：
    $$ e(t) = \frac{真实ROI-目标ROI}{\color{red}{目标ROI}}$$
  • 初期数据量较少时不要调控，因为数据还不够准确，初期就开始调控可能导致商家初期出价波动较大
  • 可以统计过去一天或多天的PID输出作为下一天的初始出价 K 值，使得PID更容易达成，也让商家初期的消耗更符合ROI目标

附录：PID的其他优化

积分限幅

• 现象：当因为不可抗力影响系统时，误差积分会一直增加，为了防止不可抗力消失的瞬间出现问题，可以给误差积分增加一个限制幅度（最大值）
• 举例：无人机中这个现象可以看做一段时间内是有人压着无人机不许升高；在智能算力场景可以看做是非高峰期间，无论PID如何调整，TP999都到不了目标值
• 解法：对误差积分项加一个上限，称为“积分限幅”

积分分离

• 现象：目标有修改时，误差会突然增加，短时间内误差非常大，容易出现超调
• 解法：对误差做一个条件判断，如果瞬间出现较大误差（比如超过一个阈值），可以让KI项的系数为0（注意不是清空KI项），只使用Kp项来调节；直到误差重新回到阈值以下，KI再生效

Kp上调下调差异化

• 在一些场景上，如果对超成本和欠成本有倾向，可以通过设置上调和下调不同Kp来实现，比如，对于厌恶超成本的场景，可以适当增大下调系数，提升上调系数