Domain ontologies are essential in disciplines as diverse as software engineering, medicine, or political science to name just a few. This paper describes an ongoing e ort to develop a methodology for collaborative ontology construction by geographically spread communities of experts and implement a web-based prototype supporting this methodology. A distinctive feature of the proposed approach is the use of conceptual exploration techniques, which make it possible to organize the process of ontology construction by automatically identifying and explicitly highlighting issues that remain to be addressed. Given a set of objects (facts, situations, etc.) of a subject domain, which is known to have considerably more such objects, and their uni ed descriptions in terms of presence or absence of certain attributes, a conceptual exploration system maintains a compact representation of implications behind the currently built ontology and o ers them for experts to accept or falsify by entering new objects or extending the description language with new attributes. Upon termination, exploration results in identi cation of a (relatively small) representative part of the domain from which a conceptual hierarchy of the entire domain can be automatically constructed. We consider theoretic, algorithmic, representational, and pragmatic issues of transforming the exploration methods into a toolset useful for domain experts.
Domain ontologies provide common interfaces to knowledge accumulated in their respective elds through achieving consensus on terminology used therein and its meaning. Their construction is thus an important topic in knowledge engineering. In this paper, we describe a project aimed at developing a platform for online collaborative ontology construction by geographically distributed groups of users that would not simply support sharing and common editing of formalized knowledge, but would also include means for on-the- y validation of the ontology being constructed and automatic generation of guidelines for its completion.
The proposed approach is based on formal concept analysis, a mathematical
theory oriented at applications in knowledge representation, knowledge
acquisition, data analysis and visualization [
The concept lattice, being a rather universal structure, provides a wealth
of information about the relations among objects and attributes, which made
possible applications in areas ranging from sociology [
One such technique is attribute exploration [
The process of attribute exploration is interactive: it consists in computer
suggesting implications and the user accepting them or providing
counterexamples. Attribute exploration is designed to be e cient, i.e., to suggest as few
implications as possible without loss in completeness of the result. It can work even if
the initial set of objects is empty. Attribute exploration is domain-independent:
although its application is more straightforward in precise domains such as
mathematics [
Advanced versions of attribute exploration can take into account background
information, such as relations among attribute values (not necessarily given as
implications), thus, avoiding suggesting trivial implications [
Our aim is to extend these methods so as to make them suitable for collaborative ontology construction over the web by a geographically spread community of researchers working in the same domain. The idea is to provide tools that would allow them to use attribute exploration and related techniques to rene the language in which their domain is described and boost their knowledge about it. Being suggested, an implication will be accepted only if no expert has a counterexample for it. In the end, there will be a list of implications correctly describing objects under study and a representative context. If, at a later stage, a counterexample becomes known, it is added to the context and the implication basis is modi ed accordingly. Thus, an up-to-date list of open problems of the domain can be maintained.
We start with a short introduction into the relevant aspects of formal concept analysis and then de ne attribute exploration. After that, we discuss possible ways to make this procedure collaborative. Finally, we describe the current state of our web-based exploration system and the work still to be done. 2
We brie y introduce necessary mathematical de nitions [
AI = fm 2 M j 8g 2 A : gImg
BI = fg 2 G j 8m 2 B : gImg In words, AI is the set of attributes common to all objects of A and BI is the set of objects sharing all attributes of B.
If this does not result in ambiguity, ( )0 is used instead of ( )I . The double application of ( )0 is a closure operator, i.e., ( )00 is extensive, idempotent, and monotonous. Therefore, sets A00 and B00 are said to be closed.
A (formal) concept of the context (G; M; I) is a pair (A; B), where A G, B M , A = B0, and B = A0. In this case, we also have A = A00 and B = B00. The set A is called the extent and B is called the intent of the concept (A; B).
A concept (A; B) is a subconcept of (C; D) if A C (equivalently, D B). The concept (C; D) is then called a superconcept of (A; B). We write (A; B) (C; D). The set of all concepts ordered by forms a lattice, which is called the concept lattice of the context K:
The formal context makes precise the scope of the discussion by specifying the domain to which it applies (listing all the objects of this domain) and de ning the terms in which it is going to be discussed (listing the attributes to be used in object descriptions).
To esh this out a bit, we give a small example based on the data from the O*NET Resource Center (http://www.onetcenter.org/), which essentially provides an interface to a taxonomy of occupations, organizing occupations in various groups and describing the knowledge, skills, and abilities required by t n e m isc ega on gn an tr i
each occupation. Here, we focus on the knowledge required by occupations from the Computer and Mathematical job family.
A formal context encompassing three occupations is shown in Fig. 1. Here, rows correspond to objects (occupations) and columns correspond to attributes (areas of knowledge). A cross indicates that the corresponding object has the corresponding attribute; in our case, it means that an occupation requires knowledge in a certain area.
A line diagram of the concept lattice of this context is shown in Fig. 2. Nodes correspond to formal concepts, with more general concepts placed above less general ones. Two concepts are connected with a line if one is more general than the other and there is no concept between the two. Every concept in the diagram is described extensionally, by a group of objects, and intensionally, by attributes shared by all the objects in the extent of this node. The names of the objects in the extent of a node can be read o from the diagram by looking at the labels immediately below this node and below all nodes that can be reached from this node by downward arcs. Conversely, the set of attributes forming the intent of a node consists of labels immediately above this node and those above nodes that can be reached from this node by upward arcs. For example, the bottom-right node corresponds to the concept whose extent consists of a single occupation, Computer and Information Research Scientists, whereas its intent includes all attributes but Physics. The top concept is labelled by Computers and Electronics and by Mathematics, which means that all the three occupations require knowledge in these two areas.
It can be seen from this diagram that all occupations in our context requiring knowledge in Education and Training also require knowledge in Administration and Management. This is formally captured by the notion of an implication,
which is, formally, an expression A ! B, where A; B M are attribute subsets. It holds or is valid in the context if A0 B0, i.e., every object of the context that has all attributes from A also has all attributes from B.
An attribute subset X M respects or is a model of an implication A ! B if A 6 X or B X. Obviously, an implication holds in a context (G; M; I) if and only if fgg0 respects the implication for all g 2 G. If an object g 2 G is such that fgg0 is not a model of A ! B, we will call g a counterexample to this implication.
If A0 = ? for A M , then the implication A ! M necessarily holds in the context. We will sometimes write such an implication as A ! ?, with ? standing for \contradiction", meaning that attributes of A never occur all together.
All valid implications of the context can be summarized by means of the Duquenne{Guigues basis : fP ! P 00 n P j P
M is pseudo-closedg;
where a set P M is recursively de ned to be pseudo-closed if P 6= P 00 and
Q00 P for every pseudo-closed Q P . The models of these implications are
precisely the models of all implications valid in the context, and the Duquenne{
Guigues basis has the smallest number of implications among all implication sets
with this property [
The Duquenne{Guigues basis of the context in Fig. 1 consists of three implications shown in Fig. 3. Although they look similar, it may be more intuitive to read them di erently: { The rst implication says that all occupations require knowledge both in
Computers and Electronics and in Mathematics. { The second implication says that, if an occupation requires knowledge in Computers and Electronics, Mathematics, and Education and Training, then it also requires knowledge in Administration and Management. ? ! fComputers and Electronics; Mathematicsg fComputers and Electronics; Mathematics; Education and Trainingg fAdministration and Managementg fComputers and Electronics; Mathematics; Administration and Management; Physicsg ! fEducation and Trainingg 0 ! 1 { The third implication means that there are no occupations requiring at the same time knowledge in Computers and Electronics, Mathematics, Administration and Management, and Physics.
These implications are valid in our context, but the context contains only three occupations. How do we know if the three implications are valid for all computer and mathematical occupations out there? This is where attribute exploration becomes useful. 3
The idea of attribute exploration is simple: consider every implication in the Duquenne{Guigues basis of the context and add a counterexample if the implication is not valid generally. To be more precise, we are dealing with two contexts here: one corresponds to the entire subject domain (computer and mathematical occupations, in our case) and may not be immediately observable in its entirety, while the other contains only a selection of objects. This smaller context is the one that we can put into a cross-table such as one in Fig. 1 and for which we can compute the implication basis. The goal is to make the smaller context representative of the larger context in a very precise sense: the two contexts must be models of exactly the same implications. Implications valid in the larger context are always valid in the smaller context; we can force the converse to become true as well by adding counterexamples to implications valid in the smaller context, but not in the larger one. When we are done, the two contexts will share the same implication basis and, furthermore, have isomorphic concept lattices: in other words, the concept intents will be the same in the two contexts.
As an example, consider again the lattice in Fig. 2 and the corresponding implication basis in Fig. 3. The implication
? ! fComputers and Electronics; Mathematicsg is valid in our current context in Fig. 1, but according to the O*NET data, knowledge of Mathematics is not really essential for Clinical Data Managers, whose role is to \apply knowledge of health care and database management to analyze clinical data, and to identify and report trends". Out of the ve areas we consider, they must have knowledge of Computers and Electronics and of Administration and Management. Therefore, we add Clinical Data Managers to our context as a counterexample to the above implication:
Clinical Data Managers
Note that Clinical Data Managers still must have knowledge of Computers and Electronics; therefore, we still have to consider the implication ? ! fComputers and Electronicsg: It seems that knowledge of Computers and Electronics is a requirement for all computer and mathematical occupations; so, we accept the implication.
Since we changed the context by adding a new object, the implication basis has also changed. Now, it includes the implication
fComputers and Electronics; Physicsg ! fMathematicsg suggesting that, for an occupation within the job family under consideration, knowledge of physics is useless without knowledge of mathematics. If we are to believe the O*NET data, the knowledge of Physics is not required for anyone within this job family but Mathematicians, for whom the knowledge of mathematics is obviously a must. Thus, we accept the implication.
For the same reason, we accept the third implication in Fig. 2: the only occupation category requiring knowledge of Physics is Mathematicians, but it does not require knowledge in Administration and Management; hence, there is no occupation satisfying the premise of the implication and the implication trivially holds.
In our modi ed context, there remains only one implication to consider: Is it true that, if an occupation requires knowledge both in Computers and Electronics and in Education and Training, then it also requires knowledge in Mathematics and in Administration and Management (as it is the case with Computer and Information Research Scientists)? The answer is negative, because this does not hold for Informatics Nurse Specialists, who are there to \apply knowledge of nursing and informatics to assist in the design, development, and ongoing modi cation of computerized health care systems". They \may educate sta [. . . ] to promote the implementation of the health care system", and, therefore, need knowledge in Education and Training, but knowledge of Mathematics is not a requirement for them. We add a new object to our context:
Informatics Nurse Specialists Proceeding likewise, we add
Statisticians to give an example of those who, according to O*NET, typically need knowledge of Education and Training, but not of Administration and Management; accept the implication indicating that no occupation in this job family typically requires the simultaneous knowledge of Physics and of Education and Training; and we are done. The resulting concept lattice is shown in Fig. 4. Below, we present the resulting implication basis:1 { ? ! fComputers and Electronicsg { fPhysicsg ! fMathematicsg { fAdministration and Management; Physicsg ! ? { fEducation and Training; Physicsg ! ?
Mathematics Education and Training aAnddmMinaisntaragteimonent
Although we have considered only a small fraction of computer and mathematical occupations, these four implications completely characterize the implicational theory of all such occupations (at least, as long as we trust the O*NET 1 Here, implication premises are given in an abbreviated form using their so-called minimal generating sets: instead of a pseudo-closed set P , we use its minimal subset Q satisfying Q00 = P 00. The resulting implication set is equivalent to the Duquenne{ Guigues basis. data) and the six occupations covered by the concept lattice in Fig. 4 are representative of the job family in this sense. The concept lattice contains all relevant combinations of knowledge areas that may be required for computer and mathematical occupations, and each such occupation can be placed into one of the ten concepts of this lattice. For example, Web Administrators must have knowledge of Computers and Electronics and of Administration and Management, but not of any of the other three areas; therefore, they are covered by the same concept as Clinical Data Managers.
But this is counterintuitive: surely, Web Administrators might need knowledge in areas foreign to Clinical Data Managers. The problem is that the six occupations we identi ed during attribute exploration and the concept lattice generated from them are representative only with respect to the ve knowledge areas we have chosen before. However, the choice of knowledge areas might not be representative itself. To correct this, we may use object exploration, a process dual to attribute exploration, which involves working with object implications, such as fInformatics Nurse Specialistsg ! fComputer and Information Research Scientistsg.
In our case, this implication is interpreted as follows: \Every knowledge area essential for Informatics Nurse Specialists is also important for Computer and Information Research Scientists." This is not so, since Informatics Nurse Specialists are typically required to have knowledge also in Medicine and Dentistry, which forces us to introduce a new attribute into the context. Thus, object exploration ensures that the language we use to describe the domain is su ciently rich to di erentiate between what must be di erentiated.
Alternating between object and attribute exploration in this way, we can
arrive at a complete conceptual hierarchy (in the form of a concept lattice) of
the domain under consideration. Such a hierarchy modeling the subconcept{
superconcept relationship is an essential part of any domain ontology. Advanced
versions of attribute exploration, such as rule exploration [
The construction of the concept lattice is automatic, but the data needed for that is gathered through exploration in an interactive fashion: the exploration system asks the user questions and the user replies positively by accepting an implication or negatively by providing a counterexample. Extending this approach to the case of many users will make it possible to apply it in construction of ontologies for large domains of which experts have only partial and mutually complementary knowledge.
It is important to note that users of such a system must not be knowledge engineers: they never have to explicitly describe the ontology of the domain under consideration using a specialized knowledge representation formalism. Instead, they only supply data su cient for building such ontology automatically, while the exploration system directs them through questions/implications. If exploration is used within a scienti c project, the users will typically be domain experts. In other cases, it is possible that they even come from the \general public". For example, if we were to collect data about occupations, we would welcome input not only from job market research analysts, but also from people working in HR departments, who know their companies' requirements, as well as from job seekers, who know about such requirements from their own experience. Thus, conceptual exploration provides a foundation for a toolset for crowdsourcing data based on which a domain ontology (or its part) can be automatically constructed.
One of the rst experiments of collaborative exploration was conducted within
lattice theory already twenty years ago. The aim was to study relations between
various properties of lattices: algebraic, atomistic, nite, etc., and, indeed,
interesting non-trivial dependencies have been discovered [
Obviously, the Internet together with appropriate software can make the process much better organized and more realizable in practice. We experimented with building a web system supporting attribute exploration within a joint project with political scientists at Higher School of Economics in Moscow. The project had as one of its goals developing a hierarchy of concepts of democracy de ned in literature and implemented in practice. The focus was on so-called \defective democracies", such as \delegative democracy" or \exclusive democracy". To make the construction of this concept hierarchy easier and more transparent, a website was set up in order to allow political scientists to collectively build a corresponding formal context using attribute exploration and related tools. Objects of this context were countries and/or regimes described in political science literature, and attributes were their various properties. During exploration, users consider implications of the form: \If a regime is characterized by all attributes from set A, it is also characterized by all attributes from set B," which they can accept or reject. In the latter case, the user must describe a regime characterized by all attributes from A, but not by all attributes from B. Similarly, object implications of the form \Every attribute characterizing all regimes in A is shared by all regimes in B" propose the user to di erentiate between regimes from sets A and B by adding a new attribute shared by all regimes in A but missing from some regimes in B.
It turned out however that there are a number of issues that must be resolved before exploration techniques become a truly useful tool for people not experienced in knowledge representation and formal concept analysis. Therefore, we settled down to developing a general paradigmatic model of collaborative conceptual exploration and its prototype implementation. A website is under development that currently supports only the basic version of attribute exploration, at the same time, providing some standard facilities of a collaborative environment such as user pro les, separate projects, etc.
Upon signing up, the user can start a new exploration project or join an existing project by contacting its owner. Of course, one user may participate in several projects. A typical work ow is as follows: project members start attribute exploration by de ning an initial list of attributes (which can afterwards be altered in any way) and continue by reviewing the dynamically updated implication basis as described above, i.e., by accepting implications they deem valid and providing counterexamples to other implications. The formal context maintained in the process can be modi ed directly, as long as the modi cations do not con ict with the accepted implications.
There are many issues that need to be addressed to allow for exploration of
complex domains:
{ Object exploration was discussed earlier; it is essential for identifying features
di erentiating objects from each other.
{ Incomplete speci cation of examples. Users must still be able to add a
counterexample for an implication to the system even if they are unsure about
its status with respect to attributes not occurring in this implication. Its
description will be completed at later stages, either manually or
automatically (if accepting an implication forces certain values for some attributes
that have been left unspeci ed). This requires a modi ed de nition of the
implication basis allowing for incompletely speci ed objects.
{ Background knowledge. There must be a way to explicitly add known facts
about the domain to speed up exploration and concentrate on new
knowledge. The implication basis must be built relative to these facts summarizing
the part of knowledge behind the context not covered by them.
{ Algorithmic issues. Since, for large ontologies, the canonical basis may also
be large, algorithms allowing for incremental update [
We believe that conceptual exploration techniques provide a powerful framework for collaborative development of domain ontologies. Recent developments in Web applications open new prospects for tools based on exploration. A proper implementation may result in a platform e ectively supporting online social networks of experts exchanging knowledge in a structured way and working together towards constructing an ontology of their eld. Nevertheless, a considerable amount of research, development, and testing is still needed to unleash the full potential of conceptual exploration in a distributive environment.
The rst author was supported by the Russian Foundation for Basic Research grant no. 14-01-93960.