arXiv雑要約
プログラム - 2025/12/16 公開
コストを考慮したLLMベースのオンラインデータセット注釈 [cs.LG, cs.CL, cs.IT, math.IT]目的：大規模言語モデルを用いた効率的かつ正確なデータセット注釈
- データセットの品質は機械学習モデルの性能に不可欠であり，大規模な注釈付きデータセットの構築が重要である。
- LLMを活用した自動注釈はコストがかかるため，効率的な手法が求められている。
- 文脈埋め込みに基づいてLLMを選択し，コストと信頼性のバランスを図ることで注釈コストを削減する。
- 提案手法CaMVoは，既存の多数決方式と同等またはそれ以上の精度を達成する。
- CaMVoは，多数決方式に比べて大幅なコスト削減を実現する。
- 動的な注釈環境において，CaMVoは実用的かつ堅牢なソリューションとなる。
論理的制約項の同値性に関する特性化：存在的制約項によるアプローチ [cs.CL, cs.LO]目的：論理的制約項の同値性判定
- 論理的制約項書き換えは，整数やビットベクトル等の組み込みデータ型をサポートする強力なフレームワークである。
- 制約項の同値性に関する研究は十分に進んでおらず，実用的な分析や応用において課題となっている。
- 存在的制約項という新しい概念を導入し，制約項の同値性を形式的に判定する手法を開発する。
- 本研究では，存在的制約項への埋め込みを通じて，制約項の同値性を特徴づける複数の健全かつ完全な解法を提示する。
- 特に，同値性チェックを容易にするための完備な特徴付けと，理論的な分析を目的とした完備な特徴付けの二つを提案する。
ブートストラップによるホップ還元器を用いた，より高速な負の長さの最短経路計算 [cs.DS]目的：負の長さの最短経路計算の効率化
- グラフ理論は，ネットワーク分析や最適化問題など，様々な分野に応用されている重要な研究分野である。
- 従来のアルゴリズムでは，大規模グラフに対する最短経路計算に時間がかかるという課題があった。
- 入力グラフの小さな部分グラフに対してホップ還元器を反復的に増幅・拡張することで，計算効率の向上を目指す。
- 本研究では，既存のアルゴリズムよりも優れた$\tilde{O}(m n^{3/4} + m^{4/5} n)$のランダム化実行時間を達成した。
- 特に，$m \geq n^{5/4}$の場合には$\tilde{O}(mn^{3/4})$， $m \leq n^{5/4}$の場合には$\tilde{O}(m^{4/5} n)$となる。
- 新しい技術として，既存のホップ還元補助グラフを，ブートストラッププロセスで置き換えている。
二次クンマー拡大からの和階数符号の明示的構成 [cs.IT, math.IT]目的：和階数符号の新たな構成
- 符号理論において，和階数符号は誤り訂正能力が高く，様々な通信システムへの応用が期待されるため重要である。
- 和階数符号に関する研究はまだ発展途上であり，効率的な構成法やパラメータ決定が課題となっている。
- 二次ガロア拡大を用いることで，既存の構成よりも長いブロック長を持つ和階数符号を構成し，パラメータを決定することを目的とする。
- 代数的関数体から和階数符号を構成する新しい手法を提案した。
- 提案手法により，符号の次元や最小距離などのパラメータを明示的に決定できた。
- 特に，楕円関数体を用いた具体例を示すことで，構成の有効性を示した。
LLMによるコード生成における誤りの評価尺度としての不整合性 [cs.PL, cs.AI, cs.LG, cs.SE]目的：LLMによるコード生成における誤りの可能性の評価
- LLMは自然言語によるプログラミングタスクにおいて大きな成功を収めている。その信頼性向上は重要である。
- 生成されたコードのバグ検出には，正解のコードや仕様書といったオラクルが必要となる場合が多い。
- オラクルなしで，生成されたコードの正しさを推定する手法の開発を目指している。
- 提案手法「不整合性」は，オラクルなしで効率的に誤りの下限を推定できる。
- 実験の結果，平均的なタスクにおいて，不整合性に基づく手法は誤ったプログラムの約3分の2を自動的に識別できた。
- オラクルに基づく評価を，不整合性に基づく評価で代替できることが示された。
局所最適解を見つけるのは容易だが，2つはどうか？ [cs.DS, cs.CC]目的：2つの局所最適解の計算困難性
- 局所探索は，組合せ最適化問題において重要な手法であり，その複雑性の理解が不可欠である。
- 重み付き問題では局所探索が困難だが，非重み付き問題では多項式時間で解ける場合もある。
- 非重み付き問題における2つの局所最適解の探索の複雑性を明らかにすること。
- 最大独立集合，最小支配集合，Max SAT，Max Cutなど，いくつかの自然な非重み付き局所探索問題において，2つの局所最適解の計算がNP困難であることが示された。
- 2つ以上の局所最適解を見つけるための，いくつかの解けるケースについても議論された。
- これにより，局所探索問題の複雑さに対する新たな視点が得られた。
連合学習における信頼性の低い通信下でのコード強制型ロバストなセキュア集約 [cs.IT, math.IT]目的：信頼性の低い通信環境下におけるプライバシー保護型連合学習のセキュア集約手法
- プライバシー保護とモデル精度を両立させる連合学習は，データ共有を促進し，AI発展に不可欠である。
- 通信の信頼性が低い場合，ノイズの連携が乱れ，集約誤差や参加率の低下を引き起こし，精度が損なわれる。
- 信頼性の低い通信環境下でも正確なモデル復元と強力なプライバシー保護を実現する手法を開発する。
- 提案手法SecCoGCは，信頼性の低い通信環境下でもロバストな性能を発揮し，既存手法と比較してテスト精度が20%-70%向上した。
- SecCoGCは，プロトコル各層におけるプライバシーを評価し，ノイズ間の相関や線形結合を考慮することで，高いプライバシー保護を実現する。
- 二値の結果に基づくグローバルモデル復元に対する収束解析を提供し，理論的な根拠を確立した。
論理制約付き書き換えと等価変換の可換性の回復（完全版） [cs.LO]目的：論理制約付き書き換えシステムの効率的な実装と理論的性質の確立
- 現代のソフトウェアおよびハードウェア検証において，書き換えシステムは不可欠な役割を果たしている。
- 論理制約付き書き換えシステムでは，書き換え規則の適用と等価変換が複雑に絡み合っている。
- 最も一般的な制約付き書き換えが等価変換と可換となるようにすることで，探索空間の肥大化を抑制する。
- 本研究では，存在的に制約された項に対する最も一般的な制約付き書き換えの概念を提案した。
- 提案する新しい書き換え形式は，既存の書き換え形式を包含し，可換性という重要な性質を持つ。
- これにより，実装時の探索空間の肥大化を緩和し，より正確で効率的なツール開発に貢献できると期待される。
行と能力：モダリティとしての効果 [cs.PL]目的：効果システムの比較分析
- プログラムにおける副作用のモジュール化と安全性の確保は重要である。
- 行多型と能力ベースの効果システムでは，効果追跡の根本的な違いが不明確である。
- モダリティ効果型を用いて，効果システムの共通基盤を確立し比較分析を可能にする。
- 本研究では，既存の行と能力ベースの効果システムをモダリティ効果型に変換する手法を提案した。
- これらの変換は型と意味論を保持し，異なる効果システムのメカニズムの本質を明らかにした。
- 効果追跡戦略の違いを直接分析し，言語設計に関する洞察を提供する。
RC-Gossip：レート変化型ゴシップによるクラスタネットワークにおける情報鮮度 [cs.CL, cs.IT, cs.NI, eess.SP, math.IT]目的：クラスタネットワークにおける情報鮮度
- 情報伝達の効率化は，様々なネットワークにおいて重要な課題である。
- 従来のゴシッププロトコルでは，ネットワーク全体の鮮度を均一に保つことが困難である。
- 情報が必要なノードに選択的にゴシップを行うことで，ネットワーク全体の鮮度向上を目指す。
- 提案手法RC-Gossipは，ネットワーク内の鮮度が高いノード数に応じてゴシップレートを変化させることで，効率的な情報伝達を実現する。
- 更新報酬に基づく解析により，RC-Gossipが従来のゴシップ手法と比較して，クラスタネットワークにおけるノードの鮮度を大幅に向上させることが示された。
- 最適なクラスタサイズにおいて，RC-Gossipは高い情報鮮度を維持することが確認された。
マルフロウ：Androidマルウェア検知のための異種フロー意味論の文脈を考慮した融合 [cs.CR, cs.SE]目的：Androidマルウェアの検知
- Androidアプリのセキュリティ確保は重要であり，静的解析はそのための基礎技術である。
- 既存手法では，異なる種類のフロー間の意味的補完性を活かしきれていない。
- 異種フローの意味論を文脈を考慮して融合し，より高精度なマルウェア検知を目指す。
- マルフロウは，制御フロー，データフロー，コンポーネント間通信を異種情報ネットワークとしてモデル化する。
- フロー2vecにより，文脈に基づいたHIN埋め込みを生成し，アプリの正確な表現を学習する。
- 実験結果から，マルフロウは既存手法を上回り，フロー2vecの有効性が確認された。
スマートコントラクトにおける状態更新の一貫性に関する脆弱性の理解 [cs.SE]目的：スマートコントラクトにおける状態更新の一貫性に関する脆弱性の実態解明
- ブロックチェーン技術の発展に伴い，スマートコントラクトの利用が拡大している。
- スマートコントラクトの状態更新における不整合は，セキュリティリスクとなり得る。
- 実世界プロジェクトにおける脆弱性の分析を通じて，開発支援を目指す。
- 116件の状態更新の一貫性に関する脆弱性を352のプロジェクトから調査し，原因，修正戦略，悪用方法をまとめた。
- その結果，11の重要な知見が得られ，開発者やツール開発者への示唆を与える。
- 開発したプロトタイプチェッカーは，64のGitHubプロジェクトで問題を検出し，19プロジェクトで修正が確認された。
AI開発における倫理的慣行：役割と地域における実証研究 [cs.CY, cs.AI, cs.HC, cs.SE]目的：AI開発に関わる人々の倫理的認識，慣行，知識
- AI技術の急速な発展に伴い，倫理的ガイドラインの必要性が高まっている。
- AI開発における倫理的配慮が，役割や地域によって異なっている。
- AI開発ライフサイクル全体における倫理的決定を支援する。
- 役割，地域，属性によって，AI倫理原則への理解度に差が見られた。
- 倫理的課題に対応するため，関係者間の協調と役割に合わせたアプローチが重要である。
- AI開発における倫理的意識を高めるための教育戦略が求められる。
解けるタプルパターンとそのプログラム検証への応用 [cs.PL]目的：再帰的データ構造を扱うプログラムの不変性推論
- プログラムの信頼性向上が不可欠であり，自動検証技術の進展が求められている。
- 再帰的データ構造を扱うプログラムの完全自動検証は未だ困難である。
- タプルパターンを用いて，より効率的な不変性推論を実現し，プログラム検証を支援する。
- 解けるタプルパターン(STP)と連言STP(CSTP)という新しい形式主義を導入した。
- STPは少数の正例から効率的に推論でき，負例は不要である点が特徴である。
- CSTP推論をCHCソルバーに組み込み，リスト型データ構造を扱うプログラム検証ツールを強化し，CHC-COMP 2025のADT-LINカテゴリで顕著な成果を上げた。
高速な証明検証によるコンパクトなILPの設計 [cs.SI, physics.soc-ph, cs.DS]目的：パラメータ化された問題に対するコンパクトな整数線形計画問題 (ILP) の設計
- パラメータ化された問題の効率的な前処理は，計算複雑性において重要な課題である。
- 多項式カーネルが存在しない問題に対する効果的な前処理手法が不足している。
- WK[1]クラスに属する問題をILPとして表現し，効率的な前処理を可能にすること。
- 本研究では，インスタンスを多項式時間でpoly(k)制約のILPに帰着できる問題が，WK[1]クラスと一致することを示した。
- また，いくつかの問題（r-Way Cut，Steiner Treeなど）に対して，効率的な証明検証プロトコルを設計し，コンパクトなILPによるモデリングを可能にした。
- 重み付き頂点被覆問題に対しても，明示的なILP/MILP定式化を提示し，ILP指向の前処理手続きの研究基盤を提供する。
近似最近傍探索のための高速収束近傍グラフ [cs.DC, cs.AR, cs.NI, cs.DS]目的：近似最近傍探索における効率的な近傍グラフ構造
- 高次元データにおける類似検索は，画像認識や情報検索など多岐にわたる応用分野で重要である。
- 既存の近傍グラフ法は，最悪の場合の検索精度が保証されておらず，理論的な裏付けが不足している。
- 本研究では，理論的保証付きで高速な近似最近傍探索を実現する新たな近傍グラフ構造を提案する。
- 提案手法であるα-convergent graph(α-CG)は，シフトされたスケーリングされた三角形不等式に基づき，エッジを効果的に刈り込む。
- α-CGは，特定の条件下において，正確な最近傍を多項式時間で発見可能であり，それ以外の場合でも近似最近傍を高速に探索できる。
- 実験結果から，提案するα-convergent neighborhood graph(α-CNG)は，既存手法と比較して距離計算回数および検索ステップ数を大幅に削減できることが示された。
単一始点最短経路問題に対するDuan et al. (2025) アルゴリズムの実装と簡単な実験分析 [cs.DS]目的：単一始点最短経路問題に対するDuan et al. (2025) アルゴリズムの実装と性能評価
- グラフ理論は，ネットワーク分析や経路最適化など，様々な分野で不可欠な役割を果たしている。
- 従来のダイクストラ法は実装が容易だが，大規模グラフでは計算効率が課題となる場合がある。
- より効率的な最短経路アルゴリズムの開発が求められており，特に大規模グラフへの適用が重要である。
- Duan et al. (2025) アルゴリズムをC++で忠実に実装し，その性能をダイクストラ法と比較した。
- 理論上優れた漸近的複雑度を持つDuan et al. (2025) アルゴリズムだが，大きな定数項の影響で，実用上はダイクストラ法よりも遅いことが示された。
- テストされた疎グラフのサイズ（数千万頂点を含む）において，Duan et al. (2025) アルゴリズムはダイクストラ法に劣るパフォーマンスを示した。
RTLアサーション失敗解決のためのLLMによる知識ツリー学習 [cs.AI, cs.SE]目的：RTLアサーション失敗の解決における再利用可能な知識の構造化
- 現代のハードウェア検証においてデバッグコストが大きく，効率化が求められている。
- LLMは有望視されるも，エンジニアの専門知識を正確に捉えきれない場合がある。
- 過去の事例からデバッグ知識を抽出し，構造化された知識ツリーとして活用する。
- GROVEは，LLMによって知識ツリーを学習・構成する階層型知識管理フレームワークである。
- 知識ツリーは，RTLアサーション失敗を解決するための知識を効果的に整理し，再利用を可能にする。
- 評価実験により，GROVEはpass@1とpass@5において一貫した改善を示し，構造化された知識進化の価値を実証した。
回転アンテナを用いたセルフリー通信 [cs.CL, cs.IT, math.IT]目的：セルフリーシステムにおける合計レート最大化
- 無線通信における容量向上が常に求められており，新たな技術が不可欠である。
- セルフリー通信では，アクセスポイントとユーザーの割り当てとビームフォーミングが課題となる。
- 回転アンテナの空間的自由度を活用し，通信性能の向上を目指す。
- 提案する回転アンテナを用いたセルフリーシステムは，既存手法と比較して大幅な性能向上を示す。
- アクセスポイントとユーザーの割り当て問題を二段階戦略で解決する。
- 回転アンテナの指向方向を最適化するために，分数計画法と逐次凸近似法を用いる。
TritonForge：プロファイリングに基づくTritonカーネル自動最適化フレームワーク [cs.SE]目的：Tritonカーネルの自動最適化
- 機械学習の性能向上にはGPUカーネルの最適化が不可欠であり，計算資源の効率的な活用が求められる。
- GPUアーキテクチャの深い理解と低レベルの性能トレードオフの知識が必要であり，最適化作業は専門性と労力を要する。
- プロファイリング結果に基づくカーネルの自動最適化を通じて，開発者の負担軽減と性能向上を目指す。
- TritonForgeは，カーネル分析，実行時プロファイリング，反復的なコード変換を統合し，最適化プロセスを効率化する。
- 多様なカーネルタイプにおいて，ベースライン実装と比較して最大5倍の性能向上を達成した。
- 最適化の成功率は平均1.76倍であり，自動GPU性能最適化研究の基盤を提供する。
再構成可能電磁構造の効率的かつ物理整合的なモデリング [eess.SP, cs.IT, math.IT]目的：再構成可能電磁構造の効率的かつ物理整合的なモデリング手法
- 無線通信やセンシングの性能向上に貢献する再構成可能電磁構造の研究が重要である。
- 既存手法は，計算効率と物理整合性の両立が難しく，正確な制御アルゴリズムの構築が課題である。
- 物理的に正確なパラメータ調整を可能にする，効率的なモデリングフレームワークを開発すること。
- 回路理論的アプローチと新たな形式主義を組み合わせることで，高速な計算を実現した。
- 一次の全波電磁界シミュレーションのみで，任意の再構成要素配置に対する放射パターンを算出可能である。
- 古典電磁気学の法則に整合し，アンテナ間結合や損失などの影響を正確にモデル化できることを検証した。
飽和集合の測度平均次元について [math.DS, cs.IT, math.IT]目的：飽和集合の測度平均次元の性質
- 力学系における複雑性の評価において，次元概念は重要な役割を果たす。
- 測度平均次元の計算は一般に困難であり，その性質解明が求められている。
- 飽和集合の測度平均次元に関する変分原理を確立し，次元構造を明確化すること。
- 飽和集合のBowen測度平均次元とpacking測度平均次元がKolmogorov-Sinai ε-エントロピーを通して関係付けられた。
- 飽和集合の上方容量測度平均次元が満次元を持つことが示された。
- 不変測度の汎用点の集合に対する測度平均次元と平均Rényi情報次元の一致が導かれた。
空間効率の良い対数因子を含まない量子誤り削減法 [quant-ph, cs.DS]目的：量子アルゴリズムの誤りを，対数因子を伴わない効率的な手法で削減すること
- 量子計算は，従来の計算機では困難な問題を解決する可能性を秘めている。誤り耐性は，実用的な量子計算機の実現に不可欠である。
- 既存の誤り削減法は，誤りの許容範囲を小さくするにつれて計算コストが指数関数的に増加する問題がある。
- 本研究は，より少ない計算資源で量子アルゴリズムの誤りを効果的に削減する手法を開発し，より複雑な量子アルゴリズムの構成を可能にすることを目指す。
- トランスデューサという量子計算モデルにおいて，誤りの削減に定数倍のオーバーヘッドで済む「精製」という手法が確立されている。
- 本研究では，この精製処理を大幅に簡略化し，より少ない空間と時間計算量で実現可能な新しい精製器を提案した。
- 提案手法は，アルゴリズムの健全性と完全性のギャップに対する依存性も改善しており，深層量子アルゴリズムの構成において有効である。
マルコフ連鎖とハードコア多参照アラインメントによる多標的検出のサンプル複雑性解析 [eess.SP, cs.IT, math.IT]目的：多標的検出問題におけるサンプル複雑性
- 単粒子クライオ電子顕微鏡の技術進歩に伴い，微細構造解析の重要性が増している。
- ノイズ下で未知の信号を効率的に検出することが困難である。
- 非独立同一分布な多参照アラインメントモデルへの帰着を通して，検出に必要なサンプル数を評価する。
- 一次元設定では，推定値の収束速度が対応する独立同一分布多参照アラインメントモデルと同等であることが示された。
- 二次元設定では，ハードコア配置モデルによって生成される指数混合ランダム場からの構造が確立された。
- 低SNR領域において，多標的検出モデルにおける信号推定に必要なパッチ数はノイズ分散の関数としてスケーリングする。
量子消去訂正における測定回数の削減：量子局所回復による手法 [quant-ph, cs.IT, math.IT]目的：量子消去訂正における測定回数および測定対象クダイト数の最小化
- 量子計算装置の発展には，測定コストとエラーの抑制が不可欠である。
- 量子消去訂正において，不要な測定が性能低下の原因となる可能性がある。
- 消去されたクダイトの訂正に必要な最小限の測定を明確化すること。
- 量子局所回復の概念を用いることで，消去されたクダイトの訂正に十分な関連のある安定化因子を形式的に定義した。
- 測定が必要な安定化因子観測値の最小数が明確化された。
- Delfosse, Iyer, Poulinの提案する一般化された表面符号において，δ個の消去を訂正するには，最大でδ個の頂点および面の測定で十分であることが示された。
一様クラス分離における敵対的障壁 [math.LO, cs.CC, cs.LO]目的：一様分離における構造的障害の特定
- 構成的算術の基礎理論を理解する上で重要。一様分離の限界を明らかにすること。
- 既存の分離障壁は，特定の証明技術に焦点を当て，一様分離の論理的構造自体を制限するものではなかった。
- HAにおける一様分離の論理的構造に内在するより根本的な制限を明らかにすること。
- 一様分離は，二つの異なる評価述語が並行して維持され，推論が一様表現可能な拡張 HA で行われる場合に，固定点構成の特別な事例となる。
- この制限は，ベイカー，ルディック，アーロンソンらの古典的な分離障壁よりも厳格であり，特定の相対化，自然化，代数化技術を制限するのではなく，HA 内の一様分離の論理的形態を制約する。
- 本研究は，意味内容に依存しない構造的障害が，一様分離における本質的な限界であることを示唆している。