Computationally Efficient Methods for MDL-Optimal Density Estimation and Data Clustering

The Minimum Description Length (MDL) principle is a general, well-founded theoretical formalization of statistical modeling. The most important notion of MDL is the stochastic complexity, which can be interpreted as the shortest description length of a given sample of data relative to a model class. The exact definition of the stochastic complexity has gone through several evolutionary steps. The latest instantation is based on the so-called Normalized Maximum Likelihood (NML) distribution which has been shown to possess several important theoretical properties. However, the applications of this modern version of the MDL have been quite rare because of computational complexity problems, i.e., for discrete data, the definition of NML involves an exponential sum, and in the case of continuous data, a multi-dimensional integral usually infeasible to evaluate or even approximate accurately. In this doctoral dissertation, we present mathematical techniques for computing NML efficiently for some model families involving discrete data. We also show how these techniques can be used to apply MDL in two practical applications: histogram density estimation and clustering of multi-dimensional data.

Plan dachi obrazovannoĭ iz Kolfondov chasti Nº 387 i NºNº 389, 390, 392 i 466, Odesskŏi gubernii Khersoskogo okruga, Snigirskogo raĭona i Nº398 Khersonskogo raĭna razverstannoi na optimalʻnye uchastki

Digital image

Optimal popular matchings

In this paper we consider the problem of computing an “optimal” popular matching. We assume that our input instance View the MathML source admits a popular matching and here we are asked to return not any popular matching but an optimal popular matching, where the definition of optimality is given as a part of the problem statement; for instance, optimality could be fairness in which case we are required to return a fair popular matching. We show an O(n2+m) algorithm for this problem, assuming that the preference lists are strict, where m is the number of edges in G and n is the number of applicants.

Iterative solution of a class of linear equations with application to reconstruction of three-dimensional object arrays

An iterative algorithm baaed on probabilistic estimation is described for obtaining the minimum-norm solution of a very large, consistent, linear system of equations AX = g where A is an (m times n) matrix with non-negative elements, x and g are respectively (n times 1) and (m times 1) vectors with positive components.

Optimal maintenance and replacement via a semi-Markov decision model

Optimal bang-coast maintenance policies for a machine, subject to failure, are considered. The approach utilizes a semi-Markov model for the system. A simplified model for modifying the probability of machine failure with maintenance is employed. A numerical example is presented to illustrate the procedure and results.

Intrinsic equations of steady rotating, incompressible viscous fluid flow

The equations governing the flow of a steady rotating incompressible viscous fluid are expressed in intrinsic form along the vortex lines and their normals. Using these equations the effects of rotation on the geometric properties of viscous fluid flows are studied. A particular flow in which the vortex lines are right circular helices is discussed.

Factors influencing kinetic and equilibrium behaviour of sodium ion exchange with strong acid cation resin

This study reports an investigation of the ion exchange treatment of sodium chloride solutions in relation to use of resin technology for applications such as desalination of brackish water. In particular, a strong acid cation (SAC) resin (DOW Marathon C) was studied to determine its capacity for sodium uptake and to evaluate the fundamentals of the ion exchange process involved. Key questions to answer included: impact of resin identity; best models to simulate the kinetics and equilibrium exchange behaviour of sodium ions; difference between using linear least squares (LLS) and non-linear least squares (NLLS) methods for data interpretation; and, effect of changing the type of anion in solution which accompanied the sodium species. Kinetic studies suggested that the exchange process was best described by a pseudo first order rate expression based upon non-linear least squares analysis of the test data. Application of the Langmuir Vageler isotherm model was recommended as it allowed confirmation that experimental conditions were sufficient for maximum loading of sodium ions to occur. The Freundlich expression best fitted the equilibrium data when analysing the information by a NLLS approach. In contrast, LLS methods suggested that the Langmuir model was optimal for describing the equilibrium process. The Competitive Langmuir model which considered the stoichiometric nature of ion exchange process, estimated the maximum loading of sodium ions to be 64.7 g Na/kg resin. This latter value was comparable to sodium ion capacities for SAC resin published previously. Inherent discrepancies involved when using linearized versions of kinetic and isotherm equations were illustrated, and despite their widespread use, the value of this latter approach was questionable. The equilibrium behaviour of sodium ions form sodium fluoride solution revealed that the sodium ions were now more preferred by the resin compared to the situation with sodium chloride. The solution chemistry of hydrofluoric acid was suggested as promoting the affinity of the sodium ions to the resin.

Optimal adaptive sequential spatial sampling of soil using pair-copulas

A spatial sampling design that uses pair-copulas is presented that aims to reduce prediction uncertainty by selecting additional sampling locations based on both the spatial configuration of existing locations and the values of the observations at those locations. The novelty of the approach arises in the use of pair-copulas to estimate uncertainty at unsampled locations. Spatial pair-copulas are able to more accurately capture spatial dependence compared to other types of spatial copula models. Additionally, unlike traditional kriging variance, uncertainty estimates from the pair-copula account for influence from measurement values and not just the configuration of observations. This feature is beneficial, for example, for more accurate identification of soil contamination zones where high contamination measurements are located near measurements of varying contamination. The proposed design methodology is applied to a soil contamination example from the Swiss Jura region. A partial redesign of the original sampling configuration demonstrates the potential of the proposed methodology.

Constrained linear filter and its relation to singular optimal control

This paper presents an analysis of an optimal linear filter in the presence of constraints on the moan squared values of the estimates from the viewpoint of singular optimal control. The singular arc has been shown to satisfy the generalized Legcndrc-Clebseh condition and Jacobson's condition. Both the cases of white measurement noise and coloured measurement noise are considered. The constrained estimate is shown to be a linear transformation of the unconstrained Kalman estimate.

Approximation of the perturbation equations of a quasi-linear hyperbolic system in the neighborhood of a bicharacteristic

In 1956 Whitham gave a nonlinear theory for computing the intensity of an acoustic pulse of an arbitrary shape. The theory has been used very successfully in computing the intensity of the sonic bang produced by a supersonic plane. [4.] derived an approximate quasi-linear equation for the propagation of a short wave in a compressible medium. These two methods are essentially nonlinear approximations of the perturbation equations of the system of gas-dynamic equations in the neighborhood of a bicharacteristic curve (or rays) for weak unsteady disturbances superimposed on a given steady solution. In this paper we have derived an approximate quasi-linear equation which is an approximation of perturbation equations in the neighborhood of a bicharacteristic curve for a weak pulse governed by a general system of first order quasi-linear partial differential equations in m + 1 independent variables (t, x1,…, xm) and derived Gubkin's result as a particular case when the system of equations consists of the equations of an unsteady motion of a compressible gas. We have also discussed the form of the approximate equation describing the waves propagating upsteam in an arbitrary multidimensional transonic flow.

Analytical method for solving a set of inhomogeneous infinite simultaneous equations

It is shown that a method based on the principle of analytic continuation can be used to solve a set of inhomogeneous infinite simultaneous equations encountered in the analysis of surface acoustic wave propagation along the periodically perturbed surface of a piezoelectric medium.

Optimal maintenance policy for equipment subject to random deterioration and random failure A modern control theory approach.

The stochastic version of Pontryagin's maximum principle is applied to determine an optimal maintenance policy of equipment subject to random deterioration. The deterioration of the equipment with age is modelled as a random process. Next the model is generalized to include random catastrophic failure of the equipment. The optimal maintenance policy is derived for two special probability distributions of time to failure of the equipment, namely, exponential and Weibull distributions Both the salvage value and deterioration rate of the equipment are treated as state variables and the maintenance as a control variable. The result is illustrated by an example

Queuing Models for Estimating Aircraft Fleet Availability

The availability of a small fleet of aircraft in a flying-base, repair-depot combination is modeled and studied. First, a deterministic flow model relates parameters of interest and represents the state-of-the art in the planning of such systems. Second, a cyclic queue model shows the effect of the principal uncertainties in operation and repair and shows the consequent decrease in the availability of aircraft at the flying-base. Several options such as increasing fleet size, investments in additional repair facilities, or building reliability and maintainability into the individual aircraft during its life-cycle are open for increasing the availability. A life-cycle cost criterion brings out some of these features. Numerical results confirm Rose's prediction that there exists a minimal cost combination of end products and repair-depot capability to achieve a prescribed operational availability.

An Optimal Mechanism for Sponsored Search Auctions on the Web and Comparison With Other Mechanisms

In this paper, we first describe a framework to model the sponsored search auction on the web as a mechanism design problem. Using this framework, we describe two well-known mechanisms for sponsored search auction-Generalized Second Price (GSP) and Vickrey-Clarke-Groves (VCG). We then derive a new mechanism for sponsored search auction which we call optimal (OPT) mechanism. The OPT mechanism maximizes the search engine's expected revenue, while achieving Bayesian incentive compatibility and individual rationality of the advertisers. We then undertake a detailed comparative study of the mechanisms GSP, VCG, and OPT. We compute and compare the expected revenue earned by the search engine under the three mechanisms when the advertisers are symmetric and some special conditions are satisfied. We also compare the three mechanisms in terms of incentive compatibility, individual rationality, and computational complexity. Note to Practitioners-The advertiser-supported web site is one of the successful business models in the emerging web landscape. When an Internet user enters a keyword (i.e., a search phrase) into a search engine, the user gets back a page with results, containing the links most relevant to the query and also sponsored links, (also called paid advertisement links). When a sponsored link is clicked, the user is directed to the corresponding advertiser's web page. The advertiser pays the search engine in some appropriate manner for sending the user to its web page. Against every search performed by any user on any keyword, the search engine faces the problem of matching a set of advertisers to the sponsored slots. In addition, the search engine also needs to decide on a price to be charged to each advertiser. Due to increasing demands for Internet advertising space, most search engines currently use auction mechanisms for this purpose. These are called sponsored search auctions. A significant percentage of the revenue of Internet giants such as Google, Yahoo!, MSN, etc., comes from sponsored search auctions. In this paper, we study two auction mechanisms, GSP and VCG, which are quite popular in the sponsored auction context, and pursue the objective of designing a mechanism that is superior to these two mechanisms. In particular, we propose a new mechanism which we call the OPT mechanism. This mechanism maximizes the search engine's expected revenue subject to achieving Bayesian incentive compatibility and individual rationality. Bayesian incentive compatibility guarantees that it is optimal for each advertiser to bid his/her true value provided that all other agents also bid their respective true values. Individual rationality ensures that the agents participate voluntarily in the auction since they are assured of gaining a non-negative payoff by doing so.