Fugu-MT 論文翻訳(概要): A dynamic programming algorithm for span-based nested named-entity recognition in O(n^2)

論文の概要: A dynamic programming algorithm for span-based nested named-entity recognition in O(n^2)

arxiv url: http://arxiv.org/abs/2210.04738v2
Date: Fri, 26 May 2023 17:19:34 GMT
ステータス: 処理完了
システム内更新日: 2023-05-29 23:46:14.306776
Title: A dynamic programming algorithm for span-based nested named-entity recognition in O(n^2)
Title（参考訳）: O(n^2)におけるスパンベースネスト付きネスト値認識のための動的プログラミングアルゴリズム
Authors: Caio Corro
Abstract要約: 探索空間に補足的構造制約を加えることで、ネストされたNERは2次時間複雑性を持ち、これは非ネストの場合と同じ複雑さを持つことを示す。提案アルゴリズムは、3つの標準英語ベンチマークの大部分をカバーし、同等の実験結果を提供する。
参考スコア（独自算出の注目度）: 5.228711636020665
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Span-based nested named-entity recognition (NER) has a cubic-time complexity using a variant of the CYK algorithm. We show that by adding a supplementary structural constraint on the search space, nested NER has a quadratic-time complexity, that is the same asymptotic complexity than the non-nested case. The proposed algorithm covers a large part of three standard English benchmarks and delivers comparable experimental results.
Abstract（参考訳）: Span-based nested named-entity recognition (NER) はCYKアルゴリズムの変種を用いた3次時間複雑性を持つ。探索空間に補足的構造制約を加えることで、ネストされたNERは2次時間複雑性を持ち、これは非ネストの場合と同じ漸近的複雑性を持つことを示す。提案アルゴリズムは3つの標準英語ベンチマークの大部分をカバーし,同等の実験結果を提供する。

関連論文リスト

Moderate Exponential-time Quantum Dynamic Programming Across the Subsets for Scheduling Problems [0.20971479389679337]
量子最小探索と動的プログラミングの組み合わせは、NPハード問題の複雑さを改善するのに特に効果的であることが証明されている。本稿では,NP-ハード単一マシンスケジューリング問題に対して,そのような改善を実現する境界付きエラーハイブリッドアルゴリズムを提案する。我々のアルゴリズムは、よく知られた古典的アルゴリズムと比較して指数関数的な部分の複雑さを減らし、時には擬似多項式因子のコストがかかる。
論文参考訳（メタデータ） (2024-08-11T10:28:49Z)
S2F-NER: Exploring Sequence-to-Forest Generation for Complex Entity Recognition [47.714230389689064]
本研究では、フォレストデコーダを介して文中のエンティティを直接抽出できる新しいシーケンス・ツー・フォレスト生成パラダイムS2F-NERを提案する。具体的には,各樹木の最大深度が3である森林において,各樹木の各経路を自己回帰的に生成する。このパラダイムに基づいて、我々のモデルは露出バイアス問題をエレガントに緩和し、Seq2Seqの単純さを維持することができる。
論文参考訳（メタデータ） (2023-10-29T09:09:10Z)
First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。これらのアルゴリズムに対する漸近的理論的保証を提供する。
論文参考訳（メタデータ） (2022-04-07T00:11:05Z)
Quantum algorithm for Neighborhood Preserving Embedding [4.248054546466641]
NPE(Norborhood Preserving Embedding)は重要な線形次元低減技術である。 LiangらはNPEのための変分量子アルゴリズム(VQA)を提案した。 NPEのための完全量子アルゴリズムを提案し、3つのサブアルゴリズムを再設計する。
論文参考訳（メタデータ） (2021-10-22T00:55:40Z)
Generalization in portfolio-based algorithm selection [97.74604695303285]
ポートフォリオベースのアルゴリズム選択に関する最初の証明可能な保証を提供する。ポートフォリオが大きければ、非常に単純なアルゴリズムセレクタであっても、過剰適合は避けられないことを示す。
論文参考訳（メタデータ） (2020-12-24T16:33:17Z)
A Constraint-Based Algorithm for the Structural Learning of Continuous-Time Bayesian Networks [70.88503833248159]
連続時間ベイズネットワークの構造を学習するための制約に基づく最初のアルゴリズムを提案する。我々は,条件付き独立性を確立するために提案した,異なる統計的テストと基礎となる仮説について論じる。
論文参考訳（メタデータ） (2020-07-07T07:34:09Z)
Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity [58.70807593332932]
近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
論文参考訳（メタデータ） (2020-06-08T09:25:47Z)
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)
A Heuristic Based on Randomized Greedy Algorithms for the Clustered Shortest-Path Tree Problem [2.099922236065961]
本稿では, RGA とショート・パス・ツリー・アルゴリズム (SPTA) の主な特徴を組み合わせたクラスタ・ショート・パス・ツリー問題 (CluSPT) を扱うアルゴリズムを提案する。提案アルゴリズムの性能を評価するため,ユークリッドベンチマークが選択される。
論文参考訳（メタデータ） (2020-05-05T08:34:58Z)

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