October 19, 2019

3787 words 18 mins read

Paper Group ANR 209

Paper Group ANR 209

Towards a Zero-One Law for Entrywise Low Rank Approximation. An Unified Intelligence-Communication Model for Multi-Agent System Part-I: Overview. MetaStyle: Three-Way Trade-Off Among Speed, Flexibility, and Quality in Neural Style Transfer. Understand, Compose and Respond - Answering Visual Questions by a Composition of Abstract Procedures. Joint S …

Towards a Zero-One Law for Entrywise Low Rank Approximation

Title Towards a Zero-One Law for Entrywise Low Rank Approximation
Authors Zhao Song, David P. Woodruff, Peilin Zhong
Abstract There are a number of approximation algorithms for NP-hard versions of low rank approximation, such as finding a rank-$k$ matrix $B$ minimizing the sum of absolute values of differences to a given matrix $A$, $\min_{\textrm{rank-}k~B}\A-B_1$, or more generally finding a rank-$k$ matrix $B$ which minimizes the sum of $p$-th powers of absolute values of differences, $\min_{\textrm{rank-}k~B}\A-B_p^p$. Many of these algorithms are linear time columns subset selection algorithms, returning a subset of ${\rm{poly}}(k\log n)$ columns whose cost is no more than a ${\rm{poly}}(k)$ factor larger than the cost of the best rank-$k$ matrix. The above error measures are special cases of the following general entrywise low rank approximation problem: given an arbitrary function $g:\mathbb{R}\rightarrow\mathbb{R}_{\geq0}$, find a rank-$k$ matrix $B$ which minimizes $\A-B_g=\sum_{i,j}g(A_{i,j}-B_{i,j})$. A natural question is which functions $g$ admit efficient approximation algorithms? Indeed, this is a central question of recent work studying generalized low rank models. We give approximation algorithms for every function $g$ which is approximately monotone and satisfies an approximate triangle inequality, and we show both of these conditions are necessary. Further, our algorithm is efficient if the function $g$ admits an efficient approximate regression algorithm. Our algorithm handles functions which are not even scale-invariant, such as the Huber loss function. Our algorithms have ${\rm{poly}}(k)$-approximation ratio in general. We further improve the approximation ratio to (1+$\epsilon$) for $\ell_1$ loss when the entries of the error matrix are i.i.d. random variables drawn from a distribution $\mu$ of which (1+$\gamma$) moment exists, for an arbitrary small constant $\gamma>0$. We also show our moment assumption is necessary.
Tasks
Published 2018-11-04
URL http://arxiv.org/abs/1811.01442v1
PDF http://arxiv.org/pdf/1811.01442v1.pdf
PWC https://paperswithcode.com/paper/towards-a-zero-one-law-for-entrywise-low-rank
Repo
Framework

An Unified Intelligence-Communication Model for Multi-Agent System Part-I: Overview

Title An Unified Intelligence-Communication Model for Multi-Agent System Part-I: Overview
Authors Bo Zhang, Bin Chen, Jinyu Yang, Wenjing Yang, Jiankang Zhang
Abstract Motivated by Shannon’s model and recent rehabilitation of self-supervised artificial intelligence having a “World Model”, this paper propose an unified intelligence-communication (UIC) model for describing a single agent and any multi-agent system. Firstly, the environment is modelled as the generic communication channel between agents. Secondly, the UIC model adopts a learning-agent model for unifying several well-adopted agent architecture, e.g. rule-based agent model in complex adaptive systems, layered model for describing human-level intelligence, world-model based agent model. The model may also provide an unified approach to investigate a multi-agent system (MAS) having multiple action-perception modalities, e.g. explicitly information transfer and implicit information transfer. This treatise would be divided into three parts, and this first part provides an overview of the UIC model without introducing cumbersome mathematical analysis and optimizations. In the second part of this treatise, case studies with quantitative analysis driven by the UIC model would be provided, exemplifying the adoption of the UIC model in multi-agent system. Specifically, two representative cases would be studied, namely the analysis of a natural multi-agent system, as well as the co-design of communication, perception and action in an artificial multi-agent system. In the third part of this treatise, the paper provides further insights and future research directions motivated by the UIC model, such as unification of single intelligence and collective intelligence, a possible explanation of intelligence emergence and a dual model for agent-environment intelligence hypothesis. Notes: This paper is a Previewed Version, the extended full-version would be released after being accepted.
Tasks
Published 2018-11-25
URL http://arxiv.org/abs/1811.09920v1
PDF http://arxiv.org/pdf/1811.09920v1.pdf
PWC https://paperswithcode.com/paper/an-unified-intelligence-communication-model
Repo
Framework

MetaStyle: Three-Way Trade-Off Among Speed, Flexibility, and Quality in Neural Style Transfer

Title MetaStyle: Three-Way Trade-Off Among Speed, Flexibility, and Quality in Neural Style Transfer
Authors Chi Zhang, Yixin Zhu, Song-Chun Zhu
Abstract An unprecedented booming has been witnessed in the research area of artistic style transfer ever since Gatys et al. introduced the neural method. One of the remaining challenges is to balance a trade-off among three critical aspects—speed, flexibility, and quality: (i) the vanilla optimization-based algorithm produces impressive results for arbitrary styles, but is unsatisfyingly slow due to its iterative nature, (ii) the fast approximation methods based on feed-forward neural networks generate satisfactory artistic effects but bound to only a limited number of styles, and (iii) feature-matching methods like AdaIN achieve arbitrary style transfer in a real-time manner but at a cost of the compromised quality. We find it considerably difficult to balance the trade-off well merely using a single feed-forward step and ask, instead, whether there exists an algorithm that could adapt quickly to any style, while the adapted model maintains high efficiency and good image quality. Motivated by this idea, we propose a novel method, coined MetaStyle, which formulates the neural style transfer as a bilevel optimization problem and combines learning with only a few post-processing update steps to adapt to a fast approximation model with satisfying artistic effects, comparable to the optimization-based methods for an arbitrary style. The qualitative and quantitative analysis in the experiments demonstrates that the proposed approach achieves high-quality arbitrary artistic style transfer effectively, with a good trade-off among speed, flexibility, and quality.
Tasks bilevel optimization, Style Transfer
Published 2018-12-13
URL http://arxiv.org/abs/1812.05233v3
PDF http://arxiv.org/pdf/1812.05233v3.pdf
PWC https://paperswithcode.com/paper/metastyle-three-way-trade-off-among-speed
Repo
Framework

Understand, Compose and Respond - Answering Visual Questions by a Composition of Abstract Procedures

Title Understand, Compose and Respond - Answering Visual Questions by a Composition of Abstract Procedures
Authors Ben Zion Vatashsky, Shimon Ullman
Abstract An image related question defines a specific visual task that is required in order to produce an appropriate answer. The answer may depend on a minor detail in the image and require complex reasoning and use of prior knowledge. When humans perform this task, they are able to do it in a flexible and robust manner, integrating modularly any novel visual capability with diverse options for various elaborations of the task. In contrast, current approaches to solve this problem by a machine are based on casting the problem as an end-to-end learning problem, which lacks such abilities. We present a different approach, inspired by the aforementioned human capabilities. The approach is based on the compositional structure of the question. The underlying idea is that a question has an abstract representation based on its structure, which is compositional in nature. The question can consequently be answered by a composition of procedures corresponding to its substructures. The basic elements of the representation are logical patterns, which are put together to represent the question. These patterns include a parametric representation for object classes, properties and relations. Each basic pattern is mapped into a basic procedure that includes meaningful visual tasks, and the patterns are composed to produce the overall answering procedure. The UnCoRd (Understand Compose and Respond) system, based on this approach, integrates existing detection and classification schemes for a set of object classes, properties and relations. These schemes are incorporated in a modular manner, providing elaborated answers and corrections for negative answers. In addition, an external knowledge base is queried for required common-knowledge. We performed a qualitative analysis of the system, which demonstrates its representation capabilities and provide suggestions for future developments.
Tasks
Published 2018-10-25
URL http://arxiv.org/abs/1810.10656v1
PDF http://arxiv.org/pdf/1810.10656v1.pdf
PWC https://paperswithcode.com/paper/understand-compose-and-respond-answering
Repo
Framework

Joint Surgical Gesture and Task Classification with Multi-Task and Multimodal Learning

Title Joint Surgical Gesture and Task Classification with Multi-Task and Multimodal Learning
Authors Duygu Sarikaya, Khurshid A. Guru, Jason J. Corso
Abstract We propose a novel multi-modal and multi-task architecture for simultaneous low level gesture and surgical task classification in Robot Assisted Surgery (RAS) videos.Our end-to-end architecture is based on the principles of a long short-term memory network (LSTM) that jointly learns temporal dynamics on rich representations of visual and motion features, while simultaneously classifying activities of low-level gestures and surgical tasks. Our experimental results show that our approach is superior compared to an ar- chitecture that classifies the gestures and surgical tasks separately on visual cues and motion cues respectively. We train our model on a fixed random set of 1200 gesture video segments and use the rest 422 for testing. This results in around 42,000 gesture frames sampled for training and 14,500 for testing. For a 6 split experimentation, while the conventional approach reaches an Average Precision (AP) of only 29% (29.13%), our architecture reaches an AP of 51% (50.83%) for 3 tasks and 14 possible gesture labels, resulting in an improvement of 22% (21.7%). Our architecture learns temporal dynamics on rich representations of visual and motion features that compliment each other for classification of low-level gestures and surgical tasks. Its multi-task learning nature makes use of learned joint re- lationships and combinations of shared and task-specific representations. While benchmark studies focus on recognizing gestures that take place under specific tasks, we focus on recognizing common gestures that reoccur across different tasks and settings and significantly perform better compared to conventional architectures.
Tasks Multi-Task Learning
Published 2018-05-02
URL http://arxiv.org/abs/1805.00721v1
PDF http://arxiv.org/pdf/1805.00721v1.pdf
PWC https://paperswithcode.com/paper/joint-surgical-gesture-and-task
Repo
Framework

Fairness and Accountability Design Needs for Algorithmic Support in High-Stakes Public Sector Decision-Making

Title Fairness and Accountability Design Needs for Algorithmic Support in High-Stakes Public Sector Decision-Making
Authors Michael Veale, Max Van Kleek, Reuben Binns
Abstract Calls for heightened consideration of fairness and accountability in algorithmically-informed public decisions—like taxation, justice, and child protection—are now commonplace. How might designers support such human values? We interviewed 27 public sector machine learning practitioners across 5 OECD countries regarding challenges understanding and imbuing public values into their work. The results suggest a disconnect between organisational and institutional realities, constraints and needs, and those addressed by current research into usable, transparent and ‘discrimination-aware’ machine learning—absences likely to undermine practical initiatives unless addressed. We see design opportunities in this disconnect, such as in supporting the tracking of concept drift in secondary data sources, and in building usable transparency tools to identify risks and incorporate domain knowledge, aimed both at managers and at the ‘street-level bureaucrats’ on the frontlines of public service. We conclude by outlining ethical challenges and future directions for collaboration in these high-stakes applications.
Tasks Decision Making
Published 2018-02-03
URL http://arxiv.org/abs/1802.01029v1
PDF http://arxiv.org/pdf/1802.01029v1.pdf
PWC https://paperswithcode.com/paper/fairness-and-accountability-design-needs-for
Repo
Framework

Optimal Balancing of Time-Dependent Confounders for Marginal Structural Models

Title Optimal Balancing of Time-Dependent Confounders for Marginal Structural Models
Authors Nathan Kallus, Michele Santacatterina
Abstract Marginal structural models (MSMs) estimate the causal effect of a time-varying treatment in the presence of time-dependent confounding via weighted regression. The standard approach of using inverse probability of treatment weighting (IPTW) can lead to high-variance estimates due to extreme weights and be sensitive to model misspecification. Various methods have been proposed to partially address this, including truncation and stabilized-IPTW to temper extreme weights and covariate balancing propensity score (CBPS) to address treatment model misspecification. In this paper, we present Kernel Optimal Weighting (KOW), a convex-optimization-based approach that finds weights for fitting the MSM that optimally balance time-dependent confounders while simultaneously controlling for precision, directly addressing the above limitations. KOW directly minimizes the error in estimation due to time-dependent confounding via a new decomposition as a functional. We further extend KOW to control for informative censoring. We evaluate the performance of KOW in a simulation study, comparing it with IPTW, stabilized-IPTW, and CBPS. We demonstrate the use of KOW in studying the effect of treatment initiation on time-to-death among people living with HIV and the effect of negative advertising on elections in the United States.
Tasks
Published 2018-06-04
URL https://arxiv.org/abs/1806.01083v2
PDF https://arxiv.org/pdf/1806.01083v2.pdf
PWC https://paperswithcode.com/paper/optimal-balancing-of-time-dependent
Repo
Framework

Towards Gaussian Bayesian Network Fusion

Title Towards Gaussian Bayesian Network Fusion
Authors Irene Córdoba, Concha Bielza, Pedro Larrañaga
Abstract Data sets are growing in complexity thanks to the increasing facilities we have nowadays to both generate and store data. This poses many challenges to machine learning that are leading to the proposal of new methods and paradigms, in order to be able to deal with what is nowadays referred to as Big Data. In this paper we propose a method for the aggregation of different Bayesian network structures that have been learned from separate data sets, as a first step towards mining data sets that need to be partitioned in an horizontal way, i.e. with respect to the instances, in order to be processed. Considerations that should be taken into account when dealing with this situation are discussed. Scalable learning of Bayesian networks is slowly emerging, and our method constitutes one of the first insights into Gaussian Bayesian network aggregation from different sources. Tested on synthetic data it obtains good results that surpass those from individual learning. Future research will be focused on expanding the method and testing more diverse data sets.
Tasks
Published 2018-12-01
URL http://arxiv.org/abs/1812.00262v1
PDF http://arxiv.org/pdf/1812.00262v1.pdf
PWC https://paperswithcode.com/paper/towards-gaussian-bayesian-network-fusion
Repo
Framework

Generalized No Free Lunch Theorem for Adversarial Robustness

Title Generalized No Free Lunch Theorem for Adversarial Robustness
Authors Elvis Dohmatob
Abstract This manuscript presents some new impossibility results on adversarial robustness in machine learning, a very important yet largely open problem. We show that if conditioned on a class label the data distribution satisfies the $W_2$ Talagrand transportation-cost inequality (for example, this condition is satisfied if the conditional distribution has density which is log-concave; is the uniform measure on a compact Riemannian manifold with positive Ricci curvature, any classifier can be adversarially fooled with high probability once the perturbations are slightly greater than the natural noise level in the problem. We call this result The Strong “No Free Lunch” Theorem as some recent results (Tsipras et al. 2018, Fawzi et al. 2018, etc.) on the subject can be immediately recovered as very particular cases. Our theoretical bounds are demonstrated on both simulated and real data (MNIST). We conclude the manuscript with some speculation on possible future research directions.
Tasks
Published 2018-10-08
URL https://arxiv.org/abs/1810.04065v8
PDF https://arxiv.org/pdf/1810.04065v8.pdf
PWC https://paperswithcode.com/paper/limitations-of-adversarial-robustness-strong
Repo
Framework

Towards Adversarial Denoising of Radar Micro-Doppler Signatures

Title Towards Adversarial Denoising of Radar Micro-Doppler Signatures
Authors Sherif Abdulatif, Karim Armanious, Fady Aziz, Urs Schneider, Bin Yang
Abstract Generative Adversarial Networks (GANs) are considered the state-of-the-art in the field of image generation. They learn the joint distribution of the training data and attempt to generate new data samples in high dimensional space following the same distribution as the input. Recent improvements in GANs opened the field to many other computer vision applications based on improving and changing the characteristics of the input image to follow some given training requirements. In this paper, we propose a novel technique for the denoising and reconstruction of the micro-Doppler ($\boldsymbol{\mu}$-D) spectra of walking humans based on GANs. Two sets of experiments were collected on 22 subjects walking on a treadmill at an intermediate velocity using a \unit[25]{GHz} CW radar. In one set, a clean $\boldsymbol{\mu}$-D spectrum is collected for each subject by placing the radar at a close distance to the subject. In the other set, variations are introduced in the experiment setup to introduce different noise and clutter effects on the spectrum by changing the distance and placing reflective objects between the radar and the target. Synthetic paired noisy and noise-free spectra were used for training, while validation was carried out on the real noisy measured data. Finally, qualitative and quantitative comparison with other classical radar denoising approaches in the literature demonstrated the proposed GANs framework is better and more robust to different noise levels.
Tasks Denoising, Denoising Of Radar Micro-Doppler Signatures, Image Generation
Published 2018-11-12
URL https://arxiv.org/abs/1811.04678v3
PDF https://arxiv.org/pdf/1811.04678v3.pdf
PWC https://paperswithcode.com/paper/towards-adversarial-denoising-of-radar-micro
Repo
Framework

Quantum dynamical mode (QDM): A possible extension of belief function

Title Quantum dynamical mode (QDM): A possible extension of belief function
Authors Fuyuan Xiao
Abstract Dempster-Shafer evidence theory has been widely used in various fields of applications, because of the flexibility and effectiveness in modeling uncertainties without prior information. Besides, it has been proven that the quantum theory has powerful capabilities of solving the decision making problems, especially for modelling human decision and cognition. However, the classical Dempster-Shafer evidence theory modelled by real numbers cannot be integrated directly with the quantum theory modelled by complex numbers. So, how can we establish a bridge of communications between the classical Dempster-Shafer evidence theory and the quantum theory? To answer this question, a generalized Dempster-Shafer evidence theory is proposed in this paper. The main contribution in this study is that, unlike the existing evidence theory, a mass function in the generalized Dempster-Shafer evidence theory is modelled by a complex number, called as a complex mass function. In addition, compared with the classical Dempster’s combination rule, the condition in terms of the conflict coefficient between two evidences K < 1 is released in the generalized Dempster’s combination rule so that it is more general and applicable than the classical Dempster’s combination rule. When the complex mass function is degenerated from complex numbers to real numbers, the generalized Dempster’s combination rule degenerates to the classical evidence theory under the condition that the conflict coefficient between the evidences K is less than 1. Numerical examples are illustrated to show the efficiency of the generalized Dempster-Shafer evidence theory. Finally, an application of an evidential quantum dynamical model is implemented by integrating the generalized Dempster-Shafer evidence theory with the quantum dynamical model. From the experimental results, it validates the feasibility and effectiveness of the proposed method.
Tasks Decision Making
Published 2018-01-16
URL http://arxiv.org/abs/1801.05707v3
PDF http://arxiv.org/pdf/1801.05707v3.pdf
PWC https://paperswithcode.com/paper/quantum-dynamical-mode-qdm-a-possible
Repo
Framework

A Directionally Selective Neural Network with Separated ON and OFF Pathways for Translational Motion Perception in a Visually Cluttered Environment

Title A Directionally Selective Neural Network with Separated ON and OFF Pathways for Translational Motion Perception in a Visually Cluttered Environment
Authors Qinbing Fu, Nicola Bellotto, Shigang Yue
Abstract With respect to biological findings underlying fly’s physiology in the past decade, we present a directionally selective neural network, with a feed-forward structure and entirely low-level visual processing, so as to implement direction selective neurons in the fly’s visual system, which are mainly sensitive to wide-field translational movements in four cardinal directions. In this research, we highlight the functionality of ON and OFF pathways, separating motion information for parallel computation corresponding to light-on and light-off selectivity. Through this modeling study, we demonstrate several achievements compared with former bio-plausible translational motion detectors, like the elementary motion detectors. First, we thoroughly mimic the fly’s preliminary motion-detecting pathways with newly revealed fly’s physiology. Second, we improve the speed response to moving dark/light features via the design of ensembles of same polarity cells in the dual-pathways. Moreover, we alleviate the impact of irrelevant motion in a visually cluttered environment like the shifting of background and windblown vegetation, via the modeling of spatiotemporal dynamics. We systematically tested the DSNN against stimuli ranging from synthetic and real-world scenes, to notably a visual modality of a ground micro robot. The results demonstrated that the DSNN outperforms former bio-plausible translational motion detectors. Importantly, we verified its computational simplicity and effectiveness benefiting the building of neuromorphic vision sensor for robots.
Tasks
Published 2018-08-23
URL http://arxiv.org/abs/1808.07692v1
PDF http://arxiv.org/pdf/1808.07692v1.pdf
PWC https://paperswithcode.com/paper/a-directionally-selective-neural-network-with
Repo
Framework

Indic Handwritten Script Identification using Offline-Online Multimodal Deep Network

Title Indic Handwritten Script Identification using Offline-Online Multimodal Deep Network
Authors Ayan Kumar Bhunia, Subham Mukherjee, Aneeshan Sain, Ankan Kumar Bhunia, Partha Pratim Roy, Umapada Pal
Abstract In this paper, we propose a novel approach of word-level Indic script identification using only character-level data in training stage. The advantages of using character level data for training have been outlined in section I. Our method uses a multimodal deep network which takes both offline and online modality of the data as input in order to explore the information from both the modalities jointly for script identification task. We take handwritten data in either modality as input and the opposite modality is generated through intermodality conversion. Thereafter, we feed this offline-online modality pair to our network. Hence, along with the advantage of utilizing information from both the modalities, it can work as a single framework for both offline and online script identification simultaneously which alleviates the need for designing two separate script identification modules for individual modality. One more major contribution is that we propose a novel conditional multimodal fusion scheme to combine the information from offline and online modality which takes into account the real origin of the data being fed to our network and thus it combines adaptively. An exhaustive experiment has been done on a data set consisting of English and six Indic scripts. Our proposed framework clearly outperforms different frameworks based on traditional classifiers along with handcrafted features and deep learning based methods with a clear margin. Extensive experiments show that using only character level training data can achieve state-of-art performance similar to that obtained with traditional training using word level data in our framework.
Tasks
Published 2018-02-23
URL https://arxiv.org/abs/1802.08568v3
PDF https://arxiv.org/pdf/1802.08568v3.pdf
PWC https://paperswithcode.com/paper/indic-handwritten-script-identification-using
Repo
Framework

How Secure are Deep Learning Algorithms from Side-Channel based Reverse Engineering?

Title How Secure are Deep Learning Algorithms from Side-Channel based Reverse Engineering?
Authors Manaar Alam, Debdeep Mukhopadhyay
Abstract Deep Learning algorithms have recently become the de-facto paradigm for various prediction problems, which include many privacy-preserving applications like online medical image analysis. Presumably, the privacy of data in a deep learning system is a serious concern. There have been several efforts to analyze and exploit the information leakages from deep learning architectures to compromise data privacy. In this paper, however, we attempt to provide an evaluation strategy for such information leakages through deep neural network architectures by considering a case study on Convolutional Neural Network (CNN) based image classifier. The approach takes the aid of low-level hardware information, provided by Hardware Performance Counters (HPCs), during the execution of a CNN classifier and a simple hypothesis testing in order to produce an alarm if there exists any information leakage on the actual input.
Tasks
Published 2018-11-13
URL http://arxiv.org/abs/1811.05259v1
PDF http://arxiv.org/pdf/1811.05259v1.pdf
PWC https://paperswithcode.com/paper/how-secure-are-deep-learning-algorithms-from
Repo
Framework

Certified Mapper: Repeated testing for acyclicity and obstructions to the nerve lemma

Title Certified Mapper: Repeated testing for acyclicity and obstructions to the nerve lemma
Authors Mikael Vejdemo-Johansson, Alisa Leshchenko
Abstract The Mapper algorithm does not include a check for whether the cover produced conforms to the requirements of the nerve lemma. To perform a check for obstructions to the nerve lemma, statistical considerations of multiple testing quickly arise. In this paper, we propose several statistical approaches to finding obstructions: through a persistent nerve lemma, through simulation testing, and using a parametric refinement of simulation tests. We suggest Certified Mapper – a method built from these approaches to generate certificates of non-obstruction, or identify specific obstructions to the nerve lemma – and we give recommendations for which statistical approaches are most appropriate for the task.
Tasks
Published 2018-08-29
URL http://arxiv.org/abs/1808.09933v1
PDF http://arxiv.org/pdf/1808.09933v1.pdf
PWC https://paperswithcode.com/paper/certified-mapper-repeated-testing-for
Repo
Framework
comments powered by Disqus