Named Entity Recognition Sequence Labeling Ner
# Named Entity Recognition: Sequence Labeling & NER
## Introduction & Motivation
Named Entity Recognition: identify entity boundaries and types. Sequence labeling: per-token classification. BIO tagging: Begin, Inside, Outside. Applications: information extraction, question answering, entity linking.
Motivation: Extract structured information from text. Essential for NLP pipelines.
Applications: Information extraction, QA systems.
---
## Core Concepts & Theory
### Token Classification
Per-token label prediction; sequence task.
### BIO Tagging
Encode entity boundaries; standard scheme.
### CRF Decoding
Viterbi algorithm; global optimization.
---
## Mathematical Formulation
Token classification loss:
$$L = -\sum_i \log p(y_i | x_1, \ldots, x_n)$$
CRF score:
$$ ext{Score}(y) = \sum_i heta_{y_{i-1} o y_i} + \sum_i \phi_i(y_i)$$
Viterbi decoding:
$$y^* = \arg\max_y ext{Score}(y)$$
---
## Advanced Theory & Extensions
### BiLSTM-CRF
Bidirectional LSTM + CRF output.
### Transformers for NER
BERT + sequence tagging.
### Multi-Task Learning
Joint NER + relation extraction.
---
## Computational Considerations
Token classification: O(T·D) where T = token count.
CRF: O(T·|Y|²) Viterbi decoding.
BiLSTM-CRF: O(T·H²) + CRF.
---
## Practical Implementation Strategies
### Word Pieces
Subword tokenization; OOV handling.
### Sequence Length
Padding/truncation; manage variable lengths.
### Imbalanced Entity Types
Weighted loss; weighted sampling.
---
## Benchmark Datasets & Evaluation
CoNLL 2003: Standard NER benchmark.
WikiAnn: Multilingual NER.
WNUT: Emerging entities.
---
## Key Challenges & Limitations
### Nested Entities
Overlapping entity spans; difficult.
### Domain Shift
Models overfit training domain.
### Low-Resource Languages
Limited labeled data.
---
## Hyperparameter Tuning
Hidden dimension: 128-256; model capacity.
Dropout: 0.1-0.3; regularization.
CRF transitions: Learn or initialize.
---
## Real-World Applications & Case Studies
Information Extraction: Web data extraction.
Question Answering: Entity recognition for QA.
Entity Linking: Link entities to KB.
---
## Integration with Other Methods
NER + Linking → entity disambiguation.
NER + Relation Extraction → IE pipeline.
---
## Summary & Key Takeaways
Named entity recognition via sequence labeling and CRF enables structured information extraction through token-level classification and global decoding.
Principles:
1. Token classification: per-token prediction.
2. BIO tagging: encode boundaries.
3. CRF: global constraint satisfaction.
4. BiLSTM: bidirectional context.
5. Transformers: BERT-based NER.
---
---
## Appendix: Practical Labs
### Lab 1: BIO Tagging
import numpy as np
def bio_decode(predictions, text_tokens):
"""Decode BIO tags to entities"""
tags = ['O', 'B-PER', 'I-PER', 'B-LOC', 'I-LOC']
entities = []
current_entity = None
current_type = None
start_idx = 0
for idx, pred in enumerate(predictions):
tag = tags[pred]
token_type = tag.split('-')[1] if '-' in tag else None
if tag == 'O':
# End current entity
if current_entity is not None:
entities.append({
"text": " ".join(text_tokens[start_idx:idx]),
"type": current_type,
"start": start_idx,
"end": idx
})
current_entity = None
elif tag.startswith('B-'):
# Begin new entity
if current_entity is not None:
entities.append({
"text": " ".join(text_tokens[start_idx:idx]),
"type": current_type,
"start": start_idx,
"end": idx
})
current_entity = token_type
current_type = token_type
start_idx = idx
elif tag.startswith('I-'):
# Continue entity
if current_type != token_type and current_entity is not None:
entities.append({
"text": " ".join(text_tokens[start_idx:idx]),
"type": current_type,
"start": start_idx,
"end": idx
})
start_idx = idx
current_type = token_type
if current_entity is not None:
entities.append({
"text": " ".join(text_tokens[start_idx:]),
"type": current_type,
"start": start_idx,
"end": len(text_tokens)
})
return entities
# Test
np.random.seed(42)
predictions = [0, 1, 2, 0, 3, 4, 0]
tokens = ["John", "lives", "in", "New", "York", "City", "."]
entities = bio_decode(predictions, tokens)
assert len(entities) > 0, "Entities extracted"
print("✓ BIO decoding working")
if __name__ == "__main__":
print("Lab 1: BIODecoding - PASSED")### Lab 2: Sequence Labeling Metrics
import numpy as np
def compute_entity_metrics(pred_entities, true_entities):
"""Compute precision, recall, F1 for entities"""
pred_set = set((e["start"], e["end"], e["type"]) for e in pred_entities)
true_set = set((e["start"], e["end"], e["type"]) for e in true_entities)
tp = len(pred_set & true_set)
fp = len(pred_set - true_set)
fn = len(true_set - pred_set)
precision = tp / (tp + fp + 1e-8)
recall = tp / (tp + fn + 1e-8)
f1 = 2 * precision * recall / (precision + recall + 1e-8)
return precision, recall, f1
# Test
np.random.seed(42)
pred = [{"start": 0, "end": 2, "type": "PER"}]
true = [{"start": 0, "end": 2, "type": "PER"}]
prec, rec, f1 = compute_entity_metrics(pred, true)
assert 0 <= prec <= 1, "Precision in [0,1]"
print("✓ Entity metrics working")
if __name__ == "__main__":
print("Lab 2: EntityMetrics - PASSED")### Lab 3: CRF Transition Scores
import numpy as np
def crf_transition_matrix(num_tags=5):
"""Learn CRF transition scores"""
# Initialize transition matrix
transitions = np.random.randn(num_tags, num_tags) * 0.1
# Make valid transitions more likely
# Example: O -> B-* allowed, I-* -> I-same encouraged
for i in range(num_tags):
transitions[i, i] += 1.0 # Self-transitions encouraged
return transitions
# Test
np.random.seed(42)
transitions = crf_transition_matrix(num_tags=5)
assert transitions.shape == (5, 5), "Transition matrix shape"
print("✓ CRF transitions working")
if __name__ == "__main__":
print("Lab 3: CRFTransitions - PASSED")### Lab 4: Viterbi Decoding
import numpy as np
def viterbi_decode(scores, transitions, num_tags=5):
"""Simplified Viterbi decoding"""
T = len(scores)
# Viterbi table
viterbi = np.full((T, num_tags), -np.inf)
backpointer = np.zeros((T, num_tags), dtype=int)
# Initialize
viterbi[0] = scores[0]
# Forward pass
for t in range(1, T):
for curr in range(num_tags):
# Find best previous state
for prev in range(num_tags):
score = viterbi[t-1, prev] + transitions[prev, curr] + scores[t, curr]
if score > viterbi[t, curr]:
viterbi[t, curr] = score
backpointer[t, curr] = prev
# Backtrack
path = []
curr = np.argmax(viterbi[-1])
for t in range(T-1, -1, -1):
path.append(curr)
curr = backpointer[t, curr]
return list(reversed(path))
# Test
np.random.seed(42)
scores = np.random.randn(10, 5)
transitions = np.random.randn(5, 5)
path = viterbi_decode(scores, transitions)
assert len(path) == 10, "Path length"
assert all(0 <= p < 5 for p in path), "Valid tags"
print("✓ Viterbi decoding working")
if __name__ == "__main__":
print("Lab 4: ViterbiDecoding - PASSED")