Metric-space Positioning Systems (MPS) for Machine Learning
Richard C. Tillquist, Manuel E. Lladser · 2016
Many machine learning techniques such as k-nearest neighbors (KNNs) and support vector machines (SVMs) require examples to be mapped to numerical feature vectors. Principal coordinate analysis (PCoA) accomplishes this by mapping a set of n examples to n points in Rn-1. However, learning from these high-dimensional vectors may require an astronomically large number of examples. Here we present an intuitive, novel method for uniquely representing sequences of symbolic features with the fewest dimensions via "multi-lateration" (i.e. the selection of a minimal feature set that uniquely distinguishes all examples under a reference metric). We show that the problem of determining a minimal multilateration set is NP-complete in general, and present a randomized algorithm for finding close to optimal subsets. As proof of concept, we apply multilateration to learn 12-mers centered at intron-exon boundaries using human annotated examples. We compare results using features derived in several different ways and an array of machine learning techniques, some of which can handle symbolic features directly and some of which cannot. Our experiments indicate that multilateration improves performance of non-symbolic classification techniques without significantly altering performance using other techniques.