3053066
Sensitivity Analysis in Bayesian Networks: From Single to Multiple Parameters
Previous work on sensitivity analysis in Bayesian networks has focused on single parameters, where the goal is to understand the sensitivity of queries to single parameter changes, and to identify single parameter changes that would enforce a certain query constraint. In this paper, we expand the work to multiple parameters which may be in the CPT of a single variable, or the CPTs of multiple variables. Not only do we identify the solution space of multiple parameter changes that would be needed to enforce a query constraint, but we also show how to find the optimal solution, that is, the one which disturbs the current probability distribution the least (with respect to a specific measure of disturbance). We characterize the computational complexity of our new techniques and discuss their applications to developing and debugging Bayesian networks, and to the problem of reasoning about the value (reliability) of new information.
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.
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.
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.
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.
182657
Key infection: smart trust for smart dust
Future distributed systems may include large self-organizing networks of locally communicating sensor nodes, any small number of which may be subvened by an adversary. Providing security for these sensor networks is important, but the problem is complicated by the fact that managing cryptographic key material is hard: low-cost nodes are neither tamper-proof nor capable of performing public key cryptography efficiently. We show how the key distribution problem can be dealt with in environments with a partially present, passive adversary: a node wishing to communicate securely with other nodes simply generates a symmetric key and sends it in the clear to its neighbours. Despite the apparent insecurity of this primitive, we can use mechanisms for key updating, multipath secrecy amplification and multihop key propagation to build up extremely resilient trust networks where at most a fixed proportion of communications links can be eavesdropped. We discuss applications in which this assumption is sensible. Many systems must perforce cope with principals who are authenticated weakly, if at all; the resulting issues have often been left in the 'too hard' tray. One particular interest of sensor networks is that they present a sufficiently compact and tractable version of this problem. We can perform quantitative analyses and simulations of alternative strategies, some of which we present here. We also hope that This work may start to challenge the common belief that authentication is substantially about bootstrapping trust. We argue that, in distributed systems where the opponent can subvert any small proportion of nodes, it is more economic to invest in resilience than in bootstrapping.
4540744
Random key predistribution schemes for sensor networks
Key establishment in sensor networks is a challenging problem because asymmetric key cryptosystems are unsuitable for use in resource constrained sensor nodes, and also because the nodes could be physically compromised by an adversary. We present three new mechanisms for key establishment using the framework of pre-distributing a random set of keys to each node. First, in the q-composite keys scheme, we trade off the unlikeliness of a large-scale network attack in order to significantly strengthen random key predistribution's strength against smaller-scale attacks. Second, in the multipath-reinforcement scheme, we show how to strengthen the security between any two nodes by leveraging the security of other links. Finally, we present the random-pairwise keys scheme, which perfectly preserves the secrecy of the rest of the network when any node is captured, and also enables node-to-node authentication and quorum-based revocation.
5337517
Throughput Optimized SHA-1 Architecture Using Unfolding Transformation
In this paper, the authors analyze the theoretical delay bound of the SHA-1 algorithm and propose architectures to achieve high throughput hardware implementations which approach this bound. According to the results of FPGA implementations, 3,541 Mbps with a pipeline and 893 Mbps without a pipeline were achieved. Moreover, synthesis results using 0.18mum CMOS technology showed that 10.4 Gbps with a pipeline and 3.1 Gbps without a pipeline can be achieved. These results are much faster than previously published results. The high throughputs are due to the unfolding transformation, which reduces the number of required cycles for one block hash. The authors reduced the required number of cycles to 12 cycles for a 512 bit block and showed that 12 cycles is the optimal in our design
18562701
Compressed Index for a Dynamic Collection of Texts
Let T be a string with n characters over an alphabet of bounded size. The recent breakthrough on compressed indexing allows us to build an index for T in optimal space (i.e., O(n) bits), while supporting very efficient pattern matching [2,4]. This paper extends the work on optimal-space indexing to a dynamic collection of texts. Precisely, we give a compressed index using O(n) bits where n is the total length of texts, such that searching for a pattern P takes O(|P|log n + occ log2 n) time where occ is the number of occurrences, and inserting or deleting a text T takes O(|T|log n) time.