OpenRaiser/Intern-Atlas huggingface dataset:
A Unifying Formalism for Shortest Path Problems with Expensive Edge Evaluations via Lazy Best-First Search over Paths with Edge Selectors
Venue: arXiv cs.DS 2016
Year: 2016

While the shortest path problem has myriad applications, the computational efficiency of suitable algorithms depends intimately on the underlying problem domain. In this paper, we focus on domains where evaluating the edge weight function dominates algorithm running time. Inspired by approaches in robotic motion planning, we define and investigate the Lazy Shortest Path class of algorithms which is differentiated by the choice of an edge selector function. We show that several algorithms in the literature are equivalent to this lazy algorithm for appropriate choice of this selector. Further, we propose various novel selectors inspired by sampling and statistical mechanics, and find that these selectors outperform existing algorithms on a set of example problems.
High-dimensional Black-box Optimization via Divide and Approximate Conquer
Venue: arXiv cs.AI 2016
Year: 2016

Divide and Conquer (DC) is conceptually well suited to high-dimensional optimization by decomposing a problem into multiple small-scale sub-problems. However, appealing performance can be seldom observed when the sub-problems are interdependent. This paper suggests that the major difficulty of tackling interdependent sub-problems lies in the precise evaluation of a partial solution (to a sub-problem), which can be overwhelmingly costly and thus makes sub-problems non-trivial to conquer. Thus, we propose an approximation approach, named Divide and Approximate Conquer (DAC), which reduces the cost of partial solution evaluation from exponential time to polynomial time. Meanwhile, the convergence to the global optimum (of the original problem) is still guaranteed. The effectiveness of DAC is demonstrated empirically on two sets of non-separable high-dimensional problems.
Regularization to orthogonal-polynomials fitting with application to magnetization data
Venue: arXiv cs.NA 2016
Year: 2016

An obstacle encountered in applying orthogonal-polynomials fitting is how to select out the proper fitting expression. By adding a Laplace term to the error expression and introducing the concept of overfitting degree, a regularization and corresponding cross validation scheme is proposed for two-variable polynomials fitting. While the Fortran implementation of above scheme is applied to magnetization data, a satisfactory fitting precision is reached, and overfitting problem can be quantitatively assessed, which therefore offers the quite reliable base for future comprehensive investigations of magnetocaloric and phase-transition properties of magnetic functional materials.
Watch-n-Patch: Unsupervised Learning of Actions and Relations
Venue: arXiv cs.CV 2016
Year: 2016

There is a large variation in the activities that humans perform in their everyday lives. We consider modeling these composite human activities which comprises multiple basic level actions in a completely unsupervised setting. Our model learns high-level co-occurrence and temporal relations between the actions. We consider the video as a sequence of short-term action clips, which contains human-words and object-words. An activity is about a set of action-topics and object-topics indicating which actions are present and which objects are interacting with. We then propose a new probabilistic model relating the words and the topics. It allows us to model long-range action relations that commonly exist in the composite activities, which is challenging in previous works. We apply our model to the unsupervised action segmentation and clustering, and to a novel application that detects forgotten actions, which we call action patching. For evaluation, we contribute a new challenging RGB-D activity video dataset recorded by the new Kinect v2, which contains several human daily activities as compositions of multiple actions interacting with different objects. Moreover, we develop a robotic system that watches people and reminds people by applying our action patching algorithm. Our robotic setup can be easily deployed on any assistive robot.
Alloy meets TLA+: An exploratory study
Venue: arXiv cs.SE 2016
Year: 2016

Alloy and TLA+ are two formal specification languages that are increasingly popular due to their simplicity and flexibility, as well as the effectiveness of their companion model checkers, the Alloy Analyzer and TLC, respectively. Nonetheless, while TLA+ focuses on temporal properties, Alloy is better suited to handle structural properties, requiring ad hoc mechanisms to reason about temporal properties. Thus, both have limitations in the specification and analysis of systems rich in both static and dynamic properties. This paper explores the pros and cons of these two frameworks when handling this class of systems through the step-by-step modeling, specification and verification of an example.
Ultra Dense Small Cell Networks: Turning Density into Energy Efficiency
Venue: arXiv cs.NI 2016
Year: 2016

In this paper, a novel approach for joint power control and user scheduling is proposed for optimizing energy efficiency (EE), in terms of bits per unit energy, in ultra dense small cell networks (UDNs). Due to severe coupling in interference, this problem is formulated as a dynamic stochastic game (DSG) between small cell base stations (SBSs). This game enables to capture the dynamics of both the queues and channel states of the system. To solve this game, assuming a large homogeneous UDN deployment, the problem is cast as a mean-field game (MFG) in which the MFG equilibrium is analyzed with the aid of low-complexity tractable partial differential equations. Exploiting the stochastic nature of the problem, user scheduling is formulated as a stochastic optimization problem and solved using the drift plus penalty (DPP) approach in the framework of Lyapunov optimization. Remarkably, it is shown that by weaving notions from Lyapunov optimization and mean-field theory, the proposed solution yields an equilibrium control policy per SBS which maximizes the network utility while ensuring users' quality-of-service. Simulation results show that the proposed approach achieves up to 70.7% gains in EE and 99.5% reductions in the network's outage probabilities compared to a baseline model which focuses on improving EE while attempting to satisfy the users' instantaneous quality-of-service requirements.
Searching for Topological Symmetry in Data Haystack
Venue: arXiv cs.LG 2016
Year: 2016

Finding interesting symmetrical topological structures in high-dimensional systems is an important problem in statistical machine learning. Limited amount of available high-dimensional data and its sensitivity to noise pose computational challenges to find symmetry. Our paper presents a new method to find local symmetries in a low-dimensional 2-D grid structure which is embedded in high-dimensional structure. To compute the symmetry in a grid structure, we introduce three legal grid moves (i) Commutation (ii) Cyclic Permutation (iii) Stabilization on sets of local grid squares, grid blocks. The three grid moves are legal transformations as they preserve the statistical distribution of hamming distances in each grid block. We propose and coin the term of grid symmetry of data on the 2-D data grid as the invariance of statistical distributions of hamming distance are preserved after a sequence of grid moves. We have computed and analyzed the grid symmetry of data on multivariate Gaussian distributions and Gamma distributions with noise.
Faster and Cheaper: Parallelizing Large-Scale Matrix Factorization on GPUs
Venue: arXiv cs.DC 2016
Year: 2016

Matrix factorization (MF) is employed by many popular algorithms, e.g., collaborative filtering. The emerging GPU technology, with massively multicore and high intra-chip memory bandwidth but limited memory capacity, presents an opportunity for accelerating MF much further when appropriately exploiting the GPU architectural characteristics. This paper presents cuMF, a CUDA-based matrix factorization library that implements memory-optimized alternate least square (ALS) method to solve very large-scale MF. CuMF uses a variety set of techniques to maximize the performance on either single or multiple GPUs. These techniques include smart access of sparse data leveraging GPU memory hierarchy, using data parallelism in conjunction with model parallelism, minimizing the communication overhead between computing units, and utilizing a novel topology-aware parallel reduction scheme. With only a single machine with four Nvidia GPU cards, cuMF can be 6-10 times as fast, and 33-100 times as cost-efficient, compared with the state-of-art distributed CPU solutions. Moreover, this cuMF can solve the largest matrix factorization problem ever reported yet in current literature, while maintaining impressively good performance.
Mapping EU fishing activities using ship tracking data
Venue: arXiv cs.OH 2016
Year: 2016

Information and understanding of fishing activities at sea are fundamental components of marine knowledge and maritime situational awareness. Such information is important to fisheries science, public authorities and policy makers. In this paper we introduce a first map at European scale of EU fishing activities extracted using Automatic Identification System (AIS) ship tracking data. The resulting map is a density of points that identify fishing activities. A measure of the reliability of such information is also presented as a map of coverage reception capabilities.
Real-time 3D scene description using Spheres, Cones and Cylinders
Venue: arXiv cs.CV 2016
Year: 2016

The paper describes a novel real-time algorithm for finding 3D geometric primitives (cylinders, cones and spheres) from 3D range data. In its core, it performs a fast model fitting with a model update in constant time (O(1)) for each new data point added to the model. We use a three stage approach.The first step inspects 1.5D sub spaces, to find ellipses. The next stage uses these ellipses as input by examining their neighborhood structure to form sets of candidates for the 3D geometric primitives. Finally, candidate ellipses are fitted to the geometric primitives. The complexity for point processing is O(n); additional time of lower order is needed for working on significantly smaller amount of mid-level objects. This allows the approach to process 30 frames per second on Kinect depth data, which suggests this approach as a pre-processing step for 3D real-time higher level tasks in robotics, like tracking or feature based mapping.
Towards Building an RGBD-M Scanner
Venue: arXiv cs.CV 2016
Year: 2016

We present a portable device to capture both shape and reflectance of an indoor scene. Consisting of a Kinect, an IR camera and several IR LEDs, our device allows the user to acquire data in a similar way as he/she scans with a single Kinect. Scene geometry is reconstructed by KinectFusion. To estimate reflectance from incomplete and noisy observations, 3D vertices of the same material are identified by our material segmentation propagation algorithm. Then BRDF observations at these vertices are merged into a more complete and accurate BRDF for the material. Effectiveness of our device is demonstrated by quality results on real-world scenes.
Spoofing Detection Goes Noisy: An Analysis of Synthetic Speech Detection in the Presence of Additive Noise
Venue: arXiv cs.SD 2016
Year: 2016

Automatic speaker verification (ASV) technology is recently finding its way to end-user applications for secure access to personal data, smart services or physical facilities. Similar to other biometric technologies, speaker verification is vulnerable to spoofing attacks where an attacker masquerades as a particular target speaker via impersonation, replay, text-to-speech (TTS) or voice conversion (VC) techniques to gain illegitimate access to the system. We focus on TTS and VC that represent the most flexible, high-end spoofing attacks. Most of the prior studies on synthesized or converted speech detection report their findings using high-quality clean recordings. Meanwhile, the performance of spoofing detectors in the presence of additive noise, an important consideration in practical ASV implementations, remains largely unknown. To this end, we analyze the suitability of state-of-the-art synthetic speech detectors under additive noise with a special focus on front-end features. Our comparison includes eight acoustic feature sets, five related to spectral magnitude and three to spectral phase information. Our extensive experiments on ASVSpoof 2015 corpus reveal several important findings. Firstly, all the countermeasures break down even at relatively high signal-to-noise ratios (SNRs) and fail to generalize to noisy conditions. Secondly, speech enhancement is not found helpful. Thirdly, GMM back-end generally outperforms the more involved i-vector back-end. Fourthly, concerning the compared features, the Mel-frequency cepstral coefficients (MFCCs) and subband spectral centroid magnitude coefficients (SCMCs) perform the best on average though the winner method depends on SNR and noise type. Finally, a study with two score fusion strategies shows that combining different feature based systems improves recognition accuracy for known and unknown attacks in both clean and noisy conditions.
Performance Analysis and Optimization of a Hybrid Distributed Reverse Time Migration Application
Venue: arXiv cs.DC 2016
Year: 2016

Applications to process seismic data employ scalable parallel systems to produce timely results. To fully exploit emerging processor architectures, application will need to employ threaded parallelism within a node and message passing across nodes. Today, MPI+OpenMP is the preferred programming model for this task. However, tuning hybrid programs for clusters is difficult. Performance tools can help users identify bottlenecks and uncover opportunities for improvement. This poster describes our experiences of applying Rice University's HPCToolkit and hardware performance counters to gain insight into an MPI+OpenMP code that performs Reverse Time Migration (RTM) on a cluster of multicore processors. The tools provided us with insights into the effectiveness of the domain decomposition strategy, the use of threaded parallelism, and functional unit utilization in individual cores. By applying insights obtained from the tools, we were able to improve the performance of the RTM code by roughly 30 percent.
Binomial Difference Ideals
Venue: arXiv cs.SC 2016
Year: 2016

In this paper, binomial difference ideals are studied. Three canonical representations for Laurent binomial difference ideals are given in terms of the reduced Groebner basis of Z[x]-lattices, regular and coherent difference ascending chains, and partial characters over Z[x]-lattices, respectively. Criteria for a Laurent binomial difference ideal to be reflexive, prime, well-mixed, and perfect are given in terms of their support lattices. The reflexive, well-mixed, and perfect closures of a Laurent binomial difference ideal are shown to be binomial. Most of the properties of Laurent binomial difference ideals are extended to the case of difference binomial ideals. Finally, algorithms are given to check whether a given Laurent binomial difference ideal I is reflexive, prime, well-mixed, or perfect, and in the negative case, to compute the reflexive, well-mixed, and perfect closures of I. An algorithm is given to decompose a finitely generated perfect binomial difference ideal as the intersection of reflexive prime binomial difference ideals.
Learning Typographic Style
Venue: arXiv cs.CV 2016
Year: 2016

Typography is a ubiquitous art form that affects our understanding, perception, and trust in what we read. Thousands of different font-faces have been created with enormous variations in the characters. In this paper, we learn the style of a font by analyzing a small subset of only four letters. From these four letters, we learn two tasks. The first is a discrimination task: given the four letters and a new candidate letter, does the new letter belong to the same font? Second, given the four basis letters, can we generate all of the other letters with the same characteristics as those in the basis set? We use deep neural networks to address both tasks, quantitatively and qualitatively measure the results in a variety of novel manners, and present a thorough investigation of the weaknesses and strengths of the approach.
Modelling Developable Ribbons Using Ruling Bending Coordinates
Venue: arXiv cs.GR 2016
Year: 2016

This paper presents a new method for modelling the dynamic behaviour of developable ribbons, two dimensional strips with much smaller width than length. Instead of approximating such surface with a general triangle mesh, we characterize it by a set of creases and bending angles across them. This representation allows the developability to be satisfied everywhere while still leaves enough degree of freedom to represent salient global deformation. We show how the potential and kinetic energies can be properly discretized in this configuration space and time integrated in a fully implicit manner. The result is a dynamic simulator with several desirable features: We can model non-trivial deformation using much fewer elements than conventional FEM method. It is stable under extreme deformation, external force or large timestep size. And we can readily handle various user constraints in Euclidean space.
Geometry of Interest (GOI): Spatio-Temporal Destination Extraction and Partitioning in GPS Trajectory Data
Venue: arXiv cs.AI 2016
Year: 2016

Nowadays large amounts of GPS trajectory data is being continuously collected by GPS-enabled devices such as vehicles navigation systems and mobile phones. GPS trajectory data is useful for applications such as traffic management, location forecasting, and itinerary planning. Such applications often need to extract the time-stamped Sequence of Visited Locations (SVLs) of the mobile objects. The nearest neighbor query (NNQ) is the most applied method for labeling the visited locations based on the IDs of the POIs in the process of SVL generation. NNQ in some scenarios is not accurate enough. To improve the quality of the extracted SVLs, instead of using NNQ, we label the visited locations as the IDs of the POIs which geometrically intersect with the GPS observations. Intersection operator requires the accurate geometry of the points of interest which we refer to them as the Geometries of Interest (GOIs). In some application domains (e.g. movement trajectories of animals), adequate information about the POIs and their GOIs may not be available a priori, or they may not be publicly accessible and, therefore, they need to be derived from GPS trajectory data. In this paper we propose a novel method for estimating the POIs and their GOIs, which consists of three phases: (i) extracting the geometries of the stay regions; (ii) constructing the geometry of destination regions based on the extracted stay regions; and (iii) constructing the GOIs based on the geometries of the destination regions. Using the geometric similarity to known GOIs as the major evaluation criterion, the experiments we performed using long-term GPS trajectory data show that our method outperforms the existing approaches.
Iterative Methods for Efficient Sampling-Based Optimal Motion Planning of Nonlinear Systems
Venue: arXiv cs.RO 2016
Year: 2016

This paper extends the RRT* algorithm, a recently developed but widely-used sampling-based optimal motion planner, in order to effectively handle nonlinear kinodynamic constraints. Nonlinearity in kinodynamic differential constraints often leads to difficulties in choosing appropriate distance metric and in computing optimized trajectory segments in tree construction. To tackle these two difficulties, this work adopts the affine quadratic regulator-based pseudo metric as the distance measure and utilizes iterative two-point boundary value problem solvers for computing the optimized segments. The proposed extension then preserves the inherent asymptotic optimality of the RRT* framework, while efficiently handling a variety of kinodynamic constraints. Three numerical case studies validate the applicability of the proposed method.
Multi-modal Tracking for Object based SLAM
Venue: arXiv cs.CV 2016
Year: 2016

We present an on-line 3D visual object tracking framework for monocular cameras by incorporating spatial knowledge and uncertainty from semantic mapping along with high frequency measurements from visual odometry. Using a combination of vision and odometry that are tightly integrated we can increase the overall performance of object based tracking for semantic mapping. We present a framework for integration of the two data-sources into a coherent framework through information based fusion/arbitration. We demonstrate the framework in the context of OmniMapper[1] and present results on 6 challenging sequences over multiple objects compared to data obtained from a motion capture systems. We are able to achieve a mean error of 0.23m for per frame tracking showing 9% relative error less than state of the art tracker.
Event-triggered leader-following tracking control for multivariable multi-agent systems
Venue: arXiv cs.SY 2016
Year: 2016

The paper considers event-triggered leader-follower tracking control for multi-agent systems with general linear dynamics. For both undirected and directed follower graphs, we propose event triggering rules which guarantee bounded tracking errors. With these rules, we also prove that the systems do not exhibit Zeno behavior, and the bounds on the tracking errors can be tuned to a desired small value. We also show that the combinational state required for the proposed event triggering conditions can be continuously generated from discrete communications between the neighboring agents occurring at event times. The efficacy of the proposed methods is discussed using a simulation example.
RISAS: A Novel Rotation, Illumination, Scale Invariant Appearance and Shape Feature
Venue: arXiv cs.RO 2016
Year: 2016

This paper presents a novel appearance and shape feature, RISAS, which is robust to viewpoint, illumination, scale and rotation variations. RISAS consists of a keypoint detector and a feature descriptor both of which utilise texture and geometric information present in the appearance and shape channels. A novel response function based on the surface normals is used in combination with the Harris corner detector for selecting keypoints in the scene. A strategy that uses the depth information for scale estimation and background elimination is proposed to select the neighbourhood around the keypoints in order to build precise invariant descriptors. Proposed descriptor relies on the ordering of both grayscale intensity and shape information in the neighbourhood. Comprehensive experiments which confirm the effectiveness of the proposed RGB-D feature when compared with CSHOT and LOIND are presented. Furthermore, we highlight the utility of incorporating texture and shape information in the design of both the detector and the descriptor by demonstrating the enhanced performance of CSHOT and LOIND when combined with RISAS detector.