Ryan Cotterell, Tim Vieira, Ran Zmigrod
We have not lifted any functions out of this paper's repositories yet, so there is nothing we have run. If it links a repository, it is listed below.
Weighted finite-state machines are a fundamental building block of NLP systems. They have withstood the test of time-from their early use in noisy channel models in the 1990s up to modern-day neurally parameterized conditional random fields. This work examines the computation of higher-order derivatives with respect to the normalization constant for weighted finite-state machines. We provide a general algorithm for evaluating derivatives of all orders, which has not been previously described in the literature. In the case of second-order derivatives, our scheme runs in the optimal O(A 2 N 4 ) time where A is the alphabet size and N is the number of states. Our algorithm is significantly faster than prior algorithms. Additionally, our approach leads to a significantly faster algorithm for computing second-order expectations, such as covariance matrices and gradients of first-order expectations.
The same record, over MCP at https://syntology.ai/mcp:
get_harvested_code_for_paper("2106.00749")
get_code_for_paper("2106.00749")
have("2106.00749")
Connect an agent — have() is free.