OpenRaiser/Intern-Atlas huggingface dataset:
Zipf's law in 50 languages: its structural pattern, linguistic interpretation, and cognitive motivation
Venue: arXiv cs.CL 2018
Year: 2018

Zipf's law has been found in many human-related fields, including language, where the frequency of a word is persistently found as a power law function of its frequency rank, known as Zipf's law. However, there is much dispute whether it is a universal law or a statistical artifact, and little is known about what mechanisms may have shaped it. To answer these questions, this study conducted a large scale cross language investigation into Zipf's law. The statistical results show that Zipf's laws in 50 languages all share a 3-segment structural pattern, with each segment demonstrating distinctive linguistic properties and the lower segment invariably bending downwards to deviate from theoretical expectation. This finding indicates that this deviation is a fundamental and universal feature of word frequency distributions in natural languages, not the statistical error of low frequency words. A computer simulation based on the dual-process theory yields Zipf's law with the same structural pattern, suggesting that Zipf's law of natural languages are motivated by common cognitive mechanisms. These results show that Zipf's law in languages is motivated by cognitive mechanisms like dual-processing that govern human verbal behaviors.
Chinese Lexical Analysis with Deep Bi-GRU-CRF Network
Venue: arXiv cs.CL 2018
Year: 2018

Lexical analysis is believed to be a crucial step towards natural language understanding and has been widely studied. Recent years, end-to-end lexical analysis models with recurrent neural networks have gained increasing attention. In this report, we introduce a deep Bi-GRU-CRF network that jointly models word segmentation, part-of-speech tagging and named entity recognition tasks. We trained the model using several massive corpus pre-tagged by our best Chinese lexical analysis tool, together with a small, yet high-quality human annotated corpus. We conducted balanced sampling between different corpora to guarantee the influence of human annotations, and fine-tune the CRF decoding layer regularly during the training progress. As evaluated by linguistic experts, the model achieved a 95.5% accuracy on the test set, roughly 13% relative error reduction over our (previously) best Chinese lexical analysis tool. The model is computationally efficient, achieving the speed of 2.3K characters per second with one thread.
Denoising Auto-encoder with Recurrent Skip Connections and Residual Regression for Music Source Separation
Venue: arXiv cs.SD 2018
Year: 2018

Convolutional neural networks with skip connections have shown good performance in music source separation. In this work, we propose a denoising Auto-encoder with Recurrent skip Connections (ARC). We use 1D convolution along the temporal axis of the time-frequency feature map in all layers of the fully-convolutional network. The use of 1D convolution makes it possible to apply recurrent layers to the intermediate outputs of the convolution layers. In addition, we also propose an enhancement network and a residual regression method to further improve the separation result. The recurrent skip connections, the enhancement module, and the residual regression all improve the separation quality. The ARC model with residual regression achieves 5.74 siganl-to-distoration ratio (SDR) in vocals with MUSDB in SiSEC 2018. We also evaluate the ARC model alone on the older dataset DSD100 (used in SiSEC 2016) and it achieves 5.91 SDR in vocals.
Multi-robot Path Planning in Well-formed Infrastructures: Prioritized Planning vs. Prioritized Wait Adjustment (Preliminary Results)
Venue: arXiv cs.AI 2018
Year: 2018

We study the problem of planning collision-free paths for a group of homogeneous robots. We propose a novel approach for turning the paths that were planned egocentrically by the robots, e.g. without taking other robots' moves into account, into collision-free trajectories and evaluate it empirically. Suggested algorithm is much faster (up to one order of magnitude) than state-of-the-art but this comes at the price of notable drop-down of the solution cost.
FocusST Solution for Analysis of Cryptographic Properties
Venue: arXiv cs.SE 2018
Year: 2018

To analyse cryptographic properties of distributed systems in a systematic way, a formal theory is required. In this paper, we present a theory that allows (1) to specify distributed systems formally, (2) to verify their cryptographic wrt. composition properties, and (3) to demonstrate the correctness of syntactic interfaces for specified system components automatically. To demonstrate the feasibility of the approach we use a typical example from the domain of crypto-based systems: a variant of the Internet security protocol TLS. A security flaw in the initial version of TLS specification was revealed using a semi-automatic theorem prover, Isabelle/HOL.
Low Overhead Weighted-Graph-Coloring-Based Two-Layer Precoding for FDD Massive MIMO Systems
Venue: arXiv cs.IT 2018
Year: 2018

A massive multiple-input multiple-output (MIMO) system, operating in Frequency Division Duplexing (FDD) mode of operation, suffers from prohibitively high overhead associated with downlink channel state information (CSI) acquisition and downlink precoding, due to the lack of uplink/downlink channel reciprocity. In this paper, a heuristic edge-weighted vertex-coloring based pattern division (EWVC-PD) scheme is proposed to alleviate the overhead of a two-layer precoding approach, in a practical scenario where the user clusters undergo serious angular-spreading-range (ASR) overlapping. Specifically, under a constraint of limited number of subchannels, an undirected edge-weighted graph (EWG) is firstly constructed, to depict the potential ASR overlapping relationship among clusters. Then, inspired by classical graph coloring algorithms, we develop the EWVC-PD scheme which mitigate the ASR by subchannel orthogonalization between clusters possessing serious ASR overlapping, and multiplexing the ones having slight ASR overlapping. Simulation results reveal that our scheme efficiently outperforms the existing pattern division schemes.
Acquire, Augment, Segment & Enjoy: Weakly Supervised Instance Segmentation of Supermarket Products
Venue: arXiv cs.CV 2018
Year: 2018

Grocery stores have thousands of products that are usually identified using barcodes with a human in the loop. For automated checkout systems, it is necessary to count and classify the groceries efficiently and robustly. One possibility is to use a deep learning algorithm for instance-aware semantic segmentation. Such methods achieve high accuracies but require a large amount of annotated training data. We propose a system to generate the training annotations in a weakly supervised manner, drastically reducing the labeling effort. We assume that for each training image, only the object class is known. The system automatically segments the corresponding object from the background. The obtained training data is augmented to simulate variations similar to those seen in real-world setups.
On-Demand Deployment of Multiple Aerial Base Stations for Traffic Offloading and Network Recovery
Venue: arXiv cs.NI 2018
Year: 2018

Unmanned aerial vehicles (UAVs) are being utilized for a wide spectrum of applications in wireless networks leading to attractive business opportunities. In the case of abrupt disruption to existing cellular network operation or infrastructure, e.g., due to an unexpected surge in user demand or a natural disaster, UAVs can be deployed to provide instant recovery via temporary wireless coverage in designated areas. A major challenge is to determine efficiently how many UAVs are needed and where to position them in a relatively large 3D search space. To this end, we formulate the problem of 3D deployment of a fleet of UAVs as a mixed integer linear program, and present a greedy approach that mimics the optimal behavior assuming a grid composed of a finite set of possible UAV locations. In addition, we propose and evaluate a novel low complexity algorithm for multiple UAV deployment in a continuous 3D space, based on an unsupervised learning technique that relies on the notion of electrostatics with repulsion and attraction forces. We present performance results for the proposed algorithm as a function of various system parameters and demonstrate its effectiveness compared to the close-to-optimal greedy approach and its superiority compared to recent related work from the literature.
3D Human Action Recognition with Siamese-LSTM Based Deep Metric Learning
Venue: arXiv cs.CV 2018
Year: 2018

This paper proposes a new 3D Human Action Recognition system as a two-phase system: (1) Deep Metric Learning Module which learns a similarity metric between two 3D joint sequences using Siamese-LSTM networks; (2) A Multiclass Classification Module that uses the output of the first module to produce the final recognition output. This model has several advantages: the first module is trained with a larger set of data because it uses many combinations of sequence pairs.Our deep metric learning module can also be trained independently of the datasets, which makes our system modular and generalizable. We tested the proposed system on standard and newly introduced datasets that showed us that initial results are promising. We will continue developing this system by adding more sophisticated LSTM blocks and by cross-training between different datasets.
Feature Assisted bi-directional LSTM Model for Protein-Protein Interaction Identification from Biomedical Texts
Venue: arXiv cs.IR 2018
Year: 2018

Knowledge about protein-protein interactions is essential in understanding the biological processes such as metabolic pathways, DNA replication, and transcription etc. However, a majority of the existing Protein-Protein Interaction (PPI) systems are dependent primarily on the scientific literature, which is yet not accessible as a structured database. Thus, efficient information extraction systems are required for identifying PPI information from the large collection of biomedical texts. Most of the existing systems model the PPI extraction task as a classification problem and are tailored to the handcrafted feature set including domain dependent features. In this paper, we present a novel method based on deep bidirectional long short-term memory (B-LSTM) technique that exploits word sequences and dependency path related information to identify PPI information from text. This model leverages joint modeling of proteins and relations in a single unified framework, which we name as Shortest Dependency Path B-LSTM (sdpLSTM) model. We perform experiments on two popular benchmark PPI datasets, namely AiMed & BioInfer. The evaluation shows the F1-score values of 86.45% and 77.35% on AiMed and BioInfer, respectively. Comparisons with the existing systems show that our proposed approach attains state-of-the-art performance.
Slytherin: Dynamic, Network-assisted Prioritization of Tail Packets in Datacenter Networks
Venue: arXiv cs.NI 2018
Year: 2018

Datacenter applications demand both low latency and high throughput; while interactive applications (e.g., Web Search) demand low tail latency for their short messages due to their partition-aggregate software architecture, many data-intensive applications (e.g., Map-Reduce) require high throughput for long flows as they move vast amounts of data across the network. Recent proposals improve latency of short flows and throughput of long flows by addressing the shortcomings of existing packet scheduling and congestion control algorithms, respectively. We make the key observation that long tails in the Flow Completion Times (FCT) of short flows result from packets that suffer congestion at more than one switch along their paths in the network. Our proposal, Slytherin, specifically targets packets that suffered from congestion at multiple points and prioritizes them in the network. Slytherin leverages ECN mechanism which is widely used in existing datacenters to identify such tail packets and dynamically prioritizes them using existing priority queues. As compared to existing state-of-the-art packet scheduling proposals, Slytherin achieves 18.6% lower 99th percentile flow completion times for short flows without any loss of throughput. Further, Slytherin drastically reduces 99th percentile queue length in switches by a factor of about 2x on average.
Natural Language Processing for Music Knowledge Discovery
Venue: arXiv cs.CL 2018
Year: 2018

Today, a massive amount of musical knowledge is stored in written form, with testimonies dated as far back as several centuries ago. In this work, we present different Natural Language Processing (NLP) approaches to harness the potential of these text collections for automatic music knowledge discovery, covering different phases in a prototypical NLP pipeline, namely corpus compilation, text-mining, information extraction, knowledge graph generation and sentiment analysis. Each of these approaches is presented alongside different use cases (i.e., flamenco, Renaissance and popular music) where large collections of documents are processed, and conclusions stemming from data-driven analyses are presented and discussed.
OSDF: An Intent-based Software Defined Network Programming Framework
Venue: arXiv cs.NI 2018
Year: 2018

Software Defined Networking (SDN) offers flexibility to program a network based on a set of network requirements. Programming the networks using SDN is not completely straightforward because a programmer must deal with low level details. To solve the problem, researchers proposed a set of network programming languages that provide a set of high level abstractions to hide low level hardware details. Most of the proposed languages provide abstractions related to packet processing and flows, and still require a programmer to specify low-level match-action fields to configure and monitor a network. Recently, in an attempt to raise the level at which programmers work, researchers have begun to investigate Intent-based, descriptive northbound interfaces. The work is still in early stages, and further investigation is required before intent-based systems will be adopted by enterprise networks. To help achieve the goal of moving to an intent-based design, we propose an SDN-based network programming framework, the Open Software Defined Framework (OSDF). OSDF provides a high level Application Programming Interface (API) that can be used by managers and network administrators to express network requirements for applications and policies for multiple domains. OSDF also provides a set of high level network operation services that handle common network configuration, monitoring, and Quality of Service (QoS) provisioning. OSDF is equipped with a policy conflict management module to help a network administrator detect and resolve policy conflicts. The paper shows how OSDF can be used and explains application-based policies. Finally, the paper reports the results of both testbed measurements and simulations that are used to evaluate the framework from multiple perspectives, including functionality and performance.
Building Transmission Backbone for Highway Vehicular Networks: Framework and Analysis
Venue: arXiv cs.NI 2018
Year: 2018

The highway vehicular ad hoc networks, where vehicles are wirelessly inter-connected, rely on the multi-hop transmissions for end-to-end communications. This, however, is severely challenged by the unreliable wireless connections, signal attenuation and channel contentions in the dynamic vehicular environment. To overcome the network dynamics, selecting appropriate relays for end-to-end connections is important. Different from the previous efforts (\emph{e.g.}, clustering and cooperative downloading), this paper explores the existence of stable vehicles and propose building a stable multi-hop transmission backbone network in the highway vehicular ad hoc network. Our work is composed of three parts. Firstly, by analyzing the real-world vehicle traffic traces, we observe that the large-size vehicles, \emph{e.g.}, trucks, are typically stable with low variations of mobility and stable channel condition of low signal attenuation; this makes their inter-connections stable in both connection time and transmission rate. Secondly, by exploring the stable vehicles, we propose a distributed protocol to build a multi-hop backbone link for end-to-end transmissions, accordingly forming a two-tier network architecture in highway vehicular ad hoc networks. Lastly, to show the resulting data performance, we develop a queueing analysis model to evaluate the end-to-end transmission delay and throughput. Using extensive simulations, we show that the proposed transmission backbone can significantly improve the reliability of multi-hop data transmissions with higher throughput, less transmission interruptions and end-to-end delay.
Adversarial Learning for Fine-grained Image Search
Venue: arXiv cs.CV 2018
Year: 2018

Fine-grained image search is still a challenging problem due to the difficulty in capturing subtle differences regardless of pose variations of objects from fine-grained categories. In practice, a dynamic inventory with new fine-grained categories adds another dimension to this challenge. In this work, we propose an end-to-end network, called FGGAN, that learns discriminative representations by implicitly learning a geometric transformation from multi-view images for fine-grained image search. We integrate a generative adversarial network (GAN) that can automatically handle complex view and pose variations by converting them to a canonical view without any predefined transformations. Moreover, in an open-set scenario, our network is able to better match images from unseen and unknown fine-grained categories. Extensive experiments on two public datasets and a newly collected dataset have demonstrated the outstanding robust performance of the proposed FGGAN in both closed-set and open-set scenarios, providing as much as 10% relative improvement compared to baselines.
SurfClipse: Context-Aware Meta Search in the IDE
Venue: arXiv cs.SE 2018
Year: 2018

Despite various debugging supports of the existing IDEs for programming errors and exceptions, software developers often look at web for working solutions or any up-to-date information. Traditional web search does not consider the context of the problems that they search solutions for, and thus it often does not help much in problem solving. In this paper, we propose a context-aware meta search tool, SurfClipse, that analyzes an encountered exception and its context in the IDE, and recommends not only suitable search queries but also relevant web pages for the exception (and its context). The tool collects results from three popular search engines and a programming Q & A site against the exception in the IDE, refines the results for relevance against the context of the exception, and then ranks them before recommendation. It provides two working modes--interactive and proactive to meet the versatile needs of the developers, and one can browse the result pages using a customized embedded browser provided by the tool. Tool page: www.usask.ca/~masud.rahman/surfclipse
Scalable Formal Concept Analysis algorithm for large datasets using Spark
Venue: arXiv cs.AI 2018
Year: 2018

In the process of knowledge discovery and representation in large datasets using formal concept analysis, complexity plays a major role in identifying all the formal concepts and constructing the concept lattice(digraph of the concepts). For identifying the formal concepts and constructing the digraph from the identified concepts in very large datasets, various distributed algorithms are available in the literature. However, the existing distributed algorithms are not very well suitable for concept generation because it is an iterative process. The existing algorithms are implemented using distributed frameworks like MapReduce and Open MP, these frameworks are not appropriate for iterative applications. Hence, in this paper we proposed efficient distributed algorithms for both formal concept generation and concept lattice digraph construction in large formal contexts using Apache Spark. Various performance metrics are considered for the evaluation of the proposed work, the results of the evaluation proves that the proposed algorithms are efficient for concept generation and lattice graph construction in comparison with the existing algorithms.
On the Use of Context in Recommending Exception Handling Code Examples
Venue: arXiv cs.SE 2018
Year: 2018

Studies show that software developers often either misuse exception handling features or use them inefficiently, and such a practice may lead an undergoing software project to a fragile, insecure and non-robust application system. In this paper, we propose a context-aware code recommendation approach that recommends exception handling code examples from a number of popular open source code repositories hosted at GitHub. It collects the code examples exploiting GitHub code search API, and then analyzes, filters and ranks them against the code under development in the IDE by leveraging not only the structural (i.e., graph-based) and lexical features but also the heuristic quality measures of exception handlers in the examples. Experiments with 4,400 code examples and 65 exception handling scenarios as well as comparisons with four existing approaches show that the proposed approach is highly promising.
Differentially Private Online Submodular Optimization
Venue: arXiv cs.DS 2018
Year: 2018

In this paper we develop the first algorithms for online submodular minimization that preserve differential privacy under full information feedback and bandit feedback. A sequence of $T$ submodular functions over a collection of $n$ elements arrive online, and at each timestep the algorithm must choose a subset of $[n]$ before seeing the function. The algorithm incurs a cost equal to the function evaluated on the chosen set, and seeks to choose a sequence of sets that achieves low expected regret. Our first result is in the full information setting, where the algorithm can observe the entire function after making its decision at each timestep. We give an algorithm in this setting that is $ε$-differentially private and achieves expected regret $\tilde{O}\left(\frac{n^{3/2}\sqrt{T}}ε\right)$. This algorithm works by relaxing submodular function to a convex function using the Lovasz extension, and then simulating an algorithm for differentially private online convex optimization. Our second result is in the bandit setting, where the algorithm can only see the cost incurred by its chosen set, and does not have access to the entire function. This setting is significantly more challenging because the algorithm does not receive enough information to compute the Lovasz extension or its subgradients. Instead, we construct an unbiased estimate using a single-point estimation, and then simulate private online convex optimization using this estimate. Our algorithm using bandit feedback is $ε$-differentially private and achieves expected regret $\tilde{O}\left(\frac{n^{3/2}T^{3/4}}ε\right)$.