論文の概要: Example-Free Learning of Regular Languages with Prefix Queries
- arxiv url: http://arxiv.org/abs/2504.02170v1
- Date: Wed, 02 Apr 2025 23:05:10 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-04 12:58:14.681200
- Title: Example-Free Learning of Regular Languages with Prefix Queries
- Title（参考訳）: プレフィックスクエリを用いた正規言語の実例自由学習
- Authors: Eve Fernando, Sasha Rubin, Rahul Gopinath,
- Abstract要約: プレフィックスクエリを利用する最初の言語学習アルゴリズムであるPL*を提案する。
PL*はプレフィックスクエリによって与えられる追加情報を活用できるので、L*よりも効率的に学習することができる。
- 参考スコア（独自算出の注目度）: 9.593394739170387
- License:
- Abstract: Language learning refers to the problem of inferring a mathematical model which accurately represents a formal language. Many language learning algorithms learn by asking certain types of queries about the language being modeled. Language learning is of practical interest in the field of cybersecurity, where it is used to model the language accepted by a program's input parser (also known as its input processor). In this setting, a learner can only query a string of its choice by executing the parser on it, which limits the language learning algorithms that can be used. Most practical parsers can indicate not only whether the string is valid or not, but also where the parsing failed. This extra information can be leveraged into producing a type of query we call the prefix query. Notably, no existing language learning algorithms make use of prefix queries, though some ask membership queries i.e., they ask whether or not a given string is valid. When these approaches are used to learn the language of a parser, the prefix information provided by the parser remains unused. In this work, we present PL*, the first known language learning algorithm to make use of the prefix query, and a novel modification of the classical L* algorithm. We show both theoretically and empirically that PL* is able to learn more efficiently than L* due to its ability to exploit the additional information given by prefix queries over membership queries. Furthermore, we show how PL* can be used to learn the language of a parser, by adapting it to a more practical setting in which prefix queries are the only source of information available to it; that is, it does not have access to any labelled examples or any other types of queries. We demonstrate empirically that, even in this more constrained setting, PL* is still capable of accurately learning a range of languages of practical interest.
- Abstract（参考訳）: 言語学習とは、形式言語を正確に表現する数学的モデルを推論する問題を指す。
多くの言語学習アルゴリズムは、モデル化されている言語についてある種のクエリーを問うことによって学習する。
言語学習は、プログラムの入力パーサ(入力プロセッサとしても知られる)によって受け入れられる言語をモデル化するために使用されるサイバーセキュリティの分野において実践的な関心事である。
この設定では、学習者はパーサを実行することで選択した文字列のみをクエリできるため、使用可能な言語学習アルゴリズムは制限される。
ほとんどの実用的なパーサーは、文字列が有効かどうかだけでなく、解析が失敗した場所を示すことができる。
この余分な情報は、プレフィックスクエリと呼ばれるクエリのタイプを生成するために利用できます。
特に、既存の言語学習アルゴリズムではプレフィックスクエリは使用されないが、ある文字列が有効かどうかを問う人もいる。
これらのアプローチがパーサの言語を学ぶために使われると、パーサが提供するプレフィックス情報は使われないままである。
本研究では,プレフィックスクエリを用いた最初の言語学習アルゴリズムであるPL*と,従来のL*アルゴリズムを改良したL*を提案する。
我々はPL*がL*よりも効率的に学習できることを理論的にも実証的にも示している。
さらに、PL*がパーサの言語を学習するためにどのように使用できるかを示し、プレフィックスクエリが唯一の情報ソースであるより実用的な設定に適応することで、ラベル付き例や他の種類のクエリにアクセスできないことを示す。
この制約のある環境でも、PL*は実践的な関心のある言語を正確に学習することができることを実証的に実証している。
関連論文リスト
- Randomly Sampled Language Reasoning Problems Reveal Limits of LLMs [8.146860674148044]
我々は,データセットリコールのリスクを回避しつつ,モデルの言語理解能力の測定を試みる。
決定論的有限オートマトン(DFA)により認識される言語タスクの多種族をパラメータ化する。
3 状態 DFA の驚くほど単純な設定であっても、LLM は言語認識と合成の両タスクにおいてパラメータ化されていない ngram モデルより劣ることがわかった。
論文 参考訳（メタデータ） (2025-01-06T07:57:51Z) - Training Neural Networks as Recognizers of Formal Languages [87.06906286950438]
ニューラルネットワークを文字列のバイナリ分類器として直接訓練し評価する。
3つのニューラルアーキテクチャに対して、チョムスキー階層の様々な言語について結果を提供する。
我々の貢献は、将来の研究において、言語認識の主張を理論的に健全に検証するのに役立つだろう。
論文 参考訳（メタデータ） (2024-11-11T16:33:25Z) - Understanding and Mitigating Language Confusion in LLMs [76.96033035093204]
我々は,既存の英語および多言語プロンプトを用いた15の型的多様言語の評価を行った。
Llama Instruct と Mistral のモデルでは,言語的混乱の度合いが高いことがわかった。
言語混乱は,数発のプロンプト,多言語SFT,選好調整によって部分的に緩和できることがわかった。
論文 参考訳（メタデータ） (2024-06-28T17:03:51Z) - Can Large Language Models Code Like a Linguist?: A Case Study in Low Resource Sound Law Induction [6.697759280660703]
本稿では,大規模言語モデルのプログラミング能力を利用した言語に依存しない手法を提案する。
音響変化例からPython音声法則プログラムを生成する。
論文 参考訳（メタデータ） (2024-06-18T15:46:04Z) - How Proficient Are Large Language Models in Formal Languages? An In-Depth Insight for Knowledge Base Question Answering [52.86931192259096]
知識ベース質問回答(KBQA)は,知識ベースにおける事実に基づいた自然言語質問への回答を目的としている。
最近の研究は、論理形式生成のための大規模言語モデル(LLM)の機能を活用して性能を向上させる。
論文 参考訳（メタデータ） (2024-01-11T09:27:50Z) - Better Than Whitespace: Information Retrieval for Languages without
Custom Tokenizers [48.036317742487796]
語彙マッチング検索アルゴリズムのための新しいトークン化手法を提案する。
教師なしのデータから自動的に構築できるWordPieceトークンライザを使用します。
以上の結果から,mBERTトークン化器は,ほとんどの言語において,"アウト・オブ・ザ・ボックス(out of the box)"を検索するための強い関連信号を提供することがわかった。
論文 参考訳（メタデータ） (2022-10-11T14:32:46Z) - Active Learning of Sequential Transducers with Side Information about
the Domain [0.0]
グレイボックス学習では、目標に関する情報を予知することで学習プロセスが加速される。
この知識を用いて後続文字列トランスデューサを学習する文字列方程式ソルバを用いたアルゴリズムが存在することを示す。
論文 参考訳（メタデータ） (2021-04-23T18:01:10Z) - BERTese: Learning to Speak to BERT [50.76152500085082]
本論文では,より良い知識抽出に向けて直接最適化されたパラフレーズクエリ"BERTese"に自動書き換える手法を提案する。
私たちのアプローチが競合するベースラインを上回ることを実証的に示し、複雑なパイプラインの必要性を回避します。
論文 参考訳（メタデータ） (2021-03-09T10:17:22Z) - Revisiting Language Encoding in Learning Multilingual Representations [70.01772581545103]
言語埋め込みを置き換えるクロスリンガル言語投影(Cross-lingual Language Projection, XLP)と呼ばれる新しいアプローチを提案する。
XLPは単語埋め込みを言語固有の意味空間に投影し、投影された埋め込みはTransformerモデルに供給される。
実験により、xlpは広範囲の多言語ベンチマークデータセットのモデル性能を自由かつ著しく向上できることが示された。
論文 参考訳（メタデータ） (2021-02-16T18:47:10Z) - X-FACTR: Multilingual Factual Knowledge Retrieval from Pretrained
Language Models [103.75890012041366]
言語モデル(LM)は、事実の知識を捉えるのに驚くほど成功した。
しかし、LMの実際の表現能力の研究は、ほぼ間違いなく英語で行われている。
我々は23の語型的多様言語に対するクローゼスタイルプローブのベンチマークを作成する。
論文 参考訳（メタデータ） (2020-10-13T05:29:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。