* Dso

G H &kdohqgdu

6\VWHP WR &ODVVLI\ 1RXQV LQ &RQWH[W

$EVWUDFW Using semantic knowledge in NLP applications always improves their competence. Broad lexicons have been developed, but there are few resources made for non-specialized domains which contain semantic information available for words. In order to build such a base, we conceived a system, SVETLAN', able to learn categories of nouns from texts, whatever their domain. In order to avoid general classes mixing all the meanings of words, they are learned taking into account the contextual use of words.

,1752'8&7,21

Using semantic knowledge in NLP applications always improves their competence as in Information Retrieval or Word Sense Disambiguation systems. Broad lexicons have been developed, but there are few existing resources which contain semantic information available for words that are not specialized to very specific domains apart from WordNet [START_REF] Fellbaum | WordNet: an electronic lexical database[END_REF]. Moreover, manual or automatic processes that build semantic categories of nouns usually lead to define general categories. For example, words in WordNet are related to a Synset when they are synonymous, however Synsets correspond to large categories, and there are some shifts of meaning so that when two words belonging to a same Synset are considered within a specific context, they often no longer share a common meaning. Automatic processes that extract knowledge from texts by using statistical [START_REF] Zernik | TRAIN2: Tagging Word Senses in Corpus[END_REF] or distributional [START_REF] Greffenstette | Explorations in automatic thesaurus discovery[END_REF], [START_REF] Faure | Learning subcategorization frames and restrictions of selection[END_REF] approaches also lead to build broad classes, if they are not applied to specialized texts belonging to a very specific domain. On the other hand, we do not want to learn a general ontology, whatever the domain is. As most words are polysemous, we claim that a semantic base has to deal with all the meanings of a word, by associating them with their context of interpretation. Having such a semantic knowledge will allow information retrieval and Question/Answering systems for example to use deeper semantic analysis of texts, even if applied on database that contain texts on different domains which are non technical articles and uses a general and common vocabulary such as newspaper articles bases.

In order to build such a base, we conceived a system, SVETLAN', able to learn categories of nouns in context from texts, whatever their domain. It is based on a distributional approach: nouns playing the same syntactic role with a verb in sentences related to the same topic, i.e. the same domain, are aggregated in the same class. SVETLAN' relies on knowledge about semantic domains automatically learned by SEGAPSITH [START_REF] Ferret | A Thematic Segmentation Procedure for Extracting Semantic Domains from Texts[END_REF].

29(59,(: 2) 7+( 6<67(0 Input data of SVETLAN' (see Fig. 1) are semantic domains with the Thematic Units (TUs) that have given birth to them. Domains are sets of weighted words, relevant to represent a same specific topic. They are automatically learned by aggregating similar thematic units, made of sets of words. Each TU corresponds to a part of text that is homogeneous from a topic point of view and is delimited from a text by a topic segmentation process relying on lexical cohesion. Processed texts are newspaper articles that are pre-treated in order to retain only lemmatized content words.

Domain TU TU TU TU TU Structured Domain V r N1, N2, … V r N1, N2, … V r N V r N STU V r N V r N STU Text Segment TU Text Segment

Input data

Avtrà . Schemata of Structured Domain learning

The first step of SVETLAN' consists of retrieving text segments of the original texts associated to the different TUs in order to parse their sentences. We extract then all the triplets constituted by a verb, the head noun of a phrase and its syntactic role from the parser results in order to produce the Syntactic Thematic Units (STUs). The STUs belonging to a same semantic domain are aggregated altogether to learn a Structured Domain. Aggregation leads to group nouns playing the same syntactic roles with a verb in order to form classes. As these aggregations are made within TUs belonging to a same domain, classes are context sensitive, which ensures a better homogeneity. A filtering step, based on the weights of the words in their domain allows the system to eliminate nouns from classes when they are not very relevant in this context.

6(0$17,& '20$,1 /($51,1*

We only give here a brief overview of the semantic domain learning module. This one is described more precisely in [START_REF] Ferret | A Thematic Segmentation Procedure for Extracting Semantic Domains from Texts[END_REF]. This module incrementally builds topic representations, made of weighted words, from discourse segments delimited by SEGCOHLEX [START_REF] Ferret | How to thematically segment texts by using lexical cohesion[END_REF]. It works without any D SULRUL classification or hand-coded pieces of knowledge. Processed texts are typically newspaper articles coming from /H 0RQGH or $)3 $JHQFH )UDQFH 3UHVVH. They are pre-processed to only keep their lemmatized content words (adjectives, single or compound nouns and verbs).

The topic segmentation implemented by SEGCOHLEX is based on a large collocation network, built from 24 months of /H 0RQGH newspaper, where a link between two words aims at capturing semantic and pragmatic relations between them. The strength of such a link is evaluated by the mutual information between its two words. The segmentation process relies on these links for computing a cohesion value for each position of a text. It assumes that a discourse segment is a part of text whose words refer to the same topic, that is, words are strongly linked to each other in the collocation network and yield a high cohesion value. On the contrary, low cohesion values indicate topics shifts. After delimiting segments by an automatic analysis of the cohesion graph, only highly cohesive segments, named Thematic Units (TUs), are kept to learn topic representations. This segmentation method entails a text to be decomposed in small thematic units, whose size is equivalent to a paragraph. Discourse segments, even related to the same topic, often develop different points of view. To enrich the particular description given by a text, we add to TUs those words of the collocation network that are particularly linked to the words found in the corresponding segment. Learning a complete description of a topic consists of merging all successive points of view, i.e. similar TUs, into a single memo-rized thematic unit, called a semantic domain. Each aggregation of a new TU increases the system's knowledge about one topic by reinforcing recurrent words and adding new ones. Weights on words represent the importance of each word relative to the topic and is computed from the number of occurrences of these words in the TUs. This method leads SEGAPSITH to learn specific topic representations as opposed to [START_REF] Lin | Robust Automated Topic Identification[END_REF] for example whose method builds general topic descriptions as for economy, sport, etc.

We have applied the learning module of SEGAPSITH on one month (May 1994) of $)3 newswires. Figure 2 shows an example of a domain about justice that gathers 69 TUs.

As some of these domains are close and refer to the same general topic, we have applied a hierarchical classification method based on their common words to organize them in separate general topics and to structure them. Figure 3 shows the hierarchies built about sport, police and stock exchange. Each leaf is a domain, named by its two more weighted words, while internal nodes are described by their name and their size, i.e. the number of common words found in their children. As in [START_REF] Faure | Learning subcategorization frames and restrictions of selection[END_REF], verbs allow us to categorize nouns. A class is defined by those nouns which play a same role relative to a same verb. In order to learn very homogeneous3 classes, we only apply this principle on words belonging to a same context, i.e. a domain.

6\QWDFWLF DQDO\VLV

In order to find the verbs and their arguments in the texts, we use the syntactic analyzer Sylex [START_REF] Constant | Analyse Syntaxique Par Couches[END_REF], [START_REF] Constant | L'analyseur linguistique SYLEX. 5ème ecole d'été du CENT[END_REF]. Figure 4 shows a little part of the results of Sylex for a sentence. The first part exhibits lexicosyntactic information for the words and this for four different interpretations pointed out by the string "WDX[ " meaning an ambiguity rate of 4. This rate is due to the fact that Sylex cannot solve two ambiguities: the ambiguity of "ODLVVH" between the verb "ODLVVHU" (to let) and the noun "ODLVVH" (leash) and the ambiguity of "FULWLTXH" between the verb "WR FULWLFL]H" and the noun "FULWLFLVP". Note that Sylex does not consider the adjectival form which is the right interpretation here. The second part shows syntactic links found by Sylex. Between parenthesis are references to the words in the preceding analysis. Here Sylex has found four times the same interpretation in each of its possible analyses. In this case, we count one occurrence of the link. However if it finds several times the same relation between a verb and different words, for example several possible subjects, then we keep all the different interpretations because we have no way to choose between them. We make the reasonable expectation that the false interpretations will have much less occurrences in the corpus and so, will be filtered out during the rest of the processing. The results of Sylex are very detailed and not easy to parse directly with, say, Perl. Furthermore, we do not need all the information it extracts. In fact, we only need to find the verb with its links and the head nouns arguments of these links. So, we have developed a formal grammar that extracts from these raw analyzes the associations between a verb and its arguments. This grammar extracts links from the results of Sylex in the following format:

i # j verb # WRNHQ # OHPPD # k rel # WRNHQ # OHPPD # l
where i and j are the boundaries of the sentence that contains the link in the corpus; WRNHQ and OHPPD are the token and the lemma of the verb respectively ; rel is the syntactic relation which can be "subject", "direct object" or a preposition ("to", "from", etc.) ; WRNHQ and OHPPD are the token and the lemma of the head noun of the noun phrase pointed by the relation; lastly, N and O are the indexes in the corpus of WRNHQ and WRNHQ respectively. Figure 5 shows some links that we have extracted from the results of Sylex. Sylex, as other syntactic analyzers, has difficulties with some constructions and as a consequence introduces errors that can cause problems to the remaining of the system. Some common errors are the bad interpretation of the passive form that causes a subject to be analyzed as a direct object and conversely, a direct object to be viewed as a subject. Another common error is that it often happens that Sylex does not find any link in a phrase. That's what we will call VLOHQFH. We will see in Section 5 that we can obtain good results despite these problems thanks to the redundancy needed to validate the links in the next steps of processing. But another consequence of this redundancy needs is that the system must use great quantities of texts in order to create classes with a satisfactory size.

Having gotten the syntactic links in the texts, we want to group them relatively to the belonging of their text segment to a Thematic Unit. So, we define a Syntactic Thematic Unit (STU) as a set of <9HUEÅV\QWDFWLF UHODWLRQÅ1RXQ> structures, i.e. a syntactic relation instantiated with a verb and a noun. We will refer to these structures as Instantiated Syntactic Relations or ISR. We are able to put in relation the links extracted from the results of Sylex and the words contained in the domains because each domain in the thematic memory remembers which thematic units have been used to create it. In the same way, each thematic unit remembers the part of text it comes from.

$JJUHJDWLRQ

In order to construct group of words with very similar meanings, we want to group the nouns appearing with the same syntactic role in relation to a verb inside a Domain. Then, a Structured Domain (SD) is a set of <9HUEÅV\QWDFWLF UHODWLRQÅ1RXQ 1 « 1RXQ n > structures, i.e. an aggregated ISR.

STUs related to a same domain are aggregated altogether to form a Structured Domain. Aggregating a STU within a SD consists of:

-aggregating their ISR that contain a same verb ; -adding new ISR, i.e. adding new verbs with their arguments made of a syntactic relation and the lemmatized form of a noun.

Figure 6 shows the aggregation of a SD and three ISR. This example shows all the possible effects of the aggregation. In the figure, bold elements represent new or updating data. Aggregating an ISR in a SD that already contains the verb of the ISR leads to increment the occurrence number of the verb, as for SOD\ in the example. Similarly, the occurrence number of same nouns related to the verb by the same relation are updated (as for PDWFK), and new relations with their associated nouns are added to the verb. In the example, the subject FKDPSLRQ is added. An ISR with a new verb is simply added with an occurrence of 1, as for <to ORVHÅ REMHFWÅ FKDPSLRQVKLS>.

object cup [START_REF] Greffenstette | Explorations in automatic thesaurus discovery[END_REF], match [START_REF] Fellbaum | WordNet: an electronic lexical database[END_REF] to play [START_REF] Faure | Learning subcategorization frames and restrictions of selection[END_REF] with ball [1] subject player [START_REF] Fellbaum | WordNet: an electronic lexical database[END_REF] to win [START_REF] Zernik | TRAIN2: Tagging Word Senses in Corpus[END_REF] object match [START_REF] Fellbaum | WordNet: an electronic lexical database[END_REF] "ÃDhvhrqÃThpvpÃSryhvÃpr subject champion to play object match to lose object championship ThpvpÃ9hvÃry object cup [START_REF] Greffenstette | Explorations in automatic thesaurus discovery[END_REF], match [!] with ball [START_REF] Fellbaum | WordNet: an electronic lexical database[END_REF] to play [$] iwrp puhvÃb d

subject player [START_REF] Fellbaum | WordNet: an electronic lexical database[END_REF] to win [START_REF] Zernik | TRAIN2: Tagging Word Senses in Corpus[END_REF] object match [START_REF] Fellbaum | WordNet: an electronic lexical database[END_REF] ÃyrÃb d iwrp puhvuvÃb d

AvtrÃ%Ã An example of the aggregation of three ISR in a SD Classes of nouns in the produced SDs contain a lot of words that disturb their homogeneity. These words often belong to parts of the different TU at the origin of the SD that are not very related to the described topic. Either they result from an error of the topic segmentation process or they correspond to a meaning of a verb scarcely used in the current context. Another possibility is that the ISR results from an error of Sylex. As these cases do not often recur for the same words in the same context, their nouns are weekly weighted in the corresponding domains. This characteristic gives us a mean to filter the class content: each noun that possesses a weight lower than a threshold is removed from the class. By this selection, we reinforce learning classes of words according to their contextual use. Figure 7 shows two aggregated links first obtained without filtering in its upper part and the filtered counterparts in its lower part. The class associated to the verb 'WR HVWDEOLVK' has been completely removed as the weights of both 'EDVH' and ']RQH' are lower than the threshold, while the class related to the verb 'WR DQVZHU' with the 'REMHFW ¶ link has been reduced by removing 'OLVW'. We can see on this example that this filtering is efficient: the verb 'WR HVWDEOLVK' as the words 'EDVH ¶ and ']RQH ¶ are not very related to the domain of 'QXFOHDU ZHDSRQV' from which this example is taken and the usage of 'WR DQVZHU D OLVW' has a very low probability. More details on the effects of the filtering process will be given in section 5. In the principle, the described operations are not very complicated. The difficulties comes from the necessity to work with data coming from various tools. Furthermore, for performance and practical reasons, we do not apply the chain of tools text by text. The natural way to see the process would be to :

Ãrhiyvu iwrp base, zone

• read a text, • extract the TUs from it, • extract the corresponding STUs, • add each TU to its domain, • add each STU to its corresponding domain, and after the processing of all the texts, to filter the classes.

In fact, each computing step is done on the entire corpus and the results are next aligned. This allows us to save computation time as we do not have to run each tool multiple times. However we have to deal with dictionaries and indexes for various files and tools.

5(68/76

The experiments 4 we have conducted had as a goal to show that SVETLAN' lead to learn classes of words which obviously belong to the same concept in the domain. To obtain such results we have chosen to run our system on one month of $)3 $JHQFH )UDQFH 3UHVVH) wires, that forms a corpus stylistically coherent but that covers varied subjects with very polysemous and non specific verbs.

These wires are made of 4,500,000 words and 48,000 sentences in 6,000 texts. The thematic analysis gives 8,000 TUs aggregated in 2,000 domains. More details on these domains can be found in [START_REF] Ferret | A Thematic Segmentation Procedure for Extracting Semantic Domains from Texts[END_REF]. From these 48,000 sentences, 117,000 different Instantiated Syntactic Links are extracted by Sylex. 24,000 of these links concern subject, direct object, or circumstantial complements introduced by a preposition and are integrated in 1,531 Structured Domains.

After aggregating, but before filtering, the system obtains 431 aggregated links with two or more arguments, equivalent to 431 word classes. Some of them, such as WR PDQXIDFWXUH Å GLUHFW REMHFW Å ERPE ZHDSRQ! are good. Nevertheless other classes are heterogeneous as WR UHWXUQ Å GLUHFW REMHFW Å WHUULWRU\ VWULS FRQWH[W V\QDJRJXH! (here strip comes from the Gaza Strip), or clearly mix different meanings of a verb, like WR TXLW Å GLUHFW REMHFW Å EDVH JRYHUQPHQW! which mix together the meanings "to leave a place" and "to retire from an institution". For the two latter cases, one can see the interest to take into account the fact that the domains contain words with different weights representing their relevance to this domain. The higher the weight, the higher the relevance of this word in this domain. So we apply the aforesaid filter to our classes and retain only those with weights higher than a threshold. The class WHUULWRU\ VWULS FRQWH[W V\QDJRJXH! is corrected to WHUULWRU\ VWULS! and EDVH JRYHUQPHQW! is removed.

Among the wrong classes, some are due to errors of Sylex, as WR FRQIHUÅ GLUHFW REMHFW Å SULFH DFWRU! where DFWRU should be linked to WR FRQIHU by the preposition WR. The remaining others are due to the extensive use of two different meanings of the verb in the same domain, as for WR FRQGXFWWR PDQDJH Å GLUHFW REMHFW Å GHOHJDWLRQ QHJRWLDWLRQ! (in French: "conduire une négociation/une délégation"). This kind of error is inherent to the method we use and should be removed by other means. Note that the correctness of the links have been manually judged by ourselves. The precision measure used below is the ratio between the number of good classes and the total number of classes. We cannot define a recall measure because we have no way to know which classes we 4 Please note that all the tests have been made in French. So the English examples that appear here are translations from French. miss. To our knowledge, there is no existing resources with associated classes that would allow us to formally judge the results.

We have tried two thresholds: 0.05 and 0.1. Figure 8 details the results for both. After filtering, a lot of classes are removed but the remaining classes are well funded in most cases. An example of a retained class for both thresholds is : WR LQMXUHÅ VXEMHFW Å FRORQLVW VROGLHU! With a threshold set to 0.1 rather than to 0.05, we retain only 38 links, but we gain 8% in precision. If we ignore the errors due to Sylex, the real precision of SVETLAN' is in the first case 78% and in the second case 87%. It is very good and shows the interest there is to choose a good threshold.

Our experiments lead to homogeneous classes containing words denoting a same concept, though these classes contain few words. In order to directly view the interest there is to construct and cluster classes of words in being guided by their belonging to a domain, it is interesting to see what kind of classes would be obtained by the merging of all domains, that is to say : creating context-free classes. So, we have applied the same aggregation principle to the same corpus but without taking into account the domains. Just below, we show two classes for the verb "WR UHSODFH". The top one is made context-free and the bottom one is made inside a domain. This verb is very general. Virtually everything can be replaced ! WR UHSODFH REMHFW text, constitution, trousers, combustible, law, dinar, rod, film, circulation, judge, season, device, parliament, battalion, police, president, treaty WR UHSODFH REMHFW combustible, rod

The first group of words merges very different senses while the second class, much more little, is better because it contains words referring to very similar concepts: a rod of enriched uranium is nuclear combustible, thus the words "URG" and "FRPEXVWLEOH" actually denote the same concept in the nuclear domain. Another example is the following, for the verb "WR DWWULEXWH": WR DWWULEXWH REMHFW talk, prize, decoration, pope, responsibility, television, attempt, letter, contract, ministry, jury, funds, authority, note, bonus, band, bombing WR DWWULEXWH REMHFW prize, decoration Obtaining meaningful classes with a corpus such as $)3 shows the efficiency of our method. Moreover, it is very good to obtain cohesive classes for verbs very general and polysemous.

At this time, the class sizes are little. They do not contain a lot of words. A way to enlarge them could be to regroup classes that are related to the same verb, by the same syntactic relation in two domains belonging to the same hierarchy, i. e. a same more general context, assuming the words always have the same meaning. However this method has to be tested on more results in order to prove its reliability. With our results, we would build for example (law, constitution, article, disposition) in the domain of "/DZ" and (rebel, force, northerner, leader) in the domain of "FRQIOLFW". SVETLAN', in collaboration with SEGAPSITH, allows an automatic learning of structured semantic domains. Instead of just having sets of weighted words for describing semantic domains, domains are described by a set of verbs related to classes of words by a syntactic link. Besides, we can also view this base as semantic classes, each one being related to its context of interpretation.

As SVETLAN' works with very specific domains, it builds small classes. In order to generalize them, we could apply a process analogous to ASIUM, that merges classes independently of the related verbs according to a similarity measure, even if, in our case, this generalization process would operate in a same general domain. Afterwards, ASIUM asks an expert to validate its results.

Words are often polysemous or ambiguous. However, when used in context, they only denote one meaning, and moreover this meaning is generally the same in different occurrences of a same context. When building classes of nouns according to their contextual use, we avoid mixing all the meanings of a word, either for the verbs or for the nouns. Such a result can be exhibited in the classes (law, constitution) and (law, article, disposition) in the juridical context, where the words "DUWLFOH", "FRQVWLWXWLRQ" and "GLVSRVLWLRQ" do not attract synonymous of their other meanings as "VHFWLRQ", "FRPSRVLWLRQ" and "DSWLWXGH" for example.

5(/$7(' :25.6

There is a lot of works dedicated to the formation of classes of words. These classes have very various status. They can contain words belonging to the same semantic field or near synonymous.

WordNet [START_REF] Fellbaum | WordNet: an electronic lexical database[END_REF] is a lexical database made by lexicographers. It aims at representing the sense of the bigger part of the lexicon. It is composed of Synsets. A Synset is a set of words that are synonymous. These Synsets are linked by IS A relations. Its coverage is large but this is, in a sense, a shortcoming as its classes are too large and do not refer to precise meanings. Indeed, the generality of its contents makes it difficult to use in real sized applications that are often centered on a domain. It rarely can be used without a lot of manual adaptation.

IMToolset, by Uri Zernik [START_REF] Zernik | TRAIN2: Tagging Word Senses in Corpus[END_REF], extracts, for a word, several clusters of words from text. Each of these clusters reflects a different meaning of the studied word. This extraction is done by scanning the local contexts of the word, the 10 words surrounding it in the texts. These signatures are statistically analyzed and clustered. The result is groups of words that are similar to our domains but more focused on the sense of a word alone.

We have already stressed out some characteristics of ASIUM by D. Faure and C. Nedellec [START_REF] Faure | Learning subcategorization frames and restrictions of selection[END_REF], and we give here some more details. ASIUM learns subcategorization frames of verbs and ontologies from text using syntactic analysis and a conceptual clustering algorithm. It analyses texts with Sylex and creates basic clusters of words appearing with a same verb and a same syntactic role or preposition, as do SVETLAN'. These basic classes are then clustered to create an ontology by the mean of a cooperative learning algorithm. The main difference with SVETLAN' is this cooperative generalization part: ASIUM depends on the expert who has to valid, and possibly to split, the clusters made by the algorithm. This approach is justified for specialized technical texts, but ASIUM, applied on texts such as $)3 wires would certainly not be able to extract good basic classes. Furthermore, as each word does not occur a lot in these texts, the distance is not appropriate to the grouping of our classes. On the contrary, on technical texts and with the cooperation of an expert, ASIUM will certainly obtain better results than ours from the point of view of the domain coverage.

&21&/86,21

The system SVETLAN' we propose, in conjunction with SEGAPSITH and the syntactic parser Sylex, extracts classes of words from raw text. These classes are created by the gathering of nouns appearing with the same syntactic role after the same verb inside a context. This context is made by the aggregation of text about similar subjects. The first experiments carried out give good results. But they also confirm that a great volume of data is necessary in order to extract a large quantity of lexical knowledge by the analysis of syntactic distributions. Moreover the very low recall of the syntactic parser and its systematic errors on some constructions, for example the passive form, which is very common in the journalistic style of our corpus, reduce the number and size of the classes. To solve this problem, we envisage trying another analyzer or adding a post-processing step to Sylex that detects the passive form by using data already in its output. These adaptations and the study of more larger corpora will allow us to obtain a good coverage of numerous semantic domains. So, we will be able to give valuable semantic data useful in a lot of applications as information retrieval systems or word sense disambiguation systems.

  Three hierarchies of semantic domains 6758&785(' '20$,1 /($51,1*

*

  ******************* Phrase 193-466 *********************************** "L'état de santé critique du pilote autrichien Karl Wendlinger (Sauber-Mercedes), victime d'un grave accident jeudi matin lors des premiers essais du Grand Prix de Monaco de Formule Un, laisse planer une menace sur le déroulement de la course, dimanche en Principauté." ******************** Partie 1 193-466 hÃ# ************************

  1ThpvpÃGvx3`L'état de santé critique' (164) ->-cn head ->-`du pilote autrichien' (170) `planer' (204) ->-a2 head ->-`une menace' (205) ...<snip>.... `planer' (153) ->-a2 head ->-`une menace' (154) ...<snip>.... `planer' (161) ->-a2 head ->-`une menace' (162) ...<snip>.... `planer' (212) ->-a2 head ->-`une menace' (213) `sur le déroulement' (66) ->-cn head ->-`de la course' (235) AvtrÃ#Ã An extract of a sentence analysis by Sylex.

  Ãhr iwrp document, question, list Ãrhiyvu iwrp base, zone Ãhr iwrp document, question, list AvtrÃ&Ã Filtered aggregated links in a domain about nuclear weapons

  ** "L'état de santé critique du pilote autrichien Karl Wendlinger (Sauber-Mercedes), victime d'un grave accident jeudi matin lors des premiers essais du Grand Prix de Monaco de Formule Un, laisse planer une menace sur le déroulement de la course, dimanche en Principauté."

	1GrvpThpvpÃvshv3
	193-195 (164) "L'" "le" [gs.1,avn,pdet.1] pdet : singulier elision dmaj
	195-208 (165) "état de santé" "état de santé" [gs.1,nom.1] nom : masculin singulier
	mot_compose locsw
	...<snip>....

382-388 (203) "laisse" "laisse" [gs.12,nom.1] nom : feminin singulier 389-395 (204) "planer" "planer" [gs.13,verbe] verbe : infinitif ...<snip>.... 193-195 (16) "L'" "le" [gs.1,avn,pdet.1] pdet : singulier elision dmaj 195-208 (117) "état de santé" "état de santé" [gs.1,nom.1] nom : masculin singulier mot_compose locsw ...<snip>.... 382-388 (211) "laisse" "laisser" [gs.13,verbe] verbe : singulier autoontif antiontif anontif present indicatif subjonctif imperatif 389-395 (212) "planer" "planer" [gs.14,verbe] verbe : infinitif ...<snip>....

We call homogeneous a class that contains words that denote a same concept in the corresponding domain.


Gaël De Chalendar

Brigitte Grau
email: grau@limsi.fr

SVETLAN' or How to Classify Words Using their Context

Using semantic knowledge in NLP applications always improves their competence. Broad lexicons have been developed, but there are few resources which contain semantic information available for words and which are nondedicated to specialized domains. In order to build such a base, we designed a system, SVETLAN', able to learn categories of nouns from texts, whatever their domain. In order to avoid general classes mixing all the meanings of words, they are learned taking into account the contextual use of words.

Introduction

Improving the competence of NLP applications and Information Research systems requires to develop more and more in-depth analysis of documents in order to capture their meaning more precisely. In NLP, existing techniques correspond to two kinds of approaches, radically different. On one hand, surface analysis of texts is based on the distribution of words and their importance in a corpus. It exploits lexical knowledge on words and, possibly, general semantic information such as the semantic classes of a word and relations between words or concepts, as those found in WordNet [START_REF] Fellbaum | WordNet: an electronic lexical database[END_REF] or in thesauri. This kind of approach can be applied to large text bases, whatever their subjects. In return, it does not allow these systems to develop a detailed and precise analysis, due to the lack of a precise and structured knowledge base. Even when using WordNet, this problem remains. Words in WordNet are related to a Synset when they are synonymous, however Synsets correspond to large categories, and there exists some shifts of meaning between two synonyms so that when two words belonging to a same Synset are considered within a specific context, they often no longer share a common meaning.

On the other hand, in-depth understanding systems require highly structured semantic knowledge as well as pragmatic knowledge about situations referred in texts (the events, their causal links and characters). These systems aim at developing semantic analysis of sentences and building a representation of the meaning of texts. Their limitation comes from these required resources that are impossible to build except in very limited and well-known domains. The problem we address in this paper is then to improve the first systems, in order to go towards the second ones, but without losing the large coverage of the first ones. This is done by automatically acquiring a more structured knowledge base than the bases presently used. Our goal is to extract knowledge from texts, considering that they contain many examples of word uses. We do not want to model a specialized domain, a priori chosen. On the contrary, we want to process "general" language, as opposed to a specialized language, but it is well known that there is no "general language corpus". Each corpus is a subpart of the language that has its own specificity. Thus we use a corpus made of newspaper articles (French Agence France Presse (AFP) newswires and "Le Monde" articles). This corpus covers a wide range of different subjects and so, is close to what would be a "general language corpus", apart from the quite fixed journalistic style.

Automatic processes that extract knowledge from texts belong to statistical or syntactical approaches with a lot of variations between these two extremes. Purely statistical ones, such as [START_REF] Zernik | TRAIN1 vs. TRAIN2: Tagging Word Senses in Corpus[END_REF] often obtain groups of words that characterize a sense of a target word. Other approaches ( [START_REF] Basili | What can be learned from raw texts?[END_REF], [START_REF] Faure | ASIUM, Learning subcategorization frames and restrictions of selection[END_REF], [START_REF] Greffenstette | Explorations in automatic thesaurus discovery[END_REF], [START_REF] Habert | Elementary dependency trees for identifying corpus-specific semantic classes[END_REF], [START_REF] Rousselot | Extracting concepts and relations from corpora[END_REF]) are more syntactical and obtain classes of words with similar meanings1 : ARIOSTO [START_REF] Basili | What can be learned from raw texts?[END_REF] and STARTEX [START_REF] Rousselot | Extracting concepts and relations from corpora[END_REF] use manual semantic tagging and next classification, but while STARTEX uses not tagged repeated text segments, ARIOSTO uses syntactically parsed text. On the contrary ASIUM [START_REF] Faure | ASIUM, Learning subcategorization frames and restrictions of selection[END_REF] applies a cooperative clustering algorithm on classes obtained from syntactically parsed texts. ZELLIG [START_REF] Habert | Elementary dependency trees for identifying corpus-specific semantic classes[END_REF] constructs a graph of words linked by their common contexts in elementary noun phrases. By the study of the characteristics of this graph, it builds semantic categories. These three systems are designed to work on specialized languages belonging to a specific domain, whose vocabulary is well defined and generally not very ambiguous. When applied to non-specialized texts, they lead to build large classes, mixing all the meanings of words2 , as shown by Fabre et al. [START_REF] Fabre | La polysémie dans la langue générale et les discours spécialisés[END_REF] for ZELLIG.

As newspapers articles contain a lot of polysemous words, these approaches cannot be applied directly, because they are more or less based on the assumption that their target corpus is sufficiently specialized to be able to ignore the problem of polysemy. However, when considering these polysemous words in their contextual use, i.e. a segment of text about only one topic, their meaning is no more ambiguous. Thus, our system, SVETLAN', takes advantage of a precise context recognition ability in order to build homogeneous classes of words despite the generality of the corpus. It is based on a distributional approach: nouns playing the same syntactic role with a verb in sentences related to the same topic, i.e. the same domain, are aggregated in the same class. The contextual approach of SVETLAN' relies on knowledge about semantic domains of texts, automatically learned by SEGAPSITH [START_REF] Ferret | A Thematic Segmentation Procedure for Extracting Semantic Domains from Texts[END_REF]. This is way of focusing the construction of the classes by reference to controlled topics. It allows our system to deal naturally with more general texts while giving classes of words with similar meanings, in comparison with the other approaches which have to process specialized texts or that give more disjoined classes.

Overview of the System

Input data of SVETLAN' (see Fig. 1) are semantic domains with the Thematic Units (TUs) that have given birth to them. TUs are the result of a topic segmentation process relying on lexical cohesion that processes texts such as newspaper articles. Each TU contains the lemmatized content words of a text segment. The domains are automatically learned by aggregating similar thematic units. So, domains are sets of weighted words, relevant to represent a specific topic.

Domain TU TU TU TU TU Structured Domain V r N1, N2, … V r N1, N2, … V r N V r N Structured TU V r N V r N Structured TU Text Segment TU Text Segment

Input data

Fig. 1. Schema of structured domain learning

The first step of SVETLAN' consists of retrieving text segments of the original texts associated to the different TUs in order to parse their sentences. SVETLAN' extracts triplets from the parser results, that are constituted by a verb, the head noun of a phrase and its syntactic role. Thus, to each TU corresponds a text segment and a set of triplets we call a structured thematic unit. In order to build classes of nouns according to their contextual use, only the structured thematic units associated to a same semantic domain are aggregated altogether. Aggregation consists of grouping nouns playing the same syntactic role with a same verb. In such an approach, a verb associated to a type of phrase (subject, direct object, …) constitutes a criterion for building categories. However, one can find words belonging to different semantic categories associated to a same verb and a same type of phrase when the verb is polysemous, as for example to drive a car and to drive a railway; the same problem occurs with very general verbs, as to search for example, that do not entail alone a discrimination among their direct objects. Thus the application of a distributional method without any control coming from the context would lead the system to build heterogeneous categories. SVETLAN' solves this problem by aggregating verb complements within TUs belonging to a same domain. That ensures a better homogeneity of the data and leads SVETLAN' to form context sensitive classes. A last filtering step, based on the weights of the words in their domain, allows the system to eliminate nouns from classes when they are not very relevant in this context. This whole process leads to the formation of structured domains, i.e. semantic domains where each verb is related to categories of nouns that are semantically homogenous.

Semantic Domain Learning

We only give here a brief overview of the semantic domain learning module. This one is described more precisely in [START_REF] Ferret | A Thematic Segmentation Procedure for Extracting Semantic Domains from Texts[END_REF]. This module incrementally builds topic representations, made of weighted words, from discourse segments delimited by SEGCOHLEX [START_REF] Ferret | How to thematically segment texts by using lexical cohesion?[END_REF]. It works without any a priori classification or hand-coded pieces of knowledge. Processed texts are typically French newspaper articles coming from Le Monde or AFP. They are pre-processed to only keep their lemmatized content words (adjectives, single or compound nouns and verbs).

The topic segmentation implemented by SEGCOHLEX is based on a large collocation network, built from 24 months of Le Monde newspaper, where a link between two words aims at capturing semantic and pragmatic relations between them. The strength of such a link is evaluated by the mutual information between its two words. The segmentation process relies on these links for computing a cohesion value for each position of a text. It assumes that a discourse segment is a part of text whose words refer to the same topic, that is, words are strongly linked to each other in the collocation network and yield a high cohesion value. On the contrary, low cohesion values indicate topic shifts. After delimiting segments by an automatic analysis of the cohesion graph, only highly cohesive segments, named Thematic Units (TUs), are kept to learn topic representations. This segmentation method entails a text to be decomposed in small thematic units, whose size is equivalent to a paragraph. Discourse segments, even related to the same topic, often develop different points of view. To enrich the particular description given by a text, we add to TUs those words of the collocation network that are particularly linked to the words found in the corresponding segment.

Learning a complete description of a topic consists of merging all successive points of view, i.e. similar TUs, into a single memorized thematic unit, called a semantic domain, or simply a domain. Each aggregation of a new TU increases the system's knowledge about one topic by reinforcing recurrent words and adding new ones. Weights on words represent the importance of each word relative to the topic and are computed from the number of occurrences of these words in the TUs. This method leads SEGAPSITH to learn specific topic representations as opposed to [START_REF] Lin | Robust Automated Topic Identification[END_REF] for example whose method builds general topic descriptions as for economy, sport, etc.

Fig. 2. The most representative words of a domain about justice

We have applied the learning module of SEGAPSITH on one month (May 1994) of AFP newswires. Fig. 2 shows an example of a domain about justice that gathers 69 TUs. In all figures displaying examples extracted from our results obtained on French texts, we will put the original data plus their literal English translation.

Fig. 3. Three hierarchies of semantic domains

As some of these domains are close and refer to the same general topic, we have applied a hierarchical classification method based on their common words to organize them in separate general topics and to structure them. Fig. 3 shows the hierarchies built about sport, police and stock exchange. Each leaf is a domain, named by its two more weighted words, while their name and their size, i.e. the number of common words found in their children, describe internal nodes.

Structured Domains Learning

As in [START_REF] Faure | ASIUM, Learning subcategorization frames and restrictions of selection[END_REF], verbs allow us to categorize nouns. Those nouns that play a same role relative to a same verb define a class. In order to learn very homogeneous3 classes, we only apply this principle on words belonging to a same context, i.e. a domain.

Syntactic Analysis

In order to find the verbs and their arguments in the texts, we use the syntactic analyzer Sylex [START_REF] Constant | Analyse Syntaxique Par Couches[END_REF][START_REF] Constant | L'analyseur linguistique SYLEX. 5ème école d'été du CNET[END_REF]. <Syntactic Links> `L'état de santé critique' (164) ->-cn head ->-`du pilote autrichien' (170) `planer' (204) ->-a2 head ->-`une menace' (205) ...<snip>.... `planer' (153) ->-a2 head ->-`une menace' (154) ...<snip>.... `planer' (161) ->-a2 head ->-`une menace' (162) ...<snip>.... `planer' (212) ->-a2 head ->-`une menace' (213) `sur le déroulement' (66) ->-cn head ->-`de la course' (235) Fig. 4. An extract of an analysis of a sentence by Sylex (in French only). Fig. 4 shows a little part of the results of Sylex for a sentence. The first part exhibits lexico-syntactic information for the words and this for four different interpretations (indicated by the code "taux 4" = rate 4) due to the fact that Sylex cannot chose between two interpretations for two words: "laisse" between the verb "laisser" (to let) and the noun "laisse" (leash) and "critique" between the verb "critiquer" (to criticize) and the adjective "critique" (critical). The second part shows the syntactic links found by Sylex. Between parenthesis are references to the words in the preceding analysis. Here Sylex has found four times the same interpretation. In this case, we count one occurrence of the link. But if it finds several times the same relation between a verb and different words, for example several possible subjects, then we keep all the different interpretations. That is because we have no way to choose between them. We make the reasonable expectation that the false interpretations will have much less occurrences in the corpus and so, will be filtered out during the rest of the processing.

The results of Sylex are very detailed and not easy to parse directly with, say, Perl. Furthermore, we do not need all the information it extracts. In fact, we only need to find the verb with its links and the head nouns arguments of these links. So, we have developed a formal grammar that extracts from these raw analyzes the associations between a verb and its arguments. This grammar extracts links from the results of Sylex in the following format: i # j verb # token1 # lemma1 # k rel # token2 # lemma2 # l where i and j are the boundaries of the sentence that contains the link in the corpus; token1 and lemma1 are the token and the lemma of the verb respectively; rel is the syntactic relation which can be "subject", "direct object" or a preposition ("to", "from", etc.) ; token2 and lemma2 are the token and the lemma of the head noun of the noun phrase pointed by the relation; lastly, k and l are the indexes in the corpus of token1 and token2 respectively. Fig. 5 shows some links that we have extracted.

Fig. 5. Examples of extracted links

Sylex, as other syntactic analyzers, has problems with some constructions and consequently introduces errors that can cause problems to the remaining of the system. Some common errors are the bad interpretation of the passive form that causes a subject to be analyzed as a direct object and conversely, a direct object to be viewed as a subject. Another common error is that it often happens that Sylex does not find any link in a phrase. That is what we call silence. We will see in Sect. 5 that we can obtain good results despite these problems thanks to the redundancy needed to validate the links in the next steps of processing. But a consequence of this redundancy need is that the system must use great quantities of texts in order to create classes with a satisfactory size.

Having obtained the syntactic links that were in the texts, we want to group them relatively to the belonging of their text segment to a Thematic Unit. So, we define a structured thematic unit as a set of <Verb syntactic relation Noun> structures, syntactic relations instantiated with a verb and a noun. We will refer to these structures as instantiated syntactic relations. We are able to put in relation the links extracted from the results of Sylex and the words contained in the domains because each domain in the thematic memory remembers which thematic units have been used to create it. In the same way, each thematic unit remembers the part of text it comes from.

Aggregation

In order to construct groups of words with very similar meanings, we want to group the nouns appearing with the same syntactic role in relation to a verb inside a domain. Then, a structured domain is a set of <Verb syntactic relation Noun 1 ,…, Noun n > structures, i.e. a set of aggregated instantiated syntactic relation.

Structured thematic units related to a same domain are aggregated altogether to form the structured domains. Aggregating a structured thematic unit within a structured domain consists of:

• aggregating their instantiated syntactic relations that contain a same verb ;

• adding new instantiated syntactic relations, i.e. adding new verbs with their arguments made of a syntactic relation and the lemmatized form of a noun.

Structured Domain source object cup [START_REF] Constant | Analyse Syntaxique Par Couches[END_REF], match [START_REF] Basili | What can be learned from raw texts?[END_REF] to play [START_REF] Constant | L'analyseur linguistique SYLEX. 5ème école d'été du CNET[END_REF] with ball [1] subject player [1] win [START_REF] Basili | Contexts and Categories: Tuning a General Purpose Verb Classification to Sublanguages[END_REF] object match [START_REF] Basili | What can be learned from raw texts?[END_REF] 2 Instantiated Syntactic Relations sources subject champion to play object match to lose object championship

Structured Domain result object cup [START_REF] Constant | Analyse Syntaxique Par Couches[END_REF], match [START_REF] Basili | Contexts and Categories: Tuning a General Purpose Verb Classification to Sublanguages[END_REF] with ball [START_REF] Basili | What can be learned from raw texts?[END_REF] to play [START_REF] Fabre | La polysémie dans la langue générale et les discours spécialisés[END_REF] subject champion [1] subject player [START_REF] Basili | What can be learned from raw texts?[END_REF] to win [START_REF] Basili | Contexts and Categories: Tuning a General Purpose Verb Classification to Sublanguages[END_REF] object match [START_REF] Basili | What can be learned from raw texts?[END_REF] to lose [START_REF] Basili | What can be learned from raw texts?[END_REF] object championship [START_REF] Basili | What can be learned from raw texts?[END_REF] Fig. 6. An example of the aggregation of an instantiated syntactic relation in a structured domain Fig. 6 shows the aggregation of a structured domain and two instantiated syntactic relations. This example shows all the possible effects of the aggregation. In the figure, bold elements represent new or updated data. Aggregating an instantiated syntactic relation in a structured domain that already contains the verb of the instantiated syntactic relation leads to increment the occurrence number of the verb, as for play in the example which occurred 4 times before the aggregation. Similarly, the occurrence number of common nouns related to the verb by the same relation are updated (match goes from 1 to 2), and new relations with their associated nouns are added to the verb. In the example, the subject champion with an occurrence of 1 is added. An instantiated syntactic relation with a new verb is simply added with an occurrence of 1, as for <to lose object championship>.

Classes of nouns in the produced structured domains contain a lot of words that disturb their homogeneity. These words often belong to parts of the various TUs at the origin of the structured domain that are not very related to the described topic. They correspond to a meaning of a verb scarcely used in the context defined by the domain. Another possibility is that the instantiated syntactic relation results from an error of Sylex. As these words are weekly weighted in the corresponding domains, the data can be filtered: each noun that possesses a weight lower than a threshold is removed from the class. By this selection, we reinforce learning classes of words according to their contextual use. At this time the threshold is empirically chosen. In the future, we plan to automatically find the threshold. It would be fixed in order to maximize the score of a validation task we outline in Sect. 7. Fig. 7 shows two aggregated links obtained without filtering in its upper part and the filtered counterparts in its lower part. The link for the verb 'to establish' has been completely removed while the link of the verb 'to answer' with the preposition 'to' has been reduced by the removing of 'list'. We can see on this example that this filtering is efficient: the verb 'to establish' is not very related to the domain of 'nuclear weapons' from which this example is taken and the usage of 'to answer to a list' has a very low probability. More details on the effects of the filtering will be given in the Results section. In the principle, the described operations are not very complicated. The difficulties come from the necessity to work with data coming from various tools. Furthermore, for performance and practical reasons, we do not apply the chain of tools text by text. The natural way to see the process would be to:

• read a text, • extract the TUs from it, • extract the corresponding structured thematic units, • add each TU to its domain, • add each structured thematic unit to its corresponding structured domain.

In fact, each computing step is done on the entire corpus and the results are next aligned. This allows us to save computation time because we do not have to run each one multiple times. But in return we have to deal with dictionaries and indexes for various files and tools.

Results

The experiments we realized aim at showing that SVETLAN' lead to learn classes of words which have similar meanings in the domain. To obtain such results we have chosen to run our system on one month of the French version of AFP wires, that forms a corpus stylistically coherent but that covers varied subjects with very polysemous and non specific verbs.

The judgements about the quality of the classes obtained are now manual and made by ourselves. We will obviously need a better and more systematic validation approach in the future. We will sketch in Sect. 7 some possibilities we consider.

The one month of AFP wires is made of 4,500,000 words and 48,000 sentences in 6,000 texts. The thematic analysis gives 8,000 TUs aggregated in 2,000 domains. More details on these domains can be found in [START_REF] Ferret | A Thematic Segmentation Procedure for Extracting Semantic Domains from Texts[END_REF]. From these 48,000 sentences, Sylex extracts 117,000 different instantiated syntactic relations. 24,000 of these links concern subject, direct object, or circumstantial complements introduced by a preposition and are integrated in 1,531 structured domains.

After aggregating, but before filtering, the system obtains 431 aggregated links with two or more arguments, equivalent to 431 word classes. Some of them, such as <to manufacture direct object bomb, weapon> are good. Nevertheless other classes are heterogeneous as <to return direct object territory, strip, context, synagogue> (here strip comes from the Gaza Strip), or clearly mix different meanings of a verb, like <to quit direct object base, government> which mixes together the meanings "to leave a place" and "to retire from an institution". For the two latter cases, one can see the interest to take into account the fact that the domains contain words with different weights representing their relevance to this domain. The higher the weight, the higher the relevance of this word in this domain. So we apply the aforesaid filter to our classes and retain only those with weights higher than a threshold. The class <territory, strip, context, synagogue> is corrected to <territory, strip> and < base, government> is removed.

Among the wrong classes, some are due to errors of Sylex, as <to confer direct object price, actor> where actor should be linked to to confer by the preposition to. The remaining errors are due to the extensive use of two different meanings of the verb in the same domain, as for: <to conduct/to manage direct object delegation, negotiation> (in French: "conduire une négociation/une délégation"). This kind of error is inherent to the method we use and should be removed by other means. Note again that the correctness of the links have been manually judged by ourselves.

We have tried two thresholds: 0.05 and 0.1. Fig. 8 details the results for both.

Fig. 8. Results of the filtering for two thresholds

After filtering, a lot of classes are removed but the remaining classes are well founded in most cases. An example of a retained class for both thresholds is: <to injure subject colonist, soldier> With a threshold set to 0.1 rather than to 0.05, we retain only 38 links, but we gain 8% in precision. If we ignore the errors due to Sylex, the real precision of SVETLAN' is in the first case 78% and in the second case 87%. It shows the interest there is to choose a good threshold.

Our experiments lead to homogeneous classes containing words having similar meanings, though these classes contain few words. In order to show the efficiency of building classes of words inside a domain, it is interesting to see what kind of classes would be obtained by the merging of all domains, that is to say: creating context-free classes. So, we have applied the same aggregation principle to the same corpus but without taking into account the domains. Just below, we show two classes for the verb "to replace". The top one is made context-free and the bottom one is made inside a domain. This verb is very general, virtually everything can be replaced. Obtaining meaningful classes with a corpus such as "AFP" shows the efficiency of our method. Moreover, we obtain cohesive classes for verbs very general and polysemous.

Words are often polysemous or ambiguous. However, when used in context, they denote one meaning, and moreover this meaning is generally the same in different occurrences of a same context. When building classes according to their context, we avoid mixing all the meanings of a word in a same class. Such a result can be exhibited in the classes (law, constitution) and (law, article, disposition) in the juridical context, for the words "articles", "constitution" and "disposition".

Related Works

There is a lot of works dedicated to the formation of classes of words. These classes have very various statuses. They can contain words belonging to the same semantic field or near synonymous. We give here some details about three approaches we cited in the introduction that are good examples of different approaches: manual, statistical and syntactical.

WordNet [START_REF] Fellbaum | WordNet: an electronic lexical database[END_REF] is a lexical database made by lexicographers. It aims at representing the sense of the bigger part of the lexicon. It is composed of Synsets. A Synset is a set of words that are synonymous. These Synsets are linked by IS A relations. Its coverage is large but this quality is, in a sense, its shortcoming. Indeed, the generality of its contents makes it difficult to use in real sized applications that are often centered on a domain. It rarely can be used without a lot of manual adaptation, even if some authors tried to relate automatically acquired lexical knowledge with it, for example [START_REF] Basili | Contexts and Categories: Tuning a General Purpose Verb Classification to Sublanguages[END_REF].

IMToolset, by Uri Zernik [START_REF] Zernik | TRAIN1 vs. TRAIN2: Tagging Word Senses in Corpus[END_REF], extracts, for a word, several clusters of words from text. Each of these clusters reflects a different meaning of the studied word. This extraction is done by scanning the local contexts of the word, the 10 words surrounding it in the texts. These signatures are statistically analyzed and clustered. The result is groups of words that are similar to our domains but more focused on the sense of a word alone.

We have already stressed out some characteristics of ASIUM by D. Faure and C. Nedellec, but we give here some more details. ASIUM learns subcategorization frames of verbs and ontologies from text using syntactic analysis and a conceptual clustering algorithm. It analyses texts with Sylex and creates basic clusters of words appearing with a same verb and a same syntactic role or preposition, as do SVETLAN'. These basic classes are then clustered to create an ontology by the mean of a cooperative learning algorithm. The main difference with SVETLAN' is this cooperative part: ASIUM critically depends on the expert that has to valid, and possibly split, the clusters made by the algorithm. As a consequence, it has to work on specific technical texts. As a consequence, ASIUM, applied on texts such as our AFP wires would certainly not have been able to extract good classes. Indeed, there is a lot of very polysemous words in these texts that take a precise meaning only in a sufficiently focused context, such as our domains. Furthermore, as each word does not occur a lot, the distance measure currently used in ASIUM would not allow grouping any cluster.

Future Directions of Work

We envisage two major directions of work that are closely related: the extension of our results and a real validation of them.

At this time, the classes do not contain a lot of words. A way to enlarge them, and the more obvious one, is to process more texts in order to have more data. That will necessitate some modifications of the algorithm of domain building. At this time, we store all the thematic units and all the words in domains, even if they are never aggregated and so have always an occurrence number of one. Thus, the memory usage is too important. We will set up a kind of "garbage collection" process to remove or maybe recycle old and not very aggregated domains. This will allow us to process much more texts and so enlarge classes in two directions: their sizes and the number of occurrences of words inside them.

Another way could be to regroup classes that are related to the same verb, by the same syntactic relation in two domains belonging to the same hierarchy, i.e. a same more general context, assuming the words always have the same meaning. However this method has to be tested on more results in order to prove its reliability. With our results, we would build for example (law, constitution, article, disposition) in the domain of "Law" and (rebel, force, northerner, leader) in the domain of "conflict". This way of enlarging the classes should be studied carefully in a theoretical point of view. Indeed, the originality of our work is the focused context entailed by the use of the domains. That allows us to deal with texts from general language. When we consider domains in the same hierarchy, we enlarge the context and so, we take the risk to have the same problems as other works, discussed in the introduction and Sect. 6, when they are applied to general language: the merging in a same class of different meanings of some words.

Another possibility to enlarge our classes is to generalize them as in ASIUM. ASIUM merges classes independently of the related verbs according to a similarity measure, even if, in our case, this generalization process would operate in a same general domain. Afterwards, as in ASIUM, we would ask an expert to validate its results. The problem would be, again, to find an expert of "general language".

Concerning the validation task, it could be realized by relating our classes to existing classifications, as do [START_REF] Basili | Contexts and Categories: Tuning a General Purpose Verb Classification to Sublanguages[END_REF] with WordNet. Another possibility would be to evaluate the improvement SVETLAN' permits when performing a task. Our group participates to the "Question Answering" track in the TREC evaluations and uses a search engine to find documents able to contain the answers. The questions of the QA track are about various topics from a newspaper corpus. So, we believe that the classes obtained by SVETLAN' could be very useful to extend precisely the requests to the search engine.

Conclusion

The system SVETLAN' we propose, in conjunction with SEGAPSITH and the syntactic parser Sylex, extracts classes of words from raw text. Instead of just having sets of weighted words for describing semantic domains, domains are described by a set of verbs related to classes of words by a syntactic link. These classes are created by the gathering of nouns appearing with the same syntactic role after the same verb inside a context. This context is made by the aggregation of text about similar subjects. Besides, we can also view this base as semantic classes, each one being related to its context of interpretation. The first experiments carried out give satisfying results. But they also confirm that a great volume of data is necessary in order to extract a large quantity of lexical knowledge by the analysis of syntactic distributions. Moreover the very low recall of the syntactic parser and its systematic errors on some constructions, for example the passive form, which is very common in the journalistic style of our corpus, reduce the number and size of the classes. To solve this problem, we envisage trying another analyzer or adding a post-processing step to Sylex that detects the passive form by using data already in its output. These adaptations and the study of larger corpora will allow us to obtain a good coverage of numerous semantic domains. So, we will be able to give valuable semantic data useful in a lot of applications as information retrieval systems or word sense disambiguation systems.

  ******************** Phrase 193-466 *********************************** "L'état de santé critique du pilote autrichien Karl Wendlinger (Sauber-Mercedes), victime d'un grave accident jeudi matin lors des premiers essais du Grand Prix de Monaco de Formule Un, laisse planer une menace sur le déroulement de la course, dimanche en Principauté." ******************** Partie 1 193-466 taux 4 ************************

Fig. 7 .

 7 Fig. 7. Two filtered aggregated links in a domain about nuclear weapons

  ** "L'état de santé critique du pilote autrichien Karl Wendlinger (Sauber-Mercedes), victime d'un grave accident jeudi matin lors des premiers essais du Grand Prix de Monaco de Formule Un, laisse planer une menace sur le déroulement de la course, dimanche en Principauté." <Lexico-Syntactic information> 193-195 (164) "L'" "le" [gs.1,avn,pdet.1] pdet : singulier elision dmaj 195-208 (165) "état de santé" "état de santé" [gs.1,nom.1] nom : masculin singulier mot_compose locsw ...<snip>....

382-388 (203) "laisse" "laisse" [gs.12,nom.1] nom : feminin singulier 389-395 (204) "planer" "planer" [gs.

13,verbe]

verbe : infinitif ...<snip>.... 193-195 (16) "L'" "le" [gs.1,avn,pdet.1] pdet : singulier elision dmaj 195-208 (117) "état de santé" "état de santé" [gs.1,nom.1] nom : masculin singulier mot_compose locsw ...<snip>.... 382-388 (211) "laisse" "laisser" [gs.13,verbe] verbe : singulier autoontif antiontif anontif present indicatif subjonctif imperatif 389-395 (212) "planer" "planer" [gs.14,verbe] verbe : infinitif ...<snip>....

  The first group of words merges very different senses while the second class, much more little, is better because it contains words referring to very similar concepts: a bar of uranium is nuclear combustible. Another example is the following, for the verb "to attribute":

	remplacer COD texte, constitution, pantalon, combustible, loi, dinar, barre,
		film, circulation, juge, saison, appareil, parlement, bataillon,
		police, président, traité
	remplacer COD combustible, barre
	to replace object text, constitution, trousers, combustible, law, dinar, bar, film,
		circulation, judge, season, device, parliament, battalion,
		police, president, treaty
	to replace object combustible, bar
	attribuer	COD parole, prix, décoration, pape, responsabilité, télévision,
		attentat, lettre, contrat, ministre, jury, fond, autorité, note,
		bonus, bande, bombardement
	attribuer	COD prix, décoration
	to attribute object talk, prize, decoration, pope, responsibility, television,
		attempt, letter, contract, ministry, jury, funds, authority, note,
		bonus, band, bombing
	to attribute object prize, decoration

In the rest of this paper, we use the term 'words with similar meanings' to identify words that refer to concepts with an immediate, or quasi-immediate, ancestor in a conceptual ontology.

Pereira et al. [13] use also syntactically parsed texts and a statistical clustering algorithm but applied to more general texts: Associated Press newswires. Classes obtained do not seem to constitute synonym sets as those of the preceding systems, but they have been used successively on a disambiguation task.

We call homogeneous a class that contains words that have similar meanings, as defined above, in the corresponding domain.


Marius Greger

Daniel Palm
email: daniel.palm@reutlingen-university.de

Louis Louw

Konrad Von Leipzig

Classification of optical technologies for the mapping of production environments

Keywords: Optical Indoor Localization Systems, Cameras, Marker-based Tracking, changeable and reconfigurable manufacturing

Indoor localization systems are becoming more and more important with the digitalization of the industrial sector. Sensor data such as the current position of machines, transport vehicles, goods or tools represent an essential component of cyber-physical production systems (CCPS). However, due to the high costs of these sensors, they are not widespread and are used mainly in special scenarios. However, especially optical indoor positioning systems (OIPS) based on cameras have certain advantages due to their technological specifications. In this paper, the application scenarios and requirements as well as their characteristics are presented and a classification approach of OIPS is introduced.

Introduction

In order to meet the requirements of Industry 4.0, a high degree of adaptability of production systems is required [1]. In this context, there is a focus on the so-called smart factory, in which people, machines, objects and products are intelligently linked with each other through the provision of hardware and software. This enables increasing automation and autonomous reaction to unpredictable events. [2] For this purpose, embedded systems are integrated into objects, devices, buildings, forklifts as well as into production facilities and logistics components, whereby these become cyber-physical systems (CPS). These systems, also known as intelligent objects, can then autonomously and decentrally communicate with each other and optimize themselves. The result is a virtual image of reality, which is continuously updated with the help of real-time data. [3] Westkämper [START_REF] Westkämper | Zukunftsperspektiven der digitalen Produktion[END_REF][START_REF] Westkämper | Integration in der digitalen Produktion[END_REF] considers the ability to unambiguously identify and localize objects and the individuality of systems, processes, objects and products as well as the controllability of the increasing complexity to be particularly important. Indoor positioning systems (IPS) are architectures of tags, location sensors, a locating engine and a locating application that can be used to determine the position of a person or an object in buildings [START_REF] Hohenstein | Systementwurf und Umsetzung einer funktionsintegrierenden Gabelstaplerlokalisierung für eine wandlungsfähige und effiziente Transportausführung[END_REF]. Tags are used as spatial reference points or for unambiguous identification and the location sensor provides ID and position values. The location engine uses this data to derive the actual position of the specific location object. The location application is the software solution for further processing the position data [START_REF] Malik | RTLS for dummies[END_REF].

Positioning can be relative or absolute. The relative positioning determines the position of the location object relative to a reference point. In absolute position determination, the position is specified in a global coordinate system [START_REF] Youssef | Indoor Localization[END_REF]. A variety of systems and technologies using different algorithms, techniques and technologies are available for the unambiguous identification and localization of objects, which differ in their degree of maturity and their performance [START_REF] Sakpere | A State-of-the-Art Survey of Indoor Positioning and Navigation Systems and Technologies[END_REF][START_REF] Lymberopoulos | A realistic evaluation and comparison of indoor location technologies[END_REF][START_REF] Brena | Evolution of Indoor Positioning Technologies: A Survey[END_REF]. Due to the high cost of these systems, they are actually only applied in a limited amount of scenarios, such as the navigation of autonomous transport vehicles [START_REF] Bubeck | Vom fahrerlosen Transportsystem zur intelligenten mobilen[END_REF]. In particular, optical indoor positioning systems (OIPS), which use cameras or other optical sensors to determine the position of localization objects in their field of view, [START_REF] Klopschitz | Visual tracking for Augmented Reality[END_REF][START_REF] Mautz | Survey of optical indoor positioning systems[END_REF], have proven to be precise and robust in industrial applications [START_REF] Essati | Staplerortung und -navigation[END_REF][START_REF]TotalTrax: Vehicle Tracking and Fleet Management[END_REF][START_REF] Logivations | Kamerabasierte Objekterkennung[END_REF]. Compared to radio-based approaches, which have also gained popularity, they are not influenced by reflections on metal, multipath propagation, interferences, scattering or absorption by liquids [START_REF] Mautz | Indoor positioning technologies[END_REF]. They are highly scalable and can work with tags that can be printed by the user inexpensively, or even without any tags. Therefore, they seem to be especially promising for the application within small and medium sized enterprises (SME).

Characteristics and Requirements of Indoor Location Systems

The wide field of application of indoor localization systems leads to a multitude of requirements. An overview of requirements mentioned in literature is given in Table 1.

The authors have been assigned to the requirements mentioned in their works. In the following section, a short description of the requirements is provided.

 Continuity refers to the ability of a system to repeat a certain function in time and space. An IPS is continuous if position determination is not limited to a few predefined measurements [START_REF] Hohenstein | Systementwurf und Umsetzung einer funktionsintegrierenden Gabelstaplerlokalisierung für eine wandlungsfähige und effiziente Transportausführung[END_REF].  Output data refers to the location data provided by an IPS, e.g. 2D or 3D coordinates, orientation, ID, etc.  Required infrastructure refers to the infrastructure needed for position determination that goes beyond the location sensor and the location engine. Mautz [START_REF] Mautz | Indoor positioning technologies[END_REF] distinguishes between OIPS with or without markers.  Accuracy refers to a numerical measure in a given metric unit and results from the deviation between nominal and actual position.  Coverage refers to the maximum range between an IPS and a location object, in which the object can still be identified and its position be determined.  Repeat accuracy or precision, describes the repeatability of a measurement result, given that the measurement is carried out under the same conditions.  Update rate refers to the frequency at which the position data can be determined by a system. An important aspect of the update rate is the latency, which is the time required by a system to determine the actual position of a localization object.  Scalability refers to the achievable number of localizable objects and structures.  Availability refers to the amount of time a system is available for use with the required accuracy and integrity.  Robustness refers to the resistance towards unwanted influences of a system, e.g. changes in temperature, reflections, occlusion, etc.  Architecture refers to the fact that systems can be realized in a way that the localization system is attached to the localization object, the position data are thus recorded directly at the object to be located (inside-out). In contrast to this approach in an outside-in approach, the localization system is attached to the infrastructure. Moreover, the number of localization objects, the required computing power and power supply are important aspects, as they influence the costs and the components of a system. Based on a literature review (see e.g. [START_REF]TotalTrax: Vehicle Tracking and Fleet Management[END_REF][START_REF] Mautz | Indoor positioning technologies[END_REF][START_REF] Zhang | Localization and navigation using QR code for mobile robot in indoor environment[END_REF][START_REF] Tilch | CLIPS -a camera and laser-based indoor positioning system[END_REF][START_REF] Hohenstein | Systementwurf und Umsetzung einer funktionsintegrierenden Gabelstaplerlokalisierung für eine wandlungsfähige und effiziente Transportausführung[END_REF]), the characteristics of the requirements were determined. The results are shown in Figure 1.

Application scenarios of OIPS

After the introduction of the requirements for OIPS in section 2, this section presents various application scenarios explored in the literature and clustered according to their main application area. A short description of the application scenario is given (see Table 2 and Table 3). The list of scenarios represents the use cases mentioned in literature.

The objective of the collection was not so much absolute completeness, but rather a representative selection, which makes it possible to assign the application scenarios to basic system configurations in the following section. Intelligent tool control Through the localization of tools and the intelligent analysis of this data, it is possible to determine and optimize the utilization. [START_REF] Schmidt | GeoCEP -RTLS und GIS unterstütztes Event Processing[END_REF][START_REF] Bespoon | Use Case Fabrik: Bringen Sie Intralogistik auf die nächste Stufe[END_REF] Inventory management Stocks are often unnecessarily increased because the storage location or filling level of containers cannot be determined. [START_REF]Management logistischer Informationsflüsse[END_REF] Navigation and localization of mobile robots

Equipped with an RTLS, mobile robots can find their way around in industrial environments. The determination of their absolute position at any time is crucial for optimal navigation. [START_REF] Siemens | Real-Time Locating Systems (RTLS) in der Produktion: Für ein digitales Unternehmen in Bewegung[END_REF] Optimization of routes Optimization of in-house transport routes to avoid empty runs and traffic jams.

Quality management

Reduction of picking errors, packed goods are counted and compared with the packing list. [START_REF] Logivations | Kamerabasierte Objekterkennung[END_REF][START_REF]Management logistischer Informationsflüsse[END_REF] Route inspection Before a transport process is started, the system checks whether the route is blocked or not.

Tracking of intralogistics transport vehicles

Current position determination of transport vehicles (e.g. forklifts, tugger trains) and their status. Optimization of availability, assignment, routes and transparency. [START_REF]Management logistischer Informationsflüsse[END_REF] Tracking of material flows, load carriers or workpieces Material movements can be recorded with Real-Time Locating Systems (RTLS) and passed on to higher-level system for analysis purposes and process optimisation. [START_REF] Hohenstein | Systementwurf und Umsetzung einer funktionsintegrierenden Gabelstaplerlokalisierung für eine wandlungsfähige und effiziente Transportausführung[END_REF][START_REF]Management logistischer Informationsflüsse[END_REF][START_REF] Pelka | [END_REF] Table 3. Application scenarios of optical indoor positioning systems (OIPS) in Production and Production-related Areas

Area Application scenario Description

Production Automation in production lines

The position data of work pieces or containers are used to improve automation in transportation and feeding processes avoiding delays in the production process. [START_REF] Schmidt | GeoCEP -RTLS und GIS unterstütztes Event Processing[END_REF] Digital twin of factory, layout of the production system Creation of the digital twin of the production system. The constant position determination of machines and vehicles enables the digital representation of the physical production system and the proactive reconfiguration of production systems. This information plays a decisive role especially in the case of increasing automation or even the introduction of autonomous system components. [START_REF] Schmidt | GeoCEP -RTLS und GIS unterstütztes Event Processing[END_REF] Intelligent tool control Depending on the position of a tool (e.g. a screwdriver) relative to a work piece to be machined, its control is automatically enabled. For instance the torque is adjusted depending on the tool position. [START_REF]Management logistischer Informationsflüsse[END_REF] Operational optimization The position determination of every single batch, tool and employee enables extensive process optimization by means of analysis. [START_REF] Bespoon | Use Case Fabrik: Bringen Sie Intralogistik auf die nächste Stufe[END_REF] Quality management Observation and reduction of assembly errors, [START_REF]Management logistischer Informationsflüsse[END_REF] Security Access control Monitoring of safety areas, increasing workplace safety. [START_REF]Management logistischer Informationsflüsse[END_REF][START_REF] Schmidt | GeoCEP -RTLS und GIS unterstütztes Event Processing[END_REF] Anti-theft protection Continuous presence check, inspection of a known object. [START_REF] Mautz | Indoor positioning technologies[END_REF] Evacuation management In emergencies (e.g. fire, release of dangerous substances, danger of terrorism, etc.) companies must be able to determine whether employees are still in the building and ideally in which areas. [START_REF] Lachmann | Indoor / Outdoor Lokalisierung -Anwendungsbeispiele[END_REF] 4

Classification of OIPS

The biggest challenge for (potential) users is the fundamental definition of the architecture and identification method of the overall system. While the technological capabilities of individual components can easily be adapted on the basis of the specific requirements of the scenarios, the decision whether the camera system is located on the object to be localized or not and if a marker-based system or a non-marker based like a feature-based-tracking system should be used. Therefore, four classes were formed based on their characteristics (see Table 4) and the application scenarios are evaluated to determine, which of these classes could be used to implement the respective scenario (see Table 5). The results show that the outside-in architecture where the localization system is attached to the infrastructure (Class 1 and 2) covers a significantly wider range of scenarios than the inside-out architecture. In practice, this gives an initial indication of a technology to be introduced if the concrete application is still unspecified. All scenarios except the self-navigation of mobile robots can be solved with the outside-in architecture. For a detailed specification, further aspects of Figure 1 have to be considered.

Table 5. Classification of optical indoor positioning system (OIPS)-scenarios

The minimum specification of an OIPS that can meet the requirements of all the scenarios listed in Class 1 must have an accuracy of better than 5 cm, a coverage of at least 10 meter, a frame rate of more than 15 frames per second (fps) to track moving objects, a periodic update rate, a latency of under 1 second, a high scalability, the ability to identify more than 50 objects, and use an active power supply. This gives users an indication how to set up an OIPS with a maximum of flexibility in relation to the scenarios. Individual application requirements of each scenario are shown in Figure 2.

Summary and Conclusion

In this paper, the literature in regard to IPS and OIPS was analyzed and application scenarios as well as their requirements and characteristics were derived. The classification framework can be used by practitioners to determine the technical requirements to realize a specific application scenario. It was shown that OIPS is a relevant technology that can cover a wide range of scenarios and that an outside-in architecture with localization system attached to the infrastructure (mounted set of cameras and marker-or non-marker-based identification and localization of the objects) covers a significant higher range of scenarios in the production environment that the inside-out architecture.

Here it could be proven that this architecture has the broader application possibilities.

The high proportion of low-cost computing power and image sensor chips on the market make cost-effective positioning solutions that can meet the requirements more attractive for a wider range of scenarios. This in combination with the possibility to paper-print a marker for identification purposes for literally no costs, opens up a costefficient realization of high number of scenarios presented and characterized.

  [START_REF] Hohenstein | Systementwurf und Umsetzung einer funktionsintegrierenden Gabelstaplerlokalisierung für eine wandlungsfähige und effiziente Transportausführung[END_REF]

Fig. 1 .

 1 Fig. 1. Requirements towards indoor positioning systems (IPS) and their characteristics

Fig. 2 .1

 2 Fig. 2. Optical indoor positioning system (OIPS)-application scenarios and their characteristics

Table 1 .

 1 Identified requirements towards indoor positioning systems (IPS)

	Author	Günthner	Hohenstein	Mautz	Liu et.al.	Han [21]	Malik [7]
		et.al.[19]	[6]	[18]	[20]
			Localization function
	Continuity		x	x			x
	Output data		x	x			x
	Required infrastructure		x	x			x
			Localization performance
	Accuracy	x	x	x	x	x
	Coverage	x	x		x	x
	Repeat accuracy	x		x
	Update rate	x	x		x	x
			Overall system
	Scalability	x	x	x	x	x	x
	Availability			x
	Robustness	x	x	x	x		x

Table 2 .

 2 Application scenarios of optical indoor positioning systems (OIPS) in Logistics

	Area Application scenario	Description
	Automatic goods recog-	Delivered goods can be automatically identified and posted directly
	nition at arrival	at the arrival. [17]
	Component search	Comprehensive localization of components and intermediate prod-
		ucts. [27]
	Logistics

Table 4 .

 4 OIPS-classes based on architecture and infrastructure

	Class	Architecture	Required infrastructure
	OIPS Class 1	outside-in	markers
	OIPS Class 2	outside-in	none
	OIPS Class 3	inside-out	markers
	OIPS Class 4	inside-out	none


HAND-CRAFTED APPROACHES FOR POINT CLOUD PROCESSING 𝜌

𝑟 𝑠 = 𝑟 0 × 𝜑 𝑠 𝑠 𝐶 𝑠 𝑟 𝑠 𝜌 ⁄ 𝜆 1 > 𝜆 2 > 𝜆 3 ∈ ℝ 𝐞 1 , 𝐞 2 , 𝐞 3 ∈ ℝ 3 cov(𝒩) = 1 |𝒩| ∑ (𝐩 -𝐩 ̅)(𝐩 -𝐩 ̅) 𝑇 𝐩∈𝒩 ∑ 𝜆 𝑖 (∏ 𝜆 𝑖 ) 1 3 ⁄ -∑ 𝜆 𝑖 ln(𝜆 𝑖 ) (𝜆 1 -𝜆 2 ) 𝜆 1 ⁄ (𝜆 2 -𝜆 3 ) 𝜆 1 ⁄ 𝜆 3 𝜆 1 ⁄ 𝜆 3 (𝜆 1 + 𝜆 2 + 𝜆 3 ) ⁄ × 2 | 𝜋 2 -angle(𝐞 𝑖 -𝐞 𝑧 )| 𝑖∈[0,2] × 6 1 |𝒩| |∑⟨𝐩 -𝐩 𝟎 |𝐞 𝑖 ⟩ 𝑘 | 𝑖∈[0,1,2] 𝑘∈[1,2] × 2 1 |𝒩| ∑⟨𝐩 -𝐩 𝟎 |𝐞 𝑖 ⟩ 𝑘 𝑘∈[1,2] |𝒩| 𝐩 ̅ 𝒩 (𝜆 1 -𝜆 3 ) 𝜆 1 ⁄ |𝜋/2 -angle(𝐞 𝑖 -𝐞 𝑧 )| 𝐞 𝑧 𝑆 = 8 𝑟 0 = 0.1𝑚 𝜑 = 2 𝜌 = 5 𝑆, 𝑟 0 , 𝜑 ρ 𝐹 1 𝐹 1 = 2𝑇𝑃 2𝑇𝑃 + 𝐹𝑃 + 𝐹𝑁 IoU = 𝑇𝑃 𝑇𝑃 + 𝐹𝑃 + 𝐹𝑁 = 𝐹 1 2 -𝐹 1 𝑇𝑃 𝐹𝑃 𝐹𝑁 ± ± ± ± ± ± ± ± ± ± ± ± ± 𝒯
𝑖 𝑚𝑎𝑥 = 20 𝐹 1 𝐹 1 𝐹 1 × 3 1 |𝒩| ∑ 𝑐 × 3 1 |𝒩| -1 ∑(𝑐 -𝑐̅ ) 2 𝑆 = 8 𝑟 0 = 0.05𝑚 𝜑 = 2 𝜌 = 5 𝑆 = 8 𝑟 0 = 0.1𝑚 𝜑 = 2 𝜌 = 5 𝑛 0 = 1,000 𝑛 𝑖𝑛𝑐 = 2,000 𝑖 𝑚𝑎𝑥 = 20 𝜌 𝜌 𝜌 𝜌 = 3 𝜌 𝜌 𝜌 = 5 𝜌 𝜌 𝜌 3 × 3 𝜌        𝐹 𝑔 𝐹 * 𝑔 = ℱ -1 (ℱ(𝐹) ⊙ ℱ(𝑔)) ⊙ * ℱ 𝑈 𝑥 𝑥 ̂= ℱ(𝑥) = 𝑈 𝑇 𝑥 𝑥 = ℱ -1 (𝑥 ̂) = 𝑈𝑥 F * 𝑔 = 𝑈(𝑈 𝑇 𝐹 ⊙ 𝑈 𝑇 𝑔) 𝑈 𝑇 𝑔 𝑈 𝑇 𝑔 Θ 𝐹 * 𝑔 = 𝑈Θ𝑈 𝑇 𝐹 Θ 𝑀𝐿𝑃(ℎ 1 , … , ℎ 𝑙 ) 𝑙 ℎ 𝑖 𝑖 1 × 1 𝑀𝐿𝑃(6,6) ℝ 2 ℝ 2 ℝ 3 ℝ 𝑛 64 × 64 3 × 3 𝑑 𝐼 𝑔 𝑥 (𝐼 * 𝑔)(𝑥) = ∑ 𝑔(𝑥 𝑖 -𝑥)𝐼(𝑥 𝑖 ) 𝑥 𝑖 ∈𝒩 𝑥 𝒩 𝑥 𝑥 𝑥 𝑥 𝑖 ℕ 2 𝑔 𝑥 𝑥 𝑥 𝑖 ℝ 3 𝑔 𝑥 𝑖 𝑓 𝑖 𝒫 ∈ ℝ 𝑁×3 ℱ ∈ ℝ 𝑁×𝐷 ℱ 𝑔 𝑥 ∈ ℝ 3 (ℱ * 𝑔)(𝑥) = ∑ 𝑔(𝑥 𝑖 -𝑥)𝑓 𝑖 𝑥 𝑖 ∈𝒩 𝑥 𝑓 𝑖 ℝ 𝐷 𝑔 ℝ 𝑂 𝑂 𝑔 𝑥 𝑦 𝑖 = 𝑥 𝑖 -𝑥 𝑔 ℝ 3 ℝ 3 𝑔 ℝ 3 𝑔 𝑔 = 𝑀𝐿𝑃(

  { (𝑥 𝑖 , 𝑓 𝑖 ) | 𝑥 𝑖 ∈ ℝ 3 , 𝑓 𝑖 ∈ ℝ 𝐷 } { (𝑥 𝑖 , 𝑓 𝑖 ) | 𝑥 𝑖 ∈ ℝ 3 , 𝑓 𝑖 ∈ ℝ 𝐷 } 𝑦 0 , 𝒫, 𝑟) = { 𝑥 𝑖 ∈ 𝒫 | ‖𝑦 0 -𝑥 𝑖 ‖ ≤ 𝑟 } 𝑦 0 𝑘 𝑦 0 𝒩 𝐾𝑁𝑁 (𝑦 0 , 𝒫, 𝑘) = {𝑥 𝑖 ∈ 𝒫 | ‖𝑦 0 -𝑥 𝑖 ‖ ≤ ‖𝑦 0 -𝑥 𝑖+1 ‖, 𝑖 < 𝑦 0 , 𝒫, 𝑟, 𝐻) = { 𝑥 𝑖 ∈ 𝒫 | ‖𝑃 𝐻 (𝑦 0 ) -𝑃 𝐻 (𝑥 𝑖 )‖ 𝐩 𝟎 ) = 𝒩(𝐩 𝟎 , 𝐶 𝑠 , 𝑟 𝑠 )

  ) = ∑ 𝑊 𝑘 (∑ 𝜒 𝑖𝑘 (𝑥)[𝑀𝐿𝑃(𝑦 𝑖 ), 𝑓 𝑖 ] 𝑖 ) = 𝑔 𝑠𝑡𝑒𝑝 (𝑦 𝑖 ) • 𝑔 𝑇𝑎𝑦𝑙𝑜𝑟 (𝑦 𝑖 ) 𝑔 𝑠𝑡𝑒𝑝 𝑔 𝑇𝑎𝑦𝑙𝑜𝑟 𝑔 𝑔(𝑦 𝑖 ) = 𝑤 𝑖 • 𝑔 𝑇𝑎𝑦𝑙𝑜𝑟 (𝑦 𝑖 ) , 𝑔 𝑑,𝑜 (𝑦 𝑖 ) = 𝑊 𝑑,𝑜 𝑦 𝑖 + 𝑏 𝑑,𝑜 𝐷 × 𝑂 × 4 𝑔 𝑔(𝑦 𝑖 ) = ∑ Φ(|𝑦 𝑖 -𝑥 ̃𝑘|){𝑥 𝑖 ∈ 𝒫 | ‖𝑥 𝑖 -𝑥‖ ≤ 𝑟} 𝑦 𝑖 = 𝑥 𝑖 -𝑥 ℬ 𝑟 3 = {𝑦 ∈ ℝ 3 | ‖𝑦‖ ≤ 𝑟} ℬ 𝑖 , 𝑥 ̃𝑘) = max (0, 1 -‖𝑦 𝑖 -𝑥 ̃𝑘‖ 𝜎 ) 𝑦 𝑖 , 𝑥 ̃𝑘) = max (0, 1 -‖𝑦 𝑖 -𝑥 ̃𝑘‖ 𝜎 ) ℎ 𝑔𝑎𝑢𝑠𝑠𝑖𝑎𝑛 (𝑦 𝑖 , 𝑥 ̃𝑘) 𝑖 ) = ∑ ℎ(𝑦 𝑖 , 𝑥 ̃𝑘)𝑊 𝑘 𝑘<𝐾 𝑔(𝑦 𝑖 ) = ℎ(𝑦 𝑖 , 𝑥 ̃𝑘 * )𝑊 𝑘 with 𝑘 𝑔)(𝑥) = ∑ 𝑔 𝑑𝑒𝑓𝑜𝑟𝑚 (𝑥 𝑖 -𝑥, ∆(𝑥))𝑓 𝑖 𝑥 𝑖 ∈𝒩 𝑥 𝑔 𝑑𝑒𝑓𝑜𝑟𝑚 (𝑦 𝑖 , ∆(𝑥)) = ∑ ℎ(𝑦 𝑖 , 𝑥 ̃𝑘 + ∆ 𝑘 (𝑥)𝑥) = ∑ ∑ ℎ(𝑥 ̃𝑘 + ∆ 𝑘 (𝑥), 𝑥 ̃𝑙 + ∆ 𝑙 (𝑥)) , de nouvelles technologies permettent l'acquisition de scènes 3D volumineuses et précises sous la forme de nuages de points. Les nouvelles applications ouvertes par ces technologies, comme les véhicules autonomes ou la maintenance d'infrastructure, reposent sur un traitement efficace des nuages de points à grande échelle. Les méthodes d'apprentissage profond par convolution ne peuvent pas être utilisées directement avec des nuages de points. Dans le cas des images, les filtres convolutifs ont permis l'apprentissage de nouvelles représentations, jusqu'alors construites « à la main » dans les méthodes de vision par ordinateur plus anciennes. En suivant le même raisonnement, nous présentons dans cette thèse une étude des représentations construites « à la main » utilisées pour le traitement des nuages de points. Nous proposons ainsi plusieurs contributions, qui serviront de base à la conception d'une nouvelle représentation convolutive pour le traitement des nuages de points. Parmi elles, une nouvelle définition de voisinages sphériques multi-échelles, une comparaison avec les k plus proches voisins multi-échelles, une nouvelle stratégie d'apprentissage actif, la segmentation sémantique des nuages de points à grande échelle, et une étude de l'influence de la densité dans les représentations multi-échelles. En se basant sur ces contributions, nous introduisons la « Kernel Point Convolution » (KPConv), qui utilise des voisinages sphériques et un noyau défini par des points. Ces points jouent le même rôle que les pixels du noyau des convolutions en image. Nos réseaux convolutionnels surpassent les approches de segmentation sémantique de l'état de l'art dans presque toutes les situations. En plus de ces résultats probants, nous avons conçu KPConv avec une grande flexibilité et une version déformable. Pour conclure notre réflexion, nous proposons plusieurs éclairages sur les représentations que notre méthode est capable d'apprendre.ABSTRACTIn the recent years, new technologies have allowed the acquisition of large and precise 3D scenes as point clouds. They have opened up new applications like self-driving vehicles or infrastructure monitoring that rely on efficient large scale point cloud processing. Convolutional deep learning methods cannot be directly used with point clouds. In the case of images, convolutional filters brought the ability to learn new representations, which were previously hand-crafted in older computer vision methods. Following the same line of thought, we present in this thesis a study of hand-crafted representations previously used for point cloud processing. We propose several contributions, to serve as basis for the design of a new convolutional representation for point cloud processing. They include a new definition of multiscale radius neighborhood, a comparison with multiscale k-nearest neighbors, a new active learning strategy, the semantic segmentation of large scale point clouds, and a study of the influence of density in multiscale representations. Following these contributions, we introduce the Kernel Point Convolution (KPConv), which uses radius neighborhoods and a set of kernel points to play the role of the kernel pixels in image convolution. Our convolutional networks outperform state-of-the-art semantic segmentation approaches in almost any situation. In addition to these strong results, we designed KPConv with a great flexibility and a deformable version. To conclude our argumentation, we propose several insights on the representations that our method is able to learn.MOTS CLÉS3D, apprentissage profond, nuage de points, convolution, sémantisation KEYWORDS 3D, deep learning, point clouds, convolution, semantic segmentation

𝒪(𝑛 2 )

𝑂(𝑁)

3

3 3 3 = 27

∆ 𝑘(𝑥)

× 1 𝐷 𝑖𝑛 ≠

2𝐷

-2 [0.8, 1.2]

× 1