OpenRaiser/Intern-Atlas huggingface dataset:
Illusion of Causality in Visualized Data
Venue: arXiv cs.HC 2019
Year: 2019

Students who eat breakfast more frequently tend to have a higher grade point average. From this data, many people might confidently state that a before-school breakfast program would lead to higher grades. This is a reasoning error, because correlation does not necessarily indicate causation -- X and Y can be correlated without one directly causing the other. While this error is pervasive, its prevalence might be amplified or mitigated by the way that the data is presented to a viewer. Across three crowdsourced experiments, we examined whether how simple data relations are presented would mitigate this reasoning error. The first experiment tested examples similar to the breakfast-GPA relation, varying in the plausibility of the causal link. We asked participants to rate their level of agreement that the relation was correlated, which they rated appropriately as high. However, participants also expressed high agreement with a causal interpretation of the data. Levels of support for the causal interpretation were not equally strong across visualization types: causality ratings were highest for text descriptions and bar graphs, but weaker for scatter plots. But is this effect driven by bar graphs aggregating data into two groups or by the visual encoding type? We isolated data aggregation versus visual encoding type and examined their individual effect on perceived causality. Overall, different visualization designs afford different cognitive reasoning affordances across the same data. High levels of data aggregation by graphs tend to be associated with higher perceived causality in data. Participants perceived line and dot visual encodings as more causal than bar encodings. Our results demonstrate how some visualization designs trigger stronger causal links while choosing others can help mitigate unwarranted perceptions of causality.
New Techniques for Graph Edit Distance Computation
Venue: arXiv cs.DS 2019
Year: 2019

Due to their capacity to encode rich structural information, labeled graphs are often used for modeling various kinds of objects such as images, molecules, and chemical compounds. If pattern recognition problems such as clustering and classification are to be solved on these domains, a (dis-)similarity measure for labeled graphs has to be defined. A widely used measure is the graph edit distance (GED), which, intuitively, is defined as the minimum amount of distortion that has to be applied to a source graph in order to transform it into a target graph. The main advantage of GED is its flexibility and sensitivity to small differences between the input graphs. Its main drawback is that it is hard to compute. In this thesis, new results and techniques for several aspects of computing GED are presented. Firstly, theoretical aspects are discussed: competing definitions of GED are harmonized, the problem of computing GED is characterized in terms of complexity, and several reductions from GED to the quadratic assignment problem (QAP) are presented. Secondly, solvers for the linear sum assignment problem with error-correction (LSAPE) are discussed. LSAPE is a generalization of the well-known linear sum assignment problem (LSAP), and has to be solved as a subproblem by many GED algorithms. In particular, a new solver is presented that efficiently reduces LSAPE to LSAP. Thirdly, exact algorithms for computing GED are presented in a systematic way, and improvements of existing algorithms as well as a new mixed integer programming (MIP) based approach are introduced. Fourthly, a detailed overview of heuristic algorithms that approximate GED via upper and lower bounds is provided, and eight new heuristics are described. Finally, a new easily extensible C++ library for exactly or approximately computing GED is presented.
Reinforcement Learning for Personalized Dialogue Management
Venue: arXiv cs.LG 2019
Year: 2019

Language systems have been of great interest to the research community and have recently reached the mass market through various assistant platforms on the web. Reinforcement Learning methods that optimize dialogue policies have seen successes in past years and have recently been extended into methods that personalize the dialogue, e.g. take the personal context of users into account. These works, however, are limited to personalization to a single user with whom they require multiple interactions and do not generalize the usage of context across users. This work introduces a problem where a generalized usage of context is relevant and proposes two Reinforcement Learning (RL)-based approaches to this problem. The first approach uses a single learner and extends the traditional POMDP formulation of dialogue state with features that describe the user context. The second approach segments users by context and then employs a learner per context. We compare these approaches in a benchmark of existing non-RL and RL-based methods in three established and one novel application domain of financial product recommendation. We compare the influence of context and training experiences on performance and find that learning approaches generally outperform a handcrafted gold standard.
Ablate, Variate, and Contemplate: Visual Analytics for Discovering Neural Architectures
Venue: arXiv cs.HC 2019
Year: 2019

Deep learning models require the configuration of many layers and parameters in order to get good results. However, there are currently few systematic guidelines for how to configure a successful model. This means model builders often have to experiment with different configurations by manually programming different architectures (which is tedious and time consuming) or rely on purely automated approaches to generate and train the architectures (which is expensive). In this paper, we present Rapid Exploration of Model Architectures and Parameters, or REMAP, a visual analytics tool that allows a model builder to discover a deep learning model quickly via exploration and rapid experimentation of neural network architectures. In REMAP, the user explores the large and complex parameter space for neural network architectures using a combination of global inspection and local experimentation. Through a visual overview of a set of models, the user identifies interesting clusters of architectures. Based on their findings, the user can run ablation and variation experiments to identify the effects of adding, removing, or replacing layers in a given architecture and generate new models accordingly. They can also handcraft new models using a simple graphical interface. As a result, a model builder can build deep learning models quickly, efficiently, and without manual programming. We inform the design of REMAP through a design study with four deep learning model builders. Through a use case, we demonstrate that REMAP allows users to discover performant neural network architectures efficiently using visual exploration and user-defined semi-automated searches through the model space.
Extract and Merge: Merging extracted humans from different images utilizing Mask R-CNN
Venue: arXiv cs.CV 2019
Year: 2019

Selecting human objects out of the various type of objects in images and merging them with other scenes is manual and day-to-day work for photo editors. Although recently Adobe photoshop released "select subject" tool which automatically selects the foreground object in an image, but still requires fine manual tweaking separately. In this work, we proposed an application utilizing Mask R-CNN (for object detection and mask segmentation) that can extract human instances from multiple images and merge them with a new background. This application does not add any overhead to Mask R-CNN, running at 5 frames per second. It can extract human instances from any number of images or videos from merging them together. We also structured the code to accept videos of different lengths as input and length of the output-video will be equal to the longest input-video. We wanted to create a simple yet effective application that can serve as a base for photo editing and do most time-consuming work automatically, so, editors can focus more on the design part. Other application could be to group people together in a single picture with a new background from different images which could not be physically together. We are showing single-person and multi-person extraction and placement in two different backgrounds. Also, we are showing a video example with single-person extraction.
Sudden Death: A New Way to Compare Recommendation Diversification
Venue: arXiv cs.IR 2019
Year: 2019

This paper describes problems with the current way we compare the diversity of different recommendation lists in offline experiments. We illustrate the problems with a case study. We propose the Sudden Death score as a new and better way of making these comparisons.
Bitcoin Security under Temporary Dishonest Majority
Venue: arXiv cs.CR 2019
Year: 2019

We prove Bitcoin is secure under temporary dishonest majority. We assume the adversary can corrupt a specific fraction of parties and also introduce crash failures, i.e., some honest participants are offline during the execution of the protocol. We demand a majority of honest online participants on expectation. We explore three different models and present the requirements for proving Bitcoin's security in all of them: we first examine a synchronous model, then extend to a bounded delay model and last we consider a synchronous model that allows message losses.
Payment Networks as Creation Games
Venue: arXiv cs.GT 2019
Year: 2019

Payment networks were introduced to address the limitation on the transaction throughput of popular blockchains. To open a payment channel one has to publish a transaction on-chain and pay the appropriate transaction fee. A transaction can be routed in the network, as long as there is a path of channels with the necessary capital. The intermediate nodes on this path can ask for a fee to forward the transaction. Hence, opening channels, although costly, can benefit a party, both by reducing the cost of the party for sending a transaction and by collecting the fees from forwarding transactions of other parties. This trade-off spawns a network creation game between the channel parties. In this work, we introduce the first game theoretic model for analyzing the network creation game on blockchain payment channels. Further, we examine various network structures (path, star, complete bipartite graph and clique) and determine for each one of them the constraints (fee value) under which they constitute a Nash equilibrium, given a fixed fee policy. Last, we show that the star is a Nash equilibrium when each channel party can freely decide the channel fee. On the other hand, we prove the complete bipartite graph can never be a Nash equilibrium, given a free fee policy.
Auditing News Curation Systems: A Case Study Examining Algorithmic and Editorial Logic in Apple News
Venue: arXiv cs.CY 2019
Year: 2019

This work presents an audit study of Apple News as a sociotechnical news curation system that exercises gatekeeping power in the media. We examine the mechanisms behind Apple News as well as the content presented in the app, outlining the social, political, and economic implications of both aspects. We focus on the Trending Stories section, which is algorithmically curated, and the Top Stories section, which is human-curated. Results from a crowdsourced audit showed minimal content personalization in the Trending Stories section, and a sock-puppet audit showed no location-based content adaptation. Finally, we perform an extended two-month data collection to compare the human-curated Top Stories section with the algorithmically curated Trending Stories section. Within these two sections, human curation outperformed algorithmic curation in several measures of source diversity, concentration, and evenness. Furthermore, algorithmic curation featured more "soft news" about celebrities and entertainment, while editorial curation featured more news about policy and international events. To our knowledge, this study provides the first data-backed characterization of Apple News in the United States.
Measuring the Clustering Strength of a Network via the Normalized Clustering Coefficient
Venue: arXiv cs.SI 2019
Year: 2019

In this paper, we propose a novel statistic of networks, the normalized clustering coefficient, which is a modified version of the clustering coefficient that is robust to network size, network density and degree heterogeneity under different network generative models. In particular, under the degree corrected block model (DCBM), the "in-out-ratio" could be inferred from the normalized clustering coefficient. Asymptotic properties of the proposed indicator are studied under three popular network generative models. The normalized clustering coefficient can also be used for networks clustering, network sampling as well as dynamic network analysis. Simulations and real data analysis are carried out to demonstrate these applications.
Single-particle cryo-electron microscopy: Mathematical theory, computational challenges, and opportunities
Venue: arXiv cs.IT 2019
Year: 2019

In recent years, an abundance of new molecular structures have been elucidated using cryo-electron microscopy (cryo-EM), largely due to advances in hardware technology and data processing techniques. Owing to these new exciting developments, cryo-EM was selected by Nature Methods as Method of the Year 2015, and the Nobel Prize in Chemistry 2017 was awarded to three pioneers in the field. The main goal of this article is to introduce the challenging and exciting computational tasks involved in reconstructing 3-D molecular structures by cryo-EM. Determining molecular structures requires a wide range of computational tools in a variety of fields, including signal processing, estimation and detection theory, high-dimensional statistics, convex and non-convex optimization, spectral algorithms, dimensionality reduction, and machine learning. The tools from these fields must be adapted to work under exceptionally challenging conditions, including extreme noise levels, the presence of missing data, and massively large datasets as large as several Terabytes. In addition, we present two statistical models: multi-reference alignment and multi-target detection, that abstract away much of the intricacies of cryo-EM, while retaining some of its essential features. Based on these abstractions, we discuss some recent intriguing results in the mathematical theory of cryo-EM, and delineate relations with group theory, invariant theory, and information theory.
ReConstructor: A Scalable Constructive Visualization Tool
Venue: arXiv cs.HC 2019
Year: 2019

Constructive approaches to visualization authoring have been shown to offer advantages such as providing options for flexible outputs, scaffolding and ideation of new data mappings, personalized exploration of data, as well as supporting data understanding and literacy. However, visualization authoring tools based on a constructive approach do not scale well to larger datasets. As construction often involves manipulating small pieces of data and visuals, it requires a significant amount of time, effort, and repetitive steps. We present ReConstructor, an authoring tool in which a visualization is constructed by instantiating its structural and functional components through four interaction elements (objects, modifiers, activators, and tools). This design preserves most of the benefits of a constructive process while avoiding scalability issues by allowing designers to propagate individual mapping steps to all the elements of a visualization. We also discuss the perceived benefits of our approach and propose avenues for future research in this area.
Neural Architecture based on Fuzzy Perceptual Representation For Online Multilingual Handwriting Recognition
Venue: arXiv cs.CV 2019
Year: 2019

Due to the omnipresence of mobile devices, online handwritten scripts have become the most important feeding input to smartphones and tablet devices. To increase online handwriting recognition performance, deeper neural networks have extensively been used. In this context, our paper handles the problem of online handwritten script recognition based on extraction features system and deep approach system for sequences classification. Many solutions have appeared in order to facilitate the recognition of handwriting. Accordingly, we used an existent method and combined with new classifiers in order to get a flexible system. Good results are achieved compared to online characters and words recognition system on Latin and Arabic scripts. The performance of our two proposed systems is assessed by using five databases. Indeed, the recognition rate exceeds 98%.
Merging variables: one technique of search in pseudo-Boolean optimization
Venue: arXiv cs.NE 2019
Year: 2019

In the present paper we describe new heuristic technique, which can be applied to the optimization of pseudo-Boolean functions including Black-Box functions. This technique is based on a simple procedure which consists in transition from the optimization problem over Boolean hypercube to the optimization problem of auxiliary function in a specially constructed metric space. It is shown that there is a natural connection between the points of the original Boolean hypercube and points from the new metric space. For the Boolean hypercube with fixed dimension it is possible to construct a number of such metric spaces. The proposed technique can be considered as a special case of Variable Neighborhood Search, which is focused on pseudo-Boolean optimization. Preliminary computational results show high efficiency of the proposed technique on some reasonably hard problems. Also it is shown that the described technique in combination with the well-known (1+1)-Evolutionary Algorithm allows to decrease the upper bound on the runtime of this algorithm for arbitrary pseudo-Boolean functions.
A Visual Technique to Analyze Flow of Information in a Machine Learning System
Venue: arXiv cs.LG 2019
Year: 2019

Machine learning (ML) algorithms and machine learning based software systems implicitly or explicitly involve complex flow of information between various entities such as training data, feature space, validation set and results. Understanding the statistical distribution of such information and how they flow from one entity to another influence the operation and correctness of such systems, especially in large-scale applications that perform classification or prediction in real time. In this paper, we propose a visual approach to understand and analyze flow of information during model training and serving phases. We build the visualizations using a technique called Sankey Diagram - conventionally used to understand data flow among sets - to address various use cases of in a machine learning system. We demonstrate how the proposed technique, tweaked and twisted to suit a classification problem, can play a critical role in better understanding of the training data, the features, and the classifier performance. We also discuss how this technique enables diagnostic analysis of model predictions and comparative analysis of predictions from multiple classifiers. The proposed concept is illustrated with the example of categorization of millions of products in the e-commerce domain - a multi-class hierarchical classification problem.
The Technical Debt Dataset
Venue: arXiv cs.SE 2019
Year: 2019

Technical Debt analysis is increasing in popularity as nowadays researchers and industry are adopting various tools for static code analysis to evaluate the quality of their code. Despite this, empirical studies on software projects are expensive because of the time needed to analyze the projects. In addition, the results are difficult to compare as studies commonly consider different projects. In this work, we propose the Technical Debt Dataset, a curated set of project measurement data from 33 Java projects from the Apache Software Foundation. In the Technical Debt Dataset, we analyzed all commits from separately defined time frames with SonarQube to collect Technical Debt information and with Ptidej to detect code smells. Moreover, we extracted all available commit information from the git logs, the refactoring applied with Refactoring Miner, and fault information reported in the issue trackers (Jira). Using this information, we executed the SZZ algorithm to identify the fault-inducing and -fixing commits. We analyzed 78K commits from the selected 33 projects, detecting 1.8M SonarQube issues, 38K code smells, 28K faults and 57K refactorings. The project analysis took more than 200 days. In this paper, we describe the data retrieval pipeline together with the tools used for the analysis. The dataset is made available through CSV files and an SQLite database to facilitate queries on the data. The Technical Debt Dataset aims to open up diverse opportunities for Technical Debt research, enabling researchers to compare results on common projects.
Competitive Online Search Trees on Trees
Venue: arXiv cs.DS 2019
Year: 2019

We consider the design of adaptive data structures for searching elements of a tree-structured space. We use a natural generalization of the rotation-based online binary search tree model in which the underlying search space is the set of vertices of a tree. This model is based on a simple structure for decomposing graphs, previously known under several names including elimination trees, vertex rankings, and tubings. The model is equivalent to the classical binary search tree model exactly when the underlying tree is a path. We describe an online $O(\log \log n)$-competitive search tree data structure in this model, matching the best known competitive ratio of binary search trees. Our method is inspired by Tango trees, an online binary search tree algorithm, but critically needs several new notions including one which we call Steiner-closed search trees, which may be of independent interest. Moreover our technique is based on a novel use of two levels of decomposition, first from search space to a set of Steiner-closed trees, and secondly from these trees into paths.
A tutorial-driven introduction to the parallel finite element library FEMPAR v1.0.0
Venue: arXiv cs.MS 2019
Year: 2019

This work is a user guide to the FEMPAR scientific software library. FEMPAR is an open-source object-oriented framework for the simulation of partial differential equations (PDEs) using finite element methods on distributed-memory platforms. It provides a rich set of tools for numerical discretization and built-in scalable solvers for the resulting linear systems of equations. An application expert that wants to simulate a PDE-governed problem has to extend the framework with a description of the weak form of the PDE at hand (and additional perturbation terms for non-conforming approximations). We show how to use the library by going through three different tutorials. The first tutorial simulates a linear PDE (Poisson equation) in a serial environment for a structured mesh using both continuous and discontinuous Galerkin finite element methods. The second tutorial extends it with adaptive mesh refinement on octree meshes. The third tutorial is a distributed-memory version of the previous one that combines a scalable octree handler and a scalable domain decomposition solver. The exposition is restricted to linear PDEs and simple geometries to keep it concise. The interested user can dive into more tutorials available in the FEMPAR public repository to learn about further capabilities of the library, e.g., nonlinear PDEs and nonlinear solvers, time integration, multi-field PDEs, block preconditioning, or unstructured mesh handling.