Optimal sequences improve measurements from broken or limited devices
Finding optimal measurement sequences for broken or constrained measuring devices
Information Theory
Summary
Sometimes, measuring devices don’t work perfectly because they are damaged or worn out. The authors found a way to get the best measurements from these imperfect devices by choosing the right series of measurement steps. They showed that picking the next measurement greedily (just based on immediate gain) is not the best way. Instead, their method uses a careful plan to avoid measurement results that cause problems, making the device provide better information overall. They also developed a new algorithm that is faster than traditional methods to find these best sequences.
What this means in practice
- •For device maintenance teams: Develop repair strategies that maximize data from devices with limited functionality by finding optimal measurement steps.
- •For quality control engineers: Improve accuracy of measurements when using partially damaged or constrained instruments by following optimized measurement sequences.
Authors
Peter N. Loxley
Abstract
Measuring devices do not always function perfectly due to fatigue, damage, or malfunction. When device repair or replacement is not possible, it becomes necessary to seek optimal measurements from a broken device. We show this is possible via a sequential decision making process where we optimize measurement sequences over the remaining available measurements using information theory. With dynamic programming, we show greedy measurement sequences are always suboptimal for a simple class of measurement constraints. Greedy measurement sequences generally lead to equiprobable measurement outcomes, while the optimal policy is found to select each measurement in such a way as to assign a low probability to any measurement outcome that triggers a constraint condition; leading to measurement outcomes that are not equiprobable. A measurement sequence generated under this policy is shown to decompress its source: that is, the expected number of measurement outcomes is strictly greater than the number of bits it encodes, defining a key property of constrained measurements. Dynamic programming is inefficient for finding optimal measurement sequences, so we develop an alternative algorithm related to optimal binary decision trees. By deriving upper and lower complexity bounds for the task, we propose this algorithm as an efficient means to find optimal measurements for a broken or constrained measuring device.