OpenRaiser/Intern-Atlas huggingface dataset:
Linear-time Algorithms for Eliminating Claws in Graphs
Venue: arXiv cs.DS 2020
Year: 2020

Since many NP-complete graph problems have been shown polynomial-time solvable when restricted to claw-free graphs, we study the problem of determining the distance of a given graph to a claw-free graph, considering vertex elimination as measure. CLAW-FREE VERTEX DELETION (CFVD) consists of determining the minimum number of vertices to be removed from a graph such that the resulting graph is claw-free. Although CFVD is NP-complete in general and recognizing claw-free graphs is still a challenge, where the current best algorithm for a graph $G$ has the same running time of the best algorithm for matrix multiplication, we present linear-time algorithms for CFVD on weighted block graphs and weighted graphs with bounded treewidth. Furthermore, we show that this problem can be solved in linear time by a simpler algorithm on forests, and we determine the exact values for full $k$-ary trees. On the other hand, we show that CLAW-FREE VERTEX DELETION is NP-complete even when the input graph is a split graph. We also show that the problem is hard to approximate within any constant factor better than $2$, assuming the Unique Games Conjecture.
A Mosquito Pick-and-Place System for PfSPZ-based Malaria Vaccine Production
Venue: arXiv cs.RO 2020
Year: 2020

The treatment of malaria is a global health challenge that stands to benefit from the widespread introduction of a vaccine for the disease. A method has been developed to create a live organism vaccine using the sporozoites (SPZ) of the parasite Plasmodium falciparum (Pf), which are concentrated in the salivary glands of infected mosquitoes. Current manual dissection methods to obtain these PfSPZ are not optimally efficient for large-scale vaccine production. We propose an improved dissection procedure and a mechanical fixture that increases the rate of mosquito dissection and helps to deskill this stage of the production process. We further demonstrate the automation of a key step in this production process, the picking and placing of mosquitoes from a staging apparatus into a dissection assembly. This unit test of a robotic mosquito pick-and-place system is performed using a custom-designed micro-gripper attached to a four degree of freedom (4-DOF) robot under the guidance of a computer vision system. Mosquitoes are autonomously grasped and pulled to a pair of notched dissection blades to remove the head of the mosquito, allowing access to the salivary glands. Placement into these blades is adapted based on output from computer vision to accommodate for the unique anatomy and orientation of each grasped mosquito. In this pilot test of the system on 50 mosquitoes, we demonstrate a 100% grasping accuracy and a 90% accuracy in placing the mosquito with its neck within the blade notches such that the head can be removed. This is a promising result for this difficult and non-standard pick-and-place task.
DarkneTZ: Towards Model Privacy at the Edge using Trusted Execution Environments
Venue: arXiv cs.LG 2020
Year: 2020

We present DarkneTZ, a framework that uses an edge device's Trusted Execution Environment (TEE) in conjunction with model partitioning to limit the attack surface against Deep Neural Networks (DNNs). Increasingly, edge devices (smartphones and consumer IoT devices) are equipped with pre-trained DNNs for a variety of applications. This trend comes with privacy risks as models can leak information about their training data through effective membership inference attacks (MIAs). We evaluate the performance of DarkneTZ, including CPU execution time, memory usage, and accurate power consumption, using two small and six large image classification models. Due to the limited memory of the edge device's TEE, we partition model layers into more sensitive layers (to be executed inside the device TEE), and a set of layers to be executed in the untrusted part of the operating system. Our results show that even if a single layer is hidden, we can provide reliable model privacy and defend against state of the art MIAs, with only 3% performance overhead. When fully utilizing the TEE, DarkneTZ provides model protections with up to 10% overhead.
Lower Bound for Succinct Range Minimum Query
Venue: arXiv cs.DS 2020
Year: 2020

Given an integer array $A[1..n]$, the Range Minimum Query problem (RMQ) asks to preprocess $A$ into a data structure, supporting RMQ queries: given $a,b\in [1,n]$, return the index $i\in[a,b]$ that minimizes $A[i]$, i.e., $\mathrm{argmin}_{i\in[a,b]} A[i]$. This problem has a classic solution using $O(n)$ space and $O(1)$ query time by Gabow, Bentley, Tarjan (STOC, 1984) and Harel, Tarjan (SICOMP, 1984). The best known data structure by Fischer, Heun (SICOMP, 2011) and Navarro, Sadakane (TALG, 2014) uses $2n+n/(\frac{\log n}{t})^t+\tilde{O}(n^{3/4})$ bits and answers queries in $O(t)$ time, assuming the word-size is $w=Θ(\log n)$. In particular, it uses $2n+n/\mathrm{poly}\log n$ bits of space as long as the query time is a constant. In this paper, we prove the first lower bound for this problem, showing that $2n+n/\mathrm{poly}\log n$ space is necessary for constant query time. In general, we show that if the data structure has query time $O(t)$, then it must use at least $2n+n/(\log n)^{\tilde{O}(t^2)}$ space, in the cell-probe model with word-size $w=Θ(\log n)$.
Deep-Edge: An Efficient Framework for Deep Learning Model Update on Heterogeneous Edge
Venue: arXiv cs.DC 2020
Year: 2020

Deep Learning (DL) model-based AI services are increasingly offered in a variety of predictive analytics services such as computer vision, natural language processing, speech recognition. However, the quality of the DL models can degrade over time due to changes in the input data distribution, thereby requiring periodic model updates. Although cloud data-centers can meet the computational requirements of the resource-intensive and time-consuming model update task, transferring data from the edge devices to the cloud incurs a significant cost in terms of network bandwidth and are prone to data privacy issues. With the advent of GPU-enabled edge devices, the DL model update can be performed at the edge in a distributed manner using multiple connected edge devices. However, efficiently utilizing the edge resources for the model update is a hard problem due to the heterogeneity among the edge devices and the resource interference caused by the co-location of the DL model update task with latency-critical tasks running in the background. To overcome these challenges, we present Deep-Edge, a load- and interference-aware, fault-tolerant resource management framework for performing model update at the edge that uses distributed training. This paper makes the following contributions. First, it provides a unified framework for monitoring, profiling, and deploying the DL model update tasks on heterogeneous edge devices. Second, it presents a scheduler that reduces the total re-training time by appropriately selecting the edge devices and distributing data among them such that no latency-critical applications experience deadline violations. Finally, we present empirical results to validate the efficacy of the framework using a real-world DL model update case-study based on the Caltech dataset and an edge AI cluster testbed.
Exploiting Interpretable Patterns for Flow Prediction in Dockless Bike Sharing Systems
Venue: arXiv cs.LG 2020
Year: 2020

Unlike the traditional dock-based systems, dockless bike-sharing systems are more convenient for users in terms of flexibility. However, the flexibility of these dockless systems comes at the cost of management and operation complexity. Indeed, the imbalanced and dynamic use of bikes leads to mandatory rebalancing operations, which impose a critical need for effective bike traffic flow prediction. While efforts have been made in developing traffic flow prediction models, existing approaches lack interpretability, and thus have limited value in practical deployment. To this end, we propose an Interpretable Bike Flow Prediction (IBFP) framework, which can provide effective bike flow prediction with interpretable traffic patterns. Specifically, by dividing the urban area into regions according to flow density, we first model the spatio-temporal bike flows between regions with graph regularized sparse representation, where graph Laplacian is used as a smooth operator to preserve the commonalities of the periodic data structure. Then, we extract traffic patterns from bike flows using subspace clustering with sparse representation to construct interpretable base matrices. Moreover, the bike flows can be predicted with the interpretable base matrices and learned parameters. Finally, experimental results on real-world data show the advantages of the IBFP method for flow prediction in dockless bike sharing systems. In addition, the interpretability of our flow pattern exploitation is further illustrated through a case study where IBFP provides valuable insights into bike flow analysis.
Adversarial Likelihood-Free Inference on Black-Box Generator
Venue: arXiv cs.LG 2020
Year: 2020

Generative Adversarial Network (GAN) can be viewed as an implicit estimator of a data distribution, and this perspective motivates using the adversarial concept in the true input parameter estimation of black-box generators. While previous works on likelihood-free inference introduces an implicit proposal distribution on the generator input, this paper analyzes theoretic limitations of the proposal distribution approach. On top of that, we introduce a new algorithm, Adversarial Likelihood-Free Inference (ALFI), to mitigate the analyzed limitations, so ALFI is able to find the posterior distribution on the input parameter for black-box generative models. We experimented ALFI with diverse simulation models as well as pre-trained statistical models, and we identified that ALFI achieves the best parameter estimation accuracy with a limited simulation budget.
Unified Multi-Criteria Chinese Word Segmentation with BERT
Venue: arXiv cs.CL 2020
Year: 2020

Multi-Criteria Chinese Word Segmentation (MCCWS) aims at finding word boundaries in a Chinese sentence composed of continuous characters while multiple segmentation criteria exist. The unified framework has been widely used in MCCWS and shows its effectiveness. Besides, the pre-trained BERT language model has been also introduced into the MCCWS task in a multi-task learning framework. In this paper, we combine the superiority of the unified framework and pretrained language model, and propose a unified MCCWS model based on BERT. Moreover, we augment the unified BERT-based MCCWS model with the bigram features and an auxiliary criterion classification task. Experiments on eight datasets with diverse criteria demonstrate that our methods could achieve new state-of-the-art results for MCCWS.
MLR: A Two-stage Conversational Query Rewriting Model with Multi-task Learning
Venue: arXiv cs.CL 2020
Year: 2020

Conversational context understanding aims to recognize the real intention of user from the conversation history, which is critical for building the dialogue system. However, the multi-turn conversation understanding in open domain is still quite challenging, which requires the system extracting the important information and resolving the dependencies in contexts among a variety of open topics. In this paper, we propose the conversational query rewriting model - MLR, which is a Multi-task model on sequence Labeling and query Rewriting. MLR reformulates the multi-turn conversational queries into a single turn query, which conveys the true intention of users concisely and alleviates the difficulty of the multi-turn dialogue modeling. In the model, we formulate the query rewriting as a sequence generation problem and introduce word category information via the auxiliary word category label predicting task. To train our model, we construct a new Chinese query rewriting dataset and conduct experiments on it. The experimental results show that our model outperforms compared models, and prove the effectiveness of the word category information in improving the rewriting performance.
Detecting Straggler MapReduce Tasks in Big Data Processing Infrastructure by Neural Network
Venue: arXiv cs.DC 2020
Year: 2020

Straggler task detection is one of the main challenges in applying MapReduce for parallelizing and distributing large-scale data processing. It is defined as detecting running tasks on weak nodes. Considering two stages in the Map phase copy, combine and three stages of Reduce shuffle, sort and reduce, the total execution time is the total sum of the execution time of these five stages. Estimating the correct execution time in each stage that results in correct total execution time is the primary purpose of this paper. The proposed method is based on the application of a backpropagation Neural Network NN on the Hadoop for the detection of straggler tasks, to estimate the remaining execution time of tasks that is very important in straggler task detection. Results achieved have been compared with popular algorithms in this domain such as LATE, ESAMR and the real remaining time for WordCount and Sort benchmarks, and shown able to detect straggler tasks and estimate execution time accurately. Besides, it supports to accelerate task execution time.
SecureIT using Firebase, Google map and Node.Js
Venue: arXiv cs.HC 2020
Year: 2020

This paper is about describing the features of a software that was developed for its user safety which we called SecureIT is a android based soft ware using Android SDK along with Firebase and Google map SDK along with Node.Js. The aim of developing this project was to make sure and taking its users safety to a next level. Actually now a days some crime incidents like rapes, fire accidents and snatchings are very common and we believe many of those can be prevented if victim got support at the right time. According to the well known daily news paper of Bangladesh The Daily Star there were about 1413 women was rapped where 76 women were dead in 2019. On the same pa-per it also said that in 2018 and 2017 the number of rapes were 732 and 818 where we can easily get that the number increases to almost double in 2019. Where we get a point that if those girls get support or get people known about their location at the right time they might get rid of the situation and the number of rapes could be reduced a lot because we all know that now a days using mo-bile smartphone is too easy for people. Although leading Chinese mobile phone company Xiaomi introduced a new feature Emergency SOS service in their mobile phones at the end of 2018 with a MIUI 10 update but this feature is only limited to the Xiaomi phones and it was well advertised as well. This paper will briefly describe all the features of our software and its usages.
Exposing Hardware Building Blocks to Machine Learning Frameworks
Venue: arXiv cs.LG 2020
Year: 2020

There are a plethora of applications that demand high throughput and low latency algorithms leveraging machine learning methods. This need for real time processing can be seen in industries ranging from developing neural network based pre-distortors for enhanced mobile broadband to designing FPGA-based triggers in major scientific efforts by CERN for particle physics. In this thesis, we explore how niche domains can benefit vastly if we look at neurons as a unique boolean function of the form $f:B^{I} \rightarrow B^{O}$, where $B = \{0,1\}$. We focus on how to design topologies that complement such a view of neurons, how to automate such a strategy of neural network design, and inference of such networks on Xilinx FPGAs. Major hardware borne constraints arise when designing topologies that view neurons as unique boolean functions. Fundamentally, realizing such topologies on hardware asserts a strict limit on the 'fan-in' bits of a neuron due to the doubling of permutations possible with every increment in input bit-length. We address this limit by exploring different methods of implementing sparsity and explore activation quantization. Further, we develop a library that supports training a neural network with custom sparsity and quantization. This library also supports conversion of trained Sparse Quantized networks from PyTorch to VERILOG code which is then synthesized using Vivado, all of which is part of the LogicNet tool-flow. To aid faster prototyping, we also support calculation of the worst-case hardware cost of any given topology. We hope that our insights into the behavior of extremely sparse quantized neural networks are of use to the research community and by extension allow people to use the LogicNet design flow to deploy highly efficient neural networks.
Blind Adversarial Training: Balance Accuracy and Robustness
Venue: arXiv cs.LG 2020
Year: 2020

Adversarial training (AT) aims to improve the robustness of deep learning models by mixing clean data and adversarial examples (AEs). Most existing AT approaches can be grouped into restricted and unrestricted approaches. Restricted AT requires a prescribed uniform budget to constrain the magnitude of the AE perturbations during training, with the obtained results showing high sensitivity to the budget. On the other hand, unrestricted AT uses unconstrained AEs, resulting in the use of AEs located beyond the decision boundary; these overestimated AEs significantly lower the accuracy on clean data. These limitations mean that the existing AT approaches have difficulty in obtaining a comprehensively robust model with high accuracy and robustness when confronting attacks with varying strengths. Considering this problem, this paper proposes a novel AT approach named blind adversarial training (BAT) to better balance the accuracy and robustness. The main idea of this approach is to use a cutoff-scale strategy to adaptively estimate a nonuniform budget to modify the AEs used in the training, ensuring that the strengths of the AEs are dynamically located in a reasonable range and ultimately improving the overall robustness of the AT model. The experimental results obtained using BAT for training classification models on several benchmarks demonstrate the competitive performance of this method.
CVPR 2019 WAD Challenge on Trajectory Prediction and 3D Perception
Venue: arXiv cs.CV 2020
Year: 2020

This paper reviews the CVPR 2019 challenge on Autonomous Driving. Baidu's Robotics and Autonomous Driving Lab (RAL) providing 150 minutes labeled Trajectory and 3D Perception dataset including about 80k lidar point cloud and 1000km trajectories for urban traffic. The challenge has two tasks in (1) Trajectory Prediction and (2) 3D Lidar Object Detection. There are more than 200 teams submitted results on Leaderboard and more than 1000 participants attended the workshop.
Adversarial Augmentation Policy Search for Domain and Cross-Lingual Generalization in Reading Comprehension
Venue: arXiv cs.CL 2020
Year: 2020

Reading comprehension models often overfit to nuances of training datasets and fail at adversarial evaluation. Training with adversarially augmented dataset improves robustness against those adversarial attacks but hurts generalization of the models. In this work, we present several effective adversaries and automated data augmentation policy search methods with the goal of making reading comprehension models more robust to adversarial evaluation, but also improving generalization to the source domain as well as new domains and languages. We first propose three new methods for generating QA adversaries, that introduce multiple points of confusion within the context, show dependence on insertion location of the distractor, and reveal the compounding effect of mixing adversarial strategies with syntactic and semantic paraphrasing methods. Next, we find that augmenting the training datasets with uniformly sampled adversaries improves robustness to the adversarial attacks but leads to decline in performance on the original unaugmented dataset. We address this issue via RL and more efficient Bayesian policy search methods for automatically learning the best augmentation policy combinations of the transformation probability for each adversary in a large search space. Using these learned policies, we show that adversarial training can lead to significant improvements in in-domain, out-of-domain, and cross-lingual (German, Russian, Turkish) generalization.
Which Blockchain to choose? A decision support tool to guide the choice of a Blockchain technology
Venue: arXiv cs.CR 2020
Year: 2020

Companies trying to build new solutions using blockchain are confronted with a plethora of available concurrent technologies that have many control knobs which require fine-tuning by experts. Exiting studies that build decision models for blockchain adoption or selection lack an automated way to use non-functional requirements to provide recommendations. In this paper, we build a knowledge base for blockchain solutions by analyzing whitepapers and studies, but also our benchmark results performed in a controlled environment. Then, we implement a Multi-Criterion Decision Analysis method to determine the most suitable blockchain solution from companies provided requirements and preferences. Finally, we illustrate our approach by running the decision process on a realistic supply-chain use case. This paper provides a rationale for blockchain deployment choices. While still limited in scope, we plan to include more blockchain alternative and more flexible requirements inputs in future work.
Selective Encoding Policies for Maximizing Information Freshness
Venue: arXiv cs.IT 2020
Year: 2020

An information source generates independent and identically distributed status update messages from an observed random phenomenon which takes $n$ distinct values based on a given pmf. These update packets are encoded at the transmitter node to be sent to a receiver node which wants to track the observed random variable with as little age as possible. The transmitter node implements a selective $k$ encoding policy such that rather than encoding all possible $n$ realizations, the transmitter node encodes the most probable $k$ realizations. We consider three different policies regarding the remaining $n-k$ less probable realizations: $highest$ $k$ $selective$ $encoding$ which disregards whenever a realization from the remaining $n-k$ values occurs; $randomized$ $selective$ $encoding$ which encodes and sends the remaining $n-k$ realizations with a certain probability to further inform the receiver node at the expense of longer codewords for the selected $k$ realizations; and $highest$ $k$ $selective$ $encoding$ $with$ $an$ $empty$ $symbol$ which sends a designated empty symbol when one of the remaining $n-k$ realizations occurs. For all of these three encoding schemes, we find the average age and determine the age-optimal real codeword lengths, including the codeword length for the empty symbol in the case of the latter scheme, such that the average age at the receiver node is minimized. Through numerical evaluations for arbitrary pmfs, we show that these selective encoding policies result in a lower average age than encoding every realization, and find the corresponding age-optimal $k$ values.