OpenRaiser/Intern-Atlas huggingface dataset:
Correlation Clustering Generalized
Venue: arXiv cs.CC 2018
Year: 2018

We present new results for LambdaCC and MotifCC, two recently introduced variants of the well-studied correlation clustering problem. Both variants are motivated by applications to network analysis and community detection, and have non-trivial approximation algorithms. We first show that the standard linear programming relaxation of LambdaCC has a $Θ(\log n)$ integrality gap for a certain choice of the parameter $λ$. This sheds light on previous challenges encountered in obtaining parameter-independent approximation results for LambdaCC. We generalize a previous constant-factor algorithm to provide the best results, from the LP-rounding approach, for an extended range of $λ$. MotifCC generalizes correlation clustering to the hypergraph setting. In the case of hyperedges of degree $3$ with weights satisfying probability constraints, we improve the best approximation factor from $9$ to $8$. We show that in general our algorithm gives a $4(k-1)$ approximation when hyperedges have maximum degree $k$ and probability weights. We additionally present approximation results for LambdaCC and MotifCC where we restrict to forming only two clusters.
Regional Seismic Information Entropy for Detecting Precursors of Earthquake Activation
Venue: arXiv cs.CE 2018
Year: 2018

Here a method is presented for detecting precursors of earthquakes from time series data on earthquakes in a target region. Regional Entropy of Seismic Information, a quantity representing the average influence of an earthquake in the target region to the diversity of clusters to which earthquakes distribute, is introduced. Based on a rough qualitative model of the dynamics of land crust, it is hypothesized that the saturation after the increase in the Regional Entropy of Seismic Information precedes the activation of earthquakes. On the open earthquake catalog, this hypothesis is validated. This temporal change turned out to correlate more with the activation of earthquakes in Japanese regions, by one to two years precedence, than the compared baseline methods.
Information Diffusion Power of Political Party Twitter Accounts During Japan's 2017 Election
Venue: arXiv cs.SI 2018
Year: 2018

In modern election campaigns, political parties utilize social media to advertise their policies and candidates and to communicate to electorates. In Japan's latest general election in 2017, the 48th general election for the Lower House, social media, especially Twitter, was actively used. In this paper, we perform a detailed analysis of social graphs and users who retweeted tweets of political parties during the election. Our aim is to obtain accurate information regarding the diffusion power for each party rather than just the number of followers. The results indicate that a user following a user who follows a political party account tended to also follow the account. This means that it does not increase diversity because users who follow each other tend to share similar values. We also find that followers of a specific party frequently retweeted the tweets. However, since users following the user who follow a political party account are not diverse, political parties delivered the information only to a few political detachment users.
Inferring Complementary Products from Baskets and Browsing Sessions
Venue: arXiv cs.IR 2018
Year: 2018

Complementary products recommendation is an important problem in e-commerce. Such recommendations increase the average order price and the number of products in baskets. Complementary products are typically inferred from basket data. In this study, we propose the BB2vec model. The BB2vec model learns vector representations of products by analyzing jointly two types of data - Baskets and Browsing sessions (visiting web pages of products). These vector representations are used for making complementary products recommendation. The proposed model alleviates the cold start problem by delivering better recommendations for products having few or no purchases. We show that the BB2vec model has better performance than other models which use only basket data.
Confidence Inference for Focused Learning in Stereo Matching
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we present confidence inference approachin an unsupervised way in stereo matching. Deep Neu-ral Networks (DNNs) have recently been achieving state-of-the-art performance. However, it is often hard to tellwhether the trained model was making sensible predictionsor just guessing at random. To address this problem, westart from a probabilistic interpretation of theL1loss usedin stereo matching, which inherently assumes an indepen-dent and identical (aka i.i.d.) Laplacian distribution. Weshow that with the newly introduced dense confidence map,the identical assumption is relaxed. Intuitively, the vari-ance in the Laplacian distribution is large for low confidentpixels while small for high-confidence pixels. In practice,the network learns toattenuatelow-confidence pixels (e.g.,noisy input, occlusions, featureless regions) andfocusonhigh-confidence pixels. Moreover, it can be observed fromexperiments that the focused learning is very helpful in find-ing a better convergence state of the trained model, reduc-ing over-fitting on a given dataset.
PhotoShape: Photorealistic Materials for Large-Scale Shape Collections
Venue: arXiv cs.GR 2018
Year: 2018

Existing online 3D shape repositories contain thousands of 3D models but lack photorealistic appearance. We present an approach to automatically assign high-quality, realistic appearance models to large scale 3D shape collections. The key idea is to jointly leverage three types of online data -- shape collections, material collections, and photo collections, using the photos as reference to guide assignment of materials to shapes. By generating a large number of synthetic renderings, we train a convolutional neural network to classify materials in real photos, and employ 3D-2D alignment techniques to transfer materials to different parts of each shape model. Our system produces photorealistic, relightable, 3D shapes (PhotoShapes).
Gathering by Repulsion
Venue: arXiv cs.CG 2018
Year: 2018

We consider a repulsion actuator located in an $n$-sided convex environment full of point particles. When the actuator is activated, all the particles move away from the actuator. We study the problem of gathering all the particles to a point. We give an $O(n^2)$ time algorithm to compute all the actuator locations that gather the particles to one point with one activation, and an $O(n)$ time algorithm to find a single such actuator location if one exists. We then provide an $O(n)$ time algorithm to place the optimal number of actuators whose sequential activation results in the gathering of the particles when such a placement exists.
Effects of Storage Heterogeneity in Distributed Cache Systems
Venue: arXiv cs.IT 2018
Year: 2018

In this work, we focus on distributed cache systems with non-uniform storage capacity across caches. We compare the performance of our system with the performance of a system with the same cumulative storage distributed evenly across the caches. We characterize the extent to which the performance of the distributed cache system deteriorates due to storage heterogeneity. The key takeaway from this work is that the effects of heterogeneity in the storage capabilities depend heavily on the popularity profile of the contents being cached and delivered. We analytically show that compared to the case where contents popularity is comparable across contents, lopsided popularity profiles are more tolerant to heterogeneity in storage capabilities. We validate our theoretical results via simulations.
Performance and sensitivities of home detection from mobile phone data
Venue: arXiv cs.CY 2018
Year: 2018

Large-scale location based traces, such as mobile phone data, have been identified as a promising data source to complement or even enrich official statistics. In many cases, a prerequisite step to deploy the massively gathered data is the detection of home location from individual users. The problem is that little research exists on the validation (comparison with ground truth datasets) or the uncertainty estimation of home detection methods, not at individual user level, nor at nation-wide levels. In this paper, we present an extensive empirical analysis of home detection methods when performed on a nation-wide mobile phone dataset from France. We analyze the validity of 9 different Home Detection Algorithms (HDAs), and we assess different sources of uncertainty. Based on 225 different set-ups for the home detection of around 18 million users we discuss different measures for validation and investigate sensitivity to user choices such as HDA parameter choice and observation period restriction. Our findings show that nation-wide performance of home detection is moderate at best, with correlations to ground truth maximizing at 0.60 only. Additionally, we show that time and duration of observation have a clear effect on performance, and that the effect of HDA criteria and parameter choice are rather small compared to other uncertainties. Our findings and discussion offer welcoming insights to other practitioners who want to apply home detection on similar datasets, or who are in need of an assessment of the challenges and uncertainties related to mobilizing mobile phone data for official statistics.
GPU Accelerated Similarity Self-Join for Multi-Dimensional Data
Venue: arXiv cs.DC 2018
Year: 2018

The self-join finds all objects in a dataset that are within a search distance, epsilon, of each other; therefore, the self-join is a building block of many algorithms. We advance a GPU-accelerated self-join algorithm targeted towards high dimensional data. The massive parallelism afforded by the GPU and high aggregate memory bandwidth makes the architecture well-suited for data-intensive workloads. We leverage a grid-based, GPU-tailored index to perform range queries. We propose the following optimizations: (i) a trade-off between candidate set filtering and index search overhead by exploiting properties of the index; (ii) reordering the data based on variance in each dimension to improve the filtering power of the index; and (iii) a pruning method for reducing the number of expensive distance calculations. Across most scenarios on real-world and synthetic datasets, our algorithm outperforms the parallel state-of-the-art approach. Exascale systems are converging on heterogeneous distributed-memory architectures. We show that an entity partitioning method can be utilized to achieve a balanced workload, and thus good scalability for multi-GPU or distributed-memory self-joins.
Satellite Imagery Multiscale Rapid Detection with Windowed Networks
Venue: arXiv cs.CV 2018
Year: 2018

Detecting small objects over large areas remains a significant challenge in satellite imagery analytics. Among the challenges is the sheer number of pixels and geographical extent per image: a single DigitalGlobe satellite image encompasses over 64 km2 and over 250 million pixels. Another challenge is that objects of interest are often minuscule (~pixels in extent even for the highest resolution imagery), which complicates traditional computer vision techniques. To address these issues, we propose a pipeline (SIMRDWN) that evaluates satellite images of arbitrarily large size at native resolution at a rate of > 0.2 km2/s. Building upon the tensorflow object detection API paper, this pipeline offers a unified approach to multiple object detection frameworks that can run inference on images of arbitrary size. The SIMRDWN pipeline includes a modified version of YOLO (known as YOLT), along with the models of the tensorflow object detection API: SSD, Faster R-CNN, and R-FCN. The proposed approach allows comparison of the performance of these four frameworks, and can rapidly detect objects of vastly different scales with relatively little training data over multiple sensors. For objects of very different scales (e.g. airplanes versus airports) we find that using two different detectors at different scales is very effective with negligible runtime cost.We evaluate large test images at native resolution and find mAP scores of 0.2 to 0.8 for vehicle localization, with the YOLT architecture achieving both the highest mAP and fastest inference speed.
Learning through Probing: a decentralized reinforcement learning architecture for social dilemmas
Venue: arXiv cs.MA 2018
Year: 2018

Multi-agent reinforcement learning has received significant interest in recent years notably due to the advancements made in deep reinforcement learning which have allowed for the developments of new architectures and learning algorithms. Using social dilemmas as the training ground, we present a novel learning architecture, Learning through Probing (LTP), where agents utilize a probing mechanism to incorporate how their opponent's behavior changes when an agent takes an action. We use distinct training phases and adjust rewards according to the overall outcome of the experiences accounting for changes to the opponents behavior. We introduce a parameter eta to determine the significance of these future changes to opponent behavior. When applied to the Iterated Prisoner's Dilemma (IPD), LTP agents demonstrate that they can learn to cooperate with each other, achieving higher average cumulative rewards than other reinforcement learning methods while also maintaining good performance in playing against static agents that are present in Axelrod tournaments. We compare this method with traditional reinforcement learning algorithms and agent-tracking techniques to highlight key differences and potential applications. We also draw attention to the differences between solving games and societal-like interactions and analyze the training of Q-learning agents in makeshift societies. This is to emphasize how cooperation may emerge in societies and demonstrate this using environments where interactions with opponents are determined through a random encounter format of the IPD.
Using Neural Networks to Generate Information Maps for Mobile Sensors
Venue: arXiv cs.RO 2018
Year: 2018

Target localization is a critical task for mobile sensors and has many applications. However, generating informative trajectories for these sensors is a challenging research problem. A common method uses information maps that estimate the value of taking measurements from any point in the sensor state space. These information maps are used to generate trajectories; for example, a trajectory might be designed so its distribution of measurements matches the distribution of the information map. Regardless of the trajectory generation method, generating information maps as new observations are made is critical. However, it can be challenging to compute these maps in real-time. We propose using convolutional neural networks to generate information maps from a target estimate and sensor model in real-time. Simulations show that maps are accurately rendered while offering orders of magnitude reduction in computation time.
Learning short-term past as predictor of human behavior in commercial buildings
Venue: arXiv cs.CY 2018
Year: 2018

This paper addresses the question of identifying the time-window in short-term past from which the information regarding the future occupant's window opening actions and resulting window states in buildings can be predicted. The addressed sequence duration was in the range between 30 and 240 time-steps of indoor climate data, where the applied temporal discretization was one minute. For that purpose, a deep neural network is trained to predict the window states, where the input sequence duration is handled as an additional hyperparameter. Eventually, the relationship between the prediction accuracy and the time-lag of the predicted window state in future is analyzed. The results pointed out, that the optimal predictive performance was achieved for the case where 60 time-steps of the indoor climate data were used as input. Additionally, the results showed that very long sequences (120-240 time-steps) could be addressed efficiently, given the right hyperprameters. Hence, the use of the memory over previous hours of high-resolution indoor climate data did not improve the predictive performance, when compared to the case where 30/60 minutes indoor sequences were used. The analysis of the prediction accuracy in the form of F1 score for the different time-lag of future window states dropped from 0.51 to 0.27, when shifting the prediction target from 10 to 60 minutes in future.
Negative Impact and Probable Management Policy of E-Waste in Bangladesh
Venue: arXiv cs.CY 2018
Year: 2018

Due to the wider usage of electrical and electronic products throughout the country, Electronic waste (E-waste) is growing and creating problems. E-waste contains toxic materials which may cause severe health risk and environmental damage. Bangladesh produces almost 2.7 million metric tons of E-waste per year and stays on high risk. This paper indicates the problem and suggests proper management of E-waste.
Programming at Exascale: Challenges and Innovations
Venue: arXiv cs.DC 2018
Year: 2018

Supercomputers become faster as hardware and software technologies continue to evolve. Current supercomputers are capable of 1015 floating point operations per second (FLOPS) that called Petascale system. The High Performance Computer (HPC) community is Looking forward to the system with capability of 1018 (FLOPS) that is called Exascale. Having a system to thousand times faster than the previous one produces challenges to the high performance computer (HPC) community. These challenges require innovation in software and hardware. In this paper, the challenges posed for programming at Exascale systems are reviewed and the developments in the main programming models and systems are surveyed.
Personalized Education at Scale
Venue: arXiv cs.CY 2018
Year: 2018

Tailoring the presentation of information to the needs of individual students leads to massive gains in student outcomes~\cite{bloom19842}. This finding is likely due to the fact that different students learn differently, perhaps as a result of variation in ability, interest or other factors~\cite{schiefele1992interest}. Adapting presentations to the educational needs of an individual has traditionally been the domain of experts, making it expensive and logistically challenging to do at scale, and also leading to inequity in educational outcomes. Increased course sizes and large MOOC enrollments provide an unprecedented access to student data. We propose that emerging technologies in reinforcement learning (RL), as well as semi-supervised learning, natural language processing, and computer vision are critical to leveraging this data to provide personalized education at scale.
On Bioelectric Algorithms: A Novel Application of Theoretical Computer Science to Core Problems in Developmental Biology
Venue: arXiv cs.DC 2018
Year: 2018

Cellular bioelectricity describes the biological phenomenon in which cells in living tissue generate and maintain patterns of voltage gradients induced by differing concentrations of charged ions. A growing body of research suggests that bioelectric patterns represent an ancient system that plays a key role in guiding many important developmental processes including tissue regeneration, tumor suppression, and embryogenesis. Understanding the relationship between high-level bioelectric patterns and low-level biochemical processes might also enable powerful new forms of synthetic biology. A key open question in this area is understanding how a collection of cells, interacting with each other and the extracellular environment only through simple ligand bindings and ion fluxes, can compute non-trivial patterns and perform non-trivial information processing tasks. The standard approach to this question is to model a given bioelectrical network as a system of differential equations and then explore its behavior using simulation techniques. In this paper, we propose applying a computational approach. In more detail, we present the cellular bioelectric model (CBM), a new computational model that captures the primary capabilities and constraints of bioelectric interactions between cells and their environment. We use this model to investigate several important topics in cellular bioelectricity, including symmetry breaking and information processing. Among other results, we describe and analyze a basic bioelectric strategy the efficiently stabilizes arbitrary cell networks into maximal independent sets (a structure known to play a role in the nervous system development of flys), and prove cells in our model are Turing complete in their ability to process information encoded in their initial voltage potential.
An extensible cluster-graph taxonomy for open set sound scene analysis
Venue: arXiv cs.SD 2018
Year: 2018

We present a new extensible and divisible taxonomy for open set sound scene analysis. This new model allows complex scene analysis with tangible descriptors and perception labels. Its novel structure is a cluster graph such that each cluster (or subset) can stand alone for targeted analyses such as office sound event detection, whilst maintaining integrity over the whole graph (superset) of labels. The key design benefit is its extensibility as new labels are needed during new data capture. Furthermore, datasets which use the same taxonomy are easily augmented, saving future data collection effort. We balance the details needed for complex scene analysis with avoiding 'the taxonomy of everything' with our framework to ensure no duplicity in the superset of labels and demonstrate this with DCASE challenge classifications.
General-purpose Declarative Inductive Programming with Domain-Specific Background Knowledge for Data Wrangling Automation
Venue: arXiv cs.AI 2018
Year: 2018

Given one or two examples, humans are good at understanding how to solve a problem independently of its domain, because they are able to detect what the problem is and to choose the appropriate background knowledge according to the context. For instance, presented with the string "8/17/2017" to be transformed to "17th of August of 2017", humans will process this in two steps: (1) they recognise that it is a date and (2) they map the date to the 17th of August of 2017. Inductive Programming (IP) aims at learning declarative (functional or logic) programs from examples. Two key advantages of IP are the use of background knowledge and the ability to synthesise programs from a few input/output examples (as humans do). In this paper we propose to use IP as a means for automating repetitive data manipulation tasks, frequently presented during the process of {\em data wrangling} in many data manipulation problems. Here we show that with the use of general-purpose declarative (programming) languages jointly with generic IP systems and the definition of domain-specific knowledge, many specific data wrangling problems from different application domains can be automatically solved from very few examples. We also propose an integrated benchmark for data wrangling, which we share publicly for the community.
Convex partial transversals of planar regions
Venue: arXiv cs.CG 2018
Year: 2018

We consider the problem of testing, for a given set of planar regions $\cal R$ and an integer $k$, whether there exists a convex shape whose boundary intersects at least $k$ regions of $\cal R$. We provide a polynomial time algorithm for the case where the regions are disjoint line segments with a constant number of orientations. On the other hand, we show that the problem is NP-hard when the regions are intersecting axis-aligned rectangles or 3-oriented line segments. For several natural intermediate classes of shapes (arbitrary disjoint segments, intersecting 2-oriented segments) the problem remains open.