OpenRaiser/Intern-Atlas huggingface dataset:
Distributed Nonblocking Commit Protocols for Many-Party Cross-Blockchain Transactions
Venue: arXiv cs.DB 2020
Year: 2020

The interoperability across multiple blockchains would play a critical role in future blockchain-based data management paradigm. Existing techniques either work only for two blockchains or requires a centralized component to govern the cross-blockchain transaction execution, neither of which would meet the scalability requirement. This paper proposes a new distributed commit protocol, namely \textit{cross-blockchain transaction} (CBT), for conducting transactions across an arbitrary number of blockchains without any centralized component. The key idea of CBT is to extend the two-phase commit protocol with a heartbeat mechanism to ensure the liveness of CBT without introducing additional nodes or blockchains. We have implemented CBT and compared it to the state-of-the-art protocols, demonstrating CBT's low overhead (3.6\% between two blockchains, less than $1\%$ among 32 or more blockchains) and high scalability (linear scalability on up to 64-blockchain transactions). In addition, we developed a graphic user interface for users to virtually monitor the status of the cross-blockchain transactions.
Undetectable Radios: Covert Communication under Spectral Mask Constraints
Venue: arXiv cs.IT 2020
Year: 2020

We consider the problem of covert communication over continuous-time additive white Gaussian noise (AWGN) channels under spectral mask constraints, wherein two legitimate parties attempt to communicate reliably in the presence of an eavesdropper that should be unable to estimate if communication takes place. The spectral mask constraint is imposed to restrict excessive radiation beyond the bandwidth of interest. We develop a communication scheme with theoretical reliability and covertness guarantees based on pulse amplitude modulation (PAM) with Binary Phase Shift Keying (BPSK) and root raised cosine (RRC) carrier pulses. Given a fixed transmission duration T and a spectral mask with bandwidth parameter W, we show that one can reliably and covertly transmit $O(\sqrt{WT})$ bits of information. We characterize the constant behind the $O$ and show that it is tight under some conditions.
Learning fine-grained search space pruning and heuristics for combinatorial optimization
Venue: arXiv cs.DS 2020
Year: 2020

Combinatorial optimization problems arise in a wide range of applications from diverse domains. Many of these problems are NP-hard and designing efficient heuristics for them requires considerable time and experimentation. On the other hand, the number of optimization problems in the industry continues to grow. In recent years, machine learning techniques have been explored to address this gap. We propose a framework for leveraging machine learning techniques to scale-up exact combinatorial optimization algorithms. In contrast to the existing approaches based on deep-learning, reinforcement learning and restricted Boltzmann machines that attempt to directly learn the output of the optimization problem from its input (with limited success), our framework learns the relatively simpler task of pruning the elements in order to reduce the size of the problem instances. In addition, our framework uses only interpretable learning models based on intuitive features and thus the learning process provides deeper insights into the optimization problem and the instance class, that can be used for designing better heuristics. For the classical maximum clique enumeration problem, we show that our framework can prune a large fraction of the input graph (around 99 % of nodes in case of sparse graphs) and still detect almost all of the maximum cliques. This results in several fold speedups of state-of-the-art algorithms. Furthermore, the model used in our framework highlights that the chi-squared value of neighborhood degree has a statistically significant correlation with the presence of a node in a maximum clique, particularly in dense graphs which constitute a significant challenge for modern solvers. We leverage this insight to design a novel heuristic for this problem outperforming the state-of-the-art. Our heuristic is also of independent interest for maximum clique detection and enumeration.
Adaptive Power and Rate Control for Real-time Status Updating over Fading Channels
Venue: arXiv cs.IT 2020
Year: 2020

Age of Information (AoI) has attracted much attention recently due to its capability of characterizing the freshness of information. To improve information freshness over fading channels, efficient scheduling methods are highly desired for wireless transmissions. However, due to the channel instability and arrival randomness, optimizing AoI is very challenging. In this paper, we are interested in the AoI-optimal transmissions with rate-adaptive transmission schemes in a buffer-aware system. More specifically, we utilize a probabilistic scheduling method to minimize the AoI while satisfying an average power constraint. By characterizing the probabilistic scheduling policy with a Constrained Markov Decision Process (CMDP), we formulate a Linear Programming (LP) problem. Further, a low complexity algorithm is presented to obtain the optimal scheduling policy, which is proved to belong to a set of semi-threshold-based policies. Numerical results verify the reduction in computational complexity and the optimality of semi-threshold-based policy, which indicates that we can achieve well real-time service with a low calculating complexity.
Evolutionary Approach to Collectible Card Game Arena Deckbuilding using Active Genes
Venue: arXiv cs.AI 2020
Year: 2020

In this paper, we evolve a card-choice strategy for the arena mode of Legends of Code and Magic, a programming game inspired by popular collectible card games like Hearthstone or TES: Legends. In the arena game mode, before each match, a player has to construct his deck choosing cards one by one from the previously unknown options. Such a scenario is difficult from the optimization point of view, as not only the fitness function is non-deterministic, but its value, even for a given problem instance, is impossible to be calculated directly and can only be estimated with simulation-based approaches. We propose a variant of the evolutionary algorithm that uses a concept of an active gene to reduce the range of the operators only to generation-specific subsequences of the genotype. Thus, we batched learning process and constrained evolutionary updates only to the cards relevant for the particular draft, without forgetting the knowledge from the previous tests. We developed and tested various implementations of this idea, investigating their performance by taking into account the computational cost of each variant. Performed experiments show that some of the introduced active-genes algorithms tend to learn faster and produce statistically better draft policies than the compared methods.
Deeper Insights into Weight Sharing in Neural Architecture Search
Venue: arXiv cs.LG 2020
Year: 2020

With the success of deep neural networks, Neural Architecture Search (NAS) as a way of automatic model design has attracted wide attention. As training every child model from scratch is very time-consuming, recent works leverage weight-sharing to speed up the model evaluation procedure. These approaches greatly reduce computation by maintaining a single copy of weights on the super-net and share the weights among every child model. However, weight-sharing has no theoretical guarantee and its impact has not been well studied before. In this paper, we conduct comprehensive experiments to reveal the impact of weight-sharing: (1) The best-performing models from different runs or even from consecutive epochs within the same run have significant variance; (2) Even with high variance, we can extract valuable information from training the super-net with shared weights; (3) The interference between child models is a main factor that induces high variance; (4) Properly reducing the degree of weight sharing could effectively reduce variance and improve performance.
Tight Localizations of Feedback Sets
Venue: arXiv cs.DM 2020
Year: 2020

The classical NP-hard feedback arc set problem (FASP) and feedback vertex set problem (FVSP) ask for a minimum set of arcs $\varepsilon \subseteq E$ or vertices $ν\subseteq V$ whose removal $G\setminus \varepsilon$, $G\setminus ν$ makes a given multi-digraph $G=(V,E)$ acyclic, respectively. Though both problems are known to be APX-hard, approximation algorithms or proofs of inapproximability are unknown. We propose a new $\mathcal{O}(|V||E|^4)$-heuristic for the directed FASP. While a ratio of $r \approx 1.3606$ is known to be a lower bound for the APX-hardness, at least by empirical validation we achieve an approximation of $r \leq 2$. The most relevant applications, such as circuit testing, ask for solving the FASP on large sparse graphs, which can be done efficiently within tight error bounds due to our approach.
Runtime Verification of Linux Kernel Security Module
Venue: arXiv cs.SE 2020
Year: 2020

The Linux kernel is one of the most important Free/Libre Open Source Software (FLOSS) projects. It is installed on billions of devices all over the world, which process various sensitive, confidential or simply private data. It is crucial to establish and prove its security properties. This work-in-progress paper presents a method to verify the Linux kernel for conformance with an abstract security policy model written in the Event-B specification language. The method is based on system call tracing and aims at checking that the results of system call execution do not lead to accesses that violate security policy requirements. As a basis for it, we use an additional Event-B specification of the Linux system call interface that is formally proved to satisfy all the requirements of the security policy model. In order to perform the conformance checks we use it to reproduce intercepted system calls and verify accesses.
Mid-Air Haptics in Aviation -- creating the sensation of touch where there is nothing but thin air
Venue: arXiv cs.HC 2020
Year: 2020

The exciting new technology known as mid-air haptics has been adopted by several industries including Automotive and Entertainment, however it has yet to emerge in simulated pilot training or in real-life flight decks. Full-flight simulators are expensive to manufacture, maintain and operate. Not only that, each simulator is limited to one aircraft type, which is inefficient for the majority of airlines that have several in service. With the growing trend in touchscreen instrumentation, cockpit displays require the pilot's attention to be drawn away from their view out of the window. But by using gesture recognition interfaces combined with mid-air haptic feedback, we can mitigate this shortcoming while also adding another dimension to the existing technology for pilots already familiar with using legacy cockpits, complete with traditional instrumentation. Meanwhile, simulation environments using augmented and virtual reality technology offers quality immersive training to the extent that pilots can go from hundreds of hours of simulated training to being responsible for hundreds of lives on their very first flight. The software re-programmability and dynamic richness afforded by mid-air haptic technologies combined with a basic full-motion platform could allow for an interchange of instrumentation layouts thus enhancing simulation immersiveness and environments. Finally, by borrowing and exploring concepts within the automotive sector, this concept paper presents how flight deck design could evolve by adopting this technology. If pilot testimony suggests that they can adapt to virtual objects, can this replace physical controls?
Stochastic Rounding: Algorithms and Hardware Accelerator
Venue: arXiv cs.AR 2020
Year: 2020

Algorithms and a hardware accelerator for performing stochastic rounding (SR) are presented. The main goal is to augment the ARM M4F based multi-core processor SpiNNaker2 with a more flexible rounding functionality than is available in the ARM processor itself. The motivation of adding such an accelerator in hardware is based on our previous results showing improvements in numerical accuracy of ODE solvers in fixed-point arithmetic with SR, compared to standard round to nearest or bit truncation rounding modes. Furthermore, performing SR purely in software can be expensive, due to requirement of a pseudorandom number generator (PRNG), multiple masking and shifting instructions, and an addition operation. Also, saturation of the rounded values is included, since rounding is usually followed by saturation, which is especially important in fixed-point arithmetic due to a narrow dynamic range of representable values. The main intended use of the accelerator is to round fixed-point multiplier outputs, which are returned unrounded by the ARM processor in a wider fixed-point format than the arguments.
Information Extraction based on Named Entity for Tourism Corpus
Venue: arXiv cs.CL 2020
Year: 2020

Tourism information is scattered around nowadays. To search for the information, it is usually time consuming to browse through the results from search engine, select and view the details of each accommodation. In this paper, we present a methodology to extract particular information from full text returned from the search engine to facilitate the users. Then, the users can specifically look to the desired relevant information. The approach can be used for the same task in other domains. The main steps are 1) building training data and 2) building recognition model. First, the tourism data is gathered and the vocabularies are built. The raw corpus is used to train for creating vocabulary embedding. Also, it is used for creating annotated data. The process of creating named entity annotation is presented. Then, the recognition model of a given entity type can be built. From the experiments, given hotel description, the model can extract the desired entity,i.e, name, location, facility. The extracted data can further be stored as a structured information, e.g., in the ontology format, for future querying and inference. The model for automatic named entity identification, based on machine learning, yields the error ranging 8%-25%.
Morphological Word Segmentation on Agglutinative Languages for Neural Machine Translation
Venue: arXiv cs.CL 2020
Year: 2020

Neural machine translation (NMT) has achieved impressive performance on machine translation task in recent years. However, in consideration of efficiency, a limited-size vocabulary that only contains the top-N highest frequency words are employed for model training, which leads to many rare and unknown words. It is rather difficult when translating from the low-resource and morphologically-rich agglutinative languages, which have complex morphology and large vocabulary. In this paper, we propose a morphological word segmentation method on the source-side for NMT that incorporates morphology knowledge to preserve the linguistic and semantic information in the word structure while reducing the vocabulary size at training time. It can be utilized as a preprocessing tool to segment the words in agglutinative languages for other natural language processing (NLP) tasks. Experimental results show that our morphologically motivated word segmentation method is better suitable for the NMT model, which achieves significant improvements on Turkish-English and Uyghur-Chinese machine translation tasks on account of reducing data sparseness and language complexity.
Why Molière most likely did write his plays
Venue: arXiv cs.CL 2020
Year: 2020

As for Shakespeare, a hard-fought debate has emerged about Molière, a supposedly uneducated actor who, according to some, could not have written the masterpieces attributed to him. In the past decades, the century-old thesis according to which Pierre Corneille would be their actual author has become popular, mostly because of new works in computational linguistics. These results are reassessed here through state-of-the-art attribution methods. We study a corpus of comedies in verse by major authors of Molière and Corneille's time. Analysis of lexicon, rhymes, word forms, affixes, morphosyntactic sequences, and function words do not give any clue that another author among the major playwrights of the time would have written the plays signed under the name Molière.
GeoBroker: Leveraging Geo-Contexts for IoT Data Distribution
Venue: arXiv cs.DC 2020
Year: 2020

In the Internet of Things, the relevance of data often depends on the geographic context of data producers and consumers. Today's data distribution services, however, mostly focus on data content and not on geo-context, which could help to reduce the dissemination of excess data in many IoT scenarios. In this paper, we propose to use the geo-context information associated with devices to control data distribution. We define what geo-context dimensions exist and compare our definition with concepts from related work. Furthermore, we designed GeoBroker, a data distribution service that uses the location of things, as well as geofences for messages and subscriptions, to control data distribution. This way, we enable new IoT application scenarios while also increasing overall system efficiency for scenarios where geo-contexts matter by delivering only relevant messages. We evaluate our approach based on a proof-of-concept prototype and several experiments.
The SmartSHARK Ecosystem for Software Repository Mining
Venue: arXiv cs.SE 2020
Year: 2020

Software repository mining is the foundation for many empirical software engineering studies. The collection and analysis of detailed data can be challenging, especially if data shall be shared to enable replicable research and open science practices. SmartSHARK is an ecosystem that supports replicable and reproducible research based on software repository mining.
Exploring Benefits of Transfer Learning in Neural Machine Translation
Venue: arXiv cs.CL 2020
Year: 2020

Neural machine translation is known to require large numbers of parallel training sentences, which generally prevent it from excelling on low-resource language pairs. This thesis explores the use of cross-lingual transfer learning on neural networks as a way of solving the problem with the lack of resources. We propose several transfer learning approaches to reuse a model pretrained on a high-resource language pair. We pay particular attention to the simplicity of the techniques. We study two scenarios: (a) when we reuse the high-resource model without any prior modifications to its training process and (b) when we can prepare the first-stage high-resource model for transfer learning in advance. For the former scenario, we present a proof-of-concept method by reusing a model trained by other researchers. In the latter scenario, we present a method which reaches even larger improvements in translation performance. Apart from proposed techniques, we focus on an in-depth analysis of transfer learning techniques and try to shed some light on transfer learning improvements. We show how our techniques address specific problems of low-resource languages and are suitable even in high-resource transfer learning. We evaluate the potential drawbacks and behavior by studying transfer learning in various situations, for example, under artificially damaged training corpora, or with fixed various model parts.
A Hybrid Approach to Temporal Pattern Matching
Venue: arXiv cs.DS 2020
Year: 2020

The primary objective of graph pattern matching is to find all appearances of an input graph pattern query in a large data graph. Such appearances are called matches. In this paper, we are interested in finding matches of interaction patterns in temporal graphs. To this end, we propose a hybrid approach that achieves effective filtering of potential matches based both on structure and time. Our approach exploits a graph representation where edges are ordered by time. We present experiments with real datasets that illustrate the efficiency of our approach.
Setting the Yardstick: A Quantitative Metric for Effectively Measuring Tactile Internet
Venue: arXiv cs.NI 2020
Year: 2020

The next frontier in communications is teleoperation -- manipulation and control of remote environments. Compared to conventional networked applications, teleoperation poses widely different requirements, ultra-low latency (ULL) being the primary one. Teleoperation, along with a host of other applications requiring ULL communication, is termed as Tactile Internet (TI). A significant redesign of conventional networking techniques is necessary to realize TI applications. Further, these advancements can be evaluated only when meaningful performance metrics are available. However, existing TI performance metrics fall severely short of comprehensively characterizing TI performance. In this paper, we take the first step towards bridging this gap. To this end, we propose a method that captures the fine-grained performance of TI in terms of delay and precision. We take Dynamic Time Warping (DTW) as the basis of our work and identify whether it is sufficient in characterizing TI systems. We refine DTW by developing a framework called Effective Time- and Value-Offset (ETVO) that extracts fine-grained time and value offsets between input and output signals of TI. Using ETVO, we present two quantitative metrics for TI -- Effective Delay-Derivative (EDD) and Effective Root Mean Square Error. Through rigorous experiments conducted on a realistic TI setup, we demonstrate the potential of the proposed metrics to precisely characterize TI interactions.
Generalizing Emergent Communication
Venue: arXiv cs.AI 2020
Year: 2020

We converted the recently developed BabyAI grid world platform to a sender/receiver setup in order to test the hypothesis that established deep reinforcement learning techniques are sufficient to incentivize the emergence of a grounded discrete communication protocol between generalized agents. This is in contrast to previous experiments that employed straight-through estimation or specialized inductive biases. Our results show that these can indeed be avoided, by instead providing proper environmental incentives. Moreover, they show that a longer interval between communications incentivized more abstract semantics. In some cases, the communicating agents adapted to new environments more quickly than a monolithic agent, showcasing the potential of emergent communication for transfer learning and generalization in general.
Plug-and-Play Rescaling Based Crowd Counting in Static Images
Venue: arXiv cs.CV 2020
Year: 2020

Crowd counting is a challenging problem especially in the presence of huge crowd diversity across images and complex cluttered crowd-like background regions, where most previous approaches do not generalize well and consequently produce either huge crowd underestimation or overestimation. To address these challenges, we propose a new image patch rescaling module (PRM) and three independent PRM employed crowd counting methods. The proposed frameworks use the PRM module to rescale the image regions (patches) that require special treatment, whereas the classification process helps in recognizing and discarding any cluttered crowd-like background regions which may result in overestimation. Experiments on three standard benchmarks and cross-dataset evaluation show that our approach outperforms the state-of-the-art models in the RMSE evaluation metric with an improvement up to 10.4%, and possesses superior generalization ability to new datasets.