pwc-archive/papers-with-abstracts huggingface dataset:
Second-Order Semantic Dependency Parsing with End-to-End Neural Networks
Authors: Xinyu Wang, Jingxian Huang, Kewei Tu
Date: 2019-06-19 00:00:00
Proceeding: ACL 2019 7
Tasks: Dependency Parsing, Semantic Dependency Parsing, Sentence, Variational Inference

Semantic dependency parsing aims to identify semantic relationships between words in a sentence that form a graph. In this paper, we propose a second-order semantic dependency parser, which takes into consideration not only individual dependency edges but also interactions between pairs of edges. We show that second-order parsing can be approximated using mean field (MF) variational inference or loopy belief propagation (LBP). We can unfold both algorithms as recurrent layers of a neural network and therefore can train the parser in an end-to-end manner. Our experiments show that our approach achieves state-of-the-art performance.
Joint Regularization on Activations and Weights for Efficient Neural Network Pruning
Authors: Qing Yang, Wei Wen, Zuoguan Wang, Hai Li
Date: 2019-06-19 00:00:00
Tasks: Efficient Neural Network, Model Compression, Network Pruning

With the rapid scaling up of deep neural networks (DNNs), extensive research studies on network model compression such as weight pruning have been performed for improving deployment efficiency. This work aims to advance the compression beyond the weights to neuron activations. We propose the joint regularization technique which simultaneously regulates the distribution of weights and activations. By distinguishing and leveraging the significance difference among neuron responses and connections during learning, the jointly pruned network, namely \textit{JPnet}, optimizes the sparsity of activations and weights for improving execution efficiency. The derived deep sparsification of JPnet reveals more optimization space for the existing DNN accelerators dedicated for sparse matrix operations. We thoroughly evaluate the effectiveness of joint regularization through various network models with different activation functions and on different datasets. With $0.4\%$ degradation constraint on inference accuracy, a JPnet can save $72.3\% \sim 98.8\%$ of computation cost compared to the original dense models, with up to $5.2\times$ and $12.3\times$ reductions in activation and weight numbers, respectively.
Space Efficient Algorithms for Breadth-Depth Search
Authors: Sankardeep Chakraborty, Anish Mukherjee, Srinivasa Rao Satti
Date: 2019-06-19 00:00:00

Continuing the recent trend, in this article we design several space-efficient algorithms for two well-known graph search methods. Both these search methods share the same name {\it breadth-depth search} (henceforth {\sf BDS}), although they work entirely in different fashion. The classical implementation for these graph search methods takes $O(m+n)$ time and $O(n \lg n)$ bits of space in the standard word RAM model (with word size being $\Theta(\lg n)$ bits), where $m$ and $n$ denotes the number of edges and vertices of the input graph respectively. Our goal here is to beat the space bound of the classical implementations, and design $o(n \lg n)$ space algorithms for these search methods by paying little to no penalty in the running time. Note that our space bounds (i.e., with $o(n \lg n)$ bits of space) do not even allow us to explicitly store the required information to implement the classical algorithms, yet our algorithms visits and reports all the vertices of the input graph in correct order.
Indexing Graph Search Trees and Applications
Authors: Sankardeep Chakraborty, Kunihiko Sadakane
Date: 2019-06-19 00:00:00

We consider the problem of compactly representing the Depth First Search (DFS) tree of a given undirected or directed graph having $n$ vertices and $m$ edges while supporting various DFS related queries efficiently in the RAM with logarithmic word size. We study this problem in two well-known models: {\it indexing} and {\it encoding} models. While most of these queries can be supported easily in constant time using $O(n \lg n)$ bits\footnote{We use $\lg$ to denote logarithm to the base $2$.} of extra space, our goal here is, more specifically, to beat this trivial $O(n \lg n)$ bit space bound, yet not compromise too much on the running time of these queries. In the {\it indexing} model, the space bound of our solution involves the quantity $m$, hence, we obtain different bounds for sparse and dense graphs respectively. In the {\it encoding} model, we first give a space lower bound, followed by an almost optimal data structure with extremely fast query time. Central to our algorithm is a partitioning of the DFS tree into connected subtrees, and a compact way to store these connections. Finally, we also apply these techniques to compactly index the shortest path structure, biconnectivity structures among others.
Analytical Derivatives for Differentiable Renderer: 3D Pose Estimation by Silhouette Consistency
Authors: Zaiqiang Wu, Wei Jiang
Date: 2019-06-19 00:00:00
Tasks: 3D Pose Estimation, 3D Reconstruction, Pose Estimation

Differentiable render is widely used in optimization-based 3D reconstruction which requires gradients from differentiable operations for gradient-based optimization. The existing differentiable renderers obtain the gradients of rendering via numerical technique which is of low accuracy and efficiency. Motivated by this fact, a differentiable mesh renderer with analytical gradients is proposed. The main obstacle of rasterization based rendering being differentiable is the discrete sampling operation. To make the rasterization differentiable, the pixel intensity is defined as a double integral over the pixel area and the integral is approximated by anti-aliasing with an average filter. Then the analytical gradients with respect to the vertices coordinates can be derived from the continuous definition of pixel intensity. To demonstrate the effectiveness and efficiency of the proposed differentiable renderer, experiments of 3D pose estimation by only multi-viewpoint silhouettes were conducted. The experimental results show that 3D pose estimation without 3D and 2D joints supervision is capable of producing competitive results both qualitatively and quantitatively. The experimental results also show that the proposed differentiable renderer is of higher accuracy and efficiency compared with previous method of differentiable renderer.
Identifiability of Hierarchical Latent Attribute Models
Authors: Yuqi Gu, Gongjun Xu
Date: 2019-06-19 00:00:00
Tasks: Attribute, Diagnostic

Hierarchical Latent Attribute Models (HLAMs) are a family of discrete latent variable models that are attracting increasing attention in educational, psychological, and behavioral sciences. The key ingredients of an HLAM include a binary structural matrix and a directed acyclic graph specifying hierarchical constraints on the configurations of latent attributes. These components encode practitioners' design information and carry important scientific meanings. Despite the popularity of HLAMs, the fundamental identifiability issue remains unaddressed. The existence of the attribute hierarchy graph leads to degenerate parameter space, and the potentially unknown structural matrix further complicates the identifiability problem. This paper addresses this issue of identifying the latent structure and model parameters underlying an HLAM. We develop sufficient and necessary identifiability conditions. These results directly and sharply characterize the different impacts on identifiability cast by different attribute types in the graph. The proposed conditions not only provide insights into diagnostic test designs under the attribute hierarchy, but also serve as tools to assess the validity of an estimated HLAM.
Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyond
Authors: Xuechen Li, Denny Wu, Lester Mackey, Murat A. Erdogdu
Date: 2019-06-19 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Numerical Integration

Sampling with Markov chain Monte Carlo methods often amounts to discretizing some continuous-time dynamics with numerical integration. In this paper, we establish the convergence rate of sampling algorithms obtained by discretizing smooth It\^o diffusions exhibiting fast Wasserstein-$2$ contraction, based on local deviation properties of the integration scheme. In particular, we study a sampling algorithm constructed by discretizing the overdamped Langevin diffusion with the method of stochastic Runge-Kutta. For strongly convex potentials that are smooth up to a certain order, its iterates converge to the target distribution in $2$-Wasserstein distance in $\tilde{\mathcal{O}}(d\epsilon^{-2/3})$ iterations. This improves upon the best-known rate for strongly log-concave sampling based on the overdamped Langevin equation using only the gradient oracle without adjustment. In addition, we extend our analysis of stochastic Runge-Kutta methods to uniformly dissipative diffusions with possibly non-convex potentials and show they achieve better rates compared to the Euler-Maruyama scheme in terms of the dependence on tolerance $\epsilon$. Numerical studies show that these algorithms lead to better stability and lower asymptotic errors.
Locally Accelerated Conditional Gradients
Authors: Jelena Diakonikolas, Alejandro Carderera, Sebastian Pokutta
Date: 2019-06-19 00:00:00

Conditional gradients constitute a class of projection-free first-order algorithms for smooth convex optimization. As such, they are frequently used in solving smooth convex optimization problems over polytopes, for which the computational cost of orthogonal projections would be prohibitive. However, they do not enjoy the optimal convergence rates achieved by projection-based accelerated methods; moreover, achieving such globally-accelerated rates is information-theoretically impossible for these methods. To address this issue, we present Locally Accelerated Conditional Gradients -- an algorithmic framework that couples accelerated steps with conditional gradient steps to achieve local acceleration on smooth strongly convex problems. Our approach does not require projections onto the feasible set, but only on (typically low-dimensional) simplices, thus keeping the computational cost of projections at bay. Further, it achieves the optimal accelerated local convergence. Our theoretical results are supported by numerical experiments, which demonstrate significant speedups of our framework over state of the art methods in both per-iteration progress and wall-clock time.
Event-based Star Tracking via Multiresolution Progressive Hough Transforms
Authors: Samya Bagchi, Tat-Jun Chin
Date: 2019-06-19 00:00:00
Tasks: Event-based Motion Estimation, Motion Estimation

Star trackers are state-of-the-art attitude estimation devices which function by recognising and tracking star patterns. Most commercial star trackers use conventional optical sensors. A recent alternative is to use event sensors, which could enable more energy efficient and faster star trackers. However, this demands new algorithms that can efficiently cope with high-speed asynchronous data, and are feasible on resource-constrained computing platforms. To this end, we propose an event-based processing approach for star tracking. Our technique operates on the event stream from a star field, by using multiresolution Hough Transforms to time-progressively integrate event data and produce accurate relative rotations. Optimisation via rotation averaging is then used to fuse the relative rotations and jointly refine the absolute orientations. Our technique is designed to be feasible for asynchronous operation on standard hardware. Moreover, compared to state-of-the-art event-based motion estimation schemes, our technique is much more efficient and accurate.
Adapting Behaviour via Intrinsic Reward: A Survey and Empirical Study
Authors: Cam Linke, Nadia M. Ady, Martha White, Thomas Degris, Adam White
Date: 2019-06-19 00:00:00
Tasks: Active Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Representation Learning, Survey

Learning about many things can provide numerous benefits to a reinforcement learning system. For example, learning many auxiliary value functions, in addition to optimizing the environmental reward, appears to improve both exploration and representation learning. The question we tackle in this paper is how to sculpt the stream of experience---how to adapt the learning system's behavior---to optimize the learning of a collection of value functions. A simple answer is to compute an intrinsic reward based on the statistics of each auxiliary learner, and use reinforcement learning to maximize that intrinsic reward. Unfortunately, implementing this simple idea has proven difficult, and thus has been the focus of decades of study. It remains unclear which of the many possible measures of learning would work well in a parallel learning setting where environmental reward is extremely sparse or absent. In this paper, we investigate and compare different intrinsic reward mechanisms in a new bandit-like parallel-learning testbed. We discuss the interaction between reward and prediction learners and highlight the importance of introspective prediction learners: those that increase their rate of learning when progress is possible, and decrease when it is not. We provide a comprehensive empirical comparison of 14 different rewards, including well-known ideas from reinforcement learning and active learning. Our results highlight a simple but seemingly powerful principle: intrinsic rewards based on the amount of learning can generate useful behavior, if each individual learner is introspective.
Multi-user Resource Control with Deep Reinforcement Learning in IoT Edge Computing
Authors: Lei Lei, Huijuan Xu, Xiong Xiong, Kan Zheng, Wei Xiang, Xianbin Wang
Date: 2019-06-19 00:00:00
Tasks: Deep Reinforcement Learning, Edge-computing, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Scheduling

By leveraging the concept of mobile edge computing (MEC), massive amount of data generated by a large number of Internet of Things (IoT) devices could be offloaded to MEC server at the edge of wireless network for further computational intensive processing. However, due to the resource constraint of IoT devices and wireless network, both the communications and computation resources need to be allocated and scheduled efficiently for better system performance. In this paper, we propose a joint computation offloading and multi-user scheduling algorithm for IoT edge computing system to minimize the long-term average weighted sum of delay and power consumption under stochastic traffic arrival. We formulate the dynamic optimization problem as an infinite-horizon average-reward continuous-time Markov decision process (CTMDP) model. One critical challenge in solving this MDP problem for the multi-user resource control is the curse-of-dimensionality problem, where the state space of the MDP model and the computation complexity increase exponentially with the growing number of users or IoT devices. In order to overcome this challenge, we use the deep reinforcement learning (RL) techniques and propose a neural network architecture to approximate the value functions for the post-decision system states. The designed algorithm to solve the CTMDP problem supports semi-distributed auction-based implementation, where the IoT devices submit bids to the BS to make the resource control decisions centrally. Simulation results show that the proposed algorithm provides significant performance improvement over the baseline algorithms, and also outperforms the RL algorithms based on other neural network architectures.
Supervised Hierarchical Clustering with Exponential Linkage
Authors: Nishant Yadav, Ari Kobren, Nicholas Monath, Andrew McCallum
Date: 2019-06-19 00:00:00
Tasks: Clustering

In supervised clustering, standard techniques for learning a pairwise dissimilarity function often suffer from a discrepancy between the training and clustering objectives, leading to poor cluster quality. Rectifying this discrepancy necessitates matching the procedure for training the dissimilarity function to the clustering algorithm. In this paper, we introduce a method for training the dissimilarity function in a way that is tightly coupled with hierarchical clustering, in particular single linkage. However, the appropriate clustering algorithm for a given dataset is often unknown. Thus we introduce an approach to supervised hierarchical clustering that smoothly interpolates between single, average, and complete linkage, and we give a training procedure that simultaneously learns a linkage function and a dissimilarity function. We accomplish this with a novel Exponential Linkage function that has a learnable parameter that controls the interpolation. In experiments on four datasets, our joint training procedure consistently matches or outperforms the next best training procedure/linkage function pair and gives up to 8 points improvement in dendrogram purity over discrepant pairs.
Adversarial training approach for local data debiasing
Authors: Ulrich Aïvodji, François Bidet, Sébastien Gambs, Rosin Claude Ngueveu, Alain Tapp
Date: 2019-06-19 00:00:00
Tasks: Attribute, Fairness

The widespread use of automated decision processes in many areas of our society raises serious ethical issues concerning the fairness of the process and the possible resulting discriminations. In this work, we propose a novel approach called GANsan whose objective is to prevent the possibility of any discrimination i.e., direct and indirect) based on a sensitive attribute by removing the attribute itself as well as the existing correlations with the remaining attributes. Our sanitization algorithm GANsan is partially inspired by the powerful framework of generative adversarial networks (in particular the Cycle-GANs), which offers a flexible way to learn a distribution empirically or to translate between two different distributions. In contrast to prior work, one of the strengths of our approach is that the sanitization is performed in the same space as the original data by only modifying the other attributes as little as possible and thus preserving the interpretability of the sanitized data. As a consequence, once the sanitizer is trained, it can be applied to new data, such as for instance, locally by an individual on his profile before releasing it. Finally, experiments on a real dataset demonstrate the effectiveness of the proposed approach as well as the achievable trade-off between fairness and utility.
Surf at MEDIQA 2019: Improving Performance of Natural Language Inference in the Clinical Domain by Adopting Pre-trained Language Model
Authors: Jiin Nam, Seunghyun Yoon, Kyomin Jung
Date: 2019-06-19 00:00:00
Proceeding: WS 2019 8
Tasks: Language Modeling, Language Modelling, Natural Language Inference, Transfer Learning

While deep learning techniques have shown promising results in many natural language processing (NLP) tasks, it has not been widely applied to the clinical domain. The lack of large datasets and the pervasive use of domain-specific language (i.e. abbreviations and acronyms) in the clinical domain causes slower progress in NLP tasks than that of the general NLP tasks. To fill this gap, we employ word/subword-level based models that adopt large-scale data-driven methods such as pre-trained language models and transfer learning in analyzing text for the clinical domain. Empirical results demonstrate the superiority of the proposed methods by achieving 90.6% accuracy in medical domain natural language inference task. Furthermore, we inspect the independent strengths of the proposed approaches in quantitative and qualitative manners. This analysis will help researchers to select necessary components in building models for the medical domain.
Key Instance Selection for Unsupervised Video Object Segmentation
Authors: Donghyeon Cho, Sungeun Hong, Sungil Kang, Jiwon Kim
Date: 2019-06-18 00:00:00
Tasks: Object, Segmentation, Semantic Segmentation, Unsupervised Video Object Segmentation, Video Object Segmentation, Video Semantic Segmentation

This paper proposes key instance selection based on video saliency covering objectness and dynamics for unsupervised video object segmentation (UVOS). Our method takes frames sequentially and extracts object proposals with corresponding masks for each frame. We link objects according to their similarity until the M-th frame and then assign them unique IDs (i.e., instances). Similarity measure takes into account multiple properties such as ReID descriptor, expected trajectory, and semantic co-segmentation result. After M-th frame, we select K IDs based on video saliency and frequency of appearance; then only these key IDs are tracked through the remaining frames. Thanks to these technical contributions, our results are ranked third on the leaderboard of UVOS DAVIS challenge.
Deep Learning-Based Quantization of L-Values for Gray-Coded Modulation
Authors: Marius Arvinte, Sriram Vishwanath, Ahmed H. Tewfik
Date: 2019-06-18 00:00:00
Tasks: Quantization

In this work, a deep learning-based quantization scheme for log-likelihood ratio (L-value) storage is introduced. We analyze the dependency between the average magnitude of different L-values from the same quadrature amplitude modulation (QAM) symbol and show they follow a consistent ordering. Based on this we design a deep autoencoder that jointly compresses and separately reconstructs each L-value, allowing the use of a weighted loss function that aims to more accurately reconstructs low magnitude inputs. Our method is shown to be competitive with state-of-the-art maximum mutual information quantization schemes, reducing the required memory footprint by a ratio of up to two and a loss of performance smaller than 0.1 dB with less than two effective bits per L-value or smaller than 0.04 dB with 2.25 effective bits. We experimentally show that our proposed method is a universal compression scheme in the sense that after training on an LDPC-coded Rayleigh fading scenario we can reuse the same network without further training on other channel models and codes while preserving the same performance benefits.
Symbolic regression by uniform random global search
Authors: Sohrab Towfighi
Date: 2019-06-18 00:00:00
Tasks: global-optimization, regression, Symbolic Regression

Symbolic regression (SR) is a data analysis problem where we search for the mathematical expression that best fits a numerical dataset. It is a global optimization problem. The most popular approach to SR is by genetic programming (SRGP). It is a common paradigm to compare an algorithm's performance to that of random search, but the data comparing SRGP to random search is lacking. We describe a novel algorithm for SR, namely SR by uniform random global search (SRURGS), also known as pure random search. We conduct experiments comparing SRURGS with SRGP using 100 randomly generated equations. Our results suggest that a SRGP is faster than SRURGS in producing equations with good R^2 for simple problems. However, our experiments suggest that SRURGS is more robust than SRGP, able to produce good output in more challenging problems. As SRURGS is arguably the simplest global search algorithm, we believe it should serve as a control algorithm against which other symbolic regression algorithms are compared. SRURGS has only one tuning parameter, and is conceptually very simple, making it a useful tool in solving SR problems. The method produces random equations, which is useful for the generation of symbolic regression benchmark problems. We have released well documented and open-source python code, currently under formal peer-review, so that interested researchers can deploy the tool in practice.