OpenRaiser/Intern-Atlas huggingface dataset:
Combat Models for RTS Games
Venue: arXiv cs.AI 2016
Year: 2016

Game tree search algorithms, such as Monte Carlo Tree Search (MCTS), require access to a forward model (or "simulator") of the game at hand. However, in some games such forward model is not readily available. This paper presents three forward models for two-player attrition games, which we call "combat models", and show how they can be used to simulate combat in RTS games. We also show how these combat models can be learned from replay data. We use StarCraft as our application domain. We report experiments comparing our combat models predicting a combat output and their impact when used for tactical decisions during a real game.
CSA++: Fast Pattern Search for Large Alphabets
Venue: arXiv cs.DS 2016
Year: 2016

Indexed pattern search in text has been studied for many decades. For small alphabets, the FM-Index provides unmatched performance, in terms of both space required and search speed. For large alphabets -- for example, when the tokens are words -- the situation is more complex, and FM-Index representations are compact, but potentially slow. In this paper we apply recent innovations from the field of inverted indexing and document retrieval to compressed pattern search, including for alphabets into the millions. Commencing with the practical compressed suffix array structure developed by Sadakane, we show that the Elias-Fano code-based approach to document indexing can be adapted to provide new tradeoff options in indexed pattern search, and offers significantly faster pattern processing compared to previous implementations, as well as reduced space requirements. We report a detailed experimental evaluation that demonstrates the relative advantages of the new approach, using the standard Pizza&Chili methodology and files, as well as applied use-cases derived from large-scale data compression, and from natural language processing. For large alphabets, the new structure gives rise to space requirements that are close to those of the most highly-compressed FM-Index variants, in conjunction with unparalleled search throughput rates.
The Bees Algorithm for the Vehicle Routing Problem
Venue: arXiv cs.NE 2016
Year: 2016

In this thesis we present a new algorithm for the Vehicle Routing Problem called the Enhanced Bees Algorithm. It is adapted from a fairly recent algorithm, the Bees Algorithm, which was developed for continuous optimisation problems. We show that the results obtained by the Enhanced Bees Algorithm are competitive with the best meta-heuristics available for the Vehicle Routing Problem (within 0.5% of the optimal solution for common benchmark problems). We show that the algorithm has good runtime performance, producing results within 2% of the optimal solution within 60 seconds, making it suitable for use within real world dispatch scenarios.
Applying Seamful Design in Location-based Mobile Museum Applications
Venue: arXiv cs.HC 2016
Year: 2016

The application of mobile computing is currently altering patterns of our behavior to a greater degree than perhaps any other invention. In combination with the introduction of power efficient wireless communication technologies, such as Bluetooth Low Energy (BLE), designers are today increasingly empowered to shape the way we interact with our physical surroundings and thus build entirely new experiences. However, our evaluations of BLE and its abilities to facilitate mobile location-based experiences in public environments revealed a number of potential problems. Most notably, the position and orientation of the user in combination with various environmental factors, such as crowds of people traversing the space, were found to cause major fluctuations of the received BLE signal strength. These issues are rendering a seamless functioning of any location-based application practically impossible. Instead of achieving seamlessness by eliminating these technical issues, we thus choose to advocate the use of a seamful approach, i.e. to reveal and exploit these problems and turn them into a part of the actual experience. In order to demonstrate the viability of this approach, we designed, implemented and evaluated the Ghost Detector - an educational location-based museum game for children. By presenting a qualitative evaluation of this game and by motivating our design decisions, this paper provides insight into some of the challenges and possible solutions connected to the process of developing location-based BLE-enabled experiences for public cultural spaces.
A General Characterization of Sync Word for Asynchronous Communication
Venue: arXiv cs.IT 2016
Year: 2016

We study a problem of sequential frame synchronization for a frame transmitted uniformly in $A$ slots. For a discrete memoryless channel (DMC), Venkat Chandar et al showed that the frame length $N$ must scale with $A$ as $e^{N α(Q)} > A$ for the frame synchronization error to go to zero (asymptotically with $A$). Here, $Q$ denotes the transition probabilities of the DMC and $α(Q)$, defined as the synchronization threshold, characterizes the scaling needed of $N$ for asymptotic error free frame synchronization. We show that the asynchronous communication framework permits a natural tradeoff between the sync frame length $N$ and the channel (usually parameterised by the input). For an AWGN channel, we study this tradeoff between the sync frame length $N$ and the input symbol power $P$ and characterise the scaling needed of the sync frame energy $E = N P$ for optimal frame synchronisation.
Towards information based spatiotemporal patterns as a foundation for agent representation in dynamical systems
Venue: arXiv cs.AI 2016
Year: 2016

We present some arguments why existing methods for representing agents fall short in applications crucial to artificial life. Using a thought experiment involving a fictitious dynamical systems model of the biosphere we argue that the metabolism, motility, and the concept of counterfactual variation should be compatible with any agent representation in dynamical systems. We then propose an information-theoretic notion of \emph{integrated spatiotemporal patterns} which we believe can serve as the basic building block of an agent definition. We argue that these patterns are capable of solving the problems mentioned before. We also test this in some preliminary experiments.
RADON: Repairable Atomic Data Object in Networks
Venue: arXiv cs.DC 2016
Year: 2016

Erasure codes offer an efficient way to decrease storage and communication costs while implementing atomic memory service in asynchronous distributed storage systems. In this paper, we provide erasure-code-based algorithms having the additional ability to perform background repair of crashed nodes. A repair operation of a node in the crashed state is triggered externally, and is carried out by the concerned node via message exchanges with other active nodes in the system. Upon completion of repair, the node re-enters active state, and resumes participation in ongoing and future read, write, and repair operations. To guarantee liveness and atomicity simultaneously, existing works assume either the presence of nodes with stable storage, or presence of nodes that never crash during the execution. We demand neither of these; instead we consider a natural, yet practical network stability condition $N1$ that only restricts the number of nodes in the crashed/repair state during broadcast of any message. We present an erasure-code based algorithm $RADON_C$ that is always live, and guarantees atomicity as long as condition $N1$ holds. In situations when the number of concurrent writes is limited, $RADON_C$ has significantly improved storage and communication cost over a replication-based algorithm $RADON_R$, which also works under $N1$. We further show how a slightly stronger network stability condition $N2$ can be used to construct algorithms that never violate atomicity. The guarantee of atomicity comes at the expense of having an additional phase during the read and write operations.
Memristor model based on fuzzy window function
Venue: arXiv cs.ET 2016
Year: 2016

Memristor (memory-resistor) is the fourth passive circuit element. We introduce a memristor model based on a fuzzy logic window function. Fuzzy models are flexible, which enables the capture of the pinched hysteresis behavior of the memristor. The introduced fuzzy model avoids common problems associated with window-function based memristor models, such as the terminal state problem, and the symmetry issues. The model captures the memristor behavior with a simple rule-base which gives an insight of how memristors work. Because of the flexibility offered by the fuzzy system, shape and distribution of input and output membership functions can be tuned to capture the behavior of various real memristors.
A First Look at Ad-block Detection: A New Arms Race on the Web
Venue: arXiv cs.CR 2016
Year: 2016

The rise of ad-blockers is viewed as an economic threat by online publishers, especially those who primarily rely on ad- vertising to support their services. To address this threat, publishers have started retaliating by employing ad-block detectors, which scout for ad-blocker users and react to them by restricting their content access and pushing them to whitelist the website or disabling ad-blockers altogether. The clash between ad-blockers and ad-block detectors has resulted in a new arms race on the web. In this paper, we present the first systematic measurement and analysis of ad-block detection on the web. We have designed and implemented a machine learning based tech- nique to automatically detect ad-block detection, and use it to study the deployment of ad-block detectors on Alexa top- 100K websites. The approach is promising with precision of 94.8% and recall of 93.1%. We characterize the spectrum of different strategies used by websites for ad-block detection. We find that most of publishers use fairly simple passive ap- proaches for ad-block detection. However, we also note that a few websites use third-party services, e.g. PageFair, for ad-block detection and response. The third-party services use active deception and other sophisticated tactics to de- tect ad-blockers. We also find that the third-party services can successfully circumvent ad-blockers and display ads on publisher websites.
Wirelessly Powered Backscatter Communication Networks: Modeling, Coverage and Capacity
Venue: arXiv cs.IT 2016
Year: 2016

Future Internet-of-Things (IoT) will connect billions of small computing devices embedded in the environment and support their device-to-device (D2D) communication. Powering this massive number of embedded devices is a key challenge of designing IoT since batteries increase the devices' form factors and battery recharging/replacement is difficult. To tackle this challenge, we propose a novel network architecture that enables D2D communication between passive nodes by integrating wireless power transfer and backscatter communication, which is called a wirelessly powered backscatter communication (WP-BackCom) network. In the network, standalone power beacons (PBs) are deployed for wirelessly powering nodes by beaming unmodulated carrier signals to targeted nodes. Provisioned with a backscatter antenna, a node transmits data to an intended receiver by modulating and reflecting a fraction of a carrier signal. Such transmission by backscatter consumes orders-of-magnitude less power than a traditional radio. Thereby, the dense deployment of low-complexity PBs with high transmission power can power a large-scale IoT. In this paper, a WP-BackCom network is modeled as a random Poisson cluster process in the horizontal plane where PBs are Poisson distributed and active ad-hoc pairs of backscatter communication nodes with fixed separation distances form random clusters centered at PBs. The backscatter nodes can harvest energy from and backscatter carrier signals transmitted by PBs. Furthermore, the transmission power of each node depends on the distance from the associated PB. Applying stochastic geometry, the network coverage probability and transmission capacity are derived and optimized as functions of backscatter parameters, including backscatter duty cycle and reflection coefficient, as well as the PB density. The effects of the parameters on network performance are characterized.
Computing Small Certificates of Inconsistency of Quadratic Fewnomial Systems
Venue: arXiv cs.SC 2016
Year: 2016

B{é}zout 's theorem states that dense generic systems of n multivariate quadratic equations in n variables have 2 n solutions over algebraically closed fields. When only a small subset M of monomials appear in the equations (fewnomial systems), the number of solutions may decrease dramatically. We focus in this work on subsets of quadratic monomials M such that generic systems with support M do not admit any solution at all. For these systems, Hilbert's Nullstellensatz ensures the existence of algebraic certificates of inconsistency. However, up to our knowledge all known bounds on the sizes of such certificates -including those which take into account the Newton polytopes of the polynomials- are exponential in n. Our main results show that if the inequality 2|M| -- 2n $\le$ $\sqrt$ 1 + 8ν -- 1 holds for a quadratic fewnomial system -- where ν is the matching number of a graph associated with M, and |M| is the cardinality of M -- then there exists generically a certificate of inconsistency of linear size (measured as the number of coefficients in the ground field K). Moreover this certificate can be computed within a polynomial number of arithmetic operations. Next, we evaluate how often this inequality holds, and we give evidence that the probability that the inequality is satisfied depends strongly on the number of squares. More precisely, we show that if M is picked uniformly at random among the subsets of n + k + 1 quadratic monomials containing at least $Ω$(n 1/2+$ε$) squares, then the probability that the inequality holds tends to 1 as n grows. Interestingly, this phenomenon is related with the matching number of random graphs in the Erd{ö}s-Renyi model. Finally, we provide experimental results showing that certificates in inconsistency can be computed for systems with more than 10000 variables and equations.
Dynamic Bayesian Networks to simulate occupant behaviours in office buildings related to indoor air quality
Venue: arXiv cs.AI 2016
Year: 2016

This paper proposes a new general approach based on Bayesian networks to model the human behaviour. This approach represents human behaviour with probabilistic cause-effect relations based on knowledge, but also with conditional probabilities coming either from knowledge or deduced from observations. This approach has been applied to the co-simulation of the CO2 concentration in an office coupled with human behaviour.
Stereotyping and Bias in the Flickr30K Dataset
Venue: arXiv cs.CL 2016
Year: 2016

An untested assumption behind the crowdsourced descriptions of the images in the Flickr30K dataset (Young et al., 2014) is that they "focus only on the information that can be obtained from the image alone" (Hodosh et al., 2013, p. 859). This paper presents some evidence against this assumption, and provides a list of biases and unwarranted inferences that can be found in the Flickr30K dataset. Finally, it considers methods to find examples of these, and discusses how we should deal with stereotype-driven descriptions in future applications.
Evaluation System for a Bayesian Optimization Service
Venue: arXiv cs.LG 2016
Year: 2016

Bayesian optimization is an elegant solution to the hyperparameter optimization problem in machine learning. Building a reliable and robust Bayesian optimization service requires careful testing methodology and sound statistical analysis. In this talk we will outline our development of an evaluation framework to rigorously test and measure the impact of changes to the SigOpt optimization service. We present an overview of our evaluation system and discuss how this framework empowers our research engineers to confidently and quickly make changes to our core optimization engine
Variational hybridization and transformation for large inaccurate noisy-or networks
Venue: arXiv cs.LG 2016
Year: 2016

Variational inference provides approximations to the computationally intractable posterior distribution in Bayesian networks. A prominent medical application of noisy-or Bayesian network is to infer potential diseases given observed symptoms. Previous studies focus on approximating a handful of complicated pathological cases using variational transformation. Our goal is to use variational transformation as part of a novel hybridized inference for serving reliable and real time diagnosis at web scale. We propose a hybridized inference that allows variational parameters to be estimated without disease posteriors or priors, making the inference faster and much of its computation recyclable. In addition, we propose a transformation ranking algorithm that is very stable to large variances in network prior probabilities, a common issue that arises in medical applications of Bayesian networks. In experiments, we perform comparative study on a large real life medical network and scalability study on a much larger (36,000x) synthesized network.
Dimensionality Reduction on SPD Manifolds: The Emergence of Geometry-Aware Methods
Venue: arXiv cs.CV 2016
Year: 2016

Representing images and videos with Symmetric Positive Definite (SPD) matrices, and considering the Riemannian geometry of the resulting space, has been shown to yield high discriminative power in many visual recognition tasks. Unfortunately, computation on the Riemannian manifold of SPD matrices -especially of high-dimensional ones- comes at a high cost that limits the applicability of existing techniques. In this paper, we introduce algorithms able to handle high-dimensional SPD matrices by constructing a lower-dimensional SPD manifold. To this end, we propose to model the mapping from the high-dimensional SPD manifold to the low-dimensional one with an orthonormal projection. This lets us formulate dimensionality reduction as the problem of finding a projection that yields a low-dimensional manifold either with maximum discriminative power in the supervised scenario, or with maximum variance of the data in the unsupervised one. We show that learning can be expressed as an optimization problem on a Grassmann manifold and discuss fast solutions for special cases. Our evaluation on several classification tasks evidences that our approach leads to a significant accuracy gain over state-of-the-art methods.
Modularity in Complex Multilayer Networks with Multiple Aspects: A Static Perspective
Venue: arXiv cs.SI 2016
Year: 2016

Complex systems are usually illustrated by networks which captures the topology of the interactions between the entities. To better understand the roles played by the entities in the system one needs to uncover the underlying community structure of the system. In recent years, systems with interactions that have various types or can change over time between the entities have attracted an increasing research attention. However, algorithms aiming to solve the key problem - community detection - in multilayer networks are still limited. In this work, we first introduce the multilayer network model representation with multiple aspects, which is flexible to a variety of networks. Then based on this model, we naturally derive the multilayer modularity - a widely adopted objective function of community detection in networks - from a static perspective as an evaluation metric to evaluate the quality of the communities detected in multilayer networks. It enables us to better understand the essence of the modularity by pointing out the specific kind of communities that will lead to a high modularity score. We also propose a spectral method called mSpec for the optimization of the proposed modularity function based on the supra-adjacency representation of the multilayer networks. Experiments on the electroencephalograph network and the comparison results on several empirical multilayer networks demonstrate the feasibility and reliable performance of the proposed method.
Visualization of Publication Impact
Venue: arXiv cs.DL 2016
Year: 2016

Measuring scholarly impact has been a topic of much interest in recent years. While many use the citation count as a primary indicator of a publications impact, the quality and impact of those citations will vary. Additionally, it is often difficult to see where a paper sits among other papers in the same research area. Questions we wished to answer through this visualization were: is a publication cited less than publications in the field?; is a publication cited by high or low impact publications?; and can we visually compare the impact of publications across a result set? In this work we address the above questions through a new visualization of publication impact. Our technique has been applied to the visualization of citation information in INSPIREHEP (http://www.inspirehep.net), the largest high energy physics publication repository.
Information Rate Performance of Massive MU-MIMO Uplink with Constant Envelope Pilot-based Frequency Synchronization
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we consider a constant envelope (CE) pilot-based low-complexity technique for frequency synchronization in multi-user massive MIMO systems. Study of the complexity-performance trade-off shows that this CE-pilot-based technique provides better MSE performance when compared to existing low-complexity high-PAPR pilot-based CFO (carrier frequency offset) estimator. Numerical study of the information rate performance of the TR-MRC receiver in imperfect CSI scenario with this CE-pilot based CFO estimator shows that it is more energy-and-spectrally efficient than existing low-complexity CFO estimator in massive MIMO systems. It is also observed that with this CE-pilot based CFO estimation, an $\mathcal{O}(\sqrt{M})$ array gain is achievable.
On-the-Fly TCP Acceleration with Miniproxy
Venue: arXiv cs.NI 2016
Year: 2016

TCP proxies are basic building blocks for many advanced middleboxes. In this paper we present Miniproxy, a TCP proxy built on top of a specialized minimalistic cloud operating system. Miniproxy's connection handling performance is comparable to that of full-fledged GNU/Linux TCP proxy implementations, but its minimalistic footprint enables new use cases. Specifically, Miniproxy requires as little as 6 MB to run and boots in tens of milliseconds, enabling massive consolidation, on-the-fly instantiation and edge cloud computing scenarios. We demonstrate the benefits of Miniproxy by implementing and evaluating a TCP acceleration use case.
Soft Covering with High Probability
Venue: arXiv cs.IT 2016
Year: 2016

Wyner's soft-covering lemma is the central analysis step for achievability proofs of information theoretic security, resolvability, and channel synthesis. It can also be used for simple achievability proofs in lossy source coding. This work sharpens the claim of soft-covering by moving away from an expected value analysis. Instead, a random codebook is shown to achieve the soft-covering phenomenon with high probability. The probability of failure is super-exponentially small in the block-length, enabling many applications through the union bound. This work gives bounds for both the exponential decay rate of total variation and the second-order codebook rate for soft covering.