اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدSkyline Computation with Noisy Comparisons
207
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Given a set of $n$ points in a $d$-dimensional space, we seek to compute the skyline, i.e., those points that are not strictly dominated by any other point, using few comparisons between elements. We adopt the noisy comparison model [FRPU94] where comparisons fail with constant probability and confidence can be increased through independent repetitions of a comparison. In this model motivated by Crowdsourcing applications, Groz & Milo [GM15] show three bounds on the query complexity for the skyline problem. We improve significantly on that state of the art and provide two output-sensitive algorithms computing the skyline with respective query complexity $O(ndlog (dk/delta))$ and $O(ndklog (k/delta))$ where $k$ is the size of the skyline and $delta$ the expected probability that our algorithm fails to return the correct answer. These results are tight for low dimensions.
قيم البحث
اقرأ أيضاً
Consider the following abstract coin tossing problem: Given a set of $n$ coins with unknown biases, find the most biased coin using a minimal number of coin tosses. This is a common abstraction of various exploration problems in theoretical computer
science and machine learning and has been studied extensively over the years. In particular, algorithms with optimal sample complexity (number of coin tosses) have been known for this problem for quite some time. Motivated by applications to processing massive datasets, we study the space complexity of solving this problem with optimal number of coin tosses in the streaming model. In this model, the coins are arriving one by one and the algorithm is only allowed to store a limited number of coins at any point -- any coin not present in the memory is lost and can no longer be tossed or compared to arriving coins. Prior algorithms for the coin tossing problem with optimal sample complexity are based on iterative elimination of coins which inherently require storing all the coins, leading to memory-inefficient streaming algorithms. We remedy this state-of-affairs by presenting a series of improved streaming algorithms for this problem: we start with a simple algorithm which require storing only $O(log{n})$ coins and then iteratively refine it further and further, leading to algorithms with $O(loglog{(n)})$ memory, $O(log^*{(n)})$ memory, and finally a one that only stores a single extra coin in memory -- the same exact space needed to just store the best coin throughout the stream. Furthermore, we extend our algorithms to the problem of finding the $k$ most biased coins as well as other exploration problems such as finding top-$k$ elements using noisy comparisons or finding an $epsilon$-best arm in stochastic multi-armed bandits, and obtain efficient streaming algorithms for these problems.
Search trees are commonly used to implement access operations to a set of stored keys. If this set is static and the probabilities of membership queries are known in advance, then one can precompute an optimal search tree, namely one that minimizes t
he expected access cost. For a non-key query, a search tree can determine its approximate location by returning the inter-key interval containing the query. This is in contrast to other dictionary data structures, like hash tables, that only report a failed search. We address the question what is the additional cost of determining approximate locations for non-key queries? We prove that for two-way comparison trees this additional cost is at most 1. Our proof is based on a novel probabilistic argument that involves converting a search tree that does not identify non-key queries into a random tree that does.
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(Bcdot Delta cdot min(n,Delta^2))$ in the round complexity, where $Delta$ 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.
Recent work by Locatello et al. (2018) has shown that an inductive bias is required to disentangle factors of interest in Variational Autoencoder (VAE). Motivated by a real-world problem, we propose a setting where such bias is introduced by providin
g pairwise ordinal comparisons between instances, based on the desired factor to be disentangled. For example, a doctor compares pairs of patients based on the level of severity of their illnesses, and the desired factor is a quantitive level of the disease severity. In a real-world application, the pairwise comparisons are usually noisy. Our method, Robust Ordinal VAE (ROVAE), incorporates the noisy pairwise ordinal comparisons in the disentanglement task. We introduce non-negative random variables in ROVAE, such that it can automatically determine whether each pairwise ordinal comparison is trustworthy and ignore the noisy comparisons. Experimental results demonstrate that ROVAE outperforms existing methods and is more robust to noisy pairwise comparisons in both benchmark datasets and a real-world application.
We consider the realization of universal quantum computation through braiding of Majorana fermions supplemented by unprotected preparation of noisy ancillae. It has been shown by Bravyi [Phys. Rev. A 73, 042313 (2006)] that under the assumption of pe
rfect braiding operations, universal quantum computation is possible if the noise rate on a particular 4-fermion ancilla is below 40%. We show that beyond a noise rate of 89% on this ancilla the quantum computation can be efficiently simulated classically: we explicitly show that the noisy ancilla is a convex mixture of Gaussian fermionic states in this region, while for noise rates below 53% we prove that the state is not a mixture of Gaussian states. These results were obtained by generalizing concepts in entanglement theory to the setting of Gaussian states and their convex mixtures. In particular we develop a complete set of criteria, namely the existence of a Gaussian-symmetric extension, which determine whether a state is a convex mixture of Gaussian states.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
