OpenRaiser/Intern-Atlas huggingface dataset:
Conditioning by adaptive sampling for robust design
Venue: arXiv cs.LG 2021
Year: 2021

We present a new method for design problems wherein the goal is to maximize or specify the value of one or more properties of interest. For example, in protein design, one may wish to find the protein sequence that maximizes fluorescence. We assume access to one or more, potentially black box, stochastic "oracle" predictive functions, each of which maps from input (e.g., protein sequences) design space to a distribution over a property of interest (e.g. protein fluorescence). At first glance, this problem can be framed as one of optimizing the oracle(s) with respect to the input. However, many state-of-the-art predictive models, such as neural networks, are known to suffer from pathologies, especially for data far from the training distribution. Thus we need to modulate the optimization of the oracle inputs with prior knowledge about what makes `realistic' inputs (e.g., proteins that stably fold). Herein, we propose a new method to solve this problem, Conditioning by Adaptive Sampling, which yields state-of-the-art results on a protein fluorescence problem, as compared to other recently published approaches. Formally, our method achieves its success by using model-based adaptive sampling to estimate the conditional distribution of the input sequences given the desired properties.
Reparameterizable Subset Sampling via Continuous Relaxations
Venue: arXiv cs.LG 2021
Year: 2021

Many machine learning tasks require sampling a subset of items from a collection based on a parameterized distribution. The Gumbel-softmax trick can be used to sample a single item, and allows for low-variance reparameterized gradients with respect to the parameters of the underlying distribution. However, stochastic optimization involving subset sampling is typically not reparameterizable. To overcome this limitation, we define a continuous relaxation of subset sampling that provides reparameterization gradients by generalizing the Gumbel-max trick. We use this approach to sample subsets of features in an instance-wise feature selection task for model interpretability, subsets of neighbors to implement a deep stochastic k-nearest neighbors model, and sub-sequences of neighbors to implement parametric t-SNE by directly comparing the identities of local neighbors. We improve performance in all these tasks by incorporating subset sampling in end-to-end training.
Robust Deep Multi-Modal Sensor Fusion using Fusion Weight Regularization and Target Learning
Venue: arXiv cs.LG 2021
Year: 2021

Sensor fusion has wide applications in many domains including health care and autonomous systems. While the advent of deep learning has enabled promising multi-modal fusion of high-level features and end-to-end sensor fusion solutions, existing deep learning based sensor fusion techniques including deep gating architectures are not always resilient, leading to the issue of fusion weight inconsistency. We propose deep multi-modal sensor fusion architectures with enhanced robustness particularly under the presence of sensor failures. At the core of our gating architectures are fusion weight regularization and fusion target learning operating on auxiliary unimodal sensing networks appended to the main fusion model. The proposed regularized gating architectures outperform the existing deep learning architectures with and without gating under both clean and corrupted sensory inputs resulted from sensor failures. The demonstrated improvements are particularly pronounced when one or more multiple sensory modalities are corrupted.
Efficiently computing runs on a trie
Venue: arXiv cs.DS 2021
Year: 2021

A maximal repetition, or run, in a string, is a maximal periodic substring whose smallest period is at most half the length of the substring. In this paper, we consider runs that correspond to a path on a trie, or in other words, on a rooted edge-labeled tree where the endpoints of the path must be a descendant/ancestor of the other. For a trie with $n$ edges, we show that the number of runs is less than $n$. We also show an asymptotic lower bound on the maximum density of runs in tries: $\lim_{n\rightarrow\infty}ρ_\mathcal{T}(n)/n \geq 0.993238$ where $ρ_{\mathcal{T}}(n)$ is the maximum number of runs in a trie with $n$ edges. Furthermore, we also show an $O(n\log \log n)$ time and $O(n)$ space algorithm for finding all runs.
Feature Concatenation Multi-view Subspace Clustering
Venue: arXiv cs.LG 2021
Year: 2021

Multi-view clustering is a learning paradigm based on multi-view data. Since statistic properties of different views are diverse, even incompatible, few approaches implement multi-view clustering based on the concatenated features straightforward. However, feature concatenation is a natural way to combine multi-view data. To this end, this paper proposes a novel multi-view subspace clustering approach dubbed Feature Concatenation Multi-view Subspace Clustering (FCMSC), which boosts the clustering performance by exploring the consensus information of multi-view data. Specifically, multi-view data are concatenated into a joint representation firstly, then, $l_{2,1}$-norm is integrated into the objective function to deal with the sample-specific and cluster-specific corruptions of multiple views. Moreover, a graph regularized FCMSC is also proposed in this paper to explore both the consensus information and complementary information of multi-view data for clustering. It is noteworthy that the obtained coefficient matrix is not derived by simply applying the Low-Rank Representation (LRR) to concatenated features directly. Finally, an effective algorithm based on the Augmented Lagrangian Multiplier (ALM) is designed to optimize the objective functions. Comprehensive experiments on six real-world datasets illustrate the superiority of the proposed methods over several state-of-the-art approaches for multi-view clustering.
Distributionally Robust and Multi-Objective Nonnegative Matrix Factorization
Venue: arXiv cs.LG 2021
Year: 2021

Nonnegative matrix factorization (NMF) is a linear dimensionality reduction technique for analyzing nonnegative data. A key aspect of NMF is the choice of the objective function that depends on the noise model (or statistics of the noise) assumed on the data. In many applications, the noise model is unknown and difficult to estimate. In this paper, we define a multi-objective NMF (MO-NMF) problem, where several objectives are combined within the same NMF model. We propose to use Lagrange duality to judiciously optimize for a set of weights to be used within the framework of the weighted-sum approach, that is, we minimize a single objective function which is a weighted sum of the all objective functions. We design a simple algorithm based on multiplicative updates to minimize this weighted sum. We show how this can be used to find distributionally robust NMF (DR-NMF) solutions, that is, solutions that minimize the largest error among all objectives, using a dual approach solved via a heuristic inspired from the Frank-Wolfe algorithm. We illustrate the effectiveness of this approach on synthetic, document and audio data sets. The results show that DR-NMF is robust to our incognizance of the noise model of the NMF problem.
Semantic Hierarchy Preserving Deep Hashing for Large-scale Image Retrieval
Venue: arXiv cs.CV 2021
Year: 2021

Deep hashing models have been proposed as an efficient method for large-scale similarity search. However, most existing deep hashing methods only utilize fine-level labels for training while ignoring the natural semantic hierarchy structure. This paper presents an effective method that preserves the classwise similarity of full-level semantic hierarchy for large-scale image retrieval. Experiments on two benchmark datasets show that our method helps improve the fine-level retrieval performance. Moreover, with the help of the semantic hierarchy, it can produce significantly better binary codes for hierarchical retrieval, which indicates its potential of providing more user-desired retrieval results.
Efficient Learning of Discrete Graphical Models
Venue: arXiv cs.LG 2021
Year: 2021

Graphical models are useful tools for describing structured high-dimensional probability distributions. Development of efficient algorithms for learning graphical models with least amount of data remains an active research topic. Reconstruction of graphical models that describe the statistics of discrete variables is a particularly challenging problem, for which the maximum likelihood approach is intractable. In this work, we provide the first sample-efficient method based on the Interaction Screening framework that allows one to provably learn fully general discrete factor models with node-specific discrete alphabets and multi-body interactions, specified in an arbitrary basis. We identify a single condition related to model parametrization that leads to rigorous guarantees on the recovery of model structure and parameters in any error norm, and is readily verifiable for a large class of models. Importantly, our bounds make explicit distinction between parameters that are proper to the model and priors used as an input to the algorithm. Finally, we show that the Interaction Screening framework includes all models previously considered in the literature as special cases, and for which our analysis shows a systematic improvement in sample complexity.
CodedPrivateML: A Fast and Privacy-Preserving Framework for Distributed Machine Learning
Venue: arXiv cs.LG 2021
Year: 2021

How to train a machine learning model while keeping the data private and secure? We present CodedPrivateML, a fast and scalable approach to this critical problem. CodedPrivateML keeps both the data and the model information-theoretically private, while allowing efficient parallelization of training across distributed workers. We characterize CodedPrivateML's privacy threshold and prove its convergence for logistic (and linear) regression. Furthermore, via extensive experiments on Amazon EC2, we demonstrate that CodedPrivateML provides significant speedup over cryptographic approaches based on multi-party computing (MPC).
Paracosm: A Language and Tool for Testing Autonomous Driving Systems
Venue: arXiv cs.SE 2021
Year: 2021

Systematic testing of autonomous vehicles operating in complex real-world scenarios is a difficult and expensive problem. We present Paracosm, a reactive language for writing test scenarios for autonomous driving systems. Paracosm allows users to programmatically describe complex driving situations with specific visual features, e.g., road layout in an urban environment, as well as reactive temporal behaviors of cars and pedestrians. Paracosm programs are executed on top of a game engine that provides realistic physics simulation and visual rendering. The infrastructure allows systematic exploration of the state space, both for visual features (lighting, shadows, fog) and for reactive interactions with the environment (pedestrians, other traffic). We define a notion of test coverage for Paracosm configurations based on combinatorial testing and low dispersion sequences. Paracosm comes with an automatic test case generator that uses random sampling for discrete parameters and deterministic quasi-Monte Carlo generation for continuous parameters. Through an empirical evaluation, we demonstrate the modeling and testing capabilities of Paracosm on a suite of autonomous driving systems implemented using deep neural networks developed in research and education. We show how Paracosm can expose incorrect behaviors or degraded performance.
Recycling Solutions for Vertex Coloring Heuristics
Venue: arXiv cs.DM 2021
Year: 2021

The vertex coloring problem is a well-known NP-hard problem and has many applications in operations research and in scheduling. A conventional approach to the problem solves the k-colorability problem iteratively, decreasing k one by one. Whether a heuristic algorithm finds a legal k-coloring quickly or not is largely affected by an initial solution. We highlight a simple initial solution generator, which we call the recycle method, which makes use of the legal (k+1)-coloring that has been found. An initial solution generated by the method is expected to guide a heuristic algorithm to find a legal k-coloring more quickly than conventional methods, as demonstrated by experimental studies. The results suggest that the recycle method should be used as the standard initial solution generator for both local search algorithms and modern hybrid methods.
Self-Adjusting Mutation Rates with Provably Optimal Success Rules
Venue: arXiv cs.NE 2021
Year: 2021

The one-fifth success rule is one of the best-known and most widely accepted techniques to control the parameters of evolutionary algorithms. While it is often applied in the literal sense, a common interpretation sees the one-fifth success rule as a family of success-based updated rules that are determined by an update strength $F$ and a success rate. We analyze in this work how the performance of the (1+1) Evolutionary Algorithm on LeadingOnes depends on these two hyper-parameters. Our main result shows that the best performance is obtained for small update strengths $F=1+o(1)$ and success rate $1/e$. We also prove that the running time obtained by this parameter setting is, apart from lower order terms, the same that is achieved with the best fitness-dependent mutation rate. We show similar results for the resampling variant of the (1+1) Evolutionary Algorithm, which enforces to flip at least one bit per iteration.
Complexity-Theoretic Aspects of Expanding Cellular Automata
Venue: arXiv cs.CC 2021
Year: 2021

The expanding cellular automata (XCA) variant of cellular automata is investigated and characterized from a complexity-theoretical standpoint. An XCA is a one-dimensional cellular automaton which can dynamically create new cells between existing ones. The respective polynomial-time complexity class is shown to coincide with ${\le_{tt}^p}(\mathsf{NP})$, that is, the class of decision problems polynomial-time truth-table reducible to problems in $\mathsf{NP}$. An alternative characterization based on a variant of non-deterministic Turing machines is also given. In addition, corollaries on select XCA variants are proven: XCAs with multiple accept and reject states are shown to be polynomial-time equivalent to the original XCA model. Finally, XCAs with alternative acceptance conditions are considered and classified in terms of ${\le_{tt}^p}(\mathsf{NP})$ and the Turing machine polynomial-time class $\mathsf{P}$.
Solving Complex Quadratic Systems with Full-Rank Random Matrices
Venue: arXiv cs.IT 2021
Year: 2021

We tackle the problem of recovering a complex signal $\boldsymbol x\in\mathbb{C}^n$ from quadratic measurements of the form $y_i=\boldsymbol x^*\boldsymbol A_i\boldsymbol x$, where $\boldsymbol A_i$ is a full-rank, complex random measurement matrix whose entries are generated from a rotation-invariant sub-Gaussian distribution. We formulate it as the minimization of a nonconvex loss. This problem is related to the well understood phase retrieval problem where the measurement matrix is a rank-1 positive semidefinite matrix. Here we study the general full-rank case which models a number of key applications such as molecular geometry recovery from distance distributions and compound measurements in phaseless diffractive imaging. Most prior works either address the rank-1 case or focus on real measurements. The several papers that address the full-rank complex case adopt the computationally-demanding semidefinite relaxation approach. In this paper we prove that the general class of problems with rotation-invariant sub-Gaussian measurement models can be efficiently solved with high probability via the standard framework comprising a spectral initialization followed by iterative Wirtinger flow updates on a nonconvex loss. Numerical experiments on simulated data corroborate our theoretical analysis.
Massively Parallel Path Space Filtering
Venue: arXiv cs.GR 2021
Year: 2021

Restricting path tracing to a small number of paths per pixel for performance reasons rarely achieves a satisfactory image quality for scenes of interest. However, path space filtering may dramatically improve the visual quality by sharing information across vertices of paths classified as proximate. Unlike screen space-based approaches, these paths neither need to be present on the screen, nor is filtering restricted to the first intersection with the scene. While searching proximate vertices had been more expensive than filtering in screen space, we greatly improve over this performance penalty by storing, updating, and looking up the required information in a hash table. The keys are constructed from jittered and quantized information, such that only a single query very likely replaces costly neighborhood searches. A massively parallel implementation of the algorithm is demonstrated on a graphics processing unit (GPU).
Intelligent Surface-Aided Transmitter Architectures for Millimeter Wave Ultra Massive MIMO Systems
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, we study two novel massive multiple-input multiple-output (MIMO) transmitter architectures for millimeter wave (mmWave) communications which comprise few active antennas, each equipped with a dedicated radio frequency (RF) chain, that illuminate a nearby large intelligent reflecting/transmitting surface (IRS/ITS). The IRS (ITS) consists of a large number of low-cost and energy-efficient passive antenna elements which are able to reflect (transmit) a phase-shifted version of the incident electromagnetic field. Similar to lens array (LA) antennas, IRS/ITS-aided antenna architectures are energy efficient due to the almost lossless over-the-air connection between the active antennas and the intelligent surface. However, unlike for LA antennas, for which the number of active antennas has to linearly grow with the number of passive elements (i.e., the lens aperture) due to the non-reconfigurablility (i.e., non-intelligence) of the lens, for IRS/ITS-aided antennas, the reconfigurablility of the IRS/ITS facilitates scaling up the number of radiating passive elements without increasing the number of costly and bulky active antennas. We show that the constraints that the precoders for IRS/ITS-aided antennas have to meet differ from those of conventional MIMO architectures. Taking these constraints into account and exploiting the sparsity of mmWave channels, we design two efficient precoders; one based on maximizing the mutual information and one based on approximating the optimal unconstrained fully digital (FD) precoder via the orthogonal matching pursuit algorithm. Furthermore, we develop a power consumption model for IRS/ITS-aided antennas that takes into account the impacts of the IRS/ITS imperfections, namely the spillover loss, taper loss, aperture loss, and phase shifter loss.
Robust and Adaptive Door Operation with a Mobile Robot
Venue: arXiv cs.RO 2021
Year: 2021

The ability to deal with articulated objects is very important for robots assisting humans. In this work, a framework to robustly and adaptively operate common doors, using an autonomous mobile manipulator, is proposed. To push forward the state-of-the-art in robustness and speed performance, we devise a novel algorithm that fuses a convolutional neural network with efficient point cloud processing. This advancement enables real-time grasping pose estimation for multiple handles from RGB-D images, providing a speed up improvement for assistive human-centered applications. In addition, we propose a versatile Bayesian framework that endows the robot with the ability to infer the door kinematic model from observations of its motion and learn from previous experiences or human demonstrations. Combining these algorithms with a Task Space Region motion planner, we achieve an efficient door operation regardless of the kinematic model. We validate our framework with real-world experiments using the Toyota Human Support Robot.
clusterNOR: A NUMA-Optimized Clustering Framework
Venue: arXiv cs.DC 2021
Year: 2021

Clustering algorithms are iterative and have complex data access patterns that result in many small random memory accesses. The performance of parallel implementations suffer from synchronous barriers for each iteration and skewed workloads. We rethink the parallelization of clustering for modern non-uniform memory architectures (NUMA) to maximizes independent, asynchronous computation. We eliminate many barriers, reduce remote memory accesses, and maximize cache reuse. We implement the 'Clustering NUMA Optimized Routines' (clusterNOR) extensible parallel framework that provides algorithmic building blocks. The system is generic, we demonstrate nine modern clustering algorithms that have simple implementations. clusterNOR includes (i) in-memory, (ii) semi-external memory, and (iii) distributed memory execution, enabling computation for varying memory and hardware budgets. For algorithms that rely on Euclidean distance, clusterNOR defines an updated Elkan's triangle inequality pruning algorithm that uses asymptotically less memory so that it works on billion-point data sets. clusterNOR extends and expands the scope of the 'knor' library for k-means clustering by generalizing underlying principles, providing a uniform programming interface and expanding the scope to hierarchical and linear algebraic classes of algorithms. The compound effect of our optimizations is an order of magnitude improvement in speed over other state-of-the-art solutions, such as Spark's MLlib and Apple's Turi.
Analyzing Deep Neural Networks with Symbolic Propagation: Towards Higher Precision and Faster Verification
Venue: arXiv cs.LG 2021
Year: 2021

Deep neural networks (DNNs) have been shown lack of robustness for the vulnerability of their classification to small perturbations on the inputs. This has led to safety concerns of applying DNNs to safety-critical domains. Several verification approaches have been developed to automatically prove or disprove safety properties of DNNs. However, these approaches suffer from either the scalability problem, i.e., only small DNNs can be handled, or the precision problem, i.e., the obtained bounds are loose. This paper improves on a recent proposal of analyzing DNNs through the classic abstract interpretation technique, by a novel symbolic propagation technique. More specifically, the values of neurons are represented symbolically and propagated forwardly from the input layer to the output layer, on top of abstract domains. We show that our approach can achieve significantly higher precision and thus can prove more properties than using only abstract domains. Moreover, we show that the bounds derived from our approach on the hidden neurons, when applied to a state-of-the-art SMT based verification tool, can improve its performance. We implement our approach into a software tool and validate it over a few DNNs trained on benchmark datasets such as MNIST, etc.