April 3, 2020

3250 words 16 mins read

Paper Group ANR 79

Unsupervised Competitive Hardware Learning Rule for Spintronic Clustering Architecture. Influence Function based Data Poisoning Attacks to Top-N Recommender Systems. Woodbury Transformations for Deep Generative Flows. Improved Optimistic Algorithms for Logistic Bandits. Deep Reinforcement Learning-Based Beam Tracking for Low-Latency Services in Veh …

Unsupervised Competitive Hardware Learning Rule for Spintronic Clustering Architecture


Title	Unsupervised Competitive Hardware Learning Rule for Spintronic Clustering Architecture
Authors	Alvaro Velasquez, Christopher H. Bennett, Naimul Hassan, Wesley H. Brigner, Otitoaleke G. Akinola, Jean Anne C. Incorvia, Matthew J. Marinella, Joseph S. Friedman
Abstract	We propose a hardware learning rule for unsupervised clustering within a novel spintronic computing architecture. The proposed approach leverages the three-terminal structure of domain-wall magnetic tunnel junction devices to establish a feedback loop that serves to train such devices when they are used as synapses in a neuromorphic computing architecture.
Tasks
Published	2020-03-24
URL	https://arxiv.org/abs/2003.11120v1
PDF	https://arxiv.org/pdf/2003.11120v1.pdf
PWC	https://paperswithcode.com/paper/unsupervised-competitive-hardware-learning
Repo
Framework

Influence Function based Data Poisoning Attacks to Top-N Recommender Systems


Title	Influence Function based Data Poisoning Attacks to Top-N Recommender Systems
Authors	Minghong Fang, Neil Zhenqiang Gong, Jia Liu
Abstract	Recommender system is an essential component of web services to engage users. Popular recommender systems model user preferences and item properties using a large amount of crowdsourced user-item interaction data, e.g., rating scores; then top-$N$ items that match the best with a user’s preference are recommended to the user. In this work, we show that an attacker can launch a data poisoning attack to a recommender system to make recommendations as the attacker desires via injecting fake users with carefully crafted user-item interaction data. Specifically, an attacker can trick a recommender system to recommend a target item to as many normal users as possible. We focus on matrix factorization based recommender systems because they have been widely deployed in industry. Given the number of fake users the attacker can inject, we formulate the crafting of rating scores for the fake users as an optimization problem. However, this optimization problem is challenging to solve as it is a non-convex integer programming problem. To address the challenge, we develop several techniques to approximately solve the optimization problem. For instance, we leverage influence function to select a subset of normal users who are influential to the recommendations and solve our formulated optimization problem based on these influential users. Our results show that our attacks are effective and outperform existing methods.
Tasks	data poisoning, Recommendation Systems
Published	2020-02-19
URL	https://arxiv.org/abs/2002.08025v2
PDF	https://arxiv.org/pdf/2002.08025v2.pdf
PWC	https://paperswithcode.com/paper/influence-function-based-data-poisoning
Repo
Framework

Woodbury Transformations for Deep Generative Flows


Title	Woodbury Transformations for Deep Generative Flows
Authors	You Lu, Bert Huang
Abstract	Normalizing flows are deep generative models that allow efficient likelihood calculation and sampling. The core requirement for this advantage is that they are constructed using functions that can be efficiently inverted and for which the determinant of the function’s Jacobian can be efficiently computed. Researchers have introduced various such flow operations, but few of these allow rich interactions among variables without incurring significant computational costs. In this paper, we introduce Woodbury transformations, which achieve efficient invertibility via the Woodbury matrix identity and efficient determinant calculation via Sylvester’s determinant identity. In contrast with other operations used in state-of-the-art normalizing flows, Woodbury transformations enable (1) high-dimensional interactions, (2) efficient sampling, and (3) efficient likelihood evaluation. Other similar operations, such as 1x1 convolutions, emerging convolutions, or periodic convolutions allow at most two of these three advantages. In our experiments on multiple image datasets, we find that Woodbury transformations allow learning of higher-likelihood models than other flow architectures while still enjoying their efficiency advantages.
Tasks
Published	2020-02-27
URL	https://arxiv.org/abs/2002.12229v1
PDF	https://arxiv.org/pdf/2002.12229v1.pdf
PWC	https://paperswithcode.com/paper/woodbury-transformations-for-deep-generative
Repo
Framework

Improved Optimistic Algorithms for Logistic Bandits


Title	Improved Optimistic Algorithms for Logistic Bandits
Authors	Louis Faury, Marc Abeille, Clément Calauzènes, Olivier Fercoq
Abstract	The generalized linear bandit framework has attracted a lot of attention in recent years by extending the well-understood linear setting and allowing to model richer reward structures. It notably covers the logistic model, widely used when rewards are binary. For logistic bandits, the frequentist regret guarantees of existing algorithms are $\tilde{\mathcal{O}}(\kappa \sqrt{T})$, where $\kappa$ is a problem-dependent constant. Unfortunately, $\kappa$ can be arbitrarily large as it scales exponentially with the size of the decision set. This may lead to significantly loose regret bounds and poor empirical performance. In this work, we study the logistic bandit with a focus on the prohibitive dependencies introduced by $\kappa$. We propose a new optimistic algorithm based on a finer examination of the non-linearities of the reward function. We show that it enjoys a $\tilde{\mathcal{O}}(\sqrt{T})$ regret with no dependency in $\kappa$, but for a second order term. Our analysis is based on a new tail-inequality for self-normalized martingales, of independent interest.
Tasks
Published	2020-02-18
URL	https://arxiv.org/abs/2002.07530v1
PDF	https://arxiv.org/pdf/2002.07530v1.pdf
PWC	https://paperswithcode.com/paper/improved-optimistic-algorithms-for-logistic
Repo
Framework

Deep Reinforcement Learning-Based Beam Tracking for Low-Latency Services in Vehicular Networks


Title	Deep Reinforcement Learning-Based Beam Tracking for Low-Latency Services in Vehicular Networks
Authors	Yan Liu, Zhiyuan Jiang, Shunqing Zhang, Shugong Xu
Abstract	Ultra-Reliable and Low-Latency Communications (URLLC) services in vehicular networks on millimeter-wave bands present a significant challenge, considering the necessity of constantly adjusting the beam directions. Conventional methods are mostly based on classical control theory, e.g., Kalman filter and its variations, which mainly deal with stationary scenarios. Therefore, severe application limitations exist, especially with complicated, dynamic Vehicle-to-Everything (V2X) channels. This paper gives a thorough study of this subject, by first modifying the classical approaches, e.g., Extended Kalman Filter (EKF) and Particle Filter (PF), for non-stationary scenarios, and then proposing a Reinforcement Learning (RL)-based approach that can achieve the URLLC requirements in a typical intersection scenario. Simulation results based on a commercial ray-tracing simulator show that enhanced EKF and PF methods achieve packet delay more than $10$ ms, whereas the proposed deep RL-based method can reduce the latency to about $6$ ms, by extracting context information from the training data.
Tasks
Published	2020-02-13
URL	https://arxiv.org/abs/2002.05564v1
PDF	https://arxiv.org/pdf/2002.05564v1.pdf
PWC	https://paperswithcode.com/paper/deep-reinforcement-learning-based-beam
Repo
Framework

Discrete Signal Processing with Set Functions


Title	Discrete Signal Processing with Set Functions
Authors	Markus Püschel, Chris Wendler
Abstract	Set functions are functions (or signals) indexed by the power set (set of all subsets) of a finite set $N$. They are ubiquitous in many application domains. For example, they are equivalent to node- or edge-weighted hypergraphs and to cooperative games in game theory. Further, the subclass of submodular functions occurs in many optimization and machine learning problems. In this paper, we derive discrete-set signal processing (SP), a shift-invariant linear signal processing framework for set functions. Discrete-set SP provides suitable definitions of shift, shift-invariant systems, convolution, Fourier transform, frequency response, and other SP concepts. Different variants are possible due to different possible shifts. Discrete-set SP is inherently different from graph SP as it distinguishes the neighbors of an index $A\subseteq N$, i.e., those with one elements more or less by providing $n = N$ shifts. Finally, we show three prototypical applications and experiments with discrete-set SP including compression in submodular function optimization, sampling for preference elicitation in auctions, and novel power set neural networks.
Tasks
Published	2020-01-28
URL	https://arxiv.org/abs/2001.10290v1
PDF	https://arxiv.org/pdf/2001.10290v1.pdf
PWC	https://paperswithcode.com/paper/discrete-signal-processing-with-set-functions
Repo
Framework

What went wrong and when? Instance-wise Feature Importance for Time-series Models


Title	What went wrong and when? Instance-wise Feature Importance for Time-series Models
Authors	Sana Tonekaboni, Shalmali Joshi, David Duvenaud, Anna Goldenberg
Abstract	Multivariate time series models are poised to be used for decision support in high-stakes applications, such as healthcare. In these contexts, it is important to know which features at which times most influenced a prediction. We demonstrate a general approach for assigning importance to observations in multivariate time series, based on their counterfactual influence on future predictions. Specifically, we define the importance of an observation as the change in the predictive distribution, had the observation not been seen. We integrate over plausible counterfactuals by sampling from the corresponding conditional distributions of generative time series models. We compare our importance metric to gradient-based explanations, attention mechanisms, and other baselines in simulated and clinical ICU data, and show that our approach generates the most precise explanations. Our method is inexpensive, model agnostic, and can be used with arbitrarily complex time series models and predictors.
Tasks	Feature Importance, Time Series
Published	2020-03-05
URL	https://arxiv.org/abs/2003.02821v1
PDF	https://arxiv.org/pdf/2003.02821v1.pdf
PWC	https://paperswithcode.com/paper/what-went-wrong-and-when-instance-wise
Repo
Framework

A Novel Decision Tree for Depression Recognition in Speech


Title	A Novel Decision Tree for Depression Recognition in Speech
Authors	Zhenyu Liu, Dongyu Wang, Lan Zhang, Bin Hu
Abstract	Depression is a common mental disorder worldwide which causes a range of serious outcomes. The diagnosis of depression relies on patient-reported scales and psychiatrist interview which may lead to subjective bias. In recent years, more and more researchers are devoted to depression recognition in speech , which may be an effective and objective indicator. This study proposes a new speech segment fusion method based on decision tree to improve the depression recognition accuracy and conducts a validation on a sample of 52 subjects (23 depressed patients and 29 healthy controls). The recognition accuracy are 75.8% and 68.5% for male and female respectively on gender-dependent models. It can be concluded from the data that the proposed decision tree model can improve the depression classification performance.
Tasks
Published	2020-02-22
URL	https://arxiv.org/abs/2002.12759v1
PDF	https://arxiv.org/pdf/2002.12759v1.pdf
PWC	https://paperswithcode.com/paper/a-novel-decision-tree-for-depression
Repo
Framework

Robust Stochastic Bandit Algorithms under Probabilistic Unbounded Adversarial Attack


Title	Robust Stochastic Bandit Algorithms under Probabilistic Unbounded Adversarial Attack
Authors	Ziwei Guan, Kaiyi Ji, Donald J Bucci Jr, Timothy Y Hu, Joseph Palombo, Michael Liston, Yingbin Liang
Abstract	The multi-armed bandit formalism has been extensively studied under various attack models, in which an adversary can modify the reward revealed to the player. Previous studies focused on scenarios where the attack value either is bounded at each round or has a vanishing probability of occurrence. These models do not capture powerful adversaries that can catastrophically perturb the revealed reward. This paper investigates the attack model where an adversary attacks with a certain probability at each round, and its attack value can be arbitrary and unbounded if it attacks. Furthermore, the attack value does not necessarily follow a statistical distribution. We propose a novel sample median-based and exploration-aided UCB algorithm (called med-E-UCB) and a median-based $\epsilon$-greedy algorithm (called med-$\epsilon$-greedy). Both of these algorithms are provably robust to the aforementioned attack model. More specifically we show that both algorithms achieve $\mathcal{O}(\log T)$ pseudo-regret (i.e., the optimal regret without attacks). We also provide a high probability guarantee of $\mathcal{O}(\log T)$ regret with respect to random rewards and random occurrence of attacks. These bounds are achieved under arbitrary and unbounded reward perturbation as long as the attack probability does not exceed a certain constant threshold. We provide multiple synthetic simulations of the proposed algorithms to verify these claims and showcase the inability of existing techniques to achieve sublinear regret. We also provide experimental results of the algorithm operating in a cognitive radio setting using multiple software-defined radios.
Tasks	Adversarial Attack
Published	2020-02-17
URL	https://arxiv.org/abs/2002.07214v1
PDF	https://arxiv.org/pdf/2002.07214v1.pdf
PWC	https://paperswithcode.com/paper/robust-stochastic-bandit-algorithms-under
Repo
Framework

FineHand: Learning Hand Shapes for American Sign Language Recognition


Title	FineHand: Learning Hand Shapes for American Sign Language Recognition
Authors	Al Amin Hosain, Panneer Selvam Santhalingam, Parth Pathak, Huzefa Rangwala, Jana Kosecka
Abstract	American Sign Language recognition is a difficult gesture recognition problem, characterized by fast, highly articulate gestures. These are comprised of arm movements with different hand shapes, facial expression and head movements. Among these components, hand shape is the vital, often the most discriminative part of a gesture. In this work, we present an approach for effective learning of hand shape embeddings, which are discriminative for ASL gestures. For hand shape recognition our method uses a mix of manually labelled hand shapes and high confidence predictions to train deep convolutional neural network (CNN). The sequential gesture component is captured by recursive neural network (RNN) trained on the embeddings learned in the first stage. We will demonstrate that higher quality hand shape models can significantly improve the accuracy of final video gesture classification in challenging conditions with variety of speakers, different illumination and significant motion blurr. We compare our model to alternative approaches exploiting different modalities and representations of the data and show improved video gesture recognition accuracy on GMU-ASL51 benchmark dataset
Tasks	Gesture Recognition, Sign Language Recognition
Published	2020-03-04
URL	https://arxiv.org/abs/2003.08753v1
PDF	https://arxiv.org/pdf/2003.08753v1.pdf
PWC	https://paperswithcode.com/paper/finehand-learning-hand-shapes-for-american
Repo
Framework

Fundamental Limits of Testing the Independence of Irrelevant Alternatives in Discrete Choice


Title	Fundamental Limits of Testing the Independence of Irrelevant Alternatives in Discrete Choice
Authors	Arjun Seshadri, Johan Ugander
Abstract	The Multinomial Logit (MNL) model and the axiom it satisfies, the Independence of Irrelevant Alternatives (IIA), are together the most widely used tools of discrete choice. The MNL model serves as the workhorse model for a variety of fields, but is also widely criticized, with a large body of experimental literature claiming to document real-world settings where IIA fails to hold. Statistical tests of IIA as a modelling assumption have been the subject of many practical tests focusing on specific deviations from IIA over the past several decades, but the formal size properties of hypothesis testing IIA are still not well understood. In this work we replace some of the ambiguity in this literature with rigorous pessimism, demonstrating that any general test for IIA with low worst-case error would require a number of samples exponential in the number of alternatives of the choice problem. A major benefit of our analysis over previous work is that it lies entirely in the finite-sample domain, a feature crucial to understanding the behavior of tests in the common data-poor settings of discrete choice. Our lower bounds are structure-dependent, and as a potential cause for optimism, we find that if one restricts the test of IIA to violations that can occur in a specific collection of choice sets (e.g., pairs), one obtains structure-dependent lower bounds that are much less pessimistic. Our analysis of this testing problem is unorthodox in being highly combinatorial, counting Eulerian orientations of cycle decompositions of a particular bipartite graph constructed from a data set of choices. By identifying fundamental relationships between the comparison structure of a given testing problem and its sample efficiency, we hope these relationships will help lay the groundwork for a rigorous rethinking of the IIA testing problem as well as other testing problems in discrete choice.
Tasks
Published	2020-01-20
URL	https://arxiv.org/abs/2001.07042v1
PDF	https://arxiv.org/pdf/2001.07042v1.pdf
PWC	https://paperswithcode.com/paper/fundamental-limits-of-testing-the
Repo
Framework

Approximate Aggregate Queries Under Additive Inequalities


Title	Approximate Aggregate Queries Under Additive Inequalities
Authors	Mahmoud Abo-Khamis, Sungjin Im, Benjamin Moseley, Kirk Pruhs, Alireza Samadian
Abstract	We consider the problem of evaluating an aggregation query, which is a sum-of-sum query or a sum-of-product query, subject to additive inequalities. Such aggregation queries, with a smallish number of additive inequalities, arise naturally/commonly in many applications, particularly in machine learning applications. We give a relatively complete categorization of the computational complexity of such problems. We first show that the problem is NP-hard, even in the case of one additive inequality. Thus we turn to approximating the query. Our main result is an efficient algorithm for approximating, with arbitrarily small relative error, many natural aggregation queries with one additive inequality. We give examples of natural queries that can be efficiently solved using this algorithm. In contrast we show that the situation with two additive inequalities is quite different, by showing that it is NP-hard to evaluate simple aggregation queries, with two additive inequalities, with any bounded relative error. We end by considering the problem of computing the gradient of the objective function in the Support Vector Machines (SVM) problem, a canonical machine learning problem. While computing the gradient for SVM can be reduced to the problem of computing an aggregation query with one additive inequality, our algorithm is not applicable due to what we call the ``subtraction problem’'. However, we show how to circumvent this subtraction problem within the context of SVM to obtain a gradient-descent algorithm that will result in an approximately correct optimal solution, using an alternative notion of approximate correctness, which may be of independent interest. \|
Tasks
Published	2020-03-24
URL	https://arxiv.org/abs/2003.10588v1
PDF	https://arxiv.org/pdf/2003.10588v1.pdf
PWC	https://paperswithcode.com/paper/approximate-aggregate-queries-under-additive
Repo
Framework

Diagnosis of Diabetic Retinopathy in Ethiopia: Before the Deep Learning based Automation


Title	Diagnosis of Diabetic Retinopathy in Ethiopia: Before the Deep Learning based Automation
Authors	Misgina Tsighe Hagos
Abstract	Introducing automated Diabetic Retinopathy (DR) diagnosis into Ethiopia is still a challenging task, despite recent reports that present trained Deep Learning (DL) based DR classifiers surpassing manual graders. This is mainly because of the expensive cost of conventional retinal imaging devices used in DL based classifiers. Current approaches that provide mobile based binary classification of DR, and the way towards a cheaper and offline multi-class classification of DR will be discussed in this paper.
Tasks
Published	2020-03-20
URL	https://arxiv.org/abs/2003.09208v1
PDF	https://arxiv.org/pdf/2003.09208v1.pdf
PWC	https://paperswithcode.com/paper/diagnosis-of-diabetic-retinopathy-in-ethiopia
Repo
Framework

Fast Implementation of Morphological Filtering Using ARM NEON Extension


Title	Fast Implementation of Morphological Filtering Using ARM NEON Extension
Authors	Elena Limonova, Arseny Terekhin, Dmitry Nikolaev, Vladimir Arlazarov
Abstract	In this paper we consider speedup potential of morphological image filtering on ARM processors. Morphological operations are widely used in image analysis and recognition and their speedup in some cases can significantly reduce overall execution time of recognition. More specifically, we propose fast implementation of erosion and dilation using ARM SIMD extension NEON. These operations with the rectangular structuring element are separable. They were implemented using the advantages of separability as sequential horizontal and vertical passes. Each pass was implemented using van Herk/Gil-Werman algorithm for large windows and low-constant linear complexity algorithm for small windows. Final implementation was improved with SIMD and used a combination of these methods. We also considered fast transpose implementation of 8x8 and 16x16 matrices using ARM NEON to get additional computational gain for morphological operations. Experiments showed 3 times efficiency increase for final implementation of erosion and dilation compared to van Herk/Gil-Werman algorithm without SIMD, 5.7 times speedup for 8x8 matrix transpose and 12 times speedup for 16x16 matrix transpose compared to transpose without SIMD.
Tasks
Published	2020-02-19
URL	https://arxiv.org/abs/2002.09474v1
PDF	https://arxiv.org/pdf/2002.09474v1.pdf
PWC	https://paperswithcode.com/paper/fast-implementation-of-morphological
Repo
Framework

A Unified Conversational Assistant Framework for Business Process Automation


Title	A Unified Conversational Assistant Framework for Business Process Automation
Authors	Yara Rizk, Abhishek Bhandwalder, Scott Boag, Tathagata Chakraborti, Vatche Isahagian, Yasaman Khazaeni, Falk Pollock, Merve Unuvar
Abstract	Business process automation is a booming multi-billion-dollar industry that promises to remove menial tasks from workers’ plates – through the introduction of autonomous agents – and free up their time and brain power for more creative and engaging tasks. However, an essential component to the successful deployment of such autonomous agents is the ability of business users to monitor their performance and customize their execution. A simple and user-friendly interface with a low learning curve is necessary to increase the adoption of such agents in banking, insurance, retail and other domains. As a result, proactive chatbots will play a crucial role in the business automation space. Not only can they respond to users’ queries and perform actions on their behalf but also initiate communication with the users to inform them of the system’s behavior. This will provide business users a natural language interface to interact with, monitor and control autonomous agents. In this work, we present a multi-agent orchestration framework to develop such proactive chatbots by discussing the types of skills that can be composed into agents and how to orchestrate these agents. Two use cases on a travel preapproval business process and a loan application business process are adopted to qualitatively analyze the proposed framework based on four criteria: performance, coding overhead, scalability, and agent overlap.
Tasks
Published	2020-01-07
URL	https://arxiv.org/abs/2001.03543v1
PDF	https://arxiv.org/pdf/2001.03543v1.pdf
PWC	https://paperswithcode.com/paper/a-unified-conversational-assistant-framework
Repo
Framework