OpenRaiser/Intern-Atlas huggingface dataset:
Clinically Meaningful Comparisons Over Time: An Approach to Measuring Patient Similarity based on Subsequence Alignment
Venue: arXiv cs.LG 2018
Year: 2018

Longitudinal patient data has the potential to improve clinical risk stratification models for disease. However, chronic diseases that progress slowly over time are often heterogeneous in their clinical presentation. Patients may progress through disease stages at varying rates. This leads to pathophysiological misalignment over time, making it difficult to consistently compare patients in a clinically meaningful way. Furthermore, patients present clinically for the first time at different stages of disease. This eliminates the possibility of simply aligning patients based on their initial presentation. Finally, patient data may be sampled at different rates due to differences in schedules or missed visits. To address these challenges, we propose a robust measure of patient similarity based on subsequence alignment. Compared to global alignment techniques that do not account for pathophysiological misalignment, focusing on the most relevant subsequences allows for an accurate measure of similarity between patients. We demonstrate the utility of our approach in settings where longitudinal data, while useful, are limited and lack a clear temporal alignment for comparison. Applied to the task of stratifying patients for risk of progression to probable Alzheimer's Disease, our approach outperforms models that use only snapshot data (AUROC of 0.839 vs. 0.812) and models that use global alignment techniques (AUROC of 0.822). Our results support the hypothesis that patients' trajectories are useful for quantifying inter-patient similarities and that using subsequence matching and can help account for heterogeneity and misalignment in longitudinal data.
Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket
Venue: arXiv cs.DS 2018
Year: 2018

As a fundamental subject of theoretical computer science, the maximum independent set (MIS) problem not only is of purely theoretical interest, but also has found wide applications in various fields. However, for a general graph determining the size of a MIS is NP-hard, and exact computation of the number of all MISs is even more difficult. It is thus of significant interest to seek special graphs for which the MIS problem can be exactly solved. In this paper, we address the MIS problem in the pseudofractal scale-free web and the Sierpiński gasket, which have the same number of vertices and edges. For both graphs, we determine exactly the independence number and the number of all possible MISs. The independence number of the pseudofractal scale-free web is as twice as the one of the Sierpiński gasket. Moreover, the pseudofractal scale-free web has a unique MIS, while the number of MISs in the Sierpiński gasket grows exponentially with the number of vertices.
Towards a Question Answering System over the Semantic Web
Venue: arXiv cs.AI 2018
Year: 2018

Thanks to the development of the Semantic Web, a lot of new structured data has become available on the Web in the form of knowledge bases (KBs). Making this valuable data accessible and usable for end-users is one of the main goals of Question Answering (QA) over KBs. Most current QA systems query one KB, in one language (namely English). The existing approaches are not designed to be easily adaptable to new KBs and languages. We first introduce a new approach for translating natural language questions to SPARQL queries. It is able to query several KBs simultaneously, in different languages, and can easily be ported to other KBs and languages. In our evaluation, the impact of our approach is proven using 5 different well-known and large KBs: Wikidata, DBpedia, MusicBrainz, DBLP and Freebase as well as 5 different languages namely English, German, French, Italian and Spanish. Second, we show how we integrated our approach, to make it easily accessible by the research community and by end-users. To summarize, we provided a conceptional solution for multilingual, KB-agnostic Question Answering over the Semantic Web. The provided first approximation validates this concept.
Beyond series-parallel concurrent systems: the case of arch processes
Venue: arXiv cs.DM 2018
Year: 2018

In this paper we focus on concurrent processes built on synchronization by means of futures. This concept is an abstraction for processes based on a main execution thread but allowing to delay some computations. The structure of a general concurrent process with futures is more or less a directed acyclic graph. Since the quantitative study of such increasingly labeled graphs (directly related to processes) seems out of reach, we restrict ourselves to the study of arch processes, a simplistic model of processes with futures. They are based on two parameters related to their sizes and their numbers of arches. The increasingly labeled structures seems not to be specifiable in the sense of Analytic Combinatorics, but we manage to derive a recurrence equation for the enumeration. For this model we first exhibit an exact and an asymptotic formula for the number of runs of a given process. The second main contribution is composed of an uniform random sampler algorithm and an unranking one that allow efficient generation and exhaustive enumeration of the runs of a given arch process.
Estimating Total Search Space Size for Specific Piece Sets in Chess
Venue: arXiv cs.AI 2018
Year: 2018

Automatic chess problem or puzzle composition typically involves generating and testing various different positions, sometimes using particular piece sets. Once a position has been generated, it is then usually tested for positional legality based on the game rules. However, it is useful to be able to estimate what the search space size for particular piece combinations is to begin with. So if a desirable chess problem was successfully generated by examining 'merely' 100,000 or so positions in a theoretical search space of about 100 billion, this would imply the composing approach used was quite viable and perhaps even impressive. In this article, I explain a method of calculating the size of this search space using a combinatorics and permutations approach. While the mathematics itself may already be established, a precise method and justification of applying it with regard to the chessboard and chess pieces has not been documented, to the best of our knowledge. Additionally, the method could serve as a useful starting point for further estimations of search space size which filter out positions for legality and rotation, depending on how the automatic composer is allowed to place pieces on the board (because this affects its total search space size).
fCDN: A Flexible and Efficient CDN Infrastructure without DNS Redirection or Content Reflection
Venue: arXiv cs.NI 2018
Year: 2018

Flexible and efficient CDNs are critical to facilitate content distribution in 5G+ architectures. Current CDNs suffer from inefficient request mapping based on DNS redirection, and inefficient content distribution from origin to edge servers, through content reflection. We proposes a novel, flexible CDN architecture that removes the need for DNS-based mapping and content reflection. Instead, requests to/from the CDN are treated as service transactions in the network, which utilises a routing function embraced from emerging research in Information-Centric Networks (ICN) to route edge-to-edge transactions to the true nearest service point. The same function is utilized to establish path-based flows over a fast forwarding substrate; thereby, eliminating the need for IP routing between service points within a single domain, and potentially at peering points with other domains. We model our architecture and formulate the resource placement problem as a variance of the K-center problem. To address the problem, we propose a greedy algorithm, Swing, that balances the placement of service points between highly and poorly connected nodes. We evaluate the efficiency of our architecture in utilising the CDN and network resources through Monte Carlo simulations that explore a range of K values. Moreover, we compare the goodness of the placement solutions provided by Swing with those provided by Largest First and Closest First Algorithms. Evaluation results show the superiority of our fCDN solution in reducing the edge-to-edge path length and the required network resources.
An Experimental Study of Factor Analysis over Cellular Network Data
Venue: arXiv cs.NI 2018
Year: 2018

Mobile Network Operators (MNOs) are evolving towards becoming data-driven, while delivering capacity to collect and analyze data. This can help in enhancing user experiences while empowering the operation workforce and building new business models. Mobile traffic demands of users can give insights to MNOs to plan, decide and act depending on network conditions. In this paper, we investigate the behaviour of Istanbul residents using the cellular network traffic activity over spatial and temporal dimensions via exploratory factor analysis (EFA) using a major MNO's cellular network traffic data in Turkey. Our results reveal various time and spatial patterns for Istanbul residents such as morning and evening commuting factors, business and residential factors as well as nightlife and weekend afternoon factors as the most prominent cultural behaviour. The analysis results also demonstrate interesting findings such as tunnels and transportation paths selected by Istanbul residents may differ during morning rush work hour compared to evening rush after-work hour.
Niching an Archive-based Gaussian Estimation of Distribution Algorithm via Adaptive Clustering
Venue: arXiv cs.NE 2018
Year: 2018

As a model-based evolutionary algorithm, estimation of distribution algorithm (EDA) possesses unique characteristics and has been widely applied to global optimization. However, traditional Gaussian EDA (GEDA) may suffer from premature convergence and has a high risk of falling into local optimum when dealing with multimodal problem. In this paper, we first attempts to improve the performance of GEDA by utilizing historical solutions and develops a novel archive-based EDA variant. The use of historical solutions not only enhances the search efficiency of EDA to a large extent, but also significantly reduces the population size so that a faster convergence could be achieved. Then, the archive-based EDA is further integrated with a novel adaptive clustering strategy for solving multimodal optimization problems. Taking the advantage of the clustering strategy in locating different promising areas and the powerful exploitation ability of the archive-based EDA, the resultant algorithm is endowed with strong capability in finding multiple optima. To verify the efficiency of the proposed algorithm, we tested it on a set of well-known niching benchmark problems and compared it with several state-of-the-art niching algorithms. The experimental results indicate that the proposed algorithm is competitive.
Secure and Privacy-Aware Data Dissemination for Cloud-Based Applications
Venue: arXiv cs.DC 2018
Year: 2018

In this paper we propose a data dissemination platform that supports data security and different privacy levels even when the platform and the data are hosted by untrusted infrastructures. The proposed system aims at enabling an application ecosystem that uses off-the-shelf trusted platforms (in this case, Intel SGX), so that users may allow or disallow third parties to access the live data stream with a specific sensitivity-level. Moreover, this approach does not require users to manage the encryption keys directly. Our experiments show that such an approach is indeed practical for medium scale systems, where participants disseminate small volumes of data at a time, such as in smart grids and IoT environments.
Classical Transitions
Venue: arXiv cs.LO 2018
Year: 2018

We introduce the calculus of Classical Transitions (CT), which extends the research line on the relationship between linear logic and processes to labelled transitions. The key twist from previous work is registering parallelism in typing judgements, by generalising linear logic judgements from one sequents to many (hypersequents). This allows us to bridge the gap between the structures of operators used as proof terms in previous work and those of the standard π-calculus (in particular parallel operator and restriction). The proof theory of CT allows for new proof transformations, which we show correspond to a labelled transition system (LTS) for processes. We prove that CT enjoys subject reduction and progress.
Matrix-product structure of constacyclic codes over finite chain rings $\mathbb{F}_{p^m}[u]/\langle u^e\rangle$
Venue: arXiv cs.IT 2018
Year: 2018

Let $m,e$ be positive integers, $p$ a prime number, $\mathbb{F}_{p^m}$ be a finite field of $p^m$ elements and $R=\mathbb{F}_{p^m}[u]/\langle u^e\rangle$ which is a finite chain ring. For any $ω\in R^\times$ and positive integers $k, n$ satisfying ${\rm gcd}(p,n)=1$, we prove that any $(1+ωu)$-constacyclic code of length $p^kn$ over $R$ is monomially equivalent to a matrix-product code of a nested sequence of $p^k$ cyclic codes with length $n$ over $R$ and a $p^k\times p^k$ matrix $A_{p^k}$ over $\mathbb{F}_p$. Using the matrix-product structures, we give an iterative construction of every $(1+ωu)$-constacyclic code by $(1+ωu)$-constacyclic codes of shorter lengths over $R$.
State and Parameter Estimation Based on Filtered Transformation for a Class of Second-Order Systems
Venue: arXiv cs.SY 2018
Year: 2018

This paper addresses the problem of state and parameter estimation for a class of second-order systems with single output. A new filtered transformation is proposed for the system via dynamic vector and matrix. In this method, the dynamics of the vector and matrix are derived by immersion and invariance technique such that the state estimation condition is guaranteed. Compared to the classical approaches that persistency of excitation (PE) condition is required for parameter convergence, the proposed method needs a weaker one, so called non-square-integrability condition, in the transformation via dynamic matrix. Simulation results are concluded for a class of regressors which are not PE but satisfy the new condition.
Real-Time Deep Learning Method for Abandoned Luggage Detection in Video
Venue: arXiv cs.CV 2018
Year: 2018

Recent terrorist attacks in major cities around the world have brought many casualties among innocent citizens. One potential threat is represented by abandoned luggage items (that could contain bombs or biological warfare) in public areas. In this paper, we describe an approach for real-time automatic detection of abandoned luggage in video captured by surveillance cameras. The approach is comprised of two stages: (i) static object detection based on background subtraction and motion estimation and (ii) abandoned luggage recognition based on a cascade of convolutional neural networks (CNN). To train our neural networks we provide two types of examples: images collected from the Internet and realistic examples generated by imposing various suitcases and bags over the scene's background. We present empirical results demonstrating that our approach yields better performance than a strong CNN baseline method.
Revisiting Spatial-Temporal Similarity: A Deep Learning Framework for Traffic Prediction
Venue: arXiv cs.LG 2018
Year: 2018

Traffic prediction has drawn increasing attention in AI research field due to the increasing availability of large-scale traffic data and its importance in the real world. For example, an accurate taxi demand prediction can assist taxi companies in pre-allocating taxis. The key challenge of traffic prediction lies in how to model the complex spatial dependencies and temporal dynamics. Although both factors have been considered in modeling, existing works make strong assumptions about spatial dependence and temporal dynamics, i.e., spatial dependence is stationary in time, and temporal dynamics is strictly periodical. However, in practice, the spatial dependence could be dynamic (i.e., changing from time to time), and the temporal dynamics could have some perturbation from one period to another period. In this paper, we make two important observations: (1) the spatial dependencies between locations are dynamic; and (2) the temporal dependency follows daily and weekly pattern but it is not strictly periodic for its dynamic temporal shifting. To address these two issues, we propose a novel Spatial-Temporal Dynamic Network (STDN), in which a flow gating mechanism is introduced to learn the dynamic similarity between locations, and a periodically shifted attention mechanism is designed to handle long-term periodic temporal shifting. To the best of our knowledge, this is the first work that tackles both issues in a unified framework. Our experimental results on real-world traffic datasets verify the effectiveness of the proposed method.
Unsupervised Learning of Face Representations
Venue: arXiv cs.CV 2018
Year: 2018

We present an approach for unsupervised training of CNNs in order to learn discriminative face representations. We mine supervised training data by noting that multiple faces in the same video frame must belong to different persons and the same face tracked across multiple frames must belong to the same person. We obtain millions of face pairs from hundreds of videos without using any manual supervision. Although faces extracted from videos have a lower spatial resolution than those which are available as part of standard supervised face datasets such as LFW and CASIA-WebFace, the former represent a much more realistic setting, e.g. in surveillance scenarios where most of the faces detected are very small. We train our CNNs with the relatively low resolution faces extracted from video frames collected, and achieve a higher verification accuracy on the benchmark LFW dataset cf. hand-crafted features such as LBPs, and even surpasses the performance of state-of-the-art deep networks such as VGG-Face, when they are made to work with low resolution input images.
Learning to Sequence Robot Behaviors for Visual Navigation
Venue: arXiv cs.RO 2018
Year: 2018

Recent literature in the robotics community has focused on learning robot behaviors that abstract out lower-level details of robot control. To fully leverage the efficacy of such behaviors, it is necessary to select and sequence them to achieve a given task. In this paper, we present an approach to both learn and sequence robot behaviors, applied to the problem of visual navigation of mobile robots. We construct a layered representation of control policies composed of low- level behaviors and a meta-level policy. The low-level behaviors enable the robot to locomote in a particular environment while avoiding obstacles, and the meta-level policy actively selects the low-level behavior most appropriate for the current situation based purely on visual feedback. We demonstrate the effectiveness of our method on three simulated robot navigation tasks: a legged hexapod robot which must successfully traverse varying terrain, a wheeled robot which must navigate a maze-like course while avoiding obstacles, and finally a wheeled robot navigating in the presence of dynamic obstacles. We show that by learning control policies in a layered manner, we gain the ability to successfully traverse new compound environments composed of distinct sub-environments, and outperform both the low-level behaviors in their respective sub-environments, as well as a hand-crafted selection of low-level policies on these compound environments.
The Sequent Calculus Trainer with Automated Reasoning - Helping Students to Find Proofs
Venue: arXiv cs.LO 2018
Year: 2018

The sequent calculus is a formalism for proving validity of statements formulated in First-Order Logic. It is routinely used in computer science modules on mathematical logic. Formal proofs in the sequent calculus are finite trees obtained by successively applying proof rules to formulas, thus simplifying them step-by-step. Students often struggle with the mathematical formalities and the level of abstraction that topics like formal logic and formal proofs involve. The difficulties can be categorised as syntactic or semantic. On the syntactic level, students need to understand what a correctly formed proof is, how rules can be applied (on paper for instance) without leaving the mathematical framework of the sequent calculus, and so on. Beyond this, on the semantic level, students need to acquire strategies that let them find the right proof. The Sequent Calculus Trainer is a tool that is designed to aid students in learning the techniques of proving given statements formally. In this paper we describe the didactical motivation behind the tool and the techniques used to address issues on the syntactic as well as on the semantic level.
Exchange of Geometric Information Between Applications
Venue: arXiv cs.CY 2018
Year: 2018

The Web Geometry Laboratory (WGL) is a collaborative and adaptive e-learning Web platform integrating a well known dynamic geometry system. Thousands of Geometric problems for Geometric Theorem Provers (TGTP) is a Web-based repository of geometric problems to support the testing and evaluation of geometric automated theorem proving systems. The users of these systems should be able to profit from each other. The TGTP corpus must be made available to the WGL user, allowing, in this way, the exploration of TGTP problems and their proofs. On the other direction TGTP could gain by the possibility of a wider users base submitting new problems. Such information exchange between clients (e.g. WGL) and servers (e.g. TGTP) raises many issues: geometric search - someone, working in a geometric problem, must be able to ask for more information regarding that construction; levels of geometric knowledge and interest - the problems in the servers must be classified in such a way that, in response to a client query, only the problems in the user's level and/or interest are returned; different aims of each tool - e.g. WGL is about secondary school geometry, TGTP is about formal proofs in semi-analytic and algebraic proof methods, not a perfect match indeed; localisation issues, e.g. a Portuguese user obliged to make the query and process the answer in English; technical issues-many technical issues need to be addressed to make this exchange of geometric information possible and useful. Instead of a giant (difficult to maintain) tool, trying to cover all, the interconnection of specialised tools seems much more promising. The challenges to make that connection work are many and difficult, but, it is the authors impression, not insurmountable.
Optimal and Suboptimal Routing Based on Partial CSI in Random Ad-hoc Networks
Venue: arXiv cs.IT 2018
Year: 2018

In this paper we consider routing in random wireless-adhoc-networks (WANETs), where each node is equipped with a single antenna. Our analysis uses a proper model of the physical layer together with an abstraction of higher communication layers. We assume that the nodes are distributed according to a Poisson-point-process and consider routing schemes that select the next relay based on the geographical locations, the channel gains of its neighbor nodes and the statistical characterization of all other nodes. While many routing problems are formulated as optimization problems, the optimal distributed solution is rarely accessible. In this work, we present the exact optimal solution for the scenario analyzed. The optimal routing is given as a maximization of a routing metric which depends solely on the known partial channel state information (CSI) and includes an expectation with respect to the interference statistics. The optimal routing scheme is important because it gives an upper bound on the performance of any other routing scheme. We also present sub-optimal routing schemes that only use part of the available knowledge and require much lower computational complexity. Numerical results demonstrate that the performance of the low complexity schemes is close to optimal and outperforms other tested routing schemes.