82 A. Carcano et al.
Example 5.The above translation applied to Example 1 gives fA = A ∧
¬B, fB= 0. Note that the form offBmeans that the only possible state change
forBisfrom1to0.
Example 6.The T-lymphocyte model studied in Sect. 5 is originally a Thomas’
network, where we have, for instance:fIFNg= (STAT4∨TBet)
4 PAC Learning from Traces
4.1 Diverse Initial States Versus Long Time Horizon
In practice, one cannot assume to have full access to the hidden Boolean function
as required bySampleandOracle, but rather to data time-series, or traces,
produced from biological experiments. For the scope of this paper, we consider
simulation traces obtained from a hidden model which we wish to discover. Two
types of traces are considered: Boolean and stochastic simulation traces. In both
cases, the mapping to the concepts of PAC-learning is easy: aSamplefor the
activation functionx+(resp. deactivaction functionx−) is a statesisuch that
xi<xi+1(resp.xi>xi+1). See Fig. 1 for an example.
Fig. 1.Illustration of a Boolean trace with three steps. Betweenaandb, the first gene
has been activated, and betweenbandc, the last one has been deactivated.
One striking feature of PAC learning is to associate a guarantee on the quality
hof each learnt Boolean function depending on the number of samples used,
namelyL(h,(2n)k+1), wherenis the number of genes/molecules observed, and
kis the maximum number of literals per conjunct. In practice,kseems to be
limited to 3 or 2, and the number 2nof different possible literals in a clause, can
also be reduced through prior knowledge (e.g. in Sect.5.3).
It is worth noticing that the global guarantee on the learnt model is the
minimum of all precision boundsh. In order to perfectly recover a hidden model,
it is thus necessary to have sufficiently diverse samples. For this reason, one
should expect to get better performance with large sets of short traces obtained
from a uniformly distributed set of initial states, rather than with a small set of
long traces which introduce a bias in the distribution of the transition samples
(e.g. when looping in an attrator). The important point is that PAC learning
algorithms do provide bounds on the error according to this space-time trade-off.