Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Keyword
- Publication
- Publication Type
Articles 1 - 30 of 36
Full-Text Articles in Physical Sciences and Mathematics
Sign Detection In Natural Images With Conditional Random Fields, Jerod Weinman
Sign Detection In Natural Images With Conditional Random Fields, Jerod Weinman
Computer Science Department Faculty Publication Series
Traditional generative Markov random fields for segmenting images model the image data and corresponding labels jointly, which requires extensive independence assumptions for tractability. We present the conditional random field for an application in sign detection, using typical scale and orientation selective texture filters and a nonlinear texture operator based on the grating cell. The resulting model captures dependencies between neighboring image region labels in a data-dependent way that escapes the difficult problem of modeling image formation, instead focusing effort and computation on the labeling task. We compare the results of training the model with pseudo-likelihood against an approximation of the …
Is Necessity The Mother Of Innovation? The Adoption And Use Of Web Technologies Among Congressional Offices, Kevin M. Esterling, David M.J. Lazer, Michael Neblo
Is Necessity The Mother Of Innovation? The Adoption And Use Of Web Technologies Among Congressional Offices, Kevin M. Esterling, David M.J. Lazer, Michael Neblo
National Center for Digital Government
From first paragraph: Communication between legislator and constituents is fundamental to effective democratic representation, and devising the institutional means for citizen/legislator communication stands as one of the core and persistent problems in the practice of democracy. A legislator needs information about the preferences, ideals, norms, and beliefs of her constituents in order to do her job well. Similarly, citizens need information about the actions and decisions of their representative in order to maintain appropriate accountability. But as national problems become more complex, and as the political process grows more and more dominated by experts and organized groups, it is becoming …
Confidence Estimation For Information Extraction, Aron Culotta, Andrew Mccallum
Confidence Estimation For Information Extraction, Aron Culotta, Andrew Mccallum
Andrew McCallum
Information extraction techniques automatically create structured databases from unstructured data sources, such as the Web or newswire documents. Despite the successes of these systems, accuracy will always be imperfect. For many reasons, it is highly desirable to accurately estimate the confidence the system has in the correctness of each extracted field. The information extraction system we evaluate is based on a linear-chain conditional random field (CRF), a probabilistic model which has performed well on information extraction tasks because of its ability to capture arbitrary, overlapping features of the input in a Markov model. We implement several techniques to estimate the …
Sign Detection In Natural Images With Conditional Random Fields, Jerod Weinman, Allen Hanson, Andrew Mccallum
Sign Detection In Natural Images With Conditional Random Fields, Jerod Weinman, Allen Hanson, Andrew Mccallum
Andrew McCallum
Traditional generative Markov random fields for segmenting images model the image data and corresponding labels jointly, which requires extensive independence assumptions for tractability. We present the conditional random field for an application in sign detection, using typical scale and orientation selective texture filters and a nonlinear texture operator based on the grating cell. The resulting model captures dependencies between neighboring image region labels in a data-dependent way that escapes the difficult problem of modeling image formation, instead focusing effort and computation on the labeling task. We compare the results of training the model with pseudo-likelihood against an approximation of the …
Table Extraction For Answer Retrieval, Xing Wei, Bruce Croft, Andrew Mccallum
Table Extraction For Answer Retrieval, Xing Wei, Bruce Croft, Andrew Mccallum
Andrew McCallum
The ability to find tables and extract information from them is a necessary component of question answering and other information retrieval tasks. Documents often contain tables in order to communicate densely packed, multidimensional 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 retrieval techniques. This paper describes techniques for extracting tables from text and retrieving answers from the extracted information. We compare machine learning (especially conditional random fields) and heuristic methods for table extraction. Our approach creates a cell document, which …
Interactive Information Extraction With Constrained Conditional Random Fields, Trausti Kristjansson, Aron Culotta, Paul Viola, Andrew Mccallum
Interactive Information Extraction With Constrained Conditional Random Fields, Trausti Kristjansson, Aron Culotta, Paul Viola, Andrew Mccallum
Andrew McCallum
Information Extraction methods can be used to automatically "fill-in" database forms from unstructured data such as Web documents or email. State-of-the-art methods have achieved low error rates but invariably make a number of errors. The goal of an Interactive Information Extraction system is to assist the user in filling in database fields while giving the user confidence in the integrity of the data. The user is presented with an interactive interface that allows both the rapid verification of automatic field assignments and the correction of errors. In cases where there are multiple errors, our system takes into account user corrections, …
Piecewise Training With Parameter Independence Diagrams: Comparing Globally- And Locally-Trained Linear-Chain Crfs, Andrew Mccallum, Charles Sutton
Piecewise Training With Parameter Independence Diagrams: Comparing Globally- And Locally-Trained Linear-Chain Crfs, Andrew Mccallum, Charles Sutton
Andrew McCallum
We present a diagrammatic formalism and practial methods for introducing additional independence assumptions into parameter estimation, enabling efficient training of undirected graphical models in locally-normalized pieces. On two real-world data sets we demonstrate our locally-trained linear-chain CRFs outperforming traditional CRFs--training in less than one-fifth the time, and providing a statistically-significant gain in accuracy.
An Exploration Of Entity Models, Collective Classification And Relation Description, Hema Raghavan, James Allan, Andrew Mccallum
An Exploration Of Entity Models, Collective Classification And Relation Description, Hema Raghavan, James Allan, Andrew Mccallum
Andrew McCallum
Traditional information retrieval typically represents data using a bag of words; data mining typically uses a highly structured database ontology. This paper explores the a middle ground we term entity models, in which questions about structured data may be posed and answered, but the complexities and task-specific restrictions of ontologies are avoided. An entity model is a language model or word distribution associated with an entity, such as a person, place or organization. Using these per-entity language models, entities may be clustered, links may be detected or described with a short summary, entities may be collectively classified, and question answering …
Collective Segmentation And Labeling Of Distant Entities In Information Extraction, Charles Sutton, Andrew Mccallum
Collective Segmentation And Labeling Of Distant Entities In Information Extraction, Charles Sutton, Andrew Mccallum
Andrew McCallum
In information extraction, we often wish to identify all mentions of an entity, such as a person or organization. Traditionally, a group of words is labeled as an entity based only on local information. But information from throughout a document can be useful; for example, if the same word is used multiple times, it is likely to have the same label each time. We present a CRF that explicitly represents dependencies between the labels of pairs of similar words in a document. On a standard information extraction data set, we show that learning these dependencies leads to a 13.7% reduction …
Classification Models For New Event Detection, Girdhar Kumaran, James Allan, Andrew Mccallum
Classification Models For New Event Detection, Girdhar Kumaran, James Allan, Andrew Mccallum
Andrew McCallum
New event detection (NED) involves monitoring news streams to detect the stories that report on new events. In this paper we explore the application of machine learning classification techniques for this task. We introduce the concept of triangulation with illustrative examples. We develop new features that build on this concept, and the named entities present in a document. The classifiers we developed showed significant and consistent improvement over the baseline vector space model system, on all the collections we tested on. Analysis of the performance of our classifiers suggests the utility of named entities, and the applicability of machine learning …
Accurate Information Extraction From Research Papers Using Conditional Random Fields, Fuchun Peng, Andrew Mccallum
Accurate Information Extraction From Research Papers Using Conditional Random Fields, Fuchun Peng, Andrew Mccallum
Andrew McCallum
With the increasing use of research paper search engines, such as CiteSeer, for both literature search and hiring decisions, the accuracy of such systems is of paramount importance. This paper employs Conditional Random Fields (CRFs) for the task of extracting various common fields from the headers and citation of research papers. The basic theory of CRFs is becoming well-understood, but best-practices for applying them to real-world data require additional exploration. This paper makes an empirical exploration of several factors, including variations on Gaussian, exponential and hyperbolic-L1 priors for improved regularization, and several classes of features and Markov order. On a …
A Note On Semi-Supervised Learning Using Markov Random Fields, Wei Li, Andrew Mccallum
A Note On Semi-Supervised Learning Using Markov Random Fields, Wei Li, Andrew Mccallum
Andrew McCallum
This paper describes conditional-probability training of Markov random fields using combinations of labeled and unlabeled data. We capture the similarities between instances learning the appropriate distance metric from the data. The likelihood model and several training procedures are presented.
Chinese Segmentation And New Word Detection Using Conditional Random Fields, Fuchun Peng, Fangfang Feng, Andrew Mccallum
Chinese Segmentation And New Word Detection Using Conditional Random Fields, Fuchun Peng, Fangfang Feng, Andrew Mccallum
Andrew McCallum
Chinese word segmentation is a difficult, important and widely-studied sequence modeling problem. This paper demonstrates the ability of linear-chain conditional random fields (CRFs) to perform robust and accurate Chinese word segmentation by providing a principled framework that easily supports the integration of domain knowledge in the form of multiple lexicons of characters and words. We also present a probabilistic new word detection method, which further improves performance. Our system is evaluated on four datasets used in a recent comprehensive Chinese word segmentation competition. State-of-the-art performance is obtained.
Extracting Social Networks And Contact Information From Email And The Web, Aron Culotta, Ron Bekkerman, Andrew Mccallum
Extracting Social Networks And Contact Information From Email And The Web, Aron Culotta, Ron Bekkerman, Andrew Mccallum
Computer Science Department Faculty Publication Series
We present an end-to-end system that extracts a user’s social network and its members’ contact information given the user’s email inbox. The system identifies unique people in email, finds theirWeb presence, and automatically fills the fields of a contact address book using conditional random fields—a type of probabilistic model well-suited for such information extraction tasks. By recursively calling itself on new people discovered on the Web, the system builds a social network with multiple degrees of separation from the user. Additionally, a set of expertise-describing keywords are extracted and associated with each person. We outline the collection of statistical and …
Dynamic Conditional Random Fields: Factorized Probabilistic Models For Labeling And Segmenting Sequence Data, Charles Sutton, Khashayar Rohanimanesh, Andrew Mccallum
Dynamic Conditional Random Fields: Factorized Probabilistic Models For Labeling And Segmenting Sequence Data, Charles Sutton, Khashayar Rohanimanesh, Andrew Mccallum
Computer Science Department Faculty Publication Series
In sequence modeling, we often wish to represent complex interaction between labels, such as when performing multiple, cascaded labeling tasks on the same sequence, or when longrange dependencies exist. We present dynamic conditional random fields (DCRFs), a generalization of linear-chain conditional random fields (CRFs) in which each time slice contains a set of state variables and edges—a distributed state representation as in dynamic Bayesian networks (DBNs)—and parameters are tied across slices. Since exact inference can be intractable in such models, we perform approximate inference using several schedules for belief propagation, including tree-based reparameterization (TRP). On a natural-language chunking task, we …
Decentralized Control Of Cooperative Systems: Categorization And Complexity Analysis, Claudia V. Goldman, Shlomo Zilberstein
Decentralized Control Of Cooperative Systems: Categorization And Complexity Analysis, Claudia V. Goldman, Shlomo Zilberstein
Computer Science Department Faculty Publication Series
Decentralized control of cooperative systems captures the operation of a group of decision-makers that share a single global objective. The difficulty in solving optimally such problems arises when the agents lack full observability of the global state of the system when they operate. The general problem has been shown to be NEXP-complete. In this paper, we identify classes of decentralized control problems whose complexity ranges between NEXP and P. In particular, we study problems characterized by independent transitions, independent observations, and goal-oriented objective functions. Two algorithms are shown to solve optimally useful classes of goal-oriented decentralized processes in polynomial time. …
Analysis Of Statistical Question Classification For Fact-Based Questions, Donald Metzler
Analysis Of Statistical Question Classification For Fact-Based Questions, Donald Metzler
Computer Science Department Faculty Publication Series
No abstract provided.
Chinese Segmentation And New Word Detection Using Conditional Random Fields, Fuchun Peng
Chinese Segmentation And New Word Detection Using Conditional Random Fields, Fuchun Peng
Computer Science Department Faculty Publication Series
Chinese word segmentation is a difficult, important and widely-studied sequence modeling problem. This paper demonstrates the ability of linear-chain conditional random fields (CRFs) to perform robust and accurate Chinese word segmentation by providing a principled framework that easily supports the integration of domain knowledge in the form of multiple lexicons of characters and words. We also present a probabilistic new word detection method, which further improves performance. Our system is evaluated on four datasets used in a recent comprehensive Chinese word segmentation competition. State-of-the-art performance is obtained.
Inferring Unobservable Learning Variables From Students’ Help Seeking Behavior, Ivon Arroyo
Inferring Unobservable Learning Variables From Students’ Help Seeking Behavior, Ivon Arroyo
Computer Science Department Faculty Publication Series
Results of an evaluation of students’ attitudes and their relationship to student behaviors within a tutoring system are presented. Starting from a correlation analysis that integrates survey-collected student attitudes, learning variables, and behaviors while using the tutor, we constructed a Bayesian Network that infers attitudes and perceptions towards help and the tutoring system.
Dependency Networks For Relational Data, Jennifer Neville
Dependency Networks For Relational Data, Jennifer Neville
Computer Science Department Faculty Publication Series
Instance independence is a critical assumption of traditional machine learning methods contradicted by many relational datasets. For example, in scientific literature datasets there are dependencies among the references of a paper. Recent work on graphical models for relational data has demonstrated significant performance gains for models that exploit the dependencies among instances. In this paper, we present relational dependency networks (RDNs), a new form of graphical model capable of reasoning with such dependencies in a relational setting. We describe the details of RDN models and outline their strengths, most notably the ability to learn and reason with cyclic relational dependencies. …
Learning To Communicate And Act Using Hierarchical Reinforcement Learning, Mohammad Ghavamzadeh, Sridhar Mahadevan
Learning To Communicate And Act Using Hierarchical Reinforcement Learning, Mohammad Ghavamzadeh, Sridhar Mahadevan
Computer Science Department Faculty Publication Series
In this paper, we address the issue of rational communication behavior among autonomous agents. The goal is for agents to learn a policy to optimize the communication needed for proper coordination, given the communication cost. We extend our previously reported cooperative hierarchical reinforcement learning (HRL) algorithm to include communication decisions and propose a new multiagent HRL algorithm, called COM-Cooperative HRL. In this algorithm, we define cooperative subtasks to be those subtasks in which coordination among agents significantly improves the performance of the overall task. Those levels of the hierarchy which include cooperative subtasks are called cooperation levels. Coordination skills among …
Umass At Trec 2004: Novelty And Hard, Nasreen Abdul-Jaleel, James Allan, W. Bruce Croft, Fernando Diaz, Leah Larkey, Xiaoyan Li, Mark D. Smucker, Courtney Wade
Umass At Trec 2004: Novelty And Hard, Nasreen Abdul-Jaleel, James Allan, W. Bruce Croft, Fernando Diaz, Leah Larkey, Xiaoyan Li, Mark D. Smucker, Courtney Wade
Computer Science Department Faculty Publication Series
For the TREC 2004 Novelty track, UMass participated in all four tasks. Although finding relevant sentences was harder this year than last, we continue to show marked improvements over the baseline of calling all sentences relevant, with a variant of tfidf being the most successful approach. We achieve 5–9%improvements over the baseline in locating novel sentences, primarily by looking at the similarity of a sentence to earlier sentences and focusing on named entities. For the High Accuracy Retrieval from Documents (HARD) track, we investigated the use of clarification forms, fixed- and variable-length passage retrieval, and the use of metadata. Clarification …
An Integrated, Conditional Model Of Information Extraction And Coreference With Application To Citation Matching, Ben Wellner, Andrew Mccallum, Fuchun Peng, Michael Hay
An Integrated, Conditional Model Of Information Extraction And Coreference With Application To Citation Matching, Ben Wellner, Andrew Mccallum, Fuchun Peng, Michael Hay
Computer Science Department Faculty Publication Series
Although information extraction and coref- erence resolution appear together in many applications, most current systems perform them as independent steps. This paper describes an approach to integrated infer- ence for extraction and coreference based on conditionally-trained undirected graphical models. We discuss the advantages of condi- tional probability training, and of a corefer- ence model structure based on graph parti- tioning. On a data set of research paper cita- tions, we show significant reduction in error by using extraction uncertainty to improve coreference citation matching accuracy, and using coreference to improve the accuracy of the extracted fields.
Hard Track Overview In Trec 2004 High Accuracy Retrieval From Documents, James Allan
Hard Track Overview In Trec 2004 High Accuracy Retrieval From Documents, James Allan
Computer Science Department Faculty Publication Series
The High Accuracy Retrieval from Documents HARD track explores methods for improving the accuracy of document retrieval systems. It does so by considering three questions. Can additional metadata about the query, the searcher, or the context of the search provide more focused and, therefore, more accurate results These metadata items generally do not directly affect whether or not a document is on topic, but they do affect whether it is relevant. For example, a person looking for introductory material will not find an on-topic but highly technical document relevant. Can highly focused, short-duration, interaction with the searcher be used to …
Using Maximum Entropy For Automatic Image Annotation, Jiwoon Jeon, R Manmatha
Using Maximum Entropy For Automatic Image Annotation, Jiwoon Jeon, R Manmatha
Computer Science Department Faculty Publication Series
In this paper, we propose the use of the Maximum Entropy approach for the task of automatic image annotation. Given labeled training data, Maximum Entropy is a statistical technique which allows one to predict the probability of a label given test data. The techniques allow for relationships between features to be effectively captured. and has been successfully applied to a number of language tasks including machine translation. In our case, we view the image annotation task as one where a training data set of images labeled with keywords is provided and we need to automatically label the test images with …
Inducing Heuristics To Decide Whether To Schedule, John Cavazos
Inducing Heuristics To Decide Whether To Schedule, John Cavazos
Computer Science Department Faculty Publication Series
Instruction scheduling is a compiler optimization that can improve program speed, sometimes by 10% or more—but it can also be expensive. Furthermore, time spent optimizing is more important in a Java just-in-time (JIT) compiler than in a traditional one because a JIT compiles code at run time, adding to the running time of the program. We found that, on any given block of code, instruction scheduling often does not produce significant benefit and sometimes degrades speed. Thus, we hoped that we could focus scheduling effort on those blocks that benefit from it. Using supervised learning we induced heuristics to predict …
Optimal Peer Selection In A Free-Market Peer-Resource Economy, Micah Adler, Rakesh Kumar, Keith Ross, Dan Rubenstein, David Turner, David D. Yao
Optimal Peer Selection In A Free-Market Peer-Resource Economy, Micah Adler, Rakesh Kumar, Keith Ross, Dan Rubenstein, David Turner, David D. Yao
Computer Science Department Faculty Publication Series
In a P2P free-market resource economy a client peer may want to select multiple server peers for either downloading a file or streaming a stored audio or video object. In general, multiple server peers will make the object available, with each peer offering a different price. The optimal peer selection problem is to select from a subset of the peers those peers that can provide the service at lowest cost. In this paper we formulate and solve the problem of optimally selecting a subset of peers for parallel downloading and for parallel streaming.
Automatic Categorization Of Email Into Folders: Benchmark Experiments On Enron And Sri Corpora, Ron Bekkerman
Automatic Categorization Of Email Into Folders: Benchmark Experiments On Enron And Sri Corpora, Ron Bekkerman
Computer Science Department Faculty Publication Series
Once workers everywhere are drowning in email|not only spam, but also large quan- tities of legitimate email to be read and organized for browsing. Although there have been extensive investigations of automatic document categorization, email gives rise to a num- ber of unique challenges, and there has been relatively little study of classifying email into folders. This paper presents an extensive benchmark study of email foldering using two large corpora of real-world email messages and foldering schemes: one from former Enron em- ployees, another from participants in an SRI research project. We discuss the challenges that arise from differences between …
Verification Of Mpi-Based Software For Scientific Computation, Stephen F. Siegel
Verification Of Mpi-Based Software For Scientific Computation, Stephen F. Siegel
Computer Science Department Faculty Publication Series
We explore issues related to the application of finite-state verification techniques to scientific computation software employing the widely-used Message-Passing Interface (MPI). Many of the features of MPI that are important for programmers present significant difficulties for model checking. In this paper, we examine a small parallel program that computes the evolution in time of a discretized function u defined on a 2-dimensional domain and governed by the diffusion equation. Although this example is simple, it makes use of many of the problematic features of MPI. We discuss the modeling of these features and use Spin and INCA to verify several …
Solving Transition Independent Decentralized Markov Decision Processes, Raphen Becker
Solving Transition Independent Decentralized Markov Decision Processes, Raphen Becker
Computer Science Department Faculty Publication Series
Formal treatment of collaborative multi-agent systems has been lagging behind the rapid progress in sequential decision making by individual agents. Recent work in the area of decentralized Markov Decision Processes (MDPs) has contributed to closing this gap, but the computational complexity of these models remains a serious obstacle. To overcome this complexity barrier, we identify a specific class of decentralized MDPs in which the agents’ transitions are independent. The class consists of independent collaborating agents that are tied together through a structured global reward function that depends on all of their histories of states and actions. We present a novel …