arXiv雑要約
プログラム - 2026/05/14 公開
Transformer における有効な文脈：断片化とトークン化の分析 [cs.LG, cs.CL, cs.IT, math.IT]目的：Transformer の性能に影響を与える表現方法（バイト，文字，サブワードトークン）の選択に関する情報理論的枠組み
- Transformer は自然言語処理の主要モデルであり，その性能向上は重要である。
- Transformer の文脈窓サイズが限られている場合，表現方法の選択が性能に影響する点が問題である。
- 表現方法の選択が Transformer の予測能力に与える影響を理論的に解明し，最適な表現方法を検討する。
- より小さな表現単位への移行は，文脈窓を拡大しても予測精度を低下させる可能性があることが示された。
- 断片化が有限文脈における損失を厳密に増加させることが証明され，表現方法に内在するギャップであることを示した。
- 貪欲なトークン化が短いトークンウィンドウを長い文脈ウィンドウのように振る舞わせることができ，その条件が明確化された。
SieveFL：スケーラブルなLLMに基づく欠陥局所化のための階層的実行時認識プルーニング [cs.DM, cs.DC, cs.SE]目的：LLMを活用した欠陥局所化の効率化と精度向上
- ソフトウェアの信頼性確保には，欠陥の迅速かつ正確な特定が不可欠である。
- 大規模なコードベースにおいて，統計的アプローチやLLMでは，候補の絞り込みが困難である。
- LLMに渡す候補を絞り込むことで，コストと精度という課題を解決する。
- SieveFLは，Defects4J v1.2.0の395個のバグに対してTop-1精度41.8% (165/395)を達成した。
- 従来のAgentFLと比較して，Top-1精度が2.1pp向上し，優れた性能を示した。
- 実行時プルーニングにより，候補メソッドが79%削減され，トークン消費量も49%減少した。
連続分布に対する厳密サンプラーの離散プログラム論理による検証 [cs.IR, cs.HC, cs.RO, cs.LO]目的：連続分布の厳密サンプラーの正当性検証
- 確率的アルゴリズムの安全性確保は重要であり，特に差分プライバシーでは厳密な数値計算が不可欠である。
- 浮動小数点演算は丸め誤差を含み，その誤差解析は困難である。厳密サンプラーは複雑で実装が難しい。
- 連続分布の厳密サンプラーを検証するための高階分離論理Continuous-Erisを開発し，その有効性を示す。
- Continuous-Erisを用いることで，一様分布，ガウス分布，ラプラス分布の厳密サンプラーの正当性を検証した。
- 生成されたサンプルを扱うための厳密実数演算ライブラリについても検証を行い，その信頼性を保証した。
- 本研究の全ての検証結果は，Rocq証明支援システムを用いて検証されており，再現性を確保している。
部分構造文脈におけるモナドと分配法則 [cs.LO, math.CT]目的：部分構造文脈におけるモナドと分配法則の圏論的理論
- プログラム言語の型システムや意味論において，モナドは重要な構成要素である。
- 既存の理論では，変数コンテキストの構造規則の有無が分配法則に影響することが認識されている。
- Troninの言語圏$\mathbf W$を用いて，これらの部分構造状況を形式化し，分配法則のより一般的な理論を構築する。
- $\mathbf W$-オペラド的モナドと$\mathbf W$-可換モナドという新しいクラスを導入した。
- モナド$S$と$T$に対して，分配法則$ST\to TS$の標準的な構成法を提供した（$S$が$\mathbf W$-オペラド的，$T$が$\mathbf W$-可換な場合）。
- $\mathbf W$-オペラド的でない$S$に対しても，$\mathbf W$-オペラド性を強制する手法を提示し，VaraccaとWinskelの指標付き評価の構成を捉えた。
自動運転車のシナリオベーステストのためのエージェントモデルをオープンシミュレーションアーキテクチャに統合 [cs.RO, cs.SE]目的：自動運転システムの安全性確保のためのシミュレーションおよびシナリオベーステスト
- 自動運転技術の安全性評価には，現実世界を忠実に再現したシミュレーションが不可欠である。
- シミュレーション環境間のエージェントモデルの相互運用性が課題であり，標準化が求められている。
- 異なるシミュレーション環境で一貫したエージェントモデルの動作を可能にする標準化アーキテクチャを提案する。
- 提案アーキテクチャは，Open Simulation Interface (OSI) と Functional Mock-up Interface (FMI) を活用し，ツールに依存しないエージェントモデル統合を実現する。
- OpenPASS，CARLA，CarMakerといった主要なシミュレーション環境へのエージェントモデル統合に成功し，汎用性を実証した。
- 統合されたモデルは全てのシミュレーションプラットフォームで一貫した挙動を示し，アーキテクチャの相互運用性，モジュール性，標準準拠を検証した。
$\mathcal{FL}_{\bot \mathit{reg}}$ におけるTBoxを用いたサブサムプションはExpTimeに属する [cs.LO]目的：記述論理における概念包含性の計算複雑性
- 知識表現と推論において重要な役割を担う記述論理の基礎研究。
- 特定の記述論理における概念包含性の計算複雑性が未解決の問題として残存する。
- $\mathcal{FL}_{\bot \mathit{reg}}$ およびその断片における概念包含性の複雑性を決定すること。
- $\mathcal{FL}_{\bot \mathit{reg}}$ および $\mathcal{FL}_\mathit{reg}$ における概念包含性の判定はPSpace-完全であることが示された。
- TBox を考慮した場合，概念包含性の判定はExpTime-完全になる。
- この結果は，パリティプッシュダウンゲームへの新しい還元によって得られた。
データレベル並列プログラムの拡張可能検証 [cs.RO, cs.SE]目的：データレベル並列プログラムの検証における拡張性向上
- 並列計算の普及に伴い，データレベル並列プログラムの検証需要が増加している。
- 大規模なデータレベル並列プログラムの検証は，計算量が多く困難である。
- 検証時間の短縮により，より大規模なプログラムの検証を可能にすること。
- 提案手法により，GPUカーネルの検証時間を平均9倍，最大150倍短縮した。
- 既存の検証事例やラジオ天体望遠鏡パイプラインのケーススタディでも，以前は検証できなかった結果を検証可能とした。
- 量化子を含む式の書き換え技術の正当性を定理証明器で検証した。
多属性時相論理監視 [cs.LO]目的：多属性時相論理監視のためのフレームワーク
- システムが多数の時相特性を満たす必要があり，その検証は重要である。
- 従来の監視アプローチでは，各特性を独立して監視するため，計算資源の無駄が生じる。
- 複数の時相特性を効率的に監視し，計算資源の利用効率を向上させる。
- 提案手法は，過去時相LTLおよびMTL仕様を共有の有向非巡回グラフにコンパイルする。
- 特性ごとのスループットが2倍から4.5倍，多属性設定では6倍から12倍に向上した。
- 大規模な仕様セットへのスケーラビリティと，高性能・リソース制約のあるシステムへのデプロイが可能になった。
スケールに依存する破砕：最適なスケールにおける学習可能性と評価可能性 [cs.LG, cs.IT, math.IT]目的：実数値関数クラスにおける一様収束と学習可能性の最適なスケール
- 機械学習において，汎化性能の理論的保証は重要であり，そのために学習可能性を評価する必要がある。
- 学習可能性を決定するスケールの正確な境界は不明であり，既存の研究にはギャップが存在した。
- 学習可能性と評価可能性を支配するスケールを正確に決定し，既存の研究のギャップを埋める。
- 本研究により，PAC学習の基本定理のスケール依存性の一般化が確立され，Longの予想を反証した。
- 経験的$\ell_\infty$被覆数の直接的な上限を導出し，既存研究よりもシャープな漸近的メトリックエントロピー上限を達成した。
- 有界積分確率測度に対する明確な二分法を確立し，Aiyerらの未解決問題を解決した。
SkillOps：LLMエージェントのスキルライブラリを自己維持型ソフトウェアエコシステムとして管理 [cs.SE, cs.MA]目的：LLMエージェントのスキルライブラリにおける技術的負債の管理
- LLMエージェントの能力向上には，効率的なスキルライブラリの構築が不可欠である。
- スキル追加や依存関係の変化により，スキルライブラリに潜在的な欠陥が蓄積しやすい。
- スキルライブラリのメンテナンスを体系化し，技術的負債を解消することを目指す。
- SkillOpsは，スキルを型付きスキルコントラクトで表現し，階層的なスキルエコシステムグラフで整理する。
- ALFWorldにおいて，SkillOpsは単独で79.5%のタスク成功率を達成し，既存のベースラインを8.8%上回った。
- プラグインとして適用した場合，既存の検索ベースラインを0.68～2.90%向上させた。ライブラリメンテナンス時のLLMコストは低い。
自律走行車テストのための責任帰属型敵対シナリオ学習 [cs.RO, cs.SY, eess.SY, cs.PF, math.PR, cs.RO, cs.SE, cs.SY, eess.SY]目的：自律走行システムの安全性評価における，避けうるシステム欠陥と不可避な交通衝突の区別
- 自動運転技術の安全性を保証することは，社会実装において不可欠である。信頼性向上への要求は高い。
- 既存の敵対的シミュレーションは衝突を露呈させるが，原因の特定が困難である。安全性評価の妨げとなる。
- 本研究は，責任帰属を考慮したシナリオ生成により，解釈可能で規制に準拠した安全性評価を実現する。
- CARS（Context-Aware, Responsibility-attributed Scenario generation）は，文脈を考慮した敵対者選択と生成敵対的方策を組み合わせる。
- CARSは，複数の交通環境において，物理的に実行可能で，責任帰属率の高い衝突シナリオを生成することに成功した。
- 敵対的生成と規範的責任評価を組み合わせることで，衝突検出を超えた，検証可能な安全性評価が可能となる。
確率的アイリスへの第一歩：独立性，条件付け，動的ヒープ割り当ての調和 [cs.LO, cs.PL]目的：確率的分離論理と現代的分離論理の統合
- 近年，確率的分離論理が発展しており，プログラムの確率的振る舞いを厳密に検証する基盤を提供する。
- 既存の確率的汎用論理は動的メモリ割り当てを扱えず，ポインタの所有権と確率的独立性・条件付けの調和が課題であった。
- 動的メモリ割り当てをサポートし，確率的独立性と条件付けを両立する確率的汎用論理を構築すること。
- Amaryllisは，独立性と条件付けの推論をサポートしつつ，動的メモリ割り当てを扱う初の確率的汎用論理である。
- 新しい「インデックス付き評価」モデルを提案することで，Irisスタイルのリソースの所有権を分布レベルに拡張し，ポインタの所有権の問題を解決した。
- Amaryllisの全ての成果はRocq証明支援システムで形式化され，Irisベースの証明モードが開発された。
高速量子化行列積 II [cs.CE, cs.LG, cs.AI, cs.IT, math.IT]目的：量子化行列積の性能向上
- 大規模言語モデルの効率化が重要であり，量子化はその有力な手法である。
- 既存の量子化手法は，基底の選択に依存し，性能が変動する可能性がある。
- 共分散行列を利用し，水張り法を用いて量子化精度を向上させる。
- 共分散行列が利用可能な環境下で，水張り法がGPTQなどの実用的な量子化アルゴリズムの性能向上に寄与する。
- WaterSICという最近のスキームは，基底に依存せず，理論上の歪み限界に0.25ビット/エントリ以内まで近づく。
- GPTQとランダム回転を用いた場合，WaterSICとの差は0.1ビット程度であり，高レート領域ではほぼ最適である。
大規模言語モデルは高レベルメッセージシーケンスチャートをどのように理解するか [cs.SE, cs.AI, cs.LO]目的：高レベルメッセージシーケンスチャート(HMSC)に対する大規模言語モデルの理解度評価
- ソフトウェア開発ライフサイクルにおける自動化の重要性が増しており，その根拠となるアーキテクチャ設計仕様の理解が不可欠である。
- 大規模言語モデルが扱う成果物の意味論との整合性が不明であり，特にアーキテクチャ設計仕様における検証が不足している。
- HMSCの厳密な形式意味論に基づき，大規模言語モデルの理解度を評価し，その限界を明らかにすることを目的とする。
- 大規模言語モデルはHMSCの形式意味論を限定的にしか理解していないことが示された(全体正答率約52%)。
- 基本的なHMSCの概念(イベントと順序)の理解度は高い(約88%)の，抽象化や合成などの意味論的推論は苦手である(約36%)。
- トレースやLTSの計算においても課題があり，特にコリージョンや明示的な因果関係の概念の活用ができていない。
自然還元における健全性検証の複雑性 [cs.PL]目的：自然還元の健全性判定問題
- 並列プログラムの正当性証明は困難であり，還元を用いることで簡略化が期待される。
- 既存の還元手法では，表現力や効率性に課題が残されている場合がある。
- 自然還元の健全性判定の計算複雑性を明らかにすることで，効率的な検証手法の確立を目指す。
- 同期がない場合，健全性判定問題は多項式時間で解決可能であることが示された。
- 同期がある場合，健全性判定問題はcoNP困難であることが証明された。
- ロックのような単純な同期機構でも，問題の難易度は高いことが示された。
エッジ故障下における低コストな樹形構造 [cs.DS]目的：エッジ故障が発生した場合の最小コスト樹形構造の維持
- ネットワークの信頼性確保は，現代社会におけるインフラ運用において極めて重要である。
- エッジ故障発生時の迅速な復旧と，それに伴う最小コスト樹形構造の再計算が課題である。
- 故障時においても効率的な再計算を可能とする疎な部分グラフの構築を試みる。
- 前処理により構築された部分グラフH上で最小コスト樹形構造を計算することで，G-f上の近似解を得る。
- H-f上の最小コスト樹形構造は，G-f上の最小コスト樹形構造の2倍以内のコストとなる。
- マトロイド設定においても，故障耐性のある維持集合のサイズに関するタイトな上限を示す。
最小最大最適化には指数関数的に多数のクエリが必要である [cs.DS, cs.CC, cs.GT, cs.LG, math.OC]目的：非凸・非凹関数fの最小最大最適化におけるクエリ複雑性
- 機械学習等の最適化問題は多岐に渡り，効率的な解法が求められている。
- 非凸・非凹関数の最適化は，局所解に陥りやすく，厳密解を見つけるのが困難である。
- ε-近似停留点を見つけるためのクエリ数を理論的に評価し，困難性を示す。
- 非凸・非凹関数の最小最大最適化において，ε-近似停留点を見つけるためには，εまたは次元dに対して指数関数的な数のクエリが必要であることが示された。
- この結果は，既存のアルゴリズムの限界を示唆しており，より効率的なアルゴリズム開発の必要性を示唆する。
- クエリ複雑性の理論的限界を理解することは，現実的な問題への適用可能性を評価する上で重要である。
ランダム化ハダマール変換による証明可能な量子化 [cs.LG, cs.DS]目的：ベクトル量子化における理論的保証と効率化
- 機械学習の分野において，類似検索や分散学習など幅広い応用を持つ基本的な手法である。
- ランダムなハダマール変換は計算コストが課題であり，理論的な保証も十分ではない。
- ジッター付き量子化により，ランダム回転行列と同等の性能を達成し，理論的保証を与える。
- ジッター付き量子化とランダム化ハダマール変換の組み合わせが，理論的に無バイアスであることが証明された。
- TurboQuantのジッター付きバージョンは，座標あたり$b$ビットで平均二乗誤差$\bigl(\pi\sqrt{3}/2 + o(1)\bigr) \cdot 4^{-b}$を達成する。
- この誤差は，量子化レベルが増加するにつれて，すべての単位ベクトルとすべての次元で一様的に消失する。
自然言語ソフトウェア要件の神経記号的監査 [cs.SE, cs.AI]目的：自然言語によるソフトウェア要件の曖昧性，矛盾，不備の検出
- 安全性に関わる分野では，要件の誤りが重大な事故につながるため，厳密な検証が不可欠である。
- 自然言語で記述された要件は解釈が曖昧で，一貫性がない場合が多く，誤った仕様や危険な実装を引き起こす。
- 大規模言語モデルとSMTソルバーを組み合わせることで，自然言語要件の曖昧性や矛盾を検出し，安全性を評価する。
- 大規模言語モデルとSMTソルバーの組み合わせにより，要件の曖昧性を検出し，複数の解釈が存在する場合にSMTソルバーで検証可能なテストを生成できる。
- 具体的なSMTソルバーの反例を用いた反復的な修正により，血液透析に関する質疑応答ベンチマークの精度が55.4%から98.5%に向上した。
- VERIMEDは，オープンソースの血液透析安全要件に対する曖昧性感受性要件を削減し，SMTベースのクエリによる厳密な監査を可能にする。
ニューロシンボリック学習と検証のための量的な線形論理 [cs.LO]目的：ニューロシンボリック学習と検証のための量的な線形論理の提案
- ニューラルネットワークに論理的制約を組み込むことで，より堅牢で解釈可能なモデルの構築が期待される。
- 従来の微分可能論理は，論理的性質と解析的な要件とのトレードオフが存在し，十分な基盤が確立されていない。
- 機械学習で用いられる演算（和とlog-sum-exp）に即した論理演算の定義により，この課題を解決する。
- 提案手法である量的な線形論理（QLL）は，標準的な線形論理の法則をほぼ満たすことが確認された。
- QLLは，テスト時の性能（敵対的攻撃に対する耐性）と論理的制約の検証結果との相関性が高いことが示された。
- この相関性の高さは，最先端技術と比較してQLLの優位性を示している。
エントロピー誘導型段階的スケーリングによる信頼性の高いソフトウェアエンジニアリング [cs.SE, cs.AI, cs.LG]目的：ソフトウェアエンジニアリングにおける信頼性向上
- ソフトウェア開発の複雑化に伴い，高品質なコード生成・バグ修正の自動化が重要である。
- 既存のテスト時スケーリング手法は計算コストが高く，実用性に課題がある。
- 効率性と有効性を両立する新たなテスト時スケーリングフレームワークを提案し，改善を図る。
- 提案手法EGSSは，SWE-Bench-Verifiedにおける複数のモデルで性能を5-10%向上させた。
- Kimi-K2-Intructの解決率を63.2%から72.2%に，GLM-4.6の解決率を65.8%から74.6%にそれぞれ向上させた。
- GLM-4.6と組み合わせることで，オープンソース大規模言語モデルの中で新たな最高性能を達成し，トークン使用量も28%以上削減した。
ノード故障における無線ネットワークの容量と遅延 [cs.IT, cs.DC, cs.NI, cs.PF, math.IT]目的：ノード故障がネットワーク性能に与える影響の理解
- 大規模無線アドホックネットワークの信頼性設計は重要である。断続的な接続が頻繁に発生する環境下での性能評価が求められる。
- ノード故障がネットワーク容量や遅延に及ぼす影響の定量的な評価が不足していた。
- ノード故障時のネットワーク容量低下を補償するための冗長性の必要量を明らかにする。
- ネットワーク容量と遅延は，ノード数nと故障確率qを用いて$\Theta\left(\sqrt{\frac{n(1-q)}{\log n}}\right)$としてスケールすることが示された。
- 同じ健全なノード数であっても，故障確率qを持つネットワークは，故障のないネットワークよりもネットワーク容量が低いことが明らかになった。
- ネットワーク容量の損失を補償するには，少なくとも$\epsilon(n,q) nq$個の冗長ノードが必要であることが示された。
情報としての最大カルーバー逸脱：統合情報理論と自由エネルギー原理の架け橋 [q-bio.NC, cs.AI, cs.IT, math.IT]目的：統合情報理論と自由エネルギー原理の数学的対応付け
- 自己組織化や学習の数理モデルとして重要性が増しているため。
- 厳密な数学的対応付けが存在せず，検証の精度に限界があるため。
- 最大カルーバー原理に基づき，両理論を結びつける理論的枠組みを構築する。
- 情報が，有限時間における制約付き最大カルーバー経路アンサンブルからの逸脱として定義できる。
- この定義のもと，IIT 3.0の中核となる因果関係のレパートリーが最大カルーバーの変分原理から直接導出される。
- マルコフ連鎖やイジングモデルへの適用により，情報は予測誤差と同等であることが示された。
マルチポートアンテナのQ因子 [eess.SP, cs.IT, math.IT]目的：マルチポートアンテナの帯域幅の推定
- 無線通信技術の発展に伴い，高効率なアンテナ設計が重要視されている。
- マルチポートアンテナの帯域幅を正確に予測することは困難である。
- シングルポートQ因子を一般化することで，帯域幅評価を可能とする。
- 提案手法は，蓄積エネルギー行列をポート等価回路に変換し，ポートパラメータを利用して帯域幅を評価する。
- 総反射係数を用いることで，単一周波数における帯域幅を簡便に算出できる。
- 2つの異なるダイポールアレイと大型パッチアンテナアレイを用いた検証により，理論の有効性が確認された。
UM-MIMOにおける近傍・遠方場THz広帯域チャネル推定のための再帰型Transformer [eess.SP, cs.IT, cs.LG, math.IT]目的：THz通信と超大規模MIMOシステムにおけるチャネル推定手法
- 6Gネットワークにおいて，高速化，スペクトル効率向上，ネットワーク性能改善が求められている。
- アンテナアパチャーの拡大と高周波数化により，近傍場と遠方場の両方の影響を考慮する必要がある。
- デジタルチェーン数の制約下で，ハイブリッドビームフォーミングにおける正確なチャネル推定を実現する。
- 提案手法は，一度学習したTransformerブロックを反復適用することで，近傍・遠方場を同時に推定可能である。
- 様々な散乱距離，伝搬パス数，広帯域環境への汎化性能を有することが確認された。
- 狭帯域および広帯域シナリオにおいて，最先端手法と比較して，それぞれ約5dB，7.5dBのNMSE性能向上を達成した。
非エルミート二変量量子信号処理における最適境界，障壁，および拡張 [quant-ph, cs.CC, cs.DS]目的：非エルミート Hamiltonian のシミュレーションにおける最適化，角度探索，および定数係数解析
- 量子シミュレーションは，新薬開発や材料設計など，様々な分野への応用が期待されている。
- 多変量量子信号処理(M-QSP)の最適化は困難であり，計算コストの削減が課題となっている。
- M-QSPの最適化の限界を明らかにし，より効率的なアルゴリズムを開発すること。
- 反エルミートクエリ複雑度に関するタイトな上限を確立し，Chebyshev係数，修正ベッセル関数，Lambert W関数の逆関数の漸近解析を用いた。
- 二変量多項式モデルにおいて，高速化は不可能であるが，状態依存の線形改善が達成可能であることを示した。
- 角度探索の計算量を削減し，エラー配分を最適化することで，情報理論的下界に近い定数係数を実現した。
メトロポリス・ヘイスティングス法のための多次元結合 [stat.CO, cs.IT, math.IT]目的：マルコフ連鎖モンテカルロ法の収束診断
- 計算統計学において，マルコフ連鎖モンテカルロ法の収束診断は重要な課題である。
- 既存手法では，高次元設定において計算コストが課題となっていた。
- 多次元結合を用いた新たな収束診断法の開発と効率化を目指す。
- 複数のメトロポリス・ヘイスティングス連鎖の結合に多次元結合を適用する手法を提案した。
- 提案手法は，従来のポアソンモンテカルロ法の次元依存性のボトルネックを回避し，高次元設定で特に効果的である。
- 実験の結果，提案手法は既存手法と比較して結合率を向上させ，収束時間を最大50%削減した。
複素周波数励起を用いた固有周波数推定 [physics.class-ph, cs.IT, math.IT, physics.app-ph]目的：機械系のノイズ下における固有周波数推定の精度向上
- 微小な振動を検出するセンサー開発や非破壊検査において，固有周波数推定の精度は極めて重要である。
- 従来の調和励起では，ノイズの影響を受けやすく，高精度な固有周波数推定が困難となる場合がある。
- 複素周波数励起の特性を解析し，ノイズに対するロバスト性を高めることで，高精度な固有周波数推定を実現する。
- 複素周波数励起は，機械共鳴器の有効Q値を大幅に向上させることが示されており，それを利用した推定精度向上が期待される。
- Fisher情報を用いた解析により，励起パラメータの適切な選択が推定精度を向上させることが理論的に示された。
- 実験結果は，複素周波数励起が従来の調和励起よりも高精度かつロバストな固有周波数推定を可能にすることを示している。
ヴァリアントの学習可能性理論で学習可能なものは何か [stat.ML, cs.DS, cs.LG, math.ST, stat.CO, stat.TH]目的：ヴァリアントの学習モデルにおける学習可能性の条件の特定
- 機械学習の理論的基盤を理解する上で，学習可能性の条件を明確にすることは重要である。
- ヴァリアントのオリジナルモデルは，PAC学習モデルとは異なり，学習クラスの特性が未解明な部分があった。
- ヴァリアントのオリジナルモデルにおける学習可能性の判定基準を確立し，PAC学習モデルとの関係を明らかにする。
- 有限ドメインにおいて，クラスが学習可能であるための必要十分条件は，実現可能な正のサンプルが多項式サイズの適応的クエリ圧縮スキームによって検証可能であることである。
- ヴァリアントモデルにおける学習可能性は，PAC学習モデルとクエリなしのヴァリアントモデルの間で厳密に挟まれることが示された。
- クエリなしでは学習不可能な$d$次元半空間が，クエリを用いることで学習可能となり，そのためのアルゴリズムとサンプル・クエリ数の下界が示された。
定数時間で効率的なPRAMを用いたクエリ評価 [cs.DB, cs.LO]目的：効率的なクエリ評価アルゴリズムの検討
- データベース処理の高速化は，大規模データ分析において不可欠である。
- 並列処理におけるクエリ評価は，計算資源の浪費やメモリの断片化を招きやすい。
- 定数時間で実行可能な効率的なクエリ評価手法の確立を目指す。
- 本研究では，CRCW PRAMモデルにおける定数時間クエリ評価アルゴリズムを提案した。
- データ値のサイズや関係のソート状態に関する穏やかな仮定の下で，弱仕事効率の良いアルゴリズムが実現された。
- 近似プレフィックス和や圧縮アルゴリズムなど，既存の手法を応用することで，最適な逐次アルゴリズムの時間に近い結果を得た。
MCAC：近似回路の誤差指標を正確に計算するモデルカウントアルゴリズム [cs.RO, cs.LO]目的：近似回路の誤差指標の正確な計算
- 高性能化と低消費電力化のために近似回路の利用が不可欠であり，その評価には正確な誤差指標の算出が重要である。
- 既存手法では，誤差指標ごとに異なるミッターが必要となり，計算コストが増大する問題があった。
- 共通の誤差ミッターを用いて，複数の誤差指標を効率的に計算し，評価プロセスを簡素化することを目指す。
- MCACは，単一のシステム合成と差分演算を用いることで，従来のミッターベース手法と比較して大幅な高速化を実現した。
- CNF式を木構造に変換し，メッセージパッシングによってすべての誤差指標を計算する新しいフレームワークを提案した。
- 提案手法は，ベンチマークインスタンスにおいて，オフザシェルフのモデルカウンターと比較して，著しい性能向上を示した。
キャリブレーションされた非パラメトリック確率予測のための効率的な分布回帰木学習アルゴリズム [cs.LG, cs.DS]目的：キャリブレーションされた非パラメトリック確率予測のための分布回帰木の学習
- 科学技術における信頼できるAI開発には，不確実性を推定できる機械学習技術が不可欠である。
- 従来のパラメトリックモデルは制約が強く，非パラメトリックモデルが柔軟な代替手段となる。
- WISやCRPSといった適切なスコアリングルールを用いて，より正確な確率予測を目指す。
- 提案手法は，WISまたはCRPS損失関数に対する確率回帰木を効率的に学習するアルゴリズムである。
- min-maxヒープ，重み付き二分木，Fenwick木といったデータ構造の適切な利用により，計算効率を高めている。
- 数値実験により，提案手法が既存手法と同等以上の性能を示すことを実証した。
半対立的エラーに対するリード・ソロモンおよび関連コードのユニークな復号 [cs.IT, cs.DS, math.IT]目的：半対立的エラーモデルにおける最適な効率的なユニーク復号アルゴリズムの解明
- 誤り訂正符号は，通信やデータ保存においてデータの信頼性を確保する上で不可欠である。
- 従来の復号アルゴリズムは，完全なランダムエラーか完全な対立的エラーのいずれかを想定しており，その中間的なケースに対応できない。
- 半対立的エラーモデルに対応する，高速かつ効率的なユニーク復号アルゴリズムの開発が求められている。
- インターリーブ型リード・ソロモン，フォールデッド型リード・ソロモン，単変量多重度符号に対して，ランダムエラーと対立的エラーの混合に対応する，ほぼ線形時間の復号アルゴリズムを設計した。
- 提案アルゴリズムの性能解析は，半対立的エラーにおける情報理論的最適値と一致している。
- フォールデッド型リード・ソロモンや多重度符号への適用には，従来の複雑な根の探索の代わりに，単純な多項式除算を用いることで，高速化を実現した。
入力相関同期エラーを持つチャネル [cs.IT, math.IT]目的：入力相関同期エラーを持つチャネルの情報容量
- 現実世界のデータストレージや情報伝送では，独立同分布の誤りモデルでは不十分である。
- 同期エラー（欠落や挿入など）が入力に依存する場合，容量解析が困難である。
- 入力相関同期エラーチャネルの容量達成条件を特定し，具体的な符号化方式を開発する。
- 入力相関同期エラーチャネルにおいて，定常エルゴード入力源で情報容量が達成される条件を導出した。
- DNAベースのデータストレージシステム等を含む広範なチャネルに対して，この結果が適用可能である。
- Pernice-Li-WoottersやBrakensiek-Li-Spangの手法を組み合わせることで，multi-traceチャネルの具体的な容量達成符号を設計した。
ニューラルネットワークとデータセットの効率的な圧縮 [cs.LG, cs.AI, cs.IT, math.IT, math.OC, math.ST, stat.TH]目的：ニューラルネットワークとデータセットの圧縮による汎化性能の向上
- 機械学習において，モデルの汎化性能は重要であり，過学習を防ぐための様々な手法が研究されている。
- モデルの複雑さとデータ量とのバランスが難しく，高精度なモデルはパラメータ数が多くなりがちである。
- モデルとデータセットの圧縮を通して，汎化性能を高める最適な手法を確立することを目指す。
- アルゴリズム情報理論とニューラルネットワークプルーニングを組み合わせ，モデルの汎化性能を向上させる効果的なデータ圧縮手法を特定した。
- パラメータの疎性をモデル記述長の有効な近似として捉え，$\ell_0$正則化学習を用いてMDL最適化を近似的に実現した。
- 提案手法は，画像とテキストデータセットにおいて，高い圧縮率と精度の維持，短いデータ記述長の実現を検証により示した。
高速化された汎用二段階近似トップK選択 [cs.RO, cs.MA, cs.LG, cs.DS]目的：配列中の上位K個の要素の特定
- 機械学習アルゴリズムにおいて頻出する処理であり，アクセラレータの性能を左右する
- アクセラレータは密行列乗算に最適化されており，トップK選択はボトルネックとなりやすい
- より効率的に入力サイズを削減し，トップK選択の高速化を実現すること
- 第一段階で各分割から上位K'個の要素を選択する汎用化により，入力サイズの削減効果が向上した。
- 既存手法と比較して，期待リコールの理論的上限が2倍に改善された。
- Cloud TPUv5e上での実装により，リコールを損なうことなく，約10倍の高速化が達成された。
速度を優先する計画：マスク拡散言語モデルのための間引きスケジュール [cs.CY, cs.RO, cs.CL, cs.AI, cs.IT, cs.LG, cs.NE, math.IT]目的：マスク拡散言語モデルにおける高速非自己回帰的テキスト生成
- 近年，大規模言語モデルの高速化が求められており，非自己回帰型生成モデルが注目されている。
- 既存の並列アンマスク手法は，位置間の相互作用を無視し，速度が低下する傾向にある。
- 並列アンマスク時のエントロピー増加の上界を最小化する間引きスケジュールを提案し，速度と品質のトレードオフを改善する。
- 提案手法DUSは，モデルの修正なしに最大5.8倍の高速化を実現し，速度と品質のバランスを改善する。
- 数学，コード，常識，指示応答など，多様なベンチマークにおいて，既存手法を上回る性能を示す。
- DUSは，適応サンプラーのポストフィルターとしても有効であり，性能向上に貢献する。
義務論的議論 [cs.AI, cs.LO]目的：義務論的議論の意味論の定義
- 規範や義務を扱う議論の基礎を築く上で重要である。
- 既存の意味論では，義務の衝突時に弱い許可を扱えない。
- 弱い許可を扱える新たな義務論的議論の理論を提案する。
- 従来のグラウンデッド意味論では弱い許可が扱えないことが再確認された。
- 弱い許可をサポートする新たな意味論を提案した。
- 提案手法は，義務の衝突時にも適切な議論結果を得ることを可能にする。
ユークリッド幾何を用いた局所情報理論的安全性 [cs.IT, cs.CR, math.IT]目的：離散無記憶線形盗聴路における安全な通信の局所的特性の調査
- 情報セキュリティは現代社会において不可欠であり，その高度化が常に求められている。
- 盗聴路における安全性評価は一般に複雑であり，効率的な手法が課題となっている。
- 局所的な幾何学的近似を用いることで，安全性を評価する際の計算量を削減することを目指す。
- 提案手法により，制約付き最適化問題を扱いやすい二次計画問題へと変換することが可能となった。
- 局所的な秘密容量の近似的な公式を導出し，チャネルの内部的な漏洩効率を定量化する新たな係数を定義した。
- 導出された局所的な係数と，真の相互情報に基づくグローバルな係数の関係性について評価を行った。
CodeClash：目標指向型ソフトウェアエンジニアリングのベンチマーク [cs.SE, cs.AI]目的：目標指向型ソフトウェアエンジニアリングにおける言語モデルの評価
- ソフトウェア開発は，単なるタスクの解決だけでなく，高レベルな目標達成が重要である。
- 既存のベンチマークは具体的なタスクに偏っており，言語モデルの目標達成能力を十分に評価できていない。
- 言語モデルが，明示的な指示なしに反復的にコードを開発し，よりオープンな目的を達成できるか検証する。
- CodeClashは，言語モデルが競争的な目的を達成するために最良のコードベースを構築する多段階トーナメントのベンチマークである。
- モデルは，対戦相手のコードを分析し，テストスイートを作成するなど，コードベースを改善する方法を自律的に決定する必要がある。
- 実験の結果，モデルは戦略的思考に限界があり，長期的なコードベースのメンテナンスにも苦戦することが示された。
Cobble：量子計算線形代数のブロック符号化のコンパイル [cs.PL, quant-ph]目的：量子計算線形代数のためのブロック符号化のコンパイル言語
- 量子アルゴリズムは，シミュレーションや回帰などに応用でき，古典アルゴリズムを凌駕する可能性がある。
- 量子アルゴリズムは古典的なメモリ管理が難しく，効率的な量子回路の実装が課題である。
- Cobbleは，ブロック符号化を扱う高水準言語を提供し，効率的な量子回路の自動生成を目指す。
- Cobbleは，量子表現の行列を操作するための高水準な表記法を提供し，正しい量子回路を自動的に生成する。
- Cobbleは，プログラムの実行時間と空間使用量を分析し，量子特異値変換などの最新技術を用いた最適化を行う。
- シミュレーション，回帰などのベンチマークで，最適化されていないベースラインと比較して2.6倍から25.4倍の高速化を実現した。
ガロア環上のリード・ソロモン符号と畳み込みリード・ソロモン符号のリスト復号 [cs.IT, cs.CR, math.IT]目的：ガロア環上のリード・ソロモン符号および畳み込みリード・ソロモン符号のリスト復号に関する研究
- 近年，ゼロ知識システムにおける需要が高まり，ガロア環上の符号に関する研究が重要視されている。
- ガロア環上の符号の復号能力に関連する近接ギャップについては，有限体上の符号ほど知見が蓄積されていない。
- この研究は，ガロア環上のリード・ソロモン符号と畳み込みリード・ソロモン符号のリスト復号能力を向上させることを目指す。
- ガロア環上のリード・ソロモン符号に対し，復号半径 $1-\sqrt{r}$ でリスト復号が可能であることを示した。
- ガロア環上の畳み込みリード・ソロモン符号のリスト復号半径は，有限体上の符号と同様にシングルトン界限に到達することを示した。
- 畳み込みリード・ソロモン符号のリストサイズを $O(\frac{1}{\varepsilon^2})$ まで改善し，平均半径における緩和された一般化シングルトン界限を満たすことを示した。
半径補償：リーマン多様体上のチャートベース生成モデルにおける半径歪みの修正 [cs.LG, cs.AI, cs.IT, math.DG, math.IT, stat.ML]目的：リーマン多様体上のチャートベース生成モデルにおける基底分布の特性
- 多様体上の生成モデルは，複雑なデータ構造を捉える上で重要である。リーマン多様体を用いることで，データの幾何学的な特徴を考慮できる。
- 従来のチャートベース生成モデルでは，チャートや曲率の違いにより，接空間のスケールと測地線半径の関係が変化する問題があった。
- 測地線半径の尤度，チャート不変な半径フィッシャー情報，接空間の等方性を同時に満たす基底分布を確立し，モデルの安定性と曲率推定の精度向上を目指す。
- 提案手法である半径補償（RC）は，ユーザー指定の一次元法則に従った測地線半径を実現し，チャートを数値的プレコンディショナーとして活用する。
- RCを用いることで，訓練の安定性が向上し，より明確な曲率推定が可能になる。曲率がチャートによる歪みを補正する必要がなくなる。
- バランスの取れた指数チャートを導入することで，モデルの密度分布を変化させずに条件付けを改善し，統計的な意味と数値的な条件付けを分離した。
有限サービス時間下における衛星メガコンステレーションのエルゴード容量と最適なハンドオーバー [cs.IT, math.IT]目的：衛星メガコンステレーションにおけるエルゴード容量の特性評価
- 宇宙通信において，高スループットかつ低遅延な通信を実現するため，衛星メガコンステレーションの活用が重要である。
- 既存研究では，現実的なハンドオーバー戦略やサービス時間に対応したエルゴード容量の解析が困難であった。
- 任意のハンドオーバー戦略とサービス時間下におけるエルゴード容量の解析手法を確立し，最適なハンドオーバー戦略を提案すること。
- 提案手法により，衛星リンクをシャドウド・ライス型フェージングとしてモデル化し，半確率的な衛星チャネルを導入することで，任意のハンドオーバー戦略下でのエルゴード容量を解析可能となった。
- 非協調ハンドオーバー下では，更新理論を用いて持続的な容量を導出し，既存研究の容量との関係を明らかにした。
- 最適なハンドオーバーは非線形分数計画として定式化され，Dinkelbach法に基づいた明示的な決定ルールが得られ，サービス容量を最大化する戦略が最適解に近似することが示された。
3値様相論理における半位相空間上の公理的理論としての宣言的分散アルゴリズム [cs.LO, cs.DC]目的：分散アルゴリズムの形式仕様
- 分散システムの設計において，正当性と信頼性の保証は不可欠である。
- 分散アルゴリズムの複雑さから，形式的な検証が困難である。
- 様相論理による公理的アプローチで，アルゴリズムの本質を捉え，検証を容易にすること。
- 分散アルゴリズムを様相論理による公理的理論として形式的に記述する手法が提案された。
- 提案手法は，投票，ブロードキャスト，合意プロトコルに適用され，既存の産業プロトコルにおける誤りの発見にも貢献した。
- このアプローチにより，より精密な仕様と，人間および機械による検証の可能性が広がる。
トーラスパズルにおけるプッシュ数のほぼ最適上限 [cs.DS]目的：トーラスパズルを解くための回転回数の上限
- 行列の要素並べ替え問題であり，計算機科学における効率的なアルゴリズム設計の基礎となる。
- 既存の上限が最適解との乖離が大きく，より効率的な解法が求められていた。
- プッシュ数の上限を改善し，既存の上界・下界のギャップを縮小することを目指す。
- 本研究では，より制限されたモデルにおいて，$O(mn \cdot \log \max \{m, n\})$回の回転でトーラスパズルを解くアルゴリズムを提案した。
- これにより，プッシュ数の上限を改善し，既存の上界・下界のギャップを$\Theta(\max\{m,n\})$から$\Theta(\log \max\{m, n\})$に縮小することに成功した。
安定化符号チャネル変換：繰り返し符号を超えてハッシュ化境界を改善 [cs.IT, math.IT, quant-ph]目的：ハッシュ化境界の改善
- 量子情報理論において，効率的な量子誤り訂正は重要課題である。特に，ハッシュ化による誤り訂正の限界を理解することは，実用的な量子通信を実現する上で不可欠である。
- 従来のハッシュ化境界は，必ずしも厳密ではなく，改善の余地がある。特定の非対称パウリチャネルにおいて，より高い符号化率を達成することが困難であった。
- 安定化符号をチャネル変換として利用することで，誘導されたチャネルに対するハッシュ化境界を適用し，従来の境界を上回る符号化率の達成を目指す。
- 任意の安定化符号をチャネル変換として一般化し，物理パウリチャネル下での論理パウリ誤りおよび症候群の関節分布を計算する手法を確立した。
- 小さな変換に対する構造化探索を行い，偏った独立した誤りを持つパウリチャネルファミリーに対して，ベースラインのハッシュ化境界を改善するインスタンスを報告した。
- 本研究は，量子誤り訂正におけるハッシュ化境界の適用範囲を拡大し，より効率的な符号設計の可能性を示唆する。
パス幅3の評価制約グラフにおける全ての昇順は指数関数的である [cs.DM, cs.DS]目的：擬似ブール関数の最大化問題における厳密な局所探索の限界
- 組み合わせ最適化問題の複雑さを評価制約充足問題(VCSP)で捉えるアプローチが重要である。
- VCSPの制約グラフの疎性は，問題の複雑さに影響するが，その影響は未だ不明な点が多い。
- パス幅3の制約グラフにおいても指数関数的な探索が必要となることを示す。
- パス幅4以上の疎なVCSPでは，全ての昇順が指数関数的に長くなることが示されていた。
- 本研究では，パス幅3のVCSPにおいて，指定された初期割り当てから指数関数的に長い昇順が存在する構成を提示した。
- これにより，単純なパス幅3の評価制約グラフ上でも，厳密な局所探索アルゴリズムは指数関数的なステップを必要とされることが結論付けられた。
高速量子化行列乗算 I [cs.IT, cs.AI, math.IT]目的：量子化行列乗算の効率化
- 大規模言語モデルの普及に伴い，計算効率が重要となっている。
- 量子化による計算効率化において，レートと歪みのトレードオフが課題。
- 事前統計情報なしでの汎用的な量子化手法の性能評価と解析。
- 量子化レートと歪みの間の情報理論的なトレードオフを再検討した。
- 一般的な量子化スキーム（absmax INT，FP）の性能を比較・評価した。
- これらのスキームに対するヒューリスティック近似を導出した。
サイコロのようなゲーム：分散システムにおける共通の乱数源 [cs.GT, cs.LO, cs.MA]目的：分散システムにおける共有乱数源の特性と最適戦略
- 分散システムにおいて，効率的な合意形成やセキュリティ確保には，質の高い乱数が不可欠である。
- 既存手法では，乱数源の共有による利点を十分に活用できていない場合がある。
- 共有乱数源を用いた分散システムの最適な戦略を分析し，乱数資源の効率的な配分方法を確立する。
- 本研究では，Dicey Gamesというフレームワークを導入し，共有乱数源の特性を形式的に分析した。
- チームがペア間で乱数を共有する場合でも，1/4以上の確率で勝利できることを示した。
- 最適戦略の存在，表現，計算複雑性を明らかにし，限られた乱数資源の最適配分に関する考察を行った。