Search

This paper presents a novel method on the optimization of bi-objective Flexible Job-shop Scheduling Problem (FJSP) under stochastic processing times. The robust counterpart model and the Non-dominated Sorting Genetic Algorithm II (NSGA-II) are used to solve the bi-objective FJSP with consideration of the completion time and the total energy consumption under stochastic processing times. The case study on GM Corporation verifies that the NSGA-II used in this paper is effective and has advantages to solve the proposed model comparing with HPSO and PSO+SA. The idea and method of the paper can be generalized widely in the manufacturing industry, because it can reduce the energy consumption of the energy-intensive manufacturing enterprise with less investment when the new approach is applied in existing systems. [ABSTRACT FROM AUTHOR]

In the Bayesian Reinforcement Learning (BRL) setting, agents try to maximise the collected rewards while interacting with their environment while using some prior knowledge that is accessed beforehand. Many BRL algorithms have already been proposed, but the benchmarks used to compare them are only relevant for specific cases. The paper addresses this problem, and provides a new BRL comparison methodology along with the corresponding open source library. In this methodology, a comparison criterion that measures the performance of algorithms on large sets of Markov Decision Processes (MDPs) drawn from some probability distributions is defined. In order to enable the comparison of non-anytime algorithms, our methodology also includes a detailed analysis of the computation time requirement of each algorithm. Our library is released with all source code and documentation: it includes three test problems, each of which has two different prior distributions, and seven state-of-the-art RL algorithms. Finally, our library is illustrated by comparing all the available algorithms and the results are discussed. [ABSTRACT FROM AUTHOR]

In this paper, we explore the (in)efficiency of the continuum Bitcoin-USD market in the period ranging from mid 2010 to early 2019. To deal with, we dynamically analyse the evolution of the self-similarity exponent of Bitcoin-USD daily returns via accurate FD4 approach by a 512 day sliding window with overlapping data. Further, we define the memory indicator by the difference between the self-similarity exponent of Bitcoin-USD series and the self-similarity index of its shuffled series. We also carry out additional analyses via FD4 approach by sliding windows of sizes equal to 64, 128, 256, and 1024 days, and also via FD algorithm for values of q equal to 1 and 2 (and sliding windows equal to 512 days). Moreover, we explored the evolution of the self-similarity exponent of actual S&P500 series via FD4 algorithm by sliding windows of sizes equal to 256 and 512 days. In all the cases, the obtained results were found to be similar to our first analysis. We conclude that the self-similarity exponent of the BTC-USD (resp., S&P500) series stands above 0.5. However, this is not due to the presence of significant memory in the series but to its underlying distribution. In fact, it holds that the self-similarity exponent of BTC-USD (resp., S&P500) series is similar or lower than the self-similarity index of a random series with the same distribution. As such, several periods with significant antipersistent memory in BTC-USD (resp., S&P500) series are distinguished. [ABSTRACT FROM AUTHOR]

In smart parking environments, how to choose suitable parking facilities with various attributes to satisfy certain criteria is an important decision issue. Based on the multiple attributes decision making (MADM) theory, this study proposed a smart parking guidance algorithm by considering three representative decision factors (i.e., walk duration, parking fee, and the number of vacant parking spaces) and various preferences of drivers. In this paper, the expected number of vacant parking spaces is regarded as an important attribute to reflect the difficulty degree of finding available parking spaces, and a queueing theory-based theoretical method was proposed to estimate this expected number for candidate parking facilities with different capacities, arrival rates, and service rates. The effectiveness of the MADM-based parking guidance algorithm was investigated and compared with a blind search-based approach in comprehensive scenarios with various distributions of parking facilities, traffic intensities, and user preferences. Experimental results show that the proposed MADM-based algorithm is effective to choose suitable parking resources to satisfy users’ preferences. Furthermore, it has also been observed that this newly proposed Markov Chain-based availability attribute is more effective to represent the availability of parking spaces than the arrival rate-based availability attribute proposed in existing research. [ABSTRACT FROM AUTHOR]

In this paper we introduce the transparent dead leaves (TDL) random field, a new germ-grain model in which the grains are combined according to a transparency principle. Informally, this model may be seen as the superposition of infinitely many semitransparent objects. It is therefore of interest in view of the modeling of natural images. Properties of this new model are established and a simulation algorithm is proposed. The main contribution of the paper is to establish a central limit theorem, showing that, when varying the transparency of the grain from opacity to total transparency, the TDL model ranges from the dead leaves model to a Gaussian random field. [ABSTRACT FROM AUTHOR]

The paper proposes a new message passing algorithm for cycle-free factor graphs. The proposed “entropy message passing” (EMP) algorithm may be viewed as sum-product message passing over the entropy semiring, which has previously appeared in automata theory. The primary use of EMP is to compute the entropy of a model. However, EMP can also be used to compute expressions that appear in expectation maximization and in gradient-descent algorithms. [ABSTRACT FROM AUTHOR]

This paper addresses object tracking in ultrasound images using a robust multiple model tracker. The proposed tracker has the following features: 1) it uses multiple dynamic models to track the evolution of the object boundary, and 2) it models invalid observations (outliers), reducing their influence on the shape estimates. The problem considered in this paper is the tracking of the left ventricle which is known to be a challenging problem. The heart motion presents two phases (diastole and systole) with different dynamics, the multiple models used in this tracker try to solve this difficulty. In addition, ultrasound images are corrupted by strong multiplicative noise which prevents the use of standard deformable models. Robust estimation techniques are used to address this difficulty. The multiple model data association (MMDA) tracker proposed in this paper is based on a bank of nonlinear filters, organized in a tree structure. The algorithm determines which model is active at each instant of time and updates its state by propagating the probability distribution, using robust estimation techniques. [ABSTRACT FROM AUTHOR]

In this paper, we study the application of the max-product algorithm (MPA) to the generalized multiple-fault diagnosis (GMFD) problem, which consists of components (to be diagnosed) and alarms/connections that can be unreliable. The MPA and the improved sequential MPA (SMPA) that we develop in this paper are local-message-passing algorithms that operate on the bipartite diagnosis graph (BDG) associated with the GMFD problem and converge to the maximum a posteriori probability (MAP) solution if this graph is acyclic (in addition, the MPA requires the MAP solution to be unique). Our simulations suggest that both the MPA and the SMPA perform well in more general systems that may exhibit cycles in the associated BDGs (the SMPA also appears to outperform the MPA in these more general systems). In this paper, we provide analytical results for acyclic BDGs and also assess the performance of both algorithms under particular patterns of alarm observations in general graphs; this allows us to obtain analytical bounds on the probability of making erroneous diagnosis with respect to the MAP solution. We also evaluate the performance of the MPA and the SMPA algorithms via simulations, and provide comparisons with previously developed heuristics for this type of diagnosis problems. We conclude that the MPA and the SMPA perform well under reasonable computational complexity when the underlying diagnosis graph is sparse. [ABSTRACT FROM AUTHOR]

Compound option valuation formulae give rise to the summation of a series of multinormal distribution functions. This paper presents an identity on sums of nested multinormal distributions of arbitrary dimension. We show that this identity generalizes some well-known low order identities for the multinormal distribution. We present three applications of the new identity to contingent claims valuation problems. The first and second applications show that by reducing significantly the number of integrals to be evaluated, faster and more accurate algorithms can be developed for implementing the Geske-Johnson American put valuation formula and the Roll-Geske-Whaley American call formula; the third gives new economic insights into the valuation of disaggregated coupon bonds. [ABSTRACT FROM AUTHOR]

Clustering large and complex data sets whose partitions may adopt arbitrary shapes remains a difficult challenge. Part of this challenge comes from the difficulty in defining a similarity measure between the data points that captures the underlying geometry of those data points. In this paper, we propose an algorithm, DCG++ that generates such a similarity measure that is data-driven and ultrametric. DCG++ uses Markov Chain Random Walks to capture the intrinsic geometry of data, scans possible scales, and combines all this information using a simple procedure that is shown to generate an ultrametric. We validate the effectiveness of this similarity measure within the context of clustering on synthetic data with complex geometry, on a real-world data set containing segmented audio records of frog calls described by mel-frequency cepstral coefficients, as well as on an image segmentation problem. The experimental results show a significant improvement on performance with the DCG-based ultrametric compared to using an empirical distance measure. [ABSTRACT FROM AUTHOR]

The article discusses geometric mean criterion and stochastic dominance decision making models. The author derives the mathematical relationship between the geometric mean and the integrals of the probability density functions used in stochastic dominance testing from a general class of distributions. However, both the models can be justified by the expected utility hypothesis. The geometric mean criterion follows as a result of the assumption that the decision-maker has a logarithmic utility function. The stochastic dominance models require the assumption of the signs of the first few derivatives of the decision-maker's utility function. The author notes that stochastic dominance showed great promise in its early development as a method for constructing a theory of security price forecasting because of its limited set of assumptions regarding investor preferences.

This paper is devoted to the perfect simulation of a stationary process with an at most countable state space. The process is specified through a kernel, prescribing the probability of the next state conditional to the whole past history. We follow the seminal work of Comets, Fernández and Ferrari (2002), who gave sufficient conditions for the construction of a perfect simulation algorithm. We define backward coalescence times for these kind of processes, which allow us to construct perfect simulation algorithms under weaker conditions than in Comets, Fermindez and Ferrari (2002). We discuss how to construct backward coalescence times (I) by means of information depths, taking into account some a priori knowledge about the histories that occur; and (ii) by identifying suitable coalescing events. [ABSTRACT FROM AUTHOR]

LDA (Latent Dirichlet Allocation) proposed by Blei is a generative probabilistic model of a corpus, where documents are represented as random mixtures over latent topics, and each topic is characterized by a distribution over words, but not the attributes of word positions of every document in the corpus. In this paper, a Word Position-Related LDA Model is proposed taking into account the attributes of word positions of every document in the corpus, where each word is characterized by a distribution over word positions. At the same time, the precision of the topic-word's interpretability is improved by integrating the distribution of the word-position and the appropriate word degree, taking into account the different word degree in the different word positions. Finally, a new method, a size-aware word intrusion method is proposed to improve the ability of the topic-word's interpretability. Experimental results on the NIPS corpus show that the Word Position-Related LDA Model can improve the precision of the topic-word's interpretability. And the average improvement of the precision in the topic-word's interpretability is about 9.67%. Also, the size-aware word intrusion method can interpret the topic-word's semantic information more comprehensively and more effectively through comparing the different experimental data. [ABSTRACT FROM AUTHOR]

We consider the problem of enriching the travelogue associated with a small number (even one) of images with more web images. Images associated with the travelogue always consist of the content and the style of textual information. Relying on this assumption, in this paper, we present a framework of travelogue enriching, exploiting both textual and visual information generated by different users. The framework aims to select the most relevant images from automatically collected candidate image set to enrich the given travelogue, and form a comprehensive overview of the scenic spot. To do these, we propose to build two-layer probabilistic models, i.e. a text-layer model and image-layer models, on offline collected travelogues and images. Each topic (e.g. Sea, Mountain, Historical Sites) in the text-layer model is followed by an image-layer model with sub-topics learnt (e.g. the topic of sea is with the sub-topic like beach, tree, sunrise and sunset). Based on the model, we develop strategies to enrich travelogues in the following steps: (1) remove noisy names of scenic spots from travelogues; (2) generate queries to automatically gather candidate image set; (3) select images to enrich the travelogue; and (4) choose images to portray the visual content of a scenic spot. Experimental results on Chinese travelogues demonstrate the potential of the proposed approach on tasks of travelogue enrichment and the corresponding scenic spot illustration. [ABSTRACT FROM AUTHOR]

Based on the operation of a state machine, this paper elucidates a comprehensive frame for probability-based primary-input-dominated X-filling methods to minimize the total weighted switching activity (WSA) during the scan capture operation. Experimental results demonstrate that the proposed approach significantly reduces both average and peak WSAs. [ABSTRACT FROM AUTHOR]

Stochastic hybrid system (SHS) models can be used to analyze and design complex embedded systems that operate in the presence of uncertainty and variability. Verification of reachability properties for such systems is a critical problem. Developing sound computational methods for verification is challenging because of the interaction between the discrete and the continuous stochastic dynamics. In this paper, we propose a probabilistic method for verification of SHSs based on discrete approximations focusing on reachability and safety problems. We show that reachability and safety can be characterized as a viscosity solution of a system of coupled Hamilton-Jacobi-Bellman equations. We present a numerical algorithm for computing the solution based on discrete approximations that are derived using finite-difference methods. An advantage of the method is that the solution converges to the one for the original system as the discretization becomes finer. We also prove that the algorithm is polynomial in the number of states of the discrete approximation. Finally, we illustrate the approach with two benchmarks: a navigation and a room heater example, which have been proposed for hybrid system verification. [ABSTRACT FROM AUTHOR]

A novel procedure for estimating the relative importance of uncertain parameters of complex FE model is presented. The method is specifically directed toward problems involving high-dimensional input parameter spaces, as they are encountered during uncertainty analysis of large scale, refined FE models. In these cases one is commonly faced with thousands of uncertain parameters and traditional techniques, e.g. finite difference or direct differentiation methods become expensive. In contrast, the presented method quickly filters out the most influential variables. Hence, the main objective is not to compute the sensitivity but to identify those parameters whose random variations have the biggest influence on the response. This is achieved by generating a set of samples with direct Monte Carlo simulation, which are closely scattered around the point at which the relative importance measures are sought. From these samples, estimators of the relative importance are synthesized and the most important ones are refined with a method of choice. In this paper, the underlying theory as well as the resulting algorithm is presented. [ABSTRACT FROM AUTHOR]

We consider online versions of the traveling salesman problem (TSP) and traveling repairman problem (TRP) where instances are not known in advance. Cities (points) to be visited are revealed over time, while the server is en route serving previously released requests. These problems are known in the literature as the online TSP (TRP, respectively). The corresponding offline problems are the TSP (TRP) with release dates, problems where each point has to be visited at or after a given release date. In the current literature, the assumption is that a request becomes known at the time of its release date. In this paper we introduce the notion of a request's disclosure date, the time when a city's location and release date are revealed to the server. In a variety of disclosure date scenarios and metric spaces, we give new online algorithms and quantify the value of this advanced information in the form of improved competitive ratios. We also provide a general result on polynomial-time online algorithms for the online TSP. [ABSTRACT FROM AUTHOR]

Expert judgment is frequently used to assess parameter values of quantitative management science models, particularly in decision-making contexts. Experts can, however, only be expected to assess observable quantities, not abstract model parameters. This means that we need a method for translating expert assessed uncertainties on model outputs into uncertainties on model parameter values. This process is called probabilistic inversion. The probability distribution on model parameters obtained in this way can be used in a variety of ways, but in particular in an uncertainty analysis or as a Bayes prior. This paper discusses computational algorithms that have proven successful in various projects and gives examples from environmental modelling and banking. Those algorithms are given a theoretical basis by adopting a minimum information approach to modelling partial information. The role of minimum information is two-fold: It enables us to resolve the problem of nonuniqueness of distributions given the information we have, and it provides numerical stability to the algorithm by guaranteeing convergence properties. [ABSTRACT FROM AUTHOR]

This paper considers three crucial issues in processing scaled down image, the representation of partial image, similarity measure and domain adaptation. Two Gaussian mixture model based algorithms are proposed to effectively preserve image details and avoids image degradation. Multiple partial images are clustered separately through Gaussian mixture model clustering with a scan and select procedure to enhance the inclusion of small image details. The local image features, represented by maximum likelihood estimates of the mixture components, are classified by using the modified Bayes factor (MBF) as a similarity measure. The detection of novel local features from MBF will suggest domain adaptation, which is changing the number of components of the Gaussian mixture model. The performance of the proposed algorithms are evaluated with simulated data and real images and it is shown to perform much better than existing Gaussian mixture model based algorithms in reproducing images with higher structural similarity index. [ABSTRACT FROM AUTHOR]

The deployment of large number of femtocell base stations allows us to extend the coverage and efficiently utilize resources in a low cost manner. However, the small cell size of femtocell networks can result in frequent handovers to the mobile user, and consequently throughput degradation. Thus, in this paper, we propose predictive association control schemes to improve the system’s effective throughput. Our design focuses on reducing handover frequency without impacting on throughput. The proposed schemes determine handover decisions that contribute most to the network throughput and are proper for distributed implementations. The simulation results show significant gains compared with existing methods in terms of handover frequency and network throughput perspective. [ABSTRACT FROM AUTHOR]

Background: Bivariate random-effects models represent a widely accepted and recommended approach for meta-analysis of test accuracy studies. Standard likelihood methods routinely used for inference are prone to several drawbacks. Small sample size can give rise to unreliable inferential conclusions and convergence issues make the approach unappealing. This paper suggests a different methodology to address such difficulties.Methods: A SIMEX methodology is proposed. The method is a simulation-based technique originally developed as a correction strategy within the measurement error literature. It suits the meta-analysis framework as the diagnostic accuracy measures provided by each study are prone to measurement error. SIMEX can be straightforwardly adapted to cover different measurement error structures and to deal with covariates. The effortless implementation with standard software is an interesting feature of the method.Results: Extensive simulation studies highlight the improvement provided by SIMEX over likelihood approach in terms of empirical coverage probabilities of confidence intervals under different scenarios, independently of the sample size and the values of the correlation between sensitivity and specificity. A remarkable amelioration is obtained in case of deviations from the normality assumption for the random-effects distribution. From a computational point of view, the application of SIMEX is shown to be neither involved nor subject to the convergence issues affecting likelihood-based alternatives. Application of the method to a diagnostic review of the performance of transesophageal echocardiography for assessing ascending aorta atherosclerosis enables overcoming limitations of the likelihood procedure.Conclusions: The SIMEX methodology represents an interesting alternative to likelihood-based procedures for inference in meta-analysis of diagnostic accuracy studies. The approach can provide more accurate inferential conclusions, while avoiding convergence failure and numerical instabilities. The application of the method in the R programming language is possible through the code which is made available and illustrated using the real data example. [ABSTRACT FROM AUTHOR]

The objective of this research is to examine the trends in the exchange rate markets of the ASEAN-5 countries (Indonesia (IDR), Malaysia (MYR), the Philippines (PHP), Singapore (SGD), and Thailand (THB)) through the application of dynamic moving average trading systems. This research offers evidence of the usefulness of the time-varying volatility technical analysis indicator, Adjustable Moving Average (AMA′) in deciphering trends in these ASEAN-5 exchange rate markets. This time-varying volatility factor, referred to as the Efficacy Ratio in this paper, is embedded in AMA′. The Efficacy Ratio adjusts the AMA′ to the prevailing market conditions by avoiding whipsaws (losses due, in part, to acting on wrong trading signals, which generally occur when there is no general direction in the market) in range trading and by entering early into new trends in trend trading. The efficacy of AMA′ is assessed against other popular moving-average rules. Based on the January 2005 to December 2014 dataset, our findings show that the moving averages and AMA′ are superior to the passive buy-and-hold strategy. Specifically, AMA′ outperforms the other models for the United States Dollar against PHP (USD/PHP) and USD/THB currency pairs. The results show that different length moving averages perform better in different periods for the five currencies. This is consistent with our hypothesis that a dynamic adjustable technical indicator is needed to cater for different periods in different markets. [ABSTRACT FROM AUTHOR]

A large-scale multiple surveillance system for infectious disease outbreaks has been in operation in England and Wales since the early 1990s. Changes to the statistical algorithm at the heart of the system were proposed and the purpose of this paper is to compare two new algorithms with the original algorithm. Test data to evaluate performance are created from weekly counts of the number of cases of each of more than 2000 diseases over a twenty-year period. The time series of each disease is separated into one series giving the baseline (background) disease incidence and a second series giving disease outbreaks. One series is shifted forward by twelve months and the two are then recombined, giving a realistic series in which it is known where outbreaks have been added. The metrics used to evaluate performance include a scoring rule that appropriately balances sensitivity against specificity and is sensitive to variation in probabilities near 1. In the context of disease surveillance, a scoring rule can be adapted to reflect the size of outbreaks and this was done. Results indicate that the two new algorithms are comparable to each other and better than the algorithm they were designed to replace. [ABSTRACT FROM AUTHOR]

Background: As a part of a larger Health Technology Assessment (HTA), the measurement error of a device used to monitor the hemoglobin concentration of a patient undergoing surgery, as well as its decision consequences, were to be estimated from published data.Methods: A Bayesian hierarchical model of measurement error, allowing the meta-analytic estimation of both central and dispersion parameters (under the assumption of normality of measurement errors) is proposed and applied to published data; the resulting potential decision errors are deduced from this estimation. The same method is used to assess the impact of an initial calibration.Results: The posterior distributions are summarized as mean ± sd (credible interval). The fitted model exhibits a modest mean expected error (0.24 ± 0.73 (-1.23 1.59) g/dL) and a large variability (mean absolute expected error 1.18 ± 0.92 (0.05 3.36) g/dL). The initial calibration modifies the bias (-0.20 ± 0.87 (-1.99 1.49) g/dL), but the variability remains almost as large (mean absolute expected error 1.05 ± 0.87 (0.04 3.21) g/dL). This entails a potential decision error ("false positive" or "false negative") for about one patient out of seven.Conclusions: The proposed hierarchical model allows the estimation of the variability from published aggregates, and allows the modeling of the consequences of this variability in terms of decision errors. For the device under assessment, these potential decision errors are clinically problematic. [ABSTRACT FROM AUTHOR]

The Artificial Bee Colony (ABC) algorithm is a recently introduced swarm intelligence algorithm that has been successfully applied on numerous and diverse optimization problems. However, one major problem with ABC is its premature convergence to local optima, which often originates from its insufficient degree of explorative search capability. This paper introduces ABC with Improved Explorations (ABC-IX), a novel algorithm that modifies both the selection and perturbation operations of the basic ABC algorithm in an explorative way. First, an explorative selection scheme based on simulated annealing allows ABC-IX to probabilistically accept both better and worse candidate solutions, whereas the basic ABC can accept better solutions only. Second, a self-adaptive strategy enables ABC-IX to automatically adapt the perturbation rate, separately for each candidate solution, to customize the degree of explorations and exploitations around it. ABC-IX is evaluated on several benchmark numerical optimization problems and results are compared with a number of state-of-the-art evolutionary and swarm intelligence algorithms. Results show that ABC-IX often performs better optimization than most other algorithms in comparison on most of the problems. [ABSTRACT FROM AUTHOR]

Channel estimation error results in severe performance deterioration in wireless networks. In this paper, we study the impact of imperfect channel estimation (ICE) on the outage performance of bidirectional relaying where the two sources have asymmetric traffic requirements (ATRs). In particular, we focus on the amplify-and-forward (AF) relay-assisted multiple-access broadcast (MABC) protocol, i.e., MABC-AF, which has received much attention due to its high spectrum efficiency and low complexity. In the single-relay scenario, we derive exact and generalized closed-form expressions for system outage probability, which indicate that the system outage is determined by the unidirectional outage in the case of highly asymmetric traffic patterns. For more insights into our approach, the closed-form asymptotic expressions are also evaluated, manifesting the interesting error floor (EF) phenomenon due to ICE. Using these analytical results, we further develop a robust and practical optimum power-allocation (OPA) algorithm that minimizes the system outage probability under aggregate and individual node power constraints. In the multirelay scenario, by taking into account the traffic knowledge, a novel relay selection criterion is proposed for asymmetric MABC-AF, followed by its impact on the system outage probability in the presence of ICE. Numerical results validate the accuracy of our analytical results and highlight the effect of the proposed OPA algorithm under various traffic requirements and channel estimation errors. Furthermore, the results also show that the proposed relay selection criterion is superior to the classical max–min criterion with ATRs, and the performance improvement becomes remarkable as channel estimation error increases. [ABSTRACT FROM PUBLISHER]

The structural reliability analysis in the presence of mixed uncertain variables demands more computation as the entire configuration fuzzy variables needs to be explored. Moreover the existence of multiple design points deviate the accuracy of results as the optimization algorithms may converge to a local design point by neglecting the main contribution from the global design point. Therefore, in this paper a novel uncertainty analysis method for estimating the membership function of failure probability of structural systems involving multiple design points in the presence of mixed uncertain variables is presented. The proposed method involves Multicut-High Dimensional Model Representation technique for the limit state function approximation, transformation technique to obtain the contribution of the fuzzy variables to the convolution integral and fast Fourier transform for solving the convolution integral. In the proposed method, efforts are required in evaluating conditional responses at a selected input determined by sample points, as compared to full scale simulation methods. Therefore, the proposed technique estimates the failure probability accurately with significantly less computational effort compared to the direct Monte Carlo simulation. The methodology developed is applicable for structural reliability analysis involving any number of fuzzy and random variables. The accuracy and efficiency of the proposed method is demonstrated through three examples. [ABSTRACT FROM AUTHOR]

In recent years, mixture models have found widespread usage in discovering latent cluster structure from data. A popular special case of finite mixture models is the family of naive Bayes (NB) models, where the probability of a feature vector factorizes over the features for any given component of the mixture. Despite their popularity, naive Bayes models do not allow data points to belong to different component clusters with varying degrees, i.e., mixed memberships, which puts a restriction on their modeling ability. In this paper, we propose mixed-membership naive Bayes (MMNB) models. On one hand, MMNB can be viewed as a generalization of NB by putting a Dirichlet prior on top to allow mixed memberships. On the other hand, MMNB can also be viewed as a generalization of latent Dirichlet allocation (LDA) with the ability to handle heterogeneous feature vectors with different types of features, e.g., real, categorical, etc.. We propose two variational inference algorithms to learn MMNB models. The first one is based on ideas originally used in LDA, and the second one uses substantially fewer variational parameters, leading to a significantly faster algorithm. Further, we extend MMNB/LDA to discriminative mixed-membership models for classification by suitably combining MMNB/LDA with multi-class logistic regression. The efficacy of the proposed mixed-membership models is demonstrated by extensive experiments on several datasets, including UCI benchmarks, recommendation systems, and text datasets. [ABSTRACT FROM AUTHOR]

We consider a statistical model for the problem of finding subgraphs with specified topology in an otherwise random graph. This task plays an important role in the analysis of social and biological networks. In these types of networks, small subgraphs with a specific structure have important functional roles, and they are referred to as motifs. Within this model, one or multiple copies of a subgraph is added (planted) in an Erdős–Renyi random graph with $n$ vertices and edge probability $q_{0}$. We ask whether the resulting graph can be distinguished reliably from a pure Erdős–Renyi random graph, and we present two types of result. First we investigate the question from a purely statistical perspective, and ask whether there isanytest that can distinguish between the two graph models. We provide necessary and sufficient conditions that are essentially tight for small enough subgraphs. Next we study two polynomial-time algorithms for solving the same problem: a spectral algorithm and a semidefinite programming (SDP) relaxation. For the spectral algorithm, we establish sufficient conditions under which it distinguishes the two graph models with high probability. Under the same conditions the spectral algorithm indeed identifies the hidden subgraph. The spectral algorithm is substantially sub-optimal with respect to the optimal test. We show that a similar gap is present for the more sophisticated SDP approach. [ABSTRACT FROM AUTHOR]

In view of the fact that the current online virtual network embedding algorithms do not consider the fragment resources generated in the embedding process deeply enough, resulting in the problem that the acceptance ratio and the revenue to cost ratio are both low, a mathematical model for virtual network reconfiguration is constructed and a heuristic algorithm for fragment-aware virtual network reconfiguration (FA-VNR) is proposed. The FA-VNR algorithm selects the set of virtual nodes to be migrated according to the fragment degrees of the physical nodes, and selects the best virtual node migration scheme according to the reduction of the fragment degrees of the physical nodes as well as the reduction of the embedding cost of the embedded virtual networks. Extensive simulation results show that the proposed FA-VNR algorithm not only can obviously improve the acceptance ratio and the revenue to cost ratio of the current online virtual network embedding algorithm, but also has better optimization effect than the existing virtual network reconfiguration algorithm. [ABSTRACT FROM AUTHOR]

Inference problems in graphical models can be represented as a constrained optimization of a free-energy function. In this paper, we treat both forms of probabilistic inference, estimating marginal probabilities of the joint distribution and finding the most probable assignment, through a unified message-passing algorithm architecture. In particular we generalize the belief propagation (BP) algorithms of sum-product and max-product and tree-reweighted (TRW) sum and max product algorithms (TRBP) and introduce a new set of convergent algorithms based on “convex-free-energy” and linear-programming (LP) relaxation as a zero-temperature of a convex-free-energy. The main idea of this work arises from taking a general perspective on the existing BP and TRBP algorithms while observing that they all are reductions from the basic optimization formula of f+\sumihi where the function f is an extended-valued, strictly convex but nonsmooth and the functions hi are extended-valued functions (not necessarily convex). We use tools from convex duality to present the “primal-dual ascent” algorithm which is an extension of the Bregman successive projection scheme and is designed to handle optimization of the general type f+\sumihi. We then map the fractional-free-energy variational principle for approximate inference onto the optimization formula above and introduce the “norm-product” message-passing algorithm. Special cases of the norm-product include sum-product and max-product (BP algorithms), TRBP and NMPLP algorithms. When the fractional-free-energy is set to be convex (convex-free-energy) the norm-product is globally convergent for the estimation of marginal probabilities and for approximating the LP-relaxation. We also introduce another branch of the norm-product which arises as the “zero-temperature” of the convex-free-energy which we refer to as the “convex-max-product”. The convex-max-product is convergent (unlike max-product) and aims at solving the LP- relaxation. [ABSTRACT FROM PUBLISHER]

Model reference adaptive search (MRAS) for solving global optimization problems works with a parameterized probabilistic model on the solution space and generates at each iteration a group of candidate solutions. These candidate solutions are then used to update the parameters associated with the probabilistic model in such a way that the future search will be biased toward the region containing high-quality solutions. The parameter updating procedure in MRAS is guided by a sequence of implicit probabilistic models we call reference models. We provide a particular algorithm instantiation of the MRAS method, where the sequence of reference models can be viewed as the generalized probability distribution models for estimation of distribution algorithms (EDAs) with proportional selection scheme. In addition, we show that the model reference framework can also be used to describe the recently proposed cross-entropy (CE) method for optimization and to study its properties. Hence, this paper can also be seen as a study on the effectiveness of combining CE and EDAs. We prove global convergence of the proposed algorithm in both continuous and combinatorial domains, and we carry out numerical studies to illustrate the performance of the algorithm. [ABSTRACT FROM AUTHOR]

The Neyman-Pearson (NP) approach to hypothesis testing is useful in situations where different types of error have different consequences or a priori probabilities are unknown. For any α > 0, the NP lemma specifies the most powerful test of size a, but assumes the distributions for each hypothesis are known or (in some cases) the likelihood ratio is monotonic in an unknown parameter. This paper investigates an extension of NP theory to situations in which one has no knowledge of the underlying distributions except for a collection of independent and identically distributed (i.i.d.) training examples from each hypothesis. Building on a "fundamental lemma" of Cannon et al., we demonstrate that several concepts from statistical learning theory have counterparts in the NP context. Specifically, we consider constrained versions of empirical risk minimization (NP-ERM) and structural risk minimization (NP-SRM), and prove performance guarantees for both. General conditions are given under which NP-SRM leads to strong universal consistency. We also apply NP-SRM to (dyadic) decision trees to derive rates of convergence. Finally, we present explicit algorithms to implement NP-SRM for histograms and dyadic decision trees. [ABSTRACT FROM AUTHOR]

Noise models are crucial for designing image restoration algorithms, generating synthetic training data, and predicting algorithm performance. There are two related but distinct estimation scenarios. The first is model calibration, where it is assumed that the input ideal bitmap and the output of the degradation process are both known. The second is the general estimation problem, where only the image from the output of the degradation process is given. While researchers have addressed the problem of calibration of models, issues with the general estimation problems have not been addressed in the literature. In this paper, we describe a parameter estimation algorithm for a morphological, binary, page-level image degradation model. The inputs to the estimation algorithm are 1) the degraded image and 2) information regarding the font type (italic, bold, serif, sans serif). We simulate degraded images using our model and search for the optimal parameter by looking for a parameter value for which the local neighborhood pattern distributions in the simulated image and the given degraded image are most similar. The parameter space is searched using a direct search optimization algorithm. We use the p-value of the Kolmogorov-Smirnov test as the measure of similarity between the two neighborhood pattern distributions. We show results of our algorithm on degraded document images. [ABSTRACT FROM AUTHOR]

The aim of this paper is to present a new heuristic method for the Traveling Salesman Problem with Time Windows, based on the solution of an auxiliary problem. The idea is to solve an assignment problem with an ad hoc objective function to obtain a solution close enough to a feasible solution of the original problem. Given this solution, made by a long main tour containing the depot and few small subtours, it is easy to insert all the subtours into the main path using a greedy insertion procedure. The algorithm described applies the proposed constructive scheme and then uses a local search procedure to improve the initial solution. The computational results show the effectiveness of this approach. [ABSTRACT FROM AUTHOR]

The paper presents a heuristic for determining the path that maximizes the expected utility of a stochastic acyclic network. The focus is on shortest route problems where a general, nonlinear utility function is used to measure outcomes. For such problems, enumerating all feasible paths is the only way to guarantee that the global optimum has been found. Alternatively, we develop a reduction algorithm based on stochastic dominance to speed up the computations. Monte Carlo simulation is used to evaluate the approach. In all, 70 test problems comprising 20 to 60 nodes are randomly generated and analyzed. The results indicate that the heuristic produces significant computational saving as the size of the network grows, and that the quality of the reduced network solutions are better than those obtained from the original formulation. [ABSTRACT FROM AUTHOR]

The Linear Programming Problem is by far the most widely used optimization model. Its impact on economic and government modeling is immense. The Simplex Method for solving the Linear Programming (LP) Problem, due to George Dantzig, has been an extremely efficient computational tool for almost four decades. The method has been the subject of intense investigations for many years, but some major aspects of its behavior are not fully understood yet. The purpose of this paper is to survey the body of knowledge on the efficiency of the Simplex Method, from both practical and theoretical points of view. Adopting the number of iterations (pivot steps) as the yardstick for efficiency, we survey four aspects of the issue: 1. Reports on practical experience of the method's performance on real-life LP problems. 2. Results on controlled (Monte-Carlo) experiments solving LP problems which were randomly generated according to some predetermined distributions. 3. Complexity results, including theoretical analyses on both upper and lower bounds for the performance of the Simplex as well as non-Simplex algorithms for LP. 4. Results of recent theoretical studies using probabilistic analysis to derive bounds on the average behavior of the Simplex Method. We discuss the consequences and limitations of the various studies. Special emphasis is given to open questions. [ABSTRACT FROM AUTHOR]

In the literature of modern psychometric modeling, mostly related to item response theory (IRT), the fit of model is evaluated through known indices, such as χ2, M2, and root mean square error of approximation (RMSEA) for absolute assessments as well as Akaike information criterion (AIC), consistent AIC (CAIC), and Bayesian information criterion (BIC) for relative comparisons. Recent developments show a merging trend of psychometric and machine learnings, yet there remains a gap in the model fit evaluation, specifically the use of the area under curve (AUC). This study focuses on the behaviors of AUC in fitting IRT models. Rounds of simulations were conducted to investigate AUC's appropriateness (e.g., power and Type I error rate) under various conditions. The results show that AUC possessed certain advantages under certain conditions such as high-dimensional structure with two-parameter logistic (2PL) and some three-parameter logistic (3PL) models, while disadvantages were also obvious when the true model is unidimensional. It cautions researchers about the dangers of using AUC solely in evaluating psychometric models. [ABSTRACT FROM AUTHOR]

Most existing algorithms used for constructing virtual backbones are based on the ideal deterministic network model (DNM) in which any pair of nodes is either fully connected or completely disconnected. Different from DNM, the probabilistic network model (PNM), which presumes that there is a probability to connect and communicate between any pair of nodes, is more suitable to the practice in many real applications. In this paper, we propose a new algorithm to construct reliable virtual backbone in probabilistic wireless sensor networks. In the algorithm, we firstly introduce Effective Degree of Delivery Probability (EDDP) to indicate the reliable degree of nodes to transfer data successfully, and then exclude those nodes with zero EDDP from the candidate dominator set to construct a reliable connected dominating set (CDS). Moreover, each dominatee selects the neighbor dominator with the maximum delivery probability to transfer data. Through simulations, we demonstrate that our proposed algorithm can remarkably prolong the network lifetime compared with existing typical algorithms. [ABSTRACT FROM AUTHOR]

In this paper, exact and approximate approaches for studying queuing models with state-dependent jump priorities are developed. Both models with finite separate buffers and finite common buffer for heterogeneous calls are investigated. It is shown that both models might be described by twodimensional Markov Chains (2-D MC). Exact approach based on solution of appropriate system of balance equations (SBE) for state probabilities faced with big computational challenges for large scale models. To overcome the indicated difficulties an approximate approach based on the state space merging algorithms is developed. This approach allows to construct simple algorithms to calculate the Quality of Service (QoS) metrics of the examined models. The results of numerical experiments are demonstrated. [ABSTRACT FROM AUTHOR]

In project management context, time management is one of the most important factors affecting project success. This paper proposes a new method to solve research project scheduling problems (RPSP) containing Fuzzy Graphical Evaluation and Review Technique (FGERT) networks. Through the deliverables of this method, a proper estimation of project completion time (PCT) and success probability can be achieved. So algorithms were developed to cover all features of the problem based on three main parameters “duration, occurrence probability, and success probability.” These developed algorithms were known as PR-FGERT (Parallel and Reversible-Fuzzy GERT networks). The main provided framework includes simplifying the network of project and taking regular steps to determine PCT and success probability. Simplifications include (1) equivalent making of parallel and series branches in fuzzy network considering the concepts of probabilistic nodes, (2) equivalent making of delay or reversible-to-itself branches and impact of changing the parameters of time and probability based on removing related branches, (3) equivalent making of simple and complex loops, and (4) an algorithm that was provided to resolve no-loop fuzzy network, after equivalent making. Finally, the performance of models was compared with existing methods. The results showed proper and real performance of models in comparison with existing methods. [ABSTRACT FROM AUTHOR]

Differential evolution (DE) is simple and effective in solving numerous real-world global optimization problems. However, its effectiveness critically depends on the appropriate setting of population size and strategy parameters. Therefore, to obtain optimal performance the time-consuming preliminary tuning of parameters is needed. Recently, different strategy parameter adaptation techniques, which can automatically update the parameters to appropriate values to suit the characteristics of optimization problems, have been proposed. However, most of the works do not control the adaptation of the population size. In addition, they try to adapt each strategy parameters individually but do not take into account the interaction between the parameters that are being adapted. In this paper, we introduce a DE algorithm where both strategy parameters are self-adapted taking into account the parameter dependencies by means of a multivariate probabilistic technique based on Gaussian Adaptation working on the parameter space. In addition, the proposed DE algorithm starts by sampling a huge number of sample solutions in the search space and in each generation a constant number of individuals from huge sample set are adaptively selected to form the population that evolves. The proposed algorithm is evaluated on 14 benchmark problems of CEC 2005 with different dimensionality. [ABSTRACT FROM AUTHOR]

Due to the strong nonlinearity and transition dynamics between different operating points of the high purity distillation column process, it is difficult to use a single model for modeling such a process. Therefore, the multiple model based approach is introduced for modeling the high purity distillation column plant under the framework of the expectation maximization (EM) algorithm. In this paper, autoregressive exogenous (ARX) models are adopted to construct the local models of this chemical process at different operating points, and the EM algorithm is used for identification of local models as well as the probability that each local model takes effect. The global model is obtained by aggregating the local models using an exponential weighting function. Finally, the simulation performed on the high purity distillation column demonstrates the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

Cost-sensitive support vector machine is one of the most popular tools to deal with class-imbalanced problem such as fault diagnosis. However, such data appear with a huge number of examples as well as features. Aiming at class-imbalanced problem on big data, a cost-sensitive support vector machine using randomized dual coordinate descent method (CSVM-RDCD) is proposed in this paper. The solution of concerned subproblem at each iteration is derived in closed form and the computational cost is decreased through the accelerating strategy and cheap computation. The four constrained conditions of CSVM-RDCD are derived. Experimental results illustrate that the proposed method increases recognition rates of positive class and reduces average misclassification costs on real big class-imbalanced data. [ABSTRACT FROM AUTHOR]

The aim of the present paper is to develop a new generalized form of the fractional kinetic equation involving a generalized k-Mittag-Leffler function Ek,ζ,ηγ,ρ(⋅). The solutions of fractional kinetic equations are discussed in terms of the Mittag-Leffler function. Further, numerical values of the results and their graphical interpretation is interpreted to study the behavior of these solutions. The results established here are quite general in nature and capable of yielding both known and new results. [ABSTRACT FROM AUTHOR]

This paper provides an analytical derivation of the probability density function of signal-to-interference-plus-noise ratio in the scenario where mobile stations interfere with each other. This analysis considers cochannel interference and adjacent channel interference. This could also remove the need for Monte Carlo simulations when evaluating the interference effect between mobile stations. Numerical verification shows that the analytical result agrees well with a Monte Carlo simulation. Also, we applied analytical methods for evaluating the interference effect between mobile stations using adjacent frequency bands. The analytical derivation of the probability density function can be used to provide the technical criteria for sharing a frequency band. [ABSTRACT FROM AUTHOR]

Consideration was given to the closed queuing network with batch jockeying customers. This network extends the Gordon-Newell model to the case of batch customer servicing. The serviced batch discharges a node without changing its size and arrives to another node with a probability depending on its size. Some constraints must be imposed on the servicing process. The form of the stationary distribution was established, and an efficient algorithm to determine it was proposed. [ABSTRACT FROM AUTHOR]

In this work, we consider a complex flowshop scheduling problem in which both no-wait and separate setup times are considered. The optimisation criterion is the minimisation of the total completion time. We propose an effective dominance rule for the four machine case that can also be used for m machines. Five simple and fast heuristics are proposed along with two easy to code stochastic local search methods, one of them being based on Iterated Local Search (ILS). An extensive computational evaluation is carried out with two sets of 5,400 instances. All seven methods are compared to two recent algorithms. The results, confirmed by thorough statistical analyses, show that the proposed methods are more effective and efficient when compared to the best existing algorithms in the literature for the considered problem. [ABSTRACT FROM AUTHOR]

In this paper we derive bounds on the conductance and hence on the spectral gap of a Metropolis algorithm with a monotone, log-concave target density on an interval of R. We show that the minimal conductance set has measure ½ and we use this characterization to bound the conductance in terms of the conductance of the algorithm restricted to a smaller domain. Whereas previous work on conductance has resulted in good bounds for Markov chains on bounded domains, this is the first conductance bound applicable to unbounded domains. We then show how this result can be combined with the state-decomposition theorem of Madras and Randall (2002) to bound the spectral gap of Metropolis algorithms with target distributions with monotone, log-concave tails on R. [ABSTRACT FROM AUTHOR]