Problem: Transforming X into φ(X)
space can be expensive, and it is usually used as an intermediate result inside of a dot product like <φ(x[i]), φ(x[j])>
.
Trick to save computation time: Conditional on having a φ
where we know how to compute <φ(x[i]), φ(x[j])>
through a shortcut, we can use the shortcut instead of explicitly calling φ
and storing the long intermediate result. The savings stem from (a) saving calls to φ
, and (b) making the dot product operate on shorter vectors.
φ(x) = (x[1]**2, sqrt(2)*x[1]* x[2], x[2]**2)
<φ(x),φ(z)> = sum((x[1]**2)(z[1]**2), 2x[1]x[2]z[1]z[2], (x[2]**2)(z[2]**2))