.Iill-llifillliiiiiifltiill “ii-fl I'E‘iif‘iiii'iill
`
`.I'il.
`
`I'll.
`
`lill- ”iiillili'ii
`
`iii???
`
`PATENT
`Docket No.: 4428-4001
`
`particular implementation ofthc invention, one or more ofthe aspects may be used together in
`
`various permutations andfor combinations, with the understanding that different permutations
`
`anda’or combinations may be better suited for particular applications or have more or less benefits
`
`or advantages than others.
`
`The underlying scenario common to all these basic examples is that there is a hierarchical
`
`arrangement to the possible choices that can be illustrated in a form of“trec" structure.
`
`FIG. I
`
`is an example graph 100 representing a possible hierarchically arranged
`
`transaction processing or decisional system suitable for use with the invention. The individual
`
`boxes 102 - 120 are referred to as “nodes” and each represents a specific choice or option in the
`
`hierarchy. For purposes described in more detail below, each node is arbitrarily uniquely
`
`identified in some manner.
`
`In the example of FIG. 1, the individual nodes 102 — 120 are
`
`numbered 1 through 10 starting from the top node 102 in the hierarchy.
`
`Each “node” is associated with exactly one verbal description, for example in the case of
`
`an airline system, a verbal description relating to some aspect ofthe reservation process. Each
`
`such description contains “key” words that are deemed to be ot‘importance and other words that
`
`can be disregarded. For example, one node may have the associated verbal description “Would
`
`you like to make a reservation?” In this description, there is only one “key“ word —
`
`“reservation" deemed important, so all ofthe other words in the description can be ignored.
`
`A level in the hierarchy below that one may be used to obtain further narrowing
`
`information, for example, using the verbal description “Is the reservation for a domestic or
`
`international Right?” In this description, the terms “domestic” and “international" are “kef’
`
`words, Similarly, the word “flight" could be a “key” word, For example, for a system that
`
`3’28851 vi
`
`214
`214
`
`

`

`.'i1'l..
`
`i111!
`
`iii}? ”135:1! "33:“ .IE‘
`
`PATENT
`Docket No.: 4428400]
`
`involves not only airline travel but also rail and/or cruise travel or it could be an “ignored” or
`
`stop word for a purely airline related system because it has minimal meaning in that context.
`
`Again, the other words can be ignored as well.
`
`The unique identification of each node allovvs the creation ofa list of all the key words
`
`and their associated nodes so that, ifa key word is duplicated in two or more nodes, it need only
`
`be listed once. For example, a hierarchical tree related to “pens" might have nodes for hall—point
`
`pens, fine point pens, medium point pens. fountain pens, felt—tip pens, quill pens, erasable pens,
`
`etc. By using this approach, one could list the keyword “point” once, but associate it with each
`
`ofthe nodes where that keyword appears by using the unique identifier for each node where the
`
`term appears.
`
`In this manner the keywords are obtained from the collection of available descriptions
`
`found in the particular application in which the invention will he used.
`
`In addition, each
`
`particular node where the keyword appears is associated with the keyword. Thus, with respect to
`
`the pen application above, the keyword “point“ might appear in nodes 2, 3, 6, 7, 13 and 15.
`
`Similarly, the keyword “erasable“ might appear in nodes 3, 4, 5, 6 and 22. An index. as
`
`described more fully below, associating these keywords with the nodes containing them is then
`
`created, for example:
`
`point: 2, 3, 6, 7,13,15
`erasable: 3, 4, 5, 22
`
`By making use ofthese associations the “tree” can be negotiated by allowing presentation
`
`of relevant verbal descriptions for the nodes associated with a term, irrespective ofwhere in the
`
`228851 v1
`
`215
`215
`
`

`

`
`
`
`
`PATENT
`Docket No.: 4428-400]
`
`hierarchy they are, thereby causing a “jump" to a particular node without neceSsarily traversing
`
`the tree in the rigid hierarchical manner.
`
`Various examples will now be presented to illustrate certain concepts related to the
`
`invention.
`
`lt should be understood that while these examples are presented in the context of
`
`things and likely experiences of ordinary people, the same approach can be applied to other
`
`forms oftransaetion processing including navigating through hierarchically nested data files in a
`
`computer system, pattern analysis or image processing, etc. the term “transaction" as used herein
`
`relating to traversal through a hierarchy to a goal, not mathematical calculation per se.
`
`Moreover, the specific formats used and presented in these examples are purely for
`
`illustration purposes.
`
`It should be understood that that other techniques for interrelating data,
`
`such as hash tables, direct or indirect indexing, etc. can be substituted in a straightlbrward
`
`manner. Thus, for example, the relationship between the word and a node could be configured
`
`such that the location ofthe word in a list as the “n—th" item could be used as an index into
`
`another list containing the nodes correlated to the list. A similar approach could be used for the
`
`thesaurus, the important aspect relative to the inventiori being the relationship among certain
`
`words and the node(s) in which they occur and, where applicable, the relationship between
`
`Certain words and “synonyms” for those words, not the data structure or its form or format
`
`whereby that information is kept or maintained.
`
`Example 1
`
`Example 1 illustrates, in simplified form, how an index is used tojunip among nodes
`
`with reference to FIG. 2.
`
`In this example, the hierarchical tree 200 represents a portion ofa more
`
`‘FZSSSI vi
`
`216
`216
`
`

`

`.1111.11:11iii-'E'I‘I'viill"31:1115511312513133“
`
`.‘IEI.
`
`."11.
`
`.1'11
`
`”iii-11171115511
`
`PATENT
`Docket No.: 4428-4001
`
`complex tree specifically involving possible decision relating to fruit and a decision between two
`
`specific types of fruits, an apple and an orange.
`
`In prior art hierarchical trees, navigation ofthis graph 200 would necessarily involve
`
`going through the “fruit" node 202 in order to reach the “apple” 204 or “orange" 206 nodes. As
`
`a result, assuming this simple tree was part ofa larger tree for an on-line supermarket that
`
`prompted the user for what they wanted to purchase, the exchange would be both rigid and time
`
`consuming. For example, in response to a prompt “What do you want to purchase?" ifthe
`
`response was anything other than “fruit" traversal to the “fruit" node 202 Could not occur. At the
`
`point in the tree that would lead to the “fruit" node 202. neither apple nor orange would be an
`
`acceptable response.
`
`In accordance with the invention, asemming the only relevant keywords for that portion of
`
`the tree were “fruit“, “apple" and “orange", an inverted index would be created that includes an
`
`association of“Fruit" with the top node 202, “Apple” with the bottom left node 204, and
`
`“Orange” with the bottom right node 206. As shown above, that association can be created using
`
`node identifiers, in this example, the node identifiers 1A01, 1A02 and 1A03 are arbitrarily
`
`assigned and used. Thus, the information can be stored in a file, for example, as follows:
`
`Fruit, 1A0}
`Apple, 1A02
`Orange, ]A03
`
`Accordingly, to navigate the system 200, when a response to a verbal description is
`
`provided by a user, possible keywords are identified in the response and used to search the index
`
`and identify any node to which the response may be directed, irrespective ofthe hierarchy.
`
`Thus, a user response of“an orange” to a verbal description located above the “fruit” node 202 in
`
`TESSSI vi
`
`10
`
`217
`217
`
`

`

`.‘Zii.
`
`lil'il ii?" "El! ‘i-Eéll
`
`IE‘E
`
`PATENT
`Docket NIL: 44284001
`
`the hierarchy, for example, “What would you like to buy today?" would cause the system to
`
`identify “orange" as a key word from the response, search the index, and directly identify node
`
`1A03 (206) as the node whose verbal description should be presented next, thereby avoiding the
`
`need to traverse intervening nodes, for example, through the “fruit” node (202) [AG] , at all.
`
`This illustrates an example ofa simplejurnp according to the invention.
`
`Example 2
`
`Having illustrated a simple “node jump" a more complex (and likely) scenario can be
`
`shown.
`
`in this example, the Example 1 graph of FIG. 2 applies, but relevant portion of the index
`
`is as follows:
`
`Fruit, lAOl
`Apple, 1A02, 22:09
`Orange, 1A03
`
`As a result, there are two nodes relevant to the keyword “apple" one being the node 204
`
`in the portion ofthe graph shown in FIG. 2 and one in the node uniquely identified as 2F09
`
`located somewhere else in the hierarchy (not shown).
`
`In this example, a user response containing the keyword “apple" would identify nodes
`
`with identifiers IA02 and 2F09.
`
`In this case, and unlike the prior art, the verbal descriptions
`
`from both nodes would be presented to the user, likely in alternative fashion. Thus, ifthe user
`
`did not want an apple, they wanted apple cider, node 21:09 might be more appropriate because it
`
`is part ofthe “drinks” portion of the overall hierarchy.
`
`Thus, presenting the user with the verbal description from both nodes would likely result
`
`in ajurnp to the portion ofthe graph nearer to node 2F09 since it is closer to the user’s goal
`
`thereby speeding up the process and avoiding potentially confusing or frustrating the user.
`
`TZSSSI vi
`
`It
`
`218
`218
`
`

`

`.::ll.
`
`ll'fil:
`
`
`
`
`
`“'37:“ 1!".ii.Jiii..i‘!!..t-ti}
`
`
`
`
`
`PATENT
`Docket No.: 4428-4001
`
`minute}:
`
`While the verbal descriptions associated with various nodes will generally be chosen to
`
`accurately represent the node, in accordance with certain variants ofthe invention, it is possible
`
`to create a situation where a user response takes them away from their ultimate desired goal.
`
`Nevertheless, by using the teachings ofthe present invention, the user can often still be brought
`
`to their goal quicker than possible with the prior art becauSe the user need not rigidly trace
`
`through the hierarchy. This is accomplished by virtue of the “grouping" aspect inherent in some
`
`implementations ofthe invention.
`
`This example illustrates the “grouping” aspect using a simplified graph 300 representing
`
`a portion of an airline reservation system as shown in FIG. 3.
`
`in particular, the graph of F1G.3 can be thought ol'as part ofa very simple interactive
`
`voice responSe (“H/R“) system.
`
`As described above, each node is uniquely identified, For example, by the numbers I
`
`through 7 and the identified terms “Reservation“, “Domestic”, “International”, “Business Class",
`
`“Economy Class" are deemed the relevant keywords. Note, there is no requirement for a the
`
`“keyword” to be a single word, in some implementations, keywords could be single words,
`
`phrases oftwo or more words, or even some other form ofinfonnation like a specific data
`
`pattern.
`
`Again, an inverted index is created as described above associating those keywords with
`
`the nodes, in this case:
`
`1
`
`Reservation,
`Domestic, 2
`International, 3
`
`7288M vl
`
`12
`
`219
`219
`
`

`

`
`."li. Hat [till
`
` iizi'i: ill. ll
`
`PATENT
`Docket No.: 4428-4001
`
`Business Class, 4, 6
`Economy Class, 5, 7
`
`Assuming that the top node is assigned the number 1, its two child nodes (Domestic and
`
`International) are assigned the numbers 2 and 3, and the grandchild nodes (i.e. at the lowest level
`
`in the hierarchy) have been assigned numbers 4, 5. 6. and 7" taken from left to right each node can
`
`be uniquely located. Note that the last two entries in the inverted index are each associated with
`
`two nodes, 4 and 6 in the first case, and 5 and 7 in the second.
`
`Using the above, the concept of grouping of nodes from different parts ofthc graph (Le.
`
`nodes that are not siblings or nodes that do not have a common parent) can be explained.
`
`Presume that the response to a verbal description presented as an initial query of “What
`
`do you want to do?" was “Make a business class reservation.” [n this case there are two
`
`keywords present, “reservation” and “business class".
`
`Depending upon the particular implementation, as noted previously, the verbal
`
`descriptions associated with each identified node could be presented together or in sequence.
`
`Alternatively, and as is the case here, a set of rules can be established, for example, such that if
`
`an identified node is a sub-node of another identified node, only the verbal description ofthe
`
`sub—node(s) is provided because efinhercnt redundancy. Thus, since both “business class”
`
`nodes 310, 314 are sub—nodes ofthe “reservation” node 302, the verbal description associated
`
`with the “reservations” node can be suppressed if it can be determined that business class
`
`necessarily implies reservations.
`
`In this example, a search ofthe inverted index would identify nodes 4 and 6 (310, 314}
`
`from different parts ofthe tree are associated with the keywords in the query, and thus the
`
`7288M vl
`
`13
`
`220
`220
`
`

`

`s. it?“ are “:51: an 35;:
`
`1-15..
`
`.IiiE.
`
`.‘iil. ”FE! FiII'vI
`
`iiEEE“.
`
`PATENT
`Docket No.2 4428—400]
`
`system, in presenting the verbal descriptions from each, in effect, alters the tree structure and
`
`groups these nodes in the result. Thus, the combination of result nodes presented depends upon
`
`the user query or response, not that predetermined by the graph structure itself.
`
`Ofcourse, the goal would still not be reached because ofthe ambiguity caused by
`
`“Business Class" being under both “Domestic” and “International". However, that ambiguity
`
`can be handled by suitable wording ofthc following verbal descriptions and whether they are
`
`combined or provided sequentially or by other nodes.
`
`Example 4
`
`A persistent and further drawback present in the prior art is the inability to operate ifany
`
`term other than the specific allowed terms are provided. Thus, in an IVR ofthe prior art,
`
`providing anything other than the recognized ternt(s) will likely result in meaningless repeat of
`
`the same inquiry by the [VR or an error.
`
`Advantageously, the teachings orthe present invention allow for construction of a more
`
`flexible system than available in the prior art. Specifically, we can incorporate a thesaurus to
`
`accommodate synonyms for the keywords.
`
`Example 4 illustrates the addition ofa simple thesaurus as an aspect of a system so that a
`
`synonym efa keyword may also be used by the system to jump to the desired nodes in the graph.
`
`Example 4 is discussed with reference to a portion 400 of an interactive television program
`
`listing system as shown in FIG. 4.
`
`Such a system implementing the invention will allow a user to speak to or interact with a
`
`device to look for programs of his choice by time slot, genre, favorite actor or actress, etc.
`
`7-‘2885l vi
`
`14
`
`221
`221
`
`

`

`
`
`
`
` "it. ”Lil! llillTil.Iii-- iiiii'
`
`
`
`
`
`PATENT
`Docket No.: 4428—4001
`
`This example, as with the other examples above, use an inverted index, in this case one
`
`where each node 402, 404, 406 is uniquely identified by a stringof six characters3 the portion of
`
`which corresponding to FIG. 4 is shown as follows.
`
`Programs; acgyct
`Sitcoms; ifgnxh
`Films; vnymos
`
`Since a common synonym for “Films” is “Movies” a thesaurus can be created associating
`
`the two. Depending upon the particular implementation. thesaurus terms to be equated to the
`
`keywords can be taken from a standard thesaurus or can be custom created for the particular
`
`application.
`
`In addition, the equating oftemis can be done in any ol'a myriad of different ways,
`
`the exact implementation details ofvvhich however re irrelevant to the invention, but a few
`
`representative examples of‘whieh however are contained herein for purposes of illustration.
`
`In one example case, the equating can be done on a purely word basis. For example, a
`
`file can be constructed such that one or more single word synonyms are directly associated with
`
`an index word, For example as follows:
`
`Movies. Flicks
`
`Films
`
`Alternatively, the synonyms can be equated with the node identifier(s) corresponding to
`
`the index term, for example as follows:
`
`Movies, Flicks -— vnymos
`
`in the former case, the system would still have to search the index after the thesaurus has
`
`provided the proper index term(s).
`
`In the latter case, the thesaurus provides a direct link to the
`
`respective node(s) so that re-searching is not required.
`
`T2SSSI vl
`
`15
`
`222
`222
`
`

`

` ii? "I'vElI
`
`...
`
`.'J!i.
`
`TH
`
`Iii.
`
`'='-:'E!t
`
`IiIIH iii?!
`
`l’r-k'l‘lt‘JNt'l~
`Docket N0.: 4428-4001
`
`In the system of Example 4, a user who provides the input “vaies” would cause the
`
`processing to occur as follows.
`
`The system would search the inverted index of keywords and fail to locate “Movies” as a
`
`keyword. As a result, it would search the thesaurus and find that the word “Movies" is a
`
`synonym that can be correlated with a keyword. At this point, depending upon the particular
`
`thesaurus, it would either relum to the inverted index and search using the synonym keyword
`
`“Films” and return the result as the node 406 identified by “vnymos”, or go directly to the node
`
`406 identified by “vnymos” based upon the thesaurus entry.
`
`Ofcourse, it is possible (and likely) that in actual usage a synonym will be associated
`
`with more than one keyword. For example, ”Comedies” may be associated with both the
`
`keywords “Sitcoms" and “Films", resulting in, for example, the following entry in a thesaurus:
`
`Comedies Sitcoms, Films
`
`In this case. a search for “Comedies" would resutt in the system identifying that the
`
`synonym was associated with nodes 404, 406 for both “Sitcoms" and “Films", and it would
`
`return both terms or node identifiers corresponding to the two keywords as the result.
`
`Example 5
`
`Advantageously, the thesaurus concept can be extended further so that an initially
`
`unknown word (i.e. a word that is neither a keyword nor a thesaurus word) can be learned by the
`
`system and added to a thesaurus for future use.
`
`This example is described with reference to FIG. 5 which is a portion 500 ofa larger
`
`system graph as part ofa very simple “geographic information system" found in some
`
`automobiles, kiosks and elsewhere today. Such a system enables a user to, among other things,
`
`rzssst vi
`
`16
`
`223
`223
`
`

`

`411%..
`
`liiiél iii]? "iii! “3:3.” _"
`
`
`
`PATENT
`Docket No.: 4428-4001
`
`identify and get information about different locations in an environment. For example,
`
`information about particular types of restaurants in an area.
`
`In this example, the inverted index for the portion 500 shown in FIG. 5 could look as
`
`follows:
`
`Restaurants, I
`Pizza, 2
`Burgers, 3
`Chinese, 4
`
`A user issues the following query to the system “fast food" in order to find a quick meal.
`
`The system’s search of both the index and thesaurus would result in the “term", in this
`
`case a phrase, not being found in either.
`
`In this case, it is an unknown phrase, and the system has
`
`to learn the “meaning” ofthe term.
`
`To do this, the system first offers the verbal description from the tOp level nede(s) 502 to
`
`the user — in this example, just “Restaurants”. The user presumably provides a positive response.
`
`(Ofcourse, in a real system, it is possible and likely there are more top level nodes thanjust one.
`
`In that case, the user would be offered two or more ofthese nodes, and would have to select
`
`“Restaurants" to match his intended request.)
`
`Continuing on, once the user has responded affirmatively, the system moves down the
`
`tree and offers the verbal description from each of the child nodes: “Pizza” (504), “Burgers"
`
`(506}. and “Chinese” (508). Presutning that the user picks “Pizza”, the transaction interaction
`
`would look something like this:
`
`User: Fast food
`
`System: Restaurants?
`
`728851 v]
`
`17
`
`224
`224
`
`

`

`"ll.
`
`llfl'll iii?! “Fill "iii! Hill l'i} ii
`
`”3211
`
`...
`
`."t|..
`
`.‘..';
`
`PATENT
`Docket No.: 4428~400l
`
`User: Yes
`
`System: Pizza, Burgers, or Chinese?
`
`User: Pizza
`
`At this point, the system has “learned” for the time being that it can equate “fast food”
`
`with “pizza” and can add “fast food” as a synonym to “pizza” in the thesaurus.
`
`This user, who first used the unknown term “fast food“, had to trace a path down the tree.
`
`However, now the system is able to associate “pizza“ with “fast food“ and create or add a
`
`thesaurus entry to reflect this association, for example as follows:
`
`Fast food — Pizza
`
`Thus, the system has learned a meaning ofthe initially unknown term “fast food" and has
`
`added it to the thesaurus for future use.
`
`As a result. a subsequent uses ofthe same term “fast food" will enable the System to jump
`
`directly to the “pizza” node 504.
`
`Example 6
`
`This example illustrates how additional meanings for an existing thesaurus term or phrase
`
`can be learned by the system for future use, whether the existing thesaurus term or phrase was an
`
`original thesaurus term or one previously learned with continuing reference to FIG. 5.
`
`At this point, the inverted index is unchanged as:
`
`Restaurants, l
`Pizza, 2
`Burgers, 3
`Chinese, 4
`
`Additionally, presume the following entry now exists in the thesaurus.
`
`TESSSI vl
`
`18
`
`225
`225
`
`

`

`
`
`PA’I‘EN'I‘
`Docket No.: 4428-400]
`
`Fast food — Pizza
`
`Suppose a new user now issues the query “fast food” as above, but with “Burgers” rather
`
`than “Pizza” in mind.
`
`Based upon the thesaurus, the system would go directly to the “Pizza” node. However,
`
`the user will reject “Pizza”, having “burgers” in mind. By rejecting the “Pizza" node 504
`
`description, the user indicates that the “Pizza“ node 504 is not ofinterest. The system is
`
`therefore configured with a further set of rules, in this case one in which the system goes up in
`
`the hierarchy to a higher node, the top node 502 in this portion of the example, and provides the
`
`verbal descriptions for the other nodes 502, 504, 506, 508 so as to cause a tracing down the tree.
`
`This can be illustrated by the following “dialog":
`
`User: Fast food
`
`Systcm: Pizza?
`
`User: No
`
`System: Restaurants?
`
`User: Yes
`
`System: Pizza, Burgers, or Chinese?
`
`User: Burgers
`
`This time, although this user has had to trace through at least a portion ofthe path from a
`
`higher-level node 502 ofthe tree 500, the system has learned yet another meaning for “fast
`
`food”.
`
`It now adds this meaning to the earlier entry in the thesaurus, for example as:
`
`Fast food — Pizza, Burgers
`
`uses: VI
`
`19
`
`226
`226
`
`

`

`
`
` ' Sill. ll'iil iii-TI! “ill ”i325“ i'. ..
`
`
`
`
`
`Ill
`
`Jill. Jill.”iEil‘lliiiliiiii‘f
`
`PATENT
`Docket Ne.: 4428-4001
`
`It has now learned two meanings for future use. If a user were now to issue the query
`
`“Fast food", the system would respond with the verbal descriptions from the nodes 504, 506
`
`corresponding to both Pizza and Burgers.
`
`Thus, the system can keep learning new meanings ofterms based on the intended
`
`meanings of users “deduced” from the interactions between users and the system.
`
`Ofcourse, the nature and extent to which the system will incorporate synonyms and/or
`
`keywords in a continual learning process will not only depend upon its construction and rules,
`
`but also on the quality ofthe original thesaurus and the quality ofthe initial inverted index.
`
`In
`
`addition, where in the tree the system jumps ifthe user rejects the initial meaning(s) offered by
`
`the system can be handled different ways in different implementations.
`
`For example, the system can always jump to fixed ancestorts) (either the top node or a
`
`parent or some ancestor(s) at an intermediate point) or a fixed level (e.g. halfway from the top).
`
`This approach has the advantage of being simple to implement, but it has the problem of
`
`inflexibility because it may be relatively efficient for certain graphs and associated verbal
`
`descriptions, but not for all. For example, iftwo or more nodes’ verbal descriptions are offered
`
`and rejected, the relevant node selected would have to be common ancestor-(s) ofthc offered
`
`nodes.
`
`In other words, with reference to Example 6 which is part ofa larger tree, going up to the
`
`“Restaurants” node 502 would mean going to the parent ofthe “Pizza” node 504 rather than all
`
`the way to the top in the larger tree containing the portion 500 shown.
`
`A more flexible alternative uses the information recorded in the thesaurus to find every
`
`synonym for “pizza” in the thesaurus and collect all the other keywords associated with those
`
`synonyms. Then the system would search the inverted index to identify all the nodes associated
`
`water vi
`
`20
`
`227
`227
`
`

`

`
`
`PATENT
`Docket No.: 4428-4001
`
`with these other associated keywords and identify the most common ancestor of all oflhose
`
`nodes and go to it. By using the information in the thesaurus in this way the system makes use
`
`of known properties ofthe one meaning of“fast food", which is “Pizza”, to construct an
`
`intelligent hypothesis about where the other meanings of“fast food” might lie in the graph. This
`
`allows the user to reach another meaning with the least effort and allows the system thereby to
`
`learn what the new meaning of“fast food" is more efficiently.
`
`Example 7
`
`Of eourse,just as it may be desirable to create implementations to add meanings to the
`
`thesaurus, it may be equally or more desirable to cause an existing meaning for a thesaurus word
`
`to be dropped, for example, due to relative lack of use. This process is described with continuing
`
`reference to FIG. 5 and the associated inverted index, particularly with respect to the thesaurus
`
`entry resulting from the most recent example.
`
`Fast food — Pizza, Burgers
`
`In this example, presume that there have been several uses ofthe query “fast food” and
`
`that the uscr('s} issuing these queries have almost always selected “Burgers” and almost never
`
`“Pizza”.
`
`In accordance with another implementation ofthe invention, the system is constructed to
`
`track the frequency of use ofa particular term in the thesaurus. Depending upon the particular
`
`implementation, the tracking can be done for all entries in the thesaurus, for only those added as
`
`part ofthe “learning” process, or for some specified combination thereof.
`
`in addition, some specified criterion is used to determine when, and which terms, if any,
`
`should be removed from the thesaurus. Depending upon the particular implementation the
`
`723851 vl
`
`2t
`
`228
`228
`
`

`

`
`
`
`
`PATENT
`Docket No.: 442 8-4001
`
`criterion can be based upon usage relative to time, usage ofa particular term relative to some
`
`other tenn(s),_tenn usage relative to overall thesaurus usage, or simply elimination ofall added
`
`terms not used since the last purge.
`
`Thus, presuming that the system has kept track of the frequency of use ofdifferent
`
`meanings of‘“fast food", and that “Pizza” does not meet the criterion for a sufficiently high
`
`frequency, the meaning “Pizza” can be dropped as a synonym for “Fast food“ and the entry (after
`
`purging) would look as follows:
`
`Fast food .. Burgers
`
`Thus, a further enhanced implementation can be constructed so the system is dynamically
`
`updating the thesaurus, either adding meanings or drOpping meanings for existing andfor initially
`
`unknown words.
`
`Example 8
`
`A further advantage to the invention is that, in some implementations, it can be
`
`configured so that, when there are multiple relevant nodes to be presented, an associated ranking
`
`can be used to determine the type, method or order of presentation. For example, the ranking can
`
`be based upon the frequency ofuse of particular nodes, which is tracked in these
`
`implementations, so that the most frequently selected or used nodes are presented first, more
`
`prominently, or in a particular manner.
`
`For example, this can be illustrated by continuing from Example 7, where the thesaurus
`
`entry was as folloWS:
`
`Fast food — Pizza, Burgers
`
`T2885] VI
`
`22
`
`229
`229
`
`

`

`
`
`PATENT
`Docket No.: 4428-4001
`
`Under the assumption that the system has been tracking the frequency of usage ofthe “Pizza”
`
`_ node and the “Burgers" node and each has been accessed an identical number oftimes. When a
`
`user enters the query “Fast food", as above, the system presents the user with both the “Pizza"
`
`node 504 and the “Burgers" node 506, but because it tracks usage and the usage is the same, it
`
`presents them in the order they are listed, i.e. “Pizza” and then “Burgers". However, at this
`
`point, the user’s selection will cause one entry to have a greater frequency of usage relative to the
`
`othcr entry, for example a selection of“Burgers” will make it have a higher frequency of usage
`
`and, accordingly, a higher ranking for the next instance of use.
`
`Thus, the next time the system will be presenting both the “Pizza" and “Burgers“ nodes
`
`to a user, the “Burgers" node 506 will have the higher frequency of usage and, accordingly, will
`
`be presented first, or more prominently, or in some other specified manner because ofits
`
`ranking.
`
`lfthe frequency reverses with use so that thc “Pizza” node 504 outranks “Burgers”
`
`node 506, then the ”Pizza" node 504 will supplant the “Burgers“ node 506.
`
`Example 9
`
`A further variant ofExample 8 allows the node rankings to be used to prune the nodes
`
`themselves.
`
`in this variant, a criterion can be specified, typically zero usage over a long
`
`specified period oftime, that is used to remove an entire node. This is advantageously made
`
`possible because ofthe system’s ability to “jump” among nodes. Thus, it may occur that a node
`
`within the tree is never accessed, but a Child node ofthat node is.
`
`In some variants therefore,
`
`when this state exists for a sufficiently long period of time, the system is constructed to delete
`
`that node.
`
`It should be understood that, if handled preperly, this process will not even affect the
`
`“Ieamin “
`
`,
`P
`recess because even ifno user action ever direct] causes the node to be resented,
`
`72835; vl
`
`23
`
`230
`230
`
`

`

`Lit.
`
`liliilii-TI ”Jill
`
`'lIEEL' Liiiilillifii'l-Elfi
`
`m til.
`
`.Iiil.
`
`.Ilil.
`
`”19%| tl'llt Iii-Tl!
`
`PATENT
`Docket No.: 4428-4001
`
`ifthe learning process causes the node to be presented the node’s access frequency will be non-
`
`zeroand it will not be “pruned",
`
`In addition, by tracking access frequency on a node basis, a qualitative evaluation ofthc
`
`hierarchical system can be made and visualized. This makes it possible to review the overall
`
`hierarchy after some period oftime and periodically optimize it based upon the result instead of
`
`relying purely upon the dynamic optimization that inherently and naturally flows from use of the
`
`teachings ofthe invention.
`
`Having now described various component aspects of different variants implementing the
`
`invention, by way ofthe above examples, it should be understood that the “jumps" can occur
`
`from any node to any node, i.e. vertically andx‘or laterally and to another node that is higher,
`
`lower or on the same “level" as the node from which the jump is made. All manner of vertical
`
`and lateral jumps from multiple nodes to multiple nodes are possible,
`
`In addition, it should be understood that in some applications (like dOCument retrieval
`
`systems) the verbal description from the identi lied node may be the one issued whereas, in others
`
`(like an IVR system), the verbal descriptions for the children of the identified nodes may be what
`
`is presented. Nevertheless, in both cases, the process as described above by way of example will
`
`be the same or directly analogous,
`
`Having described the various aspects individually a more commercially suitable example,
`
`employing a combination ofthe above examples, can now be presented with reference to FIG. 6
`
`which illustrates a simplified example of an “interactive voice response unit" (IVR) hierarchy
`
`600 that might be used in the airline industry. Of course, a real menu tree used in an IVR may
`
`have any number of nodes from several, up to a thousand, or more. For example, a tree with 4
`
`7288M vl
`
`24
`
`231
`231
`
`

`

`
`
` -." xii- :15- “131“ #2341 iiELE!‘
`
`
`
`branches from each node and which has 5 levels uniformly would have [365 nodes. As shown
`
`in FIG. 6, the tree 600 is a hierarchical tree and consists ofthe following nodes and branches:
`
`PA'I‘EN'I'
`Docket N0.: 442 8-4001
`
`Initial start {node 30) 602
`
`domestic flight arrival information (node al) 604
`
`domestic reservations (node a2) 606
`
`international flight arrival information (node 33) 608
`
`intemational reservations (node a4) 610
`
`The node 604 identified by at is a service node with pre-recorded information.
`
`The node 606 has two child node a 2, firsti'busincss class (node a5) and economy (node 36).
`
`The node 608 identified by a3 is service node with pre-recorded information.
`
`The node identified as a4 has three child nodes identified as first class (node 3?), business class
`
`(node a8), and economy (node a9).
`
`The nodes 6l2, 6 14, 6t 6, 618, 620 identified as a5, a6, a7, a8, a9 are all service nodes (i.e.
`
`terminal nodes) where a respective customer service representative will interact with the caller