O(n) время ядра SVM

Question

Я не могу понять, как вычислительное ядро, K(x,z) занимает только линейное время, несмотря на работу в O(n^d) мерном пространстве. Пожалуйста, объясните мне. Я новичок в 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], Таким образом, пространство признаков бесконечномерно, но время, необходимое для оценки ядра, является постоянным.