United States

Expressing negative conditions is a crucial feature of query languages for knowledge bases (KBs). Answering such queries over ontological KBs, however, is a very challenging task that becomes undecidable even for lightweight Description Logic (DL) ontologies. Such negative results hold even for Conjunctive Queries (CQs) equipped with basic forms negative conditions such as the the so-called &quot;safe&quot; negation or inequality atoms. One ontology language that is seemingly unaffected by these results is (the DL counterpart of) RDFS even if augmented it with disjointness axioms. Answering CQs with inequality atoms over such ontologies is known to be $\Pi^p_2$-complete, if the number of inequality atoms is unbounded, and NP-complete if we limit this number to one. Notably, these results leave open the cases of CQs with a fixed number greater than two of inequality atoms. Additionally, such a thorough analysis is missing for CQs with with safe negation.

In this paper, we embark in a refined analysis of the combined complexity of answering CQs with inequality atoms and safe negation over RDFS ontologies augmented with disjointness axioms. Firstly, we provide a unified $\Pi^p_2$ query answering algorithm for the general problem. Secondly, we confirm the generally held conjecture according to which answering CQs with two inequality atoms over such ontologies is already $\Pi^p_2$-hard. This result closes an important gap in the current literature and has an impact on the widely influential problem of query containment. We make such connection clear in the paper. Lastly, for CQs with safe negation, we prove a behavior similar to that of CQs with inequality atoms. Specifically, we show that answering CQs with at most one negative atom can be done in NP, while allowing at most two negative atoms is sufficient to obtain $\Pi^p_2$-hardness. To the best of our knowledge, this is the first result of this kind in the literature shedding light on the behavior of a fundamental query language.

AAAI 2025

Answering Conjunctive Queries with Safe Negation and Inequalities over RDFS Knowledge Bases

computational complexity of reasoning

Expressing negative conditions is a crucial feature of query languages for knowledge bases (KBs). Answering such queries over ontological KBs, however, is a very challenging task that becomes undecidable even for lightweight Description Logic (DL) ontologies. Such negative results hold even for Conjunctive Queries (CQs) equipped with basic forms negative conditions such as the the so-called "safe" negation or inequality atoms. One ontology language that is seemingly unaffected by these results is (the DL counterpart of) RDFS even if augmented it with disjointness axioms. Answering CQs with inequality atoms over such ontologies is known to be $\Pi^p_2$-complete, if the number of inequality atoms is unbounded, and NP-complete if we limit this number to one. Notably, these results leave open the cases of CQs with a fixed number greater than two of inequality atoms. Additionally, such a thorough analysis is missing for CQs with with safe negation.

In this paper, we embark in a refined analysis of the combined complexity of answering CQs with inequality atoms and safe negation over RDFS ontologies augmented with disjointness axioms. Firstly, we provide a unified $\Pi^p_2$ query answering algorithm for the general problem. Secondly, we confirm the generally held conjecture according to which answering CQs with two inequality atoms over such ontologies is already $\Pi^p_2$-hard. This result closes an important gap in the current literature and has an impact on the widely influential problem of query containment. We make such connection clear in the paper. Lastly, for CQs with safe negation, we prove a behavior similar to that of CQs with inequality atoms. Specifically, we show that answering CQs with at most one negative atom can be done in NP, while allowing at most two negative atoms is sufficient to obtain $\Pi^p_2$-hardness. To the best of our knowledge, this is the first result of this kind in the literature shedding light on the behavior of a fundamental query language.

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.



This paper investigates how hallucination rates in Large Language Models (LLMs) may be controlled via a symbolic data generation framework, and explores a fundamental relationship between the rate of certain mathematical errors and interventions. Specifically, we systematically generate data for a derivation generation task, and apply targeted interventions on prompts to perturb aspects such as the surface forms of symbols, equational tree structures, and mathematical context, and evaluate the effect of prompt interventions across a range of LLMs including fine-tuned T5 models, GPT, and others. Experiments suggest that T5-Large can outperform the few-shot performance of GPT-4T on various evaluation sets generated via the framework, however, an extensive evaluation based on human analysis, template-based error detection, and various text generation metrics, reveals fine-tuned model weaknesses beyond what the reference-based metrics singularly describe. We use these results to tie characteristic distributional footprints of interventions to the human evaluation of LLM derivation quality, potentially leading to significant control over fine-grained mathematical capabilities of language models with respect to specific types of errors.

Controlling Equational Reasoning in Large Language Models with Prompt Interventions

Question answering on free-form tables (a.k.a. TableQA) is a challenging task because of the flexible structure and the complex schema of tables. Recent studies use Large Language Models (LLMs) for this task, exploiting their capability in understanding the questions and  tabular data  which are typically given in natural language and contains many textual fields, respectively. While this approach has shown promising results, it overlooks the challenges brought by numerical values which are common in tabular data, while LLMs are known to struggle with such values.  We aim to address this issue and answer numerical questions. We propose a model named TabLaP that uses LLMs as a planner rather than an answer generator, exploiting LLMs' capability in multi-step reasoning while leaving the actual numerical calculations to a Python interpreter for accurate calculation. Recognizing the inaccurate nature of LLMs, we further make a first attempt to quantify the trustworthiness of the answers produced by TabLaP, such that users can use TabLaP in a regret-aware manner. Experimental results on two benchmark datasets show that TabLaP is substantially more accurate than the state-of-the-art models, improving the answer accuracy by 5.7% and 5.8% on the two datasets, respectively.

Accurate and Regret-Aware Numerical Problem Solver for Tabular Question Answering

Column Generation (CG) is an effective and iterative algorithm to solve large-scale linear programs (LP). During each CG iteration, new columns are added to improve the solution of the LP. Typically, CG greedily selects one column with the most negative reduced cost, which can be improved by adding more columns at once. However, selecting all columns with negative reduced costs would lead to the addition of redundant columns that do not improve the objective value. Therefore, selecting the appropriate columns to add is still an open problem and previous machine-learning-based approaches for CG only add a constant quantity of columns per iteration due to the state-space explosion problem. To address this, we propose Fast Family Column Generation (FFCG) -- a novel reinforcement-learning-based CG that selects a variable number of columns as needed in an iteration. Specifically, we formulate the column selection problem in CG as an MDP and design a reward metric that balances both the convergence speed and the number of redundant columns. In our experiments, FFCG converges faster on the common benchmarks and reduces the number of CG iterations by 77.1% for Cutting Stock Problem (CSP) and 84.8% for Vehicle Routing Problem with Time Windows (VRPTW), and a 71.4% reduction in computing time for CSP and 84.0% for VRPTW on average compared to several state-of-the-art baselines.

FFCG: Effective and Fast Family Column Generation for Solving Large-Scale Linear Program

Current collaborative perception methods often rely on fully annotated datasets, which can be expensive to obtain in practical situations. 
To reduce annotation costs, some works adopt sparsely supervised learning techniques and generate pseudo labels for the missing instances. However, these methods fail to achieve an optimal confidence threshold that harmonizes the quality and quantity of pseudo labels. To address this issue, we propose an end-to-end Collaborative perception Dual Teacher-Student framework (CoDTS), which employs adaptive complementary learning to produce both high-quality and high-quantity pseudo labels. Specifically, the Main Foreground Mining (MFM) module generates high-quality pseudo labels based on the prediction of the static teacher. Subsequently, the Supplement Foreground Mining (SFM) module ensures a balance between the quality and quantity of pseudo labels by adaptively identifying missing instances based on the prediction of the dynamic teacher. Additionally, the Neighbor Anchor Sampling (NAS) module is incorporated to enhance the representation of pseudo labels. To promote the adaptive complementary learning,  we implement a staged training strategy that trains the student and dynamic teacher in a mutually beneficial manner, enabling their continuous optimization. Extensive experiments conducted on V2X-Sim, OPV2V, DAIR-V2X and V2V4Real datasets demonstrate that the proposed CoDTS effectively ensures an optimal balance of pseudo labels in both quality and quantity, establishing a new state-of-the-art in sparsely supervised collaborative perception.

CoDTS: Enhancing Sparsely Supervised Collaborative Perception with a Dual Teacher-Student Framework

Symbolic Regression of Integer Sequences (SRIS) aims to discover precise mathematical formulas from integer sequences. The neural machine translation-based method of SRIS trains the model using randomly generated data, and directly utilizes the trained model for inference on target sequences. However, the method often fails to effectively generalize to the target sequence, since the randomly generated data can not adequately cover the distributions of target data, i.e., there are distribution differences between them. In this work, we propose a progressive self-learning (PSL) method to explicitly capture sequence-formula distributions of the target domain. Specifically, a source domain dataset is generated by incorporating initial terms of the target domain to reduce the sequence distribution gap between the source domain and the target domain. Meanwhile, a self-learning loop strategy is adopted to improve the ability of the model to capture the sequence-formula distribution of the target domain. In this strategy, a neural machine translation model is used to learn the mappings from sequences to formulas in an end-to-end fashion. Then, this model is employed to explore candidate formulas of the target sequence using beam search. After verifying these candidate formula correctness, some of them are retained as training data for the next learning. Experimental results on OEIS datasets demonstrate that the proposed method surpasses current state-of-the-art methods in accuracy, and also discovers new formulas.

Progressive Self-Learning for Domain Adaptation on Symbolic Regression of Integer Sequences

Enabling humanoid robots to perform long-horizon mobile manipulation planning in real-world environments based on embodied perception and comprehension abilities has been a longstanding challenge. 
With the recent rise of large language models (LLMs), there has been a notable increase in the development of LLM-based planners. These approaches either utilize human-provided textual representations of the real world or heavily depend on prompt engineering to extract such representations, lacking the capability to quantitatively understand the environment, such as determining the feasibility of manipulating objects.
To address these limitations, we present the Instruction-Augmented Long-Horizon Planning (IALP) system, a novel framework that employs LLMs to generate feasible and optimal actions based on real-time sensor feedback, including grounded knowledge of the environment, in a closed-loop interaction. Distinct from prior works, our approach augments user instructions into PDDL problems by leveraging both the abstract reasoning capabilities of LLMs and grounding mechanisms.
By conducting various real-world long-horizon tasks, each consisting of seven distinct manipulatory skills, our results demonstrate that the IALP system can efficiently solve these tasks with an average success rate exceeding 80\%.
Our proposed method can operate as a high-level planner for open-world long-horizon tasks, equipping robots with substantial autonomy in unstructured environments through the utilization of multi-modal sensor inputs.

Instruction-Augmented Long-Horizon Planning: Embedding Grounding Mechanisms in Embodied Mobile Manipulation

This paper presents an experiential learning pedagogy that teaches undergraduate business management infor-mation systems students hands-on AI skills through the lens of sustainability. The learning modules aim to em-power undergraduate business students to gain interest and confidence in AI knowledge, skills, and careers, to sharpen their higher order thinking abilities, and to help them gain a deeper understanding of sustainability is-sues. Students learn AI through developing chatbots that address pressing sustainability issues within their own communities. Results of the pilot study indicate that students have increased self-efficacy in AI, more positive attitudes towards AI learning and AI-related careers, en-hanced sustainability awareness, and more confidence in their ability to innovate.

Developing Chatbots for Sustainability: Experiential Learning in an Undergraduate Business Course

Developing competency in artificial intelligence is becoming increasingly crucial for computer science (CS) students at all levels of the CS curriculum. However, most previous research focuses on advanced CS courses, as traditional introductory courses provide limited opportunities to develop AI skills and knowledge. This paper introduces an introductory CS course where students learn computational thinking through computer vision, a sub-field of AI, as an application context. The course aims to achieve computational thinking outcomes alongside critical thinking outcomes that expose students to AI approaches and their societal implications. Through experiential activities such as individual projects and reading discussions, our course seeks to balance technical learning and critical thinking goals. Our evaluation, based on pre-and post-course surveys, shows an improved sense of belonging, self-efficacy, and AI ethics awareness among students. The results suggest that an AI-focused context can enhance participation and employability, student-selected projects support self-efficacy, and ethically grounded AI instruction can be effective for interdisciplinary audiences. Students' discussions on reading assignments demonstrated deep engagement with the complex challenges in today's AI landscape. Finally, we share insights on scaling such courses for larger cohorts and improving the learning experience for introductory CS students.

Computational Thinking with Computer Vision: Developing AI Competency in an Introductory Computer Science Course

This talk explores the challenge of customizing large-scale AI models, particularly generative AI, on cost-effective devices with limited memory and energy resources. Modern AI models demand substantial computational power, often relying on specialized hardware such as GPUs. To address this, the talk introduces compression-aware computing, a framework enabling AI models to recognize and adapt to their compressed states while preserving performance. Compression-aware computing integrates compression techniques like sparsification, quantization, and low-rank decomposition to enhance the efficiency and accuracy of AI models, broadening these models' accessibility across diverse devices. Additionally, this talk highlights one rationale of scalable and sustainable AI in advancing Alzheimer’s research by facilitating the analysis of large single-cell transcriptomics datasets for gene-gene interaction discovery.

Compression-Aware Computing for Scalable and Sustainable AI

Probabilistic inference is a fundamental challenge in machine learning, spanning tasks from approximate Bayesian inference to generative AI. In this talk, I will present theoretically-guaranteed scalable and efficient probabilistic inference with applications in Bayesian deep learning and generative modeling. First, I will introduce a general framework that leverages modern accelerators—specifically low-precision computation—to significantly accelerate inference while preserving accuracy. Next, I will present a new framework for efficient inference in discrete domains, using gradient information to achieve much more informed and directional exploration. Finally, I will showcase experimental results demonstrating the effectiveness of these methods across various ML tasks, including Bayesian neural networks, energy-based models, and large language models.

Answering Conjunctive Queries with Safe Negation and Inequalities over RDFS Knowledge Bases

Downloads

Next from AAAI 2025

Controlling Equational Reasoning in Large Language Models with Prompt Interventions

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES