OpenRaiser/Intern-Atlas huggingface dataset:
Thompson Sampling for Adversarial Bit Prediction
Venue: arXiv cs.LG 2019
Year: 2019

We study the Thompson sampling algorithm in an adversarial setting, specifically, for adversarial bit prediction. We characterize the bit sequences with the smallest and largest expected regret. Among sequences of length $T$ with $k < \frac{T}{2}$ zeros, the sequences of largest regret consist of alternating zeros and ones followed by the remaining ones, and the sequence of smallest regret consists of ones followed by zeros. We also bound the regret of those sequences, the worse case sequences have regret $O(\sqrt{T})$ and the best case sequence have regret $O(1)$. We extend our results to a model where false positive and false negative errors have different weights. We characterize the sequences with largest expected regret in this generalized setting, and derive their regret bounds. We also show that there are sequences with $O(1)$ regret.
The Impact of Projection and Backboning on Network Topologies
Venue: arXiv cs.SI 2019
Year: 2019

Bipartite networks are a well known strategy to study a variety of phenomena. The commonly used method to deal with this type of network is to project the bipartite data into a unipartite weighted graph and then using a backboning technique to extract only the meaningful edges. Despite the wide availability of different methods both for projection and backboning, we believe that there has been little attention to the effect that the combination of these two processes has on the data and on the resulting network topology. In this paper we study the effect that the possible combinations of projection and backboning techniques have on a bipartite network. We show that the 12 methods group into two clusters producing unipartite networks with very different topologies. We also show that the resulting level of network centralization is highly affected by the combination of projection and backboning applied.
Joint Detection of Malicious Domains and Infected Clients
Venue: arXiv cs.LG 2019
Year: 2019

Detection of malware-infected computers and detection of malicious web domains based on their encrypted HTTPS traffic are challenging problems, because only addresses, timestamps, and data volumes are observable. The detection problems are coupled, because infected clients tend to interact with malicious domains. Traffic data can be collected at a large scale, and antivirus tools can be used to identify infected clients in retrospect. Domains, by contrast, have to be labeled individually after forensic analysis. We explore transfer learning based on sluice networks; this allows the detection models to bootstrap each other. In a large-scale experimental study, we find that the model outperforms known reference models and detects previously unknown malware, previously unknown malware families, and previously unknown malicious domains.
The Fluted Fragment with Transitivity
Venue: arXiv cs.LO 2019
Year: 2019

We study the satisfiability problem for the fluted fragment extended with transitive relations. We show that the logic enjoys the finite model property when only one transitive relation is available. On the other hand we show that the satisfiability problem is undecidable already for the two-variable fragment of the logic in the presence of three transitive relations.
Verification and Control of Turn-Based Probabilistic Real-Time Games
Venue: arXiv cs.LO 2019
Year: 2019

Quantitative verification techniques have been developed for the formal analysis of a variety of probabilistic models, such as Markov chains, Markov decision process and their variants. They can be used to produce guarantees on quantitative aspects of system behaviour, for example safety, reliability and performance, or to help synthesise controllers that ensure such guarantees are met. We propose the model of turn-based probabilistic timed multi-player games, which incorporates probabilistic choice, real-time clocks and nondeterministic behaviour across multiple players. Building on the digital clocks approach for the simpler model of probabilistic timed automata, we show how to compute the key measures that underlie quantitative verification, namely the probability and expected cumulative price to reach a target. We illustrate this on case studies from computer security and task scheduling.
Uncertainty Modeling and Analysis of the European X-ray Free Electron Laser Cavities Manufacturing Process
Venue: arXiv cs.CE 2019
Year: 2019

This paper reports on comprehensive efforts on uncertainty quantification and global sensitivity analysis for accelerator cavity design. As a case study object the TESLA shaped superconducting cavities, as produced for the European X-ray Free Electron Laser (EXFEL), are selected. The choice for these cavities is explained by the available measurement data that can be leveraged to substantiate the simulation model. Each step of the manufacturing chain is documented together with the involved uncertainties. Several of these steps are mimicked on the simulation side, e.g. by introducing a random eigenvalue problem. The uncertainties are then quantified numerically and in particular the sensitivities give valuable insight into the systems behavior. We also compare these findings to purely statistical studies carried out for the manufactured cavities. More advanced, adaptive, surrogate modeling techniques are adopted, which are crucial to incorporate a large number of uncertain parameters. The main contribution is the detailed comparison and fusion of measurement results for the EXFEL cavities on the one hand and simulation based uncertainty studies on the other hand. After introducing the quantities of physical interest for accelerator cavities and the Maxwell eigenvalue problem, the details on the manufacturing of the EXFEL cavities and measurements are reported. This is followed by uncertainty modeling with quantification studies.
Privacy Preserving QoE Modeling using Collaborative Learning
Venue: arXiv cs.LG 2019
Year: 2019

Machine Learning based Quality of Experience (QoE) models potentially suffer from over-fitting due to limitations including low data volume, and limited participant profiles. This prevents models from becoming generic. Consequently, these trained models may under-perform when tested outside the experimented population. One reason for the limited datasets, which we refer in this paper as small QoE data lakes, is due to the fact that often these datasets potentially contain user sensitive information and are only collected throughout expensive user studies with special user consent. Thus, sharing of datasets amongst researchers is often not allowed. In recent years, privacy preserving machine learning models have become important and so have techniques that enable model training without sharing datasets but instead relying on secure communication protocols. Following this trend, in this paper, we present Round-Robin based Collaborative Machine Learning model training, where the model is trained in a sequential manner amongst the collaborated partner nodes. We benchmark this work using our customized Federated Learning mechanism as well as conventional Centralized and Isolated Learning methods.
A Multitask Network for Localization and Recognition of Text in Images
Venue: arXiv cs.CL 2019
Year: 2019

We present an end-to-end trainable multi-task network that addresses the problem of lexicon-free text extraction from complex documents. This network simultaneously solves the problems of text localization and text recognition and text segments are identified with no post-processing, cropping, or word grouping. A convolutional backbone and Feature Pyramid Network are combined to provide a shared representation that benefits each of three model heads: text localization, classification, and text recognition. To improve recognition accuracy, we describe a dynamic pooling mechanism that retains high-resolution information across all RoIs. For text recognition, we propose a convolutional mechanism with attention which out-performs more common recurrent architectures. Our model is evaluated against benchmark datasets and comparable methods and achieves high performance in challenging regimes of non-traditional OCR.
Building a Benchmark Dataset and Classifiers for Sentence-Level Findings in AP Chest X-rays
Venue: arXiv cs.CV 2019
Year: 2019

Chest X-rays are the most common diagnostic exams in emergency rooms and hospitals. There has been a surge of work on automatic interpretation of chest X-rays using deep learning approaches after the availability of large open source chest X-ray dataset from NIH. However, the labels are not sufficiently rich and descriptive for training classification tools. Further, it does not adequately address the findings seen in Chest X-rays taken in anterior-posterior (AP) view which also depict the placement of devices such as central vascular lines and tubes. In this paper, we present a new chest X-ray benchmark database of 73 rich sentence-level descriptors of findings seen in AP chest X-rays. We describe our method of obtaining these findings through a semi-automated ground truth generation process from crowdsourcing of clinician annotations. We also present results of building classifiers for these findings that show that such higher granularity labels can also be learned through the framework of deep learning classifiers.
Detection of Myocardial Infarction Based on Novel Deep Transfer Learning Methods for Urban Healthcare in Smart Cities
Venue: arXiv cs.LG 2019
Year: 2019

. In this paper, an effective computer-aided diagnosis (CAD) system is presented to detect MI signals using the convolution neural network (CNN) for urban healthcare in smart cities. Two types of transfer learning techniques are employed to retrain the pre-trained VGG-Net (Fine-tuning and VGG-Net as fixed feature extractor) and obtained two new networks VGG-MI1 and VGG-MI2. In the VGG-MI1 model, the last layer of the VGG-Net model is replaced with a specific layer according to our requirements and various functions are optimized to reduce overfitting. In the VGG-MI2 model, one layer of the VGG-Net model is selected as a feature descriptor of the ECG images to describe it with informative features. Considering the limited availability of dataset, ECG data is augmented which has increased the classification performance. Physikalisch-technische bundesanstalt (PTB) Diagnostic ECG database is used for experimentation, which has been widely employed in MI detection studies. In case of using VGG-MI1, we achieved an accuracy, sensitivity, and specificity of 99.02%, 98.76%, and 99.17%, respectively and we achieved an accuracy of 99.22%, a sensitivity of 99.15%, and a specificity of 99.49% with VGG-MI2 model. Experimental results validate the efficiency of the proposed system in terms of accuracy sensitivity, and specificity.
Collective Mobile Sequential Recommendation: A Recommender System for Multiple Taxicabs
Venue: arXiv cs.DS 2019
Year: 2019

Mobile sequential recommendation was originally designed to find a promising route for a single taxicab. Directly applying it for multiple taxicabs may cause an excessive overlap of recommended routes. The multi-taxicab recommendation problem is challenging and has been less studied. In this paper, we first formalize a collective mobile sequential recommendation problem based on a classic mathematical model, which characterizes time-varying influence among competing taxicabs. Next, we propose a new evaluation metric for a collection of taxicab routes aimed to minimize the sum of potential travel time. We then develop an efficient algorithm to calculate the metric and design a greedy recommendation method to approximate the solution. Finally, numerical experiments show the superiority of our methods. In trace-driven simulation, the set of routes recommended by our method significantly outperforms those obtained by conventional methods.
Learning Set-equivariant Functions with SWARM Mappings
Venue: arXiv cs.LG 2019
Year: 2019

In this work we propose a new neural network architecture that efficiently implements and learns general purpose set-equivariant functions. Such a function f maps a set of entities x = {x1, . . . , xn} from one domain to a set of same cardinality y = f (x) = {y1, . . . , yn} in another domain regardless of the ordering of the entities. The architecture is based on a gated recurrent network which is iteratively applied to all entities individually and at the same time syncs with the progression of the whole population. In reminiscence to this pattern, which can be frequently observed in nature, we call our approach SWARM mapping. Set-equivariant and generally permutation invariant functions are important building blocks for many state of the art machine learning approaches. Even in applications where the permutation invariance is not of primary interest, as to be seen in the recent success of attention based transformer models (Vaswani et. al. 2017). Accordingly, we demonstrate the power and usefulness of SWARM mappings in different applications. We compare the performance of our approach with another recently proposed set-equivariant function, the Set Transformer (Lee et.al. 2018) and we demonstrate that models solely based on SWARM layers gives state of the art results.
Comparative study of Joint Image Encryption and Compression Schemes: A Review
Venue: arXiv cs.CR 2019
Year: 2019

With the development of imaging methods in wireless communications, enhancing the security and efficiency of image transfer requires image compression and encryption schemes. In conventional methods, encryption and compression are two separate processes, therefore an adversary can organize his attack more simply but if these two processes are combined, the output uncertainty increases. As a result, adversaries face more difficulties, and schemes will be more secure. This paper introduces a number of the most important criteria for the efficiency and security evaluation of joint image encryption and compression (JIEC) schemes. These criteria were then employed to compare the schemes. The comparison results were analysed to propose suggestions and strategies for future research to develop secure and efficient JIEC schemes.
Algorithms for Similarity Search and Pseudorandomness
Venue: arXiv cs.DS 2019
Year: 2019

We study the problem of approximate near neighbor (ANN) search and show the following results: - An improved framework for solving the ANN problem using locality-sensitive hashing, reducing the number of evaluations of locality-sensitive hash functions and the word-RAM complexity compared to the standard framework. - A framework for solving the ANN problem with space-time tradeoffs as well as tight upper and lower bounds for the space-time tradeoff of framework solutions to the ANN problem under cosine similarity. - A novel approach to solving the ANN problem on sets along with a matching lower bound, improving the state of the art. - A self-tuning version of the algorithm is shown through experiments to outperform existing similarity join algorithms. - Tight lower bounds for asymmetric locality-sensitive hashing which has applications to the approximate furthest neighbor problem, orthogonal vector search, and annulus queries. - A proof of the optimality of a well-known Boolean locality-sensitive hashing scheme. We study the problem of efficient algorithms for producing high-quality pseudorandom numbers and obtain the following results: - A deterministic algorithm for generating pseudorandom numbers of arbitrarily high quality in constant time using near-optimal space. - A randomized construction of a family of hash functions that outputs pseudorandom numbers of arbitrarily high quality with space usage and running time nearly matching known cell-probe lower bounds.
Learning with fuzzy hypergraphs: a topical approach to query-oriented text summarization
Venue: arXiv cs.CL 2019
Year: 2019

Existing graph-based methods for extractive document summarization represent sentences of a corpus as the nodes of a graph or a hypergraph in which edges depict relationships of lexical similarity between sentences. Such approaches fail to capture semantic similarities between sentences when they express a similar information but have few words in common and are thus lexically dissimilar. To overcome this issue, we propose to extract semantic similarities based on topical representations of sentences. Inspired by the Hierarchical Dirichlet Process, we propose a probabilistic topic model in order to infer topic distributions of sentences. As each topic defines a semantic connection among a group of sentences with a certain degree of membership for each sentence, we propose a fuzzy hypergraph model in which nodes are sentences and fuzzy hyperedges are topics. To produce an informative summary, we extract a set of sentences from the corpus by simultaneously maximizing their relevance to a user-defined query, their centrality in the fuzzy hypergraph and their coverage of topics present in the corpus. We formulate a polynomial time algorithm building on the theory of submodular functions to solve the associated optimization problem. A thorough comparative analysis with other graph-based summarization systems is included in the paper. Our obtained results show the superiority of our method in terms of content coverage of the summaries.
Adaptive Period Embedding for Representing Oriented Objects in Aerial Images
Venue: arXiv cs.CV 2019
Year: 2019

We propose a novel method for representing oriented objects in aerial images named Adaptive Period Embedding (APE). While traditional object detection methods represent object with horizontal bounding boxes, the objects in aerial images are oritented. Calculating the angle of object is an yet challenging task. While almost all previous object detectors for aerial images directly regress the angle of objects, they use complex rules to calculate the angle, and their performance is limited by the rule design. In contrast, our method is based on the angular periodicity of oriented objects. The angle is represented by two two-dimensional periodic vectors whose periods are different, the vector is continuous as shape changes. The label generation rule is more simple and reasonable compared with previous methods. The proposed method is general and can be applied to other oriented detector. Besides, we propose a novel IoU calculation method for long objects named length independent IoU (LIIoU). We intercept part of the long side of the target box to get the maximum IoU between the proposed box and the intercepted target box. Thereby, some long boxes will have corresponding positive samples. Our method reaches the 1st place of DOAI2019 competition task1 (oriented object) held in workshop on Detecting Objects in Aerial Images in conjunction with IEEE CVPR 2019.
Andro-Simnet: Android Malware Family Classification Using Social Network Analysis
Venue: arXiv cs.CR 2019
Year: 2019

While the rapid adaptation of mobile devices changes our daily life more conveniently, the threat derived from malware is also increased. There are lots of research to detect malware to protect mobile devices, but most of them adopt only signature-based malware detection method that can be easily bypassed by polymorphic and metamorphic malware. To detect malware and its variants, it is essential to adopt behavior-based detection for efficient malware classification. This paper presents a system that classifies malware by using common behavioral characteristics along with malware families. We measure the similarity between malware families with carefully chosen features commonly appeared in the same family. With the proposed similarity measure, we can classify malware by malware's attack behavior pattern and tactical characteristics. Also, we apply a community detection algorithm to increase the modularity within each malware family network aggregation. To maintain high classification accuracy, we propose a process to derive the optimal weights of the selected features in the proposed similarity measure. During this process, we find out which features are significant for representing the similarity between malware samples. Finally, we provide an intuitive graph visualization of malware samples which is helpful to understand the distribution and likeness of the malware networks. In the experiment, the proposed system achieved 97% accuracy for malware classification and 95% accuracy for prediction by K-fold cross-validation using the real malware dataset.
Protecting shared information in networks: a network security game with strategic attacks
Venue: arXiv cs.SI 2019
Year: 2019

A digital security breach, by which confidential information is leaked, does not only affect the agent whose system is infiltrated, but is also detrimental to other agents socially connected to the infiltrated system. Although it has been argued that these externalities create incentives to under-invest in security, this presumption is challenged by the possibility of strategic adversaries that attack the least protected agents. In this paper we study a new model of security games in which agents share tokens of sensitive information in a network of contacts. The agents have the opportunity to invest in security to protect against an attack that can be either strategically or randomly targeted. We show that, in the presence of random attack, under-investments always prevail at the Nash equilibrium in comparison with the social optimum. Instead, when the attack is strategic, either under-investments or over-investments are possible, depending on the network topology and on the characteristics of the process of the spreading of information. Actually, agents invest more in security than socially optimal when dependencies among agents are low (which can happen because the information network is sparsely connected or because the probability that information tokens are shared is small). These over-investments pass on to under-investments when information sharing is more likely (and therefore, when the risk brought by the attack is higher).
Image Retrieval and Pattern Spotting using Siamese Neural Network
Venue: arXiv cs.CV 2019
Year: 2019

This paper presents a novel approach for image retrieval and pattern spotting in document image collections. The manual feature engineering is avoided by learning a similarity-based representation using a Siamese Neural Network trained on a previously prepared subset of image pairs from the ImageNet dataset. The learned representation is used to provide the similarity-based feature maps used to find relevant image candidates in the data collection given an image query. A robust experimental protocol based on the public Tobacco800 document image collection shows that the proposed method compares favorably against state-of-the-art document image retrieval methods, reaching 0.94 and 0.83 of mean average precision (mAP) for retrieval and pattern spotting (IoU=0.7), respectively. Besides, we have evaluated the proposed method considering feature maps of different sizes, showing the impact of reducing the number of features in the retrieval performance and time-consuming.
Smaller Text Classifiers with Discriminative Cluster Embeddings
Venue: arXiv cs.CL 2019
Year: 2019

Word embedding parameters often dominate overall model sizes in neural methods for natural language processing. We reduce deployed model sizes of text classifiers by learning a hard word clustering in an end-to-end manner. We use the Gumbel-Softmax distribution to maximize over the latent clustering while minimizing the task loss. We propose variations that selectively assign additional parameters to words, which further improves accuracy while still remaining parameter-efficient.