5

我正在为 Python 中的 mnist 数据实现 SVM，现在我正在使用 cvxopt 来解决 QP 并获取 alpha。

但我的问题是计算 K-gram 矩阵 ** 有效 **，我只从两个类（数字 6 和 0）开始，训练示例的数量少于前 1k，接下来是 10K。

为了更快地计算整个 1k x 1k 矩阵，我正在使用 Process，并提供不同的原始数据进行计算。但它仍然需要 2 分钟 - 它的 rbf - 高斯。（10k 一个仍在运行！）

如果有人研究它或者可能是 Python 爱好者可以在这里帮助我，那就太好了！

PS：如果有人不知道计算 gram-matrix，这里是详细信息：它很简单：

for i in range(1k):
    for j in range(1k):
         for K[i,j] = some_fun(x[i], x[j])

其中 some_fun - 是点积或花式高斯。

我正在使用 python 2.7、numpy 和 Mac Air 4G RAM，128G 固态。

[编辑] 如果有人来过这里！是的，SVM 确实需要更长的时间......如果你正在进行多分类，那么你必须再次计算 k-gram 矩阵......所以它会花费很长时间，所以我建议实施算法并检查它两次并让它运行一夜！但你肯定会在第二天看到好结果！:)

4

1 回答 1

6

你用的是numpy，对吧？您应该通过使用 numpy 的矩阵运算一次计算整个矩阵来获得很大的加速，而不是使用缓慢的 Python 循环来查找每个成对评估。例如，如果我们假设它x是一个行实例数据矩阵（每个数据点一行，每个维度一列）：

# get a matrix where the (i, j)th element is |x[i] - x[j]|^2
# using the identity (x - y)^T (x - y) = x^T x + y^T y - 2 x^T y
pt_sq_norms = (x ** 2).sum(axis=1)
dists_sq = np.dot(x, x.T)
dists_sq *= -2
dists_sq += pt_sq_norms.reshape(-1, 1)
dists_sq += pt_sq_norms

# turn into an RBF gram matrix
km = dists_sq; del dists_sq
km /= -2 * sigma**2
np.exp(km, km)  # exponentiates in-place

生成数据np.random.normal(size=(1000, 784))，这在我的四核 i5 iMac 上需要 70 毫秒。将其增加到 10k 个数据点，只需不到 7 秒。

sklearn.metrics.pairwise.rbf_kernel 的工作方式类似，但它有一些额外的输入检查和对稀疏矩阵等的支持。

还值得注意的是，在 python 2 中，你应该循环xrange(1000)，而不是range(1000). range实际上会构造一个要循环的列表对象，这会占用一些时间，也许更重要的是内存。对于 10,000，您可能没问题，但是如果您的循环太大，这可能会导致严重的问题。

于 2013-04-01T17:06:27.007 回答