OpenRaiser/Intern-Atlas huggingface dataset:
Edge-Disjoint Branchings in Temporal Graphs
Venue: arXiv cs.DS 2020
Year: 2020

A temporal digraph ${\cal G}$ is a triple $(G, γ, λ)$ where $G$ is a digraph, $γ$ is a function on $V(G)$ that tells us the timestamps when a vertex is active, and $λ$ is a function on $E(G)$ that tells for each $uv \in E(G)$ when $u$ and $v$ are linked. Given a static digraph $G$, and a subset $R\subseteq V(G)$, a spanning branching with root $R$ is a subdigraph of $G$ that has exactly one path from $R$ to each $v\in V(G)$. In this paper, we consider the temporal version of Edmonds' classical result about the problem of finding $k$ edge-disjoint spanning branchings respectively rooted at given $R_1,\cdots,R_k$. We introduce and investigate different definitions of spanning branchings, and of edge-disjointness in the context of temporal graphs. A branching ${\cal B}$ is vertex-spanning if the root is able to reach each vertex $v$ of $G$ at some time where $v$ is active, while it is temporal-spanning if $v$ can be reached from the root at every time where $v$ is active. On the other hand, two branchings ${\cal B}_1$ and ${\cal B}_2$ are edge-disjoint if they do not use the same edge of $G$, and are temporal-edge-disjoint if they can use the same edge of $G$ but at different times. This lead us to four definitions of disjoint spanning branchings and we prove that, unlike the static case, only one of these can be computed in polynomial time, namely the temporal-edge-disjoint temporal-spanning branchings problem, while the other versions are $\mathsf{NP}$-complete, even under very strict assumptions.
Automatic Section Recognition in Obituaries
Venue: arXiv cs.CL 2020
Year: 2020

Obituaries contain information about people's values across times and cultures, which makes them a useful resource for exploring cultural history. They are typically structured similarly, with sections corresponding to Personal Information, Biographical Sketch, Characteristics, Family, Gratitude, Tribute, Funeral Information and Other aspects of the person. To make this information available for further studies, we propose a statistical model which recognizes these sections. To achieve that, we collect a corpus of 20058 English obituaries from TheDaily Item, Remembering.CA and The London Free Press. The evaluation of our annotation guidelines with three annotators on 1008 obituaries shows a substantial agreement of Fleiss k = 0.87. Formulated as an automatic segmentation task, a convolutional neural network outperforms bag-of-words and embedding-based BiLSTMs and BiLSTM-CRFs with a micro F1 = 0.81.
A (probably) optimal algorithm for Bisection on bounded-treewidth graphs
Venue: arXiv cs.DS 2020
Year: 2020

The maximum/minimum bisection problems are, given an edge-weighted graph, to find a bipartition of the vertex set into two sets whose sizes differ by at most one, such that the total weight of edges between the two sets is maximized/minimized. Although these two problems are known to be NP-hard, there is an efficient algorithm for bounded-treewidth graphs. In particular, Jansen et al. (SIAM J. Comput. 2005) gave an $O(2^tn^3)$-time algorithm when given a tree decomposition of width $t$ of the input graph, where $n$ is the number of vertices of the input graph. Eiben et al. (ESA 2019) improved the dependency of $n$ in the running time by giving an $O(8^tt^5n^2\log n)$-time algorithm. Moreover, they showed that there is no $O(n^{2-\varepsilon})$-time algorithm for trees under some reasonable complexity assumption. In this paper, we show an $O(2^t(tn)^2)$-time algorithm for both problems, which is asymptotically tight to their conditional lower bound. We also show that the exponential dependency of the treewidth is asymptotically optimal under the Strong Exponential Time Hypothesis. Finally, we discuss the (in)tractability of both problems with respect to special graph classes.
Resource Management Techniques for Cloud-Based IoT Environment
Venue: arXiv cs.NI 2020
Year: 2020

Internet of Things (IoT) is an Internet-based environment of connected devices and applications. IoT creates an environment where physical devices and sensors are flawlessly combined into information nodes to deliver innovative and smart services for human-being to make their life easier and more efficient. The main objective of the IoT devices-network is to generate data, which are converted into useful information by the data analysis process, it also provides useful resources to the end users. IoT resource management is a key challenge to ensure the quality of end user experience. Many IoT smart devices and technologies like sensors, actuators, RFID, UMTS, 3G, and GSM etc. are used to develop IoT networks. Cloud Computing plays an important role in these networks deployment by providing physical resources as virtualized resources consist of memory, computation power, network bandwidth, virtualized system and device drivers in secure and pay as per use basis. One of the major concerns of Cloud-based IoT environment is resource management, which ensures efficient resource utilization, load balancing, reduce SLA violation, and improve the system performance by reducing operational cost and energy consumption. Many researchers have been proposed IoT based resource management techniques. The focus of this paper is to investigate these proposed resource allocation techniques and finds which parameters must be considered for improvement in resource allocation for IoT networks. Further, this paper also uncovered challenges and issues of Cloud-based resource allocation for IoT environment.
Linear Features Observation Model for Autonomous Vehicle Localization
Venue: arXiv cs.RO 2020
Year: 2020

Precise localization is a core ability of an autonomous vehicle. It is a prerequisite for motion planning and execution. The well-established localization approaches such as Kalman and particle filters require a probabilistic observation model allowing to compute a likelihood of measurement given a system state vector, usually vehicle pose, and a map. The higher precision of the localization system may be achieved through the development of a more sophisticated observation model considering various measurement error sources. Meanwhile model needs to be simple to be computable in real-time. This paper proposes an observation model for visually detected linear features. Examples of such features include, but not limited to, road markings and road boundaries. The proposed observation model depicts two core detection error sources: shift error and angular error. It also considers the probability of false-positive detection. The structure of the proposed model allows precomputing and incorporating the measurement error directly into the map represented by a multichannel digital image. Measurement error precomputation and storing the map as an image speeds up observation likelihood computation and in turn localization system. The experimental evaluation on real autonomous vehicle demonstrates that the proposed model allows for precise and reliable localization in a variety of scenarios.
Adversarial Deepfakes: Evaluating Vulnerability of Deepfake Detectors to Adversarial Examples
Venue: arXiv cs.CV 2020
Year: 2020

Recent advances in video manipulation techniques have made the generation of fake videos more accessible than ever before. Manipulated videos can fuel disinformation and reduce trust in media. Therefore detection of fake videos has garnered immense interest in academia and industry. Recently developed Deepfake detection methods rely on deep neural networks (DNNs) to distinguish AI-generated fake videos from real videos. In this work, we demonstrate that it is possible to bypass such detectors by adversarially modifying fake videos synthesized using existing Deepfake generation methods. We further demonstrate that our adversarial perturbations are robust to image and video compression codecs, making them a real-world threat. We present pipelines in both white-box and black-box attack scenarios that can fool DNN based Deepfake detectors into classifying fake videos as real.
Uncovering Insurance Fraud Conspiracy with Network Learning
Venue: arXiv cs.CR 2020
Year: 2020

Fraudulent claim detection is one of the greatest challenges the insurance industry faces. Alibaba's return-freight insurance, providing return-shipping postage compensations over product return on the e-commerce platform, receives thousands of potentially fraudulent claims every day. Such deliberate abuse of the insurance policy could lead to heavy financial losses. In order to detect and prevent fraudulent insurance claims, we developed a novel data-driven procedure to identify groups of organized fraudsters, one of the major contributions to financial losses, by learning network information. In this paper, we introduce a device-sharing network among claimants, followed by developing an automated solution for fraud detection based on graph learning algorithms, to separate fraudsters from regular customers and uncover groups of organized fraudsters. This solution applied at Alibaba achieves more than 80% precision while covering 44% more suspicious accounts compared with a previously deployed rule-based classifier after human expert investigations. Our approach can easily and effectively generalizes to other types of insurance.
Exact artificial boundary conditions of 1D semi-discretized peridynamics
Venue: arXiv cs.CE 2020
Year: 2020

The peridynamic theory reformulates the equations of continuum mechanics in terms of integro-differential equations instead of partial differential equations. It is not trivial to directly apply naive approach in artificial boundary conditions for continua to peridynamics modeling, because it usually involves semi-discretization scheme. In this paper, we present a new way to construct exact boundary conditions for semi-discretized peridynamics using kernel functions and recursive relations. Specially, kernel functions are used to characterize one single source are combined to construct the exact boundary conditions. The recursive relationships between the kernel functions are proposed, therefore the kernel functions can be computed through the ordinary differential system and integral system with high precision. The numerical results demonstrate that the boundary condition has high accuracy. The proposed method can be applied to modeling of wave propagation of other nonlocal theories and high dimensional cases.
Probably Approximately Correct Vision-Based Planning using Motion Primitives
Venue: arXiv cs.RO 2020
Year: 2020

This paper presents an approach for learning vision-based planners that provably generalize to novel environments (i.e., environments unseen during training). We leverage the Probably Approximately Correct (PAC)-Bayes framework to obtain an upper bound on the expected cost of policies across all environments. Minimizing the PAC-Bayes upper bound thus trains policies that are accompanied by a certificate of performance on novel environments. The training pipeline we propose provides strong generalization guarantees for deep neural network policies by (a) obtaining a good prior distribution on the space of policies using Evolutionary Strategies (ES) followed by (b) formulating the PAC-Bayes optimization as an efficiently-solvable parametric convex optimization problem. We demonstrate the efficacy of our approach for producing strong generalization guarantees for learned vision-based motion planners through two simulated examples: (1) an Unmanned Aerial Vehicle (UAV) navigating obstacle fields with an onboard vision sensor, and (2) a dynamic quadrupedal robot traversing rough terrains with proprioceptive and exteroceptive sensors.
Metaphoric Paraphrase Generation
Venue: arXiv cs.CL 2020
Year: 2020

This work describes the task of metaphoric paraphrase generation, in which we are given a literal sentence and are charged with generating a metaphoric paraphrase. We propose two different models for this task: a lexical replacement baseline and a novel sequence to sequence model, 'metaphor masking', that generates free metaphoric paraphrases. We use crowdsourcing to evaluate our results, as well as developing an automatic metric for evaluating metaphoric paraphrases. We show that while the lexical replacement baseline is capable of producing accurate paraphrases, they often lack metaphoricity, while our metaphor masking model excels in generating metaphoric sentences while performing nearly as well with regard to fluency and paraphrase quality.
Applying Tensor Decomposition to image for Robustness against Adversarial Attack
Venue: arXiv cs.CV 2020
Year: 2020

Nowadays the deep learning technology is growing faster and shows dramatic performance in computer vision areas. However, it turns out a deep learning based model is highly vulnerable to some small perturbation called an adversarial attack. It can easily fool the deep learning model by adding small perturbations. On the other hand, tensor decomposition method widely uses for compressing the tensor data, including data matrix, image, etc. In this paper, we suggest combining tensor decomposition for defending the model against adversarial example. We verify this idea is simple and effective to resist adversarial attack. In addition, this method rarely degrades the original performance of clean data. We experiment on MNIST, CIFAR10 and ImageNet data and show our method robust on state-of-the-art attack methods.
Library Adoption Dynamics in Software Teams
Venue: arXiv cs.SI 2020
Year: 2020

When a group of people strives to understand new information, struggle ensues as various ideas compete for attention. Steep learning curves are surmounted as teams learn together. To understand how these team dynamics play out in software development, we explore Git logs, which provide a complete change history of software repositories. In these repositories, we observe code additions, which represent successfully implemented ideas, and code deletions, which represent ideas that have failed or been superseded. By examining the patterns between these commit types, we can begin to understand how teams adopt new information. We specifically study what happens after a software library is adopted by a project, i.e. when a library is used for the first time in the project. We find that a variety of factors, including team size, library popularity, and prevalence on Stack Overflow are associated with how quickly teams learn and successfully adopt new software libraries.
Deterministic Intra-Vehicle Communications: Timing and Synchronization
Venue: arXiv cs.NI 2020
Year: 2020

As we power through to the future, in-vehicle communications reliance on speed is becoming a challenging predicament. This is mainly due to the ever-increasing number of electronic control units (ECUs), which will continue to drain network capacity, hence further increasing bandwidth demand. For a wired network, a tradeoff between bandwidth requirement, reliability, and cost-effectiveness has been our main motivation in developing a high-speed network architecture that is based on the integration of two time-triggered protocols namely; Time Triggered Ethernet (TT-E) and Time Triggered Controller Area Network (TT-CAN). Therefore, as a visible example of an Internet of Vehicles technology, we present a time triggered communication-based network architecture. The new architecture can provide scalable integration of advanced functionalities, while maintaining safety and high reliability. To comply with the bandwidth requirement, we consider high-speed TT-Ethernet as the main bus (i.e., backbone network) where sub-networks can use more cost-effective and lower bandwidth TT-CAN to communicate with other entities in the network via a gateway. The main challenge in the proposed network architecture has been to resolve interoperability between two entirely different time-triggered protocols, especially in terms of timing and synchronization. In this paper, we first explore the main key drivers of the proposed architecture, which are bandwidth, reliability, and timeliness. We then demonstrate the effectiveness of our gateway design in providing full interoperability between the two time-triggered protocols.
Inexpensive surface electromyography sleeve with consistent electrode placement enables dexterous and stable prosthetic control through deep learning
Venue: arXiv cs.RO 2020
Year: 2020

The dexterity of conventional myoelectric prostheses is limited in part by the small datasets used to train the control algorithms. Variations in surface electrode positioning make it difficult to collect consistent data and to estimate motor intent reliably over time. To address these challenges, we developed an inexpensive, easy-to-don sleeve that can record robust and repeatable surface electromyography from 32 embedded monopolar electrodes. Embedded grommets are used to consistently align the sleeve with natural skin markings (e.g., moles, freckles, scars). The sleeve can be manufactured in a few hours for less than $60. Data from seven intact participants show the sleeve provides a signal-to-noise ratio of 14, a don-time under 11 seconds, and sub-centimeter precision for electrode placement. Furthermore, in a case study with one intact participant, we use the sleeve to demonstrate that neural networks can provide simultaneous and proportional control of six degrees of freedom, even 263 days after initial algorithm training. We also highlight that consistent recordings, accumulated over time to establish a large dataset, significantly improve dexterity. These results suggest that deep learning with a 74-layer neural network can substantially improve the dexterity and stability of myoelectric prosthetic control, and that deep-learning techniques can be readily instantiated and further validated through inexpensive sleeves/sockets with consistent recording locations.
Improved Algorithm for Min-Cuts in Distributed Networks
Venue: arXiv cs.DS 2020
Year: 2020

In this thesis, we present fast deterministic algorithm to find small cuts in distributed networks. Finding small min-cuts for a network is essential for ensuring the quality of service and reliability. Throughout this thesis, we use the CONGEST model which is a typical message passing model used to design and analyze algorithms in distributed networks. We survey various algorithmic techniques in the CONGEST model and give an overview of the recent results to find cuts. We also describe elegant graph theoretic ideas like cut spaces and cycle spaces that provide useful intuition upon which our work is built. Our contribution is a novel fast algorith to find small cuts. Our algorithm relies on a new characterization of trees and cuts introduced in this thesis. Our algorithm is built upon several new algorithmic ideas that, when coupled with our characterization of trees and cuts, help us to find the required min-cuts. Our novel techniques include a tree restricted semigroup function (TRSF), a novel sketching technique, and a layered algorithm. TRSF is defined with respect to a spanning tree and is based on a commutative semigroup. This simple yet powerful technique helps us to deterministically find min-cuts of size one (bridges) and min-cuts of size two optimally. Our sketching technique samples a small but relevant vertex set which is enough to find small min-cuts in certain cases. Our layered algorithm finds min-cuts in smaller sub-graphs pivoted by nodes at different levels in a spanning tree and uses them to make the decision about the min-cuts in the complete graph. This is interesting because it enables us to show that even for a global property like finding min-cuts, local information can be exploited in a coordinated manner.
NLOptControl: A modeling language for solving optimal control problems
Venue: arXiv cs.MS 2020
Year: 2020

Current direct-collocation-based optimal control software is either easy to use or fast, but not both. This is a major limitation for users that are trying to formulate complex optimal control problems (OCPs) for use in on-line applications. This paper introduces NLOptControl, an open-source modeling language that allows users to both easily formulate and quickly solve nonlinear OCPs using direct-collocation methods. To achieve these attributes, NLOptControl (1) is written in an efficient, dynamically-typed computing language called Julia, (2) extends an optimization modeling language called JuMP to provide a natural algebraic syntax for modeling nonlinear OCPs; and (3) uses reverse automatic differentiation with the acrylic-coloring method to exploit sparsity in the Hessian matrix. This work explores the novel design features of NLOptControl and compares its syntax and speed to those of PROPT. The syntax comparisons shows that NLOptControl models OCPs more concisely than PROPT. The speeds of various collocation methods within PROPT and NLOptControl are benchmarked over a range of collocation points using performance profiles; overall, NLOptControl's single, two, and four interval pseudospectral methods are roughly $14$, $26$, and $36$ times faster than PROPT's, respectively. NLOptControl is well-suited to improve existing off-line and on-line control systems and to engender new ones.
WaveQ: Gradient-Based Deep Quantization of Neural Networks through Sinusoidal Adaptive Regularization
Venue: arXiv cs.LG 2020
Year: 2020

As deep neural networks make their ways into different domains, their compute efficiency is becoming a first-order constraint. Deep quantization, which reduces the bitwidth of the operations (below 8 bits), offers a unique opportunity as it can reduce both the storage and compute requirements of the network super-linearly. However, if not employed with diligence, this can lead to significant accuracy loss. Due to the strong inter-dependence between layers and exhibiting different characteristics across the same network, choosing an optimal bitwidth per layer granularity is not a straight forward. As such, deep quantization opens a large hyper-parameter space, the exploration of which is a major challenge. We propose a novel sinusoidal regularization, called SINAREQ, for deep quantized training. Leveraging the sinusoidal properties, we seek to learn multiple quantization parameterization in conjunction during gradient-based training process. Specifically, we learn (i) a per-layer quantization bitwidth along with (ii) a scale factor through learning the period of the sinusoidal function. At the same time, we exploit the periodicity, differentiability, and the local convexity profile in sinusoidal functions to automatically propel (iii) network weights towards values quantized at levels that are jointly determined. We show how SINAREQ balance compute efficiency and accuracy, and provide a heterogeneous bitwidth assignment for quantization of a large variety of deep networks (AlexNet, CIFAR-10, MobileNet, ResNet-18, ResNet-20, SVHN, and VGG-11) that virtually preserves the accuracy. Furthermore, we carry out experimentation using fixed homogenous bitwidths with 3- to 5-bit assignment and show the versatility of SINAREQ in enhancing quantized training algorithms (DoReFa and WRPN) with about 4.8% accuracy improvements on average, and then outperforming multiple state-of-the-art techniques.
A Compiler Infrastructure for FPGA and ASIC Development
Venue: arXiv cs.AR 2020
Year: 2020

This whitepaper proposes a unified framework for hardware design tools to ease the development and inter-operability of said tools. By creating a large ecosystem of hardware development tools across vendors, academia, and the open source community, we hope to significantly increase much need productivity in hardware design.