Classifications

• • G—PHYSICS
  • G06—COMPUTING OR CALCULATING; COUNTING
  • G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
  • G06N5/00—Computing arrangements using knowledge-based models
  • G06N5/02—Knowledge representation; Symbolic representation
• • G—PHYSICS
  • G06—COMPUTING OR CALCULATING; COUNTING
  • G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
  • G06N5/00—Computing arrangements using knowledge-based models
  • G06N5/01—Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound

Definitions

• the invention relates to the fusion of information from several sensors and more particularly the processing of information or data from heterogeneous sensors, the data or information may themselves be non-homogeneous.
• the merge operation is performed by means of a processor, for example, within a monitoring system. At the end of this operation, the result is transmitted, for example in the form of a control signal.
• the signal may be a signal triggering a control process, or the display of information from the merger. It can also take the form of an alarm signal.
• Systems incorporating multiple sensors are used in a wide variety of areas, such as site monitoring, maintenance, robotics, weather forecasts, as well as programming of systems or devices such as TV program recordings. Such systems can also be implemented in information interpretation systems from the media.
• Merging information or data is a critical process for decision-making, regardless of the area of interest in which the decision is made. Indeed, the first step in a decision-making process is the collection of information or data to evaluate a situation. This information can come from various sources and be expressed in different formats or media. Once collected, the information must be combined and arranged in order to obtain a global but synthetic view of the situation. This combination of heterogeneous information into a single coherent view is a complex problem to be solved, but necessary to trigger and control actions depending on the result of the merger.
• a vast majority of information fusion research focuses on merging homogeneous data with low numerical levels.
• Other methods are to merge low-level data to derive higher-level information.
• data from seismic, acoustic, chemical sensors, etc. are merged and interpreted to more generally detect the presence of a person in a room or the use of a computer.
• These methods are interested in input data that is digital and low-level, even if the output of the fusion system is higher semantic level information.
• Low level data is, for example, radar tracks, object coordinates, velocities, etc. The interpretation of these data is simple and does not require to have the general knowledge of the field of interest.
• Some information fusion methods rely on the Dempster-Shafer theory, a theory that generalizes probability theory, and thus uses belief functions. Belief functions are known for their ability to faithfully represent the information and the truth of this information. Applicant's patent application FR 0705528 is an example of its implementation to merge information from independent sensors.
• the information fusion can be divided into several levels. The first concerns the fusion of information on the characteristics of objects. This level of fusion allows to identify and refine, by fusion of several observations, the estimation of the characteristics of the objects present in the world. The second level is about merging objects. It is a question of appreciating the state of the objects present in the world. The third relates to the discovery of the relations between the different objects present in the world.
• One of the aims of the present patent application is to integrate heterogeneous information by merging them at a high level of representation and taking into account the semantics they convey.
• the terms "high level of representation or high semantics" are used to differentiate the subject matter of this patent application from low level digital data.
• the objects treated by the method according to the invention are in the form of phrase, expression, syntax, etc.
• one of the objectives of this patent application is to merge symbols rather than numbers and to have a symbolic representation of objects and heuristics. The heuristics will be expressed according to the semantics (i.e. meaning) of the information to be merged.
• the above-mentioned 2008 publication describes the use of conceptual graph formalism to represent knowledge and information as part of a recommendation system for intelligent digital television.
• the recommendation system analyzes the descriptions of the television programs and decides whether or not to recommend a program to a specific user.
• the authors use a merge platform to obtain accurate and secure television program descriptions, both in terms of the programming schedule and the description of program content.
• the model of the conceptual graphs proposed by JF Sowa and taken up in the aforementioned publication is essentially composed of a support and the graphs themselves.
• a conceptual graph represents several concepts and the relationships that exist between them.
• Conceptual graphs consist of entity nodes and relationship nodes.
• Figure 1 shows features that are drawn as rectangles while the relationships are oval.
• the theory of conceptual graphs relies, among other things, on the use of a medium.
• Support is a hierarchy of types of concepts and relationships handled. That is to say, it is the set of all types of objects and relations present in the real world that we are going to represent, organized in the form of a hierarchy.
• the support can thus be seen as a simplified ontology of the domain of interest which includes only the types of objects and the type of relation.
• T is the type of concept. This is the type of real world object that is represented, r is the value or measure observed for the represented object. For example, to represent a temperature of 30 degrees, we can write the concept [Temperature: 30], where Temperature is the type of the concept and 30 is its value, also referred to in the rest of the description.
• the methods and devices according to the prior art do not make it possible to respond to the aforementioned problem. They are restricted to data stored in numeric form (no strings of characters, for example) and are implemented in the context of very simple situation, boiling down to a measurement or the state of a characteristic of a object.
• One of the objectives here is therefore to propose a method for merging information representing complex situations.
• An object of the invention is in particular to make the information or data fusion process parameterizable taking into account, in particular, business knowledge and user preferences, and by means of a suitable fusion process, for example, of to merge data or information that is initially presented in heterogeneous formats and that verifies the compatibility criterion according to a set threshold value.
• the method uses, for example, as function of compatibility between two nodes a function expressed in the following form: fcomp: E x E -> ⁇ true, false ⁇ x E xE where E is the set of concept nodes defined on a support S and Gi and G 2 are two conceptual graphs defined on S to be compared.
• the method comprises a standardized similarity measurement complying with the following conditions (ki), (k 2 ) and (k 3 ):
• the distance measure is determined, for example, according to the data stored in the knowledge base and verifies the conditions (k ⁇ , (k ' 2 ), (k 4 ) and (k 5 )
• the fusion function can be determined as follows :> ffusion: ⁇ true, false ⁇ xE xE-> Eu ⁇ E xE ⁇ where E is the set of concept nodes defined on a support S and Gi and G 2 are two conceptual graphs defined on S to merge.
• CGE is the concept resulting from the fusion of ci and C 2 and Id is the identity function defined on E xE.
• the invention also relates to a system for the fusion of high-level semantic information representing complex situations composed of several objects or data coming from several sensors ci, characterized in that it comprises at least the following elements: allowing the observation of information and inputs, o A knowledge base comprising elements characteristic of the fusion application and adapted to parameterize the melting step performed in the method according to claim 1, and an information base containing all the data from the sensors, o A processor adapted to transfomer information from the knowledge base and the information base into a form of representation of conceptual graphs, said formatted information being transmitted to a processor adapted to perform the following steps:
• a step during which said merging strategy is applied to the different stored information in the form of graphs a step at the end of which the merged data are transmitted to a decision-making system, at least one output in connection with control devices for recording and / or displaying the results resulting from the data fusion.
• the merger system is, for example, associated with a TV program recording device and comprises two information sources which supply data, processed in such a way as to associate a conceptual graph with each, the information from these graphs being merged taking into account the user preferences present in the knowledge base and in that it comprises a module adapted to associate a TV program with a category and a module emitting a representative signal or a control signal to said device recording.
• FIG. 1 an example of a fusion of two conceptual graphs
• FIG. 2 a block diagram of the method implemented in the present invention according to the different levels of interpretation (quantity of domain knowledge necessary to represent the information),
• FIG. 3 a block diagram of the method implemented in the present invention, according to the flow of data
• FIG. 5 an example of a hierarchy for a television program
• Figures 6A and 6B information related to a television program.
• the method is applicable to information transmitted in the form of natural language, textual or audio, semi-structured data or even low-level data, insofar as there is a system, automated or otherwise, making it possible to describe, under form of conceptual graphs, the content of this information by placing it in context.
• FIG. 2 schematizes an example of implementation of the method for different sensors Ci, C 2 , etc. which constitute several different sources of information.
• the captured information is first extracted by an extraction system 10 or interpretation whose particular function is to obtain the observation of A and the observation of B.
• the two observations A and B are then transmitted to an identification system 1 1.
• Observations A and B are examined to determine whether they are compatible and whether or not they correspond to descriptions of the same object in the real world.
• a compatibility criterion is predetermined according to the field of application of the invention 12. If the observations A and B verify this criterion, then they are compatible and merged and are shown in Figure 2 in the form AB or ABC when these three values are compatible.
• the method determines the relations existing between the objects.
• Such an incompatibility between the observations can occur, for example, when a merge request is made from sensors pointing, a priori, on the same storage device of an observation or monitoring system that can contain several objects. .
• the incompatibility between the observations may be due, for example, to the fact that the sensors have observed two different objects that are spatially close.
• the method will make it possible to account both for the fact that two distinct objects exist and for the spatial relationship existing between the two objects. Once these relationships are discovered, it will then be possible to decide which of the descriptions should be returned to the system causing the merge request.
• the method uses the formalism of the conceptual graphs to represent knowledge and information, such as that described in Figure 1.
• the same model will be used to perform the merge process.
• the originality of the present patent application is in particular to use the conventional maximum join operator and to adapt it to take into account the business knowledge and the user preferences.
• this will make it possible to merge incompatible data or information in the sense of the fusion of the graphs.
• merge heuristics within the maximum join. These merge heuristics will be called "merge strategies”.
• Merge strategies are compound functions that will enable the encoding of knowledge associated with an application domain. They are used to extend the concept of compatibility between two concepts of two different graphs.
• Figure 3 schematically shows the elements necessary for the implementation of the invention.
• the system has several Ci sensors that will collect the information or data to be merged. This information is transmitted to an interpretation and extraction device 10 in order to transform them so that they appear in the form of conceptual graphs.
• the observations thus formatted are stored in a memory 13 or observation database which is in relation with a business knowledge base 12 which contains various data relating to a trade, a field of trade or a field of knowledge, which will serve to set the merge step.
• This knowledge base 12 is constituted for example by a user 14 of the system.
• This knowledge base will be used for the implementation of the various elements involved in the process: mathematical operators, parameters, business rules, etc.
• the interrogations are performed, for example, in the form of requests transmitted from the user to the module 15.
• the knowledge of the base 12 and the observations of the memory 13 are matched through the use of the operators of the module 15 to respond to requests. These queries allow the user 14, for example, to visualize the representation of the real situation according to different points of view.
• the information from the sensors is stored in the observation database, the information from the knowledge of the domain (knowledge base and business rules) and entered by an operator of the system are stored in the knowledge base.
• the function of the recommendation system is, in particular, to analyze the descriptions of the television programs and to recommend or not to recommend a program to a specific user.
• the invention uses a fusion platform such as that described in FIGS. 3 and 4 to obtain descriptions. accurate and reliable television programs, both as regards the programming schedule and the description of the program content.
• the fusion platform is, for example, made up of modules and physical equipment, such as memories, knowledge bases, processors, input / output allowing the acquisition and the communication of data between the fusion system according to the invention. invention and the data sensor and recording or result display devices.
• a first step is to build a recommendation system for television programs, which will then be coupled with a video recording system that automatically records the relevant programs for a user when the user is absent or a system for recording. display information that will be used by a user.
• the recommendation system is built through a learning phase of user habits. The programs watched by the users are studied, through their characteristics of the programs that interest them. This definition is made automatically, via a learning phase, by a learning algorithm known to those skilled in the art. The information is stored, for example, in an observation database or knowledge base.
• Figure 4 is an example of possible architecture for the automatic recording of certain TV programs according to a user's preferences.
• the system includes two information sources 20, 21 that provide data by forming XMLTV via inputs 28 of the information fusion and management system obtained. Data from these two sources are treated so as to associate for each of these sources a graph of concepts 22a, 22b.
• the information of the two graphs are first stored in a database 23. They are then merged F taking into account the elements stored in the knowledge base 27 and according to the method detailed below which takes into account the preferences of the user accessible in the domain of knowledge.
• the merged information is then transmitted to a device 24 whose particular function is to analyze the descriptions of the television programs, to determine which category belongs to a program, then to recommend it or not to a user or to transmit a signal allowing its recording or its display on a screen as a help to a user.
• This device 24 will also manage and control the recording or not of a transmission on video recording systems 26A, 26B, 26C or manage the transmission of a display signal on a screen 30 which can take the form of a recommendation or be an alarm signal. It is also possible to transmit a signal to an audible alarm.
• the signals pass through the outputs 29 of the system or fusion platform.
• the merge platform provides accurate and safe television program descriptions, both in terms of the programming schedule and the description of the content of this program.
• the device 24 uses information stored in the observation database grouping the graphs.
• This module for determining the category to which a program belongs belongs to one of the modules that directly use the result of the merger module.
• a new television program is evaluated on the basis of its description.
• the description of such a program must contain the program start and end dates, as well as the content of this program. It is on this condition that the automatic recording system will record the correct time slots.
• the recommendation system initially used the flow of data and meta-data transiting via digital terrestrial television or TNT French, called "DVB" for Digital Video Broadcast.
• Metas data of TNT include information such as title, start date, duration, genre of each TV program. However, very little information is available on the content of the program itself. In order to obtain more detailed descriptions, the information from this source is merged with that from a second source: the TV magazine online and in the pocket represented by the reference 21.
• these data are part of the composition of the database or knowledge base used by the invention.
• the ontology includes all the entities existing in a domain of application as well as the relations that can exist between them.
• the word ontology is used to refer to a structured set of terms and concepts that represent the meaning of an information field, whether by the metadata of a namespace, or the elements of a domain of knowledge.
• Ontology is itself a data model representative of a set of concepts in a domain, as well as the relationships between these concepts. It is used to reason about the objects of the domain concerned.
• Figure 5 shows an example of hierarchy and subhierarchies for a TV program. All the situations likely to unfold are formulated through canonical bases. Potential interactions between entities are represented using the conceptual graph associated with a sample model for a TV program. After having defined the model of the domain, the observations are automatically acquired in the formalism of graphs and stored in the form of conceptual graphs according to steps known to those skilled in the art in memories of the TV system.
• Figures 6A and 6B show examples of observations made on a DVB stream and on the website of the pocket TV magazine. These observations are stored as a conceptual graph. The right part and the left part of Figure 6B present two conceptual graphs that the process will combine before merging. There are several possibilities to perform the merge of these two types of observations.
• the method according to the invention will use an extended maximum join function, as defined below.
• the fusion method according to the invention will be executed within a processor of the system, which will then issue a control message to the recording system 26 (FIG. 4).
• the work data being defined we will now detail the aforementioned fusion strategies which are part of an extension of the maximum join defined by the aforementioned prior art. For this reason, the construction of the set of fusion hypotheses of two graphs remains guided by the search for compatible projections, the concept of compatibility between two concept nodes will be extended according to the principle described below.
• E be the set of concept nodes defined on a support S or simplified ontology.
• Gi and G 2 be two conceptual graphs defined on S.
• a noted fusion strategy is defined as follows: E ⁇ E u ⁇ E x E ⁇ where the initials o correspond to the mathematical operation of composition of functions, and where f fus i on : ⁇ true, false ⁇ xExE-> Eu ⁇ E xE ⁇ is a function of fusion of concept nodes of graphs, and f com p: E xE -> ⁇ true, falsexE xE is a compatibility test function between two concept nodes of graphs.
• the merger strategy results in either the merged concept, if the initial concepts are compatible, or the initial concepts, if these are not compatible, so not mergeable.
• Maximum join according to a merge strategy results in either the merged concept, if the initial concepts are compatible, or the initial concepts, if these are not compatible, so not mergeable.
• E is the set of concept nodes defined on a support S.
• the graphs H, Gi and G 2 are conceptual graphs defined on S.
• f CO mp is a compatibility test function defined on E xE -> ⁇ true, fakeExe and ffusion is a merge function defined on ⁇ true, false ⁇ xExE-> Eu ⁇ E xE ⁇ .
• the method according to the invention relates more particularly to the maximum joining method which is based on the definitions of the specialization, generalization and projection known to those skilled in the art.
• fcomp be a compatibility function defined on ExE -> ⁇ true, falseEexE, or two conceptual graphs Gi and G 2 with a common generalization H and let the projections Pi: H-> Gi and P 2 : H-> G 2 .
• Pi and P 2 are compatible according to the function f COm p if, for each concept c of the graph H, the following conditions are respected: • Pi (c) and P 2 (c) have a common subtype different from the absurd type,
• H be the general generalization of the most general graphs G 1 and G 2
• Pi and P 2 are two compatible projections of H on Gi and G 2 according to a strategy of fusion denoted by the strategy fusi orv Pi and P 2 are maximally extended.
• H-> G 2 Pi and P 2 are maximally extended if and only if there is no common generalization H 'of Gi and G 2 such that H is a subgraph of H'.
• H be the general generalization of the graphs Gi and G 2 the most general.
• Pi and P 2 are two compatible projections of H on Gi and G 2 according to a strategy of fusion noted strategy fU sion-Pi and P 2 are maximally extended.
• a join according to a merge strategy strategiefusion on extended projections is called a maximum join according to strategy.
• a merge strategy merge join on these extended projections is called maximum join according to strategiefusion Merger strategies
• a similarity or dissimilarity is an application with numerical values which makes it possible to measure the link between the individuals of the same set. For a similarity the link is all the stronger as its value is great.
• a similarity index is a diss application that satisfies condition ki above, and with the following condition:
• a distance is a dissimilarity index which also checks the following two properties:
• the compatibility function implemented in the method according to the invention can be defined with respect to a criterion to be met for declaring two "compatible" information for one or more values.
• the compatibility function can be defined either according to the distance between two values, or according to any Another similarity function defined by domain experts.
• the compatibility function between two nodes is of the following form: f ⁇ mp: E x E -> ⁇ true, false ⁇ x E xE where E is the set of concept nodes defined on a support S and Gi and G 2 are two conceptual graphs defined on S to compare.
• the compatibility between two elements of the same set can be calculated, either with respect to the similarity between these two elements, or with respect to the distance separating it.
• the remainder of the description gives two examples of definition of the compatibility function according to the measurement of the similarity and the measurement of the distance.
• Each of the approaches is illustrated in a concrete case concerning the merger of description of television programs.
• the compatibility of two elements can be defined according to the proportion of identical constituents between these two elements. It will therefore be used, initially, a standardized similarity measure to test the compatibility of two concepts, with a view to their fusion. This similarity measure is determined by an expert in the field of application and must respect the conditions (ki), (k 2 ) and (k 3 ) mentioned above.
• the compatibility of two elements can be tested according to the distance separating these two elements. The distance measurement is determined by an expert in the field of application and must comply with the conditions (ki), (k ' 2 ), (k 4 ) and (k 5 ) mentioned above. Once the distance between two elements has been calculated, it is compared with a compatibility threshold also defined by an expert in the field of application.
• the compatibility function then has the following form:
• the next step of the method is to perform a merge step which will implement a fusion function explained below.
• the merge function allows, for any pair of concept nodes to calculate if it exists, the concept node corresponding to the merge of the initial nodes. If the initial nodes are not compatible, the merge function will result in the initial nodes.
• the fusion function of two concept nodes is of the following form: ffusion: ⁇ true, false ⁇ xE xE-> Eu ⁇ E xE ⁇ where E is the set of concept nodes defined on a support S and Gi and G 2 are two conceptual graphs defined on S to merge.
• a first strategy may be to extend the notion of compatibility between dates. Two dates are compatible if the difference between the two is less than a given threshold value, for example 5 minutes. If two dates are compatible but different, the smaller date will be chosen if it is the start date of the program, otherwise the later date will be chosen.
• notions of compatibilities are extended between dates and titles. The compatibility between two dates is calculated as for the first strategy. Two titles are compatible if one of them is contained in the other.
• the notion of compatibility is also extended between dates and titles. The compatibility between two dates is calculated as for the first strategy. According to this strategy, two titles are compatible if the length of the sub-channels common to both titles exceeds a given threshold.
• the compatibility function f ⁇ mp is set to E ⁇ xE ⁇ -> ⁇ true, false ⁇ xE ⁇ xE ⁇
• the value of a concept of type Title is a string corresponding to the title of the program described.
• the similarity function is based on the cumulative length of the common character substrings between the two titles and is defined as follows:
• sim [Titre: t1], [Titre: t2]
• sim ti sim ti , r ⁇ (t1, t2)
• sim sim ti , r ⁇ (t1, t2)
• itr ⁇ (t1, t2) max (size (t1), size (t2))
• the following numerical example was performed by testing the compatibility of concept nodes of type Date. These are actually schedules start and end of program broadcast. Intuitively, it has been chosen to represent the fact that two distant schedules of less than 5 minutes are compatible. In order to manipulate these times as integers and thus facilitate comparisons, a simple transformation is applied, prior to any compatibility test, on the schedules. Each schedule is given as the number of seconds that has elapsed since a reference date.
• the compatibility function f ⁇ mp is thus defined on: E D x E D -> ⁇ true, false ⁇ xE D x E 0 , with E 0 the set of the concepts nodes of type Date.
• Schedules are given in seconds and the threshold is 5 minutes, or 300 seconds.
• the invention also applies in the field of crisis management.
• defining the domain model is the very first step in the merge process.
• the process will parameterize this device, in order to integrate knowledge of the business, necessary for the merger process.
• the projection makes it possible to find the specialized occurrences of a query graph.
• query graph For example, the following query graph:
• the process being generic, it is then a question of being able to easily parameterize it in order to adapt it to the field studied.
• the method therefore comprises a set of rules derived from the business knowledge.
• the use of such rules can inject business knowledge into the merge platform using heuristics also called strategies.
• the strategies defined for the identification step are called “choice” strategies because they make it possible to choose the description to be returned in response to the merge request.
• the strategies used in the merge step are "merge strategies", those used for knowledge-base queries, "query strategies.”
• these are rules or functions, integrating business knowledge with respect to the observations made.
• the premises of these rules are conceptual graphs representing the observations, as well as conditions on the values of the concepts and relations of these graphs (use of distance metrics).
• the conclusion is a conceptual graph corresponding to the response to be sent concerning the valid (-s) observation request (-s) (-s) - which will eventually need to be merged.
• the premise of rules is the two relationships to merge.
• the conditions present in the premises of the rules can relate both to the values of the relations and objects in relations to be merged, but also to the complete graph describing the observation.
• the conclusion of a merger strategy is the merged relationship. In other words, these are the two objects resulting from the merger of two pairs of objects observed. These two objects are themselves linked by the relation corresponding to the fusion of the two relations initially observed.
• the fusion system according to the invention can be implemented within a communication network composed of several processors (on which the sensors, the effectors and the fusion system are implemented) linked together.
• the storage of information can be performed on hard disks.
• a sensor in the context of this invention can be both a physical device (camera, radar, microphone Certainly, the corresponding data processing device.
• the object of the invention has notably the advantages listed hereafter: the possibility of merging information extracted from a report of observations made by a human with information extracted from newspaper dispatches or other sources accounting for of the same event.
• the method is applied for complex situations composed of several actors or interacting objects. It applies to high-level semantic data fusions using business knowledge that has an even higher semantic level.
• the point of view or vocabulary of the sensor can also generate another case: two observations concern the same object, but the way of expressing it is different is different according to the sensor studied. It will then be a question of not declaring these two observations as incompatible, since the knowledge of the domain makes it possible to affirm that it is indeed the same object in reality.
• the method and the system according to the invention make it possible to merge knowledge in a homogeneous manner and independent of the modalities under which the information is given. Moreover, this knowledge can come from different levels of fusion.
• the method is generic and can be applied whatever the sensors delivering the observation and whatever the situation observed.

Landscapes

• Engineering & Computer Science (AREA)
• Theoretical Computer Science (AREA)
• Computing Systems (AREA)
• Data Mining & Analysis (AREA)
• Evolutionary Computation (AREA)
• Physics & Mathematics (AREA)
• Computational Linguistics (AREA)
• General Engineering & Computer Science (AREA)
• General Physics & Mathematics (AREA)
• Mathematical Physics (AREA)
• Software Systems (AREA)
• Artificial Intelligence (AREA)
• Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Applications Claiming Priority (2)

Publications (1)

Family

ID=40940421

Family Applications (1)

Country Status (4)

Families Citing this family (22)

Family Cites Families (3)

• 2008
  • 2008-12-19 FR FR0807232A patent/FR2940487A1/fr active Pending
• 2009
  • 2009-12-21 US US13/140,807 patent/US8818929B2/en not_active Expired - Fee Related
  • 2009-12-21 EP EP09796723A patent/EP2370938A2/de not_active Withdrawn
  • 2009-12-21 WO PCT/EP2009/067666 patent/WO2010070142A2/fr not_active Ceased

Non-Patent Citations (1)

Also Published As

Similar Documents

Legal Events