Discovery and Fusion of Uncertain Knowledge in Data

The following sections are included:

• Dedication
• Preface
• About the Authors
• Acknowledgments
• Contents

The following sections are included:

• Background and Motivation
• Challenges, Research Issues and Basic Ideas
  • Learning and inferring uncertain knowledge in massive and changing data using MapReduce
  • Representing and inferring uncertain knowledge for lineage processing over uncertain data
  • Representing and inferring uncertain knowledge for tracing errors in uncertain data
  • Fusing uncertain knowledge in dynamic data
• Organization

In this chapter, we propose a parallel and incremental approach for data-intensive learning of BN from massive, distributed and dynamically changing data by extending the classic scoring & search algorithm and using MapReduce. First, we adopt the minimum description length (MDL) as the scoring metric and give a two-pass MapReduce-based algorithm for computing required marginal probabilities and scoring candidate graphical models upon sample data. Then, we give the corresponding strategy for extending the classic hill-climbing algorithm to obtain the optimal structure, as well as that for storing a Bayesian Network (BN) by 〈key, value〉 pairs. Further in view of the dynamic characteristics of changing data, we give the concept of influence degree to measure the coincidence of current BN with new data, and then propose a two-pass MapReduce-based algorithm for BN’s incremental learning. Experimental results show the efficiency, scalability and effectiveness of our methods.

In this chapter, we are to develop the method for data-intensive probabilistic inferences of uncertain knowledge represented by large-scale Bayesian Networks (BNs), which could be learned by the method presented in Chapter 2 from massive data or given corresponding to complex applications. Efficiency highlighted in real applications based on BN inferences makes it challenging due to the exponential complexity with respect to the scale of nodes in directed acyclic graph (DAG) and parameters in conditional probability tables (CPTs). Thus, we give a parallel inference method for computing joint probability distributions with large-scale BNs using MapReduce by extending the classic algorithm for BN’s exact inferences. In the method, we adopt the large-scale BN as a massive dataset stored in distributed systems, and consequently transform the concerned steps in BN inferences into data-intensive operations upon the distributed file storage. Then, we give a case study to discover user similarities in social media by the proposed algorithm for data-intensive probabilistic inferences. Experimental results show the efficiency and effectiveness of the proposed method.

In this chapter, we focus on the representation and processing of lineages over uncertain data, where we adopt Bayesian Network (BN) as the framework of uncertainty representation and inferences. Starting from the lineage expressed as Boolean formulae for Selection–Projection–Join (SPJ) queries over uncertain data, we give a method to transform the lineage expression into directed acyclic graphs (DAGs) equivalently. Specifically, we discuss the corresponding probabilistic semantics and properties to guarantee the correctness of probabilistic inferences theoretically. Then, we propose the function-based method to compute the conditional probability table (CPT) for each node in the DAG. The BN for representing lineage expressions over uncertain data, called lineage BN and abbreviated as LBN, is constructed while generally suitable for both safe and unsafe query plans. Therefore, we give the variable-elimination-based algorithm for LBN’s exact inferences to obtain the probabilities of query results, called LBN-based query processing. Then, we focus on obtaining the probabilities of inputs or intermediate tuples conditioned on query results, called LBN-based inference query processing, and give the Gibbs-sampling-based algorithm for LBN’s approximate inferences. Experimental results show the efficiency and effectiveness of our methods.

Data in probabilistic databases may not be absolutely correct, and worse, may be erroneous. Many existing data cleaning methods can be used to detect errors in traditional databases, but they fall short of guiding us to find errors in probabilistic databases, especially for databases with complex correlations among data. In this chapter, we give a method for tracing errors in probabilistic databases by adopting Bayesian Network (BN) as the framework of representing the correlations among data. We first develop the techniques to construct an augmented Bayesian Network (ABN) for an anomalous query to represent correlations among input data, intermediate data and output data in the query execution. Inspired by the notion of blame in causal models, we then define a notion of blame for ranking candidate errors. Next, we provide an efficient method for computing the degree of blame for each candidate error based on the probabilistic inference upon the ABN. Experimental results show the effectiveness and efficiency of our method.

In this chapter, we are to achieve the global uncertain knowledge during a period of time for decision making or action selection by fussing or combining the participating uncertain knowledge (represented as Bayesian Networks (BNs)) of multiple time slices consistently while satisfying the demands of high efficiency and instantaneousness. We adopt qualitative probabilistic network (QPN), the qualitative abstraction of BN, as the underlying framework of modeling and fusing time-series uncertain knowledge. BNs in continuous time slices constitute time-series BNs, from which we derive time-series QPNs. Taking as input time-series BNs, we give a QPN-based approach to fuse time-series uncertain knowledge in terms of time-series specialties. First, for each time slice, we enhance the implied QPN by augmenting interval-valued weights derived from the corresponding BN, and then obtain the QPN with weighted influences, denoted enhanced qualitative probabilistic network (EQPN), which provides a quantitative and conflict-free basis for fusing uncertain knowledge. Then, we give the method for fusing the graphical structures of time-series EQPNs based on the concept of Markov equivalence. Following, we give a superposition method for fusing qualitative influences of time-series EQPNs. Experimental results show that our method is not only efficient but also effective. Meanwhile, the simulation results when applying time-series EQPNs and the fusion algorithm to a robotic system show that our method is applicable in realistic intelligent situations.

Knowledge discovery and knowledge fusion are everlasting and challenging subjects with great interest in several paradigms including data science, artificial intelligence, machine learning, information retrieval, etc. In the background of big data, it is desirable to discover knowledge from massive, distributed, heterogeneous, uncertain and dynamically changing data, such that data understanding, data utilization and information services could be fulfilled pertinently. Meanwhile, it is more and more important to fuse fragmented, heterogeneous, multi-source knowledge from the perspective of big data intelligence and knowledge engineering, such that analysis prediction and decision could be performed appropriately…

The following sections are included:

• References
• Index