Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- Information retrieval (2)
- Algorithms (1)
- Classification (1)
- Economics (1)
- Evaluation (1)
-
- FAQ retrieval (1)
- Information Retrieval (1)
- Language Models (1)
- Machine learning (1)
- Mathematical Programming/optimization (1)
- Multi-label (1)
- Panoramas (1)
- Passage retrieval (1)
- Performance evaluation (1)
- Routing (1)
- Simulations (1)
- Statistical learning (1)
- System design (1)
- Test collections (1)
- Uncertainty (1)
- User study (1)
- Video textures (1)
- Video-based rendering (1)
- Wireless networks (1)
Articles 1 - 24 of 24
Full-Text Articles in Physical Sciences and Mathematics
Minimum Energy Reliable Paths Using Unreliable Wireless Links, Qunfeng Dong
Minimum Energy Reliable Paths Using Unreliable Wireless Links, Qunfeng Dong
Computer Science Department Faculty Publication Series
No abstract provided.
Identifying Useful Subgoals In Reinforcement Learning By Local Graph Partitioning, Özgür Şimşek, Alicia P. Wolfe, Andrew G. Barto
Identifying Useful Subgoals In Reinforcement Learning By Local Graph Partitioning, Özgür Şimşek, Alicia P. Wolfe, Andrew G. Barto
Computer Science Department Faculty Publication Series
We present a new subgoal-based method for automatically creating useful skills in reinforcement learning. Our method identifies subgoals by partitioning local state transition graphs—those that are constructed using only the most recent experiences of the agent. The local scope of our subgoal discovery method allows it to successfully identify the type of subgoals we seek—states that lie between two densely-connected regions of the state space—while producing an algorithm with low computational cost.
The Author-Recipient-Topic Model For Topic And Role Discovery In Social Networks: Experiments With Enron And Academic Email, Andrew Mccallum, Andrés Corrada-Emmanuel, Xuerui Wang
The Author-Recipient-Topic Model For Topic And Role Discovery In Social Networks: Experiments With Enron And Academic Email, Andrew Mccallum, Andrés Corrada-Emmanuel, Xuerui Wang
Computer Science Department Faculty Publication Series
Previous work in social network analysis (SNA) has modeled the existence of links from one entity to another, but not the language content or topics on those links. We present the Author-Recipient-Topic (ART) model for social network analysis, which learns topic distributions based on the the directionsensitive messages sent between entities. The model builds on Latent Dirichlet Allocation and the Author-Topic (AT) model, adding the key attribute that distribution over topics is conditioned distinctly on both the sender and recipient—steering the discovery of topics according to the relationships between people. We give results on both the Enron email corpus and …
When Will Information Retrieval Be “Good Enough”?, James Allan
When Will Information Retrieval Be “Good Enough”?, James Allan
Computer Science Department Faculty Publication Series
We describe a user study that examined the relationship between the quality of an Information Retrieval system and the effectiveness of its users in performing a task. The task involves finding answer facets of questions pertaining to a collection of newswire documents over a six month period. We artificially created sets of ranked lists at increasing levels of quality by blending the output of a state-of-the-art retrieval system with truth data created by annotators. Subjects performed the task by using these ranked lists to guide their labeling of answer passages in the retrieved articles. We found that as system accuracy …
Finding Similar Questions In Large Question And Answer Archives, Jiwoon Jeon
Finding Similar Questions In Large Question And Answer Archives, Jiwoon Jeon
Computer Science Department Faculty Publication Series
There has recently been a significant increase in the number of community-based question and answer services on the Web where people answer other peoples’ questions. These services rapidly build up large archives of questions and answers, and these archives are a valuable linguistic resource. One of the major tasks in a question and answer service is to find questions in the archive that a semantically similar to a user’s question. This enables high quality answers from the archive to be retrieved and removes the time lag associated with a community-based system. In this paper, we discuss methods for question retrieval …
Presto: A Predictive Storage Architecture For Sensor Networks, Peter Desnoyers
Presto: A Predictive Storage Architecture For Sensor Networks, Peter Desnoyers
Computer Science Department Faculty Publication Series
We describe PRESTO, a predictive storage architecture for emerging large-scale, hierarchical sensor networks. In contrast to existing techniques, PRESTO is a proxycentric architecture, where tethered proxies balance the need for interactive querying from users with the energy optimization needs of the remote sensors. The main novelty in this work lies in extensive use of predictive techniques that are a natural fit to the correlated behavior of the physical world. PRESTO exploits technology trends in storage to build an architecture that emphasizes archival at remote sensors and intelligent caching at proxies. The system also addresses user needs for querying such sensor …
Incorporating Uncertainty In Agent Commitments, Ping Xuan
Incorporating Uncertainty In Agent Commitments, Ping Xuan
Computer Science Department Faculty Publication Series
Commitments play a central role in multi-agent coordination. However, they are inherently uncertain and it is important to take these uncertainties into account during planning and scheduling. This paper addresses the problem of handling the uncertainty in commitments.We propose a new model of commitment that incorporates the uncertainty, the use of contingency analysis to reduce the uncertainty, and a negotiation framework for handling commitments with uncertainty.
On The Interaction Of Data Representation And Routing In Sensor Networks, Deepak Ganesan
On The Interaction Of Data Representation And Routing In Sensor Networks, Deepak Ganesan
Computer Science Department Faculty Publication Series
We consider data gathering by a network with a sink node and a tree communication structure, where the goal is to minimize the total transmission cost of transporting the information collected by the nodes, to the sink node. This problem requires a joint optimization of the data representation at the nodes and of the transmission structure. First, we study the case when the measured data are correlated random variables, both in the lossless scenario with Slepian-Wolf coding, and in the high-resolution lossy scenario with optimal rate-distortion allocation. We show that the optimal transmission structure is the shortest path tree, and …
Multi-Way Distributional Clustering Via Pairwise Interactions, Ron Bekkerman
Multi-Way Distributional Clustering Via Pairwise Interactions, Ron Bekkerman
Computer Science Department Faculty Publication Series
We present a novel unsupervised learning scheme that simultaneously clusters variables of several types (e.g., documents, words and authors) based on pairwise interactions be- tween the types, as observed in co-occurrence data. In this scheme, multiple clustering systems are generated aiming at maximizing an objective function that measures multiple pairwise mutual information between cluster variables. To implement this idea, we pro- pose an algorithm that interleaves top-down clustering of some variables and bottom-up clustering of the other variables, with a local optimization correction routine. Focusing on document clustering we present an extensive empirical study of two-way, three-way and four-way applications …
Topic And Role Discovery In Social Networks, Andrew Mccallum, Andrés Corrada-Emmanuel, Xuerui Wang
Topic And Role Discovery In Social Networks, Andrew Mccallum, Andrés Corrada-Emmanuel, Xuerui Wang
Computer Science Department Faculty Publication Series
Previous work in social network analysis (SNA) has modeled the existence of links from one entity to another, but not the language content or topics on those links. We present the Author- Recipient-Topic (ART) model for social network analysis, which learns topic distributions based on the direction-sensitive messages sent between entities. The model builds on Latent Dirichlet Allocation (LDA) and the Author-Topic (AT) model, adding the key attribute that distribution over topics is conditioned distinctly on both the sender and recipient—steering the discovery of topics according to the relationships between people. We give results on both the Enron email corpus …
Incremental Test Collections, Ben Carterette, James Allan
Incremental Test Collections, Ben Carterette, James Allan
Computer Science Department Faculty Publication Series
Corpora and topics are readily available for information retrieval research. Relevance judgments, which are necessary for system evaluation, are expensive; the cost of obtaining them prohibits in-house evaluation of retrieval systems on new corpora or new topics. We present an algorithm for cheaply constructing sets of relevance judgments. Our method intelligently selects documents to be judged and decides when to stop in such a way that with very little work there can be a high degree of confidence in the result of the evaluation. We demonstrate the algorithm's effectiveness by showing that it produces small sets of relevance judgments that …
Panoramic Video Textures, Aseem Agarwala, Ke Colin Zheng, Chris Pal, Maneesh Agrawala, Michael Cohen, Brian Curless, David Salesin, Richard Szeliski
Panoramic Video Textures, Aseem Agarwala, Ke Colin Zheng, Chris Pal, Maneesh Agrawala, Michael Cohen, Brian Curless, David Salesin, Richard Szeliski
Computer Science Department Faculty Publication Series
This paper describes a mostly automatic method for taking the output of a single panning video camera and creating a panoramic video texture (PVT): a video that has been stitched into a single, wide field of view and that appears to play continuously and indefinitely. The key problem in creating a PVT is that although only a portion of the scene has been imaged at any given time, the output must simultaneously portray motion throughout the scene. Like previous work in video textures, our method employs min-cut optimization to select fragments of video that can be stitched together both spatially …
Intrinsically Motivated Reinforcement Learning: A Promising Framework For Developmental Robot Learning, Andrew Stout, George D. Konidaris, Andrew G. Barto
Intrinsically Motivated Reinforcement Learning: A Promising Framework For Developmental Robot Learning, Andrew Stout, George D. Konidaris, Andrew G. Barto
Computer Science Department Faculty Publication Series
One of the primary challenges of developmental robotics is the question of how to learn and represent increasingly complex behavior in a self-motivated, open-ended way. Barto, Singh, and Chentanez (Barto, Singh, & Chentanez 2004; Singh, Barto, & Chentanez 2004) have recently presented an algorithm for intrinsically motivated reinforcement learning that strives to achieve broad competence in an environment in a tasknonspecific manner by incorporating internal reward to build a hierarchical collection of skills. This paper suggests that with its emphasis on task-general, self-motivated, and hierarchical learning, intrinsically motivated reinforcement learning is an obvious choice for organizing behavior in developmental robotics. …
Mv Routing And Capacity Building In Disruption Tolerant Networks, Brendan Burns, Oliver Brock, Brian Neil Levine
Mv Routing And Capacity Building In Disruption Tolerant Networks, Brendan Burns, Oliver Brock, Brian Neil Levine
Computer Science Department Faculty Publication Series
Disruption Tolerant Networks (DTNs) require routing algorithms that are different from those designed for ad hoc networks. In DTNs, transport of data through the network is achieved through the physical movement of the participants in the network. We address two fundamental problems of routing in DTNs: routing algorithms with robust delivery rates, and management of networks where demand for routes does not match with the movement of peers. For the first problem, we propose the MV algorithm, which is based on observed meetings between peers and visits of peers to geographic locations. We show that our approach can achieve robust …
Efficiently Registering Video Into Panoramic Mosaics, Drew Steedly
Efficiently Registering Video Into Panoramic Mosaics, Drew Steedly
Computer Science Department Faculty Publication Series
We present an automatic and efficient method to register and stitch thousands of video frames into a large panoramic mosaic. Our method preserves the robustness and accuracy of image stitchers that match all pairs of images while utilizing the ordering information provided by video. We reduce the cost of searching for matches between video frames by adaptively identifying key frames based on the amount of image-to-image overlap. Key frames are matched to all other key frames, but intermediate video frames are only matched to temporally neighboring key frames and intermediate frames. Image orientations can be estimated from this sparse set …
Privacy Vulnerabilities In Encrypted Http Streams, George Dean Bissias
Privacy Vulnerabilities In Encrypted Http Streams, George Dean Bissias
Computer Science Department Faculty Publication Series
Encrypting traffic does not prevent an attacker from per- forming some types of traffic analysis. We present a straightforward traf- fic analysis attack against encrypted HTTP streams that is surprisingly effective in identifying the source of the traffic. An attacker starts by creating a profile of the statistical characteristics of web requests from interesting sites, including distributions of packet sizes and inter-arrival times. Later, candidate encrypted streams are compared against these profiles. In our evaluations using real traffic, we find that many web sites are subject to this attack. With a training period of 24 hours and a 1 hour …
Efficient Population Registration Of 3d Data, Lilla Zollei
Efficient Population Registration Of 3d Data, Lilla Zollei
Computer Science Department Faculty Publication Series
We present a population registration framework that acts on large collections or populations of data volumes. The data alignment procedure runs in a simultaneous fashion, with every member of the population approaching the central tendency of the collection at the same time. Such a mechanism eliminates the need for selecting a particular reference frame a priori, resulting in a non-biased estimate of a digital atlas. Our algorithm adopts an affine congealing framework with an information theoretic objective function and is optimized via a gradientbased stochastic approximation process embedded in a multi-resolution setting. We present experimental results on both synthetic and …
Proto-Value Functions: Developmental Reinforcement Learning, Sridhar Mahadevan
Proto-Value Functions: Developmental Reinforcement Learning, Sridhar Mahadevan
Computer Science Department Faculty Publication Series
This paper presents a novel framework called proto-reinforcement learning (PRL), based on a mathematical model of a proto-value function: these are task-independent basis functions that form the building blocks of all value functions on a given state space manifold. Proto-value functions are learned not from rewards, but instead from analyzing the topology of the state space. Formally, proto-value functions are Fourier eigenfunctions of the Laplace-Beltrami diffusion operator on the state space manifold. Proto-value functions facilitate structural decomposition of large state spaces, and form geodesically smooth orthonormal basis functions for approximating any value function. The theoretical basis for proto-value functions combines …
A Conditional Random Field For Discriminatively-Trained Finite-State String Edit Distance, Andrew Mccallum, Kedar Bellare, Fernando Pereira
A Conditional Random Field For Discriminatively-Trained Finite-State String Edit Distance, Andrew Mccallum, Kedar Bellare, Fernando Pereira
Computer Science Department Faculty Publication Series
The need to measure sequence similarity arises in information extraction, object identity, data mining, biological sequence analysis, and other domains. This paper presents discriminative string-edit CRFs, a finitestate conditional random field model for edit sequences between strings. Conditional random fields have advantages over generative approaches to this problem, such as pair HMMs or the work of Ristad and Yianilos, because as conditionally-trained methods, they enable the use of complex, arbitrary actions and features of the input strings. As in generative models, the training data does not have to specify the edit sequences between the given string pairs. Unlike generative models, …
Sampling-Based Motion Planning Using Predictive Models, Brendan Burns, Oliver Brock
Sampling-Based Motion Planning Using Predictive Models, Brendan Burns, Oliver Brock
Computer Science Department Faculty Publication Series
Robotic motion planning requires configuration space exploration. In high-dimensional configuration spaces, a complete exploration is computationally intractable. Practical motion planning algorithms for such high-dimensional spaces must expend computational resources in proportion to the local complexity of configuration space regions. We propose a novel motion planning approach that addresses this problem by building an incremental, approximate model of configuration space. The information contained in this model is used to direct computational resources to difficult regions, effectively addressing the narrow passage problem by adapting the sampling density to the complexity of that region. In addition, the expressiveness of the model permits predictive …
Optimal Peer Selection For P2p Downloading And Streaming, Micah Adler, Rakesh Kumar, Keith Ross, Dan Rubenstein, Torsten Suel, David D. Yao
Optimal Peer Selection For P2p Downloading And Streaming, Micah Adler, Rakesh Kumar, Keith Ross, Dan Rubenstein, Torsten Suel, David D. Yao
Computer Science Department Faculty Publication Series
In a P2P system, a client peer may select one or more server peers to download a specific file. In a P2P resource economy, the server peers charge the client for the downloading. A server peer’s price would naturally depend on the specific object being downloaded, the duration of the download, and the rate at which the download is to occur. The optimal peer selection problem is to select, from the set of peers that have the desired object, the subset of peers and download rates that minimizes cost. In this paper we examine a number of natural peer selection …
Re-Using Schematic Grasping Policies, Robert Platt
Re-Using Schematic Grasping Policies, Robert Platt
Computer Science Department Faculty Publication Series
It can be difficult to generalize the solutions to grasping and manipulation problems because even small differences in problem context can require qualitatively different solutions. For example, small changes in the shape of an object to be grasped can necessitate different grasp strategies. In this paper, we introduce the action schema framework that represents generalized skills in a functional way such that all viable ways of accomplishing a task are represented as instantiations of the generalized skill. We also propose an on-line algorithm for learning how to instantiate the skill in a context-appropriate way. We test this approach with a …
Tcp Connection Game: A Study On The Selfish Behavior Of Tcp Users, Honggang Zhang
Tcp Connection Game: A Study On The Selfish Behavior Of Tcp Users, Honggang Zhang
Computer Science Department Faculty Publication Series
We present a game-theoretic study of the selfish behavior of TCP users when they are allowed to use multiple concurrent TCP connections so as to maximize their goodputs or other utility functions. We refer to this as the TCP connection game. A central question we ask is whether there is a Nash Equilibrium in such a game, and if it exists, whether the network operates efficiently at such a Nash Equilibrium. Combined with the well known PFTK TCP Model [12], we study this question for three utility functions that differ in how they capture user behavior. The bad news is …
Collective Multi-Label Classification, Nadia Ghamrawi, Andrew Mccallum
Collective Multi-Label Classification, Nadia Ghamrawi, Andrew Mccallum
Computer Science Department Faculty Publication Series
Common approaches to multi-label classification learn independent classifiers for each category, and employ ranking or thresholding schemes for classification. Because they do not exploit dependencies between labels, such techniques are only well-suited to problems in which categories are independent. However, in many domains labels are highly interdependent. This paper explores multilabel conditional random field (CRF) classification models that directly parameterize label co-occurrences in multi-label classification. Experiments show that the models outperform their singlelabel counterparts on standard text corpora. Even when multilabels are sparse, the models improve subset classification error by as much as 40%.