实现支持向量机 - 高效计算克矩阵K.

Question

我正在用Python实现mnist数据的SVM,现在我正在使用cvxopt来解决QP并恢复alpha.

但我的问题是计算K-gram矩阵**高效**,我开始只有两个类(数字6和0),训练样例的数量少于前1k,下一个10K.

为了更快地计算整个1k x 1k矩阵,我正在使用Process,并提供不同的原始计算.但它仍需要2分钟 - 它的rbf - 高斯.(10k还在运行!)

如果任何人都在努力或者可能是Python爱好者可以帮助我,这将是伟大的!

PS:如果有人不知道计算克数矩阵,这里有详细说明:它很简单:

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矩阵...所以它需要很长时间,所以我建议实现算法并检查它两次,让它运行一夜!但是你肯定会在第二天看到好结果!:)

Answer 1

你正在使用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上需要70ms.将它提升到10k数据点,只需不到7秒.

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

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