OpenRaiser/Intern-Atlas huggingface dataset:
A Game Theoretic Approach to DSRC and WiFi Coexistence
Venue: arXiv cs.NI 2018
Year: 2018

We model the coexistence of DSRC and WiFi networks as a strategic form game with the networks as the players. Nodes in a DSRC network must support messaging of status updates that are time sensitive. Such nodes would like to achieve a small age of information of status updates. In contrast, nodes in a WiFi network would like to achieve large throughputs. Each network chooses a medium access probability to be used by all its nodes. We investigate Nash and Stackelberg equilibrium strategies.
Sequentialization for full N-Graphs via sub-N-Graphs
Venue: arXiv cs.LO 2018
Year: 2018

Since proof-nets for MLL- were introduced by Girard (1987), several studies have appeared dealing with its soundness proof. Bellin & Van de Wiele (1995) produced an elegant proof based on properties of subnets (empires and kingdoms) and Robinson (2003) proposed a straightforward generalization of this presentation for proof-nets from sequent calculus for classical logic. In 2014 it was presented an extension of these studies to obtain a proof of the sequentialization theorem for the fragment of N-Graphs with conjunction, disjunction and negation connectives, via the notion of sub-N-Graphs. N-Graphs is a symmetric natural deduction calculus with multiple conclusions that adopts Danos-Regnier's criterion and has defocussing switchable links. In this paper, we present a sequentization for full propositional classical N-Graphs, showing how to find a split node in the middle of the proof even with a global rule for discharging hypothesis.
The information and wave-theoretic limits of analog beamforming
Venue: arXiv cs.IT 2018
Year: 2018

The performance of broadband millimeter-wave (mmWave) RF architectures, is generally determined by mathematical concepts such as the Shannon capacity. These systems have also to obey physical laws such as the conservation of energy and the propagation laws. Taking the physical and hardware limitations into account is crucial for characterizing the actual performance of mmWave systems under certain architecture such as analog beamforming. In this context, we consider a broadband frequency dependent array model that explicitly includes incremental time shifts instead of phase shifts between the individual antennas and incorporates a physically defined radiated power. As a consequence of this model, we present a novel joint approach for designing the optimal waveform and beamforming vector for analog beamforming. Our results show that, for sufficiently large array size, the achievable rate is mainly limited by the fundamental trade-off between the analog beamforming gain and signal bandwidth.
Static and Dynamic Robust PCA and Matrix Completion: A Review
Venue: arXiv cs.IT 2018
Year: 2018

Principal Components Analysis (PCA) is one of the most widely used dimension reduction techniques. Robust PCA (RPCA) refers to the problem of PCA when the data may be corrupted by outliers. Recent work by Cand{è}s, Wright, Li, and Ma defined RPCA as a problem of decomposing a given data matrix into the sum of a low-rank matrix (true data) and a sparse matrix (outliers). The column space of the low-rank matrix then gives the PCA solution. This simple definition has lead to a large amount of interesting new work on provably correct, fast, and practical solutions to RPCA. More recently, the dynamic (time-varying) version of the RPCA problem has been studied and a series of provably correct, fast, and memory efficient tracking solutions have been proposed. Dynamic RPCA (or robust subspace tracking) is the problem of tracking data lying in a (slowly) changing subspace while being robust to sparse outliers. This article provides an exhaustive review of the last decade of literature on RPCA and its dynamic counterpart (robust subspace tracking), along with describing their theoretical guarantees, discussing the pros and cons of various approaches, and providing empirical comparisons of performance and speed. A brief overview of the (low-rank) matrix completion literature is also provided (the focus is on works not discussed in other recent reviews). This refers to the problem of completing a low-rank matrix when only a subset of its entries are observed. It can be interpreted as a simpler special case of RPCA in which the indices of the outlier corrupted entries are known.
Planning Safe Paths through Hazardous Environments
Venue: arXiv cs.RO 2018
Year: 2018

Autonomous underwater vehicles (AUVs) are robotic platforms that are commonly used to map the sea floor, for example for benthic surveys or for naval mine countermeasures (MCM) operations. AUVs create an acoustic image of the survey area, such that objects on the seabed can be identified and, in the case of MCM, mines can be found and disposed of. The common method for creating such seabed maps is to run a lawnmower survey, which is a standard method in coverage path planning. We are interested in exploring alternate techniques for surveying areas of interest, in order to reduce mission time or assess feasible actions, such as finding a safe path through a hazardous region. In this paper, we use Gaussian Process regression to build models of seabed complexity data, obtained through lawnmower surveys. We evaluate several commonly used kernels to assess their modeling performance, which includes modeling discontinuities in the data. Our results show that an additive Matérn kernel is most suitable for modeling seabed complexity data. On top of the GP model, we use adaptations of two standard path planning methods, A* and RRT*, to find safe paths for marine vessels through the modeled areas. We evaluate the planned paths and also run a vehicle dynamics simulator to assess potential performance by a marine vessel.
Autostacker: A Compositional Evolutionary Learning System
Venue: arXiv cs.LG 2018
Year: 2018

We introduce an automatic machine learning (AutoML) modeling architecture called Autostacker, which combines an innovative hierarchical stacking architecture and an Evolutionary Algorithm (EA) to perform efficient parameter search. Neither prior domain knowledge about the data nor feature preprocessing is needed. Using EA, Autostacker quickly evolves candidate pipelines with high predictive accuracy. These pipelines can be used as is or as a starting point for human experts to build on. Autostacker finds innovative combinations and structures of machine learning models, rather than selecting a single model and optimizing its hyperparameters. Compared with other AutoML systems on fifteen datasets, Autostacker achieves state-of-art or competitive performance both in terms of test accuracy and time cost.
On the Structure of Abstract H*-Algebras
Venue: arXiv cs.LO 2018
Year: 2018

Previously we have shown that the topos approach to quantum theory of Doering and Isham can be generalised to a class of categories typically studied within the monoidal approach to quantum theory of Abramsky and Coecke. In the monoidal approach to quantum theory H*-algebras provide an axiomatisation of states and observables. Here we show that H*-algebras naturally correspond with the notions of states and observables in the generalised topos approach to quantum theory. We then combine these results with the dagger-kernel approach to quantum logic of Heunen and Jacobs, which we use to prove a structure theorem for H*-algebras. This structure theorem is a generalisation of the structure theorem of Ambrose for H*-algebras the category of Hilbert spaces.
A Factoid Question Answering System for Vietnamese
Venue: arXiv cs.CL 2018
Year: 2018

In this paper, we describe the development of an end-to-end factoid question answering system for the Vietnamese language. This system combines both statistical models and ontology-based methods in a chain of processing modules to provide high-quality mappings from natural language text to entities. We present the challenges in the development of such an intelligent user interface for an isolating language like Vietnamese and show that techniques developed for inflectional languages cannot be applied "as is". Our question answering system can answer a wide range of general knowledge questions with promising accuracy on a test set.
SCALAR - Simultaneous Calibration of 2D Laser and Robot's Kinematic Parameters Using Three Planar Constraints
Venue: arXiv cs.RO 2018
Year: 2018

Industrial robots are increasingly used in various applications where the robot accuracy becomes very important, hence calibrations of the robot's kinematic parameters and the measurement system's extrinsic parameters are required. However, the existing calibration approaches are either too cumbersome or require another expensive external measurement system such as laser tracker or measurement spinarm. In this paper, we propose SCALAR, a calibration method to simultaneously improve the kinematic parameters of a 6-DoF robot and the extrinsic parameters of a 2D Laser Range Finder (LRF) which is attached to the robot. Three flat planes are placed around the robot, and for each plane the robot moves to several poses such that the LRF's ray intersect the respective plane. Geometric planar constraints are then used to optimize the calibration parameters using Levenberg- Marquardt nonlinear optimization algorithm. We demonstrate through simulations that SCALAR can reduce the average position and orientation errors of the robot system from 14.6mm and 4.05 degrees to 0.09mm and 0.02 degrees.
Aspl{ü}nd's metric defined in the Logarithmic Image Processing (LIP) framework for colour and multivariate images
Venue: arXiv cs.CV 2018
Year: 2018

Aspl{ü}nd's metric, which is useful for pattern matching, consists in a double-sided probing, i.e. the over-graph and the sub-graph of a function are probed jointly. It has previously been defined for grey-scale images using the Logarithmic Image Processing (LIP) framework. LIP is a non-linear model to perform operations between images while being consistent with the human visual system. Our contribution consists in extending the Aspl{ü}nd's metric to colour and multivariate images using the LIP framework. Aspl{ü}nd's metric is insensitive to lighting variations and we propose a colour variant which is robust to noise.
Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve
Venue: arXiv cs.CC 2018
Year: 2018

Can we analyze data without decompressing it? As our data keeps growing, understanding the time complexity of problems on compressed inputs, rather than in convenient uncompressed forms, becomes more and more relevant. Suppose we are given a compression of size $n$ of data that originally has size $N$, and we want to solve a problem with time complexity $T(\cdot)$. The naive strategy of "decompress-and-solve" gives time $T(N)$, whereas "the gold standard" is time $T(n)$: to analyze the compression as efficiently as if the original data was small. We restrict our attention to data in the form of a string (text, files, genomes, etc.) and study the most ubiquitous tasks. While the challenge might seem to depend heavily on the specific compression scheme, most methods of practical relevance (Lempel-Ziv-family, dictionary methods, and others) can be unified under the elegant notion of Grammar Compressions. A vast literature, across many disciplines, established this as an influential notion for Algorithm design. We introduce a framework for proving (conditional) lower bounds in this field, allowing us to assess whether decompress-and-solve can be improved, and by how much. Our main results are: - The $O(nN\sqrt{\log{N/n}})$ bound for LCS and the $O(\min\{N \log N, nM\})$ bound for Pattern Matching with Wildcards are optimal up to $N^{o(1)}$ factors, under the Strong Exponential Time Hypothesis. (Here, $M$ denotes the uncompressed length of the compressed pattern.) - Decompress-and-solve is essentially optimal for Context-Free Grammar Parsing and RNA Folding, under the $k$-Clique conjecture. - We give an algorithm showing that decompress-and-solve is not optimal for Disjointness.
A more globally accurate dimensionality reduction method using triplets
Venue: arXiv cs.LG 2018
Year: 2018

We first show that the commonly used dimensionality reduction (DR) methods such as t-SNE and LargeVis poorly capture the global structure of the data in the low dimensional embedding. We show this via a number of tests for the DR methods that can be easily applied by any practitioner to the dataset at hand. Surprisingly enough, t-SNE performs the best w.r.t. the commonly used measures that reward the local neighborhood accuracy such as precision-recall while having the worst performance in our tests for global structure. We then contrast the performance of these two DR method against our new method called TriMap. The main idea behind TriMap is to capture higher orders of structure with triplet information (instead of pairwise information used by t-SNE and LargeVis), and to minimize a robust loss function for satisfying the chosen triplets. We provide compelling experimental evidence on large natural datasets for the clear advantage of the TriMap DR results. As LargeVis, TriMap scales linearly with the number of data points.
The Shape of Alerts: Detecting Malware Using Distributed Detectors by Robustly Amplifying Transient Correlations
Venue: arXiv cs.CR 2018
Year: 2018

We introduce a new malware detector - Shape-GD - that aggregates per-machine detectors into a robust global detector. Shape-GD is based on two insights: 1. Structural: actions such as visiting a website (waterhole attack) by nodes correlate well with malware spread, and create dynamic neighborhoods of nodes that were exposed to the same attack vector. However, neighborhood sizes vary unpredictably and require aggregating an unpredictable number of local detectors' outputs into a global alert. 2. Statistical: feature vectors corresponding to true and false positives of local detectors have markedly different conditional distributions - i.e. their shapes differ. The shape of neighborhoods can identify infected neighborhoods without having to estimate neighborhood sizes - on 5 years of Symantec detectors' logs, Shape-GD reduces false positives from ~1M down to ~110K and raises alerts 345 days (on average) before commercial anti-virus products; in a waterhole attack simulated using Yahoo web-service logs, Shape-GD detects infected machines when only ~100 of ~550K are compromised.
A Framework for Blockchain-Based Applications
Venue: arXiv cs.CY 2018
Year: 2018

Blockchains have recently generated explosive interest from both academia and industry, with many proposed applications. But descriptions of many these proposals are more visionary projections than realizable proposals, and even basic definitions are often missing. We define "blockchain" and "blockchain network", and then discuss two very different, well known classes of blockchain networks: cryptocurrencies and Git repositories. We identify common primitive elements of both and use them to construct a framework for explicitly articulating what characterizes blockchain networks. The framework consists of a set of questions that every blockchain initiative should address at the very outset. It is intended to help one decide whether or not blockchain is an appropriate approach to a particular application, and if it is, to assist in its initial design stage.
Impact of Biases in Big Data
Venue: arXiv cs.LG 2018
Year: 2018

The underlying paradigm of big data-driven machine learning reflects the desire of deriving better conclusions from simply analyzing more data, without the necessity of looking at theory and models. Is having simply more data always helpful? In 1936, The Literary Digest collected 2.3M filled in questionnaires to predict the outcome of that year's US presidential election. The outcome of this big data prediction proved to be entirely wrong, whereas George Gallup only needed 3K handpicked people to make an accurate prediction. Generally, biases occur in machine learning whenever the distributions of training set and test set are different. In this work, we provide a review of different sorts of biases in (big) data sets in machine learning. We provide definitions and discussions of the most commonly appearing biases in machine learning: class imbalance and covariate shift. We also show how these biases can be quantified and corrected. This work is an introductory text for both researchers and practitioners to become more aware of this topic and thus to derive more reliable models for their learning problems.
Service-based Fog architecture without DNS redirection
Venue: arXiv cs.NI 2018
Year: 2018

The heterogeneous and distributed nature of the Internet of Things (IoT) is driving the need for extremely fast and fine-grained service provisioning in 5/5+G architectures and beyond. To meet these needs, it is critical to enable efficient and flexible computation and networking fabrics, that can be rapidly reconfigured to meet the computation and communication tasks at hand. In this article, we propose a novel Fog Computing architecture that translates IoT communications into service transactions, provisioned over a fast and efficient networking fabric. Service matching is provided by a network function designed using principles from Information-Centric Networks (ICN) research, routing edge requests directly to the nearest service points without expensive and slow DNS redirects. The proposed Fog substrate reduces the networking complexity and overhead while being architecturally simple. We evaluate the architecture through a comparison with how Fog might be established over existing networking fabrics and quantify the performance benefits. Evaluation results illustrate the superiority of the proposed architecture in reducing the required backhaul capacity and the path length.
Slotted CSMA/CA Based Energy Efficient MAC Protocol Design in Nanonetworks
Venue: arXiv cs.NI 2018
Year: 2018

Devices in a beacon-enabled network use slotted CSMA/CA to contend for channel usage. Each node in the network competes for the channels when ready to transmit data. The slotted CSMA/CA mechanism based on the super-frame structure fairly provides communication chance for each node and makes a reasonable usage of the available energy in beacon-enabled Zigbee networks. When wireless nano-sensor nodes are implanted into the target human body area for detecting disease symptoms or virus existence, each node also requires a similar characteristic in channel sharing and in the transmission of event-driven data with a short length. In this paper, we suggest a wireless network model with nano-sensor nodes for the in-body application. We propose a novel MAC protocol derived from an existing Zigbee MAC protocol scheme and analyze the performance of energy usage with variable super-frame durations and packet sizes.
DEMorphy, German Language Morphological Analyzer
Venue: arXiv cs.CL 2018
Year: 2018

DEMorphy is a morphological analyzer for German. It is built onto large, compactified lexicons from German Morphological Dictionary. A guesser based on German declension suffixed is also provided. For German, we provided a state-of-art morphological analyzer. DEMorphy is implemented in Python with ease of usability and accompanying documentation. The package is suitable for both academic and commercial purposes wit a permissive licence.
Multivariate Fine-Grained Complexity of Longest Common Subsequence
Venue: arXiv cs.CC 2018
Year: 2018

We revisit the classic combinatorial pattern matching problem of finding a longest common subsequence (LCS). For strings $x$ and $y$ of length $n$, a textbook algorithm solves LCS in time $O(n^2)$, but although much effort has been spent, no $O(n^{2-\varepsilon})$-time algorithm is known. Recent work indeed shows that such an algorithm would refute the Strong Exponential Time Hypothesis (SETH) [Abboud, Backurs, Vassilevska Williams + Bringmann, Künnemann FOCS'15]. Despite the quadratic-time barrier, for over 40 years an enduring scientific interest continued to produce fast algorithms for LCS and its variations. Particular attention was put into identifying and exploiting input parameters that yield strongly subquadratic time algorithms for special cases of interest, e.g., differential file comparison. This line of research was successfully pursued until 1990, at which time significant improvements came to a halt. In this paper, using the lens of fine-grained complexity, our goal is to (1) justify the lack of further improvements and (2) determine whether some special cases of LCS admit faster algorithms than currently known. To this end, we provide a systematic study of the multivariate complexity of LCS, taking into account all parameters previously discussed in the literature: the input size $n:=\max\{|x|,|y|\}$, the length of the shorter string $m:=\min\{|x|,|y|\}$, the length $L$ of an LCS of $x$ and $y$, the numbers of deletions $δ:= m-L$ and $Δ:= n-L$, the alphabet size, as well as the numbers of matching pairs $M$ and dominant pairs $d$. For any class of instances defined by fixing each parameter individually to a polynomial in terms of the input size, we prove a SETH-based lower bound matching one of three known algorithms. Specifically, we determine the optimal running time for LCS under SETH as $(n+\min\{d, δΔ, δm\})^{1\pm o(1)}$. [...]
Estimation of Poisson arrival processes under linear models
Venue: arXiv cs.IT 2018
Year: 2018

In this paper we consider the problem of estimating the parameters of a Poisson arrival process where the rate function is assumed to lie in the span of a known basis. Our goal is to estimate the basis expansions coefficients given a realization of this process. We establish novel guarantees concerning the accuracy achieved by the maximum likelihood estimate. Our initial result is near-optimal, with the exception of an undesirable dependence on the dynamic range of the rate function. We then show how to remove this dependence through a process of "noise regularization", which results in an improved bound. We conjecture that a similar guarantee should be possible when using a more direct (deterministic) regularization scheme. We conclude with a discussion of practical applications and an empirical examination of the proposed regularization schemes.
Hybrid Model For Word Prediction Using Naive Bayes and Latent Information
Venue: arXiv cs.CL 2018
Year: 2018

Historically, the Natural Language Processing area has been given too much attention by many researchers. One of the main motivation beyond this interest is related to the word prediction problem, which states that given a set words in a sentence, one can recommend the next word. In literature, this problem is solved by methods based on syntactic or semantic analysis. Solely, each of these analysis cannot achieve practical results for end-user applications. For instance, the Latent Semantic Analysis can handle semantic features of text, but cannot suggest words considering syntactical rules. On the other hand, there are models that treat both methods together and achieve state-of-the-art results, e.g. Deep Learning. These models can demand high computational effort, which can make the model infeasible for certain types of applications. With the advance of the technology and mathematical models, it is possible to develop faster systems with more accuracy. This work proposes a hybrid word suggestion model, based on Naive Bayes and Latent Semantic Analysis, considering neighbouring words around unfilled gaps. Results show that this model could achieve 44.2% of accuracy in the MSR Sentence Completion Challenge.
Control Contraction Metrics on Finsler Manifolds
Venue: arXiv cs.SY 2018
Year: 2018

Control Contraction Metrics (CCMs) provide a nonlinear controller design involving an offline search for a Riemannian metric and an online search for a shortest path between the current and desired trajectories. In this paper, we generalize CCMs to Finsler geometry, allowing the use of non-Riemannian metrics. We provide open loop and sampled data controllers. The sampled data control construction presented here does not require real time computation of globally shortest paths, simplifying computation.