Automata Learning of Preferences over Temporal Logic Formulas from Pairwise Comparisons

📄 arXiv: 2505.18030v1 📥 PDF

作者: Hazhar Rahmani, Jie Fu

分类: cs.AI, cs.FL, cs.LG, eess.SY

发布日期: 2025-05-23

备注: 16 pages, 11 figures, technical report, submission under review

💡 一句话要点

提出基于偏好自动机学习的时间逻辑公式偏好推断方法

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 偏好学习 时间逻辑 有限自动机 机器人运动规划 决策系统 算法优化 机器学习

📋 核心要点

  1. 现有的偏好引导算法主要集中在命题逻辑公式上，缺乏对时间序列的有效处理，导致偏好推断的局限性。
  2. 本文提出了一种基于偏好确定有限自动机（PDFA）的模型，通过学习用户的时间目标及其预序关系来解决偏好推断问题。
  3. 通过对特征样本的分析，算法能够有效学习到最小PDFA，展示了在机器人运动规划问题中的应用效果。

📝 摘要（中文）

许多偏好引导算法考虑的是命题逻辑公式或具有不同属性的项目的偏好。在顺序决策中，用户的偏好可以是对可能结果的预序关系，每个结果都是事件的时间序列。本文考虑了一类偏好推断问题，其中用户的未知偏好由正则语言（时间序列集合）上的预序关系表示，称为时间目标。给定有限的成对比较样本，目标是学习时间目标集合及其预序关系。我们首先展示了时间目标上的偏好关系可以通过偏好确定有限自动机（PDFA）建模，该自动机在接受条件上增强了预序关系。偏好推断问题归结为学习PDFA，且确定是否存在小于给定整数k的PDFA的问题被证明是NP完全的。我们形式化了特征样本的属性，并开发了一种算法，保证在给定特征样本的情况下，学习到与真实PDFA等价的最小PDFA。

🔬 方法详解

问题定义：本文旨在解决用户偏好推断中的时间逻辑公式问题，现有方法在处理时间序列偏好时存在局限性，难以有效建模用户的复杂偏好关系。

核心思路：论文提出通过构建偏好确定有限自动机（PDFA）来表示用户的时间目标偏好，利用成对比较样本进行学习，从而推断出用户的偏好结构。

技术框架：整体方法包括三个主要阶段：首先，收集用户的成对比较样本；其次，构建PDFA模型以表示偏好关系；最后，应用算法从特征样本中学习到最小PDFA。

关键创新：最重要的技术创新在于将偏好关系与确定有限自动机结合，形成PDFA模型，使得偏好推断问题的求解变得更加系统化和高效。

关键设计：算法设计中考虑了特征样本的属性，确保在学习过程中能够找到与真实PDFA等价的最小模型，且在复杂度上进行了优化。具体的参数设置和损失函数设计尚未详细说明，待进一步研究。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，所提出的算法在学习PDFA方面表现出色，能够在给定特征样本的情况下，准确推断出最小PDFA，且在复杂度上优于传统方法，展示了显著的性能提升。

🎯 应用场景

该研究在机器人运动规划、智能决策系统等领域具有广泛的应用潜力。通过有效推断用户的时间偏好，可以提升系统的智能化水平，使其更好地满足用户需求，进而推动相关技术的发展与应用。

📄 摘要（原文）

Many preference elicitation algorithms consider preference over propositional logic formulas or items with different attributes. In sequential decision making, a user's preference can be a preorder over possible outcomes, each of which is a temporal sequence of events. This paper considers a class of preference inference problems where the user's unknown preference is represented by a preorder over regular languages (sets of temporal sequences), referred to as temporal goals. Given a finite set of pairwise comparisons between finite words, the objective is to learn both the set of temporal goals and the preorder over these goals. We first show that a preference relation over temporal goals can be modeled by a Preference Deterministic Finite Automaton (PDFA), which is a deterministic finite automaton augmented with a preorder over acceptance conditions. The problem of preference inference reduces to learning the PDFA. This problem is shown to be computationally challenging, with the problem of determining whether there exists a PDFA of size smaller than a given integer $k$, consistent with the sample, being NP-Complete. We formalize the properties of characteristic samples and develop an algorithm that guarantees to learn, given a characteristic sample, the minimal PDFA equivalent to the true PDFA from which the sample is drawn. We present the method through a running example and provide detailed analysis using a robotic motion planning problem.