OpenRaiser/Intern-Atlas huggingface dataset:
Localization bounds for the graph translation
Venue: arXiv cs.DM 2016
Year: 2016

The graph translation operator has been defined with good spectral properties in mind, and in particular with the end goal of being an isometric operator. Unfortunately, the resulting definitions do not provide good intuitions on a vertex-domain interpretation. In this paper, we show that this operator does have a vertex-domain interpretation as a diffusion operator using a polynomial approximation. We show that its impulse response exhibit an exponential decay of the energy way from the impulse, demonstrating localization preservation. Additionally, we formalize several techniques that can be used to study other graph signal operators.
Binary Cyclic Codes that are Locally Repairable
Venue: arXiv cs.IT 2016
Year: 2016

Codes for storage systems aim to minimize the repair locality, which is the number of disks (or nodes) that participate in the repair of a single failed disk. Simultaneously, the code must sustain a high rate, operate on a small finite field to be practically significant and be tolerant to a large number of erasures. To this end, we construct new families of binary linear codes that have an optimal dimension (rate) for a given minimum distance and locality. Specifically, we construct cyclic codes that are locally repairable for locality 2 and distances 2, 6 and 10. In doing so, we discover new upper bounds on the code dimension, and prove the optimality of enabling local repair by provisioning disjoint groups of disks. Finally, we extend our construction to build codes that have multiple repair sets for each disk.
Unsupervised Neural Hidden Markov Models
Venue: arXiv cs.CL 2016
Year: 2016

In this work, we present the first results for neuralizing an Unsupervised Hidden Markov Model. We evaluate our approach on tag in- duction. Our approach outperforms existing generative models and is competitive with the state-of-the-art though with a simpler model easily extended to include additional context.
A Simple, Fast and Highly-Accurate Algorithm to Recover 3D Shape from 2D Landmarks on a Single Image
Venue: arXiv cs.CV 2016
Year: 2016

Three-dimensional shape reconstruction of 2D landmark points on a single image is a hallmark of human vision, but is a task that has been proven difficult for computer vision algorithms. We define a feed-forward deep neural network algorithm that can reconstruct 3D shapes from 2D landmark points almost perfectly (i.e., with extremely small reconstruction errors), even when these 2D landmarks are from a single image. Our experimental results show an improvement of up to two-fold over state-of-the-art computer vision algorithms; 3D shape reconstruction of human faces is given at a reconstruction error < .004, cars at .0022, human bodies at .022, and highly-deformable flags at an error of .0004. Our algorithm was also a top performer at the 2016 3D Face Alignment in the Wild Challenge competition (done in conjunction with the European Conference on Computer Vision, ECCV) that required the reconstruction of 3D face shape from a single image. The derived algorithm can be trained in a couple hours and testing runs at more than 1, 000 frames/s on an i7 desktop. We also present an innovative data augmentation approach that allows us to train the system efficiently with small number of samples. And the system is robust to noise (e.g., imprecise landmark points) and missing data (e.g., occluded or undetected landmark points).
Graph partitioning and a componentwise PageRank algorithm
Venue: arXiv cs.DS 2016
Year: 2016

In this article we will present a graph partitioning algorithm which partitions a graph into two different types of components: the well-known `strongly connected components' as well as another type of components we call `connected acyclic component'. We will give an algorithm based on Tarjan's algorithm for finding strongly connected components used to find such a partitioning. We will also show that the partitioning given by the algorithm is unique and that the underlying graph can be represented as a directed acyclic graph (similar to a pure strongly connected component partitioning). In the second part we will show how such an partitioning of a graph can be used to calculate PageRank of a graph effectively by calculating PageRank for different components on the same `level' in parallel as well as allowing for the use of different types of PageRank algorithms for different types of components. To evaluate the method we have calculated PageRank on four large example graphs and compared it with a basic approach, as well as our algorithm in a serial as well as parallel implementation.
Fusing Similarity Models with Markov Chains for Sparse Sequential Recommendation
Venue: arXiv cs.IR 2016
Year: 2016

Predicting personalized sequential behavior is a key task for recommender systems. In order to predict user actions such as the next product to purchase, movie to watch, or place to visit, it is essential to take into account both long-term user preferences and sequential patterns (i.e., short-term dynamics). Matrix Factorization and Markov Chain methods have emerged as two separate but powerful paradigms for modeling the two respectively. Combining these ideas has led to unified methods that accommodate long- and short-term dynamics simultaneously by modeling pairwise user-item and item-item interactions. In spite of the success of such methods for tackling dense data, they are challenged by sparsity issues, which are prevalent in real-world datasets. In recent years, similarity-based methods have been proposed for (sequentially-unaware) item recommendation with promising results on sparse datasets. In this paper, we propose to fuse such methods with Markov Chains to make personalized sequential recommendations. We evaluate our method, Fossil, on a variety of large, real-world datasets. We show quantitatively that Fossil outperforms alternative algorithms, especially on sparse datasets, and qualitatively that it captures personalized dynamics and is able to make meaningful recommendations.
Your Computer is Leaking
Venue: arXiv cs.CR 2016
Year: 2016

This presentation focuses on differences between quantum computing and quantum cryptography. Both are discussed related to classical computer systems in terms of vulnerability. Research concerning quantum cryptography is analyzed in terms of work done by the University of Cambridge in partnership with a division of Toshiba, and also attacks demonstrated by Swedish researchers against QKD of energy-time entangled systems. Quantum computing is covered in terms of classical cryptography related to weaknesses presented by Shor's algorithm. Previous classical vulnerabilities also discussed were conducted by Israeli researchers as a side-channel attack using parabolic curve microphones, which has since been patched.
A Dynamic Web Service Registry Framework for Mobile Environments
Venue: arXiv cs.DC 2016
Year: 2016

Advancements in technology have transformed mobile devices from being mere communication widgets to versatile computing devices. Proliferation of these hand held devices has made them a common means to access and process digital information. Most web based applications are today available in a form that can conveniently be accessed over mobile devices. However, webservices (applications meant for consumption by other applications rather than humans) are not as commonly provided and consumed over mobile devices. Facilitating this and in effect realizing a service-oriented system over mobile devices has the potential to further enhance the potential of mobile devices. One of the major challenges in this integration is the lack of an efficient service registry system that caters to issues associated with the dynamic and volatile mobile environments. Existing service registry technologies designed for traditional systems fall short of accommodating such issues. In this paper, we propose a novel approach to manage service registry systems provided 'solely' over mobile devices, and thus realising an SOA without the need for high-end computing systems. The approach manages a dynamic service registry system in the form of light weight and distributed registries. We assess the feasibility of our approach by engineering and deploying a working prototype of the proposed registry system over actual mobile devices. A comparative study of the proposed approach and the traditional UDDI (Universal Description, Discovery, and Integration) registry is also included. The evaluation of our framework has shown propitious results in terms of battery cost, scalability, hindrance with native applications.
Kernel Methods on Approximate Infinite-Dimensional Covariance Operators for Image Classification
Venue: arXiv cs.CV 2016
Year: 2016

This paper presents a novel framework for visual object recognition using infinite-dimensional covariance operators of input features in the paradigm of kernel methods on infinite-dimensional Riemannian manifolds. Our formulation provides in particular a rich representation of image features by exploiting their non-linear correlations. Theoretically, we provide a finite-dimensional approximation of the Log-Hilbert-Schmidt (Log-HS) distance between covariance operators that is scalable to large datasets, while maintaining an effective discriminating capability. This allows us to efficiently approximate any continuous shift-invariant kernel defined using the Log-HS distance. At the same time, we prove that the Log-HS inner product between covariance operators is only approximable by its finite-dimensional counterpart in a very limited scenario. Consequently, kernels defined using the Log-HS inner product, such as polynomial kernels, are not scalable in the same way as shift-invariant kernels. Computationally, we apply the approximate Log-HS distance formulation to covariance operators of both handcrafted and convolutional features, exploiting both the expressiveness of these features and the power of the covariance representation. Empirically, we tested our framework on the task of image classification on twelve challenging datasets. In almost all cases, the results obtained outperform other state of the art methods, demonstrating the competitiveness and potential of our framework.
Experience with Heuristics, Benchmarks & Standards for Cylindrical Algebraic Decomposition
Venue: arXiv cs.SC 2016
Year: 2016

In the paper which inspired the SC-Square project, [E. Abraham, Building Bridges between Symbolic Computation and Satisfiability Checking, Proc. ISSAC '15, pp. 1-6, ACM, 2015] the author identified the use of sophisticated heuristics as a technique that the Satisfiability Checking community excels in and from which it is likely the Symbolic Computation community could learn and prosper. To start this learning process we summarise our experience with heuristic development for the computer algebra algorithm Cylindrical Algebraic Decomposition. We also propose and discuss standards and benchmarks as another area where Symbolic Computation could prosper from Satisfiability Checking expertise, noting that these have been identified as initial actions for the new SC-Square community in the CSA project, as described in [E.~Abraham et al., SC$^2$: Satisfiability Checking meets Symbolic Computation (Project Paper)}, Intelligent Computer Mathematics (LNCS 9761), pp. 28--43, Springer, 2015].
Towards performance portability through locality-awareness for applications using one-sided communication primitives
Venue: arXiv cs.DC 2016
Year: 2016

MPI is the most widely used data transfer and communication model in High Performance Computing. The latest version of the standard, MPI-3, allows skilled programmers to exploit all hardware capabilities of the latest and future supercomputing systems. The revised asynchronous remote-memory-access model in combination with the shared-memory window extension, in particular, allow writing code that hides communication latencies and optimizes communication paths according to the locality of data origin and destination. The latter is particularly important for today's multi- and many-core systems. However, writing such efficient code is highly complex and error-prone. In this paper we evaluate a recent remote-memory-access model, namely DART-MPI. This model claims to hide the aforementioned complexities from the programmer, but deliver locality-aware remote-memory-access semantics which outperforms MPI-3 one-sided communication primitives on multi-core systems. Conceptually, the DART-MPI interface is simple; at the same time it takes care of the complexities of the underlying MPI-3 and system topology. This makes DART-MPI an interesting candidate for porting legacy applications. We evaluate these claims using a realistic scientific application, specifically a finite-difference stencil code which solves the heat diffusion equation, on a large-scale Cray XC40 installation.
Competitive Propagation: Models, Asymptotic Behavior and Multi-stage Games
Venue: arXiv cs.SI 2016
Year: 2016

In this paper we propose a class of propagation models for multiple competing products over a social network. We consider two propagation mechanisms: social conversion and self conversion, corresponding, respectively, to endogenous and exogenous factors. A novel concept, the product-conversion graph, is proposed to characterize the interplay among competing products. According to the chronological order of social and self conversions, we develop two Markov-chain models and, based on the independence approximation, we approximate them with two respective difference equations systems. Theoretical analysis on these two approximation models reveals the dependency of the systems' asymptotic behavior on the structures of both the product-conversion graph and the social network, as well as the initial condition. In addition to the theoretical work, accuracy of the independence approximation and the asymptotic behavior of the Markov-chain model are investigated via numerical analysis, for the case where social conversion occurs before self conversion. Finally, we propose a class of multi-player and multi-stage competitive propagation games and discuss the seeding-quality trade-off, as well as the allocation of seeding resources among the individuals. We investigate the unique Nash equilibrium at each stage and analyze the system's behavior when every player is adopting the policy at the Nash equilibrium.
On Weighted MSE Model for MIMO Transceiver Optimization
Venue: arXiv cs.IT 2016
Year: 2016

Mean-squared-error (MSE) is one of the most widely used performance metrics for the designs and analysis of multi-input-multiple-output (MIMO) communications. Weighted MSE minimization, a more general formulation of MSE minimization, plays an important role in MIMO transceiver optimization. While this topic has a long history and has been extensively studied, existing treatments on the methods in solving the weighted MSE optimization are more or less sporadic and non-systematic. In this paper, we firstly review the two major methodologies, Lagrange multiplier method and majorization theory based method, and their common procedures in solving the weighted MSE minimization. Then some problems and limitations of the methods that were usually neglected or glossed over in existing literature are provided. These problems are fundamental and of critical importance for the corresponding MIMO transceiver optimizations. In addition, a new extended matrix-field weighted MSE model is proposed. Its solutions and applications are discussed in details. Compared with existing models, this new model has wider applications, e.g., nonlinear MIMO transceiver designs and capacity-maximization transceiver designs for general MIMO networks.
Digitizing Municipal Street Inspections Using Computer Vision
Venue: arXiv cs.CY 2016
Year: 2016

"People want an authority to tell them how to value things. But they chose this authority not based on facts or results. They chose it because it seems authoritative and familiar." - The Big Short The pavement condition index is one such a familiar measure used by many US cities to measure street quality and justify billions of dollars spent every year on street repair. These billion-dollar decisions are based on evaluation criteria that are subjective and not representative. In this paper, we build upon our initial submission to D4GX 2015 that approaches this problem of information asymmetry in municipal decision-making. We describe a process to identify street-defects using computer vision techniques on data collected using the Street Quality Identification Device (SQUID). A User Interface to host a large quantity of image data towards digitizing the street inspection process and enabling actionable intelligence for a core public service is also described. This approach of combining device, data and decision-making around street repair enables cities make targeted decisions about street repair and could lead to an anticipatory response which can result in significant cost savings. Lastly, we share lessons learnt from the deployment of SQUID in the city of Syracuse, NY.
Social Computing for Mobile Big Data in Wireless Networks
Venue: arXiv cs.SI 2016
Year: 2016

Mobile big data contains vast statistical features in various dimensions, including spatial, temporal, and the underlying social domain. Understanding and exploiting the features of mobile data from a social network perspective will be extremely beneficial to wireless networks, from planning, operation, and maintenance to optimization and marketing. In this paper, we categorize and analyze the big data collected from real wireless cellular networks. Then, we study the social characteristics of mobile big data and highlight several research directions for mobile big data in the social computing areas.
A CNN Cascade for Landmark Guided Semantic Part Segmentation
Venue: arXiv cs.CV 2016
Year: 2016

This paper proposes a CNN cascade for semantic part segmentation guided by pose-specific information encoded in terms of a set of landmarks (or keypoints). There is large amount of prior work on each of these tasks separately, yet, to the best of our knowledge, this is the first time in literature that the interplay between pose estimation and semantic part segmentation is investigated. To address this limitation of prior work, in this paper, we propose a CNN cascade of tasks that firstly performs landmark localisation and then uses this information as input for guiding semantic part segmentation. We applied our architecture to the problem of facial part segmentation and report large performance improvement over the standard unguided network on the most challenging face datasets. Testing code and models will be published online at http://cs.nott.ac.uk/~psxasj/.
Caffeinated FPGAs: FPGA Framework For Convolutional Neural Networks
Venue: arXiv cs.CV 2016
Year: 2016

Convolutional Neural Networks (CNNs) have gained significant traction in the field of machine learning, particularly due to their high accuracy in visual recognition. Recent works have pushed the performance of GPU implementations of CNNs to significantly improve their classification and training times. With these improvements, many frameworks have become available for implementing CNNs on both CPUs and GPUs, with no support for FPGA implementations. In this work we present a modified version of the popular CNN framework Caffe, with FPGA support. This allows for classification using CNN models and specialized FPGA implementations with the flexibility of reprogramming the device when necessary, seamless memory transactions between host and device, simple-to-use test benches, and the ability to create pipelined layer implementations. To validate the framework, we use the Xilinx SDAccel environment to implement an FPGA-based Winograd convolution engine and show that the FPGA layer can be used alongside other layers running on a host processor to run several popular CNNs (AlexNet, GoogleNet, VGG A, Overfeat). The results show that our framework achieves 50 GFLOPS across 3x3 convolutions in the benchmarks. This is achieved within a practical framework, which will aid in future development of FPGA-based CNNs.
Type checking through unification
Venue: arXiv cs.PL 2016
Year: 2016

In this paper we describe how to leverage higher-order unification to type check a dependently typed language with meta-variables. The literature usually presents the unification algorithm as a standalone component, however the need to check definitional equality of terms while type checking gives rise to a tight interplay between type checking and unification. This interplay is a major source of complexity in the type-checking algorithm for existing dependently typed programming languages. We propose an algorithm that encodes a type-checking problem entirely in the form of unification constraints, reducing the complexity of the type-checking code by taking advantage of higher order unification, which is already part of the implementation of many dependently typed languages.
Identification of Piecewise Affine State-Space Models via Expectation Maximization
Venue: arXiv cs.SY 2016
Year: 2016

This paper deals with the identification of piecewise affine state-space models. These models are obtained by partitioning the state or input domain into a finite number of regions and by considering affine submodels in each region. The proposed framework uses the Expectation Maximization (EM) algorithm to identify the parameters of the model. In most of the current literature, a discrete random variable with a discrete transition density is introduced to describe the transition between each submodel, leading to a further approximation of the dynamical system by a jump Markov model. On the contrary, we use the cumulative distribution function (CDF) to compute the probability of each submodel given the measurement at that time step. Then, given the submodel at each time step the latent state is estimated using the Kalman smoother. Subsequently, the parameters are estimated by maximizing a surrogate function for the likelihood. The performance of the proposed method is illustrated using the simulated model of the JAS 39 Gripen aircraft.
On the Worst-case Communication Overhead for Distributed Data Shuffling
Venue: arXiv cs.IT 2016
Year: 2016

Distributed learning platforms for processing large scale data-sets are becoming increasingly prevalent. In typical distributed implementations, a centralized master node breaks the data-set into smaller batches for parallel processing across distributed workers to achieve speed-up and efficiency. Several computational tasks are of sequential nature, and involve multiple passes over the data. At each iteration over the data, it is common practice to randomly re-shuffle the data at the master node, assigning different batches for each worker to process. This random re-shuffling operation comes at the cost of extra communication overhead, since at each shuffle, new data points need to be delivered to the distributed workers. In this paper, we focus on characterizing the information theoretically optimal communication overhead for the distributed data shuffling problem. We propose a novel coded data delivery scheme for the case of no excess storage, where every worker can only store the assigned data batches under processing. Our scheme exploits a new type of coding opportunity and is applicable to any arbitrary shuffle, and for any number of workers. We also present an information theoretic lower bound on the minimum communication overhead for data shuffling, and show that the proposed scheme matches this lower bound for the worst-case communication overhead.