It is well-known in functional analysis that an inner product always induces a norm and a norm always induces a metric, and the reverse directions do not hold in general. I am wondering if a similar claim can be made about learning from features vs. from a metric (say, via a nearest-neighbor classifier).

For example, realizable SVM is a feature-based algorithm, but can be interpreted in the language of metrics as follows. Take the sample and construct the convex hulls of the positive and negative parts of the sample (either in explicit feature space or in the reproducing kernel Hilbert space). Then we can classify test points by their closest distance to either convex hull.

On the other hand, consider the edit distance over strings. One can certainly do supervised learning via nearest-neighbor methods, but feature-based learning runs into a problem: the edit distance only embeds into Hilber or $\ell_p$ spaces with a large distortion, potentially corrupting the data geometry before the learning process has even begun. (https://dl.acm.org/citation.cfm?id=1958047)

Has anyone ever tried to formalize this line of reasoning?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.