Braque: Discourse Analysis
Items for query: discourse or RST or centering language on Braque
07/09/2014, 05:48 AM en-us Vincent D. Blondel , John N. Tsitsiklis () E1KHILL5 04/18/2014, 11:24 PM [<a href=>read later</a>] We show that the boundedness of the set of all products of a given pair of rational matrices is undecidable. Furthermore, we show that the joint (or generalized) spectral radius ( ) is not computable because testing whether ( ) 6 1 is an undecidable problem. As a consequence, the robust stability of linear systems under time-varying perturbations is undecidable, and the same is true for the stability of a simple class of hybrid systems. We also discuss some connections with the so-called "niteness conjecture". Our results are based on a simple reduction from the emptiness problem for probabilistic nite automata, which is known to be undecidable. c 2000 Elsevier Science B.V. All rights reserved. Keywords: Computability; Decidability; Matrix semigroup; Joint spectral radius; Generalised spectral radius; Finiteness conjecture; Robust stability analysis; Linear time-varying systems 1. Introduction Let be anite set of real n n matrices. We consider products of the form A t A t - 1 A 1 , where each A i is an arbitrary element of . More specically, we are interested in the largest possible rate of growth of such products. Issues of this type arise naturally when considering linear time-varying systems of the form x t +1 = A t x t , as well as in many other contexts; see [22,8]. Supported by the NATO under Grant CRG-961115, by the AFOSR under Grant F49620-99-10320, and by the NSF under Grant ACI-9873339. Corresponding author. Tel.: +32-10-472-381; fax: +32-10472-180. E-mail addresses: (V.D. Blondel), (J.N. Tsitsiklis). One measure of growth of such matrix products is provided by the joint spectral radius ^( ) [19], which is dened by ^( ) = lim sup t ^ t ( ) ; where ^ t ( ) = max A 1 ;:::; A t A t A 1 1 =t ; and is some matrix norm. The value of ^( ) turns out to be independent of the choice of the norm. Furthermore, if the matrix norm has the property AB 6 A B (e.g., if it is an induced norm), then ^ t ( ) converges and we also have ^( ) = lim t ^ t ( ) 6 ^ ( ) ; : Recall that the ... Approximate Gradient Methods in Policy-Space Optimization of Markov Reward Processes* (PETER MARBACH JOHN N. TSITSIKLIS DFKGWB50 04/18/2014, 11:22 PM [<a href=>read later</a>] We consider a discrete time,nite state Markov reward process that depends on a set of parameters. We start with a brief review of (stochastic) gradient descent methods that tune the parameters in order to optimize the average reward, using a single ( possibly simulated) sample path of the process of interest. The resulting algorithms can be implemented online, and have the property that the gradient of the average reward converges to zero with probability 1. On the other hand, the updates can have a high variance, resulting in slow convergence. We address this issue and propose two approaches to reduce the variance. These approaches rely on approximate gradient formulas, which introduce an additional bias into the update direction. We derive bounds for the resulting bias terms and characterize the asymptotic behavior of the resulting algorithms. For one of the approaches considered, the magnitude of the bias term exhibits an interesting dependence on the time it takes for the rewards to reach steady-state. We also apply the methodology to Markov reward processes with a reward-free termination state, and an expected total reward criterion. We use a call admission control problem to illustrate the performance of the proposed algorithms. Keywords: Markov reward processes, simulation-based optimization, policy-space optimization 1.Introduction We consider discrete time,nite state Markov reward processes in which the transition probabilities and one-stage rewards depend on a parameter vector y [ ` K . We propose simulation-based algorithms for tuning the parameter y to optimize either the average reward, or the expected reward-to-go. Compared with earlier work (Marbach and Tsitsiklis, 2001), these algorithms have a smaller variance and therefore tend to perform better in practice. Most of the paper focuses on methods for optimizing the average reward; the resulting methodology is readily applied to Markov processes with a rewardfree termination state where the optimizer wants to maximize the expected reward-to-go ... Average cost temporal-di erence learning () QTHOGHB5 04/18/2014, 11:16 PM [<a href=>read later</a>] We propose a variant of temporal-di ! erence learning that approximates average and di ! erential costs of an irreducible aperiodic Markov chain. Approximations are comprised of linear combinations of " xed basis functions whose weights are incrementally updated during a single endless trajectory of the Markov chain. We present a proof of convergence (with probability 1) and a characterization of the limit of convergence. We also provide a bound on the resulting approximation error that exhibits an interesting dependence on the ` mixing time a of the Markov chain. The results parallel previous work by the authors, involving approximations of discounted cost-to-go. 1999 Elsevier Science Ltd. All rights reserved. Keywords: Dynamic programming; Learning; Average cost; Reinforcement learning; Neuro-dynamic programming; Approximation; Temporal di ! erences 1. Introduction Temporal-di ! erence (TD) learning, as proposed by Sutton (1988), is an algorithm for approximating the cost-to-go function of a Markov chain (the expected future cost, as a function of the initial state) by a linear combination of a given collection of basis functions, on the basis of simulation or observation of the process. Such approximations are used primarily in approximate policy iteration methods for large-scale Markov decision problems, when the size of the state space is too large to allow exact computation of the cost-to-go function (Bertsekas & Tsitsiklis, 1996). A comprehensive convergence analysis for the case of discounted Markov chains has been provided by the authors (Tsitsiklis & Van Roy, 1997). A simpli " ed version of that work, together with extensions to the case of undiscounted absorbing Markov chains, is presented in (Bertsekas & Tsitsiklis, 1996). Related analyses are given by (Sutton, 1988; Dayan, 1992; Gurvits, Lin & Hansen, 1994), and (Pineda, 1996). The purpose of the present paper is to propose and analyze a variant of TD learning that is suitable for approximating di ! erential cost functions of undiscounted Markov ... ace2006paper.indd (jpatten) 1VCAIIQB 04/18/2014, 09:54 PM [<a href=>read later</a>] We present a set of interaction techniques for electronic musical performance using a tabletop tangible interface. Our system, the Audiopad, tracks the positions of objects on a tabletop surface and translates their motions into commands for a musical synthesizer. We developed and refi ned these interaction techniques through an iterative design process, in which new interaction techniques were periodically evaluated through performances and gallery installations. Based on our experience refi ning the design of this system, we conclude that tabletop interfaces intended for collaborative use should use interaction techniques designed to be legible to onlookers. We also conclude that these interfaces should allow users to spatially reconfi gure the objects in the interface in ways that are personally meaningful. Response Prediction Using Collaborative Filtering with Hierarchies and Side-information (Aditya Krishna Menon Sachin Garg Deepak Agarwal Nagaraj Kota) JWHTR2AC 04/18/2014, 09:30 PM [<a href=>read later</a>] In online advertising, response prediction is the problem of estimating the probability that an advertisement is clicked when displayed on a content publisher's webpage. In this paper, we show how response prediction can be viewed as a problem of matrix completion , and propose to solve it using matrix factorization techniques from collaborative fi ltering (CF). We point out the two crucial differences between standard CF problems and response prediction, namely the requirement of predicting probabilities rather than scores, and the issue of con fi dence in matrix entries. We address these issues using a matrix factorization analogue of logistic regression, and by applying a principled con fi dence-weighting scheme to its objective. We show how this factorization can be seamlessly combined with explicit features or side-information for pages and ads, which let us combine the bene fi ts of both approaches. Finally, we combat the extreme sparsity of response prediction data by incorporating hierarchical information about the pages and ads into our factorization model. Experiments on three very large real-world datasets show that our model outperforms current state-of-the-art methods for response prediction. Statistical Modeling for Unit Selection in Speech Synthesis (Cyril Allauzen Mehryar Mohri Michael Riley) V2WF3Q3N 04/18/2014, 05:11 PM [<a href=>read later</a>] Traditional concatenative speech synthesis systems use a number of heuristics to define the target and concatenation costs, essential for the design of the unit selection component. In contrast to these approaches, we introduce a general statistical modeling framework for unit selection inspired by automatic speech recognition. Given appropriate data, techniques based on that framework can result in a more accurate unit selection, thereby improving the general quality of a speech synthesizer. They can also lead to a more modular and a substantially more efficient system. We present a new unit selection system based on statistical modeling. To overcome the original absence of data, we use an existing high-quality unit selection system to generate a corpus of unit sequences. We show that the concatenation cost can be accurately estimated from this corpus using a statistical n -gram language model over units. We used weighted automata and transducers for the representation of the components of the system and designed a new and more efficient composition algorithm making use of string potentials for their combination. The resulting statistical unit selection is shown to be about 2 . 6 times faster than the last release of the AT&T Natural Voices Product while preserving the same quality, and offers much flexibility for the use and integration of new and more complex components. Sampling Methods for the Nystrom Method (Sanjiv Kumar Mehryar Mohri Ameet Talwalkar) K41XD4JV 04/18/2014, 05:08 PM [<a href=>read later</a>] The Nystrom method is an efficient technique to generate low-rank matrix approximations and is used in several large-scale learning applications. A key aspect of this method is the procedure according to which columns are sampled from the original matrix. In this work, we explore the efficacy of a variety of fixed and adaptive sampling schemes. We also propose a family of ensemble -based sampling algorithms for the Nystrom method. We report results of extensive experiments that provide a detailed comparison of various fixed and adaptive sampling techniques, and demonstrate the performance improvement associated with the ensemble Nystrom method when used in conjunction with either fixed or adaptive sampling schemes. Corroborating these empirical findings, we present a theoretical analysis of the Nystrom method, providing novel error bounds guaranteeing a better convergence rate of the ensemble Nystrom method in comparison to the standard Nystrom method. Local Grammar Algorithms () OVIU15SZ 04/18/2014, 05:08 PM [<a href=>read later</a>] Speaker Movement Correlates with Prosodic Indicators of Engagement (Rob Voigt, Robert J. Podesva, Dan Jurafsky) PJQQ5DRK 04/11/2014, 08:52 PM [<a href=>read later</a>] Recent research on multimodal prosody has begun to identify associations between discrete body movements and categorical acoustic prosodic events such as pitch accents and boundaries. We propose to generalize this work to understand more about continuous prosodic phenomena distributed over a phrase - like those indicative of speaker engagement - and how they covary with bodily movements. We introduce movement amplitude , a new vision-based metric for estimating continuous body movements over time from video by quantifying frameto-frame visual changes. Application of this automatic metric to a collection of video monologues demonstrates that speakers move more during phrases in which their pitch and intensity are higher and more variable. These findings offer further evidence for the relationship between acoustic and visual prosody, and suggest a previously unreported quantitative connection between raw bodily movement and speaker engagement. Index Terms : acoustic prosody, visual prosody, movement, gesture, speech-gesture interface, automatic methods Collection of a Simultaneous Translation Corpus for Comparative Analysis (Hiroaki Shimizu, Graham Neubig, Sakriani Sakti, Tomoki Toda, Satoshi Nakamura) JH1YAPQ5 03/28/2014, 08:49 PM [<a href=>read later</a>] This paper describes the collection of an English-Japanese/Japanese-English simultaneous interpretation corpus. There are two main features of the corpus. The first is that professional simultaneous interpreters with different amounts of experience cooperated with the collection. By comparing data from simultaneous interpretation of each interpreter, it is possible to compare better interpretations to those that are not as good. The second is that for part of our corpus there are already translation data available. This makes it possible to compare translation data with simultaneous interpretation data. We recorded the interpretations of lectures and news, and created time-aligned transcriptions. A total of 387k words of transcribed data were collected. The corpus will be helpful to analyze differences in interpretations styles and to construct simultaneous interpretation systems. Keywords: simultaneous translation, simultaneous interpretation, corpus collection Automatically enriching spoken corpora with syntactic information for linguistic studies (Alexis Nasr, Frederic Bechet, Benoit Favre, Thierry Bazillon, Jose Deulofeu, Andre Valli) U42HLHOR 03/28/2014, 06:47 PM [<a href=>read later</a>] Syntactic parsing of speech transcriptions faces the problem of the presence of disfluencies that break the syntactic structure of the utterances. We propose in this paper two solutions to this problem. The first one relies on a disfluencies predictor that detects disfluencies and removes them prior to parsing. The second one integrates the disfluencies in the syntactic structure of the utterances and train a disfluencies aware parser. Results of the WMT13 Metrics Shared Task (Matous Machacek Ondrej Bojar) D33VUDXO 03/14/2014, 12:09 AM [<a href=>read later</a>] This paper presents the results of the WMT13 Metrics Shared Task. We asked participants of this task to score the outputs of the MT systems involved in WMT13 Shared Translation Task. We collected scores of 16 metrics from 8 research groups. In addition to that we computed scores of 5 standard metrics such as BLEU, WER, PER as baselines. Collected scores were evaluated in terms of system level correlation (how well each metric's scores correlate with WMT13 official human scores) and in terms of segment level correlation (how often a metric agrees with humans in comparing two translations of a particular sentence). This is a corrected version of January 20, 2014. Making the Connection: Social Bonding in Courtship Situations () RY5DRQMF 02/21/2014, 08:39 AM [<a href=>read later</a>] The Inverse Regression Topic Model (Supplement) () DJG3NQ0U 02/20/2014, 11:25 PM [<a href=>read later</a>] The Inverse Regression Topic Model (Maxim Rabinovich David M. Blei) HQGJYDND 02/20/2014, 11:25 PM [<a href=>read later</a>] Taddy ( 2013 )proposed multinomial inverse regression (MNIR) as a new model of annotated text based on the influence of metadata and response variables on the distribution of words in a document. While effective, MNIR has no way to exploit structure in the corpus to improve its predictions or facilitate exploratory data analysis. On the other hand, traditional probabilistic topic models (like latent Dirichlet allocation) capture natural heterogeneity in a collection but do not account for external variables. In this paper, we introduce the inverse regression topic model (IRTM), a mixed-membership extension of MNIR that combines the strengths of both methodologies. We present two inference algorithms for the IRTM: an efficient batch estimation algorithm and an online variant, which is suitable for large corpora. We apply these methods to a corpus of 73K Congressional press releases and another of 150K Yelp reviews, demonstrating that the IRTM outperforms both MNIR and supervised topic models on the prediction task. Further, we give examples showing that the IRTM enables systematic discovery of in-topic lexical variation, which is not possible with previous supervised topic models. Heterogeneous Networks and Their Applications: Scientometrics, Name Disambiguation, and Topic Modeling (Ben King, Rahul Jha Dragomir R. Radev) 0POQZUSI 02/14/2014, 12:46 AM [<a href=>read later</a>] We present heterogeneous networks as a way to unify lexical networks with relational data. We build a unified ACL Anthology network, tying together the citation, author collaboration, and term-cooccurence networks with affiliation and venue relations. This representation proves to be convenient and allows problems such as name disambiguation, topic modeling, and the measurement of scientific impact to be easily solved using only this network and off-the-shelf graph algorithms. Faust.rdf - Taking RDF literally (Timm Heuss) ZUMTQSSC 02/13/2014, 11:03 PM [<a href=>read later</a>] This paper undertakes the modelling experiment of translating excerpts of the natural language play - "Faust" by Johann Wolfgang von Goethe - into a RDF structure, so that it is accessible by machines on a word or concept level. Thereby, it is crucial that statements made in the logic of the play can be distinguished from the usual, general purpose Linked Open Data. The goal is to find a standard compliant solution, stressing RDF's central role in the Web of Data as a format for arbitrary data. Transforming the Data Transcription and Analysis Tool Metadata and Labels into a Linguistic Linked Open Data Cloud Resource (Antonio Pareja-Lora Mara Blume Barbara Lust) F2DH1KTQ 02/13/2014, 11:03 PM [<a href=>read later</a>] Developing language resources requires much time, funding and effort. This is why they need to be reused in new projects and developments, so that they may both serve a wider scientific community and sustain their cost. The main problems that prevent this from happening are that (1) language resources are rarely free and/or easy to locate; and (2) they are hardly ever interoperable. Therefore, the language resource community is now working to transform their most valuable assets into open and interoperable resources, which can then be shared and linked with other open and interoperable resources. This will allow data to be reanalyzed and repurposed. In this paper, we present the first steps taken to transform a set of such resources, namely the Data Transcription and Analysis Tool's (DTA) metadata and data, into an open and interoperable language resource. These first steps include the development of two ontologies that formalize the conceptual model underlying the DTA metadata and the labels used in the DTA to annotate both utterances and their transcriptions at several annotation levels. Expectation-Maximization Gaussian-Mixture Approximate Message Passing (Jeremy P. Vila , and Philip Schniter) JEKPRA2T 02/07/2014, 12:09 AM [<a href=>read later</a>] Textual Inference and Meaning Representation in Human Robot Interaction (Emanuele Bastianelli , Giuseppe Castellucci , Danilo Croce , Roberto Basili) MEJ34GRQ 02/06/2014, 11:02 PM [<a href=>read later</a>] This paper provides a first investigation over existing textual inference paradigms in order to propose a generic framework able to capture major semantic aspects in Human Robot Interaction (HRI). We investigate the use of general semantic paradigms used in Natural Language Understanding (NLU) tasks, such as Semantic Role Labeling, over typical robot commands. The semantic information obtained is then represented under the Abstract Meaning Representation . AMR is a general representation language useful to express different level of semantic information without a strong dependence to the syntactic structure of an underlying sentence. The final aim of this work is to find an effective synergy between HRI and NLU.