Physical Sciences and Mathematics Commons^™

Query-Dependent Selection Of Retrieval Alternatives, Niranjan Balasubramanian

Open Access Dissertations

The main goal of this thesis is to investigate query-dependent selection of retrieval alternatives for Information Retrieval (IR) systems. Retrieval alternatives include choices in representing queries (query representations), and choices in methods used for scoring documents. For example, an IR system can represent a user query without any modification, automatically expand it to include more terms, or reduce it by dropping some terms. The main motivation for this work is that no single query representation or retrieval model performs the best for all queries. This suggests that selecting the best representation or retrieval model for each query can yield improved …

Computational Affect Detection For Education And Health, David G. Cooper

Open Access Dissertations

Emotional intelligence has a prominent role in education, health care, and day to day interaction. With the increasing use of computer technology, computers are interacting with more and more individuals. This interaction provides an opportunity to increase knowledge about human emotion for human consumption, well-being, and improved computer adaptation. This thesis explores the efficacy of using up to four different sensors in three domains for computational affect detection. We first consider computer-based education, where a collection of four sensors is used to detect student emotions relevant to learning, such as frustration, confidence, excitement and interest while students use a computer …

Generalized Expectation Criteria For Lightly Supervised Learning, Gregory Druck

Open Access Dissertations

Machine learning has facilitated many recent advances in natural language processing and information extraction. Unfortunately, most machine learning methods rely on costly labeled data, which impedes their application to new problems. Even in the absence of labeled data we often have a wealth of prior knowledge about these problems. For example, we may know which labels particular words are likely to indicate for a sequence labeling task, or we may have linguistic knowledge suggesting probable dependencies for syntactic analysis. This thesis focuses on incorporating such prior knowledge into learning, with the goal of reducing annotation effort for information extraction and …

Exploiting Structure In Coordinating Multiple Decision Makers, Hala Mostafa

Open Access Dissertations

This thesis is concerned with sequential decision making by multiple agents, whether they are acting cooperatively to maximize team reward or selfishly trying to maximize their individual rewards. The practical intractability of this general problem led to efforts in identifying special cases that admit efficient computation, yet still represent a wide enough range of problems. In our work, we identify the class of problems with structured interactions, where actions of one agent can have non-local effects on the transitions and/or rewards of another agent. We addressed the following research questions: 1) How can we compactly represent this class of problems? …

Variations On Stigmergic Communication To Improve Artificial Intelligence And Biological Modeling, Megan Marie Olsen

Open Access Dissertations

Stigmergy refers to indirect communication that was originally found in biological systems. It is used for self-organization by ants, bees, and flocks of birds, by allowing individuals to focus on local information. Through local communication among individuals, larger patterns are formed without centralized communication. This self-organization is just one type of system studied within complex systems. Systems of ants, bees, and flocks of birds are considered complex because they exhibit emergent behavior: the outcome is more than the sum of the individual parts. Emergent behavior can be found in many other systems as well. One example is the Internet, which …

Interactive Perception Of Articulated Objects For Autonomous Manipulation, Dov Katz

Open Access Dissertations

This thesis develops robotic skills for manipulating novel articulated objects. The degrees of freedom of an articulated object describe the relationship among its rigid bodies, and are often relevant to the object's intended function. Examples of everyday articulated objects include scissors, pliers, doors, door handles, books, and drawers. Autonomous manipulation of articulated objects is therefore a prerequisite for many robotic applications in our everyday environments. Already today, robots perform complex manipulation tasks, with impressive accuracy and speed, in controlled environments such as factory floors. An important characteristic of these environments is that they can be engineered to reduce or even …

Search Using Social Media Structures, Jangwon Seo

Open Access Dissertations

Social applications on the Web have appeared as communication spaces for sharing knowledge and information. In particular, social applications can be considered valuable information sources because information in the applications is not only easily accessible but also revealing in that the information accrues via interactions between people. In this work, we address methods for finding relevant information in social media applications that use unique properties of these applications. In particular, we focus on three unique structures in social media: hierarchical structure, conversational structure, and social structure. Hierarchical structures are used to organize information according to certain rules. Conversational structures are …

Discovering And Using Implicit Data For Information Retrieval, Xing Yi

Open Access Dissertations

In real-world information retrieval (IR) tasks, the searched items and/or the users' queries often have implicit information associated with them -- information that describes unspecified aspects of the items or queries. For example, in web search tasks, web pages are often pointed to by hyperlinks (known as anchors) from other pages, and thus have human-generated succinct descriptions of their content (anchor text) associated with them. This indirectly available information has been shown to improve search effectiveness for different retrieval tasks. However, in many real-world IR challenges this information is sparse in the data; i.e., it is incomplete or missing in …

Improving Data Center Resource Management, Deployment, And Availability With Virtualization, Timothy Wood

Open Access Dissertations

The increasing demand for storage and computation has driven the growth of large data centers--the massive server farms that run many of today's Internet and business applications. A data center can comprise many thousands of servers and can use as much energy as a small city. The massive amounts of computation power contained in these systems results in many interesting distributed systems and resource management problems. In this thesis we investigate challenges related to data centers, with a particular emphasis on how new virtualization technologies can be used to simplify deployment, improve resource efficiency, and reduce the cost of reliability, …

Scaling Multi-Agent Learning In Complex Environments, Chongjie Zhang

Open Access Dissertations

Cooperative multi-agent systems (MAS) are finding applications in a wide variety of domains, including sensor networks, robotics, distributed control, collaborative decision support systems, and data mining. A cooperative MAS consists of a group of autonomous agents that interact with one another in order to optimize a global performance measure. A central challenge in cooperative MAS research is to design distributed coordination policies. Designing optimal distributed coordination policies offline is usually not feasible for large-scale complex multi-agent systems, where 10s to 1000s of agents are involved, there is limited communication bandwidth and communication delay between agents, agents have only limited partial …

Autonomous Robot Skill Acquisition, George D. Konidaris

Open Access Dissertations

Among the most impressive of aspects of human intelligence is skill acquisition—the ability to identify important behavioral components, retain them as skills, refine them through practice, and apply them in new task contexts. Skill acquisition underlies both our ability to choose to spend time and effort to specialize at particular tasks, and our ability to collect and exploit previous experience to become able to solve harder and harder problems over time with less and less cognitive effort.

Hierarchical reinforcement learning provides a theoretical basis for skill acquisition, including principled methods for learning new skills and deploying them during problem solving. …

Enabling Peer-To-Peer Swarming For Multi-Commodity Dissemination, Daniel Sadoc Menasche

Open Access Dissertations

Peer-to-peer swarming, as used by BitTorrent, is one of the de facto solutions for content dissemination in today’s Internet. By leveraging resources provided by users, peer-to-peer swarming is a simple, scalable and efficient mechanism for content distribution. Although peer-to-peer swarming has been widely studied for a decade, prior work has focused on the dissemination of one commodity (a single file). This thesis focuses on the multi-commodity case.

We have discovered through measurements that a vast number of publishers currently disseminate multiple files in a single swarm (bundle). The first contribution of this thesis is a model for content availability. We …

Expressiveness And Succinctness Of First-Order Logic On Finite Words, Philipp P. Weis

Open Access Dissertations

Expressiveness, and more recently, succinctness, are two central concerns of finite model theory and descriptive complexity theory. Succinctness is particularly interesting because it is closely related to the complexity-theoretic trade-off between parallel time and the amount of hardware. We develop new bounds on the expressiveness and succinctness of first-order logic with two variables on finite words, present a related result about the complexity of the satisfiability problem for this logic, and explore a new approach to the generalized star-height problem from the perspective of logical expressiveness.

We give a complete characterization of the expressive power of first-order logic with two …

Adaptive Balancing Of Exploitation With Exploration To Improve Protein Structure Prediction, Tj Brunette

Open Access Dissertations

The most significant impediment for protein structure prediction is the inadequacy of conformation space search. Conformation space is too large and the energy landscape too rugged for existing search methods to consistently find near-optimal minima. Conformation space search methods thus have to focus exploration on a small fraction of the search space. The ability to choose appropriate regions, i.e. regions that are highly likely to contain the native state, critically impacts the effectiveness of search. To make the choice of where to explore requires information, with higher quality information resulting in better choices. Most current search methods are designed to …

Automated Negotiation For Complex Multi-Agent Resource Allocation, Bo An

Open Access Dissertations

The problem of constructing and analyzing systems of intelligent, autonomous agents is becoming more and more important. These agents may include people, physical robots, virtual humans, software programs acting on behalf of human beings, or sensors. In a large class of multi-agent scenarios, agents may have different capabilities, preferences, objectives, and constraints. Therefore, efficient allocation of resources among multiple agents is often difficult to achieve. Automated negotiation (bargaining) is the most widely used approach for multi-agent resource allocation and it has received increasing attention in the recent years. However, information uncertainty, existence of multiple contracting partners and competitors, agents' incentive …

Architecting Protocols To Enable Mobile Applications In Diverse Wireless Networks, Aruna Balasubramanian

Open Access Dissertations

The goal of this thesis is to architect robust protocols that overcome disruptions and enable applications in diverse mobile networks. Mobile users operate in diverse environments, starting from mostly connected cellular networks to mostly disconnected delay tolerant networks (DTNs). Each of these networks are prone to frequent disruptions due to mobility, coverage holes, poor channel conditions, and other factors. Designing protocols to tolerate such disruptions is challenging because of the extreme uncertainty in mobile wireless environments. In this thesis, I focus on four networks that span the diverse connectivity spectrum and answer the following questions for each network: (1) What …

Improving Processes Using Static Analysis Techniques, Bin Chen

Open Access Dissertations

Real-world processes often undergo improvements to meet certain goals, such as coping with changed requirements, eliminating defects, improving the quality of the products, and reducing costs. Identifying and evaluating the defects or errors in the process, identifying the causes of such defects, and validating proposed improvements all require careful analysis of the process.Human-intensive processes, where human contributions require considerable domain expertise and have a significant impact on the success or failure of the overall mission, are of particular concern because they can be extremely complex and may be used in critical, including life-critical, situations. To date, the analysis support for …

Hardening Software Against Memory Errors And Attacks, Albert Eugene Novark

Open Access Dissertations

Programs written in C and C++ are susceptible to a number of memory errors, including buffer overflows and dangling pointers. At best, these errors cause crashes or performance degradation. At worst, they enable security vulnerabilities, allowing denial-of-service or remote code execution. Existing runtime systems provide little protection against these errors. They allow minor errors to cause crashes and allow attackers to consistently exploit vulnerabilities. In this thesis, we introduce a series of runtime systems that protect deployed applications from memory errors. To guide the design of our systems, we analyze how errors interact with memory allocators to allow consistent exploitation …

A Teleological Approach To Robot Programming By Demonstration, John Douglas Sweeney

Open Access Dissertations

This dissertation presents an approach to robot programming by demonstration based on two key concepts: demonstrator intent is the most meaningful signal that the robot can observe, and the robot should have a basic level of behavioral competency from which to interpret observed actions. Intent is a teleological, robust teaching signal invariant to many common sources of noise in training. The robot can use the knowledge encapsulated in sensorimotor schemas to interpret the demonstration. Furthermore, knowledge gained in prior demonstrations can be applied to future sessions. I argue that programming by demonstration be organized into declarative and pro-cedural components. The …