Numerical methods for interval and fuzzy number comparison based on the probabilistic approach and Dempster-Shafer theory

There are many different methods for interval and fuzzy number comparison proposed in the literature which provide the results of comparison in the form of a real or Boolean value. In this paper, we use the Dempster-Shafer theory of evidence with its probabilistic interpretation to justify and construct the method which provides the result of comparison in the form of an interval or fuzzy number. The complete and consistent set of expressions for inequality and equality relations between intervals and fuzzy numbers has been obtained in the framework of the probabilistic approach. These relations make it possible to compare intervals and fuzzy numbers with real values and may be considered as an asymptotic limit of the results we obtain using the Dempster-Shafer theory. A natural fuzzy extension of the proposed approach is considered and discussed using some illustrative examples.     

Anytime measures for top-k algorithms on exact and fuzzy data sets

Top-k queries on large multi-attribute data sets are fundamental operations in information retrieval and ranking applications. In this article, we initiate research on the anytime behavior of top-k algorithms on exact and fuzzy data. In particular, given specific top-k algorithms (TA and TA-Sorted) we are interested in studying their progress toward identification of the correct result at any point during the algorithms’ execution. We adopt a probabilistic approach where we seek to report at any point of operation of the algorithm the confidence that the top-k result has been identified. Such a functionality can be a valuable asset when one is interested in reducing the runtime cost of top-k computations. We present a thorough experimental evaluation to validate our techniques using both synthetic and real data sets.     

Guaranteed characterization of exact non-asymptotic confidence regions as defined by LSCR and SPS

In parameter estimation, it is often desirable to supplement the estimates with an assessment of their quality. A new family of methods proposed by Campi et al. for this purpose is particularly attractive, as it makes it possible to obtain exact, non-asymptotic confidence regions under mild assumptions on the noise distribution. A bottleneck of this approach, however, is the numerical characterization of these confidence regions. So far, it has been carried out by gridding, which provides no guarantee as to its results and is only applicable to low dimensional spaces. This paper shows how interval analysis can contribute to removing this bottleneck.     

Probabilistic may/must testing: retaining probabilities by restricted schedulers

This paper considers the probabilistic may/must testing theory for processes having external, internal, and probabilistic choices. We observe that the underlying testing equivalence is too strong and distinguishes between processes that are observationally equivalent. The problem arises from the observation that the classical compose-and-schedule approach yields unrealistic overestimation of the probabilities, a phenomenon that has been recently well studied from the point of view of compositionality, in the context of randomized protocols and in probabilistic model checking. To that end, we propose a new testing theory, aiming at preserving the probability information in a parallel context. The resulting testing equivalence is insensitive to the exact moment the internal and the probabilistic choices occur. We also give an alternative characterization of the testing preorder as a probabilistic ready-trace preorder.     

Assessing the performance of normal-based and REML-based confidence intervals for the intraclass correlation coefficient

Using normal distribution assumptions, one can obtain confidence intervals for variance components in a variety of applications. A normal-based interval, which has exact coverage probability under normality, is usually constructed from a pivot so that the endpoints of the interval depend on the data as well as the distribution of the pivotal quantity. Alternatively, one can employ a point estimation technique to form a large-sample (or approximate) confidence interval. A commonly used approach to estimate variance components is the restricted maximum likelihood (REML) method. The endpoints of a REML-based confidence interval depend on the data and the asymptotic distribution of the REML estimator. In this paper, simulation studies are conducted to evaluate the performance of the normal-based and the REML-based intervals for the intraclass correlation coefficient under non-normal distribution assumptions. Simulated coverage probabilities and expected lengths provide guidance as to which interval procedure is favored for a particular scenario. Estimating the kurtosis of the underlying distribution plays a central role in implementing the REML-based procedure. An empirical example is given to illustrate the usefulness of the REML-based confidence intervals under non-normality.     

Dynamic probabilistic broadcasting in MANETs

In mobile ad hoc networks (MANETs), the efficiency of broadcasting protocol can dramatically affect the performance of the entire network. Appropriate use of a probabilistic method can reduce the number of rebroadcasting, therefore reduce the chance of contention and collision among neighboring nodes. A good probabilistic broadcast protocol can achieve higher throughput and lower energy consumption, without sacrificing the reachability or having any significant degradation. In this paper, we propose a probabilistic approach that dynamically adjusts the rebroadcasting probability as per the node distribution and node movement. This is done based on locally available information and without requiring any assistance of distance measurements or exact location determination devices. We evaluate the performance of our approach by comparing it with the AODV protocol (which is based on simple flooding) as well as a fixed probabilistic approach. Simulation results show our approach performs better than both simple flooding and fixed probabilistic schemes.     

Uncertain Distance-Based Range Queries over Uncertain Moving Objects

Distance-based range search is crucial in many real applications. In particular, given a database and a query issuer, a distance-based range search retrieves all the objects in the database whose distances from the query issuer are less than or equal to a given threshold. Often, due to the accuracy of positioning devices, updating protocols or characteristics of applications (for example, location privacy protection), data obtained from real world are imprecise or uncertain. Therefore, existing approaches over exact databases cannot be directly applied to the uncertain scenario. In this paper, we redefine the distance-based range query in the context of uncertain databases, namely the probabilistic uncertain distance-based range (PUDR) queries, which obtain objects with confidence guarantees. We categorize the topological relationships between uncertain objects and uncertain search ranges into six cases and present the probability evaluation in each case. It is verified by experiments that our approach outperform Monte-Carlo method utilized in most existing work in precision and time cost for uniform uncertainty distribution. This approach approximates the probabilities of objects following other practical uncertainty distribution, such as Gaussian distribution with acceptable errors. Since the retrieval of a PUDR query requires accessing all the objects in the databases, which is quite costly, we propose spatial pruning and probabilistic pruning techniques to reduce the search space. Two metrics, false positive rate and false negative rate are introduced to measure the qualities of query results. An extensive empirical study has been conducted to demonstrate the efficiency and effectiveness of our proposed algorithms under various experimental settings.     

基于混合概率模型的无监督离散化算法

现实应用中常常涉及许多连续的数值属性，而且前许多机器学习算法则要求所处理的属性取离散值，根据在对数值属性的离散化过程中，是否考虑相关类别属性的值，离散化算法可分为有监督算法和无监督算法两类。基于混合概率模型，该文提出了一种理论严格的无监督离散化算法，它能够在无先验知识，无类别是属性的前提下，将数值属性的值域划分为若干子区间，再通过贝叶斯信息准则自动地寻求最佳的子区间数目和区间划分方法。     

Imprecise probabilistic query answering using measures of ignorance and degree of satisfaction

In conditional probabilistic logic programming, given a query, the two most common forms for answering the query are either a probability interval or a precise probability obtained by using the maximum entropy principle. The former can be noninformative (e.g., interval [0, 1]) and the reliability of the latter is questionable when the priori knowledge is imprecise. To address this problem, in this paper, we propose some methods to quantitatively measure if a probability interval or a single probability is sufficient for answering a query. We first propose an approach to measuring the ignorance of a probabilistic logic program with respect to a query. The measure of ignorance (w.r.t. a query) reflects how reliable a precise probability?for the query can be and a high value of ignorance suggests that a single probability is not suitable for the query. We then propose a method to measure the probability that the exact probability of a query falls in a given interval, e.g., a second order probability. We call it the degree of satisfaction. If the degree of satisfaction is high enough w.r.t. the query, then the given interval can be accepted as the answer to the query. We also prove our measures satisfy many properties and we use a case study to demonstrate the significance of the measures.     

Worst Case and a Distribution-Based Case Analyses of Sampling for Rule Discovery Based on Generality and Accuracy

In this paper, we propose two sampling theories of rule discovery based on generality and accuracy. The first theory concerns the worst case: it extends a preliminary version of PAC learning, which represents a worst-case analysis for classification. In our analysis, a rule is defined as a probabilistic constraint of true assignment to the class attribute for corresponding examples, and we mainly analyze the case in which we try to avoid finding a bad rule. Effectiveness of our approach is demonstrated through examples for conjunction-rule discovery. The second theory concerns a distribution-based case: it represents the conditions that a rule exceeds pre-specified thresholds for generality and accuracy with high reliability. The idea is to assume a 2-dimensional normal distribution for two probabilistic variables, and obtain the conditions based on their confidence region. This approach has been validated experimentally using 21 benchmark data sets in the machine learning community against conventional methods each of which evaluates the reliability of generality. Discussions on related work are provided for PAC learning, multiple comparison, and analysis of association-rule discovery.     

Testing a probabilistic FSM using interval estimation

In this paper, we propose a method to test a probabilistic FSM. The testing process consists of two parts. First, we check if there are any output faults or transfer faults in transitions. In order to identify a state of a PFSM, the characterization set is extended such that states are identified not only by observing output sequences but also by comparing probabilities. Second, we test whether the transition probabilities are correctly implemented. Interval estimation is used to assert the correctness of transition probabilities where a test verdict is assigned with a given confidence level. From a given confidence level and confidence interval length, a method is presented to determine the test sequence repetition numbers for testing probabilities. Fault coverage evaluation is carried out based on extended fault types where probabilities are changed. As an application, we apply the proposed method to a probabilistic non-repudiation protocol.     

On probabilistic inference by weighted model counting

A recent and effective approach to probabilistic inference calls for reducing the problem to one of weighted model counting (WMC) on a propositional knowledge base. Specifically, the approach calls for encoding the probabilistic model, typically a Bayesian network, as a propositional knowledge base in conjunctive normal form (CNF) with weights associated to each model according to the network parameters. Given this CNF, computing the probability of some evidence becomes a matter of summing the weights of all CNF models consistent with the evidence. A number of variations on this approach have appeared in the literature recently, that vary across three orthogonal dimensions. The first dimension concerns the specific encoding used to convert a Bayesian network into a CNF. The second dimensions relates to whether weighted model counting is performed using a search algorithm on the CNF, or by compiling the CNF into a structure that renders WMC a polytime operation in the size of the compiled structure. The third dimension deals with the specific properties of network parameters (local structure) which are captured in the CNF encoding. In this paper, we discuss recent work in this area across the above three dimensions, and demonstrate empirically its practical importance in significantly expanding the reach of exact probabilistic inference. We restrict our discussion to exact inference and model counting, even though other proposals have been extended for approximate inference and approximate model counting.     

Some methods for strategic decision‐making problems with immediate probabilities in Pythagorean fuzzy environment

In this article, a new decision‐making model with probabilistic information and using the concept of immediate probabilities has been developed to aggregate the information under the Pythagorean fuzzy set environment. In it, the existing probabilities have been modified by introducing the attitudinal character of the decision maker by using an ordered weighted average operator. Based on it, we have developed some new probabilistic aggregation operator with Pythagorean fuzzy information, namely probabilistic Pythagorean fuzzy weighted average operator, immediate probability Pythagorean fuzzy ordered weighted average operator, probabilistic Pythagorean fuzzy ordered weighted average, probabilistic Pythagorean fuzzy weighted geometric operator, immediate probability Pythagorean fuzzy ordered weighted geometric operator, probabilistic Pythagorean fuzzy ordered weighted geometric, etc. Furthermore, we extended these operators by taking interval‐valued Pythagorean fuzzy information and developed their corresponding aggregation operators. Few properties of these operators have also been investigated. Finally, an illustrative example about the selection of the optimal production strategy has been given to show the utility of the developed method.     

Latent-space variational bayes

Variational Bayesian Expectation-Maximization (VBEM), an approximate inference method for probabilistic models based on factorizing over latent variables and model parameters, has been a standard technique for practical Bayesian inference. In this paper, we introduce a more general approximate inference framework for conjugate-exponential family models, which we call Latent-Space Variational Bayes (LSVB). In this approach, we integrate out model parameters in an exact way, leaving only the latent variables. It can be shown that the LSVB approach gives better estimates of the model evidence as well as the distribution over latent variables than the VBEM approach, but in practice, the distribution over latent variables has to be approximated. As a practical implementation, we present a First-order LSVB (FoLSVB) algorithm to approximate this distribution over latent variables. From this approximate distribution, one can estimate the model evidence and the posterior over model parameters. The FoLSVB algorithm is directly comparable to the VBEM algorithm and has the same computational complexity. We discuss how LSVB generalizes the recently proposed collapsed variational methods [20] to general conjugate-exponential families. Examples based on mixtures of Gaussians and mixtures of Bernoullis with synthetic and real-world data sets are used to illustrate some advantages of our method over VBEM.     

Probabilistic Mobile Ambients

The calculus of Mobile Ambients has been introduced for expressing mobility and mobile computation. In this paper we present a probabilistic version of Mobile Ambients by augmenting the syntax of the original Ambient Calculus with a (guarded) probabilistic choice operator. To allow for the representation of both the probabilistic behaviour introduced through the new probabilistic choice operator and the nondeterminism present in the original Ambient Calculus we use probabilistic automata as the underpinning semantic model. The Ambient logic is a logic for Mobile Ambients that contains a novel treatment of both locations and hidden names. For specifying properties of Probabilistic Mobile Ambients, we extend this logic to specify probabilistic behaviour. In addition, to show the utility of our approach we present an example of a virus infecting a network.     

A study of uncertain state estimation

In this paper, we present results of uncertain state estimation of systems that are monitored with limited accuracy. For these systems, the representation of state uncertainty as confidence intervals offers significant advantages over the more traditional approaches with probabilistic representation of noise. While the filtered-white-Gaussian noise model can be defined on grounds of mathematical convenience, its use is necessarily coupled with a hope that an estimator with good properties in idealised noise will still perform well in real noise. In this study we propose a more realistic approach of matching the noise representation to the extent of prior knowledge. Both interval and ellipsoidal representation of noise illustrate the principle of keeping the noise model simple while allowing for iterative refinement of the noise as we proceed. We evaluate one nonlinear and three linear state estimation technique both in terms of computational efficiency and the cardinality of the state uncertainty sets. The techniques are illustrated on a synthetic and a real-life system.     

Approximate inference for medical diagnosis

Computer-based diagnostic decision support systems (DSSs) will play an increasingly important role in health care. Due to the inherent probabilistic nature of medical diagnosis, a DSS should preferably be based on a probabilistic model. In particular, Bayesian networks provide a powerful and conceptually transparent formalism for probabilistic modeling. A drawback is that Bayesian networks become intractable for exact computation if a large medical domain is to be modeled in detail. This has obstructed the development of a useful system for internal medicine. Advances in approximation techniques, e.g. using variational methods with tractable structures, have opened new possibilities to deal with the computational problem. However, the only way to assess the usefulness of these methods for a DSS in practice is by actually building such a system and evaluating it by users. In the coming years, we aim to build a DSS for anaemia based on a detailed probabilistic model, and equipped with approximate methods to study the practical feasibility and the usefulness of this approach in medical practice.In this paper, we will sketch how variational techniques with tractable structures can be used in a typical model for medical diagnosis. We provide numerical results on artificial problems. In addition, we describe our approach to develop the Bayesian network for the DSS and show some preliminary results.     

PrDB: managing and exploiting rich correlations in probabilistic databases

Due to numerous applications producing noisy data, e.g., sensor data, experimental data, data from uncurated sources, information extraction, etc., there has been a surge of interest in the development of probabilistic databases. Most probabilistic database models proposed to date, however, fail to meet the challenges of real-world applications on two counts: (1) they often restrict the kinds of uncertainty that the user can represent; and (2) the query processing algorithms often cannot scale up to the needs of the application. In this work, we define a probabilistic database model, PrDB, that uses graphical models, a state-of-the-art probabilistic modeling technique developed within the statistics and machine learning community, to model uncertain data. We show how this results in a rich, complex yet compact probabilistic database model, which can capture the commonly occurring uncertainty models (tuple uncertainty, attribute uncertainty), more complex models (correlated tuples and attributes) and allows compact representation (shared and schema-level correlations). In addition, we show how query evaluation in PrDB translates into inference in an appropriately augmented graphical model. This allows us to easily use any of a myriad of exact and approximate inference algorithms developed within the graphical modeling community. While probabilistic inference provides a generic approach to solving queries, we show how the use of shared correlations, together with a novel inference algorithm that we developed based on bisimulation, can speed query processing significantly. We present a comprehensive experimental evaluation of the proposed techniques and show that even with a few shared correlations, significant speedups are possible.     

Probabilistic voxel mapping using an adaptive confidence measure of stereo matching

In this paper, we describe a probabilistic voxel mapping algorithm using an adaptive confidence measure of stereo matching. Most of the 3D mapping algorithms based on stereo matching usually generate a map formed by point cloud. There are many reconstruction errors. The reconstruction errors are due to stereo reconstruction error factors such as calibration errors, stereo matching errors, and triangulation errors. A point cloud map with reconstruction errors cannot accurately represent structures of environments and needs large memory capacity. To solve these problems, we focused on the confidence of stereo matching and probabilistic representation. For evaluation of stereo matching, we propose an adaptive confidence measure that is suitable for outdoor environments. The confidence of stereo matching can be reflected in the probability of restoring structures. For probabilistic representation, we propose a probabilistic voxel mapping algorithm. The proposed probabilistic voxel map is a more reliable representation of environments than the commonly used voxel map that just contains the occupancy information. We test the proposed confidence measure and probabilistic voxel mapping algorithm in outdoor environments.     

Robust LQR design for systems with probabilistic uncertainty

In this paper, we consider the design of robust quadratic regulators for linear systems with probabilistic uncertainty in system parameters. The synthesis algorithms are presented in a convex optimization framework, which optimize with respect to an integral cost. The optimization problem is formulated as a lower‐bound maximization problem and developed in the polynomial chaos framework. Two approaches are considered here. In the first approach, an exact optimization problem is formulated in the infinite‐dimensional space, which is solved approximately using polynomial‐chaos expansions. In the second approach, an approximate problem is formulated using a reduced‐order model and solved exactly. The robustness of the controllers from these two approaches are compared using a realistic flight control problem based on an F16 aircraft model. Linear and nonlinear simulations reveal that the first approach results in a more robust controller.