DeepType: Multilingual Entity Linking by Neural Type System Evolution

Jonathan Raiman; Olivier Raiman

Source-linked AI summary

DeepType: Multilingual Entity Linking by Neural Type System Evolution

Jonathan Raiman, Olivier Raiman

arXiv:1802.01021v1Feb 3, 2018cs.CL

TL;DR

Entity linking and other neural tasks struggle to use structured knowledge without difficult representation choices and extensive labeling. DeepType jointly designs a symbolic type system and trains a neural classifier, then uses the types to constrain predictions. On three entity-linking benchmarks, it outperforms existing approaches, supports adding entities without retraining, and reaches near-perfect Oracle disambiguation accuracy on two datasets.

Problem
Integrating structured symbolic knowledge with neural representations requires representation choices and large amounts of hand-labeled data.
Method
DeepType formulates type-system design and classifier training as a mixed integer problem, then uses the resulting type system to constrain neural-network outputs.
Results
DeepType outperforms existing solutions on WikiDisamb30, CoNLL (YAGO), and TAC KBP 2010, while incorporating new entities without retraining.
Takeaways & Limitations
99.0% CoNLL (YAGO) and 98.6% TAC KBP 2010 disambiguation accuracy with Oracle types indicates type prediction is the remaining bottleneck for entity linking.
Takeaways & Limitations
The authors identify limited type-system expressiveness and the classifier’s conditional-independence assumption as directions for future improvement.

Abstract

from arXiv · show

The wealth of structured (e.g. Wikidata) and unstructured data about the world available today presents an incredible opportunity for tomorrow's Artificial Intelligence. So far, integration of these two different modalities is a difficult process, involving many decisions concerning how best to represent the information so that it will be captured or useful, and hand-labeling large amounts of data. DeepType overcomes this challenge by explicitly integrating symbolic information into the reasoning process of a neural network with a type system. First we construct a type system, and second, we use it to constrain the outputs of a neural network to respect the symbolic structure. We achieve this by reformulating the design problem into a mixed integer problem: create a type system and subsequently train a neural network with it. In this reformulation discrete variables select which parent-child relations from an ontology are types within the type system, while continuous variables control a classifier fit to the type system. The original problem cannot be solved exactly, so we propose a 2-step algorithm: 1) heuristic search or stochastic optimization over discrete variables that define a type system informed by an Oracle and a Learnability heuristic, 2) gradient descent to fit classifier parameters. We apply DeepType to the problem of Entity Linking on three standard datasets (i.e. WikiDisamb30, CoNLL (YAGO), TAC KBP 2010) and find that it outperforms all existing solutions by a wide margin, including approaches that rely on a human-designed type system or recent deep learning-based entity embeddings, while explicitly using symbolic information lets it integrate new entities without retraining.

1 Introduction

DeepType integrates symbolic information into neural-network reasoning through an automatically designed type system. It formulates type-system design and classifier training jointly, then evaluates the approach across languages, search methods, and entity-linking benchmarks.

Approach: The approach reformulates joint type-system creation and neural-network training as a mixed integer problem.Discrete variables select ontology relations used as types, while continuous variables train the classifier.
Experiments: DeepType evaluates multilingual transfer through monolingual English and bilingual English–French training, with Oracle evaluation on German and Spanish datasets.The experiments test whether a type system optimized for one language generalizes to others.
Experiments: The study compares stochastic optimization with heuristic search and investigates symbolic-information transfer through DeepType pretraining for Named Entity Recognition.NER experiments use CoNLL 2003 and OntoNotes 5.0.
Approach: DeepType automatically designs a type system for a target task and uses it to constrain neural-network behavior without human effort.The system integrates symbolic knowledge into neural reasoning through selected ontology roots and edges.
Results: DeepType reduces entity-linking disambiguation complexity from O(N^2) to O(N), incorporates new entities without retraining, and outperforms existing solutions by a wide margin.The comparison includes human-designed type systems and neural entity-embedding approaches.
Results: 99.0% CoNLL (YAGO) and 98.6% TAC KBP 2010 disambiguation accuracy is reached when entity types are predicted by an Oracle.The authors suggest that improving type prediction accuracy could nearly solve entity linking.

2 Task

Entity Linking identifies the entities mentioned in documents and disambiguates each mention among candidate knowledge-base entities. DeepType extends this task with entity types that constrain candidates and can support cross-language knowledge representations.

Entity Linking: Entity Linking locates document mentions and selects the ground-truth knowledge-base entity from each mention’s proposal set.For example, “Washington” may refer to Washington, D.C. or George Washington.
Entity Linking: Disambiguation uses mention–entity evidence, including how frequently a mention refers to an entity in a large corpus.The supplied task description introduces this criterion before continuing beyond the excerpt.
Multilingual Setting: The task includes testing whether a knowledge representation optimized for one language works across languages.This question is stated as part of the multilingual task framing.
EL with Types: DeepType associates entities with types such as Person or Place so predicted types can rule out invalid answers and ease linking.For a mention like “Washington,” type information can distinguish candidate entities.
EL with Types: Type knowledge prunes each mention’s proposal set to a constrained subset and can contribute to probabilistic entity ranking.The ranking combines type-system predictions with the entity model.
Related Work: Prior work found that regular NER types were unhelpful, whereas finer-grained FIGER types improved entity-linking performance.The comparison used 112 FIGER types associated with entities.

3 DeepType for Entity Linking

DeepType builds a type system from ontology relations and uses predicted types to constrain entity linking. Its mixed-integer design combines symbolic disambiguation power with type learnability, then fits the classifier through gradient descent.

Type System: DeepType constrains entity prediction with a type system, so contextually predicted types can distinguish entities such as Animal and Road Vehicle for “Jaguar”.The type system assigns labels through relations and organizes mutually exclusive types into axes.
Type System: Each type axis selects a root and ontology edge type that determine membership or exclusion among entities.The system restricts types to parent-child relations over Wikipedia and Wikidata.
Mixed-Integer Formulation: The design problem jointly chooses discrete type-system relations and continuous classifier parameters to improve disambiguation while keeping selected types predictable.The objective favors relations that are useful for disambiguation and easy for a classifier to learn.
Optimization: Because the original formulation cannot be solved exactly, DeepType uses heuristic or stochastic discrete optimization followed by gradient descent for the type classifier and entity model.The search is informed by an Oracle and a Learnability heuristic.
Optimization: The objective penalizes each additional type axis because many axes can increase disambiguation power while making training and inference harder.The penalty also discourages solutions that lack higher-level concepts offering similar accuracy with fewer axes.
Inference: The Oracle prunes candidate entities whose types do not match the gold entity, then applies the entity prediction model to the remaining candidates.Types fully disambiguate a mention when only one matching candidate remains.

4 Results

The experiments evaluate search methods for discovering type systems and test their learnability, generalization, multilingual transfer, and downstream NER usefulness. Machine-discovered systems achieve near-perfect entity-linking accuracy, outperform human-designed systems and prior approaches, and transfer across languages and tasks.

Search methodology: Search methods are compared by scalability, target-task accuracy, classifier learnability, and generalization to held-out entity-linking datasets.The experiments include stochastic optimization, heuristic search, a human-designed system, and random or empty-set baselines.
Search methodology: λ = 0.00007 provides the selected tradeoff between type-system size and accuracy for subsequent comparisons.Accuracy grows more slowly below this value while system size continues increasing.
Entity Linking: Machine-discovered type systems achieve 97-99% accuracy across datasets, with held-out Wikipedia and standard-set performance remaining similar.The results support generalization of the discovered type systems and show that they outperform human-designed systems on three benchmark datasets.
Entity Linking: Machine-discovered systems outperform previous entity-linking approaches on most datasets, while human-designed systems already outperform earlier methods.The comparisons include deep-learning and embedding-based approaches, as well as count- and coherence-based techniques.
Multilingual transfer: English-optimized type systems operate at similar accuracies in French, German, and Spanish, and bilingual training does not hurt performance.The type axes derive from a multilingual knowledge base, enabling cross-lingual supervision; bilingual training might be helpful.
Named Entity Recognition Transfer: DeepType pretraining adds 3-4 F1 points in NER and outperforms the state of the art on the OntoNotes development split, but does not fully replace lexicons.The model consistently improves over baselines and partially recovers lexicon performance gains.

5 Related Work

DeepType differs from prior neural methods by designing a task-specific type system through discrete optimization and learnability rather than relying on a fixed or human-engineered symbolic structure.

Neural Network Reasoning with Symbolic structures: Earlier approaches integrate hierarchies through loss functions, whereas DeepType optimizes the ontology structure to meet task-specific accuracy goals.The comparison includes specificity-accuracy tradeoffs and hierarchical loss shaping with fixed structures.
Neural Network Reasoning with Symbolic structures: DeepType constrains neural outputs with types during decoding, while its machine-designed type system avoids the human engineering required by earlier grammar-based methods.Prior work uses NER or FIGER types and type-aware grammars; DeepType designs its types for disambiguation accuracy.
Neural Entity Linking: Unlike prior entity-linking systems based on attention or distributed word, entity, and document representations, DeepType uses type constraints alongside contextual neural representations.The related approaches include attention-based disambiguation and embeddings of words with entities or documents with entities.

6 Conclusion

The paper presents DeepType as a mixed-integer framework for automatically designing symbolic type systems and integrating them into neural reasoning. On entity linking and NER, it reports strong benchmark gains, cross-lingual transfer, and machine-designed systems that outperform human-designed ones.

Contributions: DeepType jointly formulates type-system design and neural classifier training so model outputs obey selected symbolic structure.The formulation uses discrete optimization for symbolic choices and continuous optimization for classifier parameters.
Transfer and type-system design: DeepType pretraining improves NER and yields a new state of the art on the OntoNotes development set, suggesting cross-domain transfer of symbolic information.The conclusion also reports that machine-designed type systems outperform human-designed systems on three benchmark datasets.
Entity Linking: On WikiDisamb30, CoNLL (YAGO), and TAC KBP 2010, DeepType outperforms existing solutions while reducing EL resolution complexity from O(N^2) to O(N).The comparison includes human-designed type systems and word/entity or document/entity embedding approaches.
Entity Linking: Oracle disambiguation accuracy reaches 99.0% on CoNLL (YAGO) and 98.6% on TAC KBP 2010.The authors present the gap between learned type classifiers and the Oracle as an important remaining issue.
Limitations and future work: Future work includes more expressive hierarchical type systems and relaxing the classifier’s conditional independence assumption.The paper also proposes testing DeepType on other problems where symbolic structure may be beneficial.

A Training details and hyperparameters

The implementation uses Adam optimization with regularization and data augmentation, while training is stopped using held-out validation criteria tailored to NER and type classification.

Optimization: Models use Adam with learning rate 10^-4, β1 = 0.9, β2 = 0.999, and ϵ = 10^-8, with learning-rate annealing every 10,000 iterations.Input-embedding dropout and synthetic spelling-related noise are used to reduce overfitting and improve robustness.
Regularization and stopping: NER training uses Gaussian LSTM-weight noise with σ = 10^-6 and early stopping when validation F1 stops increasing.The type-classification model is instead stopped when held-out type-training F1 no longer improves.
Training duration: Type-classifier training took approximately three days on one Titan X Pascal under the held-out-data stopping criterion.The type-classification models did not overfit, so training was stopped based on held-out F1 rather than standard NER validation stopping.

Architecture

DeepType’s architecture combines compact character and text-window representations with a search procedure for discovering type systems. The classifier configuration includes regularization and training settings intended to support type-axis learning.

Character representation: Character convolutions use filters spanning widths 1–7, a maximum word length of 40, 15-dimensional character embeddings, and two highway layers.The model also learns 6-dimensional embeddings for 2- and 3-character prefixes and suffixes.
Search configuration: The search configuration is summarized through hyperparameters for type-system discovery.The supplied passage identifies Table 2 as the source of these settings but does not list their values.
Text Window Classifier: Text-window classifiers use 5-dimensional word embeddings and dropout of 0.5.Two passes with batches of 128 suffice for convergence, while multiple type axes train at 2.5 type axes per second.

B Wikipedia Link Simplification

Wikipedia link simplification replaces certain specific entities with more-linked parents in the Wikidata graph, reducing mention polysemy while preserving aggregated semantic links. The process addresses anaphora and sparsity without simply pruning rare links.

Simplification rule: The method replaces a less-linked entity with its more-linked parent when the Wikidata graph connects them through specified inheritance or semantic relations.The procedure repeats until no further updates occur and reduces “king” senses from 974 to 143.
Motivation: Prior approaches prune rare links, whereas this method detects anaphora and recovers generic meanings through the Wikidata property graph.The simplification targets link sparsity and anaphora while retaining information through parent aggregation.
Effects: 32 to 3553 links for “queen” to monarch after aggregating specific links.This illustrates how the transformation consolidates links rather than discarding the original linking signal.
Effects: 4.73 to 3.93 mean senses per polysemous mention after simplification, with over 10,670,910 links changed.The reduction occurs automatically across multiple languages.

C Multilingual Training Representation

Ontology-based automatic labeling produces multilingual training data as a side effect. The resulting representations keep common words near cross-language counterparts, while proper nouns remain more language- and country-specific.

Multilingual training: Multilingual data creation is a side-effect of the ontology-based automatic labeling scheme.Nearest-neighbor examples include common words such as “he,” “Argentinian,” and “hypothesis,” alongside language-specific proper nouns.
Representation behavior: Common words remain close to foreign-language counterparts, whereas proper nouns group with country- or language-specific terms.The passage hypothesizes that common words can inform type context more language-independently, while proper nouns have different type requirements.

D Effect of System Size Penalty

The system-size penalty λ creates a tradeoff between type-system size and accuracy during CEM discovery. Accuracy gains diminish around λ = 10^-4 as the penalty becomes looser.

Penalty sweep: λ = 10^-4 marks a crossover where loosening the size penalty yields diminishing returns in accuracy.The effect is averaged over 10 trials across multiple penalty values.
Penalty sweep: Varying λ changes the behavior of CEM type-system discovery.The supplied figure and caption identify this parameter sweep but do not provide additional axis values.
Learnability: Type axes based on an instance of edge have higher average AUC than axes relying on Wikipedia categories.This comparison concerns the classifier population used to estimate the Learnability heuristic.
Multilingual behavior: Joint English–French training correctly detects the meaning of “car” across three possible meanings in sampled examples.The experiment uses multilingual data and illustrates cross-language behavior of the trained model.