[thxg]

The scientific article seems to be open access [1].

Before people draw links to recent large language model breakthroughs: Although they do use techniques from computational linguistics, there are no neural networks involved. This is more like old-school AI.

They have essentially a giant optimization problem, and they (approximately) model it as a lattice parsing problem, with a stochastic context-free grammar. They can solve that to optimality in O(n^3), which is too slow for some applications. So they propose a O(n) heuristic (hence no optimality guarantees, but the model was approximate to begin with anyways, and the heuristic is a lot faster), which is the reason for the name of their code: "LinearDesign".

[1] https://www.nature.com/articles/s41586-023-06127-z

[choeger]

Much appreciated! Do you have a good source on what a lattice parsing problem is?

[shishy]

"The lattice parsing problem refers to the task of parsing a word lattice, which is a graph structure that represents multiple possible sequences of words that could have generated a given speech signal [1]. The word lattice is a weighted directed acyclic graph, where each node represents a word hypothesis and each edge represents a transition between two words. The weights on the edges represent the likelihood of the transition. The goal of lattice parsing is to find the most likely sequence of words that generated the speech signal, given the word lattice [1]. Lattice parsing is a challenging problem because the word lattice can be very large and contain many alternative paths, making it difficult to find the most likely path efficiently [1]. Several techniques have been proposed to address this problem, including bi-directional LR parsing from an anchor word, augmented chart data structure, and attention shifting for parsing speech [2][3][4]."

1. https://doi.org/10.21437/interspeech.2016-1583

2. https://doi.org/10.3115/997939.997950

3. https://dl.acm.org/doi/10.3115/991146.991188

4. https://doi.org/10.21236/ada105028

----

(full disclosure this might not be correct, I tried this with an LLM approach we're beta testing at my job called scite Assistant that answers with real references - no hallucinations, just curious how the response is against someone that knows the field a bit more..!)