Guy Perrier
email: guy.perrier@loria.fr

An Interaction Grammar of interrogative and relative clauses in French

Keywords: Syntax, grammatical formalism, tree description, polarity, interrogative clause, relative clause, interaction grammar

We present a fairly complete grammar of interrogative and relative clauses in French, written in the formalism of Interaction Grammars. Interaction Grammars combine two key ideas: a grammar is viewed as a constraint system which is expressed through the notion of tree description, and the resource sensitivity of natural languages is used as a syntactic composition principle by means of a system of polarities.

Introduction

This article is a contribution to the construction of formal grammars from linguistic knowledge. This task is motivated by both applicative and scientific considerations. From an applicative point of view, it is essential for NLP systems requiring a fine and complete syntactic analysis of natural languages. From a scientific point of view, formalization can be very helpful for linguists, who aim at capturing the complexity of a natural languages with relevant generalizations. In this task, one of the most difficult challenges is to get the largest possible coverage of these formal grammars.

Regarding this challenge, relative and interrogative clauses in French are a good test because they illustrate the complexity of natural languages in a very obvious manner. They give rise to interference between several phenomena, which are present in both types of clauses and justify a common study. In the following, a clause which is a relative clause or an interrogative clause is called a wh-clause. In this paper, we have highlighted four phenomena occurring with wh-clauses:

• Wh-extraction: a particular constituent is extracted from its canonical position in the whclause to be put in front of it: if the clause is interrogative, it contains the requested information and if the clause is relative, it contains a reference to the antecedent of the relative clause; in both cases, they are represented with grammatical words, which we call wh-words. The difficulty lies in the fact that extraction can occur through a chain of a possibly indeterminate number of embedded clauses. This gives rise to an unbounded dependency which is subject to special constraints, called island constraints.

• Pied-piping: in some cases, wh-words drag a complex phrase along with them in the extraction movement. Another unbounded dependency may be generated from the fact the wh-word can be embedded less or more deeply in the extracted phrase.

• Subject inversion: contrary to canonical constructions of clauses where the subject precedes the verb, wh-clauses allow subject inversion under some conditions. These conditions depend on various factors.

• Interrogative and declarative marking: in French, relative clauses and interrogative clauses often use the same wh-words but they differ in the fact that the first ones are marked declaratively, whereas the second ones are marked interrogatively. If we consider only written texts, there are four main ways of marking clauses interrogatively or declaratively: the punctuation, the position of subject clitics with respect to the verb, the construction of clauses as objects of verbs expecting questions, and special terms like est-ce que.

If we aim at capturing all these phenomena most fairly, we need a rich formalism but which is at the same time simple enough to keep the formal representations readable. We have chosen the formalism of Interaction Grammar (IG) [START_REF] Guillaume | Interaction Grammars. Research on Language and Computation[END_REF], for two main reasons:

• The basic objects of the formalism are pieces of underspecified syntactic trees, which can combine very freely by superposition. Such a flexibility is used at the same time in the construction of modular grammars and then in the process of syntactic composition. In our application, underspecification will be used to represent unbounded dependencies related to wh-extraction and pied-piping.

• The resource sensitivity of natural languages is used as a principle of syntactic composition under the form of a system of polarities. In this way, syntactic composition consists in superposing pieces of syntactic trees under the control of polarities with the goal of saturating them. The use of polarities for managing the interrogative and declarative marking of clauses is an elegant illustration of this principle.

In section 2, we give an informal presentation of IG with the help of an example. Then, we show how to build an IG of wh-clauses focusing on four phenomena: wh-extraction (section 3.1), pied-piping (section 3.2), subject inversion (section 3.3), interrogative and declarative marking (section 3.4). We end with an evaluation of the grammar.

Presentation of Interaction Grammars

Tree descriptions and polarities

The basic objects of IG [START_REF] Guillaume | Interaction Grammars. Research on Language and Computation[END_REF] are tree descriptions, which can be viewed as partially specified syntactic trees. Their nodes represent syntactic constituents and they are labelled with feature structures representing the morpho-syntactic properties of constituents. The nodes are structured by two kinds of relations: dominance and precedence. Both can be underspecified.

Tree descriptions combine by superposition under the constraints of polarities expressing their saturation state. Polarities are attached to features, so that features are triples (name, polarity, value), which are called polarized features. Tree descriptions labelled with polarized feature structures are called polarized tree descriptions (PTD).

The superposition of two PTDs is realized by merging some of their nodes. When two nodes merge, their feature structures are composed according to an operation, which reduces to classical unification if we forget polarities.

There are 5 polarities: neutral (=), positive (→), negative (←), virtual (∼), saturated (↔). Polarities are composed according to an operation, denoted ⊕, defined by the following table .

⊕ = → ← ∼ ↔ = = → ↔ → ← ↔ ← ∼ → ← ∼ ↔ ↔ ↔
In this table, an empty entry means that the corresponding polarities fail to be composed. The neutral polarity applies to features that behave as non consumable resources, agreement features for instance. Other polarities interact together with the aim of being saturated. Thus, according to the table, there are two kinds of interactions:

• Linear interactions: a linear interaction occurs between exactly one positive feature f → v 1 and one negative feature f ← v 2 to combine in a saturated feature f ↔ v 1 ∧ v 21 ; in this way, both features become saturated. Then, they can only combine with virtual features; they cannot combine any more with another positive, negative or saturated feature. This mainly expresses interaction between predicates and arguments, in which one predicate requires exactly one argument for each function.

• Non linear interactions: a non linear interaction occurs between one saturated feature f ↔ v and n (n being possibly equal to 0) virtual features

f ∼ v 1 , . . . , f ∼ v n to saturate these virtual fea- tures into a feature f ↔ v ∧ v 1 • • • ∧ v n .
This interaction can be viewed as an absorption of any number of virtual polarities by a saturated polarity. It mainly models two types of interactions: context requirements and applications of modifiers to constituents. 22The system of polarities presented here is not the only possible one. It is important to understand that the polarity system is a parameter of any IG. For instance, the system used in the initial presentation of IG [START_REF] Guillaume | Interaction Grammars. Research on Language and Computation[END_REF] differs from the present system on one point: neutral features have the property of absorbing virtual features.

Syntactic composition and parsing

In IG, a syntactic composition process is defined as a sequence of PTD superpositions controlled by interactions between polarities. One superposition is composed of elementary operations of node merging. When two nodes merge, their feature structures are composed, which can give rise to some interactions between their polarized features.

A particular IG is defined by a finite set of PTDs, the elementary PTDs (EPTDs) of the grammar. In practice, the actual IGs are totally lexicalized: each EPTD has a special node that is linked to a word of the language; this node is unique and it is called the anchor of the EPTD.

All valid syntactic trees generated from the grammar are the saturated trees resulting from a syntactic composition process of a finite set of EPTDs. A saturated tree is a PTD that is a completely specified tree in which all polarities are neutral or saturated The language generated by the grammar is the set of the yields of the valid syntactic trees, that is the sequences of words attached to the leaves of the trees.

To parse a sentence with a particular IG, we first have to select an EPTD for each word of the sentence: the anchor of the PTD must be linked with the corresponding word. Then, we have to perform the syntactic composition of the selected EPTDs to find a valid syntactic tree, the yield of which is the parsed sentence.

The parsing problem for IG in its whole generality is NP-hard, which can be shown with an encoding of

X lequel X cat <-> np X funct <-> obj V1 cat ~v OBJ1 cat -> np funct <-obj S1 cat ~s mood ~ind Jean cat <-> np funct <-> <1>? gen = m num = sg pers = 3 NP1 cat -> np funct <-<1>? gen = m num = sg pers = 3 OBJ2 cat <-np funct -> obj V2 cat <-> v mood <-> ind num = sg pers = 3 tense = pres connaît cat <-> v mood <-> ind num = sg pers = 3 tense = pres SUBJ1 cat <-np funct -> subj num = sg pers = 3 S2 cat -> s mood <-> ind tense = pres S3 cat ~s mood ~ind V3 cat ~v SUBJ2 cat ~np funct ~subj gen = m num = sg pers = 3 il cat <-> clit V4 cat ~v mood ~ind ? X cat <-> punct X S4 cat <-s mood ~ind
Fig. 1: EPTDs selected from an IG for sentence 1 the Intuitionistic Implicative fragment of linear logic. Nevertheless, grammars aiming at modelling real natural languages allow the use of original methods for parsing, which are based on polarities and make parsing tractable. This is not the concern of this article and the reader can refer to [START_REF] Bonfante | Analyse syntaxique électrostatique[END_REF][START_REF] Bonfante | Polarization and abstraction of grammatical formalisms as methods for lexical disambiguation[END_REF][START_REF] Bonfante | Dependency constraints for lexical disambiguation[END_REF] for an in-depth study of parsing with IG.

An example

Consider the following sentence to parse with an IG: It is composed of three constituents: the verbal kernel, the subject and the object of the verb, which are respectively represented by nodes V 2 , SU BJ 1 and OBJ 2 . The basic constituent of the verbal kernel is the bare verb, the anchor of the EPTD, represented with a double frame. In SU BJ 1 , the negative feature cat ← np and the positive feature f unct → subj mean that connaît expects a noun phrase to provide it with the subject function. Underspecified strict precedence between the three nodes is represented with dashed arrows.

The EPTD associated with il represents its construction as a subject clitic pronoun, put just after the verb as a duplication of the actual subject to make the clause interrogative. Node V 4 represents the bare verb, which is concatenated with il to constitute the cliticized verb V 3 . The cat features of nodes V 3 and V 4 are virtual to express that il acts as a modifier of an actual verb: nodes V 3 and V 4 have to merge with actual verbs. Nodes S 3 and SU BJ 2 represent a required context: a finite clause with a third person singular male subject. This is expressed with virtual features.

The EPTD associated with lequel represents its construction as an object interrogative pronoun. The interrogative clause is represented by the node S 1 . The pronoun lequel is put in front of the clause to represent an extracted object 3 and the canonical position of the object is occupied by a trace, the node OBJ1 which is represented with a dashed box to express that the trace has an empty phonological form.

V1.V2.V3 cat <-> v mood <-> ind num = sg pers = 3 tense = pres connait.V4 cat <-> v mood <-> ind num = sg pers = 3 tense = pres il cat <-> clit OBJ1.OBJ2 cat <-> np funct <-> obj ? cat <-> punct S1.S2.S3.S4 cat <-> s mood <-> ind tense = pres lequel cat <-> np funct <-> obj NP1.SUBJ1.SUBJ2 cat <-> np funct <-> subj gen = m num = sg pers = 3 Jean cat <-> np funct <-> subj gen = m num = sg pers = 3
The EPTD associated with Jean contains two funct features with an undetermined value, which is expressed with a question mark. It means that the noun phrase can receive any syntactic function in the sentence. The index < 1 > that is put before the value indicates that the funct features of nodes NP1 and Jean share the same value.

Punctuation signs are considered as ordinary words and they are also associated with EPTDs. So, the question mark is associated with an EPTD, the root of which represents the interrogative sentence.

The parsing succeeds because the syntactic composition of the EPTDs from figure 1 ends with the valid syntactic tree given by figure 2. On the figure, the head of the box representing each node contains the names of the nodes from the initial EPTDs that were merged into this node. The parsing of the sentence is composed of 9 mergings, including themselves 5 linear interactions and 12 non linear interactions. Among the 12 non linear interactions, only one realizes the action of a modifier; the others realize context requirements.

3 Modelling interrogative and relative clauses in French

Wh-extraction

Wh-extraction is a common property to relative and interrogative clauses in French: wh-words appear at the beginning of the clause and they play the role of a constituent that is lacking in the clause. The empty position in the clause is usually marked with a trace.

( In sentence 2, the trace is indicated with a symbol. The wh-word is bold. Contrary to sentence 1, in sentence 2, the trace is located in a clause which is not the interrogative clause introduced by the wh-word but an embedded object clause. The clause aller is an infinitive clause, which is included in the finite clause que Marie veut aller , which is itself included in the interrogative clause où Pierre pense-t-il que Marie veut aller . The number of embedded clauses between the trace and the wh-word is undetermined, hence an unbounded dependency between the wh-word and the verb that has the trace as its complement.

X où X cat <-> pp X funct <-> loc S5 cat ~s mood ~cond | ind OBJ3 cat ~s funct ~obj V5 cat ~v OBJ4 cat ~s funct ~obj mood ~cond | ind | inf | subj cat = s funct = obj X PREP1 X cat <-> prep NP2 X cat <-> np X funct <-> loc X PP1 cat --> pp funct <--loc V6 cat ~v
Fig. 3: EPTD for the interrogative pronoun où IG uses an underspecified dominance relation to model this unbounded dependency. Figure 3 shows the EPTD used in sentence 2 to represent the interrogative pronoun où. Node OBJ3 represents the object clause that is immediately included in the main clause, que Marie veut aller in our example. Node OBJ4 represents the last embedded object clause, which has the trace as an immediate constituent, the infinitive clause aller in our example. There is an underspecified dominance relation from OBJ3 to OBJ4 , in order to express that there is an undetermined number of object clauses inserted between them. Dominance relations must be understood in a large sense: OBJ3 may merge with OBJ4.

The underspecified dominance relation is represented in figure 3 with a dashed vertical line. The line is labelled with two neutral features cat = s and funct = obj, which mean that all nodes dominated by OBJ3 and dominating OBJ4 in a large sense, must be equipped with both features. The features labelling dominance relations interact with the feature structures of the concerned nodes by unification. This mechanism models the fact that all constituents included in the main interrogative clause and containing the trace are object clauses, which is a way of implementing island constraints. Lexical Functional Grammar (LFG) [START_REF] Bresnan | Lexical-Functional Syntax[END_REF] uses a similar form of constraint on underspecified dominance: functional uncertainty.

In figure 3, the trace is represented by the subtree rooted at node PP1. This node is labelled with a positive feature cat → pp and a negative feature funct ← loc. It means that it provides a prepositional phrase which expects to receive a locative function. Both polarized features will be saturated by the verb aller.

Pied-piping

Pied-piping represents the ability of wh-words to drag complex phrases along with them when brought to the front of interrogative or relative clauses. Here is an example of pied-piping in which the extracted phrase is put between square brackets. In sentence 3, the wh-word is embedded more or less deeply in the extracted phrase, via a chain of noun complements introduced by the preposition de. Besides extraction, such a construction is a second source of unbounded dependency and IG also uses an underspecified dominance relation to model it. Figure 4 gives an example of EPTD associated with the interrogative pronoun qui used with pied-piping. The only change with respect to figure 3 lies in the subtree rooted at node PP2 representing the complex extracted phrase. In sentence 3, PP2 represents dans la maison du père de qui. Anchor qui is embedded in a chain of noun complements introduced by the preposition de. Nodes PP4 and PP5 represent the extremities of the chain and the underspecified dominance relation between them means that the number of elements of the chain is undetermined. In particular, it can be null when PP5 is identified with PP4. The features labelling the dominance relation express a constraint on the nodes constituting the chain. These nodes must be only nouns, noun phrases or prepositional phrases with either no syntactic function or complements introduced by the preposition de.

X PP2 X cat <-pp X funct -> loc NP3 X cat ~np X S6 cat ~s mood ~cond | ind OBJ3 cat ~s funct ~obj V5 cat ~v OBJ4 cat ~s funct ~obj mood ~cond | ind | inf | subj cat = s funct = obj qui X cat -> np X funct <-deobj X PP5 cat ~pp funct ~deobj PP4 X cat ~pp X funct ~deobj X cat = n | np | pp funct = deobj | void V6 cat ~v PP3 cat -> pp funct <-loc X PREP1 X cat <-> prep NP2 X cat <-> np X funct <-> loc X
Fig. 4: EPTD for the interrogative pronoun qui

Subject inversion

Subject inversion is allowed in interrogative and relative clauses under some conditions. For the relative clauses, inversion is usually possible, but there is a case in which it is strictly forbidden: when there is a possible confusion between the inverted subject and an object of the verb. For the interrogative clauses, besides the presence of an object for the verb, some interrogative words prevent subject inversion while others force it. In the first class, there is pourquoi (why) and in the second case, there is que (what). Others like où (where) are unconcerned with the subject-verb order. 5 shows how subject inversion in sentence 4 is modeled in an EPTD associated with the interrogative pronoun que. Node SUBJ3 represents the trace of the subject at the initial position just before the verbal kernel represented by node V7. Node SUBJ4 represents an expected noun phrase just after the verbal kernel, to which the EPTD gives the subject function. The interest of this way of representing subject inversion is that the same EPTD for a transitive verb is used in the canonical construction and the inverted construction of the subject-verb order. The doubling of the number of EPTDs for transitive verbs in the grammar is avoided this way.

(4) Que what fait is doing Marie Marie ? ? 'What is Marie doing?' X que X cat <-> np X funct <-> obj SUBJ3 cat -> np funct <-subj V7 cat ~v SUBJ4 cat <-np funct -> subj OBJ5 cat -> np funct <-obj S7 cat ~s mood ~cond | ind

Declarative and interrogative marking

Nodes representing clauses are equipped with a typ feature, which can take three values, decl, inter or inj, according to the type of the clause: declarative, interrogative or injunctive. The feature is polarized and since grammars are lexicalized, there is a subtle interaction between words to saturate them.

The interaction is especially complex for interrogative clauses. In direct interrogations, sentence 2 for instance, the question mark brings a negative feature typ ← inter and in indirect interrogations, the same feature is brought by the main verb which expects a question.

In direct interrogations, like sentence 2, if there is a subject clitic put just after the main verb, this clitic brings the positive feature typ → inter. Otherwise, the positive feature is brought by the wh-word.

The declarative marking of relative clauses is simpler: the relative pronoun brings the feature typ ↔ decl to the relative clause.

This way of marking interrogative and declarative clauses is not the only possible with IG. Its system of polarities is rich and flexible enough to provide other solutions.

Organization of the grammar

In previous sections, we focused on four main aspects of the grammar of the interrogative and relative clauses in French but the whole grammar is more complex and its implementation is a real challenge.

For this, we used the XMG tool [START_REF] Duchier | XMG : Un compilateur de méta-grammaires extensible[END_REF]. XMG provides a high level language dedicated to grammar description. A grammar is designed as a set of classes, each class defining a set of PTDs. The initial classes are composed into complex classes by means of two operations: conjunction and disjunction. Classes are ranked

Evaluation and comparison with other works

The evaluation of IG W h has two aspects:

• its precision measures the extent to which all parse trees generated from IG W h reflect valid constructions in French;

• its recall measures the extent to which all constructions with interrogative or relative clauses in French are captured by IG W h .

The use of treebanks on large real corpora with a classical F-measure is not well suited to such an evaluation: even if they are very large, their grammatical coverage of relative and interrogative clauses is too limited and they only include positive sentences, when ungrammatical sentences are necessary to spot overgeneration. Finally, the construction of such treebanks is very costly and for French, they are too limited both in number and size. The least costly way of evaluating IG W h is to use it for parsing a test suite of grammatical and ungrammatical sentences illustrating most rules of the French grammar related to interrogative and relative clauses. Unfortunately, there exists no test suite satisfying this specification. The TSNLP [START_REF] Lehmann | tsnlp -Test Suites for Natural Language Processing[END_REF] contains no relative clause and only direct interrogative sentences covering the grammar of these sentences very partially. The EUROTRA test suite [START_REF] Daille | L'analyse du français dans le projet EUROTRA[END_REF] contains relative clauses but its coverage is limited and it does not contain any ungrammatical sentence.

We have built our own test suite, consisting in a hundred grammatical sentences and a hundred ungrammatical sentences. These sentences cover most syntactic phenomena related to relative and interrogative clauses. Of course, these sentences need a complete grammar to be parsed but, as we focus on relative and interrogative clauses, we take care to choose only simple rules with regard to other phenomena. For the parsing, we used LEOPAR4 , which is a parser devoted to IG. The hundred grammatical sentences were parsed successfully, all parse trees were verified manually and the hundred ungrammatical sentences were rejected by the parser.

Another way of evaluating our grammar is to compare it with other existing grammars of interrogative and relative clauses in French. Unfortunately, there are very few works about this question. Anne Abeillé [START_REF] Abeillé | Une grammaire électronique du français[END_REF] has developed a grammar of French in the formalism of Tree Adjoining Grammar (TAG). This grammar covers relative and interrogative clauses. Like our grammar, it is lexicalized, but the main difference is that all syntactic constructions related to wh-clauses are attached to the head verb of these clauses. From a computational point of view, this is an important drawback because it inflates the number of elementary trees associated with verbs, which makes the selection of relevant trees more difficult. Even if it fits on with the locality principle5 , such a feature is determined by the rigidity of the operation of syntactic composition, adjunction, which does not allow for flexibility about the way of attaching syntactic information to words. Nevertheless, the attachment of the syntactic constructions related to wh-clauses to verbs presents one advantage over the attachment to wh-words: the absence of a direct objet just after the head verb of the wh-clause can be made explicit in the elementary tree attached to this verb, so that subject inversion is completely controlled. Wh-extraction, interrogative and declarative marking are expressed with the TAG machinery: the mechanism of adjunction combined with an important system of control features. Another illustration of the limited expressivity of adjunction is the inability to represent the extraction of noun complements. Finally, a point remains unclear: the modelling of unbounded dependencies generated by pied-piping.

Other formalisms, such as HPSG [START_REF] Sag | Syntactic Theory: a Formal Introduction[END_REF] and LFG [START_REF] Bresnan | Lexical-Functional Syntax[END_REF] propose solutions for relative and interrogative clauses and other languages than French but in this article, we have stressed the combination of four aspects, which is very specific to French, and an exhaustive comparison would be lengthy for this article.

( 1 )Figure 1

 11 Figure1represents a possible selection from the grammar for the words of sentence 1. The EPTD associated with connaît represents a syntactic construction where the transitive verb is used in the active voice. Node S 2 represents the clause with connaît as its head. It is composed of three constituents: the verbal kernel, the subject and the object of the verb, which are respectively represented by nodes V 2 , SU BJ 1 and OBJ 2 . The basic constituent of the verbal kernel is the bare verb, the anchor of the EPTD, represented with a double frame. In SU BJ 1 , the negative feature cat ← np and the positive feature f unct → subj mean that connaît expects a noun phrase to provide it with the subject function. Underspecified strict precedence between the three nodes is represented with dashed arrows.The EPTD associated with il represents its construction as a subject clitic pronoun, put just after the verb as a duplication of the actual subject to make the clause interrogative. Node V 4 represents the bare verb, which is concatenated with il to constitute the cliticized verb V 3 . The cat features of nodes V 3 and V 4 are virtual to express that il acts as a modifier of an actual verb: nodes V 3 and V 4 have to merge with actual verbs. Nodes S 3 and SU BJ 2 represent a required context: a finite clause with a third person singular male subject. This is expressed with virtual features.The EPTD associated with lequel represents its construction as an object interrogative pronoun. The interrogative clause is represented by the node S 1 . The

Fig. 2 :

 2 Fig. 2: Parse tree of sentence 1

  house of whom father does Pierre believe that Marie wants to go ?'

Fig. 5 :

 5 Fig. 5: EPTD for the interrogative pronoun que

Figure

  Figure5shows how subject inversion in sentence 4 is modeled in an EPTD associated with the interrogative pronoun que. Node SUBJ3 represents the trace of the subject at the initial position just before the verbal kernel represented by node V7. Node SUBJ4 represents an expected noun phrase just after the verbal kernel, to which the EPTD gives the subject function. The interest of this way of representing subject inversion is that the same EPTD for a transitive verb is

)

  Où where

		Pierre	pense-t-il	que	Marie
		Pierre	does he believe	that	Marie
	veut	aller	?
	wants	to go	?
	'Where does Pierre believe that Marie wants to go ?'

  Organization of the grammar by family. Figure6shows the architecture of our IG of interrogative and relative clauses in French. We call it IG W h . Ovals represent families and an arrow from an oval to another one means that some classes from the first family are used in the definition of classes of the second family. Some classes are distinguished as terminal classes and they are compiled by XMG into a set of EPTD constituting an IG usable for automated parsing. IG W h is composed of 40 classes. Among them, 16 terminal classes are distributed in 4 relative classes and 12 interrogative classes. These terminal classes are compiled into 77 EPTDs anchored with relative pronouns and 295 EPTDs anchored with interrogative pronouns and determiners.

	Determiners	Pronouns
	Wh-words
		StandardPronouns
	StandardDeterminers
	InterrogativeWords	RelativeWords
	Fig. 6:

Feature values v 1 and v

are disjunctions of atoms and v 1 ∧v 2 represents their conjunction.

If we look at the polarity composition table carefully, we remark that a virtual feature can also be absorbed by a positive or a negative feature but these features must then combine with a dual feature to become saturated. Apart from the order, this leads to the same result as a linear interaction followed by a non linear interaction. From this consideration, it is logical to extend the notion of non linear interaction to any interaction between a virtual feature and a positive or negative feature.

The crosses on the left of the box representing lequel mark that the node is the leftmost daughter of node S1.

http://www.loria.fr/equipes/calligramme/leopar

A predicate and its arguments must be present in the same elementary tree.


Arthur Tenenhaus Supélec
email: arthur.tenenhaus@supelec.fr

Kernel PLS path modelling

Keywords: Multi-block data analysis, Structural Equation Modelling, PLS path modelling, Kernel methods

 which will be presented during the PLS'09 conference.

Introduction

Throughout this paper ܺ ଵ , ܺ ଶ , … , ܺ are matrices with columns defined by centered variables observed on the same set of n individuals and ܭ ଵ , ܭ ଶ , … , ܭ the associated kernel matrices. Let us note  the number of variables for the block ܺ . We are interested in studying the relation between ܬ blocks of variables ܺ ଵ , ܺ ଶ , … , ܺ even though those data sets live in different spaces. We achieve this by projecting the ܬ blocks onto ܬ separate directions specified by vector ܽ ଵ , ܽ ଶ , … , ܽ , to obtain ܬ univariate variables on which "link" (such as covariance) can be computed easily. In this paper is presented a kernel version of a companion paper entitled "A criterion based PLS approach to structural equation modelling" [START_REF] Tenenhaus | A criterion based PLS approach to structural equation modelling[END_REF] which will be presented during the PLS'09 conference. The paper is organized as follows: the first part briefly introduces the primal formulation of the proposed method and the second part is devoted to its dual formulation.

The general optimization problem (primal form)

In this paper, the following general problem is considered:

൛ܽ ଵ , ܽ ଶ , … , ܽ ൟ = argmax భ , మ ,…, ܿ ݃ ቀܿݒ൫ܺ ܽ , ܺ ܽ ൯ቁ ୀଵ ୀଵ subject to the constraints: : ൫1 -߬ ൯ݎܽݒ൫ܺ ܽ ൯ + ߬ ฮܽ ฮ ଶ = 1, j =1, …, J (1)
where ݃ሺݔሻ = ݔ (Horst Scheme), ݃ሺݔሻ = ݔ ଶ (factorial scheme) or ݃ሺݔሻ = |ݔ| (centroïd scheme).

The regularisation parameters ߬ ∈ ሾ0, 1ሿ, j =1, …, J control the stability of the solution (specifically useful in a high dimensional block context) and interpolate smoothly between the maximisation of the covariance (all ߬ ݏ ᇱ = 1) and the maximisation of the correlation (all ߬ ݏ ᇱ = 0). The ܬ × ܬ design matrix ሺܥሻ = ܿ equals to 1 if the blocks i X and j X are connected and to 0 otherwise allows to immediatly extend the multiblock data analysis framework to the structural equation modelling one by limiting the sommation to connected blocks. For sake of simplicity, in this part of the paper, we focus our presentation on the Horst scheme. Applying the Lagrangian multiplier technique to the optimization of (1) gives us ܬ stationary equations:

ܽ = 1 ඥܼ ᇱ ܺ ܯ ିଵ ܺ ᇱ ܼ ൮ሺ1 -߬ ሻ 1 ݊ ܺ ᇱ ܺ + ߬ ܫ ᇣᇧᇧᇧᇧᇧᇧᇤᇧᇧᇧᇧᇧᇧᇥ ெ ൲ ିଵ ܺ ᇱ ܿ ܺ ܽ ୀଵ ᇣᇧ ᇧᇤᇧ ᇧᇥ , ݅ = 1, … , ܬ
It is noteworthy that ܯ is well-conditionned (even in high dimensional block(s) context) since the empirical covariance matrices ଵ ܺ ᇱ ܺ ݅ = 1, … , ܬ are shrunk gradually towards the identity matrices and are singular and thus invertible. To solve this optimization problem is applied an iterative "PLS style" algorithm based on the Wold procedure [START_REF] Wold | Soft Modeling: The Basic Design and Some Extensions[END_REF] which is monotonically convergent that means that the bounded criterion to be maximized is increasing at each step of the procedure [START_REF] Hanafi | PLS Path modelling: computation of latent variables with the estimation mode B[END_REF]. However, it is still remain difficult to apply such a Wold algorithm in a high dimensional block context due to the inversion of matrices ܯ of dimension  ×  , ݅ = 1, … , ܬ and we propose in the next section to reformulate this algorithm in its dual form leading to the Kernel PLS path modelling.

Kernel PLS path modelling

Let us assume that ܽ can be expressed as a linear combination of the observations of block ܺ (which is always possible). Throughout this section let us note ܽ = ܺ ᇱ ߙ and ܭ = ܺ ܺ ᇱ the matrix of inner product between pairs of observations of block ܺ (Gram matrix). We consider also the QRdecomposition of the matrix ܺ ᇱ = ܳ ܴ where ܳ is an orthonormal matrix and ܴ a rank൫ܺ ൯ × ݊ upper triangular matrix. This gives the following decomposition for the kernel matrix ܭ = ܴ ᇱ ܴ . As suggested by [START_REF] Bach | Kernel Independent Component Analysis[END_REF][START_REF] Shawe-Taylor | Kernel Methods for Pattern Analysis[END_REF], an incomplete cholesky decomposition of ܭ is used to obtain ܴ . Now the primal formulation of the general optimisation problem described previously can be formulated in its dual form as follows:

൛ߙ ଵ , ߙ ଶ , … , ߙ ൟ = argmax ఈ భ ,ఈ మ ,…,ఈ ܿ ݃ ቀܿݒ൫ܺ ܺ ᇱ ߙ , ܺ ܺ ᇱ ߙ ൯ቁ ୀଵ ୀଵ subject to the constraints: : ൫1 -߬ ൯ݎܽݒ൫ܺ ܺ ᇱ ߙ ൯ + ߬ ฮܺ ᇱ ߙ ฮ ଶ = 1, ݆ = 1, … , ܬ
To simplify the presentation, we focus on the Horst Scheme (݃ሺݔሻ

= ݔ ሻ ⇒ ൛ߙ ଵ , ߙ ଶ , … , ߙ ൟ = argmax ఈ భ ,ఈ మ ,…,ఈ ଵ ∑ ∑ ܿ ߙ ᇱ ܭ ܭ ߙ ୀଵ ୀଵ subject to the constraints : ߙ ᇱ ൬൫1 -߬ ൯ ଵ ܭ ଶ + ߬ ܭ ൰ ߙ = 1, j =1, …, J
We note that this maximization problem is expressed only in terms of kernel matrices. The regularisation parameters not only makes this optimisation problem well posed numerically but also provide control over the capacity of the function space where the solution is sought. The larger the values of ߬ are, the less sensitive the method to the input data is and the more stable (less prone to finding spurious relations) the solution becomes.

⟺ ൛ߙ ଵ , ߙ ଶ , … , ߙ ൟ = argmax ఈ భ ,ఈ మ ,…,ఈ ଵ ∑ ∑ ߙ ᇱ ܴ ᇱ ܴ ܴ ᇱ ܴ ߙ ୀଵ ୀଵ subject to the constraints : ߙ ᇱ ൬൫1 -߬ ൯ ଵ ܴ ᇱ ܴ ܴ ᇱ ܴ + ߬ ܴ ᇱ ܴ ൰ ߙ = 1, j =1, …, J Let us note ݓ = ܴ ߙ and ݊ = rank൫ܺ ൯ ⟺ ൛ݓ ଵ , ݓ ଶ , … , ݓ ൟ = argmax ௪ భ ,௪ మ ,…,௪ ଵ ∑ ∑ ݓ ᇱ ܴ ܴ ᇱ ݓ ୀଵ ୀଵ (2) subject to the constraints : ݓ ᇱ ൬൫1 -߬ ൯ ଵ ܴ ܴ ᇱ + ߬ ܫ ೕ ൰ ݓ = 1, j =1, …, J (3)
A 3-step procedure is proposed to maximize (2) subject to (3):

(1) Construct the Lagrangian function related to the maximization problem.

ܮ = ܿ 1 ݊ ୀଵ ୀଵ ݓ ᇱ ܴ ܴ ᇱ ݓ -ߣ ቆሺ1 -߬ ሻ 1 ݊ ݓ ᇱ ܴ ܴ ᇱ ݓ + ߬ ݓ ᇱ ݓ -1ቇ ୀଵ
where ߣ , ݅ = 1, … , ܬ are the Lagrangian multiplier.

(2) Define stationary equations by cancelling and simplifying the derivatives of the Lagrangian function.

ݓ = 1 ටܼ ݅ ′ ܴ ᇱ ܰ ݅ -1 ܴ ܼ ݅ ൮ሺ1 -߬ ሻ 1 ݊ ܴ ܴ ᇱ + ߬ ܫ ᇣᇧᇧᇧᇧᇧᇧᇤᇧᇧᇧᇧᇧᇧᇥ ே ൲ ିଵ ܴ ܿ ܴ ᇱ ݓ ୀଵ ᇣᇧᇧᇤᇧᇧᇥ ܼ ݅ , ݅ = 1, … , ܬ (3)
Find a solution of the ܬ stationary equations by using a PLS style iterative procedure (derived to the Wold procedure which guaranty the monotonic convergence).

It is worth pointing out that for specific values of the regularization parameters, the proposed method provides as particular cases (and among others):

• For the 2 blocks cases: Kernel PLS [START_REF] Rosipal | Kernel Partial Least Squares Regression in Reproducing Kernel Hilbert Space[END_REF] (߬ ଵ = ߬ ଶ = 1), Kernel Redundancy Analysis [START_REF] Takane | Regularized linear and kernel redundancy analysis[END_REF] which is equivalent to Kernel PLS for discrimination [START_REF] Rosipal | Kernel PLS-SVC for linear and nonlinear classification[END_REF] (߬ ଵ = 1 and ߬ ଶ = ߬), Kernel Canonical Correlation Analysis [e.g. [START_REF] Bach | Kernel Independent Component Analysis[END_REF] (߬ ଵ = ߬ ଵ and ߬ ଶ = ߬ ଶ ). • For the J blocks cases: a "Horst" Generalized Kernel CCA with the flavour of the one proposed by [START_REF] Bach | Kernel Independent Component Analysis[END_REF][START_REF] Shawe-Taylor | Kernel Methods for Pattern Analysis[END_REF]] (all ߬ s′ = ߬ ; Horst scheme). Moreover, our general optimisation problem provides a "regularized" kernel extension of the Kettenring's generalized CCA (all ߬ ′ݏ = ߬ and Factorial scheme).

Conclusion

In this paper we present a very general optimization problem covering a large spectrum of methods. This paper provides a criterion point of view of the PLS path modelling framework. To the best of our knowledge, all the Kernel CCA version proposed by the machine learning community does not consider other scheme than the Horst one. In this paper, we explore the factorial and the centroïd scheme which sound more reasonable when the number of block is greater than 2. Moreover, the introduction of the design matrix allows analysing data where all blocks are not necessarily connected. To conclude this paper, we note that by using non linear kernel such as Gaussian or polynomial kernel, we can assess non linear relation between blocks.


Julien Malapert
email: julien.malapert@femto-st.fr

Réda Yahiaoui°
email: °reda.yahiaoui@femto-st.fr

Rabah Zeggari

Jean-François Manceau

Tilted Micro Air Jet for Flow Control

Keywords: Flow control, microfluidics, tilted air jet, deep reactive ion etching (DRIE)

In this paper, we present an interesting method to microfabricate a tilted micro air jet generator. We used the well-know deep reactive ion etching (DRIE) technique in order to realize in a silicon substrate a double side etching. For aircraft and cars, micro air jets will take an important place for fluid control. Micro air jets are characterized by their speed, frequency and tilt. Usually, this micro air jets are produced by fluidic microsystems. We presented experimental results about micro tilted air jets. A comparison between finite element method simulation, theory and experimental results are performed to define the microsystem geometry leading a specific air jet angle.

Introduction

In aeronautic field, one tries to control airflow close to aircraft wing [START_REF] Stanenewshy | Adaptive wing and flow control technology[END_REF]. A new method consists in producing micro air jets coming from wing surface to avoid turbulences and in order to improve aircraft aerodynamic performances [START_REF] Hak | Modern developments in flow control[END_REF]. These micro air jets have several characteristics such as speed, frequency and tilt. We fabricated on a silicon substrate a passive fluidic microsystem able to produce a tilted micro air jet [START_REF] Lofdahl | Mems applications in turbulences and flow[END_REF]. The specific air jet angle depends on channel structure and geometry of the micro channel obtained by the well-know deep reactive ion etching (DRIE) microtechnique [4]. Instead of etching a tilted channel we made a double side deep reactive ion etching providing a tilted aperture which goes to deflect air flow like in a tilted channel case. For airflow control in aeronautic fields, one try to obtain an air jet making a 45° angle from the aircraft wing surface.

In this paper, we made comparison between finite element method simulation, theory and experimental results to define the microsystem geometry leading a specific air jet angle.

Theory

Air jet speed

According to rectangular section channel dimensions (several tens by hundreds of microns), microfluidics theory, taking into account the effects of depletion and the effects of unsteady gas, does not apply. The classical fluid dynamics theory governs the behavior of fluid inside the channels of our fluidics system. However, the equations of Navier and Stokes, involving the effects governing the incompressible fluid dynamic does not seem to be the easiest solution to estimate the flow speed inside the channels of our microsystem. The difference of pressure established between the entrance port and the ejection port allows quickly and coarsely to reach out the average speed of air jet at the ejection port (v out ) according to the formula stemming from the experiment of the tube of Pitot. This formula gives the average fluid speed according to the dynamic pressure at the tube entrance and the static pressure outside of the tube: with ρ air = 1.2 Kg/m 3 at 20°C and ∆P = |P in -P out |

Tilted air jet generator

Unlike conventional machining techniques, the collective silicon microfabrication of tilted hole is considered as a difficult task. Several micro techniques (wet or dry etching) like laser machining [5], FIB (Focused Ion Beam) machining [6], erosion by electrical discharge [7] or plasma etching (DRIE) are often used to obtain holes in silicon substrate. It is rather difficult to make tilted hole with these kinds of micro machining techniques because etching is essentially normal to the surface or they are not collective. Even if we can believe a wet isotropic silicon etching (KOH, TMAH) could be used to create inclined hole collectively, it unfortunately can not overcome the natural etching directions imposed by the crystalline mesh (typically 54.7° and 35.3° for a (100) silicon wafer). This fact limits the possibilities for hole angle.

A pressure difference established between every extremity of a channel allows the creation of an air flow going through the channel. The slope of the channel allows obtaining a tilted air jet. In our case the oblique jet is not obtained through a tilted channel but through a tilted window. The particularity of this opening allows tilting the jet as in the case of a tilted channel. The supposed jet slope depends on the both d 1 and d 2 etching depths as shown in figure 1. The theoretical air jet angle θ is proportional to the z covering depth of front and back side etching, the x opening and the thickness T w of the silicon wafer. We notice that:

Numerical model

To study air jet characteristics, FEM (Finite Element Method) simulations on COMSOL software were conducted on a different air jet generator structures and for different boundary conditions.

Tilted air jet generator model

The model geometry consists of a horizontal flow channel in the middle of which is an aperture, a narrow diagonal structure (Figure 2). The fluid comes from left to top-right and goes through a tilted narrow aperture in the middle of the channel. This tilted window imposes a specific direction for air flow creating a tilted air jet at the channel exit.

Governing equation

The fluid flow in the channel is described by the Navier-Stokes equations, solving for the velocity field u = (u, v), the pressure p and the volume force F affecting the fluid. We assume no gravitation or other volume forces affecting the fluid, so F = 0. At the channel entrance on the left, the flow has fully developed laminar characteristics with a quasi-parabolic velocity profile because the condition p > 0 is applied. At the outflow (top boundary), the boundary condition is p = 0.

Numerical results

Numerical results: air jet angle

To study air jets tilt, several numerical calculations were conducted on air jet generator having different structure geometry. Each devices is composed of the same channel dimensions except tilted aperture dimensions (x and z dimensions). The simulation takes into account the volume of air in the cavities located on the top and the bottom of the device (figure 2). We can see easily the outgoing tilted air in the cavity located in the top side. We estimate that over this cavity, the jet retains its slope (50° in figure 2) to a distance several times equal to d 1 depth. While we neglect the viscosity of fluid for the estimation of theoretical jet speed, the simulation must take into account this parameter because it is this effects that will give the slope to the air jet which can be measured. Numerical calculation on different model having various x/z ratio was conducted. Measured angle are listed in the following table and where wee can see a quiet good agreement (~20%) between theory and numerical results.

Numerical results: air jet speed

In order to estimate the real air jet velocity, we wanted to compare numerical and theory results. We made numerical calculations with a specific structure where we applied a range of inlet pressure. We measured velocity at the exhaust port of the channel for several inlet pressures. Maximum velocity is obtained at x = 250 µm for each inlet pressure. It seems the jet slope does not depend on the pressure. From these numerical results, it is possible to compare theory and numerical results. We can observe in figure 4 the good agreement between the both results and we can estimate real air jet velocity is to close them.

Experiments

Experimental set up

In order to visualize the airflow, we use smoke to make air visible for video camera. The smoke comes from a smoke generator (figure 5). Smoke makes appear tilted micro air jet above jet generator. Air jet is obtained applying a minimal pressure of 0.5 bar until a maximum pressure of 2 bar in order to avoid air jet generator destruction. No variations of jet angle have been seen in function of inlet pressure variation like in numerical results. We can consider that air jet angle does not depend on air inlet pressure in our case.

Experimental results

Fluidic experiments are made at a pressure of 1 bar. Jet angles can be measured following two methods. First one, we can use a grid behind air jet (figure 6) and second one, we can use software able to measure angle from acquired pictures. In the present case, according to generator architecture dimensions, obtaining a jet angle of less than 23° is impossible as well as an angle greater than 90°. Overall, between these two extremes, for theory, simulation and experiment, the more x/z ratio becomes high the more jet angle increases and vice versa (figure 7). We note that theory data seems to be a limit which can not exceed FEM simulation and experimental results. For example and at first glance, when x/z = 1, corresponding to a theoretical angle of 45°, this angle is approximately obtained by simulation only for x/z = 1.3 and for x/z = 1.6 in the case of experimental results.

Conclusions

FEM calculation results combined with some fluidic experiments and applying a correcting factor allow defining structure geometry to generate a specific air jet angle. A 45° jet angle is not obtained with an x/z ratio equal to 1 but with a smaller ratio (1.3 and 1.6 for numerical and experimental results). The good agreement between theory and FEM simulation results involving air jet velocity allow us to estimate real air jet velocities for greater pressures. In the future, specific measurement technique of the velocity will be implemented to confirm calculations. Moreover, we will try to make systems using this kind of air jet generators to prove their efficiency for flow control. We want to precise we employed an original and easy method using the well-known DRIE technique to develope and to collectively make fluidic microsystems able to produce tilted micro air jets.

Figure 1 .

 1 Figure 1. Sketch of the tilted micro air jet generator.

Figure 2 .

 2 Figure 2. Plot of FEM results and tilted air jet generator structure.

Figure 3 .

 3 Figure 3. Air velocity along the exhaust port of the channel for different inlet pressure.

Figure 4 .

 4 Figure 4. Air jet velocity (numerical and theory data) at the exhaust port of the channel for different inlet pressures.

Figure 5 .

 5 Figure 5. General structure of test bench for tilted air jet generators.

Figure 6 .

 6 Figure 6. Picture of tilted micro air jet above jet generator (42°).

Figure 7 .

 7 Figure 7. Air jet angle as a function of x/z ratio for theory, numerical and experimental results.

Acknowledgements

The authors would like to thank the technology staff of MIMENTO micro technology center, in Besançon, France and this research is funded by ANR Project 06 ROBO 0009 03.


Paul De Vlieger

Jean-Yves Boire

Vincent Breton

Yannick Legré

David Manset

Jérôme Revillard

David Sarramia

Lydia Maigne

Grid-enabled sentinel network for cancer surveillance

Recent developments of grid services for secured distributed data management open new perspectives for disease surveillance.

In this paper, we report on our initiative to develop a surveillance network for cancer in the Auvergne region. The network gathers cytopathology laboratories, structures in charge of cancer screening and institutes in charge of cancer epidemiology. Data stored in laboratories are queried through the grid for the purpose of second diagnosis and to produce statistical indicators.

The paper describes the network goal and design and discusses specific issues related to patient identification and security.

Introduction

Cancer is becoming the first cause of mortality in developed countries. In recent years, the number of patients treated for cancer has been constantly growing while mortality has started to decrease, thanks to the progresses accomplished in the treatment of this disease and to the development of cancer screening programs [START_REF]Cancer Screening in the European Union; Report on the implementation of the Council Recommendation on cancer screening[END_REF]. These programs allow an early detection of the malignant tumours which improves significantly the medical prognosis.

In order to evaluate the public health policies, reliable statistical indicators are needed. In France, several structures have been set up to collect epidemiological data on cancer such as CRISAPs (Centre de Regroupement Informatique et Statistique en Anatomie et cytologie Pathologiques) which are like regional data warehouses collecting anonymous data from anatomical pathology laboratories or from the healthcare structures involved in cancer treatment. The extraction of data from laboratories encounters reluctance from the healthcare professionals because of cost and also because they lose some control over the data they have produced.

Several projects in Europe have studied or are currently exploring the grid added value for addressing cancer: the pioneer projects focused on breast cancer, particularly computer-aided diagnosis of mammograms (e-Diamond [START_REF] Brady | eDiamond: a grid-enabled federated database of annotated mammograms[END_REF] and MammoGrid [START_REF] Warren | A Prototype Distributed Mammographic Database for Europe[END_REF], [START_REF] Warren | A Comparison of Some Anthropometric Parameters between an Italian and a UK Population: "proof of principle" of a European project using MammoGrid[END_REF] projects ). These projects have produced most of the middleware bricks being used to build our cancer surveillance network: MDM (Medical Data Manager) [START_REF] Montagnat | Bridging Clinical information systems and grid middleware: a Medical Data Manager[END_REF] and Globus Medicus [START_REF] Sg | Globus MEDICUS -federation of DICOM medical imaging devices into healthcare Grids[END_REF] are some of them; and more recently, the Pandora Gateway designed for the Health-e-Child project [START_REF]The Health-e-Child project[END_REF].

In this paper, we propose a very innovative approach to both cancer screening and epidemiology based on grid technology. We describe how a "collaboration" grid federating the cytopathology laboratories together with the screening associations and the institutes in charge of cancer epidemiology would manage easily the patient data in a secure and reliable way.

2 Objectives of a grid-enabled surveillance network

Context

Most EU countries have launched a national program for breast cancer screening [START_REF]Cancer Screening in the European Union; Report on the implementation of the Council Recommendation on cancer screening[END_REF]. In France, breast cancer screening is achieved through inviting women above 50 to have mammograms every 3 years. When a woman is positively diagnosed with a risk of tumour, cancer structures are in charge of providing a second diagnosis on the mammograms and have to follow-up on the anatomical pathology (or cytopathological) data about the tumour which are stored by the laboratories. Presently, the patient data are faxed on request or carried physically by the patient to the associations where they are recorded again. This process is costly and errors prone as data have to be typed and reinterpreted twice.

The cytopathological data are also extremely important for epidemiological analysis. The INVS (Institut National de Veille Sanitaire = Sanitary Surveillance Institute), French equivalent to (E)CDC 1 for the (EU)USA, is in charge of publishing indicators about global health and particularly about cancer. To produce its indicators, INVS relies on regional cancer registries (CRISAPs) set up to collect relevant information to support statistical and epidemiological studies about cancer incidence, mortality, prevalence and screening. However, regional cancer registries have several drawbacks:

1. In any healthcare system, physicians are responsible of patient information. The pathologists refuse to trust these systems as data is exported outside their databases, so patient identification criterias cannot be attached to the file in order to disengage responsibility. In this way, neither disambiguation nor patient linkage is possible, so statistics are biased. Effectively, only medical information is carried out without patient identification. As a patient can undergo several biopsies in different laboratories, the information about his cancer would be present twice in the register without linkage.

2. Some pathologists refuses to export since this method requires losing control of the data produced in their own laboratories which is like the fruits of their labor.

3. The current data gathering system needs physicians to export manually data from their software, format it according to the Crisap specification, connect to the central repository and send their file. This method is costly in time without any compensation. Now, their usage is being questioned as the global quality of these repositories decreased and less and less laboratories contribute to the registers.

Solution proposed

Our alternative is for the clients to query anatomical pathology laboratories databases directly on site. A collaborative data grid, federating the laboratories, (see Figure 1) would provide a secured framework enabling the screening associations to query databases and fill their local patient file. No action is required by physicians to push their data on the network. Thanks to the Grid Security Infrastructure (GSI) [START_REF] Welch | Security for Grid services[END_REF], the pathologists are able to define and modify the access rights of the users querying their data. If a sentinel network is able to federate anatomical pathology databases, it can be used by the epidemiological services of the INVS and the regional epidemiological observatory to build epidemiologic studies.

Material and methods

List of requirements

As shown in Figure 1, the main medical data providers are the cytopathology laboratories. These different laboratories host different software systems and local databases for medical data management. Radiology services are additional data providers for mammograms in a step futher. The data requesters are the cancer screening associations and the different epidemiological structures in charge of producing statistics on specific cancers at regional and national level. Contrary to cancer screening associations who need to obtain the entire medical patient sheet, epidemiological structures need only anonymous medical data to produce statistics but with disambiguation to avoid double counting of cancer patients.

In a near future, the network should be able to grant access to medical images like mammograms to the cancer screening associations in order to ease the second diagnosis. The infrastructure design should offer a good flexibility to ease the entrance of new actors in the network.

The security infrastructure of the network needs to comply with French regulation on medical data transfer and exchange. The pathologists need to control the access rights to their own data. The network users must authenticate themselves using recognized accreditation tools like healthcare professionals cards. The individual certificates used have to be delivered by a certification authority (CA) recognized officially by the ministry of health and compatible with the grid infrastructure deployed.

Sentinel network infrastructure

The proposed dedicated grid architecture is built upon a central set of servers hosting security features and core grid services as illustrated in Figure 2:

• VOMS is an authorization manager, which implements a PKI-based authentication with certificates delivered by trusted authorities (CA) [START_REF] Alfieri | From gridmap-file to VOMS: managing authorization in a Grid environment[END_REF]. The usage of VOMS in this project is almost mandatory as VOMS is part of the gLite [13] middleware and guarantees a robust access control to the grid. Each user must own a certificate in order to log in. During the network development phase, a local certificate authority will be created, but once the network is operational, only official certificates for duly authorized healthcare professionals will be used to log in.

• The Pandora GateWay is a set of software designed as a Service Oriented Architecture (SOA). It was developed by the Maat-G society for the Health-e-Child project [START_REF]The Health-e-Child project[END_REF]. The Pandora Gateway is used to address medical data accessibility, exchange and processing while guaranteeing a high level of security for sensitive data. The main added value of the GateWay, compared to a classic SOA platform, is the high-level security. The GateWay Authentication Service is based on several security checkpoints required for log in. The access point is a Two Factor Authentication with user certificates and pin code followed by an authentication process using a VOMS Grid Proxy creation.

• The AMGA (ARDA Metadata Grid Application) [START_REF] Koblitz | The AMGA Metadata Service[END_REF] server, which provides a way to access and store metadata. Beside its high performance, the main advantages of AMGA are the full implementation of the grid security infrastructure (GSI) as well as the integration VOMS. When dealing with medical images, the use of metadata is mandatory and MDM (Medical Data Manager) allows bridging DICOM servers and the gLite middleware through AMGA [START_REF] Montagnat | Bridging Clinical information systems and grid middleware: a Medical Data Manager[END_REF].

AMGA is a very attractive software to fulfill the strong security requirements and access right management of medical data in a grid infrastructure.

• GridFtp server for data transfer [START_REF] Allcock | The Globus Striped gridFTP Framework and Server[END_REF].

• LFC server, for data management, included in the gLite middleware [13] 4 Specific issues for prototype implementation

Data specification and retrieval system

For a better readability of cytopathological data, data sheets standardization is used to simplify the addition of medical records in the database without interfering with other data. Care must be taken at this step not to lose data coherence and the ownership of medical diagnosis. The customer part of the application hosts a grid server (under a firewall) to link patients" data in the network. For public health centers, a computer with an Internet access is just needed to launch epidemiologic requests.

Patient identification and data linkage

Patient identification is one of the major issues of modern healthcare systems. How can a healthcare system provide a way to identify surely his citizens while respecting their privacy?

As disambiguation and patient linkage is one of the central part of this project, patient identification is at the core of the data linkage problem. Currently, due to the lack of global identifier, each patient is linked to two different identification numbers (medical folder numbers) which are used inside each medical structure (see Figure 3). Our solution requires an additional identifier for the sentinel network. This identifier consists in a random number generated (uuid type as defined in the RFC 4122 [START_REF] Leach | A Universally Unique IDentifier (UUID) URN Namespace[END_REF]) for each patient. This identifier would be created only for data linkage and would always be encrypted using different keys in each database to protect patient privacy.

When a data provider downloads some new data from his local data server to the local grid server, the Pandora Gateway is in charge of searching the patient in all the local databases respect to information on the patient. It will produce a unique identification number corresponding to the medical data if two identifiers are correlated to the same patient. With this procedure, we build a consistent network with unambiguous usage as we provide statistical requests free of doubles.

Security issues: strategy

One important step in the analysis is to clarify all security aspects in the sentinel network. The usage of SSL (Secure Socket Layer) and GSI will create a trusted network where data exchange and authorization procedures will fit the security requirements. However, and in order to protect patient privacy, the network access has to be restricted to authorized physicians or related staff only. The usage of Electronic Health Cards seems to be the best solution to settle this issue. These cards exist in France2 and also in other European countries thanks to the EU framework 3 . Basically, these cards are smartcards containing certificates on a chip and supports strong authentication, electronic signature and data encryption. As bundled certificates are X509 formatted, they are intrinsically compatible with authentication on a gLitepowered Grid. These cards are also a response for data holders (i.e. pathologists) to accept the sharing of their data. As the sentinel network will be reachable only by physicians, the different queries will be launched under the responsibility of the physician who launches the query. The pathologists are now free to make available safely their data without any risk in case of wrong use.

Validation

Once the prototype operational and upstream of the real exploitation phase, the following step will consist in a validation of epidemiologic queries in order to certify the cohenrency and consistancy of the results obtained. The comparision will be possible with the previous conclusion of epidemiologic surveys locally obtained with manual methods by the regional public health service.

Conclusion

The article describes the goals and design of a surveillance network for breast cancer in the Auvergne region. The network will allow federating, in a fully secured way, cytopathology databases with cancer associations. The cancer network will be used to improve cancer screening programs and to produce reliable and theorically exhaustive cancer epidemiological indicators. Implementation of the sentinel network has started. The aim is to deploy a first prototype by the summer 2009 between one of the 2 cancer screening associations in Auvergne and a cytopathology laboratory. The beta version of the network will be operational by the end of 2009.

The integration of additional laboratories as well as the development of query interfaces for epidemiological structures will be addressed in 2010. Extension of the network to other cancer types and medical images sharing are foreseen within the framework of a new project to be funded by French Research Funding Agency.

The work described in this article was partly supported by grants from the European Commission (EGEE, Embrace), the French Ministry of Research (GWENDIA) and the regional authorities (Conseil Régional d"Auvergne, Conseil Général du Puy-de-Dôme, Conseil Général de l"Allier). The Enabling Grids for E-sciencE (EGEE) project is co-funded by the European Commission under contract INFSO-RI-031688. The EMBRACE project is co-funded by the European Commission under the thematic area "Life sciences, genomics and biotechnology for health", contract number LHSG-CT-2004-512092. Auvergrid is a project funded by the Conseil Regional d"Auvergne. The GWENDIA project is supported by the French ministry of Research.

Figure 1

 1 Figure 1 Cancer surveillance network using Grid technologies.

Figure 2

 2 Figure 2 Service Oriented Architecture of the sentinel network.If a client wants to use the system, he has to login through his local GateWay which authenticates himself on the sentinel network. When he launches a request, his local GateWay calls the different available AMGA servers on the network aggregate the responses and finally delivers the result to the client. In this way, no information is exchanged out of the different GateWays, guarantying a high level of security and easing data tracking. . Thanks to the Grid Security Infrastructure, authentication and credentials are available in the whole Grid, through GateWays and AMGA server.

Figure 3

 3 Figure 3 Patient identification problem.

(E)CDC: (European) Centre for Disease Prevention and Control

www.gip-cps.fr

www.hprocard.eu

Acknowlegements

The authors wish to acknowledge numerous discussions with P.Bouchet, A.Gaillot, L.Gerbaud, M-A.Grondin, A.Lautier, P.Lonchambon and C.Mestre.


Husain Mubashir

Aline Rehmani

Hicham Carneiro Viana

Serge Khalife

Fdida

M H Rehmani

A C Viana

H Khalife

S Fdida

Adaptive and Occupancy-based Channel Selection for unreliable Cognitive Radio Networks

Introduction

Due to limited available spectrum and fixed spectrum assignment policy in today's wireless networks, radio spectrum is used inefficiently. To counter this issue, Cognitive Radio Networks (CRNs) are designed to allow cognitive radio (CR) nodes (i) utilizing free parts of unlicensed spectrum as well as (ii) opportunistically exploiting licensed frequency bands in silent periods of licensed users, called primary radio (PR) nodes [ALVM06,MM99].

Note that the traffic pattern of primary users is of key importance here : if we know that a particular channel is heavily used by a PR node and it tends to occupy it for a long period of time, that channel would be less likely available for a CR node. Because of this PR's high time occupancy, the usability of the channels by CR nodes becomes uncertain. In addition, since PR nodes operating over different channels have different activity patterns, depending on the technology they are using and the environment characteristics, a hardly predictable and time-variant occupancy can be also perceived. Thus, it is essential and, however, extremely challenging to correctly select channels allowing reliable communication among CR nodes as well as channels that increase the number of CR receivers. This constitutes the goal of this paper.

In this paper, we present a new strategy for adaptive and occupancy-based channel selection in CRNs. Our strategy empowers CR nodes with the ability to infer, based on information regarding PR occupancy, the less occupied channel to use. CR nodes then use the proposed strategy to select channels for transmission and overhearing. Hence, by exploiting overhearing and PR occupancy properties, our strategy allows not only increasing the network reliability -since less PR-occupied channels will be selected -but also the delivery ratio -since a high number of CR nodes will overhear the selected channel.

Adaptive and occupancy-based channel selection

We are considering an ad-hoc infrastructure-less architecture of Cognitive Radio Network. In this architecture, only CR-CR communications will occur. Cognitive Radio (CR) nodes are highly frequency agile. Due to PR activity over every channel, intermittent connectivity of links occurs, requiring CRNs to be highly opportunistic. CR nodes are able to communicate over multiple channels. Within the network, two nodes can communicate if they use at least one common channel and if they are within the transmission range of each other. The spectrum used by PR and CR nodes consists of N Channels C = {1, 2, 3, . . ., N}, where channels availability for CR nodes is highly time variant and dependent on the PR activity variability over every channel.

After sensing the channels in the CRN, each CR node makes a list of detected channels in the network. Each CR node then classifies the sensed channels in a decreasing order of availability, and selects for transmission and/or overhearing the best weighted channel. Channels' weight P channel is calculated based on PR and CR nodes' occupancy :

P channel = e -PROccupancy × CROccupancy CROccupancy = 1 -PROccupancy Since PR and CR occupancy are inversely proportional, selection of the less occupied channel by PR nodes also implies the selection of the most used channel by CR nodes. Hence, the use of the best channel given by the highest value of P channel allows improving network reliability as well as increasing the delivery ratio.

Simulation Results and Conclusion

To assess the performance of the proposed approach, two performance metrics are evaluated : (i) the average delivery ratio, which is ratio of packet received by a particular CR node over total packets sent in the network and (ii) the average number of receivers, which is the real quantity of receivers per node id. In order to simulate message losses, a probability of receiving a message is assigned to each channel. Results shown below are generated for an average of 500 simulations, along with 95% of confidence interval, for a network of 10 CR nodes. Fig. 1 compare random (RD) and our strategy (OS) results for the delivery ratio and number of receivers of these two strategies, as a function of the CR nodes' ID. The results show how the number of channels impacts the average delivery ratio and the average number of receivers for the two strategies. In particular, by selecting the channel with highest P channel , CR nodes are trying to access best channel in terms of occupancy, for transmitting and overhearing. Hence, as shown in Fig. 1, our strategy considerably increases the delivery ratio and the number of receivers. Our strategy guarantees the delivery of 80% to 85% of messages, contrarily to less than 45% to 40% for the random strategy (cf. Fig. 1(a)). Note that the increase of the number of channels has a negative impact on the delivery ratio for the random strategy. This is due to the fact that the probability of a CR node to randomly select for overhearing, the same channel that another CR node has randomly selected for transmitting, decreases with the increase of the number of channels. Moreover, our strategy guarantees from 38% to 40% more nodes reception than with the random strategy (cf. Fig. 1(b)). Our solution increases the delivery ratio and the number of receivers since it selects the channel with low primary activity and have a high probability to encounter overhearing CR nodes.

In summary, our experiments reveal that, by increasing the number of channels, our proposed strategy considerably increases the average delivery ratio and the average number of receivers, when compared to the random strategy. In addition, contrarily to random strategy, our proposed strategy guarantees obtaining high delivery ratio proportional to the number of available channels. This shows how good our strategy is in allowing CR nodes taking profit of available channels. 6, no. 4 :13-18, 1999.

R éf érences

FIG. 1 :

 1 FIG. 1:Average delivery ratio and number of receivers in a CRN, for random (RD) and our adaptive strategy (OS).

[

  ALVM06] Ian F. Akyildiz, Won-Yeol Lee, Mehmet C. Vuran, and Shantidev Mohanty. Next generation/dynamic spectrum access/cognitive radio wireless networks : a survey. Computer Networks : The International Journal of Computer and Telecommunications Networking, 50 , Issue 13 :2127 -2159, 2006. [MM99] J. Mitola and G. Q. Maguire. Cognitive radio : Making software radios more personal. IEEE Personal Communications,