--- title: "A Parallel Tree Search Method" authors: - "Sei-ichi Nakagawa" - "Toshiyuki Sakai" doi: "" url: "https://ijcai.org/proceedings/1979/137" pdf: "https://ijcai.org/proceedings/1979/0137.pdf" venue: "Proceedings of the Sixth International Joint Conference on Artificial Intelligence" year: 1979 pages: "" track: "" keywords: --- # A Parallel Tree Search Method Sei-ichi Nakagawa, Toshiyuki Sakai *Proceedings of the Sixth International Joint Conference on Artificial Intelligence*. ## Abstract We describe a new tree search method which searches best few paths with backtracking in parallel by the following algorithm (a-8-y search). Expand the best a nodes at one time. If the number of new nodes which have been expanded by a selected node exceeds a pre-set threshold (8), only the best 8 nodes are kept and others are pruned. If the total number of newly generated node sequences and non-expanded node sequences exceeds a pre-set threshold (y), only the best y node sequences are kept, and others are removed. Repeat these consecutive processes until a complete sequence is generated . We evaluated this method by simulaUons and experiments, and obtained good performances both in the search efficiency and in the recognition rate. ## Full text ## 1. INTRODUCTION To recogn1ze a perceptual input (ex. speech, image), all plausible candidates should be taken into consideration, because a system cannot know exactly what the input was, that is, the input is ambiguous. However, since the number of plausible candidate sequences becomes enormous in case of continuous speech recognition, image understanding and game, a system must select some best sequences and abandon the others. Therefore, the recognition of perceptual input contains the problems of tree search (pruning) and scoring mechanism. In this paper, we describe a new tree search method employed in the LITHAN speech understanding system[l-4). For convenience' sake, we would like to discuss the case of speech recognition as an example of recognition of perceptual input and the case of left to right parsing although various parsing strategies have been proposed[S,6). ## 2. SEARCHING STRATEGY OF ALTERNATIVE SEQUENCE The aim of a speech recognition system is to determine,for an acoustic signal A and a task language L, a sequence of words W such that this sequence is consistent with the syntax, semantics and pragmatics of the task, and further that this sequence maximizes the a posteriori probability P(W/A,L). We assume an equal probability for the appearance of each sentence. Now P(W/A,L) = P(W/L)xP(A/W,L)/P(A/L) . The term P(A/L) in the denominator is independent of W, and therefore does not have to be known . \'le assumed that P(W/L) was always constant for all correct sequences of words. Thus, P(W/L) does not also have to be known. Therefore, we can regard that P(W/A,L) is proportional to P(A/W,L). However, this algorithm consumes much computing time, because the approach is equivalent to searching all possible paths or words. Seeing this difficulty, we coped with the problem by dividing the whole process into two stages : the acoustic signal-to-phoneme sequence and the phoneme sequence-to-word sequence. This division corresponds to approximating P(W/A,L) by P(W/A,L) = l;, P(PH/A,L)xP(W/PH,L)o:P(W/PHo,L) , where PH deno~s a sequence of phonemes and PHo a recognized sequence of phonemes (that is, we assume the probability of recognized phoneme » that of other phoneme). Furthermore, the maximum of P(W/PH,,L) is approximately obtained from tree search methods. If an utterance is composed of s words, and t alternative words are identified for each of these, the number of sequences to be considered is st. Therefore the problem of continuous speech recognition can be seen as that of searching through a space of st word sequences to find the most acceptable sequence (that is, the sequence with the highest score), that does not contradict all the given knowledge; syntax, semantics, pragmatics, etc. Fig.l illustrates an example of a parsing tree. In this figure, the alphabetical symbol and numerical value on a branch denote an identified word and its likelihood, respectively. An encircled numeral on a node indicates the average like I i hood for a word sequence corresponding to the path from the root node to that node. A double encircled numeral on a terminal node indicates the score of a complete sentence. The LilliAN system rejects words having a score below a pr~-determined value, sa~· . 80. It also rej~cts sentences helow another value, say 85. Th~3. in Fig.l, there are five complete sentences: BIIM, BIIN, C.JO, C.JP, and CK. If the best-first tree search is applied, the sentence BHN will be selected after the node selection sequence: s~sH~c~cJ~BHN. On the other hand, if we use the depth-first search, BH~ will be selected (A~AE~Ar:~s~sc~sH~BHM). In the case of depth-first serach with ordering, BHN will be selected (B~BH~BI-IN). We would, however, like to select the sentence CJP. Now, the best-first search may guarantee the sequence with highest score, if the score of a word sequence has a true cost function for searching (namely the breadth-first search)[?]. However, such a method requires much computation time and many storage memories. Our searching scheme is not such a case. Although many techniques have been developed in artificial intelligence research[8,9], we will pr9pose a new search technique and pruning method suitable for recognition of perceptual inputs. An exa.ple of tree searching. ![Image](https://ijcai.org/proceedings/1979/fulltext/137/image_000000_c6e6e6179202e0eb64558e75ce10e8c0f05e3b63bbe8a92f048c2a6a5289e923.png) ## 3 . ~ PARALLEL SEARCH METHOD (a-8- y METHOD) We define the parameters which are used by this method. - a: number of nodes which are expanded in parallel at the same time. - 8: number of nodes which arc kept in all generated nodes at each branching point . y: total number of parbal strings which arc kept in a partial tree. l~e score of a partial sentence is defined as the average of the score of words constituting this partial sentence. ll luor 1: thm step 1: Enter the root node into the set of OPEN NODE. step 2: Expand a nodes in the set, each of which is the last node of one of partial strings with the highest a average scores. If the number of nodes in the set is less than a, these all nodes arc expanded. If the expanded node is a terminal node, go to step 5. step 3: Enter the B nodes with the highest B scores out of the generated nodes at each branching point into the set of OPEN NO.DE. step 4: Ifthenumber of nodes in the set of OPEN NODE is more than y, select the y nodes, each of which is the last node of one of partial strings with the highest y average scores, and the other nodes (or strings) are pruned. Go to step 2. step 5: The string from root node to this terminal node is regarded as an input string. If the number of strings which are regarded as an input string is more than 6, stop. Otherwise, go to step 2. We call the successive operations from the step 2 to the step 4 as one 'round'. Although the method of Lowerre in the HARPY system (called beam search[lO]) does not have the function of backtracking, our method has it implicitely in the case of a<y. We call this method as a-8-y tree search method (or best-a tree search) for convenience' sake . For example, in Fig.l, let a, 8, y, and 6 be 2, 3, 4 and 2, respectively. llere the following word sequences will be kept at each round (the two, a=2, underlined sequences arc to he expanded at the next round) . Round 1 : B, C, ll IT may be a complete sentence in the case the score is less than 85, so it is rejected but may be reserved as a partial sentence. Round 2: BH, CK, C.J, D ~and I are rejected. CK is a complete sentence. Round 3: CK, BHM, BHN, CJO, CJP These are all the complet~ sentences. In the end, CJP is selected as the recognized sentence. Larger values of a, B and y would bring a better recognition result, hut such would also increase the tree search time. Therefore, we have to decide the optimum thresholds of a, 6 and y. ## 4 . COMPUTER S I MULA T1 ON Our tree search method was evaluated by computer simulations. The evaluation of a tree search method depends on the depth of tree (DEPTH), branching factor (BRANCH), scoring mechanism and so on. For each [DEPTH, BRANCH], 100 trees and the score of each node were generated by a random generator of a uniform distribution [from 0 to 100]. The score of a partial sentence was defined as the average score over all words in the partial sentence. We regarded the trees of [DEPTH=S, BRANCH=S] as the standard tree because a computer had the limitation of an amount of stored memories. 1be depth of all terminal nodes and the number of branches are same for u tree .in this simulation. We define that the input sequence is the sequence with the highest average score . Thus, our problem is to find the sequence with the highest average score . Table I shows the kinds of trees which were generated by a random generator . ISSS shows the logarithm of the search space size of a tree. This value can be calculated from multiplying logarithm of llABF (dynamic average branching factor) by ASL (average sentence length) [4, 11]. The table 2 shows the set of parameters for tree search which were evaluated. We can divide these parameter sets into the two types. Although the type 1 (a=y) does not have the function of backtracking, the type 2 (a<y) has it imp I i c.i te I y. The parameter o was a 1 ways set to 1. Table I Kind of trees | ype | number of branch | depth of a tree | LSSS | number of nodes | |-------|--------------------|-------------------|--------|-------------------| | l | 4 | 5 | 10.0 | 1364 | | 2 | 5 | 4 | 9.3 | 780 | | 3 | 5 | 5 | 11.6 | 3905 | | 4 | 5 | (, | 13.9 | 19530 | | 5 | (J | 5 | 12 . 9 | 9330 | Table 2 Set of parameters | type | method | a | 6 | y | |--------|----------|-----|-----|-----| | | I | 1 | l | 1 | | | 2 | 2 | 2 | 2 | | 1 | 3 | 3 | 3 | 3 | | | 4 | 4 | 4 | 4 | | | 5 | 5 | 5 | 5 | | | 6 | 1 | 5 | 10 | | | 7 | 2 | 5 | 10 | | 2 | 8 | 3 | 5 | 12 | | | 9 | 5 | 5 | IS | The simulation results are shown in Table 3 and Fig.2. The column 'I' in the 'rank of recognit . n result' corresponds to the number of trees l,hich were recognized correctly. This number associates with "recognition rate". The column '2' indicates that the input was recognized as the second best candidate. As a logical conclusion, the larger LSSS becomes, the worser the recognition rate becomes . From Fig. 2 , we find when the tree is small, the type 2 is inferior to the type 1. On the other hand, when it is large, the type 2 is superior to the type I. And also we can say that the best-first search which is simulated by Ia=!, 6=5, y.=!Oj is inferior to anyone of parallel search (a~2) . | o( ~ | nu.ber of '( •_...sed -· | rank of reCOIJfti uon naul t - l | rank of reCOIJfti uon naul t - 2 | rank of reCOIJfti uon naul t - l | rank of reCOIJfti uon naul t | rank of reCOIJfti uon naul t - 4 | rank of reCOIJfti uon naul t - 5 | rank of reCOIJfti uon naul t - 6 | rank of reCOIJfti uon naul t - 7 | rank of reCOIJfti uon naul t - • | rank of reCOIJfti uon naul t - ' | rank of reCOIJfti uon naul t - 10 | rank of reCOIJfti uon naul t - u- | |--------|----------------------------|------------------------------------|------------------------------------|------------------------------------|--------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|-------------------------------------|-------------------------------------| | 1 | 1 1 | 25 2J | 11 | 5 | | 2 | 6 | 6 | 0 | 3 | l | 0 | 41 | | 2 | 2 2 | 45 52 | u | | 4 | 7 | 2 | 2 | 4 | 3 | 2 | l | 11 | | 3 | 3 3 | 65 | 71 | 9 | v | 5 | 2 | 0 | 1 | 2 | 0 | 0 | 1 | | 4 | 4 4 | 15 | 78 | 12 | 5 | 2 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | | 5 | 5 5 | 105 | 12 | 13 | 3 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | | 1 | 5 10 | 66 | 58 | 12 | 10 | 4 | 3 | 3 | 2 | 1 | 1 | 0 | 6 | | 2 | 5 10 | 71 | 74 | 13 | 7 | 1 | 2 | 0 | 0 | 1 | 0 | 0 | 2 | | 3 | 512 | 95 | 10 | 11 | • | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 5 5 15 | | 130 13 | | 13 | 3 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 -'---- | Fig.2 Relationship between recognition rate and number of expanded nodes. ![Image](https://ijcai.org/proceedings/1979/fulltext/137/image_000001_38881af85fd9bb92f8e118e6a662247cf14e1b4a5b068734d097a97289849b07.png) This search method can control the search space size hy taking the cost of search into consideration. That is, the scoring mechanism of a partial sentence is modified as follows. Let n be the number of words in a partial sentence and s 1 .. . Sn he the score of each word, respectively. The new score of this sequence is defined hy average [Sl·· .Sn] + Wxn, where W is a weighting coefficient. If W is a negative value, the search space size becomes large and the recognition rate would be .improved. In other wards, this leads that a string of short length is treated significantly than that of long length. If W is a positive value, the opposite results will he obtained. Table 4 and Fig.3 show the results of this tree search method . Methods from 1 [a= 1, (3= 1, y= 1] to 5 [a=5, (3=5, y=5], the type l, are independent of this modification, because these methods always expand the partial sentences of same length in parallel. The simulation results arc in approximate agreement with expected results. However, when W was smaller than -10, the recognition results became wrong. We found even if W ·is selected to an optimum value for the best first search, it is also inferior to any parallel search (refer to Fig.4). Next, we investigated the effectiveness of parameters: (3 and y. The simulation results for a=l, 2 arc shown in Figs.4 and 5. In the case of these simulations [BRANCH=5], the best of (3 was 3--5. The larger the value of y becomes, the better the recognition rate becomes and then it is saturated. On the other hand, the number of expanded nodes also becomes larger dramatically. Therefore, we must set the parameters a, (3 and y according with the purpose of applications. At least, we think that a should be larger than 2 in pattern understanding systems, although a best-first search has been often adopted in the first stage of speech understanding systems[l2]. | ~ p | nWiberof r·~ -· | raftk of nootn1t1oa nault - 1 | raftk of nootn1t1oa nault - 2 | raftk of nootn1t1oa nault - ) | raftk of nootn1t1oa nault - • | raftk of nootn1t1oa nault - 5 | raftk of nootn1t1oa nault - 6 | raftk of nootn1t1oa nault - 1 | raftk of nootn1t1oa nault - • | raftk of nootn1t1oa nault - 9 | raftk of nootn1t1oa nault - 10 | raftk of nootn1t1oa nault - u- | |--------|-------------------|---------------------------------|---------------------------------|---------------------------------|---------------------------------|---------------------------------|---------------------------------|---------------------------------|---------------------------------|---------------------------------|----------------------------------|----------------------------------| | 1 1 1 | 25 | 2) | 11 | 5 | 2 | ' | 6 | 0 | ) | l | 0 | u | | 2 2 2 | . •s | 52 | 12 | • | 1 | 2 | 2 | • | l | 2 | 1 | 11 | | ) l l | 65 | 11 | ' | ' | 5 | 2 | 0 | 1 | 2 | 0 | 0 | 1 | | • • • | 15 | 11 | u | 5 | 2 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | | 5 5 5 | 105 | 82 | u | l | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | | 1 5 10 | • | 10 | u | 1 | 2 | 2 | 1 | 1 | 0 | 0 | 0 | ) | | 2 5 10 | 9) | 16 | 16 | 5 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | | l 512 | 1U | ll | 12 | • | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 5 515 | 1.5 | 15 | u | ) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | Fig.3 Relationship between recognition rate and number of expanded nodes. (DEPTH=5, BRANCH=5) ![Image](https://ijcai.org/proceedings/1979/fulltext/137/image_000002_22aec7ace8a40103f64fb7a45e92bca2b45a923738d3edaf527ef239361a0a9d.png) " " Fig.4 Relationship between recogn1t1on rate and number of expanded nodes. (a=l, DEPTII=5, BRANCII=5) ![Image](https://ijcai.org/proceedings/1979/fulltext/137/image_000003_0729181df396fd8da3283459dfdbe147324ea1ac54b0321e788e0132df0d4c0b.png) Fig.S Relationship between recognition rate and number of expanded nodes. (a=2, DEPTH=S, BRANCH=S) ![Image](https://ijcai.org/proceedings/1979/fulltext/137/image_000004_4e35fb20bd7bb2b3833503789e593d4ea4097a4b07f08478b6ce847f32ee1f6a.png) ## 5. SPEECH RECOGNITION OF 'ARITHMETIC EXPRESSION' We applied our tree search method to the speech recognition of 'Arithmetic Expression' as an example in a real world field(l,2l. In this task, the vocabulary size is 23, where each word has an average of 2.1 syllables. For example, this task accepts the sentence such as '1.2X(345 -6789.0)='. The experiments of speech recognition of arithmetic expressions were tested on a total of 80 utterances containing 560 words, spoken by five male adults at a normal speed (these were uttered in Japanese). The reference patterns were common to all speakers . The DEPTH and BRANCH on the average were 7 and 10, respectively . The value of B is always pre-set at 5, because if a word rea.lly uttered belongs to one of predicted words probably it will be identified as one of the best five words (or candidates). The value of 6 was set at 2. The relationship between recogn1t1on rates and parameters of the tree search is shown in Table 5. In this table, the search time column indicates for each case the ratio of the number of verified words to the case where a=l, B=l and y=l. The results are in approximate agreement with simulation on the relative merits for nine search methods. However, the care is necessary to compare it with simulations, because the paths with highest scores in trees of. these experiments are not always correct. from these results, we can also conclude that the hest - few search (or parallel search) is superior to the best-first search. 'l'abie 5 Racoqnition noau1ta of 'Ari~tic Expnoaaion'. | a | 8 | y | March ti• | recognition rate word ~entence | recognition rate word ~entence | no tel' | |-----|-----|-----|-------------|----------------------------------|----------------------------------|---------------------------------| | 1 | 1 | 1 | 1.0 | 80.1\ | 31.0\ | no back trackir19 | | 2 | 2 | 2 | 2.0 | 88.4 | 47.0 | • | | 3 | l | 3 | 3.0 | 92.1 | 56.0 | | | 4 | 4 | 4 | 4.0 | 93.1 | 58.0 | " ,, | | 5 | 5 | 5 | 5.0 | 93.5 | 60.0 | .,. | | 6 | 5 | 6 | 6.0 | 93.8 | 61.0 | .. | | 1 | 5 | 0 | 1.9 | 90.3 | 52.0 | (nearly) beat-firat aearch | | 2 | 5 | 10 | 2.6 | 91.9 | 58.0 | | | 3 | 5 | 2 | 3.3 | 93.2 | 60.0 | | | 5 | s | !15 | 5.1 | 93.6 | 62.0 | (rouqh) brea..Sth-firat aearc:h | ## 6. CONCLUSION We proposed a new tree search method which is suitable for the recornition of perceptual input. This is a parallel tree search method with backtracking implicitely. We evaluated this method by computer simulations and experiments of speech recognition. From these results, we found that the parallel search was superior to the best first search. By taking a weighting function into consideration, we would control the recognition rate and sear~h space size. Further, we found that the larger the tree becomes, the more the performance of parallel search becomes effective. ## ACKNOWLEDGEMENT The authors would like to thank Mr. K. Goto for his co-operative help in computer simulations. ## References 1. ~6 ~~~a~.f~d(~9 ~,~~gawa: IECEJ Trans. Vol.E-60, [3) ~9 ~s~f~j~~P~n~_? 2 gatf~7 8 y~nference Record of (4] ~n~a~s §~~~s~~dvbl~~~~~:N~~\ntl~7Ej~ng of ASA 2. ~:tsW~~ §77):roccedings of the 5-th lJCAI, 3. tn~a~~~fiR?jEA~~dp~z~•rr977): Proceedings of 4. P.H.Winston : Artifitial Intellig~ (1977). 5. B.T.Lowerre(• 1 Ph 6 o. Thesis, Carnegie Mellon Un1versi y 97 J. lll] R.G.Goodman(• 1 Ph 6 D. Thesis, Stanford University 97 J. 6. ~:~zbaffg~S)~EEE Trans. Vol.ASSP-23, No.5,