Automatic Extraction of Titles from General Documents using Machine Learning Yunhua Hu1 Computer Science Department Xi"an Jiaotong University No 28, Xianning West Road Xi'an, China, 710049 yunhuahu@mail.xjtu.edu.cn Hang Li, Yunbo Cao Microsoft Research Asia 5F Sigma Center, No. 49 Zhichun Road, Haidian, Beijing, China, 100080 {hangli,yucao}@microsoft.com Qinghua Zheng Computer Science Department Xi"an Jiaotong University No 28, Xianning West Road Xi'an, China, 710049 qhzheng@mail.xjtu.edu.cn Dmitriy Meyerzon Microsoft Corporation One Microsoft Way Redmond, WA, USA, 98052 dmitriym@microsoft.com ABSTRACT In this paper, we propose a machine learning approach to title extraction from general documents. By general documents, we mean documents that can belong to any one of a number of specific genres, including presentations, book chapters, technical papers, brochures, reports, and letters. Previously, methods have been proposed mainly for title extraction from research papers. It has not been clear whether it could be possible to conduct automatic title extraction from general documents. As a case study, we consider extraction from Office including Word and PowerPoint. In our approach, we annotate titles in sample documents (for Word and PowerPoint respectively) and take them as training data, train machine learning models, and perform title extraction using the trained models. Our method is unique in that we mainly utilize formatting information such as font size as features in the models. It turns out that the use of formatting information can lead to quite accurate extraction from general documents. Precision and recall for title extraction from Word is 0.810 and 0.837 respectively, and precision and recall for title extraction from PowerPoint is 0.875 and 0.895 respectively in an experiment on intranet data. Other important new findings in this work include that we can train models in one domain and apply them to another domain, and more surprisingly we can even train models in one language and apply them to another language. Moreover, we can significantly improve search ranking results in document retrieval by using the extracted titles. Categories and Subject Descriptors H.3.3 [Information Storage and Retrieval]: Information Search and Retrieval - Search Process; H.4.1 [Information Systems Applications]: Office Automation - Word processing; D.2.8 [Software Engineering]: Metrics - complexity measures, performance measures General Terms Algorithms, Experimentation, Performance. 1. INTRODUCTION Metadata of documents is useful for many kinds of document processing such as search, browsing, and filtering. Ideally, metadata is defined by the authors of documents and is then used by various systems. However, people seldom define document metadata by themselves, even when they have convenient metadata definition tools [26]. Thus, how to automatically extract metadata from the bodies of documents turns out to be an important research issue. Methods for performing the task have been proposed. However, the focus was mainly on extraction from research papers. For instance, Han et al. [10] proposed a machine learning based method to conduct extraction from research papers. They formalized the problem as that of classification and employed Support Vector Machines as the classifier. They mainly used linguistic features in the model.1 In this paper, we consider metadata extraction from general documents. By general documents, we mean documents that may belong to any one of a number of specific genres. General documents are more widely available in digital libraries, intranets and the internet, and thus investigation on extraction from them is sorely needed. Research papers usually have well-formed styles and noticeable characteristics. In contrast, the styles of general documents can vary greatly. It has not been clarified whether a machine learning based approach can work well for this task. There are many types of metadata: title, author, date of creation, etc. As a case study, we consider title extraction in this paper. General documents can be in many different file formats: Microsoft Office, PDF (PS), etc. As a case study, we consider extraction from Office including Word and PowerPoint. We take a machine learning approach. We annotate titles in sample documents (for Word and PowerPoint respectively) and take them as training data to train several types of models, and perform title extraction using any one type of the trained models. In the models, we mainly utilize formatting information such as font size as features. We employ the following models: Maximum Entropy Model, Perceptron with Uneven Margins, Maximum Entropy Markov Model, and Voted Perceptron. In this paper, we also investigate the following three problems, which did not seem to have been examined previously. (1) Comparison between models: among the models above, which model performs best for title extraction; (2) Generality of model: whether it is possible to train a model on one domain and apply it to another domain, and whether it is possible to train a model in one language and apply it to another language; (3) Usefulness of extracted titles: whether extracted titles can improve document processing such as search. Experimental results indicate that our approach works well for title extraction from general documents. Our method can significantly outperform the baselines: one that always uses the first lines as titles and the other that always uses the lines in the largest font sizes as titles. Precision and recall for title extraction from Word are 0.810 and 0.837 respectively, and precision and recall for title extraction from PowerPoint are 0.875 and 0.895 respectively. It turns out that the use of format features is the key to successful title extraction. (1) We have observed that Perceptron based models perform better in terms of extraction accuracies. (2) We have empirically verified that the models trained with our approach are generic in the sense that they can be trained on one domain and applied to another, and they can be trained in one language and applied to another. (3) We have found that using the extracted titles we can significantly improve precision of document retrieval (by 10%). We conclude that we can indeed conduct reliable title extraction from general documents and use the extracted results to improve real applications. The rest of the paper is organized as follows. In section 2, we introduce related work, and in section 3, we explain the motivation and problem setting of our work. In section 4, we describe our method of title extraction, and in section 5, we describe our method of document retrieval using extracted titles. Section 6 gives our experimental results. We make concluding remarks in section 7. 2. RELATED WORK 2.1 Document Metadata Extraction Methods have been proposed for performing automatic metadata extraction from documents; however, the main focus was on extraction from research papers. The proposed methods fall into two categories: the rule based approach and the machine learning based approach. Giuffrida et al. [9], for instance, developed a rule-based system for automatically extracting metadata from research papers in Postscript. They used rules like titles are usually located on the upper portions of the first pages and they are usually in the largest font sizes. Liddy et al. [14] and Yilmazel el al. [23] performed metadata extraction from educational materials using rule-based natural language processing technologies. Mao et al. [16] also conducted automatic metadata extraction from research papers using rules on formatting information. The rule-based approach can achieve high performance. However, it also has disadvantages. It is less adaptive and robust when compared with the machine learning approach. Han et al. [10], for instance, conducted metadata extraction with the machine learning approach. They viewed the problem as that of classifying the lines in a document into the categories of metadata and proposed using Support Vector Machines as the classifier. They mainly used linguistic information as features. They reported high extraction accuracy from research papers in terms of precision and recall. 2.2 Information Extraction Metadata extraction can be viewed as an application of information extraction, in which given a sequence of instances, we identify a subsequence that represents information in which we are interested. Hidden Markov Model [6], Maximum Entropy Model [1, 4], Maximum Entropy Markov Model [17], Support Vector Machines [3], Conditional Random Field [12], and Voted Perceptron [2] are widely used information extraction models. Information extraction has been applied, for instance, to part-ofspeech tagging [20], named entity recognition [25] and table extraction [19]. 2.3 Search Using Title Information Title information is useful for document retrieval. In the system Citeseer, for instance, Giles et al. managed to extract titles from research papers and make use of the extracted titles in metadata search of papers [8]. In web search, the title fields (i.e., file properties) and anchor texts of web pages (HTML documents) can be viewed as ‘titles" of the pages [5]. Many search engines seem to utilize them for web page retrieval [7, 11, 18, 22]. Zhang et al., found that web pages with well-defined metadata are more easily retrieved than those without well-defined metadata [24]. To the best of our knowledge, no research has been conducted on using extracted titles from general documents (e.g., Office documents) for search of the documents. 146 3. MOTIVATION AND PROBLEM SETTING We consider the issue of automatically extracting titles from general documents. By general documents, we mean documents that belong to one of any number of specific genres. The documents can be presentations, books, book chapters, technical papers, brochures, reports, memos, specifications, letters, announcements, or resumes. General documents are more widely available in digital libraries, intranets, and internet, and thus investigation on title extraction from them is sorely needed. Figure 1 shows an estimate on distributions of file formats on intranet and internet [15]. Office and PDF are the main file formats on the intranet. Even on the internet, the documents in the formats are still not negligible, given its extremely large size. In this paper, without loss of generality, we take Office documents as an example. Figure 1. Distributions of file formats in internet and intranet. For Office documents, users can define titles as file properties using a feature provided by Office. We found in an experiment, however, that users seldom use the feature and thus titles in file properties are usually very inaccurate. That is to say, titles in file properties are usually inconsistent with the ‘true" titles in the file bodies that are created by the authors and are visible to readers. We collected 6,000 Word and 6,000 PowerPoint documents from an intranet and the internet and examined how many titles in the file properties are correct. We found that surprisingly the accuracy was only 0.265 (cf., Section 6.3 for details). A number of reasons can be considered. For example, if one creates a new file by copying an old file, then the file property of the new file will also be copied from the old file. In another experiment, we found that Google uses the titles in file properties of Office documents in search and browsing, but the titles are not very accurate. We created 50 queries to search Word and PowerPoint documents and examined the top 15 results of each query returned by Google. We found that nearly all the titles presented in the search results were from the file properties of the documents. However, only 0.272 of them were correct. Actually, ‘true" titles usually exist at the beginnings of the bodies of documents. If we can accurately extract the titles from the bodies of documents, then we can exploit reliable title information in document processing. This is exactly the problem we address in this paper. More specifically, given a Word document, we are to extract the title from the top region of the first page. Given a PowerPoint document, we are to extract the title from the first slide. A title sometimes consists of a main title and one or two subtitles. We only consider extraction of the main title. As baselines for title extraction, we use that of always using the first lines as titles and that of always using the lines with largest font sizes as titles. Figure 2. Title extraction from Word document. Figure 3. Title extraction from PowerPoint document. Next, we define a ‘specification" for human judgments in title data annotation. The annotated data will be used in training and testing of the title extraction methods. Summary of the specification: The title of a document should be identified on the basis of common sense, if there is no difficulty in the identification. However, there are many cases in which the identification is not easy. There are some rules defined in the specification that guide identification for such cases. The rules include a title is usually in consecutive lines in the same format, a document can have no title, titles in images are not considered, a title should not contain words like ‘draft", 147 ‘whitepaper", etc, if it is difficult to determine which is the title, select the one in the largest font size, and if it is still difficult to determine which is the title, select the first candidate. (The specification covers all the cases we have encountered in data annotation.) Figures 2 and 3 show examples of Office documents from which we conduct title extraction. In Figure 2, ‘Differences in Win32 API Implementations among Windows Operating Systems" is the title of the Word document. ‘Microsoft Windows" on the top of this page is a picture and thus is ignored. In Figure 3, ‘Building Competitive Advantages through an Agile Infrastructure" is the title of the PowerPoint document. We have developed a tool for annotation of titles by human annotators. Figure 4 shows a snapshot of the tool. Figure 4. Title annotation tool. 4. TITLE EXTRACTION METHOD 4.1 Outline Title extraction based on machine learning consists of training and extraction. The same pre-processing step occurs before training and extraction. During pre-processing, from the top region of the first page of a Word document or the first slide of a PowerPoint document a number of units for processing are extracted. If a line (lines are separated by ‘return" symbols) only has a single format, then the line will become a unit. If a line has several parts and each of them has its own format, then each part will become a unit. Each unit will be treated as an instance in learning. A unit contains not only content information (linguistic information) but also formatting information. The input to pre-processing is a document and the output of pre-processing is a sequence of units (instances). Figure 5 shows the units obtained from the document in Figure 2. Figure 5. Example of units. In learning, the input is sequences of units where each sequence corresponds to a document. We take labeled units (labeled as title_begin, title_end, or other) in the sequences as training data and construct models for identifying whether a unit is title_begin title_end, or other. We employ four types of models: Perceptron, Maximum Entropy (ME), Perceptron Markov Model (PMM), and Maximum Entropy Markov Model (MEMM). In extraction, the input is a sequence of units from one document. We employ one type of model to identify whether a unit is title_begin, title_end, or other. We then extract units from the unit labeled with ‘title_begin" to the unit labeled with ‘title_end". The result is the extracted title of the document. The unique characteristic of our approach is that we mainly utilize formatting information for title extraction. Our assumption is that although general documents vary in styles, their formats have certain patterns and we can learn and utilize the patterns for title extraction. This is in contrast to the work by Han et al., in which only linguistic features are used for extraction from research papers. 4.2 Models The four models actually can be considered in the same metadata extraction framework. That is why we apply them together to our current problem. Each input is a sequence of instances kxxx L21 together with a sequence of labels kyyy L21 . ix and iy represents an instance and its label, respectively ( ki ,,2,1 L= ). Recall that an instance here represents a unit. A label represents title_begin, title_end, or other. Here, k is the number of units in a document. In learning, we train a model which can be generally denoted as a conditional probability distribution )|( 11 kk XXYYP LL where iX and iY denote random variables taking instance ix and label iy as values, respectively ( ki ,,2,1 L= ). Learning Tool Extraction Tool 21121 2222122221 1121111211 nknnknn kk kk yyyxxx yyyxxx yyyxxx LL LL LL LL → → → )|(maxarg 11 mkmmkm xxyyP LL )|( 11 kk XXYYP LL Conditional Distribution mkmm xxx L21 Figure 6. Metadata extraction model. We can make assumptions about the general model in order to make it simple enough for training. 148 For example, we can assume that kYY ,,1 L are independent of each other given kXX ,,1 L . Thus, we have )|()|( )|( 11 11 kk kk XYPXYP XXYYP L LL = In this way, we decompose the model into a number of classifiers. We train the classifiers locally using the labeled data. As the classifier, we employ the Perceptron or Maximum Entropy model. We can also assume that the first order Markov property holds for kYY ,,1 L given kXX ,,1 L . Thus, we have )|()|( )|( 111 11 kkk kk XYYPXYP XXYYP −= L LL Again, we obtain a number of classifiers. However, the classifiers are conditioned on the previous label. When we employ the Percepton or Maximum Entropy model as a classifier, the models become a Percepton Markov Model or Maximum Entropy Markov Model, respectively. That is to say, the two models are more precise. In extraction, given a new sequence of instances, we resort to one of the constructed models to assign a sequence of labels to the sequence of instances, i.e., perform extraction. For Perceptron and ME, we assign labels locally and combine the results globally later using heuristics. Specifically, we first identify the most likely title_begin. Then we find the most likely title_end within three units after the title_begin. Finally, we extract as a title the units between the title_begin and the title_end. For PMM and MEMM, we employ the Viterbi algorithm to find the globally optimal label sequence. In this paper, for Perceptron, we actually employ an improved variant of it, called Perceptron with Uneven Margin [13]. This version of Perceptron can work well especially when the number of positive instances and the number of negative instances differ greatly, which is exactly the case in our problem. We also employ an improved version of Perceptron Markov Model in which the Perceptron model is the so-called Voted Perceptron [2]. In addition, in training, the parameters of the model are updated globally rather than locally. 4.3 Features There are two types of features: format features and linguistic features. We mainly use the former. The features are used for both the title-begin and the title-end classifiers. 4.3.1 Format Features Font Size: There are four binary features that represent the normalized font size of the unit (recall that a unit has only one type of font). If the font size of the unit is the largest in the document, then the first feature will be 1, otherwise 0. If the font size is the smallest in the document, then the fourth feature will be 1, otherwise 0. If the font size is above the average font size and not the largest in the document, then the second feature will be 1, otherwise 0. If the font size is below the average font size and not the smallest, the third feature will be 1, otherwise 0. It is necessary to conduct normalization on font sizes. For example, in one document the largest font size might be ‘12pt", while in another the smallest one might be ‘18pt". Boldface: This binary feature represents whether or not the current unit is in boldface. Alignment: There are four binary features that respectively represent the location of the current unit: ‘left", ‘center", ‘right", and ‘unknown alignment". The following format features with respect to ‘context" play an important role in title extraction. Empty Neighboring Unit: There are two binary features that represent, respectively, whether or not the previous unit and the current unit are blank lines. Font Size Change: There are two binary features that represent, respectively, whether or not the font size of the previous unit and the font size of the next unit differ from that of the current unit. Alignment Change: There are two binary features that represent, respectively, whether or not the alignment of the previous unit and the alignment of the next unit differ from that of the current one. Same Paragraph: There are two binary features that represent, respectively, whether or not the previous unit and the next unit are in the same paragraph as the current unit. 4.3.2 Linguistic Features The linguistic features are based on key words. Positive Word: This binary feature represents whether or not the current unit begins with one of the positive words. The positive words include ‘title:", ‘subject:", ‘subject line:" For example, in some documents the lines of titles and authors have the same formats. However, if lines begin with one of the positive words, then it is likely that they are title lines. Negative Word: This binary feature represents whether or not the current unit begins with one of the negative words. The negative words include ‘To", ‘By", ‘created by", ‘updated by", etc. There are more negative words than positive words. The above linguistic features are language dependent. Word Count: A title should not be too long. We heuristically create four intervals: [1, 2], [3, 6], [7, 9] and [9, ∞) and define one feature for each interval. If the number of words in a title falls into an interval, then the corresponding feature will be 1; otherwise 0. Ending Character: This feature represents whether the unit ends with ‘:", ‘-", or other special characters. A title usually does not end with such a character. 5. DOCUMENT RETRIEVAL METHOD We describe our method of document retrieval using extracted titles. Typically, in information retrieval a document is split into a number of fields including body, title, and anchor text. A ranking function in search can use different weights for different fields of 149 the document. Also, titles are typically assigned high weights, indicating that they are important for document retrieval. As explained previously, our experiment has shown that a significant number of documents actually have incorrect titles in the file properties, and thus in addition of using them we use the extracted titles as one more field of the document. By doing this, we attempt to improve the overall precision. In this paper, we employ a modification of BM25 that allows field weighting [21]. As fields, we make use of body, title, extracted title and anchor. First, for each term in the query we count the term frequency in each field of the document; each field frequency is then weighted according to the corresponding weight parameter: ∑= f tfft tfwwtf Similarly, we compute the document length as a weighted sum of lengths of each field. Average document length in the corpus becomes the average of all weighted document lengths. ∑= f ff dlwwdl In our experiments we used 75.0,8.11 == bk . Weight for content was 1.0, title was 10.0, anchor was 10.0, and extracted title was 5.0. 6. EXPERIMENTAL RESULTS 6.1 Data Sets and Evaluation Measures We used two data sets in our experiments. First, we downloaded and randomly selected 5,000 Word documents and 5,000 PowerPoint documents from an intranet of Microsoft. We call it MS hereafter. Second, we downloaded and randomly selected 500 Word and 500 PowerPoint documents from the DotGov and DotCom domains on the internet, respectively. Figure 7 shows the distributions of the genres of the documents. We see that the documents are indeed ‘general documents" as we define them. Figure 7. Distributions of document genres. Third, a data set in Chinese was also downloaded from the internet. It includes 500 Word documents and 500 PowerPoint documents in Chinese. We manually labeled the titles of all the documents, on the basis of our specification. Not all the documents in the two data sets have titles. Table 1 shows the percentages of the documents having titles. We see that DotCom and DotGov have more PowerPoint documents with titles than MS. This might be because PowerPoint documents published on the internet are more formal than those on the intranet. Table 1. The portion of documents with titles Domain Type MS DotCom DotGov Word 75.7% 77.8% 75.6% PowerPoint 82.1% 93.4% 96.4% In our experiments, we conducted evaluations on title extraction in terms of precision, recall, and F-measure. The evaluation measures are defined as follows: Precision: P = A / ( A + B ) Recall: R = A / ( A + C ) F-measure: F1 = 2PR / ( P + R ) Here, A, B, C, and D are numbers of documents as those defined in Table 2. Table 2. Contingence table with regard to title extraction Is title Is not title Extracted A B Not extracted C D 6.2 Baselines We test the accuracies of the two baselines described in section 4.2. They are denoted as ‘largest font size" and ‘first line" respectively. 6.3 Accuracy of Titles in File Properties We investigate how many titles in the file properties of the documents are reliable. We view the titles annotated by humans as true titles and test how many titles in the file properties can approximately match with the true titles. We use Edit Distance to conduct the approximate match. (Approximate match is only used in this evaluation). This is because sometimes human annotated titles can be slightly different from the titles in file properties on the surface, e.g., contain extra spaces). Given string A and string B: if ( (D == 0) or ( D / ( La + Lb ) < θ ) ) then string A = string B D: Edit Distance between string A and string B La: length of string A Lb: length of string B θ: 0.1 ∑ × ++− + = t t n N wtf avwdl wdl bbk kwtf FBM )log( ))1(( )1( 25 1 1 150 Table 3. Accuracies of titles in file properties File Type Domain Precision Recall F1 MS 0.299 0.311 0.305 DotCom 0.210 0.214 0.212Word DotGov 0.182 0.177 0.180 MS 0.229 0.245 0.237 DotCom 0.185 0.186 0.186PowerPoint DotGov 0.180 0.182 0.181 6.4 Comparison with Baselines We conducted title extraction from the first data set (Word and PowerPoint in MS). As the model, we used Perceptron. We conduct 4-fold cross validation. Thus, all the results reported here are those averaged over 4 trials. Tables 4 and 5 show the results. We see that Perceptron significantly outperforms the baselines. In the evaluation, we use exact matching between the true titles annotated by humans and the extracted titles. Table 4. Accuracies of title extraction with Word Precision Recall F1 Model Perceptron 0.810 0.837 0.823 Largest font size 0.700 0.758 0.727 Baselines First line 0.707 0.767 0.736 Table 5. Accuracies of title extraction with PowerPoint Precision Recall F1 Model Perceptron 0.875 0. 895 0.885 Largest font size 0.844 0.887 0.865 Baselines First line 0.639 0.671 0.655 We see that the machine learning approach can achieve good performance in title extraction. For Word documents both precision and recall of the approach are 8 percent higher than those of the baselines. For PowerPoint both precision and recall of the approach are 2 percent higher than those of the baselines. We conduct significance tests. The results are shown in Table 6. Here, ‘Largest" denotes the baseline of using the largest font size, ‘First" denotes the baseline of using the first line. The results indicate that the improvements of machine learning over baselines are statistically significant (in the sense p-value < 0.05) Table 6. Sign test results Documents Type Sign test between p-value Perceptron vs. Largest 3.59e-26 Word Perceptron vs. First 7.12e-10 Perceptron vs. Largest 0.010 PowerPoint Perceptron vs. First 5.13e-40 We see, from the results, that the two baselines can work well for title extraction, suggesting that font size and position information are most useful features for title extraction. However, it is also obvious that using only these two features is not enough. There are cases in which all the lines have the same font size (i.e., the largest font size), or cases in which the lines with the largest font size only contain general descriptions like ‘Confidential", ‘White paper", etc. For those cases, the ‘largest font size" method cannot work well. For similar reasons, the ‘first line" method alone cannot work well, either. With the combination of different features (evidence in title judgment), Perceptron can outperform Largest and First. We investigate the performance of solely using linguistic features. We found that it does not work well. It seems that the format features play important roles and the linguistic features are supplements.. Figure 8. An example Word document. Figure 9. An example PowerPoint document. We conducted an error analysis on the results of Perceptron. We found that the errors fell into three categories. (1) About one third of the errors were related to ‘hard cases". In these documents, the layouts of the first pages were difficult to understand, even for humans. Figure 8 and 9 shows examples. (2) Nearly one fourth of the errors were from the documents which do not have true titles but only contain bullets. Since we conduct extraction from the top regions, it is difficult to get rid of these errors with the current approach. (3). Confusions between main titles and subtitles were another type of error. Since we only labeled the main titles as titles, the extractions of both titles were considered incorrect. This type of error does little harm to document processing like search, however. 6.5 Comparison between Models To compare the performance of different machine learning models, we conducted another experiment. Again, we perform 4-fold cross 151 validation on the first data set (MS). Table 7, 8 shows the results of all the four models. It turns out that Perceptron and PMM perform the best, followed by MEMM, and ME performs the worst. In general, the Markovian models perform better than or as well as their classifier counterparts. This seems to be because the Markovian models are trained globally, while the classifiers are trained locally. The Perceptron based models perform better than the ME based counterparts. This seems to be because the Perceptron based models are created to make better classifications, while ME models are constructed for better prediction. Table 7. Comparison between different learning models for title extraction with Word Model Precision Recall F1 Perceptron 0.810 0.837 0.823 MEMM 0.797 0.824 0.810 PMM 0.827 0.823 0.825 ME 0.801 0.621 0.699 Table 8. Comparison between different learning models for title extraction with PowerPoint Model Precision Recall F1 Perceptron 0.875 0. 895 0. 885 MEMM 0.841 0.861 0.851 PMM 0.873 0.896 0.885 ME 0.753 0.766 0.759 6.6 Domain Adaptation We apply the model trained with the first data set (MS) to the second data set (DotCom and DotGov). Tables 9-12 show the results. Table 9. Accuracies of title extraction with Word in DotGov Precision Recall F1 Model Perceptron 0.716 0.759 0.737 Largest font size 0.549 0.619 0.582Baselines First line 0.462 0.521 0.490 Table 10. Accuracies of title extraction with PowerPoint in DotGov Precision Recall F1 Model Perceptron 0.900 0.906 0.903 Largest font size 0.871 0.888 0.879Baselines First line 0.554 0.564 0.559 Table 11. Accuracies of title extraction with Word in DotCom Precisio n Recall F1 Model Perceptron 0.832 0.880 0.855 Largest font size 0.676 0.753 0.712Baselines First line 0.577 0.643 0.608 Table 12. Performance of PowerPoint document title extraction in DotCom Precisio n Recall F1 Model Perceptron 0.910 0.903 0.907 Largest font size 0.864 0.886 0.875Baselines First line 0.570 0.585 0.577 From the results, we see that the models can be adapted to different domains well. There is almost no drop in accuracy. The results indicate that the patterns of title formats exist across different domains, and it is possible to construct a domain independent model by mainly using formatting information. 6.7 Language Adaptation We apply the model trained with the data in English (MS) to the data set in Chinese. Tables 13-14 show the results. Table 13. Accuracies of title extraction with Word in Chinese Precision Recall F1 Model Perceptron 0.817 0.805 0.811 Largest font size 0.722 0.755 0.738Baselines First line 0.743 0.777 0.760 Table 14. Accuracies of title extraction with PowerPoint in Chinese Precision Recall F1 Model Perceptron 0.766 0.812 0.789 Largest font size 0.753 0.813 0.782Baselines First line 0.627 0.676 0.650 We see that the models can be adapted to a different language. There are only small drops in accuracy. Obviously, the linguistic features do not work for Chinese, but the effect of not using them is negligible. The results indicate that the patterns of title formats exist across different languages. From the domain adaptation and language adaptation results, we conclude that the use of formatting information is the key to a successful extraction from general documents. 6.8 Search with Extracted Titles We performed experiments on using title extraction for document retrieval. As a baseline, we employed BM25 without using extracted titles. The ranking mechanism was as described in Section 5. The weights were heuristically set. We did not conduct optimization on the weights. The evaluation was conducted on a corpus of 1.3 M documents crawled from the intranet of Microsoft using 100 evaluation queries obtained from this intranet"s search engine query logs. 50 queries were from the most popular set, while 50 queries other were chosen randomly. Users were asked to provide judgments of the degree of document relevance from a scale of 1to 5 (1 meaning detrimental, 2 - bad, 3 - fair, 4 - good and 5 - excellent). 152 Figure 10 shows the results. In the chart two sets of precision results were obtained by either considering good or excellent documents as relevant (left 3 bars with relevance threshold 0.5), or by considering only excellent documents as relevant (right 3 bars with relevance threshold 1.0) 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 P@10 P@5 Reciprocal P@10 P@5 Reciprocal 0.5 1 BM25 Anchor, Title, Body BM25 Anchor, Title, Body, ExtractedTitle Name All RelevanceThreshold Data Description Figure 10. Search ranking results. Figure 10 shows different document retrieval results with different ranking functions in terms of precision @10, precision @5 and reciprocal rank: • Blue bar - BM25 including the fields body, title (file property), and anchor text. • Purple bar - BM25 including the fields body, title (file property), anchor text, and extracted title. With the additional field of extracted title included in BM25 the precision @10 increased from 0.132 to 0.145, or by ~10%. Thus, it is safe to say that the use of extracted title can indeed improve the precision of document retrieval. 7. CONCLUSION In this paper, we have investigated the problem of automatically extracting titles from general documents. We have tried using a machine learning approach to address the problem. Previous work showed that the machine learning approach can work well for metadata extraction from research papers. In this paper, we showed that the approach can work for extraction from general documents as well. Our experimental results indicated that the machine learning approach can work significantly better than the baselines in title extraction from Office documents. Previous work on metadata extraction mainly used linguistic features in documents, while we mainly used formatting information. It appeared that using formatting information is a key for successfully conducting title extraction from general documents. We tried different machine learning models including Perceptron, Maximum Entropy, Maximum Entropy Markov Model, and Voted Perceptron. We found that the performance of the Perceptorn models was the best. We applied models constructed in one domain to another domain and applied models trained in one language to another language. We found that the accuracies did not drop substantially across different domains and across different languages, indicating that the models were generic. We also attempted to use the extracted titles in document retrieval. We observed a significant improvement in document ranking performance for search when using extracted title information. All the above investigations were not conducted in previous work, and through our investigations we verified the generality and the significance of the title extraction approach. 8. ACKNOWLEDGEMENTS We thank Chunyu Wei and Bojuan Zhao for their work on data annotation. We acknowledge Jinzhu Li for his assistance in conducting the experiments. We thank Ming Zhou, John Chen, Jun Xu, and the anonymous reviewers of JCDL"05 for their valuable comments on this paper. 9. REFERENCES [1] Berger, A. L., Della Pietra, S. A., and Della Pietra, V. J. A maximum entropy approach to natural language processing. Computational Linguistics, 22:39-71, 1996. [2] Collins, M. Discriminative training methods for hidden markov models: theory and experiments with perceptron algorithms. In Proceedings of Conference on Empirical Methods in Natural Language Processing, 1-8, 2002. [3] Cortes, C. and Vapnik, V. Support-vector networks. Machine Learning, 20:273-297, 1995. [4] Chieu, H. L. and Ng, H. T. A maximum entropy approach to information extraction from semi-structured and free text. In Proceedings of the Eighteenth National Conference on Artificial Intelligence, 768-791, 2002. [5] Evans, D. K., Klavans, J. L., and McKeown, K. R. Columbia newsblaster: multilingual news summarization on the Web. In Proceedings of Human Language Technology conference / North American chapter of the Association for Computational Linguistics annual meeting, 1-4, 2004. [6] Ghahramani, Z. and Jordan, M. I. Factorial hidden markov models. Machine Learning, 29:245-273, 1997. [7] Gheel, J. and Anderson, T. Data and metadata for finding and reminding, In Proceedings of the 1999 International Conference on Information Visualization, 446-451,1999. [8] Giles, C. L., Petinot, Y., Teregowda P. B., Han, H., Lawrence, S., Rangaswamy, A., and Pal, N. eBizSearch: a niche search engine for e-Business. In Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 413414, 2003. [9] Giuffrida, G., Shek, E. C., and Yang, J. Knowledge-based metadata extraction from PostScript files. In Proceedings of the Fifth ACM Conference on Digital Libraries, 77-84, 2000. [10] Han, H., Giles, C. L., Manavoglu, E., Zha, H., Zhang, Z., and Fox, E. A. Automatic document metadata extraction using support vector machines. In Proceedings of the Third ACM/IEEE-CS Joint Conference on Digital Libraries, 37-48, 2003. [11] Kobayashi, M., and Takeda, K. Information retrieval on the Web. ACM Computing Surveys, 32:144-173, 2000. [12] Lafferty, J., McCallum, A., and Pereira, F. Conditional random fields: probabilistic models for segmenting and 153 labeling sequence data. In Proceedings of the Eighteenth International Conference on Machine Learning, 282-289, 2001. [13] Li, Y., Zaragoza, H., Herbrich, R., Shawe-Taylor J., and Kandola, J. S. The perceptron algorithm with uneven margins. In Proceedings of the Nineteenth International Conference on Machine Learning, 379-386, 2002. [14] Liddy, E. D., Sutton, S., Allen, E., Harwell, S., Corieri, S., Yilmazel, O., Ozgencil, N. E., Diekema, A., McCracken, N., and Silverstein, J. Automatic Metadata generation & evaluation. In Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 401-402, 2002. [15] Littlefield, A. Effective enterprise information retrieval across new content formats. In Proceedings of the Seventh Search Engine Conference, http://www.infonortics.com/searchengines/sh02/02prog.html, 2002. [16] Mao, S., Kim, J. W., and Thoma, G. R. A dynamic feature generation system for automated metadata extraction in preservation of digital materials. In Proceedings of the First International Workshop on Document Image Analysis for Libraries, 225-232, 2004. [17] McCallum, A., Freitag, D., and Pereira, F. Maximum entropy markov models for information extraction and segmentation. In Proceedings of the Seventeenth International Conference on Machine Learning, 591-598, 2000. [18] Murphy, L. D. Digital document metadata in organizations: roles, analytical approaches, and future research directions. In Proceedings of the Thirty-First Annual Hawaii International Conference on System Sciences, 267-276, 1998. [19] Pinto, D., McCallum, A., Wei, X., and Croft, W. B. Table extraction using conditional random fields. In Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 235242, 2003. [20] Ratnaparkhi, A. Unsupervised statistical models for prepositional phrase attachment. In Proceedings of the Seventeenth International Conference on Computational Linguistics. 1079-1085, 1998. [21] Robertson, S., Zaragoza, H., and Taylor, M. Simple BM25 extension to multiple weighted fields, In Proceedings of ACM Thirteenth Conference on Information and Knowledge Management, 42-49, 2004. [22] Yi, J. and Sundaresan, N. Metadata based Web mining for relevance, In Proceedings of the 2000 International Symposium on Database Engineering & Applications, 113121, 2000. [23] Yilmazel, O., Finneran, C. M., and Liddy, E. D. MetaExtract: An NLP system to automatically assign metadata. In Proceedings of the 2004 Joint ACM/IEEE Conference on Digital Libraries, 241-242, 2004. [24] Zhang, J. and Dimitroff, A. Internet search engines' response to metadata Dublin Core implementation. Journal of Information Science, 30:310-320, 2004. [25] Zhang, L., Pan, Y., and Zhang, T. Recognising and using named entities: focused named entity recognition using machine learning. In Proceedings of the 27th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 281-288, 2004. [26] http://dublincore.org/groups/corporate/Seattle/ 154
title extraction formatting information generality of model classifier document retrieval information extraction search
language independence metada of document linguistic feature comparison between model model generality usefulness of extracted title extracted title usefulness genre automatic title extraction metada extraction machine learn