# US 2013/0159317 A1 · High precision set expansion for large concepts

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2013/0159317 A1
- Document ID: US20130159317A1
- Status: Published application
- Kind: A1
- Application number: 13/325,072
- Filed: 2011-12-14
- Published: 2013-06-20
- Earliest claimed: 2011-12-14
- Assignees: Microsoft Corporation
- Inventors: Jiewen Huang; Zhimin Chen; Arvind Arasu; Vivek Narasayya
- Web page: https://patentgrep.com/patent/US20130159317A1

## CPC

- G06F 16/245: Query processing
- G06F 16/9535: Search customisation based on user profiles and personalisation
- G06Q 30/0201: Market modelling; Market analysis; Collecting market data
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR

## 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.

## Claims

### Claim 1

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.

### Claim 2

(canceled)

### Claim 3 (depends on 1)

The method of claim 1 wherein receiving one or more seed items comprises querying a user to propose suggested seeds from which the user can select.

### Claim 4 (depends on 1)

The method of claim 1 wherein receiving one or more seed items comprises receiving separately identified positive and negative seeds, where negative seeds are items that are known not to be members of the concept set.

### Claim 5 (depends on 1)

The method of claim 1 wherein receiving lists comprises accessing web crawl data to identify lists in crawled web pages.

### Claim 6 (depends on 1)

The method of claim 1 wherein receiving the candidate result set comprises generating the candidate result set automatically as an initial guess of a good result set to be improved iteratively based on the determined quality.

### Claim 7 (depends on 1)

The method of claim 1 wherein determining a list weight comprises comparing a number of positive seeds the list contains versus a number of negative seeds the list contains or does not contain, where positive seeds are items known to be members of the concept set and negative seeds are items known not to be members of the concept set.

### Claim 8 (depends on 1)

The method of claim 1 wherein determining a list weight comprises calculating a ratio of a number of positive seeds present in the list plus a number of negative seeds not present in the list to a total number of seeds, where positive seeds are items known to be members of the concept set and negative seeds are items known not to be members of the concept set.

### Claim 9 (depends on 1)

The method of claim 1 wherein determining a list weight comprises applying a cutoff so that the weight of lists that contain an insufficient number of positive seeds is reduced, where positive seeds are items known to be members of the concept set.

### Claim 10 (depends on 1)

The method of claim 1 wherein determining the similarity metric comprises applying a Weighted Jaccard or a Weighted Cosine distance measurement that determines how related an item in the candidate result set is to the seeds.

### Claim 11 (depends on 1)

The method of claim 1 wherein determining the similarity metric comprises determining similarities in a distributed fashion using Map Reduce techniques to partition the determination to different computer systems and to combine the results upon completion.

### Claim 12 (depends on 1)

The method of claim 1 wherein determining the quality comprises adding the similarity metric for each item in the candidate result set to determine the quality.

### Claim 13 (depends on 1)

The method of claim 1 wherein determining the quality comprises separately determining a relevance and coherence and weighting the relevance and coherence to determine an overall quality of the candidate result set.

### Claim 14

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.

### Claim 15 (depends on 14)

The system of claim 14 wherein the system provides an application-programming interface (API) through which other software components can programmatically access the system to perform set expansion.

### Claim 16 (depends on 14)

The system of claim 14 wherein the list weighting component calculates the weight by adding how many positive seed items are in the list to how many negative seed items are not in the list, and then dividing this number by a total number of positive and negative seed items.

### Claim 17 (depends on 14)

The system of claim 14 wherein the list weighting component applies a cutoff whereby the weight of a list that does not contain a threshold number of positive seed items is reduced or set to zero.

### Claim 18 (depends on 14)

The system of claim 14 wherein the quality determining component determines the relevance metric based on how similar an entity in the candidate result set is to the received seed items and determines the coherence metric based on how consistent an entity in the candidate result set is with the rest of the candidate result set.

### Claim 19 (depends on 14)

The system of claim 14 further comprising a seed generalization component invoked by the system to generalize received negative seed items, wherein generalization identifies other candidate items that are more like the negative seed items than the positive seed items and removes such items from the candidate result set.

### Claim 20

(canceled)
