OpenRaiser/Intern-Atlas huggingface dataset:
Parallel String Graph Construction and Transitive Reduction for De Novo Genome Assembly
Venue: arXiv cs.DC 2020
Year: 2020

One of the most computationally intensive tasks in computational biology is de novo genome assembly, the decoding of the sequence of an unknown genome from redundant and erroneous short sequences. A common assembly paradigm identifies overlapping sequences, simplifies their layout, and creates consensus. Despite many algorithms developed in the literature, the efficient assembly of large genomes is still an open problem. In this work, we introduce new distributed-memory parallel algorithms for overlap detection and layout simplification steps of de novo genome assembly, and implement them in the diBELLA 2D pipeline. Our distributed memory algorithms for both overlap detection and layout simplification are based on linear-algebra operations over semirings using 2D distributed sparse matrices. Our layout step consists of performing a transitive reduction from the overlap graph to a string graph. We provide a detailed communication analysis of the main stages of our new algorithms. diBELLA 2D achieves near linear scaling with over 80% parallel efficiency for the human genome, reducing the runtime for overlap detection by 1.2-1.3x for the human genome and 1.5-1.9x for C. elegans compared to the state-of-the-art. Our transitive reduction algorithm outperforms an existing distributed-memory implementation by 10.5-13.3x for the human genome and 18-29x for the C. elegans. Our work paves the way for efficient de novo assembly of large genomes using long reads in distributed memory.
How Did That Get In My Phone? Unwanted App Distribution on Android Devices
Venue: arXiv cs.CR 2020
Year: 2020

Android is the most popular operating system with billions of active devices. Unfortunately, its popularity and openness makes it attractive for unwanted apps, i.e., malware and potentially unwanted programs (PUP). In Android, app installations typically happen via the official and alternative markets, but also via other smaller and less understood alternative distribution vectors such as Web downloads, pay-per-install (PPI) services, backup restoration, bloatware, and IM tools. This work performs a thorough investigation on unwanted app distribution by quantifying and comparing distribution through different vectors. At the core of our measurements are reputation logs of a large security vendor, which include 7.9M apps observed in 12M devices between June and September 2019. As a first step, we measure that between 10% and 24% of users devices encounter at least one unwanted app, and compare the prevalence of malware and PUP. An analysis of the who-installs-who relationships between installers and child apps reveals that the Play market is the main app distribution vector, responsible for 87% of all installs and 67% of unwanted app installs, but it also has the best defenses against unwanted apps. Alternative markets distribute instead 5.7% of all apps, but over 10% of unwanted apps. Bloatware is also a significant unwanted app distribution vector with 6% of those installs. And, backup restoration is an unintentional distribution vector that may even allow unwanted apps to survive users' phone replacement. We estimate unwanted app distribution via PPI to be smaller than on Windows. Finally, we observe that Web downloads are rare, but provide a riskier proposition even compared to alternative markets.
Constructing feature variation coefficients to evaluate feature learning capabilities of convolutional layers in steganographic detection algorithms of spatial domain
Venue: arXiv cs.CR 2020
Year: 2020

Traditional steganalysis methods generally include two steps: feature extraction and classification.A variety of steganalysis algorithms based on CNN (Convolutional Neural Network) have appeared in recent years. Among them, the convolutional layer of the CNN model is usually used to extract steganographic features, and the fully connected layer is used for classification. Because the effectiveness of feature extraction seriously influences the accuracy of classification, designers generally improve the accuracy of steganographic detection by improving the convolutional layer. For example, common optimizing methods in convolutional layer include the improvement of convolution kernel, activation functions, pooling functions, network structures, etc. However, due to the complexity and unexplainability of convolutional layers, it is difficult to quantitatively analyze and compare the effectiveness of feature extraction. Therefore, this paper proposes the variation coefficient to evaluate the feature learning ability of convolutional layers. We select four typical image steganalysis models based CNN in spatial domain, such as Ye-Net, Yedroudj-Net, Zhu-Net, and SR-Net as use cases, and verify the validity of the variation coefficient through experiments. Moreover, according to the variation coefficient , a features modification layer is used to optimize the features before the fully connected layer of the CNN model , and the experimental results show that the detection accuracy of the four algorithms were improved differently.
Keystroke Dynamics as Part of Lifelogging
Venue: arXiv cs.MM 2020
Year: 2020

In this paper we present the case for including keystroke dynamics in lifelogging. We describe how we have used a simple keystroke logging application called Loggerman, to create a dataset of longitudinal keystroke timing data spanning a period of more than 6 months for 4 participants. We perform a detailed analysis of this data by examining the timing information associated with bigrams or pairs of adjacently-typed alphabetic characters. We show how there is very little day-on-day variation of the keystroke timing among the top-200 bigrams for some participants and for others there is a lot and this correlates with the amount of typing each would do on a daily basis. We explore how daily variations could correlate with sleep score from the previous night but find no significant relation-ship between the two. Finally we describe the public release of this data as well including as a series of pointers for future work including correlating keystroke dynamics with mood and fatigue during the day.
Extracting Procedural Knowledge from Technical Documents
Venue: arXiv cs.AI 2020
Year: 2020

Procedures are an important knowledge component of documents that can be leveraged by cognitive assistants for automation, question-answering or driving a conversation. It is a challenging problem to parse big dense documents like product manuals, user guides to automatically understand which parts are talking about procedures and subsequently extract them. Most of the existing research has focused on extracting flows in given procedures or understanding the procedures in order to answer conceptual questions. Identifying and extracting multiple procedures automatically from documents of diverse formats remains a relatively less addressed problem. In this work, we cover some of this ground by -- 1) Providing insights on how structural and linguistic properties of documents can be grouped to define types of procedures, 2) Analyzing documents to extract the relevant linguistic and structural properties, and 3) Formulating procedure identification as a classification problem that leverages the features of the document derived from the above analysis. We first implemented and deployed unsupervised techniques which were used in different use cases. Based on the evaluation in different use cases, we figured out the weaknesses of the unsupervised approach. We then designed an improved version which was supervised. We demonstrate that our technique is effective in identifying procedures from big and complex documents alike by achieving accuracy of 89%.
Rate Adaptation and Latency in Heterogeneous IoT Networks
Venue: arXiv cs.IT 2020
Year: 2020

This paper studies the effect of rate adaptation in time slotted Internet of things (IoT) networks. For a given time slot duration and packets size, rate adaptation necessitates packet fragmentation to fit the time slot duration. Accounting for the quality and time resolution of the underlying traffic, this paper characterizes the tradeoff between transmission rate and packet latency in IoT networks. Using tools from stochastic geometry and queueing theory, a novel mathematical framework is developed for static and dynamic rate adaptation schemes. The results show that there is an optimal static rate that minimizes latency, which depends on the network parameters. Furthermore, the dynamic rate is shown to be resilient to different variations in the network parameters without sacrificing packet latency.
Complete Multilingual Neural Machine Translation
Venue: arXiv cs.CL 2020
Year: 2020

Multilingual Neural Machine Translation (MNMT) models are commonly trained on a joint set of bilingual corpora which is acutely English-centric (i.e. English either as the source or target language). While direct data between two languages that are non-English is explicitly available at times, its use is not common. In this paper, we first take a step back and look at the commonly used bilingual corpora (WMT), and resurface the existence and importance of implicit structure that existed in it: multi-way alignment across examples (the same sentence in more than two languages). We set out to study the use of multi-way aligned examples to enrich the original English-centric parallel corpora. We reintroduce this direct parallel data from multi-way aligned corpora between all source and target languages. By doing so, the English-centric graph expands into a complete graph, every language pair being connected. We call MNMT with such connectivity pattern complete Multilingual Neural Machine Translation (cMNMT) and demonstrate its utility and efficacy with a series of experiments and analysis. In combination with a novel training data sampling strategy that is conditioned on the target language only, cMNMT yields competitive translation quality for all language pairs. We further study the size effect of multi-way aligned data, its transfer learning capabilities and how it eases adding a new language in MNMT. Finally, we stress test cMNMT at scale and demonstrate that we can train a cMNMT model with up to 111*112=12,432 language pairs that provides competitive translation quality for all language pairs.
Scalable Shared-Memory Hypergraph Partitioning
Venue: arXiv cs.DC 2020
Year: 2020

Hypergraph partitioning is an important preprocessing step for optimizing data placement and minimizing communication volumes in high-performance computing applications. To cope with ever growing problem sizes, it has become increasingly important to develop fast parallel partitioning algorithms whose solution quality is competitive with existing sequential algorithms. To this end, we present Mt-KaHyPar, the first shared-memory multilevel hypergraph partitioner with parallel implementations of many techniques used by the sequential, high-quality partitioning systems: a parallel coarsening algorithm that uses parallel community detection as guidance, initial partitioning via parallel recursive bipartitioning with work-stealing, a scalable label propagation refinement algorithm, and the first fully-parallel direct $k$-way formulation of the classical FM algorithm. Experiments performed on a large benchmark set of instances from various application domains demonstrate the scalability and effectiveness of our approach. With 64 cores, we observe self-relative speedups of up to 51 and a harmonic mean speedup of 23.5. In terms of solution quality, we outperform the distributed hypergraph partitioner Zoltan on 95% of the instances while also being a factor of 2.1 faster. With just four cores,Mt-KaHyPar is also slightly faster than the fastest sequential multilevel partitioner PaToH while producing better solutions on 83% of all instances. The sequential high-quality partitioner KaHyPar still finds better solutions than our parallel approach, especially when using max-flow-based refinement. This, however, comes at the cost of considerably longer running times.
User-Number Threshold-based Base Station On/Off Control for Maximizing Coverage Probability
Venue: arXiv cs.IT 2020
Year: 2020

In this study, we investigate the operation of user-number threshold-based base station (BS) on/off control, in which the BS turns off when the number of active users is less than a specific threshold value. This paper presents a space-based analysis of the BS on/off control system to which a stochastic geometric approach is applied. In particular, we derive the approximated closed-form expression of the coverage probability of a homogeneous network (HomNet) with the user-number threshold-based on/off control. Moreover, the optimal user-number threshold for maximizing the coverage probability is analytically derived. In addition to HomNet, we also derive the overall coverage probability and the optimal user-number thresholds for a heterogeneous network (HetNet). The results show that HetNet, the analysis of which seems intractable, can be analyzed in the form of a linear combination of HomNets with weighted densities. In addition, the optimal user-number threshold of each tier is obtained independently of other tiers. The modeling and analysis presented in this paper are not only limited to the case of user-number threshold-based on/off control, but also applicable to other novel on/off controls with minor modifications. Finally, by comparing with the simulated results, the theoretical contributions of this study are validated.
A Benchmark for Lease Contract Review
Venue: arXiv cs.IR 2020
Year: 2020

Extracting entities and other useful information from legal contracts is an important task whose automation can help legal professionals perform contract reviews more efficiently and reduce relevant risks. In this paper, we tackle the problem of detecting two different types of elements that play an important role in a contract review, namely entities and red flags. The latter are terms or sentences that indicate that there is some danger or other potentially problematic situation for one or more of the signing parties. We focus on supporting the review of lease agreements, a contract type that has received little attention in the legal information extraction literature, and we define the types of entities and red flags needed for that task. We release a new benchmark dataset of 179 lease agreement documents that we have manually annotated with the entities and red flags they contain, and which can be used to train and test relevant extraction algorithms. Finally, we release a new language model, called ALeaseBERT, pre-trained on this dataset and fine-tuned for the detection of the aforementioned elements, providing a baseline for further research
CharacterBERT: Reconciling ELMo and BERT for Word-Level Open-Vocabulary Representations From Characters
Venue: arXiv cs.CL 2020
Year: 2020

Due to the compelling improvements brought by BERT, many recent representation models adopted the Transformer architecture as their main building block, consequently inheriting the wordpiece tokenization system despite it not being intrinsically linked to the notion of Transformers. While this system is thought to achieve a good balance between the flexibility of characters and the efficiency of full words, using predefined wordpiece vocabularies from the general domain is not always suitable, especially when building models for specialized domains (e.g., the medical domain). Moreover, adopting a wordpiece tokenization shifts the focus from the word level to the subword level, making the models conceptually more complex and arguably less convenient in practice. For these reasons, we propose CharacterBERT, a new variant of BERT that drops the wordpiece system altogether and uses a Character-CNN module instead to represent entire words by consulting their characters. We show that this new model improves the performance of BERT on a variety of medical domain tasks while at the same time producing robust, word-level and open-vocabulary representations.
Variational Dynamic Mixtures
Venue: arXiv cs.LG 2020
Year: 2020

Deep probabilistic time series forecasting models have become an integral part of machine learning. While several powerful generative models have been proposed, we provide evidence that their associated inference models are oftentimes too limited and cause the generative model to predict mode-averaged dynamics. Modeaveraging is problematic since many real-world sequences are highly multi-modal, and their averaged dynamics are unphysical (e.g., predicted taxi trajectories might run through buildings on the street map). To better capture multi-modality, we develop variational dynamic mixtures (VDM): a new variational family to infer sequential latent variables. The VDM approximate posterior at each time step is a mixture density network, whose parameters come from propagating multiple samples through a recurrent architecture. This results in an expressive multi-modal posterior approximation. In an empirical study, we show that VDM outperforms competing approaches on highly multi-modal datasets from different domains.
Where Is the Normative Proof? Assumptions and Contradictions in ML Fairness Research
Venue: arXiv cs.CY 2020
Year: 2020

Across machine learning (ML) sub-disciplines researchers make mathematical assumptions to facilitate proof-writing. While such assumptions are necessary for providing mathematical guarantees for how algorithms behave, they also necessarily limit the applicability of these algorithms to different problem settings. This practice is known--in fact, obvious--and accepted in ML research. However, similar attention is not paid to the normative assumptions that ground this work. I argue such assumptions are equally as important, especially in areas of ML with clear social impact, such as fairness. This is because, similar to how mathematical assumptions constrain applicability, normative assumptions also limit algorithm applicability to certain problem domains. I show that, in existing papers published in top venues, once normative assumptions are clarified, it is often possible to get unclear or contradictory results. While the mathematical assumptions and results are sound, the implicit normative assumptions and accompanying normative results contraindicate using these methods in practical fairness applications.
Towards Scalable Distributed Training of Deep Learning on Public Cloud Clusters
Venue: arXiv cs.DC 2020
Year: 2020

Distributed training techniques have been widely deployed in large-scale deep neural networks (DNNs) training on dense-GPU clusters. However, on public cloud clusters, due to the moderate inter-connection bandwidth between instances, traditional state-of-the-art distributed training systems cannot scale well in training large-scale models. In this paper, we propose a new computing and communication efficient top-k sparsification communication library for distributed training. To further improve the system scalability, we optimize I/O by proposing a simple yet efficient multi-level data caching mechanism and optimize the update operation by introducing a novel parallel tensor operator. Experimental results on a 16-node Tencent Cloud cluster (each node with 8 Nvidia Tesla V100 GPUs) show that our system achieves 25%-40% faster than existing state-of-the-art systems on CNNs and Transformer. We finally break the record on DAWNBench on training ResNet-50 to 93% top-5 accuracy on ImageNet.
Comparison of Interactive Knowledge Base Spelling Correction Models for Low-Resource Languages
Venue: arXiv cs.CL 2020
Year: 2020

Spelling normalization for low resource languages is a challenging task because the patterns are hard to predict and large corpora are usually required to collect enough examples. This work shows a comparison of a neural model and character language models with varying amounts on target language data. Our usage scenario is interactive correction with nearly zero amounts of training examples, improving models as more data is collected, for example within a chat app. Such models are designed to be incrementally improved as feedback is given from users. In this work, we design a knowledge-base and prediction model embedded system for spelling correction in low-resource languages. Experimental results on multiple languages show that the model could become effective with a small amount of data. We perform experiments on both natural and synthetic data, as well as on data from two endangered languages (Ainu and Griko). Last, we built a prototype system that was used for a small case study on Hinglish, which further demonstrated the suitability of our approach in real world scenarios.
Speaker Separation Using Speaker Inventories and Estimated Speech
Venue: arXiv cs.SD 2020
Year: 2020

We propose speaker separation using speaker inventories and estimated speech (SSUSIES), a framework leveraging speaker profiles and estimated speech for speaker separation. SSUSIES contains two methods, speaker separation using speaker inventories (SSUSI) and speaker separation using estimated speech (SSUES). SSUSI performs speaker separation with the help of speaker inventory. By combining the advantages of permutation invariant training (PIT) and speech extraction, SSUSI significantly outperforms conventional approaches. SSUES is a widely applicable technique that can substantially improve speaker separation performance using the output of first-pass separation. We evaluate the models on both speaker separation and speech recognition metrics.
Image-Driven Furniture Style for Interactive 3D Scene Modeling
Venue: arXiv cs.CV 2020
Year: 2020

Creating realistic styled spaces is a complex task, which involves design know-how for what furniture pieces go well together. Interior style follows abstract rules involving color, geometry and other visual elements. Following such rules, users manually select similar-style items from large repositories of 3D furniture models, a process which is both laborious and time-consuming. We propose a method for fast-tracking style-similarity tasks, by learning a furniture's style-compatibility from interior scene images. Such images contain more style information than images depicting single furniture. To understand style, we train a deep learning network on a classification task. Based on image embeddings extracted from our network, we measure stylistic compatibility of furniture. We demonstrate our method with several 3D model style-compatibility results, and with an interactive system for modeling style-consistent scenes.