論文の概要: Automata Learning of Preferences over Temporal Logic Formulas from Pairwise Comparisons

• arxiv url: http://arxiv.org/abs/2505.18030v1
• Date: Fri, 23 May 2025 15:35:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-26 18:08:34.197959
• Title: Automata Learning of Preferences over Temporal Logic Formulas from Pairwise Comparisons
• Title（参考訳）: ペアワイズ比較による時間論理式に対する選好の自動学習
• Authors: Hazhar Rahmani, Jie Fu,
• Abstract要約: 本稿では,ユーザの未知の嗜好が事前注文によって表現される選好推論問題のクラスについて考察する。 まず、時間的目標に対する嗜好関係は、優先決定論的有限オートマトンによってモデル化できることを示す。 そこで,本研究では,サンプルが描画される真のPDFAと同等のPDFAを,特徴サンプルから学習することを保証するアルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 28.920090391513
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.
• Abstract（参考訳）: 多くの選好推論アルゴリズムは、命題論理式や異なる属性を持つ項目よりも優先性を考慮する。 シーケンシャルな意思決定では、ユーザの好みは、イベントの時間的シーケンスである可能性のある結果よりも優先される。 本稿では,ユーザの未知の嗜好が,時間的目標と呼ばれる正規言語(時間的順序のセット)の事前順序で表現されるような,選好推論問題のクラスについて考察する。 有限語間の対比較の有限集合が与えられた場合、目的は時間的目標の集合とこれらの目標に対する事前順序の両方を学ぶことである。 まず,決定論的有限オートマトンであるPreference Deterministic Finite Automaton(PDFA)を用いて,時間的目標に対する嗜好関係をモデル化できることを示す。 選好推論の問題はPDFAの学習に還元される。 この問題は、与えられた整数$k$よりも小さいサイズのPDFAが存在し、サンプルと一致し、NP-Completeであるかどうかという問題によって、計算的に困難であることが示されている。 特徴サンプルの特性を定式化し,特徴サンプルが描画される真のPDFAと同等の最小限のPDFAを学習することを保証するアルゴリズムを開発する。 本稿では,ロボットの動作計画問題を用いて,動作例を用いて詳細な解析を行う。

関連論文リスト

• FastGAS: Fast Graph-based Annotation Selection for In-Context Learning [53.17606395275021]
  インコンテキスト学習(ICL)は、大規模言語モデル(LLM)に対して、一連のトレーニングインスタンスをプロンプトとして使用することにより、新しいタスクに対処する権限を与える。 既存の手法では、アノテーションのラベルなし例のサブセットを選択する方法が提案されている。 本稿では,高品質なインスタンスを効率的に識別するグラフベースの選択手法であるFastGASを提案する。
  論文  参考訳（メタデータ） (2024-06-06T04:05:54Z)
• Preference-Based Planning in Stochastic Environments: From Partially-Ordered Temporal Goals to Most Preferred Policies [25.731912021122287]
  マルコフ決定過程としてモデル化されたシステムは、時間的に拡張された一連の目標に対して部分的に順序づけられた選好を考慮に入れている。 部分的に順序づけられた選好を計画するために、時間的目標に対する選好をMDPの政策に対する選好にマッピングする順序理論を導入する。 順序付けの下で最も好まれるポリシーは、MDP内の有限経路上の非支配確率分布を誘導する。
  論文  参考訳（メタデータ） (2024-03-27T02:46:09Z)
• Learning to Select and Rank from Choice-Based Feedback: A Simple Nested Approach [10.293894471295205]
  本研究では、動的アソートによる選択に基づくフィードバックから学習する際のランク付けと選択の問題について検討する。 両学習目標に対して,新しい,シンプルなアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-07-13T05:05:30Z)
• Probabilistic Planning with Prioritized Preferences over Temporal Logic Objectives [26.180359884973566]
  マルコフ決定過程(MDP)をモデルとした確率的環境における時間的計画に関する研究 本稿では,有限トレース上の線形時間論理を優先的に定性的選択する新しい仕様言語を提案する。 ユーザの好みに応じて期待される不満のスコアを最小化する最適ポリシーを定式化し、解き明かす。
  論文  参考訳（メタデータ） (2023-04-23T13:03:27Z)
• Probabilistic Planning with Partially Ordered Preferences over Temporal Goals [22.77805882908817]
  マルコフ決定過程(MDP)における計画計画について,時間的拡張目標よりも優先的に検討した。 本稿では、時間的に拡張された目標に対するユーザの好みを特定するために、決定論的有限オートマトンの一種である選好DFAを導入する。 構築された多目的MDPにおいて、選好仕様を前提とした弱確率的非支配ポリシーが最適であることを示す。
  論文  参考訳（メタデータ） (2022-09-25T17:13:24Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。 我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
  論文  参考訳（メタデータ） (2020-04-23T05:00:21Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。 品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
  論文  参考訳（メタデータ） (2020-02-26T16:19:09Z)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。 最小クラスタ回復誤差率のアルゴリズムを考案する。 適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2019-10-14T09:18:26Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。