2 Early work: the knowledge acquisition bottleneck

Our early research investigated knowledge acquisition in the context of a user teaching a computer how to perform the aspects of the task that he or she wanted to delegate. We assumed the system had a knowledge base that the user was modifying and extending. This was dubbed as ‘the knowledge acquisition bottleneck’ in the 1980s, and there were a number of knowledge acquisition tools developed to address it. Each tool was developed for a specific type of problem-solving task. An early example was SALT, developed by expert system pioneer John McDermott and colleagues to acquire knowledge for constraint satisfaction problem solvers (Marcus & McDermott, Reference Marcus and McDermott1989).

Our research demonstrated that this proliferation of knowledge acquisition tools was unnecessary and that a single general-purpose knowledge acquisition system with an underlying generic problem solver was sufficient, as long as the problem-solving method at hand could be represented in the problem solver's language and the knowledge acquisition system could reason about it with respect to the knowledge that needed to be acquired. In Gil and Melz (Reference Gil and Melz1996), we showed that all the questions that SALT was designed to ask from users were automatically generated by our EXPECT knowledge acquisition system, and that additional questions were created by EXPECT to account for gaps in the knowledge base that SALT did not address. This meant that there was no need to develop a different system for each style of reasoning, rather that one single knowledge acquisition system with more explicit representations was sufficient.

Another issue that we investigated is maintaining a knowledge base consistent through many individual changes (Gil & Tallis, Reference Gil and Tallis1997; Tallis & Gil, Reference Tallis and Gil1999). We found that the more the knowledge acquisition system can reason about different kinds of gaps in its knowledge, the better it can hypothesize how those gaps could be filled and therefore be more proactive and cause less burden to the user. This was reported in Blythe et al. (Reference Blythe, Kim, Ramachandran and Gil2001), the last paper written about the EXPECT project and one that received a Best Paper award at the 2001 Intelligent User Interfaces conference.

Through this work, we found that we needed a methodology to assess the quality of knowledge acquisition systems, and were surprised there was not one for this area of research. We designed a methodology for user studies that drew from and extended methods from the literature on evaluating programmers, tutoring systems, and user interfaces (Tallis et al., Reference Tallis, Kim and Gil2001). We have used this methodology over the years to evaluate a number of knowledge acquisition systems in a variety of application domains, with users ranging from biologists to military officers to project assistants (Kim & Gil, Reference Kim and Gil1999, Reference Kim and Gil2000, Reference Kim and Gil2001; Clark et al., Reference Clark, Thompson, Barker, Porter, Chaudhi, Rodriguez, Thomere, Mishra, Gil, Hayes and Reichherzer2001).

Thanks to these user evaluations and experiments, we were able to obtain important quantitative findings. We learned that users were able to complete complex tasks only using the assistance of a knowledge acquisition system, that users enter knowledge much faster, and that knowledge acquisition systems help regardless of the level of programming knowledge or sophistication of the user.

3 From a single user to millions of knowledge contributors

Unlike our earlier assumption that a single user would be teaching, there are now vast amounts of people on the Web interested or willing to provide knowledge to computers, whether it be deep domain expertise or personal preferences. Myriads of Web users contribute structured content that ranges from simple labels or tags to complex mashups.

Our research in this area focused on how to acquire common knowledge from volunteer contributors. A broad repository of common knowledge would allow knowledge systems to be less brittle. We investigated how to keep volunteers engaged in contributing, and developed techniques to validate the knowledge acquired (Chklovski & Gil, Reference Chklovski and Gil2005b). An interesting aspect of this work is to accommodate natural language statements, which are very easy for users to provide, while constraining them to be in a form that makes their processing possible. We also designed user interfaces that facilitated the collection of specific types of knowledge from users, including process knowledge and argumentation structures (Chklovski & Gil, Reference Chklovski and Gil2005a, Reference Chklovski and Gil2005c). By 2006, our knowledge repository contained more than 700 000 statements concerning common knowledge, becoming one of the top 100 largest OWL documents on the Web (Ebiquity, 2006).

It became clear very quickly that there are very few universally agreed-upon truths and that accommodating different views is important in an open knowledge system such as the Web. We are currently working on novel frameworks to create knowledge resources that incorporate alternative views within a community of contributors (Vrandečić et al., Reference Vrandečić, Ratnakar, Krötzsch and Gil2010).

4 No training required

When teaching a computer a complex task, it is important to receive some training ahead of time concerning the abilities and limitations of the system, the methods to test that it has understood correctly, and most of all the use of a language to communicate knowledge. Long periods of training get in the way of doing the teaching and are generally not acceptable to users. In addition, users much prefer to communicate knowledge in a manner that is natural to them.

Some projections argue that 90 million end users without having programming expertise will be interested in creating applications of reasonable complexity such as spreadsheets, websites, and computer game content by 2012 (Scaffidi et al., Reference Scaffidi, Shaw and Myers2005). Their ‘programs’ will be shared with others and extended or adapted to other problems. The focus of our research in this area is learning procedure descriptions from users through tutorial instruction. An extensive survey of this area revealed that people find it very natural to teach procedures by giving general instructions but that typically give poor instruction. We used descriptions of data analysis workflows built by biologists and shared in a social website, and developed a knowledge acquisition system that can take such descriptions in natural language and create workflows for the user (Groth & Gil, Reference Groth and Gil2009a, Reference Groth and Gil2009b).

We are currently developing an approach to learn procedures from human tutorial instruction given in natural language, where the system uses heuristics to handle ambiguities and other imperfections in the instruction (Gil et al., Reference Gil, Ratnakar and Fritz2011).

5 Functioning with limited knowledge

Our knowledge acquisition systems enabled unsophisticated users to enter knowledge about complex processes in expert-level domains. Alas, although the knowledge was mostly correct, the missing bits did not allow the system to reason appropriately about the task. Perfect knowledge cannot be a requirement. Knowledge systems must be able to operate despite containing varying quality and coverage. The Web is full of broken links, which was traditionally considered unacceptable in hypertext circles. Similarly, knowledge systems cannot assume that the knowledge will be consistent and complete and that it can always be subject to such assumptions typically made for reasoning in first-order logic.

We turned to research on human learning to understand the principles and cognitive approaches that humans take when acquiring knowledge incrementally through a lesson (Kim & Gil, Reference Kim and Gil2002, Reference Kim and Gil2003; Gil & Kim, Reference Gil and Kim2002). We studied this from the student's perspective as well as from the tutor's perspective regarding the organization of lessons and the expectations of the student's ability to reason with limited knowledge.

In order to provide a computer with the ability to understand what it knows and what knowledge it is missing, we are investigating meta-reasoning capabilities that reason over the contents of a knowledge base and detect gaps and inconsistencies. At any given point, the system should be aware of its knowledge gaps and decide whether they affect its ability to do specific kinds of problem solving. We have developed a framework to keep track of multiple alternative models of a procedure that evolve over time as additional information is provided (Kim & Gil Reference Kim and Gil2007; Gil et al., Reference Gil, Kim and Spraragen2010a; Kim et al., Reference Kim, Myers, Gervasio and Gil2010). These techniques are used in our work on learning procedures from natural instruction mentioned above (Gil et al., Reference Gil, Ratnakar and Fritz2011).

6 Distributed problem solving

In contrast with early knowledge-based systems, today both knowledge and reasoning tend to be physically and organizationally distributed on the Web. Often, the knowledge sources needed for a task reside in distributed subsystems. Reasoning functions may also be distributed, for example, as provided by third-party services. Knowledge development may also be distributed, formed by assembling knowledge bases (or ontologies) that are separately developed.

Our research is looking at distributed knowledge sources and distributed reasoning in multi-institutional scientific collaborations. Some institutions may provide access to their data as a repository or as a remote service, while others may contribute software and tools to process data. Scientists in collaboration develop applications that retrieve, process, characterize, and store data. Our work focuses on computational workflows to represent declaratively the application software components and the dataflow among them (Gil, Reference Gil and Artz2006). We have developed semantic representations of workflows that can be used to reason about the data and the processing steps to automatically generate workflows as well as metadata descriptions of new data products that result from the computations (Gil, Reference Gil2009). Our algorithms to reason about semantic workflows assume that data repositories and software repositories are distributed and managed separately from the workflow system (Gil et al., Reference Gil, Gonzalez-Calero, Kim, Moody and Ratnakar2010b). This is a major departure from today's planning and reasoning algorithms, which assume that all the pertinent axioms are accessible to a centralized reasoner. Our algorithms call out to the external repositories with well-defined requests, which cause data-specific or component-specific reasoning at the remote sites.

A major component of this research is a collaboration with grid computing researchers to combine workflow reasoning with workflow execution planning (Deelman et al., Reference Deelman, Blythe, Gil, Kesselman, Mehta, Vahi, Blackburn, Lazzarini, Arbree, Cavanaugh and Koranda2003, Reference Deelman, Singh, Su, Blythe, Gil, Kesselman, Mehta, Vahi, Berriman, Good, Laity, Jacob and Katz2005; Maechling et al., Reference Maechling, Chalupsky, Dougherty, Deelman, Gil, Gullapalli, Gupta, Kesselman, Kim, Mehta, Mendenhall, Russ, Singh, Spraragen, Staples and Vahi2005; Gil et al., Reference Gil, Ratnakar, Deelman, Mehta and Kim2007a, Reference Gil, Deelman, Ellisman, Fahringer, Fox, Gannon, Goble, Livny, Moreau and Myers2007b; Kumar et al., 2009). We have applied these ideas to improve compiler optimization (Hall et al., Reference Hall, Gil and Lucas2008), resource-bound computations (Kumar et al., Reference Kumar, Kurc, Ratnakar, Kim, Mehta, Vahi, Nelson, Sadayappan, Deelman, Gil, Hall and Saltz2010), and scientific application performance (Woollard et al., Reference Woollard, Medvidovic, Gil and Mattmann2008).

Finding relevant components in distributed architectures is a problem for users. We have developed matchers that are given a natural language description of a task by a user and find relevant agents available to automate that task (Chalupsky et al., Reference Chalupsky, Gil, Knoblock, Lerman, Oh, Pynadath, Russ and Tambe2001; Gil & Ramachandran, Reference Gil and Ramachandran2001; Gil & Ratnakar, Reference Gil and Ratnakar2008). This capability is crucial for the approaches mentioned above to enable users to create and reuse workflows (Gil et al., Reference Gil, Kim, Florez, Ratnakar and Gonzalez Calero2009), as well as to specify procedures through tutorial instruction (Groth & Gil, Reference Groth and Gil2009a, Reference Groth and Gil2009b; Gil et al., Reference Gil, Ratnakar and Fritz2011).

7 Provenance and trust

New knowledge is often obtained from open sources on the Web, whether they be Web pages, people, mashups, or services. These sources have varying quality and coverage, and may be incomplete and contradict one another. The information is often of unknown origins and there is often no prior history with many of the sources that may be used to assess their reputation.

One focus of this research is how to determine whether to trust a particular piece of information provided by a source. Most existing trust systems are centered around the notion of entity trust, that is, whether or not to trust a given entity (Artz & Gil, Reference Artz and Gil2007). We defined content trust as a finer-grained model than entity trust in that it assigns trust to pieces of information rather than the overall entity. We identified major factors that affect trust in information sources (Gil & Artz, Reference Gil and Artz2007). We also developed a mathematical model and algorithms to derive source reputation from individual trust ratings (Gil & Ratnakar, Reference Gil and Ratnakar2002a; Gil & Artz, Reference Gil and Artz2006).

Another aspect of this research is on tracking the provenance of processed information, which is synthesized by processing inputs from many individual sources. Representing the provenance of information is key to being able to track what sources were used and how they were combined (Gil & Ratnakar, Reference Gil and Ratnakar2002a). We investigated provenance in knowledge bases, where in order to be trusted each axiom must be tied to the source used to create it (Gil & Ratnakar, Reference Gil and Ratnakar2002b). Provenance of knowledge base axioms is even more critical when the knowledge base is to be developed and used by a community, as shown by our study of the most widely adopted biomedical ontology to date (Bada et al., Reference Bada, Stevens, Goble, Gil, Ashburner, Blake, Cherry, Harris and Lewis2004). We also investigated provenance in workflow systems, and augmented existing provenance models that capture execution details with process and data semantics (Kim et al., Reference Kim, Deelman, Gil, Mehta and Ratnakar2008). As described earlier, our semantic workflow representations can be used to reason about metadata properties of data sources as well as new data products as they are processed by the workflow steps, resulting in detailed provenance records that support semantic queries (Kim et al., Reference Kim, Gil and Ratnakar2006).

Recent research aims at creating a better understanding of provenance requirements, and at fostering shared representations and standards for provenance of Web resources (Gil, Reference Gil2010; Moreau et al., Reference Moreau, Clifford, Freire, Futrelle, Gil, Groth, Kwasnikowska, Miles, Missier, Myers, Plale, Simmhan, Stephan and Van den Bussche2010).