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.

Restless bandits, linear programming relaxations and a primal-dual index heuristic

We develop a mathematical programming approach for the classicalPSPACE - hard restless bandit problem in stochastic optimization.We introduce a hierarchy of n (where n is the number of bandits)increasingly stronger linear programming relaxations, the lastof which is exact and corresponds to the (exponential size)formulation of the problem as a Markov decision chain, while theother relaxations provide bounds and are efficiently computed. Wealso propose a priority-index heuristic scheduling policy fromthe solution to the first-order relaxation, where the indices aredefined in terms of optimal dual variables. In this way wepropose a policy and a suboptimality guarantee. We report resultsof computational experiments that suggest that the proposedheuristic policy is nearly optimal. Moreover, the second-orderrelaxation is found to provide strong bounds on the optimalvalue.

An enhanced concave program relaxation for choice network revenue management

The network choice revenue management problem models customers as choosing from an offer-set, andthe firm decides the best subset to offer at any given moment to maximize expected revenue. The resultingdynamic program for the firm is intractable and approximated by a deterministic linear programcalled the CDLP which has an exponential number of columns. However, under the choice-set paradigmwhen the segment consideration sets overlap, the CDLP is difficult to solve. Column generation has beenproposed but finding an entering column has been shown to be NP-hard. In this paper, starting with aconcave program formulation based on segment-level consideration sets called SDCP, we add a class ofconstraints called product constraints, that project onto subsets of intersections. In addition we proposea natural direct tightening of the SDCP called ?SDCP, and compare the performance of both methodson the benchmark data sets in the literature. Both the product constraints and the ?SDCP method arevery simple and easy to implement and are applicable to the case of overlapping segment considerationsets. In our computational testing on the benchmark data sets in the literature, SDCP with productconstraints achieves the CDLP value at a fraction of the CPU time taken by column generation and webelieve is a very promising approach for quickly approximating CDLP when segment consideration setsoverlap and the consideration sets themselves are relatively small.

Optimization of multiclass queueing networks with changeover times via the achievable region method: Part II, the multi-station case

We address the problem of scheduling a multi-station multiclassqueueing network (MQNET) with server changeover times to minimizesteady-state mean job holding costs. We present new lower boundson the best achievable cost that emerge as the values ofmathematical programming problems (linear, semidefinite, andconvex) over relaxed formulations of the system's achievableperformance region. The constraints on achievable performancedefining these formulations are obtained by formulatingsystem's equilibrium relations. Our contributions include: (1) aflow conservation interpretation and closed formulae for theconstraints previously derived by the potential function method;(2) new work decomposition laws for MQNETs; (3) new constraints(linear, convex, and semidefinite) on the performance region offirst and second moments of queue lengths for MQNETs; (4) a fastbound for a MQNET with N customer classes computed in N steps; (5)two heuristic scheduling policies: a priority-index policy, anda policy extracted from the solution of a linear programmingrelaxation.

On heuristic and linear models of judgment: Mapping the demand for knowledge

Research on judgment and decision making presents a confusing picture of human abilities. For example, much research has emphasized the dysfunctional aspects of judgmental heuristics, and yet, other findings suggest that these can be highly effective. A further line of research has modeled judgment as resulting from as if linear models. This paper illuminates the distinctions in these approaches by providing a common analytical framework based on the central theoretical premise that understanding human performance requires specifying how characteristics of the decision rules people use interact with the demands of the tasks they face. Our work synthesizes the analytical tools of lens model research with novel methodology developed to specify the effectiveness of heuristics in different environments and allows direct comparisons between the different approaches. We illustrate with both theoretical analyses and simulations. We further link our results to the empirical literature by a meta-analysis of lens model studies and estimate both human andheuristic performance in the same tasks. Our results highlight the trade-off betweenlinear models and heuristics. Whereas the former are cognitively demanding, the latterare simple to use. However, they require knowledge and thus maps of when andwhich heuristic to employ.

O Primal e o Dual na programação Linear

O tema da Programação Linear, com as suas particularizações do Problema dos Transportes e do Problema da Afectação de Recursos, é hoje estudado em cursos diversos onde uma disciplina de Investigação Operacional esteja presente. Trata-se, em última análise, de um problema de cálculo de extremos condicionados, seja de máximo ou de mínimo, que apresenta características muito particulares e de grande elegância simbólica. Também os Problemas dos Transportes e da Afectação de Recursos se podem resolver como problemas de Programação Linear, através do Algoritmo Simplex, embora seja preferível o recurso a algoritmos próprios, de muitíssimo maior simplicidade: o Algoritmo dos Transportes e o Algoritmo Húngaro, respectivamente. De molde a facilitar a compreensão do que realmente está em jogo, consideram-se aqui dois casos de determinação de extremos e de extremos condicionados, mas ao nível do final do ensino secundário.

Biomass estimation of Triplectides egleri Sattler (Trichoptera, Leptoceridae) in a stream at Ducke Reserve, Central Amazonia

ABSTRACT Biomass is a fundamental measure for understanding the structure and functioning (e.g. fluxes of energy and nutrients in the food chain) of aquatic ecosystems. We aim to provide predictive models to estimate the biomass of Triplectides egleri Sattler, 1963, in a stream in Central Amazonia, based on body and case dimensions. We used body length, head-capsule width, interocular distance and case length and width to derive biomass estimations. Linear, exponential and power regression models were used to assess the relationship between biomass and body or case dimensions. All regression models used in the biomass estimation of T. egleri were significant. The best fit between biomass and body or case dimensions was obtained using the power model, followed by the exponential and linear models. Body length provided the best estimate of biomass. However, the dimensions of sclerotized structures (interocular distance and head-capsule width) also provided good biomass predictions, and may be useful in estimating biomass of preserved and/or damaged material. Case width was the dimension of the case that provided the best estimate of biomass. Despite the low relation, case width may be useful in studies that require low stress on individuals.

Comparação entre os métodos da transeção linear e fotográfico na avaliação de cobertura vegetal morta, sob dois métodos de preparo, após a colheita da soja

A eficácia da cobertura vegetal morta no controle da erosão pode ser avaliada através de dois indicadores principais: a porcentagem de cobertura do solo pelos resíduos culturais e sua persistência sobre a superfície ao longo do tempo. O preparo do solo, por sua vez, pode exercer influência significativa sobre esses indicadores. O trabalho foi realizado no campo, no município de Eldorado do Sul, Depressão Central do Rio Grande do Sul. Avaliou-se a persistência da cobertura vegetal morta durante um período de pousio, que foi de maio de 1989 a abril de 1990, em sucessão à cultura da soja. Os resíduos dessa cultura foram manejados sem preparo, por escarificação e por gradagem. A porcentagem de cobertura do solo pelos resíduos culturais foi quantificada pelo método fotográfico e pelo da transeção linear. A cultura da soja produziu cobertura vegetal morta em pequena quantidade e de baixa durabilidade. A distribuição dos resíduos na superfície, sem preparo do solo, foi o tratamento que possibilitou melhor correlação (R²) entre os índices de cobertura obtidos pelos dois métodos testados. Nas áreas sob gradagem ou escarificação do solo, os índices de cobertura obtidos pelo método fotográfico foram superiores aos da transeção linear, enquanto, na área sem preparo do solo, houve similaridade entre os resultados dos dois métodos.

Elevated inflammatory markers combined with positive pneumococcal urinary antigen are a good predictor of pneumococcal community-acquired pneumonia in children.

BACKGROUND: Our objective was to evaluate procalcitonin (PCT) and C-reactive protein (CRP) as predictors of a pneumococcal etiology in community-acquired pneumonia (CAP) in hospitalized children. METHODS: Children requiring hospitalization for CAP were prospectively enrolled. The following indices were determined: antibodies against pneumococcal surface proteins (anti-PLY, pneumococcal histidine triad D, pneumococcal histidine triad E, LytB and pneumococcal choline-binding protein A), viral serology, nasopharyngeal cultures and polymerase chain reaction for 13 respiratory viruses, blood pneumococcal polymerase chain reaction, pneumococcal urinary antigen, PCT and CRP. Presumed pneumococcal CAP (P-CAP) was defined as a positive blood culture or polymerase chain reaction for Streptococcus pneumoniae or as a pneumococcal surface protein seroresponse (≥2-fold increase). RESULTS: Seventy-five patients were included from which 37 (49%) met the criteria of P-CAP. Elevated PCT and CRP values were strongly associated with P-CAP with odds ratios of 23 (95% confidence interval: 5-117) for PCT and 19 (95% confidence interval: 5-75) for CRP in multivariate analysis. The sensitivity was 94.4% for PCT (cutoff: 1.5 ng/mL) and 91.9% for CRP (cutoff: 100 mg/L). A value≤0.5 ng/mL of PCT ruled out P-CAP in >90% of cases (negative likelihood ratio: 0.08). Conversely, a PCT value≥1.5 ng/mL associated with a positive pneumococcal urinary antigen had a diagnostic probability for P-CAP of almost 80% (positive likelihood ratio: 4.59). CONCLUSIONS: PCT and CRP are reliable predictors of P-CAP. Low cutoff values of PCT allow identification of children at low risk of P-CAP. The association of elevated PCT or CRP with a positive pneumococcal urinary antigen is a strong predictor of P-CAP.

New reference tables and user-friendly Internet application for predicted heart weights.

BACKGROUND: Knowledge of normal heart weight ranges is important information for pathologists. Comparing the measured heart weight to reference values is one of the key elements used to determine if the heart is pathological, as heart weight increases in many cardiac pathologies. The current reference tables are old and in need of an update. AIMS: The purposes of this study are to establish new reference tables for normal heart weights in the local population and to determine the best predictive factor for normal heart weight. We also aim to provide technical support to calculate the predictive normal heart weight. METHODS: The reference values are based on retrospective analysis of adult Caucasian autopsy cases without any obvious pathology that were collected at the University Centre of Legal Medicine in Lausanne from 2007 to 2011. We selected 288 cases. The mean age was 39.2 years. There were 118 men and 170 women. Regression analyses were performed to assess the relationship of heart weight to body weight, body height, body mass index (BMI) and body surface area (BSA). RESULTS: The heart weight increased along with an increase in all the parameters studied. The mean heart weight was greater in men than in women at a similar body weight. BSA was determined to be the best predictor for normal heart weight. New reference tables for predicted heart weights are presented as a web application that enable the comparison of heart weights observed at autopsy with the reference values. CONCLUSIONS: The reference tables for heart weight and other organs should be systematically updated and adapted for the local population. Web access and smartphone applications for the predicted heart weight represent important investigational tools.

Broad-scale adaptive genetic variation in alpine plants is driven by temperature and precipitation.

Identifying adaptive genetic variation is a challenging task, in particular in non-model species for which genomic information is still limited or absent. Here, we studied distribution patterns of amplified fragment length polymorphisms (AFLPs) in response to environmental variation, in 13 alpine plant species consistently sampled across the entire European Alps. Multiple linear regressions were performed between AFLP allele frequencies per site as dependent variables and two categories of independent variables, namely Moran's eigenvector map MEM variables (to account for spatial and unaccounted environmental variation, and historical demographic processes) and environmental variables. These associations allowed the identification of 153 loci of ecological relevance. Univariate regressions between allele frequency and each environmental factor further showed that loci of ecological relevance were mainly correlated with MEM variables. We found that precipitation and temperature were the best environmental predictors, whereas topographic factors were rarely involved in environmental associations. Climatic factors, subject to rapid variation as a result of the current global warming, are known to strongly influence the fate of alpine plants. Our study shows, for the first time for a large number of species, that the same environmental variables are drivers of plant adaptation at the scale of a whole biome, here the European Alps.

Comparison of the glomerular filtration rate in children by the new revised Schwartz formula and a new generalized formula.

The most widely used formula for estimating glomerular filtration rate (eGFR) in children is the Schwartz formula. It was revised in 2009 using iohexol clearances with measured GFR (mGFR) ranging between 15 and 75 ml/min × 1.73 m(2). Here we assessed the accuracy of the Schwartz formula using the inulin clearance (iGFR) method to evaluate its accuracy for children with less renal impairment comparing 551 iGFRs of 392 children with their Schwartz eGFRs. Serum creatinine was measured using the compensated Jaffe method. In order to find the best relationship between iGFR and eGFR, a linear quadratic regression model was fitted and a more accurate formula was derived. This quadratic formula was: 0.68 × (Height (cm)/serum creatinine (mg/dl))-0.0008 × (height (cm)/serum creatinine (mg/dl))(2)+0.48 × age (years)-(21.53 in males or 25.68 in females). This formula was validated using a split-half cross-validation technique and also externally validated with a new cohort of 127 children. Results show that the Schwartz formula is accurate until a height (Ht)/serum creatinine value of 251, corresponding to an iGFR of 103 ml/min × 1.73 m(2), but significantly unreliable for higher values. For an accuracy of 20 percent, the quadratic formula was significantly better than the Schwartz formula for all patients and for patients with a Ht/serum creatinine of 251 or greater. Thus, the new quadratic formula could replace the revised Schwartz formula, which is accurate for children with moderate renal failure but not for those with less renal impairment or hyperfiltration.

Correlação linear e espacial entre o rendimento de grãos do feijoeiro e a resistência mecânica à penetração em um Latossolo Vermelho distrófico

A resistência mecânica à penetração apresentada pelo solo exerce grande influência sobre o desenvolvimento vegetal, uma vez que o crescimento das raízes, assim como o rendimento das culturas, varia de forma inversamente proporcional ao seu valor. No ano agrícola de 2001/2002, na Fazenda Experimental de Ensino e Pesquisa da Faculdade de Engenharia/UNESP - Campus de Ilha Solteira, foram analisados o rendimento de grãos do feijoeiro (PG) e a resistência mecânica à penetração (R), de um Latossolo Vermelho distrófico. O objetivo foi apurar diretrizes relacionadas com o aumento da produtividade agrícola em questão, estudando a correlação linear e a espacial entre a PG e a R. Foi instalada uma rede geoestatística para a coleta dos dados do solo e da planta, estabelecida com espaçamentos de 5 x 5 m e 2,5 x 2,5 m, que continham 120 pontos amostrais distribuídos numa área de 1.875 m². A correlação linear entre a PG e a R foi praticamente nula, uma vez que, dependendo das profundidades estudadas do solo, apresentou coeficientes de correlação (r) menores do que 0,20. A análise geoestatística apresentou boa estrutura de dependência espacial, tanto para a PG quanto para a R, quando analisadas isoladamente. Entretanto, a análise espacial conjunta de tais atributos apresentou-se inconsistente. Assim, com o aumento da resistência mecânica à penetração, em determinada região do solo ocorreu ora aumento, ora diminuição do rendimento de grãos do feijoeiro.

Super-resolution of remotely sensed images with variable-pixel linear reconstruction

This paper describes the development and applications of a super-resolution method, known as Super-Resolution Variable-Pixel Linear Reconstruction. The algorithm works combining different lower resolution images in order to obtain, as a result, a higher resolution image. We show that it can make significant spatial resolution improvements to satellite images of the Earth¿s surface allowing recognition of objects with size approaching the limiting spatial resolution of the lower resolution images. The algorithm is based on the Variable-Pixel Linear Reconstruction algorithm developed by Fruchter and Hook, a well-known method in astronomy but never used for Earth remote sensing purposes. The algorithm preserves photometry, can weight input images according to the statistical significance of each pixel, and removes the effect of geometric distortion on both image shape and photometry. In this paper, we describe its development for remote sensing purposes, show the usefulness of the algorithm working with images as different to the astronomical images as the remote sensing ones, and show applications to: 1) a set of simulated multispectral images obtained from a real Quickbird image; and 2) a set of multispectral real Landsat Enhanced Thematic Mapper Plus (ETM+) images. These examples show that the algorithm provides a substantial improvement in limiting spatial resolution for both simulated and real data sets without significantly altering the multispectral content of the input low-resolution images, without amplifying the noise, and with very few artifacts.