Study and Design of Globally Optimal Distributed Scalar Quantizer for Binary Linear Classification

Abstract

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.