OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Path Planning in Narrow Passages for Robots with Ellipsoidal Components
Venue: arXiv cs.RO 2022
Year: 2022

Path planning has long been one of the major research areas in robotics, with PRM and RRT being two of the most effective classes of planners. Though generally very efficient, these sampling-based planners can become computationally expensive in the important case of "narrow passages". This paper develops a path planning paradigm specifically formulated for narrow passage problems. The core is based on planning for rigid-body robots encapsulated by unions of ellipsoids. Each environmental feature is represented geometrically using a strictly convex body with a $\mathcal{C}^1$ boundary (e.g., superquadric). The main benefit of doing this is that configuration-space obstacles can be parameterized explicitly in closed form, thereby allowing prior knowledge to be used to avoid sampling infeasible configurations. Then, by characterizing a tight volume bound for multiple ellipsoids, robot transitions involving rotations are guaranteed to be collision-free without needing to perform traditional collision detection. Furthermore, by combining with a stochastic sampling strategy, the proposed planning framework can be extended to solving higher dimensional problems in which the robot has a moving base and articulated appendages. Benchmark results show that the proposed framework often outperforms the sampling-based planners in terms of computational time and success rate in finding a path through narrow corridors for both single-body robots and those with higher dimensional configuration spaces. Physical experiments using the proposed framework are further demonstrated on a humanoid robot that walks in several cluttered environments with narrow passages.
Pay attention to your loss: understanding misconceptions about 1-Lipschitz neural networks
Venue: arXiv cs.LG 2022
Year: 2022

Lipschitz constrained networks have gathered considerable attention in the deep learning community, with usages ranging from Wasserstein distance estimation to the training of certifiably robust classifiers. However they remain commonly considered as less accurate, and their properties in learning are still not fully understood. In this paper we clarify the matter: when it comes to classification 1-Lipschitz neural networks enjoy several advantages over their unconstrained counterpart. First, we show that these networks are as accurate as classical ones, and can fit arbitrarily difficult boundaries. Then, relying on a robustness metric that reflects operational needs we characterize the most robust classifier: the WGAN discriminator. Next, we show that 1-Lipschitz neural networks generalize well under milder assumptions. Finally, we show that hyper-parameters of the loss are crucial for controlling the accuracy-robustness trade-off. We conclude that they exhibit appealing properties to pave the way toward provably accurate, and provably robust neural networks.
Edgeless-GNN: Unsupervised Representation Learning for Edgeless Nodes
Venue: arXiv cs.SI 2022
Year: 2022

We study the problem of embedding edgeless nodes such as users who newly enter the underlying network, while using graph neural networks (GNNs) widely studied for effective representation learning of graphs. Our study is motivated by the fact that GNNs cannot be straightforwardly adopted for our problem since message passing to such edgeless nodes having no connections is impossible. To tackle this challenge, we propose Edgeless-GNN, a novel inductive framework that enables GNNs to generate node embeddings even for edgeless nodes through unsupervised learning. Specifically, we start by constructing a proxy graph based on the similarity of node attributes as the GNN's computation graph defined by the underlying network. The known network structure is used to train model parameters, whereas a topology-aware loss function is established in such a way that our model judiciously learns the network structure by encoding positive, negative, and second-order relations between nodes. For the edgeless nodes, we inductively infer embeddings by expanding the computation graph. By evaluating the performance of various downstream machine learning tasks, we empirically demonstrate that Edgeless-GNN exhibits (a) superiority over state-of-the-art inductive network embedding methods for edgeless nodes, (b) effectiveness of our topology-aware loss function, (c) robustness to incomplete node attributes, and (d) a linear scaling with the graph size.
Ranking Sets of Objects: The Complexity of Avoiding Impossibility Results
Venue: arXiv cs.GT 2022
Year: 2022

The problem of lifting a preference order on a set of objects to a preference order on a family of subsets of this set is a fundamental problem with a wide variety of applications in AI. The process is often guided by axioms postulating properties the lifted order should have. Well-known impossibility results by Kannai and Peleg and by Barberà and Pattanaik tell us that some desirable axioms - namely dominance and (strict) independence - are not jointly satisfiable for any linear order on the objects if all non-empty sets of objects are to be ordered. On the other hand, if not all non-empty sets of objects are to be ordered, the axioms are jointly satisfiable for all linear orders on the objects for some families of sets. Such families are very important for applications as they allow for the use of lifted orders, for example, in combinatorial voting. In this paper, we determine the computational complexity of recognizing such families. We show that it is $Π_2^p$-complete to decide for a given family of subsets whether dominance and independence or dominance and strict independence are jointly satisfiable for all linear orders on the objects if the lifted order needs to be total. Furthermore, we show that the problem remains coNP-complete if the lifted order can be incomplete. Additionally, we show that the complexity of these problem can increase exponentially if the family of sets is not given explicitly but via a succinct domain restriction. Finally, we show that it is NP-complete to decide for family of subsets whether dominance and independence or dominance and strict independence are jointly satisfiable for at least one linear orders on the objects.
Autonomous Drone Delivery to Your Door and Yard
Venue: arXiv cs.RO 2022
Year: 2022

In this work, we present a system that enables delivery drones to autonomously navigate and deliver packages at various locations around a house according to the desire of the recipient and without the need for any external markers as currently used. This development is motivated by recent advancements in deep learning that can potentially supplant the specialized markers presently used by delivery drones for identifying sites at which to deliver packages. The proposed system is more natural in that it takes instruction on where to deliver the package as input, similar to the instructions provided to human couriers. First, we propose a semantic image segmentation-based descending location estimator that enables the drone to find a safe spot around the house at which it can descend from higher altitudes. Following this, we propose a strategy for visually routing the drone from the descent location to a specific site at which it is to deliver the package, such as the front door. We extensively evaluate this approach in a simulated environment and demonstrate that with our system, a delivery drone can deliver a package to the front door and also to other specified locations around a house. Relative to a frontier exploration-based strategy, drones using the proposed system found and reached the front doors of the 20 test houses 161% faster.
Multivariate Deep Evidential Regression
Venue: arXiv cs.LG 2022
Year: 2022

There is significant need for principled uncertainty reasoning in machine learning systems as they are increasingly deployed in safety-critical domains. A new approach with uncertainty-aware neural networks (NNs), based on learning evidential distributions for aleatoric and epistemic uncertainties, shows promise over traditional deterministic methods and typical Bayesian NNs, yet several important gaps in the theory and implementation of these networks remain. We discuss three issues with a proposed solution to extract aleatoric and epistemic uncertainties from regression-based neural networks. The approach derives a technique by placing evidential priors over the original Gaussian likelihood function and training the NN to infer the hyperparameters of the evidential distribution. Doing so allows for the simultaneous extraction of both uncertainties without sampling or utilization of out-of-distribution data for univariate regression tasks. We describe the outstanding issues in detail, provide a possible solution, and generalize the deep evidential regression technique for multivariate cases.
A Novel Generalised Meta-Heuristic Framework for Dynamic Capacitated Arc Routing Problems
Venue: arXiv cs.NE 2022
Year: 2022

The capacitated arc routing problem (CARP) is a challenging combinatorial optimisation problem abstracted from many real-world applications, such as waste collection, road gritting and mail delivery. However, few studies considered dynamic changes during the vehicles' service, which can cause the original schedule infeasible or obsolete. The few existing studies are limited by the dynamic scenarios considered, and by overly complicated algorithms that are unable to benefit from the wealth of contributions provided by the existing CARP literature. In this paper, we first provide a mathematical formulation of dynamic CARP (DCARP) and design a simulation system that is able to consider dynamic events while a routing solution is already partially executed. We then propose a novel framework which can benefit from existing static CARP optimisation algorithms so that they could be used to handle DCARP instances. The framework is very flexible. In response to a dynamic event, it can use either a simple restart strategy or a sequence transfer strategy that benefits from past optimisation experience. Empirical studies have been conducted on a wide range of DCARP instances to evaluate our proposed framework. The results show that the proposed framework significantly improves over state-of-the-art dynamic optimisation algorithms.
Federated Generalized Face Presentation Attack Detection
Venue: arXiv cs.CV 2022
Year: 2022

Face presentation attack detection plays a critical role in the modern face recognition pipeline. A face presentation attack detection model with good generalization can be obtained when it is trained with face images from different input distributions and different types of spoof attacks. In reality, training data (both real face images and spoof images) are not directly shared between data owners due to legal and privacy issues. In this paper, with the motivation of circumventing this challenge, we propose a Federated Face Presentation Attack Detection (FedPAD) framework that simultaneously takes advantage of rich fPAD information available at different data owners while preserving data privacy. In the proposed framework, each data center locally trains its own fPAD model. A server learns a global fPAD model by iteratively aggregating model updates from all data centers without accessing private data in each of them. To equip the aggregated fPAD model in the server with better generalization ability to unseen attacks from users, following the basic idea of FedPAD, we further propose a Federated Generalized Face Presentation Attack Detection (FedGPAD) framework. A federated domain disentanglement strategy is introduced in FedGPAD, which treats each data center as one domain and decomposes the fPAD model into domain-invariant and domain-specific parts in each data center. Two parts disentangle the domain-invariant and domain-specific features from images in each local data center, respectively. A server learns a global fPAD model by only aggregating domain-invariant parts of the fPAD models from data centers and thus a more generalized fPAD model can be aggregated in server. We introduce the experimental setting to evaluate the proposed FedPAD and FedGPAD frameworks and carry out extensive experiments to provide various insights about federated learning for fPAD.
Small World Model for scaling up prediction result based on SEIR model
Venue: arXiv cs.CY 2022
Year: 2022

Data-driven epidemic simulation helps better policymaking. Compared with macro-scale simulations driven by statistical data, individual-level GPS data can afford finer and spatialized results. However, the big GPS data, usually collected from mobile phone users, cannot cover all populations. Therefore, this study proposes a Small World Model, to map the results from the "small world" (simulation with partially sampled data) to the real world. Based on the basic principles of disease transmission, this study derives two parameters: a time scaling factor to map the simulated period to the real period, and an amount scaling factor to map the simulated infected number to the real infected number. It is believed that this model could convert the simulation of the "small world" into the state of the real world, and analyze the effectiveness of different mobility restriction policies.
Domain Adaptation and Multi-Domain Adaptation for Neural Machine Translation: A Survey
Venue: arXiv cs.CL 2022
Year: 2022

The development of deep learning techniques has allowed Neural Machine Translation (NMT) models to become extremely powerful, given sufficient training data and training time. However, systems struggle when translating text from a new domain with a distinct style or vocabulary. Fine-tuning on in-domain data allows good domain adaptation, but requires sufficient relevant bilingual data. Even if this is available, simple fine-tuning can cause overfitting to new data and `catastrophic forgetting' of previously learned behaviour. We concentrate on robust approaches to domain adaptation for NMT, particularly where a system may need to translate across multiple domains. We divide techniques into those revolving around data selection or generation, model architecture, parameter adaptation procedure, and inference procedure. We finally highlight the benefits of domain adaptation and multi-domain adaptation techniques to other lines of NMT research.
Two Birds with One Stone: Unified Model Learning for Both Recall and Ranking in News Recommendation
Venue: arXiv cs.IR 2022
Year: 2022

Recall and ranking are two critical steps in personalized news recommendation. Most existing news recommender systems conduct personalized news recall and ranking separately with different models. However, maintaining multiple models leads to high computational cost and poses great challenge to meeting the online latency requirement of news recommender systems. In order to handle this problem, in this paper we propose UniRec, a unified method for recall and ranking in news recommendation. In our method, we first infer user embedding for ranking from the historical news click behaviors of a user using a user encoder model. Then we derive the user embedding for recall from the obtained user embedding for ranking by using it as the attention query to select a set of basis user embeddings which encode different general user interests and synthesize them into a user embedding for recall. The extensive experiments on benchmark dataset demonstrate that our method can improve both efficiency and effectiveness for recall and ranking in news recommendation.
Sequence tagging for biomedical extractive question answering
Venue: arXiv cs.CL 2022
Year: 2022

Current studies in extractive question answering (EQA) have modeled the single-span extraction setting, where a single answer span is a label to predict for a given question-passage pair. This setting is natural for general domain EQA as the majority of the questions in the general domain can be answered with a single span. Following general domain EQA models, current biomedical EQA (BioEQA) models utilize the single-span extraction setting with post-processing steps. In this article, we investigate the question distribution across the general and biomedical domains and discover biomedical questions are more likely to require list-type answers (multiple answers) than factoid-type answers (single answer). This necessitates the models capable of producing multiple answers for a question. Based on this preliminary study, we propose a sequence tagging approach for BioEQA, which is a multi-span extraction setting. Our approach directly tackles questions with a variable number of phrases as their answer and can learn to decide the number of answers for a question from training data. Our experimental results on the BioASQ 7b and 8b list-type questions outperformed the best-performing existing models without requiring post-processing steps. Source codes and resources are freely available for download at https://github.com/dmis-lab/SeqTagQA
An $L^2$ Analysis of Reinforcement Learning in High Dimensions with Kernel and Neural Network Approximation
Venue: arXiv cs.LG 2022
Year: 2022

Reinforcement learning (RL) algorithms based on high-dimensional function approximation have achieved tremendous empirical success in large-scale problems with an enormous number of states. However, most analysis of such algorithms gives rise to error bounds that involve either the number of states or the number of features. This paper considers the situation where the function approximation is made either using the kernel method or the two-layer neural network model, in the context of a fitted Q-iteration algorithm with explicit regularization. We establish an $\tilde{O}(H^3|\mathcal {A}|^{\frac14}n^{-\frac14})$ bound for the optimal policy with $Hn$ samples, where $H$ is the length of each episode and $|\mathcal {A}|$ is the size of action space. Our analysis hinges on analyzing the $L^2$ error of the approximated Q-function using $n$ data points. Even though this result still requires a finite-sized action space, the error bound is independent of the dimensionality of the state space.
A Further Study of Quadratic APN Permutations in Dimension Nine
Venue: arXiv cs.IT 2022
Year: 2022

Recently, Beierle and Leander found two new sporadic quadratic APN permutations in dimension 9. Up to EA-equivalence, we present a single trivariate representation of those two permutations as $C_u \colon (\mathbb{F}_{2^m})^3 \rightarrow (\mathbb{F}_{2^m})^3, (x,y,z) \mapsto (x^3+uy^2z, y^3+uxz^2,z^3+ux^2y)$, where $m=3$ and $u \in \mathbb{F}_{2^3}\setminus\{0,1\}$ such that the two permutations correspond to different choices of $u$. We then analyze the differential uniformity and the nonlinearity of $C_u$ in a more general case. In particular, for $m \geq 3$ being a multiple of 3 and $u \in \mathbb{F}_{2^m}$ not being a 7-th power, we show that the differential uniformity of $C_u$ is bounded above by 8, and that the linearity of $C_u$ is bounded above by $8^{1+\lfloor \frac{m}{2} \rfloor}$. Based on numerical experiments, we conjecture that $C_u$ is not APN if $m$ is greater than $3$. We also analyze the CCZ-equivalence classes of the quadratic APN permutations in dimension 9 known so far and derive a lower bound on the number of their EA-equivalence classes. We further show that the two sporadic APN permutations share an interesting similarity with Gold APN permutations in odd dimension divisible by 3, namely that a permutation EA-inequivalent to those sporadic APN permutations and their inverses can be obtained by just applying EA transformations and inversion to the original permutations.
Holmes: An Efficient and Lightweight Semantic Based Anomalous Email Detector
Venue: arXiv cs.CR 2022
Year: 2022

Email threat is a serious issue for enterprise security. The threat can be in various malicious forms, such as phishing, fraud, blackmail and malvertisement. The traditional anti-spam gateway often maintains a greylist to filter out unexpected emails based on suspicious vocabularies present in the email's subject and contents. However, this type of signature-based approach cannot effectively discover novel and unknown suspicious emails that utilize various evolving malicious payloads. To address the problem, in this paper, we present Holmes, an efficient and lightweight semantic based engine for anomalous email detection. Holmes can convert each email event log into a sentence through word embedding and then identify abnormalities that deviate from a historical baseline based on those translated sentences. We have evaluated the performance of Holmes in a real-world enterprise environment, where around 5,000 emails are sent/received each day. In our experiments, Holmes shows a high capability to detect email threats, especially those that cannot be handled by the enterprise anti-spam gateway. It is also demonstrated through our experiment that Holmes can discover more concealed malicious emails that are immune from several commercial detection tools.
Membership Inference Attacks on Knowledge Graphs
Venue: arXiv cs.AI 2022
Year: 2022

Membership inference attacks (MIAs) infer whether a specific data record is used for target model training. MIAs have provoked many discussions in the information security community since they give rise to severe data privacy issues, especially for private and sensitive datasets. Knowledge Graphs (KGs), which describe domain-specific subjects and relationships among them, are valuable and sensitive, such as medical KGs constructed from electronic health records. However, the privacy threat to knowledge graphs is critical but rarely explored. In this paper, we conduct the first empirical evaluation of privacy threats to knowledge graphs triggered by knowledge graph embedding methods (KGEs). We propose three types of membership inference attacks: transfer attacks (TAs), prediction loss-based attacks (PLAs), and prediction correctness-based attacks (PCAs), according to attack difficulty levels. In the experiments, we conduct three inference attacks against four standard KGE methods over three benchmark datasets. In addition, we also propose the attacks against medical KG and financial KG. The results demonstrate that the proposed attack methods can easily explore the privacy leakage of knowledge graphs.
Surface Form Competition: Why the Highest Probability Answer Isn't Always Right
Venue: arXiv cs.CL 2022
Year: 2022

Large language models have shown promising results in zero-shot settings (Brown et al.,2020; Radford et al., 2019). For example, they can perform multiple choice tasks simply by conditioning on a question and selecting the answer with the highest probability. However, ranking by string probability can be problematic due to surface form competition-wherein different surface forms compete for probability mass, even if they represent the same underlying concept, e.g. "computer" and "PC." Since probability mass is finite, this lowers the probability of the correct answer, due to competition from other strings that are valid answers (but not one of the multiple choice options). We introduce Domain Conditional Pointwise Mutual Information, an alternative scoring function that directly compensates for surface form competition by simply reweighing each option according to a term that is proportional to its a priori likelihood within the context of the specific zero-shot task. It achieves consistent gains in zero-shot performance over both calibrated (Zhao et al., 2021) and uncalibrated scoring functions on all GPT-2 and GPT-3 models over a variety of multiple choice datasets.