题目重点：保存x/y配对，给每个基分类器不同bootstrap，定义多数平局并解释方差下降前提。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练基分类器已提供fit/predict，每个为独立实例，标签为整数；每模型抽N次有放回，输出平局取最小标签。
- 随机种子可注入复现，底层分类器不得修改调用方数据；框架原始tie规则缺失需确认。
解题路线
- bootstrap抽的是样本索引，同一索引同时选择x_train[i]与y_train[i]；分别采样x和y会破坏监督关系。抽N次但可能重复/遗漏原样本，不能改成无放回shuffle。
- 每个模型使用独立抽样轨迹并fit。多个数组位置若指向同一个模型对象，后续fit会覆盖之前状态，所以要验证独立实例或按框架clone。
- 每个模型对每个test点给类标，多数票统计标签次数，取最大；平票按固定规则，不能由set遍历顺序决定。若改用概率平均，那是另一聚合合同。
- 降方差取决于基学习器误差相关性：独立等方差均值方差σ²/M，有相关ρ时约σ²[ρ+(1−ρ)/M]；更多模型不能消除高相关误差，也不自动修正系统偏差。
- OOB样本可估泛化，因为每模型未抽到部分训练点；同一测试对象只用没训练过它的模型聚合，不能全部模型预测训练集再说无偏验证。正式业务还需独立验证和防数据泄漏。
- 训练是否并行取决于模型相互独立、资源和随机源隔离；boosting逐轮修正残差通常有顺序依赖，不与bagging混为同一种流程。
- 示例用记录采样的可控分类器验证每次索引配对与投票，避免只看随机准确率。fit/predict失败、长度错和空输入应有明确错误边界。
手动走一遍
索引抽[2,2,0]时x和y都按这三个位置选，原样本1未参与此模型。五模型对某test投[1,2,2,1,2]得2；四模型[1,2,1,2]按本合同取1。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import Counter
import random
def bagging_predict(x_train, y_train, x_test, classifiers, rng=None):
if not x_train or len(x_train) != len(y_train) or not classifiers:
raise ValueError('nonempty matching training data and classifiers required')
if len({id(model) for model in classifiers}) != len(classifiers):
raise ValueError('each estimator must be a distinct instance')
rng = rng or random.Random()
predictions = []
n = len(x_train)
for model in classifiers:
indices = [rng.randrange(n) for _ in range(n)]
model.fit([x_train[i] for i in indices], [y_train[i] for i in indices])
result = list(model.predict(x_test))
if len(result) != len(x_test) or any(type(label) is not int for label in result):
raise ValueError('estimator must return one integer label per test row')
predictions.append(result)
answer = []
for i in range(len(x_test)):
counts = Counter(p[i] for p in predictions)
answer.append(min(counts, key=lambda label: (-counts[label], label)))
return answer
复杂度
M模型bootstrap O(MN)，训练M·Tfit(N)，预测M·Tpredict(Q)，投票O(MQ)；本实现存各模型预测O(MQ)，可流式累计降低额外峰值。采样临时O(N)，模型内存另计。
易错点与追问
容易失分的边界
- x/y分别抽样。
- 所有模型共享同实例。
- 无放回采样称bootstrap。
- 模型越多必然消除偏差。
继续深挖
- OOB如何保证未训练过样本？
- 概率平均和多数票怎样选？
- 模型相关性如何降低？
