OpenRaiser/Intern-Atlas huggingface dataset:
Cloud-based Deep Learning of Big EEG Data for Epileptic Seizure Prediction
Venue: arXiv cs.LG 2017
Year: 2017

Developing a Brain-Computer Interface~(BCI) for seizure prediction can help epileptic patients have a better quality of life. However, there are many difficulties and challenges in developing such a system as a real-life support for patients. Because of the nonstationary nature of EEG signals, normal and seizure patterns vary across different patients. Thus, finding a group of manually extracted features for the prediction task is not practical. Moreover, when using implanted electrodes for brain recording massive amounts of data are produced. This big data calls for the need for safe storage and high computational resources for real-time processing. To address these challenges, a cloud-based BCI system for the analysis of this big EEG data is presented. First, a dimensionality-reduction technique is developed to increase classification accuracy as well as to decrease the communication bandwidth and computation time. Second, following a deep-learning approach, a stacked autoencoder is trained in two steps for unsupervised feature extraction and classification. Third, a cloud-computing solution is proposed for real-time analysis of big EEG data. The results on a benchmark clinical dataset illustrate the superiority of the proposed patient-specific BCI as an alternative method and its expected usefulness in real-life support of epilepsy patients.
A Fully Polynomial Time Approximation Scheme for Packing While Traveling
Venue: arXiv cs.DS 2017
Year: 2017

Understanding the interactions between different combinatorial optimisation problems in real-world applications is a challenging task. Recently, the traveling thief problem (TTP), as a combination of the classical traveling salesperson problem and the knapsack problem, has been introduced to study these interactions in a systematic way. We investigate the underlying non-linear packing while traveling (PWT) problem of the TTP where items have to be selected along a fixed route. We give an exact dynamic programming approach for this problem and a fully polynomial time approximation scheme (FPTAS) when maximising the benefit that can be gained over the baseline travel cost. Our experimental investigations show that our new approaches outperform current state-of-the-art approaches on a wide range of benchmark instances.
Student's opinions about System for automatic assessment of programming tasks Projekt Tomo
Venue: arXiv cs.CY 2017
Year: 2017

In a previous paper a web service called Projekt Tomo intended to ease the process of learning programming for teachers and students has been described. Since the service received a very warm welcome from teachers and students alike we decided to collect additional information on the students' view of the service in order to improve it even further. In the paper we briefly present our web service and a detailed analysis of the questionnaire handed out to the students of the highschool level programming course in Python.
Short Paper: On Deployment of DNS-based Security Enhancements
Venue: arXiv cs.CR 2017
Year: 2017

Although the Domain Name System (DNS) was designed as a naming system, its features have made it appealing to repurpose it for the deployment of novel systems. One important class of such systems are security enhancements, and this work sheds light on their deployment. We show the characteristics of these solutions and measure reliability of DNS in these applications. We investigate the compatibility of these solutions with the Tor network, signal necessary changes, and report on surprising drawbacks in Tor's DNS resolution.
On algebraic branching programs of small width
Venue: arXiv cs.CC 2017
Year: 2017

In 1979 Valiant showed that the complexity class VP_e of families with polynomially bounded formula size is contained in the class VP_s of families that have algebraic branching programs (ABPs) of polynomially bounded size. Motivated by the problem of separating these classes we study the topological closure VP_e-bar, i.e. the class of polynomials that can be approximated arbitrarily closely by polynomials in VP_e. We describe VP_e-bar with a strikingly simple complete polynomial (in characteristic different from 2) whose recursive definition is similar to the Fibonacci numbers. Further understanding this polynomial seems to be a promising route to new formula lower bounds. Our methods are rooted in the study of ABPs of small constant width. In 1992 Ben-Or and Cleve showed that formula size is polynomially equivalent to width-3 ABP size. We extend their result (in characteristic different from 2) by showing that approximate formula size is polynomially equivalent to approximate width-2 ABP size. This is surprising because in 2011 Allender and Wang gave explicit polynomials that cannot be computed by width-2 ABPs at all! The details of our construction lead to the aforementioned characterization of VP_e-bar. As a natural continuation of this work we prove that the class VNP can be described as the class of families that admit a hypercube summation of polynomially bounded dimension over a product of polynomially many affine linear forms. This gives the first separations of algebraic complexity classes from their nondeterministic analogs.
Empathy in One-Shot Prisoner Dilemma
Venue: arXiv cs.GT 2017
Year: 2017

Strategic decision making involves affective and cognitive functions like reasoning, cognitive and emotional empathy which may be subject to age and gender differences. However, empathy-related changes in strategic decision-making and their relation to age, gender and neuropsychological functions have not been studied widely. In this article, we study a one-shot prisoner dilemma from a psychological game theory viewpoint. Forty seven participants (28 women and 19 men), aged 18 to 42 years, were tested with a empathy questionnaire and a one-shot prisoner dilemma questionnaire comprising a closiness option with the other participant. The percentage of cooperation and defection decisions was analyzed. A new empathetic payoff model was calculated to fit the observations from the test whether multi-dimensional empathy levels matter in the outcome. A significant level of cooperation is observed in the experimental one-shot game. The collected data suggests that perspective taking, empathic concern and fantasy scale are strongly correlated and have an important effect on cooperative decisions. However, their effect in the payoff is not additive. Mixed scales as well as other non-classified subscales (25+8 out of 47) were observed from the data.
The Effect of Color Space Selection on Detectability and Discriminability of Colored Objects
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we investigate the effect of color space selection on detectability and discriminability of colored objects under various conditions. 20 color spaces from the literature are evaluated on a large dataset of simulated and real images. We measure the suitability of color spaces from two different perspectives: detectability and discriminability of various color groups. Through experimental evaluation, we found that there is no single optimal color space suitable for all color groups. The color spaces have different levels of sensitivity to different color groups and they are useful depending on the color of the sought object. Overall, the best results were achieved in both simulated and real images using color spaces C1C2C3, UVW and XYZ. In addition, using a simulated environment, we show a practical application of color space selection in the context of top-down control in active visual search. The results indicate that on average color space C1C2C3 followed by HSI and XYZ achieve the best time in searching for objects of various colors. Here, the right choice of color space can improve time of search on average by 20%. As part of our contribution, we also introduce a large dataset of simulated 3D objects
Toward Abstraction from Multi-modal Data: Empirical Studies on Multiple Time-scale Recurrent Models
Venue: arXiv cs.NE 2017
Year: 2017

The abstraction tasks are challenging for multi- modal sequences as they require a deeper semantic understanding and a novel text generation for the data. Although the recurrent neural networks (RNN) can be used to model the context of the time-sequences, in most cases the long-term dependencies of multi-modal data make the back-propagation through time training of RNN tend to vanish in the time domain. Recently, inspired from Multiple Time-scale Recurrent Neural Network (MTRNN), an extension of Gated Recurrent Unit (GRU), called Multiple Time-scale Gated Recurrent Unit (MTGRU), has been proposed to learn the long-term dependencies in natural language processing. Particularly it is also able to accomplish the abstraction task for paragraphs given that the time constants are well defined. In this paper, we compare the MTRNN and MTGRU in terms of its learning performances as well as their abstraction representation on higher level (with a slower neural activation). This was done by conducting two studies based on a smaller data- set (two-dimension time sequences from non-linear functions) and a relatively large data-set (43-dimension time sequences from iCub manipulation tasks with multi-modal data). We conclude that gated recurrent mechanisms may be necessary for learning long-term dependencies in large dimension multi-modal data-sets (e.g. learning of robot manipulation), even when natural language commands was not involved. But for smaller learning tasks with simple time-sequences, generic version of recurrent models, such as MTRNN, were sufficient to accomplish the abstraction task.
LCL problems on grids
Venue: arXiv cs.DC 2017
Year: 2017

LCLs or locally checkable labelling problems (e.g. maximal independent set, maximal matching, and vertex colouring) in the LOCAL model of computation are very well-understood in cycles (toroidal 1-dimensional grids): every problem has a complexity of $O(1)$, $Θ(\log^* n)$, or $Θ(n)$, and the design of optimal algorithms can be fully automated. This work develops the complexity theory of LCL problems for toroidal 2-dimensional grids. The complexity classes are the same as in the 1-dimensional case: $O(1)$, $Θ(\log^* n)$, and $Θ(n)$. However, given an LCL problem it is undecidable whether its complexity is $Θ(\log^* n)$ or $Θ(n)$ in 2-dimensional grids. Nevertheless, if we correctly guess that the complexity of a problem is $Θ(\log^* n)$, we can completely automate the design of optimal algorithms. For any problem we can find an algorithm that is of a normal form $A' \circ S_k$, where $A'$ is a finite function, $S_k$ is an algorithm for finding a maximal independent set in $k$th power of the grid, and $k$ is a constant. Finally, partially with the help of automated design tools, we classify the complexity of several concrete LCL problems related to colourings and orientations.
An Unsupervised Approach for Overlapping Cervical Cell Cytoplasm Segmentation
Venue: arXiv cs.CV 2017
Year: 2017

The poor contrast and the overlapping of cervical cell cytoplasm are the major issues in the accurate segmentation of cervical cell cytoplasm. This paper presents an automated unsupervised cytoplasm segmentation approach which can effectively find the cytoplasm boundaries in overlapping cells. The proposed approach first segments the cell clumps from the cervical smear image and detects the nuclei in each cell clump. A modified Otsu method with prior class probability is proposed for accurate segmentation of nuclei from the cell clumps. Using distance regularized level set evolution, the contour around each nucleus is evolved until it reaches the cytoplasm boundaries. Promising results were obtained by experimenting on ISBI 2015 challenge dataset.
A Concurrent Perspective on Smart Contracts
Venue: arXiv cs.DC 2017
Year: 2017

In this paper, we explore remarkable similarities between multi-transactional behaviors of smart contracts in cryptocurrencies such as Ethereum and classical problems of shared-memory concurrency. We examine two real-world examples from the Ethereum blockchain and analyzing how they are vulnerable to bugs that are closely reminiscent to those that often occur in traditional concurrent programs. We then elaborate on the relation between observable contract behaviors and well-studied concurrency topics, such as atomicity, interference, synchronization, and resource ownership. The described contracts-as-concurrent-objects analogy provides deeper understanding of potential threats for smart contracts, indicate better engineering practices, and enable applications of existing state-of-the-art formal verification techniques.
Overview: Generalizations of Multi-Agent Path Finding to Real-World Scenarios
Venue: arXiv cs.AI 2017
Year: 2017

Multi-agent path finding (MAPF) is well-studied in artificial intelligence, robotics, theoretical computer science and operations research. We discuss issues that arise when generalizing MAPF methods to real-world scenarios and four research directions that address them. We emphasize the importance of addressing these issues as opposed to developing faster methods for the standard formulation of the MAPF problem.
Optimal Non-uniform Deployments in Ultra-Dense Finite-Area Cellular Networks
Venue: arXiv cs.NI 2017
Year: 2017

Network densification and heterogenisation through the deployment of small cellular access points (picocells and femtocells) are seen as key mechanisms in handling the exponential increase in cellular data traffic. Modelling such networks by leveraging tools from Stochastic Geometry has proven particularly useful in understanding the fundamental limits imposed on network coverage and capacity by co-channel interference. Most of these works however assume infinite sized and uniformly distributed networks on the Euclidean plane. In contrast, we study finite sized non-uniformly distributed networks, and find the optimal non-uniform distribution of access points which maximises network coverage for a given non-uniform distribution of mobile users, and vice versa.
Two Lower Bounds for BPA
Venue: arXiv cs.LO 2017
Year: 2017

Branching bisimilarity on normed Basic Process Algebra (BPA) was claimed to be EXPTIME-hard in previous papers without any explicit proof. Recently it is reminded by Jančar that the claim is not so dependable. In this paper, we develop a new complete proof for EXPTIME-hardness of branching bisimilarity on normed BPA. We also prove the associate regularity problem on normed BPA is PSPACE-hard and in EXPTIME. This improves previous P-hard and NEXPTIME result.
A Circuit-Based Approach to Efficient Enumeration
Venue: arXiv cs.DS 2017
Year: 2017

We study the problem of enumerating the satisfying valuations of a circuit while bounding the delay, i.e., the time needed to compute each successive valuation. We focus on the class of structured d-DNNF circuits originally introduced in knowledge compilation, a sub-area of artificial intelligence. We propose an algorithm for these circuits that enumerates valuations with linear preprocessing and delay linear in the Hamming weight of each valuation. Moreover, valuations of constant Hamming weight can be enumerated with linear preprocessing and constant delay. Our results yield a framework for efficient enumeration that applies to all problems whose solutions can be compiled to structured d-DNNFs. In particular, we use it to recapture classical results in database theory, for factorized database representations and for MSO evaluation. This gives an independent proof of constant-delay enumeration for MSO formulae with first-order free variables on bounded-treewidth structures.
End-to-End Differentially-Private Parameter Tuning in Spatial Histograms
Venue: arXiv cs.DB 2017
Year: 2017

Differentially-private histograms have emerged as a key tool for location privacy. While past mechanisms have included theoretical & experimental analysis, it has recently been observed that much of the existing literature does not fully provide differential privacy. The missing component, private parameter tuning, is necessary for rigorous evaluation of these mechanisms. Instead works frequently tune on training data to optimise parameters without consideration of privacy; in other cases selection is performed arbitrarily and independent of data, degrading utility. We address this open problem by deriving a principled tuning mechanism that privately optimises data-dependent error bounds. Theoretical results establish privacy and utility while extensive experimentation demonstrates that we can practically achieve true end-to-end privacy.
Energy-Efficient Coordinated Multi-Cell Multigroup Multicast Beamforming with Antenna Selection
Venue: arXiv cs.IT 2017
Year: 2017

This paper studies energy-efficient coordinated beamforming in multi-cell multi-user multigroup multicast multiple-input single-output systems. We aim at maximizing the network energy efficiency by taking into account the fact that some of the radio frequency chains can be switched off in order to save power. We consider the antenna specific maximum power constraints to avoid non-linear distortion in power amplifiers and user-specific quality of service (QoS) constraints to guarantee a certain QoS levels. We first introduce binary antenna selection variables and use the perspective formulation to model the relation between them and the beamformers. Subsequently, we propose a new formulation which reduces the feasible set of the continuous relaxation, resulting in better performance compared to the original perspective formulation based problem. However, the resulting optimization problem is a mixed-Boolean non-convex fractional program, which is difficult to solve. We follow the standard continuous relaxation of the binary antenna selection variables, and then reformulate the problem such that it is amendable to successive convex approximation. Thereby, solving the continuous relaxation mostly results in near-binary solution. To recover the binary variables from the continuous relaxation, we switch off all the antennas for which the continuous values are smaller than a small threshold. Numerical results illustrate the superior convergence result and significant achievable gains in terms of energy efficiency with the proposed algorithm.
Revisiting Graph Construction for Fast Image Segmentation
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we propose a simple but effective method for fast image segmentation. We re-examine the locality-preserving character of spectral clustering by constructing a graph over image regions with both global and local connections. Our novel approach to build graph connections relies on two key observations: 1) local region pairs that co-occur frequently will have a high probability to reside on a common object; 2) spatially distant regions in a common object often exhibit similar visual saliency, which implies their neighborship in a manifold. We present a novel energy function to efficiently conduct graph partitioning. Based on multiple high quality partitions, we show that the generated eigenvector histogram based representation can automatically drive effective unary potentials for a hierarchical random field model to produce multi-class segmentation. Sufficient experiments, on the BSDS500 benchmark, large-scale PASCAL VOC and COCO datasets, demonstrate the competitive segmentation accuracy and significantly improved efficiency of our proposed method compared with other state of the arts.
A Research Platform for Real-World Evaluation of Routing Schemes in Delay Tolerant Social Networks
Venue: arXiv cs.NI 2017
Year: 2017

Over the past decade, online social networks (OSNs) such as Twitter and Facebook have thrived and experienced rapid growth to over 1 billion users. A major evolution would be to leverage the characteristics of OSNs to evaluate the effectiveness of the many routing schemes developed by the research community in real-world scenarios. In this demo, we showcase AlleyOop Social, a secure delay tolerant networking research platform that serves as a real-life mobile social networking application for iOS devices. AlleyOop Social allows users to interact, publish messages, and discover others that share common interests in an intermittent network using Bluetooth, peer-to-peer WiFi, and infrastructure WiFi. The research platform serves as an overlay application for the Secure Opportunistic Schemes (SOS) middleware which allows different routing schemes to be easily implemented relieving the burden of security and connection establishment.
The Game Imitation: Deep Supervised Convolutional Networks for Quick Video Game AI
Venue: arXiv cs.CV 2017
Year: 2017

We present a vision-only model for gaming AI which uses a late integration deep convolutional network architecture trained in a purely supervised imitation learning context. Although state-of-the-art deep learning models for video game tasks generally rely on more complex methods such as deep-Q learning, we show that a supervised model which requires substantially fewer resources and training time can already perform well at human reaction speeds on the N64 classic game Super Smash Bros. We frame our learning task as a 30-class classification problem, and our CNN model achieves 80% top-1 and 95% top-3 validation accuracy. With slight test-time fine-tuning, our model is also competitive during live simulation with the highest-level AI built into the game. We will further show evidence through network visualizations that the network is successfully leveraging temporal information during inference to aid in decision making. Our work demonstrates that supervised CNN models can provide good performance in challenging policy prediction tasks while being significantly simpler and more lightweight than alternatives.
Using Bad Learners to find Good Configurations
Venue: arXiv cs.SE 2017
Year: 2017

Finding the optimally performing configuration of a software system for a given setting is often challenging. Recent approaches address this challenge by learning performance models based on a sample set of configurations. However, building an accurate performance model can be very expensive (and is often infeasible in practice). The central insight of this paper is that exact performance values (e.g. the response time of a software system) are not required to rank configurations and to identify the optimal one. As shown by our experiments, models that are cheap to learn but inaccurate (with respect to the difference between actual and predicted performance) can still be used rank configurations and hence find the optimal configuration. This novel \emph{rank-based approach} allows us to significantly reduce the cost (in terms of number of measurements of sample configuration) as well as the time required to build models. We evaluate our approach with 21 scenarios based on 9 software systems and demonstrate that our approach is beneficial in 16 scenarios; for the remaining 5 scenarios, an accurate model can be built by using very few samples anyway, without the need for a rank-based approach.