提升鲁棒性的随机算法

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

为何引入随机性？

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

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

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

自举法与集成方法

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

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

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

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

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

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

神经网络 (neural network)中的Dropout

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

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

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

优化中的随机性

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

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

可重现性与控制

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

这通过设置算法使用的伪随机数生成器（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)}")

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

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