CiteULike: markusd's library [226 articles]

Hierarchical Dirichlet Processes

Teh — 2006-11-29T01:37:01-00:00

Journal of the American Statistical Association, Vol. 101, No. 476. (December 2006), pp. 1566-1581.

Design of the Moses Decoder for Statistical Machine Translation

Hieu Hoang — 2008-06-18T17:53:32-00:00

(June 2008), pp. 58-65.

Fully Distributed EM for Very Large Datasets

Jason Wolfe — 2008-06-23T14:31:04-00:00

(2008)

In EM and related algorithms, E-step compu- tations distribute easily, because data items are independent given parameters. For very large data sets, however, even storing all of the parameters in a single node for the M- step can be impractical. We present a frame- work that fully distributes the entire EM pro- cedure. Each node interacts only with pa- rameters relevant to its data, sending mes- sages to other nodes along a junction-tree topology. We demonstrate improvements over a MapReduce topology, on two tasks: word alignment and topic modeling.

Syntactic Reordering Integrated with Phrase-Based SMT

Jakob Elming — 2008-06-24T10:25:47-00:00

(2008), pp. 46-54.

We present a novel approach to word re- ordering which successfully integrates syn- tactic structural knowledge with phrase-based SMT. This is done by constructing a lattice of alternatives based on automatically learned probabilistic syntactic rules. In decoding, the alternatives are scored based on the output word order, not the order of the input. Un- like previous approaches, this makes it possi- ble to successfully integrate syntactic reorder- ing with phrase-based SMT. On an English- Danish task, we achieve an absolute improve- ment in translation quality of 1.1 % BLEU. Manual evaluation supports the claim that the present approach is signiﬁcantly superior to previous approaches.

Multiple Reorderings in Phrase-Based Machine Translation

Niyu Ge — 2008-06-25T10:29:26-00:00

(June 2008), pp. 61-68.

A New String-to-Dependency Machine Translation Algorithm with a Target Dependency Language Model

Libin Shen — 2008-06-26T15:57:47-00:00

(June 2008), pp. 577-585.

Modeling Online Reviews with Multi-Grain Topic Models

Ivan Titov — 2008-07-15T12:32:33-00:00

(2008)

Name Translation in Statistical Machine Translation - Learning When to Transliterate

Ulf Hermjakob — 2008-07-15T15:24:10-00:00

(June 2008), pp. 389-397.

Measuring Word Alignment Quality for Statistical Machine Translation.

Alex Fraser — 2008-07-15T18:25:08-00:00

Computational Linguistics, Vol. 33, No. 3. (2007), pp. 293-303.

Accurate Max-margin Training for Structured Output Spaces.

Sunita Sarawagi — 2008-06-18T07:55:10-00:00

(2008)

Bayesian Probabilistic Matrix Factorization using Markov Chain Monte Carlo.

Salakhyuditnov — 2008-06-21T04:03:24-00:00

(2008)

Learning Classifiers from Only Positive and Unlabeled Data

Charles Elkan — 2008-07-17T00:09:48-00:00

(2008)

An Algorithm to Determine Peer-Reviewers

Marko Rodriguez — 2007-07-19T08:51:55-00:00

(24 May 2006)

The peer-review process is the most widely accepted certification mechanism for legitimizing the written results of researchers within the scientific community. An essential component of this process is the identification of competent referees to review a submitted manuscript. This paper presents an algorithm to automatically determine the most appropriate reviewers for a manuscript by way of a co-authorship network data structure and a relative-rank particle-swarm algorithm. This approach is novel in that it is not limited to a pre-selected set of referees, is computationally efficient, requires no human-intervention, and can automatically identify conflict of interest situations. The algorithm is validated using referee bid data from the 2005 Joint Conference on Digital Libraries.

The Dynamic Hierarchical Dirichlet Process

Lu Ren — 2008-07-15T09:38:33-00:00

(2008)

Ultraconservative Online Algorithms for Multiclass Problems

Koby Crammer — 2008-07-17T17:35:49-00:00

Vol. 2111 (2001), pp. 99-115.

In this paper we study a paradigm to generalize online classification algorithms for binary classification problems to multiclass problems. The particular hypotheses we investigate maintain one prototype vector per class. Given an input instance, a multiclass hypothesis computes a similarityscore between each prototype and the input instance and sets the predicted label to be the index of the prototype achieving the highest similarity. To design and analyze the learning algorithms in this...

Arabic morphology using only finite-state operations

K Beesley — 2007-05-23T12:19:30-00:00

Finite-state morphology has been successful in the description and computational implementation of a wide variety of natural languages. However, the particular challenges of Arabic, and the limitations of some implementations of finite-state morphology, have led many researchers to believe that finite-state power was not sufficient to handle Arabic and other Semitic morphology. This paper illustrates how the morphotactics and the variation rules of Arabic have been described using only...

Nonparametric Bayesian Discrete Latent Variable Models for Unsupervised Learning

Dilan Görür — 2008-06-10T15:21:35-00:00

(20 April 2007)

A Discriminative Latent Variable Model for Statistical Machine Translation

Phil Blunsom — 2008-06-09T17:01:36-00:00

(2008)

Discriminative Word Alignment with Conditional Random Fields

Phil Blunsom — 2008-06-05T14:51:15-00:00

(July 2006), pp. 65-72.

Grafting: fast, incremental feature selection by gradient descent in function space

Simon Perkins — 2005-11-22T17:56:36-00:00

J. Mach. Learn. Res., Vol. 3 (2003), pp. 1333-1356.

ParaMor: Minimally Supervised Induction of Paradigm Structure and Morphological Analysis

Christian Monson — 2008-05-31T21:16:22-00:00

(June 2007), pp. 117-125.

Efficient Multi-pass Decoding for Synchronous Context Free Grammars

Hao Zhang — 2008-04-10T16:25:23-00:00

(2008)

We take a multi-pass approach to ma- chine translation decoding when using syn- chronous context-free grammars as the trans- lation model and n-gram language models: the ﬁrst pass uses a bigram language model, and the resulting parse forest is used in the second pass to guide search with a trigram lan- guage model. The trigram pass closes most of the performance gap between a bigram de- coder and a much slower trigram decoder, but takes time that is insigniﬁcant in comparison to the bigram pass. An additional fast de- coding pass maximizing the expected count of correct translation hypotheses increases the BLEU score signiﬁcantly.

Phonological Constraints and Morphological Preprocessing for Grapheme-to-Phoneme Conversion

Vera Demberg — 2008-05-31T19:52:48-00:00

(June 2007), pp. 96-103.

Latent Dirichlet allocation

D Blei — 2005-12-15T14:31:27-00:00

(2002)

We describe latent Dirichlet allocation (LDA), a generative probabilistic model for collections of discrete data such as text corpora. LDA is a three-level hierarchical Bayesian model, in which each item of a collection is modeled as a finite mixture over an underlying set of topics. Each topic is, in turn, modeled as an infinite mixture over an underlying set of topic probabilities. In the context of text modeling, the topic probabilities provide an explicit representation of a document....

Inducing Features of Random Fields

Stephen Della Pietra — 2008-05-27T14:26:23-00:00

IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 19, No. 4. (1997), pp. 380-393.

We present a technique for constructing random fields from a set of training samples. The learning paradigm builds increasingly complex fields by allowing potential functions, or features, that are supported by increasingly large subgraphs. Each feature has a weight that is trained by minimizing the Kullback-Leibler divergence between the model and the empirical distribution of the training data. A greedy algorithm determines how features are incrementally added to the field and an iterative...

Infinite Hidden Relational Models

Zhao Xu — 2007-10-24T17:32:55-00:00

(2006)

Relational learning analyzes the probabilistic constraints between the attributes of entities and relationships. We extend the expressiveness of relational models by introducing for each entity (or object) an infinitedimensional latent variable as part of a Dirichlet process (DP) mixture model. We discuss inference in the model, which is based on a DP Gibbs sampler, i.e., the Chinese restaurant process. We extended the Chinese restaurant process to be applicable to relational modeling. We discuss how information is propagated in the network of latent variables, reducing the necessity for extensive structural learning. In the context of a recommendation engine our approach realizes a principled solution for recommendations based on features of items, features of users and relational information. Our approach is evaluated in three applications: a recommendation system based on the Movie- Lens data set, the prediction of gene function using relational information and a medical recommendation system.

Structured priors for structure learning

V Mansinghka — 2007-12-12T12:38:36-00:00

(2006)

Hidden conditional random fields for phone classification

Asela Gunawardana — 2008-05-13T13:56:00-00:00

(2005)

In this paper, we show the novel application of hidden conditional random fields (HCRFs) -- conditional random fields with hidden state sequences -- for modeling speech. Hidden state sequences are critical for modeling the non-stationarity of speech signals. We show that HCRFs can easily be trained using the simple direct optimization technique of stochastic gradient descent. We present the results on the TIMIT phone classification task and show that HCRFs outperforms comparable ML and CML/MMI trained HMMs. In fact, HCRF results on this task are the best single classifier results known to us. We note that the HCRF framework is easily extensible to recognition since it is a state and label sequence modeling technique. We also note that HCRFs have the ability to handle complex features without any change in training procedure.

Training algorithms for hidden conditional random fields

Milind Mahajan — 2008-05-13T13:54:20-00:00

(2006)

We investigate algorithms for training hidden conditional random fields (HCRFs) – a class of direct models with hidden state sequences. We compare stochastic gradient ascent with the RProp algorithm, and investigate stochastic versions of RProp. We propose a new scheme for model flattening, and compare it to the state of the art. Finally we give experimental results on the TIMIT phone classification task showing how these training options interact, comparing HCRFs to HMMs trained using extended Baum-Welch as well as stochastic gradient methods.

Regularization, Adaptation, and Non-Independent Features Improve Hidden Conditional Random Fields for Phone Classification

Yun-Hsuan Sung — 2008-05-13T13:48:02-00:00

(2007)

Morphology Induction from Limited Noisy Data Using Approximate String Matching

Burcu Ayan — 2008-02-23T01:39:37-00:00

(June 2006), pp. 60-68.

Learning Probabilistic Paradigms for Morphology in a Latent Class Model

Erwin Chan — 2008-02-23T01:42:38-00:00

(June 2006), pp. 69-78.

Factor graphs and the sum-product algorithm

FR Kschischang — 2006-01-21T22:06:50-00:00

Information Theory, IEEE Transactions on, Vol. 47, No. 2. (2001), pp. 498-519.

Algorithms that must deal with complicated global functions of many variables often exploit the manner in which the given functions factor as a product of “local” functions, each of which depends on a subset of the variables. Such a factorization can be visualized with a bipartite graph that we call a factor graph, In this tutorial paper, we present a generic message-passing algorithm, the sum-product algorithm, that operates in a factor graph. Following a single, simple computational rule, the sum-product algorithm computes-either exactly or approximately-various marginal functions derived from the global function. A wide variety of algorithms developed in artificial intelligence, signal processing, and digital communications can be derived as specific instances of the sum-product algorithm, including the forward/backward algorithm, the Viterbi algorithm, the iterative “turbo” decoding algorithm, Pearl's (1988) belief propagation algorithm for Bayesian networks, the Kalman filter, and certain fast Fourier transform (FFT) algorithms

Inside-Outside Probability Computation for Belief Propagation

Taisuke Sato — 2007-12-21T22:28:39-00:00

(2007)

In this paper we prove that the well-known correspondence between the forward-backward algorithm for hidden Markov models (HMMs) and belief propagation (BP) applied to HMMs can be generalized to one between BP for junction trees and the generalized inside-outside probability computation for probabilistic logic programs applied to junction trees.

An introduction to factor graphs

HA Loeliger — 2008-01-28T06:57:13-00:00

Signal Processing Magazine, IEEE, Vol. 21, No. 1. (2004), pp. 28-41.

Graphical models such as factor graphs allow a unified approach to a number of key topics in coding and signal processing such as the iterative decoding of turbo codes, LDPC codes and similar codes, joint decoding, equalization, parameter estimation, hidden-Markov models, Kalman filtering, and recursive least squares. Graphical models can represent complex real-world systems, and such representations help to derive practical detection/estimation algorithms in a wide area of applications. Most known signal processing techniques -including gradient methods, Kalman filtering, and particle methods -can be used as components of such algorithms. Other than most of the previous literature, we have used Forney-style factor graphs, which support hierarchical modeling and are compatible with standard block diagrams.

Walk-Sums and Belief Propagation in Gaussian Graphical Models

Dmitry Malioutov — 2007-12-16T10:05:22-00:00

Journal of Machine Learning Research, Vol. 7 (October 2006)

We present a new framework based on walks in a graph for analysis and inference in Gaussian graphical models. The key idea is to decompose the correlation between each pair of variables as a sum over all walks between those variables in the graph. The weight of each walk is given by a product of edge-wise partial correlation coefficients. This representation holds for a large class of Gaussian graphical models which we call walk-summable. We give a precise characterization of this class of...

Understanding the Subprime Mortgage Crisis

Yuliya Demyanyk — 2008-04-28T23:25:08-00:00

Social Science Research Network Working Paper Series (29 February 2008)

Using loan-level data, we analyze the quality of subprime mortgage loans by adjusting their performance for differences in borrower characteristics, loan characteristics, and house price appreciation since origination. We find that the quality of loans deteriorated for six consecutive years before the crisis and that securitizers were, to some extent, aware of it. We provide evidence that the rise and fall of the subprime mortgage market follows a classic lending boom-bust scenario, in which unsustainable growth leads to the collapse of the market. Problems could have been detected long before the crisis, but they were masked by high house price appreciation between 2003 and 2005.

The Infinite Hidden Markov Model

MJ Beal — 2008-05-07T18:37:32-00:00

(2002)

We show that it is possible to extend hidden Markov models to have a countably infinite number of hidden states. By using the theory of Dirichlet processes we can implicitly integrate out the infinitely many transition parameters, leaving only three hyperparameters which can be learned from data. These three hyperparameters define a hierarchical Dirichlet process capable of capturing a rich set of transition dynamics. The three hyperparameters control the time scale of the dynamics, the...

The Infinite Markov Model

Daichi Mochihashi — 2008-02-18T09:13:26-00:00

(2008)

Introduction: A Typological Approach to Algorithmic Morphology

T Mayer — 2008-02-23T00:49:29-00:00

(November 2007)

Graph Walks and Graphical Models

William Cohen — 2008-02-07T01:24:26-00:00

(2007)

Inference in Markov random fields, and development and evaluation of similarity measures for nodes in graphs, are both active areas of data-mining research. In this paper, we demonstrate a formal connection between inference in tree-structured Markov random fields and personalized PageRank, a widely-used similarity measure for graph nodes based on graphwalks. In particular we show a connection between computation of marginal probabilities in tree-structured discrete-variable pairwise MRFs, and computation of similarity between vertices of a graph using the personalized PageRank measure: roughly speaking, for these MRFs, computing a marginal probability Pr(Xi = j) can be reduced to computing a small set of personalized-PageRank similarity vectors, followed by a very limited postprocessing stage.

Graph Theory

Frank Harary — 2005-11-30T17:15:17-00:00

An effort has been made to present the various topics in the theory of graphs in a logical order, to indicate the historical background, and to clarify the exposition by including figures to illustrate concepts and results. In addition, there are three appendices which provide diagrams of graphs, directed graphs, and trees. The emphasis throughout is on theorems rather than algorithms or applications, which however are occaisionally mentioned.

Foundations of Statistical Natural Language Processing

Christopher Manning — 2005-02-27T13:16:32-00:00

(18 June 1999)

"Statistical natural-language processing is, in my estimation, one of the most fast-moving and exciting areas of computer science these days. Anyone who wants to learn this field would be well advised to get this book. For that matter, the same goes for anyone who is already in the field. I know that it is going to be one of the most well-thumbed books on my bookshelf." -- Eugene Charniak, Department of Computer Science, Brown University <P>Statistical approaches to processing natural language text have become dominant in recent years. This foundational text is the first comprehensive introduction to statistical natural language processing (NLP) to appear. The book contains all the theory and algorithms needed for building NLP tools. It provides broad but rigorous coverage of mathematical and linguistic foundations, as well as detailed discussion of statistical methods, allowing students and researchers to construct their own implementations. The book covers collocation finding, word sense disambiguation, probabilistic parsing, information retrieval, and other applications. <P>More on this book

Bayesian Computation Via the Gibbs Sampler and Related Markov Chain Monte Carlo Methods

AFM Smith — 2006-09-05T17:59:27-00:00

The use of the Gibbs sampler for Bayesian computation is reviewed and illustrated in the context of some canonical examples. Other Markov chain Monte Carlo simulation methods are also briefly described, and comments are made on the advantages of sample-based approaches for Bayesian inference summaries.

PCA versus LDA

Aleix Martinez — 2008-05-07T16:01:07-00:00

IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 23, No. 2. (2001), pp. 228-233.

In the context of the appearance-based paradigm for object recognition, it is generally believed that algorithms based on LDA (Linear Discriminant Analysis) are superior to those based on PCA (Principal Components Analysis) . In this communication we show that this is not always the case. We present our case first by using intuitively plausible arguments and then by showing actual results on a face database. Our overall conclusion is that when the training dataset is small, PCA can outperform...

PCA versus LDA

Aleix Mart∈ez — 2007-07-13T12:09:22-00:00

IEEE Trans. Pattern Anal. Mach. Intell., Vol. 23, No. 2. (February 2001), pp. 228-233.

Machine Learning

Tom Mitchell — 2005-04-03T20:00:27-00:00

(01 March 1997)

This book covers the field of machine learning, which is the study of algorithms that allow computer programs to automatically improve through experience. The book is intended to support upper level undergraduate and introductory level graduate courses in machine learning.

Exponential Priors for Maximum Entropy Models

J Goodman — 2007-11-29T06:34:47-00:00

(2003)

Maximum entropy models are a common modeling technique, but prone to overfitting. We show that using an exponential distribution as a prior leads to bounded absolute discounting by a constant. We show that this prior is better motivated by the data than previous techniques such as a Gaussian prior, and often produces lower error rates. Exponential priors also lead to a simpler learning algorithm and to easier to understand behavior. Furthermore, exponential priors help explain the...

The information bottleneck method

N Tishby — 2005-03-02T06:57:17-00:00

(1999), pp. 368-377.

We define the relevant information in a signal x 2 X as being the information that this signal provides about another signal y 2 Y . Examples include the information that face images provide about the names of the people portrayed, or the information that speech sounds provide about the words spoken. Understanding the signal x requires more than just predicting y, it also requires specifying which features of X play a role in the prediction. We formalize the problem as that of finding a short...

Pattern Recognition and Machine Learning (Information Science and Statistics)

Christopher Bishop — 2006-09-26T12:22:37-00:00

(28 August 2006)

The dramatic growth in practical applications for machine learning over the last ten years has been accompanied by many important developments in the underlying algorithms and techniques. For example, Bayesian methods have grown from a specialist niche to become mainstream, while graphical models have emerged as a general framework for describing and applying probabilistic techniques. The practical applicability of Bayesian methods has been greatly enhanced by the development of a range of approximate inference algorithms such as variational Bayes and expectation propagation, while new models based on kernels have had a significant impact on both algorithms and applications. This completely new textbook reflects these recent developments while providing a comprehensive introduction to the fields of pattern recognition and machine learning. It is aimed at advanced undergraduates or first-year PhD students, as well as researchers and practitioners. No previous knowledge of pattern recognition or machine learning concepts is assumed. Familiarity with multivariate calculus and basic linear algebra is required, and some experience in the use of probabilities would be helpful though not essential as the book includes a self-contained introduction to basic probability theory. The book is suitable for courses on machine learning, statistics, computer science, signal processing, computer vision, data mining, and bioinformatics. Extensive support is provided for course instructors, including more than 400 exercises, graded according to difficulty. Example solutions for a subset of the exercises are available from the book web site, while solutions for the remainder can be obtained by instructors from the publisher. The book is supported by a great deal of additional material, and the reader is encouraged to visit the book web site for the latest information. A forthcoming companion volume will deal with practical aspects of pattern recognition and machine learning, and will include free software implementations of the key algorithms along with example data sets and demonstration programs. Christopher Bishop is Assistant Director at Microsoft Research Cambridge, and also holds a Chair in Computer Science at the University of Edinburgh. He is a Fellow of Darwin College Cambridge, and was recently elected Fellow of the Royal Academy of Engineering. The author's previous textbook "Neural Networks for Pattern Recognition" has been widely adopted.