基于向量运算的随机梯度下降？

数据挖掘 Python 梯度下降 回归
2021-09-22 06:55:12

假设我想使用具有 N 个样本的数据集训练随机梯度下降回归算法。由于数据集的大小是固定的，我将重复使用数据 T 次。在每次迭代或“epoch”中，我在对整个训练集进行随机重新排序后，只使用每个训练样本一次。

我的实现基于 Python 和 Numpy。因此，使用向量运算可以显着减少计算时间。提出批量梯度下降的矢量化实现非常简单。但是，在随机梯度下降的情况下，我无法弄清楚如何避免在每个时期遍历所有样本的外循环。

有人知道随机梯度下降的任何矢量化实现吗？

编辑：有人问我，如果我的数据集的大小是固定的，我为什么要使用在线梯度下降。

从 [1] 可以看出，在线梯度下降比批量梯度下降收敛到最小的经验成本要慢。然而，它更快地收敛到预期成本的最小值，这衡量了泛化性能。我想通过交叉验证来测试这些理论结果对我的特定问题的影响。如果没有矢量化实现，我的在线梯度下降代码比批量梯度下降代码要慢得多。这显着增加了完成交叉验证过程所需的时间。

编辑：我在这里包括我的在线梯度下降实现的伪代码，应 ffriend 的要求。我正在解决回归问题。

Method: on-line gradient descent (regression)
Input: X (nxp matrix; each line contains a training sample, represented as a length-p vector), Y (length-n vector; output of the training samples)
Output: A (length-p+1 vector of coefficients)

Initialize coefficients (assign value 0 to all coefficients)
Calculate outputs F
prev_error = inf
error = sum((F-Y)^2)/n
it = 0
while abs(error - prev_error)>ERROR_THRESHOLD and it<=MAX_ITERATIONS:
    Randomly shuffle training samples
    for each training sample i:
        Compute error for training sample i
        Update coefficients based on the error above
    prev_error = error
    Calculate outputs F
    error = sum((F-Y)^2)/n
    it = it + 1

[1] “大规模在线学习”，L. Bottou，Y. Le Cunn，NIPS 2003。

2个回答

首先，“样本”一词通常用于描述总体的子集，所以我将指代与“示例”相同的东西。

由于这条线，您的 SGD 实现很慢：

for each training example i:

在这里，您明确地为模型参数的每次更新使用了一个示例。根据定义，向量化是一种将对一个元素的操作转换为对这些元素的向量的操作的技术。因此，不，您不能一个接一个地处理示例并仍然使用矢量化。

但是，您可以使用mini-batches来近似真实的 SGD 。小批量是原始数据集的一小部分（例如 100 个示例）。您基于小批量计算错误和参数更新，但您仍然在没有全局优化的情况下迭代其中的许多，从而使过程随机化。因此，为了使您的实现更快，只需将上一行更改为：

batches = split dataset into mini-batches
for batch in batches:

并从批处理中计算错误，而不是从单个示例中计算。

虽然很明显，但我还应该提到每个示例级别的矢量化。也就是说，而不是这样的：

theta = np.array([...])  # parameter vector
x = np.array([...])      # example
y = 0                    # predicted response
for i in range(len(example)):
    y += x[i] * theta[i]
error = (true_y - y) ** 2  # true_y - true value of response

你绝对应该做这样的事情：

error = (true_y - sum(np.dot(x, theta))) ** 2

同样，对于小批量，这很容易概括：

true_y = np.array([...])     # vector of response values
X = np.array([[...], [...]]) # mini-batch
errors = true_y - sum(np.dot(X, theta), 1)
error = sum(e ** 2 for e in errors)

查看scikit 的 SGD 分类器的 partial_fit 方法。您可以控制使用它调用的内容：您可以通过一次传递一个实例来进行“真正的”在线学习，或者如果您的所有数据都在数组中可用，您可以将实例分批成小批量。如果是，您可以对数组进行切片以提供小批量。

其它你可能感兴趣的问题
上一篇哪个更快：大型 JSON 数据集上的 PostgreSQL 与 MongoDB？ 下一篇基于神经网络的外汇市场预测