Analogy-based domain analysis approach to software reuse

Domain analysis is an expansion of conventional requirements analysis. Domain analysis can support effective software reuse. However, domain analysis is time consuming and is limited to a particular application area. Analogical approaches to software reuse, on the other hand, often occur across domains. Analogical problem solving is a process of transferring knowledge from a well-understood base domain to a new target problem area. Analogy can facilitate software reuse for poorly understood problems or new application areas. Analogy shares similar concepts with reuse and some analogy theories have been applied to software reuse. However, current research on software analogy often overlooks the importance of analysis for the base domain and does not consider some critical aspects of analogy concepts. Reuse must be based on high quality artifacts, especially reuse across domains. This paper presents an approach to integrate domain analysis and analogy methods. In our view, domain analysis and software analogy have complementary roles. Domain analysis is regarded as a process to identify and supply necessary information for analogical transfer. Software analogy can provide the analyst with similar problems and solutions to reuse previous domain analysis knowledge or artifacts for a new domain. This paper presents case studies to demonstrate the increase of efficiency in applying the approach. Evaluation of the approach from various perspectives is also reported.     

Advantages of decision lists and implicit negatives in Inductive Logic Programming

This paper demonstrates the capabilities offoidl, an inductive logic programming (ILP) system whose distinguishing characteristics are the ability to produce first-order decision lists, the use of an output completeness assumption as a substitute for negative examples, and the use originally motivated by the problem of learning to generate the past tense of English verbs; however, this paper demonstrates its superior performance on two different sets of benchmark ILP problems. Tests on the finite element mesh design problem show thatfoidl’s decision lists enable it to produce generally more accurate results than a range of methods previously applied to this problem. Tests with a selection of list-processing problems from Bratko’s introductory Prolog text demonstrate that the combination of implicit negatives and intensionality allowfoidl to learn correct programs from far fewer examples thanfoil. This research was supported by a fellowship from AT&T awarded to the first author and by the National Science Foundation under grant IRI-9310819. Mary Elaine Califf: She is currently pursuing her doctorate in Computer Science at the University of Texas at Austin where she is supported by a fellowship from AT&T. Her research interests include natural language understanding, particularly using machine learning methods to build practical natural language understanding systems such as information extraction systems, and inductive logic programming. Raymond Joseph Mooney: He is an Associate Professor of Computer Sciences at the University of Texas at Austin. He recerived his Ph.D. in Computer Science from the University of Illinois at Urbana-Champaign in 1988. His current research interests include applying machine to natural language understanding, inductive logic programming, knowledge-base and theory refinement, learning for planning, and learning for recommender systems. He serves on the editorial boards of the journalNew Generation Computing, theMachine Learning journal, theJournal of Artificial Intelligence Research, and the journalApplied Intelligence.     

Analogical model formulation for transfer learning in AP Physics

Transfer learning is the ability to apply previously learned knowledge to new problems or domains. In qualitative reasoning, model formulation is the process of moving from the unruly, broad set of concepts used in everyday life to a concise, formal vocabulary of abstractions, assumptions, causal relationships, and models that support problem-solving. Approaching transfer learning from a model formulation perspective, we found that analogy with examples can be used to learn how to solve AP Physics style problems. We call this process analogical model formulation and implement it in the Companion cognitive architecture. A Companion begins with some basic mathematical skills, a broad common sense ontology, and some qualitative mechanics, but no equations. The Companion uses worked solutions, explanations of example problems at the level of detail appearing in textbooks, to learn what equations are relevant, how to use them, and the assumptions necessary to solve physics problems. We present an experiment, conducted by the Educational Testing Service, demonstrating that analogical model formulation enables a Companion to learn to solve AP Physics style problems. Across six different variations of relationships between base and target problems, or transfer levels, a Companion exhibited a 63% improvement in initial performance. While already a significant result, we describe an in-depth analysis of this experiment to pinpoint the causes of failures. Interestingly, the sources of failures were primarily due to errors in the externally generated problem and worked solution representations as well as some domain-specific problem-solving strategies, not analogical model formulation. To verify this, we describe a second experiment which was performed after fixing these problems. In this second experiment, a Companion achieved a 95.8% improvement in initial performance due to transfer, which is nearly perfect. We know of no other problem-solving experiments which demonstrate performance of analogical learning over systematic variations of relationships between problems at this scale.     

并行机器学习算法基础体系前沿进展综述

大数据环境下,机器学习算法受到前所未有的重视。总结和分析了传统机器学习算法在海量数据场景下出现的若干问题,基于当代并行机分类回顾了国内外并行机器学习算法的研究现状,并归纳总结了并行机器学习算法在各种基础体系下存在的问题。针对大数据环境下并行机器学习算法进行了简要的总结,并对其发展趋势作了展望。     

Book Review: Exemplar-Based Knowledge Acquisition,by Ray Bareiss. Academic Press, 1989

Summary Exemplar-Based Knowledge Acquisition is an excellent reference document describing a promising knowledge acquisition tool, the Protos system. Since it is publicly available, Protos provides a testbed for a variety of techniques and issues in machine learning: (1) the integration of similarity-based and explanation-based approaches, (2) the transition from user guidance to autonomy, and (3) the relation between knowledge representation and efficiency. Much work remains to be done to assess Protos' scaleability and to uncover and repair any possible existing complexity problems.     

Visual analogy: Viewing analogical retrieval and mapping as constraint satisfaction problems

The core issue of analogical reasoning is the transfer of relational knowledge from a source case to a target problem. Visual analogical reasoning pertains to problems containing only visual knowledge. Holyoak and Thagard proposed that the retrieval and mapping tasks of analogy in general can be productively viewed as constraint satisfaction problems, and provided connectionist implementations of their proposal. In this paper, we reexamine the retrieval and mapping tasks of analogy in the context of diagrammatic cases, representing the spatial structure of source and target diagrams as semantic networks in which the nodes represent spatial elements and the links represent spatial relations. We use a method of constraint satisfaction with backtracking for the retrieval and mapping tasks, with subgraph isomorphism over a particular domain language as the similarity measure. Results in the domain of 2D line drawings suggest that at least for this domain the above method is quite promising.     

A Deductive Database Approach to A.I. Planning

In this paper, we show that the classical A.I. planning problem can be modelled using simple database constructs with logic-based semantics. The approach is similar to that used to model updates and nondeterminism in active database rules. We begin by showing that planning problems can be automatically converted to Datalog_1S programs with nondeterministic choice constructs, for which we provide a formal semantics using the concept of stable models. The resulting programs are characterized by a syntactic structure (XY-stratification) that makes them amenable to efficient implementation using compilation and fixpoint computation techniques developed for deductive database systems. We first develop the approach for sequential plans, and then we illustrate its flexibility and expressiveness by formalizing a model for parallel plans, where several actions can be executed simultaneously. The characterization of parallel plans as partially ordered plans allows us to develop (parallel) versions of partially ordered plans that can often be executed faster than the original partially ordered plans.     

Analogical Learning and Automated Rule Constructions

This paper describes some experiments of analogical learning and automated rule construction.The present investigation focuses on knowledge acquisition,learning by analyogy,and knowledge retention.The developed system initially learns from scratch,gradually acquires knowledge from its environment through trial-and-error interaction,incrementally augments its knowledge base,and analogically solves new tasks in a more efficient and direct manner.     

Parallel programming inPanda

Distributed systems are an alternative to shared-memory multiprocessors for the execution of parallel applications.Panda is a run-time system that provides architectural support for efficient parallel and distributed programming. It supplies fast user-level threads and a means for transparent and coordinated sharing of objects across a homogeneous network. The paper motivates the major architectural choices that guided our design. The problem of sharing data in a distributed environment is discussed, and the performance of the mechanisms provided by thePanda prototype implementation is assessed.     

Information Filtering: Selection Mechanisms in Learning Systems

Knowledge has traditionally been considered to have a beneficial effect on the performance of problem solvers but recent studies indicate that knowledge acquisition is not necessarily a monotonically beneficial process, because additional knowledge sometimes leads to a deterioration in system performance. This paper is concerned with the problem of harmful knowledge: that is, knowledge whose removal would improve a system's performance. In the first part of the paper a unifying framework, called theinformation filtering model, is developed to define the various alternative methods for eliminating such knowledge from a learning system where selection processes, called filters, may be inserted to remove potentially harmful knowledge. These filters are termed selective experience, selective attention, selective acquisition, selective retention, and selective utilization. The framework can be used by developers of learning systems as a guide for selecting an appropriate filter to reduce or eliminate harmful knowledge.In the second part of the paper, the framework is used to identify a suitable filter for solving a problem caused by the acquisition of harmful knowledge in a learning system calledLassy.Lassy is a system that improves the performance of a PROLOG interpreter by utilizing acquired domain specific knowledge in the form of lemmas stating previously proved results. It is shown that the particular kind of problems that arise with this system are best solved using a novel utilization filter that blocks the use of lemmas in attempts to prove subgoals that have a high probability of failing.     

MACHINE LEARNING IN HYBRID HIERARCHICAL AND PARTIAL-ORDER PLANNERS FOR MANUFACTURING DOMAINS

ABSTRACT

The application of AI planning techniques to manufacturing systems is being widely deployed for all the tasks involved in the process, from product design to production planning and control. One of these problems is the automatic generation of control sequences for the entire manufacturing system in such a way that final plans can be directly used as the sequential control programs which drive the operation of manufacturing systems. HYBIS is a hierarchical and nonlinear planner whose goal is to obtain partially ordered plans at such a level of detail that they can be used as sequential control programs for manufacturing systems. Currently, those sequential control programs are being generated by hand using modeling tools. This document describes a work aimed to improve the efficiency of solving problems with HYBIS by using machine learning techniques. It implements a deductive learning method that is able to automatically acquire control knowledge (heuristics) by generating bounded explanations of the problem-solving episodes. The learning approach builds on HAMLET, a system that learns control knowledge in the form of control rules.     

Student modeling to support multiple instructional approaches

Intelligent computer-assisted instruction (ICAI) systems have continually sought increased flexibility to respond appropriately to the multi-faceted interests of students. Research on theImage student modeler of theGuidon2 ICAI system has developed amultiple-anticipation approach to plan generation and interpretation that directly meets a wide range of communication goals: providing information support, encouraging exploration with interesting elaborations, recognizing strategic mistakes in actions and plans, evaluating success in domain tasks, diagnosing misconceptions, and recommending improvements for mistakes.In order to meet pragmatic system constraints,Image must provide its full range of advice simultaneously, continually, and quickly. It drops many of the simplifying assumptions typically used by plan recognition user modelers, including assumptions of closed-world knowledge and of the user's correctness, cooperation, and unified goal. To maintain efficiency for dynamic plan recognition,Image relies instead on two assumptions of cognitive economy, contextualrelevance and conceptualeasiness, which are operational forms of Grice's maxims of relation and quantity. Its multiple-anticipation approach to plan management provides all of the requisite information together and allows incremental updating and relaxation methods of interpretation, even when students are shifting focus frequently.Robert London's doctoral research was on student modeling and instructional planning in theGuidon2 ICAI system, which developed several ways for students to learn by interactive development of qualitative models. His PhD disseration at Stanford University is entitledStudent Modeling with Multiple Viewpoints by Plan Inference. He has published research papers on student modeling, plan recognition, and automated learning. Recently he has led R&D projects at Cimflex Teknowledge in Palo Alto, California, in knowledge-based tools and training. His current interests include use of simulation systems for cooperative learning and design, especially with object-oriented tools and multi-media presentation systems.     

Combining Proof Plans with Partial Order Planning for Imperative Program Synthesis

The structured programming literature provides methods and a wealth of heuristic knowledge for guiding the construction of provably correct imperative programs. We investigate these methods and heuristics as a basis for mechanizing program synthesis. Our approach combines proof planning with conventional partial order planning. Proof planning is an automated theorem proving technique which uses high-level proof plans to guide the search for proofs. Proof plans are structured in terms of proof methods, which encapsulate heuristics for guiding proof search. We demonstrate that proof planning provides a local perspective on the synthesis task. In particular, we show that proof methods can be extended to represent heuristics for guiding program construction. Partial order planning complements proof planning by providing a global perspective on the synthesis task. This means that it allows us to reason about the order in which program fragments are composed. Our hybrid approach has been implemented in a semi-automatic system called Bertha. Bertha supports partial correctness and has been tested on a wide range of non-trivial programming examples.     

Effects of multimedia and schema induced analogical reasoning on science learning

The present study investigates the effects of multimedia and schema induced analogical reasoning on science learning. It involves 89 fourth grade elementary students in the north‐east of the United States. Participants are randomly assigned into four conditions: (a) multimedia with analogy; (b) multimedia without analogy; (c) analogy without multimedia; and (d) non‐multimedia and non‐analogy. The multivariate analyses of covariance reveal significant main effects for multimedia and analogy learning as well as a significant interaction between multimedia and analogy. The findings show that schema induced analogical reasoning can significantly improve science learning and that multimedia becomes more effective when it is integrated with an instructional method such as analogy and less so when it is used only as a visual tool. The study also shows the field dependence/independence as a significant covariate that influences learners' schema induced analogical reasoning in learning. Discussions pertaining to the significance of the findings and their implications for teaching and learning are made. Suggestions for future research are included with an emphasis on developing multimedia supported analogical reasoning for science learning.     

Support Vector Learning for Semantic Argument Classification

The natural language processing community has recently experienced a growth of interest in domain independent shallow semantic parsing—the process of assigning a Who did What to Whom, When, Where, Why, How etc. structure to plain text. This process entails identifying groups of words in a sentence that represent these semantic arguments and assigning specific labels to them. It could play a key role in NLP tasks like Information Extraction, Question Answering and Summarization. We propose a machine learning algorithm for semantic role parsing, extending the work of Gildea and Jurafsky (2002), Surdeanu et al. (2003) and others. Our algorithm is based on Support Vector Machines which we show give large improvement in performance over earlier classifiers. We show performance improvements through a number of new features designed to improve generalization to unseen data, such as automatic clustering of verbs. We also report on various analytic studies examining which features are most important, comparing our classifier to other machine learning algorithms in the literature, and testing its generalization to new test set from different genre. On the task of assigning semantic labels to the PropBank (Kingsbury, Palmer, & Marcus, 2002) corpus, our final system has a precision of 84% and a recall of 75%, which are the best results currently reported for this task. Finally, we explore a completely different architecture which does not requires a deep syntactic parse. We reformulate the task as a combined chunking and classification problem, thus allowing our algorithm to be applied to new languages or genres of text for which statistical syntactic parsers may not be available.Editors: Dan Roth and Pascale FungThis research was partially supported by the ARDA AQUAINT program via contract OCG4423B and by the NSF via grant IIS-9978025.     

Machine learning for map interpretation: An intelligent tool for environmental planning

The design of a user interface integrating instruments for visual and textual representation and image interpretation is a relevant problem when developing an advisory system for environmental planning. Indeed, the user of the system needs a support to the interpretation of maps, that is, a tool that segments maps and automatically associates geometric regions on a map with those semantic labels useful for applying hints and advices suggested by the environmental planning system. In the article, we present the application of symbolic machine learning techniques to the interpretation of maps. Two inductive learning systems, namely, INDUBI/CSL and ATRE, have been used to complete the knowledge base of an expert system for environmental planning. The application described concerns the recognition of four environmental concepts that are relevant for environmental protection. The positive results obtained in two different experiments prove the strength of the adopted approach for the interpretation task.