July 30, 2019

3136 words 15 mins read

Paper Group AWR 31

A Streaming Algorithm for Graph Clustering. Unite the People: Closing the Loop Between 3D and 2D Human Representations. Beam Search Strategies for Neural Machine Translation. Reservoir of Diverse Adaptive Learners and Stacking Fast Hoeffding Drift Detection Methods for Evolving Data Streams. McDiarmid Drift Detection Methods for Evolving Data Strea …

A Streaming Algorithm for Graph Clustering


Title	A Streaming Algorithm for Graph Clustering
Authors	Alexandre Hollocou, Julien Maudet, Thomas Bonald, Marc Lelarge
Abstract	We introduce a novel algorithm to perform graph clustering in the edge streaming setting. In this model, the graph is presented as a sequence of edges that can be processed strictly once. Our streaming algorithm has an extremely low memory footprint as it stores only three integers per node and does not keep any edge in memory. We provide a theoretical justification of the design of the algorithm based on the modularity function, which is a usual metric to evaluate the quality of a graph partition. We perform experiments on massive real-life graphs ranging from one million to more than one billion edges and we show that this new algorithm runs more than ten times faster than existing algorithms and leads to similar or better detection scores on the largest graphs.
Tasks	Graph Clustering
Published	2017-12-09
URL	http://arxiv.org/abs/1712.04337v1
PDF	http://arxiv.org/pdf/1712.04337v1.pdf
PWC	https://paperswithcode.com/paper/a-streaming-algorithm-for-graph-clustering
Repo	https://github.com/ahollocou/graph-streaming
Framework	none

Unite the People: Closing the Loop Between 3D and 2D Human Representations


Title	Unite the People: Closing the Loop Between 3D and 2D Human Representations
Authors	Christoph Lassner, Javier Romero, Martin Kiefel, Federica Bogo, Michael J. Black, Peter V. Gehler
Abstract	3D models provide a common ground for different representations of human bodies. In turn, robust 2D estimation has proven to be a powerful tool to obtain 3D fits “in-the- wild”. However, depending on the level of detail, it can be hard to impossible to acquire labeled data for training 2D estimators on large scale. We propose a hybrid approach to this problem: with an extended version of the recently introduced SMPLify method, we obtain high quality 3D body model fits for multiple human pose datasets. Human annotators solely sort good and bad fits. This procedure leads to an initial dataset, UP-3D, with rich annotations. With a comprehensive set of experiments, we show how this data can be used to train discriminative models that produce results with an unprecedented level of detail: our models predict 31 segments and 91 landmark locations on the body. Using the 91 landmark pose estimator, we present state-of-the art results for 3D human pose and shape estimation using an order of magnitude less training data and without assumptions about gender or pose in the fitting procedure. We show that UP-3D can be enhanced with these improved fits to grow in quantity and quality, which makes the system deployable on large scale. The data, code and models are available for research purposes.
Tasks
Published	2017-01-10
URL	http://arxiv.org/abs/1701.02468v3
PDF	http://arxiv.org/pdf/1701.02468v3.pdf
PWC	https://paperswithcode.com/paper/unite-the-people-closing-the-loop-between-3d
Repo	https://github.com/classner/up
Framework	none

Beam Search Strategies for Neural Machine Translation


Title	Beam Search Strategies for Neural Machine Translation
Authors	Markus Freitag, Yaser Al-Onaizan
Abstract	The basic concept in Neural Machine Translation (NMT) is to train a large Neural Network that maximizes the translation performance on a given parallel corpus. NMT is then using a simple left-to-right beam-search decoder to generate new translations that approximately maximize the trained conditional probability. The current beam search strategy generates the target sentence word by word from left-to- right while keeping a fixed amount of active candidates at each time step. First, this simple search is less adaptive as it also expands candidates whose scores are much worse than the current best. Secondly, it does not expand hypotheses if they are not within the best scoring candidates, even if their scores are close to the best one. The latter one can be avoided by increasing the beam size until no performance improvement can be observed. While you can reach better performance, this has the draw- back of a slower decoding speed. In this paper, we concentrate on speeding up the decoder by applying a more flexible beam search strategy whose candidate size may vary at each time step depending on the candidate scores. We speed up the original decoder by up to 43% for the two language pairs German-English and Chinese-English without losing any translation quality.
Tasks	Machine Translation
Published	2017-02-06
URL	http://arxiv.org/abs/1702.01806v2
PDF	http://arxiv.org/pdf/1702.01806v2.pdf
PWC	https://paperswithcode.com/paper/beam-search-strategies-for-neural-machine
Repo	https://github.com/CongBao/ChatBot
Framework	none

Reservoir of Diverse Adaptive Learners and Stacking Fast Hoeffding Drift Detection Methods for Evolving Data Streams


Title	Reservoir of Diverse Adaptive Learners and Stacking Fast Hoeffding Drift Detection Methods for Evolving Data Streams
Authors	Ali Pesaranghader, Herna Viktor, Eric Paquet
Abstract	The last decade has seen a surge of interest in adaptive learning algorithms for data stream classification, with applications ranging from predicting ozone level peaks, learning stock market indicators, to detecting computer security violations. In addition, a number of methods have been developed to detect concept drifts in these streams. Consider a scenario where we have a number of classifiers with diverse learning styles and different drift detectors. Intuitively, the current ‘best’ (classifier, detector) pair is application dependent and may change as a result of the stream evolution. Our research builds on this observation. We introduce the $\mbox{Tornado}$ framework that implements a reservoir of diverse classifiers, together with a variety of drift detection algorithms. In our framework, all (classifier, detector) pairs proceed, in parallel, to construct models against the evolving data streams. At any point in time, we select the pair which currently yields the best performance. We further incorporate two novel stacking-based drift detection methods, namely the $\mbox{FHDDMS}$ and $\mbox{FHDDMS}_{add}$ approaches. The experimental evaluation confirms that the current ‘best’ (classifier, detector) pair is not only heavily dependent on the characteristics of the stream, but also that this selection evolves as the stream flows. Further, our $\mbox{FHDDMS}$ variants detect concept drifts accurately in a timely fashion while outperforming the state-of-the-art.
Tasks
Published	2017-09-07
URL	http://arxiv.org/abs/1709.02457v1
PDF	http://arxiv.org/pdf/1709.02457v1.pdf
PWC	https://paperswithcode.com/paper/reservoir-of-diverse-adaptive-learners-and
Repo	https://github.com/alipsgh/tornado
Framework	none

McDiarmid Drift Detection Methods for Evolving Data Streams


Title	McDiarmid Drift Detection Methods for Evolving Data Streams
Authors	Ali Pesaranghader, Herna Viktor, Eric Paquet
Abstract	Increasingly, Internet of Things (IoT) domains, such as sensor networks, smart cities, and social networks, generate vast amounts of data. Such data are not only unbounded and rapidly evolving. Rather, the content thereof dynamically evolves over time, often in unforeseen ways. These variations are due to so-called concept drifts, caused by changes in the underlying data generation mechanisms. In a classification setting, concept drift causes the previously learned models to become inaccurate, unsafe and even unusable. Accordingly, concept drifts need to be detected, and handled, as soon as possible. In medical applications and emergency response settings, for example, change in behaviours should be detected in near real-time, to avoid potential loss of life. To this end, we introduce the McDiarmid Drift Detection Method (MDDM), which utilizes McDiarmid’s inequality in order to detect concept drift. The MDDM approach proceeds by sliding a window over prediction results, and associate window entries with weights. Higher weights are assigned to the most recent entries, in order to emphasize their importance. As instances are processed, the detection algorithm compares a weighted mean of elements inside the sliding window with the maximum weighted mean observed so far. A significant difference between the two weighted means, upper-bounded by the McDiarmid inequality, implies a concept drift. Our extensive experimentation against synthetic and real-world data streams show that our novel method outperforms the state-of-the-art. Specifically, MDDM yields shorter detection delays as well as lower false negative rates, while maintaining high classification accuracies.
Tasks
Published	2017-10-05
URL	http://arxiv.org/abs/1710.02030v2
PDF	http://arxiv.org/pdf/1710.02030v2.pdf
PWC	https://paperswithcode.com/paper/mcdiarmid-drift-detection-methods-for
Repo	https://github.com/alipsgh/codes_for_moa
Framework	none

A log-linear time algorithm for constrained changepoint detection


Title	A log-linear time algorithm for constrained changepoint detection
Authors	Toby Dylan Hocking, Guillem Rigaill, Paul Fearnhead, Guillaume Bourque
Abstract	Changepoint detection is a central problem in time series and genomic data. For some applications, it is natural to impose constraints on the directions of changes. One example is ChIP-seq data, for which adding an up-down constraint improves peak detection accuracy, but makes the optimization problem more complicated. We show how a recently proposed functional pruning technique can be adapted to solve such constrained changepoint detection problems. This leads to a new algorithm which can solve problems with arbitrary affine constraints on adjacent segment means, and which has empirical time complexity that is log-linear in the amount of data. This algorithm achieves state-of-the-art accuracy in a benchmark of several genomic data sets, and is orders of magnitude faster than existing algorithms that have similar accuracy. Our implementation is available as the PeakSegPDPA function in the coseg R package, https://github.com/tdhock/coseg
Tasks	Time Series
Published	2017-03-09
URL	http://arxiv.org/abs/1703.03352v1
PDF	http://arxiv.org/pdf/1703.03352v1.pdf
PWC	https://paperswithcode.com/paper/a-log-linear-time-algorithm-for-constrained
Repo	https://github.com/tdhock/PeakSegFPOP-paper
Framework	none

Estimation of Low-Rank Matrices via Approximate Message Passing


Title	Estimation of Low-Rank Matrices via Approximate Message Passing
Authors	Andrea Montanari, Ramji Venkataramanan
Abstract	Consider the problem of estimating a low-rank matrix when its entries are perturbed by Gaussian noise. If the empirical distribution of the entries of the spikes is known, optimal estimators that exploit this knowledge can substantially outperform simple spectral approaches. Recent work characterizes the asymptotic accuracy of Bayes-optimal estimators in the high-dimensional limit. In this paper we present a practical algorithm that can achieve Bayes-optimal accuracy above the spectral threshold. A bold conjecture from statistical physics posits that no polynomial-time algorithm achieves optimal error below the same threshold (unless the best estimator is trivial). Our approach uses Approximate Message Passing (AMP) in conjunction with a spectral initialization. AMP algorithms have proved successful in a variety of statistical estimation tasks, and are amenable to exact asymptotic analysis via state evolution. Unfortunately, state evolution is uninformative when the algorithm is initialized near an unstable fixed point, as often happens in low-rank matrix estimation. We develop a new analysis of AMP that allows for spectral initializations. Our main theorem is general and applies beyond matrix estimation. However, we use it to derive detailed predictions for the problem of estimating a rank-one matrix in noise. Special cases of this problem are closely related—via universality arguments—to the network community detection problem for two asymmetric communities. For general rank-one models, we show that AMP can be used to construct confidence intervals and control false discovery rate. We provide illustrations of the general methodology by considering the cases of sparse low-rank matrices and of block-constant low-rank matrices with symmetric blocks (we refer to the latter as to the `Gaussian Block Model’). \|
Tasks	Community Detection
Published	2017-11-06
URL	https://arxiv.org/abs/1711.01682v4
PDF	https://arxiv.org/pdf/1711.01682v4.pdf
PWC	https://paperswithcode.com/paper/estimation-of-low-rank-matrices-via
Repo	https://github.com/jamied157/AMP
Framework	none

Wasserstein Introspective Neural Networks


Title	Wasserstein Introspective Neural Networks
Authors	Kwonjoon Lee, Weijian Xu, Fan Fan, Zhuowen Tu
Abstract	We present Wasserstein introspective neural networks (WINN) that are both a generator and a discriminator within a single model. WINN provides a significant improvement over the recent introspective neural networks (INN) method by enhancing INN’s generative modeling capability. WINN has three interesting properties: (1) A mathematical connection between the formulation of the INN algorithm and that of Wasserstein generative adversarial networks (WGAN) is made. (2) The explicit adoption of the Wasserstein distance into INN results in a large enhancement to INN, achieving compelling results even with a single classifier — e.g., providing nearly a 20 times reduction in model size over INN for unsupervised generative modeling. (3) When applied to supervised classification, WINN also gives rise to improved robustness against adversarial examples in terms of the error reduction. In the experiments, we report encouraging results on unsupervised learning problems including texture, face, and object modeling, as well as a supervised classification task against adversarial attacks.
Tasks
Published	2017-11-24
URL	http://arxiv.org/abs/1711.08875v5
PDF	http://arxiv.org/pdf/1711.08875v5.pdf
PWC	https://paperswithcode.com/paper/wasserstein-introspective-neural-networks
Repo	https://github.com/kjunelee/WINN
Framework	tf

Data Distillation: Towards Omni-Supervised Learning


Title	Data Distillation: Towards Omni-Supervised Learning
Authors	Ilija Radosavovic, Piotr Dollár, Ross Girshick, Georgia Gkioxari, Kaiming He
Abstract	We investigate omni-supervised learning, a special regime of semi-supervised learning in which the learner exploits all available labeled data plus internet-scale sources of unlabeled data. Omni-supervised learning is lower-bounded by performance on existing labeled datasets, offering the potential to surpass state-of-the-art fully supervised methods. To exploit the omni-supervised setting, we propose data distillation, a method that ensembles predictions from multiple transformations of unlabeled data, using a single model, to automatically generate new training annotations. We argue that visual recognition models have recently become accurate enough that it is now possible to apply classic ideas about self-training to challenging real-world data. Our experimental results show that in the cases of human keypoint detection and general object detection, state-of-the-art models trained with data distillation surpass the performance of using labeled data from the COCO dataset alone.
Tasks	Keypoint Detection, Object Detection
Published	2017-12-12
URL	http://arxiv.org/abs/1712.04440v1
PDF	http://arxiv.org/pdf/1712.04440v1.pdf
PWC	https://paperswithcode.com/paper/data-distillation-towards-omni-supervised
Repo	https://github.com/facebookresearch/detectron
Framework	pytorch

Fast Deep Matting for Portrait Animation on Mobile Phone


Title	Fast Deep Matting for Portrait Animation on Mobile Phone
Authors	Bingke Zhu, Yingying Chen, Jinqiao Wang, Si Liu, Bo Zhang, Ming Tang
Abstract	Image matting plays an important role in image and video editing. However, the formulation of image matting is inherently ill-posed. Traditional methods usually employ interaction to deal with the image matting problem with trimaps and strokes, and cannot run on the mobile phone in real-time. In this paper, we propose a real-time automatic deep matting approach for mobile devices. By leveraging the densely connected blocks and the dilated convolution, a light full convolutional network is designed to predict a coarse binary mask for portrait images. And a feathering block, which is edge-preserving and matting adaptive, is further developed to learn the guided filter and transform the binary mask into alpha matte. Finally, an automatic portrait animation system based on fast deep matting is built on mobile devices, which does not need any interaction and can realize real-time matting with 15 fps. The experiments show that the proposed approach achieves comparable results with the state-of-the-art matting solvers.
Tasks	Image Matting
Published	2017-07-26
URL	http://arxiv.org/abs/1707.08289v1
PDF	http://arxiv.org/pdf/1707.08289v1.pdf
PWC	https://paperswithcode.com/paper/fast-deep-matting-for-portrait-animation-on
Repo	https://github.com/huochaitiantang/pytorch-fast-matting-portrait
Framework	pytorch

A Multifaceted Evaluation of Neural versus Phrase-Based Machine Translation for 9 Language Directions


Title	A Multifaceted Evaluation of Neural versus Phrase-Based Machine Translation for 9 Language Directions
Authors	Antonio Toral, Víctor M. Sánchez-Cartagena
Abstract	We aim to shed light on the strengths and weaknesses of the newly introduced neural machine translation paradigm. To that end, we conduct a multifaceted evaluation in which we compare outputs produced by state-of-the-art neural machine translation and phrase-based machine translation systems for 9 language directions across a number of dimensions. Specifically, we measure the similarity of the outputs, their fluency and amount of reordering, the effect of sentence length and performance across different error categories. We find out that translations produced by neural machine translation systems are considerably different, more fluent and more accurate in terms of word order compared to those produced by phrase-based systems. Neural machine translation systems are also more accurate at producing inflected forms, but they perform poorly when translating very long sentences.
Tasks	Machine Translation
Published	2017-01-11
URL	http://arxiv.org/abs/1701.02901v1
PDF	http://arxiv.org/pdf/1701.02901v1.pdf
PWC	https://paperswithcode.com/paper/a-multifaceted-evaluation-of-neural-versus
Repo	https://github.com/antot/neural_vs_-phrasebased_smt_eacl17
Framework	none

Character-level Intra Attention Network for Natural Language Inference


Title	Character-level Intra Attention Network for Natural Language Inference
Authors	Han Yang, Marta R. Costa-jussà, José A. R. Fonollosa
Abstract	Natural language inference (NLI) is a central problem in language understanding. End-to-end artificial neural networks have reached state-of-the-art performance in NLI field recently. In this paper, we propose Character-level Intra Attention Network (CIAN) for the NLI task. In our model, we use the character-level convolutional network to replace the standard word embedding layer, and we use the intra attention to capture the intra-sentence semantics. The proposed CIAN model provides improved results based on a newly published MNLI corpus.
Tasks	Natural Language Inference
Published	2017-07-24
URL	http://arxiv.org/abs/1707.07469v1
PDF	http://arxiv.org/pdf/1707.07469v1.pdf
PWC	https://paperswithcode.com/paper/character-level-intra-attention-network-for
Repo	https://github.com/yanghanxy/CIAN
Framework	none

Reversible Architectures for Arbitrarily Deep Residual Neural Networks


Title	Reversible Architectures for Arbitrarily Deep Residual Neural Networks
Authors	Bo Chang, Lili Meng, Eldad Haber, Lars Ruthotto, David Begert, Elliot Holtham
Abstract	Recently, deep residual networks have been successfully applied in many computer vision and natural language processing tasks, pushing the state-of-the-art performance with deeper and wider architectures. In this work, we interpret deep residual networks as ordinary differential equations (ODEs), which have long been studied in mathematics and physics with rich theoretical and empirical success. From this interpretation, we develop a theoretical framework on stability and reversibility of deep neural networks, and derive three reversible neural network architectures that can go arbitrarily deep in theory. The reversibility property allows a memory-efficient implementation, which does not need to store the activations for most hidden layers. Together with the stability of our architectures, this enables training deeper networks using only modest computational resources. We provide both theoretical analyses and empirical results. Experimental results demonstrate the efficacy of our architectures against several strong baselines on CIFAR-10, CIFAR-100 and STL-10 with superior or on-par state-of-the-art performance. Furthermore, we show our architectures yield superior results when trained using fewer training data.
Tasks
Published	2017-09-12
URL	http://arxiv.org/abs/1709.03698v2
PDF	http://arxiv.org/pdf/1709.03698v2.pdf
PWC	https://paperswithcode.com/paper/reversible-architectures-for-arbitrarily-deep
Repo	https://github.com/EmoryMLIP/DynamicBlocks
Framework	pytorch

Automated Game Design Learning


Title	Automated Game Design Learning
Authors	Joseph C Osborn, Adam Summerville, Michael Mateas
Abstract	While general game playing is an active field of research, the learning of game design has tended to be either a secondary goal of such research or it has been solely the domain of humans. We propose a field of research, Automated Game Design Learning (AGDL), with the direct purpose of learning game designs directly through interaction with games in the mode that most people experience games: via play. We detail existing work that touches the edges of this field, describe current successful projects in AGDL and the theoretical foundations that enable them, point to promising applications enabled by AGDL, and discuss next steps for this exciting area of study. The key moves of AGDL are to use game programs as the ultimate source of truth about their own design, and to make these design properties available to other systems and avenues of inquiry.
Tasks
Published	2017-07-11
URL	http://arxiv.org/abs/1707.03333v1
PDF	http://arxiv.org/pdf/1707.03333v1.pdf
PWC	https://paperswithcode.com/paper/automated-game-design-learning
Repo	https://github.com/JoeOsborn/mechlearn
Framework	none

Learning Structured Text Representations


Title	Learning Structured Text Representations
Authors	Yang Liu, Mirella Lapata
Abstract	In this paper, we focus on learning structure-aware document representations from data without recourse to a discourse parser or additional annotations. Drawing inspiration from recent efforts to empower neural networks with a structural bias, we propose a model that can encode a document while automatically inducing rich structural dependencies. Specifically, we embed a differentiable non-projective parsing algorithm into a neural model and use attention mechanisms to incorporate the structural biases. Experimental evaluation across different tasks and datasets shows that the proposed model achieves state-of-the-art results on document modeling tasks while inducing intermediate structures which are both interpretable and meaningful.
Tasks
Published	2017-05-25
URL	http://arxiv.org/abs/1705.09207v4
PDF	http://arxiv.org/pdf/1705.09207v4.pdf
PWC	https://paperswithcode.com/paper/learning-structured-text-representations
Repo	https://github.com/nlpyang/structured
Framework	tf