OpenRaiser/Intern-Atlas huggingface dataset:
On the Computational Complexity of Blind Detection of Binary Linear Codes
Venue: arXiv cs.IT 2019
Year: 2019

In this work, we study the computational complexity of the Minimum Distance Code Detection problem. In this problem, we are given a set of noisy codeword observations and we wish to find a code in a set of linear codes $\mathcal{C}$ of a given dimension $k$, for which the sum of distances between the observations and the code is minimized. We prove that, for the practically relevant case when the set $\mathcal{C}$ only contains a fixed number of candidate linear codes, the detection problem is NP-hard and we identify a number of interesting open questions related to the code detection problem.
iFair: Learning Individually Fair Data Representations for Algorithmic Decision Making
Venue: arXiv cs.LG 2019
Year: 2019

People are rated and ranked, towards algorithmic decision making in an increasing number of applications, typically based on machine learning. Research on how to incorporate fairness into such tasks has prevalently pursued the paradigm of group fairness: giving adequate success rates to specifically protected groups. In contrast, the alternative paradigm of individual fairness has received relatively little attention, and this paper advances this less explored direction. The paper introduces a method for probabilistically mapping user records into a low-rank representation that reconciles individual fairness and the utility of classifiers and rankings in downstream applications. Our notion of individual fairness requires that users who are similar in all task-relevant attributes such as job qualification, and disregarding all potentially discriminating attributes such as gender, should have similar outcomes. We demonstrate the versatility of our method by applying it to classification and learning-to-rank tasks on a variety of real-world datasets. Our experiments show substantial improvements over the best prior work for this setting.
Penalizing side effects using stepwise relative reachability
Venue: arXiv cs.LG 2019
Year: 2019

How can we design safe reinforcement learning agents that avoid unnecessary disruptions to their environment? We show that current approaches to penalizing side effects can introduce bad incentives, e.g. to prevent any irreversible changes in the environment, including the actions of other agents. To isolate the source of such undesirable incentives, we break down side effects penalties into two components: a baseline state and a measure of deviation from this baseline state. We argue that some of these incentives arise from the choice of baseline, and others arise from the choice of deviation measure. We introduce a new variant of the stepwise inaction baseline and a new deviation measure based on relative reachability of states. The combination of these design choices avoids the given undesirable incentives, while simpler baselines and the unreachability measure fail. We demonstrate this empirically by comparing different combinations of baseline and deviation measure choices on a set of gridworld experiments designed to illustrate possible bad incentives.
Computing the Spatial Probability of Inclusion inside Partial Contours for Computer Vision Applications
Venue: arXiv cs.CV 2019
Year: 2019

In Computer Vision, edge detection is one of the favored approaches for feature and object detection in images since it provides information about their objects boundaries. Other region-based approaches use probabilistic analysis such as clustering and Markov random fields, but those methods cannot be used to analyze edges and their interaction. In fact, only image segmentation can produce regions based on edges, but it requires thresholding by simply separating the regions into binary in-out information. Hence, there is currently a gap between edge-based and region-based algorithms, since edges cannot be used to study the properties of a region and vice versa. The objective of this paper is to present a novel spatial probability analysis that allows determining the probability of inclusion inside a set of partial contours (strokes). To answer this objective, we developed a new approach that uses electromagnetic convolutions and repulsion optimization to compute the required probabilities. Hence, it becomes possible to generate a continuous space of probability based only on the edge information, thus bridging the gap between the edge-based methods and the region-based methods. The developed method is consistent with the fundamental properties of inclusion probabilities and its results are validated by comparing an image with the probability-based estimation given by our algorithm. The method can also be generalized to take into consideration the intensity of the edges or to be used for 3D shapes. This is the first documented method that allows computing a space of probability based on interacting edges, which opens the path to broader applications such as image segmentation and contour completion.
Embedding Logical Queries on Knowledge Graphs
Venue: arXiv cs.SI 2019
Year: 2019

Learning low-dimensional embeddings of knowledge graphs is a powerful approach used to predict unobserved or missing edges between entities. However, an open challenge in this area is developing techniques that can go beyond simple edge prediction and handle more complex logical queries, which might involve multiple unobserved edges, entities, and variables. For instance, given an incomplete biological knowledge graph, we might want to predict "em what drugs are likely to target proteins involved with both diseases X and Y?" -- a query that requires reasoning about all possible proteins that {\em might} interact with diseases X and Y. Here we introduce a framework to efficiently make predictions about conjunctive logical queries -- a flexible but tractable subset of first-order logic -- on incomplete knowledge graphs. In our approach, we embed graph nodes in a low-dimensional space and represent logical operators as learned geometric operations (e.g., translation, rotation) in this embedding space. By performing logical operations within a low-dimensional embedding space, our approach achieves a time complexity that is linear in the number of query variables, compared to the exponential complexity required by a naive enumeration-based approach. We demonstrate the utility of this framework in two application studies on real-world datasets with millions of relations: predicting logical relationships in a network of drug-gene-disease interactions and in a graph-based representation of social interactions derived from a popular web forum.
Layer rotation: a surprisingly powerful indicator of generalization in deep networks?
Venue: arXiv cs.LG 2019
Year: 2019

Our work presents extensive empirical evidence that layer rotation, i.e. the evolution across training of the cosine distance between each layer's weight vector and its initialization, constitutes an impressively consistent indicator of generalization performance. In particular, larger cosine distances between final and initial weights of each layer consistently translate into better generalization performance of the final model. Interestingly, this relation admits a network independent optimum: training procedures during which all layers' weights reach a cosine distance of 1 from their initialization consistently outperform other configurations -by up to 30% test accuracy. Moreover, we show that layer rotations are easily monitored and controlled (helpful for hyperparameter tuning) and potentially provide a unified framework to explain the impact of learning rate tuning, weight decay, learning rate warmups and adaptive gradient methods on generalization and training speed. In an attempt to explain the surprising properties of layer rotation, we show on a 1-layer MLP trained on MNIST that layer rotation correlates with the degree to which features of intermediate layers have been trained.
Efficient Multi-Accuracy Computations of Complex Functions with Complex Arguments
Venue: arXiv cs.NA 2019
Year: 2019

We present an efficient multi-accuracy algorithm for the computations of a set of special functions of a complex argument, z=x+iy. These functions include the complex probability function w(z), and closely related functions such as the error function erf(z), complementary error function erfc(z), imaginary error function erfi(z), scaled complementary error function, erfcx(z), the plasma dispersion function Z(z), Dawson s function Daw(z), and Fresnel integrals S(z) and C(z). Computational results from the present algorithm are compared with results from competitive algorithms and widely used software packages showing superior accuracy and efficiency of the present algorithm. In particular, the present results highlight concerns about the accuracy of evaluating such special functions using commercial packages like Mathematica and free/open source packages like the MIT-C++ package.
Secrecy Outage Analysis of Mixed RF-FSO Downlink SWIPT Systems
Venue: arXiv cs.IT 2019
Year: 2019

We analyze a secure dual-hop mixed radio frequency-free space optical (RF-FSO) downlink simultaneous wireless information and power transfer (SWIPT) systems. The FSO link and all RF links experience Gamma-Gamma, independent and identical Nakagami-$m$ fading, respectively. We analyze the effects of atmospheric turbulence, pointing error, detection technology, path loss, and energy harvesting on secrecy performance. Signal-to-noise ratios at both legitimate and illegitimate receivers are not independent since they are both simultaneously influenced by the FSO link. We derive the closed-form expression of the secrecy outage probability (SOP) as well as the asymptotic result for SOP when signal-to-noise ratios at relay and legitimate destinations tend to infinity. Monte-Carlo simulations are performed to verify the accuracy of our analysis. The results show that the secrecy diversity order (SDO) depends on the fading parameter of the relay-destination link and the number of the destination's antennas. Additionally, the SDO also depends on the fading parameters, the pointing error parameter, and the detection type of the FSO link.
Learning to Understand Goal Specifications by Modelling Reward
Venue: arXiv cs.AI 2019
Year: 2019

Recent work has shown that deep reinforcement-learning agents can learn to follow language-like instructions from infrequent environment rewards. However, this places on environment designers the onus of designing language-conditional reward functions which may not be easily or tractably implemented as the complexity of the environment and the language scales. To overcome this limitation, we present a framework within which instruction-conditional RL agents are trained using rewards obtained not from the environment, but from reward models which are jointly trained from expert examples. As reward models improve, they learn to accurately reward agents for completing tasks for environment configurations---and for instructions---not present amongst the expert data. This framework effectively separates the representation of what instructions require from how they can be executed. In a simple grid world, it enables an agent to learn a range of commands requiring interaction with blocks and understanding of spatial relations and underspecified abstract arrangements. We further show the method allows our agent to adapt to changes in the environment without requiring new expert examples.
Regular tree languages in low levels of the Wadge Hierarchy
Venue: arXiv cs.FL 2019
Year: 2019

In this article we provide effective characterisations of regular languages of infinite trees that belong to the low levels of the Wadge hierarchy. More precisely we prove decidability for each of the finite levels of the hierarchy; for the class of the Boolean combinations of open sets $BC(Σ_1^0)$ (i.e. the union of the first $ω$ levels); and for the Borel class $Δ_2^0$ (i.e. for the union of the first $ω_1$ levels).
DiG: Enabling Out-of-Band Scalable High-Resolution Monitoring for Data-Center Analytics, Automation and Control (Extended)
Venue: arXiv cs.DC 2019
Year: 2019

Data centers are increasing in size and complexity, and we need scalable approaches to support their automated analysis and control. Performance counters and power consumption are their key "vital signs". State-of-the-Art (SoA) monitoring systems provide built-in tools to collect performance measurements, and custom solutions to get insight on their power consumption. However, with the increase in measurement resolution (in time and space) and the ensuing huge amount of measurement data to handle, new challenges arise, such as bottlenecks on the network bandwidth, storage and software overhead on the monitoring units. To face these challenges we propose a novel monitoring platform for data centers, which enables real-time high-resolution profiling (i.e., all available performance counters and the entire signal bandwidth of the power consumption at the plug - sampling up to 20us - with an error below 1%) and analytics, both at the edge (node-level analysis) and on a centralized unit (cluster-level analysis). The monitoring infrastructure is completely out-of-band, scalable, technology agnostic and low cost, and it is already installed in a SoA high-performance compute cluster (i.e., D.A.V.I.D.E. - 18th in Green500 November 2017).
Probabilistic Model-Agnostic Meta-Learning
Venue: arXiv cs.LG 2019
Year: 2019

Meta-learning for few-shot learning entails acquiring a prior over previous tasks and experiences, such that new tasks be learned from small amounts of data. However, a critical challenge in few-shot learning is task ambiguity: even when a powerful prior can be meta-learned from a large number of prior tasks, a small dataset for a new task can simply be too ambiguous to acquire a single model (e.g., a classifier) for that task that is accurate. In this paper, we propose a probabilistic meta-learning algorithm that can sample models for a new task from a model distribution. Our approach extends model-agnostic meta-learning, which adapts to new tasks via gradient descent, to incorporate a parameter distribution that is trained via a variational lower bound. At meta-test time, our algorithm adapts via a simple procedure that injects noise into gradient descent, and at meta-training time, the model is trained such that this stochastic adaptation procedure produces samples from the approximate model posterior. Our experimental results show that our method can sample plausible classifiers and regressors in ambiguous few-shot learning problems. We also show how reasoning about ambiguity can also be used for downstream active learning problems.
Logarithmic mathematical morphology: a new framework adaptive to illumination changes
Venue: arXiv cs.CV 2019
Year: 2019

A new set of mathematical morphology (MM) operators adaptive to illumination changes caused by variation of exposure time or light intensity is defined thanks to the Logarithmic Image Processing (LIP) model. This model based on the physics of acquisition is consistent with human vision. The fundamental operators, the logarithmic-dilation and the logarithmic-erosion, are defined with the LIP-addition of a structuring function. The combination of these two adjunct operators gives morphological filters, namely the logarithmic-opening and closing, useful for pattern recognition. The mathematical relation existing between ``classical'' dilation and erosion and their logarithmic-versions is established facilitating their implementation. Results on simulated and real images show that logarithmic-MM is more efficient on low-contrasted information than ``classical'' MM.
Applications of Gaussian Process Latent Variable Models in Finance
Venue: arXiv cs.CE 2019
Year: 2019

Estimating covariances between financial assets plays an important role in risk management. In practice, when the sample size is small compared to the number of variables, the empirical estimate is known to be very unstable. Here, we propose a novel covariance estimator based on the Gaussian Process Latent Variable Model (GP-LVM). Our estimator can be considered as a non-linear extension of standard factor models with readily interpretable parameters reminiscent of market betas. Furthermore, our Bayesian treatment naturally shrinks the sample covariance matrix towards a more structured matrix given by the prior and thereby systematically reduces estimation errors. Finally, we discuss some financial applications of the GP-LVM.
FMHash: Deep Hashing of In-Air-Handwriting for User Identification
Venue: arXiv cs.CV 2019
Year: 2019

Many mobile systems and wearable devices, such as Virtual Reality (VR) or Augmented Reality (AR) headsets, lack a keyboard or touchscreen to type an ID and password for signing into a virtual website. However, they are usually equipped with gesture capture interfaces to allow the user to interact with the system directly with hand gestures. Although gesture-based authentication has been well-studied, less attention is paid to the gesture-based user identification problem, which is essentially an input method of account ID and an efficient searching and indexing method of a database of gesture signals. In this paper, we propose FMHash (i.e., Finger Motion Hash), a user identification framework that can generate a compact binary hash code from a piece of in-air-handwriting of an ID string. This hash code enables indexing and fast search of a large account database using the in-air-handwriting by a hash table. To demonstrate the effectiveness of the framework, we implemented a prototype and achieved >99.5% precision and >92.6% recall with exact hash code match on a dataset of 200 accounts collected by us. The ability of hashing in-air-handwriting pattern to binary code can be used to achieve convenient sign-in and sign-up with in-air-handwriting gesture ID on future mobile and wearable systems connected to the Internet.
On oracle-type local recovery guarantees in compressed sensing
Venue: arXiv cs.IT 2019
Year: 2019

We present improved sampling complexity bounds for stable and robust sparse recovery in compressed sensing. Our unified analysis based on l1 minimization encompasses the case where (i) the measurements are block-structured samples in order to reflect the structured acquisition that is often encountered in applications; (ii) the signal has an arbitrary structured sparsity, by results depending on its support S. Within this framework and under a random sign assumption, the number of measurements needed by l1 minimization can be shown to be of the same order than the one required by an oracle least-squares estimator. Moreover, these bounds can be minimized by adapting the variable density sampling to a given prior on the signal support and to the coherence of the measurements. We illustrate both numerically and analytically that our results can be successfully applied to recover Haar wavelet coefficients that are sparse in levels from random Fourier measurements in dimension one and two, which can be of particular interest in imaging problems. Finally, a preliminary numerical investigation shows the potential of this theory for devising adaptive sampling strategies in sparse polynomial approximation.
Network Subgraphs of the heterogeneous Chinese credit system
Venue: arXiv cs.CE 2019
Year: 2019

In this study, we investigate the evolution of Chinese guarantee networks from the angle of sub-patterns. First, we find that the mutual, 2-out-stars and triangle sub-patterns are motifs in 2- and 3-node subgraphs. Considering the heterogeneous financial characteristics of nodes, we find that small firms tend to form a mutual guarantee relationship and large firms are likely to be the guarantors in 2-out-stars sub-patterns.
Detection of Premature Ventricular Contractions Using Densely Connected Deep Convolutional Neural Network with Spatial Pyramid Pooling Layer
Venue: arXiv cs.CV 2019
Year: 2019

Premature ventricular contraction(PVC) is a type of premature ectopic beat originating from the ventricles. Automatic method for accurate and robust detection of PVC is highly clinically desired.Currently, most of these methods are developed and tested using the same database divided into training and testing set and their generalization performance across databases has not been fully validated. In this paper, a method based on densely connected convolutional neural network and spatial pyramid pooling is proposed for PVC detection which can take arbitrarily-sized QRS complexes as input both in training and testing. With a much less complicated and more straightforward architecture,the proposed network achieves comparable results to current state-of-the-art deep learning based method with regard to accuracy,sensitivity and specificity by training and testing using the MIT-BIH arrhythmia database as benchmark.Besides the benchmark database,QRS complexes are extracted from four more open databases namely the St-Petersburg Institute of Cardiological Technics 12-lead Arrhythmia Database,The MIT-BIH Normal Sinus Rhythm Database,The MIT-BIH Long Term Database and European ST-T Database. The extracted QRS complexes are different in length and sampling rate among the five databases.Cross-database training and testing is also experimented.The performance of the network shows an improvement on the benchmark database according to the result demonstrating the advantage of using multiple databases for training over using only a single database.The network also achieves satisfactory scores on the other four databases showing good generalization capability.
Circular-shift Linear Network Codes with Arbitrary Odd Block Lengths
Venue: arXiv cs.IT 2019
Year: 2019

Circular-shift linear network coding (LNC) is a class of vector LNC with low encoding and decoding complexities, and with local encoding kernels chosen from cyclic permutation matrices. When $L$ is a prime with primitive root $2$, it was recently shown that a scalar linear solution over GF($2^{L-1}$) induces an $L$-dimensional circular-shift linear solution at rate $(L-1)/L$. In this work, we prove that for arbitrary odd $L$, every scalar linear solution over GF($2^{m_L}$), where $m_L$ refers to the multiplicative order of $2$ modulo $L$, can induce an $L$-dimensional circular-shift linear solution at a certain rate. Based on the generalized connection, we further prove that for such $L$ with $m_L$ beyond a threshold, every multicast network has an $L$-dimensional circular-shift linear solution at rate $ϕ(L)/L$, where $ϕ(L)$ is the Euler's totient function of $L$. An efficient algorithm for constructing such a solution is designed. Finally, we prove that every multicast network is asymptotically circular-shift linearly solvable.
Fairness Behind a Veil of Ignorance: A Welfare Analysis for Automated Decision Making
Venue: arXiv cs.AI 2019
Year: 2019

We draw attention to an important, yet largely overlooked aspect of evaluating fairness for automated decision making systems---namely risk and welfare considerations. Our proposed family of measures corresponds to the long-established formulations of cardinal social welfare in economics, and is justified by the Rawlsian conception of fairness behind a veil of ignorance. The convex formulation of our welfare-based measures of fairness allows us to integrate them as a constraint into any convex loss minimization pipeline. Our empirical analysis reveals interesting trade-offs between our proposal and (a) prediction accuracy, (b) group discrimination, and (c) Dwork et al.'s notion of individual fairness. Furthermore and perhaps most importantly, our work provides both heuristic justification and empirical evidence suggesting that a lower-bound on our measures often leads to bounded inequality in algorithmic outcomes; hence presenting the first computationally feasible mechanism for bounding individual-level inequality.