October 20, 2019

3078 words 15 mins read

Paper Group ANR 64

Variance Reduction Methods for Sublinear Reinforcement Learning. Building a Kannada POS Tagger Using Machine Learning and Neural Network Models. A parallel implementation of the covariance matrix adaptation evolution strategy. Mitigating Architectural Mismatch During the Evolutionary Synthesis of Deep Neural Networks. Does Your Phone Know Your Touc …

Variance Reduction Methods for Sublinear Reinforcement Learning


Title	Variance Reduction Methods for Sublinear Reinforcement Learning
Authors	Sham Kakade, Mengdi Wang, Lin F. Yang
Abstract	This work considers the problem of provably optimal reinforcement learning for episodic finite horizon MDPs, i.e. how an agent learns to maximize his/her long term reward in an uncertain environment. The main contribution is in providing a novel algorithm — Variance-reduced Upper Confidence Q-learning (vUCQ) — which enjoys a regret bound of $\widetilde{O}(\sqrt{HSAT} + H^5SA)$, where the $T$ is the number of time steps the agent acts in the MDP, $S$ is the number of states, $A$ is the number of actions, and $H$ is the (episodic) horizon time. This is the first regret bound that is both sub-linear in the model size and asymptotically optimal. The algorithm is sub-linear in that the time to achieve $\epsilon$-average regret for any constant $\epsilon$ is $O(SA)$, which is a number of samples that is far less than that required to learn any non-trivial estimate of the transition model (the transition model is specified by $O(S^2A)$ parameters). The importance of sub-linear algorithms is largely the motivation for algorithms such as $Q$-learning and other “model free” approaches. vUCQ algorithm also enjoys minimax optimal regret in the long run, matching the $\Omega(\sqrt{HSAT})$ lower bound. Variance-reduced Upper Confidence Q-learning (vUCQ) is a successive refinement method in which the algorithm reduces the variance in $Q$-value estimates and couples this estimation scheme with an upper confidence based algorithm. Technically, the coupling of both of these techniques is what leads to the algorithm enjoying both the sub-linear regret property and the asymptotically optimal regret.
Tasks	Q-Learning
Published	2018-02-26
URL	http://arxiv.org/abs/1802.09184v3
PDF	http://arxiv.org/pdf/1802.09184v3.pdf
PWC	https://paperswithcode.com/paper/variance-reduction-methods-for-sublinear
Repo
Framework

Building a Kannada POS Tagger Using Machine Learning and Neural Network Models


Title	Building a Kannada POS Tagger Using Machine Learning and Neural Network Models
Authors	Ketan Kumar Todi, Pruthwik Mishra, Dipti Misra Sharma
Abstract	POS Tagging serves as a preliminary task for many NLP applications. Kannada is a relatively poor Indian language with very limited number of quality NLP tools available for use. An accurate and reliable POS Tagger is essential for many NLP tasks like shallow parsing, dependency parsing, sentiment analysis, named entity recognition. We present a statistical POS tagger for Kannada using different machine learning and neural network models. Our Kannada POS tagger outperforms the state-of-the-art Kannada POS tagger by 6%. Our contribution in this paper is three folds - building a generic POS Tagger, comparing the performances of different modeling techniques, exploring the use of character and word embeddings together for Kannada POS Tagging.
Tasks	Dependency Parsing, Named Entity Recognition, Sentiment Analysis, Word Embeddings
Published	2018-08-09
URL	http://arxiv.org/abs/1808.03175v1
PDF	http://arxiv.org/pdf/1808.03175v1.pdf
PWC	https://paperswithcode.com/paper/building-a-kannada-pos-tagger-using-machine
Repo
Framework

A parallel implementation of the covariance matrix adaptation evolution strategy


Title	A parallel implementation of the covariance matrix adaptation evolution strategy
Authors	Najeeb Khan
Abstract	In many practical optimization problems, the derivatives of the functions to be optimized are unavailable or unreliable. Such optimization problems are solved using derivative-free optimization techniques. One of the state-of-the-art techniques for derivative-free optimization is the covariance matrix adaptation evolution strategy (CMA-ES) algorithm. However, the complexity of CMA-ES algorithm makes it undesirable for tasks where fast optimization is needed. To reduce the execution time of CMA-ES, a parallel implementation is proposed, and its performance is analyzed using the benchmark problems in PythOPT optimization environment.
Tasks
Published	2018-05-28
URL	http://arxiv.org/abs/1805.11201v1
PDF	http://arxiv.org/pdf/1805.11201v1.pdf
PWC	https://paperswithcode.com/paper/a-parallel-implementation-of-the-covariance
Repo
Framework

Mitigating Architectural Mismatch During the Evolutionary Synthesis of Deep Neural Networks


Title	Mitigating Architectural Mismatch During the Evolutionary Synthesis of Deep Neural Networks
Authors	Audrey Chung, Paul Fieguth, Alexander Wong
Abstract	Evolutionary deep intelligence has recently shown great promise for producing small, powerful deep neural network models via the organic synthesis of increasingly efficient architectures over successive generations. Existing evolutionary synthesis processes, however, have allowed the mating of parent networks independent of architectural alignment, resulting in a mismatch of network structures. We present a preliminary study into the effects of architectural alignment during evolutionary synthesis using a gene tagging system. Surprisingly, the network architectures synthesized using the gene tagging approach resulted in slower decreases in performance accuracy and storage size; however, the resultant networks were comparable in size and performance accuracy to the non-gene tagging networks. Furthermore, we speculate that there is a noticeable decrease in network variability for networks synthesized with gene tagging, indicating that enforcing a like-with-like mating policy potentially restricts the exploration of the search space of possible network architectures.
Tasks
Published	2018-11-19
URL	http://arxiv.org/abs/1811.07966v1
PDF	http://arxiv.org/pdf/1811.07966v1.pdf
PWC	https://paperswithcode.com/paper/mitigating-architectural-mismatch-during-the
Repo
Framework

Does Your Phone Know Your Touch?


Title	Does Your Phone Know Your Touch?
Authors	John Peruzzi, Phillip Andrew Wingard, David Zucker
Abstract	This paper explores supervised techniques for continuous anomaly detection from biometric touch screen data. A capacitive sensor array used to mimic a touch screen as used to collect touch and swipe gestures from participants. The gestures are recorded over fixed segments of time, with position and force measured for each gesture. Support Vector Machine, Logistic Regression, and Gaussian mixture models were tested to learn individual touch patterns. Test results showed true negative and true positive scores of over 95% accuracy for all gesture types, with logistic regression models far outperforming the other methods. A more expansive and varied data collection over longer periods of time is needed to determine pragmatic usage of these results.
Tasks	Anomaly Detection
Published	2018-09-10
URL	http://arxiv.org/abs/1809.03402v1
PDF	http://arxiv.org/pdf/1809.03402v1.pdf
PWC	https://paperswithcode.com/paper/does-your-phone-know-your-touch
Repo
Framework

Progressive Feature Alignment for Unsupervised Domain Adaptation


Title	Progressive Feature Alignment for Unsupervised Domain Adaptation
Authors	Chaoqi Chen, Weiping Xie, Wenbing Huang, Yu Rong, Xinghao Ding, Yue Huang, Tingyang Xu, Junzhou Huang
Abstract	Unsupervised domain adaptation (UDA) transfers knowledge from a label-rich source domain to a fully-unlabeled target domain. To tackle this task, recent approaches resort to discriminative domain transfer in virtue of pseudo-labels to enforce the class-level distribution alignment across the source and target domains. These methods, however, are vulnerable to the error accumulation and thus incapable of preserving cross-domain category consistency, as the pseudo-labeling accuracy is not guaranteed explicitly. In this paper, we propose the Progressive Feature Alignment Network (PFAN) to align the discriminative features across domains progressively and effectively, via exploiting the intra-class variation in the target domain. To be specific, we first develop an Easy-to-Hard Transfer Strategy (EHTS) and an Adaptive Prototype Alignment (APA) step to train our model iteratively and alternatively. Moreover, upon observing that a good domain adaptation usually requires a non-saturated source classifier, we consider a simple yet efficient way to retard the convergence speed of the source classification loss by further involving a temperature variate into the soft-max function. The extensive experimental results reveal that the proposed PFAN exceeds the state-of-the-art performance on three UDA datasets.
Tasks	Domain Adaptation, Unsupervised Domain Adaptation
Published	2018-11-21
URL	https://arxiv.org/abs/1811.08585v2
PDF	https://arxiv.org/pdf/1811.08585v2.pdf
PWC	https://paperswithcode.com/paper/progressive-feature-alignment-for
Repo
Framework

Human vs Automatic Metrics: on the Importance of Correlation Design


Title	Human vs Automatic Metrics: on the Importance of Correlation Design
Authors	Anastasia Shimorina
Abstract	This paper discusses two existing approaches to the correlation analysis between automatic evaluation metrics and human scores in the area of natural language generation. Our experiments show that depending on the usage of a system- or sentence-level correlation analysis, correlation results between automatic scores and human judgments are inconsistent.
Tasks	Text Generation
Published	2018-05-29
URL	http://arxiv.org/abs/1805.11474v2
PDF	http://arxiv.org/pdf/1805.11474v2.pdf
PWC	https://paperswithcode.com/paper/human-vs-automatic-metrics-on-the-importance
Repo
Framework

Snap ML: A Hierarchical Framework for Machine Learning


Title	Snap ML: A Hierarchical Framework for Machine Learning
Authors	Celestine Dünner, Thomas Parnell, Dimitrios Sarigiannis, Nikolas Ioannou, Andreea Anghel, Gummadi Ravi, Madhusudanan Kandasamy, Haralampos Pozidis
Abstract	We describe a new software framework for fast training of generalized linear models. The framework, named Snap Machine Learning (Snap ML), combines recent advances in machine learning systems and algorithms in a nested manner to reflect the hierarchical architecture of modern computing systems. We prove theoretically that such a hierarchical system can accelerate training in distributed environments where intra-node communication is cheaper than inter-node communication. Additionally, we provide a review of the implementation of Snap ML in terms of GPU acceleration, pipelining, communication patterns and software architecture, highlighting aspects that were critical for achieving high performance. We evaluate the performance of Snap ML in both single-node and multi-node environments, quantifying the benefit of the hierarchical scheme and the data streaming functionality, and comparing with other widely-used machine learning software frameworks. Finally, we present a logistic regression benchmark on the Criteo Terabyte Click Logs dataset and show that Snap ML achieves the same test loss an order of magnitude faster than any of the previously reported results, including those obtained using TensorFlow and scikit-learn.
Tasks
Published	2018-03-16
URL	http://arxiv.org/abs/1803.06333v3
PDF	http://arxiv.org/pdf/1803.06333v3.pdf
PWC	https://paperswithcode.com/paper/snap-ml-a-hierarchical-framework-for-machine
Repo
Framework

Topological Approaches to Deep Learning


Title	Topological Approaches to Deep Learning
Authors	Gunnar Carlsson, Rickard Brüel Gabrielsson
Abstract	We perform topological data analysis on the internal states of convolutional deep neural networks to develop an understanding of the computations that they perform. We apply this understanding to modify the computations so as to (a) speed up computations and (b) improve generalization from one data set of digits to another. One byproduct of the analysis is the production of a geometry on new sets of features on data sets of images, and use this observation to develop a methodology for constructing analogues of CNN’s for many other geometries, including the graph structures constructed by topological data analysis.
Tasks	Topological Data Analysis
Published	2018-11-02
URL	http://arxiv.org/abs/1811.01122v1
PDF	http://arxiv.org/pdf/1811.01122v1.pdf
PWC	https://paperswithcode.com/paper/topological-approaches-to-deep-learning
Repo
Framework

Exposition and Interpretation of the Topology of Neural Networks


Title	Exposition and Interpretation of the Topology of Neural Networks
Authors	Rickard Brüel Gabrielsson, Gunnar Carlsson
Abstract	Convolutional neural networks (CNN’s) are powerful and widely used tools. However, their interpretability is far from ideal. One such shortcoming is the difficulty of deducing a network’s ability to generalize to unseen data. We use topological data analysis to show that the information encoded in the weights of a CNN can be organized in terms of a topological data model and demonstrate how such information can be interpreted and utilized. We show that the weights of convolutional layers at depths from 1 through 13 learn simple global structures. We also demonstrate the change of the simple structures over the course of training. In particular, we define and analyze the spaces of spatial filters of convolutional layers and show the recurrence, among all networks, depths, and during training, of a simple circle consisting of rotating edges, as well as a less recurring unanticipated complex circle that combines lines, edges, and non-linear patterns. We also demonstrate that topological structure correlates with a network’s ability to generalize to unseen data and that topological information can be used to improve a network’s performance. We train over a thousand CNN’s on MNIST, CIFAR-10, SVHN, and ImageNet.
Tasks	Topological Data Analysis
Published	2018-10-08
URL	https://arxiv.org/abs/1810.03234v3
PDF	https://arxiv.org/pdf/1810.03234v3.pdf
PWC	https://paperswithcode.com/paper/exposition-and-interpretation-of-the-topology
Repo
Framework

Temporal Unknown Incremental Clustering (TUIC) Model for Analysis of Traffic Surveillance Videos


Title	Temporal Unknown Incremental Clustering (TUIC) Model for Analysis of Traffic Surveillance Videos
Authors	Santhosh Kelathodi Kumaran, Debi Prosad Dogra, Partha Pratim Roy
Abstract	Optimized scene representation is an important characteristic of a framework for detecting abnormalities on live videos. One of the challenges for detecting abnormalities in live videos is real-time detection of objects in a non-parametric way. Another challenge is to efficiently represent the state of objects temporally across frames. In this paper, a Gibbs sampling based heuristic model referred to as Temporal Unknown Incremental Clustering (TUIC) has been proposed to cluster pixels with motion. Pixel motion is first detected using optical flow and a Bayesian algorithm has been applied to associate pixels belonging to similar cluster in subsequent frames. The algorithm is fast and produces accurate results in $\Theta(kn)$ time, where $k$ is the number of clusters and $n$ the number of pixels. Our experimental validation with publicly available datasets reveals that the proposed framework has good potential to open-up new opportunities for real-time traffic analysis.
Tasks	Optical Flow Estimation
Published	2018-04-18
URL	http://arxiv.org/abs/1804.06680v1
PDF	http://arxiv.org/pdf/1804.06680v1.pdf
PWC	https://paperswithcode.com/paper/temporal-unknown-incremental-clustering-tuic
Repo
Framework

Learning to Optimize Tensor Programs


Title	Learning to Optimize Tensor Programs
Authors	Tianqi Chen, Lianmin Zheng, Eddie Yan, Ziheng Jiang, Thierry Moreau, Luis Ceze, Carlos Guestrin, Arvind Krishnamurthy
Abstract	We introduce a learning-based framework to optimize tensor programs for deep learning workloads. Efficient implementations of tensor operators, such as matrix multiplication and high dimensional convolution, are key enablers of effective deep learning systems. However, existing systems rely on manually optimized libraries such as cuDNN where only a narrow range of server class GPUs are well-supported. The reliance on hardware-specific operator libraries limits the applicability of high-level graph optimizations and incurs significant engineering costs when deploying to new hardware targets. We use learning to remove this engineering burden. We learn domain-specific statistical cost models to guide the search of tensor operator implementations over billions of possible program variants. We further accelerate the search by effective model transfer across workloads. Experimental results show that our framework delivers performance competitive with state-of-the-art hand-tuned libraries for low-power CPU, mobile GPU, and server-class GPU.
Tasks
Published	2018-05-21
URL	http://arxiv.org/abs/1805.08166v4
PDF	http://arxiv.org/pdf/1805.08166v4.pdf
PWC	https://paperswithcode.com/paper/learning-to-optimize-tensor-programs
Repo
Framework

The Topology ToolKit


Title	The Topology ToolKit
Authors	Julien Tierny, Guillaume Favelier, Joshua A. Levine, Charles Gueunet, Michael Michaux
Abstract	This system paper presents the Topology ToolKit (TTK), a software platform designed for topological data analysis in scientific visualization. TTK provides a unified, generic, efficient, and robust implementation of key algorithms for the topological analysis of scalar data, including: critical points, integral lines, persistence diagrams, persistence curves, merge trees, contour trees, Morse-Smale complexes, fiber surfaces, continuous scatterplots, Jacobi sets, Reeb spaces, and more. TTK is easily accessible to end users due to a tight integration with ParaView. It is also easily accessible to developers through a variety of bindings (Python, VTK/C++) for fast prototyping or through direct, dependence-free, C++, to ease integration into pre-existing complex systems. While developing TTK, we faced several algorithmic and software engineering challenges, which we document in this paper. In particular, we present an algorithm for the construction of a discrete gradient that complies to the critical points extracted in the piecewise-linear setting. This algorithm guarantees a combinatorial consistency across the topological abstractions supported by TTK, and importantly, a unified implementation of topological data simplification for multi-scale exploration and analysis. We also present a cached triangulation data structure, that supports time efficient and generic traversals, which self-adjusts its memory usage on demand for input simplicial meshes and which implicitly emulates a triangulation for regular grids with no memory overhead. Finally, we describe an original software architecture, which guarantees memory efficient and direct accesses to TTK features, while still allowing for researchers powerful and easy bindings and extensions. TTK is open source (BSD license) and its code, online documentation and video tutorials are available on TTK’s website.
Tasks	Topological Data Analysis
Published	2018-05-22
URL	https://arxiv.org/abs/1805.09110v2
PDF	https://arxiv.org/pdf/1805.09110v2.pdf
PWC	https://paperswithcode.com/paper/the-topology-toolkit
Repo
Framework

Variational Bayes Inference in Digital Receivers


Title	Variational Bayes Inference in Digital Receivers
Authors	Viet Hung Tran
Abstract	The digital telecommunications receiver is an important context for inference methodology, the key objective being to minimize the expected loss function in recovering the transmitted information. For that criterion, the optimal decision is the Bayesian minimum-risk estimator. However, the computational load of the Bayesian estimator is often prohibitive and, hence, efficient computational schemes are required. The design of novel schemes, striking new balances between accuracy and computational load, is the primary concern of this thesis. Two popular techniques, one exact and one approximate, will be studied. The exact scheme is a recursive one, namely the generalized distributive law (GDL), whose purpose is to distribute all operators across the conditionally independent (CI) factors of the joint model, so as to reduce the total number of operators required. In a novel theorem derived in this thesis, GDL, if applicable, will be shown to guarantee such a reduction in all cases. An associated lemma also quantifies this reduction. For practical use, two novel algorithms, namely the no-longer-needed (NLN) algorithm and the generalized form of the Markovian Forward-Backward (FB) algorithm, recursively factorizes and computes the CI factors of an arbitrary model, respectively. The approximate scheme is an iterative one, namely the Variational Bayes (VB) approximation, whose purpose is to find the independent (i.e. zero-order Markov) model closest to the true joint model in the minimum Kullback-Leibler divergence (KLD) sense. Despite being computationally efficient, this naive mean field approximation confers only modest performance for highly correlated models. A novel approximation, namely Transformed Variational Bayes (TVB), will be designed in the thesis in order to relax the zero-order constraint in the VB approximation, further reducing the KLD of the optimal approximation.
Tasks
Published	2018-11-03
URL	http://arxiv.org/abs/1811.02506v1
PDF	http://arxiv.org/pdf/1811.02506v1.pdf
PWC	https://paperswithcode.com/paper/variational-bayes-inference-in-digital
Repo
Framework

Linkage between piecewise constant Mumford-Shah model and ROF model and its virtue in image segmentation


Title	Linkage between piecewise constant Mumford-Shah model and ROF model and its virtue in image segmentation
Authors	Xiaohao Cai, Raymond Chan, Carola-Bibiane Schonlieb, Gabriele Steidl, Tieyong Zeng
Abstract	The piecewise constant Mumford-Shah (PCMS) model and the Rudin-Osher-Fatemi (ROF) model are two important variational models in image segmentation and image restoration, respectively. In this paper, we explore a linkage between these models. We prove that for the two-phase segmentation problem a partial minimizer of the PCMS model can be obtained by thresholding the minimizer of the ROF model. A similar linkage is still valid for multiphase segmentation under specific assumptions. Thus it opens a new segmentation paradigm: image segmentation can be done via image restoration plus thresholding. This new paradigm, which circumvents the innate non-convex property of the PCMS model, therefore improves the segmentation performance in both efficiency (much faster than state-of-the-art methods based on PCMS model, particularly when the phase number is high) and effectiveness (producing segmentation results with better quality) due to the flexibility of the ROF model in tackling degraded images, such as noisy images, blurry images or images with information loss. As a by-product of the new paradigm, we derive a novel segmentation method, called thresholded-ROF (T-ROF) method, to illustrate the virtue of managing image segmentation through image restoration techniques. The convergence of the T-ROF method is proved, and elaborate experimental results and comparisons are presented.
Tasks	Image Restoration, Semantic Segmentation
Published	2018-07-26
URL	https://arxiv.org/abs/1807.10194v2
PDF	https://arxiv.org/pdf/1807.10194v2.pdf
PWC	https://paperswithcode.com/paper/linkage-between-piecewise-constant-mumford
Repo
Framework