OpenRaiser/Intern-Atlas huggingface dataset:
Preconditioning for the Geometric Transportation Problem
Venue: arXiv cs.DS 2019
Year: 2019

In the geometric transportation problem, we are given a collection of points $P$ in $d$-dimensional Euclidean space, and each point is given a supply of $μ(p)$ units of mass, where $μ(p)$ could be a positive or a negative integer, and the total sum of the supplies is $0$. The goal is to find a flow (called a transportation map) that transports $μ(p)$ units from any point $p$ with $μ(p) > 0$, and transports $-μ(p)$ units into any point $p$ with $μ(p) < 0$. Moreover, the flow should minimize the total distance traveled by the transported mass. The optimal value is known as the transportation cost, or the Earth Mover's Distance (from the points with positive supply to those with negative supply). This problem has been widely studied in many fields of computer science: from theoretical work in computational geometry, to applications in computer vision, graphics, and machine learning. In this work we study approximation algorithms for the geometric transportation problem. We give an algorithm which, for any fixed dimension $d$, finds a $(1+\varepsilon)$-approximate transportation map in time nearly-linear in $n$, and polynomial in $\varepsilon^{-1}$ and in the logarithm of the total supply. This is the first approximation scheme for the problem whose running time depends on $n$ as $n\cdot \mathrm{polylog}(n)$. Our techniques combine the generalized preconditioning framework of Sherman, which is grounded in continuous optimization, with simple geometric arguments to first reduce the problem to a minimum cost flow problem on a sparse graph, and then to design a good preconditioner for this latter problem.
Learning to Flip Successive Cancellation Decoding of Polar Codes with LSTM Networks
Venue: arXiv cs.IT 2019
Year: 2019

The key to successive cancellation (SC) flip decoding of polar codes is to accurately identify the first error bit. The optimal flipping strategy is considered difficult due to lack of an analytical solution. Alternatively, we propose a deep learning aided SC flip algorithm. Specifically, before each SC decoding attempt, a long short-term memory (LSTM) network is exploited to either (i) locate the first error bit, or (ii) undo a previous `wrong' flip. In each SC attempt, the sequence of log likelihood ratios (LLRs) derived in the previous SC attempt is exploited to decide which action to take. Accordingly, a two-stage training method of the LSTM network is proposed, i.e., learn to locate first error bits in the first stage, and then to undo `wrong' flips in the second stage. Simulation results show that the proposed approach identifies error bits more accurately and achieves better performance than the state-of-the-art SC flip algorithms.
Reducing Total Correctness to Partial Correctness by a Transformation of the Language Semantics
Venue: arXiv cs.LO 2019
Year: 2019

We give a language-parametric solution to the problem of total correctness, by automatically reducing it to the problem of partial correctness, under the assumption that an expression whose value decreases with each program step in a well-founded order is provided. Our approach assumes that the programming language semantics is given as a rewrite theory. We implement a prototype on top of the RMT tool and we show that it works in practice on a number of examples.
Using 2.4 GHz Wireless Botnets to Implement Denial-of-Service Attacks
Venue: arXiv cs.CR 2019
Year: 2019

This article attempts to create a software and hardware complex that can work autonomously and demonstrates the ease of implementation of attacks on denial of service on wireless networks, which in turn emphasizes the need to provide comprehensive protection of wireless networks.
Online Anomaly Detection in HPC Systems
Venue: arXiv cs.DC 2019
Year: 2019

Reliability is a cumbersome problem in High Performance Computing Systems and Data Centers evolution. During operation, several types of fault conditions or anomalies can arise, ranging from malfunctioning hardware to improper configurations or imperfect software. Currently, system administrator and final users have to discover it manually. Clearly this approach does not scale to large scale supercomputers and facilities: automated methods to detect faults and unhealthy conditions is needed. Our method uses a type of neural network called autoncoder trained to learn the normal behavior of a real, in-production HPC system and it is deployed on the edge of each computing node. We obtain a very good accuracy (values ranging between 90% and 95%) and we also demonstrate that the approach can be deployed on the supercomputer nodes without negatively affecting the computing units performance.
Web Links Prediction And Category-Wise Recommendation Based On Browser History
Venue: arXiv cs.IR 2019
Year: 2019

A web browser should not be only for browsing web pages but also help users to find out their target websites and recommend similar type websites based on their behavior. Throughout this paper, we propose two methods to make a web browser more intelligent about link prediction which works during typing on address-bar and recommendation of websites according to several categories. Our proposed link prediction system is actually frecency prediction which is predicted based on the first visit, last visit and URL counts. But recommend system is the most challenging as it is needed to classify web URLs according to names without visiting web pages. So we use existing model for URL classification. The only existing approach gives unsatisfactory results and low accuracy. So we add hyperparameter optimization with an existing approach that finds the best parameters for existing URL classification model and gives better accuracy. In this paper, we propose a category wise recommendation system using frecency value and the total visit of individual URL category.
Fast and Exact Nearest Neighbor Search in Hamming Space on Full-Text Search Engines
Venue: arXiv cs.IR 2019
Year: 2019

A growing interest has been witnessed recently from both academia and industry in building nearest neighbor search (NNS) solutions on top of full-text search engines. Compared with other NNS systems, such solutions are capable of effectively reducing main memory consumption, coherently supporting multi-model search and being immediately ready for production deployment. In this paper, we continue the journey to explore specifically how to empower full-text search engines with fast and exact NNS in Hamming space (i.e., the set of binary codes). By revisiting three techniques (bit operation, subs-code filtering and data preprocessing with permutation) in information retrieval literature, we develop a novel engineering solution for full-text search engines to efficiently accomplish this special but important NNS task. In the experiment, we show that our proposed approach enables full-text search engines to achieve significant speed-ups over its state-of-the-art term match approach for NNS within binary codes.
Centrality in Time-Delay Consensus Networks with Structured Uncertainties
Venue: arXiv cs.SY 2019
Year: 2019

We investigate notions of network centrality in terms of the underlying coupling graph of the network, structure of exogenous uncertainties, and communication time-delay. Our focus is on time-delay linear consensus networks, where uncertainty is modeled by structured additive noise on the dynamics of agents. The centrality measures are defined using the $\mathcal H_2$-norm of the network. We quantify the centrality measures as functions of time-delay, the graph Laplacian, and the covariance matrix of the input noise. Several practically relevant uncertainty structures are considered, where we discuss two notions of centrality: one w.r.t intensity of the noise and the other one w.r.t coupling strength between the agents. Furthermore, explicit formulas for the centrality measures are obtained for all types of uncertainty structures. Lastly, we rank agents and communication links based on their centrality indices and highlight the role of time-delay and uncertainty structure in each scenario. Our counter intuitive grasp is that some of centrality measures are highly volatile with respect to time-delay.
Event Detection in Twitter Stream using Weighted Dynamic Heartbeat Graph Approach
Venue: arXiv cs.SI 2019
Year: 2019

Tweets about everyday events are published on Twitter. Detecting such events is a challenging task due to the diverse and noisy contents of Twitter. In this paper, we propose a novel approach named Weighted Dynamic Heartbeat Graph (WDHG) to detect events from the Twitter stream. Once an event is detected in a Twitter stream, WDHG suppresses it in later stages, in order to detect new emerging events. This unique characteristic makes the proposed approach sensitive to capture emerging events efficiently. Experiments are performed on three real-life benchmark datasets: FA Cup Final 2012, Super Tuesday 2012, and the US Elections 2012. Results show considerable improvement over existing event detection methods in most cases.
A Graph-Based Machine Learning Approach for Bot Detection
Venue: arXiv cs.CR 2019
Year: 2019

Bot detection using machine learning (ML), with network flow-level features, has been extensively studied in the literature. However, existing flow-based approaches typically incur a high computational overhead and do not completely capture the network communication patterns, which can expose additional aspects of malicious hosts. Recently, bot detection systems which leverage communication graph analysis using ML have gained attention to overcome these limitations. A graph-based approach is rather intuitive, as graphs are true representations of network communications. In this paper, we propose a two-phased, graph-based bot detection system which leverages both unsupervised and supervised ML. The first phase prunes presumable benign hosts, while the second phase achieves bot detection with high precision. Our system detects multiple types of bots and is robust to zero-day attacks. It also accommodates different network topologies and is suitable for large-scale data.
Capacity allocation through neural network layers
Venue: arXiv cs.LG 2019
Year: 2019

Capacity analysis has been recently introduced as a way to analyze how linear models distribute their modelling capacity across the input space. In this paper, we extend the notion of capacity allocation to the case of neural networks with non-linear layers. We show that under some hypotheses the problem is equivalent to linear capacity allocation, within some extended input space that factors in the non-linearities. We introduce the notion of layer decoupling, which quantifies the degree to which a non-linear activation decouples its outputs, and show that it plays a central role in capacity allocation through layers. In the highly non-linear limit where decoupling is total, we show that the propagation of capacity throughout the layers follows a simple markovian rule, which turns into a diffusion PDE in the limit of deep networks with residual layers. This allows us to recover some known results about deep neural networks, such as the size of the effective receptive field, or why ResNets avoid the shattering problem.
Internet of Things Security Problems
Venue: arXiv cs.CR 2019
Year: 2019

The rapid development of "smart" devices leads to explosive growth of unprotected or partially protected home networks. These networks are easy prey for unauthorized access, the collection of personal information (including from surveillance cameras), interference in the operation of individual devices and the entire system as a whole. In addition, existing solutions for managing a smart house offer work in the cloud, which in turn reduces the availability of the system and simultaneously increases the risk of the unscrupulous use of personal information by the service provider (up to the sale of data to a third party). This article examines the existing access technologies, their weaknesses, and offers solutions to improve the overall security of the system with a local IoT gateway and virtual subnets.
Hybrid-Vehfog: A Robust Approach for Reliable Dissemination of Critical Messages in Connected Vehicles
Venue: arXiv cs.NI 2019
Year: 2019

Vehicular Ad-hoc Networks (VANET) enable efficient communication between vehicles with the aim of improving road safety. However, the growing number of vehicles in dense regions and obstacle shadowing regions like Manhattan and other downtown areas leads to frequent disconnection problems resulting in disrupted radio wave propagation between vehicles. To address this issue and to transmit critical messages between vehicles and drones deployed from service vehicles to overcome road incidents and obstacles, we proposed a hybrid technique based on fog computing called Hybrid-Vehfog to disseminate messages in obstacle shadowing regions, and multi-hop technique to disseminate messages in non-obstacle shadowing regions. Our proposed algorithm dynamically adapts to changes in an environment and benefits in efficiency with robust drone deployment capability as needed. Performance of Hybrid-Vehfog is carried out in Network Simulator (NS-2) and Simulation of Urban Mobility (SUMO) simulators. The results showed that Hybrid-Vehfog outperformed Cloud-assisted Message Downlink Dissemination Scheme (CMDS), Cross-Layer Broadcast Protocol (CLBP), PEer-to-Peer protocol for Allocated REsource (PrEPARE), Fog-Named Data Networking (NDN) with mobility, and flooding schemes at all vehicle densities and simulation times.
MPP: Model Performance Predictor
Venue: arXiv cs.LG 2019
Year: 2019

Operations is a key challenge in the domain of machine learning pipeline deployments involving monitoring and management of real-time prediction quality. Typically, metrics like accuracy, RMSE etc., are used to track the performance of models in deployment. However, these metrics cannot be calculated in production due to the absence of labels. We propose using an ML algorithm, Model Performance Predictor (MPP), to track the performance of the models in deployment. We argue that an ensemble of such metrics can be used to create a score representing the prediction quality in production. This in turn facilitates formulation and customization of ML alerts, that can be escalated by an operations team to the data science team. Such a score automates monitoring and enables ML deployments at scale.
Enhancing Clinical Concept Extraction with Contextual Embeddings
Venue: arXiv cs.CL 2019
Year: 2019

Neural network-based representations ("embeddings") have dramatically advanced natural language processing (NLP) tasks, including clinical NLP tasks such as concept extraction. Recently, however, more advanced embedding methods and representations (e.g., ELMo, BERT) have further pushed the state-of-the-art in NLP, yet there are no common best practices for how to integrate these representations into clinical tasks. The purpose of this study, then, is to explore the space of possible options in utilizing these new models for clinical concept extraction, including comparing these to traditional word embedding methods (word2vec, GloVe, fastText). Both off-the-shelf open-domain embeddings and pre-trained clinical embeddings from MIMIC-III are evaluated. We explore a battery of embedding methods consisting of traditional word embeddings and contextual embeddings, and compare these on four concept extraction corpora: i2b2 2010, i2b2 2012, SemEval 2014, and SemEval 2015. We also analyze the impact of the pre-training time of a large language model like ELMo or BERT on the extraction performance. Last, we present an intuitive way to understand the semantic information encoded by contextual embeddings. Contextual embeddings pre-trained on a large clinical corpus achieves new state-of-the-art performances across all concept extraction tasks. The best-performing model outperforms all state-of-the-art methods with respective F1-measures of 90.25, 93.18 (partial), 80.74, and 81.65. We demonstrate the potential of contextual embeddings through the state-of-the-art performance these methods achieve on clinical concept extraction. Additionally, we demonstrate contextual embeddings encode valuable semantic information not accounted for in traditional word representations.
Attacking Hardware AES with DFA
Venue: arXiv cs.CR 2019
Year: 2019

We present the first practical attack on a hardware AES accelerator with 256 bit embedded keys using DFA. We identify the challenges of adapting well-known theoretical AES DFA models to hardware under attack from voltage fault injection and present solutions to those challenges. As a result, we managed to recover 278 real-world AES-256 keys from a secure computing system in a matter of hours with minimal cost.
Optimal Algorithm to Reconstruct a Tree from a Subtree Distance
Venue: arXiv cs.DS 2019
Year: 2019

This paper addresses the problem of finding a representation of a subtree distance, which is an extension of the tree metric. We show that a minimal representation is uniquely determined by a given subtree distance, and give a linear time algorithm that finds such a representation. This algorithm achieves the optimal time complexity.
Near neighbor preserving dimension reduction for doubling subsets of $\ell_1$
Venue: arXiv cs.CG 2019
Year: 2019

Randomized dimensionality reduction has been recognized as one of the fundamental techniques in handling high-dimensional data. Starting with the celebrated Johnson-Lindenstrauss Lemma, such reductions have been studied in depth for the Euclidean $(\ell_2)$ metric, but much less for the Manhattan $(\ell_1)$ metric. Our primary motivation is the approximate nearest neighbor problem in $\ell_1$. We exploit its reduction to the decision-with-witness version, called approximate \textit{near} neighbor, which incurs a roughly logarithmic overhead. In 2007, Indyk and Naor, in the context of approximate nearest neighbors, introduced the notion of nearest neighbor-preserving embeddings. These are randomized embeddings between two metric spaces with guaranteed bounded distortion only for the distances between a query point and a point set. Such embeddings are known to exist for both $\ell_2$ and $\ell_1$ metrics, as well as for doubling subsets of $\ell_2$. The case that remained open were doubling subsets of $\ell_1$. In this paper, we propose a dimension reduction by means of a \textit{near} neighbor-preserving embedding for doubling subsets of $\ell_1$. Our approach is to represent the pointset with a carefully chosen covering set, then randomly project the latter. We study two types of covering sets: $c$-approximate $r$-nets and randomly shifted grids, and we discuss the tradeoff between them in terms of preprocessing time and target dimension. We employ Cauchy variables: certain concentration bounds derived should be of independent interest.
Algebraic Type Theory and Universe Hierarchies
Venue: arXiv cs.LO 2019
Year: 2019

It is commonly believed that algebraic notions of type theory support only universes à la Tarski, and that universes à la Russell must be removed by elaboration. We clarify the state of affairs, recalling the details of Cartmell's discipline of _generalized algebraic theory_, showing how to formulate an algebraic version of Coquand's cumulative cwfs with universes à la Russell. To demonstrate the power of algebraic techniques, we sketch a purely algebraic proof of canonicity for Martin-Löf Type Theory with universes, dependent function types, and a base type with two constants.
ABI Neural Ensemble Model for Gender Prediction Adapt Bar-Ilan Submission for the CLIN29 Shared Task on Gender Prediction
Venue: arXiv cs.CL 2019
Year: 2019

We present our system for the CLIN29 shared task on cross-genre gender detection for Dutch. We experimented with a multitude of neural models (CNN, RNN, LSTM, etc.), more "traditional" models (SVM, RF, LogReg, etc.), different feature sets as well as data pre-processing. The final results suggested that using tokenized, non-lowercased data works best for most of the neural models, while a combination of word clusters, character trigrams and word lists showed to be most beneficial for the majority of the more "traditional" (that is, non-neural) models, beating features used in previous tasks such as n-grams, character n-grams, part-of-speech tags and combinations thereof. In contradiction with the results described in previous comparable shared tasks, our neural models performed better than our best traditional approaches with our best feature set-up. Our final model consisted of a weighted ensemble model combining the top 25 models. Our final model won both the in-domain gender prediction task and the cross-genre challenge, achieving an average accuracy of 64.93% on the in-domain gender prediction task, and 56.26% on cross-genre gender prediction.
A Microservice Architecture for Online Mobile App Optimization
Venue: arXiv cs.SE 2019
Year: 2019

A large number of techniques for analyzing and optimizing mobile apps have emerged in the past decade. However, those techniques' components are notoriously difficult to extract and reuse outside their original tools. This paper introduces MAOMAO, a microservice-based reference architecture for reusing and integrating such components. MAOMAO's twin goals are (1) adoption of available app optimization techniques in practice and (2) improved construction and evaluation of new techniques. The paper uses several existing app optimization techniques to illustrate both the motivation behind MAOMAO and its potential to fundamentally alter the landscape in this area.
Text Analysis in Adversarial Settings: Does Deception Leave a Stylistic Trace?
Venue: arXiv cs.CL 2019
Year: 2019

Textual deception constitutes a major problem for online security. Many studies have argued that deceptiveness leaves traces in writing style, which could be detected using text classification techniques. By conducting an extensive literature review of existing empirical work, we demonstrate that while certain linguistic features have been indicative of deception in certain corpora, they fail to generalize across divergent semantic domains. We suggest that deceptiveness as such leaves no content-invariant stylistic trace, and textual similarity measures provide superior means of classifying texts as potentially deceptive. Additionally, we discuss forms of deception beyond semantic content, focusing on hiding author identity by writing style obfuscation. Surveying the literature on both author identification and obfuscation techniques, we conclude that current style transformation methods fail to achieve reliable obfuscation while simultaneously ensuring semantic faithfulness to the original text. We propose that future work in style transformation should pay particular attention to disallowing semantically drastic changes.
A Driving Intention Prediction Method Based on Hidden Markov Model for Autonomous Driving
Venue: arXiv cs.LG 2019
Year: 2019

In a mixed-traffic scenario where both autonomous vehicles and human-driving vehicles exist, a timely prediction of driving intentions of nearby human-driving vehicles is essential for the safe and efficient driving of an autonomous vehicle. In this paper, a driving intention prediction method based on Hidden Markov Model (HMM) is proposed for autonomous vehicles. HMMs representing different driving intentions are trained and tested with field collected data from a flyover. When training the models, either discrete or continuous characterization of the mobility features of vehicles is applied. Experimental results show that the HMMs trained with the continuous characterization of mobility features can give a higher prediction accuracy when they are used for predicting driving intentions. Moreover, when the surrounding traffic of the vehicle is taken into account, the performances of the proposed prediction method are further improved.