OpenRaiser/Intern-Atlas huggingface dataset:
Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths
Venue: arXiv cs.DS 2017
Year: 2017

Let $G$ be an $n$-node simple directed planar graph with nonnegative edge weights. We study the fundamental problems of computing (1) a global cut of $G$ with minimum weight and (2) a~cycle of $G$ with minimum weight. The best previously known algorithm for the former problem, running in $O(n\log^3 n)$ time, can be obtained from the algorithm of \Lacki, Nussbaum, Sankowski, and Wulff-Nilsen for single-source all-sinks maximum flows. The best previously known result for the latter problem is the $O(n\log^3 n)$-time algorithm of Wulff-Nilsen. By exploiting duality between the two problems in planar graphs, we solve both problems in $O(n\log n\log\log n)$ time via a divide-and-conquer algorithm that finds a shortest non-degenerate cycle. The kernel of our result is an $O(n\log\log n)$-time algorithm for computing noncrossing shortest paths among nodes well ordered on a common face of a directed plane graph, which is extended from the algorithm of Italiano, Nussbaum, Sankowski, and Wulff-Nilsen for an undirected plane graph.
Discriminatively Boosted Image Clustering with Fully Convolutional Auto-Encoders
Venue: arXiv cs.CV 2017
Year: 2017

Traditional image clustering methods take a two-step approach, feature learning and clustering, sequentially. However, recent research results demonstrated that combining the separated phases in a unified framework and training them jointly can achieve a better performance. In this paper, we first introduce fully convolutional auto-encoders for image feature learning and then propose a unified clustering framework to learn image representations and cluster centers jointly based on a fully convolutional auto-encoder and soft $k$-means scores. At initial stages of the learning procedure, the representations extracted from the auto-encoder may not be very discriminative for latter clustering. We address this issue by adopting a boosted discriminative distribution, where high score assignments are highlighted and low score ones are de-emphasized. With the gradually boosted discrimination, clustering assignment scores are discriminated and cluster purities are enlarged. Experiments on several vision benchmark datasets show that our methods can achieve a state-of-the-art performance.
Containment for Rule-Based Ontology-Mediated Queries
Venue: arXiv cs.DB 2017
Year: 2017

Many efforts have been dedicated to identifying restrictions on ontologies expressed as tuple-generating dependencies (tgds), a.k.a. existential rules, that lead to the decidability for the problem of answering ontology-mediated queries (OMQs). This has given rise to three families of formalisms: guarded, non-recursive, and sticky sets of tgds. In this work, we study the containment problem for OMQs expressed in such formalisms, which is a key ingredient for solving static analysis tasks associated with them. Our main contribution is the development of specially tailored techniques for OMQ containment under the classes of tgds stated above. This enables us to obtain sharp complexity bounds for the problems at hand, which in turn allow us to delimitate its practical applicability. We also apply our techniques to pinpoint the complexity of problems associated with two emerging applications of OMQ containment: distribution over components and UCQ rewritability of OMQs.
Sparse Inertial Poser: Automatic 3D Human Pose Estimation from Sparse IMUs
Venue: arXiv cs.CV 2017
Year: 2017

We address the problem of making human motion capture in the wild more practical by using a small set of inertial sensors attached to the body. Since the problem is heavily under-constrained, previous methods either use a large number of sensors, which is intrusive, or they require additional video input. We take a different approach and constrain the problem by: (i) making use of a realistic statistical body model that includes anthropometric constraints and (ii) using a joint optimization framework to fit the model to orientation and acceleration measurements over multiple frames. The resulting tracker Sparse Inertial Poser (SIP) enables 3D human pose estimation using only 6 sensors (attached to the wrists, lower legs, back and head) and works for arbitrary human motions. Experiments on the recently released TNT15 dataset show that, using the same number of sensors, SIP achieves higher accuracy than the dataset baseline without using any video data. We further demonstrate the effectiveness of SIP on newly recorded challenging motions in outdoor scenarios such as climbing or jumping over a wall.
Saliency-guided video classification via adaptively weighted learning
Venue: arXiv cs.CV 2017
Year: 2017

Video classification is productive in many practical applications, and the recent deep learning has greatly improved its accuracy. However, existing works often model video frames indiscriminately, but from the view of motion, video frames can be decomposed into salient and non-salient areas naturally. Salient and non-salient areas should be modeled with different networks, for the former present both appearance and motion information, and the latter present static background information. To address this problem, in this paper, video saliency is predicted by optical flow without supervision firstly. Then two streams of 3D CNN are trained individually for raw frames and optical flow on salient areas, and another 2D CNN is trained for raw frames on non-salient areas. For the reason that these three streams play different roles for each class, the weights of each stream are adaptively learned for each class. Experimental results show that saliency-guided modeling and adaptively weighted learning can reinforce each other, and we achieve the state-of-the-art results.
Multimodal Compact Bilinear Pooling for Multimodal Neural Machine Translation
Venue: arXiv cs.CL 2017
Year: 2017

In state-of-the-art Neural Machine Translation, an attention mechanism is used during decoding to enhance the translation. At every step, the decoder uses this mechanism to focus on different parts of the source sentence to gather the most useful information before outputting its target word. Recently, the effectiveness of the attention mechanism has also been explored for multimodal tasks, where it becomes possible to focus both on sentence parts and image regions. Approaches to pool two modalities usually include element-wise product, sum or concatenation. In this paper, we evaluate the more advanced Multimodal Compact Bilinear pooling method, which takes the outer product of two vectors to combine the attention features for the two modalities. This has been previously investigated for visual question answering. We try out this approach for multimodal image caption translation and show improvements compared to basic combination methods.
Rapid-Rate: A Framework for Semi-supervised Real-time Sentiment Trend Detection in Unstructured Big Data
Venue: arXiv cs.CL 2017
Year: 2017

Commercial establishments like restaurants, service centres and retailers have several sources of customer feedback about products and services, most of which need not be as structured as rated reviews provided by services like Yelp, or Amazon, in terms of sentiment conveyed. For instance, Amazon provides a fine-grained score on a numeric scale for product reviews. Some sources, however, like social media (Twitter, Facebook), mailing lists (Google Groups) and forums (Quora) contain text data that is much more voluminous, but unstructured and unlabelled. It might be in the best interests of a business establishment to assess the general sentiment towards their brand on these platforms as well. This text could be pipelined into a system with a built-in prediction model, with the objective of generating real-time graphs on opinion and sentiment trends. Although such tasks like the one described about have been explored with respect to document classification problems in the past, the implementation described in this paper, by virtue of learning a continuous function rather than a discrete one, offers a lot more depth of insight as compared to document classification approaches. This study aims to explore the validity of such a continuous function predicting model to quantify sentiment about an entity, without the additional overhead of manual labelling, and computational preprocessing & feature extraction. This research project also aims to design and implement a re-usable document regression pipeline as a framework, Rapid-Rate, that can be used to predict document scores in real-time.
Online Distributed Learning Over Networks in RKH Spaces Using Random Fourier Features
Venue: arXiv cs.LG 2017
Year: 2017

We present a novel diffusion scheme for online kernel-based learning over networks. So far, a major drawback of any online learning algorithm, operating in a reproducing kernel Hilbert space (RKHS), is the need for updating a growing number of parameters as time iterations evolve. Besides complexity, this leads to an increased need of communication resources, in a distributed setting. In contrast, the proposed method approximates the solution as a fixed-size vector (of larger dimension than the input space) using Random Fourier Features. This paves the way to use standard linear combine-then-adapt techniques. To the best of our knowledge, this is the first time that a complete protocol for distributed online learning in RKHS is presented. Conditions for asymptotic convergence and boundness of the networkwise regret are also provided. The simulated tests illustrate the performance of the proposed scheme.
Note Value Recognition for Piano Transcription Using Markov Random Fields
Venue: arXiv cs.AI 2017
Year: 2017

This paper presents a statistical method for use in music transcription that can estimate score times of note onsets and offsets from polyphonic MIDI performance signals. Because performed note durations can deviate largely from score-indicated values, previous methods had the problem of not being able to accurately estimate offset score times (or note values) and thus could only output incomplete musical scores. Based on observations that the pitch context and onset score times are influential on the configuration of note values, we construct a context-tree model that provides prior distributions of note values using these features and combine it with a performance model in the framework of Markov random fields. Evaluation results show that our method reduces the average error rate by around 40 percent compared to existing/simple methods. We also confirmed that, in our model, the score model plays a more important role than the performance model, and it automatically captures the voice structure by unsupervised learning.
Speeding up TestU01 with the use of HTCondor
Venue: arXiv cs.DC 2017
Year: 2017

Testing random number generators is a very important task that, in the resent past, has taken upwards of twelve hours when testing with the current agship testing suite TestU01. Through this paper we will discuss the possible performance increases to the existing random number generator testing suite TestU01 that are available by offering the executable to an HTCondor pool to execute on. We will see that with a few modifications we are able to decrease the running time of a sample run of Big Crush from about five and a half hours to only five and a half minutes. We will also see that not only the time taken for the testing to complete is shortened, but also the amount of time the user is unable to use their testing computer is reduced to almost none. Additionally, during this paper we will look at the standard implementation of TestU01 and how it compares with a preexisting Parallel version of TestU01. We will be comparing the performance of the standard version of TestU01 with the parallel version so that we have a performance baseline to test our own modifications against. Finally, this paper will also discuss the use of the distributed computing system HTCondor, and cover some basic instructions related to setting up and using HTCondor. HTCondor is already known to increase the performance of a networked group of computers by allowing super users to utilize additional resources from other lesser users idle workstation. We will relate the model recommended for HTCondor to a standard computer lab found at a University and explain why they are the perfect candidates for the system.
Flare: Native Compilation for Heterogeneous Workloads in Apache Spark
Venue: arXiv cs.DB 2017
Year: 2017

The need for modern data analytics to combine relational, procedural, and map-reduce-style functional processing is widely recognized. State-of-the-art systems like Spark have added SQL front-ends and relational query optimization, which promise an increase in expressiveness and performance. But how good are these extensions at extracting high performance from modern hardware platforms? While Spark has made impressive progress, we show that for relational workloads, there is still a significant gap compared with best-of-breed query engines. And when stepping outside of the relational world, query optimization techniques are ineffective if large parts of a computation have to be treated as user-defined functions (UDFs). We present Flare: a new back-end for Spark that brings performance closer to the best SQL engines, without giving up the added expressiveness of Spark. We demonstrate order of magnitude speedups both for relational workloads such as TPC-H, as well as for a range of machine learning kernels that combine relational and iterative functional processing. Flare achieves these results through (1) compilation to native code, (2) replacing parts of the Spark runtime system, and (3) extending the scope of optimization and code generation to large classes of UDFs.
Automatically Tuning the GCC Compiler to Optimize the Performance of Applications Running on Embedded Systems
Venue: arXiv cs.DC 2017
Year: 2017

This paper introduces a novel method for automatically tuning the selection of compiler flags to optimize the performance of software intended to run on embedded hardware platforms. We begin by developing our approach on code compiled by the GNU C Compiler (GCC) for the ARM Cortex-M3 (CM3) processor; and we show how our method outperforms the industry standard -O3 optimization level across a diverse embedded benchmark suite. First we quantify the potential gains by using existing iterative compilation approaches that time-intensively search for optimal configurations for each benchmark. Then we adapt iterative compilation to output a single configuration that optimizes performance across the entire benchmark suite. Although this is a time-consuming process, our approach constructs an optimized variation of -O3, which we call -Ocm3, that realizes nearly two thirds of known available gains on the CM3 and significantly outperforms a more complex state-of-the-art predictive method in cross-validation experiments. Finally, we demonstrate our method on additional platforms by constructing two more optimization levels that find even more significant speed-ups on the ARM Cortex-A8 and 8-bit AVR processors.
Millimeter Wave Small-Scale Spatial Statistics in an Urban Microcell Scenario
Venue: arXiv cs.IT 2017
Year: 2017

This paper presents outdoor wideband small-scale spatial fading and autocorrelation measurements and results in the 73 GHz millimeter-wave (mmWave) band conducted in downtown Brooklyn, New York. Both directional and omnidirectional receiver (RX) antennas are studied. Two pairs of transmitter (TX) and RX locations were tested with one line-of-sight (LOS) and one non-line-of-sight (NLOS) environment, where a linear track was employed at each RX to move the antenna in half-wavelength increments. Measured data reveal that the small-scale spatial fading of the received signal voltage amplitude are generally Ricean-distributed for both omnidirectional and directional RX antenna patterns under both LOS and NLOS conditions in most cases, except for the log-normal distribution for the omnidirectional RX antenna pattern in the NLOS environment. Sinusoidal exponential and typical exponential functions are found to model small-scale spatial autocorrelation of the received signal voltage amplitude in LOS and NLOS environments in most cases, respectively. Furthermore, different decorrelation distances were observed for different RX track orientations, i.e., for different directions of motion relative to the TX. Results herein are valuable for characterizing small-scale spatial fading and autocorrelation properties in multiple-input multiple-output (MIMO) systems for fifth-generation (5G) mmWave frequencies.
Mean-Field Controllability and Decentralized Stabilization of Markov Chains, Part I: Global Controllability and Rational Feedbacks
Venue: arXiv cs.SY 2017
Year: 2017

In this paper, we study the controllability and stabilizability properties of the Kolmogorov forward equation of a continuous time Markov chain (CTMC) evolving on a finite state space, using the transition rates as the control parameters. Firstly, we prove small-time local and global controllability from and to strictly positive equilibrium configurations when the underlying graph is strongly connected. Secondly, we show that there always exists a locally exponentially stabilizing decentralized linear (density-)feedback law that takes zero valu at equilibrium and respects the graph structure, provided that the transition rates are allowed to be negative and the desired target density lies in the interior of the set of probability densities. For bidirected graphs, that is, graphs where a directed edge in one direction implies an edge in the opposite direction, we show that this linear control law can be realized using a decentralized rational feedback law of the form k(x) = a(x) + b(x)f(x)/g(x) that also respects the graph structure and control constraints (positivity and zero at equilibrium). This enables the possibility of using Linear Matrix Inequality (LMI) based tools to algorithmically construct decentralized density feedback controllers for stabilization of a robotic swarm to a target task distribution with no task-switching at equilibrium, as we demonstrate with several numerical examples.
On the Robustness of Convolutional Neural Networks to Internal Architecture and Weight Perturbations
Venue: arXiv cs.LG 2017
Year: 2017

Deep convolutional neural networks are generally regarded as robust function approximators. So far, this intuition is based on perturbations to external stimuli such as the images to be classified. Here we explore the robustness of convolutional neural networks to perturbations to the internal weights and architecture of the network itself. We show that convolutional networks are surprisingly robust to a number of internal perturbations in the higher convolutional layers but the bottom convolutional layers are much more fragile. For instance, Alexnet shows less than a 30% decrease in classification performance when randomly removing over 70% of weight connections in the top convolutional or dense layers but performance is almost at chance with the same perturbation in the first convolutional layer. Finally, we suggest further investigations which could continue to inform the robustness of convolutional networks to internal perturbations.
Structural Resolution with Co-inductive Loop Detection
Venue: arXiv cs.LO 2017
Year: 2017

A way to combine co-SLD style loop detection with structural resolution was found and is introduced in this work, to extend structural resolution with co-induction. In particular, we present the operational semantics, called co-inductive structural resolution, of this novel combination and prove its soundness with respect to the greatest complete Herbrand model.
A new class of three-weight linear codes from weakly regular plateaued functions
Venue: arXiv cs.IT 2017
Year: 2017

Linear codes with few weights have many applications in secret sharing schemes, authentication codes, communication and strongly regular graphs. In this paper, we consider linear codes with three weights in arbitrary characteristic. To do this, we generalize the recent contribution of Mesnager given in [Cryptography and Communications 9(1), 71-84, 2017]. We first present a new class of binary linear codes with three weights from plateaued Boolean functions and their weight distributions. We next introduce the notion of (weakly) regular plateaued functions in odd characteristic $p$ and give concrete examples of these functions. Moreover, we construct a new class of three-weight linear $p$-ary codes from weakly regular plateaued functions and determine their weight distributions. We finally analyse the constructed linear codes for secret sharing schemes.
D-Optimal Input Design for Nonlinear FIR-type Systems:A Dispersion-based Approach
Venue: arXiv cs.SY 2017
Year: 2017

Optimal input design is an important step of the identification process in order to reduce the model variance. In this work a D-optimal input design method for finite-impulse-response-type nonlinear systems is presented. The optimization of the determinant of the Fisher information matrix is expressed as a convex optimization problem. This problem is then solved using a dispersion-based optimization scheme, which is easy to implement and converges monotonically to the optimal solution. Without constraints, the optimal design cannot be realized as a time sequence. By imposing that the design should lie in the subspace described by a symmetric and non-overlapping set, a realizable design is found. A graph-based method is used in order to find a time sequence that realizes this optimal constrained design. These methods are illustrated on a numerical example of which the results are thoroughly discussed. Additionally the computational speed of the algorithm is compared with the general convex optimizer cvx.
Asymmetric Learning Vector Quantization for Efficient Nearest Neighbor Classification in Dynamic Time Warping Spaces
Venue: arXiv cs.LG 2017
Year: 2017

The nearest neighbor method together with the dynamic time warping (DTW) distance is one of the most popular approaches in time series classification. This method suffers from high storage and computation requirements for large training sets. As a solution to both drawbacks, this article extends learning vector quantization (LVQ) from Euclidean spaces to DTW spaces. The proposed LVQ scheme uses asymmetric weighted averaging as update rule. Empirical results exhibited superior performance of asymmetric generalized LVQ (GLVQ) over other state-of-the-art prototype generation methods for nearest neighbor classification.
K-Means Clustering using Tabu Search with Quantized Means
Venue: arXiv cs.LG 2017
Year: 2017

The Tabu Search (TS) metaheuristic has been proposed for K-Means clustering as an alternative to Lloyd's algorithm, which for all its ease of implementation and fast runtime, has the major drawback of being trapped at local optima. While the TS approach can yield superior performance, it involves a high computational complexity. Moreover, the difficulty in parameter selection in the existing TS approach does not make it any more attractive. This paper presents an alternative, low-complexity formulation of the TS optimization procedure for K-Means clustering. This approach does not require many parameter settings. We initially constrain the centers to points in the dataset. We then aim at evolving these centers using a unique neighborhood structure that makes use of gradient information of the objective function. This results in an efficient exploration of the search space, after which the means are refined. The proposed scheme is implemented in MATLAB and tested on four real-world datasets, and it achieves a significant improvement over the existing TS approach in terms of the intra cluster sum of squares and computational time.