The Dempster-Shafer (DS) belief theory constitutes a powerful framework for modeling and reasoning with a wide variety of uncertainties due to its greater expressiveness and flexibility. As in the Bayesian probability theory, the DS theoretic (DST) conditional plays a pivotal role in DST strategies for evidence updating and fusion. However, a major limitation in employing the DST framework in practical implementations is the absence of an efficient and feasible computational framework to overcome the prohibitive computational burden DST operations entail. The work in this article addresses the pressing need for efficient DST conditional computation via the novel computational model DS-Conditional-All. It requires significantly less time and space complexity for computing the Dempster's conditional and the Fagin-Halpern conditional, the two most widely utilized DST conditional strategies. It also provides deeper insight into the DST conditional itself, and thus acts as a valuable tool for visualizing and analyzing the conditional computation. We provide a thorough analysis and experimental validation of the utility, efficiency, and implementation of the proposed data structure and algorithms. A new computational library, which we refer to as DS-Conditional-One and DS-Conditional-All (DS-COCA), is developed and harnessed in the simulations.

Adequate representative statistical training data needed for machine learning algorithms are often unavailable and, when available, they are often mired in incomplete/missing data. Imputation of such data must be guided by the relationships among different variables and/or by data `missingness' mechanisms. Interval-valued (IV) probabilities are better suited in situations where such information is unavailable. We take the viewpoint that IV probabilities (IVPs) emerge from a single underlying probability distribution about which one has only partial information. PrBounds, the IVPs that this vantage point engenders, offer a fresh perspective of the IV counterpart notions of conditioning and independence and enable reasoning to be carried out in much the same manner as one would with probabilities. When the attribute values are unknown/missing or are known to lie within a set of values, PrBounds can be efficiently learnt by a frequency counting method. The probabilities associated with an arbitrary imputation strategy, including the underlying `true' probabilities, are guaranteed to lie within the PrBounds learnt in this manner. We present an experiment to illustrate the proposed framework.

The problem of inferring the hidden state of individual nodes in social/sensor networks in which node activities affect their neighbors is growing in importance. We present an undirected generative model, a type of probabilistic model that has so far not been used for modeling latent variables influenced by neighbors in a network. We also propose an efficient inference method based on variational inference principles which, in contrast to sampling methods used in most existing models, is scalable to larger networks. While training is intractable in general, by using stochastic methods to approximate the intractable derivative, we show that our model can be trained using the maximum likelihood method by formulating the model as an exponential family distribution. The results demonstrate that the proposed undirected model can accurately infer latent states compared to baseline methods.

Fluorescence spectroscopic excitation-emission matrices (EEMs) can be used to characterize dissolved organic matter in water with high sensitivity. Our goal is to predict the standard biosensor-based measurement Microtox® utilizing EEMs, pH, turbidity and conductivity, among other variables. EEMs h ave been modeled using novel latent fluorescent Dirichlet allocation (LFDA) based probabilistic graphical model. We found that nonparametric techniques offer a better mapping from, LFDA based EEMs scores and other measurements, to Microtox® measurements. The final decision on Microtox® measurement is given using an evidence fusion mechanism. In general, the novel LFDA based graphical model can be utilized in analyzing two dimensional data.

Variable higher pulse repetition frequencies (PRFs) are increasingly being used to meet the stricter requirements and complexities of current airborne and spaceborne synthetic aperture radar (SAR) systems associated with higher resolution and wider area products. POLYPHASE, the proposed resampling scheme, downsamples and unifies variable PRFs within a single look complex SAR acquisition and across a repeat pass sequence of acquisitions down to an effective lower PRF. A sparsity condition of the received SAR data ensures that the uniformly resampled data approximate the spectral properties of a decimated densely sampled version of the received SAR data. While experiments conducted with both synthetically generated and real airborne SAR data show that POLYPHASE retains comparable performance with the state-of-the-art best linear unbiased interpolation scheme in image quality, a polyphase filter-based implementation of POLYPHASE offers significant computational savings for arbitrary (not necessarily periodic) input PRF variations, thus allowing fully on-board, in-place, and real-time implementation.

We examine the design of self-organizing mobile adaptive networks with multiple targets in which the network nodes form distinct clusters to learn about and purse multiple targets, all while moving in a cohesive collision-free manner. We build upon previous distributed diffusion-based adaptive learning networks that focused on a single target to examine the case with multiple targets in which the nodes do not know the number of targets, and exchange local information with their neighbors in their learning objectives. In particular, we design a method allowing the nodes to switch the target they are tracking thereby engendering the formation of distinct stable learning groups that can split up and purse their distinct targets over time. We provide analytical mean stability and steady state mean-square deviation results along with simulations that demonstrate the efficacy of the proposed method.

In this paper, we present a novel latent Dirichlet allocation (LDA) based probabilistic graphical approach for modeling and analyzing fluorescent spectroscopy excitation-emission Matrices (EEMs). By viewing the EEMs as being generated from an underlying hidden pool of flourophore compounds, the pro posed method provides a latent flourophore-space representation of an EEM. We show that this LDA-based model can increase classification performance, especially when paired with parallel factor analysis (PARAFAC) which may be regarded as perhaps the most popular and widely used tool for dealing with EEMs. Our experiments show that the proposed LDA-based algorithm is in some cases more robust than PARAFAC to certain types of noise and data disturbances. We also observe that pairing this LDA-based method with PARAFAC leads to an improvement in classification performance and to added robustness at high peak-signal-to-noise-ratio (PSNR) values.

In a multi-agent data fusion scenario, agents may iteratively exchange their states to arrive at a consensus state which signifies ‘general agreement’ among the agents. Agent states that are being exchanged may have been generated from hard (i.e., physics based) or soft (i.e., human based evidence. such as opinions or beliefs regarding an event) sensors. Convergence analysis becomes an extremely challenging problem in such complex fusion environments, which may involve communication delays, ad-hoc paths, etc. In this paper, we analyze consensus of a Dempster-Shafer theoretic (DST) fusion operator by formulating the consensus problem as finding common fixed points of a pool of paracontracting operators. Due to its DST basis, this consensus protocol can deal with a wider variety of data imperfections characteristic of hard+soft data fusion environments. It also easily adapts itself to networks where agent states are captured with probability mass functions because they can be considered a special case of DST models.

Dempster-Shafer (DS) belief theory provides a convenient framework for the development of powerful data fusion engines by allowing for a convenient representation of a wide variety of data imperfections. The recent work on the DS theoretic (DST) conditional approach, which is based on the Fagin-Halpern (FH) DST conditionals, appears to demonstrate the suitability of DS theory for incorporating both soft (generated by human-based sensors) and hard (generated by physics-based sources) evidence into the fusion process. However, the computation of the FH conditionals imposes a significant computational burden. One reason for this is the difficulty in identifying the FH conditional core, i.e., the set of propositions receiving nonzero support after conditioning. The conditional core theorem (CCT) in this paper redresses this shortcoming by explicitly identifying the conditional focal elements with no recourse to numerical computations, thereby providing a complete characterization of the conditional core. In addition, we derive explicit results to identify those conditioning propositions that may have generated a given conditional core. This "converse" to the CCT is of significant practical value for studying the sensitivity of the updated knowledge base with respect to the evidence received. Based on the CCT, we also develop an algorithm to efficiently compute the conditional masses (generated by FH conditionals), provide bounds on its computational complexity, and employ extensive simulations to analyze its behavior.

In many contexts, one is confronted with the problem of extract ing information from large amounts of different types soft data (e.g., text) and hard data (from e.g., physics-based sensing systems). In handling hard data, signal and data processing offers a wealth of methods related to modeling, estimation, tracking, and inference tasks. However, soft data present several challenges that necessitate the development of new data processing methods. For example, with suitable statistical natural language processing (NLP) methods, text can be converted into logic statements that are associated with various forms of associated uncertainty related to the credibility of the statement, the reliability of the text source, and so forth. In combining or fusing soft data with either soft or hard data, one must deploy methods that can suitably preserve and update the uncertainty associated with the data, thereby providing uncertainty bounds related to any inferences regarding semantics. Since standard Bayesian probabilistic approaches have problems with suitably handling uncertain logic statements, there is an emerging need for new methods for processing heterogeneous data. In this paper, we describe a framework for fusing soft and hard data based on the Dempster-Shafer (DS) belief theoretic approach which is well-suited to the task of capturing the types of models and uncertain rules that are more typical of soft data. Since the effectiveness of traditional DS methods has been hampered by high computational requirements, we base the processing framework on our new conditional approach to DS theoretic evidence updating and fusion. We address the issue of laying the foundation for a theoretically justifiable, and computationally efficient framework for fusing soft and hard data taking into account the inherent data uncertainty such as reliability and credibility. Moreover, we present an illustrative ex ample that highlights the potential for the DS conditional approach for fusing heterogeneous data.

Automated Collaborative Filtering (ACF) refers to a group of algorithms used in recommender systems, a research topic that has received considerable attention due to its e-commerce applications. However, existing techniques are rarely capable of dealing with imperfections in user-supplied ratings. When such imperfections (e.g., ambiguities) cannot be avoided, designers resort to simplifying assumptions that impair the system's performance and utility. We have developed a novel technique referred to as CoFiDS—Collaborative Filtering based on Dempster-Shafer belief-theoretic framework—that can represent a wide variety of data imperfections, propagate them throughout the decision-making process without the need to make simplifying assumptions, and exploit contextual information. With its DS-theoretic predictions, the domain expert can either obtain a "hard” decision or can narrow the set of possible predictions to a smaller set. With its capability to handle data imperfections, CoFiDS widens the applicability of ACF to such critical and sensitive domains as medical decision support systems and defense-related applications. We describe the theoretical foundation of the system and report experiments with a benchmark movie data set. We explore some essential aspects of CoFiDS' behavior and show that its performance compares favorably with other ACF systems.

Existing research in association mining has focused mainly on how to expedite the search for frequently co-occurring groups of items in ldquoshopping cartrdquo type of transactions; less attention has been paid to methods that exploit these ldquofrequent itemsetsrdquo for prediction purposes. This paper contributes to the latter task by proposing a technique that uses partial information about the contents of a shopping cart for the prediction of what else the customer is likely to buy. Using the recently proposed data structure of itemset trees (IT-trees), we obtain, in a computationally efficient manner, all rules whose antecedents contain at least one item from the incomplete shopping cart. Then, we combine these rules by uncertainty processing techniques, including the classical Bayesian decision theory and a new algorithm based on the Dempster-Shafer (DS) theory of evidence combination.

In a multisensor target tracking application running on a shared network, at what bit rates should the sensors send their measurements to the tracking fusion center? Clearly, the sensors cannot use arbitrary rates in a shared network, and a standard network rate control algorithm may not provide rates amenable to effective target tracking. For Kalman filter-based multisensor target tracking, we derive a utility function that captures the tracking quality of service as a function of the sensor bit rates. We incorporate this utility function into a network rate resource allocation framework, deriving a distributed rate control algorithm for a shared network that is suitable for current best effort packet networks, such as the Internet. In simulation studies, the new rate control algorithm engenders significantly better tracking performance than a standard rate control method, while the ordinary data transfer flows continue to effectively operate while using their standard rate control methods.

In a multi-sensor target tracking application running on a shared network, at what bit-rates should the sensors send their measurements to the tracking fusion center? Clearly, the sensors cannot use arbitrary rates in a shared network, and a standard network rate control algorithm may not provide rates amenable to effective target tracking. For Kalman Filter-based multi-sensor target tracking, we derive a utility function that captures the tracking Quality of Service as a function of bit-rate. We incorporate this utility function into a network rate resource allocation framework, deriving a distributed rate control algorithm for a shared network that does not require network re-design. In simulation studies, the new rate-control algorithm engenders much better tracking performance than a standard rate-control method.

Bayesian networks (BNs) represent joint space probabilities compactly and enable one to carry out efficient inferencing. Although the Dempster-Shafer (DS) belief theoretic framework captures a wider class of imperfections, its utility in such graphical models is limited. This is mainly due to the requirement of having to maintain a basic probability assignment (BPA) for the whole power set of propositions of interest. In this paper, we introduce a simpler BPA that can still capture many types of imperfections that are commonly encountered in practice. This BPA is then used to develop the DS-BN, a graphical dependency model that represents the joint space belief distribution. We show how this DS-BN can efficiently carry out inferences within the DS theoretic framework. Its utility is illustrated by modeling a problem involving missing values and then comparing the inferences made with those obtained via a BN that learns its parameters using the EM algorithm.

Management of data imprecision and uncertainty has become increasingly important, especially in situation awareness and assessment applications where reliability of the decision-making process is critical (e.g., in military battlefields). These applications require the following: 1) an effective methodology for modeling data imperfections and 2) procedures for enabling knowledge discovery and quantifying and propagating partial or incomplete knowledge throughout the decision-making process. In this paper, using a Dempster-Shafer belief-theoretic relational database (DS-DB) that can conveniently represent a wider class of data imperfections, an association rule mining (ARM)-based classification algorithm possessing the desirable functionality is proposed. For this purpose, various ARM-related notions are revisited so that they could be applied in the presence of data imperfections. A data structure called belief itemset tree is used to efficiently extract frequent itemsets and generate association rules from the proposed DS-DB. This set of rules is used as the basis on which an unknown data record, whose attributes are represented via belief functions, is classified. These algorithms are validated on a simplified situation assessment scenario where sensor observations may have caused data imperfections in both attribute values and class labels.

A framework for the combination of evidence in an environment where data are generated from heterogeneous sources possessing partial or incomplete knowledge about the global network scenario is presented. The approach taken is based on the conditional belief and plausibility notions in Dempster-Shafer evidence theory that allow one to condition these partial knowledge bases so that only that portion of the incoming evidence that is relevant is utilized for updating an existing knowledge base. The strategy proposed enables one to accommodate some of the most challenging, yet essential, features that are encountered when evidence is generated from possibly a large numbers of sources. These include heterogeneity and reliability of incoming evidence, inertia and integrity of evidence already gathered, and potentially limited resources at the nodes where evidence updating is carried out. The proposed framework is applied in robot map discovery using ultrasonic sensors and a real-world scenario where sensor data generated by heterogeneous sensors are used for potential threat carrier-type detection

Depending upon the type of feedback that is utilized, network congestion control schemes can be classified into two categories: marking/loss based (e.g., TCP Reno) or delay based (e.g., TCP Vegas). Delay-based schemes have garnered much attention due to their higher network throughput than loss-based methods. Delay provides a much finer-grained measure of congestion than packet loss or packet marking feedback. However, when there are multiple bottleneck links or inadequate buffer sizes in the path between a source and destination, delay information alone is insufficient for revealing the incipient network congestion. In this paper, we consider the design of a congestion control scheme that transcends the two normal categories and instead jointly exploits both delay and marking/loss feedback. In particular, we introduce the concept of normalized queuing delay, and demonstrate how a controller based on joint feedback provides high throughput even under highly dynamic network conditions as evidenced by ns2 simulations.

A novel approach named recursive evidence filtering for information processing in distributed sensor networks (DSNs) is presented. It is based on the Dempster-Shafer (DS) formalism, facilitating evidence exchange and fusion in a simple and straightforward manner, while accommodating for partial and incomplete information. Certain restrictions on the coefficients impose several challenges in the design of such evidence filters suggesting that arbitrary frequency shaping is not possible. A general design procedure for IIR type evidence filters is presented with examples

TCP congestion avoidance mechanisms determine methods by which a source adjusts its window size according to network conditions. Although network calculus has been utilized to study window flow control, the use of network calculus to determine an optimal window controller and to provide analytical guidance to TCP congestion avoidance has persisted as an open problem. For the first time within a network calculus setting, we determine an optimal window size control method for general flow control problems. We also show that the basic TCP congestion avoidance mechanisms in TCP Vegas, enhanced TCP Vegas and fast TCP can be viewed as different approaches to approximating the optimal NC controller, with each TCP variant making different assumptions in terms of parameter estimation and control implementation strategy. Therefore, the network calculus controller reveals the inherent underlying structure in TCP congestion avoidance. Furthermore, we demonstrate through ns-2 simulations that an approximation of a particular NC controller achieves performance gains in terms of link throughput and source node throughput fairness with respect to TCP Vegas, enhanced TCP Vegas and fast TCP.

A distributed task-oriented self-organization algorithm that enables sensors in an ad-hoc network to organize them according to the task being announced is proposed in this paper. When a task is announced, a distributed leader election algorithm is used to select the sensor that best 'matches' the announced task based on minimizing a distance measure between the task and sensor specifications. The selected sensor then uses a task decomposition method to generate and announce the residual tasks that 'cover' the matching error. In this manner, sensors are sequentially selected until all residual tasks are 'covered'. All sensors selected by the algorithms from a sensor group for the originally announced task. To improve the communication overhead of a previous version of this algorithm, location information of each sensor is used to dynamically maintain a contributor group of sensors that may contribute to the announced task. Leader election and all task announcements are confined to this group.

A new, more realistic model for the available bit rate traffic class in ATM network congestion control with explicit rate feedback is introduced and analyzed. This model is based on recent results by M.M. Ekanayake ("Robust stability of discrete time nonlinear systems", Ph.D. dissertation, Univ. Miami, Coral Gables, FL, 1999) regarding discrete time models for time-variant delays. The discrete time model takes into account the effect of time-variant buffer occupancy levels of ATM switches, thus treating the case of time-variant delays between a single congested node and the connected sources. For highly dynamic situations, such a model is crucial for a valid analysis of the resulting feedback system. The new model also handles the effects of the mismatch between the resource management cell rates and the variable bit rate controller sampling rate as well as buffer and rate nonlinearities. A brief stability study shows that an equilibrium in the buffer occupancy is impossible to achieve in the presence of time-variant forward path delays. Stability conditions for the case of time-variant delays in the return path are presented. Finally, illustrative examples are provided.

Suppose the rate of change of coefficients of a linear time-variant system modeled via a difference equation is restricted. The work presented is an attempt at developing an algorithm that determines regions in the coefficient-space where such a system is guaranteed to be globally asymptotically stable. Such information can be extremely useful in many applications, such as adaptive signal processing and control. Some previously published related results are consolidated as well.

In this paper, an algorithm that can be utilized to determine the presence or absence of limit cycles in fixed-point implementation of digital filters is given. It is applicable for filters in state-space formulation (and hence, application to the corresponding direct form follows as a special case), and is independent of the order, type of quantization, and whether the accumulator is single- or double-length. Bounds on the amplitude and period of possible limit cycles are presented. The robustness of the algorithm in terms of limit cycle performance with respect to filter coefficient perturbations is verified. The algorithm is then used to obtain regions in the coefficient space where a filter of given order is limit cycle free. In this process, we have obtained limit cycle free regions that were previously unknown for the two's complement case.

This paper analyzes the problem of global asymptotic stability of delta-operator formulated discrete-time systems implemented in fixed-point arithmetic. It is shown that the free response of such a system tends to produce period one limit cycles if conventional quantization arithmetic schemes are used. Explicit necessary conditions for global asymptotic stability are derived, and these demonstrate that, in almost all cases, fixed-point arithmetic does not allow for global asymptotic stability in delta-operator formulated discrete-time systems that use a short sampling time.>