OpenRaiser/Intern-Atlas huggingface dataset:
Near-Optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs
Venue: arXiv cs.CG 2019
Year: 2019

We revisit a classical graph-theoretic problem, the \textit{single-source shortest-path} (SSSP) problem, in weighted unit-disk graphs. We first propose an exact (and deterministic) algorithm which solves the problem in $O(n \log^2 n)$ time using linear space, where $n$ is the number of the vertices of the graph. This significantly improves the previous deterministic algorithm by Cabello and Jejčič [CGTA'15] which uses $O(n^{1+δ})$ time and $O(n^{1+δ})$ space (for any small constant $δ>0$) and the previous randomized algorithm by Kaplan et al. [SODA'17] which uses $O(n \log^{12+o(1)} n)$ expected time and $O(n \log^3 n)$ space. More specifically, we show that if the 2D offline insertion-only (additively-)weighted nearest-neighbor problem with $k$ operations (i.e., insertions and queries) can be solved in $f(k)$ time, then the SSSP problem in weighted unit-disk graphs can be solved in $O(n \log n+f(n))$ time. Using the same framework with some new ideas, we also obtain a $(1+\varepsilon)$-approximate algorithm for the problem, using $O(n \log n + n \log^2(1/\varepsilon))$ time and linear space. This improves the previous $(1+\varepsilon)$-approximate algorithm by Chan and Skrepetos [SoCG'18] which uses $O((1/\varepsilon)^2 n \log n)$ time and $O((1/\varepsilon)^2 n)$ space. More specifically, we show that if the 2D offline insertion-only weighted nearest-neighbor problem with $k_1$ operations in which at most $k_2$ operations are insertions can be solved in $f(k_1,k_2)$ time, then the $(1+\varepsilon)$-approximate SSSP problem in weighted unit-disk graphs can be solved in $O(n \log n+f(n,O(\varepsilon^{-2})))$ time. Because of the $Ω(n \log n)$-time lower bound of the problem (even when approximation is allowed), both of our algorithms are almost optimal.
Towards Unsupervised Cancer Subtyping: Predicting Prognosis Using A Histologic Visual Dictionary
Venue: arXiv cs.CV 2019
Year: 2019

Unlike common cancers, such as those of the prostate and breast, tumor grading in rare cancers is difficult and largely undefined because of small sample sizes, the sheer volume of time needed to undertake on such a task, and the inherent difficulty of extracting human-observed patterns. One of the most challenging examples is intrahepatic cholangiocarcinoma (ICC), a primary liver cancer arising from the biliary system, for which there is well-recognized tumor heterogeneity and no grading paradigm or prognostic biomarkers. In this paper, we propose a new unsupervised deep convolutional autoencoder-based clustering model that groups together cellular and structural morphologies of tumor in 246 ICC digitized whole slides, based on visual similarity. From this visual dictionary of histologic patterns, we use the clusters as covariates to train Cox-proportional hazard survival models. In univariate analysis, three clusters were significantly associated with recurrence-free survival. Combinations of these clusters were significant in multivariate analysis. In a multivariate analysis of all clusters, five showed significance to recurrence-free survival, however the overall model was not measured to be significant. Finally, a pathologist assigned clinical terminology to the significant clusters in the visual dictionary and found evidence supporting the hypothesis that collagen-enriched fibrosis plays a role in disease severity. These results offer insight into the future of cancer subtyping and show that computational pathology can contribute to disease prognostication, especially in rare cancers.
Offensive Language Analysis using Deep Learning Architecture
Venue: arXiv cs.CL 2019
Year: 2019

SemEval-2019 Task 6 (Zampieri et al., 2019b) requires us to identify and categorise offensive language in social media. In this paper we will describe the process we took to tackle this challenge. Our process is heavily inspired by Sosa (2017) where he proposed CNN-LSTM and LSTM-CNN models to conduct twitter sentiment analysis. We decided to follow his approach as well as further his work by testing out different variations of RNN models with CNN. Specifically, we have divided the challenge into two parts: data processing and sampling and choosing the optimal deep learning architecture. In preprocessing, we experimented with two techniques, SMOTE and Class Weights to counter the imbalance between classes. Once we are happy with the quality of our input data, we proceed to choosing the optimal deep learning architecture for this task. Given the quality and quantity of data we have been given, we found that the addition of CNN layer provides very little to no additional improvement to our model's performance and sometimes even lead to a decrease in our F1-score. In the end, the deep learning architecture that gives us the highest macro F1-score is a simple BiLSTM-CNN.
Efficient Search-Based Weighted Model Integration
Venue: arXiv cs.AI 2019
Year: 2019

Weighted model integration (WMI) extends Weighted model counting (WMC) to the integration of functions over mixed discrete-continuous domains. It has shown tremendous promise for solving inference problems in graphical models and probabilistic programming. Yet, state-of-the-art tools for WMI are limited in terms of performance and ignore the independence structure that is crucial to improving efficiency. To address this limitation, we propose an efficient model integration algorithm for theories with tree primal graphs. We exploit the sparse graph structure by using search to performing integration. Our algorithm greatly improves the computational efficiency on such problems and exploits context-specific independence between variables. Experimental results show dramatic speedups compared to existing WMI solvers on problems with tree-shaped dependencies.
A Sliding Mode Force and Position Controller Synthesis for Series Elastic Actuators
Venue: arXiv cs.RO 2019
Year: 2019

This paper deals with the robust force and position control problems of Series Elastic Actuators. It is shown that a Series Elastic Actuator's force control problem can be described by a second-order dynamic model which suffers from only matched disturbances. However, the position control dynamics of a Series Elastic Actuator is of fourth-order and includes matched and mismatched disturbances. In other words, a Series Elastic Actuator's position control is more complicated than its force control, particularly when disturbances are considered. A novel robust motion controller is proposed for Series Elastic Actuators by using Disturbance Observer and Sliding Mode Control. When the proposed robust motion controller is implemented, a Series Elastic Actuator can precisely track desired trajectories and safely contact with an unknown and dynamic environment. The proposed motion controller does not require precise dynamic models of the actuator and environment. Therefore, it can be applied to many different advanced robotic systems such as compliant humanoids and exoskeletons. The validity of the motion controller is experimentally verified.
The Fourier Spectral Characterization for the Correlation-Immune Functions over Fp
Venue: arXiv cs.IT 2019
Year: 2019

The correlation-immune functions serve as an important metric for measuring resistance of a cryptosystem against correlation attacks. Existing literature emphasize on matrices, orthogonal arrays and Walsh-Hadamard spectra to characterize the correlation-immune functions over $\mathbb{F}_p$ ($p \geq 2$ is a prime). %with prime $p$. Recently, Wang and Gong investigated the Fourier spectral characterization over the complex field for correlation-immune Boolean functions. In this paper, the discrete Fourier transform (DFT) of non-binary functions was studied. It was shown that a function $f$ over $\mathbb{F}_p$ is $m$th-order correlation-immune if and only if its Fourier spectrum vanishes at a specific location under any permutation of variables. Moreover, if $f$ is a symmetric function, $f$ is correlation-immune if and only if its Fourier spectrum vanishes at only one location.
New Characterizations for the Multi-output Correlation-Immune Boolean Functions
Venue: arXiv cs.IT 2019
Year: 2019

Correlation-immune (CI) multi-output Boolean functions have the property of keeping the same output distribution when some input variables are fixed. Recently, a new application of CI functions has appeared in the system of resisting side-channel attacks (SCA). In this paper, three new methods are proposed to characterize the $t$ th-order CI multi-output Boolean functions ($n$-input and $m$-output). The first characterization is to regard the multi-output Boolean functions as the corresponding generalized Boolean functions. It is shown that a generalized Boolean functions $f_g$ is a $t$ th-order CI function if and only if the Walsh transform of $f_g$ defined here vanishes at all points with Hamming weights between $1$ and $t$. Compared to the previous Walsh transforms of component functions, our first method can reduce the computational complexity from $(2^m-1)\sum^t_{j=1}\binom{n}{j}$ to $m\sum^t_{j=1}\binom{n}{j}$. The last two methods are generalized from Fourier spectral characterizations. Especially, Fourier spectral characterizations are more efficient to characterize the symmetric multi-output CI Boolean functions.
A Distributed Observer for a Discrete-Time Linear System
Venue: arXiv cs.SY 2019
Year: 2019

A simply structured distributed observer is described for estimating the state of a discrete-time, jointly observable, input-free, linear system whose sensed outputs are distributed across a time-varying network. It is explained how to construct the local estimators which comprise the observer so that their state estimation errors all converge exponentially fast to zero at a fixed, but arbitrarily chosen rate provided the network's graph is strongly connected for all time. This is accomplished by exploiting several well-known properties of invariant subspaces plus several kinds of suitably defined matrix norms.
On the Efficacy and High-Performance Implementation of Quaternion Matrix Multiplication
Venue: arXiv cs.MS 2019
Year: 2019

Quaternion symmetry is ubiquitous in the physical sciences. As such, much work has been afforded over the years to the development of efficient schemes to exploit this symmetry using real and complex linear algebra. Recent years have also seen many advances in the formal theoretical development of explicitly quaternion linear algebra with promising applications in image processing and machine learning. Despite these advances, there do not currently exist optimized software implementations of quaternion linear algebra. The leverage of optimized linear algebra software is crucial in the achievement of high levels of performance on modern computing architectures, and thus provides a central tool in the development of high-performance scientific software. In this work, a case will be made for the efficacy of high-performance quaternion linear algebra software for appropriate problems. In this pursuit, an optimized software implementation of quaternion matrix multiplication will be presented and will be shown to outperform a vendor tuned implementation for the analogous complex matrix operation. The results of this work pave the path for further development of high-performance quaternion linear algebra software which will improve the performance of the next generation of applicable scientific applications.
A Comprehensive Analysis of 2D&3D Video Watching of EEG Signals by Increasing PLSR and SVM Classification Results
Venue: arXiv cs.HC 2019
Year: 2019

Despite the development of two and three dimensional (2D&3D) technology, it has attracted the attention of researchers in recent years. This research is done to reveal the detailed effects of 2D in comparison with 3D technology on the human brain waves. The impact of 2D&3D video watching using electroencephalography (EEG) brain signals is studied. A group of eight healthy volunteers with the average age of 31+-3.06 years old participated in this three-stage test. EEG signal recording consisted of three stages: After a bit of relaxation (a), a 2D video was displayed (b), the recording of the signal continued for a short period of time as rest (c), and finally the trial ended. Exactly the same steps were repeated for the 3D video. Power spectrum density (PSD) based on short time Fourier transform (STFT) was used to analyze the brain signals of 2D&3D video viewers. After testing all the EEG frequency bands, delta and theta were extracted as the features. Partial least squares regression (PLSR) and Support vector machine (SVM) classification algorithms were considered in order to classify EEG signals obtained as the result of 2D&3D video watching. Successful classification results were obtained by selecting the correct combinations of effective channels representing the brain regions.
Fuzzy Rough Set Feature Selection to Enhance Phishing Attack Detection
Venue: arXiv cs.LG 2019
Year: 2019

Phishing as one of the most well-known cybercrime activities is a deception of online users to steal their personal or confidential information by impersonating a legitimate website. Several machine learning-based strategies have been proposed to detect phishing websites. These techniques are dependent on the features extracted from the website samples. However, few studies have actually considered efficient feature selection for detecting phishing attacks. In this work, we investigate an agreement on the definitive features which should be used in phishing detection. We apply Fuzzy Rough Set (FRS) theory as a tool to select most effective features from three benchmarked data sets. The selected features are fed into three often used classifiers for phishing detection. To evaluate the FRS feature selection in developing a generalizable phishing detection, the classifiers are trained by a separate out-of-sample data set of 14,000 website samples. The maximum F-measure gained by FRS feature selection is 95% using Random Forest classification. Also, there are 9 universal features selected by FRS over all the three data sets. The F-measure value using this universal feature set is approximately 93% which is a comparable result in contrast to the FRS performance. Since the universal feature set contains no features from third-part services, this finding implies that with no inquiry from external sources, we can gain a faster phishing detection which is also robust toward zero-day attacks.
Maybe Deep Neural Networks are the Best Choice for Modeling Source Code
Venue: arXiv cs.SE 2019
Year: 2019

Statistical language modeling techniques have successfully been applied to source code, yielding a variety of new software development tools, such as tools for code suggestion and improving readability. A major issue with these techniques is that code introduces new vocabulary at a far higher rate than natural language, as new identifier names proliferate. But traditional language models limit the vocabulary to a fixed set of common words. For code, this strong assumption has been shown to have a significant negative effect on predictive performance. But the open vocabulary version of the neural network language models for code have not been introduced in the literature. We present a new open-vocabulary neural language model for code that is not limited to a fixed vocabulary of identifier names. We employ a segmentation into subword units, subsequences of tokens chosen based on a compression criterion, following previous work in machine translation. Our network achieves best in class performance, outperforming even the state-of-the-art methods of Hellendoorn and Devanbu that are designed specifically to model code. Furthermore, we present a simple method for dynamically adapting the model to a new test project, resulting in increased performance. We showcase our methodology on code corpora in three different languages of over a billion tokens each, hundreds of times larger than in previous work. To our knowledge, this is the largest neural language model for code that has been reported.
Improving Prostate Cancer Detection with Breast Histopathology Images
Venue: arXiv cs.LG 2019
Year: 2019

Deep neural networks have introduced significant advancements in the field of machine learning-based analysis of digital pathology images including prostate tissue images. With the help of transfer learning, classification and segmentation performance of neural network models have been further increased. However, due to the absence of large, extensively annotated, publicly available prostate histopathology datasets, several previous studies employ datasets from well-studied computer vision tasks such as ImageNet dataset. In this work, we propose a transfer learning scheme from breast histopathology images to improve prostate cancer detection performance. We validate our approach on annotated prostate whole slide images by using a publicly available breast histopathology dataset as pre-training. We show that the proposed cross-cancer approach outperforms transfer learning from ImageNet dataset.
Authentication by Witness Functions
Venue: arXiv cs.CR 2019
Year: 2019

Witness functions have recently been introduced in cryptographic protocols' literature as a new powerful way to prove protocol correctness with respect to secrecy. In this paper, we extend them to the property of authentication. We show how to use them safely and we run an analysis on a modified version of the Woo-Lam protocol. We show that it is correct with respect to authentication.
FAVE: A fast and efficient network Flow AVailability Estimation method with bounded relative error
Venue: arXiv cs.NI 2019
Year: 2019

This paper focuses on helping network providers to carry out network capacity planning and sales projection by answering the question: For a given topology and capacity, whether the network can serve current flow demands with high probabilities? We name such probability as "{\it flow availability}", and present the \underline{f}low \underline{av}ailability \underline{e}stimation (FAVE) problem, which is a generalisation of network connectivity or maximum flow reliability estimations. Realistic networks are often large and dynamic, so flow availabilities cannot be evaluated analytically and simulation is often used. However, naive Monte Carlo (MC) or importance sampling (IS) techniques take an excessive amount of time. To quickly estimate flow availabilities, we utilize the correlations among link and flow failures to figure out the importance of roles played by different links in flow failures, and design three "sequential importance sampling" (SIS) methods which achieve "bounded or even vanishing relative error" with linear computational complexities. When applying to a realistic network, our method reduces the flow availability estimation cost by 900 and 130 times compared with MC and baseline IS methods, respectively. Our method can also facilitate capacity planning by providing better flow availability guarantees, compared with traditional methods.
Hadoop Perfect File: A fast access container for small files with direct in disc metadata access
Venue: arXiv cs.DC 2019
Year: 2019

Storing and processing massive small files is one of the major challenges for the Hadoop Distributed File System (HDFS). In order to provide fast data access, the NameNode (NN) in HDFS maintains the metadata of all files in its main-memory. Hadoop performs well with a small number of large files that require relatively little metadata in the NN s memory. But for a large number of small files, Hadoop has problems such as NN memory overload caused by the huge metadata size of these small files. We present a new type of archive file, Hadoop Perfect File (HPF), to solve HDFS s small files problem by merging small files into a large file on HDFS. Existing archive files offer limited functionality and have poor performance when accessing a file in the merged file due to the fact that during metadata lookup it is necessary to read and process the entire index file(s). In contrast, HPF file can directly access the metadata of a particular file from its index file without having to process it entirely. The HPF index system uses two hash functions: file s metadata are distributed through index files by using a dynamic hash function and, for each index file, we build an order preserving perfect hash function that preserves the position of each file s metadata in the index file. The HPF design will only read the part of the index file that contains the metadata of the searched file during its access. HPF file also supports the file appending functionality after its creation. Our experiments show that HPF can be more than 40% faster file s access from the original HDFS. If we don t consider the caching effect, HPF s file access is around 179% faster than MapFile and 11294% faster than HAR file. If we consider caching effect, HPF is around 35% faster than MapFile and 105% faster than HAR file.
Sequence Planner - Automated Planning and Control for ROS2-based Collaborative and Intelligent Automation Systems
Venue: arXiv cs.RO 2019
Year: 2019

Systems based on the Robot Operating System (ROS) are easy to extend with new on-line algorithms and devices. However, there is relatively little support for coordinating a large number of heterogeneous sub-systems. In this paper we propose an architecture to model and control collaborative and intelligent automation systems in a hierarchical fashion.
Non-Coherent Joint Transmission in Poisson Cellular Networks Under Pilot Contamination
Venue: arXiv cs.IT 2019
Year: 2019

This paper investigates the performance of downlink cellular networks with non-coherent joint (mutlipoint) transmissions and practical channel estimation. Under a stochastic geometry framework, the spatial average signal-to-noise-ratio (SNR) is characterized, taking into account the effect of channel estimation error due to pilot contamination. A simple, easy to compute SNR expression is obtained under the assumption of randomly generated pilot sequences and minimal prior information about the channels and positions of access points (APs). This SNR expression allows for the efficient joint optimization of critical system design parameters such as number of cooperating APs and training overhead. Among others, it is shown that multipoint transmissions are preferable to conventional (non-cooperative) cellular operation under certain operational conditions. Furthermore, analytical insights are obtained regarding (a) the minimum training overhead required to achieve a given SNR degradation compared to the perfect channel estimation case and (b) the optimal number of cooperating APs when an arbitrarily large training overhead can be afforded. For the latter, in particular, a phase transition phenomenon is identified, where the optimal number of cooperating APs is either finite or infinite, depending on whether the path loss factor is less or equal than a certain value, respectively.