OpenRaiser/Intern-Atlas huggingface dataset:
Data structures to represent a set of k-long DNA sequences
Venue: arXiv cs.DS 2020
Year: 2020

The analysis of biological sequencing data has been one of the biggest applications of string algorithms. The approaches used in many such applications are based on the analysis of k-mers, which are short fixed-length strings present in a dataset. While these approaches are rather diverse, storing and querying a k-mer set has emerged as a shared underlying component. A set of k-mers has unique features and applications that, over the last ten years, have resulted in many specialized approaches for its representation. In this survey, we give a unified presentation and comparison of the data structures that have been proposed to store and query a k-mer set. We hope this survey will serve as a resource for researchers in the field as well as make the area more accessible to researchers outside the field.
IoT-Fog: A Communication Framework using Blockchain in the Internet of Things
Venue: arXiv cs.NI 2020
Year: 2020

In big cloud structures or large data structures, fog computing could be interpreted, referring critically to the growing issues and problems in accessing the information among the Internet of things (IoT) devices. Fog computing can be used to compute, store, control and connect smart devices to each other. IoT is an architecture of uniquely identified interrelated physical things, these physical things are able to communicate with each other and can transmit and receive information. This research presents a framework of the combination of the Internet of Things (IoT) and Fog computing. The blockchain is also the emerging technology that provides a hyper, distributed, public, authentic ledger to record the transactions. Blockchains technology is a secure technology that can be a great benefit to the next generation computing. The confluence of fog, blockchains, and IoT in this area introduces a new incentive. In this research work, the author mentions the convergence of blockchain, fog and IoT technological innovations to present an effective communication framework. The framework is implemented and tested using different scenarios.
How to Authenticate MQTT Sessions Without Channel- and Broker Security
Venue: arXiv cs.NI 2020
Year: 2020

This paper describes a new but state-of-the-art approach to provide authenticity in mqtt sessions using the means of zero-knowledge-proofs. This approach completely voids session hijacking for the mqtt protocol and provides authenticity without the need for any network-security nor channel-security nor broker-based predefined ACLs. The presented approach does not require the broker to keep any secrets for session handling, what so ever. Moreover, it allows the clientID, which represents the identification for a session, to be publicly known. The presented approach allows completely anonymous but authentic sessions, hence the broker does not need any a priori knowledge of the client-party. As it is especially targeted for applications within the world of IoT, the presented approach is tuned to require only the minimum in extra power in terms of energy and space. The approach does not introduce any new concept, but simply fusions a state-of-the-art cryptographic zero knowledge proof of identity with the existing MQTT-5 specification. Thus no protocol extension is required in order to provide the targeted security properties. The described approach is completely agnostic to the application layer at the client side and is only required during mqtt-session establishment.
Robust Low-Rank Tensor Ring Completion
Venue: arXiv cs.LG 2020
Year: 2020

Low-rank tensor completion recovers missing entries based on different tensor decompositions. Due to its outstanding performance in exploiting some higher-order data structure, low rank tensor ring has been applied in tensor completion. To further deal with its sensitivity to sparse component as it does in tensor principle component analysis, we propose robust tensor ring completion (RTRC), which separates latent low-rank tensor component from sparse component with limited number of measurements. The low rank tensor component is constrained by the weighted sum of nuclear norms of its balanced unfoldings, while the sparse component is regularized by its l1 norm. We analyze the RTRC model and gives the exact recovery guarantee. The alternating direction method of multipliers is used to divide the problem into several sub-problems with fast solutions. In numerical experiments, we verify the recovery condition of the proposed method on synthetic data, and show the proposed method outperforms the state-of-the-art ones in terms of both accuracy and computational complexity in a number of real-world data based tasks, i.e., light-field image recovery, shadow removal in face images, and background extraction in color video.
Implementation of Fruits Recognition Classifier using Convolutional Neural Network Algorithm for Observation of Accuracies for Various Hidden Layers
Venue: arXiv cs.CV 2020
Year: 2020

Fruit recognition using Deep Convolutional Neural Network (CNN) is one of the most promising applications in computer vision. In recent times, deep learning based classifications are making it possible to recognize fruits from images. However, fruit recognition is still a problem for the stacked fruits on weighing scale because of the complexity and similarity. In this paper, a fruit recognition system using CNN is proposed. The proposed method uses deep learning techniques for the classification. We have used Fruits-360 dataset for the evaluation purpose. From the dataset, we have established a dataset which contains 17,823 images from 25 different categories. The images are divided into training and test dataset. Moreover, for the classification accuracies, we have used various combinations of hidden layer and epochs for different cases and made a comparison between them. The overall performance losses of the network for different cases also observed. Finally, we have achieved the best test accuracy of 100% and a training accuracy of 99.79%.
Liveness in Broadcast Networks
Venue: arXiv cs.FL 2020
Year: 2020

We study liveness and model checking problems for broadcast networks, a system model of identical clients communicating via message passing. The first problem that we consider is Liveness Verification. It asks whether there is a computation such that one of the clients visits a final state infinitely often. The complexity of the problem has been open since 2010 when it was shown to be P-hard and solvable in EXPSPACE. We close the gap by a polynomial-time algorithm. The algorithm relies on a characterization of live computations in terms of paths in a suitable graph, combined with a fixed-point iteration to efficiently check the existence of such paths. The second problem is Fair Liveness Verification. It asks for a computation where all participating clients visit a final state infinitely often. We adjust the algorithm to also solve fair liveness in polynomial time. Both problems can be instrumented to answer model checking questions for broadcast networks against linear time temporal logic specifications. The first problem in this context is Fair Model Checking. It demands that for all computations of a broadcast network, all participating clients satisfy the specification. We solve the problem via the Vardi-Wolper construction and a reduction to Liveness Verification. The second problem is Sparse Model Checking. It asks whether each computation has a participating client that satisfies the specification. We reduce the problem to Fair Liveness Verification.
Distributed Ledger Technology for IoT: Parasite Chain Attacks
Venue: arXiv cs.DC 2020
Year: 2020

Directed Acyclic Graph (DAG) based Distributed Ledgers can be useful in a number of applications in the IoT domain. A distributed ledger should serve as an immutable and irreversible record of transactions, however, a DAG structure is a more complicated mathematical object than its blockchain counterparts, and as a result, providing guarantees of immutability and irreversibility is more involved. In this paper, we analyse a commonly discussed attack scenario known as a parasite chain attack for the IOTA Foundation DAG based ledger. We analyse the efficacy of IOTA core MCMC algorithm using a matrix model and present an extension which improves the ledger resistance to these attacks.
Multitask Soft Option Learning
Venue: arXiv cs.LG 2020
Year: 2020

We present Multitask Soft Option Learning(MSOL), a hierarchical multitask framework based on Planning as Inference. MSOL extends the concept of options, using separate variational posteriors for each task, regularized by a shared prior. This ''soft'' version of options avoids several instabilities during training in a multitask setting, and provides a natural way to learn both intra-option policies and their terminations. Furthermore, it allows fine-tuning of options for new tasks without forgetting their learned policies, leading to faster training without reducing the expressiveness of the hierarchical policy. We demonstrate empirically that MSOL significantly outperforms both hierarchical and flat transfer-learning baselines.
Surgical Gesture Recognition with Optical Flow only
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we address the open research problem of surgical gesture recognition using motion cues from video data only. We adapt Optical flow ConvNets initially proposed by Simonyan et al.. While Simonyan uses both RGB frames and dense optical flow, we use only dense optical flow representations as input to emphasize the role of motion in surgical gesture recognition, and present it as a robust alternative to kinematic data. We also overcome one of the limitations of Optical flow ConvNets by initializing our model with cross modality pre-training. A large number of promising studies that address surgical gesture recognition highly rely on kinematic data which requires additional recording devices. To our knowledge, this is the first paper that addresses surgical gesture recognition using dense optical flow information only. We achieve competitive results on JIGSAWS dataset, moreover, our model achieves more robust results with less standard deviation, which suggests optical flow information can be used as an alternative to kinematic data for the recognition of surgical gestures.
Source Camera Attribution of Multi-Format Devices
Venue: arXiv cs.MM 2020
Year: 2020

Photo Response Non-Uniformity (PRNU) based source camera attribution is an effective method to determine the origin camera of visual media (an image or a video). However, given that modern devices, especially smartphones, capture images, and videos at different resolutions using the same sensor array, PRNU attribution can become ineffective as the camera fingerprint and query visual media can be misaligned. We examine different resizing techniques such as binning, line-skipping, cropping and scaling that cameras use to downsize the raw sensor image to different media. Taking such techniques into account, this paper studies the problem of source camera attribution. We define the notion of Ratio of Alignment, which is a measure of shared sensor elements among spatially corresponding pixels within two media objects resized with different techniques. We then compute the Ratio of Alignment between the different combinations of three common resizing methods under simplified conditions and experimentally validate our analysis. Based on the insights drawn from the different techniques used by cameras and the RoA analysis, the paper proposes an algorithm for matching the source of a video with an image and vice versa. We also present an efficient search method resulting in significantly improved performance in matching as well as computation time.
Boolean analysis of lateral inhibition
Venue: arXiv cs.DM 2020
Year: 2020

We study Boolean networks which are simple spatial models of the highly conserved Delta-Notch system. The models assume the inhibition of Delta in each cell by Notch in the same cell, and the activation of Notch in presence of Delta in surrounding cells. We consider fully asynchronous dynamics over undirected graphs representing the neighbour relation between cells. In this framework, one can show that all attractors are fixed points for the system, independently of the neighbour relation, for instance by using known properties of simplified versions of the models, where only one species per cell is defined. The fixed points correspond to the so-called fine-grained "patterns" that emerge in discrete and continuous modelling of lateral inhibition. We study the reachability of fixed points, giving a characterisation of the trap spaces and the basins of attraction for both the full and the simplified models. In addition, we use a characterisation of the trap spaces to investigate the robustness of patterns to perturbations. The results of this qualitative analysis can complement and guide simulation-based approaches, and serve as a basis for the investigation of more complex mechanisms.
Towards Data-Driven Multilinear Metro Maps
Venue: arXiv cs.CG 2020
Year: 2020

Traditionally, most schematic metro maps in practice as well as metro map layout algorithms adhere to an octolinear layout style with all paths composed of horizontal, vertical, and 45°-diagonal edges. Despite growing interest in more general multilinear metro maps, generic algorithms to draw metro maps based on a system of $k \ge 2$ not necessarily equidistant slopes have not been investigated thoroughly. In this paper we present and implement an adaptation of the octolinear mixed-integer linear programming approach of Nöllenburg and Wolff (2011) that can draw metro maps schematized to any set C of arbitrary orientations. We further present a data-driven approach to determine a suitable set C by either detecting the best rotation of an equidistant orientation system or by clustering the input edge orientations using a k-means algorithm. We demonstrate the new possibilities of our method using several real-world examples.
Average Sensitivity of Graph Algorithms
Venue: arXiv cs.DS 2020
Year: 2020

In modern applications of graphs algorithms, where the graphs of interest are large and dynamic, it is unrealistic to assume that an input representation contains the full information of a graph being studied. Hence, it is desirable to use algorithms that, even when only a (large) subgraph is available, output solutions that are close to the solutions output when the whole graph is available. We formalize this idea by introducing the notion of average sensitivity of graph algorithms, which is the average earth mover's distance between the output distributions of an algorithm on a graph and its subgraph obtained by removing an edge, where the average is over the edges removed and the distance between two outputs is the Hamming distance. In this work, we initiate a systematic study of average sensitivity. After deriving basic properties of average sensitivity such as composition, we provide efficient approximation algorithms with low average sensitivities for concrete graph problems, including the minimum spanning forest problem, the global minimum cut problem, the minimum $s$-$t$ cut problem, and the maximum matching problem. In addition, we prove that the average sensitivity of our global minimum cut algorithm is almost optimal, by showing a nearly matching lower bound. We also show that every algorithm for the 2-coloring problem has average sensitivity linear in the number of vertices. One of the main ideas involved in designing our algorithms with low average sensitivity is the following fact; if the presence of a vertex or an edge in the solution output by an algorithm can be decided locally, then the algorithm has a low average sensitivity, allowing us to reuse the analyses of known sublinear-time algorithms and local computation algorithms (LCAs). Using this connection, we show that every LCA for 2-coloring has linear query complexity, thereby answering an open question.
Attention Distillation for Learning Video Representations
Venue: arXiv cs.CV 2020
Year: 2020

We address the challenging problem of learning motion representations using deep models for video recognition. To this end, we make use of attention modules that learn to highlight regions in the video and aggregate features for recognition. Specifically, we propose to leverage output attention maps as a vehicle to transfer the learned representation from a motion (flow) network to an RGB network. We systematically study the design of attention modules, and develop a novel method for attention distillation. Our method is evaluated on major action benchmarks, and consistently improves the performance of the baseline RGB network by a significant margin. Moreover, we demonstrate that our attention maps can leverage motion cues in learning to identify the location of actions in video frames. We believe our method provides a step towards learning motion-aware representations in deep models. Our project page is available at https://aptx4869lm.github.io/AttentionDistillation/
Evaluating Coherence in Dialogue Systems using Entailment
Venue: arXiv cs.CL 2020
Year: 2020

Evaluating open-domain dialogue systems is difficult due to the diversity of possible correct answers. Automatic metrics such as BLEU correlate weakly with human annotations, resulting in a significant bias across different models and datasets. Some researchers resort to human judgment experimentation for assessing response quality, which is expensive, time consuming, and not scalable. Moreover, judges tend to evaluate a small number of dialogues, meaning that minor differences in evaluation configuration may lead to dissimilar results. In this paper, we present interpretable metrics for evaluating topic coherence by making use of distributed sentence representations. Furthermore, we introduce calculable approximations of human judgment based on conversational coherence by adopting state-of-the-art entailment techniques. Results show that our metrics can be used as a surrogate for human judgment, making it easy to evaluate dialogue systems on large-scale datasets and allowing an unbiased estimate for the quality of the responses.
The categorical equivalence between disjunctive sequent calculi and algebraic L-domains
Venue: arXiv cs.LO 2020
Year: 2020

This paper establishes a purely syntactic representation for the category of algebraic L-domains with Scott-continuous functions as morphisms. The central tool used here is the notion of logical states, which builds a bridge between disjunctive sequent calculi and algebraic L-domains. To capture Scott-continuous functions between algebraic L-domains, the notion of consequence relations between disjunctive sequent calculi is also introduced. It is shown that the category of disjunctive sequent calculi with consequence relations as morphisms is categorical equivalent to that of algebraic L-domains with Scott-continuous functions as morphisms.
Towards Concurrent Stateful Stream Processing on Multicore Processors (Technical Report)
Venue: arXiv cs.DB 2020
Year: 2020

Recent data stream processing systems (DSPSs) can achieve excellent performance when processing large volumes of data under tight latency constraints. However, they sacrifice support for concurrent state access that eases the burden of developing stateful stream applications. Recently, some have proposed managing concurrent state access during stream processing by modeling state accesses as transactions. However, these are realized with locks involving serious contention overhead. Their coarse-grained processing paradigm further magnifies contention issues and tends to poorly utilize modern multicore architectures. This paper introduces TStream , a novel DSPS supporting efficient concurrent state access on multicore processors. Transactional semantics is employed like previous work, but scalability is greatly improved due to two novel designs: 1) dual-mode scheduling, which exposes more parallelism opportunities, 2) dynamic restructuring execution, which aggressively exploits the parallelism opportunities from dual-mode scheduling without centralized lock contentions. To validate our proposal, we evaluate TStream with a benchmark of four applications on a modern multicore machine. The experimental results show that 1) TStream achieves up to 4.8 times higher throughput with similar processing latency compared to the state-of-the-art and 2) unlike prior solutions, TStream is highly tolerant of varying application workloads such as key skewness and multi-partition state accesses.
Creating Pro-Level AI for a Real-Time Fighting Game Using Deep Reinforcement Learning
Venue: arXiv cs.AI 2020
Year: 2020

Reinforcement learning combined with deep neural networks has performed remarkably well in many genres of games recently. It has surpassed human-level performance in fixed game environments and turn-based two player board games. However, to the best of our knowledge, current research has yet to produce a result that has surpassed human-level performance in modern complex fighting games. This is due to the inherent difficulties with real-time fighting games, including: vast action spaces, action dependencies, and imperfect information. We overcame these challenges and made 1v1 battle AI agents for the commercial game "Blade & Soul". The trained agents competed against five professional gamers and achieved a win rate of 62%. This paper presents a practical reinforcement learning method that includes a novel self-play curriculum and data skipping techniques. Through the curriculum, three different styles of agents were created by reward shaping and were trained against each other. Additionally, this paper suggests data skipping techniques that could increase data efficiency and facilitate explorations in vast spaces. Since our method can be generally applied to all two-player competitive games with vast action spaces, we anticipate its application to game development including level design and automated balancing.
Factor Graph Attention
Venue: arXiv cs.CV 2020
Year: 2020

Dialog is an effective way to exchange information, but subtle details and nuances are extremely important. While significant progress has paved a path to address visual dialog with algorithms, details and nuances remain a challenge. Attention mechanisms have demonstrated compelling results to extract details in visual question answering and also provide a convincing framework for visual dialog due to their interpretability and effectiveness. However, the many data utilities that accompany visual dialog challenge existing attention techniques. We address this issue and develop a general attention mechanism for visual dialog which operates on any number of data utilities. To this end, we design a factor graph based attention mechanism which combines any number of utility representations. We illustrate the applicability of the proposed approach on the challenging and recently introduced VisDial datasets, outperforming recent state-of-the-art methods by 1.1% for VisDial0.9 and by 2% for VisDial1.0 on MRR. Our ensemble model improved the MRR score on VisDial1.0 by more than 6%.