Acquisition of new training data from unlabeled data for
product speci cation extraction
Kazutaka Shimada and Tsutomu Endo
Department of Arti cial Intelligence
Kyushu Institute of Technology 680-4 Iizuka Fukuoka 820-8502 Japanfshimada, endog@pluto.ai.kyutech.ac.jp

Abstract
In this paper we describe a method for extracting product information.

In general, information

about products, such as speci cations, is written
in tabular form.

We focus on product speci ca-tions. Speci cation extraction is a signi cant task
to treat product information. This task is the basisof various systems, such as construction of a product database. A problem in this task concerns thesize of positive data in training data. The positive
data denotes documents including target information (product speci cations in this case). It is approximately 2-5% in training data. With regard tomachine learning methods, lack of data generally
generates a weak classi er. Hence we need to increase the amount of positive data automatically.
To solve this problem, we propose a method for extracting new positive data using a similarity measure. We improve the accuracy of a classi er using

Figure 1: Speci cations of products.

original training data and new positive data extracted from unlabeled data. Experimental results
show the e ectiveness of our method.

Keywords : Table, Product speci cation, Infor-

nation extraction, Similarity

We focus on extraction of product speci cations.
We have also developed a multi-speci cations summarization system for decision support for shopping[11]. In general, their speci cations are presented

1 Introduction

cations on the WWW are written in a <TABLE>

As the World Wide Web rapidly grows, a huge num-an HTML document does not necessarily indicate

ber of online documents are easily accessible on thethe presence of speci cations.

Web.

in tabular form as shown in Fig. 1.

tag. However, the presence of the <TABLE> tag in

Finding information relevant to user needs

has become increasingly important.

The speci -Less than 30% ofHTML <TABLE> tags are real tables in one partic-

Informationular domain [1]. The systems that handle producton the WWW is in the form of not only text but

information need to extract correctly speci cations

also images and tables. Although tables are struc-written in tabular form.

tured information, i.e., attribute-value pairs, most

We have reported methods using support vec-of conventional information retrieval systems treat

tor machines (SVMs) and transductive SVMs fortables as text. Since tables are an ecient way tothis task [2]. A problem in this task concerns theexpress relational information, table extraction is anumber of positive data for machine learning meth-signi cant task for web mining, QA systems, sum-ods. The positive data denotes documents includ-marization and so on [4, 5, 9, 11, 13].

ing target information . It is approximately 2-5%

1Here we consider product information. Speci -in all data. In the case that the number of posi-

cations about the equipment for products, such astive data is insucient, a low-accuracy classi er ispersonal computers and digital still cameras, aregenerated. To generate a high-accuracy classi er,

one of the useful online documents. The speci cations are usually utilized on online-shopping sites.

1 In this paper it is product speci cations.

machine learning methods require a large amountof training data. However, collecting the training
data by hand is costly. To solve this problem, weneed to increase the amount of positive data automatically.

In this paper, we propose a method

for extracting new training data from an unlabeleddata set using a similarity measure.

We improve

the performance of a classi er using a small train-

3.1 SVMs
SVMs are a machine learning algorithm that was
introduced by [12]. They have been applied to tasks
such as face recognition and text classi cation. An
SVM is a binary classi er that
The hyperplane can be written as:

ing data set and the extracted data. We evaluateyi = w~ 1 ~x + b

the e ectiveness of the proposed method by applying to documents of speci cations of PCs, digitalstill cameras and printers. We compare SVMs and
TSVMs using our method with original SVMs and
TSVMs.

~x is an arbitrary data point, i.e., featureyi 2 f+1; 01g. The instances that lie closest to theshows an example of the hyperplane. In thetion, namely extraction of particular tables. There
are several approaches to extract information using
document structures such as itemization and tabular form. Traditionally, they handle a document
image or plain text [3, 8, 9].
On the other hand, there are several approaches
to treat HTML-based tables. Itai et al. have reported a method for information extraction fromHTML pages and integration [5].

gure,solid line shows hyperplane w~ 1 ~x + b = 0.

This paper focuses on product speci cation extrac-

They did not,however, discuss a method for extracting tables.
Although Chen et al. have reported a method forextracting tables from HTML documents, they employed heuristic rules for table extraction [1]. Constructing rules by handwork is costly. We have reported a method for table extraction using Bayes'
rule [10]. Wang et al. have evaluated a table extraction task by machine learning based approaches:
decision tree learning and SVMs [14]. These studies
did not, however, discuss the reduction of the training data. Yoshida et al. have proposed a method
for table structure recognition using an unsupervised method that was achieved by utilizing the EM
However, the accuracy was lower

than the Wang's method, i.e., SVMs. Transductive
SVMs (TSVMs) are a method to obtain high accuracy with a small training dataset and unlabeled
data.

where

vectors, w~ and b are decided by optimization, andhyperplane are called support vectors. Figure 2 (a)2 Related Workalgorithm [15].

nds a maximal

margin separating hyperplane between two classes.

TSVMs have been used for text classi ca-tion, and have improved the performance of SVMs
[6]. In this paper we improve the performance of
SVMs and TSVMs by using our method.

3.2 Transductive SVM
SVMs are a powerful approach for solving various classi cation problems.

However, collecting

the training data for machine learning methods iscostly. SVMs can perform transduction bynding

the hyperplane that maximizes the margin relative
to both the labeled and unlabeled data. This solves
the problem of the cost of collecting the training
data. Transductive SVMs that were introduced by
Joachims [6] take into account a particular test set
and try to minimize misclassi cations of those particular examples.

They improve the performanceof SVMs. The algorithm is as follows:
1. Train an inductive SVM on the training data.
2. Classify the test data by using the hyperplane.
3. Output the predicted classi cation of the test
data, on the basis of the distribution of thepositive and negative data.
4. Identify the two examples which lead to the
reduction of misclassi cations by changing theclass labels of them.
5. Switch these examples and retrain them.
Figure 2 (b) shows an example of TSVMs.
dotted line in theThegure is the hyperplane of an

inductive SVM. Solid circles are unlabeled examples. The solid line shows the transductive classi cation. For our experiment, we use the SV M

light

2
system implemented by Thorsten Joachims . We
use a linear kernel for both SVMs and TSVMs in

3 Classi ers and Feature Selection
3.3 Feature Selection
our experiment.

In this section, we describe classi ers for productspeci cation extraction and a method of feature selection for their classi er. We use SVMs and transductive SVMs as the classi ers.

Our system extracts keywords as feature vectors
for SVMs. Here we utilize the structure of specications written in tabular form for the keyword

2 http://svmlight.joachims.org/

+

+

+

+

+

+

+

+

+

+

+

+

+

+

margin(a)(b)

Figure 2: SVMs and transductive SVMs.

extraction.

The structure is that, generally, at-tributes in speci cations correspond to the 1st column in tables and values that belong to the attributes correspond to the rest of columns.

Re-

quirements for keyword extraction are as follows:
1. Words in the 1st column in a table;
2. Words which appear in a text of speci clength;not including speci cations respectively.

normalized tf 1 idf

tf 1 idf is one of the most popular method forweighting. The tf 1 idf weight of a term in one
document is the term frequency (tf ) divided
by its document frequency (idf ). In this paper,
we employ a method derived from the normal

tf 1 idf with some adjustments. This method

3. Words which appear frequently in a document
including speci cations or not including speci cations.

was used for a table detection task by Wanget al [14]. The tf 1 idf weight of termt in Dreal

and the weight of termt in Dno are computedas:

We use words that satisfy these three requirements.
We handle the contents of the 1st <TD> in <TR>tags.

documents including speci cations and documents

wtpos =The reason why we use only the 1st col-umn for the keyword extraction is that words inattributes are rarely changed to other words. For

wtneg =

example, the word \CPU" appears in attributes
about most of PCs speci cations.

However, thevalues of the attribute \CPU" are often changed(Pentium $ Celeron, GHz $ MHz).

Thereforewords in attributes are characteristic words for de-

X tf t; d 2 df N
N df
X tf t; d 2 df N
pos
t
pos

(

i)

log(

(

i)

log(

di 2Dposdi 2Dnegneg
neg + 1)
t

neg
pos
t
Nneg dftpos + 1)

where Npos and Nneg are the number of docpost
neg
are the number of documents includt

uments in Dpos and Dneg respectively.

and dfdf

tection of speci cations. If the contents consist of

ing termt in Npos and Nneg respectively. We

25 characters or less, our system extracts it as key-use cosine normalization for weighting.

word candidates.

The condition is heuristic.

We

divide the keyword candidates into words by using
the Japanese morphological analyzer ChaSen [7].
Next, the system computes the weights of the
keyword candidates and then extracts keywords
from them, i.e., the feature selection for SVMs andwtpos ; wsneg = wtneg
wspos
=
t
t
Norm
Norm
pos

where

Normpos =TSVMs.
In this paper, we use normalized
weighting.
and wsneg

tf 1 idf forwspos

A keyword has two indicators:. The ws

pos

is the weight of a keyword

in Dpos . If a keyword appears frequently in docu-

Normneg =negs X w 2w ;s X w 2w
t2Dpost2Dneg

pos
t

pos
t

no
t

neg
t

ments that contain speci cations and appears infrequently in documents that do not contain speci cations, the value of ws

pos

is high. The ws

weight of a keyword in Dneg .

negis theDpos and Dneg are

We use the words exceeding a threshold. Thesewords are feature vectors for SVMs. The weight ofa word is the value of the vector (the word).

Unlabeled Data

Table 1: Dataset

Extract a positive document

Training Data

Similarity and Vote
PC

Digital Camera

Specs

239

117

143

NotSpecs

4761

4883

4857

DivideAll Pos Docs
Half Neg Docs

High similarity Docs

Half Neg Docs
Integration

Printer

Temporal Training Data

(3-1) Compute the similarity between the

SVMs

documents and the other documents in

Temporal Test Data

Evaluation

the unlabeled data.

Integration: Training and Extracted Data

(3-2) If the similarity is more than or equal to

New Training Dataa threshold th1 , vote for the document.

SVMs or TSVMs(4) If the number of votes obtained is more than orequal to a threshold th2 , extract the document

Test Data

Evaluationas positive data.

(5) Divide the training data into two groups: (a)Figure 3: Outline of our process.

4 Extraction of Positive Data
from Unlabeled Datatemporal training data and (b) temporal test

For a small number of training data, the size ofdata consists of the other documents in thepositive data in them is a problem in this task.

training data.

It is approximately 2-5% in all data. In the casethat the number of positive data is insucient,machine learning methods usually generate a lowaccuracy classi er.

Therefore we need to extract

more amount of positive data from unlabeled data

The temporal training data consists of the extracted documents and half of negative documents in the training data. The temporal test(6) Generate a classi er from the temporal training data (a). As regards the classi er, we use
SVMs.

(7) Evaluate the performance of the classi er withthe temporal test data (b).

automatically.
In this paper, we compute the degree of similarity
between a positive document in training data anddocuments in unlabeled data. Figure 3 shows theprocessdata.

ow of the proposed method. Our method

determines an appropriate threshold in the extraction process automatically. The algorithm is as follows:(1) Extract a positive document from trainingdata.

(2) Compute the similarity between the positive(8) Decrease th1 and go back to (2) in the casethat th1 is higher than a limit.

(9) Compare the performance of the classi ers ineach turn: the results in (7). Detect the appropriate th1 .

(10) Integrate original training data and the data
extracted by the appropriate th1 .

Determination of the appropriate th1 is an issue in this proposed method.

In this paper, wesearch for the th1 in which the precision rate de-document and documents in unlabeled data.

creases as compared with the previous turn.

The similarity is computed as follows:other words, the process is to identify a disimprovedsim(px ; uy ) =

P
qP P
N
i=1

N
i=1

turn inx i 1 yix2i 2(7). Here we de ne the th1 of the previous

turn as the appropriate th1 because the decrease of

N
i=1

yi2

the precision rate in this method denotes that themethod extracted negative documents as positive

where p and u are a positive document and adocuments.

document in unlabeled data respectively.

5 Evaluationxi

and yi are the value of a word i in p and u
respectively. These words and values are thesame as feature vectors for SVMs.
number of words (vectors).

N is theThis formula iswell-known as the cosine measure.

(3) If the similarity is more than or equal to a
threshold th1 , vote for the document.
For the documents voted in (3),In

We evaluated the appropriateness for the proposed
method with a dataset.

The data was extracted

from 28 manufacturer's sites by ale download-

ing software. The data consists of web documents
about PCs, digital still cameras and printers. The
total number of pages is 86737.

The dataset forTable 2: Experimental result

Product Measure
PC
P
R
F
DigitalP
CameraR
F
PrinterP
R
F

Method(2) Our+ SVM
0.84380.86620.83630.86130.8428(1) SVM
0.9171

0.69280.7711

0.95820.52010.64080.83910.79710.89440.47980.57340.86120.8247

evaluation was constructed by 5000 web documents
extracted from all the data randomly. These documents were divided into 100 documents as training(3) TSVM
0.83840.87890.85510.72640.83480.76080.76700.78910.7574

Method(4) +Our
TSVM
0.83600.91120.87080.72180.88400.77620.84020.82660.8179

Table 3: The result of acquisition of new training
data

Product POS AVE
R
P
PCs
45
6.8 0.1511 0.8909
Cameras 16
4.2 0.2625 0.5899
Printers 34
50.1471 0.6950

data and 4,900 documents as test data. Unlabeleddata for our method and TSVMs was 1000 documents in the test data. We evaluated this experiment with 5 training data extracted from the 5000
documents. The number of data is shown in Table
1. In Table 1, the Specs and the NotSpecs denote
documents including speci cations and documents
not including speci cations, respectively. The Not-

precision rates of SVMs were higher than those ofSpecs includes speci cations of other products. For

our method and TSVMs. The results show the ef-

example, the NotSpecs for digital cameras includes

fectiveness of the proposed method.

the speci cations of video cameras and still cam-To accomplish higher F -measure, we need fur-eras.

ther consideration for the determination of two

We evaluated this task by F -measure. The F measure is computed as follows:

precision rates of the acquisition process of positive
data from unlabeled data. The POS in Table 3 is1

the number of positive data (documents including

F -measure (F ) = 1
1+
2P

thresholds th1 and th2 . Table 3 shows recall and

2R

where R and P denote a Recall and a P recision
rate respectively.
# of documents extracted correctly
Recall (R) = # of
documents including specifications

extracted correctly
Precision (P ) = # of#documentsof extracted documents
We set the initial th1 to 0.95. The th1 was decreased in decrements of 0.05 until 0.35. We set theth2 to vote num 2 32 . The vote num denotes thenumber of votes obtained in the step(3) in Sect.

4.

speci cations) in 1000 unlabeled data.

The AVE

in Table 3 is the average of the number of documents extracted correctly in the process. The results denote that our method often extracted negative documents as positive documents.

In thisprocess, the precision rate is the most importantfactor. If the process extracts negative documents
as positive documents, it generates a low-accuracy
classi er because the new training data contains
incorrect labeled data. In particular, the precision
rates of digital cameras and printers were insucient.

The results caused the decline of the pre-cision rates in the product speci cation extraction(Table 2). Therefore, the estimation of the appro-

We compared 4 methods: (1) SVMs, (2) SVMs

priate thresholds is one of the most important task.

with our method, (3) TSVMs, and (4) TSVMs with

Also, we need to treat other similarity measures forour method. The experimental results are shown

the improvement of accuracy.

in Table 2.

For PCs, the method (4), TSVMs

with our method, produced the best performanceon F -measure. For digital cameras and printers,
the method (2), SVMs with our method, yielded

6 Conclusions

the best F -measure. Our method and TSVMs im-

Table extraction in web documents is an interesting

proved the recall rate, as compared with SVMs.

problem with many applications, such as web min-This led to the improvement of F -measure. The

ing, QA systems and summarization. In this paper,

recall rates of SVMs was insucient although the

we focused on product speci cations presented intabular form. A problem in this task concerns thenumber of positive data for machine learning methods. We proposed a method for extraction of new
training data using a similarity measure.

SVMs

and TSVMs with our method outperformed original SVMs. Experimental results show the e ectiveness of this method. The accuracy of the acquisition process of positive data from unlabeled data
was insucient. To accomplish higher F -measure,
we need further consideration for the determination of two thresholds in the proposed method. Our
future work includes (1) evaluation with other machine learning methods, (2) estimation of appropriate thresholds, and (3) consideration of other similarity measures.

Croft. Table extraction using conditional ran-

In Proceedings of the 26th annual international ACM SIGIR conference on
Research and development in informaion retrieval, pages 235{242, 2003.
dom feilds.

[10] K. Shimada, K. Hayashi, and T. Endo. Keyword and weighting for product speci cations
extraction. In

Proceedings of PACLING 2003,

pages 285{293, 2003.

[11] K. Shimada, T. Ito, and T. Endo. Multiform
summarization from product speci cations. In

Proceedings of PACLING 2003, pages 83{92,2003.

References[12] V. N. Vapnik.
ley, 1999.

[1] H.H. Chen, S.C. Tsai, and J.H. Tsai. Mining
tables from large scale html texts. In

Proceed-ings of COLING2000, pages 166{172, 2000.

[2] K. Hayashi, K. Shimada, and T. Endo. Product[9] D. Pinto, A. McCallum, X. Wei, and W. B.

speci cation

extractionusingmachineStatistical Learning Theory. Wi-[13] H. L. Wang, S. H. Wu, K. K. Wang, C. L.
Sung, W. L. Hsu, and W. K. Shih. Semantic
search on internet tabular information extrac-

Proceedings ofthe ninth international conference on Information and knowledge management, pages 243{

tion for answering queries. In

Proceedings of the 10th
249, 2000.
Annual Meeting of The Association for Natural Language Processing (in Japanese), pages [14] Y. Wang and J. Hu.

learning methods. In

733{736, 2004.

A machine learning

based approach for table detection on the web.

[3] J. Hu, R. Kashi, D. Lopresti, and G. Wilfong. Medium-independent table detection. In

In Proceedings of The Eleventh International
World Web Conference, 2002.

Proceedings of Document Recognition and Re- [15] M. Yoshida, K. Torisawa, and J. Tsujii. Extrieval VII, pages 23{28, 2000.
tracting ontologies from world wide web via
html tables. In Proceedings of PACLING 2001,[4] M. Hurst. Layout and language: Challenges
pages 332{341, 2001.
for table understanding on the web. In Proceedings of Workshop on Web Document Analysis, WDA01, pages 27{30, 2001.
[5] K. Itai, A. Takasu, and J. Adachi. Information extraction from html pages and its inte-

In Proceedings of the 2003 Symposium on Application and the Internet Workshops (SAINT03), pages 276{281, 2003.

gration.

[6] T. Joachims. Transductive inference for textclassi cation using support vecor machines.

Proceedings of the Sixteenth International
Conference on Machine Learning, pages 200{In

209, 1999.

[7] Y. Matsumoto, A. Kitauchi, T. Yamashita,
Y.

Hirano,H.

Matsuda,

,

and

M.

Asa-

hara. Japanese morphological analysis systemchasen version 2.0 manual 2nd edition. Technical report, 1999.
[8] H.T. Ng, C.Y. Lim, and J.L.T. Koo. Learn-

ing to recognize tables in free text. In Proceedings of the 37th Annual Meeting of ACL,
pages 443{450, 1999.