博弈论视角的序贯非参数检验方法

版权申诉

122 浏览量更新于2024-07-06 收藏 5.28MB PDF 举报

"这篇文档是关于序贯非参数单样本和双样本检验的博弈论公式，作者是Shubhanshu Shekhar和Aaditya Ramdas，来自卡耐基梅隆大学的统计与数据科学及机器学习部门。文章探讨了在非参数背景下设计一致性的序贯单样本和双样本检验方法，主要采用测试如赌博的原理来构建这些测试。" 正文: 在统计学中，序贯检验是一种不断收集数据直至作出决策的统计分析方法，尤其适用于有限的样本资源或时间限制的情况。而非参数检验则不依赖于数据分布的具体形式，只基于数据的顺序关系或某些特征进行分析。本文档"Game-theoretic Formulations of Sequential Nonparametric One- and Two-Sample Tests"深入研究了如何在非参数环境中通过博弈论的视角设计这样的检验。作者引入了“测试如赌博”的原则，将构建序贯测试的问题转化为选择能最大化虚拟赌徒财富的支付函数（payoff functions）的过程。在这个框架下，赌徒在一系列游戏中与零假设（null hypothesis）对赌。当赌徒的财富过程超过特定阈值时，测试会拒绝零假设。这种方法确保了以下两点： 1. 在零假设下，财富过程是一个非负鞅（martingale），从而可以严格控制第一类错误（type-I error），即假阳性率。非负鞅性质保证了在没有证据反对零假设的情况下，赌徒的财富不会无理由地增加。 2. 支付函数被设计为与一些统计距离度量的变分表示相关的见证函数（witness function）的可预测估计，例如积分概率度量（IPMs）和φ-散度。这些度量通常用于衡量两个概率分布之间的差异。通过这种方式，测试的敏感性得到保证，能够在数据中检测到与零假设相矛盾的显著差异。 IPMs和φ-散度是一类广义的距离度量，它们在机器学习和统计推断中有着广泛应用。IPMs衡量的是一个概率分布与另一分布集合之间的最大偏差，而φ-散度则包括了诸如Kullback-Leibler散度、Hellinger距离等经典度量。通过选择这些度量作为见证函数，序贯检验能够捕捉到不同分布间的细微差异。总体来说，这篇文章提出的策略提供了一种创新的方法来构造非参数的序贯检验，它不仅保证了检验的统计功效，还通过博弈论的视角赋予了问题直观的解释。这种将统计决策与经济决策模型相结合的方法，可能为未来的研究开辟新的途径，特别是在处理复杂或未知分布的数据集时。

on the alternative, not satisﬁed under the general setting considered in this paper. For instance, Savage and

Sethuraman (1966) presented a sequential rank test with Lehmann alternatives, where one of the distribution

functions is a speciﬁed power of the other. For a more detailed discussion of early works in sequential

nonparametric testing, see (Ghosh and Sen 1991, Chapter 14, § 2). More related to our paper, are the

works such as (Darling and Robbins 1968; Howard and Ramdas 2022; Balsubramani and Ramdas 2016;

Lh´eritier and Cazals 2018; Manole and Ramdas 2021) that do not make strong simplifying assumptions on

the alternative, and we discuss them in more details below.

Darling and Robbins (1968) considered several nonparametric one- and two-sample testing problems

involving real-valued observations, and proposed sequential tests by combining ﬁxed sample-size uniform

deviation inequalities for the empirical distribution function with a union bound over time. Howard and

Ramdas (2022) proposed a sequential Kolmogorov-Smirnov (KS) test by obtaining a tighter time-uniform

deviation inequality for the empirical distribution functions. They followed a diﬀerent approach than Darling

and Robbins (1968), and used an inequality from the empirical process theory along with the peeling technique

of dividing the set of natural numbers into disjoint intervals of exponentially increasing lengths. However,

the sequential tests from both these works only work with real-valued observations (or more generally,

observations in a totally ordered space) and cannot be applied in problems involving multivariate observations

or observations in a discrete unordered set. The other tests discussed below address this issue.

Balsubramani and Ramdas (2016) derived a time-uniform empirical Bernstein inequality for random

walks by building upon an earlier time-uniform martingale inequality of Balsubramani (2014). Using this

result, they proposed a sequential nonparametric two-sample test by employing the linear-time kernel-MMD

as the test statistic, and obtained theoretical guarantees on its power and expected stopping time. The

original batch two-sample kernel-MMD test, proposed by Gretton, Borgwardt, Rasch, Sch¨olkopf, and Smola

(2012), uses a quadratic-time U-statistic as an empirical estimate of the squared MMD distance. The re-

liance of the sequential test of Balsubramani and Ramdas (2016) on the linear-time MMD statistic, while

making the test computationally more eﬃcient, also makes it less powerful than our proposed kernel-MMD

test (in Section 5.2) and the tests of Lh´eritier and Cazals (2018) and Manole and Ramdas (2021) discussed

below. Figure 6 in Appendix E empirically shows the signiﬁcant diﬀerence in the powers of the test of Bal-

subramani and Ramdas (2016) and our sequential kernel-MMD test.

Lh´eritier and Cazals (2018) proposed a general approach to designing sequential nonparametric two-

sample tests, by using sequentially learned probabilistic predictors of the labels indicating the population

from which an observation was drawn. The authors identiﬁed suﬃcient conditions for the λ-consistency (a

weaker notion of consistency, that informally requires the distributions to be well separated in terms of

mutual information) of the resulting sequential test, and show that these conditions are satisﬁed when the

predictors employed in deﬁning the test are strongly pointwise consistent (Gy¨orﬁ, Kohler, Krzy˙zak, and Walk

2002, Deﬁnition 25.1). Compared to Lh´eritier and Cazals (2018), our proposed approach leads to sequential

tests with stronger performance guarantees. In particular, in Proposition 4, we identify suﬃcient conditions

for our tests to be consistent (in the usual sense) and in Proposition 6, we identify suﬃcient conditions under

which the type-II error of our tests decays at an exponential rate.

Manole and Ramdas (2021) propose a general technique for constructing conﬁdence sequences for convex

divergences between two probability distributions. Their approach relies on the key observation that the em-

pirical divergence process is a reverse submartingale adapted to the exchangeable ﬁltration. By instantiating

the general conﬁdence sequence for the special cases of the Kolmogorov-Smirnov metric (Manole and Ram-

das 2021, § 4.1) and kernel-MMD distance (Manole and Ramdas 2021, § 4.2), the authors obtain consistent

sequential nonparametric two-sample tests for both univariate and multivariate distributions. Unlike Manole

and Ramdas (2021), our approach relies on constructing martingales (instead of reverse submartingales) from

statistical distances with a variational deﬁnition. Hence, our resulting sequential tests are expected to be less

conservative than those of Manole and Ramdas (2021) in rejecting the null. This intuition is veriﬁed in some

numerical experiments in Section 5.2.2, where the stopping times, under the alternative, of our proposed

test are signiﬁcantly smaller than those of Manole and Ramdas (2021).

2 Preliminaries

Our work is based on ideas drawn from diﬀerent, seemingly unrelated, research areas. In this section, we

recall (and in some cases, adapt) the key results and concepts from these diﬀerent ﬁelds that will be used in

designing our sequential tests.

2.1 Betting Strategies

In this paper, we will use a betting strategy, that we refer to as the mixture-method, based on the approach

used in the universal portfolio optimization algorithm of Cover (1991). The main idea is as follows: consider

the continuum of constant betting strategies that result in a wealth process {K

: t ≥ 1} for every λ ∈ [−1, 1].

If our goal is to perform as well as the best constant betting strategy in hindsight, we can distribute our

initial wealth (K

) among this continuum of constant betting strategies according to some distribution ν on

[−1, 1]. Since the best constant strategy in hindsight after n rounds, say λ

∗

, does exponentially better than

strategies strictly bounded away from λ

∗

, the average wealth is dominated by this term. This statement is

made precise in Proposition 1. First, we formally deﬁne the mixture-method.

Deﬁnition 5 (Mixture-method). The wealth process for the mixture-method of betting with probability

density ν on [−1, 1] and an initial wealth K

−1

ν(λ)dλ, where K

= K

t=1

(1 + λf

)) .

Under mild conditions on the mixture distribution ν, we can show that the resulting wealth process grows

nearly as fast as the best constant betting strategy in hindsight.

Proposition 1. Suppose the mixture density satisﬁes ν(λ) ≥ c

for all λ ∈ [−1, 1] for some c

> 0. Then

for any λ

max

∈ (−1, 1) and ∆λ < 1 − λ

max

and {f

: t ≥ 1} with f

(x) ≥ −1 for all x, the wealth resulting

from the mixture-method betting strategy after n rounds satisﬁes:

≥ exp

max

λ∈[−λ

max

,λ

max

]

t=1

log(1 + λf

))

−

n∆λ

1 − λ

max

− ∆λ

− log



∆λ



. (2)

In particular, by setting λ

max

= 1/2 and ∆λ = 1/n for n ≥ 4, we get

≥ exp





t=1

)

− 4 − log(n/c

)





= exp





t=1

)

− o(n)





. (3)

The proof of this statement is in Appendix B.1, and it follows from two observations: (i) for any

λ ∈ (0, 1),

the mapping x 7→ log(1 + x) with x ∈ [−

λ,

λ] is 1/(1 −

λ)-Lipschitz, and (ii) ν assigns a measure of at least

∆λ to any interval of length ∆λ containing the best constant bet. These two facts account for the second

and third terms inside the exponent in (2).

Remark 6. In the practical implementation of the mixture-method, we replace the integral with a sum over

values of λ in a ﬁnite uniform grid of points from −1 to 1, with the end points excluded, and use the uniform

distribution as the prior ν.

Remark 7. We note that there exist other betting strategies, such as potential-based strategies of Orabona

and Pal (2016) or the Online Newton Step (ONS) strategy of Cutkosky and Orabona (2018), that can

also be used in designing our tests. These methods can also guarantee results similar to those stated

in Proposition 1 (in fact, with better constants in the o(n) term). However, we restrict our attention to the

mixture strategy of Deﬁnition 5 due to its simplicity, and the fact that in some preliminary comparisons the

mixture-method outperformed the potential-based and ONS strategies, especially over shorter horizons. We

leave a more thorough investigation of the eﬀects of diﬀerent betting schemes to future work.

2.2 Nonnegative Martingales and Ville’s Inequality

As we saw in Example 1, if Forecaster’s claim is true, then it is unlikely that Skeptic’s wealth can be

multiplied by a large factor using any strategy. This intuition can be made formal by observing that for any

valid sequence of payoﬀ functions, the wealth process {K

: t ≥ 0} is a nonnegative martingale if Forecaster’s

claim is true (that is when the null hypothesis is true). Speciﬁcally, for the wealth process corresponding to

payoﬀ functions {f

: t ≥ 1} and using the mixture-method for betting, we have the following under the null:

E [K

t−1

] = E



t−1

(1 + λf

)) ν(λ)dλ|F

t−1



t−1

E [1 + λf

)|F

t−1

] ν(λ)dλ (4)

t−1

ν(λ)dλ = K

t−1

. (5)

The interchange of conditional expectation and integral to obtain (4) is justiﬁed by appealing to the condi-

tional monotone convergence theorem, while (5) follows from the deﬁning condition of a valid payoﬀ function.

We now state a time-uniform inequality for nonnegative supermartingales, which implies that it is unlikely

for the wealth process to take large values under the null hypothesis.

Fact 1 (Ville’s Inequality). Suppose {K

: t ≥ 0} is a nonnegative supermartingale process adapted to a

ﬁltration {F

: t ≥ 0}. Then, we have the following for any a > 0:

P (∃t ≥ 1 : K

≥ a) ≤

E[K

]

This fact implies that for a given level α, any wealth process constructed using a valid sequence of payoﬀ

functions will stay below the threshold 1/α with probability at least 1 − α.

In the next subsection, we state some results about the asymptotic rate at which the optimal type-II

error converges to zero in the non-sequential setting.

2.3 Optimal Error Exponent in Hypothesis Testing

For simple binary hypothesis tests, the following result (Cover and Thomas 2006, Theorem 11.8.3) charac-

terizes the rate at which the probability of type-II error of the optimal level-α vanishes asymptotically.

Fact 2 (Chernoﬀ-Stein Lemma). Given n i.i.d. the observations Y

, . . . , Y

, consider the problem of testing

: Y

∼ P versus H

: Y

∼ Q for known distributions P and Q with 0 < d

(P, Q) < ∞. For a ﬁxed

α ∈ (0, 1), let β

∗

denote the type-II error for the optimal level-α test (i.e., the level-α test, with the smallest

type-II error). Then we have,

lim

n→∞

−

log β

∗

= d

(P, Q).

剩余55页未读，继续阅读

易小侠

粉丝: 6632
资源: 9万+

博弈论视角的序贯非参数检验方法

无悔学习算法：博弈论与纳什均衡的探索

控制流劫持攻击的博弈论视角：对抗鲁棒性的统一解析

5G mMTC的博弈优化：服务质量保证下的通信协议

基于数据驱动的博弈论模型预测控制_Game-Theoretic Model Predictive Control with Da

对抗鲁棒性的统一弈论解释_A Unified Game-Theoretic Interpretation of Adversa

A-Double-Auction-Based-Game-Theoretic-Approach

多主体系统：算法，博弈论和逻辑基础Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations

A game-theoretic framework for landmark-based image segmentation

Game-Theoretic Optimization for Machine-Type Communications Under QoS Guarantee

Game-theoretic Resource Allocation Methods for.rar_d2d_d2d commu

最新资源