Approximate Positively Correlated Distributions and Approximation Algorithms for D-optimal Design
Approximate Positively Correlated Distributions and Approximation Algorithms for D-optimal Design
复制标题
D 最优设计的近似正相关分布和近似算法
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Weijun Xie
中科院分区：
文献类型：
--
作者：
Mohit Singh;Weijun Xie
实验设计是统计学的一个经典领域[21]，也发现了机器学习中的新应用[2]。在每个测量中引入的目标是从给定的N实验中挑选K，以使未知参数的最精确估计。可能会通过最小二乘计算来获得X'的可能性估计。估计误差x - x'的置信椭圆形会导致两个自然变体，具体取决于是否允许实验的重复。在传感器的地理位置中，我们还发现了应用程序[19]。在有或没有重复的情况下，D-最佳设计问题给出了问题的第一个常数因子近似。如果允许重复时[等式]，并且如果不允许重复进行重复时，则可以得到（1-ϵ） - approximation，并且显示一个尺寸M远大得多。
Experimental design is a classical area in statistics [21] and has also found new applications in machine learning[2]. In the combinatorial experimental design problem, the aim is to estimate an unknown m-dimensional vector x from linear measurements where a Gaussian noise is introduced in each measurement. The goal is to pick k out of the given n experiments so as to make the most accurate estimate of the unknown parameter x. Given a set S of chosen experiments, the most likelihood estimate x' can be obtained by a least squares computation. One of the robust measures of error estimation is the D-optimality criterion [27] which aims to minimize the generalized variance of the estimator. This corresponds to minimizing the volume of the standard confidence ellipsoid for the estimation error x − x'. The problem gives rise to two natural variants depending on whether repetitions of experiments is allowed or not. The latter variant, while being more general, has also found applications in geographical location of sensors [19]. We show a close connection between approximation algorithms for the D-optimal design problem and constructions of approximately m-wise positively correlated distributions. This connection allows us to obtain a [EQUATION]-approximation for the D-optimal design problem with and without repetitions giving the first constant factor approximation for the problem. We then consider the case when the number of experiments chosen is much larger than the dimension m and show one can obtain (1 − ϵ)-approximation if [EQUATION] when repetitions are allowed and if [EQUATION] when no repetitions are allowed improving on previous work.