OpenRaiser/Intern-Atlas huggingface dataset:
Information Privacy Opinions on Twitter: A Cross-Language Study
Venue: arXiv cs.IR 2019
Year: 2019

The Cambridge Analytica scandal triggered a conversation on Twitter about data practices and their implications. Our research proposes to leverage this conversation to extend the understanding of how information privacy is framed by users worldwide. We collected tweets about the scandal written in Spanish and English between April and July 2018. We created a word embedding to create a reduced multi-dimensional representation of the tweets in each language. For each embedding, we conducted open coding to characterize the semantic contexts of key concepts: "information", "privacy", "company" and "users" (and their Spanish translations). Through a comparative analysis, we found a broader emphasis on privacy-related words associated with companies in English. We also identified more terms related to data collection in English and fewer associated with security mechanisms, control, and risks. Our findings hint at the potential of cross-language comparisons of text to extend the understanding of worldwide differences in information privacy perspectives.
Pinning Down the Strong Wilber 1 Bound for Binary Search Trees
Venue: arXiv cs.DS 2019
Year: 2019

The dynamic optimality conjecture, postulating the existence of an $O(1)$-competitive online algorithm for binary search trees (BSTs), is among the most fundamental open problems in dynamic data structures. Despite extensive work and some notable progress, including, for example, the Tango Trees (Demaine et al., FOCS 2004), that give the best currently known $O(\log \log n)$-competitive algorithm, the conjecture remains widely open. One of the main hurdles towards settling the conjecture is that we currently do not have approximation algorithms achieving better than an $O(\log \log n)$-approximation, even in the offline setting. All known non-trivial algorithms for BST's so far rely on comparing the algorithm's cost with the so-called Wilber's first bound (WB-1). Therefore, establishing the worst-case relationship between this bound and the optimal solution cost appears crucial for further progress, and it is an interesting open question in its own right. Our contribution is two-fold. First, we show that the gap between the WB-1 bound and the optimal solution value can be as large as $Ω(\log \log n/ \log \log \log n)$; in fact, the gap holds even for several stronger variants of the bound. Second, we provide a simple algorithm, that, given an integer $D>0$, obtains an $O(D)$-approximation in time $\exp\left(O\left (n^{1/2^{Ω(D)}}\log n\right )\right )$. In particular, this gives a constant-factor approximation sub-exponential time algorithm. Moreover, we obtain a simpler and cleaner efficient $O(\log \log n)$-approximation algorithm that can be used in an online setting. Finally, we suggest a new bound, that we call {\em Guillotine Bound}, that is stronger than WB, while maintaining its algorithm-friendly nature, that we hope will lead to better algorithms. All our results use the geometric interpretation of the problem, leading to cleaner and simpler analysis.
Detection of Face Recognition Adversarial Attacks
Venue: arXiv cs.CV 2019
Year: 2019

Deep Learning methods have become state-of-the-art for solving tasks such as Face Recognition (FR). Unfortunately, despite their success, it has been pointed out that these learning models are exposed to adversarial inputs - images to which an imperceptible amount of noise for humans is added to maliciously fool a neural network - thus limiting their adoption in real-world applications. While it is true that an enormous effort has been spent in order to train robust models against this type of threat, adversarial detection techniques have recently started to draw attention within the scientific community. A detection approach has the advantage that it does not require to re-train any model, thus it can be added on top of any system. In this context, we present our work on adversarial samples detection in forensics mainly focused on detecting attacks against FR systems in which the learning model is typically used only as a features extractor. Thus, in these cases, train a more robust classifier might not be enough to defence a FR system. In this frame, the contribution of our work is four-fold: i) we tested our recently proposed adversarial detection approach against classifier attacks, i.e. adversarial samples crafted to fool a FR neural network acting as a classifier; ii) using a k-Nearest Neighbor (kNN) algorithm as a guidance, we generated deep features attacks against a FR system based on a DL model acting as features extractor, followed by a kNN which gives back the query identity based on features similarity; iii) we used the deep features attacks to fool a FR system on the 1:1 Face Verification task and we showed their superior effectiveness with respect to classifier attacks in fooling such type of system; iv) we used the detectors trained on classifier attacks to detect deep features attacks, thus showing that such approach is generalizable to different types of offensives.
User Experience with Language-Independent Formal Verification
Venue: arXiv cs.PL 2019
Year: 2019

The goal of this paper is to help mainstream programmers routinely use formal verification on their smart contracts by 1) proposing a new YAML-format for writing general-purpose formal specifications, 2) demonstrating how a formal specification can be incrementally built up without needing advanced training, and 3) showing how formal specifications can be tested by using program mutation.
On the Complexity of the Stability Problem of Binary Freezing Totalistic Cellular Automata
Venue: arXiv cs.DS 2019
Year: 2019

In this paper we study the family of two-state Totalistic Freezing Cellular Automata (TFCA) defined over the triangular and square grids with von Neumann neighborhoods. We say that a Cellular Automaton is Freezing and Totalistic if the active cells remain unchanged, and the new value of an inactive cell depends only on the sum of its active neighbors. We classify all the Cellular Automata in the class of TFCA, grouping them in five different classes: the Trivial rules, Turing Universal rules,Algebraic rules, Topological rules and Fractal Growing rules. At the same time, we study in this family the Stability problem, consisting in deciding whether an inactive cell becomes active, given an initial configuration.We exploit the properties of the automata in each group to show that: - For Algebraic and Topological Rules the Stability problem is in $\text{NC}$. - For Turing Universal rules the Stability problem is $\text{P}$-Complete.
DeepEthnic: Multi-Label Ethnic Classification from Face Images
Venue: arXiv cs.CV 2019
Year: 2019

Ethnic group classification is a well-researched problem, which has been pursued mainly during the past two decades via traditional approaches of image processing and machine learning. In this paper, we propose a method of classifying an image face into an ethnic group by applying transfer learning from a previously trained classification network for large-scale data recognition. Our proposed method yields state-of-the-art success rates of 99.02%, 99.76%, 99.2%, and 96.7%, respectively, for the four ethnic groups: African, Asian, Caucasian, and Indian.
Influenza Modeling Based on Massive Feature Engineering and International Flow Deconvolution
Venue: arXiv cs.LG 2019
Year: 2019

In this article, we focus on the analysis of the potential factors driving the spread of influenza, and possible policies to mitigate the adverse effects of the disease. To be precise, we first invoke discrete Fourier transform (DFT) to conclude a yearly periodic regional structure in the influenza activity, thus safely restricting ourselves to the analysis of the yearly influenza behavior. Then we collect a massive number of possible region-wise indicators contributing to the influenza mortality, such as consumption, immunization, sanitation, water quality, and other indicators from external data, with $1170$ dimensions in total. We extract significant features from the high dimensional indicators using a combination of data analysis techniques, including matrix completion, support vector machines (SVM), autoencoders, and principal component analysis (PCA). Furthermore, we model the international flow of migration and trade as a convolution on regional influenza activity, and solve the deconvolution problem as higher-order perturbations to the linear regression, thus separating regional and international factors related to the influenza mortality. Finally, both the original model and the perturbed model are tested on regional examples, as validations of our models. Pertaining to the policy, we make a proposal based on the connectivity data along with the previously extracted significant features to alleviate the impact of influenza, as well as efficiently propagate and carry out the policies. We conclude that environmental features and economic features are of significance to the influenza mortality. The model can be easily adapted to model other types of infectious diseases.
Perspective-consistent multifocus multiview 3D reconstruction of small objects
Venue: arXiv cs.CV 2019
Year: 2019

Image-based 3D reconstruction or 3D photogrammetry of small-scale objects including insects and biological specimens is challenging due to the use of high magnification lens with inherent limited depth of field, and the object's fine structures and complex surface properties. Due to these challenges, traditional 3D reconstruction techniques cannot be applied without suitable image pre-processings. One such preprocessing technique is multifocus stacking that combines a set of partially focused images captured from the same viewing angle to create a single in-focus image. Traditional multifocus image capture uses a camera on a macro rail. Furthermore, the scale and shift are not properly considered by multifocus stacking techniques. As a consequence, the resulting in-focus images contain artifacts that violate perspective image formation. A 3D reconstruction using such images will fail to produce an accurate 3D model of the object. This paper shows how this problem can be solved effectively by a new multifocus stacking procedure which includes a new Fixed-Lens Multifocus Capture and camera calibration for image scale and shift. Initial experimental results are presented to confirm our expectation and show that the camera poses of fixed-lens images are at least 3-times less noisy than those of conventional moving lens images.
Cubic spline approximation of the reliability polynomials of two dual hammock networks
Venue: arXiv cs.DM 2019
Year: 2019

The property of preserving the convexity and concavity of the Bernstein polynomial and of the Bézier curves is used to generate a method of approximating the reliability polynomial of a hammock network. The mutual behaviour of the reliability polynomials of two dual hammock networks is used to generate a system of constraints since the initial information is not enough for using a classical approximation scheme. A cubic spline function is constructed to generate approximations of the coefficients of the two reliability polynomials. As consequence, an approximation algorithm is described and tested through simulations on hammocks with known reliability, comparing the results with the results of approximations attempts from literature.
Hyperbolic Graph Attention Network
Venue: arXiv cs.LG 2019
Year: 2019

Graph neural network (GNN) has shown superior performance in dealing with graphs, which has attracted considerable research attention recently. However, most of the existing GNN models are primarily designed for graphs in Euclidean spaces. Recent research has proven that the graph data exhibits non-Euclidean latent anatomy. Unfortunately, there was rarely study of GNN in non-Euclidean settings so far. To bridge this gap, in this paper, we study the GNN with attention mechanism in hyperbolic spaces at the first attempt. The research of hyperbolic GNN has some unique challenges: since the hyperbolic spaces are not vector spaces, the vector operations (e.g., vector addition, subtraction, and scalar multiplication) cannot be carried. To tackle this problem, we employ the gyrovector spaces, which provide an elegant algebraic formalism for hyperbolic geometry, to transform the features in a graph; and then we propose the hyperbolic proximity based attention mechanism to aggregate the features. Moreover, as mathematical operations in hyperbolic spaces could be more complicated than those in Euclidean spaces, we further devise a novel acceleration strategy using logarithmic and exponential mappings to improve the efficiency of our proposed model. The comprehensive experimental results on four real-world datasets demonstrate the performance of our proposed hyperbolic graph attention network model, by comparisons with other state-of-the-art baseline methods.
Pairwise Neural Machine Translation Evaluation
Venue: arXiv cs.CL 2019
Year: 2019

We present a novel framework for machine translation evaluation using neural networks in a pairwise setting, where the goal is to select the better translation from a pair of hypotheses, given the reference translation. In this framework, lexical, syntactic and semantic information from the reference and the two hypotheses is compacted into relatively small distributed vector representations, and fed into a multi-layer neural network that models the interaction between each of the hypotheses and the reference, as well as between the two hypotheses. These compact representations are in turn based on word and sentence embeddings, which are learned using neural networks. The framework is flexible, allows for efficient learning and classification, and yields correlation with humans that rivals the state of the art.
Analysis of AeroMACS Data Link for Unmanned Aircraft Vehicles
Venue: arXiv cs.NI 2019
Year: 2019

Aeronautical Mobile Airport Communications System (AeroMACS) is based on the IEEE 802.16e mobile wireless standard commonly known as WiMAX. It is expected to be the main part of the next-generation aviation communication system to support fixed and mobile services for manned and unmanned applications. AeroMACS will be an essential technology helping pave the way toward full integration of Unmanned Aircraft Vehicle (UAV) into the national airspace. A number of practical tests and analyses have been done so far for AeroMACS. The main contribution of this paper is to consider the theoretical concepts behind its features and discuss their suitability for UAV applications. Mathematical analyses of the AeroMACS physical layer framework are provided to show the theoretical trade-offs. We mainly focus on the analysis of the AeroMACS OFDMA structure, which affects the speed limits, coverage cell, channel estimation requirements, and inter-carrier interference.
Modeling the Chlorophyll-a from Sea Surface Reflectance in West Africa by Deep Learning Methods: A Comparison of Multiple Algorithms
Venue: arXiv cs.NE 2019
Year: 2019

Deep learning provide successful applications in many fields. Recently, machines learning are involved for oceans remote sensing applications. In this study, we use and compare about eight (8) deep learning estimators for retrieval of a mainly pigment of phytoplankton. Depending on the water case and the multiple instruments simultaneouslyobserving the earth on a variety of platforms, several algorithm are used to estimate the chlolophyll-a from marine reflectance. By using a long-term multi-sensor time-series of satellite ocean-colour data, as MODIS, SeaWifs, VIIRS, MERIS, etc, we make a unique deep network model able to establish a relationship between sea surface reflectance and chlorophyll-a from any measurement satellite sensor over West Africa. These data fusion take into account the bias between case water and instruments. We construct several chlorophyll-a concentration prediction deep learning based models, compare them and therefore use the best for our study. Results obtained for accuracy training and test are quite good. The mean absolute error are very low and vary between 0,07 to 0,13 mg/m3.
Towards An Implementation of the Subset-sum Problem on the IBM Quantum Experience
Venue: arXiv cs.ET 2019
Year: 2019

In seeking out an algorithm to test out the capability of the IBM Quantum Experience quantum computer, we were given a review paper covering various algorithms for solving the subset-sum problem, including both classical and quantum algorithms. The paper went on to present a novel algorithm that beat the previous best algorithm known at the time. The complex nature of the algorithm made it difficult to see a path for implementation on the Quantum Experience machine and the exponential cost - only slightly better than the best classical algorithm - left us looking for a different approach for solving this problem. We present here a new quantum algorithm for solving the subset-sum problem that for many cases should lead to O(poly(n))-time to solution. The work is reminiscent of the verification procedure used in a polynomial-time algorithm for the quantum Arthur-Merlin games presented elsewhere, where the use of a quantum binary search to find a maximum eigenvalue in the final output stage has been adapted to the subset-sum problem as in another paper.
Deep Reinforcement Learning for Routing a Heterogeneous Fleet of Vehicles
Venue: arXiv cs.NE 2019
Year: 2019

Motivated by the promising advances of deep-reinforcement learning (DRL) applied to cooperative multi-agent systems we propose a model and learning procedure to solve the Capacitated Multi-Vehicle Routing Problem (CMVRP) with fixed fleet size. Our learning procedure follows a centralized-training and decentralized-execution paradigm. We empirically test our model and showed its capability for producing near-optimal solutions through cooperative actions. In large instances, our model generates better solutions than other commonly used heuristics. Additionally, our model can solve arbitrary instances of the CMVRP without requiring re-training.
A Simple Dynamization of Trapezoidal Point Location in Planar Subdivisions
Venue: arXiv cs.CG 2019
Year: 2019

We study how to dynamize the Trapezoidal Search Tree - a well known randomized point location structure for planar subdivisions of kinetic line segments. Our approach naturally extends incremental leaf-level insertions to recursive methods and allows adaptation for the online setting. Moreover, the dynamization carries over to the Trapezoidal Search DAG, offering a linear sized data structure with logarithmic point location costs as a by-product. On a set $S$ of non-crossing segments, each update performs expected ${\mathcal O}(\log^2|S|)$ operations. We demonstrate the practicality of our method with an open-source implementation, based on the Computational Geometry Algorithms Library, and experiments on the update performance.
DAVID: Dual-Attentional Video Deblurring
Venue: arXiv cs.CV 2019
Year: 2019

Blind video deblurring restores sharp frames from a blurry sequence without any prior. It is a challenging task because the blur due to camera shake, object movement and defocusing is heterogeneous in both temporal and spatial dimensions. Traditional methods train on datasets synthesized with a single level of blur, and thus do not generalize well across levels of blurriness. To address this challenge, we propose a dual attention mechanism to dynamically aggregate temporal cues for deblurring with an end-to-end trainable network structure. Specifically, an internal attention module adaptively selects the optimal temporal scales for restoring the sharp center frame. An external attention module adaptively aggregates and refines multiple sharp frame estimates, from several internal attention modules designed for different blur levels. To train and evaluate on more diverse blur severity levels, we propose a Challenging DVD dataset generated from the raw DVD video set by pooling frames with different temporal windows. Our framework achieves consistently better performance on this more challenging dataset while obtaining strongly competitive results on the original DVD benchmark. Extensive ablative studies and qualitative visualizations further demonstrate the advantage of our method in handling real video blur.
Dependability Assessment of the Android OS through Fault Injection
Venue: arXiv cs.SE 2019
Year: 2019

The reliability of mobile devices is a challenge for vendors, since the mobile software stack has significantly grown in complexity. In this paper, we study how to assess the impact of faults on the quality of user experience in the Android mobile OS through fault injection. We first address the problem of identifying a realistic fault model for the Android OS, by providing to developers a set of lightweight and systematic guidelines for fault modeling. Then, we present an extensible fault injection tool (AndroFIT) to apply such fault model on actual, commercial Android devices. Finally, we present a large fault injection experimentation on three Android products from major vendors, and point out several reliability issues and opportunities for improving the Android OS.
Generalized Data Placement Strategies for Racetrack Memories
Venue: arXiv cs.DC 2019
Year: 2019

Ultra-dense non-volatile racetrack memories (RTMs) have been investigated at various levels in the memory hierarchy for improved performance and reduced energy consumption. However, the innate shift operations in RTMs hinder their applicability to replace low-latency on-chip memories. Recent research has demonstrated that intelligent placement of memory objects in RTMs can significantly reduce the amount of shifts with no hardware overhead, albeit for specific system setups. However, existing placement strategies may lead to sub-optimal performance when applied to different architectures. In this paper we look at generalized data placement mechanisms that improve upon existing ones by taking into account the underlying memory architecture and the timing and liveliness information of memory objects. We propose a novel heuristic and a formulation using genetic algorithms that optimize key performance parameters. We show that, on average, our generalized approach improves the number of shifts, performance and energy consumption by 4.3x, 46% and 55% respectively compared to the state-of-the-art.
Learning Norms from Stories: A Prior for Value Aligned Agents
Venue: arXiv cs.AI 2019
Year: 2019

Value alignment is a property of an intelligent agent indicating that it can only pursue goals and activities that are beneficial to humans. Traditional approaches to value alignment use imitation learning or preference learning to infer the values of humans by observing their behavior. We introduce a complementary technique in which a value aligned prior is learned from naturally occurring stories which encode societal norms. Training data is sourced from the childrens educational comic strip, Goofus and Gallant. In this work, we train multiple machine learning models to classify natural language descriptions of situations found in the comic strip as normative or non normative by identifying if they align with the main characters behavior. We also report the models performance when transferring to two unrelated tasks with little to no additional training on the new task.