OpenRaiser/Intern-Atlas huggingface dataset:
A Framework for End-to-End Deep Learning-Based Anomaly Detection in Transportation Networks
Venue: arXiv cs.LG 2019
Year: 2019

We develop an end-to-end deep learning-based anomaly detection model for temporal data in transportation networks. The proposed EVT-LSTM model is derived from the popular LSTM (Long Short-Term Memory) network and adopts an objective function that is based on fundamental results from EVT (Extreme Value Theory). We compare the EVT-LSTM model with some established statistical, machine learning, and hybrid deep learning baselines. Experiments on seven diverse real-world data sets demonstrate the superior anomaly detection performance of our proposed model over the other models considered in the comparison study.
On Node Features for Graph Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

Graph neural network (GNN) is a deep model for graph representation learning. One advantage of graph neural network is its ability to incorporate node features into the learning process. However, this prevents graph neural network from being applied into featureless graphs. In this paper, we first analyze the effects of node features on the performance of graph neural network. We show that GNNs work well if there is a strong correlation between node features and node labels. Based on these results, we propose new feature initialization methods that allows to apply graph neural network to non-attributed graphs. Our experimental results show that the artificial features are highly competitive with real features.
Strategy-Proof and Non-Wasteful Multi-Unit Auction via Social Network
Venue: arXiv cs.GT 2019
Year: 2019

Auctions via social network, pioneered by Li et al. (2017), have been attracting considerable attention in the literature of mechanism design for auctions. However, no known mechanism has satisfied strategy-proofness, non-deficit, non-wastefulness, and individual rationality for the multi-unit unit-demand auction, except for some naive ones. In this paper, we first propose a mechanism that satisfies all the above properties. We then make a comprehensive comparison with two naive mechanisms, showing that the proposed mechanism dominates them in social surplus, seller's revenue, and incentive of buyers for truth-telling. We also analyze the characteristics of the social surplus and the revenue achieved by the proposed mechanism, including the constant approximability of the worst-case efficiency loss and the complexity of optimizing revenue from the seller's perspective.
A Fast Sampling Gradient Tree Boosting Framework
Venue: arXiv cs.LG 2019
Year: 2019

As an adaptive, interpretable, robust, and accurate meta-algorithm for arbitrary differentiable loss functions, gradient tree boosting is one of the most popular machine learning techniques, though the computational expensiveness severely limits its usage. Stochastic gradient boosting could be adopted to accelerates gradient boosting by uniformly sampling training instances, but its estimator could introduce a high variance. This situation arises motivation for us to optimize gradient tree boosting. We combine gradient tree boosting with importance sampling, which achieves better performance by reducing the stochastic variance. Furthermore, we use a regularizer to improve the diagonal approximation in the Newton step of gradient boosting. The theoretical analysis supports that our strategies achieve a linear convergence rate on logistic loss. Empirical results show that our algorithm achieves a 2.5x--18x acceleration on two different gradient boosting algorithms (LogitBoost and LambdaMART) without appreciable performance loss.
A Conditional Perspective for Iterated Belief Contraction
Venue: arXiv cs.AI 2019
Year: 2019

According to Boutillier, Darwiche, Pearl and others, principles for iterated revision can be characterised in terms of changing beliefs about conditionals. For iterated contraction a similar formulation is not known. This is especially because for iterated belief change the connection between revision and contraction via the Levi and Harper identity is not straightforward, and therefore, characterisation results do not transfer easily between iterated revision and contraction. In this article, we develop an axiomatisation of iterated contraction in terms of changing conditional beliefs. We prove that the new set of postulates conforms semantically to the class of operators like the ones given by Konieczny and Pino Pérez for iterated contraction.
Table-Of-Contents generation on contemporary documents
Venue: arXiv cs.CL 2019
Year: 2019

The generation of precise and detailed Table-Of-Contents (TOC) from a document is a problem of major importance for document understanding and information extraction. Despite its importance, it is still a challenging task, especially for non-standardized documents with rich layout information such as commercial documents. In this paper, we present a new neural-based pipeline for TOC generation applicable to any searchable document. Unlike previous methods, we do not use semantic labeling nor assume the presence of parsable TOC pages in the document. Moreover, we analyze the influence of using external knowledge encoded as a template. We empirically show that this approach is only useful in a very low resource environment. Finally, we propose a new domain-specific data set that sheds some light on the difficulties of TOC generation in real-world documents. The proposed method shows better performance than the state-of-the-art on a public data set and on the newly released data set.
Self-supervised Learning of 3D Objects from Natural Images
Venue: arXiv cs.CV 2019
Year: 2019

We present a method to learn single-view reconstruction of the 3D shape, pose, and texture of objects from categorized natural images in a self-supervised manner. Since this is a severely ill-posed problem, carefully designing a training method and introducing constraints are essential. To avoid the difficulty of training all elements at the same time, we propose training category-specific base shapes with fixed pose distribution and simple textures first, and subsequently training poses and textures using the obtained shapes. Another difficulty is that shapes and backgrounds sometimes become excessively complicated to mistakenly reconstruct textures on object surfaces. To suppress it, we propose using strong regularization and constraints on object surfaces and background images. With these two techniques, we demonstrate that we can use natural image collections such as CIFAR-10 and PASCAL objects for training, which indicates the possibility to realize 3D object reconstruction on diverse object categories beyond synthetic datasets.
Impact of the Net Neutrality Repeal on Communication Networks
Venue: arXiv cs.NI 2019
Year: 2019

Network neutrality (net neutrality) is the principle of treating equally all Internet traffic regardless of its source, destination, content, application or other related distinguishing metrics. Under net neutrality, ISPs are compelled to charge all content providers (CPs) the same per Gbps rate despite the growing profit achieved by CPs. In this paper, we study the impact of the repeal of net neutrality on communication networks by developing a techno-economic Mixed Integer Linear Programming (MILP) model to maximize the potential profit ISPs can achieve by offering their services to CPs. We focus on video delivery as video traffic accounts for 78% of the cloud traffic. We consider an ISP that offers CPs different classes of service representing typical video content qualities including standard definition (SD), high definition (HD) and ultra-high definition (UHD) video. The MILP model maximizes the ISP profit by optimizing the prices of the different classes according to the users demand sensitivity to the change in price, referred to as Price Elasticity of Demand (PED). We analyze how PED impacts the profit in different CP delivery scenarios in cloud-fog architectures. The results show that the repeal of net neutrality can potentially increase ISPs profit by a factor of 8 with a pricing scheme that discriminates against data intensive content. Also, the repeal of net neutrality positively impacts the network energy efficiency by reducing the core network power consumption by 55% as a result of suppressing data intensive content compared to the net neutrality scenario.
A Comparative Study on End-to-end Speech to Text Translation
Venue: arXiv cs.CL 2019
Year: 2019

Recent advances in deep learning show that end-to-end speech to text translation model is a promising approach to direct the speech translation field. In this work, we provide an overview of different end-to-end architectures, as well as the usage of an auxiliary connectionist temporal classification (CTC) loss for better convergence. We also investigate on pre-training variants such as initializing different components of a model using pre-trained models, and their impact on the final performance, which gives boosts up to 4% in BLEU and 5% in TER. Our experiments are performed on 270h IWSLT TED-talks En->De, and 100h LibriSpeech Audiobooks En->Fr. We also show improvements over the current end-to-end state-of-the-art systems on both tasks.
Understanding Troll Writing as a Linguistic Phenomenon
Venue: arXiv cs.SI 2019
Year: 2019

The current study yielded a number of important findings. We managed to build a neural network that achieved an accuracy score of 91 per cent in classifying troll and genuine tweets. By means of regression analysis, we identified a number of features that make a tweet more susceptible to correct labelling and found that they are inherently present in troll tweets as a special type of discourse. We hypothesised that those features are grounded in the sociolinguistic limitations of troll writing, which can be best described as a combination of two factors: speaking with a purpose and trying to mask the purpose of speaking. Next, we contended that the orthogonal nature of these factors must necessarily result in the skewed distribution of many different language parameters of troll messages. Having chosen as an example distribution of the topics and vocabulary associated with those topics, we showed some very pronounced distributional anomalies, thus confirming our prediction.
Transfer Learning Toolkit: Primers and Benchmarks
Venue: arXiv cs.LG 2019
Year: 2019

The transfer learning toolkit wraps the codes of 17 transfer learning models and provides integrated interfaces, allowing users to use those models by calling a simple function. It is easy for primary researchers to use this toolkit and to choose proper models for real-world applications. The toolkit is written in Python and distributed under MIT open source license. In this paper, the current state of this toolkit is described and the necessary environment setting and usage are introduced.
A Hierarchical Optimizer for Recommendation System Based on Shortest Path Algorithm
Venue: arXiv cs.SI 2019
Year: 2019

Top-k Nearest Geosocial Keyword (T-kNGK) query on geosocial network is defined to give users k recommendations based on some keywords and designated spatial range, and can be realized by shortest path algorithms. However, shortest path algorithm cannot provide convincing recommendations, so we design a hierarchical optimizer consisting of classifiers and a constant optimizer to optimize the result by some features of the service providers.
Weak Supervision for Generating Pixel-Level Annotations in Scene Text Segmentation
Venue: arXiv cs.CV 2019
Year: 2019

Providing pixel-level supervisions for scene text segmentation is inherently difficult and costly, so that only few small datasets are available for this task. To face the scarcity of training data, previous approaches based on Convolutional Neural Networks (CNNs) rely on the use of a synthetic dataset for pre-training. However, synthetic data cannot reproduce the complexity and variability of natural images. In this work, we propose to use a weakly supervised learning approach to reduce the domain-shift between synthetic and real data. Leveraging the bounding-box supervision of the COCO-Text and the MLT datasets, we generate weak pixel-level supervisions of real images. In particular, the COCO-Text-Segmentation (COCO_TS) and the MLT-Segmentation (MLT_S) datasets are created and released. These two datasets are used to train a CNN, the Segmentation Multiscale Attention Network (SMANet), which is specifically designed to face some peculiarities of the scene text segmentation task. The SMANet is trained end-to-end on the proposed datasets, and the experiments show that COCO_TS and MLT_S are a valid alternative to synthetic images, allowing to use only a fraction of the training samples and improving significantly the performances.
New structures to solve aggregated queries for trips over public transportation networks
Venue: arXiv cs.DS 2019
Year: 2019

Representing the trajectories of mobile objects is a hot topic from the widespread use of smartphones and other GPS devices. However, few works have focused on representing trips over public transportation networks (buses, subway, and trains) where a user's trips can be seen as a sequence of stages performed within a vehicle shared with many other users. In this context, representing vehicle journeys reduces the redundancy because all the passengers inside a vehicle share the same arrival time for each stop. In addition, each vehicle journey follows exactly the sequence of stops corresponding to its line, which makes it unnecessary to represent that sequence for each journey. To solve data management for transportation systems, we designed a conceptual model that gave us a better insight into this data domain and allowed us the definition of relevant terms and the detection of redundancy sources among those data. Then, we designed two compact representations focused on users' trips (TTCTR) and on vehicle trips (AcumM), respectively. Each approach owns some strengths and is able to answer some queries efficiently. We include experimental results over synthetic trips generated from accurate schedules obtained from a real network description (from the bus transportation system of Madrid) to show the space/time trade-off of both approaches. We considered a wide range of different queries about the use of the transportation network such as counting-based or aggregate queries regarding the load of any line of the network at different times.
Real-Time Emotion Recognition via Attention Gated Hierarchical Memory Network
Venue: arXiv cs.CL 2019
Year: 2019

Real-time emotion recognition (RTER) in conversations is significant for developing emotionally intelligent chatting machines. Without the future context in RTER, it becomes critical to build the memory bank carefully for capturing historical context and summarize the memories appropriately to retrieve relevant information. We propose an Attention Gated Hierarchical Memory Network (AGHMN) to address the problems of prior work: (1) Commonly used convolutional neural networks (CNNs) for utterance feature extraction are less compatible in the memory modules; (2) Unidirectional gated recurrent units (GRUs) only allow each historical utterance to have context before it, preventing information propagation in the opposite direction; (3) The Soft Attention for summarizing loses the positional and ordering information of memories, regardless of how the memory bank is built. Particularly, we propose a Hierarchical Memory Network (HMN) with a bidirectional GRU (BiGRU) as the utterance reader and a BiGRU fusion layer for the interaction between historical utterances. For memory summarizing, we propose an Attention GRU (AGRU) where we utilize the attention weights to update the internal state of GRU. We further promote the AGRU to a bidirectional variant (BiAGRU) to balance the contextual information from recent memories and that from distant memories. We conduct experiments on two emotion conversation datasets with extensive analysis, demonstrating the efficacy of our AGHMN models.
Reversible Computation in Wireless Communications
Venue: arXiv cs.ET 2019
Year: 2019

This chapter presents the pioneering work in applying reversible computation paradigms to wireless communications. These applications range from developing reversible hardware architectures for underwater acoustic communications to novel distributed optimisation procedures in large radio-frequency antenna arrays based on reversing Petri nets. Throughout the chapter, we discuss the rationale for introducing reversible computation in the domain of wireless communications, exploring the inherently reversible properties of communication channels and systems formed by devices in a wireless network.
Concurrency and Privacy with Payment-Channel Networks
Venue: arXiv cs.CR 2019
Year: 2019

Permissionless blockchains protocols such as Bitcoin are inherently limited in transaction throughput and latency. Current efforts to address this key issue focus on off-chain payment channels that can be combined in a Payment-Channel Network (PCN) to enable an unlimited number of payments without requiring to access the blockchain other than to register the initial and final capacity of each channel. While this approach paves the way for low latency and high throughput of payments, its deployment in practice raises several privacy concerns as well as technical challenges related to the inherently concurrent nature of payments, such as race conditions and deadlocks, that have been understudied so far. In this work, we lay the foundations for privacy and concurrency in PCNs, presenting a formal definition in the Universal Composability framework as well as practical and provably secure solutions. In particular, we present Fulgor and Rayo. Fulgor is the first payment protocol for PCNs that provides provable privacy guarantees for PCNs and is fully compatible with the Bitcoin scripting system. However, Fulgor is a blocking protocol and therefore prone to deadlocks of concurrent payments as in currently available PCNs. Instead, Rayo is the first protocol for PCNs that enforces non-blocking progress (i.e., at least one of the concurrent payments terminates). We show through a new impossibility result that non-blocking progress necessarily comes at the cost of weaker privacy. At the core of Fulgor and Rayo is Multi-Hop HTLC, a new smart contract, compatible with the Bitcoin scripting system, that provides conditional payments while reducing running time and communication overhead with respect to previous approaches.
The Karger-Stein Algorithm is Optimal for $k$-cut
Venue: arXiv cs.DS 2019
Year: 2019

In the $k$-cut problem, we are given an edge-weighted graph and want to find the least-weight set of edges whose deletion breaks the graph into $k$ connected components. Algorithms due to Karger-Stein and Thorup showed how to find such a minimum $k$-cut in time approximately $O(n^{2k-2})$. The best lower bounds come from conjectures about the solvability of the $k$-clique problem and a reduction from $k$-clique to $k$-cut, and show that solving $k$-cut is likely to require time $Ω(n^k)$. Our recent results have given special-purpose algorithms that solve the problem in time $n^{1.98k + O(1)}$, and ones that have better performance for special classes of graphs (e.g., for small integer weights). In this work, we resolve the problem for general graphs, by showing that for any fixed $k \geq 2$, the Karger-Stein algorithm outputs any fixed minimum $k$-cut with probability at least $\hat{O}(n^{-k})$, where $\hat{O}(\cdot)$ hides a $2^{O(\ln \ln n)^2}$ factor. This also gives an extremal bound of $\hat{O}(n^k)$ on the number of minimum $k$-cuts in an $n$-vertex graph and an algorithm to compute a minimum $k$-cut in similar runtime. Both are tight up to $\hat{O}(1)$ factors. The first main ingredient in our result is a fine-grained analysis of how the graph shrinks---and how the average degree evolves---under the Karger-Stein process. The second ingredient is an extremal result bounding the number of cuts of size at most $(2-δ) OPT/k$, using the Sunflower lemma.
Predictive Coding as Stimulus Avoidance in Spiking Neural Networks
Venue: arXiv cs.NE 2019
Year: 2019

Predictive coding can be regarded as a function which reduces the error between an input signal and a top-down prediction. If reducing the error is equivalent to reducing the influence of stimuli from the environment, predictive coding can be regarded as stimulation avoidance by prediction. Our previous studies showed that action and selection for stimulation avoidance emerge in spiking neural networks through spike-timing dependent plasticity (STDP). In this study, we demonstrate that spiking neural networks with random structure spontaneously learn to predict temporal sequences of stimuli based solely on STDP.
Self-Expiring Data Capsule using Trusted Execution Environment
Venue: arXiv cs.CR 2019
Year: 2019

Data privacy is unarguably of extreme importance. Nonetheless, there exist various daunting challenges to safe-guarding data privacy. These challenges stem from the fact that data owners have little control over their data once it has transgressed their local storage and been managed by third parties whose trustworthiness is questionable at times. Our work seeks to enhance data privacy by constructing a self-expiring data capsule. Sensitive data is encapsulated into a capsule which is associated with an access policy an expiring condition. The former indicates eligibility of functions that can access the data, and the latter dictates when the data should become inaccessible to anyone, including the previously eligible functions. Access to the data capsule, as well as its dismantling once the expiring condition is met, are governed by a committee of independent and mutually distrusting nodes. The pivotal contribution of our work is an integration of hardware primitive, state machine replication and threshold secret sharing in the design of the self-expiring data encapsulation framework. We implement the proposed framework in a system called TEEKAP. Our empirical experiments conducted on a realistic deployment setting with the access control committee spanning across four geographical regions reveal that TEEKAP can process access requests at scale with sub-second latency.
Magnetic-Assisted Initialization for Infrastructure-free Mobile Robot Localization
Venue: arXiv cs.RO 2019
Year: 2019

Most of the existing mobile robot localization solutions are either heavily dependent on pre-installed infrastructures or having difficulty working in highly repetitive environments which do not have sufficient unique features. To address this problem, we propose a magnetic-assisted initialization approach that enhances the performance of infrastructure-free mobile robot localization in repetitive featureless environments. The proposed system adopts a coarse-to-fine structure, which mainly consists of two parts: magnetic field-based matching and laser scan matching. Firstly, the interpolated magnetic field map is built and the initial pose of the mobile robot is partly determined by the k-Nearest Neighbors (k-NN) algorithm. Next, with the fusion of prior initial pose information, the robot is localized by laser scan matching more accurately and efficiently. In our experiment, the mobile robot was successfully localized in a featureless rectangular corridor with a success rate of 88% and an average correct localization time of 6.6 seconds.