OpenRaiser/Intern-Atlas huggingface dataset:
Mixed integer programming formulation of unsupervised learning
Venue: arXiv cs.LG 2020
Year: 2020

A novel formulation and training procedure for full Boltzmann machines in terms of a mixed binary quadratic feasibility problem is given. As a proof of concept, the theory is analytically and numerically tested on XOR patterns.
Secure Index Coding with Security Constraints on Receivers
Venue: arXiv cs.IT 2020
Year: 2020

Index coding is concerned with efficient broadcast of a set of messages to receivers in the presence of receiver side information. In this paper, we study the secure index coding problem with security constraints on the receivers themselves. That is, for each receiver there is a single legitimate message it needs to decode and a prohibited message list, none of which should be decoded by that receiver. To this end, our contributions are threefold. We first introduce a secure linear coding scheme, which is an extended version of the fractional local partial clique covering scheme that was originally devised for non-secure index coding. We then develop two information-theoretic bounds on the performance of any valid secure index code, namely secure polymatroidal outer bound (on the capacity region) and secure maximum acyclic induced subgraph lower bound (on the broadcast rate). The structure of these bounds leads us to further develop two necessary conditions for a given index coding problem to be securely feasible (i.e., to have nonzero rates).
On the infinite width limit of neural networks with a standard parameterization
Venue: arXiv cs.LG 2020
Year: 2020

There are currently two parameterizations used to derive fixed kernels corresponding to infinite width neural networks, the NTK (Neural Tangent Kernel) parameterization and the naive standard parameterization. However, the extrapolation of both of these parameterizations to infinite width is problematic. The standard parameterization leads to a divergent neural tangent kernel while the NTK parameterization fails to capture crucial aspects of finite width networks such as: the dependence of training dynamics on relative layer widths, the relative training dynamics of weights and biases, and overall learning rate scale. Here we propose an improved extrapolation of the standard parameterization that preserves all of these properties as width is taken to infinity and yields a well-defined neural tangent kernel. We show experimentally that the resulting kernels typically achieve similar accuracy to those resulting from an NTK parameterization, but with better correspondence to the parameterization of typical finite width networks. Additionally, with careful tuning of width parameters, the improved standard parameterization kernels can outperform those stemming from an NTK parameterization. We release code implementing this improved standard parameterization as part of the Neural Tangents library at https://github.com/google/neural-tangents.
Face Verification via learning the kernel matrix
Venue: arXiv cs.CV 2020
Year: 2020

The kernel function is introduced to solve the nonlinear pattern recognition problem. The advantage of a kernel method often depends critically on a proper choice of the kernel function. A promising approach is to learn the kernel from data automatically. Over the past few years, some methods which have been proposed to learn the kernel have some limitations: learning the parameters of some prespecified kernel function and so on. In this paper, the nonlinear face verification via learning the kernel matrix is proposed. A new criterion is used in the new algorithm to avoid inverting the possibly singular within-class which is a computational problem. The experimental results obtained on the facial database XM2VTS using the Lausanne protocol show that the verification performance of the new method is superior to that of the primary method Client Specific Kernel Discriminant Analysis (CSKDA). The method CSKDA needs to choose a proper kernel function through many experiments, while the new method could learn the kernel from data automatically which could save a lot of time and have the robust performance.
Online Caching and Coding at the WiFi Edge: Gains and Tradeoffs
Venue: arXiv cs.NI 2020
Year: 2020

Video content delivery at the wireless edge continues to be challenged by insufficient bandwidth and highly dynamic user behavior which affects both effective throughput and latency. Caching at the network edge and coded transmissions have been found to improve user performance of video content delivery. The cache at the wireless edge stations (BSs, APs) and at the users' end devices can be populated by pre-caching content or by using online caching policies. In this paper, we propose a system where content is cached at the user of a WiFi network via online caching policies, and coded delivery is employed by the WiFi AP to deliver the requested content to the user population. The content of the cache at the user serves as side information for index coding. We also propose the LFU-Index cache replacement policy at the user that demonstrably improves index coding opportunities at the WiFi AP for the proposed system. Through an extensive simulation study, we determine the gains achieved by caching and index by coding. Next, we analyze the tradeoffs between them in terms of data transmitted, latency, and throughput for different content request behaviors from the users. We also show that the proposed cache replacement policy performs better than traditional cache replacement policies like LRU and LFU.
Enabling Panoramic Full-Angle Reflection via Aerial Intelligent Reflecting Surface
Venue: arXiv cs.IT 2020
Year: 2020

This paper proposes a new three dimensional (3D) networking architecture enabled by aerial intelligent reflecting surface (AIRS) to achieve panoramic signal reflection from the sky. Compared to the conventional terrestrial IRS, AIRS not only enjoys higher deployment flexibility, but also is able to achieve 360$^\circ$ panoramic full-angle reflection and requires fewer reflections in general due to its higher likelihood of having line of sight (LoS) links with the ground nodes. We focus on the problem to maximize the worst-case signal-to-noise ratio (SNR) in a given coverage area by jointly optimizing the transmit beamforming, AIRS placement and phase shifts. The formulated problem is non-convex and the optimization variables are coupled with each other in an intricate manner. To tackle this problem, we first consider the special case of single-location SNR maximization to gain useful insights, for which the optimal solution is obtained in closed-form. Then for the general case of area coverage, an efficient suboptimal solution is proposed by exploiting the similarity between phase shifts optimization for IRS and analog beamforming for the conventional phase array. Numerical results show that the proposed design can achieve significant performance gain than heuristic AIRS deployment schemes.
Transfer Learning using Neural Ordinary Differential Equations
Venue: arXiv cs.LG 2020
Year: 2020

A concept of using Neural Ordinary Differential Equations(NODE) for Transfer Learning has been introduced. In this paper we use the EfficientNets to explore transfer learning on CIFAR-10 dataset. We use NODE for fine-tuning our model. Using NODE for fine tuning provides more stability during training and validation.These continuous depth blocks can also have a trade off between numerical precision and speed .Using Neural ODEs for transfer learning has resulted in much stable convergence of the loss function.
Pruning Neural Belief Propagation Decoders
Venue: arXiv cs.IT 2020
Year: 2020

We consider near maximum-likelihood (ML) decoding of short linear block codes based on neural belief propagation (BP) decoding recently introduced by Nachmani et al.. While this method significantly outperforms conventional BP decoding, the underlying parity-check matrix may still limit the overall performance. In this paper, we introduce a method to tailor an overcomplete parity-check matrix to (neural) BP decoding using machine learning. We consider the weights in the Tanner graph as an indication of the importance of the connected check nodes (CNs) to decoding and use them to prune unimportant CNs. As the pruning is not tied over iterations, the final decoder uses a different parity-check matrix in each iteration. For Reed-Muller and short low-density parity-check codes, we achieve performance within 0.27 dB and 1.5 dB of the ML performance while reducing the complexity of the decoder.
Domain-Aware Dialogue State Tracker for Multi-Domain Dialogue Systems
Venue: arXiv cs.CL 2020
Year: 2020

In task-oriented dialogue systems the dialogue state tracker (DST) component is responsible for predicting the state of the dialogue based on the dialogue history. Current DST approaches rely on a predefined domain ontology, a fact that limits their effective usage for large scale conversational agents, where the DST constantly needs to be interfaced with ever-increasing services and APIs. Focused towards overcoming this drawback, we propose a domain-aware dialogue state tracker, that is completely data-driven and it is modeled to predict for dynamic service schemas. The proposed model utilizes domain and slot information to extract both domain and slot specific representations for a given dialogue, and then uses such representations to predict the values of the corresponding slot. Integrating this mechanism with a pretrained language model (i.e. BERT), our approach can effectively learn semantic relations.
Ensemble Genetic Programming
Venue: arXiv cs.NE 2020
Year: 2020

Ensemble learning is a powerful paradigm that has been usedin the top state-of-the-art machine learning methods like Random Forestsand XGBoost. Inspired by the success of such methods, we have devel-oped a new Genetic Programming method called Ensemble GP. The evo-lutionary cycle of Ensemble GP follows the same steps as other GeneticProgramming systems, but with differences in the population structure,fitness evaluation and genetic operators. We have tested this method oneight binary classification problems, achieving results significantly betterthan standard GP, with much smaller models. Although other methodslike M3GP and XGBoost were the best overall, Ensemble GP was able toachieve exceptionally good generalization results on a particularly hardproblem where none of the other methods was able to succeed.
Lattice QCD on a novel vector architecture
Venue: arXiv cs.DC 2020
Year: 2020

The SX-Aurora TSUBASA PCIe accelerator card is the newest model of NEC's SX architecture family. Its multi-core vector processor features a vector length of 16 kbits and interfaces with up to 48 GB of HBM2 memory in the current models, available since 2018. The compute performance is up to 2.45 TFlop/s peak in double precision, and the memory throughput is up to 1.2 TB/s peak. New models with improved performance characteristics are announced for the near future. In this contribution we discuss key aspects of the SX-Aurora and describe how we enabled the architecture in the Grid Lattice QCD framework.
Classifying Wikipedia in a fine-grained hierarchy: what graphs can contribute
Venue: arXiv cs.LG 2020
Year: 2020

Wikipedia is a huge opportunity for machine learning, being the largest semi-structured base of knowledge available. Because of this, many works examine its contents, and focus on structuring it in order to make it usable in learning tasks, for example by classifying it into an ontology. Beyond its textual contents, Wikipedia also displays a typical graph structure, where pages are linked together through citations. In this paper, we address the task of integrating graph (i.e. structure) information to classify Wikipedia into a fine-grained named entity ontology (NE), the Extended Named Entity hierarchy. To address this task, we first start by assessing the relevance of the graph structure for NE classification. We then explore two directions, one related to feature vectors using graph descriptors commonly used in large-scale network analysis, and one extending flat classification to a weighted model taking into account semantic similarity. We conduct at-scale practical experiments, on a manually labeled subset of 22,000 pages extracted from the Japanese Wikipedia. Our results show that integrating graph information succeeds at reducing sparsity of the input feature space, and yields classification results that are comparable or better than previous works.
MonteCarloMeasurements.jl: Nonlinear Propagation of Arbitrary Multivariate Distributions by means of Method Overloading
Venue: arXiv cs.MS 2020
Year: 2020

This manuscript outlines a software package that facilitates working with probability distributions by means of Monte-Carlo methods, in a way that allows for propagation of multivariate probability distributions through arbitrary functions. We provide a \emph{type} that represents probability distributions by an internal vector of unweighted samples, \texttt{Particles}, which is a subtype of a \texttt{Real} number and behaves just like a regular real number in calculations by means of method overloading. This makes the software easy to work with and presents minimal friction for the user. We highlight how this design facilitates optimal usage of SIMD instructions and showcase the package for uncertainty propagation through an off-the-shelf ODE solver, as well as for robust probabilistic optimization with automatic differentiation.
Stochastic Finite State Control of POMDPs with LTL Specifications
Venue: arXiv cs.AI 2020
Year: 2020

Partially observable Markov decision processes (POMDPs) provide a modeling framework for autonomous decision making under uncertainty and imperfect sensing, e.g. robot manipulation and self-driving cars. However, optimal control of POMDPs is notoriously intractable. This paper considers the quantitative problem of synthesizing sub-optimal stochastic finite state controllers (sFSCs) for POMDPs such that the probability of satisfying a set of high-level specifications in terms of linear temporal logic (LTL) formulae is maximized. We begin by casting the latter problem into an optimization and use relaxations based on the Poisson equation and McCormick envelopes. Then, we propose an stochastic bounded policy iteration algorithm, leading to a controlled growth in sFSC size and an any time algorithm, where the performance of the controller improves with successive iterations, but can be stopped by the user based on time or memory considerations. We illustrate the proposed method by a robot navigation case study.
Where New Words Are Born: Distributional Semantic Analysis of Neologisms and Their Semantic Neighborhoods
Venue: arXiv cs.CL 2020
Year: 2020

We perform statistical analysis of the phenomenon of neology, the process by which new words emerge in a language, using large diachronic corpora of English. We investigate the importance of two factors, semantic sparsity and frequency growth rates of semantic neighbors, formalized in the distributional semantics paradigm. We show that both factors are predictive of word emergence although we find more support for the latter hypothesis. Besides presenting a new linguistic application of distributional semantics, this study tackles the linguistic question of the role of language-internal factors (in our case, sparsity) in language change motivated by language-external factors (reflected in frequency growth).
Enabling Highly-Scalable Remote Memory Access Programming with MPI-3 One Sided
Venue: arXiv cs.DC 2020
Year: 2020

Modern interconnects offer remote direct memory access (RDMA) features. Yet, most applications rely on explicit message passing for communications albeit their unwanted overheads. The MPI-3.0 standard defines a programming interface for exploiting RDMA networks directly, however, it's scalability and practicability has to be demonstrated in practice. In this work, we develop scalable bufferless protocols that implement the MPI-3.0 specification. Our protocols support scaling to millions of cores with negligible memory consumption while providing highest performance and minimal overheads. To arm programmers, we provide a spectrum of performance models for all critical functions and demonstrate the usability of our library and models with several application studies with up to half a million processes. We show that our design is comparable to, or better than UPC and Fortran Coarrays in terms of latency, bandwidth, and message rate. We also demonstrate application performance improvements with comparable programming complexity.
Closed form distance formula for the balanced multiple travelling salesmen
Venue: arXiv cs.DS 2020
Year: 2020

As a first contribution the mTSP is solved using an exact method and two heuristics, where the number of nodes per route is balanced. The first heuristic uses a nearest node approach and the second assigns the closest vehicle (salesman). A comparison of heuristics with test-instances being in the Euclidean plane showed similar solution quality and runtime. On average, the nearest node solutions are approximately one percent better. The closest vehicle heuristic is especially important when the nodes (customers) are not known in advance, e.g. for online routing. Whilst the nearest node is preferable when one vehicle has to be used multiple times to service all customers. The second contribution is a closed form formula that describes the mTSP distance dependent on the number of vehicles and customers. Increasing the number of salesman results in an approximately linear distance growth for uniformly distributed nodes in a Euclidean grid plane. The distance growth is almost proportional to the square root of number of customers (nodes). These two insights are combined in a single formula. The minimum distance of a node to $n$ uniformly distributed random (real and integer) points was derived and expressed as functional relationship dependent on the number of vehicles. This gives theoretical underpinnings and is in agreement with the distances found via the previous mTSP heuristics. Hence, this allows to compute all expected mTSP distances without the need of running the heuristics.
Lesion Harvester: Iteratively Mining Unlabeled Lesions and Hard-Negative Examples at Scale
Venue: arXiv cs.CV 2020
Year: 2020

Acquiring large-scale medical image data, necessary for training machine learning algorithms, is frequently intractable, due to prohibitive expert-driven annotation costs. Recent datasets extracted from hospital archives, e.g., DeepLesion, have begun to address this problem. However, these are often incompletely or noisily labeled, e.g., DeepLesion leaves over 50% of its lesions unlabeled. Thus, effective methods to harvest missing annotations are critical for continued progress in medical image analysis. This is the goal of our work, where we develop a powerful system to harvest missing lesions from the DeepLesion dataset at high precision. Accepting the need for some degree of expert labor to achieve high fidelity, we exploit a small fully-labeled subset of medical image volumes and use it to intelligently mine annotations from the remainder. To do this, we chain together a highly sensitive lesion proposal generator and a very selective lesion proposal classifier. While our framework is generic, we optimize our performance by proposing a 3D contextual lesion proposal generator and by using a multi-view multi-scale lesion proposal classifier. These produce harvested and hard-negative proposals, which we then re-use to finetune our proposal generator by using a novel hard negative suppression loss, continuing this process until no extra lesions are found. Extensive experimental analysis demonstrates that our method can harvest an additional 9,805 lesions while keeping precision above 90%. To demonstrate the benefits of our approach, we show that lesion detectors trained on our harvested lesions can significantly outperform the same variants only trained on the original annotations, with boost of average precision of 7% to 10%. We open source our annotations at https://github.com/JimmyCai91/DeepLesionAnnotation.
Depth Completion Using a View-constrained Deep Prior
Venue: arXiv cs.CV 2020
Year: 2020

Recent work has shown that the structure of convolutional neural networks (CNNs) induces a strong prior that favors natural images. This prior, known as a deep image prior (DIP), is an effective regularizer in inverse problems such as image denoising and inpainting. We extend the concept of the DIP to depth images. Given color images and noisy and incomplete target depth maps, we optimize a randomly-initialized CNN model to reconstruct a depth map restored by virtue of using the CNN network structure as a prior combined with a view-constrained photo-consistency loss. This loss is computed using images from a geometrically calibrated camera from nearby viewpoints. We apply this deep depth prior for inpainting and refining incomplete and noisy depth maps within both binocular and multi-view stereo pipelines. Our quantitative and qualitative evaluation shows that our refined depth maps are more accurate and complete, and after fusion, produces dense 3D models of higher quality.
A Price-Per-Attention Auction Scheme Using Mouse Cursor Information
Venue: arXiv cs.GT 2020
Year: 2020

Payments in online ad auctions are typically derived from click-through rates, so that advertisers do not pay for ineffective ads. But advertisers often care about more than just clicks. That is, for example, if they aim to raise brand awareness or visibility. There is thus an opportunity to devise a more effective ad pricing paradigm, in which ads are paid only if they are actually noticed. This article contributes a novel auction format based on a pay-per-attention (PPA) scheme. We show that the PPA auction inherits the desirable properties (strategy-proofness and efficiency) as its pay-per-impression and pay-per-click counterparts, and that it also compares favourably in terms of revenues. To make the PPA format feasible, we also contribute a scalable diagnostic technology to predict user attention to ads in sponsored search using raw mouse cursor coordinates only, regardless of the page content and structure. We use the user attention predictions in numerical simulations to evaluate the PPA auction scheme. Our results show that, in relevant economic settings, the PPA revenues would be strictly higher than the existing auction payment schemes.
Incentivising Exploration and Recommendations for Contextual Bandits with Payments
Venue: arXiv cs.LG 2020
Year: 2020

We propose a contextual bandit based model to capture the learning and social welfare goals of a web platform in the presence of myopic users. By using payments to incentivize these agents to explore different items/recommendations, we show how the platform can learn the inherent attributes of items and achieve a sublinear regret while maximizing cumulative social welfare. We also calculate theoretical bounds on the cumulative costs of incentivization to the platform. Unlike previous works in this domain, we consider contexts to be completely adversarial, and the behavior of the adversary is unknown to the platform. Our approach can improve various engagement metrics of users on e-commerce stores, recommendation engines and matching platforms.