OpenRaiser/Intern-Atlas huggingface dataset:
Assessing the Navigational Effects of Click Biases and Link Insertion on the Web
Venue: arXiv cs.SI 2016
Year: 2016

Websites have an inherent interest in steering user navigation in order to, for example, increase sales of specific products or categories, or to guide users towards specific information. In general, website administrators can use the following two strategies to influence their visitors' navigation behavior. First, they can introduce click biases to reinforce specific links on their website by changing their visual appearance, for example, by locating them on the top of the page. Second, they can utilize link insertion to generate new paths for users to navigate over. In this paper, we present a novel approach for measuring the potential effects of these two strategies on user navigation. Our results suggest that, depending on the pages for which we want to increase user visits, optimal link modification strategies vary. Moreover, simple topological measures can be used as proxies for assessing the impact of the intended changes on the navigation of users, even before these changes are implemented.
On the complexity of the identifiable subgraph problem, revisited
Venue: arXiv cs.DM 2016
Year: 2016

A bipartite graph $G=(L,R;E)$ with at least one edge is said to be identifiable if for every vertex $v\in L$, the subgraph induced by its non-neighbors has a matching of cardinality $|L|-1$. An $\ell$-subgraph of $G$ is an induced subgraph of $G$ obtained by deleting from it some vertices in $L$ together with all their neighbors. The Identifiable Subgraph problem is the problem of determining whether a given bipartite graph contains an identifiable $\ell$-subgraph. We show that the Identifiable Subgraph problem is polynomially solvable, along with the version of the problem in which the task is to delete as few vertices from $L$ as possible together with all their neighbors so that the resulting $\ell$-subgraph is identifiable. We also complement a known APX-hardness result for the complementary problem in which the task is to minimize the number of remaining vertices in $L$, by showing that two parameterized variants of the problem are W[1]-hard.
Cache Bypassing and Checkpointing to Circumvent Data Security Attacks on STTRAM
Venue: arXiv cs.CR 2016
Year: 2016

Spin-Transfer Torque RAM (STTRAM) is promising for cache applications. However, it brings new data security issues that were absent in volatile memory counterparts such as Static RAM (SRAM) and embedded Dynamic RAM (eDRAM). This is primarily due to the fundamental dependency of this memory technology on ambient parameters such as magnetic field and temperature that can be exploited to tamper with the stored data. In this paper we propose three techniques to enable error free computation without stalling the system, (a) stalling where the system is halted during attack; (b) cache bypass during gradually ramping attack where the last level cache (LLC) is bypassed and the upper level caches interact directly with the main memory; and, (c) checkpointing along with bypass during sudden attack where the processor states are saved periodically and the LLC is written back at regular intervals. During attack the system goes back to the last checkpoint and the computation continues with bypassed cache. We performed simulation for different duration and frequency of attack on SPLASH benchmark suite and the results show an average of 8% degradation in IPC for a one-time attack lasting for 50% of the execution time. The energy overhead is 2% for an attack lasting for the entire duration of execution.
Collaborative prediction with expert advice
Venue: arXiv cs.LG 2016
Year: 2016

Many practical learning systems aggregate data across many users, while learning theory traditionally considers a single learner who trusts all of their observations. A case in point is the foundational learning problem of prediction with expert advice. To date, there has been no theoretical study of the general collaborative version of prediction with expert advice, in which many users face a similar problem and would like to share their experiences in order to learn faster. A key issue in this collaborative framework is robustness: generally algorithms that aggregate data are vulnerable to manipulation by even a small number of dishonest users. We exhibit the first robust collaborative algorithm for prediction with expert advice. When all users are honest and have similar tastes our algorithm matches the performance of pooling data and using a traditional algorithm. But our algorithm also guarantees that adding users never significantly degrades performance, even if the additional users behave adversarially. We achieve strong guarantees even when the overwhelming majority of users behave adversarially. As a special case, our algorithm is extremely robust to variation amongst the users.
DoraPicker: An Autonomous Picking System for General Objects
Venue: arXiv cs.RO 2016
Year: 2016

Robots that autonomously manipulate objects within warehouses have the potential to shorten the package delivery time and improve the efficiency of the e-commerce industry. In this paper, we present a robotic system that is capable of both picking and placing general objects in warehouse scenarios. Given a target object, the robot autonomously detects it from a shelf or a table and estimates its full 6D pose. With this pose information, the robot picks the object using its gripper, and then places it into a container or at a specified location. We describe our pick-and-place system in detail while highlighting our design principles for the warehouse settings, including the perception method that leverages knowledge about its workspace, three grippers designed to handle a large variety of different objects in terms of shape, weight and material, and grasp planning in cluttered scenarios. We also present extensive experiments to evaluate the performance of our picking system and demonstrate that the robot is competent to accomplish various tasks in warehouse settings, such as picking a target item from a tight space, grasping different objects from the shelf, and performing pick-and-place tasks on the table.
Deep Self-Convolutional Activations Descriptor for Dense Cross-Modal Correspondence
Venue: arXiv cs.CV 2016
Year: 2016

We present a novel descriptor, called deep self-convolutional activations (DeSCA), designed for establishing dense correspondences between images taken under different imaging modalities, such as different spectral ranges or lighting conditions. Motivated by descriptors based on local self-similarity (LSS), we formulate a novel descriptor by leveraging LSS in a deep architecture, leading to better discriminative power and greater robustness to non-rigid image deformations than state-of-the-art cross-modality descriptors. The DeSCA first computes self-convolutions over a local support window for randomly sampled patches, and then builds self-convolution activations by performing an average pooling through a hierarchical formulation within a deep convolutional architecture. Finally, the feature responses on the self-convolution activations are encoded through a spatial pyramid pooling in a circular configuration. In contrast to existing convolutional neural networks (CNNs) based descriptors, the DeSCA is training-free (i.e., randomly sampled patches are utilized as the convolution kernels), is robust to cross-modal imaging, and can be densely computed in an efficient manner that significantly reduces computational redundancy. The state-of-the-art performance of DeSCA on challenging cases of cross-modal image pairs is demonstrated through extensive experiments.
Learning Dynamic Robot-to-Human Object Handover from Human Feedback
Venue: arXiv cs.RO 2016
Year: 2016

Object handover is a basic, but essential capability for robots interacting with humans in many applications, e.g., caring for the elderly and assisting workers in manufacturing workshops. It appears deceptively simple, as humans perform object handover almost flawlessly. The success of humans, however, belies the complexity of object handover as collaborative physical interaction between two agents with limited communication. This paper presents a learning algorithm for dynamic object handover, for example, when a robot hands over water bottles to marathon runners passing by the water station. We formulate the problem as contextual policy search, in which the robot learns object handover by interacting with the human. A key challenge here is to learn the latent reward of the handover task under noisy human feedback. Preliminary experiments show that the robot learns to hand over a water bottle naturally and that it adapts to the dynamics of human motion. One challenge for the future is to combine the model-free learning algorithm with a model-based planning approach and enable the robot to adapt over human preferences and object characteristics, such as shape, weight, and surface texture.
Parity Game Reductions
Venue: arXiv cs.LO 2016
Year: 2016

Parity games play a central role in model checking and satisfiability checking. Solving parity games is computationally expensive, among others due to the size of the games, which, for model checking problems, can easily contain $10^9$ vertices or beyond. Equivalence relations can be used to reduce the size of a parity game, thereby potentially alleviating part of the computational burden. We reconsider (governed) bisimulation and (governed) stuttering bisimulation, and we give detailed proofs that these relations are equivalences, have unique quotients and they approximate the winning regions of parity games. Furthermore, we present game-based characterisations of these relations. Using these characterisations our equivalences are compared to relations for parity games that can be found in the literature, such as direct simulation equivalence and delayed simulation equivalence. To complete the overview we develop coinductive characterisations of direct- and delayed simulation equivalence and we establish a lattice of equivalences for parity games.
Illumination-invariant image mosaic calculation based on logarithmic search
Venue: arXiv cs.CV 2016
Year: 2016

This technical report describes an improved image mosaicking algorithm. It is based on Jain's logarithmic search algorithm [Jain 1981] which is coupled to the method of Kourogi (1999} for matching images in a video sequence. Logarithmic search has a better invariance against illumination changes than the original optical-flow-based method of Kourogi.
Characterization of neighborhood behaviours in a multi-neighborhood local search algorithm
Venue: arXiv cs.AI 2016
Year: 2016

We consider a multi-neighborhood local search algorithm with a large number of possible neighborhoods. Each neighborhood is accompanied by a weight value which represents the probability of being chosen at each iteration. These weights are fixed before the algorithm runs, and are considered as parameters of the algorithm. Given a set of instances, off-line tuning of the algorithm's parameters can be done by automated algorithm configuration tools (e.g., SMAC). However, the large number of neighborhoods can make the tuning expensive and difficult even when the number of parameters has been reduced by some intuition. In this work, we propose a systematic method to characterize each neighborhood's behaviours, representing them as a feature vector, and using cluster analysis to form similar groups of neighborhoods. The novelty of our characterization method is the ability of reflecting changes of behaviours according to hardness of different solution quality regions. We show that using neighborhood clusters instead of individual neighborhoods helps to reduce the parameter configuration space without misleading the search of the tuning procedure. Moreover, this method is problem-independent and potentially can be applied in similar contexts.
Controlling Explanatory Heatmap Resolution and Semantics via Decomposition Depth
Venue: arXiv cs.CV 2016
Year: 2016

We present an application of the Layer-wise Relevance Propagation (LRP) algorithm to state of the art deep convolutional neural networks and Fisher Vector classifiers to compare the image perception and prediction strategies of both classifiers with the use of visualized heatmaps. Layer-wise Relevance Propagation (LRP) is a method to compute scores for individual components of an input image, denoting their contribution to the prediction of the classifier for one particular test point. We demonstrate the impact of different choices of decomposition cut-off points during the LRP-process, controlling the resolution and semantics of the heatmap on test images from the PASCAL VOC 2007 test data set.
Safety Verification of Output Feedback Controllers for Nonlinear Systems
Venue: arXiv cs.SY 2016
Year: 2016

A high-gain observer is used for a class of feedback linearisable nonlinear systems to synthesize safety-preserving controllers over the observer output. A bound on the distance between trajectories under state and output feedback is derived, and shown to converge to zero as a function of the gain parameter of an observer. We can therefore recover safety properties under output feedback and control saturation constraints by synthesizing a controller as if the full state were available. We specifically design feedback linearising controllers that satisfy certain properties, such as stability, and then construct the associated maximal safety-invariant set, namely the largest set of all initial states that are guaranteed to produce safe trajectories over a given (possibly infinite) time horizon.
Stitching Stabilizer: Two-frame-stitching Video Stabilization for Embedded Systems
Venue: arXiv cs.CV 2016
Year: 2016

In conventional electronic video stabilization, the stabilized frame is obtained by cropping the input frame to cancel camera shake. While a small cropping size results in strong stabilization, it does not provide us satisfactory results from the viewpoint of image quality, because it narrows the angle of view. By fusing several frames, we can effectively expand the area of input frames, and achieve strong stabilization even with a large cropping size. Several methods for doing so have been studied. However, their computational costs are too high for embedded systems such as smartphones. We propose a simple, yet surprisingly effective algorithm, called the stitching stabilizer. It stitches only two frames together with a minimal computational cost. It can achieve real-time processes in embedded systems, for Full HD and 30 FPS videos. To clearly show the effect, we apply it to hyperlapse. Using several clips, we show it produces more strongly stabilized and natural results than the existing solutions from Microsoft and Instagram.
On the Statistical Analysis of Practical SPARQL Queries
Venue: arXiv cs.DB 2016
Year: 2016

In this paper, we analyze some basic features of SPARQL queries coming from our practical world in a statistical way. These features include three statistic features such as the occurrence frequency of triple patterns, fragments, well-designed patterns and four semantic features such as monotonicity, non-monotonicity, weak monotonicity (old solutions are still served as parts of new solutions when some new triples are added) and satisfiability. All these features contribute to characterize SPARQL queries in different dimensions. We hope that this statistical analysis would provide some useful observation for researchers and engineers who are interested in what practical SPARQL queries look like, so that they could develop some practical heuristics for processing SPARQL queries and build SPARQL query processing engines and benchmarks. Besides, they can narrow the scope of their problems by avoiding those cases that do possibly not happen in our practical world.
Smart Grid Testbed for Demand Focused Energy Management in End User Environments
Venue: arXiv cs.SY 2016
Year: 2016

Successful deployment of smart grids necessitates experimental validities of their state-of-the-art designs in two-way communications, real-time demand response and monitoring of consumers' energy usage behavior. The objective is to observe consumers' energy usage pattern and exploit this information to assist the grid in designing incentives, energy management mechanisms, and real-time demand response protocols; so as help the grid achieving lower costs and improve energy supply stability. Further, by feeding the observed information back to the consumers instantaneously, it is also possible to promote energy efficient behavior among the users. To this end, this paper performs a literature survey on smart grid testbeds around the world, and presents the main accomplishments towards realizing a smart grid testbed at the Singapore University of Technology and Design (SUTD). The testbed is able to monitor, analyze and evaluate smart grid communication network design and control mechanisms, and test the suitability of various communications networks for both residential and commercial buildings. The testbeds are deployed within the SUTD student dormitories and the main university campus to monitor and record end-user energy consumption in real-time, which will enable us to design incentives, control algorithms and real-time demand response schemes. The testbed also provides an effective channel to evaluate the needs on communication networks to support various smart grid applications. In addition, our initial results demonstrate that our testbed can provide an effective platform to identify energy wastage, and prompt the needs of a secure communications channel as the energy usage pattern can provide privacy related information on individual user.
Signed Link Analysis in Social Media Networks
Venue: arXiv cs.SI 2016
Year: 2016

Numerous real-world relations can be represented by signed networks with positive links (e.g., trust) and negative links (e.g., distrust). Link analysis plays a crucial role in understanding the link formation and can advance various tasks in social network analysis such as link prediction. The majority of existing works on link analysis have focused on unsigned social networks. The existence of negative links determines that properties and principles of signed networks are substantially distinct from those of unsigned networks, thus we need dedicated efforts on link analysis in signed social networks. In this paper, following social theories in link analysis in unsigned networks, we adopt three social science theories, namely Emotional Information, Diffusion of Innovations and Individual Personality, to guide the task of link analysis in signed networks.
Short Literature Review for a General Player Model Based on Behavlets
Venue: arXiv cs.HC 2016
Year: 2016

We present the first in a series of three academic essays which deal with the question of how to build a generalized player model. We begin with a proposition: a general model of players requires parameters for the subjective experience of play, including at least: player psychology, game structure, and actions of play. Based on this proposition, we pose three linked research questions, which make incomplete progress toward a generalised player model: RQ1 what is a necessary and sufficient foundation to a general player model?; RQ2 can such a foundation improve performance of a computational intelligence-based player model?; and RQ3 can such a player model improve efficacy of adaptive artificial intelligence in games? We set out the arguments behind these research questions in each of the three essays, presented as three preprints. The first essay, in this preprint, reviews the literature for the core foundations for a general player model. We then propose a plan for future work to systematically extend the review and thus provide an empirical answer to RQ1 above. This work will directly support the proposed approach to address RQ2 and RQ3 above. This review was developed to support our 'Behavlets' approach to player modelling; therefore if citing this work, please use the relevant citation: Cowley B, Charles D. Behavlets: a Method for Practical Player Modelling using Psychology-Based Player Traits and Domain Specific Features. User Modelling and User-Adapted Interaction. 2016 Feb 8; online (Special Issue on Personality in Personalized Systems):1-50.
The Dimension and Minimum Distance of Two Classes of Primitive BCH Codes
Venue: arXiv cs.IT 2016
Year: 2016

Reed-Solomon codes, a type of BCH codes, are widely employed in communication systems, storage devices and consumer electronics. This fact demonstrates the importance of BCH codes -- a family of cyclic codes -- in practice. In theory, BCH codes are among the best cyclic codes in terms of their error-correcting capability. A subclass of BCH codes are the narrow-sense primitive BCH codes. However, the dimension and minimum distance of these codes are not known in general. The objective of this paper is to determine the dimension and minimum distances of two classes of narrow-sense primitive BCH codes with design distances $δ=(q-1)q^{m-1}-1-q^{\lfloor (m-1)/2\rfloor}$ and $δ=(q-1)q^{m-1}-1-q^{\lfloor (m+1)/2\rfloor}$. The weight distributions of some of these BCH codes are also reported. As will be seen, the two classes of BCH codes are sometimes optimal and sometimes among the best linear codes known.
Practical Encoder and Decoder for Power Constrained QC-LDPC lattices
Venue: arXiv cs.IT 2016
Year: 2016

LDPC lattices were the first family of lattices that equipped with iterative decoding algorithms under which they perform very well in high dimensions. In this paper, we introduce quasi cyclic low density parity check (QC-LDPC) lattices as a special case of LDPC lattices with one binary QC-LDPC code as their underlying code. These lattices are obtained from Construction A of lattices providing us to encode them efficiently using shift registers. To benefit from an encoder with linear complexity in dimension of the lattice, we obtain the generator matrix of these lattices in "quasi cyclic" form. We provide a low-complexity decoding algorithm of QC-LDPC lattices based on sum product algorithm. To design lattice codes, QC-LDPC lattices are combined with nested lattice shaping that uses the Voronoi region of a sublattice for code shaping. The shaping gain and shaping loss of our lattice codes with dimensions $40$, $50$ and $60$ using an optimal quantizer, are presented. Consequently, we establish a family of lattice codes that perform practically close to the sphere bound.
Big Data Spark Solution for Functional Magnetic Resonance Imaging
Venue: arXiv cs.DC 2016
Year: 2016

Recently, Big Data applications have rapidly expanded into different industries. Healthcare is also one the industries willing to use big data platforms so that some big data analytics tools have been adopted in this field to some extent. Medical imaging which is a pillar in diagnostic healthcare deals with high volume of data collection and processing. A huge amount of 3D and 4D images are acquired in different forms and resolutions using a variety of medical imaging modalities. Preprocessing and analyzing imaging data is currently a long process and cost and time consuming. However, not many big data platforms have been provided or redesigned for medical imaging purposes because of some restrictions such as data format. In this paper, we designed, developed and successfully tested a new pipeline for medical imaging data (especially functional magnetic resonance imaging - fMRI) using Big Data Spark / PySpark platform on a single node which allows us to read and load imaging data, convert them to Resilient Distributed Datasets in order manipulate and perform in-memory data processing in parallel and convert final results to imaging format while the pipeline provides an option to store the results in other formats such as data frame. Using this new solution and pipeline, we repeated our previous works in which we extracted brain networks from fMRI data using template matching and sum of squared differences (SSD) method. The final results revealed our Spark (PySpark) based solution improved the performance (in terms of processing time) around 4 times on a single compared to the previous work developed in Python.