Resolving entities from multiple data sources for assistant systems

• US 10,803,050 B1
• Filed: 07/27/2018
• Issued: 10/13/2020
• Est. Priority Date: 04/20/2018
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Salkola, Markku
• Primary Examiner(s): Woo, Isaac M
• Application Number:
  US16/048,049
• Time in Patent Office: 809 Days
• Field of Search: 707600-899
• CPC Class Codes: G06F 16/176 Support for shared access to files; File sharing support
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 16/24552 Database cache management
• CPC Class Codes: G06F 16/24575 using context
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/3323 using document space presentation or visualization, e.g. category, hierarchy or range presentation and selection
• CPC Class Codes: G06F 16/3329 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 16/338 Presentation of query results
• CPC Class Codes: G06F 16/90332 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 16/90335 Query processing
• CPC Class Codes: G06F 16/9038 Presentation of query results
• CPC Class Codes: G06F 16/904 Browsing; Visualisation therefor for navigating the web G06F16/954; browsing optimisation for the web G06F16/957
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9532 Query formulation
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 18/2411 : based on the proximity to a decision surface, e.g. support vector machines
• CPC Class Codes: G06F 2216/13 : Prefetching
• CPC Class Codes: G06F 3/011 : Arrangements for interaction with the human body, e.g. for user immersion in virtual reality blind teaching G09B21/00
• CPC Class Codes: G06F 3/013 : Eye tracking input arrangements G06F3/015 takes precedence
• CPC Class Codes: G06F 3/017 : Gesture based interaction, e.g. based on a set of recognized hand gestures interaction based on gestures traced on a digitiser G06F3/04883
• CPC Class Codes: G06F 3/167 : Audio in a user interface, e.g. using voice commands for navigating, audio feedback
• CPC Class Codes: G06F 40/205 : Parsing
• CPC Class Codes: G06F 40/274 : Converting codes to words; Guess-ahead of partial word inputs
• CPC Class Codes: G06F 40/295 : Named entity recognition
• CPC Class Codes: G06F 40/30 : Semantic analysis
• CPC Class Codes: G06F 40/40 : Processing or translation of natural language natural language analysis G06F40/20; semantic analysis G06F40/30
• CPC Class Codes: G06F 7/14 : Merging, i.e. combining at least two sets of record carriers each arranged in the same ordered sequence to produce a single set having the same ordered sequence
• CPC Class Codes: G06F 8/31 : Programming languages or programming paradigms
• CPC Class Codes: G06F 9/44505 : Configuring for program initiating, e.g. using registry, configuration files
• CPC Class Codes: G06F 9/4451 : User profiles; Roaming
• CPC Class Codes: G06F 9/453 : Help systems
• CPC Class Codes: G06N 20/00 : Machine learning
• CPC Class Codes: G06N 3/006 : based on simulated virtual individual or collective life forms, e.g. social simulations or particle swarm optimisation [PSO]
• CPC Class Codes: G06N 3/045 : Combinations of networks
• CPC Class Codes: G06N 3/08 : Learning methods
• CPC Class Codes: G06N 5/022 : Knowledge engineering; Knowledge acquisition
• CPC Class Codes: G06N 5/027 : Frames
• CPC Class Codes: G06N 7/01 : Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06Q 10/00 : Administration; Management
• CPC Class Codes: G06Q 50/01 : Social networking
• CPC Class Codes: G06V 10/764 : using classification, e.g. of video objects
• CPC Class Codes: G06V 10/82 : using neural networks
• CPC Class Codes: G06V 20/10 : Terrestrial scenes scenes under surveillance with static cameras G06V20/52; scenes perceived from the exterior of a vehicle G06V20/56; scenes perceived from the interior of a vehicle G06V20/59
• CPC Class Codes: G06V 40/28 : Recognition of hand or arm movements, e.g. recognition of deaf sign language static hand signs G06V40/113
• CPC Class Codes: G10L 13/00 : Speech synthesis; Text to speech systems
• CPC Class Codes: G10L 13/04 : Details of speech synthesis systems, e.g. synthesiser structure or memory management
• CPC Class Codes: G10L 15/02 : Feature extraction for speech recognition; Selection of recognition unit
• CPC Class Codes: G10L 15/063 : Training
• CPC Class Codes: G10L 15/07 : to the speaker
• CPC Class Codes: G10L 15/16 : using artificial neural networks
• CPC Class Codes: G10L 15/1815 : Semantic context, e.g. disambiguation of the recognition hypotheses based on word meaning
• CPC Class Codes: G10L 15/1822 : Parsing for meaning understanding
• CPC Class Codes: G10L 15/183 : using context dependencies, e.g. language models
• CPC Class Codes: G10L 15/187 : Phonemic context, e.g. pronunciation rules, phonotactical constraints or phoneme n-grams
• CPC Class Codes: G10L 15/22 : Procedures used during a speech recognition process, e.g. man-machine dialogue
• CPC Class Codes: G10L 15/26 : Speech to text systems G10L15/08 takes precedence
• CPC Class Codes: G10L 17/00 : Speaker identification or verification techniques
• CPC Class Codes: G10L 17/06 : Decision making techniques; Pattern matching strategies
• CPC Class Codes: G10L 17/22 : Interactive procedures; Man-machine interfaces
• CPC Class Codes: G10L 2015/223 : Execution procedure of a spoken command
• CPC Class Codes: G10L 2015/225 : Feedback of the input speech
• CPC Class Codes: H04L 12/2816 : Controlling appliance services of a home automation network by calling their functionalities arrangements in telecontrol or telemetry systems for selectively calling a substation from a main station; in which substation desired apparatus is selected for applying a control signal thereto or for obtaining measured values therefrom H04Q9/00
• CPC Class Codes: H04L 41/20 : Network management software packages
• CPC Class Codes: H04L 41/22 : comprising specially adapted graphical user interfaces [GUI]
• CPC Class Codes: H04L 43/0882 : Utilisation of link capacity
• CPC Class Codes: H04L 43/0894 : Packet rate
• CPC Class Codes: H04L 5/02 : Channels characterised by the type of signal
• CPC Class Codes: H04L 51/02 : using automatic reactions or user delegation, e.g. automatic replies or chatbot-generated messages
• CPC Class Codes: H04L 51/046 : Interoperability with other network applications or services
• CPC Class Codes: H04L 51/18 : Commands or executable codes
• CPC Class Codes: H04L 51/216 : Handling conversation history, e.g. grouping of messages in sessions or threads
• CPC Class Codes: H04L 51/222 : using geographical location information, e.g. messages transmitted or received in proximity of a certain spot or area
• CPC Class Codes: H04L 51/52 : for supporting social networking services
• CPC Class Codes: H04L 63/102 : Entity profiles
• CPC Class Codes: H04L 67/10 : in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/306 : User profiles
• CPC Class Codes: H04L 67/53 : using third party service providers
• CPC Class Codes: H04L 67/535 : Tracking the activity of the user network monitoring arrangements H04L43/00; recording of computer activity G06F11/34
• CPC Class Codes: H04L 67/5651 : Reducing the amount or size of exchanged application data
• CPC Class Codes: H04L 67/75 : Indicating network or usage conditions on the user display
• CPC Class Codes: H04W 12/08 : Access security

Abstract

In one embodiment, a method includes accessing a number of records describing a number of entities generated based on data collected from a number of data sources, where the records are grouped by data source, deduping the number of records in each group, selecting a data source as a core source, identifying, for a record in the core group, a candidate set including records from the non-core groups of records that satisfy conditions to be in the candidate set for the record, generating a feature vector for each pair of records between a record in the core group and a record in the candidate set, computing a probability that the pair of records describe a common entity for each pair of records, and linking the record in the candidate set to a globally unique entity identifier identifying a unique entity if the probability exceeds a threshold.

Claims

1. A method comprising, by one or more computing systems:

accessing a plurality of records based on data collected from a plurality of data sources, wherein the plurality of accessed records describes attributes of a plurality of entities, and wherein the records are grouped by their corresponding data source;

deduping the plurality of records by an entity-deduping module, wherein the entity-deduping module processes each group of records to associate each record within the group describing a particular entity with a unique entity identifier;

selecting, for each particular entity, one of the plurality of data sources as a core source, wherein the group of records associated with the core source is selected as the core group of records;

identifying, for a particular record in the core group of records for each particular entity, a candidate set comprising one or more records from the non-core groups of records that satisfy one or more conditions to be in the candidate set for the particular record;

generating, for each pair of records between a record in the core group and a record in the candidate set for each particular entity, a feature vector based on a measure of similarities of respective attributes in the pair of records;

computing, for each pair of records, a probability that the pair of records describe a common entity by processing the feature vector by a machine-learning classifier; and

linking, for each pair of records, the record in the candidate set to a globally unique entity identifier identifying a unique entity if the probability exceeds a threshold.

2. The method of claim 1, further comprising:

generating the plurality of records, wherein each record of the plurality of records is generated based on information associated with an entity presented around an occurrence of the entity on the collected data from a data source when the occurrence of the entity is detected by a data-analyzing module, wherein the data-analyzing module extracts the information associated with the entity by parsing and analyzing text and multimedia data around the occurrence of the entity.

3. The method of claim 1, wherein each of the plurality of records comprises one or more attribute-value pairs comprising an attribute name and an attribute value, wherein each attribute-value pair describes an attribute of the corresponding entity.

4. The method of claim 1, wherein a domain of an entity is associated with a pre-determined list of required attributes corresponding to the domain.

5. The method of claim 1, wherein deduping the plurality of records by an entity deduping-module comprises, for each group of records:

selecting a first record from the plurality of records in the group that does not have an assigned entity identifier;

assigning, to the first record, an entity identifier unique within the group;

identifying a candidate set comprising one or more records in the group that satisfy one or more conditions to be in the candidate set for the first record;

generating, for each pair of records between the first record and a second record in the candidate set, a feature vector based on a measurement of similarities of respective attributes in the pair of records;

computing, for each pair of records, a probability that the pair of records describe a common entity by processing the feature vector by a machine-learning classifier;

for each pair of records, if the probability exceeds a threshold;

if the first record does not contain more information than the second record;

assigning, to the second record, the entity identifier assigned to the first record;

swapping the two records such that the first record becomes the second record and the second record becomes the first record; and

removing the second record from the group.

6. The method of claim 1, wherein deduping the plurality of records by an entity-deduping module comprises, for each group of records:

selecting a first record from the plurality of records in the group that does not have an assigned entity identifier;

assigning, to the first record, an entity identifier unique within the group;

identifying a candidate set comprising one or more records in the group that satisfy one or more conditions to be in the candidate set for the first record;

generating, for each pair of records between the first record and a second record in the candidate set, a feature vector based on a measurement of similarities of respective attributes in the pair of records;

computing, for each pair of records, a probability that the pair of records describe a common entity by processing the feature vector by a machine-learning classifier; and

linking, for each pair of records, if the probability exceeds a threshold, the second record to the entity identifier assigned to the first record.

7. The method of claim 6, further comprising:

constructing a merged record describing the particular entity by merging the records associated with the unique entity identifier.

8. The method of claim 1, wherein the one or more conditions for a record from the non-core groups to be in the candidate set comprises a first condition that a geographic location of an entity corresponding to the record from the non-core groups is within a threshold distance from a geographic location of the particular entity.

9. The method of claim 1, wherein the one or more conditions for a record from the non-core groups to be in the candidate set comprises a first condition that an index of an entity corresponding to the record from the non-core groups is close to an index of the particular entity, wherein the indices are determined by a locality sensitive hashing algorithm.

10. The method of claim 9, wherein the locality sensitive hashing algorithm determines indices based on a similarity of entity names, wherein entities with similar names are hashed into close indices.

11. The method of claim 1, wherein the machine-learning classifier is a Gradient Boosted Decision Trees (GBDT) classifier.

12. The method of claim 1, wherein the machine-learning classifier is a logistic regression classifier.

13. The method of claim 1, wherein the machine-learning classifier is trained with labelled training data.

14. The method of claim 13, wherein the training data is labelled based on crowdsourced data.

15. The method of claim 1, wherein the globally unique entity identifier is the entity identifier unique within the core group of records.

16. One or more computer-readable non-transitory storage media embodying software that is operable when executed to:

access a plurality of records based on data collected from a plurality of data sources, wherein the plurality of accessed records describes attributes of a plurality of entities, and wherein the records are grouped by their corresponding data source;

dedupe the plurality of records by an entity-deduping module, wherein the entity-deduping module processes each group of records to associate each record within the group describing a particular entity with a unique entity identifier;

select, for each particular entity, one of the plurality of data sources as a core source, wherein the group of records associated with the core source is selected as the core group of records;

identify, for a particular record in the core group of records for each particular entity, a candidate set comprising one or more records from the non-core groups of records that satisfy one or more conditions to be in the candidate set for the particular record;

generate, for each pair of records between a record in the core group and a record in the candidate set for each particular entity, a feature vector based on a measure of similarities of respective attributes in the pair of records;

compute, for each pair of records, a probability that the pair of records describe a common entity by processing the feature vector by a machine-learning classifier; and

link, for each pair of records, the record in the candidate set to a globally unique entity identifier identifying a unique entity if the probability exceeds a threshold.

17. The media of 16, wherein the software is further operable when executed to:

generate the plurality of records, wherein each record of the plurality of records is generated based on information associated with an entity presented around an occurrence of the entity on the collected data from a data source when the occurrence of the entity is detected by a data-analyzing module, wherein the data-analyzing module extracts the information associated with the entity by parsing and analyzing text and multimedia data around the occurrence of the entity.

18. The media of 16, wherein each of the plurality of records comprises one or more attribute-value pairs comprising an attribute name and an attribute value, wherein each attribute-value pair describes an attribute of the corresponding entity.

19. The media of 16, wherein a domain of an entity is associated with a pre-determined list of required attributes corresponding to the domain.

20. A system comprising:

one or more processors; and

a non-transitory memory coupled to the processors comprising instructions executable by the processors, the processors operable when executing the instructions to;

access a plurality of records based on data collected from a plurality of data sources, wherein the plurality of accessed records describes attributes of a plurality of entities, and wherein the records are grouped by their corresponding data source;

dedupe the plurality of records by an entity-deduping module, wherein the entity-deduping module processes each group of records to associate each record within the group describing a particular entity with a unique entity identifier;

select, for each particular entity, one of the plurality of data sources as a core source, wherein the group of records associated with the core source is selected as the core group of records;

identify, for a particular record in the core group of records for each particular entity, a candidate set comprising one or more records from the non-core groups of records that satisfy one or more conditions to be in the candidate set for the particular record;

generate, for each pair of records between a record in the core group and a record in the candidate set for each particular entity, a feature vector based on a measure of similarities of respective attributes in the pair of records;

compute, for each pair of records, a probability that the pair of records describe a common entity by processing the feature vector by a machine-learning classifier; and

link, for each pair of records, the record in the candidate set to a globally unique entity identifier identifying a unique entity if the probability exceeds a threshold.