An inequality for uniform deviations of sample averages from their means

We derive a new inequality for uniform deviations of averages from their means. The inequality is a common generalization of previous results of Vapnik and Chervonenkis (1974) and Pollard (1986). Usingthe new inequality we obtain tight bounds for empirical loss minimization learning.

A sharp concentration inequality with applications

We present a new general concentration-of-measure inequality and illustrate its power by applications in random combinatorics. The results find direct applications in some problems of learning theory.

Pattern recognition theory in nonlinear signal processing

A body of research has developed within the context of nonlinear signal and image processing that deals with the automatic, statistical design of digital window-based filters. Based on pairs of ideal and observed signals, a filter is designed in an effort to minimize the error between the ideal and filtered signals. The goodness of an optimal filter depends on the relation between the ideal and observed signals, but the goodness of a designed filter also depends on the amount of sample data from which it is designed. In order to lessen the design cost, a filter is often chosen from a given class of filters, thereby constraining the optimization and increasing the error of the optimal filter. To a great extent, the problem of filter design concerns striking the correct balance between the degree of constraint and the design cost. From a different perspective and in a different context, the problem of constraint versus sample size has been a major focus of study within the theory of pattern recognition. This paper discusses the design problem for nonlinear signal processing, shows how the issue naturally transitions into pattern recognition, and then provides a review of salient related pattern-recognition theory. In particular, it discusses classification rules, constrained classification, the Vapnik-Chervonenkis theory, and implications of that theory for morphological classifiers and neural networks. The paper closes by discussing some design approaches developed for nonlinear signal processing, and how the nature of these naturally lead to a decomposition of the error of a designed filter into a sum of the following components: the Bayes error of the unconstrained optimal filter, the cost of constraint, the cost of reducing complexity by compressing the original signal distribution, the design cost, and the contribution of prior knowledge to a decrease in the error. The main purpose of the paper is to present fundamental principles of pattern recognition theory within the framework of active research in nonlinear signal processing.

Decision boundary for discrete Bayesian network classifiers

Bayesian network classifiers are a powerful machine learning tool. In order to evaluate the expressive power of these models, we compute families of polynomials that sign-represent decision functions induced by Bayesian network classifiers. We prove that those families are linear combinations of products of Lagrange basis polynomials. In absence of V-structures in the predictor sub-graph, we are also able to prove that this family of polynomials does in- deed characterize the specific classifier considered. We then use this representation to bound the number of decision functions representable by Bayesian network classifiers with a given structure and we compare these bounds to the ones obtained using Vapnik-Chervonenkis dimension.

Decision boundary for discrete Bayesian network classifiers

Bayesian network classifiers are a powerful machine learning tool. In order to evaluate the expressive power of these models, we compute families of polynomials that sign-represent decision functions induced by Bayesian network classifiers. We prove that those families are linear combinations of products of Lagrange basis polynomials. In absence of V-structures in the predictor sub-graph, we are also able to prove that this family of polynomials does in- deed characterize the specific classifier considered. We then use this representation to bound the number of decision functions representable by Bayesian network classifiers with a given structure and we compare these bounds to the ones obtained using Vapnik-Chervonenkis dimension.

The exact sample complexity of PAC-learning problems with unit VC dimension

The Vapnik-Chervonenkis (VC) dimension is a combinatorial measure of a certain class of machine learning problems, which may be used to obtain upper and lower bounds on the number of training examples needed to learn to prescribed levels of accuracy. Most of the known bounds apply to the Probably Approximately Correct (PAC) framework, which is the framework within which we work in this paper. For a learning problem with some known VC dimension, much is known about the order of growth of the sample-size requirement of the problem, as a function of the PAC parameters. The exact value of sample-size requirement is however less well-known, and depends heavily on the particular learning algorithm being used. This is a major obstacle to the practical application of the VC dimension. Hence it is important to know exactly how the sample-size requirement depends on VC dimension, and with that in mind, we describe a general algorithm for learning problems having VC dimension 1. Its sample-size requirement is minimal (as a function of the PAC parameters), and turns out to be the same for all non-trivial learning problems having VC dimension 1. While the method used cannot be naively generalised to higher VC dimension, it suggests that optimal algorithm-dependent bounds may improve substantially on current upper bounds.

Narrowing socioeconomic inequality in child stunting: the Brazilian experience, 1974–2007

Objective To assess trends in the prevalence and social distribution of child stunting in Brazil to evaluate the effect of income and basic service redistribution policies implemented in that country in the recent past. Methods The prevalence of stunting (height-for-age z score below \22122 using the Child Growth Standards of the World Health Organization) among children aged less than 5 years was estimated from data collected during national household surveys carried out in Brazil in 1974\201375 (n = 34 409), 1989 (n = 7374), 1996 (n = 4149) and 2006\201307 (n = 4414). Absolute and relative socioeconomic inequality in stunting was measured by means of the slope index and the concentration index of inequality, respectively. Findings Over a 33-year period, we documented a steady decline in the national prevalence of stunting from 37.1 per cent to 7.1 per cent. Prevalence dropped from 59.0 per cent to 11.2 per cent in the poorest quintile and from 12.1 per cent to 3.3 per cent among the wealthiest quintile. The decline was particularly steep in the last 10 years of the period (1996 to 2007), when the gaps between poor and wealthy families with children under 5 were also reduced in terms of purchasing power; access to education, health care and water and sanitation services; and reproductive health indicators.Conclusion In Brazil, socioeconomic development coupled with equity-oriented public policies have been accompanied by marked improvements in living conditions and a substantial decline in child undernutrition, as well as a reduction of the gap in nutritional status between children in the highest and lowest socioeconomic quintiles. Future studies will show whether these gains will be maintained under the current global economic crisis

Non-Spatial Government Policies and Regional Income Inequality in Brazil

Silveira Neto R. Da M. and Azzoni C. R. Non-spatial government policies and regional income inequality in Brazil, Regional Studies. This paper uses both macro- and micro-data to analyse the role of social programmes in the recent reduction in Brazilian regional income inequality. Convergence indicators are presented for different sources of regional income in the period 1995-2006. A decomposition of the Gini indicator allows the identification of the role of each of these income sources with respect to the reduction of regional inequality during the period. The results point out that both labour productivity and government non-spatial policies - mainly minimum wage changes and income transference programmes - do have a role in explaining regional inequality reduction during the period. [image omitted] Silveira Neto R. Da M. et Azzoni C. R. Les politiques gouvernementales non-spatiales et l`ecart des revenus regionaux au Bresil, Regional Studies. Cet article emploie des donnees a la fois macroeconomiques et microeconomiques afin d`analyser le role des programmes d`actions sociales quant a la baisse recente de l`ecart des revenus regionaux au Bresil. On presente des indicateurs de convergence pour diverses sources des revenus regionaux pour la periode allant de 1995 a 2006. Une decomposition du coefficient de Gini permet d`identifier le role de chacune de ces sources des revenus par rapport a la baisse de l`ecart des revenus pendant cette periode. Les resultats indiquent que la productivite du travail et les politiques gouvernementales non-spatiales - notamment la modification du salaire minimum et les programmes visant le transfert des revenus - ont un role a jouer pour expliquer la baisse de l`ecart des revenus regionaux pendant la periode en question. Convergence Productivite du travail Transfert des revenus Salaire minimum Effets spatiaux des politiques non-spatiales Silveira Neto R. Da M. und Azzoni C. R. Nicht raumliche Regierungspolitiken und das regionale Einkommensungleichgewicht in Brasilien, Regional Studies. In diesem Beitrag analysieren wir mit Hilfe von Makro- und Mikrodaten die Rolle von sozialen Programmen bei der unlangst erzielten Verringerung des regionalen Einkommensungleichgewichts in Brasilien. Wir stellen Konvergenz-Indikatoren fur verschiedene regionale Einkommensquellen im Zeitraum von 1995 bis 2006 vor. Eine Dekomposition des Gini-Indikators ermoglicht die Identifizierung der jeweiligen Rolle dieser Einkommensquellen fur die Verringerung des regionalen Ungleichgewichts im betreffenden Zeitraum. Die Ergebnisse weisen darauf hin, dass sowohl die Produktivitat der Arbeitskrafte als auch die nicht raumlichen Regierungspolitiken - in erster Linie Veranderungen beim Mindestlohn und Programme fur Einkommenstransfers - als Grunde fur die Verringerung des regionalen Ungleichgewichts in dieser Periode durchaus eine Rolle spielen. Konvergenz Arbeitsproduktivitat Einkommenstransfer Mindestlohn Raumliche Auswirkungen nicht raumlicher Politiken Silveira Neto R. Da M. y Azzoni C. R. Politicas gubernamentales no espaciales y desigualdades de ingresos regionales en Brasil, Regional Studies. En este articulo utilizamos datos macro y micro para analizar el papel de los programas sociales en la reciente reduccion en las desigualdades de ingresos regionales de Brasil. Presentamos los indicadores de convergencia para diferentes fuentes de ingresos regionales en el periodo de 1995 a 2006. Una descomposicion del indice Gini permite identificar el papel de cada una de estas fuentes de ingresos con respecto a la reduccion de las desiguadades regionales durante este periodo. Los resultados destacan que tanto la productividad laboral como las politicas no espaciales del gobierno - principalmente los cambios de salario minimo y los programas de transferencias de ingresos - desempenan una funcion a la hora de explicar la reduccion de las desigualdades regionales durante este periodo. Convergencia Productividad laboral Transferencias de ingresos Salario minimo Efectos espaciales de politicas no espaciales.

Income inequality and pecuniary crimes

This paper verifies the relationship between income inequality and pecuniary crimes. The elasticity of pecuniary crimes relative to inequality is 1.46, corroborating previous literature. Other factors important to decrease criminality are expanding job opportunities and a more efficient legal system, (C) 2009 Elsevier B.V. All rights reserved.

Income inequality and male homicide rates: Sao Paulo, Brazil, 1996-2007

In Sao Paulo, Brazil, homicides to men aged 15-44 years increased with an annual percentage change (APC) of 4.7% from 1996 to 2001, and then decreased from 2001 to 2007 with an APC of -14.6%. Analyzing the intra-urban distribution according to family income, the increase in the homicide rate was restricted to men living in the poorest neighbourhoods. In contrast, the decline in homicide rates was observed to men living in all districts. The reasons for this `up and down` trend are not clear.