論文の概要: Developing a Totally Unimodular Linear Program for Optimal Conformance Checking: When and Why It Complements A*

• arxiv url: http://arxiv.org/abs/2605.26938v1
• Date: Tue, 26 May 2026 12:30:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-27 17:51:42.085258
• Title: Developing a Totally Unimodular Linear Program for Optimal Conformance Checking: When and Why It Complements A*
• Title（参考訳）: 最適コンフォーマンスチェックのための完全一様線形プログラムの開発:A*を補完する時期と理由
• Authors: Izack Cohen,
• Abstract要約: 本稿では、完全一様線形プログラム(LP)としてのアライメントに基づく整合性チェックの再構成を提案する。 基礎となるネットワークフロー構造を利用することで、LP緩和による最適極点解が保証される。 両手法を併用した単純なアルゴリズム選択ガイドラインを導出し, 平均実行時節約率38.6%, 選択精度96%を実現した。
• 参考スコア（独自算出の注目度）: 0.324890820102255
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Alignment-based conformance checking is the state-of-the-art approach for comparing observed process executions with normative process models. The standard exact solution relies on an A*-based heuristic search, which can exhibit exponential runtime in the presence of long traces or substantial deviations. This paper introduces a reformulation of alignment-based conformance checking as a totally unimodular linear program (LP) defined on the reachability graph of the synchronous product. By exploiting the underlying network-flow structure, the proposed formulation guarantees the existence of an integral optimal extreme-point solution through LP relaxation, thereby avoiding the combinatorial overhead associated with integer variables and branch-and-bound search. We conduct an extensive empirical evaluation on more than 2.1 million conformance checking instances derived from real-world and synthetic benchmark datasets. The results show that A* and the LP approach exhibit complementary performance characteristics: the former performs best on short, well-conforming traces, while the LP formulation provides substantial speedups for longer traces with deviations, precisely where conformance checking is most informative. Based on these findings, we derive simple algorithm-selection guidelines that combine both approaches, achieving average runtime savings of 38.6% with 96% selection accuracy compared to always using A*.
• Abstract（参考訳）: アライメントベースの適合性チェックは、観察されたプロセスの実行と規範的なプロセスモデルを比較するための最先端のアプローチである。 標準的な正確な解法はA*に基づくヒューリスティック探索に依存しており、長いトレースや実質的な偏差の存在下で指数的ランタイムを示すことができる。 本稿では、同期積の到達可能性グラフ上に定義された完全一様線形プログラム(LP)としてアライメントに基づく整合性チェックの再構成を提案する。 基礎となるネットワークフロー構造を利用することで、LP緩和による積分最適極点解の存在を保証し、整数変数と分岐境界探索に付随する組合せオーバーヘッドを回避する。 我々は、実世界および合成ベンチマークデータセットから得られた2100万以上の適合性チェックインスタンスについて、広範な実証評価を行う。 その結果, A* と LP のアプローチは相補的な性能特性を示し, 前者は短く, 整合性のあるトレースに対して, LP の定式化は, 整合性チェックが最も有意な位置にある長いトレースに対して, 相当なスピードアップを提供することがわかった。 これらの結果から,A*を常用する場合と比較して,平均実行時節約率38.6%,選択精度96%を達成できる,単純なアルゴリズム選択ガイドラインを導出した。

関連論文リスト

• Self-Improving In-Context Learning [3.9202238580555417]
  本稿では,短時間の即時テストの埋め込みを最適化し,文脈内学習を改善することを提案する。 我々はこの信号を有界自己監督キャリブレーション法として定式化する。 ICLタスクの包括的なスイート全体において、提案されたキャリブレーションはベースモデルを改善したり、一致させたりすることで、ほとんどのタスクにおける分類固有のベースラインを一貫して上回る。
  論文  参考訳（メタデータ） (2026-05-22T03:01:34Z)
• Direct Preference Optimization with Rating Information: Practical Algorithms and Provable Gains [67.71020482405343]
  評価ギャップの形で追加情報を活用するアルゴリズムを設計する方法について検討する。 精度の高いレーティングギャップ情報が存在する場合,DPOよりも高速な統計的レートを実現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-01-31T08:38:21Z)
• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  ROC曲線の下の領域(AUC)は、クラス不均衡と決定制約の両方を持つ実世界のシナリオにおける重要な評価指標である。 PAUC最適化の近似ギャップを埋めるために,2つの簡単なインスタンス単位のミニマックス修正を提案する。 得られたアルゴリズムは、サンプルサイズと典型的な一方方向と双方向のPAUCに対して$O(-2/3)$の収束率の線形パーイテレーション計算複雑性を享受する。
  論文  参考訳（メタデータ） (2025-12-01T02:52:33Z)
• Conformance Checking for Less: Efficient Conformance Checking for Long Event Sequences [3.3170150440851485]
  ConLESは、長いイベントシーケンスのスライディングウィンドウ適合性チェックアプローチである。 トレースを管理可能なサブトレースに分割し、それぞれが期待する振る舞いと整合する。 トレースとプロセスモデルの両方の構造特性をキャプチャするグローバル情報を使用します。
  論文  参考訳（メタデータ） (2025-03-09T16:42:59Z)
• A Scalable and Near-Optimal Conformance Checking Approach for Long Traces [3.3170150440851485]
  プロセスマイニングにおける重要なタスクであるコンフォーマルティチェックは、最適なアライメントを見つけるという指数関数的な複雑さのため、計算不能になる可能性がある。 本稿では,これらの拡張性に対処する新しいスライディングウインドウ手法を提案する。 トレースを管理可能なサブトレースに分割し,プロセスモデルと反復的に整列することにより,検索空間を大幅に削減する。
  論文  参考訳（メタデータ） (2024-06-08T11:04:42Z)
• Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems [62.83783246648714]
  目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。 アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
  論文  参考訳（メタデータ） (2022-11-29T05:52:17Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。 既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。 本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
  論文  参考訳（メタデータ） (2022-10-08T08:26:22Z)
• Fast and Robust Certifiable Estimation of the Relative Pose Between Two Calibrated Cameras [0.0]
  カメラの相対Pose問題(RPp)は、2つのカメラ間のペアワイズ回転のセットを与えられた相対方向変換(構成)を目指しています。 本稿では,検出された最適解の比率を高めるための証明書群について紹介する。 提案手法が高速でロバストなポーズ推定を実現することを,合成および実データにより証明する。
  論文  参考訳（メタデータ） (2021-01-21T10:07:05Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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