OpenRaiser/Intern-Atlas huggingface dataset:
Revisiting L21-norm Robustness with Vector Outlier Regularization
Venue: arXiv cs.CV 2020
Year: 2020

In many real-world applications, data usually contain outliers. One popular approach is to use L2,1 norm function as a robust error/loss function. However, the robustness of L2,1 norm function is not well understood so far. In this paper, we propose a new Vector Outlier Regularization (VOR) framework to understand and analyze the robustness of L2,1 norm function. Our VOR function defines a data point to be outlier if it is outside a threshold with respect to a theoretical prediction, and regularize it-pull it back to the threshold line. We then prove that L2,1 function is the limiting case of this VOR with the usual least square/L2 error function as the threshold shrinks to zero. One interesting property of VOR is that how far an outlier lies away from its theoretically predicted value does not affect the final regularization and analysis results. This VOR property unmasks one of the most peculiar property of L2,1 norm function: The effects of outliers seem to be independent of how outlying they are-if an outlier is moved further away from the intrinsic manifold/subspace, the final analysis results do not change. VOR provides a new way to understand and analyze the robustness of L2,1 norm function. Applying VOR to matrix factorization leads to a new VORPCA model. We give a comprehensive comparison with trace-norm based L21-norm PCA to demonstrate the advantages of VORPCA.
Indefinite Kernel Logistic Regression with Concave-inexact-convex Procedure
Venue: arXiv cs.LG 2020
Year: 2020

In kernel methods, the kernels are often required to be positive definite, which restricts the use of many indefinite kernels. To consider those non-positive definite kernels, in this paper, we aim to build an indefinite kernel learning framework for kernel logistic regression. The proposed indefinite kernel logistic regression (IKLR) model is analysed in the Reproducing Kernel Kre\uın Spaces (RKKS) and then becomes non-convex. Using the positive decomposition of a non-positive definite kernel, the derived IKLR model can be decomposed into the difference of two convex functions. Accordingly, a concave-convex procedure is introduced to solve the non-convex optimization problem. Since the concave-convex procedure has to solve a sub-problem in each iteration, we propose a concave-inexact-convex procedure (CCICP) algorithm with an inexact solving scheme to accelerate the solving process. Besides, we propose a stochastic variant of CCICP to efficiently obtain a proximal solution, which achieves the similar purpose with the inexact solving scheme in CCICP. The convergence analyses of the above two variants of concave-convex procedure are conducted. By doing so, our method works effectively not only under a deterministic setting but also under a stochastic setting. Experimental results on several benchmarks suggest that the proposed IKLR model performs favorably against the standard (positive-definite) kernel logistic regression and other competitive indefinite learning based algorithms.
A Probabilistic Calculus of Cyber-Physical Systems
Venue: arXiv cs.LO 2020
Year: 2020

We propose a hybrid probabilistic process calculus for modelling and reasoning on cyber-physical systems (CPSs). The dynamics of the calculus is expressed in terms of a probabilistic labelled transition system in the SOS style of Plotkin. This is used to define a bisimulation-based probabilistic behavioural semantics which supports compositional reasonings. For a more careful comparison between CPSs, we provide two compositional probabilistic metrics to formalise the notion of behavioural distance between systems, also in the case of bounded computations. Finally, we provide a non-trivial case study, taken from an engineering application, and use it to illustrate our definitions and our compositional behavioural theory for CPSs.
Interference-Aware Opportunistic Random Access in Dense IoT Networks
Venue: arXiv cs.IT 2020
Year: 2020

It is a challenging task to design a random access protocol that achieves the optimal throughput in multi-cell random access with decentralized transmission due to the difficulty of coordination. In this paper, we present a decentralized interference-aware opportunistic random access (IA-ORA) protocol that enables us to obtain the optimal throughput scaling in an ultra-dense multi-cell random access network with one access point (AP) and a number of users. In sharp contrast to opportunistic scheduling for cellular multiple access where users are selected by base stations, under the IA-ORA protocol, each user opportunistically transmits with a predefined physical layer (PHY) data rate in a decentralized manner if not only the desired signal power to the serving AP is sufficiently large but also the generating interference leakage power to the other APs is sufficiently small (i.e., two threshold conditions are fulfilled). As a main result, it is shown that the optimal aggregate throughput scaling (i.e., the MAC throughput of $\frac{1}{e}$ in a cell and the power gain) is achieved in a high signal-to-noise ratio regime if the number of per-cell users exceeds some level. Additionally, it is numerically demonstrated via computer simulations that under practical settings, the proposed IA-ORA protocol outperforms conventional opportunistic random access protocols in terms of aggregate throughput.
Arrangements of Pseudocircles: Triangles and Drawings
Venue: arXiv cs.CG 2020
Year: 2020

A pseudocircle is a simple closed curve on the sphere or in the plane. The study of arrangements of pseudocircles was initiated by Grünbaum, who defined them as collections of simple closed curves that pairwise intersect in exactly two crossings. Grünbaum conjectured that the number of triangular cells $p_3$ in digon-free arrangements of $n$ pairwise intersecting pseudocircles is at least $2n-4$. We present examples to disprove this conjecture. With a recursive construction based on an example with $12$ pseudocircles and $16$ triangles we obtain a family with $p_3(\mathcal{A})/n \to 16/11 = 1.\overline{45}$. We expect that the lower bound $p_3(\mathcal{A}) \geq 4n/3$ is tight for infinitely many simple arrangements. It may however be true that all digon-free arrangements of $n$ pairwise intersecting circles have at least $2n-4$ triangles. For pairwise intersecting arrangements with digons we have a lower bound of $p_3 \geq 2n/3$, and conjecture that $p_3 \geq n-1$. Concerning the maximum number of triangles in pairwise intersecting arrangements of pseudocircles, we show that $p_3 \le 2n^2/3 +O(n)$. This is essentially best possible because there are families of pairwise intersecting arrangements of $n$ pseudocircles with $p_3/n^2 \to 2/3$. The paper contains many drawings of arrangements of pseudocircles and a good fraction of these drawings was produced automatically from the combinatorial data produced by our generation algorithm. In the final section we describe some aspects of the drawing algorithm.
Recovering Structured Data From Superimposed Non-Linear Measurements
Venue: arXiv cs.IT 2020
Year: 2020

This work deals with the problem of distributed data acquisition under non-linear communication constraints. More specifically, we consider a model setup where $M$ distributed nodes take individual measurements of an unknown structured source vector $x_0 \in \mathbb{R}^n$, communicating their readings simultaneously to a central receiver. Since this procedure involves collisions and is usually imperfect, the receiver measures a superposition of non-linearly distorted signals. In a first step, we will show that an $s$-sparse vector $x_0$ can be successfully recovered from $O(s \cdot\log(2n/s))$ of such superimposed measurements, using a traditional Lasso estimator that does not rely on any knowledge about the non-linear corruptions. This direct method however fails to work for several "uncalibrated" system configurations. These blind reconstruction tasks can be easily handled with the $\ell^{1,2}$-Group-Lasso, but coming along with an increased sampling rate of $O(s\cdot \max\{M, \log(2n/s) \})$ observations - in fact, the purpose of this lifting strategy is to extend a certain class of bilinear inverse problems to non-linear acquisition. Our two algorithmic approaches are a special instance of a more abstract framework which includes sub-Gaussian measurement designs as well as general (convex) structural constraints. These results are of independent interest for various recovery and learning tasks, as they apply to arbitrary non-linear observation models. Finally, to illustrate the practical scope of our theoretical findings, an application to wireless sensor networks is discussed, which actually serves as the prototypical example of our methodology.
An Adversarial Model for Scheduling with Testing
Venue: arXiv cs.DS 2020
Year: 2020

We introduce a novel adversarial model for scheduling with explorable uncertainty. In this model, the processing time of a job can potentially be reduced (by an a priori unknown amount) by testing the job. Testing a job $j$ takes one unit of time and may reduce its processing time from the given upper limit $\bar{p}_j$ (which is the time taken to execute the job if it is not tested) to any value between $0$ and $\bar{p}_j$. This setting is motivated e.g. by applications where a code optimizer can be run on a job before executing it. We consider the objective of minimizing the sum of completion times on a single machine. All jobs are available from the start, but the reduction in their processing times as a result of testing is unknown, making this an online problem that is amenable to competitive analysis. The need to balance the time spent on tests and the time spent on job executions adds a novel flavor to the problem. We give the first and nearly tight lower and upper bounds on the competitive ratio for deterministic and randomized algorithms. We also show that minimizing the makespan is a considerably easier problem for which we give optimal deterministic and randomized online algorithms.
A Zero-Positive Learning Approach for Diagnosing Software Performance Regressions
Venue: arXiv cs.SE 2020
Year: 2020

The field of machine programming (MP), the automation of the development of software, is making notable research advances. This is, in part, due to the emergence of a wide range of novel techniques in machine learning. In this paper, we apply MP to the automation of software performance regression testing. A performance regression is a software performance degradation caused by a code change. We present AutoPerf - a novel approach to automate regression testing that utilizes three core techniques: (i) zero-positive learning, (ii) autoencoders, and (iii) hardware telemetry. We demonstrate AutoPerf's generality and efficacy against 3 types of performance regressions across 10 real performance bugs in 7 benchmark and open-source programs. On average, AutoPerf exhibits 4% profiling overhead and accurately diagnoses more performance bugs than prior state-of-the-art approaches. Thus far, AutoPerf has produced no false negatives.
Exact Computation of a Manifold Metric, via Lipschitz Embeddings and Shortest Paths on a Graph
Venue: arXiv cs.CG 2020
Year: 2020

Data-sensitive metrics adapt distances locally based the density of data points with the goal of aligning distances and some notion of similarity. In this paper, we give the first exact algorithm for computing a data-sensitive metric called the nearest neighbor metric. In fact, we prove the surprising result that a previously published $3$-approximation is an exact algorithm. The nearest neighbor metric can be viewed as a special case of a density-based distance used in machine learning, or it can be seen as an example of a manifold metric. Previous computational research on such metrics despaired of computing exact distances on account of the apparent difficulty of minimizing over all continuous paths between a pair of points. We leverage the exact computation of the nearest neighbor metric to compute sparse spanners and persistent homology. We also explore the behavior of the metric built from point sets drawn from an underlying distribution and consider the more general case of inputs that are finite collections of path-connected compact sets. The main results connect several classical theories such as the conformal change of Riemannian metrics, the theory of positive definite functions of Schoenberg, and screw function theory of Schoenberg and Von Neumann. We develop novel proof techniques based on the combination of screw functions and Lipschitz extensions that may be of independent interest.
Multiagent Maximum Coverage Problems: The Trade-off Between Anarchy and Stability
Venue: arXiv cs.GT 2020
Year: 2020

The price of anarchy and price of stability are three well-studied performance metrics that seek to characterize the inefficiency of equilibria in distributed systems. The distinction between these two performance metrics centers on the equilibria that they focus on: the price of anarchy characterizes the quality of the worst-performing equilibria, while the price of stability characterizes the quality of the best-performing equilibria. While much of the literature focuses on these metrics from an analysis perspective, in this work we consider these performance metrics from a design perspective. Specifically, we focus on the setting where a system operator is tasked with designing local utility functions to optimize these performance metrics in a class of games termed covering games. Our main result characterizes a fundamental trade-off between the price of anarchy and price of stability in the form of a fully explicit Pareto frontier. Within this setup, optimizing the price of anarchy comes directly at the expense of the price of stability (and vice versa). Our second results demonstrates how a system-operator could incorporate an additional piece of system-level information into the design of the agents' utility functions to breach these limitations and improve the system's performance. This valuable piece of system-level information pertains to the performance of worst performing agent in the system.
Combining Learned and Analytical Models for Predicting Action Effects from Sensory Data
Venue: arXiv cs.RO 2020
Year: 2020

One of the most basic skills a robot should possess is predicting the effect of physical interactions with objects in the environment. This enables optimal action selection to reach a certain goal state. Traditionally, dynamics are approximated by physics-based analytical models. These models rely on specific state representations that may be hard to obtain from raw sensory data, especially if no knowledge of the object shape is assumed. More recently, we have seen learning approaches that can predict the effect of complex physical interactions directly from sensory input. It is however an open question how far these models generalize beyond their training data. In this work, we investigate the advantages and limitations of neural network based learning approaches for predicting the effects of actions based on sensory input and show how analytical and learned models can be combined to leverage the best of both worlds. As physical interaction task, we use planar pushing, for which there exists a well-known analytical model and a large real-world dataset. We propose to use a convolutional neural network to convert raw depth images or organized point clouds into a suitable representation for the analytical model and compare this approach to using neural networks for both, perception and prediction. A systematic evaluation of the proposed approach on a very large real-world dataset shows two main advantages of the hybrid architecture. Compared to a pure neural network, it significantly (i) reduces required training data and (ii) improves generalization to novel physical interaction.
Generating Reflectance Curves from sRGB Triplets
Venue: arXiv cs.CV 2020
Year: 2020

The color sensation evoked by an object depends on both the spectral power distribution of the illumination and the reflectance properties of the object being illuminated. The color sensation can be characterized by three color-space values, such as XYZ, RGB, HSV, L*a*b*, etc. It is straightforward to compute the three values given the illuminant and reflectance curves. The converse process of computing a reflectance curve given the color-space values and the illuminant is complicated by the fact that an infinite number of different reflectance curves can give rise to a single set of color-space values (metamerism). This paper presents five algorithms for generating a reflectance curve from a specified sRGB triplet, written for a general audience. The algorithms are designed to generate reflectance curves that are similar to those found with naturally occurring colored objects. The computed reflectance curves are compared to a database of thousands of reflectance curves measured from paints and pigments available both commercially and in nature, and the similarity is quantified. One particularly useful application of these algorithms is in the field of computer graphics, where modeling color transformations sometimes requires wavelength-specific information, such as when modeling subtractive color mixture.
SMR: Medical Knowledge Graph Embedding for Safe Medicine Recommendation
Venue: arXiv cs.IR 2020
Year: 2020

Most of the existing medicine recommendation systems that are mainly based on electronic medical records (EMRs) are significantly assisting doctors to make better clinical decisions benefiting both patients and caregivers. Even though the growth of EMRs is at a lighting fast speed in the era of big data, content limitations in EMRs restrain the existed recommendation systems to reflect relevant medical facts, such as drug-drug interactions. Many medical knowledge graphs that contain drug-related information, such as DrugBank, may give hope for the recommendation systems. However, the direct use of these knowledge graphs in the systems suffers from robustness caused by the incompleteness of the graphs. To address these challenges, we stand on recent advances in graph embedding learning techniques and propose a novel framework, called Safe Medicine Recommendation (SMR), in this paper. Specifically, SMR first constructs a high-quality heterogeneous graph by bridging EMRs (MIMIC-III) and medical knowledge graphs (ICD-9 ontology and DrugBank). Then, SMR jointly embeds diseases, medicines, patients, and their corresponding relations into a shared lower dimensional space. Finally, SMR uses the embeddings to decompose the medicine recommendation into a link prediction process while considering the patient's diagnoses and adverse drug reactions. To our best knowledge, SMR is the first to learn embeddings of a patient-disease-medicine graph for medicine recommendation in the world. Extensive experiments on real datasets are conducted to evaluate the effectiveness of proposed framework.
Targeting Interventions in Networks
Venue: arXiv cs.GT 2020
Year: 2020

We study games in which a network mediates strategic spillovers and externalities among the players. How does a planner optimally target interventions that change individuals' private returns to investment? We analyze this question by decomposing any intervention into orthogonal principal components, which are determined by the network and are ordered according to their associated eigenvalues. There is a close connection between the nature of spillovers and the representation of various principal components in the optimal intervention. In games of strategic complements (substitutes), interventions place more weight on the top (bottom) principal components, which reflect more global (local) network structure. For large budgets, optimal interventions are simple -- they involve a single principal component.
Preserving Injectivity under Subgaussian Mappings and Its Application to Compressed Sensing
Venue: arXiv cs.IT 2020
Year: 2020

The field of compressed sensing has become a major tool in high-dimensional analysis, with the realization that vectors can be recovered from relatively very few linear measurements as long as the vectors lie in a low-dimensional structure, typically the vectors that are zero in most coordinates with respect to a basis. However, there are many applications where we instead want to recover vectors that are sparse with respect to a dictionary rather than a basis. That is, we assume the vectors are linear combinations of at most $s$ columns of a $d \times n$ matrix $\mathbf{D}$, where $s$ is very small relative to $n$ and the columns of $\mathbf{D}$ form a (typically overcomplete) spanning set. In this direction, we show that as a matrix $\mathbf{D}$ stays bounded away from zero in norm on a set $S$ and a provided map ${\boldsymbol Φ}$ comprised of i.i.d. subgaussian rows has number of measurements at least proportional to the square of $w(\mathbf{D}S)$, the Gaussian width of the related set $\mathbf{D}S$, then with high probability the composition ${\boldsymbol Φ} \mathbf{D}$ also stays bounded away from zero. As a specific application, we obtain that the null space property of order $s$ is preserved under such subgaussian maps with high probability. Consequently, we obtain stable recovery guarantees for dictionary-sparse signals via the $\ell_1$-synthesis method with only $O(s\log(n/s))$ random measurements and a minimal condition on $\mathbf{D}$, which complements the compressed sensing literature.
Robust registration of medical images in the presence of spatially-varying noise
Venue: arXiv cs.CV 2020
Year: 2020

Spatially-varying intensity noise is a common source of distortion in medical images. Bias field noise is one example of such a distortion that is often present in the magnetic resonance (MR) images or other modalities such as retina images. In this paper, we first show that the bias field noise can be considerably reduced using Empirical Mode Decomposition (EMD) technique. EMD is a multi-resolution tool that decomposes a signal into several principle patterns and residual components. We show that the spatially-varying noise is highly expressed in the residual component of the EMD and could be filtered out. Then, we propose two hierarchical multi-resolution EMD-based algorithms for robust registration of images in the presence of spatially varying noise. One algorithm (LR-EMD) is based on registration of EMD feature-maps from both floating and reference images in various resolution levels. In the second algorithm (AFR-EMD), we first extract an average feature-map based on EMD from both floating and reference images. Then, we use a simple hierarchical multi-resolution algorithm to register the average feature-maps. For the brain MR images, both algorithms achieve lower error rate and higher convergence percentage compared to the intensity-based hierarchical registration. Specifically, using mutual information as the similarity measure, AFR-EMD achieves 42% lower error rate in intensity and 52% lower error rate in transformation compared to intensity-based hierarchical registration. For LR-EMD, the error rate is 32% lower for the intensity and 41% lower for the transformation. Furthermore, we demonstrate that our proposed algorithms improve the registration of retina images in the presence of spatially varying noise.
New Covering Array Numbers
Venue: arXiv cs.DM 2020
Year: 2020

A covering array CA(N; t; k; v) is an N x k array on v symbols such that every N x t subarray contains as a row each t-tuple over the v symbols at least once. The minimum N for which a CA(N; t; k; v) exists is called the covering array number of t, k, and v, and it is denoted by CAN(t; k; v). In this work we prove new CANs using an optimized procedure.