A Review of Kernel Methods Based Approaches to Classification and Clustering of Sequential Patterns, Part I: Sequences of Continuous Feature Vectors

Introduction To Sequential Pattern Analysis Using Kernel Methods

Classification and clustering of patterns extracted from sequential data are important for pattern discovery using sequence data mining. Pattern discovery from bio-sequences involves classification and clustering of discrete symbol sequences. Pattern discovery from multimedia data such as audio, speech and video data involves classification and clustering of continuous valued feature vector sequences. Classification and clustering of sequential patterns of varying length have been challenging tasks in pattern recognition. Conventional methods for classification of sequential patterns use discrete hidden Markov models (HMMs) for discrete sequences, and continuous density HMMs for continuous feature vector sequences. Conventional methods for clustering of sequential patterns use distance measures such as edit distance for discrete sequences and dynamic time warping based distance for continuous feature vector sequences. During the past 15 years, kernel methods based approaches such as support vector machines and kernel K-means clustering have been explored for classification and clustering of static patterns and sequential patterns. Kernel methods have been shown to give a good generalization performance. This Chapter presents a review of kernel methods based approaches to classification and clustering of sequential patterns.

Kernel methods for pattern analysis involve performing a nonlinear transformation from the input feature space to a higher dimensional feature space induced by a Mercer kernel function, and then constructing an optimal linear solution in the kernel feature space. Support vector machine for two class pattern classification constructs an optimal hyperplane corresponding to the maximum margin separating hyperplane in the kernel feature space (Burges, 1998). Kernel K-means clustering gives an optimal nonlinear separation of clusters in the input feature space by minimizing the trace of the within-cluster scatter matrix for the clusters formed in the kernel feature space (Girolami, 2002; Satish, 2005). The choice of the kernel function used in the kernel methods is important for their performance. Several kernel functions have been proposed for static patterns. Kernel methods for sequential pattern analysis adopt one of the following two strategies: (1) Convert a sequential pattern into a static pattern and then use a kernel function defined for static patterns, and (2) Design and use a kernel function for sequential patterns. Kernel functions designed for sequential data are referred to as dynamic kernels or sequence kernels (Wan & Renals, 2002). Examples of dynamic kernels for continuous feature vector sequences are Gaussian mixture model (GMM) supervector kernel (Campbell et al., 2006b) and intermediate matching kernel (Boughorbel et al., 2005). Fisher kernel (Jaakkola et al,. 2000) is used for both the discrete observation symbol sequences and sequences of continuous feature vectors. This Chapter discusses the issues in designing dynamic kernels for continuous feature vector sequences and then presents a review of dynamic kernels proposed in the literature.

Dynamic kernels for continuous feature vector sequences belong to the following two main categories: (1) Kernels such as Fisher kernels that capture the sequence information in the feature vector sequences, and (2) Kernels such as GMM supervector kernels and intermediate matching kernels that consider the feature vector sequences as sets of feature vectors. The kernels belonging to the first category have been explored for classification of units of speech such as phonemes, syllables and words in speech recognition. The kernels belonging to the second category have been explored for tasks such as speaker identification and verification, speech emotion recognition and image classification. This chapter presents a review of dynamic kernels based approaches to classification and clustering of sequential patterns.

The organization of the rest of the chapter is as follows: The next section describes the kernel methods for pattern analysis. The SVM based approach to pattern classification and kernel based approaches to pattern clustering are presented in this section. Then the design of dynamic kernels for sequential patterns is presented in the third section. This section also describes the dynamic kernels for continuous feature vector sequences. Finally, we present a review of kernel methods based approaches to sequential pattern analysis.