OpenRaiser/Intern-Atlas huggingface dataset:
New Secure Sparse Inner Product with Applications to Machine Learning
Venue: arXiv cs.CR 2022
Year: 2022

Sparse inner product (SIP) has the attractive property of overhead being dominated by the intersection of inputs between parties, independent of the actual input size. It has intriguing prospects, especially for boosting machine learning on large-scale data, which is tangled with sparse data. In this paper, we investigate privacy-preserving SIP problems that have rarely been explored before. Specifically, we propose two concrete constructs, one requiring offline linear communication which can be amortized across queries, while the other has sublinear overhead but relies on the more computationally expensive tool. Our approach exploits state-of-the-art cryptography tools including garbled Bloom filters (GBF) and Private Information Retrieval (PIR) as the cornerstone, but carefully fuses them to obtain non-trivial overhead reductions. We provide formal security analysis of the proposed constructs and implement them into representative machine learning algorithms including k-nearest neighbors, naive Bayes classification and logistic regression. Compared to the existing efforts, our method achieves $2$-$50\times$ speedup in runtime and up to $10\times$ reduction in communication.
1st Place Solution in Google Universal Images Embedding
Venue: arXiv cs.CV 2022
Year: 2022

This paper presents the 1st place solution for the Google Universal Images Embedding Competition on Kaggle. The highlighted part of our solution is based on 1) A novel way to conduct training and fine-tuning; 2) The idea of a better ensemble in the pool of models that make embedding; 3) The potential trade-off between fine-tuning on high-resolution and overlapping patches; 4) The potential factors to work for the dynamic margin. Our solution reaches 0.728 in the private leader board, which achieve 1st place in Google Universal Images Embedding Competition.
Urban form and COVID-19 cases and deaths in Greater London: an urban morphometric approach
Venue: arXiv cs.CY 2022
Year: 2022

The COVID-19 pandemic generated a considerable debate in relation to urban density. This is an old debate, originated in mid 19th century's England with the emergence of public health and urban planning disciplines. While popularly linked, evidence suggests that such relationship cannot be generally assumed. Furthermore, urban density has been investigated in a spatially coarse manner (predominantly at city level) and never contextualised with other descriptors of urban form. In this work, we explore COVID-19 and urban form in Greater London, relating a comprehensive set of morphometric descriptors (including built-up density) to COVID-19 deaths and cases, while controlling for socioeconomic, ethnicity, age, and co-morbidity. We describe urban form at individual building level and then aggregate information for official neighbourhoods, allowing for a detailed intra-urban representation. Results show that: i) control variables significantly explain more variance of both COVID-19 cases and deaths than the morphometric descriptors; ii) of what the latter can explain, built-up density is indeed the most associated, though inversely. The typical London neighbourhood with high levels of COVID-19 infections and deaths resembles a suburb, featuring a low-density urban fabric dotted by larger free-standing buildings and framed by a poorly inter-connected street network.
CDConv: A Benchmark for Contradiction Detection in Chinese Conversations
Venue: arXiv cs.CL 2022
Year: 2022

Dialogue contradiction is a critical issue in open-domain dialogue systems. The contextualization nature of conversations makes dialogue contradiction detection rather challenging. In this work, we propose a benchmark for Contradiction Detection in Chinese Conversations, namely CDConv. It contains 12K multi-turn conversations annotated with three typical contradiction categories: Intra-sentence Contradiction, Role Confusion, and History Contradiction. To efficiently construct the CDConv conversations, we devise a series of methods for automatic conversation generation, which simulate common user behaviors that trigger chatbots to make contradictions. We conduct careful manual quality screening of the constructed conversations and show that state-of-the-art Chinese chatbots can be easily goaded into making contradictions. Experiments on CDConv show that properly modeling contextual information is critical for dialogue contradiction detection, but there are still unresolved challenges that require future research.
Comparing Synthetic Tabular Data Generation Between a Probabilistic Model and a Deep Learning Model for Education Use Cases
Venue: arXiv cs.LG 2022
Year: 2022

The ability to generate synthetic data has a variety of use cases across different domains. In education research, there is a growing need to have access to synthetic data to test certain concepts and ideas. In recent years, several deep learning architectures were used to aid in the generation of synthetic data but with varying results. In the education context, the sophistication of implementing different models requiring large datasets is becoming very important. This study aims to compare the application of synthetic tabular data generation between a probabilistic model specifically a Bayesian Network, and a deep learning model, specifically a Generative Adversarial Network using a classification task. The results of this study indicate that synthetic tabular data generation is better suited for the education context using probabilistic models (overall accuracy of 75%) than deep learning architecture (overall accuracy of 38%) because of probabilistic interdependence. Lastly, we recommend that other data types, should be explored and evaluated for their application in generating synthetic data for education use cases.
Logical Relations for Partial Features and Automatic Differentiation Correctness
Venue: arXiv cs.PL 2022
Year: 2022

We present a simple technique for semantic, open logical relations arguments about languages with recursive types, which, as we show, follows from a principled foundation in categorical semantics. We demonstrate how it can be used to give a very straightforward proof of correctness of practical forward- and reverse-mode dual numbers style automatic differentiation (AD) on ML-family languages. The key idea is to combine it with a suitable open logical relations technique for reasoning about differentiable partial functions (a suitable lifting of the partiality monad to logical relations), which we introduce.
Data-Model-Circuit Tri-Design for Ultra-Light Video Intelligence on Edge Devices
Venue: arXiv cs.CV 2022
Year: 2022

In this paper, we propose a data-model-hardware tri-design framework for high-throughput, low-cost, and high-accuracy multi-object tracking (MOT) on High-Definition (HD) video stream. First, to enable ultra-light video intelligence, we propose temporal frame-filtering and spatial saliency-focusing approaches to reduce the complexity of massive video data. Second, we exploit structure-aware weight sparsity to design a hardware-friendly model compression method. Third, assisted with data and model complexity reduction, we propose a sparsity-aware, scalable, and low-power accelerator design, aiming to deliver real-time performance with high energy efficiency. Different from existing works, we make a solid step towards the synergized software/hardware co-optimization for realistic MOT model implementation. Compared to the state-of-the-art MOT baseline, our tri-design approach can achieve 12.5x latency reduction, 20.9x effective frame rate improvement, 5.83x lower power, and 9.78x better energy efficiency, without much accuracy drop.
Nowhere to Hide: A Lightweight Unsupervised Detector against Adversarial Examples
Venue: arXiv cs.LG 2022
Year: 2022

Although deep neural networks (DNNs) have shown impressive performance on many perceptual tasks, they are vulnerable to adversarial examples that are generated by adding slight but maliciously crafted perturbations to benign images. Adversarial detection is an important technique for identifying adversarial examples before they are entered into target DNNs. Previous studies to detect adversarial examples either targeted specific attacks or required expensive computation. How design a lightweight unsupervised detector is still a challenging problem. In this paper, we propose an AutoEncoder-based Adversarial Examples (AEAE) detector, that can guard DNN models by detecting adversarial examples with low computation in an unsupervised manner. The AEAE includes only a shallow autoencoder but plays two roles. First, a well-trained autoencoder has learned the manifold of benign examples. This autoencoder can produce a large reconstruction error for adversarial images with large perturbations, so we can detect significantly perturbed adversarial examples based on the reconstruction error. Second, the autoencoder can filter out the small noise and change the DNN's prediction on adversarial examples with small perturbations. It helps to detect slightly perturbed adversarial examples based on the prediction distance. To cover these two cases, we utilize the reconstruction error and prediction distance from benign images to construct a two-tuple feature set and train an adversarial detector using the isolation forest algorithm. We show empirically that the AEAE is unsupervised and inexpensive against the most state-of-the-art attacks. Through the detection in these two cases, there is nowhere to hide adversarial examples.
Computing a Stable Distance on Merge Trees
Venue: arXiv cs.CG 2022
Year: 2022

Distances on merge trees facilitate visual comparison of collections of scalar fields. Two desirable properties for these distances to exhibit are 1) the ability to discern between scalar fields which other, less complex topological summaries cannot and 2) to still be robust to perturbations in the dataset. The combination of these two properties, known respectively as stability and discriminativity, has led to theoretical distances which are either thought to be or shown to be computationally complex and thus their implementations have been scarce. In order to design similarity measures on merge trees which are computationally feasible for more complex merge trees, many researchers have elected to loosen the restrictions on at least one of these two properties. The question still remains, however, if there are practical situations where trading these desirable properties is necessary. Here we construct a distance between merge trees which is designed to retain both discriminativity and stability. While our approach can be expensive for large merge trees, we illustrate its use in a setting where the number of nodes is small. This setting can be made more practical since we also provide a proof that persistence simplification increases the outputted distance by at most half of the simplified value. We demonstrate our distance measure on applications in shape comparison and on detection of periodicity in the von Kármán vortex street.
EventGraph: Event Extraction as Semantic Graph Parsing
Venue: arXiv cs.CL 2022
Year: 2022

Event extraction involves the detection and extraction of both the event triggers and corresponding event arguments. Existing systems often decompose event extraction into multiple subtasks, without considering their possible interactions. In this paper, we propose EventGraph, a joint framework for event extraction, which encodes events as graphs. We represent event triggers and arguments as nodes in a semantic graph. Event extraction therefore becomes a graph parsing problem, which provides the following advantages: 1) performing event detection and argument extraction jointly; 2) detecting and extracting multiple events from a piece of text; and 3) capturing the complicated interaction between event arguments and triggers. Experimental results on ACE2005 show that our model is competitive to state-of-the-art systems and has substantially improved the results on argument extraction. Additionally, we create two new datasets from ACE2005 where we keep the entire text spans for event arguments, instead of just the head word(s). Our code and models are released as open-source.
Decision-Making Among Bounded Rational Agents
Venue: arXiv cs.RO 2022
Year: 2022

When robots share the same workspace with other intelligent agents (e.g., other robots or humans), they must be able to reason about the behaviors of their neighboring agents while accomplishing the designated tasks. In practice, frequently, agents do not exhibit absolutely rational behavior due to their limited computational resources. Thus, predicting the optimal agent behaviors is undesirable (because it demands prohibitive computational resources) and undesirable (because the prediction may be wrong). Motivated by this observation, we remove the assumption of perfectly rational agents and propose incorporating the concept of bounded rationality from an information-theoretic view into the game-theoretic framework. This allows the robots to reason other agents' sub-optimal behaviors and act accordingly under their computational constraints. Specifically, bounded rationality directly models the agent's information processing ability, which is represented as the KL-divergence between nominal and optimized stochastic policies, and the solution to the bounded-optimal policy can be obtained by an efficient importance sampling approach. Using both simulated and real-world experiments in multi-robot navigation tasks, we demonstrate that the resulting framework allows the robots to reason about different levels of rational behaviors of other agents and compute a reasonable strategy under its computational constraint.
On construction of quantum codes with dual-containing quasi-cyclic codes
Venue: arXiv cs.IT 2022
Year: 2022

One of the main objectives of quantum error-correction theory is to construct quantum codes with optimal parameters and properties. In this paper, we propose a class of 2-generator quasi-cyclic codes and study their applications in the construction of quantum codes over small fields. Firstly, some sufficient conditions for these 2-generator quasi-cyclic codes to be dual-containing concerning Hermitian inner product are determined. Then, we utilize these Hermitian dual-containing quasi-cyclic codes to produce quantum codes via the famous Hermitian construction. Moreover, we present a lower bound on the minimum distance of these quasi-cyclic codes, which is helpful to construct quantum codes with larger lengths and dimensions. As the computational results, many new quantum codes that exceed the quantum Gilbert-Varshamov bound are constructed over $F_q$, where $q$ is $2,3,4,5$. In particular, 16 binary quantum codes raise the lower bound on the minimum distance in Grassl's table \cite{Grassl:codetables}. In nonbinary cases, many quantum codes are new or have better parameters than those in the literature.
VoxelCache: Accelerating Online Mapping in Robotics and 3D Reconstruction Tasks
Venue: arXiv cs.AR 2022
Year: 2022

Real-time 3D mapping is a critical component in many important applications today including robotics, AR/VR, and 3D visualization. 3D mapping involves continuously fusing depth maps obtained from depth sensors in phones, robots, and autonomous vehicles into a single 3D representative model of the scene. Many important applications, e.g., global path planning and trajectory generation in micro aerial vehicles, require the construction of large maps at high resolutions. In this work, we identify mapping, i.e., construction and updates of 3D maps to be a critical bottleneck in these applications. The memory required and access times of these maps limit the size of the environment and the resolution with which the environment can be feasibly mapped, especially in resource constrained environments such as autonomous robot platforms and portable devices. To address this challenge, we propose VoxelCache: a hardware-software technique to accelerate map data access times in 3D mapping applications. We observe that mapping applications typically access voxels in the map that are spatially co-located to each other. We leverage this temporal locality in voxel accesses to cache indices to blocks of voxels to enable quick lookup and avoid expensive access times. We evaluate VoxelCache on popularly used mapping and reconstruction applications on both GPUs and CPUs. We demonstrate an average speedup of 1.47X (up to 1.66X) and 1.79X (up to 1.91X) on CPUs and GPUs respectively.
Robust Bayesian state and parameter estimation framework for stochastic dynamical systems with combined time-varying and time-invariant parameters
Venue: arXiv cs.CE 2022
Year: 2022

We consider state and parameter estimation for a dynamical system having both time-varying and time-invariant parameters. It has been shown that the robustness of the Markov Chain Monte Carlo (MCMC) algorithm for estimating time-invariant parameters alongside nonlinear filters for state estimation provided more reliable estimates than the estimates obtained solely using nonlinear filters for combined state and parameter estimation. In a similar fashion, we adopt the extended Kalman filter (EKF) for state estimation and the estimation of the time-varying system parameters, but reserve the task of estimating time-invariant parameters to the MCMC algorithm. In a standard method, we augment the state vector to include the original states of the system and the subset of the parameters that are time-varying. Each time-varying parameter is perturbed by a white noise process, and we treat the strength of this artificial noise as an additional time-invariant parameter to be estimated by MCMC, circumventing the need for manual tuning. Conventionally, both time-varying and time-invariant parameters are appended in the state vector, and thus for the purpose of estimation, both are free to vary in time. However, allowing time-invariant system parameters to vary in time introduces artificial dynamics into the system, which we avoid by treating these time-invariant parameters as static and estimating them using MCMC. Furthermore, by estimating the time-invariant parameters by MCMC, the augmented state is smaller and the nonlinearity in the ensuing state space model will tend to be weaker than in the conventional approach. We illustrate the above-described approach for a simple dynamical system in which some model parameters are time-varying, while the remaining parameters are time-invariant.
Sequential Topic Selection Model with Latent Variable for Topic-Grounded Dialogue
Venue: arXiv cs.CL 2022
Year: 2022

Recently, topic-grounded dialogue system has attracted significant attention due to its effectiveness in predicting the next topic to yield better responses via the historical context and given topic sequence. However, almost all existing topic prediction solutions focus on only the current conversation and corresponding topic sequence to predict the next conversation topic, without exploiting other topic-guided conversations which may contain relevant topic-transitions to current conversation. To address the problem, in this paper we propose a novel approach, named Sequential Global Topic Attention (SGTA) to exploit topic transition over all conversations in a subtle way for better modeling post-to-response topic-transition and guiding the response generation to the current conversation. Specifically, we introduce a latent space modeled as a Multivariate Skew-Normal distribution with hybrid kernel functions to flexibly integrate the global-level information with sequence-level information, and predict the topic based on the distribution sampling results. We also leverage a topic-aware prior-posterior approach for secondary selection of predicted topics, which is utilized to optimize the response generation task. Extensive experiments demonstrate that our model outperforms competitive baselines on prediction and generation tasks.
Bootstrapping the Relationship Between Images and Their Clean and Noisy Labels
Venue: arXiv cs.CV 2022
Year: 2022

Many state-of-the-art noisy-label learning methods rely on learning mechanisms that estimate the samples' clean labels during training and discard their original noisy labels. However, this approach prevents the learning of the relationship between images, noisy labels and clean labels, which has been shown to be useful when dealing with instance-dependent label noise problems. Furthermore, methods that do aim to learn this relationship require cleanly annotated subsets of data, as well as distillation or multi-faceted models for training. In this paper, we propose a new training algorithm that relies on a simple model to learn the relationship between clean and noisy labels without the need for a cleanly labelled subset of data. Our algorithm follows a 3-stage process, namely: 1) self-supervised pre-training followed by an early-stopping training of the classifier to confidently predict clean labels for a subset of the training set; 2) use the clean set from stage (1) to bootstrap the relationship between images, noisy labels and clean labels, which we exploit for effective relabelling of the remaining training set using semi-supervised learning; and 3) supervised training of the classifier with all relabelled samples from stage (2). By learning this relationship, we achieve state-of-the-art performance in asymmetric and instance-dependent label noise problems.
Joint Multilingual Knowledge Graph Completion and Alignment
Venue: arXiv cs.CL 2022
Year: 2022

Knowledge graph (KG) alignment and completion are usually treated as two independent tasks. While recent work has leveraged entity and relation alignments from multiple KGs, such as alignments between multilingual KGs with common entities and relations, a deeper understanding of the ways in which multilingual KG completion (MKGC) can aid the creation of multilingual KG alignments (MKGA) is still limited. Motivated by the observation that structural inconsistencies -- the main challenge for MKGA models -- can be mitigated through KG completion methods, we propose a novel model for jointly completing and aligning knowledge graphs. The proposed model combines two components that jointly accomplish KG completion and alignment. These two components employ relation-aware graph neural networks that we propose to encode multi-hop neighborhood structures into entity and relation representations. Moreover, we also propose (i) a structural inconsistency reduction mechanism to incorporate information from the completion into the alignment component, and (ii) an alignment seed enlargement and triple transferring mechanism to enlarge alignment seeds and transfer triples during KGs alignment. Extensive experiments on a public multilingual benchmark show that our proposed model outperforms existing competitive baselines, obtaining new state-of-the-art results on both MKGC and MKGA tasks. We publicly release the implementation of our model at https://github.com/vinhsuhi/JMAC