The notion of class is ubiquitous in computer science and is central in many formalisms for the representation of structured knowledge used both in knowledge representation and in databases. In this paper we study the basic issues underlying such representation formalisms and single out both their common characteristics and their distinguishing features. Such investigation leads us to propose a unifying framework in which we are able to capture the fundamental aspects of several representation languages used in different contexts. The proposed formalism is expressed in the style of description logics, which have been introduced in knowledge representation as a means to provide a semantically well-founded basis for the structural aspects of knowledge representation systems. The description logic considered in this paper is a subset of first order logic with nice computational characteristics. It is quite expressive and features a novel combination of constructs that has not been studied before. The distinguishing constructs are number restrictions, which generalize existence and functional dependencies, inverse roles, which allow one to refer to the inverse of a relationship, and possibly cyclic assertions, which are necessary for capturing real world domains. We are able to show that it is precisely such combination of constructs that makes our logic powerful enough to model the essential set of features for defining class structures that are common to frame systems, object-oriented database languages, and semantic data models. As a consequence of the established correspondences, several significant extensions of each of the above formalisms become available. The high expressiveness of the logic we propose and the need for capturing the reasoning in different contexts forces us to distinguish between unrestricted and finite model reasoning. A notable feature of our proposal is that reasoning in both cases is decidable. We argue that, by virtue of the high expressive power and of the associated reasoning capabilities on both unrestricted and finite models, our logic provides a common core for class-based representation formalisms.
Normative expert systems have not become commonplace because they have been difficult to build and use. Over the past decade, however, researchers have developed the influence diagram, a graphical representation of a decision maker's beliefs, alternatives, and preferences that serves as the knowledge base of a normative expert system. Most people who have seen the representation find it intuitive and easy to use. Consequently, the influence diagram has overcome significantly the barriers to constructing normative expert systems. Nevertheless, building influence diagrams is not practical for extremely large and complex domains. In this book, I address the difficulties associated with the construction of the probabilistic portion of an influence diagram, called a knowledge map, belief network, or Bayesian network. I introduce two representations that facilitate the generation of large knowledge maps. In particular, I introduce the similarity network, a tool for building the network structure of a knowledge map, and the partition, a tool for assessing the probabilities associated with a knowledge map. I then use these representations to build Pathfinder, a large normative expert system for the diagnosis of lymph-node diseases (the domain contains over 60 diseases and over 100 disease findings). In an early version of the system, I encoded the knowledge of the expert using an erroneous assumption that all disease findings were independent, given each disease. When the expert and I attempted to build a more accurate knowledge map for the domain that would capture the dependencies among the disease findings, we failed. Using a similarity network, however, we built the knowledge-map structure for the entire domain in approximately 40 hours. Furthermore, the partition representation reduced the number of probability assessments required by the expert from 75,000 to 14,000.
Tao, Yumeng (University of California, Irvine) | Bhattacharjya, Debarun (IBM Thomas J. Watson Research Center) | Heching, Aliza R. (IBM Thomas J. Watson Research Center) | Vempaty, Aditya (IBM Thomas J. Watson Research Center) | Singh, Moninder (IBM Thomas J. Watson Research Center) | Lam, Felix (Clinton Health Access Initiative) | Varshney, Kush R. (IBM Thomas J. Watson Research Center) | Mojsilović, Aleksandra (IBM Thomas J. Watson Research Center)
Diarrhea is one of the leading killers of children under five years old in Nigeria. To tackle this challenge, many activities were conducted by government institutions, non-governmental organizations, and private companies to promote the usage of the best treatment for the disease: the combination of Zinc and Oral Rehydration Salts (ORS). One of the activities, undertaken by the Clinton Health Access Initiative (CHAI), is hiring and training peer detailers to explain the benefits of the treatment to patent and proprietary medicine vendors (PPMVs), a major source of primary healthcare in Nigeria. This paper investigates the effectiveness of this information dissemination program for treatments of children’s diarrhea in Nigeria. Two aspects are considered when evaluating the effectiveness of the program: awareness (knowledge) and availability (inventory) of Zinc and ORS among PPMVs. We performed exploratory data analysis and statistical hypothesis tests, and found that the percentage of PPMVs with the desired knowledge of treatments for children’s diarrhea increases significantly in most states in Nigeria after the peer detailing. On the other hand, no significant patterns are detected for the percentage of PPMVs with inventory of the treatments. Logistic regression models with confounding factors suggest that PPMVs promoted by CHAI have significantly higher ratios of both the knowledge and inventory of the best treatment for children’s diarrhea.
We address the problem of propositional logic-based abduction, i.e., the problem of searching for a best explanation for a given propositional observation according to a given propositional knowledge base. We give a general algorithm, based on the notion of projection; then we study restrictions over the representations of the knowledge base and of the query, and find new polynomial classes of abduction problems.
Independence -- the study of what is relevant to a given problem of reasoning -- has received an increasing attention from the AI community. In this paper, we consider two basic forms of independence, namely, a syntactic one and a semantic one. We show features and drawbacks of them. In particular, while the syntactic form of independence is computationally easy to check, there are cases in which things that intuitively are not relevant are not recognized as such. We also consider the problem of forgetting, i.e., distilling from a knowledge base only the part that is relevant to the set of queries constructed from a subset of the alphabet. While such process is computationally hard, it allows for a simplification of subsequent reasoning, and can thus be viewed as a form of compilation: once the relevant part of a knowledge base has been extracted, all reasoning tasks to be performed can be simplified.