machine-learning - SVM 内核的 O(n) 时间

Question

尽管在 O(n^d) 维空间中工作，但我无法理解计算内核 K(x,z) 仅需要线性时间。请解释一下。我是 ML 的新手。

Answer 1

为了计算K(x, z)，您必须：

• 执行O(n)乘法x1 * z1, x2 * x2, ..., xn * zn,
• 执行O(n)加法(x1 * z1) + (x2 * x2) + ... + (xn * zn)，
• 执行两个O(1)操作_ + c和_ ^ d。

因此，计算K(x, z) = (dot(x, z) + c)^d需要O(n)时间。

特征空间的维度比计算内核所需的时间高得多是完全正常的：否则我们一开始就不需要内核，因为我们可以直接计算特征向量。

如果您想要一个更极端的示例，请查看K(x, y) = min(x, y)非负实数x, y。评估需要恒定的时间min(x, y)。然而，特征空间是L^2(R)（实线上的平方可积函数，与标准希尔伯特空间标量积），特征映射是phi(x) = chi_{[0, x]}，其中chi_{[0, x]}表示区间 的特征函数[0, x]。因此，特征空间是无限维的，但评估内核所需的时间是恒定的。