Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 23 of 23
Full-Text Articles in Physical Sciences and Mathematics
Multi-Resolution Storage And Search In Sensor Networks, Deepak Ganesan
Multi-Resolution Storage And Search In Sensor Networks, Deepak Ganesan
Computer Science Department Faculty Publication Series
No abstract provided.
Designing Overlay Multicast Networks For Streaming, Ramesh Sitaraman
Designing Overlay Multicast Networks For Streaming, Ramesh Sitaraman
Computer Science Department Faculty Publication Series
In this paper we present a polynomial time approximation algorithm for designing a multicast overlay network. The algorithm finds a solution that satisfies capacity and reliability constraints to within a constant factor of optimal, and cost to within alogarithmic factor. The class of networks that our algorithm applies to includes the one used by Akamai Technologies to deliver live media streams over the Internet. In particular, we analyze networks consisting of three stages of nodes. The nodes in the first stage are the sources where live streams originate. A source forwards each of its streams to one or more nodes …
A Framework For Humanoid Control And Intelligence, Robert Platt
A Framework For Humanoid Control And Intelligence, Robert Platt
Computer Science Department Faculty Publication Series
One of the goals of humanoid research is the development of a humanoid capable of performing useful tasks in unknown or unpredictable environments. To address the complexities of this task, the robot must continually accumulate and utilize new control and perceptual knowledge. In this paper, we present a control framework for accomplishing this. Robot control policies can be learned at different levels of abstraction. We show how task-relevant perceptual features can be discovered that make better control policies possible. We also explore how trajectories of closed-loop policies can provide uniquely relevant state information. The approach presented in this paper is …
On Inferring And Characterizing Internet Routing Policies, Feng Wang
On Inferring And Characterizing Internet Routing Policies, Feng Wang
Computer Science Department Faculty Publication Series
Border Gateway Protocol allows Autonomous Systems (ASs) to apply diverse routing policies for selecting routes and for propagating reachability information to other ASs. Although a significant number of studies have been focused on the Internet topology, little is known about what routing policies network operators employ to configure their networks. In this paper, we infer and characterize routing policies employed in the Internet. We find that routes learned from customers are preferred over those from peers and providers, and those from peers are typically preferred over those from providers. We present an algorithm for inferring and characterizing export policies. We …
Augmenting Naive Bayes Classifiers With Statistical Language Models, Fuchun Peng
Augmenting Naive Bayes Classifiers With Statistical Language Models, Fuchun Peng
Computer Science Department Faculty Publication Series
We augment naive Bayes models with statistical n-gram language models to address short- comings of the standard naive Bayes text classifier. The result is a generalized naive Bayes classifier which allows for a local Markov dependence among observations; a model we re- fer to as the Chain Augmented Naive Bayes (CAN) Bayes classifier. CAN models have two advantages over standard naive Bayes classifiers. First, they relax some of the indepen- dence assumptions of naive Bayes—allowing a local Markov chain dependence in the observed variables—while still permitting efficient inference and learning. Second, they permit straight- forward application of sophisticated smoothing techniques …
Early Results For Named Entity Recognition With Conditional Random Fields, Feature Induction And Web-Enhanced Lexicons, Andrew Mccallum, Wei Li
Early Results For Named Entity Recognition With Conditional Random Fields, Feature Induction And Web-Enhanced Lexicons, Andrew Mccallum, Wei Li
Computer Science Department Faculty Publication Series
No abstract provided.
Toward Conditional Models Of Identity Uncertainty With Application To Proper Noun Coreference, Andrew Mccallum, Ben Wellner
Toward Conditional Models Of Identity Uncertainty With Application To Proper Noun Coreference, Andrew Mccallum, Ben Wellner
Computer Science Department Faculty Publication Series
Coreference analysis, also known as record linkage or identity uncertainty, is a difficult and important problem in natural language processing, databases, citation matching and many other tasks. This paper introduces several discriminative, conditionalprobability models for coreference analysis, all examples of undirected graphical models. Unlike many historical approaches to coreference, the models presented here are relational—they do not assume that pairwise coreference decisions should be made independently from each other. Unlike other relational models of coreference that are generative, the conditional model here can incorporate a great variety of features of the input without having to be concerned about their dependencies— …
Learning Assumptions For Compositional Verification, Jamieson M. Cobleigh
Learning Assumptions For Compositional Verification, Jamieson M. Cobleigh
Computer Science Department Faculty Publication Series
Compositional verification is a promising approach to addressing the state explosion problem associated with model checking. One compositional technique advocates proving properties of a system by checking properties of its components in an assume-guarantee style. However, the application of this technique is difficult because it involves non-trivial human input. This paper presents a novel framework for performing assume-guarantee reasoning in an incremental and fully automated fashion. To check a component against a property, our approach generates assumptions that the environment needs to satisfy for the property to hold. These assumptions are then discharged on the rest of the system. Assumptions …
Hierarchical Policy Gradient Algorithms, Mohammad Ghavamzadeh, Sridhar Mahadevan
Hierarchical Policy Gradient Algorithms, Mohammad Ghavamzadeh, Sridhar Mahadevan
Computer Science Department Faculty Publication Series
Hierarchical reinforcement learning is a general framework which attempts to accelerate policy learning in large domains. On the other hand, policy gradient reinforcement learning (PGRL) methods have received recent attention as a means to solve problems with continuous state spaces. However, they suffer from slow convergence. In this paper, we combine these two approaches and propose a family of hierarchical policy gradient algorithms for problems with continuous state and/or action spaces. We also introduce a class of hierarchical hybrid algorithms, in which a group of subtasks, usually at the higher-levels of the hierarchy, are formulated as value function-based RL (VFRL) …
A Knowledge Acquisition Tool For Course Of Action Analysis, Ken Barker, Jim Blythe, Gary Borchardt, Vinay K. Chaudhri, Peter E. Clark, Paul Cohen, Julie Fitzgerald, Ken Forbus, Yolanda Gil, Boris Katz, Jihie Kim, Gary King, Sunil Mishra, Clayton Morrison, Ken Murray, Charley Otstott, Bruce Porter, Robert C. Schrag, Tomás Uribe, Jeff Usher, Peter Z. Yeh
A Knowledge Acquisition Tool For Course Of Action Analysis, Ken Barker, Jim Blythe, Gary Borchardt, Vinay K. Chaudhri, Peter E. Clark, Paul Cohen, Julie Fitzgerald, Ken Forbus, Yolanda Gil, Boris Katz, Jihie Kim, Gary King, Sunil Mishra, Clayton Morrison, Ken Murray, Charley Otstott, Bruce Porter, Robert C. Schrag, Tomás Uribe, Jeff Usher, Peter Z. Yeh
Computer Science Department Faculty Publication Series
We present the novel application of a general-purpose knowledge-based system, SHAKEN, to the specific task of acquiring knowledge for military Course of Action (COA) analysis. We show how SHAKEN can capture and reuse expert knowledge for COA critiquing, which can then be used to produce high-level COA assessments through declarative inference and simulation. The system has been tested and evaluated by domain experts, and we report on the results. The generality of the approach makes it applicable to task analysis and knowledge capture in other domains. The primary objective of this work is to demonstrate the application of the knowledge …
A Comparison Of Hard-State And Soft-State Signaling Protocols, Ping Ji
A Comparison Of Hard-State And Soft-State Signaling Protocols, Ping Ji
Computer Science Department Faculty Publication Series
One of the key infrastructure components in all telecommunication networks, ranging from the telephone network, to VC-oriented data networks, to the Internet, is its signaling system. Two broad approaches towards signaling can be identified: so-called hard-state and soft-state approaches. Despite the fundamental importance of signaling, our understanding of these approaches - their pros and cons and the circumstances in which they might best be employed - is mostly anecdotal (and occasionally religious). In this paper, we compare and contrast a variety of signaling approaches ranging from a "pure" soft state, to soft-state approaches augmented with explicit state removal and/or reliable …
A Note On The Unification Of Information Extraction And Data Mining Using Conditional-Probability, Relational Models, Andrew Mccallum, David Jensen
A Note On The Unification Of Information Extraction And Data Mining Using Conditional-Probability, Relational Models, Andrew Mccallum, David Jensen
Computer Science Department Faculty Publication Series
Although information extraction and data mining appear together in many applications, their interface in most current systems would better be described as serial juxtaposition than as tight integration. Information extraction populates slots in a database by identifying relevant subsequences of text, but is usually not aware of the emerging patterns and regularities in the database. Data mining methods begin from a populated database, and are often unaware of where the data came from, or its inherent uncertainties. The result is that the accuracy of both suffers, and significant mining of complex text sources is beyond reach. This position paper proposes …
Table Extraction Using Conditional Random Fields, David Pinto
Table Extraction Using Conditional Random Fields, David Pinto
Computer Science Department Faculty Publication Series
The ability to find tables and extract information from them is a necessary component of data mining, question answering, and other information retrieval tasks. Documents often contain tables in order to communicate densely packed, multi-dimensional information. Tables do this by employing layout patterns to efficiently indicate fields and records in two-dimensional form. Their rich combination of formatting and content present difficulties for traditional language modeling techniques, however. This paper presents the use of conditional random fields (CRFs) for table extraction, and compares them with hidden Markov models (HMMs). Unlike HMMs, CRFs support the use of many rich and overlapping layout …
Mobile Distributed Information Retrieval For Highly-Partitioned Networks, Katrina M. Hanna, Brian Neil Levine, R. Manmatha
Mobile Distributed Information Retrieval For Highly-Partitioned Networks, Katrina M. Hanna, Brian Neil Levine, R. Manmatha
Computer Science Department Faculty Publication Series
We propose and evaluate a mobile, peer-to-peer Information Retrieval system. Such a system can, for example, support medical care in a disaster by allowing access to a large collections of medical literature. In our system, documents in a collection are replicated in an overlapping manner at mobile peers. This provides resilience in the face of node failures, malicious attacks, and network partitions. We show that our design manages the randomness of node mobility. Although nodes contact only direct neighbors (who change frequently) and do not use any ad hoc routing, the system maintains good IR performance. This makes our design …
Dynamic Resource Allocation For Shared Data Centers Using Online Measurements, Abhishek Chandra, Weibo Gong, Prashant Shenoy
Dynamic Resource Allocation For Shared Data Centers Using Online Measurements, Abhishek Chandra, Weibo Gong, Prashant Shenoy
Computer Science Department Faculty Publication Series
Since web workloads are known to vary dynamically with time, in this paper, we argue that dynamic resource allocation techniques are necessary to provide guarantees to web applications running on shared data centers. To address this issue, we use a system architecture that combines online measurements with prediction and resource allocation techniques. To capture the transient behavior of the application workloads, we model a server resource using a time-domain description of a generalized processor sharing (GPS) server. This model relates application resource requirements to their dynamically changing workload characteristics. The parameters of this model are continuously updated using an online …
Quantifying The Benefits Of Resource Multiplexing In On-Demand Data Centers, Abhishek Chandra, Pawan Goyal, Prashant Shenoy
Quantifying The Benefits Of Resource Multiplexing In On-Demand Data Centers, Abhishek Chandra, Pawan Goyal, Prashant Shenoy
Computer Science Department Faculty Publication Series
On-demand data centers host multiple applications on server farms by dynamically provisioning resources in response to workload variations. The efficiency of such dynamic provisioning on the required server farm capacity is dependent on several factors — the granularity and frequency of reallocation, the number of applications being hosted, the amount of resource overprovisioning and the accuracy of workload prediction. In this paper, we quantify the effect of these factors on the multiplexing benefits achievable in an on-demand data center. Using traces of real e-commerce workloads, we demonstrate that the ability to allocate fractional server resources at fine time-scales of tens …
Simple Estimators For Relational Bayesian Classifiers, Jennifer Neville
Simple Estimators For Relational Bayesian Classifiers, Jennifer Neville
Computer Science Department Faculty Publication Series
This paper evaluates several modifications of the Simple Bayesian Classifier to enable estimation and inference over relational data. The resulting Relational Bayesian Classifiers are evaluated on three real-world datasets and compared to a baseline SBC using no relational information. The approach we call INDEPVAL achieves the best results. We use synthetic data sets to further explore performance as relational data characteristics vary.
Interactive Color Mosaic And Dendrogram Displays For Signal/Noise Optimization In Microarray Data Analysis, Jinwook Seo
Interactive Color Mosaic And Dendrogram Displays For Signal/Noise Optimization In Microarray Data Analysis, Jinwook Seo
Computer Science Department Faculty Publication Series
Data analysis and visualization is strongly influenced by noise and noise filters. There are multiple sources of “noise” in microarray data analysis, but signal/noise ratios are rarely optimized, or even considered. Here, we report a noise analysis of a novel 13 million oligonucleotide dataset - 25 human U133A (~500,000 features) profiles of patient muscle biposies. We use our recently described interactive visualization tool, the Hierarchical Clustering Explorer (HCE) to systemically address the effect of different noise filters on resolution of arrays into “correct” biological groups (unsupervised clustering into three patient groups of known diagnosis). We varied probe set interpretation methods …
Scalability And Schedulability In Large, Coordinated, Distributed Robot Systems, John D. Sweeney
Scalability And Schedulability In Large, Coordinated, Distributed Robot Systems, John D. Sweeney
Computer Science Department Faculty Publication Series
Multiple, independent robot platforms promise significant advantage with respect to robustness and flexibility. However, coordination between otherwise independent robots requires the exchange of information; either implicitly (as in gestural communication), or explicitly (as in message passing in a communication network.) In either case, control processes resident on all coordinated peers must participate in the collective behavior. This paper evaluates the potential to scale such a coupled control framework to many participating individuals, where scalability is evaluated in terms of the schedulability of coupled, distributed control processes. We examine how schedulability affects the scalability of a robot system, and discuss an …
Srl2003 Ijcai 2003 Workshop On Learning Statistical Models From Relational Data, Lise Getoor
Srl2003 Ijcai 2003 Workshop On Learning Statistical Models From Relational Data, Lise Getoor
Computer Science Department Faculty Publication Series
No abstract provided.
Learning To Exploit Dynamics For Robot Motor Coordination, Michael T. Rosenstein
Learning To Exploit Dynamics For Robot Motor Coordination, Michael T. Rosenstein
Computer Science Department Faculty Publication Series
Humans exploit dynamics—gravity, inertia, joint coupling, elasticity, and so on—as a regular part of skillful, coordinated movements. Such movements comprise everyday activities, like reaching and walking, as well as highly practiced maneuvers as used in athletics and the performing arts. Robots, especially industrial manipulators, instead use control schemes that ordinarily cancel the complex, nonlinear dynamics that humans use to their advantage. Alternative schemes from the machine learning and intelligent control communities offer a number of potential benefits, such as improved efficiency, online skill acquisition, and tracking of nonstationary environments. However, the success of such methods depends a great deal on …
Relativized Options: Choosing The Right Transformation, Balaraman Ravindran, Andrew G. Barto
Relativized Options: Choosing The Right Transformation, Balaraman Ravindran, Andrew G. Barto
Computer Science Department Faculty Publication Series
Relativized options combine model minimization methods and a hierarchical reinforcement learning framework to derive compact reduced representations of a related family of tasks. Relativized options are defined without an absolute frame of reference, and an option's policy is transformed suitably based on the circumstances under which the option is invoked. In earlier work we addressed the issue of learning the option policy online. In this article we develop an alogrithm for choosing, from among a set of candidate transformations, the right transformation for each member of the family of tasks.
Tracking Student Propositions In An Inquiry System, Beverly Park Woolf, David Marshall, Matthew Mattingly, Joshua Lewis, Sean Wright, Michael Jellison, Tom Murray
Tracking Student Propositions In An Inquiry System, Beverly Park Woolf, David Marshall, Matthew Mattingly, Joshua Lewis, Sean Wright, Michael Jellison, Tom Murray
Computer Science Department Faculty Publication Series
We built software to support student reasoning about a phenomenon and development of hypotheses to explain it. The goal is to engage students in asking questions, generating hypotheses and testing predictions. Rashi, an intelligent tutor, tracks students’ investigations (e.g., hypotheses, questions, data collection, and inferences) and helps articulate how evidence and theories are related. The tutor provides advice, such as recognizing when data does not support a hypothesis Cases are presented in geology, biology or engineering, and students are scaffolded to use an inquiry-based approach to posit a theory to explain the situation. Generic and reusable structured tools guide students …