OpenRaiser/Intern-Atlas huggingface dataset:
An Intrinsically-Motivated Approach for Learning Highly Exploring and Fast Mixing Policies
Venue: arXiv cs.LG 2019
Year: 2019

What is a good exploration strategy for an agent that interacts with an environment in the absence of external rewards? Ideally, we would like to get a policy driving towards a uniform state-action visitation (highly exploring) in a minimum number of steps (fast mixing), in order to ease efficient learning of any goal-conditioned policy later on. Unfortunately, it is remarkably arduous to directly learn an optimal policy of this nature. In this paper, we propose a novel surrogate objective for learning highly exploring and fast mixing policies, which focuses on maximizing a lower bound to the entropy of the steady-state distribution induced by the policy. In particular, we introduce three novel lower bounds, that lead to as many optimization problems, that tradeoff the theoretical guarantees with computational complexity. Then, we present a model-based reinforcement learning algorithm, IDE$^{3}$AL, to learn an optimal policy according to the introduced objective. Finally, we provide an empirical evaluation of this algorithm on a set of hard-exploration tasks.
Optimal mechanisms with budget for user generated contents
Venue: arXiv cs.GT 2019
Year: 2019

In this paper, we design gross product maximization mechanisms which incentivize users to upload high-quality contents on user-generated-content (UGC) websites. We show that, the proportional division mechanism, which is widely used in practice, can perform arbitrarily bad in the worst case. The problem can be formulated using a linear program with bounded and increasing variables. We then present an $O(n\log n)$ algorithm to find the optimal mechanism, where n is the number of players.
Bayesian Optimization in Variational Latent Spaces with Dynamic Compression
Venue: arXiv cs.RO 2019
Year: 2019

Data-efficiency is crucial for autonomous robots to adapt to new tasks and environments. In this work we focus on robotics problems with a budget of only 10-20 trials. This is a very challenging setting even for data-efficient approaches like Bayesian optimization (BO), especially when optimizing higher-dimensional controllers. Simulated trajectories can be used to construct informed kernels for BO. However, previous work employed supervised ways of extracting low-dimensional features for these. We propose a model and architecture for a sequential variational autoencoder that embeds the space of simulated trajectories into a lower-dimensional space of latent paths in an unsupervised way. We further compress the search space for BO by reducing exploration in parts of the state space that are undesirable, without requiring explicit constraints on controller parameters. We validate our approach with hardware experiments on a Daisy hexapod robot and an ABB Yumi manipulator. We also present simulation experiments with further comparisons to several baselines on Daisy and two manipulators. Our experiments indicate the proposed trajectory-based kernel with dynamic compression can offer ultra data-efficient optimization.
Do Design Metrics Capture Developers Perception of Quality? An Empirical Study on Self-Affirmed Refactoring Activities
Venue: arXiv cs.SE 2019
Year: 2019

Background. Refactoring is a critical task in software maintenance and is generally performed to enforce the best design and implementation practices or to cope with design defects. Several studies attempted to detect refactoring activities through mining software repositories allowing to collect, analyze and get actionable data-driven insights about refactoring practices within software projects. Aim. We aim at identifying, among the various quality models presented in the literature, the ones that are more in-line with the developer's vision of quality optimization, when they explicitly mention that they are refactoring to improve them. Method. We extract a large corpus of design-related refactoring activities that are applied and documented by developers during their daily changes from 3,795 curated open source Java projects. In particular, we extract a large-scale corpus of structural metrics and anti-pattern enhancement changes, from which we identify 1,245 quality improvement commits with their corresponding refactoring operations, as perceived by software engineers. Thereafter, we empirically analyze the impact of these refactoring operations on a set of common state-of-the-art design quality metrics. Results. The statistical analysis of the obtained results shows that (i) a few state-of-the-art metrics are more popular than others; and (ii) some metrics are being more emphasized than others. Conclusions. We verify that there are a variety of structural metrics that can represent the internal quality attributes with different degrees of improvement and degradation of software quality. Most of the metrics that are mapped to the main quality attributes do capture developer intentions of quality improvement reported in the commit messages.
Quantifying Error in the Presence of Confounders for Causal Inference
Venue: arXiv cs.LG 2019
Year: 2019

Estimating average causal effect (ACE) is useful whenever we want to know the effect of an intervention on a given outcome. In the absence of a randomized experiment, many methods such as stratification and inverse propensity weighting have been proposed to estimate ACE. However, it is hard to know which method is optimal for a given dataset or which hyperparameters to use for a chosen method. To this end, we provide a framework to characterize the loss of a causal inference method against the true ACE, by framing causal inference as a representation learning problem. We show that many popular methods, including back-door methods can be considered as weighting or representation learning algorithms, and provide general error bounds for their causal estimates. In addition, we consider the case when unobserved variables can confound the causal estimate and extend proposed bounds using principles of robust statistics, considering confounding as contamination under the Huber contamination model. These bounds are also estimable; as an example, we provide empirical bounds for the Inverse Propensity Weighting (IPW) estimator and show how the bounds can be used to optimize the threshold of clipping extreme propensity scores. Our work provides a new way to reason about competing estimators, and opens up the potential of deriving new methods by minimizing the proposed error bounds.
The Almost-Disjoint 2-Path Decomposition Problem
Venue: arXiv cs.DM 2019
Year: 2019

We consider the problem of decomposing a given (di)graph into paths of length 2 with the additional restriction that no two such paths may have more than one vertex in common. We establish its NP-hardness by a reduction from 3-SAT, characterize (di)graph classes for which the problem can be be reduced to the Stable-set problem on claw-free graphs and describe a dynamic program for solving it for series-parallel digraphs.
Executability of Python Snippets in Stack Overflow
Venue: arXiv cs.SE 2019
Year: 2019

Online resources today contain an abundant amount of code snippets for documentation, collaboration, learning, and problem-solving purposes. Their executability in a "plug and play" manner enables us to confirm their quality and use them directly in projects. But, in practice that is often not the case due to several requirements violations or incompleteness. However, it is a difficult task to investigate the executability on a large scale due to different possible errors during the execution. We have developed a scalable framework to investigate this for SOTorrent Python snippets. We found that with minor adjustments, 27.92% of snippets are executable. The executability has not changed significantly over time. The code snippets referenced in GitHub are more likely to be directly executable. But executability does not affect the chances of the answer to be selected as the accepted answer significantly. These properties help us understand and improve the interaction of users with online resources that include code snippets.
Modelling the Socialization of Creative Agents in a Master-Apprentice Setting: The Case of Movie Title Puns
Venue: arXiv cs.CL 2019
Year: 2019

This paper presents work on modelling the social psychological aspect of socialization in the case of a computationally creative master-apprentice system. In each master-apprentice pair, the master, a genetic algorithm, is seen as a parent for its apprentice, which is an NMT based sequence-to-sequence model. The effect of different parenting styles on the creative output of each pair is in the focus of this study. This approach brings a novel view point to computational social creativity, which has mainly focused in the past on computationally creative agents being on a socially equal level, whereas our approach studies the phenomenon in the context of a social hierarchy.
Diverse Trajectory Forecasting with Determinantal Point Processes
Venue: arXiv cs.CV 2019
Year: 2019

The ability to forecast a set of likely yet diverse possible future behaviors of an agent (e.g., future trajectories of a pedestrian) is essential for safety-critical perception systems (e.g., autonomous vehicles). In particular, a set of possible future behaviors generated by the system must be diverse to account for all possible outcomes in order to take necessary safety precautions. It is not sufficient to maintain a set of the most likely future outcomes because the set may only contain perturbations of a single outcome. While generative models such as variational autoencoders (VAEs) have been shown to be a powerful tool for learning a distribution over future trajectories, randomly drawn samples from the learned implicit likelihood model may not be diverse -- the likelihood model is derived from the training data distribution and the samples will concentrate around the major mode that has most data. In this work, we propose to learn a diversity sampling function (DSF) that generates a diverse and likely set of future trajectories. The DSF maps forecasting context features to a set of latent codes which can be decoded by a generative model (e.g., VAE) into a set of diverse trajectory samples. Concretely, the process of identifying the diverse set of samples is posed as a parameter estimation of the DSF. To learn the parameters of the DSF, the diversity of the trajectory samples is evaluated by a diversity loss based on a determinantal point process (DPP). Gradient descent is performed over the DSF parameters, which in turn move the latent codes of the sample set to find an optimal diverse and likely set of trajectories. Our method is a novel application of DPPs to optimize a set of items (trajectories) in continuous space. We demonstrate the diversity of the trajectories produced by our approach on both low-dimensional 2D trajectory data and high-dimensional human motion data.
Integer Laplacian Eigenvalues of Chordal Graphs
Venue: arXiv cs.DM 2019
Year: 2019

In this paper, structural properties of chordal graphs are analysed, in order to establish a relationship between these structures and integer Laplacian eigenvalues. We present the characterization of chordal graphs with equal vertex and algebraic connectivities, by means of the vertices that compose the minimal vertex separators of the graph; we stablish a sufficient condition for the cardinality of a maximal clique to appear as an integer Laplacian eigenvalue. Finally, we review two subclasses of chordal graphs, showing for them some new properties.
Two-stream Spatiotemporal Feature for Video QA Task
Venue: arXiv cs.CV 2019
Year: 2019

Understanding the content of videos is one of the core techniques for developing various helpful applications in the real world, such as recognizing various human actions for surveillance systems or customer behavior analysis in an autonomous shop. However, understanding the content or story of the video still remains a challenging problem due to its sheer amount of data and temporal structure. In this paper, we propose a multi-channel neural network structure that adopts a two-stream network structure, which has been shown high performance in human action recognition field, and use it as a spatiotemporal video feature extractor for solving video question and answering task. We also adopt a squeeze-and-excitation structure to two-stream network structure for achieving a channel-wise attended spatiotemporal feature. For jointly modeling the spatiotemporal features from video and the textual features from the question, we design a context matching module with a level adjusting layer to remove the gap of information between visual and textual features by applying attention mechanism on joint modeling. Finally, we adopt a scoring mechanism and smoothed ranking loss objective function for selecting the correct answer from answer candidates. We evaluate our model with TVQA dataset, and our approach shows the improved result in textual only setting, but the result with visual feature shows the limitation and possibility of our approach.
On Analysis of the Bitcoin and Prism Backbone Protocols
Venue: arXiv cs.CR 2019
Year: 2019

Bitcoin is a peer-to-peer payment system proposed by Nakamoto in 2008. Properties of the bitcoin backbone protocol have been investigated in some depth: the blockchain growth property quantifies the number of blocks added to the blockchain during any time intervals; the blockchain quality property ensures the honest miners always contribute at least a certain fraction of the blockchain; the common prefix property ensures if a block is deep enough, it will eventually be adopted by all honest miners with high probability. Following the spirit of decoupling various functionalities of the blockchain, the Prism protocol is proposed to dramatically improve the throughput while maintaining the same level of security. Prior analyses of the bitcoin and Prism backbone protocols assume the lifespan of blockchain is finite. This paper presents a streamlined and strengthened analysis without the finite horizon assumption. Specifically, the results include a blockchain growth property, a blockchain quality property, and a common prefix property of the bitcoin backbone protocol, as well as the liveness and persistence of the Prism backbone protocol regardless of whether the blockchains have a infinite lifespan. We also express the properties of bitcoin and Prism backbone protocols in explicit expressions rather than order optimal results, which lead to tighter bounds and practical references for public transaction ledger protocol design.
A General Framework for Complex Network-Based Image Segmentation
Venue: arXiv cs.CV 2019
Year: 2019

With the recent advances in complex networks theory, graph-based techniques for image segmentation has attracted great attention recently. In order to segment the image into meaningful connected components, this paper proposes an image segmentation general framework using complex networks based community detection algorithms. If we consider regions as communities, using community detection algorithms directly can lead to an over-segmented image. To address this problem, we start by splitting the image into small regions using an initial segmentation. The obtained regions are used for building the complex network. To produce meaningful connected components and detect homogeneous communities, some combinations of color and texture based features are employed in order to quantify the regions similarities. To sum up, the network of regions is constructed adaptively to avoid many small regions in the image, and then, community detection algorithms are applied on the resulting adaptive similarity matrix to obtain the final segmented image. Experiments are conducted on Berkeley Segmentation Dataset and four of the most influential community detection algorithms are tested. Experimental results have shown that the proposed general framework increases the segmentation performances compared to some existing methods.
Human Body Parts Tracking: Applications to Activity Recognition
Venue: arXiv cs.CV 2019
Year: 2019

As cameras and computers became popular, the applications of computer vision techniques attracted attention enormously. One of the most important applications in the computer vision community is human activity recognition. In order to recognize human activities, we propose a human body parts tracking system that tracks human body parts such as head, torso, arms and legs in order to perform activity recognition tasks in real time. This thesis presents a real-time human body parts tracking system (i.e. HBPT) from video sequences. Our body parts model is mostly represented by body components such as legs, head, torso and arms. The body components are modeled using torso location and size which are obtained by a torso tracking method in each frame. In order to track the torso, we are using a blob tracking module to find the approximate location and size of the torso in each frame. By tracking the torso, we will be able to track other body parts based on their location with respect to the torso on the detected silhouette. In the proposed method for human body part tracking, we are also using a refining module to improve the detected silhouette by refining the foreground mask (i.e. obtained by background subtraction) in order to detect the body parts with respect to torso location and size. Having found the torso size and location, the region of each human body part on the silhouette will be modeled by a 2D-Gaussian blob in each frame in order to show its location, size and pose. The proposed approach described in this thesis tracks accurately the body parts in different illumination conditions and in the presence of partial occlusions. The proposed approach is applied to activity recognition tasks such as approaching an object, carrying an object and opening a box or suitcase.
Voxel-FPN: multi-scale voxel feature aggregation in 3D object detection from point clouds
Venue: arXiv cs.CV 2019
Year: 2019

Object detection in point cloud data is one of the key components in computer vision systems, especially for autonomous driving applications. In this work, we present Voxel-FPN, a novel one-stage 3D object detector that utilizes raw data from LIDAR sensors only. The core framework consists of an encoder network and a corresponding decoder followed by a region proposal network. Encoder extracts multi-scale voxel information in a bottom-up manner while decoder fuses multiple feature maps from various scales in a top-down way. Extensive experiments show that the proposed method has better performance on extracting features from point data and demonstrates its superiority over some baselines on the challenging KITTI-3D benchmark, obtaining good performance on both speed and accuracy in real-world scenarios.
StakeCube: Combining Sharding and Proof-of-Stake to build Fork-free Secure Permissionless Distributed Ledgers
Venue: arXiv cs.DC 2019
Year: 2019

Our work focuses on the design of a scalable permissionless blockchain in the proof-of-stake setting. In particular, we use a distributed hash table as a building block to set up randomized shards, and then leverage the sharded architecture to validate blocks in an efficient manner. We combine verifiable Byzantine agreements run by shards of stakeholders and a block validation protocol to guarantee that forks occur with negligible probability. We impose induced churn to make shards robust to eclipse attacks, and we rely on the UTXO coin model to guarantee that any stakeholder action is securely verifiable by anyone. Our protocol works against adaptive adversary, and makes no synchrony assumption beyond what is required for the byzantine agreement.
Computing sharp recovery structures for Locally Recoverable codes
Venue: arXiv cs.IT 2019
Year: 2019

A locally recoverable code is an error-correcting code such that any erasure in a single coordinate of a codeword can be recovered from a small subset of other coordinates. In this article we develop an algorithm that computes a recovery structure as concise posible for an arbitrary linear code $\mathcal{C}$ and a recovery method that realizes it. This algorithm also provides the locality and the dual distance of $\mathcal{C}$. Complexity issues are studied as well. Several examples are included.
Competitive Analysis with a Sample and the Secretary Problem
Venue: arXiv cs.DS 2019
Year: 2019

We extend the standard online worst-case model to accommodate past experience which is available to the online player in many practical scenarios. We do this by revealing a random sample of the adversarial input to the online player ahead of time. The online player competes with the expected optimal value on the part of the input that arrives online. Our model bridges between existing online stochastic models (e.g., items are drawn i.i.d. from a distribution) and the online worst-case model. We also extend in a similar manner (by revealing a sample) the online random-order model. We study the classical secretary problem in our new models. In the worst-case model we present a simple online algorithm with optimal competitive-ratio for any sample size. In the random-order model, we also give a simple online algorithm with an almost tight competitive-ratio for small sample sizes. Interestingly, we prove that for a large enough sample, no algorithm can be simultaneously optimal both in the worst-cast and random-order models.
Visualização e animação de autómatos em Ocsigen Framework
Venue: arXiv cs.FL 2019
Year: 2019

Formal Languages and Automata Theory are important foundational topics in Computer Science. Their rigorous and formal characteristics make their learning them demanding. An important support for the assimilation of concepts is the possibility of interactively visualizing concrete examples of these computational models, facilitating understanding them. The tools available are neither complete nor fully support the interactive aspect. This project aims at the development of an interactive web tool in Portuguese to help in an assisted and intuitive way to understand the concepts and algorithms in question, seeing them work step-by-step, through typical examples preloaded or built by the user (an original aspect of our platform). The tool should therefore enable the creation and edition of an automata, as well as execute the relevant classical algorithms such as word acceptance, model conversions, etc. It is also intended to visualize not only the process of construction of the automaton, but also all the steps of applying the given algorithm. This tool uses the Ocsigen Framework because it provides the development of complete and interactive web tools written in OCaml, a functional language with a strong type checking system and therefore perfect for a web page without errors. Ocsigen was also chosen because it allows the creation of dynamic pages with a singular client-server system. This article presents the first phase of the development of the project. It is already possible to create automata, check the nature of its states and verify step-by-step (with undo) the acceptance of a word.