Finding It Now: Construction and Configuration of Networked Classifiers in Real-Time Stream Mining Systems - Signal Processing Systems - page 124

In case of joint ordering and operating point selection, there exist multiple
equilibrium points, each corresponding to a local minimum of the utility function.
The selection of the equilibrium point among the set of possible equilibria depends
on the initial condition (i.e. order and operating points) of the algorithm. To select
the best equilibrium, we can perform the Partial Search Algorithm for multiple
initial conditions and keep only the solution which yielded the maximum utility.
In practice, stable stream conditions will not be verified by the stream mining
system, since the system's characteristics vary at a time scale of

dyn . Hence, rather
than achieving convergence, we would like the Partial Search Algorithm to reach
near-equilibrium fast enough for the system to deliver solution to the accuracy and
delay joint optimization on a timely basis.
In analogy to [ 13 ] , we first discuss how model-free Safe Experimentation, a
heuristic case of Partial Search Algorithm can be used for decentralized stream
mining and leads to a low-complexity algorithm, however with slow convergence
rate. Fortunately, the convergence speed of the Partial Search Algorithm can be
improved by appropriately selecting the screening probabilities p i j . In Sect. 4.5 , we
will construct a model-based algorithm which enables to control the convergence
properties of the Partial Search Algorithm, and lead to faster convergence.

τ

4.4 Multi-agent Learning in Decentralized Algorithm

We aim to construct an algorithm which would maximize as fast as possible
the global utility of the stream mining system expressed in Eq. ( 4 ) . We want to
determine whether it is worthwhile for a classifier C i to probe a child classifier C j
for its utility parameters and determine search probabilities p i j of the Partial Search
Algorithm accordingly.

4.4.1 Tradeoff between Efficiency and Computational Time

Define an experiment E i → j as classifier C i 's action of probing a child classifier C j

by requesting its utility parameter v j w j . Performing an experiment can lead to a
higher utility, but will induce a cost in terms of computational time:

U

￿ the expected additional utility achieved by the stream

mining system if the experiment E i → j is performed under state s k .
￿Let

Denote by ( E i → j | s k )

ex represent the expected amount of time required to perform an experiment.
This computational time will be assumed independent of the classifiers involved
in the experiment performed and the state observed.
Then, the total expected utility per iteration is given by U

τ

U

p i j )= ∑ p i j

( ( E i → j | s k )

p i )= p i j ) τ

ex ,where n

p i j )

and the time required for one iteration is represents

the expected number of experiments performed in one iteration of the Partial Search
Algorithm and will be defined precisely in the next paragraph.

τ ( n ( (