网页排序中的随机模型及算法

随着互联网规模的日益增长, 搜索引擎已经成为互联网上有效的信息获取工具. 而在众多搜索引擎的背后, 是信息检索技术, 也即网页排序算法在起作用. 网页排序包括重要性排序和相关性排序. 通过我们研究发现, 尽管这两类排序所依据的准则不同, 但是都可以通过建立适当的随机过程模型来研究. 对于网页重要性排序, 我们通过分析用户浏览网页的行为建立了Markov 骨架过程的框架. 基于该框架我们分析了三种不同的随机过程模型对用户行为模拟的合理程度, 并设计了名为BrowseRank 的一组新算法, 该算法可以根据用户上网行为来计算网页的重要性. 在网页相关性排序中, 我们主要针对排序结果联合问题建立了一个基于Markov 链的监督学习框架. 通过将传统方法的监督化, 使原来难于解决的问题变的易于学习, 将原来的NP- 难问题转化为一个半正定规划问题, 提高了效率.     

A web-based methodology for product design evaluation and optimisation

The authors have developed a methodology that takes advantages of the World Wide Web to analyse and develop optimal new product designs. This paper describes the methodology and illustrates its application to a case study involving the design of an actual Web site where music CDs are sold. The proposed methodology has the following features: (a) it is based on a design inspired by conjoint analysis; (b) it involves unobtrusive electronic measurement of the actual behavior of Web users who remain undisturbed by experimental factors; and (c) it utilises an integer programming approach to seek optimal Web site configurations. The methodology uses limited dependent variable methods to develop response models that provide the basis for the development of objective functions for an optimisation model. The optimisation model can consider either single or multiple objective functions by using a Pareto optimum approach.     

Two classes of time-inhomogeneous Markov chains: Analysis of the periodic case

We consider the M/G/1 and GI/M/1 types of Markov chains for which their one step transitions depend on the times of the transitions. These types of Markov chains are encountered in several stochastic models, including queueing systems, dams, inventory systems, insurance risk models, etc. We show that for the cases when the time parameters are periodic the systems can be analyzed using some extensions of known results in the matrix-analytic methods literature. We have limited our examples to those relating to queueing systems to allow us a focus. An example application of the model to a real life problem is presented.     

Stability analysis of N-model systems under a static priority rule

We consider the stability of N-model systems that consist of two customer classes and two server pools. Servers in one of the pools can serve both classes, but those in the other pool can serve only one of the classes. The standard fluid models in general are not sufficient to establish the stability region of these systems under static priority policies. Therefore, we use a novel and a general approach to augment the fluid model equations based on induced Markov chains. Using this new approach, we establish the stability region of these systems under a static priority rule with thresholds when the service and interarrival times have phase-type distributions. We show that, in certain cases, the stability region depends on the distributions of the service and interarrival times (beyond their mean), on the number of servers in the system, and on the threshold value. We also show that it is possible to expand the stability region in these systems by increasing the variability of the service times (without changing their mean) while keeping the other parameters fixed. The extension of our results to parallel server systems and general service time distributions is also discussed.     

A general performance analysis method for uniform memory architectures

The performance of a multiprocessor system greatly depends on the bandwidth of its memory architecture. In this paper, uniform memory architectures with various interconnection networks including crossbar, multiple-buses and generalized shuffle networks are studied. We propose a general method based on the Markov chain model by assuming that the blocked memory requests will be redistributed to the memory modules in the next memory cycle. This assumption results in an analysis with lower complexity where the number of states is linearly proportional to the number of processors. Moreover, it can provide excellent estimation on the system power and memory bandwidth for all three types of interconnection networks as compared with the simulation results in which the blocked memory requests are resubmitted to the same memory module. Comparisons also show that our method is more general and precise than most existing analysis methods. The method is further extended to estimate the performance of multiprocessor system with caches. The approximation results are also shown to be remarkably good.     

Bayesian Methods for Wavelet Series in Single-Index Models

Single-index models have found applications in econometrics and biometrics, where multidimensional regression models are often encountered. This article proposes a nonparametric estimation approach that combines wavelet methods for nonequispaced designs with Bayesian models. We consider a wavelet series expansion of the unknown regression function and set prior distributions for the wavelet coefficients and the other model parameters. To ensure model identifiability, the direction parameter is represented via its polar coordinates. We employ ad hoc hierarchical mixture priors that perform shrinkage on wavelet coefficients and use Markov chain Monte Carlo methods for a posteriori inference. We investigate an independence-type Metropolis-Hastings algorithm to produce samples for the direction parameter. Our method leads to simultaneous estimates of the link function and of the index parameters. We present results on both simulated and real data, where we look at comparisons with other methods.     

Semiparametric Bayesian optimal replacement policies: application to railroad tracks

We present a Bayesian decision theoretic approach for developing replacement strategies. In so doing, we consider a semiparametric model to describe the failure characteristics of systems by specifying a nonparametric form for cumulative intensity function and by taking into account effect of covariates by a parametric form. Use of a gamma process prior for the cumulative intensity function complicates the Bayesian analysis when the updating is based on failure count data. We develop a Bayesian analysis of the model using Markov chain Monte Carlo methods and determine replacement strategies. Adoption of Markov chain Monte Carlo methods involves a data augmentation algorithm. We show the implementation of our approach using actual data from railroad tracks. Copyright © 2016 John Wiley & Sons, Ltd.     

A Markov modulated Poisson model for software reliability

In this paper, we consider a latent Markov process governing the intensity rate of a Poisson process model for software failures. The latent process enables us to infer performance of the debugging operations over time and allows us to deal with the imperfect debugging scenario. We develop the Bayesian inference for the model and also introduce a method to infer the unknown dimension of the Markov process. We illustrate the implementation of our model and the Bayesian approach by using actual software failure data.     

Some limit theorems for regenerative queues

We consider a single server queue with the interarrival times and the service times forming a regenerative sequence. This traffic class includes the standard models: iid, periodic, Markov modulated (e.g., BMAP model of Lucantoni [18]) and their superpositions. This class also includes the recently proposed traffic models in high speed networks, exhibiting long range dependence. Under minimal conditions we obtain the rates of convergence to stationary distributions, finiteness of stationary moments, various functional limit theorems and the continuity of stationary distributions and moments. We use the continuity results to obtain approximations for stationary distributions and moments of an MMPP/GI/1 queue where the modulating chain has a countable state space. We extend all our results to feed-forward networks where the external arrivals to each queue can be regenerative. In the end we show that the output process of a leaky bucket is regenerative if the input process is and hence our results extend to a queue with arrivals controlled by a leaky bucket. This revised version was published online in June 2006 with corrections to the Cover Date.     

A comparison of some criteria for states selection in the latent Markov model for longitudinal data

We compare different selection criteria to choose the number of latent states of a multivariate latent Markov model for longitudinal data. This model is based on an underlying Markov chain to represent the evolution of a latent characteristic of a group of individuals over time. Then, the response variables observed at different occasions are assumed to be conditionally independent given this chain. Maximum likelihood estimation of the model is carried out through an Expectation–Maximization algorithm based on forward–backward recursions which are well known in the hidden Markov literature for time series. The selection criteria we consider are based on penalized versions of the maximum log-likelihood or on the posterior probabilities of belonging to each latent state, that is, the conditional probability of the latent state given the observed data. Among the latter criteria, we propose an appropriate entropy measure tailored for the latent Markov models. We show the results of a Monte Carlo simulation study aimed at comparing the performance of the above states selection criteria on the basis of a wide set of model specifications.     

Assessing Convergence and Mixing of MCMC Implementations via Stratification

Some posterior distributions lead to Markov chain Monte Carlo (MCMC) chains that are naturally viewed as collections of subchains. Examples include mixture models, regime-switching models, and hidden Markov models. We obtain MCMC-based estimators of posterior expectations by combining different subgroup (subchain) estimators using stratification and poststratification methods. Variance estimates of the limiting distributions of such estimators are developed. Based on these variance estimates, we propose a test statistic to aid in the assessment of convergence and mixing of chains. We compare our diagnostic with other commonly used methods. The approach is illustrated in two examples: a latent variable model for arsenic concentration in public water systems in Arizona and a Bayesian hierarchical model for Pacific sea surface temperatures. Supplementary materials, which include MATLAB codes for the proposed method, are available online.     

Filter‐based portfolio strategies in an HMM setting with varying correlation parametrizations

We consider portfolio optimization in a regime‐switching market. The assets of the portfolio are modeled through a hidden Markov model (HMM) in discrete time, where drift and volatility of the single assets are allowed to switch between different states. We consider different parametrizations of the involved asset covariances: statewise uncorrelated assets (though linked through the common Markov chain), assets correlated in a state‐independent way, and assets where the correlation varies from state to state. As a benchmark, we also consider a model without regime switches. We utilize a filter‐based expectation‐maximization (EM) algorithm to obtain optimal parameter estimates within this multivariate HMM and present parameter estimators in all three HMM settings. We discuss the impact of these different models on the performance of several portfolio strategies. Our findings show that for simulated returns, our strategies in many settings outperform naïve investment strategies, like the equal weights strategy. Information criteria can be used to detect the best model for estimation as well as for portfolio optimization. A second study using real data confirms these findings.     

A MILP approach to the optimization of banner display strategy to tackle banner blindness

The paper addresses the issue of online advertising efficiency in the context of the “banner blindness” phenomenon. We extend the traditional exposure metric of banner efficiency by allowing the effect of a banner display (exposure effect, EE) to vary depending on the sequence of pages that lead to the display. Within a user session on the given website, we assume that EE differs for a banner carried over from the previous page (low EE), from the case where the banner suddenly appears in a previously unoccupied place (high EE). This assumption implies that a banner’s efficiency can be increased by optimising its placement throughout the website’s structure; to this end, we develop a simple model framework. First, we formalize the efficiency metric based on expected total EE for a representative user, using a Markov chain model estimable from the website’s clickstream data. Next, we formulate the selection of efficient banner placement as a mixed integer linear programming problem. We consider two scenarios: (i) a static one, where banner placement is fixed throughout the day, and (ii) a dynamic one, where banner placement is allowed to vary in different time intervals in order to respond to changes in browsing patterns. Finally, we demonstrate the use of our model on an empiric case study, and analyse the effect of different parameter settings.     

Multiperiod portfolio optimization models in stochastic markets using the mean–variance approach

We consider several multiperiod portfolio optimization models where the market consists of a riskless asset and several risky assets. The returns in any period are random with a mean vector and a covariance matrix that depend on the prevailing economic conditions in the market during that period. An important feature of our model is that the stochastic evolution of the market is described by a Markov chain with perfectly observable states. Various models involving the safety-first approach, coefficient of variation and quadratic utility functions are considered where the objective functions depend only on the mean and the variance of the final wealth. An auxiliary problem that generates the same efficient frontier as our formulations is solved using dynamic programming to identify optimal portfolio management policies for each problem. Illustrative cases are presented to demonstrate the solution procedure with an interpretation of the optimal policies.     

Dynamic mean-risk optimization in a binomial model

We consider a dynamic mean-risk problem, where the risk constraint is given by the Average Value–at–Risk. As financial market we choose a discrete-time binomial model which allows for explicit solutions. Problems where the risk constraint on the final wealth is replaced by intermediate risk constraints are also considered. The problems are solved with the help of the theory of Markov decision models and a Lagrangian approach.     

From polynomial matrices to markov parameters and back: Theory and numerical algorithms

We consider polynomial matrix representations of MIMO linear systems and their connection to Markov parameters. Specifically, we consider polynomial matrix models in an arbitrary operator ρ, and develop theory and numerical algorithms for transforming polynomial matrix models into Markov parameter models, and vice versa. We also provide numerical examples to illustrate the proposed algorithms.     

On the asymptotics of fault probability in least‐recently‐used caching with Zipf‐type request distribution

We consider the least‐recently‐used cache replacement rule with a Zipf‐type page request distribution and investigate an asymptotic property of the fault probability with respect to an increase of cache size. We first derive the asymptotics of the fault probability for the independent‐request model and then extend this derivation to a general dependent‐request model, where our result shows that under some weak assumptions the fault probability is asymptotically invariant with regard to dependence in the page request process. In a previous study, a similar result was derived by applying a Poisson embedding technique, where a continuous‐time proof was given through some assumptions based on a continuous‐time modeling. The Poisson embedding, however, is just a technique used for the proof and the problem is essentially on a discrete‐time basis; thus, it is preferable to make assumptions, if any, directly in the discrete‐time setting. We consider a general dependent‐request model and give a direct discrete‐time proof under different assumptions. A key to the proof is that the numbers of requests for respective pages represent conditionally negatively associated random variables. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

On Queues with Markov Modulated Service Rates

In this paper, we consider a queue whose service speed changes according to an external environment that is governed by a Markov process. It is possible that the server changes its service speed many times while serving a customer. We derive first and second moments of the service time of customers in system using first step analysis to obtain an insight on the service process. In fact, we obtain an intriguing result in that the moments of service time actually depend on the arrival process! We also show that the mean service rate is not the reciprocal of the mean service time. Further, since it is not possible to obtain a closed form expression for the queue length distribution, we use matrix geometric methods to compute performance measures such as average queue length and waiting time. We apply the method of large deviations to obtain tail distributions of the workload in the queue using the concept of effective bandwidth. We present two applications in computer systems: (1) Web server with multi-class requests and (2) CPU with multiple processes. We illustrate the analysis and various methods discussed with the help of numerical examples for the above two applications. AMS subject classification: 90B22, 68M20     

A higher-order Markov model for the Newsboy's problem

Markov models are commonly used in modelling many practical systems such as telecommunication systems, manufacturing systems and inventory systems. However, higher-order Markov models are not commonly used in practice because of their huge number of states and parameters that lead to computational difficulties. In this paper, we propose a higher-order Markov model whose number of states and parameters are linear with respect to the order of the model. We also develop efficient estimation methods for the model parameters. We then apply the model and method to solve the generalised Newsboy's problem. Numerical examples with applications to production planning are given to illustrate the power of our proposed model.     

Discrete time Markov chains with interval probabilities

The parameters of Markov chain models are often not known precisely. Instead of ignoring this problem, a better way to cope with it is to incorporate the imprecision into the models. This has become possible with the development of models of imprecise probabilities, such as the interval probability model. In this paper we discuss some modelling approaches which range from simple probability intervals to the general interval probability models and further to the models allowing completely general convex sets of probabilities. The basic idea is that precisely known initial distributions and transition matrices are replaced by imprecise ones, which effectively means that sets of possible candidates are considered. Consequently, sets of possible results are obtained and represented using similar imprecise probability models.We first set up the model and then show how to perform calculations of the distributions corresponding to the consecutive steps of a Markov chain. We present several approaches to such calculations and compare them with respect to the accuracy of the results. Next we consider a generalisation of the concept of regularity and study the convergence of regular imprecise Markov chains. We also give some numerical examples to compare different approaches to calculations of the sets of probabilities.