October 17, 2019

3023 words 15 mins read

Paper Group ANR 864

Adversarial Reinforcement Learning for Observer Design in Autonomous Systems under Cyber Attacks. Experiments with Universal CEFR Classification. Explaining Explanations in AI. On the Regret Minimization of Nonconvex Online Gradient Ascent for Online PCA. HyperFusion-Net: Densely Reflective Fusion for Salient Object Detection. Will it Blend? Compos …

Adversarial Reinforcement Learning for Observer Design in Autonomous Systems under Cyber Attacks


Title	Adversarial Reinforcement Learning for Observer Design in Autonomous Systems under Cyber Attacks
Authors	Abhishek Gupta, Zhaoyuan Yang
Abstract	Complex autonomous control systems are subjected to sensor failures, cyber-attacks, sensor noise, communication channel failures, etc. that introduce errors in the measurements. The corrupted information, if used for making decisions, can lead to degraded performance. We develop a framework for using adversarial deep reinforcement learning to design observer strategies that are robust to adversarial errors in information channels. We further show through simulation studies that the learned observation strategies perform remarkably well when the adversary’s injected errors are bounded in some sense. We use neural network as function approximator in our studies with the understanding that any other suitable function approximating class can be used within our framework.
Tasks
Published	2018-09-15
URL	http://arxiv.org/abs/1809.06784v1
PDF	http://arxiv.org/pdf/1809.06784v1.pdf
PWC	https://paperswithcode.com/paper/adversarial-reinforcement-learning-for
Repo
Framework

Experiments with Universal CEFR Classification


Title	Experiments with Universal CEFR Classification
Authors	Sowmya Vajjala, Taraka Rama
Abstract	The Common European Framework of Reference (CEFR) guidelines describe language proficiency of learners on a scale of 6 levels. While the description of CEFR guidelines is generic across languages, the development of automated proficiency classification systems for different languages follow different approaches. In this paper, we explore universal CEFR classification using domain-specific and domain-agnostic, theory-guided as well as data-driven features. We report the results of our preliminary experiments in monolingual, cross-lingual, and multilingual classification with three languages: German, Czech, and Italian. Our results show that both monolingual and multilingual models achieve similar performance, and cross-lingual classification yields lower, but comparable results to monolingual classification.
Tasks
Published	2018-04-18
URL	http://arxiv.org/abs/1804.06636v1
PDF	http://arxiv.org/pdf/1804.06636v1.pdf
PWC	https://paperswithcode.com/paper/experiments-with-universal-cefr
Repo
Framework

Explaining Explanations in AI


Title	Explaining Explanations in AI
Authors	Brent Mittelstadt, Chris Russell, Sandra Wachter
Abstract	Recent work on interpretability in machine learning and AI has focused on the building of simplified models that approximate the true criteria used to make decisions. These models are a useful pedagogical device for teaching trained professionals how to predict what decisions will be made by the complex system, and most importantly how the system might break. However, when considering any such model it’s important to remember Box’s maxim that “All models are wrong but some are useful.” We focus on the distinction between these models and explanations in philosophy and sociology. These models can be understood as a “do it yourself kit” for explanations, allowing a practitioner to directly answer “what if questions” or generate contrastive explanations without external assistance. Although a valuable ability, giving these models as explanations appears more difficult than necessary, and other forms of explanation may not have the same trade-offs. We contrast the different schools of thought on what makes an explanation, and suggest that machine learning might benefit from viewing the problem more broadly.
Tasks
Published	2018-11-04
URL	http://arxiv.org/abs/1811.01439v1
PDF	http://arxiv.org/pdf/1811.01439v1.pdf
PWC	https://paperswithcode.com/paper/explaining-explanations-in-ai
Repo
Framework

On the Regret Minimization of Nonconvex Online Gradient Ascent for Online PCA


Title	On the Regret Minimization of Nonconvex Online Gradient Ascent for Online PCA
Authors	Dan Garber
Abstract	In this paper we focus on the problem of Online Principal Component Analysis in the regret minimization framework. For this problem, all existing regret minimization algorithms for the fully-adversarial setting are based on a positive semidefinite convex relaxation, and hence require quadratic memory and SVD computation (either thin of full) on each iteration, which amounts to at least quadratic runtime per iteration. This is in stark contrast to a corresponding stochastic i.i.d. variant of the problem, which was studied extensively lately, and admits very efficient gradient ascent algorithms that work directly on the natural non-convex formulation of the problem, and hence require only linear memory and linear runtime per iteration. This raises the question: can non-convex online gradient ascent algorithms be shown to minimize regret in online adversarial settings? In this paper we take a step forward towards answering this question. We introduce an \textit{adversarially-perturbed spiked-covariance model} in which, each data point is assumed to follow a fixed stochastic distribution with a non-zero spectral gap in the covariance matrix, but is then perturbed with some adversarial vector. This model is a natural extension of a well studied standard stochastic setting that allows for non-stationary (adversarial) patterns to arise in the data and hence, might serve as a significantly better approximation for real-world data-streams. We show that in an interesting regime of parameters, when the non-convex online gradient ascent algorithm is initialized with a “warm-start” vector, it provably minimizes the regret with high probability. We further discuss the possibility of computing such a “warm-start” vector, and also the use of regularization to obtain fast regret rates. Our theoretical findings are supported by empirical experiments on both synthetic and real-world data.
Tasks
Published	2018-09-27
URL	http://arxiv.org/abs/1809.10491v2
PDF	http://arxiv.org/pdf/1809.10491v2.pdf
PWC	https://paperswithcode.com/paper/on-the-regret-minimization-of-nonconvex
Repo
Framework

HyperFusion-Net: Densely Reflective Fusion for Salient Object Detection


Title	HyperFusion-Net: Densely Reflective Fusion for Salient Object Detection
Authors	Pingping Zhang, Huchuan Lu, Chunhua Shen
Abstract	Salient object detection (SOD), which aims to find the most important region of interest and segment the relevant object/item in that area, is an important yet challenging vision task. This problem is inspired by the fact that human seems to perceive main scene elements with high priorities. Thus, accurate detection of salient objects in complex scenes is critical for human-computer interaction. In this paper, we present a novel feature learning framework for SOD, in which we cast the SOD as a pixel-wise classification problem. The proposed framework utilizes a densely hierarchical feature fusion network, named HyperFusion-Net, automatically predicts the most important area and segments the associated objects in an end-to-end manner. Specifically, inspired by the human perception system and image reflection separation, we first decompose input images into reflective image pairs by content-preserving transforms. Then, the complementary information of reflective image pairs is jointly extracted by an interweaved convolutional neural network (ICNN) and hierarchically combined with a hyper-dense fusion mechanism. Based on the fused multi-scale features, our method finally achieves a promising way of predicting SOD. As shown in our extensive experiments, the proposed method consistently outperforms other state-of-the-art methods on seven public datasets with a large margin.
Tasks	Object Detection, Salient Object Detection
Published	2018-04-14
URL	http://arxiv.org/abs/1804.05142v1
PDF	http://arxiv.org/pdf/1804.05142v1.pdf
PWC	https://paperswithcode.com/paper/hyperfusion-net-densely-reflective-fusion-for
Repo
Framework

Will it Blend? Composing Value Functions in Reinforcement Learning


Title	Will it Blend? Composing Value Functions in Reinforcement Learning
Authors	Benjamin van Niekerk, Steven James, Adam Earle, Benjamin Rosman
Abstract	An important property for lifelong-learning agents is the ability to combine existing skills to solve unseen tasks. In general, however, it is unclear how to compose skills in a principled way. We provide a “recipe” for optimal value function composition in entropy-regularised reinforcement learning (RL) and then extend this to the standard RL setting. Composition is demonstrated in a video game environment, where an agent with an existing library of policies is able to solve new tasks without the need for further learning.
Tasks
Published	2018-07-12
URL	http://arxiv.org/abs/1807.04439v1
PDF	http://arxiv.org/pdf/1807.04439v1.pdf
PWC	https://paperswithcode.com/paper/will-it-blend-composing-value-functions-in
Repo
Framework

Evorus: A Crowd-powered Conversational Assistant Built to Automate Itself Over Time


Title	Evorus: A Crowd-powered Conversational Assistant Built to Automate Itself Over Time
Authors	Ting-Hao ‘Kenneth’ Huang, Joseph Chee Chang, Jeffrey P. Bigham
Abstract	Crowd-powered conversational assistants have been shown to be more robust than automated systems, but do so at the cost of higher response latency and monetary costs. A promising direction is to combine the two approaches for high quality, low latency, and low cost solutions. In this paper, we introduce Evorus, a crowd-powered conversational assistant built to automate itself over time by (i) allowing new chatbots to be easily integrated to automate more scenarios, (ii) reusing prior crowd answers, and (iii) learning to automatically approve response candidates. Our 5-month-long deployment with 80 participants and 281 conversations shows that Evorus can automate itself without compromising conversation quality. Crowd-AI architectures have long been proposed as a way to reduce cost and latency for crowd-powered systems; Evorus demonstrates how automation can be introduced successfully in a deployed system. Its architecture allows future researchers to make further innovation on the underlying automated components in the context of a deployed open domain dialog system.
Tasks
Published	2018-01-08
URL	http://arxiv.org/abs/1801.02668v2
PDF	http://arxiv.org/pdf/1801.02668v2.pdf
PWC	https://paperswithcode.com/paper/evorus-a-crowd-powered-conversational
Repo
Framework

Entity Resolution and Federated Learning get a Federated Resolution


Title	Entity Resolution and Federated Learning get a Federated Resolution
Authors	Richard Nock, Stephen Hardy, Wilko Henecka, Hamish Ivey-Law, Giorgio Patrini, Guillaume Smith, Brian Thorne
Abstract	Consider two data providers, each maintaining records of different feature sets about common entities. They aim to learn a linear model over the whole set of features. This problem of federated learning over vertically partitioned data includes a crucial upstream issue: entity resolution, i.e. finding the correspondence between the rows of the datasets. It is well known that entity resolution, just like learning, is mistake-prone in the real world. Despite the importance of the problem, there has been no formal assessment of how errors in entity resolution impact learning. In this paper, we provide a thorough answer to this question, answering how optimal classifiers, empirical losses, margins and generalisation abilities are affected. While our answer spans a wide set of losses — going beyond proper, convex, or classification calibrated —, it brings simple practical arguments to upgrade entity resolution as a preprocessing step to learning. One of these suggests that entity resolution should be aimed at controlling or minimizing the number of matching errors between examples of distinct classes. In our experiments, we modify a simple token-based entity resolution algorithm so that it indeed aims at avoiding matching rows belonging to different classes, and perform experiments in the setting where entity resolution relies on noisy data, which is very relevant to real world domains. Notably, our approach covers the case where one peer \textit{does not} have classes, or a noisy record of classes. Experiments display that using the class information during entity resolution can buy significant uplift for learning at little expense from the complexity standpoint.
Tasks	Entity Resolution, Question Answering
Published	2018-03-11
URL	http://arxiv.org/abs/1803.04035v2
PDF	http://arxiv.org/pdf/1803.04035v2.pdf
PWC	https://paperswithcode.com/paper/entity-resolution-and-federated-learning-get
Repo
Framework

Finding Optimal Solutions to Token Swapping by Conflict-based Search and Reduction to SAT


Title	Finding Optimal Solutions to Token Swapping by Conflict-based Search and Reduction to SAT
Authors	Pavel Surynek
Abstract	We study practical approaches to solving the token swapping (TSWAP) problem optimally in this short paper. In TSWAP, we are given an undirected graph with colored vertices. A colored token is placed in each vertex. A pair of tokens can be swapped between adjacent vertices. The goal is to perform a sequence of swaps so that token and vertex colors agree across the graph. The minimum number of swaps is required in the optimization variant of the problem. We observed similarities between the TSWAP problem and multi-agent path finding (MAPF) where instead of tokens we have multiple agents that need to be moved from their current vertices to given unique target vertices. The difference between both problems consists in local conditions that state transitions (swaps/moves) must satisfy. We developed two algorithms for solving TSWAP optimally by adapting two different approaches to MAPF - CBS and MDD- SAT. This constitutes the first attempt to design optimal solving algorithms for TSWAP. Experimental evaluation on various types of graphs shows that the reduction to SAT scales better than CBS in optimal TSWAP solving.
Tasks	Multi-Agent Path Finding
Published	2018-06-25
URL	http://arxiv.org/abs/1806.09487v1
PDF	http://arxiv.org/pdf/1806.09487v1.pdf
PWC	https://paperswithcode.com/paper/finding-optimal-solutions-to-token-swapping
Repo
Framework

Overcoming the vanishing gradient problem in plain recurrent networks


Title	Overcoming the vanishing gradient problem in plain recurrent networks
Authors	Yuhuang Hu, Adrian Huber, Jithendar Anumula, Shih-Chii Liu
Abstract	Plain recurrent networks greatly suffer from the vanishing gradient problem while Gated Neural Networks (GNNs) such as Long-short Term Memory (LSTM) and Gated Recurrent Unit (GRU) deliver promising results in many sequence learning tasks through sophisticated network designs. This paper shows how we can address this problem in a plain recurrent network by analyzing the gating mechanisms in GNNs. We propose a novel network called the Recurrent Identity Network (RIN) which allows a plain recurrent network to overcome the vanishing gradient problem while training very deep models without the use of gates. We compare this model with IRNNs and LSTMs on multiple sequence modeling benchmarks. The RINs demonstrate competitive performance and converge faster in all tasks. Notably, small RIN models produce 12%–67% higher accuracy on the Sequential and Permuted MNIST datasets and reach state-of-the-art performance on the bAbI question answering dataset.
Tasks	Question Answering
Published	2018-01-18
URL	https://arxiv.org/abs/1801.06105v3
PDF	https://arxiv.org/pdf/1801.06105v3.pdf
PWC	https://paperswithcode.com/paper/overcoming-the-vanishing-gradient-problem-in
Repo
Framework

Multi-Agent Path Finding with Deadlines


Title	Multi-Agent Path Finding with Deadlines
Authors	Hang Ma, Glenn Wagner, Ariel Felner, Jiaoyang Li, T. K. Satish Kumar, Sven Koenig
Abstract	We formalize Multi-Agent Path Finding with Deadlines (MAPF-DL). The objective is to maximize the number of agents that can reach their given goal vertices from their given start vertices within the deadline, without colliding with each other. We first show that MAPF-DL is NP-hard to solve optimally. We then present two classes of optimal algorithms, one based on a reduction of MAPF-DL to a flow problem and a subsequent compact integer linear programming formulation of the resulting reduced abstracted multi-commodity flow network and the other one based on novel combinatorial search algorithms. Our empirical results demonstrate that these MAPF-DL solvers scale well and each one dominates the other ones in different scenarios.
Tasks	Multi-Agent Path Finding
Published	2018-06-11
URL	http://arxiv.org/abs/1806.04216v1
PDF	http://arxiv.org/pdf/1806.04216v1.pdf
PWC	https://paperswithcode.com/paper/multi-agent-path-finding-with-deadlines
Repo
Framework

Efficient Reciprocal Collision Avoidance between Heterogeneous Agents Using CTMAT


Title	Efficient Reciprocal Collision Avoidance between Heterogeneous Agents Using CTMAT
Authors	Yuexin Ma, Dinesh Manocha, Wenping Wang
Abstract	We present a novel algorithm for reciprocal collision avoidance between heterogeneous agents of different shapes and sizes. We present a novel CTMAT representation based on medial axis transform to compute a tight fitting bounding shape for each agent. Each CTMAT is represented using tuples, which are composed of circular arcs and line segments. Based on the reciprocal velocity obstacle formulation, we reduce the problem to solving a low-dimensional linear programming between each pair of tuples belonging to adjacent agents. We precompute the Minkowski Sums of tuples to accelerate the runtime performance. Finally, we provide an efficient method to update the orientation of each agent in a local manner. We have implemented the algorithm and highlight its performance on benchmarks corresponding to road traffic scenarios and different vehicles. The overall runtime performance is comparable to prior multi-agent collision avoidance algorithms that use circular or elliptical agents. Our approach is less conservative and results in fewer false collisions.
Tasks
Published	2018-04-07
URL	http://arxiv.org/abs/1804.02512v1
PDF	http://arxiv.org/pdf/1804.02512v1.pdf
PWC	https://paperswithcode.com/paper/efficient-reciprocal-collision-avoidance
Repo
Framework

Stripe-Based Fragility Analysis of Concrete Bridge Classes Using Machine Learning Techniques


Title	Stripe-Based Fragility Analysis of Concrete Bridge Classes Using Machine Learning Techniques
Authors	Sujith Mangalathu, Jong-Su Jeon
Abstract	A framework for the generation of bridge-specific fragility utilizing the capabilities of machine learning and stripe-based approach is presented in this paper. The proposed methodology using random forests helps to generate or update fragility curves for a new set of input parameters with less computational effort and expensive re-simulation. The methodology does not place any assumptions on the demand model of various components and helps to identify the relative importance of each uncertain variable in their seismic demand model. The methodology is demonstrated through the case studies of multi-span concrete bridges in California. Geometric, material and structural uncertainties are accounted for in the generation of bridge models and fragility curves. It is also noted that the traditional lognormality assumption on the demand model leads to unrealistic fragility estimates. Fragility results obtained the proposed methodology curves can be deployed in risk assessment platform such as HAZUS for regional loss estimation.
Tasks
Published	2018-07-25
URL	http://arxiv.org/abs/1807.09761v1
PDF	http://arxiv.org/pdf/1807.09761v1.pdf
PWC	https://paperswithcode.com/paper/stripe-based-fragility-analysis-of-concrete
Repo
Framework

Utilizing Smartphone-Based Machine Learning in Medical Monitor Data Collection: Seven Segment Digit Recognition


Title	Utilizing Smartphone-Based Machine Learning in Medical Monitor Data Collection: Seven Segment Digit Recognition
Authors	Varun N. Shenoy, Oliver O. Aalami
Abstract	Biometric measurements captured from medical devices, such as blood pressure gauges, glucose monitors, and weighing scales, are essential to tracking a patient’s health. Trends in these measurements can accurately track diabetes, cardiovascular issues, and assist medication management for patients. Currently, patients record their results and data of measurement in a physical notebook. It may be weeks before a doctor sees a patient’s records and can assess the health of the patient. With a predicted 6.8 billion smartphones in the world by 2022, health monitoring platforms, such as Apple’s HealthKit, can be leveraged to provide the right care at the right time. This research presents a mobile application that enables users to capture medical monitor data and send it to their doctor swiftly. A key contribution of this paper is a robust engine that can recognize digits from medical monitors with an accuracy of 98.2%.
Tasks
Published	2018-07-13
URL	http://arxiv.org/abs/1807.04888v1
PDF	http://arxiv.org/pdf/1807.04888v1.pdf
PWC	https://paperswithcode.com/paper/utilizing-smartphone-based-machine-learning
Repo
Framework

Chore division on a graph


Title	Chore division on a graph
Authors	Sylvain Bouveret, Katarína Cechlárová, Julien Lesca
Abstract	The paper considers fair allocation of indivisible nondisposable items that generate disutility (chores). We assume that these items are placed in the vertices of a graph and each agent’s share has to form a connected subgraph of this graph. Although a similar model has been investigated before for goods, we show that the goods and chores settings are inherently different. In particular, it is impossible to derive the solution of the chores instance from the solution of its naturally associated fair division instance. We consider three common fair division solution concepts, namely proportionality, envy-freeness and equitability, and two individual disutility aggregation functions: additive and maximum based. We show that deciding the existence of a fair allocation is hard even if the underlying graph is a path or a star. We also present some efficiently solvable special cases for these graph topologies.
Tasks
Published	2018-12-05
URL	http://arxiv.org/abs/1812.01856v1
PDF	http://arxiv.org/pdf/1812.01856v1.pdf
PWC	https://paperswithcode.com/paper/chore-division-on-a-graph
Repo
Framework