Case-base maintenance with multi-objective evolutionary algorithms

Case-Base Reasoning is a problem-solving methodology that uses old solved problems, called cases, to solve new problems. The case-base is the knowledge source where the cases are stored, and the amount of stored cases is critical to the problem-solving ability of the Case-Base Reasoning system. However, when the case-base has many cases, then performance problems arise due to the time needed to find those similar cases to the input problem. At this point, Case-Base Maintenance algorithms can be used to reduce the number of cases and maintain the accuracy of the Case-Base Reasoning system at the same time. Whereas Case-Base Maintenance algorithms typically use a particular heuristic to remove (or select) cases from the case-base, the resulting maintained case-base relies on the proportion of redundant and noisy cases that are present in the case-base, among other factors. That is, a particular Case-Base Maintenance algorithm is suitable for certain types of case-bases that share some indicators, such as redundancy and noise levels. In the present work, we consider Case-Base Maintenance as a multi-objective optimization problem, which is solved with a Multi-Objective Evolutionary Algorithm. To this end, a fitness function is introduced to measure three different objectives based on the Complexity Profile model. Our hypothesis is that the Multi-Objective Evolutionary Algorithm performing Case-Base Maintenance may be used in a wider set of case-bases, achieving a good balance between the reduction of cases and the problem-solving ability of the Case-Based Reasoning system. Finally, from a set of the experiments, our proposed Multi-Objective Evolutionary Algorithm performing Case-Base Maintenance shows regularly good results with different sets of case-bases with different proportion of redundant and noisy cases.     

Modeling user interests by conceptual clustering

As more information becomes available on the Web, there has been a crescent interest in effective personalization techniques. Personal agents providing assistance based on the content of Web documents and the user interests emerged as a viable alternative to this problem. Provided that these agents rely on having knowledge about users contained into user profiles, i.e., models of user preferences and interests gathered by observation of user behavior, the capacity of acquiring and modeling user interest categories has become a critical component in personal agent design. User profiles have to summarize categories corresponding to diverse user information interests at different levels of abstraction in order to allow agents to decide on the relevance of new pieces of information. In accomplishing this goal, document clustering offers the advantage that an a priori knowledge of categories is not needed, therefore the categorization is completely unsupervised. In this paper we present a document clustering algorithm, named WebDCC (Web Document Conceptual Clustering), that carries out incremental, unsupervised concept learning over Web documents in order to acquire user profiles. Unlike most user profiling approaches, this algorithm offers comprehensible clustering solutions that can be easily interpreted and explored by both users and other agents. By extracting semantics from Web pages, this algorithm also produces intermediate results that can be finally integrated in a machine-understandable format such as an ontology. Empirical results of using this algorithm in the context of an intelligent Web search agent proved it can reach high levels of accuracy in suggesting Web pages.     

Compiling conceptual graphs

The paper addresses problems in conceptual graph implementation: subsumption and classification in a taxonomy. Conceptual graphs are typically stored using a directed acyclic graph data structure based on the partial order over conceptual graphs. We give an improved algorithm for classifying conceptual graphs into this hierarchy. It prunes the search space in the database using the information gathered while searching. We show how conceptual graphs in this hierarchy can be compiled into instructions which represent specialized cases of the canonical formation rules. This compiles subsumption of conceptual graphs and compresses knowledge in a knowledge base. Conceptual graphs are compiled as differences between adjacent graphs in the hierarchy. The differences represent the rules used in deriving the graph from the adjacent graphs. We illustrate how the method compresses knowledge bases in some experiments. Compilation is effected in three ways: removal of redundant data, use of simple instructions which ignore redundant checks when performing matching, and by sharing common processing between graphs     

Automatic structuring of knowledge bases by conceptual clustering

An important structuring mechanism for knowledge bases is building an inheritance hierarchy of classes based on the content of their knowledge objects. This hierarchy facilitates group-related processing tasks such as answering set queries, discriminating between objects, finding similarities among objects, etc. Building this hierarchy is a difficult task for the knowledge engineer. Conceptual clustering may be used to automate or assist the engineer in the creation of such a classification structure. This article introduces a new conceptual clustering method which addresses the problem of clustering large amounts of structured objects. The conditions under which the method is applicable are discussed     

Incremental planning using conceptual graphs

Abstract

When performing a planning or design task in many domains it is often difficult to specify in advance what the precise goals are. It is therefore useful to have a system in which the planning process is performed interactively, with the solution approaching the users' intent incrementally through iterations of the planning process. A planning system intended to function in this way must be able to take goal specifications interactively rather than all at once at the beginning of the planning process. The planning process then becomes one of satisfying new goals as they are given by the user, modifying as little as possible the results of previous planning work. Incremental planning is an approach to interactive planning problems that allows a system to create a plan incrementally, modifying a previous plan to satisfy new or more precise goal specifications. In this paper we present an incremental planning system called the general constraint system (GCS) that is based on the conceptual programming environment (CP) developed at New Mexico State University and we show an example of the use of the system for a simple civil engineering design problem     

Protein classification by matching and clustering surface graphs

In this paper, we address the problem of comparing and classifying protein surfaces with graph-based methods. Comparison relies on matching surface graphs, extracted from the surfaces by considering concave and convex patches, through a kernelized version of the Softassign graph-matching algorithm. On the other hand, classification is performed by clustering the surface graphs with an EM-like algorithm, also relying on kernelized Softassign, and then calculating the distance of an input surface graph to the closest prototype. We present experiments showing the suitability of kernelized Softassign for both comparing and classifying surface graphs.     

Verifying task-based specifications in conceptual graphs

A conceptual model is a model of real world concepts and application domains as perceived by users and developers. It helps developers investigate and represent the semantics of the problem domain, as well as communicate among themselves and with users. In this paper, we propose the use of task-based specifications in conceptual graphs (TBCG) to construct and verify a conceptual model. Task-based specification methodology is used to serve as the mechanism to structure the knowledge captured in the conceptual model; whereas conceptual graphs are adopted as the formalism to express task-based specifications and to provide a reasoning capability for the purpose of verification. Verifying a conceptual model is performed on model specifications of a task through constraints satisfaction and relaxation techniques, and on process specifications of the task based on operators and rules of inference inherited in conceptual graphs.     

Representing temporal knowledge in conceptual graphs

This study was motivated by some difficulties encountered by the authors when trying to express temporal knowledge using Sowa's conceptual graph (CG) approach. An overview of Sowa's approach is given and the difficulties encountered when trying to model temporal knowledge are outlined: the disparity of notations allowed by CG theory for expressing temporal information; the ambiguity and incompleteness of tense sspecification; the difficulty of harmonizing tenses and intergraph temporal relations. Various approaches suggested for representing time both in artificial intelligence and linguistics are presented, and an extension to Sowa's approach is proposed in which temporal and nontemporal knowledge are differentiated. In this model points in time are represented as well as time intervals. A semantic interpretation of verbs is provided based on an extension of Reichenbach's model of temporal markers. The authors show how their approach enables the representation of tenses as well as the aspectual properties of natural language sentences.     

面向属性的归纳与概念聚类

面向属性的归纳是新近提出的一种广泛用于数据库中的知识发现的方法，提出这种方法与一种机器学习方法－－概念聚类之间的紧密联系，并描述如何使用一个概念聚类算法进行面向属性的归纳。     

Generality-based conceptual clustering with probabilistic concepts

Statistical research in clustering has almost universally focused on data sets described by continuous features and its methods are difficult to apply to tasks involving symbolic features. In addition, these methods are seldom concerned with helping the user in interpreting the results obtained. Machine learning researchers have developed conceptual clustering methods aimed at solving these problems. Following a long term tradition in AI, early conceptual clustering implementations employed logic as the mechanism of concept representation. However, logical representations have been criticized for constraining the resulting cluster structures to be described by necessary and sufficient conditions. An alternative are probabilistic concepts which associate a probability or weight with each property of the concept definition. In this paper, we propose a symbolic hierarchical clustering model that makes use of probabilistic representations and extends the traditional ideas of specificity-generality typically found in machine learning. We propose a parameterized measure that allows users to specify both the number of levels and the degree of generality of each level. By providing some feedback to the user about the balance of the generality of the concepts created at each level and given the intuitive behavior of the user parameter, the system improves user interaction in the clustering process     

An extended system for conceptual clustering

CLUSTER/2 (Michalski, 1980a, Stepp&Michalski, 1986) in a conceptual clustering system, having the great advantage that obtained clusters are represented in the formof symbolic expressions. However, it has some disadvantages. In this article, a modified version of CLUSTER/2 is proposed. Background knowledge can be conveyed to the system through semantic networks; differentiation among objects is calculating using semantic distance. A different quality evaluation is used to measure the quality of clustering in a more sensible way. The order dependence problem of overlap resolution is eliminated with a fuzzy k-nearest neighborhood technique. Finally, a hill-climbing algorithm is applied to determine the number of clusters automatically. These improvements provide a more stable and user-friendly clustering environment for the user, without changing the system architecture of CLUSTER/2.     

On generalization/specialization for conceptual graphs

Abstract

This paper centres on the generalization/specialization relation in the framework of conceptual graphs (this relation corresponds to logical subsumption when considering logical formulas associated with conceptual graphs). Results given here apply more generally to any model where knowledge is described by labelled graphs and reasoning is based on graph subsumption, as in semantic networks or in structural machine learning. The generalization/specialization relation, as defined by Sowa, is first precisely analysed, in particular its links with a graph morphism, called projection. Besides Sowa's specialization relation (which is a preorder), another one is actually used in some practical applications (which is an order). These are comparatively studied. The second topic of this paper is the design of efficient algorithms for computing these specialization relations. Since the associated problems are NP-hard, the form of the graphs is restricted in order to arrive at polynomial algorithms. In particular, polynomial algorithms are presented for computing a projection from a conceptual ‘tree’ to any conceptual graph, and for counting the number of such projections. The algorithms are also described in a generic way, replacing the projection by a parametrized graph morphism, and conceptual graphs by directed labelled graphs.     

A basic mathematical framework for conceptual graphs

Based on the original idea of Sowa on conceptual graph and a recent formalism by Corbett on ontology, this paper presents a rigorous mathematization of basic concepts encountered in the conceptual structure theory, including canon, ontology, conceptual graph, projection, and canonical formation operations, with the aim of deriving their mathematical properties and applying them to future research and development on knowledge representation. Our proposed formalism enhances the conceptual structure theory and enables it to compare favorably with other alternative methods such as the formal concept analysis theory.     

Implicit consensus clustering from multiple graphs

Data Mining and Knowledge Discovery - Dealing with relational learning generally relies on tools modeling relational data. An undirected graph can represent these data with vertices depicting...     

On querying simple conceptual graphs with negation

We consider basic conceptual graphs, namely simple conceptual graphs (SGs), which are equivalent to the existential conjunctive positive fragment of first-order logic. The fundamental problem, deduction, is performed by a graph homomorphism called projection. The existence of a projection from a SG Q to a SG G means that the knowledge represented by Q is deducible from the knowledge represented by G. In this framework, a knowledge base is composed of SGs representing facts and a query is itself a SG. We focus on the issue of querying SGs, which highlights another fundamental problem, namely query answering. Each projection from a query to a fact defines an answer to the query, with an answer being itself a SG. The query answering problem asks for all answers to a query.

This paper introduces atomic negation into this framework. Several understandings of negation are explored, which are all of interest in real world applications. In particular, we focus on situations where, in the context of incomplete knowledge, classical negation is not satisfactory because deduction can be proven but there is no answer to the query. We show that intuitionistic deduction captures the notion of an answer and can be solved by projection checking. Algorithms are provided for all studied problems. They are all based on projection. They can thus be combined to deal with several kinds of negation simultaneously. Relationships with problems on conjunctive queries in databases are recalled and extended. Finally, we point out that this discussion can be put in the context of semantic web databases.     

Cognitive agents and machine learning by example: Representation with conceptual graphs

As machine learning (ML) and artificial intelligence progress, more complex tasks can be addressed, quite often by cascading or combining existing models and technologies, known as the bottom‐up design. Some of those tasks are addressed by agents, which attempt to simulate or emulate higher cognitive abilities that cover a broad range of functions; hence, those agents are named cognitive agents. We formulate, implement, and evaluate such a cognitive agent, which combines learning by example with ML. The mechanisms, algorithms, and theories to be merged when training a cognitive agent to read and learn how to represent knowledge have not, to the best of our knowledge, been defined by the current state‐of‐the‐art research. The task of learning to represent knowledge is known as semantic parsing, and we demonstrate that it is an ability that may be attained by cognitive agents using ML, and the knowledge acquired can be represented by using conceptual graphs. By doing so, we create a cognitive agent that simulates properties of “learning by example,” while performing semantic parsing with good accuracy. Due to the unique and unconventional design of this agent, we first present the model and then gauge its performance, showcasing its strengths and weaknesses.