# US 2014/0156274 A1 · Methods and systems to traverse graph-based networks

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

- Number: US 2014/0156274 A1
- Document ID: US20140156274A1
- Status: Published application
- Kind: A1
- Application number: 13/925,150
- Filed: 2013-06-24
- Published: 2014-06-05
- Earliest claimed: 2009-12-14
- Assignees: Intel Corporation
- Inventors: Kisun You; Christopher J. Hughes; Yen-Kuang Chen
- Web page: https://patentgrep.com/patent/US20140156274A1

## CPC

- G10L 15/063: {Training}
- G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks
- G10L 15/02: Feature extraction for speech recognition; Selection of recognition unit
- G10L 15/083: {Recognition networks (G10L15/142, G10L15/16 take precedence)}
- G10L 15/34: Adaptation of a single recogniser for parallel processing, e.g. by use of multiple processors or cloud computing
- G10L 15/19: Grammatical context, e.g. disambiguation of the recognition hypotheses based on word sequence rules
- G10L: SPEECH ANALYSIS TECHNIQUES OR SPEECH SYNTHESIS; SPEECH RECOGNITION; SPEECH OR VOICE PROCESSING TECHNIQUES; SPEECH OR AUDIO CODING OR DECODING
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

Methods and systems to translate input labels of arcs of a network, corresponding to a sequence of states of the network, to a list of output grammar elements of the arcs, corresponding to a sequence of grammar elements. The network may include a plurality of speech recognition models combined with a weighted finite state machine transducer (WFST). Traversal may include active arc traversal, and may include active arc propagation. Arcs may be processed in parallel, including arcs originating from multiple source states and directed to a common destination state. Self-loops associated with states may be modeled within outgoing arcs of the states, which may reduce synchronization operations. Tasks may be ordered with respect to cache-data locality to associate tasks with processing threads based at least in part on whether another task associated with a corresponding data object was previously assigned to the thread.

## Claims

### Claim 1

A method, comprising:
iteratively traversing a network in response to a stream of feature vectors to translate input labels of arcs of the network, corresponding to a sequence of states of the network, to a list of output grammar elements of the arcs, corresponding to a sequence of grammar elements; and
ordering tasks associated with data objects based on processing threads to which prior tasks associated with the data objects are assigned;
wherein the iteratively traversing and the ordering are performed within a suitably programmed multiple processor computer system.

### Claim 2 (depends on 1)

The method of claim 1, wherein the ordering includes:
receiving a list of active data objects of a subsequent iteration from each of the processing threads;
receiving identifications of tasks associated with the active data objects of the subsequent iteration;
associating each of the tasks with one of the processing threads based on the list in which the corresponding data object is identified; and
ordering the tasks in accordance with a task manager heuristic to direct the tasks to the associated processing threads.

### Claim 3 (depends on 1)

The method of claim 1, wherein the ordering includes:
assigning a first task associated with a data object to a first one of the processing threads in a current iteration;
associating an identification of the first processing thread with the data object;
receiving a second task associated with the data object; and
assigning the second task to the first processing thread based at least in part on the identification of the first processing thread associated with the data object.

### Claim 4 (depends on 1)

The method of claim 1, wherein the iteratively traversing includes:
propagating active arcs of the network, including updating destination states of the active arcs in response to a feature vector.

### Claim 5 (depends on 4)

The method of claim 4,wherein the propagating of the active arcs includes:
retrieving information associated with originating states of the active arcs, including a likelihood measure associated with the originating states;
updating the active arcs with the likelihood measures of the corresponding originating states and the feature vector; and
updating the corresponding destination states in accordance with the updated active arcs.

### Claim 6 (depends on 1)

The method of claim 1, further including:
modeling self-loop information corresponding to each of a plurality of the states within one or more outgoing arcs of the corresponding states.

### Claim 7 (depends on 6)

The method of claim 6, wherein the self loop information includes inherent likelihood information, and wherein the modeling includes:
modifying inherent likelihood information of an outgoing arc with the self-loop inherent likelihood information.

### Claim 8 (depends on 6)

The method of claim 6, wherein the self loop information includes inherent likelihood information, and wherein the modeling includes:
modifying a data object representative of an outgoing arc to include a plurality of fields to hold the self-loop likelihood information and an indication of a presence of the self-loop likelihood information.

### Claim 9 (depends on 1)

The method of claim 1, wherein the arcs include inherent likelihood information, wherein at least a portion of the arcs further include self loop inherent likelihood information, and wherein traversing includes:
identifying a set of active arcs;
updating accumulated likelihood information of at least a subset of the set of active arcs that include the self-loop inherent likelihood information, based at least on the corresponding self-loop inherent likelihood information;
propagating accumulated likelihood information of the set of active arcs during a first propagating phase, subsequent to the updating of the accumulated likelihood information;
propagating accumulated likelihood information to newly activated arcs in a second propagating phase subsequent to the first propagating phase, wherein the newly activated arcs include one or more outgoing arcs of one or more states updated during the first propagating phase;
revising the set of active arcs to include the newly activated arcs and to omit arcs having an accumulated likelihood value below a threshold; and
repeating the updating, the first propagating phase, and the second propagating phase with respect to the revised set of active arcs.

### Claim 10 (depends on 9)

The method of claim 9, wherein the inherent likelihood information of the portion of the arcs is modified to include the corresponding self-loop inherent likelihood information, and wherein the updating includes:
updating the accumulated likelihood information of all active arcs within the set of active arcs based on the inherent likelihood information of the corresponding arcs.

### Claim 11 (depends on 9)

The method of claim 9, wherein at least non-epsilon arcs of the network each include a first set of one or more fields to hold the inherent likelihood information of the arc, a second set of one or more fields to hold self-loop inherent likelihood information, and a self-loop indicator field to hold a self-loop indication when the second set of one or more fields is populated with self-loop inherent likelihood information, and wherein the updating includes:
identifying the subset of arcs within the current set of active arcs as arcs that include the self-loop indication; and
updating the accumulated self-loop likelihood information only with respect to the identified subset of the active arcs.

### Claim 12

A system, comprising:
a network to translate input labels of arcs of a network, corresponding to a sequence of states of the network, to a list of output grammar elements of the arcs, corresponding to a sequence of grammar elements; and
an inference engine to iteratively propagate active arcs of the network in response to a stream of feature vectors, including to update destination states of the active arcs in response to the feature vectors.

### Claim 13 (depends on 12)

The system of claim 12, wherein the inference engine is configured to:
retrieve information associated with originating states of the active arcs, including a likelihood measure associated with the originating states;
update the active arcs with the likelihood measures of the corresponding originating states and the feature vectors; and
update the corresponding destination states in accordance with the updated active arcs.

### Claim 14 (depends on 12)

The system of claim 12, further including:
an ordering system to order tasks associated with data objects based on processing threads to which prior tasks associated with the data objects are assigned.

### Claim 15 (depends on 12)

The system of claim 12, wherein the arcs include inherent likelihood information wherein at least a portion of the arcs further include self-loop inherent likelihood information, and wherein the inference engine is configured to:
identify a set of active arcs;
update accumulated likelihood information of at least a subset of the set of active arcs that include the self-loop inherent likelihood information, based at least on the corresponding self-loop inherent likelihood information;
propagate accumulated likelihood information of the set of active arcs during a first propagation phase, subsequent to the updating of the accumulated likelihood information;
propagate accumulated likelihood information to newly activated arcs in a second propagation phase subsequent to the first propagation phase, wherein the newly activated arcs include one or more outgoing arcs of one or more states updated during the first propagation phase;
revise the set of active arcs to include the newly activated arcs and to omit arcs having an accumulated likelihood value below a threshold; and
repeat the update, the first propagation phase, and the second propagation phase with respect to the revised set of active arcs.

### Claim 16

A computer program product including a computer readable medium having computer program logic stored therein, the computer program logic comprising:
inference logic to cause a processor to translate input labels of arcs of a network, corresponding to a sequence of states of the network, to a list of output grammar elements of the arcs, corresponding to a sequence of grammar elements;
wherein the arcs include inherent likelihood information;
wherein at least a portion of the arcs further include self loop inherent likelihood information; and
wherein the inference logic includes,
self loop update logic to cause the processor to update accumulated likelihood information of at least a subset of the set of active arcs that include the self-loop inherent likelihood information, based at least on the corresponding self-loop inherent likelihood information,
first propagation logic to cause the processor to propagate accumulated likelihood information of the set of active arcs during a first propagation phase, subsequent to the updating of the accumulated likelihood information,
second propagation logic to cause the processor to propagate accumulated likelihood information to newly activated arcs in a second propagation phase subsequent to the first propagation phase, wherein the newly activated arcs include one or more outgoing arcs of one or more states updated during the first propagation phase;
logic to cause the processor to revise the set of active arcs to include the newly activated arcs and to omit arcs having an accumulated likelihood value below a threshold; and
repeat logic to cause the processor to invoke self-loop update logic, the first propagation logic, and the second propagation logic with respect to the revised set of active arcs.

### Claim 17 (depends on 16)

The computer program product of claim 16, wherein the inherent likelihood information of the portion of the arcs is modified to include the corresponding self-loop inherent likelihood information, and wherein the self-loop update logic includes:
logic to cause the processor to update the accumulated likelihood information of all active arcs within the set of active arcs based on the inherent likelihood information of the corresponding arcs.

### Claim 18 (depends on 16)

The computer program product of claim 16, wherein at least non-epsilon arcs of the network each include a first set of one or more fields to hold the inherent likelihood information of the arc, a second set of one or more fields to hold self-loop inherent likelihood information, and a self-loop indicator field to hold a self-loop indication when the second set of one or more fields is populated with self-loop inherent likelihood information, and wherein the self-loop update logic includes:
logic to cause the processor to identify the subset of arcs within the current set of active arcs as arcs that include the self-loop indication; and
logic to cause the processor to update the accumulated self-loop likelihood information only with respect to the identified subset of the active arcs.

### Claim 19 (depends on 16)

The computer program product of claim 16, wherein the inference logic includes:
order logic to cause the processor to order tasks associated with data objects based on processing threads to which prior tasks associated with the data objects are assigned.

### Claim 20 (depends on 16)

The computer program product of claim 16, wherein the inference logic includes:
logic to cause the processor to propagate active arcs of the network, including to update destination states of the active arcs in response to a feature vector.