Table Recognition Using Attribute Likelihood
Computed from Words
Tsubasa Kitayama, Kazutaka Shimada and Tsutomu Endo
Department of Arti cial Intelligence,
Kyushu Institute of Technology,
Iizuka, Fukuoka 820-8502 Japanft kitayama, shimada, endog@pluto.ai.kyutech.ac.jp

Abstract. Tables are an ecient way to express relational information. Understanding tables is

an important task for various applications. In this paper, we describe a method of recognition oftable structures. Here the table structures are the relations of attributes and values in a table.
For this process, we employ attribute likelihood which is computed from words in tables. First
we compute weights of words from training data. Next our method identi es an attribute row (orcolumn) using the weights. Experimental results show the e ectiveness of our method.
1 Introduction

As the World Wide Web rapidly grows, a huge number of online documents are easily accessible on
the Web. Finding information relevant to user needs has become increasingly important. Information on
the WWW is in the form of not only text but also images and tables. Although tables are structuredinformation, i.e., attribute-value pairs, most of conventional information retrieval systems treat tables astext. Since tables are an ecient way to express relational information, table extraction is a signi canttask for web mining, QA systems, summarization and so on [2, 3, 4, 7].
In general, tables on the WWW are written in a <TABLE> tag. However, the presence of the<TABLE> tag in an HTML document does not necessarily indicate the presence of tables. Less than30% of HTML <TABLE> tags are real tables in one particular domain [1]. There are several approaches
to treat HTML-based tables. Although Chen et al. have reported a method for extracting tables fromHTML documents, they employed heuristic rules for table extraction [1]. Constructing rules by handwork
is costly. Wang et al. have evaluated a table extraction task with machine learning based approaches:
decision tree learning and SVMs [10]. We have reported a method for table extraction based on Bayes'
rule [8] and Transductive SVMs [9].
The purpose of most of the previous work is to detect real tables in HTML documents. For thedevelopment of systems handling tables appropriately we need to identify relations in tables. In this paper
we de ne the relation as attribute-value pairs. Masuda et al. have reported a table structure recognition
method based on content features and layout features [5]. For example, one of the content features is unit
features such as \feet" and \inch". The appropriate selection of these features by handwork is costly.
Yoshida et al. have proposed a method for table structure recognition using an unsupervised methodthat was achieved by utilizing the EM algorithm [11]. However, their method can not recognize all typesof the location of attributes and values because the number of table structures they de ned was only 9.
In this paper, we propose a method of recognition of table structures. For this method, we employ
attribute likelihood which is computed from words in tables. First we compute weights of words fromtraining data. The weight denotes the polarization of a word: a word is an attribute or a value. Next ourmethod identi es an attribute row (or column) using the weights. This method classi es <TABLE> tags
into real tables and <TABLE> tags used for layout and also can recognize all kinds of table structures.
2 Table Recognition

In this paper, real tables denote that <TABLE> tags consist of attributes and values. Figure 1 shows
an example of a real table. In Figure 1, the 1st column is the attribute area and the 2nd column is thevalue area.
2.1

Weight of words

We use the weights of words appearing in tables for table structure recognition. The weights are computedfrom training data. The weight denotes the polarization of a word. If the weight of a word is large, theFig. 1. An example of a real table.
word appears frequently in attribute rows and columns. For this process, we need a corpus containing
tagged cells (\attribute" or \value").
The algorithm consists of the following steps:
1. Extract word strings in table cells from training data.
2. Divide the word strings into words. In order to obtain the words, we use the Japanese morphologicalanalyzer ChaSen1 .
3. For each word, the weight is computed as follows:
Pword (w) =w
freqattrwfreqtable(1)

w is the frequency of a word w in attribute rows or columns. freq w is the frequency
where freqattr
tableof the word w in training data.
Pword (w) is a probability that the word w occurs in attribute rows or columns.
2.2

Attribute likelihood

We estimate attribute likelihood of each row and column by using the word weights computed by Eq.
(1). First we compute the weight of each cell and then the weight of all cells. Finally we compute thein uence of each row and column. If the attribute likelihood computed from the in uence is more thanor equal to a threshold, the <TABLE> tag is a real table and the row or column is an attribute. If not,our method judges that the <TABLE> tag is used for layout.
The algorithm consists of the following steps:a) Compute the weight of each cell. It is computed as follows:
Pw2x Pword(w)Pcell (x) =(2)Nxwhere x and Nx is a cell and the number of words in the cell x respectively. If a cell does not containany words extracted in Section 2.1, the weight of the cell (Pcell (x)) is 0.
b) Compute the weight of a table as follows:
Px2t Pcell(x)Ptable (t) =(3)Ntwhere t and Nt is a <TABLE> tag and the number of cells in the <TABLE> tag t respectively.
c) Compute the in uence of each row and column. We compute two values as follows:
Px2t;x=2i Pcell(x)Px2t;x=2j Pcell(x)Prow (i) =; Pcol (j ) =(4)
jNit

Nt

where i and j are a row and a column respectively. Nti and Ntj are the total number of cells fromwhich the row i and the column j were removed. If i (or j ) is an attribute in t, Prow (i) (or Pcol (j ))is small value.
d) Detect the minimum value Pmin from all Prow and Pcol . Finally we compute the maximum value of
attribute likelihood.
Pmax = Ptable 0 Pmin
(5)
If Pmax > T h , the row or the column is an attribute of the table t. T h is a threshold value.
Figure 2 shows an example of the process. The values in the cells in Fig. 2 denote the values of Pcell (x).
1
http://chasen.naist.jp/hiki/ChaSen/

0.80.9
0.85

0.6
0.2
0.5

0.7
0.3
0.5

Ptable (t) = 0.594

Compute the influence of each row and column

0.8
0.6
0.7
0.9
0.2
0.3
Attribute
0.85
0.5
0.5
Pcol( j 1) = 0.467

0.8
0.6
0.7
0.9 Attribute
0.2
0.3
0.85
0.5
0.5
Pcol( j 2) = 0.675

Pmin = 0.467

0.8
0.6
0.7
0.9
0.2
0.3
0.85 Attribute
0.5
0.5
Prow( i3 ) = 0.583

Pmax = 0.127

Fig. 2. An example of the process.
3 Experiment
3.1

DatasetWe evaluated the appropriateness for the proposed method with a dataset. The data was extracted
from several manufacturer's sites by a le-downloading software. The total number of pages is 10935.
We extracted 3229 <TABLE> tags from the pages. These <TABLE> tags did not contain nested tables,<A> tags, <IMG> tags, COLSPAN and ROWSPAN attributes2 . The tables in the data contained 2 ormore rows and columns at least. The dataset for this evaluation was constructed by 1000 <TABLE> tags
extracted from the <TABLE> tags randomly. The dataset contains real tables and <TABLE> tags forlayout. We evaluated our method with 5-fold cross validation.
Our method needs a threshold T h in the detection process of the maximum value of attribute likelihood. We compared several threshold by handwork with a threshold calculated from training data
automatically. The threshold by mechanical work was computed as follows:# of words that belong to attributes in training data
Th =(6)# of words in training data
3.2

Experimental results

Table 1 shows the experimental result. The \simple method" in Table 1 was a simpli ed method. Thismethod used the weights computed in the process a) in the Section 2.2. Next the method computed thefollowing scores of each row and column.
P Pcell(x)P Pcell(x)
x2jx
2i(7)
Srow (i) =# of cells in a row i ; Scol(j ) = # of cells in a column j
Finally the method computed Pmax = max(Srow ; Scol ).
The accuracy of the proposed method outperformed the simple method and the related work. The
best accuracy was 84.5 % in the case that the T h = 0:07. The threshold by handwork outperformed thatcomputed from the training data automatically. However, the best threshold was close to the mechanicalthreshold. Hence the value computed from training data is useful to determine the best threshold byhandwork.
One of the reasons that the accuracy of related work was low is the problem of the features theyemployed. The accuracy of their method depends on the features that they decided by hand. Theirfeatures were not suitable for our dataset. Moreover their method is not appropriate to recognize small
tables, especially 2 2 2 tables. These results show the e ectiveness of our method.
2The <A> tag is the anchor tag for hypertext documents. The <IMG> tag is used to insert images within text.
The ROWSPAN and COLSPAN attributes indicate how many rows or columns this cell overlaps.

Table 1. The result of the experimentby handworkfrom training data simple method Related work [5]0.04 0.05 0.06 0.07 0.08 0.09 0.1
0.07860.15
Accuracy 67.2 76.9 82 84.5 82.5 81.7 80.7
82.6
78.4
56.6
Th

One of the problems of our method is the number of training data. For constructing a strong table
recognizer, our method requires a large amount of training data. However, gathering the training databy handwork is costly. To solve this problem, Yoshida et al. employed EM algorithm [11]. Ohmae et al.
have reported a method of automated extraction of attribute words in tables [6]. The method is basedon a supposition that attribute words frequently appear in the 1st column and row of the tables. With
regard to their experiment, they obtained 77.4 points in F-measure without training data. We evaluatedthis method with our experimental dataset. However, the accuracy of the table recognition was very low(less than 30%). The reason for the low accuracy in our dataset was that they treated only data thatwas retrieved with some queries in their experiment. In other words, their method is an e ective solution
for domain-speci c data. This result shows that we need to consider some modi cations for applying theapproach to our method.
4 Conclusion

In this paper, we proposed a method of recognition of table structures. For this process, we used attributelikelihood which is computed from words in tables. This method classi ed <TABLE> tags into real tables
and <TABLE> tags used for layout and also recognized table structures, i.e., attribute-value pairs. The
experimental results show the e ectiveness of the proposed method.
Our future work includes (1) the expansion of our method for tables that contain 2 or more attributerows or columns and (2) the reduction of training data with machine learning methods and heuristic
models of tables.
References

1. H. H. Chen, S. C. Tsai and J. H. Tsai: Mining tables from large scale HTML texts, Proc. of COLING2000,
pp. 166-172, 2000.
2. Gen Hattori, Kazunori Matsumoto, Fumiaki Sugaya, \Understandable and Discriminative Object Label Extraction Scheme for Summarizing Table-Type Information", Transactions of IEICE, D-I, Vol. J88-D-I, No. 9,
pp. 1467-1476, 2005 (in Japanese).
3. Matthew Hurst, \Layout and language: Challenges for table understanding on the web", Proceedings ofWorkshop on Web Document Analysis, WDA01, pp. 27-30, 2001.
4. Kumi Itai, Atsuhiro Takasu and Jun Adachi, Information extraction from HTML pages and its integration,
Proceedings of the 2003 Symposium on Application and the Internet Workshops (SAINT03), pp. 276-281,2003.
5. Hidetaka Masuda, Shuichi Tsukamoto and Hiroshi Nakagawa, \Recognition of HTML Table Structure", TheFirst International Joint Conference on Natural Language Processing (IJCNLP-04), pp.183-188, 2004.
6. Nobuhiro Ohmae and Koichi Kise, \Automatic recognition of attributes from tables in web pages", Technical
Report of IPSJ, NL-171, pp. 43-48, 2006 (in Japanese).
7. Kazutaka Shimada, Atsushi Fukumoto and Tsutomu Endo, Information extraction from personal computer
speci cations on the Web using a user's request, IEICE Transactions on Information and Systems, E86-D,
No. 8, pp. 1386-1395, 2003.
8. Kazutaka Shimada, Koji Hayashi and Tsutomu Endo, \Keyword and Weighting for Product Speci cations
Extraction", Proceedings of PACLING 2003, pp. 285-293, 2003.
9. Kazutaka Shimada, Koji Hayashi and Tsutomu Endo, \Product Speci cation Extraction Using SVM andTransductive SVM", Journal of Natural Language Processing, Vol.12, No.3, pp. 43-66, 2005 (in Japanese).
10. Yalin Wang, Jianying Hu, \A Machine Learning Based Approach for Table Detection on The Web", The
Eleventh International World Wide Web Conference, 2002.
11. Minoru Yoshida, Kentaro Torisawa, Jun'ichi Tsujii, \Integrating Tables on the World Wide Web", Transactions of the Japanese Society for Arti cial Intelligence, 19(6). pp. 548-560, 2004.