January 26, 2020

3141 words 15 mins read

Paper Group ANR 1588

Context-Aware Self-Attention Networks. Diverse Agents for Ad-Hoc Cooperation in Hanabi. The Homunculus Brain and Categorical Logic. Normal Approximation and Confidence Region of Singular Subspaces. A Compressed Coding Scheme for Evolutionary Algorithms in Mixed-Integer Programming: A Case Study on Multi-Objective Constrained Portfolio Optimization. …

Context-Aware Self-Attention Networks


Title	Context-Aware Self-Attention Networks
Authors	Baosong Yang, Jian Li, Derek Wong, Lidia S. Chao, Xing Wang, Zhaopeng Tu
Abstract	Self-attention model have shown its flexibility in parallel computation and the effectiveness on modeling both long- and short-term dependencies. However, it calculates the dependencies between representations without considering the contextual information, which have proven useful for modeling dependencies among neural representations in various natural language tasks. In this work, we focus on improving self-attention networks through capturing the richness of context. To maintain the simplicity and flexibility of the self-attention networks, we propose to contextualize the transformations of the query and key layers, which are used to calculates the relevance between elements. Specifically, we leverage the internal representations that embed both global and deep contexts, thus avoid relying on external resources. Experimental results on WMT14 English-German and WMT17 Chinese-English translation tasks demonstrate the effectiveness and universality of the proposed methods. Furthermore, we conducted extensive analyses to quantity how the context vectors participate in the self-attention model.
Tasks
Published	2019-02-15
URL	http://arxiv.org/abs/1902.05766v1
PDF	http://arxiv.org/pdf/1902.05766v1.pdf
PWC	https://paperswithcode.com/paper/context-aware-self-attention-networks
Repo
Framework

Diverse Agents for Ad-Hoc Cooperation in Hanabi


Title	Diverse Agents for Ad-Hoc Cooperation in Hanabi
Authors	Rodrigo Canaan, Julian Togelius, Andy Nealen, Stefan Menzel
Abstract	In complex scenarios where a model of other actors is necessary to predict and interpret their actions, it is often desirable that the model works well with a wide variety of previously unknown actors. Hanabi is a card game that brings the problem of modeling other players to the forefront, but there is no agreement on how to best generate a pool of agents to use as partners in ad-hoc cooperation evaluation. This paper proposes Quality Diversity algorithms as a promising class of algorithms to generate populations for this purpose and shows an initial implementation of an agent generator based on this idea. We also discuss what metrics can be used to compare such generators, and how the proposed generator could be leveraged to help build adaptive agents for the game.
Tasks
Published	2019-07-08
URL	https://arxiv.org/abs/1907.03840v1
PDF	https://arxiv.org/pdf/1907.03840v1.pdf
PWC	https://paperswithcode.com/paper/diverse-agents-for-ad-hoc-cooperation-in
Repo
Framework

The Homunculus Brain and Categorical Logic


Title	The Homunculus Brain and Categorical Logic
Authors	Michael Heller
Abstract	The interaction between syntax (formal language) and its semantics (meanings of language) is one which has been well studied in categorical logic. The results of this particular study are employed to understand how the brain is able to create meanings. To emphasize the toy character of the proposed model, we prefer to speak of the homunculus brain rather than the brain per se. The homunculus brain consists of neurons, each of which is modeled by a category, and axons between neurons, which are modeled by functors between the corresponding neuron-categories. Each neuron (category) has its own program enabling its working, i.e. a theory of this neuron. In analogy to what is known from categorical logic, we postulate the existence of a pair of adjoint functors, called Lang and Syn, from a category, now called BRAIN, of categories, to a category, now called MIND, of theories. Our homunculus is a kind of `mathematical robot'', the neuronal architecture of which is not important. Its only aim is to provide us with the opportunity to study how such a simple brain-like structure could` create meanings’’ and perform abstraction operations out of its purely syntactic program. The pair of adjoint functors Lang and Syn model the mutual dependencies between the syntactical structure of a given theory of MIND and the internal logic of its semantics given by a category of BRAIN. In this way, a formal language (syntax) and its meanings (semantics) are interwoven with each other in a manner corresponding to the adjointness of the functors Lang and Syn. Higher cognitive functions of abstraction and realization of concepts are also modelled by a corresponding pair of adjoint functors. The categories BRAIN and MIND interact with each other with their entire structures and, at the same time, these very structures are shaped by this interaction.
Tasks
Published	2019-02-28
URL	https://arxiv.org/abs/1903.03424v2
PDF	https://arxiv.org/pdf/1903.03424v2.pdf
PWC	https://paperswithcode.com/paper/homunculus-brain-and-categorical-logic
Repo
Framework

Normal Approximation and Confidence Region of Singular Subspaces


Title	Normal Approximation and Confidence Region of Singular Subspaces
Authors	Dong Xia
Abstract	This paper is on the normal approximation of singular subspaces when the noise matrix has i.i.d. entries. Our contributions are three-fold. First, we derive an explicit representation formula of the empirical spectral projectors. The formula is neat and holds for deterministic matrix perturbations. Second, we calculate the expected projection distance between the empirical singular subspaces and true singular subspaces. Our method allows obtaining arbitrary $k$-th order approximation of the expected projection distance. Third, we prove the non-asymptotical normal approximation of the projection distance with different levels of bias corrections. By the $\lceil \log(d_1+d_2)\rceil$-th order bias corrections, the asymptotical normality holds under optimal signal-to-noise ration (SNR) condition where $d_1$ and $d_2$ denote the matrix sizes. In addition, it shows that higher order approximations are unnecessary when $d_1-d_2=O((d_1+d_2)^{1/2})$. Finally, we provide comprehensive simulation results to merit our theoretic discoveries. Unlike the existing results, our approach is non-asymptotical and the convergence rates are established. Our method allows the rank $r$ to diverge as fast as $o((d_1+d_2)^{1/3})$. Moreover, our method requires no eigen-gap condition (except the SNR) and no constraints between $d_1$ and $d_2$.
Tasks
Published	2019-01-02
URL	https://arxiv.org/abs/1901.00304v4
PDF	https://arxiv.org/pdf/1901.00304v4.pdf
PWC	https://paperswithcode.com/paper/data-dependent-confidence-regions-of-singular
Repo
Framework

A Compressed Coding Scheme for Evolutionary Algorithms in Mixed-Integer Programming: A Case Study on Multi-Objective Constrained Portfolio Optimization


Title	A Compressed Coding Scheme for Evolutionary Algorithms in Mixed-Integer Programming: A Case Study on Multi-Objective Constrained Portfolio Optimization
Authors	Yi Chen, Aimin Zhou, Swagatam Das
Abstract	A lot of real-world applications could be modeled as the Mixed-Integer Non-Linear Programming (MINLP) problems, and some prominent examples include portfolio optimization, resource allocation, image classification, as well as path planning. Actually, most of the models for these applications are non-convex and always involve some conflicting objectives. Hence, the Multi-Objective Evolutionary Algorithm (MOEA), which does not require the gradient information and is efficient at dealing with the multi-objective optimization problems, is adopted frequently for these problems. In this work, we discuss the coding scheme for MOEA in MINLP, and the major discussion focuses on the constrained portfolio optimization problem, which is a classic financial problem and could be naturally modeled as MINLP. As a result, the challenge, faced by a direct coding scheme for MOEA in MINLP, is pointed out that the searching in multiple search spaces is very complicated. Thus, a Compressed Coding Scheme (CCS), which converts an MINLP problem into a continuous problem, is proposed to address this challenge. The analyses and experiments on 20 portfolio benchmark instances, of which the number of available assets ranging from 31 to 2235, consistently indicate that CCS is not only efficient but also robust for dealing with the constrained multi-objective portfolio optimization.
Tasks	Image Classification, Portfolio Optimization
Published	2019-09-19
URL	https://arxiv.org/abs/1909.08748v1
PDF	https://arxiv.org/pdf/1909.08748v1.pdf
PWC	https://paperswithcode.com/paper/a-compressed-coding-scheme-for-evolutionary
Repo
Framework

Model-based Deep Reinforcement Learning for Dynamic Portfolio Optimization


Title	Model-based Deep Reinforcement Learning for Dynamic Portfolio Optimization
Authors	Pengqian Yu, Joon Sern Lee, Ilya Kulyatin, Zekun Shi, Sakyasingha Dasgupta
Abstract	Dynamic portfolio optimization is the process of sequentially allocating wealth to a collection of assets in some consecutive trading periods, based on investors’ return-risk profile. Automating this process with machine learning remains a challenging problem. Here, we design a deep reinforcement learning (RL) architecture with an autonomous trading agent such that, investment decisions and actions are made periodically, based on a global objective, with autonomy. In particular, without relying on a purely model-free RL agent, we train our trading agent using a novel RL architecture consisting of an infused prediction module (IPM), a generative adversarial data augmentation module (DAM) and a behavior cloning module (BCM). Our model-based approach works with both on-policy or off-policy RL algorithms. We further design the back-testing and execution engine which interact with the RL agent in real time. Using historical {\em real} financial market data, we simulate trading with practical constraints, and demonstrate that our proposed model is robust, profitable and risk-sensitive, as compared to baseline trading strategies and model-free RL agents from prior work.
Tasks	Data Augmentation, Portfolio Optimization
Published	2019-01-25
URL	http://arxiv.org/abs/1901.08740v1
PDF	http://arxiv.org/pdf/1901.08740v1.pdf
PWC	https://paperswithcode.com/paper/model-based-deep-reinforcement-learning-for
Repo
Framework

Master your Metrics with Calibration


Title	Master your Metrics with Calibration
Authors	Wissam Siblini, Jordan Fréry, Liyun He-Guelton, Frédéric Oblé, Yi-Qing Wang
Abstract	Machine learning models deployed in real-world applications are often evaluated with precision-based metrics such as F1-score or AUC-PR (Area Under the Curve of Precision Recall). Heavily dependent on the class prior, such metrics may sometimes lead to wrong conclusions about the performance. For example, when dealing with non-stationary data streams, they do not allow the user to discern the reasons why a model performance varies across different periods. In this paper, we propose a way to calibrate the metrics so that they are no longer tied to the class prior. It corresponds to a readjustment, based on probabilities, to the value that the metric would have if the class prior was equal to a reference prior (user parameter). We conduct a large number of experiments on balanced and imbalanced data to assess the behavior of calibrated metrics and show that they improve interpretability and provide a better control over what is really measured. We describe specific real-world use-cases where calibration is beneficial such as, for instance, model monitoring in production, reporting, or fairness evaluation.
Tasks	Calibration
Published	2019-09-06
URL	https://arxiv.org/abs/1909.02827v1
PDF	https://arxiv.org/pdf/1909.02827v1.pdf
PWC	https://paperswithcode.com/paper/master-your-metrics-with-calibration
Repo
Framework

Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimization


Title	Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimization
Authors	Gautam Goel, Yiheng Lin, Haoyuan Sun, Adam Wierman
Abstract	We study online convex optimization in a setting where the learner seeks to minimize the sum of a per-round hitting cost and a movement cost which is incurred when changing decisions between rounds. We prove a new lower bound on the competitive ratio of any online algorithm in the setting where the costs are $m$-strongly convex and the movement costs are the squared $\ell_2$ norm. This lower bound shows that no algorithm can achieve a competitive ratio that is $o(m^{-1/2})$ as $m$ tends to zero. No existing algorithms have competitive ratios matching this bound, and we show that the state-of-the-art algorithm, Online Balanced Decent (OBD), has a competitive ratio that is $\Omega(m^{-2/3})$. We additionally propose two new algorithms, Greedy OBD (G-OBD) and Regularized OBD (R-OBD) and prove that both algorithms have an $O(m^{-1/2})$ competitive ratio. The result for G-OBD holds when the hitting costs are quasiconvex and the movement costs are the squared $\ell_2$ norm, while the result for R-OBD holds when the hitting costs are $m$-strongly convex and the movement costs are Bregman Divergences. Further, we show that R-OBD simultaneously achieves constant, dimension-free competitive ratio and sublinear regret when hitting costs are strongly convex.
Tasks
Published	2019-05-29
URL	https://arxiv.org/abs/1905.12776v4
PDF	https://arxiv.org/pdf/1905.12776v4.pdf
PWC	https://paperswithcode.com/paper/beyond-online-balanced-descent-an-optimal
Repo
Framework

Proof-Based Synthesis of Sorting Algorithms Using Multisets in Theorema


Title	Proof-Based Synthesis of Sorting Algorithms Using Multisets in Theorema
Authors	Isabela Drămnesc, Tudor Jebelean
Abstract	Using multisets, we develop novel techniques for mechanizing the proofs of the synthesis conjectures for list-sorting algorithms, and we demonstrate them in the Theorema system. We use the classical principle of extracting the algorithm as a set of rewrite rules based on the witnesses found in the proof of the synthesis conjecture produced from the specification of the desired function (input and output conditions). The proofs are in natural style, using standard rules, but most importantly domain specific inference rules and strategies. In particular the use of multisets allows us to develop powerful strategies for the synthesis of arbitrarily structured recursive algorithms by general Noetherian induction, as well as for the automatic generation of the specifications of all necessary auxiliary functions (insert, merge, split), whose synthesis is performed using the same method.
Tasks
Published	2019-09-04
URL	https://arxiv.org/abs/1909.01747v1
PDF	https://arxiv.org/pdf/1909.01747v1.pdf
PWC	https://paperswithcode.com/paper/proof-based-synthesis-of-sorting-algorithms
Repo
Framework

Variational Osmosis for Non-linear Image Fusion


Title	Variational Osmosis for Non-linear Image Fusion
Authors	Simone Parisotto, Luca Calatroni, Aurélie Bugeau, Nicolas Papadakis, Carola-Bibiane Schönlieb
Abstract	We propose a new variational model for non-linear image fusion. Our approach is based on the use of an osmosis energy term related to the one studied in Vogel et al. (2013) and Weickert et al. (2013) The minimization of the proposed non-convex energy realizes visually plausible image data fusion, invariant to multiplicative brightness changes. On the practical side, it requires minimal supervision and parameter tuning and can encode prior information on the structure of the images to be fused. For the numerical solution of the proposed model, we develop a primal-dual algorithm and we apply the resulting minimization scheme to solve multi-modal face fusion, color transfer and cultural heritage conservation problems. Visual and quantitative comparisons to state-of-the-art approaches prove the out-performance and the flexibility of our method.
Tasks
Published	2019-10-04
URL	https://arxiv.org/abs/1910.02012v2
PDF	https://arxiv.org/pdf/1910.02012v2.pdf
PWC	https://paperswithcode.com/paper/variational-osmosis-for-non-linear-image
Repo
Framework

Energy Usage Reports: Environmental awareness as part of algorithmic accountability


Title	Energy Usage Reports: Environmental awareness as part of algorithmic accountability
Authors	Kadan Lottick, Silvia Susai, Sorelle A. Friedler, Jonathan P. Wilson
Abstract	The carbon footprint of algorithms must be measured and transparently reported so computer scientists can take an honest and active role in environmental sustainability. In this paper, we take analyses usually applied at the industrial level and make them accessible for individual computer science researchers with an easy-to-use Python package. Localizing to the energy mixture of the electrical power grid, we make the conversion from energy usage to CO2 emissions, in addition to contextualizing these results with more human-understandable benchmarks such as automobile miles driven. We also include comparisons with energy mixtures employed in electrical grids around the world. We propose including these automatically-generated Energy Usage Reports as part of standard algorithmic accountability practices, and demonstrate the use of these reports as part of model-choice in a machine learning context.
Tasks
Published	2019-11-19
URL	https://arxiv.org/abs/1911.08354v2
PDF	https://arxiv.org/pdf/1911.08354v2.pdf
PWC	https://paperswithcode.com/paper/energy-usage-reports-environmental-awareness
Repo
Framework

Dynamic Knowledge Graph Construction for Zero-shot Commonsense Question Answering


Title	Dynamic Knowledge Graph Construction for Zero-shot Commonsense Question Answering
Authors	Antoine Bosselut, Yejin Choi
Abstract	Understanding narratives requires dynamically reasoning about the implicit causes, effects, and states of the situations described in text, which in turn requires understanding rich background knowledge about how the social and physical world works. At the core of this challenge is how to access contextually relevant knowledge on demand and reason over it. In this paper, we present initial studies toward zero-shot commonsense QA by formulating the task as probabilistic inference over dynamically generated commonsense knowledge graphs. In contrast to previous studies for knowledge integration that rely on retrieval of existing knowledge from static knowledge graphs, our study requires commonsense knowledge integration where contextually relevant knowledge is often not present in existing knowledge bases. Therefore, we present a novel approach that generates contextually relevant knowledge on demand using generative neural commonsense knowledge models. Empirical results on the SocialIQa and StoryCommonsense datasets in a zero-shot setting demonstrate that using commonsense knowledge models to dynamically construct and reason over knowledge graphs achieves performance boosts over pre-trained language models and using knowledge models to directly evaluate answers.
Tasks	graph construction, Knowledge Graphs, Question Answering
Published	2019-11-10
URL	https://arxiv.org/abs/1911.03876v1
PDF	https://arxiv.org/pdf/1911.03876v1.pdf
PWC	https://paperswithcode.com/paper/dynamic-knowledge-graph-construction-for-zero
Repo
Framework

Zap Q-Learning With Nonlinear Function Approximation


Title	Zap Q-Learning With Nonlinear Function Approximation
Authors	Shuhang Chen, Adithya M. Devraj, Ana Bušić, Sean Meyn
Abstract	The Zap stochastic approximation (SA) algorithm was introduced recently as a means to accelerate convergence in reinforcement learning algorithms. While numerical results were impressive, stability (in the sense of boundedness of parameter estimates) was established in only a few special cases. This class of algorithms is generalized in this paper, and stability is established under very general conditions. This general result can be applied to a wide range of algorithms found in reinforcement learning. Two classes are considered in this paper: (i)The natural generalization of Watkins’ algorithm is not always stable in function approximation settings. Parameter estimates may diverge to infinity even in the \textit{linear} function approximation setting with a simple finite state-action MDP. Under mild conditions, the Zap SA algorithm provides a stable algorithm, even in the case of \textit{nonlinear} function approximation. (ii) The GQ algorithm of Maei et.~al.~2010 is designed to address the stability challenge. Analysis is provided to explain why the algorithm may be very slow to converge in practice. The new Zap GQ algorithm is stable even for nonlinear function approximation.
Tasks	Q-Learning
Published	2019-10-11
URL	https://arxiv.org/abs/1910.05405v1
PDF	https://arxiv.org/pdf/1910.05405v1.pdf
PWC	https://paperswithcode.com/paper/zap-q-learning-with-nonlinear-function
Repo
Framework

An Investigation of Quantum Deep Clustering Framework with Quantum Deep SVM & Convolutional Neural Network Feature Extractor


Title	An Investigation of Quantum Deep Clustering Framework with Quantum Deep SVM & Convolutional Neural Network Feature Extractor
Authors	Arit Kumar Bishwas, Ashish Mani, Vasile Palade
Abstract	In this paper, we have proposed a deep quantum SVM formulation, and further demonstrated a quantum-clustering framework based on the quantum deep SVM formulation, deep convolutional neural networks, and quantum K-Means clustering. We have investigated the run time computational complexity of the proposed quantum deep clustering framework and compared with the possible classical implementation. Our investigation shows that the proposed quantum version of deep clustering formulation demonstrates a significant performance gain (exponential speed up gains in many sections) against the possible classical implementation. The proposed theoretical quantum deep clustering framework is also interesting & novel research towards the quantum-classical machine learning formulation to articulate the maximum performance.
Tasks
Published	2019-09-21
URL	https://arxiv.org/abs/1909.09852v1
PDF	https://arxiv.org/pdf/1909.09852v1.pdf
PWC	https://paperswithcode.com/paper/190909852
Repo
Framework

Residual Networks Behave Like Boosting Algorithms


Title	Residual Networks Behave Like Boosting Algorithms
Authors	Chapman Siu
Abstract	We show that Residual Networks (ResNet) is equivalent to boosting feature representation, without any modification to the underlying ResNet training algorithm. A regret bound based on Online Gradient Boosting theory is proved and suggests that ResNet could achieve Online Gradient Boosting regret bounds through neural network architectural changes with the addition of a shrinkage parameter in the identity skip-connections and using residual modules with max-norm bounds. Through this relation between ResNet and Online Boosting, novel feature representation boosting algorithms can be constructed based on altering residual modules. We demonstrate this through proposing decision tree residual modules to construct a new boosted decision tree algorithm and demonstrating generalization error bounds for both approaches; relaxing constraints within BoostResNet algorithm to allow it to be trained in an out-of-core manner. We evaluate convolution ResNet with and without shrinkage modifications to demonstrate its efficacy, and demonstrate that our online boosted decision tree algorithm is comparable to state-of-the-art offline boosted decision tree algorithms without the drawback of offline approaches.
Tasks
Published	2019-09-25
URL	https://arxiv.org/abs/1909.11790v1
PDF	https://arxiv.org/pdf/1909.11790v1.pdf
PWC	https://paperswithcode.com/paper/residual-networks-behave-like-boosting
Repo
Framework