Conference Papers

Stacking dependency parsers

Martins A.F.T., Das D., Smith N.A., Xing E.P.

EMNLP 2008 - 2008 Conference on Empirical Methods in Natural Language Processing, Proceedings of the Conference: A Meeting of SIGDAT, a Special Interest Group of the ACL

2008

Abstract:

We explore a stacked framework for learning to predict dependency structures for natural language sentences. A typical approach in graph-based dependency parsing has been to assume a factorized model, where local features are used but a global function is optimized (McDonald et al., 2005b). Recently Nivre and McDonald (2008) used the output of one dependency parser to provide features for another. We show that this is an example of stacked learning, in which a second predictor is trained to improve the performance of the first. Further, we argue that this technique is a novel way of approximating rich non-local features in the second parser, without sacrificing efficient, model-optimal prediction. Experiments on twelve languages show that stacking transition-based and graph-based parsers improves performance over existing state-of-the-art dependency parsers.

Statistical model checking for Markov decision processes

Henriques D., Martins J.G., Zuliani P., Platzer A., Clarke E.M.

Proceedings - 2012 9th International Conference on Quantitative Evaluation of Systems, QEST 2012

2012

Abstract:

Statistical Model Checking (SMC) is a computationally very efficient verification technique based on selective system sampling. One well identified shortcoming of SMC is that, unlike probabilistic model checking, it cannot be applied to systems featuring nondeterminism, such as Markov Decision Processes (MDP). We address this limitation by developing an algorithm that resolves nondeterminism probabilistically, and then uses multiple rounds of sampling and Reinforcement Learning to provably improve resolutions of nondeterminism with respect to satisfying a Bounded Linear Temporal Logic (BLTL) property. Our algorithm thus reduces an MDP to a fully probabilistic Markov chain on which SMC may be applied to give an approximate solution to the problem of checking the probabilistic BLTL property. We integrate our algorithm in a parallelised modification of the PRISM simulation framework. Extensive validation with both new and PRISM benchmarks demonstrates that the approach scales very well in scenarios where symbolic algorithms fail to do so.

Statistics of parked cars for urban vehicular networks

Reis A.B., Sargento S.

WoWMoM 2016 - 17th International Symposium on a World of Wireless, Mobile and Multimedia Networks

2016

Abstract:

The ability to predict the behavior of cars that are parked in an urban area can be very useful to the development of vehicular networks that leverage these parked cars. In this paper, we analyze the mobility patterns of people living in US cities who use cars as their primary means of transportation. We process and analyze survey data from the metropolitan areas of Atlanta, Chicago, and Knoxville, to extract statistics on the parking behaviors of individual cars.

Stereoscopic aerial photography: An alternative to model-based urban mobility approaches

Ferreira M., Conceicao H., Fernandes R., Tonguz O.K.

VANET'09 - Proceedings of the 6th ACM International Workshop on VehiculAr Inter-NETworking

2009

Abstract:

In the absence of large-scale deployments of VANETs, simulation based research is until now the only choice available to address and validate the design of protocols in the context of vehicular networks. The simulation frameworks involved in this research have to model two essential components, namely the vehicular mobility and the wireless inter-vehicle communication. Both of these aspects are especially complex in urban scenarios. In this paper we propose an alternative approach to obtain a realistic configuration of vehicles, and the respective traveling speeds, based on stereoscopic aerial photography, that is available to virtually every city in the world. We further use the aerial perspective of an urban area to identify a buildings layer and evaluate a wireless communication model that accounts for the obstructions caused by such layer on the connectivity of the wireless network. We evaluate our proposal over the city of Porto and compare the results obtained with model-based mobility approaches. Our results show significant differences in the connectivity profile of the analyzed urban VANET.

Strong convergence to mixed equilibria in fictitious play

Swenson B., Kar S., Xavier J.

2014 48th Annual Conference on Information Sciences and Systems, CISS 2014

2014

Abstract:

Learning processes that converge to mixed-strategy equilibria often exhibit learning only in the weak sense in that the time-averaged empirical distribution of players’ actions converges to a set of equilibria. A stronger notion of learning mixed equilibria is to require that players period-by-period strategies converge to a set of equilibria. A simple and intuitive method is considered for adapting algorithms that converge in the weaker sense in order to obtain convergence in the stronger sense. The adaptation is applied to the the well-known fictitious play (FP) algorithm, and the adapted version of FP is shown to converge to the set of Nash equilibria in the stronger sense for games known to have the FP property.

Structured sparsity in structured prediction

Martins A.F.T., Smith N.A., Aguiar P.M.Q., Figueiredo M.A.T.

EMNLP 2011 - Conference on Empirical Methods in Natural Language Processing, Proceedings of the Conference

2011

Abstract:

Linear models have enjoyed great success in structured prediction in NLP. While a lot of progress has been made on efficient training with several loss functions, the problem of endowing learners with a mechanism for feature selection is still unsolved. Common approaches employ ad hoc filtering or L1-regularization; both ignore the structure of the feature space, preventing practicioners from encoding structural prior knowledge. We fill this gap by adopting regularizers that promote structured sparsity, along with efficient algorithms to handle them. Experiments on three tasks (chunking, entity recognition, and dependency parsing) show gains in performance, compactness, and model interpretability.

Substructural typestates

Militao F., Aldrich J., Caires L.

PLPV 2014 - Proceedings of the 2014 ACM SIGPLAN Workshop on Programming Languages Meets Program Verification, Co-located with POPL 2014

2014

Abstract:

Finding simple, yet expressive, verification techniques to reason about both aliasing and mutable state has been a major challenge for static program verification. One such approach, of practical relevance, is centered around a lightweight typing discipline where types denote abstract object states, known as typestates. In this paper, we show how key typestate concepts can be precisely captured by a substructural type-and-effect system, exploiting ideas from linear and separation logic. Building on this foundation, we show how a small set of primitive concepts can be composed to express high-level idioms such as objects with multiple independent state dimensions, dynamic state tests, and behavior-oriented usage protocols that enforce strong information hiding. By exploring the relationship between two mainstream modularity concepts, state abstraction and hiding, we also provide new insights on how they naturally fit together and complement one another. Technically, our results are based on a typed lambda calculus with mutable references, location-dependent types, and second-order polymorphism. The soundness of our type system is shown through progress and preservation theorems. We also describe a prototype implementation of a type checker for our system, which is available on the web and can be used to experiment with the examples in the paper.

Sufficient condition for survival of the fittest in a bi-virus epidemics

Santos A., Moura J.M.F., Xavier J.M.F.

Conference Record - Asilomar Conference on Signals, Systems and Computers

2016

Abstract:

We study the spread of two strains of virus competing for space in a network modeled by the classical logistic ordinary differential equations. In large-scale complex networks, the underlying nonlinear dynamical system is high-dimensional and performing qualitative analysis of the differential equation becomes prohibitive. The study of such systems is often deferred to numerical simulations or local analysis about equilibrium points of the system. In this paper, we extend the work developed in [1], to formally establish a simple sufficient condition for (exponentially fast) survival of the fittest in a bi-layer weighted digraph: the weaker strain dies out regardless of the initial conditions if its maximum in-flow rate of infection across nodes is smaller than the minimum in-flow rate of the stronger strain. We bound any solution of the logistic ODE by one- dimensional solutions over certain homogeneous networks, for which the system is well understood. Our global stability approach via bounds readily applies to the discrete-time logistic model counterpart.

Summarization of films and documentaries based on subtitles and scripts

Aparicio M., Figueiredo P., Raposo F., Martins De Matos D., Ribeiro R., Marujo L.

Pattern Recognition Letters

2016

Abstract:

We assess the performance of generic text summarization algorithms applied to films and documentaries, using extracts from news articles produced by reference models of extractive summarization. We use three datasets: (i) news articles, (ii) film scripts and subtitles, and (iii) documentary subtitles. Standard ROUGE metrics are used for comparing generated summaries against news abstracts, plot summaries, and synopses. We show that the best performing algorithms are LSA, for news articles and documentaries, and LexRank and Support Sets, for films. Despite the different nature of films and documentaries, their relative behavior is in accordance with that obtained for news articles.