# US 2018/0025720 A1 · Optimizations to decoding of wfst models for automatic speech recognition

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2018/0025720 A1
- Document ID: US20180025720A1
- Status: Published application
- Kind: A1
- Application number: 15/615,799
- Filed: 2017-06-06
- Published: 2018-01-25
- Earliest claimed: 2014-09-26
- Assignees: Intel Corporation
- Applicants: Intel Corporation
- Inventors: Joachim HOFER; Georg STEMMER
- Web page: https://patentgrep.com/patent/US20180025720A1

## CPC

- G10L 15/02: Feature extraction for speech recognition; Selection of recognition unit
- G10L 15/142: {Hidden Markov Models [HMMs]}
- G10L 2015/025: {Phonemes, fenemes or fenones being the recognition units}
- G10L 2015/0635: {updating or merging of old and new templates; Mean values; Weighting}
- G10L: SPEECH ANALYSIS TECHNIQUES OR SPEECH SYNTHESIS; SPEECH RECOGNITION; SPEECH OR VOICE PROCESSING TECHNIQUES; SPEECH OR AUDIO CODING OR DECODING

## Abstract

A method in a computing device for decoding a weighted finite state transducer (WFST) for automatic speech recognition is described. The method includes sorting a set of one or more WFST arcs based on their arc weight in ascending order. The method further includes iterating through each arc in the sorted set of arcs according to the ascending order until the score of the generated token corresponding to an arc exceeds a score threshold. The method further includes discarding any remaining arcs in the set of arcs that have yet to be considered.

## Claims

### Claim 1

A method for performing weighted finite state transducer (WFST) speech recognition, comprising:
sorting a set of one or more WFST arcs based on their weight in ascending order;
iterating through each arc in the sorted set of arcs according to the ascending order until the score of a generated token corresponding to the arc exceeds a score threshold; and
discarding any remaining arcs in the set of arcs that have yet to be considered.

### Claim 2 (depends on 1)

The method of claim 1, wherein the score of each token is the sum of a cumulative score of that token from the previous frame, the weight of the corresponding arc, and the best acoustic score of the current frame.

### Claim 3 (depends on 2)

The method of claim 2, wherein the score threshold is the sum of the best score from the previous frame, the best acoustic score of the current frame and a predefined constant.

### Claim 4 (depends on 3)

The method of claim 3, further comprising:
for each remaining token, calculating the actual acoustic score for the token;
discarding the tokens with a modified score exceeding another score threshold, wherein the modified score is a sum of a cumulative score of that token from the previous frame, the weight of the corresponding arc, and the acoustic score of the current frame; and
placing any tokens that have not been discarded in an active token buffer for the next frame.

### Claim 5 (depends on 1)

The method of claim 1, wherein the set of arcs is one clustered set of arcs of a plurality of clustered sets of tokens, and wherein the best acoustic score of the clustered set of arcs is used for computing the score threshold.

### Claim 6 (depends on 1)

The method of claim 1, wherein the WFST is dynamically composed to a second WFST using a single lookup arc cache for the second WFST, wherein the single lookup arc cache includes cache entries for input labels that are recursively reachable by epsilon arcs in the second WFST.

### Claim 7 (depends on 6)

The method of claim 6, wherein each entry in the single lookup arc cache includes a source state identifier, an input label identifier, an arc identifier, and an accumulated weight value, wherein the accumulated weight value corresponds to the weight of the arcs along the path from the state identified by the source state identifier to the arc identified by the arc identifier.

### Claim 8 (depends on 7)

The method of claim 7, further comprising:
looking up in the single lookup arc cache the arc identifier and accumulated weight for an input label and a source state; and
receiving from the single lookup arc cache the arc identifier and accumulated weight for the input label and the source state.

### Claim 9 (depends on 7)

The method of claim 7, further comprising:
looking up in the single lookup arc cache the arc identifier and accumulated weight for an input label and a source state, wherein the single lookup arc cache does not include an entry corresponding to the input label and the source state; and
in response to the look up, generating a cache miss in the single lookup arc cache, causing a cache controller to search the second WFST for an arc with the input label in the source state, and causing the cache controller to recursively search all states in the second WFST that are reachable via epsilon arcs, in order to populate the single lookup arc cache with the missed entry.

### Claim 10

An apparatus for weighted finite state transducer (WFST) speech recognition, comprising:
an acoustic frontend configured to receive a digital audio signal representing human speech from an analog/digital converter and convert the digital audio signal into a set of one or more acoustic features;
a memory to store a trained WFST model for speech recognition;
a WFST decoder to use token passing to decode the acoustic features into transcribed words based on the WFST model, the WFST decoder to execute instructions to:
sort a set of one or more WFST arcs based on their arc weight in ascending order;
iterate through each arc in the sorted set of arcs according to the ascending order until the score of the generated token corresponding to the arc exceeds a score threshold; and
discard any remaining arcs in the set of arcs that have yet to be considered; and
a language interpreter execution unit to output the transcribed words to at least one of a sound output and a visual output.

### Claim 11 (depends on 10)

The apparatus of claim 10, wherein the score of each token is the sum of a cumulative score of that token from the previous frame, the weight of the corresponding arc, and the best acoustic score of the current frame.

### Claim 12 (depends on 11)

The apparatus of claim 11, wherein the score threshold is the sum of the best score from the previous frame, the best acoustic score of the current frame and a predefined constant.

### Claim 13 (depends on 12)

The apparatus of claim 12, wherein the WFST decoder further executes instructions to:
for each remaining token, calculate the actual acoustic score for the token;
discard the tokens with a modified score exceeding another score threshold, wherein the modified score is a sum of a cumulative score of that token from the previous frame, the weight of the corresponding arc, and the acoustic score of the current frame; and
place any tokens that have not been discarded in an active token buffer for the next frame.

### Claim 14 (depends on 10)

The apparatus of claim 10, wherein the WFST is dynamically composed to a second WFST using a single lookup arc cache for the second WFST, wherein the single lookup arc cache includes cache entries for input labels that are recursively reachable by epsilon arcs in the second WFST.

### Claim 15 (depends on 14)

The apparatus of claim 14, wherein each entry in the single lookup arc cache includes a source state identifier, an input label identifier, an arc identifier, and an accumulated weight value, wherein the accumulated weight value corresponds to the weight of the arcs along the path from the state identified by the source state identifier to the arc identified by the arc identifier.

### Claim 16 (depends on 15)

The apparatus of claim 15, wherein the WFST decoder further executes instructions to:
look up in the single lookup arc cache the arc identifier and accumulated weight for an input label and a source state; and
receive from the single lookup arc cache the arc identifier and accumulated weight for the input label and the source state.

### Claim 17 (depends on 15)

The apparatus of claim 15, wherein the WFST decoder further executes instructions to:
look up in the single lookup arc cache the arc identifier and accumulated weight for an input label and a source state, wherein the single lookup arc cache does not include an entry corresponding to the input label and the source state; and
in response to the look up, generate a cache miss in the single lookup arc cache, to cause a cache controller to search the second WFST for an arc with the input label in the source state, and to cause the cache controller to recursively search all states in the second WFST that are reachable via epsilon arcs, in order to populate the single lookup arc cache with the missed entry.

### Claim 18

A non-transitory computer-readable storage medium having instructions stored therein, wherein the instructions, when executed by a processor of a client device, causes the processor to perform operations for weighted finite state transducer (WFST) speech recognition, the operations comprising:
sorting a set of one or more arcs based on their arc weight in ascending order;
iterating through each arc in the sorted set of arcs according to the ascending order until the score of the generated token corresponding to the arc exceeds a score threshold; and
discarding any remaining arcs in the set of arcs that have yet to be considered.

### Claim 19 (depends on 18)

The non-transitory computer-readable storage medium of claim 18, wherein the score of each token is the sum of a cumulative score of that token from the previous frame, the weight of the corresponding arc, and the best acoustic score of the current frame.

### Claim 20 (depends on 19)

The non-transitory computer-readable storage medium of claim 19, wherein the score threshold is the sum of the best score from the previous frame, the best acoustic score of the current frame and a predefined constant.

### Claim 21 (depends on 20)

The non-transitory computer-readable storage medium of claim 20, the operations further comprising:
for each remaining token, calculating the actual acoustic score for the token;
discarding the tokens with a modified score exceeding another score threshold, wherein the modified score is a sum of a cumulative score of that token from the previous frame, the weight of the corresponding arc, and the acoustic score of the current frame; and
placing any tokens that have not been discarded in an active token buffer for the next frame.

### Claim 22 (depends on 18)

The non-transitory computer-readable storage medium of claim 18, wherein the WFST is dynamically composed to a second WFST using a single lookup arc cache for the second WFST, wherein the single lookup arc cache includes cache entries for input labels that are recursively reachable by epsilon arcs in the second WFST.

### Claim 23 (depends on 22)

The non-transitory computer-readable storage medium of claim 22, wherein each entry in the single lookup arc cache includes a source state identifier, an input label identifier, an arc identifier, and an accumulated weight value, wherein the accumulated weight value corresponds to the weight of the arcs along the path from the state identified by the source state identifier to the arc identified by the arc identifier.

### Claim 24 (depends on 23)

The non-transitory computer-readable storage medium of claim 23, the operations further comprising:
looking up in the single lookup arc cache the arc identifier and accumulated weight for an input label and a source state; and
receiving from the single lookup arc cache the arc identifier and accumulated weight for the input label and the source state.

### Claim 25 (depends on 23)

The non-transitory computer-readable storage medium of claim 23, the operations further comprising:
looking up in the single lookup arc cache the arc identifier and accumulated weight for an input label and a source state, wherein the single lookup arc cache does not include an entry corresponding to the input label and the source state; and
in response to the look up, generating a cache miss in the single lookup arc cache, causing a cache controller to search the second WFST for an arc with the input label in the source state, and causing the cache controller to recursively search all states in the second WFST that are reachable via epsilon arcs, in order to populate the single lookup arc cache with the missed entry.