OpenRaiser/Intern-Atlas huggingface dataset:
Chauffeuring a Crashed Robot from a Disk
Venue: arXiv cs.DC 2019
Year: 2019

Evacuation of robots from a disk has attained a lot of attention recently. We visit the problem from the perspective of fault-tolerance. We consider two robots trying to evacuate from a disk via a single hidden exit on the perimeter of the disk. The robots communicate wirelessly. The robots are susceptible to crash faults after which they stop moving and communicating. We design the algorithms for tolerating one fault. The objective is to minimize the worst-case time required to evacuate both the robots from the disk. When the non-faulty robot chauffeurs the crashed robot, it takes $α\geq 1$ amount of time to travel unit distance. With this, we also provide a lower bound for the evacuation time. Further, we evaluate the worst-case of the algorithms for different values of $α$ and the crash time.
FASTER: Fusion AnalyticS for public Transport Event Response
Venue: arXiv cs.CY 2019
Year: 2019

Increasing urban concentration raises operational challenges that can benefit from integrated monitoring and decision support. Such complex systems need to leverage the full stack of analytical methods, from state estimation using multi-sensor fusion for situational awareness, to prediction and computation of optimal responses. The FASTER platform that we describe in this work, deployed at nation scale and handling 1.5 billion public transport trips a year, offers such a full stack of techniques for this large-scale, real-time problem. FASTER provides fine-grained situational awareness and real-time decision support with the objective of improving the public transport commuter experience. The methods employed range from statistical machine learning to agent-based simulation and mixed-integer optimization. In this work we present an overview of the challenges and methods involved, with details of the commuter movement prediction module, as well as a discussion of open problems.
Approximate Identification of the Optimal Epidemic Source in Complex Networks
Venue: arXiv cs.SI 2019
Year: 2019

We consider the problem of identifying the source of an epidemic, spreading through a network, from a complete observation of the infected nodes in a snapshot of the network. Previous work on the problem has often employed geometric, spectral or heuristic approaches to identify the source, with the trees being the most studied network topology. We take a fully statistical approach and derive novel recursions to compute the Bayes optimal solution, under a susceptible-infected (SI) epidemic model. Our analysis is time and rate independent, and holds for general network topologies. We then provide two tractable algorithms for solving these recursions, a mean-field approximation and a greedy approach, and evaluate their performance on real and synthetic networks. Real networks are far from tree-like and an emphasis will be given to networks with high transitivity, such as social networks and those with communities. We show that on such networks, our approaches significantly outperform geometric and spectral centrality measures, most of which perform no better than random guessing. Both the greedy and mean-field approximation are scalable to large sparse networks.
A Tree Pattern Matching Algorithm for XML Queries with Structural Preferences
Venue: arXiv cs.DB 2019
Year: 2019

In the XML community, exact queries allow users to specify exactly what they want to check and/or retrieve in an XML document. When they are applied to a semi-structured document or to a document with an overly complex model, the lack or the ignorance of the explicit document model (DTD-Document Type Definition, Schema, etc.) increases the risk of ob-taining an empty result set when the query is too specific, or, too large result set when it is too vague (e.g. it contains wildcards such as "*"). The reason is that in both cases, users write queries according to the document model they have in mind; this can be very far from the one that can actually be extracted from the document. Opposed to exact queries, preference queries are more flexible and can be relaxed to expand the search space during their evalua-tions. Indeed, during their evaluation, certain constraints (the preferences they contain) can be relaxed if necessary to avoid precisely empty results; moreover, the returned answers can be filtered to retain only the best ones. This paper presents an algorithm for evaluating such queries inspired by the TreeMatch algorithm proposed by Yao et al. for exact queries. In the pro-posed algorithm, the best answers are obtained by using an adaptation of the Skyline operator (defined in relational databases) in the context of documents (trees) to incrementally filter into the partial solutions set, those which satisfy the maximum of preferential constraints. The only restriction imposed on documents is No-Self-Containment.
Highly Scalable and Flexible Model for Effective Aggregation of Context-based Data in Generic IIoT Scenarios
Venue: arXiv cs.CY 2019
Year: 2019

Interconnectivity of production machines is a key feature of the Industrial Internet of Things (IIoT). This feature allows for many advantages in producing. Configuration and maintenance gets easier, as access to the given production unit is not necessarily coupled to physical presence. Customized production of goods is easily possible, reducing production times and increasing throughput. There are, however, also dangers to the increasing talkativeness of industrial production machines. The more open a system is, the more points of entry for an attacker exist. Furthermore, the amount of data a production site also increases rapidly due to the integrated intelligence and interconnectivity. To keep track of this data in order to detect attacks and errors in the production site, it is necessary to smartly aggregate and evaluate the data. In this paper, we present a new approach for collecting, aggregating and analysing data from different sources and on three different levels of abstraction. Our model is event-centric, considering every occurrence of information inside the system as an event. In the lowest level of abstraction, singular packets are collected, correlated with log-entries and analysed. On the highest level of abstraction, networks are pictured as a connectivity graph, enriched with information about host-based activities. Furthermore, we describe our work in progress of evaluating our aggregation model on two different system settings. In the first scenario, we verify the usability of our model in a remote maintenance application. In the second scenario, we evaluate our model in the context of network sniffing and correlation with log-files. First results show that our model is a promising solution to cope with increasing amounts of data and to correlate information from different types of sources.
Non-Differentiable Supervised Learning with Evolution Strategies and Hybrid Methods
Venue: arXiv cs.NE 2019
Year: 2019

In this work we show that Evolution Strategies (ES) are a viable method for learning non-differentiable parameters of large supervised models. ES are black-box optimization algorithms that estimate distributions of model parameters; however they have only been used for relatively small problems so far. We show that it is possible to scale ES to more complex tasks and models with millions of parameters. While using ES for differentiable parameters is computationally impractical (although possible), we show that a hybrid approach is practically feasible in the case where the model has both differentiable and non-differentiable parameters. In this approach we use standard gradient-based methods for learning differentiable weights, while using ES for learning non-differentiable parameters - in our case sparsity masks of the weights. This proposed method is surprisingly competitive, and when parallelized over multiple devices has only negligible training time overhead compared to training with gradient descent. Additionally, this method allows to train sparse models from the first training step, so they can be much larger than when using methods that require training dense models first. We present results and analysis of supervised feed-forward models (such as MNIST and CIFAR-10 classification), as well as recurrent models, such as SparseWaveRNN for text-to-speech.
Image Encryption Algorithm Based on Facebook Social Network
Venue: arXiv cs.MM 2019
Year: 2019

Facebook is the online social networks (OSNs) platform with the largest number of users in the world today, information protection based on Facebook social network platform have important practical significance. Since the information users share on social networks is often based on images, this paper proposes a more secure image encryption algorithm based on Facebook social network platform to ensure the loss of information as much as possible. When the sender encrypts the image for uploading, it can first resist the third party's attack on the encrypted image and prevent the image data from leaking, simultaneously processed by some unknown processing such as compression and filtering of the image on the Facebook platform, the receiver can still decrypt the corresponding image data.
The Concept of Cyber Defence Exercises (CDX): Planning, Execution, Evaluation
Venue: arXiv cs.CR 2019
Year: 2019

This paper discusses the concept of cyber defence exercises -CDX- that are very important tool when it comes to enhancing the safety awareness of cyberspace, testing an organization's ability to put up resistance and respond to different cyber events to establish the secure environment, gathering empirical data related to security, and looking at the practical training of experts on this subject. The exercises can give ideas to the decision makers about the precautions in the cybersecurity area and to the officials, institutions, organizations, and staff who are responsible on the cyber tools, techniques, and procedures that can be developed for this field. In the cyber defense exercises, the scenarios that are simulated closest to reality which provides very important contributions by bringing together the necessity of making the best decisions and management capabilities under the cyber crisis by handling stress and coordinated movement as a team. The objective of this paper is to address the issue from a scientific point of view by setting out the stages of planning, implementation, and evaluation of these exercises, taking into account and comparing international firefighting exercises. Another aim of the work is to be able to reveal the necessary processes that are required for all kind of cyber exercises, regardless of the type, although the processes involved vary according to the target mass of the planned exercise.
Fighting Quantization Bias With Bias
Venue: arXiv cs.LG 2019
Year: 2019

Low-precision representation of deep neural networks (DNNs) is critical for efficient deployment of deep learning application on embedded platforms, however, converting the network to low precision degrades its performance. Crucially, networks that are designed for embedded applications usually suffer from increased degradation since they have less redundancy. This is most evident for the ubiquitous MobileNet architecture which requires a costly quantization-aware training cycle to achieve acceptable performance when quantized to 8-bits. In this paper, we trace the source of the degradation in MobileNets to a shift in the mean activation value. This shift is caused by an inherent bias in the quantization process which builds up across layers, shifting all network statistics away from the learned distribution. We show that this phenomenon happens in other architectures as well. We propose a simple remedy - compensating for the quantization induced shift by adding a constant to the additive bias term of each channel. We develop two simple methods for estimating the correction constants - one using iterative evaluation of the quantized network and one where the constants are set using a short training phase. Both methods are fast and require only a small amount of unlabeled data, making them appealing for rapid deployment of neural networks. Using the above methods we are able to match the performance of training-based quantization of MobileNets at a fraction of the cost.
Extracting Visual Knowledge from the Internet: Making Sense of Image Data
Venue: arXiv cs.CV 2019
Year: 2019

Recent successes in visual recognition can be primarily attributed to feature representation, learning algorithms, and the ever-increasing size of labeled training data. Extensive research has been devoted to the first two, but much less attention has been paid to the third. Due to the high cost of manual labeling, the size of recent efforts such as ImageNet is still relatively small in respect to daily applications. In this work, we mainly focus on how to automatically generate identifying image data for a given visual concept on a vast scale. With the generated image data, we can train a robust recognition model for the given concept. We evaluate the proposed webly supervised approach on the benchmark Pascal VOC 2007 dataset and the results demonstrates the superiority of our proposed approach in image data collection.
Crypto art: A decentralized view
Venue: arXiv cs.CY 2019
Year: 2019

This is a decentralized position paper on crypto art, which includes viewpoints from different actors of the system: artists, collectors, galleries, art scholars, data scientists. The writing process went as follows: a general definition of the topic was put forward by two of the authors (Franceschet and Colavizza), and used as reference to ask to a set of diverse authors to contribute with their viewpoints asynchronously and independently. No guidelines were offered before the first draft, if not to reach a minimum of words to justify a separate section/contribution. Afterwards, all authors read and commented on each other's work and minimal editing was done. Every author was asked to suggest open questions and future perspectives on the topic of crypto art from their vantage point, while keeping full control of their own sections at all times. While this process does not necessarily guarantee the uniformity expected from, say, a research article, it allows for multiple voices to emerge and provide for a contribution on a common topic. The ending section offers an attempt to pull all these threads together into a perspective on the future of crypto art.
Efficient Project Gradient Descent for Ensemble Adversarial Attack
Venue: arXiv cs.LG 2019
Year: 2019

Recent advances show that deep neural networks are not robust to deliberately crafted adversarial examples which many are generated by adding human imperceptible perturbation to clear input. Consider $l_2$ norms attacks, Project Gradient Descent (PGD) and the Carlini and Wagner (C\&W) attacks are the two main methods, where PGD control max perturbation for adversarial examples while C\&W approach treats perturbation as a regularization term optimized it with loss function together. If we carefully set parameters for any individual input, both methods become similar. In general, PGD attacks perform faster but obtains larger perturbation to find adversarial examples than the C\&W when fixing the parameters for all inputs. In this report, we propose an efficient modified PGD method for attacking ensemble models by automatically changing ensemble weights and step size per iteration per input. This method generates smaller perturbation adversarial examples than PGD method while remains efficient as compared to C\&W method. Our method won the first place in IJCAI19 Targeted Adversarial Attack competition.
Extension of Rough Set Based on Positive Transitive Relation
Venue: arXiv cs.AI 2019
Year: 2019

The application of rough set theory in incomplete information systems is a key problem in practice since missing values almost always occur in knowledge acquisition due to the error of data measuring, the limitation of data collection, or the limitation of data comprehension, etc. An incomplete information system is mainly processed by compressing the indiscernibility relation. The existing rough set extension models based on tolerance or symmetric similarity relations typically discard one relation among the reflexive, symmetric and transitive relations, especially the transitive relation. In order to overcome the limitations of the current rough set extension models, we define a new relation called the positive transitive relation and then propose a novel rough set extension model built upon which. The new model holds the merit of the existing rough set extension models while avoids their limitations of discarding transitivity or symmetry. In comparison to the existing extension models, the proposed model has a better performance in processing the incomplete information systems while substantially reducing the computational complexity, taking into account the relation of tolerance and similarity of positive transitivity, and supplementing the related theories in accordance to the intuitive classification of incomplete information. In summary, the positive transitive relation can improve current theoretical analysis of incomplete information systems and the newly proposed extension model is more suitable for processing incomplete information systems and has a broad application prospect.
Unsupervised Feature Learning with K-means and An Ensemble of Deep Convolutional Neural Networks for Medical Image Classification
Venue: arXiv cs.CV 2019
Year: 2019

Medical image analysis using supervised deep learning methods remains problematic because of the reliance of deep learning methods on large amounts of labelled training data. Although medical imaging data repositories continue to expand there has not been a commensurate increase in the amount of annotated data. Hence, we propose a new unsupervised feature learning method that learns feature representations to then differentiate dissimilar medical images using an ensemble of different convolutional neural networks (CNNs) and K-means clustering. It jointly learns feature representations and clustering assignments in an end-to-end fashion. We tested our approach on a public medical dataset and show its accuracy was better than state-of-the-art unsupervised feature learning methods and comparable to state-of-the-art supervised CNNs. Our findings suggest that our method could be used to tackle the issue of the large volume of unlabelled data in medical imaging repositories.
Applications of Gaussian Binomials to Coding Theory for Deletion Error Correction
Venue: arXiv cs.IT 2019
Year: 2019

We present new applications on $q$-binomials, also known as Gaussian binomial coefficients. Our main theorems determine cardinalities of certain error-correcting codes based on Varshamov-Tenengolts codes and prove a curious phenomenon relating to deletion sphere for specific cases.
How Different Is It Between Machine-Generated and Developer-Provided Patches? An Empirical Study on The Correct Patches Generated by Automated Program Repair Techniques
Venue: arXiv cs.SE 2019
Year: 2019

Background: Over the years, Automated Program Repair (APR) has attracted much attention from both academia and industry since it can reduce the costs in fixing bugs. However, how to assess the patch correctness remains to be an open challenge. Two widely adopted ways to approach this challenge, including manually checking and validating using automated generated tests, are biased (i.e., suffering from subjectivity and low precision respectively). Aim: To address this concern, we propose to conduct an empirical study towards understanding the correct patches that are generated by existing state-of-the-art APR techniques, aiming at providing guidelines for future assessment of patches. Method: To this end, we first present a Literature Review (LR) on the reported correct patches generated by recent techniques on the Defects4J benchmark and collect 177 correct patches after a process of sanity check. We investigate how these machine-generated correct patches achieve semantic equivalence, but syntactic difference compared with developer-provided ones, how these patches distribute in different projects and APR techniques, and how the characteristics of a bug affect the patches generated for it. Results: Our main findings include 1) we do not need to fix bugs exactly like how developers do since we observe that 25.4% (45/177) of the correct patches generated by APR techniques are syntactically different from developer-provided ones; 2) the distribution of machine-generated correct patches diverges for the aspects of Defects4J projects and APR techniques; and 3) APR techniques tend to generate patches that are different from those by developers for bugs with large patch sizes. Conclusion: Our study not only verifies the conclusions from previous studies but also highlights implications for future study towards assessing patch correctness.
Making Asynchronous Stochastic Gradient Descent Work for Transformers
Venue: arXiv cs.CL 2019
Year: 2019

Asynchronous stochastic gradient descent (SGD) is attractive from a speed perspective because workers do not wait for synchronization. However, the Transformer model converges poorly with asynchronous SGD, resulting in substantially lower quality compared to synchronous SGD. To investigate why this is the case, we isolate differences between asynchronous and synchronous methods to investigate batch size and staleness effects. We find that summing several asynchronous updates, rather than applying them immediately, restores convergence behavior. With this hybrid method, Transformer training for neural machine translation task reaches a near-convergence level 1.36x faster in single-node multi-GPU training with no impact on model quality.
ML-LOO: Detecting Adversarial Examples with Feature Attribution
Venue: arXiv cs.LG 2019
Year: 2019

Deep neural networks obtain state-of-the-art performance on a series of tasks. However, they are easily fooled by adding a small adversarial perturbation to input. The perturbation is often human imperceptible on image data. We observe a significant difference in feature attributions of adversarially crafted examples from those of original ones. Based on this observation, we introduce a new framework to detect adversarial examples through thresholding a scale estimate of feature attribution scores. Furthermore, we extend our method to include multi-layer feature attributions in order to tackle the attacks with mixed confidence levels. Through vast experiments, our method achieves superior performances in distinguishing adversarial examples from popular attack methods on a variety of real data sets among state-of-the-art detection methods. In particular, our method is able to detect adversarial examples of mixed confidence levels, and transfer between different attacking methods.