题目描述

• 餐馆有12生肖优惠券,每天给小明等概率随机发放一张,问: 小明集齐12中生肖优惠券的天数
• 相关延伸: 掷骰子, 要求每个面都出现一次, 求投掷次数的期望

问题求解

• 思路:
  • 把天数 \(X\) 这个随机变量变成12个随机变量的和$$X = \sum_{i=1}^{12}x_{i}$$
  • 于是可以把期望分解为12个随机变量的期望和$$E(X) = \sum_{i=1}^{12}E(x_{i})$$
• 第一种优惠券(12种中的任意一种均可):
  • 第一天随机拿到一个优惠券一定能够对应其中某一个生肖,概率为 \(p_{1} = 1\)
  • 期望天数 \(E(x_{1})\) 与概率的关系为 \(E(x_{1})\cdot p_{1} = 1\)
    • 一个直观的说明,为什么 \(E(x_{1})\cdot p_{1} = 1\)：由于每一天成功的概率为 \(p_{1}\)，不成功概率为 \(1-p_{1}\)，显然为二项分布,由二项分布的期望应该为1次 ，即 \(np_{1}=1\)，其中n就是我们天数的期望(注意:二项分布的期望与这里的天数期望不同,后者为使得二项分布期望为1所需要的天数)
    • 上面的证明不够严谨,严谨的数学证明如下:
      • 假设期望天数是 \(E\)，每天成功的概率为 \(p\)，下面我们求成功和不成功的概率分布
      • 第一天成功的概率为 \(p\)，成功时只需要 \(1\) 天即可, 即有 \(p\) 的概率需要 \(1\) 天
      • 第一天没成功的概率为 \(1-p\)，不成功时需要将当前日子(\(1\) 天)算上,然后回到原点,重新开始,即有 \(1-p\) 的概率需要 \(1+E\) 天
      • 期望公式
        $$E = p*1 + (1-p)(1+E)$$
      • 化简为:
        $$pE = 1$$
  • 需要天数的期望为$$E(x_{1}) = \frac{1}{p_{1}} = 1$$
• 第二种优惠券(11种中的任意一种均可):
  • 每天随机收到的优惠券有 \(p_{2} = \frac{11}{12}\) 的概率满足剩余的11个生肖中的一个
  • 期望天数 \(E(x_{2})\) 与概率的关系为 \(x_{2}\cdot p_{2} = 1\)
  • 需要的天数期望为$$E(x_{2}) = \frac{1}{p_{2}} = \frac{12}{11}$$
• …
• 以此类推可得:
  $$
  \begin{align}
  E(X) &= \sum_{i=1}^{n}E(x_{i}) \\
  &= \sum_{i=0}^{11}\frac{12}{12-i} \\
  &= \sum_{i=1}^{12}\frac{12}{i} \\
  &= 12\sum_{i=1}^{12}\frac{1}{i} \\
  \end{align}
  $$
• 由于调和级数的和与n的自然对数有关系,详情参考调和级数的和
  $$
  \begin{align}
  \sum_{i=1}^{n}\frac{1}{i} = ln(n) + \gamma + \epsilon_{n}
  \end{align}
  $$
  • \(\gamma\) 为欧拉-马歇罗尼常数,近似值为γ≈0.57721
  • \(\epsilon_{n}\) 约等于 \(\frac{1}{2n}\)，随着n的不断增大, \(\epsilon_{n}\) 趋于0
• 所以有
  $$
  \begin{align}
  E(X) &= 12\sum_{i=1}^{12}\frac{1}{i} \\
  &\approx 12(ln(12)+\gamma+\frac{1}{24})
  \end{align}
  $$
• 将12生肖推广到n,有
  $$
  \begin{align}
  E(X) &= n\sum_{i=1}^{n}\frac{1}{i} \\
  &\approx n(ln(n)+\gamma+\frac{1}{2n}) \\
  &\approx nln(n)
  \end{align}
  $$

寻找最优者：不可逆的做出选择，如何使得选到最优者的概率最大，又称为1/e法则，“秘书问题”或“相亲问题“

题目描述

• 由于无人知道缘分何时到来，假设人的一生会遇到100个异性，这100个人参差不齐，其中有个人是最好的，100人随机的排着队出现，而我们对每个人必须决定是否接受，而且一旦决定后不能修改，那么用什么策略选择更有机会选到最好的那一个呢?

解决方案

策略设想

• 拒绝前 k 个人，然后从第 k+1 个开始，只要 优于前面的所有人 ，则接受
• k 值的设定比较难，太小了容易找到不好的，太多了容易错过最好的

证明

• 假设最优者出现在第 \(i(k< i \leq n)\) 个(事件A)，那么最优者被选中(事件B)的概率为前i-1个中的最优者在前k个人中的概率
  $$ P(B|A) = \frac{k}{i-1} $$
  • \(P(B|A) = P(最优者被选中|第 i 个为最优者)\)
• 最优者出现在第 \(i\) 个的概率为
  $$P(B) = \frac{1}{n}$$
• 最优者被选中的概率为
• 接下来的证明用到了调和级数的和，详情参考调和级数的和
  $$
  \begin{align}
  \sum_{i=1}^{n}\frac{1}{i} = ln(n) + \gamma + \epsilon_{n}
  \end{align}
  $$
  • \(\gamma\) 为欧拉-马歇罗尼常数，近似值为γ≈0.57721，下面的推导都不需要精确解的，所以可以使用该公式
  • \(\epsilon_{n}\) 约等于 \(\frac{1}{2n}\)，随着n的不断增大， \(\epsilon_{n}\) 趋于0
    $$
    \begin{align}
    P(B) &= \sum_{A}P(B,A) \\
    &= \sum_{A}P(B|A)P(A) \\
    &= \sum_{i=k+1}^{n}\frac{k}{i-1}\frac{1}{n} \\
    &= \sum_{i=k+1}^{n}\frac{k}{n}\frac{1}{i-1} \\
    &= \frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1} \\
    &= \frac{k}{n}\sum_{i=k}^{n-1}\frac{1}{i} \\
    &= \frac{k}{n}(\sum_{i=1}^{n-1}\frac{1}{i} - \sum_{i=1}^{k-1}\frac{1}{i}) \\
    &\approx \frac{k}{n}((ln(n-1)+C)-(ln(k-1)+C)) \\
    &= \frac{k}{n}ln(\frac{n-1}{k-1}) \\
    \end{align}
    $$
• 当n和k足够大时有
  • (不能证明 k 也会足够大，但是直觉上 n 足够大 k 也会足够大，因为 n 足够大时往往需要拒绝更多的人)
    $$\frac{n-1}{k-1} = \frac{n}{k}$$
• 令 \(x=\frac{k}{n}\)，则有
  $$
  \begin{align}
  f(x) &= xln\frac{1}{x} \\
  {f}’(x) &= ln(\frac{1}{x})+(-\frac{1}{x^2}\cdot x \cdot x) \\
  &= ln(\frac{1}{x})-1
  \end{align}
  $$
• 求 \(f(x)\) 的最大值，令 \({f}’(x)=0\) 有
  $$ ln(\frac{1}{x})-1 = 0 $$
• 解方程得
  $$ x = \frac{1}{e} $$
• 也就是说当 \(\frac{k}{n} = \frac{1}{e} \) 时，找到最优者的概率最大

策略描述

• 拒绝前 \(\frac{n}{e}\) 个人(也就是拒绝前37%的人)，然后从第 \(\frac{n}{e}+1\) 个开始，只要优于前面的所有人 ，则接受
• 这种方式可以保证我们有最大的概率找到最优者

初始题目为1米长的绳子剪成三段后能够构成三角形的概率，实际上绳子的长度可以是任意的，解法都一样

题目描述

• 一根绳子长度为 n，剪三段后能构成三角形的概率是多少？
• 由于长度与概率无关，所以接下来我们把绳子当做长度为 1 米来处理

解决方案

• 三段绳子的长度分别为 x，y，1-x-y
• 首先需要满足
  $$
  \begin{align}
  x &> 0 \\
  y &> 0\\
  1-x-y &> 0 \\
  \end{align}
  $$
  • 以 x 为横坐标，y 为纵坐标画图得到阴影区域面积为 \(\frac{1}{2}\)
• 图片来源于：https://blog.csdn.net/fanoluo/article/details/40374571*
• 进一步分析三段绳子能生成组成三角形的概率
  $$
  \begin{align}
  x+y &> 1-x-y \\
  y + 1-x-y &> x\\
  x + 1-x-y &> y \\
  \end{align}
  $$
  • 进一步分析得到阴影部分面积为 \(\frac{1}{8}\)
• 图片来源于：https://blog.csdn.net/fanoluo/article/details/40374571*
• 所以有
  $$P = \frac{1/8}{1/2} = \frac{1}{4}$$

整体说明

• 蓄水池采样 (Reservoir Sampling) 算法是一种在数据流中进行随机抽样的方法
• 它的独特之处在于，不知道数据流的总长度 ，但可以实现对样本等概率采样
• 场景：处理一个无法放入内存的巨大文件，或者一个实时传入的无限数据流
  • 在这种情况下，需要从这个流中随机选择 \(k\) 个元素，并且要确保每个元素被选中的概率是相等的

算法流程

• 蓄水池采样算法的核心思想是，随着数据流的不断输入，动态地更新一个大小为 \(k\) 的“蓄水池”
• 以下是该算法的详细流程：
• 第一步：初始化蓄水池
  • 创建一个大小为 \(k\) 的数组或列表，这就是我们的蓄水池 (Reservoir)
    • 1）从数据流中读取前 \(k\) 个元素
    • 2）将这 \(k\) 个元素直接放入蓄水池中
• 第二步：处理后续元素
  • 从数据流中继续读取第 \(i\) 个元素，其中 \(i > k\)。对于每一个新元素，执行以下操作：
    • 1）生成一个 \(1\) 到 \(i\) 之间的随机整数 \(j\)
    • 2）如果 \(j\) 满足条件 \(1 \le j \le k\)，则将当前元素替换蓄水池中索引为 \(j\) 的元素
    • 3）如果 \(j > k\)，则不做任何操作，直接丢弃该元素
• 第三步：重复
  • 1）重复第二步，直到数据流结束
  • 2）当数据流处理完毕后，蓄水池中剩下的 \(k\) 个元素就是我们最终的随机样本

算法证明

• 蓄水池采样算法之所以有效，是因为它能确保数据流中的每个元素被选入蓄水池的概率都是 \(k/N\) ，其中 \(N\) 是数据流的总长度。我们通过数学归纳法来简单理解一下
• 初始阶段 ：前 \(k\) 个元素被直接放入蓄水池，因此它们被选中的概率是 \(1\)
• 第 \(i\) 个元素 (\(i > k\)):
  • 第 \(i\) 个元素被选中的概率是 \(k/i\)。这是因为我们生成了一个 \(1\) 到 \(i\) 的随机数，只有当它落在前 \(k\) 个位置时，第 \(i\) 个元素才会被选中并替换掉蓄水池中的一个元素
  • 关键是保持之前元素的概率不变。我们来看一下，在第 \(i\) 步，蓄水池中某个旧元素被保留的概率
    • 在第 \(i-1\) 步结束时，蓄水池中的每个元素被选中的概率是 \(k/(i-1)\)
    • 当第 \(i\) 个元素进入时，这个旧元素被替换的概率是 \(1/i\)（因为它有 \(1/i\) 的概率被选中并替换掉蓄水池中的一个随机位置）
    • 所以，一个旧元素被保留的概率是 \(1 - 1/i = (i-1)/i\)
    • 那么，这个旧元素在第 \(i\) 步结束后仍然留在蓄水池中的概率是：
      $$P(\text{留在蓄水池}) = P(\text{在第 }i-1 \text{ 步被选中}) \times P(\text{在第 }i \text{ 步被保留}) = \frac{k}{i-1} \times \frac{i-1}{i} = \frac{k}{i}$$
  • 通过这个过程，我们可以看到，在处理完第 \(i\) 个元素后，所有 \(i\) 个元素（包括新来的和之前的）被选中的概率都精确地保持在 \(k/i\)。当数据流结束时，假设总长度为 \(N\)，则每个元素被选中的概率都是 \(k/N\)

和Java类似,Python实现了丰富的基本数据结构,但是使用方式和Java有所不同

字符类型

• Python中没有Java以及C++一样的字符类型,只有字符串类型

字符和数字的比较

• 'a'表示的不是字符’a’, 而是字符串”a”,也就是说0 < 'a'这样的写法是不可以的,因为'a'不是一个数字
• 若非要和数字比较,方式如下:

  1 2 3 4 5 6 7 8 9 10 11

  string = "12_abc*ABZ-=" alphanumeric_str = "" for char in string: if (ord(char) >= ord('0') and ord(char) <= ord('9'))\ or (ord(char) >= ord('a') and ord(char) <= ord('z'))\ or (ord(char) >= ord('A') and ord(char) <= ord('Z')): alphanumeric_str += char print(alphanumeric_str) # # output: # 12abcABZ

集合类型的复制

浅拷贝

以list为例

1
2
3
4
5
6
7
8

l = [1, 2, 3]
# method 1
lcopy = l[:] # notice: ls.append(l[:]), 添加的是副本!!!
# method 2
lcopy = l.copy()
# method 3
import copy
lcopy = copy.copy(l)

深拷贝

1
2
3
4

import copy

l = [1, 2, 3, [4, 5, 6]]
l = copy.deepcopy(l)

format函数的使用

• format是用于格化式字符串的函数

• format是字符串自带的函数

  1 2 3 4 5 6 7 8 9 10 11

  # format string print "{} {}".format("hello", "world") print "{0} {1}".format("hello", "world") print "{1} {0} {1}".format("hello", "world") # output 'hello world' 'hello world' 'world hello world' # format number print "{:.2f}".format(3.1415926)

• 其他使用方式之后再补充

字符串到数字的转换

1
2
3
4
5
6
7
8
9

# string to integer, int(str, base=10)
a = "101"
integer = int(a, 10)
integer = int(a, 2)
integer = int(a, 7)

# string to float, float(str)
b = "123.4"
f = float(b)

进制转换

转换示例

1
2
3
4
5
6
7
8
9

# binary, octonary, hexadecimal to decimal(from string)
dec_num = int("1001", 2) # or int("0b1001", 2)
dec_num = int("657", 8) # or int("0657", 8)
dec_num = int("ff", 16) # or int("0xff", 16)

# decimal to binary, octonary, hexadecimal(or string)
bin_num = bin(123) # or str(bin(123))
oct_num = oct(123) # or str(oct(123))
hex_num = hex(123) # or str(hex(123))

总结:

• 词的表示为十进制(123), 二进制(0b110), 八进制(0567), 十六进制(0xff1)
• 词的转换函数如下:

map函数的使用

定义

• Python3

  1	map(function, iterable, ...) -> map

• Python2

  1	map(function, iterable, ...) -> list

示例

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

# Python2
print map(lambda x: x**2, [1, 2, 3])
# output:
[1, 4, 9]

print map(lambda x, y: x+y, [1, 2, 3], [5, 6, 7])
# output:
[6, 8, 10]

# Python3
result = map(lambda x: x**2, [1, 2, 3])
print(list(result))

chain()

• chain() 是 itertools 模块提供的一个非常实用的函数，它能够把多个可迭代对象连接起来，形成一个连续的迭代器

• 基本用法为：

  1 2	from itertools import chain chain(*iterables) # 参数是多个可迭代对象（注意是展开形式）

• 链接多个可迭代对象，可以是不同对象，对象内部的元素也可以是不同类型

  1 2 3 4 5 6 7 8

  from itertools import chain set1 = {1, '2'} set2 = {3, 4} list1 = [5, 6] combined = list(chain(set1, set2, list1)) print(combined) # 输出：[1, '2', 3, 4, 5, 6]（集合元素顺序可能不同）

• 特别说明，chain() 对可迭代对象是依次访问的，只有迭代访问完前面一个采集继续访问另一个

zip() 函数

• 当 zip 函数输入长度不一致时，不会报错，会适配最短长度
• 示例：

  1 2 3 4 5 6

  for a, b in zip([1,2,3],[1,4,4,5,4,5,6,7]): print(a, b) # 1 1 # 2 4 # 3 4

for…else 语句

• 在 Python 中，for...else 是一种特殊的流程控制结构，for...else 的核心是通过 else 子句判断循环是否“自然完成”，而非被 break 强制终止，这在需要验证“遍历完整性”的场景中非常实用

• 其基本语法为：

  1 2 3 4

  for 变量 in 可迭代对象: 循环体（当迭代继续时执行） else: else子句（当循环正常结束时执行）

• 核心逻为：

  • else 子句的执行条件 ：当 for 循环完整遍历了所有元素（即没有通过 break 语句提前退出循环），则循环结束后会执行 else 中的代码
  • else 子句不执行的情况 ：如果循环中遇到 break 语句并跳出循环（提前终止），则 else 子句不会执行

• 示例 1：循环正常结束（执行 else）

  1 2 3 4 5 6 7 8

  for i in range(3): print(i) else: print("循环正常结束，执行 else") # 循环完整遍历了 `range(3)` 的所有元素（0、1、2），没有 `break`，因此 `else` 被执行 # 0 # 1 # 2 # 循环正常结束，执行 else

• 示例 2：循环被 break 终止（不执行 else）

  1 2 3 4 5 6 7 8

  for i in range(3): print(i) if i == 1: break # 当i=1时提前退出循环 else: print("循环正常结束，执行 else") # 循环在 `i=1` 时通过 `break` 提前终止，因此 `else` 子句未执行 # 0 # 1

• 典型应用场景：for...else 常用于判断“是否在循环中找到目标” ，例如在列表中查找元素：

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

  target = 5 nums = [1, 3, 4, 6] for num in nums: if num == target: print(f"找到目标：{target}") break else: # 若循环完整执行（未触发break），说明未找到目标 print(f"未找到目标：{target}") # 由于 `nums` 中没有 5，循环完整遍历后执行 `else`，提示“未找到目标” # 未找到目标：5

dict 特殊初始化逻辑

• 示例：

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

  default_config = { # 默认值定义 "pass_score": 60, "check_mode": "all", "time_limit": 30 } custom_config = { "pass_score": 75, # 覆盖默认：及格线提高到75分 "need_detail": True # 新增：需要详细报告 } # 配置合并，第一个是默认配置，第二个是新增或修改配置 final_config = {**default_config, **custom_config} print(f"最终配置：{final_config}") # 最终配置：{'pass_score': 75, 'check_mode': 'all', 'time_limit': 30, 'need_detail': True}

• 注：Python 3.9+ 还支持更简洁的 | 字典合并运算符（效果完全一致）：

  1	grader_params = grader_config.defaults | grader_dict

• 运行原代码后，grader_params 的结果的是：

  1 2 3 4 5 6

  { "score_threshold": 70, # 自定义覆盖了默认 "check_type": "full", # 保留默认（无自定义冲突） "timeout": 30, # 保留默认 "check_detail": True # 新增自定义配置 }

string 的 rindex 和 rfind 函数用法

• rindex() 和 rfind() 是字符串（str）的内置方法，核心作用是从字符串右侧（末尾）开始查找指定子串的最后一次出现位置 ，返回其索引值

  • 两者用法高度相似，仅在“子串未找到”时的行为不同
    • rfind()：未找到返回 -1
    • rindex()：未找到抛出 ValueError 异常
  • 两者返回子串都是在原字符串中最后一次出现的起始索引（索引从 0 开始）

• 完整语法

  1 2 3 4 5

  # rfind()：未找到返回 -1 str.rfind(sub, start=0, end=len(str)) # rindex()：未找到抛出 ValueError 异常 str.rindex(sub, start=0, end=len(str))

  • sub：必需参数，要查找的子串（可以是单个字符、多个字符的字符串）
  • start：可选参数，查找的起始索引（从左往右的索引，默认 0，即从字符串开头开始限定查找范围）
  • end：可选参数，查找的结束索引（不包含 end 本身，默认 len(str)，即到字符串末尾结束）

• 选择建议：如果不确定子串是否存在，优先用 rfind()（避免异常）；如果明确子串一定存在，用 rindex()（逻辑更简洁）

使用示例

• 基础用法（无 start/end 参数）：从字符串末尾开始查找子串的最后一次出现位置：

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

  s = "hello world, hello python" # 查找 "hello" 的最后一次出现 print(s.rfind("hello")) # 输出 13（第二个 "hello" 的起始索引） print(s.rindex("hello")) # 输出 13 # 查找单个字符 "o" 的最后一次出现 print(s.rfind("o")) # 输出 18（"python" 中的 "o"） print(s.rindex("o")) # 输出 18 # 查找不存在的子串 print(s.rfind("java")) # 输出 -1（不报错） # print(s.rindex("java")) # 抛出 ValueError: substring not found

• 指定 start/end 参数（限定查找范围）：start 和 end 限定“从原字符串的 [start, end) 区间内，从右往左查找”：

  1 2 3 4 5 6 7 8 9 10

  s = "abcdeabcde" # 索引 0-9 # 限定查找范围：start=2，end=8（即子字符串 "cdeabc"，索引 2-7） # 从该区间右侧开始找 "abc"，最后一次出现是索引 5 print(s.rfind("abc", 2, 8)) # 输出 5 print(s.rindex("abc", 2, 8)) # 输出 5 # 限定范围：start=0，end=5（子字符串 "abcde"） # 该区间内 "abc" 只在索引 0 出现，从右找也是 0 print(s.rfind("abc", 0, 5)) # 输出 0

• 查找空字符串（特殊情况）：如果 sub 是空字符串 ""，两者都会返回 end - 1（因为空字符串在任何位置都存在，最后一次位置是 end 前一个索引）：

  1 2 3

  s = "test" print(s.rfind("")) # 新版本输出4，3.9前的旧版本输出 3， print(s.rindex("", 0, 2)) # 新版本输出2，3.9前的旧版本输出 1

附录：与 index()/find() 的对比

• find() / index()：从左侧开始查找子串的第一次出现位置（未找到时 find 返回 -1，index 抛异常）
• rfind() / rindex()：从右侧开始查找子串的最后一次出现位置（未找到时行为同上）
• 示例对比：

  1 2 3 4 5

  s = "abacada" print(s.find("a")) # 0（左侧第一次） print(s.rfind("a")) # 6（右侧第一次，即最后一次） print(s.index("a")) # 0 print(s.rindex("a")) # 6

自定义的HashKey类

什么样的自定义类可以用作HashMap的Key？

• 实现了HashCode方法和equals方法的类

作为Key后的对象有什么要求？

• 该对象的值不能再修改，否则将导致containsKey找不到已经存储的Key
• 注意，Key值被修改后是无论如何都找不到的，因为hash对象变化导致hash方式变了
  • 能正确找到hash桶的对象与目标对象（修改后的值）不相等
  • 与对象与目标对象（修改后的值）相等的对象找不到正确的Hash桶
  • 除非将修改的值改回来

拓展

• 如果是使用TreeMap，则不是考虑hashCode方法，而是其他方法

本文将介绍一般RNN,RNN的变种GRU(门控循环单元)和LSTM(长短期记忆网络)等神经网络结构

• LSTM原始论文: NIPS 2014, Sequence to Sequence Learning with Neural Networks
• GRU原始论文: EMNLP 2014, Learning Phrase Representations using RNN Encoder–Decoder for Statistical Machine Translation

一般的RNN

循环神经网络(Recurrent Neural Network，RNN)

• 将神经单元展开后的示意图如下:

RNN与CNN优缺点比较

此处我们之比较 CNN 和 RNN 在序列预测问题中的优劣

• 关于前馈神经网络:
  • 是一种最简单的神经网络
  • 各神经元分层排列，每个神经元只接受前一层的输入，输出到下一层，已知到输出层
  • 整个网络中没有反馈（后面的 backward 求梯度不能算反馈，这里指一次输入到输出计算各层间没有反馈，数据流只能从上一层到下一层单向流动）
  • 可以用一个有向无环图表示
• CNN:
  • 是一种前馈神经网络(多层感知机)，是多层感知机的变体
  • 采用固定大小的输入并生成固定大小的输出
  • CNN是图像和视频处理的理想选择
• RNN:
  • 不是前馈神经网络，有环
  • 可以处理任意长度的输入输出
  • 使用时间序列信息，能用之前的状态影响下一个状态
  • RNN是文本和语音分析的理想选择
• RNN在处理序列信息的缺点:
  • 对短期输入非常敏感，但是对长期输入不敏感
  • 难以处理长文本中长距离的单词间的关系

LSTM

长短期记忆网络(Long Short-Term Memory, LSTM)

• 整体示意图如下:
• 核心是”(Gate)门”结构
  • 其中Sigmoid是输出0到1的数值，描述每个部分有多少量可以通过当前门
  • 0表示拒绝所有，1表示接受所有
• 多个门和状态共同作用，使LSTM能够有效捕捉长期依赖关系并避免梯度消失问题：
  • 细胞状态 \( C_t \)部分 ：长期记忆，传递历史信息
  • 隐藏状态 \( h_t \)部分 ：短期记忆，当前时间步的输出
  • 输入门 \( i_t \)部分 ：控制新信息的加入
  • 遗忘门 \( f_t \)部分 ：控制历史信息的保留
  • 输出门 \( o_t \)部分 ：控制细胞状态对隐藏状态的影响
  • 候选细胞状态 \( \tilde{C}_t \)部分 ：当前时间步的候选更新值

遗忘门（Forget Gate，\( f_t \) ）

• 作用 ：控制前一个细胞状态 \( C_{t-1} \) 的遗忘程度：\(f_t = \sigma(W_f \cdot [h_{t-1}, x_t] + b_f)\)，输出在0到1之间，决定保留或丢弃多少历史信息

输入门（Input Gate，\( i_t \)）和 候选细胞状态（Candidate Cell State，\( \tilde{C}_t \)）

• 输入门作用 ：控制当前输入信息对细胞状态的更新程度, \(i_t = \sigma(W_i \cdot [h_{t-1}, x_t] + b_i)\)，输入门的输出在0到1之间，决定哪些新信息需要加入细胞状态
• 候选细胞状态作用 ：表示当前时间步的候选更新值， \(\tilde{C}_t = \tanh(W_C \cdot [h_{t-1}, x_t] + b_C)\)，用于更新细胞状态，候选细胞状态是当前输入和前一隐藏状态的非线性组合

细胞状态（Cell State, \( C_t \) ）

• 细胞状态 \( C_t \) 作用 ：细胞状态是LSTM的核心，负责长期记忆的传递。\(C_t = f_t \cdot C_{t-1} + i_t \cdot \tilde{C}_t\)，它像一个“传送带”，能够在时间步之间传递信息，并通过门控机制（遗忘门控制历史信息的保留，输入门控制新信息的加入）决定保留或丢弃哪些信息，细胞状态的变化相对平缓，能够捕捉长期依赖关系，通过遗忘门和输入门更新：

输出门（Output Gate，\( o_t \)）和 隐藏状态（Hidden State，\( h_t \)）

• 输出门 \( o_t \) 作用 ：控制细胞状态对当前隐藏状态的影响程度，\(o_t = \sigma(W_o \cdot [h_{t-1}, x_t] + b_o)\)，输出门的输出在0到1之间，决定细胞状态如何影响当前隐藏状态
• 隐藏状态 \( h_t \) 作用 ：隐藏状态是LSTM的短期记忆，表示当前时间步的输出，\(h_t = o_t \cdot \tanh(C_t)\)，它基于细胞状态和当前输入生成（输出门控制细胞状态对当前隐藏状态的影响，生成当前时间步的输出），并传递到下一个时间步，隐藏状态是LSTM对外的输出（即 output_t），它既用于当前时间步的输出，也用于下一个时间步的计算
• 特别说明 ：LSTM中的第 \(t\) 步的输出不是 \(o_t\)（\(o_t\)是输出门，而不是输出）, LSTM的通用输出就是 \(h_t\) 本身，但具体将LSTM应用到不同场景中时，可以接入不同的层来将 \(h_t\) 解码/转换为真实的输出 \(output_t = TransLayer(h_t)\)
• 补充问题 ：在文本翻译中，解码阶段，是否LSTM的 \(h_{t-1}\) 和 \(x_t\) 相等？一般不相等，因为解码时有:
  $$x_t = Embedding(output_{t-1}) = Embedding(TransLayer(h_{t-1}))$$
  • 比如在文本翻译中 \(h_{t-1}\) 是一个向量，而 \(output_{t-1}\) 是一个具体的 token，而上述公式中的 \(x_t \) 则一般是输入 \(input_t\)（\(= output_{t-1}\)） 经过 Embedding 后的向量

LSTM简单代码实现

• LSTM的PyTorch实现Demo：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

  # 定义 LSTM 单元 class LSTMCell(nn.Module): def __init__(self, input_size, hidden_size): super(LSTMCell, self).__init__() self.input_size = input_size self.hidden_size = hidden_size # 定义门参数 self.W_i = nn.Linear(input_size + hidden_size, hidden_size) # 输入门参数 self.W_f = nn.Linear(input_size + hidden_size, hidden_size) # 遗忘门参数 self.W_c = nn.Linear(input_size + hidden_size, hidden_size) # 候选记忆单元参数 self.W_o = nn.Linear(input_size + hidden_size, hidden_size) # 输出门参数 def forward(self, x, h_prev, c_prev): combined = torch.cat((x, h_prev), dim=1) i = torch.sigmoid(self.W_i(combined)) f = torch.sigmoid(self.W_f(combined)) c_tilde = torch.tanh(self.W_c(combined)) o = torch.sigmoid(self.W_o(combined)) c_next = f * c_prev + i * c_tilde h_next = o * torch.tanh(c_next) return h_next, c_next

GRU

门控循环单元(Gated Recurrent Unit, GRU)

• 整体示意图及推导如下:

  

• 特别说明 ：上述公式中，没有明确包含输出 \(output_t\)，GRU中的第 \(t\) 步的通用输出和LSTM一致，就是 \(h_t\) 本身，但具体将GRU应用到不同场景中时，可以接入不同的层来将 \(h_t\) 解码/转换为真实的输出 \(output_t = TransLayer(h_t)\)

GRU简单代码实现

• GRU的PyTorch实现Demo：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

  # 定义 GRU 单元 class GRUCell(nn.Module): def __init__(self, input_size, hidden_size): super(GRUCell, self).__init__() self.input_size = input_size self.hidden_size = hidden_size # 定义门参数 self.W_z = nn.Linear(input_size + hidden_size, hidden_size) self.W_r = nn.Linear(input_size + hidden_size, hidden_size) self.W_h = nn.Linear(input_size + hidden_size, hidden_size) def forward(self, x, h_prev): combined = torch.cat((x, h_prev), dim=1) z = torch.sigmoid(self.W_z(combined)) r = torch.sigmoid(self.W_r(combined)) h_tilde = torch.tanh(self.W_h(torch.cat((x, r * h_prev), dim=1))) h_next = (1 - z) * h_prev + z * h_tilde return h_next

GRU与LSTM对比

• 二者提出的时间基本相同
• 都是用来解决RNN不能处理长期依赖的问题
• LSTM有三个”门”结构， GRU只有两个”门结构”
• GRU较简单，参数比较少，不容易过拟合，LSTM 比较复杂一点，但是常用

附录：一个基于nn.LSTM的Decoder-Encoder翻译模型实现

• 一个基于nn.LSTM的Decoder-Encoder翻译实现示例：

  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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129

  import torch import torch.nn as nn import torch.optim as optim # 编码器 class Encoder(nn.Module): def __init__(self, input_size, hidden_size): super(Encoder, self).__init__() self.hidden_size = hidden_size self.embedding = nn.Embedding(input_size, hidden_size) self.lstm = nn.LSTM(hidden_size, hidden_size) def forward(self, input, hidden): embedded = self.embedding(input).view(1, 1, -1) output = embedded output, hidden = self.lstm(output, hidden) return output, hidden def initHidden(self): return (torch.zeros(1, 1, self.hidden_size), torch.zeros(1, 1, self.hidden_size)) # 解码器 class Decoder(nn.Module): def __init__(self, hidden_size, output_size): super(Decoder, self).__init__() self.hidden_size = hidden_size self.embedding = nn.Embedding(output_size, hidden_size) self.lstm = nn.LSTM(hidden_size, hidden_size) self.out = nn.Linear(hidden_size, output_size) self.softmax = nn.LogSoftmax(dim=1) def forward(self, input, hidden): output = self.embedding(input).view(1, 1, -1) output = torch.relu(output) output, hidden = self.lstm(output, hidden) output = self.softmax(self.out(output[0])) return output, hidden def initHidden(self): return (torch.zeros(1, 1, self.hidden_size), torch.zeros(1, 1, self.hidden_size)) # 数据集 source_vocab = {'hello': 0, 'world': 1, '!': 2} target_vocab = {'你好': 0, '世界': 1, '！': 2, '<EOS>': 3} input_size = len(source_vocab) output_size = len(target_vocab) hidden_size = 256 encoder = Encoder(input_size, hidden_size) decoder = Decoder(hidden_size, output_size) # 合并编码器和解码器的参数 params = list(encoder.parameters()) + list(decoder.parameters()) # 创建一个优化器来更新所有参数 optimizer = optim.SGD(params, lr=0.01) criterion = nn.NLLLoss() # 训练数据 train_data = [ (["hello", "world", "!"], ["你好", "世界", "！", "<EOS>"]) ] # 训练 for epoch in range(100): total_loss = 0 for src, tgt in train_data: input_tensor = torch.tensor([source_vocab[word] for word in src]) target_tensor = torch.tensor([target_vocab[word] for word in tgt]) optimizer.zero_grad() encoder_hidden = encoder.initHidden() for ei in range(len(input_tensor)): encoder_output, encoder_hidden = encoder(input_tensor[ei].unsqueeze(0), encoder_hidden) decoder_input = torch.tensor([[0]]) decoder_hidden = encoder_hidden loss = 0 for di in range(len(target_tensor)): decoder_output, decoder_hidden = decoder(decoder_input, decoder_hidden) topv, topi = decoder_output.topk(1) decoder_input = topi.squeeze().detach() loss += criterion(decoder_output, target_tensor[di].unsqueeze(0)) loss.backward() optimizer.step() total_loss += loss.item() if (epoch + 1) % 10 == 0: print(f'Epoch {epoch + 1}, Loss: {total_loss / len(train_data)}') # 评估 reverse_target_vocab = {idx: word for word, idx in target_vocab.items()} for src, _ in train_data: input_tensor = torch.tensor([source_vocab[word] for word in src]) encoder_hidden = encoder.initHidden() for ei in range(len(input_tensor)): encoder_output, encoder_hidden = encoder(input_tensor[ei].unsqueeze(0), encoder_hidden) decoder_input = torch.tensor([[0]]) decoder_hidden = encoder_hidden decoded_words = [] for di in range(10): decoder_output, decoder_hidden = decoder(decoder_input, decoder_hidden) topv, topi = decoder_output.topk(1) # topk(1)函数在默认维度（最后一维）上抽取最大的1个数字，并返回其在这个维度上的index decoded_word = reverse_target_vocab[topi.item()] decoded_words.append(decoded_word) if decoded_word == '<EOS>': break decoder_input = topi.squeeze().detach() print(f'Input: {" ".join(src)}, Translation: {" ".join(decoded_words)}') # Epoch 10, Loss: 4.957141399383545 # Epoch 20, Loss: 4.250643253326416 # Epoch 30, Loss: 3.5705487728118896 # Epoch 40, Loss: 2.95521879196167 # Epoch 50, Loss: 2.438739538192749 # Epoch 60, Loss: 2.025095224380493 # Epoch 70, Loss: 1.698549509048462 # Epoch 80, Loss: 1.438602328300476 # Epoch 90, Loss: 1.2278329133987427 # Epoch 100, Loss: 1.0538270473480225 # Input: hello world !, Translation: 你好 世界 ！ <EOS>

附录：一个基于 nn.GRU 的 Decoder-Encoder 翻译模型实现

• 一个基于 nn.GRU 的 Decoder-Encoder 翻译实现示例：

  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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127

  import torch import torch.nn as nn import torch.optim as optim # 编码器 class Encoder(nn.Module): def __init__(self, input_size, hidden_size): super(Encoder, self).__init__() self.hidden_size = hidden_size self.embedding = nn.Embedding(input_size, hidden_size) self.gru = nn.GRU(hidden_size, hidden_size) def forward(self, input, hidden): embedded = self.embedding(input).view(1, 1, -1) output = embedded output, hidden = self.gru(output, hidden) return output, hidden def initHidden(self): return torch.zeros(1, 1, self.hidden_size) # 解码器 class Decoder(nn.Module): def __init__(self, hidden_size, output_size): super(Decoder, self).__init__() self.hidden_size = hidden_size self.embedding = nn.Embedding(output_size, hidden_size) self.gru = nn.GRU(hidden_size, hidden_size) self.out = nn.Linear(hidden_size, output_size) self.softmax = nn.LogSoftmax(dim=1) def forward(self, input, hidden): output = self.embedding(input).view(1, 1, -1) output = torch.relu(output) output, hidden = self.gru(output, hidden) output = self.softmax(self.out(output[0])) return output, hidden def initHidden(self): return torch.zeros(1, 1, self.hidden_size) # 这里LSTM是2个隐向量 # 数据集 source_vocab = {'hello': 0, 'world': 1, '!': 2} target_vocab = {'你好': 0, '世界': 1, '！': 2, '<EOS>': 3} input_size = len(source_vocab) output_size = len(target_vocab) hidden_size = 256 encoder = Encoder(input_size, hidden_size) decoder = Decoder(hidden_size, output_size) # 合并编码器和解码器的参数 params = list(encoder.parameters()) + list(decoder.parameters()) # 创建一个优化器来更新所有参数 optimizer = optim.SGD(params, lr=0.01) criterion = nn.NLLLoss() # 训练数据 train_data = [ (["hello", "world", "!"], ["你好", "世界", "！", "<EOS>"]) ] # 训练 for epoch in range(100): total_loss = 0 for src, tgt in train_data: input_tensor = torch.tensor([source_vocab[word] for word in src]) target_tensor = torch.tensor([target_vocab[word] for word in tgt]) optimizer.zero_grad() encoder_hidden = encoder.initHidden() for ei in range(len(input_tensor)): encoder_output, encoder_hidden = encoder(input_tensor[ei].unsqueeze(0), encoder_hidden) decoder_input = torch.tensor([[0]]) decoder_hidden = encoder_hidden loss = 0 for di in range(len(target_tensor)): decoder_output, decoder_hidden = decoder(decoder_input, decoder_hidden) topv, topi = decoder_output.topk(1) decoder_input = topi.squeeze().detach() loss += criterion(decoder_output, target_tensor[di].unsqueeze(0)) loss.backward() optimizer.step() total_loss += loss.item() if (epoch + 1) % 10 == 0: print(f'Epoch {epoch + 1}, Loss: {total_loss / len(train_data)}') # 评估 reverse_target_vocab = {idx: word for word, idx in target_vocab.items()} for src, _ in train_data: input_tensor = torch.tensor([source_vocab[word] for word in src]) encoder_hidden = encoder.initHidden() for ei in range(len(input_tensor)): encoder_output, encoder_hidden = encoder(input_tensor[ei].unsqueeze(0), encoder_hidden) decoder_input = torch.tensor([[0]]) decoder_hidden = encoder_hidden decoded_words = [] for di in range(10): decoder_output, decoder_hidden = decoder(decoder_input, decoder_hidden) topv, topi = decoder_output.topk(1) # topk(1)函数在默认维度（最后一维）上抽取最大的1个数字，并返回其在这个维度上的index decoded_word = reverse_target_vocab[topi.item()] decoded_words.append(decoded_word) if decoded_word == '<EOS>': break decoder_input = topi.squeeze().detach() print(f'Input: {" ".join(src)}, Translation: {" ".join(decoded_words)}') # Epoch 10, Loss: 4.1139960289001465 # Epoch 20, Loss: 2.4189529418945312 # Epoch 30, Loss: 1.5635995864868164 # Epoch 40, Loss: 1.0992240905761719 # Epoch 50, Loss: 0.8163852691650391 # Epoch 60, Loss: 0.6290442943572998 # Epoch 70, Loss: 0.49852463603019714 # Epoch 80, Loss: 0.4044916033744812 # Epoch 90, Loss: 0.3349364101886749 # Epoch 100, Loss: 0.2822900116443634 # Input: hello world !, Translation: 你好 世界 ！ <EOS>

• 与LSTM实现的主要区别是，output, hidden = self.gru(output, hidden) 中输入和输出的 hiden 的数量不同，LSTM 包含两个向量（\(C_t\) 和 \(h_t\)），而 GRU 只包含一个 \(h_t\)

本文不定期更新

模型的一般使用流程

• init
• fit(x_train, y_train)
• predict(x_test)

模型输出预测概率

• 方法名称: predict_proba(x_test)
• 该方法对于预测时使用概率或者分数的算法来说直接返回概率值,对于不能返回概率的类来说一般返回交叉验证结果的平均值等
  • NB: 概率值
  • LR: 逻辑回归的分数
  • SVM: 交叉验证生成的平均值, 这里的结果与predict预测结果可能有偏差

关于参数

• 待补充

为DataFrame的某一列实行OneHot编码

使用OneHotEncoder进行编码

• 基本实现思路:

  • 生成一个OneHotEncoder对象
  • 取出对应的列并处理成N*1维的数组,用其训练OneHotEncoder对象并进行编码转换
  • 将新编码的数据生成为新的DataFrame对象
    • 为新的编码每一列生成新的列名称
    • 为新的每行索引赋值为原始DataFrame对应的索引
  • 按照列合并两个DataFrame
  • 删除之前的列

• 实现代码:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

  from sklearn.preprocessing import OneHotEncoder def one_hot_for_column(df, column): """ encode column of df with one hot method :param df: an object of DataFrame :param column: the name of column in df :return: new object of DataFrame and object of OneHotEncoder """ ohe = OneHotEncoder() # ohe.fit(df[column].values.reshape(-1, 1)) # col_series = ohe.transform(df[column].values.reshape(-1, 1)).toarray() # <==> col_series = ohe.fit_transform(df[column].values.reshape(-1, 1)).toarray() columns = ["%s_%s" % (column, str(m)) for m in range(1, col_series.shape[1] + 1)] sub_df = pd.DataFrame(col_series, columns=columns, dtype=int, index=df.index) new_df = pd.concat([df, sub_df], axis=1) new_df.drop(columns=column, inplace=True) return new_df, ohe