OpenRaiser/Intern-Atlas huggingface dataset:
Perfect Memory Context Trees in time series modeling
Venue: arXiv cs.LO 2016
Year: 2016

The Stochastic Context Tree (SCOT) is a useful tool for studying infinite random sequences generated by an m-Markov Chain (m-MC). It captures the phenomenon that the probability distribution of the next state sometimes depends on less than m of the preceding states. This allows compressing the information needed to describe an m-MC. The SCOT construction has been earlier used under various names: VLMC, VOMC, PST, CTW. In this paper we study the possibility of reducing the m-MC to a 1-MC on the leaves of the SCOT. Such context trees are called perfect-memory. We give various combinatorial characterizations of perfect-memory context trees and an efficient algorithm to find the minimal perfect-memory extension of a SCOT.
The Dynamic Descriptive Complexity of k-Clique
Venue: arXiv cs.LO 2016
Year: 2016

In this work the dynamic descriptive complexity of the k-clique query is studied. It is shown that when edges may only be inserted then k-clique can be maintained by a quantifier-free update program of arity k-1, but it cannot be maintained by a quantifier-free update program of arity k-2 (even in the presence of unary auxiliary functions). This establishes an arity hierarchy for graph queries for quantifier-free update programs under insertions. The proof of the lower bound uses upper and lower bounds for Ramsey numbers.
Improved Lower Bounds for Graph Embedding Problems
Venue: arXiv cs.CC 2016
Year: 2016

In this paper, we give new, tight subexponential lower bounds for a number of graph embedding problems. We introduce two related combinatorial problems, which we call String Crafting and Orthogonal Vector crafting, and show that these cannot be solved in time $2^{o(|s|/\log{|s|})}$, unless the Exponential Time Hypothesis fails. These results are used to obtain simplified hardness results for several graph embedding problems, on more restricted graph classes than previously known: assuming the Exponential Time Hypothesis, there do not exist algorithms that run in $2^{o(n/\log n)}$ time for Subgraph Isomorphism on graphs of pathwidth 1, Induced Subgraph Isomorphism on graphs of pathwidth 1, Graph Minor on graphs of pathwidth 1, Induced Graph Minor on graphs of pathwidth 1, Intervalizing 5-Colored Graphs on trees, and finding a tree or path decomposition with width at most $c$ with a minimum number of bags, for any fixed $c\geq 16$. $2^{Θ(n/\log n)}$ appears to be the "correct" running time for many packing and embedding problems on restricted graph classes, and we think String Crafting and Orthogonal Vector Crafting form a useful framework for establishing lower bounds of this form.
Towards Asymptotically Optimal One-to-One PDP Algorithms for Capacity 2+ Vehicles
Venue: arXiv cs.CC 2016
Year: 2016

We consider the one-to-one Pickup and Delivery Problem (PDP) in Euclidean Space with arbitrary dimension $d$ where $n$ transportation requests are picked i.i.d. with a separate origin-destination pair for each object to be moved. First, we consider the problem from the customer perspective where the objective is to compute a plan for transporting the objects such that the Euclidean distance traveled by the vehicles when carrying objects is minimized. We develop a polynomial time asymptotically optimal algorithm for vehicles with capacity $o(\sqrt[2d]{n})$ for this case. This result also holds imposing LIFO constraints for loading and unloading objects. Secondly, we extend our algorithm to the classical single-vehicle PDP where the objective is to minimize the total distance traveled by the vehicle and present results indicating that the extended algorithm is asymptotically optimal for a fixed vehicle capacity if the origins and destinations are picked i.i.d. using the same distribution.
Grey-box nonlinear state-space modelling for mechanical vibrations identification
Venue: arXiv cs.SY 2016
Year: 2016

In the present paper, a flexible and parsimonious model of the vibrations of nonlinear mechanical systems is introduced in the form of state-space equations. It is shown that the nonlinear model terms can be formed using a limited number of output measurements. A two-step identification procedure is derived for this grey-box model, integrating nonlinear subspace initialisation and maximum likelihood optimisation. The complete procedure is demonstrated on the Silverbox benchmark, which is an electrical mimicry of a single-degree-of-freedom mechanical system with one displacement-dependent nonlinearity.
Effects of Social Ties in Knowledge Diffusion: case study on PLOS ONE
Venue: arXiv cs.SI 2016
Year: 2016

In order to capture the effects of social ties in knowledge diffusion, this paper examines the publication network that emerges from the collaboration of researchers, using citation information as means to estimate knowledge flow. For this purpose, we analyzed the papers published in the PLOS ONE journal finding strong evidence to support that the closer two authors are in the co-authorship network, the larger the probability that knowledge flow will occur between them. Moreover, we also found that when it comes to knowledge diffusion, strong co-authorship proximity is more determinant than geographic proximity.
On the Connection Between Different Noise Structures for LPV-SS Models
Venue: arXiv cs.SY 2016
Year: 2016

Different representations to describe noise processes and finding connections or equivalence between them have been part of active research for decades, in particular for linear time-invariant case. In this paper the linear parameter-varying (LPV) setting is addressed; starting with the connection between an LPV state-space (SS) representation with a general noise structure and the LPV-SS model in an innovation structure, i.e., the Kalman filter. More specifically, the considered LPV-SS representation with general noise structure has static, affine dependence on the scheduling signal; however, we show that its companion innovation structure has a dynamic, rational dependency structure. Following, we would like to highlight the consequences of approximating this Kalman gain by a static, affine dependency structure. To this end, firstly, we use the "fading memory" effect of the Kalman filter to reason how the Kalman gain can be approximated to depend only on a partial trajectory of the scheduling signal. This effect is shown by proving an asymptotically decreasing error upper bound on the covariance matrix associated to the innovation structure in case the covariance matrix is subjected to an incorrect initialization or disturbance. Secondly, we show by an example that an LPV-SS representation that has dynamical, rational dependency on the scheduling signal can be transformed into static, affinely dependent representation by introducing additional states. Therefore, an approximated Kalman gain can, in some cases, be represented by a static, affine Kalman gain at the cost of additional states.
Decentralized Power Control for Slotted Spread Spectrum Aloha with Successive Interference Cancellation
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we study slotted Spread Spectrum Aloha with Successive Interference Cancellation at the receiver over a Gaussian channel. We consider a decentralized power control setting in which each user chooses its transmit power independently at random according to a power distribution with continuous support. In this setting, we derive an analytical expression for the expected interference power experienced by a user. This allows us to derive analytically the power distribution that, during the Successive Interference Cancellation process leads to a constant signal to noise plus interference ratio for all users. We consider both perfect and imperfect interference cancellation.
Integration Checker of JAVA P2P distributed System with Auto Source Code Composition
Venue: arXiv cs.CR 2016
Year: 2016

This paper presents an integrity checker of JAVA P2P distributed system with auto source code composition. JAVA distributed system must guarantee the integrity of program itself and the system components of JAVA virtual machine against attackers, hackers, spies, cheaters, conspirators, etc. There are lots of trusted computing methods to guarantee the integrity of the system. We here present a novel method using just-in-time auto source code composition to generate autocheck class for integrity measure and encrypt of integrity reporting. By companies' effort, we have implemented and use it in DSCloud platform.
Radio Link Planning made easy with a Telegram Bot
Venue: arXiv cs.NI 2016
Year: 2016

Traditional radio planning tools present a steep learning curve. We present BotRf, a Telegram Bot that facilitates the process by guiding non-experts in assessing the feasibility of radio links. Built on open source tools, BotRf can run on any smartphone or PC running Telegram. Using it on a smartphone has the added value that the Bot can leverage the internal GPS to enter coordinates. BotRf can be used in environments with low bandwidth as the generated data traffic is quite limited. We present examples of its use in Venezuela.
Performance Impact of LOS and NLOS Transmissions in Dense Cellular Networks under Rician Fading
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we analyse the performance of dense small cell network (SCNs). We derive analytical expressions for both their coverage probability and their area spectral efficiency (ASE) using a path loss model that considers both line-of-sight (LOS) and non-LOS (NLOS) components. Due to the close proximity of small cell base stations (BSs) and user equipments (UEs) in such dense SCNs, we also consider Rician fading as the multi-path fading channel model for both the LOS and NLOS fading transmissions. The Rayleigh fading used in most of existing works analysing dense SCNs is not accurate enough. Then, we compare the performance impact of LOS and NLOS transmissions in dense SCNs under Rician fading with that based on Rayleigh fading. The analysis and the simulation results show that in dense SCNs where LOS transmissions dominate the performance, the impact of Rician fading on the overall system performance is minor, and does not help to address the performance losses brought by the transition of many interfering signals from NLOS to LOS.
On Achievability for Downlink Cloud Radio Access Networks with Base Station Cooperation
Venue: arXiv cs.IT 2016
Year: 2016

This work investigates the downlink of a cloud radio access network (C-RAN) in which a central processor communicates with two mobile users through two base stations (BSs). The BSs act as relay nodes and cooperate with each other through error-free rate-limited links. We develop and analyze two coding schemes for this scenario. The first coding scheme is based on Liu-Kang scheme for C-RANs without BS cooperation; and extends it to scenarios allowing conferencing between the BSs. Among few other features, our new coding scheme enables arbitrary correlation among the auxiliary codewords that are recovered by the BSs. It also introduces common codewords to be described to both BSs. For the analysis of this coding scheme, we extend the multivariate covering lemma to non-Cartesian product sets, thereby correcting an erroneous application of this lemma in Liu-Kang's related work. We highlight key aspects of this scheme by studying three important instances of it. The second coding scheme extends the so-called compression scheme that was originally developed for memoryless Gaussian C-RANs without BS cooperation to general discrete memoryless C-RANs with BS cooperation. We show that this scheme subsumes the original compression scheme when applied to memoryless Gaussian C-RAN models. In the analysis of this scheme, we also highlight important connections with the so-called distributed decode--forward scheme, and refine the approximate capacity of a general $N$-BS $L$-user C-RAN model in the memoryless Gaussian case.
Probabilistic Model Checking for Complex Cognitive Tasks -- A case study in human-robot interaction
Venue: arXiv cs.AI 2016
Year: 2016

This paper proposes to use probabilistic model checking to synthesize optimal robot policies in multi-tasking autonomous systems that are subject to human-robot interaction. Given the convincing empirical evidence that human behavior can be related to reinforcement models, we take as input a well-studied Q-table model of the human behavior for flexible scenarios. We first describe an automated procedure to distill a Markov decision process (MDP) for the human in an arbitrary but fixed scenario. The distinctive issue is that -- in contrast to existing models -- under-specification of the human behavior is included. Probabilistic model checking is used to predict the human's behavior. Finally, the MDP model is extended with a robot model. Optimal robot policies are synthesized by analyzing the resulting two-player stochastic game. Experimental results with a prototypical implementation using PRISM show promising results.
Spatial-Temporal BEM and Channel Estimation Strategy for Massive MIMO Time-Varying Systems
Venue: arXiv cs.IT 2016
Year: 2016

This paper proposes a new channel estimation scheme for the multiuser massive multiple-input multiple-output (MIMO) systems in time-varying environment. We introduce a discrete Fourier transform (DFT) aided spatial-temporal basis expansion model (ST-BEM) to reduce the effective dimensions of uplink/downlink channels, such that training overhead and feedback cost could be greatly decreased. The newly proposed ST-BEM is suitable for both time division duplex (TDD) systems and frequency division duplex (FDD) systems thanks to the angle reciprocity, and can be efficiently deployed by fast Fourier transform (FFT). Various numerical results have corroborated the proposed studies.
Microservice-based IoT for Smart Buildings
Venue: arXiv cs.CY 2016
Year: 2016

A large percentage of buildings in domestic or special-purpose is expected to become increasingly "smarter" in the future, due to the immense benefits in terms of energy saving, safety, flexibility, and comfort, that relevant new technologies offer. As concerns hardware, software, or platform level, however, no clearly dominant standards currently exist. Such standards, would ideally, fulfill a number of important desiderata, which are to be touched upon in this paper. Here, we will present a prototype platform for supporting multiple concurrent applications for smart buildings, which is utilizing an advanced sensor network as well as a distributed microservices architecture, centrally featuring the Jolie programming language. The architecture and benefits of our system are discussed, as well as a prototype containing a number of nodes and a user interface, deployed in a real-world academic building environment. Our results illustrate the promising nature of our approach, as well as open avenues for future work towards its wider and larger scale applicability.
Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
Venue: arXiv cs.LG 2016
Year: 2016

This paper studies systematic exploration for reinforcement learning with rich observations and function approximation. We introduce a new model called contextual decision processes, that unifies and generalizes most prior settings. Our first contribution is a complexity measure, the Bellman rank, that we show enables tractable learning of near-optimal behavior in these processes and is naturally small for many well-studied reinforcement learning settings. Our second contribution is a new reinforcement learning algorithm that engages in systematic exploration to learn contextual decision processes with low Bellman rank. Our algorithm provably learns near-optimal behavior with a number of samples that is polynomial in all relevant parameters but independent of the number of unique observations. The approach uses Bellman error minimization with optimistic exploration and provides new insights into efficient exploration for reinforcement learning with function approximation.
Finding Street Gang Members on Twitter
Venue: arXiv cs.SI 2016
Year: 2016

Most street gang members use Twitter to intimidate others, to present outrageous images and statements to the world, and to share recent illegal activities. Their tweets may thus be useful to law enforcement agencies to discover clues about recent crimes or to anticipate ones that may occur. Finding these posts, however, requires a method to discover gang member Twitter profiles. This is a challenging task since gang members represent a very small population of the 320 million Twitter users. This paper studies the problem of automatically finding gang members on Twitter. It outlines a process to curate one of the largest sets of verifiable gang member profiles that have ever been studied. A review of these profiles establishes differences in the language, images, YouTube links, and emojis gang members use compared to the rest of the Twitter population. Features from this review are used to train a series of supervised classifiers. Our classifier achieves a promising F1 score with a low false positive rate.
The Processing Using Memory Paradigm:In-DRAM Bulk Copy, Initialization, Bitwise AND and OR
Venue: arXiv cs.AR 2016
Year: 2016

In existing systems, the off-chip memory interface allows the memory controller to perform only read or write operations. Therefore, to perform any operation, the processor must first read the source data and then write the result back to memory after performing the operation. This approach consumes high latency, bandwidth, and energy for operations that work on a large amount of data. Several works have proposed techniques to process data near memory by adding a small amount of compute logic closer to the main memory chips. In this article, we describe two techniques proposed by recent works that take this approach of processing in memory further by exploiting the underlying operation of the main memory technology to perform more complex tasks. First, we describe RowClone, a mechanism that exploits DRAM technology to perform bulk copy and initialization operations completely inside main memory. We then describe a complementary work that uses DRAM to perform bulk bitwise AND and OR operations inside main memory. These two techniques significantly improve the performance and energy efficiency of the respective operations.
Accurate Deep Representation Quantization with Gradient Snapping Layer for Similarity Search
Venue: arXiv cs.CV 2016
Year: 2016

Recent advance of large scale similarity search involves using deeply learned representations to improve the search accuracy and use vector quantization methods to increase the search speed. However, how to learn deep representations that strongly preserve similarities between data pairs and can be accurately quantized via vector quantization remains a challenging task. Existing methods simply leverage quantization loss and similarity loss, which result in unexpectedly biased back-propagating gradients and affect the search performances. To this end, we propose a novel gradient snapping layer (GSL) to directly regularize the back-propagating gradient towards a neighboring codeword, the generated gradients are un-biased for reducing similarity loss and also propel the learned representations to be accurately quantized. Joint deep representation and vector quantization learning can be easily performed by alternatively optimize the quantization codebook and the deep neural network. The proposed framework is compatible with various existing vector quantization approaches. Experimental results demonstrate that the proposed framework is effective, flexible and outperforms the state-of-the-art large scale similarity search methods.
Visual Tracking via Boolean Map Representations
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we present a simple yet effective Boolean map based representation that exploits connectivity cues for visual tracking. We describe a target object with histogram of oriented gradients and raw color features, of which each one is characterized by a set of Boolean maps generated by uniformly thresholding their values. The Boolean maps effectively encode multi-scale connectivity cues of the target with different granularities. The fine-grained Boolean maps capture spatially structural details that are effective for precise target localization while the coarse-grained ones encode global shape information that are robust to large target appearance variations. Finally, all the Boolean maps form together a robust representation that can be approximated by an explicit feature map of the intersection kernel, which is fed into a logistic regression classifier with online update, and the target location is estimated within a particle filter framework. The proposed representation scheme is computationally efficient and facilitates achieving favorable performance in terms of accuracy and robustness against the state-of-the-art tracking methods on a large benchmark dataset of 50 image sequences.
Stop Clickbait: Detecting and Preventing Clickbaits in Online News Media
Venue: arXiv cs.SI 2016
Year: 2016

Most of the online news media outlets rely heavily on the revenues generated from the clicks made by their readers, and due to the presence of numerous such outlets, they need to compete with each other for reader attention. To attract the readers to click on an article and subsequently visit the media site, the outlets often come up with catchy headlines accompanying the article links, which lure the readers to click on the link. Such headlines are known as Clickbaits. While these baits may trick the readers into clicking, in the long run, clickbaits usually don't live up to the expectation of the readers, and leave them disappointed. In this work, we attempt to automatically detect clickbaits and then build a browser extension which warns the readers of different media sites about the possibility of being baited by such headlines. The extension also offers each reader an option to block clickbaits she doesn't want to see. Then, using such reader choices, the extension automatically blocks similar clickbaits during her future visits. We run extensive offline and online experiments across multiple media sites and find that the proposed clickbait detection and the personalized blocking approaches perform very well achieving 93% accuracy in detecting and 89% accuracy in blocking clickbaits.
Joint Large-Scale Motion Estimation and Image Reconstruction
Venue: arXiv cs.CV 2016
Year: 2016

This article describes the implementation of the joint motion estimation and image reconstruction framework presented by Burger, Dirks and Schönlieb and extends this framework to large-scale motion between consecutive image frames. The variational framework uses displacements between consecutive frames based on the optical flow approach to improve the image reconstruction quality on the one hand and the motion estimation quality on the other. The energy functional consists of a data-fidelity term with a general operator that connects the input sequence to the solution, it has a total variation term for the image sequence and is connected to the underlying flow using an optical flow term. Additional spatial regularity for the flow is modeled by a total variation regularizer for both components of the flow. The numerical minimization is performed in an alternating manner using primal-dual techniques. The resulting schemes are presented as pseudo-code together with a short numerical evaluation.