Non-numeric Values

Question 1

How can we convert non-numeric data types?

Answer 1

We can use a feature mapping to devise an appropriate feature embedding and compute its kernel or an appropriate similarity function and use its kernel. The similarity function needs to correspond to an inner product in some embedding.

Question 2

What kernel can we use for sets?

Answer 2

We can use the similarity function k(A1, A2) = 2 ^ |A1 n A2|

Question 3

What can we use for strings?

Answer 3

For strings, we consider an infinite embedding ϕ(s) where each dimension corresponds to a string s’ in the set of all possible strings A*. We could only considering terms that appear in s and t and up to size min(|s|,|t|) but time complexity is still exponential.

k(s, t) = ϕ(s)Tϕ(t) = ∞Σi=1 ϕi(s)ϕi(t)

Question 4

What can we use for trees? (also works for graphs)

Answer 4

Compare the similarities of common subtrees in two trees.

k(T1, T2) = ϕ(T1)Tϕ(T2) = Σ S∈𝒯 ϕS(T1)ϕS(T2)