OpenRaiser/Intern-Atlas huggingface dataset:
A Polynomial Time Match Test for Large Classes of Extended Regular Expressions
Venue: arXiv cs.FL 2017
Year: 2017

In the present paper, we study the match test for extended regular expressions. We approach this NP-complete problem by introducing a novel variant of two-way multihead automata, which reveals that the complexity of the match test is determined by a hidden combinatorial property of extended regular expressions, and it shows that a restriction of the corresponding parameter leads to rich classes with a polynomial time match test. For presentational reasons, we use the concept of pattern languages in order to specify extended regular expressions. While this decision, formally, slightly narrows the scope of our results, an extension of our concepts and results to more general notions of extended regular expressions is straightforward.
Incidental or influential? - Challenges in automatically detecting citation importance using publication full texts
Venue: arXiv cs.DL 2017
Year: 2017

This work looks in depth at several studies that have attempted to automate the process of citation importance classification based on the publications full text. We analyse a range of features that have been previously used in this task. Our experimental results confirm that the number of in text references are highly predictive of influence. Contrary to the work of Valenzuela et al. we find abstract similarity one of the most predictive features. Overall, we show that many of the features previously described in literature are not particularly predictive. Consequently, we discuss challenges and potential improvements in the classification pipeline, provide a critical review of the performance of individual features and address the importance of constructing a large scale gold standard reference dataset.
Learning Features from Co-occurrences: A Theoretical Analysis
Venue: arXiv cs.CL 2017
Year: 2017

Representing a word by its co-occurrences with other words in context is an effective way to capture the meaning of the word. However, the theory behind remains a challenge. In this work, taking the example of a word classification task, we give a theoretical analysis of the approaches that represent a word X by a function f(P(C|X)), where C is a context feature, P(C|X) is the conditional probability estimated from a text corpus, and the function f maps the co-occurrence measure to a prediction score. We investigate the impact of context feature C and the function f. We also explain the reasons why using the co-occurrences with multiple context features may be better than just using a single one. In addition, some of the results shed light on the theory of feature learning and machine learning in general.
Defensive Alliances in Graphs of Bounded Treewidth
Venue: arXiv cs.CC 2017
Year: 2017

A set S of vertices of a graph is a defensive alliance if, for each element of S, the majority of its neighbors is in S. The problem of finding a defensive alliance of minimum size in a given graph is NP-hard and there are polynomial-time algorithms if certain parameters are bounded by a fixed constant. In particular, fixed-parameter tractability results have been obtained for some structural parameters such as the vertex cover number. However, for the parameter treewidth, the question of whether the problem is FPT has remained open. This is unfortunate because treewidth is perhaps the most prominent graph parameter and has proven successful for many problems. In this work, we give a negative answer by showing that the problem is W[1]-hard when parameterized by treewidth, which rules out FPT algorithms under common assumptions. This is surprising since the problem is known to be FPT when parameterized by solution size and "subset problems" that satisfy this property usually tend to be FPT for bounded treewidth as well. We prove W[1]-hardness by using techniques from a recent hardness result for the problem of finding so-called secure sets in a graph.
Coalescent-based species tree estimation: a stochastic Farris transform
Venue: arXiv cs.LG 2017
Year: 2017

The reconstruction of a species phylogeny from genomic data faces two significant hurdles: 1) the trees describing the evolution of each individual gene--i.e., the gene trees--may differ from the species phylogeny and 2) the molecular sequences corresponding to each gene often provide limited information about the gene trees themselves. In this paper we consider an approach to species tree reconstruction that addresses both these hurdles. Specifically, we propose an algorithm for phylogeny reconstruction under the multispecies coalescent model with a standard model of site substitution. The multispecies coalescent is commonly used to model gene tree discordance due to incomplete lineage sorting, a well-studied population-genetic effect. In previous work, an information-theoretic trade-off was derived in this context between the number of loci, $m$, needed for an accurate reconstruction and the length of the locus sequences, $k$. It was shown that to reconstruct an internal branch of length $f$, one needs $m$ to be of the order of $1/[f^{2} \sqrt{k}]$. That previous result was obtained under the molecular clock assumption, i.e., under the assumption that mutation rates (as well as population sizes) are constant across the species phylogeny. Here we generalize this result beyond the restrictive molecular clock assumption, and obtain a new reconstruction algorithm that has the same data requirement (up to log factors). Our main contribution is a novel reduction to the molecular clock case under the multispecies coalescent. As a corollary, we also obtain a new identifiability result of independent interest: for any species tree with $n \geq 3$ species, the rooted species tree can be identified from the distribution of its unrooted weighted gene trees even in the absence of a molecular clock.
Developing a concept-level knowledge base for sentiment analysis in Singlish
Venue: arXiv cs.CL 2017
Year: 2017

In this paper, we present Singlish sentiment lexicon, a concept-level knowledge base for sentiment analysis that associates multiword expressions to a set of emotion labels and a polarity value. Unlike many other sentiment analysis resources, this lexicon is not built by manually labeling pieces of knowledge coming from general NLP resources such as WordNet or DBPedia. Instead, it is automatically constructed by applying graph-mining and multi-dimensional scaling techniques on the affective common-sense knowledge collected from three different sources. This knowledge is represented redundantly at three levels: semantic network, matrix, and vector space. Subsequently, the concepts are labeled by emotions and polarity through the ensemble application of spreading activation, neural networks and an emotion categorization model.
Square Deviation Based Symbol-Level Selection for Virtual Full-Duplex Relaying Networks
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, a symbol-level selective transmission for virtual full-duplex (FD) relaying networks is proposed, which aims to mitigate error propagation effects and improve system spectral efficiency. The idea is to allow two half-duplex relays, mimicked as FD relaying, to alternatively serve as transmitter and receiver to forward the source's messages. In this case, each relay predicts the correctly decoded symbols of its received frame, based on the generalized square deviation method, and discard the erroneously decoded symbols, resulting in fewer errors being forwarded to the destination. Then, a modified maximum \textit{a posteriori} receiver at the destination is provided to eliminate the inter-frame interference and identify the positions of discarded symbols from the relays. In addition, the diversity-multiplexing trade-off (DMT) for our proposed scheme is also analysed. It is found that our proposed scheme outperforms the conventional selective decode-and-forward (S-DF) relaying schemes, such as cyclic redundancy check based S-DF and threshold based S-DF, in terms of DMT. Moreover, the bit-error-rate performance are also simulated to confirm the DMT results.
Probabilistic Timed Automata with Clock-Dependent Probabilities
Venue: arXiv cs.LO 2017
Year: 2017

Probabilistic timed automata are classical timed automata extended with discrete probability distributions over edges. We introduce clock-dependent probabilistic timed automata, a variant of probabilistic timed automata in which transition probabilities can depend linearly on clock values. Clock-dependent probabilistic timed automata allow the modelling of a continuous relationship between time passage and the likelihood of system events. We show that the problem of deciding whether the maximum probability of reaching a certain location is above a threshold is undecidable for clock-dependent probabilistic timed automata. On the other hand, we show that the maximum and minimum probability of reaching a certain location in clock-dependent probabilistic timed automata can be approximated using a region-graph-based approach.
Competitive Algorithms for Generalized k-Server in Uniform Metrics
Venue: arXiv cs.DS 2017
Year: 2017

The generalized k-server problem is a far-reaching extension of the k-server problem with several applications. Here, each server $s_i$ lies in its own metric space $M_i$. A request is a k-tuple $r = (r_1,r_2,\dotsc,r_k)$ and to serve it, we need to move some server $s_i$ to the point $r_i \in M_i$, and the goal is to minimize the total distance traveled by the servers. Despite much work, no f(k)-competitive algorithm is known for the problem for k > 2 servers, even for special cases such as uniform metrics and lines. Here, we consider the problem in uniform metrics and give the first f(k)-competitive algorithms for general k. In particular, we obtain deterministic and randomized algorithms with competitive ratio $O(k 2^k)$ and $O(k^3 \log k)$ respectively. Our deterministic bound is based on a novel application of the polynomial method to online algorithms, and essentially matches the long-known lower bound of $2^k-1$. We also give a $2^{2^{O(k)}}$-competitive deterministic algorithm for weighted uniform metrics, which also essentially matches the recent doubly exponential lower bound for the problem.
Autonomous Racing with AutoRally Vehicles and Differential Games
Venue: arXiv cs.RO 2017
Year: 2017

Safe autonomous vehicles must be able to predict and react to the drivers around them. Previous control methods rely heavily on pre-computation and are unable to react to dynamic events as they unfold in real-time. In this paper, we extend Model Predictive Path Integral Control (MPPI) using differential game theory and introduce Best-Response MPPI (BR-MPPI) for real-time multi-vehicle interactions. Experimental results are presented using two AutoRally platforms in a racing format with BR-MPPI competing against a skilled human driver at the Georgia Tech Autonomous Racing Facility.
Linguistic Markers of Influence in Informal Interactions
Venue: arXiv cs.CL 2017
Year: 2017

There has been a long standing interest in understanding `Social Influence' both in Social Sciences and in Computational Linguistics. In this paper, we present a novel approach to study and measure interpersonal influence in daily interactions. Motivated by the basic principles of influence, we attempt to identify indicative linguistic features of the posts in an online knitting community. We present the scheme used to operationalize and label the posts with indicator features. Experiments with the identified features show an improvement in the classification accuracy of influence by 3.15%. Our results illustrate the important correlation between the characteristics of the language and its potential to influence others.
Image-based Proof of Work Algorithm for the Incentivization of Blockchain Archival of Interesting Images
Venue: arXiv cs.CR 2017
Year: 2017

A new variation of blockchain proof of work algorithm is proposed to incentivize the timely execution of image processing algorithms. A sample image processing algorithm is proposed to determine interesting images using analysis of the entropy of pixel subsets within images. The efficacy of the image processing algorithm is examined using two small sets of training and test data. The interesting image algorithm is then integrated into a simplified blockchain mining proof of work algorithm based on Bitcoin. The incentive of cryptocurrency mining is theorized to incentivize the execution of the algorithm and thus the retrieval of images that satisfy a minimum requirement set forth by the interesting image algorithm. The digital storage implications of running an image- based blockchain are then examined mathematically.
Pushing the Limits of Online Auto-tuning: Machine Code Optimization in Short-Running Kernels
Venue: arXiv cs.PF 2017
Year: 2017

We propose an online auto-tuning approach for computing kernels. Differently from existing online auto-tuners, which regenerate code with long compilation chains from the source to the binary code, our approach consists on deploying auto-tuning directly at the level of machine code generation. This allows auto-tuning to pay off in very short-running applications. As a proof of concept, our approach is demonstrated in two benchmarks, which execute during hundreds of milliseconds to a few seconds only. In a CPU-bound kernel, the average speedups achieved are 1.10 to 1.58 depending on the target micro-architecture, up to 2.53 in the most favourable conditions (all run-time overheads included). In a memory-bound kernel, less favourable to our runtime auto-tuning optimizations, the average speedups are 1.04 to 1.10, up to 1.30 in the best configuration. Despite the short execution times of our benchmarks, the overhead of our runtime auto-tuning is between 0.2 and 4.2% only of the total application execution times. By simulating the CPU-bound application in 11 different CPUs, we showed that, despite the clear hardware disadvantage of In-Order (io) cores vs. Out-of-Order (ooo) equivalent cores, online auto-tuning in io CPUs obtained an average speedup of 1.03 and an energy efficiency improvement of 39~\% over the SIMD reference in ooo CPUs.
Compliant Movement Primitives in a Bimanual Setting
Venue: arXiv cs.RO 2017
Year: 2017

Simultaneously achieving low trajectory errors and compliant control \emph{without} explicit models of the task was effectively addressed with Compliant Movement Primitives (CMP). For a single-robot task, this means that it is accurately following its trajectory, but also exhibits compliant behavior in case of perturbations. In this paper we extend this kind of behavior without explicit models to bimanual tasks. In the presence of an external perturbation on any of the robots, they will both move in synchrony in order to maintain their relative posture, and thus not exert force on the object they are carrying. Thus, they will act compliantly in their absolute task, but remain stiff in their relative task. To achieve compliant absolute behavior and stiff relative behavior, we combine joint-space CMPs with the well known symmetric control approach. To reduce the necessary feedback reaction of symmetric control, we further augment it with copying of a virtual force vector at the end-effector, calculated through the measured external joint torques. Real-world results on two Kuka LWR-4 robots in a bimanual setting confirm the applicability of the approach.
Predicting multicellular function through multi-layer tissue networks
Venue: arXiv cs.LG 2017
Year: 2017

Motivation: Understanding functions of proteins in specific human tissues is essential for insights into disease diagnostics and therapeutics, yet prediction of tissue-specific cellular function remains a critical challenge for biomedicine. Results: Here we present OhmNet, a hierarchy-aware unsupervised node feature learning approach for multi-layer networks. We build a multi-layer network, where each layer represents molecular interactions in a different human tissue. OhmNet then automatically learns a mapping of proteins, represented as nodes, to a neural embedding based low-dimensional space of features. OhmNet encourages sharing of similar features among proteins with similar network neighborhoods and among proteins activated in similar tissues. The algorithm generalizes prior work, which generally ignores relationships between tissues, by modeling tissue organization with a rich multiscale tissue hierarchy. We use OhmNet to study multicellular function in a multi-layer protein interaction network of 107 human tissues. In 48 tissues with known tissue-specific cellular functions, OhmNet provides more accurate predictions of cellular function than alternative approaches, and also generates more accurate hypotheses about tissue-specific protein actions. We show that taking into account the tissue hierarchy leads to improved predictive power. Remarkably, we also demonstrate that it is possible to leverage the tissue hierarchy in order to effectively transfer cellular functions to a functionally uncharacterized tissue. Overall, OhmNet moves from flat networks to multiscale models able to predict a range of phenotypes spanning cellular subsystems
Recognizing Abnormal Heart Sounds Using Deep Learning
Venue: arXiv cs.SD 2017
Year: 2017

The work presented here applies deep learning to the task of automated cardiac auscultation, i.e. recognizing abnormalities in heart sounds. We describe an automated heart sound classification algorithm that combines the use of time-frequency heat map representations with a deep convolutional neural network (CNN). Given the cost-sensitive nature of misclassification, our CNN architecture is trained using a modified loss function that directly optimizes the trade-off between sensitivity and specificity. We evaluated our algorithm at the 2016 PhysioNet Computing in Cardiology challenge where the objective was to accurately classify normal and abnormal heart sounds from single, short, potentially noisy recordings. Our entry to the challenge achieved a final specificity of 0.95, sensitivity of 0.73 and overall score of 0.84. We achieved the greatest specificity score out of all challenge entries and, using just a single CNN, our algorithm differed in overall score by only 0.02 compared to the top place finisher, which used an ensemble approach.
A Novel Airborne Self-organising Architecture for 5G+ Networks
Venue: arXiv cs.NI 2017
Year: 2017

Network Flying Platforms (NFPs) such as unmanned aerial vehicles, unmanned balloons or drones flying at low/medium/high altitude can be employed to enhance network coverage and capacity by deploying a swarm of flying platforms that implement novel radio resource management techniques. In this paper, we propose a novel layered architecture where NFPs, of various types and flying at low/medium/high layers in a swarm of flying platforms, are considered as an integrated part of the future cellular networks to inject additional capacity and expand the coverage for exceptional scenarios (sports events, concerts, etc.) and hard-to-reach areas (rural or sparsely populated areas). Successful roll-out of the proposed architecture depends on several factors including, but are not limited to: network optimisation for NFP placement and association, safety operations of NFP for network/equipment security, and reliability for NFP transport and control/signaling mechanisms. In this work, we formulate the optimum placement of NFP at a Lower Layer (LL) by exploiting the airborne Self-organising Network (SON) features. Our initial simulations show the NFP-LL can serve more User Equipment (UE)s using this placement technique.
Binarized Convolutional Neural Networks with Separable Filters for Efficient Hardware Acceleration
Venue: arXiv cs.CV 2017
Year: 2017

State-of-the-art convolutional neural networks are enormously costly in both compute and memory, demanding massively parallel GPUs for execution. Such networks strain the computational capabilities and energy available to embedded and mobile processing platforms, restricting their use in many important applications. In this paper, we push the boundaries of hardware-effective CNN design by proposing BCNN with Separable Filters (BCNNw/SF), which applies Singular Value Decomposition (SVD) on BCNN kernels to further reduce computational and storage complexity. To enable its implementation, we provide a closed form of the gradient over SVD to calculate the exact gradient with respect to every binarized weight in backward propagation. We verify BCNNw/SF on the MNIST, CIFAR-10, and SVHN datasets, and implement an accelerator for CIFAR-10 on FPGA hardware. Our BCNNw/SF accelerator realizes memory savings of 17% and execution time reduction of 31.3% compared to BCNN with only minor accuracy sacrifices.
Modified Alpha-Rooting Color Image Enhancement Method On The Two-Side 2-D Quaternion Discrete Fourier Transform And The 2-D Discrete Fourier Transform
Venue: arXiv cs.CV 2017
Year: 2017

Color in an image is resolved into 3 or 4 color components and 2-Dimages of these components are stored in separate channels. Most of the color image enhancement algorithms are applied channel-by-channel on each image. But such a system of color image processing is not processing the original color. When a color image is represented as a quaternion image, processing is done in original colors. This paper proposes an implementation of the quaternion approach of enhancement algorithm for enhancing color images and is referred as the modified alpha-rooting by the two-dimensional quaternion discrete Fourier transform (2-D QDFT). Enhancement results of this proposed method are compared with the channel-by-channel image enhancement by the 2-D DFT. Enhancements in color images are quantitatively measured by the color enhancement measure estimation (CEME), which allows for selecting optimum parameters for processing by the genetic algorithm. Enhancement of color images by the quaternion based method allows for obtaining images which are closer to the genuine representation of the real original color.
MPIgnite: An MPI-Like Language and Prototype Implementation for Apache Spark
Venue: arXiv cs.DC 2017
Year: 2017

Scale-out parallel processing based on MPI is a 25-year-old standard with at least another decade of preceding history of enabling technologies in the High Performance Computing community. Newer frameworks such as MapReduce, Hadoop, and Spark represent industrial scalable computing solutions that have received broad adoption because of their comparative simplicity of use, applicability to relevant problems, and ability to harness scalable, distributed resources. While MPI provides performance and portability, it lacks in productivity and fault tolerance. Likewise, Spark is a specific example of a current-generation MapReduce and data-parallel computing infrastructure that addresses those goals but in turn lacks peer communication support to allow featherweight, highly scalable peer-to-peer data-parallel code sections. The key contribution of this paper is to demonstrate how to introduce the collective and point-to-point peer communication concepts of MPI into a Spark environment. This is done in order to produce performance-portable, peer-oriented and group-oriented communication services while retaining the essential, desirable properties of Spark. Additional concepts of fault tolerance and productivity are considered. This approach is offered in contrast to adding MapReduce framework as upper-middleware based on a traditional MPI implementation as baseline infrastructure.