Information Technology Reference
In-Depth Information
t))
spent by
p
on
computing
h(
≤
t)
. A runtime-dependent quality measure inspired by optimal uni-
versal search (Levin
1973
)is
C
lτ
p,h(
C
l
(p, h(
≤
t))
does not take into account the time
τ(p,h(
≤
t)
.
(12.4)
Here additional compression by one bit is worth as much as runtime reduction by a
factor of
t)
=
C
l
p,h(
t)
+
log
τ
p,h(
≤
≤
≤
1
2
. From an asymptotic optimality-oriented point of view this is a best way
of trading off storage and computation time (Levin
1973
, Schmidhuber
2004
).
In practical applications (Sect.
12.4
) the compressor/predictor of the continually
growing data typically will have to calculate its output online, that is, it will be
able to use only a constant number of computational instructions per second to pre-
dict/compress new data. The goal of the typically slower learning algorithm must
then be to improve the compressor such that it keeps operating online within those
time limits, while compressing/predicting better than before. The costs of comput-
ing
C
xry
(p, h(
≤
≤
t))
and similar performance measures are linear
in
t
, assuming
p
consumes equal amounts of computation time for each prediction.
Hence online evaluations of learning progress on the full history so far generally
cannot take place as frequently as the continually ongoing online predictions.
Some of the learning and its progress evaluations may take place during occa-
sional “sleep” phases (Schmidhuber
2006a
). But previous practical implementations
have looked only at parts of the history for efficiency reasons: The systems men-
tioned in Sect.
12.4
used online settings (one prediction per time step, and constant
computational effort per prediction), non-universal adaptive compressors or predic-
tors, and approximative evaluations of learning progress, each consuming only con-
stant time despite the continual growth of the history.
t))
and
C
l
(p, h(
12.3.1 Continuous Time Formulation
In continuous time,
O(t)
denotes the state of subjective observer
O
at time
t
.The
subjective compressibility (simplicity or regularity)
B(D,O(t))
of a sequence of
observations and/or actions is the negative number of bits required to encode
D
,
given
O(t)
's current limited prior knowledge and limited compression/prediction
method. The time-dependent and observer-dependent subjective
interestingness
or
surprise
or
aesthetic value
,
I(D,O(t))
is
I
D,O(t)
∼
∂B(D, O(t))
∂t
,
(12.5)
the
first derivative
of subjective simplicity: as
O
improves its compression algo-
rithm, formerly apparently random data parts become subjectively more regular and
beautiful, requiring fewer bits for their encoding.
There are at least two ways of having “fun”: execute a learning algorithm that
improves the compression of the already known data (in online settings, without
increasing computational needs of the compressor/predictor), or execute actions that
generate more data, then learn to better compress or explain this new data.
