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.

Worst-case bounds for the logarithmic loss of predictors

We investigate on-line prediction of individual sequences. Given a class of predictors, the goal is to predict as well as the best predictor in the class, where the loss is measured by the self information (logarithmic) loss function. The excess loss (regret) is closely related to the redundancy of the associated lossless universal code. Using Shtarkov's theorem and tools from empirical process theory, we prove a general upper bound on the best possible (minimax) regret. The bound depends on certain metric properties of the class of predictors. We apply the bound to both parametric and nonparametric classes ofpredictors. Finally, we point out a suboptimal behavior of the popular Bayesian weighted average algorithm.

On bounds for network revenue management

The Network Revenue Management problem can be formulated as a stochastic dynamic programming problem (DP or the\optimal" solution V *) whose exact solution is computationally intractable. Consequently, a number of heuristics have been proposed in the literature, the most popular of which are the deterministic linear programming (DLP) model, and a simulation based method, the randomized linear programming (RLP) model. Both methods give upper bounds on the optimal solution value (DLP and PHLP respectively). These bounds are used to provide control values that can be used in practice to make accept/deny decisions for booking requests. Recently Adelman [1] and Topaloglu [18] have proposed alternate upper bounds, the affine relaxation (AR) bound and the Lagrangian relaxation (LR) bound respectively, and showed that their bounds are tighter than the DLP bound. Tight bounds are of great interest as it appears from empirical studies and practical experience that models that give tighter bounds also lead to better controls (better in the sense that they lead to more revenue). In this paper we give tightened versions of three bounds, calling themsAR (strong Affine Relaxation), sLR (strong Lagrangian Relaxation) and sPHLP (strong Perfect Hindsight LP), and show relations between them. Speciffically, we show that the sPHLP bound is tighter than sLR bound and sAR bound is tighter than the LR bound. The techniques for deriving the sLR and sPHLP bounds can potentially be applied to other instances of weakly-coupled dynamic programming.

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.

Bounds for the Betti numbers of generalized Cohen-Macaulay ideals

Upper bounds for the Betti numbers of generalized Cohen-Macaulay ideals are given. In particular, for the case of non-degenerate, reduced and ir- reducible projective curves we get an upper bound which only depends on their degree.

Bounds on multisecant lines

The purpose of this paper is two fold. First, we give an upper bound on the orderof a multisecant line to an integral arithmetically Cohen-Macaulay subscheme in Pn of codimension two in terms of the Hilbert function. Secondly, we givean explicit description of the singular locus of the blow up of an arbitrary local ring at a complete intersection ideal. This description is used to refine standardlinking theorem. These results are tied together by the construction of sharp examples for the bound, which uses the linking theorems.

A new estimator to minimize the error due to breathing in the measurement of respiratory impedance

This paper presents a new respiratory impedance estimator to minimize the error due to breathing. Its practical reliability was evaluated in a simulation using realistic signals. These signals were generated by superposing pressure and flow records obtained in two conditions: 1) when applying forced oscillation to a resistance- inertance- elastance (RIE) mechanical model; 2) when healthy subjects breathed through the unexcited forced oscillation generator. Impedances computed (4-32 Hz) from the simulated signals with the new estimator resulted in a mean value which was scarcely biased by the added breathing (errors less than 1 percent in the mean R, I , and E ) and had a small variability (coefficients of variation of R, I, and E of 1.3, 3.5, and 9.6 percent, respectively). Our results suggest that the proposed estimator reduces the error in measurement of respiratory impedance without appreciable extracomputational cost.

The assignment game: core bounds for mixed-pair coalitions

In the assignment game framework, we try to identify those assignment matrices in which no entry can be increased without changing the coreof the game. These games will be called buyer¿seller exact games and satisfy the condition that each mixed¿pair coalition attains the corresponding matrix entry in the core of the game. For a given assignment game, a unique buyerseller exact assignment game with the same core is proved to exist. In order to identify this matrix and to provide a characterization of those assignment games which are buyer¿seller exact in terms of the assignment matrix, attainable upper and lower core bounds for the mixed¿pair coalitions are found. As a consequence, an open question posed in Quint (1991) regarding a canonical representation of a ¿45o¿lattice¿ by means of the core of an assignment game can now be answered

Model-independent bounds for the potential and kinetic energy of liquid 4He at zero temperature

Using the experimental values of the chemical potentials of liquid 4He and of a 3He impurity in liquid 4He, we derive a model-independent lower (upper) bound to the kinetic (potential) energy per particle at zero temperature. The values of the bounds at the experimental saturation density are 13.42 K for the kinetic energy and -20.59 K for the potential energy. All the theoretical calculations based on the Lennard-Jones potential violate the upper-bound condition for the potential energy.

Exact lower bounds to the ground-state energy of spin systems: The two-dimensional S=1/2 antiferromagnetic Heisenberg model

We present a very simple but fairly unknown method to obtain exact lower bounds to the ground-state energy of any Hamiltonian that can be partitioned into a sum of sub-Hamiltonians. The technique is applied, in particular, to the two-dimensional spin-1/2 antiferromagnetic Heisenberg model. Reasonably good results are easily obtained and the extension of the method to other systems is straightforward.

Discriminant ECOC: a heuristic method for application dependent design of error correcting output codes

We present a heuristic method for learning error correcting output codes matrices based on a hierarchical partition of the class space that maximizes a discriminative criterion. To achieve this goal, the optimal codeword separation is sacrificed in favor of a maximum class discrimination in the partitions. The creation of the hierarchical partition set is performed using a binary tree. As a result, a compact matrix with high discrimination power is obtained. Our method is validated using the UCI database and applied to a real problem, the classification of traffic sign images.

Subclass problem-dependent design for error-correcting output codes

A common way to model multiclass classification problems is by means of Error-Correcting Output Codes (ECOCs). Given a multiclass problem, the ECOC technique designs a code word for each class, where each position of the code identifies the membership of the class for a given binary problem. A classification decision is obtained by assigning the label of the class with the closest code. One of the main requirements of the ECOC design is that the base classifier is capable of splitting each subgroup of classes from each binary problem. However, we cannot guarantee that a linear classifier model convex regions. Furthermore, nonlinear classifiers also fail to manage some type of surfaces. In this paper, we present a novel strategy to model multiclass classification problems using subclass information in the ECOC framework. Complex problems are solved by splitting the original set of classes into subclasses and embedding the binary problems in a problem-dependent ECOC design. Experimental results show that the proposed splitting procedure yields a better performance when the class overlap or the distribution of the training objects conceal the decision boundaries for the base classifier. The results are even more significant when one has a sufficiently large training size.

The assignment game: core bounds for mixed-pair coalitions

In the assignment game framework, we try to identify those assignment matrices in which no entry can be increased without changing the coreof the game. These games will be called buyer¿seller exact games and satisfy the condition that each mixed¿pair coalition attains the corresponding matrix entry in the core of the game. For a given assignment game, a unique buyerseller exact assignment game with the same core is proved to exist. In order to identify this matrix and to provide a characterization of those assignment games which are buyer¿seller exact in terms of the assignment matrix, attainable upper and lower core bounds for the mixed¿pair coalitions are found. As a consequence, an open question posed in Quint (1991) regarding a canonical representation of a ¿45o¿lattice¿ by means of the core of an assignment game can now be answered

Les cegueses del coneixement: l'error i la il·lusió a partir de "El cónsul de sodoma"

Podeu consultar el document complet de la "XVI Setmana de Cinema Formatiu" a: http://hdl.handle.net/2445/22523

Subjetividad humana y "error" en la filosofía cartesiana

El presente trabajo, continuando la línea investigadora acerca de las nociones derazón, conciencia y subjetividad en Descartes, tal como se ha defendido en otros artículos ya publicados, aporta un nuevo argumento a una línea de trabajo previamente iniciada, poniendo de relieve que el problema gnoseológico del error viene condicionado por la misma noción cartesiana de racionalidad, y que ésta dista mucho de lo que tradicionalmente se ha entendido como una racionalidad abstracta y formal, libre de los imperativos humanos. Por otro lado, y a la inversa, también se intenta mostrar como el hecho del error contribuye, cartesianamente hablando, a definir un modelo de racionalidad profundamentehumanizada. El artículo, tras una introducción, se propone analizar las relaciones entre los conceptos básicos de racionalidad, dogma, y naturaleza, lo que permitirá a continuación dejar constancia de la copertenencia entre racionalidad y error, para acabar viendo como la libertad humana es la vez, y para ambos, su fundamento último.