System and method of automatically mapping a given annotator to an aggregate of given annotators

[0001] The field of the invention is data processing of documents, more specifically, mapping a given annotator to an aggregate of other annotators in a given knowledge domain.

[0002] Text analysis, referenced hereinafter as “TA,” is known in the art pertaining to this invention as a sub-area or component of Natural Language Processing, hereinafter referenced as “NLP.” TA is used in a range of commercial, research and educational industries and uses including, for example, information search and retrieval systems, e-commerce and e-learning systems. A typical TA involves an “annotator” which, as known in the relevant art, is a process for searching and analyzing text documents using a defined set of tags, and running the annotator on the text document to generate what is known in the art as “linguistic annotations.” Annotators and linguistic annotations are well known. For the interested reader, an example listing of the many available TA publications can be found at the following URL: <http://www.ldc.upenn.edu/>.

[0003] An example TA may be illustrated by: <annot type=“X”>text<|annot>, where “X” may be any of a defined set of annotation types such as, for example, Person, Organization and Location, and “text” is the text that the “X” annotation characterizes. This example TA, when inserted into or otherwise associated with an example text to indicate or delineate the beginning and end of the annotated text, may be as follows:

• • [0004] “The underlying economic fundamentals remain sound as has been pointed out by the Fed,” said <annot type=“Person”>Alan Gayle</annot>, a managing director of <annot type=“Organization”>Trusco Capital Management</annot> in <annot type=“Location” kind=“city”>Atlanta</annot>, “though fourth-quarter growth may suffer”.

[0005] In the above example, “Alan Gayle” is an instance of the annotation type Person, “Trusco Capital Management” is an instance of the annotation type Organization and “Atlanta” is an instance of the annotation type Location. The example annotation type Location has an example feature, shown as “kind,” with example possible values of “city”, “state”, and the like.

[0006] A problem can exist or present, though, when using a new or unknown annotator, which is that the industrial fields or other TA objectives to which the unknown annotator relates, to which it may be best suited, may not be fully known.

[0007] These and other problems can be considerable, because a user often needs a particularly tailored application, e.g. particular annotation rules and annotation types (e.g. annotate all CEOs of IT companies), in documents from in a given document collection or domain. There are known ways of building such particularly tailored applications, such as, for example, Interactive Learning System (see, for instance, SAIL system—Semi-Automated Interactive Learning, being researched at IBM). These related art systems can eventually generate a rule-based annotation engine, capable of producing desired annotations, but have at least two shortcomings: human judgment is required, and there is a possibility of producing or converging on an inefficient result. For example, there may be a high number of processing rules generated by the SAIL system in response to interactions with the human user. Further, a new knowledge domain, and even a new document corpus, may require re-training of the system and re-generating the rules.

[0008] It is therefore an object of the invention to provide a method and apparatus for mapping an annotator to a best aggregate of a collection's annotators.

[0009] Another object of the invention is to provide a method and apparatus that, based on a given corpus of documents, and a given collection of known annotators, identifies whether there exists an aggregate of the known annotators that is a functional equivalent to an unknown annotator.

[0010] Another object of the invention is to provide a method and apparatus for replacing a plurality of annotators in an annotation processing pipe with one, potentially more efficient, aggregate of known annotators. This object particularly relates to certain objects of TA, in that analysis application often involves a large set of annotators that form the annotation processing pipe.

[0011] A general embodiment of the invention includes a given collection of annotators and a subject annotator. The annotators in the given collection may include annotators that are non-aggregated, i.e., primitive annotators, and/or annotators that are themselves aggregates of other annotators. The subject annotator may be a known annotator, or may be an unknown annotator, but in both cases it is analyzed as a black box.

[0012] A general embodiment performs steps, or includes machine-readable instructions, for identifying whether the subject annotator is functionally equivalent to an aggregate of the given annotators and, if such a functionally equivalent aggregate is identified, a general embodiment performs steps, or includes machine readable instructions, for mapping the subject annotator to the identified virtual aggregate of collection's annotators.

[0013] A general embodiment identifies whether the subject annotator includes providing a corpora of original documents and providing or generating a corresponding corpora of annotated documents. The original documents are selected or provided such that the corpora of annotated documents contains instances of annotations produced by all of the collection's annotators and by all of annotators' possible aggregates.

[0014] A general embodiment further includes applying the subject annotator to the corpus of original documents to produce instances of its annotations in all documents.

[0015] A general embodiment further may include sorting-out good candidate annotations, from the set of annotations produced by annotators from the given collection, and decomposing annotations produced by the subject annotator, to represent them as superpositions of the given candidate annotations, on a per document group basis.

[0016] A general embodiment further includes mapping the subject annotator to a virtual or actual aggregate of the given annotators, and the mapping may include selecting the most representative superposition of the given candidate annotations and then mapping that superposition to a virtual or actual aggregate of the collection's given annotators.

[0021] It is to be understood that the present invention is not limited to the specific examples described herein and/or depicted by the attached drawings, and that other configurations and arrangements embodying or practicing the present invention can, upon reading this description, be readily implemented by persons skilled in the arts pertaining to the invention.

[0022] In the drawings, like numerals appearing in different drawings, either of the same or different embodiments of the invention, reference functional or system blocks that are, or may be, identical or substantially identical between the different drawings.

[0023] It is to be understood that the various embodiments of the invention, although different, are not necessarily mutually exclusive. For example, a particular feature, function, act or characteristic described in one embodiment may, within the scope of the invention, be included in other embodiments.

[0024] Further, it is to be understood that the terminology used herein is not limiting and, instead, is only for purposes of ease of reference.

[0025] Further, it is to be understood that functions and operations shown or described as separate blocks are not, unless otherwise specified or clear from the context, necessarily performed at separate times, or on separate computational units, and operations described or depicted as being separate may be implemented or modeled as a single block.

[0026] Further, as will be understood by persons skilled in the art upon reading this description, certain well-known methods, arrangements, acts and operations of annotators are omitted, or are not described in detail, so as to better focus on, and avoid obscuring the novel features, combinations, and structures of the present invention.

[0027] The present invention includes various functional blocks, acts, steps and/or operations (collectively “operations”), which will be described below. The operations can be embodied in machine-executable instructions, which may be stored on a machine-readable medium, which can be used to cause a general-purpose or special-purpose processor programmed with the instructions to perform the operations.

[0028] FIG. 1 illustrates one example of a detailed system architecture 10 in accordance with at least one embodiment, in which described operations can be embodied in machine-executable instructions stored on, for example, the disk 12 or other machine-readable medium, the instructions causing a general-purpose or special-purpose processor, such as, for example, the central the processing unit, or CPU 14 to perform the operations. The instructions may be stored on, for example, the disk 12 or another other storage medium. The described data and annotator systems, such as the corpus of documents, pre-annotated documents and annotated documents, given annotators and subject or unknown annotator described in reference to FIGS. 2-4, may be stored on, for example, the disk 12 or another machine medium. An I/0 unit or system 16 such as, for example, a keyboard and/or graphical user interface or, for example, a personal computer connected via network to the CPU 14 is included in the example system 10.

[0029] Alternatively, the described operations may be performed by specific hardware components that contain hardwired logic for performing the steps, or by any combination of programmed computer components and custom hardware components. Further, the described operations may be performed in distributed computing systems or environments, such as processors and processing components remote from a machine-readable medium, where instructions from the medium are communicated over a communication link or network.

[0030] A collection of given annotators is provided. For purposes of this description, an annotator is a process, method or routine that inserts, adds or associates annotations to textual media documents. The given annotators may include primitive annotators and aggregate annotators, where primitive annotator means a species of annotator that itself carries out annotator processes methods or routines, without using other annotators and aggregate annotators, or aggregates, means a species of annotator composed of a plurality of other annotators, which themselves may be primitive and/or aggregate annotators. An aggregate is defined as a flow of annotators constituting the aggregate operation flow.

[0031] All possible aggregates of the given annotators are also provided in the collection, or are generated using, for example, conventional methods or algorithms for aggregating annotators. A corpora of original documents is provided, and a corresponding corpora of annotated documents is provided or generated. The annotated documents are the original documents annotated to contain instances of annotations produced by all of the collection's given annotators and by all aggregates of the given annotators. These instances are referenced in this description as “given annotations.” The subject annotator is applied to the corpus of original documents to produce instances of its annotations in all documents. These instances are referenced in this description as “subject annotations.”

[0032] A filtering may be performed, to reduce unnecessary computational burden in subsequently described operations, to sort out annotations from the given annotations using a described method of calculating their relevance, these filtered annotations being collectively referenced in this description as “good candidate annotations.”

[0033] The subject annotations are decomposed into a representation that is by superpositions of the given annotations. The decomposition is in terms of certain of the given annotations, which are either those sorted out as good candidate annotations, by the optional filtering or, inherent in the decomposition, ones of the given annotations that would have been identified as good candidate annotations if the filtering were performed. The decomposition is on a per document group basis.

[0034] A mapping is performed that selects the most representative superposition of the given candidate annotations and maps that superposition to a virtual or actual aggregate of collection's annotators. This, in turn, provides automatic mapping any given annotator to a virtual or actual aggregate of the given collection's annotators.

[0035] An example overview of the decomposition of subject annotations into a representation as superpositions of the given annotations may be represented as follows:

[0036] i. Represent annotations as mapping functions from the space of documents and sentences to the space of tagged textual spans;

[0037] ii. Embed the space of equitagged spans into the vector space of appropriate dimension. With this abstraction annotation functions map the space of documents and sentences into the vector space;

[0038] iv. Define Boolean expressions on the annotation spans;

[0039] v. Form a basis on the set of annotation expressions; and

[0040] vi. Identify an expression of the untried equitagged Annotation through the given set of annotations.

[0041] FIG. 2 illustrates an example functional flow diagram for an embodiment of the method.

[0042] At 102 a plurality of N annotators is provided, represented in FIG. 2 by the sub-blocks labeled Annotator_n, for n=1 to N. Also at 102, all aggregates of the annotators, Annotator_n n=1 to N, are provided or generated. The aggregates are represented at 102 of FIG. 2 as Aggregate_i, for i=1-2 . . . 1-N, 2-1 . . . 2-N . . . K-L-M . . . . The hyphenated value of the subscript i of Aggregate_i represents all of the Annotator_n aggregated to form that Aggregate_i. For example, Aggregate_2-4-N is the aggregate of the 102 given Annotator₂, Annotator₄ and Annotator_N, and Aggregate_1-4-6 is the aggregate of Annotator₁, Annotator₄ and Annotator₆.

[0043] 102 may be realized by providing all of the N annotators and all of the aggregates, or by providing all of the N annotators and then generating all of the possible aggregates. As can be understood by persons of ordinary skill in the relevant arts, the above phrase “all of the possible aggregates” means all reasonable aggregates that can be created from the given annotators, where “reasonable” is associated with two general conditions: (i) an input/output condition requiring compatibility at the type system level, because annotators can be aggregated only if they have such compatibility; and (ii) a semantic condition, requiring that the annotators be such that their aggregation is meaningful.

[0044] With continuing reference to FIG. 2, at 104 an original document corpus is provided.

[0045] At 106 a subject annotator, which may be an unknown annotator, or one of the given annotators, is applied to the original document corpus 104 to generate a corpus of annotated documents 108.

[0046] At 110 each Annotator_n, for n=1 to N, and each Aggregate_i, for i=1-2 . . . 1-N, 2-1 . . . 2-N . . . K-L-M, is applied to the original document corpus to generate a corpus of pre-annotated documents 112.

[0047] At 114, which is an option that may reduce unnecessary computation burden in carrying out the decomposing 116 described below, a sorting is performed to sort out from the annotations contained in the pre-annotated documents 112 those annotations meeting a criteria for correlation, in terms of occurrences, with the subject annotations. Such annotations are referenced in this description as “good candidate annotations.”

[0048] An example of the 114 filtering is illustrated in FIG. 3, as follows:

[0049] a) a graph, or information that can be described in graph form is constructed or calculated for each concrete annotation type of the given annotators, for each document in the pre-annotated documents 112, representing frequencies of the candidate annotation instances in each sentence of the document;

[0050] b) analogous frequency graphs, or frequency information that can be described in graph form as graphs, are calculated or constructed, for each document in the annotated documents 108, for the subject annotation instances; and

[0051] c) by comparing, on a per document basis, the graphs or information identified at sub-paragraph (a) above, i.e., the given candidate annotations frequency graphs, to the graphs or information identified at sub-paragraph (b) above, i.e., the subject annotations frequency graphs, filtering is obtained as to the given candidate annotations instances that have frequency graphs correlated with the frequency graphs of the subject annotations instances.

[0052] Referring again to FIG. 2, at 116 the subject annotations are decomposed into aggregates of the given annotations.

[0053] FIG. 4 illustrates an example flow diagram for the 116 decomposition. Referring to FIG. 4, at 302 the annotations are formally modeled as a mapping from a (corpus, document, sentence) space to a (span, tag) space. An example modeling identifies, as equitagged spans, the spans with the same value of the tag. The measure on the spans may be represented as follows: Span S is represented as the union of non-intersecting intervals I_k from the sentence associated with the annotation. For each interval I_k=[a_k, a_(k+1)], where a_i are coordinates (positions) within the document, the measure may be defined as measure m(I_k) being |a_(k+1)−a_k|, and for the span the measure may be defined as m(S)=Σm(I_k).

[0054] At 304 the spans are embedded into a vector space of dimension preferably greater or equal to the number of all possible spans for this sentence. For example, the sentence “The summit starts today.” can have 4+6+3+1=14 spans, including non-contiguous spans.

[0055] An example of the embedding 304 is as follows:

[0056] Consider functions F from (corpus, document, sentence)->R^d, where d=length_of(sentence).

[0057] Span-interval I_k corresponds to the vector space generated by the coordinates [a_k, a_(k+1)] and, with each span S defined as a union of the non-intersecting intervals I_k, we associate FS(S) as a function from set of all functions from (corpus, document, sentence)->subspaces generated by appropriately taken coordinates of the R^d. Regarding the “appropriately taken coordinates,” for this example embedding 304 the vector space dimension is equal to the number of characters in the sentence, which is d generated by the above-described functions F. The position of each character position this sentence may be represented by the vector d, having a logical “1” coordinate in the position corresponding to the position of the character in the sentence and logical “0” coordinates in all other positions (like ‘100 . . . 0’ for the 1^st character, etc.) In the same way, the embedding 304 may associate each word in the sentence with a sum of vectors representing its characters. Each span may include one or more words, so the ‘span’ function can map the tuple (corpus, document, sentence) into subspaces of the R^d that include vectors corresponding to whole words or their combinations. An example embedding 304 may fix a counting measure on (corpus, document, sentence), and define a scalar product on FS as (FS₁, FS₂)=Sum over all (corpus, document, sentence) of m(S1 intersect S2).

[0058] Referring to the FIG. 4 example functional flow, 306 maps the annotation expression into, for example, a lattice of the possible expressions. An example 306 mapping may be as follows:

• • [0059] a. let annotation A_i correspond to the span S_i;
  • [0060] b. define for two annotations, labeled for reference as A₁ and A₂, an intersection operation S₀ as the coordinate-wise union of all possible pairwise intersections of intervals defining S₁ and S₂;
  • [0061] c. define a union operation S₀ of A₁ and A₂ in a similar manner as (b). It should be noted that the union S₀ of S₁ and S₂ is a union of spans coordinate wise;
  • [0062] d. define in a similar manner a complement of S₁ and inclusion S₂ in S₁;
  • [0063] e. define, as possible Boolean expressions corresponding spans, coordinate-wise, the set of all possible expressions of the annotations A_i; and
  • [0064] f. form the set of all possible expressions, referenced hereinafter as APE, on the annotations A_i as a lattice LA with respect to union, intersection, inclusion and complement.

[0065] It will be understood that the above-listed example outline for carrying out the example mapping 306 to a lattice is only for purposes of presenting an example logical representation, and is not necessarily a representation of a sequence, grouping or modules of operations or machine-readable code for the mapping.

[0066] With continuing reference to FIG. 4, 308 extracts a basis on the set of all possible expressions (APE). The basis may not be unique, but the described system and method, and the processing results, do not depend on the specific extracted or chosen basis. An example 308 extraction chooses as the basis on the set of all possible expressions (APE) the minimal set of elements from inclusion APE (IAPE), in the sense that no element is less than a given element with respect to inclusion, so that each expression E from APE may be represented as a union of elements from IAPE. A minimal set of elements is the smallest possible result, which is the intersection of all annotations. This may be an empty set. Identifying the basis may be, for example, generally along the flow of Gauss elimination for linear matrices. For example, extraction 308 may iteratively remove indices, one at a time, and create an intersection for them. The iterations may be in accordance with, or carried out applying the following logic:

[0067] i) The removed index may be empty, or it may be the first index for which all possible further intersections will be empty. If it is the first such index then it is a minimal set and it is chosen.

[0068] ii) If the removed index is not the first non-empty index, then the difference between this set and all possible chosen minimal sets may be considered, and a complementary minimal set may be chosen based on this difference.

[0069] It will be understood that the above-listed example outline for carrying out the example extraction 308 is for only for purposes of presenting an example logical representation, and is not necessarily a representation of a sequence, grouping or modules of operations or machine-readable code for the extraction.

[0070] By the above example construction in the extraction 308, every expression E on APE can be represented as a union of the minimal or complementary minimal sets. Accordingly, if some E on APE cannot be represented as a union of minimal or complimentary minimal sets then it is not acceptable.

[0071] Referring to the FIG. 4 example flow diagram for the FIG. 2 decomposition 116, at 310 the expression of the subject equitagged Annotation is found in terms of the annotations in the pre-annotated documents 112 that were inserted by the given annotators and aggregates 102. An example expression 310 may be as follows:

[0072] a. Find the basis of the given set of annotation expressions;

[0073] b. Express the subject annotation as an expression on the basis; and

[0074] c. Substitute each element of the basis in the expression of the subject annotation, inserted by the subject annotator at 106 and extant in the annotated documents 108, through the basis with its expression through annotations inserted by the 102 annotators.

[0075] It will be understood that the above-listed example outline for carrying out the example expression 308 is only for purposes of presenting an example expression through the basis, and is not necessarily a representation of a sequence, grouping or modules of operations or machine-readable code for the expression.

[0076] Referring again to the FIG. 2 example flow diagram, after the decomposing 116, at 118 the most suitable expression of the subject annotation (which is an expression on the basis) is identified on a per document basis. Most suitable are those expressions that proved to be the most common, i.e., have the highest frequencies of occurrence, on the given group/corpus of documents.

[0077] At 120 that identified expression is mapped to the virtual or actual aggregate of the given annotators 102, where “virtual aggregate” means an aggregate that does not exist in the collection of given annotators Annotator_n, but that may be created if needed, and an “actual aggregate” one the one that already exists in the collection of given annotators 102.

[0078] An example of carrying out the above-described method, or system if performed on a machine reading machine-readable instruction, is as follows:

[0079] Given: two given annotations, which we will labeled for reference as A1 (Official_Title) and A2 (Person_Name), in the pre-annotated documents 112, and a subject annotation, which will be labeled for reference as A3. Also given: the following example original text, appearing in a document in the original document corpus 104:

• • [0080] The deal appeared to be a clear victory for Sen. John Smith, Named Political Party, Somestate, who sponsored the proposed bill, and a setback for Sen. Bill Murray and others who had argued that the bill would impede United States security efforts.

[0081] The above example original text, in the pre-annotated documents 112 annotated by the annotators in 102 that implement A1 and A2, is as follows:

• • [0082] The deal appeared to be a clear victory for <annot type=“Official_Title”>Sen.</annot><annottype=“Person_Nam e”>John Smith</annot>, Named Political Party-Somestate, who sponsored the proposed bill, and a setback for <annot type=“Official_Title”>Vice President</annot><annot type=“Person_Name”>Bill Murray</annot> and others who had argued that the proposed bill would impede United States security efforts.

[0083] The same text, in the annotated documents 108 annotated by the subject annotator 106 that implements unknown annotation A3:

• • [0084] The deal appeared to be a clear victory for <annot type=“AT3”>Sen. John Smith </annot>, Named Political Party-Somestate, who sponsored the proposed bill, and a setback for <annot type=“AT3”>Vice President Bill Murray </annot> and others who had argued that the proposed bill would impede United States security efforts.

[0085] Decomposing A3 by A1 and A2, applying the decomposing 116 in accordance with, for example, the FIG. 4 example flow diagram, we get the following expression:
A3=A1unionA2

[0086] Applying the described system and method, users can identify that already known or accessible annotators, i.e., an “annotator library,” (see, for instance, UIMA Component Repository at http://uima.lti.cs.cmu.edu:8080/UCR/Welcome.do) that if, combined in an appropriate way to form an aggregate annotator, may meet desired objectives.

[0087] As described, this method and system automatically map a given subject annotator 106 to a virtual or actual aggregate of the given annotators 102. Applying the described system and method, a SAIL or other generated annotator may be identified as functionally equivalent to, i.e., produce the same annotations as, a combination of library annotators. Accordingly, using the described system and method a rule based annotator, generated by for example the SAIL or equivalent system, for a particular document collection, may be replaced with a functionally equivalent aggregate of already existing library annotators that is generated by the present system and method, thus significantly improving the overall performance of the TA application.

[0088] This in turn, may allow substituting several adjacent annotators in the given annotation processing pipe with one, possibly more efficient, functionally equivalent annotator from the given collection. Such a substitution may be possible after mapping a selected group of annotators from the given processing pipe to one of existing annotators from the given collection.

[0089] Further, the described system and method provide for selecting a suitable mapping for any group of adjacent annotators from the given annotation processing pipe. In addition, the method and system may be applied to extend methods of automated planning to a set of annotators that include both well-known and untried ones. Automated planning is known in the relevant art, see, for example, “Stream Processing Planning”, G. Grabarnik, Z. Liu, A. Riabov, ICAPS 2005, and “Automated planning in the Grid stream processing environment”, G. Grabamik, L. Shwartz, Applied Computing, 2006, so further description is unnecessary for applying the described system and method. Further, the system and method may assist or provide reduction in the dimensionality of planning problems, such as for example, the type described in “Algorithm Overview” section of “Automated planning in the Grid stream processing environment”, G. Grabarnik, L. Shwartz, Applied Computing, 2006, p. 4, and similar publications.

[0090] While certain embodiments and features of the invention have been illustrated and described herein, many modifications, substitutions, changes, and equivalents will occur to those of ordinary skill in the art. It is therefore to be understood that the appended claims are intended to cover all such modifications and changes as fall within the spirit of the invention.