論文の概要: A* shortest string decoding for non-idempotent semirings

• arxiv url: http://arxiv.org/abs/2204.07236v2
• Date: Thu, 25 Jan 2024 19:05:33 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-29 18:58:17.122375
• Title: A* shortest string decoding for non-idempotent semirings
• Title（参考訳）: 非べき半環に対する最短文字列復号法
• Authors: Kyle Gorman and Cyril Allauzen
• Abstract要約: 非等化半環上の重み付き非決定論的オートマトンに対する最短文字列を求めるアルゴリズムについて述べる。 DFAには指数関数的に多くの状態が存在するかもしれないが、このアルゴリズムは、決定が「オンザフライ」に実行された場合、少数の状態のみにアクセスする必要がある。
• 参考スコア（独自算出の注目度）: 6.646663925708157
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The single shortest path algorithm is undefined for weighted finite-state automata over non-idempotent semirings because such semirings do not guarantee the existence of a shortest path. However, in non-idempotent semirings admitting an order satisfying a monotonicity condition (such as the plus-times or log semirings), the notion of shortest string is well-defined. We describe an algorithm which finds the shortest string for a weighted non-deterministic automaton over such semirings using the backwards shortest distance of an equivalent deterministic automaton (DFA) as a heuristic for A* search performed over a companion idempotent semiring, which is proven to return the shortest string. While there may be exponentially more states in the DFA, this algorithm needs to visit only a small fraction of them if determinization is performed "on the fly".
• Abstract（参考訳）: 単一最短経路アルゴリズムは、最短経路の存在を保証しないため、非等方半環上の重み付き有限状態オートマトンに対して未定義である。 しかし、単調条件を満たす順序(プラス時間やログ半環など)を許容する非イデミネーション半環では、最短弦の概念はよく定義される。 本稿では,同値な決定論的オートマトン(DFA)の後方最短距離を用いて,重み付き非決定論的オートマトンに対する最短文字列を求めるアルゴリズムについて述べる。 DFAには指数関数的に多くの状態が存在するかもしれないが、このアルゴリズムは、決定が「オンザフライ」で実行される場合、少数の状態のみにアクセスする必要がある。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Pathfinding with Lazy Successor Generation [12.02023514105999]
  位置のみを付与し,エッジを暗黙的に定義するパスフィンディング問題について検討する。 単純な構造にもかかわらず、この問題は膨大な数の位置で非自明になる。 そこで我々は,LaCAS*アルゴリズムを提案する。これは,全ての後継を一度に生成するのではなく,探索が進むにつれて徐々に後継を生成できる。
  論文  参考訳（メタデータ） (2024-08-27T23:25:25Z)
• When can you trust feature selection? -- I: A condition-based analysis of LASSO and generalised hardness of approximation [49.1574468325115]
  近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。 不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。 無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
  論文  参考訳（メタデータ） (2023-12-18T18:29:01Z)
• On the success probability of the quantum algorithm for the short DLP [0.0]
  我々は,Ekeraa-Haastadのアルゴリズムが単一ランで短い$d$を回復する確率の低い境界を証明した。 私たちの限界によって、成功確率は、任意の短い$d$に対して1から1010$まで容易に押し付けられる。
  論文  参考訳（メタデータ） (2023-09-04T18:26:45Z)
• Efficient Semiring-Weighted Earley Parsing [71.77514972816347]
  本稿では,様々なスピードアップを伴うEarey (1970) の文脈自由構文解析アルゴリズムの,推論システムという形での参照記述を提供する。 私たちのプレゼンテーションには、Earey氏の$O(N3|GR|)$から、既知の最悪のランタイム改善が含まれています。 半重み付き推論への一般化を扱い、Stolcke (1995)のような文法を前処理して推論サイクルを排除し、さらに文プレフィックスの重みを計算するStolckeの手法を一般化する。
  論文  参考訳（メタデータ） (2023-07-06T13:33:59Z)
• Efficient Quantum State Synthesis with One Query [0.0]
  本稿では,古典的オラクルへの単一クエリ(重ね合わせ)を実現する時間類似量子アルゴリズムを提案する。 我々は、すべての$n$-qubit状態が、適切な有限ゲート集合上の$On/n)$-size回路によって0.01エラー内に構築可能であることを証明した。
  論文  参考訳（メタデータ） (2023-06-02T17:49:35Z)
• A Non-monotonic Self-terminating Language Model [62.93465126911921]
  本稿では,不完全復号アルゴリズムによる非終端列の問題に焦点をあてる。 まず、グリーディ探索、トップ$kのサンプリング、核サンプリングを含む不完全確率復号アルゴリズムを定義する。 次に,単調な終端確率の制約を緩和する非単調な自己終端言語モデルを提案する。
  論文  参考訳（メタデータ） (2022-10-03T00:28:44Z)
• Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
  本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。 文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。 我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
  論文  参考訳（メタデータ） (2021-06-01T19:51:55Z)
• Quantum Algorithm for Lexicographically Minimal String Rotation [5.905222176603487]
  語彙的最小弦回転(lexicographically minimal string rotation, LMSR)は、語彙的順序で弦のすべての回転の中で最小の回転を求める問題である。 LMSRのための$O(n3/4)$量子クエリアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-17T03:13:45Z)
• The Long, the Short and the Random [0.0]
  アルゴリズムは、サブ指数時間における満足な割り当ての正確なカウントを計算する。 このアルゴリズムは、すべてのCNF式が持つ優れた性質を使い、不満足な代入の個数をモノトーン部分形式の空間に関連付けている。
  論文  参考訳（メタデータ） (2020-11-03T12:00:07Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)

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

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