Leonor Becerra-Bonache

M Dolores Jiménez-López

Children as Models for Computers: Natural Language Acquisition for Machine Learning

This paper focuses on a subfield of machine learning, the socalled grammatical inference. Roughly speaking, grammatical inference deals with the problem of inferring a grammar that generates a given set of sample sentences in some manner that is supposed to be realized by some inference algorithm. We discuss how the analysis and formalization of the main features of the process of human natural language acquisition may improve results in the area of grammatical inference.

Introduction

In the so-called information society there is a need for a comprehensive language technology for information management. While computers can communicate only through artificial languages designed specifically for them, its use will be restricted to a minority of people. The natural thing would be to allow users to speak to the computer in their own natural language. To solve the problem of communication between machines and humans it is necessary to construct artificial mechanisms to simulate the human processing and acquisition/learning of language. The computational models of language that have been proposed up to now are far from satisfactory. To reach suitable models is a problem that must be approached from an interdisciplinary perspective. In this interdisciplinary task, linguistics and the knowledge of how natural language is acquired and processed have a key role.

Artificial Intelligence aims to study and design intelligent machines. This field was founded in 1956. AI founders were very optimistic about the future of this new field. For example, H. Simon predicted that "machines will be capable, within twenty years, of doing any work a man can do" [START_REF] Culy | The complexity of the vocabulary of bambara[END_REF]. In 2010, we can state that this prediction has not come true yet. However, we have machines that are able to do "some of the things" that a man can do; for example, we have machines that are able to play soccer, to play some instruments, to express feelings by moving their face (e.g., MDX, KISMET), etc. Nevertheless, what has not been achieved yet is that machines learn to speak.

It is a truism that natural languages are very complex, but despite this complexity a child is able to efficiently learn a natural language in a very short time. Children are able to learn any natural language given the adequate input, and they do so effortlessly, with a limited exposure to data, and without any specific training. Therefore, if we are able to give machines the capacity of learning language as children do, maybe we could reach to have computers that learn to speak. A computational simulation of natural language acquisition could be used to develop computer systems that can recognize, understand and generate natural languages, solving in this way the problem of communication between machines and humans.

Machine Learning is a field of Artificial Intelligence that aims to develop techniques that allow computers to learn. Concretely, it consists in designing and developing algorithms that allow to computers to change their behaviour based on some data. Grammatical Inference (GI) is a specialized subfield of Machine Learning that deals with the learning of formal languages from a set of data. To solve a GI problem requires, on one hand, a teacher that provides data to a learner, and on the other hand, a learner (or learning algorithm) that from that data must identify the underlying language. As we can see, this process has some similarities with the process of language acquisition (instead of a teacher and a learner, we have an adult and a child). Therefore, GI provides a good theoretical framework to investigate the idea of simulating some of the features of natural language acquisition in order to check if they could simplify or improve the problem of learning a language.

In general it is claimed that machine learning or GI can provide natural language processing/acquistion a range of alternative learning algorithms as well as additional general approaches and methodologies [START_REF] Parekh | Grammar inference, automata induction and language acquisition[END_REF][START_REF] Clark | Grammatical inference and first language acquisition[END_REF]. So, it is accepted that GI models can help in the understanding of how humans process and acquire language. In this paper we claim the opposite direction, that is, that simulation of the process of acquiring a natural language could improve GI techniques and this improvement could have important implications in the field of human language technologies. Therefore, what we defend here is that natural language acquisition can help GI. If computers are able to learn a language like a human, they could use language like a human. If we are able to create machines with human-like capabilities (like learning a language), we will make possible for the user to interact with the computer, without any special skill or training, just as they would do to a person.

Grammatical Inference Models

The research field known as GI deals with the learning of formal languages. Roughly speaking, a GI problem can be considered as a game played between two players: a teacher and a learner. The teacher provides information to the learner, and the learner must identify the underlying language from that information [START_REF] Clark | Grammatical inference and first language acquisition[END_REF]. The initial theoretical foundations of GI were given by E.M. Gold [START_REF] Gold | Language identification in the limit[END_REF]. A remarkable amount of research has been done after Gold's seminal work. Three formal models have been widely investigated in the field of GI:

-Identification in the limit [START_REF] Gold | Language identification in the limit[END_REF].

-Query learning model [START_REF] Angluin | Learning regular sets from queries and counterexamples[END_REF].

-PAC learning model [START_REF] Valiant | A theory of the learnable[END_REF].

Each of these models is based on different learning settings (what kind of data is used in the learning process and how these data are provided to the learner) and different criteria for a successful inference (under what conditions we say that a learner has been successful in the language learning task).

In 1967 Gold introduced the first model for GI: identification in the limit. In this model, after each new example received, the learner (inference algorithm) must return some hypotheses. If the learner returns a correct answer and does not change its guess after this, then we can say that the identification is achieved. There are two traditional settings: i) Learning from text: only positive data (i.e. strings that belong to the languages to be learned) are given to the learner; ii) Learning from informant: positive and negative data (i.e., strings that do not belong to the language) are available to the learner.

A different learning paradigm that has been exhaustively studied in GI is learning from queries, introduced by Angluin. In the query learning model, there is a teacher (oracle) that knows the language and has to answer correctly specific kind of queries asked by the learner. Different kind of queries could be available to the learner, but membership queries (MQs) and equivalence queries (EQs) have established themselves as the standard combination to be used. In the case of a MQ, the learner asks if a string is in the language, and the teacher answers "yes" or "no". When the learner asks an EQ, he makes a conjecture and the teacher answers "yes" if it generates the same language, and if the answer is "no", a counterexample is returned.

Valiant introduced probably approximately correct learning (PAC learning) [START_REF] Valiant | A theory of the learnable[END_REF], which is a distribution-independent probabilistic model of learning from random examples. In this model, the inference algorithm takes a sample as input and produces a grammar as output. A successful inference algorithm is one that with high probability finds a grammar whose error is small. In this PAC learning model, more negative results have been proved than positive results (for GI). Even for the case of DF A, most results are negative. The requirement that the learning algorithm must learn under any arbitrary (but fixed) probability distribution seems too strong.

Each of these models have aspects that make them useful to study the problem of natural language acquisition to a certain extent, but other aspects of the models make them unsuitable for this task. For example, in Gold's model, there is not limit on how long it can take the learner to guess the correct language (but children are able to learn language in an efficient way), the learner hypothesizes complete grammars instantaneously (this is not the case in children's language acquisition), and the learner passively receives strings of the language (but children also interact with their environment). In Angluin's model, the queries introduced in this model are quite unnatural for real learning environments (a child will never ask if his/her grammar is the correct one). Moreover, the learner has to learn exactly the target language (but everybody has imperfections in their linguistic competence) and the teacher is assumed to be perfect (i.e., he knows everything and always gives the correct answers. This is an ideal teacher that does not occur in a real situation). In Valiant's model, the requirement that the examples have the same distribution throughout the process is too strong for practical situations. Therefore, none of these models perfectly accounts for natural language acquisition.

Grammatical Inference as Natural Language Acquistion

The problem of language learning in GI presents similarities with the process of language acquisition. In a GI problem we have a teacher and a learner, the teacher provides information about a language to the learner and the learner must infer the grammar for that language. Similarly, in a process of natural language acquisition, the child receives information from the adult and has to learn the grammar under that language. Taking into account this similarities, and the fact that, despite the complexity of language, a child is able to efficiently learn a natural language in a very short time, what we propose in this section is to implement in GI algorithms some of the main characteristics of natural language acquisition, in order to check if they could simplify or improve the problem of learning a language in the field of GI.

We deal with three different aspects. First, we discuss about the class of languages to be learned. Second, we take into account the type of data/information that should be provided to the algorithm. And finally, we discuss which component of the grammar should be learned.

The Language to be Learned

An important question in GI models is the type of grammars that must be learned. Most of them try to learn regular and context-free grammars and languages. However, limitations of the Chomsky hierarchy to describe natural languages are well known.

The question whether grammatical sentences of natural languages form regular, context-free, context-sensitive or recursively enumerable sets has been subject to many discussions since it was posed by Chomsky in 1957. There seems to be little agreement among linguists concerning the position of natural languages in the Chomsky hierarchy. It seems that neither the family of regular or context-free languages have enough expressiveness to describe the basic contextsensitive syntactic constructions found in natural languages. Several attempts have been made to prove the non-context-freeness of natural languages [START_REF] Bresnan | Cross-serial dependencies in dutch[END_REF][START_REF] Culy | The complexity of the vocabulary of bambara[END_REF]. Despite the fact that the non-context-freeness of natural language has become the standardly accepted theory, there are linguists such as Pullum and Gazdar who, after reviewing the various attempts to establish that natural languages are not context-free, come to the conclusion that every published argument purporting to demonstrate the non-context-freeness of some natural language is invalid, either formally or empirically or both [START_REF] Pullum | Natural languages and context-free languages[END_REF]. Despite these arguments, it seems to be an untenable position that all syntactical aspects in natural languages can be captured by context-free grammars. However, the overwhelming bulk of natural language syntax is context-sensitive. Therefore, it is of interest to study grammatical formalisms with more generative power than CF. However, context-sensitive grammars seems not to be the right solution: they are too powerful, many problems are undecidable, etc. Therefore, it is desirable to find intermediate generative devices able of conjoining the simplicity of context-free grammars with the power of context-sensitive ones.

Within the field of formal languages, the above idea has led to the branch of Regulated Rewriting [START_REF] Dassow | Regulated Rewriting in Formal Language Theory[END_REF]. Matrix grammars, programmed and controlled grammars, random context grammars, conditional grammars, etc. are examples of devices that use context-free grammars while applying some restrictions to the rewriting process in order to obtain context-free structures as well as the noncontext-free constructions present in natural language. However, those devices present, in general, an excesive big generative power that leads to the generation of structures non-significative for natural languages. The idea of keeping under control the generative power, while generating context-free structures and non-context-free constructions, has led to the so-called mildly context-sensitive grammars [START_REF] Joshi | How much context-sensitivity is required to provide reasonable structural descriptions: Tree adjoining grammars[END_REF]. Tree adjoining-grammars, head grammars, indexed grammars, categorial grammars, simple matrix grammars, etc. are well-known mechanisms that generate mildly context-sensitive languages.

Moreover, it is suggested natural languages could occupy an orthogonal position in the Chomsky Hierarchy (i.e., class of languages that contains some regular languages, some non-context-free, and so on). In fact, we can find some examples of natural languages constructions that are neither regular or context-free, and also some regular or context-free constructions that do not appear naturally in sentences. Thus, it seems that Chomsky Hierarchy is not the appropriate place for locating natural languages.

Therefore, if GI models aims to simulate the learning process of natural language they cannot focus on the inference of context-free or regular grammars, but it could be desirable that they concentrate on the learning of grammars that generates mildly context-sensitive languages and that occupies an orthogonal position in the Chomsky Hierarchy. In [START_REF] Becerra-Bonache | On the Learnability of Mildly Context-Sensitive Languages using Positive Data and Correction Queries[END_REF], it has been studied a non-classical mechanism with such properties: the class of Simple p-dimensional External Contextual grammars (SEC). Unlike the Chomsky grammars, SEC do not involve nonterminals and they do not have rules of derivation except one general rule: to adjoin contexts. Roughly speaking, a SEC produces a language starting from a word (base) and iteratively adding contexts (pair of words) at the ends of the currently generated word.

Becerra-Bonache and Yokomori [START_REF] Becerra-Bonache | Learning mild context-sensitiveness: Toward understanding children's language learning[END_REF] made the first attempt to learn SEC. They proved that the class of languages generated by SEC with fixed dimension p and fixed number of contexts q is learnable from positive data, from Shinohara's results. The learning algorithm derived from their main result was not time efficient. In [START_REF] Oates | Inferring grammars for mildly context sensitive languages in polynomial-time[END_REF], it was presented a polynomial-time algorithm for inferring SEC from positive data (small values of p and q were considered). Later, in [START_REF] Becerra-Bonache | Iterative learning of simple external contextual languages[END_REF], it was investigated for which choice of the parameter q (denoting the number of contexts) the class of SEC is iteratively learnable.

All these results suggest that SEC is an interesting class to study. Therefore, due to its linguistic and computational properties, SEC may be an appropriate candidate to model natural language syntax and could improve results in the field of GI.

Available Data for Learning

Another interesting question is to determine the data that must be available to the machine in order to learn the language. In order to correctly simulate natural language learning and take advantage of the simulation, the examples provided to our learning algorithm should be the same as the ones available to a child. But, which source of data is available to children during the learning process? This question has been a subject of controversy and it is still of importance in discussions of learnability. Most GI systems are based on only positive data. If we look at natural language acquisition, the availability of positive data to children is trivially accepted. However, is this the only source of data available to children in order to acquire their native language?

Researchers tend to reduce the kind of data available to children to two types: positive and negative. Positive data is defined as sentences that are grammatically correct and all the remainder is considered negative data. The availability of positive evidence is widely accepted (children are exposed to a large amount of grammatical sentences uttered by adults), but the availability of negative evidence remains a matter of substantial controversy. The distinction between positive and negative data was used by Gold in [START_REF] Gold | Language identification in the limit[END_REF]. This distinction is clear within the framework of formal languages, since positive data refers to strings that belong to the language and negative data to strings that do not belong. However, this classification seems not to be right within the framework of natural languages; it is difficult to classify all the data that children receive as positive or negative, since we can find sentences that are grammatically correct but contain negative information. Therefore, definitions about the kind of data available to children should be refined. Negative data should specially be well defined (its definition is so general than different interpretations have been given [START_REF] Marcus | Negative evidence in language acquisition[END_REF][START_REF] Saxton | The contrast theory of negative input[END_REF]). Beliefs about whether or not children receive negative evidence depends crucially on how one defines that concept. Hence, it is important to define what negative data is exactly. If we consider that negative evidence is completely incorrect utterances from the adult, or adult replies to a child's ungrammatical utterance like "That's wrong", we can state that this source of evidence is very rare.

However, there is growing evidence that corrective input for grammatical errors is widely available to children ( [START_REF] Farrar | Negative evidence and grammatical morpheme acquisition[END_REF][START_REF] Morgan | Negative evidence on negative evidence[END_REF]). During the first stages of children's language acquisition, adults tend to correct incomplete sentences uttered by the child; adults try to repeat the same idea but constructing grammatically correct sentences in the adult grammar [START_REF] Chouinard | Adult reformulations of child errors as negative evidence[END_REF]. This type of correction is called expansion. Expansion preserves the meaning of the child's utterance. Hence, adult's correction have the same meaning as the child's utterance, but different form. Moreover, the correction is a sentence that is grammatically correct, so positive information is obtained. Nevertheless, if a correction is received, this means that the string uttered by the child was not grammatically correct, so negative information is also obtained. Therefore, should corrections be considered as positive or negative data?

Most researchers have traditionally considered that corrections are negative data and should not be taken into account in the learning process, but as we can see, expansions are a kind of correction that is available to children (specifically during the two-word stage of child linguistic development, in which children go from the production of one word to the combination of two elements). Moreover, corrections are difficult to classify as positive or negative data, since they contain positive and negative information at the same time.

Although positive examples are an essential part of the language learning process and play the main role in that process, corrections can play a complementary role, providing additional information that can be helpful during the learning process. Moreover, the information available with a correction could improve learnability, and even some aspects of the language could be learned faster. In fact, some studies show that children that receive expansions learn faster some aspects of the language than those that do not receive them [START_REF] Hernández Pina | Teorías Psicosociolingüísticas y su aplicación a la adquisición del español como lengua materna[END_REF].

Taking into account that none of the GI models has considered the combination of positive data and corrections, what we propose is to formalize a new learning model based on the combination of positive data and corrections. Moreover, this model will try to simulate the different stages of language acquisition in children, and to reflect the real interaction between child-adult during the process of language acquisition.

The first attempt to learn from corrections was made by Becerra-Bonache et al. in [START_REF] Becerra-Bonache | Learning dfa from correction and equivalence queries[END_REF]. They applied the idea of corrections (given to the child during the process of language acquisition) to GI studies, and showed that models of GI can benefit from corrections, for instance, the query learning model proposed by Angluin [START_REF] Angluin | Learning regular sets from queries and counterexamples[END_REF]. Taking into account that the queries available to the learner in Angluin's model are quite unnatural for real learning environments, Becerra-Bonache et al. proposed a new type of queries called correction query (CQ). A CQ is defined as an extension of a MQ, but instead of a yes/no answer, a corrected string is returned to the learner; the correction consists of the shortest extension of the queried string. They proved that it is possible to learn DFA from corrections with a considerable reduced number of queries. Some other works have also followed this line of research, for example, [START_REF] Tîrnauca | Polynomial time algorithms for learning k-reversible languages and pattern languages with correction queries[END_REF]; they also use a correction based on the shortest extension of the wrong queried string, and showed the learnability of k-reversible regular languages in the limit. This model have been also applied to learning pattern languages.

In [START_REF] Becerra-Bonache | Learning balls of strings from edit corrections[END_REF], a new CQ based on edit distance was introduced; when a string is submitted to the teacher, either he validates it (if it belongs to the target language), or he proposes a correction, that is to say, a string of the language close to the query with respect to the edit distance. In that way, the learner is corrected in a more "natural" way. Becerra-Bonache et al. proposed to learn classes of languages defined via edit distance (i.e., topological balls of strings), and with the help of this new CQ. They showed that this class is not learnable in Angluin's MAT model, but is with a linear number of CQs. Moreover, they conducted several experiments with a teacher simulating a human Expert, and showed that their algorithm is resistant to approximate answers. In [START_REF] Kinber | On learning regular expressions and patterns via membership and correction queries[END_REF], it is considered learning the class of pattern languages and a class of regular expressions using MQs and CQs also based in edit distance.

Syntax or Semantics?

Most of the research within the field of GI has focused on learning syntax, and tends to omit any semantic information. However, do children learn their native language independent of meaning? What is the role of semantics in language learning? As linguistic and cognitive studies suggest, semantic and pragmatic information is also available to the child. Moreover, semantics and context seem to play an especially important role in the 2-word stage of child linguistic development. In this stage, context is important to understand the meaning of 2-word sentences and, thanks to the shared context, child and adult can communicate with each other although their grammars are different.

Taking into account that formal language learning is a hard problem, and taking into account the evidence of semantic learning in the first stages of natural language acquisition, we claim that semantic information can simplify the learning problem, and can make learning easier.

The first attempt to incorporate semantics in the field of GI has been made by Angluin and Becerra-Bonache in [START_REF] Angluin | Learning meaning before syntax[END_REF][START_REF] Angluin | Experiments with an algorithm to learn meaning before syntax[END_REF][START_REF] Angluin | A model of semantics and corrections in language learning[END_REF]. Inspired by the two-word stage of children's language acquisition, they proposed a computational model that takes into account semantics for language learning. In contrast to other approaches, their model does not rely on a complex syntactic mechanism; in that way, they try to represent the fact that, although the child and adult grammars are different, the semantic situation allows communication. This model also tries to give an account of the meaning-preserving corrections given to the child during the first stages of language acquisition (child's erroneous utterances are corrected by her parents based on the meaning that the child intends to express). This model has allowed them to investigate aspects of the roles of semantics and corrections in the process of learning to understand and speak a natural language.

How children acquire and use natural language is a fundamental problem that has attracted the attention of researchers for several decades. Besides obtaining a better understanding of natural language acquisition, interest in studying formal models of language learning stems also from the numerous practical applications of language learning by machines. In this paper we have proposed some ideas for simulating, in GI, the process of natural language acquisition. We claim that the simulation of that acquisition process might improve the methods in GI and, therefore, provide natural interfaces that may improve the efficiency and complexity of the mechanisms that we use in our everyday activities related with the information and the communication.

We have presented some ideas to improve models/techniques in GI by using as a model natural language acquisition. In that way, we have proposed that GI models use information that is relevant for natural language acquisition, that they take into account more aspects of real learning processes and use more natural tools. Thanks to these ideas, new challenging results in the field of GI can also be obtained. We have presented some works done in that direction; such works (bio-linguistically motivated) show that ideas coming from natural language acquisition studies can really improve results in the field of GI.

Therefore, ideas coming from linguistics can be useful in GI in order to obtain new perspectives of the problem and possible new solutions. But, of course, the theory of inferring formal grammars can also help to understand the process of language acquisition. GI can be relevant to understand language learning and could be a useful tool for any researcher interested in human language. Hence, the study of language learning from an interdisciplinary point of view is of great interest, not only to understand the learning mechanisms that underlie children's language acquisition, but also to develop computer systems that can recognize, understand and generate natural languages. In that way, such systems could also solve the problem of communication between machines and humans.


Lucie Daubigney

Olivier Pietquin

Single-trial P300 detection with Kalman filtering and SVMs

Brain Computer Interfaces (BCI) are systems enabling humans to communicate with machines through signals generated by the brain. Several kinds of signals can be envisioned as well as means to measure them. In this paper we are particularly interested in even-related brain potentials (ERP) and especially visually-evoked potential signals (P300) measured with surface electroencephalograms (EEG). When the human is stimulated with visual inputs, the P300 signals arise about 300 ms after the visual stimulus has been received. Yet, the EEG signal is often very noisy which makes the P300 detection hard. It is customary to use an average of several trials to enhance the P300 signal and reduce the random noise but this results in a lower bit rate of the interface. In this contribution, we propose a novel approach to P300 detection using Kalman filtering and SVMs. Experiments show that this method is a promising step toward single-trial detection of P300.

Introduction

Event-related brain potentials (ERP) are modifications of the electrical activity of the brain happening after some stimulation (e.g. visual or audio stimuli) [START_REF] Brazier | Evoked responses recorded from the depths of the human brain[END_REF]. They can serve in the framework of Brain-Computer Interfaces (BCI) [START_REF] Farwell | Talking off the top of your head : toward a mental prosthesis utilizing event-related brain potentials[END_REF], or in the analysis of brain diseases [START_REF] David | The P300: Where in the Brain Is It Produced and What Does It Tell Us?[END_REF]. There are several reasons for which the detection of P 300 is difficult among which, the Signal to Noise Ratio (SNR) is one of the most important. For this reason, it is very frequent that a synchronous averaging of several signals is used to enhance the SNR [START_REF] Sörnmo | EEG signal processing[END_REF], considering that the time evolution of EEG is similar for all ERPs. This assumption is actually false and ERPs can suffer from distorsions which are not only due to additive noise. For this reason, among other methods, Kalman filtering [START_REF] Kalman | A new approach to linear filtering and prediction problems[END_REF] has been studied to model in an online fashion the ERPs [START_REF] Vedel-Larsen | A comparative study between a simplified Kalman filter and sliding window averaging for single trial dynamical estimation of event-related potentials[END_REF][START_REF] Georgiadis | Single-trial dynamical estimation of event-related potentials: a Kalman filter-based approach[END_REF] and has proven to be an efficient method. The Kalman filter can be combined with a classifier for the P 300 to be automatically detected [START_REF] Ishita | Development of P300 Detection Algorithm for Brain Computer Interface in Single Trial[END_REF]. We propose here an original way to detect the P 300 by using the coefficients found by the Kalman filter to represent the P 300 as features for a Support Vector Machine (SVM).

Signal modeling

The EEG signal arises from the sum of several electrical activities produced simultaneously by the brain. An exemple is given Figure 1. The activity produced by a resting brain will be considered as noise (white, centered, gaussian) and the P300 wave as the signal of interest. Notice that on the Figure 1, the maximum amplitude is about 25µV . The maximum amplitude for a P300 wave is about 10µV . The signal to noise ratio is thus very small.

A parametric model of this signal is proposed under some assumptions and the parameters are adapted online according to observations of the brain activity. The signal is supposed to be C 1 , bounded, defined on a segment of R. Under these assumptions, the signal, y(t), can be approximated by a sum of Gaussians :

y(t) = α T φ t with α T = [α 1 , . . . , α p ] and φ T t = [exp( (t-t1) 2 2σ 2 1 ), • • • , exp( (t-tp) 2 σ 2 p )]
. On Figure 2 one can see the expected shape of a P300 wave, resulting of a sum of three Gaussians. -0. Fig. 2: Modeling of a P300 as a sum of three gaussians (abscissa in s, ordinate in normalized V ). The plain curve is the expected shape of the P300.

The α parameters have to be estimated by using the observations of the brain activity. In the following a method based on the Kalman filtering paradigm is proposed, after the works presented in [START_REF] Georgiadis | Single-trial dynamical estimation of event-related potentials: a Kalman filter-based approach[END_REF][START_REF] Vedel-Larsen | A comparative study between a simplified Kalman filter and sliding window averaging for single trial dynamical estimation of event-related potentials[END_REF]. After the α parameters are found they are used by a SVM to detect the P 300 in the signal.

Parameters estimation

The P300 wave is thus described by a generic model and the model parameters have to be adapted to detect P300 in the signal. As said before, the information used to learn the parameters come from noisy observations. This estimation problem is cast into the Kalman filtering paradigm. In this paradigm, the hidden state of a dynamic system has to be estimated online from noisy observations. This is done given that the evolution of the state is ruled by a known equation (evolution equation, Equation 1) and that the state is linked to the observations by another known equation (observation equation, Equation 2). These two equations form the so called state-space representation of the problem. In the general case, Equation 1x represents the state, F the process matrix and v is the 400 ESANN 2011 proceedings, European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning. Bruges (Belgium), 27-29 April 2011, i6doc.com publ., ISBN 978-2-87419-044-5. Available from http://www.i6doc.com/en/livre/?GCOI=28001100817300. process noise. In the Equation 2 which describes the observations, y represents the observations, H the matrix of observations and w observation noise.

x t+1 = F t x t + v t (1) y t+1 = H t x t + w t (2)
The Kalman filter computes the estimation of the state at time t by using the previous estimation, at time t -1 and the current observation. The estimation of the state is computed according to Equation 3.

xt|t = xt|t-1 + K t (ŷ t -y t ) (3) E xt|t -x t 2 |y 1 , . . . , y t (4)
In Equation 3, xt|t-1 = E[x t |Equation 1] = F t xt-1|t-1 represents the prediction obtained according to Equation 1 and xt-1|t-1 the estimation at the previous time and given that the process noise is considered as white and centered (E[v] = 0). ŷt = H t xt|t-1 is the prediction of the observation (E[y t |Equation 2]), computed according to Equation 2 and y t is the current observation. K t is the so-called Kalman gain. It is computed such as that the estimates minimise the expression 4 which is explained later in this section. First, the parameter estimation problem is cast into a state-space formulation. According to section 2 the signal can be approximated by a sum of Gaussians. The observation equation is thus Equation 5 with Φ a matrix of known Gaussians and w the observation noise (which reflects the fact that the real signal is not exactly a sum of Gaussians). An equation describing the evolution of the system is also needed. Here, the hidden state we are trying to estimate is the vector containing the parameters which we will note as α t . As the evolution of the parameters α over time is not well known (it depends on the P 300 evolution), a random walk is used (see Equation 6). The sample at the time t is the same as the one at the time t -1 plus a small random variation. The aim of the filter is to find the hidden parameters α i t (i from 0 to p, the number of Gaussians chosen to estimate the signal) from observations. The bigger the number of observations, the better the estimation of the parameters. For an infinite number of observations, the estimated parameters tends towards the actual ones.

y t = α T t Φ + w t (5) α t = α t-1 + v t (6)
Three steps are needed to compute the gain. The a priori estimation of the covariance of the error between the hidden variable α t and its estimation αt is computed according to the Equation 7, Q being the matrix of covariance of the process noise whose expression is E vv T . This Q matrix takes into accounts the small variations between the P300 waves. Q is usually chosen equal to ηP t-1|t-1 , η depending of the differences between the P300. Then the gain 1 is computed using the Equation 8, with σ 2 wi , variance of the observation noise, which represents the accepted gap between the estimated parameters and the real parameters. This expression is determined to minimize the expression given in 4. Finally the a posteriori estimation of the covariance of the error is computed using Equation 9.

P t|t-1 = P t-1|t-1 + Q (7) K t = P t|t-1 φ T t φ t • P t|t-1 • φ T t + σ 2 wi ( 8
)
P t|t = (Id -K t φ t ) • P t|t-1 (9)
The Kalman filter is convenient to use in that case because the computation of the gain does not require a lot of resources. The filter can be used "online" to estimate the signal from the observations. Once a model of a signal without noise is obtained (like in [START_REF] Vedel-Larsen | A comparative study between a simplified Kalman filter and sliding window averaging for single trial dynamical estimation of event-related potentials[END_REF][START_REF] Georgiadis | Single-trial dynamical estimation of event-related potentials: a Kalman filter-based approach[END_REF]), it can be used to detect if the signal contains or not a P300 wave.

Detection

The P300 wave is created by the brain after it has been submitted at a random time to an expected visual stimulus among other stimuli. The target stimuli is chosen before the beginning of the experiment. The aim is thus to determine in the EEG signal if the target stimulus provoked a P300. The times at which the stimuli had been displayed are known but the moment at which the P300 may appear is not necessarily known precisely. This moment may vary by several milli secondes depending on the subject (gender, age, tiredness, etc). The P300 wave is supposed to last around 400ms.

An automatic detection of P300 waves is made using the result of the Kalman filtering by a SVM. Here we want to classify the data in two categories : P 300 or noise. The SVM is first trained with two sets of data in a supervised manner, then new data are submitted to the classifier to be classified. The originality of this work is to provide the estimated parameters α to the SVM classifier.

Experiment

Data

The processing of the data, the estimation of the signal and the classification, have been tested with two different datasets like in [START_REF] Vedel-Larsen | A comparative study between a simplified Kalman filter and sliding window averaging for single trial dynamical estimation of event-related potentials[END_REF] : a set of artificial data and a set of real EEG signals. The artificial data is a constructed P300 wave added to real background noise got from a human brain. This solution has fist been tested to be sure that the set of data contains P300 and avoid problem of generating P300.

The real data comes from an experiment led with a human watching at several pictures displayed one after another. Among the displayed pictures, the subject has to find the target picture (s)he was asked to recognize. This experiment

402

ESANN 2011 proceedings, European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning. Bruges (Belgium), 27-29 April 2011, i6doc.com publ., ISBN 978-2-87419-044-5. Available from http://www.i6doc.com/en/livre/?GCOI=28001100817300.

is supposed to make the brain generate P300 waves since the subject does not know at which moment the picture will be displayed.

Results

Each part of the data processing chain has been tested separately in both cases i.e. with artificial and real data. The Kalman filter has been fed with data containing a P300 wave. Examples of the estimated signals are provided on Figure 3. The shape of the P300 can be recognized in the estimated signal.

Then, the accuracy of the classifier is tested. It has first to be trained with exemples from both classes which are to be recognized (P300 vs noise). The set of examples representing the first class is composed of α parameters from sections of observations which most likely contain a P300 wave. Each section which more likely contains a P300 is made of samples collected from the display of the target stimulus to several hundreds of ms (here 600ms) after the display. The set of examples representing the second class contains α parameters computed from noise. Fifty sets of α parameters selected by hands have been used in each category. The performance of the classifier alone obtained with cross-validation are the following : for the artificial P300 the rate of 90% of success is reached and for real P300 the rate of 87% is reached.

The accuracy has been measured on a 60s signal containing periodic P300, with a period equal to 1.8s. Sets of α parameters were computed periodically for a 600ms window, with a period equal to 200ms. We thus know here, by construction, that the P300 appears 300ms after the target stimulus. The results are given Figure 4. They are promising since only the sets of α computed for a portion of signal starting 300ms before the P300 were detected by the classifier as containing a P300. The number of false positives is kept quite low while the

403

ESANN 2011 proceedings, European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning. Bruges (Belgium), 27-29 April 2011, i6doc.com publ., ISBN 978-2-87419-044-5. Available from http://www.i6doc.com/en/livre/?GCOI=28001100817300. true positives are fairly numerous. Similar results have been obtained with the X X X X X X X X X X Signal Classifier detect a P300 does not detect a P300 contains a P300 88% 12% does not contain aP300 1% 99% Fig. 4: Results of the experiments obtained with artificial data real data although it is much difficult to assess since the exact time of appearance of P300 in the signal is unknown. Particularly, a true negatives rate of 98.5% could be obtained. Yet, true positives were difficult to assess but the method worked in more than 50% of the cases where a P300 was expected.

Conclusion

This new approach for the detection of P300 gave encouraging results since the detection is only made in a single trial. But some improvements could be brought by leading more tests to determine exactly why experiments on real data do not give the same results as those got with the artificial data. Some tests could be ran about the reliability of generating the P300 waves. Maybe the assumption we made concerning the shape of the P300 as a sum of gaussians is not exactly true either. The results obtained could be compared with the ones of the speller which is the reference experiment ( [START_REF] Farwell | Talking off the top of your head : toward a mental prosthesis utilizing event-related brain potentials[END_REF]) to eliminate some causes of problem.

Fig. 1 :

 1 Fig. 1: Raw example of the electrical activity of the brain captured on a surface EEG (abscissa in s, ordinate in µV ).

Fig. 3 :

 3 Fig.3: Test of the Kalman filter. The signals have been normalized to be between -1 and 1. The curves have been obtained with the following initial values : σ 2 v0 = 1, η = 1.10 -5 , λ = 1 and α take the values obtained in a previous estimation. The dotted curve gives the observation of a raw EEG after a passband filter (0 to 20 Hz), then estimated with Kalman filter (curve with crosses). The shape of the P300 is reminded on the left figure.

The initial value, for a normalized signal are : P 0 = λId with λ = 1, σw 0 = 10 -3 , α 0 = 0 or α 0 fixed with the values of a previous estimation.401 ESANN

proceedings, European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning. Bruges (Belgium), 27-29 April 2011, i6doc.com publ., ISBN 978-2-87419-044-5. Available from http://www.i6doc.com/en/livre/?GCOI=28001100817300.

ESANN 2011 proceedings, European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning. Bruges (Belgium), 27-29 April 2011, i6doc.com publ., ISBN 978-2-87419-044-5. Available from http://www.i6doc.com/en/livre/?GCOI=28001100817300.