SVM Kernel 的 O(n) 时间
SVM Kernel's O(n) time
我无法理解尽管在 O(n^d) 维 space 中工作，但计算内核 K(x,z) 只需要线性时间。
请解释一下。我是ML的新手。
为了计算 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) 时间。
特征 space 的维度比计算内核所需的时间高得多是完全正常的：否则我们一开始就不需要内核，因为我们可以只计算特征直接向量。
如果您想要一个更极端的例子，请查看 K(x, y) = min(x, y) 非负实数 x, y。评估 min(x, y) 需要常数时间。但是，特征space是L^2(R)（实线上的平方可积函数，与标准的Hilbert-space标量积），特征映射是phi(x) = chi_{[0, x]}，其中chi_{[0, x]}表示区间[0, x]的特征函数。因此，特征 space 是无限维的，但计算内核所需的时间是常数。
我无法理解尽管在 O(n^d) 维 space 中工作，但计算内核 K(x,z) 只需要线性时间。
请解释一下。我是ML的新手。
为了计算 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) 时间。
特征 space 的维度比计算内核所需的时间高得多是完全正常的：否则我们一开始就不需要内核，因为我们可以只计算特征直接向量。
如果您想要一个更极端的例子，请查看 K(x, y) = min(x, y) 非负实数 x, y。评估 min(x, y) 需要常数时间。但是，特征space是L^2(R)（实线上的平方可积函数，与标准的Hilbert-space标量积），特征映射是phi(x) = chi_{[0, x]}，其中chi_{[0, x]}表示区间[0, x]的特征函数。因此，特征 space 是无限维的，但计算内核所需的时间是常数。