Adaptive model selection using empirical complexities

Given $n$ independent replicates of a jointly distributed pair $(X,Y)\in {\cal R}^d \times {\cal R}$, we wish to select from a fixed sequence of model classes ${\cal F}_1, {\cal F}_2, \ldots$ a deterministic prediction rule $f: {\cal R}^d \to {\cal R}$ whose risk is small. We investigate the possibility of empirically assessingthe {\em complexity} of each model class, that is, the actual difficulty of the estimation problem within each class. The estimated complexities are in turn used to define an adaptive model selection procedure, which is based on complexity penalized empirical risk.The available data are divided into two parts. The first is used to form an empirical cover of each model class, and the second is used to select a candidate rule from each cover based on empirical risk. The covering radii are determined empirically to optimize a tight upper bound on the estimation error. An estimate is chosen from the list of candidates in order to minimize the sum of class complexity and empirical risk. A distinguishing feature of the approach is that the complexity of each model class is assessed empirically, based on the size of its empirical cover.Finite sample performance bounds are established for the estimates, and these bounds are applied to several non-parametric estimation problems. The estimates are shown to achieve a favorable tradeoff between approximation and estimation error, and to perform as well as if the distribution-dependent complexities of the model classes were known beforehand. In addition, it is shown that the estimate can be consistent,and even possess near optimal rates of convergence, when each model class has an infinite VC or pseudo dimension.For regression estimation with squared loss we modify our estimate to achieve a faster rate of convergence.

A simple randomized algorithm for consistent sequential prediction of ergodic time series

We present a simple randomized procedure for the prediction of a binary sequence. The algorithm uses ideas from recent developments of the theory of the prediction of individual sequences. We show that if thesequence is a realization of a stationary and ergodic random process then the average number of mistakes converges, almost surely, to that of the optimum, given by the Bayes predictor.

Revealed preference and indifferent selection

It is shown that preferences can be constructed from observed choice behavior in a way that is robust to indifferent selection (i.e., the agent is indifferent between two alternatives but, nevertheless, is only observed selecting one of them). More precisely, a suggestion by Savage (1954) to reveal indifferent selection by considering small monetary perturbations of alternatives is formalized and generalized to a purely topological framework: references over an arbitrary topological space can be uniquely derived from observed behavior under the assumptions that they are continuous and nonsatiated and that a strictly preferred alternative is always chosen, and indifferent selection is then characterized by discontinuity in choice behavior. Two particular cases are then analyzed: monotonic preferences over a partially ordered set, and preferences representable by a continuous pseudo-utility function.

A model of collateral, investment and adverse selection

This paper characterizes the relationship between entrepreneurial wealth and aggregate investmentunder adverse selection. Its main finding is that such a relationship need not bemonotonic. In particular, three results emerge from the analysis: (i) pooling equilibria, in whichinvestment is independent of entrepreneurial wealth, are more likely to arise when entrepreneurialwealth is relatively low; (ii) separating equilibria, in which investment is increasing inentrepreneurial wealth, are most likely to arise when entrepreneurial wealth is relatively highand; (iii) for a given interest rate, an increase in entrepreneurial wealth may generate a discontinuousfall in investment.

Model selection and error estimation

We study model selection strategies based on penalized empirical loss minimization. We point out a tight relationship between error estimation and data-based complexity penalization: any good error estimate may be converted into a data-based penalty function and the performance of the estimate is governed by the quality of the error estimate. We consider several penalty functions, involving error estimates on independent test data, empirical {\sc vc} dimension, empirical {\sc vc} entropy, andmargin-based quantities. We also consider the maximal difference between the error on the first half of the training data and the second half, and the expected maximal discrepancy, a closely related capacity estimate that can be calculated by Monte Carlo integration. Maximal discrepancy penalty functions are appealing for pattern classification problems, since their computation is equivalent to empirical risk minimization over the training data with some labels flipped.

Revised NEO personality inventory normative data for catalan police officer selection: preliminary study

El Servei d'Avaluació, Seguiment i Selecció de l'ISPC han elaborat un estudi sobre el perfil de personalitat dels aspirants al Curs de Formació bàsica per policies, que es va presentar a l'International Society for the Study of Individual Differences Meeting celebrat al CosmoCaixa de Barcelona i que organitzen conjuntament l’Associació Iberoamericana per a la recerca de les diferències individuals i la Universitat de Barcelona. L’estudi, titulat Revised NEO Personality Inventory Normative Data for Catalan police officer selection: A preliminary study, té com a objectiu comparar els perfils de personalitat d’una mostra d’aspirants de l’ISPC amb els resultats d’una mostra d’aspirants a policia dels EUA, publicada en una revista científica de prestigi el mes de febrer passat. Els resultats mostren que els aspirants catalans destaquen per obtenir millors puntuacions en les dimensions de responsabilitat i amabilitat, cosa que indicaria que aquest tret es valora especialment durant el procés de selecció de la policia de Catalunya; en altres característiques de la personalitat les dues mostres obtenen resultats similars. Els trets característics del perfil del policia català seria el de persones estables emocionalment, poc impulsives, amb capacitat per gestionar l’estrés, orientades a les persones, agradables, sociables, responsables, disciplinades i cauteloses. Enllaç a: International Society for the Study of Individual Differences Meeting :http://www.issid.org/conferences/ISSID2013/ISSIDconference2013.html

MSISpIC: A Probabilistic Scan Matching Algorithm Using a Mechanical Scanned Imaging Sonar

This paper compares two well known scan matching algorithms: the MbICP and the pIC. As a result of the study, it is proposed the MSISpIC, a probabilistic scan matching algorithm for the localization of an Autonomous Underwater Vehicle (AUV). The technique uses range scans gathered with a Mechanical Scanning Imaging Sonar (MSIS), and the robot displacement estimated through dead-reckoning with the help of a Doppler Velocity Log (DVL) and a Motion Reference Unit (MRU). The proposed method is an extension of the pIC algorithm. Its major contribution consists in: 1) using an EKF to estimate the local path traveled by the robot while grabbing the scan as well as its uncertainty and 2) proposing a method to group into a unique scan, with a convenient uncertainty model, all the data grabbed along the path described by the robot. The algorithm has been tested on an AUV guided along a 600m path within a marina environment with satisfactory results

An Efficient Nominal Unification Algorithm

Nominal Unification is an extension of first-order unification where terms can contain binders and unification is performed modulo α equivalence. Here we prove that the existence of nominal unifiers can be decided in quadratic time. First, we linearly-reduce nominal unification problems to a sequence of freshness and equalities between atoms, modulo a permutation, using ideas as Paterson and Wegman for first-order unification. Second, we prove that solvability of these reduced problems may be checked in quadràtic time. Finally, we point out how using ideas of Brown and Tarjan for unbalanced merging, we could solve these reduced problems more efficiently

A fast Bayesian reconstruction algorithm for emission tomography with entropy prior converging to feasible images

The development and tests of an iterative reconstruction algorithm for emission tomography based on Bayesian statistical concepts are described. The algorithm uses the entropy of the generated image as a prior distribution, can be accelerated by the choice of an exponent, and converges uniformly to feasible images by the choice of one adjustable parameter. A feasible image has been defined as one that is consistent with the initial data (i.e. it is an image that, if truly a source of radiation in a patient, could have generated the initial data by the Poisson process that governs radioactive disintegration). The fundamental ideas of Bayesian reconstruction are discussed, along with the use of an entropy prior with an adjustable contrast parameter, the use of likelihood with data increment parameters as conditional probability, and the development of the new fast maximum a posteriori with entropy (FMAPE) Algorithm by the successive substitution method. It is shown that in the maximum likelihood estimator (MLE) and FMAPE algorithms, the only correct choice of initial image for the iterative procedure in the absence of a priori knowledge about the image configuration is a uniform field.

Habitat selection by grey mullets (Osteichthyes: Mugilidae) in Mediterranean estuaries: the role of salinity.

A stratified study of microhabitat use by grey mullet on the island of Minorca (Balearic archipelago, western Mediterranean) showed that the distribution of all the species was dramatically affected by salinity. Sites with a salinity level under 15 were positively selected in spring and summer by those species whose growth performance was the best in oligomesohaline water (Liza ramado and Mugil cephalus) but also by a species whose growth was not affected by salinity (Chelon labrosus). Liza aurata concentrated in polyhaline and euhaline sites, where growth was improved, a pattern also exhibited by Liza saliens. Both species avoided fresh water sites all year round. As a consequence, community structure was correlated with salinity. The above reported electivity patterns often disappeared in autumn, when most grey mullets migrate off-shore.

Fine-Tuning Translation Kinetics Selection as the Driving Force of Codon Usage Bias in the Hepatitis A Virus Capsid

Hepatitis A virus (HAV), the prototype of genus Hepatovirus, has several unique biological characteristics that distinguish it from other members of the Picornaviridae family. Among these, the need for an intact eIF4G factor for the initiation of translation results in an inability to shut down host protein synthesis by a mechanism similar to that of other picornaviruses. Consequently, HAV must inefficiently compete for the cellular translational machinery and this may explain its poor growth in cell culture. In this context of virus/cell competition, HAV has strategically adopted a naturally highly deoptimized codon usage with respect to that of its cellular host. With the aim to optimize its codon usage the virus was adapted to propagate in cells with impaired protein synthesis, in order to make tRNA pools more available for the virus. A significant loss of fitness was the immediate response to the adaptation process that was, however, later on recovered and more associated to a re-deoptimization rather than to an optimization of the codon usage specifically in the capsid coding region. These results exclude translation selection and instead suggest fine-tuning translation kinetics selection as the underlying mechanism of the codon usage bias in this specific genome region. Additionally, the results provide clear evidence of the Red Queen dynamics of evolution since the virus has very much evolved to re-adapt its codon usage to the environmental cellular changing conditions in order to recover the original fitness.

Numerical algorithm for Ginzburg-Landau equations with multiplicative noise: Application to domain growth

We consider stochastic partial differential equations with multiplicative noise. We derive an algorithm for the computer simulation of these equations. The algorithm is applied to study domain growth of a model with a conserved order parameter. The numerical results corroborate previous analytical predictions obtained by linear analysis.

Comment on "Selection of the Saffman-Taylor finger width in the absence of surface tension: an exact result"

A Comment on the Letter by Mark Mineev-Weinstein, Phys. Rev. Lett. 80, 2113 (1998). The authors of the Letter offer a Reply.

Majorization arrow in quantum-algorithm design

We apply majorization theory to study the quantum algorithms known so far and find that there is a majorization principle underlying the way they operate. Grover's algorithm is a neat instance of this principle where majorization works step by step until the optimal target state is found. Extensions of this situation are also found in algorithms based in quantum adiabatic evolution and the family of quantum phase-estimation algorithms, including Shor's algorithm. We state that in quantum algorithms the time arrow is a majorization arrow.

Selection, shape and relaxation of fronts: A numerical study of the effects of inertia.

We study the problem of front propagation in the presence of inertia. We extend the analytical approach for the overdamped problem to this case, and present numerical results to support our theoretical predictions. Specifically, we conclude that the velocity and shape selection problem can still be described in terms of the metastable, nonlinear, and linear overdamped regimes. We study the characteristic relaxation dynamics of these three regimes, and the existence of degenerate (¿quenched¿) solutions.