October 18, 2019

3014 words 15 mins read

Paper Group ANR 548

Observability Properties of Colored Graphs. Learning on Hypergraphs with Sparsity. Multi-Target Prediction: A Unifying View on Problems and Methods. Detection based Defense against Adversarial Examples from the Steganalysis Point of View. Deep Convolutional Neural Networks for Map-Type Classification. Towards Effective Deep Embedding for Zero-Shot …

Observability Properties of Colored Graphs


Title	Observability Properties of Colored Graphs
Authors	Mark Chilenski, George Cybenko, Isaac Dekine, Piyush Kumar, Gil Raz
Abstract	A colored graph is a directed graph in which nodes or edges have been assigned colors that are not necessarily unique. Observability problems in such graphs consider whether an agent observing the colors of edges or nodes traversed on a path in the graph can determine which node they are at currently or which nodes were visited earlier in the traversal. Previous research efforts have identified several different notions of observability as well as the associated properties of graphs for which those observability properties hold. This paper unifies the prior work into a common framework with several new results about relationships between those notions and associated graph properties. The new framework provides an intuitive way to reason about the attainable accuracy as a function of lag and time spent observing, and identifies simple modifications to improve the observability of a given graph. We show that one form of the graph modification problem is in NP-Complete. The intuition of the new framework is borne out with numerical experiments. This work has implications for problems that can be described in terms of an agent traversing a colored graph, including the reconstruction of hidden states in a hidden Markov model (HMM).
Tasks
Published	2018-11-09
URL	https://arxiv.org/abs/1811.04803v2
PDF	https://arxiv.org/pdf/1811.04803v2.pdf
PWC	https://paperswithcode.com/paper/observability-properties-of-colored-graphs
Repo
Framework

Learning on Hypergraphs with Sparsity


Title	Learning on Hypergraphs with Sparsity
Authors	Canh Hao Nguyen, Hiroshi Mamitsuka
Abstract	Hypergraph is a general way of representing high-order relations on a set of objects. It is a generalization of graph, in which only pairwise relations can be represented. It finds applications in various domains where relationships of more than two objects are observed. On a hypergraph, as a generalization of graph, one wishes to learn a smooth function with respect to its topology. A fundamental issue is to find suitable smoothness measures of functions on the nodes of a graph/hypergraph. We show a general framework that generalizes previously proposed smoothness measures and also gives rise to new ones. To address the problem of irrelevant or noisy data, we wish to incorporate sparse learning framework into learning on hypergraphs. We propose sparsely smooth formulations that learn smooth functions and induce sparsity on hypergraphs at both hyperedge and node levels. We show their properties and sparse support recovery results. We conduct experiments to show that our sparsely smooth models have benefits to irrelevant and noisy data, and usually give similar or improved performances compared to dense models.
Tasks	Sparse Learning
Published	2018-04-03
URL	http://arxiv.org/abs/1804.00836v1
PDF	http://arxiv.org/pdf/1804.00836v1.pdf
PWC	https://paperswithcode.com/paper/learning-on-hypergraphs-with-sparsity
Repo
Framework

Multi-Target Prediction: A Unifying View on Problems and Methods


Title	Multi-Target Prediction: A Unifying View on Problems and Methods
Authors	Willem Waegeman, Krzysztof Dembczynski, Eyke Huellermeier
Abstract	Multi-target prediction (MTP) is concerned with the simultaneous prediction of multiple target variables of diverse type. Due to its enormous application potential, it has developed into an active and rapidly expanding research field that combines several subfields of machine learning, including multivariate regression, multi-label classification, multi-task learning, dyadic prediction, zero-shot learning, network inference, and matrix completion. In this paper, we present a unifying view on MTP problems and methods. First, we formally discuss commonalities and differences between existing MTP problems. To this end, we introduce a general framework that covers the above subfields as special cases. As a second contribution, we provide a structured overview of MTP methods. This is accomplished by identifying a number of key properties, which distinguish such methods and determine their suitability for different types of problems. Finally, we also discuss a few challenges for future research.
Tasks	Matrix Completion, Multi-Label Classification, Multi-Task Learning, Zero-Shot Learning
Published	2018-09-07
URL	http://arxiv.org/abs/1809.02352v1
PDF	http://arxiv.org/pdf/1809.02352v1.pdf
PWC	https://paperswithcode.com/paper/multi-target-prediction-a-unifying-view-on
Repo
Framework

Detection based Defense against Adversarial Examples from the Steganalysis Point of View


Title	Detection based Defense against Adversarial Examples from the Steganalysis Point of View
Authors	Jiayang Liu, Weiming Zhang, Yiwei Zhang, Dongdong Hou, Yujia Liu, Hongyue Zha, Nenghai Yu
Abstract	Deep Neural Networks (DNNs) have recently led to significant improvements in many fields. However, DNNs are vulnerable to adversarial examples which are samples with imperceptible perturbations while dramatically misleading the DNNs. Moreover, adversarial examples can be used to perform an attack on various kinds of DNN based systems, even if the adversary has no access to the underlying model. Many defense methods have been proposed, such as obfuscating gradients of the networks or detecting adversarial examples. However it is proved out that these defense methods are not effective or cannot resist secondary adversarial attacks. In this paper, we point out that steganalysis can be applied to adversarial examples detection, and propose a method to enhance steganalysis features by estimating the probability of modifications caused by adversarial attacks. Experimental results show that the proposed method can accurately detect adversarial examples. Moreover, secondary adversarial attacks cannot be directly performed to our method because our method is not based on a neural network but based on high-dimensional artificial features and FLD (Fisher Linear Discriminant) ensemble.
Tasks
Published	2018-06-21
URL	http://arxiv.org/abs/1806.09186v3
PDF	http://arxiv.org/pdf/1806.09186v3.pdf
PWC	https://paperswithcode.com/paper/detection-based-defense-against-adversarial
Repo
Framework

Deep Convolutional Neural Networks for Map-Type Classification


Title	Deep Convolutional Neural Networks for Map-Type Classification
Authors	Xiran Zhou, Wenwen Li, Samantha T. Arundel, Jun Liu
Abstract	Maps are an important medium that enable people to comprehensively understand the configuration of cultural activities and natural elements over different times and places. Although massive maps are available in the digital era, how to effectively and accurately access the required map remains a challenge today. Previous works partially related to map-type classification mainly focused on map comparison and map matching at the local scale. The features derived from local map areas might be insufficient to characterize map content. To facilitate establishing an automatic approach for accessing the needed map, this paper reports our investigation into using deep learning techniques to recognize seven types of map, including topographic map, terrain map, physical map, urban scene map, the National Map, 3D map, nighttime map, orthophoto map, and land cover classification map. Experimental results show that the state-of-the-art deep convolutional neural networks can support automatic map-type classification. Additionally, the classification accuracy varies according to different map-types. We hope our work can contribute to the implementation of deep learning techniques in cartographical community and advance the progress of Geographical Artificial Intelligence (GeoAI).
Tasks
Published	2018-05-26
URL	http://arxiv.org/abs/1805.10402v1
PDF	http://arxiv.org/pdf/1805.10402v1.pdf
PWC	https://paperswithcode.com/paper/deep-convolutional-neural-networks-for-map
Repo
Framework

Towards Effective Deep Embedding for Zero-Shot Learning


Title	Towards Effective Deep Embedding for Zero-Shot Learning
Authors	Lei Zhang, Peng Wang, Lingqiao Liu, Chunhua Shen, Wei Wei, Yannning Zhang, Anton Van Den Hengel
Abstract	Zero-shot learning (ZSL) can be formulated as a cross-domain matching problem: after being projected into a joint embedding space, a visual sample will match against all candidate class-level semantic descriptions and be assigned to the nearest class. In this process, the embedding space underpins the success of such matching and is crucial for ZSL. In this paper, we conduct an in-depth study on the construction of embedding space for ZSL and posit that an ideal embedding space should satisfy two criteria: intra-class compactness and inter-class separability. While the former encourages the embeddings of visual samples of one class to distribute tightly close to the semantic description embedding of this class, the latter requires embeddings from different classes to be well separated from each other. Towards this goal, we present a simple but effective two-branch network to simultaneously map semantic descriptions and visual samples into a joint space, on which visual embeddings are forced to regress to their class-level semantic embeddings and the embeddings crossing classes are required to be distinguishable by a trainable classifier. Furthermore, we extend our method to a transductive setting to better handle the model bias problem in ZSL (i.e., samples from unseen classes tend to be categorized into seen classes) with minimal extra supervision. Specifically, we propose a pseudo labeling strategy to progressively incorporate the testing samples into the training process and thus balance the model between seen and unseen classes. Experimental results on five standard ZSL datasets show the superior performance of the proposed method and its transductive extension.
Tasks	Zero-Shot Learning
Published	2018-08-30
URL	http://arxiv.org/abs/1808.10075v2
PDF	http://arxiv.org/pdf/1808.10075v2.pdf
PWC	https://paperswithcode.com/paper/towards-effective-deep-embedding-for-zero
Repo
Framework

On-device Scalable Image-based Localization via Prioritized Cascade Search and Fast One-Many RANSAC


Title	On-device Scalable Image-based Localization via Prioritized Cascade Search and Fast One-Many RANSAC
Authors	Ngoc-Trung Tran, Dang-Khoa Le Tan, Anh-Dzung Doan, Thanh-Toan Do, Tuan-Anh Bui, Mengxuan Tan, Ngai-Man Cheung
Abstract	We present the design of an entire on-device system for large-scale urban localization using images. The proposed design integrates compact image retrieval and 2D-3D correspondence search to estimate the location in extensive city regions. Our design is GPS agnostic and does not require network connection. In order to overcome the resource constraints of mobile devices, we propose a system design that leverages the scalability advantage of image retrieval and accuracy of 3D model-based localization. Furthermore, we propose a new hashing-based cascade search for fast computation of 2D-3D correspondences. In addition, we propose a new one-many RANSAC for accurate pose estimation. The new one-many RANSAC addresses the challenge of repetitive building structures (e.g. windows, balconies) in urban localization. Extensive experiments demonstrate that our 2D-3D correspondence search achieves state-of-the-art localization accuracy on multiple benchmark datasets. Furthermore, our experiments on a large Google Street View (GSV) image dataset show the potential of large-scale localization entirely on a typical mobile device.
Tasks	Image-Based Localization, Image Retrieval, Pose Estimation
Published	2018-02-10
URL	http://arxiv.org/abs/1802.03510v2
PDF	http://arxiv.org/pdf/1802.03510v2.pdf
PWC	https://paperswithcode.com/paper/on-device-scalable-image-based-localization
Repo
Framework

Multi-Label Zero-Shot Learning with Transfer-Aware Label Embedding Projection


Title	Multi-Label Zero-Shot Learning with Transfer-Aware Label Embedding Projection
Authors	Meng Ye, Yuhong Guo
Abstract	Zero-shot learning transfers knowledge from seen classes to novel unseen classes to reduce human labor of labelling data for building new classifiers. Much effort on zero-shot learning however has focused on the standard multi-class setting, the more challenging multi-label zero-shot problem has received limited attention. In this paper we propose a transfer-aware embedding projection approach to tackle multi-label zero-shot learning. The approach projects the label embedding vectors into a low-dimensional space to induce better inter-label relationships and explicitly facilitate information transfer from seen labels to unseen labels, while simultaneously learning a max-margin multi-label classifier with the projected label embeddings. Auxiliary information can be conveniently incorporated to guide the label embedding projection to further improve label relation structures for zero-shot knowledge transfer. We conduct experiments for zero-shot multi-label image classification. The results demonstrate the efficacy of the proposed approach.
Tasks	Image Classification, Transfer Learning, Zero-Shot Learning
Published	2018-08-07
URL	http://arxiv.org/abs/1808.02474v1
PDF	http://arxiv.org/pdf/1808.02474v1.pdf
PWC	https://paperswithcode.com/paper/multi-label-zero-shot-learning-with-transfer
Repo
Framework

Human Action Adverb Recognition: ADHA Dataset and A Three-Stream Hybrid Model


Title	Human Action Adverb Recognition: ADHA Dataset and A Three-Stream Hybrid Model
Authors	Bo Pang, Kaiwen Zha, Cewu Lu
Abstract	We introduce the first benchmark for a new problem — recognizing human action adverbs (HAA): “Adverbs Describing Human Actions” (ADHA). This is the first step for computer vision to change over from pattern recognition to real AI. We demonstrate some key features of ADHA: a semantically complete set of adverbs describing human actions, a set of common, describable human actions, and an exhaustive labeling of simultaneously emerging actions in each video. We commit an in-depth analysis on the implementation of current effective models in action recognition and image captioning on adverb recognition, and the results show that such methods are unsatisfactory. Moreover, we propose a novel three-stream hybrid model to deal the HAA problem, which achieves a better result.
Tasks	Image Captioning, Temporal Action Localization
Published	2018-02-04
URL	http://arxiv.org/abs/1802.01144v2
PDF	http://arxiv.org/pdf/1802.01144v2.pdf
PWC	https://paperswithcode.com/paper/human-action-adverb-recognition-adha-dataset
Repo
Framework

Alpha-Beta Divergence For Variational Inference


Title	Alpha-Beta Divergence For Variational Inference
Authors	Jean-Baptiste Regli, Ricardo Silva
Abstract	This paper introduces a variational approximation framework using direct optimization of what is known as the {\it scale invariant Alpha-Beta divergence} (sAB divergence). This new objective encompasses most variational objectives that use the Kullback-Leibler, the R{'e}nyi or the gamma divergences. It also gives access to objective functions never exploited before in the context of variational inference. This is achieved via two easy to interpret control parameters, which allow for a smooth interpolation over the divergence space while trading-off properties such as mass-covering of a target distribution and robustness to outliers in the data. Furthermore, the sAB variational objective can be optimized directly by repurposing existing methods for Monte Carlo computation of complex variational objectives, leading to estimates of the divergence instead of variational lower bounds. We show the advantages of this objective on Bayesian models for regression problems.
Tasks
Published	2018-05-02
URL	http://arxiv.org/abs/1805.01045v2
PDF	http://arxiv.org/pdf/1805.01045v2.pdf
PWC	https://paperswithcode.com/paper/alpha-beta-divergence-for-variational
Repo
Framework

Privacy Partitioning: Protecting User Data During the Deep Learning Inference Phase


Title	Privacy Partitioning: Protecting User Data During the Deep Learning Inference Phase
Authors	Jianfeng Chi, Emmanuel Owusu, Xuwang Yin, Tong Yu, William Chan, Patrick Tague, Yuan Tian
Abstract	We present a practical method for protecting data during the inference phase of deep learning based on bipartite topology threat modeling and an interactive adversarial deep network construction. We term this approach \emph{Privacy Partitioning}. In the proposed framework, we split the machine learning models and deploy a few layers into users’ local devices, and the rest of the layers into a remote server. We propose an approach to protect user’s data during the inference phase, while still achieve good classification accuracy. We conduct an experimental evaluation of this approach on benchmark datasets of three computer vision tasks. The experimental results indicate that this approach can be used to significantly attenuate the capacity for an adversary with access to the state-of-the-art deep network’s intermediate states to learn privacy-sensitive inputs to the network. For example, we demonstrate that our approach can prevent attackers from inferring the private attributes such as gender from the Face image dataset without sacrificing the classification accuracy of the original machine learning task such as Face Identification.
Tasks	Face Identification
Published	2018-12-07
URL	http://arxiv.org/abs/1812.02863v1
PDF	http://arxiv.org/pdf/1812.02863v1.pdf
PWC	https://paperswithcode.com/paper/privacy-partitioning-protecting-user-data
Repo
Framework

Structure Learning for Relational Logistic Regression: An Ensemble Approach


Title	Structure Learning for Relational Logistic Regression: An Ensemble Approach
Authors	Nandini Ramanan, Gautam Kunapuli, Tushar Khot, Bahare Fatemi, Seyed Mehran Kazemi, David Poole, Kristian Kersting, Sriraam Natarajan
Abstract	We consider the problem of learning Relational Logistic Regression (RLR). Unlike standard logistic regression, the features of RLRs are first-order formulae with associated weight vectors instead of scalar weights. We turn the problem of learning RLR to learning these vector-weighted formulae and develop a learning algorithm based on the recently successful functional-gradient boosting methods for probabilistic logic models. We derive the functional gradients and show how weights can be learned simultaneously in an efficient manner. Our empirical evaluation on standard and novel data sets demonstrates the superiority of our approach over other methods for learning RLR.
Tasks
Published	2018-08-06
URL	http://arxiv.org/abs/1808.02123v1
PDF	http://arxiv.org/pdf/1808.02123v1.pdf
PWC	https://paperswithcode.com/paper/structure-learning-for-relational-logistic
Repo
Framework

Representational Power of ReLU Networks and Polynomial Kernels: Beyond Worst-Case Analysis


Title	Representational Power of ReLU Networks and Polynomial Kernels: Beyond Worst-Case Analysis
Authors	Frederic Koehler, Andrej Risteski
Abstract	There has been a large amount of interest, both in the past and particularly recently, into the power of different families of universal approximators, e.g. ReLU networks, polynomials, rational functions. However, current research has focused almost exclusively on understanding this problem in a worst-case setting, e.g. bounding the error of the best infinity-norm approximation in a box. In this setting a high-degree polynomial is required to even approximate a single ReLU. However, in real applications with high dimensional data we expect it is only important to approximate the desired function well on certain relevant parts of its domain. With this motivation, we analyze the ability of neural networks and polynomial kernels of bounded degree to achieve good statistical performance on a simple, natural inference problem with sparse latent structure. We give almost-tight bounds on the performance of both neural networks and low degree polynomials for this problem. Our bounds for polynomials involve new techniques which may be of independent interest and show major qualitative differences with what is known in the worst-case setting.
Tasks
Published	2018-05-29
URL	http://arxiv.org/abs/1805.11405v1
PDF	http://arxiv.org/pdf/1805.11405v1.pdf
PWC	https://paperswithcode.com/paper/representational-power-of-relu-networks-and
Repo
Framework

How Could Polyhedral Theory Harness Deep Learning?


Title	How Could Polyhedral Theory Harness Deep Learning?
Authors	Thiago Serra, Christian Tjandraatmadja, Srikumar Ramalingam
Abstract	The holy grail of deep learning is to come up with an automatic method to design optimal architectures for different applications. In other words, how can we effectively dimension and organize neurons along the network layers based on the computational resources, input size, and amount of training data? We outline promising research directions based on polyhedral theory and mixed-integer representability that may offer an analytical approach to this question, in contrast to the empirical techniques often employed.
Tasks
Published	2018-06-17
URL	http://arxiv.org/abs/1806.06365v1
PDF	http://arxiv.org/pdf/1806.06365v1.pdf
PWC	https://paperswithcode.com/paper/how-could-polyhedral-theory-harness-deep
Repo
Framework

On the Non-asymptotic and Sharp Lower Tail Bounds of Random Variables


Title	On the Non-asymptotic and Sharp Lower Tail Bounds of Random Variables
Authors	Anru Zhang, Yuchen Zhou
Abstract	The non-asymptotic tail bounds of random variables play crucial roles in probability, statistics, and machine learning. Despite much success in developing upper tail bounds in literature, the lower tail bound results are relatively fewer. In this partly expository paper, we introduce systematic and user-friendly schemes for developing non-asymptotic lower tail bounds with elementary proofs. In addition, we develop sharp lower tail bounds for the sum of independent sub-Gaussian and sub-exponential random variables, which matches the classic Hoeffding-type and Bernstein-type concentration inequalities, respectively. We also provide non-asymptotic matching upper and lower tail bounds for a suite of distributions, including gamma, beta, (regular, weighted, and noncentral) chi-squared, binomial, Poisson, Irwin-Hall, etc. We apply the result to establish the matching upper and lower bounds for extreme value expectation of the sum of independent sub-Gaussian and sub-exponential random variables. A statistical application of signal identification from sparse heterogeneous mixtures is finally studied.
Tasks
Published	2018-10-21
URL	http://arxiv.org/abs/1810.09006v2
PDF	http://arxiv.org/pdf/1810.09006v2.pdf
PWC	https://paperswithcode.com/paper/on-the-non-asymptotic-and-sharp-lower-tail
Repo
Framework