OpenRaiser/Intern-Atlas huggingface dataset:
Worst-Case Efficient Sorting with QuickMergesort
Venue: arXiv cs.DS 2018
Year: 2018

The two most prominent solutions for the sorting problem are Quicksort and Mergesort. While Quicksort is very fast on average, Mergesort additionally gives worst-case guarantees, but needs extra space for a linear number of elements. Worst-case efficient in-place sorting, however, remains a challenge: the standard solution, Heapsort, suffers from a bad cache behavior and is also not overly fast for in-cache instances. In this work we present median-of-medians QuickMergesort (MoMQuickMergesort), a new variant of QuickMergesort, which combines Quicksort with Mergesort allowing the latter to be implemented in place. Our new variant applies the median-of-medians algorithm for selecting pivots in order to circumvent the quadratic worst case. Indeed, we show that it uses at most $n \log n + 1.6n$ comparisons for $n$ large enough. We experimentally confirm the theoretical estimates and show that the new algorithm outperforms Heapsort by far and is only around 10% slower than Introsort (std::sort implementation of stdlibc++), which has a rather poor guarantee for the worst case. We also simulate the worst case, which is only around 10% slower than the average case. In particular, the new algorithm is a natural candidate to replace Heapsort as a worst-case stopper in Introsort.
Understanding Deep Neural Networks Using Topological Data Analysis
Venue: arXiv cs.LG 2018
Year: 2018

Deep neural networks (DNN) are black box algorithms. They are trained using a gradient descent back propagation technique which trains weights in each layer for the sole goal of minimizing training error. Hence, the resulting weights cannot be directly explained. Using Topological Data Analysis (TDA) we can get an insight on how the neural network is thinking, specifically by analyzing the activation values of validation images as they pass through each layer.
Can automated smoothing significantly improve benchmark time series classification algorithms?
Venue: arXiv cs.LG 2018
Year: 2018

tl;dr: no, it cannot, at least not on average on the standard archive problems. We assess whether using six smoothing algorithms (moving average, exponential smoothing, Gaussian filter, Savitzky-Golay filter, Fourier approximation and a recursive median sieve) could be automatically applied to time series classification problems as a preprocessing step to improve the performance of three benchmark classifiers (1-Nearest Neighbour with Euclidean and Dynamic Time Warping distances, and Rotation Forest). We found no significant improvement over unsmoothed data even when we set the smoothing parameter through cross validation. We are not claiming smoothing has no worth. It has an important role in exploratory analysis and helps with specific classification problems where domain knowledge can be exploited. What we observe is that the automatic application does not help and that we cannot explain the improvement of other time series classification algorithms over the baseline classifiers simply as a function of the absence of smoothing.
Alert Correlation Algorithms: A Survey and Taxonomy
Venue: arXiv cs.CR 2018
Year: 2018

Alert correlation is a system which receives alerts from heterogeneous Intrusion Detection Systems and reduces false alerts, detects high level patterns of attacks, increases the meaning of occurred incidents, predicts the future states of attacks, and detects root cause of attacks. To reach these goals, many algorithms have been introduced in the world with many advantages and disadvantages. In this paper, we are trying to present a comprehensive survey on already proposed alert correlation algorithms. The approach of this survey is mainly focused on algorithms in correlation engines which can work in enterprise and practical networks. Having this aim in mind, many features related to accuracy, functionality, and computation power are introduced and all algorithm categories are assessed with these features. The result of this survey shows that each category of algorithms has its own strengths and an ideal correlation frameworks should be carried the strength feature of each category.
Two Novel Server-Side Attacks against Log File in Shared Web Hosting Servers
Venue: arXiv cs.CR 2018
Year: 2018

Shared Web Hosting service enables hosting multitude of websites on a single powerful server. It is a well-known solution as many people share the overall cost of server maintenance and also, website owners do not need to deal with administration issues is not necessary for website owners. In this paper, we illustrate how shared web hosting service works and demonstrate the security weaknesses rise due to the lack of proper isolation between different websites, hosted on the same server. We exhibit two new server-side attacks against the log file whose objectives are revealing information of other hosted websites which are considered to be private and arranging other complex attacks. In the absence of isolated log files among websites, an attacker controlling a website can inspect and manipulate contents of the log file. These attacks enable an attacker to disclose file and directory structure of other websites and launch other sorts of attacks. Finally, we propose several countermeasures to secure shared web hosting servers against the two attacks subsequent to the separation of log files for each website.
An Anomaly-based Botnet Detection Approach for Identifying Stealthy Botnets
Venue: arXiv cs.CR 2018
Year: 2018

Botnets (networks of compromised computers) are often used for malicious activities such as spam, click fraud, identity theft, phishing, and distributed denial of service (DDoS) attacks. Most of previous researches have introduced fully or partially signature-based botnet detection approaches. In this paper, we propose a fully anomaly-based approach that requires no a priori knowledge of bot signatures, botnet C&C protocols, and C&C server addresses. We start from inherent characteristics of botnets. Bots connect to the C&C channel and execute the received commands. Bots belonging to the same botnet receive the same commands that causes them having similar netflows characteristics and performing same attacks. Our method clusters bots with similar netflows and attacks in different time windows and perform correlation to identify bot infected hosts. We have developed a prototype system and evaluated it with real-world traces including normal traffic and several real-world botnet traces. The results show that our approach has high detection accuracy and low false positive.
Learning to Rank Query Graphs for Complex Question Answering over Knowledge Graphs
Venue: arXiv cs.LG 2018
Year: 2018

In this paper, we conduct an empirical investigation of neural query graph ranking approaches for the task of complex question answering over knowledge graphs. We experiment with six different ranking models and propose a novel self-attention based slot matching model which exploits the inherent structure of query graphs, our logical form of choice. Our proposed model generally outperforms the other models on two QA datasets over the DBpedia knowledge graph, evaluated in different settings. In addition, we show that transfer learning from the larger of those QA datasets to the smaller dataset yields substantial improvements, effectively offsetting the general lack of training data.
The Burst Failure Influence on the $H_\infty$ Norm
Venue: arXiv cs.SY 2018
Year: 2018

In this work, we present an analysis of the Burst failure effect in the $H_\infty$ norm. We present a procedure to perform an analysis between different Markov Chain models and a numerical example. In the numerical example the results obtained pointed out that the burst failure effect in the performance does not exceed 6.3%. However, this work is an introduction for a wider and more extensive analysis in this subject.
The IFF Approach to the Lattice of Theories
Venue: arXiv cs.LO 2018
Year: 2018

The IFF approach for the notion of "lattice of theories" uses the idea of a concept lattice from Formal Concept Analysis (Ganter and Wille) and the idea of the truth classification from Information Flow (Barwise and Seligman). The IFF approach is concentrated in the joining of these two important ideas. The result is called the truth concept lattice, the concept lattice of the truth classification. The IFF provides a principled (versus ad hoc) approach for John Sowa's "lattice of theories" framework. The "lattice of theories" is represented by the truth concept lattice, each theory in the lattice is represented by a formal concept in the truth concept lattice.
Pushing the boundaries of audiovisual word recognition using Residual Networks and LSTMs
Venue: arXiv cs.CV 2018
Year: 2018

Visual and audiovisual speech recognition are witnessing a renaissance which is largely due to the advent of deep learning methods. In this paper, we present a deep learning architecture for lipreading and audiovisual word recognition, which combines Residual Networks equipped with spatiotemporal input layers and Bidirectional LSTMs. The lipreading architecture attains 11.92% misclassification rate on the challenging Lipreading-In-The-Wild database, which is composed of excerpts from BBC-TV, each containing one of the 500 target words. Audiovisual experiments are performed using both intermediate and late integration, as well as several types and levels of environmental noise, and notable improvements over the audio-only network are reported, even in the case of clean speech. A further analysis on the utility of target word boundaries is provided, as well as on the capacity of the network in modeling the linguistic context of the target word. Finally, we examine difficult word pairs and discuss how visual information helps towards attaining higher recognition accuracy.
DUNet: A deformable network for retinal vessel segmentation
Venue: arXiv cs.CV 2018
Year: 2018

Automatic segmentation of retinal vessels in fundus images plays an important role in the diagnosis of some diseases such as diabetes and hypertension. In this paper, we propose Deformable U-Net (DUNet), which exploits the retinal vessels' local features with a U-shape architecture, in an end to end manner for retinal vessel segmentation. Inspired by the recently introduced deformable convolutional networks, we integrate the deformable convolution into the proposed network. The DUNet, with upsampling operators to increase the output resolution, is designed to extract context information and enable precise localization by combining low-level feature maps with high-level ones. Furthermore, DUNet captures the retinal vessels at various shapes and scales by adaptively adjusting the receptive fields according to vessels' scales and shapes. Three public datasets DRIVE, STARE and CHASE_DB1 are used to train and test our model. Detailed comparisons between the proposed network and the deformable neural network, U-Net are provided in our study. Results show that more detailed vessels are extracted by DUNet and it exhibits state-of-the-art performance for retinal vessel segmentation with a global accuracy of 0.9697/0.9722/0.9724 and AUC of 0.9856/0.9868/0.9863 on DRIVE, STARE and CHASE_DB1 respectively. Moreover, to show the generalization ability of the DUNet, we used another two retinal vessel data sets, one is named WIDE and the other is a synthetic data set with diverse styles, named SYNTHE, to qualitatively and quantitatively analyzed and compared with other methods. Results indicates that DUNet outperforms other state-of-the-arts.
Reliable graph-based collaborative ranking
Venue: arXiv cs.SI 2018
Year: 2018

GRank is a recent graph-based recommendation approach the uses a novel heterogeneous information network to model users' priorities and analyze it to directly infer a recommendation list. Unfortunately, GRank neglects the semantics behind different types of paths in the network and during the process, it may use unreliable paths that are inconsistent with the general idea of similarity in neighborhood collaborative ranking. That negligence undermines the reliability of the recommendation list generated by GRank. This paper seeks to present a novel framework for reliable graph-based collaborative ranking, called ReGRank, that ranks items based on reliable recommendation paths that are in harmony with the semantics behind different approaches in neighborhood collaborative ranking. To our knowledge, ReGRank is the first unified framework for neighborhood collaborative ranking that in addition to traditional user-based collaborative ranking, can also be adapted for preference-based and representative-based collaborative ranking as well. Experimental results show that ReGRank significantly improves the state-of-the art neighborhood and graph-based collaborative ranking algorithms.
Relation Mention Extraction from Noisy Data with Hierarchical Reinforcement Learning
Venue: arXiv cs.CL 2018
Year: 2018

In this paper we address a task of relation mention extraction from noisy data: extracting representative phrases for a particular relation from noisy sentences that are collected via distant supervision. Despite its significance and value in many downstream applications, this task is less studied on noisy data. The major challenges exists in 1) the lack of annotation on mention phrases, and more severely, 2) handling noisy sentences which do not express a relation at all. To address the two challenges, we formulate the task as a semi-Markov decision process and propose a novel hierarchical reinforcement learning model. Our model consists of a top-level sentence selector to remove noisy sentences, a low-level mention extractor to extract relation mentions, and a reward estimator to provide signals to guide data denoising and mention extraction without explicit annotations. Experimental results show that our model is effective to extract relation mentions from noisy data.
A dataset for benchmarking vision-based localization at intersections
Venue: arXiv cs.CV 2018
Year: 2018

In this report we present the work performed in order to build a dataset for benchmarking vision-based localization at intersections, i.e., a set of stereo video sequences taken from a road vehicle that is approaching an intersection, altogether with a reliable measure of the observer position. This report is meant to complement our paper "Vision-Based Localization at Intersections using Digital Maps" submitted to ICRA2019. It complements the paper because the paper uses the dataset, but it had no space for describing the work done to obtain it. Moreover, the dataset is of interest for all those tackling the task of online localization at intersections for road vehicles, e.g., for a quantitative comparison with the proposal in our submitted paper, and it is therefore appropriate to put the dataset description in a separate report. We considered all datasets from road vehicles that we could find as for the end of August 2018. After our evaluation, we kept only sub-sequences from the KITTI dataset. In the future we will increase the collection of sequences with data from our vehicle.
Lower Bounds for External Memory Integer Sorting via Network Coding
Venue: arXiv cs.DS 2018
Year: 2018

Sorting extremely large datasets is a frequently occuring task in practice. These datasets are usually much larger than the computer's main memory; thus external memory sorting algorithms, first introduced by Aggarwal and Vitter (1988), are often used. The complexity of comparison based external memory sorting has been understood for decades by now, however the situation remains elusive if we assume the keys to be sorted are integers. In internal memory, one can sort a set of $n$ integer keys of $Θ(\lg n)$ bits each in $O(n)$ time using the classic Radix Sort algorithm, however in external memory, there are no faster integer sorting algorithms known than the simple comparison based ones. In this paper, we present a tight conditional lower bound on the complexity of external memory sorting of integers. Our lower bound is based on a famous conjecture in network coding by Li and Li, who conjectured that network coding cannot help anything beyond the standard multicommodity flow rate in undirected graphs. The only previous work connecting the Li and Li conjecture to lower bounds for algorithms is due to Adler et al. Adler et al. indeed obtain relatively simple lower bounds for oblivious algorithms (the memory access pattern is fixed and independent of the input data). Unfortunately obliviousness is a strong limitations, especially for integer sorting: we show that the Li and Li conjecture implies an $Ω(n \log n)$ lower bound for internal memory oblivious sorting when the keys are $Θ(\lg n)$ bits. This is in sharp contrast to the classic (non-oblivious) Radix Sort algorithm. Indeed going beyond obliviousness is highly non-trivial; we need to introduce several new methods and involved techniques, which are of their own interest, to obtain our tight lower bound for external memory integer sorting.
Syntax and Typing for Cedille Core
Venue: arXiv cs.LO 2018
Year: 2018

This document specifies a core version of the type theory implemented in the Cedille tool. Cedille is a language for dependently typed programming and computer-checked proof. Cedille can elaborate source programs down to Cedille Core, which can be checked in a straightforward way by a small checker (a reference implementation included with Cedille is under 1000 lines of Haskell). Other tools could also target Cedille Core as an expressive backend type theory. The document describes syntax and typing rules for Cedille Core.
Synchronized Multi-Load Balancer with Fault Tolerance in Cloud
Venue: arXiv cs.DC 2018
Year: 2018

In this method, service of one load balancer can be borrowed or shared among other load balancers when any correction is needed in the estimation of the load.
RA-UNet: A hybrid deep attention-aware network to extract liver and tumor in CT scans
Venue: arXiv cs.CV 2018
Year: 2018

Automatic extraction of liver and tumor from CT volumes is a challenging task due to their heterogeneous and diffusive shapes. Recently, 2D and 3D deep convolutional neural networks have become popular in medical image segmentation tasks because of the utilization of large labeled datasets to learn hierarchical features. However, 3D networks have some drawbacks due to their high cost on computational resources. In this paper, we propose a 3D hybrid residual attention-aware segmentation method, named RA-UNet, to precisely extract the liver volume of interests (VOI) and segment tumors from the liver VOI. The proposed network has a basic architecture as a 3D U-Net which extracts contextual information combining low-level feature maps with high-level ones. Attention modules are stacked so that the attention-aware features change adaptively as the network goes "very deep" and this is made possible by residual learning. This is the first work that an attention residual mechanism is used to process medical volumetric images. We evaluated our framework on the public MICCAI 2017 Liver Tumor Segmentation dataset and the 3DIRCADb dataset. The results show that our architecture outperforms other state-of-the-art methods. We also extend our RA-UNet to brain tumor segmentation on the BraTS2018 and BraTS2017 datasets, and the results indicate that RA-UNet achieves good performance on a brain tumor segmentation task as well.
Validated Asynchronous Byzantine Agreement with Optimal Resilience and Asymptotically Optimal Time and Word Communication
Venue: arXiv cs.DC 2018
Year: 2018

We provide a new protocol for Validated Asynchronous Byzantine Agreement. Validated (multi-valued) Asynchronous Byzantine Agreement is a key building block in constructing Atomic Broadcast and fault-tolerant state machine replication in the asynchronous setting. Our protocol can withstand the optimal number $f<n/3$ of Byzantine failures and reaches agreement in the asymptotically optimal expected $O(1)$ running time. Honest parties in our protocol send only an expected $O(n^2)$ messages where each message contains a value and a constant number of signatures. Hence our total expected communication is $O(n^2)$ words. The best previous result of Cachin et al. from 2001 solves Validated Byzantine Agreement with optimal resilience and $O(1)$ expected time but with $O(n^3)$ expected word communication. Our work addresses an open question of Cachin et al. from 2001 and improves the expected word communication from $O(n^3)$ to the asymptotically optimal $O(n^2)$.
Neural CRF transducers for sequence labeling
Venue: arXiv cs.LG 2018
Year: 2018

Conditional random fields (CRFs) have been shown to be one of the most successful approaches to sequence labeling. Various linear-chain neural CRFs (NCRFs) are developed to implement the non-linear node potentials in CRFs, but still keeping the linear-chain hidden structure. In this paper, we propose NCRF transducers, which consists of two RNNs, one extracting features from observations and the other capturing (theoretically infinite) long-range dependencies between labels. Different sequence labeling methods are evaluated over POS tagging, chunking and NER (English, Dutch). Experiment results show that NCRF transducers achieve consistent improvements over linear-chain NCRFs and RNN transducers across all the four tasks, and can improve state-of-the-art results.
Improving Zero-Shot Translation of Low-Resource Languages
Venue: arXiv cs.CL 2018
Year: 2018

Recent work on multilingual neural machine translation reported competitive performance with respect to bilingual models and surprisingly good performance even on (zeroshot) translation directions not observed at training time. We investigate here a zero-shot translation in a particularly lowresource multilingual setting. We propose a simple iterative training procedure that leverages a duality of translations directly generated by the system for the zero-shot directions. The translations produced by the system (sub-optimal since they contain mixed language from the shared vocabulary), are then used together with the original parallel data to feed and iteratively re-train the multilingual network. Over time, this allows the system to learn from its own generated and increasingly better output. Our approach shows to be effective in improving the two zero-shot directions of our multilingual model. In particular, we observed gains of about 9 BLEU points over a baseline multilingual model and up to 2.08 BLEU over a pivoting mechanism using two bilingual models. Further analysis shows that there is also a slight improvement in the non-zero-shot language directions.
Semantic Role Labeling for Knowledge Graph Extraction from Text
Venue: arXiv cs.AI 2018
Year: 2018

This paper introduces TakeFive, a new semantic role labeling method that transforms a text into a frame-oriented knowledge graph. It performs dependency parsing, identifies the words that evoke lexical frames, locates the roles and fillers for each frame, runs coercion techniques, and formalises the results as a knowledge graph. This formal representation complies with the frame semantics used in Framester, a factual-linguistic linked data resource. The obtained precision, recall and F1 values indicate that TakeFive is competitive with other existing methods such as SEMAFOR, Pikes, PathLSTM and FRED. We finally discuss how to combine TakeFive and FRED, obtaining higher values of precision, recall and F1.