5:00PM: Tropical Support Vector Machines
Ruriko Yoshida
Most data in genome-wide phylogenetic analysis is essentially multidimensional, posing a major challenge to human comprehension and computational analysis. Also, we cannot directly apply statistical learning models in data science to a set of phylogenetic trees since tree space is not Euclidean. In fact, the space of phylogenetic trees is a tropical Grassmanian in the max-plus algebra. Therefore, to classify multi-locus data sets for phylogenetic analysis, we propose tropical Support Vector Machines (SVMs) over the space of phylogenetic trees. Like classical SVMs, a tropical SVM is a discriminative classifier defined by a tropical hyperplane which maximizes the minimum tropical distance from data points to itself to separate these data points into sectors. We show that, even though we have to solve exponentially many linear programming problems to find tropical SVMs, many instances are infeasible. Then we show the necessary and sufficient conditions for each instance to be feasible. In each case, there is an explicit formula for the optimal solution for the feasible linear programming problem. Based on our theorems, we develop novel methods to compute tropical SVMs, and computational experiments that show our methods work well.
|
