IRList Digest Monday, 1 December 1986 Volume 2 : Issue 67 Today's Topics: Abstracts - NSF IST Awards for Fiscal Year 1986 - Part 5 of 5 News addresses are ARPANET: fox%vt@csnet-relay.arpa BITNET: foxea@vtvax3.bitnet CSNET: fox@vt UUCPNET: seismo!vtisr1!irlistrq ---------------------------------------------------------------------- Date: Fri, 21 Nov 86 18:38:14 est From: vtopus!fox (Ed Fox) Subject: Information on NSF awards, sent by J. Deken at NSF Fiscal Year 1986 Research Projects Funded by the Information Science Program (now Knowledge and Database Systems Program) Part 5 of 5 IST-8640053 $59,178 - 12 mos. Sharon C. Salveter Boston University Transportable Natural Language Database Update - - - The use of natural languages such as English to interact with computer databases has been an active research area for many years. Most projects in this area have been limited to handling requests for information already in the database. This research project uses verbgraphs, a formal representation technique previously developed by the Principal Investigator, as a basis for also handling the more difficult task of making changes to this information in the database. General information needed to handle natural language is kept separate from information about a specific application, in order to allow the system to be used for a variety of applications with as few changes as possible. The project will advance both the theory and the applications of database management systems and natural language understanding. _____ IST-8610293 $80,630 - 12 mos. Glenn R. Shafer University of Kansas Main Campus Belief Functions in Artificial Intelligence - - - This research develops and investigates the "belief function" approach to representing uncertainty. In realistic situations which are now being modeled by expert computer systems, hypotheses, facts, and values are usually not held with certainty. Classic approaches to uncertainty such as probability have a firm mathematical foundation but often require more input data than realistic expert systems have available. In the belief function approach pioneered by Dempster and Shafer, uncertain elements are not assigned probabilities but degrees of belief. The present theoretical research extends the range of situations where belief functions can be used, and develops procedures which will allow computers to reason efficiently to derive new hypotheses and conclusions from belief function representations. The representation of uncertainty is a pivotal element in modern artificial intelligence systems. The dual (and often competing) goals are to provide new frameworks which will be expressive enough to capture realistic situations, and yet sufficiently formal that the accuracy of derived conclusions can be trusted. _____ IST-8603214 $85,583 - 12 mos. William Shaw University of North Carolina An Evaluation and Comparison of Term and Citation Indexing - - - Text documents are produced and stored in vast quantities today. Consequently, it is nearly impossible to locate relevant text documents for any particular purpose without computerized searching. For reasons of efficiency, computer systems for searching documents do not use the entire text of such documents; only a compact representation of each document is stored in memory, along with the information necessary to locate the original text if it should be needed. This research investigates two of the more common components of compact representations for documents: A representation based on the terms contained in the text, and a representation based on the documents which the text cites. Both of these representations are evaluated by extensive judgements (by human experts) of the relevance of documents retrieved using them. The research illuminates the optimal use of each alternate type of representation, as well as a comparison between the two alternatives. The importance of the research is that it provides a solid base of empirical evidence and a benchmark document collection for evaluating information retrieval strategies. Although new architectures for document representation and retrieval may make some of the specific style of queries obsolete, the value of the test collection and the insights about intrinsic content (term) versus extrinsic context (citation) analysis for documents will be valuable for future work. _____ DMS-8606178 $20,000 - 12 mos. Paul C. Shields University of Toledo Mathematical Sciences: Entropy in Ergodic Theory, Graph Theory and Statistics - - - Professor Shields was one of the first American mathematicians to become actively involved in the subject of information theory, and he has been one of the creative contributors. His work cuts across traditional disciplinary boun- daries in mathematics, for it utilizes ideas from ergodic theory, information theory, statistics, data compression, graph theory, diffusion theory, and com- puter science. He proposes here to continue his highly original recent work in an exciting international collaboration with some of the world's outstanding information theorists. The project involves entropy and asymptotic estimates for algorithms for compression of binary data in computer science, tests for statistical independence, and applications in the communications field. The latter might ultimately impact the current state of our knowledge in speech coding and recognition, spectral estimation, and pattern recognition. This is exciting, innovative, multidisciplinary work that possesses the added value of international cooperation among world experts. _____ IST-8607849 $101,839 - 12 mos. Edward Smith BBN Laboratories, Inc. A Computational Approach to Decision-Making - - - The purpose of this collaborative research is to develop a theory of how humans make decisions. The theory is developed as a computational theory, using the representations and processes currently prevalent in cognitive science and artificial intelligence research. The theory explains the formation of complex concepts. Additionally, it accounts for people's incorrect estimates of the likelihood with which events will occur. The theory is tested through psychological experimentation. Knowledge about how people make decisions and estimate probabilities is useful to all decision makers. Additionally, a computational theory of the process allows the development of computer based decision-making aids. _____ IST-8609599 $80,963 - 12 mos. Paul Smolensky University of Colorado at Boulder Inference in Massively Parallel Artificial Intelligence Systems - - - The purpose of this research is to study how parallel Artificial Intelligence (AI) systems can make inferences which allow full use of the information in the computer system's memory. The approach here is to synthesize the varying methods of inference currently used in the field in order to formulate general principles of inference in parallel systems. The synthesis is accomplished by applying the varying inference methods to a set of inference problems and developing the resulting set of core models. These models are studied through mathematical analysis and computer simulation and the relationships among them are found. Artificial intelligence systems need to be able to make inferences in order to use whatever knowledge they have stored. This full use of knowledge is one of the main ways in which AI systems are powerful. This research deals with inference methods and contributes to the development of more sophisticated computer systems. _____ IST-8644907 $15,634 - 12 mos. Frederik Springsteel University of Missouri Formalization of Entity-Relationship Diagrams - - - The design of the logical structure of a database is an important component of the design of many information systems, and the entity-relationship model is frequently used as a tool in such design. Most of the work on this approach has emphasized its practical applications rather than its theoretical aspects. The purpose of this research is to develop more formal analyses of the assumptions and benefits of this model and to relate it to other models such as the rela- tional model, which are better understood. The significance of this research lies in its potential to contribute to the theory and practice of database design. _____ IST-8640120 $66,004 - 12 mos. Robert E. Stepp University of Illinois at Urbana Discovering Underlying Concepts in Data Through Conceptual Clustering - - - The purpose of this research is to develop theoretical principles, algorithms, and practical methods for the discovery of underlying concepts in descriptions of objects or situations through the use of conceptual clustering. A computer system is being developed that will build a conceptual classification for descriptions of objects. It acts by generating concepts that describe object classes and then partitioning the given objects into the appropriate classes. The generated concepts are encoded as conjunctive statements in an extended predicate calculus notation and are optimized with respect to a user-supplied classification evaluation function. The techniques are evaluated by examining selected problems, such as discovering classes of simple organic molecules and discovering kinship units within the kinship network. The significance of the research lies in its potential to contribute to the design and development of computer-based knowledge resource systems. _____ IST-8516313 $60,907 - 12 mos. Richmond H. Thomason Mellon-Pitt-Carnegie Corp. Nonmonotonic Reasoning - - - Classical logic is inadequate in many ways for modeling real-world reasoning by computers. In particular, classical logic is monotonic - adding information or premises never reverses previously valid conclusions. By contrast, the appearance of new information in real world situations often causes previous conclusions or judgements to be reversed. This research, an interdisciplinary collaboration of computer scientists, philosophers, and logicians, explores real-world, nonmonotonic reasoning in intelligent computer systems. In particular, the research investigates how intelligent systems can arrive at reasonable conclusions by adding assumptions to their current information, and how intelligent computer programs should cause assumptions to be inherited in individual cases of general situations. The research provides significant insight into the strengths and weaknesses of established logical approaches to reasoning, as well as breaking ground in the implementation of realistic reasoning networks in computer systems. _____ IST-8516330 $63,854 - 12 mos. David S. Touretzky Carnegie-Mellon University Distributed Representations for Symbolic Data Structures - - - In this project the investigator is studying the representation of symbols in parallel computers. Symbols are being represented by the presence of activity in the (processing units) of the computer. Each processing unit contributes to the representation of many symbols and particular symbols are identified by activity in some subset of units. This particular method of representation is called a "parallel distributed" method. The investigator is studying the representation of symbols in parallel computers by implementing some common symbolic structures in a parallel computer called the Boltzmann machine. Additionally, he is studying the mathematical properties of his implementations. Parallel computers offer a plausible theory of the brain. Using a parallel computer to implement the kind of symbolic data structure needed for theories of cognition allows us to link theories of mind with theories of brain. Making this link, will give us more complete theories of cognition and better computer implementations of these theories, ultimately producing better artificial intelligence systems. _____ IST-8517289 $164,786 - 12 mos. Joseph F. Traub Columbia University The Information Level: Effective Computing with Partial, Contaminated, and Costly Information - - - The information available to solve real-world problems is usually only incomplete and contaminated by noise or systematic error. The principal investigators are developing in this research a theory about such problems, where partial and contaminated information must be used as well as possible. Potential applications for the theory, which is called "Information Based Complexity Theory" range from medical imaging and robot vision to economics. The key goal of this theory is to explain how the accuracy of solving a given problem is related to the amount and kind of information available. The project will be significant both for the general mathematical methods it develops and for the insights it provides into formulating and refining computer systems and algorithms. _____ IST-8544806 $121,222 - 12 mos. Jeffrey D. Ullman Stanford University Implementation of Logical Query Languages for Databases - - - This research will develop a logic language for databases that will be substantially more powerful than current formal languages such as relational calculus. This new language will allow for the use of a knowledge base of rules, as well as rules for performing integrity and security functions. This new language will be a form of parallel prolog, an important artificial intelli- gence language. The significance of this research lies in the fact that it will provide a very natural language for querying databases. _____ IST-8511348 $30,383 - 12 mos. Kenneth Wexler University of California at Irvine Learnability and Parsability (see description of award to Berwick) _____ IST-8514890 $80,000 - 12 mos. R. Wilensky and R. Alterman University of California at Berkeley Adaptive Planning - - - In this project the PIs look at issues concerning automated planning systems. They are developing methods for "adaptive planning" (using familiar plans in unfamiliar situations). The issue is being addressed through the development of a computer system in which old plans are first generalized and then appropriately specialized. Robots need to plan in order to act independently. Adaptive planning allows a system to plan in novel situations. By addressing issues of adaptive planning, this project works towards the long-range goal of building robots which can function in situations that they have not previously encountered. _____ IST-8600788 $81,660 - 12 mos. Robert T. Winkler Duke University Combining Dependent Information: Models and Issues - - - In realistic applications of computers to modeling knowledge and decision pro- cesses, information is often available only partially about events of interest. In addition, many sources may contribute information about the same event, and these sources in turn are generally not independent of each other. This research investigates ways in which such uncertain, overlapping, interrelated information about events may be combined automatically to improve the certainty of knowledge and the appropriateness of decision-making. A key component of the research is to test alternative formal models of uncertain information by experiments in real world applications. This research is significant both for the explication and comparision of various formal models of uncertainty, and for the critical feedback obtained by observing the performance of competing models in realistic situations. _____ IST-8644767 $38,474 - 12 mos. Ronald R. Yager Iona College Specificity Measures of Information in Possibility Distributions - - - Possibility distributions provide a formalism for representing some types of uncertainty in information. A measure of the information content in a possibility distribution is introduced; this measure is called a specificity measure. The objective of this research is the investigation of properties, uses, and formulations of the specificity measures associated with possibility distributions and fuzzy subsets. The trade-offs involved in providing information that is both specific and correct are also investigated. The significance of this research lies in its potential contribution to the development of computer based systems which can handle imprecise and uncertain information. _____ IST-8644435 $50,878 - 12 mos. Po-Lung Yu University of Kansas Habitual Domain Analysis for Effective Information Interface and Decision Support - - - Many nontrivial decision and conflict problems cannot readily be solved by traditional optimization and game theoretic techniques. The concepts of second order games and habitual domains can be used to approach such problems. This research investigates several topics in the development and use of habitual domains, which provide a framework for models of individual and organizational users of information systems. Specific goals include identifying effective means for specifying and using habitual domains and developing approaches to using them in information systems. The significance of this research lies in its potential for improving computer-based decision systems. _____ IST-8642900 $108,182 - 12 mos. Lotfi A. Zadeh University of California at Berkeley Management of Uncertainty in Expert Systems - - - Much of the information which is resident in the knowledge base of a typical expert system is imprecise or incomplete. This research provides an approach, based upon the use of fuzzy logic, for handling this problem. The approach provides a computational framework for dealing with fuzzy quantifiers, e.g., most, many, almost, all, etc., and thereby makes it possible to compute with imprecisely known probabilities and certainty factors. In this approach the propositions which form the knowledge base of an expert system may be expressed in a canonical form which places in evidence the variables which are constrained by the constituent proposition. From the canonical forms, one can construct a global possibility distribution which reduces the deduction of a conclusion to the solution of a nonlinear system. This research will provide an approach for the systematic inclusion in expert systems of the types of imprecise rules used by experts. _____ IST-8605163 $19,776 - 12 mos. Maria Zemankova University of Tennessee at Knoxville Travel to the International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems - - - This award supports travel funds for 15 U.S. participants for the International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems. The conference takes place in Paris, France on June 30, 1986 through July 4 1986. The conference will be co-sponsored by the International Fuzzy Systems Association. The conference topics cover uncertainty management, fuzzy sets, possibility measures, and the mathematical theory of evidence. The conference provides an opportunity for strengthening the quality of research in reasoning with uncertainty, as well as facilitating international communication in the area. _____ IST-8600616 $97,727 - 12 mos. Pranas Zunde Georgia Institute of Technology A Study of Word Association Aids in Information Retrieval - - - This research investigates the usefulness of word associations - the additional words an individual can think of in response to an initial stimulus word - in assisting information retrieval. Advanced information retrieval systems of the future will be expected to go beyond simply sorting and matching terms with documents. These systems must become capable of understanding and reasoning, both about the knowledge contained in a collection of documents and about the user's intentions. As investigated in this proposal, knowledge of word associations represents one such type of understanding an information retrieval system may exhibit to enhance its performance. The significance of this project is that it probes a new dimension of semantic content for keyword searching, virtually unexplored in information retrieval studies to date. User/system interaction observations gained in the process are likely to have additional impact on information retrieval concepts. ------------------------------ END OF IRList Digest ********************