April 2, 2020

2985 words 15 mins read

Paper Group ANR 382

Fundamental Limits of Online Learning: An Entropic-Innovations Viewpoint. Stochastic L-system Inference from Multiple String Sequence Inputs. Robust data encodings for quantum classifiers. A Hybrid Solution to Learn Turn-Taking in Multi-Party Service-based Chat Groups. Smooth markets: A basic mechanism for organizing gradient-based learners. The pr …

Fundamental Limits of Online Learning: An Entropic-Innovations Viewpoint


Title	Fundamental Limits of Online Learning: An Entropic-Innovations Viewpoint
Authors	Song Fang, Quanyan Zhu
Abstract	In this paper, we examine the fundamental performance limitations of online machine learning, by viewing the online learning problem as a prediction problem with causal side information. Towards this end, we combine the entropic analysis from information theory and the innovations approach from prediction theory to derive generic lower bounds on the prediction errors as well as the conditions (in terms of, e.g., directed information) to achieve the bounds. It is seen in general that no specific restrictions have to be imposed on the learning algorithms or the distributions of the data points for the performance bounds to be valid. In addition, the cases of supervised learning, semi-supervised learning, as well as unsupervised learning can all be analyzed accordingly. We also investigate the implications of the results in analyzing the fundamental limits of generalization.
Tasks
Published	2020-01-12
URL	https://arxiv.org/abs/2001.03813v2
PDF	https://arxiv.org/pdf/2001.03813v2.pdf
PWC	https://paperswithcode.com/paper/fundamental-limits-of-online-learning-an
Repo
Framework

Stochastic L-system Inference from Multiple String Sequence Inputs


Title	Stochastic L-system Inference from Multiple String Sequence Inputs
Authors	Jason Bernard, Ian McQuillan
Abstract	Lindenmayer systems (L-systems) are a grammar system that consist of string rewriting rules. The rules replace every symbol in a string in parallel with a successor to produce the next string, and this procedure iterates. In a stochastic context-free L-system (S0L-system), every symbol may have one or more rewriting rule, each with an associated probability of selection. Properly constructed rewriting rules have been found to be useful for modeling and simulating some natural and human engineered processes where each derived string describes a step in the simulation. Typically, processes are modeled by experts who meticulously construct the rules based on measurements or domain knowledge of the process. This paper presents an automated approach to finding stochastic L-systems, given a set of string sequences as input. The implemented tool is called the Plant Model Inference Tool for S0L-systems (PMIT-S0L). PMIT-S0L is evaluated using 960 procedurally generated S0L-systems in a test suite, which are each used to generate input strings, and PMIT-S0L is then used to infer the system from only the sequences. The evaluation shows that PMIT-S0L infers S0L-systems with up to 9 rewriting rules each in under 12 hours. Additionally, it is found that 3 sequences of strings is sufficient to find the correct original rewriting rules in 100% of the cases in the test suite, and 6 sequences of strings reduces the difference in the associated probabilities to approximately 1% or less.
Tasks
Published	2020-01-29
URL	https://arxiv.org/abs/2001.10922v1
PDF	https://arxiv.org/pdf/2001.10922v1.pdf
PWC	https://paperswithcode.com/paper/stochastic-l-system-inference-from-multiple
Repo
Framework

Robust data encodings for quantum classifiers


Title	Robust data encodings for quantum classifiers
Authors	Ryan LaRose, Brian Coyle
Abstract	Data representation is crucial for the success of machine learning models. In the context of quantum machine learning with near-term quantum computers, equally important considerations of how to efficiently input (encode) data and effectively deal with noise arise. In this work, we study data encodings for binary quantum classification and investigate their properties both with and without noise. For the common classifier we consider, we show that encodings determine the classes of learnable decision boundaries as well as the set of points which retain the same classification in the presence of noise. After defining the notion of a robust data encoding, we prove several results on robustness for different channels, discuss the existence of robust encodings, and prove an upper bound on the number of robust points in terms of fidelities between noisy and noiseless states. Numerical results for several example implementations are provided to reinforce our findings.
Tasks	Quantum Machine Learning
Published	2020-03-03
URL	https://arxiv.org/abs/2003.01695v1
PDF	https://arxiv.org/pdf/2003.01695v1.pdf
PWC	https://paperswithcode.com/paper/robust-data-encodings-for-quantum-classifiers
Repo
Framework

A Hybrid Solution to Learn Turn-Taking in Multi-Party Service-based Chat Groups


Title	A Hybrid Solution to Learn Turn-Taking in Multi-Party Service-based Chat Groups
Authors	Maira Gatti de Bayser, Melina Alberio Guerra, Paulo Cavalin, Claudio Pinhanez
Abstract	To predict the next most likely participant to interact in a multi-party conversation is a difficult problem. In a text-based chat group, the only information available is the sender, the content of the text and the dialogue history. In this paper we present our study on how these information can be used on the prediction task through a corpus and architecture that integrates turn-taking classifiers based on Maximum Likelihood Expectation (MLE), Convolutional Neural Networks (CNN) and Finite State Automata (FSA). The corpus is a synthetic adaptation of the Multi-Domain Wizard-of-Oz dataset (MultiWOZ) to a multiple travel service-based bots scenario with dialogue errors and was created to simulate user’s interaction and evaluate the architecture. We present experimental results which show that the CNN approach achieves better performance than the baseline with an accuracy of 92.34%, but the integrated solution with MLE, CNN and FSA achieves performance even better, with 95.65%.
Tasks
Published	2020-01-14
URL	https://arxiv.org/abs/2001.06350v1
PDF	https://arxiv.org/pdf/2001.06350v1.pdf
PWC	https://paperswithcode.com/paper/a-hybrid-solution-to-learn-turn-taking-in
Repo
Framework

Smooth markets: A basic mechanism for organizing gradient-based learners


Title	Smooth markets: A basic mechanism for organizing gradient-based learners
Authors	David Balduzzi, Wojciech M Czarnecki, Thomas W Anthony, Ian M Gemp, Edward Hughes, Joel Z Leibo, Georgios Piliouras, Thore Graepel
Abstract	With the success of modern machine learning, it is becoming increasingly important to understand and control how learning algorithms interact. Unfortunately, negative results from game theory show there is little hope of understanding or controlling general n-player games. We therefore introduce smooth markets (SM-games), a class of n-player games with pairwise zero sum interactions. SM-games codify a common design pattern in machine learning that includes (some) GANs, adversarial training, and other recent algorithms. We show that SM-games are amenable to analysis and optimization using first-order methods.
Tasks
Published	2020-01-14
URL	https://arxiv.org/abs/2001.04678v2
PDF	https://arxiv.org/pdf/2001.04678v2.pdf
PWC	https://paperswithcode.com/paper/smooth-markets-a-basic-mechanism-for-1
Repo
Framework

The problems with using STNs to align CNN feature maps


Title	The problems with using STNs to align CNN feature maps
Authors	Lukas Finnveden, Ylva Jansson, Tony Lindeberg
Abstract	Spatial transformer networks (STNs) were designed to enable CNNs to learn invariance to image transformations. STNs were originally proposed to transform CNN feature maps as well as input images. This enables the use of more complex features when predicting transformation parameters. However, since STNs perform a purely spatial transformation, they do not, in the general case, have the ability to align the feature maps of a transformed image and its original. We present a theoretical argument for this and investigate the practical implications, showing that this inability is coupled with decreased classification accuracy. We advocate taking advantage of more complex features in deeper layers by instead sharing parameters between the classification and the localisation network.
Tasks
Published	2020-01-14
URL	https://arxiv.org/abs/2001.05858v1
PDF	https://arxiv.org/pdf/2001.05858v1.pdf
PWC	https://paperswithcode.com/paper/the-problems-with-using-stns-to-align-cnn
Repo
Framework

Rethinking the Distribution Gap of Person Re-identification with Camera-based Batch Normalization


Title	Rethinking the Distribution Gap of Person Re-identification with Camera-based Batch Normalization
Authors	Zijie Zhuang, Longhui Wei, Lingxi Xie, Tianyu Zhang, Hengheng Zhang, Haozhe Wu, Haizhou Ai, Qi Tian
Abstract	The fundamental difficulty in person re-identification (ReID) lies in learning the correspondence among individual cameras. It strongly demands costly inter-camera annotations, yet the trained models are not guaranteed to transfer well to previously unseen cameras. These problems significantly limit the application of ReID. This paper rethinks the working mechanism of conventional ReID approaches and puts forward a new solution. With an effective operator named Camera-based Batch Normalization (CBN), we force the image data of all cameras to fall onto the same subspace, so that the distribution gap between any camera pair is largely shrunk. This alignment brings two benefits. First, the trained model enjoys better abilities to generalize across scenarios with unseen cameras as well as transfer across multiple training sets. Second, we can rely on intra-camera annotations, which have been undervalued before due to the lack of cross-camera information, to achieve competitive ReID performance. Experiments on a wide range of ReID tasks demonstrate the effectiveness of our approach. The code will be publicly available.
Tasks	Domain Adaptation, Person Re-Identification
Published	2020-01-23
URL	https://arxiv.org/abs/2001.08680v2
PDF	https://arxiv.org/pdf/2001.08680v2.pdf
PWC	https://paperswithcode.com/paper/disassembling-the-dataset-a-camera-alignment
Repo
Framework

Memorizing Comprehensively to Learn Adaptively: Unsupervised Cross-Domain Person Re-ID with Multi-level Memory


Title	Memorizing Comprehensively to Learn Adaptively: Unsupervised Cross-Domain Person Re-ID with Multi-level Memory
Authors	Xinyu Zhang, Dong Gong, Jiewei Cao, Chunhua Shen
Abstract	Unsupervised cross-domain person re-identification (Re-ID) aims to adapt the information from the labelled source domain to an unlabelled target domain. Due to the lack of supervision in the target domain, it is crucial to identify the underlying similarity-and-dissimilarity relationships among the unlabelled samples in the target domain. In order to use the whole data relationships efficiently in mini-batch training, we apply a series of memory modules to maintain an up-to-date representation of the entire dataset. Unlike the simple exemplar memory in previous works, we propose a novel multi-level memory network (MMN) to discover multi-level complementary information in the target domain, relying on three memory modules, i.e., part-level memory, instance-level memory, and domain-level memory. The proposed memory modules store multi-level representations of the target domain, which capture both the fine-grained differences between images and the global structure for the holistic target domain. The three memory modules complement each other and systematically integrate multi-level supervision from bottom to up. Experiments on three datasets demonstrate that the multi-level memory modules cooperatively boost the unsupervised cross-domain Re-ID task, and the proposed MMN achieves competitive results.
Tasks	Person Re-Identification
Published	2020-01-13
URL	https://arxiv.org/abs/2001.04123v1
PDF	https://arxiv.org/pdf/2001.04123v1.pdf
PWC	https://paperswithcode.com/paper/memorizing-comprehensively-to-learn
Repo
Framework

Multi-Attribute Guided Painting Generation


Title	Multi-Attribute Guided Painting Generation
Authors	Minxuan Lin, Yingying Deng, Fan Tang, Weiming Dong, Changsheng Xu
Abstract	Controllable painting generation plays a pivotal role in image stylization. Currently, the control way of style transfer is subject to exemplar-based reference or a random one-hot vector guidance. Few works focus on decoupling the intrinsic properties of painting as control conditions, e.g., artist, genre and period. Under this circumstance, we propose a novel framework adopting multiple attributes from the painting to control the stylized results. An asymmetrical cycle structure is equipped to preserve the fidelity, associating with style preserving and attribute regression loss to keep the unique distinction of colors and textures between domains. Several qualitative and quantitative results demonstrate the effect of the combinations of multiple attributes and achieve satisfactory performance.
Tasks	Image Stylization, Style Transfer
Published	2020-02-26
URL	https://arxiv.org/abs/2002.11261v1
PDF	https://arxiv.org/pdf/2002.11261v1.pdf
PWC	https://paperswithcode.com/paper/multi-attribute-guided-painting-generation
Repo
Framework

Towards a Soft Faceted Browsing Scheme for Information Access


Title	Towards a Soft Faceted Browsing Scheme for Information Access
Authors	Yinan Zhang, Parikshit Sondhi, Anjan Goswami, ChengXiang Zhai
Abstract	Faceted browsing is a commonly supported feature of user interfaces for access to information. Existing interfaces generally treat facet values selected by a user as hard filters and respond to the user by only displaying information items strictly satisfying the filters and in their original ranking order. We propose a novel alternative strategy for faceted browsing, called soft faceted browsing, where the system also includes some possibly relevant items outside the selected filter in a non-intrusive way and re-ranks the items to better satisfy the user’s information need. Such a soft faceted browsing strategy can be beneficial when the user does not have a very confident and strict preference for the selected facet values, and is especially appropriate for applications such as e-commerce search where the user would like to explore a larger space before finalizing a purchasing decision. We propose a probabilistic framework for modeling and solving the soft faceted browsing problem, and apply the framework to study the case of facet filter selection in e-commerce search engines. Preliminary experiment results demonstrate the soft faceted browsing scheme is better than the traditional faceted browsing scheme in terms of its efficiency in helping users navigate in the information space.
Tasks
Published	2020-02-20
URL	https://arxiv.org/abs/2002.08577v1
PDF	https://arxiv.org/pdf/2002.08577v1.pdf
PWC	https://paperswithcode.com/paper/towards-a-soft-faceted-browsing-scheme-for
Repo
Framework

Image Stylization: From Predefined to Personalized


Title	Image Stylization: From Predefined to Personalized
Authors	Ignacio Garcia-Dorado, Pascal Getreuer, Bartlomiej Wronski, Peyman Milanfar
Abstract	We present a framework for interactive design of new image stylizations using a wide range of predefined filter blocks. Both novel and off-the-shelf image filtering and rendering techniques are extended and combined to allow the user to unleash their creativity to intuitively invent, modify, and tune new styles from a given set of filters. In parallel to this manual design, we propose a novel procedural approach that automatically assembles sequences of filters, leading to unique and novel styles. An important aim of our framework is to allow for interactive exploration and design, as well as to enable videos and camera streams to be stylized on the fly. In order to achieve this real-time performance, we use the \textit{Best Linear Adaptive Enhancement} (BLADE) framework – an interpretable shallow machine learning method that simulates complex filter blocks in real time. Our representative results include over a dozen styles designed using our interactive tool, a set of styles created procedurally, and new filters trained with our BLADE approach.
Tasks	Image Stylization
Published	2020-02-22
URL	https://arxiv.org/abs/2002.10945v1
PDF	https://arxiv.org/pdf/2002.10945v1.pdf
PWC	https://paperswithcode.com/paper/image-stylization-from-predefined-to
Repo
Framework

Improved Consistency Regularization for GANs


Title	Improved Consistency Regularization for GANs
Authors	Zhengli Zhao, Sameer Singh, Honglak Lee, Zizhao Zhang, Augustus Odena, Han Zhang
Abstract	Recent work has increased the performance of Generative Adversarial Networks (GANs) by enforcing a consistency cost on the discriminator. We improve on this technique in several ways. We first show that consistency regularization can introduce artifacts into the GAN samples and explain how to fix this issue. We then propose several modifications to the consistency regularization procedure designed to improve its performance. We carry out extensive experiments quantifying the benefit of our improvements. For unconditional image synthesis on CIFAR-10 and CelebA, our modifications yield the best known FID scores on various GAN architectures. For conditional image synthesis on CIFAR-10, we improve the state-of-the-art FID score from 11.48 to 9.21. Finally, on ImageNet-2012, we apply our technique to the original BigGAN model and improve the FID from 6.66 to 5.38, which is the best score at that model size.
Tasks	Image Generation
Published	2020-02-11
URL	https://arxiv.org/abs/2002.04724v1
PDF	https://arxiv.org/pdf/2002.04724v1.pdf
PWC	https://paperswithcode.com/paper/improved-consistency-regularization-for-gans
Repo
Framework

Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive


Title	Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive
Authors	Matteo Castiglioni, Andrea Celli, Nicola Gatti
Abstract	Persuasion studies how an informed principal may influence the behavior of agents by the strategic provision of payoff-relevant information. We focus on the fundamental multi-receiver model by Arieli and Babichenko (2019), in which there are no inter-agent externalities. Unlike prior works on this problem, we study the public persuasion problem in the general setting with: (i) arbitrary state spaces; (ii) arbitrary action spaces; (iii) arbitrary sender’s utility functions. We fully characterize the computational complexity of computing a bi-criteria approximation of an optimal public signaling scheme. In particular, we show, in a voting setting of independent interest, that solving this problem requires at least a quasi-polynomial number of steps even in settings with a binary action space, assuming the Exponential Time Hypothesis. In doing so, we prove that a relaxed version of the Maximum Feasible Subsystem of Linear Inequalities problem requires at least quasi-polynomial time to be solved. Finally, we close the gap by providing a quasi-polynomial time bi-criteria approximation algorithm for arbitrary public persuasion problems that, in specific settings, yields a QPTAS.
Tasks
Published	2020-02-12
URL	https://arxiv.org/abs/2002.05156v2
PDF	https://arxiv.org/pdf/2002.05156v2.pdf
PWC	https://paperswithcode.com/paper/public-bayesian-persuasion-being-almost
Repo
Framework

Safe Reinforcement Learning for Autonomous Vehicles through Parallel Constrained Policy Optimization


Title	Safe Reinforcement Learning for Autonomous Vehicles through Parallel Constrained Policy Optimization
Authors	Lu Wen, Jingliang Duan, Shengbo Eben Li, Shaobing Xu, Huei Peng
Abstract	Reinforcement learning (RL) is attracting increasing interests in autonomous driving due to its potential to solve complex classification and control problems. However, existing RL algorithms are rarely applied to real vehicles for two predominant problems: behaviours are unexplainable, and they cannot guarantee safety under new scenarios. This paper presents a safe RL algorithm, called Parallel Constrained Policy Optimization (PCPO), for two autonomous driving tasks. PCPO extends today’s common actor-critic architecture to a three-component learning framework, in which three neural networks are used to approximate the policy function, value function and a newly added risk function, respectively. Meanwhile, a trust region constraint is added to allow large update steps without breaking the monotonic improvement condition. To ensure the feasibility of safety constrained problems, synchronized parallel learners are employed to explore different state spaces, which accelerates learning and policy-update. The simulations of two scenarios for autonomous vehicles confirm we can ensure safety while achieving fast learning.
Tasks	Autonomous Driving, Autonomous Vehicles
Published	2020-03-03
URL	https://arxiv.org/abs/2003.01303v1
PDF	https://arxiv.org/pdf/2003.01303v1.pdf
PWC	https://paperswithcode.com/paper/safe-reinforcement-learning-for-autonomous
Repo
Framework

Kernelized Support Tensor Train Machines


Title	Kernelized Support Tensor Train Machines
Authors	Cong Chen, Kim Batselier, Wenjian Yu, Ngai Wong
Abstract	Tensor, a multi-dimensional data structure, has been exploited recently in the machine learning community. Traditional machine learning approaches are vector- or matrix-based, and cannot handle tensorial data directly. In this paper, we propose a tensor train (TT)-based kernel technique for the first time, and apply it to the conventional support vector machine (SVM) for image classification. Specifically, we propose a kernelized support tensor train machine that accepts tensorial input and preserves the intrinsic kernel property. The main contributions are threefold. First, we propose a TT-based feature mapping procedure that maintains the TT structure in the feature space. Second, we demonstrate two ways to construct the TT-based kernel function while considering consistency with the TT inner product and preservation of information. Third, we show that it is possible to apply different kernel functions on different data modes. In principle, our method tensorizes the standard SVM on its input structure and kernel mapping scheme. Extensive experiments are performed on real-world tensor data, which demonstrates the superiority of the proposed scheme under few-sample high-dimensional inputs.
Tasks	Image Classification
Published	2020-01-02
URL	https://arxiv.org/abs/2001.00360v1
PDF	https://arxiv.org/pdf/2001.00360v1.pdf
PWC	https://paperswithcode.com/paper/kernelized-support-tensor-train-machines
Repo
Framework