July 27, 2019

3107 words 15 mins read

Paper Group ANR 530

Butterfly Effect: Bidirectional Control of Classification Performance by Small Additive Perturbation. Hierarchical and Interpretable Skill Acquisition in Multi-task Reinforcement Learning. An Analysis of 1-to-First Matching in Iris Recognition. Unsupervised and Semi-supervised Anomaly Detection with LSTM Neural Networks. Character Distributions of …

Butterfly Effect: Bidirectional Control of Classification Performance by Small Additive Perturbation


Title	Butterfly Effect: Bidirectional Control of Classification Performance by Small Additive Perturbation
Authors	YoungJoon Yoo, Seonguk Park, Junyoung Choi, Sangdoo Yun, Nojun Kwak
Abstract	This paper proposes a new algorithm for controlling classification results by generating a small additive perturbation without changing the classifier network. Our work is inspired by existing works generating adversarial perturbation that worsens classification performance. In contrast to the existing methods, our work aims to generate perturbations that can enhance overall classification performance. To solve this performance enhancement problem, we newly propose a perturbation generation network (PGN) influenced by the adversarial learning strategy. In our problem, the information in a large external dataset is summarized by a small additive perturbation, which helps to improve the performance of the classifier trained with the target dataset. In addition to this performance enhancement problem, we show that the proposed PGN can be adopted to solve the classical adversarial problem without utilizing the information on the target classifier. The mentioned characteristics of our method are verified through extensive experiments on publicly available visual datasets.
Tasks
Published	2017-11-27
URL	http://arxiv.org/abs/1711.09681v2
PDF	http://arxiv.org/pdf/1711.09681v2.pdf
PWC	https://paperswithcode.com/paper/butterfly-effect-bidirectional-control-of
Repo
Framework

Hierarchical and Interpretable Skill Acquisition in Multi-task Reinforcement Learning


Title	Hierarchical and Interpretable Skill Acquisition in Multi-task Reinforcement Learning
Authors	Tianmin Shu, Caiming Xiong, Richard Socher
Abstract	Learning policies for complex tasks that require multiple different skills is a major challenge in reinforcement learning (RL). It is also a requirement for its deployment in real-world scenarios. This paper proposes a novel framework for efficient multi-task reinforcement learning. Our framework trains agents to employ hierarchical policies that decide when to use a previously learned policy and when to learn a new skill. This enables agents to continually acquire new skills during different stages of training. Each learned task corresponds to a human language description. Because agents can only access previously learned skills through these descriptions, the agent can always provide a human-interpretable description of its choices. In order to help the agent learn the complex temporal dependencies necessary for the hierarchical policy, we provide it with a stochastic temporal grammar that modulates when to rely on previously learned skills and when to execute new skills. We validate our approach on Minecraft games designed to explicitly test the ability to reuse previously learned skills while simultaneously learning new skills.
Tasks
Published	2017-12-20
URL	http://arxiv.org/abs/1712.07294v1
PDF	http://arxiv.org/pdf/1712.07294v1.pdf
PWC	https://paperswithcode.com/paper/hierarchical-and-interpretable-skill
Repo
Framework

An Analysis of 1-to-First Matching in Iris Recognition


Title	An Analysis of 1-to-First Matching in Iris Recognition
Authors	Andrey Kuehlkamp, Kevin W. Bowyer
Abstract	Iris recognition systems are a mature technology that is widely used throughout the world. In identification (as opposed to verification) mode, an iris to be recognized is typically matched against all N enrolled irises. This is the classic “1-to-N search”. In order to improve the speed of large-scale identification, a modified “1-to-First” search has been used in some operational systems. A 1-to-First search terminates with the first below-threshold match that is found, whereas a 1-to-N search always finds the best match across all enrollments. We know of no previous studies that evaluate how the accuracy of 1-to-First search differs from that of 1-to-N search. Using a dataset of over 50,000 iris images from 2,800 different irises, we perform experiments to evaluate the relative accuracy of 1-to-First and 1-to-N search. We evaluate how the accuracy difference changes with larger numbers of enrolled irises, and with larger ranges of rotational difference allowed between iris images. We find that False Match error rate for 1-to-First is higher than for 1-to-N, and the the difference grows with larger number of enrolled irises and with larger range of rotation.
Tasks	Iris Recognition
Published	2017-02-03
URL	http://arxiv.org/abs/1702.01167v1
PDF	http://arxiv.org/pdf/1702.01167v1.pdf
PWC	https://paperswithcode.com/paper/an-analysis-of-1-to-first-matching-in-iris
Repo
Framework

Unsupervised and Semi-supervised Anomaly Detection with LSTM Neural Networks


Title	Unsupervised and Semi-supervised Anomaly Detection with LSTM Neural Networks
Authors	Tolga Ergen, Ali Hassan Mirza, Suleyman Serdar Kozat
Abstract	We investigate anomaly detection in an unsupervised framework and introduce Long Short Term Memory (LSTM) neural network based algorithms. In particular, given variable length data sequences, we first pass these sequences through our LSTM based structure and obtain fixed length sequences. We then find a decision function for our anomaly detectors based on the One Class Support Vector Machines (OC-SVM) and Support Vector Data Description (SVDD) algorithms. As the first time in the literature, we jointly train and optimize the parameters of the LSTM architecture and the OC-SVM (or SVDD) algorithm using highly effective gradient and quadratic programming based training methods. To apply the gradient based training method, we modify the original objective criteria of the OC-SVM and SVDD algorithms, where we prove the convergence of the modified objective criteria to the original criteria. We also provide extensions of our unsupervised formulation to the semi-supervised and fully supervised frameworks. Thus, we obtain anomaly detection algorithms that can process variable length data sequences while providing high performance, especially for time series data. Our approach is generic so that we also apply this approach to the Gated Recurrent Unit (GRU) architecture by directly replacing our LSTM based structure with the GRU based structure. In our experiments, we illustrate significant performance gains achieved by our algorithms with respect to the conventional methods.
Tasks	Anomaly Detection, Time Series
Published	2017-10-25
URL	http://arxiv.org/abs/1710.09207v1
PDF	http://arxiv.org/pdf/1710.09207v1.pdf
PWC	https://paperswithcode.com/paper/unsupervised-and-semi-supervised-anomaly
Repo
Framework

Character Distributions of Classical Chinese Literary Texts: Zipf’s Law, Genres, and Epochs


Title	Character Distributions of Classical Chinese Literary Texts: Zipf’s Law, Genres, and Epochs
Authors	Chao-Lin Liu, Shuhua Zhang, Yuanli Geng, Huei-ling Lai, Hongsu Wang
Abstract	We collect 14 representative corpora for major periods in Chinese history in this study. These corpora include poetic works produced in several dynasties, novels of the Ming and Qing dynasties, and essays and news reports written in modern Chinese. The time span of these corpora ranges between 1046 BCE and 2007 CE. We analyze their character and word distributions from the viewpoint of the Zipf’s law, and look for factors that affect the deviations and similarities between their Zipfian curves. Genres and epochs demonstrated their influences in our analyses. Specifically, the character distributions for poetic works of between 618 CE and 1644 CE exhibit striking similarity. In addition, although texts of the same dynasty may tend to use the same set of characters, their character distributions still deviate from each other.
Tasks
Published	2017-09-17
URL	http://arxiv.org/abs/1709.05587v1
PDF	http://arxiv.org/pdf/1709.05587v1.pdf
PWC	https://paperswithcode.com/paper/character-distributions-of-classical-chinese
Repo
Framework

Actor-Critic Reinforcement Learning with Simultaneous Human Control and Feedback


Title	Actor-Critic Reinforcement Learning with Simultaneous Human Control and Feedback
Authors	Kory W. Mathewson, Patrick M. Pilarski
Abstract	This paper contributes a first study into how different human users deliver simultaneous control and feedback signals during human-robot interaction. As part of this work, we formalize and present a general interactive learning framework for online cooperation between humans and reinforcement learning agents. In many human-machine interaction settings, there is a growing gap between the degrees-of-freedom of complex semi-autonomous systems and the number of human control channels. Simple human control and feedback mechanisms are required to close this gap and allow for better collaboration between humans and machines on complex tasks. To better inform the design of concurrent control and feedback interfaces, we present experimental results from a human-robot collaborative domain wherein the human must simultaneously deliver both control and feedback signals to interactively train an actor-critic reinforcement learning robot. We compare three experimental conditions: 1) human delivered control signals, 2) reward-shaping feedback signals, and 3) simultaneous control and feedback. Our results suggest that subjects provide less feedback when simultaneously delivering feedback and control signals and that control signal quality is not significantly diminished. Our data suggest that subjects may also modify when and how they provide feedback. Through algorithmic development and tuning informed by this study, we expect semi-autonomous actions of robotic agents can be better shaped by human feedback, allowing for seamless collaboration and improved performance in difficult interactive domains.
Tasks
Published	2017-03-03
URL	http://arxiv.org/abs/1703.01274v2
PDF	http://arxiv.org/pdf/1703.01274v2.pdf
PWC	https://paperswithcode.com/paper/actor-critic-reinforcement-learning-with
Repo
Framework

Linear Dimensionality Reduction in Linear Time: Johnson-Lindenstrauss-type Guarantees for Random Subspace


Title	Linear Dimensionality Reduction in Linear Time: Johnson-Lindenstrauss-type Guarantees for Random Subspace
Authors	Nick Lim, Robert J. Durrant
Abstract	We consider the problem of efficient randomized dimensionality reduction with norm-preservation guarantees. Specifically we prove data-dependent Johnson-Lindenstrauss-type geometry preservation guarantees for Ho’s random subspace method: When data satisfy a mild regularity condition – the extent of which can be estimated by sampling from the data – then random subspace approximately preserves the Euclidean geometry of the data with high probability. Our guarantees are of the same order as those for random projection, namely the required dimension for projection is logarithmic in the number of data points, but have a larger constant term in the bound which depends upon this regularity. A challenging situation is when the original data have a sparse representation, since this implies a very large projection dimension is required: We show how this situation can be improved for sparse binary data by applying an efficient `densifying’ preprocessing, which neither changes the Euclidean geometry of the data nor requires an explicit matrix-matrix multiplication. We corroborate our theoretical findings with experiments on both dense and sparse high-dimensional datasets from several application domains. \|
Tasks	Dimensionality Reduction
Published	2017-05-18
URL	http://arxiv.org/abs/1705.06408v1
PDF	http://arxiv.org/pdf/1705.06408v1.pdf
PWC	https://paperswithcode.com/paper/linear-dimensionality-reduction-in-linear
Repo
Framework

Hierarchical Gaussian Descriptors with Application to Person Re-Identification


Title	Hierarchical Gaussian Descriptors with Application to Person Re-Identification
Authors	Tetsu Matsukawa, Takahiro Okabe, Einoshin Suzuki, Yoichi Sato
Abstract	Describing the color and textural information of a person image is one of the most crucial aspects of person re-identification (re-id). In this paper, we present novel meta-descriptors based on a hierarchical distribution of pixel features. Although hierarchical covariance descriptors have been successfully applied to image classification, the mean information of pixel features, which is absent from the covariance, tends to be the major discriminative information for person re-id. To solve this problem, we describe a local region in an image via hierarchical Gaussian distribution in which both means and covariances are included in their parameters. More specifically, the region is modeled as a set of multiple Gaussian distributions in which each Gaussian represents the appearance of a local patch. The characteristics of the set of Gaussians are again described by another Gaussian distribution. In both steps, we embed the parameters of the Gaussian into a point of Symmetric Positive Definite (SPD) matrix manifold. By changing the way to handle mean information in this embedding, we develop two hierarchical Gaussian descriptors. Additionally, we develop feature norm normalization methods with the ability to alleviate the biased trends that exist on the descriptors. The experimental results conducted on five public datasets indicate that the proposed descriptors achieve remarkably high performance on person re-id.
Tasks	Image Classification, Person Re-Identification
Published	2017-06-14
URL	http://arxiv.org/abs/1706.04318v1
PDF	http://arxiv.org/pdf/1706.04318v1.pdf
PWC	https://paperswithcode.com/paper/hierarchical-gaussian-descriptors-with
Repo
Framework

Sparse modeling approach to analytical continuation of imaginary-time quantum Monte Carlo data


Title	Sparse modeling approach to analytical continuation of imaginary-time quantum Monte Carlo data
Authors	Junya Otsuki, Masayuki Ohzeki, Hiroshi Shinaoka, Kazuyoshi Yoshimi
Abstract	A new approach of solving the ill-conditioned inverse problem for analytical continuation is proposed. The root of the problem lies in the fact that even tiny noise of imaginary-time input data has a serious impact on the inferred real-frequency spectra. By means of a modern regularization technique, we eliminate redundant degrees of freedom that essentially carry the noise, leaving only relevant information unaffected by the noise. The resultant spectrum is represented with minimal bases and thus a stable analytical continuation is achieved. This framework further provides a tool for analyzing to what extent the Monte Carlo data need to be accurate to resolve details of an expected spectral function.
Tasks
Published	2017-02-10
URL	http://arxiv.org/abs/1702.03056v2
PDF	http://arxiv.org/pdf/1702.03056v2.pdf
PWC	https://paperswithcode.com/paper/sparse-modeling-approach-to-analytical
Repo
Framework

Duluth at SemEval-2017 Task 6: Language Models in Humor Detection


Title	Duluth at SemEval-2017 Task 6: Language Models in Humor Detection
Authors	Xinru Yan, Ted Pedersen
Abstract	This paper describes the Duluth system that participated in SemEval-2017 Task 6 #HashtagWars: Learning a Sense of Humor. The system participated in Subtasks A and B using N-gram language models, ranking highly in the task evaluation. This paper discusses the results of our system in the development and evaluation stages and from two post-evaluation runs.
Tasks	Humor Detection
Published	2017-04-27
URL	http://arxiv.org/abs/1704.08390v1
PDF	http://arxiv.org/pdf/1704.08390v1.pdf
PWC	https://paperswithcode.com/paper/duluth-at-semeval-2017-task-6-language-models
Repo
Framework

Entropic Causality and Greedy Minimum Entropy Coupling


Title	Entropic Causality and Greedy Minimum Entropy Coupling
Authors	Murat Kocaoglu, Alexandros G. Dimakis, Sriram Vishwanath, Babak Hassibi
Abstract	We study the problem of identifying the causal relationship between two discrete random variables from observational data. We recently proposed a novel framework called entropic causality that works in a very general functional model but makes the assumption that the unobserved exogenous variable has small entropy in the true causal direction. This framework requires the solution of a minimum entropy coupling problem: Given marginal distributions of m discrete random variables, each on n states, find the joint distribution with minimum entropy, that respects the given marginals. This corresponds to minimizing a concave function of nm variables over a convex polytope defined by nm linear constraints, called a transportation polytope. Unfortunately, it was recently shown that this minimum entropy coupling problem is NP-hard, even for 2 variables with n states. Even representing points (joint distributions) over this space can require exponential complexity (in n, m) if done naively. In our recent work we introduced an efficient greedy algorithm to find an approximate solution for this problem. In this paper we analyze this algorithm and establish two results: that our algorithm always finds a local minimum and also is within an additive approximation error from the unknown global optimum.
Tasks
Published	2017-01-28
URL	http://arxiv.org/abs/1701.08254v1
PDF	http://arxiv.org/pdf/1701.08254v1.pdf
PWC	https://paperswithcode.com/paper/entropic-causality-and-greedy-minimum-entropy
Repo
Framework

Dynamic Principal Projection for Cost-Sensitive Online Multi-Label Classification


Title	Dynamic Principal Projection for Cost-Sensitive Online Multi-Label Classification
Authors	Hong-Min Chu, Kuan-Hao Huang, Hsuan-Tien Lin
Abstract	We study multi-label classification (MLC) with three important real-world issues: online updating, label space dimensional reduction (LSDR), and cost-sensitivity. Current MLC algorithms have not been designed to address these three issues simultaneously. In this paper, we propose a novel algorithm, cost-sensitive dynamic principal projection (CS-DPP) that resolves all three issues. The foundation of CS-DPP is an online LSDR framework derived from a leading LSDR algorithm. In particular, CS-DPP is equipped with an efficient online dimension reducer motivated by matrix stochastic gradient, and establishes its theoretical backbone when coupled with a carefully-designed online regression learner. In addition, CS-DPP embeds the cost information into label weights to achieve cost-sensitivity along with theoretical guarantees. Experimental results verify that CS-DPP achieves better practical performance than current MLC algorithms across different evaluation criteria, and demonstrate the importance of resolving the three issues simultaneously.
Tasks	Multi-Label Classification
Published	2017-11-14
URL	http://arxiv.org/abs/1711.05060v2
PDF	http://arxiv.org/pdf/1711.05060v2.pdf
PWC	https://paperswithcode.com/paper/dynamic-principal-projection-for-cost
Repo
Framework

Leveraging the Crowd to Detect and Reduce the Spread of Fake News and Misinformation


Title	Leveraging the Crowd to Detect and Reduce the Spread of Fake News and Misinformation
Authors	Jooyeon Kim, Behzad Tabibian, Alice Oh, Bernhard Schoelkopf, Manuel Gomez-Rodriguez
Abstract	Online social networking sites are experimenting with the following crowd-powered procedure to reduce the spread of fake news and misinformation: whenever a user is exposed to a story through her feed, she can flag the story as misinformation and, if the story receives enough flags, it is sent to a trusted third party for fact checking. If this party identifies the story as misinformation, it is marked as disputed. However, given the uncertain number of exposures, the high cost of fact checking, and the trade-off between flags and exposures, the above mentioned procedure requires careful reasoning and smart algorithms which, to the best of our knowledge, do not exist to date. In this paper, we first introduce a flexible representation of the above procedure using the framework of marked temporal point processes. Then, we develop a scalable online algorithm, Curb, to select which stories to send for fact checking and when to do so to efficiently reduce the spread of misinformation with provable guarantees. In doing so, we need to solve a novel stochastic optimal control problem for stochastic differential equations with jumps, which is of independent interest. Experiments on two real-world datasets gathered from Twitter and Weibo show that our algorithm may be able to effectively reduce the spread of fake news and misinformation.
Tasks	Point Processes
Published	2017-11-27
URL	http://arxiv.org/abs/1711.09918v1
PDF	http://arxiv.org/pdf/1711.09918v1.pdf
PWC	https://paperswithcode.com/paper/leveraging-the-crowd-to-detect-and-reduce-the
Repo
Framework

Benefits from Superposed Hawkes Processes


Title	Benefits from Superposed Hawkes Processes
Authors	Hongteng Xu, Dixin Luo, Xu Chen, Lawrence Carin
Abstract	The superposition of temporal point processes has been studied for many years, although the usefulness of such models for practical applications has not be fully developed. We investigate superposed Hawkes process as an important class of such models, with properties studied in the framework of least squares estimation. The superposition of Hawkes processes is demonstrated to be beneficial for tightening the upper bound of excess risk under certain conditions, and we show the feasibility of the benefit in typical situations. The usefulness of superposed Hawkes processes is verified on synthetic data, and its potential to solve the cold-start problem of recommendation systems is demonstrated on real-world data.
Tasks	Point Processes, Recommendation Systems
Published	2017-10-14
URL	http://arxiv.org/abs/1710.05115v3
PDF	http://arxiv.org/pdf/1710.05115v3.pdf
PWC	https://paperswithcode.com/paper/benefits-from-superposed-hawkes-processes
Repo
Framework

Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCA


Title	Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCA
Authors	Ji Chen, Xiaodong Li
Abstract	This work studies low-rank approximation of a positive semidefinite matrix from partial entries via nonconvex optimization. We characterized how well local-minimum based low-rank factorization approximates a fixed positive semidefinite matrix without any assumptions on the rank-matching, the condition number or eigenspace incoherence parameter. Furthermore, under certain assumptions on rank-matching and well-boundedness of condition numbers and eigenspace incoherence parameters, a corollary of our main theorem improves the state-of-the-art sampling rate results for nonconvex matrix completion with no spurious local minima in Ge et al. [2016, 2017]. In addition, we investigated when the proposed nonconvex optimization results in accurate low-rank approximations even in presence of large condition numbers, large incoherence parameters, or rank mismatching. We also propose to apply the nonconvex optimization to memory-efficient Kernel PCA. Compared to the well-known Nystr"{o}m methods, numerical experiments indicate that the proposed nonconvex optimization approach yields more stable results in both low-rank approximation and clustering.
Tasks	Dimensionality Reduction, Matrix Completion
Published	2017-11-06
URL	http://arxiv.org/abs/1711.01742v3
PDF	http://arxiv.org/pdf/1711.01742v3.pdf
PWC	https://paperswithcode.com/paper/memory-efficient-kernel-pca-via-partial
Repo
Framework