October 17, 2019

3494 words 17 mins read

Paper Group ANR 726

Algorithmic Causal Deconvolution of Intertwined Programs and Networks by Generative Mechanism. Teaching Multiple Concepts to a Forgetful Learner. Complexity Results for Preference Aggregation over (m)CP-nets: Pareto and Majority Voting. What am I searching for?. Multimodal matching using a Hybrid Convolutional Neural Network. Wasserstein Distributi …

Algorithmic Causal Deconvolution of Intertwined Programs and Networks by Generative Mechanism


Title	Algorithmic Causal Deconvolution of Intertwined Programs and Networks by Generative Mechanism
Authors	Hector Zenil, Narsis A. Kiani, Allan A. Zea, Jesper Tegnér
Abstract	Complex data usually results from the interaction of objects produced by different generating mechanisms. Here we introduce a universal, unsupervised and parameter-free model-oriented approach, based upon the seminal concept of algorithmic probability, that decomposes an observation into its most likely algorithmic generative sources. Our approach uses a causal calculus to infer model representations. We demonstrate its ability to deconvolve interacting mechanisms regardless of whether the resultant objects are strings, space-time evolution diagrams, images or networks. While this is mostly a conceptual contribution and a novel framework, we provide numerical evidence evaluating the ability of our methods to separate data from observations produced by discrete dynamical systems such as cellular automata and complex networks. We think that these separating techniques can contribute to tackling the challenge of causation, thus complementing other statistically oriented approaches.
Tasks
Published	2018-02-18
URL	http://arxiv.org/abs/1802.09904v8
PDF	http://arxiv.org/pdf/1802.09904v8.pdf
PWC	https://paperswithcode.com/paper/algorithmic-causal-deconvolution-of
Repo
Framework

Teaching Multiple Concepts to a Forgetful Learner


Title	Teaching Multiple Concepts to a Forgetful Learner
Authors	Anette Hunziker, Yuxin Chen, Oisin Mac Aodha, Manuel Gomez Rodriguez, Andreas Krause, Pietro Perona, Yisong Yue, Adish Singla
Abstract	How can we help a forgetful learner learn multiple concepts within a limited time frame? While there have been extensive studies in designing optimal schedules for teaching a single concept given a learner’s memory model, existing approaches for teaching multiple concepts are typically based on heuristic scheduling techniques without theoretical guarantees. In this paper, we look at the problem from the perspective of discrete optimization and introduce a novel algorithmic framework for teaching multiple concepts with strong performance guarantees. Our framework is both generic, allowing the design of teaching schedules for different memory models, and also interactive, allowing the teacher to adapt the schedule to the underlying forgetting mechanisms of the learner. Furthermore, for a well-known memory model, we are able to identify a regime of model parameters where our framework is guaranteed to achieve high performance. We perform extensive evaluations using simulations along with real user studies in two concrete applications: (i) an educational app for online vocabulary teaching; and (ii) an app for teaching novices how to recognize animal species from images. Our results demonstrate the effectiveness of our algorithm compared to popular heuristic approaches.
Tasks
Published	2018-05-21
URL	https://arxiv.org/abs/1805.08322v4
PDF	https://arxiv.org/pdf/1805.08322v4.pdf
PWC	https://paperswithcode.com/paper/teaching-multiple-concepts-to-a-forgetful
Repo
Framework

Complexity Results for Preference Aggregation over (m)CP-nets: Pareto and Majority Voting


Title	Complexity Results for Preference Aggregation over (m)CP-nets: Pareto and Majority Voting
Authors	Thomas Lukasiewicz, Enrico Malizia
Abstract	Combinatorial preference aggregation has many applications in AI. Given the exponential nature of these preferences, compact representations are needed and ($m$)CP-nets are among the most studied ones. Sequential and global voting are two ways to aggregate preferences over CP-nets. In the former, preferences are aggregated feature-by-feature. Hence, when preferences have specific feature dependencies, sequential voting may exhibit voting paradoxes, i.e., it might select sub-optimal outcomes. To avoid paradoxes in sequential voting, one has often assumed the $\mathcal{O}$-legality restriction, which imposes a shared topological order among all the CP-nets. On the contrary, in global voting, CP-nets are considered as a whole during preference aggregation. For this reason, global voting is immune from paradoxes, and there is no need to impose restrictions over the CP-nets’ topological structure. Sequential voting over $\mathcal{O}$-legal CP-nets has extensively been investigated. On the other hand, global voting over non-$\mathcal{O}$-legal CP-nets has not carefully been analyzed, despite it was stated in the literature that a theoretical comparison between global and sequential voting was promising and a precise complexity analysis for global voting has been asked for multiple times. In quite few works, very partial results on the complexity of global voting over CP-nets have been given. We start to fill this gap by carrying out a thorough complexity analysis of Pareto and majority global voting over not necessarily $\mathcal{O}$-legal acyclic binary polynomially connected (m)CP-nets. We settle these problems in the polynomial hierarchy, and some of them in PTIME or LOGSPACE, whereas EXPTIME was the previously known upper bound for most of them. We show various tight lower bounds and matching upper bounds for problems that up to date did not have any explicit non-obvious lower bound.
Tasks
Published	2018-06-26
URL	http://arxiv.org/abs/1806.10018v1
PDF	http://arxiv.org/pdf/1806.10018v1.pdf
PWC	https://paperswithcode.com/paper/complexity-results-for-preference-aggregation
Repo
Framework

What am I searching for?


Title	What am I searching for?
Authors	Mengmi Zhang, Jiashi Feng, Joo Hwee Lim, Qi Zhao, Gabriel Kreiman
Abstract	Can we infer intentions and goals from a person’s actions? As an example of this family of problems, we consider here whether it is possible to decipher what a person is searching for by decoding their eye movement behavior. We conducted two human psychophysics experiments on object arrays and natural images where we monitored subjects’ eye movements while they were looking for a target object. Using as input the pattern of “error” fixations on non-target objects before the target was found, we developed a model (InferNet) whose goal was to infer what the target was. “Error” fixations share similar features with the sought target. The Infernet model uses a pre-trained 2D convolutional architecture to extract features from the error fixations and computes a 2D similarity map between the error fixation and all locations across the search image by modulating the search image via convolution across layers. InferNet consolidates the modulated response maps across layers via max pooling to keep track of the sub-patterns highly similar to features at error fixations and integrates these maps across all error fixations. InferNet successfully identifies the subject’s goal and outperforms all the competitive null models, even without any object-specific training on the inference task.
Tasks
Published	2018-07-31
URL	http://arxiv.org/abs/1807.11926v1
PDF	http://arxiv.org/pdf/1807.11926v1.pdf
PWC	https://paperswithcode.com/paper/what-am-i-searching-for
Repo
Framework

Multimodal matching using a Hybrid Convolutional Neural Network


Title	Multimodal matching using a Hybrid Convolutional Neural Network
Authors	Elad Ben Baruch, Yosi Keller
Abstract	In this work, we propose a novel Convolutional Neural Network (CNN) architecture for the joint detection and matching of feature points in images acquired by different sensors using a single forward pass. The resulting feature detector is tightly coupled with the feature descriptor, in contrast to classical approaches (SIFT, etc.), where the detection phase precedes and differs from computing the descriptor. Our approach utilizes two CNN subnetworks, the first being a Siamese CNN and the second, consisting of dual non-weight-sharing CNNs. This allows simultaneous processing and fusion of the joint and disjoint cues in the multimodal image patches. The proposed approach is experimentally shown to outperform contemporary state-of-the-art schemes when applied to multiple datasets of multimodal images by reducing the matching errors by 50%-70% compared with previous works. It is also shown to provide repeatable feature points detections across multi-sensor images, outperforming state-of-the-art detectors such as SIFT and ORB. To the best of our knowledge, it is the first unified approach for the detection and matching of such images.
Tasks
Published	2018-10-30
URL	https://arxiv.org/abs/1810.12941v2
PDF	https://arxiv.org/pdf/1810.12941v2.pdf
PWC	https://paperswithcode.com/paper/multimodal-matching-using-a-hybrid
Repo
Framework

Wasserstein Distributionally Robust Kalman Filtering


Title	Wasserstein Distributionally Robust Kalman Filtering
Authors	Soroosh Shafieezadeh-Abadeh, Viet Anh Nguyen, Daniel Kuhn, Peyman Mohajerin Esfahani
Abstract	We study a distributionally robust mean square error estimation problem over a nonconvex Wasserstein ambiguity set containing only normal distributions. We show that the optimal estimator and the least favorable distribution form a Nash equilibrium. Despite the non-convex nature of the ambiguity set, we prove that the estimation problem is equivalent to a tractable convex program. We further devise a Frank-Wolfe algorithm for this convex program whose direction-searching subproblem can be solved in a quasi-closed form. Using these ingredients, we introduce a distributionally robust Kalman filter that hedges against model risk.
Tasks
Published	2018-09-24
URL	http://arxiv.org/abs/1809.08830v3
PDF	http://arxiv.org/pdf/1809.08830v3.pdf
PWC	https://paperswithcode.com/paper/wasserstein-distributionally-robust-kalman
Repo
Framework

Model Inconsistent but Correlated Noise: Multi-view Subspace Learning with Regularized Mixture of Gaussians


Title	Model Inconsistent but Correlated Noise: Multi-view Subspace Learning with Regularized Mixture of Gaussians
Authors	Hongwei Yong, Deyu Meng, Jinxing Li, Wangmeng Zuo, Lei Zhang
Abstract	Multi-view subspace learning (MSL) aims to find a low-dimensional subspace of the data obtained from multiple views. Different from single view case, MSL should take both common and specific knowledge among different views into consideration. To enhance the robustness of model, the complexity, non-consistency and similarity of noise in multi-view data should be fully taken into consideration. Most current MSL methods only assume a simple Gaussian or Laplacian distribution for the noise while neglect the complex noise configurations in each view and noise correlations among different views of practical data. To this issue, this work initiates a MSL method by encoding the multi-view-shared and single-view-specific noise knowledge in data. Specifically, we model data noise in each view as a separated Mixture of Gaussians (MoG), which can fit a wider range of complex noise types than conventional Gaussian/Laplacian. Furthermore, we link all single-view-noise as a whole by regularizing them by a common MoG component, encoding the shared noise knowledge among them. Such regularization component can be formulated as a concise KL-divergence regularization term under a MAP framework, leading to good interpretation of our model and simple EM-based solving strategy to the problem. Experimental results substantiate the superiority of our method.
Tasks
Published	2018-11-07
URL	http://arxiv.org/abs/1811.02934v1
PDF	http://arxiv.org/pdf/1811.02934v1.pdf
PWC	https://paperswithcode.com/paper/model-inconsistent-but-correlated-noise-multi
Repo
Framework

Not just about size - A Study on the Role of Distributed Word Representations in the Analysis of Scientific Publications


Title	Not just about size - A Study on the Role of Distributed Word Representations in the Analysis of Scientific Publications
Authors	Andres Garcia, Jose Manuel Gomez-Perez
Abstract	The emergence of knowledge graphs in the scholarly communication domain and recent advances in artificial intelligence and natural language processing bring us closer to a scenario where intelligent systems can assist scientists over a range of knowledge-intensive tasks. In this paper we present experimental results about the generation of word embeddings from scholarly publications for the intelligent processing of scientific texts extracted from SciGraph. We compare the performance of domain-specific embeddings with existing pre-trained vectors generated from very large and general purpose corpora. Our results suggest that there is a trade-off between corpus specificity and volume. Embeddings from domain-specific scientific corpora effectively capture the semantics of the domain. On the other hand, obtaining comparable results through general corpora can also be achieved, but only in the presence of very large corpora of well formed text. Furthermore, We also show that the degree of overlapping between knowledge areas is directly related to the performance of embeddings in domain evaluation tasks.
Tasks	Knowledge Graphs, Word Embeddings
Published	2018-04-05
URL	http://arxiv.org/abs/1804.01772v1
PDF	http://arxiv.org/pdf/1804.01772v1.pdf
PWC	https://paperswithcode.com/paper/not-just-about-size-a-study-on-the-role-of
Repo
Framework

Phenotyping Endometriosis through Mixed Membership Models of Self-Tracking Data


Title	Phenotyping Endometriosis through Mixed Membership Models of Self-Tracking Data
Authors	Iñigo Urteaga, Mollie McKillop, Sharon Lipsky-Gorman, Noémie Elhadad
Abstract	We investigate the use of self-tracking data and unsupervised mixed-membership models to phenotype endometriosis. Endometriosis is a systemic, chronic condition of women in reproductive age and, at the same time, a highly enigmatic condition with no known biomarkers to monitor its progression and no established staging. We leverage data collected through a self-tracking app in an observational research study of over 2,800 women with endometriosis tracking their condition over a year and a half (456,900 observations overall). We extend a classical mixed-membership model to accommodate the idiosyncrasies of the data at hand (i.e., the multimodality of the tracked variables). Our experiments show that our approach identifies potential subtypes that are robust in terms of biases of self-tracked data (e.g., wide variations in tracking frequency amongst participants), as well as to variations in hyperparameters of the model. Jointly modeling a wide range of observations about participants (symptoms, quality of life, treatments) yields clinically meaningful subtypes that both validate what is already known about endometriosis and suggest new findings.
Tasks
Published	2018-11-06
URL	http://arxiv.org/abs/1811.03431v1
PDF	http://arxiv.org/pdf/1811.03431v1.pdf
PWC	https://paperswithcode.com/paper/phenotyping-endometriosis-through-mixed
Repo
Framework

A 3-D Projection Model for X-ray Dark-field Imaging


Title	A 3-D Projection Model for X-ray Dark-field Imaging
Authors	Shiyang Hu, Lina Felsner, Andreas Maier, Veronika Ludwig, Gisela Anton, Christian Riess
Abstract	Talbot-Lau X-ray phase-contrast imaging is a novel imaging modality, which provides not only an X-ray absorption image, but also additionally a differential phase image and a dark-field image. The dark-field image is related to small angle scattering and has an interesting property when canning oriented structures: the recorded signal depends on the relative orientation of the structure in the imaging system. Exactly this property allows to draw conclusions about the orientation and to reconstruct the structure. However, the reconstruction is a complex, non-trivial challenge. A lot of research was conducted towards this goal in the last years and several reconstruction algorithms were proposed. A key step of the reconstruction algorithm is the inversion of a forward projection model. Up until now, only 2-D projection models are available, with effectively limit the scanning trajectory to a 2-D plane. To obtain true 3-D information, this limitation requires to combine several 2-D scans, which leads to quite complex, impractical acquisitions schemes. Furthermore, it is not possible with these models to use 3-D trajectories that might allow simpler protocols, like for example a helical trajectory. To address these limitations, we propose in this work a very general 3-D projection model. Our projection model defines the dark-field signal dependent on an arbitrarily chosen ray and sensitivity direction. We derive the projection model under the assumption that the observed scatter distribution has a Gaussian shape. We theoretically show the consistency of our model with more constrained existing 2-D models. Furthermore, we experimentally show the compatibility of our model with dark-field measurements of two matchsticks. We believe that this 3-D projection model is an important step towards more flexible trajectories and imaging protocols that are much better applicable in practice.
Tasks
Published	2018-11-11
URL	http://arxiv.org/abs/1811.04457v2
PDF	http://arxiv.org/pdf/1811.04457v2.pdf
PWC	https://paperswithcode.com/paper/a-3-d-projection-model-for-x-ray-dark-field
Repo
Framework

Concise Explanations of Neural Networks using Adversarial Training


Title	Concise Explanations of Neural Networks using Adversarial Training
Authors	Prasad Chalasani, Jiefeng Chen, Amrita Roy Chowdhury, Somesh Jha, Xi Wu
Abstract	We show new connections between adversarial learning and explainability for deep neural networks (DNNs). One form of explanation of the output of a neural network model in terms of its input features, is a vector of feature-attributions. Two desirable characteristics of an attribution-based explanation are: (1) $\textit{sparseness}$: the attributions of irrelevant or weakly relevant features should be negligible, thus resulting in $\textit{concise}$ explanations in terms of the significant features, and (2) $\textit{stability}$: it should not vary significantly within a small local neighborhood of the input. Our first contribution is a theoretical exploration of how these two properties (when using attributions based on Integrated Gradients, or IG) are related to adversarial training, for a class of 1-layer networks (which includes logistic regression models for binary and multi-class classification); for these networks we show that (a) adversarial training using an $\ell_\infty$-bounded adversary produces models with sparse attribution vectors, and (b) natural model-training while encouraging stable explanations (via an extra term in the loss function), is equivalent to adversarial training. Our second contribution is an empirical verification of phenomenon (a), which we show, somewhat surprisingly, occurs $\textit{not only}$ $\textit{in 1-layer networks}$, $\textit{but also}$ $\textit{DNNs trained on}$ $\textit{standard image}$ $\textit{ datasets}$, and extends beyond IG-based attributions, to those based on DeepSHAP: adversarial training with $\ell_\infty$-bounded perturbations yields significantly sparser attribution vectors, with little degradation in performance on natural test data, compared to natural training. Moreover, the sparseness of the attribution vectors is significantly better than that achievable via $\ell_1$-regularized natural training.
Tasks
Published	2018-10-15
URL	https://arxiv.org/abs/1810.06583v8
PDF	https://arxiv.org/pdf/1810.06583v8.pdf
PWC	https://paperswithcode.com/paper/adversarial-learning-and-explainability-in
Repo
Framework

Detecting Work Zones in SHRP 2 NDS Videos Using Deep Learning Based Computer Vision


Title	Detecting Work Zones in SHRP 2 NDS Videos Using Deep Learning Based Computer Vision
Authors	Franklin Abodo, Robert Rittmuller, Brian Sumner, Andrew Berthaume
Abstract	Naturalistic driving studies seek to perform the observations of human driver behavior in the variety of environmental conditions necessary to analyze, understand and predict that behavior using statistical and physical models. The second Strategic Highway Research Program (SHRP 2) funds a number of transportation safety-related projects including its primary effort, the Naturalistic Driving Study (NDS), and an effort supplementary to the NDS, the Roadway Information Database (RID). This work seeks to expand the range of answerable research questions that researchers might pose to the NDS and RID databases. Specifically, we present the SHRP 2 NDS Video Analytics (SNVA) software application, which extracts information from NDS-instrumented vehicles’ forward-facing camera footage and efficiently integrates that information into the RID, tying the video content to geolocations and other trip attributes. Of particular interest to researchers and other stakeholders is the integration of work zone, traffic signal state and weather information. The version of SNVA introduced in this paper focuses on work zone detection, the highest priority. The ability to automate the discovery and cataloging of this information, and to do so quickly, is especially important given the two petabyte (2PB) size of the NDS video data set.
Tasks
Published	2018-11-10
URL	http://arxiv.org/abs/1811.04250v1
PDF	http://arxiv.org/pdf/1811.04250v1.pdf
PWC	https://paperswithcode.com/paper/detecting-work-zones-in-shrp-2-nds-videos
Repo
Framework

A Formalization of Kant’s Second Formulation of the Categorical Imperative


Title	A Formalization of Kant’s Second Formulation of the Categorical Imperative
Authors	Felix Lindner, Martin Mose Bentzen
Abstract	We present a formalization and computational implementation of the second formulation of Kant’s categorical imperative. This ethical principle requires an agent to never treat someone merely as a means but always also as an end. Here we interpret this principle in terms of how persons are causally affected by actions. We introduce Kantian causal agency models in which moral patients, actions, goals, and causal influence are represented, and we show how to formalize several readings of Kant’s categorical imperative that correspond to Kant’s concept of strict and wide duties towards oneself and others. Stricter versions handle cases where an action directly causally affects oneself or others, whereas the wide version maximizes the number of persons being treated as an end. We discuss limitations of our formalization by pointing to one of Kant’s cases that the machinery cannot handle in a satisfying way.
Tasks
Published	2018-01-09
URL	https://arxiv.org/abs/1801.03160v3
PDF	https://arxiv.org/pdf/1801.03160v3.pdf
PWC	https://paperswithcode.com/paper/a-formalization-of-kants-second-formulation
Repo
Framework

Learning under selective labels in the presence of expert consistency


Title	Learning under selective labels in the presence of expert consistency
Authors	Maria De-Arteaga, Artur Dubrawski, Alexandra Chouldechova
Abstract	We explore the problem of learning under selective labels in the context of algorithm-assisted decision making. Selective labels is a pervasive selection bias problem that arises when historical decision making blinds us to the true outcome for certain instances. Examples of this are common in many applications, ranging from predicting recidivism using pre-trial release data to diagnosing patients. In this paper we discuss why selective labels often cannot be effectively tackled by standard methods for adjusting for sample selection bias, even if there are no unobservables. We propose a data augmentation approach that can be used to either leverage expert consistency to mitigate the partial blindness that results from selective labels, or to empirically validate whether learning under such framework may lead to unreliable models prone to systemic discrimination.
Tasks	Data Augmentation, Decision Making
Published	2018-07-02
URL	http://arxiv.org/abs/1807.00905v2
PDF	http://arxiv.org/pdf/1807.00905v2.pdf
PWC	https://paperswithcode.com/paper/learning-under-selective-labels-in-the
Repo
Framework

Ranking with Features: Algorithm and A Graph Theoretic Analysis


Title	Ranking with Features: Algorithm and A Graph Theoretic Analysis
Authors	Aadirupa Saha, Arun Rajkumar
Abstract	We consider the problem of ranking a set of items from pairwise comparisons in the presence of features associated with the items. Recent works have established that $O(n\log(n))$ samples are needed to rank well when there is no feature information present. However, this might be sub-optimal in the presence of associated features. We introduce a new probabilistic preference model called feature-Bradley-Terry-Luce (f-BTL) model that generalizes the standard BTL model to incorporate feature information. We present a new least squares based algorithm called fBTL-LS which we show requires much lesser than $O(n\log(n))$ pairs to obtain a good ranking – precisely our new sample complexity bound is of $O(\alpha\log \alpha)$, where $\alpha$ denotes the number of `independent items’ of the set, in general $\alpha « n$. Our analysis is novel and makes use of tools from classical graph matching theory to provide tighter bounds that sheds light on the true complexity of the ranking problem, capturing the item dependencies in terms of their feature representations. This was not possible with earlier matrix completion based tools used for this problem. We also prove an information theoretic lower bound on the required sample complexity for recovering the underlying ranking, which essentially shows the tightness of our proposed algorithms. The efficacy of our proposed algorithms are validated through extensive experimental evaluations on a variety of synthetic and real world datasets. \|
Tasks	Graph Matching, Matrix Completion
Published	2018-08-11
URL	http://arxiv.org/abs/1808.03857v1
PDF	http://arxiv.org/pdf/1808.03857v1.pdf
PWC	https://paperswithcode.com/paper/ranking-with-features-algorithm-and-a-graph
Repo
Framework