This paper describes our participation in the BioASQ semantic indexing challenge with two hierarchical text categorization systems. Both systems originated from previous research in thesaurus topic assignment applied on small domains from the legal document management eld. One of the described systems employs a classical top-down approach based on a collection of local classi ers. The other system builds a Bayesian network induced by the thesaurus structure and contents, taking into account descriptor labels and related terms. We describe the adaptations required to deal with a large thesaurus like MeSH and a huge document collection and discuss the results obtained in the BioASQ challenge and the limitations of both approaches.
Text classi cation on hierarchies is a research eld that has had limited presence
at both machine learning and natural language processing elds, although it has
recently started to gain greater attention. This rise is mainly due to the increasing
amount of available on-line resources involving large conceptual taxonomies such
as web directories or huge document collections like MEDLINE 4, EUR-Lex 5 or
even Wikipedia. This resource availability makes hierarchical text categorization
a promising research eld in which to experiment and combine many di erent
4 A bibliographic database of life sciences and biomedical information whose
contents are indexed using Medical Subject Headings (MeSH) thesaurus (see
http://www.ncbi.nlm.nih.gov/pubmed).
5 A service providing legal texts of the European Union that employs EUROVOC
multilingual thesaurus in indexing and searching tasks (see http://eur-lex.europa.eu).
approaches proposed by researchers in machine learning and natural language
processing. Proof of this interest are the recent Large Scale Hierarchical Text
Classi cation (LSHTC) challenges [
In this context, the BioASQ challenge goes a step further by o ering a huge real world environment in a complex domain, biomedical document management, which is currently experiencing a boom and where automatic text understanding tools are becoming a need. Of the two main areas in BioASQ challenge, semantic indexing and question answering (QA), our work falls into the rst one. Our research groups have previous experience in small and medium scale automatic text indexing using medium size thesauri in the legal domain, employing two di erent methods to accomplish the hierarchical categorization task. Our intention in this participation in BioASQ is to check the suitability of our previous approaches in a larger domain, with a much more complex terminology and with strict time and processing restrictions.
The rest of the paper is organized as follows. Section 2 brie y describes the two hierarchical classi cation schemes that we have employed in our BioASQ challenge participation. Section 3 gives details about the preprocessing and adaptations made in both approaches to make them able to deal with the training dataset and the requirements of the BioASQ semantic indexing task. Section 4 discusses some experimental results with di erent parametrization of our categorization tools, and nally, we detail the more relevant conclusions of our participation in the challenge. 2
In our participation in the BioASQ challenge we have employed two systems developed by two di erent research groups. Both of them model the thesaurus descriptor assignment task as a hierarchical categorization problem, and the two categorization tools were result of independent previous research on automatic indexing using thesaurus structures.
In both cases the original domains were very di erent from those considered in the BioASQ challenge, parliamentary resolutions in one case and public grants and subsides on the other. Additionally, in the initial versions of these tools both the size and the complexity of the thesaurus being employed were signi cantly smaller than in the case of the MeSH thesaurus. In the parliamentary documents case, the multilingual thesaurus EUROVOC was in use as indexing base, with less than 4000 descriptors, whereas in the subsides and grants publications collection a custom thesaurus with about 1800 descriptors was employed. 2.1
The hace approach: top-down hierarchy of local classi ers
hace (Hierarchical Annotation and Categorization Engine) is a generic
framework for hierarchical categorization that evolved from previous work on text
categorization on legislative document domain [
Roughly speaking, this approach builds a local binary classi er for each node in the hierarchy of classes, except for the root node, which will be responsible for determining the pertinence of assigning that class or one of its descendants as a label for each input example being classi ed. hace allows both tree-shaped hierarchies and taxonomies structured as DAG (directed acyclic graph). In the second case, it will create as many local models as hierarchical contexts the node may appear, that is, the framework will build a local model for every di erent parent a node can have in the considered DAG, what we call a context. The hace framework aims to provide a modular collection of components to build and train the local classi ers associated with each node in the class taxonomy, covering the following aspects: { strategy for building/selecting positive examples set with a bottom-up procedure { strategy for building/selecting negative examples set { feature selection method used at each local model: employing conventional feature selection (Information Gain, Chi Squared, etc) or features extracted from thesaurus labels { classi cation algorithm being used to perform the "routing" decisions at each local model { strategies for handling unbalanced classes: reweighting, selecting boundary negative examples, distribution of negative examples in an ensemble of classi ers
Additionally, hace o ers features speci cally designed for classi cation tasks
in large textual data collections. In particular, textual repositories are backed by
an Apache Lucene 6 textual index with three elds storing document ID,
categories list and full text. This index helps in computing feature vectors during
local model training and in other complementary tasks like searching for similar
documents. In the case of large hierarchies or problems with large amounts of
training examples an incremental bottom-up scheme for positive example
selection can be employed. This approach helps to mitigate performance problems
when building local models in higher classes in the topology when a "less
exclusive" policy, as de ned in Eisner et al work [
The hace framework also allows the use of a local classi er per node approach
using a sort of "contextual" classi er following an approach inspired by [
Thus, after the training phase, each node/context in the taxonomy of classes will have an associated local model characterized by a list of positive examples that provide a representation of the concepts linked to the corresponding class, a list of features selected as relevant to make the local routing decisions and the content based classi er that exploits these features. Optionally, these local models may include a classi er/router based on context, that uses as metafeatures content based decisions made by surrounding local models. During classi cation of new examples, the set of local models is consulted using a pachinko-like approach to determine in a top-down fashion the list of potential classes that will be employed to label those unlabeled examples. This pachinko-like approach starts at the taxonomy root and consults every direct descendant node model to determine the next branch, or set of branches, where this top-down procedure will be repeated until a leaf node is reached or all of the descendants of a internal node decide to discard the current example. Those nodes where this top-down search stops are included in the nal list of assigned labels for the current example.
An additional feature available during classi cation phase and useful for text
classi cation tasks in large hierarchies is the ability to perform a guided
topdown search with a pre- ltering step. This pre- ltering step exploits the set
of descriptors linked to the most similar documents retrieved from the Lucene
index that backs feature vector building. For a given document to be labeled, the
Lucene index is queried using the document text contents to retrieve the top most
similar documents with their respective categories. These sets of categories are
employed to create with them a weighted ranking of potential labels in a similar
way as is described in [
The Rebayct approach: Bayesian network induced from taxonomy Rebayct is a software tool for document classi cation using descriptors extracted from a thesaurus, based on Bayesian networks.
protection policy health service care dispensary centre medical outpatient clinic hospital institution psychiatric ND:health NDpr:ohteeaclttihon D:phoelailctyh NDse:mrveicdeical D:sheeravlitche NcDar:ehceeanltthre ND:dispensary D:cmeendtriecal D:imnsetditiuctailon ND:outpatient ND:clinic ND:hospital D:psychiatric ND:psychiatric clinic institution hospital T:phoealilcthy E:phoealilcthy
T:health service
E:health service
T:medical centre
T:medical institution
T:psychiatric institution
E:psychiatric institution E:medical institution C:medical institution
C:psychiatric institution E:medical centre C:medical centre H:health service C:health policy
H:health policy
C:health service
Rebayct creates a Bayesian network to model the hierarchical and equivalence relationships in the thesaurus and extends it to incorporate training data. Then, given a document to be classi ed, its terms are instantiated in the network and a probabilistic inference algorithm, speci cally designed and particularly e cient, computes the posterior probabilities of the descriptors in the thesaurus.
Our model of a thesaurus through a Bayesian network is based on two key ideas: (1) to explicitly distinguish between a concept and the descriptor label and non-descriptor labels used to represent it and (2) to clearly separate, through the use of additional nodes, the di erent information sources (hierarchy and equivalence relationships, and training data) in uencing a concept.
Therefore, according to the rst idea, each concept, labeled identically as the descriptor representing it, will be a node C in the network. We shall distinguish between basic and complex concepts: the former do not contain other concepts, whereas the later are composed of other concepts (either basic or complex). Each descriptor and each non-descriptor 7 in the thesaurus will also be nodes D and N D in the network. All the words or terms appearing in either a descriptor label, a non-descriptor label or a training document will be term nodes T . To accomplish with the second key idea, for each concept node C we shall also create three (virtual) nodes: EC , which will receive the information provided by the equivalence relationships involving C; HC , which will collect the hierarchical information, i.e. the in uence of the concepts contained in C; and TC , which will concentrate the information obtained for this concept from the training documents. 7 Usually a synonym or a lexical variation of the descriptor. In the XML version of MeSH thesaurus are linked to the descriptor using TermList elements.
With respect to the links, there is an arc from each term node to each descriptor and/or non-descriptor node containing it, as well as from each term node to the virtual training node TC if the term appears in training documents which are associated with the concept C (these arcs represent the training information). There are also arcs from each non-descriptor node, associated to a concept node C, to the corresponding virtual node EC (these arcs correspond with the USE relationships in the thesaurus), as well as from the own descriptor node associated with the concept C to EC . There is also an arc from each concept node C0 to the virtual node(s) HC associated with the broader complex concept(s) C containing C0 (these arcs correspond with the BT (Broader Term) relationships in the thesaurus). Finally, there are arcs from the virtual nodes EC , HC and TC to its associated concept node C, representing that the relevance of a given concept will directly depend on the information provided by the equivalence (EC node) and the hierarchical (HC node) relationships, together with the training information (TC node).
For example consider a fragment of the EUROVOC thesaurus composed of two complex descriptors, health service and health policy, and three basic descriptors, medical centre, medical institution and psychiatric institution. Health service is the broader term of medical centre, medical institution and psychiatric institution; health policy is in turn the broader term of health service (and also of other ve descriptors which are not considered). The associated non-descriptors are: medical service for health service; health and health protection for health policy; dispensary and health care centre for medical centre; clinic, hospital and outpatients' clinic for medical institution; and psychiatric hospital for psychiatric institution. The network corresponding to this example is displayed in Figure 1
The conditional probabilities for the nodes in the network are de ned by
using several canonical models (additive and an or-gate model) which allow us
to perform exact inference e ciently (see [
Training data in BioASQ challenge on Large-Scale On-line Biomedical Semantic Indexing consisted in about 11 million annotated articles from MEDLINE collection. Each training document was manually labeled with a set of descriptors taken from the Medical Subject Headings (MeSH) thesaurus.
Although BioASQ organizers also included a concept hierarchy extracted from MeSH thesaurus, in our experiments we have employed the XML version of MeSH 2013 edition to create our own concept taxonomy with a DAG structure. MeSH thesaurus consists of 26,853 descriptors arranged in 16 thematic taxonomies. The hierarchical relationships between descriptors are coded in TreeNumber elements. Each MeSH descriptor has one or more TreeNumbers describing the places it occupies inside the 16 concept taxonomies. We have exploited these TreeNumbers to create our class taxonomy, obtaining a DAG with 26,702 nodes, after the exclusion of 151 descriptors from subhierarchy \[V] Publication Characteristics" which are not actually used as labels, and 36,647 parent-child links. In our taxonomy extraction process we have only found two direct cycles 8, that where discarded in the nal taxonomy. We also extracted the list of related terms for each descriptor in the MeSH thesaurus, usually synonyms or lexical variants, giving a total of 108,117 distinct terms.
Regarding the preprocessing performed on the training and validation documents, we have only employed elementary text processing operations: stopword removal and stemming with the default English stemmer from the Snowball project9. Additionally we have processed the resulting tokens to create sets of word bigrams for each document. This way we have built an alternative collection with bigram versions of the original documents and also the word bigrams for descriptor labels and related terms.
The hace framework was developed from scratch with a modular architecture and with clear guidance to work in large textual collections and incorporate components and adaptations to allow an e ective construction of local models in large environments, such as the training set of Task1 of BioASQ challenge. However, Rebayct software was designed with a very speci c domain in mind and all its processing is done against memory resident data structures. The size and complexity of the MeSH thesaurus and the huge amount of di erent tokens in the biomedical training corpus employed in the BioASQ challenge makes it unfeasible to apply the Rebayct approach on the full training set. Therefore, it was necessary to perform a previous selection phase by extracting a reduced training set of 1,242,670 documents, approximately 10 % of available documents. This process employed a Lucene index constructed from the whole collection. For every descriptor ID a Lucene query was launched selecting the top 50 documents for each descriptor not previously included in the list of selected documents. These top documents use to have quite few assigned descriptors and potentially are good samples of the kind of documents linked to the considered descriptor.
Additionally, these 1,242,670 documents were split into ve groups of 248.534 training instances, each of these ve datasets was employed to train a Rebayct model. In the annotation phase every Rebayct model was applied to the unlabeled test documents and the resulting label lists were combined in a similar way as is done in ensemble methods using bagging approaches. 8 Descriptor D009014 (Morals) with descriptor D004989 (Ethics) and descriptor
D006885 (Hydroxybutyrates) with descriptor D020155 (3-Hydroxybutyric Acid ). 9 http://snowball.tartarus.org guided search 0.435 0.458 0.451 0.394 0.421 0.409 0.403 0.487 0.445 bigram features 0.397 0.429 0.413 0.346 0.405 0.369 0.390 0.432 0.411 Table 2. Guided top-down search and word bigram features results. 4
For evaluation and parameter tuning, a custom evaluation dataset was built randomly selecting a set of 2,000 documents from the training set provided by the BioASQ challenge organizers. This evaluation set covers 6,413 di erent MeSH descriptors. Also an arbitrary limit of 15 descriptors was employed to restrict the maximum size of the list of labels assigned to each evaluation document by our tools. This limit was set from the average number of assigned descriptors in the BioASQ training dataset, that according to the BioASQ team is 12,55 MeSH descriptors per article.
As classi cation performance measures we have employed a set of at
measures similar to the one employed by the BioASQ challenge, using MULAN [
hace experiments
Several aspects of hierarchical categorization can be tuned in the hace
framework. After a preliminary tuning phase using a fragment of MeSH subhierarchy
"[C] Diseases" and a reduced set of training documents, we decided to employ
as local classi er for node models the Support Vector Machines implementation
available in Weka [
We concentrate our experiments on evaluating the e ectiveness of bottomup positive examples selection, using two strategies: a simple random document selection among descendant nodes selected documents and a k-means based document selection. In both cases we evaluated this positive document selection with a maximum number of 500, 1000 and 2000 instances for each node. Table 1 summarizes the obtained results. Results con rm the intuition that using more documents per node model increases the overall performance. Using the k-means based bottom-up instance selection obtains a small improvement in the performance. The random documents selection gives slightly lower values, but they are obtained with much less computational e ort, since it does not require the processing of documents to extract feature vectors neither distance computations needed by k-means clustering.
We also have evaluated the e ect of using a guided top-down classi cation based on a previously selected list of candidate descriptors using a similarity query against the Lucene index used to support the feature vector computation. For any given test document the 10 most similar documents in the index are selected and a similarity weighted ranking is done with the assigned descriptors. From this descriptor list the top 20 are selected to start a top-down search along the taxonomy local models starting at their grandparents. An additional experiment was performed comparing single token features against word bigram based features. The results obtained in these two situations are shown in table 2, where a random document selection approach with a limit of 2000 instances was used. The guided top-down search improves the performance and reduces the overall computational cost. On the other hand the performance gain due to using word bigram features is not very relevant. 4.2
Rebayct experiments Rebayct customization capabilities are more restricted. In table 3 we show the results obtained with three con gurations: using only one of the trained models, aggregating the results of 5 models built with di erent training subsets and, nally, one single model using word bigrams as instance features and in descriptor labels and related terms. The best results are obtained when bigrams are employed. This seems reasonable since biomedical documents tend to employ complex terminologies with long nominal phrases and many named entities that word bigrams are able to partially cover. 4.3
O
cial BioASQ results As an illustration of the performance of our systems at BioASQ challenge, Table 4 shown the results obtained by our runs in test set batch number 3. In this batch we have participated with the following ve con gurations, using both single word tokens and word bigrams. hace1. hace framework using k-means bottom-up positive example selection with up to 2000 examples per node, Information Gain feature selection with up to 100 features per node and a SVM classi er as content based router for each model. hace2. Same con guration as hace1 using the guided top-down search approach described in section 2.2. hace2-ne. Same con guration as hace2 using word bigrams as textual features. rebayct. Combination of ve Rebayct models trained with ve splits of the 1,242,670 documents in the reduced training set described in section 3. rebayct2. A Rebayct model trained on one of these 248.534 documents split using word bigrams as document features and also in descriptor labels and related term labels (non-descriptors). We have taken part in the BioASQ biomedical semantic indexing challenge with two di erent hierarchical text categorization systems, a hierarchy of local classi ers and an induced Bayesian network. As shown in the previous section the performance of our two systems in BioASQ challenge was not very good.
In the case of Rebayct system we have some limitations that make it unsuitable for a huge domain like the one we are working with in BioASQ challenge. The Rebayct approach is able to manage both hierarchical information taken from the thesaurus links and information extracted from the training instances. In our experiments we have con rmed that in the case of BioASQ challenge the more relevant element is the training data, mainly due to the large amount of available instances. In other domains with a lack in training data the Rebayct ability to label documents with small or no training would make this tool more attractive.
The hace framework was designed to deal with large categorization problems. There are many components and parameters to con gure and a more deep parameter tuning could improve the reported results. In preliminary experiments with smaller document collections we have evaluated several strategies to deal with unbalanced categorization in local classi ers obtaining some improvements in overall categorization performance. Another important line of research which can lead to improvements in categorization quality in complex domains like biomedical semantic indexing is related with the collection preprocessing using natural language processing approaches more sophisticated than simple stemming and stop-word removal, like domain speci c lemmatization or 10 http://bioasq.lip6.fr/results/ named entities recognition. With our hace framework participation in BioASQ challenge we have also con rmed the relevance of working with large training datasets, since the best results were obtained using the guided top-down search, which starts with a rst step that is essentially a kind of k nearest neighbours assisted by a Lucene index.
Research reported in this paper has been partially funded by "Ministerio de Econom a y Competitividad" and FEDER under the project TIN2010-18552C03-01, by "Xunta de Galicia" under the projects CN 2012/319 and CN 2012/317 and by \Consejera de Innovacion, Ciencia y Empresa de la Junta de Andaluc a" under the project P09-TIC-4526. week 2, labeled documents: 2674/10233
at hier. system rank MiF EBP EBR EBF MaP MaR MaF MiP MiR Acc. rank LCA-F HiP HiR HiF LCA-P LCA-R best 1/24 0.578 0.577 0.589 0.566 0.598 0.435 0.427 0.585 0.572 0.410 1/24 0.486 0.735 0.711 0.702 0.507 0.496 hace2 13/24 0.488 0.473 0.533 0.481 0.436 0.363 0.346 0.473 0.505 0.330 11/24 0.433 0.660 0.672 0.641 0.444 0.456 hace1 18/24 0.415 0.402 0.459 0.411 0.294 0.324 0.297 0.402 0.429 0.268 17/24 0.388 0.599 0.629 0.588 0.393 0.416 rebayct 21/24 0.302 0.293 0.330 0.297 0.545 0.145 0.149 0.293 0.312 0.181 22/24 0.291 0.557 0.489 0.497 0.289 0.320