OpenRaiser/Intern-Atlas huggingface dataset:
Fixed-MAML for Few Shot Classification in Multilingual Speech Emotion Recognition
Venue: arXiv cs.SD 2022
Year: 2022

In this paper, we analyze the feasibility of applying few-shot learning to speech emotion recognition task (SER). The current speech emotion recognition models work exceptionally well but fail when then input is multilingual. Moreover, when training such models, the models' performance is suitable only when the training corpus is vast. This availability of a big training corpus is a significant problem when choosing a language that is not much popular or obscure. We attempt to solve this challenge of multilingualism and lack of available data by turning this problem into a few-shot learning problem. We suggest relaxing the assumption that all N classes in an N-way K-shot problem be new and define an N+F way problem where N and F are the number of emotion classes and predefined fixed classes, respectively. We propose this modification to the Model-Agnostic MetaLearning (MAML) algorithm to solve the problem and call this new model F-MAML. This modification performs better than the original MAML and outperforms on EmoFilm dataset.
On the Approximation Relationship between Optimizing Ratio of Submodular (RS) and Difference of Submodular (DS) Functions
Venue: arXiv cs.DS 2022
Year: 2022

We demonstrate that from an algorithm guaranteeing an approximation factor for the ratio of submodular (RS) optimization problem, we can build another algorithm having a different kind of approximation guarantee -- weaker than the classical one -- for the difference of submodular (DS) optimization problem, and vice versa. We also illustrate the link between these two problems by analyzing a \textsc{Greedy} algorithm which approximately maximizes objective functions of the form $Ψ(f,g)$, where $f,g$ are two non-negative, monotone, submodular functions and $Ψ$ is a {quasiconvex} 2-variables function, which is non decreasing with respect to the first variable. For the choice $Ψ(f,g)\triangleq f/g$, we recover RS, and for the choice $Ψ(f,g)\triangleq f-g$, we recover DS. To the best of our knowledge, this greedy approach is new for DS optimization. For RS optimization, it reduces to the standard \textsc{GreedRatio} algorithm that has already been analyzed previously. However, our analysis is novel for this case.
Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints
Venue: arXiv cs.LG 2022
Year: 2022

We study reinforcement learning (RL) with linear function approximation under the adaptivity constraint. We consider two popular limited adaptivity models: the batch learning model and the rare policy switch model, and propose two efficient online RL algorithms for episodic linear Markov decision processes, where the transition probability and the reward function can be represented as a linear function of some known feature mapping. In specific, for the batch learning model, our proposed LSVI-UCB-Batch algorithm achieves an $\tilde O(\sqrt{d^3H^3T} + dHT/B)$ regret, where $d$ is the dimension of the feature mapping, $H$ is the episode length, $T$ is the number of interactions and $B$ is the number of batches. Our result suggests that it suffices to use only $\sqrt{T/dH}$ batches to obtain $\tilde O(\sqrt{d^3H^3T})$ regret. For the rare policy switch model, our proposed LSVI-UCB-RareSwitch algorithm enjoys an $\tilde O(\sqrt{d^3H^3T[1+T/(dH)]^{dH/B}})$ regret, which implies that $dH\log T$ policy switches suffice to obtain the $\tilde O(\sqrt{d^3H^3T})$ regret. Our algorithms achieve the same regret as the LSVI-UCB algorithm (Jin et al., 2019), yet with a substantially smaller amount of adaptivity. We also establish a lower bound for the batch learning model, which suggests that the dependency on $B$ in our regret bound is tight.
Demand Forecasting for Platelet Usage: from Univariate Time Series to Multivariate Models
Venue: arXiv cs.LG 2022
Year: 2022

Platelet products are both expensive and have very short shelf lives. As usage rates for platelets are highly variable, the effective management of platelet demand and supply is very important yet challenging. The primary goal of this paper is to present an efficient forecasting model for platelet demand at Canadian Blood Services (CBS). To accomplish this goal, four different demand forecasting methods, ARIMA (Auto Regressive Moving Average), Prophet, lasso regression (least absolute shrinkage and selection operator) and LSTM (Long Short-Term Memory) networks are utilized and evaluated. We use a large clinical dataset for a centralized blood distribution centre for four hospitals in Hamilton, Ontario, spanning from 2010 to 2018 and consisting of daily platelet transfusions along with information such as the product specifications, the recipients' characteristics, and the recipients' laboratory test results. This study is the first to utilize different methods from statistical time series models to data-driven regression and a machine learning technique for platelet transfusion using clinical predictors and with different amounts of data. We find that the multivariate approaches have the highest accuracy in general, however, if sufficient data are available, a simpler time series approach such as ARIMA appears to be sufficient. We also comment on the approach to choose clinical indicators (inputs) for the multivariate models.
SHARKS: Smart Hacking Approaches for RisK Scanning in Internet-of-Things and Cyber-Physical Systems based on Machine Learning
Venue: arXiv cs.CR 2022
Year: 2022

Cyber-physical systems (CPS) and Internet-of-Things (IoT) devices are increasingly being deployed across multiple functionalities, ranging from healthcare devices and wearables to critical infrastructures, e.g., nuclear power plants, autonomous vehicles, smart cities, and smart homes. These devices are inherently not secure across their comprehensive software, hardware, and network stacks, thus presenting a large attack surface that can be exploited by hackers. In this article, we present an innovative technique for detecting unknown system vulnerabilities, managing these vulnerabilities, and improving incident response when such vulnerabilities are exploited. The novelty of this approach lies in extracting intelligence from known real-world CPS/IoT attacks, representing them in the form of regular expressions, and employing machine learning (ML) techniques on this ensemble of regular expressions to generate new attack vectors and security vulnerabilities. Our results show that 10 new attack vectors and 122 new vulnerability exploits can be successfully generated that have the potential to exploit a CPS or an IoT ecosystem. The ML methodology achieves an accuracy of 97.4% and enables us to predict these attacks efficiently with an 87.2% reduction in the search space. We demonstrate the application of our method to the hacking of the in-vehicle network of a connected car. To defend against the known attacks and possible novel exploits, we discuss a defense-in-depth mechanism for various classes of attacks and the classification of data targeted by such attacks. This defense mechanism optimizes the cost of security measures based on the sensitivity of the protected resource, thus incentivizing its adoption in real-world CPS/IoT by cybersecurity practitioners.
On a Class of Time-Varying Gaussian ISI Channels
Venue: arXiv cs.IT 2022
Year: 2022

This paper studies a class of stochastic and time-varying Gaussian intersymbol interference~(ISI) channels. The probability law for the~$i^{th}$ channel tap during time slot~$t$ is supported over an interval of centre $c_i$ and radius~$ r_{i}$. The transmitter and the receiver only know the centres $c_i$ and the radii $r_i$. The joint distribution for the array of channel taps and their realizations are unknown to both the transmitter and the receiver. A lower bound (achievability result) is presented on the channel capacity which results in an upper bound on the capacity loss compared to when all radii are zeros. The lower bound on the channel capacity saturates at a positive value as the maximum average input power $P$ increases beyond what is referred to as the saturation power $P_{sat}$. Roughly speaking, $P_{sat}$ is inversely proportional to the sum of the squares of the radii $r_i$. A partial converse result is provided in the worst-case scenario where the array of channel taps varies independently along both indices $t$ and $i$ with uniform marginals. It is shown that for every sequence of codebooks with vanishing probability of error, if the size of each symbol in every codeword is bounded away from zero by an amount proportional to $\sqrt{P}$, then the rate of that sequence of codebooks does not scale with~$P$. Tools in matrix analysis such as matrix norms and Weyl's inequality on perturbation of eigenvalues of symmetric matrices are used in order to analyze the probability of error.
Tackling Instance-Dependent Label Noise via a Universal Probabilistic Model
Venue: arXiv cs.LG 2022
Year: 2022

The drastic increase of data quantity often brings the severe decrease of data quality, such as incorrect label annotations, which poses a great challenge for robustly training Deep Neural Networks (DNNs). Existing learning \mbox{methods} with label noise either employ ad-hoc heuristics or restrict to specific noise assumptions. However, more general situations, such as instance-dependent label noise, have not been fully explored, as scarce studies focus on their label corruption process. By categorizing instances into confusing and unconfusing instances, this paper proposes a simple yet universal probabilistic model, which explicitly relates noisy labels to their instances. The resultant model can be realized by DNNs, where the training procedure is accomplished by employing an alternating optimization algorithm. Experiments on datasets with both synthetic and real-world label noise verify that the proposed method yields significant improvements on robustness over state-of-the-art counterparts.
Temporal Logic Task Allocation in Heterogeneous Multi-Robot Systems
Venue: arXiv cs.RO 2022
Year: 2022

In this paper, we consider the problem of optimally allocating tasks, expressed as global Linear Temporal Logic (LTL) specifications, to teams of heterogeneous mobile robots. The robots are classified in different types that capture their different capabilities, and each task may require robots of multiple types. The specific robots assigned to each task are immaterial, as long as they are of the desired type. Given a discrete workspace, our goal is to design paths, i.e., sequences of discrete states, for the robots so that the LTL specification is satisfied. To obtain a scalable solution to this complex temporal logic task allocation problem, we propose a hierarchical approach that first allocates specific robots to tasks using the information about the tasks contained in the Nondeterministic Buchi Automaton (NBA) that captures the LTL specification, and then designs low-level executable plans for the robots that respect the high-level assignment. Specifically, we first prune and relax the NBA by removing all negative atomic propositions. This step is motivated by "lazy collision checking" methods in robotics and allows to simplify the planning problem by checking constraint satisfaction only when needed. Then, we extract sequences of subtasks from the relaxed NBA along with their temporal orders, and formulate a Mixed Integer Linear Program (MILP) to allocate these subtasks to the robots. Finally, we define generalized multi-robot path planning problems to obtain low-level executable robot plans that satisfy both the high-level task allocation and the temporal constraints captured by the negative atomic propositions in the original NBA. We show that our method is complete for a subclass of LTL that covers a broad range of tasks and present numerical simulations demonstrating that it can generate paths with lower cost, considerably faster than existing methods.
Hierarchical Reinforcement Learning By Discovering Intrinsic Options
Venue: arXiv cs.LG 2022
Year: 2022

We propose a hierarchical reinforcement learning method, HIDIO, that can learn task-agnostic options in a self-supervised manner while jointly learning to utilize them to solve sparse-reward tasks. Unlike current hierarchical RL approaches that tend to formulate goal-reaching low-level tasks or pre-define ad hoc lower-level policies, HIDIO encourages lower-level option learning that is independent of the task at hand, requiring few assumptions or little knowledge about the task structure. These options are learned through an intrinsic entropy minimization objective conditioned on the option sub-trajectories. The learned options are diverse and task-agnostic. In experiments on sparse-reward robotic manipulation and navigation tasks, HIDIO achieves higher success rates with greater sample efficiency than regular RL baselines and two state-of-the-art hierarchical RL methods.
On Unimodality of Independence Polynomials of Trees
Venue: arXiv cs.DM 2022
Year: 2022

An independent set in a graph is a set of pairwise non-adjacent vertices. The independence number $α{(G)}$ is the size of a maximum independent set in the graph $G$. The independence polynomial of a graph is the generating function for the sequence of numbers of independent sets of each size. In other words, the $k$-th coefficient of the independence polynomial equals the number of independent sets comprised of $k$ vertices. For instance, the degree of the independence polynomial of the graph $G$ is equal to $α{(G)}$. In 1987, Alavi, Malde, Schwenk, and Erd{ö}s conjectured that the independence polynomial of a tree is unimodal. In what follows, we provide support to this assertion considering trees with up to $20$ vertices. Moreover, we show that the corresponding independence polynomials are log-concave and, consequently, unimodal. The algorithm computing the independence polynomial of a given tree makes use of a database of non-isomorphic unlabeled trees to prevent repeated computations.
Exploring Adversarial Robustness of Multi-Sensor Perception Systems in Self Driving
Venue: arXiv cs.CV 2022
Year: 2022

Modern self-driving perception systems have been shown to improve upon processing complementary inputs such as LiDAR with images. In isolation, 2D images have been found to be extremely vulnerable to adversarial attacks. Yet, there have been limited studies on the adversarial robustness of multi-modal models that fuse LiDAR features with image features. Furthermore, existing works do not consider physically realizable perturbations that are consistent across the input modalities. In this paper, we showcase practical susceptibilities of multi-sensor detection by placing an adversarial object on top of a host vehicle. We focus on physically realizable and input-agnostic attacks as they are feasible to execute in practice, and show that a single universal adversary can hide different host vehicles from state-of-the-art multi-modal detectors. Our experiments demonstrate that successful attacks are primarily caused by easily corrupted image features. Furthermore, we find that in modern sensor fusion methods which project image features into 3D, adversarial attacks can exploit the projection process to generate false positives across distant regions in 3D. Towards more robust multi-modal perception systems, we show that adversarial training with feature denoising can boost robustness to such attacks significantly. However, we find that standard adversarial defenses still struggle to prevent false positives which are also caused by inaccurate associations between 3D LiDAR points and 2D pixels.
A Tensor-Based Formulation of Hetero-functional Graph Theory
Venue: arXiv cs.AI 2022
Year: 2022

Recently, hetero-functional graph theory (HFGT) has developed as a means to mathematically model the structure of large-scale complex flexible engineering systems. It does so by fusing concepts from network science and model-based systems engineering (MBSE). For the former, it utilizes multiple graph-based data structures to support a matrix-based quantitative analysis. For the latter, HFGT inherits the heterogeneity of conceptual and ontological constructs found in model-based systems engineering including system form, system function, and system concept. These diverse conceptual constructs indicate multi-dimensional rather than two-dimensional relationships. This paper provides the first tensor-based treatment of hetero-functional graph theory. In particular, it addresses the ``system concept" and the hetero-functional adjacency matrix from the perspective of tensors and introduces the hetero-functional incidence tensor as a new data structure. The tensor-based formulation described in this work makes a stronger tie between HFGT and its ontological foundations in MBSE. Finally, the tensor-based formulation facilitates several analytical results that provide an understanding of the relationships between HFGT and multi-layer networks.
Unsupervised Imputation of Non-ignorably Missing Data Using Importance-Weighted Autoencoders
Venue: arXiv cs.LG 2022
Year: 2022

Deep Learning (DL) methods have dramatically increased in popularity in recent years. While its initial success was demonstrated in the classification and manipulation of image data, there has been significant growth in the application of DL methods to problems in the biomedical sciences. However, the greater prevalence and complexity of missing data in biomedical datasets present significant challenges for DL methods. Here, we provide a formal treatment of missing data in the context of Variational Autoencoders (VAEs), a popular unsupervised DL architecture commonly utilized for dimension reduction, imputation, and learning latent representations of complex data. We propose a new VAE architecture, NIMIWAE, that is one of the first to flexibly account for both ignorable and non-ignorable patterns of missingness in input features at training time. Following training, samples can be drawn from the approximate posterior distribution of the missing data can be used for multiple imputation, facilitating downstream analyses on high dimensional incomplete datasets. We demonstrate through statistical simulation that our method outperforms existing approaches for unsupervised learning tasks and imputation accuracy. We conclude with a case study of an EHR dataset pertaining to 12,000 ICU patients containing a large number of diagnostic measurements and clinical outcomes, where many features are only partially observed.
Inferring COVID-19 Biological Pathways from Clinical Phenotypes via Topological Analysis
Venue: arXiv cs.CL 2022
Year: 2022

COVID-19 has caused thousands of deaths around the world and also resulted in a large international economic disruption. Identifying the pathways associated with this illness can help medical researchers to better understand the properties of the condition. This process can be carried out by analyzing the medical records. It is crucial to develop tools and models that can aid researchers with this process in a timely manner. However, medical records are often unstructured clinical notes, and this poses significant challenges to developing the automated systems. In this article, we propose a pipeline to aid practitioners in analyzing clinical notes and revealing the pathways associated with this disease. Our pipeline relies on topological properties and consists of three steps: 1) pre-processing the clinical notes to extract the salient concepts, 2) constructing a feature space of the patients to characterize the extracted concepts, and finally, 3) leveraging the topological properties to distill the available knowledge and visualize the result. Our experiments on a publicly available dataset of COVID-19 clinical notes testify that our pipeline can indeed extract meaningful pathways.
Locality-Sensitive Orderings and Applications to Reliable Spanners
Venue: arXiv cs.DS 2022
Year: 2022

Chan, Har-Peled, and Jones [2020] recently developed locality-sensitive ordering (LSO), a new tool that allows one to reduce problems in the Euclidean space $\mathbb{R}^d$ to the $1$-dimensional line. They used LSO's to solve a host of problems. Later, Buchin, Har-Peled, and Ol{á}h [2019,2020] used the LSO of Chan {\em et al. } to construct very sparse \emph{reliable spanners} for the Euclidean space. A highly desirable feature of a reliable spanner is its ability to withstand a massive failure: the network remains functioning even if 90\% of the nodes fail. In a follow-up work, Har-Peled, Mendel, and Ol{á}h [2021] constructed reliable spanners for general and topologically structured metrics. Their construction used a different approach, and is based on sparse covers. In this paper, we develop the theory of LSO's in non-Euclidean metrics by introducing new types of LSO's suitable for general and topologically structured metrics. We then construct such LSO's, as well as constructing considerably improved LSO's for doubling metrics. Afterwards, we use our new LSO's to construct reliable spanners with improved stretch and sparsity parameters. Most prominently, we construct $\tilde{O}(n)$-size reliable spanners for trees and planar graphs with the optimal stretch of $2$. Along the way to the construction of LSO's and reliable spanners, we introduce and construct ultrametric covers, and construct $2$-hop reliable spanners for the line.
Mirror-Descent Inverse Kinematics for Box-constrained Joint Space
Venue: arXiv cs.RO 2022
Year: 2022

To control humanoid robots, the reference pose of end effector(s) is planned in task space, then mapped into the reference joints by IK. By viewing that problem as approximate quadratic programming (QP), recent QP solvers can be applied to solve it precisely, but iterative numerical IK solvers based on Jacobian are still in high demand due to their low computational cost. However, the conventional Jacobian-based IK usually clamps the obtained joints during iteration according to the constraints in practice, causing numerical instability due to non-smoothed objective function. To alleviate the clamping problem, this study explicitly considers the joint constraints, especially the box constraints in this paper, inside the new IK solver. Specifically, instead of clamping, a mirror descent (MD) method with box-constrained real joint space and no-constrained mirror space is integrated with the Jacobian-based IK, so-called MD-IK. In addition, to escape local optima nearly on the boundaries of constraints, a heuristic technique, called $ε$-clamping, is implemented as margin in software level. Finally, to increase convergence speed, the acceleration method for MD is integrated assuming continuity of solutions at each time. As a result, the accelerated MD-IK achieved more stable and enough fast tracking performance compared to the conventional IK solvers. The low computational cost of the proposed method mitigated the time delay until the solution is obtained in real-time humanoid gait control, achieving a more stable gait.
Resource Bisimilarity in Petri Nets is Decidable
Venue: arXiv cs.LO 2022
Year: 2022

Petri nets are a popular formalism for modeling and analyzing distributed systems. Tokens in Petri net models can represent the control flow state or resources produced/consumed by transition firings. We define a resource as a part (a submultiset) of Petri net markings and call two resources equivalent when replacing one of them with another in any marking does not change the observable Petri net behavior. We consider resource similarity and resource bisimilarity, two congruent restrictions of bisimulation equivalence on Petri net markings. Previously it was proved that resource similarity (the largest congruence included in bisimulation equivalence) is undecidable. Here we present an algorithm for checking resource bisimilarity, thereby proving that this relation (the largest congruence included in bisimulation equivalence that is a bisimulation) is decidable. We also give an example of two resources in a Petri net that are similar but not bisimilar.