Hexo

凡事预则立,不预则废


  • Home

  • Tags

  • Archives

  • Navigation

  • Search

Python——OrderedDict类的使用


整体说明

  • OrderedDict 是 Python 标准库中的一个类,它位于 collections 模块下
  • 相对于普通字典,OrderedDict 能够记住元素插入的顺序,在迭代时,元素会按照插入的先后顺序被返回
  • OrderedDict 类对象的主要特点有:
    • 仍然是一个字典 :即仍然是 Key-Value 结构,且 Key 值不能重复
    • 保持插入顺序 :迭代时,元素会按照插入的顺序返回
    • 顺序敏感 :如果两个 OrderedDict 包含相同内容,但元素插入顺序不同,它们会被视为不相等
    • 支持移动操作 :可以通过 move_to_end() 方法将元素移动到开头或末尾
    • 删除操作保留顺序 :删除元素后,剩余元素的顺序保持不变

OrderedDict 的基本用法

  • OrderedDict 的一些常见操作示例:
    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
    from collections import OrderedDict

    od = OrderedDict()
    od['a'] = 1
    od['b'] = 2
    od['c'] = 3
    od['b'] = 10

    # 迭代时保持插入顺序
    for key, value in od.items():
    print(key, value) # 输出: a 1, b 10, c 3

    print('---')
    # 移动元素到开始
    od.move_to_end('b', last=False)
    for key, value in od.items():
    print(key, value) # 输出: b 10, a 1, c 3

    print('---')
    # 移动元素到末尾
    od.move_to_end('b', last=True)
    for key, value in od.items():
    print(key, value) # 输出: a 1, c 3, b 10

    print('---')
    # 删除元素后结果不变
    del od['c']
    for key, value in od.items():
    print(key, value) # 输出: a 1, b 10

比较:与普通字典的区别

  • 在 Python 3.7 及以后的版本中,普通字典也会保持插入顺序,但 OrderedDict 仍然有其独特优势:
    • 明确的顺序语义 :使用 OrderedDict 可以更清晰地表达代码对顺序的依赖
    • 支持顺序相关的方法 :如 move_to_end()、popitem(last=False) 等,且这两个函数都可以通过 last 参数指定是操作第一个还是最后一个
    • 顺序敏感的比较 :两个字典即使包含元素相同,但元素顺序不同也会被视为不等

Math——博弈论-Shapley-Value


整体说明

  • Shapley Value(沙普利值) 是合作博弈论中的一个核心概念,由诺贝尔经济学奖得主 Lloyd Shapley 于 1953 年提出
  • Shapley Value 用于解决一个基本问题:在一个多人合作博弈中,如何公平地分配所有合作者共同创造的总收益?
  • Shapley Value 给出了一种按照每个参与者的“边际贡献”来分配总收益的数学方法

Shapley Value 核心思想

  • Shapley Value 分配的唯一标准是:每个参与者获得的收益,应该等于他在所有可能的加入顺序下,对联盟平均边际贡献的期望值

Shapley Value 数学定义

  • 场景设定:
    • 参与者集合为 \(N = \{1, 2, \dots, n\}\)
    • 特征函数 \(v(S)\):表示任意子集 \(S \subseteq N\) 合作所能创造的总价值(满足 \(v(\emptyset) = 0\))
  • 参与者 \(i\) 的 Shapley Value \(\phi_i(v)\) 定义为:
    $$
    \phi_i(v) = \frac{1}{n!} \sum_{\pi \in \Pi_n} \left[ v(S_{\pi,i} \cup \{i\}) - v(S_{\pi,i}) \right]
    $$
  • 其中:
    • \(\Pi_n\) 是所有 \(n!\) 种排列(加入顺序)的集合
    • \(S_{\pi,i}\) 是在排列 \(\pi\) 中出现在参与者 \(i\) 之前的所有参与者集合
    • 方括号内就是参与者 \(i\) 加入当前联盟 \(S_{\pi,i}\) 时带来的边际贡献

Shapley Value 直观理解

  • 假设有三个朋友 A、B、C 一起做项目,总共赚了 100 元,他们想知道:每个人应该分多少才公平 ?
  • Shapley Value 的思路是:
    • 1)考虑所有可能的加入顺序(3! = 6 种)
    • 2)在每种顺序下,计算每个人“刚好加入时”带来的价值增量
    • 3)把每个人在所有顺序下的边际贡献求平均
  • 例如:
    加入顺序 A 的边际贡献 B 的边际贡献 C 的边际贡献
    A → B → C v(A) v(AB) - v(A) v(ABC) - v(AB)
    A → C → B v(A) v(ABC) - v(AC) v(AC) - v(A)
    … … … …
  • 最终:
    $$
    \phi_A = \frac{\text{A 在 6 种顺序下的边际贡献之和} }{6}
    $$

更细节的示例

  • 假设一个简单的投票博弈:
    • 参与者:A、B、C
    • 总收益:1 元
    • 获胜规则:多数票(至少 2 票)
  • 特征函数:
    • \(v(\{A,B\}) = 1\)
    • \(v(\{A,C\}) = 1\)
    • \(v(\{B,C\}) = 1\)
    • \(v(\{A,B,C\}) = 1\)
    • 其余子集为 0
  • 计算 A 的 Shapley Value:
    • 考虑 6 种顺序:
      • A 先来:边际贡献 = 0(A 一个人无法获胜)
      • A 在 B 之后加入(B → A):此时已有 B(0 票),A 加入后达到 2 票 → 边际贡献 = 1
      • A 在 C 之后加入 → 边际贡献 = 1
      • A 在 B、C 之后加入 → 边际贡献 = 0(已经赢了)
  • 平均后:\(\phi_A = \frac{1}{3}\)
  • 同理:
    • \(\phi_B = \frac{1}{3}\)
    • \(\phi_C = \frac{1}{3}\)
  • 结果:三个人平分收益,符合多数投票博弈的对称性直觉

Shapley Vlaue 满足四大公理(唯一性保证)

  • Shapley Value 是唯一同时满足以下四条公理的分配方式:
    • 效率性(Efficiency / 帕累托最优) :所有参与者的 Shapley Value 之和等于总收益:
      $$ \sum_{i=1}^n \phi_i(v) = v(N) $$
      • 合作产生的总收益必须被全部分配完,既没有剩余,也没有透支,即所有人的沙普利值之和等于团队总收益
    • 对称性(Symmetry) : 如果两个参与者对任何联盟的贡献相同,则他们获得相同的收益
    • 线性性(Additivity) : 若游戏可分解为两个独立子游戏的求和,则 Shapley Value 也相应求和
    • 哑元性(Dummy Player / 零贡献者) : 如果一个参与者对所有联盟的边际贡献均为 0,则其收益为 0
  • 这些公理使得 Shapley Value 成为一种公平、无偏、可解释 的信用分配方式

Shapley Value 的其他定义形式

  • Shapley Value 是一种公平分配合作总收益的方法:每个人得到的等于他在所有可能加入顺序下的平均边际贡献
  • 假设有一群人要组成一个团队,每个人是一个接一个加入的
    • 当一个人加入团队时,团队的总收益会因为他的加入而增加,这个增加的量就是他的“边际贡献”
    • 参与者加入团队的先后顺序会影响他的边际贡献
    • 沙普利值的做法是:考虑所有可能的加入顺序,计算该参与者在每种顺序下的边际贡献,然后求平均值

Shapley Value 数学公式

  • 沙普利值的计算公式如下:
    $$ \phi_i(v) = \sum_{S \subseteq N \setminus \{i\} } \frac{|S|! (n - |S| - 1)!}{n!} (v(S \cup \{i\}) - v(S)) $$
    • \(N\):所有参与者的集合
    • \(n\):参与者的总人数
    • \(S\):不包含参与者 \(i\) 的某个子联盟
    • \(|S|\):子联盟 \(S\) 中的人数
    • \(v(S)\):子联盟 \(S\) 能创造的收益
    • \(v(S \cup \{i\}) - v(S)\):参与者 \(i\) 加入联盟 \(S\) 后带来的边际贡献
    • \(\frac{|S|! (n - |S| - 1)!}{n!}\):这是一个权重,代表在所有可能的排列顺序中,刚好形成联盟 \(S\) 并且 \(i\) 紧接着加入的概率
1…103104105…352
San Ye

San Ye

Stay Hungry. Stay Foolish.

704 posts
53 tags
© 2026 San Ye
Powered by Hexo
|
Theme — NexT.Gemini v5.1.4