OpenRaiser/Intern-Atlas huggingface dataset:
Tensor-based Subspace Factorization for StyleGAN
Venue: arXiv cs.CV 2021
Year: 2021

In this paper, we propose $τ$GAN a tensor-based method for modeling the latent space of generative models. The objective is to identify semantic directions in latent space. To this end, we propose to fit a multilinear tensor model on a structured facial expression database, which is initially embedded into latent space. We validate our approach on StyleGAN trained on FFHQ using BU-3DFE as a structured facial expression database. We show how the parameters of the multilinear tensor model can be approximated by Alternating Least Squares. Further, we introduce a tacked style-separated tensor model, defined as an ensemble of style-specific models to integrate our approach with the extended latent space of StyleGAN. We show that taking the individual styles of the extended latent space into account leads to higher model flexibility and lower reconstruction error. Finally, we do several experiments comparing our approach to former work on both GANs and multilinear models. Concretely, we analyze the expression subspace and find that the expression trajectories meet at an apathetic face that is consistent with earlier work. We also show that by changing the pose of a person, the generated image from our approach is closer to the ground truth than results from two competing approaches.
A Roadmap for Enabling a Future-Proof In-Network Computing Data Plane Ecosystem
Venue: arXiv cs.NI 2021
Year: 2021

As the vision of in-network computing becomes more mature, we see two parallel evolutionary trends. First, we see the evolution of richer, more demanding applications that require capabilities beyond programmable switching ASICs. Second, we see the evolution of diverse data plane technologies with many other future capabilities on the horizon. While some point solutions exist to tackle the intersection of these trends, we see several ecosystem-level disconnects today; e.g., the need to refactor applications for new data planes, lack of systematic guidelines to inform the development of future data plane capabilities, and lack of holistic runtime frameworks for network operators. In this paper, we use a simple-yet-instructive emerging application-data plane combination to highlight these disconnects. Drawing on these lessons, we sketch a high-level roadmap and guidelines for the community to tackle these to create a more thriving "future-proof" data plane ecosystem.
An Improved Local Search Algorithm for k-Median
Venue: arXiv cs.DS 2021
Year: 2021

We present a new local-search algorithm for the $k$-median clustering problem. We show that local optima for this algorithm give a $(2.836+ε)$-approximation; our result improves upon the $(3+ε)$-approximate local-search algorithm of Arya et al. [STOC 01]. Moreover, a computer-aided analysis of a natural extension suggests that this approach may lead to an improvement over the best-known approximation guarantee for the problem. The new ingredient in our algorithm is the use of a potential function based on both the closest and second-closest facilities to each client. Specifically, the potential is the sum over all clients, of the distance of the client to its closest facility, plus (a small constant times) the truncated distance to its second-closest facility. We move from one solution to another only if the latter can be obtained by swapping a constant number of facilities, and has a smaller potential than the former. This refined potential allows us to avoid the bad local optima given by Arya et al. for the local-search algorithm based only on the cost of the solution.
Graphs can be succinctly indexed for pattern matching in $ O(|E|^2 + |V|^{5 / 2}) $ time
Venue: arXiv cs.DS 2021
Year: 2021

For the first time we provide a succinct pattern matching index for arbitrary graphs that can be built in polynomial time, which requires less space and answers queries more efficiently than the one in [SODA 2021]. We show that, given an edge-labeled graph $ G = (V, E) $, there exists a data structures of $|E /_{\le_G}|(\lceil \log|Σ|\rceil + \lceil\log q\rceil + 2)\cdot (1+o(1)) + |V /_{\le_G}|\cdot (1+o(1))$ bits which can be built in $ O(|E|^2 + |V /_{\le_G}|^{5 / 2}) $ time and supports pattern matching on $ G $ in $O(|P| \cdot q^2 \cdot \log(q\cdot |Σ|))$ time, where $ G /_{\le_G} = (V /_{\le_G}, E /_{\le_G}) $ is a quotient graph obtained by collapsing some nodes in $ G $ (so $ |V /_{\le_G}| \le |V| $ and $ |E /_{\le_G}| \le |E| $) and $ q $ is the width of the maximum co-lex relation on $ G $. Our results have relevant applications in automata theory. First, we can build a succinct data structure to decide whether a string is accepted by a given automaton. Second, starting from an automaton $ \mathcal{A} $, one can define a relation $ \preceq_\mathcal{A} $ and a quotient automaton that capture the nondeterminism of $ \mathcal{A} $, improving the results in [SODA 2021].
Isometry invariant shape recognition of projectively perturbed point clouds by the mergegram extending 0D persistence
Venue: arXiv cs.CG 2021
Year: 2021

Rigid shapes should be naturally compared up to rigid motion or isometry, which preserves all inter-point distances. The same rigid shape can be often represented by noisy point clouds of different sizes. Hence the isometry shape recognition problem requires methods that are independent of a cloud size. This paper studies stable-under-noise isometry invariants for the recognition problem stated in the harder form when given clouds can be related by affine or projective transformations. The first contribution is the stability proof for the invariant mergegram, which completely determines a single-linkage dendrogram in general position. The second contribution is the experimental demonstration that the mergegram outperforms other invariants in recognizing isometry classes of point clouds extracted from perturbed shapes in images.
Efficient multi-partition topology optimization
Venue: arXiv cs.CE 2021
Year: 2021

In topology optimization, the state of structures is typically obtained by numerically evaluating a discretized PDE-based model. The degrees of freedom of such a model can be partitioned in free and prescribed sets to define the boundary conditions. A multi-partition problem involves multiple partitions of the same discretization, typically corresponding to different loading scenarios. As a result, solving multi-partition problems involves multiple factorization/preconditionings of the system matrix, requiring a high computational effort. In this paper, a novel method is proposed to efficiently calculate the responses and accompanying design sensitivities in such multi-partition problems using static condensation for use in gradient-based topology optimization. A main problem class that benefits from the proposed method is the topology optimization of small-displacement multi-input-multi-output compliant mechanisms. However, the method is applicable to any linear problem. We present its formulation and an algorithmic complexity analysis to estimate computational advantages for both direct and iterative solution methods to solve the system of equations, verified by numerical experiments. It is demonstrated that substantial gains are achievable for large-scale multi-partition problems. This is especially true for problems with both a small set of number of degrees of freedom that fully describes the performance of the structure and with large similarities between the different partitions. A major contribution to the gain is the lack of large adjoint analyses required to obtain the sensitivities of the performance measure.
A simple and versatile topology optimization formulation for flexure synthesis
Venue: arXiv cs.CE 2021
Year: 2021

High-tech equipment critically relies on flexures for precise manipulation and measurement. Through elastic deformation, flexures offer extreme position repeatability within a limited range of motion in their degrees of freedom, while constraining motion in the degrees of constraint. Topology optimization proves a prospective tool for the design of short-stroke flexures, providing maximum design freedom and allowing for application-specific requirements. State-of-the-art topology optimization formulations for flexure synthesis are subject to challenges like ease of use, versatility, implementation complexity, and computational cost, leaving a generally accepted formulation absent. This study proposes a novel topology optimization formulation for the synthesis of short-stroke flexures uniquely based on strain energy measures under prescribed displacement scenarios. The resulting self-adjoint optimization problem resembles great similarity to classic compliance minimization and inherits similar implementation simplicity, computational efficiency, and convergence properties. Numerical examples demonstrate the versatility in flexure types and the extendability of additional design requirements. The provided source code encourages the formulation to be explored and applied in academia and industry.
Machine Learning-based Test Selection for Simulation-based Testing of Self-driving Cars Software
Venue: arXiv cs.SE 2021
Year: 2021

Abstract Simulation platforms facilitate the development of emerging cyber-physical systems (CPS) like self-driving cars (SDC) because they are more efficient and less dangerous than field operational tests. Despite this, thoroughly testing SDCs in simulated environments remains challenging because SDCs must be tested in a sheer amount of long-running test scenarios. Past results on software testing optimization have shown that not all the tests contribute equally to establishing confidence in test subjects' quality and reliability, with some \uninformative" tests that can be skipped (or removed) to reduce testing effort. However, this problem was partially addressed in the context of SDC simulation platforms. In this paper, we investigate test selection strategies to increase the cost-effectiveness of simulation-based testing in the context of SDCs. We propose an approach called SDC-Scissor (SDC coSt-effeCtIve teSt SelectOR), which leverages machine learning (ML) strategies to identify and skip tests that are unlikely to detect faults in SDCs before executing them. Specifically, SDC-Scissor extract features concerning the characteristics of the test scenarios being executed in the simulation environment and via ML strategies predict tests that lead to faults before executing them. Our evaluation shows that SDC-Scissor achieved high classification accuracy (up to 93.4%) in classifying tests leading to a fault which allows improving testing cost-effectiveness: SDC-Scissor was able to reduce (ca. 170%) the time spent in running irrelevant tests as well as identified 33% more failure triggering tests compared to a randomized baseline. Interestingly, SDC-Scissor does not introduce significant computational overhead in the SDCs testing process, which is critical to SDC development in industrial settings.
Information-Theoretic Bias Assessment Of Learned Representations Of Pretrained Face Recognition
Venue: arXiv cs.CV 2021
Year: 2021

As equality issues in the use of face recognition have garnered a lot of attention lately, greater efforts have been made to debiased deep learning models to improve fairness to minorities. However, there is still no clear definition nor sufficient analysis for bias assessment metrics. We propose an information-theoretic, independent bias assessment metric to identify degree of bias against protected demographic attributes from learned representations of pretrained facial recognition systems. Our metric differs from other methods that rely on classification accuracy or examine the differences between ground truth and predicted labels of protected attributes predicted using a shallow network. Also, we argue, theoretically and experimentally, that logits-level loss is not adequate to explain bias since predictors based on neural networks will always find correlations. Further, we present a synthetic dataset that mitigates the issue of insufficient samples in certain cohorts. Lastly, we establish a benchmark metric by presenting advantages in clear discrimination and small variation comparing with other metrics, and evaluate the performance of different debiased models with the proposed metric.
Reinforcement Learning for Mixed Autonomy Intersections
Venue: arXiv cs.AI 2021
Year: 2021

We propose a model-free reinforcement learning method for controlling mixed autonomy traffic in simulated traffic networks with through-traffic-only two-way and four-way intersections. Our method utilizes multi-agent policy decomposition which allows decentralized control based on local observations for an arbitrary number of controlled vehicles. We demonstrate that, even without reward shaping, reinforcement learning learns to coordinate the vehicles to exhibit traffic signal-like behaviors, achieving near-optimal throughput with 33-50% controlled vehicles. With the help of multi-task learning and transfer learning, we show that this behavior generalizes across inflow rates and size of the traffic network. Our code, models, and videos of results are available at https://github.com/ZhongxiaYan/mixed_autonomy_intersections.
Use of 1D-CNN for input data size reduction of LSTM in Hourly Rainfall-Runoff modeling
Venue: arXiv cs.LG 2021
Year: 2021

An architecture consisting of a serial coupling of the one-dimensional convolutional neural network (1D-CNN) and the long short-term memory (LSTM) network, which is referred as CNNsLSTM, was proposed for hourly-scale rainfall-runoff modeling in this study. In CNNsLTSM, the CNN component receives the hourly meteorological time series data for a long duration, and then the LSTM component receives the extracted features from 1D-CNN and the hourly meteorological time series data for a short-duration. As a case study, CNNsLSTM was implemented for hourly rainfall-runoff modeling at the Ishikari River watershed, Japan. The meteorological dataset, consists of precipitation, air temperature, evapotranspiration, and long- and short-wave radiation, were utilized as input, and the river flow was used as the target data. To evaluate the performance of proposed CNNsLSTM, results of CNNsLSTM were compared with those of 1D-CNN, LSTM only with hourly inputs (LSTMwHour), parallel architecture of 1D-CNN and LSTM (CNNpLSTM), and the LSTM architecture which uses both daily and hourly input data (LSTMwDpH). CNNsLSTM showed clear improvements on the estimation accuracy compared to the three conventional architectures (1D-CNN, LSTMwHour, and CNNpLSTM), and recently proposed LSTMwDpH. In comparison to observed flows, the median of the NSE values for the test period are 0.455-0.469 for 1D-CNN (based on NCHF=8, 16, and 32, the numbers of the channels of the feature map of the first layer of CNN), 0.639-0.656 for CNNpLSTM (based on NCHF=8, 16, and 32), 0.745 for LSTMwHour, 0.831 for LSTMwDpH, and 0.865-0.873 for CNNsLSTM (based on NCHF=8, 16, and 32). Furthermore, the proposed CNNsLSTM reduces the median RMSE of 1D-CNN by 50.2%-51.4%, CNNpLSTM by 37.4%-40.8%, LSTMwHour by 27.3%-29.5%, and LSTMwDpH by 10.6%-13.4%.
Capacity and Performance Analysis of RIS-Assisted Communication Over Rician Fading Channels
Venue: arXiv cs.IT 2021
Year: 2021

This paper investigates two performance metrics, namely ergodic capacity and symbol error rate, of mmWave communication system assisted by a reconfigurable intelligent surface (RIS). We assume independent and identically distributed (i.i.d.) Rician fadings between user-RIS-Access Point (AP), with RIS surface consisting of passive reflecting elements. First, we derive a new unified closed-form formula for the average symbol error probability of generalised M-QAM/M-PSK signalling over this mmWave link. We then obtain new closed-form expressions for the ergodic capacity with and without channel state information (CSI) at the AP.
Locally Testable Codes with constant rate, distance, and locality
Venue: arXiv cs.IT 2021
Year: 2021

A locally testable code (LTC) is an error-correcting code that has a property-tester. The tester reads $q$ bits that are randomly chosen, and rejects words with probability proportional to their distance from the code. The parameter $q$ is called the locality of the tester. LTCs were initially studied as important components of PCPs, and since then the topic has evolved on its own. High rate LTCs could be useful in practice: before attempting to decode a received word, one can save time by first quickly testing if it is close to the code. An outstanding open question has been whether there exist "$c^3$-LTCs", namely LTCs with *c*onstant rate, *c*onstant distance, and *c*onstant locality. In this work we construct such codes based on a new two-dimensional complex which we call a left-right Cayley complex. This is essentially a graph which, in addition to vertices and edges, also has squares. Our codes can be viewed as a two-dimensional version of (the one-dimensional) expander codes, where the codewords are functions on the squares rather than on the edges.
Analyzing and Improving Fault Tolerance of Learning-Based Navigation Systems
Venue: arXiv cs.RO 2021
Year: 2021

Learning-based navigation systems are widely used in autonomous applications, such as robotics, unmanned vehicles and drones. Specialized hardware accelerators have been proposed for high-performance and energy-efficiency for such navigational tasks. However, transient and permanent faults are increasing in hardware systems and can catastrophically violate tasks safety. Meanwhile, traditional redundancy-based protection methods are challenging to deploy on resource-constrained edge applications. In this paper, we experimentally evaluate the resilience of navigation systems with respect to algorithms, fault models and data types from both RL training and inference. We further propose two efficient fault mitigation techniques that achieve 2x success rate and 39% quality-of-flight improvement in learning-based navigation systems.
Convolutional Neural Networks with Radio-Frequency Spintronic Nano-Devices
Venue: arXiv cs.ET 2021
Year: 2021

Convolutional neural networks are state-of-the-art and ubiquitous in modern signal processing and machine vision. Nowadays, hardware solutions based on emerging nanodevices are designed to reduce the power consumption of these networks. Spintronics devices are promising for information processing because of the various neural and synaptic functionalities they offer. However, due to their low OFF/ON ratio, performing all the multiplications required for convolutions in a single step with a crossbar array of spintronic memories would cause sneak-path currents. Here we present an architecture where synaptic communications have a frequency selectivity that prevents crosstalk caused by sneak-path currents. We first demonstrate how a chain of spintronic resonators can function as synapses and make convolutions by sequentially rectifying radio-frequency signals encoding consecutive sets of inputs. We show that a parallel implementation is possible with multiple chains of spintronic resonators to avoid storing intermediate computational steps in memory. We propose two different spatial arrangements for these chains. For each of them, we explain how to tune many artificial synapses simultaneously, exploiting the synaptic weight sharing specific to convolutions. We show how information can be transmitted between convolutional layers by using spintronic oscillators as artificial microwave neurons. Finally, we simulate a network of these radio-frequency resonators and spintronic oscillators to solve the MNIST handwritten digits dataset, and obtain results comparable to software convolutional neural networks. Since it can run convolutional neural networks fully in parallel in a single step with nano devices, the architecture proposed in this paper is promising for embedded applications requiring machine vision, such as autonomous driving.
Incremental Meta-Learning via Episodic Replay Distillation for Few-Shot Image Recognition
Venue: arXiv cs.CV 2021
Year: 2021

Most meta-learning approaches assume the existence of a very large set of labeled data available for episodic meta-learning of base knowledge. This contrasts with the more realistic continual learning paradigm in which data arrives incrementally in the form of tasks containing disjoint classes. In this paper we consider this problem of Incremental Meta-Learning (IML) in which classes are presented incrementally in discrete tasks. We propose an approach to IML, which we call Episodic Replay Distillation (ERD), that mixes classes from the current task with class exemplars from previous tasks when sampling episodes for meta-learning. These episodes are then used for knowledge distillation to minimize catastrophic forgetting. Experiments on four datasets demonstrate that ERD surpasses the state-of-the-art. In particular, on the more challenging one-shot, long task sequence incremental meta-learning scenarios, we reduce the gap between IML and the joint-training upper bound from 3.5% / 10.1% / 13.4% with the current state-of-the-art to 2.6% / 2.9% / 5.0% with our method on Tiered-ImageNet / Mini-ImageNet / CIFAR100, respectively.
Learning Numerical Action Models from Noisy Input Data
Venue: arXiv cs.AI 2021
Year: 2021

This paper presents the PlanMiner-N algorithm, a domain learning technique based on the PlanMiner domain learning algorithm. The algorithm presented here improves the learning capabilities of PlanMiner when using noisy data as input. The PlanMiner algorithm is able to infer arithmetic and logical expressions to learn numerical planning domains from the input data, but it was designed to work under situations of incompleteness making it unreliable when facing noisy input data. In this paper, we propose a series of enhancements to the learning process of PlanMiner to expand its capabilities to learn from noisy data. These methods preprocess the input data by detecting noise and filtering it and study the learned action models learned to find erroneous preconditions/effects in them. The methods proposed in this paper were tested using a set of domains from the International Planning Competition (IPC). The results obtained indicate that PlanMiner-N improves the performance of PlanMiner greatly when facing noisy input data.
Pattern Matching on Grammar-Compressed Strings in Linear Time
Venue: arXiv cs.DS 2021
Year: 2021

The most fundamental problem considered in algorithms for text processing is pattern matching: given a pattern $p$ of length $m$ and a text $t$ of length $n$, does $p$ occur in $t$? Multiple versions of this basic question have been considered, and by now we know algorithms that are fast both in practice and in theory. However, the rapid increase in the amount of generated and stored data brings the need of designing algorithms that operate directly on compressed representations of data. In the compressed pattern matching problem we are given a compressed representation of the text, with $n$ being the length of the compressed representation and $N$ being the length of the text, and an uncompressed pattern of length $m$. The most challenging (and yet relevant when working with highly repetitive data, say biological information) scenario is when the chosen compression method is capable of describing a string of exponential length (in the size of its representation). An elegant formalism for such a compression method is that of straight-line programs, which are simply context-free grammars describing exactly one string. While it has been known that compressed pattern matching problem can be solved in $O(m+n\log N)$ time for this compression method, designing a linear-time algorithm remained open. We resolve this open question by presenting an $O(n+m)$ time algorithm that, given a context-free grammar of size $n$ that produces a single string $t$ and a pattern $p$ of length $m$, decides whether $p$ occurs in $t$ as a substring. To this end, we devise improved solutions for the weighted ancestor problem and the substring concatenation problem.