Mateda-2.0: Estimation of Distribution Algorithms in MATLAB

This paper describes Mateda-2.0, a MATLAB package for estimation of distribution algorithms (EDAs). This package can be used to solve single and multi-objective discrete and continuous optimization problems using EDAs based on undirected and directed probabilistic graphical models. The implementation contains several methods commonly employed by EDAs. It is also conceived as an open package to allow users to incorporate different combinations of selection, learning, sampling, and local search procedures. Additionally, it includes methods to extract, process and visualize the structures learned by the probabilistic models. This way, it can unveil previously unknown information about the optimization problem domain. Mateda-2.0 also incorporates a module for creating and validating function models based on the probabilistic models learned by EDAs.

Efficient learning of decomposable models with a bounded clique size

The learning of probability distributions from data is a ubiquitous problem in the fields of Statistics and Artificial Intelligence. During the last decades several learning algorithms have been proposed to learn probability distributions based on decomposable models due to their advantageous theoretical properties. Some of these algorithms can be used to search for a maximum likelihood decomposable model with a given maximum clique size, k, which controls the complexity of the model. Unfortunately, the problem of learning a maximum likelihood decomposable model given a maximum clique size is NP-hard for k > 2. In this work, we propose a family of algorithms which approximates this problem with a computational complexity of O(k · n^2 log n) in the worst case, where n is the number of implied random variables. The structures of the decomposable models that solve the maximum likelihood problem are called maximal k-order decomposable graphs. Our proposals, called fractal trees, construct a sequence of maximal i-order decomposable graphs, for i = 2, ..., k, in k − 1 steps. At each step, the algorithms follow a divide-and-conquer strategy based on the particular features of this type of structures. Additionally, we propose a prune-and-graft procedure which transforms a maximal k-order decomposable graph into another one, increasing its likelihood. We have implemented two particular fractal tree algorithms called parallel fractal tree and sequential fractal tree. These algorithms can be considered a natural extension of Chow and Liu’s algorithm, from k = 2 to arbitrary values of k. Both algorithms have been compared against other efficient approaches in artificial and real domains, and they have shown a competitive behavior to deal with the maximum likelihood problem. Due to their low computational complexity they are especially recommended to deal with high dimensional domains.

Problems when generating virtual models representing real objects: Hondarribia walls

[EN] This paper is based in the following project:

Applying hedonic property models in the planning and evaluation of shoreline management

According to the Millennium Ecosystem Assessment’s chapter “Coastal Systems” (Agardy and Alder 2005), 40% of the world population falls within 100 km of the coast. Agardy and Alder report that population densities in coastal regions are three times those of inland regions and demographic forecasts suggest a continued rise in coastal populations. These high population levels can be partially traced to the abundance of ecosystem services provided in the coastal zone. While populations benefit from an abundance of services, population pressure also degrades existing services and leads to increased susceptibility of property and human life to natural hazards. In the face of these challenges, environmental administrators on the coast must pursue agendas which reflect the difficult balance between private and public interests. These decisions include maintaining economic prosperity and personal freedoms, protecting or enhancing the existing flow of ecosystem services to society, and mitigating potential losses from natural hazards. (PDF contains 5 pages)

Searches for new symmetries in pp collisions with the razor kinematic variables at √s = 7 TeV

The construction and LHC phenomenology of the razor variables M_R, an event-by-event indicator of the heavy particle mass scale, and R, a dimensionless variable related to the transverse momentum imbalance of events and missing transverse energy, are presented.  The variables are used  in the analysis of the first proton-proton collisions dataset at CMS  (35 pb^-1) in a search for superpartners of the quarks and gluons, targeting indirect hints of dark matter candidates in the context of supersymmetric theoretical frameworks. The analysis produced the highest sensitivity results for SUSY to date and extended the LHC reach far beyond the previous Tevatron results.  A generalized inclusive search is subsequently presented for new heavy particle pairs produced in √s = 7 TeV proton-proton collisions at the LHC using 4.7±0.1 fb^-1 of integrated luminosity from the second LHC run of 2011.  The selected events are analyzed in the 2D razor-space of M_R and R and the analysis is performed in 12 tiers of all-hadronic, single and double leptons final states in the presence and absence of b-quarks, probing the third generation sector using the event heavy-flavor content.   The search is sensitive to generic supersymmetry models with minimal assumptions about the superpartner decay chains. No excess is observed in the number or shape of event yields relative to Standard Model predictions. Exclusion limits are derived in the CMSSM framework with  gluino masses up to 800 GeV and squark masses up to 1.35 TeV excluded at 95% confidence level, depending on the model parameters. The results are also interpreted for a collection of simplified models, in which gluinos are excluded with masses as large as 1.1 TeV, for small neutralino masses, and the first-two generation squarks, stops and sbottoms are excluded for masses up to about 800, 425 and 400 GeV, respectively.

With the discovery of a new boson by the CMS and ATLAS experiments in the γ-γ and 4 lepton final states, the identity of the putative Higgs candidate must be established through the measurements of its properties. The spin and quantum numbers are of particular importance, and we describe a method for measuring the J^PC of this particle using the observed signal events in the H to ZZ^* to 4 lepton channel developed before the discovery. Adaptations of the razor kinematic variables are introduced for the H to WW^* to 2 lepton/2 neutrino channel, improving the resonance mass resolution and increasing the discovery significance. The prospects for incorporating this channel in an examination of the new boson J^PC is discussed, with indications that this it could provide complementary information to the H to ZZ^* to 4 lepton final state, particularly for measuring CP-violation in these decays.

New directions in sparse sampling and estimation for underdetermined systems

A central objective in signal processing is to infer meaningful information from a set of measurements or data. While most signal models have an overdetermined structure (the number of unknowns less than the number of equations), traditionally very few statistical estimation problems have considered a data model which is underdetermined (number of unknowns more than the number of equations). However, in recent times, an explosion of theoretical and computational methods have been developed primarily to study underdetermined systems by imposing sparsity on the unknown variables. This is motivated by the observation that inspite of the huge volume of data that arises in sensor networks, genomics, imaging, particle physics, web search etc., their information content is often much smaller compared to the number of raw measurements. This has given rise to the possibility of reducing the number of measurements by down sampling the data, which automatically gives rise to underdetermined systems.

In this thesis, we provide new directions for estimation in an underdetermined system, both for a class of parameter estimation problems and also for the problem of sparse recovery in compressive sensing. There are two main contributions of the thesis: design of new sampling and statistical estimation algorithms for array processing, and development of improved guarantees for sparse reconstruction by introducing a statistical framework to the recovery problem.

We consider underdetermined observation models in array processing where the number of unknown sources simultaneously received by the array can be considerably larger than the number of physical sensors. We study new sparse spatial sampling schemes (array geometries) as well as propose new recovery algorithms that can exploit priors on the unknown signals and unambiguously identify all the sources. The proposed sampling structure is generic enough to be extended to multiple dimensions as well as to exploit different kinds of priors in the model such as correlation, higher order moments, etc.

Recognizing the role of correlation priors and suitable sampling schemes for underdetermined estimation in array processing, we introduce a correlation aware framework for recovering sparse support in compressive sensing. We show that it is possible to strictly increase the size of the recoverable sparse support using this framework provided the measurement matrix is suitably designed. The proposed nested and coprime arrays are shown to be appropriate candidates in this regard. We also provide new guarantees for convex and greedy formulations of the support recovery problem and demonstrate that it is possible to strictly improve upon existing guarantees.

This new paradigm of underdetermined estimation that explicitly establishes the fundamental interplay between sampling, statistical priors and the underlying sparsity, leads to exciting future research directions in a variety of application areas, and also gives rise to new questions that can lead to stand-alone theoretical results in their own right.

Efficient methods for empirical tests of behavioral economics theories in laboratory and field experiments

In the quest for a descriptive theory of decision-making, the rational actor model in economics imposes rather unrealistic expectations and abilities on human decision makers. The further we move from idealized scenarios, such as perfectly competitive markets, and ambitiously extend the reach of the theory to describe everyday decision making situations, the less sense these assumptions make. Behavioural economics has instead proposed models based on assumptions that are more psychologically realistic, with the aim of gaining more precision and descriptive power. Increased psychological realism, however, comes at the cost of a greater number of parameters and model complexity. Now there are a plethora of models, based on different assumptions, applicable in differing contextual settings, and selecting the right model to use tends to be an ad-hoc process. In this thesis, we develop optimal experimental design methods and evaluate different behavioral theories against evidence from lab and field experiments.

We look at evidence from controlled laboratory experiments. Subjects are presented with choices between monetary gambles or lotteries. Different decision-making theories evaluate the choices differently and would make distinct predictions about the subjects' choices. Theories whose predictions are inconsistent with the actual choices can be systematically eliminated. Behavioural theories can have multiple parameters requiring complex experimental designs with a very large number of possible choice tests. This imposes computational and economic constraints on using classical experimental design methods. We develop a methodology of adaptive tests: Bayesian Rapid Optimal Adaptive Designs (BROAD) that sequentially chooses the "most informative" test at each stage, and based on the response updates its posterior beliefs over the theories, which informs the next most informative test to run. BROAD utilizes the Equivalent Class Edge Cutting (EC²) criteria to select tests. We prove that the EC² criteria is adaptively submodular, which allows us to prove theoretical guarantees against the Bayes-optimal testing sequence even in the presence of noisy responses. In simulated ground-truth experiments, we find that the EC² criteria recovers the true hypotheses with significantly fewer tests than more widely used criteria such as Information Gain and Generalized Binary Search. We show, theoretically as well as experimentally, that surprisingly these popular criteria can perform poorly in the presence of noise, or subject errors. Furthermore, we use the adaptive submodular property of EC² to implement an accelerated greedy version of BROAD which leads to orders of magnitude speedup over other methods.

We use BROAD to perform two experiments. First, we compare the main classes of theories for decision-making under risk, namely: expected value, prospect theory, constant relative risk aversion (CRRA) and moments models. Subjects are given an initial endowment, and sequentially presented choices between two lotteries, with the possibility of losses. The lotteries are selected using BROAD, and 57 subjects from Caltech and UCLA are incentivized by randomly realizing one of the lotteries chosen. Aggregate posterior probabilities over the theories show limited evidence in favour of CRRA and moments' models. Classifying the subjects into types showed that most subjects are described by prospect theory, followed by expected value. Adaptive experimental design raises the possibility that subjects could engage in strategic manipulation, i.e. subjects could mask their true preferences and choose differently in order to obtain more favourable tests in later rounds thereby increasing their payoffs. We pay close attention to this problem; strategic manipulation is ruled out since it is infeasible in practice, and also since we do not find any signatures of it in our data.

In the second experiment, we compare the main theories of time preference: exponential discounting, hyperbolic discounting, "present bias" models: quasi-hyperbolic (α, β) discounting and fixed cost discounting, and generalized-hyperbolic discounting. 40 subjects from UCLA were given choices between 2 options: a smaller but more immediate payoff versus a larger but later payoff. We found very limited evidence for present bias models and hyperbolic discounting, and most subjects were classified as generalized hyperbolic discounting types, followed by exponential discounting.

In these models the passage of time is linear. We instead consider a psychological model where the perception of time is subjective. We prove that when the biological (subjective) time is positively dependent, it gives rise to hyperbolic discounting and temporal choice inconsistency.

We also test the predictions of behavioral theories in the "wild". We pay attention to prospect theory, which emerged as the dominant theory in our lab experiments of risky choice. Loss aversion and reference dependence predicts that consumers will behave in a uniquely distinct way than the standard rational model predicts. Specifically, loss aversion predicts that when an item is being offered at a discount, the demand for it will be greater than that explained by its price elasticity. Even more importantly, when the item is no longer discounted, demand for its close substitute would increase excessively. We tested this prediction using a discrete choice model with loss-averse utility function on data from a large eCommerce retailer. Not only did we identify loss aversion, but we also found that the effect decreased with consumers' experience. We outline the policy implications that consumer loss aversion entails, and strategies for competitive pricing.

In future work, BROAD can be widely applicable for testing different behavioural models, e.g. in social preference and game theory, and in different contextual settings. Additional measurements beyond choice data, including biological measurements such as skin conductance, can be used to more rapidly eliminate hypothesis and speed up model comparison. Discrete choice models also provide a framework for testing behavioural models with field data, and encourage combined lab-field experiments.

Hunting spectro-temporal information in unevenly spaced paleoclimate time series

18 p.

The search for gravitational waves from the coalescence of black hole binary systems in data from the LIGO and Virgo detectors. Or: A dark walk through a random forest

The LIGO and Virgo gravitational-wave observatories are complex and extremely sensitive strain detectors that can be used to search for a wide variety of gravitational waves from astrophysical and cosmological sources. In this thesis, I motivate the search for the gravitational wave signals from coalescing black hole binary systems with total mass between 25 and 100 solar masses. The mechanisms for formation of such systems are not well-understood, and we do not have many observational constraints on the parameters that guide the formation scenarios. Detection of gravitational waves from such systems — or, in the absence of detection, the tightening of upper limits on the rate of such coalescences — will provide valuable information that can inform the astrophysics of the formation of these systems. I review the search for these systems and place upper limits on the rate of black hole binary coalescences with total mass between 25 and 100 solar masses. I then show how the sensitivity of this search can be improved by up to 40% by the the application of the multivariate statistical classifier known as a random forest of bagged decision trees to more effectively discriminate between signal and non-Gaussian instrumental noise. I also discuss the use of this classifier in the search for the ringdown signal from the merger of two black holes with total mass between 50 and 450 solar masses and present upper limits. I also apply multivariate statistical classifiers to the problem of quantifying the non-Gaussianity of LIGO data. Despite these improvements, no gravitational-wave signals have been detected in LIGO data so far. However, the use of multivariate statistical classification can significantly improve the sensitivity of the Advanced LIGO detectors to such signals.

Informazio-iturrien garrantzia berrikuntza teknologikoko jardueretarako

[EU]Gaur egunean bizi dugun krisi ekonomiko, produkzio ereduen transformazio eta globalizazioko testuinguruan, ikerketa, garapena eta berrikuntza (I+G+b) ezinbesteko faktoreak bilakatu dira herrialdeen hazkunde eta enpresen lidergo zein biziraupenerako. Berritasunaren bilatze horretan, egungo merkatuan enpresek etengabe egin beharreko egokitzapen teknologikoak direla eta, berrikuntza teknologikoak, hau da, produktuan edo prozesuan berritzeak, berebiziko garrantzia du. Gainera, oro har, lehiakortasunik ez galtzeko informazio estrategikoaren jabe izatea enpresentzat funtsezkoa bada ere, berrikuntza jarduerak aurrera eramateko oraindik ere gailentasun handiagoa dauka. Informazio estrategikoa iturri ezberdinetatik jaso daiteke eta horietako bakoitzari ematen zaion garrantzia ezberdina da. Lan honen helburua erlazio hori aztertzearena izanik, ondoriozta dezakegu, alde batetik, produktuan zein prozesuan berritzen duten enpresek, berrikuntza teknologikoak aurrera eramateko garaian, enpresa barnetik jasotako informazioari ematen diotela garrantzi gehien. Eta bestaldetik, instituzio publikoetatik, hau da, unibertsitate edo goi-ikasketetako zentroetatik, ikerketako erakunde publikoetatik edota zentro teknologikoetatik jasotako informazioari garrantzi gutxi ematen zaiola.

As finanças públicas e a sociedade: um estudo de caso dos gastos em educação dos municípios da região metropolitana do Estado do Rio de Janeiro no período de 2004 a 2008

O objetivo desta pesquisa acadêmica é o de compreender os aspectos que envolvem os gastos com educação dos municípios que compõe a região metropolitana do Estado do Rio de Janeiro no período de 2004 a 2008, através do estudo da sua aplicação e dos aspectos que envolvem a sociedade. Apesar do acesso às informações financeiras dos entes governamentais serem disponibilizada mediante a atuação das finanças públicas, dando cumprimento às diferentes normas legais, a necessidade de tornar transparente o patrimônio público insere a um percepção por uma demanda por modelos de indicadores que evidenciem o controle dos gastos públicos. Desta forma, pretende-se entender as relações e características que envolvem tais informações e aguça a atenção em melhor conhecê-las. A análise de diferenciados aspectos governamentais, legais e socioambiental que afetam os gastos públicos em educação dos municípios que ocupam a região metropolitana do Estado do Rio de Janeiro, impondo aos entes governamentais algumas das responsabilidades que são compartilhadas pela população, legisladores e administradores. O conhecimento dos padrões de comportamento dos envolvidos nesta relação traz esclarecimentos úteis, como fundamentais, para o planejamento e o controle a curto e longo prazo. Ao desenvolver a pesquisa bibliográfica, esta requereu uma revisão das obras literárias e nas experiências e vivências nelas contidas para satisfazer a curiosidade crítica que propelia a pesquisa. A discussão precedente das análises efetuadas neste estudo mostrou a ampla possibilidade em ressaltar-se que compreender e acompanhar os gastos públicos em educação e a elaboração de indicadores de percepção dos gastos públicos representa papel de suma importância ao exercício democrático de fiscalização do poder público pela sociedade.