40802326
Constructing Efficient Belief Network Structures With Expert Provided Information
Presents a technique to construct efficient belief network structures for application areas where large amounts of data are available and information on the ordering of the variables can be obtained from domain experts. We identify classes of networks that are efficient for propagating beliefs. We formulate the problem as one of determining the belief network representation from a given class that best represents the data. We use the I-Divergence measure which is known to have certain desirable properties for evaluating different approximations. We present some theoretical findings that characterize the nature of solutions that are obtained. These theoretical results lead to an efficient solution procedure for finding the best network representation. We also discuss other information that may be reasonably obtained from experts, and show how such information leads to improving the efficiency of the technique to find the best network structure.
476243
Reconciling Attribute Values from Multiple Data Sources
Because of the heterogeneous nature of multiple data sources, data integration is often one of the most challenging tasks of today’s information systems. While the existing literature has focused on problems such as schema integration and entity identification, our current study attempts to answer a basic question: When an attribute value for a real-world entity is recorded differently in two databases, how should the “best” value be chosen from the set of possible values? We first show how probabilities for attribute values can be derived, and then propose a framework for deciding the cost-minimizing value based on the total cost of type I, type II, and misrepresentation errors.
14335537
A Data Perturbation Approach to Privacy Protection in Data Mining
Advances in data mining techniques have raised growing concerns about privacy of personal information. Organizations that use their customers’ records in data mining activities are forced to take actions to protect the privacy of the individuals involved. A common practice for many organizations today is to remove the identity-reated attributes from customer records before releasing them to data miners or analysts. In this study, we investigate the effect of this practice and demonstrate that a majority of the records in a dataset can be uniquely identified even after identity related attributes are removed. We propose a data perturbation method that can be used by organizations to prevent such unique identification of individual records, while providing the data to analysts for data mining. The proposed method attempts to preserve the statistical properties of the data based on privacy protection parameters specified by the organization. We show that the problem can be solved in two phases, with a linear programming formulation in phase one (to preserve the marginal distribution), followed by a simple Bayes-based swapping procedure in phase two (to preserve the joint distribution). The proposed method is compared with a random perturbation method in classification performance on two real-world datasets. The results of the experiments indicate that it significantly outperforms the random method.
500117
A probabilistic relational model and algebra
Although the relational model for databases provides a great range of advantages over other data models, it lacks a comprehensive way to handle incomplete and uncertain data. Uncertainty in data values, however, is pervasive in all real-world environments and has received much attention in the literature. Several methods have been proposed for incorporating uncertain data into relational databases. However, the current approaches have many shortcomings and have not established an acceptable extension of the relational model. In this paper, we propose a consistent extension of the relational model. We present a revised relational structure and extend the relational algebra. The extended algebra is shown to be closed, a consistent extension of the conventional relational algebra, and reducible to the latter.
29720896
Assessing data quality for information products
Data quality is a critical issue in the design and implementation of databases. Often, the information provided to decision-makers is derived from heterogeneous databases. To determine the quality characteristics of information provided to decision-makers (derived data), it is necessary to determine how quality characteristics associated with diverse data sources affect the quality of the derived data. We discuss a methodology to determine two data quality characteristics, accuracy and incompleteness, that are of critical importance to decision-makers. We examine how the quality metrics of source data affect metrics for data derived using relational algebra operations.
3382815
PSQL: A Query Language for Probabilistic Relational Data
Abstract Database systems based on the relational model have become very popular for the storage of large volumes of business-related data. Although the relational model provides a great range of advantages over other data models, it was designed to support deterministic data and, consequently, it lacks a comprehensive way for handling uncertain data. However, in all real-world environments, uncertainty in data values is a common occurrence. Therefore, there is a need to extend the relational model so that data uncertainty can be captured explicitly. In an earlier work, we have proposed a probabilistic relational algebra that is a consistent extension of the conventional relational algebra and is reducible to the latter. The contribution of this work is the development of a non-procedural probabilistic query language—structured around the popular SQL—that can be built on top of that algebra. We formalize the extended syntax, provide examples to illustrate the syntax, and examine query formulation from a decision-theoretic perspective.
1183276
Effective Use of Memory in Iterative Deepening Search
Abstract The Iterative Deepening A∗ (IDA∗) (R.E. Korf, Artificial Intelligence 27 (1985)) algorithm often reexpands too many nodes while solving certain combinatorial problems. Algorithm IDA∗_CR (U.K. Sarkar, Artificial Intelligence 50 (1991)) attempted to remedy this drawback. These algorithms require very little memory although much more is available in practice. This paper introduces an algorithm IDA∗_CRM which shows how the available memory can be advantageously utilized in IDAast;_CR in order to reduce the number of expanded nodes. IDA∗_CRAM, an approximation scheme derived from IDA∗_CRM, is also presented. Computational results are shown for the Flow-Shop Scheduling Problem.
34366805
An efficient dynamic program slicing technique
Abstract An important application of the dynamic program slicing technique is program debugging. In applications such as interactive debugging, the dynamic slicing algorithm needs to be efficient. In this context, we propose a new dynamic program slicing technique that is more efficient than the related algorithms reported in the literature. We use the program dependence graph as an intermediate program representation, and modify it by introducing the concepts of stable and unstable edges . Our algorithm is based on marking and unmarking the unstable edges as and when the dependences arise and cease during run-time. We call this algorithm edge-marking algorithm . After an execution of a node x , an unstable edge ( x , y ) is marked if the node x uses the value of the variable defined at node y . A marked unstable edge ( x , y ) is unmarked after an execution of a node z if the nodes y and z define the same variable var , and the value of var computed at the node y does not affect the present value of var defined at the node z . We show that our algorithm is more time and space efficient than the existing ones. The worst case space complexity of our algorithm is O ( n 2 ), where n is the number of statements in the program. We also briefly discuss an implementation of our algorithm.
4723885
Learning while solving problems in best first search
We investigate the role of learning in search-based systems for solving optimization problems. We use a learning model, where the values of a set of features can be used to induce a clustering of the problem state space. The feasible set of h* values corresponding to each cluster is called h*set. If we relax the optimality guarantee, and tolerate a risk factor, the distribution of h*set can be used to expedite search and produce results within a given risk of suboptimality. The off-line learning method consists of solving a batch of problems by using A* to learn the distribution of the h*set in the learning phase. This distribution can be used to solve the rest of the problems effectively. We show how the knowledge acquisition phase can be integrated with the problem solving phase. We present a continuous online learning scheme that uses an "anytime" algorithm to learn continuously while solving problems.
5653745
Foundational Certified Code in a Metalogical Framework
Foundational certified code systems seek to prove untrusted programs to be safe relative to safety policies given in terms of actual machine architectures, thereby improving the systems’ flexibility and extensibility. Previous efforts have employed a structure wherein the proofs are expressed in the same logic used to express the safety policy. We propose an alternative structure wherein safety proofs are expressed in the Twelf metalogic, thereby eliminating from those proofs an extra layer of encoding needed in the previous accounts. Using this metalogical approach, we have constructed a complete, foundational account of safety for a fully expressive typed assembly language.
15753347
Basic Theory in Construction of Boolean Functions with Maximum Possible Annihilator Immunity
So far there is no systematic attempt to construct Boolean functions with maximum annihilator immunity. In this paper we present a construction keeping in mind the basic theory of annihilator immunity. This construction provides functions with the maximum possible annihilator immunity and the weight, nonlinearity and algebraic degree of the functions can be properly calculated under certain cases. The basic construction is that of symmetric Boolean functions and applying linear transformation on the input variables of these functions, one can get a large class of non-symmetric functions too. Moreover, we also study several other modifications on the basic symmetric functions to identify interesting non-symmetric functions with maximum annihilator immunity. In the process we also present an algorithm to compute the Walsh spectra of a symmetric Boolean function with O(n2) time and O(n) space complexity.