Human activities can be recognized in sensor data using supervised machine learning algorithms. In this approach, human annotators must annotate events in the sensor data which are used as input to supervised learning algorithms. Annotating events directly in time series graphs of data streams is difficult. Video is often collected and synchronized to the sensor data to aid human annotators in identifying events in the data. Other work in human activity recognition (HAR) minimizes the cost of annotation by using unsupervised or semi-supervised machine learning algorithms or using algorithms that are more tolerant of human annotation errors. Rather than adjusting algorithms, we focus on the performance of the human annotators themselves. Understanding how human annotators perform annotation may lead to annotation interfaces and data collection schemes that better support annotators. We investigate the accuracy and efficiency of human annotators in the context of four HAR tasks when using video, data, or both to annotate events. After a training period, we found that annotators were more efficient when using data alone on three of four tasks and more accurate when marking event types when using video alone on all four tasks. Annotators were more accurate when marking event boundaries using data alone on two tasks and more accurate using video alone on the other two tasks. Our results suggest that data and video collected for annotation of HAR tasks play different roles in the annotation process and these roles may vary with the HAR task.

Text classification is a significant branch of natural language processing, and has many applications including document classification and sentiment analysis.Unsurprisingly, those who do text classification are concerned with the run-time of their algorithms, many of which depend on the size of the corpus' vocabulary due to their bag-of-words representation.Although many studies have examined the effect of preprocessing techniques on vocabulary size and accuracy, none have examined how these methods affect a model's run-time.To fill this gap, we provide a comprehensive study that examines how preprocessing techniques affect the vocabulary size, model performance, and model run-time, evaluating ten techniques over four models and two datasets.We show that some individual methods can reduce run-time with no loss of accuracy, while some combinations of methods can trade 2-5% of the accuracy for up to a 65% reduction of run-time.Furthermore, some combinations of preprocessing techniques can even provide a 15% reduction in run-time while simultaneously improving model accuracy.1

Orion Weller, Jordan Hildebrandt, Ilya Reznik, Christopher Challis, E. Shannon Tass, Quinn Snell, Kevin Seppi. Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics. 2020.

We explore predictability and control in interactive systems where controls are easy to validate. Human-in-the-loop techniques allow users to guide unsupervised algorithms by exposing and supporting interaction with underlying model representations, increasing transparency and promising fine-grained control. However, these models must balance user input and the underlying data, meaning they sometimes update slowly, poorly, or unpredictably---either by not incorporating user input as expected (adherence) or by making other unexpected changes (instability). While prior work exposes model internals and supports user feedback, less attention has been paid to users' reactions when transparent models limit control. Focusing on interactive topic models, we explore user perceptions of control using a study where 100 participants organize documents with one of three distinct topic modeling approaches. These approaches incorporate input differently, resulting in varied adherence, stability, update speeds, and model quality. Participants disliked slow updates most, followed by lack of adherence. Instability was polarizing: some participants liked it when it surfaced interesting information, while others did not. Across modeling approaches, participants differed only in whether they noticed adherence.

Humor is a complicated language phenomenon that depends upon many factors, including topic, date, and recipient. Because of this variation, it can be hard to determine what exactly makes a joke humorous, leading to difficulties in joke identification and related tasks. Furthermore, current humor datasets are lacking in both joke variety and size, with almost all current datasets having less than 100k jokes. In order to alleviate this issue we compile a collection of over 550,000 jokes posted over an 11 year period on the Reddit r/Jokes subreddit (an online forum), providing a large scale humor dataset that can easily be used for a myriad of tasks. This dataset also provides quantitative metrics for the level of humor in each joke, as determined by subreddit user feedback. We explore this dataset through the years, examining basic statistics, most mentioned entities, and sentiment proportions. We also introduce this dataset as a task for future work, where models learn to predict the level of humor in a joke. On that task we provide strong state-of-the-art baseline models and show room for future improvement. We hope that this dataset will not only help those researching computational humor, but also help social scientists who seek to understand popular culture through humor.

To address the lack of comparative evaluation of Human-in-the-Loop Topic Modeling (HLTM) systems, we implement and evaluate three contrasting HLTM modeling approaches using simulation experiments.These approaches extend previously proposed frameworks, including constraints and informed prior-based methods.Users should have a sense of control in HLTM systems, so we propose a control metric to measure whether refinement operations' results match users' expectations.Informed prior-based methods provide better control than constraints, but constraints yield higher quality topics.

Jeffrey Lund, Piper Armstrong, Wilson Fearn, Stephen Cowley, Courtni Byun, Jordan Boyd-Graber, Kevin Seppi. Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics. 2019.

Orion Weller, Kevin Seppi. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). 2019.

This Research Full Paper provides a review of literature regarding the participation of women in Computer Science (CS) related disciplines and discusses four different categories of variables, with the goal of determining what current professors, staff, and students can do to promote the retention and inclusion of female students in CS programs.1)Static attributes of female students (race, socioeconomic background, GPA, ACT/SAT score, etc).2)Adjustable attributes of the female students themselves (qualities that could be changed through workshops, courses, mentoring, or other training programs).3)Static attributes of the environment around female students (location of a university, number of students enrolled, etc).4)Adjustable attributes of the environments around female students (aspects of a program or university like what courses are required and in what order, who is teaching, what they are teaching, how they are teaching, etc).We review literature that suggests departments can attempt to influence attributes of the female students themselves, like students' self efficacy, thinking habits, and academic goals, through courses and programs. We conclude that this category of variables could be split into two ill-defined subcategories. First, variables which may be ethical to adjust, like students' confidence or self efficacy. Second, variables which may be better left unchanged: we note that if interventions lead female students to be more like their male peers, we are not attaining true diversity. We discuss the implications of attempting to change female students and discuss the effectiveness of modifying environments around female students.We take the position that the study of static attributes, whether internal or external to female students, leads to few actionable tasks. We propose that future research should look for adjustable factors that allow for professors, staff, and students to change their actions in order to increase retention rates.

This Research Full Paper presents the results of a longitudinal study about confidence and academic performance conducted at a large, R1, university over the course of a semester. We surveyed male (N = 226) and female (N = 67) students six times throughout the course of the semester and once after final grades were released. Each time, we asked students four questions designed to gauge students' overall confidence. Using a modified latent growth curve analysis, we found distinctively different patterns in confidence trajectories between students in CS-1, CS-2, CS-3, and CS-4; the four consecutive introductory courses. We found that students' confidence tended to show a significant decrease across all confidence variables for all four courses, though some courses showed a stronger decrease than others. We found a similar decline pattern for gender such that males initially reported higher confidence than females, but also showed a steeper decrease in confidence after receiving final grades. This declining trend was also predicted by grades, such that individuals who earned higher grades at the end of the semester initially began the semester with higher confidence, but these individuals also showed a steeper decrease in confidence after receiving their final grades. This work has implications for researchers interested in developing interventions designed to help students gain confidence when they need it most and for those interested in the relationship between confidence and retention.

Particle Swarm Optimization is an effective algorithm because of the combination of the stochastic behavior of particles and the swarm structure. Unfortunately these features also make it difficult to understand the dynamics of PSO. Common methods of analyzing PSO rely on simplifying the algorithm, e.g., assuming stagnation (a state where the swarm ceases finding better solutions) or treating the stochastic factors as constants. In this paper, we expand on earlier work to understand the dynamics of PSO which used input-to-state stability analysis. In particular, we decompose PSO more completely and use the properties of combinations of input-to-state stable components to model convergence at all levels up to and including the entire swarm. This approach allows us to conceptualize the swam as a leader-follower structure and analyze the swarm under a variety of conditions including various fitness functions.

We seek to make physical user interface (PHUI) design more like graphical user interface (GUI) design by using a drag-and drop interface to place widgets, allowing widgets to be repositioned and by hiding implementation details. PHUIs are interfaces built from tangible widgets arranged on the surfaces of physical objects. PHUI layout will become more important as we move from rectangular screens to purpose-built interactive devices. Approaches to PHUI layout based on sculpture make it difficult to reposition widgets, and software approaches do not involve placing widgets on the device exterior. We created PHUI-kit, a software approach to PHUI layout on 3D printed enclosures, which has a drag-and-drop interface, supports repositioning of widgets, and hides implementation details. We describe algorithms for placing widgets on curved surfaces, modifying the enclosure geometry, and routing wiring inside the enclosure. The tool is easy to use and supports a wide range of design possibilities.

Annotated corpora enable supervised machine learning and data analysis. To reduce the cost of manual annotation, tasks are often assigned to internet workers whose judgments are reconciled by crowdsourcing models. We approach the problem of crowdsourcing using a framework for learning from rich prior knowledge, and we identify a family of crowdsourcing models with the novel ability to combine annotations with differing structures: e.g., document labels and word labels. Annotator judgments are given in the form of the predicted expected value of measurement functions computed over annotations and the data, unifying annotation models. Our model, a specific instance of this framework, compares favorably with previous work. Furthermore, it enables active sample selection, jointly selecting annotator, data item, and annotation structure to reduce annotation effort.

We propose Labeled Anchors, an interactive and supervised topic model based on the anchor words algorithm (Arora et al., 2013).Labeled Anchors is similar to Supervised Anchors (Nguyen et al., 2014) in that it extends the vector-space representation of words to include document labels.However, our formulation also admits a classifier which requires no training beyond inferring topics, which means our approach is also fast enough to be interactive.We run a small user study that demonstrates that untrained users can interactively update topics in order to improve classification accuracy.

Human-in-the-loop topic modeling allows users to guide the creation of topic models and to improve model quality without having to be experts in topic modeling algorithms. Prior work in this area has focused either on algorithmic implementation without understanding how users actually wish to improve the model or on user needs but without the context of a fully interactive system. To address this disconnect, we implemented a set of model refinements requested by users in prior work and conducted a study with twelve non-expert participants to examine how end users are affected by issues that arise with a fully interactive, user-centered system. As these issues mirror those identified in interactive machine learning more broadly, such as unpredictability, latency, and trust, we also examined interactive machine learning challenges with non-expert end users through the lens of human-in-the-loop topic modeling. We found that although users experience unpredictability, their reactions vary from positive to negative, and, surprisingly, we did not find any cases of distrust, but instead noted instances where users perhaps trusted the system too much or had too little confidence in themselves.

Recent work in tangible interfaces, including widget sets like .NET Gadgeteer and Phidgets, has enabled prototyping of rich physical interaction at a handheld or tabletop scale. But it remains unclear how participants respond to physical widgets at larger scales. What kinds of interaction would larger widgets enable, and what kinds of systems - if any - can or should be built with them? We built unusually-sized widgets, or "mega-widgets" in order to explore this territory. We present the results of two iterations of building mega-widgets and accompanying user studies designed to help understand participants» reactions to mega-widgets and probe possible applications. Responses indicated, among other things, a correlation between widget size and the perceived size or importance of what it might control. Mega-widgets were also perceived as increasing the precision of user input control and providing a fun and playful element. We hope that knowledge gained from this exploratory work can help lay groundwork for further exploration of widgets at larger scales.

Interactive topic models are powerful tools for understanding large collections of text.However, existing sampling-based interactive topic modeling approaches scale poorly to large data sets.Anchor methods, which use a single word to uniquely identify a topic, offer the speed needed for interactive work but lack both a mechanism to inject prior knowledge and lack the intuitive semantics needed for userfacing applications.We propose combinations of words as anchors, going beyond existing single word anchor algorithmsan approach we call "Tandem Anchors".We begin with a synthetic investigation of this approach then apply the approach to interactive topic modeling in a user study and compare it to interactive and noninteractive approaches.Tandem anchors are faster and more intuitive than existing interactive approaches.

In interactive human-robot path-planning, a capability for expressing the path topology provides a natural mechanism for describing task requirements. We propose a topology-aware RRT∗ algorithm that can explore in parallel any given set of topologies. The topological information used by the algorithm can either be assigned by the human prior to the planning or be selected from the human in posterior path selection. Theoretical analyses and experimental results are given to show that the optimal path of any topology can be found, including a winding topological constraint wherein the robot must circle one or more objects of interest.

Topic modeling is a common tool for understanding large bodies of text, but is typically provided as a “take it or leave it” proposition. Incorporating human knowledge in unsupervised learning is a promising approach to create high-quality topic models. Existing interactive systems and modeling algorithms support a wide range of refinement operations to express feedback. However, these systems’ interactions are primarily driven by algorithmic convenience, ignoring users who may lack expertise in topic modeling. To better understand how non-expert users understand, assess, and refine topics, we conducted two user studies—an in-person interview study and an online crowdsourced study. These studies demonstrate a disconnect between what non-expert users want and the complex, low-level operations that current interactive systems support . In particular, our findings include: (1) analysis of how non-expert users perceive topic models; (2) characterization of primary refinement operations expected by non-expert users and ordered by relative preference; (3) further evidence of the benefits of supporting users in directly refining a topic model; (4) design implications for future human-in-the-loop topic modeling interfaces.

Effective text classification requires experts to annotate data with labels; these training data are time-consuming and expensive to obtain.If you know what labels you want, active learning can reduce the number of labeled documents needed.However, establishing the label set remains difficult.Annotators often lack the global knowledge needed to induce a label set.We introduce ALTO: Active Learning with Topic Overviews, an interactive system to help humans annotate documents: topic models provide a global overview of what labels to create and active learning directs them to the right documents to label.Our forty-annotator user study shows that while active learning alone is best in extremely resource limited conditions, topic models (even by themselves) lead to better label sets, and ALTO's combination is best overall.

We present a method for fabricating prototypes of interactive computing devices from clay sculptures without requiring the designer to be skilled in CAD software. The method creates a "what you sculpt is what you get" process that mimics the "what you see is what you get" processes used in interface design for 2D screens. Our approach uses clay for modeling the basic shape of the device around 3D printed representations, which we call "blanks", of physical interaction widgets such as buttons, sliders, knobs and other electronics. Each blank includes 4 fiducial markers uniquely arranged on a visible surface. After scanning the sculpture, these fiducial marks allow our software to identify widget types and locations in the scanned model. The software then converts the scan into a printable prototype by positioning mounting surfaces, openings for the controls and a splitting plane for assembly. Because the blanks fit in the sculpted shape, they will reliably fit in the interactive prototype. Creating an interactive prototype requires about 30 minutes of human effort for sculpting, and after scanning, involves a single button click to use the process.

In modern text annotation projects, crowdsourced annotations are often aggregated using item response models or by majority vote. Recently, item response models enhanced with generative data models have been shown to yield substantial benefits over those with conditional or no data models. However, suitable generative data models do not exist for many tasks, such as semantic labeling tasks. When no generative data model exists, we demonstrate that similar benefits may be derived by conditionally modeling documents that have been previously embedded in a semantic space using recent work in vector space models. We use this approach to show state-of-the-art results on a variety of semantic annotation aggregation tasks.

Probabilistic models are a useful means for analyzing large text corpora. Integrating such models with human interaction enables many new use cases. However, adding human interaction to probabilistic models requires inference algorithms which are both fast and accurate. We explore the use of Iterated Conditional Modes as a fast alternative to Gibbs sampling or variational EM. We demonstrate superior performance both in run time and model quality on three different models of text including a DP Mixture of Multinomials for web search result clustering, the Interactive Topic Model, and M OM R ESP , a multinomial crowdsourcing model.

An important problem in human-robot interaction is for a human to be able to tell the robot go to a particular location with instructions on how to get there or what to avoid on the way. This paper provides a solution to problems where the human wants the robot not only to optimize some objective but also to honor “soft” or “hard” topological constraints, i.e. “go quickly from A to B while avoiding C”. The paper presents the HARRT* (homotopy-aware RRT*) algorithm, which is a computationally scalable algorithm that a robot can use to plan optimal paths subject to the information provided by the human. The paper provides a theoretic justification for the key property of the algorithm, proposes a heuristic for RRT*, and uses a set of simulation case studies of the resulting algorithm to make a case for why these properties are compatible with the requirements of human-robot interactive path-planning.

Allowing a human to express topological requirements to a robot in language enables untrained users to guide robot movement without requiring the human to understand sophisticated robot algorithms. By using a homotopy class or classes to represent one or more topological requirements, we build a framework that helps a robot understand a human's intent. This paper reviews a homotopic decomposition method that is used to convert any path into a string, which allows homotopic path equivalence to be performed by comparing strings. We then integrate the Homotopic Distributed Correspondence Graph (HoDCG) to infer the homotopic constraint in the format of strings from a language instruction. Finally, we use a homotopic path-planning algorithm that finds the optimal paths for a given objective and homotopic constraint. Experiment results show how a language instruction is converted into a path driven by an implicit topological requirement.

Context.Several empirical studies have explored the benefits of software design patterns, but their collective results are highly inconsistent. Resolving the inconsistencies requires investigating moderators—i.e., variables that cause an effect to differ across contexts.Objectives.Replicate a design patterns experiment at multiple sites and identify sufficient moderators to generalize the results across prior studies.Methods.We perform a close replication of an experiment investigating the impact (in terms of time and quality) of design patterns (Decorator and Abstract Factory) on software maintenance. The experiment was replicated once previously, with divergent results. We execute our replication at four universities—spanning two continents and three countries—using a new method for performing distributed replications based on closely coordinated, small-scale instances (“joint replication”). We perform two analyses: 1) apost-hocanalysis of moderators, based on frequentist and Bayesian statistics; 2) ana priorianalysis of the original hypotheses, based on frequentist statistics.Results.The main effect differs across the previous instances of the experiment and across the sites in our distributed replication. Our analysis of moderators (including developer experience and pattern knowledge) resolves the differences sufficiently to allow for cross-context (and cross-study) conclusions. The final conclusions represent 126 participants from five universities and 12 software companies, spanning two continents and at least four countries.Conclusions.The Decorator pattern is found to be preferable to a simpler solution during maintenance, as long as the developer has at least some prior knowledge of the pattern. For Abstract Factory, the simpler solution is found to be mostly equivalent to the pattern solution. Abstract Factory is shown to require a higher level of knowledge and/or experience than Decorator for the pattern to be beneficial.

Corpus labeling projects frequently use low-cost workers from microtask marketplaces; however, these workers are often inexperienced or have misaligned incentives.Crowdsourcing models must be robust to the resulting systematic and nonsystematic inaccuracies.We introduce a novel crowdsourcing model that adapts the discrete supervised topic model sLDA to handle multiple corrupt, usually conflicting (hence "confused") supervision signals.Our model achieves significant gains over previous work in the accuracy of deduced ground truth.

This paper examines the dynamics of particle swarm optimization (PSO) by modeling PSO as a feedback cascade system and then applying input-to-state stability analysis. Using a feedback cascade system model we can include the effects of the global-best and personal-best values more directly in the model of the dynamics. Thus in contrast to previous study of PSO dynamics, the input-to-state stability property used here allows for the analysis of PSO both before and at stagnation. In addition, the use of input-to-state stability allows this analysis to preserve random terms which were heretofore simplified to constants. This analysis is important because it can inform the setting of PSO parameters and better characterize the nature of PSO as a dynamic system. This work also illuminates the way in which the personal-best and the global-best updates influence the bound on the particle's position and hence, how the algorithm exploits and explores the fitness landscape as a function of the personal best and global best.

Paul Felt, Kevin Black, Eric Ringger, Kevin Seppi, Robbie Haertel. Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. 2015.

Thang Nguyen, Jordan Boyd-Graber, Jeffrey Lund, Kevin Seppi, Eric Ringger. Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. 2015.

From multi-core processors to parallel GPUs to computing clusters, computing resources are increasingly parallel. These parallel resources are being used to address increasingly challenging applications. This presents an opportunity to design optimization algorithms that use parallel processors efficiently. In spite of the intuitively parallel nature of Particle Swarm Optimization (PSO), most PSO variants are not evaluated from a parallel perspective and introduce extra communication and bottlenecks that are inefficient in a parallel environment. We argue that the standard practice of evaluating a PSO variant by reporting function values with respect to the number of function evaluations is inadequate for evaluating PSO in a parallel environment. Evaluating the parallel performance of a PSO variant instead requires reporting function values with respect to the number of iterations to show how the algorithm scales with the number of processors, along with an implementation-independent description of task interactions and communication. Furthermore, it is important to acknowledge the dependence of performance on specific properties of the objective function and computational resources. We discuss parallel evaluation of PSO, and we review approaches for increasing concurrency and for reducing communication which should be considered when discussing the scalability of a PSO variant. This discussion is essential both for designers who are defending the performance of an algorithm and for practitioners who are determining how to apply PSO for a given objective function and parallel environment.

One way for a human and a robot to collaborate on a search task is for the human to specify constraints on the robot's path and then allow the robot to find an optimal path subject to these constraints. This paper presents an anytime solution to the robot's path-planning problem when the human specifies a path constraint and an acceptable amount of deviation from this path. The robot's objective is to maximize information gathered during the search subject to this constraint. We first discretize the path constraint and then convert the resulting problem into a multi-partite graph. Information maximization becomes a submodular orienteering problem on this topology structure. Backtracking is used to generate an efficient heuristic for solving this problem, and an expanding tree is used to facilitate an anytime algorithm.

Particle Swarm Optimization uses noisy historical information to select potentially optimal function samples. Though information-theoretic principles suggest that less noise indicates greater certainty, PSO's momentum term is usually both the least informed and the most deterministic. This dichotomy suggests that while momentum has a profound impact on swarm diversity, it would benefit from a more principled approach. We demonstrate that momentum can be made both more effective and better behaved with informed feedback, and that it may even be completely eliminated with proper application of more straightforward and well-behaved diversity injection strategies.

We formally define multi-capacity bin packing, a generalization of conventional bin packing, and develop an algorithm called Reordering Grouping Genetic Algorithm (RGGA) to assign VMs to servers. We first test RGGA on conventional bin packing problems and show that it yields excellent results but much more efficiently. We then generate a multi-constraint test set, and demonstrate the effectiveness of RGGA in this context. Lastly, we show the applicability of RGGA in its desired context by using it to develop an assignment of real virtual machines to servers.

Bayesian methods are theoretically optimal in many situations. Bayesian model averaging is generally considered the standard model for creating ensembles of learners using Bayesian methods, but this technique is often out-performed by more ad hoc methods in empirical studies. The reason for this failure has important theoretical implications for our understanding of why ensembles work. It has been proposed that Bayesian model averaging struggles in practice because it accounts for uncertainty about which model is correct but still operates under the assumption that only one of them is. In order to more effectively access the benefits inherent in ensembles, Bayesian strategies should therefore be directed more towards model combination rather than the model selection implicit in Bayesian model averaging. This work provides empirical verification for this hypothesis using several different Bayesian model combination approaches tested on a wide variety of classification problems. We show that even the most simplistic of Bayesian model combination strategies outperforms the traditional ad hoc techniques of bagging and boosting, as well as outperforming BMA over a wide variety of cases. This suggests that the power of ensembles does not come from their ability to account for model uncertainty, but instead comes from the changes in representational and preferential bias inherent in the process of combining several different models.

Particle Swarm Optimization (PSO) has typically been used with small swarms of about 50 particles. However, PSO is more efficiently parallelized with large swarms. We formally describe existing topologies and identify variations which are better suited to large swarms in both sequential and parallel computing environments. We examine the performance of PSO for benchmark functions with respect to swarm size and topology. We develop and demonstrate a new PSO variant which leverages the unique strengths of large swarms. “Hearsay PSO” allows for information to flow quickly through the swarm, even with very loosely connected topologies. These loosely connected topologies are well suited to large scale parallel computing environments because they require very little communication between particles. We consider the case where function evaluations are expensive with respect to communication as well as the case where function evaluations are relatively inexpensive. We also consider a situation where local communication is inexpensive compared to external communication, such as multicore systems in a cluster.

This paper presents Bayesian edge inference (BEI), a single frame super resolution method explicitly grounded in Bayesian inference that addresses issues common to existing methods. Though the best give excellent results at modest magnification factors, they suffer from gradient stepping and boundary coherence problems by factors of 4x. Central to BEI is a causal framework that allows image capture and recapture to be modeled differently, a principled way of undoing downsampling blur, and a technique for incorporating Markov random field potentials arbitrarily into Bayesian networks. Besides addressing gradient and boundary issues, BEI is shown to be competitive with existing methods on published correctness measures. The model and framework are shown to generalize to other reconstruction tasks by demonstrating BEI's effectiveness at CCD demosaicing and inpainting with only trivial changes.

We present a statistical model of empirical optimization that admits the creation of algorithms with explicit and intuitively defined desiderata. Because No Free Lunch theorems dictate that no optimization algorithm can be considered more efficient than any other when considering all possible functions, the desired function class plays a prominent role in the model. In particular, this provides a direct way to answer the traditionally difficult question of what algorithm is best matched to a particular class of functions. Among the benefits of the model are the ability to specify the function class in a straightforward manner, a natural way to specify noisy or dynamic functions, and a new source of insight into No Free Lunch theorems for optimization.

In optimization problems involving large amounts of data, such as web content, commercial transaction information, or bioinformatics data, individual function evaluations may take minutes or even hours. particle swarm optimization (PSO) must be parallelized for such functions. However, large-scale parallel programs must communicate efficiently, balance work across all processors, and address problems such as failed nodes. We present mapreduce particle swarm optimization (MRPSO), a PSO implementation based on the mapreduce parallel programming model. We describe MapReduce and show how PSO can be naturally expressed in this model, without explicitly addressing any of the details of parallelization. We present a benchmark function for evaluating MRPSO and note that MRPSO is not appropriate for optimizing easily evaluated functions. We demonstrate that MRPSO scales to 256 processors on moderately difficult problems and tolerates node failures.

We recast the problem of unconstrained continuous evolutionary optimization as inference in a fixed graphical model. This approach allows us to address several pervasive issues in optimization, including the traditionally difficult problem of selecting an algorithm that is most appropriate for a given task. This is accomplished by placing a prior distribution over the expected class of functions, then employing inference and intuitively defined utilities and costs to transform the evolutionary optimization problem into one of active sampling. This allows us to pose an approach to optimization that is optimal for each expressly stated function class. The resulting solution methodology can optimally navigate exploration-exploitation tradeoffs using well-motivated decision theory, while providing the process with a natural stopping criterion. Finally, the model naturally accommodates the expression of dynamic and noisy functions, setting it apart from most existing algorithms that address these issues as an afterthought. We demonstrate the characteristics and advantages of this algorithm formally and with examples.

In optimization problems involving large amounts of data, Particle Swarm Optimization (PSO) must be parallelized because individual function evaluations may take minutes or even hours. However, large-scale parallelization is difficult because programs must communicate efficiently, balance workloads and tolerate node failures. To address these issues, we present Map Reduce Particle Swarm Optimization(MRPSO), a PSO implementation based on Google's Map Reduce parallel programming model.

This paper shows that the basic Hough transform is implicitly a Bayesian process-that it computes an unnormalized posterior distribution over the parameters of a single shape given feature points. The proof motivates a purely Bayesian approach to the problem of finding parameterized shapes in digital images. A proof-of-concept implementation that finds multiple shapes of four parameters is presented. Extensions to the basic model that are made more obvious by the presented reformulation are discussed.

Dynamic pricing is a real-time machine learning problem with scarce prior data and a concrete learning cost. While the Kalman Filter can be employed to track hidden demand parameters and extensions to it can facilitate exploration for faster learning, the exploratory nature of Particle Swarm Optimization makes it a natural choice for the dynamic pricing problem. We compare both the Kalman Filter and existing particle swarm adaptations for dynamic and/or noisy environments with a novel approach that time-decays each particle's previous best value; this new strategy provides more graceful and effective transitions between exploitation and exploration, a necessity in the dynamic and noisy environments inherent to the dynamic pricing problem.

Spatial Extension PSO (SEPSO) and Attractive-Repulsive PSO (ARPSO) are methods for artificial injection of diversity into particle swarm optimizers that are intended to encourage converged swarms to engage in exploration. While simple to implement, effective when tuned correctly, and benefiting from intuitive appeal, SEPSO behavior can be improved by adapting its radius and bounce parameters in response to collisions. In fact, adaptation can allow SEPSO to compete with and outperform ARPSO. The adaptation strategies presented here are simple to implement, easy to tune, and retain SEPSO's intuitive appeal.

This paper shows how the notion of value of cooperation, a measure of the percentage of a firm's profits due strictly to the cooperative effects among the goods it sells, can be used to analyze the relative economic advantage afforded by various organizational structures. The value of cooperation is computed from transactions data by solving a regression problem to fit the parameters of the consumer demand function, and then simulating the resulting profit-maximizing dynamic system under various organizational structures. A hierarchical agglomerative clustering algorithm can be applied to reveal the optimal organizational substructure.

We present a homomorphous mapping that converts problems with linear equality constraints into fully unconstrained and lower-dimensional problems for optimization with PSO. This approach, in contrast with feasibility preservation methods, allows any unconstrained optimization algorithm to be applied to a problem with linear equality constraints, making available tools that are known to be effective and simplifying the process of choosing an optimizer for these kinds of constrained problems. The application of some PSO algorithms to a problem that has undergone the mapping presented here is shown to be more effective and more consistent than other approaches to handling linear equality constraints in PSO

We explore the use of information models as a guide for the development of single objective optimization algorithms, giving particular attention to the use of Bayesian models in a PSO context. The use of an explicit information model as the basis for particle motion provides tools for designing successful algorithms. One such algorithm is developed and shown empirically to be effective. Its relationship to other popular PSO algorithms is explored and arguments are presented that those algorithms may be developed from the same model, potentially providing new tools for their analysis and tuning.

We discuss testing methods for exposing origin-seeking bias in PSO motion algorithms. The strategy of resizing the initialization space, proposed by Gehlhaar and Fogel and made popular in the PSO context by Angeline, is shown to be insufficiently general for revealing an algorithm's tendency to focus its efforts on regions at or near the origin. An alternative testing method is proposed that reveals problems with PSO motion algorithms that are not visible when merely resizing the initialization space.

Recent research in task transfer and task clustering has necessitated the need for task similarity measures in reinforcement learning. Determining task similarity is necessary for selective transfer where only information from relevant tasks and portions of a task are transferred. Which task similarity measure to use is not immediately obvious. It can be shown that no single task similarity measure is uniformly superior. The optimal task similarity measure is dependent upon the task transfer method being employed. We define similarity in terms of tasks, and propose several possible task similarity measures, d/sub T/, d/sub P/, d/sub Q/, and d/sub R/ which are based on the transfer time, policy overlap, Q-values, and reward structure respectively. We evaluate their performance in three separate experimental situations.

The performance of value and policy iteration can be dramatically improved by eliminating redundant or useless backups, and by backing up states in the right order. We study several methods designed to accelerate these iterative solvers, including prioritization, partitioning, and variable reordering. We generate a family of algorithms by combining several of the methods discussed, and present extensive empirical evidence demonstrating that performance can improve by several orders of magnitude for many problems, while preserving accuracy and convergence guarantees.

We present an examination of the state-of-the-art for using value iteration to solve large-scale discrete Markov Decision Processes. We introduce an architecture which combines three independent performance enhancements (the intelligent prioritization of computation, state partitioning, and massively parallel processing) into a single algorithm. We show that each idea improves performance in a different way, meaning that algorithm designers do not have to trade one improvement for another. We give special attention to parallelization issues, discussing how to efficiently partition states, distribute partitions to processors, minimize message passing and ensure high scalability. We present experimental results which demonstrate that this approach solves large problems in reasonable time.

In a reinforcement learning task library system for Multiple Goal Markov Decision Process (MGMDP), localization in the task space allows the agent to determine whether a given task is already in its library in order to exploit previously learned experience. Task localization in MGMDPs can be accomplished through a Bayesian approach, however a trivial approach fails when the rewards are not distributed normally. This can be overcome through our Bayesian Task Localization Technique (BTLT).

We present JoSTLe, an algorithm that performs value iteration on control problems with continuous actions, allowing this useful reinforcement learning technique to be applied to problems where a priori action discretization is inadequate. The algorithm is an extension of a variable resolution technique that works for problems with continuous states and discrete actions [6]. Results are given that indicate that JoSTLe is a promising step toward reinforcement learning in a fully continuous domain.

The focus of this paper is the application of Bayesian concepts to database query optimization. In relational database systems users retrieve data by describing the desired data. The description of the desired data takes the form of statements which specify operations on “relations” (as defined by set theory). In a relational database system a “query optimizer” determines how the desired data is to be found. The optimizer may have access to several potential algorithms for each step in the query. Each algorithm has a unique effect on the cost of evaluating the query. No single algorithm is best in all cases. To choose among the possible alternatives, the optimizer uses summary statistics of the data stored in the database to estimate the cost associated with the use of each alternative algorithm. Given the summary nature of the statistics typically collected, the true cost of the use of a given algorithm can be only estimated. As such, the query optimizer must choose algorithms in the presence of uncertainty. As will be illustrated later with a simple model, cases exist where the expected improvement in decision quality more than offsets the cost of sampling the database to gathering additional, more accurate, information. These cases are identified before such sampling is performed by using Bayesian pre-posterier analysis. When sample information is expected to have significant net value to the decision making process, sampling should be performed. In database query optimization readily available summary information is sufficient for the decision making process in some cases, in other cases, it is wholly inadequate. Examples of each of these cases will be identified. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.