5D Library › 未知地形中的贝叶斯搜索、秘书问题与吉廷斯指数 · English

第三章 贝叶斯搜索:往哪里找,没找到又说明了什么

从反潜到搜索论

第二次世界大战期间,美国海军反潜作战研究小组的数学家库普曼研究怎样用有限的飞机与舰艇在大片海域中发现潜艇。他在战后把这些工作整理成三篇《搜索论》,发表在 1956—1957 年的《运筹学》上:第一篇讨论搜索者与目标的相对运动,第二篇讨论发现概率,第三篇讨论在已知目标位置分布时,怎样分配有限的搜索努力,使发现的概率最大 (Koopman 1956, 1957)。斯通 1975 年的《最优搜索理论》系统总结了这一领域 (Stone 1975)。

搜索论有三个基本要素。第一是先验:目标可能在哪里,各处的概率是多少。第二是发现函数:如果目标确实在某处,在那里投入一定的搜索努力,发现它的概率是多少;在海底地形复杂、水深大或天气恶劣的地方,同样的努力发现的概率更低。第三是更新:搜过某处而没有发现,并不说明目标不在那里,只是降低了它在那里的概率,同时提高了其他地方的概率。

推导

把搜索区域分成格子,pcp_c 为目标在格子 cc 中的概率,dcd_c 为目标若在 cc 中、搜一次 cc 就发现它的概率。搜 cc 一次而没有发现,按贝叶斯公式: pc′=pc(1−dc)1−pcdc,pk′=pk1−pcdc(k≠c).p_c' = \frac{p_c(1-d_c)}{1-p_c d_c}, \qquad p_k' = \frac{p_k}{1-p_c d_c}\quad (k \ne c). 这一次搜索发现目标的概率是 pcdcp_c d_c。所以「下一次搜哪里」的贪婪规则是:选 pcdcp_c d_c 最大的格子。对于每次只搜一格、每格的发现概率固定的离散搜索问题,可以证明这条规则使期望搜索次数最小 (Stone 1975)。

这条规则有两层含义。一是「先搜最可能的地方」不总是对的:一个概率较高但很难搜的格子,可能不如一个概率稍低但容易搜的格子。二是没有发现也是信息:每一次失败的搜索都会把概率从容易搜的地方推向难搜的地方,所以按规则搜下去,搜索会自动转向那些「搜过但没搜干净」的区域。

在网格上搜索

推导

一片虚构的 20×2020 \times 20 海域。先验混合三种情景,这是实际搜索规划中常用的做法:在最后已知位置周围 8 格内均匀分布(权重 0.35),以最后已知位置为中心的正态分布(0.35),以由漂流反推出的位置为中心的正态分布(0.30)。平坦海底的发现概率为 0.8,东侧与一条海岭的崎岖海底为 0.4。每天搜 10 次。比较三种计划:(A)每次搜 pcdcp_c d_c 最大的格子;(B)每次搜 pcp_c 最大的格子,不考虑发现概率;(C)从最后已知位置由近及远逐格扫过,不用先验。程序计算各计划到第 tt 天为止发现目标的概率(在先验下求期望)以及平均所需天数(截至第 120 天)。

# Bayesian search, invented 20 x 20 sea area, 10 looks a day; prior and detection
# probabilities as in the text. Plans: (A) largest p_c d_c; (B) largest p_c; (C) sweep.
import math

N, LKP, DRIFT, LOOKS = 20, (8, 10), (12, 7), 10
CELLS = [(x, y) for x in range(N) for y in range(N)]

def prior():
    inside = [c for c in CELLS if math.dist(c, LKP) <= 8]
    p = {c: 0.0 for c in CELLS}
    for w, m, s in ((0.35, LKP, None), (0.35, LKP, 3.0), (0.30, DRIFT, 2.5)):
        part = {c: 1.0 if s is None else math.exp(-math.dist(c, m) ** 2 / (2 * s * s))
                for c in inside}
        tot = sum(part.values())
        for c, v in part.items():
            p[c] += w * v / tot
    return p

def detect(c):
    return 0.4 if c[0] >= 13 or abs(c[0] - c[1] - 2) <= 1 else 0.8

def update(p, c):                     # unsuccessful look at c (Bayes's rule)
    miss = 1 - p[c] * detect(c)
    for k in p:
        p[k] /= miss
    p[c] *= 1 - detect(c)
    return miss

def run(plan, days):
    p, found, curve, snaps, k = prior(), 0.0, [], {}, 0
    sweep = sorted((c for c in CELLS if math.dist(c, LKP) <= 8),
                   key=lambda c: (math.dist(c, LKP), c))
    for day in range(1, days + 1):
        for _ in range(LOOKS):
            if plan == "A":
                c = max(CELLS, key=lambda c: p[c] * detect(c))
            elif plan == "B":
                c = max(CELLS, key=lambda c: p[c])
            else:
                c = sweep[k % len(sweep)]; k += 1
            found += (1 - found) * (1 - update(p, c))
        curve.append(found)
        if day in (1, 5, 20):
            snaps[day] = dict(p)
    return curve, snaps

if __name__ == "__main__":
    p0 = prior(); top = sorted(p0.values(), reverse=True)
    print(f"prior: {sum(v > 0 for v in p0.values())} cells possible;"
          f" top 10 hold {sum(top[:10]):.3f}, top 50 hold {sum(top[:50]):.3f}")
    print("P(found by day t)            t=1     t=5    t=10    t=20    t=40   mean days")
    for plan, name in (("A", "A largest p x d"), ("B", "B largest p"), ("C", "C sweep")):
        curve, _ = run(plan, 120)
        cols = "".join(f"  {curve[t - 1]:.3f}" for t in (1, 5, 10, 20, 40))
        print(f"   {name:25s}{cols}   {sum(1 - f for f in curve) + 1:6.1f}")
    snaps = run("A", 20)[1]
    rough = lambda p: sum(v for k, v in p.items() if detect(k) < 0.5)
    print("plan A, no success: rough-cell mass after 0/1/5/20 days: " + " ".join(
        f"{rough(p):.3f}" for p in (p0, *snaps.values())))
    tops = [(max(CELLS, key=lambda c: p[c]), max(p.values())) for p in snaps.values()]
    print("   top cell after 1/5/20 days: " + ", ".join(f"{c} {v:.4f}" for c, v in tops))
# prior: 197 cells possible; top 10 hold 0.119, top 50 hold 0.473
# P(found by day t)            t=1     t=5    t=10    t=20    t=40   mean days
#    A largest p x d            0.088  0.311  0.484  0.694  0.892     17.5
#    B largest p                0.067  0.287  0.459  0.672  0.888     18.3
#    C sweep                    0.071  0.262  0.451  0.665  0.850     21.3
# plan A, no success: rough-cell mass after 0/1/5/20 days: 0.349 0.382 0.465 0.559
#    top cell after 1/5/20 days: (11, 8) 0.0139, (12, 9) 0.0158, (10, 7) 0.0136

先验中可能的格子有 197 个,概率最大的 10 个格子只占 0.119,50 个格子占 0.473:先验相当分散,没有一个计划能很快找到目标。按 pcdcp_c d_c 搜索的计划 A 第一天的发现概率为 0.088,十天 0.484,四十天 0.892,平均需要 17.5 天;只看 pcp_c 的计划 B 平均 18.3 天;不用先验、由近及远扫过的计划 C 平均 21.3 天,四十天时只有 0.850。这里的差别不算大,因为三种情景的先验都集中在最后已知位置附近,计划 C 的顺序碰巧与先验大致相符;先验越偏离搜索者的直觉(例如漂流使目标远离最后已知位置),不用先验的代价就越大。

程序最后一部分显示了「没有发现也是信息」:崎岖海底的格子在先验中占 0.349,按计划 A 搜了 1 天、5 天、20 天而没有发现后,分别升到 0.382、0.465 与 0.559。概率最大的格子也在移动,从靠近漂流反推点的 (11, 8) 移到 (12, 9),再移到 (10, 7)。

左:虚构海域的先验分布(叉为最后已知位置),中:按计划 A 搜了 5 天而没有发现后的后验分布,容易搜的中心区域颜色变浅;右:三种计划到第 t 天为止发现目标的概率。

「天蝎号」与法航 447

证据

「天蝎号」潜艇(1968)。 美国核潜艇「天蝎号」1968 年在大西洋失踪。理查森与斯通 1971 年报告了搜寻中的运筹分析:他们设想了九种失事情景,给每种情景一个可信度权重,用蒙特卡罗方法生成残骸位置的先验分布;搜寻过程中,他们按每次搜索的效果更新目标分布,指导下一步搜哪里。残骸最终在先验概率最高的格子 260 码之内被找到 (Richardson and Stone 1971)。斯通当时在亚速尔群岛附近现场做了约六周的分析。

证据

法航 447(2009—2011)。 2009 年 6 月 1 日,从里约热内卢飞往巴黎的法航 447 航班在大西洋上空的恶劣天气中失踪。此后两年的四个阶段——水面搜索、2009 年 6—7 月对水下定位信标的被动声学搜索、2009 年 8 月与 2010 年 4—5 月的侧扫声呐搜索——都没有找到残骸。法国事故调查局请斯通等人分析残骸的位置 (Stone et al. 2014)。他们以最后已知位置为中心、半径 40 海里的圆为范围,把三种分布混合成先验:圆内均匀分布、根据九起失控事故得出的标准差 8 海里的正态分布,以及根据打捞到的遇难者遗体反推漂流得到的分布,权重分别为 0.35、0.35 与 0.30;再按各阶段搜索的发现概率逐一更新。被动声学搜索的有效性取决于两个信标是否工作;由于对信标能否在撞击中幸存存在疑问,他们给出了一个「两个信标都失效」时的后验分布。2011 年的搜索从这个分布的中心开始,在约一周内找到了残骸,位置落在高概率区域内,而这一带此前已被被动声学搜索完整覆盖。事后发现,一个回收的信标接上充满电的电池也不发信号。作者写道,更好的做法是把信标是否失效与残骸位置放进同一个联合分布。

这个案例的教训不是「贝叶斯方法神奇地找到了残骸」,而是:对过去搜索效果的估计本身就是一个需要验证的假设。如果高估了过去搜索的发现概率,后验就会过早地把最可能的区域「排除」掉,之后的搜索都转向错误的地方。

推导

用同一片虚构海域演示这个教训。设之前的声学搜索覆盖了最后已知位置 4 格以内的区域,如果信标工作,发现概率为 0.9。三位规划者对「信标工作」的概率 ww 看法不同:完全相信之前的搜索(w=1w = 1),用联合模型(w=0.8w = 0.8),完全不理会之前的搜索(w=0w = 0)。各自用自己的后验按计划 A 搜索;真相分为「信标失效」与「信标工作」两种。数字是示意性的。

# An earlier search that was less effective than assumed (stylised after Stone et al.
# 2014; same invented grid and prior as p04). An acoustic search covered all cells within
# 4 of the last known position, detecting w.p. 0.9 IF the beacons work. Planners give
# "beacons work" probability w = 1, 0.8 (joint model) or 0 and then search by p x d.
import math

N, LKP, DRIFT, LOOKS = 20, (8, 10), (12, 7), 10
CELLS = [(x, y) for x in range(N) for y in range(N)]

def prior():
    inside = [c for c in CELLS if math.dist(c, LKP) <= 8]
    p = {c: 0.0 for c in CELLS}
    for w, m, s in ((0.35, LKP, None), (0.35, LKP, 3.0), (0.30, DRIFT, 2.5)):
        part = {c: 1.0 if s is None else math.exp(-math.dist(c, m) ** 2 / (2 * s * s))
                for c in inside}
        tot = sum(part.values())
        for c, v in part.items():
            p[c] += w * v / tot
    return p

def detect(c):
    return 0.4 if c[0] >= 13 or abs(c[0] - c[1] - 2) <= 1 else 0.8

def after_acoustic(p, w):
    q = {c: v * (1 - 0.9 * w if math.dist(c, LKP) <= 4 else 1.0) for c, v in p.items()}
    tot = sum(q.values())
    return {c: v / tot for c, v in q.items()}

def days_to_find(belief, truth, days=200):
    b, n, curve = dict(belief), {c: 0 for c in CELLS}, []
    for _ in range(days * LOOKS):
        c = max(CELLS, key=lambda c: b[c] * detect(c))
        miss = 1 - b[c] * detect(c)
        b = {k: v / miss for k, v in b.items()}; b[c] *= 1 - detect(c); n[c] += 1
        if sum(n.values()) % LOOKS == 0:
            curve.append(sum(truth[c] * (1 - (1 - detect(c)) ** n[c]) for c in CELLS))
    return 1 + sum(1 - f for f in curve), curve

if __name__ == "__main__":
    p0 = prior()
    area = sum(v for c, v in p0.items() if math.dist(c, LKP) <= 4)
    post = 0.8 * (1 - 0.9 * area) / (0.8 * (1 - 0.9 * area) + 0.2)
    print(f"prior mass in the acoustic area {area:.3f};"
          f" w = 0.8 -> {post:.3f} after the miss")
    truths = {"failed": p0, "worked": after_acoustic(p0, 1.0)}
    print("mean days to find (to 200) and P(found by day 10)")
    print("   planner's w     truth: beacons failed     truth: beacons worked")
    for w in (1.0, 0.8, 0.0):
        row = [days_to_find(after_acoustic(p0, w), t) for t in truths.values()]
        cols = "".join(f"          {m:6.1f} days, {c[9]:.3f}" for m, c in row)
        print(f"   w = {w:.1f}{cols}")
# prior mass in the acoustic area 0.381; w = 0.8 -> 0.725 after the miss
# mean days to find (to 200) and P(found by day 10)
#    planner's w     truth: beacons failed     truth: beacons worked
#    w = 1.0            24.6 days, 0.336            16.3 days, 0.511
#    w = 0.8            20.2 days, 0.371            16.8 days, 0.500
#    w = 0.0            17.5 days, 0.484            20.3 days, 0.365

声学搜索区域在先验中占 0.381。用联合模型的规划者在声学搜索没有发现之后,把「信标工作」的概率从 0.8 降到 0.725:没有发现本身就是信标可能失效的证据。

如果真相是信标失效,完全相信之前搜索的规划者平均要 24.6 天才能找到,十天内找到的概率只有 0.336;不理会之前搜索的规划者只要 17.5 天;用联合模型的规划者为 20.2 天。如果真相是信标工作,结果反过来:完全相信的规划者最快(16.3 天),不理会的规划者最慢(20.3 天),联合模型为 16.8 天。联合模型在两种真相下都不是最好的,但也都不是最差的,而且在「信标工作」时几乎没有损失。这正是斯通等人所说的「更好的做法」:不把一个不确定的假设当作确定,而是让数据去更新它。

注

贝叶斯搜索的局限。 搜索的效果取决于先验与发现概率是否合理;两个成功的案例说明方法可行,不能证明它总会成功。先验通常来自专家判断与历史事故,第 26 本《概率判断、布莱尔分数校准与群体智慧的统计理论》讨论过怎样检查这类主观概率是否校准。本章的程序只演示结构,数字都是示意的。

动物怎样找:边际价值定理与列维飞行之争

前面的搜索论假定只有一个目标、先验已知。觅食生态学研究另一种搜索:资源分散在许多斑块里,觅食者要决定在一个斑块里待多久才离开,以及在斑块之间怎样移动。两个问题各有一个著名的模型,一个结论稳健,一个至今仍有争议。

证据

查诺夫的边际价值定理(1976)。 设觅食者在一个斑块里待 tt 时间得到的收获为 g(t)g(t),gg 递增但边际收益递减(斑块被逐渐吃空),在斑块之间移动平均要 τ\tau 时间。若目标是长期平均收获率最大,所有斑块相同时,长期收获率为 R(t)=g(t)/(τ+t)R(t) = g(t)/(\tau + t),令 R′(t)=0R'(t) = 0 得最优离开时间 t*t^* 满足

g′(t*)=g(t*)τ+t*,g'(t^*) = \frac{g(t^*)}{\tau + t^*},

即离开时斑块内的边际收获率恰好降到整个生境的平均收获率(包括路上的时间)。查诺夫的原话是:觅食者应当在所处斑块中的边际捕获率降到生境的平均捕获率时离开 (Charnov 1976)。几何上,t*t^* 是从横轴上 −τ-\tau 一点向收获曲线所作切线的切点。两个直接的预测是:斑块之间的路程越远,应在每个斑块里待得越久;觅食者离开时斑块并没有被吃空。考伊 1977 年让大山雀在鸟舍里从装有食物的杯子(斑块)中觅食,用松紧不同的杯盖改变在斑块之间「移动」所需的时间;「路程」更长时,它们在每个斑块里停留得更久,与预测方向一致,只是平均停留时间比模型的最优值还要长一些 (Cowie 1977)。斯蒂芬斯与克雷布斯 1986 年的专著系统整理了这一类检验:多数研究在方向上支持该定理,在定量上常有偏离 (Stephens and Krebs 1986)。

推导

设 g(t)=G(1−e−rt)g(t) = G(1 – e^{-rt}),G=10G = 10,r=0.5r = 0.5。程序用二分法求 t*t^*,并核对离开时边际收获率等于平均收获率;最后一列是不论路程远近一律在 t=2t = 2 时离开的收获率。

# Charnov's marginal value theorem. A patch gives g(t) = G(1 - exp(-r t)); travel between
# patches takes tau. The long-run rate is g(t)/(tau + t); the best leaving time t* solves
# g'(t*) = g(t*)/(tau + t*): leave when the marginal rate falls to the average rate.
import math

G, R = 10.0, 0.5

def g(t):
    return G * (1 - math.exp(-R * t))

def dg(t):
    return G * R * math.exp(-R * t)

def t_star(tau):
    lo, hi = 1e-9, 100.0          # h(t) = g'(t)(tau + t) - g(t) falls from + to -
    for _ in range(100):
        mid = (lo + hi) / 2
        lo, hi = (mid, hi) if dg(mid) * (tau + mid) - g(mid) > 0 else (lo, mid)
    return lo

if __name__ == "__main__":
    print("marginal value theorem, G = 10, r = 0.5")
    print("  tau    t*   g(t*)/G   g'(t*)   g/(tau+t*) = best rate   rate if leave at t = 2")
    for tau in (1, 2, 4, 8):
        t = t_star(tau)
        best = g(t) / (tau + t)
        print(f"  {tau:3d}  {t:5.2f}    {g(t) / G:5.3f}   {dg(t):6.3f}          {best:6.3f}"
              f"                {g(2) / (tau + 2):6.3f}")
# marginal value theorem, G = 10, r = 0.5
#   tau    t*   g(t*)/G   g'(t*)   g/(tau+t*) = best rate   rate if leave at t = 2
#     1   1.72    0.576    2.121           2.121                 2.107
#     2   2.29    0.682    1.589           1.589                 1.580
#     4   3.01    0.778    1.110           1.110                 1.054
#     8   3.87    0.856    0.721           0.721                 0.632

路程 τ\tau 从 1 增加到 8,最优停留时间从 1.72 增加到 3.87,离开时已取走的比例从 57.6% 增加到 85.6%,没有一种情形把斑块吃空;每一行 g′(t*)g'(t^*) 都等于 g(t*)/(τ+t*)g(t^*)/(\tau + t^*)。一律在 t=2t = 2 离开的规则在路程短时几乎没有损失(τ=1\tau = 1 时 2.107 对 2.121,约 0.6%),路程长时损失约 12%(τ=8\tau = 8 时 0.632 对 0.721)。

边际价值定理本身就是一条停止规则:继续的边际价值一旦低于「放弃之后能得到的平均价值」就停下。它与第五章的单臂老虎机是同一个结构,只是这里斑块的收获曲线已知;斑块质量不确定时,离开的决定还要考虑继续停留带来的信息,这正是第四、五章讨论的问题。

证据

列维飞行觅食假说及其争议。 维斯瓦纳坦等人 1996 年分析装在漂泊信天翁身上的海水浸湿记录器数据,把连续不沾水的时段当作飞行,报告飞行时长服从幂律分布,认为信天翁的搜索是「列维飞行」(Viswanathan et al. 1996)。1999 年,他们在《自然》上证明:目标稀疏、随机分布、可以重复访问(找到后还会再生),觅食者没有记忆、只能发现近处的目标时,步长分布 p(ℓ)∝ℓ−μp(\ell) \propto \ell^{-\mu} 中 μ=2\mu = 2(「逆平方」列维飞行)使搜索效率最高;目标一被找到就消失时,接近直线运动(μ→1\mu \to 1)更好 (Viswanathan et al. 1999)。此后「生物用列维飞行觅食」被广泛引用。

2007 年,爱德华兹等人(包括 1996 年论文的几位作者)重新检查了信天翁数据 (Edwards et al. 2007)。1996 年的分析以 1 小时为分辨率,把每段不沾水的时段都算作飞行,但每次觅食行程开头与结尾的不沾水时段往往包括鸟还在南乔治亚的鸟岛上的时间;最长的 14 段(21—99 小时)全部出现在行程的开头或结尾。去掉这些时段后,最长的飞行从 99 小时降到 20 小时,数据不再呈现幂律。他们用 2004 年 20 只装有记录器与 GPS 的信天翁的新数据(1,416 段飞行,10 秒分辨率)发现,飞行时长与平移伽马分布一致,长飞行的尾部是指数型的;对 1999 年论文中鹿与熊蜂的四组数据重新分析,也没有一组表现出幂律优于指数分布的证据。他们同时提出用似然与赤池权重比较幂律尾与指数尾,代替在双对数直方图上画直线。

证据

争论没有结束。 汉弗莱斯等人 2010 年分析 14 种大洋性鱼类(鲨鱼、金枪鱼、旗鱼与翻车鲀等)的移动数据,发现列维型移动多出现在猎物稀少、生产力低的水域,布朗型移动多出现在生产力高的陆架与锋面,并有个体在不同生境间切换 (Humphries et al. 2010);2012 年,他们用高时间分辨率的 GPS 与同步记录的捕食数据分析漂泊信天翁与黑眉信天翁,认为两种移动模式都存在 (Humphries et al. 2012)。另一方面,派克 2015 年认为列维模型忽略了步与步之间的方向相关,效率不如更现实的模型,经验证据也不令人信服,主张放弃这一假说 (Pyke 2015);勒韦尼耶等人 2020 年证明,在二维及更高维中,相遇率随目标密度变化的标度与列维指数无关,因此调节 μ\mu 只改变一个前置系数,最优的 μ\mu 取决于建模细节,几乎可以是任何值;在他们的二维模型(目标被取走后立即再生)中,逆平方列维行走只在每次从紧贴目标边缘处重新出发、步长尺度远小于目标大小的特殊极限下才是最优的,而且最优列维行走带来的好处也很小 (Levernier et al. 2020)。

推导

下面的程序用最简单的一维模型复现 1999 年论文的结论:目标相距 λ\lambda,发现半径为 1,步长 ℓ≥1\ell \geq 1 服从 p(ℓ)∝ℓ−μp(\ell) \propto \ell^{-\mu},方向随机,一步走到目标就停下。「可重复访问」时从刚找到的目标旁 1 个单位处重新出发,「一次性」目标则从两个目标的中点出发。效率是找到的目标数除以走过的总路程。

# Levy walks in one dimension (after Viswanathan et al. 1999): targets lambda apart,
# detection radius 1, step lengths l >= 1 with p(l) ~ l^-mu, random direction; a step that
# reaches a target stops there. Revisitable targets: restart 1 from the target just found;
# one-off (destructive) targets: restart midway between two targets.
import random

def efficiency(mu, lam, destructive, finds, rng):
    dist = 0.0
    for _ in range(finds):
        x = lam / 2 if destructive else 1.0
        while True:
            step = rng.random() ** (-1 / (mu - 1))
            left = rng.random() < 0.5
            room = x if left else lam - x
            if step >= room:
                dist += room
                break
            x += -step if left else step
            dist += step
    return finds / dist

if __name__ == "__main__":
    rng = random.Random(42)
    mus = (1.3, 1.5, 1.7, 1.8, 1.9, 2.0, 2.1, 2.3, 2.5)
    n = 40000
    print("revisitable targets: efficiency relative to the best mu (40,000 finds)")
    print("  lambda  best mu  " + "  ".join(f"{m:4.1f}" for m in mus))
    for lam in (100.0, 1000.0, 10000.0):
        eff = [efficiency(m, lam, False, n, rng) for m in mus]
        top = max(eff)
        print(f"  {lam:6.0f}   {mus[eff.index(top)]:4.1f}    "
              + "  ".join(f"{e / top:4.2f}" for e in eff))
    print("one-off targets, lambda = 200: finds per 1,000 units of path")
    for m in (1.1, 1.5, 2.0, 2.5, 3.0):
        print(f"  mu = {m:3.1f}: {1000 * efficiency(m, 200.0, True, 1500, rng):6.2f}")
# revisitable targets: efficiency relative to the best mu (40,000 finds)
#   lambda  best mu   1.3   1.5   1.7   1.8   1.9   2.0   2.1   2.3   2.5
#      100    1.7    0.85  0.94  1.00  0.98  0.94  0.93  0.88  0.81  0.68
#     1000    1.8    0.59  0.79  0.92  1.00  0.97  0.98  0.89  0.74  0.56
#    10000    1.9    0.35  0.58  0.82  0.90  1.00  0.92  0.87  0.60  0.39
# one-off targets, lambda = 200: finds per 1,000 units of path
#   mu = 1.1:   8.92
#   mu = 1.5:   5.94
#   mu = 2.0:   2.84
#   mu = 2.5:   1.08
#   mu = 3.0:   0.45

目标可重复访问时,这次运行中最优的 μ\mu 在 λ=100\lambda = 100 时为 1.7,λ=1,000\lambda = 1{,}000 时为 1.8,λ=10,000\lambda = 10{,}000 时为 1.9。换用其他随机种子,最优值会相差 0.1 到 0.2(λ=1,000\lambda = 1{,}000 时 1.8 与 1.9 几乎打平),但在我们试过的 12 个种子中,它都不随 λ\lambda 增大而减小:目标越稀疏,最优值越接近 2,这与 1999 年的结论一致,但即使在一维的理想模型中,μ=2\mu = 2 也只是稀疏极限下的结果。最优值附近的效率曲线很平坦(λ=1,000\lambda = 1{,}000 时 μ\mu 取 1.8 到 2.0 都在最大值的 97% 以上),相邻两个 μ\mu 之间几个百分点的差别在模拟误差(约 1%—3%)之内。目标一次性时,结论完全不同:μ=1.1\mu = 1.1 时每 1,000 单位路程找到 8.92 个目标,μ=2\mu = 2 时只有 2.84 个,越接近直线运动越好。

所以「列维飞行是最优搜索策略」不是一条普适的结论。它依赖目标能否再生、目标有多稀疏、维度与觅食者的感知范围;而「动物确实在用列维飞行」又是一个独立的经验问题,信天翁一案说明,一个数据处理上的疏忽就足以制造出幂律。这一案例也是第 20 本与第 25 本讨论过的幂律检验问题的一个例子:在双对数图上看到一条直线,不等于数据来自幂律。

假说 · 尚未验证 · 赛道测试中的边际价值规则

假说(尚未检验)。作者推测,把边际价值定理用于同时测试多个赛道的团队,即「当一个赛道的边际回报降到整个组合的平均回报率(计入切换所需的时间)以下时就转移资源」,比按固定期限轮换赛道的团队在同样的总投入下得到更高的累计回报。可以检验的预测是:在预先登记了切换成本与回报口径的多期模拟商业游戏中,按边际价值规则分配时间的组,其累计回报高于按固定期限轮换的组;若两组差别在预先设定的最小关注效应以内,这一假说即失去支持。

从海底到组织里的「搜索」

在若干市场、渠道或方向中寻找「有效的那一个」,也有搜索的结构:一次失败的小规模试验相当于在某格搜了一次而没有发现,它该把判断改变多少,取决于这次试验的「发现概率」。

假说 · 尚未验证

「过早排除」假说(尚未确立)。作者推测,团队在评估新方向时,系统性地高估了自己早期小规模试验的「发现概率」,因而像法航 447 的前几阶段搜索一样,过早地把一些方向排除掉。可以检验的预测是:在事先记录了每次试验的样本量与检验效能的组织中,被「一次失败」排除、后来又被重新测试的方向,其再次测试的成功率明显高于按原试验效能计算的预期值。如果重新测试的成功率与预期一致,这一假说即失去支持。

本章小结

搜索论把「往哪里找」写成先验、发现函数与贝叶斯更新三个要素;下一次搜索的贪婪规则是选后验概率与发现概率乘积最大的地方。没有发现也是信息,它把概率从容易搜的地方推向难搜的地方。在示意的网格中,按乘积搜索比只看概率或由近及远扫过更快。「天蝎号」与法航 447 的经验说明,好的先验与诚实的发现概率是关键;法航 447 一例尤其说明,对过去搜索效果的假设本身需要放进模型里更新。觅食生态学的边际价值定理把「何时离开一个斑块」写成边际收获率降到平均收获率时停止;「列维飞行最优」则只在目标稀疏、可重复访问等条件下成立,动物是否真的这样搜索仍有争议。下一章讨论另一种搜索:在几个收益不确定的选项之间分配有限的尝试。

参考文献

Charnov, Eric L. 1976. “Optimal Foraging, the Marginal Value Theorem.” Theoretical Population Biology 9 (2): 129–36. https://doi.org/10.1016/0040-5809(76)90040-X.
Cowie, Richard J. 1977. “Optimal Foraging in Great Tits (Parus major).” Nature 268: 137–39. https://doi.org/10.1038/268137a0.
Edwards, Andrew M., Richard A. Phillips, Nicholas W. Watkins, et al. 2007. “Revisiting Lévy Flight Search Patterns of Wandering Albatrosses, Bumblebees and Deer.” Nature 449 (7165): 1044–48. https://doi.org/10.1038/nature06199.
Humphries, Nicolas E., Nuno Queiroz, Jennifer R. M. Dyer, et al. 2010. “Environmental Context Explains Lévy and Brownian Movement Patterns of Marine Predators.” Nature 465 (7301): 1066–69. https://doi.org/10.1038/nature09116.
Humphries, Nicolas E., Henri Weimerskirch, Nuno Queiroz, Emily J. Southall, and David W. Sims. 2012. “Foraging Success of Biological Lévy Flights Recorded in Situ.” Proceedings of the National Academy of Sciences 109 (19): 7169–74. https://doi.org/10.1073/pnas.1121201109.
Koopman, Bernard O. 1956. “The Theory of Search. I. Kinematic Bases.” Operations Research 4 (3): 324–46. https://doi.org/10.1287/opre.4.3.324.
Koopman, Bernard O. 1957. “The Theory of Search. III. The Optimum Distribution of Searching Effort.” Operations Research 5 (5): 613–26. https://doi.org/10.1287/opre.5.5.613.
Levernier, Nicolas, Johannes Textor, Olivier Bénichou, and Raphaël Voituriez. 2020. “Inverse Square Lévy Walks Are Not Optimal Search Strategies for d≥2d \geq 2.” Physical Review Letters 124 (8): 080601. https://doi.org/10.1103/PhysRevLett.124.080601.
Pyke, Graham H. 2015. “Understanding Movements of Organisms: It’s Time to Abandon the Lévy Foraging Hypothesis.” Methods in Ecology and Evolution 6 (1): 1–16. https://doi.org/10.1111/2041-210X.12298.
Richardson, Henry R., and Lawrence D. Stone. 1971. “Operations Analysis During the Underwater Search for Scorpion.” Naval Research Logistics Quarterly 18 (2): 141–57. https://doi.org/10.1002/nav.3800180202.
Stephens, David W., and John R. Krebs. 1986. Foraging Theory. Princeton University Press.
Stone, Lawrence D. 1975. Theory of Optimal Search. Academic Press.
Stone, Lawrence D., Colleen M. Keller, Thomas M. Kratzke, and Johan P. Strumpfer. 2014. “Search for the Wreckage of Air France Flight AF 447.” Statistical Science 29 (1): 69–80. https://doi.org/10.1214/13-STS420.
Viswanathan, G. M., V. Afanasyev, S. V. Buldyrev, E. J. Murphy, P. A. Prince, and H. E. Stanley. 1996. “Lévy Flight Search Patterns of Wandering Albatrosses.” Nature 381 (6581): 413–15. https://doi.org/10.1038/381413a0.
Viswanathan, G. M., Sergey V. Buldyrev, Shlomo Havlin, M. G. E. da Luz, E. P. Raposo, and H. Eugene Stanley. 1999. “Optimizing the Success of Random Searches.” Nature 401 (6756): 911–14. https://doi.org/10.1038/44831.

Fan, Y. (2026). Bayesian Search in Unknown Landscapes, Optimal Stopping and Gittins Indices: Exploration–Exploitation Trade-offs and Sunk-Cost Truncation in Statistical Decision Theory [未知地形中的贝叶斯搜索、秘书问题与吉廷斯指数] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23810102 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).