論文の概要: Classical and quantum Merlin-Arthur automata

• arxiv url: http://arxiv.org/abs/2212.13801v1
• Date: Wed, 28 Dec 2022 12:46:18 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-09 03:36:41.461951
• Title: Classical and quantum Merlin-Arthur automata
• Title（参考訳）: 古典的および量子的メルリン・アーサーオートマトン
• Authors: Abuzer Yakary{\i}lmaz
• Abstract要約: メルリン・アーサー決定論、確率論、量子有限状態オートマトンを定義する。 我々はMA-DFAが一定の長さの証明書を使用しており、マルチエントリーDFAと等価であることを示す。 線形長証明書では、MA-PostPFAはカットポイント1/2を持ついくつかの非確率ユニタリ言語を認識できる。 任意に長い証明書で、有界エラーMA-PostQFAはすべての一意決定可能な言語を検証する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce Merlin-Arthur (MA) automata as Merlin provides a single certificate and it is scanned by Arthur before reading the input. We define Merlin-Arthur deterministic, probabilistic, and quantum finite state automata (resp., MA-DFAs, MA-PFAs, MA-QFAs) and postselecting MA-PFAs and MA-QFAs (resp., MA-PostPFA and MA-PostQFA). We obtain several results using different certificate lengths. We show that MA-DFAs use constant length certificates, and they are equivalent to multi-entry DFAs. Thus, they recognize all and only regular languages but can be exponential and polynomial state efficient over binary and unary languages, respectively. With sublinear length certificates, MA-PFAs can recognize several nonstochastic unary languages with cutpoint 1/2. With linear length certificates, MA-PostPFAs recognize the same nonstochastic unary languages with bounded error. With arbitrarily long certificates, bounded-error MA-PostPFAs verify every unary decidable language. With sublinear length certificates, bounded-error MA-PostQFAs verify several nonstochastic unary languages. With linear length certificates, they can verify every unary language and some NP-complete binary languages. With exponential length certificates, they can verify every binary language.
• Abstract（参考訳）: 我々はMerlin-Arthur Automaticaを紹介し、Merlinは単一の証明書を提供し、入力を読む前にArthurによってスキャンされる。 本稿では,Merlin-Arthurによる決定論的,確率的,量子有限状態オートマトン(Resp.,MA-DFAs,MA-PFA,MA-QFAs)を定義し,MA-PFAsとMA-QFAs(resp.,MA-PostPFA,MA-PostQFAs)をポストセレクトする。 異なる証明書長を用いていくつかの結果を得る。 我々はMA-DFAが一定の長さの証明書を使用することを示す。 したがって、すべての正規言語と正規言語のみを認識できるが、指数関数と多項式状態はそれぞれ二進言語と一進言語よりも効率的である。 線形長証明書では、MA-PFAはカットポイント1/2を持ついくつかの非確率的ユニタリ言語を認識できる。 線形長証明では、MA-PostPFAは同じ非確率的な単言語を有界エラーで認識する。 任意に長い証明書で、有界エラーMA-PostPFAはすべての一意決定可能な言語を検証する。 サブ線形長証明書では、有界エラーMA-PostQFAはいくつかの非確率的ユニタリ言語を検証する。 線形長証明では、すべてのユニタリ言語とNP完全バイナリ言語を検証できる。 指数長証明書を使用すると、すべてのバイナリ言語を検証できる。

関連論文リスト

• M2QA: Multi-domain Multilingual Question Answering [63.191474328757366]
  入力変動に対する一般化と堅牢性は、機械学習研究の核となるデシダータである。 マルチドメイン多言語質問応答ベンチマークであるM2QAを紹介する。 M2QAには、ドイツ語、トルコ語、中国語で13500のSQuAD 2.0スタイルの質問応答インスタンスが含まれている。
  論文  参考訳（メタデータ） (2024-07-01T08:48:49Z)
• On the Evaluation Practices in Multilingual NLP: Can Machine Translation Offer an Alternative to Human Translations? [19.346078451375693]
  NLPにおける既存の評価フレームワークについて分析する。 より堅牢で信頼性の高い評価手法を提案する。 より単純なベースラインは,大規模多言語事前学習の恩恵を受けずに比較的高い性能が得られることを示す。
  論文  参考訳（メタデータ） (2024-06-20T12:46:12Z)
• Parrot: Multilingual Visual Instruction Tuning [66.65963606552839]
  視覚エンコーダとマルチモーダル大言語モデル(MLLM)の整合性に着目した既存手法 そこで本研究では,テキストガイダンスを用いて視覚的トークンアライメントを言語レベルで促進する新しい手法であるParrotを紹介する。 本手法は,多言語MMBenchおよびMMMB上での最先端性能を示すだけでなく,多モーダルタスクにも優れる。
  論文  参考訳（メタデータ） (2024-06-04T17:56:28Z)
• Mitigating Language-Level Performance Disparity in mPLMs via Teacher Language Selection and Cross-lingual Self-Distillation [25.850573463743352]
  大規模多言語事前訓練言語モデル(mPLMs)は、言語横断タスクにおいて優れた性能を発揮する。 しかし、mPLM内では異なる言語にまたがって大きな性能格差が存在する。 我々は ALSACE を導入し,優れた言語から学んだ知識を活用して,mPLM の低性能言語を誘導する。
  論文  参考訳（メタデータ） (2024-04-12T14:19:16Z)
• MYTE: Morphology-Driven Byte Encoding for Better and Fairer Multilingual Language Modeling [70.34758460372629]
  多様な言語にまたがる一貫した大きさのセグメントで同一情報をエンコードする新しいパラダイムを導入する。 MYTEは99の言語すべてに対して短いエンコーディングを生成する。 これにより、多言語LMの性能が向上し、多言語間でのパープレキシティギャップが減少する。
  論文  参考訳（メタデータ） (2024-03-15T21:21:11Z)
• Extrapolating Large Language Models to Non-English by Aligning Languages [109.09051737966178]
  既存の大きな言語モデルは、異なる言語間で異なる能力を示す。 本稿では,言語間のセマンティックアライメントを構築することで,英語以外の言語に事前学習したLLMを強化する。
  論文  参考訳（メタデータ） (2023-08-09T13:32:06Z)
• Do Multi-Lingual Pre-trained Language Models Reveal Consistent Token Attributions in Different Languages? [42.47155960879255]
  多言語 PLM が異なる言語で一貫したトークン属性を示すかどうかは不明である。 3つの下流タスクにおける広範囲な実験により、多言語 PLM は多言語同義語に大きく異なる属性を割り当てることを示した。 スペイン語は、PLMのトレーニングに使用される際、異なる言語で最も一貫性のあるトークン属性を達成している。
  論文  参考訳（メタデータ） (2021-12-23T04:40:06Z)
• Multilingual Autoregressive Entity Linking [49.35994386221958]
  mGENREはMultilingual Entity Linking問題のためのシーケンス対シーケンスシステムである。 与えられた言語で言及すると、mGENREはターゲットエンティティの名前を左から右へ、トークンごとに予測します。 提案手法の有効性を3つのMELベンチマーク実験を含む広範囲な評価により示す。
  論文  参考訳（メタデータ） (2021-03-23T13:25:55Z)
• X-FACTR: Multilingual Factual Knowledge Retrieval from Pretrained Language Models [103.75890012041366]
  言語モデル(LM)は、事実の知識を捉えるのに驚くほど成功した。 しかし、LMの実際の表現能力の研究は、ほぼ間違いなく英語で行われている。 我々は23の語型的多様言語に対するクローゼスタイルプローブのベンチマークを作成する。
  論文  参考訳（メタデータ） (2020-10-13T05:29:56Z)

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

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