OpenRaiser/Intern-Atlas huggingface dataset:
The Limitations of Deep Learning in Adversarial Settings
Venue: arXiv cs.CR 2015
Year: 2015

Deep learning takes advantage of large datasets and computationally efficient training algorithms to outperform other approaches at various machine learning tasks. However, imperfections in the training phase of deep neural networks make them vulnerable to adversarial samples: inputs crafted by adversaries with the intent of causing deep neural networks to misclassify. In this work, we formalize the space of adversaries against deep neural networks (DNNs) and introduce a novel class of algorithms to craft adversarial samples based on a precise understanding of the mapping between inputs and outputs of DNNs. In an application to computer vision, we show that our algorithms can reliably produce samples correctly classified by human subjects but misclassified in specific targets by a DNN with a 97% adversarial success rate while only modifying on average 4.02% of the input features per sample. We then evaluate the vulnerability of different sample classes to adversarial perturbations by defining a hardness measure. Finally, we describe preliminary work outlining defenses against adversarial samples by defining a predictive measure of distance between a benign input and a target classification.
An Efficient Coded Multicasting Scheme Preserving the Multiplicative Caching Gain
Venue: arXiv cs.IT 2015
Year: 2015

Coded multicasting has been shown to be a promis- ing approach to significantly improve the caching performance of content delivery networks with multiple caches downstream of a common multicast link. However, achievable schemes proposed to date have been shown to achieve the proved order-optimal performance only in the asymptotic regime in which the number of packets per requested item goes to infinity. In this paper, we first extend the asymptotic analysis of the achievable scheme in [1], [2] to the case of heterogeneous cache sizes and demand distributions, providing the best known upper bound on the fundamental limiting performance when the number of packets goes to infinity. We then show that the scheme achieving this upper bound quickly loses its multiplicative caching gain for finite content packetization. To overcome this limitation, we design a novel polynomial-time algorithm based on random greedy graph- coloring that, while keeping the same finite content packetization, recovers a significant part of the multiplicative caching gain. Our results show that the order-optimal coded multicasting schemes proposed to date, while useful in quantifying the fundamental limiting performance, must be properly designed for practical regimes of finite packetization.
A Comparative Study of Statistical Learning and Adaptive Learning
Venue: arXiv cs.CY 2015
Year: 2015

Numerous strategies have been adopted in order to make the process of learning simple, efficient and within less amount of time.. Classroom learning is slowly replaced by E-learning and M- learning. These techniques involve the usage of computers, smart phones and tablets for the process of learning. Learning from the internet has become popular among the e-learners where learner tends to rely greatly upon information provided by the World Wide Web. However, the e-learners have to go through a huge volume of data produced by the first tier search engine, some of which are not suited to the interest of the user. Various strategies, namely Statistical Learning and Adaptive Learning, have been adopted to cater to the need of the user and produce data best suited to the interest of the user. The authors have tried to present a comparative study of Statistical Learning and Adaptive Learning based on certain parameters, which arise from the characteristics of the learning process. As a consequence of the comparative study, it has been concluded that Adaptive learning is more efficient than Statistical learning.
Pairwise Comparisons Rating Scale Paradox
Venue: arXiv cs.OH 2015
Year: 2015

This study demonstrates that incorrect data are entered into a pairwise comparisons matrix for processing into weights for the data collected by a rating scale. Unprocessed rating scale data lead to a paradox. A solution to it, based on normalization, is proposed. This is an essential correction for virtually all pairwise comparisons methods using rating scales. The illustration of the relative error currently, taking place, is discussed.
Lower bounds for constant query affine-invariant LCCs and LTCs
Venue: arXiv cs.CC 2015
Year: 2015

Affine-invariant codes are codes whose coordinates form a vector space over a finite field and which are invariant under affine transformations of the coordinate space. They form a natural, well-studied class of codes; they include popular codes such as Reed-Muller and Reed-Solomon. A particularly appealing feature of affine-invariant codes is that they seem well-suited to admit local correctors and testers. In this work, we give lower bounds on the length of locally correctable and locally testable affine-invariant codes with constant query complexity. We show that if a code $\mathcal{C} \subset Σ^{\mathbb{K}^n}$ is an $r$-query locally correctable code (LCC), where $\mathbb{K}$ is a finite field and $Σ$ is a finite alphabet, then the number of codewords in $\mathcal{C}$ is at most $\exp(O_{\mathbb{K}, r, |Σ|}(n^{r-1}))$. Also, we show that if $\mathcal{C} \subset Σ^{\mathbb{K}^n}$ is an $r$-query locally testable code (LTC), then the number of codewords in $\mathcal{C}$ is at most $\exp(O_{\mathbb{K}, r, |Σ|}(n^{r-2}))$. The dependence on $n$ in these bounds is tight for constant-query LCCs/LTCs, since Guo, Kopparty and Sudan (ITCS `13) construct affine-invariant codes via lifting that have the same asymptotic tradeoffs. Note that our result holds for non-linear codes, whereas previously, Ben-Sasson and Sudan (RANDOM `11) assumed linearity to derive similar results. Our analysis uses higher-order Fourier analysis. In particular, we show that the codewords corresponding to an affine-invariant LCC/LTC must be far from each other with respect to Gowers norm of an appropriate order. This then allows us to bound the number of codewords, using known decomposition theorems which approximate any bounded function in terms of a finite number of low-degree non-classical polynomials, upto a small error in the Gowers norm.
Towards A Marketplace for Mobile Content: Dynamic Pricing and Proactive Caching
Venue: arXiv cs.GT 2015
Year: 2015

In this work, we investigate the profit maximization problem for a wireless network carrier and the payment minimization for end-users. Motivated by recent findings on proactive resource allocation, we focus on the scenario whereby end-users who are equipped with device-to-device (D2D)communication can harness predictable demand in proactive data contents caching and the possibility of trading their proactive downloads to minimize their expected payments. The carrier, on the other hand, utilizes a dynamic pricing scheme to differentiate between off-peak and peak time prices and applies commissions on each trading process to further maximize its profit. A novel marketplace that is based on risk sharing between end-users is proposed where the tension between carrier and end-users is formulated as a Stackelberg game. The existence and uniqueness of the non-cooperative sub-game Nash equilibrium is shown. Furthermore, we explore the equilibrium points for the case when the D2D is available and when it is not available, and study the impact of the uncertainty of users future demands on the system's performance. In particular, we compare the new equilibrium with the baseline scenario of flat pricing. Despite end-users connectivity with each other, the uncertainty of their future demands, and the freshness of the pre-cached contents, we characterize a new equilibrium region which yields to a win-win situation with respect to the baseline equilibrium. We show that end-users activity patterns can be harnessed to maximize the carrier's profit while minimizing the end-users expected payments.
A communication game related to the sensitivity conjecture
Venue: arXiv cs.CC 2015
Year: 2015

One of the major outstanding foundational problems about boolean functions is the sensitivity conjecture, which (in one of its many forms) asserts that the degree of a boolean function (i.e. the minimum degree of a real polynomial that interpolates the function) is bounded above by some fixed power of its sensitivity (which is the maximum vertex degree of the graph defined on the inputs where two inputs are adjacent if they differ in exactly one coordinate and their function values are different). We propose an attack on the sensitivity conjecture in terms of a novel two-player communication game. A lower bound of the form $n^{Ω(1)}$ on the cost of this game would imply the sensitivity conjecture. To investigate the problem of bounding the cost of the game, three natural (stronger) variants of the question are considered. For two of these variants, protocols are presented that show that the hoped for lower bound does not hold. These protocols satisfy a certain monotonicity property, and (in contrast to the situation for the two variants) we show that the cost of any monotone protocol satisfies a strong lower bound. There is an easy upper bound of $\sqrt{n}$ on the cost of the game. We also improve slightly on this upper bound.
Bayesian Identification of Fixations, Saccades, and Smooth Pursuits
Venue: arXiv cs.CV 2015
Year: 2015

Smooth pursuit eye movements provide meaningful insights and information on subject's behavior and health and may, in particular situations, disturb the performance of typical fixation/saccade classification algorithms. Thus, an automatic and efficient algorithm to identify these eye movements is paramount for eye-tracking research involving dynamic stimuli. In this paper, we propose the Bayesian Decision Theory Identification (I-BDT) algorithm, a novel algorithm for ternary classification of eye movements that is able to reliably separate fixations, saccades, and smooth pursuits in an online fashion, even for low-resolution eye trackers. The proposed algorithm is evaluated on four datasets with distinct mixtures of eye movements, including fixations, saccades, as well as straight and circular smooth pursuits; data was collected with a sample rate of 30 Hz from six subjects, totaling 24 evaluation datasets. The algorithm exhibits high and consistent performance across all datasets and movements relative to a manual annotation by a domain expert (recall: μ= 91.42%, σ= 9.52%; precision: μ= 95.60%, σ= 5.29%; specificity μ= 95.41%, σ= 7.02%) and displays a significant improvement when compared to I-VDT, an state-of-the-art algorithm (recall: μ= 87.67%, σ= 14.73%; precision: μ= 89.57%, σ= 8.05%; specificity μ= 92.10%, σ= 11.21%). For algorithm implementation and annotated datasets, please contact the first author.
Weakly Supervised Object Boundaries
Venue: arXiv cs.CV 2015
Year: 2015

State-of-the-art learning based boundary detection methods require extensive training data. Since labelling object boundaries is one of the most expensive types of annotations, there is a need to relax the requirement to carefully annotate images to make both the training more affordable and to extend the amount of training data. In this paper we propose a technique to generate weakly supervised annotations and show that bounding box annotations alone suffice to reach high-quality object boundaries without using any object-specific boundary annotations. With the proposed weak supervision techniques we achieve the top performance on the object boundary detection task, outperforming by a large margin the current fully supervised state-of-the-art methods.
rnn : Recurrent Library for Torch
Venue: arXiv cs.NE 2015
Year: 2015

The rnn package provides components for implementing a wide range of Recurrent Neural Networks. It is built withing the framework of the Torch distribution for use with the nn package. The components have evolved from 3 iterations, each adding to the flexibility and capability of the package. All component modules inherit either the AbstractRecurrent or AbstractSequencer classes. Strong unit testing, continued backwards compatibility and access to supporting material are the principles followed during its development. The package is compared against existing implementations of two published papers.
Asynchronous Performance of Circularly Pulse-Shaped Waveforms for 5G
Venue: arXiv cs.IT 2015
Year: 2015

The fifth generation of wireless networks (5G) necessitates the use of waveforms with loose constraints on synchronization in multiuser scenarios. Also, carrier aggregation, as a way to better utilize the spectrum in 5G, needs a waveform with low out-of-band (OOB) emission. Generalized frequency division multiplexing (GFDM) and circular filter bank multicarrier (C-FBMC) are two candidate waveforms that fulfill these requirements. Both GFDM and C-FBMC operate based on circular convolution, and use cyclic prefix to combat channel response. In this paper, we develop an analytical technique for examining the OOB emission and multiuser interference (MUI) in circularly shaped waveforms, like GFDM and C-FBMC. To stay focused, the study in this paper is limited to C-FBMC modulation. However, the approach we take is trivially extendable to other waveforms as well. We derive equations that quantify OOB emission and MUI. Our analysis allows us to identify the source of OOB emission and MUI. This leads us to quantify the methods proposed by other researchers to decrease OOB emission and MUI. Moreover, we quantify the impact of signal windowing at the transmitter and receiver in reducing OOB emission and MUI, respectively.
Principal Basis Analysis in Sparse Representation
Venue: arXiv cs.CV 2015
Year: 2015

This article introduces a new signal analysis method, which can be interpreted as a principal component analysis in sparse decomposition of the signal. The method, called principal basis analysis, is based on a novel criterion: reproducibility of component which is an intrinsic characteristic of regularity in natural signals. We show how to measure reproducibility. Then we present the principal basis analysis method, which chooses, in a sparse representation of the signal, the components optimizing the reproducibility degree to build the so-called principal basis. With this principal basis, we show that the underlying signal pattern could be effectively extracted from corrupted data. As illustration, we apply the principal basis analysis to image denoising corrupted by Gaussian and non-Gaussian noises, showing better performances than some reference methods at suppressing strong noise and at preserving signal details.
Embedding of Hypercube into Cylinder
Venue: arXiv cs.GR 2015
Year: 2015

Task mapping in modern high performance parallel computers can be modeled as a graph embedding problem, which simulates the mapping as embedding one graph into another and try to find the minimum wirelength for the mapping. Though embedding problems have been considered for several regular graphs, such as hypercubes into grids, binary trees into grids, et al, it is still an open problem for hypercubes into cylinders. In this paper, we consider the problem of embedding hypercubes into cylinders to minimize the wirelength. We obtain the exact wirelength formula of embedding hypercube $Q^r$ into cylinder $C_{2^3}\times P_{2^{r-3}}$ with $r\ge3$.
PASCAL Boundaries: A Class-Agnostic Semantic Boundary Dataset
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we address the boundary detection task motivated by the ambiguities in current definition of edge detection. To this end, we generate a large database consisting of more than 10k images (which is 20x bigger than existing edge detection databases) along with ground truth boundaries between 459 semantic classes including both foreground objects and different types of background, and call it the PASCAL Boundaries dataset, which will be released to the community. In addition, we propose a novel deep network-based multi-scale semantic boundary detector and name it Multi-scale Deep Semantic Boundary Detector (M-DSBD). We provide baselines using models that were trained on edge detection and show that they transfer reasonably to the task of boundary detection. Finally, we point to various important research problems that this dataset can be used for.
Calculate distance to object in the area where car, using video analysis
Venue: arXiv cs.CV 2015
Year: 2015

The method of using video cameras installed on the car, to calculate the distance to the object in its area of movement.
Authentication With a Guessing Adversary
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we consider the authentication problem where a candidate measurement presented by an unidentified user is compared to a previously stored measurement of the legitimate user, the enrollment, with respect to a certain distortion criteria for authentication. An adversary wishes to impersonate the legitimate user by guessing the enrollment until the system authenticates him. For this setting, we study the minimum number of required guesses (on average) by the adversary for a successful impersonation attack and find the complete characterization of the asymptotic exponent of this metric, referred to as the deception exponent. Our result is a direct application of the results of the Guessing problem by Arikan and Merhav [19]. Paralleling the work in [19] we also extend this result to the case where the adversary may have access to additional side information correlated to the enrollment data. The paper is a revised version of a submission to IEEE WIFS 2015, with the referencing to the paper [19] clarified compared with the conference version.
Industrial Experiences with a Formal DSL Semantics to Check Correctness of DSL Transformations
Venue: arXiv cs.SE 2015
Year: 2015

A domain specific language (DSL) abstracts from implementation details and is aligned with the way domain experts reason about a software component. The development of DSLs is usually centered around a grammar and transformations that generate implementation code or analysis models. The semantics of the language is often defined implicitly and in terms of a transformation to implementation code. In the presence of multiple transformations from the DSL, the consistency of the generated artifacts with respect to the semantics of the DSL is a relevant issue. We show that a formal semantics is essential for checking the consistency between the generated artifacts. We exploit the formal semantics in an industrial project and use formal techniques based on equivalence checking and model-based testing for consistency checking. We report about our experience with this approach in an industrial development project.
The Journal Coverage of Web of Science and Scopus: a Comparative Analysis
Venue: arXiv cs.DL 2015
Year: 2015

Bibliometric methods are used in multiple fields for a variety of purposes, namely for research evaluation. Most bibliometric analyses have in common their data sources: Thomson Reuters' Web of Science (WoS) and Elsevier's Scopus. This research compares the journal coverage of both databases in terms of fields, countries and languages, using Ulrich's extensive periodical directory as a base for comparison. Results indicate that the use of either WoS or Scopus for research evaluation may introduces biases that favor Natural Sciences and Engineering as well as Biomedical Research to the detriment of Social Sciences and Arts and Humanities. Similarly, English-language journals are overrepresented to the detriment of other languages. While both databases share these biases, their coverage differs substantially. As a consequence, the results of bibliometric analyses may vary depending on the database used.
Strategic Dialogue Management via Deep Reinforcement Learning
Venue: arXiv cs.AI 2015
Year: 2015

Artificially intelligent agents equipped with strategic skills that can negotiate during their interactions with other natural or artificial agents are still underdeveloped. This paper describes a successful application of Deep Reinforcement Learning (DRL) for training intelligent agents with strategic conversational skills, in a situated dialogue setting. Previous studies have modelled the behaviour of strategic agents using supervised learning and traditional reinforcement learning techniques, the latter using tabular representations or learning with linear function approximation. In this study, we apply DRL with a high-dimensional state space to the strategic board game of Settlers of Catan---where players can offer resources in exchange for others and they can also reply to offers made by other players. Our experimental results report that the DRL-based learnt policies significantly outperformed several baselines including random, rule-based, and supervised-based behaviours. The DRL-based policy has a 53% win rate versus 3 automated players (`bots'), whereas a supervised player trained on a dialogue corpus in this setting achieved only 27%, versus the same 3 bots. This result supports the claim that DRL is a promising framework for training dialogue systems, and strategic agents with negotiation abilities.
Reinstating Combinatorial Protections for Manipulation and Bribery in Single-Peaked and Nearly Single-Peaked Electorates
Venue: arXiv cs.GT 2015
Year: 2015

Understanding when and how computational complexity can be used to protect elections against different manipulative actions has been a highly active research area over the past two decades. A recent body of work, however, has shown that many of the NP-hardness shields, previously obtained, vanish when the electorate has single-peaked or nearly single-peaked preferences. In light of these results, we investigate whether it is possible to reimpose NP-hardness shields for such electorates by allowing the voters to specify partial preferences instead of insisting they cast complete ballots. In particular, we show that in single-peaked and nearly single-peaked electorates, if voters are allowed to submit top-truncated ballots, then the complexity of manipulation and bribery for many voting rules increases from being in P to being NP-complete.
Tracking Motion and Proxemics using Thermal-sensor Array
Venue: arXiv cs.CV 2015
Year: 2015

Indoor tracking has all-pervasive applications beyond mere surveillance, for example in education, health monitoring, marketing, energy management and so on. Image and video based tracking systems are intrusive. Thermal array sensors on the other hand can provide coarse-grained tracking while preserving privacy of the subjects. The goal of the project is to facilitate motion detection and group proxemics modeling using an 8 x 8 infrared sensor array. Each of the 8 x 8 pixels is a temperature reading in Fahrenheit. We refer to each 8 x 8 matrix as a scene. We collected approximately 902 scenes with different configurations of human groups and different walking directions. We infer direction of motion of a subject across a set of scenes as left-to-right, right-to-left, up-to-down and down-to-up using cross-correlation analysis. We used features from connected component analysis of each background subtracted scene and performed Support Vector Machine classification to estimate number of instances of human subjects in the scene.