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,都在左下那堆。比距离时用距离的平方,省掉开根号,大小顺序不变。
-
第 0 步:随手挑 A、C 当两个中心 c₁、c₂。
-
第 1 步:每个点分给最近的中心。A、B 离 c₁ 近;C 本身就是 c₂;D、E、F 离 c₂ 更近。分成 {A, B} 和 {C, D, E, F}。
-
第 2 步:每组取平均,中心挪过去。c₁ 挪到 (1.5, 1.5),c₂ 挪到 (6.75, 6),被右上那堆拉过去了。
-
第 3 步:重新分配。C 到 c₁ 的距离平方是 4.5,到 c₂ 的是 23.0625,C 换到第 1 组。分成 {A, B, C} 和 {D, E, F}。
-
第 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 步继续。
怎么判断
一个任务是不是强化学习,看三点:有没有一个会做动作的智能体;动作会不会改变环境;反馈是不是奖励,而不是标准答案。三点都满足就是强化学习。
答强化学习的题时,五个词 agent、environment、state、action、reward 最好都用上,再补一句目标是学出最大化长期累计奖励的策略。
常见误解
以为强化学习就是「有奖励的监督学习」
监督学习每一步都有人告诉你正确答案。强化学习的奖励只说做得好不好,不说正确做法是什么,智能体得自己试出来。
以为智能体要让每一步的奖励都最大
目标是长期累计奖励最大。下棋时送掉一个子当下是损失,却可能换来最后的胜利。
试一下
扫地机器人自己学怎么打扫房间:撞墙扣分、吸到灰尘加分、电量耗尽扣大分。把五个词分别对上。
agent 是扫地机器人;environment 是房间;state 是它当前的位置、电量、周围有没有灰尘;action 是前进、转向、回去充电;reward 是吸到灰尘加分、撞墙和电量耗尽扣分。它要学的策略是「什么情况下往哪走、什么时候回去充电」。
3. 奖励来得晚:信用分配问题
它解决什么问题
强化学习和另外两类最本质的区别,在反馈的方式上。奖励可以每一步都有,也可以很久才来一次;可以很密,也可以很稀。下棋就是最极端的情况:整盘下完才知道输赢。这时智能体面对一个难题:赢了,该归功于哪一步?
直觉
一盘棋几十步,最后赢了。有的步是妙手,有的步是随便走的,有的步其实是坏棋,只是对手没抓住。只凭最后一个「赢」,分不出这些步谁功劳大。
这个问题叫信用分配(credit assignment):把一个迟来的结果,合理地分摊到前面的每一步上。AlphaGo 和玩 Atari 游戏的智能体,核心难点都在这里。
一步一步看
目标:拿同一盘棋对比两种反馈,看出强化学习只在终局拿到奖励,得自己把功劳分摊到每一步。
对比同一盘棋在两种学习方式下得到的反馈:
- 监督学习的做法:每一步都有一位老师给出正确走法,第 12 步走错了,马上就知道。
- 强化学习的做法:中间每一步都没有反馈,奖励是 0。
- 整盘下完,环境只给一个奖励:赢了加 1,输了减 1。
- 智能体要自己推断:这个最终结果,该把多少功劳或过错记到每一步上。
| 每一步的反馈 | 最后的反馈 | 要不要自己分摊功劳 | |
|---|---|---|---|
| 监督学习 | 每步都有正确答案 | — | 不要 |
| 强化学习 | 大多是 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 换组那一步的两个距离平方;然后用自己的话说出信用分配是什么;最后做完整例题和变式题。
必背
- k-means 四步:随机选 k 个中心点 → 把每个样本分给最近的中心 → 重新计算每组的中心(取组内均值)→ 重复分配与更新直到中心不再移动。
- k-means 的分组不是分类:类别是算出来的,每组代表什么要人事后解释,k 要人预先指定。
- 强化学习五要素 agent / environment / state / action / reward,目标是学出最大化长期累计奖励的策略(policy)。
- 强化学习的反馈可以延迟、稀疏,要解决信用分配问题(credit assignment):赢了一盘,功劳该记在哪一步上。
- 监督学习每一步都有人给正确答案;强化学习只有奖励告诉你做得好不好,不告诉你正确做法。
课件例题
本讲课件没有例题。k-means 和强化学习在这一讲只建立印象,考试里以简答为主:写出 k-means 的四个步骤、说明它的分组和分类的区别、写出强化学习的五个词、说明强化学习和监督学习的本质区别。k-means 的手算会在第 5 周正式讲,下面的完整例题先按手算的样子练一遍。
完整例题
题面(自编):五个一维数据点 1、2、3、10、12,k = 2,初始中心选 1 和 2。用 k-means 跑到停止,写出每一轮的分组和中心。再说明结果的两组能不能直接叫做「小数类」和「大数类」。
解法:
- 第 1 轮分配:1 归中心 1;2、3、10、12 都离中心 2 更近,归中心 2。分组 {1} 和 {2, 3, 10, 12}。
- 第 1 轮更新:中心 1 仍是 1;中心 2 = (2 + 3 + 10 + 12) ÷ 4 = 6.75。
- 第 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}。
- 第 2 轮更新:中心 1 = (1 + 2 + 3) ÷ 3 = 2;中心 2 = (10 + 12) ÷ 2 = 11。
- 第 3 轮分配:1、2、3 离 2 近,10、12 离 11 近,分组不变,停止。
- 名字问题: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。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。