論文の概要: Sequence graphs realizations and ambiguity in language models
- arxiv url: http://arxiv.org/abs/2402.08830v1
- Date: Tue, 13 Feb 2024 22:22:51 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-02-15 17:32:37.171056
- Title: Sequence graphs realizations and ambiguity in language models
- Title（参考訳）: 言語モデルにおけるシーケンスグラフの実現と曖昧性
- Authors: Sammy Khalife, Yann Ponty, Laurent Bulteau
- Abstract要約: 計算的観点から,シーケンスグラフの実現可能性とあいまいさについて検討する。
大きさが 3 の窓に対して、w が定数であるとしても、すべての不変量の硬さを証明する。
本稿では、実現可能性問題を解く整数プログラムと、列挙問題の解法を動的プログラミングで結論付ける。
- 参考スコア（独自算出の注目度）: 1.4732811715354455
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Several popular language models represent local contexts in an input text 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, and may
introduce some degree of ambiguity. Some sequence graphs may admit 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 computational 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 a window of size at
least 3, we prove 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 an XP algorithms for both (realizability and enumeration)
problems, tight due to a corresponding W[1]-hardness result. We conclude with
an integer program formulation to solve the realizability problem, and with
dynamic programming to solve the enumeration problem. This work leaves open the
membership to NP for both problems, a non-trivial question due to the existence
of minimum realizations having exponential size on the instance encoding.
- Abstract（参考訳）: いくつかのポピュラー言語モデルは、入力テキスト中のローカルコンテキストを単語の袋として表現する。
このような表現は、頂点がxで生じる異なる単語である列グラフによって自然に符号化され、エッジはサイズ w のスライディングウィンドウ内で2つの単語の(順序付けられた)共起を表す。
しかし、この圧縮表現は一般に単射的ではなく、ある程度の曖昧さをもたらす可能性がある。
いくつかのシーケンスグラフは、列としていくつかの実現を許容するが、他のグラフは任意の実現を認めない。
本稿では,コンビネーションと計算の観点から,シーケンスグラフの実現可能性と曖昧性について検討する。
ウィンドウサイズw,グラフ配向の有無,重み(多重度)の存在/吸収など,複数の設定下でのシーケンスグラフの実現の有無と列挙について考察する。
w = 2 の場合、非有向/重み付け設定を除いて、すべての場合において実現可能性と列挙のための多項式時間アルゴリズムを提供する。
大きさが 3 のウィンドウでは、w が定数と見なされる場合でも、対応する W[1]-ハードネスの結果により厳密な(実現可能性と列挙性の両方)問題に対する XP アルゴリズムを提案する非方向/非重み付きケースの顕著な例外を除いて、すべての変量体の硬さを証明する。
我々は、実現可能性問題を解決するための整数プログラム定式化と、列挙問題を解くための動的プログラミングで締めくくった。
この研究は、両方の問題に対してNPへのメンバシップを開放するが、これはインスタンスエンコーディングの指数的なサイズを持つ最小化の存在による非自明な問題である。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。