Pith. sign in

REVIEW 3 major objections 5 minor 66 references

Bregman Conditional Random Fields: Sequence Labeling with Parallelizable Inference Algorithms

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Bregman conditional random fields replace the sequential Viterbi and Forward dynamic programs with parallelizable iterative Bregman projections, matching CRF accuracy on sequence labeling while training up to about seven times faster on…

desk verdict A promising new parallel inference idea that is currently not well-defined as written: Algorithm 1's initialization contradicts the KL projection derivation, and the iteration budget is unanalyzed. read the letter →

arxiv 2506.00732 v1 pith:H2OATZVD submitted 2025-05-31 cs.LG cs.CL

Caio Corro , Mathieu Lacroix , Joseph Le Roux This is my paper
classification cs.LGcs.CL MSC 68T0790C25
keywords sequencelabelingconditionalrandomfieldsiterativeBregmanprojectionsmeanregularizationFenchel-Younglossesmarginalpolytopeparallelinferencepartiallabels
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Standard linear-chain conditional random fields pay for their exactness with the Viterbi and Forward algorithms, which sweep through a sentence one position at a time and so barely exploit GPU parallelism. This paper proposes Bregman conditional random fields (BCRF), a linear-chain model that swaps the usual entropy over complete tag sequences for entropy on the marginal transition probabilities inside the variational form of the log-partition. That swap turns MAP and marginal inference alike into a Kullback-Leibler projection onto the marginal polytope, and the paper shows the polytope factors into even- and odd-position constraint sets so the projection can be computed by alternating Bregman projections whose subproblems are independent and closed-form. The payoff, on GPUs, is a drop-in parallel replacement for both Viterbi and Forward: experiments on part-of-speech tagging, joint segmentation and tagging, and named-entity recognition report accuracy on par with CRF, training up to about seven times faster, and better accuracy than mean field in the constrained settings where tag transitions are forbidden. The paper extends the same projection-based routine to learning from partial labels, so one parallel primitive drives the whole pipeline.

What carries the argument

The load-bearing object is the mean-regularized log-partition $B_Y(w)$, whose gradient $\nabla B_Y(w)$ yields the transition marginals of the BCRF distribution. Three identities carry the argument. First, the change of variables $q = Mp$ with entropy $H(q)$ replacing entropy over outputs turns $B_Y$ into a concave maximization over the marginal polytope with a simple analytical regularizer. Second, that maximization is a KL projection onto $\text{conv}(Y)$, which the paper characterizes as an integral polytope defined by flow-conservation constraints (7) and (8) on a layered arc graph (Proposition 2). Third, splitting the clusters by parity gives $\text{conv}(Y) = C_{\mathrm{even}} \cap C_{\mathrm{odd}}$, so iterative Bregman projections alternate between the two sets; each step splits into independent per-cluster KL projections with closed-form solutions (Appendix F). The Fenchel-Young loss with $\Omega = -H$ and its partial-label variant then reuse the same projection as the gradient, and Proposition 1 ties the whole scheme to approximate MAP by temperature annealing.

What would settle it

One decisive check: solve the entropy-regularized problem of Definition 1 exactly for short sentences with a standard convex solver, and measure the KL divergence between that exact projection and the 10-iteration output of Algorithm 1; if the divergence is large enough to change the decoded tag sequence, or if on sentences of thousands of tokens the accuracy gap between BCRF and CRF grows with length at the fixed iteration budget, the central promise of accuracy at a constant small number of parallel projections would be refuted in exactly the regime the method targets.

Watch

Extended reading notes

Core claim

The central claim is that entropic mean regularization removes the sequential bottleneck of CRF sequence labeling without giving up accuracy. A BCRF is defined through $$B_Y(w) = \max_{p \in \$\Delta$(Y)} \langle p, M^\top w\rangle + H(Mp) = \max_{q \in \text{conv}(Y)} \langle q, w\rangle + H(q),$$ so its marginal transition probabilities are $\nabla B_Y(w)$, the entropy-regularized maximizer over the marginal polytope $\text{conv}(Y)$. Because $\langle q, \mathbf{1}\rangle = n-1$ is constant on that polytope, computing $\nabla B_Y(\tau^{-1}w)$ is exactly a KL projection, $$\nabla B_Y(\$tau^{{-1}}$w) = \arg\min_{q \in \text{conv}(Y)} D_{KL}[q \| \exp(\$tau^{{-1}}$ w)],$$ and the paper characterizes the polytope by flow conservation on a layered arc graph (Proposition 2), then splits the constraints by odd and even positions so that $\text{conv}(Y) = C_{\mathrm{even}} \cap C_{\mathrm{odd}}$. Iterating KL projections onto the two sets (Algorithm 1) is the inference algorithm: each projection decomposes into independent per-cluster subproblems with closed-form solutions derived from the KKT conditions. The same subroutine computes the gradient of the mean-regularized Fenchel-Young loss for supervised learning and of the partial-label variant, making it the parallel replacement for both Viterbi and Forward; Proposition 1 (annealing $\tau$ drives $B_Y(\tau^{-1}w)$ to the MAP score) links marginal and MAP inference. Experimentally the paper reports BCRF at 5 or 10 projection iterations matching CRF accuracy across POS tagging, BIES segmentation, and NER, with training up to 7.3 times faster than CRF, while mean field visibly degrades when forbidden transitions encode well-formedness constraints.

Load-bearing premise

The load-bearing premise is that a fixed budget of 5 or 10 alternating Bregman projections lands close enough to the true KL projection onto the marginal polytope that both decoding and gradient-based training behave like exact CRF inference; the paper gives no convergence rate or error bound for this particular alternating scheme, and instead points to a related algorithm from the optimal-transport literature.

Editorial extensions

If this is right

  • GPU training of sequence taggers no longer needs the sequential Forward sweep: the BCRF loss uses the same parallel projection routine as inference, and the paper measures training speed-ups over CRF of up to roughly 7x for POS tagging and about 2x with BERT-based NER.
  • Decoding can replace Viterbi with the same projection routine followed by minimum-Bayes-risk tag selection; on POS tagging and NER, BCRF at 5 or 10 iterations matches Viterbi decoding accuracy and slightly improves on it in one BERT-large configuration.
  • In highly structured settings where forbidden transitions enforce well-formed outputs, BCRF stays close to CRF (within about one F-score point on Chinese and Japanese segmentation), whereas mean field drops ten points or more, making BCRF the viable parallel alternative there.
  • Learning from partial labels works with the same primitive: the partial Fenchel-Young loss is the difference of two projections, and on NER with only one entity type annotated per sentence BCRF recovers CRF-level F-scores, while mean field cannot even be applied in that regime.
  • Because $\lim_{\tau\to 0} B_Y(\tau^{-1}w)$ recovers the MAP score (Proposition 1), one implementation serves both marginal and MAP inference; the experiments fix $\tau^{-1} = 10$ throughout.
  • The same projection routine serves as the gradient of the partial-label loss by subtracting the projection onto $\text{conv}(\tilde{Y})$ from the projection onto $\text{conv}(Y)$, so weakly supervised training keeps the parallel structure.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The speed-up is fundamentally an occupancy argument: each IBP step does O(n|T|^2) work split into roughly n/2 independent closed-form projections, so the advantage over wavefront-parallel Viterbi should grow with sequence length and tag-set size, a scaling the paper does not report and a natural next measurement.
  • The paper fixes the projection budget at 5 or 10 iterations and cites the optimal-transport literature for convergence, but no rate or error bound is proved for this particular alternating scheme; deriving one for flow polytopes of layered DAGs would turn the empirical iteration count into a guarantee and would show whether very long sequences need more iterations.
  • The odd/even decomposition is a recipe, not a chain-specific trick: any structured prediction whose feasible set is an integral polytope cut into two constraint families with closed-form KL projections could reuse it, and the authors point at row/column-decomposed grid CRFs, parsing, and speech recognition as targets, while hypergraph-based dynamic programs are excluded because their per-cluster p
  • Marginal (MBR) decoding can return tag sequences that violate the transition constraints, which the paper notes in a footnote but never measures; a cheap post-hoc check, or projecting the decoded sequence back onto the valid set, would quantify and possibly close the remaining gap to Viterbi.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proposes Bregman conditional random fields (BCRF), a sequence labeling model in which marginal transition probabilities are defined through mean regularization, namely B_Y(w) = max_{q in conv(Y)} <q,w> + H(q), where conv(Y) is the transition marginal polytope. The main contributions are: a tight integral polytope characterization of conv(Y) for linear-chain tag sequences (Proposition 2), an inference algorithm based on iterative Bregman projections (Algorithm 1), Fenchel-Young losses for supervised and partial-label learning, and experiments on POS tagging, joint word segmentation/POS tagging, and NER. The experiments report that BCRF matches CRF accuracy while being faster, and outperforms mean-field inference in constrained settings.

Significance. If the algorithmic gaps identified below are resolved, this is a valuable contribution: it offers a genuinely parallelizable alternative to Viterbi/forward for a core structured prediction task, backed by a clean polyhedral characterization and a sound Fenchel-Young learning framework. The paper ships publicly available code and includes machine-checkable derivations for the polytope integrality and the closed-form KL projections. The experimental evidence is encouraging, especially the speedups and the behavior on forbidden-transition settings, but the absence of convergence analysis for the inference algorithm and the decoding validity issue currently prevent the central claim from being fully established.

major comments (3)
  1. [Section 3.3, Algorithm 1] The pseudocode initializes q^(0) <- w, but the KL projection problem derived immediately above is D_KL[q | exp(tau^{-1} w)] and every subsequent step projects a vector onto C_i with D_KL[mu | q^(i-1)]. Since w is an unconstrained neural score that can have negative entries, D_KL is undefined for such reference vectors; as stated, the algorithm is not well-defined on the actual inputs produced by f_theta. The fix is straightforward: initialize q^(0) <- exp(tau^{-1} w), or explicitly exponentiate before each KL projection, and then state that the returned q^(k) is an approximation of the KL projection rather than of w itself.
  2. [Sections 3.3, 4.1, and 6] No convergence or error bound is provided for Algorithm 1, yet the paper treats q^(5) and q^(10) as if they equal grad B_Y(w). This equality is load-bearing: Section 4.1 defines the training gradient as -y + grad B_Y(w), the partial-label gradient in Section 4.2 similarly uses grad B_Y(w) and grad B_{\tilde Y}(w), and Section 3.1 uses the same quantity for MBR decoding. The citation to Benamou et al. (2015) concerns iterative Bregman projections for entropic optimal transport and does not by itself establish convergence to the KL projection onto conv(Y) = C_even intersect C_odd. If the iterates have not converged, the training objective is an uncontrolled surrogate of the Fenchel-Young loss. Please add a convergence analysis for the exact projection, or at least verify q^(k) against the exact grad B_Y(w) on small instances where the projection can be computed by an independent solver, and justify the fixed iteration budget of 5 or 10.
  3. [Section 3.1 and Section 6.2] MBR decoding from grad B_Y(tau^{-1} w) does not guarantee a globally valid tag sequence: taking per-position argmax over transition marginals can select adjacent tags whose transition is forbidden, even though the overall marginal vector belongs to conv(Y). This is particularly relevant for the joint segmentation/POS experiments in Section 6.2, where forbidden transitions are enforced and the paper claims better behavior in highly constrained settings. The manuscript should explain how invalid MBR outputs are handled (e.g., constrained remapping, Viterbi decoding on the marginals, or a validity check), or provide evidence that such invalid outputs do not occur at tau^{-1}=10.
minor comments (5)
  1. [Section 6] The temperature inverse tau^{-1}=10 is fixed without a sensitivity analysis; since Proposition 1 concerns the tau -> 0 limit and very small tau causes numerical instability, a small sweep would strengthen the decoding claims.
  2. [Section 4.2] The text says 'property (5)' when referring to the enumerated properties, but only three properties are listed; this should be corrected to the appropriate property number.
  3. [Limitations] The first limitations bullet contains an incomplete sentence ('On a purely sequential architecture.') and should be completed or merged with the following sentence.
  4. [Tables 1b and 1d] Some rows in Tables 1b and 1d read 'BCRF5' and 'BCRF10' while other rows read 'BCRF5 it.' and 'BCRF10 it.'; the formatting should be made consistent.
  5. [Tables 1 and 3] The experimental tables do not report error bars or statistical significance, which matters because many of the reported accuracy differences are small; adding standard deviations or a significance test would help substantiate the 'comparable results' claim.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the model, losses, and inference derivation are self-contained; the iterative-Bregman projection concern is an unproven approximation risk, not a circular step.

full rationale

The derivation chain is not circular. Definition 1 defines the BCRF distribution through the exact quantity ∇B_Y(w)=argmax_{q∈conv(Y)}⟨q,w⟩+H(q), and Algorithm 1 is explicitly labeled "Returns an approximation of ∇B_Y(w)"; the approximation status is declared rather than silently equated with the definition. Section 3.3 reduces B_Y(w) to a KL projection by algebraic rewriting of the same objective, not by assuming the algorithm's output. Proposition 2's polytope description is proved in Appendix E via integrality of an extended formulation; the Fenchel-Young loss gradient −y+∇B_Y(w) and the partial-loss gradient follow by direct conjugacy and calculus. Experiments are run on standard external benchmarks (UD, CoNLL 2003) with fixed k=5,10 and τ^{-1}=10, so no fitted parameter is renamed as a prediction. The self-citations (Corro 2024; Ondel et al. 2022) are background or side remarks and are not load-bearing; the key methodological references (Blondel et al. 2020; Benamou et al. 2015) are external. The Limitations section explicitly restricts the method to linear-chain/GPU-style settings and graph dynamic programs, which bounds applicability without affecting the derivation's independence. The real weaknesses are correctness risks, not circularity: convergence of the alternating KL projections is deferred to Benamou et al. (2015) without a proof for this specific Ceven/Codd decomposition, and Algorithm 1 initializes q^(0)←w although the projection is derived for exp(τ^{-1}w), leaving the procedure ill-defined for negative scores. These concerns do not make any output equal to its input by construction, so the circularity score is 0.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The central model introduces no new physical entities or free constants. The two free parameters listed are algorithmic/hyperparameter choices that affect accuracy and speed. The main mathematical pill is the integrality of the path polytope and the convergence of IBP, both supported by prior literature.

free parameters (2)
  • temperature inverse τ^{-1} = 10
    Chosen manually for approximate MAP decoding via MBR; no sensitivity analysis or tuning reported. It controls the sharpness of the marginal probabilities and affects downstream accuracy.
  • number of IBP iterations k = 5 or 10
    Computational budget for the alternating projections; the output is an approximation whose distance to the true ∇B_Y(w) is unmeasured.
assumptions (3)
  • standard math The path polytope of a DAG is integral (Prop. 2).
    Used to claim conv(Y) is exactly described by flow constraints (7)-(8). Proven in Appendix E via extended formulation.
  • standard math Iterative Bregman projections converge to the KL projection onto the intersection of convex sets.
    Invoked in Section 3.3 to justify Algorithm 1; cited to Benamou et al. (2015) rather than proved for this scheme.
  • domain assumption Mean regularization defines a distribution over sequences with marginals ∇B_Y(w).
    Definition 1 postulates BCRF; the paper does not prove that a unique sequence distribution exists for every w, but the marginal representation is the model itself.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Bregman Conditional Random Fields: Sequence Labeling with Parallelizable Inference Algorithms." pith.science (2026). https://pith.science/paper/H2OATZVD

@misc{pith2026250600732,
  author       = {Pith},
  title        = {Pith review of: Bregman Conditional Random Fields: Sequence Labeling with Parallelizable Inference Algorithms},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/H2OATZVD}},
  note         = {Machine review of arXiv:2506.00732}
}
read the original abstract

We propose a novel discriminative model for sequence labeling called Bregman conditional random fields (BCRF). Contrary to standard linear-chain conditional random fields, BCRF allows fast parallelizable inference algorithms based on iterative Bregman projections. We show how such models can be learned using Fenchel-Young losses, including extension for learning from partial labels. Experimentally, our approach delivers comparable results to CRF while being faster, and achieves better results in highly constrained settings compared to mean field, another parallelizable alternative.

Figures

Figures reproduced from arXiv: 2506.00732 by the authors.

Figure 1
Figure 1. Illustration of the dependency between stages [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

66 extracted references · 46 canonical work pages

  1. [1]

    Arturo Argueta and David Chiang. 2018. https://doi.org/10.18653/v1/P18-1251 Composing finite state transducers on GPU s . In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 2697--2705, Melbourne, Australia. Association for Computational Linguistics

    work page doi:10.18653/v1/p18-1251 2018

  2. [2]

    Amir Beck. 2017. https://doi.org/10.1137/1.9781611974997 First-Order Methods in Optimization . Society for Industrial and Applied Mathematics, Philadelphia, PA

    doi:10.1137/1.9781611974997 2017

  3. [3]

    Richard Bellman. 1954. https://doi.org/10.1090/s0002-9904-1954-09848-8 The theory of dynamic programming . Bulletin of the American Mathematical Society, 60(6):503–515

    doi:10.1090/s0002-9904-1954-09848-8 1954

  4. [4]

    Jean-David Benamou, Guillaume Carlier, Marco Cuturi, Luca Nenna, and Gabriel Peyré. 2015. https://doi.org/10.1137/141000439 Iterative bregman projections for regularized transportation problems . SIAM J. Sci. Comput., 37(2)

    doi:10.1137/141000439 2015

  5. [5]

    Dimitri P Bertsekas. 1999. http://www.athenasc.com/nonlinbook.html Nonlinear programming . Athena Scientific Belmont

    work page 1999

  6. [6]

    Bickel and Kjell A

    Peter J. Bickel and Kjell A. Doksum. 1977. Mathematical Statistics: Basic Ideas and Selected Topics. Prentice Hall

    work page 1977

  7. [7]

    Martins, and Vlad Niculae

    Mathieu Blondel, André F.T. Martins, and Vlad Niculae. 2020. http://jmlr.org/papers/v21/19-021.html Learning with fenchel-young losses . Journal of Machine Learning Research, 21(35):1--69

    work page 2020

  8. [8]

    Stephen P Boyd and Lieven Vandenberghe. 2004. Convex optimization. Cambridge university press

    work page 2004

Show all 66 references
  1. [9]

    Lev M. Bregman. 1967. https://doi.org/10.1016/0041-5553(67)90040-7 The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming . USSR Computational Mathematics and Mathematical Physics, 7(3):200 -- 217

    1967 doi

  2. [10]

    Yair Censor. 1998. https://doi.org/10.1093/oso/9780195100624.001.0001 Parallel Optimization: Theory, Algorithms, and Applications . Oxford University PressNew York, NY

    1998

  3. [11]

    Kenneth Ward Church. 1988. https://doi.org/10.3115/974235.974260 A stochastic parts program and noun phrase parser for unrestricted text . In Second Conference on Applied Natural Language Processing, pages 136--143, Austin, Texas, USA. Association for Computational Linguistics

    1988

  4. [12]

    Michele Conforti, Gérard Cornuéjols, and Giacomo Zambelli. 2013. https://doi.org/10.1007/s10479-012-1269-0 Extended formulations in combinatorial optimization . Annals of Operations Research, 204(1):97--143

    2013 doi

  5. [13]

    Caio Filippo Corro. 2024. https://doi.org/10.18653/v1/2024.emnlp-main.1087 A fast and sound tagging method for discontinuous named-entity recognition . In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 19506--19518, Miami, Florida...

    2024 doi

  6. [14]

    Marco Cuturi. 2013. https://proceedings.neurips.cc/paper_files/paper/2013/file/af21d0c97db2e27e13572cbf59eb343d-Paper.pdf Sinkhorn distances: Lightspeed computation of optimal transport . In Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc

    2013

  7. [15]

    John M. Danskin. 1966. http://www.jstor.org/stable/2946123 The theory of max-min, with applications . SIAM Journal on Applied Mathematics, 14(4):641--664

    1966

  8. [16]

    Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. https://doi.org/10.18653/v1/N19-1423 BERT : Pre-training of deep bidirectional transformers for language understanding . In Proceedings of the 2019 Conference of the North A merican Chapter of the Associat...

    2019 doi

  9. [17]

    S. C. Fang. 1992. https://doi.org/10.1007/BF01417214 An unconstrained convex programming view of linear programming . ZOR Zeitschrift für Operations Research Methods and Models of Operations Research, 36(2):149--161

    1992 doi

  10. [18]

    S.-C. Fang, J. R. Rajasekera, and H.-S. J. Tsao. 1997. https://doi.org/10.1007/978-1-4615-6131-6 Entropy Optimization and Mathematical Programming . Springer US

    1997 doi

  11. [19]

    G.D. Forney. 1973. https://doi.org/10.1109/PROC.1973.9030 The V iterbi algorithm . Proceedings of the IEEE, 61(3):268--278

    1973

  12. [20]

    Carlos G \'o mez-Rodr \'i guez and David Vilares. 2018. https://doi.org/10.18653/v1/D18-1162 Constituent parsing as sequence labeling . In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 1314--1324, Brussels, Belgium. Association f...

    2018 doi

  13. [21]

    Joshua Goodman. 1996. https://doi.org/10.3115/981863.981887 Parsing algorithms and metrics . In 34th Annual Meeting of the Association for Computational Linguistics, pages 177--183, Santa Cruz, California, USA. Association for Computational Linguistics

    1996

  14. [22]

    Joshua Goodman. 1999. Semiring parsing. Computational Linguistics, 25(4):573--606

    1999

  15. [23]

    Albert Gu, Karan Goel, and Christopher Re. 2022. https://openreview.net/forum?id=uYLFoz1vlAC Efficiently modeling long sequences with structured state spaces . In International Conference on Learning Representations

    2022

  16. [24]

    David Hall, Taylor Berg-Kirkpatrick, and Dan Klein. 2014. https://doi.org/10.3115/v1/P14-1020 Sparser, better, faster GPU parsing . In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 208--217, Baltimore, Ma...

    2014 doi

  17. [25]

    JM Hammersley and P Clifford. 1971. Markov fields on finite graphs and lattices

    1971

  18. [26]

    Hua He, Jimmy Lin, and Adam Lopez. 2015. https://doi.org/10.1162/tacl_a_00124 Gappy pattern matching on GPU s for on-demand extraction of hierarchical translation grammars . Transactions of the Association for Computational Linguistics, 3:87--100

    2015 doi

  19. [27]

    Yang He. 1988. https://doi.org/10.1109/ICPR.1988.28338 Extended viterbi algorithm for second order hidden markov process . In [1988 Proceedings] 9th International Conference on Pattern Recognition, pages 718--720 vol.2

    1988

  20. [28]

    Xiao Huang, Li Dong, Elizabeth Boschee, and Nanyun Peng. 2019. https://doi.org/10.18653/v1/K19-1048 Learning a unified named entity tagger from multiple partially annotated corpora for efficient adaptation . In Proceedings of the 23rd Conference on Computational Natural Langua...

    2019 doi

  21. [29]

    Frederik Jelinek. 1997. Statistical Methods for Speech Recognition. MIT Press

    1997

  22. [30]

    Rong Jin and Zoubin Ghahramani. 2002. https://proceedings.neurips.cc/paper_files/paper/2002/file/653ac11ca60b3e021a8c609c7198acfc-Paper.pdf Learning with multiple labels . In Advances in Neural Information Processing Systems, volume 15. MIT Press

    2002

  23. [31]

    Mark Johnson. 2011. https://aclanthology.org/U11-1006/ Parsing in parallel on multiple cores and GPU s . In Proceedings of the Australasian Language Technology Association Workshop 2011, pages 29--37, Canberra, Australia

    2011

  24. [32]

    Kingma and Jimmy Ba

    Diederik P. Kingma and Jimmy Ba. 2015. http://arxiv.org/abs/1412.6980 Adam: A method for stochastic optimization . In ICLR (Poster)

    2015 arXiv

  25. [33]

    Nikos Komodakis, Nikos Paragios, and Georgios Tziritas. 2011. https://doi.org/10.1109/TPAMI.2010.108 MRF energy minimization and beyond via dual decomposition . IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(3):531--552

    2011 doi

  26. [34]

    Philipp Kraehenbuehl and Vladlen Koltun. 2013. https://proceedings.mlr.press/v28/kraehenbuehl13.html Parameter learning and convergent inference for dense random fields . In Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machi...

    2013

  27. [35]

    Lafferty, Andrew McCallum, and Fernando C

    John D. Lafferty, Andrew McCallum, and Fernando C. N. Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of the Eighteenth International Conference on Machine Learning (ICML 2001), Williams College, Williams...

    2001

  28. [36]

    Saeed Maleki, Madanlal Musuvathi, and Todd Mytkowicz. 2014. https://doi.org/10.1145/2555243.2555264 Parallelizing dynamic programming through rank convergence . In ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '14, Orlando, FL, USA, February 1...

    2014

  29. [37]

    Diego Marcheggiani, Anton Frolov, and Ivan Titov. 2017. https://doi.org/10.18653/v1/K17-1041 A simple and accurate syntax-agnostic neural model for dependency-based semantic role labeling . In Proceedings of the 21st Conference on Computational Natural Language Learning ( C o ...

    2017 doi

  30. [38]

    R Kipp Martin, Ronald L Rardin, and Brian A Campbell. 1990. Polyhedral characterization of discrete dynamic programming. Operations research, 38(1):127--138

    1990

  31. [39]

    Arthur Mensch and Mathieu Blondel. 2018. https://proceedings.mlr.press/v80/mensch18a.html Differentiable dynamic programming for structured prediction and attention . In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine L...

    2018

  32. [40]

    Yoichi Muraoka. 1971. Parallelism exposure and exploitation in programs. Ph.D. thesis, University of Illinois at Urbana-Champaign

    1971

  33. [41]

    Nesterov

    Yu. Nesterov. 2004. https://doi.org/10.1007/s10107-004-0552-5 Smooth minimization of non-smooth functions . Mathematical Programming, 103(1):127–152

    2004 doi

  34. [42]

    Vlad Niculae and Mathieu Blondel. 2017. https://proceedings.neurips.cc/paper_files/paper/2017/file/2d1b2a5ff364606ff041650887723470-Paper.pdf A regularized framework for sparse and structured neural attention . In Advances in Neural Information Processing Systems, volume 30. C...

    2017

  35. [43]

    Vlad Niculae, Andre Martins, Mathieu Blondel, and Claire Cardie. 2018. https://proceedings.mlr.press/v80/niculae18a.html S parse MAP : Differentiable sparse structured inference . In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings...

    2018

  36. [44]

    Manning, Sampo Pyysalo, Sebastian Schuster, Francis Tyers, and Daniel Zeman

    Joakim Nivre, Marie-Catherine de Marneffe, Filip Ginter, Jan Haji c , Christopher D. Manning, Sampo Pyysalo, Sebastian Schuster, Francis Tyers, and Daniel Zeman. 2020. https://aclanthology.org/2020.lrec-1.497 U niversal D ependencies v2: An evergrowing multilingual treebank co...

    2020

  37. [45]

    Lucas Ondel, Léa-Marie Lam-Yee-Mui, Martin Kocour, Caio Filippo Corro, and Lukás Burget. 2022. https://doi.org/10.1109/ICASSP43922.2022.9746824 Gpu-accelerated forward-backward algorithm with application to lattice-free mmi . In ICASSP 2022 - 2022 IEEE International Conference...

    2022

  38. [46]

    Giorgio Parisi. 1979. https://doi.org/10.1016/0375-9601(79)90708-4 Toward a mean field theory for spin glasses . Physics Letters A, 73(3):203--205

    1979 doi

  39. [47]

    Gabriel Peyré and Marco Cuturi. 2019. https://doi.org/10.1561/2200000073 Computational optimal transport: With applications to data science . Foundations and Trends® in Machine Learning, 11(5-6):355--607

    2019 doi

  40. [48]

    L. R. Rabiner. 1989. A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2):257--285

    1989

  41. [49]

    Lance Ramshaw and Mitch Marcus. 1995. https://aclanthology.org/W95-0107/ Text chunking using transformation-based learning . In Third Workshop on Very Large Corpora

    1995

  42. [50]

    Lev Ratinov and Dan Roth. 2009. https://aclanthology.org/W09-1119/ Design challenges and misconceptions in named entity recognition . In Proceedings of the Thirteenth Conference on Computational Natural Language Learning ( C o NLL -2009) , pages 147--155, Boulder, Colorado. As...

    2009

  43. [51]

    Alexander Schrijver. 1986. Theory of linear and integer programming. Publication Title: Wiley-Interscience series in discrete mathematics and optimization

    1986

  44. [52]

    Lawrence Stewart, Francis Bach, Felipe Llinares-Lopez, and Quentin Berthet. 2023. https://proceedings.neurips.cc/paper_files/paper/2023/file/637a456d89289769ac1ab29617ef7213-Paper-Conference.pdf Differentiable clustering with perturbed spanning forests . In Advances in Neural ...

    2023

  45. [53]

    Tjong Kim Sang and Fien De Meulder

    Erik F. Tjong Kim Sang and Fien De Meulder. 2003. https://aclanthology.org/W03-0419/ Introduction to the C o NLL -2003 shared task: Language-independent named entity recognition . In Proceedings of the Seventh Conference on Natural Language Learning at HLT - NAACL 2003 , pages...

    2003

  46. [54]

    L. G. Valiant, S. Skyum, S. Berkowitz, and C. Rackoff. 1983. https://doi.org/10.1137/0212043 Fast parallel computation of polynomials using few processors . SIAM Journal on Computing, 12(4):641--644

    1983 doi

  47. [55]

    Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, ukasz Kaiser, and Illia Polosukhin. 2017. https://proceedings.neurips.cc/paper/2017/file/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf Attention is all you need . In Advances in Neural Informa...

    2017

  48. [56]

    A. Viterbi. 1967. https://doi.org/10.1109/tit.1967.1054010 Error bounds for convolutional codes and an asymptotically optimum decoding algorithm . IEEE Transactions on Information Theory, 13(2):260–269

    1967

  49. [57]

    Martin J Wainwright and Michael I Jordan. 2008. Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learning , 1(1--2):1--305

    2008

  50. [58]

    Xinyu Wang, Yong Jiang, Nguyen Bach, Tao Wang, Zhongqiang Huang, Fei Huang, and Kewei Tu. 2020. https://doi.org/10.18653/v1/2020.emnlp-main.485 AIN : Fast and accurate sequence labeling with approximate inference network . In Proceedings of the 2020 Conference on Empirical Met...

    2020 doi

  51. [59]

    Pierre Weiss. 1907. https://doi.org/10.1051/jphystap:019070060066100 L'hypothèse du champ moléculaire et la propriété ferromagnétique . J. Phys. Theor. Appl., 6(1):661--690

    1907 doi

  52. [60]

    J. F. Q. Xipeng. 2009. A new chinese dependency analysis method based on sequence labeling model. In Computer Applications and Software

    2009

  53. [61]

    Nianwen Xue. 2003. https://aclanthology.org/O03-4002/ C hinese word segmentation as character tagging . In International Journal of Computational Linguistics & C hinese Language Processing, Volume 8, Number 1, F ebruary 2003: Special Issue on Word Formation and C hinese Langua...

    2003

  54. [62]

    Songlin Yang, Bailin Wang, Yu Zhang, Yikang Shen, and Yoon Kim. 2024. https://proceedings.neurips.cc/paper_files/paper/2024/file/d13a3eae72366e61dfdc7eea82eeb685-Paper-Conference.pdf Parallelizing linear transformers with the delta rule over sequence length . In Advances in Ne...

    2024

  55. [63]

    Yaosheng Yang, Wenliang Chen, Zhenghua Li, Zhengqiu He, and Min Zhang. 2018. https://aclanthology.org/C18-1183/ Distantly supervised NER with partial annotation learning and reinforcement learning . In Proceedings of the 27th International Conference on Computational Linguisti...

    2018

  56. [64]

    Shuai Zheng, Sadeep Jayasumana, Bernardino Romera - Paredes, Vibhav Vineet, Zhizhong Su, Dalong Du, Chang Huang, and Philip H. S. Torr. 2015. https://doi.org/10.1109/ICCV.2015.179 Conditional random fields as recurrent neural networks . In 2015 IEEE International Conference on...

    2015 doi

  57. [65]

    online" 'onlinestring :=

    ENTRY address archivePrefix author booktitle chapter edition editor eid eprint eprinttype howpublished institution journal key month note number organization pages publisher school series title type volume year doi pubmed url lastchecked label extra.label sort.label short.list...

  58. [66]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.