In domains such as health care and finance, shortage of labeled data and computational resources is a critical issue while developing machine learning algorithms. To address the issue of labeled data ...scarcity in training and deployment of neural network-based systems, we propose a new technique to train deep neural networks over several data sources. Our method allows for deep neural networks to be trained using data from multiple entities in a distributed fashion. We evaluate our algorithm on existing datasets and show that it obtains performance which is similar to a regular neural network trained on a single machine. We further extend it to incorporate semi-supervised learning when training with few labeled samples, and analyze any security concerns that may arise. Our algorithm paves the way for distributed training of deep neural networks in data sensitive applications when raw data may not be shared directly.
Unmanned Aerial Vehicles (UAVs) are an emerging technology with the potential to be used in industries and various sectors of human life to provide a wide range of applications and services. During ...the last decade, there has been a growing focus of research in the UAV's assistance paradigm as a fundamental concept resulting in the constant improvement between different kinds of ground networks and the hovering UAVs in the sky. Recently, the wide availability of embedded wireless interfaces in the communicating entities has allowed the deployment of such a paradigm simpler and easiest. Moreover, due to UAVs' controlled mobility and adjustable altitudes, they can be considered as the most appropriate candidate to enhance the performance and overcome the restrictions of ground networks. This comprehensive survey both studies and summarizes the existing UAV-assisted research, such as routing, data gathering, cellular communications, Internet of Things (IoT) networks, and disaster management that supports existing enabling technologies. Descriptions, classifications, and comparative studies related to different UAV-assisted proposals are presented throughout the paper. By pointing out numerous future challenges, it is expected to simulate research in this emerging and hot research area. To the best of our knowledge, there are many survey papers on the topic from a technology perspective. Nevertheless, this survey can be considered as the first attempt at a comprehensive analysis of different types of existing UAV-assisted networks and describes the state-of-the-art in UAV-assisted research.
Planar Graphs Have Bounded Queue-Number Dujmović, Vida; Joret, Gwenaël; Micek, Piotr ...
Journal of the ACM,
08/2020, Letnik:
67, Številka:
4
Journal Article
Recenzirano
Odprti dostop
We show that planar graphs have bounded queue-number, thus proving a conjecture of Heath et al. 66 from 1992. The key to the proof is a new structural tool called
layered partitions
, and the result ...that every planar graph has a vertex-partition and a layering, such that each part has a bounded number of vertices in each layer, and the quotient graph has bounded treewidth. This result generalises for graphs of bounded Euler genus. Moreover, we prove that every graph in a minor-closed class has such a layered partition if and only if the class excludes some apex graph. Building on this work and using the graph minor structure theorem, we prove that every proper minor-closed class of graphs has bounded queue-number.
Layered partitions have strong connections to other topics, including the following two examples. First, they can be interpreted in terms of strong products. We show that every planar graph is a subgraph of the strong product of a path with some graph of bounded treewidth. Similar statements hold for all proper minor-closed classes. Second, we give a simple proof of the result by DeVos et al. 31 that graphs in a proper minor-closed class have low treewidth colourings.
A convolutional neural network (CNN) is one of the most significant networks in the deep learning field. Since CNN made impressive achievements in many areas, including but not limited to computer ...vision and natural language processing, it attracted much attention from both industry and academia in the past few years. The existing reviews mainly focus on CNN's applications in different scenarios without considering CNN from a general perspective, and some novel ideas proposed recently are not covered. In this review, we aim to provide some novel ideas and prospects in this fast-growing field. Besides, not only 2-D convolution but also 1-D and multidimensional ones are involved. First, this review introduces the history of CNN. Second, we provide an overview of various convolutions. Third, some classic and advanced CNN models are introduced; especially those key points making them reach state-of-the-art results. Fourth, through experimental analysis, we draw some conclusions and provide several rules of thumb for functions and hyperparameter selection. Fifth, the applications of 1-D, 2-D, and multidimensional convolution are covered. Finally, some open issues and promising directions for CNN are discussed as guidelines for future work.
As data are increasingly being stored in different silos and societies becoming more aware of data privacy issues, the traditional centralized training of artificial intelligence (AI) models is ...facing efficiency and privacy challenges. Recently, federated learning (FL) has emerged as an alternative solution and continues to thrive in this new reality. Existing FL protocol designs have been shown to be vulnerable to adversaries within or outside of the system, compromising data privacy and system robustness. Besides training powerful global models, it is of paramount importance to design FL systems that have privacy guarantees and are resistant to different types of adversaries. In this article, we conduct a comprehensive survey on privacy and robustness in FL over the past five years. Through a concise introduction to the concept of FL and a unique taxonomy covering: 1) threat models; 2) privacy attacks and defenses; and 3) poisoning attacks and defenses, we provide an accessible review of this important topic. We highlight the intuitions, key techniques, and fundamental assumptions adopted by various attacks and defenses. Finally, we discuss promising future research directions toward robust and privacy-preserving FL, and their interplays with the multidisciplinary goals of FL.
Abstract
Accurate traffic flow prediction is valuable for satisfying citizens’ travel needs and alleviating urban traffic pressure. However, it is highly challenging due to the complexity of the ...urban geospatial structure and the highly nonlinear temporal and spatial dependence on human mobility. Most existing works proposed to rely on strict periods (e.g. daily and weekly) and separate the extraction of temporal and spatial features. Besides, most Recurrent Neural Network (RNN)-based models either fail to capture variations of spatial–temporal features in adjacent timestamps or ignore details of closeness. In this paper, we propose a Multi-attention based Hybrid-convolution Spatial-temporal Recurrent Network (MHSRN) for region-based traffic flow prediction. In MHSRN, we leverage a hybrid-convolution module to capture both shifting features and rich information at the nearest timestamps, and we apply the downsampling procedure to reduce the computation of RNN-based model. Furthermore, we propose to adopt a space-aware multi-attention module to re-perceive global and local spatial–temporal features. We conduct extensive experiments based on three real-world datasets. The results show that the MHSRN outperforms other challenging baselines by approximately 0.2–8.1% in mean absolute error on all datasets. On datasets other than TaxiBJ, the MHSRN reduces the root mean square error by at least 2.8% compared with the RNN-based model.
We present Path ORAM, an extremely simple Oblivious RAM protocol with a small amount of client storage. Partly due to its simplicity, Path ORAM is the most practical ORAM scheme known to date with ...small client storage. We formally prove that Path ORAM has a
O
(log
N
) bandwidth cost for blocks of size
B
= Ω (log
2
N
) bits. For such block sizes, Path ORAM is asymptotically better than the best-known ORAM schemes with small client storage. Due to its practicality, Path ORAM has been adopted in the design of secure processors since its proposal.
While improving prediction accuracy has been the focus of machine learning in recent years, this alone does not suffice for reliable decision-making. Deploying learning systems in consequential ...settings also requires calibrating and communicating the uncertainty of predictions. To convey instance-wise uncertainty for prediction tasks, we show how to generate set-valued predictions from a black-box predictor that controls the expected loss on future test points at a user-specified level. Our approach provides explicit finite-sample guarantees for any dataset by using a holdout set to calibrate the size of the prediction sets. This framework enables simple, distribution-free, rigorous error control for many tasks, and we demonstrate it in five large-scale machine learning problems: (1) classification problems where some mistakes are more costly than others; (2) multi-label classification, where each observation has multiple associated labels; (3) classification problems where the labels have a hierarchical structure; (4) image segmentation, where we wish to predict a set of pixels containing an object of interest; and (5) protein structure prediction. Last, we discuss extensions to uncertainty quantification for ranking, metric learning, and distributionally robust learning.
Universal Image Segmentation is not a new concept. Past attempts to unify image segmentation include scene parsing, panoptic segmentation, and, more recently, new panoptic architectures. However, ...such panoptic architectures do not truly unify image segmentation because they need to be trained individually on the semantic, instance, or panoptic segmentation to achieve the best performance. Ideally, a truly universal framework should be trained only once and achieve SOTA performance across all three image segmentation tasks. To that end, we propose OneFormer, a universal image segmentation framework that unifies segmentation with a multi-task train-once design. We first propose a task-conditioned joint training strategy that enables training on ground truths of each domain (semantic, instance, and panoptic segmentation) within a single multi-task training process. Secondly, we introduce a task token to condition our model on the task at hand, making our model task-dynamic to support multi-task training and inference. Thirdly, we propose using a query-text contrastive loss during training to establish better intertask and inter-class distinctions. Notably, our single OneFormer model outperforms specialized Mask2Former models across all three segmentation tasks on ADE20k, Cityscapes, and COCO, despite the latter being trained on each task individually. We believe OneFormer is a significant step towards making image segmentation more universal and accessible.
PDF
