United States

In adaptive systems, predictors are used to anticipate changes in the system’s state or behavior that may require system adaption, e.g., changing its configuration or adjusting resource allocation. Therefore, the quality of predictors is crucial for the overall reliability and performance of the system under control. This paper studies predictors in systems exhibiting probabilistic and non-deterministic behavior modelled as Markov decision processes (MDPs). Main contributions are the introduction of quantitative notions that measure the effectiveness of predictors in terms of their average capability to predict the occurrence of failures or other undesired system behaviors. The average is taken over all memoryless policies. We study two classes of such notions. One class is inspired by concepts that have been introduced in statistical analysis to explain the impact of features on the decisions of binary classifiers (such as precision, recall, f-score). Second, we study a measure that borrows ideas from recent work on probability-raising causality in MDPs and determines the quality of a predictor by the fraction of memoryless policies under which (the set of states in) the predictor is a probabilityraising cause for the considered failure scenario.

AAAI 2025

Formal Quality Measures for Predictors in Markov Decision Processes

causality

## Welcome to EMNLP 2024! 
We are excited to welcome you to one of the most prominent conferences in the field of Natural Language Processing. This year, EMNLP 2024 is being held in a hybrid format,
offering both virtual and in-person participation in beautiful Miami. Due to a record-breaking number of submissions, we've expanded the total number of accepted papers to accommodate more cutting-edge research from around the globe.
### [Conference Handbook](https://drive.google.com/file/d/1WPROgxjLAC96AJL7Ugy0tEnYm7dkrbHt/view?usp=sharing)

You are required to register for this event. **Please register [here](https://2024.emnlp.org/registration/).** The EMNLP 2024 event page on Underline will be open to public one week prior to the event.

Please register!

EMNLP 2024

EMNLP 2024 will take place in Miami, Florida from Nov 12th to Nov 16th, 2024, at the Hyatt Regency Miami Hote and on Underline for remote participants.

technical paper

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 multimodal large language models (MLLMs) have shown unprecedented capabilities in advancing various vision-language tasks. However, MLLMs face significant challenges with hallucinations, and misleading outputs that do not align with the input data. While existing efforts are paid to combat MLLM hallucinations, several pivotal challenges are still unsolved. First, while current approaches aggressively focus on addressing errors at the perception level, another important type at the cognition level requiring factual commonsense can be overlooked. In addition, existing methods might fall short in finding a more effective way to represent visual input, which is yet a key bottleneck that triggers visual hallucinations. Moreover, MLLMs can frequently be misled by faulty textual inputs and cause hallucinations, while unfortunately, this type of issue has long been overlooked by existing studies. Inspired by human intuition in handling hallucinations, this paper introduces a novel bottom-up reasoning framework. Our framework systematically addresses potential issues in both visual and textual inputs by verifying and integrating perception-level information with cognition-level commonsense knowledge, ensuring more accurate and reliable outputs. Extensive experiments demonstrate significant improvements in multiple hallucination benchmarks after integrating MLLMs with the proposed framework. In-depth analysis reveals the great potential of our methods in addressing perception- and cognition-level hallucinations.

Combating Multimodal LLM Hallucination via Bottom-Up Holistic Reasoning

We initiate the study of tree structures in the context of scenario-based robust optimization. Specifically, we study Binary Search Trees (BSTs) and Huffman coding, two fundamental techniques for efficiently managing and encoding data based on a known set of frequencies of keys. Given $k$ different scenarios, each defined by a distinct frequency distribution over the keys, our objective is to compute a single tree of best-possible performance, relative to any scenario. 

We consider, as performance metrics, the competitive ratio, which compares multiplicatively the cost of the solution to the tree of least cost among all scenarios, as well as the regret, which induces a similar, but additive comparison. For BSTs, we show that the problem is NP-hard across both  metrics. We also show how to obtain a tree of competitive ratio  $\lceil \log_2(k+1) \rceil$, and we prove that this ratio is optimal. For Huffman Trees, we show that the problem is, likewise, NP-hard across both metrics; we also give an algorithm of regret $\lceil \log_2 k \rceil$, which we show is near-optimal, by proving a lower bound of $\lfloor \log_2 k \rfloor$. Last, we give a polynomial-time algorithm for computing Pareto-optimal BSTs with respect to their regret, assuming scenarios defined by uniform distributions over the keys. This setting captures, in particular, the first study of fairness in the context of data structures. We provide an experimental evaluation of all algorithms. To this end, we also provide mixed integer linear program formulation for computing optimal trees.

Scenario-Based Robust Optimization of Tree Structures

Strategic interactions can be represented more concisely, and analyzed and solved more efficiently, if we are aware of the symmetries within that multi-agent system. Symmetries also have conceptual implications, for example for equilibrium selection. We study the computational complexity of identifying and using symmetries. Using the classical framework of normal-form games, we consider game symmetries that can be across some or all players and/or actions. We find a strong connection between game symmetries and graph automorphisms, yielding graph automorphism and graph isomorphism completeness results for characterizing the symmetries present in a game.

Next, we investigate when exactly game symmetries can be successfully leveraged for Nash equilibrium computation. We show that finding a Nash equilibrium that respects a given set of symmetries is PPAD- and CLS-complete in general-sum and team games respectively---that is, exactly as hard as Brouwer fixed point and gradient descent problems. Finally, we present polynomial-time methods for the special cases where we are aware of a vast number of symmetries, or where the game is two-player zero-sum and we do not even know the symmetries.

Computing Game Symmetries and Equilibria That Respect Them

There is an increasing body of work using Large Language Models (LLMs) as agents for orchestrating workflows and making decisions in domains that require planning and multi-step reasoning. As a result, it is imperative to evaluate LLMs on core skills required for planning. In this work, we present ACPBench, a collection of benchmark that evaluates the reasoning tasks in the field of planning. The benchmark consists of 7 reasoning tasks over 13 planning domains. The collection is constructed from planning domains described in a formal
language. This allows us to use planning tools for obtaining provably correct information and generate massive data, meeting the large-scale data requirements of language models. Our extensive evaluation of 18 open-sourced and frontier LLMs highlight the significant gap in the reasoning capability of the LLMs. The average accuracy of even the best-performing frontier LLM GPT-4o on these tasks can fall as low as 52.50%.

ACPBench: Reasoning About Action, Change, and Planning

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.

Searching for and Avoiding Hidden Sets Using Queries with Local Feedback

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

Recommender systems in various applications often encounter the challenge of cold-start, which refers to how to provide recommendations for completely new users. Cross-domain recommendation offers a solution to address this cold-start issue by leveraging user interaction information from other domains and providing recommendations for users in the target domain. However, applying the classic two-tower model in cross-domain scenarios for pure cold-start users proves challenging, and most existing cross-domain cold-start recommendation models adopt an embedding-mapping framework that lacks end-to-end efficiency. The parallel training recommendation method lacks consideration of the domain-level intrinsic characteristics of cross-domain information. In this paper, we propose a generalized framework that Domain-level Disentanglement framework based on information enhancement for Cross-domain Cold-start Recommendation. On one hand, we achieve deep utilization of domain-level information through independent extraction of domain knowledge and fusion using heuristic strategies. On the other hand, our model is incorporated with an information enhancement network based on user attention and a user personalized adaptor. We introduce measures to assess user variability and immutability in cross-domain recommendation, aiming to eliminate inter-domain bias and highlight individual user preferences. Experimental results on widely used cross-domain recommendation datasets demonstrate that our proposed model outperforms state-of-the-art methods, validating its effectiveness.

Domain-Level Disentanglement Framework Based on Information Enhancement for Cross-Domain Cold-Start Recommendation

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

Among various temporal knowledge graph (TKG) extrapolation methods, rule-based approaches stand out for their explicit rules and transparent reasoning paths. However, the vast search space for rule extraction poses a challenge in identifying high-quality logic rules. To navigate this challenge, we explore the use of generation models to generate new rules, thereby enriching our rule base and enhancing our reasoning capabilities. In this paper, we introduce LLM-DR, an innovative rule-based method for TKG extrapolation, which harnesses diffusion models to generate rules that are consistent with the distribution of the source data, while also amalgamating the rich semantic insights of Large Language Models (LLMs). Specifically, our LLM-DR generates semantically relevant and high-quality rules, employing conditional diffusion models in a classifier-free guidance fashion and refining them with LLM-based constraints. To assess rule efficacy, we meticulously design a coarse-to-fine evaluation strategy that initiates with coarse-grained filtering to eliminate less plausible rules and proceeds with fine-grained scoring to quantify the reliability of the retained. Extensive experiments demonstrate the promising capacity of our LLM-DR.

LLM-DR: A Novel LLM-Aided Diffusion Model for Rule Generation on Temporal Knowledge Graphs

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.

Downloads

Next from AAAI 2025

Combating Multimodal LLM Hallucination via Bottom-Up Holistic Reasoning

Similar lecture

Transformers Learn Hidden Dynamics when Trained to Predict Markov Decision Processes

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES