OpenRaiser/Intern-Atlas huggingface dataset:
NETR-Tree: An Eifficient Framework for Social-Based Time-Aware Spatial Keyword Query
Venue: arXiv cs.SI 2022
Year: 2022

The development of global positioning system stimulates the popularity of location-based social network (LBSN) services. With a large volume of data containing locations, texts, check-in information, and social relationships, spatial keyword queries in LBSNs have become increasingly complex. In this paper, we identify and solve the Social-based Time-aware Spatial Keyword Query (STSKQ) that returns the top-k objects by considering geo-spatial score, keywords similarity, visiting time score, and social relationship effect. To tackle STSKQ, we propose a two-layer hybrid index structure called Network Embedding Time-aware R-tree (NETR-Tree). In the user layer, we exploit the network embedding strategy to measure the relationship effect in users' relationship network. In the location layer, we build a Time-aware R-tree (TR-tree) considered spatial objects' spatiotemporal check-in information, and present a corresponding query processing algorithm. Finally, extensive experiments on two different real-life LBSNs demonstrate the effectiveness and efficiency of our methods, compared with existing state-of-the-art methods.
A Survey on Bias and Fairness in Machine Learning
Venue: arXiv cs.LG 2022
Year: 2022

With the widespread use of AI systems and applications in our everyday lives, it is important to take fairness issues into consideration while designing and engineering these types of systems. Such systems can be used in many sensitive environments to make important and life-changing decisions; thus, it is crucial to ensure that the decisions do not reflect discriminatory behavior toward certain groups or populations. We have recently seen work in machine learning, natural language processing, and deep learning that addresses such challenges in different subdomains. With the commercialization of these systems, researchers are becoming aware of the biases that these applications can contain and have attempted to address them. In this survey we investigated different real-world applications that have shown biases in various ways, and we listed different sources of biases that can affect AI applications. We then created a taxonomy for fairness definitions that machine learning researchers have defined in order to avoid the existing bias in AI systems. In addition to that, we examined different domains and subdomains in AI showing what researchers have observed with regard to unfair outcomes in the state-of-the-art methods and how they have tried to address them. There are still many future directions and solutions that can be taken to mitigate the problem of bias in AI systems. We are hoping that this survey will motivate researchers to tackle these issues in the near future by observing existing work in their respective fields.
Defeating Misclassification Attacks Against Transfer Learning
Venue: arXiv cs.LG 2022
Year: 2022

Transfer learning is prevalent as a technique to efficiently generate new models (Student models) based on the knowledge transferred from a pre-trained model (Teacher model). However, Teacher models are often publicly available for sharing and reuse, which inevitably introduces vulnerability to trigger severe attacks against transfer learning systems. In this paper, we take a first step towards mitigating one of the most advanced misclassification attacks in transfer learning. We design a distilled differentiator via activation-based network pruning to enervate the attack transferability while retaining accuracy. We adopt an ensemble structure from variant differentiators to improve the defence robustness. To avoid the bloated ensemble size during inference, we propose a two-phase defence, in which inference from the Student model is firstly performed to narrow down the candidate differentiators to be assembled, and later only a small, fixed number of them can be chosen to validate clean or reject adversarial inputs effectively. Our comprehensive evaluations on both large and small image recognition tasks confirm that the Student models with our defence of only 5 differentiators are immune to over 90% of the adversarial inputs with an accuracy loss of less than 10%. Our comparison also demonstrates that our design outperforms prior problematic defences.
Global Entity Disambiguation with BERT
Venue: arXiv cs.CL 2022
Year: 2022

We propose a global entity disambiguation (ED) model based on BERT. To capture global contextual information for ED, our model treats not only words but also entities as input tokens, and solves the task by sequentially resolving mentions to their referent entities and using resolved entities as inputs at each step. We train the model using a large entity-annotated corpus obtained from Wikipedia. We achieve new state-of-the-art results on five standard ED datasets: AIDA-CoNLL, MSNBC, AQUAINT, ACE2004, and WNED-WIKI. The source code and model checkpoint are available at https://github.com/studio-ousia/luke.
Duality Regularization for Unsupervised Bilingual Lexicon Induction
Venue: arXiv cs.CL 2022
Year: 2022

Unsupervised bilingual lexicon induction naturally exhibits duality, which results from symmetry in back-translation. For example, EN-IT and IT-EN induction can be mutually primal and dual problems. Current state-of-the-art methods, however, consider the two tasks independently. In this paper, we propose to train primal and dual models jointly, using regularizers to encourage consistency in back translation cycles. Experiments across 6 language pairs show that the proposed method significantly outperforms competitive baselines, obtaining the best-published results on a standard benchmark.
On the Acceleration of Deep Learning Model Parallelism with Staleness
Venue: arXiv cs.LG 2022
Year: 2022

Training the deep convolutional neural network for computer vision problems is slow and inefficient, especially when it is large and distributed across multiple devices. The inefficiency is caused by the backpropagation algorithm's forward locking, backward locking, and update locking problems. Existing solutions for acceleration either can only handle one locking problem or lead to severe accuracy loss or memory inefficiency. Moreover, none of them consider the straggler problem among devices. In this paper, we propose Layer-wise Staleness and a novel efficient training algorithm, Diversely Stale Parameters (DSP), to address these challenges. We also analyze the convergence of DSP with two popular gradient-based methods and prove that both of them are guaranteed to converge to critical points for non-convex problems. Finally, extensive experimental results on training deep learning models demonstrate that our proposed DSP algorithm can achieve significant training speedup with stronger robustness than compared methods.
AutoML for Contextual Bandits
Venue: arXiv cs.LG 2022
Year: 2022

Contextual Bandits is one of the widely popular techniques used in applications such as personalization, recommendation systems, mobile health, causal marketing etc . As a dynamic approach, it can be more efficient than standard A/B testing in minimizing regret. We propose an end to end automated meta-learning pipeline to approximate the optimal Q function for contextual bandits problems. We see that our model is able to perform much better than random exploration, being more regret efficient and able to converge with a limited number of samples, while remaining very general and easy to use due to the meta-learning approach. We used a linearly annealed e-greedy exploration policy to define the exploration vs exploitation schedule. We tested the system on a synthetic environment to characterize it fully and we evaluated it on some open source datasets to benchmark against prior work. We see that our model outperforms or performs comparatively to other models while requiring no tuning nor feature engineering.
Does Order Matter? An Empirical Study on Generating Multiple Keyphrases as a Sequence
Venue: arXiv cs.CL 2022
Year: 2022

Recently, concatenating multiple keyphrases as a target sequence has been proposed as a new learning paradigm for keyphrase generation. Existing studies concatenate target keyphrases in different orders but no study has examined the effects of ordering on models' behavior. In this paper, we propose several orderings for concatenation and inspect the important factors for training a successful keyphrase generation model. By running comprehensive comparisons, we observe one preferable ordering and summarize a number of empirical findings and challenges, which can shed light on future research on this line of work.
Noisy Beeping Networks
Venue: arXiv cs.DS 2022
Year: 2022

We introduce noisy beeping networks, where nodes have limited communication capabilities, namely, they can only emit energy or sense the channel for energy. Furthermore, imperfections may cause devices to malfunction with some fixed probability when sensing the channel, which amounts to deducing a noisy received transmission. Such noisy networks have implications for ultra-lightweight sensor networks and biological systems. We show how to compute tasks in a noise-resilient manner over noisy beeping networks of arbitrary structure. In particular, we transform any algorithm that assumes a noiseless beeping network (of size $n$) into a noise-resilient version while incurring a multiplicative overhead of only $O(\log n)$ in its round complexity, with high probability. We show that our coding is optimal for some tasks, such as node-coloring of a clique. We further show how to simulate a large family of algorithms designed for distributed networks in the CONGEST($B$) model over a noisy beeping network. The simulation succeeds with high probability and incurs an asymptotic multiplicative overhead of $O(B\cdot Δ\cdot \min(n,Δ^2))$ in the round complexity, where $Δ$ is the maximal degree of the network. The overhead is tight for certain graphs, e.g., a clique. Further, this simulation implies a constant overhead coding for constant-degree networks.
Construction of sequences with high nonlinear complexity from a generalization of the Hermitian function field
Venue: arXiv cs.IT 2022
Year: 2022

For $r \geq 1$ an odd integer, we provide a sequence from the function field $\mathcal{F}_{q, r}$ of the maximal curve over $\mathbb{F}_{q^{2r}}$ defined by the affine equation $y^q+y=x^{q^r + 1}$. This sequence has high nonlinear complexity, and this fact comes from the existence of a rational function on $\mathcal{F}_{q, r}$ with pole divisor of small degree, and support in certain $q$ rational places.
BPMR: Bayesian Probabilistic Multivariate Ranking
Venue: arXiv cs.IR 2022
Year: 2022

Multi-aspect user preferences are attracting wider attention in recommender systems, as they enable more detailed understanding of users' evaluations of items. Previous studies show that incorporating multi-aspect preferences can greatly improve the performance and explainability of recommendation. However, as recommendation is essentially a ranking problem, there is no principled solution for ranking multiple aspects collectively to enhance the recommendation. In this work, we derive a multi-aspect ranking criterion. To maintain the dependency among different aspects, we propose to use a vectorized representation of multi-aspect ratings and develop a probabilistic multivariate tensor factorization framework (PMTF). The framework naturally leads to a probabilistic multi-aspect ranking criterion, which generalizes the single-aspect ranking to a multivariate fashion. Experiment results on a large multi-aspect review rating dataset confirmed the effectiveness of our solution.
Density Encoding Enables Resource-Efficient Randomly Connected Neural Networks
Venue: arXiv cs.LG 2022
Year: 2022

The deployment of machine learning algorithms on resource-constrained edge devices is an important challenge from both theoretical and applied points of view. In this article, we focus on resource-efficient randomly connected neural networks known as Random Vector Functional Link (RVFL) networks since their simple design and extremely fast training time make them very attractive for solving many applied classification tasks. We propose to represent input features via the density-based encoding known in the area of stochastic computing and use the operations of binding and bundling from the area of hyperdimensional computing for obtaining the activations of the hidden neurons. Using a collection of 121 real-world datasets from the UCI Machine Learning Repository, we empirically show that the proposed approach demonstrates higher average accuracy than the conventional RVFL. We also demonstrate that it is possible to represent the readout matrix using only integers in a limited range with minimal loss in the accuracy. In this case, the proposed approach operates only on small n-bits integers, which results in a computationally efficient architecture. Finally, through hardware Field-Programmable Gate Array (FPGA) implementations, we show that such an approach consumes approximately eleven times less energy than that of the conventional RVFL.
Universal Graph Transformer Self-Attention Networks
Venue: arXiv cs.LG 2022
Year: 2022

We introduce a transformer-based GNN model, named UGformer, to learn graph representations. In particular, we present two UGformer variants, wherein the first variant (publicized in September 2019) is to leverage the transformer on a set of sampled neighbors for each input node, while the second (publicized in May 2021) is to leverage the transformer on all input nodes. Experimental results demonstrate that the first UGformer variant achieves state-of-the-art accuracies on benchmark datasets for graph classification in both inductive setting and unsupervised transductive setting; and the second UGformer variant obtains state-of-the-art accuracies for inductive text classification. The code is available at: \url{https://github.com/daiquocnguyen/Graph-Transformer}.
Mining Uncertain Event Data in Process Mining
Venue: arXiv cs.AI 2022
Year: 2022

Nowadays, more and more process data are automatically recorded by information systems, and made available in the form of event logs. Process mining techniques enable process-centric analysis of data, including automatically discovering process models and checking if event data conform to a certain model. In this paper we analyze the previously unexplored setting of uncertain event logs: logs where quantified uncertainty is recorded together with the corresponding data. We define a taxonomy of uncertain event logs and models, and we examine the challenges that uncertainty poses on process discovery and conformance checking. Finally, we show how upper and lower bounds for conformance can be obtained aligning an uncertain trace onto a regular process model.
TriMap: Large-scale Dimensionality Reduction Using Triplets
Venue: arXiv cs.LG 2022
Year: 2022

We introduce "TriMap"; a dimensionality reduction technique based on triplet constraints, which preserves the global structure of the data better than the other commonly used methods such as t-SNE, LargeVis, and UMAP. To quantify the global accuracy of the embedding, we introduce a score that roughly reflects the relative placement of the clusters rather than the individual points. We empirically show the excellent performance of TriMap on a large variety of datasets in terms of the quality of the embedding as well as the runtime. On our performance benchmarks, TriMap easily scales to millions of points without depleting the memory and clearly outperforms t-SNE, LargeVis, and UMAP in terms of runtime.
Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
Venue: arXiv cs.DS 2022
Year: 2022

We study the complexity of graph modification problems with respect to homomorphism-based colouring properties of edge-coloured graphs. A homomorphism from edge-coloured graph $G$ to edge-coloured graph $H$ is a vertex-mapping from $G$ to $H$ that preserves adjacencies and edge-colours. We consider the property of having a homomorphism to a fixed edge-coloured graph $H$. The question we are interested in is: given an edge-coloured graph $G$, can we perform $k$ graph operations so that the resulting graph admits a homomorphism to $H$? The operations we consider are vertex-deletion, edge-deletion and switching (an operation that permutes the colours of the edges incident to a given vertex). Switching plays an important role in the theory of signed graphs, that are 2-edge-coloured graphs whose colours are the signs $+$ and $-$. We denote the corresponding problems (parameterized by $k$) by VD-$H$-COLOURING, ED-$H$-COLOURING and SW-$H$-COLOURING. These problems generalise $H$-COLOURING (to decide if an input graph admits a homomorphism to a fixed target $H$). Our main focus is when $H$ is an edge-coloured graph with at most two vertices, a case that is already interesting as it includes problems such as VERTEX COVER, ODD CYCLE RANSVERSAL and EDGE BIPARTIZATION. For such a graph $H$, we give a P/NP-c complexity dichotomy for VD-$H$-COLOURING, ED-$H$-COLOURING and SW-$H$-COLOURING. We then address their parameterized complexity. We show that VD-$H$-COLOURING and ED-$H$-COLOURING for all such $H$ are FPT. In contrast, already for some $H$ of order 3, unless P=NP, none of the three problems is in XP, since 3-COLOURING is NP-c. We show that SW-$H$-COLOURING is different: there are three 2-edge-coloured graphs $H$ of order 2 for which SW-$H$-COLOURING is W-hard, and assuming the ETH, admits no algorithm in time $f(k)n^{o(k)}$. For the other cases, SW-$H$-COLOURING is FPT.
REDS: Rule Extraction for Discovering Scenarios
Venue: arXiv cs.LG 2022
Year: 2022

Scenario discovery is the process of finding areas of interest, known as scenarios, in data spaces resulting from simulations. For instance, one might search for conditions, i.e., inputs of the simulation model, where the system is unstable. Subgroup discovery methods are commonly used for scenario discovery. They find scenarios in the form of hyperboxes, which are easy to comprehend. Given a computational budget, results tend to get worse as the number of inputs of the simulation model and the cost of simulations increase. We propose a new procedure for scenario discovery from few simulations, dubbed REDS. A key ingredient is using an intermediate machine learning model to label data for subsequent use by conventional subgroup discovery methods. We provide statistical arguments why this is an improvement. In our experiments, REDS reduces the number of simulations required by 50--75\% on average, depending on the quality measure. It is also useful as a semi-supervised subgroup discovery method and for discovering better scenarios from third-party data, when a simulation model is not available.
Distributed Learning of Deep Neural Networks using Independent Subnet Training
Venue: arXiv cs.LG 2022
Year: 2022

Distributed machine learning (ML) can bring more computational resources to bear than single-machine learning, thus enabling reductions in training time. Distributed learning partitions models and data over many machines, allowing model and dataset sizes beyond the available compute power and memory of a single machine. In practice though, distributed ML is challenging when distribution is mandatory, rather than chosen by the practitioner. In such scenarios, data could unavoidably be separated among workers due to limited memory capacity per worker or even because of data privacy issues. There, existing distributed methods will utterly fail due to dominant transfer costs across workers, or do not even apply. We propose a new approach to distributed fully connected neural network learning, called independent subnet training (IST), to handle these cases. In IST, the original network is decomposed into a set of narrow subnetworks with the same depth. These subnetworks are then trained locally before parameters are exchanged to produce new subnets and the training cycle repeats. Such a naturally "model parallel" approach limits memory usage by storing only a portion of network parameters on each device. Additionally, no requirements exist for sharing data between workers (i.e., subnet training is local and independent) and communication volume and frequency are reduced by decomposing the original network into independent subnets. These properties of IST can cope with issues due to distributed data, slow interconnects, or limited device memory, making IST a suitable approach for cases of mandatory distribution. We show experimentally that IST results in training times that are much lower than common distributed learning approaches.
Executing Instructions in Situated Collaborative Interactions
Venue: arXiv cs.CL 2022
Year: 2022

We study a collaborative scenario where a user not only instructs a system to complete tasks, but also acts alongside it. This allows the user to adapt to the system abilities by changing their language or deciding to simply accomplish some tasks themselves, and requires the system to effectively recover from errors as the user strategically assigns it new goals. We build a game environment to study this scenario, and learn to map user instructions to system actions. We introduce a learning approach focused on recovery from cascading errors between instructions, and modeling methods to explicitly reason about instructions with multiple goals. We evaluate with a new evaluation protocol using recorded interactions and online games with human users, and observe how users adapt to the system abilities.
On Robustness of Neural Ordinary Differential Equations
Venue: arXiv cs.LG 2022
Year: 2022

Neural ordinary differential equations (ODEs) have been attracting increasing attention in various research domains recently. There have been some works studying optimization issues and approximation capabilities of neural ODEs, but their robustness is still yet unclear. In this work, we fill this important gap by exploring robustness properties of neural ODEs both empirically and theoretically. We first present an empirical study on the robustness of the neural ODE-based networks (ODENets) by exposing them to inputs with various types of perturbations and subsequently investigating the changes of the corresponding outputs. In contrast to conventional convolutional neural networks (CNNs), we find that the ODENets are more robust against both random Gaussian perturbations and adversarial attack examples. We then provide an insightful understanding of this phenomenon by exploiting a certain desirable property of the flow of a continuous-time ODE, namely that integral curves are non-intersecting. Our work suggests that, due to their intrinsic robustness, it is promising to use neural ODEs as a basic block for building robust deep network models. To further enhance the robustness of vanilla neural ODEs, we propose the time-invariant steady neural ODE (TisODE), which regularizes the flow on perturbed data via the time-invariant property and the imposition of a steady-state constraint. We show that the TisODE method outperforms vanilla neural ODEs and also can work in conjunction with other state-of-the-art architectural methods to build more robust deep networks.