Many recent efforts explore the task of Taxonomy Derivation from Wikipedia Category Network (TDWCN), which induces rich hypernymy relations between instances and classes from Wikipedia to integrate hierarchical information into knowledge graphs. However, current methods rely heavily on languagedependent information including heuristic rules, human annotations and inter-language links, which limit their applications. In this paper, we propose a language-independent model for TDWCN. Specifically, we design an adversarial learning approach to distill hypernymy relations from noisy raw Wikipedia, avoiding any language dependencies. Besides, we incorporate multi-task learning to explore the correlation among instanceOf, subClassOf, and the relations of instances. In addition, we contribute an English evaluation dataset ENT5k with about 6000 categories. Experimental results on 4 different languages demonstrate that our model can be applied generally to any language and achieve better or comparable performance compared with previous language-dependent models.
Taxonomies hierarchically organize hypernymy (consisting of instanceOf and subClassOf ) among
instances and classes, which are the core pieces of large-scale knowledge graphs [
Current approaches for taxonomy derivation can be divided into three lines: (1) manual
construction [
As shown in Figure 1, WCN is a directed graph linking Wikipedia articles (e.g., Micky Mouse) with inter-connected categories of different granularities (e.g., Disney comics characters, Disney characters, Disney comics). The links from articles to categories are articleOf, and those between
The Walt Disney Company
Disney
Comics Characters
The Walt Disney Company
Disney
Comics Characters
article/instance category/class articleOf subClassOf instanceOf subClassOf categories are subCategoryOf. By treating each article and category as one candidate instance and class, each articleOf and subCategoryOf as one candidate instanceOf and subClassOf respectively, we can obtain a large-scale taxonomy with millions of instances and classes without extra human efforts. However, not all articleOf and subCategoryOf links are correct hypernymy relations. If we do not filter out the non-hypernymy in WCN, wrong facts might be inferred (e.g., “(Micky Mouse, instanceOf, The Walt Disney Company)”). Therefore, TDWCN needs to recognize whether each articleOf and subCategoryOf in WCN is a correct hypernymy relation, which can be formed as a hypernymy classification task consisting of InstanceOf Classification and SubClassOf Classification.
Most previous methods for TDWCN [
To address the above issues, we propose a language-independent method through multi-task adversarial learning to perform TDWCN. Specifically, we pretrain a coarse classifier over the raw WCN, based on which we split the training data into a reliable set and an unreliable set. Then, we use adversarial learning to iteratively distill the two training sets and refine the classifier (i.e., the discriminator) through a min-max game between the discriminator and sampler. Our model can purify the large-scale raw WCN and is general enough to any language without the limitation of heuristic rules, human annotations or inter-language links. In addition, considering that (1) InstanceOf Classification and SubClassOf Classification can mutually enhance each other because instances and classes are highly correlated; (2) the rich semantics provided by relational facts among instances through Knowledge Embedding may benefit Hypernymy Classification, we propose a multi-task learning framework to learn Knowledge Embedding, InstanceOf Classification and SubClassOf Classification simultaneously. These three sub-tasks fully integrate the connections from multiple views of instance-instance, instance-class and class-class information lfow respectively to further improve the performance of TDWCN.
Taxonomy Derivation. Taxonomies organize classes and instances in the real world in hierarchical structure, and directly affect the computational ability of knowledge graphs. Therefore, the derivation of large-scale, high-coverage and high-quality taxonomies is essential.
Current methods for taxonomy derivation can be divided into three categories. One category
focuses on manual construction [
Different from MENTA, MultiWiBi and MultiTax, our method avoids language-dependent information including heuristic rules and inter-language links. Different from WiBi and MultiWiBi which also consider the correlation between instances and classes, we use deep representation learning to vectorize them, which serve as a basis that connects InstanceOf and SubClassOf classification.
Note that Wikipedia has links from each article to the corresponding Wikidata item and Wikidata has taxonomic relations among its items. However, these relations focus only on the articles of Wikipedia and ignore categories. We believe the rich taxonomic relations among articles and categories in Wikipedia are crucial for large-scale and high-coverage taxonomies and can complement with the existing taxonomy in Wikidata.
Adversarial Training. For adversarial training, prior works in computer vision add imperceptible
adversarial perturbations to input images, relying on the fact that such small perturbations cannot
change an image’s true label. [
Different from previous works, we exploit the ability of adversarial training to distinguish nuances between input data and refine a pretrained coarse classifier. We split the unlabeled training data into a reliable set and an unreliable set, and use adversarial training to iteratively distill the two training sets through a min-max game between a discriminator and a sampler.
Definition 1. WCN is a directed graph defined as = ⟨, , ℛ, ℛ⟩: Each ∈ is an article in Wikipedia. Each ∈ is a category grouping articles and other categories on similar topics, which can be represented as a word sequence {1, . . . , ||}. ℛ = {| = (, ), ∈ , ∈ }, is articleOf between article and category . ℛ = {| = (, ), , ∈ }, is subCategoryOf between two categories , .
Definition 2. Taxonomy is a directed acyclic graph defined as = ⟨ℐ, ˜, ℛℐ , ℛ˜⟩: (1) Each ∈ ℐ is an instance. Each ˜ ∈ ˜ is a class. (2) ℛℐ = { | = (, ˜), ∈ ℐ, ˜ ∈ ˜}, is instanceOf between instance and class ˜. ℛ˜ = {˜|˜ = (˜, ˜), ˜, ˜ ∈ ˜}, ˜ is subClassOf between two classes ˜, ˜.
As shown in Figure 1, articles and categories in WCN can be viewed as candidate instances and classes respectively; articleOf and subCategoryOf are candidates of instanceOf and subClassOf. Namely, ℐ ⊆ , ˜ ⊆ , ℛℐ ⊆ ℛ and ℛ˜ ⊆ ℛ . We want to recognize whether each articleOf is a correct instanceOf and whether each subCategoryOf is a correct subClassOf. Therefore, the main task Hypernymy Classification can be formalized as follows.
Definition 3. Hypernymy Classification is to learn two functions ℐ and for instanceOf classification and subClassOf classification respectively: (1) ℐ() ↦→ {+1, − 1}, ∈ ℛ, +1 denotes articleOf is a correct instanceOf and -1 not. (2) ( ) ↦→ {+1, − 1}, ∈ ℛ, +1 denotes subCategoryOf is a correct subClassOf and -1 not.
We conduct taxonomy derivation in three steps: (1) Network cleanup, a pre-processing step to iflter out meta-categories related to Wikipedia management; (2) Hypernymy classification, the core step to learn both InstanceOf and SubClassOf classification; (3) Taxonomy induction, a post-processing step to induce a globally-optimized taxonomy.
For network cleanup, we follow [
For Hypernymy Classification, as shown in Figure 2, we learn three sub-tasks Knowledge Embedding, InstanceOf Classification and SubClassOf Classification simultaneously in a multitask learning framework to fully incorporate the connections among instances and classes. For Coarse Pretraining (') via negative sampling
(%) from WCN
Classifier Unreliable set ( '
Reliable set ( % Adversarial Refining
( ' Unreliable Samples
Reliable Samples
( %
Encoder Discriminator Shared instances
InstanceOf Classification
Shared classes SubClassOf
Classification
Knowledge Embedding, we introduce an external knowledge graph with rich semantic relations among instances. For InstanceOf and SubClassOf classification, they follow the same learning process and model architecture. Specifically, we pretrain a coarse classifier based on the raw WCN and a negative sampling strategy. According to the output of the classifier, we split the training data into a reliable set and an unreliable set. Then, we use adversarial learning to iteratively distill the two training sets and refine the classifier (i.e., the discriminator) through a min-max game between the discriminator and sampler. In Section Coarse Pretraining and Adversarial Refining, we take SubClassOf Classification as a representative to introduce the details. In Section Multi-task Learning, we introduce the overall learning objective in the multi-task learning framework. 4.1. Coarse Pretraining The coarse pretraining aims to learn a coarse classifier to predict whether each relation in WCN is a hypernymy.
Encoder Scorer
Sampler Noisy
Informative
0/1
4.1.1. Category Encoding
Firstly, we capture the semantics for each category from its word sequence. Specifically, given
the word sequence {1, · · · , ||} of category ∈ , we represent all words with their word
embeddings {1, . . . , ||}, and then feed the embeddings into a neural encoder to obtain the
category representation . Without loss of generality, we select convolutional neural networks
(CNN) [
We observe that most of subCategoryOf are correct subClassOf and most of subClassOf are already contained in subCategoryOf. Due to the lack of supervised labels, we assume the equivalence between the subClassOf set and subCategoryOf set to coarsely train our classifier, and then enhance it in a finer granularity by multi-task adversarial learning which will be explained in the following.
Specifically, let (+) and (− ) be the positive and negative sample sets of the subClassOf classifier. We have (+) = ℛ and (− ) = {( , )| , ∈ , ( , ) ∈/ ℛ}. As there are a huge amount of negative samples and most of them can be easily recognized, we design an efficient negative sampling strategy to sample the most informative ones from (− ). Specifically, for each category pair ( , ) ∈ (+), we choose (1) one reverse hypernymy pair for predicting the directionality of hypernymy; (2) one co-hypernymy pair for distinguishing hypernymy from semantic relatedness relations; (3) one randomly corrupted pair for distinguishing hypernymy from other relations. The loss function of coarse pretraining is: ℒ = − −
∑︁ (,)∈(+)
∑︁ (,)∈(− ) log (︀ ( , )︀) log (︀ 1 − ( , )︀) .
(1)
(2)
1For InstanceOf Classification, given a relation (, ) ∈ ℛℐ, the relation embedding , = () −
where is the instance embedding initialized by Knowledge Embedding as will be introduced in Section
Multitask Learning and (· ) is a multilayer perceptron to project the instance embedding to the space of category
embedding.
4.2. Adversarial Refining
The (+) and (− ) mentioned in the above section are coarse-grained because a critical mass of
samples are placed into the mistaken set. Inspired by [
(+) and (− ) and refine the classifier.
According to the predicted score in Eq. (1), we choose the samples in (+) whose scores are higher than a threshold to construct a reliable set ˜ (+) , and the remaining samples in (+) and (− ) to construct an unreliable set ˜ (− ). As shown in Figure 2, we design a discriminator and a sampler to conduct an adversarial min-max game. Given a sample ( , ), the discriminator aims to learn a score function ( , ) to judge whether it is from ˜ (+) or ˜ (− ), while the sampler learns a probability ( , ) for each sample of ˜ (− ), representing its chance of being a false negative. According to , we select the most confusing negative samples from ˜ (− ) to cheat the discriminator. During training, the generator provides large amounts of latent noisy samples to enhance the discriminator, and the discriminator influences the generator to select the more informative samples. We also dynamically select the most informative and reliable samples from the unreliable set to the reliable set. During the adversarial refining process, we can enhance the classification capability of the discriminator. Formally, the objective of the min-max game can be expressed as
Discriminator is transferred from the coarsely trained hypernymy classifier in Eq. 1: min max(
(,)∼ ˜(+) [( , )] + (,)∼ [(1 − ( , ))]).
( , ) = (︀ , · )︀ . calculated as, which will be further refined with adversarial loss.
Sampler aims to select samples from ˜ (− ) to cheat the discriminator according to which is ( , ) = · , + ; ( , ) = ∑︀ (˜,˜)∈ exp (︀ ( , )︀) ˜(− ) exp (︀ (˜ , ˜) ︀) .
By unfolding the min-max objective in Eq. 3, the adversarial loss for the discriminator is as where and are parameters. follows: And the adversarial loss for the sampler is: ℒ = − − ∑︁ ∑︁ (,)∈ (,)∈
˜(− ) ℒ = −
∑︁ (,)∈ ˜(− )
1 ˜(+) |˜ (+) log ( , )
| ( , ) log (︀ 1
− ( , )︀) . ( , ) log ( , ).
(3) (4) (5) (6) (7)
As we treat instanceOf and subClassOf separately, and adopt adversarial training for both of them, the holistic adversarial training loss functions for instanceOf and subClassOf are: ℒ = ℒ + ℒ; ℒ = ℒ + ℒ . (8) ℒ and ℒ are the discriminator loss functions for instanceOf and subClassOf respectively. Similarly, ℒ and ℒ denote the sampler loss functions. and are the weighting factors. 4.3. Multi-task Learning Besides distilling the training data and refining the classifiers through adversarial learning, we further incorporate multi-task learning to enhance the hypernymy classifiers. The main idea is that (1) InstanceOf Classification and SubClassOf Classification can mutually enhance each other because instances and classes are highly correlated; (2) relational facts about instances provide rich semantics which benefits Hypernymy Classification. Specifically, we learn three sub-tasks, Knowledge Embedding, InstanceOf Classification, and SubClassOf Classification simultaneously to integrate the instance-instance, instance-class and class-class information flow.
For Knowledge Embedding, we introduce a knowledge graph , which expresses data as a
directed graph = {ℐ, , }. ℐ, and indicate the sets of instances, predicates and triples
respectively. A score function (ℎ, , ) is learned to measure the plausibility of (ℎ, , ) being
a legal triple, where ℎ, ∈ ℐ, ∈ . In this paper, we utilize TransE [
∑︁ (ℎ,,)∈ (ℎ˜,˜,˜)∈/ max (︀ 0, + (ℎ, , ) − (ℎ˜, ˜, ˜))︀ where is a hyper-parameter denoting the margin.
Finally, the overall loss of multi-task learning is formalized as
ℒ = ℒ + 1ℒ + 2ℒ.
Here, 1 and 2 are two weighting factors. Specifically, instance embeddings are shared by Knowledge Embedding and InstanceOf Classification. Class embeddings are shared by InstanceOf Classification and SubClassOf Classification. By jointly optimizing the shared parameters, we can fully integrate the connections among instances and classes and enhance the hypernymy classifiers. 4.4. Model Training First, we optimize the loss function ℒ in Eq. (2). Then, we use the coarsely trained model and hyper-parameter to construct ˜ (+) and ˜ (− ) for adversarial training. In practice, we share the parameters of the classifier (Eq. (2)) and discriminator (Eq. (6)) to warm up the adversarial training process. Then, we optimize the multi-task learning loss function in Eq. (10). ℒ and ℒ are optimized alternately, with integrated into the learning rate of ℒ to avoid adjusting. ℒ and ℒ take the similar optimization strategy. Instead of directly updating ℒ, we optimize ℒ , ℒ and ℒ alternatively.
(9) (10)
5.1. Datasets As far as we know, previous datasets for TDWCN are all small datasets. For example, as shown in Table 1, the datasets in MultiTax contain only about 200 articles and 200 categories. For better evaluation, we create a large-scale English evaluation dataset ENT5k. Specifically, we use a 2018 snapshot of Wikipedia, select 7,000 articles and 7,000 categories from its WCN and then annotate whether articleOf and subCategoryOf of sampled WCN are hypernymy or not. Each articleOf or subCategoryOf is allocated to 5 highly-educated crowd-workers2. Only the ones consented by more than 4 crowd-workers are kept to assure quality. Instead of selecting categories randomly, we consider both the abstract ones such as “(Learning, Education)” and the specific ones such as “(American Male Painters, American Painters)”, and select categories to cover diverse areas such as people, society, geography, etc. Finally, ENT5k contains 5,989 articles, 5,983 categories, 27,696 articleOf and 19,857 subCategoryOf. As for the annotated results, for articleOf, the incorrect relations make up 3.0% and for subCategoryOf, the incorrect make up 24.8%. 2Inter-annotator agreement (Cohen’s Kappa) is 0.72 5.2. Baselines As far as we know, our model is the first weakly-supervised method. We compare our method with the following rule-based and supervised methods:
Heads [
MENTA [
MultiWiBi [
MultiTax [
For a fair comparison with the baselines, we follow the evaluation metrics used in
MultiWiBi [
(1) For English, our model distinguishes the non-hypernymy from the original WCN and improves P* by a large margin. It also surpasses Heads and MultiWiBi significantly, which indicates that our neural model can outperform the rule-based method.
(2) For the non-English languages, our method significantly outperforms the rule-based models. Even compared with the supervised model, our weakly-supervised model provides comparable performance. Especially for subClassOf, it even outperforms MultiTax slightly in French and Spanish, indicating that weakly-supervised methods are promising and worth exploring in the future.
(3) Our model performance for instanceOf is worse than that for subClassOf. A possible reason is that infrequent instances cannot learn a good representation due to data sparsity. As described in Section Coarse Pretraining, categories are represented by a textual encoder, but most of the instances (e.g., “Donald Duck") are named entities whose semantics are beyond the word sequence can describe. Instead, instance embeddings are randomly initialized and further learned from the knowledge graph by Knowledge Embedding. However, as previous study shows [36, 37], the frequency of instances follows a pow-law distribution and most of the instances are infrequent, which cannot learn a good representation and further harm InstanceOf Classification. A reasonable solution is to utilize instance descriptions, which will be our future work.
As shown in Table 2, the original WCNs for different languages vary a lot. For French, only 72.0% articleOf are correct, yet for English, 97% are correct. For English, improving InstanceOf Classification is not easy but necessary because more than 25 million articleOf exist in WCN and the number of invalid articleOf is 750k, which will harm SubClassOf Classification due to error propagation.
Note that we propose the language-independent method to avoid excessive manual rules and corpus labeling in the language-dependent method. Our focus is on reducing costs and improving generalization ability, rather than claiming that our experimental results are definitely better than theirs. Therefore, in the experiment, compared to language-dependent methods (which are based on manual rules or corpus annotations), our model can achieve comparable results and be applied generally to different languages without rules or annotations, showing the benefits of our method. 5.5. Ablation Study In this section, we conduct ablation study to further investigate the proposed adversarial training strategy and multi-task learning framework. Without loss of generality, we investigate the subClassOf results on ENT5k. We refer to the coarsely trained classifier as BASE, the classifier with adversarial training as BASE+ADV, and the classifier with both adversarial training and multi-task learning as BASE+ADV+MT. Further, we denote the BASE+ADV+MT model without Knowledge Embedding as BASE+ADV+MT− .
We use a variant of precision (P˜), recall ( R˜), F1 score (F̃︁1) and Area Under Curve (A˜U︁C) for evaluation. Specifically, since we expect our model to find out as many true negatives as possible, we employ P˜ = (TN+FN) , R˜ = (TN+FP) , where TN, FN and FP denote true negative, false
TN TN negative and false positive results respectively. A˜U︁C is the area under the P˜- R˜ curve. The overall results are shown in Table 4.
The reasons that different metrics are used in the overall performance evaluation and the ablation study are as follows: (1) the overall performance evaluation is to measure the quality of taxonomy, while the ablation study is to investigate the effectiveness of hypernymy classification. (2) the quality of our taxonomy is not merely determined by hypernymy classification, because we conduct taxonomy derivation in three steps: network cleanup, hypernymy classification and taxonomy induction. Therefore, in the ablation study, we use the precision, recall and F1 measures for the classification model. While in the overall performance evaluation, we follow previous work and use P*, R* and C.
Effect of Adversarial Training. When we apply adversarial training, F̃︁1 is improved by 3.6% and A˜U︁C is improved by 3.9%, which indicates that adversarial training improves classification performance and generalization ability.
We further conduct an in-depth study of the sampler. Examples in Table 5 show that, given a hyponym and multiple candidate hypernyms, the sampler can reasonably calculate the probability distribution and distinguish informative candidates from noisy ones. The informative data from the sampler can further help to boost the performance of the discriminator, which explains the improvement of BASE+ADV over BASE. Effect of Multi-task Learning. When we compare BASE+ADV+MT− with BASE+ADV, F̃︁1 and A˜U︁C is improved by 1.0% and 2.2% respectively, demonstrating that InstanceOf and SubClassOf classification mutually enhance each other. When introducing Knowledge Embedding, we achieve the best F̃︁1 and A˜U︁C compared with all the other models. Specifically, when we compare BASE+ADV+MT with BASE+ADV+MT− , F̃︁1 and A˜U︁C is increased by 2.7% and 4.5% respectively. This shows the relational facts among instances benefit Hypernymy Classification. All the results demonstrate the effectiveness of our multi-task learning framework.
To further show the effectiveness of multi-task learning, we conduct a case study by comparing BASE+ADV+MT with BASE+ADV. From Table 6 we can see that BASE+ADV+MT can produce more reasonable results.
In this paper, we propose a language-independent model for TDWCN, which (1) designs an adversarial learning approach to distill hypernymy relations from noisy raw Wikipedia without the limitation of language dependencies; (2) incorporates multi-task learning to integrate the information flow among instances and classes. In addition, we contribute a large-scale evaluation dataset with 27k articleOf and 19k subCategoryOf for TDWCN. Experimental results on 4 different languages demonstrate that our model can be applied generally to different languages and achieve better or comparable performance compared with previous language-dependent approaches. Future work includes investigating instance embeddings, deriving taxonomies for more languages and extracting domain-specific taxonomies based on our approach. [33] J. Pennington, R. Socher, C. D. Manning, Glove: Global vectors for word representation, in: EMNLP, 2014. [34] A. Joulin, E. Grave, P. Bojanowski, T. Mikolov, Bag of tricks for efficient text classification, in: EACL, 2016. [35] D. Vrandecic, M. Krötzsch, Wikidata: a free collaborative knowledgebase, Commun. ACM 57 (2014). [36] Z. Wang, K. P. Lai, P. Li, L. Bing, W. H. Lam, Tackling long-tailed relations and uncommon entities in knowledge graph completion, ArXiv abs/1909.11359 (2019). [37] E. Cao, D. feng Wang, J. Huang, W. Hu, Open knowledge enrichment for long-tail entities, Proceedings of The Web Conference 2020 (2020).