Research Experiences for Undergraduates (REU)-Project Presentations

Research Experiences for Undergraduates (REU)

"Cooption and Catalysis in a Model of Technological Evolution"

Eric Scott, Andrews University

Cooptive phenomena lie at the heart of the evolution of complex functions in nature and engineering, where solutions adapted for one problem are retooled to solve another, related problem. We explore the dynamics of a model of combinatorially evolving logic circuits developed by Brian Arthur and Wolfgang Polak, and identify cooption potential of various functions under a battery of fitness niches. We also measure the effect of evolving circuits under different multiobjective environments, identifying catalytic effects between niches.

Mentor: J. Doyne Farmer

"Cosmopolitan Ancestors: Simulations Calibrated with Genetic and Ethnographic Data Show that Prehistoric Populations Were Not Small and Isolated"

Stefany M. Gomez, Universidad de Los Andes and Universidad Sergio Arboleda

A widely held view is that our hunter gatherer ancestors lived in closed worlds, their interactions, limited to just a small number of close family or lifelong associates. However, the extent of genetic differentiation (Wright’s FST) in populations which are likely to have had population structures and characteristics similar to our ancestors suggests that this idea is incorrect. Under idealized assumptions in which only random migration and small group size are affecting the degree of genetic differentiation among groups, we show that the observed FST values could, indeed, be produced by small and isolated populations. However, when we introduce empirically plausible deviations from the idealized assumptions -reproductive skew, population crashes, single propagule recolonization processes, linage-based group fission and non-random migration- that reflect human social structure and social processes during the Pleistocene, our simulations indicate that the observed FST values could not be produced by small and isolated populations but are consistent only with large and cosmopolitan ones.

Mentors: Samuel Bowles and Jon Wilkins

"Fluctuations and Asymmetries in Financial Market Microstructure"

Aaron Miller, University of New Mexico

In this paper I investigate the asymmetries and changes that occur in financial market microstructure. Using data from the London Stock Exchange, I analyze the response and impact of individual transactions conditioned on the sign of the trade. I also determine the effect that tick size changes have on microstructural dynamics.

Mentor: J. Doyne Farmer

"The Statistical Characteristics of Urban Indicators"

Nathaniel Rodriguez, University of Redlands

Many characteristics of cities, such as income, patent creation, and violent crime, scale with population according to universal scaling laws. These laws are a good description of the general trends in these urban indicators, but there are also other underlying structures in the dynamics of cities such as their indicators exhibiting long term memory and their universal statistical behavior. We have been exploring the statistical behavior of urban indicators and their deviation from their power-laws to show that they behave similarly over time and over multiple indicators and nations. We also find that the indicators of these cities follow the same type of statistical deviation from the power-law and that the power-laws of various nations for a quantity can be collapsed to follow a single line. This shows that regardless of city size or location, indicators share some very basic rules and statistics even though cities have diverse histories and exist in very different environments.

Mentor: Luis Bettencourt

"Disease Dynamics in Hive Populations"

Amalie McKee, Case Western Reserve

Colony Collapse Disorder has drawn attention to just how dependent we are on pollinators. However, while we are still trying to figure out what pathogen might cause the phenomenon, the dynamics and spread are still widely unknown.

We adapt the traditional SIR model for malaria ecology to model disease dynamics in a pollinator species. We then examine potential treatments, looking for a method of treatment that will enable hive survival and examining changes in long term behavior.

Mentors: Jeremy Van Cleve and Jennifer Dunne

"Developing Lexicons in a Continuous Meaning Space"

Avril Kenney, Massachusetts Institute of Technology

When people are acquiring language, it is not always clear from context which words refer to which objects, and the examples they see for any particular word will not all be the same. Previous approaches to the problem of learning or building a lexicon have characterized it as creating a mapping between a fixed set of words and a fixed set of meanings. I will describe simulations of lexicon development using an agent-based model in which word-meanings are distributions over a continuous feature space; agents communicate about objects and infer the meanings of words based on the example objects they see. Agents in the model are able to develop a shared lexicon, and the meanings they reach are efficient given what objects tend to be present. Even when the objects are entirely random, the lexicons that develop tend to result in a near-optimal probability of communicative success. If new agents are being introduced into the population, the lexicon will continue to change, and will have periods of stability punctuated by periods of fluctuation.

Mentor: Eric Smith

slides

"Adapting to Non-Stationarity with Growing Predictor Ensembles"

Abigail Jacobs, Northwestern University

Forecasting sequences by expert ensembles generally assumes stationary or near-stationary processes; however, in complex systems and many real-world applications, we are frequently confronted with non-stationarities, including both abrupt and gradual changes in distribution. We present an algorithm for forecasting non-stationary time series by combining predictions of a growing ensemble of models, adding new models as new data becomes available. Our approach modifies the exponentially weighted average forecaster (Littlestone & Warmuth, 1994) and fixed shares forecaster (Helmbold & Warmuth, 1998) to let the ensemble models grow, but retains the property of performing almost as well as an oracle which knows the optimal sequence of models to use. Additionally, we relate this to recent work in sequential anomaly detection using exponential-family models (Raginsky, et al., 2010) and to the larger context of universal prediction.

Helmbold, D. P. and Warmuth, M. Tracking the Best Expert. Machine Learning, 32(2):151-178, 1998.

Littlestone, N. and Warmuth, M. The weighted majority algorithm. Information and Computation, 108:212-261, 1994.

Raginsky, M., Willett, R., Horn, C., Silva, J., & Marcia, R. Sequential anomaly detection in the presence of noise and limited feedback. IEEE Transactions on Information Theory, 2010. Submitted. arXiv:0901.2904.

Mentors: Cosma Shalizi & Aaron Clauset

"The Proving Ground: Adaptation and Learning in Blotto Games"

Elais Jackson, Tennessee State University

Blotto is a class of two-person zero-sum games where colonels are tasked to simultaneously allocate troops over a number of battlefronts. The game, first proposed by Borel(1921) and later refined by Gross and Wagner(1950), has several applications to military, business, and political problems that arise in the real world. However, as the number of troops or battlefronts increase, the game's complexity also increases which makes equilibria harder to find. In this paper, I show that equilibria can be found more easily by playing a large number of games. To do this, continuing with the military theme, I construct a model of a repeating Blotto game consisting of two players representing colonels who are given troops to allocate across a given number of battlefronts based on predetermined strategies. In each game, the colonels add weight to the strategies they use and eventually they converge on optimal strategies. This research shows that using a simple learning technique, optimal strategies can be found computationally in addition to the purely mathematical methods already used in the literature.

Mentor: John Miller

"Mutational Robustness and Automatic Program Repair"

Ethan Fast, University of Virginia

Mutational robustness describes how likely a variant's phenotype is to remain constant in response to mutations applied within its genotype. This measure has not been evaluated generally across software, nor more specifically in the context of a genetic programming (GP) approach to automated program repair. We provide an analysis of this metric across eight benchmark programs, representing each program's genotype as an AST, and each phenotype with a regression test suite. First, we quantify the robustness of these programs, with respect to the mutational operators used in existing GP program repair methods, and analyze the extent that these results can be applied to software more broadly. Next, we evaluate the relationship between program robustness and repair success in existing GP techniques. Finally, we identify a class of program faults which inhibit robustness under current repair methods, and propose changes in variant representation under GP that enable the repair of these more difficult bugs.

Mentor: Stephanie Forrest

Slides (if you want to actually see the arrows) Robustness.pdf