A gentle tutorial and a structured reformulation of Bock's algorithm for minimum directed spanning trees
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Dependency ParsingSimilar Papers 제목 키워드 기반
Tutorial on Deep Learning for Human Activity Recognition
Activity recognition systems that are capable of estimating human activities from wearable inertial sensors have come a long way in the past decades. Not only have state-of-the-art methods moved away from feature enginee…
Activity RecognitionDeep LearningFeature EngineeringHuman Activity RecognitionA Gentle Introduction to Deep Nets and Opportunities for the Future
The first half of this tutorial will make deep nets more accessible to a broader audience, following “Deep Nets for Poets” and “A Gentle Introduction to Fine-Tuning.” We will also introduce GFT (general fine tuning), a l…
Getting Started with Particle Metropolis-Hastings for Inference in Nonlinear Dynamical Models
This tutorial provides a gentle introduction to the particle Metropolis-Hastings (PMH) algorithm for parameter inference in nonlinear state-space models together with a software implementation in the statistical programm…
State Space ModelsA tutorial on the dynamic Laplacian
Spectral techniques are popular and robust approaches to data analysis. A prominent example is the use of eigenvectors of a Laplacian, constructed from data affinities, to identify natural data groupings or clusters, or …
BOCK : Bayesian Optimization with Cylindrical Kernels
A major challenge in Bayesian Optimization is the boundary issue (Swersky, 2017) where an algorithm spends too many evaluations near the boundary of its search space. In this paper, we propose BOCK, Bayesian Optimization…
Bayesian Optimization