机器学习数学基础 120 章

排列组合与古典概型

层级：B｜按需

1. 计数是有限概率的基础

若有限样本空间中基本结果等可能：

P(A)=∣A∣∣Ω∣.P(A)=\frac{|A|}{|\Omega|}.

关键就变成正确计数。必须先判断：是否考虑顺序、是否允许重复、对象是否可区分。

2. 加法原理与乘法原理

若完成任务有互斥的两类方式，分别 m,nm,n 种，共 m+nm+n 种。

若任务分两步，第一步 mm 种，每种情况下第二步 nn 种，共 mnmn 种。更一般地，多阶段选择数相乘。

例如 3 种模型、4 组学习率的网格有 3×4=123\times4=12 个组合。

3. 排列

nn 个不同对象全部排序：

n!=n(n−1)⋯1.n!=n(n-1)\cdots1.

从 nn 个中有序选 kk 个：

P(n,k)=n!(n−k)!.P(n,k)=\frac{n!}{(n-k)!}.

例：10 个候选中选冠亚季军，有 10×9×8=72010\times9\times8=720 种。

4. 组合

从 nn 个不同对象中无序选 kk 个：

(nk)=n!k!(n−k)!.\binom nk=\frac{n!}{k!(n-k)!}.

因为每个无序集合被 k!k! 种内部排列重复计算。

对称性：

(nk)=(nn−k),\binom nk=\binom n{n-k},

选择 kk 个保留等价于选择 n−kn-k 个删除。

5. 有重复的序列

长度 kk，每个位置可从 nn 个对象独立选，允许重复：

nk.n^k.

如 KK 类标签的 nn 个样本所有可能标注有 KnK^n 种。这种指数增长解释了假设空间为何巨大。

6. 多项式计数

nn 个位置中，类别计数为 n1,ldots,nKn_1,ldots,n_K，和为 nn，不同排列数：

(nn1,ldots,nK)=n!n1!⋯nK!.\binom{n}{n_1,ldots,n_K} =\frac{n!}{n_1!\cdots n_K!}.

它是多项分布概率中的组合因子，表示同一计数组合对应多少标签序列。

7. 有重复组合

从 nn 类对象中选 kk 个，允许重复且不计顺序，数量为

(n+k−1k).\binom{n+k-1}{k}.

“隔板法”把 kk 个相同球分到 nn 个盒子，用 n−1n-1 个隔板编码。这个公式不是常用主线，但能帮助识别重复与无序同时出现的情形。

8. 古典概型的使用条件

只有基本结果等可能时才能用

P(A)=∣A∣/∣Ω∣.P(A)=|A|/|\Omega|.

两枚硬币若偏置或相关，四个序列不等可能；抽样过程若带权，也不能只计数。

“随机选择”要明确机制。数据库 ORDER BY random() LIMIT k、每个用户先均匀再抽记录、直接从所有记录均匀抽样，产生不同样本分布。

9. 有放回与无放回

从 NN 个对象抽 nn 个：

  • 有放回：每次总体不变，独立（若均匀抽）；
  • 无放回：后续概率依赖前面结果，样本不独立。

无放回抽到某类别数量服从超几何分布；有放回独立抽则对应二项分布。

10. 生日问题

nn 人生日在 365 天均匀独立。无重复概率：

P(all distinct)=365⋅364⋯(365−n+1)365n.P(\text{all distinct}) =\frac{365\cdot364\cdots(365-n+1)}{365^n}.

至少重复：

1−P(all distinct).1-P(\text{all distinct}).

用补事件比直接计数各种重复模式简单。这一技巧在故障概率、碰撞与哈希分析中常用。

11. 二项式定理

(a+b)n=∑k=0n(nk)akbn−k.(a+b)^n =\sum_{k=0}^{n}\binom nk a^kb^{n-k}.

令 a=p,b=1−pa=p,b=1-p：

∑k=0n(nk)pk(1−p)n−k=1,\sum_{k=0}^{n}\binom nkp^k(1-p)^{n-k}=1,

正是二项分布概率总和为 1。

12. 组合爆炸与机器学习

  • dd 个特征的所有子集有 2d2^d 个；
  • 决策树结构数量巨大；
  • 最优 L0 特征选择通常是组合难题；
  • 所有标签赋值有 KnK^n 个；
  • 网格搜索随超参数维度指数增长。

这解释了为何使用贪心、动态规划、凸松弛、随机搜索和启发式算法。

易错点

  1. 等可能是古典概率的前提。
  2. 组合不计顺序，排列计顺序。
  3. 有放回通常独立，无放回通常不独立。
  4. “至少一个”常用补事件更易算。
  5. 大阶乘直接计算会溢出，应使用对数 Gamma 或稳定递推。

常见问答

Q1：训练/测试随机切分是有放回还是无放回？

通常是无放回划分，每个样本只进入一个集合；但同一用户/群组记录仍可能跨集合造成依赖泄漏。

Q2：为什么随机搜索常优于相同预算网格搜索？

若只有少数超参数真正重要，网格会在不重要维度重复相同重要坐标值；随机搜索能覆盖更多不同的重要坐标取值。

Q3：类别不平衡下 accuracy 的随机基线怎样算？

取决于预测机制。总预测多数类准确率等于多数类比例；按真实先验随机独立预测，期望准确率为各类先验平方和。

练习

  1. 8 个特征选 3 个，有多少子集？
  2. 若还考虑选择顺序，有多少？
  3. 5 位密码每位 10 个数字、允许重复，有多少种？
  4. 10 个样本的所有特征子集有多少个？（把“特征”改为 10 个对象）
  5. 解释为什么无放回抽样不独立。

答案与提示

  1. (83)=56\binom83=56。
  2. 8×7×6=3368\times7\times6=336。
  3. 10510^5。
  4. 210=10242^{10}=1024。
  5. 抽到某对象/类别会改变剩余总体组成，从而改变下一次概率。