OpenRaiser/Intern-Atlas huggingface dataset:
Integrating Novelty Detection Capabilities with MSL Mastcam Operations to Enhance Data Analysis
Venue: arXiv cs.LG 2021
Year: 2021

While innovations in scientific instrumentation have pushed the boundaries of Mars rover mission capabilities, the increase in data complexity has pressured Mars Science Laboratory (MSL) and future Mars rover operations staff to quickly analyze complex data sets to meet progressively shorter tactical and strategic planning timelines. MSLWEB is an internal data tracking tool used by operations staff to perform first pass analysis on MSL image sequences, a series of products taken by the Mast camera, Mastcam. Mastcam's multiband multispectral image sequences require more complex analysis compared to standard 3-band RGB images. Typically, these are analyzed using traditional methods to identify unique features within the sequence. Given the short time frame of tactical planning in which downlinked images might need to be analyzed (within 5-10 hours before the next uplink), there exists a need to triage analysis time to focus on the most important sequences and parts of a sequence. We address this need by creating products for MSLWEB that use novelty detection to help operations staff identify unusual data that might be diagnostic of new or atypical compositions or mineralogies detected within an imaging scene. This was achieved in two ways: 1) by creating products for each sequence to identify novel regions in the image, and 2) by assigning multispectral sequences a sortable novelty score. These new products provide colorized heat maps of inferred novelty that operations staff can use to rapidly review downlinked data and focus their efforts on analyzing potentially new kinds of diagnostic multispectral signatures. This approach has the potential to guide scientists to new discoveries by quickly drawing their attention to often subtle variations not detectable with simple color composites.
An Approach for the Automation of IaaS Cloud Upgrade
Venue: arXiv cs.DC 2021
Year: 2021

An Infrastructure as a Service (IaaS) cloud provider is committed to each tenant by a service level agreement (SLA) which indicates the terms of commitment, e.g. the level of availability of the IaaS cloud service.The different resources providing this IaaS cloud service may need to be upgraded several times throughout their life-cycle; and these upgrades may affect the service delivered by the IaaS layer. This may violate the SLAs towards the tenants and result in penalty as they impact the tenant services relying on the IaaS.Therefore, it is important to handle upgrades properly with respect to the SLAs.The upgrade of IaaS cloud systems inherits all the challenges of clustered systems and faces other, cloud specific challenges, such as size and dynamicity due to elasticity.In this paper, we propose a novel approach to automatically upgrade an IaaS cloud system under SLA constraints such as availability and elasticity.In this approach, the upgrade methods and actions appropriate for each upgrade request are identified, scheduled, and applied automatically in an iterative manner based on the vendors descriptions of the infrastructure components, the tenant SLAs, and the status of the system. The proposed approach allows new upgrade requests during ongoing upgrades, which makes it suitable for continuous delivery.In addition, it also handles failures of upgrade actions through localized retry and undo operations automatically.
Privacy-preserving Identity Broadcast for Contact Tracing Applications
Venue: arXiv cs.CR 2021
Year: 2021

Wireless Contact tracing has emerged as an important tool for managing the COVID19 pandemic and relies on continuous broadcasting of a person's presence using Bluetooth Low Energy beacons. The limitation of current contact tracing systems in that a reception of a single beacon is sufficient to reveal the user identity, potentially exposing users to malicious trackers installed along the roads, passageways, and other infrastructure. In this paper, we propose a method based on Shamir secret sharing algorithm, which lets mobile nodes reveal their identity only after a certain predefined contact duration, remaining invisible to trackers with short or fleeting encounters. Through data-driven evaluation, using a dataset containing 18 million BLE sightings, we show that the method drastically reduces the privacy exposure of users. Finally, we implemented the approach on Android phones to demonstrate its feasibility and measure performance for various network densities.
A High-order Tuner for Accelerated Learning and Control
Venue: arXiv cs.LG 2021
Year: 2021

Gradient-descent based iterative algorithms pervade a variety of problems in estimation, prediction, learning, control, and optimization. Recently iterative algorithms based on higher-order information have been explored in an attempt to lead to accelerated learning. In this paper, we explore a specific a high-order tuner that has been shown to result in stability with time-varying regressors in linearly parametrized systems, and accelerated convergence with constant regressors. We show that this tuner continues to provide bounded parameter estimates even if the gradients are corrupted by noise. Additionally, we also show that the parameter estimates converge exponentially to a compact set whose size is dependent on noise statistics. As the HT algorithms can be applied to a wide range of problems in estimation, filtering, control, and machine learning, the result obtained in this paper represents an important extension to the topic of real-time and fast decision making.
The Multicolored Graph Realization Problem
Venue: arXiv cs.CC 2021
Year: 2021

We introduce the Multicolored Graph Realization problem (MGRP). The input to the problem is a colored graph $(G,φ)$, i.e., a graph together with a coloring on its vertices. We can associate to each colored graph a cluster graph ($G_φ)$ in which, after collapsing to a node all vertices with the same color, we remove multiple edges and self-loops. A set of vertices $S$ is multicolored when $S$ has exactly one vertex from each color class. The problem is to decide whether there is a multicolored set $S$ such that, after identifying each vertex in $S$ with its color class, $G[S]$ coincides with $G_φ$. The MGR problem is related to the class of generalized network problems, most of which are NP-hard. For example the generalized MST problem. MGRP is a generalization of the Multicolored Clique Problem, which is known to be W[1]-hard when parameterized by the number of colors. Thus MGRP remains W[1]-hard, when parameterized by the size of the cluster graph and when parameterized by any graph parameter on $G_φ$, among those for treewidth. We look to instances of the problem in which both the number of color classes and the treewidth of $G_φ$ are unbounded. We show that MGRP is NP-complete when $G_φ$ is either chordal, biconvex bipartite, complete bipartite or a 2-dimensional grid. Our hardness results follows from suitable reductions from the 1-in-3 monotone SAT problem. Our reductions show that the problem remains hard even when the maximum number of vertices in a color class is 3. In the case of the grid, the hardness holds also graphs with bounded degree. We complement those results by showing combined parameterizations under which the MGR problem became tractable.
An Offline Delegatable Cryptocurrency System
Venue: arXiv cs.CR 2021
Year: 2021

Blockchain-based cryptocurrencies, facilitating the convenience of payment by providing a decentralized online solution, have not been widely adopted so far due to slow confirmation of transactions. Offline delegation offers an efficient way to exchange coins. However, in such an approach, the coins that have been delegated confront the risk of being spent twice since the delegator's behaviour cannot be restricted easily on account of the absence of effective supervision. Even if a third party can be regarded as a judge between the delegator and delegatee to secure transactions, she still faces the threat of being compromised or providing misleading assure. Moreover, the approach equipped with a third party contradicts the real intention of decentralized cryptocurrency systems. In this paper, we propose \textit{DelegaCoin}, an offline delegatable cryptocurrency system to mitigate such an issue. We exploit trusted execution environments (TEEs) as decentralized "virtual agents" to prevent malicious delegation. In DelegaCoin, an owner can delegate his coins through offline-transactions without interacting with the blockchain network. A formal model and analysis, prototype implementation, and further evaluation demonstrate that our scheme is provably secure and practically feasible.
A Challenge Obfuscating Interface for Arbiter PUF Variants against Machine Learning Attacks
Venue: arXiv cs.CR 2021
Year: 2021

Security is of critical importance for the Internet of Things (IoT). Many IoT devices are resource-constrained, calling for lightweight security protocols. Physical unclonable functions (PUFs) leverage integrated circuits' variations to produce responses unique for individual devices, and hence are not reproducible even by the manufacturers. Implementable with simplistic circuits of thousands of transistors and operable with low energy, Physical unclonable functions are promising candidates as security primitives for resource-constrained IoT devices. Arbiter PUFs (APUFs) are a group of delay-based PUFs which are highly lightweight in resource requirements but suffer from high susceptibility to machine learning attacks. To defend APUF variants against machine learning attacks, we introduce challenge input interface, which incurs low resource overhead. With the interface, experimental attack study shows that all tested PUFs have substantially improved their resistance against machine learning attacks, rendering interfaced APUF variants promising candidates for security critical applications.
Outage Probability Expressions for an IRS-Assisted System with and without Source-Destination Link for the Case of Quantized Phase Shifts in $κ-μ$ fading
Venue: arXiv cs.IT 2021
Year: 2021

In this work, we study the outage probability (OP) at the destination of an intelligent reflecting surface (IRS) assisted communication system in a $κ-μ$ fading environment. A practical system model that takes into account the presence of phase error due to quantization at the IRS when a) source-destination (SD) link is present and b) SD link is absent is considered. First, an exact expression is derived, and then we derive three simple approximations for the OP using the following approaches: (i) uni-variate dimension reduction, (ii) moment matching and, (iii) Kullback-Leibler divergence minimization. The resulting expressions for OP are simple to evaluate and quite tight even in the tail region. The validity of these approximations is demonstrated using extensive Monte Carlo simulations. We also study the impact of the number of bits available for quantization, the position of IRS with respect to the source and destination and the number of IRS elements on the OP for systems with and without an SD link.
Hetero-Modal Learning and Expansive Consistency Constraints for Semi-Supervised Detection from Multi-Sequence Data
Venue: arXiv cs.CV 2021
Year: 2021

Lesion detection serves a critical role in early diagnosis and has been well explored in recent years due to methodological advancesand increased data availability. However, the high costs of annotations hinder the collection of large and completely labeled datasets, motivating semi-supervised detection approaches. In this paper, we introduce mean teacher hetero-modal detection (MTHD), which addresses two important gaps in current semi-supervised detection. First, it is not obvious how to enforce unlabeled consistency constraints across the very different outputs of various detectors, which has resulted in various compromises being used in the state of the art. Using an anchor-free framework, MTHD formulates a mean teacher approach without such compromises, enforcing consistency on the soft-output of object centers and size. Second, multi-sequence data is often critical, e.g., for abdominal lesion detection, but unlabeled data is often missing sequences. To deal with this, MTHD incorporates hetero-modal learning in its framework. Unlike prior art, MTHD is able to incorporate an expansive set of consistency constraints that include geometric transforms and random sequence combinations. We train and evaluate MTHD on liver lesion detection using the largest MR lesion dataset to date (1099 patients with >5000 volumes). MTHD surpasses the best fully-supervised and semi-supervised competitors by 10.1% and 3.5%, respectively, in average sensitivity.
Including Sparse Production Knowledge into Variational Autoencoders to Increase Anomaly Detection Reliability
Venue: arXiv cs.LG 2021
Year: 2021

Digitalization leads to data transparency for production systems that we can benefit from with data-driven analysis methods like neural networks. For example, automated anomaly detection enables saving resources and optimizing the production. We study using rarely occurring information about labeled anomalies into Variational Autoencoder neural network structures to overcome information deficits of supervised and unsupervised approaches. This method outperforms all other models in terms of accuracy, precision, and recall. We evaluate the following methods: Principal Component Analysis, Isolation Forest, Classifying Neural Networks, and Variational Autoencoders on seven time series datasets to find the best performing detection methods. We extend this idea to include more infrequently occurring meta information about production processes. This use of sparse labels, both of anomalies or production data, allows to harness any additional information available for increasing anomaly detection performance.
Discriminator Augmented Model-Based Reinforcement Learning
Venue: arXiv cs.LG 2021
Year: 2021

By planning through a learned dynamics model, model-based reinforcement learning (MBRL) offers the prospect of good performance with little environment interaction. However, it is common in practice for the learned model to be inaccurate, impairing planning and leading to poor performance. This paper aims to improve planning with an importance sampling framework that accounts and corrects for discrepancy between the true and learned dynamics. This framework also motivates an alternative objective for fitting the dynamics model: to minimize the variance of value estimation during planning. We derive and implement this objective, which encourages better prediction on trajectories with larger returns. We observe empirically that our approach improves the performance of current MBRL algorithms on two stochastic control problems, and provide a theoretical basis for our method.
deGraphCS: Embedding Variable-based Flow Graph for Neural Code Search
Venue: arXiv cs.SE 2021
Year: 2021

With the rapid increase in the amount of public code repositories, developers maintain a great desire to retrieve precise code snippets by using natural language. Despite existing deep learning based approaches(e.g., DeepCS and MMAN) have provided the end-to-end solutions (i.e., accepts natural language as queries and shows related code fragments retrieved directly from code corpus), the accuracy of code search in the large-scale repositories is still limited by the code representation (e.g., AST) and modeling (e.g., directly fusing the features in the attention stage). In this paper, we propose a novel learnable deep Graph for Code Search (calleddeGraphCS), to transfer source code into variable-based flow graphs based on the intermediate representation technique, which can model code semantics more precisely compared to process the code as text directly or use the syntactic tree representation. Furthermore, we propose a well-designed graph optimization mechanism to refine the code representation, and apply an improved gated graph neural network to model variable-based flow graphs. To evaluate the effectiveness of deGraphCS, we collect a large-scale dataset from GitHub containing 41,152 code snippets written in C language, and reproduce several typical deep code search methods for comparison. Besides, we design a qualitative user study to verify the practical value of our approach. The experimental results have shown that deGraphCS can achieve state-of-the-art performances, and accurately retrieve code snippets satisfying the needs of the users.
Online Stochastic Matching, Poisson Arrivals, and the Natural Linear Program
Venue: arXiv cs.DS 2021
Year: 2021

We study the online stochastic matching problem. Consider a bipartite graph with offline vertices on one side, and with i.i.d.online vertices on the other side. The offline vertices and the distribution of online vertices are known to the algorithm beforehand. The realization of the online vertices, however, is revealed one at a time, upon which the algorithm immediately decides how to match it. For maximizing the cardinality of the matching, we give a $0.711$-competitive online algorithm, which improves the best previous ratio of $0.706$. When the offline vertices are weighted, we introduce a $0.7009$-competitive online algorithm for maximizing the total weight of the matched offline vertices, which improves the best previous ratio of $0.662$. Conceptually, we find that the analysis of online algorithms simplifies if the online vertices follow a Poisson process, and establish an approximate equivalence between this Poisson arrival model and online stochstic matching. Technically, we propose a natural linear program for the Poisson arrival model, and demonstrate how to exploit its structure by introducing a converse of Jensen's inequality. Moreover, we design an algorithmic amortization to replace the analytic one in previous work, and as a result get the first vertex-weighted online stochastic matching algorithm that improves the results in the weaker random arrival model.
Accelerating Sparse Approximate Matrix Multiplication on GPUs
Venue: arXiv cs.PF 2021
Year: 2021

Although the matrix multiplication plays a vital role in computational linear algebra, there are few efficient solutions for matrix multiplication of the near-sparse matrices. The Sparse Approximate Matrix Multiply (SpAMM) is one of the algorithms to fill the performance gap neglected by traditional optimizations for dense/sparse matrix multiplication. However, existing SpAMM algorithms fail to exploit the performance potential of GPUs for acceleration. In this paper, we present cuSpAMM, the first parallel SpAMM algorithm optimized for multiple GPUs. Several performance optimizations have been proposed, including algorithm re-design to adapt to the thread parallelism, blocking strategies for memory access optimization, and the acceleration with the tensor core. In addition, we scale cuSpAMM to run on multiple GPUs with an effective load balance scheme. We evaluate cuSpAMM on both synthesized and real-world datasets on multiple GPUs. The experiment results show that cuSpAMM achieves significant performance speedup compared to vendor optimized cuBLAS and cuSPARSE libraries.
Single-Sample Prophet Inequalities Revisited
Venue: arXiv cs.GT 2021
Year: 2021

The study of the prophet inequality problem in the limited information regime was initiated by Azar et al. [SODA'14] in the pursuit of prior-independent posted-price mechanisms. As they show, $O(1)$-competitive policies are achievable using only a single sample from the distribution of each agent. A notable portion of their results relies on reducing the design of single-sample prophet inequalities (SSPIs) to that of order-oblivious secretary (OOS) policies. The above reduction comes at the cost of not fully utilizing the available samples. However, to date, this is essentially the only method for proving SSPIs for many combinatorial sets. Very recently, Rubinstein et al. [ITCS'20] give a surprisingly simple algorithm which achieves the optimal competitive ratio for the single-choice SSPI problem $-$ a result which is unobtainable going through the reduction to secretary problems. Motivated by this discrepancy, we study the competitiveness of simple SSPI policies directly, without appealing to results from OOS literature. In this direction, we first develop a framework for analyzing policies against a greedy-like prophet solution. Using this framework, we obtain the first SSPI for general (non-bipartite) matching environments, as well as improved competitive ratios for transversal and truncated partition matroids. Second, motivated by the observation that many OOS policies for matroids decompose the problem into independent rank-$1$ instances, we provide a meta-theorem which applies to any matroid satisfying this partition property. Leveraging the recent results by Rubinstein et al., we obtain improved competitive guarantees (most by a factor of $2$) for a number of matroids captured by the reduction of Azar et al. Finally, we discuss applications of our SSPIs to the design of mechanisms for multi-dimensional limited information settings with improved revenue and welfare guarantees.
A computational framework for modeling cell-matrix interactions in soft biological tissues
Venue: arXiv cs.CE 2021
Year: 2021

Living soft tissues appear to promote the development and maintenance of a preferred mechanical state within a defined tolerance around a so-called set-point. This phenomenon is often referred to as mechanical homeostasis. In contradiction to the prominent role of mechanical homeostasis in various (patho)physiological processes, its underlying micromechanical mechanisms acting on the level of individual cells and fibers remain poorly understood, especially, how these mechanisms on the microscale lead to what we macroscopically call mechanical homeostasis. Here, we present a novel finite element based computational framework that is constructed bottom up, that is, it models key mechanobiological mechanisms such as actin cytoskeleton contraction and molecular clutch behavior of individual cells interacting with a reconstructed three-dimensional extracellular fiber matrix. The framework reproduces many experimental observations regarding mechanical homeostasis on short time scales (hours), in which the deposition and degradation of extracellular matrix can largely be neglected. This model can serve as a systematic tool for future in silico studies of the origin of the numerous still unexplained experimental observations about mechanical homeostasis.
Representing Numbers in NLP: a Survey and a Vision
Venue: arXiv cs.CL 2021
Year: 2021

NLP systems rarely give special consideration to numbers found in text. This starkly contrasts with the consensus in neuroscience that, in the brain, numbers are represented differently from words. We arrange recent NLP work on numeracy into a comprehensive taxonomy of tasks and methods. We break down the subjective notion of numeracy into 7 subtasks, arranged along two dimensions: granularity (exact vs approximate) and units (abstract vs grounded). We analyze the myriad representational choices made by 18 previously published number encoders and decoders. We synthesize best practices for representing numbers in text and articulate a vision for holistic numeracy in NLP, comprised of design trade-offs and a unified evaluation.