← COMP5511 全部讲次
L01e · 第 1 周

L01e 没有标准答案时:k-means 自己分组,强化学习靠奖惩摸索

用六个点一帧一帧跑完 k-means,讲清它的分组为什么不是分类;再把强化学习的五个词摆进一个循环,说明奖励来得晚为什么是它最大的难点。

一句话版

前一页的监督学习,每条数据都带标准答案。这一页的两类都没有。

无监督学习手上只有数据,代表方法 k-means 把数据自动分成 k 组,组内相近、组间相远。分完以后,每组代表什么还得人来解释。

强化学习连固定的数据都没有。一个智能体在环境里做动作,环境回给它新的状态和奖励,它要学的是一套让累计奖励最大的做法。难处在于奖励常常很久才来,赢了一盘也不知道该归功于哪一步。

先认识这几个词

词 全称 / 读法 一句人话
聚类 clustering 把相近的数据自动归成一组
k-means 读「k 均值」 用 k 个中心点反复分组、取平均的聚类方法
中心 / 质心 centroid 一组点的平均位置
智能体 agent 做决定、做动作的那一方
奖励 reward 环境对动作给的分,有正有负
策略 policy 「看到什么状态就做什么动作」的一套做法
信用分配 credit assignment 结果出来后,判断功劳或过错该算在哪一步

一个类比:新生分宿舍楼层和学下象棋

开学时,宿管要把一栋楼的新生分到两层,只知道每个人的作息时间,没有任何现成的分组名单。他先随手挑两个人当两层的「代表」,其他人跟谁作息更接近就去谁那层。分完后,把每层所有人的作息取个平均,当成新的代表,再重新分一次。来回几轮,没人换层了,就分好了。分完以后他才发现:一层基本是早睡的,一层基本是夜猫子。这就是 k-means。

学下象棋是另一回事。没人告诉你每一步的标准答案,你只知道最后赢了还是输了。输了一盘,你得自己回想是哪一步走坏的。下得越多,你越知道什么局面该怎么走。这就是强化学习。

类比在哪里失效:

  • 宿管分完会给两层起名字。k-means 只给出「第 1 组、第 2 组」,起名字是人的事。
  • 人下棋会复盘、会看棋谱。最基本的强化学习只能靠自己一盘盘试,试的次数往往是人的成千上万倍。

从零讲起

1. k-means:反复「分组、取平均」

它解决什么问题

手上有一大堆数据,没有任何标签,想知道它们自然地分成哪几群。比如把顾客按消费习惯分群,把新闻按内容归类。k-means 是最常用的入门方法,第 5 周会细讲,这一讲先建立印象。

从哪来(补充)

k-means 的标准算法是 Stuart Lloyd 1957 年在贝尔实验室提出的,当时用于信号处理,直到 1982 年才正式发表。k-means 这个名字是 James MacQueen 1967 年起的。同样的思路还能追溯到 Hugo Steinhaus 1956 年的工作。

出处:Wikipedia: k-means clustering

直觉

先定要分几组,记作 k。随手放 k 个中心点。

然后反复做两件事。第一件,每个点去找离自己最近的中心,跟它一组。第二件,每组把成员的位置取平均,中心挪到平均位置上。中心挪了,有些点会发现另一个中心更近了,就换组。来回几轮,没有点再换组,中心也不再动,就结束了。

一步一步看

目标:从两个故意选坏的中心出发,看 k-means 反复分组、取平均,几轮后把六个点分回两堆。

六个点:A (1, 2)、B (2, 1)、C (3, 3) 在左下,D (7, 6)、E (8, 8)、F (9, 7) 在右上。k = 2,初始中心故意选得不好:A 和 C,都在左下那堆。比距离时用距离的平方,省掉开根号,大小顺序不变。

  1. 第 0 步:随手挑 A、C 当两个中心 c₁、c₂。

    第 0 步:六个点 A、B、C 在左下,D、E、F 在右上,两个青绿的叉是初始中心 c₁ 在 A (1, 2)、c₂ 在 C (3, 3),还没有分组

  2. 第 1 步:每个点分给最近的中心。A、B 离 c₁ 近;C 本身就是 c₂;D、E、F 离 c₂ 更近。分成 {A, B} 和 {C, D, E, F}。

    第 1 步:每个点用青绿实线连到最近的中心,A、B 连到 c₁,C、D、E、F 连到 c₂;第 1 组是 A B,第 2 组是 C D E F

  3. 第 2 步:每组取平均,中心挪过去。c₁ 挪到 (1.5, 1.5),c₂ 挪到 (6.75, 6),被右上那堆拉过去了。

    第 2 步:两个中心沿青绿箭头移动,c₁ 从 (1, 2) 挪到 A B 的平均 (1.5, 1.5),c₂ 从 (3, 3) 挪到 C D E F 的平均 (6.75, 6)

  4. 第 3 步:重新分配。C 到 c₁ 的距离平方是 4.5,到 c₂ 的是 23.0625,C 换到第 1 组。分成 {A, B, C} 和 {D, E, F}。

    第 3 步:C 用青绿实线连到 c₁,表示它换到了第 1 组;右侧注明 C 到 c₁ 距离平方 4.5,到 c₂ 距离平方 23.0625;第 1 组 A B C,第 2 组 D E F

  5. 第 4 步:再取平均,c₁ = (2, 2),c₂ = (8, 7)。再分配一次,没有点换组,中心不再动,结束。

    第 4 步:c₁ 挪到 (2, 2),c₂ 挪到 (8, 7),青绿箭头标出最后一次移动;右侧注明再分配一次没有点换组,中心不再动,结束

怎么算

两点间距离的平方:d² = (x₁ − x₂)² + (y₁ − y₂)²

意思是:横向差几格、纵向差几格,各自平方后加起来。只比远近时不用开根号。

第 3 步里 C (3, 3) 到两个中心:

到 c₁ (1.5, 1.5):d² = 1.5² + 1.5² = 2.25 + 2.25 = 4.5

到 c₂ (6.75, 6):d² = 3.75² + 3² = 14.0625 + 9 = 23.0625

意思是:C 离 c₁ 近得多,所以换到第 1 组。

组的中心是组内点的平均:{C, D, E, F} 的中心 = ((3 + 7 + 8 + 9) ÷ 4, (3 + 6 + 8 + 7) ÷ 4) = (6.75, 6)

意思是:横坐标加起来除以人数,纵坐标加起来除以人数。

常见误解

以为 k-means 的分组就是分类

分类的类别是人事先定义好的,训练数据带着标签。k-means 的分组是算出来的,只有「第 1 组、第 2 组」,每组代表什么要人事后解释。

以为每一轮都要重新随机选中心

随机初始化只在开头做一次。之后重复的是「分配样本」和「更新中心」两步。

以为 k 是算法自己算出来的

k 要人预先指定,这是 k-means 最大的实践难点。k 定错了,比如数据本来有三群却让它分两组,它也会老老实实分成两组。

试一下

四个点 P (0, 0)、Q (0, 2)、R (10, 0)、S (10, 2),k = 2,初始中心选 P 和 Q。第一轮怎么分组?中心挪到哪?

R 到 P 的 d² = 100,到 Q 的 d² = 100 + 4 = 104,归 P;S 到 P 是 104,到 Q 是 100,归 Q。分成 {P, R} 和 {Q, S}。中心挪到 (5, 0) 和 (5, 2)。初始中心选得不好时,k-means 可能停在这种横着切的分法上,没切出左右两堆。

2. 强化学习的五个词

它解决什么问题

有些任务既没有标准答案,也没有一批现成的数据,比如下棋、玩游戏、控制机器人。没人能告诉你每一步的正确做法,只能做了以后看结果好不好。强化学习就是为这种「边做边学」的任务设计的。

直觉

一个智能体(agent)待在一个环境(environment)里。它看到当前的状态(state),选一个动作(action)。环境因为这个动作变了样,给它新的状态,同时给一个奖励(reward),可正可负。

智能体反复这样做,慢慢摸出一套「看到什么状态就做什么动作」的做法,这套做法叫策略(policy)。它要的是一整局下来的累计奖励最大,单看某一步的奖励没有意义。

一步一步看

目标:用闯关游戏走一轮状态、动作、新状态、奖励、更新策略,看这五个词怎样连成一个循环。

拿玩一个闯关游戏走一轮:

  1. 智能体看到当前状态:自己站在坑边,前面有金币。

  2. 它按当前策略选一个动作:往前跳。

  3. 环境变化,返回新状态:它落到坑对面,捡到金币。

  4. 环境同时给奖励:捡金币加分。如果掉坑,就扣分。

  5. 智能体根据这次的奖励更新策略,回到第 1 步继续。

    强化学习交互循环:左边是智能体 agent,按策略 policy 选动作;右边是环境 environment;上方箭头是智能体对环境做动作 action;下方两条箭头是环境返回新的状态 state 和青绿标出的奖励 reward,奖励可能很久才来;目标是一整局的累计奖励最大

怎么判断

一个任务是不是强化学习,看三点:有没有一个会做动作的智能体;动作会不会改变环境;反馈是不是奖励,而不是标准答案。三点都满足就是强化学习。

答强化学习的题时,五个词 agent、environment、state、action、reward 最好都用上,再补一句目标是学出最大化长期累计奖励的策略。

常见误解

以为强化学习就是「有奖励的监督学习」

监督学习每一步都有人告诉你正确答案。强化学习的奖励只说做得好不好,不说正确做法是什么,智能体得自己试出来。

以为智能体要让每一步的奖励都最大

目标是长期累计奖励最大。下棋时送掉一个子当下是损失,却可能换来最后的胜利。

试一下

扫地机器人自己学怎么打扫房间:撞墙扣分、吸到灰尘加分、电量耗尽扣大分。把五个词分别对上。

agent 是扫地机器人;environment 是房间;state 是它当前的位置、电量、周围有没有灰尘;action 是前进、转向、回去充电;reward 是吸到灰尘加分、撞墙和电量耗尽扣分。它要学的策略是「什么情况下往哪走、什么时候回去充电」。

3. 奖励来得晚:信用分配问题

它解决什么问题

强化学习和另外两类最本质的区别,在反馈的方式上。奖励可以每一步都有,也可以很久才来一次;可以很密,也可以很稀。下棋就是最极端的情况:整盘下完才知道输赢。这时智能体面对一个难题:赢了,该归功于哪一步?

直觉

一盘棋几十步,最后赢了。有的步是妙手,有的步是随便走的,有的步其实是坏棋,只是对手没抓住。只凭最后一个「赢」,分不出这些步谁功劳大。

这个问题叫信用分配(credit assignment):把一个迟来的结果,合理地分摊到前面的每一步上。AlphaGo 和玩 Atari 游戏的智能体,核心难点都在这里。

一步一步看

目标:拿同一盘棋对比两种反馈,看出强化学习只在终局拿到奖励,得自己把功劳分摊到每一步。

对比同一盘棋在两种学习方式下得到的反馈:

  1. 监督学习的做法:每一步都有一位老师给出正确走法,第 12 步走错了,马上就知道。
  2. 强化学习的做法:中间每一步都没有反馈,奖励是 0。
  3. 整盘下完,环境只给一个奖励:赢了加 1,输了减 1。
  4. 智能体要自己推断:这个最终结果,该把多少功劳或过错记到每一步上。
每一步的反馈 最后的反馈 要不要自己分摊功劳
监督学习 每步都有正确答案 — 不要
强化学习 大多是 0 赢 +1 / 输 −1 要,这就是信用分配

怎么判断

题目问「强化学习和监督学习最本质的区别」,按两层写:第一层,监督学习每一步有正确答案,强化学习只有奖励;第二层,奖励常常延迟且稀疏,所以要解决信用分配问题。

奖励也不一定都延迟。游戏里每吃一个金币就加分,是即时而密集的奖励。题目给出的场景奖励来得越晚、越少,信用分配就越难。

常见误解

以为强化学习的奖励一定要到最后才给

奖励可以即时也可以延迟,可以密集也可以稀疏。下棋是延迟稀疏的极端,吃金币加分是即时密集的。延迟稀疏让信用分配变难,但它不是强化学习的定义。

以为强化学习一定要在线和环境交互

这一讲用的是在线交互的模型。也有离线强化学习,用一批事先收集的经验来学,课上暂不涉及。

试一下

一个机器人学走迷宫:方案 A 只在走出迷宫时给 +1,方案 B 每靠近出口一步给 +0.1、撞墙给 −0.1。哪个方案的信用分配更难?

方案 A 更难。奖励只在最后出现一次,前面几百步谁有用、谁绕了远路都要自己推断。方案 B 每一步都有反馈,功劳和过错几乎当场就能记上。

把它们串起来

没有标准答案时,机器学习分成两条路。

只有数据,就找数据自己的结构。k-means 先定要分 k 组,随手放 k 个中心,然后反复「每个点找最近的中心」「每组取平均挪中心」,直到没有点再换组。它分出来的组没有名字,每组代表什么要人解释,k 也要人事先定。

连数据都没有,只有一个能交互的环境,就是强化学习。智能体看状态、做动作,环境回给新状态和奖励,智能体学的是让累计奖励最大的策略。奖励常常来得晚、来得少,所以要把最终的结果分摊到前面每一步上,这就是信用分配。

到这里,三类都讲完了:监督学习有答案,无监督学习找结构,强化学习靠奖惩。下一讲换到 AI 的另一条路:不学习,靠搜索在状态空间里找到目标。

课件里的坑

  • [分组不是分类] 课件特别强调 k-means 的「分组」不是分类。答题时要写出两点:类别是算出来的、要人事后解释;k 要人预先指定(p.78)
  • [重复哪两步] 课件四步里第 4 步写「重复直到中心不再移动」,重复的是分配样本和更新中心两步,不包括随机初始化(p.78)
  • [奖励的说法] 常见讲法说强化学习「只有延迟且稀疏的反馈」。更准的说法是奖励可即时或延迟、密集或稀疏,延迟稀疏是让它难的那种情况(p.80)
  • [应用页指向强化学习] p.62–65 的模拟智能体、Atari、机器人都指向强化学习,不直接考,但可以拿来当答题时的例子(p.62–65)

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,先默写 k-means 四步和强化学习五个词;再拿六个点 A 到 F 在纸上从第 0 步跑到第 4 步,重点算 C 换组那一步的两个距离平方;然后用自己的话说出信用分配是什么;最后做完整例题和变式题。

必背

  1. k-means 四步:随机选 k 个中心点 → 把每个样本分给最近的中心 → 重新计算每组的中心(取组内均值)→ 重复分配与更新直到中心不再移动。
  2. k-means 的分组不是分类:类别是算出来的,每组代表什么要人事后解释,k 要人预先指定。
  3. 强化学习五要素 agent / environment / state / action / reward,目标是学出最大化长期累计奖励的策略(policy)。
  4. 强化学习的反馈可以延迟、稀疏,要解决信用分配问题(credit assignment):赢了一盘,功劳该记在哪一步上。
  5. 监督学习每一步都有人给正确答案;强化学习只有奖励告诉你做得好不好,不告诉你正确做法。

课件例题

本讲课件没有例题。k-means 和强化学习在这一讲只建立印象,考试里以简答为主:写出 k-means 的四个步骤、说明它的分组和分类的区别、写出强化学习的五个词、说明强化学习和监督学习的本质区别。k-means 的手算会在第 5 周正式讲,下面的完整例题先按手算的样子练一遍。

完整例题

题面(自编):五个一维数据点 1、2、3、10、12,k = 2,初始中心选 1 和 2。用 k-means 跑到停止,写出每一轮的分组和中心。再说明结果的两组能不能直接叫做「小数类」和「大数类」。

解法:

  1. 第 1 轮分配:1 归中心 1;2、3、10、12 都离中心 2 更近,归中心 2。分组 {1} 和 {2, 3, 10, 12}。
  2. 第 1 轮更新:中心 1 仍是 1;中心 2 = (2 + 3 + 10 + 12) ÷ 4 = 6.75。
  3. 第 2 轮分配:2 到 1 的距离是 1,到 6.75 是 4.75,归中心 1;3 到 1 是 2,到 6.75 是 3.75,也归中心 1;10、12 归中心 2。分组 {1, 2, 3} 和 {10, 12}。
  4. 第 2 轮更新:中心 1 = (1 + 2 + 3) ÷ 3 = 2;中心 2 = (10 + 12) ÷ 2 = 11。
  5. 第 3 轮分配:1、2、3 离 2 近,10、12 离 11 近,分组不变,停止。
  6. 名字问题:k-means 只给出「第 1 组、第 2 组」。叫它们「小数类」「大数类」是人看了结果之后起的名字,算法本身不知道。这正是分组和分类的区别。

要点:每轮先分配再更新,更新后要再分配一次确认没有点换组才算停。

答题格式:每轮写「分配:…;更新:…」两行,最后一行写停止的理由。

变式题(先自己做)

(1) 自编情境:一款外卖 App 想把骑手按接单时段、跑单距离分成几类,事先不知道该分几类。用 k-means 时最先遇到的难点是什么?分出来的组怎么用? (2) 自编情境:一个程序学玩俄罗斯方块,每消掉一行加分,堆到顶游戏结束。写出五个词各是什么,说明它的奖励是即时还是延迟。 (3) 自编情境:围棋程序只在一局结束时得到胜负。为什么它比俄罗斯方块程序更难学?

提示

(1) 回到 k 由谁来定,和分组有没有名字。(2) 按 agent、environment、state、action、reward 逐个填。(3) 比较两者奖励来的时机和次数。

判分点与答案(非官方评分标准)

判分点:① (1) 写出 k 要人预先指定、分组要人解释;② (2) 五个词齐全并判断奖励类型;③ (3) 写出信用分配问题。

(1) 难点是 k 要人预先指定,不知道该分几类就得试几个 k 比较。分出来的组只有编号,要人看每组骑手的特点,再起名字、定运营策略。

(2) agent 是玩游戏的程序;environment 是游戏画面和规则;state 是当前方块堆的形状和下一个方块;action 是左移、右移、旋转、下落;reward 是消行加分。消一行就加分,奖励相对即时。

(3) 围棋的奖励延迟且稀疏,整局只有一次胜负。程序要自己判断几百步里哪些步带来了胜利,信用分配比俄罗斯方块难得多。

闪卡自测

1. 描述 k-means 的四个步骤。

随机选 k 个中心点 → 把每个样本分给最近的中心 → 重新计算每组的中心(取组内均值)→ 重复分配样本与更新中心两步,直到中心不再移动(p.78)。

2. k-means 的分组和分类的类别有什么本质区别?

分类的类别是人事先定义好的,有标签;k-means 的分组是算出来的,每组代表什么要人事后解释(p.78)。

3. k-means 最大的实践难点是什么?

k 要人预先指定(p.78)。

4. k-means 每一轮重复的是哪两步?

分配样本给最近的中心、按组内均值更新中心。随机初始化只在开头做一次(p.78)。

5. 强化学习的五个标准名词是什么?

agent / environment / state / action / reward(p.80)。

6. 强化学习要学出什么?

一个策略(policy),也就是看到什么状态做什么动作,使长期累计奖励最大(p.80)。

7. 强化学习和监督学习最本质的区别在哪?

监督学习每一步都有人给正确答案;强化学习只有奖励,奖励可以延迟、稀疏(下完一整盘棋才知道输赢),所以要解决信用分配问题(p.80)。

8. 什么是信用分配问题?

结果出来后,判断功劳或过错该记在前面哪一步上。例如一盘棋赢了,功劳该归哪几步(p.80)。

下一讲

下一讲把 AI 问题改写成「从起点找到终点」,先讲搜索问题怎么定义,再讲 BFS、DFS 这些不需要学习的找法。见 L02a-1。

下一讲 →
T01a T01a Tutorial 1 上半:论文去哪找、什么样的能引、八个部分各装什么

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。