OpenRaiser/Intern-Atlas huggingface dataset:
A Service-Oriented Architecture for Assisting the Authoring of Semantic Crowd Maps
Venue: arXiv cs.AI 2017
Year: 2017

Although there are increasingly more initiatives for the generation of semantic knowledge based on user participation, there is still a shortage of platforms for regular users to create applications on which semantic data can be exploited and generated automatically. We propose an architecture, called Semantic Maps (SeMaps), for assisting the authoring and hosting of applications in which the maps combine the aggregation of a Geographic Information System and crowd-generated content (called here crowd maps). In these systems, the digital map works as a blackboard for accommodating stories told by people about events they want to share with others typically participating in their social networks. SeMaps offers an environment for the creation and maintenance of sites based on crowd maps with the possibility for the user to characterize semantically that which s/he intends to mark on the map. The designer of a crowd map, by informing a linguistic expression that designates what has to be marked on the maps, is guided in a process that aims to associate a concept from a common-sense base to this linguistic expression. Thus, the crowd maps start to have dominion over common-sense inferential relations that define the meaning of the marker, and are able to make inferences about the network of linked data. This makes it possible to generate maps that have the power to perform inferences and access external sources (such as DBpedia) that constitute information that is useful and appropriate to the context of the map. In this paper we describe the architecture of SeMaps and how it was applied in a crowd map authoring tool.
On Multi-source Networks: Enumeration, Rate Region Computation, and Hierarchy
Venue: arXiv cs.IT 2017
Year: 2017

Recent algorithmic developments have enabled computers to automatically determine and prove the capacity regions of small hypergraph networks under network coding. A structural theory relating network coding problems of different sizes is developed to make best use of this newfound computational capability. A formal notion of network minimality is developed which removes components of a network coding problem that are inessential to its core complexity. Equivalence between different network coding problems under relabeling is formalized via group actions, an algorithm which can directly list single representatives from each equivalence class of minimal networks up to a prescribed network size is presented. This algorithm, together with rate region software, is leveraged to create a database containing the rate regions for all minimal network coding problems with five or fewer sources and edges, a collection of 744119 equivalence classes representing more than 9 million networks. In order to best learn from this database, and to leverage it to infer rate regions and their characteristics of networks at scale, a hierarchy between different network coding problems is created with a new theory of combinations and embedding operators.
ActiVis: Visual Exploration of Industry-Scale Deep Neural Network Models
Venue: arXiv cs.HC 2017
Year: 2017

While deep learning models have achieved state-of-the-art accuracies for many prediction tasks, understanding these models remains a challenge. Despite the recent interest in developing visual tools to help users interpret deep learning models, the complexity and wide variety of models deployed in industry, and the large-scale datasets that they used, pose unique design challenges that are inadequately addressed by existing work. Through participatory design sessions with over 15 researchers and engineers at Facebook, we have developed, deployed, and iteratively improved ActiVis, an interactive visualization system for interpreting large-scale deep learning models and results. By tightly integrating multiple coordinated views, such as a computation graph overview of the model architecture, and a neuron activation view for pattern discovery and comparison, users can explore complex deep neural network models at both the instance- and subset-level. ActiVis has been deployed on Facebook's machine learning platform. We present case studies with Facebook researchers and engineers, and usage scenarios of how ActiVis may work with different models.
A Characterization of Undirected Graphs Admitting Optimal Cost Shares
Venue: arXiv cs.GT 2017
Year: 2017

In a seminal paper, Chen, Roughgarden and Valiant studied cost sharing protocols for network design with the objective to implement a low-cost Steiner forest as a Nash equilibrium of an induced cost-sharing game. One of the most intriguing open problems to date is to understand the power of budget-balanced and separable cost sharing protocols in order to induce low-cost Steiner forests. In this work, we focus on undirected networks and analyze topological properties of the underlying graph so that an optimal Steiner forest can be implemented as a Nash equilibrium (by some separable cost sharing protocol) independent of the edge costs. We term a graph efficient if the above stated property holds. As our main result, we give a complete characterization of efficient undirected graphs for two-player network design games: an undirected graph is efficient if and only if it does not contain (at least) one out of few forbidden subgraphs. Our characterization implies that several graph classes are efficient: generalized series-parallel graphs, fan and wheel graphs and graphs with small cycles.
Tactics and Tallies: A Study of the 2016 U.S. Presidential Campaign Using Twitter 'Likes'
Venue: arXiv cs.SI 2017
Year: 2017

We propose a framework to measure, evaluate, and rank campaign effectiveness in the ongoing 2016 U.S. presidential election. Using Twitter data collected from Sept. 2015 to Jan. 2016, we first uncover the tweeting tactics of the candidates and second, using negative binomial regression and exploiting the variations in 'likes,' we evaluate the effectiveness of these tactics. Thirdly, we rank the candidates' campaign tactics by calculating the conditional expectation of their generated 'likes.' We show that while Ted Cruz and Marco Rubio put much weight on President Obama, this tactic is not being well received by their supporters. We demonstrate that Hillary Clinton's tactic of linking herself to President Obama resonates well with her supporters but the same is not true for Bernie Sanders. In addition, we show that Donald Trump is a major topic for all the other candidates and that the women issue is equally emphasized in Sanders' campaign as in Clinton's. Finally, we suggest two ways that politicians can use the feedback mechanism in social media to improve their campaign: (1) use feedback from social media to improve campaign tactics within social media; (2) prototype policies and test the public response from the social media.
Total Variation Minimization in Compressed Sensing
Venue: arXiv cs.IT 2017
Year: 2017

This chapter gives an overview over recovery guarantees for total variation minimization in compressed sensing for different measurement scenarios. In addition to summarizing the results in the area, we illustrate why an approach that is common for synthesis sparse signals fails and different techniques are necessary. Lastly, we discuss a generalizations of recent results for Gaussian measurements to the subgaussian case.
Partial Face Detection in the Mobile Domain
Venue: arXiv cs.CV 2017
Year: 2017

Generic face detection algorithms do not perform well in the mobile domain due to significant presence of occluded and partially visible faces. One promising technique to handle the challenge of partial faces is to design face detectors based on facial segments. In this paper two different approaches of facial segment-based face detection are discussed, namely, proposal-based detection and detection by end-to-end regression. Methods that follow the first approach rely on generating face proposals that contain facial segment information. The three detectors following this approach, namely Facial Segment-based Face Detector (FSFD), SegFace and DeepSegFace, discussed in this paper, perform binary classification on each proposal based on features learned from facial segments. The process of proposal generation, however, needs to be handled separately, which can be very time consuming, and is not truly necessary given the nature of the active authentication problem. Hence a novel algorithm, Deep Regression-based User Image Detector (DRUID) is proposed, which shifts from the classification to the regression paradigm, thus obviating the need for proposal generation. DRUID has an unique network architecture with customized loss functions, is trained using a relatively small amount of data by utilizing a novel data augmentation scheme and is fast since it outputs the bounding boxes of a face and its segments in a single pass. Being robust to occlusion by design, the facial segment-based face detection methods, especially DRUID show superior performance over other state-of-the-art face detectors in terms of precision-recall and ROC curve on two mobile face datasets.
Hierarchical Clustering: Objective Functions and Algorithms
Venue: arXiv cs.DS 2017
Year: 2017

Hierarchical clustering is a recursive partitioning of a dataset into clusters at an increasingly finer granularity. Motivated by the fact that most work on hierarchical clustering was based on providing algorithms, rather than optimizing a specific objective, Dasgupta framed similarity-based hierarchical clustering as a combinatorial optimization problem, where a `good' hierarchical clustering is one that minimizes some cost function. He showed that this cost function has certain desirable properties. We take an axiomatic approach to defining `good' objective functions for both similarity and dissimilarity-based hierarchical clustering. We characterize a set of "admissible" objective functions (that includes Dasgupta's one) that have the property that when the input admits a `natural' hierarchical clustering, it has an optimal value. Equipped with a suitable objective function, we analyze the performance of practical algorithms, as well as develop better algorithms. For similarity-based hierarchical clustering, Dasgupta showed that the divisive sparsest-cut approach achieves an $O(\log^{3/2} n)$-approximation. We give a refined analysis of the algorithm and show that it in fact achieves an $O(\sqrt{\log n})$-approx. (Charikar and Chatziafratis independently proved that it is a $O(\sqrt{\log n})$-approx.). This improves upon the LP-based $O(\log n)$-approx. of Roy and Pokutta. For dissimilarity-based hierarchical clustering, we show that the classic average-linkage algorithm gives a factor 2 approx., and provide a simple and better algorithm that gives a factor 3/2 approx.. Finally, we consider `beyond-worst-case' scenario through a generalisation of the stochastic block model for hierarchical clustering. We show that Dasgupta's cost function has desirable properties for these inputs and we provide a simple 1 + o(1)-approximation in this setting.
Could you guess an interesting movie from the posters?: An evaluation of vision-based features on movie poster database
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we aim to estimate the Winner of world-wide film festival from the exhibited movie poster. The task is an extremely challenging because the estimation must be done with only an exhibited movie poster, without any film ratings and box-office takings. In order to tackle this problem, we have created a new database which is consist of all movie posters included in the four biggest film festivals. The movie poster database (MPDB) contains historic movies over 80 years which are nominated a movie award at each year. We apply a couple of feature types, namely hand-craft, mid-level and deep feature to extract various information from a movie poster. Our experiments showed suggestive knowledge, for example, the Academy award estimation can be better rate with a color feature and a facial emotion feature generally performs good rate on the MPDB. The paper may suggest a possibility of modeling human taste for a movie recommendation.
Modulation in the Air: Backscatter Communication over Ambient OFDM Carrier
Venue: arXiv cs.IT 2017
Year: 2017

Ambient backscatter communication (AmBC) enables radio-frequency (RF) powered backscatter devices (BDs) (e.g., sensors, tags) to modulate their information bits over ambient RF carriers in an over-the-air manner. This technology also called "modulation in the air", thus has emerged as a promising solution to achieve green communications for future Internet-of-Things. This paper studies an AmBC system by leveraging the ambient orthogonal frequency division multiplexing (OFDM) modulated signals in the air. We first model such AmBC system from a spread-spectrum communication perspective, upon which a novel joint design for BD waveform and receiver detector is proposed. The BD symbol period is designed to be in general an integer multiplication of the OFDM symbol period, and the waveform for BD bit `0' maintains the same state within a BD symbol period, while the waveform for BD bit `1' has a state transition in the middle of each OFDM symbol period within a BD symbol period. In the receiver detector design, we construct the test statistic that cancels out the direct-link interference by exploiting the repeating structure of the ambient OFDM signals due to the use of cyclic prefix. For the system with a single-antenna receiver, the maximum-likelihood detector is proposed to recover the BD bits, for which the optimal threshold is obtained in closed-form expression. For the system with a multi-antenna receiver, we propose a new test statistic, and derive the optimal detector. Moreover, practical timing synchronization algorithms are proposed, and we also analyze the effect of various system parameters on the system performance. Finally, extensive numerical results are provided to verify that the proposed transceiver design can improve the system bit-error-rate (BER) performance and the operating range significantly, and achieve much higher data rate, as compared to the conventional design.
Recurrent Environment Simulators
Venue: arXiv cs.AI 2017
Year: 2017

Models that can simulate how environments change in response to actions can be used by agents to plan and act efficiently. We improve on previous environment simulators from high-dimensional pixel observations by introducing recurrent neural networks that are able to make temporally and spatially coherent predictions for hundreds of time-steps into the future. We present an in-depth analysis of the factors affecting performance, providing the most extensive attempt to advance the understanding of the properties of these models. We address the issue of computationally inefficiency with a model that does not need to generate a high-dimensional image at each time-step. We show that our approach can be used to improve exploration and is adaptable to many diverse environments, namely 10 Atari games, a 3D car racing environment, and complex 3D mazes.
Algorithms for Stable Matching and Clustering in a Grid
Venue: arXiv cs.DS 2017
Year: 2017

We study a discrete version of a geometric stable marriage problem originally proposed in a continuous setting by Hoffman, Holroyd, and Peres, in which points in the plane are stably matched to cluster centers, as prioritized by their distances, so that each cluster center is apportioned a set of points of equal area. We show that, for a discretization of the problem to an $n\times n$ grid of pixels with $k$ centers, the problem can be solved in time $O(n^2 \log^5 n)$, and we experiment with two slower but more practical algorithms and a hybrid method that switches from one of these algorithms to the other to gain greater efficiency than either algorithm alone. We also show how to combine geometric stable matchings with a $k$-means clustering algorithm, so as to provide a geometric political-districting algorithm that views distance in economic terms, and we experiment with weighted versions of stable $k$-means in order to improve the connectivity of the resulting clusters.
Automated Unsupervised Segmentation of Liver Lesions in CT scans via Cahn-Hilliard Phase Separation
Venue: arXiv cs.CV 2017
Year: 2017

The segmentation of liver lesions is crucial for detection, diagnosis and monitoring progression of liver cancer. However, design of accurate automated methods remains challenging due to high noise in CT scans, low contrast between liver and lesions, as well as large lesion variability. We propose a 3D automatic, unsupervised method for liver lesions segmentation using a phase separation approach. It is assumed that liver is a mixture of two phases: healthy liver and lesions, represented by different image intensities polluted by noise. The Cahn-Hilliard equation is used to remove the noise and separate the mixture into two distinct phases with well-defined interfaces. This simplifies the lesion detection and segmentation task drastically and enables to segment liver lesions by thresholding the Cahn-Hilliard solution. The method was tested on 3Dircadb and LITS dataset.
Uncovering Group Level Insights with Accordant Clustering
Venue: arXiv cs.LG 2017
Year: 2017

Clustering is a widely-used data mining tool, which aims to discover partitions of similar items in data. We introduce a new clustering paradigm, \emph{accordant clustering}, which enables the discovery of (predefined) group level insights. Unlike previous clustering paradigms that aim to understand relationships amongst the individual members, the goal of accordant clustering is to uncover insights at the group level through the analysis of their members. Group level insight can often support a call to action that cannot be informed through previous clustering techniques. We propose the first accordant clustering algorithm, and prove that it finds near-optimal solutions when data possesses inherent cluster structure. The insights revealed by accordant clusterings enabled experts in the field of medicine to isolate successful treatments for a neurodegenerative disease, and those in finance to discover patterns of unnecessary spending.
PreCog: Improving Crowdsourced Data Quality Before Acquisition
Venue: arXiv cs.DB 2017
Year: 2017

Quality control in crowdsourcing systems is crucial. It is typically done after data collection, often using additional crowdsourced tasks to assess and improve the quality. These post-hoc methods can easily add cost and latency to the acquisition process--particularly if collecting high-quality data is important. In this paper, we argue for pre-hoc interface optimizations based on feedback that helps workers improve data quality before it is submitted and is well suited to complement post-hoc techniques. We propose the Precog system that explicitly supports such interface optimizations for common integrity constraints as well as more ambiguous text acquisition tasks where quality is ill-defined. We then develop the Segment-Predict-Explain pattern for detecting low-quality text segments and generating prescriptive explanations to help the worker improve their text input. Our unique combination of segmentation and prescriptive explanation are necessary for Precog to collect 2x more high-quality text data than non-Precog approaches on two real domains.
Stein Variational Policy Gradient
Venue: arXiv cs.LG 2017
Year: 2017

Policy gradient methods have been successfully applied to many complex reinforcement learning problems. However, policy gradient methods suffer from high variance, slow convergence, and inefficient exploration. In this work, we introduce a maximum entropy policy optimization framework which explicitly encourages parameter exploration, and show that this framework can be reduced to a Bayesian inference problem. We then propose a novel Stein variational policy gradient method (SVPG) which combines existing policy gradient methods and a repulsive functional to generate a set of diverse but well-behaved policies. SVPG is robust to initialization and can easily be implemented in a parallel manner. On continuous control problems, we find that implementing SVPG on top of REINFORCE and advantage actor-critic algorithms improves both average return and data efficiency.
A Deep Cascade of Convolutional Neural Networks for Dynamic MR Image Reconstruction
Venue: arXiv cs.CV 2017
Year: 2017

Inspired by recent advances in deep learning, we propose a framework for reconstructing dynamic sequences of 2D cardiac magnetic resonance (MR) images from undersampled data using a deep cascade of convolutional neural networks (CNNs) to accelerate the data acquisition process. In particular, we address the case where data is acquired using aggressive Cartesian undersampling. Firstly, we show that when each 2D image frame is reconstructed independently, the proposed method outperforms state-of-the-art 2D compressed sensing approaches such as dictionary learning-based MR image reconstruction, in terms of reconstruction error and reconstruction speed. Secondly, when reconstructing the frames of the sequences jointly, we demonstrate that CNNs can learn spatio-temporal correlations efficiently by combining convolution and data sharing approaches. We show that the proposed method consistently outperforms state-of-the-art methods and is capable of preserving anatomical structure more faithfully up to 11-fold undersampling. Moreover, reconstruction is very fast: each complete dynamic sequence can be reconstructed in less than 10s and, for the 2D case, each image frame can be reconstructed in 23ms, enabling real-time applications.
Exact 3D seismic data reconstruction using Tubal-Alt-Min algorithm
Venue: arXiv cs.CE 2017
Year: 2017

Data missing is an common issue in seismic data, and many methods have been proposed to solve it. In this paper, we present the low-tubal-rank tensor model and a novel tensor completion algorithm to recover 3D seismic data. This is a fast iterative algorithm, called Tubal-Alt-Min which completes our 3D seismic data by exploiting the low-tubal-rank property expressed as the product of two much smaller tensors. TubalAlt-Min alternates between estimating those two tensor using least squares minimization. We evaluate its reconstruction performance both on synthetic seismic data and land data survey. The experimental results show that compared with the tensor nuclear norm minimization algorithm, Tubal-Alt-Min improves the reconstruction error by orders of magnitude.
Securing Vehicle to Vehicle Communications using Blockchain through Visible Light and Acoustic Side-Channels
Venue: arXiv cs.CR 2017
Year: 2017

Autonomous and self-driving vehicles are appearing on the public highways. These vehicles commonly use wireless communication techniques for both vehicle-to-vehicle and vehicle-to-infrastructure communications. Manufacturers, regulators and the public are understandably concerned about large-scale systems failure or malicious attack via these wireless vehicular networks. This paper explores the use of sensing and signalling devices that are commonly integrated into modern vehicles for side-channel communication purposes. Visible light (using a CMOS camera) and acoustic (ultrasonic audio) side-channel encoding techniques are proposed, developed and evaluated in this context. The side-channels are examined both theoretically and experimentally and an upper bound on the line code modulation rate that is achievable with these side channel schemes in the vehicular networking context is established. A novel inter-vehicle session key establishment protocol, leveraging both side-channels and a blockchain public key infrastructure, is then presented. In light of the limited channel capacity and the interoperability/security requirements for vehicular communications, techniques for constraining the throughput requirement, providing device independence and validating the location of the intended recipient vehicle, are presented. These reduce the necessary device handshake throughput to 176 bits for creating symmetric encryption and message authentication keys and in verifying a vehicle's certificate with a recognised certification authority.