Natural Language Processing | Jacob Eisenstein, draft 2018.
Sections from this book were read during during Text and Multimedia Mining .
Chapter 4: Linguistic applications of classification
4.2 Word sense disambiguation
Lexical semantics is concerning with meanings of words.
The problem of word sense disambiguation "is to identify the correct sense for each word token in a document" (73).
That is a different problem from part-of-speech ambiguity.
Senses are properties of lemmas rather than words, and PoS-ambiguity concerns correctly identifying the right PoS and lemma. This problem is prior to word sense ambiguity.
A lemma is polysemous if it occurs in multiple synsets (sets of synonyms, e.g. recorded in WordNet). Cf. polysemy.
There is debate on whether it's sensible to accurately distinguish word senses in a "task-neutral way" (74).
Lexical semantic relations:
- Antonymy: opposite meaning
- Hyponymy: Red is a special case of Color
- Hypernymy: Color is a general case of Red
- Meronymy: Wheel is a part of Bicycle.
- Holonymy: Bicicly includes Wheel
We can try to find these relations by:
- Finding characteristic patterns between words
- X such as Y
- X but Y
- Analyze a term's distributional statistics
- Which words co-occur frequently?
Word sense disambiguation can be seen as a classification task.
If we treat the context of an (ambiguous) word as a pseudo-document we can build feature vectors, and have as a classification task to classify the context.
One example sentence is about manufacturing plants, whereas another sentence is about endangered plants. The words "manufacturing" and "endangered" give a strong hint towards the appropriate context. For example, in the context of biology "endangered" will likely be used often, whereas "manufacturing" will not. This requires training with labeled data.
Beyond bag-of-words, the collocation of a word w.r.t. the context word of interest can be added to the feature vector. We can also include a dependency path.
Semantic concordance: words tagged with a word sense from a thesaurus/dictionary.
Main problem w.r.t. machine learning approach: "each polysemous lemma requires its own training set: having a good classifier for the sense of serve is no help towards disambiguating plant". (76)
Therefore, there's more hope for unsupervised or semi-supervised methods.
"Unsupervised methods typically lean on the heuristic of “one sense per discourse”, which means that a lemma will usually have a single, consistent sense throughout any given document (Gale et al., 1992)." (76)
"Based on this heuristic, we can propagate information from high-confidence instances to lower-confidence instances in the same document (Yarowsky, 1995)." (76)
4.3 Design decisions for text classification
-
First we define what constitutes a word. This is the prime purpose of a tokenizer.
-
Text normalization
Case conversion. Upper case at beginning of a sentence is likely irrelevant. But Apple/apple is a meaningful distinction.
Examples: see differences between porter stemmer, Lancaster stemmer, WordNet stemmer on page 78.
Chapter 17: Information extraction
wk3 TMM: 17.1-17.4, excluding the neural approaches.
17.1 Entities
Entity recognition: identify mentions of entities in text.
Named entity recognition: entities which are an organization, a specific location or a specific date.
We want to:
- Identify entities
- Link then together in a knowledge base
- The strings to be linked are called mentions.
- We speak of named entity linking if only named entities are linking candidates
- In wikification any string can be a mention, e.g. corresponding to a wikipedia page
- Identify if a mention is not yet in the knowledge base, called a NIL entity.
How to choose one possible link amongst many possible links (cf. ambiguous).
Entity linking can be done supervised or unsupervised.
Unsupervised entity linking is closely related to the problem of cross-document coreference resolution, where the task is to identify pairs of mentions that corefer, across document boundaries (Bagga and Baldwin, 1998b; Singh et al., 2011). (406)
Entity linking as a ranking problem
Relevant components of a scoring function, for each candidate in a list of candidate entities:
- target entity
- description of the mention
- description of the context
Candidate identification
How do we restrict the set of candidate entities?
- Name dictionary: many-to-many mapping from strings to the entities that they might mention
- So includes all ambiguities with different mappings
- Can be mined e.g. from Wikipedia
- You may allow partial matches or approximate matching to increase recall
- But this will increase risk of false positives as well
Features
Feature-based entity linking uses local feature information:
- (String) similarity of mention string with entity name in name dictionary
- String: "Atlanta". Rank "Atlanta" > "Atlanta Hawks"
- Popularity of the entity
- Rank "Atlanta, Georgia" over "unincorporated community of ATLANTA, OHIA" (408).
- Entity type (output of entity recognition system)
- Atlanta (city) > Atlanta (magazine) if the context of the mention is "location".
Non-local information can be used bye computing the similarity between the mention context and e.g. the Wikipedia page describing the candidate entity.
Collective Entity Linking
Instead of figuring out the entity links for each mention, we can try to collectively link these references together in such a way that they are most coherent.
Example from page 408: "Washington, Adams, Jefferson". Each of these entities has a long list of candidates. However, when regarded together, it is very likely that these refer to US presidents. This would be the most coherent.
A common approach is to optimize a global objective where we take into account the scoring functions of the individual assignments, plus a coherence measure, e.g. a pairwise compatibility function.
Options for such a compatibility function (p. 409):
- See how much categories on Wikipedia they have in common
- Number of shared incoming hyperlinks on Wikipedia
- Inner product of their embeddings (in a neural architecture)
- Use a probabilistic topic model
This type of optimization is clearly NP-hard.
Approximation methods:
- Integer linear programming
- Gibbs sampling
- Graph-based algorithms
17.2 Relations
After identifying entities we identify their relations.
Could use ontologies, e.g. Automatic Content Extraction (ACE) ontology (Linguistic Data Consortium, 2005).
Example relations:
- Cause-effect
- Product-producer
- Content-container
- Component-whole
The difference with semantic role labeling is that relation extracting is restricted to a set of predefined relation types (in an ontology?)
Pattern-based relation extraction
The old approach was to handcraft patterns that indicate a certain relationship; and extensions thereof (using synonyms or lemmas for triggering the same patterns).
Relation extraction as a classification task
If we have two "spans" where one would correspond to the first argument of the relation, and the other to the second argument of the relation; then we can have a classifier try to determine to which relation these spans may belong. This may be based on several features.
Are entities recognized? Do they appear in a gazetteer of entity names? Is there a dependency path between the arguments? And so on.
Q: Is "gazetteer" different than a "name dictionary"?
So N.B. relation extraction is defined on two spans of text, not solely on entities.
Kernels
Instead of using local features, which requires a weight vector indicating connections from all local features to dependency paths/relations, we can create a similarity function for any two instances. If this meets some additional requirements (Gram matrix must be symmetric) this is a kernel function.
Kernel-based classification can be viewed as a weighted form of the nearest-neighbor classifier (Hastie et al., 2009), in which test instances are assigned the most common label among their near neighbors in the training set. This results in a non-linear classification boundary. The parameters are typically learned from a margin-based objective (see section 2.4), leading to the kernel support vector machine. To generalize to multi-class classification, we can train separate binary classifiers for each label (sometimes called one-versus-all), or train binary classifiers for each pair of possible labels (one-versus-one). (414)
Knowledge base population
KBP: "the task of filling in Wikipedia-style infoboxes" (416)
- entity linking
- slot filling
Slot filling differs from relation extraction because:
- Defined on entities and not spans of text
-
Evaluated on type level (entity pairs) instead of token level (sentences)
-
Often done in response to a query; so the problem can be scoped to text passages that are retrieved as being relevant.
- Multiple text passage may provide evidence for different relation types, but the system must predict a single relation type. See information fusion.
- "Labeled data is usually available in the form of pairs of related entities, rather than annotated passages of text. Training from such type-level annotations is a challenge: two entities may be linked by several relations, or they may appear together in a passage of text that nonetheless does not describe their relation to each other." (417)
Information fusion
So it may be the case that there's various text passages that provide evidence for multiple relations between two entities. We must weight these results and decide on a single relation type to fill in the slot.
When we retrieve multiple relevant passages, we could extract a relation for each of them, and then do a weighted aggregation where higher confidence relations are weighed more. The idea is that if a relation occurs with high confidence in multiple documents, this is likely the most appropriate relation to pick.
Tips: "Precision can be improved by introducing constraints across multiple relations. For example, if we are certain of the relation PARENT(e1; e2), then it cannot also be the case that PARENT(e2; e1)." (418) Or instead take into account correlations between relations. Such contrainst can be incorporated by Integer Linear Programming.
Distant supervision
TBC, p. 418