OpenRaiser/Intern-Atlas huggingface dataset:
Strict Very Fast Decision Tree: a memory conservative algorithm for data stream mining
Venue: arXiv cs.AI 2018
Year: 2018

Dealing with memory and time constraints are current challenges when learning from data streams with a massive amount of data. Many algorithms have been proposed to handle these difficulties, among them, the Very Fast Decision Tree (VFDT) algorithm. Although the VFDT has been widely used in data stream mining, in the last years, several authors have suggested modifications to increase its performance, putting aside memory concerns by proposing memory-costly solutions. Besides, most data stream mining solutions have been centred around ensembles, which combine the memory costs of their weak learners, usually VFDTs. To reduce the memory cost, keeping the predictive performance, this study proposes the Strict VFDT (SVFDT), a novel algorithm based on the VFDT. The SVFDT algorithm minimises unnecessary tree growth, substantially reducing memory usage and keeping competitive predictive performance. Moreover, since it creates much more shallow trees than VFDT, SVFDT can achieve a shorter processing time. Experiments were carried out comparing the SVFDT with the VFDT in 11 benchmark data stream datasets. This comparison assessed the trade-off between accuracy, memory, and processing time. Statistical analysis showed that the proposed algorithm obtained similar predictive performance and significantly reduced processing time and memory use. Thus, SVFDT is a suitable option for data stream mining with memory and time limitations, recommended as a weak learner in ensemble-based solutions.
Deep Segmentation and Registration in X-Ray Angiography Video
Venue: arXiv cs.CV 2018
Year: 2018

In interventional radiology, short video sequences of vein structure in motion are captured in order to help medical personnel identify vascular issues or plan intervention. Semantic segmentation can greatly improve the usefulness of these videos by indicating exact position of vessels and instruments, thus reducing the ambiguity. We propose a real-time segmentation method for these tasks, based on U-Net network trained in a Siamese architecture from automatically generated annotations. We make use of noisy low level binary segmentation and optical flow to generate multi class annotations that are successively improved in a multistage segmentation approach. We significantly improve the performance of a state of the art U-Net at the processing speeds of 90fps.
Hybrid Adaptive Fuzzy Extreme Learning Machine for text classification
Venue: arXiv cs.IR 2018
Year: 2018

In traditional ELM and its improved versions suffer from the problems of outliers or noises due to overfitting and imbalance due to distribution. We propose a novel hybrid adaptive fuzzy ELM(HA-FELM), which introduces a fuzzy membership function to the traditional ELM method to deal with the above problems. We define the fuzzy membership function not only basing on the distance between each sample and the center of the class but also the density among samples which based on the quantum harmonic oscillator model. The proposed fuzzy membership function overcomes the shortcoming of the traditional fuzzy membership function and could make itself adjusted according to the specific distribution of different samples adaptively. Experiments show the proposed HA-FELM can produce better performance than SVM, ELM, and RELM in text classification.
Slicing Virtualized EPC-based 5G Core Network for Content Delivery
Venue: arXiv cs.NI 2018
Year: 2018

Traditional Content Delivery Networks (CDNs) built with traditional Internet technology are less and less able to cope with today's tremendous growth of content. Information Centric Networks (ICN), a proposed future Internet technology, may aid in remedying the situation. Unlike the current Internet, it decouples information from its sources and provides in-network storage. We expect traditional CDN and ICN-based CDN to co-exist in the foreseeable future, especially as it is now known that it might be possible to evolve traditional CDNs to gain the benefits promised by ICN. 5G providers must therefore aim to offer core network slices on which both ICN-based CDNs and traditional CDNs can be built. These slices could of course also be offered to providers of other applications with requirements similar to those of content delivery. This paper tackles the problem of slicing 5G for content delivery over ICN-based CDNs and traditional CDNs. Only virtualized Evolved Packet Core (EPC)-based 5G is considered. The problem is defined as a resource allocation problem which aims at minimizing the cost of slice assignment, while meeting QoS requirements. An Integer linear programming (ILP) formulation is provided and evaluated in a small-scale scenario.
Dancing Pigs or Externalities? Measuring the Rationality of Security Decisions
Venue: arXiv cs.GT 2018
Year: 2018

Accurately modeling human decision-making in security is critical to thinking about when, why, and how to recommend that users adopt certain secure behaviors. In this work, we conduct behavioral economics experiments to model the rationality of end-user security decision-making in a realistic online experimental system simulating a bank account. We ask participants to make a financially impactful security choice, in the face of transparent risks of account compromise and benefits offered by an optional security behavior (two-factor authentication). We measure the cost and utility of adopting the security behavior via measurements of time spent executing the behavior and estimates of the participant's wage. We find that more than 50% of our participants made rational (e.g., utility optimal) decisions, and we find that participants are more likely to behave rationally in the face of higher risk. Additionally, we find that users' decisions can be modeled well as a function of past behavior (anchoring effects), knowledge of costs, and to a lesser extent, users' awareness of risks and context (R2=0.61). We also find evidence of endowment effects, as seen in other areas of economic and psychological decision-science literature, in our digital-security setting. Finally, using our data, we show theoretically that a "one-size-fits"-all emphasis on security can lead to market losses, but that adoption by a subset of users with higher risks or lower costs can lead to market gains.
DeepGlobe 2018: A Challenge to Parse the Earth through Satellite Images
Venue: arXiv cs.CV 2018
Year: 2018

We present the DeepGlobe 2018 Satellite Image Understanding Challenge, which includes three public competitions for segmentation, detection, and classification tasks on satellite images. Similar to other challenges in computer vision domain such as DAVIS and COCO, DeepGlobe proposes three datasets and corresponding evaluation methodologies, coherently bundled in three competitions with a dedicated workshop co-located with CVPR 2018. We observed that satellite imagery is a rich and structured source of information, yet it is less investigated than everyday images by computer vision researchers. However, bridging modern computer vision with remote sensing data analysis could have critical impact to the way we understand our environment and lead to major breakthroughs in global urban planning or climate change research. Keeping such bridging objective in mind, DeepGlobe aims to bring together researchers from different domains to raise awareness of remote sensing in the computer vision community and vice-versa. We aim to improve and evaluate state-of-the-art satellite image understanding approaches, which can hopefully serve as reference benchmarks for future research in the same topic. In this paper, we analyze characteristics of each dataset, define the evaluation criteria of the competitions, and provide baselines for each task.
FastFCA: A Joint Diagonalization Based Fast Algorithm for Audio Source Separation Using A Full-Rank Spatial Covariance Model
Venue: arXiv cs.SD 2018
Year: 2018

A source separation method using a full-rank spatial covariance model has been proposed by Duong et al. ["Under-determined Reverberant Audio Source Separation Using a Full-rank Spatial Covariance Model," IEEE Trans. ASLP, vol. 18, no. 7, pp. 1830-1840, Sep. 2010], which is referred to as full-rank spatial covariance analysis (FCA) in this paper. Here we propose a fast algorithm for estimating the model parameters of the FCA, which is named Fast-FCA, and applicable to the two-source case. Though quite effective in source separation, the conventional FCA has a major drawback of expensive computation. Indeed, the conventional algorithm for estimating the model parameters of the FCA requires frame-wise matrix inversion and matrix multiplication. Therefore, the conventional FCA may be infeasible in applications with restricted computational resources. In contrast, the proposed FastFCA bypasses matrix inversion and matrix multiplication owing to joint diagonalization based on the generalized eigenvalue problem. Furthermore, the FastFCA is strictly equivalent to the conventional algorithm. An experiment has shown that the FastFCA was over 250 times faster than the conventional algorithm with virtually the same source separation performance.
Taxi demand forecasting: A HEDGE based tessellation strategy for improved accuracy
Venue: arXiv cs.LG 2018
Year: 2018

A key problem in location-based modeling and forecasting lies in identifying suitable spatial and temporal resolutions. In particular, judicious spatial partitioning can play a significant role in enhancing the performance of location-based forecasting models. In this work, we investigate two widely used tessellation strategies for partitioning city space, in the context of real-time taxi demand forecasting. Our study compares (i) Geohash tessellation, and (ii) Voronoi tessellation, using two distinct taxi demand datasets, over multiple time scales. For the purpose of comparison, we employ classical time-series tools to model the spatio-temporal demand. Our study finds that the performance of each tessellation strategy is highly dependent on the city geography, spatial distribution of the data, and the time of the day, and that neither strategy is found to perform optimally across the forecast horizon. We propose a hybrid tessellation algorithm that picks the best tessellation strategy at each instant, based on their performance in the recent past. Our hybrid algorithm is a non-stationary variant of the well-known HEDGE algorithm for choosing the best advice from multiple experts. We show that the hybrid tessellation strategy performs consistently better than either of the two strategies across the data sets considered, at multiple time scales, and with different performance metrics. We achieve an average accuracy of above 80% per km^2 for both data sets considered at 60 minute aggregation levels.
Dual parameterization of Weighted Coloring
Venue: arXiv cs.DS 2018
Year: 2018

Given a graph $G$, a proper $k$-coloring of $G$ is a partition $c = (S_i)_{i\in [1,k]}$ of $V(G)$ into $k$ stable sets $S_1,\ldots, S_{k}$. Given a weight function $w: V(G) \to \mathbb{R}^+$, the weight of a color $S_i$ is defined as $w(i) = \max_{v \in S_i} w(v)$ and the weight of a coloring $c$ as $w(c) = \sum_{i=1}^{k}w(i)$. Guan and Zhu [Inf. Process. Lett., 1997] defined the weighted chromatic number of a pair $(G,w)$, denoted by $σ(G,w)$, as the minimum weight of a proper coloring of $G$. The problem of determining $σ(G,w)$ has received considerable attention during the last years, and has been proved to be notoriously hard: for instance, it is NP-hard on split graphs, unsolvable on $n$-vertex trees in time $n^{o(\log n)}$ unless the ETH fails, and W[1]-hard on forests parameterized by the size of a largest tree. In this article we provide some positive results for the problem, by considering its so-called dual parameterization: given a vertex-weighted graph $(G,w)$ and an integer $k$, the question is whether $σ(G,w) \leq \sum_{v \in V(G)} w(v) - k$. We prove that this problem is FPT by providing an algorithm running in time $9^k \cdot n^{O(1)}$, and it is easy to see that no algorithm in time $2^{o(k)} \cdot n^{O(1)}$ exists under the ETH. On the other hand, we present a kernel with at most $(2^{k-1}+1) (k-1)$ vertices, and we rule out the existence of polynomial kernels unless ${\sf NP} \subseteq {\sf coNP} / {\sf poly}$, even on split graphs with only two different weights. Finally, we identify some classes of graphs on which the problem admits a polynomial kernel, in particular interval graphs and subclasses of split graphs, and in the latter case we present lower bounds on the degrees of the polynomials.
Quadratic Word Equations with Length Constraints, Counter Systems, and Presburger Arithmetic with Divisibility
Venue: arXiv cs.LO 2018
Year: 2018

Word equations are a crucial element in the theoretical foundation of constraint solving over strings, which have received a lot of attention in recent years. A word equation relates two words over string variables and constants. Its solution amounts to a function mapping variables to constant strings that equate the left and right hand sides of the equation. While the problem of solving word equations is decidable, the decidability of the problem of solving a word equation with a length constraint (i.e., a constraint relating the lengths of words in the word equation) has remained a long-standing open problem. In this paper, we focus on the subclass of quadratic word equations, i.e., in which each variable occurs at most twice. We first show that the length abstractions of solutions to quadratic word equations are in general not Presburger-definable. We then describe a class of counter systems with Presburger transition relations which capture the length abstraction of a quadratic word equation with regular constraints. We provide an encoding of the effect of a simple loop of the counter systems in the theory of existential Presburger Arithmetic with divisibility (PAD). Since PAD is decidable, we get a decision procedure for quadratic words equations with length constraints for which the associated counter system is \emph{flat} (i.e., all nodes belong to at most one cycle). We show a decidability result (in fact, also an NP algorithm with a PAD oracle) for a recently proposed NP-complete fragment of word equations called regular-oriented word equations, together with length constraints. Decidability holds when the constraints are additionally extended with regular constraints with a 1-weak control structure.
Exploiting the Superposition Property of Wireless Communication for Max-Consensus Problems in Multi-Agent Systems
Venue: arXiv cs.SY 2018
Year: 2018

This paper presents a consensus protocol that achieves max-consensus in multi-agent systems over wireless channels. Interference, a feature of the wireless channel, is exploited: each agent receives a superposition of broadcast data, rather than individual values. With this information, the system endowed with the proposed consensus protocol reaches max-consensus in a finite number of steps. A comparison with traditional approaches shows that the proposed consensus protocol achieves a faster convergence.
Action Completion: A Temporal Model for Moment Detection
Venue: arXiv cs.CV 2018
Year: 2018

We introduce completion moment detection for actions - the problem of locating the moment of completion, when the action's goal is confidently considered achieved. The paper proposes a joint classification-regression recurrent model that predicts completion from a given frame, and then integrates frame-level contributions to detect sequence-level completion moment. We introduce a recurrent voting node that predicts the frame's relative position of the completion moment by either classification or regression. The method is also capable of detecting incompletion. For example, the method is capable of detecting a missed ball-catch, as well as the moment at which the ball is safely caught. We test the method on 16 actions from three public datasets, covering sports as well as daily actions. Results show that when combining contributions from frames prior to the completion moment as well as frames post completion, the completion moment is detected within one second in 89% of all tested sequences.
Betting on Blockchain Consensus with Fantomette
Venue: arXiv cs.CR 2018
Year: 2018

Blockchain-based consensus protocols present the opportunity to develop new protocols, due to their novel requirements of open participation and explicit incentivization of participants. To address the first requirement, it is necessary to consider the leader election inherent in consensus protocols, which can be difficult to scale to a large and untrusted set of participants. To address the second, it is important to consider ways to provide incentivization without relying on the resource-intensive proofs-of-work used in Bitcoin. In this paper, we propose a secure leader election protocol, Caucus; we next fit this protocol into a broader blockchain-based consensus protocol, Fantomette, that provides game-theoretic guarantees in addition to traditional blockchain security properties. Fantomette is the first proof-of-stake protocol to give formal game-theoretic proofs of security in the presence of non-rational players.
On two consequences of Berge-Fulkerson conjecture
Venue: arXiv cs.DM 2018
Year: 2018

The classical Berge-Fulkerson conjecture states that any bridgeless cubic graph $G$ admits a list of six perfect matchings such that each edge of $G$ belongs to two of the perfect matchings from the list. In this short note, we discuss two statements that are consequences of this conjecture. We show that the first statement is equivalent to Fan-Raspaud conjecture. We also show that the smallest counter-example to the second one is a cyclically $4$-edge-connected cubic graph.
Changing Observations in Epistemic Temporal Logic
Venue: arXiv cs.LO 2018
Year: 2018

We study dynamic changes of agents' observational power in logics of knowledge and time. We consider CTL*K, the extension of CTL* with knowledge operators, and enrich it with a new operator that models a change in an agent's way of observing the system. We extend the classic semantics of knowledge for perfect-recall agents to account for changes of observation, and we show that this new operator strictly increases the expressivity of CTL*K. We reduce the model-checking problem for our logic to that for CTL*K, which is known to be decidable. This provides a solution to the model-checking problem for our logic, but its complexity is not optimal. Indeed we provide a direct decision procedure with better complexity.
Neural User Simulation for Corpus-based Policy Optimisation for Spoken Dialogue Systems
Venue: arXiv cs.CL 2018
Year: 2018

User Simulators are one of the major tools that enable offline training of task-oriented dialogue systems. For this task the Agenda-Based User Simulator (ABUS) is often used. The ABUS is based on hand-crafted rules and its output is in semantic form. Issues arise from both properties such as limited diversity and the inability to interface a text-level belief tracker. This paper introduces the Neural User Simulator (NUS) whose behaviour is learned from a corpus and which generates natural language, hence needing a less labelled dataset than simulators generating a semantic output. In comparison to much of the past work on this topic, which evaluates user simulators on corpus-based metrics, we use the NUS to train the policy of a reinforcement learning based Spoken Dialogue System. The NUS is compared to the ABUS by evaluating the policies that were trained using the simulators. Cross-model evaluation is performed i.e. training on one simulator and testing on the other. Furthermore, the trained policies are tested on real users. In both evaluation tasks the NUS outperformed the ABUS.
Learning Permutations with Sinkhorn Policy Gradient
Venue: arXiv cs.LG 2018
Year: 2018

Many problems at the intersection of combinatorics and computer science require solving for a permutation that optimally matches, ranks, or sorts some data. These problems usually have a task-specific, often non-differentiable objective function that data-driven algorithms can use as a learning signal. In this paper, we propose the Sinkhorn Policy Gradient (SPG) algorithm for learning policies on permutation matrices. The actor-critic neural network architecture we introduce for SPG uniquely decouples representation learning of the state space from the highly-structured action space of permutations with a temperature-controlled Sinkhorn layer. The Sinkhorn layer produces continuous relaxations of permutation matrices so that the actor-critic architecture can be trained end-to-end. Our empirical results show that agents trained with SPG can perform competitively on sorting, the Euclidean TSP, and matching tasks. We also observe that SPG is significantly more data efficient at the matching task than the baseline methods, which indicates that SPG is conducive to learning representations that are useful for reasoning about permutations.
Blind Receive Beamforming for Autonomous Grant-Free High-Overloading Multiple Access
Venue: arXiv cs.IT 2018
Year: 2018

Massive number of internet of things (IoT) devices are expected to simultaneously connect to the mMTC and beyond future generations of wireless network, posing severe challenge to aspects such as RACH procedure, user equipment detection and channel estimation. Although spatial combining has provided significant gains in conventional grant-based transmission, this technique is stuck in dilemma when it comes to autonomous grant-free transmission tailored for IoT use cases. To address this, blind spatial combining and its incorporation in the data-only MUD are elaborated in this paper answering to both the academic and industry's concern in the overloading potential of autonomous grant-free (AGF) transmission. Blind spatial combining could be interpreted as blind receive beamforming heuristically. Simulation results show that the blind spatial combining enhanced data-only MUD performance for AGF transmission is rather impressive.
Blockchain Cohomology
Venue: arXiv cs.DC 2018
Year: 2018

We follow existing distributed systems frameworks employing methods from algebraic topology to formally define primitives of blockchain technology. We define the notion of cross chain liquidity, sharding and probability spaces between and within blockchain protocols. We incorporate recent advancements in synthetic homology to show that this topological framework can be implemented within a type system. We use recursion schemes to define kernels admitting smooth manifolds across protocol complexes, leading to the formal definition of a Poincare protocol.
SNU_IDS at SemEval-2018 Task 12: Sentence Encoder with Contextualized Vectors for Argument Reasoning Comprehension
Venue: arXiv cs.CL 2018
Year: 2018

We present a novel neural architecture for the Argument Reasoning Comprehension task of SemEval 2018. It is a simple neural network consisting of three parts, collectively judging whether the logic built on a set of given sentences (a claim, reason, and warrant) is plausible or not. The model utilizes contextualized word vectors pre-trained on large machine translation (MT) datasets as a form of transfer learning, which can help to mitigate the lack of training data. Quantitative analysis shows that simply leveraging LSTMs trained on MT datasets outperforms several baselines and non-transferred models, achieving accuracies of about 70% on the development set and about 60% on the test set.
Evaluation of a congruent auditory feedback for Motor Imagery BCI
Venue: arXiv cs.HC 2018
Year: 2018

Designing a feedback that helps participants to achieve higher performances is an important concern in brain-computer interface (BCI) research. In a pilot study, we demonstrate how a congruent auditory feedback could improve classification in a electroencephalography (EEG) motor imagery BCI. This is a promising result for creating alternate feedback modality.