United States

Discovering elements of the hidden set(s), also known as Group Testing (GT), is a well-established area in which one party tries to discover elements hidden by the other party by asking queries and analyzing feedback. The feedback is a function of the intersection of the query with the hidden set - in our case, it is a classical double-threshold function, which returns $i$ if the intersection is a singleton $i$
and &quot;null&quot; otherwise (i.e., when the intersection is empty or of size at least $2$). Group testing query systems are used to efficiently maintain &quot;hot&quot; elements in data streaming, to construct signature files, to (distributed) reconstruction of noisy pooled data, dimensionality reduction, and in many other areas. In this work, we enhance GT by two features. First, we introduce a local feedback framework to this problem: each hidden element is an &quot;autonomous&quot; element and can analyze feedback itself, but only for the queries which this element is a part of. The goal is to design a deterministic non-adaptive sequence of queries that allows each non-hidden element to learn about all other hidden elements. We show that, surprisingly, this task requires substantially more queries than the classic group testing - by proving a super-qubic (in terms of the number of hidden elements) lower bound and by constructing a specific query sequence of slightly longer length. Such a query system is also an extension of a well-known superimposed code, in a way that the decoding can be done only by the owners of the codewords. Second, we extend the results to the model where elements may belong to certain clusters and retrieving them could be done only via queries avoiding elements from &quot;interfering&quot; clusters. The main challenge is in not knowing which interfering clusters are non-empty (and thus, need to be avoided) and how to speed up the retrieval process by asking queries across many clusters. Our algorithms could be generalized to other feedback functions, to adversarial/stochastic fault-prone scenarios, implemented in a distributed setting and applied to the information theory and codes.

AAAI 2025

Searching for and Avoiding Hidden Sets Using Queries with Local Feedback

adversarial search

# Welcome everyone to ACL 2022!

The 60th Annual Meeting of the Association for Computational Linguistics is taking place May 22-27, 2022 as a hybrid event, in Dublin and online. We are happy to welcome all of you to this anniversary edition with an almost 50-50 in-person and virtual participation. 
The main conference program features oral presentations, in-person and virtual posters and demo sessions, a plenary session for our best paper presentations and awards, three amazing keynote events and two new initiatives of invited talks: Spotlight Talks for Young Rising Stars (STIRS) and The Next Big Idea Talks. Posters (including Findings of ACL 2022) and demos are grouped by areas for both the in-person and the virtual sessions. For the virtual component, the talks will be on Zoom and the posters and the demos will be in GatherTown. The Student Research Workshop will have an oral session and a poster session as part of Poster Session 1. The program also features eight Tutorials and 28 Workshops. 

 
We wish you a wonderful conference! 
[**The ACL 2022 Organizing Committee**](https://www.2022.aclweb.org/organisers)
 
[**Conference Handbook**](https://drive.google.com/file/d/1_BUCMfhMVrjG9E2e71aHdHeE28KSje0l/view?usp=sharing) 
[**Mini Handbook**](https://drive.google.com/file/d/1qlBKl0wzmlVF1oCeMQl3BahLd9nLP5Ce/view?usp=sharing) 
[**Posters and Demo guides**](https://drive.google.com/file/d/1UucMAoCNncIOaH1rMMDa0owuG9qgvJTG/view?usp=sharing)

ACL 2022

The Association for Computational Linguistics (ACL) is the premier international scientific and professional society for people working on computational problems involving human language, a field often referred to as either computational linguistics or natural language processing (NLP). 

Discovering elements of the hidden set(s), also known as Group Testing (GT), is a well-established area in which one party tries to discover elements hidden by the other party by asking queries and analyzing feedback. The feedback is a function of the intersection of the query with the hidden set - in our case, it is a classical double-threshold function, which returns $i$ if the intersection is a singleton $i$
and "null" otherwise (i.e., when the intersection is empty or of size at least $2$). Group testing query systems are used to efficiently maintain "hot" elements in data streaming, to construct signature files, to (distributed) reconstruction of noisy pooled data, dimensionality reduction, and in many other areas. In this work, we enhance GT by two features. First, we introduce a local feedback framework to this problem: each hidden element is an "autonomous" element and can analyze feedback itself, but only for the queries which this element is a part of. The goal is to design a deterministic non-adaptive sequence of queries that allows each non-hidden element to learn about all other hidden elements. We show that, surprisingly, this task requires substantially more queries than the classic group testing - by proving a super-qubic (in terms of the number of hidden elements) lower bound and by constructing a specific query sequence of slightly longer length. Such a query system is also an extension of a well-known superimposed code, in a way that the decoding can be done only by the owners of the codewords. Second, we extend the results to the model where elements may belong to certain clusters and retrieving them could be done only via queries avoiding elements from "interfering" clusters. The main challenge is in not knowing which interfering clusters are non-empty (and thus, need to be avoided) and how to speed up the retrieval process by asking queries across many clusters. Our algorithms could be generalized to other feedback functions, to adversarial/stochastic fault-prone scenarios, implemented in a distributed setting and applied to the information theory and codes.

poster

We are pleased to announce the Thirty-Ninth AAAI Conference on Artificial Intelligence (AAAI-25), which will be held in Philadelphia, Pennsylvania at the Pennsylvania Convention Center from February 25 to March 4, 2025.

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-25 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and a range of other activities to be announced.

### [Invited Speakers](https://aaai.org/conference/aaai/aaai-25/aaai-25-invited-speakers/)

Register [here](https://aaai.org/conference/aaai/aaai-25/registration/)

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-25 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and a range of other activities to be announced.



Recent advancements in Zero-shot Neural Architecture Search (NAS) highlight the ability of zero-cost proxies in identifying superior architecture. However, we identify a critical issue with current zero-cost proxies: they aggregate node-wise zero-cost statistics without considering that not all nodes in a neural network equally impact performance estimation. Our observations reveal that node-wise zero-cost statistics significantly vary in their contributions to performance, with each node exhibiting a degree of uncertainty. Based on this insight, we introduce a novel method called Parametric Zero-Cost Proxies (ParZC) framework to enhance the adaptability of zero-cost proxies through parameterization. To address the node indiscrimination, we propose a Mixer Architecture with Bayesian Network (MABN) to explore the node-wise zero-cost statistics and estimate node-specific uncertainty. Moreover, we propose DiffKendall as a loss function to improve ranking consistency. Comprehensive experiments on NAS-Bench-101, 201, and NDS demonstrate the superiority of our proposed ParZC compared to existing zero-shot NAS methods. Additionally, we demonstrate the versatility and adaptability of ParZC by transferring it to the Vision Transformer search space. Code will be available upon acceptance.

ParZC: Parametric Zero-Cost Proxies for Efficient NAS

In the multi-objective discrete optimization problem (MODOP), the exact nadir objective vector is crucial for decision-making, yet it remains challenging to find. Existing methods for tackling this problem have limitations in theoretical guarantees or high computational costs. This paper first applies boundary decomposition to the MODOP and proposes an exact algorithm called BDNC. BDNC is designed to address a bilevel optimization problem for each objective with finite-time convergence guarantees. The lower-level optimization problem, termed the boundary subproblem, is a scalarization of the MODOP. It can be solved using any suitable single-objective exact solver. According to the theoretical foundations of boundary decomposition, some specific settings of the boundary subproblem can ensure alignment with the nadir objective vector under mild conditions. The upper-level optimization problem evaluates a potential setting using the optimal solution to the lower-level one. It employs our proposed novel pruning method to efficiently identify the specific settings. Moreover, BDNC can leverage a trade-off provided by the decision-makers, potentially facilitating the decision-making process. Experiments on various MODOPs demonstrate that BDNC exhibits superior and reliable performance in terms of runtime compared to existing exact methods.

Boundary Decomposition for Finding Nadir Objective Vector in Multi-Objective Discrete Optimization

Search and recommendation ecosystems exhibit competition among content creators. This competition has been tackled in a variety of game-theoretic frameworks. Content creators generate documents with the aim of being recommended by a content ranker for various information needs. In order for the ecosystem, modeled as a content ranking game, to be effective and maximize user welfare, it should guarantee stability, where stability is associated with the existence of pure Nash equilibrium in the corresponding game. Moreover, if the contents' ranking algorithm possesses a game in which any best-response learning dynamics of the content creators converge to equilibrium of high welfare, the system is considered highly attractive. However, as classical content ranking algorithms, employed by search and recommendation systems, rank documents by their distance to information needs, it has been shown that they fail to provide such stability properties. As a result, novel content ranking algorithms have been devised. In this work, we offer an alternative approach: corpus enrichment with a small set of fixed dummy documents. It turns out that, with the right design, such enrichment can lead to pure Nash equilibrium and even to the convergence of any best-response dynamics to a high welfare result, where we still employ the classical/current content ranking approach. We show two such corpus enrichment techniques with tight bounds on the number of documents needed to obtain the desired results. Interestingly, our study is a novel extension of Borel's Colonel Blotto game.

On the Power of Strategic Corpus Enrichment in Content Creation Games

Probabilities of causation (PoC) offer valuable insights for informed decision-making. This paper introduces novel variants of PoC-controlled direct, natural direct, and natural indirect probability of necessity and sufficiency (PNS). These metrics quantify the necessity and sufficiency of a treatment for producing an outcome, accounting for different causal pathways. We develop identification theorems for these new PoC measures, allowing for their estimation from observational data. We demonstrate the practical application of our results through an analysis of a real-world psychology dataset.

Mediation Analysis for Probabilities of Causation

Knowledge graph (KG) completion aims to identify additional facts that can be inferred from the existing facts in the KG. Recent developments in this field have explored this task in the inductive setting, where at test time one sees entities that were not present during training; the most performant models in the inductive setting have employed path encoding modules in addition to standard subgraph encoding modules. This work similarly focuses on KG completion in the inductive setting, without the explicit use of path encodings, which can be time-consuming and introduces several hyperparameters that require costly hyperparameter optimization. Our approach uses a Transformer-based subgraph encoding module only; we introduce connection-biased attention and entity role embeddings into the subgraph encoding module to eliminate the need for an expensive and time-consuming path encoding module. Evaluations on standard inductive KG completion benchmark datasets demonstrate that our \textbf{C}onnection-\textbf{B}iased \textbf{Li}nk \textbf{P}rediction (CBLiP) model has superior performance to models that do not use path information. Compared to models that utilize path information, CBLiP shows competitive or superior performance while being faster. Additionally, to show that the effectiveness of connection-biased attention and entity role embeddings also holds in the transductive setting, we compare CBLiP's performance on the relation prediction task in the transductive setting.

Replacing Paths with Connection-Biased Attention for Knowledge Graph Completion

Multimodal large language models (MLLMs) demand considerable computations for inference due to the extensive parameters and the additional input tokens needed for visual information representation. Herein, we introduce Visual Tokens Withdrawal (VTW), a plug-and-play module to boost MLLMs for rapid inference. Our approach is inspired by two intriguing phenomena we have observed: (1) the attention sink phenomenon that is prevalent in LLMs also persists in MLLMs, suggesting that initial tokens and nearest tokens receive the majority of attention, while middle vision tokens garner minimal attention in deep layers; (2) the presence of information migration, which implies that visual information is transferred to subsequent text tokens within the first few layers of MLLMs. As per our findings, we conclude that vision tokens are unnecessary in the deep layers of MLLMs. Thus, we strategically withdraw them at a certain layer, enabling only text tokens to engage in subsequent layers. To pinpoint the ideal layer for VTW, we initially analyze a limited set of tiny datasets and choose the first layer that meets the Kullback-Leibler divergence criterion. Our VTW approach can cut computational overhead by over 40\% across diverse multimodal tasks while maintaining performance.

Boosting Multimodal Large Language Models with Visual Tokens Withdrawal for Rapid Inference

This paper focuses on generative depth estimation. Current discriminative depth estimation approaches are limited due to blurry artifacts, while state-of-the-art generative methods suffer from slow sampling because of SDE nature between noise and depth map transport. Our method advances depth estimation by framing it as direct transport between paired image and depth distributions. We find that flow matching effectively addresses this, as its straight trajectories through solution space provide efficiency and high quality. Generative depth estimation has long faced challenges in training and data efficiency due to optimization difficulties and data annotation. To address this, we incorporate external knowledge from pretrained foundation diffusion models and discriminative depth estimators. Generative models produce high-fidelity depth predictions but often lack the accuracy of discriminative models. By leveraging prediction similarities between diffusion models and flow matching, we initialize our model with this knowledge to enhance training efficiency. To improve data efficiency, we train on synthetic data in a source-data-free manner, drawing on the strengths of discriminative models. Because of its generative nature, our model reliably predicts the confidence of its depth estimates. On standard benchmarks of complex natural scenes, our approach achieves competitive performance by improving sampling, training, and data efficiency, despite being trained on minimal synthetic data. Project page and code are available.

DepthFM: Fast Generative Monocular Depth Estimation with Flow Matching

Multimodal knowledge graphs (MMKG) store structured world knowledge enriched with multimodal descriptive information. However, MMKG often faces the challenge of incompleteness. The primary objective of multimodal knowledge graph completion (MMKGC) is to predict missing entities within MMKG. Current MMKGC methods struggle with addressing the issue of over-trust attention and how to enhance the robustness of the model. To overcome these problems, we introduce APKGC, a noise-enhanced multimodal method for knowledge graph completion with attention penalty. APKGC effectively adjusts the attention scores in the language model and alleviates over-trust attention through a specifically designed attention penalty module. Additionally, an adaptive noise sampling module is proposed to supplement the entity's multimodal information, thereby enhancing the model's robustness. Experimental evaluation demonstrates that APKGC excels in overcoming these challenges. Compared to the existing state-of-the-art MMKGC model, APKGC improves Hit@1 by 3.3% on the DB15K dataset and by 3.4% on the MKG-W dataset. Our code is available at https://anonymous.4open.science/r/APKGC-FC82.

APKGC: Noise-enhanced Multi-Modal Knowledge Graph Completion with Attention Penalty

Video Internet of Things (VIoT) has shown full potential in collecting an unprecedented volume of video data. How to schedule the domain-specific perceiving models and analyze the collected videos uniformly, efficiently, and especially intelligently to accomplish complicated tasks is challenging. To address the challenge, we build VIoTGPT, the framework based on LLMs to correctly interact with humans, query knowledge videos, and invoke vision models to analyze multimedia data collaboratively. To support VIoTGPT and related future works, we meticulously crafted the VIoT-Tool dataset, including the training dataset and the benchmark involving 11 representative vision models across three categories based on semi-automatic annotations. To guide LLM to act as the intelligent agent towards intelligent VIoT, we resort to ReAct instruction tuning method based on VIoT-Tool to learn the tool capability. Quantitative and qualitative experiments and analyses demonstrate the effectiveness of VIoTGPT. We believe VIoTGPT contributes to improving human-centered experiences in VIoT applications.

VIoTGPT: Learning to Schedule Vision Tools Towards Intelligent Video Internet of Things

Model editing aims at selectively updating a small subset of a neural model's parameters with an interpretable strategy to achieve desired modifications. It can significantly reduce computational costs to adapt to large language models(LLMs). Given its ability to precisely target critical components within LLMs, model editing shows great potential for efficient fine-tuning applications. In this work, we investigate model editing to serve as an efficient method for adapting LLMs to solve aspect-based sentiment classification. Through causal interventions, we trace and determine which neuron hidden states are essential for the model’s predictions. By performing interventions and restorations on each component of an LLM, we identify the importance of these components for aspect-based sentiment classification. Our findings reveal that a distinct set of mid-layer representations is essential for detecting the sentiment polarity of given aspect words. Leveraging these insights, we develop a model editing approach that focuses exclusively on these critical parts of the LLM, leading to a more efficient method for adapting LLMs. Our in and out of domain experiments demonstrate that this approach achieves competitive results compared to the currently strongest methods with significantly fewer trainable parameters, highlighting a more efficient and interpretable fine-tuning strategy.

Downloads

Next from AAAI 2025

ParZC: Parametric Zero-Cost Proxies for Efficient NAS

Similar lecture

Query Generation with External Knowledge for Dense Retrieval

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES