OpenRaiser/Intern-Atlas huggingface dataset:
The Capacity of Private Information Retrieval with Private Side Information Under Storage Constraints
Venue: arXiv cs.IT 2018
Year: 2018

We consider the problem of private information retrieval (PIR) of a single message out of $K$ messages from $N$ replicated and non-colluding databases where a cache-enabled user (retriever) of cache-size $S$ possesses side information in the form of uncoded portions of the messages that are unknown to the databases. The identities of these side information messages need to be kept private from the databases, i.e., we consider PIR with private side information (PSI). We characterize the optimal normalized download cost for this PIR-PSI problem under the storage constraint $S$ as $D^*=1+\frac{1}{N}+\frac{1}{N^2}+\dots+\frac{1}{N^{K-1-M}}+\frac{1-r_M}{N^{K-M}}+\frac{1-r_{M-1}}{N^{K-M+1}}+\dots+\frac{1-r_1}{N^{K-1}}$, where $r_i$ is the portion of the $i$th side information message that is cached with $\sum_{i=1}^M r_i=S$. Based on this capacity result, we prove two facts: First, for a fixed memory size $S$ and a fixed number of accessible messages $M$, uniform caching achieves the lowest normalized download cost, i.e., $r_i=\frac{S}{M}$, for $i=1,\dots, M$, is optimum. Second, for a fixed memory size $S$, among all possible $K-\left \lceil{S} \right \rceil+1$ uniform caching schemes, the uniform caching scheme which caches $M=K$ messages achieves the lowest normalized download cost.
Agreement-based Learning
Venue: arXiv cs.LG 2018
Year: 2018

Model selection is a problem that has occupied machine learning researchers for a long time. Recently, its importance has become evident through applications in deep learning. We propose an agreement-based learning framework that prevents many of the pitfalls associated with model selection. It relies on coupling the training of multiple models by encouraging them to agree on their predictions while training. In contrast with other model selection and combination approaches used in machine learning, the proposed framework is inspired by human learning. We also propose a learning algorithm defined within this framework which manages to significantly outperform alternatives in practice, and whose performance improves further with the availability of unlabeled data. Finally, we describe a number of potential directions for developing more flexible agreement-based learning algorithms.
Relational inductive biases, deep learning, and graph networks
Venue: arXiv cs.LG 2018
Year: 2018

Artificial intelligence (AI) has undergone a renaissance recently, making major progress in key domains such as vision, language, control, and decision-making. This has been due, in part, to cheap data and cheap compute resources, which have fit the natural strengths of deep learning. However, many defining characteristics of human intelligence, which developed under much different pressures, remain out of reach for current approaches. In particular, generalizing beyond one's experiences--a hallmark of human intelligence from infancy--remains a formidable challenge for modern AI. The following is part position paper, part review, and part unification. We argue that combinatorial generalization must be a top priority for AI to achieve human-like abilities, and that structured representations and computations are key to realizing this objective. Just as biology uses nature and nurture cooperatively, we reject the false choice between "hand-engineering" and "end-to-end" learning, and instead advocate for an approach which benefits from their complementary strengths. We explore how using relational inductive biases within deep learning architectures can facilitate learning about entities, relations, and rules for composing them. We present a new building block for the AI toolkit with a strong relational inductive bias--the graph network--which generalizes and extends various approaches for neural networks that operate on graphs, and provides a straightforward interface for manipulating structured knowledge and producing structured behaviors. We discuss how graph networks can support relational reasoning and combinatorial generalization, laying the foundation for more sophisticated, interpretable, and flexible patterns of reasoning. As a companion to this paper, we have released an open-source software library for building graph networks, with demonstrations of how to use them in practice.
Equivalence Between Wasserstein and Value-Aware Loss for Model-based Reinforcement Learning
Venue: arXiv cs.LG 2018
Year: 2018

Learning a generative model is a key component of model-based reinforcement learning. Though learning a good model in the tabular setting is a simple task, learning a useful model in the approximate setting is challenging. In this context, an important question is the loss function used for model learning as varying the loss function can have a remarkable impact on effectiveness of planning. Recently Farahmand et al. (2017) proposed a value-aware model learning (VAML) objective that captures the structure of value function during model learning. Using tools from Asadi et al. (2018), we show that minimizing the VAML objective is in fact equivalent to minimizing the Wasserstein metric. This equivalence improves our understanding of value-aware models, and also creates a theoretical foundation for applications of Wasserstein in model-based reinforcement~learning.
Data-driven Localization and Estimation of Disturbance in the Interconnected Power System
Venue: arXiv cs.LG 2018
Year: 2018

Identifying the location of a disturbance and its magnitude is an important component for stable operation of power systems. We study the problem of localizing and estimating a disturbance in the interconnected power system. We take a model-free approach to this problem by using frequency data from generators. Specifically, we develop a logistic regression based method for localization and a linear regression based method for estimation of the magnitude of disturbance. Our model-free approach does not require the knowledge of system parameters such as inertia constants and topology, and is shown to achieve highly accurate localization and estimation performance even in the presence of measurement noise and missing data.
Document Chunking and Learning Objective Generation for Instruction Design
Venue: arXiv cs.CL 2018
Year: 2018

Instructional Systems Design is the practice of creating of instructional experiences that make the acquisition of knowledge and skill more efficient, effective, and appealing. Specifically in designing courses, an hour of training material can require between 30 to 500 hours of effort in sourcing and organizing reference data for use in just the preparation of course material. In this paper, we present the first system of its kind that helps reduce the effort associated with sourcing reference material and course creation. We present algorithms for document chunking and automatic generation of learning objectives from content, creating descriptive content metadata to improve content-discoverability. Unlike existing methods, the learning objectives generated by our system incorporate pedagogically motivated Bloom's verbs. We demonstrate the usefulness of our methods using real world data from the banking industry and through a live deployment at a large pharmaceutical company.
Factorized Adversarial Networks for Unsupervised Domain Adaptation
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we propose Factorized Adversarial Networks (FAN) to solve unsupervised domain adaptation problems for image classification tasks. Our networks map the data distribution into a latent feature space, which is factorized into a domain-specific subspace that contains domain-specific characteristics and a task-specific subspace that retains category information, for both source and target domains, respectively. Unsupervised domain adaptation is achieved by adversarial training to minimize the discrepancy between the distributions of two task-specific subspaces from source and target domains. We demonstrate that the proposed approach outperforms state-of-the-art methods on multiple benchmark datasets used in the literature for unsupervised domain adaptation. Furthermore, we collect two real-world tagging datasets that are much larger than existing benchmark datasets, and get significant improvement upon baselines, proving the practical value of our approach.
New And Surprising Ways to Be Mean. Adversarial NPCs with Coupled Empowerment Minimisation
Venue: arXiv cs.AI 2018
Year: 2018

Creating Non-Player Characters (NPCs) that can react robustly to unforeseen player behaviour or novel game content is difficult and time-consuming. This hinders the design of believable characters, and the inclusion of NPCs in games that rely heavily on procedural content generation. We have previously addressed this challenge by means of empowerment, a model of intrinsic motivation, and demonstrated how a coupled empowerment maximisation (CEM) policy can yield generic, companion-like behaviour. In this paper, we extend the CEM framework with a minimisation policy to give rise to adversarial behaviour. We conduct a qualitative, exploratory study in a dungeon-crawler game, demonstrating that CEM can exploit the affordances of different content facets in adaptive adversarial behaviour without modifications to the policy. Changes to the level design, underlying mechanics and our character's actions do not threaten our NPC's robustness, but yield new and surprising ways to be mean.
CFCM: Segmentation via Coarse to Fine Context Memory
Venue: arXiv cs.CV 2018
Year: 2018

Recent neural-network-based architectures for image segmentation make extensive usage of feature forwarding mechanisms to integrate information from multiple scales. Although yielding good results, even deeper architectures and alternative methods for feature fusion at different resolutions have been scarcely investigated for medical applications. In this work we propose to implement segmentation via an encoder-decoder architecture which differs from any other previously published method since (i) it employs a very deep architecture based on residual learning and (ii) combines features via a convolutional Long Short Term Memory (LSTM), instead of concatenation or summation. The intuition is that the memory mechanism implemented by LSTMs can better integrate features from different scales through a coarse-to-fine strategy; hence the name Coarse-to-Fine Context Memory (CFCM). We demonstrate the remarkable advantages of this approach on two datasets: the Montgomery county lung segmentation dataset, and the EndoVis 2015 challenge dataset for surgical instrument segmentation.
NDN, CoAP, and MQTT: A Comparative Measurement Study in the IoT
Venue: arXiv cs.NI 2018
Year: 2018

This paper takes a comprehensive view on the protocol stacks that are under debate for a future Internet of Things (IoT). It addresses the holistic question of which solution is beneficial for common IoT use cases. We deploy NDN and the two popular IP-based application protocols, CoAP and MQTT, in its different variants on a large-scale IoT testbed in single- and multi-hop scenarios. We analyze the use cases of scheduled periodic and unscheduled traffic under varying loads. Our findings indicate that (a) NDN admits the most resource-friendly deployment on nodes, and (b) shows superior robustness and resilience in multi-hop scenarios, while (c) the IP protocols operate at less overhead and higher speed in single-hop deployments. Most strikingly we find that NDN-based protocols are in significantly better flow balance than the UDP-based IP protocols and require less corrective actions.
A Primer on Causal Analysis
Venue: arXiv cs.LG 2018
Year: 2018

We provide a conceptual map to navigate causal analysis problems. Focusing on the case of discrete random variables, we consider the case of causal effect estimation from observational data. The presented approaches apply also to continuous variables, but the issue of estimation becomes more complex. We then introduce the four schools of thought for causal analysis
Using the AIDA Language to Formally Organize Scientific Claims
Venue: arXiv cs.DL 2018
Year: 2018

Scientific communication still mainly relies on natural language written in scientific papers, which makes the described knowledge very difficult to access with automatic means. We can therefore only make limited use of formal knowledge organization methods to support researchers and other interested parties with features such as automatic aggregations, fact checking, consistency checking, question answering, and powerful semantic search. Existing approaches to solve this problem by improving the scientific communication methods have either very restricted coverage, require formal logic skills on the side of the researchers, or depend on unreliable machine learning for the formalization of knowledge. Here, I propose an approach to this problem that is general, intuitive, and flexible. It is based on a unique kind of controlled natural language, called AIDA, consisting of English sentences that are atomic, independent, declarative, and absolute. Such sentences can then serve as nodes in a network of scientific claims linked to publications, researchers, and domain elements. I present here some small studies on preliminary applications of this language. The results indicate that it is well accepted by users and provides a good basis for the creation of a knowledge graph of scientific findings.
L'acceptation et l'appropriation des ENT (Espaces Num{é}riques de Travail) par les enseignants du primaire
Venue: arXiv cs.CY 2018
Year: 2018

This article presents an evaluation of the conditions of use of a VWE (Virtual Work Environment) by primary school teachers. To this end, we conducted two studies and used activity theory as theoretical framework. Our first study aims to assess real practices carried out with the VWE and analyzed publications' content in order to understand how users appropriate the tool. The second study describes how teachers perceive the role of the VWE in the evolution of their working prac-tices (maintaining, transforming and restricting the existent practices). These stud-ies indicate that technological appropriation is achieved through instructional and communicational uses. The acceptance of this VWE is due to its ease of use and interface adequacy to teachers and young children.
Multi-sensor data fusion based on a generalised belief divergence measure
Venue: arXiv cs.AI 2018
Year: 2018

Multi-sensor data fusion technology plays an important role in real applications. Because of the flexibility and effectiveness in modelling and processing the uncertain information regardless of prior probabilities, Dempster-Shafer evidence theory is widely applied in a variety of fields of information fusion. However, counter-intuitive results may come out when fusing the highly conflicting evidences. In order to deal with this problem, a novel method for multi-sensor data fusion based on a new generalised belief divergence measure of evidences is proposed. Firstly, the reliability weights of evidences are determined by considering the sufficiency and importance of the evidences. After that, on account of the reliability weights of evidences, a new Generalised Belief Jensen-Shannon divergence (GBJS) is designed to measure the discrepancy and conflict degree among multiple evidences, which can be utilised to measure the support degrees of evidences. Afterwards, the support degrees of evidences are used to adjust the bodies of the evidences before using the Dempster's combination rule. Finally, an application in fault diagnosis demonstrates the validity of the proposed method.
Adaptive Importance Learning for Improving Lightweight Image Super-resolution Network
Venue: arXiv cs.CV 2018
Year: 2018

Deep neural networks have achieved remarkable success in single image super-resolution (SISR). The computing and memory requirements of these methods have hindered their application to broad classes of real devices with limited computing power, however. One approach to this problem has been lightweight network architectures that bal- ance the super-resolution performance and the computation burden. In this study, we revisit this problem from an orthog- onal view, and propose a novel learning strategy to maxi- mize the pixel-wise fitting capacity of a given lightweight network architecture. Considering that the initial capacity of the lightweight network is very limited, we present an adaptive importance learning scheme for SISR that trains the network with an easy-to-complex paradigm by dynam- ically updating the importance of image pixels on the basis of the training loss. Specifically, we formulate the network training and the importance learning into a joint optimization problem. With a carefully designed importance penalty function, the importance of individual pixels can be gradu- ally increased through solving a convex optimization problem. The training process thus begins with pixels that are easy to reconstruct, and gradually proceeds to more complex pixels as fitting improves.
Dynamic Programming Optimization in Line of Sight Networks
Venue: arXiv cs.DS 2018
Year: 2018

Line of Sight (LoS) networks were designed to model wireless communication in settings which may contain obstacles restricting node visibility. For fixed positive integer $d$, and positive integer $ω$, a graph $G=(V,E)$ is a ($d$-dimensional) LoS network with range parameter $ω$ if it can be embedded in a cube of side size $n$ of the $d$-dimensional integer grid so that each pair of vertices in $V$ are adjacent if and only if their embedding coordinates differ only in one position and such difference is less than $ω$. In this paper we investigate a dynamic programming (DP) approach which can be used to obtain efficient algorithmic solutions for various combinatorial problems in LoS networks. In particular DP solves the Maximum Independent Set (MIS) problem in LoS networks optimally for any $ω$ on {\em narrow} LoS networks (i.e. networks which can be embedded in a $n \times k \times k \ldots \times k$ region, for some fixed $k$ independent of $n$). In the unrestricted case it has been shown that the MIS problem is NP-hard when $ ω> 2$ (the hardness proof goes through for any $ω=O(n^{1-δ})$, for fixed $0<δ<1$). We describe how DP can be used as a building block in the design of good approximation algorithms. In particular we present a 2-approximation algorithm and a fast polynomial time approximation scheme for the MIS problem in arbitrary $d$-dimensional LoS networks. Finally we comment on how the approach can be adapted to solve a number of important optimization problems in LoS networks.
On the Energy Efficiency of MIMO Hybrid Beamforming for Millimeter Wave Systems with Nonlinear Power Amplifiers
Venue: arXiv cs.IT 2018
Year: 2018

Multiple-input multiple-output (MIMO) millimeter wave (mmWave) systems are vulnerable to hardware impairments due to operating at high frequencies and employing a large number of radio- frequency (RF) hardware components. In particular, nonlinear power amplifiers (PAs) employed at the transmitter distort the signal when operated close to saturation due to energy efficiency considerations. In this paper, we study the performance of a MIMO mmWave hybrid beamforming scheme in the presence of nonlinear PAs. First, we develop a statistical model for the transmitted signal in such systems and show that the spatial direction of the inband distortion is shaped by the beamforming filter. This suggests that even in the large antenna regime, where narrow beams can be steered toward the receiver, the impact of nonlinear PAs should not be ignored. Then, by employing a realistic power consumption model for the PAs, we investigate the trade-off between spectral and energy efficiency in such systems. Our results show that increasing the transmit power level when the number of transmit antennas grows large can be counter-effective in terms of energy efficiency. Furthermore, using numerical simulation, we show that when the transmit power is large, analog beamforming leads to higher spectral and energy efficiency compared to digital and hybrid beamforming schemes.
Understanding Meanings in Multilingual Customer Feedback
Venue: arXiv cs.CL 2018
Year: 2018

Understanding and being able to react to customer feedback is the most fundamental task in providing good customer service. However, there are two major obstacles for international companies to automatically detect the meaning of customer feedback in a global multilingual environment. Firstly, there is no widely acknowledged categorisation (classes) of meaning for customer feedback. Secondly, the applicability of one meaning categorisation, if it exists, to customer feedback in multiple languages is questionable. In this paper, we extracted representative real world samples of customer feedback from Microsoft Office customers in multiple languages, English, Spanish and Japanese,and concluded a five-class categorisation(comment, request, bug, complaint and meaningless) for meaning classification that could be used across languages in the realm of customer feedback analysis.
Level-Based Analysis of the Population-Based Incremental Learning Algorithm
Venue: arXiv cs.NE 2018
Year: 2018

The Population-Based Incremental Learning (PBIL) algorithm uses a convex combination of the current model and the empirical model to construct the next model, which is then sampled to generate offspring. The Univariate Marginal Distribution Algorithm (UMDA) is a special case of the PBIL, where the current model is ignored. Dang and Lehre (GECCO 2015) showed that UMDA can optimise LeadingOnes efficiently. The question still remained open if the PBIL performs equally well. Here, by applying the level-based theorem in addition to Dvoretzky--Kiefer--Wolfowitz inequality, we show that the PBIL optimises function LeadingOnes in expected time $\mathcal{O}(nλ\log λ+ n^2)$ for a population size $λ= Ω(\log n)$, which matches the bound of the UMDA. Finally, we show that the result carries over to BinVal, giving the fist runtime result for the PBIL on the BinVal problem.
Luminoso at SemEval-2018 Task 10: Distinguishing Attributes Using Text Corpora and Relational Knowledge
Venue: arXiv cs.CL 2018
Year: 2018

Luminoso participated in the SemEval 2018 task on "Capturing Discriminative Attributes" with a system based on ConceptNet, an open knowledge graph focused on general knowledge. In this paper, we describe how we trained a linear classifier on a small number of semantically-informed features to achieve an $F_1$ score of 0.7368 on the task, close to the task's high score of 0.75.
On MIMO Channel Capacity with Output Quantization Constraints
Venue: arXiv cs.IT 2018
Year: 2018

The capacity of a Multiple-Input Multiple-Output (MIMO) channel in which the antenna outputs are processed by an analog linear combining network and quantized by a set of threshold quantizers is studied. The linear combining weights and quantization thresholds are selected from a set of possible configurations as a function of the channel matrix. The possible configurations of the combining network model specific analog receiver architectures, such as single antenna selection, sign quantization of the antenna outputs or linear processing of the outputs. An interesting connection between the capacity of this channel and a constrained sphere packing problem in which unit spheres are packed in a hyperplane arrangement is shown. From a high-level perspective, this follows from the fact that each threshold quantizer can be viewed as a hyperplane partitioning the transmitter signal space. Accordingly, the output of the set of quantizers corresponds to the possible regions induced by the hyperplane arrangement corresponding to the channel realization and receiver configuration. This connection provides a number of important insights into the design of quantization architectures for MIMO receivers; for instance, it shows that for a given number of quantizers, choosing configurations which induce a larger number of partitions can lead to higher rates.