Riccardo Poli, Luca Citi, Francisco Sepulveda,
Brain Computer Interfaces Laboratory
School of Computer Science and Electronic Enginneering, University of Essex, UK
The keyboard is a device that, with its many switches, provides us with an interface that is reliable but also very unnatural. The mouse is only slightly less primitive, being an electro-mechanical transducer of musculoskeletal movement. Both have been with us for decades, yet they are unusable for people with severe musculoskeletal disorders and are themselves known causes of work-related upper-limb and back disorders, both hugely widespread problems [1,2]. It will be a major contribution to computer interface technology one day to be able to replace mouse and keyboard with Brain-Computer Interfaces (BCIs) capable of directly interpreting the desires and intentions of computer users.
In this article we describe our approach, results and promising new research directions in the realisation of BCIs, with particular reference to a 2-D pointing device.
Several features characterise our approach. Firstly, our system is logically analogue. That is, contrary to previous BCI design wisdom, at no point a binary decision is made as to whether or not specific brain signals were actually produced in response to stimuli, the actions of the system being controlled by directly combining the amplitudes of the output produced by a filter in the presence of different stimuli. The use of Evolutionary Algorithms (EAs) is the second unique feature of our approach to BCI. Since prior to this work no design techniques existed for this type of system, part of the system was designed by an EA (see appendix for a brief introduction to EAs). Interdisciplinarity is the third feature of our approach as BCIs require that technical solutions are compatible or even exploit the cognitive and perceptual limits of the human mind.
Many different signals have been used in BCI studies to date. These include: or rhythms , evoked potentials (EPs) , ERD/ERS , activation patterns induced by mental task strategies [6,7], slow cortical potentials  recorded from the scalp, cortical neuron activity recorded by implanted electrodes , neuromagnetic signals recorded through MEG , BOLD responses recorded through fMRI , activity-related, localised brain oxygenation recorded through near infrared systems , and, last but not least, P300 waves  and other event related potentials (ERPs).
ERPs are relatively well defined shape-wise variations to the ongoing EEG elicited by a stimulus and temporally linked to it. ERPs include an exogenous response, due to the primary processing of the stimulus, as well as an endogenous response, which is a reflection of higher cognitive processing induced by the stimulus . The P300 wave is a late appearing ERP with a latency of about 300 ms that is elicited by rare and/or significant stimuli. Effectively the presence of P300s depends on whether or not a user attends such stimuli. This is what makes it possible to use them in BCI systems to determine user intentions. P300s are the basis of our approach to BCI.
Over the years, there have been some attempts to develop BCI systems for controlling 2-D pointer movements. In [15,16] a BCI mouse was proposed which is based on P300s. Four stimuli (arrows) are placed at the margins of the screen. They flash at regular intervals. When the arrow in the direction of interest is flashed, a P300 wave is produced. A relatively simple algorithm performs a binary classification of the stimulus response for each of the four directions as target or non-target and then moves the pointer in the direction of the target. In an effort to limit interference between different stimuli, the system uses a rather long inter-stimulus interval (2.5 seconds). Therefore, the mouse pointer moves at the rate of one movement every 10 seconds. Because the system can only detect the desired direction of motion, not the desired extent of the motion, motion is quantised.
A different approach for 2-D cursor movement based on P300 has been proposed in . There, too, four stimuli positioned to the north, east, west and south of a fixation cross were used. The stimuli (four crosses) were only about 1 cm away from the middle of the screen. At intervals of 1 second one random stimulus was replaced by an asterisk for 250 ms. When all stimuli had flashed, the amplitude of each response was averaged over the intervals 300-600 ms typical of P300s. A decision as to which stimulus the subject was attending was made on the basis of which of the four stimuli produced the highest average. So, also this system, like [15,16], makes binary classifications. Its best speed is one cursor movement every 4 seconds. The best accuracy achieved in the system in detecting P300s was only about 50%, which implies that reaching a target ten steps away in the attended target direction would require about 2 minutes of actual time on task [17, pp. 180]. To increase accuracy, the use of multiple repetitions of each trial before making a decision was explored. However, this approach gave no improvements.
Much better performance can be obtained in systems based on frequency analysis, and in particular the detection of or rhythms. For example,  reports that four users where able to move a 2-D pointer to one of 8 target locations at the margins of the screen within between 1.9 and 3.9 seconds with accuracies ranging from 70% to 92%. The disadvantage of this kind of systems is that they require an extensive training period. For example, in , users underwent between 22 and 68 training sessions at a rate of 2 to 4 sessions per week. Another disadvantage is that around 20% of users are unable to control their rhythms.
There is also research on invasive BCIs for 2-D pointer control (e.g., ). However, the invasiveness of the approach still poses ethical concerns, especially for healthy subjects.
We took some initial successful steps with an evolutionary approach to P300-based BCIs in  using one of the Wadsworth datasets  following the Donchin P300 matrix speller paradigm  for the BCI competition 2003 . There, despite our using a traditional P300-detection-based approach, a GA found new ways of processing and combining EEG signals to improve P300 detection accuracy.
When analysing the behaviour of the evolved detectors we found evidence for what we called ``near targets'': P300-like waves were generated in the presence of stimuli that were close to the target. What was most interesting was that the amplitude of these waves appeared to be modulated by the distance from the target: the closer the flashing stimulus to the target, the larger the amplitude of the P300 waves it genereated. Irrespective of the interpretations that can be given to this phenomenon (see for example ), it then became clear that other perceptual phenomena such as attentional blink, repetition blindness and other effects caused by attentional limits can happen in the presence of rapid serial visual stimulation such as that used in many P300-based BCI systems .
These perceptual errors may hamper the performance of single-trial P300 detectors. The standard approach is to circumvent their effects. For example, to achieve reliable recognition designers typically average multiple repetitions of the same stimuli, before allowing the BCI system to make a decision. However, averaging makes BCI systems slow. Our approach, instead, is to attempt to build systems that exploit the information contained in spurious waves elicited in the presence of perceptual errors.
Encouraged by the positive results with evolutionary BCIs, we decided to extend the approach and build a BCI mouse system with realtime processing and classification which fully embraced the idea of exploiting all the information available in P300s. For space limitations, below we provide an overview of the system. Full details on the experimental procedure and the system can be found in [25,26,27].
Similarly to [15,16], in our system four stimuli (rectangles) are also constantly superimposed on whatever is shown on a computer screen. They are unobtrusive, being small and aligned with the upper, lower, left and right borders of the screen (see Figure 1). Each rectangle corresponds to a possible direction of movement for the mouse cursor. At 180 ms intervals, this static display is altered by changing the colour of a randomly chosen rectangle from gray to red for 100 ms. Rectangles are drawn without replacement and the last rectangle to flash in a series is not allowed to be the first to flash in the next series. The user devotes his/her attention to the flashes of the rectangle towards which the cursor should move. This produces endogenous EEG components following each stimulus, which the system analyses to infer the user's intentions and move the cursor.
The analysis of the P300 components is based on a preprocessing phase in which the Continuous Wavelet Transform (CWT) of the EEG is performed. In the normal use of the system only a subset of EEG channels and wavelets are used. However, during an initial adaptation phase, CWT is computed for all channels and at several tens of scales and times after the presentation of the stimuli. So, the ERP response to each stimulus is a set of over 20,000 features.
To avoid the standard problems caused by such a large number of features, we took a wrapper approach to feature selection  where the selection of features and the training of an adaptive system using them are performed jointly by an EA. This implies that the system needs to be adapted and optimised by an EA before a user can use it. However, this phase is very short and our evolutionary system makes it possible to control the pointer for a person having undergone no previous training and within minutes of wearing the electrode cap.
Pointer motion control is achieved via a squashed linear combination of features selected by the EA. The coefficients of this linear filter are also optimised by the EA. The output of the filter is interpreted as the degree to which a trial contains a target, i.e., the stimulus on which a participant is focusing his/her attention. When all rectangles have flashed exactly once, the pointer is moved. The vertical motion of the pointer is proportional to the difference between the output produced by the filter when processing a trial where the ``up'' rectangle was flashed and the output produced by the filter when processing an trial where the ``down'' rectangle was flashed. Similarly, the horizontal motion of the pointer is determined by the difference between the outputs produced in response to the flashing of the ``right'' and ``left'' rectangles. At our stimulus presentation rate the pointer moves once per second, which compares very favourably with other systems.
Our system presents unique features. It completely dispenses with the problem of detecting P300s (a notoriously difficult task) by logically behaving as an analogue device. Thus, the motion step-size varies with the shape and size of the elicited P300s, thereby providing a more natural motion than that produced by systems based on the classification of P300s. Also, the system uses a single trial approach where the mouse performs an action once per second. All this has been made possible by the use of EAs, which rapidly and effectively adapt the design of the system to each user.
In  the system was tested in controlled conditions where the screen was exactly as shown in Figure 1, i.e., without icons, windows, etc. We collected data with six participants (including one with a neuromuscular disability). In all cases users were able to control the mouse. In tests where users controlled the mouse for 4 to 8 30-second periods, the distance moved in the target direction over the absolute error in orthogonal direction was on average 28.1 (i.e., ).
Having established that the approach works and is accurate in controlled conditions, we also explored more realistic applications of the mouse with one of our participants .
The first application we considered was the use of the mouse to control a standard computer system. In this application, the screen included our four flashing rectangles and a fixation cross as in the tests of the BCI mouse described above. Naturally, the background included the standard windows and icons normally available in a user interface (see Figure 2). In order to make the system as user friendly as possible for people with limited or no oculomotor control, instead of moving the mouse pointer on a fixed screen, we decided to scroll the screen, thereby ensuring that the entities of interest for the user were always near the fixation cross. In addition, we used a zoom factor of 2 to ensure maximum readability.
The user was immediately able to move the pointer to the desired locations on the screen and after a few minutes had a good control of the system, as shown in the ``film strip'' in Figure 2, where the user was able to scroll from the top left corner to the lower left corner of the main window in around 13 seconds, which we find encouraging particularly considering that other P300-based systems may require minutes to achieve the same. We expect that much better performance could be obtained by specifically training the control system for this specific application and by giving participants more time to adjust to the system.
Naturally, the availability of 2-D pointer motion makes it possible to input data of any other type. Numerous systems exist, for example, that can turn mouse movements into text. So, as our second test application we designed a simple prototype speller system. We wanted to test the viability of spelling by BCI mouse and determine whether the accuracy of the control is sufficient for the task. In our BCI speller system, a circle with 8 sectors is drawn in the centre of the screen (Fig. 3). Each sector represents one of the 8 most used characters in English. The system starts with the pointer at the centre. To enter a character, the user moves the pointer in the desired sector of the screen. The character is acquired as soon as the cursor reaches the perimeter of the circle or a maximum time has elapsed. Once a character is entered the pointer is repositioned at the centre.
The user was able to input the words ``she has'' three times, albeit very slowly (3.2 bits/minute), making only two spelling errors. However, again, we should expect much better performance by retraining the system for this application.
The aim of our present work has been to turn these preliminary proof-of-concept explorations into practical systems for everyday use. Many problems need to be solved to achieve this goal. These include, for example, the maximisation of information transfer from a user's mind to the computer, the minimisation of the cognitive effort involved in using our BCI-mouse systems and its derivates, the maximisation of the practicality and cost-effectiveness of the system, the verification of the long term viability of the system, the exploration of the limits of an analogue BCI approach, etc.
Many of these problems require an interdisciplinary approach where engineering principles come to terms with (and exploit) the psychophysics of perception and attention. This is perhaps our current biggest challenge.
The problem is not simply the need to plough the immense literature accumulated over more than 50 years of ERP research in psychology, psychophysiology, etc. in search for results applicable to the stimuli and tasks of a specific BCI. A big problem is that information about ERP shapes and latencies, while available, can be contradictory. For example, the shape of ERPs may depend on whether one uses AC- or DC-coupled amplifiers, the degree to which pre-processing filters affect the frequency spectrum of such ERPs, the electrode and reference chosen, etc. Also, how would we know what ERPs will be present at different stages in the processing of a novel or perhaps complex set of BCI stimuli? We would need to perform psychophysiological studies to find out.
An important question one needs to ask in relation to this is whether we can trust such studies (whether new or from the literature). As researchers have known for many years [29,30,31,32], and as we have recently confirmed , the standard techniques of stimulus-locked or response-locked averaging used in such studies are highly biased and may severely misrepresent what really goes on in the brain on a trial by trial basis.
As part of our BCI studies, we have recently developed a new simple technique that can provably improve the situation . We have also found that with the help of EAs this technique can be further improved . Nonetheless, our averaging technique is new and has only been applied to a handful of cases. So, from the point of view of designing psycho-physiologically sound BCIs, we find ourselves back to square one, our prior knowledge of the shape and latencies of ERPs being unreliable and requiring case-by-case corroboration using the new technique.
Our long term objective is to obtain brain-computer interfaces that are more powerful, reliable, adaptable and user-friendly than musculoskeletal computer control. While for able-bodied people there is still a long way to go before we can achieve this, for people who are ``locked-in'' or lack any useful muscle control, even a slow BCI system could give the ability to answer simple questions, express wishes to their caregivers, control the environment, perform slow word processing, or even operate a prosthesis. Also, to people who suffer from upper-limb disorders and are forced to use speech-recognition software, through which it is difficult to control point-and-click interfaces, a BCI mouse could prove a wonderful solution.
In this paper we have presented our approach to the development of BCI systems based on the use of P300 waves. We advocate the use of analogue systems that do not require a binary decision to be made as to whether or not a P300 is actually produced in response to a stimulus. In such systems, the actions of a BCI are directly controlled by combining the amplitudes of the output produced by a filter in the presence of different stimuli. The use of an analogue system was suggested by our desire to exploit as much of the information within ERPs as possible, including that deriving from perceptual errors resulting from the limitations of human cognitive systems.
We also advocate the use of EAs: the most ardous part of the design of our systems (i.e., feature selection and the selection of the type, order and parameters of the controller) was entirely left to EAs. There is very limited knowledge as to how to manually design analogue BCI mouse systems. Evolution, on the other hand, being entirely guided by objective measures of success (the fitness function), was able to achieve this almost effortlessly. The GA was very effective and efficient at finding good designs for the system. Indeed, it succeed in every run, suggesting that we had chosen the infrastructure for the system and the feature set reasonably well.
The performance of our systems has been very encouraging. As mentioned above, all participants have been able to use our mouse within minutes. In validation, the trajectories of the pointer have achieved high accuracy. The system issues control commands at a much faster rate (approximately once per second) than other P300-based computer mice previously described in the literature. The systems evolved were also rather robust. For example, it was possible to control the mouse even in situations very different from the ones originally considered in training, such as in tests with control in a real Windows environment and in our BCI speller, without retraining the system.
Our encouraging results indicate that there may be a lot of unexploited information about user intentions in EEG signals, and that perhaps, traditional design and analysis techniques may be a limiting factor. We plan to explore this in future research.
Evolutionary algorithms are search and optimisation algorithms inspired by Darwinian evolution, which have been applied very successfully to a large number of difficult problems with human-competitive results (e.g., see  for a comprehensive list). Many variants of evolutionary algorithms exist [36,37,38,39,40].
In Genetic Algorithms (GAs)  -- the type of evolutionary algorithm used in the work reported in this paper -- a population of random tentative solutions to a problem (e.g., BCI classifiers) is created and evaluated to assess the degree to which they solve the problem at hand. New generations of individuals are created by recombining the characteristics of individuals in the previous generation, giving better performing parent solutions a higher chance of reproduction. In this way, like in nature, generation after generation, better and better solutions emerge. Genetic Programming (GP) [37,38,41] is a variant of the GA where the population under evolution is made up of computer programs. Unlike in nature where thousands of years are necessary to evolve highly fit individuals, on modern computer GAs and GP can solve complex problems within a few minutes.
Because of their effectiveness, evolutionary algorithms are now routinely applied in the area of image and signal processing (e.g., see [42,43,44,45] and [41, Chapter 12]). However, no application of EC in the area of BCI has been reported with the exception of the work discussed in this article and our own preliminary results in  where we used an evolutionary approach to process speller data.