OpenRaiser/Intern-Atlas huggingface dataset:
Recruiting Hay to Find Needles: Recursive Incentives and Innovation in Social Networks
Venue: arXiv cs.SI 2019
Year: 2019

Finding innovative solutions to complex problems is often about finding people who have access to novel information and alternative viewpoints. Research has found that most people are connected to each other through just a few degrees of separation, but successful social search is often difficult because it depends on people using their weak ties to make connections to distant social networks. Recursive incentive schemes have shown promise for social search by motivating people to use their weak ties to find distant targets, such as specific people or even weather balloons placed at undisclosed locations. Here, we report on a case study of a similar recursive incentive scheme for finding innovative ideas. Specifically, we implemented a competition to reward individuals(s) who helped refer Grand Prize winner(s) in MIT's Climate CoLab, an open innovation platform for addressing global climate change. Using data on over 78,000 CoLab members and over 36,000 people from over 100 countries who engaged with the referral contest, we find that people who are referred using this method are more likely than others to submit proposals and to submit high quality proposals. Furthermore, we find suggestive evidence that among the contributors referred via the contest, those who had more than one degree of separation from a pre-existing CoLab member were more likely to submit high quality proposals. Thus, the results from this case study are consistent the theory that people from distant networks are more likely to provide innovative solutions to complex problems. More broadly, the results suggest that rewarding indirect intermediaries in addition to final finders may promote effective social network recruitment.
Coalitional Game Framework for Content Distribution Using Device-to-device Communication
Venue: arXiv cs.IT 2019
Year: 2019

We consider a set of cellular users associated with a base station (BS) in a cellular network that employs Device-to-device (D2D) communication. A subset of the users request for some files from the BS. Now, some of the users can potentially act as relays and forward the requested files, or partitions of files, from the BS to some of the requesting users (destination nodes) over D2D links. However, this requires cooperation among the cellular users. In this paper, we seek conditions under which users have an incentive to cooperate with each other. We model the above scenario using the frameworks of cooperative game theory and stable partitions in coalitional games. We consider two different models for file transfer within a coalition: (i) Model A, in which the BS can split a file into multiple partitions and send these partitions to different relays, which multicast the partitions to the destination nodes of the coalition, and (ii) Model B, in which for each file, the BS sends the entire file to a single relay, which multicasts it to the destination nodes of the coalition. First, we explore the question of whether it is beneficial for all the cellular users to cooperate, i.e., whether the grand coalition is stable. For this we use the solution concept of core from cooperative game theory. We show that, in general, the above coalitional game under Model A may have an empty core. Next, we provide conditions under which the core is always non-empty and a D_c-stable partition always exists. Also, we show that under Model B, the problem of assigning relays to destination nodes so as to maximize the sum of utilities of all the users is NP-Complete. Finally, we show via numerical computations that a significant reduction in the energy expenditure of cellular users can be achieved via cooperation.
A Statistical Explanation of the Timing Attack on QC-MDPC Code Crypto-system
Venue: arXiv cs.CR 2019
Year: 2019

The McEliece cryptosystem based on quasi-cyclic moderate-density parity-check (QC-MDPC) codes is first purposed in 2013\cite{QCMDPC} and is considered a promising contender in the post-quantum era. Understanding its security is hence essential. Till now, the most effective attacks are the reaction attack\cite{Reaction} and the timing attack\cite{Timing}. Both of these attacks rely on the decoding performance to recover the private key. The reaction attack relies on the decoding failure rate and the timing attack relies on the iterations during decoding. However, the mechanics behind these attacks remain elusive. In this paper, a mathematical model is proposed to explain both attacks by connecting the spectrum of private key and first-layer performance of the decoder.
Hunting for supernovae articles in the universe of scientometrics
Venue: arXiv cs.DL 2019
Year: 2019

This short note records an unusual situation with some Google Scholar's profiles that imply the existence of "supernovae" articles, i.e., articles whose impact -- in terms of number of citations -- in a single year gets (almost) an order of magnitude higher than the previous year and immediate drops (and remains steady) to a very low level after the next year. We analyse the issue and resolve the situation providing an answer whether there exist supernovae articles.
Drawbacks and Proposed Solutions for Real-time Processing on Existing State-of-the-art Locality Sensitive Hashing Techniques
Venue: arXiv cs.DB 2019
Year: 2019

Nearest-neighbor query processing is a fundamental operation for many image retrieval applications. Often, images are stored and represented by high-dimensional vectors that are generated by feature-extraction algorithms. Since tree-based index structures are shown to be ineffective for high dimensional processing due to the well-known "Curse of Dimensionality", approximate nearest neighbor techniques are used for faster query processing. Locality Sensitive Hashing (LSH) is a very popular and efficient approximate nearest neighbor technique that is known for its sublinear query processing complexity and theoretical guarantees. Nowadays, with the emergence of technology, several diverse application domains require real-time high-dimensional data storing and processing capacity. Existing LSH techniques are not suitable to handle real-time data and queries. In this paper, we discuss the challenges and drawbacks of existing LSH techniques for processing real-time high-dimensional image data. Additionally, through experimental analysis, we propose improvements for existing state-of-the-art LSH techniques for efficient processing of high-dimensional image data.
Robust Named Entity Recognition with Truecasing Pretraining
Venue: arXiv cs.CL 2019
Year: 2019

Although modern named entity recognition (NER) systems show impressive performance on standard datasets, they perform poorly when presented with noisy data. In particular, capitalization is a strong signal for entities in many languages, and even state of the art models overfit to this feature, with drastically lower performance on uncapitalized text. In this work, we address the problem of robustness of NER systems in data with noisy or uncertain casing, using a pretraining objective that predicts casing in text, or a truecaser, leveraging unlabeled data. The pretrained truecaser is combined with a standard BiLSTM-CRF model for NER by appending output distributions to character embeddings. In experiments over several datasets of varying domain and casing quality, we show that our new model improves performance in uncased text, even adding value to uncased BERT embeddings. Our method achieves a new state of the art on the WNUT17 shared task dataset.
Efficient Bitmap-based Indexing and Retrieval of Similarity Search Image Queries
Venue: arXiv cs.MM 2019
Year: 2019

Finding similar images is a necessary operation in many multimedia applications. Images are often represented and stored as a set of high-dimensional features, which are extracted using localized feature extraction algorithms. Locality Sensitive Hashing is one of the most popular approximate processing techniques for finding similar points in high-dimensional spaces. Locality Sensitive Hashing (LSH) and its variants are designed to find similar points, but they are not designed to find objects (such as images, which are made up of a collection of points) efficiently. In this paper, we propose an index structure, Bitmap-Image LSH (bImageLSH), for efficient processing of high-dimensional images. Using a real dataset, we experimentally show the performance benefit of our novel design while keeping the accuracy of the image results high.
On Opacity Verification for Discrete-Event Systems
Venue: arXiv cs.FL 2019
Year: 2019

Opacity is an information flow property characterizing whether a system reveals its secret to an intruder. Verification of opacity for discrete-event systems modeled by automata is in general a hard problem. We discuss the question whether there are structural restrictions on the system models for which the opacity verification is tractable. We consider two kinds of automata models: (i) acyclic automata, and (ii) automata where all cycles are only in the form of self-loops. In some sense, these models are the simplest models of (deadlock-free) systems. Although the expressivity of such systems is weaker than the expressivity of linear temporal logic, we show that the opacity verification for these systems is still hard.
The Recurrent Processing Unit: Hardware for High Speed Machine Learning
Venue: arXiv cs.ET 2019
Year: 2019

Machine learning applications are computationally demanding and power intensive. Hardware acceleration of these software tools is a natural step being explored using various technologies. A recurrent processing unit (RPU) is fast and power-efficient hardware for machine learning under development at the University of Maryland. It is comprised of a recurrent neural network and a trainable output vector as a hardware implementation of a reservoir computer. The reservoir is currently realized on both Xilinx 7-series and Ultrascale+ ZYNQ SoCs using an autonomous Boolean network for processing and a Python-based software API. The RPU is capable of classifying up to 40M MNIST images per second with the reservoir consuming under 261mW of power. Using an array of 2048 unclocked gates with roughly 100pS transition times, we achieve about 20 TOPS and 75 TOPS/W.
Algorithmic Injustices: Towards a Relational Ethics
Venue: arXiv cs.CY 2019
Year: 2019

It has become trivial to point out how decision-making processes in various social, political and economical sphere are assisted by automated systems. Improved efficiency, the hallmark of these systems, drives the mass scale integration of automated systems into daily life. However, as a robust body of research in the area of algorithmic injustice shows, algorithmic tools embed and perpetuate societal and historical biases and injustice. In particular, a persistent recurring trend within the literature indicates that society's most vulnerable are disproportionally impacted. When algorithmic injustice and bias is brought to the fore, most of the solutions on offer 1) revolve around technical solutions and 2) do not focus centre disproportionally impacted groups. This paper zooms out and draws the bigger picture. It 1) argues that concerns surrounding algorithmic decision making and algorithmic injustice require fundamental rethinking above and beyond technical solutions, and 2) outlines a way forward in a manner that centres vulnerable groups through the lens of relational ethics.
Optimal Wireless Caching with Placement Cost
Venue: arXiv cs.IT 2019
Year: 2019

Coded caching has been shown to result in significant throughput gains, but its gains were proved only by assuming a placement phase with no transmission cost. A free placement phase is, however, an unrealistic assumption that could stand as an obstacle towards delivering the promise of coded caching. In [1], we relaxed this assumption by introducing a general caching framework that captures transmission costs for both delivery and placement phases under general assumptions on varying network architectures, memory constraints, and traffic patterns. Here, we leverage this general framework and focus on analyzing the effect of the placement communication cost on the overall throughput and the structure of the optimal caching scheme, under the assumptions of the worst case traffic pattern and unlimited memory at the end users. Interestingly, we find relevant network configurations where uncoded caching is the optimal solution.
UAV-to-UAV Communications in Cellular Networks
Venue: arXiv cs.IT 2019
Year: 2019

We consider a cellular network deployment where UAV-to-UAV (U2U) transmit-receive pairs share the same spectrum with the uplink (UL) of cellular ground users (GUEs). For this setup, we focus on analyzing and comparing the performance of two spectrum sharing mechanisms: (i) underlay, where the same time-frequency resources may be accessed by both UAVs and GUEs, resulting in mutual interference, and (ii)overlay, where the available resources are divided into orthogonal portions for U2U and GUE communications. We evaluate the coverage probability and rate of both link types and their interplay to identify the best spectrum sharing strategy. We do so through an analytical framework that embraces realistic height-dependent channel models, antenna patterns, and practical power control mechanisms. For the underlay, we find that although the presence of U2U direct communications may worsen the uplink performance of GUEs, such effect is limited as base stations receive the power-constrained UAV signals through their antenna sidelobes. In spite of this, our results lead us to conclude that in urban scenarios with a large number of UAV pairs, adopting an overlay spectrum sharing seems the most suitable approach for maintaining a minimum guaranteed rate for UAVs and a high GUE UL performance.
To Follow or not to Follow: Selective Imitation Learning from Observations
Venue: arXiv cs.RO 2019
Year: 2019

Learning from demonstrations is a useful way to transfer a skill from one agent to another. While most imitation learning methods aim to mimic an expert skill by following the demonstration step-by-step, imitating every step in the demonstration often becomes infeasible when the learner and its environment are different from the demonstration. In this paper, we propose a method that can imitate a demonstration composed solely of observations, which may not be reproducible with the current agent. Our method, dubbed selective imitation learning from observations (SILO), selects reachable states in the demonstration and learns how to reach the selected states. Our experiments on both simulated and real robot environments show that our method reliably performs a new task by following a demonstration. Videos and code are available at https://clvrai.com/silo .
Generative Teaching Networks: Accelerating Neural Architecture Search by Learning to Generate Synthetic Training Data
Venue: arXiv cs.LG 2019
Year: 2019

This paper investigates the intriguing question of whether we can create learning algorithms that automatically generate training data, learning environments, and curricula in order to help AI agents rapidly learn. We show that such algorithms are possible via Generative Teaching Networks (GTNs), a general approach that is, in theory, applicable to supervised, unsupervised, and reinforcement learning, although our experiments only focus on the supervised case. GTNs are deep neural networks that generate data and/or training environments that a learner (e.g. a freshly initialized neural network) trains on for a few SGD steps before being tested on a target task. We then differentiate through the entire learning process via meta-gradients to update the GTN parameters to improve performance on the target task. GTNs have the beneficial property that they can theoretically generate any type of data or training environment, making their potential impact large. This paper introduces GTNs, discusses their potential, and showcases that they can substantially accelerate learning. We also demonstrate a practical and exciting application of GTNs: accelerating the evaluation of candidate architectures for neural architecture search (NAS), which is rate-limited by such evaluations, enabling massive speed-ups in NAS. GTN-NAS improves the NAS state of the art, finding higher performing architectures when controlling for the search proposal mechanism. GTN-NAS also is competitive with the overall state of the art approaches, which achieve top performance while using orders of magnitude less computation than typical NAS methods. Speculating forward, GTNs may represent a first step toward the ambitious goal of algorithms that generate their own training data and, in doing so, open a variety of interesting new research questions and directions.
Community detectability and structural balance dynamics in signed networks
Venue: arXiv cs.SI 2019
Year: 2019

We investigate signed networks with community structure with respect to their spectrum and their evolution under a dynamical model of structural balance, a prominent theory of signed social networks. The spectrum of the adjacency matrix generated by a stochastic block model with two equal size communities shows detectability transitions in which the community structure becomes manifest when its signal eigenvalue appears outside the main spectral band. The spectrum also exhibits "sociality" transitions involving the homogeneous structure representing the average tie value. We derive expressions for the eigenvalues associated with the community and homogeneous structure as well as the transition boundaries, all in good agreement with numerical results. Using the stochastically-generated networks as initial conditions for a simple model of structural balance dynamics yields three outcome regimes: two hostile factions that correspond with the initial communities, two hostile factions uncorrelated with those communities, and a single harmonious faction of all nodes. The detectability transition predicts the boundary between the assortative and mixed two-faction states and the sociality transition predicts that between the mixed and harmonious states. Our results may yield insight into the dynamics of cooperation and conflict among actors with distinct social identities.
Unpaired Image Enhancement Featuring Reinforcement-Learning-Controlled Image Editing Software
Venue: arXiv cs.CV 2019
Year: 2019

This paper tackles unpaired image enhancement, a task of learning a mapping function which transforms input images into enhanced images in the absence of input-output image pairs. Our method is based on generative adversarial networks (GANs), but instead of simply generating images with a neural network, we enhance images utilizing image editing software such as Adobe Photoshop for the following three benefits: enhanced images have no artifacts, the same enhancement can be applied to larger images, and the enhancement is interpretable. To incorporate image editing software into a GAN, we propose a reinforcement learning framework where the generator works as the agent that selects the software's parameters and is rewarded when it fools the discriminator. Our framework can use high-quality non-differentiable filters present in image editing software, which enables image enhancement with high performance. We apply the proposed method to two unpaired image enhancement tasks: photo enhancement and face beautification. Our experimental results demonstrate that the proposed method achieves better performance, compared to the performances of the state-of-the-art methods based on unpaired learning.
Controlling network coordination games
Venue: arXiv cs.GT 2019
Year: 2019

We study a novel control problem in the context of network coordination games: the individuation of the smallest set of players capable of driving the system, globally, from one Nash equilibrium to another one. Our main contribution is the design of a randomized algorithm based on a time-reversible Markov chain with provable convergence garantees.
Probabilistic Software Modeling: A Data-driven Paradigm for Software Analysis
Venue: arXiv cs.SE 2019
Year: 2019

Software systems are complex, and behavioral comprehension with the increasing amount of AI components challenges traditional testing and maintenance strategies.The lack of tools and methodologies for behavioral software comprehension leaves developers to testing and debugging that work in the boundaries of known scenarios. We present Probabilistic Software Modeling (PSM), a data-driven modeling paradigm for predictive and generative methods in software engineering. PSM analyzes a program and synthesizes a network of probabilistic models that can simulate and quantify the original program's behavior. The approach extracts the type, executable, and property structure of a program and copies its topology. Each model is then optimized towards the observed runtime leading to a network that reflects the system's structure and behavior. The resulting network allows for the full spectrum of statistical inferential analysis with which rich predictive and generative applications can be built. Applications range from the visualization of states, inferential queries, test case generation, and anomaly detection up to the stochastic execution of the modeled system. In this work, we present the modeling methodologies, an empirical study of the runtime behavior of software systems, and a comprehensive study on PSM modeled systems. Results indicate that PSM is a solid foundation for structural and behavioral software comprehension applications.
Toward Fast and Optimal Robotic Pick-and-Place on a Moving Conveyor
Venue: arXiv cs.RO 2019
Year: 2019

Robotic pick-and-place (PnP) operations on moving conveyors find a wide range of industrial applications. In practice, simple greedy heuristics (e.g., prioritization based on the time to process a single object) are applied that achieve reasonable efficiency. We show analytically that, under a simplified telescoping robot model, these greedy approaches do not ensure time optimality of PnP operations. To address the shortcomings of classical solutions, we develop algorithms that compute optimal object picking sequences for a predetermined finite horizon. Employing dynamic programming techniques and additional heuristics, our methods scale to up to tens to hundreds of objects. In particular, the fast algorithms we develop come with running time guarantees, making them suitable for real-time PnP applications demanding high throughput. Extensive evaluation of our algorithmic solution over dominant industrial PnP robots used in real-world applications, i.e., Delta robots and Selective Compliance Assembly Robot Arm (SCARA) robots, shows that a typical efficiency gain of around 10-40% over greedy approaches can be realized.
The accuracy vs. coverage trade-off in patient-facing diagnosis models
Venue: arXiv cs.LG 2019
Year: 2019

A third of adults in America use the Internet to diagnose medical concerns, and online symptom checkers are increasingly part of this process. These tools are powered by diagnosis models similar to clinical decision support systems, with the primary difference being the coverage of symptoms and diagnoses. To be useful to patients and physicians, these models must have high accuracy while covering a meaningful space of symptoms and diagnoses. To the best of our knowledge, this paper is the first in studying the trade-off between the coverage of the model and its performance for diagnosis. To this end, we learn diagnosis models with different coverage from EHR data. We find a 1\% drop in top-3 accuracy for every 10 diseases added to the coverage. We also observe that complexity for these models does not affect performance, with linear models performing as well as neural networks.