July 27, 2019

2803 words 14 mins read

Paper Group ANR 634

Decoding with Finite-State Transducers on GPUs. An Efficient ADMM Algorithm for Structural Break Detection in Multivariate Time Series. Towards a Unified Taxonomy of Biclustering Methods. High-order Tensor Completion for Data Recovery via Sparse Tensor-train Optimization. Associative content-addressable networks with exponentially many robust stabl …

Decoding with Finite-State Transducers on GPUs


Title	Decoding with Finite-State Transducers on GPUs
Authors	Arturo Argueta, David Chiang
Abstract	Weighted finite automata and transducers (including hidden Markov models and conditional random fields) are widely used in natural language processing (NLP) to perform tasks such as morphological analysis, part-of-speech tagging, chunking, named entity recognition, speech recognition, and others. Parallelizing finite state algorithms on graphics processing units (GPUs) would benefit many areas of NLP. Although researchers have implemented GPU versions of basic graph algorithms, limited previous work, to our knowledge, has been done on GPU algorithms for weighted finite automata. We introduce a GPU implementation of the Viterbi and forward-backward algorithm, achieving decoding speedups of up to 5.2x over our serial implementation running on different computer architectures and 6093x over OpenFST.
Tasks	Chunking, Morphological Analysis, Named Entity Recognition, Part-Of-Speech Tagging, Speech Recognition
Published	2017-01-11
URL	http://arxiv.org/abs/1701.03038v2
PDF	http://arxiv.org/pdf/1701.03038v2.pdf
PWC	https://paperswithcode.com/paper/decoding-with-finite-state-transducers-on
Repo
Framework

An Efficient ADMM Algorithm for Structural Break Detection in Multivariate Time Series


Title	An Efficient ADMM Algorithm for Structural Break Detection in Multivariate Time Series
Authors	Alex Tank, Emily B. Fox, Ali Shojaie
Abstract	We present an efficient alternating direction method of multipliers (ADMM) algorithm for segmenting a multivariate non-stationary time series with structural breaks into stationary regions. We draw from recent work where the series is assumed to follow a vector autoregressive model within segments and a convex estimation procedure may be formulated using group fused lasso penalties. Our ADMM approach first splits the convex problem into a global quadratic program and a simple group lasso proximal update. We show that the global problem may be parallelized over rows of the time dependent transition matrices and furthermore that each subproblem may be rewritten in a form identical to the log-likelihood of a Gaussian state space model. Consequently, we develop a Kalman smoothing algorithm to solve the global update in time linear in the length of the series.
Tasks	Time Series
Published	2017-11-22
URL	http://arxiv.org/abs/1711.08392v2
PDF	http://arxiv.org/pdf/1711.08392v2.pdf
PWC	https://paperswithcode.com/paper/an-efficient-admm-algorithm-for-structural
Repo
Framework

Towards a Unified Taxonomy of Biclustering Methods


Title	Towards a Unified Taxonomy of Biclustering Methods
Authors	Dmitry I. Ignatov, Bruce W. Watson
Abstract	Being an unsupervised machine learning and data mining technique, biclustering and its multimodal extensions are becoming popular tools for analysing object-attribute data in different domains. Apart from conventional clustering techniques, biclustering is searching for homogeneous groups of objects while keeping their common description, e.g., in binary setting, their shared attributes. In bioinformatics, biclustering is used to find genes, which are active in a subset of situations, thus being candidates for biomarkers. However, the authors of those biclustering techniques that are popular in gene expression analysis, may overlook the existing methods. For instance, BiMax algorithm is aimed at finding biclusters, which are well-known for decades as formal concepts. Moreover, even if bioinformatics classify the biclustering methods according to reasonable domain-driven criteria, their classification taxonomies may be different from survey to survey and not full as well. So, in this paper we propose to use concept lattices as a tool for taxonomy building (in the biclustering domain) and attribute exploration as means for cross-domain taxonomy completion.
Tasks
Published	2017-02-17
URL	http://arxiv.org/abs/1702.05376v1
PDF	http://arxiv.org/pdf/1702.05376v1.pdf
PWC	https://paperswithcode.com/paper/towards-a-unified-taxonomy-of-biclustering
Repo
Framework

High-order Tensor Completion for Data Recovery via Sparse Tensor-train Optimization


Title	High-order Tensor Completion for Data Recovery via Sparse Tensor-train Optimization
Authors	Longhao Yuan, Qibin Zhao, Jianting Cao
Abstract	In this paper, we aim at the problem of tensor data completion. Tensor-train decomposition is adopted because of its powerful representation ability and linear scalability to tensor order. We propose an algorithm named Sparse Tensor-train Optimization (STTO) which considers incomplete data as sparse tensor and uses first-order optimization method to find the factors of tensor-train decomposition. Our algorithm is shown to perform well in simulation experiments at both low-order cases and high-order cases. We also employ a tensorization method to transform data to a higher-order form to enhance the performance of our algorithm. The results of image recovery experiments in various cases manifest that our method outperforms other completion algorithms. Especially when the missing rate is very high, e.g., 90% to 99%, our method is significantly better than the state-of-the-art methods.
Tasks
Published	2017-11-07
URL	http://arxiv.org/abs/1711.02271v2
PDF	http://arxiv.org/pdf/1711.02271v2.pdf
PWC	https://paperswithcode.com/paper/high-order-tensor-completion-for-data
Repo
Framework

Associative content-addressable networks with exponentially many robust stable states


Title	Associative content-addressable networks with exponentially many robust stable states
Authors	Rishidev Chaudhuri, Ila Fiete
Abstract	The brain must robustly store a large number of memories, corresponding to the many events encountered over a lifetime. However, the number of memory states in existing neural network models either grows weakly with network size or recall fails catastrophically with vanishingly little noise. We construct an associative content-addressable memory with exponentially many stable states and robust error-correction. The network possesses expander graph connectivity on a restricted Boltzmann machine architecture. The expansion property allows simple neural network dynamics to perform at par with modern error-correcting codes. Appropriate networks can be constructed with sparse random connections, glomerular nodes, and associative learning using low dynamic-range weights. Thus, sparse quasi-random structures—characteristic of important error-correcting codes—may provide for high-performance computation in artificial neural networks and the brain.
Tasks
Published	2017-04-06
URL	http://arxiv.org/abs/1704.02019v2
PDF	http://arxiv.org/pdf/1704.02019v2.pdf
PWC	https://paperswithcode.com/paper/associative-content-addressable-networks-with
Repo
Framework

On the role of synaptic stochasticity in training low-precision neural networks


Title	On the role of synaptic stochasticity in training low-precision neural networks
Authors	Carlo Baldassi, Federica Gerace, Hilbert J. Kappen, Carlo Lucibello, Luca Saglietti, Enzo Tartaglione, Riccardo Zecchina
Abstract	Stochasticity and limited precision of synaptic weights in neural network models are key aspects of both biological and hardware modeling of learning processes. Here we show that a neural network model with stochastic binary weights naturally gives prominence to exponentially rare dense regions of solutions with a number of desirable properties such as robustness and good generalization performance, while typical solutions are isolated and hard to find. Binary solutions of the standard perceptron problem are obtained from a simple gradient descent procedure on a set of real values parametrizing a probability distribution over the binary synapses. Both analytical and numerical results are presented. An algorithmic extension aimed at training discrete deep neural networks is also investigated.
Tasks
Published	2017-10-26
URL	http://arxiv.org/abs/1710.09825v2
PDF	http://arxiv.org/pdf/1710.09825v2.pdf
PWC	https://paperswithcode.com/paper/on-the-role-of-synaptic-stochasticity-in
Repo
Framework

Efficient Column Generation for Cell Detection and Segmentation


Title	Efficient Column Generation for Cell Detection and Segmentation
Authors	Chong Zhang, Shaofei Wang, Miguel A. Gonzalez-Ballester, Julian Yarkony
Abstract	We study the problem of instance segmentation in biological images with crowded and compact cells. We formulate this task as an integer program where variables correspond to cells and constraints enforce that cells do not overlap. To solve this integer program, we propose a column generation formulation where the pricing program is solved via exact optimization of very small scale integer programs. Column generation is tightened using odd set inequalities which fit elegantly into pricing problem optimization. Our column generation approach achieves fast stable anytime inference for our instance segmentation problems. We demonstrate on three distinct light microscopy datasets, with several hundred cells each, that our proposed algorithm rapidly achieves or exceeds state of the art accuracy.
Tasks	Instance Segmentation, Semantic Segmentation
Published	2017-09-21
URL	http://arxiv.org/abs/1709.07337v1
PDF	http://arxiv.org/pdf/1709.07337v1.pdf
PWC	https://paperswithcode.com/paper/efficient-column-generation-for-cell
Repo
Framework

Multimodal Image Super-resolution via Joint Sparse Representations induced by Coupled Dictionaries


Title	Multimodal Image Super-resolution via Joint Sparse Representations induced by Coupled Dictionaries
Authors	Pingfan Song, Xin Deng, João F. C. Mota, Nikos Deligiannis, Pier Luigi Dragotti, Miguel R. D. Rodrigues
Abstract	Real-world data processing problems often involve various image modalities associated with a certain scene, including RGB images, infrared images or multi-spectral images. The fact that different image modalities often share certain attributes, such as certain edges, textures and other structure primitives, represents an opportunity to enhance various image processing tasks. This paper proposes a new approach to construct a high-resolution (HR) version of a low-resolution (LR) image given another HR image modality as reference, based on joint sparse representations induced by coupled dictionaries. Our approach, which captures the similarities and disparities between different image modalities in a learned sparse feature domain in \emph{lieu} of the original image domain, consists of two phases. The coupled dictionary learning phase is used to learn a set of dictionaries that couple different image modalities in the sparse feature domain given a set of training data. In turn, the coupled super-resolution phase leverages such coupled dictionaries to construct a HR version of the LR target image given another related image modality. One of the merits of our sparsity-driven approach relates to the fact that it overcomes drawbacks such as the texture copying artifacts commonly resulting from inconsistency between the guidance and target images. Experiments on real multimodal images demonstrate that incorporating appropriate guidance information via joint sparse representation induced by coupled dictionary learning brings notable benefits in the super-resolution task with respect to the state-of-the-art. Of particular relevance, the proposed approach also demonstrates better robustness than competing deep-learning-based methods in the presence of noise.
Tasks	Dictionary Learning, Image Super-Resolution, Super-Resolution
Published	2017-09-25
URL	http://arxiv.org/abs/1709.08680v2
PDF	http://arxiv.org/pdf/1709.08680v2.pdf
PWC	https://paperswithcode.com/paper/multimodal-image-super-resolution-via-joint
Repo
Framework

NeuroRule: A Connectionist Approach to Data Mining


Title	NeuroRule: A Connectionist Approach to Data Mining
Authors	Hongjun Lu, Rudy Setiono, Huan Liu
Abstract	Classification, which involves finding rules that partition a given data set into disjoint groups, is one class of data mining problems. Approaches proposed so far for mining classification rules for large databases are mainly decision tree based symbolic learning methods. The connectionist approach based on neural networks has been thought not well suited for data mining. One of the major reasons cited is that knowledge generated by neural networks is not explicitly represented in the form of rules suitable for verification or interpretation by humans. This paper examines this issue. With our newly developed algorithms, rules which are similar to, or more concise than those generated by the symbolic methods can be extracted from the neural networks. The data mining process using neural networks with the emphasis on rule extraction is described. Experimental results and comparison with previously published works are presented.
Tasks
Published	2017-01-05
URL	http://arxiv.org/abs/1701.01358v1
PDF	http://arxiv.org/pdf/1701.01358v1.pdf
PWC	https://paperswithcode.com/paper/neurorule-a-connectionist-approach-to-data
Repo
Framework

A Bidirectional Adaptive Bandwidth Mean Shift Strategy for Clustering


Title	A Bidirectional Adaptive Bandwidth Mean Shift Strategy for Clustering
Authors	Fanyang Meng, Hong Liu, Yongsheng Liang, Wei Liu, Jihong Pei
Abstract	The bandwidth of a kernel function is a crucial parameter in the mean shift algorithm. This paper proposes a novel adaptive bandwidth strategy which contains three main contributions. (1) The differences among different adaptive bandwidth are analyzed. (2) A new mean shift vector based on bidirectional adaptive bandwidth is defined, which combines the advantages of different adaptive bandwidth strategies. (3) A bidirectional adaptive bandwidth mean shift (BAMS) strategy is proposed to improve the ability to escape from the local maximum density. Compared with contemporary adaptive bandwidth mean shift strategies, experiments demonstrate the effectiveness of the proposed strategy.
Tasks
Published	2017-12-22
URL	http://arxiv.org/abs/1712.08283v1
PDF	http://arxiv.org/pdf/1712.08283v1.pdf
PWC	https://paperswithcode.com/paper/a-bidirectional-adaptive-bandwidth-mean-shift
Repo
Framework

Parameter Adaptation and Criticality in Particle Swarm Optimization


Title	Parameter Adaptation and Criticality in Particle Swarm Optimization
Authors	Carlos Garcia Cordero
Abstract	Generality is one of the main advantages of heuristic algorithms, as such, multiple parameters are exposed to the user with the objective of allowing them to shape the algorithms to their specific needs. Parameter selection, therefore, becomes an intrinsic problem of every heuristic algorithm. Selecting good parameter values relies not only on knowledge related to the problem at hand, but to the algorithms themselves. This research explores the usage of self-organized criticality to reduce user interaction in the process of selecting suitable parameters for particle swarm optimization (PSO) heuristics. A particle swarm variant (named Adaptive PSO) with self-organized criticality is developed and benchmarked against the standard PSO. Criticality is observed in the dynamic behaviour of this swarm and excellent results are observed in the long run. In contrast with the standard PSO, the Adaptive PSO does not stagnate at any point in time, balancing the concepts of exploration and exploitation better. A software platform for experimenting with particle swarms, called PSO Laboratory, is also developed. This software is used to test the standard PSO as well as all other PSO variants developed in the process of creating the Adaptive PSO. As the software is intended to be of aid to future and related research, special attention has been put in the development of a friendly graphical user interface. Particle swarms are executed in real time, allowing users to experiment by changing parameters on-the-fly.
Tasks
Published	2017-05-19
URL	http://arxiv.org/abs/1705.06966v1
PDF	http://arxiv.org/pdf/1705.06966v1.pdf
PWC	https://paperswithcode.com/paper/parameter-adaptation-and-criticality-in
Repo
Framework

Online and Batch Supervised Background Estimation via L1 Regression


Title	Online and Batch Supervised Background Estimation via L1 Regression
Authors	Aritra Dutta, Peter Richtarik
Abstract	We propose a surprisingly simple model for supervised video background estimation. Our model is based on $\ell_1$ regression. As existing methods for $\ell_1$ regression do not scale to high-resolution videos, we propose several simple and scalable methods for solving the problem, including iteratively reweighted least squares, a homotopy method, and stochastic gradient descent. We show through extensive experiments that our model and methods match or outperform the state-of-the-art online and batch methods in virtually all quantitative and qualitative measures.
Tasks
Published	2017-11-23
URL	http://arxiv.org/abs/1712.02249v1
PDF	http://arxiv.org/pdf/1712.02249v1.pdf
PWC	https://paperswithcode.com/paper/online-and-batch-supervised-background
Repo
Framework

Learning Differentially Private Recurrent Language Models


Title	Learning Differentially Private Recurrent Language Models
Authors	H. Brendan McMahan, Daniel Ramage, Kunal Talwar, Li Zhang
Abstract	We demonstrate that it is possible to train large recurrent language models with user-level differential privacy guarantees with only a negligible cost in predictive accuracy. Our work builds on recent advances in the training of deep networks on user-partitioned data and privacy accounting for stochastic gradient descent. In particular, we add user-level privacy protection to the federated averaging algorithm, which makes “large step” updates from user-level data. Our work demonstrates that given a dataset with a sufficiently large number of users (a requirement easily met by even small internet-scale datasets), achieving differential privacy comes at the cost of increased computation, rather than in decreased utility as in most prior work. We find that our private LSTM language models are quantitatively and qualitatively similar to un-noised models when trained on a large dataset.
Tasks
Published	2017-10-18
URL	http://arxiv.org/abs/1710.06963v3
PDF	http://arxiv.org/pdf/1710.06963v3.pdf
PWC	https://paperswithcode.com/paper/learning-differentially-private-recurrent
Repo
Framework

Objectness Scoring and Detection Proposals in Forward-Looking Sonar Images with Convolutional Neural Networks


Title	Objectness Scoring and Detection Proposals in Forward-Looking Sonar Images with Convolutional Neural Networks
Authors	Matias Valdenegro-Toro
Abstract	Forward-looking sonar can capture high resolution images of underwater scenes, but their interpretation is complex. Generic object detection in such images has not been solved, specially in cases of small and unknown objects. In comparison, detection proposal algorithms have produced top performing object detectors in real-world color images. In this work we develop a Convolutional Neural Network that can reliably score objectness of image windows in forward-looking sonar images and by thresholding objectness, we generate detection proposals. In our dataset of marine garbage objects, we obtain 94% recall, generating around 60 proposals per image. The biggest strength of our method is that it can generalize to previously unseen objects. We show this by detecting chain links, walls and a wrench without previous training in such objects. We strongly believe our method can be used for class-independent object detection, with many real-world applications such as chain following and mine detection.
Tasks	Object Detection
Published	2017-09-08
URL	http://arxiv.org/abs/1709.02600v1
PDF	http://arxiv.org/pdf/1709.02600v1.pdf
PWC	https://paperswithcode.com/paper/objectness-scoring-and-detection-proposals-in
Repo
Framework

Safe Reinforcement Learning via Shielding


Title	Safe Reinforcement Learning via Shielding
Authors	Mohammed Alshiekh, Roderick Bloem, Ruediger Ehlers, Bettina Könighofer, Scott Niekum, Ufuk Topcu
Abstract	Reinforcement learning algorithms discover policies that maximize reward, but do not necessarily guarantee safety during learning or execution phases. We introduce a new approach to learn optimal policies while enforcing properties expressed in temporal logic. To this end, given the temporal logic specification that is to be obeyed by the learning system, we propose to synthesize a reactive system called a shield. The shield is introduced in the traditional learning process in two alternative ways, depending on the location at which the shield is implemented. In the first one, the shield acts each time the learning agent is about to make a decision and provides a list of safe actions. In the second way, the shield is introduced after the learning agent. The shield monitors the actions from the learner and corrects them only if the chosen action causes a violation of the specification. We discuss which requirements a shield must meet to preserve the convergence guarantees of the learner. Finally, we demonstrate the versatility of our approach on several challenging reinforcement learning scenarios.
Tasks
Published	2017-08-29
URL	http://arxiv.org/abs/1708.08611v2
PDF	http://arxiv.org/pdf/1708.08611v2.pdf
PWC	https://paperswithcode.com/paper/safe-reinforcement-learning-via-shielding
Repo
Framework