提升鲁棒性的随机算法

虽然确定性算法在相同输入下遵循可预测的执行路径，但随机算法在其逻辑中引入了随机因素。这对于要求精确的任务可能反直觉，但在机器学习中引入随机性是一种有效的方法，常用于提升鲁棒性、跳出局部最优、提高泛化能力以及更高效地处理大规模问题。这些算法通常不保证每次都得到完全相同的结果，但能以高概率提供正确或最优的结果，或者它们通过随机性更有效地搜索解空间。

为何引入随机性？

随机性不仅仅是不可预测性；它在机器学习算法中服务于特定的目的：

1. 提高泛化能力： 随机性可以作为一种正则化形式，防止模型在训练数据上过拟合。通过在训练过程中引入变化，模型对训练集中的特定模式的敏感度降低，并在未见过的数据上表现更好。
2. 打破对称性并避免最坏情况： 在某些算法中，确定性选择可能导致在特定输入上持续表现不佳（最坏情况行为）。随机化可以打破这些模式，使最坏情况的发生概率在实际应用中大大降低（例如，快速排序中的随机主元选择）。
3. 搜索： 随机性使得算法能够搜索解空间的不同部分，这在优化问题中可以帮助避免陷入较差的局部最优。
4. 效率： 对于海量数据集，纯粹的确定性方法可能计算上不可行。随机算法通常能更快地提供良好的近似解（例如，近似计数或查找最近邻）。

让我们看看随机化是如何应用在一些重要的机器学习技术中的。

自举法与集成方法

随机化在机器学习中的一个应用是自举法，此方法是Bagging（自举聚合）以及随机森林等集成模型的基础。

自举法通过有放回抽样从原始数据集中创建多个新数据集。每个新数据集与原始数据集大小相同，但由于是有放回抽样，原始数据集中的某些数据点可能会在自举样本中出现多次，而其他数据点可能根本不出现。

通过有放回抽样从原始数据集中创建多个自举样本。每个样本用于训练集成中的一个独立模型。

在随机森林中，这一过程更进了一步：

1. 数据随机化（自举法）： 创建多个自举样本。每个样本上训练一个独立的决策树。
2. 特征随机化： 在构建每个决策树时，在每个节点分裂处，仅考虑可用特征的随机子集来寻找最佳分裂。这进一步降低了各个树之间的相关性。

这两种随机源的结合使得随机森林能有效对抗过拟合，并且通常能产生高预测精度。最终预测通常是通过对森林中所有树的预测进行平均（用于回归）或进行多数投票（用于分类）来完成的。

神经网络中的Dropout

Dropout是一种专门为神经网络设计的正则化技术。在训练过程中，对于每个训练样本（或小批量），dropout会随机地“丢弃”（设置为零）某一层中一部分神经元的激活值。丢弃神经元的概率 $p$ 是一个超参数（通常约为0.5）。

应用Dropout的神经网络层在训练时的示意。在此训练步骤中，神经元N2和N4（右侧）被随机停用。

这种随机停用可防止神经元之间过度相互依赖。它迫使网络学习更多的冗余表示，使其对特定神经元的有无不那么敏感，并提高其对未见过数据的泛化能力。在测试时，通常会关闭dropout，并且激活值会被按比例缩小，以弥补比训练时更多神经元处于活跃状态的事实。

优化中的随机性

尽管像梯度下降这样的迭代优化方法在给定起点和数据集的情况下主要是确定性的，但**随机梯度下降（SGD）**变体引入了随机性。SGD不是使用整个数据集（这计算成本高昂）来计算梯度，而是在每次迭代时基于单个随机选择的数据点或一个小的随机子集（小批量）来计算梯度。

这种随机性为梯度更新增加了噪声。尽管这种噪声可能使收敛路径不如批量梯度下降平滑，但它有一个有益的副作用：它可以帮助优化过程跳出浅层局部最小值，并可能在损失空间中找到更好、更深的最小值。选择小批量固有的随机性使得SGD在实践中成为一种随机算法。

可重现性与控制

使用随机算法的一个结果是，在相同数据上两次运行同一算法可能会产生略微不同的结果（例如，模型权重略有不同，森林中的树不同）。对于开发、调试和比较实验，通常需要确保可重现性。

这通过设置算法使用的伪随机数生成器（PRNG）的种子来实现。NumPy、Scikit-learn、TensorFlow和PyTorch等库提供了设置随机种子的函数。将种子设置为特定的整数可确保每次运行代码时生成的“随机”数序列都相同，从而使随机算法的结果可重现。

import numpy as np
import sklearn.ensemble
import sklearn.model_selection

# 为NumPy的随机数生成器设置一个种子
np.random.seed(42)

# 使用np.random的操作现在将是确定性的
random_indices = np.random.choice(10, 5, replace=False)
print(f"使用种子42的随机索引: {random_indices}")

# 许多机器学习库使用NumPy的RNG或有自己的种子参数
# 随机森林分类器示例
# 设置'random_state'确保自举法和特征选择的可重现性
X = np.random.rand(100, 10)
y = np.random.randint(0, 2, 100)
X_train, X_test, y_train, y_test = sklearn.model_selection.train_test_split(
    X, y, test_size=0.3, random_state=42 # 分割的种子
)

model = sklearn.ensemble.RandomForestClassifier(n_estimators=10, random_state=42) # 森林的种子
model.fit(X_train, y_train)
print(f"模型得分: {model.score(X_test, y_test)}")

# 多次运行此代码将产生完全相同的输出。
# 更改种子（或不设置）将导致不同的结果。

总而言之，随机算法并非对正确性的妥协，而是机器学习中的一种策略性选择。它们通过随机性来构建模型，这些模型通常更有效、泛化能力更好，并且可以更高效地进行训练，尤其是在大型数据集上。自举法、dropout和SGD中的随机性等技术是构建有效的现代机器学习系统的基本工具。理解何时以及为何使用随机性有助于选择合适的算法并解释其行为。