Parallelized Knowledge Discovery System:
An Enhancement to BONSAI
Hideo Bannai

1Toshio Masuda

bannai@ims.u-tokyo.ac.jp
Tomohiro Yasuda

1

tyasuda@ims.u-tokyo.ac.jp
1
2
3

2

Masao Nagasaki

tmasuda@ims.u-tokyo.ac.jp
Osamu Maruyama

masao@ims.u-tokyo.ac.jp

3maruyama@ims.u-tokyo.ac.jp1

Satoru Miyano

3

miyano@ims.u-tokyo.ac.jp

Department of Information Science, Graduate School of Science, The University ofTokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8654, Japan
Course in

Computer

Scienceand Information

Mathematics,

Graduate SchoolofElectro-Communications, 1-5-1 Chofugaoka, Choufu-city, Tokyo 182-8585, Japan
Human Genome Center, Institute of Medical Science, The University of Tokyo, 4-6-1
Shirokanedai, Minato-ku, Tokyo 108-8639, Japan

1 Introduction
BONSAI is a machine learning system for knowledge acquisition from positive and negative examples
of strings. It is reported that the system has discovered knowledge which can classify amino acidsequences of transmembrane domains and randomly chosen amino acid sequences located in otherparts of the PIR database, with over 90% accuracy [4]. A hypothesis generated by the system is a pairof a classi cation of symbols called an alphabet indexing, and a decision tree over regular patterns,
which classi es given examples with high accuracy. The whole algorithm of the system consists of
two parts: a learning algorithm for constructing a decision tree over regular patterns, and a searchingalgorithm for nding an alphabet indexing to produce a better decision tree.
Through providing a service of BONSAI system, which is available at our web site
http://bonsai.ims.u-tokyo.ac.jp/bonsai/, we have found problems concerned with the system.
One of the problem is that for the size n of an alphabet indexing, which can be speci ed by the user,
the current system is implemented to take time exponential in n. In fact, it is impossible to executethe system with a large n. To overcome this situation, we have discussed how to parallelize BONSAI
and succeeded in implementing BONSAI in parallel with some more enhancements.

2 Improvements of BONSAI
Local Search in Parallel:

Generally, an indexing of an alphabet 6 by another alphabet 0 is a mapping from 6 to 0. The
neighbors of are the indexing whose distance from is one, where the distance between and anindexing  of 6 by 0 is de ned by jf 2 6 j () 6= ()gj. For an alphabet indexing , the BONSAI
system produces a decision tree T by employing a learning algorithm, and outputs as a hypothesis thepair and T . To nd the best possible hypothesis, a pair of an alphabet indexing and a decision
tree T , the system is designed to nd an alphabet indexing by a local search method. In this local
search method, for an alphabet indexing , the system nds a local optimum  among the neighborsof , and replaces with . The search for a local optimum is repeated until  is no better than .
We have implemented in parallel this procedure searching for a local optimum by using multi-threads.
The improvement in performance concerning with this work is shown in Fig. 1.

238

Data Filter:

The algorithm of BONSAI has no restriction on strings as input. However, the system has been
mainly applied to mere sequence data such as DNA or amino acid sequences. The reason would bethat, as positive and negative examples, the system accepts only strings over the ASCII character set,say 6, and construct an alphabet indexing of 6, that is, each alphabet of 6 is indexed to a symbolof another alphabet. To conquer the obstacle to handling various data, we have modi ed BONSAI
to execute the preprocess which employs a lter, called a data lter, transforming data according to
the user's intention. This enables us apply various data to BONSAI just by creating a plug-in of alter for the data type. Currently, data lters for English and Japanese sentences are available, which
implies that BONSAI can try to automatically acquire knowledge from documents.
Node Limit:

60
50
40
30

Speed-up

20

10
9
8
7
6
5
4
3
2
Actual performance
Ideal performance
1
1

2

3

4

5

6

7 8 9 10# of Threads

20

30

40

50 60

Figure 1: Performance of BONSAI. The performance is measured on a Sun Ultra Enterprise-10000 with 64 processors of
250MHz UltraSPARC. The implemented program adopts the
POSIX thread. 689 positive (Transmembrane domain taken fromthe PIR database) and 19256 negative (generated randomly) examples were used. The window size was set at 10 and the indexingalphabet size was set at 6.

Some users prefer a compact hypothesis
to a precise one. A smaller hypothesis
may capture the knowledge involved ina more comprehensible manner. Compact hypotheses in BONSAI are createdby limiting the size of the decision tree.
Even a stub, which is a decision tree withexactly one node, has been veri ed to
be an acceptable model of a hypothesis[1]. Our new BONSAI system provides
an option that limits the size of the decision tree created, therefore making a stubavailable as an alternative hypothesis in
the BONSAI system.

Boosting:

Boosting is a general method which can be used to reduce the error of any \weak" learning algorithm, as long as the algorithm can consistently generate classi ers that are better than random
guessing [3]. A form of boosting called AdaBoost [2] has been empirically shown to improve BONSAI's precision [1]. We have integrated AdaBoost into our new system, therefore providing resultswith higher accuracy. Also, boosting stubs has yielded interesting results [1].

3 Concluding Remarks
As we are now in the process of preliminary experiment, we will report the experimental results at aposter site. The service of the new version of BONSAI is available at our BONSAI site
http://bonsai.ims.u-tokyo.ac.jp/heibon/.

References[1] Bannai H., Boosting BONSAI, Senior Thesis, Department of Information Science, The Universityof Tokyo, 1998.
[2] Freund, Y. and Schapire, R.E., A Decision-Theoretic Generalization of On-line Learning and an
Application to Boosting, Journal of Computer and System Sciences, 55(1):119{139, 1997.
[3] Schapire, R.E., The Strength of Weak Learnability, Machine Learning, 5(2):197{227, 1990.
[4] Shimozono, S., Shinohara, A., Shinohara, T., Miyano, S., Kuhara, S., and Arikawa, S., Knowledge
Acquisition from Amino Acid Sequences by Machine Learning System BONSAI, Transactions ofInformation Processing Society of Japan, 35(10): 2009{2017, 1994.
239