This thesis addresses the design of distributed scalar quantizers (DSQs) for two sensors,
tailored to maximize the classification accuracy for a pre-trained binary linear classifier
at the central node, diverging from traditional designs that prioritize data reconstruction
quality.
The first contribution of this thesis is the development of efficient globally optimal
DSQ design algorithms for two correlated discrete sources when the quantizer cells are
assumed to be convex. First, it is shown that the problem is equivalent to a minimum
weight path problem (with certain constraints) in a weighted directed acyclic graph.
The latter problem can be solved using dynamic programming with O(K_1K_2M^4) computational
complexity, where Ki, is the number of cells for the quantizer of source i,
i = 1, 2, and M is the size of the union of the sources’ alphabets. Additionally, it is
proved that the dynamic programming algorithm can be expedited by a factor of M by
exploiting the so called Monge property, for scenarios where the pre-trained classifier is
the optimal classifier for the unquantized sources.
Next, the design of so-called staggered DSQs (SDSQs) is addressed, i.e., DSQ’s with
K_1 = K_2 = K and with the thresholds of the two quantizers being interleaved. First, a
faster dynamic programming algorithm with only O(KM^2) time complexity is devised
for the design of the SDSQ that minimizes an upperbound on the classification error.
This sped up is obtained by simplifying the graph model for the problem. Moreover,
it is shown that this algorithm can also be further accelerated by a factor of M when
the pre-trained linear classifier is the optimal classifier. Furthermore, some theoretical
results are derived that provide support to imposing the above constraints to the DSQ
design problem in the case when the pre-trained classifier is optimal. First, it is shown
that when the sources (discrete or continuous) satisfy a certain symmetry property, the
SDSQ that minimizes the modified cost also minimizes the original cost within the class
of DSQs without the staggerness constraint. For continuous sources, it is also shown
that the SDSQ that minimizes the modified cost also minimizes the original cost and all
quantizer thresholds are distinct, even if the sources do not satisfy the aforementioned
symmetry condition. The latter result implies that DSQs with identical encoders are
not optimal even when the sources has the same marginal distribution, a fact which is
proved here for the first time, up to our knowledge.
The last (but not least) contribution of this thesis resides in leveraging the aforementioned
results to obtain efficient globally optimal solution algorithms for the problem
of decentralized detection under the probability of error criterion of two discrete vector
sources that are conditionally independent given any class label. The previously
known globally optimal solution has O(N^(K_1+K_2+1)) time complexity, where N is the
size of the union of the alphabets of the two sources. We show that by applying an
appropriate transformation to each vector source, the problem reduces to the problem
of designing the optimal DSQ with convex cells in the transformed scalar domain for
a scenario where the pre-trained linear classifier is the optimal classifier. We conclude
that the problem can be solved by a much faster algorithm with only O(K_1K_2N^3) time
complexity. Similarly, for the case of equal quantizer rates, the problem can be solved
in O(KN) operations if the sources satisfy an additional symmetry condition. Furthermore,
our results prove the conjecture that for continuous sources, imposing the
constraint that the encoders be identical precludes optimality, even when the marginal
distributions of the sources are the same. / Thesis / Doctor of Philosophy (PhD)
| Identifer | oai:union.ndltd.org:mcmaster.ca/oai:macsphere.mcmaster.ca:11375/30409 |
| Date | 11 1900 |
| Creators | Zendehboodi, Sara |
| Contributors | Dumitrescu, Sorina, Electrical and Computer Engineering |
| Source Sets | McMaster University |
| Language | English |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0016 seconds