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

The key of the proof of this result is to show that the Greedy Algorithm is
equivalent to a greedy 4-approximation algorithm for pipelined set-cover. We refer
the interested reader to the demonstration made by Munagala and Ali in [ 4 ] and
let him show that our problem setting is equivalent to the one formulated in their
problem.

3.3 Joint Order and Operating Point Selection

Further system performance can be achieved by both optimizing the order of the
chain of classifiers and the operating point configuration.
To build a joint order and operating point selection strategy, we propose to
combine the SQP-based solution for operating point selection with the iterative
Greedy order selection. This iterative approach, or SQP-Greedy algorithm, is
summarized as follows:

Centralized Algorithm 2 SQP-Greedy algorithm for joint ordering and operating
point selection
•

Initialize σ ( 0 ) .

• Repeat until greedy algorithm does not modify order.

1. Given order σ ( j ) , compute locally optimal x ( j ) through SQP.

2. Given operating points x ( j ) , update order σ ( j + 1 ) using (A-)Greedy algorithm.

Each step of the SQP-Greedy algorithm is guaranteed to improve the global
utility of the problem. Given a maximum bounded utility, the algorithm is then
guaranteed to converge. However, it may be difficult to bound the performance gap
between the SQP-Greedy and the optimal algorithm with a constant factor, since
the SQP only achieves local optima. As a whole, identification and optimization of
algorithms used to compute optimal order and operating points represents a major
roadblock to stream mining optimization.

3.3.1 Limits of Centralized Algorithms for Order Selection

We want to underline that updating the ex-post selectivities requires strong coordina-
tion between classifiers. A first solution would be for classifiers to send their choice
of operating point p F p D to a central agent (w hic h would also have knowledge

about the a-priori conditional selectivities

( , )

φ σ ) and would compute the ex-
post conditional selectivities. A second solution would be for each classifier C i
to send their rates t i and g i to the classifiers C j which have not yet processed the
stream for them to compute

φ σ ,

j . In both cases, heavy message exchange is required,
which can lead to system inefficiency (cf. Sect. 4.1 ) . We will propose in Sect. 4
a decentralized solution with limited message exchanges, as an alternative to this
centralized approach.

ψ