.. include:: common.inc.rst ============== Introduction ============== .. index:: artificial intelligence see: AI; artificial intelligence Artificial intelligence (AI) can be argued to be as old (if not older) as computer science itself. Indeed, the question of intelligent machines was one of the motivations of Alan `@TuringIntelligence1950` for stating the principles of the Turing Machine, which remains until this day the abstract model of computers. Building intelligent systems out of computers has hence been a continuous challenge for many computer scientists and developers. Among different paths to that goal, one that has been largely studied involves the explicit representation of *knowledge*, and the processing of those representations by generic reasoning engines\ [#machine-learning]_ `[@SchreiberKnowledge2000]`. The advent of the Web, and then of mobile computing, has however dramatically changed the way we use computers, and with it our expectations of what such intelligent systems should be. Of course, it has also changed the means available to build them. One could argue that the Web changes the fundamental assumptions on which |AI| was traditionally built, raising a number of new challenges, but also providing new opportunities. The goal of this dissertation is to show how, in my work in the last ten years, I have been aiming at novel approaches to knowledge engineering, intending to tackle those challenges and leverage those opportunities. Dynamics and ambivalence ======================== .. long story short: traditional AI considered knowledge as rare, stable and absolute, while on the web it is overwhelming, dynamic and relative. Since the first attempts to build knowledge-based computer systems, the process of acquiring and formalizing knowledge has been recognized as a major bottleneck in the building of such systems. With expert systems, knowledge was first acquired by knowledge engineers through interviews with domain experts. Such interviews are very time consuming, as the parties have different skills (respectively in formal models and in the application domain) and must learn enough from each other in order to reach an agreement on how to represent the experts' knowledge. Furthermore, a large part of the expert's knowledge is tacit `[@NonakaKnowledge1995]` and eliciting it can be challenging. Finally, experts can be reluctant to disclose their knowledge if they have the feeling that the system is meant to replace them. .. index:: natural language processing see: NLP; natural language processing In order to tackle those difficulties, alternative approaches have been proposed, such as applying natural language processing (NLP) to a corpus of texts related to the application domain `[@DelannoyExtraction1993;@MooneyMining2005]`. The goal is to automatically or semi-automatically discover the domain terminology, and extract relevant knowledge in the desired formalism (rules, description logics, |etc|). While less time-consuming than interviewing experts, such approaches produce knowledge representations that, most of the time, still require human validation. This is related to the fact that traditional |AI| is strongly rooted in formal logic, which leaves no room for approximate or relative truths\ [#fuzzy-logic]_. Hence, whatever piece of knowledge that could be collected had to be scrutinized for validity and consistency. Not only does this make the building of the knowledge base costly, but also any evolution that this knowledge base might undergo. Knowledge-based |AI| has therefore mostly developed on the premise that knowledge was **rare**, and as such should be made as **stable** as possible, despite a few efforts to temper this tendency by applying agile methodologies `[@AuerAgile2007;@CanalsCollaborative2013]`, .. index:: case-based teasoning see: CBR; case-based reasoning Another popular alternative approach is case-based reasoning (CBR), founded on a memory-model proposed by `@SchankDynamic1982` and formalized by `@AamodtCase1994`. Schank points out that many reasoning tasks are not performed from first principles, but instead by reproducing or adapting the solution of a past similar problem. In |CBR|, problem solving knowledge is then captured by a set of *cases*, that are examples of previous problems with their solution. Reasoning is achieved by comparing the problem at hand with the ones previously solved, retrieved from the case base, and adapting the solution of the closest case. If successful, that adapted solution is in turn recorded as a new case\ [#negative-case]_. One benefit of |CBR| over other approaches is that it does not require domain knowledge to be fully formalized. Instead, a representative set of prototypical cases is enough to get it started. Those may be significantly easier to acquire than more general knowledge, as they are not expected to hold a general or universal truth, but only a local solution in the context of the given problem. Another benefit is that a |CBR| system learns new cases as it is being used, which makes it able to improve over time. Still, those benefits must not hide inherent difficulties. While the case base may be relatively easy to gather, it is only one of the knowledge containers required by the |CBR| system `[@RichterContainers2003;@CordierInteractive2008]`. Other knowledge containers include: the structural representation of cases, the similarity measure used to compare cases to the problem at hand, and the adaptation knowledge used to adapt its solution. Furthermore, an ever-growing case base requires continuous maintenance `[@LopezRetrieval2005 section 5;@CumminsChoosing2011]` in order to prevent pollution (from bad quality cases) or bloating (from an excessive quantity of cases). Maintenance becomes even more challenging when changes occur in the context in which the |CBR| system operates, and old cases become obsolete. Replacing obsolete cases by new ones is often not enough to take changes into account: all the knowledge containers mentioned above may have to evolve as well. The very structure of the cases (a problem and its solution) may have to be revised as the nature of the problem, or its understanding, may change over time. This of course may have a huge impact on the whole system, as all knowledge containers are strongly dependent on that structure. A large part of our work has been inspired by |CBR|, and trying to leverage the problems faced by any knowledge-based system when its context changes. Indeed, is not adaptability a core aspect of intelligence? But evolving implies the continuous acquisition of knowledge. In other words, adaptive reasoning mechanisms must take into account, from the ground up, the **dynamics** of their knowledge base. It does not just mean being able to integrate new knowledge as it is being acquired; it does not even limit to being able to revoke old knowledge obsoleted by new information. It requires to embrace the fact that information is inherently **ambivalent**, that it acquires meaning (and hence becomes knowledge) only in the context of a particular problem or task\ [#cbr-ambivalence]_. Note that ambivalence must not be confused with *ambiguity*; effective ambivalence means that enough contextual information is available to disambiguate knowledge, to decide on a particular interpretation. .. todo I would have liked to make it clear that there is no intrinsic distinction btw contextual and "primary" information. However it seems a little to precise for this introduction. I have to remember to mention that in the chapter on traces. This is where the Web offers an unprecedented opportunity, as it has become the hub of most of our digital activities, even more, a large part of our personal and social lives. Its network structure naturally relates our actions to a vast amount of information, either text material (Wikipedia\ [#wikipedia]_, various blogs or forums), structured databases (such as Freebase\ [#freebase]_ or Musicrainz\ [#musicbrainz]_), or interactive services (weather forecast, route planning, |etc|). Of course, this is not new, and major Web companies have a long (and controversial\ [#controversies]_) history of studying and using this wealth of information, to gain deeper knowledge about their users and provide more targeted services. Their approach is however mostly one-way: users have few (if any) insight or control over the information that services have about them, or how it is used. And even if they did, that information is buried into machine-generated statistical models, that produce results mostly in a black-box fashion. In contrast to this service-centered approach, we have been pursuing a user-centered approach, much in the line of `@EstrinLifestreams2013`, where data collection and reasoning processes are as transparent as possible. It is important that every result can be explained and traced back to its premises, and that the interpretation choices about ambivalent information can be elicited. Indeed, the ultimate judge of the relevance of a reasoning process is the human on behalf of whom the system is working. It is therefore important that users have all the means to understand the results of the system, that they can comment on them, and that their feedback be collected as additional knowledge for future reasoning tasks. That way, meaning is not a pre-defined property of information, but negotiated and co-constructed with users. More generally, user feedback does not have to be explicit or direct: any interaction of the users with the system can be considered as a clue and participate to this negotiation. Structure of the dissertation ============================= The rest of this dissertation is structured as follows. In :doc:`Chapter 2 `, I will first present our work on building knowledge-based systems exploiting a special kind of knowledge, namely *activity traces*. More precisely, those systems keep track of how users have interacted with them in the past, in order to gather experience and, from this, to learn both *about* the users and *from* them. By capturing the inherent complexitiy of the user's task, this kind of knowledge allows for multiple interpretations, and hence requires a special kind of reasoning as well. I will describe the theoretical framework that we have proposed to build such trace-based systems, as well as the generic implementation of that framework which we have used in order to validate our proposals in various contexts. One particular domain where experiential knowledge can prove useful is doubtlessly user assistance. In :doc:`Chapter 3 `, I will present a number of our works focusing on that topic. The most straightforward use of traces to help users is simply to present them with their traces, in order to help them remember their activity or explain it to others. Of course, one's activity is not always a flawless and straight path, and it may be useful to detect failures and errors in the collected traces in order to make them more useful. Finally, observing the user's interactions with the system, and detecting unsuccessful or abnormal patterns, can help detect problems and make helpful proposals. :doc:`Chapter 4 ` will then describe our activity related to Web technologies and Web standards. The Web was initially designed as a document space, and documents are the traditional means for humans to represent their knowledge. Thus, *digital* documents, such as those used on the Web, can be designed in such a way that the knowledge they represent be equally usable by humans and machines. This is the starting idea that lead to the concept of the Semantic Web `[@BernersSemantic2001;@BernersSemantic2006]`. I will show how the REST architectural style, which is one of the foundations of the Web, accommodates and even encourages ambivalent information. As such, it allows to bridge the gap between documents, data and knowledge representations. In :doc:`Chapter 5