Cyrille Migniot

Pascal Bertolino

Jean-Marc Chassery

AUTOMATIC PEOPLE SEGMENTATION WITH A TEMPLATE-DRIVEN GRAPH CUT

Keywords: people segmentation, graph cut, template of silhouette, part-based template

This paper presents a new fully automatic method for segmenting upright people in the images. Is is based on the efficient graph cut segmentation. Since colour and texture prevent from discriminating this particular class, silhouette shape is used instead. The graph cut is guided by a non-binary template of silhouette that represents the probability of each pixel to be a part of the person to segment. Subsequently, partbased template is used to better take into account the different postures of a person. Our method is close to real time and is tested on a large person dataset.

INTRODUCTION

To detect and segment people, numerous methods use binary templates. A template is a model used to characterize the elements of a class. In the class of upright people, the one we are interested in, the possible postures are fairly varied. In the form of a binary mask, a template represents the silhouette for one of these typical postures. A catalogue of templates contains all the postures that a person may take. These templates are then compared one by one to the attributes of the image (often the edges [START_REF] Zhao | Closely coupled object detection and segmentation[END_REF]). If the comparison is positive, a person is detected and the silhouette corresponding to his/her posture is evaluated. The final segmentation is obtained by slightly adapting this silhouette to the edges in the image [START_REF] Rodriguez | Detecting and segmenting humans in crowded scenes[END_REF]. To reduce the computing time, [START_REF] Gavrila | Shape-based pedestrian detection and tracking[END_REF] makes a hierarchical repartition of the templates. Thus, the comparisons are not performed with all the templates (using a template depends on the result of the previous comparisons). Finally, [START_REF] Lin | Hierarchical part-template matching for human detection and segmentation[END_REF] divides the body in three parts (head-torso, upper legs and lower legs) and searches the best template for each part.

Concerning shape-guided graph cut segmentation, a number of proposals has been done. The original graph cut method was modified by adding a third term to its energy function to take into account the shape with level sets [START_REF] Freedman | Interactive graph cut based segmentation with shape priors[END_REF]. The region or the boundary term (or both) of the energy function were modified [START_REF] Wang | Adaptive shape prior in graph cut segmentation[END_REF][START_REF] Slabaugh | Graph cuts segmentation using an elliptical shape prior[END_REF][START_REF] Das | Semiautomatic segmentation with compact shape prior[END_REF]. [START_REF] Malcolm | Graph cut segmentation with nonlinear shape priors[END_REF] proposed an interesting but rather time-costly solution where a pre-image obtained from a training set with a Kernel PCA was iteratively updated.

The work presented in this paper only deals with segmentation. The preliminary people detection is carried out with the method by [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF] that provides normalized windows centered on the person (see examples figure 5).

The graph cut as defined by [START_REF] Boykov | Interactive graph cuts for optimal boundary and region segmentation of objects in n-d images[END_REF] is an efficient segmentation method. One of its main advantage is its easy interaction with the user. As a consequence, it is widely used in image segmentation [START_REF] Rother | Grabcut: Interactive foreground extraction using iterated graph cuts[END_REF].

The graph is made up of nodes corresponding to the image pixels. Neighborhood links (n-links) connect the nodes to model the pixel adjacency. Two special nodes called source and sink are added to the graph to materialize the foreground and the background. Terminal links (t-links) connect each pixel to the source and to the sink. A weight is associated to each of the links. Then a graph cut that minimizes the sum of the weights of the cut edges is calculated. Pixels that are on the same side of the cut as the source belong to the foreground while the other pixels belong to the background.

In order to take into account the image content, the nlink weights are related to the image boundaries and the t-link weights are related to the probability of a pixel to belong to the foreground and to the background. These probabilities are generally based on the color repartitions since the user may teach the graph how foreground and background look like by drawing scribbles in the image. This method is quite efficient but quite general. In this paper, we present a new technique for adapting graph cut to the characteristics of people segmentation without any user interaction. Our contribution is first to weight the graph cut with a learned mean silhouette called template and secondly to adapt this technique by computing several graphcuts on each body part and keeping the ones that give the best response to build a part-based template.

In section 2, we introduce a non binary template learned from a training dataset, that represents the probability of a pixel to belong to the silhouette of a person. This probability is used to initialize the weights of the t-links.

Then in section 3, the segmentation is refined in order to adapt to the various postures: the image and thus the body is divided in several parts. For each part, several sub-templates are tested and the final template (called part-based template) is obtained by concataining the best sub-templates.

Finally, in section 4 our two approaches (single template and part-based template) are evaluated.

The graph is achieved from a window encompassing the person provided by the detection process. A source F and a sink B represent the foreground and the background. Each pixel of the window is a node of the graph and is connected to its neighbors by n-links and to F and B by t-links. The links are weighed in order to introduce image information in the graph representation. The relative strength between n-links and t-links weights is tuned using two coefficients (α and β).

Neighborhood links

N-links weights correspond to a penalty for discontinuity between the pixels. Thus it is logical to represent them with the image boundaries. The intensity difference is used like in the work of Boykov et al [START_REF] Boykov | Interactive graph cuts for optimal boundary and region segmentation of objects in n-d images[END_REF]. Let I p be the intensity of pixel p and I q be the intensity of a neighbor pixel q. The weight associated to the n-link between p and q is defined by:

ω pq = βe - |I p -I q | 2 2σ 2 (1)
where σ is the filtering realized by the exponential. The small values of this function represent the strong contour probabilities.

Terminal links

T-links connect each pixel to F and B. For a given pixel, the cut passes through only one of these two links which indicates to which region the pixel is assigned. The way these links are weighted must reflect the probability of the pixel to belong to foreground or background. [START_REF] Boykov | Interactive graph cuts for optimal boundary and region segmentation of objects in n-d images[END_REF] expresses this probability using color distribution. But the wide variety of colors among people and in the background make this attribute too few discriminative when dealing with people. So we make a template of the size of the detection window that gives for each pixel its probability to belong to a human silhouette. This template is made from a training set of 200 silhouettes [START_REF] Migniot | Contour segment analysis for human silhouette presegmentation[END_REF] well representative of upright postures (figure 1). Let t p be the probability of the template for pixel p. The t-link weights for F and B are defined by:

ω F p = -αln(1 -t p ) (2)
ω B p = -αln(t p ) (3)

A PART-BASED TEMPLATE

The template presented in the previous section takes into account all the postures but penalizes the ones with a low occurrence, in particular when legs are spread. The idea is then to use a template adapted to the posture itself. It would be possible to perform a graph cut with as many templates as there exist different postures. But the number of postures is high and the processing cost would be high too. We propose to process independently the different parts of the body: the silhouette is divided into five parts: head, right and left part of the torso including the arm, right and left leg. For each of these parts, some sub-templates are built using the corresponding postures in the people dataset (figure 2). The number of subtemplate is proportional to the variability of the body part and can be tuned according to the needs if the dataset contains the corresponding cases. We chose one sub-template for the head, five for each side of the torso including the arm and nine for each leg. For each part, a graph cut is carried out using each of the n sub-templates. The best of the n max-flows (i.e. the lowest sum of the weights among the n graph cuts) indicates which sub-template fits the best any part of the silhouette. The part-based template is simply the concatenation of the five best sub-templates (figure 3). Finally, in order to preserve continuity of the silhouette between its different parts, a graph cut is performed on the whole window using the part-based template obtained above. A small number of sub-templates is sufficient. Indeed, since the n-links will adapt the cut to the edges, the templates just have to promote a state (unstuck arms, bended legs, . . . ) and don't have to perfectly fit the silhouette. Fig. 3. For each part of the detection window (here the left part of the torso), several graph cuts are carried out using several sub-templates. The one that provides the minimal flow cut is added to the part-based template

PERFORMANCES

Our method was evaluated with tests on a set of 400 images of people from the INRIA Person Dataset. The F measure and the Yasnoff measure [START_REF] Philipp-Foliguet | Mutlti-scale criteria for the evaluation of image segmentation algorithms[END_REF] evaluate our method by comparing a ground truth segmentation performed manually with the results obtained. The two measures are used for each of the 400 segmented images and a mean is calculated for both. The processing times are obtained with a non-optimized C++ implementation running on a 3GHz Pentium D.

Optimizing the parameters

In order to optimize the process, we must determine the values of parameters α, β and σ that give the best performances. Tests have been made with different values of these parameters. The results given in figure 4 are obtained with a partbased template but the ones obtained with a single template are very similar.

In order to obtain the best segmentation, i.e. to minimize1 the Yasnoff measure and to maximize the F measure , in the sequel the values σ = 9, α = 12 and β = 60 are chosen.

Single or part-based template?

Since we have presented two versions of the template, their respective performances must be compared. First, the process with a single template is logically faster: a 96 × 160 pixel window is processed in a mean of 12 ms as against a mean of 70 ms with the part-based template. The part-based template provides both better F measure and Yasnoff measure as shown in table 1. In the great majority of the cases, the part-based template gives a better adapted and more accurate segmentation (figure 5). Table 1. Segmentation performances over a set of 400 images

CONCLUSION

In this paper we have proposed a new segmentation method that adapts the well-known graph-cut method to the particular case of persons. To do this, we have introduced templates to evaluate the shape of the silhouette. The template is either generic for the class or adapted to the person posture. The process is efficient and close to real time. The segmentation of video sequences and the possibility of an easy interaction with the user are among the main advantages of the graph cut approach. Future relevant works would be to adapt our method to videos and to permit an efficient user interaction to segment people in difficult cases.

Fig. 1 .

 1 Fig. 1. Template (i.e. mean silhouette) made from a dataset of 200 binary silhouettes.

Fig. 2 .

 2 Fig. 2. 1 (head), 2 × 5 (torso and arms) and 2 × 9 (legs) subtemplates to adapt to specificities of the five silhouette parts

Fig. 4 .

 4 Fig. 4. Results of the tests carried out to optimize the values of σ (first row), α (second row) and β (third row). The F measure (↑) left column and the Yasnoff measure (↓) right column give an evaluation of the segmentation quality. Measure Single template Part-based template F measure (↑) 0,8813 0,8849 Yasnoff (↓) 0,4178 0,4087

Fig. 5 .

 5 Fig. 5. From left to right: initial image, segmentation obtained with a single template and with a part-based template. In most of the cases, the segmentation is more accurate with the part-based template

in order to facilitate the coming reading, the sign ↓ indicates a measure to minimize and the sign ↑ a measure to maximize


Nicolas Béchet
email: bechet@lirmm.fr

Mathieu Roche
email: mroche@lirmm.fr

How to Expand Dictionaries with Web-Mining Techniques

This paper presents an approach to enrich conceptual classes based on the Web. To test our approach, we first build conceptual classes using syntactic and semantic information provided by a corpus. The concepts can be the input of a dictionary. Our web-mining approach deals with a cognitive process which simulates human reasoning based on the enumeration principle. The experiments reveal the interest of our approach by adding new relevant terms to existing conceptual classes.

Introduction

Concepts have several definitions; one of the most general describes a concept 'as the mind's representation of a thing or an item' [START_REF] Desrosiers-Sabbath | Comment enseigner les concepts[END_REF]. In a domain such as ours, i.e. ontology building, semantic webs, and computational linguistics, it seems appropriate to stick to the Aristotelian approach to a concept, and consider it as a set of knowledge (gathered information) on common semantic features. The choice of the features and how the knowledge is gathered depend on criteria we will explain below.

In this paper, we deal with the building of conceptual classes, which can be defined as gathering semantically close terms. First, we suggest building specific conceptual classes by focusing on knowledge extracted from corpora.

Conceptual classes are shaped by the study of syntactic dependencies between corpus terms (as described in section 2). Dependencies tackle relations such as Verb/Subject, Noun/Noun Phrase Complements, Verb/Object, Verb/Complements, and sometimes Sentence Head/Complements. In this paper, we focus on the Verb/Object dependency because it is representative of a field. For instance, in computer science, the verb 'to load' takes as objects, nouns of the conceptual class software [START_REF] L'homme | Le statut du verbe en langue de spécialité et sa description lexicographique[END_REF]. This feature also extends to 'download' or 'upload', which have the same verbal root.

Corpora are rich sources of terminological information that can be mined. A terminology extraction of this kind is similar to a Harris-like distributional analysis [START_REF] Harris | Mathematical Structures of Language[END_REF]) and many works in the literature have been the subject of distributional analysis to acquire terminological or ontological knowledge from textual data (e.g (Bourigault and Lame, 2002) for law, [START_REF] Nazarenko | Corpus-based extension of a terminological semantic lexicon[END_REF][START_REF] Weeds | Weir using distributional similarity to organise biomedical terminology[END_REF] for medicine).

After building conceptual classes (section 2), we describe an approach to expand concepts by using a Web search engine to discover new terms (section 3). In section 4, experiments conducted on real data enable us to validate our approach.

Building Conceptual Classes

Principle

In our approach, a class can be defined as a gathering of terms with a common field. In this paper, we focus on objects of verbs judged to be semantically close by using a measure. These objects are thus considered as instances of conceptual classes. The first step in building conceptual classes consists in extracting Verb/Object syntactic relations as explained in the following section.

Mining for Verb/Object relations

Our corpora are in French since our team is mostly devoted to French-based NLP applications. However, the following method can be used for any other language, provided a reliable dependency parser is available. In our case, we use the SYGFRAN parser developed by [START_REF] Chauché | Un outil multidimensionnel de l'analyse du discours[END_REF]. As an example, in the French sentence "Thierry Dusautoir brandissant le drapeau tricolore sur la pelouse de Cardiff après la victoire." (translation: 'Thierry Dusautoir brandishing the three colored flag on Cardiff lawn after the victory'), there is a verb-object syntactic relation: "verb: brandir (to brandish), object: drapeau (flag)", which is a good candidate for retrieval. The second step of the building process corresponds to the gathering of common objects related to semantically close verbs. Assumption of Semantic Closeness. The underlying linguistic hypothesis is the following: Verbs with a significant number of common objects are semantically close. To measure closeness, the ASIUM score [START_REF] Faure | Knowledge acquisition of predicate argument structures from technical texts using machine learning: The system ASIUM[END_REF][START_REF] Faure | Conception de méthode d'apprentissage symbolique et automatique pour l'acquisition de cadres de sous-catégorisation de verbes et de connaissances sémantiques à partir de textes : le système ASIUM[END_REF] is used (see figure 1). This type of work is similar to distributional analysis approaches such as that of (Bourigault and Lame, 2002).

As explained in the introduction, the measure considers two verbs to be close if they have a significant number of common features (objects).

Let p and q be verbs with their respective p 1 ,...,p n and q 1 ,...,q m objects. NbOC p (q i ) is the number of occurrences of q i objects from q that are also objects of p (common objects). NbO(q i ) is the number of occurrences of q i objects of q verb. The Asium measure is then:

Where log Asium (x) is equal to:

• for x = 0, log Asium (x) = 0 • else log Asium (x) = log(x) + 1
Therefore, conceptual classes instances are the common objects of close verbs, according to the ASIUM proximity measure.

The following section describes the acquisition of new terms starting with a list of terms/concepts obtained with the global process summarized in this section and detailed in (Béchet et al., 2008).

Expanding conceptual classes

Acquisition of candidate terms

The aim of this approach is to provide new candidates for a given concept. It is based on enumeration on the Web of terms that are semantically close. For instance, with a query (string) "bicycle, car, and", we can find other vehicles. We propose to use the Web to acquire new candidates. This kind of method uses information regarding the "popularity" of the web and is independent of a particular corpus.

Our method of acquisition is quite similar to that of [START_REF] Nakov | Solving relational similarity problems using the web as a corpus[END_REF]. These authors propose to query the Web using the Google search engine to characterize the semantic relation between a pair of nouns. The Google star operator among others, is used to that end. [START_REF] Nakov | Solving relational similarity problems using the web as a corpus[END_REF] refer to the study of [START_REF] Lin | Discovery of inference rules for question answering[END_REF] who used a Web mining approach to discover inference rules missed by humans.

To apply our method, we first consider the common objects of semantically close verbs, which are instances of reference concepts (e.g. vehicle). Let N concepts C i {1, N} and their respective instances I j (C i ). For each concept C i , we submit to a search engine the following queries: "I jA (C i ), I jB (C i ), and" and "I jA (C i ), I jB (C i ), or" with jA and jB ϵ {1, ..., NbInstanceC i } and jA ≠ jB.

The search engine returns a set of results from which we extract new candidate instances of a concept. For example, if we consider the query: "bicycle, car, and", one page returned by a search engine gives the following text: Listen here for the Great Commuter Race (17/11/05) between bicycle, car and bus, as part of...

Having identified the relevant features in the result returned (in bold in our example), we add the term "bus" to the initial concept "vehicle". In this way, we obtain new candidates for our concepts. The process can be repeated. In order to automatically determine which candidates are relevant, the candidates are filtered as shown in the following section.

Filtering of candidates

The quality of the extracted terms can be validated by an expert, or automatically by using the Web to check if the extracted candidates (see section 3.1) are relevant. The principle is to consider a relevant term if it is often present with the terms of the original conceptual class (kernel of words). Thus, our aim is to validate a term "in the context". From that point of view, our method is close to that of [START_REF] Turney | Mining the Web for synonyms: PMI-IR versus LSA on TOEFL[END_REF], which queries the Web via the AltaVista search engine to determine appropriate synonyms for a given term. Like [START_REF] Turney | Mining the Web for synonyms: PMI-IR versus LSA on TOEFL[END_REF], we consider that information concerning the number of pages returned by the queries can give an indication of the relevance of a term.

Thus, we submit to a search engine different strings (using citation marks). A query consists of the new candidate and both terms of the concept. Formally, our approach can be defined as follows. Let N concepts C i ϵ {1, N}, their respective instances I j (C i ) and the new candidates for a concept C i , N ik {1, NbNI(Ci)} . For each C i , each new candidate N ik is sent as a query to a Web search engine. In practice the three terms are separated either by a comma or the word "or" or "and" 1 . For each query, the search engine returns a number of results (i.e. number of web pages). Then, the sum of these results is calculated using all possible combinations of "or", "and", or of the three words (words of the kernel plus candi-1 Note that the commas are automatically removed by the search engines.

date word to enrich it). Below is an example with the kernel words "car", "bicycle" and the candidate "bus" to test (using Yahoo):

• "car, bicycle, and bus": 71 pages returned

• "car, bicycle, or bus": 268 pages returned

• "bicycle, bus, and car": 208 pages returned

• and so forth Global result: 71 + 268 + 208...

The filtering of candidates consists in selecting the k first candidates by class (i.e. with the highest sum), they are added as new instances of the initial concept. We can reiterate the acquisition approach by including these new terms. The acquisition/filtering process can be repeated several times.

In the next section, we present experiments conducted to evaluate the quality of our approach.

Experiments

Evaluation protocol

We used a French corpus from the Yahoo site (http://fr.news.yahoo.com/) composed of 8,948 news items (16.5 MB) from newspapers. Experiments were performed on 60,000 syntactic relations (Béchet et al., 2008;Béchet et al., 2009) to build original conceptual classes. We manually selected five concepts (see Figure 2). Instances of these concepts are the common objects of verbs defining the concept (see section 2.2). For our experiments, we use an API of the search engine Yahoo! to obtain new terms. We apply the following post-treatments for each new candidate term. They are initially lemmatized. Therefore, we only keep the nouns, after applying a PoS (Part of Speech) tagger, the TreeTagger [START_REF] Schmid | Improvements in part-of-speech tagging with an application to german[END_REF].

After these post-treatments, we manually validate the new terms using three experts. We compute the precision of our approach to each expert. The average is calculated to define the quality of the terms. Precision is defined as follows.

Precision =

Numberof relevantterms given by our system Numberof terms given by our system

In the next section, we present the evaluation of our method.

Experimental results

Table 1 gives the results of the term acquisition method (i.e. for each acquisition step, we apply our approach to filter candidate terms). For each step, the table lists the degree of precision obtained after expertise:

• All candidates. We calculate the precision before the filtering step.

• Filtered candidates. After applying the automatic filtering by selecting k terms per class, we calculate the precision obtained. Note that the automatic filtering (see section 3.2) reduces the number of terms proposed, and thus reduces the recall2 .

Table 1: Results obtained with k=4 (i.e. automatic selection of the k first ranked terms by the filtering approach).

Finally Table 1 shows the number of terms generated by the acquisition system.

These results show that a significant number of terms can be generated (i.e. 103 words). For example, for the concept 'feeling', using the initial terms given in figure 1, we obtained the following eight French terms (in two steps): "horreur (horror), satisfaction (satisfaction), déprime (depression), faiblesse (weakness), tristesse (sadness), désenchantement (disenchantment), folie (madness), fatalisme (fatalism)". This approach is appropriate to produce new relevant terms to enrich conceptual classes, in particular when we select the first terms (k = 4) returned by the filtering system. In a future work, we plan to test other values of the automatic filtering. The precision obtained in the first two steps was high (i.e. 0.69 to 0.83). The third step returned lower scores; noise was introduced because we were too "far" from the initial kernel words.

Conclusion and Future Work

This paper describes an approach for conceptual enrichment classes based on the Web. We apply the "enumeration" principle to find new terms using Web search engines. This approach has the advantage of being less dependent on the corpus. Note that as the use of the Web requires validation of candidates, we propose an automatic filtering method to select relevant terms to add to the concept. In a future work, we plan to use other statistical web measures (e.g. Mutual Information, Dice measure, and so forth) to automatically validate terms.

Figure 1 :

 1 Figure 1: Common and complementary objects of the verbs "to consume" and "to eat"

Figure 2 :

 2 Figure 2: The five selected concepts and their instances.

  Béchet, N., M. Roche, and J. Chauch´e. 2008. How the ExpLSA approach impacts the document classification tasks. In Proceedings of the International Conference on Digital Information Management, ICDIM'08, pages 241-246, University of East London, London, United Kingdom. Béchet, N., M. Roche, and J. Chauché. 2009. Towards the selection of induced syntactic relations. In European Conference on Information Retrieval (ECIR), Poster, pages 786-790. Bourigault, D. and G. Lame. 2002. Analyse distributionnelle et structuration de terminologie. Application à la construction d'une ontologie documentaire du droit. In TAL, pages 43-51.

	1 2 3 Steps #	0.69 0.69 0.56 All terms Precision Filtered terms (without filter) 0.83 0.77 0.65 103 47 29 Terms number

The recall is not calculated because in an unsupervised context it is difficult to estimate.


Mathieu Roche
email: mroche@lirmm.fr

HOW STATISTICAL INFORMATION FROM THE WEB CAN HELP IDENTIFY NAMED ENTITIES

Keywords: Text-Mining, Natural Language Processing, Terminology, Named Entity

This paper presents a Natural Language Processing (NLP) approach to filter Named Entities (NE) from a list of collocation candidates. The NE are defined as the names of 'People', 'Places', 'Organizations', 'Software', 'Illnesses', and so forth. The proposed method is based on statistical measures associated with Web resources to identify NE. Our method has three stages: (1) Building artificial prepositional collocations from Noun-Noun candidates; (2) Measuring the "relevance" of the resulting prepositional collocations using statistical methods (Web Mining); (3) Selecting prepositional collocations. The evaluation of Noun-Noun collocations from French and English corpora confirmed the relevance of our system.

INTRODUCTION

In this paper, we focus on the study of French and English phrases called collocations that can be extracted using NLP (Natural Language Processing) methods. [START_REF] Clas | Collocations et langues de spécialité[END_REF] uses two properties to define a collocation. First, it is defined as a phrase with a meaning that can be deduced from the words that comprise the phrase. For instance, the French phrase lumière vive (bright light) is considered to be a collocation because the overall meaning of the phrase can be deduced from the two words lumière and vive. Based on this definition, the phrase tirer son chapeau (to take off one's hat), is not a collocation because its meaning cannot be deduced from each word. These forms are called "fixed expressions".

A second property was added by the author [START_REF] Clas | Collocations et langues de spécialité[END_REF] to define a collocation. The meaning of the words of the collocation has to be limited. For example, acheter un chapeau (buy a hat) is not a collocation since the meaning of acheter and chapeau is not limited. Indeed, a multitude of objects can be purchased.

Such phrases are called "free expressions". However it is still very difficult to distinguish between "fixed expressions, "free expressions", and collocations automatically.

The above definitions of collocation can be enriched with two additional characteristics, i.e. semantic and syntactic knowledge [START_REF] Heid | Towards a corpus-based dictionary of german noun-verb collocations[END_REF]. The first point is based on a semantic shared by the collocations. For example, lait tourné (sour milk) and beurre rance (rancid butter) have a very similar meaning as both describe a degradation phenomenon. The semantic information contained in collocations has been taken into account in many studies [START_REF] Melcuk | Dictionnaire explicatif et combinatoire du français contemporain[END_REF][START_REF] Heid | Towards a corpus-based dictionary of german noun-verb collocations[END_REF]. The second linguistic characteristic is the syntactic information contained in the collocation [START_REF] Clas | Collocations et langues de spécialité[END_REF][START_REF] Daille | Study and implementation of combined techniques for automatic extraction of terminology[END_REF]. Generally, collocations have one of the following patterns: Noun-Verb, Noun-Adjective, Noun-Noun, Noun-Preposition-Noun, Verb-Adverb, Adverb-Adjective, etc.

Using automatic processing, it is difficult to identify collocations based on all these linguistic definitions. So we decided to focus on the extraction of "collocation candidates" displaying a specific syntactic pattern. However, the originality of the approach described in this paper is the automatic identification of Named Entities (NE) among these candidates. NE are conventionally defined as the names of 'People', 'Places', and 'Organizations'. Originally, this definition was used in evaluation challenges such as MUC (Message Understanding Conferences). Today these kinds of challenges (e.g. TREC in English, DEFT in French) cover a wide range of tasks. As indicated in [START_REF] Daille | Catégorisation des noms propres : une étude en corpus[END_REF], the basic classes of NE defined in MUC challenges needed to be enriched. For example, [START_REF] Paik | Categorizing and standardizing proper nouns for efficient information retrieval[END_REF] defined two new classes: 'Document' (e.g. software, hardware) and 'Science' (e.g. illness, medication). To identify NE, many systems rely on the use of uppercase letters [START_REF] Farkas | Improving a state-of-the-art named entity recognition system using the world wide web[END_REF]. However, this may not be applicable to non-capitalized NE (for instance in non-standard documents like emails, blogs, tweets, texts or text fragments that are written using either uppercase or lowercase). Consequently, in the present study, we did not chose to exploit this lexical information to identify NE. Neither do we use machine learning approaches for the recognition of NE cited in [START_REF] Baluja | Applying machine learning for high-performance named-entity extraction[END_REF][START_REF] Farkas | Improving a state-of-the-art named entity recognition system using the world wide web[END_REF].

In addition to characterize the NE, the criteria uniqueness referential (i.e. a proper name refers to a single referential entity), and stability of the denomination (i.e. few possible variations) are specified by [START_REF] Fort | Vers une méthodologie d'annotation des entités nommées en corpus[END_REF]. Our approach is based on this last criterion to identify NE among collocation candidates.

The extraction of collocation candidates is based on a text mining process (see 'stage 1' -Figure 1). After the acquisition of a corpus, a cleaning process has to be applied. This removes noise in the texts (e.g. HTML tags) that can lead to mistakes in an NLP application. With the normalized texts, a part-of-speech (PoS) tagger can be used. This attributes a grammatical label (e.g. adjective, noun, and so on) to each word of the corpus [START_REF] Brill | Some advances in transformationbased part of speech tagging[END_REF]. In this paper, we describe a method to extract collocation candidates from tagged texts. The process is based on the use of patterns to extract nominal terminology such as Noun-Adjective (in French), Adjective-Noun, Noun-Noun, Noun-Preposition-Noun [START_REF] Bourigault | Term extraction + term clustering: An integrated platform for computer-aided terminology[END_REF][START_REF] Daille | Study and implementation of combined techniques for automatic extraction of terminology[END_REF][START_REF] Roche | Pruning Terminology Extracted from a Specialized Corpus for CV Ontology Acquisition[END_REF].

-Cleaning -Tagging -Terminology extraction

Web

------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ Corpus Figure 1: Global process.
In the following section (section 2), we focus on a statistical method for selecting NE from Noun-Noun collocation candidates (see 'stage 2' -Figure 1). The results of experimental tests of our method conduced on real data (French and English corpora) are presented in section 3. Finally, section 4 presents our future work.

NAMED ENTITY FILTERING

General Principle

Noun-Noun terminology has often various forms. For example, the French collocation fichier clients (customer file) can be found with the Noun-Preposition-Noun form: fichier de clients (file of customers), fichiers pour clients (file for customers), and so forth. Note that the variations of NE are rare. Based on this remark we will use NLP methods in order to identify NE from a list of Noun-Noun collocation candidates.

Our method has three stages detailled in the following section:

1. Building artificial prepositional collocations from Noun-Noun candidates.

2. Measuring the "relevance" of the resulting prepositional collocations using statistical methods.

3. Selecting prepositional collocations with low scores (i.e. irrelevant built collocation).

Description of the process

Step 1 -Building

Based on Noun-Noun candidates, we built prepositional candidates by adding the most common preposition: "de" (in French 1 ) and "of" (in English). When this principle was applied to both French examples fichier clients (customer file) and logiciel ciel (ciel software), we obtained the following results:

• fichier clients N N → fichier de clients

N -P rep-N • logiciel ciel N N → logiciel de ciel N -P rep-N
Note that the English variations of Noun-Noun candidates consist in adding a preposition associated with a swapping operation between the nouns [START_REF] Jacquemin | Variation terminologique : Reconnaissance et acquisition automatiques de termes et de leurs variantes en corpus[END_REF]:

• knowledge discovery N N → discovery of knowledge N -P rep-N
Step 2 -Measuring

The goal of the second step was to measure the dependence between each word of the collocations we built. This process is based on the use of the Dice measure [START_REF] Smadja | Translating collocations for bilingual lexicons : A statistical approach[END_REF] which has good behavior [START_REF] Roche | Managing the Acronym/Expansion Identification Process for Text-Mining Applications[END_REF][START_REF] Roche | Text and web mining approaches in order to build specialized ontologies[END_REF]. The measure is defined by 1 Note that when the second word of the candidate begins with a vowel, the preposition used is " d' "

the following formula based on three elements as in [START_REF] Petrovic | Comparison of collocation extraction measures for document indexing[END_REF]:

Dice(x, y, z) = 3 × nb(x, y, z) nb(x) + nb(y) + nb(z) (1)
The principle of this measure is to calculate the number of occurrences of each word x (i.e. nb(x)) or collocation x y z (i.e. nb(x, y, z)). In general, the number of occurrences represents the frequency of the words and/or collocations. This frequency is generally calculated regarding a corpus [START_REF] Daille | Study and implementation of combined techniques for automatic extraction of terminology[END_REF]. In our case, the Dice measure is applied in a web-mining context [START_REF] Turney | Mining the Web for synonyms: PMI-IR versus LSA on TOEFL[END_REF].

Thus, the frequency nb corresponds to the number of web pages containing words or collocations. This number is returned by querying search engines (Google, Yahoo, Exalead, etc.). For example, nb(f ichier) is the number of pages returned with the single keyword, and nb(f ichier, de, clients) is the number of pages returned with the query "fichier de clients" (by using quotes to search an exact phrase). An example of values obtained with Dice measure is given below:

Dice(f ichier, de, clients) = 3×999,000 37,200,000+6,350,000,000+208,000,000 = 0.000454 Dice(logiciel, de, ciel) = 3×89,800 35,000,000+6,350,000,000+35,400,000 = 0.0000419

This result shows that the lowest score in major proportions (factor ten) is given by logiciel ciel. Thus, our measure predicts that this Noun-Noun candidate is a NE. This is very relevant because this one is a management software adapted to one class of NE (i.e. 'Document' class) [START_REF] Daille | Catégorisation des noms propres : une étude en corpus[END_REF][START_REF] Paik | Categorizing and standardizing proper nouns for efficient information retrieval[END_REF]. Web gives an indication of popularity of the words/collocations. Moreover with "external" knowledge (i.e. Web) we are less sensitive to the size of the used data (i.e. corpus).

Note that this measure has two differencies with the web-mining approach described in (Turney, 2001): (1) We use the Dice measure because it provides best results than Mutual Information [START_REF] Roche | Text and web mining approaches in order to build specialized ontologies[END_REF]; (2) The numerator of this measure is based on the exact search of phrases (by using quotes) and not on the presence (i.e. AND operator) or the proximity (i.e. NEAR operator) of the nouns.

Step 3 -Selecting Constructed candidates with low scores are elements with few possible variations. In our approach, these candidates are considered to be NE. We introduce a parameter S which represents a selection threshold. For example, with a threshold S = 10, ten candidates with the lowest scores will be selected as possible NE. The results with different values of S are discussed in the following section.

EXPERIMENTS

Experimental protocol

In our experiments, the first used corpus (called CV) is composed of 1, 144 Curriculum Vitae provided by the VediorBis company (120, 000 words). The second specialized French corpus (called HR) is composed of a set of texts from the Human Resources field. The texts correspond to summaries of psychological tests of 378 persons (600, 000 words). First we select collocation candidates which are present a minimum number of times in the corpus.

This pruning task enables to exclude candidates which are often unrepresentative of the field. The Table 1 shows the number of candidates obtained before and after pruning at 3 such as [START_REF] Thanopoulos | Comparative evaluation of collocation extraction metrics[END_REF][START_REF] Roche | Pruning Terminology Extracted from a Specialized Corpus for CV Ontology Acquisition[END_REF].

According to the same field and language, the results may differ. For example, with the CV corpus after pruning, the number of Noun-Noun candidates is much larger than the Human Resources corpus. Yet the size of Human Resources corpus is five times larger than the CV corpus. This is because CV are written in a condensed way, using very specific nominal terminology. We select this kind of collocation in the study presented below.

The goal of our experiments is to evaluate if the collocation candidates selected with our webmining approach represent really relevant NE. In this context, we relied on the most frequent Noun-Noun candidates of the CV corpus. In our experiments, 70 candidates have been evaluated manually (18 NE have been identified). Note that this protocol needs an automatic execution of 210 queries2 with the search engine Exalead (http://www.exalead.com/), this search engine giving good results, in particular for French data.

To evaluate the generalisation of our approach, we also propose to work with an English corpus composed of Noun-Noun collocation candidates. This list has 105 NE (examples of topics: politicy, military, religious, etc) and 200 terms (topic: data-mining). We have ranked all the candidates applying our web-mining approach by performing 915 queries.

The benchmarks used in these experiments are very specific because they have only lowercase words. This situation is distinct from classic benchmarks of the state-of-the-art.

Results

In order to evaluate our text-mining system Precision (formula (2)) and Recall (formula (3)) are calculated. A precision at 100% means that all NE returned with our system are relevant, and a recall at 100% means that all relevant NE are returned. In addition, the F-measure (formula ( 4)) combines the precision and recall.

F -measure = 2 × Precision × Recall Precision + Recall (4)
We measure the quality of our system with different thresholds S (see Tables 2 and3). The results show that the best value of F-measure is obtained when we take into account the first half of candidates from French and English corpora. We can consider that our method has a good behaviour because our ranking function returns a lot of NE at the top the list. For instance, with the English corpus, the value of the precision is 83% when 40 candidates are selected with our web-mining approach (a random ranking returns a precision at 34%).

Finally, note that the F-measure with our approach is better in a large proportion than a random distribution for all values of S (see Tables 2 and3).

CONCLUSION AND FUTURE WORK

This paper presents a text mining method for extracting collocation candidates and identifying Named Entities from a list of candidates. The filtering method uses only a statistical approach based on the Dice measure and exploitation of the results of search engines. The NE is "stable", which is why we built variations of the candidates and checked their popularity using search engines. If the candidates we built turned out to be irrelevant (i.e. low value of the statistical measure), they were considered as NE.

In the next step of our work, we plan to enrich the rules concerning variations, which is a precondition to take into account the vast majority of possible linguistic variations. Finally, we plan to combine this approach, which is only based on statistical knowledge, with lexical information, particularly the use of uppercase letters when possible.

Table 1 :

 1 Number of collocation candidates obtained before and after pruning.

		Before pruning After pruning
		HR	CV	HR	CV
	Noun-Noun	98	1,781	11	162
	Noun-Preposition-Noun 4,703	3,634	1,268	307
	Adjective-Noun	1,260	1,291	478	103
	Noun-Adjective	5,768	3,455	1,628	448
			French corpus
		S	10	40	70
	Web-Mining	Precision 0.60 0.35 0.26
	ranking	Recall	0.33 0.78	1
		F-measure 0.43 0.48 0.41
	Random ranking F-measure 0.18 0.35 0.41

Table 2 :

 2 Precision, Recall, and F-measure with different values of S -French corpus

					English corpus
		S	10	40	70	140	210	305
	Web-Mining	Precision	1	0.83 0.73 0.58 0.46 0.34
	ranking	Recall	0.10 0.31 0.49 0.77 0.92	1
		F-measure	0.17 0.46 0.58 0.66 0.62 0.51
	Random ranking F-measure	0.06 0.19 0.28 0.39 0.46 0.51

Table 3 :

 3 Precision, Recall, and F-measure with different values of S -English corpus

We apply 70 queries for the numerators, and 140 queries for both nouns of the denominators (the query for the prepositions have been applied only once for all calculations).

ACKNOWLEDGMENT

I thank Daphne Goodfellow who improved the readability of this paper.


Carmen Tur
email: c.tur@ion.ucl.ac.uk

MD Zhaleh Khaleeli
email: z.khaleeli@ion.ucl.ac.uk

Olga Ciccarelli
email: o.ciccarelli@ion.ucl.ac.uk

DPhil Daniel R Altmann
email: daniel.altmann@lshtm.ac.uk

Mara Cercignani
email: m.cercignani@hsantalucia.it

PhD D H Miller
email: d.miller@ion.ucl.ac.uk

J Thompson

O Mrcp

Ciccarelli

M Dphil

Cercignani

Professor Alan J Thompson
email: a.thompson@ion.ucl.ac.uk

Frcp

Complementary roles of grey matter MTR and T2 lesions in predicting progression in early PPMS

Keywords: 40, Tables: 3, Figures: 1, Suppl. tables: 3 Multiple sclerosis, MRI, MTI, Tur et al

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

Progression in primary progressive multiple sclerosis (PPMS) varies widely amongst patients [START_REF] Tremlett | The natural history of primary progressive MS in British Columbia, Canada[END_REF] , but, at present, only a few tools provide modest prediction of clinical outcome [START_REF] Tremlett | The natural history of primary progressive MS in British Columbia, Canada[END_REF] . Among these tools, conventional magnetic resonance imaging (MRI), including T2-weighted imaging, is attractive, since it can easily be performed and standardised across scanners. Although T2 lesion load at study entry did not predict progression in patients with established PPMS [START_REF] Sastre-Garriga | Long-term clinical outcome of primary progressive MS: predictive value of clinical and MRI data[END_REF][START_REF] Khaleeli | Predicting progression in primary progressive multiple sclerosis: a 10-year multicenter study[END_REF] , other features of T2 lesions, such as their increase over a short period of time, were reported to predict clinical outcome at five-year follow-up [START_REF] Sastre-Garriga | Long-term clinical outcome of primary progressive MS: predictive value of clinical and MRI data[END_REF] , suggesting that T2 lesion load may be relevant to determine disability, and, therefore, progression.

Whether T2 lesion load is a predictor of disability over a longer period in patients with early PPMS has not been addressed.

Another tool is magnetization transfer imaging (MTI), which, although being dependant on the characteristics of scanners and sequences, and therefore less suitable for multi-centre studies, has a higher pathological specificity than conventional MRI. Magnetization transfer ratio (MTR) reflects demyelination and axonal loss, and can be measured in normal-appearing tissue, i.e. outside visible lesions [START_REF] Schmierer | Magnetization transfer ratio and myelin in postmortem multiple sclerosis brain[END_REF] . We found that, in patients with early PPMS, MTR of the normalappearing white matter (NAWM) and grey matter (GM) at baseline were the best predictors of clinical outcome at one and three-year follow-up, respectively [START_REF] Khaleeli | Magnetisation transfer ratio in the normal appearing white matter predicts progression of disability over 1 year in early primary progressive multiple sclerosis[END_REF][START_REF] Khaleeli | Magnetization transfer ratio in gray matter: a potential surrogate marker for progression in early primary progressive multiple sclerosis[END_REF] .

Since MTR of GM predicted disability over a longer period than that of NAWM, and had, in addition, a steeper rate of change over time [START_REF] Khaleeli | Magnetization transfer ratio in gray matter: a potential surrogate marker for progression in early primary progressive multiple sclerosis[END_REF] , MTR of the GM appears the more promising candidate for predicting long-term progression in early PPMS.

Although not yet confirmed, it has been suggested GM MTR abnormalities reflect axonal damage [START_REF] Young | Imaging correlates of decreased axonal Na+/K+ ATPase in chronic multiple sclerosis lesions[END_REF] and, to a greater extent, demyelination [START_REF] Schmierer | Magnetization transfer ratio and myelin in postmortem multiple sclerosis brain[END_REF] , mainly within GM lesions [START_REF] Peterson | Transected neurites, apoptotic neurons, and reduced inflammation in cortical multiple sclerosis lesions[END_REF][START_REF] Geurts | Grey matter pathology in multiple sclerosis[END_REF] , since little is known about pathological findings outside GM lesions [START_REF] Geurts | Grey matter pathology in multiple sclerosis[END_REF] . Moreover, GM lesions have been found to play an important part in determining disability in other forms of MS [START_REF] Calabrese | Cortical lesions and atrophy associated with cognitive impairment in relapsing-remitting multiple sclerosis[END_REF][START_REF] Roosendaal | Accumulation of cortical lesions in MS: relation with cognitive impairment[END_REF] . These findings prompted investigation of the MTR of GM as a potential measure to predict disability in PPMS.

We hypothesised that T2 lesion load and MTR of the GM at study entry were independent predictors of clinical progression over a five-year follow-up in early PPMS. We also assessed whether T2 lesion load and MTR of the normalappearing brain correlated with progression over five years. We investigated the cohort of patients with early PPMS previously studied [START_REF] Khaleeli | Magnetisation transfer ratio in the normal appearing white matter predicts progression of disability over 1 year in early primary progressive multiple sclerosis[END_REF][START_REF] Khaleeli | Magnetization transfer ratio in gray matter: a potential surrogate marker for progression in early primary progressive multiple sclerosis[END_REF] and, in order to ensure that the effect of the imaging measures were independent of brain atrophy [START_REF] Bakshi | Predicting clinical progression in multiple sclerosis with the magnetic resonance disease severity scale[END_REF] , our statistical analyses controlled for the NAWM and GM brain volumes. Clinical progression was measured by the expanded disability status scale (EDSS) [START_REF] Kurtzke | Rating neurologic impairment in multiple sclerosis: an expanded disability status scale (EDSS)[END_REF] , and, since this measure is known to have limitations in reflecting accumulation of disability over time [START_REF] Hobart | Kurtzke scales revisited: the application of psychometric methods to clinical intuition[END_REF][START_REF] Bosma | The search for responsive clinical endpoints in primary progressive multiple sclerosis[END_REF] , we also used the subsets of the multiple sclerosis functional composite (MSFC) [START_REF] Cutter | Development of a multiple sclerosis functional composite as a clinical trial outcome measure[END_REF] , which is potentially more sensitive to clinical worsening [START_REF] Bosma | The search for responsive clinical endpoints in primary progressive multiple sclerosis[END_REF] .

METHODS

Subjects

Forty-seven patients with definite or probable PPMS [START_REF] Thompson | Diagnostic criteria for primary progressive multiple sclerosis: a position paper[END_REF] within five years of symptom onset and 18 healthy controls (10 female, mean age 34.56yrs., range 27-52) were studied at baseline (see their clinical and demographic characteristics in table 1). All subjects were then invited for clinical and radiologic assessment at baseline and every six months for three years, and again at five years. The number of individuals studied at each time point is shown in supplemental table 1. Although not all patients attended all time points, the use of linear mixed effect models allowed us to take into account all the clinical and radiologic data acquired at each time point for statistical analysis (see below), which corrected for the difference in age between patients and controls.

Regarding the five-year follow-up visit, 42 patients (16 female, mean age 44.38yrs., range 19-63) and 10 controls were assessed. The reasons for not being assessed, in patients, were: death for causes unrelated to MS (two cases); withdrawal from the study (three cases).

None of the patients was taking disease-modifying medication. Two patients had received a single course of intravenous corticosteroids for a deterioration of symptoms (two males, who received steroids at three and between three and five-year follow-up, respectively). Two patients were taking oral corticosteroids every three months (two males). One male patient took five courses of mitoxantrone between three and five-year follow-up.

Clinical assessments

At every visit, patients were scored on the EDSS [START_REF] Kurtzke | Rating neurologic impairment in multiple sclerosis: an expanded disability status scale (EDSS)[END_REF] . Where possible, patients were also scored on the MSFC subtests (i.e., the timed 25-foot walk test [TWT], the nine hole peg test [NHPT] and the paced auditory serial addition test [PASAT]) [START_REF] Cutter | Development of a multiple sclerosis functional composite as a clinical trial outcome measure[END_REF] . At the last follow-up visit, the EDSS was obtained in person in 27 patients; the EDSS of the remaining 15 patients was assessed by phone [START_REF] Lechner-Scott | Can the Expanded Disability Status Scale be assessed by telephone?[END_REF] , since they were too disabled to undergo MRI, and declined the invitation to attend in person. The MSFC scores were obtained in 26 patients (out of those 27 who attended their last appointment).

Image acquisition and processing

At each time point, all subjects underwent the whole brain sequences described below, acquired using a 1.5-Tesla GE Signa scanner (General Electric Co, Milwaukee, Wisconsin). The scanner was upgraded during the study, increasing the maximum gradient strength from 22 mTm-1 to 33 mTm-1, and changing the imager software version from 5x to 11x. 1) Magnetization transfer (MT) dual echo spin-echo sequence, including PD and T2-weighted images, acquired with and without a MT presaturation pulse to calculate the MT ratio (MTR) images [START_REF] Barker | An interleaved sequence for accurate and reproducible clinical measurement of magnetization transfer ratio[END_REF] . T2 lesions were contoured, and T2 lesion load (T2LL) and lesion masks were obtained [START_REF] Plummer | DispImage: Un mezzo di analisi e presentazione per iconografia medica (DispImage: a display and analysis tool for medical images)[END_REF] . GM and NAWM MTR histograms were generated (bin width, 0.1 percentage unit [PU]; smoothing window, 0.3 PU), and the histogram mean, peak location (PL) and peak height (PH) were calculated [START_REF] Khaleeli | Magnetization transfer ratio in gray matter: a potential surrogate marker for progression in early primary progressive multiple sclerosis[END_REF] .

2) 3D inversion prepared fast spoiled gradient recall (FSPGR) images.

Segmentation was carried out using SPM2 (Statistical Parametric Mapping; Wellcome Department of Cognitive Neurology), for consistency with previous studies in the same patient cohort. For each tissue class, the output of the algorithm is an image, whose voxel intensity represents the probability (from 0 to 1) of belonging to that class. To obtain binary masks for NAWM and GM, we set a threshold of 0.75 for the NAWM and GM map, meaning that only those voxels with a 75% or more likelihood of being NAWM and GM, respectively, were retained) [START_REF] Khaleeli | Magnetization transfer ratio in gray matter: a potential surrogate marker for progression in early primary progressive multiple sclerosis[END_REF][START_REF] Smith | Tract-based spatial statistics: voxelwise analysis of multi-subject diffusion data[END_REF] . In patients, binary lesion masks were applied to the tissue probability maps to obtain NAWM, lesions, and GM maps. GM and NAWM volumes were divided by the total intracranial volume (sum of GM, NAWM, lesion and cerebrospinal fluid volumes), to obtain normalised volumes. These resulting volumes were multiplied by 100 to produce percentage GM and NAWM fractions [START_REF] Khaleeli | Magnetization transfer ratio in gray matter: a potential surrogate marker for progression in early primary progressive multiple sclerosis[END_REF] .

Statistical analysis

Analysis was carried out with Stata 9.2 statistical software (Stata-Corp, College Station, Texas).

Assessment of clinical progression over five years

To assess changes in EDSS over time, the EDSS scores at baseline and at five years were compared using the Wilcoxon matched-pairs signed rank test, given its non-normal distribution. Changes in EDSS scores from baseline to five-year follow-up were then converted into steps by considering 1 step change equal to 1 point increase for values of EDSS of 5.5 or lower, and 0.5 increase in the EDSS for values of EDSS higher than 5.5, as previously described [START_REF] Khaleeli | Magnetisation transfer ratio in the normal appearing white matter predicts progression of disability over 1 year in early primary progressive multiple sclerosis[END_REF][START_REF] Khaleeli | Magnetization transfer ratio in gray matter: a potential surrogate marker for progression in early primary progressive multiple sclerosis[END_REF] ; this unequal step size helps to overcome the intrinsic limitation of the EDSS in depicting real clinical changes at different levels of the scale. To assess changes in z-scores over time, scores of 180secs. and 300secs. were assigned to the TWT and NHPT of patients who were unable to perform these tests [START_REF] Hoogervorst | A study validating changes in the multiple sclerosis functional composite[END_REF] . Then, all the MSFC subtests were transformed into z-scores (z-NHPT, z-TWT, and z-PASAT), using our baseline sample as reference [START_REF] Fischer | Administration and scoring manual for the MS Functional Composite measure (MSFC)[END_REF] . Finally, rather than perform paired t-tests which lose data on patients not present at both baseline and final follow-up, changes over time were assessed using linear mixed regression models [START_REF] Verbeke | Linear Mixed Models for Longitudinal data[END_REF] , which maximise the efficient use of all available data. In particular, each z-score recorded at each time point and for each subtest was used, in turn, as the dependent variable, and time was entered as the independent variable [START_REF] Laird | Random-effects models for longitudinal data[END_REF] .

Tur et al.

10

Prediction of clinical progression over five years

To identify predictors of progression, a multiple proportional odds ordinal logistic regression was used for the EDSS, and a multiple linear regression was used for the z-TWT, z-NHPT and z-PASAT. The EDSS step changes, and the z-score of each MSFC subtest at five-year were used as dependent variables, and age, gender, baseline z-scores (where appropriate) and baseline MRI measures were used as explanatory variables. To predict progression on the z-TWT, data from those unable to walk at baseline were excluded from the analysis, since their score at baseline would predict perfectly the score at five years, as both would be 180secs.

First, each MRI measure (i.e., MTR mean, PL and PH for GM and NAWM, percentage of GM and NAWM fractions, T2 lesion load) was entered singly into the model. Secondly, to assess the best MRI predictor of progression, the significant MRI measures were included together in a new regression model, and the significant variables retained, although a correlation between the MRI measures might contribute to a possible loss of significant association when they are put together into the model. Thirdly, to assess the proportion of variance of progression explained by the best MRI predictors (R-squared x100), final models were created considering only the MRI measures which were significant in the previous step.

Concurrent MRI and clinical changes over five years

To make the most efficient use of the data points, and to avoid bias from excluding subjects not present at both baseline and five years, associations between clinical and MRI changes were assessed using linear mixed longitudinal models [START_REF] Verbeke | Linear Mixed Models for Longitudinal data[END_REF] , which estimated rates of change using all of a subject's available data points. When the MRI measure was the response variable, and 'group' and time were the explanatory variables, the groupxtime interaction term coefficient assessed the extent to which the group variable was associated with rate of MRI change over time, and estimated the difference in rates between different groups. 'Group' variables were both subject type, and, within patients only, clinical progression category. Additional explanatory variables were age, gender, and an additional indicator for whether a data point was observed before or after April 2004, to adjust for a scanner upgrade at that time.

To assess the correlations between MRI changes and clinical changes over time, similar models were used in patients only, but with clinical change and clinicalxtime interaction replacing the subject terms. The EDSS clinical change variable had three categories: minimal progression (deterioration ≤ 0.5 steps, 13 patients), moderate progression (deterioration of 1-2.5 steps, 13 patients), and considerable progression (deterioration ≥ 3 steps, 16 patients). For MSFC components the continuous Z scores were used.

Residuals from the final models, in both prediction and correlation analyses, were checked for normality and outliers.

Tur et al.

12

RESULTS

Predictors of clinical progression over five years

Patients showed a significant increase in their disability during the follow-up, as measured by EDSS, z-TWT and z-NHPT (table 2). Progression on the EDSS was predicted by T2LL, NAWM PL MTR and percentage NAWM fraction measured at baseline (table 3). However, when these variables were put together into the same regression model to assess the best MRI predictor, none remained significant.

Worsening on z-TWT was predicted by T2LL, all the GM MTR histogram parameters, NAWM mean and PL MTR, and both percentages of GM and NAWM fractions (p<0.001) (table 3). When these variables were modelled together, T2LL, GM PL and PH MTR were significantly associated with progression (T2LL: Regression coefficient (RC, in z-TWT unit/mL) -0.04, 95%CI:

-0.08, -0.01, p=0.007; PL: RC (z-TWT unit/pu) 1.73 z-TWT, 95%CI: 0.53, 2.93, p=0.007; PH: RC (z-TWT unit/pv) 527.4, 95%CI: 227.09, 827.73, p=0.002). The final resulting model, including, baseline T2LL, GM PL and PH MTR, together with z-TWT at baseline and age, explained 91% of the variance, which was significantly higher than the percentages obtained when the MRI variables were modelled individually (from 68% for GM PH MTR, to 80% for T2LL).

None of the MRI measures predicted changes in the z-NHPT and z-PASAT.

Concurrent MRI and clinical changes over five years

In patients, T2LL significantly increased over five years follow-up and all the MTR histogram parameters (except GM PH and NAWM PH), and both percentages of GM and NAWM fractions, significantly decreased (Supplemental table 2). T2LL increased by about 3mL (95%CI 2.1-3.9, p<0.0001) every year.

Of the MTR measures, GM mean and PL MTR had the highest rate of reduction (RC: -0.384 and -0.235 per year, respectively). Of the volumetric measures, the percentage GM fraction decreased more than the percentage NAWM fraction (RC: -0.686 and -0.415 per year, respectively). In controls, none of the MRI measures changed over time. The rates of changes in all MRI measures, except GM and NAWM PH and PL MTR, were significantly greater in patients than in controls (Supplemental table 2).

In patients, a greater progression rate, as measured by EDSS, z-TWT, z-NHPT, and z-PASAT, correlated significantly with a steeper increase in T2LL (p<0.0005, p=0.001, p=0.009 and p=0.017, respectively). In addition, a greater decline in z-TWT and z-NHPT correlated with a faster rate of decline in GM mean MTR (p=0.008 and p=0.043, respectively); a steeper reduction in z-NHPT and z-PASAT correlated with a faster rate of reduction in GM PL MTR (p=0.045 and p=0.016, respectively). Finally, a greater rate of decline in z-NHPT correlated with a steeper reduction in NAWM PL MTR (p=0.025) (Supplemental table 3).

DISCUSSION

In this study of early PPMS we found evidence supporting the hypothesis that T2LL and GM MTR were independent predictors of the accumulation of disability, as measured by changes in TWT, considered a more responsive clinical endpoint in PPMS than the EDSS [START_REF] Bosma | The search for responsive clinical endpoints in primary progressive multiple sclerosis[END_REF] . We found that T2LL and GM MTR had complementary roles, since the model including them together with age and TWT at baseline, explained 91% of the variance of the progression (as measured by changes in TWT). This was significantly higher than the percentages obtained by T2LL and GM MTR histogram parameters alone. A possible explanation for this finding is that combining T2LL and GM MTR provides a comprehensive assessment of the visible damage occurring in the white matter and of the "occult" involvement of the GM. However, the finding of a significant role of T2LL in predicting progression independently from the other MRI measures is in contrast with the results of the MAGNIMS studies performed in patients with well established PPMS [START_REF] Sastre-Garriga | Long-term clinical outcome of primary progressive MS: predictive value of clinical and MRI data[END_REF][START_REF] Khaleeli | Predicting progression in primary progressive multiple sclerosis: a 10-year multicenter study[END_REF] , which reported that baseline T2LL did not predict progression after five and ten years. This may suggest the relevance of the T2LL to the accrual of disability declines in the later stages of PPMS. A similar finding has also been reported in the 20-year follow-up study of patients with relapse onset MS [START_REF] Fisniku | Disability and T2 MRI lesions: a 20year follow-up of patients with relapse onset of multiple sclerosis[END_REF] .

With regard to the GM damage, GM lesions are mostly undetected on conventional images [START_REF] Geurts | Intracortical lesions in multiple sclerosis: improved detection with 3D double inversion-recovery MR imaging[END_REF] , so that the damage in this tissue compartment, which has been reported to be extensive [START_REF] Geurts | Grey matter pathology in multiple sclerosis[END_REF] , cannot be assessed with conventional scans.

Instead, MTI has a higher histopathological specificity than T2 scans [START_REF] Barkhof | Imaging outcomes for neuroprotection and repair in multiple sclerosis trials[END_REF] , although both normal-appearing GM damage and GM lesions may contribute to the observed abnormal GM MTR. Our findings, therefore, extend the results of our three year follow-up study performed in the same patient cohort [START_REF] Khaleeli | Magnetization transfer ratio in gray matter: a potential surrogate marker for progression in early primary progressive multiple sclerosis[END_REF] , by highlighting the relevance of GM damage in determining disability, and therefore long-term progression, in patients with early PPMS. Due to the method used to segment the GM tissue, both cortical GM MTR and deep GM MTR contributed to the final MTR values. Thus, it is plausible that structures such as the thalamus, which is known to be affected by atrophy in PPMS [START_REF] Sepulcre | Regional gray matter atrophy in early primary progressive multiple sclerosis: a voxel-based morphometry study[END_REF] that correlates with disability [START_REF] Khaleeli | Localized grey matter damage in early primary progressive multiple sclerosis contributes to disability[END_REF] , plays a role, in addition to the cortical GM damage, in contributing to progression. The prominent role of GM damage in determining disability in PPMS has been also suggested by other authors, who reported that GM damage quantified by means of diffusion tensor MRI at study entry was the best MRI predictor of clinical progression over the following five years [START_REF] Rovaris | Grey matter damage predicts the evolution of primary progressive multiple sclerosis at 5 years[END_REF] .

Another important finding of our study was the strong correlation between clinical progression and changes in T2 lesion load and GM MTR over five years. However, while T2 lesion load changes correlated with clinical deterioration measured by all the clinical scales, the GM MTR decline strongly correlated with MSFC subtests decrease and only a trend was achieved for the correlation with EDSS changes. These findings highlight the higher sensitivity of the MSFC in detecting clinical changes [START_REF] Bosma | The search for responsive clinical endpoints in primary progressive multiple sclerosis[END_REF] when compared with the EDSS, and extend the results of the 10-year MAGNIMS study in patients with PPMS [START_REF] Khaleeli | Predicting progression in primary progressive multiple sclerosis: a 10-year multicenter study[END_REF] , which showed that the TWT at baseline predicted clinical progression, whilst EDSS did not.

We also found that the T2 lesion load and GM mean and PL MTR showed dynamic changes over time in patients, and distinguished between patients and controls, in agreement with previous reports [START_REF] Khaleeli | Magnetization transfer ratio in gray matter: a potential surrogate marker for progression in early primary progressive multiple sclerosis[END_REF][START_REF] Davies | Increasing normalappearing grey and white matter magnetisation transfer ratio abnormality in early relapsing-remitting multiple sclerosis[END_REF] . Also, rates of GM MTR changes over time were higher than those of NAWM, suggesting that GM pathology changed more rapidly than the NAWM. Since a similar result has been reported in patients with early relapsing-remitting MS [START_REF] Davies | Increasing normalappearing grey and white matter magnetisation transfer ratio abnormality in early relapsing-remitting multiple sclerosis[END_REF] , one possible conclusion is that GM abnormalities develop faster than NAWM changes in the early stages of the disease.

We found that although NAWM MTR and percentage of NAWM and GM fractions predicted progression, especially if this was measured by TWT, when they were entered individually into the model, they became non-significant when they were modelled together and with the other MTR histogram parameters, suggesting that their role is less important than that of the T2 lesion load and the GM damage. The presence of strong correlations between the MRI measures may well have also contributed to the loss of correlation when they were combined. However, a recent paper reported that brain and spinal cord atrophy and GM MTR, when combined together, correlated with EDSS in patients with PPMS, who had a mean disease duration of 9.6 years [START_REF] Rovaris | Large-scale, multicentre, quantitative MRI study of brain and cord damage in primary progressive multiple sclerosis[END_REF] , suggesting that the role of CNS atrophy may be important if spinal cord atrophy is included, especially when patients with well-established PPMS are studied.

From the clinical point of view, patients significantly deteriorated over time on all the EDSS, TWT and NHPT, suggesting that progression in this cohort of early PPMS mainly related to the deterioration of motor function. Interestingly, the two MSFC subtests which reflected motor function (TWT and NHPT) showed stronger and more frequent correlations with the MRI measures than the EDSS.

Despite the lack of progression on the PASAT over time in our cohort as a whole, probably due to a learning effect [START_REF] Khaleeli | Magnetization transfer ratio in gray matter: a potential surrogate marker for progression in early primary progressive multiple sclerosis[END_REF] , we found that people with higher cognitive decline over five-years had steeper decline of GM MTR and higher lesion load increase, suggesting that these radiological measures have an impact on cognition in PPMS, as previously reported [START_REF] Camp | A longitudinal study of cognition in primary progressive multiple sclerosis[END_REF][START_REF] Ukkonen | Cognitive dysfunction in primary progressive multiple sclerosis: a neuropsychological and MRI study[END_REF][START_REF] Ramio-Torrenta | Abnormalities in normal appearing tissues in early primary progressive multiple sclerosis and their relation to disability: a tissue specific magnetisation transfer study[END_REF] . However, this finding should be taken cautiously, and further studies are needed to clarify the relative contribution of GM MTR changes to cognitive decline in PPMS.

Although a number of statistical tests are reported in this paper, we did not feel it was appropriate to adjust for multiple comparisons, as a number of separate null hypotheses was examined, rather than one single null hypothesis, whose error rate is affected by every reported test [START_REF] Perneger | What's wrong with Bonferroni adjustments[END_REF][START_REF] Rothman | No adjustments are needed for multiple comparisons[END_REF] .

A possible limitation of this prospective, longitudinal study is that the number of patients who underwent the MRI scan and were assessed on the MSFC subtests at five years was lower compared to the number of patients studied at baseline. However, we used mixed effects models [START_REF] Verbeke | Linear Mixed Models for Longitudinal data[END_REF] which estimate the mean rate of change of the response variable over time using information from all available data points in each subject. This minimises the bias which can result from excluding patients with missing data at the last time point (such patients may have higher or lower individual rates than other patients). Another limitation is that we did not take into consideration the involvement of the spinal cord, which may play a role in the development of disability in PPMS [START_REF] Oppenheimer | The cervical cord in multiple sclerosis[END_REF]40 .

Finally, this study has the longest follow up of a cohort of early PPMS comprehensively investigated by means of MTI. We showed that combining measures that reflected both GM and WM damage improved on the currently available tools to predict the accrual of disability in PPMS. This combined assessment is more accurate in predicting clinical progression than previous approaches, which focused mainly on the WM damage, and, in particular, on the lesion load. Thus this approach may be of benefit either to monitor treatment effects or to identify patients with a higher risk for developing irreversible disability, for whom more aggressive therapeutic approaches might be offered.

In conclusion, a comprehensive assessment of the damage occurring in the WM and GM is an attractive approach that offers insights into the pathological mechanisms underlying progression in MS and may help to predict clinical progression.

(

  The study was approved by the Joint Medical Ethics Committee of the National Hospital for Neurology and Neurosurgery and the Institute of Neurology, London, England.

(LegendFigure 1 .

 1 Figure 1. Predicted versus real z-TWT scores at five years. This graph

Table 1 .

 1 40) Stevenson VL, Leary SM, Losseff NA, et al. Spinal cord atrophy and disability in MS: a longitudinal study. Neurology 1998 Jul;51(1):234-238. Clinical and demographic characteristics of subjects at the study entry.Results are mean (SD) unless otherwise stated.

	Tur et al.

Table 1 (

 1

footnote). EDSS: expanded disability status scale; z-TWT: timed 25foot walk test z-score; z-NHPT: nine hole peg test z-score; z-PASAT: paced auditory serial addition test z-score. SD: standard deviation.

Table 2 .

 2 Clinical data in patients at baseline and at five years follow-up, and clinical changes over time.

Table 2 (footnote).

 2

	PASAT: paced auditory serial addition test. SD: standard deviation; RC (95%CI):
	regression coefficient (given as z-score unit change/year) (95% confidence
	interval), which represents the annual change of each z-score; p: p value.

a : Wilcoxon matched-pairs signed rank test; b : Longitudinal model (see text for further details). EDSS: expanded disability status scale; z-TWT: timed 25-foot walk test z-score; z-NHPT: nine hole peg test z-score; z-

Table 3 .

 3 Results of the regression models used to predict progression when MRI measures were entered individually into the model.

	MRI MEASURES MODELLED INDIVIDUALLY (FIRST STEP)
	Baseline
	MRI	EDSS				z-TWT		z-NHPT			z-PASAT
	measures	OR	p	a	R 2	RC	p b	R 2	RC	p b	R 2	RC	p b	R 2
		(95%CI)				(95%CI)		(95%CI)			(95%CI)
	T2LL	1.03	0.015	0.09	-0.09	0.0001 0.80 -0.01	0.080	0.77	-	0.131	-
		(1.01, 0.05)				(-0.12, -		(-0.03,
						0.06)		0.002)
	GM mean	0.61	0.057	0.08	1.52	0.0001 0.76 -		0.450	-	-	0.120	-
	MTR	(0.36, 1.02)				(0.90, 2.14)
	GM PL MTR	-	0.255	-	3.29	0.0001 0.74 -		0.293	-	-	0.705	-
						(1.81, 4.77)
	GM PH MTR	-	0.154	-	858.12	0.001	0.68 -		0.447	-	-	0.263	-
						(381.44,
						1334.81)
	NAWM mean	0.58	0.093	0.07	2.15	0.0001 0.74 -		0.371	-	-	0.270	-
	MTR	(0.30, 1.1)				(1.2, 3.09)
	NAWM PL	0.44	0.029	0.08	2.11	0.0001 0.73 -		0.407	-	-	0.249	-
	MTR	(0.21, 0.92)				(1.13, 3.1)
	NAWM PH	-	0.324	-	266.4	0.052	0.56 -		0.952	-	-	0.444	-
	MTR					(-1.93,
						534.72)
														-
	PGMF	-	0.165	-	0.63	0.001	0.69 -		0.116	-	-	0.138
						(0.28, 0.97)
	PNAWMF	0.78	0.037	0.08	0.70	0.0001 0.71 -		0.183	-	-	0.278	-
		(0.61, 0.99)				(0.35, 1.05)

Table 3 (

 3 footnote). a : Multiple proportional odds ordinal logistic regression (results adjusted by age and gender); b : Multiple linear regression analysis

Acknowledgements:

Dr Tur had full access to all of the data in the study and takes responsibility for the integrity of the data and the accuracy of the data analysis.

The authors thank the subjects for kindly agreeing to take part in this study. The MS NMR Research Unit is supported by the MS Society of Great Britain and Northern Ireland. This work was undertaken at UCLH/UCL who received a proportion of funding from the Department of Health's NIHR Biomedical Research Centres funding scheme. C. Tur is funded by the Multiple Sclerosis International Federation. O. Ciccarelli is a Wellcome Advanced Fellow. The Corresponding Author has the right to grant on behalf of all authors and does grant on behalf of all authors, an exclusive licence (or non-exclusive for government employees) on a worldwide basis to the BMJ Group and co-owners or contracting owning societies (where published by the BMJ Group on their behalf), and its Licensees to permit this article (if accepted) to be published in Journal of Neurology, Neurosurgery and Psychiatry and any other BMJ Group products and to exploit all subsidiary rights, as set out in our licence Disclosures: C. Tur was funded by the Multiple Sclerosis International Federation (McDonald Fellowship) and has received honoraria and support for travel from Serono Foundation and Sanofi-Aventis Z. Khaleeli was funded by the MS Society of Great Britain and Northern Ireland O. Ciccarelli was funded by the Wellcome Trust and receives an honorarium for work as Clinical Editor of Current Medical Literature -Multiple Sclerosis. D.R. Altmann reports no conflicts of interest. M. Cercignani was funded by the Italian Ministry of Health (grant number PS05.5B) and has received travel expenses and/or honoraria for lectures or educational activities not funded by industry. D. H. Miller has received honoraria from UCB Pharma, Schering, Biogen Idec, GSK, and Wyeth for consulting services, speaking, and serving on a scientific advisory board. He has received reimbursement for work as co-chief Editor of Journal of Neurology and research grant support from the MS Society of Great