January 31, 2020

3427 words 17 mins read

Paper Group ANR 45

A constrained ICA-EMD Model for Group Level fMRI Analysis. PanDA: Panoptic Data Augmentation. A study of problems with multiple interdependent components - Part I. Quantitative Mitigation of Timing Side Channels. Deception through Half-Truths. A Logic-Based Framework Leveraging Neural Networks for Studying the Evolution of Neurological Disorders. B …

A constrained ICA-EMD Model for Group Level fMRI Analysis


Title	A constrained ICA-EMD Model for Group Level fMRI Analysis
Authors	Simon Wein, Ana Maria Tomé, Markus Goldhacker, Mark W. Greenlee, Elmar W. Lang
Abstract	Independent component analysis (ICA), as a data driven method, has shown to be a powerful tool for functional magnetic resonance imaging (fMRI) data analysis. One drawback of this multivariate approach is, that it is not compatible to the analysis of group data in general. Therefore various techniques have been proposed in order to overcome this limitation of ICA. In this paper a novel ICA-based work-flow for extracting resting state networks from fMRI group studies is proposed. An empirical mode decomposition (EMD) is used to generate reference signals in a data driven manner, which can be incorporated into a constrained version of ICA (cICA), what helps to eliminate the inherent ambiguities of ICA. The results of the proposed workflow are then compared to those obtained by a widely used group ICA approach for fMRI analysis. In this paper it is demonstrated that intrinsic modes, extracted by EMD, are suitable to serve as references for cICA to obtain typical resting state patterns, which are consistent over subjects. By introducing these reference signals into the ICA, our processing pipeline makes it transparent for the user, how comparable activity patterns across subjects emerge. This additionally allows adapting the trade-off between enforcing similarity across subjects and preserving individual subject features.
Tasks
Published	2019-03-22
URL	http://arxiv.org/abs/1903.09412v1
PDF	http://arxiv.org/pdf/1903.09412v1.pdf
PWC	https://paperswithcode.com/paper/a-constrained-ica-emd-model-for-group-level
Repo
Framework

PanDA: Panoptic Data Augmentation


Title	PanDA: Panoptic Data Augmentation
Authors	Yang Liu, Pietro Perona, Markus Meister
Abstract	The recently proposed panoptic segmentation task presents a significant challenge of image understanding with computer vision by unifying semantic segmentation and instance segmentation tasks. In this paper we present an efficient and novel panoptic data augmentation (PanDA) method which operates exclusively in pixel space, requires no additional data or training, and is computationally cheap to implement. We retrain the original state-of-the-art UPSNet panoptic segmentation model on PanDA augmented Cityscapes dataset, and demonstrate all-round performance improvement upon the original model. We also show that PanDA is effective across scales from 10 to 30,000 images, as well as generalizable to Microsoft COCO panoptic segmentation task. Finally, the effectiveness of PanDA generated unrealistic-looking training images suggest that we should rethink about optimizing levels of image realism for efficient data augmentation.
Tasks	Data Augmentation, Instance Segmentation, Panoptic Segmentation, Semantic Segmentation
Published	2019-11-27
URL	https://arxiv.org/abs/1911.12317v1
PDF	https://arxiv.org/pdf/1911.12317v1.pdf
PWC	https://paperswithcode.com/paper/panda-panoptic-data-augmentation
Repo
Framework

A study of problems with multiple interdependent components - Part I


Title	A study of problems with multiple interdependent components - Part I
Authors	Mohamed El Yafrani
Abstract	Recognising that real-world optimisation problems have multiple interdependent components can be quite easy. However, providing a generic and formal model for dependencies between components can be a tricky task. In fact, a PMIC can be considered simply as a single optimisation problem and the dependencies between components could be investigated by studying the decomposability of the problem and the correlations between the sub-problems. In this work, we attempt to define PMICs by reasoning from a reverse perspective. Instead of considering a decomposable problem, we model multiple problems (the components) and define how these components could be connected. In this document, we introduce notions related to problems with mutliple interndependent components. We start by introducing realistic examples from logistics and supply chain management to illustrate the composite nature and dependencies in these problems. Afterwards, we provide our attempt to formalise and classify dependency in multi-component problems.
Tasks
Published	2019-03-01
URL	http://arxiv.org/abs/1903.03557v2
PDF	http://arxiv.org/pdf/1903.03557v2.pdf
PWC	https://paperswithcode.com/paper/a-study-of-problems-with-multiple
Repo
Framework

Quantitative Mitigation of Timing Side Channels


Title	Quantitative Mitigation of Timing Side Channels
Authors	Saeid Tizpaz-Niari, Pavol Cerny, Ashutosh Trivedi
Abstract	Timing side channels pose a significant threat to the security and privacy of software applications. We propose an approach for mitigating this problem by decreasing the strength of the side channels as measured by entropy-based objectives, such as min-guess entropy. Our goal is to minimize the information leaks while guaranteeing a user-specified maximal acceptable performance overhead. We dub the decision version of this problem Shannon mitigation, and consider two variants, deterministic and stochastic. First, we show the deterministic variant is NP-hard. However, we give a polynomial algorithm that finds an optimal solution from a restricted set. Second, for the stochastic variant, we develop an algorithm that uses optimization techniques specific to the entropy-based objective used. For instance, for min-guess entropy, we used mixed integer-linear programming. We apply the algorithm to a threat model where the attacker gets to make functional observations, that is, where she observes the running time of the program for the same secret value combined with different public input values. Existing mitigation approaches do not give confidentiality or performance guarantees for this threat model. We evaluate our tool SCHMIT on a number of micro-benchmarks and real-world applications with different entropy-based objectives. In contrast to the existing mitigation approaches, we show that in the functional-observation threat model, SCHMIT is scalable and able to maximize confidentiality under the performance overhead bound.
Tasks
Published	2019-06-21
URL	https://arxiv.org/abs/1906.08957v1
PDF	https://arxiv.org/pdf/1906.08957v1.pdf
PWC	https://paperswithcode.com/paper/quantitative-mitigation-of-timing-side
Repo
Framework

Deception through Half-Truths


Title	Deception through Half-Truths
Authors	Andrew Estornell, Sanmay Das, Yevgeniy Vorobeychik
Abstract	Deception is a fundamental issue across a diverse array of settings, from cybersecurity, where decoys (e.g., honeypots) are an important tool, to politics that can feature politically motivated “leaks” and fake news about candidates.Typical considerations of deception view it as providing false information.However, just as important but less frequently studied is a more tacit form where information is strategically hidden or leaked.We consider the problem of how much an adversary can affect a principal’s decision by “half-truths”, that is, by masking or hiding bits of information, when the principal is oblivious to the presence of the adversary. The principal’s problem can be modeled as one of predicting future states of variables in a dynamic Bayes network, and we show that, while theoretically the principal’s decisions can be made arbitrarily bad, the optimal attack is NP-hard to approximate, even under strong assumptions favoring the attacker. However, we also describe an important special case where the dependency of future states on past states is additive, in which we can efficiently compute an approximately optimal attack. Moreover, in networks with a linear transition function we can solve the problem optimally in polynomial time.
Tasks
Published	2019-11-14
URL	https://arxiv.org/abs/1911.05885v1
PDF	https://arxiv.org/pdf/1911.05885v1.pdf
PWC	https://paperswithcode.com/paper/deception-through-half-truths
Repo
Framework

A Logic-Based Framework Leveraging Neural Networks for Studying the Evolution of Neurological Disorders


Title	A Logic-Based Framework Leveraging Neural Networks for Studying the Evolution of Neurological Disorders
Authors	Francesco Calimeri, Francesco Cauteruccio, Luca Cinelli, Aldo Marzullo, Claudio Stamile, Giorgio Terracina, Francoise Durand-Dubief, Dominique Sappey-Marinier
Abstract	Deductive formalisms have been strongly developed in recent years; among them, Answer Set Programming (ASP) gained some momentum, and has been lately fruitfully employed in many real-world scenarios. Nonetheless, in spite of a large number of success stories in relevant application areas, and even in industrial contexts, deductive reasoning cannot be considered the ultimate, comprehensive solution to AI; indeed, in several contexts, other approaches result to be more useful. Typical Bioinformatics tasks, for instance classification, are currently carried out mostly by Machine Learning (ML) based solutions. In this paper, we focus on the relatively new problem of analyzing the evolution of neurological disorders. In this context, ML approaches already demonstrated to be a viable solution for classification tasks; here, we show how ASP can play a relevant role in the brain evolution simulation task. In particular, we propose a general and extensible framework to support physicians and researchers at understanding the complex mechanisms underlying neurological disorders. The framework relies on a combined use of ML and ASP, and is general enough to be applied in several other application scenarios, which are outlined in the paper.
Tasks
Published	2019-10-21
URL	https://arxiv.org/abs/1910.09472v1
PDF	https://arxiv.org/pdf/1910.09472v1.pdf
PWC	https://paperswithcode.com/paper/a-logic-based-framework-leveraging-neural
Repo
Framework

BINOCULARS for Efficient, Nonmyopic Sequential Experimental Design


Title	BINOCULARS for Efficient, Nonmyopic Sequential Experimental Design
Authors	Shali Jiang, Henry Chai, Javier Gonzalez, Roman Garnett
Abstract	Finite-horizon sequential experimental design (SED) arises naturally in many contexts, including hyperparameter tuning in machine learning among more traditional settings. Computing the optimal policy for such problems requires solving Bellman equations, which are generally intractable. Most existing work resorts to severely myopic approximations by limiting the decision horizon to only a single time-step, which can underweight exploration in favor of exploitation. We present BINOCULARS: Batch-Informed NOnmyopic Choices, Using Long-horizons for Adaptive, Rapid SED, a general framework for deriving efficient, nonmyopic approximations to the optimal experimental policy. Our key idea is simple and surprisingly effective: we first compute a one-step optimal batch of experiments, then select a single point from this batch to evaluate. We realize BINOCULARS for Bayesian optimization and Bayesian quadrature – two notable SED problems with radically different objectives – and demonstrate that BINOCULARS significantly outperforms myopic alternatives in real-world scenarios.
Tasks
Published	2019-09-10
URL	https://arxiv.org/abs/1909.04568v3
PDF	https://arxiv.org/pdf/1909.04568v3.pdf
PWC	https://paperswithcode.com/paper/efficient-nonmyopic-bayesian-optimization-and
Repo
Framework

AI Décor


Title	AI Décor
Authors	Sharmin Pathan
Abstract	Confused about renovating your space? Choosing the perfect color for your walls is always a challenging task. One does rounds of color consultation and several patch tests. This paper proposes an AI tool to pitch paint based on attributes of your room and other furniture, and visualize it on your walls. It makes the color selection process a whole lot easier. It basically takes in images of a room, detects furniture objects using YOLO object detection. Once these objects have been detected, the tool picks out color of the object. Later this object specific information gets appended to the room attributes (room_type, room_size, preferred_tone, etc) and a deep neural net is trained to make predictions for color/texture/wallpaper for the walls. Finally, these predictions are visualized on the walls from the images provided. The idea is to take the knowledge of a color consultant and pitch colors that suit the walls and provide a good contrast with the furniture and harmonize with different colors in the room. Transfer learning for YOLO object detection from the COCO dataset was used as a starting point and the weights were later fine-tuned by training on additional images. The model was trained on 1000 records listing the room and furniture attributes, to predict colors. Given the room image, this method finds the best color scheme for the walls. These predictions are then visualized on the walls in the image using image segmentation. The results are visually appealing and automatically enhance the color look-and-feel.
Tasks	Object Detection, Semantic Segmentation, Transfer Learning
Published	2019-07-31
URL	https://arxiv.org/abs/1908.04344v1
PDF	https://arxiv.org/pdf/1908.04344v1.pdf
PWC	https://paperswithcode.com/paper/ai-decor
Repo
Framework

Development of Deep Learning Based Natural Language Processing Model for Turkish


Title	Development of Deep Learning Based Natural Language Processing Model for Turkish
Authors	Baris Baburoglu, Adem Tekerek, Mehmet Tekerek
Abstract	Natural language is one of the most fundamental features that distinguish people from other living things and enable people to communicate each other. Language is a tool that enables people to express their feelings and thoughts and to transfers cultures through generations. Texts and audio are examples of natural language in daily life. In the natural language, many words disappear in time, on the other hand new words are derived. Therefore, while the process of natural language processing (NLP) is complex even for human, it is difficult to process in computer system. The area of linguistics examines how people use language. NLP, which requires the collaboration of linguists and computer scientists, plays an important role in human computer interaction. Studies in NLP have increased with the use of artificial intelligence technologies in the field of linguistics. With the deep learning methods which are one of the artificial intelligence study areas, platforms close to natural language are being developed. Developed platforms for language comprehension, machine translation and part of speech (POS) tagging benefit from deep learning methods. Recurrent Neural Network (RNN), one of the deep learning architectures, is preferred for processing sequential data such as text or audio data. In this study, Turkish POS tagging model has been proposed by using Bidirectional Long-Short Term Memory (BLSTM) which is an RNN type. The proposed POS tagging model is provided to natural language researchers with a platform that allows them to perform and use their own analysis. In the development phase of the platform developed by using BLSTM, the error rate of the POS tagger has been reduced by taking feedback with expert opinion.
Tasks	Machine Translation, Part-Of-Speech Tagging
Published	2019-05-07
URL	https://arxiv.org/abs/1905.05699v1
PDF	https://arxiv.org/pdf/1905.05699v1.pdf
PWC	https://paperswithcode.com/paper/190505699
Repo
Framework

Robust and Sample Optimal Algorithms for PSD Low-Rank Approximation


Title	Robust and Sample Optimal Algorithms for PSD Low-Rank Approximation
Authors	Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff
Abstract	Recently, Musco and Woodruff (FOCS, 2017) showed that given an $n \times n$ positive semidefinite (PSD) matrix $A$, it is possible to compute a relative-error $(1+\epsilon)$-approximate low-rank approximation to $A$ by querying $\widetilde{O}(nk/\epsilon^{2.5})$ entries of $A$ in time $\widetilde{O}(nk/\epsilon^{2.5} +n k^{\omega-1}/\epsilon^{2(\omega-1)})$. They also showed that any relative-error low-rank approximation algorithm must query $\widetilde{\Omega}(nk/\epsilon)$ entries of $A$, and closing this gap is an important open question. Our main result is to resolve this question by showing an algorithm that queries an optimal $\widetilde{O}(nk/\epsilon)$ entries of $A$ and outputs a relative-error low-rank approximation in $\widetilde{O}(n\cdot(k/\epsilon)^{\omega-1})$ time. Note, our running time improves that of Musco and Woodruff, and matches the information-theoretic lower bound if the matrix-multiplication exponent $\omega$ is $2$. Next, we introduce a new robust low-rank approximation model which captures PSD matrices that have been corrupted with noise. We assume that the Frobenius norm of the corruption is bounded. Here, we relax the notion of approximation to additive-error, since it is information-theoretically impossible to obtain a relative-error approximation in this setting. While a sample complexity lower bound precludes sublinear algorithms for arbitrary PSD matrices, we provide the first sublinear time and query algorithms when the corruption on the diagonal entries is bounded. As a special case, we show sample-optimal sublinear time algorithms for low-rank approximation of correlation matrices corrupted by noise.
Tasks
Published	2019-12-09
URL	https://arxiv.org/abs/1912.04177v2
PDF	https://arxiv.org/pdf/1912.04177v2.pdf
PWC	https://paperswithcode.com/paper/robust-and-sample-optimal-algorithms-for-psd
Repo
Framework

On the modes of convergence of Stochastic Optimistic Mirror Descent (OMD) for saddle point problems


Title	On the modes of convergence of Stochastic Optimistic Mirror Descent (OMD) for saddle point problems
Authors	Yanting Ma, Shuchin Aeron, Hassan Mansour
Abstract	In this article, we study the convergence of Mirror Descent (MD) and Optimistic Mirror Descent (OMD) for saddle point problems satisfying the notion of coherence as proposed in Mertikopoulos et al. We prove convergence of OMD with exact gradients for coherent saddle point problems, and show that monotone convergence only occurs after some sufficiently large number of iterations. This is in contrast to the claim in Mertikopoulos et al. of monotone convergence of OMD with exact gradients for coherent saddle point problems. Besides highlighting this important subtlety, we note that the almost sure convergence guarantees of MD and OMD with stochastic gradients for strictly coherent saddle point problems that are claimed in Mertikopoulos et al. are not fully justified by their proof. As such, we fill out the missing details in the proof and as a result have only been able to prove convergence with high probability. We would like to note that our analysis relies heavily on the core ideas and proof techniques introduced in Zhou et al. and Mertikopoulos et al., and we only aim to re-state and correct the results in light of what we were able to prove rigorously while filling in the much needed missing details in their proofs.
Tasks
Published	2019-08-02
URL	https://arxiv.org/abs/1908.01071v1
PDF	https://arxiv.org/pdf/1908.01071v1.pdf
PWC	https://paperswithcode.com/paper/on-the-modes-of-convergence-of-stochastic
Repo
Framework

A Grounded Unsupervised Universal Part-of-Speech Tagger for Low-Resource Languages


Title	A Grounded Unsupervised Universal Part-of-Speech Tagger for Low-Resource Languages
Authors	Ronald Cardenas, Ying Lin, Heng Ji, Jonathan May
Abstract	Unsupervised part of speech (POS) tagging is often framed as a clustering problem, but practical taggers need to \textit{ground} their clusters as well. Grounding generally requires reference labeled data, a luxury a low-resource language might not have. In this work, we describe an approach for low-resource unsupervised POS tagging that yields fully grounded output and requires no labeled training data. We find the classic method of Brown et al. (1992) clusters well in our use case and employ a decipherment-based approach to grounding. This approach presumes a sequence of cluster IDs is a ciphertext' and seeks a POS tag-to-cluster ID mapping that will reveal the POS sequence. We show intrinsically that, despite the difficulty of the task, we obtain reasonable performance across a variety of languages. We also show extrinsically that incorporating our POS tagger into a name tagger leads to state-of-the-art tagging performance in Sinhalese and Kinyarwanda, two languages with nearly no labeled POS data available. We further demonstrate our tagger's utility by incorporating it into a true zero-resource’ variant of the Malopa (Ammar et al., 2016) dependency parser model that removes the current reliance on multilingual resources and gold POS tags for new languages. Experiments show that including our tagger makes up much of the accuracy lost when gold POS tags are unavailable.
Tasks	Part-Of-Speech Tagging
Published	2019-04-10
URL	http://arxiv.org/abs/1904.05426v1
PDF	http://arxiv.org/pdf/1904.05426v1.pdf
PWC	https://paperswithcode.com/paper/a-grounded-unsupervised-universal-part-of
Repo
Framework

Measuring Unfairness through Game-Theoretic Interpretability


Title	Measuring Unfairness through Game-Theoretic Interpretability
Authors	Juliana Cesaro, Fabio G. Cozman
Abstract	One often finds in the literature connections between measures of fairness and measures of feature importance employed to interpret trained classifiers. However, there seems to be no study that compares fairness measures and feature importance measures. In this paper we propose ways to evaluate and compare such measures. We focus in particular on SHAP, a game-theoretic measure of feature importance; we present results for a number of unfairness-prone datasets.
Tasks	Feature Importance
Published	2019-10-12
URL	https://arxiv.org/abs/1910.05591v1
PDF	https://arxiv.org/pdf/1910.05591v1.pdf
PWC	https://paperswithcode.com/paper/measuring-unfairness-through-game-theoretic
Repo
Framework

Information-Bottleneck Approach to Salient Region Discovery


Title	Information-Bottleneck Approach to Salient Region Discovery
Authors	Andrey Zhmoginov, Ian Fischer, Mark Sandler
Abstract	We propose a new method for learning image attention masks in a semi-supervised setting based on the Information Bottleneck principle. Provided with a set of labeled images, the mask generation model is minimizing mutual information between the input and the masked image while maximizing the mutual information between the same masked image and the image label. In contrast with other approaches, our attention model produces a Boolean rather than a continuous mask, entirely concealing the information in masked-out pixels. Using a set of synthetic datasets based on MNIST and CIFAR10 and the SVHN datasets, we demonstrate that our method can successfully attend to features known to define the image class.
Tasks
Published	2019-07-22
URL	https://arxiv.org/abs/1907.09578v2
PDF	https://arxiv.org/pdf/1907.09578v2.pdf
PWC	https://paperswithcode.com/paper/information-bottleneck-approach-to-salient
Repo
Framework

Robust One-Bit Recovery via ReLU Generative Networks: Near Optimal Statistical Rate and Global Landscape Analysis


Title	Robust One-Bit Recovery via ReLU Generative Networks: Near Optimal Statistical Rate and Global Landscape Analysis
Authors	Shuang Qiu, Xiaohan Wei, Zhuoran Yang
Abstract	We study the robust one-bit compressed sensing problem whose goal is to design an algorithm that faithfully recovers any sparse target vector $\theta_0\in\mathbb{R}^d$ uniformly $m$ quantized noisy measurements. Under the assumption that the measurements are sub-Gaussian random vectors, to recover any $k$-sparse $\theta_0$ ($k\ll d$) uniformly up to an error $\varepsilon$ with high probability, the best known computationally tractable algorithm requires $m\geq\tilde{\mathcal{O}}(k\log d/\varepsilon^4)$ measurements. In this paper, we consider a new framework for the one-bit sensing problem where the sparsity is implicitly enforced via mapping a low dimensional representation $x_0 \in \mathbb{R}^k$ through a known $n$-layer ReLU generative network $G:\mathbb{R}^k\rightarrow\mathbb{R}^d$. Such a framework poses low-dimensional priors on $\theta_0$ without a known basis. We propose to recover the target $G(x_0)$ via an unconstrained empirical risk minimization (ERM) problem under a much weaker sub-exponential measurement assumption. For such a problem, we establish a joint statistical and computational analysis. In particular, we prove that the ERM estimator in this new framework achieves a statistical rate of $m=\tilde{\mathcal{O}}(kn \log d /\varepsilon^2)$ recovering any $G(x_0)$ uniformly up to an error $\varepsilon$. When network is shallow (i.e., $n$ is small), we show this rate matches the information-theoretic lower bound up to logarithm factors on $\varepsilon^{-1}$. From the lens of computation, despite non-convexity, we prove that the objective of our ERM problem has no spurious stationary point, that is, any stationary point are equally good for recovering the true target up to scaling with a certain accuracy.
Tasks
Published	2019-08-14
URL	https://arxiv.org/abs/1908.05368v2
PDF	https://arxiv.org/pdf/1908.05368v2.pdf
PWC	https://paperswithcode.com/paper/robust-one-bit-recovery-via-relu-generative
Repo
Framework