US 2013/0159317 A1 · HIGH PRECISION SET EXPANSION FOR LARGE CONCEPTS

Abstract

A set expansion system is described herein that improves precision, recall, and performance of prior set expansion methods for large sets of data. The system maintains high precision and recall by 1) identifying the qualify of particular lists and applying that quality through a weight, 2) allowing for the specification or negative examples in a set of seeds to reduce the introduction of bad entities into the set, and 3) applying a cutoff to eliminate lists that include a low number of positive matches. The system may perform multiple passes to first generate a good candidate result set and then refine the set to find a set with highest quality. The system may also apply Map Reduce or other distributed processing techniques to allow calculation in parallel. Thus, the system efficiently expands large concept sets from a potentially small set of initial seeds from readily available web data.

Claims20

Dependent claims

A computer-implemented method to measure the quality of a candidate result set expanded from a set of seed items, the method comprising:

receiving one or more seed items that represent members of a concept set for which a user wants to automatically generate additional members of the concept set;
automatically identifying additional seeds based on the received one or more seed items;
receiving one or more lists that include some items that are members of the concept set and other items that are not members of the concept set;
receiving a candidate result set that expands the received seed items to include items suspected of being members of the concept set;
determining a weight for each received list based on the received seeds, wherein the weight corresponds to an initial measure of the quality of the list;
determining a similarity metric of each item in the received candidate result set with the received seed items based on which of the received lists contain each item and the determined list weights;
determining a quality of the received candidate result set by combining the determined similarity metrics;
and
outputting the determined quality of the candidate result set,
wherein the preceding steps are performed by at least one processor.

7 more elements

A computer system for performing high precision set expansion for large concepts, the system comprising:

a processor and memory configured to execute software instructions embodied within the following components;
a list identification component that identifies one or more sources of potential entities that belong to a concept set of entities for expanding a known set of seed entities to include a larger portion of the concept set;
a seed receiving component that receives a set of positive seed items and a set of negative seed items, wherein the positive seed items represent items to expand and find similar items and the negative seed items represent items that are not indicative of similar items;, the seed receiving component configured to automatically identify additional seed items from the set of positive seed items and the set of negative seed items,
a list weighting component that determines a weight for each list based on a number of positive seed items contained in the list and a number of negative seed items contained in the list;
a candidate generation component that generates one or more candidate result sets that contain an expansion of items in addition to the received positive seed items, wherein the expansion includes one or more items discovered in the identified sources;
a similarity calculation component that determines a similarity metric between each entity in a generated candidate result set and one or more of the received seed items;
a quality determining component that combines a determined relevance metric and a coherence metric to determine a quality metric that indicates relevance and coherence among a set of entities in the generated candidate result set;
and
an iterative quality component that finds an acceptable result set by generating an initial candidate result set with a base quality metric and iteratively generating new candidate result sets with improved quality metrics.

6 more elements

Dependencies are inferred from the claim text.

High precision set expansion for large concepts

Life of this patent

High precision set expansion for large concepts

Life of this patent

Abstract

Claims20