The Query/Hit Model for Sequential Hypothesis Testing

• URL: http://arxiv.org/abs/2502.00605v1
• Date: Sun, 02 Feb 2025 00:23:28 GMT
• Title: The Query/Hit Model for Sequential Hypothesis Testing
• Authors: Mahshad Shariatnasab, Stefano Rini, Farhad Shirani, S. Sitharama Iyengar,
• Abstract summary: This work introduces the Query/Hit (Q/H) learning model.<n>One agent, Alice, has access to a streaming source, while the other, Bob, does not have direct access to the source.<n> Communication occurs through sequential Q/H pairs: Bob sends a sequence of source symbols (queries), and Alice responds with the waiting time until each query appears in the source stream (hits)
• Score: 8.242194776558895
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This work introduces the Query/Hit (Q/H) learning model. The setup consists of two agents. One agent, Alice, has access to a streaming source, while the other, Bob, does not have direct access to the source. Communication occurs through sequential Q/H pairs: Bob sends a sequence of source symbols (queries), and Alice responds with the waiting time until each query appears in the source stream (hits). This model is motivated by scenarios with communication, computation, and privacy constraints that limit real-time access to the source. The error exponent for sequential hypothesis testing under the Q/H model is characterized, and a querying strategy, the Dynamic Scout-Sentinel Algorithm (DSSA), is proposed. The strategy employs a mutual information neural estimator to compute the error exponent associated with each query and to select the query with the highest efficiency. Extensive empirical evaluations on both synthetic and real-world datasets -- including mouse movement trajectories, typesetting patterns, and touch-based user interactions -- are provided to evaluate the performance of the proposed strategy in comparison with baselines, in terms of probability of error, query choice, and time-to-detection.

Related papers

• Unbiased Learning to Rank with Query-Level Click Propensity Estimation: Beyond Pointwise Observation and Relevance [74.43264459255121]
  In real-world scenarios, users often click only one or two results after examining multiple relevant options. We propose a query-level click propensity model to capture the probability that users will click on different result lists. Our method introduces a Dual Inverse Propensity Weighting mechanism to address both relevance saturation and position bias.
  arXiv  Detail & Related papers  (2025-02-17T03:55:51Z)
• SureMap: Simultaneous Mean Estimation for Single-Task and Multi-Task Disaggregated Evaluation [75.56845750400116]
  Disaggregated evaluation -- estimation of performance of a machine learning model on different subpopulations -- is a core task when assessing performance and group-fairness of AI systems. We develop SureMap that has high estimation accuracy for both multi-task and single-task disaggregated evaluations of blackbox models. Our method combines maximum a posteriori (MAP) estimation using a well-chosen prior together with cross-validation-free tuning via Stein's unbiased risk estimate (SURE)
  arXiv  Detail & Related papers  (2024-11-14T17:53:35Z)
• pEBR: A Probabilistic Approach to Embedding Based Retrieval [4.8338111302871525]
  Embedding retrieval aims to learn a shared semantic representation space for both queries and items. In current industrial practice, retrieval systems typically retrieve a fixed number of items for different queries.
  arXiv  Detail & Related papers  (2024-10-25T07:14:12Z)
• Long-Span Question-Answering: Automatic Question Generation and QA-System Ranking via Side-by-Side Evaluation [65.16137964758612]
  We explore the use of long-context capabilities in large language models to create synthetic reading comprehension data from entire books. Our objective is to test the capabilities of LLMs to analyze, understand, and reason over problems that require a detailed comprehension of long spans of text.
  arXiv  Detail & Related papers  (2024-05-31T20:15:10Z)
• Scalable Decentralized Algorithms for Online Personalized Mean Estimation [12.002609934938224]
  This study focuses on a simplified version of the overarching problem, where each agent collects samples from a real-valued distribution over time to estimate its mean. We introduce two collaborative mean estimation algorithms: one draws inspiration from belief propagation, while the other employs a consensus-based approach.
  arXiv  Detail & Related papers  (2024-02-20T08:30:46Z)
• MeaeQ: Mount Model Extraction Attacks with Efficient Queries [6.1106195466129485]
  We study model extraction attacks in natural language processing (NLP) We propose MeaeQ, a straightforward yet effective method to address these issues. MeaeQ achieves higher functional similarity to the victim model than baselines while requiring fewer queries.
  arXiv  Detail & Related papers  (2023-10-21T16:07:16Z)
• Causal Feature Selection via Transfer Entropy [59.999594949050596]
  Causal discovery aims to identify causal relationships between features with observational data. We introduce a new causal feature selection approach that relies on the forward and backward feature selection procedures. We provide theoretical guarantees on the regression and classification errors for both the exact and the finite-sample cases.
  arXiv  Detail & Related papers  (2023-10-17T08:04:45Z)
• Single-Stage Visual Relationship Learning using Conditional Queries [60.90880759475021]
  TraCQ is a new formulation for scene graph generation that avoids the multi-task learning problem and the entity pair distribution. We employ a DETR-based encoder-decoder conditional queries to significantly reduce the entity label space as well. Experimental results show that TraCQ not only outperforms existing single-stage scene graph generation methods, it also beats many state-of-the-art two-stage methods on the Visual Genome dataset.
  arXiv  Detail & Related papers  (2023-06-09T06:02:01Z)
• Walk for Learning: A Random Walk Approach for Federated Learning from Heterogeneous Data [17.978941229970886]
  We focus on Federated Learning (FL) as a canonical application. One of the main challenges of FL is the communication bottleneck between the nodes and the parameter server. We present an adaptive random walk learning algorithm.
  arXiv  Detail & Related papers  (2022-06-01T19:53:24Z)
• Pre and Post Counting for Scalable Statistical-Relational Model Discovery [19.18886406228943]
  Statistical-Relational Model Discovery aims to find statistically relevant patterns in relational data. As with propositional (non-relational) graphical models, the major scalability bottleneck for model discovery is computing instantiation counts. This paper takes a detailed look at the memory and speed trade-offs between pre-counting and post-counting strategies for relational learning.
  arXiv  Detail & Related papers  (2021-10-19T07:03:35Z)
• Probabilistic Case-based Reasoning for Open-World Knowledge Graph Completion [59.549664231655726]
  A case-based reasoning (CBR) system solves a new problem by retrieving cases' that are similar to the given problem. In this paper, we demonstrate that such a system is achievable for reasoning in knowledge-bases (KBs) Our approach predicts attributes for an entity by gathering reasoning paths from similar entities in the KB.
  arXiv  Detail & Related papers  (2020-10-07T17:48:12Z)
• Tradeoffs in Sentence Selection Techniques for Open-Domain Question Answering [54.541952928070344]
  We describe two groups of models for sentence selection: QA-based approaches, which run a full-fledged QA system to identify answer candidates, and retrieval-based models, which find parts of each passage specifically related to each question. We show that very lightweight QA models can do well at this task, but retrieval-based models are faster still.
  arXiv  Detail & Related papers  (2020-09-18T23:39:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.