OpenRaiser/Intern-Atlas huggingface dataset:
Secure Federated Matrix Factorization
Venue: arXiv cs.CR 2019
Year: 2019

To protect user privacy and meet law regulations, federated (machine) learning is obtaining vast interests in recent years. The key principle of federated learning is training a machine learning model without needing to know each user's personal raw private data. In this paper, we propose a secure matrix factorization framework under the federated learning setting, called FedMF. First, we design a user-level distributed matrix factorization framework where the model can be learned when each user only uploads the gradient information (instead of the raw preference data) to the server. While gradient information seems secure, we prove that it could still leak users' raw data. To this end, we enhance the distributed matrix factorization framework with homomorphic encryption. We implement the prototype of FedMF and test it with a real movie rating dataset. Results verify the feasibility of FedMF. We also discuss the challenges for applying FedMF in practice for future research.
A decentralized trust-aware collaborative filtering recommender system based on weighted items for social tagging systems
Venue: arXiv cs.SI 2019
Year: 2019

Recommender systems are used with the purpose of suggesting contents and resources to the users in a social network. These systems use ranks or tags each user assign to different resources to predict or make suggestions to users. Lately, social tagging systems, in which users can insert new contents, tag, organize, share, and search for contents are becoming more popular. These systems have a lot of valuable information, but data growth is one of its biggest challenges and this has led to the need for recommender systems that will predict what each user may like or need. One approach to the design of these systems which uses social environment of users is known as collaborative filtering (CF). One of the problems in CF systems is trustworthy of users and their tags. In this work, we consider a trust metric (which is concluded from users tagging behavior) beside the similarities to give suggestions and examine its effect on results. On the other hand, a decentralized approach is introduced which calculates similarity and trust relationships between users in a distributed manner. This causes the capability of implementing the proposed approach among all types of users with respect to different types of items, which are accessed by unique id across heterogeneous networks and environments. Finally, we show that the proposed model for calculating similarities between users reduces the size of the user-item matrix and considering trust in collaborative systems can lead to a better performance in generating suggestions.
Collaborative Broadcast in O(log log n) Rounds
Venue: arXiv cs.IT 2019
Year: 2019

We consider the multihop broadcasting problem for $n$ nodes placed uniformly at random in a disk and investigate the number of hops required to transmit a signal from the central node to all other nodes under three communication models: Unit-Disk-Graph (UDG), Signal-to-Noise-Ratio (SNR), and the wave superposition model of multiple input/multiple output (MIMO). In the MIMO model, informed nodes cooperate to produce a stronger superposed signal. We do not consider the problem of transmitting a full message nor do we consider interference. In each round, the informed senders try to deliver to other nodes the required signal strength such that the received signal can be distinguished from the noise. We assume sufficiently high node density $ρ= Ω(\log n)$. In the unit-disk graph model, broadcasting needs $O(\sqrt{n/ρ})$ rounds. In the other models, we use an Expanding Disk Broadcasting Algorithm, where in a round only triggered nodes within a certain distance from the initiator node contribute to the broadcasting operation. This algorithm achieves a broadcast in only $O(\frac{\log n}{\log ρ})$ rounds in the SNR-model. Adapted to the MIMO model, it broadcasts within $O(\log \log n - \log \log ρ)$ rounds. All bounds are asymptotically tight and hold with high probability, i.e. $1- n^{-O(1)}$.
VIPER: Volume Invariant Position-based Elastic Rods
Venue: arXiv cs.GR 2019
Year: 2019

We extend the formulation of position-based rods to include elastic volumetric deformations. We achieve this by introducing an additional degree of freedom per vertex -- isotropic scale (and its velocity). Including scale enriches the space of possible deformations, allowing the simulation of volumetric effects, such as a reduction in cross-sectional area when a rod is stretched. We rigorously derive the continuous formulation of its elastic energy potentials, and hence its associated position-based dynamics (PBD) updates to realize this model, enabling the simulation of up to 26000 DOFs at 140 Hz in our GPU implementation. We further show how rods can provide a compact alternative to tetrahedral meshes for the representation of complex muscle deformations, as well as providing a convenient representation for collision detection. This is achieved by modeling a muscle as a bundle of rods, for which we also introduce a technique to automatically convert a muscle surface mesh into a rods-bundle. Finally, we show how rods and/or bundles can be skinned to a surface mesh to drive its deformation, resulting in an alternative to cages for real-time volumetric deformation.
GluonTS: Probabilistic Time Series Models in Python
Venue: arXiv cs.LG 2019
Year: 2019

We introduce Gluon Time Series (GluonTS, available at https://gluon-ts.mxnet.io), a library for deep-learning-based time series modeling. GluonTS simplifies the development of and experimentation with time series models for common tasks such as forecasting or anomaly detection. It provides all necessary components and tools that scientists need for quickly building new models, for efficiently running and analyzing experiments and for evaluating model accuracy.
Optimizing Redundancy Levels in Master-Worker Compute Clusters for Straggler Mitigation
Venue: arXiv cs.PF 2019
Year: 2019

Runtime variability in computing systems causes some tasks to straggle and take much longer than expected to complete. These straggler tasks are known to significantly slowdown distributed computation. Job execution with speculative execution of redundant tasks has been the most widely deployed technique for mitigating the impact of stragglers, and many recent theoretical papers have studied the advantages and disadvantages of using redundancy under various system and service models. However, no clear guidelines could yet be found on when, for which jobs, and how much redundancy should be employed in Master-Worker compute clusters, which is the most widely adopted architecture in modern compute systems. We are concerned with finding a strategy for scheduling jobs with redundancy that works well in practice. This is a complex optimization problem, which we address in stages. We first use Reinforcement Learning (RL) techniques to learn good scheduling principles from realistic experience. Building on these principles, we derive a simple scheduling policy and present an approximate analysis of its performance. Specifically, we derive expressions to decide when and which jobs should be scheduled with how much redundancy. We show that policy that we devise in this way performs as good as the more complex policies that are derived by RL. Finally, we extend our approximate analysis to the case when system employs the other widely deployed remedy for stragglers, which is relaunching straggler tasks after waiting some time. We show that scheduling with redundancy significantly outperforms straggler relaunch policy when the offered load on the system is low or moderate, and performs slightly worse when the offered load is very high.
The Herbarium Challenge 2019 Dataset
Venue: arXiv cs.CV 2019
Year: 2019

Herbarium sheets are invaluable for botanical research, and considerable time and effort is spent by experts to label and identify specimens on them. In view of recent advances in computer vision and deep learning, developing an automated approach to help experts identify specimens could significantly accelerate research in this area. Whereas most existing botanical datasets comprise photos of specimens in the wild, herbarium sheets exhibit dried specimens, which poses new challenges. We present a challenge dataset of herbarium sheet images labeled by experts, with the intent of facilitating the development of automated identification techniques for this challenging scenario.
Lower Bounds for the Happy Coloring Problems
Venue: arXiv cs.DS 2019
Year: 2019

In this paper, we study the Maximum Happy Vertices and the Maximum Happy Edges problems (MHV and MHE for short). Very recently, the problems attracted a lot of attention and were studied in Agrawal '17, Aravind et al. '16, Choudhari and Reddy '18, Misra and Reddy '17. Main focus of our work is lower bounds on the computational complexity of these problems. Established lower bounds can be divided into the following groups: NP-hardness of the above guarantee parameterization, kernelization lower bounds (answering questions of Misra and Reddy '17), exponential lower bounds under the Set Cover Conjecture and the Exponential Time Hypothesis, and inapproximability results. Moreover, we present an $\mathcal{O}^*(\ell^k)$ randomized algorithm for MHV and an $\mathcal{O}^*(2^k)$ algorithm for MHE, where $\ell$ is the number of colors used and $k$ is the number of required happy vertices or edges. These algorithms cannot be improved to subexponential taking proved lower bounds into account.
Tackling Climate Change with Machine Learning
Venue: arXiv cs.CY 2019
Year: 2019

Climate change is one of the greatest challenges facing humanity, and we, as machine learning experts, may wonder how we can help. Here we describe how machine learning can be a powerful tool in reducing greenhouse gas emissions and helping society adapt to a changing climate. From smart grids to disaster management, we identify high impact problems where existing gaps can be filled by machine learning, in collaboration with other fields. Our recommendations encompass exciting research questions as well as promising business opportunities. We call on the machine learning community to join the global effort against climate change.
Factors for the Generalisation of Identity Relations by Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

Many researchers implicitly assume that neural networks learn relations and generalise them to new unseen data. It has been shown recently, however, that the generalisation of feed-forward networks fails for identity relations.The proposed solution for this problem is to create an inductive bias with Differential Rectifier (DR) units. In this work we explore various factors in the neural network architecture and learning process whether they make a difference to the generalisation on equality detection of Neural Networks without and and with DR units in early and mid fusion architectures. We find in experiments with synthetic data effects of the number of hidden layers, the activation function and the data representation. The training set size in relation to the total possible set of vectors also makes a difference. However, the accuracy never exceeds 61% without DR units at 50% chance level. DR units improve generalisation in all tasks and lead to almost perfect test accuracy in the Mid Fusion setting. Thus, DR units seem to be a promising approach for creating generalisation abilities that standard networks lack.
S3: A Spectral-Spatial Structure Loss for Pan-Sharpening Networks
Venue: arXiv cs.CV 2019
Year: 2019

Recently, many deep-learning-based pan-sharpening methods have been proposed for generating high-quality pan-sharpened (PS) satellite images. These methods focused on various types of convolutional neural network (CNN) structures, which were trained by simply minimizing a spectral loss between network outputs and the corresponding high-resolution multi-spectral (MS) target images. However, due to different sensor characteristics and acquisition times, high-resolution panchromatic (PAN) and low-resolution MS image pairs tend to have large pixel misalignments, especially for moving objects in the images. Conventional CNNs trained with only the spectral loss with these satellite image datasets often produce PS images of low visual quality including double-edge artifacts along strong edges and ghosting artifacts on moving objects. In this letter, we propose a novel loss function, called a spectral-spatial structure (S3) loss, based on the correlation maps between MS targets and PAN inputs. Our proposed S3 loss can be very effectively utilized for pan-sharpening with various types of CNN structures, resulting in significant visual improvements on PS images with suppressed artifacts.
On Longest Common Property Preserved Substring Queries
Venue: arXiv cs.DS 2019
Year: 2019

We revisit the problem of longest common property preserving substring queries introduced by~Ayad et al. (SPIRE 2018, arXiv 2018). We consider a generalized and unified on-line setting, where we are given a set $X$ of $k$ strings of total length $n$ that can be pre-processed so that, given a query string $y$ and a positive integer $k'\leq k$, we can determine the longest substring of $y$ that satisfies some specific property and is common to at least $k'$ strings in $X$. Ayad et al. considered the longest square-free substring in an on-line setting and the longest periodic and palindromic substring in an off-line setting. In this paper, we give efficient solutions in the on-line setting for finding the longest common square, periodic, palindromic, and Lyndon substrings. More precisely, we show that $X$ can be pre-processed in $O(n)$ time resulting in a data structure of $O(n)$ size that answers queries in $O(|y|\logσ)$ time and $O(1)$ working space, where $σ$ is the size of the alphabet, and the common substring must be a square, a periodic substring, a palindrome, or a Lyndon word.
Know What You Don't Know: Modeling a Pragmatic Speaker that Refers to Objects of Unknown Categories
Venue: arXiv cs.CL 2019
Year: 2019

Zero-shot learning in Language & Vision is the task of correctly labelling (or naming) objects of novel categories. Another strand of work in L&V aims at pragmatically informative rather than ``correct'' object descriptions, e.g. in reference games. We combine these lines of research and model zero-shot reference games, where a speaker needs to successfully refer to a novel object in an image. Inspired by models of "rational speech acts", we extend a neural generator to become a pragmatic speaker reasoning about uncertain object categories. As a result of this reasoning, the generator produces fewer nouns and names of distractor categories as compared to a literal speaker. We show that this conversational strategy for dealing with novel objects often improves communicative success, in terms of resolution accuracy of an automatic listener.
Illuminant Chromaticity Estimation from Interreflections
Venue: arXiv cs.CV 2019
Year: 2019

Reliable estimation of illuminant chromaticity is crucial for simulating color constancy and for white balancing digital images. However, estimating illuminant chromaticity from a single image is an ill-posed task, in general, and existing solutions typically employ a variety of assumptions and heuristics. In this paper, we present a new, physically-based, approach for estimating illuminant chromaticity from interreflections of light between diffuse surfaces. Our approach assumes that all of the direct illumination in the scene has the same chromaticity, and that at least two areas where interreflections between Lambertian surfaces occur may be detected in the image. No further assumptions or restrictions on the illuminant chromaticty or the shading in the scene are necessary. Our approach is based on representing interreflections as lines in a special 2D color space, and the chromaticity of the illuminant is estimated from the approximate intersection between two or more such lines. Experimental results are reported on a dataset of illumination and surface reflectance spectra, as well as on real images we captured. The results indicate that our approach can yield state-of-the-art results when the interreflections are significant enough to be captured by the camera.
The Consensus Number of a Cryptocurrency (Extended Version)
Venue: arXiv cs.DC 2019
Year: 2019

Many blockchain-based algorithms, such as Bitcoin, implement a decentralized asset transfer system, often referred to as a cryptocurrency. As stated in the original paper by Nakamoto, at the heart of these systems lies the problem of preventing double-spending; this is usually solved by achieving consensus on the order of transfers among the participants. In this paper, we treat the asset transfer problem as a concurrent object and determine its consensus number, showing that consensus is, in fact, not necessary to prevent double-spending. We first consider the problem as defined by Nakamoto, where only a single process---the account owner---can withdraw from each account. Safety and liveness need to be ensured for correct account owners, whereas misbehaving account owners might be unable to perform transfers. We show that the consensus number of an asset transfer object is $1$. We then consider a more general $k$-shared asset transfer object where up to $k$ processes can atomically withdraw from the same account, and show that this object has consensus number $k$. We establish our results in the context of shared memory with benign faults, allowing us to properly understand the level of difficulty of the asset transfer problem. We also translate these results in the message passing setting with Byzantine players, a model that is more relevant in practice. In this model, we describe an asynchronous Byzantine fault-tolerant asset transfer implementation that is both simpler and more efficient than state-of-the-art consensus-based solutions. Our results are applicable to both the permissioned (private) and permissionless (public) setting, as normally their differentiation is hidden by the abstractions on top of which our algorithms are based.
$c^+$GAN: Complementary Fashion Item Recommendation
Venue: arXiv cs.CV 2019
Year: 2019

We present a conditional generative adversarial model to draw realistic samples from paired fashion clothing distribution and provide real samples to pair with arbitrary fashion units. More concretely, given an image of a shirt, obtained from a fashion magazine, a brochure or even any random click on ones phone, we draw realistic samples from a parameterized conditional distribution learned as a conditional generative adversarial network ($c^+$GAN) to generate the possible pants which can go with the shirt. We start with a classical cGAN model as proposed by Mirza and Osindero [arXiv:1411.1784] and modify both the generator and discriminator to work on captured-in-the-wild data with no human alignment. We gather a dataset from web crawled data, systematically develop a method which counters the problems inherent to such data, and finally present plausible results based on our technique. We propose simple ideas to evaluate how these techniques can conquer the cognitive gap that exists when arbitrary clothing articles need to be paired with another relevant article, based on similarity of search results.
Representation Learning for Words and Entities
Venue: arXiv cs.CL 2019
Year: 2019

This thesis presents new methods for unsupervised learning of distributed representations of words and entities from text and knowledge bases. The first algorithm presented in the thesis is a multi-view algorithm for learning representations of words called Multiview Latent Semantic Analysis (MVLSA). By incorporating up to 46 different types of co-occurrence statistics for the same vocabulary of english words, I show that MVLSA outperforms other state-of-the-art word embedding models. Next, I focus on learning entity representations for search and recommendation and present the second method of this thesis, Neural Variational Set Expansion (NVSE). NVSE is also an unsupervised learning method, but it is based on the Variational Autoencoder framework. Evaluations with human annotators show that NVSE can facilitate better search and recommendation of information gathered from noisy, automatic annotation of unstructured natural language corpora. Finally, I move from unstructured data and focus on structured knowledge graphs. I present novel approaches for learning embeddings of vertices and edges in a knowledge graph that obey logical constraints.
Understanding artificial intelligence ethics and safety
Venue: arXiv cs.CY 2019
Year: 2019

A remarkable time of human promise has been ushered in by the convergence of the ever-expanding availability of big data, the soaring speed and stretch of cloud computing platforms, and the advancement of increasingly sophisticated machine learning algorithms. Innovations in AI are already leaving a mark on government by improving the provision of essential social goods and services from healthcare, education, and transportation to food supply, energy, and environmental management. These bounties are likely just the start. The prospect that progress in AI will help government to confront some of its most urgent challenges is exciting, but legitimate worries abound. As with any new and rapidly evolving technology, a steep learning curve means that mistakes and miscalculations will be made and that both unanticipated and harmful impacts will occur. This guide, written for department and delivery leads in the UK public sector and adopted by the British Government in its publication, 'Using AI in the Public Sector,' identifies the potential harms caused by AI systems and proposes concrete, operationalisable measures to counteract them. It stresses that public sector organisations can anticipate and prevent these potential harms by stewarding a culture of responsible innovation and by putting in place governance processes that support the design and implementation of ethical, fair, and safe AI systems. It also highlights the need for algorithmically supported outcomes to be interpretable by their users and made understandable to decision subjects in clear, non-technical, and accessible ways. Finally, it builds out a vision of human-centred and context-sensitive implementation that gives a central role to communication, evidence-based reasoning, situational awareness, and moral justifiability.
A JIT Compiler for Neural Network Inference
Venue: arXiv cs.LG 2019
Year: 2019

This paper describes a C++ library that compiles neural network models at runtime into machine code that performs inference. This approach in general promises to achieve the best performance possible since it is able to integrate statically known properties of the network directly into the code. In our experiments on the NAO V6 platform, it outperforms existing implementations significantly on small networks, while being inferior on large networks. The library was already part of the B-Human code release 2018, but has been extended since and is now available as a standalone version that can be integrated into any C++14 code base.
Learning Video Representations using Contrastive Bidirectional Transformer
Venue: arXiv cs.LG 2019
Year: 2019

This paper proposes a self-supervised learning approach for video features that results in significantly improved performance on downstream tasks (such as video classification, captioning and segmentation) compared to existing methods. Our method extends the BERT model for text sequences to the case of sequences of real-valued feature vectors, by replacing the softmax loss with noise contrastive estimation (NCE). We also show how to learn representations from sequences of visual features and sequences of words derived from ASR (automatic speech recognition), and show that such cross-modal training (when possible) helps even more.