مقاله آزمایش توزیع با یک کلکتور مغشوش

چکیده

We are interested in testing properties of distributions with systematically mislabeled samples. Our goal is to make decisions about unknown probability distributions, using a sample that has been collected by a confused collector, such as a machine-learning classifier that has not learned to distinguish all elements of the domain. The confused collector holds an unknown clustering of the domain and an input distribution $μ$, and provides two oracles: a sample oracle which produces a sample from $μ$ that has been labeled according to the clustering; and a label-query oracle which returns the label of a query point $x$ according to the clustering. Our first set of results shows that identity, uniformity, and equivalence of distributions can be tested efficiently, under the earth-mover distance, with remarkably weak conditions on the confused collector, even when the unknown clustering is adversarial. This requires defining a variant of the distribution testing task (inspired by the recent testable learning framework of Rubinfeld & Vasilyan), where the algorithm should test a joint property of the distribution and its clustering. As an example, we get efficient testers when the distribution tester is allowed to reject if it detects that the confused collector clustering is “far” from being a decision tree. The second set of results shows that we can sometimes do significantly better when the clustering is random instead of adversarial. For certain one-dimensional random clusterings, we show that uniformity can be tested under the TV distance using $\widetilde O\left(\frac{\sqrt n}{ρ^{3/2} ε^2}\right)$ samples and zero queries, where $ρ\in (0,1]$ controls the “resolution” of the clustering. We improve this to $O\left(\frac{\sqrt n}{ρε^2}\right)$ when queries are allowed.

چکیده به فارسی (ترجمه ماشینی)

ما علاقه مند به آزمایش خواص توزیع با نمونه های بطور منظم گمراه شده هستیم.هدف ما تصمیم گیری در مورد توزیع احتمال ناشناخته ، با استفاده از نمونه ای است که توسط یک جمع کننده سردرگم جمع آوری شده است ، مانند طبقه بندی کننده یادگیری ماشین که آموخته است که همه عناصر دامنه را متمایز کند.جمع کننده سردرگم یک خوشه بندی ناشناخته از دامنه و توزیع ورودی $ μ $ $ دارد و دو اوراکل را فراهم می کند: یک نمونه اوراکل که نمونه ای را از $ $ $ تولید می کند که مطابق با خوشه بندی برچسب گذاری شده است.و یک اوراکل برچسب برچسب که برچسب یک نقطه پرس و جو $ x $ را مطابق با خوشه بندی باز می گرداند.اولین مجموعه از نتایج ما نشان می دهد که هویت ، یکنواختی و هم ارزی توزیع ها می توانند به طور مؤثر ، در فاصله زمین-حرکت ، با شرایط قابل ملاحظه ای ضعیف بر روی جمع کننده سردرگم ، آزمایش شوند ، حتی اگر خوشه بندی ناشناخته مخالف باشد.این امر مستلزم تعریف نوع از کار تست توزیع (با الهام از چارچوب یادگیری قابل آزمایش اخیر Rubinfeld & Vasilyan) است ، جایی که الگوریتم باید یک خاصیت مشترک توزیع و خوشه بندی آن را آزمایش کند.به عنوان نمونه ، وقتی آزمایش کننده توزیع اجازه می دهد رد شود اگر تشخیص دهد که خوشه بندی جمع کننده سردرگم “از یک درخت تصمیم گیری” دور است ، آزمایش کنندگان کارآمد می گیریم.مجموعه دوم نتایج نشان می دهد که ما گاهی اوقات می توانیم به طور قابل توجهی بهتر عمل کنیم وقتی خوشه بندی به جای مخالفان تصادفی باشد.برای برخی از خوشه های تصادفی یک بعدی ، ما نشان می دهیم که یکنواختی را می توان در فاصله تلویزیون با استفاده از $ wideTilde o سمت چپ ( frac { sqrt n} {ρ^{3/2} ε^2} راست) $ آزمایش کرد.نمونه ها و نمایش داده های صفر ، که در آن $ ρ in (0،1] $ “وضوح” خوشه بندی را کنترل می کند. ما این را به $ o سمت چپ ( frac { sqrt n} {ρε^2} Right) $ بهبود می بخشیم.هنگامی که نمایش داده شد مجاز است.