跳转至

2023 年 5 月

Dijkstra 算法求解最短路径问题

本文使用 Python 实现了 Dijkstra 算法求解最短路径问题。在算法实现中，使用数组存储网络中各结点之间的距离，使用二叉堆存储 T 集合，并尽量使用向量化计算加快运行速度。

最终在三种网络结构下的运行时间为：

输入文件 grid_150_150 random_20000_40000 dense_1000
运行时间 302.93ms 292.14ms 135.29ms

但在最开始实现 Dijkstra 算法时，我的程序需要花 5 秒才能完成计算。经过逐步优化，运行时间可以降为 3 秒甚至 0.13 秒。把算法效率优化到极致的过程是非常有收获的，既加深了对算法本身的理解，又学习了许多优化算法的经验。

优化算法的经验

  1. 多考虑用向量化计算，尽量避免使用 for 循环。
  2. 想清楚算法的终止条件是什么。例如，在 One-to-all 问题中，可以把“遍历完T集合中的所有元素，直到 T 集合为空集”作为终止条件，也可以把“ P 集合中的元素个数等于网络中的结点个数”作为终止条件。虽然两者都能得到正确的结果，但当 P 集合中的元素个数等于网络中的结点个数时，T 集合中的元素是不需要再更新的，所以后者比前者所需要的运算次数少得多。
  3. 熟悉 NumPy 等科学计算库的实现细节。例如，在 NumPy 中，np.ones 和 np.empty 都可以用来创建指定形状的数组，其中 np.ones 会创建一个填充 1 的数组，而 np.empty 会在一块内存上创建一个未初始化的数组。由于 np.empty 不会进行初始化，因此生成速度要比 np.ones 更快。
  4. 使用合适的数据类型。例如，若问题中的变量可以肯定为整数，则可以考虑用 dtype=np.int32 或者 dtype=np.int16，节约内存空间。不同整数数据类型所能表示的整数范围如下：
Type Capacity
Int16 (-32,768 to +32,767)
Int32 (-2,147,483,648 to +2,147,483,647)
Int64 (-9,223,372,036,854,775,808 to +9,223,372,036,854,775,807)
  • 统计
  • 阅读时间 4 分钟

Conformal Learning 求解回归问题和多标签分类问题

Conformal Learning 是一种非参数统计方法，利用“样本属于某个标签时的离群程度”来进行回归和分类。本文分别使用“老忠实泉的爆发和等待时间数据”进行回归预测，使用“玻璃分类数据”进行多标签分类预测。

参考文献：A Tutorial on Conformal Prediction

回归问题

  1. 对于训练集的某一个样本 \(i\)，找到离样本 \(i\) 最近的样本。

    • 若最近的样本只有一个，记为样本 \(j\)，则计算样本 \(i\) 和 样本 \(j\) 的标签之间的差值的绝对值；

    • 若最近的样本有多个，则先计算这多个样本的标签的中位数，再将样本 \(i\) 的标签值与该中位数做差后取绝对值。

  2. 此“绝对值”就衡量了样本 \(i\) 的离群程度。

  3. 对于一个新样本 \(n\)，同样找到离样本 \(n\) 最近的样本，用“离样本 \(n\) 最近的一个或多个样本的标签的中位数”作为新样本的标签预测值。

  4. 根据信心水平 \(level\)（例如 \(90\%\)），选定一个离群程度，使得该离群程度在所有训练样本的离群程度中的大小排名分位数是 \(1-level\)（例如 \(10\%\)，即100个数中第10大的数）。

  5. 在该预测值的基础上加减上一步选定的离群程度，就得到新样本标签值的预测区间。

分类问题

  1. 对于一个新样本，为其赋予所有可能的标签后，将其纳入训练样本中，形成一个 Bag。
  2. 对于 Bag 中的每一个样本：
    1. 对于与该样本的标签相同的其他样本，计算它们与该样本的距离，从中选择最小的，作为分子。
    2. 对于与该样本的标签不同的其他样本，计算它们与该样本的距离，从中选择最小的，作为分母。
    3. 将前两步的分子除以分母，即可衡量“为该样本赋予该标签时的离群程度”。该值越大，说明分子越大、分母越小。
      • 分子越大，说明虽然标签相同但距离很远，可以推测这个样本很可能并不属于这个标签。
      • 分母越大，说明虽然标签不同但距离很近，可以推测这个样本很可能属于其他标签。
  3. 对于每一个可能的标签，根据信心水平 \(level\)（例如 \(90\%\)），判断：当新样本确实属于这个标签时，Bag 中有多少比例样本的离群程度比新样本的离群程度更高。如果这个比例超过了 \(1-level\)（例如 \(10\%\)），则将这个标签加入到预测标签集中。
  4. 输出预测标签集，它可能有一个或多个预测值，也可能是空集。
  • 统计
  • 阅读时间 6 分钟

多重假设检验

本文使用 Benjamini-Hochberg Procedure 和 Adaptive z-value Procedure 进行多重假设检验，在实际数据上验证了后者的优势，并展示了估计原假设的分布参数的重要性。

image-20230503022842066

  • 运筹学
  • 阅读时间 6 分钟

Gurobi 求解线性规划问题

本文针对钢铁企业对供应商的选择问题，构建线性规划模型，并使用 Gurobi 求解器进行求解。

题目背景

考虑一家小型的钢铁企业，该企业炼钢时使用的主要原材料是炼焦煤，每年的需求量在 100 到 150 万吨。现在需要帮助该公司安排明年的生产，选择原料的供应商。目前他们收到了 8 家供应商的报价，如下表。表格中的信息包括了每家供应商的最大供应量、是否为工会的公司、运输的方式、炼焦煤的可燃率、单位价格。

1 2 3 4 5 6 7 8
供应量 （千吨/年） 300 600 510 655 575 680 450 490
工会U/ 非工会 N U U N U N U N N
卡车T/ 铁路 R R T R T T T R R
可燃率（%） 15 16 18 20 21 22 23 25
价格 (￥/吨) 49.5 50.0 61.0 63.5 66.5 71.0 72.5 80.0

GPT 论文精读笔记

Generative Pre-trained Transformer（GPT）系列是由 OpenAI 提出的非常强大的预训练语言模型，这一系列的模型可以在非常复杂的 NLP 任务中取得非常惊艳的效果，例如文章生成，代码生成，机器翻译，问答等，而完成这些任务甚至 并不需要有监督学习进行模型微调 。

本文梳理了 GPT 系列文章中介绍的的关键技术，包括：

  • GPT-1 的解码器、微调、输入形式；
  • GPT-2 的 Zero-shot 和 Prompt；
  • GPT-3 的 Few-shot；
  • Instruct GPT 如何通过基于人类反馈的强化学习生成有帮助的和安全的文本。
  • 统计
  • 阅读时间 1 分钟

为什么 P 值是均匀分布的？

在学习多重假设检验时，提到了“P 值是均匀分布的”这个结论。本文对“单边检验”和“双边检验”的情形，证明了 P 值是均匀分布的。

直觉理解

直觉理解

以单边左侧检验为例（单边检验最好理解，不用考虑两侧的情况），可以这样想：

P 值小于 \(0.25\) 意味着什么？意味着观测到的统计量要小于 \(0.25\) 分位数。

观测到的统计量小于 \(0.25\) 分位数的概率是多少？就是 \(0.25\)。

也就是说，P 值小于 \(0.25\) 的概率就是 \(0.25\)。

把 \(0.25\) 换成任何一个 \(0\) 到 \(1\) 之间的值，都可以得到：P 值小于某个数的概率就是这个数本身。这就是均匀分布。

证明

单边检验