論文の概要: Efficient Multiple Constraint Acquisition
- arxiv url: http://arxiv.org/abs/2109.05920v1
- Date: Mon, 13 Sep 2021 12:42:16 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-14 23:34:34.463367
- Title: Efficient Multiple Constraint Acquisition
- Title(参考訳): 効率的な多重制約獲得
- Authors: Dimosthenis C. Tsouros and Kostas Stergiou
- Abstract要約: QuAcqやMultiAcqのような制約獲得システムは、専門家でないユーザが自身の問題を制約ネットワークとしてモデル化するのを支援できる。
本稿では,クエリ数を大幅に削減することで,制約獲得の性能を高める手法を提案する。
そして、我々はクエリ生成に注意を向けます。
- 参考スコア(独自算出の注目度): 1.3706331473063877
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Constraint acquisition systems such as QuAcq and MultiAcq can assist
non-expert users to model their problems as constraint networks by classifying
(partial) examples as positive or negative. For each negative example, the
former focuses on one constraint of the target network, while the latter can
learn a maximum number of constraints. Two bottlenecks of the acquisition
process where both these algorithms encounter problems are the large number of
queries required to reach convergence, and the high cpu times needed to
generate queries, especially near convergence. In this paper we propose
algorithmic and heuristic methods to deal with both these issues. We first
describe an algorithm, called MQuAcq, that blends the main idea of MultiAcq
into QuAcq resulting in a method that learns as many constraints as MultiAcq
does after a negative example, but with a lower complexity. A detailed
theoretical analysis of the proposed algorithm is also presented. %We also
present a technique that boosts the performance of constraint acquisition by
reducing the number of queries significantly. Then we turn our attention to
query generation which is a significant but rather overlooked part of the
acquisition process. We describe %in detail how query generation in a typical
constraint acquisition system operates, and we propose heuristics for improving
its efficiency. Experiments from various domains demonstrate that our resulting
algorithm that integrates all the new techniques does not only generate
considerably fewer queries than QuAcq and MultiAcq, but it is also by far
faster than both of them, in average query generation time as well as in total
run time, and also largely alleviates the premature convergence problem.
- Abstract(参考訳): quacqやmultiacqといった制約取得システムは、(部分的な)例を正か負かに分類することで、非専門家のユーザが自身の問題を制約ネットワークとしてモデル化するのに役立つ。
負の例では、前者はターゲットネットワークの1つの制約に焦点を当て、後者は最大数の制約を学ぶことができる。
両方のアルゴリズムが問題に遭遇する買収プロセスのボトルネックは、収束に達するのに必要な大量のクエリと、特に収束に近いクエリを生成するのに必要なcpu時間である。
本稿では,これらの問題に対処するアルゴリズムとヒューリスティックな手法を提案する。
最初に、MQuAcqと呼ばれるアルゴリズムを記述し、MQuAcqの主アイデアをQuAcqにブレンドすることで、MultiAcqが負の例の後に行うような多くの制約を学習するが、複雑さは小さくなる。
また,提案アルゴリズムの詳細な理論的解析を行った。
また,クエリ数を大幅に削減することで,制約獲得の性能を向上させる手法を提案する。
次に、買収プロセスにおいて重要ではあるが見落とされた部分であるクエリ生成に注意を向ける。
本稿では,典型的な制約獲得システムにおけるクエリ生成の動作を詳細に記述し,その効率向上のためのヒューリスティックスを提案する。
様々な領域からの実験により、新しい手法を全て統合したアルゴリズムはQuAcqやMultiAcqよりもはるかに少ないクエリを生成するだけでなく、平均クエリ生成時間と総実行時間において、両者よりもはるかに高速であり、また早めの収束問題をほとんど軽減していることが示された。
関連論文リスト
- Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。
赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
論文 参考訳(メタデータ) (2024-06-21T05:57:08Z) - Adaptive-RAG: Learning to Adapt Retrieval-Augmented Large Language Models through Question Complexity [59.57065228857247]
Retrieval-augmented Large Language Models (LLMs) は、質問回答(QA)のようなタスクにおける応答精度を高めるための有望なアプローチとして登場した。
本稿では,クエリの複雑さに基づいて,LLMの最適戦略を動的に選択できる適応型QAフレームワークを提案する。
オープンドメインのQAデータセットを用いて、複数のクエリの複雑さを網羅し、QAシステムの全体的な効率性と精度を高めることを示す。
論文 参考訳(メタデータ) (2024-03-21T13:52:30Z) - Query-Efficient Correlation Clustering with Noisy Oracle [17.11782578276788]
共同マルチアーマッドバンド(PE-CMAB)における純粋探索のパラダイムに根ざしたオンライン学習問題の2つの新しい定式化を導入する。
我々は,サンプリング戦略と古典近似アルゴリズムを組み合わせるアルゴリズムを設計し,それらの理論的保証について検討する。
本研究は, PE-CMABの場合のクラスタリング時アルゴリズムの最初の例であり, 基礎となるオフライン最適化問題はNP-hardである。
論文 参考訳(メタデータ) (2024-02-02T13:31:24Z) - Learning to Learn in Interactive Constraint Acquisition [7.741303298648302]
制約獲得(CA:Constraint Acquisition)では、モデルを自動的に学習することでユーザを支援することが目標である。
アクティブCAでは、クエリを対話的にユーザにポストすることでこれを行う。
本稿では、確率論的分類モデルを用いて対話型CAを誘導し、より有望なクエリを生成することを提案する。
論文 参考訳(メタデータ) (2023-12-17T19:12:33Z) - Guided Bottom-Up Interactive Constraint Acquisition [10.552990258277434]
制約獲得システム(Constraint Acquisition, CA)は制約満足度問題のモデル化を支援する。
現在の対話型CAアルゴリズムは、少なくとも2つの大きなボトルネックに悩まされている。
本稿では,CAの効率を向上する2つの新しい手法を提案する。
論文 参考訳(メタデータ) (2023-07-12T12:25:37Z) - Lifting Symmetry Breaking Constraints with Inductive Logic Programming [2.036811219647753]
我々は、Symmetry Breaking Constraintsを解釈可能な一階制約の集合に引き上げる、Answer Set Programmingのための新しいモデル指向のアプローチを導入する。
実験は、我々のフレームワークがインスタンス固有のSBCから一般的な制約を学習できることを実証する。
論文 参考訳(メタデータ) (2021-12-22T11:27:48Z) - Global Optimization of Objective Functions Represented by ReLU Networks [77.55969359556032]
ニューラルネットワークは複雑で非敵対的な関数を学ぶことができ、安全クリティカルな文脈でそれらの正しい振る舞いを保証することは困難である。
ネットワーク内の障害を見つけるための多くのアプローチ(例えば、敵の例)があるが、これらは障害の欠如を保証できない。
本稿では,最適化プロセスを検証手順に統合し,本手法よりも優れた性能を実現する手法を提案する。
論文 参考訳(メタデータ) (2020-10-07T08:19:48Z) - An Efficient Algorithm for Cooperative Semi-Bandits [0.0]
本稿では,有名なFollow The Perturbed Leaderアルゴリズムの協調バージョンであるCoop-FTPLを紹介する。
T 時間ステップ後のアルゴリズムの期待された後悔は QT log(k)(k$alpha$ 1 /Q + m) であり、Q は総アクティベーション確率質量である。
論文 参考訳(メタデータ) (2020-10-05T07:08:26Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。
都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文 参考訳(メタデータ) (2020-05-27T01:10:41Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳(メタデータ) (2020-05-09T02:48:23Z) - Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。
最小クラスタ回復誤差率のアルゴリズムを考案する。
適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
論文 参考訳(メタデータ) (2019-10-14T09:18:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。