Computer Science Theses and Dissertations
Permanent URI for this collectionhttp://hdl.handle.net/1903/2756
Browse
14 results
Search Results
Item Cooperative Particle Swarm Optimization for Combinatorial Problems(2009) Lapizco Encinas, Grecia del Carmen; Reggia, James A; Kingsford, Carl L; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)A particularly successful line of research for numerical optimization is the well-known computational paradigm particle swarm optimization (PSO). In the PSO framework, candidate solutions are represented as particles that have a position and a velocity in a multidimensional search space. The direct representation of a candidate solution as a point that flies through hyperspace (i.e., Rn) seems to strongly predispose the PSO toward continuous optimization. However, while some attempts have been made towards developing PSO algorithms for combinatorial problems, these techniques usually encode candidate solutions as permutations instead of points in search space and rely on additional local search algorithms. In this dissertation, I present extensions to PSO that by, incorporating a cooperative strategy, allow the PSO to solve combinatorial problems. The central hypothesis is that by allowing a set of particles, rather than one single particle, to represent a candidate solution, combinatorial problems can be solved by collectively constructing solutions. The cooperative strategy partitions the problem into components where each component is optimized by an individual particle. Particles move in continuous space and communicate through a feedback mechanism. This feedback mechanism guides them in the assessment of their individual contribution to the overall solution. Three new PSO-based algorithms are proposed. Shared-space CCPSO and multispace CCPSO provide two new cooperative strategies to split the combinatorial problem, and both models are tested on proven NP-hard problems. Multimodal CCPSO extends these combinatorial PSO algorithms to efficiently sample the search space in problems with multiple global optima. Shared-space CCPSO was evaluated on an abductive problem-solving task: the construction of parsimonious set of independent hypothesis in diagnostic problems with direct causal links between disorders and manifestations. Multi-space CCPSO was used to solve a protein structure prediction subproblem, sidechain packing. Both models are evaluated against the provable optimal solutions and results show that both proposed PSO algorithms are able to find optimal or near-optimal solutions. The exploratory ability of multimodal CCPSO is assessed by evaluating both the quality and diversity of the solutions obtained in a protein sequence design problem, a highly multimodal problem. These results provide evidence that extended PSO algorithms are capable of dealing with combinatorial problems without having to hybridize the PSO with other local search techniques or sacrifice the concept of particles moving throughout a continuous search space.Item Representing and Querying Uncertain Data(2009) Sen, Prithviraj; Getoor, Lise C; Deshpande, Amol V; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)There has been a longstanding interest in building systems that can handle uncertain data. Traditional database systems inherently assume exact data and harbor fundamental limitations when it comes to handling uncertain data. In this dissertation, we present a probabilistic database model that can compactly represent uncertainty models in full generality. Our representation is associated with precise and intuitive semantics and we show that the answer to every user-submitted query can be obtained by performing probabilistic inference. To query large-scale probabilistic databases, we propose a number of techniques that help scale probabilistic inference. Foremost among these techniques is a novel lifted inference algorithm that determines and exploits symmetries in the uncertainty model to speed up query evaluation. For cases when the uncertainty model stored in the database does not contain symmetries, we propose a number of techniques that perform approximate lifted inference. Our techniques for approximate lifted inference have the added advantage of allowing the user to control the degree of approximation through a handful of tunable parameters. Besides scaling probabilistic inference, we also develop techniques that alter the structure of inference required to evaluate a query. More specifically, we show that for a restricted model of our probabilistic database, if each result tuple can be represented by a boolean formula with special characteristics, i.e., it is a read-once function, then the complexity of inference can be drastically reduced. We conclude the dissertation with a listing of directions for future work.Item Beyond Nouns and Verbs(2009) Gupta, Abhinav; Davis, Larry; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)During the past decade, computer vision research has focused on constructing image based "appearance" models of objects and action classes using large databases of examples (positive and negative) and machine learning to construct models. Visual inference however involves not only detecting and recognizing objects and actions but also extracting rich relationships between objects and actions to form storylines or plots. These relationships also improve recognition performance of appearance-based models. Instead of identifying individual objects and actions in isolation, such systems improve recognition rates by augmenting appearance based models with contextual models based on object-object, action-action and object-action relationships. In this thesis, we look at the problem of using contextual information for recognition from three different perspectives: (a) Representation of Contextual Models (b) Role of language in learning semantic/contextual models (c) Learning of contextual models from weakly labeled data. Our work departs from the traditional view of visual and contextual learning where individual detectors and relationships are learned separately. Our work focuses on simultaneous learning of visual appearance and contextual models from richly annotated, weakly labeled datasets. Specifically, we show how rich annotations can be utilized to constrain the learning of visually grounded models of nouns, prepositions and comparative adjectives from weakly labeled data. I will also show how visually grounded models of prepositions and comparative adjectives can be utilized as contextual models for scene analysis. We also present storyline models for interpretation of videos. Storyline models go beyond pair-wise contextual models and represent higher order constraints by allowing only specific possible action sequences (stories). Visual inference using storyline models involve inferring the ``plot'' of the video (sequence of actions) and recognizing individual activities in the plot.Item Synthesis of Strategies for Non-Zero-Sum Repeated Games(2008-08-21) Au, Tsz-Chiu; Nau, Dana; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)There are numerous applications that involve two or more self-interested autonomous agents that repeatedly interact with each other in order to achieve a goal or maximize their utilities. This dissertation focuses on the problem of how to identify and exploit useful structures in agents' behavior for the construction of good strategies for agents in multi-agent environments, particularly non-zero-sum repeated games. This dissertation makes four contributions to the study of this problem. First, this thesis describes a way to take a set of interaction traces produced by different pairs of players in a two-player repeated game, and then find the best way to combine them into a strategy. The strategy can then be incorporated into an existing agent, as an enhancement of the agent's original strategy. In cross-validated experiments involving 126 agents for the Iterated Prisoner's Dilemma, Iterated Chicken Game, and Iterated Battle of the Sexes, my technique was able to make improvement to the performance of nearly all of the agents. Second, this thesis investigates the issue of uncertainty about goals when a goal-based agent situated in a nondeterministic environment. The results of this investigation include the necessary and sufficiency conditions for such guarantee, and an algorithm for synthesizing a strategy from interaction traces that maximizes the probability of success of an agent even when no strategy can assure the success of the agent. Third, this thesis introduces a technique, Symbolic Noise Detection (SND), for detecting noise (i.e., mistakes or miscommunications) among agents in repeated games. The idea is that if we can build a model of the other agent's behavior, we can use this model to detect and correct actions that have been affected by noise. In the 20th Anniversary Iterated Prisoner's Dilemma competition, the SND agent placed third in the "noise" category, and was the best performer among programs that had no "slave" programs feeding points to them. Fourth, the thesis presents a generalization of SND that can be wrapped around any existing strategy. Finally, the thesis includes a general framework for synthesizing strategies from experience for repeated games in both noisy and noisy-free environments.Item Artificial Evolution of Arbitrary Self-Replicating Cellular Automata(2007-08-22) Pan, Zhijian; Reggia, James; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Since John von Neumann's seminal work on developing cellular automata models of self-replication, there have been numerous computational studies that have sought to create self-replicating structures or "machines". Cellular automata (CA) has been the most widely used method in these studies, with manual designs yielding a number of specific self-replicating structures. However, it has been found to be very difficult, in general, to design local state-transition rules that, when they operate concurrently in each cell of the cellular space, produce a desired global behavior such as self-replication. This has greatly limited the number of different self-replicating structures designed and studied to date. In this dissertation, I explore the feasibility of overcoming this difficulty by using genetic programming (GP) to evolve novel CA self-replication models. I first formulate an approach to representing structures and rules in cellular automata spaces that is amenable to manipulation by the genetic operations used in GP. Then, using this representation, I demonstrate that it is possible to create a "replicator factory" that provides an unprecedented ability to automatically generate a whole class of new self-replicating structures and that allows one to systematically investigate the properties of replicating structures as one varies the initial configuration, its size, shape, symmetry, and allowable states. This approach is then extended to incorporate multi-objective fitness criteria, resulting in production of diversified replicators. For example, this allows generation of target structures whose complexity greatly exceeds that of the seed structure itself. Finally, the extended multi-objective replicator factory is further generalized into a structure/rule co-evolution model, such that replicators with unspecified seed structures can also be concurrently evolved, resulting in different structure/rule combinations and having the capability of not only replicating but also carrying out a secondary pre-specified task with different strategies. I conclude that GP provides a powerful method for creating CA models of self-replication.Item The Influence of Collective Working Memory Strategies on Agent Teams(2007-08-03) Winder, Ransom Kershaw; Reggia, James A.; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Past self-organizing models of collectively moving "particles" (simulated bird flocks, fish schools, etc.) typically have been based on purely reflexive agents that have no significant memory of past movements or environmental obstacles. These agent collectives usually operate in abstract environments, but as these domains take on a greater realism, the collective requires behaviors use not only presently observed stimuli but also remembered information. It is hypothesized that the addition of a limited working memory of the environment, distributed among the collective's individuals can improve efficiency in performing tasks. This is first approached in a more traditional particle system in an abstract environment. Then it is explored for a single agent, and finally a team of agents, operating in a simulated 3-dimensional environment of greater realism. In the abstract environment, a limited distributed working memory produced a significant improvement in travel between locations, in some cases improving performance over time, while in others surprisingly achieving an immediate benefit from the influence of memory. When strategies for accumulating and manipulating memory were subsequently explored for a more realistic single agent in the 3-dimensional environment, if the agent kept a local or a cumulative working memory, its performance improved on different tasks, both when navigating nearby obstacles and, in the case of cumulative memory, when covering previously traversed terrain. When investigating a team of these agents engaged in a pursuit scenario, it was determined that a communicating and coordinating team still benefited from a working memory of the environment distributed among the agents, even with limited memory capacity. This demonstrates that a limited distributed working memory in a multi-agent system improves performance on tasks in domains of increasing complexity. This is true even though individual agents know only a fraction of the collective's entire memory, using this partial memory and interactions with others in the team to perform tasks. These results may prove useful in improving existing methodologies for control of collective movements for robotic teams, computer graphics, particle swarm optimization, and computer games, and in interpreting future experimental research on group movements in biological populations.Item Adapting Swarm Intelligence for the Self-Assembly of Prespecified Artificial Structures(2007-04-25) Grushin, Alexander; Reggia, James A; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The self-assembly problem involves designing individual behaviors that a collection of agents can follow in order to form a given target structure. An effective solution would potentially allow self-assembly to be used as an automated construction tool, for example, in dangerous or inaccessible environments. However, existing methodologies are generally limited in that they are either only capable of assembling a very limited range of simple structures, or only applicable in an idealized environment having few or no constraints on the agents' motion. The research presented here seeks to overcome these limitations by studying the self-assembly of a diverse class of non-trivial structures (building, bridge, etc.) from different-sized blocks, whose motion in a continuous, three-dimensional environment is constrained by gravity and block impenetrability. These constraints impose ordering restrictions on the self-assembly process, and necessitate the assembly and disassembly of temporary structures such as staircases. It is shown that self-assembly under these conditions can be accomplished through an integration of several techniques from the field of swarm intelligence. Specifically, this work extends and incorporates computational models of distributed construction, collective motion, and communication via local signaling. These mechanisms enable blocks to determine where to deposit themselves, to effectively move through continuous space, and to coordinate their behavior over time, while using only local information. Further, an algorithm is presented that, given a target structure, automatically generates distributed control rules that encode individual block behaviors. It is formally proved that under reasonable assumptions, these rules will lead to the emergence of correct system-level coordination that allows self-assembly to complete in spite of environmental constraints. The methodology is also verified experimentally by generating rules for a diverse set of structures, and testing them via simulations. Finally, it is shown that for some structures, the generated rules are able to parsimoniously capture the necessary behaviors. This work yields a better understanding of the complex relationship between local behaviors and global structures in non-trivial self-assembly processes, and presents a step towards their use in the real world.Item Scalable machine learning for massive datasets: Fast summation algorithms(2007-04-25) Raykar, Vikas Chandrakant; Duraiswami, Ramani; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Huge data sets containing millions of training examples with a large number of attributes are relatively easy to gather. However one of the bottlenecks for successful inference is the computational complexity of machine learning algorithms. Most state-of-the-art nonparametric machine learning algorithms have a computational complexity of either O(N^2) or O(N^3), where N is the number of training examples. This has seriously restricted the use of massive data sets. The bottleneck computational primitive at the heart of various algorithms is the multiplication of a structured matrix with a vector, which we refer to as matrix-vector product (MVP) primitive. The goal of my thesis is to speedup up some of these MVP primitives by fast approximate algorithms that scale as O(N) and also provide high accuracy guarantees. I use ideas from computational physics, scientific computing, and computational geometry to design these algorithms. The proposed algorithms have been applied to speedup kernel density estimation, optimal bandwidth estimation, projection pursuit, Gaussian process regression, implicit surface fitting, and ranking.Item Bilattice based Logical Reasoning for Automated Visual Surveillance and other Applications(2007-03-23) Shet, Vinay Damodar; Davis, Larry S; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The primary objective of an automated visual surveillance system is to observe and understand human behavior and report unusual or potentially dangerous activities/events in a timely manner. Automatically understanding human behavior from visual input, however, is a challenging task. The research presented in this thesis focuses on designing a reasoning framework that can combine, in a principled manner, high level contextual information with low level image processing primitives to interpret visual information. The primary motivation for this work has been to design a reasoning framework that draws heavily upon human like reasoning and reasons explicitly about visual as well as non-visual information to solve classification problems. Humans are adept at performing inference under uncertainty by combining evidence from multiple, noisy and often contradictory sources. This thesis describes a logical reasoning approach in which logical rules encode high level knowledge about the world and logical facts serve as input to the system from real world observations. The reasoning framework supports encoding of multiple rules for the same proposition, representing multiple lines of reasoning and also supports encoding of rules that infer explicit negation and thereby potentially contradictory information. Uncertainties are associated with both the logical rules that guide reasoning as well as with the input facts. This framework has been applied to visual surveillance problems such as human activity recognition, identity maintenance, and human detection. Finally, we have also applied it to the problem of collaborative filtering to predict movie ratings by explicitly reasoning about users preferences.Item Neural Network Generation of Temporal Sequences from Single Static Vector Inputs using Varying Length Distal Target Sequences(2007-04-10) Gittens, Shaun; Reggia, James; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Training an agent to operate in an environment whose mappings are largely unknown is generally recognized to be exceptionally difficult. Further, granting such a learning agent the ability to produce an appropriate sequence of actions entirely from a single input stimulus remains a key problem. Various reinforcement learning techniques have been utilized to handle such learning tasks, but convergence to optimal policies is not guaranteed for many of these methods. Traditional supervised learning methods hold more assurances of convergence, but these methods are not well suited for tasks where desired actions in the output space of the learner, termed proximal actions, are not available for training. Rather, target outputs from the environment are distal from where the learning takes place. For example, a child acquiring language skill who makes speech errors must learn to correct them based on heard information that reaches his/her auditory cortex, which is distant from the motor cortical regions that control speech output. While distal supervised learning techniques for neural networks have been devised, it remains to be established how they can be trained to produce sequences of proximal actions from only a single static input. The architecture demonstrated here incorporates recurrent multi-layered neural networks, each maintaining some manner of memory in the form of a context vector, into the distal supervised learning framework. This enables it to train learners capable of generating correct proximal sequences from single static input stimuli. This is in contrast to existing distal learning methods designed for non-recurrent neural network learners that utilize no concept of memory of their prior behavior. Also, a technique known as teacher forcing was adapted for use in distal sequential learning settings which is shown to result in more efficient usage of the recurrent neural network's context layer. The effectiveness of this approach is demonstrated by applying it in training recurrent learners to acquire phoneme sequence generating behavior using only previously heard and stored auditory phoneme sequences. The results indicate that recurrent networks can be integrated with distal learning methods to create effective sequence generators even when constantly updating current state information is unavailable.