`
`ELASTIC - EXHIBIT 1002 - Part 2 of 3
`
`
`
` THTiesek aE
`
`PATENT
`Docket No.: 4428-4001
`
`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 becauseit has minimal meaning in that context.
`
`Again, the other words can be ignored as well.
`
`The unique identification of each node allowsthe creation of a list of all the key words
`
`and their associated nodesso that, if a key word is duplicated in two or more nodes,it need only
`
`be listed once. For example, a hierarchicaltree related to “pens” might have nodesfor ball-point
`
`pens, fine point pens, mediumpoint 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
`
`of the 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 inventionwill be 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 of these associationsthe “‘tree’’ can be negotiated by allowing presentation
`
`of relevant verbal descriptions for the nodes associated with a term, irrespective of where in the
`
`728851 vi
`
`(cid:21)(cid:20)(cid:24)
`215
`
`
`
`
`
`
`
`PATENT
`Docket No.: 4428-4001
`
`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 bepresentedto illustrate certain concepts related to the
`
`invention.
`
`It 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 of transaction 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 througha hierarchy to a goal, not mathematical calculation perse.
`
`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 hashtables, direct or indirect indexing, etc. can be substituted in a straightforward
`
`manner. Thus, for example, the relationship between the word and a node could be configured
`
`such that the location of the wordinalist as the “n-th” item could be used as an index into
`
`anotherlist containing the nodescorrelated to the list. A similar approach could be used for the
`
`thesaurus, the important aspect relative to the invention being the relationship amongcertain
`
`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 | illustrates, in simplified form, how an index is used to jump among nodes
`
`with reference to FIG. 2.
`
`In this example, the hierarchical tree 200 represents a portion of a more
`
`728851 v1
`
`(cid:21)(cid:20)(cid:25)
`216
`
`
`
`TAL ACTaes est ap TSG Me SOL SHLD ESet
`
`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 of this 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 of a 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?”if the
`
`response was anything other than “fruit” traversal to the “fruit” node 202 could not occur. At the
`
`pointin the tree that would lead to the “fruit” node 202, neither apple nor orange would be an
`
`acceptable response.
`
`In accordance with the invention, assuming the only relevant keywords for that portion of
`
`the tree were “fruit”, “apple” and “‘orange”’, an inverted index wouldbe created that includes an
`
`association of “Fruit” with the top node 202, “Apple” with the bottom left node 204, and
`
`“Orange” with the bottomright node 206. As shown above, that association can be created using
`
`nodeidentifiers, in this example, the node identifiers 1A01, 1AQ2 and 1A03 are arbitrarily
`
`assigned and used. Thus, the information can be stored inafile, for example, as follows:
`
`Fruit, 1A01
`Apple, 1A02
`Orange, 1A03
`
`Accordingly, to navigate the system 200, when a response to a verbal description is
`
`provided by a user, possible keywordsare identified in the response and used to search the index
`
`and identify any node to which the response may be directed, irrespective of the hierarchy.
`
`Thus, a user response of “an orange” to a verbal description located above the “fruit” node 202 in
`
`728851 vi
`
`10
`
`(cid:21)(cid:20)(cid:26)
`217
`
`
`
`ietas
`
`
`
`wo ARaeek
`
`PATENT
`Docket No.: 4428-4001
`
`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) 1A01, at all.
`
`This illustrates an example of a simple jump accordingto the invention.
`
`Example 2
`
`Havingillustrated a simple “node jump” a more complex (and likely) scenario can be
`
`shown.
`
`In this example, the Example | graph of FIG. 2 applies, but relevant portion of the index
`
`is as follows:
`
`Fruit, 1A01
`Apple, 1A02, 2F09
`Orange, 1A03
`
`As aresult, there are two nodesrelevant to the keyword “apple” one being the node 204
`
`in the portion of the graph shownin FIG. 2 and one in the node uniquely identified as 2F09
`
`located somewhereelse in the hierarchy (not shown).
`
`In this example, a user response containing the keyword “apple” would identify nodes
`
`with identifiers |AOQ2 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, if the user
`
`did not want an apple, they wanted apple cider, node 2FO9 might be more appropriate becauseit
`
`is part of the “drinks” portion of the overall hierarchy.
`
`Thus, presenting the user with the verbal description from both nodes would likely result
`
`in a jumpto the portion of the graph nearer to node 2F09 sinceit is closer to the user’s goal
`
`thereby speeding up the process and avoiding potentially confusing or frustrating the user.
`
`728851 vl
`
`11
`
`(cid:21)(cid:20)(cid:27)
`218
`
`
`
`We
`
`
`
`rt eo at a SIL AL ak etl
`
`
`
`PATENT
`Docket No.: 4428-4001
`
`Example3
`
`While the verbal descriptions associated with various nodes will generally be chosen to
`
`accurately represent the node, in accordance withcertain variants of the invention,it is possible
`
`to create a situation where a user response takes them awayfrom their ultimate desired goal.
`
`Nevertheless, by using the teachings of the present invention, the user can often still be brought
`
`to their goal quicker than possible with the prior art because the user need notrigidly trace
`
`throughthe hierarchy. This is accomplished by virtue of the “grouping” aspect inherent in some
`
`implementations of the invention.
`
`This exampleillustrates the “grouping” aspect using a simplified graph 300 representing
`
`a portion of an airline reservation system as shownin FIG. 3.
`
`In particular, the graph of FIG.3 can be thoughtofas part of a very simple interactive
`
`voice response (“IVR”) system.
`
`Asdescribed above, each nodeis uniquely identified, for example, by the numbers 1
`
`through 7 and the identified terms “Reservation”, “Domestic”, “International”, “Business Class”,
`
`“Economy Class” are deemed the relevant keywords. Note, there is no requirementfor a the
`
`“keyword”to be a single word, in some implementations, keywords could be single words,
`
`phrases of two or more words, or even some other form of information like a specific data
`
`pattern.
`
`Again, an inverted index is created as described above associating those keywords with
`
`the nodes, in this case:
`
`|
`
`Reservation,
`Domestic, 2
`International, 3
`
`728851 vi
`
`12
`
`(cid:21)(cid:20)(cid:28)
`219
`
`
`
`aact
`
`PATENT
`Docket No.: 4428-4001
`
`Business Class, 4, 6
`Economy Class, 5, 7
`
`Assumingthat the top node is assigned the number1, 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 numbers4, 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 cach associated with
`
`two nodes, 4 and 6 inthe first case, and 5 and 7 in the second.
`
`Using the above, the concept of grouping of nodes from different parts of the graph(i.e.
`
`nodes that are not siblings or nodes that do not have a commonparent) can be explained.
`
`Presume that the response to a verbal description presented as an initial query of “What
`
`do you want to do?” was “Makea businessclass reservation.” In this case there are two
`
`keywordspresent, “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 thatif
`
`an identified node is a sub-node of another identified node, only the verbal description of the
`
`sub-node(s) is provided because of inherent redundancy. Thus, since both “business class”
`
`nodes 310, 314 are sub-nodes of the “reservation” node 302,the verbal description associated
`
`with the “reservations” node can be suppressedif it can be determined that business class
`
`necessarily implies reservations.
`
`In this example, a search of the inverted index would identify nodes 4 and 6 (310, 314)
`
`from different parts of the tree are associated with the keywords in the query, and thus the
`
`728851 v1
`
`13
`
`(cid:21)(cid:21)(cid:19)
`220
`
`
`
`aL a eb al Ae
`
`wa AIL oH ee aes
`
`PATENT
`Docket No.: 4428-4001
`
`system, in presenting the verbal descriptions from each, in effect, alters the tree structure and
`
`groups these nodesin the result. Thus, the combination of result nodes presented depends upon
`
`the user query or response, not that predetermined by the graphstructureitself.
`
`Of course, the goal would still not be reached because of the ambiguity caused by
`
`“Business Class” being under both “Domestic” and “International”. However, that ambiguity
`
`can be handled by suitable wording of the following verbal descriptions and whetherthey are
`
`combinedor provided sequentially or by other nodes.
`
`Example 4
`
`A persistent and further drawback present in the priorart is the inability to operate if any
`
`term other than the specific allowed terms are provided. Thus, in an IVR ofthe priorart,
`
`providing anything other than the recognized term(s) will likely result in meaningless repeat of
`
`the same inquiry by the IVR oran error.
`
`Advantageously, the teachings of the 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 of a simple thesaurus as an aspect of a system so that a
`
`synonym of a keyword may also be used by the system to jump to the desired nodesin 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.
`
`728851 vi
`
`14
`
`(cid:21)(cid:21)(cid:20)
`221
`
`
`
` foe IL ES
`
`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 characters, the portion of
`
`which corresponding to FIG. 4 is shownasfollows.
`
`Programs; acgyct
`Sitcoms; ifgnxh
`Films; vnymos
`
`Since a common synonymfor“Films”is “Movies” a thesaurus can be created associating
`
`the two. Depending uponthe 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 of terms can be done in any ofa myriad ofdifferent ways,
`
`the exact implementation details of which howeverre irrelevant to the invention, but a few
`
`representative examples of which howeverare contained herein for purposes of illustration.
`
`In one example case, the equating can be done on a purely wordbasis. For example, a
`
`file can be constructed such that one or more single word synonymsare 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 formercase, the system wouldstill have to search the index after the thesaurus has
`
`provided the proper index term(s).
`
`In the latter case, the thesaurus providesa directlink to the
`
`respective node(s) so that re-searching is not required.
`
`728851 v1
`
`15
`
`(cid:21)(cid:21)(cid:21)
`222
`
`
`
` HLessa PH iw SA A et
`
`PATENT
`Docket No.: 4428-4001
`
`In the system of Example 4, a user who provides the input “Movies” would cause the
`
`processing to occuras follows.
`
`The system would search the inverted index of keywords and fail to locate “Movies” as a
`
`keyword. Asa 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 uponthe particular
`
`thesaurus, 1t would either return 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.
`
`Of course, it is possible (and likely) that in actual usage a synonymwill 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 result in the system identifying that the
`
`synonym wasassociated with nodes 404, 406 for both “Sitcoms” and“Films”, and it would
`
`return both terms or node identifiers corresponding to the two keywordsasthe 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 whichis a portion 500 of a larger
`
`system graphaspart of a very simple “geographic information system” found in some
`
`automobiles, kiosks and elsewhere today. Such a system enables a user to, among other things,
`
`728851 vl
`
`16
`
`(cid:21)(cid:21)(cid:22)
`223
`
`
`
`AL. ACret Heat Ht
`
`
`
`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 shownin FIG. 5 could look as
`
`follows:
`
`Restaurants, |
`Pizza, 2
`Burgers, 3
`Chinese, 4
`
`A userissues 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 unknownphrase, and the system has
`
`to learn the “meaning”ofthe term.
`
`To dothis, the systemfirst offers the verbal description from the top level node(s) 502 to
`
`the user — in this example, just “Restaurants”. The user presumably providesa posilive response.
`
`(Of course, in areal 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 of these nodes, and would haveto select
`
`“Restaurants” to match his intended request.)
`
`Continuing on, once the user has respondedaffirmatively, the system moves downthe
`
`tree and offers the verbal description from each of the child nodes: “Pizza” (504), “Burgers”
`
`(506), and “Chinese” (508). Presuming that the user picks “‘Pizza’’, the transaction interaction
`
`would look somethinglike this:
`
`User: Fast food
`
`System: Restaurants?
`
`728851 v1
`
`17
`
`(cid:21)(cid:21)(cid:23)
`224
`
`
`
`
`HTeth es a ALL
`
`PATENT
`Docket No.: 4428-4001
`
`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 synonymto “pizza”in the thesaurus.
`
`This user, who first used the unknownterm “fast food”, had to trace a path downthetree.
`
`However, now the systemis 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 meaningof the initially unknownterm“fast food” and has
`
`addedit to the thesaurus for future use.
`
`As aresult, a subsequent uses of the 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 termor 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, |
`Pizza, 2
`Burgers, 3
`Chinese, 4
`
`Additionally, presume the following entry now exists in the thesaurus.
`
`728851 v1
`
`18
`
`(cid:21)(cid:21)(cid:24)
`225
`
`
`
`» 4 ALA
`
`PATENT
`Docket No.: 4428-4001
`
`Fast food — Pizza
`
`Suppose a newuser nowissues the query “fast food” as above, but with “Burgers” rather
`
`than “Pizza” in mind.
`
`Based uponthe 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 of interest. The systemis
`
`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 downthetree.
`
`This canbeillustrated by the following “dialog”:
`
`User: Fast food
`
`System: Pizza?
`
`User: No
`
`System: Restaurants?
`
`User: Yes
`
`System: Pizza, Burgers, or Chinese?
`
`User: Burgers
`
`This time, although this user has had to trace throughatleast a portion of the 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
`
`728851 vi
`
`19
`
`(cid:21)(cid:21)(cid:25)
`226
`
`
`
`
`
` Sah eT Paw Te ies
`
`PATENT
`Docket No.: 4428-4001
`
`It has now learned two meaningsfor future use. [f a user were now to issue the query
`
`“Fast food”, the system would respond with the verbal descriptions from the nodes 504, 506
`
`correspondingto both Pizza and Burgers.
`
`Thus, the system can keep learning new meanings of terms based on the intended
`
`meanings of users “deduced”fromthe interactions between users and the system.
`
`Of course, the nature and extent to which the system will incorporate synonyms and/or
`
`keywords in a continual learning process will not only depend uponits construction and rules,
`
`but also on the quality of the original thesaurus and the quality of the initial inverted index.
`
`In
`
`addition, where in the tree the system jumpsif the user rejects the initial meaning(s) offered by
`
`the system can be handled different ways in different implementations.
`
`For example, the system can always jumpto fixed ancestor(s) (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 approachhas 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, if two or more nodes’ verbal descriptions are offered
`
`and rejected, the relevant node selected would have to be commonancestor(s) of the offered
`
`nodes.
`
`In other words, with reference to Example 6 which is part of a larger tree, going up to the
`
`“Restaurants” node 502 would mean goingto the parent of the “Pizza” node 504 rather than all
`
`the way to the top in the larger tree containing the portion 500 shown.
`
`A moreflexible 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
`
`728851 vl
`
`20
`
`(cid:21)(cid:21)(cid:26)
`227
`
`
`
`
`
`PATENT
`Docket No.: 4428-4001
`
`with these other associated keywordsand identify the most commonancestorof all of those
`
`nodes and go to it. By using the information in the thesaurusin this way the system makes use
`
`of knownproperties of the one meaning of “fast food”, whichis “Pizza”, to construct an
`
`intelligent hypothesis about where the other meanings of “fast food” mightlie in the graph. This
`
`allows the user to reach another meaning withthe least effort and allows the system thereby to
`
`learn what the new meaningof “fast food” is more efficiently.
`
`Example 7
`
`Ofcourse, 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, presumethat there have been several uses of the query “fast food” and
`
`that the user(s) issuing these queries have almost always selected “Burgers” and almost never
`
`“Pizza”.
`
`In accordance with another implementation of the invention, the system is constructed to
`
`track the frequency of use of a particular term in the thesaurus. Depending upon the particular
`
`implementation, the tracking can be doneforall entries in the thesaurus, for only those added as
`
`part of the “learning” process, or for some specified combination thereof.
`
`In addition, some specified criterion is used to determine when, and whichterms,if any,
`
`should be removed from the thesaurus. Depending upon the particular implementation the
`
`728851 vi
`
`zl
`
`(cid:21)(cid:21)(cid:27)
`228
`
`
`
`
`
`
`
`PATENT
`Docket No.: 4428-4001
`
`criterion can be based uponusagerelative to time, usage of a particular term relative to some
`
`otherterm(s), term usage relative to overall thesaurus usage, or simply elimination of all added
`
`terms not used since the last purge.
`
`Thus, presuming that the system has kept track of the frequencyof use of different
`
`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 and/orinitially
`
`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 of use 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 wasas follows:
`
`Fast food — Pizza, Burgers
`
`728851 v1
`
`22
`
`(cid:21)(cid:21)(cid:28)
`229
`
`
`
` CYi ow OL aL,
`
`PATENT
`Docket No.: 4428-4001
`
`Underthe assumption that the system has been tracking the frequency of usage of the “Pizza”
`
`_ node and the “Burgers” node and each has been accessed an identical number of times. 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 becauseit tracks usage and the usageis the same, it
`
`presents them in the order theyarelisted, i.e. “Pizza” and then “Burgers”. However,at this
`
`point, the user’s selection will cause one entry to have a greater frequency ofusagerelative to the
`
`other 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 ofuse.
`
`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 becauseof its
`
`ranking. If the frequency reverses with use so that the “Pizza” node 504 outranks “Burgers”
`
`node 506, then the “Pizza” node 504 will supplant the “Burgers” node 506.
`
`Example 9
`
`A further variant of Example 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 of time, that is used to remove an entire node. This is advantageously made
`
`possible because of the system’s ability to “jump” among nodes. Thus, it may occur that a node
`
`within the tree is never accessed, but a child node of that node is.
`
`In some variants therefore,
`
`whenthis state exists for a sufficiently long period of time, the system is constructed to delete
`
`that node.
`
`It should be understoodthat, if handled properly, this process will not even affect the
`
`>
`p
`“learning” process because, even if no user action ever directly causes the node to be presented,
`
`728851 vl
`
`23
`
`(cid:21)(cid:22)(cid:19)
`230
`
`
`
`SALAeeAG Me eS HSEH
`
`PATENT
`Docket No.: 4428-4001
`
`if the learning process causes the node to be presented the node’s access frequency will be non-
`
`zero andit will not be “pruned”.
`
`In addition, by tracking access frequency on a nodebasis, a qualitative evaluation of the
`
`hierarchical system can be made and visualized. This makesit possible to review the overall
`
`hierarchy after some period of time and periodically optimize it based uponthe result instead of
`
`relying purely upon the dynamic optimization that inherently and naturally flows from use ofthe
`
`teachings of the invention.
`
`Having now described various component aspects of different variants implementing the
`
`invention, by way of the above examples, it should be understood that the “jumps” can occur
`
`from any nodeto any node,i.e. vertically and/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 mannerof vertical
`
`and lateral jumps from multiple nodes to multiple nodes are possible.
`
`In addition, it should be understood that in some applications (like documentretrieval
`
`systems) the verbal description from the identified node may be the one issued whereas, in others
`
`(like an [VR 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 sameordirectly analogous.
`
`Having described the various aspects individually a more commercially suitable example,
`
`employing a combination of the above examples, can now be presented with reference to FIG. 6
`
`whichillustrates a simplified example of an “interactive voice response unit” ([VR) hierarchy
`
`600 that might be used in the airline industry. Of course, a real menu tree used in an TVR may
`
`have any numberof nodes from several, up to a thousand, or more. For example, a tree with 4
`
`728851 vi
`
`24
`
`(cid:21)(cid:22)(cid:20)
`231
`
`
`
` io OkaS
`
`PATENT
`Docket No.: 4428-4001
`
`branches from each node and whichhas5 levels uniformly would have 1365 nodes. As shown
`
`in FIG. 6, the tree 600 is a hierarchical tree and consists of the following nodes and branches:
`
`Initial start (node a0) 602
`
`domestic flight arrival information (node al) 604
`
`domestic reservations (node a2) 606
`
`internationalflight arrival information (node a3) 608
`
`international reservations (node a4) 610
`
`The node 604 identified by al is a service node with pre-recorded information.
`
`The node 606 has two child nodea 2, first/business class (node a5) and economy (nodea6).
`
`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 a7), business class
`
`(node a8), and economy (node a9).
`
`The nodes 612, 614, 616, 618, 620 identified as a5, a6, a7, a8, a9 are all service nodes(i.c.
`
`terminal nodes) where a respective customerservice representative will interact with the caller.
`
`Of course, a real system may also have a choiceat the top level or at each level for a live
`
`operator and may even have a choice to go back to the previous menu.
`
`Evenfor such a simple example, in a traditional interactive voice response system, the
`
`caller would have to listen to several choices and then traverse a path downto a service node.
`
`Someoneinterested in business class reservations on a domestic flight would have to traverse the
`
`path (a0, a2, a5) for example. This involves listening to multiple choicesat cach level of the tree
`
`(e.g. first a prompt at a0, then four prompts offering al, a2, a3, and a4 at the next level, at which
`
`the caller would choose a2, and finally two prompts offering a5 and a6, at which level the caller
`
`728851 vl
`
`25
`
`(cid:21)(cid:22)(cid:21)
`232
`
`
`
`A ASH ee
`
`A BS ee
`
`
`PATENT
`Docket No.: 4428-4001
`
`would choose a5 and then wait for the operator) and then making a choice by pressing an
`
`appropriate number on the telephone dial pad or alternatively saying the appropriate number. In
`
`certain cases, he may make a mistake: he may choose international reservations when heis
`
`interested in domestic reservations or something similar (simply by pressing the wrong number
`
`on his touch-tone telephone or saying the wrong number). If he does, then he has no choice but
`
`to disconnect the phoneandredial the number(orif the system has a backtracking option, then
`
`he can backtrack, but even here he has wasted valuable time).
`
`In contrast, in accordance with a system implementing the invention, the caller would be
`
`able to say what he was lookingfor (e.g. “I want to make a domestic business class reservation’’)
`
`and the system would identify and respond with the appropriate node 612 (e.g. a5 in this case or
`
`the relevant customer service representative directly).
`
`In other words, it would enable the caller
`
`to skip to the correct node(s) without having to trace through the entire path. If the user makes a
`
`mistake, he could ask for something different wherever he finds himselfin the tree, and skip
`
`laterally or vertically to his preferred choice.
`
`The system implementing the invention can further include an option that the entire
`
`transaction (e.g. the making of the reservation) would becarried out through natural language
`
`interactions with the system without the intervention o