Source: http://www.google.com/patents/US20080005094?ie=ISO-8859-1
Timestamp: 2015-07-28 01:50:46
Document Index: 746470839

Matched Legal Cases: ['arth 700', 'arth 700', 'arth 700', 'arth 700', 'arth 700', 'arth 700', 'arth 700', 'arth 700', 'arth 700', 'arth 810', 'arth 800', 'arth 800', 'arth 800', 'arth 800', 'arth 800']

Patent US20080005094 - Method and system for finding the focus of a document - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsA method and apparatus for identifying the focus of a document, in a natural language processing application, the natural language processing application comprising a hierarchical concept tree having a plurality of nodes, each node being associated with a term, the method comprising the steps of: mapping...http://www.google.com/patents/US20080005094?utm_source=gb-gplus-sharePatent US20080005094 - Method and system for finding the focus of a documentAdvanced Patent SearchPublication numberUS20080005094 A1Publication typeApplicationApplication numberUS 11/696,279Publication dateJan 3, 2008Filing dateApr 4, 2007Priority dateJul 1, 2006Also published asUS7953754Publication number11696279, 696279, US 2008/0005094 A1, US 2008/005094 A1, US 20080005094 A1, US 20080005094A1, US 2008005094 A1, US 2008005094A1, US-A1-20080005094, US-A1-2008005094, US2008/0005094A1, US2008/005094A1, US20080005094 A1, US20080005094A1, US2008005094 A1, US2008005094A1InventorsKevin Cunnane, Emma Curran, Jan Macek, Daniel McCloskey, Brendan Moorehead, Ross Shannon, Alexander TroussovOriginal AssigneeKevin Cunnane, Emma Curran, Jan Macek, Mccloskey Daniel, Brendan Moorehead, Ross Shannon, Alexander TroussovExport CitationBiBTeX, EndNote, RefManReferenced by (9), Classifications (6), Legal Events (2) External Links: USPTO, USPTO Assignment, EspacenetMethod and system for finding the focus of a document
US 20080005094 A1Abstract
1. A method for identifying the focus of a document, in a natural language processing application, the natural language processing application comprising a hierarchical concept tree having a plurality of nodes, each node being associated with a term, the method comprising the steps of:
mapping an input document to nodes in a concept tree to determine a number of occurrences of a term in the input document which also occur at a node in the concept tree; weighting each node in the concept tree, depending on the determined number of occurrences of the term in the input document and a determined value assigned to each node in the concept tree; traversing the concept tree to identify a heaviest weighted path, in dependence on the weighting of each node in the concept tree; and determining the focus of the input document by identifying a node having the heaviest weight along the most heavily-weighted path. 2. The method as claimed in claim 1 wherein the determining step further comprises determining if the determined focus is too specific for the input document and on a positive determination identifying a specific focus of the input document by identifying a node having a value which is less than the sum of the node's child nodes.
8. An apparatus for identifying the focus of a document, in a natural language processing application, the natural language processing application comprising a hierarchical concept tree having a plurality of nodes, each node being associated with a term, the apparatus comprising:
a scanning component for mapping an input document to nodes in a concept tree to determine a number of occurrences of a term in the input document which also occur at each of the nodes in the concept tree; a determining component for weighting each node in the concept tree, depending on the determined number of occurrences of the term in the input document and a determined value assigned to each node in the concept tree; a determining component for traversing the concept tree to identify a heaviest weighted path, in dependence of the weighting of each node in the concept tree; and a determiner component for determining the focus of the input document by identifying a node having the heaviest weight along the most heavily weighted path. 9. The apparatus as claimed in claim 8 wherein the determining component further comprises determining if the determined focus is too specific for the input document and on a positive determination identifying a specific focus of the input document by identifying a node having a value which is less than the sum of the node's child nodes.
10. The apparatus as claimed in claim 8 wherein the determiner component further comprises incrementing a weight count at each node, each time a term in the input document is mapped to a node in the concept tree.
11. The apparatus as claimed in claim 8 wherein the determiner component further comprises identifying an ambiguous term in the input document, by mapping the term in the input document to a plurality of nodes in the concept tree.
12. The apparatus as claimed in claim 8 wherein the determiner component further comprises performing a depth first search to identify the node along a weighted path having the heaviest weight when traversing the concept tree.
13. The apparatus as claimed in claim 8 wherein the determiner component on traversing the concept tree to identify the focus, and on determining more than one focus, the determiner component further comprises determining whether the determined weights of each of the focus nodes differ by a threshold value and, on a positive determination, traversing each of the focus node's paths until another focus node is identified.
14. The apparatus as claimed in claim 8 wherein if the determiner component traverses the concept tree and identifies the focus as a node which only has a weight of the sum of its child node, the determiner component continues to traverse the remainder of the node's path to find an alternative focus.
a central processing unit; and a computer readable medium for storing the scanning component for mapping an input document to nodes in a concept tree, the determining component for weighting each node in the concept tree, the determining component for traversing the concept tree, and the determiner component for determining the focus of the input document. 16. A computer program product, wherein said computer program product includes a computer readable storage medium, said computer readable storage medium having computer program code recorded thereon for identifying the focus of a document, in a natural language processing application, the natural language processing application comprising a hierarchical concept tree having a plurality of nodes, each node being associated with a term, wherein said program code, when executed, would cause a computer system to:
map an input document to nodes in a concept tree to determine a number of occurrences of a term in the input document which also occur at a node in the concept tree; weight each node in the concept tree, depending on the determined number of occurrences of the term in the input document and a determined value assigned to each node in the concept tree; traverse the concept tree to identify a heaviest weighted path, in dependence on the weighting of each node in the concept tree; and determine the focus of the input document by identifying a node having the heaviest weight along the most heavily-weighted path. 17. A system for identifying the focus of a document, in a natural language processing application, the natural language processing application comprising a hierarchical concept tree having a plurality of nodes, each node being associated with a term, comprising:
means for mapping an input document to nodes in a concept tree to determine a number of occurrences of a term in the input document which also occur at a node in the concept tree; means for weighting each node in the concept tree, depending on the determined number of occurrences of the term in the input document and a determined value assigned to each node in the concept tree; means for traversing the concept tree to identify a heaviest weighted path, in dependence on the weighting of each node in the concept tree; and means for determining the focus of the input document by identifying a node having the heaviest weight along the most heavily-weighted path. Description
Using knowledge organized in hierarchical structures is useful for text analysis. In computer applications this knowledge is often modeled by graphs—networks of interconnected concepts. For example, geographical locations lend themselves to be easily organized into a hierarchical tree—a “concept tree”—where each city has a parent country, which has a parent continent, and so on, all the way up to a common root element. Similarly, employees in an organization can be arranged into a hierarchical management structure, where managers themselves have managers and a list of subordinates.
The example of geographic focus is used throughout this document to illustrate a type of clearly-defined focus which can be expressed in hierarchical form. However, this should not be construed as limiting the scope of this disclosure and is merely used as an example of a type of focus. The types of focus are wide-ranging and include any topic which can be expressed in a hierarchy; for example an employee's reporting structure. To accomplish the goal of determining the focus of a document, an understanding of the topics in a document is needed. This is usually inferred from an analysis of the words used in the document, performed by some form of Natural Language Processing. However, words are ambiguous and the same word or term might refer to different concepts. In the case of geographic topics, confusion can arise if there exists several places in the world with the same name, or where a place name is also a common word or an individual's name, etc. For example, when finding the geographic focus of a document, if we take the term ‘Dublin’; it is known that there are multiple locations in the world with the name ‘Dublin’ and thus the term ‘Dublin’ may be confusing and the ambiguity caused by this needs to be resolved—i.e. the term needs to be disambiguated.
To do this, a data mining algorithm parses a document and maps each term in the document to a pre-existing concept tree in order to find the focus of the document. A graph clustering algorithm establishes the central concept of the document i.e. that a central concept or focus of the document is of a geographical nature. Next any ambiguous terms i.e. where there are occurrences of the terms like ‘Dublin’, or ‘Galway’, must be resolved—i.e. are the terms ‘Dublin’ and ‘Galway’ referring to the cities in Ireland or those in the U.S.A? The step of resolving ambiguous terms based on the metric of their theoretical similarity to the document's focus is called term disambiguation.
There are a number of known prior art methods for finding the focus of a document and for providing term disambiguation. However, normally different methods are suggested for the tasks of finding the focus of a document and term disambiguation—please refer to Wu and Palmer, 1994 “(Verb semantics and lexical selection”, 32nd Annual meeting of the Association for Computational Linguistics, Las Cruces, N. Mex., 1994, pp. 305-332) and Leacock and Chodorow 1998 “(Combining local context and WordNet similarity for word sense identification”, In C. Fellbaum (Ed.), Wordnet: An electronic lexical database, MIT Press 1998, pp. 265-283).
FIGS. 3 a and 3 b are tree diagrams illustrating two types of hierarchical tree structures—a geographical taxonomy and a file system hierarchy;
The scanning component 225 scans an input document 200 to identify instances of term references in the form of words or phrases. For each instance located, this occurrence is recorded in a concept tree 220. A concept tree 200 is a hierarchical data structure comprising nodes, in the form of a root node 300 and a number of internal or leaf nodes 305, 310—the totality of the nodes comprising a hierarchical taxonomy.
Two types of hierarchical taxonomies are shown in FIGS. 3 a and 3 b. As previously explained a concept tree 220 comprises a root 300 i.e. the high level classifier —geography in FIG. 3 a and email folders in FIG. 3 b. From the root a number of branches are provided in which nodes exist 305. Each branch comprises a level, for example, countries in FIG. 3 a and high level activities in FIG. 3 b. Each branch results in an internal node, for example England, Ireland, Scotland and Wales in FIG. 3 a and Commercial, Free time and studies in FIG. 3 b. From each level of nodes 305, a further level of branches may exist, each branch having further child nodes 310, and each increasing in specificity. For example, in FIG. 3 a, there are further branches i.e. cities and post codes etc each level having further nodes. The same idea is shown in FIG. 3b wherein from the level of high level activities branch into levels of categories of the high level activities and so on. Each concept tree 220 may have many hundreds if not thousands of nodes 305, 310.
On the scanning component's 225 first pass of the document 200 it records each occurrence of a term in the document 220 that also appears in the concept tree 220. For example, using the example of FIG. 3 a the scanning component 225 scans the document 200 and parses the term ‘England’; if the term ‘England’ also appears in the geographical concept tree 220, the scanning component 225 increments a counter on each node 305 that represents the term ‘England’ in the concept tree.
Once the scanning component 225 has completed this process for every term in the document 200, the determiner component 230 determines weights to be added to each occurrence of each term in the concept tree 220—this is the first step of term disambiguation.
For example, if the term ‘Dublin’ appeared in the concept tree 220 five times—each of these nodes would have a one in five probability of being the ‘correct’ Dublin. Hence the determiner component 230 assigns a weighting of ⅕ to each occurrence of the term ‘Dublin’ in the concept tree 220, as they are ambiguous nodes. However, if an instance of a term only appeared once in the concept tree 220, the node representing the instance of the term is assigned a weighting of one and would be classed as an unambiguous node with a weighting of one.
Each mention of a term in the document 200 raises those nodes' weights by this same amount, so that if ‘Dublin’ was mentioned twice in the document 200, each node that represented the concept of ‘Dublin’ will have a weight of ⅖. This additional weighting means that geographic locations (or employees etc.) that are mentioned more often will have greater bearing on the document's eventual computed focus.
Taxonomies typically produce a ‘tree-shaped’ hierarchy which allow
Given a tree and a node ‘a’ in the tree, the set of all nodes which have
‘a’ as ancestor represents a tree structure; this is called the subtree
A node. We use this variable in the algorithm for finding the “focus”
“weight” of the node
Subtree weight - “weight” of the subtree rooted in a, (the sum of
“Generalization force” - function used by algorithms. Relations
“gravitation” force which pushes focus from the root to more specific
concepts, while function U(a) prevents “over-specification” by pulling
if there is unambiguous mapping from mention in text to the node a, then w(a)+=1
if a mention of a term in a document 200 corresponds to n ambiguous nodes in the concept tree 220, then w(a)+=1/n This occurs when there is more than one instance of a term in the concept tree 220.
The operational steps of the focus determining algorithm can be explained as followed. Computing the focus position on the concept tree 220 is a multi-step process. To begin, the focus is placed at the root node 300 (the most general concept). Then, the focus determining algorithm 210 continuously moves the focus down the tree following the “heaviest path”. More specifically, the focus determining algorithm 210 works in iterations moving the focus from a parent node 300 to its child node 305 with the biggest value of specification force W. This process allows it to find most specific concepts mentioned in the document 200.
However, finding the most specific concepts is not always the goal, some generalization is beneficial. At each step in the focus-finding process, the decision to move the focus further from the root 300, narrowing to a particular subtree of interest, is taken by comparing the “specification force” W(node) with “the generalization force” U(node) for that node.
The focus will come to rest on a node 305, 310 when all of its children's U(node) value is greater than their W(node) property. The above concepts will be explained further with reference to FIGS. 4, 5, 6 and 7—each of these figures should be read in conjunction with the others.
The focus determining component 210 begins by taking a text document 200 as input. The text document 200 comprises words making up two paragraphs of text as shown in FIG. 6. The scanning component 225 begins by scanning (step 900 of FIG. 9) the text document 200 and identifies the text document 200 having a geographical focus and requests the requester component 235 to retrieve a geographical concept tree (step 905). The scanning component 225 scans the document 200 for geographical terms and each time the scanning component 225 locates a geographical term it increments a counter in the concept tree 220 for each occurrence of the term. For example, taking the document 200 of FIG. 5, the scanning component 225 scans the document 200 and locates the term ‘Dublin’. The scanning component 225 then performs a lookup in the concept tree 220 (FIG. 6) and determines that the term ‘Dublin’ appears twice and increments a counter for each node with the term ‘Dublin’.
Next the scanning component 225 locates the term ‘Ireland’ and again performs a lookup in the concept tree 220 of FIG. 6 to locate the term ‘Ireland’ and increments a counter. As shown so far the term ‘Dublin’ is an ambiguous term but the term ‘Ireland’ is unambiguous. Next, the scanning component 225 locates a second occurrence of the term ‘Dublin’ in the document 200 and again increments a counter for the term ‘Dublin’ in the concept tree 220. Both occurrences of ‘Dublin’ now have a count of two. Next, the scanning component 225 locates the term ‘U.S.A’ and again increments a counter in the concept tree 220. This process is continued until all geographical terms in the document 200 have been processed—thus deriving the final result of:
Next, the determining component 230, determines from the concept tree 220, the number of times a specific term occurs in the concept tree 220. In the example, of FIG. 6, Dublin occurs twice and therefore for any instance of the term ‘Dublin’ found in the document 200, the term ‘Dublin’ has a fifty percent chance of being either Dublin of Ireland and thus the focus of the document is Ireland or Europe, or Dublin of the U.S.A and thus the focus of the document should be California or the U.S.A.
Taking each of these values the determination component 230 then sums each of the children nodes 310 weights with their parent node's 305 weight until each parent node 305 is weighted as its own assigned value summed with each of its child node's weights. This is shown in FIG. 6—where each node 305, 310 has a value comprising the sum of its own value with that of its child node's values and thus performing term disambiguation (step 925).
Then, the determination component 230, starting from the root node, traverses the concept tree 220, following the heaviest path (step 930)—in the example of FIG. 6 the heaviest path is Europe 605, Ireland 615 and Dublin 635. The focus of the document 200 will come to rest on a node in the tree, where all of its children's generalization value is greater than their weights i.e. the focus will fall on the node Ireland 615 (step 935).
h = 3 (tree depth), alpha = 1/3, beta = 0.1/h
[(Balbriggan,2.0), (Malahide,1.0), (Galway,1.0)]
Found Ireland 705/earth 700/ with normalized weight 0.3056
Found U.S.A 710/earth 700/ with normalized weight 0.0277
Choose Ireland 705 /earth 700/ with generalization force 0.136
Found Dublin 715 /Ireland 705/earth 700/ with normalized
Found Galway 720 /Ireland 705 /earth 700/ with normalized
Choose Dublin 715 /Ireland 705 /earth 700/ with generalization
force 0.247
Found Balbriggan 725 /Dublin 715 /Ireland 705 /earth 700/ with
normalized weight 0.167
Found Malahide 730 /Dublin 715 /Ireland 705 /earth 700/ with
normalized weight 0.083
Choose Balbriggan 725 /Dublin 715 /Ireland 705 /earth 700/ with
generalization force 0.3583
h = 3 (tree depth), alpha = 5/6, beta = 1/h
Found Ireland 805/earth 810/with normalized weight 0.916
Found U.S.A 810/earth 800/with normalized weight 0.083
Choose Ireland 807/earth 800/with generalization force 0.527
Found Dublin 815/Ireland 805/earth 800/with normalized weight 0.75
Found Galway 820/Ireland 805/earth 800/with normalized weight
Choose Dublin 815/Ireland 805/earth 800/with generalization force
Possible Modifications of the Algorithm
U(a)=alpha (level(a)+1)/height+beta.
This causes that the focus determining algorithm to behave differently for the nodes Commercial 305 and Free Time 305. To make the focus determining algorithm perform uniformly, it is possible to not use a normalization function U(n) taking into account that the leaf nodes of the tree 220 have different distances to the root node 300:
U(a) = alpha (level(a) + 1) / AverageHeight(a) + beta,
AverageHeight(a) = 1 + Average level(b)
for all b which are leafs and have a as ancestor.
Optimizing Computation of Specialization Force
As the weights of nodes 305, 310 in a subtree are propagated upwards through the concept tree 220, it may be useful to introduce a further metric when assigning the focus node in the concept tree 220. If the current node that the focus comes to rest on has no weight of its own—i.e. all of its weight is derived from the nodes beneath it—algorithm specifies that the focus should continue on down the tree until it comes to a node which was explicitly mentioned in the input document.
Select a child with the biggest value W(a)* P(a)
a* = argmax { W(a)*P(a): a is a child of the node f }
Parameterized Level of Specification/Generalization
Culturally, this parameterization is also a benefit. If one were to ask users from Ireland to decide on the focus of a document 200, they might decide it should be ‘Cork’. However, users from another country may instead decide that the focus is simply “Ireland”, not requiring any further specificity.
Advantages of using such a combined approach compared to “complex” text categorization are that text categorization is a run-time expensive procedure compared to graph algorithms working on small graphs. The focus-determining algorithm 210 approach allows the utilization of less expensive flat text categorization, but obtained results which take into account the hierarchical structure of the concept tree.
Referenced byCiting PatentFiling datePublication dateApplicantTitleUS7870141 *Feb 26, 2008Jan 11, 2011International Business Machines CorporationMethod and system for finding a focus of a documentUS8285716 *Dec 21, 2009Oct 9, 2012Google Inc.Identifying and ranking digital resources relating to placesUS8566321 *Mar 12, 2012Oct 22, 2013Amco LlcRelativistic concept measuring system for data clusteringUS8639643Oct 31, 2008Jan 28, 2014Hewlett-Packard Development Company, L.P.Classification of a document according to a weighted search tree created by genetic algorithmsUS8732167 *Sep 13, 2012May 20, 2014Google Inc.Identifying digital resources relating to entitiesUS8782051Apr 26, 2013Jul 15, 2014South Eastern Publishers Inc.System and method for text categorization based on ontologiesUS20120233188 *Mar 12, 2012Sep 13, 2012Arun MajumdarRelativistic concept measuring system for data clusteringWO2008125495A2 *Apr 2, 2008Oct 23, 2008IbmA method and system for finding a focus of a documentWO2010048758A1 *Oct 31, 2008May 6, 2010Shanghai Hewlett-Packard Co., LtdClassification of a document according to a weighted search tree created by genetic algorithms* Cited by examinerClassifications U.S. Classification1/1, 707/E17.015, 707/999.004International ClassificationG06F7/00Cooperative ClassificationG06F17/2745European ClassificationG06F17/27HLegal EventsDateCodeEventDescriptionApr 4, 2007ASAssignmentOwner name: INTERNATIONAL BUSINESS MACHINES CORPORATION, NEW YFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:CUNNANE, KEVIN;CURRAN, EMMA;MACEK, JAN;AND OTHERS;REEL/FRAME:019112/0382;SIGNING DATES FROM 20070315 TO 20070326Owner name: INTERNATIONAL BUSINESS MACHINES CORPORATION, NEW YFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:CUNNANE, KEVIN;CURRAN, EMMA;MACEK, JAN;AND OTHERS;SIGNING DATES FROM 20070315 TO 20070326;REEL/FRAME:019112/0382Oct 10, 2014FPAYFee paymentYear of fee payment: 4RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services