WO2006032735A1

WO2006032735A1 - System and automatic method for searching data in a knowledge base

Info

Publication number: WO2006032735A1
Application number: PCT/FR2004/002386
Authority: WO
Inventors: Carole Manquillet; Jean-Pierre Le Pape; Philippe Bretier
Original assignee: France Telecom
Priority date: 2004-09-22
Filing date: 2004-09-22
Publication date: 2006-03-30

Abstract

The invention concerns an automatic system (1) for searching data in a knowledge base by dialogue between a user and the system comprising interface means (2) connected to means (3) for analyzing sentences to detect the focus and its properties, connected to means (4) for storing the history of the dialogue between the user and the system, and means (5) for storing at least one ontological view of the knowledge base (6), connected to means (7) for selecting an ontological view from the focus, connected to means (8) for projecting the dialogue on the selected ontological view to provide a list of possible suggestions, connected to means (9) for selecting and editing the suggestions for sorting the list of suggestions into at least two categories, the first category being the suggestions whereof the choices are exhaustively declinable and the second category being suggestions corresponding to unknown elements.

Description

System and automatic method of searching information in a knowledge base.

The present invention relates to an automatic system and method, as well as the associated software product, for searching information in a knowledge base by dialogue between a user and the system.

Typically, a knowledge base is a structured set of data in which the data is grouped into classes and subclasses, which are linked together by semantic relations. For example, in a knowledge base, a "human being" class is defined as well as a "date" class. Between these two classes, it is possible to define a "birth date" relationship such that an entity, or instance, of the "human being" class is linked to a date, corresponding to the date of birth of that entity. The grouping by classes and subclasses is such that, for example, if "stock object" is a class then the possible subclasses are "stock", "index" and "currency", the US dollar and the euro being then instances of the subclass "currency".

Among the various techniques for searching information in knowledge bases and, more generally, in a set of data, by a user, in an interactive environment, two modes are privileged:

The first search mode uses keywords. It has been popularized by Internet search engines like Google (trademark of Google, Inc.). It is based on the indexing of knowledge objects (for example web documents) based on keywords mentioned. In general, the documents found are ordered according to their relevance to the keywords mentioned or to a Boolean combination of them.

The second mode of research is directed research.

For directed research, pre-established concatenations are defined for a given scope of applications such as assistants rolling steps. These sequences are based on predefined data qualifying the objects of knowledge. These data are either more or less rigid classifications such as a hierarchy of topics and sub-sections of search or menus and sub-menus, or specific attributes possibly accompanied by their possible values (forms / forms search).

The search for the user is guided by the system that unfolds one of the pre-established sequences and offers him to choose among the proposed attribute values to reach an object or a subset of objects.

These two search modes have the disadvantage of offering only a very limited guide to help the user. In the case of keywords, the relevance of the documents found is based on a representation of the search space limited to an unstructured list of keywords. In the case of a directed research, the questioning of the user and its progression are limited by the structure and the pre-established organization.

The object of the invention is therefore to overcome this disadvantage. The object of the invention is an automatic system for searching information in a knowledge base by dialogue between a user and the system comprising

man-machine interface means capable of enabling the exchange of information between the user and the system in the form of a dialogue, connected to

means for analyzing the sentences entered by the user able to detect in said sentences the focus and its properties connected to

storage means able to preserve the history of the dialogue between the user and the system, characterized in that it also comprises

means for storing at least one ontological view of the knowledge base, connected to

means for selecting at least one ontological view stored from at least one focus entered by the user and stored in the storage means of the dialogue, connected to

means for projecting the dialogue on the selected ontological view capable of providing a list of possible suggestions, connected to

means for selecting and formatting the suggestions objects able to sort the list of suggestions into at least two categories, the first category being the suggestions whose choices are exhaustively declinable and the second category being the suggestions corresponding to of the elements not known, and to provide the man-machine interface means with a sorted list of questions to be presented to the user.

Another object of the invention is an automatic process for searching information in a knowledge base by dialogue between a user and a system comprising the steps of

- acquisition of information from the user,

- analysis of this information to extract the focus and its properties,

selecting an ontological view from at least one focus from the user, this selection being made on a set of previously defined ontological views,

- projection of the dialogue information on the selected ontological view to obtain a list of all possible suggestions,

selecting the suggestions to be presented by sorting the list of suggestions into at least two categories, the first category being the suggestions whose choices are exhaustively declinable and the second category being the suggestions corresponding to unknown elements,

- formatting suggestions, and

- presentation of suggestions to the user. Another object is a software product recorded on a storage medium for implementation by a computer acting as a dedicated equipment of the system and the automatic process of searching for information.

According to other characteristics of the system: the ontological views are stored in the form of a logical tree structure such that, seen from a node corresponding to a class, the link between the corresponding class and its subclasses corresponds to links Exclusive OR and the relations between this node and other classes of the knowledge base correspond to AND links, the root of the tree being the focus object of the ontological view;

the means for projecting the dialogue on the ontological view comprise first means for traversing the tree representing the ontological view of the focus object towards the semantic guidance objects and second means for traversing the tree from the objects. guiding identify and lower all AND links from the current node and down the exclusive OR links corresponding to elements listed in the dialog;

if the second means of traversing the tree encounter exclusive OR links none of which results from the request, then a suggestion of choice on these links is proposed, and if no exclusive OR link is encountered in a branch of the tree, then a suggestion of choice is proposed on the instances of the current class;

the means for storing the history of the dialogue comprise structured storage means capable of memorizing in the form of a graph all the semantic concepts referenced in the current state of the search dialog;

the means of formatting the suggestions are able to sort the suggestions into a first category of closed questions and into a second category of open questions. According to other characteristics of the process

an ontological view being structured in the form of a logical tree whose root is the focus object, the links between the classes and their subclasses of the OR knowledge base and the relationships of the knowledge base of the AND links, the projection of the dialog information on the ontological view includes the steps of:

- search from the root of the guidance object,

recursively traversing the tree from the guidance object so as to identify and descend all the AND links from the current node and identify and descend the only exclusive OR links corresponding to elements of the dialogue;

- when browsing the tree, the meeting of a class with exclusive OR links to its subclasses, none of which corresponds to an element of the dialogue, generates the creation of a suggestion of choice on these links and the meeting of 'no exclusive OR link on a branch of the tree generates the creation of a suggestion of choice on the instances of the current class;

after analyzing the information from the user, the semantic concepts thereof are stored in a structured dialogue history in the form of a graph representing the current state of the search dialog; - The formatting of suggestions includes the step of sorting the suggestions into a first category of closed questions and a second category of open questions.

The invention will be better understood on reading the description which follows, given solely by way of example, and with reference to the appended drawings, in which:

FIG. 1 is the diagram of an automatic system according to the invention;

FIG. 2 is the representative graph of an exemplary knowledge base; FIG. 3 is the representative graph of an ontological view extracted from the knowledge base of FIG. 2;

FIG. 4 is a flowchart for projecting the dialogue on an ontological view;

FIG. 5 is a process flow chart according to the invention. An automatic system 1 for searching information of a knowledge base by dialogue between a user and the system comprises, in FIG. 1, classically means 2 of human-machine interface allowing the user to ask his question as well as to clarify it as the dialogue progresses and, on the other hand, allow the system to present the answers found and, if necessary, to ask questions to clarify the purpose of research.

Conventionally, this human-machine interface comprises an input keyboard and a display screen. It can also be voice-based with a voice recognition module capable of interpreting user-spoken sentences and a speech synthesis module capable of phonetically generating the system feedback sentences.

Whatever the input mode of the information coming from the user, these interface means 2 are connected to means 3 for analyzing the sentence making it possible to detect the focus of the latter, as well as the properties of that -this.

The focus is the intention of the speaker. It is determined by the syntactic and semantic analysis of the sentence.

An example of the focus search is described in the application FR 2 787 902 of the applicant. The focus concretely translates into a word. It differs from a keyword in that the focus may not appear as such in the sentence. For example, in the middle of a dialogue, the question "what is the age of this person? Has as a focus "Mr Dupont" who is the person referenced by the "this" and therefore known by a previous sentence of this dialogue. The properties of the focus correspond to the precisions provided by the user. In the above example, the focus property is the age of the focus.

As explained below, the automatic information retrieval system constructs a dialogue with the user in order to specify his request and thus best meet his expectations.

It therefore comprises means 4 for storing the different sentences, and more particularly the different focuses and their properties, used by the user during this dialogue, the storage of this history allowing, among other things, to avoid asking the user a question for which he has already provided an answer.

Preferably, the storage of this history is done in the form of a graph of which each node is a property. The graph is called the state of the dialogue or semantic sharing graph.

The system also includes means 5 for storing at least one ontological view of the knowledge base 6.

An ontological view is a partial view of the ontology of the domain of knowledge. Classically, in the field of knowledge bases, ontology is the representation of the sum of knowledge and the definition of all categories by a single set of logical relationships.

In the present case, an ontological view is a partial representation of a knowledge base from a certain point of view. It is therefore an extraction of classes and relationships from the knowledge base from a theme, or a focus or focus object. The classes and relationships of the knowledge base are then reorganized as a tree structure whose focus object is the root.

Thus, in a knowledge base, figure 2, gathering information on finance and geography, it is possible to define an ontological view, figure 3, in relation to the topic "course" by extracting and organizing knowledge base information on this issue.

It is easy to imagine that a unique knowledge base can thus give rise to a plurality of different ontological views. An ontological view is therefore defined in relation to its focus, that is to say the theme on which the extraction and organization of this one is based. In the previous example, "course" is the focus of the created ontological view.

The ontological view can be represented, figure 3, in the form of a tree whose focus is the starting point, the root. The links between classes and their subclasses and relationships correspond to tree links with particular properties and are noted differently in a graphical representation of the tree. For example, the subclass link is noted as an arrow pointing to the main class while the relationship link is non-directional. Another representation of an ontological view uses a description language.

By way of example, FIG. 3 can be described by: km_model_vers (1.0, 'stock market application'). km_focus (course).

km_view_model (course,

[price_object (price, sales_object), OR (sales_base, [share, index, currency])

]) ^• km_view_model (index,

[index_bourse (index, city), index_country (index, country), pad_in (city, country)

]) • km_object__restrict (stock object, 1). km_priorite_restrict (index, [index, city, country]) km_rest_forbidden ([broker_object, instances]). km_profondeur_rest (1). km_nb_restrict (2).

The declaration km_view_model (node, expression) defines the links in "expression" of the node "node" with the other nodes or leaves.

For example, the node "index" has logical relationships with "city" and "country" knowing that "city" has a logical relation of type "paddock-in" with "country".

In the tree structure of the ontological view, the logical links are thus branches of the tree connecting two nodes. These links are of two types: the first type is defined by the link between the classes and their subclasses and the second type is defined by the logical relations between the instances of these classes.

Each ontological view also includes a certain number of parameters allowing an optimal use thereof by the tools described hereinafter.

Thus, in the example above, the scanning depth of the graph is restricted to a single level. Similarly, for "index", the scan is limited to the nodes "index", "city" and "country". Selection means 7, FIG. 1, look for the relevant ontological view (s) according to the request of the user.

The selection is made by searching ontological views whose focus corresponds to the focus entered.

Then, for each selected ontological view, the system comprises means 8 for projection of the dialogue on this ontological view.

The projection of the dialogue on the ontological view is understood to mean the operation of scanning and traversing the ontological view from the focus node, for the purpose of unification, which, in FIG. 4, in a first step in search of the object semantic guidance, that is to say the objective deduced by the process of the intention of the user, so the focus. As a rule, the focus and the semantic guidance object are therefore merged. Then, in a second step, steps 11 to 15, and from the semantic guidance node, the projection traverses the node tree in a node, recursively. For each node encountered, the projection identifies and descends all relationship links, considered as AND links, possible from the current node. At the same time, if links of subclasses are possible, the projection checks that one of them follows from the elements of the request. Subclass links are therefore considered exclusive OR links. This projection of the dialog on the ontological view makes it possible to define a list of objects of suggestion, or suggestions according to the following algorithm. For each class, thus corresponding to a node, at 11, from the guidance object, if subclasses are defined in the ontological view at 12 and none of them results from the request at 13, then a suggestion of choice on the subclasses, and / or on the instances is defined in 14. But if, subclasses being defined in the ontological view at 12, at least one of these results from the dialogue at 13, then go down the corresponding link and start the search again starting from this subclass, in 11. Finally, if no subclass is defined in 12, then a choice suggestion is defined on the instances of the current class, in 15 .

The means 8 of projection of the dialogue on the ontological view thus generate a list of objects of suggestion.

It should be noted that the settings of the ontological view are used by the projection means to refine and limit the path in the nodes of the ontological view. This is the parameter that limits the search depth in the graph or the semantic guidance object.

The list of suggestion objects provided by the projection means includes all possible suggestions.

This list is then transmitted to means 9 for selection, FIG. 1, and formatting of the suggestion messages.

This list of suggestions includes, in the form of a data structure, for each suggestion, the object to which the suggestion relates, the list of possible responses for the user, as well as the extension of the dialogue to be performed, c ' that is, the new semantic element to share with the user, if this message is to be really proposed.

This list must be sorted so as to respect the priorities attached to the ontological view, if such a parameterization exists, and also so as to be as relevant as possible with respect to the present state of the dialogue.

The list is divided into three sub-lists: - a first sub-list contains suggestions where choices can be declined in an exhaustive way. This corresponds to closed questions, that is, questions containing the answer in the form of a list of choices such as "Are you interested in A, B or C? ". Suggestions in this sub-list therefore have possible responses stored in memory corresponding to subclasses or instances of the class.

- a second sub-list contains, among the remaining suggestions, those which, if retained, correspond to sheets of semantic sharing graph. This corresponds to open questions, that is, questions whose answer is not a choice in a list, dealing with elements of which nothing is known in the current context of the dialogue.

- the third sub-list corresponds to the suggestions not classified in the previous sub-lists.

The first sub-list is used in priority to define the possible questions, then the second sub-list and finally the third sub-list so as to keep only a predefined maximum number of simultaneous suggestion messages which are then presented to the user by the man / machine interface

2.

The operation of the system will now be explained using a dialogue example.

This example uses the knowledge base of FIG. 2 and the ontological view associated with it represented in FIG. 3. This ontological view has as its focus object "COURSES" and as an ontological guidance object "STOCK OBJECT". The other parameters of the ontological view are the scanning depth set at 1 level and the prohibition to make suggestions on instances of "OBJECT STOCK".

«User: I'm looking for a quote»

The focus is "quotation" which refers to "course" which is the focus object of the ontological view. The object of ontological guidance being "object_boursier", the course of the tree makes appear three subclasses: "index", "action" and "currency". Since the scan depth is set to 1, the path stops at this level. «Answer: The value of a stock market information. What stock market information are you interested in? An index, an action or a currency? "

"User: a clue. "Answer: the value of the index. Which index are you interested in?

Which city are you interested in? "

Index being fixed, it corresponds to a descent of a level in the ontological view. We get a complete list of suggestions in the form of 3 open questions on "index", "city" and "country". The parameters of the dialogue defining the maximum number of questions to 2 (km_nb_restrict (2)), the process retains the first two suggestions: the set of instances of "index" corresponding to a first open question and all instances of "City" for a second open question. «User: Paris»

"Answer: the value of the Paris index. Which index of Paris are you interested in? The SBF250 index, the SBF120 index or the CAC 40 index? "

The system thus proposes all instances of "index" corresponding to the city "Paris".

"User: the first"

"Answer: The SBF250 index was worth 2128 euros 94 at 11:40. Do you want other information? "

In this last exchange, it is no longer necessary to specify the question. As a result, the analysis and the search as described above are not carried out and a simple search for the requested information takes place in a conventional manner.

Thus, FIG. 4, the automatic process for searching information in a knowledge base by dialogue between a user and the system comprises the steps of

- acquisition of information from the user, in 20.

- analysis of this information to extract the focus and its properties, in 21. selecting an ontological view from at least one focus coming from the user, this selection being made on a set of previously defined ontological views, in 22.

- projection of the information of the dialogue on the selected ontological view to obtain a list of all possible suggestions, in 23;

- selection of the suggestions, in 24, to present by sorting the list of suggestions in at least two categories, the first category being the suggestions whose choices are exhaustively declinable and the second category being the suggestions corresponding to unknown elements . - formatting suggestions, in 25, and

- presentation of suggestions to the user, in 26.

It can thus be seen that by using the semantics of the domain considered by the use of ontological views, it is possible to offer the user particularly useful suggestions to help him in his search for information.

Claims

1. Automatic system (1) for searching information in a knowledge base by dialogue between a user and the system comprising

man-machine interface means (2) able to allow the exchange of information between the user and the system in the form of a dialogue, connected to

means (3) for analyzing the sentences entered by the user able to detect the focus and its properties of said sentences, connected to

- Storage means (4) able to maintain the history of the dialogue between the user and the system, characterized in that it also comprises

means (5) for storing at least one ontological view of the knowledge base (6), connected to

means (7) for selecting at least one ontological view stored from at least one focus entered by the user and stored in the storage means of the dialogue, connected to

means (8) for projecting the dialogue onto the selected ontological view capable of providing a list of possible suggestions connected to

means (9) for selecting and formatting suggestions objects able to sort the list of suggestions into at least two categories, the first category being the suggestions whose choices are exhaustively declinable and the second category being the suggestions corresponding to unknown elements, and to provide the human-machine interface means with a sorted list of questions to be presented to the user.

2. Automatic system for searching information in a knowledge base by dialogue between a user and the system according to claim 1, characterized in that the ontological views are stored in the form of a logical tree structure such that, seen from a node corresponding to a class, the link between the corresponding class and its subclasses corresponds to exclusive OR links and the relations between this node and other classes of the knowledge base correspond to AND links, the root of the tree being the focus object of the ontological view.

3. Automatic system for searching information in a knowledge base by dialogue between a user and the system according to the claim 2, characterized in that the means (8) for projecting the dialogue on the ontological view comprise first means for traversing the tree representing the ontological view of the focus object towards the semantic guidance objects and second means for traversing the tree from the guide objects able to identify and descend all the AND links from the current node and down the exclusive OR links corresponding to elements mentioned in the dialogue.

4. Automatic system for searching information in a knowledge base by dialogue between a user and the system according to claim 3, characterized in that if the second means of travel of the tree encounter exclusive OR links none of which results of the request, then a suggestion of choice on these links is proposed, and if no exclusive OR link is encountered in a branch of the tree, then a suggestion of choice is proposed on the instances of the current class.

5. information retrieval system according to any one of the preceding claims, characterized in that the means (4) for storing the history of the dialogue comprise structured storage means, able to memorize in the form of a graph. all the semantic concepts referenced in the current state of the search dialog.

6. Information search system according to any one of the preceding claims, characterized in that the means (9) formatting suggestions are able to sort the suggestions into a first category of closed questions and a second category open questions.

7. Automatic process for searching information in a knowledge base by dialogue between a user and a system comprising the steps of

acquisition (20) of the information coming from the user,

- analysis (21) of this information to extract the focus and its properties,

selecting (22) an ontological view from at least one focus coming from the user, this selection being made on a set of previously defined ontological views, projecting (23) the information of the dialogue on the selected ontological view to obtain a list of all possible suggestions,

selecting (24) the suggestions to be presented by sorting the list of suggestions into at least two categories, the first category being the suggestions whose choices are exhaustively declinable and the second category being the suggestions corresponding to unknown elements,

- formatting (25) suggestions, and

- presentation (26) suggestions to the user.

An automatic information retrieval method according to claim 7, characterized in that an ontological view being structured in the form of a logical tree whose root is the focus object, the links between the classes and their subclasses of the knowledge base of the exclusive OR links and the relations of the knowledge base of the links AND, the projection of the dialogue information on the ontological view comprises the steps of: - searching from the root of the guidance object,

recursively traversing the tree from the guidance object so as to identify and descend all the AND links from the current node and identify and descend the only exclusive OR links corresponding to elements of the dialogue.

9. Automatic information search method according to claim 8, characterized in that during the course of the tree, the meeting of a class having exclusive OR links to its subclasses, none of which corresponds to an element of the dialog generates the creation of a suggestion of choice on these links and the absence of meeting an exclusive OR link on a branch of the tree generates the creation of a choice suggestion on the instances of the current class.

10. automatic information retrieval method according to any one of claims 7 to 9, characterized in that after the analysis of the information from the user, the semantic concepts thereof are stored in a history structured dialog in the form of a graph representing the current state of the search dialog.

11. Automatic information retrieval method according to any one of claims 7 to 10, characterized in that the formatting of the suggestions comprises the step of sorting the suggestions in a first category of closed questions and a second category of open questions.

12. Software product recorded on a storage medium for implementation by a computer serving as a dedicated equipment of the system and the automatic information retrieval method according to claims 1 to 6, respectively claims 7 to 11.