Module 3

3 Extracting Relations from Text: From Word Sequences to Dependency Paths

3.1 Introduction

Extracting semantic relationships between entities in text documents is a crucial task in natural
language processing (NLP) for providing structured information to text mining systems. This
task typically involves a predefined set of entity and relation types relevant to a user and a
particular text collection. For instance, information extraction from newspaper articles focuses
on identifying people, organizations, locations, and their relationships (e.g., social
relationships, roles within organizations, physical locations). In the biomedical domain, relevant
entities include proteins, genes, and cells, with relations like subcellular localizations and
protein-protein interactions. A significant challenge in the biomedical domain is the scarcity of
NLP tools trained on this specific narrative, as most existing tools are trained on newspaper
corpora, leading to accuracy loss. Therefore, systems for biological corpora need to be robust to
parsing errors or rely on shallower, more reliable information.

This chapter presents two approaches to relation extraction, differing in the linguistic
information they use:

1. Subsequence Kernels: Represents potential relations as a vector of features corresponding to

word sequences anchored at the two entities, generalized with word classes like POS tags or
WordNet synsets.
2. Dependency-Path Kernel: Centers representation on the shortest dependency path between
entities in a sentence's dependency graph, applicable where syntactic parsing is accurate.

Both methods assume that entity recognition has already been performed.

3.2 Subsequence Kernels for Relation Extraction

This approach implicitly represents each potential relation as a vector of features, where each
feature corresponds to a word sequence anchored at the two entities forming the relationship.
The method generalizes by allowing words to be replaced with word classes (e.g., POS tags,
named entity recognition, chunking, or WordNet synsets) to alleviate data sparsity.

 Capturing Relation Patterns with a String Kernel (3.2.1):

o Relation extraction can be based on a limited set of matching rules, where a rule is a
sparse subsequence of words or POS tags anchored on two entity tokens.
o Support Vector Machines (SVMs) are used to compute the dot-product (kernel)
between feature vectors, efficiently calculating common anchored subsequences.
o Four main patterns are used to express relationships, typically using at most four words
(excluding entity names):
 Fore–Between [FB]: Words before and between the entities are used (e.g.,
"interaction of with ").
  Between [B]: Only words between entities are essential (e.g., " interacts with ").
 Between–After [BA]: Words between and after entities are used (e.g., " –
complex").
 Modifier [M]: No words between entities, common in noun-noun or adjective-
noun compounds (e.g., "U.S. troops").
o Restricting subsequences to these patterns and a maximum word-length of four
improves kernel computation speed and accuracy by reducing overfitting.
 A Generalized Subsequence Kernel (3.2.2):
o This kernel operates over disjoint feature spaces (e.g., words, POS tags). A sequence u is
a sparse subsequence of s if its elements are present in s in ascending order of indices.
o Kn(s, t, λ) is defined as the number of weighted sparse subsequences of length n
common to s and t, with a weight of λ^(l(i)+l(j)).
o The decaying factor λ penalizes longer subsequences and wider gaps, reflecting less
confidence in head-modifier relationships with larger word gaps.
 Computing the Relation Kernel (3.2.3):
o The relation kernel, rK(s, t), is the sum of four sub-kernels: fbK, bK, baK, and mK, each
counting common patterns of the four types described earlier.

3.3 A Dependency-Path Kernel for Relation Extraction

This approach focuses on the shortest dependency path between two entities in the dependency
graph of a sentence.

 Sentences as Dependency Graphs: Words are nodes, and word-word dependencies are directed
edges. Dependencies are categorized as:
o Local Dependencies: Correspond to predicate-argument or head-modifier constructions
(e.g., "troops → raided").
o Non-local Dependencies: Arise from linguistic constructions like coordination or
extraction (e.g., "troops → warning").
 The Shortest Path Hypothesis (3.3.1): This hypothesis states that the information relevant to a
relationship between two entities (e1, e2) is almost exclusively concentrated in the shortest
path between them in the undirected dependency graph.
o Paths may pass through a common predicate if entities are arguments of the same
predicate, or through a common argument if they belong to different predicate-
argument structures.
o The shortest path offers a condensed representation, but its lexicalized nature can lead
to data sparsity. This is mitigated by allowing paths to use both words and word classes.
o Features are generated as a Cartesian product over words and word classes along the
dependency path, allowing for sparse or contiguous subsequences (path fragments).
o Negative polarity items (e.g., "not," "never") are integrated by adding a '(-)' suffix to
verbs or nouns in the path.
o The kernel, K(x,y), is computed as the product of common word classes at each position,
with a value of 0 if paths have different lengths, implying different ways of expressing
the relationship.
3.4 Experimental Evaluation

The two relation kernels are evaluated on two corpora with different narrative types: AIMed
(biomedical abstracts) and ACE (newspaper corpus).

 Methodology:
o Sentences with n (≥ 2) entities are replicated into n choose 2 sentences, each with two
entities, and added to positive or negative sets based on known relationships.
o SVM learning is used with the custom kernels (LibSVM package), setting the λ factor in
the subsequence kernel to 0.75.
o Performance is measured using precision, recall, and F-measure.
 Interaction Extraction from AIMed (3.4.1):
o Compares the subsequence kernel (SSK) and shortest path dependency kernel (SPK)
against rule-based (Manual) and ELCS systems.
o SSK outperforms the other systems significantly. SPK has reduced accuracy due to less
accurate dependency structures built by parsers (trained on newspaper corpora) for
biomedical text.
 Relation Extraction from ACE (3.4.2):
o Evaluates SSK and SPK (using Hockenmaier's CCG parser and Collins' CFG parser) on
extracting top-level relations (Role, Part, Located, Near, Social) from newspaper articles.
o SSK utilizes word vocabulary, POS tags, generic POS tags, and entity types as feature
spaces. Chunking information is used, considering only chunk heads.
o SPK-CFG and SPK-CCG are trained under two scenarios: multi-class SVM for five relation
types plus no-relation, and a binary SVM for relation detection followed by a multi-class
SVM for classification.
o Shortest-path dependency kernels (SPK-CFG, SPK-CCG) outperform other dependency
kernels, with SPK-CFG showing a more substantial gain. Collins' parser's better capture
of local dependencies contributes to SPK-CFG's increased accuracy. Training and testing
are very fast for SPK kernels. Parsing errors are less common in newspaper articles
compared to biomedical texts, leading to improved accuracy for the dependency kernel
in ACE.

4 Mining Diagnostic Text Reports by Learning to Annotate Knowledge Roles

4.1 Introduction

Performing text mining on new data requires combining and adapting different research
approaches to handle issues like data sparsity, availability of labeled data, and quality of text
data. For tasks requiring sentence-level operation (e.g., summarization, information extraction,
question answering), natural language processing (NLP) is needed to produce more informative
features.

This chapter presents an approach to extracting knowledge from diagnostic text reports in
electrical engineering by combining NLP, knowledge engineering, and machine learning
techniques. The goal is to annotate cases with knowledge roles, which facilitates case retrieval,
empirical domain knowledge collection, and reasoning with an ontology. The work involved
several steps:
  Document transformation to XML.
 Extraction of case-related paragraphs.
 Part-of-speech tagging and syntactic parsing.
 XML representation for manual annotation.
 Feature construction for learning algorithms.
 Implementation of an active learning strategy.

Experimental results on 500 German Microsoft Word documents (approx. one million words)
demonstrated the feasibility and high quality of the annotation.

4.2 Domain Knowledge and Knowledge Roles

 Domain Knowledge (4.2.1): The domain is predictive maintenance in power engineering,

specifically insulation systems of high-voltage rotating electrical machines. Findings from
maintenance processes are documented in various forms, including textual diagnostic reports.
The most crucial information is in the evaluations of measurements and tests.
 Domain Concepts (4.2.2): While reports contain domain-specific terms (e.g., "insulation,"
"discharge"), simply using these as indices is insufficient for supporting diagnostic problem-
solving. More than domain concepts are needed to capture the knowledge expressed.
 Knowledge Roles (4.2.3): The solution involves labeling text with semantic annotations
expressed as knowledge roles, a concept from CommonKADS. Knowledge roles are abstract
names referring to the function a domain concept plays in tasks like diagnosis, assessment, or
planning. For a diagnosis task, roles might include finding, symptom, fault, parameter, or
hypothesis.
o For example, in a sentence like "The insulating resistance had lower values due to
dirtiness at the surface," the knowledge roles would be: Observed Object: insulating
resistance, Symptom: lower values, Cause: dirtiness at the surface.
o Such a representation has advantages, such as retrieving symptoms for an Observed
Object or causes for a Symptom.
o Automatically performing this annotation is the goal, drawing on natural language
understanding research.
o Keyword-based approaches are often inadequate due to the large number of words
describing changes, the abundance of verbs with varying meanings (affected by
adverbs and negations), and the fact that meaning often emerges from relations
between words rather than isolated terms.
o Knowledge roles are abstract, domain-independent constructs from knowledge
engineering, and bridging the gap between them and natural language constructs is a
key contribution.

4.3 Frame Semantics and Semantic Role Labeling

 Frame Semantics (4.3.1): In frame semantics, a frame is a conceptual structure describing a

situation, object, or event and its participants. The Berkeley FrameNet Project creates an online
lexical resource by annotating text with frames, lexical units, and frame elements (semantic
roles). For example, the Evidence frame includes roles like Proposition and Support, and
sentences are annotated with these roles.
  Semantic Role Labeling (4.3.2): This is the automatic task of identifying and labeling syntactic
constituents with semantic roles associated with a target verb in a sentence. SRL systems
typically create feature vectors for each constituent and feed them to supervised classifiers. The
CoNLL shared tasks have advanced SRL research, leading to corpora like PropBank and Salsa
(for German).
 Frames and Roles for Annotating Cases (4.3.3):
o Knowledge roles from knowledge engineering (e.g., diagnosis) can map to semantic
roles from frame semantics.
o Diagnostic evaluations often contain observations, explanations based on evidence,
and suggestions for activities, aligning with FrameNet frames like Observation, Change,
Evidence, or Activity.
o The Proposition role in the Evidence frame is similar to Cause, and Support is similar to
Symptom in diagnosis.
o Lexical units (verbs) are key to finding relevant frames and mapping semantic roles to
desired knowledge roles.
o Annotating text with frames and roles generates informative data for text mining,
allowing for insights into frequent symptoms, causes, and problems associated with
specific machines. This approach is valuable for repetitive tasks where a small number of
underlying semantic frames are expressed.

4.4 Learning to Annotate Cases with Knowledge Roles

A software framework was implemented for this learning task, beginning with document
preparation.

 Document Preparation (4.4.1): Official diagnostic reports, structured in sections and subsections
using MS Word, were transformed into XML format. Challenges included disentangling
formatting instructions from content and handling variations from a common style template.
Subcorpora of text containing specific measurement evaluations were then created as
paragraphs.
 Tagging (4.4.2): The TreeTagger (a probabilistic POS tagger) was used for German to obtain
stem information and divide paragraphs into sentences. Stemming showed about 1%
improvement in recall and precision for the learning task, suggesting it's not critically important
when many other features are used. Stem information is valuable for capturing word
composition in German (e.g., compound words like "Ableitstromwerte" share "Wert" - value).
 Parsing (4.4.3): Syntactical parse trees are crucial inputs for feature creation. Experiments were
conducted with Stanford, BitPar, and Sleepy parsers. The Sleepy parser was chosen for its speed
and informative output (log likelihood, grammatical function labels), as parsing accuracy was
presumed similar across parsers trained on the same German corpora (Negra/Tiger).
 Tree Representation (4.4.4): Parse trees and stem information are converted into a tree data
structure (terminals and non-terminals/constituents). These are stored in XML format according
to the TigerSearch schema for exploration and annotation.
 Feature Creation (4.4.5): Feature vectors are created for every constituent of the parse tree,
including unique constituent features, common sentence features, and features relative to the
target predicate verb. Examples include phrase type, grammatical function, path from target
verb to constituent, path length, relative position, parent phrase type, target lemma, target
 POS, passive voice indicator, preposition, head word, sibling phrase types/lemmas, first/last
word/POS, frame, and role (the class label to be predicted).
 Annotation (4.4.6): The Salsa annotation tool allows users to manually add frames and roles to
constituents of the parse tree, linking them to target verbs. This process adds an <frames>
element to the XML representation.
 Active Learning (4.4.7): An active learning strategy, using a committee-based classification
scheme steered by corpus statistics, was implemented. Steps include:
o Clustering sentences by target verb and merging small clusters by frame.
o Grouping sentences with the same parse sub-tree within each cluster.
o Selecting sentences from large groups/clusters for manual annotation.
o Bootstrapping initialization: Applying user-assigned labels to sentences with identical
parse sub-trees, effective for repetitive text with consistent syntactic structures and
assigned roles (e.g., passive verb "feststellen" leading to NP-Finding, PP-Observed
Object roles).
o Committee of classifiers: Consists of a MaxEnt classifier (Mallet), a Winnow classifier
(SNoW), and a memory-based learner (TiMBL). An instance is presented for manual
labeling if there is disagreement among classifiers or if the cluster of nearest neighbors
is not homogenous.
o Selecting new sentences for manual annotation from large, un-labeled clusters to avoid
outliers.

4.5 Evaluations

Experiments evaluated the active learning approach on two manually annotated benchmark
subcorpora: Isolation Current and Wedging System.

 Learning Performance on the Benchmark Datasets (4.5.1):

o 10-fold cross-validation on these datasets yielded high results.
o Isolation Current: Recall = 0.913, Precision = 0.934, Fβ=1 = 0.92.
o Wedging System: Recall = 0.838, Precision = 0.882, Fβ=1 = 0.86.
o Classification errors were sometimes due to parsing anomalies that forced role splitting
across constituents.
 Active Learning versus Uniform Random Selection (4.5.2):
o Active learning (Fβ=1 measure) showed 5–10 points better results than uniform random
selection of sentences for manual annotation.
 Bootstrapping Based on Other Sets (4.5.3):
o Experiments tested if text annotated in one subcorpus (e.g., Isolation Current) could
bootstrap learning in another (e.g., Wedging System).
o Using Isolation Current to train for Wedging System resulted in Recall = 0.765, Precision
= 0.859.
o Using Wedging System to train for Isolation Current resulted in Recall = 0.642, Precision
= 0.737.
o These results suggest the possibility of using previously annotated text to alleviate
manual annotation for new text.
5 A Case Study in Natural Language Based Web Search

5.2 InFact System Overview

InFact is a natural language search engine designed to combine keyword search speed with NLP
power, performing clause-level indexing and offering functionalities ranging from Boolean
operators to linguistic pattern matching. It enables users to navigate and retrieve information
based on an understanding of actions, roles, and relationships. InFact uses a new approach to
text parameterization that captures syntactic categories (POS), syntactical roles (subject,
object), and semantic categories (people, places), which are ignored by standard inverted
indices.

 Indexing (5.2.1): InFact's Indexing Service performs document processing, clause processing,
and linguistic normalization.
o Document Processing: Involves format conversion, customized document parsing
(recognizing zones, segmenting information), sentence splitting (handling delimiters,
lists/tables), and extracting morphological stems and frequency counts.
o Clause Processing:
 Feeds sentence splitter output to a deep linguistic parser.
 Performs clause-level indexing, capturing syntactic categories (POS tags) and
grammatical roles (subject, object) for each term.
 Tokens undergo grammatical stemming (e.g., normalizing verbs to infinitive)
and optional additional tagging (e.g., temporal, aspect, mood/modality tags).
 Captures inter-clause links via explicit tagging of conjunctions/pronouns and
pointing to annotated keywords in adjacent sentences.
 Recognizes and cross-references appositive clauses.
o Linguistic Normalization:
 Applies rules at syntactic, semantic, or pragmatic levels.
 Coreferencing and anaphora resolution use syntactic agreement (person,
gender, number), binding theory constraints, referential distance, syntactic
position, and head noun weighting.
 Applies a transformational grammar to map multiple surface structures into an
equivalent deep structure (e.g., passive to active voice).
 Normalizes composite verb expressions, captures explicit/implicit negations,
and verbalizes nouns/adjectives conveying action.
 Storage (5.2.2):
o Converts complex augmented parse tree structures into scalable data storage.
o Models storage after subject-action-object triplets, which, with modifiers, can express
most syntactic relations.
o The index abstraction includes a "Dist" column for degrees of separation and "Neg" for
negated actions.
o Stores normalized triplets in dedicated index structures optimized for efficient keyword
search, cross-document retrieval of relationships/events, and document metadata
filtering.
 o Optionally superimposes annotations and taxonomical dependencies from custom
ontologies.
o Stores "soft events"—data structures that can be recombined to form events and
relationships—allowing for multiple interpretations (e.g., a presidential visit and
diplomatic relations).

 Search (5.2.3):
o Employs InFact Query Language (IQL), combining grammatical roles with Boolean
operators to search for actions, entities, relationships, and events.
o Basic relationship expression: Subject Entity > Action > Object Entity (arrows indicate
directionality, wildcards allowed).
o Supports entity types (e.g., [Country], [Location]) organized hierarchically in a
taxonomy, with queries automatically including subpaths.
o Allows searching for any relationships involving an entity, relationships between two
entities/types, events involving one or more entities/types, and events involving a
certain action type (groups of semantically linked actions).
o Supports keyword boosting/filtering and a context operator for inter-clause linking
(e.g., ~plane crash to link events across sentences).
o Can support synonyms and query expansion via custom ontologies.

5.4 The [Link] Experience

In Fact powered the [Link] website starting June 22, 2005, serving a community of
100,000 users including news reporters and subject matter experts.

 Usability Considerations (5.4.3):

o In Fact defaults to keyword search for users accustomed to it.
o Strategies to migrate users to natural language ("fact") search include:
 Hot Search links: Predefined fact searches (e.g., "Iran and Nuclear program").
 Custom Query Generator: Helps users build IQL queries.
 Tip generation: The most interesting device, where InFact recommends fact
searches based on keywords. For a keyword like "blackhawk," it might suggest
links like "Combat," "Its Usage/Operation," "Military Organizations," or
"Money," leading to tables of relationships.
 Analysis of Query Logs (5.4.4):
o Hot Search links accounted for 36% of all fact search queries executed, indicating a
significant entry point.
o Keyword tips are the most effective way to migrate users to Fact Search. Tip clickers
are more engaged, spend more time, frequently try their own fact searches (87%), and
write better, more valid queries (two-thirds relevant).
o Examples in Help File/Query Generator are largely ineffective in getting users to try
Fact Search, as they often don't relate to user needs. However, those who do try Fact
Search after seeing examples have a better chance of writing good queries (60% valid).
o About 75% of users who try Fact Search directly with IQL syntax without prior
exposure fail to get results, often making errors like inserting nouns in the action field or
specifying too much information. Successful direct users are likely expert analysts.
o Overall traffic to the site increased by almost 40% since InFact search was introduced.
o The percentage of users clicking on tips increased from 4% to 10% over six months.
o Exposing users to summary result displays from natural language queries helps them
learn to use new search functions correctly.
 Module 4

Evaluating Self-Explanations in iSTART: Word Matching, Latent Semantic

Analysis, and Topic Models

 Introduction
o iSTART (Interactive Strategy Trainer for Active Reading and Thinking) is a web-
based, automated tutor designed to improve students' reading comprehension
through self-explanation and reading strategy training (SERT).
o SERT strategies include comprehension monitoring, paraphrasing, elaboration
(domain-specific, common sense), predictions, and bridging.
o The core computational challenge is to provide appropriate feedback to
students on their self-explanations, requiring the system to capture both
meaning and quality.
o Initially, iSTART was proposed to use Latent Semantic Analysis (LSA), but it
first used simpler word matching algorithms. A combination of word matching
and LSA was found to yield better results.
o The goal of algorithm evaluation is to imitate expert judgments of self-
explanation quality on a 4-point scale (0=irrelevant/too short, 1=minimally
acceptable, 2=better/local context, 3=global comprehension). Agreement with
expert evaluations has ranged from 55% to 70%.
o Current efforts aim to improve effectiveness by incorporating Topic Models
(TM), either alone or with LSA, and using multiple LSA spaces from different
genres.
o The evaluation is also expanding to assess specific reading strategies (e.g.,
paraphrasing, bridging, elaboration) to provide more tailored feedback and
individualized curricula.
 iSTART: Feedback Systems
o iSTART was initially designed to use LSA to determine feedback, specifically
by measuring the similarity of a trainee's explanation to predefined "benchmarks"
for each SERT strategy and sentence.
o A preliminary "word-based" (WB) system was developed for the first iSTART
version, providing feedback in experimental settings.
o The second iSTART version integrated both LSA and WB in the evaluation
process, though it still provides only overall quality feedback.
o Current investigations focus on developing systems capable of providing
feedback based on identifying specific reading strategies.
 iSTART: Evaluation of Feedback Systems
 o Two experiments were conducted to evaluate the performance of various
feedback algorithm systems (word-based, LSA, combined, and word-based TM).
o Experiment 1 compared eight systems for overall quality score using self-
explanation protocols from college students that were human-rated on overall
quality.
 Explanations were coded on a 4-point scale (0=vague/irrelevant,
1=sentence-focused, 2=local-focused, 3=global-focused) to reflect
elaboration beyond the current sentence.
 Results showed general improvement from word-based to LSA, and best
performance with combined systems (LSA + word-based). LSA systems
were more stable.
 Both LSA2/WB2-TT and TM2 systems performed well for human ratings
of 0, 1, or 3, successfully identifying poor explanations, paraphrases, and
very good explanations, but were less successful at identifying local-
focused (2) explanations.
o Experiment 2 investigated two systems (LSA2/WB2-TT and TM2) using
explanations from middle-school students, which were scored to identify
particular reading strategies.
 Strategies included paraphrases, irrelevant elaborations, text-based
elaborations (bridging), and knowledge-based elaborations.
 Both systems performed very well, with average agreement of 77%
(LSA2/WB2-TT) and 75% (TM2) with expert ratings for specific
reading strategies. This approaches the 85% agreement criteria for trained
human experts.

Textual Signatures: Identifying Text-Types Using Latent Semantic Analysis to

Measure the Cohesion of Text Structures

 Introduction
o Texts are more than just sequences of sentences; they contain pertinent co-
referring information, causal links between phrases/clauses/sentences, and
temporal features. These are called cohesive elements.
o Cohesion exists on a continuum of presence and can indicate text-type or
intended audience.
o The chapter discusses cohesion, demonstrates a computational tool to measure it,
and introduces a novel approach to identifying text-types by incorporating
contrasting rates of cohesion, leading to "textual signatures".
 Cohesion
o Cohesion is the degree to which ideas in a text are explicitly related, facilitating a
unified situation model for the reader.
o It is particularly important for low-knowledge students reading challenging texts
(e.g., science), as explicit cohesion alleviates the cognitive burden of making
inferences across texts.
o Recent computational linguistics and discourse processing advancements allow
for measuring textual cohesion.
 Coh-Metrix
 o Coh-Metrix is a computational tool that assesses text characteristics using part-
of-speech classifiers and latent semantic analysis.
o It generates indices that measure cohesiveness and readability, used to rate text
difficulty and cohesion levels.
o Coh-Metrix has been used to identify variations in cohesion across written/spoken
texts, distinguish authors, differentiate authentic vs. simplified texts, and
investigate cohesion in science/history textbooks.
o The chapter builds on this to demonstrate how Coh-Metrix cohesion indices can
form prototypical models of text-types, called textual signatures.
 Approaches to Analyzing Texts
o Traditional approaches analyze texts as homogeneous wholes, classifying them
by features into categories like dialect, domain, genre, or author (e.g., Biber for
English dialects, Louwerse et al. for spoken/written texts).
o However, texts are often heterogeneous, composed of parts that serve the whole
by function or form (e.g., Propp's fundamental components, Labov's narrative
theory with abstract, orientation, action, evaluation, resolution, coda).
o Identifying fine-grained discourse markers has been problematic, but coarser-
grained analyses (e.g., beginnings, middles, and ends of texts) have been
productive.
o The hypothesis is that parts of a text are interdependent and structurally
inter-related, and cohesion across these parts indicates the text type. For
example, in a narrative, the abstract and coda might have high co-reference due to
semantic relatedness, while evaluation and resolution might have less.
o A "textual signature" is a prototypical model of text structure derived from the
degree to which textual parts inter-relate.
o Benefits of textual signatures include helping students assess their papers'
structure and helping researchers in text mining to locate appropriate texts or
reduce search space in Question Answering (QA) systems.
 Latent Semantic Analysis
o LSA is a technique that uses a large corpus and singular value decomposition
(SVD) to represent the meaning of words based on their co-occurrences.
o It goes beyond lexical similarities (e.g., chair/chairs) to rate semantic similarity
(e.g., chair/table) and is as reliable as human raters for such judgments.
o LSA has been used to rate summary/essay quality, trace essay elements, optimize
text-reader matches, and predict metaphor difficulty.
o For this study, LSA is adapted to measure cohesion between textual sections,
similar to Foltz et al.'s work on paragraphs. Instead of paragraphs, journal
sections are compared, with predictions made on relative similarity rather than
assuming cohesion decreases with distance.
 Predictions
o The abstract section was chosen as the primary source for comparison because
its function is to relate key elements of all other paper sections.
o Predictions for the textual signature of scientific reports:
 Greater reference between abstracts and introduction sections (AI) and
discussion sections (AD).
  Less reference to the results section (AR), as key findings are often
restated in the discussion.
 Weakest co-reference to the methods section (AM), as experimental
methods are often standardized and less critical to an abstract's gist.
 Results of Experiment 1
o A repeated measures ANOVA on LSA cosines of abstract-to-section
comparisons (AI, AM, AR, AD) confirmed the predictions.
o There was a main effect of comparison type (F(3,66)= 54.701, p<.001).
o Pairwise contrasts showed reliable differences, except between AI and AD.
o The observed pattern (AI ≈ AD > AR > AM) is referred to as the textual
signature for scientific reports.
o An analysis of section lengths confirmed that the LSA signature did not simply
reflect relative text length.

Automatic Document Separation: A Combination of Probabilistic Classification

and Finite-State Sequence Modeling

 Introduction
o The problem is to automatically separate a long sequence of scanned paper
pages into distinct documents and assign them appropriate types.
o The automated solution involves:
1. Scanning batches of pages.
2. Using an OCR engine to read text from each page.
3. A classification engine to determine likely document types (e.g.,
Appraisals, Tax Forms).
4. A separation mechanism to insert virtual boundaries between documents.
5. Labeling and delivering separated documents for further processing (e.g.,
information extraction).
 Related Work
o Traditionally, processing focused on structured forms with well-defined
physical areas. For these, separation often involves identifying the document type
from the first page, which defines its fixed length.
o However, for semi-structured (e.g., appraisals) or unstructured (e.g., legal
documents) forms, layout-based recognition is difficult or unlikely to succeed.
o Therefore, content-based recognition is favored over rule-driven layout-based
recognition for these document types.
o Treating separation and extraction as distinct steps is advantageous and can
simplify rule writing for information extraction.
o A direct approach could be a segmentation problem using Maximum Entropy
methods to classify page transitions as boundary/non-boundary.
o Another method involves calculating a similarity measure between consecutive
pages (considering document structure, layout, and content) and using
agglomerative clustering to group pages, bounded by manual thresholds.
 Data Preparation
 o The input is OCR-generated text from scanned page images, with data
primarily from the mortgage processing industry (e.g., Appraisals, Truth in
Lending).
o Preprocessing steps: tokenization (simple regular expression to eliminate special
characters) and stemming (Porter algorithm for English).
o Text representation: bag-of-words model; each token type is a feature, its value
is the number of occurrences on the page, filtered by a stopword list.
o These processes introduce significant abstractions: loss of morphological detail
(e.g., "address" from "addressing"), loss of linear text structure (word order), and
de-emphasis of syntactic information.
o Benefits of abstraction: reduces the number of parameters to estimate during
training and thus reduces the number of training samples required (acceptable
results with 20-30 examples per document type).
o It is acknowledged that sequence-aware modeling can be superior and
necessary for certain problems (e.g., distinguishing document types based on
filled columns) but requires hundreds of samples.
 Document Separation as a Sequence Mapping Problem
o The problem is viewed as mapping an input sequence of scanned pages to an
output sequence of document types.
o Probabilistic models are used to determine the probabilities of possible output
sequences given an input sequence.
o The approach aims to find the most likely output sequence (sequence of
document types) to effectively separate pages.
o Models gradually increase complexity by incorporating historical document types:

 p(dj | pcj): document type dj depends only on page content pcj.

 p(dj | dj-1, pcj): dj depends on previous document type dj-1 and
pcj.
 p(dj | dj-1, dj-2, pcj): dj depends on two previous document types
and pcj.
o A key improvement is altering the output language by splitting each document
type into three symbols: Start, middle, and end page (e.g., TaxForm1,
TaxForm2, TaxForm3). This is because forms often have distinctive first and last
pages.
o The model p(d'j | pcj) uses this new output language and page type
consistency constraints, allowing it to separate subsequent instances of the
same document type, which the p(dj | dj-1, dj-2, pcj) model cannot.
 Results
o Evaluation of probability models (F1-values) showed three main results:

1. Including a history of document types improves performance (e.g.,

trigram model yielded 31% improvement over unigram).
2. Specializing page descriptions (Start, middle, end) improves
performance and allows separation of consecutive instances of the same
document type.
 3. Conditioning on the content of surrounding pages improves
performance (around a 3.5% boost in F1-value).
o The best model in experiments (Eq. 8.8) uses surrounding page content, but its
high CPU/memory usage for training makes it too costly for deployment for a 3%
gain.
o For production deployment, model Eq. 8.6 was chosen as it is the best one-page-
content model and its page type distinction helps with integration into extraction-
oriented systems.
o Detailed results (Table 8.6) for the final deployment model show that sequence-
level measures are much stricter than page-level measures.
o Comparison: while classification of documents with given boundaries achieved
95% F1-value (Table 8.3), classifying each page separately and inferring
boundaries with a comparable model (Eq. 8.2) initially only reached 63% F1-
value. This was raised to 92% on the page level with model Eq. 8.6 through
careful probability model selection.
o SVM multi-class classifier scores are calibrated to class membership probabilities,
allowing thresholding to control errors and manual review, achieving >95%
precision with >80% recall.

Evolving Explanatory Novel Patterns for Semantically- Based Text Mining

 Related Work
o Traditional Text Mining (KDT) often uses Bag-of-Words (BOW)
representations, which are easy to analyze but restrict discovered knowledge to
numerical associations, failing to provide explanations. They lose underlying
linguistic information.
o There's a distinction between Information Access (finding documents) and KDT
(discovering novel information and patterns across documents).
o Information Extraction (IE) is a Natural Language (NL) technology that
performs shallow analysis using defined patterns to resolve implicit discourse-
level information (e.g., anaphora) and extract relevant information (e.g., names,
events, entities).
o Hearst (1992) proposed a domain-independent method for automatically
discovering WordNet-style lexicosemantic relations by searching for
lexicographical patterns in unrestricted text. This can aid lexicographers but still
requires manual input for selecting relations and word pairs.
o WordNet has been used as a commonsense knowledge base for relation-driven
inference by Harabagiu and Moldovan. Mooney and colleagues attempted to
combine ontologies, IE, and machine learning to mine prediction rules, proposing
a novelty measure based on semantic distances in WordNet. However, this highly
depends on WordNet's organization, potentially leading to misleading novelty
decisions if text information is not included.
o The role of "learning" in many KDT systems is often unclear, relying on primitive
search strategies rather than comprehensive exploration of the search space.
o Genetic Algorithms (GAs) are a recent research topic for applying evolutionary
methods to text mining. GAs offer advantages such as global search, parallel
 exploration, robustness to noisy data, and the ability to assess solution quality.
Compared to other approaches, GAs can provide more robust results by exploring
a wider number of possible hypotheses and automatically learning IE patterns.
 A Semantically Guided Model for Effective Text Mining
o A semantically guided, evolutionary model for KDT is proposed, which is
domain-independent but genre-based.
o It does not rely on external resources or domain knowledge beyond the text
corpus and generated training data.
o The model includes strategies for automatically evaluating the quality of
"novel" hypotheses.
o The process begins with an Information Extraction (IE) task, which applies
extraction patterns to generate a rule-like representation for each document
(containing conditions and conclusions). These rules, along with other training
data, guide the GA-based discovery.
o An initial population of hypotheses is created by building random hypotheses
from these initial rules, incorporating predicate and rhetorical information.
o Text Preprocessing and Training
 The preprocessing phase extracts important information and generates
training data and the initial GA population.
 It focuses on scientific/technical abstracts due to their well-defined
macro-structure (genre-dependent rhetorical structure: background,
methods, achievements, conclusions).
 This macro-structure and its rhetorical roles are domain-independent but
genre-based.
 Key constituents identified from text examples:
 Rhetorical Roles: Discourse-level knowledge indicating author
assertions (e.g., goal, object of study, method, conclusion).
 Predicate Relations: Actions (predicate and arguments) linked to
identified roles, stating relations between terms.
 Causal Relations: IF-THEN rules extracted from individual
abstracts (e.g., IF goals and methods THEN conclusions).
 An IE module tags documents (using a POS tagger like Brill Tagger),
produces an intermediate "template" representation, and converts it into a
general rule. This uses hand-crafted domain-independent extraction
patterns.
 Key training data is captured from the document corpus and the semantic
information in the rules to guide discovery and similarity judgments.
 Training Information from the Corpus: Utilizes a semi-
structured LSA representation where predicate information
(verbs) and arguments (terms) are represented separately. Semantic
similarity (SemSim) between predicates/arguments is calculated by
computing the cosine between their meaning vectors (sum of term
vectors for arguments, sum of predicate and argument vectors).
 Training Information from the Rules:
  Creating the initial population of hypotheses:
Components of initial rules (rhetorical roles, predicate
relations) are stored as a "database".
 Computing correlations: Correlations between rhetorical
roles and predicate relations are computed.
 Computing co-occurrences of rhetorical information:
Conditional probabilities Prob(rp | rq) for role
sequences are generated to evaluate the coherence of new
hypotheses, acknowledging that the order of rhetorical roles
affects meaning. For example, "goal-method" sequence
(0.54) is more likely than "goal-conclusion" (0.08).
o Knowledge Discovery and Automatic Evaluation of Patterns
 The KDT approach is guided by semantic and rhetorical information, with
"soft constraints" for offspring coherence.
 The GA starts with a semi-random population of hypotheses, applies
constrained GA operations, and evaluates hypotheses using an
evolutionary multi-objective optimization strategy based on the
Strength Pareto Evolutionary Algorithm (SPEA). SPEA handles diversity
and fitness assignment in a representation-independent way.
 New operations for guided discovery include:
 Selection: selects best parent hypotheses based on multi-objective
fitness (Pareto Optimum).
 Crossover: recombination of hypotheses' conditions/conclusions,
restricted to preserve semantic coherence. Two types:
 Swanson's Crossover: Infers IF A THEN C from IF A
THEN B and IF B' THEN C (where B' is semantically
similar to B) if conclusions of AB have high semantic
similarity with conditions of BC.
 Default Semantic Crossover: Recombination if overall
hypotheses have high semantic similarity.
 Evaluation uses EMOO-based metrics to assess hypotheses' fitness in a
domain-independent way without external domain knowledge. Eight
criteria are defined, producing an 8-dimensional vector of objective
functions:
 Relevance: How important the hypothesis is to target concepts,
estimated by semantic closeness between hypothesis
predicates/arguments and target concepts using LSA meaning
vectors.
 Structure: Measures how much of the original rules' rhetorical
structure is exhibited, using a Markov chain model of role
sequences (e.g., Prob(r1) * Prod Prob(ri | ri-1)).
 Cohesion: Measures the degree of "connection" between rhetorical
roles and predicate actions, formally Prob(Pi | ri).
 Interestingness: Defined as the degree of unexpectedness
(semantic dissimilarity between antecedent and consequent); lower
similarity implies more interesting.
 Coherence: Measures if elements relate semantically, calculated as
the average LSA-based semantic similarity between consecutive
predicate elements.
 Coverage: How much the hypothesis is supported by the training
rules (representing original documents), by checking if hypothesis
predicates are approximately contained in rules.
 Simplicity: Shorter/easier-to-interpret hypotheses are preferred,
based on hypothesis length.
 Plausibility of Origin: If a hypothesis resulted from Swanson's
crossover, higher semantic similarity between parent's consequent
and other parent's antecedent indicates more precise evidence and
novelty.