Browsing by Subject "Knowledge representation"
Now showing 1 - 9 of 9
Results Per Page
Sort Options
Item Answering questions about dynamic domains from natural language using ASP(2011-08) Todorova, Yana; Gelfond, Michael; Watson, Richard; Zhang, YuanlinAnswer Set Programming (ASP) is a knowledge representation methodology that has well-established theoretical foundations and good practical uses. The goal of my dissertation was to build an automatic system for answering non-trivial questions from texts in natural language. This is an important task, because the results are very useful in many areas. The final result of this work is an elaboration tolerant question answering system MQA capable of giving provably correct answers. We also used this research to test our reasoning techniques, such as reasoning in dynamic domains, where movement is involved, and reasoning about changes in cardinalities. The original discourse was written in our controlled language MCL , which allowed us to remove a variety of natural language phenomena and to focus on limited grammar rules and on a restricted vocabulary. For the actual reasoning, we used ASP, because of its nonmonotonic features, and its ability to represent defaults and dynamic domains. Thus, given a discourse and a question in our controlled natural language MCL, we first generated a new logic form representation. We represented the knowledge using action language ALM and we included background information not found in the original text. After that, we performed commonsense reasoning using ASP axioms. Finally, we obtained the correct and expected answer to the question.Item The diagrammatic specification and automatic generation of geometry subroutines(2010-05) Li, Yulin, Ph. D.; Novak, Gordon S.; Porter, Bruce; Boyer, Robert; Gouda, Mohamed; Kant, ElaineProgramming has advanced a great deal since the appearance of the stored-program architecture. Through the successive generations of machine codes, assembly languages, high-level languages, and object-oriented languages, the drive has been toward program descriptions that express more meaning in a shorter space. This trend continues today with domain-specific languages. However, conventional languages rely on a textual formalism (commands, statements, lines of code) to capture the programmer's intent, which, regardless of its level of abstraction, imposes inevitable overheads. Before successful programming activities can take place, the syntax has to be mastered, names and keywords memorized, the library routines mastered, etc. Existing visual programming languages avoid some of these overheads, but do not release the programmer from the task of specifying the program logic, which consumes the main portion of programming time and also is the major source of difficult bugs. Our work aims to minimize the demands a formalism imposes on the programmer of geometric subroutines other than what is inherent in the problem itself. Our approach frees the programmer from syntactic constraints and generates logically correct programs automatically from program descriptions in the form of diagrams. To write a program, the programmer simply draws a few diagrams to depict the problem context and specifies all the necessary parameters through menu operations. Diagrams are succinct, easy to learn, and intuitive to use. They are much easier to modify than code, and they help the user visualize and analyze the problem, in addition to providing information to the computer. Furthermore, diagrams describe a situation rather than a task and thus are reusable for different tasks—in general, a single diagram can generate many programs. For these reasons, we have chosen diagrams as the main specification mechanism. In addition, we leverage the power of automatic inference to reason about diagrams and generic components—the building blocks of our programs—and discover the logic for assembling these components into correct programs. To facilitate inference, symbolic facts encode entities present in the diagrams, their spatial relationships, and the preconditions and effects of reusable components. We have developed a reference implementation and tested it on a number of real-world examples to demonstrate the feasibility and efficacy of our approach.Item Integrating ASP and CLP systems: computing answer sets from partially ground programs(Texas Tech University, 2007-12) Mellarkod, Veena S.; Gelfond, Michael; Watson, Richard; Zhang, Yuanlin; Son, Tran CaoAnswer set programming (ASP) has emerged as a declarative paradigm for knowledge representation and reasoning. In this approach, a logic program is used to represent the knowledge of the domain and various tasks are reduced to computing answer sets of this program. ASP languages A-Prolog and CR-Prolog have been proven as powerful tools for constructing complex reasoning systems. Constraint logic programming (CLP) emerged as an alternate paradigm through the fusion of logic programming and constraint solving. A CLP solver thus integrates resolution techniques from logic programming and constraint solving techniques from constraint satisfaction. While ASP is expressive for knowledge representation and reasoning, CLP solvers are efficient in reasoning with numerical constraints. Every state-of-the-art ASP solver computes answer sets of programs from their ground equivalents. Though these systems solve large industrial problems, the ground programs become huge and unmanageable. This is especially true when programs contain variables that range over large numerical domains; huge memory requirements eventually force the solvers to fail. The goal of this research is to address this issue by integrating different types of reasoning techniques to compute answer sets of programs. First, we investigate the integration of answer set reasoning, a form of abduction, and constraint solving techniques. We design a collection of languages, V(C), parameterized over a class C of constraints. An instance ACo from this family is studied as a knowledge representation tool. An algorithm to compute answer sets of ACo programs is developed. An ACo solver is built that computes answer sets from partially ground programs. The use of this language and the efficiency of the solver are demonstrated. We extend our investigation to develop methods to include resolution techniques. We design a collection of languages AC(C) parameterized over a class C of constraints. We develop an algorithm to compute answer sets of AC(C) programs from their partial ground instances by integrating the four reasoning techniques and prove correctness. A solver is built to compute answer sets for a class of AC(C) programs. Our work is a significant step to declaratively solve problems that cannot be solved by pure ASP or CLP solvers. The solvers built are the first to tightly integrate different reasoning techniques to compute answer sets from partial ground programs.Item Modality and identity(Texas Tech University, 1996-12) Cochran, John MurrayKripke semantics will be discussed in some detail along with a fairly common modification which will be central to the arguments of this paper. In order to explicate this modification a discussion of several semantic issues will be helpful. These will include the difference between representational semantics and interpretational semantics, how interpretational semantics can be seen as a type of counterpart semantics, and how the modified Kripke semantics can be viewed as a representational-interpretational hybrid semantics. Several types of modality will be discussed. The paper will be primarily concerned with alethic modality as opposed to deontic, temporal or other general categories of modality although epistemic modality will be discussed briefly. The types of modality which will be discussed include narrow and broad logical modalities, intermediaries between these two types of logical modalities which include mathematical modality and what will be termed semantic modality, and natural modality. Relations between these modalities will be investigated with particular attention to the semantic theories which will be presented and several common misconceptions about modal logic will be dispelled.Item Modular action language ALM for dynamic domain representation(2012-08) Inclezan, Daniela; Gelfond, Michael; Lifschitz, Vladimir; Watson, Richard; Zhang, YuanlinThe goal of this dissertation is to define a modular action language, ALM, for the elaboration tolerant representation of knowledge about medium-size dynamic domains. Discrete dynamic domains can be theoretically captured by transition diagrams. The problem of concisely and precisely specifying such diagrams was the subject of study for several decades. Action languages were introduced as a solution to this problem. However, traditional action languages are not suitable for the specification of medium and large size domains because they lack the means for structuring knowledge and do not thoroughly address the problem of representing objects of the domain. Language ALM addresses these issues. The task of designing a modular action language is a relevant one in the field of AI: it is the first step towards the creation of intelligent agents capable of reasoning about, or acting in a wide variety of dynamic environments. More importantly, the design of ALM allows us to better understand how to represent knowledge. Other modular action languages exist (e.g., MAD, TAL-C), but they correspond to different intuitions and knowledge representation styles. ALM is an alternative to these languages. The design of ALM was not a trivial task. ALM is intended to be a simple but powerful language that would allow for elegant representations of a variety of dynamic domains. Hence, our main design and evaluation criteria were its expressive power and its simplicity and elegance. Generally, there is a tension between the two, which makes it challenging to design a modular action language. Our language is intended to facilitate the creation of knowledge representation libraries, as well as the stepwise development, testing, and readability of a knowledge base. This is achieved by separating the description of a domain into two parts: a general theory, which consists of several modules that can be reused in modeling other domains, and an interpretation of this theory, which is particular to the specific domain. As well, ALM introduces classes of objects that can be described in terms of previously defined ones. Classes have attributes that are optional, a feature that contributes to the elaboration tolerance of the language. We tested that these and other features of our language accomplish our goal by modeling several domains, both commonsensical (e.g., motion) and specialized (e.g., cell division), in ALM. We were satisfied with the formalizations that resulted and with the capabilities of our language. In this dissertation, we formally present language ALM, illustrate the methodology of its use for knowledge representation and problem solving, report on an application of ALM to question answering, and compare our language with the closest existing modular action language, MAD.Item A modular language for describing actions(2009-12) Ren, Wanwan; Lifschitz, Vladimir; Boyer, Robert; Gelfond, Michael; Novak, Gordon; Porter, BruceThis dissertation is about the design of a modular language for describing actions. The modular action description language, MAD, is based on the action language C+. In this new language, the possibility of "importing" a module allows us to describe actions by referring to descriptions of related actions introduced earlier, rather than by listing all effects and preconditions of every action explicitly. The use of modular action descriptions eliminates the need to reinvent theories of similar domains over and over again. Another advantage of this representation style is that it is similar to the way humans describe actions in terms of other actions. We first define the syntax of a fragment of MAD, called mini-MAD, and then extend it to the full version of MAD. The semantics of mini-MAD is defined by grounding action descriptions and translating them into C+. However, for the full version of MAD, it would be difficult to define grounding. Instead, we use a new approach to the semantics of variables in action descriptions, which is based on more complex logical machinery---first-order causal logic. Grounding is important as an implementation method, but we argue that it should be best avoided in the definition of the semantics of expressive action languages. We show that, in application to mini-MAD, the two semantics are equivalent. Furthermore, we prove that MAD action descriptions have some desirable, intuitively expected mathematical properties. We hope that MAD will make it possible to create a useful general-purpose library of standard action descriptions and will contribute in this way to solving the problem of generality in Artificial Intelligence.Item Ontology as a means for systematic biology(2011-05) Tirmizi, Syed Hamid Ali; Miranker, Daniel P.; Batory, Don; Grauman, Kristen; Gutell, Robin; Porter, BruceBiologists use ontologies as a method to organize and publish their acquired knowledge. Computer scientists have shown the value of ontologies as a means for knowledge discovery. This dissertation makes a number of contributions to enable systematic biologists to better leverage their ontologies in their research. Systematic biology, or phylogenetics, is the study of evolution. “Assembling a Tree of Life” (AToL) is an NSF grand challenge to describe all life on Earth and estimate its evolutionary history. AToL projects commonly include a study a taxon (organism) to create an ontology to capture its anatomy. Such anatomy ontologies are manually curated based on the data from morphology-based phylogenetic studies. Annotated digital imagery, morphological characters and phylogenetic (evolutionary) trees are the key components of morphological studies. Given the scale of AToL, building an anatomy ontology for each taxon manually is infeasible. The primary contribution of this dissertation is automatic inference and concomitant formalization required to compute anatomy ontologies. New anatomy ontologies are formed by applying transformations on an existing anatomy ontology for a model organism. The conditions for the transformations are derived from observational data recorded as morphological characters. We automatically created the Cypriniformes Gill and Hyoid Arches Ontology using the morphological character data provided by the Cypriniformes Tree of Life (CTOL) project. The method is based on representing all components of a phylogenetic study as an ontology using a domain meta-model. For this purpose we developed Morphster, a domain-specific knowledge acquisition tool for biologists. Digital images often serve as proxies for natural specimens and are the basis of many observations. A key problem for Morphster is the treatment of images in conjunction with ontologies. We contributed a formal system for integrating images with ontologies where images either capture observations of nature or scientific hypotheses. Our framework for image-ontology integration provides opportunities for building workflows that allow biologists to synthesize and align ontologies. Biologists building ontologies often had to choose between two ontology systems: Open Biomedical Ontologies (OBO) or the Semantic Web. It was critical to bridge the gap between the two systems to leverage biological ontologies for inference. We created a methodology and a lossless round-trip mapping for OBO ontologies to the Semantic Web. Using the Semantic Web as a guide to organize OBO, we developed a mapping system which is now a community standard.Item Role-governed categorization(2009-12) Goldwater, Micah Balser; Markman, Arthur B.; Echols, Catharine H.; Griffin, Zenzi; Loewenstein, Jeffrey; Schnyer, DavidTheories of categorization typically assume that categories are represented by some set of features that describe the properties of category members. However this view of category representation is incomplete. This dissertation lays out a framework for category representation, following Markman and Stilwell (2001), that creates a taxonomy of categories based on different components of relational structures. Relational categories are categories of entire relational systems while, role-governed categories, are represented as the roles in these systems. Lastly, thematic-relation categories group entities together that play complementary roles within a system. Four experiments are presented in support of this framework. They contrast thematic-relation categorization with role-governed categorization. Thematic-relation categorization entails categorizing objects together that play different roles within a domain, while role-governed categorization entails categorizing two entities that play the same role across domains. When the two are put in direct conflict, people prefer to form a thematic-relation category because within-domain connections are easier to find than across-domain connections. The purpose of the four experiments is to examine ways to boost the preference for role-governed categorization, thus revealing underlying processes. Here, role-governed categorization is facilitated in two ways. Experiment 1 re-frames the question of category formation as novel word extension. Natural role-governed categories have labels while thematic-relation categories do not. This pattern is reflected in the measured behavior as novel labels are extended across members of role-governed categories more readily than across members of thematic-relation categories. By claiming relational structures are critical to category representation, the framework described in this dissertation predicts that role-governed categorization and analogical reasoning share underlying mechanisms. Experiments 2-4 examine how making an analogy between the members of role-governed categories facilitates forming such categories. When making an analogy, people align the relational representations of a pair of domains, putting entities into correspondence by role, ignoring featural dissimilarities. When analogical comparison is induced, the rate of role-governed categorization is shown to double as compared to a baseline with no such analogical processes. The thesis concludes by outlining several future lines of research generated by unifying the fields of analogy and concept learning.Item Towards Answer Set Programming Based Architectures for Intelligent Agents(2010-12) Chintabathina, Sandeep; Watson, Richard; Gelfond, Michael; Zhang, Yuanlin; Balduccini, MarcelloThe design of intelligent agents is an important research area in the field of Artificial Intelligence. Research in this area has led to the development of agent architectures that support various tasks such as reasoning, planning, diagnosis etc. One such architecture is based on the agent repeatedly executing the observe-think-act loop. In this architecture a dynamic system is viewed as a transition diagram whose nodes represent possible physical states of the system and whose arcs are labeled by actions. One of the approaches to describing these diagrams is a theory based on action languages, which are high-level languages for reasoning about actions and their effects. One such action language is AL. A theory in AL describes a transition diagram that contains all possible trajectories of a given dynamic system. However, it was not designed to reason about properties of a domain that change continuously with time. In this dissertation we present action language H which extends AL with the ability to reason about continuous change. We design this language by extending the signature of AL with a collection of numbers for representing continuous time and a collection of functions defined over time (processes). Like AL, H is based on transition diagram based semantics. We model a variety of examples in H to demonstrate that H is very useful for knowledge representation. We compared H with other approaches and discovered that action descriptions of H are simpler, concise and elaboration tolerant. We studied timed automata and discovered that H expands timed automata. An action description of AL is implemented by translating it into a program of answer set programming (ASP) and computing answer sets of the resulting program. Thus, various tasks of the agent can be reduced to asking questions about answer sets of programs. In this dissertation, we came up with an encoding of action descriptions of H into a variant of ASP called AC. Using this encoding, several agent tasks can be reduced to asking questions about answer sets of AC programs. With the help of existing solvers we are able to run our encodings and confirm that the resulting answer sets are the ones we expected.