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

4.2.4 Local Utility of a Classifier

We define the local utility of a chain of classifiers by backward induction:
U σ ( h ) = − ρ σ ( h ) t h − 1 +

U σ ( N ) = − ρ σ ( N ) t N − 1 + g N − Kt N . U σ ( h + 1 ) and (9)

The end-to-end utility of the chain of classifiers can then be reduced to U = U σ ( 1 ) .

4.2.5 Decision Taking

The key result of this section consists in the fact that the global optimum can be
achieved locally with limited information. Indeed, each classifier C i = C σ ( h ) will

globally maximize the system's utility by autonomously maximizing its local utility

t h − 1
g h − 1

where the local utility parameters v h

= v h w h
=[

w h are defined

U i

v i w i ]

recursively:

0

v N w N = −

+

K 1 T N ρ σ ( N ) −

0 + v h + 1 w h + 1 T h .

This proposition can easily be proven recursively.
Therefore, the local utility of classifier C i can now be rewritten as
U i = −

v h w h = −

ρ σ ( h )

x i ) t h − 1
g h − 1

ρ i 0 + v h + 1 w h + 1 T i (

. (10)

As such, the decision of classifier C i only depends on its operating point x i ,on
the state

and on the local utility parameters v j w j of its θ i which it observe s 5

children classifiers C j ∈ . Once it knows the utility parameters of all its

children, classifier C i can then uniquely determine its best action (i.e. its operating
point x i and its trusted child C i → ) in order to maximize its local utility.

Children ( C i )

4.3 Decentralized Algorithms

At this stage, we consider classifiers with fixed operating points. The action of a
classifier C i is therefore limited to selecting the trusted child C i → ∈ Children ( C i ) to

which it will forward the stream.

g i − 1 = − ρ i 0 +

U i

5 t i − 1

and g i − 1 are not required since: argmax U i = argmax

v i + 1 w i + 1 T i θ i
1

.