我无法理解为什么计算核函数K(x,z)只需要线性时间，尽管它是在O(n^d)维空间中进行。请解释一下。我在机器学习方面是个新手。
回答：
为了计算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)的时间。
特征空间的维度远高于计算核函数所需的时间是完全正常的：否则我们一开始就不需要核函数，因为我们可以直接计算特征向量。
如果你想要一个更极端的例子，可以看看在非负实数x, y上的K(x, y) = min(x, y)。评估min(x, y)只需要常数时间。然而，特征空间是L^2(R)（实线上平方可积函数，带有标准的希尔伯特空间标量乘积），特征映射是phi(x) = chi_{[0, x]}，其中chi_{[0, x]}表示区间[0, x]的特征函数。因此，特征空间是无限维的，但评估核函数所需的时间是常数。
