OpenRaiser/Intern-Atlas huggingface dataset:
Equilibrium Computation in Atomic Splittable Routing Games with Convex Cost Functions
Venue: arXiv cs.GT 2018
Year: 2018

We present polynomial-time algorithms as well as hardness results for equilibrium computation in atomic splittable routing games, for the case of general convex cost functions. These games model traffic in freight transportation, market oligopolies, data networks, and various other applications. An atomic splittable routing game is played on a network where the edges have traffic-dependent cost functions, and player strategies correspond to flows in the network. A player can thus split it's traffic arbitrarily among different paths. While many properties of equilibria in these games have been studied, efficient algorithms for equilibrium computation are known for only two cases: if cost functions are affine, or if players are symmetric. Neither of these conditions is met in most practical applications. We present two algorithms for routing games with general convex cost functions on parallel links. The first algorithm is exponential in the number of players, while the second is exponential in the number of edges; thus if either of these is small, we get a polynomial-time algorithm. These are the first algorithms for these games with convex cost functions. Lastly, we show that in general networks, given input $C$, it is NP-hard to decide if there exists an equilibrium where every player has cost at most $C$.
QuickMergesort: Practically Efficient Constant-Factor Optimal Sorting
Venue: arXiv cs.DS 2018
Year: 2018

We consider the fundamental problem of internally sorting a sequence of $n$ elements. In its best theoretical setting QuickMergesort, a combination Quicksort with Mergesort with a Median-of-$\sqrt{n}$ pivot selection, requires at most $n \log n - 1.3999n + o(n)$ element comparisons on the average. The questions addressed in this paper is how to make this algorithm practical. As refined pivot selection usually adds much overhead, we show that the Median-of-3 pivot selection of QuickMergesort leads to at most $n \log n - 0{.}75n + o(n)$ element comparisons on average, while running fast on elementary data. The experiments show that QuickMergesort outperforms state-of-the-art library implementations, including C++'s Introsort and Java's Dual-Pivot Quicksort. Further trade-offs between a low running time and a low number of comparisons are studied. Moreover, we describe a practically efficient version with $n \log n + O(n)$ comparisons in the worst case.
Big Data Analytic based on Scalable PANFIS for RFID Localization
Venue: arXiv cs.DC 2018
Year: 2018

RFID technology has gained popularity to address localization problem in the manufacturing shopfloor due to its affordability and easiness in deployment. This technology is used to track the manufacturing object location to increase the production efficiency. However, the data used for localization task is not easy to analyze because it is generated from the non-stationary environment. It also continuously arrive over time and yields the large-volume of data. Therefore, an advanced big data analytic is required to overcome this problem. We propose a distributed big data analytic framework based on PANFIS (Scalable PANFIS), where PANFIS is an evolving algorithm which has capability to learn data stream in the single pass mode. Scalable PANFIS can learn big data stream by processing many chunks/partitions of data stream. Scalable PANFIS is also equipped with rule structure merging to eliminate the redundancy among rules. Scalable PANFIS is validated by measuring its performance against single PANFIS and other Spark scalable machine learning algorithms. The result shows that Scalable PANFIS performs running time more than 20 times faster than single PANFIS. The rule merging process in Scalable PANFIS shows that there is no significant reduction of accuracy in classification task with 96.67 percent of accuracy in comparison with single PANFIS of 98.71 percent. Scalable PANFIS also generally outperforms some Spark MLib machine learnings to classify RFID data with the comparable speed in running time.
Capsule networks for low-data transfer learning
Venue: arXiv cs.CV 2018
Year: 2018

We propose a capsule network-based architecture for generalizing learning to new data with few examples. Using both generative and non-generative capsule networks with intermediate routing, we are able to generalize to new information over 25 times faster than a similar convolutional neural network. We train the networks on the multiMNIST dataset lacking one digit. After the networks reach their maximum accuracy, we inject 1-100 examples of the missing digit into the training set, and measure the number of batches needed to return to a comparable level of accuracy. We then discuss the improvement in low-data transfer learning that capsule networks bring, and propose future directions for capsule research.
Communication over an Arbitrarily Varying Channel under a State-Myopic Encoder
Venue: arXiv cs.IT 2018
Year: 2018

We study the problem of communication over a discrete arbitrarily varying channel (AVC) when a noisy version of the state is known non-causally at the encoder. The state is chosen by an adversary which knows the coding scheme. A state-myopic encoder observes this state non-causally, though imperfectly, through a noisy discrete memoryless channel (DMC). We first characterize the capacity of this state-dependent channel when the encoder-decoder share randomness unknown to the adversary, i.e., the randomized coding capacity. Next, we show that when only the encoder is allowed to randomize, the capacity remains unchanged when positive. Interesting and well-known special cases of the state-myopic encoder model are also presented.
Decoding Reed-Muller Codes Using Minimum-Weight Parity Checks
Venue: arXiv cs.IT 2018
Year: 2018

Reed-Muller (RM) codes exhibit good performance under maximum-likelihood (ML) decoding due to their highly-symmetric structure. In this paper, we explore the question of whether the code symmetry of RM codes can also be exploited to achieve near-ML performance in practice. The main idea is to apply iterative decoding to a highly-redundant parity-check (PC) matrix that contains only the minimum-weight dual codewords as rows. As examples, we consider the peeling decoder for the binary erasure channel, linear-programming and belief propagation (BP) decoding for the binary-input additive white Gaussian noise channel, and bit-flipping and BP decoding for the binary symmetric channel. For short block lengths, it is shown that near-ML performance can indeed be achieved in many cases. We also propose a method to tailor the PC matrix to the received observation by selecting only a small fraction of useful minimum-weight PCs before decoding begins. This allows one to both improve performance and significantly reduce complexity compared to using the full set of minimum-weight PCs.
Communication, Computing and Caching for Mobile VR Delivery: Modeling and Trade-off
Venue: arXiv cs.IT 2018
Year: 2018

Mobile virtual reality (VR) delivery is gaining increasing attention from both industry and academia due to its ability to provide an immersive experience. However, achieving mobile VR delivery requires ultra-high transmission rate, deemed as a first killer application for 5G wireless networks. In this paper, in order to alleviate the traffic burden over wireless networks, we develop an implementation framework for mobile VR delivery by utilizing caching and computing capabilities of mobile VR device. We then jointly optimize the caching and computation offloading policy for minimizing the required average transmission rate under the latency and local average energy consumption constraints. In a symmetric scenario, we obtain the optimal joint policy and the closed-form expression of the minimum average transmission rate. Accordingly, we analyze the tradeoff among communication, computing and caching, and then reveal analytically the fact that the communication overhead can be traded by the computing and caching capabilities of mobile VR device, and also what conditions must be met for it to happen. Finally, we discuss the optimization problem in a heterogeneous scenario, and propose an efficient suboptimal algorithm with low computation complexity, which is shown to achieve good performance in the numerical results.
Attacks and Defenses in Mobile IP: Modeling with Stochastic Game Petri Net
Venue: arXiv cs.NI 2018
Year: 2018

The urging need for seamless connectivity in mobile environment has contributed to the rapid expansion of Mobile IP. Mobile IP uses wireless transmission medium, thereby making it subject to many security threats during various phases of route optimization. Modeling Mobile IP attacks reasonably and efficiently is the basis for defending against those attacks, which requires quantitative analysis and modeling approaches for expressing threat propagation in Mobile IP. In this Paper, we present four well-known Mobile IP attacks, such as Denial-of-Service (DoS) attack, bombing attack, redirection attack and replay attack and model them with Stochastic Game Petri Net (SGPN). Furthermore, we propose mixed strategy based defense strategies for the aforementioned attacks and model them with SGPN. Finally, we calculate the Nash Equilibrium of the attacker-defender game and thereby obtain the steady state probability of the vulnerable attack states. We show that, under the optimal strategy, an IDS needs to remain active 72.4%, 70%, 68.4% and 66.6% of the time to restrict the attacker's success rate to 8.5%, 6.4%, 7.2% and 8.3% respectively for the aforementioned attacks, thus performing better than the state-of-the-art approach.
Exploiting the Superposition Property of Wireless Communication For Average Consensus Problems in Multi-Agent Systems
Venue: arXiv cs.SY 2018
Year: 2018

This paper studies system stability and performance of multi-agent systems in the context of consensus problems over wireless multiple-access channels (MAC). We propose a consensus algorithm that exploits the broadcast property of the wireless channel. Therefore, the algorithm is expected to exhibit fast convergence and high efficiency in terms of the usage of scarce wireless resources. The designed algorithm shows robustness against variations in the channel and consensus is always reached. However the consensus value will be depending on these variations.
Regularized Nonparametric Volterra Kernel Estimation
Venue: arXiv cs.SY 2018
Year: 2018

In this paper, the regularization approach introduced recently for nonparametric estimation of linear systems is extended to the estimation of nonlinear systems modelled as Volterra series. The kernels of order higher than one, representing higher dimensional impulse responses in the series, are considered to be realizations of multidimensional Gaussian processes. Based on this, prior information about the structure of the Volterra kernel is introduced via an appropriate penalization term in the least squares cost function. It is shown that the proposed method is able to deliver accurate estimates of the Volterra kernels even in the case of a small amount of data points.
Bound and Conquer: Improving Triangulation by Enforcing Consistency
Venue: arXiv cs.CV 2018
Year: 2018

We study the accuracy of triangulation in multi-camera systems with respect to the number of cameras. We show that, under certain conditions, the optimal achievable reconstruction error decays quadratically as more cameras are added to the system. Furthermore, we analyse the error decay-rate of major state-of-the-art algorithms with respect to the number of cameras. To this end, we introduce the notion of consistency for triangulation, and show that consistent reconstruction algorithms achieve the optimal quadratic decay, which is asymptotically faster than some other methods. Finally, we present simulations results supporting our findings. Our simulations have been implemented in MATLAB and the resulting code is available in the supplementary material.
Weaver: Deep Co-Encoding of Questions and Documents for Machine Reading
Venue: arXiv cs.CL 2018
Year: 2018

This paper aims at improving how machines can answer questions directly from text, with the focus of having models that can answer correctly multiple types of questions and from various types of texts, documents or even from large collections of them. To that end, we introduce the Weaver model that uses a new way to relate a question to a textual context by weaving layers of recurrent networks, with the goal of making as few assumptions as possible as to how the information from both question and context should be combined to form the answer. We show empirically on six datasets that Weaver performs well in multiple conditions. For instance, it produces solid results on the very popular SQuAD dataset (Rajpurkar et al., 2016), solves almost all bAbI tasks (Weston et al., 2015) and greatly outperforms state-of-the-art methods for open domain question answering from text (Chen et al., 2017).
Intermediate Data Caching Optimization for Multi-Stage and Parallel Big Data Frameworks
Venue: arXiv cs.PF 2018
Year: 2018

In the era of big data and cloud computing, large amounts of data are generated from user applications and need to be processed in the datacenter. Data-parallel computing frameworks, such as Apache Spark, are widely used to perform such data processing at scale. Specifically, Spark leverages distributed memory to cache the intermediate results, represented as Resilient Distributed Datasets (RDDs). This gives Spark an advantage over other parallel frameworks for implementations of iterative machine learning and data mining algorithms, by avoiding repeated computation or hard disk accesses to retrieve RDDs. By default, caching decisions are left at the programmer's discretion, and the LRU policy is used for evicting RDDs when the cache is full. However, when the objective is to minimize total work, LRU is woefully inadequate, leading to arbitrarily suboptimal caching decisions. In this paper, we design an algorithm for multi-stage big data processing platforms to adaptively determine and cache the most valuable intermediate datasets that can be reused in the future. Our solution automates the decision of which RDDs to cache: this amounts to identifying nodes in a direct acyclic graph (DAG) representing computations whose outputs should persist in the memory. Our experiment results show that our proposed cache optimization solution can improve the performance of machine learning applications on Spark decreasing the total work to recompute RDDs by 12%.
Certified Graph View Maintenance with Regular Datalog
Venue: arXiv cs.DB 2018
Year: 2018

We employ the Coq proof assistant to develop a mechanically-certified framework for evaluating graph queries and incrementally maintaining materialized graph instances, also called views. The language we use for defining queries and views is Regular Datalog (RD) -- a notable fragment of non-recursive Datalog that can express complex navigational queries, with transitive closure as native operator. We first design and encode the theory of RD and then mechanize a RD-specific evaluation algorithm capable of fine-grained, incremental graph view computation, which we prove sound with respect to the declarative RD semantics. By using the Coq extraction mechanism, we test an Ocaml version of the verified engine on a set of preliminary benchmarks. Our development is particularly focused on leveraging existing verification and notational techniques to: a) define mechanized properties that can be easily understood by logicians and database researchers and b) attain formal verification with limited effort. Our work is the first step towards a unified, machine-verified, formal framework for dynamic graph query languages and their evaluation engines. This paper is under consideration for acceptance in TPLP.
Queuing Theoretic Models for Multicast and Coded-Caching in Downlink Wireless Systems
Venue: arXiv cs.PF 2018
Year: 2018

We consider a server connected to $L$ users over a shared finite capacity link. Each user is equipped with a cache. File requests at the users are generated as independent Poisson processes according to a popularity profile from a library of $M$ files. The server has access to all the files in the library. Users can store parts of the files or full files from the library in their local caches. The server should send missing parts of the files requested by the users. The server attempts to fulfill the pending requests with minimal transmissions exploiting multicasting and coding opportunities among the pending requests. We study the performance of this system in terms of queuing delays for the naive multicasting and several coded multicasting schemes proposed in the literature. We also provide approximate expressions for the mean queuing delay for these models and establish their effectiveness with simulations.
An Unsupervised Word Sense Disambiguation System for Under-Resourced Languages
Venue: arXiv cs.CL 2018
Year: 2018

In this paper, we present Watasense, an unsupervised system for word sense disambiguation. Given a sentence, the system chooses the most relevant sense of each input word with respect to the semantic similarity between the given sentence and the synset constituting the sense of the target word. Watasense has two modes of operation. The sparse mode uses the traditional vector space model to estimate the most similar word sense corresponding to its context. The dense mode, instead, uses synset embeddings to cope with the sparsity problem. We describe the architecture of the present system and also conduct its evaluation on three different lexical semantic resources for Russian. We found that the dense mode substantially outperforms the sparse one on all datasets according to the adjusted Rand index.
Modified Apriori Graph Algorithm for Frequent Pattern Mining
Venue: arXiv cs.AI 2018
Year: 2018

Web Usage Mining is an application of Data Mining Techniques to discover interesting usage patterns from web data in order to understand and better serve the needs of web-based applications. The paper proposes an algorithm for finding these usage patterns using a modified version of Apriori Algorithm called Apriori-Graph. These rules will help service providers to predict, which web pages, the user is likely to visit next. This will optimize the website in terms of efficiency, bandwidth and will have positive economic benefits for them. The proposed Apriori Graph Algorithm O((V)(E)) works faster compared to the existing Apriori Algorithm and is well suitable for real-time application.
Extracting the Most Weighted Throughput in UAV Empowered Wireless Systems With Nonlinear Energy Harvester
Venue: arXiv cs.IT 2018
Year: 2018

With the maturity of unmanned aerial vehicle (UAV) technology, this work investigates the integration of UAV into wireless communication systems. Since the UAV is powered by a capacity-limited battery, this work proposes to use the radio energy harvesting technology at the UAV in order to extend the lifetime of UAV empowered base station. To extract the most weighted throughput of UAV empowered wireless systems, the dirty paper coding scheme and information-theoretic uplink-downlink channel duality are exploited to propose an extracting the most weighted throughput algorithm. Numerical results are used to verify the proposed algorithm.
Grey-box state-space identification of nonlinear mechanical vibrations
Venue: arXiv cs.SY 2018
Year: 2018

The present paper deals with the identification of nonlinear mechanical vibrations. A grey-box, or semi-physical, nonlinear state-space representation is introduced, expressing the nonlinear basis functions using a limited number of measured output variables. This representation assumes that the observed nonlinearities are localised in physical space, which is a generic case in mechanics. A two-step identification procedure is derived for the grey-box model parameters, integrating nonlinear subspace initialisation and weighted least-squares optimisation. The complete procedure is applied to an electrical circuit mimicking the behaviour of a single-input, single-output (SISO) nonlinear mechanical system and to a single-input, multiple-output (SIMO) geometrically nonlinear beam structure.
Detect, Quantify, and Incorporate Dataset Bias: A Neuroimaging Analysis on 12,207 Individuals
Venue: arXiv cs.CV 2018
Year: 2018

Neuroimaging datasets keep growing in size to address increasingly complex medical questions. However, even the largest datasets today alone are too small for training complex models or for finding genome wide associations. A solution is to grow the sample size by merging data across several datasets. However, bias in datasets complicates this approach and includes additional sources of variation in the data instead. In this work, we combine 15 large neuroimaging datasets to study bias. First, we detect bias by demonstrating that scans can be correctly assigned to a dataset with 73.3% accuracy. Next, we introduce metrics to quantify the compatibility across datasets and to create embeddings of neuroimaging sites. Finally, we incorporate the presence of bias for the selection of a training set for predicting autism. For the quantification of the dataset bias, we introduce two metrics: the Bhattacharyya distance between datasets and the age prediction error. The presented embedding of neuroimaging sites provides an interesting new visualization about the similarity of different sites. This could be used to guide the merging of data sources, while limiting the introduction of unwanted variation. Finally, we demonstrate a clear performance increase when incorporating dataset bias for training set selection in autism prediction. Overall, we believe that the growing amount of neuroimaging data necessitates to incorporate data-driven methods for quantifying dataset bias in future analyses.
Specifying and Verbalising Answer Set Programs in Controlled Natural Language
Venue: arXiv cs.AI 2018
Year: 2018

We show how a bi-directional grammar can be used to specify and verbalise answer set programs in controlled natural language. We start from a program specification in controlled natural language and translate this specification automatically into an executable answer set program. The resulting answer set program can be modified following certain naming conventions and the revised version of the program can then be verbalised in the same subset of natural language that was used as specification language. The bi-directional grammar is parametrised for processing and generation, deals with referring expressions, and exploits symmetries in the data structure of the grammar rules whenever these grammar rules need to be duplicated. We demonstrate that verbalisation requires sentence planning in order to aggregate similar structures with the aim to improve the readability of the generated specification. Without modifications, the generated specification is always semantically equivalent to the original one; our bi-directional grammar is the first one that allows for semantic round-tripping in the context of controlled natural language processing. This paper is under consideration for acceptance in TPLP.
Binary reachability of timed pushdown automata via quantifier elimination and cyclic order atoms
Venue: arXiv cs.FL 2018
Year: 2018

We study an expressive model of timed pushdown automata extended with modular and fractional clock constraints. We show that the binary reachability relation is effectively expressible in hybrid linear arithmetic with a rational and an integer sort. This subsumes analogous expressibility results previously known for finite and pushdown timed automata with untimed stack. As key technical tools, we use quantifier elimination for a fragment of hybrid linear arithmetic and for cyclic order atoms, and a reduction to register pushdown automata over cyclic order atoms.