自适应学习的两种设计方案:知识点间和知识点内

这篇文章将介绍两种自适应学习方案:“知识点间”(between knowledge points)自适应和“知识点内”(within knowledge points)自适应。知识点间自适应适合推荐引擎可以控制课程进度的学习场景。知识点内自适应适合推荐引擎无法控制课程进度但是有丰富题库的学习场景。

1.知识点自适应

知识点间自适应方案主要对于知识点的学习顺序进行优化。大部分“基于知识图谱”的自适应学习都属于这个大类下。

这种自适应方案的核心问题是:

假设有一个知识点集合,是否存在一个学习路径,使得学生在掌握前置知识点的前提下,必然能够沿着这个学习路径掌握所有的知识点?

比如说,Khan Academy构建了一张数学知识图谱,为每一个知识点都刻画了一个学习路径。它的暗含假设是,如果一个学生掌握了这个路径上的全部前置知识点,他必然可以通过练习掌握这个知识点。因此,只要按图索骥,就可以避免Khan所担心的知识网络“奶酪式”成长(aka都是洞)的问题。

因为知识图谱上的学习路径是唯一的,Khan Academy的自适应仅局限于对于学习速度的自适应。如果学生A花了一周还没有学会几何法求解空间二面角,他应该花更长的时间来巩固这个知识点直到掌握。如果学生B花了一天就学会了,他应该继续去学别的内容。这相对于统一步调的课堂教学而言,的确是一个实质性的改进。但是,Khan Academy式的知识图谱不能针对掌握水平分布进行自适应。如果学生A并不擅长几何思考,但是熟练地掌握了空间直角坐标系,为什么他不能通过空间直角坐标系来解决这个问题呢?

上述例子展示了绘制知识图谱所面临的巨大挑战。知识图谱是否只有一种画法?同一个知识点是否只有一条路径?ALEKS理论上为这两个问题提供了解答。即使知识图谱不只有一个,通往同一个知识点的路径不只有一条,可以学会全部知识点的可行路径依然存在。但是可行路径的数量级可能在千万级。

仅仅有知识图谱并不足够,系统还需要对于学生在每个知识点上的掌握程度进行诊断。掌握程度(mastery)之所以困难,是因为它是一个不可见的抽象构架。学界和业界对于该如何定义“掌握”存在比较大的分歧。例如,老版的Khan Academy用了最简单的“连对10个就算掌握”的规则。Duolingo也使用预测正确率作为用户掌握某个词汇或者语法的依据。从智能教学系统科班出身的自适应系统,例如卡耐基学习出品的Cognitive Tutor或者Knewton,都使用结构模型来定义掌握程度和做题结果的关联,从而部分抵消题目特性对于掌握程度推断的影响。例如,75分到底是掌握水平高,还是掌握水平低呢?如果平均分是60分(题目偏难),75分可能说明学生的水平相当不错;如果平均分是90分(题目偏易),75分可能说明学生的水平相当糟糕。

传统的知识点间自适应系统只对于学生做过题的知识点进行掌握程度推断。更复杂的一点自适应系统,(例如Knewton),会使用知识点间的关联关系来推断学生未做过题的知识点的掌握程度。这种关联推断只能算是锦上添花。尽管它降低了学生学习整个图谱所需要完成的最低做题量,但是它并没有提供探索可行学习路径的更好办法。

“知识点间自适应”是一个在直觉上合理并且在技术上成熟的设计方案。今天我们在中国看到的自适应学习系统,大部分属于这个类别。然而,“知识点间自适应”系统在美国的实际使用中效果差强人意。Eric Taylor 对智能学习系统的实证效果进行了综述,发现大部分混合教学并没有取得比课堂教学更好的教学效果。笔者认为原因有三:

第一,教材本身内含了一个设计良好的知识图谱和学习路径;由第三方教学专家构建的图谱和路径,未必有久经考验的教材版本效果更好。

第二,“知识点间自适应”要求老师允许学生以不同的速度学习,从而出现自然的教学分层现象。不论从政治环境上,还是从老师的教学负担上,教学分层都只能是一个“看上去很美”的教学设想。由于大部分知识点间自适应系统并没有ALEKS那样的基于掌握水平的自适应,而只有基于速度的自适应,不允许学习速度分化,事实上扼杀了自适应系统的优势。

第三,知识点间自适应和老师的替代性超过互补性,因此老师使用自适应系统后偷懒也可能是效果不章的原因之一。

2.知识点自适应

知识点内自适应方案在给定知识点内的不同题目之间进行筛选和排序。笔者认为这与国内大部分题库产品比较类似。笔者不能确定它们是否采用了这种自适应设计方案,因为它们对于自己的方法论讳莫如深。

“知识点内自适应”是一种颇具中国特色的产品形态。在美国,由于可公开获得的题库不论在数量上和质量上都难以尽如人意,因此大部分自适应学习系统在知识点内都采用计算机出题的模式,包括Khan Academy,Duolingo,Cognitive Tutor和ALEKS。这些题目本身高度雷同,因此并不存在太多的自适应空间。但是这种可控程度较高的练习题生成方式基本没有被中国的教育互联网公司采用。笔者认为一方面是成本的考量,另一方面也是用户体验的考量。从成本上说,在国内获取一个数目客观、质量尚可的题库较挨个知识点写生成器要便宜的多,也要快得多。从用户体验上说,家长和老师可能更希望练习题目应该类似于考试题目(特别是初高中学段)。此外,国内教学环境对于“超纲”比较敏感,知识点自适应在不能自由选择教学进度的前提下并没有太大用武之地。因此,利用一个数量庞大且品质参差不齐的题库进行知识点内练习(和教学)推荐,是一个非常具有中国特色的技术问题。

这类推荐系统需要回答的核心问题是:

假设有一个题库,是否存在一个练习路径,使得学生以最少的做题量达到某个预先指定的熟练程度?

这里有两点值得强调:

第一,这个问题与传统上的计算机辅助测试(Computerized Adaptive Testing),比如ETS的TOEFL和GRE,具有本质的区别。CAT的问题是,假设被试者能力不变,给定一个题库,是否存在一个测试路径,使得系统以最少的题量将学生能力估计到某个预先指定的熟练程度。因为CAT从根本假设上否定了通过练习进行学习(learning through practice)的可能性,因此使用IRT/CAT做推荐引擎的知识点自适应学习产品都有一点“挂羊头卖狗肉”的嫌疑(但是知识点自适应系统并不存在这个问题)。

第二,这个问题与传统上的协同推荐算法,比如淘宝,具有本质区别。协同推荐的问题是,假设每一个用户的偏好不变但是用户之间的偏好不同,是否存在一个办法可以通过用户的行为对于用户进行分类,从而为每一个类别的用户提供更适合其偏好的产品或服务。与CAT系统一样,协同推荐算法从根本上否定了学习的可能性,因此其推荐逻辑不具有教学逻辑。因为有和你类似做题记录的学生做错了这道题,所以你也应该试试这道题。这是一个非常糟糕的教学逻辑(如果有任何教学逻辑的话)。

知识点自适应可以说是一个还有待进一步研究的领域。笔者在此仅阐述一个理论框架。

一个描述动态学习的系统首先要定义什么叫“学习”(learning)。一个直观的办法是把学习和掌握程度(mastery)联系起来,将其定义为低掌握程度到高掌握程度的转换概率。每一个掌握程度由一套可观察的表现来定义。比如,给定一道题,90分以上是精通,60-90是掌握,60以下是未掌握。学习可以定义为从“未掌握”到“掌握”的概率(渐悟),也可以定义为从“未掌握”到“精通”的概率(顿悟)。这并不是唯一的定义方法,但可能是最简单但是不失普遍性的定义方法。

定义了学习,就可以定义“学习差异性”(learning heterogeneity)。差异性是构造自适应系统的根本原因,否则最优的教学方案会是千人一面而不是千人千面。学习差异性可以抽象成:

(1)水平差异性:目标是“精通”,题目对于“未掌握”和“掌握”的学习者的效果应该不同

(2)速度差异性:目标是精通,起点是“掌握”,题目对于一个快速学习者和慢速学习者的效果应该不同。

如果接受这套定义,接下来有两个重要的实际问题需要回答:

(1)上述定义系统中的参数是否可以被数据估计?

(2)如果估计了这些参数,如何构建一个推荐逻辑?

遗憾的是,笔者自己的研究表明,问题(1)的答案可能是否定的。只有在特定的题目顺序结构下,题目的参数和用户的类型才能被估计。但是如果我们忽视速度差异性,问题(1)的答案可能是肯定的。

问题(2)与其说是一个技术问题,不如说是一个教学问题。笔者认为,推荐逻辑应该由“测评-教学”的两步循环来构成。在测评环节,练习推荐侧重于题目的区分度和测量精度,从而区分用户的不同类型;在教学环节,根据学生类型,练习推荐侧重于题目的教学效果。在下一个测评环境,练习推荐再测试学生的水平和类型,如此循环往复,直到学生达到指定的熟练程度为止。

此外,练习推荐也应该注意对于用户留存的影响,如果学生不持续投入地练习,不论推荐逻辑再优秀,也无法展现其应有的效果。

全栈数据工程师:独当一面

fullstack data analyst从0到1后,这个指南旨在帮助你成为一个可以独立地完整地交付用户价值,即从模型研发到服务维护的全生命周期开发。

1.基本功


1.1 理论基础

数据结构(CS 61b )和设计思想(CS 61c)是成为中阶程序员的必修科目。

1.2 编程哲学(*)

每个程序员都有自己的编程哲学,你应该早日形成自己的哲学。下面两本书是我的红宝书。每年读一遍,带着问题读,常读常新。

(1)Pragmatic Programmer: From journeyman to master (特别鸣谢付剑同志的推荐)

(2)Scrum: The Art of Doing Twice the work in Half the time

(3)每个程序员都应该读的书

2. Golang


专为云端+高并发+团队而生的工程语言。Python的确具有很强的泛用性,但是后端服务用Go更为给力。你也可以选择学习”write once , run debug everywhere”的Java。它会让你在当下更容易找到工作。

入门推荐:

(1) a tour of Go

(2) build Web application with Go (了解怎么在go get中利用github替代golang.org)

(3)Go语言标准库用例

 3. 机器学习


大部分数据科学家其实都是调库工程师和调参工程师。能够根据业务调整模型选择(aka 调库),根据具体数据进行特征工程(aka 调参),已经是不小的成就了。

练习方法

(1)入门级别:Applied Data Science with Python

(2)复制Scikit-learn里的主要模型的 code demo

(3)通读 周志华老师的机器学习或者Bishop大神的Pattern Recognition and Machine Learning。尽管这两本书常常被用来作为本科高年级入门的教材,但是如果能真正消化任意一本书,统计建模已经一马平川了。

4. 架构


测试驱动(TDD)是战术素养,而设计模式则是战略眼光。战术上的勤劳无法弥补战略上的懒惰。建议至少读一遍 Agile Software Development, Principles, Patterns, and Practices

 5.ELK


流式信息处理已经从最开始的log处理小能手变成一个完善的数据生态系统。其独特的数据储存、检索和使用的模式可以解决许多用SQL乃至NoSQL都很难解决的问题。

6.持续发布(continuous development)


在持续发布(continuous deployment)思潮的影响下,微服务已经成为主流架构模式。

Docker

Docker技术为规模化微服务提供了可能。此外,各种云平台也在docker化。因此不论是公司项目还是个人创业,docker都是必学必会的基本技能。

微服务和API

如何在Python 3中使用API

7.前端


Vue

网页前端框架,容易入门,适合小团队;在国内非常流行

 

Flutter

“革命性”mobile app 前端技术

全栈数据工程师:从0到1

全栈的定义

1. 具备在简单产品项目上将产品理念快速、有效地转化为产品价值的全部技术能力

2. 对于软件工程的生命周期的复杂性有初步认识,并能使用成熟方法和工具来控制复杂性

职能描述

你的主要任务是把代码写对(Code Right)。

一个合格的助理devops,能够维护一个Linux/unix的开发环境,进行利用既有平台工具实现单一应用服务的持续集成和持续部署(CI/CD)。为此,你应该掌握常见的shell脚本;掌握基于git的项目流程管理;熟练使用pipenv来维护软件虚拟环境;并使用docker及其关联的平台组件来构建CI/CD流程。

一个合格的助理工程师,能够独立完成一个模块的开发和测试。你能够向一个架构明确的项目中增补功能而不破坏现有代码或者降低整体代码质量;你能够编写必要的单元测试、集成测试和网页自动化测试;如果给你提供线上报错的堆栈,你能在合理的时间内找到bug所在并消灭之。为此,你应该了解计算机科学的基础性知识,熟悉最基本的设计模式,并践行测试驱动的代码开发和重构。

一个合格的助理前端开发,能够根据原型图实现网页开发。你能够渲染基础的网页组件;处理简单用户交互带来的前后端数据交互;你对于用户交互体验有基本的认知,能够察觉并优化易用性问题。为此,你应该熟悉H5和CSS的基本语法,了解MVC模式,能够使用一种前端框架,并且了解用户界面设计的基本原则。

一个合格的初级数据科学家,能够对于一个应用场景明确、数据操作化定义明晰的业务问题进行描述统计、简单假设检验、分类与预测。你能够从不同来源的数据库中获得你想要的原始数据,通过数据清洗构建特征,并利用成熟数据模型和流程得到结论。为此,你应该了解基本的统计学知识,掌握OLS/logit模型,学会调用常见的机器学习模型,并且具备基本的业务分析(Business Intelligence)能力。

在大多数公司,上述四个角色是4个不同的职位;而在我们团队,只有1个职位。因此,你一年内需要学习的,可能相当于别人三四年的经验。这是对你天赋、毅力和时间管理能力的重要考验。除了向书本和教程学习,你更需要向前辈和同僚学习:能够在code review过程中接受他们的建设性意见,并且积极向他们提出有意思的问题。

最后,你需要“学会上班”。遵守公司/团队的组织纪律,学会高效利用上班时间,学会团队合作,并开始有自己职业规划。


晋升规则

分数分布:

  1. 非技术要求 – 10
  1. 基础知识 – 20
  1. IT/CS – 5
  1. 编程 – 10
  1. 统计学 – 5
  1. 技术要求 – 70
  1. Server, Network and Hosting Environment – 10
  1. Data Modeling – 13
  1. Business Logic – 20
  1. Action Layer – 11
  1. User Interface – 6
  1. User Experimence – 5
  1. Product Value – 5

得分规则

(1a) 考核方法为项目,需要由申请者提交项目报告书;团队技术评审通过后,得到全部分数

(1b) 考核方法为面试,由面试官打分;考核方法为笔试,按笔试成绩比例给分

(1c) 未标明考核方法的,由申请者提交自评分数和陈述;团队技术评审酌情给分

(2)额外奖励分数由团队技术评审酌情授予

入职要求

完成全部必修课程(标记黄色高亮的是必修内容)

  1. 总积分达到50分
  1. 分类别积分最低积分要求
  1. 基础知识 >= 16
  1. 技术要求 – Server, Network and Hosting Environemtn >= 6
  1. 技术要求 – Data Modeling >= 9
  1. 技术要求 – Business Logic >= 10
  1. 技术要求 – Action Layer >= 6
  1. 技术要求 – User Interface >= 3

加薪要求

每积20分可以要求加薪一次

晋升T2要求

  1. 总积分达到90分以上
  1. 分类别积分要求:
  1. 非技术要求得分率不低于95%
  1. 基础知识满分
  1. 技术要求中的Data Modeling、Business Logic和Action Layer得分率不低于95%
  1. 技术要求中的单项得分率不为0

1.非技术要求 [10]
1.1 Google It [2]

定义:

使用Google作为搜索引擎;(大部分情况下)使用stack overflow

训练方法:

将Google做为默认地址栏搜索工具

将英语做为默认搜索语言

1.2 Ask Right Question [5]

定义:

你可以问一个愚蠢的问题,但是你不应该问一个没有思考过、没有探索过的问题

训练方法:

How to ask questions the smartest way By Eric Raymond and Rick Moen

How do I ask a good question by StackOverflow

面试考核:展示一个你在stackoverflow/github上提交的问题/issue,并说明它符合社区规范

1.3 Be A Team Player [3]

定义:

Trust, conflict, committment, accountability, results

Care personally, challenge directly

Radically Transparent

训练方法:

阅读 Five Dysfunctions of a Team by Patrick Lecioni

阅读 Radical Candor By Kim Scott

阅读 Principles By Ray Dalio

笔试考核

2 基础知识 [20]
2.1 IT/CS 基础知识 [5]

定义

理解互联网协议:IP地址,端口,socket,TCP协议

理解web工作方式:URL/DNS,HTTP协议,request种类,response结构,状态码

CPU管理:CPU, Core, 进程/线程/协程

训练方法:

互联网协议入门 by 阮一峰

web工作方式 by Asta Xie

Intro to Threads and Processes in Python, by Breden Fortuner

笔试考核

2.2 编程基础知识 [10]

2.2.1 数据类型 [2]

string,int,float

list,tuple, dictionary, namedtuple

data abstraction

2.2.2 控制 [2]

if, for, while, yield

2.2.3 组件 [3]

function, higher order function(decorator)

recursion

object

function oriented programming

object oriented programming

2.2.4 IO [1]

txt, csv, json的读写

bytes

unicode

2.2.5 python包 [2]

os(主要是path函数)

sys(主要是subprocess和命令行传参)

collections(这里面函数值得研究)

black

ipdb

datetime

训练方法:

cs61a by UC Berkeley

Learn python the hard way by Zed Shaw

A Hitchhiker’s guide to Python by realPython

笔试考核

2.3 统计学 [5]

事件/随机变量

条件概率/独立事件/贝叶斯

常见离散分布(Bernoulli,Binomial, Poisson)

常见连续分布(Uniform,Normal,Beta)

统计量(均值,方差,分位数)

从分布中抽样

训练方法:

Think Stats(Chp.1,2,5,7) by Allen B Downey

Think Stats(Chp.3,4,6) by Allen B Downey

笔试考核

3技术要求 [70]
3.1 Server, Network, and Hosting Environment [8]
3.1.1 Shell [2]

定义:

yum/apt-get/brew isntall

nohup

文件通道符

crontab

grep

训练方法:

The art of command line by jlevy

笔试考核

3.1.2 GIT [4]

定义:

git pull – commit – push

git checkout

git rebase

git merge / resolve conflict

git tag

训练方法:

Git tutorial,着重学习workflow management

面试考核:在一个toy project上展示上述git操作

3.1.3 PIPENV [2]

定义:

pipenv –py / –three/two / –rm

pipenv install (–dev) (–skip-lock)

pipenv install git+

pipenv shell

pipenv graph

理解Pipfile和Pipfile.lock的作用

训练方法:

pipenv 文档

面试考核:从0构建一个pipenv,分开安装生产/开发包,通过git在另一个服务器上复制该环境

3.1.4 vim [2]

定义

(1) 学使用vim,并配置以下插件

syntastic(或其他语法检查)

youcompleteme(或其他自动补全)

black

(2) 能够自定义快捷键

训练方法

https://vim-adventures.com

面试考核:在vim8(with python3 support)上配置vimrc来安装这些包,确保可以使用

3.2 Data Modeling [13]
3.2.1 数据库类型 [1]

定义:

解SQL和NO SQL的概念和优劣

理解Key-Value Store的优势和局限

理解ElasticSearch的基本原理

训练方法:

Database by 付剑

笔试考核

3.2.2 MySQL [4]

定义:

create table的基本语法

left /inner / right join

group by

order by

index

insert (overwrite)

load data in file

(transaction)update

训练方法

HackerRank SQL module

sqlalchemy tutorial

项目考核

3.2.3 Mongo [5]

定义:

insert

delete

update

replace

find

unqiue

elemMatch

group_by / aggregate

训练方法

pymongo tutorial

mongoengine tutorial

项目考核

3.2.5 ELK [3]

定义:

Kafka的基本概念和用法

ElasticSearch基本语法

Kibana制作visualize dashboard

训练方法

python kafka tutorial

python elasticsearch tutorial by Julie Qiu

项目考核

3.3 Business Logic [22]
3.3.1 Acceptance Test [2]

定义

behavior driven development

behave框架

训练方法:

introduction to bdd by Dan North & Associates

笔试考核

3.3.2 Unit Test [2]

定义

单元测试编写的基本原则

python unittest(特别是mock和monkey patch)

训练方法

A programming episode by Robert C. Martin, Micah Martin

python web tdd by Harry Parcival

项目考核

3.3.3 测试自动化[1]

定义

使用selenium进行web测试自动化

训练方法

python selenium tutorial

3.3.4 设计模式 [5]

定义

Single Responsibility

Open Close Principle

Liskov Substitution Principle

Interface Segregation Principle

Dependency Inversion Principle

训练方法:

Agile Principles, Patterns, and Practices in C# (Chp.8-12) By Robert C. Martin, Micah Martin

SOLID in Python by dboyliao

项目考核:提交一个code refactor/design例子来证明你在工作中使用了这些原则(LSP可以不考核)

3.3.5 Refactor [4]

定义:

了解基本的重构原则

熟悉重构的一般步骤

train your nose for the smell of the bad code

训练方法:

Refactoring by Martin Folwer

Clean Code:A Handbook of Agile Software Craftmanship By Robert C. Martin

3.3.6 性能监控 [1]

定义:

使用python profiler和snakeviz对于代码进行性能监控

能够进行API压力测试

训练方法:

cProfile tutorial

3.3.7 经典统计(or 计量经济学)[3]

定义:

OLS模型进行预测

OLS进行假设检验

训练方法:

Think Stats(Chp.10,11) by Allen B Downey

面试考核

3.3.8 机器学习 [4]

定义:

数据清洗(ETL)

特征提取

svm/logit/decision tree/gbdt/random forest选型

cross-validation调参

训练方法:

sckit-learn CV调参官方教程

项目考核

3.4 Action Layer [11]
3.4.1 MVC [1]

定义

理解模型层、展现层和控制层的功能及这种设计模式的优点

训练方法

Simple Example of MVC Design

笔试考核

3.4.2 API [1]

定义

API设计

flask api服务

训练方法

Effective API Design

项目考核

3.4.3 交互控件 [2]

定义:

提供基本交互:按钮、下拉、alert、弹窗

训练方法:

Forms by 付剑

项目考核

3.4.4 Flask [4]

定义:

能够用flask完成后端驱动的网页服务

训练方法:

CURD application with Flask by Mbithe Nzomo

Test a Flask App with Selenium Web Driver by Mbithe Nzomo

Flask-bootstrap Tutorial

项目考核

3.4.5 Asyncio [3]

定义

asyncio

aiohttp

motor

训练方法

Get to grips with asyncio in Python 3 by Robert Smallshire

A Guide to Asynchronous Programming in Python with Asyncio by Roman Gaponov

项目考核

3.5 User Interface [6]
3.5.1 HTML5 & css[5]

定义:

元素:doc/ p / div / table / img/ hyperlink / iframe

属性:height, width, color, align, position, etc

事件:windows, form, keyboard, mouse, etc

训练方法

Learn HTML by CodeAcademy

项目考核

3.5.2 基础数据可视化工具 [1]

定义:

Tufte 可视化原则

散点图

条形图

线图

概率直方图

boxplot

训练方法:

Matplotlib Intro Tutorial

Matplotlib Tutorial

项目考核

3.6 User Experience [5]

定义

尼尔森十大交互原则

笔试考核

3.7 Product Value [5]

定义

给定AB Test数据,进行假设检验分析

Minimum Viable Product

训练方法

Think Stats(Chp.8,9) by Allen B Downey

面试考核

 

基于IRT的计算机自适应测评系统

本文将介绍在教育模型中理论基础最完善且使用最广泛的自适应算法:计算机自适应测评系统(Computerized Adaptive Testing, CAT)。大家耳熟能详的一些计算机测评服务,例如ETS的GRE和TOEFL,都采用CAT作为推荐引擎。此外,CAT所依赖的测评理论,即项目反应理论(Item Response Theory, IRT),是心理测量学(psychometrics)的中流砥柱,有逾40年的理论研究基础,发展非常完善。最后,中国大部分教育技术公司在使用的自适应算法,可能不超过CAT的范畴。

本文首先介绍CAT的直觉基础,然后简要介绍其所依赖的IRT模型,并描述一种最简单的CAT工程设计。文章最后简单批判CAT作为一种学习算法的不足。

相较于传统的纸笔考试,CAT的优点是在相同题目数量下所达到的测评精度更高。或者反过来说,为了达到相同的测评精度,CAT所需要的题目更少。CAT能够实现更高效测评的直觉原因就是它能针对不同的作答挑选信息量最大(aka最具有甄别性)的考题。IRT模型是对于考题对于考生的信息量的定量评估的方法论基础。

 

I.自适应测评的理论基础

假设纸笔考试和计算机考试(CAT)的唯一区别在于是否存在自适应,那么什么时候CAT比纸笔考试好?这个小节将回答这个问题。

在这个小节中,我们将假设学生可以从一个能力维度上被分为两类人:学霸和学渣。顾名思义,学霸能力强,学渣能力弱。假设学霸和学渣在人群中各占50%。

(A)

假设有两道题,分别为送分题(易)和压轴题(难)。学霸和学渣都可以做出送分题,但只有学霸能做出压轴题。

假设你的目标是区分一个学生究竟是学霸和学渣,那么你应该出一张怎么样的卷子?

如果把送分题给学生做,不论是学霸和学渣都会做出来;其结果对于判定学生类型毫无帮助。如果把压轴题给学生做,做出来的就是学霸,做不出来的就是学渣;其结果对于判定学生类型非常有帮助。

让我们用更加严谨的数学语言来翻译上面的直觉推理(假设你熟悉贝叶斯定理)。假设你给了学生难题(Y_h),学生答对了(1)。此时,这个学生是一个学霸(X=1)的后验概率为

    \[P(X=1|Y_h=1) =\frac{P(X=1,Y_h=1)}{P(Y_h=1)}=1\]

与此相反,如果学生答错了,他为学霸的后验概率为0%。如果我们给了学生易题,学生答对了,他是学霸的后验概率依然是50%,和先验概率没有改变。(注意当给学生送分题时,不可能出现错误)

考卷/答案组合10
100%0%
50%NA

上表(计算过程参见这个链接的例1)列举了所有试卷/答案组合下的学霸后验概率。给定答案的组合,最优的试卷组合应该给与尽可能极端的后验概率(即最小化信息熵)。例如,当学生答对时,难题优于易题(100%>50%)。

综上所述,在这个情况下,卷子里只要有压轴题就够了。最优试卷方案唯一,因此纸笔考试和CAT一样。

(B)

案例A的结论主要来自于学生水平和解题结果存在确定关系的超强假设。而事实上两者的关系有不确定性。学霸也有失手的可能,学渣也有蒙对的希望。不可观察的学生能力和可观察的解题结果之间的不确定性是学习数据分析的根本问题

现在假设有难中易三道题,其中:

(1)难题学霸有60%的概率做出来,学渣有10%的概率做出来;

(2)中题学霸有80%的概率做出来,学渣有60%的概率做出来;

(3)易题学霸有95%的概率做出来,学渣有90%的概率做出来。

假设你的目标是尽可能的精确地判断学生类型,你应该怎么出卷子?

答案是三道题全做。每一道题都有一定的区分度,信息量不为0。如果我们希望最精准的类型判断,每一道题都有价值。因此,如果可以不计代价地进行测评,选题没有什么价值,纸笔考试和CAT一样好。

(C)

然而事实上测评这件事情本身是有成本的,主要体现在时间成本;因此,大部分的考试都有时间限制。所以一个更加现实的目标是:

假设目标是在两道题内尽可能精确地判断学生类型,你应该怎么出卷子?

让我先给出答案:最优的测试方案取决于学生回答。因为CAT可以根据学生的作答进行选择,而纸笔考试不行。因此,给定相同题库和相同测试长度,CAT比纸笔测试要强。

[1]  纸笔考试

根据贝叶斯概率公式,我们可以得到全部试题+答案组合的学霸后验概率(具体计算过程请查看这个链接的例2[1])。因为只有两类学生,所以只要最佳辨认学霸的方法也是最佳辨认学渣的方法。

考卷方案/答案组合11100100
难+中89%75%37%18%
难+易86%75%31%18%
中+易58%40%34%20%

类似的,给定答案组合,后验概率最为极端的试题组合为最优。例如,当两题都答对时,难题加中题的组合最优,因为它的后验概率最大(89%>86%,89%>56%)。上表告诉我们,大部分情况下(除了第三列之外),难中的组合是最优的试卷组合。因此纸笔试卷会选择“难题+中题”的组合

[2] CAT出题

CAT的优势在于它在出第二道题时,已经观察到了第一道题的结果。因此,它在第二题可以做出更好的选择。

通过类似于(A)中的计算,CAT的第一题会选择难题。假设学生做对了,他是学霸的后验概率为86%,他是学渣的后验概率为31%。第一题的后验概率会成为第二题的先验概率;并且此时我们从题库中刨去难题,只需考虑中题和易题。

第一题结果
试卷/答案1010
89%75%36%18%
86%75%31%18%

上表告诉我们,当学生第一题做对时,第二题应该出中题;当学生第二题做错时,第二题应该出易题。因此,CAT的选择是 难+中(第一题对)/难+易(第一题错)

在这个具体例子中,CAT在学生第一题做错,第二题做对的情况下比纸笔考试的后验概率方差有所降低,尽管差距并不是很明显(0.1476 Vs. 0.1474)。

2. IRT模型

第一节简单介绍了CAT的原理。因为测试题对于隐藏能力的探测具有不确定性,而且相同测试题对于不同能力的学生而言,不确定性不同。因为CAT可以根据应试者的回答动态选择测评不确定性最小的题目,因此和纸笔考试相比,它达到相同的精度需要更少的题目,或者使用相同的题目数获取更好的精度。

第一节的分析做了一些非常强的假设:

(1)我们知道学生的类型(学霸Vs学渣)

(2)我们知道不同类型的学生在各个测试题上的正确率(eg,学霸难题60%正确率)

在现实中,这两个假设都不成立。因此我们需要一个模型来提供这两个重要的信息。项目反应理论(Item Response Theory,IRT)是提供这些信息的最流行的模型。关于IRT模型的较为详细的介绍在可以参见这个链接(ETS在2013年提供了一个IRT发展的综述)。常见的IRT会做了以下的假设:

(1)被试者能力是一维的(\theta

(2)被试者能力是连续的(即不存在学霸VS学渣这样的有限多且可被解释分组,但是不同学生间可以排序)

(3)题目参数(\alpha,\beta)和学生能力(\theta)关于正确率(P(Y=1),假设题目只有对错两种)的函数对应是

    \[P(Y=1|\theta,\alpha,\beta) = \frac{e^{\alpha(\theta-\beta)}}{1+e^{\alpha(\theta-\beta)}}\]

通过数据估计\theta,\alpha,\beta就可以得到学生能力的分布以及不同学生在同一道题上的正确率分布。此外,这个结构式对于某些CAT选题算法而言,也是必须的。

3. 最简CAT的工程设计

上面两节介绍了CAT的原理以及IRT的概要,这一节将描述一个最简单(也是最经典)的CAT工程设计。这一节将以数学和符号为主,只想大概了解CAT的读者可以直接跳到讨论CAT扩展的第四节。

题目选择的算法有很多。这里我们介绍历史最悠久的一种:最大信息原则(Maximum Information Criterion)。

 

记学生id为i。学生i的真实能力值为\theta^i,学生i在第t道测试题的预估能力值为\hat{\theta}^i_t

记题目id为j。题目j的参数为\Theta_j。在二参数IRT模型中(第二节的例子),\Theta_j= \{\alpha_j,\beta_j\}

我们只把学生能力当做变量,把题目参数和做题结果都当做常量。

在二参数IRT模型下,记题目参数和学生参数与正确率的对应关系为

    \[p^i_j(\theta^i) = P(Y^i_j=1,\theta^i|\Theta_j) = \frac{e^{\alpha_j(\theta^i-\beta_j)}}{1+e^{\alpha_j(\theta^i-\beta_j)}}\]

这种函数设定的好处是,Fisher information function(一种度量信息的方法)是线性可加的。因此,假设学生已经做了k-1题,第k题的Fisher Information就是

    \[I_j(\theta^i) = \frac{[p^i_j'(\theta^i)]^2}{p^i_j'(\theta^i)[1-p^i_j'(\theta^i)]}\]

其中

    \[p^i_j'(\theta^i) = \frac{\partial}{\partial \theta^i} p^i_j(\theta^i)\]

如果\theta^i是已知的,那我们就可以计算每道题的Fisher Information,然后选取最大的那个题。然而遗憾的是,我们并不知道\theta^i。所以在每一步中,我们都用估计值\hat{\theta}^i_t来替代\theta^i。这个估计值可以这么估算

(1)初始化

给定学生能力值的先验概率分布g(\theta)

    \[\hat{\theta}^i_1 = \int \theta g(\theta) d\theta\]

(2)后续迭代

之后每一步的\hat{\theta}^i_k都是似然函数的最大似然估计值(Maximum Likelihood Estimator),其中似然函数是

    \[L(\theta) = \prod_{j=1}^{k-1} \frac{(e^{\alpha_j(\theta-\beta_j)})^{Y^_j}}{1+e^{\alpha_j(\theta-\beta_j)}}\]

 

 

4. CAT的高阶话题

CAT作为一个有近30年历史的学科,其理论深度和宽度远远超过本文所讨论的内容。有兴趣的朋友可以阅读由Wim J. van der Linden和Cees A.W. Glas编辑的Computerized Adaptive Testing: Theory and Practice。这本书覆盖了2000年左右CAT发展。

大体上说,一个完善的CAT系统需要解决以下几个麻烦的问题:

(1) 第三节假设题目参数是已知的,而实际上题目参数是未知的。怎么解决题目参数估计误差所导致的题目选择偏差?

(2)因为学生能力估计是有误差的,如果选择区分度高的题,可能导致估计该步信息失准

(3) 怎么评估题库题目的质量?怎么确保题库有足够多的题目可以应付多场考试?(例如GRE要保证70套完整题目组)怎么确保题库题目更新迭代不影响不同考试间的可比性(GRE题目的寿命是3个月)

(4)如果能力是多元的怎么办?更麻烦的是(对于国内中高考尤其是如此),如果一道题涉及多个能力项怎么办?

(5)怎么处理额外的试卷限制,例如考试时长,平均分限制和题目曝光总量控制

 

5.CAT作为自适应“学习”算法的不足

CAT作为一种测评算法已经被证明是可行且高效的。 随着人机交互界面的改善和算法的进步,计算机将不仅可以完全兼容纸笔试题(主要是主观题),而且可以实现许多纸笔考试难以完成的试题(例如VR支持的实验动手测试)。因此,CAT将会在测评领域取得更进一步的发展,这是毋庸置疑的。

然而,作为一种学习算法,CAT却是先天不足。CAT假设学生在做题过程中,其能力值是不变的;这从根本上否定了学习的可能性。一个否定学习可能性的算法,如何用来指导教学推荐呢?因此,仅仅是CAT(或者IRT)是不能够独立支撑起一个学习推荐系统的。

当自适应学习发生在知识点间时(参考我的这篇文章),CAT可以作为测评模块,配合知识空间理论(比如ALEKS)或者专家系统(比如Khan Academy)的教学模块,组成一个智能学习推荐系统。

 

适用于在线服务的A/B测试方法论

简介:

这篇文章旨在介绍适用于为在线服务进行A/B测试(A/B Test)的方法论。中文网络中目前还缺乏全面的入门级介绍。

我将首先讨论在线服务业进行A/B测试所考虑的决策问题,然后介绍两种不太常见的统计测试:序列概率比测试(Sequential Probability Ratio Test, SPRT)和基于多臂老虎机(Multi-armed Bandit, MAB)算法的测试。

I.不只是P-Value

经典统计学会用如下的方法进行A/B测试:

(F1)选择一个样本N

(F2)随机平分到A/B组

(F3)计算原假设H_0:\mu_A=\mu_B 的t统计量(双样本+未知方差)所对应的p-value

(F4)如过p-value小于一个特定的显著性水平(例如0.05),那么就拒绝原假设,否则啥也做不了。

基于农业和工业生产体系产生的经典统计检验方法并不一定适用于在线服务业。这不完全是因为p-value经常被误解了,更多是因为经典假设检验不能满足在线服务业的业务要求。

1.1 为持续改进服务的AB测试是决策问题而不是推断问题

大部分时候,我们只关心是否A方案比B方案好,而不关心A方案比B方案好多少。换句话说,我们只关心实验的业务正确性(decision),而不在乎实验的统计可靠程度(inference)

从这个角度来看,双边检验是一个糟糕的决策问题。拒绝原假设H_0:\mu_A=\mu_B 并不能告诉我们到底应该选择A方案还是B方案。单边检验H_0:\mu_A<\mu_B 是一个更好的原假设。如果拒绝了原假设,那么应该选择A方案;否则就选择B方案。

假设检验还可以有其他形式。我们可能并不关心A方案和B方案是否完全一致(贝叶斯主义者会说永远不会一致),我们可能关心A方案的B方案差距是否在一定范围内。如果是,那么我们应该做出选择,否则可以保持现有的方案。这样的原假设检验是等价检验(equivalence test):H_0: |\mu_A-\mu_B| < \epsilon

总而言之,F3不适合在线AB测试。事实上,假设检验的鼻祖Ronald Fisher反对将原假设检验作为决策依据。

1.2 不仅关心实验结果,而且关心实验成本

在线上运行试验(特别是大规模实验)时,可能会影响用户体验,从而影响用户留存等关键业务指标。除非主管老板正好是实证主义的狂热信徒,否则他们可能会对于做实验颇有微词。如果你运气好,去了一家完全由A/B测试驱动的公司,那么实验成本的问题不仅没有消失反而更为重要了。

因此,我们希望在实验过程中,尽可能降低优势方案向用户曝光的频率。要实现这个目标有两种方法,动态结束机制和非均衡分组。动态结束机制是指一旦确认某个方案胜出,就立即停止实验;采用这种方法意味着F1不适合在线AB测试,因为我们不必死等到耗尽预订样本为止。非均衡分组是指向在当前估计下优势方案多分配用户,我们将在多臂老虎机一节中更加详细地讨论这个问题;采用这种方法意味着F2不适用在线AB测试。

1.3 样本是序列生成的

经典统计学暗中假定数据是同时生成的,而不是依次生成的(大概要归功于假设检验的始祖Ronald Fisher是个农业统计学家)。然而在线服务业的用户总是依次到达的。这个重要特征使得我们可以兼顾实验可靠性和实验的成本,也是下面两种检验方法的核心特征。

II.序列概率比测试

序列概率比测试(Sequential Probability Ratio Test,以下简称SPRT)可以认为是经典假设检验在序列样本环境下的变体。在相同显著性(significance)和检验力(power)下,SPRT可以比经典t检验结束的更早,需要的样本更少。而其代价就是更加复杂的统计量和更加复杂的决策程序。

对于SPRT理论性质和正规检验方法感兴趣的读者可以钻研David Seigmund(1985)的Sequential Analysis一书。在这里我们提供两个更为实际的检验方法。第一是optimizely的统计检测引擎,另一个是Evan Miller的简易SPRT。前者虽然提供一个严格的False positive边界,但是没有完全披露其核心参数,因此不能下架即用。后者是个傻瓜式的检验,但是其显著性和检验力堪忧,能够适用的业务场景也较少(几乎仅限于二元变量)。

如果你对于显著性这个概念情有独钟,那么SPRT可能是一个值得投入时间研究的方法。

III. 多臂老虎机测试

如果SPRT所涉及的数学水平是精深的话,那么真正理解多臂老虎机(以下简称MAB)问题所需要的数学水平已经是非人了。Scott(2010)为MAB问题的历史提供了一个深入浅出的回顾。O’Reilly有一本书介绍了MAB的经典解法和其Python代码

幸运的是,MAB有一个名为汤普森抽样(Thompson Sampling)的贝叶斯解法。它容易理解,容易执行,扩展性强;因此非常适合用于在线AB测试。事实上,它正是Google AnalyticsYahoo!Bing实际使用的方法。

关于汤普森抽样的技术细节请参见Google Analytics的帮助菜单和例子Scott(2010)提供了更为正式的表述。在这儿我主要讨论一下GA算法的核心思想。

3.1 什么是多臂老虎机

Bandit是美国人给老虎机取得别名。下图的老虎机是一个独臂老虎机。你拉一下摇杆,得到一个奖励。进一步假设奖励是取值0,1的随机变量,取值为1的概率是p。

假设这个老虎机有多个摇杆,从1到N编号,每个摇杆返回奖励的概率为p_1, p_2, \dots, p_n ,但是这个概率你不知道。每个回合你可以选择拉动一个摇杆。

假设各个摇杆的返奖概率不变,使用什么策略可以使得累计奖励最大化?

简而言之,这就是多臂老虎机问题。回顾第一节关于在线服务优化的讨论,可以发现两者间的强关联:两者的核心目标都是做出决策;两者的核心考量都是成本收益,两者的数据生成过程都是序列化的。

3.2 探索与利用的权衡

如果用经典t检验的思路来解决多臂老虎机问题,你的策略是这样的:

(1)在1到tN轮,确保每个摇杆拉t

(2)在tN结束时,计算每个摇杆的样本平均\hat{p_i},选出样本返奖概率最高的摇杆i^*

(3)从第tN+1轮开始,一直选择摇杆i^*

tN+1轮开始的策略是纯利用(Exploration):即选择实证奖励最高的选项(play the winner);而前tN轮所用的策略是纯探索(Exploitation):即无视经验奖励,让概率做决定。

一般而言,像这样泾渭分明的策略组合不是最优的。在实验初期,应该鼓励探索,因为我们不知道哪个选项更好。但是,当有证据表明某几个选项相对更优时,应该增加“利用”的比例。这样做有两个好处:第一,多选赢家可以提高策略的整体收入;第二,多选赢家可以比平均分配更快地降低标准误,从而提高我们对于“赢家估计”的信心。因此,利用的比例应该随着时间的增加而增加。

汤普森抽样提出了这样一种直观的贝叶斯解决方案:

在每个周期计算“摇杆i是最优摇杆”的后验概率,以此作为下一轮随机分配摇杆的依据。

汤普森抽样保证”在实验过程中“坑用户”的比例是最小的。此外,如果你懂一些贝叶斯模型,你就可以看到这种方法的灵活性和可扩展性有多强。

3.2 停止条件:潜在剩余价值

尽管汤普森抽样看似秒杀经典t检验,但是在决策过程中它有一个致命问题。所有的MAB策略本身都不是一个统计检验,因为它们没有停止条件。汤普森抽样会跑到海枯石烂,但是实际操作不允许无限长的实验。目前为止,还没有人公开发表一个简单靠谱的终止条件。和经典t检验相比,这是基于MAB测试的一个重要缺点。

Google Analytics推荐使用“潜在剩余价值”(Potential Value Remaining,PVR)来判断实验结束的时间。当选择摇杆i^*后,我们想知道(基于返奖概率的后验概率分布)如果选择其他摇杆的潜在收益有多大。如果这个收益很小,那么我们就有足够的理由的选择最优解;如果这个收益还很大,那么还需要收集更多的数据来消除对于返奖概率的不确定性。事实上,PVR并不是一个值,而是一个分布。因此,潜在收益“大小”需要用两个数(\epsilon\delta)衡量,分界线\epsilon,分界概率\delta

潜在最优收益比目前最优收益大\epsilon%的概率小于\delta

比如,Google Analytics默认的设置是(0.01,0.05),即潜在最优收益比目前最优收益大1%的概率不到5%。

需要警告读者的是,即使A/B方案没有任何区别,PVR停止政策也会导致相当一部分的实验在有限时间内终止;并且随着时间的延长,这样第一类错误的概率会不断增加。这与经典t检验下固定pvalue,样本越大,显著性越小的特征正好相反。如果你非常关心第一类错误概率,那么MAB测试不是一个好选择

IV. 什么时候应该关心显著性?

在假设检验中,我们一般讨论第一类错误(Type I Error)和第二类错误(Type II Error)。假设原假设为H0:你没有怀孕,被择假设为H1:你怀孕了。那么,两类错误描述的情况如下图所示。

Scott在好几处都提到一个观点,那就是线上实验根本不用考虑第一类错误,因为其代价极小;反而是第二类错误犯了才致命。事实上,Scott反对的并不是第一类错误,而是双边假设检验。

考虑形如H_0:\mu_A=\mu_B 下第一类错误和第二类错误的业务含义。如果犯了第一类错误,A方案和B方案完全等效,我们错误认为其中一个方案更好。这有什么实际代价么?如果代码转换和用户体验变化的成本可以忽略不计(对于小改变而言的确如此),那么第一类错误的代价的确是0。与此恰恰相反,假设我们犯了第二类错误,并且假设新方案是更优的选择,我们就错过了一个永久改进的机会:这是一个代价不菲的错误。

当产品线稳定后,持续改进只能从细节入手时,Scott的批评是非常有用的。因为PM们能想到的改进都已经做了,意外惊喜靠人的想象力来发掘已经不太现实了;相反,用算法生成大量组合,进行持续测试和优化,说不定可以积跬步而致千里。因此对于诸如Google或者Facebook这样的公司来说,用实验主导开发是更合理的选择。

如果产品线不稳定,实验数据被用来做改版的调研,此时我们在做推断,而不是决策。因为人很容易被随机性所欺骗,看到海市蜃楼般的改进道理;所以实验方法论应该设计的更为保守。如果因为第一类错误而导致失败的all in,这是一个代价不菲的错误。

因此,我个人推荐使用汤普森抽样作为自动化实验体系的统计检验方法,使用经典t检验作为战略决策实验的统计检验方法。

延展阅读

为了提高可读性,本文避开了以下重要话题。这些问题有助于我们更加深入地理解假设检验与业务的契合。有兴趣的童鞋可以从这些博客出发,进一步阅读:

(1)频率学派贝叶斯学派关于p-value的相爱相杀

(2)重复显著性检验(repeated significance test):为什么Bayesian Test或者不是解决方案。我个人认为信贝叶斯又信p value属于人格分裂,Andrew Gelman有更加科学的解释(下面的评论值得详细阅读!)。

(3)多重对比,为什么过度的(简易)AB测试是伪科学

关于经典t检验应该怎么做,实验经济学大神John List(2010)有一个非常实用的指导手册。经典t检验绝不是把样本五五开这么简单。