OpenRaiser/Intern-Atlas huggingface dataset:
Signature-Based Abduction for Expressive Description Logics -- Technical Report
Venue: arXiv cs.AI 2020
Year: 2020

Signature-based abduction aims at building hypotheses over a specified set of names, the signature, that explain an observation relative to some background knowledge. This type of abduction is useful for tasks such as diagnosis, where the vocabulary used for observed symptoms differs from the vocabulary expected to explain those symptoms. We present the first complete method solving signature-based abduction for observations expressed in the expressive description logic ALC, which can include TBox and ABox axioms, thereby solving the knowledge base abduction problem. The method is guaranteed to compute a finite and complete set of hypotheses, and is evaluated on a set of realistic knowledge bases.
Convolutional Neural Network Training with Distributed K-FAC
Venue: arXiv cs.LG 2020
Year: 2020

Training neural networks with many processors can reduce time-to-solution; however, it is challenging to maintain convergence and efficiency at large scales. The Kronecker-factored Approximate Curvature (K-FAC) was recently proposed as an approximation of the Fisher Information Matrix that can be used in natural gradient optimizers. We investigate here a scalable K-FAC design and its applicability in convolutional neural network (CNN) training at scale. We study optimization techniques such as layer-wise distribution strategies, inverse-free second-order gradient evaluation, and dynamic K-FAC update decoupling to reduce training time while preserving convergence. We use residual neural networks (ResNet) applied to the CIFAR-10 and ImageNet-1k datasets to evaluate the correctness and scalability of our K-FAC gradient preconditioner. With ResNet-50 on the ImageNet-1k dataset, our distributed K-FAC implementation converges to the 75.9% MLPerf baseline in 18-25% less time than does the classic stochastic gradient descent (SGD) optimizer across scales on a GPU cluster.
TiledSoilingNet: Tile-level Soiling Detection on Automotive Surround-view Cameras Using Coverage Metric
Venue: arXiv cs.CV 2020
Year: 2020

Automotive cameras, particularly surround-view cameras, tend to get soiled by mud, water, snow, etc. For higher levels of autonomous driving, it is necessary to have a soiling detection algorithm which will trigger an automatic cleaning system. Localized detection of soiling in an image is necessary to control the cleaning system. It is also necessary to enable partial functionality in unsoiled areas while reducing confidence in soiled areas. Although this can be solved using a semantic segmentation task, we explore a more efficient solution targeting deployment in low power embedded system. We propose a novel method to regress the area of each soiling type within a tile directly. We refer to this as coverage. The proposed approach is better than learning the dominant class in a tile as multiple soiling types occur within a tile commonly. It also has the advantage of dealing with coarse polygon annotation, which will cause the segmentation task. The proposed soiling coverage decoder is an order of magnitude faster than an equivalent segmentation decoder. We also integrated it into an object detection and semantic segmentation multi-task model using an asynchronous back-propagation algorithm. A portion of the dataset used will be released publicly as part of our WoodScape dataset to encourage further research.
Query-Free Adversarial Transfer via Undertrained Surrogates
Venue: arXiv cs.CV 2020
Year: 2020

Deep neural networks are vulnerable to adversarial examples -- minor perturbations added to a model's input which cause the model to output an incorrect prediction. We introduce a new method for improving the efficacy of adversarial attacks in a black-box setting by undertraining the surrogate model which the attacks are generated on. Using two datasets and five model architectures, we show that this method transfers well across architectures and outperforms state-of-the-art methods by a wide margin. We interpret the effectiveness of our approach as a function of reduced surrogate model loss function curvature and increased universal gradient characteristics, and show that our approach reduces the presence of local loss maxima which hinder transferability. Our results suggest that finding strong single surrogate models is a highly effective and simple method for generating transferable adversarial attacks, and that this method represents a valuable route for future study in this field.
Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text Retrieval
Venue: arXiv cs.IR 2020
Year: 2020

Conducting text retrieval in a dense learned representation space has many intriguing advantages over sparse retrieval. Yet the effectiveness of dense retrieval (DR) often requires combination with sparse retrieval. In this paper, we identify that the main bottleneck is in the training mechanisms, where the negative instances used in training are not representative of the irrelevant documents in testing. This paper presents Approximate nearest neighbor Negative Contrastive Estimation (ANCE), a training mechanism that constructs negatives from an Approximate Nearest Neighbor (ANN) index of the corpus, which is parallelly updated with the learning process to select more realistic negative training instances. This fundamentally resolves the discrepancy between the data distribution used in the training and testing of DR. In our experiments, ANCE boosts the BERT-Siamese DR model to outperform all competitive dense and sparse retrieval baselines. It nearly matches the accuracy of sparse-retrieval-and-BERT-reranking using dot-product in the ANCE-learned representation space and provides almost 100x speed-up.
Triple Scissor Extender: A 6-DOF Lifting and Positioning Robot
Venue: arXiv cs.RO 2020
Year: 2020

We present a novel 6 DOF robotic mechanism for reaching high ceilings and positioning an end-effector. The end-effector is supported with three scissor mechanisms that extend towards the ceiling with 6 independent linear actuators moving the base ends of the individual scissors. The top point of each scissor is connected to one of three ball joints located at the three vertices of the top triangular plate holding the end-effector. Coordinated motion of the 6 linear actuators at the base allows the end-effector to reach an arbitrary position with an arbitrary orientation. The design concept of the Triple Scissor Extender is presented, followed by kinematic modeling and analysis of the the Inverse Jacobian relating actuator velocities to the end-effector velocities. The Inverse Jacobian eigenvalues are determined for diverse configurations in order to characterize the kinematic properties. A proof-of-concept prototype has been designed and built. The Inverse Jacobian for use in differential control is evaluated through experiments.
Efficient Document Exchange and Error Correcting Codes with Asymmetric Information
Venue: arXiv cs.CC 2020
Year: 2020

We study two fundamental problems in communication, Document Exchange (DE) and Error Correcting Code (ECC). In the first problem, two parties hold two strings, and one party tries to learn the other party's string through communication. In the second problem, one party tries to send a message to another party through a noisy channel, by adding some redundant information to protect the message. Two important goals in both problems are to minimize the communication complexity or redundancy, and to design efficient protocols or codes. Both problems have been studied extensively. In this paper we study whether asymmetric partial information can help in these two problems. We focus on the case of Hamming distance/errors, and the asymmetric partial information is modeled by one party having a vector of disjoint subsets $\vec{S}=(S_1, \cdots, S_t)$ of indices and a vector of integers $\vec{k}=(k_1, \cdots, k_t)$, such that in each $S_i$ the Hamming distance/errors is at most $k_i$. We establish both lower bounds and upper bounds in this model, and provide efficient randomized constructions that achieve a $\min\lbrace O(t^2), O\left((\log \log n)^2\right) \rbrace $ factor within the optimum, with almost linear running time. We further show a connection between the above document exchange problem and the problem of document exchange under edit distance, and use our techniques to give an efficient randomized protocol with optimal communication complexity and \emph{exponentially} small error for the latter. This improves the previous result by Haeupler \cite{haeupler2018optimal} (FOCS'19) and that by Belazzougui and Zhang \cite{BelazzouguiZ16} (FOCS'16). Our techniques are based on a generalization of the celebrated expander codes by Sipser and Spielman \cite{sipser1996expander}, which may be of independent interests.
Image Analysis Based on Nonnegative/Binary Matrix Factorization
Venue: arXiv cs.CV 2020
Year: 2020

Using nonnegative/binary matrix factorization (NBMF), a matrix can be decomposed into a nonnegative matrix and a binary matrix. Our analysis of facial images, based on NBMF and using the Fujitsu Digital Annealer, leads to successful image reconstruction and image classification. The NBMF algorithm converges in fewer iterations than those required for the convergence of nonnegative matrix factorization (NMF), although both techniques perform comparably in image classification.
Guidance of Agents in Cyclic Pursuit
Venue: arXiv cs.RO 2020
Year: 2020

This report studies the emergent behavior of systems of agents performing cyclic pursuit controlled by an external broadcast signal detected by a random set of the agents. Two types of cyclic pursuit are analyzed: 1)linear cyclic pursuit, where each agent senses the relative position of its target or leading agent 2)non-linear cyclic pursuit, where the agents can sense only bearing to their leading agent and colliding agents merge and continue on the path of the pursued agent (a so-called "bugs" model). Cyclic pursuit is, in both cases, a gathering algorithm, which has been previously analyzed. The novelty of our work is the derivation of emergent behaviours, in both linear and non-linear cyclic pursuit, in the presence of an exogenous broadcast control detected by a random subset of agents. We show that the emergent behavior of the swarm depends on the type of cyclic pursuit. In the linear case, the agents asymptotically align in the desired direction and move with a common speed which is a proportional to the ratio of the number of agents detecting the broadcast control to the total number of agents in the swarm, for any magnitude of input (velocity) signal. In the non-linear case, the agents gather and move with a shared velocity, which equals the input velocity signal, independently of the number of agents detecting the broadcast signal.
Gravity: a blockchain-agnostic cross-chain communication and data oracles protocol
Venue: arXiv cs.CR 2020
Year: 2020

This paper intends to propose the architecture of a blockchain-agnostic protocol designed for communication of blockchains amongst each other (i.e. cross-chain), and for blockchains with the outside world (i.e. data oracles). The expansive growth of cutting-edge technology in the blockchain industry outlines the need and opportunity for addressing oracle consensus in a manner both technologically and economically efficient as well as futureproof. Blockchain-agnosticism is inherently limited if proposing a technological solution involves adding one more architectural layer. As such, Gravity protocol is designed to be a truly blockchain-agnostic protocol. By ensuring parity through direct integration and by leveraging the stability and security of the respective interconnected ecosystems, Gravity circumvents the need for a dedicated, public blockchain and a native token. Ultimately, Gravity protocol intends to address scalability challenges by providing a solid infrastructure for the creation of gateways, cross-chain applications, and sidechains. This paper introduces and defines the concept of Oracle Consensus and its implementation in the Gravity protocol named the Pulse Consensus algorithm. The proposed consensus architecture allows Gravity to be considered a singular decentralized blockchain-agnostic oracle.
Hunting for Re-Entrancy Attacks in Ethereum Smart Contracts via Static Analysis
Venue: arXiv cs.CR 2020
Year: 2020

Ethereum smart contracts are programs that are deployed and executed in a consensus-based blockchain managed by a peer-to-peer network. Several re-entrancy attacks that aim to steal Ether, the cryptocurrency used in Ethereum, stored in deployed smart contracts have been found in the recent years. A countermeasure to such attacks is based on dynamic analysis that executes the smart contracts themselves, but it requires the spending of Ether and knowledge of attack patterns for analysis in advance. In this paper, we present a static analysis tool named \textit{RA (Re-entrancy Analyzer)}, a combination of symbolic execution and equivalence checking by a satisfiability modulo theories solver to analyze smart contract vulnerabilities to re-entrancy attacks. In contrast to existing tools, RA supports analysis of inter-contract behaviors by using only the Etherum Virtual Machine bytecodes of target smart contracts, i.e., even without prior knowledge of attack patterns and without spending Ether. Furthermore, RA can verify existence of vulnerabilities to re-entrancy attacks without execution of smart contracts and it does not provide false positives and false negatives. We also present an implementation of RA to evaluate its performance in analyzing the vulnerability of deployed smart contracts to re-entrancy attacks and show that RA can precisely determine which smart contracts are vulnerable.
Estimating Blink Probability for Highlight Detection in Figure Skating Videos
Venue: arXiv cs.CV 2020
Year: 2020

Highlight detection in sports videos has a broad viewership and huge commercial potential. It is thus imperative to detect highlight scenes more suitably for human interest with high temporal accuracy. Since people instinctively suppress blinks during attention-grabbing events and synchronously generate blinks at attention break points in videos, the instantaneous blink rate can be utilized as a highly accurate temporal indicator of human interest. Therefore, in this study, we propose a novel, automatic highlight detection method based on the blink rate. The method trains a one-dimensional convolution network (1D-CNN) to assess blink rates at each video frame from the spatio-temporal pose features of figure skating videos. Experiments show that the method successfully estimates the blink rate in 94% of the video clips and predicts the temporal change in the blink rate around a jump event with high accuracy. Moreover, the method detects not only the representative athletic action, but also the distinctive artistic expression of figure skating performance as key frames. This suggests that the blink-rate-based supervised learning approach enables high-accuracy highlight detection that more closely matches human sensibility.
An ensemble learning framework based on group decision making
Venue: arXiv cs.LG 2020
Year: 2020

The classification problem is a significant topic in machine learning which aims to teach machines how to group together data by particular criteria. In this paper, a framework for the ensemble learning (EL) method based on group decision making (GDM) has been proposed to resolve this issue. In this framework, base learners can be considered as decision-makers, different categories can be seen as alternatives, classification results obtained by diverse base learners can be considered as performance ratings, and the precision, recall, and accuracy which can reflect the performances of the classification methods can be employed to identify the weights of decision-makers in GDM. Moreover, considering that the precision and recall defined in binary classification problems can not be used directly in the multi-classification problem, the One vs Rest (OvR) has been proposed to obtain the precision and recall of the base learner for each category. The experimental results demonstrate that the proposed EL method based on GDM has higher accuracy than other 6 current popular classification methods in most instances, which verifies the effectiveness of the proposed method.
Processing South Asian Languages Written in the Latin Script: the Dakshina Dataset
Venue: arXiv cs.CL 2020
Year: 2020

This paper describes the Dakshina dataset, a new resource consisting of text in both the Latin and native scripts for 12 South Asian languages. The dataset includes, for each language: 1) native script Wikipedia text; 2) a romanization lexicon; and 3) full sentence parallel data in both a native script of the language and the basic Latin alphabet. We document the methods used for preparation and selection of the Wikipedia text in each language; collection of attested romanizations for sampled lexicons; and manual romanization of held-out sentences from the native script collections. We additionally provide baseline results on several tasks made possible by the dataset, including single word transliteration, full sentence transliteration, and language modeling of native script and romanized text. Keywords: romanization, transliteration, South Asian languages
Software Engineering Event Modeling using Relative Time in Temporal Knowledge Graphs
Venue: arXiv cs.LG 2020
Year: 2020

We present a multi-relational temporal Knowledge Graph based on the daily interactions between artifacts in GitHub, one of the largest social coding platforms. Such representation enables posing many user-activity and project management questions as link prediction and time queries over the knowledge graph. In particular, we introduce two new datasets for i) interpolated time-conditioned link prediction and ii) extrapolated time-conditioned link/time prediction queries, each with distinguished properties. Our experiments on these datasets highlight the potential of adapting knowledge graphs to answer broad software engineering questions. Meanwhile, it also reveals the unsatisfactory performance of existing temporal models on extrapolated queries and time prediction queries in general. To overcome these shortcomings, we introduce an extension to current temporal models using relative temporal information with regards to past events.
Globally Optimal Segmentation of Mutually Interacting Surfaces using Deep Learning
Venue: arXiv cs.CV 2020
Year: 2020

Segmentation of multiple surfaces in medical images is a challenging problem, further complicated by the frequent presence of weak boundary and mutual influence between adjacent objects. The traditional graph-based optimal surface segmentation method has proven its effectiveness with its ability of capturing various surface priors in a uniform graph model. However, its efficacy heavily relies on handcrafted features that are used to define the surface cost for the "goodness" of a surface. Recently, deep learning (DL) is emerging as powerful tools for medical image segmentation thanks to its superior feature learning capability. Unfortunately, due to the scarcity of training data in medical imaging, it is nontrivial for DL networks to implicitly learn the global structure of the target surfaces, including surface interactions. In this work, we propose to parameterize the surface cost functions in the graph model and leverage DL to learn those parameters. The multiple optimal surfaces are then simultaneously detected by minimizing the total surface cost while explicitly enforcing the mutual surface interaction constraints. The optimization problem is solved by the primal-dual Internal Point Method, which can be implemented by a layer of neural networks, enabling efficient end-to-end training of the whole network. Experiments on Spectral Domain Optical Coherence Tomography (SD-OCT) retinal layer segmentation and Intravascular Ultrasound (IVUS) vessel wall segmentation demonstrated very promising results. All source code is public to facilitate further research at this direction.
Automatic Horizontal Fusion for GPU Kernels
Venue: arXiv cs.DC 2020
Year: 2020

We present automatic horizontal fusion, a novel optimization technique that complements the standard kernel fusion techniques for GPU programs. Unlike the standard fusion, whose goal is to eliminate intermediate data round trips, our horizontal fusion technique aims to increase the thread-level parallelism to hide instruction latencies. We also present HFuse, a new source to source CUDA compiler that implements automatic horizontal fusion. Our experimental results show that horizontal fusion can speed up the running time by 2.5%-60.8%. Our results reveal that the horizontal fusion is especially beneficial for fusing kernels with instructions that require different kinds of GPU resources (e.g., a memory-intensive kernel and a compute-intensive kernel).
Smt-Switch: a solver-agnostic C++ API for SMT Solving
Venue: arXiv cs.LO 2020
Year: 2020

This extended abstract describes work in progress on Smt-Switch, an open-source, solver-agnostic API for SMT solving. Smt-Switch provides an abstract interface, which can be implemented by different SMT solvers. Smt-Switch provides simple, uniform, and high-performance access to SMT solving for applications in areas such as automated reasoning, planning, and formal verification. The interface allows the user to create, traverse, and manipulate terms, as well as to dynamically dispatch queries to different underlying SMT solvers.
Secure Beamforming and Ergodic Secrecy Rate Analysis for Amplify-and-Forward Relay Networks with Wireless Powered Jammer
Venue: arXiv cs.IT 2020
Year: 2020

In this correspondence, we consider an amplify-and-forward relay network in which relayed information is overheard by an eavesdropper. In order to confound the eavesdropper, a wireless-powered jammer is also considered which harvests energy from a multiple-antenna source. We proposed a new secure beamforming scheme in which beamforming vector is a linear combination of the energy beamforming (EB) and information beamforming (IB) vectors. We also present a new closed-form solution for the proposed beamforming vector which is shown to achieve a higher secrecy rate as compared to the trivial EB and IB vectors. Moreover, a tight closed-form approximation for the ergodic secrecy rate is also derived for the asymptotic regime of a large number of antennas at the source. Finally, numerical examples and simulations are provided which validate our analytical results.