OpenRaiser/Intern-Atlas huggingface dataset:
PRINS: Scalable Model Inference for Component-based System Logs
Venue: arXiv cs.SE 2022
Year: 2022

Behavioral software models play a key role in many software engineering tasks; unfortunately, these models either are not available during software development or, if available, quickly become outdated as implementations evolve. Model inference techniques have been proposed as a viable solution to extract finite state models from execution logs. However, existing techniques do not scale well when processing very large logs that can be commonly found in practice. In this paper, we address the scalability problem of inferring the model of a component-based system from large system logs, without requiring any extra information. Our model inference technique, called PRINS, follows a divide-and-conquer approach. The idea is to first infer a model of each system component from the corresponding logs; then, the individual component models are merged together taking into account the flow of events across components, as reflected in the logs. We evaluated PRINS in terms of scalability and accuracy, using nine datasets composed of logs extracted from publicly available benchmarks and a personal computer running desktop business applications. The results show that PRINS can process large logs much faster than a publicly available and well-known state-of-the-art tool, without significantly compromising the accuracy of inferred models.
Few-Shot Segmentation via Cycle-Consistent Transformer
Venue: arXiv cs.CV 2022
Year: 2022

Few-shot segmentation aims to train a segmentation model that can fast adapt to novel classes with few exemplars. The conventional training paradigm is to learn to make predictions on query images conditioned on the features from support images. Previous methods only utilized the semantic-level prototypes of support images as conditional information. These methods cannot utilize all pixel-wise support information for the query predictions, which is however critical for the segmentation task. In this paper, we focus on utilizing pixel-wise relationships between support and query images to facilitate the few-shot segmentation task. We design a novel Cycle-Consistent TRansformer (CyCTR) module to aggregate pixel-wise support features into query ones. CyCTR performs cross-attention between features from different images, i.e. support and query images. We observe that there may exist unexpected irrelevant pixel-level support features. Directly performing cross-attention may aggregate these features from support to query and bias the query features. Thus, we propose using a novel cycle-consistent attention mechanism to filter out possible harmful support features and encourage query features to attend to the most informative pixels from support images. Experiments on all few-shot segmentation benchmarks demonstrate that our proposed CyCTR leads to remarkable improvement compared to previous state-of-the-art methods. Specifically, on Pascal-$5^i$ and COCO-$20^i$ datasets, we achieve 67.5% and 45.6% mIoU for 5-shot segmentation, outperforming previous state-of-the-art methods by 5.6% and 7.1% respectively.
Fair Exploration via Axiomatic Bargaining
Venue: arXiv cs.LG 2022
Year: 2022

Exploration is often necessary in online learning to maximize long-term reward, but it comes at the cost of short-term 'regret'. We study how this cost of exploration is shared across multiple groups. For example, in a clinical trial setting, patients who are assigned a sub-optimal treatment effectively incur the cost of exploration. When patients are associated with natural groups on the basis of, say, race or age, it is natural to ask whether the cost of exploration borne by any single group is 'fair'. So motivated, we introduce the 'grouped' bandit model. We leverage the theory of axiomatic bargaining, and the Nash bargaining solution in particular, to formalize what might constitute a fair division of the cost of exploration across groups. On the one hand, we show that any regret-optimal policy strikingly results in the least fair outcome: such policies will perversely leverage the most 'disadvantaged' groups when they can. More constructively, we derive policies that are optimally fair and simultaneously enjoy a small 'price of fairness'. We illustrate the relative merits of our algorithmic framework with a case study on contextual bandits for warfarin dosing where we are concerned with the cost of exploration across multiple races and age groups.
Differentially Empirical Risk Minimization under the Fairness Lens
Venue: arXiv cs.LG 2022
Year: 2022

Differential Privacy (DP) is an important privacy-enhancing technology for private machine learning systems. It allows to measure and bound the risk associated with an individual participation in a computation. However, it was recently observed that DP learning systems may exacerbate bias and unfairness for different groups of individuals. This paper builds on these important observations and sheds light on the causes of the disparate impacts arising in the problem of differentially private empirical risk minimization. It focuses on the accuracy disparity arising among groups of individuals in two well-studied DP learning methods: output perturbation and differentially private stochastic gradient descent. The paper analyzes which data and model properties are responsible for the disproportionate impacts, why these aspects are affecting different groups disproportionately and proposes guidelines to mitigate these effects. The proposed approach is evaluated on several datasets and settings.
Algorithms from Invariants: Smoothed Analysis of Orbit Recovery over $SO(3)$
Venue: arXiv cs.DS 2022
Year: 2022

In this work we study orbit recovery over $SO(3)$, where the goal is to recover a function on the sphere from noisy, randomly rotated copies of it. We assume that the function is a linear combination of low-degree spherical harmonics. This is a natural abstraction for the problem of recovering the three-dimensional structure of a molecule through cryo-electron tomography. For provably learning the parameters of a generative model, the method of moments is the standard workhorse of theoretical machine learning. It turns out that there is a natural incarnation of the method of moments for orbit recovery based on invariant theory. Bandeira et al. [BBSK+18] used invariant theory to give tight bounds on the sample complexity in terms of the noise level. However many of the key challenges remain: Can we prove bounds on the sample complexity that are polynomial in $n$, the dimension of the signal? The bounds in [BBSK+18] hide constants that have an unspecified dependence on $n$ and only hold in the limit as $σ^2 \rightarrow \infty$ where $σ^2$ is the variance of the noise. Moreover can we give efficient algorithms? We revisit these challenges from the perspective of smoothed analysis, where we assume that the coefficients of the signal, in the basis of spherical harmonics, are subject to small random perturbations. Our main result is a quasi-polynomial time algorithm for orbit recovery over $SO(3)$ in this model. Our approach is based on frequency marching, which sequentially solves linear systems to find higher degree coefficients. Our main technical contribution is to show that these linear systems have unique solutions, are well-conditioned, and that the error can be made to compound over at most a logarithmic number of rounds. We believe that our work takes an important first step towards uncovering the algorithmic implications of invariant theory.
Location and audience selection for maximizing social influence
Venue: arXiv cs.SI 2022
Year: 2022

Viral marketing campaigns target primarily those individuals who are central in social networks and hence have social influence. Marketing events, however, may attract diverse audience. Despite the importance of event marketing, the influence of heterogeneous target groups is not well understood yet. In this paper, we define the Spreading Potential (SP) problem in which different sets of agents need to evaluated and compared based on their social influence. A typical application of SP is choosing locations for a series of marketing events. The SP problem is different from the well-known Influence Maximization (IM) problem in two aspects. Firstly, it deals with sets rather than nodes. Secondly, the sets are diverse, composed by a mixture of influential and ordinary agents. Thus, SP needs to assess the contribution of ordinary agents too, while IM only aims to find top spreaders. We provide a systemic test for ranking influence measures in the SP problem based on node sampling and on a novel statistical method, the Sum of Ranking Differences. Using a Linear Threshold diffusion model on an online social network, we evaluate seven network measures of social influence. We demonstrate that the statistical assessment of these influence measures is remarkably different in the SP problem, when low-ranked individuals are present, from the IM problem, when we focus on the algorithm's top choices exclusively.
Trajectory Optimization of Chance-Constrained Nonlinear Stochastic Systems for Motion Planning Under Uncertainty
Venue: arXiv cs.RO 2022
Year: 2022

We present gPC-SCP: Generalized Polynomial Chaos-based Sequential Convex Programming to compute a sub-optimal solution for a continuous-time chance-constrained stochastic nonlinear optimal control (SNOC) problem. The approach enables motion planning for robotic systems under uncertainty. The gPC-SCP method involves two steps. The first step is to derive a surrogate problem of \emph{deterministic} nonlinear optimal control (DNOC) with convex constraints by using gPC expansion and the distributionally-robust convex subset of the chance constraints. The second step is to solve the DNOC problem using sequential convex programming for trajectory generation and control. We prove that in the unconstrained case, the optimal value of the DNOC converges to that of SNOC asymptotically and that any feasible solution of the constrained DNOC is a feasible solution of the chance-constrained SNOC. We also present the predictor-corrector extension (gPC-SCP$^\mathrm{PC}$) for real-time motion trajectory generation in the presence of stochastic uncertainty. In the gPC-SCP$^\mathrm{PC}$ method, we first predict the uncertainty using the gPC method and then optimize the motion plan to accommodate the uncertainty. We empirically demonstrate the efficacy of the gPC-SCP and the gPC-SCP$^\mathrm{PC}$ methods for the following two test cases: 1) collision checking under uncertainty in actuation and physical parameters and 2) collision checking with stochastic obstacle model for 3DOF and 6DOF robotic systems. We validate the effectiveness of the gPC-SCP method on the 3DOF robotic spacecraft testbed.
A Convergence Theory for SVGD in the Population Limit under Talagrand's Inequality T1
Venue: arXiv cs.LG 2022
Year: 2022

Stein Variational Gradient Descent (SVGD) is an algorithm for sampling from a target density which is known up to a multiplicative constant. Although SVGD is a popular algorithm in practice, its theoretical study is limited to a few recent works. We study the convergence of SVGD in the population limit, (i.e., with an infinite number of particles) to sample from a non-logconcave target distribution satisfying Talagrand's inequality T1. We first establish the convergence of the algorithm. Then, we establish a dimension-dependent complexity bound in terms of the Kernelized Stein Discrepancy (KSD). Unlike existing works, we do not assume that the KSD is bounded along the trajectory of the algorithm. Our approach relies on interpreting SVGD as a gradient descent over a space of probability measures.
Neural Implicit 3D Shapes from Single Images with Spatial Patterns
Venue: arXiv cs.CV 2022
Year: 2022

Neural implicit functions have achieved impressive results for reconstructing 3D shapes from single images. However, the image features for describing 3D point samplings of implicit functions are less effective when significant variations of occlusions, views, and appearances exist from the image. To better encode image features, we study a geometry-aware convolutional kernel to leverage geometric relationships of point samplings by the proposed \emph{spatial pattern}, i.e., a structured point set. Specifically, the kernel operates at 2D projections of 3D points from the spatial pattern. Supported by the spatial pattern, the 2D kernel encodes geometric information that is crucial for 3D reconstruction tasks, while traditional ones mainly consider appearance information. Furthermore, to enable the network to discover more adaptive spatial patterns for further capturing non-local contextual information, the kernel is devised to be deformable manipulated by a spatial pattern generator. Experimental results on both synthetic and real datasets demonstrate the superiority of the proposed method. Pre-trained models, codes, and data are available at https://github.com/yixin26/SVR-SP.
FlexParser -- the adaptive log file parser for continuous results in a changing world
Venue: arXiv cs.LG 2022
Year: 2022

Any modern system writes events into files, called log files. Those contain crucial information which are subject to various analyses. Examples range from cybersecurity, intrusion detection over usage analyses to trouble shooting. Before data analysis is possible, desired information needs to be extracted first out of the semi-structured log messages. State-of-the-art event parsing often assumes static log events. However, any modern system is updated consistently and with updates also log file structures can change. We call those changes "mutation" and study parsing performance for different mutation cases. Latest research discovers mutations using anomaly detection post mortem, however, does not cover actual continuous parsing. Thus, we propose a novel and flexible parser, called FlexParser, which can extract desired values despite gradual changes in the log messages. It implies basic text preprocessing followed by a supervised Deep Learning method. We train a stateful LSTM on parsing one event per data set. Statefulness enforces the model to learn log message structures across several examples. Our model was tested on seven different, publicly available log file data sets and various kinds of mutations. Exhibiting an average F1-Score of 0.98, it outperforms other Deep Learning methods as well as state-of-the-art unsupervised parsers.
An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL
Venue: arXiv cs.DS 2022
Year: 2022

In general, a graph modification problem is defined by a graph modification operation $\boxtimes$ and a target graph property ${\cal P}$. Typically, the modification operation $\boxtimes$ may be vertex removal}, edge removal}, edge contraction}, or edge addition and the question is, given a graph $G$ and an integer $k$, whether it is possible to transform $G$ to a graph in ${\cal P}$ after applying $k$ times the operation $\boxtimes$ on $G$. This problem has been extensively studied for particilar instantiations of $\boxtimes$ and ${\cal P}$. In this paper we consider the general property ${\cal P}_{ϕ}$ of being planar and, moreover, being a model of some First-Order Logic sentence $ϕ$ (an FOL-sentence). We call the corresponding meta-problem Graph $\boxtimes$-Modification to Planarity and $ϕ$ and prove the following algorithmic meta-theorem: there exists a function $f:\Bbb{N}^{2}\to\Bbb{N}$ such that, for every $\boxtimes$ and every FOL sentence $ϕ$, the Graph $\boxtimes$-Modification to Planarity and $ϕ$ is solvable in $f(k,|ϕ|)\cdot n^2$ time. The proof constitutes a hybrid of two different classic techniques in graph algorithms. The first is the irrelevant vertex technique that is typically used in the context of Graph Minors and deals with properties such as planarity or surface-embeddability (that are not FOL-expressible) and the second is the use of Gaifman's Locality Theorem that is the theoretical base for the meta-algorithmic study of FOL-expressible problems.
Self-Supervision & Meta-Learning for One-Shot Unsupervised Cross-Domain Detection
Venue: arXiv cs.CV 2022
Year: 2022

Deep detection approaches are powerful in controlled conditions, but appear brittle and fail when source models are used off-the-shelf on unseen domains. Most of the existing works on domain adaptation simplify the setting and access jointly both a large source dataset and a sizable amount of target samples. However this scenario is unrealistic in many practical cases as when monitoring image feeds from social media: only a pretrained source model is available and every target image uploaded by the users belongs to a different domain not foreseen during training. We address this challenging setting by presenting an object detection algorithm able to exploit a pre-trained source model and perform unsupervised adaptation by using only one target sample seen at test time. Our multi-task architecture includes a self-supervised branch that we exploit to meta-train the whole model with single-sample cross-domain episodes, and prepare to the test condition. At deployment time the self-supervised task is iteratively solved on any incoming sample to one-shot adapt on it. We introduce a new dataset of social media image feeds and present a thorough benchmark with the most recent cross-domain detection methods showing the advantages of our approach.
Learning by Transference: Training Graph Neural Networks on Growing Graphs
Venue: arXiv cs.LG 2022
Year: 2022

Graph neural networks (GNNs) use graph convolutions to exploit network invariances and learn meaningful feature representations from network data. However, on large-scale graphs convolutions incur in high computational cost, leading to scalability limitations. Leveraging the graphon -- the limit object of a graph -- in this paper we consider the problem of learning a graphon neural network (WNN) -- the limit object of a GNN -- by training GNNs on graphs sampled from the graphon. Under smoothness conditions, we show that: (i) the expected distance between the learning steps on the GNN and on the WNN decreases asymptotically with the size of the graph, and (ii) when training on a sequence of growing graphs, gradient descent follows the learning direction of the WNN. Inspired by these results, we propose a novel algorithm to learn GNNs on large-scale graphs that, starting from a moderate number of nodes, successively increases the size of the graph during training. This algorithm is further benchmarked on a decentralized control problem, where it retains comparable performance to its large-scale counterpart at a reduced computational cost.
Acoustic Power Management by Swarms of Microscopic Robots
Venue: arXiv cs.RO 2022
Year: 2022

Microscopic robots in the body could harvest energy from ultrasound to provide on-board control of autonomous behaviors such as measuring and communicating diagnostic information and precisely delivering drugs. This paper evaluates the acoustic power available to micron-size robots that collect energy using pistons. Acoustic attenuation and viscous drag on the pistons are the major limitations on the available power. Frequencies around 100kHz can deliver hundreds of picowatts to a robot in low-attenuation tissue within about 10cm of transducers on the skin, but much less in high-attenuation tissue such as a lung. However, applications of microscopic robots could involve such large numbers that the robots significantly increase attenuation, thereby reducing power for robots deep in the body. This paper describes how robots can collectively manage where and when they harvest energy to mitigate this attenuation so that a swarm of a few hundred billion robots can provide tens of picowatts to each robot, on average.
Expressivity of Emergent Language is a Trade-off between Contextual Complexity and Unpredictability
Venue: arXiv cs.CL 2022
Year: 2022

Researchers are using deep learning models to explore the emergence of language in various language games, where agents interact and develop an emergent language to solve tasks. We focus on the factors that determine the expressivity of emergent languages, which reflects the amount of information about input spaces those languages are capable of encoding. We measure the expressivity of emergent languages based on the generalisation performance across different games, and demonstrate that the expressivity of emergent languages is a trade-off between the complexity and unpredictability of the context those languages emerged from. Another contribution of this work is the discovery of message type collapse, i.e. the number of unique messages is lower than that of inputs. We also show that using the contrastive loss proposed by Chen et al. (2020) can alleviate this problem.
Theoretically Motivated Data Augmentation and Regularization for Portfolio Construction
Venue: arXiv cs.LG 2022
Year: 2022

The task we consider is portfolio construction in a speculative market, a fundamental problem in modern finance. While various empirical works now exist to explore deep learning in finance, the theory side is almost non-existent. In this work, we focus on developing a theoretical framework for understanding the use of data augmentation for deep-learning-based approaches to quantitative finance. The proposed theory clarifies the role and necessity of data augmentation for finance; moreover, our theory implies that a simple algorithm of injecting a random noise of strength $\sqrt{|r_{t-1}|}$ to the observed return $r_{t}$ is better than not injecting any noise and a few other financially irrelevant data augmentation techniques.
White Paper Assistance: A Step Forward Beyond the Shortcut Learning
Venue: arXiv cs.CV 2022
Year: 2022

The promising performances of CNNs often overshadow the need to examine whether they are doing in the way we are actually interested. We show through experiments that even over-parameterized models would still solve a dataset by recklessly leveraging spurious correlations, or so-called 'shortcuts'. To combat with this unintended propensity, we borrow the idea of printer test page and propose a novel approach called White Paper Assistance. Our proposed method involves the white paper to detect the extent to which the model has preference for certain characterized patterns and alleviates it by forcing the model to make a random guess on the white paper. We show the consistent accuracy improvements that are manifest in various architectures, datasets and combinations with other techniques. Experiments have also demonstrated the versatility of our approach on fine-grained recognition, imbalanced classification and robustness to corruptions.
Learning from Multiple Noisy Partial Labelers
Venue: arXiv cs.LG 2022
Year: 2022

Programmatic weak supervision creates models without hand-labeled training data by combining the outputs of heuristic labelers. Existing frameworks make the restrictive assumption that labelers output a single class label. Enabling users to create partial labelers that output subsets of possible class labels would greatly expand the expressivity of programmatic weak supervision. We introduce this capability by defining a probabilistic generative model that can estimate the underlying accuracies of multiple noisy partial labelers without ground truth labels. We show how to scale up learning, for example learning on 100k examples in one minute, a 300x speed up compared to a naive implementation. We also prove that this class of models is generically identifiable up to label swapping under mild conditions. We evaluate our framework on three text classification and six object classification tasks. On text tasks, adding partial labels increases average accuracy by 8.6 percentage points. On image tasks, we show that partial labels allow us to approach some zero-shot object classification problems with programmatic weak supervision by using class attributes as partial labelers. On these tasks, our framework has accuracy comparable to recent embedding-based zero-shot learning methods, while using only pre-trained attribute detectors.