Speech recognition method and apparatus using lexicon group tree

• US 7,953,594 B2
• Filed: 01/31/2006
• Issued: 05/31/2011
• Est. Priority Date: 02/02/2005
• Status: Expired due to Fees

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Choi, In-jeong, Han, Ick-sang, Jeong, Sang-bae, Kim, Jeong-su
• Primary Examiner(s): Dorvil; Richemond
• Assistant Examiner(s): Borsetti; Greg
• Application Number:
  US11/342,701
• Publication Number:
  US 20060173673A1
• Time in Patent Office: 1,946 Days
• Field of Search: 704 9- 10, 707/E17.046
• US Class Current: 704/10
• CPC Class Codes: G06F 40/279 Recognition of textual entities
• CPC Class Codes: G10L 15/197 Probabilistic grammars, e.g. word n-grams

Abstract

A method and an apparatus for selecting a vocabulary closest to an input speech from among lexicons stored in memory, wherein a centroid lexicon representing lexicons belonging to a predetermined lexicon group is generated. Two lexicons, having a longest distance therebetween in the lexicon group, are selected using the centroid lexicon from the lexicon group, and a node indicating the lexicon group branches based on the two selected lexicons. A node having low group similarity is selected from among current terminal nodes, including branch nodes, and the above procedure is repeatedly performed on a lexicon group indicated by the selected node.

Claims

1. A method of generating a lexicon group tree, comprising the steps of:

(a) generating, using at least one processor, a centroid lexicon representing lexicons belonging to a predetermined lexicon group;

(b) selecting two lexicons, having a longest distance therebetween in the lexicon group, using the centroid lexicon from the lexicon group, and branching a node indicating the lexicon group, based on the two selected lexicons; and

(c) selecting a node having low group similarity from among current terminal nodes, including branch nodes, and repeatedly performing steps (a) and (b) on a lexicon group indicated by the selected node,

wherein the steps (a) and (b) are repeatedly performed until a variance, indicating group similarity, becomes lower than a predetermined threshold value and/or until the number of lexicons, belonging to a node, decreases to a predetermined number or less, and

wherein the step (b) comprises the steps of;

(b1) selecting a first lexicon having a longest distance to the centroid lexicon from the lexicon group;

(b2) selecting a second lexicon having a longest distance to the first lexicon from the lexicon group; and

(b3) bisecting remaining lexicons belonging to the lexicon group, based on the two selected lexicons.

2. The lexicon group tree generation method according to claim 1, wherein the step (a) comprises the steps of:

(a1) initializing a virtual centroid lexicon of the lexicon group; and

(a2) updating the centroid lexicon using the initialized centroid lexicon.

3. The lexicon group tree generation method according to claim 2, wherein the step (a1) comprises the steps of:

(a11) multiplying a number smaller than 1 by the average number of states of the lexicon group, thus determining the initial number of states expressed by a predetermined integer;

(a12) uniformly segmenting each lexicon, existing in the lexicon group, into states depending on the initial number of states;

(a13) allocating the uniformly segmented states to states of the centroid lexicon; and

(a14) obtaining virtual average models for respective states of the centroid lexicon.

4. The lexicon group tree generation method according to claim 3, wherein the initial number of states increases as depth of a tree increases.

5. The lexicon group tree generation method according to claim 2, wherein the step (a2) comprises the steps of:

(a21) performing distance matching with each lexicon in the corresponding lexicon group, based on the initialized centroid lexicon;

(a22) allocating states matched through the matching step to respective states of the centroid lexicon; and

(a23) averaging models allocated to the states of the centroid lexicon and obtaining an average vector, thus updating the centroid lexicon.

6. The lexicon group tree generation method according to claim 1, wherein the step (b3) comprises the step of allocating each of the lexicons of the lexicon group to a node on which a closer one of the two selected lexicons is based, and allocating a corresponding lexicon to two nodes on which the two lexicons are based when a distance between the centroid lexicon and the corresponding lexicon is within a predetermined threshold value.

7. The lexicon group tree generation method according to claim 1, wherein the step (c) comprises the step of selecting all of two or more nodes, having group similarity lower than a predetermined threshold value, from among the current terminal nodes, thus repeatedly performing steps (a) and (b) on the selected nodes.

8. The lexicon group tree generation method according to claim 1, wherein the distance between lexicons is determined by generating states of the two lexicons in a two-dimensional coordinate system and calculating cumulative distances at respective coordinate points.

9. A device for generating a lexicon group tree, comprising:

at least one processing unit comprising;

a centroid lexicon generation unit, using the at least one processing unit to generate a centroid lexicon representing lexicons belonging to a predetermined lexicon group;

a node branching determination unit to select a node having low group similarity from among current terminal nodes; and

a node branching unit to select two lexicons, having a longest distance therebetween in the lexicon group, using the centroid lexicon from the lexicon group, and branching a node indicating the lexicon group, based on the two selected lexicons,

wherein the node branching is repeatedly performed until a variance, indicating group similarity, becomes lower than a predetermined threshold value and/or until the number of lexicons, belonging to a node, decreases to a predetermined number or less, and

wherein the node branching unit selects a first lexicon having a longest distance to the centroid lexicon from the lexicon group, selects a second lexicon having a longest distance to the first lexicon from the lexicon group, and bisects remaining lexicons belonging to the lexicon group, based on the two selected lexicons.

10. The lexicon group tree generation device according to claim 9, wherein the centroid lexicon generation unit initializes a virtual centroid lexicon of the lexicon group, and updates the centroid lexicon using the initialized centroid lexicon.

11. The lexicon group tee generation device according to claim 10, wherein the centroid lexicon generation unit multiplies a number smaller than 1 by the average number of states of the lexicon group to determine the initial number of states expressed by a predetermined integer, uniformly segments each lexicon, existing in the lexicon group, into states depending on the initial number of states, allocates the uniformly segmented states to states of the centroid lexicon, and obtains virtual average models for respective states of the centroid lexicon.

12. The lexicon group tree generation device according to claim 11, wherein the initial number of states increases as depth of a tree increases.

13. The lexicon group tree generation device according to claim 10, wherein the centroid lexicon generation unit performs distance matching with each lexicon in the corresponding lexicon group, based on the initialized centroid lexicon, allocates states matched through the matching step to respective states of the centroid lexicon, and updates the centroid lexicon by averaging models allocated to the states of the centroid lexicon and obtaining an average vector.

14. The lexicon group tree generation device according to claim 9, wherein the node branching unit allocates each of the lexicons of the lexicon group to a node on which a closer one of the two selected lexicons is based, and allocates a corresponding lexicon to both the two nodes on which the two lexicons are based when a distance between the centroid lexicon and the corresponding lexicon is within a predetermined threshold value.

15. The lexicon group tree generation device according to claim 9, wherein the node branching determination unit selects all nodes, having group similarity lower than a predetermined threshold value, from among the current terminal nodes.

16. The lexicon group tree generation device according to claim 9, wherein the distance between lexicons is determined by generating states of the two lexicons in a two-dimensional coordinate system and calculating cumulative distances at respective coordinate points.