Multimedia Multimedia information information extraction extraction from from HTML HTML product catalogues product catalogues Martin Labský1 , Pavel Praks2, Vojtěch Svátek1 , Ondřej Šváb1 Martin Labský1 , Pavel Praks2 , Vojtěch Svátek1 , and Ondřej Šváb1 1 Department of Information and Knowledge Engineering, 1 University of Economics, Department Prague, of Information andW. ChurchillEngineering, Knowledge Sq. 4, 130 67University Praha 3, Czech Republic of Economics, {labsky,svatek,xsvao06}@vse.cz Prague, W. Churchill Sq. 4, 130 67 Praha 3, Czech Republic 2 Department of Mathematics and Descriptive Geometry, {labsky,svatek,xsvao06}@vse.cz 2 Department Department of Applied of Applied Mathematics, Mathematics, Technical VŠB University – Technical of Ostrava, University of Ostrava 17. listopadu 15, 708 33 Ostrava-Poruba, Czech Republic pavel.praks@vsb.cz pavel.praks@vsb.cz Abstract. We describe a demo application of information extraction from company websites, focusing on bicycle product offers. A statistical approach (Hidden Markov Models) is used in combination with different ways of image classification, including latent semantic analysis of image collections. Ontological knowledge is used to group the extracted items into structured objects. The results are stored in an RDF repository and made available for structured search. 1 Introduction Tools and techniques for web information extraction (WIE) have recently been recognised as one of key enablers for semantic web (SW) scaling. In our long-term project named Rainbow 3 we address several intertwined topics that we consider important for efficient ‘WIE for SW’ applications: 1. Exploitation of multiple information modalities available in web documents 2. Synergy of learning and reuse of ontological information 3. Automated acquisition and labelling of training data for extractor learning 4. Bridging between automated acquisition of SW data and their usage 5. Support for easy design of WIE applications from components. In this paper, we focus on an ongoing demo application in the domain of bicycle product offers. Section 2 presents the core method: automated HTML annotation based on Hidden Markov Models. Section 3 extends the analysis of HTML code with that of images. Section 4 describes the composition of product offer instances with the help of a simple ontology. Section 5 outlines the archi- tecture of the demo application and the subsequent usage of extracted data in an RDF repository. Finally, section 6 focuses on future work. 3 http://rainbow.vse.cz K. Richta, V. Snášel, J. Pokorný (Eds.): Dateso 2005, pp. 84–93, ISBN 80-01-03204-3. Multimedia information extraction from HTML product catalogues 85 Fig. 1. Hand-annotated training data 2 Web Page Annotation Using HMMs For extracting product entries from web catalogues, we built a Hidden Markov Model (HMM) tagger, which assigns a semantic tag to each token from a docu- ment. Tokens are either words, formatting tags or images. In our experiments, we evaluated the HMM performance on a diverse set of web pages, which come from different web sites and have heterogenous formattings. We manually annotated a set of 100 HTML documents chosen from the Google Directory Sports-Cycling-BikeShops-Europe-UK-England. Each document contains from 1 to 50 bicycle offers, and each offer consists of at least the bicycle name and price. There are typically 3–4 documents from the same shop in the data. Annotations for 15 bicycle characteristics were made using SGML tags4 . A sample annotated data is shown in Figure 1. To represent web documents, we employed extensive pre-processing. Similarly to [7], we transform each document into XHTML and perform canonicalisation of XML entities5 . Certain HTML tags and tag groups are replaced by their generalisations6. Since only words and images can be extracted, we dispose of mark-up blocks that do not directly contain words or images. HMMs are probabilistic finite state machines, which represent text as a se- quence of tokens. An HMM consists of states which generate tokens, and of 4 The training data and a demo are available at http://rainbow.vse.cz. 5 This step unifies different ways of writing the same characters in XML. 6 Most tags are only represented using their names, disregarding any attributes. Often- occuring design patterns, such as add-to-basket buttons, are identified using several manually authored rules, and replaced by dedicated tokens. 86 Martin Labský, Pavel Praks, Vojtěch Svátek, Ondřej Šváb Fig. 2. HMM architecture transitions between these states. States are associated with token generation probabilities, and transitions with transition probabilities. Both kinds of these probababilities are estimated from training data. For the purposes of information extraction, states are typically associated with semantic tags to be extracted. To annotate a document using a trained HMM, that document is assumed to have been generated by that HMM. The most probable state sequence is then found using the Viterbi algorithm [12]. The structure of our HMM is inspired by [6] and is sketched in Figure 2. Extracted slots are modelled using target states (denoted as T). Each target state is accompanied by two types of helper states responsible for representing the slot’s characteristic context – the prefix and suffix states (P and S). Irrelevant tokens are modelled by a single background state (B). Contrary to [6] and [17], which use independent HMMs trained for each slot separately, we train a single composite HMM capable of extracting all slots at once. Our model thus contains multiple target, prefix and suffix states. This approach, also used in [1], captures the ordering relations between nearby slots (e.g. product image often follows its name). We experimented also with other HMM architectures, with results presented in [16]. 3 Impact of Image Classification For the purpose of extracting product images, we examined the impact of image information available to the HMM tagger. As a baseline approach, we measured the tagging performance when no image information was available for tagging. In this case, all images were represented by the same token and product pictures could only be distinguished based on the context in which they appeared. In order to provide our tagger with more information, we built image clas- sifiers to determine whether the extracted product is depicted in a particular image. We used the following features for classification: image dimensions, simi- larity to training product images, and whether there is more than one occurrence of the same image in the containing document. Multimedia information extraction from HTML product catalogues 87 3.1 Image dimensions For our domain, we modelled images of bicycles using a 2-dimensional normal distribution, only estimated from positive training examples7 . The dimensions x, y of a new image I are first evaluated using the estimated normal density N . The density value is then normalized to the interval (0,1) using the density’s maximum value Nmax . N (x, y) Dim(I) := (1) Nmax An image I is then classified as P os or N eg by comparing its Dim(I) score to a threshold TDim . This threshold was estimated by minimizing the classification error rate on a separate heldout set of 150 images.  P os if (Dim(I) ≥ T Dim ), class(I) = (2) N eg otherwise. Within our document collection, image dimensions appeared to be the best single predictor with the error rate of 6.6%. However, this is mainly due to our collec- tion being limited to relevant product catalogues only. When dealing with more heterogeneous data, features describing the actual image content will become necessary. 3.2 Image similarity We experimented with a latent semantic approach to measuring image similarity, described in [10] and [11]. This kind of image similarity has been applied to image retrieval from collections, where the task often is to find the most similar image to a query. We used this image-to-image similarity measure sim(I, J) to compute simC (I), the similarity of an image I to a collection of images C. In our experiments, C contained the training bicycle pictures (positive examples only). To compute simC (I), we used the K nearest neighbor approach and averaged the similarities of the K most similar images from the collection.  K best images J∈C sim(I, J) simC (I) = (3) K Experimentaly, we set K = 20, since lower values of K lead to a decrease in the similarity’s robustness8 and higher values did not bring further improvement. To build a classifier, a similarity threshold TSim was estimated on a heldout set in the same way as for the dimension classifier above. The error rate of the classifier was 26.7% on our document collection. 7 The positive examples comprise of all bicycle pictures found in the documents, not only those labeled as parts of bicycle offers. For information extraction, this increases the role of image context for correct tagging. 8 With low values of K, simC (I) became too sensitive to individual images J with misleading values of sim(I, J). 88 Martin Labský, Pavel Praks, Vojtěch Svátek, Ondřej Šváb 3.3 Combined classifier For the combined image classifier, we used the above described dimension score Dim(I), similarity score Sim(I) and a binary feature indicating whether the image occurs more than once in the document. We experimented with different classifiers available in the Weka9 environment, and the best error rate10 of 4.8% was achieved by the multilayer perceptron algorithm. Results for all three classifiers are compared in Table 1. All results were mea- sured using 10-fold cross-validation on a set of 1, 507 occurences of 999 unique images taken from our training documents. The first two algorithms used ad- ditional 150 heldout images to estimate their decision thresholds. The cross- validation splitting was done at the level of documents, so that all images from a single document were either used for training or for testing. Table 1. Image classification results Dimension Similarity Combined Error rate (%) 6.6 26.7 4.8 3.4 Using Image Information for Extraction To improve extraction results, we need to communicate the image classifier’s results to the HMM tagger. Currently we do this simply by substituting each image occurence in a document by its class. Since these binary decisions would leave little room for the HMM tagger to fix incorrect classifications, we adapted the above binary classifiers to classify into 3 classes: P os, N eg, and U nk. In this way, the HMM tagger learns to classify the P os and N eg classes correspondingly, and the tagging of the U nk class depends more strongly on the context. To build the ternary versions of the dimension- and similarity-based classi- fiers, we introduced costs for the classifier’s decisions. Each wrong decision was penalized by CMiss = 1 and the cost of each U nk decision was CUnk ∈ (0, 1). We set CUnk manually such that the classifier produced 5-10% of U nk decisions on the heldout set. While minimizing the sum of these costs on the heldout set, two thresholds were estimated for both the dimension- and similarity-based classifiers, delimiting their N eg, U nk and P os decisions. For the combined ternary classifier, we achieved the best results with a de- cision list shown in Table 2. The list combines image occurence count with the results of the dimension- and similarity-based ternary classifiers, denoted as class3Dim and class3Sim respectively. We evaluated information extraction results with all three ternary classifiers and compared the results to the case where no image information was available. 9 http://www.cs.waikato.ac.nz/~ml 10 This error rate comes from 10-fold cross-validation without using heldout data. Multimedia information extraction from HTML product catalogues 89 Table 2. Decision list for the combined ternary classifier Order Rule 1 class(I) = N eg if(occurences(I) > 1) 2 class(I) = P os if(class3Dim (I) = P os) 3 class(I) = U nk if(class3Dim (I) = U nk) 4 class(I) = U nk if(class3Sim (I) = P os) 5 class(I) = N eg The new image information from the combined classifier lead to an increase of 19.1% points in picture precision and also to subtle improvements for other tags. Improvements in precision and recall for 3 chosen slots (product pictures, names and prices), measured on a per-token basis, are shown in Table 3 for all three classifiers. Table 3. 10-fold cross-validation results for selected tags over 100 documents Tag Precision Recall F-measure Precision Recall F-measure No image information Image similarity Picture 67.8 87.1 76.2 78.5 87.3 82.7 Name 83.7 82.5 83.1 83.9 82.5 83.2 Price 83.7 94.4 88.8 84.0 94.4 88.9 Image Dimensions Combined Picture 85.6 88.4 87.0 86.9 89.1 88.0 Name 83.8 82.5 83.1 83.8 82.5 83.2 Price 84.0 94.4 88.9 84.0 94.4 88.9 4 Ontology-Based Instance Composition Semantic web is not about isolated tagged items but about complex and in- terrelated entities; we thus need to group the labels produced by automated annotation into instances. We currently use a simple sequential algorithm that exploits constraints defined in a tiny presentation ontology 11 [9], which partly pertain to the generic domain (bike offers) and partly to the way of presenting information in web catalogues. Figure 3 shows an experimental presentation on- tology containing the class ’Bike offer’. The utilized constraints are uniqueness, multiplicity and optionality of certain properties, the latter two indicated with the * and ? symbols, respectively12 . In addition, ‘sticky’ properties (indicated with !) are distinguished: as soon as the value of sticky property is discovered 11 Similar to ‘extraction ontologies’ used by Embley [5]. 12 Although not shown in the example, we can also use e.g. property value types or regular expressions. 90 Martin Labský, Pavel Praks, Vojtěch Svátek, Ondřej Šváb Fig. 3. Bicycle offer presentation ontology on a page, it is filled to all objects extracted afterwards, until a new value is discovered for this property. An annotated item is added to the currently assembled (bike offer) instance unless it would cause inconsistency; otherwise, the current instance is saved and a new instance created to accommodate this item and the following ones. De- spite acceptable performance on error-free, hand-annotated training data, where the algorithm correctly groups about 90% of names and prices, this ‘baseline’ approach achieves very poor results on automatically annotated data: on aver- age, less than 50% of corresponding annotations are grouped properly, often for trivial reasons. The most critical problems are connected with missing or extra annotations, multiple different references to a single slot, and with transposed HTML tables. 5 Result Transformation, Storage And Retrieval All components developed within the Rainbow project are wrapped as web ser- vices. The WIE component itself is currently being called by a simple control routine (written in Java), which also optionally calls other analysis tools: in the bicycle application, we so far experimented with URL-based navigation over the website, extraction of the content of selected META tags, and extraction of ‘company profile sentences’ from free text13 . The results are transformed to RDF (with respect to a ‘bicycle-offer RDFS ontology’) and stored in a Sesame [2] repository. An end-user search interface to this repository14 is shown in Fig. 4. It relies on a collection of query templates expressed in SeRQL (the native query language of Sesame) and enables a simple form of navigational retrieval [16]. 13 These three approaches to website analysis, implemented independent of the bicycle demo application, are evaluated in [13]. 14 Available at http://rainbow.vse.cz:8000/sesame. Multimedia information extraction from HTML product catalogues 91 Fig. 4. End-user search interface 6 Future Work Most urgently, we need to replace the ‘toy’ implementation of ontology-based instance composition with a version reasonably robust on automatically anno- tated data. For some of the layout-oriented problems mentioned in section 4, partial solutions recently suggested in IE research (e.g. [3, 5]) could be reused. We also consider introducing HMMs even to this phase of extraction; a modified version of Viterbi algorithm supporting domain constraints (such as those in our presentation ontology) has already been described in [1]. Another aspect worth investigation is the possibility of (semi-)automatic construction of presentation ontologies from the corresponding domain ontologies. A critical bottleneck of ML-based IE methods (in particular of statistical ones) is the volume of labelled training data required. In our experiments with product catalogues, we noticed that the tagger often classifies most product en- tries correctly but misses a few product names that are very different from the training data. We developed a simple symbolic algorithm that identifies similar structural patterns in a document. For example, the HTML tag sequence
with arbitrary words in between ap- pears 34 times in one of our training documents: the tagger successfully anno- tated 28 product names contained in these patterns between and
, but missed the remaining 6. In such cases, we could collect the remaining prod- uct names and use them to enrich the model’s training data. By learning novel product names from these ‘easy’ pages, the model will learn to also recognise 92 Martin Labský, Pavel Praks, Vojtěch Svátek, Ondřej Šváb them in less structured documents15 . We also plan to bootstrap the method with data picked from public resources related to product offering, following up with our earlier experiments with Open Directory headings and references [8]. Another important task is to replace hard-coded control routines with semi- automatically constructed, implementation-independent application models. A knowledge modelling framework has already been introduced for this purpose [14]; currently we examine the adaptability of a PSM-based semantic web-service configuration technique in connection with this framework [15]. Eventually, we plan to associate our efforts with the popular Armadillo project [3], with which we share most of our abovementioned research interests. The research is partially supported by grant no.201/03/1318 of the Grant Agency of the Czech Republic, “Intelligent analysis of the WWW content and structure”. References 1. Borkar V., Deshmukh K., Sarawagi S.: Automatic segmentation of text into struc- tured records. In: SIGMOD Conference, 2001. 2. Broekstra J., Kampman A., van Harmelen F.: Sesame: An Architecture for Storing and Querying RDF and RDF Schema. In: Proc. ISWC 2002, Springer LNCS no. 2342. 3. Ciravegna, F., Chapman, S., Dingli, A., Wilks, Y.: Learning to Harvest Information for the Semantic Web. In: ESWS-04, Heraklion, Springer LNCS 2004. 4. Dingli A., Ciravegna F., Guthrie D., Wilks Y.: Mining Web Sites Using Unsupervised Adaptive Information Extraction. In: EACL, 2003. 5. Embley, D.W., Tao, C., Liddle, S.W.: Automatically extracting ontologically speci- fied data from HTML tables with unknown structure. In: ER2002, Tampere 2002, 322-337. 6. Freitag D., McCallum A.: Information extraction with HMMs and shrinkage. In: Proceedings of the AAAI-99 Workshop on Machine Learning for IE, 1999. 7. Grover C., McDonald S., Gearailt D., Karkaletsisy V., Farmakiotouy D., Samaritak- isy G., Petasis G., Pazienza M., Vindigni M., Vichotz F., Wolinskiz F.: Multilingual XML-Based Named Entity Recognition for E-Retail Domains. In: LREC Confer- ence, Las Palmas, 2002. 8. Kavalec, M., Svátek, V.: Information Extraction and Ontology Learning Guided by Web Directory. In: ECAI Workshop on NLP and ML for ontology engineering. Lyon 2002. 9. Labský, M., Svátek, V., Šváb, O.: Types and Roles of Ontologies in Web Information Extraction. In: ECML/PKDD04 Workshop on Knowledge Discovery and Ontologies, Pisa 2004. 10. Praks P., Dvorský J., Snášel V.: Latent semantic indexing for image retrieval sys- tems. In: Proceedings of the SIAM Conference on Applied Linear Algebra (LA03), Williamsburg, USA, The College of William and Mary, 2003. 11. Praks P., Machala L., Snášel V.: Iris Recognition Using the SVD-Free Latent Se- mantic Indexing. In: MDM/KDD 2004 - Fifth International Workshop on Multime- dia Data Mining, Seattle, USA, 2004. 15 Similar bootstrapping strategies are shown in [4]. Multimedia information extraction from HTML product catalogues 93 12. Rabiner, L.R.: A tutorial on hidden Markov models and selected applications in speech recognition. In: Proceedings of the IEEE, 77(2), 1989. 13. Svátek V., Berka, P., Kavalec, M., Kosek, J., Vávra, V.: Discovering Company De- scriptions on the Web by Multiway Analysis. In: Intelligent Information Processing and Web Mining, IIPWM’03., Springer Verlag, 2003. 14. Svátek, V., Labský, M., Vacura, M.: Knowledge Modelling for Deductive Web Mining. In: Proc. EKAW 2004, Springer Verlag, LNCS, 2004. 15. Svátek, V., ten Teije, A., Vacura, M.: Web Service Composition for Deductive Web Mining: A Knowledge Modelling Approach. In: Proc. Znalosti 2005, VSB-TU Ostrava, to appear 2005. 16. Šváb, O., Labský, M., Svátek, V.: RDF-Based Retrieval of Information Extracted from Web Product Catalogues. In: SIGIR’04 Semantic Web Workshop, Sheffield. 17. Valarakos A., Sigletos G., Karkaletsis V., Paliouras G.: A Methodology for Seman- tically Annotating a Corpus Using a Domain Ontology and Machine Learning. In: RANLP Conference, Borovets, 2003.