OpenRaiser/Intern-Atlas huggingface dataset:
A Morphological Adaptation Approach to Path Planning Inspired by Slime Mould
Venue: arXiv cs.ET 2015
Year: 2015

Using a particle model of slime mould we demonstrate scoping experiments which explore how path planning may be performed by morphological adaptation. We initially demonstrate simple path planning by a shrinking blob of virtual plasmodium between two attractant sources within a polygonal arena. We examine the case where multiple paths are required and the subsequent selection of a single path from multiple options. Collision-free paths are implemented via repulsion from the borders of the arena. Finally, obstacle avoidance is implemented by repulsion from obstacles as they are uncovered by the shrinking blob. These examples show proof-of-concept results of path planning by morphological adaptation which complement existing research on path planning in novel computing substrates.
A New Coding Scheme for Discrete Memoryless MACs with Common Rate-Limited Feedback
Venue: arXiv cs.IT 2015
Year: 2015

We propose a new coding scheme for the discrete memoryless two-user multi-access channel (MAC) with rate-limited feedback. Our scheme combines ideas from the Venkataramanan-Pradhan scheme for perfect feedback with ideas from the Shaviv-Steinberg scheme for rate-limited feedback. Our achievable region includes the Shaviv-Steinberg achievable region and this inclusion can be strict. For general MACs and for sufficiently large feedback rates, our scheme outperforms the Shaviv-Steinberg scheme as it achieves the same rate region as the Venkataramanan-Pradhan scheme for perfect feedback (which cannot be achieved by the Shaviv-Steinberg scheme). Furthermore, we numerically evaluate our achievable region with a specific (Gaussian) choice of random variables for the memoryless two-user Gaussian MAC. Our simulation results show that for some parameters of the Gaussian MAC and the feedback rate, our scheme achieves a strictly larger sum-rate than the Shaviv-Steinberg scheme.
Using Calculation Fragments for Spreadsheet Testing and Debugging
Venue: arXiv cs.SE 2015
Year: 2015

A number of automated techniques and tools were proposed in the research literature over the years which aim to support the spreadsheet developer in the process of testing and debugging a faulty spreadsheet. One underlying assumption of many of these approaches is that the spreadsheet developer is capable of providing test cases or is at least reliably able to determine whether a calculated value in a certain cell is correct given the current set of inputs. Since real-world spreadsheets can be complex, we argue that these assumptions might be too strong in some situations. We therefore propose to support the user during testing and debugging by automatically computing spreadsheet fragments of manageable size. The spreadsheet developer can then verify the correctness of a smaller set of formulas for which the calculated output can be more easily validated.
"Roles for the boys?" Mining cast lists for gender and role distributions over time
Venue: arXiv cs.CY 2015
Year: 2015

Film and television play an important role in popular culture, however studies that require watching and annotating video are time-consuming and expensive to run at scale. We explore information mined from media database cast lists to explore onscreen gender depictions and how they change over time. We find differences between web-mediated onscreen gender proportions and those from US Census data. We propose these methodologies are a useful adjunct to traditional analysis that allow researchers to explore the relationship between online and onscreen gender depictions.
On the decomposition of stochastic cellular automata
Venue: arXiv cs.FL 2015
Year: 2015

In this paper we present two interesting properties of stochastic cellular automata that can be helpful in analyzing the dynamical behavior of such automata. The first property allows for calculating cell-wise probability distributions over the state set of a stochastic cellular automaton, i.e. images that show the average state of each cell during the evolution of the stochastic cellular automaton. The second property shows that stochastic cellular automata are equivalent to so-called stochastic mixtures of deterministic cellular automata. Based on this property, any stochastic cellular automaton can be decomposed into a set of deterministic cellular automata, each of which contributes to the behavior of the stochastic cellular automaton.
Station Keeping through Beacon-referenced Cyclic Pursuit
Venue: arXiv cs.SY 2015
Year: 2015

This paper investigates a modification of cyclic constant bearing (CB) pursuit in a multi-agent system in which each agent pays attention to a neighbor and a beacon. The problem admits shape equilibria with collective circling about the beacon, with the circling radius and angular separation of agents determined by choice of parameters in the feedback law. Stability of circling shape equilibria is shown for a 2-agent system, and the results are demonstrated on a collective of mobile robots tracked by a motion capture system.
Get 'em Moles! : Learning Spelling and Pronunciation through an Educational Game
Venue: arXiv cs.HC 2015
Year: 2015

Get 'em Moles! is a single-player educational game inspired by the classic arcade game Whac-A-Mole. Primarily designed for touchscreen devices, Get 'em Moles! aims to teach English spelling and pronunciation through engaging game play. This paper describes the game, design decisions in the form of elements that support learning, preliminary play-testing results, and future work.
Kempe Equivalence of Colourings of Cubic Graphs
Venue: arXiv cs.DM 2015
Year: 2015

Given a graph $G=(V,E)$ and a proper vertex colouring of $G$, a Kempe chain is a subset of $V$ that induces a maximal connected subgraph of $G$ in which every vertex has one of two colours. To make a Kempe change is to obtain one colouring from another by exchanging the colours of vertices in a Kempe chain. Two colourings are Kempe equivalent if each can be obtained from the other by a series of Kempe changes. A conjecture of Mohar asserts that, for $k \geq 3$, all $k$-colourings of $k$-regular graphs that are not complete are Kempe equivalent. We address the case $k=3$ by showing that all $3$-colourings of a cubic graph $G$ are Kempe equivalent unless $G$ is the complete graph $K_4$ or the triangular prism.
Diverse Landmark Sampling from Determinantal Point Processes for Scalable Manifold Learning
Venue: arXiv cs.LG 2015
Year: 2015

High computational costs of manifold learning prohibit its application for large point sets. A common strategy to overcome this problem is to perform dimensionality reduction on selected landmarks and to successively embed the entire dataset with the Nyström method. The two main challenges that arise are: (i) the landmarks selected in non-Euclidean geometries must result in a low reconstruction error, (ii) the graph constructed from sparsely sampled landmarks must approximate the manifold well. We propose the sampling of landmarks from determinantal distributions on non-Euclidean spaces. Since current determinantal sampling algorithms have the same complexity as those for manifold learning, we present an efficient approximation running in linear time. Further, we recover the local geometry after the sparsification by assigning each landmark a local covariance matrix, estimated from the original point set. The resulting neighborhood selection based on the Bhattacharyya distance improves the embedding of sparsely sampled manifolds. Our experiments show a significant performance improvement compared to state-of-the-art landmark selection techniques.
Training Binary Multilayer Neural Networks for Image Classification using Expectation Backpropagation
Venue: arXiv cs.NE 2015
Year: 2015

Compared to Multilayer Neural Networks with real weights, Binary Multilayer Neural Networks (BMNNs) can be implemented more efficiently on dedicated hardware. BMNNs have been demonstrated to be effective on binary classification tasks with Expectation BackPropagation (EBP) algorithm on high dimensional text datasets. In this paper, we investigate the capability of BMNNs using the EBP algorithm on multiclass image classification tasks. The performances of binary neural networks with multiple hidden layers and different numbers of hidden units are examined on MNIST. We also explore the effectiveness of image spatial filters and the dropout technique in BMNNs. Experimental results on MNIST dataset show that EBP can obtain 2.12% test error with binary weights and 1.66% test error with real weights, which is comparable to the results of standard BackPropagation algorithm on fully connected MNNs.
Adaptive Logging for Distributed In-memory Databases
Venue: arXiv cs.DB 2015
Year: 2015

A new type of logs, the command log, is being employed to replace the traditional data log (e.g., ARIES log) in the in-memory databases. Instead of recording how the tuples are updated, a command log only tracks the transactions being executed, thereby effectively reducing the size of the log and improving the performance. Command logging on the other hand increases the cost of recovery, because all the transactions in the log after the last checkpoint must be completely redone in case of a failure. In this paper, we first extend the command logging technique to a distributed environment, where all the nodes can perform recovery in parallel. We then propose an adaptive logging approach by combining data logging and command logging. The percentage of data logging versus command logging becomes an optimization between the performance of transaction processing and recovery to suit different OLTP applications. Our experimental study compares the performance of our proposed adaptive logging, ARIES-style data logging and command logging on top of H-Store. The results show that adaptive logging can achieve a 10x boost for recovery and a transaction throughput that is comparable to that of command logging.
2D Face Recognition System Based on Selected Gabor Filters and Linear Discriminant Analysis LDA
Venue: arXiv cs.CV 2015
Year: 2015

We present a new approach for face recognition system. The method is based on 2D face image features using subset of non-correlated and Orthogonal Gabor Filters instead of using the whole Gabor Filter Bank, then compressing the output feature vector using Linear Discriminant Analysis (LDA). The face image has been enhanced using multi stage image processing technique to normalize it and compensate for illumination variation. Experimental results show that the proposed system is effective for both dimension reduction and good recognition performance when compared to the complete Gabor filter bank. The system has been tested using CASIA, ORL and Cropped YaleB 2D face images Databases and achieved average recognition rate of 98.9 %.
Manipulation and abuse on social media
Venue: arXiv cs.SI 2015
Year: 2015

The computer science research community has became increasingly interested in the study of social media due to their pervasiveness in the everyday life of millions of individuals. Methodological questions and technical challenges abound as more and more data from social platforms become available for analysis. This data deluge not only yields the unprecedented opportunity to unravel questions about online individuals' behavior at scale, but also allows to explore the potential perils that the massive adoption of social media brings to our society. These communication channels provide plenty of incentives (both economical and social) and opportunities for abuse. As social media activity became increasingly intertwined with the events in the offline world, individuals and organizations have found ways to exploit these platforms to spread misinformation, to attack and smear others, or to deceive and manipulate. During crises, social media have been effectively used for emergency response, but fear-mongering actions have also triggered mass hysteria and panic. Criminal gangs and terrorist organizations like ISIS adopt social media for propaganda and recruitment. Synthetic activity and social bots have been used to coordinate orchestrated astroturf campaigns, to manipulate political elections and the stock market. The lack of effective content verification systems on many of these platforms, including Twitter and Facebook, rises concerns when younger users become exposed to cyber-bulling, harassment, or hate speech, inducing risks like depression and suicide. This article illustrates some of the recent advances facing these issues and discusses what it remains to be done, including the challenges to address in the future to make social media a more useful and accessible, safer and healthier environment for all users.
A Class of Random Sequences for Key Generation
Venue: arXiv cs.CR 2015
Year: 2015

This paper investigates randomness properties of sequences derived from Fibonacci and Gopala-Hemachandra sequences modulo m for use in key distribution applications. We show that for sequences modulo a prime a binary random sequence B(n) is obtained based on whether the period is p-1 (or a divisor) or 2p+2 (or a divisor). For the more general case of arbitrary m, we use the property if the period is a multiple of 8 or not. The sequences for prime modulo have much better autocorrelation properties. These are good candidates for key distribution since the generation process is not computationally complex.
Diagnosing Heterogeneous Dynamics for CT Scan Images of Human Brain in Wavelet and MFDFA domain
Venue: arXiv cs.CV 2015
Year: 2015

CT scan images of human brain of a particular patient in different cross sections are taken, on which wavelet transform and multi-fractal analysis are applied. The vertical and horizontal unfolding of images are done before analyzing these images. A systematic investigation of de-noised CT scan images of human brain in different cross-sections are carried out through wavelet normalized energy and wavelet semi-log plots, which clearly points out the mismatch between results of vertical and horizontal unfolding. The mismatch of results confirms the heterogeneity in spatial domain. Using the multi-fractal de-trended fluctuation analysis (MFDFA), the mismatch between the values of Hurst exponent and width of singularity spectrum by vertical and horizontal unfolding confirms the same.
Implementation of an efficient Fuzzy Logic based Information Retrieval System
Venue: arXiv cs.IR 2015
Year: 2015

This paper exemplifies the implementation of an efficient Information Retrieval (IR) System to compute the similarity between a dataset and a query using Fuzzy Logic. TREC dataset has been used for the same purpose. The dataset is parsed to generate keywords index which is used for the similarity comparison with the user query. Each query is assigned a score value based on its fuzzy similarity with the index keywords. The relevant documents are retrieved based on the score value. The performance and accuracy of the proposed fuzzy similarity model is compared with Cosine similarity model using Precision-Recall curves. The results prove the dominance of Fuzzy Similarity based IR system.
An implementation of Apertium based Assamese morphological analyzer
Venue: arXiv cs.CL 2015
Year: 2015

Morphological Analysis is an important branch of linguistics for any Natural Language Processing Technology. Morphology studies the word structure and formation of word of a language. In current scenario of NLP research, morphological analysis techniques have become more popular day by day. For processing any language, morphology of the word should be first analyzed. Assamese language contains very complex morphological structure. In our work we have used Apertium based Finite-State-Transducers for developing morphological analyzer for Assamese Language with some limited domain and we get 72.7% accuracy
Join Processing for Graph Patterns: An Old Dog with New Tricks
Venue: arXiv cs.DB 2015
Year: 2015

Join optimization has been dominated by Selinger-style, pairwise optimizers for decades. But, Selinger-style algorithms are asymptotically suboptimal for applications in graphic analytics. This suboptimality is one of the reasons that many have advocated supplementing relational engines with specialized graph processing engines. Recently, new join algorithms have been discovered that achieve optimal worst-case run times for any join or even so-called beyond worst-case (or instance optimal) run time guarantees for specialized classes of joins. These new algorithms match or improve on those used in specialized graph-processing systems. This paper asks can these new join algorithms allow relational engines to close the performance gap with graph engines? We examine this question for graph-pattern queries or join queries. We find that classical relational databases like Postgres and MonetDB or newer graph databases/stores like Virtuoso and Neo4j may be orders of magnitude slower than these new approaches compared to a fully featured RDBMS, LogicBlox, using these new ideas. Our results demonstrate that an RDBMS with such new algorithms can perform as well as specialized engines like GraphLab -- while retaining a high-level interface. We hope this adds to the ongoing debate of the role of graph accelerators, new graph systems, and relational systems in modern workloads.
Non-normal modalities in variants of Linear Logic
Venue: arXiv cs.LO 2015
Year: 2015

This article presents modal versions of resource-conscious logics. We concentrate on extensions of variants of Linear Logic with one minimal non-normal modality. In earlier work, where we investigated agency in multi-agent systems, we have shown that the results scale up to logics with multiple non-minimal modalities. Here, we start with the language of propositional intuitionistic Linear Logic without the additive disjunction, to which we add a modality. We provide an interpretation of this language on a class of Kripke resource models extended with a neighbourhood function: modal Kripke resource models. We propose a Hilbert-style axiomatization and a Gentzen-style sequent calculus. We show that the proof theories are sound and complete with respect to the class of modal Kripke resource models. We show that the sequent calculus admits cut elimination and that proof-search is in PSPACE. We then show how to extend the results when non-commutative connectives are added to the language. Finally, we put the logical framework to use by instantiating it as logics of agency. In particular, we propose a logic to reason about the resource-sensitive use of artefacts and illustrate it with a variety of examples.
Radar Precoder Design for Spectral Coexistence with Coordinated Multi-point (CoMP) System
Venue: arXiv cs.IT 2015
Year: 2015

This paper details the design of precoders for a MIMO radar spectrally coexistent with a MIMO cellular network. We focus on a coordinated multi-point (CoMP) system where a cluster of base stations (BSs) coordinate their transmissions to the intended user. The radar operates in two modes, interference-mitigation mode when it avoids interference with the CoMP system and cooperation mode when it exchanges information with it. Using either the conventional Switched Null Space Projection (SNSP) or the newly proposed Switched Small Singular Value Space Projection (SSSVSP), the radar beam sweeps across the BS clusters focusing on the optimal ones, optimal in either nullity or difference between the precoded and original radar signal. Taking the channel estimation error into account, the design of precoder is pivoted on the minimal radar interference at the BS clusters during interference-mitigation mode and minimal bit-error-rate at the BSs during cooperation mode while interfering minimally with the radar target detection capability. Our investigation shows that loss in radar performance can be compensated using SSSVSP instead of SNSP to some extent but increasing the number of radar antenna elements goes a long way to serve the purpose. Simulations verify our theoretical predictions about the proposed SSSVSP.
An Emphatic Approach to the Problem of Off-policy Temporal-Difference Learning
Venue: arXiv cs.LG 2015
Year: 2015

In this paper we introduce the idea of improving the performance of parametric temporal-difference (TD) learning algorithms by selectively emphasizing or de-emphasizing their updates on different time steps. In particular, we show that varying the emphasis of linear TD($λ$)'s updates in a particular way causes its expected update to become stable under off-policy training. The only prior model-free TD methods to achieve this with per-step computation linear in the number of function approximation parameters are the gradient-TD family of methods including TDC, GTD($λ$), and GQ($λ$). Compared to these methods, our _emphatic TD($λ$)_ is simpler and easier to use; it has only one learned parameter vector and one step-size parameter. Our treatment includes general state-dependent discounting and bootstrapping functions, and a way of specifying varying degrees of interest in accurately valuing different states.
Predicting Item Popularity: Analysing Local Clustering Behaviour of Users
Venue: arXiv cs.SI 2015
Year: 2015

Predicting the popularity of items in rating networks is an interesting but challenging problem. This is especially so when an item has first appeared and has received very few ratings. In this paper, we propose a novel approach to predicting the future popularity of new items in rating networks, defining a new bipartite clustering coefficient to predict the popularity of movies and stories in the MovieLens and Digg networks respectively. We show that the clustering behaviour of the first user who rates a new item gives insight into the future popularity of that item. Our method predicts, with a success rate of over 65% for the MovieLens network and over 50% for the Digg network, the future popularity of an item. This is a major improvement on current results.
The Simulation Powers and Limitations of Higher Temperature Hierarchical Self-Assembly Systems
Venue: arXiv cs.CG 2015
Year: 2015

In this paper, we extend existing results about simulation and intrinsic universality in a model of tile-based self-assembly. Namely, we work within the 2-Handed Assembly Model (2HAM), which is a model of self-assembly in which assemblies are formed by square tiles that are allowed to combine, using glues along their edges, individually or as pairs of arbitrarily large assemblies in a hierarchical manner, and we explore the abilities of these systems to simulate each other when the simulating systems have a higher "temperature" parameter, which is a system wide threshold dictating how many glue bonds must be formed between two assemblies to allow them to combine. It has previously been shown that systems with lower temperatures cannot simulate arbitrary systems with higher temperatures, and also that systems at some higher temperatures can simulate those at particular lower temperatures, creating an infinite set of infinite hierarchies of 2HAM systems with strictly increasing simulation power within each hierarchy. These previous results relied on two different definitions of simulation, one (strong simulation) seemingly more restrictive than the other (standard simulation), but which have previously not been proven to be distinct. Here we prove distinctions between them by first fully characterizing the set of pairs of temperatures such that the high temperature systems are intrinsically universal for the lower temperature systems (i.e. one tile set at the higher temperature can simulate any at the lower) using strong simulation. This includes the first impossibility result for simulation downward in temperature. We then show that lower temperature systems which cannot be simulated by higher temperature systems using the strong definition, can in fact be simulated using the standard definition, proving the distinction between the types of simulation.