October 16, 2019

3388 words 16 mins read

Paper Group ANR 1109

Paper Group ANR 1109

Detecting Adversarial Samples for Deep Neural Networks through Mutation Testing. Medical Images Analysis in Cancer Diagnostic. Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials. Towards Non-Parametric Learning to Rank. Bag-of-Visual-Words for Signature-Based Multi-Scri …

Detecting Adversarial Samples for Deep Neural Networks through Mutation Testing

Title Detecting Adversarial Samples for Deep Neural Networks through Mutation Testing
Authors Jingyi Wang, Jun Sun, Peixin Zhang, Xinyu Wang
Abstract Recently, it has been shown that deep neural networks (DNN) are subject to attacks through adversarial samples. Adversarial samples are often crafted through adversarial perturbation, i.e., manipulating the original sample with minor modifications so that the DNN model labels the sample incorrectly. Given that it is almost impossible to train perfect DNN, adversarial samples are shown to be easy to generate. As DNN are increasingly used in safety-critical systems like autonomous cars, it is crucial to develop techniques for defending such attacks. Existing defense mechanisms which aim to make adversarial perturbation challenging have been shown to be ineffective. In this work, we propose an alternative approach. We first observe that adversarial samples are much more sensitive to perturbations than normal samples. That is, if we impose random perturbations on a normal and an adversarial sample respectively, there is a significant difference between the ratio of label change due to the perturbations. Observing this, we design a statistical adversary detection algorithm called nMutant (inspired by mutation testing from software engineering community). Our experiments show that nMutant effectively detects most of the adversarial samples generated by recently proposed attacking methods. Furthermore, we provide an error bound with certain statistical significance along with the detection.
Tasks
Published 2018-05-14
URL http://arxiv.org/abs/1805.05010v2
PDF http://arxiv.org/pdf/1805.05010v2.pdf
PWC https://paperswithcode.com/paper/detecting-adversarial-samples-for-deep-neural
Repo
Framework

Medical Images Analysis in Cancer Diagnostic

Title Medical Images Analysis in Cancer Diagnostic
Authors Jelena Vasiljević, Ivica Milosavljević, Vladimir Krstić, Nataša Zivić, Lazar Berbakov, Luka Lopušina, Dhinaharan Nagamalai, Milutin Cerović
Abstract This paper shows results of computer analysis of images in the purpose of finding differences between medical images in order of their classifications in terms of separation malign tissue from a normal and benign tissue. The diagnostics of malign tissue is of the crucial importance in medicine. Therefore, ascertainment of the correlation between multifractals parameters and “chaotic” cells could be of the great appliance. This paper shows the application of multifractal analysis for additional help in cancer diagnosis, as well as diminishing. of the subjective factor and error probability
Tasks
Published 2018-10-05
URL http://arxiv.org/abs/1810.02495v1
PDF http://arxiv.org/pdf/1810.02495v1.pdf
PWC https://paperswithcode.com/paper/medical-images-analysis-in-cancer-diagnostic
Repo
Framework

Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials

Title Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials
Authors R. Ryan Williams
Abstract We consider the problem of representing Boolean functions exactly by “sparse” linear combinations (over $\mathbb{R}$) of functions from some “simple” class ${\cal C}$. In particular, given ${\cal C}$ we are interested in finding low-complexity functions lacking sparse representations. When ${\cal C}$ is the set of PARITY functions or the set of conjunctions, this sort of problem has a well-understood answer, the problem becomes interesting when ${\cal C}$ is “overcomplete” and the set of functions is not linearly independent. We focus on the cases where ${\cal C}$ is the set of linear threshold functions, the set of rectified linear units (ReLUs), and the set of low-degree polynomials over a finite field, all of which are well-studied in different contexts. We provide generic tools for proving lower bounds on representations of this kind. Applying these, we give several new lower bounds for “semi-explicit” Boolean functions. For example, we show there are functions in nondeterministic quasi-polynomial time that require super-polynomial size: $\bullet$ Depth-two neural networks with sign activation function, a special case of depth-two threshold circuit lower bounds. $\bullet$ Depth-two neural networks with ReLU activation function. $\bullet$ $\mathbb{R}$-linear combinations of $O(1)$-degree $\mathbb{F}_p$-polynomials, for every prime $p$ (related to problems regarding Higher-Order “Uncertainty Principles”). We also obtain a function in $E^{NP}$ requiring $2^{\Omega(n)}$ linear combinations. $\bullet$ $\mathbb{R}$-linear combinations of $ACC \circ THR$ circuits of polynomial size (further generalizing the recent lower bounds of Murray and the author). (The above is a shortened abstract. For the full abstract, see the paper.)
Tasks
Published 2018-02-26
URL http://arxiv.org/abs/1802.09121v1
PDF http://arxiv.org/pdf/1802.09121v1.pdf
PWC https://paperswithcode.com/paper/limits-on-representing-boolean-functions-by
Repo
Framework

Towards Non-Parametric Learning to Rank

Title Towards Non-Parametric Learning to Rank
Authors Ao Liu, Qiong Wu, Zhenming Liu, Lirong Xia
Abstract This paper studies a stylized, yet natural, learning-to-rank problem and points out the critical incorrectness of a widely used nearest neighbor algorithm. We consider a model with $n$ agents (users) ${x_i}{i \in [n]}$ and $m$ alternatives (items) ${y_j}{j \in [m]}$, each of which is associated with a latent feature vector. Agents rank items nondeterministically according to the Plackett-Luce model, where the higher the utility of an item to the agent, the more likely this item will be ranked high by the agent. Our goal is to find neighbors of an arbitrary agent or alternative in the latent space. We first show that the Kendall-tau distance based kNN produces incorrect results in our model. Next, we fix the problem by introducing a new algorithm with features constructed from “global information” of the data matrix. Our approach is in sharp contrast to most existing feature engineering methods. Finally, we design another new algorithm identifying similar alternatives. The construction of alternative features can be done using “local information,” highlighting the algorithmic difference between finding similar agents and similar alternatives.
Tasks Feature Engineering, Learning-To-Rank
Published 2018-07-09
URL http://arxiv.org/abs/1807.03395v1
PDF http://arxiv.org/pdf/1807.03395v1.pdf
PWC https://paperswithcode.com/paper/towards-non-parametric-learning-to-rank
Repo
Framework

Bag-of-Visual-Words for Signature-Based Multi-Script Document Retrieval

Title Bag-of-Visual-Words for Signature-Based Multi-Script Document Retrieval
Authors Ranju Mandal, Partha Pratim Roy, Umapada Pal, Michael Blumenstein
Abstract An end-to-end architecture for multi-script document retrieval using handwritten signatures is proposed in this paper. The user supplies a query signature sample and the system exclusively returns a set of documents that contain the query signature. In the first stage, a component-wise classification technique separates the potential signature components from all other components. A bag-of-visual-words powered by SIFT descriptors in a patch-based framework is proposed to compute the features and a Support Vector Machine (SVM)-based classifier was used to separate signatures from the documents. In the second stage, features from the foreground (i.e. signature strokes) and the background spatial information (i.e. background loops, reservoirs etc.) were combined to characterize the signature object to match with the query signature. Finally, three distance measures were used to match a query signature with the signature present in target documents for retrieval. The `Tobacco’ document database and an Indian script database containing 560 documents of Devanagari (Hindi) and Bangla scripts were used for the performance evaluation. The proposed system was also tested on noisy documents and promising results were obtained. A comparative study shows that the proposed method outperforms the state-of-the-art approaches. |
Tasks
Published 2018-07-18
URL http://arxiv.org/abs/1807.06772v1
PDF http://arxiv.org/pdf/1807.06772v1.pdf
PWC https://paperswithcode.com/paper/bag-of-visual-words-for-signature-based-multi
Repo
Framework

Learning to Branch

Title Learning to Branch
Authors Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, Ellen Vitercik
Abstract Tree search algorithms, such as branch-and-bound, are the most widely used tools for solving combinatorial and nonconvex problems. For example, they are the foremost method for solving (mixed) integer programs and constraint satisfaction problems. Tree search algorithms recursively partition the search space to find an optimal solution. In order to keep the tree size small, it is crucial to carefully decide, when expanding a tree node, which question (typically variable) to branch on at that node in order to partition the remaining space. Numerous partitioning techniques (e.g., variable selection) have been proposed, but there is no theory describing which technique is optimal. We show how to use machine learning to determine an optimal weighting of any set of partitioning procedures for the instance distribution at hand using samples from the distribution. We provide the first sample complexity guarantees for tree search algorithm configuration. These guarantees bound the number of samples sufficient to ensure that the empirical performance of an algorithm over the samples nearly matches its expected performance on the unknown instance distribution. This thorough theoretical investigation naturally gives rise to our learning algorithm. Via experiments, we show that learning an optimal weighting of partitioning procedures can dramatically reduce tree size, and we prove that this reduction can even be exponential. Through theory and experiments, we show that learning to branch is both practical and hugely beneficial.
Tasks
Published 2018-03-27
URL http://arxiv.org/abs/1803.10150v2
PDF http://arxiv.org/pdf/1803.10150v2.pdf
PWC https://paperswithcode.com/paper/learning-to-branch
Repo
Framework

Neural Predictive Belief Representations

Title Neural Predictive Belief Representations
Authors Zhaohan Daniel Guo, Mohammad Gheshlaghi Azar, Bilal Piot, Bernardo A. Pires, Rémi Munos
Abstract Unsupervised representation learning has succeeded with excellent results in many applications. It is an especially powerful tool to learn a good representation of environments with partial or noisy observations. In partially observable domains it is important for the representation to encode a belief state, a sufficient statistic of the observations seen so far. In this paper, we investigate whether it is possible to learn such a belief representation using modern neural architectures. Specifically, we focus on one-step frame prediction and two variants of contrastive predictive coding (CPC) as the objective functions to learn the representations. To evaluate these learned representations, we test how well they can predict various pieces of information about the underlying state of the environment, e.g., position of the agent in a 3D maze. We show that all three methods are able to learn belief representations of the environment, they encode not only the state information, but also its uncertainty, a crucial aspect of belief states. We also find that for CPC multi-step predictions and action-conditioning are critical for accurate belief representations in visually complex environments. The ability of neural representations to capture the belief information has the potential to spur new advances for learning and planning in partially observable domains, where leveraging uncertainty is essential for optimal decision making.
Tasks Decision Making, Representation Learning, Unsupervised Representation Learning
Published 2018-11-15
URL https://arxiv.org/abs/1811.06407v2
PDF https://arxiv.org/pdf/1811.06407v2.pdf
PWC https://paperswithcode.com/paper/neural-predictive-belief-representations
Repo
Framework

Cataract influence on iris recognition performance

Title Cataract influence on iris recognition performance
Authors Mateusz Trokielewicz, Adam Czajka, Piotr Maciejewicz
Abstract This paper presents the experimental study revealing weaker performance of the automatic iris recognition methods for cataract-affected eyes when compared to healthy eyes. There is little research on the topic, mostly incorporating scarce databases that are often deficient in images representing more than one illness. We built our own database, acquiring 1288 eye images of 37 patients of the Medical University of Warsaw. Those images represent several common ocular diseases, such as cataract, along with less ordinary conditions, such as iris pattern alterations derived from illness or eye trauma. Images were captured in near-infrared light (used in biometrics) and for selected cases also in visible light (used in ophthalmological diagnosis). Since cataract is a disorder that is most populated by samples in the database, in this paper we focus solely on this illness. To assess the extent of the performance deterioration we use three iris recognition methodologies (commercial and academic solutions) to calculate genuine match scores for healthy eyes and those influenced by cataract. Results show a significant degradation in iris recognition reliability manifesting by worsening the genuine scores in all three matchers used in this study (12% of genuine score increase for an academic matcher, up to 175% of genuine score increase obtained for an example commercial matcher). This increase in genuine scores affected the final false non-match rate in two matchers. To our best knowledge this is the only study of such kind that employs more than one iris matcher, and analyzes the iris image segmentation as a potential source of decreased reliability.
Tasks Iris Recognition, Semantic Segmentation
Published 2018-09-01
URL http://arxiv.org/abs/1809.00211v1
PDF http://arxiv.org/pdf/1809.00211v1.pdf
PWC https://paperswithcode.com/paper/cataract-influence-on-iris-recognition
Repo
Framework

A Survey of Machine and Deep Learning Methods for Internet of Things (IoT) Security

Title A Survey of Machine and Deep Learning Methods for Internet of Things (IoT) Security
Authors Mohammed Ali Al-Garadi, Amr Mohamed, Abdulla Al-Ali, Xiaojiang Du, Mohsen Guizani
Abstract The Internet of Things (IoT) integrates billions of smart devices that can communicate with one another with minimal human intervention. It is one of the fastest developing fields in the history of computing, with an estimated 50 billion devices by the end of 2020. On the one hand, IoT play a crucial role in enhancing several real-life smart applications that can improve life quality. On the other hand, the crosscutting nature of IoT systems and the multidisciplinary components involved in the deployment of such systems introduced new security challenges. Implementing security measures, such as encryption, authentication, access control, network security and application security, for IoT devices and their inherent vulnerabilities is ineffective. Therefore, existing security methods should be enhanced to secure the IoT system effectively. Machine learning and deep learning (ML/DL) have advanced considerably over the last few years, and machine intelligence has transitioned from laboratory curiosity to practical machinery in several important applications. Consequently, ML/DL methods are important in transforming the security of IoT systems from merely facilitating secure communication between devices to security-based intelligence systems. The goal of this work is to provide a comprehensive survey of ML /DL methods that can be used to develop enhanced security methods for IoT systems. IoT security threats that are related to inherent or newly introduced threats are presented, and various potential IoT system attack surfaces and the possible threats related to each surface are discussed. We then thoroughly review ML/DL methods for IoT security and present the opportunities, advantages and shortcomings of each method. We discuss the opportunities and challenges involved in applying ML/DL to IoT security. These opportunities and challenges can serve as potential future research directions.
Tasks
Published 2018-07-29
URL http://arxiv.org/abs/1807.11023v1
PDF http://arxiv.org/pdf/1807.11023v1.pdf
PWC https://paperswithcode.com/paper/a-survey-of-machine-and-deep-learning-methods
Repo
Framework

Semi Parametric Estimations of rotating and scaling parameters for aeronautic loads

Title Semi Parametric Estimations of rotating and scaling parameters for aeronautic loads
Authors Edouard Fournier, Stéphane Grihon, Thierry Klein
Abstract In this paper, we perform registration of noisy curves. We provide an appropriate model in estimating the rotation and scaling parameters to adjust a set of curves through a M-estimation procedure. We prove the consistency and the asymptotic normality of our estimators. Numerical simulation and a real life aeronautic example are given to illustrate our methodology.
Tasks
Published 2018-09-24
URL http://arxiv.org/abs/1809.08871v2
PDF http://arxiv.org/pdf/1809.08871v2.pdf
PWC https://paperswithcode.com/paper/semi-parametric-estimations-of-rotating-and
Repo
Framework

View Inter-Prediction GAN: Unsupervised Representation Learning for 3D Shapes by Learning Global Shape Memories to Support Local View Predictions

Title View Inter-Prediction GAN: Unsupervised Representation Learning for 3D Shapes by Learning Global Shape Memories to Support Local View Predictions
Authors Zhizhong Han, Mingyang Shang, Yu-Shen Liu, Matthias Zwicker
Abstract In this paper we present a novel unsupervised representation learning approach for 3D shapes, which is an important research challenge as it avoids the manual effort required for collecting supervised data. Our method trains an RNN-based neural network architecture to solve multiple view inter-prediction tasks for each shape. Given several nearby views of a shape, we define view inter-prediction as the task of predicting the center view between the input views, and reconstructing the input views in a low-level feature space. The key idea of our approach is to implement the shape representation as a shape-specific global memory that is shared between all local view inter-predictions for each shape. Intuitively, this memory enables the system to aggregate information that is useful to better solve the view inter-prediction tasks for each shape, and to leverage the memory as a view-independent shape representation. Our approach obtains the best results using a combination of L_2 and adversarial losses for the view inter-prediction task. We show that VIP-GAN outperforms state-of-the-art methods in unsupervised 3D feature learning on three large scale 3D shape benchmarks.
Tasks Representation Learning, Unsupervised Representation Learning
Published 2018-11-07
URL http://arxiv.org/abs/1811.02744v1
PDF http://arxiv.org/pdf/1811.02744v1.pdf
PWC https://paperswithcode.com/paper/view-inter-prediction-gan-unsupervised
Repo
Framework

Assertion-based QA with Question-Aware Open Information Extraction

Title Assertion-based QA with Question-Aware Open Information Extraction
Authors Zhao Yan, Duyu Tang, Nan Duan, Shujie Liu, Wendi Wang, Daxin Jiang, Ming Zhou, Zhoujun Li
Abstract We present assertion based question answering (ABQA), an open domain question answering task that takes a question and a passage as inputs, and outputs a semi-structured assertion consisting of a subject, a predicate and a list of arguments. An assertion conveys more evidences than a short answer span in reading comprehension, and it is more concise than a tedious passage in passage-based QA. These advantages make ABQA more suitable for human-computer interaction scenarios such as voice-controlled speakers. Further progress towards improving ABQA requires richer supervised dataset and powerful models of text understanding. To remedy this, we introduce a new dataset called WebAssertions, which includes hand-annotated QA labels for 358,427 assertions in 55,960 web passages. To address ABQA, we develop both generative and extractive approaches. The backbone of our generative approach is sequence to sequence learning. In order to capture the structure of the output assertion, we introduce a hierarchical decoder that first generates the structure of the assertion and then generates the words of each field. The extractive approach is based on learning to rank. Features at different levels of granularity are designed to measure the semantic relevance between a question and an assertion. Experimental results show that our approaches have the ability to infer question-aware assertions from a passage. We further evaluate our approaches by incorporating the ABQA results as additional features in passage-based QA. Results on two datasets show that ABQA features significantly improve the accuracy on passage-based~QA.
Tasks Learning-To-Rank, Open-Domain Question Answering, Open Information Extraction, Question Answering, Reading Comprehension
Published 2018-01-23
URL http://arxiv.org/abs/1801.07414v1
PDF http://arxiv.org/pdf/1801.07414v1.pdf
PWC https://paperswithcode.com/paper/assertion-based-qa-with-question-aware-open
Repo
Framework

Online Prediction of Switching Graph Labelings with Cluster Specialists

Title Online Prediction of Switching Graph Labelings with Cluster Specialists
Authors Mark Herbster, James Robinson
Abstract We address the problem of predicting the labeling of a graph in an online setting when the labeling is changing over time. We present an algorithm based on a specialist approach; we develop the machinery of cluster specialists which probabilistically exploits the cluster structure in the graph. Our algorithm has two variants, one of which surprisingly only requires $\mathcal{O}(\log n)$ time on any trial $t$ on an $n$-vertex graph, an exponential speed up over existing methods. We prove switching mistake-bound guarantees for both variants of our algorithm. Furthermore these mistake bounds smoothly vary with the magnitude of the change between successive labelings. We perform experiments on Chicago Divvy Bicycle Sharing data and show that our algorithms significantly outperform an existing algorithm (a kernelized Perceptron) as well as several natural benchmarks.
Tasks
Published 2018-06-17
URL https://arxiv.org/abs/1806.06439v3
PDF https://arxiv.org/pdf/1806.06439v3.pdf
PWC https://paperswithcode.com/paper/predicting-switching-graph-labelings-with
Repo
Framework

A Connectome Based Hexagonal Lattice Convolutional Network Model of the Drosophila Visual System

Title A Connectome Based Hexagonal Lattice Convolutional Network Model of the Drosophila Visual System
Authors Fabian David Tschopp, Michael B. Reiser, Srinivas C. Turaga
Abstract What can we learn from a connectome? We constructed a simplified model of the first two stages of the fly visual system, the lamina and medulla. The resulting hexagonal lattice convolutional network was trained using backpropagation through time to perform object tracking in natural scene videos. Networks initialized with weights from connectome reconstructions automatically discovered well-known orientation and direction selectivity properties in T4 neurons and their inputs, while networks initialized at random did not. Our work is the first demonstration, that knowledge of the connectome can enable in silico predictions of the functional properties of individual neurons in a circuit, leading to an understanding of circuit function from structure alone.
Tasks Object Tracking
Published 2018-06-12
URL http://arxiv.org/abs/1806.04793v2
PDF http://arxiv.org/pdf/1806.04793v2.pdf
PWC https://paperswithcode.com/paper/a-connectome-based-hexagonal-lattice
Repo
Framework

Finite Sample Analysis of LSTD with Random Projections and Eligibility Traces

Title Finite Sample Analysis of LSTD with Random Projections and Eligibility Traces
Authors Haifang Li, Yingce Xia, Wensheng Zhang
Abstract Policy evaluation with linear function approximation is an important problem in reinforcement learning. When facing high-dimensional feature spaces, such a problem becomes extremely hard considering the computation efficiency and quality of approximations. We propose a new algorithm, LSTD($\lambda$)-RP, which leverages random projection techniques and takes eligibility traces into consideration to tackle the above two challenges. We carry out theoretical analysis of LSTD($\lambda$)-RP, and provide meaningful upper bounds of the estimation error, approximation error and total generalization error. These results demonstrate that LSTD($\lambda$)-RP can benefit from random projection and eligibility traces strategies, and LSTD($\lambda$)-RP can achieve better performances than prior LSTD-RP and LSTD($\lambda$) algorithms.
Tasks
Published 2018-05-25
URL http://arxiv.org/abs/1805.10005v1
PDF http://arxiv.org/pdf/1805.10005v1.pdf
PWC https://paperswithcode.com/paper/finite-sample-analysis-of-lstd-with-random
Repo
Framework
comments powered by Disqus