OpenRaiser/Intern-Atlas huggingface dataset:
Beat Detection and Automatic Annotation of the Music of Bharatanatyam Dance using Speech Recognition Techniques
Venue: arXiv cs.SD 2020
Year: 2020

Bharatanatyam, an Indian Classical Dance form, represents the rich cultural heritage of India. Analysis and recognition of such dance forms are critical for the preservation of cultural heritage. Like in most dance forms, a Bharatanatyam dancer performs in synchronization with structured rhythmic music, called Sollukattu, which comprises instrumental beats and vocalized utterances (bols) to create a rhythmic music structure. Computer analysis of Bharatanatyam, therefore, requires a structural analysis of Sollukattus. In this paper, we use speech processing techniques to recognize bols. Exploiting the predefined structures of Sollukattus and the detected bols, we recognize the Sollukattu. We estimate the tempo period by two methods. Finally, we generate a complete annotation of the audio signal by beat marking. For this, we also use the information of beats detected from the onset envelope of a Sollukattu signal. For training and test, we create a data set for Sollukattus and annotate them. We achieve 85% accuracy in bol recognition, 95% in Sollukattu recognition, 96% in tempo period estimation, and over 90% in beat marking. This is the maiden attempt to fully structurally analyze the music of an Indian Classical Dance form and the use of speech processing techniques for beat marking.
Finding Small Proofs for Description Logic Entailments: Theory and Practice (Extended Technical Report)
Venue: arXiv cs.LO 2020
Year: 2020

Logic-based approaches to AI have the advantage that their behaviour can in principle be explained by providing their users with proofs for the derived consequences. However, if such proofs get very large, then it may be hard to understand a consequence even if the individual derivation steps are easy to comprehend. This motivates our interest in finding small proofs for Description Logic (DL) entailments. Instead of concentrating on a specific DL and proof calculus for this DL, we introduce a general framework in which proofs are represented as labeled, directed hypergraphs, where each hyperedge corresponds to a single sound derivation step. On the theoretical side, we investigate the complexity of deciding whether a certain consequence has a proof of size at most $n$ along the following orthogonal dimensions: (i) the underlying proof system is polynomial or exponential; (ii) proofs may or may not reuse already derived consequences; and (iii) the number $n$ is represented in unary or binary. We have determined the exact worst-case complexity of this decision problem for all but one of the possible combinations of these options. On the practical side, we have developed and implemented an approach for generating proofs for expressive DLs based on a non-standard reasoning task called forgetting. We have evaluated this approach on a set of realistic ontologies and compared the obtained proofs with proofs generated by the DL reasoner ELK, finding that forgetting-based proofs are often better w.r.t. different measures of proof complexity.
Motion and Region Aware Adversarial Learning for Fall Detection with Thermal Imaging
Venue: arXiv cs.CV 2020
Year: 2020

Automatic fall detection is a vital technology for ensuring the health and safety of people. Home-based camera systems for fall detection often put people's privacy at risk. Thermal cameras can partially or fully obfuscate facial features, thus preserving the privacy of a person. Another challenge is the less occurrence of falls in comparison to the normal activities of daily living. As fall occurs rarely, it is non-trivial to learn algorithms due to class imbalance. To handle these problems, we formulate fall detection as an anomaly detection within an adversarial framework using thermal imaging. We present a novel adversarial network that comprises of two-channel 3D convolutional autoencoders which reconstructs the thermal data and the optical flow input sequences respectively. We introduce a technique to track the region of interest, a region-based difference constraint, and a joint discriminator to compute the reconstruction error. A larger reconstruction error indicates the occurrence of a fall. The experiments on a publicly available thermal fall dataset show the superior results obtained compared to the standard baseline.
Low-stretch spanning trees of graphs with bounded width
Venue: arXiv cs.DS 2020
Year: 2020

We study the problem of low-stretch spanning trees in graphs of bounded width: bandwidth, cutwidth, and treewidth. We show that any simple connected graph $G$ with a linear arrangement of bandwidth $b$ can be embedded into a distribution $\mathcal T$ of spanning trees such that the expected stretch of each edge of $G$ is $O(b^2)$. Our proof implies a linear time algorithm for sampling from $\mathcal T$. Therefore, we have a linear time algorithm that finds a spanning tree of $G$ with average stretch $O(b^2)$ with high probability. We also describe a deterministic linear-time algorithm for computing a spanning tree of $G$ with average stretch $O(b^3)$. For graphs of cutwidth $c$, we construct a spanning tree with stretch $O(c^2)$ in linear time. Finally, when $G$ has treewidth $k$ we provide a dynamic programming algorithm computing a minimum stretch spanning tree of $G$ that runs in polynomial time with respect to the number of vertices of $G$.
Fitting the Search Space of Weight-sharing NAS with Graph Convolutional Networks
Venue: arXiv cs.LG 2020
Year: 2020

Neural architecture search has attracted wide attentions in both academia and industry. To accelerate it, researchers proposed weight-sharing methods which first train a super-network to reuse computation among different operators, from which exponentially many sub-networks can be sampled and efficiently evaluated. These methods enjoy great advantages in terms of computational costs, but the sampled sub-networks are not guaranteed to be estimated precisely unless an individual training process is taken. This paper owes such inaccuracy to the inevitable mismatch between assembled network layers, so that there is a random error term added to each estimation. We alleviate this issue by training a graph convolutional network to fit the performance of sampled sub-networks so that the impact of random errors becomes minimal. With this strategy, we achieve a higher rank correlation coefficient in the selected set of candidates, which consequently leads to better performance of the final architecture. In addition, our approach also enjoys the flexibility of being used under different hardware constraints, since the graph convolutional network has provided an efficient lookup table of the performance of architectures in the entire search space.
Automated System Performance Testing at MongoDB
Venue: arXiv cs.DB 2020
Year: 2020

Distributed Systems Infrastructure (DSI) is MongoDB's framework for running fully automated system performance tests in our Continuous Integration (CI) environment. To run in CI it needs to automate everything end-to-end: provisioning and deploying multi-node clusters, executing tests, tuning the system for repeatable results, and collecting and analyzing the results. Today DSI is MongoDB's most used and most useful performance testing tool. It runs almost 200 different benchmarks in daily CI, and we also use it for manual performance investigations. As we can alert the responsible engineer in a timely fashion, all but one of the major regressions were fixed before the 4.2.0 release. We are also able to catch net new improvements, of which DSI caught 17. We open sourced DSI in March 2020.
A Weighted Population Update Rule for PACO Applied to the Single Machine Total Weighted Tardiness Problem
Venue: arXiv cs.NE 2020
Year: 2020

In this paper a new population update rule for population based ant colony optimization (PACO) is proposed. PACO is a well known alternative to the standard ant colony optimization algorithm. The new update rule allows to weight different parts of the solutions. PACO with the new update rule is evaluated for the example of the single machine total weighted tardiness problem (SMTWTP). This is an $\mathcal{NP}$-hard optimization problem where the aim is to schedule jobs on a single machine such that their total weighted tardiness is minimized. PACO with the new population update rule is evaluated with several benchmark instances from the OR-Library. Moreover, the impact of the weights of the jobs on the solutions in the population and on the convergence of the algorithm are analyzed experimentally. The results show that PACO with the new update rule has on average better solution quality than PACO with the standard update rule.
Lidar for Autonomous Driving: The principles, challenges, and trends for automotive lidar and perception systems
Venue: arXiv cs.RO 2020
Year: 2020

Autonomous vehicles rely on their perception systems to acquire information about their immediate surroundings. It is necessary to detect the presence of other vehicles, pedestrians and other relevant entities. Safety concerns and the need for accurate estimations have led to the introduction of Light Detection and Ranging (LiDAR) systems in complement to the camera or radar-based perception systems. This article presents a review of state-of-the-art automotive LiDAR technologies and the perception algorithms used with those technologies. LiDAR systems are introduced first by analyzing the main components, from laser transmitter to its beam scanning mechanism. Advantages/disadvantages and the current status of various solutions are introduced and compared. Then, the specific perception pipeline for LiDAR data processing, from an autonomous vehicle perspective is detailed. The model-driven approaches and the emerging deep learning solutions are reviewed. Finally, we provide an overview of the limitations, challenges and trends for automotive LiDARs and perception systems.
A Simple, General, and GPU Friendly Method for Computing Dual Mesh and Iso-Surfaces of Adaptive Mesh Refinement (AMR) Data
Venue: arXiv cs.GR 2020
Year: 2020

We propose a novel approach to extracting crack-free iso-surfaces from Structured AMR data that is more general than previous techniques, is trivially simple to implement, requires no information other than the list of AMR cells, and works, in particular, for different AMR formats including octree AMR, block-structured AMR with arbitrary level differences at level boundaries, and AMR data that consist of individual cells without any existing grid structure. We describe both the technique itself and a CUDA-based GPU implementation of this technique, and evaluate it on several non-trivial AMR data sets.
A Formal Hierarchy of RNN Architectures
Venue: arXiv cs.CL 2020
Year: 2020

We develop a formal hierarchy of the expressive capacity of RNN architectures. The hierarchy is based on two formal properties: space complexity, which measures the RNN's memory, and rational recurrence, defined as whether the recurrent update can be described by a weighted finite-state machine. We place several RNN variants within this hierarchy. For example, we prove the LSTM is not rational, which formally separates it from the related QRNN (Bradbury et al., 2016). We also show how these models' expressive capacity is expanded by stacking multiple layers or composing them with different pooling functions. Our results build on the theory of "saturated" RNNs (Merrill, 2019). While formally extending these findings to unsaturated RNNs is left to future work, we hypothesize that the practical learnable capacity of unsaturated RNNs obeys a similar hierarchy. Experimental findings from training unsaturated networks on formal languages support this conjecture.
Accurate Tumor Tissue Region Detection with Accelerated Deep Convolutional Neural Networks
Venue: arXiv cs.CV 2020
Year: 2020

Manual annotation of pathology slides for cancer diagnosis is laborious and repetitive. Therefore, much effort has been devoted to develop computer vision solutions. Our approach, (FLASH), is based on a Deep Convolutional Neural Network (DCNN) architecture. It reduces computational costs and is faster than typical deep learning approaches by two orders of magnitude, making high throughput processing a possibility. In computer vision approaches using deep learning methods, the input image is subdivided into patches which are separately passed through the neural network. Features extracted from these patches are used by the classifier to annotate the corresponding region. Our approach aggregates all the extracted features into a single matrix before passing them to the classifier. Previously, the features are extracted from overlapping patches. Aggregating the features eliminates the need for processing overlapping patches, which reduces the computations required. DCCN and FLASH demonstrate high sensitivity (~ 0.96), good precision (~0.78) and high F1 scores (~0.84). The average time taken to process each sample for FLASH and DCNN is 96.6 seconds and 9489.20 seconds, respectively. Our approach was approximately 100 times faster than the original DCNN approach while simultaneously preserving high accuracy and precision.
sFuzz: An Efficient Adaptive Fuzzer for Solidity Smart Contracts
Venue: arXiv cs.SE 2020
Year: 2020

Smart contracts are Turing-complete programs that execute on the infrastructure of the blockchain, which often manage valuable digital assets. Solidity is one of the most popular programming languages for writing smart contracts on the Ethereum platform. Like traditional programs, smart contracts may contain vulnerabilities. Unlike traditional programs, smart contracts cannot be easily patched once they are deployed. It is thus important that smart contracts are tested thoroughly before deployment. In this work, we present an adaptive fuzzer for smart contracts on the Ethereum platform called sFuzz. Compared to existing Solidity fuzzers, sFuzz combines the strategy in the AFL fuzzer and an efficient lightweight multi-objective adaptive strategy targeting those hard-to-cover branches. sFuzz has been applied to more than 4 thousand smart contracts and the experimental results show that (1) sFuzz is efficient, e.g., two orders of magnitude faster than state-of-the-art tools; (2) sFuzz is effective in achieving high code coverage and discovering vulnerabilities; and (3) the different fuzzing strategies in sFuzz complement each other.
Remote Empirical Coordination
Venue: arXiv cs.IT 2020
Year: 2020

We apply the framework of imperfect empirical coordination to a two-node setup where the action $X$ of the first node is not observed directly but via $L$ agents who observe independently impaired measurements $\hat X$ of the action. These $L$ agents, using a rate-limited communication that is available to all of them, help the second node to generate the action $Y$ in order to establish the desired coordinated behaviour. When $L<\infty$, we prove that it suffices $R_i\geq I\left(\hat X;\hat{Y}\right)$ for at least one agent whereas for $L\longrightarrow\infty$, we show that it suffices $R_i\geq I\left(\hat X;\hat Y|X\right)$ for all agents where $\hat Y$ is a random variable such that $X-\hat X-\hat Y$ and $\|p_{X,\hat Y}\left(x,y\right)-p_{X,Y}\left(x,y\right)\|_{TV}\leq Δ$ ( $Δ$ is the pre-specified fidelity).
Feathers dataset for Fine-Grained Visual Categorization
Venue: arXiv cs.CV 2020
Year: 2020

This paper introduces a novel dataset FeatherV1, containing 28,272 images of feathers categorized by 595 bird species. It was created to perform taxonomic identification of bird species by a single feather, which can be applied in amateur and professional ornithology. FeatherV1 is the first publicly available bird's plumage dataset for machine learning, and it can raise interest for a new task in fine-grained visual recognition domain. The latest version of the dataset can be downloaded at https://github.com/feathers-dataset/feathersv1-dataset. We also present feathers classification task results. We selected several deep learning architectures (DenseNet based) for categorical crossentropy values comparison on the provided dataset.
The $(1+(λ,λ))$ Genetic Algorithm for Permutations
Venue: arXiv cs.NE 2020
Year: 2020

The $(1+(λ,λ))$ genetic algorithm is a bright example of an evolutionary algorithm which was developed based on the insights from theoretical findings. This algorithm uses crossover, and it was shown to asymptotically outperform all mutation-based evolutionary algorithms even on simple problems like OneMax. Subsequently it was studied on a number of other problems, but all of these were pseudo-Boolean. We aim at improving this situation by proposing an adaptation of the $(1+(λ,λ))$ genetic algorithm to permutation-based problems. Such an adaptation is required, because permutations are noticeably different from bit strings in some key aspects, such as the number of possible mutations and their mutual dependence. We also present the first runtime analysis of this algorithm on a permutation-based problem called Ham whose properties resemble those of OneMax. On this problem, where the simple mutation-based algorithms have the running time of $Θ(n^2 \log n)$ for problem size $n$, the $(1+(λ,λ))$ genetic algorithm finds the optimum in $O(n^2)$ fitness queries. We augment this analysis with experiments, which show that this algorithm is also fast in practice.
A Critical Review of Concepts, Benefits, and Pitfalls of Blockchain Technology Using Concept Map
Venue: arXiv cs.SE 2020
Year: 2020

Blockchain is relatively a new area of research. However, a surge of research studies on the blockchain has taken place in recent years. These research studies have mostly focused on designing and developing conceptual frameworks to build more reliable, transparent and efficient digital systems. While blockchain brings a wide variety of benefits, it also imposes certain challenges. Therefore, the objective of this research is to understand the properties of blockchain, its current uses, observed benefits and pitfalls to provide a balanced understanding of blockchain. A systematic literature review approach was adopted in this paper in order to attain the objective. A total of 51 articles were selected and reviewed. As outcomes, this research provides a summary of the state-of-the-art research studies conducted in the area of blockchain. Furthermore, we develop a set of concept maps aiming to provide in-depth knowledge on blockchain technology for its efficient and effective usage in the development of future technological solutions.
A Hybrid Approach for Aspect-Based Sentiment Analysis Using Deep Contextual Word Embeddings and Hierarchical Attention
Venue: arXiv cs.CL 2020
Year: 2020

The Web has become the main platform where people express their opinions about entities of interest and their associated aspects. Aspect-Based Sentiment Analysis (ABSA) aims to automatically compute the sentiment towards these aspects from opinionated text. In this paper we extend the state-of-the-art Hybrid Approach for Aspect-Based Sentiment Analysis (HAABSA) method in two directions. First we replace the non-contextual word embeddings with deep contextual word embeddings in order to better cope with the word semantics in a given text. Second, we use hierarchical attention by adding an extra attention layer to the HAABSA high-level representations in order to increase the method flexibility in modeling the input data. Using two standard datasets (SemEval 2015 and SemEval 2016) we show that the proposed extensions improve the accuracy of the built model for ABSA.
Detecting Centralized Architecture-Based Botnets using Travelling Salesperson Non-Deterministic Polynomial-Hard problem, TSP-NP Technique
Venue: arXiv cs.CR 2020
Year: 2020

The threats posed by botnets in the cyberspace continue to grow each day and it has become very hard to detect or infiltrate the cynicism of bots. This, is owing to the fact, that, the botnet developers each day, keep changing the propagation and attack techniques. Currently, most of these attacks have been centered on stealing computing energy, theft of personal information and Distributed Denial of Service (DDoS) attacks. In this paper, the authors propose a novel technique that uses the Non-Deterministic Polynomial-Time Hardness (NP-Hard Problem) based on the Traveling Salesperson Person (TSP) that depicts that a given bot, bj, is able to visit each host on a network environment, NE, and then it returns to the botmaster, in form of instruction(command), through optimal minimization of the hosts that are (may) be attacked. Given that bj represents a piece of malicious code and TSP-NP Hard Problem, which forms part of combinatorial optimization, the authors present this as an effective approach for the detection of the botnet. It is worth noting that the concentration of this study is basically on the centralized botnet architecture. This holistic approach shows that botnet detection accuracy can be increased with a degree of certainty and potentially decrease the chances of false positives. Nevertheless, a discussion on the possible applicability and implementation has also been given in this paper.
Zeus: A System Description of the Two-Time Winner of the Collegiate SAE AutoDrive Competition
Venue: arXiv cs.RO 2020
Year: 2020

The SAE AutoDrive Challenge is a three-year collegiate competition to develop a self-driving car by 2020. The second year of the competition was held in June 2019 at MCity, a mock town built for self-driving car testing at the University of Michigan. Teams were required to autonomously navigate a series of intersections while handling pedestrians, traffic lights, and traffic signs. Zeus is aUToronto's winning entry in the AutoDrive Challenge. This article describes the system design and development of Zeus as well as many of the lessons learned along the way. This includes details on the team's organizational structure, sensor suite, software components, and performance at the Year 2 competition. With a team of mostly undergraduates and minimal resources, aUToronto has made progress towards a functioning self-driving vehicle, in just two years. This article may prove valuable to researchers looking to develop their own self-driving platform.
Heterogeneous CPU+GPU Stochastic Gradient Descent Algorithms
Venue: arXiv cs.DC 2020
Year: 2020

The widely-adopted practice is to train deep learning models with specialized hardware accelerators, e.g., GPUs or TPUs, due to their superior performance on linear algebra operations. However, this strategy does not employ effectively the extensive CPU and memory resources -- which are used only for preprocessing, data transfer, and scheduling -- available by default on the accelerated servers. In this paper, we study training algorithms for deep learning on heterogeneous CPU+GPU architectures. Our two-fold objective -- maximize convergence rate and resource utilization simultaneously -- makes the problem challenging. In order to allow for a principled exploration of the design space, we first introduce a generic deep learning framework that exploits the difference in computational power and memory hierarchy between CPU and GPU through asynchronous message passing. Based on insights gained through experimentation with the framework, we design two heterogeneous asynchronous stochastic gradient descent (SGD) algorithms. The first algorithm -- CPU+GPU Hogbatch -- combines small batches on CPU with large batches on GPU in order to maximize the utilization of both resources. However, this generates an unbalanced model update distribution which hinders the statistical convergence. The second algorithm -- Adaptive Hogbatch -- assigns batches with continuously evolving size based on the relative speed of CPU and GPU. This balances the model updates ratio at the expense of a customizable decrease in utilization. We show that the implementation of these algorithms in the proposed CPU+GPU framework achieves both faster convergence and higher resource utilization than TensorFlow on several real datasets and on two computing architectures -- an on-premises server and a cloud instance.