論文の概要: A gentle tutorial and a structured reformulation of Bock's algorithm for minimum directed spanning trees
- arxiv url: http://arxiv.org/abs/2603.27530v1
- Date: Sun, 29 Mar 2026 05:44:07 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-31 23:18:45.006616
- Title: A gentle tutorial and a structured reformulation of Bock's algorithm for minimum directed spanning trees
- Title（参考訳）: 最小方向スパンニング木に対する緩やかなチュートリアルとボックアルゴリズムの構造化
- Authors: Yuxi Wang, Jungyeul Park,
- Abstract要約: そこで本研究では,ボックの1971年アルゴールの最小配向木構築手順の構造化について述べる。
非プロジェクティブグラフベースの依存性解析のための正確なデコーダとして、その関連性を強調します。
- 参考スコア（独自算出の注目度）: 14.064332086144406
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: This paper presents a gentle tutorial and a structured reformulation of Bock's 1971 Algol procedure for constructing minimum directed spanning trees. Our aim is to make the original algorithm readable and reproducible for modern readers, while highlighting its relevance as an exact decoder for nonprojective graph based dependency parsing. We restate the minimum arborescence objective in Bock's notation and provide a complete line by line execution trace of the original ten node example, extending the partial trace given in the source paper from initialization to termination. We then introduce a structured reformulation that makes explicit the procedure's phase structure, maintained state, and control flow, while preserving the logic of the original method. As a further illustration, we include a worked example adapted from {jurafsky-martin-2026-book} for dependency parsing, showing how a maximum weight arborescence problem is reduced to Bock's minimum cost formulation by a standard affine transformation and traced under the same state variables.
- Abstract（参考訳）: 本稿では,ボックの1971年アルゴル法を整理し,最小方向のスパンニング木を構築するための簡単なチュートリアルと構造的再構成について述べる。
本研究の目的は,非プロジェクティブグラフによる依存性解析の正確なデコーダとしての妥当性を強調しつつ,アルゴリズムの可読性と再現性を現代読者に示すことである。
我々は,Bockの表記における最小アーボラッセンス目標を復元し,元の10ノード例の行実行トレースによる完全ラインを提供し,ソースペーパーに与えられた部分トレースを初期化から終了まで拡張する。
次に,プロシージャの位相構造,維持状態,制御フローを明確にし,元の手法の論理を保ちながら構造化された再構成を導入する。
さらに、従属解析のために {jurafsky-martin-2026-book} を応用した実例を挙げ、標準アフィン変換によるボックの最小コストの定式化に最大重量アーボラッセンス問題がいかに還元され、同じ状態変数の下でトレースされるかを示す。
関連論文リスト
- Efficient Zero-Shot Inpainting with Decoupled Diffusion Guidance [28.412652896195684]
拡散モデルは、塗装や局所的な修正といった画像編集タスクの強力な先駆者として現れてきた。
本稿では,ガウス後続遷移のサンプリングをシンプルかつ効率的に行う新しいサロゲートを提案する。
提案手法は,微調整ベースラインに比べて強い観測一貫性を実現し,コヒーレントで高品質な再構成を実現する。
論文 参考訳（メタデータ） (2025-12-20T13:32:06Z) - Trunc-Opt vine building algorithms [0.0]
本報告では, トリュンケートブドウのウェイト(Weight of truncated Vine)と呼ばれる, 与えられたデータにトリュンケートブドウを適合させる新しいスコアを提案する。
我々は、それらを活用して、切り刻まれたブドウを構築および符号化するアルゴリズムを提供する。
論文 参考訳（メタデータ） (2025-12-16T13:37:00Z) - LRANet++: Low-Rank Approximation Network for Accurate and Efficient Text Spotting [118.93173826110815]
高精度検出のための低ランク近似に基づく新しいパラメータ化テキスト形状法を提案する。
異なるテキストの輪郭間の固有形状相関を利用して、形状表現の一貫性とコンパクト性を実現する。
我々は、LRANet++と呼ばれるエンドツーエンドテキストスポッティングフレームワークを構築するために、拡張検出モジュールを軽量な認識ブランチに統合する。
論文 参考訳（メタデータ） (2025-11-08T03:08:03Z) - ProofFlow: A Dependency Graph Approach to Faithful Proof Autoformalization [10.021930888250546]
現在のアプローチでは、オリジナルの人間による議論の意味的意味と論理的構造を保存できない。
本稿では,構造的忠実度を主目的とする新しいパイプラインであるProofFlowを紹介する。
我々は184人の学部レベルの問題に対して,ステップバイステップのソリューションを手動でアノテートした新しいベンチマークを提示する。
また,構文的正しさ,意味的忠実度,構造的忠実度を評価するための新しい合成指標ProofScoreを導入する。
論文 参考訳（メタデータ） (2025-10-13T10:20:11Z) - Semi-Supervised Laplace Learning on Stiefel Manifolds [48.3427853588646]
グラフベースで教師付きサンプルを低ラベルレートで作成するためのフレームワークSequential Subspaceを開発した。
我々の手法は極めて低いレートで、高いラベルレートで達成できる。
論文 参考訳（メタデータ） (2023-07-31T20:19:36Z) - Structured Dialogue Discourse Parsing [79.37200787463917]
談話解析は、多人数会話の内部構造を明らかにすることを目的としている。
本稿では,符号化と復号化という2つの観点から,従来の作業を改善する原理的手法を提案する。
実験の結果,本手法は,STACでは2.3,Mollweniでは1.5,先行モデルでは2.3を上回った。
論文 参考訳（メタデータ） (2023-06-26T22:51:01Z) - Scalable Learning of Latent Language Structure With Logical Offline
Cycle Consistency [71.42261918225773]
概念的には、LOCCOは、トレーニング対象のセマンティクスを使用してラベルなしテキストのアノテーションを生成する、自己学習の一形態と見なすことができる。
追加ボーナスとして、LOCCOによって生成されたアノテーションは、神経テキスト生成モデルをトレーニングするために自明に再利用することができる。
論文 参考訳（メタデータ） (2023-05-31T16:47:20Z) - MLPruning: A Multilevel Structured Pruning Framework for
Transformer-based Models [78.45898846056303]
プルーニングは、大きな自然言語処理モデルに関連するメモリフットプリントと計算コストを削減する効果的な方法である。
我々は,頭部刈り込み,行刈り,ブロックワイズ刈りという3つの異なるレベルの構造化刈り込みを利用する,新しいマルチレベル構造化刈り込みフレームワークを開発した。
論文 参考訳（メタデータ） (2021-05-30T22:00:44Z) - Progressive Identification of True Labels for Partial-Label Learning [112.94467491335611]
部分ラベル学習(Partial-label Learning, PLL)は、典型的な弱教師付き学習問題であり、各トレーニングインスタンスには、真のラベルである候補ラベルのセットが設けられている。
既存のほとんどの手法は、特定の方法で解決しなければならない制約付き最適化として精巧に設計されており、計算複雑性をビッグデータにスケールアップするボトルネックにしている。
本稿では,モデルと最適化アルゴリズムの柔軟性を備えた分類器の新しいフレームワークを提案する。
論文 参考訳（メタデータ） (2020-02-19T08:35:15Z) - Stochastic tree ensembles for regularized nonlinear regression [0.913755431537592]
本稿では,非線形回帰のための新しいツリーアンサンブル法を開発し,これをXBARTと呼ぶ。
ベイズモデルからの正規化と探索戦略と計算効率のよい手法を組み合わせることで、新しい手法は最先端の性能を達成できる。
論文 参考訳（メタデータ） (2020-02-09T14:37:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。