OpenRaiser/Intern-Atlas huggingface dataset:
Efficient algorithms for robust submodular maximization under matroid constraints
Venue: arXiv cs.DS 2018
Year: 2018

In this work, we consider robust submodular maximization with matroid constraints. We give an efficient bi-criteria approximation algorithm that outputs a small family of feasible sets whose union has (nearly) optimal objective value. This algorithm theoretically performs less function calls than previous works at cost of adding more elements to the final solution. We also provide significant implementation improvements showing that our algorithm outperforms the algorithms in the existing literature. We finally assess the performance of our contributions in three real-world applications.
Distinctive-attribute Extraction for Image Captioning
Venue: arXiv cs.CV 2018
Year: 2018

Image captioning, an open research issue, has been evolved with the progress of deep neural networks. Convolutional neural networks (CNNs) and recurrent neural networks (RNNs) are employed to compute image features and generate natural language descriptions in the research. In previous works, a caption involving semantic description can be generated by applying additional information into the RNNs. In this approach, we propose a distinctive-attribute extraction (DaE) which explicitly encourages significant meanings to generate an accurate caption describing the overall meaning of the image with their unique situation. Specifically, the captions of training images are analyzed by term frequency-inverse document frequency (TF-IDF), and the analyzed semantic information is trained to extract distinctive-attributes for inferring captions. The proposed scheme is evaluated on a challenge data, and it improves an objective performance while describing images in more detail.
Prototype Discovery using Quality-Diversity
Venue: arXiv cs.NE 2018
Year: 2018

An iterative computer-aided ideation procedure is introduced, building on recent quality-diversity algorithms, which search for diverse as well as high-performing solutions. Dimensionality reduction is used to define a similarity space, in which solutions are clustered into classes. These classes are represented by prototypes, which are presented to the user for selection. In the next iteration, quality-diversity focuses on searching within the selected class. A quantitative analysis is performed on a 2D airfoil, and a more complex 3D side view mirror domain shows how computer-aided ideation can help to enhance engineers' intuition while allowing their design decisions to influence the design process.
Using control synthesis to generate corner cases: A case study on autonomous driving
Venue: arXiv cs.SY 2018
Year: 2018

This paper employs correct-by-construction control synthesis, in particular controlled invariant set computations, for falsification. Our hypothesis is that if it is possible to compute a "large enough" controlled invariant set either for the actual system model or some simplification of the system model, interesting corner cases for other control designs can be generated by sampling initial conditions from the boundary of this controlled invariant set. Moreover, if falsifying trajectories for a given control design can be found through such sampling, then the controlled invariant set can be used as a supervisor to ensure safe operation of the control design under consideration. In addition to interesting initial conditions, which are mostly related to safety violations in transients, we use solutions from a dual game, a reachability game for the safety specification, to find falsifying inputs. We also propose optimization-based heuristics for input generation for cases when the state is outside the winning set of the dual game. To demonstrate the proposed ideas, we consider case studies from basic autonomous driving functionality, in particular, adaptive cruise control and lane keeping. We show how the proposed technique can be used to find interesting falsifying trajectories for classical control designs like proportional controllers, proportional integral controllers and model predictive controllers, as well as an open source real-world autonomous driving package.
Who is the director of this movie? Automatic style recognition based on shot features
Venue: arXiv cs.MM 2018
Year: 2018

We show how low-level formal features, such as shot duration, meant as length of camera takes, and shot scale, i.e. the distance between the camera and the subject, are distinctive of a director's style in art movies. So far such features were thought of not having enough varieties to become distinctive of an author. However our investigation on the full filmographies of six different authors (Scorsese, Godard, Tarr, Fellini, Antonioni, and Bergman) for a total number of 120 movies analysed second by second, confirms that these shot-related features do not appear as random patterns in movies from the same director. For feature extraction we adopt methods based on both conventional and deep learning techniques. Our findings suggest that feature sequential patterns, i.e. how features evolve in time, are at least as important as the related feature distributions. To the best of our knowledge this is the first study dealing with automatic attribution of movie authorship, which opens up interesting lines of cross-disciplinary research on the impact of style on the aesthetic and emotional effects on the viewers.
A Memo on the Proof-of-Stake Mechanism
Venue: arXiv cs.CR 2018
Year: 2018

We analyze the economic incentives generated by the proof-of-stake mechanism discussed in the Ethereum Casper upgrade proposal. Compared with proof-of-work, proof-of-stake has a different cost structure for attackers. In Budish (2018), three equations characterize the limits of Bitcoin, which has a proof-of-work mechanism. We investigate their counterparts and evaluate the risk of double-spending attack and sabotage attack. We argue that PoS is safer than PoW agaisnt double-spending attack because of the tractability of attackers, which implies a large "stock" cost for the attacker. Compared to a PoW system whose mining equipments are repurposable, PoS is also safer against a sabotage attack.
Attend Before you Act: Leveraging human visual attention for continual learning
Venue: arXiv cs.AI 2018
Year: 2018

When humans perform a task, such as playing a game, they selectively pay attention to certain parts of the visual input, gathering relevant information and sequentially combining it to build a representation from the sensory data. In this work, we explore leveraging where humans look in an image as an implicit indication of what is salient for decision making. We build on top of the UNREAL architecture in DeepMind Lab's 3D navigation maze environment. We train the agent both with original images and foveated images, which were generated by overlaying the original images with saliency maps generated using a real-time spectral residual technique. We investigate the effectiveness of this approach in transfer learning by measuring performance in the context of noise in the environment.
Directory Reconciliation
Venue: arXiv cs.DS 2018
Year: 2018

We initiate the theoretical study of directory reconciliation, a generalization of document exchange, in which Alice and Bob each have different versions of a set of documents that they wish to synchronize. This problem is designed to capture the setting of synchronizing different versions of file directories, while allowing for changes of file names and locations without significant expense. We present protocols for efficiently solving directory reconciliation based on a reduction to document exchange under edit distance with block moves, as well as protocols combining techniques for reconciling sets of sets with document exchange protocols. Along the way, we develop a new protocol for document exchange under edit distance with block moves inspired by noisy binary search in graphs, which uses only $O(k \log n)$ bits of communication at the expense of $O(k \log n)$ rounds of communication.
Robust Set Reconciliation via Locality Sensitive Hashing
Venue: arXiv cs.DS 2018
Year: 2018

We consider variations of set reconciliation problems where two parties, Alice and Bob, each hold a set of points in a metric space, and the goal is for Bob to conclude with a set of points that is close to Alice's set of points in a well-defined way. This setting has been referred to as robust set reconciliation. More specifically, in one variation we examine the goal is for Bob to end with a set of points that is close to Alice's in earth mover's distance, and in another the goal is for Bob to have a point that is close to each of Alice's. The first problem has been studied before; our results scale better with the dimension of the space. The second problem appears new. Our primary novelty is utilizing Invertible Bloom Lookup Tables in combination with locality sensitive hashing. This combination allows us to cope with the geometric setting in a communication-efficient manner.
Data Infrastructure and Approaches for Ontology-Based Drug Repurposing
Venue: arXiv cs.IR 2018
Year: 2018

We report development of a data infrastructure for drug repurposing that takes advantage of two currently available chemical ontologies. The data infrastructure includes a database of compound- target associations augmented with molecular ontological labels. It also contains two computational tools for prediction of new associations. We describe two drug-repurposing systems: one, Nascent Ontological Information Retrieval for Drug Repurposing (NOIR-DR), based on an information retrieval strategy, and another, based on non-negative matrix factorization together with compound similarity, that was inspired by recommender systems. We report the performance of both tools on a drug-repurposing task.
Formalizing the Cox-Ross-Rubinstein pricing of European derivatives in Isabelle/HOL
Venue: arXiv cs.LO 2018
Year: 2018

We formalize in the proof assistant Isabelle essential basic notions and results in financial mathematics. We provide generic formal definitions of concepts such as markets, portfolios, derivative products, arbitrages or fair prices, and we show that, under the usual no-arbitrage condition, the existence of a replicating portfolio for a derivative implies that the latter admits a unique fair price. Then, we provide a formalization of the Cox-Rubinstein model and we show that the market is complete in this model, i.e., that every derivative product admits a replicating portfolio. This entails that in this model, every derivative product admits a unique fair price.
General-purpose Tagging of Freesound Audio with AudioSet Labels: Task Description, Dataset, and Baseline
Venue: arXiv cs.SD 2018
Year: 2018

This paper describes Task 2 of the DCASE 2018 Challenge, titled "General-purpose audio tagging of Freesound content with AudioSet labels". This task was hosted on the Kaggle platform as "Freesound General-Purpose Audio Tagging Challenge". The goal of the task is to build an audio tagging system that can recognize the category of an audio clip from a subset of 41 diverse categories drawn from the AudioSet Ontology. We present the task, the dataset prepared for the competition, and a baseline system.
Iterative Crowd Counting
Venue: arXiv cs.CV 2018
Year: 2018

In this work, we tackle the problem of crowd counting in images. We present a Convolutional Neural Network (CNN) based density estimation approach to solve this problem. Predicting a high resolution density map in one go is a challenging task. Hence, we present a two branch CNN architecture for generating high resolution density maps, where the first branch generates a low resolution density map, and the second branch incorporates the low resolution prediction and feature maps from the first branch to generate a high resolution density map. We also propose a multi-stage extension of our approach where each stage in the pipeline utilizes the predictions from all the previous stages. Empirical comparison with the previous state-of-the-art crowd counting methods shows that our method achieves the lowest mean absolute error on three challenging crowd counting benchmarks: Shanghaitech, WorldExpo'10, and UCF datasets.
Abstractions for Symbolic Controller Synthesis are Composable
Venue: arXiv cs.SY 2018
Year: 2018

Translating continuous control system models into finite automata allows us to use powerful discrete tools to synthesize controllers for complex specifications. The abstraction construction step is unfortunately hamstrung by high runtime and memory requirements for high dimensional systems. This paper describes how the transition relation encoding the abstract system dynamics can be generated by connecting smaller abstract modules in series and parallel. We provide a composition operation and show that composing a collection of abstract modules yields another abstraction satisfying a feedback refinement relation. Through compositionality we circumvent the acute computational cost of directly abstracting a high dimensional system and also modularize the abstraction construction pipeline.
Sparips
Venue: arXiv cs.CG 2018
Year: 2018

Persistent homology of the Rips filtration allows to track topological features of a point cloud over scales, and is a foundational tool of topological data analysis. Unfortunately, the Rips-filtration is exponentially sized, when considered as a filtered simplicial complex. Hence, the computation of full persistence modules is impossible for all but the tiniest of datasets; when truncating the dimension of topological features, the situation becomes slightly less intractable, but still daunting for medium-sized datasets. It is theoretically possible to approximate the Rips-filtration by a much smaller and sparser, linear-sized simplicial complexs, however, possibly due to the complexity of existing approaches, we are not aware of any existing implementation. We propose a different sparsification scheme, based on cover-trees, that is easy to implement, while giving similar guarantees on the computational scaling. We further propose a visualization that is adapted to approximate persistence diagrams, by incorporating a variant of error bars and keeping track of all approximation guarantees, explicitly.
A Better Baseline for AVA
Venue: arXiv cs.CV 2018
Year: 2018

We introduce a simple baseline for action localization on the AVA dataset. The model builds upon the Faster R-CNN bounding box detection framework, adapted to operate on pure spatiotemporal features - in our case produced exclusively by an I3D model pretrained on Kinetics. This model obtains 21.9% average AP on the validation set of AVA v2.1, up from 14.5% for the best RGB spatiotemporal model used in the original AVA paper (which was pretrained on Kinetics and ImageNet), and up from 11.3 of the publicly available baseline using a ResNet101 image feature extractor, that was pretrained on ImageNet. Our final model obtains 22.8%/21.9% mAP on the val/test sets and outperforms all submissions to the AVA challenge at CVPR 2018.
AlphaGAN: Generative adversarial networks for natural image matting
Venue: arXiv cs.CV 2018
Year: 2018

We present the first generative adversarial network (GAN) for natural image matting. Our novel generator network is trained to predict visually appealing alphas with the addition of the adversarial loss from the discriminator that is trained to classify well-composited images. Further, we improve existing encoder-decoder architectures to better deal with the spatial localization issues inherited in convolutional neural networks (CNN) by using dilated convolutions to capture global context information without downscaling feature maps and losing spatial information. We present state-of-the-art results on the alphamatting online benchmark for the gradient error and give comparable results in others. Our method is particularly well suited for fine structures like hair, which is of great importance in practical matting applications, e.g. in film/TV production.
Trend Analysis on the Metadata of Program Comprehension Papers
Venue: arXiv cs.SE 2018
Year: 2018

As program comprehension is a vast research area, it is necessary to get an overview of its rising and falling trends. We performed an n-gram frequency analysis on titles, abstracts and keywords of 1885 articles about program comprehension from the years 2000-2014. According to this analysis, the most rising trends are feature location and open source systems, the most falling ones are program slicing and legacy systems.
Superpixel Sampling Networks
Venue: arXiv cs.CV 2018
Year: 2018

Superpixels provide an efficient low/mid-level representation of image data, which greatly reduces the number of image primitives for subsequent vision tasks. Existing superpixel algorithms are not differentiable, making them difficult to integrate into otherwise end-to-end trainable deep neural networks. We develop a new differentiable model for superpixel sampling that leverages deep networks for learning superpixel segmentation. The resulting "Superpixel Sampling Network" (SSN) is end-to-end trainable, which allows learning task-specific superpixels with flexible loss functions and has fast runtime. Extensive experimental analysis indicates that SSNs not only outperform existing superpixel algorithms on traditional segmentation benchmarks, but can also learn superpixels for other tasks. In addition, SSNs can be easily integrated into downstream deep networks resulting in performance improvements.
Visual Display and Retrieval of Music Information
Venue: arXiv cs.IR 2018
Year: 2018

This paper describes computational methods for the visual display and analysis of music information. We provide a concise description of software, music descriptors and data visualization techniques commonly used in music information retrieval. Finally, we provide use cases where the described software, descriptors and visualizations are showcased.
On Optimizing Power Allocation For Reliable Communication over Fading Channels with Uninformed Transmitter
Venue: arXiv cs.IT 2018
Year: 2018

We investigate energy efficient packet scheduling and power allocation problem for the services which require reliable communication to guarantee a certain quality of experience (QoE). We establish links between average transmit power and reliability of data transfer, which depends on both average amount of data transfer and short term rate guarantees. We consider a slow-fading point-to-point channel without channel state information at the transmitter side (CSIT). In the absence of CSIT, the slow fading channel has an outage probability associated with every transmit power. As a function of data loss tolerance parameters, and minimum rate and peak power constraints, we formulate an optimization problem that adapts rate and power to minimize the average transmit power for the user equipment (UE). Then, a relaxed optimization problem is formulated where transmission rate is assumed to be fixed for each packet transmission. We use Markov chain to model constraints of the optimization problem. The corresponding problem is not convex for both of the formulated problems, therefore a stochastic optimization technique, namely the simulated annealing algorithm, is used to solve them. The numerical results quantify the effect of various system parameters on average transmit power and show significant energy savings when the service has less stringent requirements on timely and reliable communication.
Seeded Graph Matching via Large Neighborhood Statistics
Venue: arXiv cs.LG 2018
Year: 2018

We study a well known noisy model of the graph isomorphism problem. In this model, the goal is to perfectly recover the vertex correspondence between two edge-correlated Erdős-Rényi random graphs, with an initial seed set of correctly matched vertex pairs revealed as side information. For seeded problems, our result provides a significant improvement over previously known results. We show that it is possible to achieve the information-theoretic limit of graph sparsity in time polynomial in the number of vertices $n$. Moreover, we show the number of seeds needed for exact recovery in polynomial-time can be as low as $n^{3ε}$ in the sparse graph regime (with the average degree smaller than $n^ε$) and $Ω(\log n)$ in the dense graph regime. Our results also shed light on the unseeded problem. In particular, we give sub-exponential time algorithms for sparse models and an $n^{O(\log n)}$ algorithm for dense models for some parameters, including some that are not covered by recent results of Barak et al.
Robot Motion Planning in Learned Latent Spaces
Venue: arXiv cs.RO 2018
Year: 2018

This paper presents Latent Sampling-based Motion Planning (L-SBMP), a methodology towards computing motion plans for complex robotic systems by learning a plannable latent representation. Recent works in control of robotic systems have effectively leveraged local, low-dimensional embeddings of high-dimensional dynamics. In this paper we combine these recent advances with techniques from sampling-based motion planning (SBMP) in order to design a methodology capable of planning for high-dimensional robotic systems beyond the reach of traditional approaches (e.g., humanoids, or even systems where planning occurs in the visual space). Specifically, the learned latent space is constructed through an autoencoding network, a dynamics network, and a collision checking network, which mirror the three main algorithmic primitives of SBMP, namely state sampling, local steering, and collision checking. Notably, these networks can be trained through only raw data of the system's states and actions along with a supervising collision checker. Building upon these networks, an RRT-based algorithm is used to plan motions directly in the latent space - we refer to this exploration algorithm as Learned Latent RRT (L2RRT). This algorithm globally explores the latent space and is capable of generalizing to new environments. The overall methodology is demonstrated on two planning problems, namely a visual planning problem, whereby planning happens in the visual (pixel) space, and a humanoid robot planning problem.
Resource Orchestration of 5G Transport Networks for Vertical Industries
Venue: arXiv cs.NI 2018
Year: 2018

The future 5G transport networks are envisioned to support a variety of vertical services through network slicing and efficient orchestration over multiple administrative domains. In this paper, we propose an orchestrator architecture to support vertical services to meet their diverse resource and service requirements. We then present a system model for resource orchestration of transport networks as well as low-complexity algorithms that aim at minimizing service deployment cost and/or service latency. Importantly, the proposed model can work with any level of abstractions exposed by the underlying network or the federated domains depending on their representation of resources.
BSAS: Beetle Swarm Antennae Search Algorithm for Optimization Problems
Venue: arXiv cs.NE 2018
Year: 2018

Beetle antennae search (BAS) is an efficient meta-heuristic algorithm. However, the convergent results of BAS rely heavily on the random beetle direction in every iterations. More specifically, different random seeds may cause different optimized results. Besides, the step-size update algorithm of BAS cannot guarantee objective become smaller in iterative process. In order to solve these problems, this paper proposes Beetle Swarm Antennae Search Algorithm (BSAS) which combines swarm intelligence algorithm with feedback-based step-size update strategy. BSAS employs k beetles to find more optimal position in each moving rather than one beetle. The step-size updates only when k beetles return without better choices. Experiments are carried out on building system identification. The results reveal the efficacy of the BSAS algorithm to avoid influence of random direction of Beetle. In addition, the estimation errors decrease as the beetles number goes up.