Nouredine Tamani
email: tamani@enssat.fr

Ludovic Liétard
email: ludovic.lietard@univ-rennes1.fr

Daniel Rocacher
email: rocacher@enssat.fr

An Extension of a Fuzzy Ontology for Flexible Querying

Keywords: Ontology, flexible querying, personalization, fuzzy DLR-Lite, SQLf, fuzzy sets theory, multimodal transportation

In this paper, we propose a personalized approach for flexible querying of information systems. This approach consists in the combination of the reasoning capabilities of the fuzzy DLR-Lite ontology and the expressivity of the SQLf language. The interpretation of the gradual inclusion (subsumption) axioms of the ontology is based on the Gödel fuzzy implication. Its generalization to a tree of inclusions is also proposed. This tree and its property of propagation of degrees are the basic theoretical elements of our application, which consists in querying of a multimodal transport information system which is embedded in a mobile terminal characterized by limited storage and processing capabilities.

I. INTRODUCTION

The personalization of flexible querying of information systems dedicated to multimodal transportation networks is addressed in this paper. We propose an approach which consists in the development of a fuzzy semantic layer in order to extend the functionalities of information systems to reasoning. This layer is made of reasoning functions which combine domain application data with ontology axioms. Ontologies are able (i) to model the domain knowledge, (ii) to unify its vocabulary, (iii) to reason with available knowledge and (iv) to deduce implicit data from explicit data.

The proposed approach is developed in the framework of flexible querying of information systems which allows the user to express preferences in his/her queries. In such a system, the delivered answers are ranked from the most to the least preferred. In this context, user preferences can be expressed by vague or fuzzy predicates such as fast, expensive, near, etc. which are defined by fuzzy sets [START_REF] Zadeh | Fuzzy sets[END_REF]. From the querying point of view, the SQLf language [START_REF] Bosc | SQLf: A relational database langage for fuzzy querying[END_REF], [START_REF] Bosc | Base de données -Gradualité et imprécision dans les bases de données Ensembles flous, requêtes flexibles et interrogation de données mal connues[END_REF] is a suitable language to express query with preferences. It is an extension of the SQL language to fuzzy predicates (conditions) and provides more expressive SQL-like statements.

From the reasoning point of view, several fuzzy ontologies (based on description logics [START_REF] Baader | The Description Logic Handbook : Theory, Implementation and Applications[END_REF]) have been developed (see [START_REF] Bobillo | fuzzyDL : An expressive fuzzy description logic reasoner[END_REF], [START_REF] Hudelot | Fuzzy spatial relation ontology for image interpretation[END_REF], [START_REF] Lu | Reasoning within extended fuzzy description logic[END_REF], [START_REF] Pan | Expressive querying over fuzzy DL-Lite ontologies[END_REF], [START_REF] Stoilos | Fuzzy OWL: Uncertainty and the semantic web[END_REF], [START_REF] Straccia | Towards a fuzzy description logic for the semantic web (preliminary report)[END_REF]) in which theoretical aspects have been widely studied (the definition of fuzzy concepts and relations, the definition and the interpretation of fuzzy inclusion or subsumption axioms, the fuzzy extension of subsumption algorithms, etc.). However, these ontologies are not suitable to address querying issue. Indeed, ontologies save axioms, individuals and related data in text files which are not appropriate for the needs of real applications. Ontology-based querying systems are faced with a large amount of data to such extent that the combination of ontologies and databases become an absolute necessity. In addition, the developed ontology-based querying systems, such as [START_REF] Straccia | DLmedia: an ontology mediated multimedia information retrieval system[END_REF], [START_REF] Calvanese | Data complexity of query answering in description logics[END_REF], [START_REF] Pan | Expressive querying over fuzzy DL-Lite ontologies[END_REF], [START_REF] Straccia | Answering vague queries in fuzzy DL-lite[END_REF], are based on limited description logics in terms of expressivity. To overcome this limitation, databases are combined with ontologies to provide DBMS functionalities such as data persistence and query evaluation. Ontology axioms are then used in the query rewriting process to take into account the logical relationships between concepts.

In this context, we consider the Description Logic extended to m-ary Relations [START_REF] Calvanese | Data complexity of query answering in description logics[END_REF] denoted DLR-Lite. More precisely, we are interested in the fuzzy extension of the DLR-Lite, called fuzzy DLR-Lite [START_REF] Colucci | Semantic Web Information Management, chapter 19 : Informative Top-k retrieval for advanced skill management[END_REF], [START_REF] Straccia | Softfacts : a top-k retrieval engine for a tractable description logic accessing relational databases[END_REF], [START_REF] Straccia | DLmedia: an ontology mediated multimedia information retrieval system[END_REF], which is made of a reduced set of fuzzy operators and abstraction rules which are connected to databases through SQL statements.

In this paper, we aim to design a flexible querying system that combines a fuzzy DLR-Lite knowledge base with the SQLf language, so as to take profit from the expressivity of the SQLf language and the reasoning mechanisms of the fuzzy DLR-Lite. Firstly, we show the relevance of the Gödel fuzzy implication to the interpretation of gradual inclusion (subsumption) axioms of the fuzzy ontology. Then, we consider the enrichment of the fuzzy DLR-Lite knowledge base with the SQLf language. The resulting knowledge base is finally applied on a sample mobile application in the field of multimodal transportation. The developed application is embedded in a lightweight terminal in which the accessible data are limited to a subset of the knowledge base. This restriction is due to the limited storage and processing capabilities of such terminals.

The remainder of the paper is structured as follows. Section II introduces the fuzzy DLR-Lite knowledge base. In section III, the Gödel fuzzy implication is used to define an interpretation to the gradual inclusion axiom; its contrapositive is also used to define a restricted form of the negation operator. We also show in section III the way in which our interpretation is extended to a tree of gradual inclusion axioms and its degree propagation property. Section IV introduces briefly the SQLf language and points out the relevance of the enrichment of the fuzzy DLR-Lite knowledge base with this language. Our sample application is described in section V. Section VI recalls our contributions and draws some lines for future works.

II. THE FUZZY DLR-LITE ONTOLOGY

In this section, we introduce some elements of both the fuzzy sets theory and the fuzzy DLR-Lite knowledge base.

A. The Fuzzy Sets Theory

The fuzzy sets theory is introduced by Zadeh [START_REF] Zadeh | Fuzzy sets[END_REF] to express the gradual membership of an element to a set. Formally, a fuzzy set F is defined on a referential U by a membership function µ F : U → [0, 1] such that µ F (x) denotes the membership grade of x in F.

In particular, µ F (x) = 1 denotes the full membership of x in F, µ F (x) = 0 expresses the absolute non-membership and when 0 < µ F (x) < 1, it reflects a partial membership (the more µ F (x) is close to 1, the more x is a member of F).

A fuzzy set generalizes a crisp set in which membership grades are in {0, 1}. If a fuzzy set is a discrete set then it is denoted by F = {(x 1 , µ F (x 1 )), ..., (x n , µ F (x n ))}, otherwise, it is characterized by its membership function.

The union ∪ and the intersection ∩ operators are defined with a couple of (t-norm, t-conorm) such as (min, max). Let F, G be two fuzzy sets;

µ F∪G (x) = max(µ F (x), µ G (x)), µ F∩G (x) = min(µ F (x), µ G (x)) and the complement of F, noted F c , is defined by µ F c (x) = 1 -µ F (x).
The logical counterparts of ∩, ∪ and the complement are resp. ∧, ∨ and ¬. Other operators are also defined such as fuzzy implications.

B. The Fuzzy DLR-Lite Knowledge Base

The fuzzy DLR-Lite knowledge base K consists of three components (O, F , A ) defined in what follows.

1) The Facts Component F : It contains the extensions of relations made of tuples of the form R(c 1 , ..., c n )[s], where R is an n-ary relation, c i,i=1,...,n are constants and s ∈]0, 1] is a grade indicating in which extent the tuple c 1 , ..., c n is an instance of the relation R.

2) The Ontology Component O: The ontology defines the concepts of the application domain by means of projection, intersection and inclusion axioms:

• The gradual inclusion (subsumption) axiom has the form

(R 1 R 2 ... R l R r )[s]
, where l ≥ 1 and all the involved relations are of the same arity and s ∈]0, 1] is the truth degree of the axiom. 3) The Abstraction Component A : It forms the set of statements that connect concepts and relations, defined in the ontology component, to physical relational tables defined in a database. Simple and complex abstraction statements are defined as follows:

• Simple abstraction statement has the form: It is worth noticing that the interpretation function R I has the same meaning as the membership function µ R as defined in the fuzzy sets theory. Therefore, both R I (x) and µ R (x) notations are identical.

R 1 -→ R 2 (c 1 [t 1 ], ..., c n [t n ])[c s ]
For sake of clarity, we only introduce the interpretation of the gradual inclusion axiom; see [START_REF] Straccia | Softfacts : a top-k retrieval engine for a tractable description logic accessing relational databases[END_REF] for more details about the interpretation of simple and restricted projection axioms.

The interpretation of the gradual inclusion axiom is defined as follows:

I |= (R 1 ... R l R r )[n] ⇔ ∀c ∈ ∆ m , n ⊗ R I 1 (c) ⊗ . . . ⊗ R I l (c) ≤ R I r (c), (1)
where m is the arity of the relations R i,i=1,...,m and R r and ⊗ is a t-norm.

The formula [START_REF] Baader | The Description Logic Handbook : Theory, Implementation and Applications[END_REF] states that if c is an instance of R i,i=1,...,l at the degree

s i = R I i (c) then c is an instance of R r at the minimal degree n ⊗ s 1 ⊗ ... ⊗ s l .

D. The Query Language

A fuzzy DLR-Lite query consists in a conjunction query combined with a scoring function to rank answers. The query is of the following form:

q(x)[s] head ← ∃yR 1 (z 1 )[s 1 ], ..., R l (z l )[s l ], body OrderBy(s = f (s 1 , ..., s l )) scoring f unction ,
where q is a k-ary relation, each R i is a relation, x (resp. y) is a vector of distinguished (resp. non distinguished) variables, z i is a tuple of constants or variables from x or y, f is a scoring function which combines the scores s 1 , ..., s l and s is the degree of satisfaction of a tuple x to the query q. Such a query is evaluated using the gradual inclusion axioms defined in the ontology component. Each query atom (R i (z i )[s i ]) appearing in the right-hand side of an inclusion axiom is substituted by its left-hand side. Each axiom substitution generates a new query which is added to a disjunctive query. Each subquery of the resulting disjunctive query is finally translated into an SQL query to be evaluated over the facts component.

Example 1. Let Journey be a relational table of journeys defined from a multimodal transportation system. We define the fuzzy relation FastJourney from the Journey relation and the following inclusion (subsumption) axiom:

(FastJourney FavoriteJourney)[0.7], which states that each fast journey is also a favorite journey at the minimal degree of 0.7.

Any query involving favorite journeys, such as: q(t)[s] ← FavoriteJourney(t), OrderBy(s) is rewritten, based on the above gradual inclusion axiom, in terms of fast journeys (the t-norm used is min) as follows:

q (t)[s] ← FastJourney(t)[s ],
OrderBy(s = min(0.7, s )), where s = f ast I (t) is the grade which expresses in what extent the journey t is fast.

We obtain for each journey t a minimal grade of satisfaction to the query q equals to min(0.7, f ast I (t)) since the interpretation of the gradual inclusion axiom means: ∀t, Favorite I (t) ≥ min(0.7, f ast I (t)). p

III. THE GRADUAL INCLUSION AXIOM AND THE G ÖDEL FUZZY IMPLICATION

In this section, we show that the interpretation of the gradual inclusion axioms of the fuzzy DLR-Lite ontology is based on the Gödel fuzzy implication. We also show the interest of its contrapositive for the definition of a restricted form of the negation operator. We finally generalize the Gödel fuzzy implication based interpretation to a tree of gradual inclusion axioms.

A. Gödel Fuzzy Implication Based Interpretation of the Gradual Inclusion (Subsumption) Axiom

Let (A B)[α] be a gradual inclusion axiom, denoted by A α B. It is interpreted in the framework of the fuzzy DLR-Lite [START_REF] Straccia | Softfacts : a top-k retrieval engine for a tractable description logic accessing relational databases[END_REF] as follows:

∀x ∈ ∆, B I (x) ≥ min(α, A I (x)) (2)
We can prove that this interpretation is based on a gradual inclusion defined by the Gödel fuzzy implication (µ

A (x) ⇒ G ö µ B (x) = 1 if µ A (x) ≤ µ B (x); µ B (x), otherwise): A α G ö B ⇔ min x (µ A (x) ⇒ G ö µ B (x)) = α (3)
In the remainder of the paper, we use equally the notations A α B and A α G ö B. Proof: The Gödel fuzzy implication is an R-implication defined by:

µ A (x) ⇒ G ö µ B (x) = sup [0,1] {u|min(µ A (x), u) ≤ µ B (x)}. We denote (µ A (x) ⇒ G ö µ B (x)) by I(µ A (x), µ B (x)). As I(µ A (x), µ B (x)) is a u value then: ∀x, min(µ A (x), I(µ A (x), µ B (x))) ≤ µ B (x) (4)
having α = min x (I(µ A (x), µ B (x))) then ∀x, α ≤ I(µ A (x), µ B (x)) ⇒ ∀x, min(µ A (x), α) ≤ min(µ A (x), I(µ A (x), µ B (x))
). From the formula (4), we obtain: ∀x, min(µ A (x), α) ≤ µ B (x).

This interpretation, based on the Gödel fuzzy implication, allows the definition of a minimal threshold of satisfaction to queries in which substitutions of the gradual inclusion axioms are performed.

In addition, the Gödel fuzzy implication provides effective means of computing the minimal grade of the gradual inclusion axioms (formula ( 1)).

B. The Gradual Inclusion Axiom and the Contrapositive of the Gödel Fuzzy Implication

The contrapositive of the Gödel fuzzy implication could be used to define a new type of fuzzy inclusion (subsumption) denoted ContG :

A β ContG B ⇔ min x (1 -µ B (x) ⇒ G ö 1 -µ A (x)) = β (5)
The interpretation of this form of fuzzy inclusion axioms is deduced from the interpretation based on the Gödel fuzzy implication as follows:

A β ContG B ⇒ ∀x, ¬A I (x) ≥ min(β , ¬B I (x)) (6)
The proof of this interpretation is similar to the previous proof. This form of gradual inclusion axioms allows to express a restricted negation operator.

Example 2. Let TouristJourney 0.6

ContG FavoriteJourney be a fuzzy inclusion (subsumption) axiom which means that the fuzzy set of touristic journeys is included in the fuzzy set of favorite journeys at the minimal degree of 0.6. In the case that the access is limited to favorite journeys, the system can answer queries about journeys which aren't touristic, based on the above fuzzy inclusion axiom, as follows: ¬TouristJourney(t) ≥ min(1 -FavoriteJourney(t), 0.6) (formula (5)). p Please notice that this negation is only applicable to relations involved in gradual inclusion axioms.

C. Interpretation of a Tree of Gradual Inclusion Axioms

The proposed interpretation of the gradual inclusion axiom is generalized in the case of a tree of inclusion axioms. This tree structure and its property of degree propagation are the basis of the developed application in section 5.

Without loss of generality, we restrict the tree structure to two levels of inclusion as depicted in Fig. 1a.

Such a tree structure means:

A α G ö B and B β G ö C, where α, β ∈]0, 1]. !! !"! !#! !$! %! &! (a) !! !"! !#! !$! %! !! &'()%*!!+! ! ! (b)
Fig. 1: A tree structure with two levels.

By applying the formula (2), we obtain:

µ B (x) ≥ min(µ A (x), α) (7)
µ C (x) ≥ min(µ B (x), β ) (8)
The propagation property allows the deduction of the grade of inclusion of the concept A in the concept C (see Fig. 1b).

Proof: From the formula (7), we deduce:

µ B (x) ≥ min(µ A (x), α) ⇒ min(β , µ B (x)) ≥ min(β , min(µ A (x), α)) = min(α, β , µ A (x)) = min(min(α, β ), µ A (x)). From min(β , µ B (x)) ≥ min(min(α, β ), µ A (x)) µ C (x) ≥ min(µ B (x), β ) (cf. formula 8) ⇒ µ C (x) ≥ min(min(α, β ), µ A (x)).
This property of degree propagation can be generalized to a series of gradual inclusion axioms of the form:

A 1 α 1 G ö A 2 α 2 G ö ... α n-1
G ö A n . Effectively, transitive relationships of the form: A i α G ö A j , where i < j can be interpreted as follows:

∀x : µ A j (x) ≥ min(µ A i (x), α),
where α = min(α i , α i+1 , ..., α j-1 ).

IV. THE ENRICHMENT OF THE FUZZY DLR-LITE WITH THE SQLF LANGUAGE

The SQLf language [START_REF] Bosc | SQLf: A relational database langage for fuzzy querying[END_REF], [START_REF] Bosc | Base de données -Gradualité et imprécision dans les bases de données Ensembles flous, requêtes flexibles et interrogation de données mal connues[END_REF] is an extension of the SQL language to flexible querying by extending its statements to fuzzy conditions. An SQLf query delivers a fuzzy relation r which is a fuzzy set in which the grade of membership of tuple t to the relation r, denoted µ r (t), expresses its level of satisfaction. The closer to 1 µ r (t), the more t is preferred.

The SQLf language is based on the extension of the relational algebra operators to fuzzy conditions. The basic form of an SQLf query (fuzzy restriction) is as follows:

Select [distinct] [n|t|n,t] attributes From relations Where fuzzy cond; The above query returns a set of ranked tuples with their grades of satisfaction, where n is a limitation of the size of the returned set and t ∈]0, 1] is a minimal threshold of satisfaction.

Furthermore, the SQLf language allows more complex statements such as partitioning, fuzzy nesting, division involving fuzzy relations and queries based on fuzzy quantified propositions. These complex statements haven't any boolean counterpart [START_REF] Bosc | Base de données -Gradualité et imprécision dans les bases de données Ensembles flous, requêtes flexibles et interrogation de données mal connues[END_REF].

The limitation of the fuzzy DLR-Lite lies in its inability to express complex preferences. This is due to the fact that abstraction statements, based on SQL queries, do not allow the user to define complex concepts such as "journeys that satisfy almost all important criteria", which is based on a fuzzy quantified proposition.

In order to improve the expressiveness of the fuzzy DLR-Lite knowledge base, we propose the extension of the complex abstraction statements to the SQLf language. So that, it becomes possible to express preferences using complex SQLf statements. We redefine, then, the extended complex abstraction statements as follows:

R 1 → (t 1 , ...,t k )[c s ].sqlf
, where R 1 is a concept from the ontology and sqlf is an SQLf query which delivers a fuzzy relation.

Example 3. The extended complex abstraction statements allow to define concepts and relations corresponding to complex preferences, such as MyFastJourney that corresponds to "journeys having most of steps are fast", which is a fuzzy relation that can be defined by the following extended abstraction statement using an SQLf statement:

MyFastJourneys → (int)[c s ].(Select #Journey From Journey Group By #Journey Having most (#step) are fast(durLink)); p From the semantic point of view, our extension fits in well with the fuzzy DLR-Lite knowledge base and ensures backward compatibility, since the SQLf language covers the SQL language and the fuzzy sets theory is the common formal framework of interpretation of both SQLf queries and axioms of the fuzzy DLR-Lite, which is based on the Gödel fuzzy implication and the t-norm min.

V. ILLUSTRATIVE EXAMPLE

In this section, a sample application is developed in the field of multimodal transportation, in order to show the interests of our approach, and to emphasize the benefit gained from the interpretation of the gradual inclusion axiom, using the Gödel fuzzy implication and the enrichment of the knowledge base with the SQLf language. The main features and the context of the application are described in following subsections.

A. The Context of the application

The considered application is developed in the context of mobile applications. The user terminal is a lightweight terminal which is limited in terms of main storage and processing capabilities. Therefore, the user terminal only embeds a subset of the knowledge base that consists of (i) fuzzy relations defined by the abstraction statements, (ii) fuzzy predicates and (iii) gradual inclusion axioms.

The user can query the embedded application with conjunctive queries which will be evaluated over the available data, based on the gradual inclusion axioms.

We assume that a user interface is provided to define membership functions corresponding to fuzzy concepts. The embedded system can deduce, from the gradual inclusion axioms, the minimal grade of inclusion of the already defined fuzzy concepts in the user-defined fuzzy concepts.

B. An Embedded Multimodal Transport Information System

We design a mobile application in the field of multimodal transportation. The conceptual data model of the system is consistent with the Transmodel standard [START_REF] Carles | Modèle conceptuel de données générique pour la représentation des réseaux intermodaux[END_REF]. Transmodel is an european standard defining a unified conceptual data model of multimodal transport networks which combine bus, tramway, trolley bus and underground networks. Transmodel provides operating data model for network management activities such as timetables, staff, fleet and rolling stock management, real time monitoring and user information circulation.

In practice, travelers are more interested in information about available networks, timetables and services. So, a subset of the database is enough, from the user point of view, to answer his/her queries which are generally about journeys.

For the sake of clarity, the knowledge base of our application is limited to one level of gradual inclusion enriched after that with a user defined fuzzy predicate.

We introduce below the 3 steps for the design of the embedded application: (i) data preprocessing, (ii) querying of the embedded system and (iii) the enrichment of the system.

1) Step 1. Data Preprocessing: Let the following tables be a subset of a database from a multimodal transport information system:

Network, Line, Station, Link and LinkLine. We define the Journey relation as follows: Journey (#journey, #link, departure, arrival, source, destination, duration, DepLink, ArrLink, modeLink, durLink, costLink, comfLink, waitLink).

It is assumed that journeys from source s to destination d are preprocessed.

Based on the SQLf queries, the following fuzzy relations are defined from the Journey relation:

1) TouristJourney → [#Journey].Select #Journey From Journey Group By #Journey Having (most #Link are Touristic); 2) PleasantJourney → [#Journey].Select #Journey From Journey Group By #Journey Having (most #Link are Short(waitLink)); The above extended complex abstraction statements state respectively that a touristic journey is a journey in which most of its steps (named link in the statements) cut across touristic sites and a pleasant journey is a journey in which the waiting time of most of its steps is short. Both touristic and short are fuzzy predicates.

The fuzzy predicate MorningDeparture is also defined by the membership function described in Fig. 2.

The following gradual inclusion axioms could be obtained by a processing using the formula (2) over the database:

• TouristJourney 0.7 G ö MorningDepartureJourney • PleasantJourney 0.8 G ö MorningDepartureJourney Fig. 3: The embedded concepts and data.

2) Step 2. Querying the Embedded System: The data embedded in the user terminal are illustrated in Fig. 3. The fuzzy relations R i,i=1,2 (#Journey) (in the sense of the SQLf language) are resulting from SQLf queries of the extended complex abstraction statements and mapped respectively to fuzzy concepts (relations in the sense of the fuzzy DLR-Lite) TouristJourney et PleasantJourney.

Due to the storage limitation of the user terminal, both the relations R i,i=1,2 only contain the #Journey and the score columns. The membership function of the fuzzy predicate MorningDeparture is also embedded.

The user can query the system based on the embedded fuzzy predicates. The grade of satisfaction to both fuzzy conditions Touristic and pleasant are embedded within the relations R i,i=1,2 . About the fuzzy relation MorningDepartureJourney, a minimal grade of satisfaction can be obtained using the formula (2). For example: ∀t, µ Morning (t) ≥ min(µ Touristic , 0.7) = min(µ R 1 (t), 0.7), and ∀t, µ Morning (t) ≥ min(µ Pleasant (t), 0.8) = min(µ R 2 (t), 0.8). Finally, we can write: ∀t, µ Morning (t) ≥ max(min(µ R 1 (t), 0.7), min(µ R 2 (t), 0.8)). 3) Step 3. Enrichment of the Embedded System: The user can define his/her own fuzzy concepts to express his/her preferences. These concepts could be connected to the previously defined tree structure of concepts in order to personalize the embedded system. The query evaluation process is then made more accurate and close to user expectations.

Example 4. Through the fuzzy concept definition interface, the user can define FavoriteDepartureJourney as a fuzzy concept based on the favorite departure time (see Fig. 4). FavoriteDepartureJourney is then bound to MorningDepar-tureJourney fuzzy concept as follows: MorningDepartureJourney α G ö FavoriteDepartureJourney. The value of α in the above gradual inclusion axiom is α = min t (µ Morning (t) ⇒ G ö µ Favorite (t)) and can be computed from the membership functions of both Morning and Favorite fuzzy predicates as depicted in Fig. 5.

Once the value of α is obtained (α = 0.5 in this example), the embedded system, by applying the propagation property, deduces the grade of gradual inclusion links that bind the added concept to existing ones as described in Fig. 6.

Any query which is about the fuzzy predicate Favorit-eDepartureJourney is evaluated over the available data which covers pleasant and touristic journeys such that: ∀t, µ Favorite (t) ≥ max(min(0.5, µ R 1 (t)), min(0.5, µ R 2 (t))). p

Remark. The deduction of the minimal grade of inclusion of a fuzzy concept in a user-defined fuzzy concept is based on both their respective membership function and the formula:

A α G ö B ⇔ min x (µ A (x) ⇒ G ö µ B (x)) = α. This computation is only significant if the concept B generalizes the concept A (in the same way as concept hierarchies in ontologies) which means that Support(A) ⊆ Support(B). Indeed, if Support(A) Support(B) then the grade of inclusion is equal to 0; which is in fact worthless.

VI. CONCLUSION AND FUTURE WORKS

The flexible querying approach developed in this paper is based on the combination of a fuzzy description logic (denoted fuzzy DLR-Lite) and the SQLf language that allows the expression of more complex fuzzy relations than those could be expressed by the SQL language. An interpretation of the gradual inclusion axiom based on the Gödel fuzzy implication is introduced. This interpretation provides a formal framework in which a restricted form of the negation operator is defined and a generalization to a tree of fuzzy relations is also proposed.

An implementation, based on algorithms for query evaluation introduced in [START_REF] Straccia | Softfacts : a top-k retrieval engine for a tractable description logic accessing relational databases[END_REF], is in progress. It remains the development of an effective algorithm to compute the minimum grade of inclusion of fuzzy concepts added to the knowledge base. We also plan to extend the enrichment process to complex fuzzy predicates as those defined by division involving fuzzy relations.

C

  . Interpretation of the Ontology Axioms O An interpretation of the fuzzy DLR-Lite ontology, denoted I =< ∆, • I >, consists of a finite interpretation domain ∆ and of an interpretation function . I which associates for each relation R (of arity m) an interpretation R I : ∆ m → [0, 1] where R I (c) denotes the grade of membership of the tuple c to the relation R.

Fig. 2 :

 2 Fig. 2: The membership function of the fuzzy predicate Morning.

Fig. 4 :Fig. 5 :

 45 Fig. 4: The membership function of the fuzzy predicate Favorite.

Fig. 6 :

 6 Fig.6: Enrichment of the system.

  which states that the n-ary relation R 1 of the ontology component is mapped into the projection on columns c 1 , ..., c n of the m-ary table R 2 (n ≤ m) each of which is of type t i . The score of the delivered tuples is provided by the column c s . • Complex abstraction statement has the form: R 1 -→ (t 1 , ...,t n )[c s ].sql where R 1 is an n-ary relation of the ontology component and sql is an SQL query which returns the n-ary tuples t 1 , ...,t n ranked in decreasing order of their scores c s .

ACKNOWLEDGMENTS

This work is funded by the Brittany region and the department of Côtes-d'Armor and is partially supported by the National Agency of Research (AOC Ref. ANR-08-CORD-009).


Emmanuel Lassalle
email: emmanuel.lassalle@ens-lyon.org

Pascal Denis Alpage

Leveraging different meronym discovery methods for bridging resolution in French

 for English. In addition, our evaluation indicates that the different meronym extraction methods have a cumulative effect, but that the text pattern-based extraction method is more robust and leads to higher accuracy than the Web-based approach.

Introduction

Bridging descriptions are a special kind of anaphora whose interpretation requires not only identifying an antecedent, but also inferring a specific relation linking it to the anaphor [START_REF] Clark | Bridging[END_REF]. In this paper, we focus on mereological bridging anaphora (that is, cases wherein the inferred relation is a part-whole relation). An illustrative English example is given in (1): [START_REF] Agichtein | Snowball: extracting relations from large plain-text collections[END_REF] The car will not move. The engine is broken.

The resolution of bridging anaphora currently represents one of the most challenging tasks in discourse processing. It is considerably much harder than standard coreferential anaphora resolution for which shallow predictors (like distance, string matching, or morphosyntactic agreement) have been shown to be rather effective [START_REF] Mitkov | Anaphora resolution[END_REF][START_REF] Meng Soon | A machine learning approach to coreference resolution of noun phrases[END_REF][START_REF] Ng | Supervised noun phrase coreference research: The first fifteen years[END_REF]. Part of the challenge is due to an important information bottleneck. Lexical resources like WordNet are still too poor and uneven in coverage to provide a realistic solution [START_REF] Poesio | Resolving bridging references in unrestricted text[END_REF]. In turn, more recent approaches to bridging resolution have turned to web-based extraction methods to fill this "knowledge gap" [START_REF] Bunescu | Associative anaphora resolution: A web-based approach[END_REF][START_REF] Poesio | Learning to resolve bridging references[END_REF]. To date, the most complete and best-performing approach combines focus and lexical distance predictors using machine learning techniques [START_REF] Poesio | Learning to resolve bridging references[END_REF].

While there has been a lot of research on resolving bridging anaphora in English [START_REF] Poesio | Resolving bridging references in unrestricted text[END_REF][START_REF] Vieira | Corpus-based development and evaluation of a system for processing definite descriptions[END_REF][START_REF] Bunescu | Associative anaphora resolution: A web-based approach[END_REF][START_REF] Poesio | Learning to resolve bridging references[END_REF], much fewer work exist for other languages (see [START_REF] Versley | Using the web to resolve coreferent bridging in german newspaper text[END_REF] for an attempt on German). In this paper, we develop a system that performs bridging resolution in French; to our knowledge, this is first such system for this language. Note that languages other than English, the knowledge gap is even wider, since lexical resources are typically scarcer. Our system directly builds upon the system developed for English by [START_REF] Poesio | Learning to resolve bridging references[END_REF], and enriches it in several ways. First, we refine the search engine queries to include a wider range of meronym-holonym extraction patterns (some of them specific to French). Second, and more substantially, we augment the system with an original iterative pattern-based relation extraction method from raw text.

Our system is evaluated on DEDE [START_REF] Gardent | Création d'un corpus annoté pour le traitement des descriptions définies[END_REF], a corpus of French definite descriptions annotated for bridging. Initial experiments indicate that our system achieves performance that compares favorably to those of [START_REF] Poesio | Learning to resolve bridging references[END_REF] for English under the same simple evaluation protocols. We found that the two meronym discovery approaches have a cumulative effect for resolution accuracy, and further comparison between the two methods suggests extraction from raw text is less noisy. But we also show that, when tested in a more realistic setting, the system still has rather low accuracy (at least for French). Our analysis reveals that the current features are still not discriminative enough, which in turns suggests the need for acquiring additional relational data.

The rest of this paper is organized as follows. Section 2 briefly presents the corpus we used. In section 3, we first describe a free lexical database for French, as well as our two methods for extracting meronyms. Section 4 details various experiments wherein we use these different resources for bridging resolution. A detailed comparison of the two extraction methods is given in section 5. Finally, section 6 discusses related work and section 7 offers some conclusions and directions for future work.

DEDE: a French corpus for bridging descriptions

For this study, we use DEDE1 , a French corpus annotated with definite descriptions [START_REF] Gardent | Création d'un corpus annoté pour le traitement des descriptions définies[END_REF], built from Le Monde articles in 1987. The corpus is not only the first of its kind in French with a high agreement rate between annotators, but it also introduces a fine-grained classification of definite descriptions.

The corpus contains 4, 910 descriptions classified in 5 main categories (autonomous, coreferential, associative, situational and non-referential) themselves further divided into subcategories, so that the corpus provides an appropriate resource for evaluating a complete system for processing definite descriptions. As we are solely interested in bridging resolution for now, we only detail the "associative" class (that is bridging).

The "associative" class contains 530 anaphoras of 4 different types (see [START_REF] Gardent | Création d'un corpus annoté pour le traitement des descriptions définies[END_REF] for details): 322 MERO (meronymy, e.g. a tree/the trunk ), 87 CIRC (modifiermodified relation, e.g. Paris/the region), 97 REL (predicate-argument, e.g. two robbers/the attack ), 24 MOD (relation introduced by a modifier e.g. in July/the next month). The MERO subclass involves 296 distinct holonym-meronym pairs. It is worth noticing that the MERO subclass of DEDE collapses together several kinds of part-whole relation: it contains classical component-object relations (e.g., trunk/tree), unnecessary parts (e.g., wine/diner ), and functions (e.g., mayor/city).

Some of bridging relations involve a proper name as antecedent such as: steering committee/La Société Générale. That should be taken into account in resolution. For more details on part-whole relations, please refer to [START_REF] Winston | A taxonomy of partwhole relations[END_REF][START_REF] Kleiber | L'anaphore associative[END_REF].

Methods for meronymy extraction

Having access to lexical and encyclopedic knowledge is an essential ingredient for resolving definite bridging, for it is precisely the existence of an inferable relation that permits bridging. Static databases like WordNet suffer from a low coverage impacting the performance in bridging resolution. In French, similar databases are even smaller than in English, which further motivates the need for automatic lexical relation extraction methods. Another point is that bridging relations do not always correspond to a lexical relation (e.g. fragment/pot, about archaeology) so that we cannot expect to find some of those relations in a static lexicon, but perhaps in texts if their usage is frequent enough.

A static lexical database

As there is no free equivalent to the Princeton WordNet2 for French, we use the WOLF database3 [START_REF] Sagot | Construction d'un wordnet libre du français à partir de ressources multilingues[END_REF], a resource built from WordNet and several multilingual resources. It has a total of 32, 351 synsets, which is more than the French EuroWordNet (22, 121 synsets), but much less than English WordNet (177, 659 synsets). Crucially, WOLF only covers 2.7% of meronyms in DEDE, whereas WordNet covers 38.8% of the corpus used in [START_REF] Poesio | Resolving bridging references in unrestricted text[END_REF]. We will see during the experiment that the contribution of this resource in bridging resolution is very small because of this low coverage. In particular, many lexical distance calculations will be impossible because of this low coverage.

Querying meronyms from the Web

Recent approaches to bridging resolution compensate the lack of lexical data by using web-based methods [START_REF] Bunescu | Associative anaphora resolution: A web-based approach[END_REF][START_REF] Poesio | Learning to resolve bridging references[END_REF] (see also [START_REF] Markert | Using the web for nominal anaphora resolution[END_REF][START_REF] Markert | Comparing knowledge sources for nominal anaphora resolution[END_REF] for related tasks). The idea is to query a search engine for syntactic patterns taken to instantiate a particular lexical relation, and use the number of hits returned as an estimate of the plausibility of that relation. In English, the pattern mostly used to instantiate meronymy is "the X of the Y".

We also adopt this method (using Yahoo! 4 ), with some modifications. In French, the equivalent of "the X of the Y" has different realizations depending on the grammatical genders and numbers of X and Y. Because we used lemmatized lexical heads, we only took singular Xs and Ys5 , which gives the three initial patterns: "le X du/de/de la Y".

Because the first patterns are not in one-to-one correspondence with the meronymy relation, we defined another set of nine syntactical patterns, based on the possessive. Our purpose is to combine them to obtain less noisy results. Different settings can be applied to combine the patterns, whether we want a better coverage or a better precision: we set a threshold that corresponds to a minimum of nonzero matches among all the patterns required to accept a meronym candidate. In our experiments, meronym candidates are (potential antecedent, anaphora) pairs for the MERO class of DEDE. The Web-based method has a very high coverage: with a threshold set at value 1, 92.9% of all meronyms were positively identified (=275/296 different meronyms in DEDE, or 292/322 annotated bridges). We will give more detailed results in section 5.

Extracting meronyms from raw text

To further alleviate the "knowledge gap", we set up a system that iteratively extracts lexical relations and corresponding syntactic patterns from raw text. This type of approach has proven quite efficient on problems similar to bridging [START_REF] Markert | Comparing knowledge sources for nominal anaphora resolution[END_REF][START_REF] Berland | Finding parts in very large corpora[END_REF][START_REF] Hearst | Automatic acquisition of hyponyms from large text corpora[END_REF][START_REF] Snow | Learning syntactic patterns for automatic hypernym discovery[END_REF]. Although it was developed independently, our system is most similar to [START_REF] Agichtein | Snowball: extracting relations from large plain-text collections[END_REF] in the sense that it alternatively extracts syntactic patterns and pairs. However, we enhance the system by considering two kinds of pattern: (i) linear patterns (i.e., a n-gram between 2 words) as well as (ii) dependency patterns (i.e., a path between 2 words in the dependency tree). In the latter case, we use two kinds of pattern (common ancestor or domination, see figure 1). We used a preprocessed corpus of 142M words from newspaper L'Est Républicain 6 . The system starts from a database of meronyms and syntactic patterns (linear or in dependencies) and iteratively extracts new pairs and patterns to enrich the initial database. To avoid to noisy results, we only retain pairs of nouns appearing within two patterns or more (about 50, 000 pairs). We also discard all pairs of patterns occurring less than a threshold of 5 (an empiric value). The system was initialized with two different types of seed data. When starting with a small set of manually crafted pairs and patterns, it retrieved 0.5% (=54) of meronyms in WOLF and 11.5% (=34) of meronyms in DEDE. When launched with the known meronyms in WOLF (with no patterns), the system was able to retrieve up to 16.2% (=48/296 different meronyms in DEDE, or 57/322 annotated bridges) of distinct meronyms in DEDE (by extracting 135 linear patterns and 42 dependency patterns), a much better coverage than WOLF but well below the Web-based method. This will be the final setting for our resolution system. A more restrictive selection of extracted pairs (e.g. with a ranking method like in [START_REF] Agichtein | Snowball: extracting relations from large plain-text collections[END_REF]) would have reduced that coverage (some of DEDE meronyms were not found frequently by the system). But our purpose was mainly to reach an acceptable coverage while still filtering noisy pairs. Section 5 provides further comparison between the two extraction methods.

Experiments on bridging resolution

4.1 Task and system setup Our system performs the following task: given a definite description known to be a meronymic bridging anaphora, find its correct antecedent among previously occurring NPs. We avoid the complete inference task on DEDE (jointly resolving bridging and coreference, finding the lexical relation, and the antecedent) to fully evaluate the performances of the system (and extraction methods) on meronymy.

Our system relies heavily on [START_REF] Poesio | Learning to resolve bridging references[END_REF]. This system uses standard classification techniques to combine focus features (such utterance distance and first-mentionhood) and lexical features (scores calculated from WordNet and Google results). Our feature set (see Table 1) enriches that of [START_REF] Poesio | Learning to resolve bridging references[END_REF] with new lexical features, and an extra salience feature (salience is enriched by the grammatical function of the antecedent). WOLF is used to calculate lexical similarity and directly as a meronymy database. Extracted relations are used as a database (with an associated Yahoo! score for the Web-based method). Like [START_REF] Poesio | Learning to resolve bridging references[END_REF], we have experimented with a naive Bayes and multi-layer perceptron classifier, but we found no significant differences in performance. Results will therefore be reported only for the naive Bayes classifier (for which distances are modelled by exponential laws, and Yahoo! scores by a Gaussian).

Corpus preprocessing

DEDE corpus was preprocessed in several ways. First, we recovered accentuations: these were absent from the released texts. We performed NPs chunking (with TreeTagger7 ), as well as dependency parsing (using MSTParser8 ). We also separated texts in much finer and balanced documents than the originals (original documents contain several articles with non-related topics). All NP chunks that precede an anaphor in the text are considered as potential antecedents.

Evaluation and results

We use two different types of evaluation procedures. For comparison, we first follow the evaluation protocol of [START_REF] Poesio | Learning to resolve bridging references[END_REF] and first report accuracy figures for positive and negative instances classification (all results were obtained by doing 5-fold cross-validations). Under this evaluation we obtain from 88.12% (salience only) to 90.0% (all features) 9 . These high scores come in part from the rareness of the bridging relation, and in turn the overwhelming number of negative instances. Recall on positives was around 76% with salience features, and lexical features did not bring any significant improvement.

baseline accuracy accuracy in [START_REF] Poesio | Learning to resolve bridging references[END_REF] random (previous) mention A second, more realistic evaluation consists in evaluating the accuracy in finding the correct antecedent for a given bridging anaphora. For comparison, we used various baselines similar to those in [START_REF] Poesio | Learning to resolve bridging references[END_REF]. As shown in table 2, the accuracy rates are consistently much lower than for equivalent baselines on Poesio et al.'s corpus, suggesting that the number of potential antecedents is probably much higher in DEDE corpus than the corpus used in [START_REF] Poesio | Learning to resolve bridging references[END_REF]. Note that the low score of the baseline based on Yahoo! score suggests that the number of hits is not necessarily a good indicator. We tested our system by successively adding features to the classifier (see table 3). First, note that the salience features make the system better than the baselines. Lexical features increase performance, and the different lexical resources appear to have a cumulative effect on performance (suggesing that they are somehow complementary). Under this evaluation, our best system obtains an overall accuracy of 23.6%, which is significantly lower than the scores reported by [START_REF] Poesio | Learning to resolve bridging references[END_REF] on their corpus10 but comparatively much better than the baselines 11 . The results were almost the same when ignoring Yahoo! scores and using extracted meronyms as a database (with a threshold on Yahoo! score to filter noisy pairs).

Error analysis

Preliminary error analysis reveals that (i) the correct antecedent was in the top 10 candidates (out of 206 on average) in 66, 5% of cases; (ii) many errors are due to selecting an antecedent with the same lexical head as the true one; (iii) the system fails in most cases where the antecedent is a proper name12 ; (iv) the system sometimes selects a meronym of the true antecedent (e.g. room/first floor/hotel ). These results suggest that current features are still not discriminative enough, and point to a need for acquiring additional relational data using a more accurate model for selecting new pairs and patterns.

Web-based method vs. extraction from text

In order to gain a better understanding of the influence of the different meronym extraction methods on resolution, we perform some additional evaluation. When setting up the two methods, we were mainly concerned with maximizing coverage (to make up for the lack of coverage of WOLF). On that metric alone, the webbased extraction technique clearly outperforms both WOLF and the raw text extraction. Given that the two approaches produce noisy results, we also have to compare them on the basis of precision.

The evaluation protocol we propose is simple: all pairs (potential antecedent, anaphora) of DEDE are tested as meronym candidates (there are 45, 605 different pairs). A pair is marked as positive if it has been extracted by the method, and negative otherwise. Only meronyms marked in DEDE are considered true positives, and all the other pairs are negatives. We aware that this evaluation clearly over-estimates the number of false positives, but the point is meronyms that are not marked in DEDE are a small portion of all possible pairs and the aim of this test is to compare the noise of our two methods.

Looking first at the web-based approach, we compared extracted pairs to DEDE meronyms. For this, we considered a pair to be extracted if its Yahoo! score was above an arbitrary threshold. First, we tested all patterns separately and grouped them by gender variation (results in table 4). French translations of "the X of the Y" ("X du/de l'/de la Y") have the best coverage but one of the lowest precision. Patterns based on the possessive have a low coverage but they also less noisy. Finally, patterns obtaining the best F1-score are "X et son/et sa Y".

Next we defined a more restrictive criterion to classify meronyms: a pair is classified as a meronym if it has been observed by the search engine with strictly more than x patterns, x being a parameter that varies from 0 to 11 13 . From the precision, recall and F1 values given in table 5 we see that combining the patterns leads to a better F1-score than using patterns separately: at x = 7, the F1-score has doubled (5.10%) compared to the best F1-score for isolated patterns. This motivates the use of several patterns with the web-based method. Now turning to meronyms extracted from raw text (using the settings mentioned in section 3, we found 48 true positives and 1, 096 false positives, which gives a precision of 4.20%, a recall of 16.22%, and reaches a F1 of 6.66%, which is better than the F1-score for all settings of the web-based method (the comparison is acceptable because, as mentioned in section 4, Yahoo! scores do not have a strong influence on the performances of our resolution system compared to using a threshold on it and considering extracted pairs as a lexical database). Extracting meronyms from text seems not only less noisy than web-based methods, but it also has the advantage of being faster than web queries, and the possibility to exploit more information (e.g. dependency parses or contextual information).

Related work

Bridging anaphora resolution was investigated by [START_REF] Vieira | Corpus-based development and evaluation of a system for processing definite descriptions[END_REF][START_REF] Poesio | Learning to resolve bridging references[END_REF][START_REF] Bunescu | Associative anaphora resolution: A web-based approach[END_REF][START_REF] Versley | Using the web to resolve coreferent bridging in german newspaper text[END_REF], among others. Earlier systems were rule-based, while more recent ones use machine-learning techniques. We can find similar work (web-based methods) on similar problems such as nominal anaphora [START_REF] Markert | Using the web for nominal anaphora resolution[END_REF] and metonymy [START_REF] Nastase | Combining collocations, lexical and encyclopedic knowledge for metonymy resolution[END_REF]. [START_REF] Poesio | Acquiring lexical knowledge for anaphora resolution[END_REF] points out the problem of lack of knowledge with static lexical resources on bridging anaphora resolution and examines the contribution of lexical extraction techniques on this task.

Pattern-based lexical relation extraction from raw text dates back to [START_REF] Hearst | Automatic acquisition of hyponyms from large text corpora[END_REF], but fully automatic methods have now become available [START_REF] Agichtein | Snowball: extracting relations from large plain-text collections[END_REF]. Recently, many advances have been made in open information extraction [START_REF] Wu | Open information extraction using wikipedia[END_REF][START_REF] Zhu | Statsnowball: a statistical approach to extracting entity relationships[END_REF][START_REF] Hoffmann | Learning 5000 relational extractors[END_REF] and can be also applied to discovering lexical relations.

Extraction of relations from the Web using patterns were used in bootstrapping methods for discovering named entities or relations [START_REF] Brin | Extracting patterns and relations from the world wide web[END_REF][START_REF] Etzioni | Unsupervised namedentity extraction from the web: an experimental study[END_REF] as well as directly in the resolution of problems requiring lexical knowledge [START_REF] Bunescu | Associative anaphora resolution: A web-based approach[END_REF][START_REF] Poesio | Learning to resolve bridging references[END_REF][START_REF] Markert | Using the web for nominal anaphora resolution[END_REF][START_REF] Markert | Comparing knowledge sources for nominal anaphora resolution[END_REF].

Conclusion and perspectives

We have set up and compared two approaches for extracting meronyms. We have improved the web-based method for French by using several patterns and combining them, and we have developed an original method pattern-based extraction method from raw text. We have then used the acquired lexical data as features in a system for resolving bridging anaphora in the case of a part-whole relation. In the system, salience is a very relevant feature to localize antecedent in a region (in restricting the antecedent space), while lexical features must provide a better precision in this region to find the actual antecedent. However, our results show that current methods for discovering meronyms are still not sufficient to get reach good results in the resolution process. Finally, we have shown that the web-based method, even when it combines several syntactic patterns, is more noisy that extraction from raw text although it provides a wider coverage.

Improving the resolution system will first require more accurate data, both lexical and encyclopedic. In fact, some of the required data, such as proper nouns classes, can be retrieved from Wikipedia, and some other data, like lexical relations between common nouns, might be inferred by relational learning. Then, transforming Wikipedia into an ontology (like in [START_REF] Strube | Wikirelate! computing semantic relatedness using wikipedia[END_REF][START_REF] Nastase | Wikinet: A very large scale multi-lingual concept network[END_REF]) and relational learning become central issues for a proper treatment of bridging. While the improvement of web-based methods appears limited, there are more possible extensions in relational learning that can be applied to text pattern-based methods. We now plan to extend these techniques and apply them to definite bridging processing.

Fig. 1 .

 1 Fig. 1. Two types of dependency pattern.

Fig. 2 .

 2 Fig. 2. Our system for extracting meronyms.

Table 1 .

 1 Feature set (a is the anaphora and p a potential antecedent).

	group	feature	description	type
		utterance distance	# of sentences separating p and a	num
	salience	NPs distance "is first mention"	# of NPs separating p and a p is the first mention of a sentence	num bool
		grammatical function the function of p (sub, obj, dep, ...)	class
	known relations	WOLF meronyms extracted meronyms	(a,p) is a meronymy in WOLF (a,p) is an extracted meronymy	bool bool
	lexical distance	WOLF distance	L(ShortestP ath(a,p)) L(M axLengthP ath(a,p)) or 0 if no path	num
	search engine	Yahoo! score	number of pages, on 12 patterns	num/bool

Table 2 .

 2 Baselines comparison with[START_REF] Poesio | Learning to resolve bridging references[END_REF]

	1.7%	-

Table 3 .

 3 Overall resolution accuracy results.

	features	accuracy
	salience	7.9%
	+ WOLF (distance/meronyms)	12.6%
	+ Yahoo! score	22.4%
	+ extracted meronyms	23.6%

Table 4 .

 4 testing patterns independently on DEDE meronyms (best results were boldfaced)

		TP	FP	prec.	recall	F1-score
	X d'Y	74	6904	1.06 %	25.00 %	2.03 %
	X de Y	245	29081	0.84 %	82.77 %	1.65 %
	comb.	248	29781	0.83 %	83.78 %	1.64 %
	X du Y	165	16159	1.01 %	55.74 %	1.99 %
	X de l'Y	69	6924	0.99 %	23.31 %	1.89 %
	X de la Y	135	13383	1.00 %	45.61 %	1.95%
	comb.	252	28760	0.87 %	85.14 %	1.72 %
	Y dont le X	72	5749	1.24 %	24.32 %	2.35 %
	Y dont l'X	38	2949	1.27 %	12.84 %	2.31 %
	Y dont la X	47	3731	1.24 %	15.88 %	2.31 %
	comb.	144	12008	1.18 %	48.65 %	2.31 %
	Y et son X	100	7483	1.32 %	33.78 %	2.54 %
	Y et sa X	41	3569	1.14 %	13.85 %	2.10 %
	comb.	136	10858	1.24 %	45.95 %	2.41 %
	X de son Y	98	7602	1.27 %	33.11 %	2.45 %
	X de sa Y	33	4175	0.78 %	11.15 %	1.47 %
	comb.	129	11189	1.14 %	43.58 %	2.22 %

Table 5 .

 5 testing patterns combinations on DEDE meronyms (best results were boldfaced)

		TP	FP	prec.	recall	F1-score
	# patterns > 0	275	34319	0.79 %	92.91 %	1.58 %
	# patterns > 1	246	27664	0.88 %	83.11 %	1.74 %
	# patterns > 2	193	19661	0.97 %	65.20 %	1.92 %
	# patterns > 3	150	12718	1.17 %	50.68 %	2.28 %
	# patterns > 4	116	7569	1.51 %	39.19 %	2.91 %
	# patterns > 5	72	3926	1.80 %	24.32 %	3.35 %
	# patterns > 6	36	1452	2.42 %	12.16 %	4.04 %
	# patterns > 7	20	469	4.09 %	6.76 %	5.10 %
	# patterns > 8	7	100	6.54 %	2.36 %	3.47 %
	# patterns > 9	0	14	0 %	0 %	-
	# patterns > 10	0	4	0 %	0 %	-
	# patterns > 11	0	0	-	0 %	-

http://www.cnrtl.fr/corpus/dede/

http://wordnet.princeton.edu/

https://gforge.inria.fr/projects/wolf/

http://developer.yahoo.com/search/boss/

Another reason is the time it takes to query a search engine with meronym candidates: for all the patterns we used, it took more than a week.

[START_REF] Clark | Bridging[END_REF] http://www.cnrtl.fr/corpus/estrepublicain/

http://www.ims.uni-stuttgart.de/projekte/corplex/TreeTagger/

We used the retrained version of the MSTParser[START_REF] Mcdonald | Online largemargin training of dependency parsers[END_REF] described in[START_REF] Candito | Benchmarking of statistical dependency parsers for french[END_REF].

The best score obtained in[START_REF] Poesio | Learning to resolve bridging references[END_REF] among several classifier is 79.3%

They report an impressive 92.5%, but their evaluation protocol consists in finding the correct antecedent for 6 anaphora randomly chosen in the evaluation set, which is absolutely not significant if not repeated a large number of times (but in that case, cross-validations would be wiser).

Baselines are the only point of comparison we can have with[START_REF] Poesio | Learning to resolve bridging references[END_REF] on this task.

Proper nouns antecedents require a two steps inference (e.g. identify Technip as a company, identify the meronymy employees/company).

Acknowledgments

We thank the DAARC 2011 anonymous reviewers for their helpful comments.


J Rynkiewicz

General bound of overfitting for MLP regression models

Multilayer perceptrons (MLP) with one hidden layer have been used for a long time to deal with non-linear regression. However, in some task, MLP's are too powerful models and a small mean square error (MSE) may be more due to overfitting than to actual modelling. If the noise of the regression model is Gaussian, the overfitting of the model is totally determined by the behavior of the likelihood ratio test statistic (LRTS), however in numerous cases the assumption of normality of the noise is arbitrary if not false. In this paper, we present an universal bound for the overfitting of such model under weak assumptions, this bound is valid without Gaussian or identifiability assumptions. The main application of this bound is to give a hint about determining the true architecture of the MLP model when the number of data goes to infinite. As an illustration, we use this theoretical result to propose and compare effective criteria to find the true architecture of an MLP.

Introduction

Feed-forward neural networks are well known and popular tools to deal with non-linear regression models. We can describe MLP models as a parametric family of regression functions. White [START_REF] White | Artificial Neural Networks: Approximation and Learning Theory[END_REF] reviews statistical properties of MLP estimation in detail. However he leaves an important question pending i.e. the asymptotic behavior of the estimator when the MLP in use has redundant hidden units. If we assume that the noise is Gaussian it is well known that the Least square Estimator (LSE) and the maximum likelihood estimator (MLE) are equivalent and Amari et al. [START_REF] Amari | Singularities affect dynamics of learning in Neuromanifolds[END_REF] give several examples of the behavior of MLE in case of redundant hidden units. Moreover, if n is the number of observations, Fukumizu [START_REF] Fukumizu | Likelihood ratio of unidentifiable models and multilayer neural networks[END_REF] shows that, for unbounded parameters and Gaussian noise, LRTS can have an order lower bounded by O(log(n)) instead of the classical convergence property to a χ 2 law. In the same spirit, Hagiwara and Fukumizu [START_REF] Hagiwara | between weight size and degree of over-fitting in neural network regression[END_REF] investigate relation between LRTS divergence and weight size in a simple neural networks regression problem. Hence, if parameters of MLP models are not bounded, these papers show that, for Gaussian noise, the overfitting is strong, even if the number of data is large. Note that this is no more the case if the parameters of the MLP are supposed to be a priori bounded.

But, even if Gaussian assumption for the noise is standard, it may be not suitable for some models. This assumption is false, for example, when the range of observations is known to be bounded, since Gaussian variables can be arbitrary large in absolute value, even if the probability of such events is small. Hence, we need a theory which gives evaluation of the overfitting of MLP regression without knowing the density of the noise and which works even if the model is not identifiable.

In this paper, we prove an inequality bounding the MSE difference between the true model and an over-determined model. This inequality shows that, under suitable assumptions, the asymptotic overfitting of the MSE is upper bounded by the maximum of the square of a Gaussian process. Moreover, this bound shows that suitably penalized MSE criteria allow to select asymptotically the true model. The paper is organized as follows: In section 2 we state the model, section 3 presents our main inequality and in section 4 we apply this inequality to select the optimal architecture of the MLP model. Finally, in section 5, a little experiment gives us some insight to apply this theoretical results in real life problems.

The model

Let x = (x(1), • • • , x(d))
T ∈ R d be the vector of inputs and w i := (w i1 , • • • , w id ) T ∈ R d be a parameter vector for the hidden unit i. The MLP function with k hidden units can be written :

f θ (x) = β + k i=1 a i φ w T i x + b i , with θ = (β, a 1 , • • • , a k , b 1 , • • • , b k , w 11 , • • • , w 1d , • • • , w k1 , • • • , w kd
) the parameter vector of the model and φ a bounded transfer function, usually a sigmoïdal function. Note that we consider only real functions, extension to vectorial functions is straightforward but not discussed in this paper. Let Θ k ⊂ R k×(d+2)+1 be a compact (i.e. closed and bounded) set of possible parameters, we consider regression model

S = {f θ (y, x), θ ∈ Θ k } with Y = f θ (X) + ε (1)
X is a random input variable and ε is the noise of the model. Let n be a strictly positive integer, we assume that the observed data (x 1 , y 1 ) ,

• • • , (x n , y n ) come from a true model (X i , Y i ) i∈N,i>0
of which the true regression function is f θ 0 , for an θ 0 (possibly not unique) in the interior of Θ k .

Estimation of MLP regression model

The main goal of non-linear regression is to give an estimation of the true parameter θ 0 based on observations ((x 1 , y 1 ), • • • , (x n , y n )). This can be done by minimizing the Mean Square Error (MSE) function:

E n (θ) := 1 n n t=1 (y t -f θ (x t )) 2 (2)
with respect to parameter vector θ ∈ Θ k . The parameter vectors θn realizing the minimum will be called Least Square Estimator (LSE). Note that parameters realizing the true distribution function may belong to a non-null dimension sub-manifold if the number of hidden units is overestimated. Suppose, for example, we have a multilayer perceptron with two hidden units and the true function f θ 0 is given by a perceptron with only one hidden unit, say f θ 0 = a 0 tanh(w 0 x), with x ∈ R. Then, any parameter θ in the set:

{θ |w 2 = w 1 = w 0 , b 2 = b 1 = 0, a 1 + a 2 = a 0 }
realizes the function f θ 0 . Hence, classical statistical theory for studying the LSE can not be applied because it requires the identification of the parameters (up to a permutation).

In the next section, we will compare MSE of over-determined models against MSE of the true model :

1 n n t=1 (y t -f θ (x t )) 2 - 1 n n t=1 (y t -f θ 0 (x t )) 2 = E n (θ) -E n (θ 0 ). ( 3
)

A general bound for the MSE

For an square integrable function g(X, Y ) the L 2 norm is:

g(X, Y ) 2 := g 2 (x, y)dP (x, y). (4)
Now, for λ > 0, let us define the generalized derivative function :

d λ θ (X, Y ) = e -λ(Y -f θ (X)) 2 -e -λ(Y -f θ 0 (X)) 2 e -λ(Y -f θ 0 (X)) 2 e -λ(Y -f θ (X)) 2 -e -λ(Y -f θ 0 (X)) 2 e -λ(Y -f θ 0 (X)) 2 2 = e -λ((Y -f θ (X)) 2 -(Y -f θ 0 (X)) 2 ) -1 e -λ((Y -f θ (X)) 2 -(Y -f θ 0 (X)) 2 ) -1 2
(5) and let us define d λ θ -(x, y) = min 0, d λ θ (x, y) . Note that the generalized derivative function converges toward the derivative function if θ converges toward θ 0 .

For now, let us assume that d λ θ is well defined, this point will be discuss later. We can state the following inequality:

Inequality : for λ > 0, sup θ∈Θ k n • E n (θ 0 ) -E n (θ) ≤ 1 2λ sup θ∈Θ k n i=1 d λ θ (x i , y i ) n i=1 d λ θ 2 -(x i , y i ) (6)
Proof :

We have

n • (E n (θ 0 ) -E n (θ)) = 1 λ n i=1 log 1 + e -λ(Y -f θ (X)) 2 -e -λ(Y -f θ 0 (X)) 2 e -λ(Y -f θ 0 (X)) 2 2 d λ θ (x i , y i ) ≤ sup 0≤p≤ e -λ(Y -f θ (X)) 2 -e -λ(Y -f θ 0 (X)) 2 e -λ(Y -f θ 0 (X)) 2 2 1 λ n i=1 log 1 + pd λ θ (x i , y i ) ≤ sup p≥0 1 λ p n i=1 d λ θ (x i , y i ) -p 2 2 n i=1 d λ θ 2 -(x i , y i ) .
Since for any real number u, log(1 + u) ≤ u -1 2 u 2 -. Finally, replacing p by the optimal value, we found

n • (E n (θ 0 ) -E n (θ)) ≤ 1 2λ n i=1 d λ θ (x i ,y i ) n i=1 (d λ θ ) 2 - (x i ,y i )
This inequality allows to prove the tightness of n• (E n (θ 0 ) -E n (θ)) under simple assumptions. It is used in the next section to prove consistency of an estimator of the number of hidden units using penalized MSE criterion.

4 Estimation of the number of hidden units.

Let k 0 be the minimal number of hidden units needed to realize the true regression function f θ 0 . In this section, the set Θ of possible parameters will be set to Θ = ∪ K k=1 Θ k , where K is a, possibly huge, fixed constant: The maximum number of hidden units for MLP models. We define the minimum-penalized MSE estimator of k 0 , as the minimizer k of

T n (k) = min θ∈Θ (E n (θ) + a n (k)) (7)
Let us assume the following assumptions:

(A1) a n (.) is increasing, n • (a n (k 1 ) -a n (k 2 )
) tends to infinity as n tends to infinity, for any k 1 > k 2 and a n (k) tends to 0 as n tends to infinity for any k.

(A2) It exists λ > 0 so that d λ θ , θ ∈ Θ is a Donsker class (see van der Vaart [START_REF] Van Der | Asymptotic statistics[END_REF]) and appendix.

We now have: Theorem: Under (A1) and (A2), k converges in probability to the true number of hidden units k 0 . Proof : By applying the inequality,

P ( k > k 0 ) ≤ K k=k 0 +1 P (T n (k) ≥ T n (k 0 )) = K k=k 0 +1 P n sup θ∈Θ k 0 E n (θ) -sup θ∈Θ k E n (θ) ≥ n (a n (k) -a n (k 0 )) ≤ K k=k 0 +1 P 1 λ sup θ∈Θ k n i=1 d λ θ (x i ,y i ) n i=1 (d λ θ ) 2 - (x i ,y i ) ≥ n (a n (k) -a n (k 0 ))
Now, under (A2)

sup θ∈Θ k 1 n n i=1 d λ θ (x i , y i ) 2 = O P (1)
where, O p (1) means bounded in probability. Moreover, under (A2) the set

d λ θ (x i , y i ) 2
is Glivenko-Cantelli (the set admits an uniform law of large numbers). Hence inf

θ∈Θ k 1 n n i=1 d λ θ (x i , y i ) 2 - n→∞ -→ inf θ∈Θ k d λ θ (X, Y ) - 2 2 But inf θ∈Θ k d λ θ (X, Y ) -2 > 0, since the random variable d λ θ (X, Y ) is cen- tered and d λ θ (X, Y ) 2 = 1.
Then, we get :

1 λ sup θ∈Θ k n i=1 d λ θ (x i , y i ) n i=1 d λ θ 2 -(x i , y i ) = O P (1)
and P ( k > k 0 ) tends to 0 as n tends to infinity. Finally,

P ( k < k 0 ) ≤ k 0 -1 k=1 P sup θ∈Θ k E n (θ) -E n (θ 0 ) n ≥ a n (k) -a n (k 0 ) n and sup θ∈Θ k En(θ)-En(θ 0 ) n converges in probability to sup θ∈Θ k E E n (θ) -E n (θ 0 ) < 0 since k < k 0 , so k P -→ k 0
The assumption (A1) is fairly standard for model selection, in the Gaussian case (A1) will be fulfilled by the BIC criterion. The assumption (A2) is more difficult to check. First we note:

e -λ((Y -f θ (X)) 2 -(Y -f θ 0 (X)) 2 ) -1 2 = e -2λ((Y -f θ (X)) 2 -(Y -f θ 0 (X)) 2 ) -2e -λ((Y -f θ (X)) 2 -(Y -f θ 0 (X)) 2 ) + 1 So, d λ θ is well defined if E e -2λ((Y -f θ (X)) 2 -(Y -f θ 0 (X)) 2 ) < ∞, but (Y -f θ (X)) 2 -(Y -f θ 0 (X)) 2 = (Y -f θ 0 (X) + f θ 0 (X) -f θ (X)) 2 -(Y -f θ 0 (X)) 2 = 2ε(f θ 0 (X) -f θ (X)) + (f θ 0 (X) -f θ (X)) 2
where ε = Yf θ 0 (X) is the noise of the model. Since an MLP function is bounded, d λ θ is well defined if λ > 0 exists such that e λ|ε| < ∞ i.e. ε admits exponential moments. Finally, using the same techniques of reparameterization as in Rynkiewicz [START_REF] Rynkiewicz | Consistent estimation of the architecture of multilayer perceptrons[END_REF], assumption (A2) can be shown to be true for MLP models with sigmoïdal transfer functions, if the set of possible parameters Θ is compact.

A little experiment

The theoretical penalization terms of the previous section can be chosen among a wide range of functions (see condition A1). In the sequel, a little experiment is conducted to assess the right rate of penalization to guess the "true" architecture of a model.

Consider a simulated model:

Z t = F θ 0 (X t , Y t ) + ε t , t = 1, • • • , n, with ((X 1 , Y 1 ), • • • , (X n , Y n )) i.i.d., (X t , Y t ) ∼ N (0 R 2 , 3 • I 2 ), (ε 1 , • • • , ε n ) i.i.d., ε t ∼ U [-1, 1]
, the uniform law in [-1; 1] and

F θ 0 (x, y) = tanh(6 • x -2 • y) + 2 • tanh(8 -x + 3 • y) -3 • tanh(2 -6 • x -2 • y) + 1.5. (8)
Here, the true model is an MLP with 2 inputs, 3 hidden units and one output.

In order to avoid too long time of computation, the number of hidden units is assumed to be between 1 and 10. We estimate the true architecture of the MLP according to [START_REF] Van Der | Asymptotic statistics[END_REF]. First, let us write the log-likelihood of the data as if the density of the noise would be Gaussian :

l θ     x 1 y 1 z 1   , • • • ,   x n y n z n     = -n 2 • log(2πσ 2 ) -n t=1 1 2σ 2 (z t -F θ (x t , y t )) 2 + n t=1 g(x t , y t ) (9)
Here, we assume that the variance of the noise σ 2 is a known constant and that the density of the explicative variables (X, Y ) is a function g(., .) independent of the parameter vector θ. Two classical criteria are:

AIC : n t=1 1 σ 2 (z t -F θ (x t , y t )) 2 + 2 • D + Cte BIC : n t=1 1 σ 2 (z t -F θ (x t , y t )) 2 + D • log(n) + Cte (10)
where D is the size of the parameter vector (the dimension of the model or the number of weights of the MLP) and Cte a constant independent of the parameter θ.

The optimization of the log-likelihood is done with respect to the parameter θ, so maximimizing this quantity is equivalent to minimizing :

E n (θ) = 1 n • n t=1 (z t -F θ (x t , y t )) 2 (11)
Hence, an AIC like minimum-penalized MSE criterion would be:

1 n n t=1 (z t -F θ (x t , y t )) 2 + 2σ 2 D n
and, a BIC like minimum-penalized MSE criterion would be:

1 n n t=1 (z t -F θ (x t , y t )) 2 + σ 2 D log(n) n
Note, that these criteria involve the knowledge of the variance of the noise σ 2 . In a first experiment we will use the true variance of the noise, then this problem will be addressed in the following sections.

In the following sections, the optimization of MLP is done with the Broy-denFletcherGoldfarbShanno (BFGS) method. In order to avoid bad local minima, 10 random initializations of the weights are done for each estimation.

Model selection with σ 2 known

We will compare 4 criteria, from the least penalized (AIC like) to the most penalized (Very Strong Penalization), the following penalized criteria are assessed:

• AIC like: 1 n n t=1 (z t -F θ (x t , y t )) 2 + 2σ 2 D n • BIC like: 1 n n t=1 (z t -F θ (x t , y t )) 2 + σ 2 D log(n) n • SP (Strong Penalization): 1 n n t=1 (z t -F θ (x t , y t )) 2 + σ 2 D √ n n • VSP (Very Strong Penalization): 1 n n t=1 (z t -F θ (x t , y t )) 2 + σ 2 Dn 3/4 n
We simulate n = 100, n = 500 and n = 1000 data according to the true model ( 8), for each n the experiment is repeated 100 times.

The following architectures are chosen by the penalized criteria :

• n=100 nb h. units 1 2 3 4 5 6 7 8 9 10 AIC like models sel. 0 0 47 35 10 2 3 3 0 0 BIC like models sel. 0 0 100 0 0 0 0 0 0 0 SP models sel. 0 0 100 0 0 0 0 0 0 0 VSP models sel. 0 74 26 0 0 0 0 0 0 0

• n=500 nb h. units 1 2 3 4 5 6 7 8 9 10 AIC like models sel. 0 0 3 14 17 14 13 15 10 13 BIC like models sel. 0 0 100 0 0 0 0 0 0 0 SP models sel. 0 0 100 0 0 0 0 0 0 0 VSP models sel. 0 1 99 0 0 0 0 0 0 0

• n=1000 nb h. units 1 2 3 4 5 6 7 8 9 10 AIC like models sel. 0 0 0 0 0 0 0 7 24 69 BIC like models sel. 0 0 100 0 0 0 0 0 0 0 SP models sel. 0 0 100 0 0 0 0 0 0 0 VSP models sel. 0 0 100 0 0 0 0 0 0 0

The BIC like criterion and the Strong Penalization chose always the true architecture whatever the number of data. According to the theory, AIC like criterion is not consistent (see condition A1) and the chosen architecture is always too large. The Very Strong penalization chose a too small architecture when the number of data is small (n = 100), however it is a consistent criterion, so its behavior is correct for larger number of data (n = 500 and n = 1000). This good results assume that the true variance of the noise is known, but for regression models this is never the case. A first idea may be to replace the unknown variance by the estimated one, the is done in the next section.

Model selection using estimated variance σ2 .

The estimated variance σ2 is the mean square error of the model:

σ2 := E n ( θ) = 1 n n t=1 (z t -F θ(x t , y t )) 2
computed for the least square estimator θ. Hence, the comparison is done with the penalized criteria :

• AIC like: 1 n n t=1 (z t -F θ (x t , y t )) 2 + 2σ 2 D n • BIC like: 1 n n t=1 (z t -F θ (x t , y t )) 2 + σ2 D log(n) n • SP (Strong Penalization): 1 n n t=1 (z t -F θ (x t , y t )) 2 + σ2 D √ n n • VSP (Very Strong Penalization): 1 n n t=1 (z t -F θ (x t , y t )) 2 + σ2 Dn 3/4 n
The following architectures are chosen by the penalized criteria:

• n=100 nb h. units 1 2 3 4 5 6 7 8 9 10 AIC like models sel. 0 0 0 0 0 1 0 4 27 68 BIC like models sel. 0 0 22 6 3 1 3 5 15 45 SP models sel. 0 0 85 3 1 0 0 0 1 10 VSP models sel. 0 0 100 0 0 0 0 0 0 0 • n=500 nb h. units 1 2 3 4 5 6 7 8 9 10 AIC like models sel. 0 0 0 4 4 6 9 23 19 35 BIC like models sel. 0 0 100 0 0 0 0 0 0 0 SP models sel. 0 0 100 0 0 0 0 0 0 0 VSP models sel. 0 0 100 0 0 0 0 0 0 0

• n=1000 nb h. units 1 2 3 4 5 6 7 8 9 10 AIC like models sel. 0 0 0 0 3 7 12 16 29 33 BIC like models sel. 0 0 100 0 0 0 0 0 0 0 SP models sel. 0 0 100 0 0 0 0 0 0 0 VSP models sel. 0 0 100 0 0 0 0 0 0 0

As usual the AIC like criterion misbehaves like in the previous section. But, for a small number of data (n = 100) the use of an estimation of the variance of the noise instead of the true one leads to overestimation of the number of hidden unit for the BIC like criterion and the strong penalization. The explanation is that the variance of the noise is underestimated for large number of hidden units and so the penalized criterion. This drawback disappears for larger number of data (n = 500 and n = 1000) because the estimation of the variance becomes better. Despite that the Very Strong Penalized criterion seems to guess the true architecture whatever the number of data, to plug estimated variance instead of the true one seems maybe to be a too naive approach for small number of data. As the goal of penalized criterion is to compare models, we could use the logarithm of the mean square error instead of the mean square error itself, hence the lack of the true variance is no more a problem because this number is simplified in the difference of the logarithms. This approach is studied in the next section.

Model selection using logarithm of mean square error

Choosing between two number of hidden units, k 1 and k 2 is the result of a comparison between min θ 1 ∈Θ k 1 (E n (θ 1 ) + a n (k 1 )) on one hand and min θ 2 ∈Θ k 2 (E n (θ) + a n (k 2 )) on the other hand, where a n (k) is the penalization term. So, the results of the comparison may be changed if we consider C • E n (θ) instead of E n (θ) when C is a very big (or very small) constant. But, if we compare min

θ 1 ∈Θ k 1 (log (E n (θ 1 )) + a n (k 1 )) and min θ 2 ∈Θ k 2 (log (E n (θ 2 )) + a n (k 2 )) the results of the comparison is the same if we change E n (θ) in C • E n (θ).
Moreover, E n (θ) may be seen as an approximation of the variance of the noise σ 2 , so

E n (θ) = σ 2 • (1 -ε(θ)) and log (E n (θ)) ≃ log(σ 2 ) -ε(θ) + o(ε(θ))
The term ε(θ) may be seen as the normalized term of overfitting of the model. Finally we get:

min θ∈Θ (log (E n (θ)) + a n (k 1 )) -min θ∈Θ (log (E n (θ)) + a n (k 2 )) ≃ ε(θ 2 ) -ε(θ 1 ) + a n (k 2 ) -a n (k 1 )
and the penalization term plays fully is role of compensation of the "normalized" overfitting.

The results on our little experiment with these new criteria are the following:

• n=100 nb h. units 1 2 3 4 5 6 7 8 9 10 AIC like models sel. 0 0 3 7 4 11 9 13 24 29 BIC like models sel. 0 0 96 4 0 0 0 0 0 0 SP models sel. 0 0 100 0 0 0 0 0 0 0 VSP models sel. 73 27 0 0 0 0 0 0 0 0

• n=500 nb h. units 1 2 3 4 5 6 7 8 9 10 AIC like models sel. 0 0 3 6 8 13 18 10 17 25 BIC like models sel. 0 0 99 1 0 0 0 0 0 0 SP models sel. 0 0 100 0 0 0 0 0 0 0 VSP models sel. 0 69 31 0 0 0 0 0 0 0

• n=1000 nb h. units 1 2 3 4 5 6 7 8 9 10 AIC like models sel. 0 0 1 2 7 13 16 21 19 21 BIC like models sel. 0 0 100 0 0 0 0 0 0 0 SP models sel. 0 0 100 0 0 0 0 0 0 0 VSP models sel. 0 2 98 0 0 0 0 0 0 0

We can see that this method yields very good results, whatever the number of data, for BIC like criterion and the Strong Penalization without knowing the true variance of the noise. Strong Penalization seems even to be a little better than BIC like criterion.

Conclusion

MLP regression is widely used and always a very competitive method (see Osowski et al. [START_REF] Osowski | MLP and SVM networks -a Comparative study[END_REF]), but theoretical justification is lacking for determining the true architecture and especially the number of hidden units. Indeed, the classical asymptotic theory fails when the model is not identifiable. In this paper, we prove an inequality showing that overfitting of MLP is moderate if the noise admits exponential moments and the parameters of the model are a priori bounded. This bound justifies the use of penalized criteria in order to fit the architecture of MLP models in the framework of regression without knowing the density of the noise. Hence, The user can select the true number of hidden units thanks to penalized criteria, of the form E n (θ) + a n (k) or ln(E n (θ)) + a n (k)

If the penalization term a n (k) is well calibrated ( C•k n < a n (k) < C • k), the true number of hidden units will be automatically selected if n is large enough. A little experiment suggests that a good choice of penalization seems to be the middle of the possible range: a n (k) = C•k √ n . The use of the logarithm of the mean square error E n (θ) is an easy way to avoid to know the true variance of the noise. A further question could be to know if this empirical finding for the tuning of the penalization term can be justified theoretically.

Note that, this paper was only concerned with the identification of the true model. The point is more to have an idea of the complexity of the model determining the data than to have a predictive model. However, if there are enough data, the true model will also be the best predictor. Hence, the spirit of the studied criterion is then very different from the approach used in Extreme Learning Machine (ELM) which provides a good predictive model at extremely fast learning speed. Indeed, in ELM, all the hidden node parameters are independent from the target functions or the training datasets so the weights between input and hidden node are no more considered as parameters. Such method is really not concerned by model identification but only by predictive power and speed of computing, for example it is possible to use ELM even if the relation between inputs and ouput is linear. Finally, If ELM seems to work well in pratice, the theoritical justification of the superiority of such method is still lacking.

Another issue may be when the unknow regression function is not represented by an MLP at all, in such case there is no more over-determination and the asymptotic behaviour of the model is more underfitting than overfitting. The overfitting occures only when we consider finite number of data and the theory to deal with such problem is the very difficult non-asymptotic statistical theory as in Massart [4]. As far as we know this theory gives no hints for choosing the number of hidden units for finite number of data.

Appendix

A Donsker class is a notion from the "empirical processes theory". This theory deals with "law of large number" and "asymptotic normality" for set of functions. Basically, a Donsker class is a set of functions which is "not too big".

Let X 1 , • • • , X n be a random sample from a probability distribution P . The empirical distribution is the discrete uniform measure on the observations. We denote it by P n = 1 n n i=1 δ X i , where δ x is the probability distribution that is degenerate at x. Given a function f , we write P n f for the expectation of f under the empirical measure and P f for the expectation under P . Thus

f (X i ) and P f = f dP.

The empirical process evaluated at f is defined as

Consider a set of functions F endowed with the L 2 norm • (see ( 4)). For every ε > 0, we define an ε-bracket by

where

The class F of functions is called Donsker if the covering number, which depends of the diameter ε of the balls, is smaller than order e 1 ε 2 when ε goes to 0. Then, the sequence of processes {G n f, f ∈ F } converges in distribution to a tight limit process. Finally, if F = d λ θ , θ ∈ Θ is a Donsker class, the