July 29, 2019

3162 words 15 mins read

Paper Group ANR 73

Logic Tensor Networks for Semantic Image Interpretation. Communication-Avoiding Optimization Methods for Distributed Massive-Scale Sparse Inverse Covariance Estimation. Batch-Based Activity Recognition from Egocentric Photo-Streams. A Survey on Hardware Implementations of Visual Object Trackers. Continuous State-Space Models for Optimal Sepsis Trea …

Logic Tensor Networks for Semantic Image Interpretation


Title	Logic Tensor Networks for Semantic Image Interpretation
Authors	Ivan Donadello, Luciano Serafini, Artur d’Avila Garcez
Abstract	Semantic Image Interpretation (SII) is the task of extracting structured semantic descriptions from images. It is widely agreed that the combined use of visual data and background knowledge is of great importance for SII. Recently, Statistical Relational Learning (SRL) approaches have been developed for reasoning under uncertainty and learning in the presence of data and rich knowledge. Logic Tensor Networks (LTNs) are an SRL framework which integrates neural networks with first-order fuzzy logic to allow (i) efficient learning from noisy data in the presence of logical constraints, and (ii) reasoning with logical formulas describing general properties of the data. In this paper, we develop and apply LTNs to two of the main tasks of SII, namely, the classification of an image’s bounding boxes and the detection of the relevant part-of relations between objects. To the best of our knowledge, this is the first successful application of SRL to such SII tasks. The proposed approach is evaluated on a standard image processing benchmark. Experiments show that the use of background knowledge in the form of logical constraints can improve the performance of purely data-driven approaches, including the state-of-the-art Fast Region-based Convolutional Neural Networks (Fast R-CNN). Moreover, we show that the use of logical background knowledge adds robustness to the learning system when errors are present in the labels of the training data.
Tasks	Relational Reasoning, Tensor Networks
Published	2017-05-24
URL	http://arxiv.org/abs/1705.08968v1
PDF	http://arxiv.org/pdf/1705.08968v1.pdf
PWC	https://paperswithcode.com/paper/logic-tensor-networks-for-semantic-image
Repo
Framework

Communication-Avoiding Optimization Methods for Distributed Massive-Scale Sparse Inverse Covariance Estimation


Title	Communication-Avoiding Optimization Methods for Distributed Massive-Scale Sparse Inverse Covariance Estimation
Authors	Penporn Koanantakool, Alnur Ali, Ariful Azad, Aydin Buluc, Dmitriy Morozov, Leonid Oliker, Katherine Yelick, Sang-Yun Oh
Abstract	Across a variety of scientific disciplines, sparse inverse covariance estimation is a popular tool for capturing the underlying dependency relationships in multivariate data. Unfortunately, most estimators are not scalable enough to handle the sizes of modern high-dimensional data sets (often on the order of terabytes), and assume Gaussian samples. To address these deficiencies, we introduce HP-CONCORD, a highly scalable optimization method for estimating a sparse inverse covariance matrix based on a regularized pseudolikelihood framework, without assuming Gaussianity. Our parallel proximal gradient method uses a novel communication-avoiding linear algebra algorithm and runs across a multi-node cluster with up to 1k nodes (24k cores), achieving parallel scalability on problems with up to ~819 billion parameters (1.28 million dimensions); even on a single node, HP-CONCORD demonstrates scalability, outperforming a state-of-the-art method. We also use HP-CONCORD to estimate the underlying dependency structure of the brain from fMRI data, and use the result to identify functional regions automatically. The results show good agreement with a clustering from the neuroscience literature.
Tasks
Published	2017-10-30
URL	http://arxiv.org/abs/1710.10769v2
PDF	http://arxiv.org/pdf/1710.10769v2.pdf
PWC	https://paperswithcode.com/paper/communication-avoiding-optimization-methods
Repo
Framework

Batch-Based Activity Recognition from Egocentric Photo-Streams


Title	Batch-Based Activity Recognition from Egocentric Photo-Streams
Authors	Alejandro Cartas, Mariella Dimiccoli, Petia Radeva
Abstract	Activity recognition from long unstructured egocentric photo-streams has several applications in assistive technology such as health monitoring and frailty detection, just to name a few. However, one of its main technical challenges is to deal with the low frame rate of wearable photo-cameras, which causes abrupt appearance changes between consecutive frames. In consequence, important discriminatory low-level features from motion such as optical flow cannot be estimated. In this paper, we present a batch-driven approach for training a deep learning architecture that strongly rely on Long short-term units to tackle this problem. We propose two different implementations of the same approach that process a photo-stream sequence using batches of fixed size with the goal of capturing the temporal evolution of high-level features. The main difference between these implementations is that one explicitly models consecutive batches by overlapping them. Experimental results over a public dataset acquired by three users demonstrate the validity of the proposed architectures to exploit the temporal evolution of convolutional features over time without relying on event boundaries.
Tasks	Activity Recognition, Optical Flow Estimation
Published	2017-08-25
URL	http://arxiv.org/abs/1708.07889v1
PDF	http://arxiv.org/pdf/1708.07889v1.pdf
PWC	https://paperswithcode.com/paper/batch-based-activity-recognition-from
Repo
Framework

A Survey on Hardware Implementations of Visual Object Trackers


Title	A Survey on Hardware Implementations of Visual Object Trackers
Authors	Al-Hussein A. El-Shafie, S. E. D. Habib
Abstract	Visual object tracking is an active topic in the computer vision domain with applications extending over numerous fields. The main sub-tasks required to build an object tracker (e.g. object detection, feature extraction and object tracking) are computation-intensive. In addition, real-time operation of the tracker is indispensable for almost all of its applications. Therefore, complete hardware or hardware/software co-design approaches are pursued for better tracker implementations. This paper presents a literature survey of the hardware implementations of object trackers over the last two decades. Although several tracking surveys exist in literature, a survey addressing the hardware implementations of the different trackers is missing. We believe this survey would fill the gap and complete the picture with the existing surveys of how to design an efficient tracker and point out the future directions researchers can follow in this field. We highlight the lack of hardware implementations for state-of-the-art tracking algorithms as well as for enhanced classical algorithms. We also stress the need for measuring the tracking performance of the hardware-based trackers. Additionally, enough details of the hardware-based trackers need to be provided to allow reasonable comparison between the different implementations.
Tasks	Object Detection, Object Tracking, Visual Object Tracking
Published	2017-11-07
URL	http://arxiv.org/abs/1711.02441v1
PDF	http://arxiv.org/pdf/1711.02441v1.pdf
PWC	https://paperswithcode.com/paper/a-survey-on-hardware-implementations-of
Repo
Framework

Continuous State-Space Models for Optimal Sepsis Treatment - a Deep Reinforcement Learning Approach


Title	Continuous State-Space Models for Optimal Sepsis Treatment - a Deep Reinforcement Learning Approach
Authors	Aniruddh Raghu, Matthieu Komorowski, Leo Anthony Celi, Peter Szolovits, Marzyeh Ghassemi
Abstract	Sepsis is a leading cause of mortality in intensive care units (ICUs) and costs hospitals billions annually. Treating a septic patient is highly challenging, because individual patients respond very differently to medical interventions and there is no universally agreed-upon treatment for sepsis. Understanding more about a patient’s physiological state at a given time could hold the key to effective treatment policies. In this work, we propose a new approach to deduce optimal treatment policies for septic patients by using continuous state-space models and deep reinforcement learning. Learning treatment policies over continuous spaces is important, because we retain more of the patient’s physiological information. Our model is able to learn clinically interpretable treatment policies, similar in important aspects to the treatment policies of physicians. Evaluating our algorithm on past ICU patient data, we find that our model could reduce patient mortality in the hospital by up to 3.6% over observed clinical policies, from a baseline mortality of 13.7%. The learned treatment policies could be used to aid intensive care clinicians in medical decision making and improve the likelihood of patient survival.
Tasks	Decision Making
Published	2017-05-23
URL	http://arxiv.org/abs/1705.08422v1
PDF	http://arxiv.org/pdf/1705.08422v1.pdf
PWC	https://paperswithcode.com/paper/continuous-state-space-models-for-optimal
Repo
Framework

A Local Analysis of Block Coordinate Descent for Gaussian Phase Retrieval


Title	A Local Analysis of Block Coordinate Descent for Gaussian Phase Retrieval
Authors	David Barmherzig, Ju Sun
Abstract	While convergence of the Alternating Direction Method of Multipliers (ADMM) on convex problems is well studied, convergence on nonconvex problems is only partially understood. In this paper, we consider the Gaussian phase retrieval problem, formulated as a linear constrained optimization problem with a biconvex objective. The particular structure allows for a novel application of the ADMM. It can be shown that the dual variable is zero at the global minimizer. This motivates the analysis of a block coordinate descent algorithm, which is equivalent to the ADMM with the dual variable fixed to be zero. We show that the block coordinate descent algorithm converges to the global minimizer at a linear rate, when starting from a deterministically achievable initialization point.
Tasks
Published	2017-12-06
URL	http://arxiv.org/abs/1712.02083v1
PDF	http://arxiv.org/pdf/1712.02083v1.pdf
PWC	https://paperswithcode.com/paper/a-local-analysis-of-block-coordinate-descent
Repo
Framework

Stochastic Variational Inference for Bayesian Sparse Gaussian Process Regression


Title	Stochastic Variational Inference for Bayesian Sparse Gaussian Process Regression
Authors	Haibin Yu, Trong Nghia Hoang, Kian Hsiang Low, Patrick Jaillet
Abstract	This paper presents a novel variational inference framework for deriving a family of Bayesian sparse Gaussian process regression (SGPR) models whose approximations are variationally optimal with respect to the full-rank GPR model enriched with various corresponding correlation structures of the observation noises. Our variational Bayesian SGPR (VBSGPR) models jointly treat both the distributions of the inducing variables and hyperparameters as variational parameters, which enables the decomposability of the variational lower bound that in turn can be exploited for stochastic optimization. Such a stochastic optimization involves iteratively following the stochastic gradient of the variational lower bound to improve its estimates of the optimal variational distributions of the inducing variables and hyperparameters (and hence the predictive distribution) of our VBSGPR models and is guaranteed to achieve asymptotic convergence to them. We show that the stochastic gradient is an unbiased estimator of the exact gradient and can be computed in constant time per iteration, hence achieving scalability to big data. We empirically evaluate the performance of our proposed framework on two real-world, massive datasets.
Tasks	Stochastic Optimization
Published	2017-11-01
URL	http://arxiv.org/abs/1711.00221v3
PDF	http://arxiv.org/pdf/1711.00221v3.pdf
PWC	https://paperswithcode.com/paper/stochastic-variational-inference-for-fully
Repo
Framework

Network-size independent covering number bounds for deep networks


Title	Network-size independent covering number bounds for deep networks
Authors	Mayank Kabra, Kristin Branson
Abstract	We give a covering number bound for deep learning networks that is independent of the size of the network. The key for the simple analysis is that for linear classifiers, rotating the data doesn’t affect the covering number. Thus, we can ignore the rotation part of each layer’s linear transformation, and get the covering number bound by concentrating on the scaling part.
Tasks
Published	2017-11-02
URL	http://arxiv.org/abs/1711.00753v2
PDF	http://arxiv.org/pdf/1711.00753v2.pdf
PWC	https://paperswithcode.com/paper/network-size-independent-covering-number
Repo
Framework

Deep Network Flow for Multi-Object Tracking


Title	Deep Network Flow for Multi-Object Tracking
Authors	Samuel Schulter, Paul Vernaza, Wongun Choi, Manmohan Chandraker
Abstract	Data association problems are an important component of many computer vision applications, with multi-object tracking being one of the most prominent examples. A typical approach to data association involves finding a graph matching or network flow that minimizes a sum of pairwise association costs, which are often either hand-crafted or learned as linear functions of fixed features. In this work, we demonstrate that it is possible to learn features for network-flow-based data association via backpropagation, by expressing the optimum of a smoothed network flow problem as a differentiable function of the pairwise association costs. We apply this approach to multi-object tracking with a network flow formulation. Our experiments demonstrate that we are able to successfully learn all cost functions for the association problem in an end-to-end fashion, which outperform hand-crafted costs in all settings. The integration and combination of various sources of inputs becomes easy and the cost functions can be learned entirely from data, alleviating tedious hand-designing of costs.
Tasks	Graph Matching, Multi-Object Tracking, Object Tracking
Published	2017-06-26
URL	http://arxiv.org/abs/1706.08482v1
PDF	http://arxiv.org/pdf/1706.08482v1.pdf
PWC	https://paperswithcode.com/paper/deep-network-flow-for-multi-object-tracking
Repo
Framework

Finite Sample Analysis of Two-Timescale Stochastic Approximation with Applications to Reinforcement Learning


Title	Finite Sample Analysis of Two-Timescale Stochastic Approximation with Applications to Reinforcement Learning
Authors	Gal Dalal, Balazs Szorenyi, Gugan Thoppe, Shie Mannor
Abstract	Two-timescale Stochastic Approximation (SA) algorithms are widely used in Reinforcement Learning (RL). Their iterates have two parts that are updated using distinct stepsizes. In this work, we develop a novel recipe for their finite sample analysis. Using this, we provide a concentration bound, which is the first such result for a two-timescale SA. The type of bound we obtain is known as `lock-in probability’. We also introduce a new projection scheme, in which the time between successive projections increases exponentially. This scheme allows one to elegantly transform a lock-in probability into a convergence rate result for projected two-timescale SA. From this latter result, we then extract key insights on stepsize selection. As an application, we finally obtain convergence rates for the projected two-timescale RL algorithms GTD(0), GTD2, and TDC. \|
Tasks
Published	2017-03-15
URL	http://arxiv.org/abs/1703.05376v5
PDF	http://arxiv.org/pdf/1703.05376v5.pdf
PWC	https://paperswithcode.com/paper/finite-sample-analysis-of-two-timescale
Repo
Framework

Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues


Title	Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues
Authors	Noga Alon, Moshe Babaioff, Yannai A. Gonczarowski, Yishay Mansour, Shay Moran, Amir Yehudayoff
Abstract	In this work we derive a variant of the classic Glivenko-Cantelli Theorem, which asserts uniform convergence of the empirical Cumulative Distribution Function (CDF) to the CDF of the underlying distribution. Our variant allows for tighter convergence bounds for extreme values of the CDF. We apply our bound in the context of revenue learning, which is a well-studied problem in economics and algorithmic game theory. We derive sample-complexity bounds on the uniform convergence rate of the empirical revenues to the true revenues, assuming a bound on the $k$th moment of the valuations, for any (possibly fractional) $k>1$. For uniform convergence in the limit, we give a complete characterization and a zero-one law: if the first moment of the valuations is finite, then uniform convergence almost surely occurs; conversely, if the first moment is infinite, then uniform convergence almost never occurs.
Tasks
Published	2017-05-23
URL	http://arxiv.org/abs/1705.08430v3
PDF	http://arxiv.org/pdf/1705.08430v3.pdf
PWC	https://paperswithcode.com/paper/submultiplicative-glivenko-cantelli-and
Repo
Framework

Efficient Twitter Sentiment Classification using Subjective Distant Supervision


Title	Efficient Twitter Sentiment Classification using Subjective Distant Supervision
Authors	Tapan Sahni, Chinmay Chandak, Naveen Reddy Chedeti, Manish Singh
Abstract	As microblogging services like Twitter are becoming more and more influential in today’s globalised world, its facets like sentiment analysis are being extensively studied. We are no longer constrained by our own opinion. Others opinions and sentiments play a huge role in shaping our perspective. In this paper, we build on previous works on Twitter sentiment analysis using Distant Supervision. The existing approach requires huge computation resource for analysing large number of tweets. In this paper, we propose techniques to speed up the computation process for sentiment analysis. We use tweet subjectivity to select the right training samples. We also introduce the concept of EFWS (Effective Word Score) of a tweet that is derived from polarity scores of frequently used words, which is an additional heuristic that can be used to speed up the sentiment classification with standard machine learning algorithms. We performed our experiments using 1.6 million tweets. Experimental evaluations show that our proposed technique is more efficient and has higher accuracy compared to previously proposed methods. We achieve overall accuracies of around 80% (EFWS heuristic gives an accuracy around 85%) on a training dataset of 100K tweets, which is half the size of the dataset used for the baseline model. The accuracy of our proposed model is 2-3% higher than the baseline model, and the model effectively trains at twice the speed of the baseline model.
Tasks	Sentiment Analysis, Twitter Sentiment Analysis
Published	2017-01-11
URL	http://arxiv.org/abs/1701.03051v1
PDF	http://arxiv.org/pdf/1701.03051v1.pdf
PWC	https://paperswithcode.com/paper/efficient-twitter-sentiment-classification
Repo
Framework

Two-sample Hypothesis Testing for Inhomogeneous Random Graphs


Title	Two-sample Hypothesis Testing for Inhomogeneous Random Graphs
Authors	Debarghya Ghoshdastidar, Maurilio Gutzeit, Alexandra Carpentier, Ulrike von Luxburg
Abstract	The study of networks leads to a wide range of high dimensional inference problems. In many practical applications, one needs to draw inference from one or few large sparse networks. The present paper studies hypothesis testing of graphs in this high-dimensional regime, where the goal is to test between two populations of inhomogeneous random graphs defined on the same set of $n$ vertices. The size of each population $m$ is much smaller than $n$, and can even be a constant as small as 1. The critical question in this context is whether the problem is solvable for small $m$. We answer this question from a minimax testing perspective. Let $P,Q$ be the population adjacencies of two sparse inhomogeneous random graph models, and $d$ be a suitably defined distance function. Given a population of $m$ graphs from each model, we derive minimax separation rates for the problem of testing $P=Q$ against $d(P,Q)>\rho$. We observe that if $m$ is small, then the minimax separation is too large for some popular choices of $d$, including total variation distance between corresponding distributions. This implies that some models that are widely separated in $d$ cannot be distinguished for small $m$, and hence, the testing problem is generally not solvable in these cases. We also show that if $m>1$, then the minimax separation is relatively small if $d$ is the Frobenius norm or operator norm distance between $P$ and $Q$. For $m=1$, only the latter distance provides small minimax separation. Thus, for these distances, the problem is solvable for small $m$. We also present near-optimal two-sample tests in both cases, where tests are adaptive with respect to sparsity level of the graphs.
Tasks
Published	2017-07-04
URL	https://arxiv.org/abs/1707.00833v4
PDF	https://arxiv.org/pdf/1707.00833v4.pdf
PWC	https://paperswithcode.com/paper/two-sample-hypothesis-testing-for
Repo
Framework

Learning a Dilated Residual Network for SAR Image Despeckling


Title	Learning a Dilated Residual Network for SAR Image Despeckling
Authors	Qiang Zhang, Qiangqiang Yuan, Jie Li, Zhen Yang, Xiaoshuang Ma
Abstract	In this paper, to break the limit of the traditional linear models for synthetic aperture radar (SAR) image despeckling, we propose a novel deep learning approach by learning a non-linear end-to-end mapping between the noisy and clean SAR images with a dilated residual network (SAR-DRN). SAR-DRN is based on dilated convolutions, which can both enlarge the receptive field and maintain the filter size and layer depth with a lightweight structure. In addition, skip connections and residual learning strategy are added to the despeckling model to maintain the image details and reduce the vanishing gradient problem. Compared with the traditional despeckling methods, the proposed method shows superior performance over the state-of-the-art methods on both quantitative and visual assessments, especially for strong speckle noise.
Tasks	Sar Image Despeckling
Published	2017-09-09
URL	http://arxiv.org/abs/1709.02898v3
PDF	http://arxiv.org/pdf/1709.02898v3.pdf
PWC	https://paperswithcode.com/paper/learning-a-dilated-residual-network-for-sar
Repo
Framework

Extremely Low Bit Neural Network: Squeeze the Last Bit Out with ADMM


Title	Extremely Low Bit Neural Network: Squeeze the Last Bit Out with ADMM
Authors	Cong Leng, Hao Li, Shenghuo Zhu, Rong Jin
Abstract	Although deep learning models are highly effective for various learning tasks, their high computational costs prohibit the deployment to scenarios where either memory or computational resources are limited. In this paper, we focus on compressing and accelerating deep models with network weights represented by very small numbers of bits, referred to as extremely low bit neural network. We model this problem as a discretely constrained optimization problem. Borrowing the idea from Alternating Direction Method of Multipliers (ADMM), we decouple the continuous parameters from the discrete constraints of network, and cast the original hard problem into several subproblems. We propose to solve these subproblems using extragradient and iterative quantization algorithms that lead to considerably faster convergency compared to conventional optimization methods. Extensive experiments on image recognition and object detection verify that the proposed algorithm is more effective than state-of-the-art approaches when coming to extremely low bit neural network.
Tasks	Object Detection, Quantization
Published	2017-07-24
URL	http://arxiv.org/abs/1707.09870v2
PDF	http://arxiv.org/pdf/1707.09870v2.pdf
PWC	https://paperswithcode.com/paper/extremely-low-bit-neural-network-squeeze-the
Repo
Framework