An estimation of distribution algorithm with intelligent local search for rule-based nurse rostering

This paper proposes a new memetic evolutionary algorithm to achieve explicit learning in rule-based nurse rostering, which involves applying a set of heuristic rules for each nurse's assignment. The main framework of the algorithm is an estimation of distribution algorithm, in which an ant-miner methodology improves the individual solutions produced in each generation. Unlike our previous work (where learning is implicit), the learning in the memetic estimation of distribution algorithm is explicit, that is, we are able to identify building blocks directly. The overall approach learns by building a probabilistic model, that is, an estimation of the probability distribution of individual nurse–rule pairs that are used to construct schedules. The local search processor (ie the ant-miner) reinforces nurse–rule pairs that receive higher rewards. A challenging real-world nurse rostering problem is used as the test problem. Computational results show that the proposed approach outperforms most existing approaches. It is suggested that the learning methodologies suggested in this paper may be applied to other scheduling problems where schedules are built systematically according to specific rules.     

Bayesian networks with a logistic regression model for the conditional probabilities

Logistic regression techniques can be used to restrict the conditional probabilities of a Bayesian network for discrete variables. More specifically, each variable of the network can be modeled through a logistic regression model, in which the parents of the variable define the covariates. When all main effects and interactions between the parent variables are incorporated as covariates, the conditional probabilities are estimated without restrictions, as in a traditional Bayesian network. By incorporating interaction terms up to a specific order only, the number of parameters can be drastically reduced. Furthermore, ordered logistic regression can be used when the categories of a variable are ordered, resulting in even more parsimonious models. Parameters are estimated by a modified junction tree algorithm. The approach is illustrated with the Alarm network.     

Computational learning of the conditional phase-type (C-Ph) distribution

This paper presents a new algorithm for learning the structure of a special type of Bayesian network. The conditional phase-type (C-Ph) distribution is a Bayesian network that models the probabilistic causal relationships between a skewed continuous variable, modelled by the Coxian phase-type distribution, a special type of Markov model, and a set of interacting discrete variables. The algorithm takes a data set as input and produces the structure, parameters and graphical representations of the fit of the C-Ph distribution as output. The algorithm, which uses a greedy-search technique and has been implemented in MATLAB, is evaluated using a simulated data set consisting of 20,000 cases. The results show that the original C-Ph distribution is recaptured and the fit of the network to the data is discussed.     

Conditioning (updating) non-additive measures

Several update rules for non-additive probabilities, among them the Dempster-Shafer rule for belief functions and certain update rules in the spirit of Bayesian statistics with multiple prior probabilities, are reviewed, investigated and compared with each other. This is done within the unifying framework of general, non-additive measure and integration theory. The methods exposed here are capable of generalizing conditional expectation of random variables to the sub-modular or supermodular case at least if the given algebra is finite.     

Learning continuous time Bayesian network classifiers

Streaming data are relevant to finance, computer science, and engineering while they are becoming increasingly important to medicine and biology. Continuous time Bayesian network classifiers are designed for analyzing multivariate streaming data when time duration of event matters. Structural and parametric learning for the class of continuous time Bayesian network classifiers are considered in the case where complete data is available. Conditional log-likelihood scoring is developed for structural learning on continuous time Bayesian network classifiers. Performance of continuous time Bayesian network classifiers learned when combining conditional log-likelihood scoring and Bayesian parameter estimation are compared with that achieved by continuous time Bayesian network classifiers when learning is based on marginal log-likelihood scoring and to that achieved by dynamic Bayesian network classifiers. Classifiers are compared in terms of accuracy and computation time. Comparison is based on numerical experiments where synthetic and real data are used. Results show that conditional log-likelihood scoring combined with Bayesian parameter estimation outperforms marginal log-likelihood scoring. Conditional log-likelihood scoring becomes even more effective when the amount of available data is limited. Continuous time Bayesian network classifiers outperform in terms of computation time and accuracy dynamic Bayesian network on synthetic and real data sets.     

Propagation effects of model-calculated probability values in Bayesian networks

Probabilistic causal interaction models have become quite popular among Bayesian-network engineers as elicitation of all probabilities required often proves the main bottleneck in building a real-world network with domain experts. The best-known interaction models are the noisy-OR model and its generalisations. These models in essence are parameterised conditional probability tables for which just a limited number of parameter probabilities are required. The models assume specific properties of intercausal interaction and cannot be applied uncritically. Given their clear engineering advantages however, they are subject to ill-considered use. This paper demonstrates that such ill-considered use can result in poorly calibrated output probabilities from a Bayesian network. By studying, in an analytical way, the propagation effects of noisy-OR calculated probability values, we identify conditions under which use of the model can be harmful for a network's performance. These conditions demonstrate that use of the noisy-OR model for mere pragmatic reasons is sometimes warranted, even when the model's underlying assumptions are not met in reality.     

Independence for full conditional probabilities: Structure,factorization, non-uniqueness,and Bayesian networks

This paper examines concepts of independence for full conditional probabilities; that is, for set-functions that encode conditional probabilities as primary objects, and that allow conditioning on events of probability zero. Full conditional probabilities have been used in economics, in philosophy, in statistics, in artificial intelligence. This paper characterizes the structure of full conditional probabilities under various concepts of independence; limitations of existing concepts are examined with respect to the theory of Bayesian networks. The concept of layer independence (factorization across layers) is introduced; this seems to be the first concept of independence for full conditional probabilities that satisfies the graphoid properties of Symmetry, Redundancy, Decomposition, Weak Union, and Contraction. A theory of Bayesian networks is proposed where full conditional probabilities are encoded using infinitesimals, with a brief discussion of hyperreal full conditional probabilities.     

Consistency of a myopic Bayesian algorithm for one-dimensional global optimization

A sequential Bayesian method for finding the maximum of a function based on myopically minimizing the expected dispersion of conditional probabilities is described. It is shown by example that an algorithm that generates a dense set of observations need not converge to the correct answer for some priors on continuous functions on the unit interval. For the Brownian motion prior the myopic algorithm is consistent; for any continuous function, the conditional probabilities converge weakly to a point mass at the true maximum.     

利用贝叶斯网络分析基因表达数据

利用基因表达数据提出一种新的网络模型—贝叶斯网络,发现基因的互作.一个贝叶斯网络是多变量联合概率分布的有向图模型,表示变量间的条件独立属性.首先我们阐明贝叶斯网络如何表示基因间的互作,然后介绍从基因芯片数据学习贝叶斯网络的方法.     

On cautious probabilistic inference and default detachment

Conditional probabilities are one promising and widely used approach to model uncertainty in information systems. This paper discusses the DUCK-calculus, which is founded on the cautious approach to uncertain probabilistic inference. Based on a set of sound inference rules, derived probabilistic information is gained by local bounds propagation techniques. Precision being always a central point of criticism to such systems, we demonstrate that DUCK need not necessarily suffer from these problems. We can show that the popular Bayesian networks are subsumed by DUCK, implying that precise probabilities can be deduced by local propagation techniques, even in the multiply connected case. A comparative study with INFERNO and with inference techniques based on global operations-research techniques yields quite favorable results for our approach. Since conditional probabilities are also suited to model nonmonotonic situations by considering different contexts, we investigate the problems of maximal and relevant contexts, needed to draw default conclusions about individuals.     

Bayesian networks for discrete multivariate data: an algebraic approach to inference

In this paper we demonstrate how Gröbner bases and other algebraic techniques can be used to explore the geometry of the probability space of Bayesian networks with hidden variables. These techniques employ a parametrisation of Bayesian network by moments rather than conditional probabilities. We show that whilst Gröbner bases help to explain the local geometry of these spaces a complimentary analysis, modelling the positivity of probabilities, enhances and completes the geometrical picture. We report some recent geometrical results in this area and discuss a possible general methodology for the analyses of such problems.     

Modeling women's menstrual cycles using PICI gates in Bayesian network

A major difficulty in building Bayesian network (BN) models is the size of conditional probability tables, which grow exponentially in the number of parents. One way of dealing with this problem is through parametric conditional probability distributions that usually require only a number of parameters that is linear in the number of parents. In this paper, we introduce a new class of parametric models, the Probabilistic Independence of Causal Influences (PICI) models, that aim at lowering the number of parameters required to specify local probability distributions, but are still capable of efficiently modeling a variety of interactions. A subset of PICI models is decomposable and this leads to significantly faster inference as compared to models that cannot be decomposed. We present an application of the proposed method to learning dynamic BNs for modeling a woman's menstrual cycle. We show that PICI models are especially useful for parameter learning from small data sets and lead to higher parameter accuracy than when learning CPTs.     

Learning agents for the multi-mode project scheduling problem

Intelligent optimization refers to the promising technique of integrating learning mechanisms into (meta-)heuristic search. In this paper, we use multi-agent reinforcement learning for building high-quality solutions for the multi-mode resource-constrained project scheduling problem (MRCPSP). We use a network of distributed reinforcement learning agents that cooperate to jointly learn a well-performing constructive heuristic. Each agent, being responsible for one activity, uses two simple learning devices, called learning automata, that learn to select a successor activity order and a mode, respectively. By coupling the reward signals for both learning tasks, we can clearly show the advantage of using reinforcement learning in search. We present some comparative results, to show that our method can compete with the best performing algorithms for the MRCPSP, yet using only simple learning schemes without the burden of complex fine-tuning.     

Bayesian networks applied to credit scoring

Email: kchang{at}gmu.eduEmail: RobertFung{at}Fairlsaac.comEmail: alan.lucas{at}hotmail.com^¶Email: BobOliver{at}Fairlsaac.com^||Email: NShikaloff{at}Fairlsaac.com The objectives of this paper are to apply the theory and numericalalgorithms of Bayesian networks to risk scoring, and comparethe results with traditional methods for computing scores andposterior predictions of performance variables. Model identification,inference, and prediction of random variables using Bayesiannetworks have been successfully applied in a number of areas,including medical diagnosis, equipment failure, informationretrieval, rare-event prediction, and pattern recognition. Theability to graphically represent conditional dependencies andindependencies among random variables may also be useful incredit scoring. Although several papers have already appearedin the literature which use graphical models for model identification,as far as we know there have been no explicit experimental resultsthat compare a traditionally computed risk score with predictionsbased on Bayesian learning algorithms. In this paper, we examine a database of credit-card applicantsand attempt to ‘learn’ the graphical structure ofthe characteristics or variables that make up the database.We identify representative Bayesian networks in a developmentsample as well as the associated Markov blankets and cliquestructures within the Markov blanket. Once we obtain the structureof the underlying conditional independencies, we are able toestimate the probabilities of each node conditional on its directpredecessor node(s). We then calculate the posterior probabilitiesand scores of a performance variable for the development sample.Finally, we calculate the receiver operating characteristic(ROC) curves and relative profitability of scorecards basedon these identifications. The results of the different modelsand methods are compared with both development and validationsamples. Finally, we report on a statistical entropy calculationthat measures the degree to which cliques identified in theBayesian network are independent of one another.     

基于动态列生成算法的飞机排班问题研究

飞机排班是航空运输生产计划的重要环节,对航空公司的正常运营和整体效益有着决定性影响;飞机排班通常构建为大规模整数规划问题,是航空运筹学研究的重要课题,构建的模型属于严重退化的NP-Hard问题.在考虑对多种机型的飞机进行排班时,大大增加了问题的复杂性.针对航空公司实际情况,建立多种机型的飞机排班模型;为实现模型的有效求解,提出了基于约束编程的动态列生成算法;即用约束编程快速求解航班连线(航班串)并计算航班串简约成本,动态选择列集并与限制主问题进行迭代.最后,利用国内某航空公司干线航班网络实际数据验证模型和算法的有效性.     

An optimization-based approach for the design of Bayesian networks

Bayesian networks model conditional dependencies among the domain variables, and provide a way to deduce their interrelationships as well as a method for the classification of new instances. One of the most challenging problems in using Bayesian networks, in the absence of a domain expert who can dictate the model, is inducing the structure of the network from a large, multivariate data set. We propose a new methodology for the design of the structure of a Bayesian network based on concepts of graph theory and nonlinear integer optimization techniques.     

Learning Bayesian network classifiers by risk minimization

Bayesian networks (BNs) provide a powerful graphical model for encoding the probabilistic relationships among a set of variables, and hence can naturally be used for classification. However, Bayesian network classifiers (BNCs) learned in the common way using likelihood scores usually tend to achieve only mediocre classification accuracy because these scores are less specific to classification, but rather suit a general inference problem. We propose risk minimization by cross validation (RMCV) using the 0/1 loss function, which is a classification-oriented score for unrestricted BNCs. RMCV is an extension of classification-oriented scores commonly used in learning restricted BNCs and non-BN classifiers. Using small real and synthetic problems, allowing for learning all possible graphs, we empirically demonstrate RMCV superiority to marginal and class-conditional likelihood-based scores with respect to classification accuracy. Experiments using twenty-two real-world datasets show that BNCs learned using an RMCV-based algorithm significantly outperform the naive Bayesian classifier (NBC), tree augmented NBC (TAN), and other BNCs learned using marginal or conditional likelihood scores and are on par with non-BN state of the art classifiers, such as support vector machine, neural network, and classification tree. These experiments also show that an optimized version of RMCV is faster than all unrestricted BNCs and comparable with the neural network with respect to run-time. The main conclusion from our experiments is that unrestricted BNCs, when learned properly, can be a good alternative to restricted BNCs and traditional machine-learning classifiers with respect to both accuracy and efficiency.     

Bayesian Estimation of Discrete Multivariate Latent Structure Models With Structural Zeros

In multivariate categorical data, models based on conditional independence assumptions, such as latent class models, offer efficient estimation of complex dependencies. However, Bayesian versions of latent structure models for categorical data typically do not appropriately handle impossible combinations of variables, also known as structural zeros. Allowing nonzero probability for impossible combinations results in inaccurate estimates of joint and conditional probabilities, even for feasible combinations. We present an approach for estimating posterior distributions in Bayesian latent structure models with potentially many structural zeros. The basic idea is to treat the observed data as a truncated sample from an augmented dataset, thereby allowing us to exploit the conditional independence assumptions for computational expediency. As part of the approach, we develop an algorithm for collapsing a large set of structural zero combinations into a much smaller set of disjoint marginal conditions, which speeds up computation. We apply the approach to sample from a semiparametric version of the latent class model with structural zeros in the context of a key issue faced by national statistical agencies seeking to disseminate confidential data to the public: estimating the number of records in a sample that are unique in the population on a set of publicly available categorical variables. The latent class model offers remarkably accurate estimates of population uniqueness, even in the presence of a large number of structural zeros.     

G-PNN: A genetically engineered probabilistic neural network

The probabilistic neural network (PNN) is a neural network architecture that approximates the functionality of the Bayesian classifier, the optimal classifier. Designing the optimal Bayesian classifier is infeasible in practice, since the distributions of data belonging to each class are unknown. PNN is an approximation of the Bayesian classifier by approximating these distributions using the Parzen window approach. One of the criticisms of the PNN classifier is that, at times, it uses a lot of training data for its design. Furthermore, the PNN classifier requires that the user specifies certain network parameters, called the smoothing (spread) parameters, in order to approximate the distributions of the class data, which is not an easy task. A number of approaches have been reported in the literature for addressing both of these issues (i.e., reducing the number of training data needed for the building of the PNN model and producing good values for the smoothing parameters). In this effort, genetic algorithms are used to achieve both goals at once, and some promising results are reported.     

The optimal sequential information acquisition structure: A rational utility-maximizing perspective

We consider a rational utility maximizer decision maker (DM) who must gather two pieces of information from a set of multidimensional products before making a choice. We analyze the resulting sequential information acquisition process where the DM tries to find the best possible product subject to his information acquisition constraint. In addition, we introduce publicly observable signals that allow the DM to update his expected utility functions following a standard Bayesian learning rule. Even though it seems intuitively plausible to assume that the transmission of positive and credible information may lead DMs to accept any product signaled more eagerly, this paper illustrates how transmitting credible positive information is not sufficient to decrease the rejection probability faced by the information sender on its set of products. A significant difference in product rejection probabilities arises depending on the characteristic on which signals are issued, as will be illustrated numerically for both risk-neutral and risk-averse DMs.