State of the art

We consider how existing disciplines deal with the problem of knowledge evolution. This state of the art is divided into three broad parts: Knowledge representation, cultural evolution and multi-agent systems.

Knowledge representation

Knowledge representation has been studied in artificial intelligence for decades leading to semantically well-defined formalisms. Shared representations have been promoted in the context of the semantic web as ontologies. We will consider ontologies and data expressed using the vocabulary of these ontologies, alignments between these ontologies and links between their data. This provides a well integrated framework, designed for sharing knowledge at a wide scale and for which both formal semantics and tools exist [baader2003a, antoniou2012a]. In particular, they are available for reasoning with these ontologies [antoniou2012a], for matching them [euzenat2013c] and for revising ontologies and alignments [euzenat2015a, meilicke2011a]. Nonetheless, our results should apply to wider classes of representation formalisms.

Sharing knowledge leads to problems of heterogeneity: different individuals or organisations will develop and share different representations. For dealing with these problems, we have developed ontology matching [euzenat2013c]. Ontology matching finds relations between ontology entities and expresses them as sets of correspondences, called alignments.

When different knowledge representations are confronted, they may be compatible or incompatible; in logical terms, merging them may be consistent or inconsistent. In the latter case, belief and knowledge revision [alchourron1985a] has been developed for adopting a consistent theory minimising the changes brought for recovering consistency. This has recently been adapted to alignment repair [meilicke2011a] and network of ontology revision [euzenat2015a]. However, revision only characterises the set of possible solutions: it does not take into account the situation in which representations are used for selecting the revision to apply. Hence, applying revision blindly may lead to consistent knowledge irrelevant to the context in which agents live. Through the introduction of adaptation operators, we will allow for selecting the revision according to the situation [euzenat2014c]. Taking advantage of the context has been studied for ontology matching: Interaction-situated semantic alignment [atencia2012a] considers ontology matching as framed by interaction protocols that agents use to communicate. Agents induce alignments between the different ontologies that they use depending on the success expectation of each correspondence with respect to the protocol. Failing dialogues lead them to revise their expectations and associated correspondences. This approach has recently been studied under the angle of cultural evolution providing encouraging results [chocron2016a].

Other approaches, such as Bayes networks, neural networks, or Markov decision processes, address this problem by introducing non symbolic processing. They hardly suffer from inconsistency due to smoother conditions. However, their numerical basis hinders the extraction of an explicit shareable knowledge representation that may be communicated across agents.

Cultural evolution

The notion of cultural evolution applies an idealised version of the theory of evolution to culture. Culture, in this context refers to a "patrimony of knowledge accumulating over generations" [cavallisforza1981a]. It is somewhat related to the notion of meme [dawkins1976a] which follows more closely the genetic evolution analogy. It has been introduced, in ethology [dawkins1976a, hauser1997a], population dynamics [cavallisforza1981a] and anthropology [richerson2005a]. In such fields, culture may be bird song melodies, food regime, tool design, or psychological dispositions. Work in cultural evolution is usually based on the observation of long-term behaviours: it relies on the long-term observation of populations or the study of archeological artefacts. In its quantitative form, it is modelled as dynamic systems and compared to observations [cavallisforza1981a, richerson2005a]. Computers have been recently used for exploring small scale phenomena, e.g., the influence of population size on artefact complexity [derex2013a].

Cultural evolution experiments are performed through multi-agent simulation: a society of agents adapts its culture through a precisely defined protocol [axelrod1997a, bryson2014a]. Agents perform repeatedly and randomly a specific task, called game, and their evolution is monitored. This protocol aims to discover experimentally the state that agents may reach and the properties of that state.

Experimental cultural evolution has been successfully and convincingly applied to the evolution of natural language [steels2012a, spranger2016a]. Agents play language games and adjust their vocabulary and grammar as soon as they are not able to communicate properly, i.e., they misuse a term or they do not behave in the expected way. It showed its capacity to model various settings in a systematic framework and to provide convincing explanations of linguistic phenomena. Such experiments have shown how agents can agree on a colour coding system or a grammatical case system.

This approach has not been applied yet to knowledge representation directly. Although language experiments involve modifying cognitive representations, e.g., of colour [steels2012a] or position [spranger2016a], their properties are measured through language. So far, the closest works have only considered the terminological aspects of ontologies, i.e., associations between terms and concepts [steels1998a, reitter2011a]. This is the goal of the well-known naming game where agents learn to associate terms to objects or concepts [steels1998a]. Experiments have focussed on the way agents agree on terms for naming concepts (chair is the same as seat) and not on the way concepts are organised (through subsumption or disjointness relations for instance, e.g., what is the relation between a chair and a seat with four legs?). Only recently, we [euzenat2014c] and others [chocron2016a] started to deal with elaborate symbolic knowledge representation using a cultural evolution approach.

Multi-agent systems

BDI (Beliefs, Desires, Intentions) is the dominant paradigm in multi-agent systems. Agents attribute beliefs, desires and intentions to themselves and other agents. On a theoretical side, agent knowledge is expressed in a modal logic allowing them to reason about such beliefs, desires and intentions (and in particular to compute plans which allow agents to fulfil their desires) [wooldridge2000a]. Focusing more on agent's knowledge, epistemic logics [fagin1995a] are very appealing to reason about what others know and its dynamic version accounts for events [vanditmarsch2007a]. So, these logics may be useful to abstract what occur in the situation we consider; less useful for agent implementations as they often adopt a global view of phenomena.

As mentioned previously, experimental cultural evolution uses directly multi-agent simulations. Such social simulations are also related to the artificial life field, which may include evolutionary simulations. For instance, Aevol simulates the evolution of bacteria colonies over hundred thousands of generations [batut2013a].

Cultural evolution suggests connections with various bioinspired approaches, such as evolutionary computation [eiben2015a], including memetics [dawkins1976a], or biological models, such as evolutionary game theory [maynardsmith1982a]. An important difference with cultural evolution is that, because it leads to faster adaptation, cultural evolution focuses on horizontal rather than vertical, i.e., genetic, transmission [cavallisforza1981a]: agents manipulate directly their culture, through adaptation operators, instead of depending on random mutations. So we will not attempt to combine them in the mOeX project.

Moreover, our goal is to study knowledge evolution and what knowledge properties are satisfied by specific operators, thus we can find only limited inspiration in these works.