5935513
On Bayesian Network Approximation by Edge Deletion
We consider the problem of deleting edges from a Bayesian network for the purpose of simplifying models in probabilistic inference. In particular, we propose a new method for deleting network edges, which is based on the evidence at hand. We provide some interesting bounds on the KL-divergence between original and approximate networks, which highlight the impact of given evidence on the quality of approximation and shed some light on good and bad candidates for edge deletion. We finally demonstrate empirically the promise of the proposed edge deletion technique as a basis for approximate inference.
10310314
Sensitivity Analysis in Markov Networks
This paper explores the topic of sensitivity analysis in Markov networks, by tackling questions similar to those arising in the context of Bayesian networks: the tuning of parameters to satisfy query constraints, and the bounding of query changes when perturbing network parameters. Even though the distribution induced by a Markov network corresponds to ratios of multi-linear functions, whereas the distribution induced by a Bayesian network corresponds to multi-linear functions, the results we obtain for Markov networks are as effective computationally as those obtained for Bayesian networks. This similarity is due to the fact that conditional probabilities have the same functional form in both Bayesian and Markov networks, which turns out to be the more influential factor. The major difference we found, however, is in how changes in parameter values should be quantified, as such parameters are interpreted differently in Bayesian networks and Markov networks.
17538498
Reasoning about Bayesian Network Classifiers
Bayesian network classifiers are used in many fields, and one common class of classifiers are naive Bayes classifiers. In this paper, we introduce an approach for reasoning about Bayesian network classifiers in which we explicitly convert them into Ordered Decision Diagrams (ODDS), which are then used to reason about the properties of these classifiers. Specifically, we present an algorithm for converting any naive Bayes classifier into an ODD, and we show theoretically and experimentally that this algorithm can give us an ODD that is tractable in size cvcn given an intractable number of instances. Since ODDS are tractable representations of classifiers, our algorithm allows us to efficiently test the equivalence of two naive Bayes classifiers and characterize discrepancies between them. We also show a number of additional results including a count of distinct classifiers that can be induced by changing some CPT in a naive Bayes classifier, and the range of allowable changes to a CPT which keeps the current classifier unchanged.
5672538
When do Numbers Really Matter?
Common wisdom has it that small distinctions in the probabilities quantifying a belief network do not matter much for the results of probabilistic queries. Yet, one can develop realistic scenarios under which small variations in network probabilities can lead to significant changes in computed queries. A pending theoretical question is then to analytically characterize parameter changes that do or do not matter. In this paper, we study the sensitivity of probabilistic queries to changes in network parameters and prove some tight bounds on the impact that such parameters can have on queries. Our analytical results pinpoint some interesting situations under which parameter changes do or do not matter. These results are important for knowledge engineers as they help them identify influential network parameters. They also help explain some of the previous experimental results and observations with regards to network robustness against parameter changes.
1880699
A distance measure for bounding probabilistic belief change
We propose a distance measure between two probability distributions, which allows one to bound the amount of belief change that occurs when moving from one distribution to another. We contrast the proposed measure with some well known measures, including KL-divergence, showing how they fail to be the basis for bounding belief change as is done using the proposed measure. We then present two practical applications of the proposed distance measure: sensitivity analysis in belief networks and probabilistic belief revision. We show how the distance measure can be easily computed in these applications, and then use it to bound global belief changes that result from either the perturbation of local conditional beliefs or the accommodation of soft evidence. Finally, we show that two well known techniques in sensitivity analysis and belief revision correspond to the minimization of our proposed distance measure and, hence, can be shown to be optimal from that viewpoint.
987821
Using Clustering Information for Sensor Network Localization
Sensor network localization continues to be an important research challenge. The goal of localization is to assign geographic coordinates to each node in the sensor network. Localization schemes for sensor network systems should work with inexpensive off-the-shelf hardware, scale to large networks, and also achieve good accuracy in the presence of irregularities and obstacles in the deployment area. 
 
We present a novel approach for localization that can satisfy all of these desired properties. Recent developments in sensor network clustering algorithms have resulted in distributed algorithms that produce highly regular clusters. We propose to make use of this regularity to inform our localization algorithm. The main advantages of our approach are that our protocol requires only three randomly-placed nodes that know their geographic coordinates, and does not require any ranging or positioning equipment (i.e., no signal strength measurement, ultrasound ranging, or directional antennas are needed). So far, only the DV-Hop localization mechanism worked with the same assumptions [1]. We show that our proposed approach may outperform DV-Hop in certain scenarios, in particular when there exist large obstacles in the deployment field, or when the deployment area is free of obstacles but the number of anchors is limited.
19601656
A mutation-sensitive approach for locating conserved gene pairs between related species
This paper proposes a new approach for solving the whole genome alignment problem. Our approach is based on a new structural optimization problem (called the MUM selection problem) related to mutations via reversals and transpositions. We have devised a practical algorithm for this optimization problem and have evaluated the algorithm using 15 pairs of human and mouse chromosomes. The results show that our algorithm is both effective and efficient. More specifically, our algorithm can reveal 91% of the conserved gene pairs that have been reported in the literature. When compared to existing software MUMmer and MaxMinCluster , our algorithm uncovers 15% and 7% more genes on average, respectively. The sensitivity of our algorithm is also slightly higher. The paper concludes with a remark on the computational hardness of the MUM selection problem.
8638055
Function-Based Analysis of an Electronic Commerce Website
Traditionally, studies with the technology acceptance model (TAM) have treated software systems as holistic units. A survey is conducted to understand the model better by dropping from system-wide measurement to function-based measurement. The first part of the survey replicates Gefen and Straub’s (2000) study where only intention is measured at the function level, with consistent results. System-wide perceived ease of use (PEOU) has more effect on an intrinsic task (intention to search for books) than on an extrinsic task (intention to purchase books). In the second part of the survey, all factors are measured at the function level. The result shows that the function-level models are more predictive than the system-wide model. Specifically, each PEOU is a significant predictor for each intention in both models. This study shows the value of using function-based analysis and suggests that function-based analysis is particularly useful and timely for the study of integrated products offering relatively distinct functions.
15971365
Efficiency of Data Distribution in BitTorrent-Like Systems
BitTorrent (BT) in practice is a very efficient method to share data over a network of clients. In this paper we extend the recent work of Arthur and Panigrahy [1] on modelling the distribution of individual data blocks in BT systems, aiming at a better understanding of why BT can achieve a high degree of parallelism. In particular, we include in our study several new network features that BT systems are using, as well as different local heuristics for routing data blocks in each client. We conduct simulations to figure out to what extent the new network features and routing heuristics would affect the distribution efficiency. Our findings confirm that for the primitive network setting studied in [1], it does require i¾?(blogn) phases for nclients to download bdata blocks. More interestingly, our work suggests that for the more realistic network setting, the heuristics Random and Rarest Block First both allow nclients to download bblocks in b+ O(logn) phases. We believe that the latter bound better reflects the high degree of parallelism of BT observed in reality. It is also worth-mentioning that b+ lognis the smallest possible number of phases needed; it is interesting to see that some simple local routing heuristics have a performance so close to the optimal.
2565301
Visualizing input and output analysis for simulation (VINOAS)
Abstract Input analysis which involves a large amount of statistical analysis is one of the major steps in simulation. A software package with a well-designed user-friendly graphical window interface has been developed to assist modelers in identifying the underlying statistical distribution of the input data. It integrates techniques for assessing sample independence, hypothesizing families of distributions, estimation of parameters, and performing goodness-of-fit tests in a graphical environment. This allows the modelers to use the package in an interactive way and efforts can be saved in specifying the input probability distribution.