Yasser Bourahla
email: yasser.bourahla@inria.fr

Jérôme David
email: jerome.david@univ-grenoble-alpes.fr

Jérôme Euzenat
email: jerome.euzenat@inria.fr

Meryem Naciri
email: meryem.naciri@inria.fr

Measuring and controlling knowledge diversity

Keywords: Knowledge diversity, Diversity measure, Ontology dissimilarity, Diversity control, Entropy

Assessing knowledge diversity may be useful for many purposes. In particular, it is necessary to measure diversity in order to understand how it arises or is preserved; it is also necessary to control it in order to measure its effects. Here we consider measuring knowledge diversity using two components: (a) a diversity measure taking advantage of (b) a knowledge difference measure. We present the general principles and various candidates for such components. We discuss how these measures may be used to generate populations of agents with controlled levels of knowledge diversity.

Introduction

Agents may hold different knowledge. This characterises the knowledge diversity of an agent population. In general, diversity is an important asset. It has been shown, in different contexts, that groups of agents with diverse abilities have better problem solving skills those with high abilities [START_REF] Stirling | A general framework for analysing diversity in science, technology and society[END_REF][START_REF] Hong | Groups of diverse problem solvers can outperform groups of highability problem solvers[END_REF][START_REF] Noble | Collaboration in Social Problem-Solving: When Diversity Trumps Network Efficiency[END_REF]. In an evolutionary context, diversity is considered to have influence on species resilience [START_REF] Reed | Population fitness is correlated with genetic diversity[END_REF].

However, knowing that agents in a population are diverse does not tell how much diverse is the population's knowledge, nor which population has more diverse knowledge. There are various reasons to assess agent populations' knowledge diversity, in particular studies in social modelling. Our own work aims at performing experiments for which we have to measure knowledge diversity [START_REF] Bourahla | Knowledge improvement and diversity under interaction-driven adaptation of learned ontologies[END_REF], because we want to characterise those factors that promote or inhibit diversity, and we have to control knowledge diversity, because we want to characterise its influence on other factors, e.g. robustness. Of course, the diversity that is measured should be the same as that which is controlled.

Hence we are in need of formal knowledge diversity models applicable to formal knowledge representations [START_REF] Goguen | Support for ontological diversity and evolution[END_REF]. In this paper, we focus on both measuring and controlling knowledge diversity in a coherent way. Measuring knowledge diversity may be split in two components: (a) taking advantage of proved diversity measures (b) relying on knowledge-specific structures, and in particular ontology dissimilarities. We show how this can be achieved in an integrated way. We do not provide the single best measure, but instead an ordered set of measures and methods which balance accuracy and complexity. Controlling knowledge may be grounded on such measures.

After stating the problem to solve ( §2), we discuss related work addressing it ( §3). We first provide a concrete example of ontology dissimilarites based on the semantics of the representation language and one specific way to categorise ontologies ( §4). We then introduce a simple way to measure knowledge diversity among agents based on such measures ( §5). This view is refined by segmenting the knowledge space into a priori categories and considering the distribution of agents with respect to these ( §6). Finally, we discuss simple ways to control knowledge diversity among a population of agents with respect to the proposed measures ( §7).

Problem statement

The problem which is considered here is to associate a number to the knowledge diversity of a population of agents (measure) and to associate knowledge to a population of agents so that their diversity is close to such a number (control). We only consider agent populations of the same size.

In principle, a population 𝐴 ∈ 𝒜 of agents is characterised by a set of features 𝐹 . Each 𝑎 ∈ 𝐴 may be considered a point in the space induced by ×𝐹 . In our case, there is a single, but complex, feature 𝑓 which associates to each agent its knowledge (in this paper, we assume that it is an ontology 𝑜 ∈ 𝒪 expressed in a description logic [START_REF] Baader | The description logic handbook: Theory, implementation and applications[END_REF]).

Given an agent population 𝐴, 𝑂 𝐴 = {𝑓 (𝑎); 𝑎 ∈ 𝐴} is the multiset of their ontologies representing the distribution of these ontologies in the population. If one replaces some of these ontologies by others, then this multiset contains 0 or more occurrences of each ontology. The number of different ontologies used by the population is noted |𝑂 𝐴 | and the number of occurrences of ontology 𝑜 in 𝑂 is #𝑜 (also called the abundance of 𝑜). By extension, the cardinal of a distribution 𝑆 is noted #𝑆, e.g. #𝑂 𝐴 = ∑ 𝑜∈𝑂 #𝑜 = |𝐴|. Accounting for diversity may be achieved by defining an index 𝛿 : 𝒜 → R of diversity within a population or a partial order ⪯⊆ 𝒜 × 𝒜 indicating that a population is more diverse than another. Such a diversity measure (𝛿) is an absolute measure within a population. It is also possible to consider diversity across populations. For that purpose, it is sufficient to define an order relation ⪯⊆ 𝒜 × 𝒜 (a population's knowledge is less diverse than another). When a diversity measure 𝛿 has been defined, it is easy to test if 𝛿(𝐴) ≤ 𝛿(𝐴 ′ ) and then decide that 𝐴 ⪯ 𝐴 ′ . It may also be possible to define such an order directly.

Related work

With respect to this problem, three lines of related works may be considered: how this is approached in biology, how this is approached in social sciences, and how knowledge difference is measured in knowledge representation.

Measuring biological diversity. In genetics, diversity is usually obtained by measuring a distance between observed biological objects [START_REF] Aremu | Exploring statistical tools in measuring genetic diversity for crop improvement[END_REF][START_REF] Avolio | Measuring genetic diversity in ecological studies[END_REF]: (DNA) sequences (blast), genes or proteomes. This measures the distance between individual characteristics or possibly species (represented by one representative object or specimen). It has to be generalised to populations. In ecology, many measures of diversity exist [START_REF] Jost | Entropy and diversity[END_REF]. One important line of these is based on the probability of a random individual to be in a category and rely on entropy [START_REF] Jost | Entropy and diversity[END_REF][START_REF] Leinster | Entropy and diversity: the axiomatic approach[END_REF].

Diversity properties

Variety

Balance

Disparity

Amount of diversity

Low

Moderate High

(a) (c) (d) (d) (f) (g) (a) (b) (e)
Figure 1: Presentation of the diversity properties of [START_REF] Stirling | A general framework for analysing diversity in science, technology and society[END_REF] inspired by Figure 1 of [START_REF] Harrison | What's the difference? Diversity constructs as separation, variety, or disparity in organizations[END_REF]. 10 objects are distributed within 5 different categories. Variety considers the number of instantiated categories, balance, the evenness of the distribution, and disparity, the distance between the categories (here taken as their linear position). These dimensions are independent.

Measuring social diversity. Measuring social and human diversity may be a more controversial issue [START_REF] Cheng | How to measure diversity -mathematical theory gives some rigor to discussion of a sensitive social and political issue[END_REF]. Because the number of distinguishing features can be large, it is necessary to reduce these to identifiable categories. This may be achieved by clustering [START_REF] Cooke | Diversity in theory and practice: a review with application to the evolution of renewable energy generation in the UK[END_REF] or by using predefined questionnaires, localising people on a predefined space partition. [START_REF] Stirling | A general framework for analysing diversity in science, technology and society[END_REF] identifies three properties to take into account in measuring diversity (see Figure 1) which may be sumarised by:

• Variety: how many categories are represented? • Balance: how many representatives of each category are there? • Disparity: how different are these categories? [START_REF] Harrison | What's the difference? Diversity constructs as separation, variety, or disparity in organizations[END_REF] provides a different interpretation of disparity as the way an amount of resources is shared among a population depending on the feature values. Although, the latter is important in social sciences, knowledge diversity may be better measured in terms of the three former ones.

Knowledge measures. Concerning knowledge representation, we have the possibility to directly access agent knowledge, like DNA sequences. Hence, it should be possible to measure knowledge diversity [START_REF] Giunchiglia | On knowledge diversity[END_REF]. [START_REF] Morales | Measuring diversity in heterogeneous information networks[END_REF] considers how to compute diversity by extracting data from graphs called 'heteroegenous information networks'. This could be applied directly to RDF graphs. It consists of specifying random walks from which collecting the data and applying an entropy measure on the probability distribution of the collected data. Beyond data, various measures have been developed to compute distances or dissimilarities between knowledge representations. These may be used to assess disparity. In particular, ontology dissimilarities have been designed based on lexical (4.2 of [START_REF] David | Comparison between ontology distances[END_REF]), syntactic [START_REF] David | Comparison between ontology distances[END_REF][START_REF] Mädche | Measuring Similarity between Ontologies[END_REF], vector-space (4.1 of [START_REF] David | Comparison between ontology distances[END_REF]), alignment-based (using explicit relations between ontologies [START_REF] David | Ontology similarity in the alignment space[END_REF]), instance-based [START_REF] Giunchiglia | On knowledge diversity[END_REF], semantic (based on models and closure) [START_REF] Euzenat | Ontology distances for contextualisation[END_REF]. Once measures between individual knowledge are available, classical descriptive statistic measures can be used to aggregate them at the population level.

⊤ 𝑝 𝑞 ¬𝑝 𝑝 ⊓ 𝑞 ¬𝑝 ⊓ 𝑞 ⊥ (A) ⊤ 𝑝 ¬𝑝 ⊥ (B) ⊤ ⊥ (C) ⊤ 𝑞 ¬𝑞 ⊥ (D) ⊤ 𝑞 ¬𝑞 ¬𝑝 ⊓ 𝑞 𝑝 ⊓ 𝑞 ⊥ (E)
We will build on such ontology dissimilarities to assess and control knowledge diversity in a set of agents.

Knowledge dissimilarity and categories

In order to provide precise examples, this section introduces specific ways to measure how far away knowledge representations can be and how they can be grouped into categories. These techniques have been used to measure diversity in the experiments of [START_REF] Bourahla | Knowledge improvement and diversity under interaction-driven adaptation of learned ontologies[END_REF]. However, this example applies on a specific use case, in which knowledge is expressed as description logic ontologies and diversity is based on the semantics of named classes. This is not supposed to be the only answer to measuring knowledge differences. It is an example showing that knowledge can be taken seriously, through its semantics, when measuring diversity. All techniques briefly mentioned in Section 3, from the simplest to the most sophisticated, may be used instead.

Ontologies

Knowledge is expressed through a very limited description logic [START_REF] Baader | The description logic handbook: Theory, implementation and applications[END_REF] based on a finite set of properties 𝑃 ̸ = ∅. For simplicity, the properties are considered Boolean, i.e. an object either has a property 𝑝 ∈ 𝑃 or it does not. The grammar of class descriptions is:

𝐶 := ⊤ | ⊥ | ∃𝑝.⊤ | ∀𝑝.⊥ | 𝐶 ⊓ 𝐷 | 𝐶 ⊔ 𝐷 | ¬𝐶
Constraints on properties may be ∃𝑝.⊤ (noted 𝑝: the class of objects having property 𝑝) or ∀𝑝.⊥ (noted ¬𝑝, the class of objects not having property 𝑝). Named classes are defined through axioms of the form 'name ≡ description'. The set 𝐶(𝑜) of the named classes of ontology 𝑜 contains ⊤ (the class of all objects) and ⊥ (the empty class). We assume that ontologies follow the unique name assumption: two equivalent classes cannot have different names.

Figure 2 presents five simple such ontologies. We use them to illustrate dissimilarity between ontologies and its use to compute diversity among agents.

A B C D E A 0 1 /3 2 /3 1 1 B 0 1 /3 1 1 C 0 1 /3 2 /3 D 0 1 /3 E 0 C B D E A A B C D E A 0 4 /7 2 /7 3 /7 5 /7 B 0 2 /4 2 /4 2 /6 C 0 2 /4 2 /6 D 0 4 /6 E 0

Semantic dissimilarity between ontologies

In [START_REF] Bourahla | Knowledge improvement and diversity under interaction-driven adaptation of learned ontologies[END_REF], the dissimilarity 𝑑 between two ontologies 𝑜 and 𝑜 ′ is defined as:

𝑑(𝑜, 𝑜 ′ ) = 1 - |{(𝑐, 𝑐 ′ ) ∈ 𝐶(𝑜) × 𝐶(𝑜 ′ )|𝑜 ∪ 𝑜 ′ |= 𝑐 ≡ 𝑐 ′ }| 𝑚𝑎𝑥(|𝐶(𝑜)|, |𝐶(𝑜 ′ )|)
i.e. the proportion of named classes in the largest ontology with no equivalent class in the other.

If two ontologies are semantically equivalent, from the standpoint of their named classes, then their dissimilarity will be 0. For instance, consider the ontology 𝐸 of Figure 2 in which ¬𝑝 ⊓ 𝑞 is expressed as ¬(𝑝 ⊔ ¬𝑞), then its dissimilarity to 𝐸 will be 0.

The use of this dissimilarity on the ontologies of Figure 2 is given in Figure 3 (right).

Graph-based dissimilarity between ontologies

It is also possible to derive a dissimilarity from the graph of a subsumption relation across ontologies. The usual way to define subsumption across ontologies would be 𝑜 ⊑ 𝑜 ′ iff 𝑜 ′ ≡ 𝑜∪𝑜 ′ (∪ here denoting the union of the axioms). We may also base it, in the continuity of the previous section on named class equivalence, i.e. an ontology subsumes another if it contains at least one equivalent class for each class of the other. Formally:

𝑜 ⊑ 𝑜 ′ if ∀𝑐 ′ ∈ 𝑜 ′ , ∃𝑐 ∈ 𝑜; 𝑜 ∪ 𝑜 ′ |= 𝑐 ≡ 𝑐 ′
Such a relation can structure 𝑂 in a graph ⟨𝑂, ⊑⟩ as the one featured at the centre of Figure 3. From this graph, the dissimilarity between two ontologies may be the length of the shortest monotonous subsumption chain within the transitively reduced version of ⊑ normalised by the longest such path +1 (with the measure set to 1 when no such path exists). The result is given, for ontologies of Figure 2, on Figure 3 (left).

Semantic categories of ontology

A way to define categories from a set of ontologies is to group equivalent ontologies in one single category. Different predicates (≡) may be used to describes what counts as same ontologies. This may be based on strict syntactic equivalence, on named class equivalence, on equality of the sets of models, etc. This predicate allows us to group ontologies, but may be used for other purposes.

Finally, the dissimilarity defined between ontologies may be applied to the categories themselves. If they are compatible with the way to group ontologies into categories, i.e. ∀𝑜, 𝑜 ′ , 𝑜 ′′ ∈ 𝑂, 𝑜 ≡ 𝑜 ′ ⇒ 𝑑(𝑜, 𝑜 ′′ ) = 𝑑(𝑜 ′ , 𝑜 ′′ ), then the dissimilarities defined above between two categories is the dissimilarity between any members of these categories.

This will be useful to integrate the dissimilarity 𝑑 between ontologies in more sophisticated diversity measures (Section 6).

So far, we have defined simple semantic measures between ontologies and have provided a simple way to group ontologies. This does not tell us what the diversity of a set of agents is.

Measuring diversity as a dissimilarity

It is possible to consider that diversity can be measured by how far appart are the agents' knowledge. The simplest measure would be to consider whether ontologies are different or not. This can be generalised by introducing a dissimilarity between these ontologies introducing gradation in the differences.

Knowledge diversity as different ontologies

The most basic way to assess the diversity of a population is to count the different ontologies agents have. This requires to be able to identify when these ontologies are different. This is achieved with an equivalence predicate (≡) which can be a simple predicate to express that two ontologies are the same (𝑜 ≡ 𝑜 ′ ) or different (¬(𝑜 ≡ 𝑜 ′ )). This equality may be a syntactic or semantic equality, as discussed in Section 4. [START_REF] Reed | Population fitness is correlated with genetic diversity[END_REF]. In fact, it can be any equivalence relation.

Predicates based on a dissimilarity 𝑑 between ontologies and a threshold 𝜃 such that any pair of ontologies below the threshold are considered the same (𝑜 ≡ 𝑜 ′ iff 𝑑(𝑜, 𝑜 ′ ) ≤ 𝜃), is not an equivalence relation in general. These may be used a posteriori to determine clusters of ontologies.

In order to aggregate this difference at the population level, it is possible to simply compute the number of different ontologies with respect to the number of agents:

𝛿 ≡ (𝐴) = |{𝑓 (𝑎); 𝑎 ∈ 𝐴}/ ≡ | |𝐴|
In case of syntactic equivalence, the measure is:

𝛿 = (𝐴) = |𝑂 𝐴 | |𝐴|
Such an indicator 𝛿 = , will provide the highest diversity measure: as soon as two ontologies are different, even slightly, their difference will be counted maximally. A finer view of this may be to compute a dissimilarity between ontologies instead of using a Boolean predicate.

Knowledge diversity as how ontologies are different

It is possible to define a similarity or dissimilarity between agents' ontologies measuring how alike or different they are. Here we consider a dissimilarity 𝑑 : 𝒪 × 𝒪 → R because it is compatible with the boolean measure. It will return 0 when the ontologies are the same.

Any dissimilarity (or similarity) between ontologies can be used, such as those presented in Section 4 and those mentioned in Section 3.

With respect to a population 𝐴, diversity may be assessed by agregating the dissimilarity between their ontologies. This may be achieved with:

• the average dissimilarity 𝛿 𝑑 𝛼 (𝐴) in the population (works as well with predicates); • the median 𝛿 𝑑 𝜇 (𝐴) of the dissimilarities (the set of dissimilarities is a multiset); • the span or diameter of the population, i.e. the largest dissimilarity: 𝛿 𝑑 ∅ (𝐴).

Table 1 shows results for distributions of ontologies. It can be observed that the diameter and median are not very discriminative of different case. Similarly, average dissimilarity may return the same value for quite different cases: there are many ways to distribute ontologies at the same dissimilarity. Hence, it is useful to consider that for the same average dissimilarity, a lower the standard deviation means that this dissimilarity is regularly shared and the population is more diverse.

We extend this line of reasoning to taking distribution of knowledge in different categories instead of considering ontologies one by one.

Measuring diversity on a distribution

So far, we only considered dissimilarities between individual knowledge (or ontologies). When the set of possible objects becomes larger, it is customary to group them into categories. Indeed, each individual is usually different from the others but what counts as diversity is how specific categories of individuals are represented. These categories group objects (ontologies) whose difference is considered as insufficient to consider them different (hence diverse).

There are two ways to determine such categories: a priori diversity is measured based on a set of predefined categories that can be assigned to individuals. These categories are independent from the data.

a posteriori the categories are determined through how individuals may be grouped together. This may be determined through clustering or applying factorial analysis to the ontologies. Such categories are usually relative to the considered data.

We will work on a priori categories because it allows to define what kind of diversity is to be measured (knowing what to look for) and not diversity that has to be discovered (returning what is the most diverse). For that purpose we will use a set 𝐾 of categories. Each ontology belongs to one and only one category. The number of agents 𝑎 ∈ 𝐴 whose ontology 𝑓 (𝑎) belong to a category 𝑘 ∈ 𝐾 is denoted by #𝑘. Figure 1 shows the diversity of possible distributions of 10 objects in 5 categories presented along a linear order.

For the sake of simplicity, we will consider the categories of Section 4.4. They have the advantage that any ontology in these category may be taken as representing it, and, as already discussed, its dissimilarity to another category will be the same as its dissimilarity to any element of that other category. Hence, the set of category 𝐾 will be a set of ontologies 𝑂 and the distribution of agents' knowledge in this set will simply be 𝑂 𝐴 .

A measure of diversity in categories must take into account:

• the number of filled categories, which correspond to the variety of [START_REF] Harrison | What's the difference? Diversity constructs as separation, variety, or disparity in organizations[END_REF] (Figure 1),

• the distribution of objects in these categories, which correspond to separation (or intensity),

• how far appart are such categories, which corresponds to the disparity (or spread), and which can be measured by a dissimilarity.

We consider two families of measures in this context.

Weighted average dissimilarity in a distribution

A non-structured distribution is one in which the set of categories is simply a set with no additional structure. In such a case, two ontology within the same category will be counted as the same (0) and two objects in different category will be counted as different [START_REF] Stirling | A general framework for analysing diversity in science, technology and society[END_REF]. The diversity measure may be computed with respect to the abundance of each category as:

𝛿 ≡ (𝐴) = ∑ 𝑜∈𝑂 𝐴 #𝑜 × (|𝐴| -#𝑜) |𝐴| × (|𝐴| -1)
A structured distribution is defined when there exists a structure among the categories. This is given by providing a dissimilarity 𝑑 between categories representing this structure.

The diversity is then the average dissimilarity between the objects' categories:

𝛿 𝑑 𝛼 (𝐴) = ∑ 𝑜∈𝑂 𝐴 #𝑜 × ( ∑ 𝑜 ′ ̸ =𝑜 𝑜 ′ ∈𝑂 𝐴 #𝑜 ′ × 𝑑(𝑜, 𝑜 ′ )) |𝐴| × (|𝐴| -1)
This is the same measure as in Section 5.2 but applied to categories instead of individual ontologies.

The structure may have various interpretations:

• The non-structured case may be obtained by taking the dissimilarity as the inverse of the identity matrix (0 on the diagonal, 1 otherwise). • The linear structure that corresponds to the alignment of the five categories in Figure 1.

The dissimilarity corresponds to how many slots the two categories are appart. • Any dissimilarity between categories may be used and it can be based on syntactic or semantic cues. We will use the two semantic dissimilarities presented in Section 4.2 and 4.3.

Entropy of a distribution

The distribution among classes can be considered as the probability #𝑜 |𝐴| of obtaining an ontology of category 𝑜 when drawing it randomly among 𝐴, also called relative abundance. The entropy measures how much random this probability is, i.e. how much the category of a random individual may be predicted. This seems a very good candidate to measure diversity and it has been used for that purpose [START_REF] Leinster | Entropy and diversity: the axiomatic approach[END_REF].

On such a distribution, a parametric measure of diversity can be defined [START_REF] Jost | Entropy and diversity[END_REF][START_REF] Hill | Diversity and evenness: a unifying notation and its consequences[END_REF]:

𝛿 𝑞 (𝐴) = ⎛ ⎝ #𝑜̸ =0 ∑ 𝑜∈𝑂 𝐴 ( #𝑜 |𝐴| ) 𝑞 ⎞ ⎠ 1 1-𝑞
It is the exponent of a general entropy measure. This measure has been extended to structured distributions in which a similarity exists [START_REF] Leinster | Measuring diversity: the importance of species similarity[END_REF]. Such a similarity 𝑠 may be obtained from a dissimilarity 𝑑 by taking 𝑠(𝑜, 𝑜 ′ ) = 𝑒 -𝑑(𝑜,𝑜 ′ ) .

𝛿 𝑑 𝑞 (𝐴) = ⎛ ⎝ #𝑜̸ =0 ∑ 𝑜∈𝑂 𝐴 #𝑜 |𝐴| × ⎛ ⎝ #𝑜 ′ ̸ =0 ∑ 𝑜 ′ ∈𝑂 𝐴 #𝑜 ′ |𝐴| × 𝑒 -𝑑(𝑜,𝑜 ′ ) ⎞ ⎠ 𝑞-1 ⎞ ⎠ 1 1-𝑞
The same dissimilarities between categories as above may be retained.

Depending of the parameter 𝑞, called the order of diversity, a different measure is obtained ranging from assigning more weight to the rarest category to assigning more weight to the commonest category, with more balanced weighting around 1. Here we use 𝑞 = 2 which corresponds to the inverse of the Gini-Simpson measure. The notion of 'diversity profile' (the evolution of diversity with 𝑞) may be useful in defining a partial order between populations: a population 𝐴 is more diverse than another 𝐴 ′ , 𝐴 ′ ⪯ 𝐴 if for any 𝑞, 𝛿 𝑑 𝑞 (𝐴) ≥ 𝛿 𝑑 𝑞 (𝐴 ′ ). This diversity measure is not normalised. It ranges within [1.0 + ∞]. When comparing a finite set of distributions, it is possible to normalise it as:

𝛿 ¯𝑑 𝑞 (𝐴) = 𝛿 𝑑 𝑞 (𝐴) -1 𝛿 ˙𝑑 𝑞 -1
with 𝛿 ˙𝑑 𝑞 the maximum value among the set. Contrary to average dissimilarities, diameter and entropy are independent from scale (adding more agents in the same distribution will return the same measure).

Table 1 provides the measure values for these different distributions. Concerning the semantic measures, the five categories are considered as corresponding from left to right to the ontologies (A-E) of Figure 2.

As expected the diversity is minimum for distribution (a) for all measures. We also expect it to be maximum for distribution (g). But this did not happen in the case of the linear distance in which (e) has the highest diversity value. Actually (e) is polarised with two groups very far apart. However it is not very diverse as only two categories are filled. Measures corresponding to the distributions of Figure 1 with non structured, linearly structured (with the A-B-C-D-E order), graph-based and named-class-based semantic categories. In each case, is displayed the diameter, the median, the average dissimilarity and the normalised entropybased diversity (𝑞 = 2).

distribution (a) (b) (c) (d) (e) (f) (g)
The entropy-based diversity measures seems to be behaving better. They are also very sensitive to the influence of the dissimilarity: there is no consensus between the orders induced by the measures except for the extrema. For instance, the graph-based semantic diversity has the same high values for (b) and (e) because the two categories which are filled have the same dissimilarity. These measures also do not account very well for the empty categories: they have been designed for applications for which most categories have some representations. Our example is likely too small.

In conclusion, it seems that entropy-based measures, by putting emphasis on equal dispersion of objects in all categories is a good measure of diversity, and that a semantic dissimilarity structures knowledge categories appropriately. However, it is not always the case that agents ontologies present themselves as distributions. In this case, a semantic dissimilarity alone should provide a good idea of diversity.

Controlling diversity

When one wants to observe experimentally the consequences of diversity, it is necessary to be able to control it.

The conceptually most straightforward way to achieve this is to determine the diversity measure to be used and to design agent populations and their knowledge which comply to different values of these measures. This may be quite difficult because we already have two factors (agents and knowledge) and knowledge itself may be diverse in a variety of ways. Synthesising artificial ontologies is possible, but may result in non representative results.

In our experiments [START_REF] Bourahla | Knowledge improvement and diversity under interaction-driven adaptation of learned ontologies[END_REF], we observed that some factors, e.g. number of object descriptors, have an influence on the diversity of the resulting knowledge. It would thus be tempting to control these factors in order to obtain the desired diversity. However, this is not a good way to control diversity because it would be very difficult to determine if the observed effects will be due to diversity or to these factors themselves.

One possible way to improve on that is to perform such an experiment and to stop the simulation. What is obtained is a population of agents 𝐴 with a 'roof' diversity 𝛿 ˙= 𝛿(𝐴). At that stage, if each agent knowledge is replaced by the ontology of one specific agent, taken at random or as the fittest knowledge for some measure, yielding distribution 𝐴 ′ , then 𝛿(𝐴 ′ ) will be minimal. One further advantage of this procedure is that it compares distributions over the same set of agents and the same set of ontologies. Hence all distributional measures may be used and may be normalised without inconvenient. It is thus possible to obtain different distributions with diversity ranging in [0..𝛿 ˙] by distributing not 1 but 𝑛 ∈ [1..|𝐴|] different ontologies among the agents.

Boolean approach

In the case of a boolean distance function, the natural approach is to replace an ontology by another (already used by one agent).

The diversity of a (multi)set of such ontologies is computed by 𝛿(𝐴) (with any of the 𝛿 defined before).

We consider a simple operation 𝑟 which consists of replacing one ontology by another ontology that is already present in the multiset. Applying iteratively this operation progressively reduces the diversity in the multiset. These successive applications define a path in the graphs of Figure 4.

If one takes care to never apply an operation that increases diversity, then this path goes from the top to (one of) the bottom(s). Figure 4 presents multisets of ontologies of the same cardinality, up to category permutation, related by arrows representing the application of 𝑟; dashed arrows are those which do not decrease diversity. This enable to define different levels of diversity that can be used for the experiments. For the sake of simplicity, diversity is here measured by average dissimilarity in a non structured set of categories. The more ontologies are initially in the set, the more levels can be defined.

Simple dissimilarity-based approach

It may be more interesting to control diversity based on non-boolean dissimilarities between ontologies. The same type of reasoning may be applied with 𝛿 𝑑 .

Hence, contrary to what appears in Figure 4, the levels do not depend on the number of occurrences of ontologies only. Their respective dissimilarity measures will play an important role and lead to a larger variety of diversity levels.

Consider three ontologies 𝐴, 𝐵, and 𝐶 such that 𝑑(𝐴, 𝐵) = .8, 𝑑(𝐵, 𝐶) = 1. and 𝑑(𝐴, 𝐶) = 1.21 . These may be considered as ontologies 𝑜 ∈ 𝑂 or categories 𝑘 ∈ 𝐾. The development of the pattern above on these three ontologies provide the result of Figure 5.

The opportunities are here very limited due to the strict pattern followed for only three ontologies by only three agents. Starting with four, the diagram becomes largely more complex with more paths from top to bottom.

Figure 4 and 5 show that the diversity levels are fixed and relatively more dense over .5 than below it. This may be a problem when one wants to control better the given level. However, this is also very dependent on the diversity measure, hence unless one knows very precisely the meaning of these levels, it may be better to rely only on the order between distributions. Moreover, on a statistical basis if the goal is to establish the relation between a similarity measure and another measure, it is not strictly necessary to have a regularly spaced sample.

A simple algorithm for generating new sets of ontologies consists of computing the average dissimilarity between each ontologies and all the others. Then replacing the one with the higher dissimilarity with either (a) the most central (closer to the barycentre), or (b) the most central with respect to the remaining ones. Such an algorithm would again define a path within the lattice of possible ontology distributions.

Increasing the ratio agent/ontologies and using more sophisticated measures, such as the entropy-based ones, provide a reasonable way to collect samples of various diversity-levels.

Finely controlling diversity

The algorithm sketched in the previous section still does not allow to control finely the obtained levels. If someone would like to obtain a set of ontologies for 1., .75, .5, .25 and 0. diversity. It will not return exactly this. Worse, it will not return the best possible solution. It is possible to express it as an optimisation problem. Indeed, the goal is to find, for each diversity level 𝑙, the assignment # that provides the multiset 𝑂 * whose diversity 𝛿(𝑂) is the closest to 𝑙, i.e. A very expensive algorithm for achieving this would be to compute all the replacement combinations, to measure their diversity, and to retain those which are the closest to the expected levels.

Conclusions

This work was motivated by the need to measure and control knowledge diversity. It seems to us that the approach consisting in taking advantage of measures already defined to assess diversity and adjoining them with measures already defined to assess knowledge difference is a promising one. However, there are so many such measures to be combined that a careful examination of the properties of these and their combinations is an interesting perspective. This would benefit from carefully studying the interactions between axioms governing both components in the spirit of [START_REF] Morales | Measuring diversity in heterogeneous information networks[END_REF][START_REF] Leinster | Entropy and diversity: the axiomatic approach[END_REF]. We briefly discussed one practical way to control knowledge diversity for the purpose of experiments. This is a critical issue that has no simple solution. However, the problem has to be tied to the knowledge diversity measure.

Figure 2 :

 2 Figure 2: Five ontologies to be compared. Each of the concept presented in these corresponds to the named classes of the ontologies.

Figure 3 :

 3 Figure 3: Semantic dissimilarity measures between the ontologies of Figure 2. Graph-based (left) and named-class-based (right) and the transitive reduction of the subsumption graph ⟨𝑂, ⊑⟩ (middle).

Figure 4 :

 4 Figure 4: Patterns of ontology substitution for |𝐴| = 3, 4, 5. Dashed transitions do not decrease diversity.

Figure 5 :

 5 Figure 5: The different distributions of three ontologies in three categories and the possible transitions for 𝑟. Dashed transitions do not decrease diversity.

  𝑂 * = 𝐴𝑅𝐺𝑀 𝐼𝑁 # |𝑙 -𝛿(𝑂)|under the constraints that:∀𝑜 ∈ 𝑂, #𝑜 ≥ 0 and ∑ 𝑜∈𝑂 #𝑜 = |𝐴|

Table 1

 1

	Stats	|𝐴| 10 |𝑂 𝐴 | 1 |𝑂 𝐴 | |𝐴| .1	10 2 .2	10 3 .3	10 5 .5	10 2 .2	10 5 .5	10 5 .5
	Non struct.	∅ 𝛿 𝑑 𝜇 𝛿 𝑑 𝛼 𝛿 ¯𝑑 2 0.0 .45 .54 .60 0 1 1 1 0.0 1.0 1.0 1.0 0 .56 .62 .67	1 1.0 .56 .45	1 1.0 .82 .86	1 1.0 .89 1.0
	Linear	∅ 𝛿 𝑑 𝜇 𝛿 𝑑 𝛼	0 0.0 2.0 1.0 1.0 2 2 4 0.0 1.11 .71 1.11 2.22 1.33 1.78 4 4 4 4.0 1.0 1.0
		𝛿 ¯𝑑 2 0.0 .43 .33 .48	.54	.70	1.0
	Graph-B.	∅ 𝛿 𝑑 𝜇 𝛿 𝑑 𝛼 𝛿 ¯𝑑 2 0.0 .78 .39 .56 0 1 1 1 0.0 1.0 .33 .33 0.0 .56 .27 .37	1 1.0 .56 .78	1 .33 .47 .74	1 .33 .59 1.0
	Name-b.	∅ 𝛿 𝑑 𝜇 𝛿 𝑑 𝛼 𝛿 ¯𝑑 2 0.0 .52 .61 .74 0 .5 .5 .5 0.0 .5 .5 .5 0.0 .28 .31 .38	.71 .29 .16 .30	.29 .5 .44 .94	.71 .5 .46 1.0

This averages to 1., but there is no obligation. Moreover, it still provides high level of diversity (all over 0.5).

Acknowledgments

This work has been partially supported by the MIAI Knowledge communication and evolution chair (ANR-19-P3IA-0003). We thank the reviewers for their careful reading and for helping clarify some formulations.

Code and data availability

All measures and algorithms have been implemented in Python and can retrieved from https: //moex.inria.fr/software/kdiv/.


The Semantic Web: Year One T he Semantic Web began at the end of the last century as an object of investigation and experimentation. It has grown into a subject of huge interest to several research communities and to Web users at large. Many people consider it the next generation of the Web, a Web that machines themselves can handle to help users.

The few available books on the Semantic Web cover its programming or research aspects. Spinning the Semantic Web: Bringing the World Wide Web to Its Full Potential, however, is a kind of handbook on the Semantic Web's first steps and the principles behind them. The book stemmed from a Daghstul seminar in 2000, at the beginning of the Semantic Web development, and features contributions from some of the main actors in that development. It includes general chapters on the subject and several chapters relating early experiments and system designs (indeed, these chapters were written just before the OWL, or Web Ontology Language, era). In this way, this well-crafted book can be a starting point and reference book for understanding the forthcoming Semantic Web design issues.

From a general point of view, Spinning the Semantic Web contains no formalisation (it is not very technical, except that some chapters display computer code). Rather, the book describes systems, languages, and their designs.

In the book's foreword, Tim Berners-Lee offers a techno-philosophical motivation of the Semantic Web. In the introduction, editors Dieter Fensel, James Hendler, Henry Lieberman, and Wolfgang Wahlster present an extensive overview of applications the Semantic Web is meant to enable and the required technologies, and then describe the book itself. These two sections are complementary: while Berners-Lee focuses on information and linking, Fensel and his colleagues center on applications and resources. They present the Semantic Web infrastructure as a set of languages, ontologies, and intelligent information access, and applications developed on top of these. This roughly parallels the rest of the book structure.

The core of the book comprises three parts: Languages and Ontologies, Knowledge Support, and Dynamic Aspect. We found that the chapters tend to fall into two categories: ones raising problems and ones offering solutions. This distinction is not absolute; presenting a solution requires presenting the problem it solves, and presenting a problem is often followed by some tracks to solve it. However, it is useful for the purposes of this review.

Languages and ontologies

To be understood by machines, the Semantic Web pages (or resources) should be expressed in a language designed for this purpose. Such a language is a crossbreed of knowledge representation languages from artificial intelligence and markup languages from document engineering. This part of the book covers various languages designed from the Semantic Web perspective. It includes materials about languages that are not widely available, providing a good foundation for understanding them and their design rationale. Of course, all of the chapters that present languages provide solutions for expressing knowledge on the Web.

Chapter 2 describes SHOE (Simple HTML Ontology Extensions) and the developments surrounding it. SHOE is based on HTML and is a precursor of the current Semantic Web infrastructure. This chapter explains what is new in using a knowledge representation language in a distributed environment: interoperability, evolution, and scalability.

Chapter 3 covers DAML-ONT (Darpa Agent Markup Language-Ontology). You can think of DAML-ONT as a frame language on top of RDFS (Resource Descriptive Framework Schema).

Chapter 4 introduces OIL (Ontology Inference Layer), RDFS, and XML (Extensible Markup Language) Schema. This chapter is an interesting overview of these languages and their merits. It also details specific points, such as the way to em-bed OIL (and thus OWL) within RDFS.

Chapter 5 discusses Web services with UPML (Unified Problem-Solving Method Development Language) and IBrow, an intelligent broker for retrieving a set of knowledge components from the Web. With IBrow, the reasoning components themselves must be available on the Web, and the broker selects the set of suitable components for the ongoing task. So, you can think of UPML as a precursor of Web services description languages. The chapter briefly describes how to use the Protégé editor in this framework.

Chapter 6 provides different definitions of ontology and the kind of applications ontologies can support. Because this chapter is rather introductory, exploring the jungle of multiple definitions, you can read it before the other chapters in this part.

These chapters would have been clearer and more understandable if they had shared a common example, but this is difficult to achieve when the chapters have different authors. This part of the book does show well the need for each successive language to have increased expressive power (especially the chapter on OIL, RDFS, and XML Schema). The emphasis on languages predating DAML+OIL and OWL should help readers understand the genesis of more recent languages.

Knowledge support

The second part covers tools and architectures that will take advantage of the Semantic Web resources. Two chapters in this part provide solutions. Chapter 7 takes a look at Sesame, an architecture for efficient storage and expressive querying of large quantities of metadata. The chapter includes a simple presentation of RDF and RDFS, as well as a query language for RDFS. In particular, it explains how answers to queries differ at the syntactic, structural, and semantic levels. For semantic-level querying, the authors suggest using RQL (RDF Query Language, an extension of Ob-ject Query Language for the Semantic Web) or a similar query language. The chapter also discusses a concrete experiment with the PostGres database management system.

Chapter 11 promotes ontologies as a sound basis for communications of all types on the Web. This position is based on experience with Ontobroker and relies on Ontobroker's application to a laboratory Semantic Web site (a Web site generated from data systematically related to an ontology). The chapter also discusses modelling and designing ontologies (ontology engineering) and comparing ontologies. The authors describe the SEAL tool suite, built around Ontobroker, and discuss topics important for Semantic Web sites, such as ranking knowledge and personalising the user experience. The chapter tells how to include such a site within the Semantic Web through knowledge export in RDF.

The other chapters deal primarily with problems. Chapter 8 is oriented toward industry. It advocates interpreting resources in regard to tasks. It also provides a systematic analysis of querying a set of resources in terms of the frequency of queries and ability to anticipate them. The chapter describes a help desk application that exploits the Web and knowledge-based resources.

However, it does not go all the way in providing a task-oriented view of the application. In particular, the chapter gives no key for generalising the approach to the Web.

Chapter 9 presents the risks of interoperability through ontologies because of granularity mismatches, inconsistencies, and modelling mismatches between ontologies. The author suggests using knowledge bases hyperlinked to their sources and elaboration substrate. These "resilient hyperknowledge bases" should provide the required mobility to ontologies. This perspective would be more integrated with the Semantic Web if the author had defined it in terms of the Web, which remains the ideal context for linking to background sources.

Chapter 10 deals with relationships as a fundamental element for supporting semantics in knowledge systems. In queries that involve several domains at once, interoperability problems exist between ontologies. One proposed solution is to model relationships between ontologies. This chapter includes several interesting examples that you could use for designing systems for the Semantic Web that take into account complex relations.

Because most chapters in this part of the book focus on problems rather than solutions, the "support" aspect is lacking. Nonetheless, the discussion of Semantic Web design problems and general principles for addressing them provide much food for thought.

Dynamic aspect

In this part, the book shifts its focus from the Semantic Web evolution to its dynamic use. Again, two chapters present problems. In Chapter 12, the problem is opportunistic communication between heterogeneous and unprepared knowledge sources. This chapter covers ubiquitous computing: small, handheld, wireless devices for computing the needs of everyday life. The ultimate goal is for automated systems to discover and use services without human intervention. However, the story presented in this chapter, a visit to a museum, illustrates a recurring question: When the Semantic Web starts handling everyday decisions, where should it stop? This old question does not receive any answer here.

Chapter 13 discusses Web page dynamic aspect during user interaction. The author advocates including this procedural element in the Semantic Web through a dedicated prototype-based language embedded in XML pages.

The last two chapters offer solutions. Chapter 14 describes a content adaptation engine that adapts requested documents in accordance with the capabilities of the client sending the request (transcoding). This chapter concerns itself strictly with syntactic transformation ("semantic" denotes the transformation context) but shows the way to extend such methods to semantic descriptions.

Chapter 15 proposes the Inova language for representing issues, tasks, and plans and the OP3 (Open Planning Process Panel) framework for representing the planning process. This chapter provides a methodology for integrating planners and users within the Semantic Web. Regrettably, Chapter 15 is not tied more to the UPML presentation in Chapter 5.

This part of the book highlights the various ways the Semantic Web could handle dynamicity. Dynamicity plays an important role when Semantic Web resources must be used in context, but current development does not widely address it.

S

pinning the Semantic Web is a good, substantial book on the Semantic Web origin and design. However, we would have expected better coordination between chapters. Cross-references would have been useful for both understanding the material and comparing approaches (the index partly serves this purpose).

The book also contains several conflicting ontology definitions and RDF presentations. A more integrated construction (even explaining disagreements) would have contributed to readability. Finally, from a historical standpoint, we would have liked an indepth presentation of the philosophy behind Ontobroker and the DAML program.

Nonetheless, we warmly thank the editors for gathering in a single volume these enlightening contributions documenting both the historical and technical aspects of the Semantic Web early development-most of the contributions would not have been available otherwise. We highly recommend it to everyone wanting to work in the field. This comprehensive reference could help many newcomers grasp the spirit behind the Semantic Web.

As we mentioned before, this book is a handbook on the Semantic Web in the making. The answers it provides will be realised only "by construction" in the forthcoming languages and tools for the Semantic Web. We encourage a follow-up book that integrates all the presented approaches in their presentation and, above all, in their implementation.

Jérôme Euzenat is a research scientist at INRIA Rhône-Alpes. Contact him at jerome.euzenat@inrialpes.fr. Amedeo Napoli is a senior research scientist at LORIA Nancy. Contact him at amedeo.napoli@loria.fr.