Edmundo-Pavel Soriano-Morales
email: edmundo.soriano-morales@univ-lyon2.fr

Julien Ah-Pine
email: julien.ah-pine@univ-lyon2.fr

Sabine Loudcher
email: sabine.loudcher@univ-lyon2.fr

Hypergraph Modelization of a Syntactically Annotated English Wikipedia Dump

Wikipedia, the well known internet encyclopedia, is nowadays a widely used source of information. To leverage its rich information, already parsed versions of Wikipedia have been proposed. We present an annotated dump of the English Wikipedia. This dump draws upon previously released Wikipedia parsed dumps. Still, we head in a different direction. In this parse we focus more into the syntactical characteristics of words: aside from the classical Part-of-Speech (PoS) tags and dependency parsing relations, we provide the full constituent parse branch for each word in a succinct way. Additionally, we propose a hypergraph network representation of the extracted linguistic information. The proposed modelization aims to take advantage of the information stocked within our parsed Wikipedia dump. We hope that by releasing these resources, researchers from the concerned communities will have a ready-to-experiment Wikipedia corpus to compare and distribute their work. We render public our parsed Wikipedia dump as well as the tool (and its source code) used to perform the parse. The hypergraph network and its related metadata is also distributed.

Introduction and Related Work

Today, the broad reach of Wikipedia in Text Mining (TM) and Natural Language Processing (NLP) research is indisputable. Several recent approaches and tools have been conducted based on the explicit and implicit knowledge contained in it. Certainly, Wikipedia provides a common ground for researchers and developers to test and compare their results. Wikipedia has been used as a source of valuable data as well as a common background corpus to perform experiments and compare results for diverse NLP/TM related tasks. For example, concerning the first case, in the area of Information Extraction, Wikipedia's infoboxes structured information is used in [START_REF] Wu | Open information extraction using wikipedia[END_REF] as a valuable resource to complement and improve their open IE system. Along the same line, [START_REF] Charton | NLGbAse: A Free Linguistic Resource for Natural Language Processing Systems[END_REF] extracted metadata from Wikipedia while leveraging its internal structure in order to produce a semantically annotated corpus. Moving on to the Information Retrieval field, features extracted from Wikipedia can also help to better predict the performance of a query [START_REF] Katz | Wikipedia-based query performance prediction[END_REF] in a given corpus. In the second case, as a background collection for experiments, a document-aligned version of English and Italian Wikipedia has been used to determine the quality between word's translations [START_REF] Vulić | Identifying word translations from comparable corpora using latent topic models[END_REF]. Wikipedia, being such a popular resource already has various off-the-shelf parsed snapshots (or dumps). These parsed dumps allow researchers to focus more into their approaches than into the extraction and transformation of Wikipedia's data. We briefly describe certain relevant parses found in the literature. A relevant Wikipedia parsed dump example comes from (Jordi [START_REF] Atserias | Semantically Annotated Snapshot of the English Wikipedia[END_REF]. Their work provides a balanced amount of syntactic and semantic information. In short, the dump includes each word's Part-of-Speech (PoS) tag, their dependency relations as well as the output of three different named entity recognition parsers. Additionally, they provide a graph structure that leverages Wikipedia's internal composition alongside its corresponding metadata.

Nonetheless, the resource is no longer available on the original URL although it may be obtained through Yahoo's Webscope1 datasets library. In [START_REF] Flickinger | WikiWoods: Syntacto-Semantic Annotation for English Wikipedia[END_REF], they perform a deep parse analysis is performed to provide detailed syntactic and semantic information. The authors leverage a previously manually annotated portion of the English Wikipedia. They extract a grammar from this portion and also train a statistical model to automatically parse the rest of Wikipedia. Even though the parse offered is deep and rich in details, the annotation labels, as well as the corpus output format, may not be convenient and easy to use because of its complexity and particular nature. [START_REF] Schenkel | Fachtagung des GI-Fachbereichs "Datenbanken und Informationssysteme[END_REF] released a purely semantic XML parse that links WordNet concepts to Wikipedia pages. They focus greatly on cleaning and pre-treating Wikipedia. In this paper we do not focus as much into the cleaning of Wikipedia as already available tools can solve the task quite well for non-specific needs. Finally, there are certain Wikipedia dumps that offer the raw cleaned text without any extra subsequent parsing or analysis. Such is the case of the corpus made available by [START_REF] Shaoul | The Westbury Lab Wikipedia Corpus[END_REF]. This corpus makes use of the WikiExtractor script (Giuseppe [START_REF] Attardi | WikiExtractor[END_REF] to clean the Wikipedia dump. Although the existing parses and dumps already satisfy numerous specific research needs, they have certain limitations that drove us to build our own resource: the Syntactically Annotated English Wikipedia Dump (SAEWD). Specifically, we address the following shortcomings: the lack of constituents-based tree information, the complex output formats, the limited online access and the absence of the tools used (i.e., the source code) to create the annotated corpus. In SAEWD we include the complete parse tree information for each word provided by well-known parsing tools. We store the extracted information in a simple and already existing output format. Additionally, we give open access to the parsed dump and we share our source code with the community. The code allows anyone (with programming skills) to apply our processing pipeline and build their own particular Wikipedia parse or even to parse other text collections. Finally, we present and provide a hypergraph linguistic network for fast NLP/TM experimentation. Indeed, SAEWD aims to be used as a stepping stone for a standard Wikipedia parsed version for the largest possible set of tasks in future research. SAEWD uses widely known English language parsing tools, namely those included in the Stanford CoreNLP suite. Aside from being accessible and regularly maintained, it provides a common set of labels (Universal Dependencies 2 ) used by numerous NLP and TM experiments. Regarding SAEWD output's format, we believe that the file format we use, which follows that of (Jordi [START_REF] Atserias | Semantically Annotated Snapshot of the English Wikipedia[END_REF], allows for fast reading and simple interpretation. Among other syntactical information, we provide the constituents parse branch for each word (explained in detail in Section 3.). Constituent's paths, and hence chunk's production rules, have been proved useful as a complement feature to classic text representations [START_REF] Sagae | Clustering Words by Syntactic Similarity Improves Dependency Parsing of Predicate-Argument Structures[END_REF][START_REF] Bergsma | Stylometric Analysis of Scientific Articles[END_REF][START_REF] Massung | Structural parse tree features for text representation[END_REF]. As a second contribution, we propose a hypergraph linguistic representation. Over the past few years, research on the NLP domain has been focusing on novel techniques that take advantage of the characteristics of language networks to achieve new and interesting results [START_REF] Mihalcea | Graphbased Natural Language Processing and Information Retrieval[END_REF]. That is why, in addition to SAEWD, we also propose, as a proof of concept, a hypergraph representation that stores certain information found in a SAEWD in a practical way that allows for fast and effortless data extraction. This hypergraph can be indeed considered as a Linguistic Network [START_REF] Choudhury | The structure and dynamics of linguistic networks[END_REF]. It aims to facilitate the implementation of graph-based approaches by allowing researchers to jump directly into the algorithm development stage. We use a sub-sample of the Wikipedia corpus consisting of articles related to Natural Language Processing and Text Mining. In the following sections we describe the steps we undertook to transform a Wikipedia dump into SAEWD (Section 2), we give a detailed account of the contents of SAEWD and the format in which we stored the parsed information (Section 3), then we explain the characteristics of our proposed network structure (Section 4). Lastly, we present our final comments on the nature of the work done as well as possible future work perspectives.

Construction of SAEWD

The three main steps we followed to build SAEWD are presented in Figure 1. Briefly, we have one input, which is the Wikipedia dump and one output which is the parsed snapshot. In the following we provide a detailed description of each of the process. We begin the construction of the parsed corpus with the Wikipedia dump XML file obtained from the Wikipedia database 3 from early November 2014. This dump contains around 4.7 million article pages 4 . As shown in Figure 1, 2 http://universaldependencies.github.io/ docs/ 3 https://dumps.wikimedia.org/enwiki 4 We kept all articles available in the Wikipedia dump. we apply the following processing steps in order to yield the final parsed version.

Cleaning Wikipedia

First, we discard Wikipedia's tables, references and lists, markup annotations and HTML tags with the WikiExtractor (Giuseppe [START_REF] Attardi | WikiExtractor[END_REF] script. We used this tool to clean and split the content of the original XML file into 429 folders each one containing 100 files of approximately 300 kB. These files contain a certain number of complete Wikipedia articles which is automatically determined by WikiExtractor according to the maximum possible size assigned for each file, 300 kB in our case, thus the number of articles in each file may vary. We decided to use numerous files as well as a small size to easily read their content into memory while parsing. Having multiple small files also makes it easier to handle the multi-threading aspect of our parsing tool. We kept WikiExtractor's original folder nomenclature which assigns to each one of them a sequence of letters sorted lexicographically5 . The files containing the cleaned text is simply named wiki XX where XX goes from 00 to 99, as we have 100 files per folder. It is important to note that the Wikipedia articles' titles themselves are not sorted in any specific way, as it was not in the interest of our research to have them ordered. Inside each cleaned file, besides the article's text, WikiExtractor keeps the original article's URL as well as its unique Wikipedia ID within an XML-like label that also doubles as article separator.

Parsing Wikipedia

Next, once the Wikipedia dump had been cleaned, we use the Stanford CoreNLP6 [START_REF] Manning | The Stanford CoreNLP Natural Language Processing Toolkit[END_REF] analysis tools to parse all the file texts produced during the previous step. As a part of our processing pipeline, we first perform sentence segmentation, word tokenization and lemmatization. Below, we briefly describe each of the extracted attributes. We also exemplify them in detail in Section 3.. • PoS tagging: We obtain the grammatical category of each word, i.e., the part-of-speech tag, using the CoreNLP default tagger, the left3words PoS tagging model.

• Dependency parse: this attribute consists on an extracted tree that describes the types of grammatical relations between words, i.e., the dependency-based parse tree. The analysis was performed with the Stanford's Shift-Reduce parser. As information representation, we use the basic dependencies scheme, as we wanted to include each one of the possible dependency relations without any collapsing between them.

• Constituents parse: the output of this analysis is a rooted tree that represents the syntactic structure of a phrase. This tree is commonly known as the constituency-based parse tree. For each word, we store its complete path in the constituency tree. Specifically, we keep all the nodes of a word's own branch from the root to the word itself. We employ the Stanford Shift-Reduce parser. This path is transformed into a single line and included in SAEWD.

Finally, once the parsing process is complete, the parsed files are stored into individual files and thus there are as much parsed files as input Wikipedia cleaned files. The parsed files keep their original name plus the parsed extension, e.g., wiki 00.parsed. The structure within the files is described in Section 3.2.. After parsing, we found the statistics shown in Table 1.

SAEWD Description

In this section we describe in detail the characteristics of SAEWD.

Constituency parse storage in detail

We will use an example to better explain the storage of the constituency-based parse tree. In Figure 2 we can see the constituency parse of the phrase A great brigand becomes a ruler of a Nation. On the bottom of the figure, we observe the constituent's path (or branch), of the words brigand and Nation. As in any tree structure, each leaf node has a defined path from the root node to itself. In this example, the leaf containing the noun brigand follows the bottom-up path NP22→S97. Brigand's parent node is a Noun Phrase (NP) node which in turn comes from the root of the tree, the Sentence node S. We assign to each phrase chunk an identifier (22 and 97 in this case) in order to distinguish them according to their building elements as specified by the grammar rule used. In other words, a phrase chunk, e.g., a NP, a Verbal Phrase (VP), a Prepositional Phrase (PP), or other chunk defined by the grammar in CoreNLP, may be built from different types of PoS tags. Thus, again from Figure 2, we see that the sentence S97 is built both from a NP and a VP chunk. In a similar way, the noun phrase NP18 is produced by a determinant (DT) and a noun (NN), while NP22 is generated by a determinant, an adjective (JJ) and a noun. The identification digits are obtained from the hash code that represents each chunk object inside our Java application. For each phrase-chunk tree node, we keep the last two significative figures produced by the hashCode7 Java method.

As another example, the noun Nation has the following bottom-up constituency path: NP18→PP57→NP20→VP44.

Indeed, the string NP 18,PP 57,NP 20,VP 44,S 97, originating from the previously described path, is the information we keep about the constituency parse for each token in the Wikipedia dump.

Annotation scheme

To store the parsed text we use a scheme inspired by that used in (Jordi [START_REF] Atserias | Semantically Annotated Snapshot of the English Wikipedia[END_REF]. The format can be considered as a regular tsv file (i.e., the entries are separated by tab spaces) with additional metadata tags. An extract from a parsed file can be observed in Table 2. The file includes two headers: the first one simply indicates the name of the current parse file; the second one contains the names that describe each column. The tags and columns our parsed dump contains are the following:

NN brigand 1 1 1 ruler 1 1 1 nation 1 1 1 1 VB becomes 1 JJ great 1 1 1
Table 3: Brief example of the linguistic network incidence matrix of the previous used phrase. On the left side, as on the top, we can see the metadata we store for each word (rows) and each column (hyperedges). We omit the rest of the words from the example phrase for brevity.

3. %%#SEN: marks the beginning of a new sentence. It is followed by two integers: (1) the number of the current sentence, and (2), the number of tokens in the sentence.

• Parse columns for each token:

1. Token: the token itself, 2. Lemma: the token the canonical form, 3. POS: its part of speech tag, 4. Constituency: the bottom-up constituency path described before, 5. Head: the head index of the dependency relation the current token belongs to, 6. Constituency: the name of the grammatical relationship this token participates in as a dependent.

Using the example phrase introduced before (Table 2), the token becomes has become as lemma, it is a verb, thus it has VBZ as PoS tag, its constituency path is VP 44,S 97, so it belongs to the verb phrase VP44 which in turn comes from sentence S97. Finally, becomes, being the main verb, is in this case the grammatical root of the sentence and its head is by convention determined as zero.

Concerning the computation time, SAEWD takes around 40 hours to be produced using a general purpose laptop (Intel i7 4700MQ with 4 cores, 8 GB and Linux Mint 17 as operative system). Most of the time is taken by the parsing step.

We verified the consistency of the corpus built by analyzing a sample of 20 Wikipedia articles. The output of CoreNLP and the information contained in the corpus match.

Hypergraph and its Metadata

Once SAEWD is saved to disk, we leverage its information by building a linguistic network by connecting tokens according to their interaction within the Wikipedia corpus.

The following section describes the network built from a sample of the information stored in SAEWD.

Given the large size of the Wikipedia corpus, we chose a sample of it to illustrate our proposed representation. We selected all the articles that are linked and that link to the Natural Language Processing Wikipedia's page. The network is modeled as a hypergraph. Briefly, a hypergraph is a graph generalization where the main difference is that edges (named hyperedges) can link any number of vertices. Hypergraphs have been previously used to model complex networks allowing for a more complete representation of their inner dynamics [START_REF] Estrada | Complex networks as hypergraphs[END_REF]. In our case, hyperedges allow us to group words together according to certain features, such as whether words belong to the same phrase chunk, to the same sentence, whether they share the same dependency relation or if they occur in the same context window with another and so on.

Our hypergraph provides a structure that establishes relations between tokens. These relationships can be one of two broad types: syntactical dependencies or contextual co-occurrences. The former takes into account the gram-matical relation tokens partake in; the latter connects words according to their co-occurrences at the sentence or NP chunk level. Formally, our hypergraph is defined by a pair G = (V, E), where the vertices V = {v 1 , v 2 , ..., v n } represent the set of tokens in the corpus and E = {e 1 , e 2 , ..., e m } the set of hyperedges.

Each hyperedge may be one of three types: noun phrase (NP), dependency (DEP), or sentence (SEN). These hyperedges represent linuistic units. The NP set of hyperedges contain words that appear in the same noun phrase.

In the same sense, DEP hyperedges are the sets of words that share the same syntactic dependency relation (as dependents of a specific head). Finally, hyperedges of type SEN group tokens that appear in the same sentence.

Our hypergraph can be represented as a n × m incidence matrix with entries h(i, j) = N (v i , e j ) where N (v i , e j ) is the number of times v i ∈ e j occurs in the corpus. That is to say, the value h(i, j) correspond to the number of times a token i occurs in the same sentence, noun phrase or syntactic relation j across the entire Wikipedia corpus.

Table 3 shows the nature of the hypergraph data structure we provide using again the example phrase described in previous sections. There are two main parts to it: (1) the incidence matrix, and (2) its accompanying metadata. The matrix contains the counts of the occurrences of each word within each kind of column as stated above. The metadata is the information that describes the meaning of each row (tokens) and each column (hyperedges) in the matrix.

The matrix itself contains only positive values as it is the number of times each word has occurred in each one of the hyperedges considered. The metadata, shown in Table 3, gives us, for each line and column, information about the token itself, its PoS tag, the type of column (NP,DEP, SEN), and the sub-type columns of NP and DEP, that is, what kind of noun phrase or syntactic relation we are considering. Looking at the first line of the matrix, we can know it is the token brigand, which is a noun (its PoS tag is NN). The metadata also tells us that it occurred in the first noun phrase of type NP 22, it took part in the nominal subject relation (nsubj) where the head was the lemmatized token become. Finally, we know it occurred in the same sentence as ruler, nation, becomes, great and the rest of the words from the phrase, which are not shown for brevity. We store the incidence matrix (which is in fact a sparse matrix) on disk as a Matrix Market format file. The metadata is stored as JSON files. Both formats allow for an easy data lecture.

Conclusion and Future Work

We parsed the English Wikipedia, focusing on syntactic features namely the dependencies and constituents parse trees. We believe that the constituent membership for each token is a rich source of information for future research. The Wikipedia dump was stripped clean of tables, lists and other noisy elements, thanks to the WikiExtractor script.

Our analysis was done with the CoreNLP suite which is a common tool among NLP/TM researchers and developers.

It is a reliable tool that allow us to hastily and reliably process the complete corpus. The format of SAEWD follows a previous one which hopefully will allow for an easier adoption throughout the community. We proposed and make available a hypergraph representation of a sample of the data collected in SAEWD.

All our resources are available in http://eric. univ-lyon2.fr/ ˜psoriano/SAWD.html.

As future research directions, we are currently working with the information contained in SAEWD, in part using the network proposed. We believe that the use of the constituency paths, coupled with the classic word cooccurrence relations, can shed light into interesting results to a number of tasks in NLP. Concerning the hypergraph, we plan to analyze the possible redundancy that may exist while adding hyperedges for each noun phrase found in the corpus. Although we get access to detailed syntactic information, the number of columns grows rapidly. Finally, a comparison between the nature of the network among different languages is also of our interest.

Figure 1 :

 1 Figure1: The tree steps we took to build SAEWD.

Figure 2 :

 2 Figure 2: Constituency tree for the phrase A great brigand becomes a ruler of a Nation.

Table 1 :

 1 English Wikipedia dump statistics.

	Number of tokens	1,889,769,908
	Unique tokens (types)	8,761,691
	Number of sentences	84,760,512
	Average number of tokens per sentence	22.30

Table 2 :

 2 Extract of a Wikipedia parsed file. The phrase shown is the parse result of the previous example sentence in Figure2NP 20 1 NP 18 1 NP 18 2 nsubj become xcomp become nmod ruler amod brigand S 1

	• Metadata tags:
	1. FILENAME: indicates the original file used to
	extract the current parse,
	2. %%#PAGE: denotes a new Wikipedia article, as
	well as its title,

https://webscope.sandbox.yahoo.com/

We have folders named AA, AB, AC and so on.

http://nlp.stanford.edu/software/ corenlp.shtml

Java hashCode function description: https://en. wikipedia.org/wiki/Java_hashCode%28%29


Mustapha Bouakkaz

Sabine Loudcher

Youcef Ouinten
email: ouinteny@lagh-univ.dzsabine.loudcher@univ-lyon2.fr

A New Tool for Textual Aggregation in OLAP Context

Keywords: Aggregation, OLAP, Textual data, Algorithm

We present in this paper a system for textual aggregation from scientific documents in the online analytical processing (OLAP) context. The system extracts keywords automatically from a set of documents according to the lists compiled in the Microsoft Academia Search web site. It gives the user the possibility to choose their methods of aggregation among the implemented ones. That is TOP-Keywords, TOPIC, TUBE, TAG, BienCube and GOTA. The performance of the chosen methods, in terms of recall, precision, F-measure and runtime, is investigated with two real corpora ITINNOVATION and OHSUMED with 600 and 13,000 scientific articles respectively, other corpora can be integrated to the system by users.

INTRODUCTION

The huge increasing amount of complex data such as text available in different web sites, e-mails, local networks in business company, electronic news and elsewhere is overwhelming. This uncontrolled increase of information in the different fields, makes difficult to exploit the useful ones from the rest of data. This situation starts switching the information from useful to troublesome. The capability of OLAP tools available especially the text OLAP is not growing in the same way and the same speed the amount of textual documents is increasing. This problem is dramatically exacerbated by the big quantity of textual documents indexed by Search engines every moment. This makes the task of text OLAP and knowledge extraction from textual documents very limited and reduces the competitive advantage we can gain. Recently, a large number of systems have been developed over the years to solve this kind of problems and perform tasks in Information Retrieval; many of these systems perform specific tasks such as word counter and text summarization, however they are not in the level to satisfy the growing need of users to extract the useful information from documents using Text OLAP approaches.

In this paper we describe a software platform for keywords extraction and aggregation in an OLAP context. The platform implements a new way for extracting keywords from a corpus of document based on the Microsoft academia research web site and six algo-rithms for keyword aggregation which process a corpus of textual data to discover aggregated keywords. The rest of the paper is organized as follows: Section 2 introduces related works in keywords extraction and aggregation in OLAP context. Section 3 describes the main components of the software prototype along with their functionalities. Whereas section 4 is devoted to numerical experiments. Finally, Section 5 presents conclusions and discusses further developments.

EXISTING APPROACHES AND TOOLS

Many approaches are proposed for keyword extraction but only a few for aggregation keywords. On the other hand, the majority of the existing work is based on information retrieval, and only some of them are in the OLAP context, where textual documents are stored in a data warehouse. In this section we make an inventory of the existing approaches in OLAP context, which describes a corpus of documents through the most representative aggregated keywords. There is a classical classification that includes the supervised and unsupervised approaches for keywords extraction, meanwhile in our case we introduce a new classification for textual extraction and aggregation approaches proposed in the OLAP context. We classify the previous works found in the literature into four categories. The first one uses statistical methods; the second one is based on linguistic knowledge; the third one is based on graphs; while the last uses external knowledge. The approaches based on statistical methods use the occurrence frequencies of terms and the correlation between terms to extract the keywords. Hady et al. [START_REF] Hady | Tube (textcube) for discovering documentary evidence of associations among entities[END_REF] proposed an approach called TUBE (Text-cUBE). They adopted a relational database to textual data based on the cube design, each cell contains keywords, and they attached to each keyword an interestingness value. Zhang et al. [START_REF] Zhang | Topic cube: Topic modeling for olap on multidimensional text databases[END_REF] proposed an approach called Topic Cube. The main idea of a Topic Cube is to use the hierarchical topic tree as the hierarchy for the text dimension. This structure allows users to drill-down and roll-up along this tree. users discover also the content of the text documents in order to view the different granularities and levels of topics in the cube. The first level in the tree contains the detail of topics, the second level contains more general types and the last level contains the aggregation of all topics. A textual measure is needed to aggregate the textual data. The authors proposed two types of textual measures, word distribution and topic coverage. The topic coverage computes the probability that a document contains the topic. These measures allow user to know which topic is dominant in the set of documents by aggregating the coverage over the corpus. Ravat et al. [START_REF] Ravat | Top keyword extraction method for olap document[END_REF] proposed an aggregation function called TOP-Keywords to aggregate keywords extracted from documents. They used the t f .id f measure, then they selected the first k most frequent terms. [START_REF] Bringay | Towards an on-line analysis of tweets processing[END_REF] proposed an aggregation function, based on a new adaptive measure of t f .id f . It takes into account the hierarchies associated to the dimensions. [START_REF] Wartena | Topic detection by clustering keywords[END_REF] proposed another method we called TOPIC in which they used the k-bisecting clustering algorithm and based on the Jensen-Shannon divergence for the probability distributions as described in [START_REF] Archetti | A hierarchical document clustering environment based on the induced bisecting k-means[END_REF]. Their method starts with the selection of two elements for the two first clusters. are assigned to the cluster of the closest of the two selected elements. Once all the terms are assigned, the process will be repeated for each cluster with a diameter larger than a specified threshold value. Bouakkz et al. [START_REF] Bouakkaz | Gota: Using the google similarity distance for olap textual aggregation[END_REF] proposed a textual aggregation based on keywords. When a user wants to obtain a more aggregate view of data, he does a roll-up operation which needs an adapted aggregation function. their approach entitled GOTA is composed of three main parts, including: (1) extraction of keywords with their frequencies; (2) construction of the distance matrix between words using the Google similarity distance;

(3) applying the k-means algorithm to distribute keywords according to their distances, and finally (4) selection the k aggregated keywords. The approaches based on linguistic knowledge consider a corpus as a set of the vocabulary mentioned in the documents; but the results in this case are sometimes ambiguous. However, to overcome this obstacle, techniques based on lexical knowledge and syntactic knowledge previews have been introduced. In [START_REF] Poudat | Cleuziou g., and clavier v., categorisation de textes en domaines et genres. complementarite des indexations lexicale et morpho syntaxique[END_REF][START_REF] Kohomban | Optimizing classifier performance in word sense disambiguation by redefining sense classes[END_REF] the authors described a classification of textual documents based on scientific lexical variables of discourse. Among these lexical variables, they chose nouns because they are more likely to emphasize the scientific concepts, rather than adverbs, verbs or adjectives. The approaches based on the use of external knowledge select certain keywords that represent a domain. These approaches often use models of knowledge such as ontology. Ravat et al. proposed an other aggregation function that takes as input a set of keywords extracted from documents of a corpus and that outputs another set of aggregated keywords [START_REF] Ravat | Olap aggregation function for textual data warehouse[END_REF]. They assumed that both the ontology and the corpus of documents belong to the same domain. Oukid et al. proposed an aggregation operator Orank (OLAP rank) that aggregated a set of documents by ranking them in a descending order using a vector space representation [START_REF] Oukid | Cxt-cube: Contextual text cube model and aggregation operator for text olap[END_REF]. The approaches based on graphs use keywords to construct a keyword graph. The nodes represent the keywords obtained after pre-processing, candidate selection and edge representation. After the graph representation step, different types of keyword ranking approaches have been applied. The first approach proposed in [START_REF] Mihalcea | Textrank: Bringing order into texts[END_REF]) is called Tex-tRank, where graph nodes are the keywords and edges represent the co-occurrence relations between keywords. The idea is that, if a keyword gets link to a large number of other keywords, this keyword will be considered as important. Bouakkaz et al. [START_REF] Bouakkaz | Automatic textual aggregation approach of scientific articles in olap context[END_REF] propose a new method which performs aggregation of keywords of documents based on the graph theory. This function produces the main aggregated keywords out of a set of terms representing a corpus. Their aggregation approach is called TAG (Textual Aggregation by Graph). It aims at extracting from a set of terms a set of the most representative keywords for the corpus of textual document using a graph. The function takes as input the set of all extracted terms from a corpus, and outputs an ordered set, containing the aggregated keywords. The process of aggregation goes through three steps: (1) Extraction of keywords with their frequencies, (2) Construction of the affinity matrix and the affinity graph, and (3) Cycle construction and aggregated keywords selection.

The software system developed in this domain consists of two main components; Text Pre-processor and Topics Extractor. Text pre-processor, offers learning and inference functionalities. The learning functionality pre-processes a document collection by exploiting a stop words list and a general purpose to obtain the word-document matrix according to the bagof-words model. The user can choose the number of words to be used for document indexing. The inference functionality processes a document to obtain one of the following bag-of-words representations; binary, term frequencies and the inverse term document frequency. Topic extractor implements a customized version of the Latent Dirichlet Allocation (LDA) model [START_REF] Blei | Latent dirichlet allocation[END_REF]. The solution of the LDA learning is obtained by using the Expected Maximization and the Gibbs Sampling algorithms which have been implemented in the C++ programming language on a single processor machine. Each topic is summarized through the estimate of its prior probability, a sorted list of its most frequent words together with the estimate of their conditional probabilities. Semantria 1 is a text analytical tool that offers an API that performs sentiment analysis and analytic text. Users can be integrated in the service to quickly yield actionable data from their unstructured text data, from review sites, blogs, or other sources. Additionally, users can download trial version and use Semantria for Excel, which installs directly into Office Excel to set up an environment for analyses.

THE SOFTWARE SYSTEM DESCRIPTION

In order to create a suitable environment for the online analysis of textual data, we intend to propose a new software which performs aggregation of keywords. The system described in this paper consists of three main components; namely Text Preprocessor, Keywords Extractor and Keywords Aggregator. These components have been integrated into a software system developed with Java programming language.

1 https://semantria.com/

Text Pre-processor

This software component implements functionalities devoted to document pre-processing and document corpus representation. It offers words counter, and represents the documents of the corpus as a list of words with their frequencies (Figure1). Furthermore, binary and term frequency representations are allowed. The system takes the pdf, Microsoft Word and txt formats as valid inputs as shown in figure 1.

Keywords Extractor

This component is for keywords extraction. The keyword extraction function is based on the Microsoft Academic Search web site (MAS). MAS is a service provided by Microsoft to the public and it is free of charge. MAS classifies scientific articles into fifteen categories according to their fields. In each category it extracts the scientific keywords from articles and reorders them according to their frequencies. Our keywords extractor component uses this list of keywords and takes form each field the 2000 most frequent keywords, which are saved in separate text files. After that, Keywords Extractor process starts to compare MAS keywords with whole words extracted by the Text Pre-processor component. When a MAS keyword exists in the list, the extractor component saves it in a text file with its frequency and the name of the document in which it occurs. Once our process is finished, we will get the right useful keywords validated by MAS. The output of this component is a two fold Matrix of document and keywords (MDKW). which is used by the third component to aggregate keywords.

Keywords aggregation

The keywords aggregation component uses a set of textual aggregation algorithms TOP-Keywords, TOPIC, TUBE, TAG, BienCube and GOTA to aggregate keywords obtained in the previous step. it also produces the recall, precision, F-measure and the run time for each algorithm.

Graphical User Interface

The graphical user interface (GUI) is a necessary element in our system (OLAP-TAS) we take into consideration the ergonomical aspect to add an interactivity between the user and the machine when using our platform. The aim of the graphical user interface is to give the user a simple access to OLAP-TAS algorithms by a number of windows In this subsection, we present an example to show how OLAP-TAS has been used. We compiled two real corpora, the first is from the IIT conference 2 (conference and workshop papers) from the years 2008 to 2012. It consists of 600 papers ranging from 7 to 8 pages in IEEE format, including tables and figures. The keywords are extracted from the full words according to the Microsoft Academia Search 3 keywords. The second corpus is used by many authors to test their works such as [START_REF] Sebastiani | Machine learning in automated text categorization[END_REF][START_REF] Moschitti | Natural language processing and text categorization: a study on the reciprocal beneficial interactions[END_REF] [START_REF] Moschitti | Complex linguistic features for text classification: a comprehensive study[END_REF], this corpus is called Ohsumed collection4 , it includes medical abstracts from the MeSH (Medical Subject Headings)5 , it contains 20,000 documents. In our case we selected 13,000 medical abstracts to test the performance of the implemented algorithm in our OLAP-TAS. For the evaluation task, many types of measures have been proposed to evaluate keywords aggregation approaches, the majority of them insist on three measures, which are known as recall, precision, and Fmeasure. these measures are defined as fallows: The recall is the ratio of the number of documents to the total number of retrieved documents.

Recall = | {RelevantDoc} ∩ {RetrievedDoc} | | {RelevantDoc} | (1)
The precision is the ratio of the number of relevant documents to the total number of retrieved documents.

Precision = | {RelevantDoc} ∩ {RetrievedDoc} | | {RetrievedDoc} | (
2) The F-measure or balanced F-score, which combines precision and recall, is the harmonic mean of precision and recall. To show the kind of results and statistics obtained by OLAP-TAS after the execution, we take the first corpus as an example to illustrate the different graphs obtained for different algorithms in Figures 4,5, 6 and 7.

Uses of OLAP-TAS

In this section we will illustrate the use of the developed tool in both education and research. Education: OLAP-TAS is a visual tool that instructors can use to help their students understand the basic concepts and the algorithms they face during their study. For example, it can be used to teach the students how the k-bisecting clustering algorithm based on the Jensen-Shannon divergence for the probability distribution works [START_REF] Wartena | Topic detection by clustering keywords[END_REF]. As well as the T F * IDF and their variation in Top-keyword [START_REF] Ravat | Top keyword extraction method for olap document[END_REF] and Biencube [START_REF] Bringay | Towards an on-line analysis of tweets processing[END_REF]. It can also help students to understand how to use graphs for textual by the selection of cycles in TAG [START_REF] Bouakkaz | Automatic textual aggregation approach of scientific articles in olap context[END_REF] and the use of Google similarity distance (Cilibrasi and Vi-tanyi, 2007). In addition it shows the students how the recall, precision and F-measure change their values according to number of aggregated keywords k introduced by the user. Instructors may ask their students to do experiments with a real corpus using OLAP-TAS, write applications that use the Java classes, extend an existing approaches, or contribute in implementing a new algorithm to integrate in OLAP-TAS.

Research: OLAP-TAS contains implementations for several algorithms and approaches that solve common problems, such as textual aggregation in an OLAP context. It also comes with two corpora and annotated datasets. The implementation of other algorithms as well as other corpora, can be integrated into the platform. This makes it a good resource for researchers to build systems and conduct experiments. OLAP-TAS was successfully used in several research projects as shown in [START_REF] Bouakkaz | Automatic textual aggregation approach of scientific articles in olap context[END_REF].

CONCLUSIONS

In this paper a system for textual aggregation in text OLAP (OLAP-TAS) has been described. The software assists the user to discover the main aggregated keywords that best represent in a document collection. It is important to note that each approach is coded in a separate Java class to allow users to extend it or export it to another system. The use of OLAP-TAS reduces the amount of repeated code; it simplifies common tasks, and provides a graphical interface for textual aggregation approaches without requiring the knowledge in Java programming language.

Figure 1 :

 1 Figure 1: System architecture

Figure 2 :

 2 Figure 2: The Text Pre-processor and Keywords Extraction component interface

Figure 4 :

 4 Figure 4: Comparaison of the Recall

Figure 5 :

 5 Figure 5: Comparaison of the Precision

http://www.it-innovations.ae

academic.research.microsoft.com/

ftp://medir.ohsu.edu/pub/ohsumed

http://www.ncbi.nlm.nih.gov/mesh/


Edmundo-Pavel Soriano-Morales
email: edmundo.soriano-morales@univ-lyon2.fr

Julien Ah-Pine
email: julien.ah-pine@univ-lyon2.fr

Sabine Loudcher
email: sabine.loudcher@univ-lyon2.fr

Using a Heterogeneous Linguistic Network for Word Sense Induction and Disambiguation

Linguistic Networks are structures that allow us to model the characteristics of human language through a graph-like schema. This kind of modelization has proven to be useful while dealing with natural language processing tasks. In this paper, we first present and discuss the state of the art of recent semantic relatedness methods from a networkcentric point of view. That is, we are interested in the types of networks used to solve practical semantic tasks. In order to address some of the short-comings in the studied approaches, we propose a hybrid linguistic structure that takes into account lexical and syntactical language information. We show our model's practicality with a proof of concept: we set to solve word sense disambiguation and induction while using the presented network schema. Our modelization aims to shed light into ways of combining distinct types of linguistic information in order to take advantage of each of its components' unique characteristics.

Introduction

Today, thanks to the global pervasiveness of the Web, we have access to large quantities of open and collaborative sources of textual data. Nonetheless, all this information, in the form of language units and related linguistic attributes, requires a proper method for representation, querying and analysis while taking into account the attribute of each unit within its local and global context. With these requirements in mind, researchers have used language networks1 since a long time [START_REF] Quillian | Semantic memory[END_REF] to model linguistic complex data. Indeed, a complex network allows us to have a look at the information from both local and global perspectives. However, it is not until recently, with the growth of computational power, that we are able to exploit linguistic networks at a larger level. In short, in order to extract useful knowledge from a linguistic network we need a representation that can combine diverse kinds of language attributes (and the relations among them), as well as facilitate the application of graph analytic algorithms.

The characteristics of a linguistic network varies according to the necessities of the natural language processing (NLP) task we are trying to solve. Still, we can identify two general aspects: the type of network used to hold the information and the algorithms applied on it to extract new insights. In this context, the work presented in this article has two goals: [START_REF] Quillian | Semantic memory[END_REF] review recent linguistic network models used to resolve semantic NLP tasks, and [START_REF] Choudhury | The structure and dynamics of linguistic networks[END_REF], propose a novel linguistic network that addresses some of the structural limitations of the works studied.

Accordingly, we first provide a simplified and organized state of the art of linguistic networks in the domain of Word Sense Disambiguation and Induction (WSD and WSI). As we will find out, relatively few approaches go beyond using classic lexical co-occurrence information as a source to discriminate contexts and different senses of a word. It is our intuition that by leveraging different types of linguistic relations we can obtain more pertinent results on a given semantic task. In this sense, we propose a network model that is able to hold diverse kinds of language information and allow for a simple manipulation of the data contained in it. Using this schema, we perform a proof of concept to illustrate the advantages of using such structures for the word sense disambiguation and word sense induction tasks. In that respect, it is not our goal to compete against the best systems for WSD and WSI described in the literature and which require tuning parameters most of the time. Our aim is rather to show that using linguistic networks enables us to encode more fine-grained language information that we could leverage to better address NLP tasks in comparison to basic lexical co-occurrences information.

We organize the paper as follows, in Section 2 we introduce basic concepts and in Section 3 we review network-based approaches to semantic-similarity tasks specifically from a graph-centric view. In Section 4 we propose a linguistic network based on hypergraphs. Next, we show the potential utility of such network in Section 5. Finally, we present our conclusion and future research in Section 6.

Background

Below we will delineate the preliminary concepts used throughout the rest of our paper. We introduce the concept of linguistic network (or language network) as well as the semantic tasks we are interested in.

Linguistic Network We define a Linguistic Network (LN) as a modelization of the human language in terms of a graph structure. Usually, textual entities (e.g., letters, words, phrases) are linked together by means of grammatical or semantic relations [START_REF] Choudhury | The structure and dynamics of linguistic networks[END_REF]. A network structure allows us to study the characteristics of said relations in order to extract useful knowledge from them.

In this work we focus on two aspects of a linguistic network: the type of LN, with regards to its contents, as well as the graph algorithms used over the network to solve a given NLP task. In this work we concentrate on wordsemantics related tasks. Among these tasks, two that are highly popular are word sense disambiguation and word sense induction and.

Word Sense Disambiguation (WSD) Given a target word tw, a context ct, and a set mn containing possible meanings for tw, the goal of WSD is to determine which signification corresponds to tw from the set mn according to the context ct. This task is usually solved leveraging a dictionary or thesaurus that establishes semantic links between word senses. This type of resource is also known as Lexical Knowledge Base (LKB) 2 . A LKB can be defined as an ontology that relates words according to their semantic relation. Two quintessential examples of a LKB are the Wordnet semantic dictionary [START_REF] Miller | Wordnet: A lexical database for english[END_REF] and BabelNet [START_REF] Navigli | Babelnet: Building a very large multilingual semantic network[END_REF].

Word Sense Induction (WSI)

The methods employed to solve WSD are generally unsupervised, that is, they do not require an annotated corpus to infer the appropriate sense for a given word. Nonetheless, a certain level of supervision can be distinguished on these approaches. Indeed, LKBs are, most of the time, built using human supervision. In order to circumvent this constraint, researchers have devised fully unsupervised techniques to automatically find the senses mn of a word tw by leveraging a background corpus. Once the senses have been induced, these approaches perform WSD. This task is named Word Sense Induction (WSI).

State of the Art

According to their objectives, we can consider two types of contributions in the linguistic-network literature [START_REF] Choudhury | The structure and dynamics of linguistic networks[END_REF]: on the one hand, there are those approaches that investigate the nature of language via a graph representation, and on the other hand, we find those that propose a practical solution to a given NLP problem.

In that regard we can cite the following survey papers [START_REF] Navigli | Word sense disambiguation: A survey[END_REF][START_REF] Navigli | A quick tour of word sense disambiguation, induction and related approaches[END_REF][START_REF] Agirre | Random walks for knowledge-based word sense disambiguation[END_REF][START_REF] Mihalcea | Graph-based Natural Language Processing and Information Retrieval[END_REF].

This article focuses on the latter type of approaches. Moreover, we pay particular attention to two aspects of a given network-based technique: (1) the characteristics of the linguistic data within the network, and (2), the algorithms used to extract knowledge from it.

Once the LN modelization concept and the concerned tasks are introduced, we move on to the content of our literature review. As we defined before, a LN comprises two main characteristics: the type of language network and the nature of the algorithms used in each network.

Types of Linguistic Networks

In the following paragraphs we introduce the general categories of LNs according to their type of content and relations. We will introduce these categories as well as the approaches that make use of them.

In [START_REF] Mihalcea | Graph-based Natural Language Processing and Information Retrieval[END_REF] they define four types of LNs: co-occurrence network, dependencies network, semantic network and similarity network. Meanwhile, from a deeper linguistic point of view, [START_REF] Choudhury | The structure and dynamics of linguistic networks[END_REF] defines broader categories, each having several sub-types.

The main difference (in our context) between both definitions lies in the separation of categories. In [START_REF] Choudhury | The structure and dynamics of linguistic networks[END_REF], they conflate syntactic-dependency and co-occurrence networks into the same category: word co-occurrence networks. Similarly, they join semantic and similarity networks together and place them inside a broader category of lexical networks. The third family defined concerns phonological networks which is out of the scope of this paper. In this work we will explore five categories of linguistic networks: semantic, lexical co-occurrence, syntactic co-occurrence and heterogeneous networks. The following sections will elucidate what each kind of network represent, we will mention works that employ this kind of networks and also list the main methodology differences that variate from one approach to another.

Semantic Networks A Semantic Network (SN) relates words, or concepts, according to their meaning. The classical example of a SN is the renowned knowledge base Wordnet. This network, which serves also as an ontology, contains sets of synonyms (called synsets) as vertices and semantic relations as their edges. Typical semantic relationships include synonym-antonym, hypernym-hyponym, holonym-meronym. However, other semantic similarities can be defined. The edges are usually not weighted, although in some cases certain graph similarity measures may be used.

Word sense disambiguation is indeed a task usually solved using semantic networks, specially Wordnet (and to lesser extent, BabelNet) [START_REF] Mihalcea | Pagerank on semantic networks, with application to word sense disambiguation[END_REF][START_REF] Sinha | Unsupervised graph-basedword sense disambiguation using measures of word semantic similarity[END_REF][START_REF] Tsatsaronis | Word sense disambiguation with spreading activation networks generated from thesauri[END_REF][START_REF] Navigli | Graph connectivity measures for unsupervised word sense disambiguation[END_REF][START_REF] Agirre | Personalizing pagerank for word sense disambiguation[END_REF] Given an input text with a set of ambiguous target words to process, these approaches follow a two-step algorithm:

1. Link target words (usually nouns, without stop-words and functional words)

with their corresponding sense (or synset in the case of Wordnet-like dictionaries) and extract their vertices and edges into a new, smaller, SN. 2. Apply a node ranking technique, usually a random walk based method, and select, for each ambiguous word in the input text, its top ranking synset node as the correct sense.

Lexical Co-occurrence Networks Most co-occurrence based intuitions in NLP have their origin in the distributional hypothesis [START_REF] Harris | Distributional structure[END_REF]. The idea is resumed by the well know phrase "a word is characterized by the company it keeps" [START_REF] Firth | A synopsis of linguistic theory[END_REF]. That is to say, words with similar neighbor words (or contexts) tend to be semantically similar. This intuition has been exploited deeply in NLP. One of the most effective ways of representing word co-occurrences is by means of a graph structure. Indeed, this kind of graphs are the central column of a Lexical Co-occurrence Network (LCN). In these structures, nodes represent words and edges indicate co-occurrence between them, i.e., two words appear together in the same context. A context can vary from a couple of words (before or after a given word) to a full document, although it is usually defined at sentence level. The edges' weight represent the strength of a link and is generally a frequency based metric that takes into account the number of apparitions of each word independently and together.

To solve a task in a completely unsupervised way, researchers generally use this kind of networks instead of LKBs. It is then natural that word sense disambiguation approaches leverage lexical co-occurrence networks, and in return, the distributional hypothesis, to automatically discover senses for a given target word. That is why WSI methods [START_REF] Vronis | Hyperlex: lexical cartography for information retrieval[END_REF][START_REF] Klapaftis | Uoy: A hypergraph model for word sense induction & disambiguation[END_REF][START_REF] Navigli | Inducing word senses to improve web search result clustering[END_REF] are tightly related to LCNs. The cited works use a LCN as described before while other works such as [START_REF] Navigli | Graph connectivity measures for unsupervised word sense disambiguation[END_REF][START_REF] Qian | Word sense induction using lexical chain based hypergraph model[END_REF] represent the co-occurrence by means of a hypergraph schema. In short, a hypergraph structure is a graph generalization where an edge (called hyperedge) can link multiple vertices per edge and thus it is able to provide a more complete description of the interactions between several nodes [START_REF] Estrada | Complex networks as hypergraphs[END_REF].

WSI systems generally perform four steps. Given an input text with a set of target words and their contexts (target words must have several instances throughout the document to cluster them), the steps are the following:

1. Build a LCN, assigning tokens as nodes and establishing edges between them if they co-occur in a given context (usually if they both appear in the same sentence). 2. Determine the weights for each edge according to a frequency metric. 3. Apply a graph clustering algorithm. Each cluster found will represent a sense of the polysemous word. 4. Match target word instances with the clusters found by leveraging each target word context. Specifically, assign a cluster (a sense) to each instance by looking at the tokens in the context.

Syntactic Co-occurrence Networks A Syntactic Co-occurrence Network (SCN) is very similar to a LCN in the sense that both exploit the distributional hypothesis. Nonetheless, SCNs go further by leveraging syntactic information extracted from the text. There are two main types of syntactic information both represented as tree structures: constituency-based parse trees and dependency-based parse trees. Briefly, the former structure splits a phrase into several sub-phrases. In this way we can get a glimpse of the role of each word inside a phrase. The latter tells us about the relationships existing between words in the phrase. SCNs employ, most of the time, dependency trees to create a graph that relates words according to their syntactic relations. In the case of [START_REF] Hope | Uos: A graph-based system for graded word sense induction[END_REF], a graph is built using syntactic dependencies. It is used to perform WSI using a very similar approach as those systems using LCNs. We note that approaches based on SCNs are scarcely used in WSD or WSI systems, and therefore they are an interesting research avenue to explore.

4 Heterogeneous Linguistic Network: Our Proposal

In the previous section we have mentioned two disadvantages found in the language networks covered in Section 3. Namely, the lack of syntactic information and the homogeneous nature of the networks. In this section we propose a language network that, at this point of our research, addresses both of these concerns. Building upon previous linguistic representations [START_REF] Klapaftis | Uoy: A hypergraph model for word sense induction & disambiguation[END_REF][START_REF] Liu | A hypergraph-based method for discovering semantically associated itemsets[END_REF][START_REF] Qian | Word sense induction using lexical chain based hypergraph model[END_REF], our model is based on the use of a hypergraph. Hypergraphs have been employed in the literature to model complex systems. Their single most important difference, being able to relate more than two vertices at the same type, allows for a better characterization of interactions within a set of individual elements (in our case, words) [START_REF] Heintz | Beyond graphs: toward scalable hypergraph analysis systems[END_REF]. Indeed, our hypergraph modelization integrates four types of relations between tokens: sentence co-occurrence, part-of-speech tags, words' constituents data and dependency relations in a single linguistic structure. We group words together according to the these features.

Formally, a hypergraph is a generalization of a graph defined as a tuple G = (V, E), where the vertices V = {v 1 , v 2 , ..., v n } represent the set of nodes and E = {e 1 , e 2 , ..., e m } the set of hyperedges which contain links between one or more vertices [START_REF] Berge | Graphs and Hypergraphs[END_REF].

In our case, the set of tokens in the corpus are the set of nodes V , and the set of hyperedges E represent the relations between nodes according to different linguistic aspects. Each hyperedge may be one of three types: noun phrase3 constituents (CONST ), dependency relations (dep), or sentence context (SEN ). We consider that a token v belongs to a hyperedge of type NP or SEN if the token appears in the same noun phrase or in the same sentence. A token v belongs to a hyperedge of type DEP if it is the dependent of a certain dependency relation coupled with its corresponding head (or governor). The hypergraph can be represented as a n × m incidence H matrix with entries h(i, j) = N (v i , e j ) where N (v i , e j ) is the number of times v i ∈ e j occurs in the corpus.

We illustrate our hypergraph incidence matrix with the following example phrase: The report contains copies of the minutes of these meetings.. We tokenize the phrase, keeping all the words, and we lemmatize and parse it to obtain both constituency and dependency trees.

The constituency tree of the example phrase is shown in Figure 1. The sentence, as well as each noun phrase (NP) node is identified by a number. We can observe that this phrase is composed by five noun phrases (NP) and one verb phrase. Meanwhile, some of the NPs are formed by other kind of phrases, depending on the grammar production rule used to build each one of them. As is usual in this kind of structures, there is a one to one relation between the number of tokens in the sentence and the number of leaves in the tree. The dependencies of the example phrase are shown in Table 1. They indicate the syntactic relation between the governor of a phrase and a dependent. In these relations' examples, the head is the first token to appear followed by the dependent word.

From both of these types of information we can build a hypergraph representation as stated before. The incidence matrix is illustrated in Table 2. For brevity, we only show nouns as well as only the first three noun phrases and the nominal subject (nsubj ) and direct object (dobj ) dependency relations. Looking at the table, we can therefore infer that the word copies appears in two hyper- edges of type CONST: NP 2 , which is built from a NP, and two prepositional phrases (PP). Also, we see that it is part of NP 3 , which indicates a plural noun (NNS). Regarding the syntactic dependency hyperedges, the word copies appear in the dobj contains column which indicates the copies was indeed the direct object of the verb contains, Finally, we can know that copies appeared in the same sentence S 1 as the other four noun words.

Table 2. Incidence matrix of the example phrase hypergraph modelization. In this section we carry out a proof of concept experiment to verify the potential of our proposed network modelization. We use the task of word sense induction and disambiguation as an application context for our procedure. As stated before, we do not aim to create a system able to beat the reviewed WSD or WSI techniques. Instead, our goal is to show that using other kinds of language information we can improve the results of those obtained while using classic lexical co-occurrence, and thus emphasize the utility of using diverse linguistic information, in our case through a language hypergraph structure.

Methodology

The task is the following: we are given a document d with several target words tw and multiple paragraph instances for each tw. We consider each of these paragraphs as the context ct of a target word tw. The goal is to first automatically determine a set of senses for a given tw (WSI), and then assign one meaning to each of its instances (WSD).

As described before, WSI (including WSD) is usually solved following four steps: (1) creation of a linguistic network, (2) determine the level of similarity between nodes within the network, (3) cluster nodes together, thus creating individual senses, and (4) assign a cluster (sense) to each instance of a target word in the input document.

In our process, we follow a similar approach to those used in [START_REF] Vronis | Hyperlex: lexical cartography for information retrieval[END_REF][START_REF] Klapaftis | Uoy: A hypergraph model for word sense induction & disambiguation[END_REF]. In short, these methods build a network of lexical co-occurrence with a background corpus and then exploit the real-world characteristics of said networks by theorizing that there are certain important nodes (called hubs) that carry a significant role among the words contained in the network and therefore may represent, coupled with their neighbors, a sense for a given target word.

In our approach, we generate a network for each tw and the high-degree nodes found inside this network ideally represent a tw sense. As presented in the previous sections, we use a hypergraph structure, similar to the one used in [START_REF] Klapaftis | Uoy: A hypergraph model for word sense induction & disambiguation[END_REF] Creation of the linguistic network In the previous sections we worked with the English Wikipedia as background corpus to build and model our proposed linguistic network. Given the large size of Wikipedia, and to iterate faster our experiments, we decided to change the corpus to one with a more manageable size. We use the Open American National Corpus (OANC) [START_REF] Ide | The american national corpus first release[END_REF] as background document collection to build a hypergraph network G H following our proposed model. The OANC includes texts from several domains and encompasses 11,406,155 words. We split the documents in the corpus in sentences, then we tokenize and parse them with Stanford's CoreNLP [START_REF] Manning | The Stanford CoreNLP natural language processing toolkit[END_REF]. As described before, the dependency and constituency tree are used to build the hypergraph: words are depicted by nodes, and they may exist inside any of the three different types of hyperedges defined: sentence, noun phrase or dependency contexts. If any hyperedge is repeated through the corpus, we increment a counter and keep the number of apparitions instead of adding redundant columns to the hypergraph incidence matrix.

At each step, that is, for each tw in the input document, we extract a subgraph G tw from G H that contains all the words that appear together with tw (line 2), whether by lexical or syntactic co-occurrence. The tw is removed from G tw . In this approach we focus specifically on dependency relations and lexical co-occurrence.

Computing similarity between nodes In order to computationally treat G tw , we first induce a bipartite graph B tw = (U, W, E) from G tw (line 3). The set of left nodes U represent words and the set of right nodes W depicts the membership to a given hyperedge. Thus, we have as many nodes in W as we had hyperedges in G H .

We compute the Jaccard index between each node n i , n j ∈ U as Jaccard(i, j) =

|N (i)∩N (j)| |N (i)∪N (j)| , N (
j) being the neighbors of n j . We use this metric in order to build a |U | × |U | similarity matrix S tw (line 4). We induce from S tw a new filtered hypergraph incidence matrix F tw (line 5), which contains word nodes as rows and columns as hyperedges. Each of these hyperedges represent a set of words that are deemed similar between them according to their Jaccard index value, which must be equal or higher than an assigned threshold th 1 .

Clustering words together Once the incidence matrix F tw is built we can proceed to induce senses for a target word by clustering words (vertices) together. First, we calculate the degree of each node n i ∈ F tw . The degree of a node is simply the number of hyperedges it is incident in. Nodes are sorted in descending order and evaluated one by one. Each node is considered as a candidate sense hub (line 6). We accept or reject a node n ∈ F tw as a sense carrying word according to two thresholds: th 2 and th 3 . The former (line 9) is the minimum degree a node must have, which is automatically determined by taking into account a node if it is degree is superior to the 85th percentile among all the calculated degrees. The latter (from line 11 to 17) sets a minimum limit to the average of the Jaccard similarities between each pair of neighbors of node n ∈ F tw , within each hyperedge n belongs to. Formally, for a node n, we define the average Jaccard measure as:

AvgJaccard(n) = 1 |hedges(n)| h∈hedges(n) i∈h j∈h;i =j Jaccard(i, j)
|h| where hedeges(n) is the set of hyperedges n is incident in and its cardinality is defined as |hedges(n)|. |h| is the number of nodes in hyperedge h.

If node n satisfies both thresholds th 2 and th 3 , it is deemed as a sense purveyor and all its neighbors (words that appear in the same hyperedges as n) are conflated into a single set representing a tw sense. This new sense is added to SoS tw (line 17). The sense set is then removed from F tw .

The process is repeated until no more nodes satisfy both boundaries. When the process is complete, we obtain a set of senses SoS tw where each set contains words that ideally represent a unique meaning for each target word.

Sense assignation

The assignation of a sense consists in looking at each tw instance represented by a context ct and simply determining which sense s in SoS tw shares the highest amount of words with ct. The sense s is thus assigned to that instance. If two senses in SoS tw share the same amount of words with ct, one of them is randomly chosen. This operation is repeated for each instance of each target word.

Experiments and Results

The objective of this proof of concept is to show the advantages of using syntactic co-occurrence information compared to simple lexical co-occurrence. To this end, we solve the word sense induction and disambiguation tasks using the method described in the previous subsection. We create two independent systems: lex, which uses lexical co-occurrence hyperedges, and dep, which employs syntactic dependency hyperedges.

As evaluation dataset, we employ the data provided for Task 02 of Semeval-2007 [START_REF] Agirre | Semeval-2007 task 02: Evaluating word sense induction and discrimination systems[END_REF] which evaluated word sense induction systems. The data consists on 100 target words4 (65 verbs and 35 nouns), each target word having a set of paragraph contexts where it appears. From the available performance assessing techniques, supervised and unsupervised, we are interested in the unsupervised evaluation, which is rated using the F-score produced by an evaluation script. We also modify it to obtain also the precision and recall measures to build a precision-recall curve.

Each type of language information has its own characteristics. The subnetwork formed by sentence hyperedges tends to have a much smaller number of nodes (words) than those of the dependency type. This make sense as sentences usually contain a few words, meanwhile a dependency hyperedge may incorporate upwards to hundreds of words that are related to a word by the same dependency relation. These characteristics affect the similarity between vertices and thus drove us to set the threshold (th1 and th2 ) values for lex and for dep in function of the percentile of the node's degree and similarity values distributions, respectively. This leaves only one threshold left, th 3 . We experiment with two different ranges of values, one for each system. For dep we set the range [0.3, 0.65] with a step of 0.05. For lex we set [0.01, 0.08] with a step of 0.01. These ranges were chosen experimentally with two constraints in mind: (1) lower threshold values usually gave the same results5 as those already included in our ranges, and (2) higher threshold values forced the system to either give only one sense per word (resulting in the most frequent baseline), or even worse, not accepting any sense, thus having a null solution. Again, we evaluate our systems by means of the (unsupervised) F-score and a precision-recall curve which provides a deeper analysis of the performance of each system while considering the variation of threshold th 3 .

The F-score of both systems, and the average number of clusters (senses) produced, is shown in Figure 2. Indeed, in our experiment, the dependency based model dep preformed better than lex using classic lexical co-occurrence. We include the result of the uoy system [START_REF] Klapaftis | Uoy: A hypergraph model for word sense induction & disambiguation[END_REF] as a similar-method benchmark. In uoy, two background corpora are also used to build a linguistic network of lexical co-occurrences. One of the corpus is the same as the one we used to evaluate. This allows their system to induce the exact senses used in each target word instance. While this is a practical idea, we, by using a large, multipledomain corpus, are able to induce word senses that may not even be used in the Semeval dataset. Concerning the thresholds, we use percentiles to automatically adapt to the characteristics of the hyperedges, as the lexical and dependency co-occurrences hyperedges behave differently within the linguistic network.

In Figure 3 we appreciate that even while using different threshold values, we achieve, in general, better recall and precision by using syntactic dependencies. It must be noted that this particular Semeval task was dominated by the most frequent sense with an F-score of 80.7, assigning an average of one sense per target word. Our solutions assign an average of 1.257 and 1.200 for lex and dep respectively. Based on our proof of concept experiment, we confirm that using syntactic dependencies in order to disambiguate word senses improves can improve the results when compared with regular lexical co-occurrence approaches.

Conclusion and future work

In this paper we analyzed the state of the art of linguistic network-based approaches to semantic similarity task from a graph-centric point of view. We reviewed the techniques in terms of its graph characteristics, from their structure to the algorithms employed. Among the literature covered, certain non-explored research paths were identified, namely the lack of syntactic data on the networks employed, and therefore, a homogeneous network nature that only allows for relations of a unique type.

We addressed with the proposition of a hypergraph linguistic model that is able to hold heterogeneous language information. We believe that this structure allows the integration multiple kinds of information and has vast potential in terms of which algorithms it can be used with. Our model was tested in a word sense induction proof of concept experiment and found interesting and encouraging results. Again, we note that the approach proposed to solve word sense disambiguation and induction is a proof of concept and as encouraging as the results are, we still need to improve the system in order to compete with the best solutions in the state of the art.

As future work, we are currently extending our algorithm to properly combine the different types of information within our model. We would like to test other kind of graph inductions (instead of transforming the hypergraph into a bipartite graph), or even better, use the incidence matrix of the hypergraph to calculate custom similarity metrics. In this same context, we believe that a deep analysis on the semantic meaning of different types of similarities (and their magnitudes) between words is needed to better determine which metric to use in a specific context. Finally, we also plan to address other NLP domains with our hypergraph model, notably information extraction problems.

Fig. 1 .

 1 Fig. 1. Constituency-based tree of the phrase The report contains copies of the minutes of these meetings.

5

 5 Proof of concept: Word Sense Induction and Disambiguation

Table 1 .

 1 Dependency relations of the example phrase.

root(root, contains)

det(minutes, the) det(report, The) nmod(copies, minutes) nsubj(contains, report) case(meetings, of) dobj(contains, copies) det(meetings, these) case(minutes, of) nmod(minutes, meetings)

  Algorithm 1: Pseudo-code of our WSD/WSI network-based approach Input: A set tw set = {tw 1 , tw 2 , ..., tw n } of target words. A background linguistic network G H . Filtering thresholds th 1 , th 2 , th 3 Output: A set SoS tw of senses for each target word 1 foreach target word tw in tw set do 2 G tw = extract subgraph(G H , tw); tw = induce hypergraph(S tw , th1 );

	3	B tw = induce bipartite graph(G tw );
	4	S tw = sim matrix(B tw );
	6	candidate hubs = sort(degree(F tw ));
	7	SoS tw = [ ];
	8	foreach candidate hub in candidate hubs do
	9	if degree(candidate hub) < th2 then
	10	continue;
	11	candidate hyperedges = get hyperedges(candidate hub, F tw );
	12	candidate avg j accard = 0;
	13	foreach hyperedge in candidate hyperedges do
	14	candidate avg jaccard += get avg jaccard(hyperedge);
	15	end
	16	if candidate jaccard > th3 then
	17	SoS tw .add(get words(candidate hyperedges));
	18	F tw = F tw \ candidate hyperedges;
	19	end
	20	return SoS tw
	21 end

5

F

  Precision-Recall curve for lex and dep systems. To improve visibility, we focused the scale on the curves.

					0.75
	System dep lex uoy	Nouns FSc. 80.6 79.5 65.8	Nb. Clusters 1.200 11.28 1.257	Precision	0.74 0.74
	Fig. 2. Best F-scores obtained for both our methods on Task 02 of Semeval-		0.94	0.96	0.98	1
	2007, using lexical (lex) and syntactic			Recall
	dependency (dep) co-occurrences.
				Fig. 3.

In general, we use the term network and graph interchangeably. However, in some cases we consider a network as being represented by a graph structure, among other properties.

We note that in our context, a LKB has the same characteristics of a semantic linguistic network. Thus, we employ both terms interchangeably.

In this work we consider only noun phrases (NPs). Still, we can easily add other type of phrase chunks.

We note that for this experiment we worked solely with nouns.

Still, some of the values used produced equal results and thus are not visible in Figure3.