OpenRaiser/Intern-Atlas huggingface dataset:
Outlier-robust moment-estimation via sum-of-squares
Venue: arXiv cs.DS 2017
Year: 2017

We develop efficient algorithms for estimating low-degree moments of unknown distributions in the presence of adversarial outliers. The guarantees of our algorithms improve in many cases significantly over the best previous ones, obtained in recent works of Diakonikolas et al, Lai et al, and Charikar et al. We also show that the guarantees of our algorithms match information-theoretic lower-bounds for the class of distributions we consider. These improved guarantees allow us to give improved algorithms for independent component analysis and learning mixtures of Gaussians in the presence of outliers. Our algorithms are based on a standard sum-of-squares relaxation of the following conceptually-simple optimization problem: Among all distributions whose moments are bounded in the same way as for the unknown distribution, find the one that is closest in statistical distance to the empirical distribution of the adversarially-corrupted sample.
A Color Intensity Invariant Low Level Feature Optimization Framework for Image Quality Assessment
Venue: arXiv cs.MM 2017
Year: 2017

Image Quality Assessment (IQA) algorithms evaluate the perceptual quality of an image using evaluation scores that assess the similarity or difference between two images. We propose a new low-level feature based IQA technique, which applies filter-bank decomposition and center-surround methodology. Differing from existing methods, our model incorporates color intensity adaptation and frequency scaling optimization at each filter-bank level and spatial orientation to extract and enhance perceptually significant features. Our computational model exploits the concept of object detection and encapsulates characteristics proposed in other IQA algorithms in a unified architecture. We also propose a systematic approach to review the evolution of IQA algorithms using unbiased test datasets, instead of looking at individual scores in isolation. Experimental results demonstrate the feasibility of our approach.
Machine Learning and Manycore Systems Design: A Serendipitous Symbiosis
Venue: arXiv cs.LG 2017
Year: 2017

Tight collaboration between experts of machine learning and manycore system design is necessary to create a data-driven manycore design framework that integrates both learning and expert knowledge. Such a framework will be necessary to address the rising complexity of designing large-scale manycore systems and machine learning techniques.
Inertial-aided Rolling Shutter Relative Pose Estimation
Venue: arXiv cs.CV 2017
Year: 2017

Relative pose estimation is a fundamental problem in computer vision and it has been studied for conventional global shutter cameras for decades. However, recently, a rolling shutter camera has been widely used due to its low cost imaging capability and, since the rolling shutter camera captures the image line-by-line, the relative pose estimation of a rolling shutter camera is more difficult than that of a global shutter camera. In this paper, we propose to exploit inertial measurements (gravity and angular velocity) for the rolling shutter relative pose estimation problem. The inertial measurements provide information about the partial relative rotation between two views (cameras) and the instantaneous motion that causes the rolling shutter distortion. Based on this information, we simplify the rolling shutter relative pose estimation problem and propose effective methods to solve it. Unlike the previous methods, which require 44 (linear) or 17 (nonlinear) points with the uniform rolling shutter camera model, the proposed methods require at most 9 or 11 points to estimate the relative pose between the rolling shutter cameras. Experimental results on synthetic data and the public PennCOSYVIO dataset show that the proposed methods outperform the existing methods.
Demystifying Mobile Web Browsing under Multiple Protocols
Venue: arXiv cs.NI 2017
Year: 2017

With the popularity of mobile devices, such as smartphones, tablets, users prefer visiting Web pages on mobile devices. Meanwhile, HTTP(S) plays as the major protocol to deliver Web contents, and has served the Web well for more than 15 years. However, as the Web pages grow increasingly complex to provide more content and functionality, the shortcomings and inflexibility of HTTP become more and more urgent to solve, e.g., the sluggish page load, insecure content, redundant transfer, etc. SPDY and HTTP/2 are promoted to solve the shortcomings and inflexibilities of HTTP/1.x. We are interested in how Web pages perform on smartphones with different protocols, including HTTP, HTTPS, SPDY, and HTTP/2. In this paper, we divide our experiments into two parts. First, in order to simplify our analysis, we develop our own HTTP client ignoring complicated process in real browsers to fetch synthetic Web pages with pre-specified object sizes and object numbers with different protocols, respectively. Meanwhile, we emulate different network conditions between client and server using Traffic Control. In order to test with real browsers, we clone Alexa top 200 websites, which have the corresponding mobile version, into our local host. Meanwhile, we control mobile Chrome browser to load those Web pages with different protocols and emulate different network conditions using Traffic Control. We identify how Web page characteristics and network conditions affect Web performance on smartphones for each protocol. We also conduct experiments on a low-end device to observe if a less powerful processor could affect Web page performance for each protocol.
The Snow Team Problem (Clearing Directed Subgraphs by Mobile Agents)
Venue: arXiv cs.DM 2017
Year: 2017

We study several problems of clearing subgraphs by mobile agents in digraphs. The agents can move only along directed walks of a digraph and, depending on the variant, their initial positions may be pre-specified. In general, for a given subset~$\mathcal{S}$ of vertices of a digraph $D$ and a positive integer $k$, the objective is to determine whether there is a subgraph $H=(\mathcal{V}_H,\mathcal{A}_H)$ of $D$ such that (a) $\mathcal{S} \subseteq \mathcal{V}_H$, (b) $H$ is the union of $k$ directed walks in $D$, and (c) the underlying graph of $H$ includes a Steiner tree for $\mathcal{S}$ in $D$. We provide several results on the polynomial time tractability, hardness, and parameterized complexity of the problem.
Unsupervised Generative Adversarial Cross-modal Hashing
Venue: arXiv cs.CV 2017
Year: 2017

Cross-modal hashing aims to map heterogeneous multimedia data into a common Hamming space, which can realize fast and flexible retrieval across different modalities. Unsupervised cross-modal hashing is more flexible and applicable than supervised methods, since no intensive labeling work is involved. However, existing unsupervised methods learn hashing functions by preserving inter and intra correlations, while ignoring the underlying manifold structure across different modalities, which is extremely helpful to capture meaningful nearest neighbors of different modalities for cross-modal retrieval. To address the above problem, in this paper we propose an Unsupervised Generative Adversarial Cross-modal Hashing approach (UGACH), which makes full use of GAN's ability for unsupervised representation learning to exploit the underlying manifold structure of cross-modal data. The main contributions can be summarized as follows: (1) We propose a generative adversarial network to model cross-modal hashing in an unsupervised fashion. In the proposed UGACH, given a data of one modality, the generative model tries to fit the distribution over the manifold structure, and select informative data of another modality to challenge the discriminative model. The discriminative model learns to distinguish the generated data and the true positive data sampled from correlation graph to achieve better retrieval accuracy. These two models are trained in an adversarial way to improve each other and promote hashing function learning. (2) We propose a correlation graph based approach to capture the underlying manifold structure across different modalities, so that data of different modalities but within the same manifold can have smaller Hamming distance and promote retrieval accuracy. Extensive experiments compared with 6 state-of-the-art methods verify the effectiveness of our proposed approach.
Probabilistic Adaptive Computation Time
Venue: arXiv cs.LG 2017
Year: 2017

We present a probabilistic model with discrete latent variables that control the computation time in deep learning models such as ResNets and LSTMs. A prior on the latent variables expresses the preference for faster computation. The amount of computation for an input is determined via amortized maximum a posteriori (MAP) inference. MAP inference is performed using a novel stochastic variational optimization method. The recently proposed Adaptive Computation Time mechanism can be seen as an ad-hoc relaxation of this model. We demonstrate training using the general-purpose Concrete relaxation of discrete variables. Evaluation on ResNet shows that our method matches the speed-accuracy trade-off of Adaptive Computation Time, while allowing for evaluation with a simple deterministic procedure that has a lower memory footprint.
Multiple Stopping Time POMDPs: Structural Results & Application in Interactive Advertising in Social Media
Venue: arXiv cs.SY 2017
Year: 2017

This paper considers a multiple stopping time problem for a Markov chain observed in noise, where a decision maker chooses at most L stopping times to maximize a cumulative objective. We formulate the problem as a Partially Observed Markov Decision Process (POMDP) and derive structural results for the optimal multiple stopping policy. The main results are as follows: i) The optimal multiple stopping policy is shown to be characterized by threshold curves in the unit simplex of Bayesian Posteriors. ii) The stopping setsl (defined by the threshold curves) are shown to exhibit a nested structure. iii) The optimal cumulative reward is shown to be monotone with respect to the copositive ordering of the transition matrix. iv) A stochastic gradient algorithm is provided for estimating linear threshold policies by exploiting the structural results. These linear threshold policies approximate the threshold curves, and share the monotone structure of the optimal multiple stopping policy. As an illustrative example, we apply the multiple stopping framework to interactively schedule advertisements in live online social media. It is shown that advertisement scheduling using multiple stopping performs significantly better than currently used methods.
An Enhanced LMMSE Channel Estimation under High Speed Railway Scenarios
Venue: arXiv cs.IT 2017
Year: 2017

With the rapid deployment of the high speed railway (HSR), the wireless communication in HSR has been one of the indispensable scenarios in the fifth generation (5G) communications. In order to improve the performance of the orthogonal frequency division multiplexing (OFDM) system in the HSR scenarios, we propose an enhanced linear minimum mean square error channel estimation scheme based on multi-path Doppler frequency offset (DFO) estimation in this paper. The proposed scheme can estimate DFO of each path, and generate the frequency and time channel correlation more accurately, which can improve the accuracy of channel estimation in the HSR scenarios. Simulation results show that the proposed scheme can reduce the channel estimation error and achieve attractive gain in the HSR scenarios.
PFAx: Predictable Feature Analysis to Perform Control
Venue: arXiv cs.LG 2017
Year: 2017

Predictable Feature Analysis (PFA) (Richthofer, Wiskott, ICMLA 2015) is an algorithm that performs dimensionality reduction on high dimensional input signal. It extracts those subsignals that are most predictable according to a certain prediction model. We refer to these extracted signals as predictable features. In this work we extend the notion of PFA to take supplementary information into account for improving its predictions. Such information can be a multidimensional signal like the main input to PFA, but is regarded external. That means it won't participate in the feature extraction - no features get extracted or composed of it. Features will be exclusively extracted from the main input such that they are most predictable based on themselves and the supplementary information. We refer to this enhanced PFA as PFAx (PFA extended). Even more important than improving prediction quality is to observe the effect of supplementary information on feature selection. PFAx transparently provides insight how the supplementary information adds to prediction quality and whether it is valuable at all. Finally we show how to invert that relation and can generate the supplementary information such that it would yield a certain desired outcome of the main signal. We apply this to a setting inspired by reinforcement learning and let the algorithm learn how to control an agent in an environment. With this method it is feasible to locally optimize the agent's state, i.e. reach a certain goal that is near enough. We are preparing a follow-up paper that extends this method such that also global optimization is feasible.
Nearly Optimal Scheduling of Wireless Ad Hoc Networks in Polynomial Time
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we address the scheduling problem in wireless ad hoc networks by exploiting the computational advantage that comes when such scheduling problems can be represented by claw-free conflict graphs where we consider a wireless broadcast medium. It is possible to formulate a scheduling problem of network coded flows as finding maximum weighted independent set (MWIS) in the conflict graph of the network. Finding MWIS of a general graph is NP-hard leading to an NP-hard complexity of scheduling. In a claw-free conflict graph, MWIS can be found in polynomial time leading to a throughput-optimal scheduling. We show that the conflict graph of certain wireless ad hoc networks are claw-free. In order to obtain claw-free conflict graphs in general networks, we suggest introducing additional conflicts (edges) while keeping the decrease in MWIS size minimal. To this end, we introduce an iterative optimization problem to decide where to introduce edges and investigate its efficient implementation. Besides, we exemplify some physical modifications to manipulate the conflict graph of a network and also propose a mixed scheduling strategy for specific networks. We conclude that claw breaking method by adding extra edges can perform nearly optimal under the necessary assumptions.
Impact Of Urban Technology Deployments On Local Commercial Activity
Venue: arXiv cs.CY 2017
Year: 2017

While smart city innovations seem to be a common and necessary response to increasing challenges of urbanization, foreseeing their impact on complex urban system is critical for informed decision making. Moreover, often the effect of urban interventions goes beyond the original expectations, including multiple indirect impacts. The present study considers the impact of two urban deployments, Citi Bike (bike sharing system) and LinkNYC kiosks, on the local commercial activity in the affected neighborhoods of New York City. The study uses anonymized and aggregated insights provided through a grant from the Mastercard Center for Inclusive Growth in order to provide initial data-driven evidence towards the hypothesis that proximity of Citi Bike stations incentivizes local sales at eating places, while LinkNYC kiosks help people, especially visitors, to navigate local businesses and thus incentivize commercial activity in different business categories.
Polystore Mathematics of Relational Algebra
Venue: arXiv cs.DB 2017
Year: 2017

Financial transactions, internet search, and data analysis are all placing increasing demands on databases. SQL, NoSQL, and NewSQL databases have been developed to meet these demands and each offers unique benefits. SQL, NoSQL, and NewSQL databases also rely on different underlying mathematical models. Polystores seek to provide a mechanism to allow applications to transparently achieve the benefits of diverse databases while insulating applications from the details of these databases. Integrating the underlying mathematics of these diverse databases can be an important enabler for polystores as it enables effective reasoning across different databases. Associative arrays provide a common approach for the mathematics of polystores by encompassing the mathematics found in different databases: sets (SQL), graphs (NoSQL), and matrices (NewSQL). Prior work presented the SQL relational model in terms of associative arrays and identified key mathematical properties that are preserved within SQL. This work provides the rigorous mathematical definitions, lemmas, and theorems underlying these properties. Specifically, SQL Relational Algebra deals primarily with relations - multisets of tuples - and operations on and between these relations. These relations can be modeled as associative arrays by treating tuples as non-zero rows in an array. Operations in relational algebra are built as compositions of standard operations on associative arrays which mirror their matrix counterparts. These constructions provide insight into how relational algebra can be handled via array operations. As an example application, the composition of two projection operations is shown to also be a projection, and the projection of a union is shown to be equal to the union of the projections.
Lower Bounds on Regular Expression Size
Venue: arXiv cs.FL 2017
Year: 2017

We introduce linear programs encoding regular expressions of finite languages. We show that, given a language, the optimum value of the associated linear program is a lower bound on the size of any regular expression of the language. Moreover we show that any regular expression can be turned into a dual feasible solution with an objective value that is equal to the size of the regular expression. For binomial languages we can relax the associated linear program using duality theorem. We use this relaxation to prove lower bounds on the size of regular expressions of binomial and threshold languages.
Leaf Identification Using a Deep Convolutional Neural Network
Venue: arXiv cs.CV 2017
Year: 2017

Convolutional neural networks (CNNs) have become popular especially in computer vision in the last few years because they achieved outstanding performance on different tasks, such as image classifications. We propose a nine-layer CNN for leaf identification using the famous Flavia and Foliage datasets. Usually the supervised learning of deep CNNs requires huge datasets for training. However, the used datasets contain only a few examples per plant species. Therefore, we apply data augmentation and transfer learning to prevent our network from overfitting. The trained CNNs achieve recognition rates above 99% on the Flavia and Foliage datasets, and slightly outperform current methods for leaf classification.
Mining Supervisor Evaluation and Peer Feedback in Performance Appraisals
Venue: arXiv cs.CL 2017
Year: 2017

Performance appraisal (PA) is an important HR process to periodically measure and evaluate every employee's performance vis-a-vis the goals established by the organization. A PA process involves purposeful multi-step multi-modal communication between employees, their supervisors and their peers, such as self-appraisal, supervisor assessment and peer feedback. Analysis of the structured data and text produced in PA is crucial for measuring the quality of appraisals and tracking actual improvements. In this paper, we apply text mining techniques to produce insights from PA text. First, we perform sentence classification to identify strengths, weaknesses and suggestions of improvements found in the supervisor assessments and then use clustering to discover broad categories among them. Next we use multi-class multi-label classification techniques to match supervisor assessments to predefined broad perspectives on performance. Finally, we propose a short-text summarization technique to produce a summary of peer feedback comments for a given employee and compare it with manual summaries. All techniques are illustrated using a real-life dataset of supervisor assessment and peer feedback text produced during the PA of 4528 employees in a large multi-national IT company.
GANerated Hands for Real-time 3D Hand Tracking from Monocular RGB
Venue: arXiv cs.CV 2017
Year: 2017

We address the highly challenging problem of real-time 3D hand tracking based on a monocular RGB-only sequence. Our tracking method combines a convolutional neural network with a kinematic 3D hand model, such that it generalizes well to unseen data, is robust to occlusions and varying camera viewpoints, and leads to anatomically plausible as well as temporally smooth hand motions. For training our CNN we propose a novel approach for the synthetic generation of training data that is based on a geometrically consistent image-to-image translation network. To be more specific, we use a neural network that translates synthetic images to "real" images, such that the so-generated images follow the same statistical distribution as real-world hand images. For training this translation network we combine an adversarial loss and a cycle-consistency loss with a geometric consistency loss in order to preserve geometric properties (such as hand pose) during translation. We demonstrate that our hand tracking system outperforms the current state-of-the-art on challenging RGB-only footage.
Performance Heuristics for GR(1) Synthesis and Related Algorithms
Venue: arXiv cs.LO 2017
Year: 2017

Reactive synthesis for the GR(1) fragment of LTL has been implemented and studied in many works. In this workshop paper we present and evaluate a list of heuristics to potentially reduce running times for GR(1) synthesis and related algorithms. The list includes early detection of fixed-points and unrealizability, fixed-point recycling, and heuristics for unrealizable core computations. We evaluate the presented heuristics on SYNTECH15, a total of 78 specifications of 6 autonomous Lego robots, written by 3rd year undergraduate computer science students in a project class we have taught, as well as on several benchmarks from the literature. The evaluation investigates not only the potential of the suggested heuristics to improve computation times, but also the difference between existing benchmarks and the robot's specifications in terms of the effectiveness of the heuristics.
Why my photos look sideways or upside down? Detecting Canonical Orientation of Images using Convolutional Neural Networks
Venue: arXiv cs.CV 2017
Year: 2017

Image orientation detection requires high-level scene understanding. Humans use object recognition and contextual scene information to correctly orient images. In literature, the problem of image orientation detection is mostly confronted by using low-level vision features, while some approaches incorporate few easily detectable semantic cues to gain minor improvements. The vast amount of semantic content in images makes orientation detection challenging, and therefore there is a large semantic gap between existing methods and human behavior. Also, existing methods in literature report highly discrepant detection rates, which is mainly due to large differences in datasets and limited variety of test images used for evaluation. In this work, for the first time, we leverage the power of deep learning and adapt pre-trained convolutional neural networks using largest training dataset to-date for the image orientation detection task. An extensive evaluation of our model on different public datasets shows that it remarkably generalizes to correctly orient a large set of unconstrained images; it also significantly outperforms the state-of-the-art and achieves accuracy very close to that of humans.