OpenRaiser/Intern-Atlas huggingface dataset:
Optimizing Safe Flow Decompositions in DAGs
Venue: arXiv cs.DS 2022
Year: 2022

Network flow is one of the most studied combinatorial optimization problems having innumerable applications. Any flow on a directed acyclic graph $G$ having $n$ vertices and $m$ edges can be decomposed into a set of $O(m)$ paths. In some applications, each solution (decomposition) corresponds to some particular data that generated the original flow. Given the possibility of multiple optimal solutions, no optimization criterion ensures the identification of the correct decomposition. Hence, recently flow decomposition was studied [RECOMB22] in the Safe and Complete framework, particularly for RNA Assembly. They presented a characterization of the safe paths, resulting in an $O(mn+out_R)$ time algorithm to compute all safe paths, where $out_R$ is the size of the raw output reporting each safe path explicitly. They also showed that $out_R$ can be $Ω(mn^2)$ in the worst case but $O(m)$ in the best case. Hence, they further presented an algorithm to report a concise representation of the output $out_C$ in $O(mn+out_C)$ time, where $out_C$ can be $Ω(mn)$ in the worst case but $O(m)$ in the best case. In this work, we study how different safe paths interact, resulting in optimal output-sensitive algorithms requiring $O(m+out_R)$ and $O(m+out_C)$ time for computing the existing representations of the safe paths. Further, we propose a new characterization of the safe paths resulting in the {\em optimal} representation of safe paths $out_O$, which can be $Ω(mn)$ in the worst case but requires optimal $O(1)$ space for every safe path reported, with a near-optimal computation algorithm. Overall we further develop the theory of safe and complete solutions for the flow decomposition problem, giving an optimal algorithm for the explicit representation, and a near-optimal algorithm for the optimal representation of the safe paths
Improved LP-based Approximation Algorithms for Facility Location with Hard Capacities
Venue: arXiv cs.DS 2022
Year: 2022

The Capacitated Facility Location (CFL), a long-standing classic problem with intriguing approximability and literature dated back to the 90s, is considered. Following the open question posted in [Williamson and Shmoys, 2011] and the notable work due to [An et al., FOCS~2014], we present an LP-based approximation algorithm with a guarantee of $(10+\sqrt{67})/2 \approx 9.0927$, a significant improvement upon the previous LP-based ratio of $288$ due to An et al. in 2014. Our contribution for this part is a simple and elegant rounding algorithm that brings clear insights for the MFN relaxation and the CFL problem. For CFL with cardinality facility cost (CFL-CFC), we present an LP-based $4$-approximation algorithm, which improves upon the decades-old ratio of 5 due to Levi et al. that ages up since 2004. Prior to our work, it was not clear whether or not LP-based methods can be used to provide a guarantee better than 5 for the CFL problem, even for restricted versions of this problem, for which natural LPs are already known to have small integrality gaps. Our rounding algorithm provides the first affirmative answer on the case with cadinality facility cost.
Multimodal Data Visualization and Denoising with Integrated Diffusion
Venue: arXiv cs.LG 2022
Year: 2022

We propose a method called integrated diffusion for combining multimodal datasets, or data gathered via several different measurements on the same system, to create a joint data diffusion operator. As real world data suffers from both local and global noise, we introduce mechanisms to optimally calculate a diffusion operator that reflects the combined information from both modalities. We show the utility of this joint operator in data denoising, visualization and clustering, performing better than other methods to integrate and analyze multimodal data. We apply our method to multi-omic data generated from blood cells, measuring both gene expression and chromatin accessibility. Our approach better visualizes the geometry of the joint data, captures known cross-modality associations and identifies known cellular populations. More generally, integrated diffusion is broadly applicable to multimodal datasets generated in many medical and biological systems.
Machine Learning for Mechanical Ventilation Control
Venue: arXiv cs.LG 2022
Year: 2022

We consider the problem of controlling an invasive mechanical ventilator for pressure-controlled ventilation: a controller must let air in and out of a sedated patient's lungs according to a trajectory of airway pressures specified by a clinician. Hand-tuned PID controllers and similar variants have comprised the industry standard for decades, yet can behave poorly by over- or under-shooting their target or oscillating rapidly. We consider a data-driven machine learning approach: First, we train a simulator based on data we collect from an artificial lung. Then, we train deep neural network controllers on these simulators.We show that our controllers are able to track target pressure waveforms significantly better than PID controllers. We further show that a learned controller generalizes across lungs with varying characteristics much more readily than PID controllers do.
Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization
Venue: arXiv cs.LG 2022
Year: 2022

Recently there has been increased interest in semi-supervised classification in the presence of graphical information. A new class of learning models has emerged that relies, at its most basic level, on classifying the data after first applying a graph convolution. To understand the merits of this approach, we study the classification of a mixture of Gaussians, where the data corresponds to the node attributes of a stochastic block model. We show that graph convolution extends the regime in which the data is linearly separable by a factor of roughly $1/\sqrt{D}$, where $D$ is the expected degree of a node, as compared to the mixture model data on its own. Furthermore, we find that the linear classifier obtained by minimizing the cross-entropy loss after the graph convolution generalizes to out-of-distribution data where the unseen data can have different intra- and inter-class edge probabilities from the training data.
Model-free Representation Learning and Exploration in Low-rank MDPs
Venue: arXiv cs.LG 2022
Year: 2022

The low rank MDP has emerged as an important model for studying representation learning and exploration in reinforcement learning. With a known representation, several model-free exploration strategies exist. In contrast, all algorithms for the unknown representation setting are model-based, thereby requiring the ability to model the full dynamics. In this work, we present the first model-free representation learning algorithms for low rank MDPs. The key algorithmic contribution is a new minimax representation learning objective, for which we provide variants with differing tradeoffs in their statistical and computational properties. We interleave this representation learning step with an exploration strategy to cover the state space in a reward-free manner. The resulting algorithms are provably sample efficient and can accommodate general function approximation to scale to complex environments.
NeRF--: Neural Radiance Fields Without Known Camera Parameters
Venue: arXiv cs.CV 2022
Year: 2022

Considering the problem of novel view synthesis (NVS) from only a set of 2D images, we simplify the training process of Neural Radiance Field (NeRF) on forward-facing scenes by removing the requirement of known or pre-computed camera parameters, including both intrinsics and 6DoF poses. To this end, we propose NeRF$--$, with three contributions: First, we show that the camera parameters can be jointly optimised as learnable parameters with NeRF training, through a photometric reconstruction; Second, to benchmark the camera parameter estimation and the quality of novel view renderings, we introduce a new dataset of path-traced synthetic scenes, termed as Blender Forward-Facing Dataset (BLEFF); Third, we conduct extensive analyses to understand the training behaviours under various camera motions, and show that in most scenarios, the joint optimisation pipeline can recover accurate camera parameters and achieve comparable novel view synthesis quality as those trained with COLMAP pre-computed camera parameters. Our code and data are available at https://nerfmm.active.vision.
Learning Student-Friendly Teacher Networks for Knowledge Distillation
Venue: arXiv cs.LG 2022
Year: 2022

We propose a novel knowledge distillation approach to facilitate the transfer of dark knowledge from a teacher to a student. Contrary to most of the existing methods that rely on effective training of student models given pretrained teachers, we aim to learn the teacher models that are friendly to students and, consequently, more appropriate for knowledge transfer. In other words, at the time of optimizing a teacher model, the proposed algorithm learns the student branches jointly to obtain student-friendly representations. Since the main goal of our approach lies in training teacher models and the subsequent knowledge distillation procedure is straightforward, most of the existing knowledge distillation methods can adopt this technique to improve the performance of diverse student models in terms of accuracy and convergence speed. The proposed algorithm demonstrates outstanding accuracy in several well-known knowledge distillation techniques with various combinations of teacher and student models even in the case that their architectures are heterogeneous and there is no prior knowledge about student models at the time of training teacher networks.
Optimal Priority Assignment for Real-Time Systems: A Coevolution-Based Approach
Venue: arXiv cs.SE 2022
Year: 2022

In real-time systems, priorities assigned to real-time tasks determine the order of task executions, by relying on an underlying task scheduling policy. Assigning optimal priority values to tasks is critical to allow the tasks to complete their executions while maximizing safety margins from their specified deadlines. This enables real-time systems to tolerate unexpected overheads in task executions and still meet their deadlines. In practice, priority assignments result from an interactive process between the development and testing teams. In this article, we propose an automated method that aims to identify the best possible priority assignments in real-time systems, accounting for multiple objectives regarding safety margins and engineering constraints. Our approach is based on a multi-objective, competitive coevolutionary algorithm mimicking the interactive priority assignment process between the development and testing teams. We evaluate our approach by applying it to six industrial systems from different domains and several synthetic systems. The results indicate that our approach significantly outperforms both our baselines, i.e., random search and sequential search, and solutions defined by practitioners.Our approach scales to complex industrial systems as an offline analysis method that attempts to find near-optimal solutions within acceptable time, i.e., less than 16 hours.
Neural Posterior Regularization for Likelihood-Free Inference
Venue: arXiv cs.LG 2022
Year: 2022

A simulation is useful when the phenomenon of interest is either expensive to regenerate or irreproducible with the same context. Recently, Bayesian inference on the distribution of the simulation input parameter has been implemented sequentially to minimize the required simulation budget for the task of simulation validation to the real-world. However, the Bayesian inference is still challenging when the ground-truth posterior is multi-modal with a high-dimensional simulation output. This paper introduces a regularization technique, namely Neural Posterior Regularization (NPR), which enforces the model to explore the input parameter space effectively. Afterward, we provide the closed-form solution of the regularized optimization that enables analyzing the effect of the regularization. We empirically validate that NPR attains the statistically significant gain on benchmark performances for diverse simulation tasks.
Representing Hierarchical Structure by Using Cone Embedding
Venue: arXiv cs.AI 2022
Year: 2022

Graph embedding is becoming an important method with applications in various areas, including social networks and knowledge graph completion. In particular, Poincaré embedding has been proposed to capture the hierarchical structure of graphs, and its effectiveness has been reported. However, most of the existing methods have isometric mappings in the embedding space, and the choice of the origin point can be arbitrary. This fact is not desirable when the distance from the origin is used as an indicator of hierarchy, as in the case of Poincaré embedding. In this paper, we propose cone embedding, embedding method in a metric cone, which solve these problems, and we gain further benefits: 1) we provide an indicator of hierarchical information that is both geometrically and intuitively natural to interpret, and 2) we can extract the hierarchical structure from a graph embedding output of other methods by learning additional one-dimensional parameters.
Nominal Unification and Matching of Higher Order Expressions with Recursive Let
Venue: arXiv cs.LO 2022
Year: 2022

A sound and complete algorithm for nominal unification of higher-order expressions with a recursive let is described, and shown to run in nondeterministic polynomial time. We also explore specializations like nominal letrec-matching for expressions, for DAGs, and for garbage-free expressions and determine their complexity. We also provide a nominal unification algorithm for higher-order expressions with recursive let and atom-variables, where we show that it also runs in nondeterministic polynomial time. In addition we prove that there is a guessing strategy for nominal unification with letrec and atom-variable that is a trade-off between exponential growth and non-determinism. Nominal matching with variables representing partial letrec-environments is also shown to be in NP.
Improved management of issue dependencies in issue trackers of large collaborative projects
Venue: arXiv cs.SE 2022
Year: 2022

Issue trackers, such as Jira, have become the prevalent collaborative tools in software engineering for managing issues, such as requirements, development tasks, and software bugs. However, issue trackers inherently focus on the lifecycle of single issues, although issues have and express dependencies on other issues that constitute issue dependency networks in large complex collaborative projects. The objective of this study is to develop supportive solutions for the improved management of dependent issues in an issue tracker. This study follows the Design Science methodology, consisting of eliciting drawbacks and constructing and evaluating a solution and system. The study was carried out in the context of The Qt Company's Jira, which exemplifies an actively used, almost two-decade-old issue tracker with over 100,000 issues. The drawbacks capture how users operate with issue trackers to handle issue information in large, collaborative, and long-lived projects. The basis of the solution is to keep issues and dependencies as separate objects and automatically construct an issue graph. Dependency detections complement the issue graph by proposing missing dependencies, while consistency checks and diagnoses identify conflicting issue priorities and release assignments. Jira's plugin and service-based system architecture realize the functional and quality concerns of the system implementation. We show how to adopt the intelligent supporting techniques of an issue tracker in a complex use context and a large data-set. The solution considers an integrated and holistic system view, practical applicability and utility, and the practical characteristics of issue data, such as inherent incompleteness.
User Tracking in the Post-cookie Era: How Websites Bypass GDPR Consent to Track Users
Venue: arXiv cs.CY 2022
Year: 2022

During the past few years, mostly as a result of the GDPR and the CCPA, websites have started to present users with cookie consent banners. These banners are web forms where the users can state their preference and declare which cookies they would like to accept, if such option exists. Although requesting consent before storing any identifiable information is a good start towards respecting the user privacy, yet previous research has shown that websites do not always respect user choices. Furthermore, considering the ever decreasing reliance of trackers on cookies and actions browser vendors take by blocking or restricting third-party cookies, we anticipate a world where stateless tracking emerges, either because trackers or websites do not use cookies, or because users simply refuse to accept any. In this paper, we explore whether websites use more persistent and sophisticated forms of tracking in order to track users who said they do not want cookies. Such forms of tracking include first-party ID leaking, ID synchronization, and browser fingerprinting. Our results suggest that websites do use such modern forms of tracking even before users had the opportunity to register their choice with respect to cookies. To add insult to injury, when users choose to raise their voice and reject all cookies, user tracking only intensifies. As a result, users' choices play very little role with respect to tracking: we measured that more than 75% of tracking activities happened before users had the opportunity to make a selection in the cookie consent banner, or when users chose to reject all cookies.
A Framework for Characterising the Value of Information in Hidden Markov Models
Venue: arXiv cs.IT 2022
Year: 2022

In this paper, a general framework is formalised to characterise the value of information (VoI) in hidden Markov models. Specifically, the VoI is defined as the mutual information between the current, unobserved status at the source and a sequence of observed measurements at the receiver, which can be interpreted as the reduction in the uncertainty of the current status given that we have noisy past observations of a hidden Markov process. We explore the VoI in the context of the noisy Ornstein-Uhlenbeck process and derive its closed-form expressions. Moreover, we investigate the effect of different sampling policies on VoI, deriving simplified expressions in different noise regimes and analysing statistical properties of the VoI in the worst case. We also study the optimal sampling policy to maximise the average information value under the sampling rate constraint. In simulations, the validity of theoretical results is verified, and the performance of VoI in Markov and hidden Markov models is also analysed. Numerical results further illustrate that the proposed VoI framework can support timely transmission in status update systems, and it can also capture the correlation properties of the underlying random process and the noise in the transmission environment.
IoTDevID: A Behavior-Based Device Identification Method for the IoT
Venue: arXiv cs.CR 2022
Year: 2022

Device identification is one way to secure a network of IoT devices, whereby devices identified as suspicious can subsequently be isolated from a network. In this study, we present a machine learning-based method, IoTDevID, that recognizes devices through characteristics of their network packets. As a result of using a rigorous feature analysis and selection process, our study offers a generalizable and realistic approach to modelling device behavior, achieving high predictive accuracy across two public datasets. The model's underlying feature set is shown to be more predictive than existing feature sets used for device identification, and is shown to generalize to data unseen during the feature selection process. Unlike most existing approaches to IoT device identification, IoTDevID is able to detect devices using non-IP and low-energy protocols.
Improved Deep Reinforcement Learning with Expert Demonstrations for Urban Autonomous Driving
Venue: arXiv cs.RO 2022
Year: 2022

Learning-based approaches, such as reinforcement learning (RL) and imitation learning (IL), have indicated superiority over rule-based approaches in complex urban autonomous driving environments, showing great potential to make intelligent decisions. However, current RL and IL approaches still have their own drawbacks, such as low data efficiency for RL and poor generalization capability for IL. In light of this, this paper proposes a novel learning-based method that combines deep reinforcement learning and imitation learning from expert demonstrations, which is applied to longitudinal vehicle motion control in autonomous driving scenarios. Our proposed method employs the soft actor-critic and modifies the learning process of the policy network to incorporate both the goals of maximizing reward and imitating the expert. Moreover, an adaptive prioritized experience replay is designed to sample experience from both the agent's self-exploration and expert demonstration, in order to improve sample efficiency. The proposed method is validated in a simulated urban roundabout scenario and compared with various prevailing RL and IL baselines. The results manifest that the proposed method has a faster training speed, as well as better performance in navigating safely and time-efficiently.
Temporal Locality in Online Algorithms
Venue: arXiv cs.DS 2022
Year: 2022

Online algorithms make decisions based on past inputs. In general, the decision may depend on the entire history of inputs. If many computers run the same online algorithm with the same input stream but are started at different times, they do not necessarily make consistent decisions. In this work we introduce time-local online algorithms. These are online algorithms where the output at a given time only depends on $T = O(1)$ latest inputs. The use of (deterministic) time-local algorithms in a distributed setting automatically leads to globally consistent decisions. Our key observation is that time-local online algorithms (in which the output at a given time only depends on local inputs in the temporal dimension) are closely connected to local distributed graph algorithms (in which the output of a given node only depends on local inputs in the spatial dimension). This makes it possible to interpret prior work on distributed graph algorithms from the perspective of online algorithms. We describe an algorithm synthesis method that one can use to design optimal time-local online algorithms for small values of $T$. We demonstrate the power of the technique in the context of a variant of the online file migration problem, and show that e.g. for two nodes and unit migration costs there exists a $3$-competitive time-local algorithm with horizon $T=4$, while no deterministic online algorithm (in the classic sense) can do better. We also derive upper and lower bounds for a more general version of the problem; we show that there is a $6$-competitive deterministic time-local algorithm and a $2.62$-competitive randomized time-local algorithm for any migration cost $α\ge 1$.