Research On Knowledge Representation And Reasoning Based On Decision Implication

Broadly speaking,knowledge representation refers to the associations between knowledge factors and knowledge in objects,so as to facilitate people to identify and understand knowledge,and knowledge reasoning is the process of reasoning from the initial knowledge state to the predefined target state.Knowledge representation and reasoning is one of the important research topics in Artificial Intelligence.Formal Concept Analysis(FCA)is a partially ordered set theory for concept analysis and visualization in formal contexts.This theory has a solid mathematical foundation,an algebraic structure(called concept lattice)that intuitively and formally reflects the information in data,and a high interpret ability.Decision implication is one of the basic knowledge representations for decision-making in FCA,with expressing the dependency and decision knowledge between conditions and consequences(causes and effects).Knowledge representation and reasoning based on decision implica-tion is to perform an extremely compact representation of the decision information implied in data,and obtain all decision information in data by means of reasoning,based on the current representation.The existing research in logic and data aspects of decision implication proposes a set of decision implications with information integrity and extreme simplicity(non-redundancy and optimality)-Decision Implication Canonical Basis(DICB),which lays a solid foundation for constructing a knowledge representation and reasoning framework in formal contexts.This paper conducts a systematic and in-depth study on the important issues of knowledge representation capability,basic algorithms,data adaptability and reasoning based on decision implications,etc.The main results and originalities are summarized as follows:(1)Knowledge representation capability of decision implicationThe knowledge representation capability of decision implication refers to the ability to maintain the completeness of decision information.Concept rule and granular rule are two common forms of decision implication in FCA.Clarifying the relationships between granular rule,concept rule and decision implication,and revealing the strength of their knowledge representation capability are fundamental issues of knowledge representation and reasoning in formal contexts.The research in this paper shows that,in terms of knowledge representation capability,granular rule is weaker than concept rule,and concept rule is weaker than decision implication.In other words,decision implication has the strongest knowledge representation capability,and when using granular rule or concept rule to conduct knowledge representation,there will exist various degrees of decision information loss.(2)Algorithms for generating decision implication canonical basisDecision implication canonical basis is a complete and extremely compact representation of decision information in data.The existing algorithm for generating DICB is based on minimal generators,and has an exponential time complexity.Efficient algorithms for DICB generation are essential for the DICB-based knowledge representation and reasoning.This paper studies the properties of decision premise and true premise,and the relationship between them,and then proposes a true premise-based algorithm for DICB generation(called MBTP).Experimental results show that,MBTP is significantly superior to the minimal generator-based algorithm in time efficiency.Furthermore,considering data is always changing dynamically in applications,this paper reveals the renewal mechanism of DICB,and puts forward an incremental algorithm.Experiment shows that,when the sample size is much larger than then condition attribute size,the incremental algorithm is more effective than MBTP.(3)Knowledge representation and reasoning in incomplete formal contextsCompared with formal context,incomplete formal context is more suitable for characterizing the data in realistic scenarios,and its knowledge representation and reasoning is one of the research topics in FCA.Necessary implications and possible implications are two implication-types of knowledge representations in incomplete formal contexts,and seeking their bases is a fundamental issue of knowledge representation and reasoning in incomplete formal contexts.The research in this paper shows that necessary implication and possible implication can be equivalently recharacterized by decision implication,and the inference rules of decision implication also apply to necessary implication and possible implication.Furthermore,based on the inference rules of decision implication and Reflexivity(another inference rule),this paper defines the completeness and non-redundancy of necessary implication sets and possible implication sets,and presents the most compact representations of necessary implications and possible implications-necessary implication basis and possible implication basis,which indirectly proves that the existing reasoning strategies of decision implication also apply to necessary implications and possible implications.(4)Knowledge representation and reasoning in correlative formal contextsCorrelative formal context formally characterizes the correlative data that exists widely in practical applications,in which the "correlation"refers to the interactions or connections between individuals in different domains.For correlative formal contexts,the study of knowledge representation and reasoning from a correlation perspective expands the application scenarios of FCA.From the perspectives of correlation,cross-domain and multi-granularity,this paper introduces the notion of multi-granularity decision implication in correlative formal contexts,and studies its logical representation and reasoning mechanism.Specifically,the semantic aspect describes the completeness and non-redundancy of multi-granularity decision implication sets,and the syntactical aspect provides a set of inference rule with completeness and non-redundancy,which are of semantical consistency.Finally,this paper presents the most compact representation of knowledge in correlative formal contexts-multi-granularity decision implication basis.This paper clarifies the value of decision implication being a form of knowledge representation in formal contexts,and provides effective fundamental algorithms for DICB-based knowledge representation and reasoning.Furthermore,the conclusions of knowledge representation and reasoning in incomplete formal contexts and correlative formal contexts expand the application data range of decision implication.In conclusion,the results in this paper enrich and develop the theories and methodologies of FCA,and hence have an theoretical significance and potential values for applications.