ARKTis -A Fast Tag recommender system Based on heuristics Thomas Kleinbauer and sebastian ger erman Research Center for Artificial Intelligence(DFKI) 66123 Saarbrucken Germany irstname,lastnameddfki de Abstract. This paper describes the tag recommender system ARKTis our contribution to the 2009 ECML PKDd tag discovery challenge ARKTiS consists of two separate modules for BIBTEX entries and for book marked web pages For generating tags, we distinguish between so-called internal and erternal methods, depending on whether a tag tracted from the given information about a resource or whether addi- tional resources were employed 1 Introduction The role of the end-user in the world wide web(www) has undergone a sub- stantial change in recent years from a passive consumer of relatively static web pages to a central content producer. The addition of backchannels from Www clients to internet servers empowers non-expert users to actively participate in the generation of web content. This has led to a new paradigm of usage, collo- quially coined“Web20”[1 These novel kinds of interactions can be divided into two categories: produc ing or making accessible of new information(e.g, web logs, forums, wiki wikis etc. )and enriching already existing contents(e. g, consumer reviews, recom- mendations, tagging, etc. ) One interpretation of the second type of interaction is that it provides means to cope with one of the problems generated by the first type of interaction, namely the massive growth of available content and the increasing difficulty for traditional information retrieval approaches to support efficient access to the contained information. In this sense, the meta-content pro- duced in the second kind of interaction can be construed as mainly serving as a navigation aid in an increasingly complex, but weakly structured online-world In particular, the possibility for users to attach keywords to web resources in order to describe or classify their contents bares an enormous potential for structuring information which facilitates subsequent access by both the original user and other users. This task, commonly referred to as tagging is simple enough not to scare users away, yet the benefit of web resources annotated in such a way is obvious enough to keep the motivation to supply tags high. The process of attaching tags to web resource must therefore show a fine balance between
1 ARKTiS - A Fast Tag Recommender System Based On Heuristics Thomas Kleinbauer and Sebastian Germesin German Research Center for Artificial Intelligence (DFKI) 66123 Saarbr¨ucken Germany firstname.lastname@dfki.de Abstract. This paper describes the tag recommender system ARKTiS, our contribution to the 2009 ECML PKDD tag discovery challenge. ARKTiS consists of two separate modules for BibTEX entries and for bookmarked web pages. For generating tags, we distinguish between so-called internal and external methods, depending on whether a tag was extracted from the given information about a resource or whether additional resources were employed. 1 Introduction The role of the end-user in the world wide web (WWW) has undergone a substantial change in recent years from a passive consumer of relatively static web pages to a central content producer. The addition of backchannels from WWW clients to internet servers empowers non-expert users to actively participate in the generation of web content. This has led to a new paradigm of usage, colloquially coined “Web 2.0” [1]. These novel kinds of interactions can be divided into two categories: producing or making accessible of new information (e.g., web logs, forums, wiki wikis, etc.) and enriching already existing contents (e.g., consumer reviews, recommendations, tagging, etc.). One interpretation of the second type of interaction is that it provides means to cope with one of the problems generated by the first type of interaction, namely the massive growth of available content and the increasing difficulty for traditional information retrieval approaches to support efficient access to the contained information. In this sense, the meta-content produced in the second kind of interaction can be construed as mainly serving as a navigation aid in an increasingly complex, but weakly structured online-world. In particular, the possibility for users to attach keywords to web resources in order to describe or classify their contents bares an enormous potential for structuring information which facilitates subsequent access by both the original user and other users. This task, commonly referred to as tagging is simple enough not to scare users away, yet the benefit of web resources annotated in such a way is obvious enough to keep the motivation to supply tags high. The process of attaching tags to web resource must therefore show a fine balance between
simplicity and quality. Both of these properties could be greatly improved an automatic system could support a user by recommending tags for a given In this paper, we describe the ARKTiS system, developed to recommend tags o a user for two specific types of web resources. The system was developed as a contribution to an international challenge as part of the 2009 European Confer- ence on Machine Learning and Principles and Practice of Knowledge Discovery in Databases(ECML PKDD 2009) 2 Task and data The goal of this challenge is the implementation of a system that can auto- matically generate tag recommendations for a given resource. Here, a resource is either a bookmark of a web page or a BIBTEX entry for different kinds of documents. Tags typically are short English words although they may also be artificially created terms, generated e. g by concatenating words("indexforum") or by using abbreviations ("langfr", for"language french"). The number of tags a system may generate is restricted to a maximum of five To prepare for the challenge, a training set of manually tagged reso was provided. The data set consists of web page bookmarks and BIBTEX entries taken from the bib sonomy project Each entry has a unique id and was tagged by at least two users. Thus a point in the data set can be viewed as a triple <resource-id, user-id, tags For each resource, the corpus contains meta-data describing the resource with a number of different fields. These fields are different for BIBTEX entries and for bookmark entries. For instance, the meta-data for BIBTEX entries contain fields describing the title of an article, the authors, the year of publication, or the number of pages. For bookmarks, one field gives a short description of the resource while another one contains the web pages'URL. A full list of all available fields can be found on the homepage of the challenge In total, the training corpus contains 41, 268 entries for bookmarks and 22, 852 IBTEX entries, annotated with 1, 3276 unique tags by 1, 185 different users The data of the actual challenge(the eval set), was provided 48 hours before the submission deadline. This set consists of unseen data that each system had to tag and all results that are presented and analyzed in section 5 were achieved on this set. The evaluation data set contains 43, 002 entries in total, with 26, 104 BIBTEX- and 16, 898 bookmark-entries-circa two thirds of the amount of the For the remainder of this paper, we will refer to this process as"(automatic)tagging
simplicity and quality. Both of these properties could be greatly improved if an automatic system could support a user by recommending tags for a given resource. In this paper, we describe the ARKTiS system, developed to recommend tags to a user for two specific types of web resources. The system was developed as a contribution to an international challenge as part of the 2009 European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD 2009). 2 Task and Data The goal of this challenge is the implementation of a system that can automatically generate tag recommendations1 for a given resource. Here, a resource is either a bookmark of a web page or a BibTEX entry for different kinds of documents. Tags typically are short English words although they may also be artificially created terms, generated e.g. by concatenating words (“indexforum”) or by using abbreviations (“langfr”, for “language french”). The number of tags a system may generate is restricted to a maximum of five. To prepare for the challenge, a training set of manually tagged resources was provided. The data set consists of web page bookmarks and BibTEX entries taken from the BibSonomy project2 . Each entry has a unique id and was tagged by at least two users. Thus a point in the data set can be viewed as a triple <resource-id, user-id, tags>. For each resource, the corpus contains meta-data describing the resource with a number of different fields. These fields are different for BibTEX entries and for bookmark entries. For instance, the meta-data for BibTEX entries contain fields describing the title of an article, the authors, the year of publication, or the number of pages. For bookmarks, one field gives a short description of the resource while another one contains the web pages’ URL. A full list of all available fields can be found on the homepage of the challenge. In total, the training corpus contains 41,268 entries for bookmarks and 22,852 BibTEX entries, annotated with 1,3276 unique tags by 1,185 different users. The data of the actual challenge (the eval set), was provided 48 hours before the submission deadline. This set consists of unseen data that each system had to tag and all results that are presented and analyzed in section 5 were achieved on this set. The evaluation data set contains 43,002 entries in total, with 26,104 BibTEX- and 16,898 bookmark-entries - circa two thirds of the amount of the training data. 1 For the remainder of this paper, we will refer to this process as “(automatic) tagging” 2 http://www.bibsonomy.org
3 Approach One key observation for our participation in the ECML PKDD challenge was that time played a central role in two different senses. First, the task required each system to suggest tags for quite a large number of resources in a rather short period of time: 43. 002 entries only 48 hours, including retrieval and parsing of the test data as well as formatting and uploading of the final result data. Second, since the challenge had a fixed deadline, the time to develop a running system faced a naturally limit with the release of the 48 hour evaluation period Both points had a direct influence on the conceptualization and realization of our system ARKTis, in that a number of more sophisticated ideas had to be acrificed. As a result, ARKTis can be seen as an exercise in software engineer ing rather than thorough science. The final system implements straight-forward strategies with a focus on robustness and processing speed 3.1 Motivation As outlined above, the training corpus contains 13276 different tags for over 41268 data points, a proportion that indicates a potential data sparseness prob- lem for classical machine learning approaches. We therefore opted for an algo- rithmic approach instead, based on heuristic considerations Since the desired system output is(English) words, we can distinguish two potential sources for output: from within the resource itself (internal words )or from outside material (external words). This distinction is in so far blurred, as the system input actually consists not of the resources themselves, but rather of meta-data. In so far, even tags taken from the resources themselves could be argued to be external. We take the view that words stemming from meta-data or the resources referred to by the meta-data are considered internal. Since we could not hope to implement a competitive system, we were mainly interested in how useful such a distinction would be in terms of recommending tags. Although we concentrated on internal methods as described below, we explored using document similarity measures in the BIBTEX module to re-use tags that were manually assigned to documents similar to the current system input. Also, some of our implemented techniques, such as translating German words from the original resource to english, can be considered borderline between For the internal approaches, we looked at the task of tagging a resource as an talogy to automatic text summarization, somewhat taken to an extreme where a"summary"consists only of five words In extractive summarization, of documents are generated by identifying those sentences in a document which when concatenated serve as surrogate for the original document. In that spirit tagging becomes the task of identifying those words from a resource that together describe the“ aboutness” of the resource
3 Approach One key observation for our participation in the ECML PKDD challenge was that time played a central role in two different senses. First, the task required each system to suggest tags for quite a large number of resources in a rather short period of time: 43,002 entries in only 48 hours, including retrieval and parsing of the test data as well as formatting and uploading of the final result data. Second, since the challenge had a fixed deadline, the time to develop a running system faced a naturally limit with the release of the 48 hour evaluation period. Both points had a direct influence on the conceptualization and realization of our system ARKTiS, in that a number of more sophisticated ideas had to be sacrificed. As a result, ARKTiS can be seen as an exercise in software engineering rather than thorough science. The final system implements straight-forward strategies with a focus on robustness and processing speed. 3.1 Motivation As outlined above, the training corpus contains 13276 different tags for over 41268 data points, a proportion that indicates a potential data sparseness problem for classical machine learning approaches. We therefore opted for an algorithmic approach instead, based on heuristic considerations. Since the desired system output is (English) words, we can distinguish two potential sources for output: from within the resource itself (internal words) or from outside material (external words). This distinction is in so far blurred, as the system input actually consists not of the resources themselves, but rather of meta-data. In so far, even tags taken from the resources themselves could be argued to be external. We take the view that words stemming from meta-data or the resources referred to by the meta-data are considered internal. Since we could not hope to implement a competitive system, we were mainly interested in how useful such a distinction would be in terms of recommending tags. Although we concentrated on internal methods as described below, we explored using document similarity measures in the BibTEX module to re-use tags that were manually assigned to documents similar to the current system input. Also, some of our implemented techniques, such as translating German words from the original resource to English, can be considered borderline between internal and external. For the internal approaches, we looked at the task of tagging a resource as an analogy to automatic text summarization, somewhat taken to an extreme where a “summary” consists only of five words. In extractive summarization, summaries of documents are generated by identifying those sentences in a document which when concatenated serve as surrogate for the original document. In that spirit, tagging becomes the task of identifying those words from a resource that together describe the “aboutness” of the resource
3.2 Related work A number of researchers in recent years have engaged in the task of developing an automatic tagging system. 2 use a natural language resources to suggest tags for BIBTEX entries and web pages. They include conceptual information external esources, such as WordNet 3, to create the notion of a"concept space". On top of this notion, they exploit the textual content that can be associated with bookmarks, documents and users and generate models within the concept space or the tag space derived from the training data 4 model the problem of automated tag suggestion as a multi-label text classification problem with tags as categories In 5, the TAG ASSIST system focuses on the task of the generation of tags for web-log entries. They access tags of similar documents in a similar spirit to our own method described in section 4.1 In addition to these concrete systems, we find automatic tagging to bare some similarities with research in automatic extractive summarization. in both task the identification of salient portions of a resource's text is a central consideration For tagging which reduces extraction single words, we call such a method an internal approach. (s. section 3.1) For instance, in 6, the author conducted a wide range of tests to find predic tive features for relevant sentences. Despite relying on manual experiments, the general results from this early research were later confirmed by machine learn- ing approaches, e. g, 7. For the bookmark modules, both the title and the first sentence heuristic (see 4.2)were inspired by these findings aggers As hinted by the data set, the task can be viewed as two different sub-tasks the tagging of BIBTEX entries and the tagging of bookmarked web pages. Con sequently, the ARKTis system consists of two independent modules which are both instances of a common framework architecture, depicted in Figure 1. The modules can be run in two distinct processes Efficient processing of the input data is an important requirement for this challenge. In a sequential architecture, processing 43002 data points in 48 hours would leave a tagging system about 4 seconds per data point on average. Given that the data points contain only metadata and that the actual documents, if needed, have to be retrieved through the internet and parsed, a time span of 4 seconds poses quite a strong limitation on the complexity of the performed computations. Running multiple instances of taggers concurrently relaxes this limitation In our current setup, both modules for BIBTEX and bookmark tag ging internally run ten tagging threads in parallel which increases the maximum average processing time to 80 seconds per data point
3.2 Related Work A number of researchers in recent years have engaged in the task of developing an automatic tagging system. [2] use a natural language resources to suggest tags for BibTEX entries and web pages. They include conceptual information external resources, such as WordNet [3], to create the notion of a “concept space”. On top of this notion, they exploit the textual content that can be associated with bookmarks, documents and users and generate models within the concept space or the tag space derived from the training data. [4] model the problem of automated tag suggestion as a multi-label text classification problem with tags as categories. In [5], the TagAssist system focuses on the task of the generation of tags for web-log entries. They access tags of similar documents in a similar spirit to our own method described in section 4.1. In addition to these concrete systems, we find automatic tagging to bare some similarities with research in automatic extractive summarization. In both task, the identification of salient portions of a resource’s text is a central consideration. For tagging which reduces extraction single words, we call such a method an internal approach. (s. section 3.1). For instance, in [6], the author conducted a wide range of tests to find predictive features for relevant sentences. Despite relying on manual experiments, the general results from this early research were later confirmed by machine learning approaches, e.g., [7]. For the bookmark modules, both the title and the first sentence heuristic (see 4.2) were inspired by these findings. 4 Taggers As hinted by the data set, the task can be viewed as two different sub-tasks, the tagging of BibTEX entries and the tagging of bookmarked web pages. Consequently, the ARKTiS system consists of two independent modules which are both instances of a common framework architecture, depicted in Figure 1. The modules can be run in two distinct processes. Efficient processing of the input data is an important requirement for this challenge. In a sequential architecture, processing 43002 data points in 48 hours would leave a tagging system about 4 seconds per data point on average. Given that the data points contain only metadata and that the actual documents, if needed, have to be retrieved through the internet and parsed, a time span of 4 seconds poses quite a strong limitation on the complexity of the performed computations. Running multiple instances of taggers concurrently relaxes this limitation. In our current setup, both modules for BibTEX and bookmark tagging internally run ten tagging threads in parallel which increases the maximum average processing time to 80 seconds per data point
i tagger Handler : Fig. 1. The parallel architecture of ARKTis 4.1 The BibTEXTagger The tagging system responsible for the BIBTEX entries uses a combination of in- ternal and external techniques. a thorough investigation of the provided training material showed that most of the entries(95. 4%)do not contain a valid link to the actual PDF document. This is unfortunate, as it limits erternal approaches which draw tags from the contents of the document in question Internal approach To compensate the cases in which the PdF document is available, we use the remaining information from the meta-data, namely the title of the document, its description and its abstract. The employed approach alyzes these fields and extracts tags directly out of their textual information Before that, we lowercase all words in the text of each field and remove all punc- tuation and symbols. After that, we apply the POS tagging system described in 8 to extract content-words -nouns, adjectives and verbs- out of the text. The sequential processing of the text is shown belot Pre-processing Original title: Th itation Ranking: Bringing Order to the web citation ranking bringing order to the web Extraction of Tags POS-tagged: ranking/NN bringing/VBG N to/to the/DT web/NN n ranking order web Fig. 2. Sequential processing of textual contents After removing stop-words, the remaining words are directly used as tags giving preference to tags stemming from the title field over those from description field over those from the abstract field. Only the first five tags are returned after filtering out duplicate
Fig. 1. The parallel architecture of ARKTiS. 4.1 The BibTEXTagger The tagging system responsible for the BibTEX entries uses a combination of internal and external techniques. A thorough investigation of the provided training material showed that most of the entries (95.4%) do not contain a valid link to the actual PDF document. This is unfortunate, as it limits external approaches which draw tags from the contents of the document in question. Internal approach To compensate the cases in which the PDF document is unavailable, we use the remaining information from the meta-data, namely the title of the document, its description and its abstract. The employed approach analyzes these fields and extracts tags directly out of their textual information. Before that, we lowercase all words in the text of each field and remove all punctuation and symbols. After that, we apply the POS tagging system described in [8] to extract content-words - nouns, adjectives and verbs - out of the text. The sequential processing of the text is shown below: Pre-processing Original title: The PageRank Citation Ranking: Bringing Order to the Web Lowercased: the pagerank citation ranking: bringing order to the web No symbols: the pagerank citation ranking bringing order to the web Extraction of Tags POS-tagged: the/DT pagerank/NN citation/NN ranking/NN bringing/VBG order/NN to/TO the/DT web/NN Content words: pagerank citation ranking order web Fig. 2. Sequential processing of textual contents After removing stop-words, the remaining words are directly used as tags, giving preference to tags stemming from the title field over those from description field over those from the abstract field. Only the first five tags are returned after filtering out duplicates