人工智能：搜索、推理与学习

运行一个完整示例 · 01

A* 找到更优路径时重新展开状态

米娜制作路线规划器，用下界估计剩余成本。每个估计都没有高估，但相邻节点的估计变化不够平稳。程序先以成本 2 到达 A，之后发现成本 1.5 的路线。永久关闭状态的写法丢弃了这次改善。米娜改为保存最佳已知成本，成本改善时允许状态重新进入边界。

from heapq import heappop, heappush
from math import inf

def astar(graph, heuristic, start, goal):
    best = {start: 0.0}
    parent = {}
    frontier = [(heuristic[start], 0.0, start)]
    expanded = []
    while frontier:
        _, cost, node = heappop(frontier)
        if cost != best[node]:
            continue
        expanded.append(node)
        if node == goal:
            path = [goal]
            while path[-1] != start:
                path.append(parent[path[-1]])
            return cost, list(reversed(path)), expanded
        for nxt, step in graph[node]:
            if step < 0:
                raise ValueError("nonnegative edges required")
            candidate = cost + step
            if candidate < best.get(nxt, inf):
                best[nxt] = candidate
                parent[nxt] = node
                heappush(frontier, (candidate + heuristic[nxt], candidate, nxt))
    return inf, [], expanded

graph = {"S": [("A", 2), ("B", 1)], "A": [("G", 2)],
         "B": [("A", 0.5), ("G", 100)], "G": []}
h = {"S": 3.5, "A": 0, "B": 2.5, "G": 0}
cost, path, expanded = astar(graph, h, "S", "G")
assert cost == 3.5 and path == ["S", "B", "A", "G"]
assert expanded == ["S", "A", "B", "A", "G"]
assert astar(graph, {node: 0 for node in graph}, "S", "G")[0] == cost
print("expanded:", expanded)
print("path:", path)
print(f"cost: {cost:.1f}")

python astar-heuristics-astar-reopen-states.py

expanded: ['S', 'A', 'B', 'A', 'G']
path: ['S', 'B', 'A', 'G']
cost: 3.5

按执行顺序理解

1. 堆中保存 f=g+h，并同时保存 g；best 字典记录到每个状态已发现的最低成本。

2. 只要 g 改善，就插入新的堆条目，即使该状态之前已展开。

3. 若条目的 g 已不同于 best，就跳过，因为它描述过期路线。

4. 目标以当前最佳 g 出堆时才停止，仅仅生成目标还太早。

逐步读懂代码

可采纳性要求 h(v) 不超过真实剩余成本。一致性更强，要求每条边满足 h(u)≤w(u,v)+h(v)。本例 h(B)=2.5 可采纳，因为 B→A→G 恰好花费 2.5；但在 B→A 上不一致，因为 2.5>0.5+0。

S 展开后，A 的 f=2，B 的 f=3.5。先展开 A，发现成本 4 的 G；再展开 B，把 A 改善到 g=1.5；重新展开 A，才把 G 改善到 3.5。在这里规定的有限图、非负边、有限可采纳启发式且 h(目标)=0 的条件下，重新展开能保留 A* 最优终止所需的路线。函数假定调用者提供满足条件的启发式，不会自动验证可采纳性。

启发式不一致时，状态可能多次展开，不能声称每个状态只处理一次的复杂度。特殊情形 h=0 就是一致代价搜索。实践中应选择能够解释假设的启发式，并同时记录解的质量和展开次数。

运行一个完整示例 · 01

找到并平均两个邻居

用排序距离表重现第一道完整例题。

records = [(0, 2), (4, 10), (7, 16)]
query = 5
ranked = []
for x, target in records:
    distance = abs(x - query)
    ranked.append((distance, x, target))
ranked.sort()
selected = ranked[:2]
total = 0
for distance, x, target in selected:
    total += target
prediction = total / len(selected)
print("Neighbors:", selected)
print("Prediction:", prediction)
assert prediction == 13

python learning-neighbors-nearest-two-trace.py

Neighbors: [(1, 4, 10), (2, 7, 16)]
Prediction: 13.0

按执行顺序理解

1. 排序前距离5、1、2。

2. 排序使输入4、7在前，目标10、16。

3. 平均26/2=13，改变 k 会改变选中集合。

逐步读懂代码

每条记录是输入与目标的一对。for 把值对拆到变量名，abs 求绝对距离，append 把三数元组加入 ranked 列表。

sort 先按元组首数排序，平局再看后面数字。切片 [:2] 保留前两项。第二循环加目标，+= 表示加到现有总数。len 数入选项，总数除项数得平均，assert 检查例题答案。只有一个输入坐标，演示未做特征缩放。

运行一个完整示例 · 01

在对数空间中计算长文本似然

社团把留言分成两个主题。米娜连乘词概率，短留言的结果看起来正常。留言变长后，两个类别的分数在浮点运算中都变成零。不是留言突然不可能出现，而是表示范围不够了。她改存对数分数，累加各词贡献，并先减去最大分数再归一化。

from math import exp, log, isclose

vocabulary = ["red", "round", "blue"]
counts = {"A": {"red": 3, "round": 1, "blue": 0},
          "B": {"red": 0, "round": 1, "blue": 3}}

def log_scores(document):
    result = {}
    for label, words in counts.items():
        denominator = sum(words.values()) + len(vocabulary)
        score = log(0.5)
        for word in vocabulary:
            probability = (words[word] + 1) / denominator
            score += document.get(word, 0) * log(probability)
        result[label] = score
    return result

def posterior(scores):
    largest = max(scores.values())
    weights = {label: exp(value - largest) for label, value in scores.items()}
    total = sum(weights.values())
    return {label: value / total for label, value in weights.items()}

short = {"red": 2, "round": 1}
scores = log_scores(short)
probabilities = posterior(scores)
assert isclose(probabilities["A"], 16 / 17)
print(f"short P(A|text): {probabilities['A']:.6f}")
long = {word: count * 1000 for word, count in short.items()}
long_scores = log_scores(long)
print("raw scores underflow:", [exp(x) == 0 for x in long_scores.values()])
print("log-space winner:", max(long_scores, key=long_scores.get))
assert isclose(sum(posterior(long_scores).values()), 1.0)

python naive-bayes-log-space-word-counts.py

short P(A|text): 0.941176
raw scores underflow: [True, True]
log-space winner: A

按执行顺序理解

1. 每个类别的每个词计数加一；类别词元总数加上词表大小。

2. 计算对数先验，再累加“出现次数×对数似然”，重复词会重复贡献。

3. 取指数前减去最大对数分数，保持比例不变，并使最大权重等于一。

4. 用 16/17 核对短文结果，并展示长文原始分数为何下溢。

逐步读懂代码

类别 c 的分数为 score(c)=log P(c)+对所有词 w 求和 n_w×log((N_cw+alpha)/(N_c+alpha×V))。n_w 是新文档中词的次数，N_cw 是训练集中该类别该词的次数，N_c 是该类别训练词元总数，V 是词表大小，本例 alpha=1。与词序无关的多项式系数对两类相同，会在归一化中抵消，因此省略。

新文档包含两个 red、一个 round 时，包含相同先验后的未归一化分数分别为 16/343、1/343，归一化后得到 P(A|text)=16/17。本例使用固定词表，忽略未见词；实际流程需要说明未知词策略，并只用训练数据拟合。

稳定算术避免下溢抹掉类别比较，却不能修复条件独立近似，也不会自动校准概率。重复高度相关的词仍可能使模型过度自信。因此要区分数值正确与建模正确。

运行一个完整示例 · 01

看清平均数掩盖了哪个类别

分类器识别十张图片：八张叶片、一张花、一张种子。米娜看到 90% 准确率，以为每个类别都不错。但唯一的花被预测成了叶片。她先为各类别分别计分，再求平均，小类别的问题就不会被大类别掩盖。

from math import isclose
labels = ["leaf", "flower", "seed"]
truth = ["leaf"] * 8 + ["flower", "seed"]
predicted = ["leaf"] * 9 + ["seed"]

def report(truth, predicted, labels):
    if len(truth) != len(predicted) or not truth:
        raise ValueError("nonempty aligned observations required")
    if set(truth + predicted) - set(labels):
        raise ValueError("unknown label")
    per_class = []
    total_tp = total_fp = total_fn = 0
    for label in labels:
        tp = sum(t == label and p == label for t, p in zip(truth, predicted))
        fp = sum(t != label and p == label for t, p in zip(truth, predicted))
        fn = sum(t == label and p != label for t, p in zip(truth, predicted))
        denominator = 2 * tp + fp + fn
        f1 = 2 * tp / denominator if denominator else 0.0
        per_class.append((label, tp, fp, fn, f1))
        total_tp += tp; total_fp += fp; total_fn += fn
    macro = sum(row[4] for row in per_class) / len(labels)
    micro = 2 * total_tp / (2 * total_tp + total_fp + total_fn)
    return per_class, macro, micro

rows, macro, micro = report(truth, predicted, labels)
for label, tp, fp, fn, f1 in rows:
    print(f"{label}: TP={tp} FP={fp} FN={fn} F1={f1:.4f}")
accuracy = sum(t == p for t, p in zip(truth, predicted)) / len(truth)
assert isclose(macro, (16/17 + 0 + 1)/3) and isclose(micro, accuracy)
print(f"macro F1={macro:.4f}; micro F1={micro:.4f}; accuracy={accuracy:.4f}")

python classification-metrics-macro-micro-report.py

leaf: TP=8 FP=1 FN=0 F1=0.9412
flower: TP=0 FP=0 FN=1 F1=0.0000
seed: TP=1 FP=0 FN=0 F1=1.0000
macro F1=0.6471; micro F1=0.9000; accuracy=0.9000

按执行顺序理解

1. 每次把一个类别当作正类。被错分的花给叶片增加一个假正例，给花增加一个假负例。

2. 计算每类 F1_c=2TP_c/(2TP_c+FP_c+FN_c)，并明确零分母约定。

3. 宏平均让各类 F1 权重相同；微平均先合并计数，再算一个分数。

4. 在单标签且覆盖所有类别的本例中，用准确率核对微平均 F1。

逐步读懂代码

宏平均 F1=(1/K)×K 个类别 F1 之和，每个纳入类别获得 1/K 权重。微平均 F1=2ΣTP/(2ΣTP+ΣFP+ΣFN)。在覆盖全部类别的单标签分类中，每个错误预测贡献一个 FP 和一个 FN，因此微平均 F1 等于准确率。但该等式不能直接推广到多标签任务或只评估部分类别的情况。

叶片 F1=16/17，花 F1=0，种子 F1=1。宏平均约为 0.6471，微平均与准确率则都是 0.9。任何平均数都不能替代逐类计数；十个样本也远不足以可靠估计部署表现。

程序把零分母类别计为零，并纳入明确列出的全部标签。其他规则可能排除未定义类别。因此比较报告前要先说明约定，否则两个工具即使都正确，也可能从同一数据得出不同宏平均值。

运行一个完整示例 · 01

检查一次 sigmoid 更新

只用标准 math 模块跟踪第一道完整例题。

import math

x, target = 2.0, 1.0
weight, bias = 0.0, 0.0
rate = 0.1
score = weight * x + bias
activation = 1 / (1 + math.exp(-score))
delta = (activation - target) * activation * (1 - activation)
weight_gradient = delta * x
bias_gradient = delta
weight = weight - rate * weight_gradient
bias = bias - rate * bias_gradient
print(f"Old output: {activation:.6f}")
print(f"New weight: {weight:.6f}")
print(f"New bias: {bias:.6f}")
print(f"New score: {weight * x + bias:.6f}")
assert abs(weight - 0.025) < 1e-12

python backpropagation-sigmoid-one-update.py

Old output: 0.500000
New weight: 0.025000
New bias: 0.012500
New score: 0.062500

按执行顺序理解

1. 旧分数0给激活0.5、delta −0.125。

2. 输入2使权重梯度−0.25，偏置梯度−0.125。

3. 减负更新使分数升至0.0625。

逐步读懂代码

import math 使指数函数 math.exp 可用。逗号赋值将两个数字分别存入两个名称。sigmoid 把旧分数转为0与1间输出。

delta 将损失斜率乘 sigmoid 斜率。两个梯度先保存，再改变任一参数。减学习率乘梯度就是下降。f 字符串插入数值，:.6f 显示六位小数。abs 与小容差检查浮点结果。这是手工设定的单神经元与一步训练，不是训练好的通用分类器。

运行一个完整示例 · 01

跟踪两轮 Lloyd 更新

检查四个一维点的分配、均值与平方误差。

points = [1, 3, 9, 11]
centers = [1, 9]
for step in range(2):
    groups = [[], []]
    for point in points:
        distances = [abs(point - centers[0]), abs(point - centers[1])]
        group_id = 0 if distances[0] <= distances[1] else 1
        groups[group_id].append(point)
    centers = [sum(group) / len(group) for group in groups]
    error = 0
    for group_id, group in enumerate(groups):
        for point in group:
            error += (point - centers[group_id]) ** 2
    print(f"Step {step + 1}: centers={centers}, SSE={error:.1f}")
assert centers == [2.0, 10.0]

python kmeans-lloyd-two-clusters.py

Step 1: centers=[2.0, 10.0], SSE=4.0
Step 2: centers=[2.0, 10.0], SSE=4.0

按执行顺序理解

1. 首轮分配成[1,3]与[9,11]。

2. 均值2、10给四个各1的平方误差，总4。

3. 第二次分配不变，均值与 SSE 均不变。

逐步读懂代码

range(2) 使外循环两次，step 为0与1。groups 含两个空列表。索引0指首中心，1指第二。条件表达式选择近中心，<= 将平局给首组。此处绝对距离与平方距离最近排序一致。append 把点放入选定列表。

列表推导式对每组用 sum/len 求平均。本例两组非空，通用实现需空组规则。enumerate 同时给列表索引和组。内循环加平方误差，**2 表平方。第二次打印确认本数据稳定，不证明任意数据全局最优。