Reasoning with similarities is seen as one of the crucial steps in Artificial Intelligence. Turing, in his paper Computing Machinery and Intelligence [1], suggested that a machine having passed the so-called test, should appear as a human 70% of the time after five minutes of conversation. From Joseph Weizenbaum, and his seminal proposal Eliza [2] in 1966, until the last generation of programs Jabberwacky and Cleverbot developed by Rollo Carpenter [3] during the last decade, the treatment of similarities attracted a lot of interest to tackle this issue. Formerly, one classical way was to deal with Natural Language Processing (NLP), focusing on syntactic similarities through a case-based reasoning machinery.
These last years, the Semantic Web [4] has given complementary resources in terms of knowledge bases, offering new standards to deal with lexical databases. The semantic dimension of similarities is now guided by well-established and moderated repositories of knowledge including ontological layers (see [5]), but few attempts was performed to combine the classical NLP-based technologies together with semantic web infrastructures in order to analyze the limits of such interactions (see for example [6]). Moreover, if some methods were also proposed to compute global scores of similarities between two phrases based on local semantic similarities of their components (see [7,8]), we remark that the usual way to output a set of similarities between a phrase and a set of phrases is an ordered list of items (e.g. the popular search engines), and very few approaches were proposed in the literature in order to screen the similarity scores in different ways (see [9,10]).
In this paper, we present a logical and visual framework to represent and reason with textual relatedness measures guided by ontologies. In order to bridge the gap between natural language and ontologies, we introduced a fragment of Description Logic (DL), underpinning the well-known lexical database WORDNET [11]. With this fragment, we can properly redefine some relatedness measures historically used in taxonomies. To gain place, we only introduced here the path length relatedness measure denoted plr. Nevertheless, other historical similarity measures considering the maximum depth in taxonomy (see lch in [12]), the depth of the least common subsumer (see wup in [13]) or the supported information content (see jcn in [14] and lin in [15]) have also been integrated in this framework.
After some preliminaries to introduce our logical framework in section 2, we describe in section 3 both our computation and an interface to screen the similarities between a phrase and a set of phrases. Finally, in section 4 we present an experimental validation to confront the theoretical similarities with some experimental ones.
DL is a well-known family of formal knowledge representation models. Semantic languages used on the web to share knowledge (e.g. RDFS [16], OWL [17] and OWL2 [18]) have all some direct underpinning logics that are fragments of DL. The core interpretation of a DL in first order logic was given by Baader and Nutt in [19] as follows: Definition 1. Let C the set all the atomic concepts and R the set all the atomic roles, an interpretation I is an ordered pair (∆ I , • I ) such that: -∆ I is the domain, i.e. a non-empty set of individuals, -• I is the interpretation function which maps:
-each atomic concept A ∈ C to a set A I ⊆ ∆ I , -each atomic role r ∈ R to a binary relation r I ⊆ ∆ I × ∆ I .
In this paper, we chose to introduce FLH ± defined in Definition 2 as an extension of AL [20] using transitivity and hierarchy for roles but removing negation, intersection, limited existential and value restrictions. Definition 2. Let an interpretation I, {A, B} ⊆ C and {r, s} ⊆ R
As redefined in [19], a Terminology Box or a TBox in DL is a finite set of axioms, with no symbolic name (equality whose left-hand side is an atomic concept), which is defined more than once. Princeton's WORDNET is a lexical database for the English language [21]. A decade after the creation of this database, van Assem [22] proposed a conversion of WORDNET in OWL. Example 1 presents a sample of TBox underpinning WORDNET in OWL introducing particularly the concept SYNSET 4 and the role h5 .
In the terms of Baader and Nuts [19], an Assertional Box or an ABox is a specific state of affairs of an application domain in terms of concepts and roles. Example 2 depicts a graph representing a sample of ABox underpinning WORDNET in OWL where n represents the individual root of all the individual nouns present in WORDNET, the edge represents synsets (e.g. SYNSET(Astract)) and the directed arcs represent the hyponym relation assertions between two individuals (e.g. h(Attribute, Abstract)). Note that the WORDNET Abox is partitioned in different set, dealing with different parts of speech (nouns, verbs, adjectives and adverbs).
n Astract Relation Attribute
The idea of computing relatedness measures between concepts occurring in a taxonomy is an old issue (see [23]). Few approaches (see [24,25]) have described the common relatedness measures through a DL formalism. According to Rada [26], a path length is founded on a node-counting scheme concerning the smallest specified role counting between two individuals. Given an interpretation and two individuals, we redefined the shortest path length function denoted L as follows:
Note that if a practitioner deals with the transitive closure of the WORDNET ABox, a min max operator may be used due to the transitivity of the relation h. Example 3 lists the shortest path length between individual nouns introduced in Example 2. We denote v the individual root of all the verbs. The ABox being partitioned, note that no verb is involved in a hyponym relation with a noun (and vice-versa).
Example 3 (Shortest Path Length).
As reintroduced by Pedersen [27], the path length based relatedness score is equal to the inverse of the shortest path length between two concepts. Naturally, it is inversely proportional to the number of nodes along the shortest path between the synsets. The path length based relatedness denoted plr is defined as follows:
If no path exists (e.g. between a verb and a noun) we consider that L tends to ∞, and then the path length based relatedness score approaches 0. The highest possible score occurs when the two synsets are the same, in which case the score is 1.
plr(Relation, Abstract) = 1/2 plr(Relation, Attribute) = 1/3 plr(P hysical, P hysical) = 1 plr(P hysical, v ) → 0
In the next section, we present our method to compute similarity scores between two phrases based on the local semantic similarities of their components (e.g. plr), moreover we depict a way to screen them through a graphical user interface.
The finality of our framework is to screen similarity scores between one phrase and a set of phrases. We chose to investigate the way transforming a phrase in a set of triples before performing the computation of similarities. We selected the API REVERB, an information extractor for massive corpora (working without pre-specified vocabulary). In [28], REVERB was judged with a extraction precision of 0,8 or higher in at least 30% of the time, substantially outperforming others extractors like TEXTRUNNER (see [29]) and WOE (see [30]). Formally and for the following, we can see a phrase p as a set of triples {t 1 , . . . , t n } where t l = t 1 l , t 2 l , t 3 l with t k l ∈ ∆ I . Thereafter, we define the global score between two phrases as the maximum of the averages of similarities between the components from the triples (average of similarities between subjects, objects, and complements). Moreover, we arbitrary avoid to take into account two kinds of scores: scores of 0, it is the case when at least one entry is not present in the lexical base of WORDNET (see section 2), and the score of 1 (similar strings) only if the individuals in comparison are present in a stop words set denoted θ.
Definition 5. Let θ and two phrases p, q, the Score of similarity is defined as follows:
with ti ∈ p, tj ∈ q, k ∈ [ [1,3]], s ∈ {plr, lch, wup, jcn, lin} and S the upper case of s.
To support this computation, we used the STANFORD CORENLP API [31] to perform the lemmatization of the components from the triples. The similarities calculus of the lemme were performed by WORDNET:SIMILARITY (developed by Pedersen et al. in [32] and redesigned in Java by Shima [33]).
All this treatment is included in the framework LooPings 6 (Lexical and ontological observations to Plot ingathering similarities). Looking at the system description of Fig. 1, LooPings is decomposed in several modules:
INPUT takes a phrase and some parameters (e.g. local measure, stop words list, etc.). LIBRARIES comprise REVERB, STANFORD CORENLP and WS4J API (bundled with WORDNET). CORE manages the computation. OUTPUT is devoted to screen and to plot the similarity scores.
One of the most challenging steps is the connection between the NLP APIs RE-VERB and WS4J. The main aspect that made this compatibility a little immature is the fact that REVERB can output expressions (several raw words) while WS4J accepts only a single element as input (a lemme or an expression of lemmes linked themselves in one string by underscores). Then, we had to perform a treatment from our raw phrases, following some basic heuristics, as described through the example below:
What can we learn from the neural networks of C.elegans to understand human brains?
The outputted triple is we,learn from,the neural networks of C.elegans .
we,learn from,the neural network of C.elegans 2. Chunking:
we,learn from,the neural network C.elegans 3. Stop words removing:
we, learn, neural network C.elegans 4. Cutting:
we, learn, neural network ; we, learn, C.elegans
Note that during the step of the removal, stop words were never removed from the triples when it involved an empty set for one component. Fig. 2 presents the interface of LooPings, where practitioners can visualize and confront the semantic similarities. Note that this framework is oriented to integrate queries and SPARQL [34] interpretations allowing a possible integration of other semantic web technologies. The similarity scores are represented on a segment [0,1].
The last section is dedicated to the confrontation between the theoretical scores with some experimental ones.
In order to deal with real queries, we used STACK EXCHANGE API allowing us to extract from a website some structured data (in JSON format) about different questionand-answer themes. The total number of available queries for the Cognitive Science section of STACK EXCHANGE website was 1245, we decided to extract the 1200 first queries (w.r.t. the extraction order), from each of them we stored ids (from 1 to 4697) and queries. Formally, a query referenced by an id is denoted q id , moreover we call series S j a set of queries: S j ⊆ {q id |1 ≤ id ≤ 4697}. A tricky aspect was the fact that REVERB outputted nothing in 70.75 percent of queries. So, we decided to divide, the 1200 queries in 12 series of 100 queries, finally giving a median series of 28 queries. Due to space limitation, we will depict in this article only two series (A and B).
Once the extraction was performed, we created an on-line semantic recall based experience. For each series, we designed a witness query. We attached a questionnaire to each series and sent them by e-mail to mailing lists of PhD students. The requirement for participating was to be proficient in English. Questionnaires were designed as follows:
1. Instruction to read carefully a witness query. 2. Instruction to read the series of queries and to check 1, 2 or 3 queries among them, (at least 1, at most 3), the most similar, for the user, to the witness queries. 3. Instruction to partially preorder the selected query(ies).
We succeeded in obtaining 50 volunteers. We gave accumulated marks for queries in each series w.r.t the preorders given by the volunteers. For example if a volunteer selected only one query q i in the series, the accumulated mark for q i was increased by 6, the remaining possible situations are listed below: q i q j q i (+4); q j (+2) q i ∼ q j q i , q j (+3) q i q j q k q i (+3); q j (+2); q k (+1) q i ∼ q j ∼ q k q i , q j , q k (+2) q i q j ∼ q k q i (+3); q j , q k (+1.5) q i ∼ q j q k q i , q j (+2.5); q k (+1)
The maximum mark is translated to an experimental score of 1, after what all the other marks have been transposed in experimental scores by cross-multiplications. As depicted in Fig. 3, we took the PLR score as a reference in order to observe how the other scores behaved following it. Thereafter, we describe what is globally remarkable in the behavior of the theoretical similarities.
-The higher the PLR is, the lower is the difference between scores founded on path lengths (LCH, WUP) and scores founded on information contents (JCN, LIN). -WUP and LIN react in the same way in the case of a sudden increase or drop.
-LIN and JCN scores have a behavior of exponential shape in all the series. Nevertheless, there are some limitations for this framework. We relate for example the case of a saturation. Series B is remarkable by the fact that 5 queries are outputted with the maximal score.
Where could I find psychological experiments tools? The outputted triples were I,find,psychological ; I,find,experiment ; I,find,tool
Here, the systematic presence of two stop words "I" and "find" make that all the similarity scores are 1 iff one of the words "psychological", "experiment" or "tool" is present in one of the extracted triples. This experience showed some natural limits concerning our approach. The main issue seems to be the automatic semantic annotation step (REVERB) and the matching step with WORDNET individuals (through WORDNET:SIMILARITY).
In this paper, we presented both a computational and a visual framework to support semantic similarities guided by ontologies. The first contribution was to redefine some taxonomy-based relatedness measures (e.g. path length relatedness) in a DL fragment (FLH ± ) we introduced. The core of our framework orchestrates the computation of similarity scores supported by REVERB, STANFORD CORENLP and WORDNET:SIMILARITY APIs and interfaces results in graphical way through segments. Moreover, we plotted the behavior of our computations by designing a semantic recall-based experience to confront empirical similarities with the theoretical ones. Some research perspectives for this work would be to extend LooPings in two ways. The first concerns the core of our framework by interpreting scores founded on other relations like for instance the mereology in WORDNET. The second is to integrate other repositories to support the similarities or other frameworks to compute similarities directly on semantic web languages (e.g. using the technology of QAKiS [35]).