論文の概要: 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へのメンバシップを開放するが、これはインスタンスエンコーディングの指数的なサイズを持つ最小化の存在による非自明な問題である。
関連論文リスト
- 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) - 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) - Casting graph isomorphism as a point set registration problem using a
simplex embedding and sampling [0.0]
グラフは、単純な埋め込みとサンプリングを用いて、十分な次元でセットされた点として表すことができる。
それらの同型は、グラフの点集合形式の間の完全登録の存在に対応する。
等値類に関する関連する考えは、グラフの正準化がグラフ同型問題に取り組む上で重要なツールであることを示している。
論文 参考訳（メタデータ） (2021-11-15T12:16:21Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。