OpenRaiser/Intern-Atlas huggingface dataset:
Combinatorial Sleeping Bandits with Fairness Constraints
Venue: arXiv cs.LG 2019
Year: 2019

The multi-armed bandit (MAB) model has been widely adopted for studying many practical optimization problems (network resource allocation, ad placement, crowdsourcing, etc.) with unknown parameters. The goal of the player here is to maximize the cumulative reward in the face of uncertainty. However, the basic MAB model neglects several important factors of the system in many real-world applications, where multiple arms can be simultaneously played and an arm could sometimes be "sleeping". Besides, ensuring fairness is also a key design concern in practice. To that end, we propose a new Combinatorial Sleeping MAB model with Fairness constraints, called CSMAB-F, aiming to address the aforementioned crucial modeling issues. The objective is now to maximize the reward while satisfying the fairness requirement of a minimum selection fraction for each individual arm. To tackle this new problem, we extend an online learning algorithm, UCB, to deal with a critical tradeoff between exploitation and exploration and employ the virtual queue technique to properly handle the fairness constraints. By carefully integrating these two techniques, we develop a new algorithm, called Learning with Fairness Guarantee (LFG), for the CSMAB-F problem. Further, we rigorously prove that not only LFG is feasibility-optimal, but it also has a time-average regret upper bounded by $\frac{N}{2η}+\frac{β_1\sqrt{mNT\log{T}}+β_2 N}{T}$, where N is the total number of arms, m is the maximum number of arms that can be simultaneously played, T is the time horizon, $β_1$ and $β_2$ are constants, and $η$ is a design parameter that we can tune. Finally, we perform extensive simulations to corroborate the effectiveness of the proposed algorithm. Interestingly, the simulation results reveal an important tradeoff between the regret and the speed of convergence to a point satisfying the fairness constraints.
Unconstrained Church-Turing thesis cannot possibly be true
Venue: arXiv cs.LO 2019
Year: 2019

The Church-Turing thesis asserts that if a partial strings-to-strings function is effectively computable then it is computable by a Turing machine. In the 1930s, when Church and Turing worked on their versions of the thesis, there was a robust notion of algorithm. These traditional algorithms are known also as classical or sequential. In the original thesis, effectively computable meant computable by an effective classical algorithm. Based on an earlier axiomatization of classical algorithms, the original thesis was proven in 2008. Since the 1930s, the notion of algorithm has changed dramatically. New species of algorithms have been and are being introduced. We argue that the generalization of the original thesis, where effectively computable means computable by an effective algorithm of any species, cannot possibly be true.
On (The Lack Of) Location Privacy in Crowdsourcing Applications
Venue: arXiv cs.CR 2019
Year: 2019

Crowdsourcing enables application developers to benefit from large and diverse datasets at a low cost. Specifically, mobile crowdsourcing (MCS) leverages users' devices as sensors to perform geo-located data collection. The collection of geolocated data raises serious privacy concerns for users. Yet, despite the large research body on location privacy-preserving mechanisms (LPPMs), MCS developers implement little to no protection for data collection or publication. To understand this mismatch, we study the performance of existing LPPMs on publicly available data from two mobile crowdsourcing projects. Our results show that well-established defenses are either not applicable or offer little protection in the MCS setting. Additionally, they have a much stronger impact on applications' utility than foreseen in the literature. This is because existing LPPMs, designed with location-based services (LBSs) in mind, are optimized for utility functions based on users' locations, while MCS utility functions depend on the values (e.g., measurements) associated with those locations. We finally outline possible research avenues to facilitate the development of new location privacy solutions that fit the needs of MCS so that the increasing number of such applications do not jeopardize their users' privacy.
Unicast-Uniprior Index Coding Problems: Minrank and Criticality
Venue: arXiv cs.IT 2019
Year: 2019

An index coding problem is called unicast-uniprior when each receiver demands a unique subset of messages while knowing another unique subset of messages apriori as side-information. In this work, we give an algorithm to compute the minrank of a unicast-uniprior problem. The proposed algorithm greatly simplifies the computation of minrank for unicast-uniprior problem settings, over the existing method whose complexity is exponential in the number of messages. First, we establish some properties that are exclusive to the fitting matrix of a unicast-uniprior problem. Further, these properties are used to lay down the algorithm that computes the minrank.
Incremental Reading for Question Answering
Venue: arXiv cs.CL 2019
Year: 2019

Any system which performs goal-directed continual learning must not only learn incrementally but process and absorb information incrementally. Such a system also has to understand when its goals have been achieved. In this paper, we consider these issues in the context of question answering. Current state-of-the-art question answering models reason over an entire passage, not incrementally. As we will show, naive approaches to incremental reading, such as restriction to unidirectional language models in the model, perform poorly. We present extensions to the DocQA [2] model to allow incremental reading without loss of accuracy. The model also jointly learns to provide the best answer given the text that is seen so far and predict whether this best-so-far answer is sufficient.
A New Inequality Related to Proofs of Strong Converse Theorems for Source or Channel Networks
Venue: arXiv cs.IT 2019
Year: 2019

In this paper we provide a new inequality useful for the proofs of strong converse theorems in the multiterminal information theory. We apply this inequality to the recent work by Tyagi and Watanabe on the strong converse theorem for the Wyner-Ziv source coding problem to obtain a new strong converse outer bound. This outer bound deviates from the Wyner-Ziv rate distortion region with the order $O\left(\frac{1}{\sqrt{n}}\right)$ on the length $n$ of source outputs.
Translation Validation for Security Properties
Venue: arXiv cs.PL 2019
Year: 2019

Secure compilation aims to build compilation chains that preserve security properties when translating programs from a source to a target language. Recent research led to the definition of secure compilation principles that, if met, guarantee that the compilation chain in hand never violates specific families of security properties. Still, to the best of our knowledge, no effective procedure is available to check if a compilation chain meets such requirements. Here, we outline our ongoing research inspired by translation validation, to effectively check one of those principles.
GridSim: A Vehicle Kinematics Engine for Deep Neuroevolutionary Control in Autonomous Driving
Venue: arXiv cs.RO 2019
Year: 2019

Current state of the art solutions in the control of an autonomous vehicle mainly use supervised end-to-end learning, or decoupled perception, planning and action pipelines. Another possible solution is deep reinforcement learning, but such a method requires that the agent interacts with its surroundings in a simulated environment. In this paper we introduce GridSim, which is an autonomous driving simulator engine running a car-like robot architecture to generate occupancy grids from simulated sensors. We use GridSim to study the performance of two deep learning approaches, deep reinforcement learning and driving behavioral learning through genetic algorithms. The deep network encodes the desired behavior in a two elements fitness function describing a maximum travel distance and a maximum forward speed, bounded to a specific interval. The algorithms are evaluated on simulated highways, curved roads and inner-city scenarios, all including different driving limitations.
Space-Efficient Computation of the LCP Array from the Burrows-Wheeler Transform
Venue: arXiv cs.DS 2019
Year: 2019

We show that the Longest Common Prefix Array of a text collection of total size n on alphabet [1, σ] can be computed from the Burrows-Wheeler transformed collection in O(n log σ) time using o(n log σ) bits of working space on top of the input and output. Our result improves (on small alphabets) and generalizes (to string collections) the previous solution from Beller et al., which required O(n) bits of extra working space. We also show how to merge the BWTs of two collections of total size n within the same time and space bounds. The procedure at the core of our algorithms can be used to enumerate suffix tree intervals in succinct space from the BWT, which is of independent interest. An engineered implementation of our first algorithm on DNA alphabet induces the LCP of a large (16 GiB) collection of short (100 bases) reads at a rate of 2.92 megabases per second using in total 1.5 Bytes per base in RAM. Our second algorithm merges the BWTs of two short-reads collections of 8 GiB each at a rate of 1.7 megabases per second and uses 0.625 Bytes per base in RAM. An extension of this algorithm that computes also the LCP array of the merged collection processes the data at a rate of 1.48 megabases per second and uses 1.625 Bytes per base in RAM.
Assessing BERT's Syntactic Abilities
Venue: arXiv cs.CL 2019
Year: 2019

I assess the extent to which the recently introduced BERT model captures English syntactic phenomena, using (1) naturally-occurring subject-verb agreement stimuli; (2) "coloreless green ideas" subject-verb agreement stimuli, in which content words in natural sentences are randomly replaced with words sharing the same part-of-speech and inflection; and (3) manually crafted stimuli for subject-verb agreement and reflexive anaphora phenomena. The BERT model performs remarkably well on all cases.
Secure Cloud-Edge Deployments, with Trust
Venue: arXiv cs.NI 2019
Year: 2019

Assessing the security level of IoT applications to be deployed to heterogeneous Cloud-Edge infrastructures operated by different providers is a non-trivial task. In this article, we present a methodology that permits to express security requirements for IoT applications, as well as infrastructure security capabilities, in a simple and declarative manner, and to automatically obtain an explainable assessment of the security level of the possible application deployments. The methodology also considers the impact of trust relations among different stakeholders using or managing Cloud-Edge infrastructures. A lifelike example is used to showcase the prototyped implementation of the methodology.
TensorFlow.js: Machine Learning for the Web and Beyond
Venue: arXiv cs.LG 2019
Year: 2019

TensorFlow.js is a library for building and executing machine learning algorithms in JavaScript. TensorFlow.js models run in a web browser and in the Node.js environment. The library is part of the TensorFlow ecosystem, providing a set of APIs that are compatible with those in Python, allowing models to be ported between the Python and JavaScript ecosystems. TensorFlow.js has empowered a new set of developers from the extensive JavaScript community to build and deploy machine learning models and enabled new classes of on-device computation. This paper describes the design, API, and implementation of TensorFlow.js, and highlights some of the impactful use cases.
Joint Spatial and Layer Attention for Convolutional Networks
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, we propose a novel approach that learns to sequentially attend to different Convolutional Neural Networks (CNN) layers (i.e., ``what'' feature abstraction to attend to) and different spatial locations of the selected feature map (i.e., ``where'') to perform the task at hand. Specifically, at each Recurrent Neural Network (RNN) step, both a CNN layer and localized spatial region within it are selected for further processing. We demonstrate the effectiveness of this approach on two computer vision tasks: (i) image-based six degree of freedom camera pose regression and (ii) indoor scene classification. Empirically, we show that combining the ``what'' and ``where'' aspects of attention improves network performance on both tasks. We evaluate our method on standard benchmarks for camera localization (Cambridge, 7-Scenes, and TUM-LSI) and for scene classification (MIT-67 Indoor Scenes). For camera localization our approach reduces the median error by 18.8\% for position and 8.2\% for orientation (averaged over all scenes), and for scene classification it improves the mean accuracy by 3.4\% over previous methods.
Artificial Intelligence for Social Good
Venue: arXiv cs.CY 2019
Year: 2019

The Computing Community Consortium (CCC), along with the White House Office of Science and Technology Policy (OSTP), and the Association for the Advancement of Artificial Intelligence (AAAI), co-sponsored a public workshop on Artificial Intelligence for Social Good on June 7th, 2016 in Washington, DC. This was one of five workshops that OSTP co-sponsored and held around the country to spur public dialogue on artificial intelligence, machine learning, and to identify challenges and opportunities related to AI. In the AI for Social Good workshop, the successful deployments and the potential use of AI in various topics that are essential for social good were discussed, including but not limited to urban computing, health, environmental sustainability, and public welfare. This report highlights each of these as well as a number of crosscutting issues.
A System Dynamics Analysis of National R&D Performance Measurement System in Korea
Venue: arXiv cs.DL 2019
Year: 2019

Peer review is one of useful and powerful performance measurement process. In Korea, it needs to increase quality of R&D performance, but bibliometric evaluation and lack of peers have opposite effect. We used system dynamics to describe Korean R&D performance measurement system and ways to increase performance quality. To meet a desired R&D performance quality, increasing fairness and quality of evaluation is needed. Size of peer pool decreased because of the specialization of R&D projects and the Sangpi process both, and it is critical to acquire both fairness and quality. Also, shortening evaluation period affect to R&D performance quality, by causing workloads increase, limiting long-term and innovative R&D projects, and decreasing evaluation quality. Previous evaluation policies do a role like micro-controlling the R&D's activities, but increasing the size of peer pool and changing evaluation period would make a change to quality and fairness of evaluation.
Trends in Demand, Growth, and Breadth in Scientific Computing Training Delivered by a High-Performance Computing Center
Venue: arXiv cs.CY 2019
Year: 2019

We analyze the changes in the training and educational efforts of the SciNet HPC Consortium, a Canadian academic High Performance Computing center, in the areas of Scientific Computing and High-Performance Computing, over the last six years. Initially, SciNet offered isolated training events on how to use HPC systems and write parallel code, but the training program now consists of a broad range of workshops and courses that users can take toward certificates in scientific computing, data science, or high-performance computing. Using data on enrollment, attendence, and certificate numbers from SciNet's education website, used by almost 1800 users so far, we extract trends on the growth, demand, and breadth of SciNet's training program. Among the results are a steady overall growth, a sharp and steady increase in the demand for data science training, and a wider participation of 'non-traditional' computing disciplines, which has motivated an increasingly broad spectrum of training offerings. Of interest is also that many of the training initiatives have evolved into courses that can be taken as part of the graduate curriculum at the University of Toronto.
An analysis of the Geodesic Distance and other comparative metrics for tree-like structures
Venue: arXiv cs.DS 2019
Year: 2019

Graphs are interesting structures: extremely useful to depict real-life problems, extremely easy to understand given a sketch, extremely complicated to represent formally, extremely complicated to compare. Phylogeny is the study of the relations between biological entities. From it, the interest in comparing tree graphs grew more than in other fields of science. Since there is no definitive way to compare them, multiple distances were formalized over the years since the early sixties, when the first effective numerical method to compare dendrograms was described. This work consists of formalizing, completing (with original work) and give a universal notation to analyze and compare the discriminatory power and time complexity of computing the thirteen here formalized metrics. We also present a new way to represent tree graphs, reach deeper in the details of the Geodesic Distance and discuss its worst-case time complexity in a suggested implementation. Our contribution ends up as a clean, valuable resource for anyone looking for an introduction to comparative metrics for tree graphs.
Set-Codes with Small Intersections and Small Discrepancies
Venue: arXiv cs.IT 2019
Year: 2019

We are concerned with the problem of designing large families of subsets over a common labeled ground set that have small pairwise intersections and the property that the maximum discrepancy of the label values within each of the sets is less than or equal to one. Our results, based on transversal designs, factorizations of packings and Latin rectangles, show that by jointly constructing the sets and labeling scheme, one can achieve optimal family sizes for many parameter choices. Probabilistic arguments akin to those used for pseudorandom generators lead to significantly suboptimal results when compared to the proposed combinatorial methods. The design problem considered is motivated by applications in molecular data storage and theoretical computer science.
Off-Policy Evaluation of Probabilistic Identity Data in Lookalike Modeling
Venue: arXiv cs.LG 2019
Year: 2019

We evaluate the impact of probabilistically-constructed digital identity data collected from Sep. to Dec. 2017 (approx.), in the context of Lookalike-targeted campaigns. The backbone of this study is a large set of probabilistically-constructed "identities", represented as small bags of cookies and mobile ad identifiers with associated metadata, that are likely all owned by the same underlying user. The identity data allows to generate "identity-based", rather than "identifier-based", user models, giving a fuller picture of the interests of the users underlying the identifiers. We employ off-policy techniques to evaluate the potential of identity-powered lookalike models without incurring the risk of allowing untested models to direct large amounts of ad spend or the large cost of performing A/B tests. We add to historical work on off-policy evaluation by noting a significant type of "finite-sample bias" that occurs for studies combining modestly-sized datasets and evaluation metrics involving rare events (e.g., conversions). We illustrate this bias using a simulation study that later informs the handling of inverse propensity weights in our analyses on real data. We demonstrate significant lift in identity-powered lookalikes versus an identity-ignorant baseline: on average ~70% lift in conversion rate. This rises to factors of ~(4-32)x for identifiers having little data themselves, but that can be inferred to belong to users with substantial data to aggregate across identifiers. This implies that identity-powered user modeling is especially important in the context of identifiers having very short lifespans (i.e., frequently churned cookies). Our work motivates and informs the use of probabilistically-constructed identities in marketing. It also deepens the canon of examples in which off-policy learning has been employed to evaluate the complex systems of the internet economy.
Metaflow: A DAG-Based Network Abstraction for Distributed Applications
Venue: arXiv cs.NI 2019
Year: 2019

In the past decade, increasingly network scheduling techniques have been proposed to boost the distributed application performance. Flow-level metrics, such as flow completion time (FCT), are based on the abstraction of flows yet they cannot capture the semantics of communication in a cluster application. Being aware of this problem, coflow is proposed as a new network abstraction. However, it is insufficient to reveal the dependencies between computation and communication. As a result, the real application performance can be hurt, especially in the absence of hard barriers. Based on the computation DAG of the application, we propose an expressive abstraction namely metaflow that resides in the middle of the two extreme points of flows and coflows. Evaluation results show that metaflow-based scheduling can outperform the coflow-based algorithm by 1.78x.
Quadratic Autoencoder (Q-AE) for Low-dose CT Denoising
Venue: arXiv cs.LG 2019
Year: 2019

Inspired by complexity and diversity of biological neurons, our group proposed quadratic neurons by replacing the inner product in current artificial neurons with a quadratic operation on input data, thereby enhancing the capability of an individual neuron. Along this direction, we are motivated to evaluate the power of quadratic neurons in popular network architectures, simulating human-like learning in the form of quadratic-neuron-based deep learning. Our prior theoretical studies have shown important merits of quadratic neurons and networks in representation, efficiency, and interpretability. In this paper, we use quadratic neurons to construct an encoder-decoder structure, referred as the quadratic autoencoder, and apply it to low-dose CT denoising. The experimental results on the Mayo low-dose CT dataset demonstrate the utility of quadratic autoencoder in terms of image denoising and model efficiency. To our best knowledge, this is the first time that the deep learning approach is implemented with a new type of neurons and demonstrates a significant potential in the medical imaging field.
Enhance the Motion Cues for Face Anti-Spoofing using CNN-LSTM Architecture
Venue: arXiv cs.CV 2019
Year: 2019

Spatio-temporal information is very important to capture the discriminative cues between genuine and fake faces from video sequences. To explore such a temporal feature, the fine-grained motions (e.g., eye blinking, mouth movements and head swing) across video frames are very critical. In this paper, we propose a joint CNN-LSTM network for face anti-spoofing, focusing on the motion cues across video frames. We first extract the high discriminative features of video frames using the conventional Convolutional Neural Network (CNN). Then we leverage Long Short-Term Memory (LSTM) with the extracted features as inputs to capture the temporal dynamics in videos. To ensure the fine-grained motions more easily to be perceived in the training process, the eulerian motion magnification is used as the preprocessing to enhance the facial expressions exhibited by individuals, and the attention mechanism is embedded in LSTM to ensure the model learn to focus selectively on the dynamic frames across the video clips. Experiments on Replay Attack and MSU-MFSD databases show that the proposed method yields state-of-the-art performance with better generalization ability compared with several other popular algorithms.