SVM-Q Based Classification Method In EEG-Based Brain-Computer Interfaces

SVM-Q Based Classification Method In EEG-Based Brain-Computer Interfaces

SVM-Q Based Classification Method In EEG-Based Brain-Computer Interfaces

Ashwani Kumar Jha Shikhar Kumar

Birla Institute of Technology, Mesra Birla Institute of Technology, Deoghar

Abstract

Brain computer interface technology provides a physically disabled person to control a device with the help of brain signal. In previous studies various signal processing techniques followed by classification method allows to distinguish the brain signal which is best suited for communication. This paper gives the proposal of signal classification by a Support Vector Machine (SVM) with the addition of sub algorithm called Quick sort method. After extracting the features by using different phase locking methods followed by sorting of feature vector. There after SVM is applied to this feature vector for classification of Brain signal for two different motor imagery action for left and right hand movement.SVM-Q is very effective in the calculation as our best result were 86% on BCI competition Data Set IIIa and 77% on Data Set IIIb. In summary this paper demonstrates how the sorting algorithm enhances the ability of SVM classifier.

Keywords- Brain Computer Interface (BCI), Phase Locking Value (PLV), Support Vector Machine (SVM), Event-RelatedSynchronization(ERS), Event-Related Desynchronization (ERD) and Quicksort.

1. Introduction

   A BCI is a system which allows us to control the devices with the help of brain signal. This enables us to operate and move like computer cursor or robotic limb by only using our thoughts. The idea is just to provide a new communication channel to people who are paralyzed but are cognitively intact, e.g. people suffering from the so called locked-in syndrome. It is very active area of research especially over past ten years. This research is especially based on recording and analyzing EEG brain activity and recognizing EEG patterns associated with mental states. Likewise, imagining a movement of the right hand is associated with a pattern of EEG activity in the left side of the motor cortex. Thats why we have to be very careful in choosing the mental tasks. As they activate different parts of brain and make possible to detect it. For example we consider left hand

   movement and right hand movement are associated with the right side of cortex and left side of cortex.

   The increasing success of BCI system is partially due to a better understanding of the dynamics of brain oscillation that generate EEG signals. Feedback loop is responsible for the oscillatory activity generated by brain network of neurons which is recorded in the EEG. Normally the frequency of such oscillations become slower with increase

   in synchronization. Sensorimotor activity such as body movements or mental imagery (e.g. imagining body movement) changes the oscillatory pattern resulting in amplitude suppression called event related desynchronization or amplitude enhancement called event related synchronization on the Rolandic mu rhythm(7-13Hz) and the central beta rhythms above 13 Hz. This phenomenon has been known since the 1940s (Jasper and Penfield 1949)[6]. Thereafter the supervised classification methods are employed to learn to recognize these patterns of EEG activities, i.e. to learn the mapping between the EEG data and classes corresponding to mental tasks such as movement of right hand (Lotte et al. 2007).

   In this paper we use classifier called Support Vector Machine (SVM) which is also known as binary classifier. It is most popular classification algorithm for the EEG for its usually higher classification accuracy compared to the other classifier tools. This classification method is introduced by Vapnik (1995). The primary motivation behind SVM is to directly deal with the objective of generalization from training data to testing data with minimization of error and complexity of learning algorithm.

   Here we used dataset of BCI competition III [1] for the analysis purpose. After applying feature extraction on the given set of data we used sorting algorithm called quicksort. This enables the SVM to be applicable on very large dataset and causes better effect on result. Sorting of data in the form of matrix is performed at the stage of training the system.For better classification motor imagery through SVM classifier, Phase locking value (PLV) is taken in this paper for feature extraction process .The instantaneous phase relation was statistically distributed and was computed through Phase locking value (PLV) and was provided to SVM-Q classifier.

   The main goal of this study is to address the following question: Does EEG preprocessing which involves PLV feature extraction techniques with SVM-Q(using quicksort as sub algorithm) classifier improve the classification accuracy in the context of BCIs? The rest of paper is organized as follows: Section II contains Experimental methods which includes description of dataset. It also contains the feature extraction techniques and SVM-Q classification techniques in detail.

   Section III contains result and analysis of paper followed by the section IV which contains most crucial part i.e. conclusion. It also contains mathematical formulation for the validation of result estimated in this paper.

2. Methods

   1. Description of Dataset

      We used dataset IIIa from the BCI III competition (BCI Competition III 2008)[1]. It contains data from 3 subjects: K3b, K6b and L1b and was collected as follows (Schlögel 2005). Each subject, sitting in front of a computer, was asked to perform imaginary movements of the left hand, right hand, tongue or foot during a pre-specified time interval. As mentioned before, when a person imagines such movements, there are associated changes in the EEG datacalled ERD or ERS. 60 electrodes were placed on the scalp of the subject recording a signal sampled at 250 Hz and filtered between 1 and 50 Hz using a Notch filter.

      Each trial starts with a blank screen. At t=2s, a beep is generated and a cross +is shown to inform the subject to pay attention. At t=3s an arrow pointing to the left, right, up or down is shown for 1s and the subject is asked to imagine a left hand, right hand, tongue or foot movement, respectively, until the cross disappears at t=7s. This is followed by a 2s break, and then the next trial begins. For each subject 60 trials per class were recorded.

      Two data files are available for each subject: training and testing.

   2. Pre-processing and Feature Extraction

      Data Pre-processing: The data of the C3,Cz, and C4 electrode was pre filtered between 8-30 Hz by Chebyshev band pass filter because motor imagery action takes place between this frequency .Then phase synchronization methods was applied to the filtered data for feature extraction.

      Feature Extraction: Phase Synchronization Method

      The synchronization which is taken here between EEG signals is classical coherence method known as phase locking Value (PLV)[3]. It is defined as by the following equation

      PLV=|< m n () >| (1)

      Here isthe instantaneous phase of the electrodes m and n. The instantaneous phase could be calculated by Hilbert transform and is defined as

      x=1 PV () (2)

      PV is defined as the integral is taken in sense of Cauchy principal value, and the instantaneous phase is calculated as

      i=tan-1 (3)

      In equation 1 ( < >) denotes the operator averaging over time. For discrete time signal following expression is used to compute the phase ocking value

      =1

      =1

      PLV=| N eii | (4)

      PLV is calculated by averaging the eii vector over time .When the phase difference is constant the PLV is equal to 1 and if the phase is random over [0-2] then vector sum and thus the PLV is zero[4].

      The PLV between the electrode pair was C3,C4 and Cz was calculated and appreciable phase difference was selected as the feature vector and was put SVM- Q classifier .

   3. SVM-Q Classifier

      Support Vector Machine (SVM): Support Vector Machines (SVM) have recently gainedprominence in the field of machine learning and pattern classification. Classification is achieved by realizing a linearor non-linear separation surface in the input space[5].In Support Vector classification, the separating function canbe expressed as a linear combination of kernels associatedwith the Support Vectors as

      = , +

      Where xi denotes the training pattern, yi {+1,-1} denotes the corresponding class label and S denotes the set of Support Vector.

      The dual formulation yields

      The outline of our algorithm is as follows:

      1. Apply PLV as feature selection method and obtain feature vector.

      2. The above feature vector is then sorted by

         min

         = 1

         + 1

         using Quick-sort sorting techniques.

         0

         2

         ,

         int functionPartition (ArrayA, intLb, intUb);

         begin

         select a pivot from A[Lb]…A[Ub];

         reorderA[Lb]…A[Ub] such that:

         all values to the left of the pivot are <= pivot all values to the right of the pivot are >= pivot

         returnpivot position;

         end;

         int functionPartition (ArrayA, intLb, intUb);

         begin

         select a pivot from A[Lb]…A[Ub];

         reorderA[Lb]…A[Ub] such that:

         all values to the left of the pivot are <= pivot all values to the right of the pivot are >= pivot

         returnpivot position;

         end;

         ,

         Where i are the corresponding coefficients, b is the offset, Qij = yiyjK(xixj) is a symmetric positive definite kernel matrix and C is the parameter used to penalize error points in the inseparable case. The Karush-Kuhn-Tucker (KKT) conditions for the dual can be expressed as

         = = + 1

         procedureQuickSort intUb);

         begin ifLb<Ubthen

         procedureQuickSort intUb);

         begin ifLb<Ubthen

         (ArrayA,

         (ArrayA,

         intLb,

         intLb,

         and

         = ( 1) (2)

         M = Partition (A, Lb, Ub); QuickSort (A, Lb, M – 1); QuickSort (A, M + 1, Ub);

         end;

         M = Partition (A, Lb, Ub); QuickSort (A, Lb, M – 1); QuickSort (A, M + 1, Ub);

         end;

         = = 0 (3)

         This partitions the training set into S the Support Vector Set (0< i<C, = 0), E the error set (i = C,

         < 0) and R the well classified set (i = 0, > 0) .

         If the points in error are penalized quadratically with a penalty factor C, then, it has been shown that the problem reduces to that of a separable case with C =

         . The Kernel function is modified as

         = + 1

      3. The sorted feature vector is then classified by using SVM.

3. Results and Discussion

   Where = 1 if i=j and = 0 otherwise. The advantage of this kind formulation is that the SVM problem reduces to that of linear separable case.

   While training the SVM we use sorted form of data after applying feature selection techniques. We intently used Quicksort techniques for sorting the data as it took less memory of computer and have less time complexity in comparison to other sorting algorithm. Since, the training set data is very large and it requires sorting for the better accuracy in classification. We need the large data set for the training of system.

   Figure 1: Classification of motor Imagery left hand and right hand movement before sorting

   The fig. 1 illustrates the SVM classification of the test data. After getting feature vector from the PLV feature selection method. We can clearly observe from figure is that the classification of motor imagery of left hand and right hand is not so good as the optimal hyperplaneis not able to classify it into two part. Clearly the feature vector of different motor

   imagery action is randomly distributed throughout in the space.

   Figure 2: Classification of Motor Imagery left hand and right movement after sorting

   After applying sorting (Quicksort) algorithm and then classify the test data with classifier SVM. This allows the maximization of two different motor imagery action on two opposite side of hyperplane which is decision boundary surface. Since the fig.2 illustrates that the sorting of feature vector allows to cluster of two different kind of feature vector (denoting two separate imagery action) in 2-D space at two different location. Due to this reason optimal hyperplane can able to classify the test data and will improve in accuracy of the classification.

   Table 1. Classification accuracy for each subject when two different classification tools SVM and SVM-Q are used .

   Subjects SVM-Q SVM K3b 86% 62%

   K6b 82% 57%

   L1b 77% 54%

   Hence, the table 1 confirm that the enhancement in SVM classifier provide the better accuracy rate in comparison to previous normal SVM classifier. SVM-Q is just an approach which makes the performance of SVM classifier even better.

   In summary our experiment show that the addition of sub-algorithm of sorting techniques with SVM have better accuracy rate than the normal SVM classifier.

4. Conclusion

   In this paper we study classification of mental tasks for EEG based BCI with the help of SVM-Q.

   Our evaluation included algorithm that have not been previously applied for classification of BCI data or have received very little attention. EEG synchronous oscillation for a key component for establishing information exchange between different regions of brain. Phase Synchronization not only provides an effective feature vector but also establish reference for motor imagery. The results showed that these classifiers (SVM) in addition with very popular sub- algorithm for sorting (Quicksort) produced better result than the normal SVM classifier.

   The results also showed that our classification accuracy for this classifier is far better than the previously used SVM.

   There are several avenues for future work. First we use this method of classification after using different feature selection techniques like CSP, spectral estimation.

   Second, the BCI2000 software could be extended to report accuracy.

   Third, more research is needed to choose the right mental tasks for an on-line BCI application and also to study the effect of the feedback and the potential benefit of using on-line classification algorithm.

5. References

1. A.Schlogl, Result of BCI competition III for data set IIIa and III b, 2005. [Online].Availabe:http://bci.tugraz.at/schloegl/public ation/TR_BCI2005_III.pdf

2. Wolpaw J R and Mcfarland DJ 1994, Multichannel EEG based brain computer communication Electroencephalgr.

   Clin.Neurophysiol90 444-9

3. CCarmeli, M. G. Knyazeva, G. innocenti, and

   O. De

   Feo., Assessment of EEG synchronization based on state-space analysis, NeuroImage., vol.25, 2005, pp.339-354

4. Clemens Brunner, Reinhold Scherer, Bernhard Graimann,

   Online Control of a Brain-Computer Interface Using Phase

   Synchronization, IEEE Trans on Biomed Eng. Vol.53, no

   12 , 2006, pp.2501-2506..

5. C.J.C Burger, A tutorial on support vector machine for pattern recognition, Data mining Knowl.

   Discov.2 (1998)121-167

6. Jasper H.H. and Penfield, W (1949): Electrocardiograms in man: efect of voluntary movement upon electrical activity of the pre central gyrus. Arc.Psychiat.Z.Neurol.183:163-174.