Efficient learning algorithm for sparse subsequence pattern-based classification and applications to comparative animal trajectory data analysis

ABSTRACT

Recent advances in robotics and measurement technologies have enabled biologists to record the trajectories created by animal movements. In this paper, we convert time series of animal trajectories into sequences of finite symbols, and then propose a machine learning method for gaining biological insight from the trajectory data in the form of symbol sequences. The proposed method is used for training a classifier which differentiates between the trajectories of two groups of animals such as male and female. The classifier is represented in the form of a sparse linear combination of subsequence patterns, and we call the classifier an S3P-classifier. The trained S3P-classifier is easy to interpret because each coefficient represents the specificity of the subsequence patterns in either of the two classes of animal trajectories. However, fitting an S3P-classifier is computationally challenging because the number of subsequence patterns is extremely large. The main technical contribution in this paper is the development of a novel algorithm for overcoming this computational difficulty by combining a sequential mining technique with a recently developed convex optimization technique called safe screening. We demonstrate the effectiveness of the proposed method by applying it to three animal trajectory data analysis tasks.