OpenRaiser/Intern-Atlas huggingface dataset:
An Adaptive Sublinear-Time Block Sparse Fourier Transform
Venue: arXiv cs.DS 2017
Year: 2017

The problem of approximately computing the $k$ dominant Fourier coefficients of a vector $X$ quickly, and using few samples in time domain, is known as the Sparse Fourier Transform (sparse FFT) problem. A long line of work on the sparse FFT has resulted in algorithms with $O(k\log n\log (n/k))$ runtime [Hassanieh et al., STOC'12] and $O(k\log n)$ sample complexity [Indyk et al., FOCS'14]. These results are proved using non-adaptive algorithms, and the latter $O(k\log n)$ sample complexity result is essentially the best possible under the sparsity assumption alone. This paper revisits the sparse FFT problem with the added twist that the sparse coefficients approximately obey a $(k_0,k_1)$-block sparse model. In this model, signal frequencies are clustered in $k_0$ intervals with width $k_1$ in Fourier space, where $k= k_0k_1$ is the total sparsity. Signals arising in applications are often well approximated by this model with $k_0\ll k$. Our main result is the first sparse FFT algorithm for $(k_0, k_1)$-block sparse signals with the sample complexity of $O^*(k_0k_1 + k_0\log(1+ k_0)\log n)$ at constant signal-to-noise ratios, and sublinear runtime. A similar sample complexity was previously achieved in the works on model-based compressive sensing using random Gaussian measurements, but used $Ω(n)$ runtime. To the best of our knowledge, our result is the first sublinear-time algorithm for model based compressed sensing, and the first sparse FFT result that goes below the $O(k\log n)$ sample complexity bound. Our algorithm crucially uses {\em adaptivity} to achieve the improved sample complexity bound, and we prove that adaptivity is in fact necessary if Fourier measurements are used: Any non-adaptive algorithm must use $Ω(k_0k_1\log \frac{n}{k_0k_1})$ samples for the $(k_0,k_1$)-block sparse model, ruling out improvements over the vanilla sparsity assumption.
Combinatorial Secretary Problems with Ordinal Information
Venue: arXiv cs.DS 2017
Year: 2017

The secretary problem is a classic model for online decision making. Recently, combinatorial extensions such as matroid or matching secretary problems have become an important tool to study algorithmic problems in dynamic markets. Here the decision maker must know the numerical value of each arriving element, which can be a demanding informational assumption. In this paper, we initiate the study of combinatorial secretary problems with ordinal information, in which the decision maker only needs to be aware of a preference order consistent with the values of arrived elements. The goal is to design online algorithms with small competitive ratios. For a variety of combinatorial problems, such as bipartite matching, general packing LPs, and independent set with bounded local independence number, we design new algorithms that obtain constant competitive ratios. For the matroid secretary problem, we observe that many existing algorithms for special matroid structures maintain their competitive ratios even in the ordinal model. In these cases, the restriction to ordinal information does not represent any additional obstacle. Moreover, we show that ordinal variants of the submodular matroid secretary problems can be solved using algorithms for the linear versions by extending [Feldman and Zenklusen, 2015]. In contrast, we provide a lower bound of $Ω(\sqrt{n}/(\log n))$ for algorithms that are oblivious to the matroid structure, where $n$ is the total number of elements. This contrasts an upper bound of $O(\log n)$ in the cardinal model, and it shows that the technique of thresholding is not sufficient for good algorithms in the ordinal model.
Embedded Systems Architecture for SLAM Applications
Venue: arXiv cs.AR 2017
Year: 2017

In recent years, we have observed a clear trend in the rapid rise of autonomous vehicles, robotics, virtual reality, and augmented reality. The core technology enabling these applications, Simultaneous Localization And Mapping (SLAM), imposes two main challenges: first, these workloads are computationally intensive and they often have real-time requirements; second, these workloads run on battery-powered mobile devices with limited energy budget. In short, the essence of these challenges is that performance should be improved while simultaneously reducing energy consumption, two rather contradicting goals by conventional wisdom. In this paper, we take a close look at state-of-the-art Simultaneous Localization And Mapping (SLAM) workloads, especially how these workloads behave on mobile devices. Based on the results, we propose a mobile architecture to improve SLAM performance on mobile devices.
Fast and easy blind deblurring using an inverse filter and PROBE
Venue: arXiv cs.CV 2017
Year: 2017

PROBE (Progressive Removal of Blur Residual) is a recursive framework for blind deblurring. Using the elementary modified inverse filter at its core, PROBE's experimental performance meets or exceeds the state of the art, both visually and quantitatively. Remarkably, PROBE lends itself to analysis that reveals its convergence properties. PROBE is motivated by recent ideas on progressive blind deblurring, but breaks away from previous research by its simplicity, speed, performance and potential for analysis. PROBE is neither a functional minimization approach, nor an open-loop sequential method (blur kernel estimation followed by non-blind deblurring). PROBE is a feedback scheme, deriving its unique strength from the closed-loop architecture rather than from the accuracy of its algorithmic components.
Robust features for facial action recognition
Venue: arXiv cs.CV 2017
Year: 2017

Automatic recognition of facial gestures is becoming increasingly important as real world AI agents become a reality. In this paper, we present an automated system that recognizes facial gestures by capturing local changes and encoding the motion into a histogram of frequencies. We evaluate the proposed method by demonstrating its effectiveness on spontaneous face action benchmarks: the FEEDTUM dataset, the Pain dataset and the HMDB51 dataset. The results show that, compared to known methods, the new encoding methods significantly improve the recognition accuracy and the robustness of analysis for a variety of applications.
Online Voltage Stability Assessment for Load Areas Based on the Holomorphic Embedding Method
Venue: arXiv cs.CE 2017
Year: 2017

This paper proposes an online steady-state voltage stability assessment scheme to evaluate the proximity to voltage collapse at each bus of a load area. Using a non-iterative holomorphic embedding method (HEM) with a proposed physical germ solution, an accurate loading limit at each load bus can be calculated based on online state estimation on the entire load area and a measurement-based equivalent for the external system. The HEM employs a power series to calculate an accurate Power-Voltage (P-V) curve at each load bus and accordingly evaluates the voltage stability margin considering load variations in the next period. An adaptive two-stage Pade approximants method is proposed to improve the convergence of the power series for accurate determination of the nose point on the P-V curve with moderate computational burden. The proposed method is illustrated in detail on a 4-bus test system and then demonstrated on a load area of the Northeast Power Coordinating Council (NPCC) 48-geneartor, 140-bus power system.
Generalized 3D Voxel Image Synthesis Architecture for Volumetric Spatial Visualization
Venue: arXiv cs.GR 2017
Year: 2017

A general concept of 3D volumetric visualization systems is described based on 3D discrete voxel scenes (worlds) representation. Definitions of 3D discrete voxel scene (world) basic elements and main steps of the image synthesis algorithm are formulated. An algorithm for solving the problem of the voxelized world 3D image synthesis, intended for the systems of volumetric spatial visualization, is proposed. A computer-based architecture for 3D volumetric visualization of 3D discrete voxel world is presented. On the basis of the proposed overall concept of discrete voxel representation, the proposed architecture successfully adapts the ray tracing technique for the synthesis of 3D volumetric images. Since it is algorithmically simple and effectively supports parallelism, it can efficiently be implemented. Key words:Volumetric spatial visualization, 3D volumetric imagesynthesis, discrete voxel world, ray tracing.
Concurrent Activity Recognition with Multimodal CNN-LSTM Structure
Venue: arXiv cs.CV 2017
Year: 2017

We introduce a system that recognizes concurrent activities from real-world data captured by multiple sensors of different types. The recognition is achieved in two steps. First, we extract spatial and temporal features from the multimodal data. We feed each datatype into a convolutional neural network that extracts spatial features, followed by a long-short term memory network that extracts temporal information in the sensory data. The extracted features are then fused for decision making in the second step. Second, we achieve concurrent activity recognition with a single classifier that encodes a binary output vector in which elements indicate whether the corresponding activity types are currently in progress. We tested our system with three datasets from different domains recorded using different sensors and achieved performance comparable to existing systems designed specifically for those domains. Our system is the first to address the concurrent activity recognition with multisensory data using a single model, which is scalable, simple to train and easy to deploy.
Feasibility, Architecture and Cost Considerations of Using TVWS for Rural Internet Access in 5G
Venue: arXiv cs.NI 2017
Year: 2017

The cellular technology is mostly an urban technology that has been unable to serve rural areas well. This is because the traditional cellular models are not economical for areas with low user density and lesser revenues. In 5G cellular networks, the coverage dilemma is likely to remain the same, thus widening the rural-urban digital divide further. It is about time to identify the root cause that has hindered the rural technology growth and analyse the possible options in 5G architecture to address this issue. We advocate that it can only be accomplished in two phases by sequentially addressing economic viability followed by performance progression. We deliberate how various works in literature focus on the later stage of this two-phase problem and are not feasible to implement in the first place. We propose the concept of TV band white space (TVWS) dovetailed with 5G infrastructure for rural coverage and show that it can yield cost-effectiveness from a service provider perspective.
Q-WordNet PPV: Simple, Robust and (almost) Unsupervised Generation of Polarity Lexicons for Multiple Languages
Venue: arXiv cs.CL 2017
Year: 2017

This paper presents a simple, robust and (almost) unsupervised dictionary-based method, qwn-ppv (Q-WordNet as Personalized PageRanking Vector) to automatically generate polarity lexicons. We show that qwn-ppv outperforms other automatically generated lexicons for the four extrinsic evaluations presented here. It also shows very competitive and robust results with respect to manually annotated ones. Results suggest that no single lexicon is best for every task and dataset and that the intrinsic evaluation of polarity lexicons is not a good performance indicator on a Sentiment Analysis task. The qwn-ppv method allows to easily create quality polarity lexicons whenever no domain-based annotated corpora are available for a given language.
Search Intelligence: Deep Learning For Dominant Category Prediction
Venue: arXiv cs.IR 2017
Year: 2017

Deep Neural Networks, and specifically fully-connected convolutional neural networks are achieving remarkable results across a wide variety of domains. They have been trained to achieve state-of-the-art performance when applied to problems such as speech recognition, image classification, natural language processing and bioinformatics. Most of these deep learning models when applied to classification employ the softmax activation function for prediction and aim to minimize cross-entropy loss. In this paper, we have proposed a supervised model for dominant category prediction to improve search recall across all eBay classifieds platforms. The dominant category label for each query in the last 90 days is first calculated by summing the total number of collaborative clicks among all categories. The category having the highest number of collaborative clicks for the given query will be considered its dominant category. Second, each query is transformed to a numeric vector by mapping each unique word in the query document to a unique integer value; all padded to equal length based on the maximum document length within the pre-defined vocabulary size. A fully-connected deep convolutional neural network (CNN) is then applied for classification. The proposed model achieves very high classification accuracy compared to other state-of-the-art machine learning techniques.
A 2-Approximation for the Height of Maximal Outerplanar Graph Drawings
Venue: arXiv cs.DS 2017
Year: 2017

In this paper, we study planar drawings of maximal outerplanar graphs with the objective of achieving small height. A recent paper gave an algorithm for such drawings that is within a factor of 4 of the optimum height. In this paper, we substantially improve the approximation factor to become 2. The main ingredient is to define a new parameter of outerplanar graphs (the so-called umbrella depth, obtained by recursively splitting the graph into graphs called umbrellas). We argue that the height of any poly-line drawing must be at least the umbrella depth, and then devise an algorithm that achieves height at most twice the umbrella depth.
Successive Local and Successive Global Omniscience
Venue: arXiv cs.IT 2017
Year: 2017

This paper considers two generalizations of the cooperative data exchange problem, referred to as the successive local omniscience (SLO) and the successive global omniscience (SGO). The users are divided into $\ell$ nested sub-groups. Each user initially knows a subset of packets in a ground set $X$ of size $k$, and all users wish to learn all packets in $X$. The users exchange their packets by broadcasting coded or uncoded packets. In SLO or SGO, in the $l$th ($1\leq l\leq \ell$) round of transmissions, the $l$th smallest sub-group of users need to learn all packets they collectively hold or all packets in $X$, respectively. The problem is to find the minimum sum-rate (i.e., the total transmission rate by all users) for each round, subject to minimizing the sum-rate for the previous round. To solve this problem, we use a linear-programming approach. For the cases in which the packets are randomly distributed among users, we construct a system of linear equations whose solution characterizes the minimum sum-rate for each round with high probability as $k$ tends to infinity. Moreover, for the special case of two nested groups, we derive closed-form expressions, which hold with high probability as $k$ tends to infinity, for the minimum sum-rate for each round.
ASHACL: Alternative Shapes Constraint Language
Venue: arXiv cs.AI 2017
Year: 2017

ASHACL, a variant of the W3C Shapes Constraint Language, is designed to determine whether an RDF graph meets some conditions. These conditions are grouped into shapes, which validate whether particular RDF terms each meet the constraints of the shape. Shapes are themselves expressed as RDF triples in an RDF graph, called a shapes graph.
Radial Contour Labeling with Straight Leaders
Venue: arXiv cs.CG 2017
Year: 2017

The usefulness of technical drawings as well as scientific illustrations such as medical drawings of human anatomy essentially depends on the placement of labels that describe all relevant parts of the figure. In order to not spoil or clutter the figure with text, the labels are often placed around the figure and are associated by thin connecting lines to their features, respectively. This labeling technique is known as external label placement. In this paper we introduce a flexible and general approach for external label placement assuming a contour of the figure prescribing the possible positions of the labels. While much research on external label placement aims for fast labeling procedures for interactive systems, we focus on highest-quality illustrations. Based on interviews with domain experts and a semi-automatic analysis of 202 handmade anatomical drawings, we identify a set of 18 layout quality criteria, naturally not all of equal importance. We design a new geometric label placement algorithm that is based only on the most important criteria. Yet, other criteria can flexibly be included in the algorithm, either as hard constraints not to be violated or as soft constraints whose violation is penalized by a general cost function. We formally prove that our approach yields labelings that satisfy all hard constraints and have minimum overall cost. Introducing several speedup techniques, we further demonstrate how to deploy our approach in practice. In an experimental evaluation on real-world anatomical drawings we show that the resulting labelings are of high quality and can be produced in adequate time.
Ensemble Distillation for Neural Machine Translation
Venue: arXiv cs.CL 2017
Year: 2017

Knowledge distillation describes a method for training a student network to perform better by learning from a stronger teacher network. Translating a sentence with an Neural Machine Translation (NMT) engine is time expensive and having a smaller model speeds up this process. We demonstrate how to transfer the translation quality of an ensemble and an oracle BLEU teacher network into a single NMT system. Further, we present translation improvements from a teacher network that has the same architecture and dimensions of the student network. As the training of the student model is still expensive, we introduce a data filtering method based on the knowledge of the teacher model that not only speeds up the training, but also leads to better translation quality. Our techniques need no code change and can be easily reproduced with any NMT architecture to speed up the decoding process.
Beam Search Strategies for Neural Machine Translation
Venue: arXiv cs.CL 2017
Year: 2017

The basic concept in Neural Machine Translation (NMT) is to train a large Neural Network that maximizes the translation performance on a given parallel corpus. NMT is then using a simple left-to-right beam-search decoder to generate new translations that approximately maximize the trained conditional probability. The current beam search strategy generates the target sentence word by word from left-to- right while keeping a fixed amount of active candidates at each time step. First, this simple search is less adaptive as it also expands candidates whose scores are much worse than the current best. Secondly, it does not expand hypotheses if they are not within the best scoring candidates, even if their scores are close to the best one. The latter one can be avoided by increasing the beam size until no performance improvement can be observed. While you can reach better performance, this has the draw- back of a slower decoding speed. In this paper, we concentrate on speeding up the decoder by applying a more flexible beam search strategy whose candidate size may vary at each time step depending on the candidate scores. We speed up the original decoder by up to 43% for the two language pairs German-English and Chinese-English without losing any translation quality.
Sharing LRU Cache Resources among Content Providers: A Utility-Based Approach
Venue: arXiv cs.NI 2017
Year: 2017

In this paper, we consider the problem of allocating cache resources among multiple content providers. The cache can be partitioned into slices and each partition can be dedicated to a particular content provider, or shared among a number of them. It is assumed that each partition employs the LRU policy for managing content. We propose utility-driven partitioning, where we associate with each content provider a utility that is a function of the hit rate observed by the content provider. We consider two scenarios: i)~content providers serve disjoint sets of files, ii)~there is some overlap in the content served by multiple content providers. In the first case, we prove that cache partitioning outperforms cache sharing as cache size and numbers of contents served by providers go to infinity. In the second case, It can be beneficial to have separate partitions for overlapped content. In the case of two providers, it is usually always beneficial to allocate a cache partition to serve all overlapped content and separate partitions to serve the non-overlapped contents of both providers. We establish conditions when this is true asymptotically but also present an example where it is not true asymptotically. We develop online algorithms that dynamically adjust partition sizes in order to maximize the overall utility and prove that they converge to optimal solutions, and through numerical evaluations, we show they are effective.
Linear Time Approximation Schemes for Geometric Maximum Coverage
Venue: arXiv cs.CG 2017
Year: 2017

We study approximation algorithms for the following geometric version of the maximum coverage problem: Let $\mathcal{P}$ be a set of $n$ weighted points in the plane. Let $D$ represent a planar object, such as a rectangle, or a disk. We want to place $m$ copies of $D$ such that the sum of the weights of the points in $\mathcal{P}$ covered by these copies is maximized. For any fixed $\varepsilon>0$, we present efficient approximation schemes that can find a $(1-\varepsilon)$-approximation to the optimal solution. In particular, for $m=1$ and for the special case where $D$ is a rectangle, our algorithm runs in time $O(n\log (\frac{1}{\varepsilon}))$, improving on the previous result. For $m>1$ and the rectangular case, our algorithm runs in $O(\frac{n}{\varepsilon}\log (\frac{1}{\varepsilon})+\frac{m}{\varepsilon}\log m +m(\frac{1}{\varepsilon})^{O(\min(\sqrt{m},\frac{1}{\varepsilon}))})$ time. For a more general class of shapes (including disks, polygons with $O(1)$ edges), our algorithm runs in $O(n(\frac{1}{\varepsilon})^{O(1)}+\frac{m}ε\log m + m(\frac{1}{\varepsilon})^{O(\min(m,\frac{1}{\varepsilon^2}))})$ time.
Extracting Lifted Mutual Exclusion Invariants from Temporal Planning Domains
Venue: arXiv cs.AI 2017
Year: 2017

We present a technique for automatically extracting mutual exclusion invariants from temporal planning instances. It first identifies a set of invariant templates by inspecting the lifted representation of the domain and then checks these templates against properties that assure invariance. Our technique builds on other approaches to invariant synthesis presented in the literature, but departs from their limited focus on instantaneous actions by addressing temporal domains. To deal with time, we formulate invariance conditions that account for the entire structure of the actions and the possible concurrent interactions between them. As a result, we construct a significantly more comprehensive technique than previous methods, which is able to find not only invariants for temporal domains, but also a broader set of invariants for non-temporal domains. The experimental results reported in this paper provide evidence that identifying a broader set of invariants results in the generation of fewer multi-valued state variables with larger domains. We show that, in turn, this reduction in the number of variables reflects positively on the performance of a number of temporal planners that use a variable/value representation by significantly reducing their running time.