Digital Signal Processing Reference
In-Depth Information
Fig. 11
Feedback information for Decentralized Algorithms
4.3.1
Exhaustive Search Ordering Algorithm
We will say that a classifier
C
i
probes
a child classifier
C
j
when it requests its child
utility parameters
v
j
w
j
.
To best determine its trusted child, a classifier only requires knowledge on the
utility parameters of all its children. We can therefore build a recursive algorithm
as follows: all classifiers are probed by the source classifier
C
0
; to compute their
local utility, each of the probed classifiers then probes its children for their utility
parameters
vw
. To determine these, each of the probed children needs to probe
its own children for their utility parameter, etc. The local utilities are computed in
backwards order, from leaf classifiers to the root classifier
C
0
. The order yielding
the maximal utility is selected.
Observe that this decentralized ordering algorithm leads to a full exploration
of all
N
! possible orders at each iteration. Achieving the optimal order only
requires one iteration, but this iteration requires
O
(
)
operations and may thus
For quasi-stationary input data, the ordering could be performed offline and
such computational time requirement would not affect the system's performance.
However, in bursty and heterogeneous settings, we have to ensure that the optimal
order calculated by the algorithm would not arrive too late and thus be completely
obsolete. In particular, the time constraint
N
!
dyn
, defined in Sect.
4.1
must not
τ
≤
C
τ
be violated.
We therefore need algorithms capable of quickly determining a good order,
though convergence may require more than one iteration. In this way, it will be
possible to reassess the order of classifiers on a regular basis to adapt to the
environment.
6
This can take
τ
>
5 min for seven classifiers.
