Devices, systems, and methods for resolving named entities

An information processing apparatus to select a token from a document to describe a field of interest includes an obtaining unit, a determining unit, a clustering unit, and a selecting unit. The obtaining unit obtains a list of tokens output from extractors that received the document as an input. Each output token has an extractor score assigned to by an extractor. The determining unit determines, as a word frequency value, a frequency of each word in the list of tokens, determines a token score for each token in the list of tokens, and determines a distance between each token in the list of tokens. The clustering unit clusters each token in the list of tokens into a plurality of groups. The selecting unit selects a token with a group of the plurality of groups to describe the field of interest in the document.

BACKGROUND

Technical Field

This application generally relates to computer recognition of named entities in the text of a document.

Background

Natural language processing includes information extraction (IE) as a computer based task of automatically extracting structured information from unstructured and/or semi-structured machine-readable documents. In Information extraction, named entities are real world objects, such as organizations, persons, locations, and products that can be denoted with a proper name. Named entity recognition (NER) is that part of information extraction which uses named entity extractors to locate and classify named entities in text into pre-defined categories, such as organizations, the names of persons, locations, expressions of times, quantities, monetary values, and percentages.

At present, there exist conventional techniques related to named entity extractors which seek to provide a better result set. Conventional techniques address a set of data annotated by one NER model and address combing multiple NER models. Techniques related to combing multiple NER models tend to focus on how to use multiple named entity recognition techniques to have better precision/recall in order to identity various entities.

For a given a set of data annotated by one NER model, conventional techniques look to determine how to resolve which entities reference the same entity (i.e., that Bush and George Bush both reference the same person). In other words, given a set of extracted named entities from a document and comments, find all references to the same entity. In this regard, English Wikipedia policy on article titles provides standards for naming article titles in a recognizable, concise, and natural way that is precise and consistent and provides redirects to article titles that are less than this. For a set of data annotated by one NER model, some conventional techniques are dependent on a Wikipedia reference to find which variation of the entity name is the most accurate.

Conventional techniques also look to combine multiple NER models to obtain a more accurately annotated results. For example, given a token in a document (such as a “Party To Contract”), conventional techniques try to solve whether a given name entity is a desired name entity to extract by combining multiple NER models. However, this requires outputting all references to the “Party To Contract” rather than attempting to output a single answer such as where a user desires to determine a particular “Party To Contract” in a contract.

SUMMARY

According to an aspect of the present invention, an information processing apparatus to select a token from a document to describe a field of interest in the document includes an obtaining unit configured to obtain a list of tokens output from a plurality of extractors that received the document as an input, wherein each output token has an extractor score assigned to by an extractor of the plurality of extractors, a determining unit configured to determine, as a word frequency value, a frequency of each word in the list of tokens, determine a token score for each token in the list of tokens, and determine a distance between each token in the list of tokens, a clustering unit configured to cluster each token in the list of tokens into a plurality of groups, and a selecting unit configured to select a token with a group of the plurality of groups to describe the field of interest in the document.

DESCRIPTION

The following paragraphs describe certain explanatory embodiments. Other embodiments may include alternatives, equivalents, and modifications. Additionally, the explanatory embodiments may include several novel features, and a particular feature may not be essential to some embodiments of the devices, systems, and methods that are described herein.

Embodiments may be implemented by an information processing apparatus that uses, as an input, the output of many named entity recognition (NER) models to determine which name entities reference the same name entity and, the set of those name entities which reference the same name entity, which variation in the set is the most appropriate to be returned as the one string that best represents the set. In other words, given a document, embodiments determine which string is the desired entity to extract. For example, in a particular contract, embodiments may determine what company listed in a contract is the “Party To Contract” and which date is the effective date of the contract. Embodiments work towards outputting a single answer—there is only one “Party To Contract” in a contract—as the most accurate representation of the entity without finding all references to the “Party to the Contract” and without being dependent on a third party standard such as Wikipedia. In finding which string best represents a set of related entities, figuring out what entities are actually referencing the same entity is a subset of embodiments.

FIG. 1illustrates a hardware configuration example of an information processing apparatus (computer)100. Information processing apparatus100may be utilized to locate named entities in the text of a document. A central processing unit (CPU)101of the information processing apparatus100executes a processing based on an operating system (OS) and various programs to control the respective units of the information processing apparatus. A read-only memory (ROM)102stores static data among the programs executed by the CPU101and stores parameters for computations. A random-access memory (RAM)103is utilized as a work area for the CPU101and as a temporary storage area of data. The ROM102and the RAM103are connected via a bus104to the CPU101. An input apparatus105, such as a keyboard or a touch panel, a display apparatus106, such as a cathode ray tube (CRT) or a liquid crystal display, and an external storage apparatus107such as a hard disk apparatus or a Compact Disc Read-Only Memory (CD-ROM), are connected via an interface108to the bus104. In addition, the bus104is connected via a communication unit109to a network110, which may be a telecommunications network which allows computers to exchange data. It is noted that the CPU101executes the processing based on the operating system and the various programs.

FIG. 2illustrates, as a first embodiment, a method200to select a token to describe an entity of interest within a document.FIG. 3illustrates a system300to process a document302into a list of tokens330. At step S210inFIG. 2, the document302ofFIG. 3is input into a set304of named entity recognition (NER) modules. The document302may be a contract for services and/or products, a book, written opinions of judges, the Congressional Record, a transcription of a presentation, or any recorded representation of information, intentions, and/or activities. Typically, the document302will have been passed through an optical character recognition device and be in an electronic form having characters that can be read by the NER module set304. For example, the document302may be Portable Document Format (PDF), Office, or a plain text document.

The NER module set304may include extractors306,308, and310. Extractors306,308, and310are recognizers configured to locate and classify items in the text of the document302into pre-defined categories/fields. Prior to the document302being input to the extractors306,308, and310, extractors306,308, and310are programmed to look in a particular field to locate items in the document text that fall within the given field. For example, the rules of each extractor306,308, and310may be pre-programmed to search the document302for the name of a judge, effective date of the document, or the name of the outside party to a contract where the inside party to the contract is known by the operators of the extractor set304. When the extractors306,308, and310are pre-programmed to look for real world object that can be denoted with a proper name, extractors306,308, and310may be thought of as named entity extractors.

Each extractors306,308, and310may be produced by a different company or have its own unique internal operations. For example, extractor306may be an Apache OpenNLP (natural language processing) module, extractor308may be a Stanford CoreNLP module, and extractor310may be a Reyex natural language processing module. Each model of extractor has strengths and weaknesses that balance precision, noise, and recall. Information extracted by the NER module set304may be used to populate fields in a table that is displayed as a page on the display apparatus106. For example, if a law firm receives hundreds of documents302in reply to a discovery request, each document may be passed through the extractors306,308, and310to obtain text that may be used to populate an electronic intake form for a given document. A goal is to find the most likely and best representative example to populate each field of each intake form.

Passing the document302through each extractor304at step S210results in one or more tokens312-328. The tokens output from the NER module set304are obtained in step S220ofFIG. 2. The particular extractor from the NER module set304assigns each token a confidence score based on how close the extractor304predicts the token is to representing the searched-for field. Since each model of extractor has strengths and weaknesses that balance precision, noise, and recall, one extractor may assign a score to a token that is different from a score assigned by another extractor to that same token.

In an example, suppose the document302is a contract for services between two parties and one of the parties to the contract runs the document302through extractor set304to electronically acquire the name of the outside party to the contract and populate an intake form for that document with the outside party name.FIG. 4is an example output of the NER module set304. The extractors in the NER module set304may use either statistical and/or heuristics methods to extract information from document. After this, the extractor set304to look for the name of the outside party to the contract and passing the document302through extractor set304, the output may be a token set402, a token set404, and a token set406as illustrated inFIG. 4. Since the text of the contract for services may have a variety of named entities that may or may not be a signor of the contract, each token set may include various name entitles. Token set402, for example, includes versions of named entities ABC and XYZ. Each token within the token set402may be assigned a score between 0.0 and 1.0 by the extractor306that represents, in some cases, a probability that the particular token is the name of the outside party to the contract. The extractor306similarly may assign a score to each token in token set404and the extractor308may assign a score to each token in token set406.

At step S230, tokens in each token set402,404, and406are combined into one list of tokens330.FIG. 5illustrates a list of tokens330. The list of tokens330illustrated inFIG. 5includes each token ofFIG. 4associated with the score assigned to the token by the extractor producing the token.

Steps S240through S280of method200inFIG. 2work towards selecting a token from the list of tokens330to describe an item of interest. In the present example, steps S240through S280work towards selecting a token from the list of tokens330that is the most likely and best representation of the name of the outside party to the contract. Steps S240through S280resolve which entities reference the same entity and, of those, which variation is the most appropriate to be returned as the name of the outside party to the contract. That is to say, method200works towards finding which entity string best represents a set of related entities. In addition, rather than be dependent on an external reference such as Wikipedia to find which variation is the most accurate, steps S240through S280are a standalone way to find the most accurate representation of the entity. The returned name of the outside party to the contract then may be use to populate an outside-party-to-the-contract field in a table for display as a page on the display apparatus106.

At step S240, the method200determines whether there are any tokens from the list of tokens330that have not been processed. At step S250, the method200selects two unprocessed tokens from the list of tokens330. As the first selected token, the method200may select a token with the highest score. In the example illustrated inFIG. 5, the token ABC Inc. having 0.9 as a score has a highest score from the list of tokens330and is selected as the first selected token at step S250. Multiple second tokens are selected one at a time as part of an iterative process. The method200determines at step S260whether the two selected tokens are mergeable tokens. As discussed in more detail below, two tokens are considered mergeable if their word tokenized form is a fuzzy sub/super list of one another. Each of the remaining unprocessed tokens will be selected, one at a time, as the second selected token to determine at step S260whether the two selected tokens are mergeable tokens.

FIG. 6is a method600to determine at step S260whether two tokens are mergeable tokens. Tokens are strings spanning one or more words which potentially represent a desired entity to extract. The method600starts at step S602. Recall that tokens are considered mergeable if their word tokenized form is a fuzzy sub/super list of one another. At step S604, the method600determines the word tokenized form of each token—first word token (WT1) and second word token (WT2)—selected at step S250.

The word tokenized form of a token is a list of words which compose that token. In other words, each extracted token (Entity) is represented by a token feature Fiwhich is constructed by tokenizing each token (extracted Entity) into a set of words. For example, the token “San Francisco Stat” is transformed into the list: Fi=[“San”, “Francisco”, “Stat”] and the token “San Francisco State University” is transformed into the list: F2=[“San”, “Francisco”, “State”, “University”]. Along with ABC Inc. selected as WT1, assume that “0.5 ABC” is the second token with score selected at step S250. The word tokenized form for WT1ABC Inc. is [ABC”, “Inc.”] and the word tokenized form for WT2ABC is [“ABC”].

At step S606, the method600determines whether there is a word in the tokenized form for WT1having a position that corresponds to a position of a word in the tokenized form for WT2. In the example with WT1=[“San”, “Francisco”, “Stat”] and WT2=[“San”, “Francisco”, “State”, “University”], the first positioned word “San” in WT1has a corresponding first position word in WT2, namely “San”. In the example with WT1=[ABC”, “Inc.”] and WT2=[“ABC”], the first positioned word “ABC” in WT1has a corresponding first position word in WT2, namely “ABC”.

At step S608, the position corresponding words in WT1and WT2are selected. In step S610, the method600then determines the distances between the two selected words. In one example, step S610utilizes the Levenshtein Distance between the two words to determine an edit distance. The Levenshtein Distance between the two words is the minimum number of single-character edits (i.e. insertions, deletions or substitutions) required to change one word into the other. In the example with WT1=[“San”, “Francisco”, “Stat”] and WT2=[“San”, “Francisco”, “State”, “University”], the Levenshtein Distance between “San” in WT1and “San” in WT2is zero. When the words “Stat” and “State” are reached at step S608, the Levenshtein Distance between “Stat” and “State” determined at step S608is one. In other words, it can be see that both words “San”—“San” and “Francisco”-“Francisco” match exactly. However, “State” and “Stat” do not. Computing the word Levenshtein Distance for “State” and “Stat” finds that the minimum number of single-character edits required to change Stat into State is equal to one. At step S612, the amount determined at step S610is added to an edit distance.

In the example with WT1=[ABC”, “Inc.”] and WT2=[“ABC”], the second positioned word is “Inc.” and there is no second positioned word in WT2. In the example with WT1=[“San”, “Francisco”, “Stat”] and WT2=[“San”, “Francisco”, “State”, “University”], there is no fourth positioned word in WT1whereas “University” is the fourth positioned word in WT2. In other words, WT2has the word token “University” whereas WT2has nothing in the corresponding position. While the Levenshtein Distance between the two tokens “San Francisco Stat” and “San Francisco State University” is twelve, the method600only compares words to position corresponding words since, as discussed below, the method600looks to determine whether word tokenized forms are fuzzy sub/super list of one another. Thus, in this example, the edit distance between “San Francisco Stat” and “San Francisco State University” is one, not twelve.

At step S614, the method600determines whether the determined edit distance between WT1and WT2is less than a predetermined number. If the determined edit distance between WT1and WT2is less than a predetermined number, the two strings are defined at step S616as being fuzzily equal. In other words, two strings are defined as being fuzzily equal if their Levenshtein Distance excluding added tokens is below a configurable number. This number may be relative to the minimum length of the two strings.

In the above examples, the word Levenshtein Distance between words in WT1=[ABC”, “Inc.”] and WT2=[“ABC”] is zero and the word Levenshtein Distance between words in WT1=[“San”, “Francisco”, “Stat”] and WT2=[“San”, “Francisco”, “State”, “University”] is one. If WT1=[ABC”, “Inc.”] and WT2=[“MNO”, “Corp”], the word Levenshtein Distance between the words in each token seven. If the determined edit distance between WT1and WT2is not less than the predetermined number (NO at step S614), the method proceeds to step S618where WT1and WT2are determined not to be mergeable tokens.

Recall that tokens are considered mergeable if their word tokenized form is a fuzzy sub/super list of one another. At step S620, the method600determines whether WT1is a fuzzy sublist of WT2. If not, then the method600determines at step S622whether WT1is a fuzzy superlist of WT2. Tokens are fuzzy sub/super lists of one another if their word tokenized forms are fuzzy sub/super sets of one another. In the case where WT1=[“San”, “Francisco”, “Stat”] and WT2=[“San”, “Francisco”, “State”, “University”], WT1is a fuzzy sublist of WT2since only the word “University” is missing from WT1. In the case where WT1=[ABC”, “Inc.”] and WT2=[“ABC”], WT1is not a fuzzy sublist of WT2(NO at step S620). However, WT1not a fuzzy superlist of WT2(YES at step S622) since only the word “Inc.” is missing from WT2.

If, after determining at step S616that WT1and WT2are fuzzily equal to each other and determining at step S620that WT1is not a fuzzy sublist of WT2, it is determined at step S622that WT1and WT2are not fuzzy super lists of one another, then it is determined at step S618that WT1and WT2are not mergeable tokens. When it is determined at step S618that two tokens are not mergable tokens, it is determined at step S260ofFIG. 2that the two tokens are not mergable tokens. The method200then proceeds from step S260inFIG. 2to step S240. At step S240, another unprocessed token is selected and, at step S250, the token is selected as the next WT2to be processed with WT10.9 ABC Inc. The token with score 0.9 ABC Inc. eventually is processed with each token with score inFIG. 5.

If, after determining at step S616inFIG. 6that WT1and WT2are fuzzily equal to each other, it is determined at step S620or step S622that WT1and WT2are sub/super lists of one another, then it is determined at step S624that WT1and WT2are mergeable tokens. If it is determined at step S624that WT1and WT2are mergeable tokens, then it is determined at step S260ofFIG. 2that WT1and WT2are mergeable tokens. The method200then proceeds to step S270ofFIG. 2.

At step S270, WT1and WT2are merged. Once it is determined that two tokens should be merged, determining how to do so is critical to the goal of finding the token which best describes the sought after entity name. In order to merge two tokens at step S270, the score given to each token by the extractor producing the token is utilized in that the token with the highest score prevails. For example, if the first token is “ABC Inc.” with the score of 0.9 given by the extractor306and the second token is “ABC” having the score of 0.5 given by the extractor310, “ABC” is absorbed into “ABC Inc.” since 0.5 is less than 0.9 so that only “ABC Inc.” remains out of the two. The 0.5 score of the token “ABC” is then added to the 0.9 score of “ABC Inc.” to give the token “ABC Inc.” a score of 1.4. To resolve ties where the score of WT1and WT2are the same, three configurable options are available. For example, either the token with the most number of characters prevails, or the shorted token prevails, or a random picking happens. If both tokens are the same length, one token is picked at random and the other token is merged into the picked token.

From step S270, the method200returns to step S240.FIG. 5illustrates nine tokens. Eventually, all nine tokens are processed as the first token WT1and compared with the remaining tokens serving as the second token WT2. In an example, the tokens 0.3 ABBC, 0.9 ABC Inc., 0.4 ABC Ltd, and 0.5 ABC may be merge into the token ABC Inc. with a score of 2.1 (=0.3+0.9+0.4+0.5) for the token ABC Inc. The tokens 0.6 MNO and 0.5 MNO Corp may be merged into the token MNO and assigned a score of 1.1 for the token MNO and the tokens 0.5 XYZ Ltd, 0.2 XYZ, and 0.9 XYZ Inc. may be merged into the token XYZ Inc. and assigned a score of 1.6 for the token XYZ Inc.

After the method200determines at step S240that there are no unprocessed tokens, the method proceeds to step S280. At step S280, the method200selects a token to describe an entity of interest. In the present example, the method200selects the one token that most likely is the name of the outside party to the contract. In reviewing the choices between 2.1 ABC Inc., 1.6 XYZ Inc., and 1.1 MNO, the method600selects ABC Inc. as the name of the outside party to the contract since its score of 2.1 is greater than the remaining scores of 1.6 and 1.1.

The approach of the first embodiment above has several benefits. For example, the method200automatically figures out which string best represents a desired entity type in contrast to the conventional art, which does not. Moreover, the method200can figures out which string best represents a desired entity type by using a combination of NER models. This allows for approaching entity extraction with numerous techniques.

According to a second embodiment, an example is presented to select a token from a document to describe an entity of interest in that document.FIG. 7illustrates, as a second embodiment, a method700to select a token to describe an entity of interest. The ranking by the method700involves (i) clustering tokens extracted by various NER models into sets based on their similarity to each other, (ii) ranking the resulting cluster sets based on scores of tokens that are members of that set, and (iii) choosing a representative token from one of the cluster sets. The second embodiment improves the accuracy of predicting the correct “Party to Contract” named entity over the first embodiment.

Method700has steps in common with the method200ofFIG. 2to output a list of tokens, such as the list of tokens illustratedFIG. 5. At step S210inFIG. 7, the document302ofFIG. 3is input into a set304of named entity recognition (NER) modules. The tokens output from the NER module set304are obtained in step S220inFIG. 7. The particular extractor304assigns each token a confidence score based on how close the extractor304predicts the token is to representing the searched-for field. At step S230inFIG. 7, tokens in each token set402,404, and406ofFIG. 4are combined into one list of tokens330as illustrated inFIG. 5. Similar to step S604ofFIG. 6, step S708of the method700determines the word tokenized form of each token, where the word tokenized form of a token is a list of words which compose that token.

The method700determines at step S710the frequency with which each word in the list of tokens330appears in the list of tokens330.FIG. 8illustrates the frequency with which each word in the list of tokens330appears in the list of tokens330. Within the nine tokens in the list of tokens330, there are fourteen words. As illustrated inFIG. 8, seven of the fourteen words in the list of tokens330are unique to the list of tokens330. For example, the word ABBC appears once among the fourteen words, the word ABC appears three times, and the word Inc. appears twice. The frequency with which each of the seven words appears in the list of tokens330is determined by dividing the number of times the word appears in the list of tokens330by the total number of words in the list of tokens330. For example, the frequency of the word ABBC in the list of tokens330is one divided by fourteen, or 0.07.

In order perform clustering, a distance measure needs to compute the similarity (actually dissimilarity) between two tokens. The distance measure of the second embodiment takes into account the text-similarity as well as individual token's term frequencies.

The method700determines at step S712the token score for each token in the list of tokens330.FIG. 9illustrates the token score for each token in the list of tokens330. A token score is calculated by summing up scaled weights of a given token's words as determined by equation (i) below:

TokenScore⁡(TSk)=∑i=1length⁢w⁢⁢fii*W(i)
where length is the number of words in the token, wfiis the word frequency weight for a given word, i is the location or position of a particular word within the given token, and w is the score/weight for a particular token assigned by the extractor306, the extractor308, or the extractor310ofFIG. 4. The token score determined by equation (i) is designed to give a higher score to tokens that have words that occur more frequently, tokens starting with a higher weighted word (wfi), tokens of greater length, and tokens with a higher score (w).

After step S712, the method700proceeds to step S714. At step S714, the method700determines the distance between each token. In one example, step S714may utilize any distance measure such as Levenshtein Distance, Cosine Similarity, etc., to determining a distance between two tokens. However, the inventors determined a custom distance measure that produces higher quality results.

FIG. 10is a method1000to determine the distance between two tokens in step S714ofFIG. 7.FIG. 11illustrates a result of performing method1000on the tokens in the list of tokens330inFIG. 5to determine the distance between two tokens. Distance determined in step S714is dependent on two circumstances. Where there are words in common between the two tokens selected in step S1002, the distance is expressed by equation (ii) below as a ratio of different to common word weights:
Distance(WTi,WTj)=(different)/(common)  (ii)
where “different” is a sum of word weights that are different between tokens and “common” is a sum of word weights that are in common between tokens. Both common measure and different measure take into account word sequence/order as well as occurrence of words in the tokens being compared into account. If there are no words in common between the two tokens selected in step S1002, the distance is expressed as the different word weights multiplied by a constant C (for example C=100):
Distance(WTi,WTj)=(different)  (iii)

The method1000ofFIG. 10begins at step S1002where two tokens are selected from the list of tokens330—first word token (WT1) and second word token (WT2). At step S1004, the method1000determines the word tokenized form of each token WT1and WT2selected at step S1002. The processing at step S1004is similar to the process performed at step S604ofFIG. 6. At step S1006, the method1000determines whether there is a word in the tokenized form for WT1having a position that corresponds to a position of a word in the tokenized form for WT2. The processing at step S1006is similar to the process performed at step S606ofFIG. 6.

In the present embodiment, assume, as a first example chosen at step S1002, that WT1is ABC Ltd and WT2is ABC Inc. As a second example chosen at step S1002, assume that WT1is MNO Corp and WT2is ABBC as in Table I below.

If it is determined at step S1006that there is a word in the tokenized form for WT1having a position that corresponds to a position of a word in the tokenized form for WT2(YES at step S1006), the method1000proceeds to step S1008. At step S1008, the method1000determines, word-by-word, whether the word in WT1whose position corresponds to the word in WT2equal each other. In the first example where WT1is ABC Ltd and WT2is ABC Inc., “ABC” in WT1matches “ABC” in WT2. That is, “ABC” in WT1is in common with “ABC” in WT2. Where the word in WT1that corresponds to the word in WT2equal each other (YES at step S1008), the method1000proceeds to step S1010. At step S1010, the word frequency value of each common word is added to an intermediate common total. Here, the word frequency value for the word “ABC” indicated inFIG. 8as 0.21 (= 3/14). The word frequency value 0.21 for “ABC” in WT1and the word frequency value 0.21 for “ABC” in WT2are added to the intermediate common total for a value of 0.42 (=0.21+0.21).

Where the word in WT1that corresponds to the word in WT2do not equal each other (NO at step S1008), the method1000proceeds from step S1008to step S1012. At step S1012, the word frequency value of each word is added to an intermediate difference total.

The method1000returns from step S1010and step S1012to step S1006. In the first example where WT1is ABC Ltd and WT2is ABC Inc., the second positioned word “Ltd” in WT1corresponds to the second position word “Inc.” in WT2, again resulting in YES at step S1006for the first example. However, “Ltd” and “Inc.” are not equal. That is, “Ltd” in WT1is different from “Inc.” in WT2(NO at step S1008). Here, the word frequency value for the word “Ltd” listed inFIG. 8, 0.14 (=2/14), and the word frequency value for the word “Inc.”, 0.14 (=2/14), are added to the intermediate difference total at step S1012, giving an intermediate difference total of 0.28 (=0.14+0.14) and, from above, an intermediate common total of 0.42 for the first example. From step S1012, the first example where WT1is ABC Ltd and WT2is ABC Inc. is processed at step S1006for a third time. Since WT1and WT2do not have a word in the third position of their tokens, the method1000proceeds from step S1006to step S1014(NO at step S1006).

In the second example where WT1is MNO Corp and WT2is ABBC, WT1position one word “MNO” is not equal to WT2position one word “ABBC” (NO at step S1008). That is, “MNO” in WT1is different from “ABBC” in WT2. Here, the word frequency value for the word “MNO” listed inFIG. 8, 0.14 (=2/14), and the word frequency value for the word “ABBC”, 0.07 (= 1/14), are added to the intermediate difference total at step S1012to give a value of 0.21 (=0.14+0.07). From step S1012, the second example where WT1is MNO Corp and WT2is ABBC is again processed at step S1006. While WT1has a word in position two, “Corp”, WT2does not have a position two word that corresponds to “Corp”. Accordingly, the method1000proceeds from step S1006to step S1014(NO at step S1006).

On entering step S1014, the intermediate totals for the two examples are in Table II below:

The above step S1006through step S1012took into account the sequence/order of each word in each token on a word-by-word basis and the length of each token. Irrespective of the order and length regarding the tokens, steps S1014and S1016look at the words in common and the words that are different between the two tokens selected in step S1002.

At step S1014, the method1000obtains a common total by adding one word-frequency-value to the intermediate common total for words in WT1and WT2that are equal. In the first example where WT1is ABC Ltd and WT2is ABC Inc., the tokens have “ABC” in common. FromFIG. 8, the frequency value for “ABC” is 0.21 (= 3/14). Thus, 0.21 is added to the intermediate common total of 0.42 to give 0.63 (=0.42+0.21) as the common total for the first example. At step S1016, the method1000obtains a difference total for the two tokens being processed by adding a word frequency value to the intermediate difference total for each word in WT1and WT2that are not equal. In the first example where WT1is ABC Ltd and WT2is ABC Inc., the tokens have “Ltd” and “Inc.” as different words. The frequency value for “Ltd” (0.14—seeFIG. 8) and “Inc.” (0.14) are added at step S1016to the intermediate difference total of 0.28 so that the difference total becomes 0.56 (=0.28+0.14+0.14).

Processing the second example for WT1and WT2through steps S1014and step S1016, WT1and WT2for the second example have no words in common and three words that are different: “MNO”, “Corp”, and ABBC”. Adding 0.14, 0.07, and 0.07 to 0.21 results in a difference total of 0.49 (0.50when rounded up). The resulting Totals are in table III below:

After proceeding from step S1014to step S1016, the method1000proceeds from step S1016to step S1018. At step S1018, the method1000determines whether the common total is zero. If the common total is zero, then none of the words in the two tokens selected in step S1002are in common. In such a case, it is desirable that the distance between the two words be great to lessen their influence on the ultimate selection of a token to describe an entity of interest at step S722inFIG. 7. If the common total is not zero, then it is important that the distance between the two words have more of an influence on the ultimate selection of a token to describe an entity of interest at step S722inFIG. 7.

If the common total is not equal to zero (NO at step S1018), then the method1000proceeds to step S1020. At step S1020, the distance between the two tokens selected at step S1002is equal to the ratio of the difference total to the common total:
Distance(WTi,WTj)=(different)/(common)  (ii)
In the first example where WT1is ABC Ltd and WT2is ABC Inc., the distance between ABC Ltd and ABC Inc. is determined to be 0.89 (=0.56/0.63). The value of 0.89 appears inFIG. 11where ABC Ltd and ABC Inc. intersect.

If the common total is equal to zero (YES at step S1018), then the method1000proceeds to step S1022. At step S1022, the distance between the two tokens selected at step S1002is equal to the difference total times a constant C (for example, C=100):
Distance(WTi,WTj)=(different)  (iii)
In the second example where WT1is MNO Corp and WT2is ABBC, the distance between MNO Corp and ABBC is determined to be 50.00 (=(0.50)*100). The value of 50.00 appears inFIG. 11where MNO Corp and ABBC intersect.

The method1000proceeds from step S1020and step S1022to step S1024. At step S1024, the method1000determines whether there are any tokens within the list of tokens330that have not yet been processed by the method1000. In this way, method1000determines whether any of the distance values of those inFIG. 11have yet to be determined.

If there are tokens within the list of tokens330that have not yet been processed by the method1000(YES at step S1024), the method1000returns to step S1002inFIG. 10. If all the tokens within the list of tokens330have been processed by the method1000(NO at step S1024), the method1000, and step S714where the distance between each token is determined, ends. From step S714, the method700ofFIG. 7proceeds to step S716.

At step S716, the method700clusters each of the tokens in the list of tokens330into one or more groups. To achieve this, the method700uses an iterative bisecting clustering process to cluster extracted tokens based on their similarity. The process relies on a token-to-token distance measure determined at step S714.

FIG. 12is a method1200to clusters each of the tokens in the list of tokens330into one or more groups as part of step S716ofFIG. 7. At step S1202, the method1200determines plot points for each token that may be used to plot each token on a graph. In a simple example, points may be plotted on a two-dimensional graph where the set of tokens330includes only two unique words. In the present example, the list of tokens330includes seven unique words: ABBC, ABC, CORP, Inc., Ltd, MNO, and XYZ. Here, each of the nine tokens is located on a seven-dimensional graph.

FIG. 13illustrates the plot points for the tokens in the list of tokens330. The top row contains the seven unique words in the list of tokens330as seven dimensions. The left-most column contains each of the nine tokens. A frequency value fromFIG. 8representing the frequency of a word in the list of tokens330is place at a grid reference where one of the words in the token in the left-most column matches a dimension word in the top-most row ofFIG. 13. For example, in the first token row ABBC, the frequency value of 1/14 is placed at the grid reference ABBC-ABBC and zero is placed at the remainder of grid references, giving a plot point coordinate for ABBC of ( 1/14, 0, 0, 0, 0, 0, 0). For the fourth token row ABC Ltd, 3/14 is placed at the ABC Ltd-ABC grid reference representing the frequency value of ABC and 2/14 is placed at the ABC Ltd-Ltd grid reference representing the frequency value of Ltd. This giving a plot point coordinate for ABC Ltd of (0, 3/14, 0, 0, 2/14, 0, 0). Since there are nine tokens in the list of tokens330, there are nine plot points.

The method1200proceeds from step S1202to step S1204. At step S1204, the method1200chooses two plot points from the nine plot points and identifies each of the two chosen plot points as a center. Here, the centers are chosen from the available points rather than using calculated average points. At step S1206, all remaining plot points are assigned to one of the two centers. This splits the set of tokens into two groups. At step S1208, the k-medoids algorithm is used in an iterative process to bisect all the tokens into the two most compact clusters.

The k-medoids algorithm is a clustering algorithm that breaks a dataset up into groups (partitional) to minimize the distance between points labeled to be in a cluster and a point designated as the center of that cluster. The k-medoids algorithm chooses datapoints as centers (medoids or exemplars) and works with an arbitrary metrics of distances between datapoints. As a partitioning technique of clustering, the k-medoids algorithm clusters the data set of n objects into k clusters known a priori. The k-medoids algorithm is robust to noise and outliers because it minimizes a sum of pairwise dissimilarities.

From step S1208, the method iteratively passes through step S1204, step S1206, and step S1208until all the tokens of the list of tokens330are clustered into the two most compact groups. Once it is determined that all the tokens are clustered into the two most compact groups, the method1200proceeds from step S1206to step S1210. At step S1210, a center of each of the two groups is determined. At step S1212, the method1200determines the compactness of each group.

Compactness is a measure of how closely and firmly the tokens in a cluster are united or packed together within a space. If the determined compactness of a group is below a threshold, then the tokens within that group are sufficiently compact to be representative of the same entity of interest. Intra-Cluster distance may measure compactness where the sum of the distances of the objects within the same cluster is minimized. In one example, the distance of the farthest cluster member point is used to determine how well does the cluster center represent its member points. In another example, the method1200uses the isoperimetric quotient—the ratio of the area of the shape to the area of a circle (the most compact shape) having the same perimeter—to determine compactness of a group of tokens.

The method1200proceeds from step S1212to step S1214. At step S1214, the method1200determines whether there is any unprocessed group. Here, there are two groups and each group is process one at a time.

If there is an unprocessed group (YES at S1214), then the method1200proceeds from step S1214to step S1216. At step S1216, the method1200determines whether the compactness for a given group determined at step S1212is less than a predetermined compactness threshold. The predetermined compactness threshold may be a value, relevant to the technique used to calculate compactness at step S1212, below which a group may be deemed sufficiently compact.

If the compactness for a given group is less than the predetermined compactness threshold (YES at step S1216), the method1200proceeds to step S1218. At step S1218, the determined compact group is added to a ready-queue as a token cluster having tokens that are deemed to be representative of the same entity of interest. In other words, if compactness is below a threshold, then the cluster (token center+token points) is added to the ready-queue. The method1200returns from step S1218to step S1214to determine whether there are any unprocessed groups.

If the compactness for a given group is equal to or greater than the predetermined compactness threshold (NO at step S1216), the method1200proceeds from step S1216to step S1220. At step S1220, the determined uncondensed group is added to a split-queue as a cluster having tokens that are deemed not to be representative of the same entity of interest. This uncondensed group will be returned to processing at step S1204to eventually be split into two new groups whose compactness is compared to the predetermined compactness threshold at step S1216.

If it is determined at step S1214that there are no more unprocessed groups (NO at step S1214), the method1200proceeds to step S1222. As step S1222, the method700ofFIG. 7proceeds from step S716to step S718. At step S718, a cluster score is determined for each cluster. Other termination conditions for method1200can be used, such as stopping the splitting when a predetermined number of clusters have been calculated.

FIG. 14illustrates token clusters added to the ready-queue at step S1220and the score for each cluster. The processing of method1200coalesced the nine tokens of the list of tokens330into four token clusters: (i) ABBC, (ii) ABC, ABC Inc., ABC Ltd, (iii) MNO, MNO Corp, and (iv) XYZ, XYZ Inc., XYZ Ltd. The center for each group is chosen as indicated by a “C=” inFIG. 14. For group No. (ii) for example, ABC was chosen as the center since the word is the most common out of all the words in the tokens in that token cluster.

Once the all of the tokens have been clustered at step S716ofFIG. 7using the proposed distance measure, each cluster is scored at step S718in order to produce a ranked list of resolved Entities. The cluster score at step S718may be determined using the following:

ClusterScore⁡(C⁢⁢S)=∑i=1count⁢TokenScore⁡(TSi⁢)(1+Distance⁡(T,C))(iv)
where the count represents one for each token in the token cluster, the TokenScore is the score for each token fromFIG. 9, and the Distance (Dist) is the distance between a token T and the center token C of the token cluster fromFIG. 11. Here, a particular cluster score is calculated by summing up all of the token scores of the tokens belonging to a particular cluster, which are scaled by their distance from the center. The determined score for each of the four token clusters is as illustrated inFIG. 14.

Once all of the clusters have been scored in step S718, the next steps are to rank the clusters and choose the best representing feature token or (extracted Entity) to represent the cluster. From step S718ofFIG. 7, the method700proceeds to step S720to rank the clusters based on their cluster scores. In the example using the list of tokens330inFIG. 5, token cluster (ii) ofFIG. 14has the cluster score of 0.41, which is the largest of the four cluster scores. In the example, the ranking of the token clusters is (ii), (iv), (iii), and then (i).

From step S720, the method700proceeds to step S722. At step S722, the best representative token in each token cluster to describe an entity of interested is selected. One approach is to choose the cluster center (C). However, choosing a highest ranked token (highest score/count) from the set of tokens belonging to a particular cluster produced better results. In this example, ABC Inc. received a score of 0.9 from extractor306(FIG. 4), ABC received a score of 0.5 from extractor310, and ABC Ltd received a score of 0.4 from extractor308. With a score of 0.9, ABC Inc. is chosen at step S722to be the token to describe token cluster (ii). In the example, the ranked entity of interest recommendation result is 1) ABC Inc., 2) XYZ Inc., 3) MNO, and 4) ABBC. In this case, the entity of interest is the outside party to a contract (where the inside party to the contract is known by the operators of the extractor set304). This ranked result may be displayed to a user in a pull-down menu. As the highest ranked entity of interest recommendation, a user may select ABC Inc. to populate the field “Outside Party to Contract” field in a table that is displayed as a page on the display apparatus106or the field automatically be populated by the highest ranked entity of interest recommendation.

In the example methods for picking “best” Named Entity given a set of extracted entities extracted from single or multiple named entity extractors, some embodiments use one or more functional units to implement the above-described devices, systems, and methods. The functional units may be implemented in only hardware (e.g., customized circuitry) or in a combination of software and hardware (e.g., a microprocessor that executes software). Moreover, the scope of the claims is not limited to the above-described embodiments and includes various modifications and equivalent arrangements. In addition, as used herein, the conjunction “or” generally refers to an inclusive “or,” though “or” may refer to an exclusive “or” if expressly indicated or if the context indicates that the “or” must be an exclusive “or.”