Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Keyword
-
- Localization (6)
- Information retrieval (4)
- Robotics (4)
- Algorithms (3)
- Reinforcement learning (3)
-
- Cache (2)
- Computer Vision (2)
- Digital elevation models (2)
- Evaluation (2)
- Information Retrieval (2)
- Language Models (2)
- Machine Learning (2)
- Mobile robots (2)
- Photogrammetry (2)
- Probabilistic memory safety (2)
- Simulation (2)
- World Wide Web (2)
- Reinforcement Learning (RL) (1)
- decision-theoretic planning. (1)
- explicit congestion notification (ECN) (1)
- explicit loss notification (ELN) (1)
- notation. (1)
- 3D (1)
- Abstraction (1)
- Alias analysis (1)
- Anomaly detection. (1)
- Anonymity (1)
- Anonymous communication (1)
- Application (1)
- Applications (1)
Articles 31 - 60 of 232
Full-Text Articles in Physical Sciences and Mathematics
Structure Theorem And Strict Alternation Hierarchy For Fo2 On Words, Philipp Weis
Structure Theorem And Strict Alternation Hierarchy For Fo2 On Words, Philipp Weis
Computer Science Department Faculty Publication Series
It is well-known that every first-order property on words is expressible using at most three variables. The subclass of properties expressible with only two variables is also quite interesting and wellstudied. We prove precise structure theorems that characterize the exact expressive power of first-order logic with two variables on words. Our results apply to FO2[<] and FO 2[<; Suc], the latter of which includes the binary successor relation in addition to the linear ordering on string positions. For both languages, our structuretheorems showexactly whatis expressible using a given quantifier depth, n, and using m blocks of alternating quantifiers, for any m ≤ n. Using these characterizations, we prove, among other results, that there is a strict hierarchy of alternating quantifiers for both languages. The question whether there was such a hierarchy had been completely open. As another consequence of our structural results, we show that satisfiability for FO2[<], which is NEXP-complete in general, becomes NP-complete once we only consider alphabets of a bounded size.
Learning State-Action Basis Functions For Hierarchical Mdps, Sarah Osentoski
Learning State-Action Basis Functions For Hierarchical Mdps, Sarah Osentoski
Computer Science Department Faculty Publication Series
This paper introduces a new approach to actionvalue function approximation by learning basis functions from a spectral decomposition of the state-action manifold. This paper extends previous work on using Laplacian bases for value function approximation by using the actions of the agent as part of the representation when creating basis functions. The approach results in a nonlinear learned representation particularly suited to approximating action-value functions, without incurring the wasteful duplication of state bases in previous work. We discuss two techniques to create state-action graphs: offpolicy and on-policy. We show that these graphs have a greater expressive power and have better …
Evaluating Search Engines By Modeling The Relationship Between Relevance And Clicks, Ben Carterette, Rosie Jones
Evaluating Search Engines By Modeling The Relationship Between Relevance And Clicks, Ben Carterette, Rosie Jones
Computer Science Department Faculty Publication Series
We propose a model that leverages the millions of clicks received by web search engines to predict document relevance. This allows the comparison of ranking functions when clicks are available but complete relevance judgments are not. After an initial training phase using a set of relevance judgments paired with click data, we show that our model can predict the relevance score of documents that have not been judged. These predictions can be used to evaluate the performance of a search engine, using our novel formalization of the confidence of the standard evaluation metric discounted cumulative gain (DCG), so comparisons can …
Dtn Routing As A Resource Allocation Problem, Aruna Balasubramanian, Brian Neil Levine, Arun Venkataramani
Dtn Routing As A Resource Allocation Problem, Aruna Balasubramanian, Brian Neil Levine, Arun Venkataramani
Computer Science Department Faculty Publication Series
Routing protocols for disruption-tolerant networks (DTNs) use a variety of mechanisms, including discovering the meeting probabilities among nodes, packet replication, and network coding. The primary focus of these mechanisms is to increase the likelihood of finding a path with limited information, and so these approaches have only an incidental effect on routing such metrics as maximum or average delivery delay. In this paper, we present rapid, an intentional DTN routing protocol that can optimize a specific routing metric such as the worst-case delivery delay or the fraction of packets that are delivered within a deadline. The key insight is to …
A Framework For Meta-Level Control In Multi-Agent Systems, Anita Raja, Victor Lesser
A Framework For Meta-Level Control In Multi-Agent Systems, Anita Raja, Victor Lesser
Computer Science Department Faculty Publication Series
Sophisticated agents operating in open environments must make decisions that efficiently trade off the use of their limited resources between dynamic deliberative actions and domain actions. This is the meta-level control problem for agents operating in resource-bounded multi-agent environments. Control activities involve decisions on when to invoke and the amount to effort to put into scheduling and coordination of domain activities. The focus of this paper is how to make effectivemeta-level control decisions. We show that meta-level control with bounded computational overhead allows complex agents to solve problems more efficiently than current approaches in dynamic open multi-agent environments. The meta-level …
Expertise Modeling For Matching Papers With Reviewers, David Mimno
Expertise Modeling For Matching Papers With Reviewers, David Mimno
Computer Science Department Faculty Publication Series
An essential part of an expert-finding task, such as matching reviewers to submitted papers, is the ability to model the expertise of a person based on documents. We evaluate several measures of the association between an author in an existing collection of research papers and a previously unseen document. We compare two language model based approaches with a novel topic model, Author-Persona-Topic (APT). In this model, each author can write under one or more "personas," which are represented as independent distributions over hidden topics. Examples of previous papers written by prospective reviewers are gathered from the Rexa database, which extracts …
Bounds On The Gain Of Network Coding And Broadcasting In Wireless Networks, Junning Liu
Bounds On The Gain Of Network Coding And Broadcasting In Wireless Networks, Junning Liu
Computer Science Department Faculty Publication Series
Gupta and Kumar established that the per node throughput of ad hoc networks with multi-pair unicast traffic scales (poorly) as lambda(n) = Theta (1 / radic(n log n)) with an increasing number of nodes n. However, Gupta and Kumar did not consider the possibility of network coding and broadcasting in their model, and recent work has suggested that such techniques have the potential to greatly improve network throughput. In [1], we have shown that for the protocol communication model of Gupta and Kumar [2], the multi-unicast throughput of schemes using arbitrary network coding and broadcasting in a two-dimensional random topology …
Finding Tribes: Identifying Close-Knit Individuals From Employment Patterns, Lisa Friedland
Finding Tribes: Identifying Close-Knit Individuals From Employment Patterns, Lisa Friedland
Computer Science Department Faculty Publication Series
We present a family of algorithms to uncover tribes—groups of individuals who share unusual sequences of affiliations. While much work inferring community structure describes large-scale trends, we instead search for small groups of tightly linked individuals who behave anomalously with respect to those trends. We apply the algorithms to a large temporal and relational data set consisting of millions of employment records from the National Association of Securities Dealers. The resulting tribes contain individuals at higher risk for fraud, are homogenous with respect to risk scores, and are geographically mobile, all at significant levels compared to random or to other …
Unsupervised Joint Alignment Of Complex Images, Gary B. Huang
Unsupervised Joint Alignment Of Complex Images, Gary B. Huang
Computer Science Department Faculty Publication Series
Many recognition algorithms depend on careful positioning of an object into a canonical pose, so the position of features relative to a fixed coordinate system can be examined. Currently, this positioning is done either manually or by training a class-specialized learning algorithm with samples of the class that have been hand-labeled with parts or poses. In this paper, we describe a novel method to achieve this positioning using poorly aligned examples of a class with no additional labeling. Given a set of unaligned examplars of a class, such as faces, we automatically build an alignment mechanism, without any additional labeling …
Eflux: A Language And Runtime System For Perpetual Systems, Jacob Sorber
Eflux: A Language And Runtime System For Perpetual Systems, Jacob Sorber
Computer Science Department Faculty Publication Series
A key goal of mobile computing is untethering devices from wires, making them truly portable. While mobile devices can make use of wireless communication for network connectivity, they are still dependent on an electrical connection for continued operation. This need for tethering to available electricity significantly limits their range, usefulness, and manageability. Environmental energy harvesting—collecting energy from the sun, wind, heat differentials, and motion—offers the prospect of unprecedented, large-scale deployments of perpetual mobile systems that never need to be recharged. However, programming these systems presents new challenges: perpetual systems must adapt dynamically to available energy, delivering higher service levels when …
Adaptive Control Of Duty Cycling In Energy-Harvesting Wireless Sensor Networks, Christopher M. Vigorito
Adaptive Control Of Duty Cycling In Energy-Harvesting Wireless Sensor Networks, Christopher M. Vigorito
Computer Science Department Faculty Publication Series
Increasingly many wireless sensor network deployments are using harvested environmental energy to extend system lifetime. Because the temporal profiles of such energy sources exhibit great variability due to dynamic weather patterns, an important problem is designing an adaptive duty-cycling mechanism that allows sensor nodes to maintain their power supply at sufficient levels (energy neutral operation) by adapting to changing environmental conditions. Existing techniques to address this problem are minimally adaptive and assume a priori knowledge of the energy profile. While such approaches are reasonable in environments that exhibit low variance, we find that it is highly inefficient in more variable …
Mixtures Of Hierarchical Topics With Pachinko Allocation, David Mimno
Mixtures Of Hierarchical Topics With Pachinko Allocation, David Mimno
Computer Science Department Faculty Publication Series
The four-level pachinko allocation model (PAM) (Li & McCallum, 2006) represents correlations among topics using a DAG structure. It does not, however, represent a nested hierarchy of topics, with some topical word distributions representing the vocabulary that is shared among several more specific topics. This paper presents hierarchical PAM---an enhancement that explicitly represents a topic hierarchy. This model can be seen as combining the advantages of hLDA's topical hierarchy representation with PAM's ability to mix multiple leaves of the topic hierarchy. Experimental results show improvements in likelihood of held-out documents, as well as mutual information between automatically-discovered topics and humangenerated …
Statistical Models And Analysis Techniques For Learning In Relational Data, Jennifer Neville
Statistical Models And Analysis Techniques For Learning In Relational Data, Jennifer Neville
Computer Science Department Faculty Publication Series
Many data sets routinely captured by organizations are relational in nature— from marketing and sales transactions, to scientific observations and medical records. Relational data record characteristics of heterogeneous objects and persistent relationships among those objects (e.g., citation graphs, the World Wide Web, genomic structures). These data offer unique opportunities to improve model accuracy, and thereby decision-making, if machine learning techniques can effectively exploit the relational information. This work focuses on how to learn accurate statistical models of complex, relational data sets and develops two novel probabilistic models to represent, learn, and reason about statistical dependencies in these data. Relational dependency …
A Framework To Predict The Quality Of Answers With Nontextual, University Of Massachusetts Amherst
A Framework To Predict The Quality Of Answers With Nontextual, University Of Massachusetts Amherst
Computer Science Department Faculty Publication Series
New types of document collections are being developed by various web services. The service providers keep track of non-textual features such as click counts. In this paper, we present a framework to use non-textual features to pre- dict the quality of documents. We also show our quality measure can be successfully incorporated into the language modeling-based retrieval model. We test our approach on a collection of question and answer pairs gathered from a community based question answering service where people ask and answer questions. Experimental results using our quality measure show a signi¯cant improvement over our baseline.
Bibliometric Impact Measures Leveraging Topic Analysis, Gideon S. Mann
Bibliometric Impact Measures Leveraging Topic Analysis, Gideon S. Mann
Computer Science Department Faculty Publication Series
Measurements of the impact and history of research literature provide a useful complement to scientific digital library collections. Bibliometric indicators have been extensively studied, mostly in the context of journals. However, journal-based metrics poorly capture topical distinctions in fast-moving fields, and are increasingly problematic with the rise of open-access publishing. Recent developments in latent topic models have produced promising results for automatic sub-field discovery. The fine-grained, faceted topics produced by such models provide a clearer view of the topical divisions of a body of research literature and the interactions between those divisions. We demonstrate the usefulness of topic models in …
A Hierarchical, Hmmbased Accuracy For A Digital Library Of Books, Shaolei Feng
A Hierarchical, Hmmbased Accuracy For A Digital Library Of Books, Shaolei Feng
Computer Science Department Faculty Publication Series
A number of projects are creating searchable digital libraries of printed books. These include the Million Book Project, the Google Book project and similar efforts from Yahoo and Microsoft. Content-based on line book retrieval usually requires first converting printed text into machine readable (e.g. ASCII) text using an optical character recognition (OCR) engine and then doing full text search on the results. Many of these books are old and there are a variety of processing steps that are required to create an end to end system. Changing any step (including the scanning process) can affect OCR performance and hence a …
Flux: A Language For Programming High-Performance Servers, Brendan Burns, Kevin Grimaldi, Alexander Kostadinov, Emery D. Berger, Mark D. Corner
Flux: A Language For Programming High-Performance Servers, Brendan Burns, Kevin Grimaldi, Alexander Kostadinov, Emery D. Berger, Mark D. Corner
Computer Science Department Faculty Publication Series
Programming high-performance server applications is challenging: it is both complicated and error-prone to write the concurrent code required to deliver high performance and scalability. Server performance bottlenecks are difficult to identify and correct. Finally, it is difficult to predict server performance prior to deployment. This paper presents Flux, a language that dramatically simplifies the construction of scalable high-performance server applications. Flux lets programmers compose offthe- shelf, sequential C or C++ functions into concurrent servers. Flux programs are type-checked and guaranteed to be deadlock-free. We have built a number of servers in Flux, including a web server with PHP support, an …
Autonomous Shaping: Knowledge Transfer In Reinforcement Learning, George Konidaris
Autonomous Shaping: Knowledge Transfer In Reinforcement Learning, George Konidaris
Computer Science Department Faculty Publication Series
We introduce the use of learned shaping rewards in reinforcement learning tasks, where an agent uses prior experience on a sequence of tasks to learn a portable predictor that estimates intermediate rewards, resulting in accelerated learning in later tasks that are related but distinct. Such agents can be trained on a sequence of relatively easy tasks in order to develop a more informative measure of reward that can be transferred to improve performance on more difficult tasks without requiring a hand coded shaping function. We use a rod positioning task to show that this significantly improves performance even after a …
Hierarchical Power Management In Disruption Tolerant Networks With Trafficaware, Hyewon Jun
Hierarchical Power Management In Disruption Tolerant Networks With Trafficaware, Hyewon Jun
Computer Science Department Faculty Publication Series
Recent efforts in Disruption Tolerant Networks (DTNs) have shown that mobility can be a powerful means for delivering messages in highly-challenged environments. DTNs are wireless mobile networks that are particularly useful in sparse environments where the density of nodes is insufficient to support direct end-to-end communication. Unfortunately, many mobility scenarios depend on untethered devices with limited energy supplies. Without careful management depleted energy supplies will degrade network connectivity and counteract the robustness gained by mobility. A primary concern is the energy consumed by wireless communication, and in particular the energy consumed in searching for other nodes to communicate with. In …
Using Structure Indices For Efficient Approximation Of Network Properties, Matthew J. Rattigan, Marc Maier, David Jensen
Using Structure Indices For Efficient Approximation Of Network Properties, Matthew J. Rattigan, Marc Maier, David Jensen
Computer Science Department Faculty Publication Series
Statistics on networks have become vital to the study of relational data drawn from areas including bibliometrics, fraud detection, bioinformatics, and the Internet. Calculating many of the most important measures—such as betweenness centrality, closeness centrality, and graph diameter—requires identifying short paths in these networks. However, finding these short paths can be intractable for even moderate-size networks. We introduce the concept of a network structure index (NSI), a composition of (1) a set of annotations on every node in the network and (2) a function that uses the annotations to estimate graph distance between pairs of nodes. We present several varieties …
Oasis: An Overlayaware, Harsha V. Madhyastha
Oasis: An Overlayaware, Harsha V. Madhyastha
Computer Science Department Faculty Publication Series
Overlays have enabled several new and popular distributed applications such as Akamai, Kazaa, and Bittorrent. However, the lack of an overlay-aware network stack has hindered the widespread use of general purpose overlay packet delivery services [16, 29, 26]. In this paper, we describe the design and implementation of Oasis, a system and toolkit that enables legacy operating systems to access overlay-based packet delivery services. Oasis combines a set of ideas – network address translation, name resolution, packet capture, dynamic code execution – to provide greater user choice. We are in the process of making the Oasis toolkit available for public …
Ultra-Low Power Data Storage For Sensor Networks, Gaurav Mathur
Ultra-Low Power Data Storage For Sensor Networks, Gaurav Mathur
Computer Science Department Faculty Publication Series
Local storage is required in many sensor network applications, both for archival of detailed event information, as well as to overcome sensor platform memory constraints. While extensive measurement studies have been performed to highlight the trade-off between computation and communication in sensor networks, the role of storage has received little attention. The storage subsystems on currently available sensor platforms have not exploited technology trends, and consequently the energy cost of storage on these platforms is as high as that of communication. Current flash memories, however, offer a low-priced, high-capacity and extremely energy-efficient storage solution. In this paper, we perform a …
A Survey Of Practical Issues In Underwater Networks, Jim Partan
A Survey Of Practical Issues In Underwater Networks, Jim Partan
Computer Science Department Faculty Publication Series
No abstract provided.
Capacity Enhancement Using Throwboxes In Dtns, Wenrui Zhao, Yang Chen, Mostafa Ammar, Mark Corner, Brain Levine, Ellen Zegura
Capacity Enhancement Using Throwboxes In Dtns, Wenrui Zhao, Yang Chen, Mostafa Ammar, Mark Corner, Brain Levine, Ellen Zegura
Computer Science Department Faculty Publication Series
Disruption Tolerant Networks (DTNs) are designed to overcome limitations in connectivity due to conditions such as mobility, poor infrastructure, and short range radios. DTNs rely on the inherent mobility in the network to deliver packets around frequent and extended network partitions using a store-carry-andforward paradigm. However, missed contact opportunities decrease throughput and increase delay in the network.We propose the use of throwboxes in mobile DTNs to create a greater number of contact opportunities, consequently improving the performance of the network. Throwboxes are wireless nodes that act as relays, creating additional contact opportunities in the DTN. We propose algorithms to deploy …
Fast Direct Policy Evaluation Using Multiscale Analysis Of Markov Diffusion Processes, Mauro Maggioni, Sridhar Mahadevan
Fast Direct Policy Evaluation Using Multiscale Analysis Of Markov Diffusion Processes, Mauro Maggioni, Sridhar Mahadevan
Computer Science Department Faculty Publication Series
Policy evaluation is a critical step in the approximate solution of large Markov decision processes (MDPs), typically requiring O(|S|3) to directly solve the Bellman system of |S| linear equations (where |S| is the state space size in the discrete case, and the sample size in the continuous case). In this paper we apply a recently introduced multiscale framework for analysis on graphs to design a faster algorithm for policy evaluation. For a fixed policy π, this framework efficiently constructs a multiscale decomposition of the random walk P¼ associated with the policy π. This enables efficiently computing medium and long term …
Socially Guided Machine Learning, Andrea Lockerd Thomaz, Cynthia Breazeal, Andrew G. Barto, Rosalind Picard
Socially Guided Machine Learning, Andrea Lockerd Thomaz, Cynthia Breazeal, Andrew G. Barto, Rosalind Picard
Computer Science Department Faculty Publication Series
Social interaction will be key to enabling robots and machines in general to learn new tasks from ordinary people (not experts in robotics or machine learning). Everyday people who need to teach their machines new things will find it natural for to rely on their interpersonal interaction skills. This thesis provides several contributions towards the understanding of this Socially GuidedMachine Learning scenario. While the topic of human input to machine learning algorithms has been explored to some extent, prior works have not gone far enough to understand what people will try to communicate when teaching a machine and how algorithms …
Proto-Transfer Learning In Markov Decision Processes Using Spectral Methods, Kimberly Ferguson, Sridhar Mahadevan
Proto-Transfer Learning In Markov Decision Processes Using Spectral Methods, Kimberly Ferguson, Sridhar Mahadevan
Computer Science Department Faculty Publication Series
In this paper we introduce proto-transfer leaning, a new framework for transfer learning. We explore solutions to transfer learning within reinforcement learning through the use of spectral methods. Proto-value functions (PVFs) are basis functions computed from a spectral analysis of random walks on the state space graph. They naturally lead to the ability to transfer knowledge and representation between related tasks or domains. We investigate task transfer by using the same PVFs in Markov decision processes (MDPs) with different rewards functions. Additionally, our experiments in domain transfer explore applying the Nyström method for interpolation of PVFs between MDPs of different …
Find-Similar: Similarity Browsing As A Search Tool, Mark D. Smucker, James Allan
Find-Similar: Similarity Browsing As A Search Tool, Mark D. Smucker, James Allan
Computer Science Department Faculty Publication Series
Search systems have for some time provided users with the ability to request documents similar to a given document. Interfaces provide this feature via a link or button for each document in the search results. We call this feature findsimilar or similarity browsing. We examined find-similar as a search tool, like relevance feedback, for improving retrieval performance. Our investigation focused on find-similar’s document-to-document similarity, the reexamination of documents during a search, and the user’s browsing pattern. Find-similar with a query-biased similarity, avoiding the reexamination of documents, and a breadth-like browsing pattern achieved a 23% increase in the arithmetic mean average …
An Intrinsic Reward Mechanism For Efficient Exploration, Özgür Şimşek, Andrew G. Barto
An Intrinsic Reward Mechanism For Efficient Exploration, Özgür Şimşek, Andrew G. Barto
Computer Science Department Faculty Publication Series
How should a reinforcement learning agent act if its sole purpose is to efficiently learn an optimal policy for later use? In other words, how should it explore, to be able to exploit later? We formulate this problem as a Markov Decision Process by explicitly modeling the internal state of the agent and propose a principled heuristic for its solution. We present experimental results in a number of domains, also exploring the algorithm’s use for learning a policy for a skill given its reward function—an important but neglected component of skill discovery.
Key Regression: Enabling Efficient Key Distribution For Secure Distributed Storage, Kevin Fu, Seny Kamara, Tadayoshi Kohno
Key Regression: Enabling Efficient Key Distribution For Secure Distributed Storage, Kevin Fu, Seny Kamara, Tadayoshi Kohno
Computer Science Department Faculty Publication Series
The Plutus file system introduced the notion of key rotation as a means to derive a sequence of temporally-related keys from the most recent key. In this paper we show that, despite natural intuition to the contrary, key rotation schemes cannot generically be used to key other crypto- graphic objects; in fact, keying an encryption scheme with the output of a key rotation scheme can yield a composite system that is insecure. To address these shortcomings, we introduce a new cryptographic object called a key regression scheme, and we propose three constructions that are provably secure under standard cryptographic assumptions. …