Discovery of Nominally Conditioned
Polynomials using Neural Networks, Vector
Quantizers and Decision Trees
Kazumi Saito1 and Ryohei Nakano2
1
NTT Communication Science Laboratories
2-4 Hikaridai, Seika, Soraku, Kyoto 619-0237 Japansaito@cslab.kecl.ntt.co.jp
2
Nagoya Institute of Technology
Gokiso-cho, Showa-ku, Nagoya 466-8555 Japannakano@ics.nitech.ac.jp

1

Introduction

2

Restoring Nominally Conditioned Polynomials

The discovery of a numeric law, e.g., Kepler’s third law T = kr3/2 , from datais the central part of scientiﬁc discovery systems. The data considered in many
real ﬁelds usually contains both nominal and numeric values. Thus, we consider
discovering a law that governs such data in the form of a rule set of nominallyconditioned polynomials. Recently, a connectionist method called RF6 [1] wasproposed to solve problems of this type. RF6 can learn multiple nominally conditioned polynomials with single neural networks; besides, RF6 can discover generalized polynomials whose power values are not restricted to integers. However,for real complex problems, RF6 will suﬀer from a combinatorial explosion in theprocess of restoring rules from a trained neural network. Therefore, this paper
proposes a new version of RF6 by greatly improving its procedure of restoring
nominally conditioned polynomials from a trained neural network.

Let {q1 , · · · , qK1 , x1 , · · · , xK2 , y} be a set of variables describing an example,
where qk is a nominal explanatory variable, xk is a numeric explanatory variable
and y is a numeric target variable. For each qk we introduce a dummy variable
expressed by qkl , i.e., qkl = 1 if qk matches the l-th category; otherwise 0, wherel = 1, · · · , Lk , and Lk is the number of distinct categories appearing in qk . As atrue model governing data, we consider the following set of multiple nominallyconditioned polynomials whose power values are not restricted to integers.
if


qkl

∈Qi

i

qkl = 1theniy(x; Θ ) = w0i +

J

j=1

wji

K2

k=1

wi

xk jk ,

i = 1, · · · , I ∗ (1)where I ∗ is the number of rules, Qi denotes a set of dummy variables corresponding to the i-th nominal condition and Θi is a parameter vector used in theii-th generalized polynomial. Here, each parameter wji or wjk
is a real number,i
and J is an integer corresponding to the number of terms.

 1 L k
Consider a function c(q; V ) = exp( K
k=1
l=1 vkl qkl ), where V denotes avector of parameters vkl . We can show [1] that with an adequate number J, cer
 1 L ktain type of neural network y(q, x; Θ) = w0 + Jj=1 wj exp( K
k=1
l=1 vjkl qkl +
 K2
µ
µ µ
k=1 wjk ln xk ) can closely approximate Eq. (1). Let D = {(q , x , y ) : µ =1, · · · , N } be a set of training data, where N is the number of examples. Then,each parameter can be estimated by minimizing an objective function E(Θ) =
N
T
µ
µ
µ
2
µ=1 (y − y(q , x ; Θ)) + Θ ΛΘ, where a penalty term is added to improve
both the generalization performance and the readability of the learning results.
2.1 Restoring Procedures
Assume that we have already obtained a neural network trained as the best
law-candidate. In order to restore a set of nominally conditioned polynomials as
described in Eq. (1), we need a suitable eﬃcient procedure.
RF6 [1] has a decomposition procedure for this purpose; i.e., a set of nominally conditioned terms is extracted from each hidden unit, and then each ofthese terms is in turn combined through all of the hidden units. When α denotes the average number of terms over each hidden unit, the total number ofthese combined terms approximately amounts to αJ . Thus, as the number ofhidden units or the number of nominal variables increases, this procedure comesto suﬀer from a combinatorial explosion.
As another approach, we can extract nominally conditioned polynomials foreach training example, and simply assemble them to obtain a ﬁnal set of rules
as a law. Then, the following set of nominally conditioned polynomials can beobtained directly from the training data and the trained neural network.
if

qkl = 1 then y = w
0 +µ{k,l:qkl
=1}

K2
J


w

cµj
xk jk ,j=1

µ = 1, · · · , N,

(2)

k=1

where cµj denotes the j-th coeﬃcient calculated from the nominal values of theK1 Lkµj exp( k=1
vjkl qkl). However, in comµ-th training example, i.e., cµj = w
l=1 
parison with the true model governing the data deﬁned in Eq. (1), the results ofthis naive procedure can be far from desirable because they will contain a large
number of similar polynomials, and each nominal condition will be too speciﬁc
in terms of representing only one training example.
Based on the above considerations, we propose a new restoring procedure.
step1. finding subspace representatives
In order to ﬁnd subspace representatives, a set of coeﬃcient vectors {cµ =(cµ1 , · · · , cµJ )T : µ = 1, · · · , N } calculated from the training data is quantized
into a set of representative vectors {r i = (r1i , · · · , rJi )T : i = 1, · · · , I}, where
I is the number of representatives. Among several vector quantization (VQ)
algorithms, we employ the k-means algorithm due to its simplicity.
step2. criterion for model selection
Consider the following set of rules using the representative vectors.
if i(q) = i

then y = w
0 +

J

j=1

rji

K2

k=1

w


xk jk ,

i = 1, · · · , I,(3)

where i(q) denotes a function that returns the index of the representative vecJ
tor minimizing the distance, i.e., i(q) = arg mini j=1 (cj − rji )2 . Here, since K1  L k
j exp( k=1jkl qkl ), Eq. (3)each element of c is calculated as cj = w
l=1 v
can be applied to a new example, as well as the training examples. Thus,
to determine an adequate number I of representatives, we employ the procedure of cross-validation which divides the data D at random into S dis (s)tinct segments {Ds : s = 1, · · · , S}. Namely, by using the ﬁnal weights Θtrained without data segment Ds , we can deﬁne a cross-validation error func(s)JS i(q ν ) K2
(s)
jk
ν w
tion CV = N −1 s=1 ν∈Ds (y ν − (w
0 + j=1 rj))2 .
k=1 (xk )step 3. generating conditional parts
The indexing functions {i(q)} described in Eq. (3) must be transformed into a
set of nominal conditions as described in Eq. (1). One reasonable approach is toperform this transformation by solving a classiﬁcation problem whose training
examples are {(qµ , i(q µ )) : µ = 1, · · · , N }, where i(q µ ) indicates the class labelof a training example q µ . For this classiﬁcation problem, we employ the c4.5
decision tree generation program due to its wide availability. From the generated
decision tree, we can easily obtain the ﬁnal rule set as described in Eq. (1).
Clearly, these steps can be executed within the computational complexity oflinear order with respect to the numbers of training examples, variables, hidden
units, representatives, iterations performed by the k-means algorithm, and data
segments used concerning cross-validation; i.e., this new restoring procedure canbe much more eﬃcient than the old decomposition procedure which requires
the computational complexity of exponential order. Hereafter, the law discovery
method using the above restoring procedure is called RF6.2.
2.2 Evaluation by Experiments
By using three data sets, we evaluated the performance of RF6.2. In the kmeans algorithm, initial representative vectors {ri } are randomly selected as asubset of coeﬃcient vectors {cµ }. For each I, trials are repeated 100 times with
diﬀerent initial values, and the best result is reported. The cross-validation error
is calculated by using the leave-one-out method, i.e., S = N . The candidate
number I of representative vectors is incremented in turn from 1 until the crossvalidation error increases. The c4.5 program is used with the initial settings.
Artificial data set.
We consider an artiﬁcial law described by
1/2 −1/3−1 3
 if q21 = 1 ∧ (q31 = 1 ∨ q33 = 1) then y = 2 + 3x1 x2 + 4x3 x4 x5
1/2 −1/3
3(4)
if q21 = 0 ∧ (q32 = 1 ∨ q34 = 1) then y = 2 + 5x−1
1 x2 + 2x3 x4 x5
1/2 −1/3−1 3
else
then y = 2 + 4x1 x2 + 3x3 x4 x5
where we have three nominal and nine numeric explanatory variables, and thenumbers of categories of q1 , q2 and q3 are set as L1 = 2, L2 = 3 and L3 = 4,
respectively. Clearly, variables q1 , x6 , · · · , x9 are irrelevant to Eq. (4). Each valueof nominal variables q1 , q2 , q3 is randomly generated so that only one dummy
variable becomes 1, each value of numeric variables x1 , · · · , x9 is randomly generated in the range of (0, 1), and we get the corresponding value of y by calculating

Eq. (4) and adding Gaussian noise with a mean of 0 and a standard deviationof 0.1. The number of examples is set to 400.
In this experiment, a neural network was trained by setting the number ofhidden units J to 2. We examined the performance of the experimental results
obtained by applying the k-means algorithm with the diﬀerent number of representative vectors, where the RMSE (root mean squared error) was used forthe evaluation; the training error was evaluated as a rule set by using Eq. (3);the cross-validation error was calculated by using the function CV; and the generalization error was also evaluated as a rule set and measured by using a setof noise-free 10, 000 test examples generated independently of the training examples. The experimental results showed that the training error almost monotonically decreased (2.090, 0.828, 0.142, and 0.142 for I = 1, 2, 3, and 4, respectively); the cross-validation error was minimized when I = 3 (2.097, 0.841,
0.156, and 0.160 for I = 1, 2, 3, and 4, respectively, i.e., indicating that an adequate number of representative vectors is 3); and the generalization error was
also minimized when I = 3 (2.814, 1.437, 0.320, and 0.322 for I = 1, 2, 3, and4, respectively). Since the cross-validation and generalization errors were minimized with the same number of representative vectors, we can consequently seethat the desirable model was selected by using the cross-validation.
By applying the c4.5 program, we obtained the following decision tree whose
leaf nodes correspond to the following.
q21 = 0:||q21 = 1:||

q34 = 1: 2 (83.0)
q34 = 0: q32 = 0: 3 (129.0)|
q32 = 1: 2 (53.0)
q34 = 1: 3 (36.0)
q34 = 0: q32 = 0: 1 (73.0)|
q32 = 1: 3 (26.0)

⇔
⇔
⇔
⇔
⇔
⇔

r2 = (+5.04, +2.13)
r3 = (+3.96, +2.97)
r2 = (+5.04, +2.13)
r3 = (+3.96, +2.97)
r1 = (+3.10, +4.07)
r3 = (+3.96, +2.97)

where the coeﬃcient values were rounded oﬀ to the second decimal place; eachnumber of training examples arriving at the corresponding leaf node is shown inparenthesis. Then, the following rule set was straightforwardly obtained.

if q21 = 1 ∧ (q31 = 1 ∨ q33 = 1)then y = 2.01 + 3.10x−1.00
x+3.01+ 4.07x+1.02
x+0.51x−0.3312
3
4
5
if q21 = 0 ∧ (q32 = 1 ∨ q34 = 1)(5)
−1.00 +3.01+1.02 +0.51 −0.33

then
y
=
2.01
+
5.04x
x
+
2.13x
x
x

1
2
3
4
5


else then y = 2.01 + 3.96x−1.00
x+3.01+ 2.97x+1.02
x+0.51x−0.33.
12
3
45
Recall that each nominal variable matches only one category, e.g., (q32 = 1∧q34 =0) ≡ (q32 = 1). Therefore, although some of the weight values were slightly
diﬀerent, we can see that a law almost equivalent to the true one was found.
Financial data set.
We performed an experimental study to discover underlying laws of market capitalization from six fundamental BS (Balance Sheet) items and the type of industry (the 33 classiﬁcations of the Tokyo Stock Exchange). Our experiments useddata from 953 companies listed on the ﬁrst section of the TSE, where banks,

and insurance, securities and recently listed companies were excluded. In orderto understand the eﬀect of the nominal variable intuitively, the number of hidden
units was ﬁxed at 1. The cross-validation error was minimized at I = 3. Then,the following rule set was obtained.
ql = 1 then y = 12891.6 + ri x+0.668
x+1.043x−0.747
,
2
3
6

if

i = 1, 2, 3 (6)ql ∈Qiwhere r1 = +1.907, r2 = +1.122, r3 = +0.657 and each of the nominal conditions was as follow: Q1 = {“Pharmaceuticals”, “Rubber Products”, “Metal
Products”, “Machinery”, “Electrical Machinery”, “Transport Equipment”, “Precision Instruments”, “Other Products”, “Communications”, “Services”}; Q2 ={“Foods”, “Textiles”, “Pulp & Paper”, “Chemicals”, “Glass & Ceramics”, “Nonferrous Metals”, “Maritime Transport”, “Retail Trade”}; and Q3 = {“Fisheries”,“Mining”, “Construction”, “Oil & Coal Products”, “Iron & Steal”, “Electricity & Gas”, “Land Transport”, “Air Transport”, “Wearhousing”, “Wholesale”,“Other Financing Business”, “Real Estate”}. Since the second term on the righthand side of the polynomials appearing in Eq. (6) is always positive, each of
the coeﬃcient values ri can indicate the stock price setting tendency of industry
groups in similar BS situations, i.e., the discovered law tells us that industries
appearing in Q1 are likely to have a high setting, while those in Q3 are likely tohave a low setting.
Automobile data set.
The Automobile data set contained data on the car and truck speciﬁcations in
1985, and was used to predict prices based on these speciﬁcations. The data set
had 159 examples with no missing values, and consisted of 10 nominal and 14
numeric explanatory variables and one target variable (price). In this experiment,
since the number of examples was small, the number of hidden units was also set
to 1. The cross-validation error was minimized at I = 3. The polynomial part ofthe discovered law was as follows:
x+0.046x−1.436
x+0.997x−0.245x−0.071
y = 1163.16 + ri x+1.638
2
4
5
6
9
13
1

2

(7)

3

where r = +1.453, r = +1.038, r = +0.763 and the relatively simple nominal
conditions were obtained. Similarly as described for the experiments using theﬁnancial data set, since the second term on the right hand side of Eq. (7) is always
positive, the coeﬃcient value ri can indicate the car price setting tendency forsimilar speciﬁcations. Actually, the discovered law verbally told us that cars ofa high price setting are: “5-cylinder ones”, “BMW’s”, “convertibles”, “VOLVO
turbos”, “SAAB turbos”, and “6-cylinder turbos”; cars of a middle price setting
are: “PEUGOT’s”, “VOLVO non-turbos”, “SAAB non-turbos”, “HONDA 1bblfuel-system ones”, “MAZDA fair-risk-level ones”, “non-BMW non-turbos & 6cylinder ones”, “non-5-cylinder turbos & fair-risk-level ones”; and other cars areof a low price setting.

Reference
1. R. Nakano and K. Saito. Discovery of a set of nominally conditioned polynomials.
In Proc. 2nd Int. Conference on Discovery Science, LNAI 1721, pp. 287–298, 1999.