Construction and Methods of Learning of Bayesian Networks

Methods of learning Bayesian networks from databases, basic concepts of Bayesian networks, basic methods of learning, methods of learning parameters, and the structures of a network and hidden parameters are considered. Basic definitions and key concepts with illustrative examples are presented. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 133–147, July–August 2005.     

Troubleshooting: NP-hardness and solution methods

 Troubleshooting is one of the areas where Bayesian networks are successfully applied [9]. In this paper we show that the generally defined troubleshooting task is NP-hard. We propose a heuristic function that exploits the conditional independence of all actions and questions given the fault of the device. It can be used as a lower bound of the expected cost of repair in heuristic algorithms searching an optimal troubleshooting strategy. In the paper we describe two such algorithms: the depth first search algorithm with pruning and the AO^* algorithm. RID="*" ID="*" The authors were supported through grant #87.2 of National Centre for IT Research, Denmark and through grant MSMT VS96008 from the Ministry of Education, Youth and Sports of the Czech Republic. We would like to thank Finn Verner Jensen for inspiring us to work on the discussed problem and for many valuable comments on this paper. We are grateful to Claus Skaanning for the detailed explanation of the BATS troubleshooter approach and to anonymous reviewers for helpful suggestions.     

Functional Topology Classification of Biological Computing Networks

Current analyses of complex biological networks focus either on their global statistical connectivity properties (e.g. topological path lengths and nodes connectivity ranks) or the statistics of specific local connectivity circuits (motifs). Here we present a different approach – Functional Topology, to enable identification of hidden topological and geometrical fingerprints of biological computing networks that afford their functioning – the form-function fingerprints. To do so we represent the network structure in terms of three matrices: 1. Topological connectivity matrix – each row (i) is the shortest topological path lengths of node i with all other nodes; 2. Topological correlation matrix – the element (i,j) is the correlation between the topological connectivity of nodes (i) and (j); and 3. Weighted graph matrix – in this case the links represent the conductance between nodes that can be simply one over the geometrical length, the synaptic strengths in case of neural networks or other quantity that represents the strengths of the connections. Various methods (e.g. clustering algorithms, random matrix theory, eigenvalues spectrum etc.), can be used to analyze these matrices, here we use the newly developed functional holography approach which is based on clustering of the matrices following their collective normalization. We illustrate the approach by analyzing networks of different topological and geometrical properties: 1. Artificial networks, including – random, regular 4-fold and 5-fold lattice and a tree-like structure; 2. Cultured neural networks: A single network and a network composed of three linked sub-networks; and 3. Model neural network composed of two overlapping sub-networks. Using these special networks, we demonstrate the method’s ability to reveal functional topology features of the networks.     

Short term memory in recurrent networks of spiking neurons

We present in this paper a general model of recurrent networks of spiking neurons, composed of several populations, and whose interaction pattern is set with a random draw. We use for simplicity discrete time neuron updating, and the emitted spikes are transmitted through randomly delayed lines. In excitatory-inhibitory networks, we show that inhomogeneous delays may favour synchronization provided that the inhibitory delays distribution is significantly stronger than the excitatory one. In that case, slow waves of synchronous activity appear (this synchronous activity is stronger in inhibitory population). This synchrony allows for a fast ada ptivity of the network to various input stimuli. In networks observing the constraint of short range excitation and long range inhibition, we show that under some parameter settings, this model displays properties of –1– dynamic retention –2– input normalization –3– target tracking. Those properties are of interest for modelling biological topologically organized structures, and for robotic applications taking place in noisy environments where targets vary in size, speed and duration. This revised version was published online in June 2006 with corrections to the Cover Date.     

A Petri net representation of Bayesian message flows: importance of Bayesian networks for biological applications

This article combines Bayes’ theorem with flows of probabilities, flows of evidences (likelihoods), and fundamental concepts for learning Bayesian networks as biological models from data. There is a huge amount of biological applications of Bayesian networks. For example in the fields of protein modeling, pathway modeling, gene expression analysis, DNA sequence analysis, protein–protein interaction, or protein–DNA interaction. Usually, the Bayesian networks have to be learned (statistically constructed) from array data. Then they are considered as an executable and analyzable model of the data source. To improve that, this work introduces a Petri net representation for the propagation of probabilities and likelihoods in Bayesian networks. The reason for doing so is to exploit the structural and dynamic properties of Petri nets for increasing the transparency of propagation processes. Consequently the novel Petri nets are called “probability propagation nets”. By means of examples it is shown that the understanding of the Bayesian propagation algorithm is improved. This is of particular importance for an exact visualization of biological systems by Bayesian networks.     

The application of ridge polynomial neural network to multi-step ahead financial time series prediction

Motivated by the slow learning properties of multilayer perceptrons (MLPs) which utilize computationally intensive training algorithms, such as the backpropagation learning algorithm, and can get trapped in local minima, this work deals with ridge polynomial neural networks (RPNN), which maintain fast learning properties and powerful mapping capabilities of single layer high order neural networks. The RPNN is constructed from a number of increasing orders of Pi–Sigma units, which are used to capture the underlying patterns in financial time series signals and to predict future trends in the financial market. In particular, this paper systematically investigates a method of pre-processing the financial signals in order to reduce the influence of their trends. The performance of the networks is benchmarked against the performance of MLPs, functional link neural networks (FLNN), and Pi–Sigma neural networks (PSNN). Simulation results clearly demonstrate that RPNNs generate higher profit returns with fast convergence on various noisy financial signals.     

Bayes网络最优近似下边缘分布的不变性

删除Bayes网络中的弧以减小网络结构的复杂性，从而降低概率推理算法的复杂度是一种对Bayes网络进行近似的方法．该文讨论了在删除Bayes网络中的一条弧之后得到的最优近似概率分布和原概率分布之间的关系，证明了对满足一定条件的结点子集而言，其边缘概率分布在近似以后具有不变性．     

Learning probabilistic classifiers for human–computer interaction applications

Human–computer interaction (HCI) lies at the crossroads of many scientific areas including artificial intelligence, computer vision, face recognition, motion tracking, etc. It is argued that to truly achieve effective human–computer intelligent interaction, the computer should be able to interact naturally with the user, similar to the way HCI takes place. In this paper, we discuss training probabilistic classifiers with labeled and unlabeled data for HCI applications. We provide an analysis that shows under what conditions unlabeled data can be used in learning to improve classification performance, and we investigate the implications of this analysis to a specific type of probabilistic classifiers, Bayesian networks. Finally, we show how the resulting algorithms are successfully employed in facial expression recognition, face detection, and skin detection.     

Accuracy vs. Lifetime: Linear Sketches for Aggregate Queries in Sensor Networks

The in–network aggregation paradigm in sensor networks provides a versatile approach for evaluating aggregate queries. Traditional approaches need a separate aggregate to be computed and communicated for each query and hence do not scale well with the number of queries. Since approximate query results are sufficient for many applications, we use an alternate approach based on summary data–structures. We consider two kinds of aggregate queries: location range queries that compute the sum of values reported by sensors in a given location range, and value range queries that compute the number of sensors that report values in a given range. We construct summary data–structures called linear sketches, over the sensor data using in–network aggregation and use them to answer aggregate queries in an approximate manner at the base–station. There is a trade–off between accuracy of the query results and lifetime of the sensor network that can be exploited to achieve increased lifetimes for a small loss in accuracy. Most commonly occurring sets of range queries are highly correlated and display rich algebraic structure. Our approach takes full advantage of this by constructing linear sketches that depend on queries. Experimental results show that linear sketching achieves significant improvements in lifetime of sensor networks for only a small loss in accuracy of the queries. Further, our approach achieves more accurate query results than the other classical techniques using Discrete Fourier Transform and Discrete Wavelet Transform. This work was supported in part by NASA under Cooperative Agreement NCC5–315.     

A Bayesian Method for the Induction of Probabilistic Networks from Data

This paper presents a Bayesian method for constructing probabilistic networks from databases. In particular, we focus on constructing Bayesian belief networks. Potential applications include computer-assisted hypothesis testing, automated scientific discovery, and automated construction of probabilistic expert systems. We extend the basic method to handle missing data and hidden (latent) variables. We show how to perform probabilistic inference by averaging over the inferences of multiple belief networks. Results are presented of a preliminary evaluation of an algorithm for constructing a belief network from a database of cases. Finally, we relate the methods in this paper to previous work, and we discuss open problems.     

Coherence checking and propagation of lower probability bounds

 In this paper we use imprecise probabilities, based on a concept of generalized coherence (g-coherence), for the management of uncertain knowledge and vague information. We face the problem of reducing the computational difficulties in g-coherence checking and propagation of lower conditional probability bounds. We examine a procedure, based on linear systems with a reduced number of unknowns, for the checking of g-coherence. We propose an iterative algorithm to determine the reduced linear systems. Based on the same ideas, we give an algorithm for the propagation of lower probability bounds. We also give some theoretical results that allow, by suitably modifying our algorithms, the g-coherence checking and propagation by working with a reduced set of variables and/or with a reduced set of constraints. Finally, we apply our algorithms to some examples. RID="*" ID="*" This paper is a revised and substantially extended version of a previous paper by the same authors, appeared in the Proc. of the 5th Workshop on Uncertainty Processing (WUPES'2000), Jindřichu̇v Hradec, Czech Republic, June 21–24, 1–13, 2000.     

Study on IAC networks models: learning and stability

This paper presents a methodology that uses evolutionary learning in training ‘A’ model networks, a topology based on Interactive Activation and Competition (IAC) neural networks. IAC networks show local knowledge and processing units clustered in pools. The connections among units may assume only 1, 0 or −1. On the other hand, ‘A’ model network uses values in interval [−1, 1]. This feature provides a wider range of applications for this network, including problems which do not show mutually exclusive concepts. However, there is no algorithm to adjust the network weights and still preserve the desired characteristics of the original network. Accordingly, we propose the use of genetic algorithms in a new methodology to obtain the correct weight set for this network. Two examples are used to illustrate the proposed method. Findings are considered consistent and generic enough to allow further applications on similar classes of problems suitable for ‘A’ model IAC Networks.     

The Neural Network Approach to Input–Output Analysis for Economic Systems

Economic practitioners in China are giving up the classical Leontief’s Input–Output analysis methods. This paper offers an alternative method of input–output analysis. The proposed method is based on the layered neural network model. It shows that neural networks method can be useful for input–output analysis for a dynamic economic system.       

Discovering excitatory relationships using dynamic Bayesian networks

Mining temporal network models from discrete event streams is an important problem with applications in computational neuroscience, physical plant diagnostics, and human–computer interaction modeling. In this paper, we introduce the notion of excitatory networks which are essentially temporal models where all connections are stimulative, rather than inhibitive. The emphasis on excitatory connections facilitates learning of network models by creating bridges to frequent episode mining. Specifically, we show that frequent episodes help identify nodes with high mutual information relationships and that such relationships can be summarized into a dynamic Bayesian network (DBN). This leads to an algorithm that is significantly faster than state-of-the-art methods for inferring DBNs, while simultaneously providing theoretical guarantees on network optimality. We demonstrate the advantages of our approach through an application in neuroscience, where we show how strong excitatory networks can be efficiently inferred from both mathematical models of spiking neurons and several real neuroscience datasets.     

A roadmap of fuzzy logic in ATM,mobile and active networks: challenges of the new century

 ATM networking technology was conceived 20 years ago, and installations will reach their peak the next 10 years. Active networks will be the technology which will follow the ATM. In this article, we address the most important issues regarding recent advances and future perspectives in ATM, including IP/ATM integration, Active Networks, MobileActive Networks and the impact of fuzzy technology in solving the important problems of the above future networking technologies. In the new century it is imperative that we shift from a technology to an application (needs of consumers) focus, where ubiquitous and invisible (context-aware) computing will be a reality.     

Self-stabilizing smoothing and balancing networks

A smoothing network is a distributed data structure that accepts tokens on input wires and routes them to output wires. It ensures that however imbalanced the traffic on input wires, the numbers of tokens emitted on output wires are approximately balanced. Prior work on smoothing networks always assumed that such networks were properly initialized. In a real distributed system, however, network switches may be rebooted or replaced dynamically, and it may not be practical to determine the correct initial state for the new switch. Prior analyses do not work under these new assumptions. This paper makes the following contributions. First, we show that some well-known 1-smoothing networks, known as counting networks, when started in an arbitrary initial state (perhaps chosen by an adversary), remain remarkably smooth, degrading from 1-smooth to (log n)-smooth, where n is the number of input/output wires. For the networks that we consider, we show that the above (log n) bound for the smoothness is tight. Our second contribution is to show how any balancing network can be made self-stabilizing with the addition of local stabilization actions and state, which restore the network back to a “legal state” even if it starts out in an illegal state. A preliminary version of this work appeared in the Proceedings of The 23rd International Conference on Distributed Computing Systems, Providence, Rhode Island, USA.     

Cluster ranking with an application to mining mailbox networks

We initiate the study of a new clustering framework, called cluster ranking. Rather than simply partitioning a network into clusters, a cluster ranking algorithm also orders the clusters by their strength. To this end, we introduce a novel strength measure for clusters—the integrated cohesion—which is applicable to arbitrary weighted networks. We then present a new cluster ranking algorithm, called C-Rank. We provide extensive theoretical and empirical analysis of C-Rank and show that it is likely to have high precision and recall. A main component of C-Rank is a heuristic algorithm for finding sparse vertex separators. At the core of this algorithm is a new connection between vertex betweenness and multicommodity flow. Our experiments focus on mining mailbox networks. A mailbox network is an egocentric social network, consisting of contacts with whom an individual exchanges email. Edges between contacts represent the frequency of their co–occurrence on message headers. C-Rank is well suited to mine such networks, since they are abundant with overlapping communities of highly variable strengths. We demonstrate the effectiveness of C-Rank on the Enron data set, consisting of 130 mailbox networks.     

Convergence analysis of convex incremental neural networks

Recently, a convex incremental algorithm (CI-ELM) has been proposed in Huang and Chen (Neurocomputing 70:3056–3062, 2007), which randomly chooses hidden neurons and then analytically determines the output weights connecting with the hidden layer and the output layer. Though hidden neurons are generated randomly, the network constructed by CI-ELM is still based on the principle of universal approximation. The random approximation theory breaks through the limitation of most conventional theories, eliminating the need for tuning hidden neurons. However, due to the random characteristic, some of the neurons contribute little to decrease the residual error, which eventually increase the complexity and computation of neural networks. Thus, CI-ELM cannot precisely give out its convergence rate. Based on Lee’s results (Lee et al., IEEE Trans Inf Theory 42(6):2118–2132, 1996), we first show the convergence rate of a maximum CI-ELM, and then systematically analyze the convergence rate of an enhanced CI-ELM. Different from CI-ELM, the hidden neurons of the two algorithms are chosen by following the maximum or optimality principle under the same structure as CI-ELM. Further, the proof process also demonstrates that our algorithms achieve smaller residual errors than CI-ELM. Since the proposed neural networks remove these “useless” neurons, they improve the efficiency of neural networks. The experimental results on benchmark regression problems will support our conclusions. The work is under the funding of Singapore MOE AcRF Tier 1 grant WBS No: R 252-000-221-112.     

Intelligent management of distributed dynamic sensor networks

A universal solution for the management of dynamic sensor networks will be presented, covering both networking and application layers. A network of intelligent modules, overlaying the sensor network, collectively interprets mission scenarios in a special high-level language, which can start from any nodes and cover the network at runtime. The spreading scenarios are extremely compact, which may be useful for energy-saving communications. The code will be exhibited for distributed collection and fusion of sensor data, and also for tracking mobile targets by scattered and communicating sensors. This work was presented in part at the 12th International Symposium on Artificial Life and Robotics, Oita, Japan, January 25–27, 2007     

Boundedness analysis for open Chemical Reaction Networks with mass-action kinetics

This paper describes the working principles of an algorithm for boundedness analysis of open Chemical Reaction Networks endowed with mass-action kinetics. Such models can be thought of both as a special class of compartmental systems or a particular type of continuous Petri Nets, in which the firing rates of transitions are not constant or preassigned, but expressed as a function of the continuous marking of the network (function which in chemistry is referred to as the “kinetics”). The algorithm can be applied to a broad class of such open networks, and returns, as an outcome, a classification of the possible dynamical behaviors that are compatible with the network structure, by classifying each variable either as bounded, converging to 0 or diverging to ∞. This can be viewed as a qualitative study of Input–Output Stability for chemical networks, or more precisely, as a classification of its possible I–O instability patterns. Our goal is to analyze the system irrespectively of values of kinetic parameters. More precisely, we attempt to analyze it simultaneously for all possible values. Remarkably, tests on non-trivial examples (one of which is discussed in this paper) showed that, as the kinetic constants of the network are varied, all the compatible behaviors could be observed in simulations. Finally, we discuss and illustrate how the results relate to previous works on the qualitative dynamics of closed reaction networks.