OpenRaiser/Intern-Atlas huggingface dataset:
Technical Report: Design, Implementation and Deployment of Intermittency-aware Cellular Edge Services for Rural areas
Venue: arXiv cs.NI 2016
Year: 2016

Rural areas continue to be plagued by limited data connectivity due to poor and unreliable power infrastructure, poor backhaul connectivity and lack of economic incentives for telecom providers. These factors continue to be an impediment to providing reliable, highly available and bandwidth intensive mobile services and applications to function well in such contexts. This paper presents the design, implementation and deployment of GreenLinks, a new ground-up platform that enables intermittency-aware, reliable and available cellular services and application support in rural contexts under extreme operational environments with limited power and no existing cellular coverage. Unlike the conventional monolithic cellular network architecture, GreenLinks enables a distributed (and potentially disjoint) collection of open, programmable cellular base stations to offer a gamut of both conventional cellular services and new forms of distributed edge services. GreenLinks offers new application primitives to support different types of intermittency-aware distributed mobile edge services including P2P transactions, voice-based social media applications, and distributed mobile sensing applications. Using a participatory sensing white spaces approach, a GreenLinks base stati
Improving Raw Image Storage Efficiency by Exploiting Similarity
Venue: arXiv cs.DC 2016
Year: 2016

To improve the temporal and spatial storage efficiency, researchers have intensively studied various techniques, including compression and deduplication. Through our evaluation, we find that methods such as photo tags or local features help to identify the content-based similar- ity between raw images. The images can then be com- pressed more efficiently to get better storage space sav- ings. Furthermore, storing similar raw images together enables rapid data sorting, searching and retrieval if the images are stored in a distributed and large-scale envi- ronment by reducing fragmentation. In this paper, we evaluated the compressibility by designing experiments and observing the results. We found that on a statistical basis the higher similarity photos have, the better com- pression results are. This research helps provide a clue for future large-scale storage system design.
Intelligent Agent-Based Stimulation for Testing Robotic Software in Human-Robot Interactions
Venue: arXiv cs.RO 2016
Year: 2016

The challenges of robotic software testing extend beyond conventional software testing. Valid, realistic and interesting tests need to be generated for multiple programs and hardware running concurrently, deployed into dynamic environments with people. We investigate the use of Belief-Desire-Intention (BDI) agents as models for test generation, in the domain of human-robot interaction (HRI) in simulations. These models provide rational agency, causality, and a reasoning mechanism for planning, which emulate both intelligent and adaptive robots, as well as smart testing environments directed by humans. We introduce reinforcement learning (RL) to automate the exploration of the BDI models using a reward function based on coverage feedback. Our approach is evaluated using a collaborative manufacture example, where the robotic software under test is stimulated indirectly via a simulated human co-worker. We conclude that BDI agents provide intuitive models for test generation in the HRI domain. Our results demonstrate that RL can fully automate BDI model exploration, leading to very effective coverage-directed test generation.
Efficient Calculation of Bigram Frequencies in a Corpus of Short Texts
Venue: arXiv cs.CL 2016
Year: 2016

We show that an efficient and popular method for calculating bigram frequencies is unsuitable for bodies of short texts and offer a simple alternative. Our method has the same computational complexity as the old method and offers an exact count instead of an approximation.
Real-Time Contingency Analysis with Corrective Transmission Switching - Part I: Methodology
Venue: arXiv cs.OH 2016
Year: 2016

Transmission switching (TS) has gained significant attention recently. However, barriers still remain and must be overcome before the technology can be adopted by the industry. The state of the art challenges include AC feasibility and performance, computational complexity, the ability to handle large-scale real power systems, and dynamic stability. This two-part paper investigates these challenges by developing an AC TS-based real-time contingency analysis (RTCA) tool that can handle large-scale systems within a reasonable time. The tool proposes multiple corrective switching actions, after detection of a contingency with potential violations. To reduce the computational complexity, three heuristic algorithms are proposed to generate a small set of candidates for switching. Parallel computing is implemented to further speed up the solution time. Furthermore, stability analysis is performed to check for dynamic stability of proposed TS solutions. Part I of the paper presents a comprehensive literature review and the methodology. The promising results, tested on the Tennessee Valley Authority (TVA) system and actual energy management system (EMS) snapshots from Pennsylvania New Jersey Maryland (PJM) and the Electric Reliability Council of Texas (ERCOT), are presented in Part II. It is concluded that RTCA with corrective TS significantly reduces potential post-contingency violations and is ripe for industry adoption.
Wiretapped Oblivious Transfer
Venue: arXiv cs.CR 2016
Year: 2016

In this paper, we study the problem of obtaining $1$-of-$2$ string oblivious transfer (OT) between users Alice and Bob, in the presence of a passive eavesdropper Eve. The resource enabling OT in our setup is a noisy broadcast channel from Alice to Bob and Eve. Apart from the OT requirements between the users, Eve is not allowed to learn anything about the users' inputs. When Alice and Bob are honest-but-curious and the noisy broadcast channel is made up of two independent binary erasure channels (connecting Alice-Bob and Alice-Eve), we derive the $1$-of-$2$ string OT capacity for both $2$-privacy (when Eve can collude with either Alice or Bob) and $1$-privacy (when no such collusion is allowed). We generalize these capacity results to $1$-of-$N$ string OT and study other variants of this problem. When Alice and/or Bob are malicious, we present a different scheme based on interactive hashing. This scheme is shown to be optimal for certain parameter regimes. We present a new formulation of multiple, simultaneous OTs between Alice-Bob and Alice-Cathy. For this new setup, we present schemes and outer bounds that match in all but one regime of parameters. Finally, we consider the setup where the broadcast channel is made up of a cascade of two independent binary erasure channels (connecting Alice-Bob and Bob-Eve) and $1$-of-$2$ string OT is desired between Alice and Bob with $1$-privacy. For this setup, we derive an upper and lower bound on the $1$-of-$2$ string OT capacity which match in one of two possible parameter regimes.
Reinventing the Arcade: Computer Game Mediated Play Spaces for Physical Interaction
Venue: arXiv cs.HC 2016
Year: 2016

This paper suggests that recent developments in video game technology have occurred in parallel to play being moved from public into private spaces, which has had impact on the way people interact with games. The paper also argues and that there is potentially value in the creation of public play spaces to create opportunities to utilise both technology and body for the benefit of community culture and experiences through gaming. Co-located social gaming coupled with tangible interfaces offer alternative possibilities for the local video game scene. This paper includes a descriptive account of Rabble Room Arcade, an experimental social event combining custom-built tangible interface devices and multiplayer video games. The event was designed around games that promoted a return to simplicity through the use of unique tangible controllers to allow casual gamers to connect to the game and to each other, whilst also transforming the event into a spectacle.
Depth Image Inpainting: Improving Low Rank Matrix Completion with Low Gradient Regularization
Venue: arXiv cs.CV 2016
Year: 2016

We consider the case of inpainting single depth images. Without corresponding color images, previous or next frames, depth image inpainting is quite challenging. One natural solution is to regard the image as a matrix and adopt the low rank regularization just as inpainting color images. However, the low rank assumption does not make full use of the properties of depth images. A shallow observation may inspire us to penalize the non-zero gradients by sparse gradient regularization. However, statistics show that though most pixels have zero gradients, there is still a non-ignorable part of pixels whose gradients are equal to 1. Based on this specific property of depth images , we propose a low gradient regularization method in which we reduce the penalty for gradient 1 while penalizing the non-zero gradients to allow for gradual depth changes. The proposed low gradient regularization is integrated with the low rank regularization into the low rank low gradient approach for depth image inpainting. We compare our proposed low gradient regularization with sparse gradient regularization. The experimental results show the effectiveness of our proposed approach.
A Factorization Machine Framework for Testing Bigram Embeddings in Knowledgebase Completion
Venue: arXiv cs.CL 2016
Year: 2016

Embedding-based Knowledge Base Completion models have so far mostly combined distributed representations of individual entities or relations to compute truth scores of missing links. Facts can however also be represented using pairwise embeddings, i.e. embeddings for pairs of entities and relations. In this paper we explore such bigram embeddings with a flexible Factorization Machine model and several ablations from it. We investigate the relevance of various bigram types on the fb15k237 dataset and find relative improvements compared to a compositional model.
Optimal online escape path against a certificate
Venue: arXiv cs.CG 2016
Year: 2016

More than fifty years ago, Bellman asked for the best escape path within a known forest but for an unknown starting position. This deterministic finite path is the shortest path that leads out of a given environment from any starting point. There are some worst case positions where the full path length is required. Up to now such a fixed ultimate optimal escape path for a known shape for any starting position is only known for some special convex shapes (i.e., circles, strips of a given width, fat convex bodies, some isosceles triangles). Therefore, we introduce a different, simple and intuitive escape path, the so-called certificate path. This escape path depends on the starting position s and takes the distances from s to the outer boundary of the environment into account. Due to the additional information, the certificate path always (for any position s) leaves the environment earlier than the ultimate escape path, in the above convex examples. Next we assume that fewer information is available. Neither the precise shape of the envir- onment, nor the location of the starting point is known. For a class of environments (convex shapes and shapes with kernel positions), we design an online strategy that always leaves the environment. We show that the path length for leaving the environment is always shorter than 3.318764 the length of the corresponding certificate path. We also give a lower bound of 3.313126, which shows that for the above class of environments the factor 3.318764 is (almost) tight.
Bounding the optimal rate of the ICSI and ICCSI problem
Venue: arXiv cs.IT 2016
Year: 2016

In this work we study both the index coding with side information (ICSI) problem introduced by Birk and Kol in 1998 and the more general problem of index coding with coded side information (ICCSI), described by Shum et al in 2012. We estimate the optimal rate of an instance of the index coding problem. In the ICSI problem case, we characterize those digraphs having min-rank one less than their order and we give an upper bound on the min-rank of a hypergraph whose incidence matrix can be associated with that of a 2-design. Security aspects are discussed in the particular case when the design is a projective plane. For the coded side information case, we extend the graph theoretic upper bounds given by Shanmugam et al in 2014 on the optimal rate of index code.
Greedy Criterion in Orthogonal Greedy Learning
Venue: arXiv cs.LG 2016
Year: 2016

Orthogonal greedy learning (OGL) is a stepwise learning scheme that starts with selecting a new atom from a specified dictionary via the steepest gradient descent (SGD) and then builds the estimator through orthogonal projection. In this paper, we find that SGD is not the unique greedy criterion and introduce a new greedy criterion, called "$δ$-greedy threshold" for learning. Based on the new greedy criterion, we derive an adaptive termination rule for OGL. Our theoretical study shows that the new learning scheme can achieve the existing (almost) optimal learning rate of OGL. Plenty of numerical experiments are provided to support that the new scheme can achieve almost optimal generalization performance, while requiring less computation than OGL.
Q-Resolution with Generalized Axioms
Venue: arXiv cs.LO 2016
Year: 2016

Q-resolution is a proof system for quantified Boolean formulas (QBFs) in prenex conjunctive normal form (PCNF) which underlies search-based QBF solvers with clause and cube learning (QCDCL). With the aim to derive and learn stronger clauses and cubes earlier in the search, we generalize the axioms of the Q-resolution calculus resulting in an exponentially more powerful proof system. The generalized axioms introduce an interface of Q-resolution to any other QBF proof system allowing for the direct combination of orthogonal solving techniques. We implemented a variant of the Q-resolution calculus with generalized axioms in the QBF solver DepQBF. As two case studies, we apply integrated SAT solving and resource-bounded QBF preprocessing during the search to heuristically detect potential axiom applications. Experiments with application benchmarks indicate a substantial performance improvement.
Symmetry-aware Depth Estimation using Deep Neural Networks
Venue: arXiv cs.CV 2016
Year: 2016

Due to the abundance of 2D product images from the Internet, developing efficient and scalable algorithms to recover the missing depth information is central to many applications. Recent works have addressed the single-view depth estimation problem by utilizing convolutional neural networks. In this paper, we show that exploring symmetry information, which is ubiquitous in man made objects, can significantly boost the quality of such depth predictions. Specifically, we propose a new convolutional neural network architecture to first estimate dense symmetric correspondences in a product image and then propose an optimization which utilizes this information explicitly to significantly improve the quality of single-view depth estimations. We have evaluated our approach extensively, and experimental results show that this approach outperforms state-of-the-art depth estimation techniques.
Convex Hull Calculations: a Matlab Implementation and Correctness Proofs for the lrs-Algorithm
Venue: arXiv cs.MS 2016
Year: 2016

This paper provides full \Matlab-code and informal correctness proofs for the lexicographic reverse search algorithm for convex hull calculations. The implementation was tested on a 1993 486-PC for various small and some larger, partially highly degenerate combinatorial polytopes, one of which (a certain 13-dimensional 24 vertex polyhedron) occurs naturally in the study of a well known problem posed by Professor Graciano de Oliveira: see end of section 1.
Embedded all relevant feature selection with Random Ferns
Venue: arXiv cs.LG 2016
Year: 2016

Many machine learning methods can produce variable importance scores expressing the usability of each feature in context of the produced model; those scores on their own are yet not sufficient to generate feature selection, especially when an all relevant selection is required. Although there are wrapper methods aiming to solve this problem, they introduce a substantial increase in the required computational effort. In this paper I investigate an idea of incorporating all relevant selection within the training process by producing importance for implicitly generated shadows, attributes irrelevant by design. I propose and evaluate such a method in context of random ferns classifier. Experiment results confirm the effectiveness of such approach, although show that fully stochastic nature of random ferns limits its applicability either to small dimensions or as a part of a broader feature selection procedure.
Outage Probability Analysis of Amplify-and-Forward Cooperative Diversity Relay Networks
Venue: arXiv cs.IT 2016
Year: 2016

The statistical analysis of the fading End to End channel gain of the amplify and forward relaying protocol, however, is well known as extremely complex, and research work to date have only studied the asymptotic behaviour of the outage probability of the network at either very low or very high Signal Noise Ratios. Most current works circumvent the analytical complexity by first ignoring the effect of Additive White Gaussian noise then by using the simple approximated upper bound for the Signal Noise Ratio. The new approximated upper bound proposed in this paper, is far better bound than the previous results for the entire Signal Noise Ratio, which allows us to derive exact analytical expressions to study the effect of Additive White Gaussian noise on the network performance.
Training Deep Nets with Sublinear Memory Cost
Venue: arXiv cs.LG 2016
Year: 2016

We propose a systematic approach to reduce the memory consumption of deep neural network training. Specifically, we design an algorithm that costs O(sqrt(n)) memory to train a n layer network, with only the computational cost of an extra forward pass per mini-batch. As many of the state-of-the-art models hit the upper bound of the GPU memory, our algorithm allows deeper and more complex models to be explored, and helps advance the innovations in deep learning research. We focus on reducing the memory cost to store the intermediate feature maps and gradients during training. Computation graph analysis is used for automatic in-place operation and memory sharing optimizations. We show that it is possible to trade computation for memory - giving a more memory efficient training algorithm with a little extra computation cost. In the extreme case, our analysis also shows that the memory consumption can be reduced to O(log n) with as little as O(n log n) extra cost for forward computation. Our experiments show that we can reduce the memory cost of a 1,000-layer deep residual network from 48G to 7G with only 30 percent additional running time cost on ImageNet problems. Similarly, significant memory cost reduction is observed in training complex recurrent neural networks on very long sequences.
Articulated Hand Pose Estimation Review
Venue: arXiv cs.CV 2016
Year: 2016

With the increase number of companies focusing on commercializing Augmented Reality (AR), Virtual Reality (VR) and wearable devices, the need for a hand based input mechanism is becoming essential in order to make the experience natural, seamless and immersive. Hand pose estimation has progressed drastically in recent years due to the introduction of commodity depth cameras. Hand pose estimation based on vision is still a challenging problem due to its complexity from self-occlusion (between fingers), close similarity between fingers, dexterity of the hands, speed of the pose and the high dimension of the hand kinematic parameters. Articulated hand pose estimation is still an open problem and under intensive research from both academia and industry. The 2 approaches used for hand pose estimation are: discriminative and generative. Generative approach is a model based that tries to fit a hand model to the observed data. Discriminative approach is appearance based, usually implemented with machine learning (ML) and require a large amount of training data. Recent hand pose estimation uses hybrid approach by combining both discriminative and generative methods into a single hand pipeline. In this paper, we focus on reviewing recent progress of hand pose estimation from depth sensor. We will survey discriminative methods, generative methods and hybrid methods. This paper is not a comprehensive review of all hand pose estimation techniques, it is a subset of some of the recent state-of-the-art techniques.
Interference Management in Massive MIMO HetNets: A Nested Array Approach
Venue: arXiv cs.NI 2016
Year: 2016

The nested array, which is implemented by nonuniform antenna placement, is an effective approach to achieve O(N^2) degrees of freedom (DoF) with an antenna array of N antennas. Such DoF refers to the number of directions of incoming signals that can be resolved. With the increased number of DoF, an important application of nested array is to nullify the interference signals from multiple directions. In this paper, we apply nested array in a massive MIMO heterogeneous network (HetNet) for interference management. With nested array based interference nulling, each base station (BS) can nullify a certain number of interference signals. A key design issue is to select the interference sources to be nullified at each BS. We formulate this problem as an integer programming problem. The objective is to maximize the sum rate of all users, subject to BS DoF constraints. We propose an approximation scheme to solve this problem and derive a performance upper bound. Simulation results show that the proposed scheme effectively improves the sum rate and achieves a near optimal performance.
Incremental Reconstruction of Urban Environments by Edge-Points Delaunay Triangulation
Venue: arXiv cs.CV 2016
Year: 2016

Urban reconstruction from a video captured by a surveying vehicle constitutes a core module of automated mapping. When computational power represents a limited resource and, a detailed map is not the primary goal, the reconstruction can be performed incrementally, from a monocular video, carving a 3D Delaunay triangulation of sparse points; this allows online incremental mapping for tasks such as traversability analysis or obstacle avoidance. To exploit the sharp edges of urban landscape, we propose to use a Delaunay triangulation of Edge-Points, which are the 3D points corresponding to image edges. These points constrain the edges of the 3D Delaunay triangulation to real-world edges. Besides the use of the Edge-Points, a second contribution of this paper is the Inverse Cone Heuristic that preemptively avoids the creation of artifacts in the reconstructed manifold surface. We force the reconstruction of a manifold surface since it makes it possible to apply computer graphics or photometric refinement algorithms to the output mesh. We evaluated our approach on four real sequences of the public available KITTI dataset by comparing the incremental reconstruction against Velodyne measurements.