Embedding Semantic Taxonomies (2020)

Abstract: A common step in developing an understanding of a vertical domain, e.g. shopping, dining, movies, medicine, etc., is curating a taxonomy of categories specific to the domain. These human created artifacts have been the subject of research in embeddings that attempt to encode aspects of the partial ordering property of taxonomies. We compare Box Embeddings, a natural containment representation of category taxonomies, to partial-order embeddings and a baseline Bayes Net, in the context of representing the Medical Subject Headings (MeSH) taxonomy given a set of 300K PubMed articles with subject labels from MeSH. We deeply explore the experimental properties of training box embeddings, including preparation of the training data, sampling ratios and class balance, initialization strategies, and propose a fix to the original box objective. We then present first results in using these techniques for representing a bipartite learning problem (i.e. collaborative filtering) in the presence of taxonomic relations within each partition, inferring disease (anatomical) locations from their use as subject labels in journal articles. Our box model substantially outperforms all baselines for taxonomic reconstruction and bipartite relationship experiments. This performance improvement is observed both in overall accuracy and the weighted spread by true taxonomic depth.

## introduction recent work on hierarchical representational structures in machine learning promise to blend the value of human curated taxonomies with the power and flexibility of machine learning systems. a plethora of such taxonomies exist across many domains as seen in libraries, linguistic resources, medicine and popular culture, yet they rely on an assumption of discreteness -category membership is either true or false -and this assumption does not generally lend itself to modelling with continuous valued systems or spatial embeddings. taxonomic knowledge can be leveraged in the semantic space to extract hierarchical relations between words, and this simple observation has been the basis of many computational resources for linguistics, such as wordnet, eurowordnet, framenet, etc. for example, the similarity of the words lion and tiger may be indistinguishable from the similarity of lion and animal in a naive text embedding space, as they may simply be the same distance apart, but in wordnet the difference and similarity are made clear through the taxonomy. in many cases, this explicit knowledge can be derived from existing taxonomies, but without some way of understanding this knowledge in the embedding space, it is just another similarity signal. recently, order embeddings addressed this issue by orienting similarity in two axes and adding a constraint to similarity embeddings that ensured more general terms had to be closer to the origin @xcite . more recently we've seen the introduction of box lattice embeddings, which treat categories in a taxonomy as n-dimensional boxes, with a constraint that boxes representing more general terms should contain boxes representing more specific terms @xcite . on a different front, there has been steady progress in automating knowledge-base construction (kbc) from text, as a pure demonstration of nlp as well as a productive tool for end to end tasks like question answering. a key part of kbc efforts is learning relations from text, yet a key research question remains relatively unexplored: can we use taxonomic similarity in conjunction with kb relations? in the early days of nlp and knowledge representation (kr), it had always been assumed these two kinds of knowledge would work together, but there is little evidence in existing systems that they do. this work is motivated by that key research question. similar to prior work, we began by experimenting with various taxonomy embedding techniques to reconstruct the medical subject headings (mesh) taxonomy from published article tags. we customize a box embedding model for the task and compare the results to several baselines. finally, we explore a familiar problem: learning a relation on a bipartite graph, in this case the relation between diseases and parts of the body using the co-occurrence of human-assigned mesh labels on pubmed abstracts. the work tests the hypothesis that the mesh taxonomy can provide a useful signal in learning this relation: if asthma (disease) and bronchi (anatomy) co-occur in data, and bronchi is a subcategory of lung in the taxonomy, then asthma and lung are related. the contributions of this paper include the following: 1. a customized box model objective function that smooths the non-differentiable hinge property of the naive learning problem 2. performance improvements for the taxonomic learning task via variations of negative sampling and weighting. 3. a methodology for incorporating sparse instance data evidence without exploding the size of the parameter space 4. defining evaluation metrics specialized to the unique requirements of the learning of a taxonomy 5. defining and testing novel experiments for learning taxonomies on bipartite graphs. ## related work previous research in learning semantic taxonomies has included a few approaches. @xcite proposed learning hierarchies from straight text using formal concept analysis and @xcite learned ontologies with the semantic web. @xcite extracted taxonomies from keywords. @xcite learned taxonomy by clustering based on informed syntactic matching and semantic relations. @xcite automatically extracts taxonomies from web sites using concepts and hypernym relations. much early work with ontologies focused explicitly on expanding a given taxonomy or examining a specific area in more depth. @xcite used a classifier for predicting new undiscovered edges in wordnet. @xcite used an initial taxonomy to algorithmically crawl the web. @xcite uses a seed taxonomy for guided hierarchical expansion. other work considered noisy real word graphs and suggested algorithms to remove edges from a formal taxonomy @xcite . similarly, there has been a corpus of work in embedding techniques to extract hierarchical structures in text. @xcite utilized co-occurrence for creating simple euclidean embeddings. @xcite employs hierarchical clustering in a recursive process to construct topic taxonomies. @xcite represented text with partial order embeddings (poe). @xcite explored partial order embeddings with distributional co-occurrences for learning ontologies. @xcite extended the functionality of poe to better reflect conditional probabilities of an ontology with box embeddings. @xcite explored gaussian word embeddings. earlier the authors showed preliminary results using box embeddings for constructing taxonomies in @xcite . in this work, we expand the performance analysis and add experimental results for the novel bipartite relations problem. more recently, several works have explored hyperbolic embeddings, in which hierarchical structures are represented as continuous generalizations in non-euclidean space. @xcite @xcite @xcite . @xcite uses hyperbolic embeddings for learning concept hierarchies from text. @xcite introduced an application of glove in hyperbolic space. ## mesh dataset mesh, the nlm medical subject headings, (u.s. national library of medicine, 2018a) is a taxonomy of subject headings for categorizing medical writing. pubmed (u.s. national library of medicine, 2018b) is a very large collection over 30 million medical journal articles, each with metadata including human labeled subject categories from mesh. mesh is organized into 16 top level categories, such as a: anatomy, b: organisms, c: diseases, which themselves cannot be the subjects of articles. the taxonomy is on average 8 levels deep, with a generalization or broader-term relationship from child to parent nodes, e.g. <respiratory system, anatomy>, <larynx, respiratory system>, <asthma, diseases>. we adopt the notation in which the taxonomy is represented as a collection of child, parent edges in a tree-shaped taxonomy graph (noting that it is not strictly a tree). the mesh anatomy hierarchy mostly follows a mereological generalization (sub-parts to parts), while diseases follow a slightly more causal generalization (<pneumonia, bacterial @xmath0. this kind of semantic promiscuity is extremely common in taxonomies @xcite , and causes an imprecision that begs for an approach with soft, continuous-valued constraints, as opposed to the traditional discrete reading of the taxonomic relationship (all members of the subcategory are members of the super-category). it was this observation that led us to taxonomy embeddings. articles listed in pubmed can have any number of subject headings, on average 8-10, and it is fully expected by the published methodology that assigning a particular subject heading to an article also assigns the mesh parents and ancestors -they expect the transitive closure to hold. ## taxonomy embedding experiments this work explores box lattice embeddings @xcite as a technique uniquely suited to the semantic taxonomy space. the efficacy of this approach is validated with partial order embeddings and naive bayes are examined as baselines. ## learning taxonomies many taxonomies are extensional: the categories organize sets of entities in some problem domain, such as movies, stores, restaurants, books, songs, etc. there is a fairly clear instance/category distinction in these cases and the number of instances vastly outweighs the number of categories. such taxonomies have edges from instances to categories, inst-cat edges (e.g. <star wars, science-fiction @xmath1, and edges between categories, cat-cat edges (e.g. <cult science-fiction movie, science-fiction @xmath2. some taxonomies are intensional: they have no instances, at least none represented in data. wordnet synsets, for example, are arranged in a taxonomy, and there are very few instance-like synsets in wordnet, referring e.g. to specific people and organizations, but for the most part, synsets like "amount of matter" have no clear extension. such taxonomies have only cat-cat edges. many previous experiments on learning taxonomy embeddings were conducted on intensional taxonomies, with no instances, and the objective (for training and evaluation) was simply the number of correct cat-cat edges learned above some confidence threshold. our datasets are extensional and contain millions of instances: pubmed 2018 has over 30 million. ## customized box embeddings for taxonomy reconstruction the promise of the representational power of boxes over vectors motivated us to dive deeper into the poor performance of boxes in these settings. specifically, we modified the negative ratio, experimented with informed sampling, changed the objective function and utilized centered initialization to improve the box embedding model performance. negative ratio: in the original box and order embedding papers, negatives were sampled uniformly from the complement of positive edges with a ratio of 1:1. the prior probability of a negative edge was greater than 0.99, so this sampling method allowed for a problem as shown in fig. 1a . given a simple toy taxonomy of five categories, fig. 1a shows a version of the box layout we would expect, and fig. 1b shows an actual learned set of box embeddings (in 2d) with no negatives. one problem becomes clear, the intuition of the box objective fails to account for the fact that it is easiest to satisfy the objective by making most of the boxes overlap. negative sampling rates are a common ml problem, and a commonly used approach is to increase the negative ratio to 10:1, which led to a problem illustrated in fig. 1b . by increasing the number of negative edges in training, we increased the chances of a bad edge that creates competing constraints. in this case, since we have no edge a, b it could be naively sampled as a negative. having that as a negative edge forces the two boxes apart, even though the edges c, a and c, b should cause them to overlap. informed sampling: some improvements to sampling were proposed in @xcite , but these were more specific to order embeddings. instead, we addressed the problems of naive sampling with informed sampling (see appendix -in section 10 for details). in a nutshell the algorithm uses traditional taxonomic reasoning as a way to identify edges that, while not necessarily positive, should not be negative. as in the example shown in fig. 1b , one such case are edges between ancestors of the same category. informed sampling improved matters but revealed another problem with training boxes, the box crossing problem, shown in fig. 2a . in the example, we have altered the simple taxonomy a bit by making the edge c, b negative, and with a and c on opposite sides of b, the gradient will not allow them to cross and ultimately meet. as the neg:pos ratio increases, the chances of box crossing standing in the way increases dramatically. while in some sense this is no more than a gradient descent problem, getting stuck in a local neighborhood, the fact that boxes have volume, corners, and edges, leads to a solution space that is full of local minima. solutions that smooth the space can help dramatically. the improvements in performance from informed sampling can be seen for the partial order embedding (poe) baselines in ## taxonomy depth the hierarchical nature of taxonomy datasets yields a further evaluation problem. when using box embeddings, it is expected that the volume of root nodes will substantially exceed those of the leaf nodes. as such, a naive evaluation of performance can yield decent results with a model that only learns the root nodes and/or nodes with edges close to the root. given the structure of box embeddings where the marginal probability of a node is equivalent to the box volume, such an evaluation problem may be more pronounced. as such, we have examined the notion of taxonomy depth as used by @xcite . ## conclusions we presented the practical problem of extracting implicit underlying taxonomies from instance data in the pubmed mesh dataset. the work also explored the more complex task of extracting bipartite relations within multiple taxonomies. an in-depth exploration of re-constructing a single taxonomy with box embeddings yielded experiments in negative sampling, solutions to the box crossing problem and a customized objective function. the final model demonstrated impressive f-measure scores for reconstructing the mesh disease taxonomy. unlike other baselines, the model scores were consistent for all depths. finally, we defined a problem of extracting bipartite relations between multiple taxonomies within the pubmed article subject headings. our customized box embedding models outperformed other baselines for both problems and we introduced a methodology conducive to the taxonomy extraction space.