اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOrdinally Consensus Subset over Multiple Metrics
102
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In this paper, we propose to study the following maximum ordinal consensus problem: Suppose we are given a metric system (M, X), which contains k metrics M = {rho_1,..., rho_k} defined on the same point set X. We aim to find a maximum subset X of X such that all metrics in M are consistent when restricted on the subset X. In particular, our definition of consistency will rely only on the ordering between pairwise distances, and thus we call a consistent subset an ordinal consensus of X w.r.t. M. We will introduce two concepts of consistency in the ordinal sense: a strong one and a weak one. Specifically, a subset X is strongly consistent means that the ordering of their pairwise distances is the same under each of the input metric rho_i from M. The weak consistency, on the other hand, relaxes this exact ordering condition, and intuitively allows us to take the plurality of ordering relation between two pairwise distances. We show in this paper that the maximum consensus problems over both the strong and the weak consistency notions are NP-complete, even when there are only 2 or 3 simple metrics, such as line metrics and ultrametrics. We also develop constant-factor approximation algorithms for the dual version, the minimum inconsistent subset problem of a metric system (M, P), - note that optimizing these two dual problems are equivalent.
قيم البحث
اقرأ أيضاً
The ethical concept of fairness has recently been applied in machine learning (ML) settings to describe a wide range of constraints and objectives. When considering the relevance of ethical concepts to subset selection problems, the concepts of diver
sity and inclusion are additionally applicable in order to create outputs that account for social power and access differentials. We introduce metrics based on these concepts, which can be applied together, separately, and in tandem with additional fairness constraints. Results from human subject experiments lend support to the proposed criteria. Social choice methods can additionally be leveraged to aggregate and choose preferable sets, and we detail how these may be applied.
We establish average consensus on graphs with dynamic topologies prescribed by evolutionary games among strategic agents. Each agent possesses a private reward function and dynamically decides whether to create new links and/or whether to delete exis
ting ones in a selfish and decentralized fashion, as indicated by a certain randomized mechanism. This model incurs a time-varying and state-dependent graph topology for which traditional consensus analysis is not applicable. We prove asymptotic average consensus almost surely and in mean square for any initial condition and graph topology. In addition, we establish exponential convergence in expectation. Our results are validated via simulation studies on random networks.
This work views neural networks as data generating systems and applies anomalous pattern detection techniques on that data in order to detect when a network is processing an anomalous input. Detecting anomalies is a critical component for multiple ma
chine learning problems including detecting adversarial noise. More broadly, this work is a step towards giving neural networks the ability to recognize an out-of-distribution sample. This is the first work to introduce Subset Scanning methods from the anomalous pattern detection domain to the task of detecting anomalous input of neural networks. Subset scanning treats the detection problem as a search for the most anomalous subset of node activations (i.e., highest scoring subset according to non-parametric scan statistics). Mathematical properties of these scoring functions allow the search to be completed in log-linear rather than exponential time while still guaranteeing the most anomalous subset of nodes in the network is identified for a given input. Quantitative results for detecting and characterizing adversarial noise are provided for CIFAR-10 images on a simple convolutional neural network. We observe an interference pattern where anomalous activations in shallow layers suppress the activation structure of the original image in deeper layers.
Dynamic graph representation learning is a task to learn node embeddings over dynamic networks, and has many important applications, including knowledge graphs, citation networks to social networks. Graphs of this type are usually large-scale but onl
y a small subset of vertices are related in downstream tasks. Current methods are too expensive to this setting as the complexity is at best linear-dependent on both the number of nodes and edges. In this paper, we propose a new method, namely Dynamic Personalized PageRank Embedding (textsc{DynamicPPE}) for learning a target subset of node representations over large-scale dynamic networks. Based on recent advances in local node embedding and a novel computation of dynamic personalized PageRank vector (PPV), textsc{DynamicPPE} has two key ingredients: 1) the per-PPV complexity is $mathcal{O}(m bar{d} / epsilon)$ where $m,bar{d}$, and $epsilon$ are the number of edges received, average degree, global precision error respectively. Thus, the per-edge event update of a single node is only dependent on $bar{d}$ in average; and 2) by using these high quality PPVs and hash kernels, the learned embeddings have properties of both locality and global consistency. These two make it possible to capture the evolution of graph structure effectively. Experimental results demonstrate both the effectiveness and efficiency of the proposed method over large-scale dynamic networks. We apply textsc{DynamicPPE} to capture the embedding change of Chinese cities in the Wikipedia graph during this ongoing COVID-19 pandemic (https://en.wikipedia.org/wiki/COVID-19_pandemic). Our results show that these representations successfully encode the dynamics of the Wikipedia graph.
The recent surge in federated data-management applications has brought forth concerns about the security of underlying data and the consistency of replicas in the presence of malicious attacks. A prominent solution in this direction is to employ a pe
rmissioned blockchain framework that is modeled around traditional Byzantine Fault-Tolerant (BFT) consensus protocols. Any federated application expects its data to be globally scattered to achieve faster access. But, prior works have shown that traditional BFT protocols are slow and this led to the rise of sharded-replicated blockchains. Existing BFT protocols for these sharded blockchains are efficient if client transactions require access to a single-shard, but face performance degradation if there is a cross-shard transaction that requires access to multiple shards. However, cross-shard transactions are common, and to resolve this dilemma, we present RingBFT, a novel meta-BFT protocol for sharded blockchains. RingBFT requires shards to adhere to the ring order, and follow the principle of process, forward, and re-transmit while ensuring the communication between shards is linear. Our evaluation of RingBFT against state-of-the-art sharding BFT protocols illustrates that RingBFT achieves up to 25x higher throughput, easily scales to nearly 500 globally distributed nodes, and achieves a peak throughput of 1.2 million txns/s.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
