You are here

Gradient boosting for sequence alignment

TitleGradient boosting for sequence alignment
Publication TypeConference Paper
Year of Publication2006
AuthorsParker, C., A. Fern, and P. Tadepalli
Conference NameNational Conference on Artificial Intelligence (AAAI-2006)
Date Published07/2006
PublisherAAAI Press
Conference LocationBoston, MA
ISBN Number978-1-57735-281-5

Sequence alignment is a common subtask in many applications such as genetic matching and music information retrieval. Crucial to the performance of any sequence alignment algorithm is an accurate model of the reward of transforming one sequence into another. Using this model, we can find the optimal alignment of two sequences or perform query-based selection from a database of target sequences with a dynamic programming approach. In this paper, we describe a new algorithm to learn the reward models from positive and negative examples of matching sequences. We develop a gradient boosting approach that reduces sequence learning to a series of standard function approximation problems that can be solved by any function approximator. A key advantage of this approach is that it is able to induce complex features using function approximation rather than relying on the user to predefine such features. Our experiments on synthetic data and a fairly complex real-world music retrieval domain demonstrate that our approach can achieve better accuracy and faster learning compared to a state-of-the-art structured SVM approach.