July 29, 2019

3150 words 15 mins read

Paper Group ANR 20

Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution. Towards Robust Detection of Adversarial Examples. GANosaic: Mosaic Creation with Generative Texture Manifolds. Automatic Generation of Typographic Font from a Small Font Subset. Sympathy B …


Title	Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
Authors	Cong Ma, Kaizheng Wang, Yuejie Chi, Yuxin Chen
Abstract	Recent years have seen a flurry of activities in designing provably efficient nonconvex procedures for solving statistical estimation problems. Due to the highly nonconvex nature of the empirical loss, state-of-the-art procedures often require proper regularization (e.g. trimming, regularized cost, projection) in order to guarantee fast convergence. For vanilla procedures such as gradient descent, however, prior theory either recommends highly conservative learning rates to avoid overshooting, or completely lacks performance guarantees. This paper uncovers a striking phenomenon in nonconvex optimization: even in the absence of explicit regularization, gradient descent enforces proper regularization implicitly under various statistical models. In fact, gradient descent follows a trajectory staying within a basin that enjoys nice geometry, consisting of points incoherent with the sampling mechanism. This “implicit regularization” feature allows gradient descent to proceed in a far more aggressive fashion without overshooting, which in turn results in substantial computational savings. Focusing on three fundamental statistical estimation problems, i.e. phase retrieval, low-rank matrix completion, and blind deconvolution, we establish that gradient descent achieves near-optimal statistical and computational guarantees without explicit regularization. In particular, by marrying statistical modeling with generic optimization theory, we develop a general recipe for analyzing the trajectories of iterative algorithms via a leave-one-out perturbation argument. As a byproduct, for noisy matrix completion, we demonstrate that gradient descent achieves near-optimal error control — measured entrywise and by the spectral norm — which might be of independent interest.
Tasks	Low-Rank Matrix Completion, Matrix Completion
Published	2017-11-28
URL	https://arxiv.org/abs/1711.10467v3
PDF	https://arxiv.org/pdf/1711.10467v3.pdf
PWC	https://paperswithcode.com/paper/implicit-regularization-in-nonconvex
Repo
Framework

Towards Robust Detection of Adversarial Examples


Title	Towards Robust Detection of Adversarial Examples
Authors	Tianyu Pang, Chao Du, Yinpeng Dong, Jun Zhu
Abstract	Although the recent progress is substantial, deep learning methods can be vulnerable to the maliciously generated adversarial examples. In this paper, we present a novel training procedure and a thresholding test strategy, towards robust detection of adversarial examples. In training, we propose to minimize the reverse cross-entropy (RCE), which encourages a deep network to learn latent representations that better distinguish adversarial examples from normal ones. In testing, we propose to use a thresholding strategy as the detector to filter out adversarial examples for reliable predictions. Our method is simple to implement using standard algorithms, with little extra training cost compared to the common cross-entropy minimization. We apply our method to defend various attacking methods on the widely used MNIST and CIFAR-10 datasets, and achieve significant improvements on robust predictions under all the threat models in the adversarial setting.
Tasks
Published	2017-06-02
URL	http://arxiv.org/abs/1706.00633v4
PDF	http://arxiv.org/pdf/1706.00633v4.pdf
PWC	https://paperswithcode.com/paper/towards-robust-detection-of-adversarial
Repo
Framework

GANosaic: Mosaic Creation with Generative Texture Manifolds


Title	GANosaic: Mosaic Creation with Generative Texture Manifolds
Authors	Nikolay Jetchev, Urs Bergmann, Calvin Seward
Abstract	This paper presents a novel framework for generating texture mosaics with convolutional neural networks. Our method is called GANosaic and performs optimization in the latent noise space of a generative texture model, which allows the transformation of a content image into a mosaic exhibiting the visual properties of the underlying texture manifold. To represent that manifold, we use a state-of-the-art generative adversarial method for texture synthesis, which can learn expressive texture representations from data and produce mosaic images with very high resolution. This fully convolutional model generates smooth (without any visible borders) mosaic images which morph and blend different textures locally. In addition, we develop a new type of differentiable statistical regularization appropriate for optimization over the prior noise space of the PSGAN model.
Tasks	Texture Synthesis
Published	2017-12-01
URL	http://arxiv.org/abs/1712.00269v1
PDF	http://arxiv.org/pdf/1712.00269v1.pdf
PWC	https://paperswithcode.com/paper/ganosaic-mosaic-creation-with-generative
Repo
Framework

Automatic Generation of Typographic Font from a Small Font Subset


Title	Automatic Generation of Typographic Font from a Small Font Subset
Authors	Tomo Miyazaki, Tatsunori Tsuchiya, Yoshihiro Sugaya, Shinichiro Omachi, Masakazu Iwamura, Seiichi Uchida, Koichi Kise
Abstract	This paper addresses the automatic generation of a typographic font from a subset of characters. Specifically, we use a subset of a typographic font to extrapolate additional characters. Consequently, we obtain a complete font containing a number of characters sufficient for daily use. The automated generation of Japanese fonts is in high demand because a Japanese font requires over 1,000 characters. Unfortunately, professional typographers create most fonts, resulting in significant financial and time investments for font generation. The proposed method can be a great aid for font creation because designers do not need to create the majority of the characters for a new font. The proposed method uses strokes from given samples for font generation. The strokes, from which we construct characters, are extracted by exploiting a character skeleton dataset. This study makes three main contributions: a novel method of extracting strokes from characters, which is applicable to both standard fonts and their variations; a fully automated approach for constructing characters; and a selection method for sample characters. We demonstrate our proposed method by generating 2,965 characters in 47 fonts. Objective and subjective evaluations verify that the generated characters are similar to handmade characters.
Tasks
Published	2017-01-20
URL	http://arxiv.org/abs/1701.05703v1
PDF	http://arxiv.org/pdf/1701.05703v1.pdf
PWC	https://paperswithcode.com/paper/automatic-generation-of-typographic-font-from
Repo
Framework

Sympathy Begins with a Smile, Intelligence Begins with a Word: Use of Multimodal Features in Spoken Human-Robot Interaction


Title	Sympathy Begins with a Smile, Intelligence Begins with a Word: Use of Multimodal Features in Spoken Human-Robot Interaction
Authors	Jekaterina Novikova, Christian Dondrup, Ioannis Papaioannou, Oliver Lemon
Abstract	Recognition of social signals, from human facial expressions or prosody of speech, is a popular research topic in human-robot interaction studies. There is also a long line of research in the spoken dialogue community that investigates user satisfaction in relation to dialogue characteristics. However, very little research relates a combination of multimodal social signals and language features detected during spoken face-to-face human-robot interaction to the resulting user perception of a robot. In this paper we show how different emotional facial expressions of human users, in combination with prosodic characteristics of human speech and features of human-robot dialogue, correlate with users’ impressions of the robot after a conversation. We find that happiness in the user’s recognised facial expression strongly correlates with likeability of a robot, while dialogue-related features (such as number of human turns or number of sentences per robot utterance) correlate with perceiving a robot as intelligent. In addition, we show that facial expression, emotional features, and prosody are better predictors of human ratings related to perceived robot likeability and anthropomorphism, while linguistic and non-linguistic features more often predict perceived robot intelligence and interpretability. As such, these characteristics may in future be used as an online reward signal for in-situ Reinforcement Learning based adaptive human-robot dialogue systems.
Tasks
Published	2017-06-08
URL	http://arxiv.org/abs/1706.02757v1
PDF	http://arxiv.org/pdf/1706.02757v1.pdf
PWC	https://paperswithcode.com/paper/sympathy-begins-with-a-smile-intelligence
Repo
Framework

Phase Transitions of the Typical Algorithmic Complexity of the Random Satisfiability Problem Studied with Linear Programming


Title	Phase Transitions of the Typical Algorithmic Complexity of the Random Satisfiability Problem Studied with Linear Programming
Authors	Hendrik Schawe, Roman Bleim, Alexander K. Hartmann
Abstract	Here we study the NP-complete $K$-SAT problem. Although the worst-case complexity of NP-complete problems is conjectured to be exponential, there exist parametrized random ensembles of problems where solutions can typically be found in polynomial time for suitable ranges of the parameter. In fact, random $K$-SAT, with $\alpha=M/N $ as control parameter, can be solved quickly for small enough values of $\alpha$. It shows a phase transition between a satisfiable phase and an unsatisfiable phase. For branch and bound algorithms, which operate in the space of feasible Boolean configurations, the empirically hardest problems are located only close to this phase transition. Here we study $K$-SAT ($K=3,4$) and the related optimization problem MAX-SAT by a linear programming approach, which is widely used for practical problems and allows for polynomial run time. In contrast to branch and bound it operates outside the space of feasible configurations. On the other hand, finding a solution within polynomial time is not guaranteed. We investigated several variants like including artificial objective functions, so called cutting-plane approaches, and a mapping to the NP-complete vertex-cover problem. We observed several easy-hard transitions, from where the problems are typically solvable (in polynomial time) using the given algorithms, respectively, to where they are not solvable in polynomial time. For the related vertex-cover problem on random graphs these easy-hard transitions can be identified with structural properties of the graphs, like percolation transitions. For the present random $K$-SAT problem we have investigated numerous structural properties also exhibiting clear transitions, but they appear not be correlated to the here observed easy-hard transitions. This renders the behaviour of random $K$-SAT more complex than, e.g., the vertex-cover problem.
Tasks
Published	2017-02-09
URL	http://arxiv.org/abs/1702.02821v2
PDF	http://arxiv.org/pdf/1702.02821v2.pdf
PWC	https://paperswithcode.com/paper/phase-transitions-of-the-typical-algorithmic
Repo
Framework

Learning to Teach Reinforcement Learning Agents


Title	Learning to Teach Reinforcement Learning Agents
Authors	Anestis Fachantidis, Matthew E. Taylor, Ioannis Vlahavas
Abstract	In this article we study the transfer learning model of action advice under a budget. We focus on reinforcement learning teachers providing action advice to heterogeneous students playing the game of Pac-Man under a limited advice budget. First, we examine several critical factors affecting advice quality in this setting, such as the average performance of the teacher, its variance and the importance of reward discounting in advising. The experiments show the non-trivial importance of the coefficient of variation (CV) as a statistic for choosing policies that generate advice. The CV statistic relates variance to the corresponding mean. Second, the article studies policy learning for distributing advice under a budget. Whereas most methods in the relevant literature rely on heuristics for advice distribution we formulate the problem as a learning one and propose a novel RL algorithm capable of learning when to advise, adapting to the student and the task at hand. Furthermore, we argue that learning to advise under a budget is an instance of a more generic learning problem: Constrained Exploitation Reinforcement Learning.
Tasks	Transfer Learning
Published	2017-07-28
URL	http://arxiv.org/abs/1707.09079v1
PDF	http://arxiv.org/pdf/1707.09079v1.pdf
PWC	https://paperswithcode.com/paper/learning-to-teach-reinforcement-learning
Repo
Framework

Multi-Class Model Fitting by Energy Minimization and Mode-Seeking


Title	Multi-Class Model Fitting by Energy Minimization and Mode-Seeking
Authors	Daniel Barath, Jiri Matas
Abstract	We propose a general formulation, called Multi-X, for multi-class multi-instance model fitting - the problem of interpreting the input data as a mixture of noisy observations originating from multiple instances of multiple classes. We extend the commonly used alpha-expansion-based technique with a new move in the label space. The move replaces a set of labels with the corresponding density mode in the model parameter domain, thus achieving fast and robust optimization. Key optimization parameters like the bandwidth of the mode seeking are set automatically within the algorithm. Considering that a group of outliers may form spatially coherent structures in the data, we propose a cross-validation-based technique removing statistically insignificant instances. Multi-X outperforms significantly the state-of-the-art on publicly available datasets for diverse problems: multiple plane and rigid motion detection; motion segmentation; simultaneous plane and cylinder fitting; circle and line fitting.
Tasks	Motion Detection, Motion Segmentation
Published	2017-06-02
URL	http://arxiv.org/abs/1706.00827v2
PDF	http://arxiv.org/pdf/1706.00827v2.pdf
PWC	https://paperswithcode.com/paper/multi-class-model-fitting-by-energy
Repo
Framework

Fast Estimation of Haemoglobin Concentration in Tissue Via Wavelet Decomposition


Title	Fast Estimation of Haemoglobin Concentration in Tissue Via Wavelet Decomposition
Authors	Geoffrey Jones, Neil T Clancy, Xiaofei Du, Maria Robu, Simon Arridge, Daniel S Elson, Danail Stoyanov
Abstract	Tissue oxygenation and perfusion can be an indicator for organ viability during minimally invasive surgery, for example allowing real-time assessment of tissue perfusion and oxygen saturation. Multispectral imaging is an optical modality that can inspect tissue perfusion in wide field images without contact. In this paper, we present a novel, fast method for using RGB images for MSI, which while limiting the spectral resolution of the modality allows normal laparoscopic systems to be used. We exploit the discrete Haar decomposition to separate individual video frames into low pass and directional coefficients and we utilise a different multispectral estimation technique on each. The increase in speed is achieved by using fast Tikhonov regularisation on the directional coefficients and more accurate Bayesian estimation on the low pass component. The pipeline is implemented using a graphics processing unit (GPU) architecture and achieves a frame rate of approximately 15Hz. We validate the method on animal models and on human data captured using a da Vinci stereo laparoscope.
Tasks
Published	2017-06-22
URL	http://arxiv.org/abs/1706.07263v1
PDF	http://arxiv.org/pdf/1706.07263v1.pdf
PWC	https://paperswithcode.com/paper/fast-estimation-of-haemoglobin-concentration
Repo
Framework

An approach to reachability analysis for feed-forward ReLU neural networks


Title	An approach to reachability analysis for feed-forward ReLU neural networks
Authors	Alessio Lomuscio, Lalit Maganti
Abstract	We study the reachability problem for systems implemented as feed-forward neural networks whose activation function is implemented via ReLU functions. We draw a correspondence between establishing whether some arbitrary output can ever be outputed by a neural system and linear problems characterising a neural system of interest. We present a methodology to solve cases of practical interest by means of a state-of-the-art linear programs solver. We evaluate the technique presented by discussing the experimental results obtained by analysing reachability properties for a number of benchmarks in the literature.
Tasks
Published	2017-06-22
URL	http://arxiv.org/abs/1706.07351v1
PDF	http://arxiv.org/pdf/1706.07351v1.pdf
PWC	https://paperswithcode.com/paper/an-approach-to-reachability-analysis-for-feed
Repo
Framework

Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions


Title	Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions
Authors	Paul Beame, Shayan Oveis Gharan, Xin Yang
Abstract	We develop an extension of recently developed methods for obtaining time-space tradeoff lower bounds for problems of learning from random test samples to handle the situation where the space of tests is signficantly smaller than the space of inputs, a class of learning problems that is not handled by prior work. This extension is based on a measure of how matrices amplify the 2-norms of probability distributions that is more refined than the 2-norms of these matrices. As applications that follow from our new technique, we show that any algorithm that learns $m$-variate homogeneous polynomial functions of degree at most $d$ over $\mathbb{F}_2$ from evaluations on randomly chosen inputs either requires space $\Omega(mn)$ or $2^{\Omega(m)}$ time where $n=m^{\Theta(d)}$ is the dimension of the space of such functions. These bounds are asymptotically optimal since they match the tradeoffs achieved by natural learning algorithms for the problems.
Tasks
Published	2017-08-08
URL	http://arxiv.org/abs/1708.02640v1
PDF	http://arxiv.org/pdf/1708.02640v1.pdf
PWC	https://paperswithcode.com/paper/time-space-tradeoffs-for-learning-from-small
Repo
Framework

Targeted Learning with Daily EHR Data


Title	Targeted Learning with Daily EHR Data
Authors	Oleg Sofrygin, Zheng Zhu, Julie A Schmittdiel, Alyce S. Adams, Richard W. Grant, Mark J. van der Laan, Romain Neugebauer
Abstract	Electronic health records (EHR) data provide a cost and time-effective opportunity to conduct cohort studies of the effects of multiple time-point interventions in the diverse patient population found in real-world clinical settings. Because the computational cost of analyzing EHR data at daily (or more granular) scale can be quite high, a pragmatic approach has been to partition the follow-up into coarser intervals of pre-specified length. Current guidelines suggest employing a ‘small’ interval, but the feasibility and practical impact of this recommendation has not been evaluated and no formal methodology to inform this choice has been developed. We start filling these gaps by leveraging large-scale EHR data from a diabetes study to develop and illustrate a fast and scalable targeted learning approach that allows to follow the current recommendation and study its practical impact on inference. More specifically, we map daily EHR data into four analytic datasets using 90, 30, 15 and 5-day intervals. We apply a semi-parametric and doubly robust estimation approach, the longitudinal TMLE, to estimate the causal effects of four dynamic treatment rules with each dataset, and compare the resulting inferences. To overcome the computational challenges presented by the size of these data, we propose a novel TMLE implementation, the ‘long-format TMLE’, and rely on the latest advances in scalable data-adaptive machine-learning software, xgboost and h2o, for estimation of the TMLE nuisance parameters.
Tasks
Published	2017-05-27
URL	http://arxiv.org/abs/1705.09874v2
PDF	http://arxiv.org/pdf/1705.09874v2.pdf
PWC	https://paperswithcode.com/paper/targeted-learning-with-daily-ehr-data
Repo
Framework

Agent-Centric Risk Assessment: Accident Anticipation and Risky Region Localization


Title	Agent-Centric Risk Assessment: Accident Anticipation and Risky Region Localization
Authors	Kuo-Hao Zeng, Shih-Han Chou, Fu-Hsiang Chan, Juan Carlos Niebles, Min Sun
Abstract	For survival, a living agent must have the ability to assess risk (1) by temporally anticipating accidents before they occur, and (2) by spatially localizing risky regions in the environment to move away from threats. In this paper, we take an agent-centric approach to study the accident anticipation and risky region localization tasks. We propose a novel soft-attention Recurrent Neural Network (RNN) which explicitly models both spatial and appearance-wise non-linear interaction between the agent triggering the event and another agent or static-region involved. In order to test our proposed method, we introduce the Epic Fail (EF) dataset consisting of 3000 viral videos capturing various accidents. In the experiments, we evaluate the risk assessment accuracy both in the temporal domain (accident anticipation) and spatial domain (risky region localization) on our EF dataset and the Street Accident (SA) dataset. Our method consistently outperforms other baselines on both datasets.
Tasks
Published	2017-05-18
URL	http://arxiv.org/abs/1705.06560v1
PDF	http://arxiv.org/pdf/1705.06560v1.pdf
PWC	https://paperswithcode.com/paper/agent-centric-risk-assessment-accident
Repo
Framework

Adversarial Connective-exploiting Networks for Implicit Discourse Relation Classification


Title	Adversarial Connective-exploiting Networks for Implicit Discourse Relation Classification
Authors	Lianhui Qin, Zhisong Zhang, Hai Zhao, Zhiting Hu, Eric P. Xing
Abstract	Implicit discourse relation classification is of great challenge due to the lack of connectives as strong linguistic cues, which motivates the use of annotated implicit connectives to improve the recognition. We propose a feature imitation framework in which an implicit relation network is driven to learn from another neural network with access to connectives, and thus encouraged to extract similarly salient features for accurate classification. We develop an adversarial model to enable an adaptive imitation scheme through competition between the implicit network and a rival feature discriminator. Our method effectively transfers discriminability of connectives to the implicit features, and achieves state-of-the-art performance on the PDTB benchmark.
Tasks	Implicit Discourse Relation Classification, Relation Classification
Published	2017-04-01
URL	http://arxiv.org/abs/1704.00217v1
PDF	http://arxiv.org/pdf/1704.00217v1.pdf
PWC	https://paperswithcode.com/paper/adversarial-connective-exploiting-networks
Repo
Framework

Enhance Feature Discrimination for Unsupervised Hashing


Title	Enhance Feature Discrimination for Unsupervised Hashing
Authors	Tuan Hoang, Thanh-Toan Do, Dang-Khoa Le Tan, Ngai-Man Cheung
Abstract	We introduce a novel approach to improve unsupervised hashing. Specifically, we propose a very efficient embedding method: Gaussian Mixture Model embedding (Gemb). The proposed method, using Gaussian Mixture Model, embeds feature vector into a low-dimensional vector and, simultaneously, enhances the discriminative property of features before passing them into hashing. Our experiment shows that the proposed method boosts the hashing performance of many state-of-the-art, e.g. Binary Autoencoder (BA) [1], Iterative Quantization (ITQ) [2], in standard evaluation metrics for the three main benchmark datasets.
Tasks	Quantization
Published	2017-04-06
URL	http://arxiv.org/abs/1704.01754v2
PDF	http://arxiv.org/pdf/1704.01754v2.pdf
PWC	https://paperswithcode.com/paper/enhance-feature-discrimination-for
Repo
Framework