Decomposing Bayesian networks: triangulation of the moral graph with genetic algorithms

In this paper we consider the optimal decomposition of Bayesian networks. More concretely, we examine empirically the applicability of genetic algorithms to the problem of the triangulation of moral graphs. This problem constitutes the only difficult step in the evidence propagation algorithm of Lauritzen and Spiegelhalter (1988) and is known to be NP-hard (Wen, 1991). We carry out experiments with distinct crossover and mutation operators and with different population sizes, mutation rates and selection biasses. The results are analysed statistically. They turn out to improve the results obtained with most other known triangulation methods (Kjærulff, 1990) and are comparable to results obtained with simulated annealing (Kjærulff, 1990; Kjærulff, 1992).     

Reliability evaluation subject to assured accuracy rate and time for stochastic unreliable-node computer networks

In many real-life networks such as computer networks, branches and nodes have multi-state capacity, lead time, and accuracy rate. The network with unreliable nodes is more complex to evaluate the reliability because node failure results in the disabled of adjacent branches. Such a network is named a stochastic unreliable-node computer network (SUNCN). Under the strict assumption that each component (branch and node) has a deterministic capacity, the quickest path (QP) problem is to find a path sending a specific amount of data with minimum transmission time. The accuracy rate is a critical index to measure the performance of a computer network because some packets are damaged or lost due to voltage instability, magnetic field effects, lightning, etc. Subject to both assured accuracy rate and time constraints, this paper extends the QP problem to discuss the system reliability of an SUNCN. An efficient algorithm based on a graphic technique is proposed to find the minimal capacity vector meeting such constraints. System reliability, the probability to send a specific amount of data through multiple minimal paths subject to both assured accuracy rate and time constraints, can subsequently be computed.     

VisIOT:经济产业结构关联可视分析

随着经济统计范畴的精细化以及统计过程的规范化，能够表现产业部门关联关系的投入产出表（Input-Output Table，IOT）数据日益呈现复杂的结构特性。传统的统计分析软件和方法形式单一且传达信息有限，面对结构关系复杂且动态演化的IOT数据，难以有效分析和探索其中复杂的关联模式和时序变化特征。为此，本文设计面对IOT数据分析的经济产业结构关联特征可视化工具——VisIOT。首先设计双向力导向图描述国民经济结构关联网络，并对网络中的顶点和边进行属性映射；然后构建时序矩阵图，直观地展示IOT数据差异，并按照时间顺序依次嵌入时序IOT数据；其次利用部门间的经济技术联系优化模块度算法，发掘经济产业结构关联网络中隐含的社区特征，有效支持关联紧密的社区结构的交互式分析和提取；再次设计社区时序演变图展示社区结构特征的时序演化规律，借助交叉优化算法和前后向的扫描算法，优化部门排列顺序，减少部门交叉，帮助用户有效捕捉社区结构的稳定性；最后有效设计交互方案关联可视化界面，实现经济产业结构关联可视分析系统。本文利用真实的IOT数据进行实例分析与验证，结果表明本文设计的VisIOT系统能够帮助用户快速识别和感知IOT数据中隐含的关联特征及其时序变化规律。     

Community detection with structural and attribute similarities

An important problem in network analysis is to identify significant communities. Most of the real-world data sets exhibit a certain topological structure between nodes and the attributes describing them. In this paper, we propose a new community detection criterion considering both structural similarities and attribute similarities. The clustering method integrates the cost of clustering node attributes with the cost of clustering the structural information via the normalized modularity. We show that the joint clustering problem can be formulated as a spectral relaxation problem. The proposed algorithm is capable of learning the degree of contributions of individual node attributes. A number of numerical studies involving simulated and real data sets demonstrate the effectiveness of the proposed method.     

Asymptotic Throughput in Discrete‐Time Cyclic Networks with Queue‐Length‐Dependent Service Rates

Abstract

For a discrete‐time closed cyclic network of single server queues whose service rates are non‐decreasing in the queue length, we compute the queue‐length distribution at each node in terms of throughputs of related networks. For the asymptotic analysis, we consider sequences of networks where the number of nodes grows to infinity, service rates are taken only from a fixed finite set of non‐decreasing sequences, the ratio of customers to nodes has a limit, and the proportion of nodes for each possible service‐rate sequence has a limit. Under these assumptions, the asymptotic throughput exists and is calculated explicitly. Furthermore, the asymptotic queue‐length distribution at any node can be obtained in terms of the asymptotic throughput. The asymptotic throughput, regarded as a function of the limiting customer‐to‐node ratio, is strictly increasing for ratios up to a threshold value (possibly infinite) and is constant thereafter. For ratios less than the threshold, the asymptotic queue‐length distribution at each node has finite moments of all orders. However, at or above the threshold, bottlenecks (nodes with asymptotically‐infinite mean queue length) do occur, and we completely characterize such nodes.     

Analysing organic food buyers' perceptions with Bayesian networks: a case study in Turkey

Bayesian network (BN) is an efficient graphical method that uses directed acyclic graphs (DAG) to provide information about a set of data. BNs consist of nodes and arcs (or edges) where nodes represent variables and arcs represent relations and influences between nodes. Interest in organic food has been increasing in the world during the last decade. The same trend is also valid in Turkey. Although there are numerous studies that deal with customer perception of organic food and customer characteristics, none of them used BNs. Thus, this study, which shows a new application area of BNs, aims to reveal the perception and characteristics of organic food buyers. In this work, a survey is designed and applied in seven different organic bazaars in Turkey. Afterwards, BNs are constructed with the data gathered from 611 organic food consumers. The findings match with the previous studies as factors such as health, environmental factors, food availability, product price, consumers' income and trust to organization are found to influence consumers effectively.     

An iterative algorithm for optimal variable weighting in K-means clustering

The K-means clustering method is a widely adopted clustering algorithm in data mining and pattern recognition, where the partitions are made by minimizing the total within group sum of squares based on a given set of variables. Weighted K-means clustering is an extension of the K-means method by assigning nonnegative weights to the set of variables. In this paper, we aim to obtain more meaningful and interpretable clusters by deriving the optimal variable weights for weighted K-means clustering. Specifically, we improve the weighted k-means clustering method by introducing a new algorithm to obtain the globally optimal variable weights based on the Karush-Kuhn-Tucker conditions. We present the mathematical formulation for the clustering problem, derive the structural properties of the optimal weights, and implement an recursive algorithm to calculate the optimal weights. Numerical examples on simulated and real data indicate that our method is superior in both clustering accuracy and computational efficiency.     

Influence diagnostics and outlier tests for semiparametric mixed models

Summary. Semiparametric mixed models are useful in biometric and econometric applications, especially for longitudinal data. Maximum penalized likelihood estimators (MPLEs) have been shown to work well by Zhang and co-workers for both linear coefficients and nonparametric functions. This paper considers the role of influence diagnostics in the MPLE by extending the case deletion and subject deletion analysis of linear models to accommodate the inclusion of a nonparametric component. We focus on influence measures for the fixed effects and provide formulae that are analogous to those for simpler models and readily computable with the MPLE algorithm. We also establish an equivalence between the case or subject deletion model and a mean shift outlier model from which we derive tests for outliers. The influence diagnostics proposed are illustrated through a longitudinal hormone study on progesterone and a simulated example.     

Asymptotically Optimal Design Points for Rejection Algorithms

ABSTRACT

Very fast automatic rejection algorithms were developed recently which allow us to generate random variates from large classes of unimodal distributions. They require the choice of several design points which decompose the domain of the distribution into small sub-intervals. The optimal choice of these points is an important but unsolved problem. Therefore, we present an approach that allows us to characterize optimal design points in the asymptotic case (when their number tends to infinity) under mild regularity conditions. We describe a short algorithm to calculate these asymptotically optimal points in practice. Numerical experiments indicate that they are very close to optimal even when only six or seven design points are calculated.     

Optimal control strategies for dividend payments and capital injections in compound Markov binomial risk model with penalties for deficits

We consider the compound Markov binomial risk model. The company controls the amount of dividends paid to the shareholders as well as the capital injections in order to maximize the cumulative expected discounted dividends minus the discounted capital injections and the discounted penalties for deficits prior to ruin. We show that the optimal value function is the unique solution of an HJB equation, and the optimal control strategy is a two-barriers strategy given the current state of the Markov chain. We obtain some properties of the optimal strategy and the optimal condition for ruining the company. We offer a high-efficiency algorithm for obtaining the optimal strategy and the optimal value function. In addition, we also discuss the optimal control problem under a restriction of bounded dividend rates. Numerical results are provided to illustrate the algorithm and the impact of the penalties.     

Modeling veterans’ health benefit grants using the expectation maximization algorithm

A novel application of the expectation maximization (EM) algorithm is proposed for modeling right-censored multiple regression. Parameter estimates, variability assessment, and model selection are summarized in a multiple regression settings assuming a normal model. The performance of this method is assessed through a simulation study. New formulas for measuring model utility and diagnostics are derived based on the EM algorithm. They include reconstructed coefficient of determination and influence diagnostics based on a one-step deletion method. A real data set, provided by North Dakota Department of Veterans Affairs, is modeled using the proposed methodology. Empirical findings should be of benefit to government policy-makers.     

An evolutionary algorithm for A-optimal incomplete block designs

Evolutionary algorithms are heuristic stochastic search and optimization techniques with principles taken from natural genetics. They are procedures mimicking the evolution process of an initial population through genetic transformations. This paper is concerned with the problem of finding A-optimal incomplete block designs for multiple treatment comparisons represented by a matrix of contrasts. An evolutionary algorithm for searching optimal, or nearly optimal, incomplete block designs is described in detail. Various examples regarding the application of the algorithm to some well-known problems illustrate the good performance of the algorithm     

Simulation-Based Inspection Policies for a One-Shot System in Storage Over a Finite Time Span

In this paper, we consider an inspection policy problem for a one-shot system with two types of units over a finite time span and want to determine inspection intervals optimally with given replacement points of Type 2 units. The interval availability and life cycle cost are used as optimization criteria and estimated by simulation. Two optimization models are proposed to find the optimal inspection intervals for the exponential and general distributions. A heuristic method and a genetic algorithm are proposed to find the near-optimal inspection intervals, to satisfy the target interval availability and minimize the life-cycle cost. We study numerical examples to compare the heuristic method with the genetic algorithm and investigate the effect of model parameters to the optimal solutions.     

Optimal designs for non-competitive enzyme inhibition kinetic models

In this paper, we present a new method for determining optimal designs for enzyme inhibition kinetic models, which are used to model the influence of the concentration of a substrate and an inhibition on the velocity of a reaction. The approach uses a nonlinear transformation of the vector of predictors such that the model in the new coordinates is given by an incomplete response surface model. Although there exist no explicit solutions of the optimal design problem for incomplete response surface models so far, the corresponding design problem in the new coordinates is substantially more transparent, such that explicit or numerical solutions can be determined more easily. The designs for the original problem can finally be found by an inverse transformation of the optimal designs determined for the response surface model. We illustrate the method determining explicit solutions for the D-optimal design and for the optimal design problem for estimating the individual coefficients in a non-competitive enzyme inhibition kinetic model.     

Missing covariates in generalized linear models when the missing data mechanism is non-ignorable

We propose a method for estimating parameters in generalized linear models with missing covariates and a non-ignorable missing data mechanism. We use a multinomial model for the missing data indicators and propose a joint distribution for them which can be written as a sequence of one-dimensional conditional distributions, with each one-dimensional conditional distribution consisting of a logistic regression. We allow the covariates to be either categorical or continuous. The joint covariate distribution is also modelled via a sequence of one-dimensional conditional distributions, and the response variable is assumed to be completely observed. We derive the E- and M-steps of the EM algorithm with non-ignorable missing covariate data. For categorical covariates, we derive a closed form expression for the E- and M-steps of the EM algorithm for obtaining the maximum likelihood estimates (MLEs). For continuous covariates, we use a Monte Carlo version of the EM algorithm to obtain the MLEs via the Gibbs sampler. Computational techniques for Gibbs sampling are proposed and implemented. The parametric form of the assumed missing data mechanism itself is not `testable' from the data, and thus the non-ignorable modelling considered here can be viewed as a sensitivity analysis concerning a more complicated model. Therefore, although a model may have `passed' the tests for a certain missing data mechanism, this does not mean that we have captured, even approximately, the correct missing data mechanism. Hence, model checking for the missing data mechanism and sensitivity analyses play an important role in this problem and are discussed in detail. Several simulations are given to demonstrate the methodology. In addition, a real data set from a melanoma cancer clinical trial is presented to illustrate the methods proposed.     

Comparison of a genetic algorithm and simulated annealing in an application to statistical image reconstruction

Genetic algorithms (GAs) are adaptive search techniques designed to find near-optimal solutions of large scale optimization problems with multiple local maxima. Standard versions of the GA are defined for objective functions which depend on a vector of binary variables. The problem of finding the maximum a posteriori (MAP) estimate of a binary image in Bayesian image analysis appears to be well suited to a GA as images have a natural binary representation and the posterior image probability is a multi-modal objective function. We use the numerical optimization problem posed in MAP image estimation as a test-bed on which to compare GAs with simulated annealing (SA), another all-purpose global optimization method. Our conclusions are that the GAs we have applied perform poorly, even after adaptation to this problem. This is somewhat unexpected, given the widespread claims of GAs' effectiveness, but it is in keeping with work by Jennison and Sheehan (1995) which suggests that GAs are not adept at handling problems involving a great many variables of roughly equal influence.We reach more positive conclusions concerning the use of the GA's crossover operation in recombining near-optimal solutions obtained by other methods. We propose a hybrid algorithm in which crossover is used to combine subsections of image reconstructions obtained using SA and we show that this algorithm is more effective and efficient than SA or a GA individually.     

Multiple deletion measures and conditional influence in regression model

The joint effect of the deletion of the ith and jih cases is given by Gray and Ling (1984), they discussed the influence measures for influential subsets in linear regression analysis. The present paper is concerned with multiple sets of deletion measures in the linear regression model. In particular we are interested in the effects of the jointly and conditional influence analysis for the detection of two influential subsets.     

Applying designed experiments to optimize the performance of genetic algorithms used for scheduling complex products in the capital goods industry

Conventional optimization approaches, such as Linear Programming, Dynamic Programming and Branch-and-Bound methods are well established for solving relatively simple scheduling problems. Algorithms such as Simulated Annealing, Taboo Search and Genetic Algorithms (GA) have recently been applied to large combinatorial problems. Owing to the complex nature of these problems it is often impossible to search the whole problem space and an optimal solution cannot, therefore, be guaranteed. A BiCriteria Genetic Algorithm (BCGA) has been developed for the scheduling of complex products with multiple resource constraints and deep product structure. This GA identifies and corrects infeasible schedules and takes account of the early supply of components and assemblies, late delivery of final products and capacity utilization. The research has used manufacturing data obtained from a capital goods company. Genetic Algorithms include a number of parameters, including the probabilities of crossover and mutation, the population size and the number of generations. The BCGA scheduling tool provides 16 alternative crossover operations and eight different mutation mechanisms. The overall objective of this study was to develop an efficient design-of-experiments approach to identify genetic algorithm operators and parameters that produce solutions with minimum total cost. The case studies were based upon a complex, computationally intensive scheduling problem that was insoluble using conventional approaches. This paper describes an efficient sequential experimental strategy that enabled this work to be performed within a reasonable time. The first stage was a screening experiment, which had a fractional factorial embedded within a half Latin-square design. The second stage was a half-fraction design with a reduced number of GA operators. The results are compared with previous studies. It is demonstrated that, in this case, improved GA performance was achieved using the experimental strategy proposed. The appropriate genetic operators and parameters may be case specific, leading to the view that experimental design may be the best way to proceed when finding the 'best' combination of GA operators and parameters.     

Robust estimators for additive models using backfitting

Additive models provide an attractive setup to estimate regression functions in a nonparametric context. They provide a flexible and interpretable model, where each regression function depends only on a single explanatory variable and can be estimated at an optimal univariate rate. Most estimation procedures for these models are highly sensitive to the presence of even a small proportion of outliers in the data. In this paper, we show that a relatively simple robust version of the backfitting algorithm (consisting of using robust local polynomial smoothers) corresponds to the solution of a well-defined optimisation problem. This formulation allows us to find mild conditions to show Fisher consistency and to study the convergence of the algorithm. Our numerical experiments show that the resulting estimators have good robustness and efficiency properties. We illustrate the use of these estimators on a real data set where the robust fit reveals the presence of influential outliers.