OpenRaiser/Intern-Atlas huggingface dataset:
ENI: Quantifying Environment Compatibility for Natural Walking in Virtual Reality
Venue: arXiv cs.GR 2023
Year: 2023

We present a novel metric to analyze the similarity between the physical environment and the virtual environment for natural walking in virtual reality. Our approach is general and can be applied to any pair of physical and virtual environments. We use geometric techniques based on conforming constrained Delaunay triangulations and visibility polygons to compute the Environment Navigation Incompatibility (ENI) metric that can be used to measure the complexity of performing simultaneous navigation. We demonstrate applications of ENI for highlighting regions of incompatibility for a pair of environments, guiding the design of the virtual environments to make them more compatible with a fixed physical environment, and evaluating the performance of different redirected walking controllers. We validate the ENI metric using simulations and two user studies. Results of our simulations and user studies show that in the environment pair that our metric identified as more navigable, users were able to walk for longer before colliding with objects in the physical environment. Overall, ENI is the first general metric that can automatically identify regions of high and low compatibility in physical and virtual environments. Our project website is available at https://gamma.umd.edu/eni/.
Bridging Adversarial and Nonstationary Multi-armed Bandit
Venue: arXiv cs.LG 2023
Year: 2023

In the multi-armed bandit framework, there are two formulations that are commonly employed to handle time-varying reward distributions: adversarial bandit and nonstationary bandit. Although their oracles, algorithms, and regret analysis differ significantly, we provide a unified formulation in this paper that smoothly bridges the two as special cases. The formulation uses an oracle that takes the best-fixed arm within time windows. Depending on the window size, it turns into the oracle in hindsight in the adversarial bandit and dynamic oracle in the nonstationary bandit. We provide algorithms that attain the optimal regret with the matching lower bound.
CFU Playground: Full-Stack Open-Source Framework for Tiny Machine Learning (tinyML) Acceleration on FPGAs
Venue: arXiv cs.LG 2023
Year: 2023

Need for the efficient processing of neural networks has given rise to the development of hardware accelerators. The increased adoption of specialized hardware has highlighted the need for more agile design flows for hardware-software co-design and domain-specific optimizations. In this paper, we present CFU Playground: a full-stack open-source framework that enables rapid and iterative design and evaluation of machine learning (ML) accelerators for embedded ML systems. Our tool provides a completely open-source end-to-end flow for hardware-software co-design on FPGAs and future systems research. This full-stack framework gives the users access to explore experimental and bespoke architectures that are customized and co-optimized for embedded ML. Our rapid, deploy-profile-optimization feedback loop lets ML hardware and software developers achieve significant returns out of a relatively small investment in customization. Using CFU Playground's design and evaluation loop, we show substantial speedups between 55$\times$ and 75$\times$. The soft CPU coupled with the accelerator opens up a new, rich design space between the two components that we explore in an automated fashion using Vizier, an open-source black-box optimization service.
Bidirectional Runtime Enforcement of First-Order Branching-Time Properties
Venue: arXiv cs.LO 2023
Year: 2023

Runtime enforcement is a dynamic analysis technique that instruments a monitor with a system in order to ensure its correctness as specified by some property. This paper explores bidirectional enforcement strategies for properties describing the input and output behaviour of a system. We develop an operational framework for bidirectional enforcement and use it to study the enforceability of the safety fragment of Hennessy-Milner logic with recursion (sHML). We provide an automated synthesis function that generates correct monitors from sHML formulas, and show that this logic is enforceable via a specific type of bidirectional enforcement monitors called action disabling monitors.
Ancestral Instrument Method for Causal Inference without Complete Knowledge
Venue: arXiv cs.AI 2023
Year: 2023

Unobserved confounding is the main obstacle to causal effect estimation from observational data. Instrumental variables (IVs) are widely used for causal effect estimation when there exist latent confounders. With the standard IV method, when a given IV is valid, unbiased estimation can be obtained, but the validity requirement on a standard IV is strict and untestable. Conditional IVs have been proposed to relax the requirement of standard IVs by conditioning on a set of observed variables (known as a conditioning set for a conditional IV). However, the criterion for finding a conditioning set for a conditional IV needs a directed acyclic graph (DAG) representing the causal relationships of both observed and unobserved variables. This makes it challenging to discover a conditioning set directly from data. In this paper, by leveraging maximal ancestral graphs (MAGs) for causal inference with latent variables, we study the graphical properties of ancestral IVs, a type of conditional IVs using MAGs, and develop the theory to support data-driven discovery of the conditioning set for a given ancestral IV in data under the pretreatment variable assumption. Based on the theory, we develop an algorithm for unbiased causal effect estimation with a given ancestral IV and observational data. Extensive experiments on synthetic and real-world datasets demonstrate the performance of the algorithm in comparison with existing IV methods.
The extreme upper tail of Japan's citation distribution reveals its research success
Venue: arXiv cs.DL 2023
Year: 2023

A number of indications, such as the number of Nobel Prize winners, show Japan to be a scientifically advanced country. However, standard bibliometric indicators place Japan as a scientifically developing country. The present study is based on the conjecture that scientific publications from Japan belong to two different populations: one originates from studies that advance science and includes highly cited papers, while the other is formed by poorly cited papers with almost zero probability of being highly cited. Although these two categories of papers cannot be easily identified and separated, the scientific level of Japan can be tested by studying the extreme upper tail of the citation distribution of all scientific articles. In contrast to standard bibliometric indicators, which are calculated from the total number of papers or from sets of papers in which the two categories of papers are mixed, in the extreme upper tail, only papers that are addressed to the advance of science will be present. Based on the extreme upper tail, Japan belongs to the group of scientifically advanced countries and is significantly different from countries with a low scientific level. The number of Clarivate Citation laureates also supports our hypothesis that some citation-based metrics do not reveal the high scientific level of Japan. Our findings suggest that Japan is an extreme case of inaccuracy of some citation metrics; the same drawback might affect other countries, although to a lesser degree.
A Unified Framework for Calculating First Arrival Position Density in Molecular Communication
Venue: arXiv cs.IT 2023
Year: 2023

This paper introduces a novel unified framework for calculating the first arrival position (FAP) density in diffusion-based molecular communication (MC) systems with fully-absorbing receivers, applicable to any spatial dimension or receiver shape. We validate the effectiveness of our proposed method by presenting two concrete examples from the MC literature: the 2D line receiver and 3D spherical receiver. Our approach successfully reproduces existing results on FAP density and further enhances the original formula for the 2D line receiver by accommodating arbitrary drift directions. The proposed framework offers a comprehensive and versatile solution for determining FAP density in diffusive MC channels with fully-absorbing receivers, paving the way for more robust and efficient system designs.
Fine-grained Graph Learning for Multi-view Subspace Clustering
Venue: arXiv cs.LG 2023
Year: 2023

Multi-view subspace clustering (MSC) is a popular unsupervised method by integrating heterogeneous information to reveal the intrinsic clustering structure hidden across views. Usually, MSC methods use graphs (or affinity matrices) fusion to learn a common structure, and further apply graph-based approaches to clustering. Despite progress, most of the methods do not establish the connection between graph learning and clustering. Meanwhile, conventional graph fusion strategies assign coarse-grained weights to combine multi-graph, ignoring the importance of local structure. In this paper, we propose a fine-grained graph learning framework for multi-view subspace clustering (FGL-MSC) to address these issues. To utilize the multi-view information sufficiently, we design a specific graph learning method by introducing graph regularization and a local structure fusion pattern. The main challenge is how to optimize the fine-grained fusion weights while generating the learned graph that fits the clustering task, thus making the clustering representation meaningful and competitive. Accordingly, an iterative algorithm is proposed to solve the above joint optimization problem, which obtains the learned graph, the clustering representation, and the fusion weights simultaneously. Extensive experiments on eight real-world datasets show that the proposed framework has comparable performance to the state-of-the-art methods. The source code of the proposed method is available at https://github.com/siriuslay/FGL-MSC.
Polynomial Turing Compressions for Some Graph Problems Parameterized by Modular-Width
Venue: arXiv cs.DS 2023
Year: 2023

A polynomial Turing compression (PTC) for a parameterized problem $L$ is a polynomial time Turing machine that has access to an oracle for a problem $L'$ such that a polynomial in the input parameter bounds each query. Meanwhile, a polynomial (many-one) compression (PC) can be regarded as a restricted variant of PTC where the machine can query the oracle exactly once and must output the same answer as the oracle. Bodlaender et al. (ICALP 2008) and Fortnow and Santhanam (STOC 2008) initiated an impressive hardness theory for PC under the assumption coNP $\not\subseteq$ NP/poly. Since PTC is a generalization of PC, we define $\mathcal{C}$ as the set of all problems that have PTCs but have no PCs under the assumption coNP $\not\subseteq$ NP/poly. Based on the hardness theory for PC, Fernau et al. (STACS 2009) found the first problem Leaf Out-tree($k$) in $\mathcal{C}$. However, very little is known about $\mathcal{C}$, as only a dozen problems were shown to belong to the complexity class in the last ten years. Several problems are open, for example, whether CNF-SAT($n$) and $k$-path are in $\mathcal{C}$, and novel ideas are required to better understand the fundamental differences between PTCs and PCs. In this paper, we enrich our knowledge about $\mathcal{C}$ by showing that several problems parameterized by modular-width ($mw$) belong to $\mathcal{C}$. More specifically, exploiting the properties of the well-studied structural graph parameter $mw$, we demonstrate 17 problems parameterized by $mw$ are in $\mathcal{C}$, such as Chromatic Number($mw$) and Hamiltonian Cycle($mw$). In addition, we develop a general recipe to prove the existence of PTCs for a large class of problems, including our 17 problems.
A Fine-Grained Analysis of Public Opinion toward Chinese Technology Companies on Reddit
Venue: arXiv cs.SI 2023
Year: 2023

In the face of the growing global influence and prevalence of Chinese technology companies, governments worldwide have expressed concern and mistrust toward these companies. There is a scarcity of research that specifically examines the widespread public response to this phenomenon on a large scale. This study aims to fill in the gap in understanding public opinion toward Chinese technology companies using Reddit data, a popular news-oriented social media platform. We employ the state-of-the-art transformer model to build a reliable sentiment classifier. We then use LDA to extract the topics associated with positive and negative comments. We also conduct content analysis by studying the changes in the semantic meaning of the companies' names over time. Our main findings include the following: 1) Notable difference exists in the proportions of positive comments (8.42%) and negative comments (14.12%); 2) Positive comments are mostly associated with the companies' consumer products, such as smartphones, laptops, and wearable electronics. Negative comments have a more diverse topic distribution (notable topics include criticism toward the platform, dissatisfaction with the companies' smartphone products, companies' ties to the Chinese government, data security concerns, 5G construction, and general political discussions); and 3) Characterization of each technology company is usually centered around a particular predominant theme related to the company, while real-world political events may trigger drastic changes in users' characterization.
Demystifying Reinforcement Learning in Time-Varying Systems
Venue: arXiv cs.LG 2023
Year: 2023

Recent research has turned to Reinforcement Learning (RL) to solve challenging decision problems, as an alternative to hand-tuned heuristics. RL can learn good policies without the need for modeling the environment's dynamics. Despite this promise, RL remains an impractical solution for many real-world systems problems. A particularly challenging case occurs when the environment changes over time, i.e. it exhibits non-stationarity. In this work, we characterize the challenges introduced by non-stationarity, shed light on the range of approaches to them and develop a robust framework for addressing them to train RL agents in live systems. Such agents must explore and learn new environments, without hurting the system's performance, and remember them over time. To this end, our framework (i) identifies different environments encountered by the live system, (ii) triggers exploration when necessary, (iii) takes precautions to retain knowledge from prior environments, and (iv) employs safeguards to protect the system's performance when the RL agent makes mistakes. We apply our framework to two systems problems, straggler mitigation and adaptive video streaming, and evaluate it against a variety of alternative approaches using real-world and synthetic data. We show that all components of the framework are necessary to cope with non-stationarity and provide guidance on alternative design choices for each component.
FairIF: Boosting Fairness in Deep Learning via Influence Functions with Validation Set Sensitive Attributes
Venue: arXiv cs.LG 2023
Year: 2023

Most fair machine learning methods either highly rely on the sensitive information of the training samples or require a large modification on the target models, which hinders their practical application. To address this issue, we propose a two-stage training algorithm named FAIRIF. It minimizes the loss over the reweighted data set (second stage) where the sample weights are computed to balance the model performance across different demographic groups (first stage). FAIRIF can be applied on a wide range of models trained by stochastic gradient descent without changing the model, while only requiring group annotations on a small validation set to compute sample weights. Theoretically, we show that, in the classification setting, three notions of disparity among different groups can be mitigated by training with the weights. Experiments on synthetic data sets demonstrate that FAIRIF yields models with better fairness-utility trade-offs against various types of bias; and on real-world data sets, we show the effectiveness and scalability of FAIRIF. Moreover, as evidenced by the experiments with pretrained models, FAIRIF is able to alleviate the unfairness issue of pretrained models without hurting their performance.
Synthesis and Reconstruction of Fingerprints using Generative Adversarial Networks
Venue: arXiv cs.CV 2023
Year: 2023

Deep learning-based models have been shown to improve the accuracy of fingerprint recognition. While these algorithms show exceptional performance, they require large-scale fingerprint datasets for training and evaluation. In this work, we propose a novel fingerprint synthesis and reconstruction framework based on the StyleGan2 architecture, to address the privacy issues related to the acquisition of such large-scale datasets. We also derive a computational approach to modify the attributes of the generated fingerprint while preserving their identity. This allows synthesizing multiple different fingerprint images per finger. In particular, we introduce the SynFing synthetic fingerprints dataset consisting of 100K image pairs, each pair corresponding to the same identity. The proposed framework was experimentally shown to outperform contemporary state-of-the-art approaches for both fingerprint synthesis and reconstruction. It significantly improved the realism of the generated fingerprints, both visually and in terms of their ability to spoof fingerprint-based verification systems. The code and fingerprints dataset are publicly available: https://github.com/rafaelbou/fingerprint_generator.
A Deep Convolutional Neural Networks Based Multi-Task Ensemble Model for Aspect and Polarity Classification in Persian Reviews
Venue: arXiv cs.CL 2023
Year: 2023

Aspect-based sentiment analysis is of great importance and application because of its ability to identify all aspects discussed in the text. However, aspect-based sentiment analysis will be most effective when, in addition to identifying all the aspects discussed in the text, it can also identify their polarity. Most previous methods use the pipeline approach, that is, they first identify the aspects and then identify the polarities. Such methods are unsuitable for practical applications since they can lead to model errors. Therefore, in this study, we propose a multi-task learning model based on Convolutional Neural Networks (CNNs), which can simultaneously detect aspect category and detect aspect category polarity. creating a model alone may not provide the best predictions and lead to errors such as bias and high variance. To reduce these errors and improve the efficiency of model predictions, combining several models known as ensemble learning may provide better results. Therefore, the main purpose of this article is to create a model based on an ensemble of multi-task deep convolutional neural networks to enhance sentiment analysis in Persian reviews. We evaluated the proposed method using a Persian language dataset in the movie domain. Jacquard index and Hamming loss measures were used to evaluate the performance of the developed models. The results indicate that this new approach increases the efficiency of the sentiment analysis model in the Persian language.
Towards Adversarial Evaluations for Inexact Machine Unlearning
Venue: arXiv cs.LG 2023
Year: 2023

Machine Learning models face increased concerns regarding the storage of personal user data and adverse impacts of corrupted data like backdoors or systematic bias. Machine Unlearning can address these by allowing post-hoc deletion of affected training data from a learned model. Achieving this task exactly is computationally expensive; consequently, recent works have proposed inexact unlearning algorithms to solve this approximately as well as evaluation methods to test the effectiveness of these algorithms. In this work, we first outline some necessary criteria for evaluation methods and show no existing evaluation satisfies them all. Then, we design a stronger black-box evaluation method called the Interclass Confusion (IC) test which adversarially manipulates data during training to detect the insufficiency of unlearning procedures. We also propose two analytically motivated baseline methods~(EU-k and CF-k) which outperform several popular inexact unlearning methods. Overall, we demonstrate how adversarial evaluation strategies can help in analyzing various unlearning phenomena which can guide the development of stronger unlearning algorithms.
Surrogate-assisted distributed swarm optimisation for computationally expensive geoscientific models
Venue: arXiv cs.DC 2023
Year: 2023

Evolutionary algorithms provide gradient-free optimisation which is beneficial for models that have difficulty in obtaining gradients; for instance, geoscientific landscape evolution models. However, such models are at times computationally expensive and even distributed swarm-based optimisation with parallel computing struggles. We can incorporate efficient strategies such as surrogate-assisted optimisation to address the challenges; however, implementing inter-process communication for surrogate-based model training is difficult. In this paper, we implement surrogate-based estimation of fitness evaluation in distributed swarm optimisation over a parallel computing architecture. We first test the framework on a set of benchmark optimisation problems and then apply it to a geoscientific model that features a landscape evolution model. Our results demonstrate very promising results for benchmark functions and the Badlands landscape evolution model. We obtain a reduction in computational time while retaining optimisation solution accuracy through the use of surrogates in a parallel computing environment. The major contribution of the paper is in the application of surrogate-based optimisation for geoscientific models which can in the future help in a better understanding of paleoclimate and geomorphology.
Taylor3DNet: Fast 3D Shape Inference With Landmark Points Based Taylor Series
Venue: arXiv cs.CV 2023
Year: 2023

Benefiting from the continuous representation ability, deep implicit functions can represent a shape at infinite resolution. However, extracting high-resolution iso-surface from an implicit function requires forward-propagating a network with a large number of parameters for numerous query points, thus preventing the generation speed. Inspired by the Taylor series, we propose Taylo3DNet to accelerate the inference of implicit shape representations. Taylor3DNet exploits a set of discrete landmark points and their corresponding Taylor series coefficients to represent the implicit field of a 3D shape, and the number of landmark points is independent of the resolution of the iso-surface extraction. Once the coefficients corresponding to the landmark points are predicted, the network evaluation for each query point can be simplified as a low-order Taylor series calculation with several nearest landmark points. Based on this efficient representation, our Taylor3DNet achieves a significantly faster inference speed than classical network-based implicit functions. We evaluate our approach on reconstruction tasks with various input types, and the results demonstrate that our approach can improve the inference speed by a large margin without sacrificing the performance compared with state-of-the-art baselines.