October 20, 2019

3208 words 16 mins read

Paper Group AWR 305

A Two-point Method for PTZ Camera Calibration in Sports. Invariant Information Clustering for Unsupervised Image Classification and Segmentation. Imputation and low-rank estimation with Missing Not At Random data. Coupled Graphs and Tensor Factorization for Recommender Systems and Community Detection. Model Agnostic Time Series Analysis via Matrix …

A Two-point Method for PTZ Camera Calibration in Sports


Title	A Two-point Method for PTZ Camera Calibration in Sports
Authors	Jianhui Chen, Fangrui Zhu, James J. Little
Abstract	Calibrating narrow field of view soccer cameras is challenging because there are very few field markings in the image. Unlike previous solutions, we propose a two-point method, which requires only two point correspondences given the prior knowledge of base location and orientation of a pan-tilt-zoom (PTZ) camera. We deploy this new calibration method to annotate pan-tilt-zoom data from soccer videos. The collected data are used as references for new images. We also propose a fast random forest method to predict pan-tilt angles without image-to-image feature matching, leading to an efficient calibration method for new images. We demonstrate our system on synthetic data and two real soccer datasets. Our two-point approach achieves superior performance over the state-of-the-art method.
Tasks	Calibration
Published	2018-01-26
URL	http://arxiv.org/abs/1801.09005v1
PDF	http://arxiv.org/pdf/1801.09005v1.pdf
PWC	https://paperswithcode.com/paper/a-two-point-method-for-ptz-camera-calibration
Repo	https://github.com/lood339/two_point_calib
Framework	none

Invariant Information Clustering for Unsupervised Image Classification and Segmentation


Title	Invariant Information Clustering for Unsupervised Image Classification and Segmentation
Authors	Xu Ji, João F. Henriques, Andrea Vedaldi
Abstract	We present a novel clustering objective that learns a neural network classifier from scratch, given only unlabelled data samples. The model discovers clusters that accurately match semantic classes, achieving state-of-the-art results in eight unsupervised clustering benchmarks spanning image classification and segmentation. These include STL10, an unsupervised variant of ImageNet, and CIFAR10, where we significantly beat the accuracy of our closest competitors by 6.6 and 9.5 absolute percentage points respectively. The method is not specialised to computer vision and operates on any paired dataset samples; in our experiments we use random transforms to obtain a pair from each image. The trained network directly outputs semantic labels, rather than high dimensional representations that need external processing to be usable for semantic clustering. The objective is simply to maximise mutual information between the class assignments of each pair. It is easy to implement and rigorously grounded in information theory, meaning we effortlessly avoid degenerate solutions that other clustering methods are susceptible to. In addition to the fully unsupervised mode, we also test two semi-supervised settings. The first achieves 88.8% accuracy on STL10 classification, setting a new global state-of-the-art over all existing methods (whether supervised, semi-supervised or unsupervised). The second shows robustness to 90% reductions in label coverage, of relevance to applications that wish to make use of small amounts of labels. github.com/xu-ji/IIC
Tasks	Image Classification, Semantic Segmentation, Unsupervised Image Classification, Unsupervised MNIST
Published	2018-07-17
URL	https://arxiv.org/abs/1807.06653v4
PDF	https://arxiv.org/pdf/1807.06653v4.pdf
PWC	https://paperswithcode.com/paper/invariant-information-distillation-for
Repo	https://github.com/nathanin/IIC
Framework	pytorch

Imputation and low-rank estimation with Missing Not At Random data


Title	Imputation and low-rank estimation with Missing Not At Random data
Authors	Aude Sportisse, Claire Boyer, Julie Josse
Abstract	Missing values challenge data analysis because many supervised and unsupervised learning methods cannot be applied directly to incomplete data. Matrix completion based on low-rank assumptions are very powerful solution for dealing with missing values. However, existing methods do not consider the case of informative missing values which are widely encountered in practice. This paper proposes matrix completion methods to recover Missing Not At Random (MNAR) data. Our first contribution is to suggest a model-based estimation strategy by modelling the missing mechanism distribution. An EM algorithm is then implemented, involving a Fast Iterative Soft-Thresholding Algorithm (FISTA). Our second contribution is to suggest a computationally efficient surrogate estimation by implicitly taking into account the joint distribution of the data and the missing mechanism: the data matrix is concatenated with the mask coding for the missing values; a low-rank structure for exponential family is assumed on this new matrix, in order to encode links between variables and missing mechanisms. The methodology that has the great advantage of handling different missing value mechanisms is robust to model specification errors.The performances of our methods are assessed on the real data collected from a trauma registry (TraumaBase ) containing clinical information about over twenty thousand severely traumatized patients in France. The aim is then to predict if the doctors should administrate tranexomic acid to patients with traumatic brain injury, that would limit excessive bleeding.
Tasks	Imputation, Matrix Completion
Published	2018-12-29
URL	https://arxiv.org/abs/1812.11409v3
PDF	https://arxiv.org/pdf/1812.11409v3.pdf
PWC	https://paperswithcode.com/paper/imputation-and-low-rank-estimation-with
Repo	https://github.com/AudeSportisse/stat
Framework	none

Coupled Graphs and Tensor Factorization for Recommender Systems and Community Detection


Title	Coupled Graphs and Tensor Factorization for Recommender Systems and Community Detection
Authors	Vassilis N. Ioannidis, Ahmed S. Zamzam, Georgios B. Giannakis, Nicholas D. Sidiropoulos
Abstract	Joint analysis of data from multiple information repositories facilitates uncovering the underlying structure in heterogeneous datasets. Single and coupled matrix-tensor factorization (CMTF) has been widely used in this context for imputation-based recommendation from ratings, social network, and other user-item data. When this side information is in the form of item-item correlation matrices or graphs, existing CMTF algorithms may fall short. Alleviating current limitations, we introduce a novel model coined coupled graph-tensor factorization (CGTF) that judiciously accounts for graph-related side information. The CGTF model has the potential to overcome practical challenges, such as missing slabs from the tensor and/or missing rows/columns from the correlation matrices. A novel alternating direction method of multipliers (ADMM) is also developed that recovers the nonnegative factors of CGTF. Our algorithm enjoys closed-form updates that result in reduced computational complexity and allow for convergence claims. A novel direction is further explored by employing the interpretable factors to detect graph communities having the tensor as side information. The resulting community detection approach is successful even when some links in the graphs are missing. Results with real data sets corroborate the merits of the proposed methods relative to state-of-the-art competing factorization techniques in providing recommendations and detecting communities.
Tasks	Community Detection, Imputation, Recommendation Systems
Published	2018-09-22
URL	https://arxiv.org/abs/1809.08353v2
PDF	https://arxiv.org/pdf/1809.08353v2.pdf
PWC	https://paperswithcode.com/paper/coupled-graphs-and-tensor-factorization-for
Repo	https://github.com/bioannidis/Coupled_tensors_graphs
Framework	none

Model Agnostic Time Series Analysis via Matrix Estimation


Title	Model Agnostic Time Series Analysis via Matrix Estimation
Authors	Anish Agarwal, Muhammad Jehangir Amjad, Devavrat Shah, Dennis Shen
Abstract	We propose an algorithm to impute and forecast a time series by transforming the observed time series into a matrix, utilizing matrix estimation to recover missing values and de-noise observed entries, and performing linear regression to make predictions. At the core of our analysis is a representation result, which states that for a large model class, the transformed time series matrix is (approximately) low-rank. In effect, this generalizes the widely used Singular Spectrum Analysis (SSA) in time series literature, and allows us to establish a rigorous link between time series analysis and matrix estimation. The key to establishing this link is constructing a Page matrix with non-overlapping entries rather than a Hankel matrix as is commonly done in the literature (e.g., SSA). This particular matrix structure allows us to provide finite sample analysis for imputation and prediction, and prove the asymptotic consistency of our method. Another salient feature of our algorithm is that it is model agnostic with respect to both the underlying time dynamics and the noise distribution in the observations. The noise agnostic property of our approach allows us to recover the latent states when only given access to noisy and partial observations a la a Hidden Markov Model; e.g., recovering the time-varying parameter of a Poisson process without knowing that the underlying process is Poisson. Furthermore, since our forecasting algorithm requires regression with noisy features, our approach suggests a matrix estimation based method - coupled with a novel, non-standard matrix estimation error metric - to solve the error-in-variable regression problem, which could be of interest in its own right. Through synthetic and real-world datasets, we demonstrate that our algorithm outperforms standard software packages (including R libraries) in the presence of missing data as well as high levels of noise.
Tasks	Imputation, Time Series, Time Series Analysis
Published	2018-02-25
URL	http://arxiv.org/abs/1802.09064v6
PDF	http://arxiv.org/pdf/1802.09064v6.pdf
PWC	https://paperswithcode.com/paper/model-agnostic-time-series-analysis-via
Repo	https://github.com/jehangiramjad/tslib
Framework	none

Target Driven Instance Detection


Title	Target Driven Instance Detection
Authors	Phil Ammirato, Cheng-Yang Fu, Mykhailo Shvets, Jana Kosecka, Alexander C. Berg
Abstract	While state-of-the-art general object detectors are getting better and better, there are not many systems specifically designed to take advantage of the instance detection problem. For many applications, such as household robotics, a system may need to recognize a few very specific instances at a time. Speed can be critical in these applications, as can the need to recognize previously unseen instances. We introduce a Target Driven Instance Detector(TDID), which modifies existing general object detectors for the instance recognition setting. TDID not only improves performance on instances seen during training, with a fast runtime, but is also able to generalize to detect novel instances.
Tasks
Published	2018-03-13
URL	https://arxiv.org/abs/1803.04610v6
PDF	https://arxiv.org/pdf/1803.04610v6.pdf
PWC	https://paperswithcode.com/paper/target-driven-instance-detection
Repo	https://github.com/ammirato/target_driven_instance_detection
Framework	pytorch

Retinal vessel segmentation based on Fully Convolutional Neural Networks


Title	Retinal vessel segmentation based on Fully Convolutional Neural Networks
Authors	Américo Oliveira, Sérgio Pereira, Carlos A. Silva
Abstract	The retinal vascular condition is a reliable biomarker of several ophthalmologic and cardiovascular diseases, so automatic vessel segmentation may be crucial to diagnose and monitor them. In this paper, we propose a novel method that combines the multiscale analysis provided by the Stationary Wavelet Transform with a multiscale Fully Convolutional Neural Network to cope with the varying width and direction of the vessel structure in the retina. Our proposal uses rotation operations as the basis of a joint strategy for both data augmentation and prediction, which allows us to explore the information learned during training to refine the segmentation. The method was evaluated on three publicly available databases, achieving an average accuracy of 0.9576, 0.9694, and 0.9653, and average area under the ROC curve of 0.9821, 0.9905, and 0.9855 on the DRIVE, STARE, and CHASE_DB1 databases, respectively. It also appears to be robust to the training set and to the inter-rater variability, which shows its potential for real-world applications.
Tasks	Data Augmentation, Retinal Vessel Segmentation
Published	2018-12-18
URL	http://arxiv.org/abs/1812.07110v2
PDF	http://arxiv.org/pdf/1812.07110v2.pdf
PWC	https://paperswithcode.com/paper/retinal-vessel-segmentation-based-on-fully
Repo	https://github.com/americofmoliveira/VesselSegmentation_ESWA
Framework	none

Generative networks as inverse problems with Scattering transforms


Title	Generative networks as inverse problems with Scattering transforms
Authors	Tomás Angles, Stéphane Mallat
Abstract	Generative Adversarial Nets (GANs) and Variational Auto-Encoders (VAEs) provide impressive image generations from Gaussian white noise, but the underlying mathematics are not well understood. We compute deep convolutional network generators by inverting a fixed embedding operator. Therefore, they do not require to be optimized with a discriminator or an encoder. The embedding is Lipschitz continuous to deformations so that generators transform linear interpolations between input white noise vectors into deformations between output images. This embedding is computed with a wavelet Scattering transform. Numerical experiments demonstrate that the resulting Scattering generators have similar properties as GANs or VAEs, without learning a discriminative network or an encoder.
Tasks
Published	2018-05-17
URL	http://arxiv.org/abs/1805.06621v1
PDF	http://arxiv.org/pdf/1805.06621v1.pdf
PWC	https://paperswithcode.com/paper/generative-networks-as-inverse-problems-with
Repo	https://github.com/tomas-angles/generative-scattering-networks
Framework	pytorch

Modeling Empathy and Distress in Reaction to News Stories


Title	Modeling Empathy and Distress in Reaction to News Stories
Authors	Sven Buechel, Anneke Buffone, Barry Slaff, Lyle Ungar, João Sedoc
Abstract	Computational detection and understanding of empathy is an important factor in advancing human-computer interaction. Yet to date, text-based empathy prediction has the following major limitations: It underestimates the psychological complexity of the phenomenon, adheres to a weak notion of ground truth where empathic states are ascribed by third parties, and lacks a shared corpus. In contrast, this contribution presents the first publicly available gold standard for empathy prediction. It is constructed using a novel annotation methodology which reliably captures empathy assessments by the writer of a statement using multi-item scales. This is also the first computational work distinguishing between multiple forms of empathy, empathic concern, and personal distress, as recognized throughout psychology. Finally, we present experimental results for three different predictive models, of which a CNN performs the best.
Tasks
Published	2018-08-30
URL	http://arxiv.org/abs/1808.10399v1
PDF	http://arxiv.org/pdf/1808.10399v1.pdf
PWC	https://paperswithcode.com/paper/modeling-empathy-and-distress-in-reaction-to
Repo	https://github.com/wwbp/empathic_reactions
Framework	none

Unsupervised Learning of Goal Spaces for Intrinsically Motivated Goal Exploration


Title	Unsupervised Learning of Goal Spaces for Intrinsically Motivated Goal Exploration
Authors	Alexandre Péré, Sébastien Forestier, Olivier Sigaud, Pierre-Yves Oudeyer
Abstract	Intrinsically motivated goal exploration algorithms enable machines to discover repertoires of policies that produce a diversity of effects in complex environments. These exploration algorithms have been shown to allow real world robots to acquire skills such as tool use in high-dimensional continuous state and action spaces. However, they have so far assumed that self-generated goals are sampled in a specifically engineered feature space, limiting their autonomy. In this work, we propose to use deep representation learning algorithms to learn an adequate goal space. This is a developmental 2-stage approach: first, in a perceptual learning stage, deep learning algorithms use passive raw sensor observations of world changes to learn a corresponding latent space; then goal exploration happens in a second stage by sampling goals in this latent space. We present experiments where a simulated robot arm interacts with an object, and we show that exploration algorithms using such learned representations can match the performance obtained using engineered representations.
Tasks	Representation Learning
Published	2018-03-02
URL	http://arxiv.org/abs/1803.00781v3
PDF	http://arxiv.org/pdf/1803.00781v3.pdf
PWC	https://paperswithcode.com/paper/unsupervised-learning-of-goal-spaces-for
Repo	https://github.com/flowersteam/Unsupervised_Goal_Space_Learning
Framework	none

Efficient Differentiable Programming in a Functional Array-Processing Language


Title	Efficient Differentiable Programming in a Functional Array-Processing Language
Authors	Amir Shaikhha, Andrew Fitzgibbon, Dimitrios Vytiniotis, Simon Peyton Jones, Christoph Koch
Abstract	We present a system for the automatic differentiation of a higher-order functional array-processing language. The core functional language underlying this system simultaneously supports both source-to-source automatic differentiation and global optimizations such as loop transformations. Thanks to this feature, we demonstrate how for some real-world machine learning and computer vision benchmarks, the system outperforms the state-of-the-art automatic differentiation tools.
Tasks
Published	2018-06-06
URL	http://arxiv.org/abs/1806.02136v1
PDF	http://arxiv.org/pdf/1806.02136v1.pdf
PWC	https://paperswithcode.com/paper/efficient-differentiable-programming-in-a
Repo	https://github.com/sunze1/Differential-Programming
Framework	tf

Constant-Delay Enumeration for Nondeterministic Document Spanners


Title	Constant-Delay Enumeration for Nondeterministic Document Spanners
Authors	Antoine Amarilli, Pierre Bourhis, Stefan Mengel, Matthias Niewerth
Abstract	We consider the information extraction framework known as document spanners, and study the problem of efficiently computing the results of the extraction from an input document, where the extraction task is described as a sequential variable-set automaton (VA). We pose this problem in the setting of enumeration algorithms, where we can first run a preprocessing phase and must then produce the results with a small delay between any two consecutive results. Our goal is to have an algorithm which is tractable in combined complexity, i.e., in the sizes of the input document and the VA; while ensuring the best possible data complexity bounds in the input document size, i.e., constant delay in the document size. Several recent works at PODS’18 proposed such algorithms but with linear delay in the document size or with an exponential dependency in size of the (generally nondeterministic) input VA. In particular, Florenzano et al. suggest that our desired runtime guarantees cannot be met for general sequential VAs. We refute this and show that, given a nondeterministic sequential VA and an input document, we can enumerate the mappings of the VA on the document with the following bounds: the preprocessing is linear in the document size and polynomial in the size of the VA, and the delay is independent of the document and polynomial in the size of the VA. The resulting algorithm thus achieves tractability in combined complexity and the best possible data complexity bounds. Moreover, it is rather easy to describe, in particular for the restricted case of so-called extended VAs.
Tasks
Published	2018-07-24
URL	http://arxiv.org/abs/1807.09320v3
PDF	http://arxiv.org/pdf/1807.09320v3.pdf
PWC	https://paperswithcode.com/paper/constant-delay-enumeration-for
Repo	https://github.com/PoDMR/enum-spanner-rs
Framework	none

Differentiable Satisfiability and Differentiable Answer Set Programming for Sampling-Based Multi-Model Optimization


Title	Differentiable Satisfiability and Differentiable Answer Set Programming for Sampling-Based Multi-Model Optimization
Authors	Matthias Nickles
Abstract	We propose Differentiable Satisfiability and Differentiable Answer Set Programming (Differentiable SAT/ASP) for multi-model optimization. Models (answer sets or satisfying truth assignments) are sampled using a novel SAT/ASP solving approach which uses a gradient descent-based branching mechanism. Sampling proceeds until the value of a user-defined multi-model cost function reaches a given threshold. As major use cases for our approach we propose distribution-aware model sampling and expressive yet scalable probabilistic logic programming. As our main algorithmic approach to Differentiable SAT/ASP, we introduce an enhancement of the state-of-the-art CDNL/CDCL algorithm for SAT/ASP solving. Additionally, we present alternative algorithms which use an unmodified ASP solver (Clingo/clasp) and map the optimization task to conventional answer set optimization or use so-called propagators. We also report on the open source software DelSAT, a recent prototype implementation of our main algorithm, and on initial experimental results which indicate that DelSATs performance is, when applied to the use case of probabilistic logic inference, on par with Markov Logic Network (MLN) inference performance, despite having advantageous properties compared to MLNs, such as the ability to express inductive definitions and to work with probabilities as weights directly in all cases. Our experiments also indicate that our main algorithm is strongly superior in terms of performance compared to the presented alternative approaches which reduce a common instance of the general problem to regular SAT/ASP.
Tasks
Published	2018-12-31
URL	http://arxiv.org/abs/1812.11948v1
PDF	http://arxiv.org/pdf/1812.11948v1.pdf
PWC	https://paperswithcode.com/paper/differentiable-satisfiability-and
Repo	https://github.com/MatthiasNickles/DelSAT
Framework	none

A Surprising Linear Relationship Predicts Test Performance in Deep Networks


Title	A Surprising Linear Relationship Predicts Test Performance in Deep Networks
Authors	Qianli Liao, Brando Miranda, Andrzej Banburski, Jack Hidary, Tomaso Poggio
Abstract	Given two networks with the same training loss on a dataset, when would they have drastically different test losses and errors? Better understanding of this question of generalization may improve practical applications of deep networks. In this paper we show that with cross-entropy loss it is surprisingly simple to induce significantly different generalization performances for two networks that have the same architecture, the same meta parameters and the same training error: one can either pretrain the networks with different levels of “corrupted” data or simply initialize the networks with weights of different Gaussian standard deviations. A corollary of recent theoretical results on overfitting shows that these effects are due to an intrinsic problem of measuring test performance with a cross-entropy/exponential-type loss, which can be decomposed into two components both minimized by SGD – one of which is not related to expected classification performance. However, if we factor out this component of the loss, a linear relationship emerges between training and test losses. Under this transformation, classical generalization bounds are surprisingly tight: the empirical/training loss is very close to the expected/test loss. Furthermore, the empirical relation between classification error and normalized cross-entropy loss seem to be approximately monotonic
Tasks
Published	2018-07-25
URL	http://arxiv.org/abs/1807.09659v1
PDF	http://arxiv.org/pdf/1807.09659v1.pdf
PWC	https://paperswithcode.com/paper/a-surprising-linear-relationship-predicts
Repo	https://github.com/liaoq/Generalization-Puzzles-in-Deep-Networks
Framework	pytorch

CatBoost: gradient boosting with categorical features support


Title	CatBoost: gradient boosting with categorical features support
Authors	Anna Veronika Dorogush, Vasily Ershov, Andrey Gulin
Abstract	In this paper we present CatBoost, a new open-sourced gradient boosting library that successfully handles categorical features and outperforms existing publicly available implementations of gradient boosting in terms of quality on a set of popular publicly available datasets. The library has a GPU implementation of learning algorithm and a CPU implementation of scoring algorithm, which are significantly faster than other gradient boosting libraries on ensembles of similar sizes.
Tasks	Dimensionality Reduction
Published	2018-10-24
URL	http://arxiv.org/abs/1810.11363v1
PDF	http://arxiv.org/pdf/1810.11363v1.pdf
PWC	https://paperswithcode.com/paper/catboost-gradient-boosting-with-categorical
Repo	https://github.com/catboost/catboost
Framework	none