System, method, and computer program product for a network-based content exchange system6735592Abstract A system, method and computer program product are provided for providing a content exchange system. A request is received from a user utilizing a local system. A determination is made as to whether the user request can be fulfilled from information stored by the local system. The request is fulfilled from a local data source if the request can be fulfilled locally. If the request cannot be fulfilled locally, the request is fulfilled at a network site. A content directory connected to the network site is examined for selecting one or more network data sites having content potentially satisfying the request. The request is sent to the data site(s). Content pertaining to the request is received from the data site(s) and sent to the user. Claims What is claimed is: Description FIELD OF THE INVENTION
TABLE 1
1. Tokenizer. This phase accepts a stream of characters as input, and
transforms it into a sequence of tokens.
2. Multiword Analyzer. This phase is generated automatically by the
lexicon to recognize token sequences (like "because of") that are
combined to form single lexical items.
3. Name Recognizer. This phase recognizes word sequences that can be
unambiguously identified as names from their internal structure (like
"ABC Corp." and "John Smith").
4. Parser. This phase constructs basic syntactic constituents of the
language, consisting only of those that can be nearly unambiguously
constructed from the input using finite-state rules (i.e., noun groups,
verb groups, and particles).
5. Combiner. This phase produces larger constituents from the output of
the parser when it can be done fairly reliably on the basis of local
information. Examples are possessives, appositives, "of"
prepositional phrases ("John Smith, 56, president of IBM's
subsidiary"), coordination of same-type entities, and locative and
temporal prepositional phrases.
6. Domain or Clause-Level Phase. The final phase recognizes the
particular combinations of subjects, verbs, objects, prepositional
phrases, and adjuncts that are necessary for correctly filling the
templates for a given information extraction task.
The rules for each phase may be specified in a pattern language, such as "FAST-SPEC" available through SRI International. The rules take the form of regular productions that are translated automatically into finite-state machines by an optimizing compiler. There are many good reasons for extending a separation between application-independent rules and application-specific instances to earlier phases of the present embodiment, in particular to the Parser and Combiner. Example 1 illustrates the various ways in which the simple predication pollute (x, body-of-water) might be expressed, and patterns automatically generated to parse. EXAMPLE 1 full clauses in the Domain phase "they polluted the stream" "the reservoir has been contaminated" complex noun phrases in the Combiner phase "the contamination of the creek" "the bay's pollution" compound nouns in the Parser phase "the water pollution" "the polluted lake" Table 2 illustrates the general pattern for the first of the two complex noun phrases of Example 1. In such phrases, the object of the "of" phrase is the object of the event expressed by the head of the noun phrase ("contamination").
TABLE 2
ComplexNP --> ({NP[??subj] .vertline. NP[??obj]} P[subcat=gen])
{V-ING[TRANS,??head] .vertline. NP[TRANS,??head]}
{ P["of"] NP[??obj] .vertline.
P["by"] NP[??subj] .vertline.
P[??prep1] NP[??pobj1] .vertline.
P[??prep2] NP[??pobj2] }*;
??semantics ;;
Table 3 sets forth a topic-specific instance of the pattern of Table 2.
TABLE 3
Instantiate
OfNP
??label = combiner-1-pollute
??subj = chemical
??head = pollute
??obj = body-of-water
??semantics = weight = (assign-weight ((subj && obj) 10000).vertline. (obj
1000))
;;
The topic-specific instance of Table 3 can be thought of as a collection of macro definitions. During grammar-compilation, the "macro calls" in the patterns are expanded. In Table 3, the string "??subj" is replaced by "chemical"; "??head" by "pollute", and so on. The resulting instantiated pattern is shown in Table 4.
TABLE 4
ComplexNP --> ({NP[chemical] .vertline. NP[body-of-water]}
P[subcat=gen])
{V-ING[TRANS, pollute] .vertline. NP[TRANS, pollute]}
{ P["of"] NP[body-of-water] .vertline.
P["by"] NP[chemical] }*;
weight = (assign-weight ((subj && obj) 10000).vertline. (obj 1000));;
Items in square brackets of Table 4 represent constraints on the phrase. For instance, "stream", "river" and "reservoir" are all nouns with the lexical feature body-of-water and only noun phrases with such nouns as heads satisfy the constraints on noun phrases in the rule instance. EXAMPLE 2 Grammar Writing Plus Probabilistic Models Having extended the method of general rules and application-specific instances to the Parser and Combiner, the example focuses on the ability to write grammars for multiple topics. The topic associated with the present example includes: "Document will announce the appointment of a new CEO and/or the resignation of a CEO of a company." The foregoing topic was run in a database as an ad hoc query, producing a set of 1000 text documents it deemed most likely to be relevant, and ranking them in order from most likely relevant to least likely. Both the document set and the ordering served as inputs to information extraction sub-system. In one embodiment, the information extraction sub-system may include FASTUS offered by SRI International. For more information on such system, reference may be made to: Doug Appelt, John Bear, Jerry Hobbs, David Israel, Megumi Kameyama, Andrew Kehler, Mark Stickel, and Mabry Tyson. 1995. SRI International's FASTUS System MUC-6 Test Results and Analysis. In Proceedings of the 6th Message Understanding Conference, ARPA, Columbia, Md.; and Doug Appelt, John Bear, Jerry Hobbs, David Israel, Megumi Kameyama, Mark Stickel, and Mabry Tyson. 1996. FASTUS: A Cascaded Finite-State Transducer for Extracting Information from Natural-Language Text. In Emmanuel Roche and Yves Schabes (eds.) Finite State Devices for Natural Language Processing. MIT Press, Cambridge, Mass., which are each incorporated herein by reference in their entirety. Further, it should be noted that the document retrieval sub-system may include SMART offered by GENERAL ELECTRIC. Two different schemes were tried for using the information from the information extraction sub-system to reorder the input list. Both involved configuring the grammar to assign scores to phrases based on correlation of phrase type with relevance. In one scheme, scores were assigned to patterns manually, based on intuitions as to differential contributions to relevance judgments; in the second, a probabilistic model for the relevance of a document was inferred from a set of training data. As a basis for the present experiment, 100 were picked articles from the middle of the ordered set that the document retrieval sub-system produced (in particular, articles ranked 401 through 500). The templates that the information extraction sub-system produced from those articles were examined to identify criteria for assigning a relevance rank to an article. The information extraction sub-system then assigned a numerical score from 0.1 to 1000 to the templates that it produced for a phrase. The manner in which this scoring is carried out is shown in Table 5.
TABLE 5
1. CEO + person name + company name .fwdarw. 1000
2. CEO + company name .fwdarw. 100
3. CEO + person name .fwdarw. 10
4. CEO + transition verb .fwdarw. 1
5. CEO + BE verb .fwdarw. 0.1
The score of a phrase was taken to be the sum of the scores of the templates created from that phrase; the scores from the phrases were summed to yield an article's score. For a second experiment, it was asked how a system for automatically identifying features concerning the output of the information extraction sub-system would compare with the results obtained by the manually tuned system. This was accomplished by first determining the relative strengths of the features concerning the output of the information extraction sub-system. A probabilistic model for the relevance of a document was inferred from a set of training data. In yet another experiment, a ranked list of 2,000 documents for each query were used. Grammars for 23 of the 47 topics were developed. For these 23 topics, the information extraction sub-system ran over the 2,000 articles, reordered them, and truncated the same to 1000. For the other 24 topics, the original ordering was truncated at 1000 documents. As in the first experiments set forth hereinabove, the reordering is achieved by having patterns, that is, instances (see example above), assign a score to the segment (phrase) of an article successfully matched against. An article's total score is the sum of the scores of all the patterns that matched against phrases in that article. For each topic, a small number of relevant articles (10-15) were read, and a topic-specific grammar was constructed by writing instances of the kind exemplified above. The grammar was then run over some portion of the training data. Whenever a pattern matched a phrase, the phrase was recorded as being either a correct match or a false positive. Both sets of phrases were then reviewed to look at some of the relevant articles that were missed, and revise the grammar. After a small number of iterations of this kind, the grammar was declared done, and work was then started on the next topic. The scores were assigned with a threshold score in mind. An article had to contain at least one pattern that had a score of 1000 or above to be moved toward the beginning of the ordering; scores below 1000 had no effect on the order and were used solely for diagnostics. There was one exception to this general rule. In one topic, the following mini-experiment was used: phrases were assigned maximum scores of 250, so that at least four matching phrases were needed to move an article to the front of the ranking. This was intended to handle cases where one could find no especially reliable phrasal indicators of relevance. Another way to put this is that this method is a crude approximation to a statistical approach based on co-occurrence data. When writing the grammars, the present approach was to aim for high precision and to sacrifice recall when in a position to make a precision/recall tradeoff. As noted above, grammars were written for 23 of the topics. FIG. 4 illustrates a graph 400 of precision versus recall for the 23 topics. The overall results of the combined system for average precision are: 12 topics above the median; 3 at the median; and 8 below the median. Various guidelines may be followed during use of the present embodiment. Table 6 illustrates such guidelines.
TABLE 6
.multidot. There should be sufficient data, in particular, enough relevant
articles,
(i) to accumulate patterns for the initial grammar-writing exercise and
(ii) to use as a training corpus for adding to and "debugging" those
grammars.
.multidot. There should be fairly reliable indicators of relevance that are
fully
phrasal in structure.
.multidot. If relevant data is scarce in a given corpus, it is worth it to
go out and
look for more.
.multidot. In following a hybrid approach, it is important to use the
output of the
document retrieval system in training.
Content Exchange System FIG. 5 illustrates a Content Exchange (CE) system 500 according to an embodiment of the present invention. The system includes all participating local systems with their associated Dialogue Managers, Extraction Engines and local Information Caches, (and any local structured databases the Dialogue Managers can query). At its center is a networked content directory, which contains representations of the information holdings of the sites in the Network and which is used to handle requests from local systems for content from the network. A user at a local System (portal) 502 makes a Natural Language request of the Dialog Manager 504 (at the local site). Following are four models that can be used to determine whether the query will be handled locally: If the local Topic Determiner 506 determines that content is available locally (via result of the local query parser and content directory 508) the request is satisfied from the local NL Cache (Information Cache) 510 or local structured database(s) 512. See the section below entitled "Local Topic Determiner" for more information. Alternatively, all requests can be sent directly to the Content Exchange 514 for determination of the appropriate cache, which might be the local cache 510 described in the previous paragraph. The Local cache can start to answer the query while also forwarding it to the Content Exchange, which then compares all the results and ranks them. As a final alternative, the most likely entries in the network content directory 516 could be replicated in the local content determiner so that the most likely queries that couldn't be handled locally can be sent directly to the cache most able to fulfill the request If the request cannot be satisfied locally, and the operator of the local system has chosen to subscribe to the Content Exchange, the request will be forwarded to the Content Exchange via the Internet, a private network, or other communications means. The network topic determiner 518 takes the request and examines the network content directory and determines where (if at all) the content is available and routes via established rules on Site of Origin, Query Topic, Specified Partners or RFQ to the main Network, and other Business Rules. The network topic determiner can use one or more of the following algorithms, or others, to determine which local site to send the query to: Standard information retrieval (IR) techniques such as Cosine Vector analysis, Poisson Distribution analysis, and "Term Frequency * Inverse Document Frequency" (TF*IDF) which would be run against the corpus associated with each site. These TF*IDF generated indices must be maintained for each participating site. The Content Exchange then broadcasts the query to all participating sites, which then return an indication of how likely their holdings are relevant to the query, or they can return the results if relevance is fairly high. In the former case, the CE routes the query back to the most relevant cache and then routes the answer back to the user. Or, the sites which determine that their content is very relevant to the query and return their answers to the CE, which then compares and ranks them. Add weighting to TF*IDF to reflect syntactic structure and other NL features (smart TF*IDF), which would be run against the corpus associated with the site. Same considerations as above. Perform a full parse on the query using NL parsing techniques to determine the exact meaning of the question and match the representation of that meaning against the content directory. Add interactive dialogue to the Dialogue Manager, so that the local Dialogue Manager mediates an interaction where the Content Exchange can ask for clarification. Build a taxonomy keyed to specific sites and compare terms in the query to the taxonomy. The request is forwarded to the selected site 520 which returns content to the local site 502. The Content Exchange logs the transaction detail for settlement. FIG. 6 describes an alternative embodiment 600 where each participating site is equipped with Information Retrieval (IR) Indexer 602. This embodiment is particularly useful for information retrieval on a text stream. The IR indexer at each site builds a word frequency table of the incoming text stream 604 and sends it to the Network Content Directory 516. In this model, the Network Content Directory is preferably a table with the significant words in the collected corpora as the rows and the sites as the columns (that is, the entire site appears as one column). A TF*IDF comparison is performed against the table and the original query is forwarded to the n most likely sites as above. FIG. 7 depicts another alternative embodiment 700 where each participating site is equipped with Information Retrieval (IR) Indexer 602. This embodiment is particularly useful for information retrieval on cache and structured data. The IR indexer at each site builds a word frequency table of the local Cache 702 and sends it to the Network Content Directory 516. Otherwise this is similar to the scenario depicted in FIG. 6 and described above. In any of the above embodiments, additional content can be pushed to the user. Such content can be selected based on user activity including the request. An example of such content is advertising. A cookie can also be generated. A cookie is information that a Web site puts on the user's hard disk so that it can remember something about the user at a later time. (More technically, it is information for future use that is stored by the server on the client side of a client/server communication.) Typically, a cookie records user preferences when using a particular site. Using the Web's Hypertext Transfer Protocol (HTTP), each request for a Web page is independent of all other requests. For this reason, the Web page server has no memory of what pages it has sent to a user previously or anything about your previous visits. A cookie is a mechanism that allows the server to store its own information about a user on the user's own computer. The cookie may be used to pass the recent history of a user to another site if the rule is to forward the user. This may be used to personalize content for that user. Cookies can be used to rotate the banner ads that a site sends so that it doesn't keep sending the same ad as it already has sent. They can also be used to customize pages for a particular user based on the browser type or other information the user may have provided the Web site. The content for fulfilling the request can be filtered based on a transaction history of the user. Preferably, the user's requests and/or content selections (including the responses selected) are monitored to generate the transaction history. Before providing more detail about each of the components of the Content Exchange system, an exemplary embodiment will be set forth to provide a context of the operations of the Content Exchange system. EXAMPLE 3 FIG. 8 depicts a content exchange system 800 according to an illustrative embodiment of the present invention. In this example, a Wine Wizard content exchange system is implemented as a community of four agents: 1. a User Interface (UI) agent 802, implemented as a Java.TM. Servlet that is run from a web browser; 2. a Dialog Manager (DM) agent 804, which interacts with the other agents and controls the dialog; 3. a Natural Language (NL) agent 806, which parses the user input; and p1 4. a Database (DB) agent 808, which provides domain information (mostly data about various wines) to the DM. The agent interactions are defined using the Open Agent Architecture.TM. (OAA.RTM.) middleware, a product of SRI International's Artificial Intelligence Center (AIC). A description of the OAA is found below. The DM receives a user's input from the UI and returns the system's response. Unlike many prior art dialog systems, the present invention allows for a mixed-initiative dialog, i.e., one where the user as well as the system can take the initiative in issuing directives or asking questions. The system supports multimodal input, i.e., the user can input non-linguistic or linguistic information via typing, speech, menu selection, etc. As another example, is gesture input, such as in the case of a person sitting in front of the computer with a camera mounted on the terminal that monitors the user. In such a case, the user knows that he could just shrug and communicate that he is lost. Suppose the user types or says "I am looking for a wine to buy for dinner tonight." When the "Submit" button on the UI is pushed, the UI agent sends the request for a response to the DM. The DM then asks the NL agent to parse the user input and return a logical form (LF). The NL agent identifies the language of the request, parses the request to generate a language independent LF, and returns the LF. Upon receiving the LF, the DM translates it into an interpretation, taking the state of the dialog into account. The interpretation phase is accomplished using a form of recursive-descent parser to analyze the LF. First, the "parser" recognizes whether the LF represents a statement, a wh-question, a yn-question, a fragment, etc.; then delves more deeply into a structure to find out exactly what is being stated or asked. For fragments and utterances with pronouns, the dialog state--i.e., the context of the utterance--is examined to "fill in the blanks." For example, "okay" is taken to be an answer to the most recent system-asked yes/no question. The ultimate result of the interpretation phase is a triple consisting of 1) positive constraints, 2) negative constraints, and 3) "other." This triple becomes the input to the response phase. First, however, the dialog frame--the part of the dialog state that represents the constraints--is updated with the information contained in the first two elements. The response phase checks several distinct possibilities to determine the proper response. The first possibility is that the user has asked a question, e.g., "What vineyard does that wine come from?" (This information will be in the "other" slot of the interpretation.) The proper response in this case is to answer the question. This case also covers certain explicit dialog moves, such as accepting a recommendation. The second possibility is that the user has rejected a recommendation ("What else do you have?"). In that case, the proper response is to offer an alternate suggestion. If neither of the above cases apply, the next step is to look for triggers in the interpretation. The new positive constraints are examined to see if they match a trigger rule. For example, if the user has indicated that he wants the wine for a dinner party, the system will immediately ask about the menu. If no triggers apply, the DM checks whether it has enough information to make a specific recommendation. In the illustrative system, the necessary and sufficient conditions are that a price range and a wine variety are known. If this is not the case, the system defaults to asking a slot-filling question (e.g., "What's the occasion?", "What are you having for dinner?", "What is a maximum/minimum price?", etc.). An NL Generation agent 810 can be utilized to generate such questions for presentment to the user. If the user responds "I am going to have chicken." to the question "What are you having for dinner?", the DM searches a local and/or third party knowledge base that maps kinds of foods to kinds of wines to ascertain a type of wine. If there are no more slot-filling questions to be asked, the system is out of options and must declare defeat or offer a general recommendation. However, this point can be reached only if the customer rejects multiple suggestions. Finally, the DM selects the recommendation from an information cache and/or third party database and composes a response to the user's input, which is then returned to the UI. Preferably, the DM utilizes the NL Generation agent to generate a NL text or speech response in the user's native tongue. As an option, after the response has been determined, the DM performs some necessary state maintenance tasks and then takes a snapshot of the dialog state. The snapshot is used by the system's "back up" feature, which permits a user to return to an earlier point in the dialog and continue from there. Finally, the DM collects all the requested state information and returns it to the UI along with the response information. Open Agent Architecture.TM. (OAA.RTM.) Open Agent Architecture is a software platform, developed by SRI International, that enables effective, dynamic collaboration among communities of distributed electronic agents. Very briefly, the functionality of each client agent is made available to the agent community through registration of the client agent's capabilities with a facilitator. A software "wrapper" essentially surrounds the underlying application program performing the services offered by each client. The common infrastructure for constructing agents is preferably supplied by an agent library. The agent library is preferably accessible in the runtime environment of several different programming languages. The agent library preferably minimizes the effort required to construct a new system and maximizes the ease with which legacy systems can be "wrapped" and made compatible with the agent-based architecture of the present invention. When invoked, a client agent makes a connection to a facilitator, which is known as its parent facilitator. Upon connection, an agent registers with its parent facilitator a specification of the capabilities and services it can provide, using a high-level, declarative Interagent Communication Language ("ICL") to express those capabilities. Tasks are presented to the facilitator in the form of ICL goal expressions. When a facilitator determines that the registered capabilities of one of its client agents will help satisfy a current goal or sub-goal thereof, the facilitator delegates that sub-goal to the client agent in the form of an ICL request. The client agent processes the request and returns answers or information to the facilitator. In processing a request, the client agent can use ICL to request services of other agents, or utilize other infrastructure services for collaborative work. The facilitator coordinates and integrates the results received from different client agents on various sub-goals, in order to satisfy the overall goal. OAA provides a useful software platform for building systems that integrate spoken natural language as well as other user input modalities. Indeed, an advantage of OAA-based embodiments of the present invention, that will be apparent to practitioners in light of the above teachings and in light of the teachings disclosed in the cited co-pending patent applications, is the relative ease and flexibility with which additional service agents can be plugged into the existing platform, immediately enabling the facilitator to respond dynamically to spoken natural language requests for the corresponding services. Dialog Manager 504 (See FIG. 5.) According to a preferred embodiment of the present invention, the DM is a universal piece of software or hardware that performs various tasks such as managing a query entered into the system by a user. Because of its universality, it can be embedded into many types of applications for a variety of purposes, including electronic commerce. As set forth above in Example 3, the DM interleaves several different types of knowledge: 1. Knowledge about a language being used, such as English, etc. The manager is able to recognize a language being used and configure itself appropriately to understand dialog, which often including dialects and slang words, in that language. Preferably, the manager is able to respond to the user in that language, either audibly or in natural language text. 2. Knowledge of the grammatical structure of the query dialog and the way people interact in dialog. This can also include knowledge about the way particular users speak and write. 3. Knowledge of the non-linguistic task and what agents/programs are involved in the task for which the query was made. 4. Knowledge of user interaction and presentation of information. The dialog manager knows how to present information to the user and knows what is on the screen that the user is interacting with. Multi-modal interfaces are supported, so that the user can see information on the screen and can point at it. 5. Knowledge about the user. Preferably, the DM is language and dialect independent so that queries in any dialect of a language can be analyzed and satisfied, so long as the proper NL module (agent) is implemented. To achieve this functionality, natural language parsers and generation tools particular to various languages/dialects can be plugged into the dialog manager. First the language is typed, i.e., whether it is English, German, French, or other language, and then the parser determines a meaning of the request, preferably in light of the local dialect and/or slang terms. Modules for each language ensure that the proper context of the dialog can be determined. The DM is preferably neutral as to domain and task and therefore works with any task, though it must have access to the domain from which it takes information for performing the task. Thus, for example, the same DM can handle all queries about wine, baseball, etc. The DM will determine what the task is and then determine the proper domain in which to seek information to complete the task. In one embodiment of the present invention, the DM can be tuned for specific types of content or tasks. For example, the DM set forth above in Example 3 can be tuned to handle orders for wine. To tune the DM, the sources of knowledge that the DM needs knowledge about are plugged in to the DM, preferably in the form of task modules. The DM can be tuned by integration with modularized software wrapped as a JAVA bean. The modularized software is preferably in the form of separate modules that represent knowledge based on forms. Each of the sources of programs has an agent wrapper and some protocol to obtain help on tuning the dialog manager for the particular information. An interaction communication language is utilized to allow the DM to query the correct agent (module) for information. The tuning of the DM can be based on content in the business sense. Cross-selling and up-selling can be performed. For example, consistently popular items can be given priority as a result. The DM can also be tuned for a particular person or type of person. The DM accesses a source of knowledge to retrieve a personality (or user) module containing user profile information to tailor itself. The system learns from task interaction with the user to log information in a relational database. An agent architecture can also be leveraged to identify characteristics of the user. The agents talk amongst themselves to gather information. Information can also be pulled from the billing system to determine characteristics of a user. When tuning for a particular user, the personality module associated with the user is selected. Several methods that the DM can use to determine which personality module belongs to the user, including an explicit login by the user, cookies, tracking, etc. The personality module will be used to tailor performance of tasks and results for the associated user. Thus, when two persons are doing/requesting a similar task, different results will be output. Further, the general traits of the user can be applied across domains. As an option, the same person can be dealt with at different levels based on the domain or content. For example, if the DM knows that the user is a software engineer, the level of detail when utilizing information from a technology site will be much more intense than when using information from a site about wine. When tuning for different types of persons, such as a high schooler v. a .sub.6 th grader, personality modules are again used, except that the modules will apply general rules applied to all users of that type. EXAMPLE 4 FIG. 9 illustrates a process 900 for retrieving content according to an embodiment of the present invention. In operation 902, the DM determines the identity of a user based on the login information of a user logging on to the system. The DM selects the user module corresponding to the identity of the user in operation 904, and selects English (the user's preferred language) as the default language. In operation 906, the DM interacts with an English language module so that all communications with the user will be in English. If the DM determines that the user is from Northern California, the Northern California dialect can also be set as a default. The module having knowledge of the user posts a message to the dialog manager saying that the user is very good at leveraging resources and is intelligent. The user requests information about automobiles, such as by selecting an "Autos" link. In operation 908, the DM receives a message from an application module that tells the DM that the user desires information about "automobiles." A search is made of a table of URL's v. content types in the content directory in operation 910. To determine knowledge of the domain(s) and task(s), the DM determines information based on the URL in operation 912. In this example, assume the domain is a site for car buying. The DM asks the domain and task modules for information about "automobiles" and a type of task (buy, sell, price). If the DM doesn't have access to the information, it notifies the user of such in operation 914. The particular instantiation of the DM will have information based on the specific application(s) or task(s). Whether different tasks are to be performed or if it a single family of tasks can be inferred from the characteristics of the site. In operation 916, the DM selects information based on the user information. Inside the DM is a model of the context. The DM should determine what is in focus, what is salient, etc. For example, while reviewing a site, the DM spots a flashing picture on the network data site. The DM recognizes the event (flashing picture) and takes action based thereon. The DM determines whether this is an event it should recognize, and if so, whether it should be sent to the user. The DM then tweaks the dialog with the user based on the event. Representation of the content are generated and are independent of its language. The DM sends the string to a natural language parser to understand the language information. The parser sends back a representation of what was said. Then the DM determines what the user wants to see. If the user inputs an indicative sentence that states facts, such as "I want to see a Ferrari." The response is to show an image of the Ferrari. Which model to display can be determined based on various things, such as how much each model costs. The DM synchronizes information for presentment to the user in operation 918. Clarification subdialogs can be submitted to the user to limit results if there are over a predetermined amount of answers. In operation 920, the information is output. If the user is American, then the price is presented in dollars. If the user is French, then the price is in francs. By following a user path through the dialog, then the DM can dynamically infer information about the user and create a dialog that is well tuned to the user. The DM can respond to the user with pictures, animation, advertisements, etc. to help sell the user a particular automobile. Possible responses that the DM can submit to the user include: "Sorry I do not know, but . . . " "I know the answer, which is . . . " Output whatever the application allows. Inside the DM is a model of the context. The DM should determine what is in focus, what is salient, etc. For example, while reviewing a site, the DM spots a flashing picture on the network data site. The DM recognizes the event (flashing picture) and takes action based thereon. The DM determines whether this is an event it should recognize, and if so, whether it should be sent to the user. The DM then tweaks the dialog with the user based on the event. Representation of the content are generated and are independent of its language. The DM sends the string to a natural language parser to understand the language information. The parser sends back a representation of what was said. Then the DM determines what the user wants to see. If the user inputs an indicative sentence that states facts, such as "I want to see a Ferrari." The response is to show an image of the Ferrari. Preferably, the state of the dialog manager is tracked by an ongoing data structure. Local Topic Determiner 506 (See FIGS. 5-7.) FIG. 10 is a flow diagram setting forth a general procedure 1000 that can be utilized to perform a query using the local topic determiner. In operation 1002, the query is parsed with local grammars. The parsed query is presented to the local Information Cache in operation 1004. At decision 1006, it is determined whether the local answer is "high confidence." If the local answer is "high confidence" (e.g. enough slots in the recognition template are filled) then the result(s) are presented to the user in operation 1008 and the process ends. Otherwise, continue on to operation 1010. In operation 1010, the local business rules are checked to determine what action to take. At decision 1012, a determination is made as to whether the local business rules allow a network query. If so, in operation 1014 the English language query and parsed query are sent to the DDN(s) (note that there may be more than one DDN available to the site). If the local business rules do not allow a network query, a message indicating that no information is available is presented in operation 1016. If the DDN responds with a result, the result are presented to the user in operation 1018 and the appropriate logs are updated in operation 1020. If the DDN doesn't respond with a result, a message is presented in operation 1022 indicating that no information is available. It should be noted that the query can be in any language. The table below sets forth the parameters of the content request message sent to the DDN (to be formatted as an XML DTD):
TABLE 7
Requesting Site
English Query
Parsed Query
Time stamp
Rule used
cookie
Local Rules The local rules are executed in order of priority. Upon executing the first rule that is true, the rules are exited. Example 5 sets forth sample code. EXAMPLE 5 CASE CASE=RULE 1 Always send queries to Site XXX CASE=RULE 2 Send Queries to site A OR IF no result THEN site B OR IF no result THEN Site C CASE=RULE 3 IF no result returned THEN offer to anyone who wants to respond ranked by lowest price CASE=RULE 4 IF no result returned THEN offer to anyone who responds ranked by highest confidence CASE=RULE 5 IF no result returned THEN offer to anyone who wants to respond ranked by highest confidence with a maximum price of $X.XX CASE=RULE 6 Send user to site willing to pay more than $x.xx ENDCASE Network Topic Determiner 518 Several different methods are defined for determining which site has the content desired. Other methods may also be used. See the discussion above with reference to FIGS. 5-7 for more details. FIG. 11 is a flow diagram of a general procedure 1100 for finding a site with content utilizing the Network Topic Determiner (NTD). In operation 1102, the NTD receives the Content Request Message and, in operation 1104, determines the n most likely sites to have the relevant information (excluding any systems that only communicate with named systems of whom the requesting site is not one). In operation 1106, the NTD forwards the query from the Content Request Message to the n most likely sites. The best answers along with a confidence rating are received from the sites in operation 1108. In operation 1110, the NTD looks at the content, confidence and business rules in the Content Request Message and in the network content rules and, in operation 1112, sends a pointer to the content back to the requesting site. The appropriate logs are updated in operation 1114. A service fee is charged to the user who made the query in operation 1116. The table below sets forth the parameters of the content offer message sent to the DDN (to be formatted as an XML DTD):
TABLE 8
Offering Site
English Response
Time stamp
Rule used
Confidence
Content class
Content price (if dynamic)
Network Rules The network rules are executed in order of priority. Upon executing the first rule that is true, the rules are exited. See the following table.
TABLE 9
Content Provider Pointer to Rule 1 Code
Example 6 sets forth sample code. EXAMPLE 6 CASE CASE=RULE 1 Always provide content to Site XXX at negotiated rate CASE=RULE 2 Always sell content of class "A" (where there may be multiple classes of content) for $x.xx if not a known site CASE=RULE 3 Will pay $x.xx for you to send me your user ENDCASE Content Directory FIG. 12 depicts a process 1200 for creating a content directory. Information about content of one ore more network data sites is received in operation 1202. In operation 1204, the information about the content is analyzed. An index of representations of the content is generated in operation 1206 based on the analysis. Note that the representations can be organized into groups and subgroups, and the same representations can be placed in more than one group. Preferably, the data in the index is organized hierarchically. In operation 1208, a query engine is allowed to utilize the index to select a network data site in which to search for information pertinent to a query. In one embodiment of the present invention, a term frequency analysis is performed on the content of each of the network data sites and the term frequencies (i.e., word counts) are placed in the index. See Example 7 below. A weighted measure of relevance between a query and a site is generated. If a term is used only on one site, it is given heavier weight. The relevance of the query can be determined based on the frequency of terms in each of the items of content, as determined by the term frequency analysis. Preferably, each site is taken independently and a judgment is made as to how much a site knows about a particular topic based on how often various terms appear. EXAMPLE 7 In this example, four sites are analyzed. The content of the four is downloaded in its entirety. For greater performance, only text can be downloaded. In this example,--ESPN, CNN, Entertainment Tonight and The Weather Channel--content overlaps when it is taken out of context. For example, the word "strike" will have a different meaning on the ESPN site (baseball) than on the CNN site (labor strike). In another embodiment of the present invention, all of the network data sites' directories (indexes) are received from the network data site(s) and merged into a single weighted index. The text itself can be analyzed to determine its general context, thereby creating a concept index rather than a word count index. In yet another embodiment of the present invention, the index is normalized based on the query. Here, the proper nouns and verbs are analyzed to determine a context of the question at a predetermined (or acceptable) level. It should be noted that more complex analysis of the question can be performed. For example, prepositional phrases, adverbial terms/phrases, etc. can be identified and analyzed. The determined context is then used to normalize the site index(es). Information on the sites is parsed to determine which nouns and normalized verbs are resident there in order to determine the best manner in which to approach the query. To normalize an input string such as sentence, for example the string is first morphologically analyzed, using the predefined record in the lexicon for each of its constituent words, to generate a so-called "stem" (or "base") form therefor. Stem forms are used in order to normalize differing word forms, e.g., verb tense and singular-plural noun variations, to a common morphological form for use by a parser. Once the stem forms are produced, the input string is syntactically analyzed by the parser, using the grammatical rules and attributes in the records of the constituent words, to yield the syntactic parse tree therefor. This tree depicts the structure of the input string, specifically each word or phrase, e.g. noun phrase, in the input string, a category of its corresponding grammatical function, and link(s) to each syntactically related word or phrase therein. In another embodiment of the present invention, the analysis of the information about the content includes performing a linguistic analysis on the content of the at least one network data site for generating the index. Alternatively, the analysis of the information can include performing a statistical analysis of co-occurrence data, i.e., the matching of word and/or phrase patterns to a model word and/or phrase, to determine where to index a particular content item. Preferably, locations of the content are determined and pointers to the content are generated and stored in the index. As an option, the index can be dynamically updated based on a trend of usage such as, for example, content items selected repeatedly by users for a particular query topic. The network data site can be an information cache which contains content previously retrieved from other network data sites. Further, a fee can be charged for utilizing the index. During a query, a ranking analysis is performed to determine which site has the most relevant documents. Next, a relevancy analysis is performed on the selected documents. Relevance measures can include such things as whether the content is from a trusted source, authorship, a seal of approval, business rules, and link popularity. The query is also parsed to some level to determine its topic. The site with the most relevant documents is selected and the query and documents are matched. See also Example 8, below. Also note that the various embodiments of the present invention are not to be limited by the examples pertaining to retrieving documents, but rather can be utilized to find and retrieve any type of information. FIG. 13 depicts a data structure 1300 of an index according to an embodiment of the present invention. As shown, content items 1302 are organized in groups under main topics or headings 1304. Some analysis of the content may have to be performed to determine what can be distributed to the content directory at the meta level. The main topics can be likened to desks of a news organization with, for example, a desk for sports, another desk for business news, and a desk for weather. Under each main topic are subtopics 1306 each having an associated subdirectory of content and further subdirectories. For example, under the "sports desk," sports would be divided into Football, Basketball, Soccer, Swimming, etc.. Alternatively, an existing structure can be scraped to obtain a directory of categories. As an option, the index can be organized in accordance with the Open Directory Project (ODP) standard for directories. When performing a query, some high level of the data structure is chosen and enough analysis to get into that level is performed. The dashed line 1308 of FIG. 13 shows an illustrative threshold level for entering the data structure of the content directory. Then the analysis is pushed down into the branches of the structure. EXAMPLE 8 Continuing with the desk example, an illustrative query asks "Who did AOL acquire?" "AOL" is recognized as a proper name, but is it a person, place, thing, organization? "Acquire" is recognized as a verb, but it is not yet determined if it is AOL acquiring something or being acquired. Just enough analysis to get to the proper desk, i.e., the desk that most likely holds the answer, should be performed on the index entries. Upon performing the partial analysis, it is determined that the query most likely corresponds to the business desk. Since AOL could also be a name of a sports team, the query is also routed to the sports desk with a low priority and the business desk with a high priority. Restrictions can also be used to select the proper desk. For example, if it is suspected that "acquire" is a word associated with companies, that word can be used to limit the query. For example, the query could be set to block out names of people, because companies do not acquire people. On the query side, the search can be treated as a bag of words. The sequence of words and the linguistic relationship in the query is not taken into account. Rather the query is read "AOL acquired." The general desk is determined based on this simplified query, though it is not know that it is AOL doing the acquiring vs. who acquired AOL. Retrieving Event Information from Basic Syntactic Information In one embodiment of the present invention, the following are indexed: events as described by linguists. An event has a type and event participants. Participants can be agents, objects, time, and location (probably some other thematic types as well). company names people names other items When a query is performed, a resulting event template is generated or retrieved and it is used to match against information held in the information cache (content directory). In addition to capturing information through a focused combiner-grammar method, the present invention can also take advantage of the syntactic information that would otherwise be set aside by doing the following: 1. index all information that "could" lead to identification of an event and its participants: a. all nominalized events i. all possible major participants in nominalized events, such as: (a). those coming from pre-nominal positions (b). those coming from predominantly noun-modifying prepositional phrases (e.g., those headed by "of") (c). those from other prepositional phrases that statistically align with certain nominalized events (this bit requires some investigation because we might not be able to limit nominals and prepositional phrases in a useful way. b. all main sentence head verbs i. all possible major participants such as: (a). all syntactic argument positions for verbs (b). those event participants from prepositional phrases that statistically align with certain verbs. c. all the information that is sometimes collected from relative clauses (the linguists can help describe this one). 2. assign a unique label/D to each syntactic contributor type above 3. for every verb and noun that contributes to an event what is needed to be known is: a. the syntactic structures in which they are found. Each word-syntactic-structure combination (e.g., agree+sentence-verb-head) is indexed. b. each syntactic structure in which the noun or verb is found has accompanying "offset" information. For each word-syntactic-structure, the sentence in which it is found is recorded as well as its sentence position (e.g. first, second, etc. position in the sentence) in which the word occurs. c. the documents in which the syntactic structures occur. To help with retrieval, the present invention can supplement the information above by doing the following: 1. organize the current collection of "combinators" and establish how to universally organize other combinators that may be used in the future. For instance a combinator that uses a pre-nominal modifier and nominalized event would be given its own ID (putting aside for the moment the particular verb that may have been used in one of the current combinator rules). 2. better recall performance can be achieved by grouping verbs and their respective nominalized forms (e.g., the verb "agree" with its nominalized form "agreement"). 3. better recall performance is also achieved by identifying other event combinators that may point to the same event type. 4. the more known verb-specific information, the better. For instance, knowing that a verb like "agree" often has one of its arguments located in an accompanying prepositional phrase headed by "with" is very valuable information. 5. better recall performance can be achieved by grouping verbs by semantic types. 6. better recall performance can be achieved by grouping nouns by semantic types. During retrieval, the following can be performed: 1. parse the query 2. first, use the information that is currently captured in combinators and domain-specific rules. If through the parse, a match is found through default methods, then use that information and retrieve information by the default method. 3. if a match is not found through the default methods, the following occurs: a. use information from the parse of a query which will include: i. the syntactic element types that potentially identify head verbs and event participants. These elements are labeled by an ID as mentioned above. The general phrase "syntactic element types" is used here because the combinators may use a combination of syntactic constituents and sub-constituents. ii. various combinator rules that could be used to combine head verbs and event participants. iii. the particular verbs and nouns that appear in the query b. each query has the potential for multiple interpretations because multiple combinator rules might be applicable to the available syntactic elements in a query. For each interpretation, the respective contributing syntactic elements are recorded, including the words in the syntactic elements. c. for each interpretation, the available information is taken and used to submit a two-part query. i. the first part has the word information (from the potentially contributing verbs and nouns) and the syntactic structures in which they appear (e.g., a noun-noun combination). (a). from the word and respective syntactic structures, an identification is made of those sentences (or perhaps paragraphs) which have occurrences of the words from the query and their respective syntactic information. (b). results in the first can be ranked by: (i). giving more value to those sentences which have the more occurrences of the relevant words and respective syntactic structures from the query. (ii). giving more value to those sentences in which the words and respective syntactic structures are more adjacent to one another. ii. try to apply the combinator(s) used in the query to the results returned from the first part of the query. (a). rank results by way of the "best" fit. "Best" fit will be determined by: (i). the number of event elements filled. (ii). closeness to the rules derived as important for the interpretation of an event found in the user's query. d. the queries above can be expanded by using any available information regarding: i. other syntactic combinations in which the event may be found, such as: (a). sister nominalized or verb-headed event forms. (b). other words that have similar meanings to those found in the query. (c). other event combinators that are known to possibly identify events similar to that in a query. ii. there is the potential to give results that match "expansions" to a query less value than those found through the direct matching methods described above. e. for each "interpretation" of the query, the interpretation can be paraphrased and given back to the user. The user can select the preferred interpretation. Then the respective results can be returned. Dynamically Updating the Cache with Event Information The approach above can also be used for improved "dynamic" updating of the information cache. In a simple embodiment of the present invention, when new event combinators are created, documents are re-parsed and then re-indexed. To improve updating of the cache, the basic syntactic information is retained. This allows the preset invention to go into the information cache, target the syntactic structures and words of interest--namely those that fit with new event combinators, create new event structures from the "old" syntactic information, and index the new event information. Also when perfect matches are not found for those events found in user queries, as described above, there is the potential for the present invention to return multiple interpretations from which the user picks one. The present invention can also use the alignment of the query and the user-feedback regarding the correct interpretation of the query to update the information cache. An event type can be assigned to that information that corresponds with the interpretation selected by the user. Business Processes According to an embodiment of the present invention, a fee may be charged for access to content, presentation of content, etc. As such, a call detail record is maintained. The call detail record stores information about the requesting site, all sites that information was obtained or searched from, etc. Information on licensing relationships between sites on the web is applied to the information in the call detail record to determine the fee for accessing the content. Many different types of pricing schemes may be used, such as, for example, pricing a document based on its relevancy to the query. If multiple content items are found at a site and/or at various sites, such multi-document, multi-source information can be charged for individually. In an additional method to generate revenue, the viewer can be driven to one or more sites so that a fee can be collected for information retrieved from each of these sites. The content can be delivered to the viewer or the viewer can be directed to the content. Output results When performing the search, multiple answers are likely to be found. The results may be weighted and presented to the users ordered by weight. Illustrative weighting processes have been set forth above. The relevance of a particular content item can be set forth in terms of a percentage. Another output structure is tabular output of data items or categories. Graphical presentation of outputs can also be created, such as a Java 3D presentation using color coding to illustrate the weights of the various results. Summaries of the results can be presented, each with a pointer to the full content item. Such summaries may include a cite or link to the content, a brief summary of the content, a full summary of the content, etc. When generating summaries, structured records can be are pulled up from the content directory or actual site, rather than the text. For example, structured data from the cache can be used to produce human readable text from the information. Thus, a natural language summary can be created from the cache. It should be noted that if the structures are identical, there may not be a need to report the redundant text. While various embodiments have been described above, it should be understood that they have been presented by way of example only, and not limitation. Thus, the breadth and scope of a preferred embodiment should not be limited by any of the above-described exemplary embodiments, but should be defined only in accordance with the following claims and their equivalents.
|
Same subclass Same class Consider this |
||||||||||