Guoliang LI Lining XING Zhongshan ZHANG Yingwu CHEN
Bayesian networks are a powerful approach for representation and reasoning under conditions of uncertainty. Of the many good algorithms for learning Bayesian networks from data, the bio-inspired search algorithm is one of the most effective. In this paper, we propose a hybrid mutual information-modified binary particle swarm optimization (MI-MBPSO) algorithm. This technique first constructs a network based on MI to improve the quality of the initial population, and then uses the decomposability of the scoring function to modify the BPSO algorithm. Experimental results show that, the proposed hybrid algorithm outperforms various other state-of-the-art structure learning algorithms.
Maiko SAKAMOTO Hiromi YAMAGUCHI Toshimasa YAMAZAKI Ken-ichi KAMIJO Takahiro YAMANOI
We have proposed a new Bayesian network model (BNM) framework for single-trial-EEG-based Brain-Computer Interface (BCI). The BNM was constructed in the following. In order to discriminate between left and right hands to be imaged from single-trial EEGs measured during the movement imagery tasks, the BNM has the following three steps: (1) independent component analysis (ICA) for each of the single-trial EEGs; (2) equivalent current dipole source localization (ECDL) for projections of each IC on the scalp surface; (3) BNM construction using the ECDL results. The BNMs were composed of nodes and edges which correspond to the brain sites where ECDs are located, and their connections, respectively. The connections were quantified as node activities by conditional probabilities calculated by probabilistic inference in each trial. The BNM-based BCI is compared with the common spatial pattern (CSP) method. For ten healthy subjects, there was no significant difference between the two methods. Our BNM might reflect each subject's strategy for task execution.
In social websites, users acquire information from adjacent neighbors as well as distant users by seeking along hyperlinks, and therefore, information diffusions, also seen as processes of “user infection”, show both cascading and jumping routes in social networks. Currently, existing analysis suffers from the difficulty in distinguishing between the impacts of information seeking behaviors, i.e. random walks, and other factors leading to user infections. To this end, we present a mechanism to recognize and measure influences of random walks on information diffusions. Firstly, we propose the concept of information propagation structure (IPS), which is also a directed acyclic graph, to represent frequent information diffusion routes in social networks. In IPS, we represent “jumping routes” as virtual arcs and regard them as the traces of random walks. Secondly, we design a frequent IPS mining algorithm (FIPS). By considering descendant node infections as a consequence of ancestor node infections in IPS, we can use a Bayesian network to model each IPS, and learn parameters based on the records of information diffusions passing through the IPS. Finally, we present a quantitative description method of random walks influence, the method is based on Bayesian probabilistic inferring in IPS, which is used to determine the ancestors, whose infection causes the infection of target users. We also employ betweenness centralities of arcs to evaluate contributions of random walks to certain infections. Experiments are carried out with real datasets and simulations. The results show random walks are influential in early and steady phases of information diffusions. They help diffusions pass through some topology limitations in social networks.
A method of calculating the top event probability of a fault tree, where dynamic gates and repeated events are included and the occurrences of basic events follow nonexponential distributions, is proposed. The method is on the basis of the Bayesian network formulation for a DFT proposed by Yuge and Yanagi [1]. The formulation had a difficulty in calculating a sequence probability if components have nonexponential failure distributions. We propose an alternative method to obtain the sequence probability in this paper. First, a method in the case of the Erlang distribution is discussed. Then, Tijms's fitting procedure is applied to deal with a general distribution. The procedure gives a mixture of two Erlang distributions as an approximate distribution for a general distribution given the mean and standard deviation. A numerical example shows that our method works well for complex systems.
A method of calculating the exact top event probability of a fault tree with dynamic gates and repeated basic events is proposed. The top event probability of such a dynamic fault tree is obtained by converting the tree into an equivalent Markov model. However, the Markov-based method is not realistic for a complex system model because the number of states that should be considered in the Markov analysis increases explosively as the number of basic events in the model increases. To overcome this shortcoming, we propose an alternative method in this paper. It is a hybrid of a Bayesian network (BN) and an algebraic technique. First, modularization is applied to a dynamic fault tree. The detected modules are classified into two types: one satisfies the parental Markov condition and the other does not. The module without the parental Markov condition is replaced with an equivalent single event. The occurrence probability of this event is obtained as the sum of disjoint sequence probabilities. After the contraction of modules without parent Markov condition, the BN algorithm is applied to the dynamic fault tree. The conditional probability tables for dynamic gates are presented. The BN is a standard one and has hierarchical and modular features. Numerical example shows that our method works well for complex systems.
Hocheol JEON Taehwan KIM Joongmin CHOI
This paper proposes a proactive management system for the events that occur across multiple personal user devices, including desktop PCs, laptops, and smart phones. We implemented the Personal Event Management Service using Dynamic Bayesian Networks (PEMS-DBN) system that proactively executes appropriate tasks across multiple devices without explicit user requests by recognizing the user's device reuse intention, based on the observed actions of the user for specific devices. The client module of PEMS-DBN installed on each device monitors the user actions and recognizes user intention by using dynamic Bayesian networks. The server provides data sharing and maintenance for the clients. A series of experiments were performed to evaluate user satisfaction and system accuracy, and also the amounts of resource consumption during intention recognition and proactive execution are measured to ensure the system efficiency. The experimental results showed that the PEMS-DBN system can proactively provide appropriate, personalized services with a high degree of satisfaction to the user in an effective and efficient manner.
Takamitsu HASHIMOTO Maomi UENO
Item response theory (IRT) is widely used for test analyses. Most models of IRT assume that a subject's responses to different items in a test are statistically independent. However, actual situations often violate this assumption. Thus, conditional independence (CI) tests among items given a latent ability variable are needed, but traditional CI tests suffer from biases. This study investigated a latent conditional independence (LCI) test given a latent variable. Results show that the LCI test can detect CI given a latent variable correctly, whereas traditional CI tests often fail to detect CI. Application of the LCI test to mathematics test data revealed that items that share common alternatives might be conditionally dependent.
Kenji TSUCHIE Yoshiko HANADA Seiji MIYOSHI
We propose an "estimation of distribution algorithm" incorporating switching. The algorithm enables switching from the standard estimation of distribution algorithm (EDA) to the genetic algorithm (GA), or vice versa, on the basis of switching criteria. The algorithm shows better performance than GA and EDA in deceptive problems.
Hirotoshi IWASAKI Nobuhiro MIZUNO Kousuke HARA Yoichi MOTOMURA
Mobile devices, such as cellular phones and car navigation systems, are essential to daily life. People acquire necessary information and preferred content over communication networks anywhere, anytime. However, usability issues arise from the simplicity of user interfaces themselves. Thus, a recommendation of content that is adapted to a user's preference and situation will help the user select content. In this paper, we describe a method to realize such a system using Bayesian networks. This user-adapted mobile system is based on a user model that provides recommendation of content (i.e., restaurants, shops, and music that are suitable to the user and situation) and that learns incrementally based on accumulated usage history data. However, sufficient samples are not always guaranteed, since a user model would require combined dependency among users, situations, and contents. Therefore, we propose the LK method for modeling, which complements incomplete and insufficient samples using knowledge data, and CPT incremental learning for adaptation based on a small number of samples. In order to evaluate the methods proposed, we applied them to restaurant recommendations made on car navigation systems. The evaluation results confirmed that our model based on the LK method can be expected to provide better generalization performance than that of the conventional method. Furthermore, our system would require much less operation than current car navigation systems from the beginning of use. Our evaluation results also indicate that learning a user's individual preference through CPT incremental learning would be beneficial to many users, even with only a few samples. As a result, we have developed the technology of a system that becomes more adapted to a user the more it is used.
Jaehun LEE Wooyong CHUNG Euntai KIM
A new structure learning approach for Bayesian networks (BNs) based on dual genetic algorithm (DGA) is proposed in this paper. An individual of the population is represented as a dual chromosome composed of two chromosomes. The first chromosome represents the ordering among the BN nodes and the second represents the conditional dependencies among the ordered BN nodes. It is rigorously shown that there is no BN structure that cannot be encoded by the proposed dual genetic encoding and the proposed encoding explores the entire solution space of the BN structures. In contrast with existing GA-based structure learning methods, the proposed method learns not only the topology of the BN nodes, but also the ordering among the BN nodes, thereby, exploring the wider solution space of a given problem than the existing method. The dual genetic operators are closed in the set of the admissible individuals. The proposed method is applied to real-world and benchmark applications, while its effectiveness is demonstrated through computer simulation.
This paper presents an inversion algorithm for dynamic Bayesian networks towards robust speech recognition, namely DBNI, which is a generalization of hidden Markov model inversion (HMMI). As a dual procedure of expectation maximization (EM)-based model reestimation, DBNI finds the 'uncontaminated' speech by moving the input noisy speech to the Gaussian means under the maximum likelihood (ML) sense given the DBN models trained on clean speech. This algorithm can provide both the expressive advantage from DBN and the noise-removal feature from model inversion. Experiments on the Aurora 2.0 database show that the hidden feature model (a typical DBN for speech recognition) with the DBNI algorithm achieves superior performance in terms of word error rate reduction.
Sungwon JUNG Kwang Hyung LEE Doheon LEE
We propose a recursive clustering and order restriction (R-CORE) method for learning large-scale Bayesian networks. The proposed method considers a reduced search space for directed acyclic graph (DAG) structures in scoring-based Bayesian network learning. The candidate DAG structures are restricted by clustering variables and determining the intercluster directionality. The proposed method considers cycles on only cmax(«n) variables rather than on all n variables for DAG structures. The R-CORE method could be a useful tool in very large problems where only a very small amount of training data is available.
Detecting edge directions and estimating the exact value of a missing line are currently active research areas in deinterlacing processing. This paper proposes a spatial domain fuzzy rule that is based on an interpolation algorithm, which is suitable to the region with high motion or scene change. The algorithm utilizes fuzzy theory to find the most accurate edge direction with which to interpolate missing pixels. The proposed fuzzy direction oriented interpolator operates by identifying small pixel variations in seven orientations (0°, 45°, -45°, 63°, -63°, 72°, and -72°), while using rules to infer the edge direction. The Bayesian network model selects the most suitable deinterlacing method among three deinterlacing methods and it successively builds approximations of the deinterlaced sequence, by evaluating three methods in each condition. Detection and interpolation results are presented. Experimental results show that the proposed algorithm provides a significant improvement over other existing deinterlacing methods. The proposed algorithm is not only for speed, but also effective for reducing deinterlacing artifacts.
Konstantin MARKOV Satoshi NAKAMURA
In recent years, the number of studies investigating new directions in speech modeling that goes beyond the conventional HMM has increased considerably. One promising approach is to use Bayesian Networks (BN) as speech models. Full recognition systems based on Dynamic BN as well as acoustic models using BN have been proposed lately. Our group at ATR has been developing a hybrid HMM/BN model, which is an HMM where the state probability distribution is modeled by a BN, instead of commonly used mixtures of Gaussian functions. In this paper, we describe how to use the hybrid HMM/BN acoustic models, especially emphasizing some design and implementation issues. The most essential part of HMM/BN model building is the choice of the state BN topology. As it is manually chosen, there are some factors that should be considered in this process. They include, but are not limited to, the type of data, the task and the available additional information. When context-dependent models are used, the state-level structure can be obtained by traditional methods. The HMM/BN parameter learning is based on the Viterbi training paradigm and consists of two alternating steps - BN training and HMM transition updates. For recognition, in some cases, BN inference is computationally equivalent to a mixture of Gaussians, which allows HMM/BN model to be used in existing decoders without any modification. We present two examples of HMM/BN model applications in speech recognition systems. Evaluations under various conditions and for different tasks showed that the HMM/BN model gives consistently better performance than the conventional HMM.
Since their inception almost fifty years ago, hidden Markov models (HMMs) have have become the predominant methodology for automatic speech recognition (ASR) systems--today, most state-of-the-art speech systems are HMM-based. There have been a number of ways to explain HMMs and to list their capabilities, each of these ways having both advantages and disadvantages. In an effort to better understand what HMMs can do, this tutorial article analyzes HMMs by exploring a definition of HMMs in terms of random variables and conditional independence assumptions. We prefer this definition as it allows us to reason more throughly about the capabilities of HMMs. In particular, it is possible to deduce that there are, in theory at least, no limitations to the class of probability distributions representable by HMMs. This paper concludes that, in search of a model to supersede the HMM (say for ASR), rather than trying to correct for HMM limitations in the general case, new models should be found based on their potential for better parsimony, computational requirements, and noise insensitivity.
Toru KUMAGAI Motoyuki AKAMATSU
This paper presents a method of predicting future human driving behavior under the condition that its resultant behavior and past observations are given. The proposed method makes use of a dynamic Bayesian network and the junction tree algorithm for probabilistic inference. The method is applied to behavior prediction for a vehicle assumed to stop at an intersection. Such a predictive system would facilitate warning and assistance to prevent dangerous activities, such as red-light violations, by allowing detection of a deviation from normal behavior.
Abdulrahman ALHARBY Hideki IMAI
Security protocols flaws represent a substantial portion of security exposures of data networks. In order to evaluate security protocols against any attack, formal methods are equipped with a number of techniques. Unfortunately, formal methods are applicable for static state only, and don't guarantee detecting all possible flaws. Therefore, formal methods should be complemented with dynamic protection. Anomaly detection systems are very suitable for security protocols environments as dynamic activities protectors. This paper presents an intrusion detection system that uses a number of different anomaly detection techniques to detect attacks against security protocols.
Elaheh HOMAYOUNVALA A. Hamid AGHVAMI
Access selection in future multiple radio access environments is considered in this paper from a new perspective, that of the consumer. A model is proposed for the automatic acquisition of user preferences to assist in access selection decision making. The proposed approach uses a two-level Bayesian C-Metanetwork that models individual user preferences in terms of affordable cost, acceptable level of quality of service and reputation of the access networks. User preferences under different contexts, such as leisure and business, are also considered. The model also adapts to the change of user preferences over time. A simulator has been developed to evaluate the proposed model and the simulation results are promising in terms of the proportion of correct preference predictions after a small number of training samples.
Hiroyuki SUZUKI Heiga ZEN Yoshihiko NANKAKU Chiyomi MIYAJIMA Keiichi TOKUDA Tadashi KITAMURA
This paper describes continuous speech recognition incorporating the additional complement information, e.g., voice characteristics, speaking styles, linguistic information and noise environment, into HMM-based acoustic modeling. In speech recognition systems, context-dependent HMMs, i.e., triphone, and the tree-based context clustering have commonly been used. Several attempts to utilize not only phonetic contexts, but additional complement information based on context (factor) dependent HMMs have been made in recent years. However, when the additional factors for testing data are unobserved, methods for obtaining factor labels is required before decoding. In this paper, we propose a model integration technique based on general factor dependent HMMs for decoding. The integrated HMMs can be used by a conventional decoder as standard triphone HMMs with Gaussian mixture densities. Moreover, by using the results of context clustering, the proposed method can determine an optimal number of mixture components for each state dependently of the degree of influence from additional factors. Phoneme recognition experiments using voice characteristic labels show significant improvements with a small number of model parameters, and a 19.3% error reduction was obtained in noise environment experiments.
Takahiro SHINOZAKI Sadaoki FURUI
One of the most important issues in spontaneous speech recognition is how to cope with the degradation of recognition accuracy due to speaking rate fluctuation within an utterance. This paper proposes an acoustic model for adjusting mixture weights and transition probabilities of the HMM for each frame according to the local speaking rate. The proposed model is implemented along with variants and conventional models using the Bayesian network framework. The proposed model has a hidden variable representing variation of the "mode" of the speaking rate, and its value controls the parameters of the underlying HMM. Model training and maximum probability assignment of the variables are conducted using the EM/GEM and inference algorithms for the Bayesian networks. Utterances from meetings and lectures are used for evaluation where the Bayesian network-based acoustic models are used to rescore the likelihood of the N-best lists. In the experiments, the proposed model indicated consistently higher performance than conventional HMMs and regression HMMs using the same speaking rate information.