OpenRaiser/Intern-Atlas huggingface dataset:
Deep Spatially and Temporally Aware Similarity Computation for Road Network Constrained Trajectories
Venue: arXiv cs.LG 2022
Year: 2022

Trajectory similarity computation has drawn massive attention, as it is core functionality in a wide range of applications such as ride-sharing, traffic analysis, and social recommendation. Motivated by the recent success of deep learning technologies, researchers start devoting efforts to learning-based similarity analyses to overcome the limitations (i.e., high cost and poor adaptability) of traditional methods. Specifically, deep trajectory similarity computation aims to learn a distance function that can evaluate how similar two trajectories are via neural networks. However, existing learning-based methods focus on spatial similarity but ignore the time dimension of trajectories, which is suboptimal for time-aware applications. Besides, they tend to disregard the embedding of trajectories into road networks, restricting their applicability in real scenarios. In this paper, we propose an effective learning-based framework, called ST2Vec, to perform efficient spatially and temporally aware trajectory similarity computation in road networks. Finally, extensive experimental evaluation using three real trajectory data sets shows that ST2Vec outperforms all the state-of-the-art approaches substantially.
Towards a Complexity Classification of LCL Problems in Massively Parallel Computation
Venue: arXiv cs.DC 2022
Year: 2022

In this work, we develop the low-space Massively Parallel Computation (MPC) complexity landscape for a family of fundamental graph problems on trees. We present a general method that solves most locally checkable labeling (LCL) problems exponentially faster in the low-space MPC model than in the LOCAL message passing model. In particular, we show that all solvable LCL problems on trees can be solved in $O(\log n)$ time (high-complexity regime) and that all LCL problems on trees with deterministic complexity $n^{o(1)}$ in the LOCAL model can be solved in $O(\log \log n)$ time (mid-complexity regime). We observe that obtaining a greater speed-up than from $n^{o(1)}$ to $Θ(\log \log n)$ is conditionally impossible, since the problem of 3-coloring trees, which is a LCL problem with LOCAL time complexity $n^{o(1)}$, has a conditional MPC lower bound of $Ω(\log \log n)$ [Linial, FOCS'87; Ghaffari, Kuhn and Uitto, FOCS'19]. We emphasize that we solve LCL problems on constant-degree trees, and that our algorithms are deterministic, component-stable, and work in the low-space MPC model, where local memory is $O(n^δ)$ for $δ\in (0,1)$ and global memory is $O(m)$. For the high-complexity regime, there are two key ingredients. One is a novel $O(\log n)$-time tree rooting algorithm, which may be of independent interest. The other is a novel pointer-chain technique and analysis that allows us to solve any solvable LCL problem on trees in $O(\log n)$ time. For the mid-complexity regime, we adapt the approach by Chang and Pettie [FOCS'17], who gave a canonical LOCAL algorithm for solving LCL problems on trees.
A Belief Propagation Solution for Beam Coordination in MmWave Vehicular Networks
Venue: arXiv cs.NI 2022
Year: 2022

Millimeter-wave communication is widely seen as a promising option to increase the capacity of vehicular networks, where it is expected that connected cars will soon need to transmit and receive large amounts of data. Due to harsh propagation conditions, mmWave systems resort to narrow beams to serve their users, and such beams need to be configured according to traffic demand and its spatial distribution, as well as interference. In this work, we address the beam management problem, considering an urban vehicular network composed of gNBs. We first build an accurate, yet tractable, system model and formulate an optimization problem aiming at maximizing the total network data rate while accounting for the stochastic nature of the network scenario. Then we develop a graph-based model capturing the main system characteristics and use it to develop a belief propagation algorithmic framework, called CRAB, that has low complexity and, hence, can effectively cope with large-scale scenarios. We assess the performance of our approach under real-world settings and show that, in comparison to state-of-the-art alternatives, CRAB provides on average a 50% improvement in the amount of data transferred by the single gNBs and up to 30% better user coverage.
Visual Microfossil Identification via Deep Metric Learning
Venue: arXiv cs.CV 2022
Year: 2022

We apply deep metric learning for the first time to the problem of classifying planktic foraminifer shells on microscopic images. This species recognition task is an important information source and scientific pillar for reconstructing past climates. All foraminifer CNN recognition pipelines in the literature produce black-box classifiers that lack visualization options for human experts and cannot be applied to open-set problems. Here, we benchmark metric learning against these pipelines, produce the first scientific visualization of the phenotypic planktic foraminifer morphology space, and demonstrate that metric learning can be used to cluster species unseen during training. We show that metric learning outperforms all published CNN-based state-of-the-art benchmarks in this domain. We evaluate our approach on the 34,640 expert-annotated images of the Endless Forams public library of 35 modern planktic foraminifera species. Our results on this data show leading 92% accuracy (at 0.84 F1-score) in reproducing expert labels on withheld test data, and 66.5% accuracy (at 0.70 F1-score) when clustering species never encountered in training. We conclude that metric learning is highly effective for this domain and serves as an important tool towards expert-in-the-loop automation of microfossil identification. Keycode, network weights, and data splits are published with this paper for full reproducibility.
ColO-RAN: Developing Machine Learning-based xApps for Open RAN Closed-loop Control on Programmable Experimental Platforms
Venue: arXiv cs.NI 2022
Year: 2022

In spite of the new opportunities brought about by the Open RAN, advances in ML-based network automation have been slow, mainly because of the unavailability of large-scale datasets and experimental testing infrastructure. This slows down the development and widespread adoption of Deep Reinforcement Learning (DRL) agents on real networks, delaying progress in intelligent and autonomous RAN control. In this paper, we address these challenges by proposing practical solutions and software pipelines for the design, training, testing, and experimental evaluation of DRL-based closed-loop control in the Open RAN. We introduce ColO-RAN, the first publicly-available large-scale O-RAN testing framework with software-defined radios-in-the-loop. Building on the scale and computational capabilities of the Colosseum wireless network emulator, ColO-RAN enables ML research at scale using O-RAN components, programmable base stations, and a "wireless data factory". Specifically, we design and develop three exemplary xApps for DRL-based control of RAN slicing, scheduling and online model training, and evaluate their performance on a cellular network with 7 softwarized base stations and 42 users. Finally, we showcase the portability of ColO-RAN to different platforms by deploying it on Arena, an indoor programmable testbed. Extensive results from our first-of-its-kind large-scale evaluation highlight the benefits and challenges of DRL-based adaptive control. They also provide insights on the development of wireless DRL pipelines, from data analysis to the design of DRL agents, and on the tradeoffs associated to training on a live RAN. ColO-RAN and the collected large-scale dataset will be made publicly available to the research community.
Rank4Class: A Ranking Formulation for Multiclass Classification
Venue: arXiv cs.LG 2022
Year: 2022

Multiclass classification (MCC) is a fundamental machine learning problem of classifying each instance into one of a predefined set of classes. In the deep learning era, extensive efforts have been spent on developing more powerful neural embedding models to better represent the instance for improving MCC performance. In this paper, we do not aim to propose new neural models for instance representation learning, but to show that it is promising to boost MCC performance with a novel formulation through the lens of ranking. In particular, by viewing MCC as to rank classes for an instance, we first argue that ranking metrics, such as Normalized Discounted Cumulative Gain, can be more informative than the commonly used Top-$K$ metrics. We further demonstrate that the dominant neural MCC recipe can be transformed to a neural ranking framework. Based on such generalization, we show that it is intuitive to leverage advanced techniques from the learning to rank literature to improve the MCC performance out of the box. Extensive empirical results on both text and image classification tasks with diverse datasets and backbone neural models show the value of our proposed framework.
Know Your Customer: Balancing Innovation and Regulation for Financial Inclusion
Venue: arXiv cs.CY 2022
Year: 2022

Financial inclusion depends on providing adjusted services for citizens with disclosed vulnerabilities. At the same time, the financial industry needs to adhere to a strict regulatory framework, which is often in conflict with the desire for inclusive, adaptive, and privacy-preserving services. In this article we study how this tension impacts the deployment of privacy-sensitive technologies aimed at financial inclusion. We conduct a qualitative study with banking experts to understand their perspectives on service development for financial inclusion. We build and demonstrate a prototype solution based on open source decentralized identifiers and verifiable credentials software and report on feedback from the banking experts on this system. The technology is promising thanks to its selective disclosure of vulnerabilities to the full control of the individual. This supports GDPR requirements, but at the same time, there is a clear tension between introducing these technologies and fulfilling other regulatory requirements, particularly with respect to 'Know Your Customer.' We consider the policy implications stemming from these tensions and provide guidelines for the further design of related technologies.
Scalable Bicriteria Algorithms for Non-Monotone Submodular Cover
Venue: arXiv cs.DS 2022
Year: 2022

In this paper, we consider the optimization problem \scpl (\scp), which is to find a minimum cost subset of a ground set $U$ such that the value of a submodular function $f$ is above a threshold $τ$. In contrast to most existing work on \scp, it is not assumed that $f$ is monotone. Two bicriteria approximation algorithms are presented for \scp that, for input parameter $0 < ε< 1$, give $O( 1 / ε^2 )$ ratio to the optimal cost and ensures the function $f$ is at least $τ(1 - ε)/2$. A lower bound shows that under the value query model shows that no polynomial-time algorithm can ensure that $f$ is larger than $τ/2$. Further, the algorithms presented are scalable to large data sets, processing the ground set in a stream. Similar algorithms developed for \scp also work for the related optimization problem of \smpl (\smp). Finally, the algorithms are demonstrated to be effective in experiments involving graph cut and data summarization functions.
Zero-shot and Few-shot Learning with Knowledge Graphs: A Comprehensive Survey
Venue: arXiv cs.LG 2022
Year: 2022

Machine learning especially deep neural networks have achieved great success but many of them often rely on a number of labeled samples for supervision. As sufficient labeled training data are not always ready due to e.g., continuously emerging prediction targets and costly sample annotation in real world applications, machine learning with sample shortage is now being widely investigated. Among all these studies, many prefer to utilize auxiliary information including those in the form of Knowledge Graph (KG) to reduce the reliance on labeled samples. In this survey, we have comprehensively reviewed over 90 papers about KG-aware research for two major sample shortage settings -- zero-shot learning (ZSL) where some classes to be predicted have no labeled samples, and few-shot learning (FSL) where some classes to be predicted have only a small number of labeled samples that are available. We first introduce KGs used in ZSL and FSL as well as their construction methods, and then systematically categorize and summarize KG-aware ZSL and FSL methods, dividing them into different paradigms such as the mapping-based, the data augmentation, the propagation-based and the optimization-based. We next present different applications, including not only KG augmented prediction tasks such as image classification, question answering, text classification and knowledge extraction, but also KG completion tasks, and some typical evaluation resources for each task. We eventually discuss some challenges and open problems from different perspectives.
Online Grounding of Symbolic Planning Domains in Unknown Environments
Venue: arXiv cs.AI 2022
Year: 2022

If a robotic agent wants to exploit symbolic planning techniques to achieve some goal, it must be able to properly ground an abstract planning domain in the environment in which it operates. However, if the environment is initially unknown by the agent, the agent needs to explore it and discover the salient aspects of the environment needed to reach its goals. Namely, the agent has to discover: (i) the objects present in the environment, (ii) the properties of these objects and their relations, and finally (iii) how abstract actions can be successfully executed. The paper proposes a framework that aims to accomplish the aforementioned perspective for an agent that perceives the environment partially and subjectively, through real value sensors (e.g., GPS, and on-board camera) and can operate in the environment through low level actuators (e.g., move forward of 20 cm). We evaluate the proposed architecture in photo-realistic simulated environments, where the sensors are RGB-D on-board camera, GPS and compass, and low level actions include movements, grasping/releasing objects, and manipulating objects. The agent is placed in an unknown environment and asked to find objects of a certain type, place an object on top of another, close or open an object of a certain type. We compare our approach with the state of the art methods on object goal navigation based on reinforcement learning, showing better performances.
Precondition and Effect Reasoning for Action Recognition
Venue: arXiv cs.CV 2022
Year: 2022

Human action recognition has drawn a lot of attention in the recent years due to the research and application significance. Most existing works on action recognition focus on learning effective spatial-temporal features from videos, but neglect the strong causal relationship among the precondition, action and effect. Such relationships are also crucial to the accuracy of action recognition. In this paper, we propose to model the causal relationships based on the precondition and effect to improve the performance of action recognition. Specifically, a Cycle-Reasoning model is proposed to capture the causal relationships for action recognition. To this end, we annotate precondition and effect for a large-scale action dataset. Experimental results show that the proposed Cycle-Reasoning model can effectively reason about the precondition and effect and can enhance action recognition performance.
Efficient Strong Scaling Through Burst Parallel Training
Venue: arXiv cs.DC 2022
Year: 2022

As emerging deep neural network (DNN) models continue to grow in size, using large GPU clusters to train DNNs is becoming an essential requirement to achieving acceptable training times. In this paper, we consider the case where future increases in cluster size will cause the global batch size that can be used to train models to reach a fundamental limit: beyond a certain point, larger global batch sizes cause sample efficiency to degrade, increasing overall time to accuracy. As a result, to achieve further improvements in training performance, we must instead consider "strong scaling" strategies that hold the global batch size constant and allocate smaller batches to each GPU. Unfortunately, this makes it significantly more difficult to use cluster resources efficiently. We present DeepPool, a system that addresses this efficiency challenge through two key ideas. First, burst parallelism allocates large numbers of GPUs to foreground jobs in bursts to exploit the unevenness in parallelism across layers. Second, GPU multiplexing prioritizes throughput for foreground training jobs, while packing in background training jobs to reclaim underutilized GPU resources, thereby improving cluster-wide utilization. Together, these two ideas enable DeepPool to deliver a 1.2 - 2.3x improvement in total cluster throughput over standard data parallelism with a single task when the cluster scale is large.
Detect what you want: Target Sound Detection
Venue: arXiv cs.SD 2022
Year: 2022

Human beings can perceive a target sound type from a multi-source mixture signal by the selective auditory attention, however, such functionality was hardly ever explored in machine hearing. This paper addresses the target sound detection (TSD) task, which aims to detect the target sound signal from a mixture audio when a target sound's reference audio is given. We present a novel target sound detection network (TSDNet) which consists of two main parts: A conditional network which aims at generating a sound-discriminative conditional embedding vector representing the target sound, and a detection network which takes both the mixture audio and the conditional embedding vector as inputs and produces the detection result of the target sound. These two networks can be jointly optimized with a multi-task learning approach to further improve the performance. In addition, we study both strong-supervised and weakly-supervised strategies to train TSDNet and propose a data augmentation method by mixing two samples. To facilitate this research, we build a target sound detection dataset (\textit{i.e.} URBAN-TSD) based on URBAN-SED and UrbanSound8K datasets, and experimental results indicate our method could get the segment-based F scores of 76.3$\%$ and 56.8$\%$ on the strongly-labelled and weakly-labelled data respectively.
What are Weak Links in the npm Supply Chain?
Venue: arXiv cs.CR 2022
Year: 2022

Modern software development frequently uses third-party packages, raising the concern of supply chain security attacks. Many attackers target popular package managers, like npm, and their users with supply chain attacks. In 2021 there was a 650% year-on-year growth in security attacks by exploiting Open Source Software's supply chain. Proactive approaches are needed to predict package vulnerability to high-risk supply chain attacks. The goal of this work is to help software developers and security specialists in measuring npm supply chain weak link signals to prevent future supply chain attacks by empirically studying npm package metadata. In this paper, we analyzed the metadata of 1.63 million JavaScript npm packages. We propose six signals of security weaknesses in a software supply chain, such as the presence of install scripts, maintainer accounts associated with an expired email domain, and inactive packages with inactive maintainers. One of our case studies identified 11 malicious packages from the install scripts signal. We also found 2,818 maintainer email addresses associated with expired domains, allowing an attacker to hijack 8,494 packages by taking over the npm accounts. We obtained feedback on our weak link signals through a survey responded to by 470 npm package developers. The majority of the developers supported three out of our six proposed weak link signals. The developers also indicated that they would want to be notified about weak links signals before using third-party packages. Additionally, we discussed eight new signals suggested by package developers.
Lane Departure Prediction Based on Closed-Loop Vehicle Dynamics
Venue: arXiv cs.RO 2022
Year: 2022

An automated driving system should have the ability to supervise its own performance and to request human driver to take over when necessary. In the lane keeping scenario, the prediction of vehicle future trajectory is the key to realize safe and trustworthy driving automation. Previous studies on vehicle trajectory prediction mainly fall into two categories, i.e. physics-based and manoeuvre-based methods. Using a physics-based methodology, this paper proposes a lane departure prediction algorithm based on closed-loop vehicle dynamics model. We use extended Kalman filter to estimate the current vehicle states based on sensing module outputs. Then a Kalman Predictor with actual lane keeping control law is used to predict steering actions and vehicle states in the future. A lane departure assessment module evaluates the probabilistic distribution of vehicle corner positions and decides whether to initiate a human takeover request. The prediction algorithm is capable to describe the stochastic characteristics of future vehicle pose, which is preliminarily proved in simulated tests. Finally, the on-road tests at speeds of 15 to 50 km/h further show that the pro-posed method can accurately predict vehicle future trajectory. It may work as a promising solution to lane departure risk assessment for automated lane keeping functions.
Decentralized Stochastic Proximal Gradient Descent with Variance Reduction over Time-varying Networks
Venue: arXiv cs.LG 2022
Year: 2022

In decentralized learning, a network of nodes cooperate to minimize an overall objective function that is usually the finite-sum of their local objectives, and incorporates a non-smooth regularization term for the better generalization ability. Decentralized stochastic proximal gradient (DSPG) method is commonly used to train this type of learning models, while the convergence rate is retarded by the variance of stochastic gradients. In this paper, we propose a novel algorithm, namely DPSVRG, to accelerate the decentralized training by leveraging the variance reduction technique. The basic idea is to introduce an estimator in each node, which tracks the local full gradient periodically, to correct the stochastic gradient at each iteration. By transforming our decentralized algorithm into a centralized inexact proximal gradient algorithm with variance reduction, and controlling the bounds of error sequences, we prove that DPSVRG converges at the rate of $O(1/T)$ for general convex objectives plus a non-smooth term with $T$ as the number of iterations, while DSPG converges at the rate $O(\frac{1}{\sqrt{T}})$. Our experiments on different applications, network topologies and learning models demonstrate that DPSVRG converges much faster than DSPG, and the loss function of DPSVRG decreases smoothly along with the training epochs.