January 28, 2020

3293 words 16 mins read

Paper Group ANR 956

Complete Dictionary Learning via $\ell^4$-Norm Maximization over the Orthogonal Group. OK-VQA: A Visual Question Answering Benchmark Requiring External Knowledge. Exploring Unsupervised Pretraining and Sentence Structure Modelling for Winograd Schema Challenge. Interaction-aware Decision Making with Adaptive Strategies under Merging Scenarios. Aski …

Complete Dictionary Learning via $\ell^4$-Norm Maximization over the Orthogonal Group


Title	Complete Dictionary Learning via $\ell^4$-Norm Maximization over the Orthogonal Group
Authors	Yuexiang Zhai, Zitong Yang, Zhenyu Liao, John Wright, Yi Ma
Abstract	This paper considers the fundamental problem of learning a complete (orthogonal) dictionary from samples of sparsely generated signals. Most existing methods solve the dictionary (and sparse representations) based on heuristic algorithms, usually without theoretical guarantees for either optimality or complexity. The recent $\ell^1$-minimization based methods do provide such guarantees but the associated algorithms recover the dictionary one column at a time. In this work, we propose a new formulation that maximizes the $\ell^4$-norm over the orthogonal group, to learn the entire dictionary. We prove that under a random data model, with nearly minimum sample complexity, the global optima of the $\ell^4$ norm are very close to signed permutations of the ground truth. Inspired by this observation, we give a conceptually simple and yet effective algorithm based on “matching, stretching, and projection” (MSP). The algorithm provably converges locally at a superlinear (cubic) rate and cost per iteration is merely an SVD. In addition to strong theoretical guarantees, experiments show that the new algorithm is significantly more efficient and effective than existing methods, including KSVD and $\ell^1$-based methods. Preliminary experimental results on mixed real imagery data clearly demonstrate advantages of so learned dictionary over classic PCA bases.
Tasks	Dictionary Learning
Published	2019-06-06
URL	https://arxiv.org/abs/1906.02435v3
PDF	https://arxiv.org/pdf/1906.02435v3.pdf
PWC	https://paperswithcode.com/paper/complete-dictionary-learning-via-ell4-norm
Repo
Framework

OK-VQA: A Visual Question Answering Benchmark Requiring External Knowledge


Title	OK-VQA: A Visual Question Answering Benchmark Requiring External Knowledge
Authors	Kenneth Marino, Mohammad Rastegari, Ali Farhadi, Roozbeh Mottaghi
Abstract	Visual Question Answering (VQA) in its ideal form lets us study reasoning in the joint space of vision and language and serves as a proxy for the AI task of scene understanding. However, most VQA benchmarks to date are focused on questions such as simple counting, visual attributes, and object detection that do not require reasoning or knowledge beyond what is in the image. In this paper, we address the task of knowledge-based visual question answering and provide a benchmark, called OK-VQA, where the image content is not sufficient to answer the questions, encouraging methods that rely on external knowledge resources. Our new dataset includes more than 14,000 questions that require external knowledge to answer. We show that the performance of the state-of-the-art VQA models degrades drastically in this new setting. Our analysis shows that our knowledge-based VQA task is diverse, difficult, and large compared to previous knowledge-based VQA datasets. We hope that this dataset enables researchers to open up new avenues for research in this domain. See http://okvqa.allenai.org to download and browse the dataset.
Tasks	Object Detection, Question Answering, Scene Understanding, Visual Question Answering
Published	2019-05-31
URL	https://arxiv.org/abs/1906.00067v2
PDF	https://arxiv.org/pdf/1906.00067v2.pdf
PWC	https://paperswithcode.com/paper/190600067
Repo
Framework

Exploring Unsupervised Pretraining and Sentence Structure Modelling for Winograd Schema Challenge


Title	Exploring Unsupervised Pretraining and Sentence Structure Modelling for Winograd Schema Challenge
Authors	Yu-Ping Ruan, Xiaodan Zhu, Zhen-Hua Ling, Zhan Shi, Quan Liu, Si Wei
Abstract	Winograd Schema Challenge (WSC) was proposed as an AI-hard problem in testing computers’ intelligence on common sense representation and reasoning. This paper presents the new state-of-theart on WSC, achieving an accuracy of 71.1%. We demonstrate that the leading performance benefits from jointly modelling sentence structures, utilizing knowledge learned from cutting-edge pretraining models, and performing fine-tuning. We conduct detailed analyses, showing that fine-tuning is critical for achieving the performance, but it helps more on the simpler associative problems. Modelling sentence dependency structures, however, consistently helps on the harder non-associative subset of WSC. Analysis also shows that larger fine-tuning datasets yield better performances, suggesting the potential benefit of future work on annotating more Winograd schema sentences.
Tasks	Common Sense Reasoning
Published	2019-04-22
URL	http://arxiv.org/abs/1904.09705v1
PDF	http://arxiv.org/pdf/1904.09705v1.pdf
PWC	https://paperswithcode.com/paper/exploring-unsupervised-pretraining-and
Repo
Framework

Interaction-aware Decision Making with Adaptive Strategies under Merging Scenarios


Title	Interaction-aware Decision Making with Adaptive Strategies under Merging Scenarios
Authors	Yeping Hu, Alireza Nakhaei, Masayoshi Tomizuka, Kikuo Fujimura
Abstract	In order to drive safely and efficiently under merging scenarios, autonomous vehicles should be aware of their surroundings and make decisions by interacting with other road participants. Moreover, different strategies should be made when the autonomous vehicle is interacting with drivers having different level of cooperativeness. Whether the vehicle is on the merge-lane or main-lane will also influence the driving maneuvers since drivers will behave differently when they have the right-of-way than otherwise. Many traditional methods have been proposed to solve decision making problems under merging scenarios. However, these works either are incapable of modeling complicated interactions or require implementing hand-designed rules which cannot properly handle the uncertainties in real-world scenarios. In this paper, we proposed an interaction-aware decision making with adaptive strategies (IDAS) approach that can let the autonomous vehicle negotiate the road with other drivers by leveraging their cooperativeness under merging scenarios. A single policy is learned under the multi-agent reinforcement learning (MARL) setting via the curriculum learning strategy, which enables the agent to automatically infer other drivers’ various behaviors and make decisions strategically. A masking mechanism is also proposed to prevent the agent from exploring states that violate common sense of human judgment and increase the learning efficiency. An exemplar merging scenario was used to implement and examine the proposed method.
Tasks	Autonomous Vehicles, Common Sense Reasoning, Decision Making, Multi-agent Reinforcement Learning
Published	2019-04-12
URL	https://arxiv.org/abs/1904.06025v2
PDF	https://arxiv.org/pdf/1904.06025v2.pdf
PWC	https://paperswithcode.com/paper/interaction-aware-decision-making-with
Repo
Framework

Asking the Right Question: Inferring Advice-Seeking Intentions from Personal Narratives


Title	Asking the Right Question: Inferring Advice-Seeking Intentions from Personal Narratives
Authors	Liye Fu, Jonathan P. Chang, Cristian Danescu-Niculescu-Mizil
Abstract	People often share personal narratives in order to seek advice from others. To properly infer the narrator’s intention, one needs to apply a certain degree of common sense and social intuition. To test the capabilities of NLP systems to recover such intuition, we introduce the new task of inferring what is the advice-seeking goal behind a personal narrative. We formulate this as a cloze test, where the goal is to identify which of two advice-seeking questions was removed from a given narrative. The main challenge in constructing this task is finding pairs of semantically plausible advice-seeking questions for given narratives. To address this challenge, we devise a method that exploits commonalities in experiences people share online to automatically extract pairs of questions that are appropriate candidates for the cloze task. This results in a dataset of over 20,000 personal narratives, each matched with a pair of related advice-seeking questions: one actually intended by the narrator, and the other one not. The dataset covers a very broad array of human experiences, from dating, to career options, to stolen iPads. We use human annotation to determine the degree to which the task relies on common sense and social intuition in addition to a semantic understanding of the narrative. By introducing several baselines for this new task we demonstrate its feasibility and identify avenues for better modeling the intention of the narrator.
Tasks	Common Sense Reasoning
Published	2019-04-02
URL	http://arxiv.org/abs/1904.01587v1
PDF	http://arxiv.org/pdf/1904.01587v1.pdf
PWC	https://paperswithcode.com/paper/asking-the-right-question-inferring-advice
Repo
Framework

Generalized Sliced Wasserstein Distances


Title	Generalized Sliced Wasserstein Distances
Authors	Soheil Kolouri, Kimia Nadjahi, Umut Simsekli, Roland Badeau, Gustavo K. Rohde
Abstract	The Wasserstein distance and its variations, e.g., the sliced-Wasserstein (SW) distance, have recently drawn attention from the machine learning community. The SW distance, specifically, was shown to have similar properties to the Wasserstein distance, while being much simpler to compute, and is therefore used in various applications including generative modeling and general supervised/unsupervised learning. In this paper, we first clarify the mathematical connection between the SW distance and the Radon transform. We then utilize the generalized Radon transform to define a new family of distances for probability measures, which we call generalized sliced-Wasserstein (GSW) distances. We also show that, similar to the SW distance, the GSW distance can be extended to a maximum GSW (max-GSW) distance. We then provide the conditions under which GSW and max-GSW distances are indeed distances. Finally, we compare the numerical performance of the proposed distances on several generative modeling tasks, including SW flows and SW auto-encoders.
Tasks
Published	2019-02-01
URL	http://arxiv.org/abs/1902.00434v1
PDF	http://arxiv.org/pdf/1902.00434v1.pdf
PWC	https://paperswithcode.com/paper/generalized-sliced-wasserstein-distances
Repo
Framework

Deep RGB-D Canonical Correlation Analysis For Sparse Depth Completion


Title	Deep RGB-D Canonical Correlation Analysis For Sparse Depth Completion
Authors	Yiqi Zhong, Cho-Ying Wu, Suya You, Ulrich Neumann
Abstract	In this paper, we propose our Correlation For Completion Network (CFCNet), an end-to-end deep learning model that uses the correlation between two data sources to perform sparse depth completion. CFCNet learns to capture, to the largest extent, the semantically correlated features between RGB and depth information. Through pairs of image pixels and the visible measurements in a sparse depth map, CFCNet facilitates feature-level mutual transformation of different data sources. Such a transformation enables CFCNet to predict features and reconstruct data of missing depth measurements according to their corresponding, transformed RGB features. We extend canonical correlation analysis to a 2D domain and formulate it as one of our training objectives (i.e. 2d deep canonical correlation, or “2D2CCA loss”). Extensive experiments validate the ability and flexibility of our CFCNet compared to the state-of-the-art methods on both indoor and outdoor scenes with different real-life sparse patterns. Codes are available at: https://github.com/choyingw/CFCNet.
Tasks	Depth Completion
Published	2019-06-21
URL	https://arxiv.org/abs/1906.08967v3
PDF	https://arxiv.org/pdf/1906.08967v3.pdf
PWC	https://paperswithcode.com/paper/deep-rgb-d-canonical-correlation-analysis-for
Repo
Framework

Automated Testing for Deep Learning Systems with Differential Behavior Criteria


Title	Automated Testing for Deep Learning Systems with Differential Behavior Criteria
Authors	Yuan Gao, Yiqiang Han
Abstract	In this work, we conducted a study on building an automated testing system for deep learning systems based on differential behavior criteria. The automated testing goals were achieved by jointly optimizing two objective functions: maximizing differential behaviors from models under testing and maximizing neuron coverage. By observing differential behaviors from three pre-trained models during each testing iteration, the input image that triggered erroneous feedback was registered as a corner-case. The generated corner-cases can be used to examine the robustness of DNNs and consequently improve model accuracy. A project called DeepXplore was also used as a baseline model. After we fully implemented and optimized the baseline system, we explored its application as an augmenting training dataset with newly generated corner cases. With the GTRSB dataset, by retraining the model based on automated generated corner cases, the accuracy of three generic models increased by 259.2%, 53.6%, and 58.3%, respectively. Further, to extend the capability of automated testing, we explored other approaches based on differential behavior criteria to generate photo-realistic images for deep learning systems. One approach was to apply various transformations to the seed images for the deep learning framework. The other approach was to utilize the Generative Adversarial Networks (GAN) technique, which was implemented on MNIST and Driving datasets. The style transferring capability has been observed very effective in adding additional visual effects, replacing image elements, and style-shifting (virtual image to real images). The GAN-based testing sample generation system was shown to be the next frontier for automated testing for deep learning systems.
Tasks
Published	2019-12-31
URL	https://arxiv.org/abs/1912.13258v1
PDF	https://arxiv.org/pdf/1912.13258v1.pdf
PWC	https://paperswithcode.com/paper/automated-testing-for-deep-learning-systems
Repo
Framework

Memory Management in Resource-Bounded Agents


Title	Memory Management in Resource-Bounded Agents
Authors	Valentina Pitoni
Abstract	In artificial intelligence, multi agent systems constitute an interesting typology of society modeling, and have in this regard vast fields of application, which extend to the human sciences. Logic is often used to model such kind of systems as it is easier to verify the explainability and validation, so for this reason we have tried to manage agents’ memory extending a previous work by inserting the concept of time.
Tasks
Published	2019-09-18
URL	https://arxiv.org/abs/1909.09454v1
PDF	https://arxiv.org/pdf/1909.09454v1.pdf
PWC	https://paperswithcode.com/paper/memory-management-in-resource-bounded-agents
Repo
Framework

Detection and Prediction of Cardiac Anomalies Using Wireless Body Sensors and Bayesian Belief Networks


Title	Detection and Prediction of Cardiac Anomalies Using Wireless Body Sensors and Bayesian Belief Networks
Authors	Asim Darwaish, Farid Naït-Abdesselam, Ashfaq Khokhar
Abstract	Intricating cardiac complexities are the primary factor associated with healthcare costs and the highest cause of death rate in the world. However, preventive measures like the early detection of cardiac anomalies can prevent severe cardiovascular arrests of varying complexities and can impose a substantial impact on healthcare cost. Encountering such scenarios usually the electrocardiogram (ECG or EKG) is the first diagnostic choice of a medical practitioner or clinical staff to measure the electrical and muscular fitness of an individual heart. This paper presents a system which is capable of reading the recorded ECG and predict the cardiac anomalies without the intervention of a human expert. The paper purpose an algorithm which read and perform analysis on electrocardiogram datasets. The proposed architecture uses the Discrete Wavelet Transform (DWT) at first place to perform preprocessing of ECG data followed by undecimated Wavelet transform (UWT) to extract nine relevant features which are of high interest to a cardiologist. The probabilistic mode named Bayesian Network Classifier is trained using the extracted nine parameters on UCL arrhythmia dataset. The proposed system classifies a recorded heartbeat into four classes using Bayesian Network classifier and Tukey’s box analysis. The four classes for the prediction of a heartbeat are (a) Normal Beat, (b) Premature Ventricular Contraction (PVC) (c) Premature Atrial Contraction (PAC) and (d) Myocardial Infarction. The results of experimental setup depict that the proposed system has achieved an average accuracy of 96.6 for PAC% 92.8% for MI and 87% for PVC, with an average error rate of 3.3% for PAC, 6% for MI and 12.5% for PVC on real electrocardiogram datasets including Physionet and European ST-T Database (EDB).
Tasks
Published	2019-04-16
URL	http://arxiv.org/abs/1904.07976v1
PDF	http://arxiv.org/pdf/1904.07976v1.pdf
PWC	https://paperswithcode.com/paper/detection-and-prediction-of-cardiac-anomalies
Repo
Framework

On Graph Classification Networks, Datasets and Baselines


Title	On Graph Classification Networks, Datasets and Baselines
Authors	Enxhell Luzhnica, Ben Day, Pietro Liò
Abstract	Graph classification receives a great deal of attention from the non-Euclidean machine learning community. Recent advances in graph coarsening have enabled the training of deeper networks and produced new state-of-the-art results in many benchmark tasks. We examine how these architectures train and find that performance is highly-sensitive to initialisation and depends strongly on jumping-knowledge structures. We then show that, despite the great complexity of these models, competitive performance is achieved by the simplest of models – structure-blind MLP, single-layer GCN and fixed-weight GCN – and propose these be included as baselines in future.
Tasks	Graph Classification
Published	2019-05-12
URL	https://arxiv.org/abs/1905.04682v1
PDF	https://arxiv.org/pdf/1905.04682v1.pdf
PWC	https://paperswithcode.com/paper/on-graph-classification-networks-datasets-and
Repo
Framework

HUGE2: a Highly Untangled Generative-model Engine for Edge-computing


Title	HUGE2: a Highly Untangled Generative-model Engine for Edge-computing
Authors	Feng Shi, Ziheng Xu, Tao Yuan, Song-Chun Zhu
Abstract	As a type of prominent studies in deep learning, generative models have been widely investigated in research recently. Two research branches of the deep learning models, the Generative Networks (GANs, VAE) and the Semantic Segmentation, rely highly on the upsampling operations, especially the transposed convolution and the dilated convolution. However, these two types of convolutions are intrinsically different from standard convolution regarding the insertion of zeros in input feature maps or in kernels respectively. This distinct nature severely degrades the performance of the existing deep learning engine or frameworks, such as Darknet, Tensorflow, and PyTorch, which are mainly developed for the standard convolution. Another trend in deep learning realm is to deploy the model onto edge/ embedded devices, in which the memory resource is scarce. In this work, we propose a Highly Untangled Generative-model Engine for Edge-computing or HUGE2 for accelerating these two special convolutions on the edge-computing platform by decomposing the kernels and untangling these smaller convolutions by performing basic matrix multiplications. The methods we propose use much smaller memory footprint, hence much fewer memory accesses, and the data access patterns also dramatically increase the reusability of the data already fetched in caches, hence increasing the localities of caches. Our engine achieves a speedup of nearly 5x on embedded CPUs, and around 10x on embedded GPUs, and more than 50% reduction of memory access.
Tasks	Semantic Segmentation
Published	2019-07-25
URL	https://arxiv.org/abs/1907.11210v1
PDF	https://arxiv.org/pdf/1907.11210v1.pdf
PWC	https://paperswithcode.com/paper/huge2-a-highly-untangled-generative-model
Repo
Framework

Efficient Regret Minimization Algorithm for Extensive-Form Correlated Equilibrium


Title	Efficient Regret Minimization Algorithm for Extensive-Form Correlated Equilibrium
Authors	Gabriele Farina, Chun Kai Ling, Fei Fang, Tuomas Sandholm
Abstract	Self-play methods based on regret minimization have become the state of the art for computing Nash equilibria in large two-players zero-sum extensive-form games. These methods fundamentally rely on the hierarchical structure of the players’ sequential strategy spaces to construct a regret minimizer that recursively minimizes regret at each decision point in the game tree. In this paper, we introduce the first efficient regret minimization algorithm for computing extensive-form correlated equilibria in large two-player general-sum games with no chance moves. Designing such an algorithm is significantly more challenging than designing one for the Nash equilibrium counterpart, as the constraints that define the space of correlation plans lack the hierarchical structure and might even form cycles. We show that some of the constraints are redundant and can be excluded from consideration, and present an efficient algorithm that generates the space of extensive-form correlation plans incrementally from the remaining constraints. This structural decomposition is achieved via a special convexity-preserving operation that we coin scaled extension. We show that a regret minimizer can be designed for a scaled extension of any two convex sets, and that from the decomposition we then obtain a global regret minimizer. Our algorithm produces feasible iterates. Experiments show that it significantly outperforms prior approaches and for larger problems it is the only viable option.
Tasks
Published	2019-10-28
URL	https://arxiv.org/abs/1910.12450v1
PDF	https://arxiv.org/pdf/1910.12450v1.pdf
PWC	https://paperswithcode.com/paper/efficient-regret-minimization-algorithm-for
Repo
Framework

A Guiding Principle for Causal Decision Problems


Title	A Guiding Principle for Causal Decision Problems
Authors	M. Gonzalez-Soto, L. E. Sucar, H. J. Escalante
Abstract	We define a Causal Decision Problem as a Decision Problem where the available actions, the family of uncertain events and the set of outcomes are related through the variables of a Causal Graphical Model $\mathcal{G}$. A solution criteria based on Pearl’s Do-Calculus and the Expected Utility criteria for rational preferences is proposed. The implementation of this criteria leads to an on-line decision making procedure that has been shown to have similar performance to classic Reinforcement Learning algorithms while allowing for a causal model of an environment to be learned. Thus, we aim to provide the theoretical guarantees of the usefulness and optimality of a decision making procedure based on causal information.
Tasks	Decision Making
Published	2019-02-06
URL	http://arxiv.org/abs/1902.02279v1
PDF	http://arxiv.org/pdf/1902.02279v1.pdf
PWC	https://paperswithcode.com/paper/a-guiding-principle-for-causal-decision
Repo
Framework

The Use of Binary Choice Forests to Model and Estimate Discrete Choices


Title	The Use of Binary Choice Forests to Model and Estimate Discrete Choices
Authors	Ningyuan Chen, Guillermo Gallego, Zhuodong Tang
Abstract	We show the equivalence of discrete choice models and the class of binary choice forests, which are random forests based on binary choice trees. This suggests that standard machine learning techniques based on random forests can serve to estimate discrete choice models with an interpretable output. This is confirmed by our data-driven theoretical results which show that random forests can predict the choice probability of any discrete choice model consistently, with its splitting criterion capable of recovering preference rank lists. The framework has unique advantages: it can capture behavioral patterns such as irrationality or sequential searches; it handles nonstandard formats of training data that result from aggregation; it can measure product importance based on how frequently a random customer would make decisions depending on the presence of the product; it can also incorporate price information and customer features. Our numerical results show that using random forests to estimate customer choices represented by binary choice forests can outperform the best parametric models in synthetic and real datasets.
Tasks
Published	2019-08-03
URL	https://arxiv.org/abs/1908.01109v3
PDF	https://arxiv.org/pdf/1908.01109v3.pdf
PWC	https://paperswithcode.com/paper/the-use-of-binary-choice-forests-to-model-and
Repo
Framework