OpenRaiser/Intern-Atlas huggingface dataset:
Using Timeliness in Tracking Infections
Venue: arXiv cs.IT 2022
Year: 2022

We consider real-time timely tracking of infection status (e.g., covid-19) of individuals in a population. In this work, a health care provider wants to detect infected people as well as people who have recovered from the disease as quickly as possible. In order to measure the timeliness of the tracking process, we use the long-term average difference between the actual infection status of the people and their real-time estimate by the health care provider based on the most recent test results. We first find an analytical expression for this average difference for given test rates, infection rates and recovery rates of people. Next, we propose an alternating minimization based algorithm to find the test rates that minimize the average difference. We observe that if the total test rate is limited, instead of testing all members of the population equally, only a portion of the population may be tested in unequal rates calculated based on their infection and recovery rates. Next, we characterize the average difference when the test measurements are erroneous (i.e., noisy). Further, we consider the case where the infection status of individuals may be dependent, which happens when an infected person spreads the disease to another person if they are not detected and isolated by the health care provider. Then, we consider an age of incorrect information based error metric where the staleness metric increases linearly over time as long as the health care provider does not detect the changes in the infection status of the people. In numerical results, we observe that an increased population size increases diversity of people with different infection and recovery rates which may be exploited to spend testing capacity more efficiently. Depending on the health care provider's preferences, test rate allocation can be adjusted to detect either the infected people or the recovered people more quickly.
Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs
Venue: arXiv cs.CG 2022
Year: 2022

We initiate the study of diameter computation in geometric intersection graphs from the fine-grained complexity perspective. A geometric intersection graph is a graph whose vertices correspond to some shapes in $d$-dimensional Euclidean space, such as balls, segments, or hypercubes, and whose edges correspond to pairs of intersecting shapes. The diameter of a graph is the largest distance realized by a pair of vertices in the graph. Computing the diameter in near-quadratic time is possible in several classes of intersection graphs [Chan and Skrepetos 2019], but it is not at all clear if these algorithms are optimal, especially since in the related class of planar graphs the diameter can be computed in $\widetilde{\mathcal{O}}(n^{5/3})$ time [Cabello 2019, Gawrychowski et al. 2021]. In this work we (conditionally) rule out sub-quadratic algorithms in several classes of intersection graphs, i.e., algorithms of running time $\mathcal{O}(n^{2-δ})$ for some $δ>0$. In particular, there are no sub-quadratic algorithms already for fat objects in small dimensions: unit balls in $\mathbb{R}^3$ or congruent equilateral triangles in $\mathbb{R}^2$. For unit segments and congruent equilateral triangles, we can even rule out strong sub-quadratic approximations already in $\mathbb{R}^2$. It seems that the hardness of approximation may also depend on dimensionality: for axis-parallel unit hypercubes in~$\mathbb{R}^{12}$, distinguishing between diameter 2 and 3 needs quadratic time (ruling out $(3/2-\varepsilon)$- approximations), whereas for axis-parallel unit squares, we give an algorithm that distinguishes between diameter $2$ and $3$ in near-linear time. Note that many of our lower bounds match the best known algorithms up to sub-polynomial factors.
WaveMix: Resource-efficient Token Mixing for Images
Venue: arXiv cs.CV 2022
Year: 2022

Although certain vision transformer (ViT) and CNN architectures generalize well on vision tasks, it is often impractical to use them on green, edge, or desktop computing due to their computational requirements for training and even testing. We present WaveMix as an alternative neural architecture that uses a multi-scale 2D discrete wavelet transform (DWT) for spatial token mixing. Unlike ViTs, WaveMix neither unrolls the image nor requires self-attention of quadratic complexity. Additionally, DWT introduces another inductive bias -- besides convolutional filtering -- to utilize the 2D structure of an image to improve generalization. The multi-scale nature of the DWT also reduces the requirement for a deeper architecture compared to the CNNs, as the latter relies on pooling for partial spatial mixing. WaveMix models show generalization that is competitive with ViTs, CNNs, and token mixers on several datasets while requiring lower GPU RAM (training and testing), number of computations, and storage. WaveMix have achieved State-of-the-art (SOTA) results in EMNIST Byclass and EMNIST Balanced datasets.
Low-Loss Subspace Compression for Clean Gains against Multi-Agent Backdoor Attacks
Venue: arXiv cs.LG 2022
Year: 2022

Recent exploration of the multi-agent backdoor attack demonstrated the backfiring effect, a natural defense against backdoor attacks where backdoored inputs are randomly classified. This yields a side-effect of low accuracy w.r.t. clean labels, which motivates this paper's work on the construction of multi-agent backdoor defenses that maximize accuracy w.r.t. clean labels and minimize that of poison labels. Founded upon agent dynamics and low-loss subspace construction, we contribute three defenses that yield improved multi-agent backdoor robustness.
Learning to Bound: A Generative Cramér-Rao Bound
Venue: arXiv cs.LG 2022
Year: 2022

The Cramér-Rao bound (CRB), a well-known lower bound on the performance of any unbiased parameter estimator, has been used to study a wide variety of problems. However, to obtain the CRB, requires an analytical expression for the likelihood of the measurements given the parameters, or equivalently a precise and explicit statistical model for the data. In many applications, such a model is not available. Instead, this work introduces a novel approach to approximate the CRB using data-driven methods, which removes the requirement for an analytical statistical model. This approach is based on the recent success of deep generative models in modeling complex, high-dimensional distributions. Using a learned normalizing flow model, we model the distribution of the measurements and obtain an approximation of the CRB, which we call Generative Cramér-Rao Bound (GCRB). Numerical experiments on simple problems validate this approach, and experiments on two image processing tasks of image denoising and edge detection with a learned camera noise model demonstrate its power and benefits.
High-Dimensional Expanders from Chevalley Groups
Venue: arXiv cs.DM 2022
Year: 2022

Let $Φ$ be an irreducible root system (other than $G_2$) of rank at least $2$, let $\mathbb{F}$ be a finite field with $p = \operatorname{char} \mathbb{F} > 3$, and let $\mathrm{G}(Φ,\mathbb{F})$ be the corresponding Chevalley group. We describe a strongly explicit high-dimensional expander (HDX) family of dimension $\mathrm{rank}(Φ)$, where $\mathrm{G}(Φ,\mathbb{F})$ acts simply transitively on the top-dimensional faces; these are $λ$-spectral HDXs with $λ\to 0$ as $p \to \infty$. This generalizes a construction of Kaufman and Oppenheim (STOC 2018), which corresponds to the case $Φ= A_d$. Our work gives three new families of spectral HDXs of any dimension $\ge 2$, and four exceptional constructions of dimension $4$, $6$, $7$, and $8$.
Detection of AI Synthesized Hindi Speech
Venue: arXiv cs.SD 2022
Year: 2022

The recent advancements in generative artificial speech models have made possible the generation of highly realistic speech signals. At first, it seems exciting to obtain these artificially synthesized signals such as speech clones or deep fakes but if left unchecked, it may lead us to digital dystopia. One of the primary focus in audio forensics is validating the authenticity of a speech. Though some solutions are proposed for English speeches but the detection of synthetic Hindi speeches have not gained much attention. Here, we propose an approach for discrimination of AI synthesized Hindi speech from an actual human speech. We have exploited the Bicoherence Phase, Bicoherence Magnitude, Mel Frequency Cepstral Coefficient (MFCC), Delta Cepstral, and Delta Square Cepstral as the discriminating features for machine learning models. Also, we extend the study to using deep neural networks for extensive experiments, specifically VGG16 and homemade CNN as the architecture models. We obtained an accuracy of 99.83% with VGG16 and 99.99% with homemade CNN models.
Algorithmic audits of algorithms, and the law
Venue: arXiv cs.CY 2022
Year: 2022

Algorithmic decision making is now widespread, ranging from health care allocation to more common actions such as recommendation or information ranking. The aim to audit these algorithms has grown alongside. In this paper, we focus on external audits that are conducted by interacting with the user side of the target algorithm, hence considered as a black box. Yet, the legal framework in which these audits take place is mostly ambiguous to researchers developing them: on the one hand, the legal value of the audit outcome is uncertain; on the other hand the auditors' rights and obligations are unclear. The contribution of this paper is to articulate two canonical audit forms to law, to shed light on these aspects: 1) the first audit form (we coin the Bobby audit form) checks a predicate against the algorithm, while the second (Sherlock) is more loose and opens up to multiple investigations. We find that: Bobby audits are more amenable to prosecution, yet are delicate as operating on real user data. This can lead to reject by a court (notion of admissibility). Sherlock audits craft data for their operation, most notably to build surrogates of the audited algorithm. It is mostly used for acts for whistleblowing, as even if accepted as a proof, the evidential value will be low in practice. 2) these two forms require the prior respect of a proper right to audit, granted by law or by the platform being audited; otherwise the auditor will be also prone to prosecutions regardless of the audit outcome. This article thus highlights the relation of current audits with law, in order to structure the growing field of algorithm auditing.
Biometric recognition: why not massively adopted yet?
Venue: arXiv cs.CY 2022
Year: 2022

Although there has been a dramatically reduction on the prices of capturing devices and an increase on computing power in the last decade, it seems that biometric systems are still far from massive adoption for civilian applications. This paper deals with the causes of this phenomenon, as well as some misconceptions regarding biometric identification.
Judging the algorithm: A case study on the risk assessment tool for gender-based violence implemented in the Basque country
Venue: arXiv cs.CY 2022
Year: 2022

Since 2010, the output of a risk assessment tool that predicts how likely an individual is to commit severe violence against their partner has been integrated within the Basque country courtrooms. The EPV-R, the tool developed to assist police officers during the assessment of gender-based violence cases, was also incorporated to assist the decision-making of judges. With insufficient training, judges are exposed to an algorithmic output that influences the human decision of adopting measures in cases of gender-based violence. In this paper, we examine the risks, harms and limits of algorithmic governance within the context of gender-based violence. Through the lens of an Spanish judge exposed to this tool, we analyse how the EPV-R is impacting on the justice system. Moving beyond the risks of unfair and biased algorithmic outputs, we examine legal, social and technical pitfalls such as opaque implementation, efficiency's paradox and feedback loop, that could led to unintended consequences on women who suffer gender-based violence. Our interdisciplinary framework highlights the importance of understanding the impact and influence of risk assessment tools within judicial decision-making and increase awareness about its implementation in this context.
Provably Accurate and Scalable Linear Classifiers in Hyperbolic Spaces
Venue: arXiv cs.LG 2022
Year: 2022

Many high-dimensional practical data sets have hierarchical structures induced by graphs or time series. Such data sets are hard to process in Euclidean spaces and one often seeks low-dimensional embeddings in other space forms to perform the required learning tasks. For hierarchical data, the space of choice is a hyperbolic space because it guarantees low-distortion embeddings for tree-like structures. The geometry of hyperbolic spaces has properties not encountered in Euclidean spaces that pose challenges when trying to rigorously analyze algorithmic solutions. We propose a unified framework for learning scalable and simple hyperbolic linear classifiers with provable performance guarantees. The gist of our approach is to focus on Poincaré ball models and formulate the classification problems using tangent space formalisms. Our results include a new hyperbolic perceptron algorithm as well as an efficient and highly accurate convex optimization setup for hyperbolic support vector machine classifiers. Furthermore, we adapt our approach to accommodate second-order perceptrons, where data is preprocessed based on second-order information (correlation) to accelerate convergence, and strategic perceptrons, where potentially manipulated data arrives in an online manner and decisions are made sequentially. The excellent performance of the Poincaré second-order and strategic perceptrons shows that the proposed framework can be extended to general machine learning problems in hyperbolic spaces. Our experimental results, pertaining to synthetic, single-cell RNA-seq expression measurements, CIFAR10, Fashion-MNIST and mini-ImageNet, establish that all algorithms provably converge and have complexity comparable to those of their Euclidean counterparts. Accompanying codes can be found at: https://github.com/thupchnsky/PoincareLinearClassification.
Towards Efficient Data-Centric Robust Machine Learning with Noise-based Augmentation
Venue: arXiv cs.LG 2022
Year: 2022

The data-centric machine learning aims to find effective ways to build appropriate datasets which can improve the performance of AI models. In this paper, we mainly focus on designing an efficient data-centric scheme to improve robustness for models towards unforeseen malicious inputs in the black-box test settings. Specifically, we introduce a noised-based data augmentation method which is composed of Gaussian Noise, Salt-and-Pepper noise, and the PGD adversarial perturbations. The proposed method is built on lightweight algorithms and proved highly effective based on comprehensive evaluations, showing good efficiency on computation cost and robustness enhancement. In addition, we share our insights about the data-centric robust machine learning gained from our experiments.
Online Target Localization using Adaptive Belief Propagation in the HMM Framework
Venue: arXiv cs.RO 2022
Year: 2022

This paper proposes a novel adaptive sample space-based Viterbi algorithm for target localization in an online manner. The method relies on discretizing the target's motion space into cells representing a finite number of hidden states. Then, the most probable trajectory of the tracked target is computed via dynamic programming in a Hidden Markov Model (HMM) framework. The proposed method uses a Bayesian estimation framework which is neither limited to Gaussian noise models nor requires a linearized target motion model or sensor measurement models. However, an HMM-based approach to localization can suffer from poor computational complexity in scenarios where the number of hidden states increases due to high-resolution modeling or target localization in a large space. To improve this poor computational complexity, this paper proposes a belief propagation in the most probable belief space with a low to high-resolution sequentially, reducing the required resources significantly. The proposed method is inspired by the k-d Tree algorithm (e.g., quadtree) commonly used in the computer vision field. Experimental tests using an ultra-wideband (UWB) sensor network demonstrate our results.
Virtual Displacement based Discontinuity Layout Optimization
Venue: arXiv cs.CE 2022
Year: 2022

Discontinuity layout optimization (DLO) is a relatively new upper bound limit analysis method. Compared to classic topology optimization methods, aimed at obtaining the optimum design of a structure by considering its self-weight, building cost or bearing capacity, DLO optimizes the failure pattern of the structure under specific loading conditions and constraints by minimizing the dissipation energy. In this work, we present a modified DLO algorithm that contains all of the advantages of DLO. It is referred to virtual displacement-based discontinuity layout optimization (VDLO). VDLO takes the stress state of a loaded structure as a snapshot and correspondingly provides the optimum failure pattern, which greatly extends the application potential of DLO. Numerical examples indicate the effectiveness and flexibility of VDLO. It is regarded as a highly promising supplemental tool for other numerical methods in element-/node-based frameworks.
Where Does the Performance Improvement Come From? -- A Reproducibility Concern about Image-Text Retrieval
Venue: arXiv cs.IR 2022
Year: 2022

This article aims to provide the information retrieval community with some reflections on recent advances in retrieval learning by analyzing the reproducibility of image-text retrieval models. Due to the increase of multimodal data over the last decade, image-text retrieval has steadily become a major research direction in the field of information retrieval. Numerous researchers train and evaluate image-text retrieval algorithms using benchmark datasets such as MS-COCO and Flickr30k. Research in the past has mostly focused on performance, with multiple state-of-the-art methodologies being suggested in a variety of ways. According to their assertions, these techniques provide improved modality interactions and hence more precise multimodal representations. In contrast to previous works, we focus on the reproducibility of the approaches and the examination of the elements that lead to improved performance by pretrained and nonpretrained models in retrieving images and text. To be more specific, we first examine the related reproducibility concerns and explain why our focus is on image-text retrieval tasks. Second, we systematically summarize the current paradigm of image-text retrieval models and the stated contributions of those approaches. Third, we analyze various aspects of the reproduction of pretrained and nonpretrained retrieval models. To complete this, we conducted ablation experiments and obtained some influencing factors that affect retrieval recall more than the improvement claimed in the original paper. Finally, we present some reflections and challenges that the retrieval community should consider in the future. Our source code is publicly available at https://github.com/WangFei-2019/Image-text-Retrieval.
DARER: Dual-task Temporal Relational Recurrent Reasoning Network for Joint Dialog Sentiment Classification and Act Recognition
Venue: arXiv cs.CL 2022
Year: 2022

The task of joint dialog sentiment classification (DSC) and act recognition (DAR) aims to simultaneously predict the sentiment label and act label for each utterance in a dialog. In this paper, we put forward a new framework which models the explicit dependencies via integrating \textit{prediction-level interactions} other than semantics-level interactions, more consistent with human intuition. Besides, we propose a speaker-aware temporal graph (SATG) and a dual-task relational temporal graph (DRTG) to introduce \textit{temporal relations} into dialog understanding and dual-task reasoning. To implement our framework, we propose a novel model dubbed DARER, which first generates the context-, speaker- and temporal-sensitive utterance representations via modeling SATG, then conducts recurrent dual-task relational reasoning on DRTG, in which process the estimated label distributions act as key clues in prediction-level interactions. Experiment results show that DARER outperforms existing models by large margins while requiring much less computation resource and costing less training time. Remarkably, on DSC task in Mastodon, DARER gains a relative improvement of about 25% over previous best model in terms of F1, with less than 50% parameters and about only 60% required GPU memory.
HyperPELT: Unified Parameter-Efficient Language Model Tuning for Both Language and Vision-and-Language Tasks
Venue: arXiv cs.CL 2022
Year: 2022

The workflow of pretraining and fine-tuning has emerged as a popular paradigm for solving various NLP and V&L (Vision-and-Language) downstream tasks. With the capacity of pretrained models growing rapidly, how to perform parameter-efficient fine-tuning has become fairly important for quick transfer learning and deployment. In this paper, we design a novel unified parameter-efficient transfer learning framework that works effectively on both pure language and V&L tasks. In particular, we use a shared hypernetwork that takes trainable hyper-embeddings as input, and outputs weights for fine-tuning different small modules in a pretrained language model, such as tuning the parameters inserted into multi-head attention blocks (i.e., prefix-tuning) and feed-forward blocks (i.e., adapter-tuning). We define a set of embeddings (e.g., layer, block, task and visual embeddings) as the key components to calculate hyper-embeddings, which thus can support both pure language and V&L tasks. Our proposed framework adds fewer trainable parameters in multi-task learning while achieving superior performances and transfer ability compared to state-of-the-art methods. Empirical results on the GLUE benchmark and multiple V&L tasks confirm the effectiveness of our framework on both textual and visual modalities.
An Analysis of Measure-Valued Derivatives for Policy Gradients
Venue: arXiv cs.LG 2022
Year: 2022

Reinforcement learning methods for robotics are increasingly successful due to the constant development of better policy gradient techniques. A precise (low variance) and accurate (low bias) gradient estimator is crucial to face increasingly complex tasks. Traditional policy gradient algorithms use the likelihood-ratio trick, which is known to produce unbiased but high variance estimates. More modern approaches exploit the reparametrization trick, which gives lower variance gradient estimates but requires differentiable value function approximators. In this work, we study a different type of stochastic gradient estimator - the Measure-Valued Derivative. This estimator is unbiased, has low variance, and can be used with differentiable and non-differentiable function approximators. We empirically evaluate this estimator in the actor-critic policy gradient setting and show that it can reach comparable performance with methods based on the likelihood-ratio or reparametrization tricks, both in low and high-dimensional action spaces. With this work, we want to show that the Measure-Valued Derivative estimator can be a useful alternative to other policy gradient estimators.