跳转至

所有文章

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

饮料企业多工厂生产与补货优化

本文基于某饮料企业的工厂、仓库与商品相关的历史信息，结合随机模拟的售价与成本数据，构建了多工厂、多仓库的生产与补货优化模型。

数值试验表明，本文构建的优化后的生产与补货模型能够比基线模型（简单基于历史销量而固定生产量）多获得约 500 万元的利润，且在补货行为上更具优势。对工厂和仓库容量的灵敏度分析表明，工厂 2 和 DC4、5、7、14 多具有当前容量较小、运输成本低、历史销量高等特点，对它们进行扩容能够取得显著的回报增益。对整托约束的松弛表明，整托运输虽以节省运输成本为目的，但实际却可能造成运输资源的浪费，而考虑适当放松整托约束有潜力能够提高约 100 万元的利润。

问题目标示意图

使用 Conformal Learning 预测企业信贷违约情况

本文使用 8 种经典的分类器，基于逆概率错误进行 Conformal Learning。

本文使用了 nonconformist 包，它在使用 Conformal Learning 进行分类预测时的核心步骤是：

  1. 在训练集上训练，这一步和常规的机器学习训练相同。
  2. 在校准集上校准，得到每个校准集样本属于每个标签的预测概率。
  3. 用一个 ErrFunc 衡量每个校准集样本的预测效果，作为 nonconformity score。最简单的是 InverseProbabilityErrFunc，它等于 1-predict_probability[true_y]。例如，某个样本的真实标签是 1，而模型预测出该样本属于标签 1 的概率是 0.9，则 ErrFunc 的值是 1-0.9=0.1。
  4. 在测试集上测试，得到每个测试集样本属于每个标签的预测概率。
  5. 用 ErrFunc 衡量每个测试集样本的预测效果。
  6. 对每一个测试集样本，计算：有多少比例的校准集样本的 nonconformity score 大于或等于当前测试样本的 nonconformity score，记为 p。p 越大，说明校准集中有非常多的样本比当前测试集样本的预测效果更差，说明第 j 个测试样本属于第 i 个类的可能性越大。
  7. 返回 p > significance。得到一个 N*2 的 True 和 False 组成的二维矩阵，每一行代表一个测试集样本，每一列代表是否将该标签纳入该样本的 prediction set 中。

image-20230606154615357

本项目的完整展示文件在这里。

深度学习 Cheat Sheet

本文整理了深度学习期末考试 Cheat Sheet。内容包括：

  • 神经网络基础（激活函数、梯度下降优化方法、参数初始化）
  • 前馈神经网络（Dense NN、反向传播算法）
  • 卷积神经网络（CNN）
  • 循环神经网络（RNN、LSTM、GRU、随时间的反向传播）
  • 生成模型（自编码器、变分自编码器、GAN、WGAN）
  • Transformer（注意力机制、多头注意力、位置编码）
  • 强化学习基础：多臂老虎机（遗憾值、Eoplore Then Commit、Upper Confidence Bound）
  • 强化学习进阶：马尔可夫决策过程、动作价值函数、贝尔曼方程、计算状态价值、Q-Learning

PDF 版 Cheat Sheet 在这里。

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