Biology Reference
In-Depth Information
3.5.1
Preprocessing: Minimal Sets Algorithm
We saw in the previous section that the choice of monomial ordering affects which
model is selected from the model space. One way to minimize the effect of this
choice is to minimize the number of variables in the ambient ring. We again restrict
our attention to finding functions
f
j
for a node
x
j
. Consider the data set
D
j
=
{
(
as above and let
F
j
be the set of polynomials that fit the
data. Next we describe the Minimal Sets Algorithm (MSA) which finds the smallest
sets of variables such that a polynomial in
F
j
in those variables exists (see [
18
]for
more details).
Definition 3.8.
Let
D
j
and
F
j
be as above. Then
M
s
1
,
t
1
j
),...,(
s
m
,
t
mj
)
}
={
x
i
1
,...,
x
i
r
}⊆{
x
1
,...,
x
n
}
is a
minimal set
if
F[
x
i
1
,...,
x
i
r
]∩
F
j
=∅
and removal of any variable from
M
renders
the intersection empty.
Minimal Sets Algorithm:
1.
Input
D
j
.
2.
Partition the input states
s
1
,...,
s
m
according to the output values
t
1
j
,...,
t
mj
.
For each output value
t
ij
,let
X
t
ij
={
s
k
|
(
s
k
,
t
ij
)
∈
D
j
}
. Then the partition is
.
3.
Compute the square-free monomial
given by
X
={
X
t
ij
|
1
≤
i
≤
m
}
ideal
M
generated by the monomials
)
=
s
ki
=
s
i
x
i
for all
s
k
m
(
s
k
,
s
∈
X
t
kj
and
s
∈
X
t
j
in which
t
kj
=
t
j
.
The monomials
m
(
s
k
,
s
)
encode the coordinates in which the input states
s
k
and
differ.
4.
Compute the primary decomposition of
M
; that is, write
M
as the irredundant
intersection
i
Q
i
of primary ideals.
s
5.
Return the generating sets of the associated minimal prime ideals
√
Q
i
.
The generating sets of the ideals
√
Q
i
are the sought after minimal sets (see
Corollary 4 of [
18
]).
Theorem 3.1.
Let D
j
be as above. The minimal sets for D
j
are the generating
sets of the minimal primes in the primary decomposition of the monomial ideal M as
constructed above.
Example 3.8.
Consider the data in Example
3.6
. The minimal sets for
x
1
are
{
, meaning that there is a polynomial function in one variable that
fits the data for
x
1
. In this case the minimal sets are the same for nodes 2 and 3.
Essentially what the MSA does is it computes the intersection of all possible
“minimal” wiring diagrams. In the above example, the minimal sets for
x
1
are
x
1
}
,
{
x
2
}
, and
{
x
3
}
{
x
1
}
,
{
which indicates that ALL minimally described functions which fit the
data for
x
1
will be in terms of just one variable.
As the above example demonstrates, there are typically many minimal sets for a
node. Next we introduce a method to score minimal sets, based on the sparseness
assumption.
Let
M
j
be the set of minimal sets for a node
x
j
. Define
Z
s
to be the number of
sets in
M
j
of cardinality
s
and
W
i
(
x
2
}
, and
{
x
3
}
s
)
to be the number of sets
X
in
M
j
of cardinality
Search WWH ::
Custom Search