文章基本信息

标题：Computing Approximate Statistical Discrepancy
本地全文：下载
作者：Michael Matheny ; Jeff M. Phillips
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：123
页码：1-13
DOI：10.4230/LIPIcs.ISAAC.2018.32
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Consider a geometric range space (X,A) where X is comprised of the union of a red set R and blue set B. Let Phi(A) define the absolute difference between the fraction of red and fraction of blue points which fall in the range A. The maximum discrepancy range A^* = arg max_{A in (X,A)} Phi(A). Our goal is to find some A^ in (X,A) such that Phi(A^*) - Phi(A^) <= epsilon. We develop general algorithms for this approximation problem for range spaces with bounded VC-dimension, as well as significant improvements for specific geometric range spaces defined by balls, halfspaces, and axis-aligned rectangles. This problem has direct applications in discrepancy evaluation and classification, and we also show an improved reduction to a class of problems in spatial scan statistics.
关键词：Scan Statistics; Discrepancy; Rectangles