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

uniform search: 1.) As a consequence, the time required to reach the optimal

solution might be infinitely long, since the optimal order could be experimented
after an infinitely large number of iterations.

ε t =

￿ General Approach : This slow convergence can be explained by the fact that

Safe Experimentation, as a model-free approach, does not leverage the structure
of the problem studied. In particular, one major constraint fixed by Safe Exper-
imentation is to try only one classifier among all its children, while the stream
mining optimization problem allows to probe multiple children simultaneously

by requesting their utility parameters vw and selecting the trusted child based
on these fed back values. This capacity to try multiple orders per iterations will
enable to build a parameterized algorithm to speed-up the convergence to optimal
order by choosing screening probabilities p i j appropriately.

4.5 Parametric Partial Search Order and Operating Point

Selection Algorithm

As expressed in ( 12 ) , the screening probabilities p i j can be used to tradeoff the
expected utility and the computational cost. In this final section, we frame a general
methodology aiming to determine the optimal tradeoff. In order to be adaptable
to the setting considered, we construct our learning algorithm in three steps, each
step representing a certain granularity level, and each step being controllable
by one “macroscopic” state variable. Doing so, we put forward three tradeoffs
corresponding to three independent questions: (a) how much to search? (b) how
deep to search? (c) where to search?
This enables the construction of a parametric learning algorithm, extensively
detailed in [ 11 ] . This article shows that the probability p i j ( that the h th

p , ξ , β )

classifier C σ ( h ) = C i probes its children C j , given that it received data with

throughput-to-goodput ratio θ i ∈ S k can be expressed as:

C e β U i ( j , k )

∑
C l ∈ Children ( C i )

p i j (

p , ξ , β )=

howmuch ? ×

p × .

h − [ Np ]
ξ
howdeep ?

e β U i ( l , k )

e −

+

1

where ?

The reader will find a justification of the formalism of p i j in [ 11 ] .

4.5.1 Controlling the Screening Probability

Using this expression of p i j is meant to be able to control key characteristics of the
screening probability by tuning parameters p ,

ξ and β .