論文の概要: Sequence graphs realizations and ambiguity in language models

• arxiv url: http://arxiv.org/abs/2402.08830v2
• Date: Fri, 11 Jul 2025 00:42:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-14 18:03:54.02279
• Title: Sequence graphs realizations and ambiguity in language models
• Title（参考訳）: 言語モデルにおけるシーケンスグラフの実現とあいまいさ
• Authors: Sammy Khalife, Yann Ponty, Laurent Bulteau,
• Abstract要約: いくつかの人気のある言語モデルは、単語の袋として入力テキスト$x$でローカルコンテキストを表す。 いくつかは曖昧で、列としていくつかの実現を認めたり、あるものは実現を認めなかったりする。 本稿では,シーケンスグラフの実現可能性とあいまいさについて,アルゴリズムの観点から検討する。
• 参考スコア（独自算出の注目度）: 1.3108652488669736
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Several popular language models represent local contexts in an input text $x$ as bags of words. Such representations are naturally encoded by a sequence graph whose vertices are the distinct words occurring in $x$, with edges representing the (ordered) co-occurrence of two words within a sliding window of size $w$. However, this compressed representation is not generally bijective: some may be ambiguous, admitting several realizations as a sequence, while others may not admit any realization. In this paper, we study the realizability and ambiguity of sequence graphs from a combinatorial and algorithmic point of view. We consider the existence and enumeration of realizations of a sequence graph under multiple settings: window size $w$, presence/absence of graph orientation, and presence/absence of weights (multiplicities). When $w=2$, we provide polynomial time algorithms for realizability and enumeration in all cases except the undirected/weighted setting, where we show the $\#$P-hardness of enumeration. For $w \ge 3$, we prove the hardness of all variants, even when $w$ is considered as a constant, with the notable exception of the undirected unweighted case for which we propose XP algorithms for both problems, tight due to a corresponding $W[1]-$hardness result. We conclude with an integer program formulation to solve the realizability problem, and a dynamic programming algorithm to solve the enumeration problem in instances of moderate sizes. This work leaves open the membership to NP of both problems, a non-trivial question due to the existence of minimum realizations having size exponential on the instance encoding.
• Abstract（参考訳）: いくつかの人気のある言語モデルは、単語の袋として入力テキスト$x$でローカルコンテキストを表す。 このような表現は、頂点が$x$の異なる単語であり、エッジが$w$のスライドウィンドウ内の2つの単語の(順序付けられた)共起を表すシーケンスグラフによって、自然に符号化される。 しかし、この圧縮された表現は一般に単射的ではない: いくつかは曖昧であり、列としていくつかの実現を認めたり、あるものはいかなる実現も認めなかったりする。 本稿では,組合せとアルゴリズムの観点から,シーケンスグラフの実現可能性とあいまいさについて検討する。 複数の設定でシーケンスグラフの存在と列挙を考える:ウィンドウサイズ$w$、グラフ配向の存在/存在、重み(多重性)の存在/存在。 w=2$のとき、無向/重み付けの設定を除いて、すべてのケースで実現可能性および列挙のための多項式時間アルゴリズムを提供し、ここでは、列挙の$$$#$P-hardnessを示す。 for $w \ge 3$, we prove the hardness of all variants, when $w$ is considered a constant, and the noted exception of the undirected unweighted case that we propose XP algorithm for both problems, tight due with a $W[1]-$hardness result。 本稿では,実現可能性問題を解く整数プログラムの定式化と,中間サイズの場合の列挙問題の解法を動的プログラミングアルゴリズムで行う。 このことは、インスタンスエンコーディングに指数関数的な大きさを持つ最小化の存在による非自明な問題である。

関連論文リスト

• A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition [79.18735797001183]
  解法 (Stampacchia) 変分不等式 (SVIs) は最適化の中心にある基礎的な問題である。 楕円体の中心から勾配降下ステップを踏み出した後に超平面が得られる楕円体アルゴリズムの新たな変種を導入する。 主な成果のいくつかの拡張と新しい応用を提供しています。
  論文  参考訳（メタデータ） (2025-04-04T13:24:41Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Efficient Solution of Point-Line Absolute Pose [52.775981113238046]
  点や線である可能性のある特徴間の3D--2D対応に基づくポーズ推定の特定の問題を再検討する。 得られた解法は数値的に安定かつ高速であることを示す。
  論文  参考訳（メタデータ） (2024-04-25T12:09:16Z)
• SAT-Based Algorithms for Regular Graph Pattern Matching [40.86962847131912]
  複素構造特性をチェックできるグラフ同型を一般化する。 この仕様は正規表現にインスパイアされた特殊なグラフである正規グラフパターン(ReGaP)の形で与えられる。 本稿では、対象グラフが所定のReGaPと一致するかどうかをチェックするSATベースのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-15T18:12:44Z)
• The Complexity of Envy-Free Graph Cutting [44.58084909019557]
  我々は,異なる選好を持つエージェント間で,不均一なリソースの集合を公平に分割する問題を考察する。 我々は、リソースが連結グラフのエッジに対応するような設定に集中し、すべてのエージェントがこのグラフの連結片を割り当てなければならない。 問題はNP完全であり、エージェントの数とグラフ内のエッジの数という2つの自然な複雑さの尺度に関して、その複雑さを分析する。
  論文  参考訳（メタデータ） (2023-12-12T07:54:30Z)
• Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions [49.69852011882769]
  一般化線形モデル (GLMs) の重畳雑音の存在下での回帰問題に対する最初のアルゴリズムを示す。 本稿では,この問題に最も一般的な分布非依存設定で対処するアルゴリズムを提案する。 これは、サンプルの半分以上を任意に破損させる難聴ノイズを持つGLMレグレッションに対する最初の新しいアルゴリズムによる結果である。
  論文  参考訳（メタデータ） (2023-09-20T21:41:59Z)
• Fast Maximum $k$-Plex Algorithms Parameterized by Small Degeneracy Gaps [30.06993761032835]
  最大$k$-plex問題は、グラフマイニングやコミュニティ検出といったアプリケーションでは重要であるが、計算的に困難である。 我々は、入力グラフのサイズで最悪のランニング時間を持ち、$g_k(G)$で指数関数的な$g_k(G)$でパラメータ化された正確なアルゴリズムを示す。 我々はさらに議論を、より小さなパラメータ$cg_k(G)$、コミュニティの世代境界と最大$k$-plexのサイズの間のギャップにまで拡張します。
  論文  参考訳（メタデータ） (2023-06-23T01:28:24Z)
• Discrete Graph Auto-Encoder [52.50288418639075]
  離散グラフオートエンコーダ(DGAE)という新しいフレームワークを導入する。 まず、置換同変オートエンコーダを用いてグラフを離散潜在ノード表現の集合に変換する。 2番目のステップでは、離散潜在表現の集合をソートし、特別に設計された自己回帰モデルを用いてそれらの分布を学習する。
  論文  参考訳（メタデータ） (2023-06-13T12:40:39Z)
• Compositional Generalization without Trees using Multiset Tagging and Latent Permutations [121.37328648951993]
  まず、各入力トークンに複数の出力トークンをタグ付けします。 次に、新しいパラメータ化法と置換予測法を用いて、トークンを出力シーケンスに配置する。 我々のモデルは、事前訓練されたセq2seqモデルと、現実的なセマンティック解析タスクに関する先行研究より優れている。
  論文  参考訳（メタデータ） (2023-05-26T14:09:35Z)
• Linear-Time Modeling of Linguistic Structure: An Order-Theoretic Perspective [97.57162770792182]
  文字列内のトークンのペア間の関係をモデル化するタスクは、自然言語を理解する上で不可欠な部分である。 これらの徹底的な比較は避けられ、さらに、トークン間の関係を文字列上の部分順序としてキャストすることで、複雑さを線形に減らすことができる。 提案手法は,文字列中の各トークンの実際の数を並列に予測し,それに従ってトークンをソートすることで,文字列内のトークンの総順序を決定する。
  論文  参考訳（メタデータ） (2023-05-24T11:47:35Z)
• Can Language Models Solve Graph Problems in Natural Language? [51.28850846990929]
  大型言語モデル (LLM) は暗黙的なグラフィカル構造を持つ様々なタスクに採用されている。 自然言語をシミュレーションするグラフベース問題解決のベンチマークであるNLGraphを提案する。
  論文  参考訳（メタデータ） (2023-05-17T08:29:21Z)
• Non-Autoregressive Math Word Problem Solver with Unified Tree Structure [62.869481432887106]
  我々は,この問題を解析し,統一木に基づいて解表現を推論する,新しい非自己回帰解法であるtextitMWP-NAS を提案する。 Math23K と MAWPS を用いた大規模な実験の結果,提案したMWP-NAS の有効性が示された。
  論文  参考訳（メタデータ） (2023-05-08T08:53:37Z)
• The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits [0.0]
  量子回路におけるパターンマッチングを同時に行うアルゴリズムを提案する。 量子回路の場合、量子ビットの最大数から得られる境界を表現することができる。
  論文  参考訳（メタデータ） (2023-02-13T22:09:02Z)
• Casting graph isomorphism as a point set registration problem using a simplex embedding and sampling [0.0]
  グラフは、単純な埋め込みとサンプリングを用いて、十分な次元でセットされた点として表すことができる。 それらの同型は、グラフの点集合形式の間の完全登録の存在に対応する。 等値類に関する関連する考えは、グラフの正準化がグラフ同型問題に取り組む上で重要なツールであることを示している。
  論文  参考訳（メタデータ） (2021-11-15T12:16:21Z)
• Inferring Hidden Structures in Random Graphs [13.031167737538881]
  本研究では,ランダムなグラフ上に植えられた群集群集の検出と復元の2つの推論問題について検討する。 我々は、パラメータ $(n,k,q)$ や $Gamma_k$ の特定の性質の観点から、構造を検出・復元するための下限を導出し、これらの下限を達成するための計算学的に最適なアルゴリズムを示す。
  論文  参考訳（メタデータ） (2021-10-05T09:39:51Z)
• The Generalized Mean Densest Subgraph Problem [30.33731479053404]
  1つのパラメータ$p$でパラメータ化された、高密度なサブグラフ対象の新しいファミリーを導入する。 我々の目的は、標準の高密度部分グラフ問題と特別な場合の最大$k$-coreの両方をキャプチャする。 我々の研究の大きな貢献は、理論と実践の両方において、密接な部分グラフに対する様々な種類の剥離アルゴリズムの性能を分析することである。
  論文  参考訳（メタデータ） (2021-06-02T02:58:35Z)
• Random Graph Matching with Improved Noise Robustness [2.294014185517203]
  本稿では確率モデルに基づくグラフマッチングの新しいアルゴリズムを提案する。 我々のアルゴリズムは、$alpha le 1 / (log log n)C$ のとき、その基礎となるマッチングを高い確率で復元する。 これにより、以前の作業で達成された条件 $alpha le 1 / (log n)C$ が改善される。
  論文  参考訳（メタデータ） (2021-01-28T02:39:27Z)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。 エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。 textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
  論文  参考訳（メタデータ） (2020-12-10T15:40:07Z)
• Evolving test instances of the Hamiltonian completion problem [0.7734726150561086]
  本稿では,進化的アルゴリズムを用いて多様なインスタンス群を生成する手法を提案する。 得られたグラフを分析し、どの属性がアルゴリズムのパフォーマンスに最も関連しているかについて重要な洞察を得る。
  論文  参考訳（メタデータ） (2020-10-05T20:04:58Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Can Graph Neural Networks Count Substructures? [53.256112515435355]
  グラフニューラルネットワーク(GNN)の能力について,属性付きグラフサブ構造をカウントする能力を用いて検討する。 我々は2種類のサブストラクチャカウントを区別する: インダクションサブグラフカウントとサブグラフカウント、および人気のあるGNNアーキテクチャに対する肯定的および否定的な回答である。
  論文  参考訳（メタデータ） (2020-02-10T18:53:30Z)

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

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