OpenRaiser/Intern-Atlas huggingface dataset:
Graphical Conjunctive Queries
Venue: arXiv cs.LO 2018
Year: 2018

The Calculus of Conjunctive Queries (CCQ) has foundational status in database theory. A celebrated theorem of Chandra and Merlin states that CCQ query inclusion is decidable. Its proof transforms logical formulas to graphs: each query has a natural model - a kind of graph - and query inclusion reduces to the existence of a graph homomorphism between natural models. We introduce the diagrammatic language Graphical Conjunctive Queries (GCQ) and show that it has the same expressivity as CCQ. GCQ terms are string diagrams, and their algebraic structure allows us to derive a sound and complete axiomatisation of query inclusion, which turns out to be exactly Carboni and Walters' notion of cartesian bicategory of relations. Our completeness proof exploits the combinatorial nature of string diagrams as (certain cospans of) hypergraphs: Chandra and Merlin's insights inspire a theorem that relates such cospans with spans. Completeness and decidability of the (in)equational theory of GCQ follow as a corollary. Categorically speaking, our contribution is a model-theoretic completeness theorem of free cartesian bicategories (on a relational signature) for the category of sets and relations.
Evolution of a Functionally Diverse Swarm via a Novel Decentralised Quality-Diversity Algorithm
Venue: arXiv cs.NE 2018
Year: 2018

The presence of functional diversity within a group has been demonstrated to lead to greater robustness, higher performance and increased problem-solving ability in a broad range of studies that includes insect groups, human groups and swarm robotics. Evolving group diversity however has proved challenging within Evolutionary Robotics, requiring reproductive isolation and careful attention to population size and selection mechanisms. To tackle this issue, we introduce a novel, decentralised, variant of the MAP-Elites illumination algorithm which is hybridised with a well-known distributed evolutionary algorithm (mEDEA). The algorithm simultaneously evolves multiple diverse behaviours for multiple robots, with respect to a simple token-gathering task. Each robot in the swarm maintains a local archive defined by two pre-specified functional traits which is shared with robots it come into contact with. We investigate four different strategies for sharing, exploiting and combining local archives and compare results to mEDEA. Experimental results show that in contrast to previous claims, it is possible to evolve a functionally diverse swarm without geographical isolation, and that the new method outperforms mEDEA in terms of the diversity, coverage and precision of the evolved swarm.
Modelling customer online behaviours with neural networks: applications to conversion prediction and advertising retargeting
Venue: arXiv cs.LG 2018
Year: 2018

In this paper, we apply neural networks into digital marketing world for the purpose of better targeting the potential customers. To do so, we model the customer online behaviours using dedicated neural network architectures. Starting from user searched keywords in a search engine to the landing page and different following pages, until the user left the site, we model the whole visited journey with a Recurrent Neural Network (RNN), together with Convolution Neural Networks (CNN) that can take into account of the semantic meaning of user searched keywords and different visited page names. With such model, we use Monte Carlo simulation to estimate the conversion rates of each potential customer in the future visiting. We believe our concept and the preliminary promising results in this paper enable the use of largely available customer online behaviours data for advanced digital marketing analysis.
twAwler: A lightweight twitter crawler
Venue: arXiv cs.SI 2018
Year: 2018

This paper presents twAwler, a lightweight twitter crawler that targets language-specific communities of users. twAwler takes advantage of multiple endpoints of the twitter API to explore user relations and quickly recognize users belonging to the targetted set. It performs a complete crawl for all users, discovering many standard user relations, including the retweet graph, mention graph, reply graph, quote graph, follow graph, etc. twAwler respects all twitter policies and rate limits, while able to monitor large communities of active users. twAwler was used between August 2016 and March 2018 to generate an extensive dataset of close to all Greek-speaking twitter accounts (about 330 thousand) and their tweets and relations. In total, the crawler has gathered 750 million tweets of which 424 million are in Greek; 750 million follow relations; information about 300 thousand lists, their members (119 million member relations) and subscribers (27 thousand subscription relations); 705 thousand trending topics; information on 52 million users in total of which 292 thousand have been since suspended, 141 thousand have deleted their account, and 3.5 million are protected and cannot be crawled. twAwler mines the collected tweets for the retweet, quote, reply, and mention graphs, which, in addition to the follow relation crawled, offer vast opportunities for analysis and further research.
The Statistical Model for Ticker, an Adaptive Single-Switch Text-Entry Method for Visually Impaired Users
Venue: arXiv cs.AI 2018
Year: 2018

This paper presents the statistical model for Ticker [1], a novel probabilistic stereophonic single-switch text entry method for visually-impaired users with motor disabilities who rely on single-switch scanning systems to communicate. All terminology and notation are defined in [1].
An Aggregated Multicolumn Dilated Convolution Network for Perspective-Free Counting
Venue: arXiv cs.CV 2018
Year: 2018

We propose the use of dilated filters to construct an aggregation module in a multicolumn convolutional neural network for perspective-free counting. Counting is a common problem in computer vision (e.g. traffic on the street or pedestrians in a crowd). Modern approaches to the counting problem involve the production of a density map via regression whose integral is equal to the number of objects in the image. However, objects in the image can occur at different scales (e.g. due to perspective effects) which can make it difficult for a learning agent to learn the proper density map. While the use of multiple columns to extract multiscale information from images has been shown before, our approach aggregates the multiscale information gathered by the multicolumn convolutional neural network to improve performance. Our experiments show that our proposed network outperforms the state-of-the-art on many benchmark datasets, and also that using our aggregation module in combination with a higher number of columns is beneficial for multiscale counting.
A New Formulation of The Shortest Path Problem with On-Time Arrival Reliability
Venue: arXiv cs.DB 2018
Year: 2018

We study stochastic routing in the PAth-CEntric (PACE) uncertain road network model. In the PACE model, uncertain travel times are associated with not only edges but also some paths. The uncertain travel times associated with paths are able to well capture the travel time dependency among different edges. This significantly improves the accuracy of travel time distribution estimations for arbitrary paths, which is a fundamental functionality in stochastic routing, compared to classic uncertain road network models where uncertain travel times are associated with only edges. We investigate a new formulation of the shortest path with on-time arrival reliability (SPOTAR) problem under the PACE model. Given a source, a destination, and a travel time budget, the SPOTAR problem aims at finding a path that maximizes the on-time arrival probability. We develop a generic algorithm with different speed-up strategies to solve the SPOTAR problem under the PACE model. Empirical studies with substantial GPS trajectory data offer insight into the design properties of the proposed algorithm and confirm that the algorithm is effective. This report extends the paper "Stochastic Shortest Path Finding in Path-Centric Uncertain Road Networks", to appear in IEEE MDM 2018, by providing a concrete running example of the studied SPOTAR problem in the PACE model and additional statistics of the used GPS trajectories in the experiments.
Sherali-Adams Integrality Gaps Matching the Log-Density Threshold
Venue: arXiv cs.DS 2018
Year: 2018

The log-density method is a powerful algorithmic framework which in recent years has given rise to the best-known approximations for a variety of problems, including Densest-$k$-Subgraph and Bipartite Small Set Vertex Expansion. These approximations have been conjectured to be optimal based on various instantiations of a general conjecture: that it is hard to distinguish a fully random combinatorial structure from one which contains a similar planted sub-structure with the same "log-density". We bolster this conjecture by showing that in a random hypergraph with edge probability $n^{-α}$, $\tildeΩ(\log n)$ rounds of Sherali-Adams with cannot rule out the existence of a $k$-subhypergraph with edge density $k^{-α-o(1)}$, for any $k$ and $α$. This holds even when the bound on the objective function is lifted. This gives strong integrality gaps which exactly match the gap in the above distinguishing problems, as well as the best-known approximations, for Densest $k$-Subgraph, Smallest $p$-Edge Subgraph, their hypergraph extensions, and Small Set Bipartite Vertex Expansion (or equivalently, Minimum $p$-Union). Previously, such integrality gaps were known only for Densest $k$-Subgraph for one specific parameter setting.
Is feature selection secure against training data poisoning?
Venue: arXiv cs.LG 2018
Year: 2018

Learning in adversarial settings is becoming an important task for application domains where attackers may inject malicious data into the training set to subvert normal operation of data-driven technologies. Feature selection has been widely used in machine learning for security applications to improve generalization and computational efficiency, although it is not clear whether its use may be beneficial or even counterproductive when training data are poisoned by intelligent attackers. In this work, we shed light on this issue by providing a framework to investigate the robustness of popular feature selection methods, including LASSO, ridge regression and the elastic net. Our results on malware detection show that feature selection methods can be significantly compromised under attack (we can reduce LASSO to almost random choices of feature sets by careful insertion of less than 5% poisoned training samples), highlighting the need for specific countermeasures.
Predicting User Performance and Bitcoin Price Using Block Chain Transaction Network
Venue: arXiv cs.SI 2018
Year: 2018

This work is organized as follows. In the first section we review the prior work and we have obtained our data. Next, we will look at address reuse in the Bitcoin network. We show that a great portion of users reuse their addresses which could enable us to cluster the addresses and attribute them to single users. Next, we will categorize the nodes based on their role in the network as a customer or seller. Finally, we do a study of nodes and network performance.
Anchor-based Nearest Class Mean Loss for Convolutional Neural Networks
Venue: arXiv cs.CV 2018
Year: 2018

Discriminative features are critical for machine learning applications. Most existing deep learning approaches, however, rely on convolutional neural networks (CNNs) for learning features, whose discriminant power is not explicitly enforced. In this paper, we propose a novel approach to train deep CNNs by imposing the intra-class compactness and the inter-class separability, so as to enhance the learned features' discriminant power. To this end, we introduce anchors, which are predefined vectors regarded as the centers for each class and fixed during training. Discriminative features are obtained by constraining the deep CNNs to map training samples to the corresponding anchors as close as possible. We propose two principles to select the anchors, and measure the proximity of two points using the Euclidean and cosine distance metric functions, which results in two novel loss functions. These loss functions require no sample pairs or triplets and can be efficiently optimized by batch stochastic gradient descent. We test the proposed method on three benchmark image classification datasets and demonstrate its promising results.
IIIDYT at SemEval-2018 Task 3: Irony detection in English tweets
Venue: arXiv cs.CL 2018
Year: 2018

In this paper we introduce our system for the task of Irony detection in English tweets, a part of SemEval 2018. We propose representation learning approach that relies on a multi-layered bidirectional LSTM, without using external features that provide additional semantic information. Although our model is able to outperform the baseline in the validation set, our results show limited generalization power over the test set. Given the limited size of the dataset, we think the usage of more pre-training schemes would greatly improve the obtained results.
Swarm robotics in wireless distributed protocol design for coordinating robots involved in cooperative tasks
Venue: arXiv cs.AI 2018
Year: 2018

The mine detection in an unexplored area is an optimization problem where multiple mines, randomly distributed throughout an area, need to be discovered and disarmed in a minimum amount of time. We propose a strategy to explore an unknown area, using a stigmergy approach based on ants behavior, and a novel swarm based protocol to recruit and coordinate robots for disarming the mines cooperatively. Simulation tests are presented to show the effectiveness of our proposed Ant-based Task Robot Coordination (ATRC) with only the exploration task and with both exploration and recruiting strategies. Multiple minimization objectives have been considered: the robots' recruiting time and the overall area exploration time. We discuss, through simulation, different cases under different network and field conditions, performed by the robots. The results have shown that the proposed decentralized approaches enable the swarm of robots to perform cooperative tasks intelligently without any central control.
A Primal-Dual Online Deterministic Algorithm for Matching with Delays
Venue: arXiv cs.DS 2018
Year: 2018

In the Min-cost Perfect Matching with Delays (MPMD) problem, 2 m requests arrive over time at points of a metric space. An online algorithm has to connect these requests in pairs, but a decision to match may be postponed till a more suitable matching pair is found. The goal is to minimize the joint cost of connection and the total waiting time of all requests. We present an O(m)-competitive deterministic algorithm for this problem, improving on an existing bound of O(m^(log(5.5))) = O(m^2.46). Our algorithm also solves (with the same competitive ratio) a bipartite variant of MPMD, where requests are either positive or negative and only requests with different polarities may be matched with each other. Unlike the existing randomized solutions, our approach does not depend on the size of the metric space and does not have to know it in advance.
Rician $K$-Factor-Based Analysis of XLOS Service Probability in 5G Outdoor Ultra-Dense Networks
Venue: arXiv cs.IT 2018
Year: 2018

In this report, we introduce the concept of Rician $K$-factor-based radio resource and mobility management for fifth generation (5G) ultra-dense networks (UDN), where the information on the gradual visibility between the new radio node B (gNB) and the user equipment (UE)---dubbed X-line-of-sight (XLOS)---would be required. We therefore start by presenting the XLOS service probability as a new performance indicator; taking into account both the UE serving and neighbor cells. By relying on a lognormal $K$-factor model, a closed-form expression of the XLOS service probability in a 5G outdoor UDN is derived in terms of the multivariate Fox H-function; wherefore we develop a GPU-enabled MATLAB routine and automate the definition of the underlying Mellin-Barnes contour via linear optimization. Residue theory is then applied to infer the relevant asymptotic behavior and show its practical implications. Finally, numerical results are provided for various network configurations, and underpinned by extensive Monte-Carlo simulations.
Performance Impact Caused by Hidden Bias of Training Data for Recognizing Textual Entailment
Venue: arXiv cs.CL 2018
Year: 2018

The quality of training data is one of the crucial problems when a learning-centered approach is employed. This paper proposes a new method to investigate the quality of a large corpus designed for the recognizing textual entailment (RTE) task. The proposed method, which is inspired by a statistical hypothesis test, consists of two phases: the first phase is to introduce the predictability of textual entailment labels as a null hypothesis which is extremely unacceptable if a target corpus has no hidden bias, and the second phase is to test the null hypothesis using a Naive Bayes model. The experimental result of the Stanford Natural Language Inference (SNLI) corpus does not reject the null hypothesis. Therefore, it indicates that the SNLI corpus has a hidden bias which allows prediction of textual entailment labels from hypothesis sentences even if no context information is given by a premise sentence. This paper also presents the performance impact of NN models for RTE caused by this hidden bias.
Matching Fingerphotos to Slap Fingerprint Images
Venue: arXiv cs.CV 2018
Year: 2018

We address the problem of comparing fingerphotos, fingerprint images from a commodity smartphone camera, with the corresponding legacy slap contact-based fingerprint images. Development of robust versions of these technologies would enable the use of the billions of standard Android phones as biometric readers through a simple software download, dramatically lowering the cost and complexity of deployment relative to using a separate fingerprint reader. Two fingerphoto apps running on Android phones and an optical slap reader were utilized for fingerprint collection of 309 subjects who primarily work as construction workers, farmers, and domestic helpers. Experimental results show that a True Accept Rate (TAR) of 95.79 at a False Accept Rate (FAR) of 0.1% can be achieved in matching fingerphotos to slaps (two thumbs and two index fingers) using a COTS fingerprint matcher. By comparison, a baseline TAR of 98.55% at 0.1% FAR is achieved when matching fingerprint images from two different contact-based optical readers. We also report the usability of the two smartphone apps, in terms of failure to acquire rate and fingerprint acquisition time. Our results show that fingerphotos are promising to authenticate individuals (against a national ID database) for banking, welfare distribution, and healthcare applications in developing countries.
Active Authentication of Keyboard Users: Performance Evaluation on 736 Subjects
Venue: arXiv cs.CR 2018
Year: 2018

Keystroke timing based active authentication systems are conceptually attractive because: (i) they use the keyboard as the sensor and are not hardware-cost prohibitive, and (ii) they use the keystrokes generated from normal usage of computers as input and are not interruptive. Several experiments have been reported on the performance of keystroke based authentication using small datasets. None of them, however, study a practical active authentication system, and the feasibility of keystroke based active authentication system for large scale and continuous deployment is still not demonstrated in the literature. We investigate this issue and establish that keystroke based active authentication systems can be highly accurate and scalable. We use a real active authentication system that we developed and analyze a dataset large enough to produce statistically significant results. We also present empirical methodologies used for characterizing various design parameters of the developed system.
Adaptive Performance Assessment For Drivers Through Behavioral Advantage
Venue: arXiv cs.LG 2018
Year: 2018

The potential positive impact of autonomous driving and driver assistance technolo- gies have been a major impetus over the last decade. On the flip side, it has been a challenging problem to analyze the performance of human drivers or autonomous driving agents quantitatively. In this work, we propose a generic method that compares the performance of drivers or autonomous driving agents even if the environmental conditions are different, by using the driver behavioral advantage instead of absolute metrics, which efficiently removes the environmental factors. A concrete application of the method is also presented, where the performance of more than 100 truck drivers was evaluated and ranked in terms of fuel efficiency, covering more than 90,000 trips spanning an average of 300 miles in a variety of driving conditions and environments.
PlusEmo2Vec at SemEval-2018 Task 1: Exploiting emotion knowledge from emoji and #hashtags
Venue: arXiv cs.CL 2018
Year: 2018

This paper describes our system that has been submitted to SemEval-2018 Task 1: Affect in Tweets (AIT) to solve five subtasks. We focus on modeling both sentence and word level representations of emotion inside texts through large distantly labeled corpora with emojis and hashtags. We transfer the emotional knowledge by exploiting neural network models as feature extractors and use these representations for traditional machine learning models such as support vector regression (SVR) and logistic regression to solve the competition tasks. Our system is placed among the Top3 for all subtasks we participated.
Minimum Symbol Error Rate-Based Constant Envelope Precoding for Multiuser Massive MISO Downlink
Venue: arXiv cs.IT 2018
Year: 2018

This paper considers the problem of constant envelope (CE) precoder designs for multiuser massive MISO downlink channels. The use of CE signals allows one to employ low-cost radio frequency chains and thereby facilitates the implementation of massive MIMO. However, the subsequent CE precoder designs are usually challenging owing to the non-convex CE constraints. The existing CE precoder designs consider minimization of some measures on the distortion levels of the received symbols, and they usually aim at improving the symbol-error rate (SER) performances. In this paper we formulate a minimum SER-based design for CE precoding. The design formulation is non-convex and we propose two low-complexity first-order algorithms using gradient projection. Curiously, our simulation results show that the proposed designs can achieve bit-error rate performance close to that of zero-forcing beamforming without CE signaling restrictions.
Convolutional capsule network for classification of breast cancer histology images
Venue: arXiv cs.CV 2018
Year: 2018

Automatization of the diagnosis of any kind of disease is of great importance and it's gaining speed as more and more deep learning solutions are applied to different problems. One of such computer aided systems could be a decision support too able to accurately differentiate between different types of breast cancer histological images - normal tissue or carcinoma. In this paper authors present a deep learning solution, based on convolutional capsule network for classification of four types of images of breast tissue biopsy when hematoxylin and eusin staining is applied. The cross-validation accuracy was achieved to be 0.87 with equaly high sensitivity.