Bayesian Diagnosis Tracing Model: Assigning Blaming for Multiple Knowledge Components (Draft)

                                                                                                                                                               I.        Introduction

When a practice item is linked to multiple knowledge components, there are no widely accepted best practices on how to assign blame. In the context of mathematics education in China, the blaming problem comes into prominence as early as second grade. Despite its practical importance, this problem is under-studied in both the literature and the industry. Several solutions known to the authors are flawed as formative assessment tools, as we will discuss in the next section.

This paper proposes a new framework, Bayesian Diagnosis Tracing (BDT), to deal with the blaming problem in a logically consistent way without losing track of learning progress. The BDT model combines two well established streams in the learning analytics literature: the research on Bayesian Knowledge Tracing model and the study of procedural misconceptions. In a nutshell, the binary response in the BKT model is replaced with a vector of misconception diagnosis, allowing an intelligent tutor to mimic the reasoning of a human tutor.

                                                                                                                                          II.       Relevant Theories of Learning

A.   The Bayesian Knowledge Tracing and the Cognitive Diagnosis Model

The BKT model is the most widely accepted analytical framework in modeling the learning process. There are two implicit assumptions. The first assumption is that each practice item maps to ONE knowledge component. The second assumption is that wrong responses are qualitatively the same conditional on the latent state[[1]]. In the context of multiple knowledge components, the first assumption is clearly violated. A common practice is to pretend that the learner practices N separate items that each map to one knowledge component. If the learner answers the original item correctly, they answer N artificial items correctly. Otherwise, the learner fails all N artificial items. This method has a fatal logic inconsistency. In the case of a correct response, then the components are treated as if they were connecting by an “AND” gate. In the case of a wrong response, then the components are treated as if they were connected by an “OR” gate. Both statements cannot be true for the item in question.

The Deterministic Input Noisy “And” Gate (DINA) model avoids such logical fallacy. However, DINA model, and likewise the family of cognitive diagnosis, cannot replace BKT model because it has no learning process. Tracing the progress of a learner is a must-have feature of the Intelligent Tutor System (ITS). In addition, the DINA model only uses the binary response, which means it throws away the information encoded in different responses.

To our best knowledge, there is not any analytical framework that can logically handle the problem of blaming multiple knowledge components in the context of dynamic mastery tracing. The ambition of this paper is to do just that.

B.   Procedural Misconceptions

Inspired by the study of procedural misconceptions by VanLehn(1990), this paper to propose a semi-automatic wrong response generator based on a data informed expert system. Such data informed expert system is import because the distribution of wrong responses has a long tail. Without the help of the frequency table based on large amount of data, experts are likely to only recall a few common mistakes, which probably accounts for less than 20% of the cumulative distribution. However, without the help of pedagogical expert, one cannot make sense of the wrong answers.

                                                                                                                                    III.      Enabling Technological Advances

A.   Variant, Solution Tree and Automatic Diagnoses of Procedure Misconceptions

This paper defines the solution tree as all possible paths of mathematical reasoning for solving a problem, including those of correct reasoning and those of incorrect reasoning[[2]]. A variant is defined as the class of problems that are identical in solution tree[[3]] but different in application settings[[4]]. In essence, the distribution of numerical responses of an instance can be generated from the distribution of algebraic responses of its variant when the parameter of the instance is plugged in. The application section offers an example of using solution tree to generate responses.

When given a wrong response of an instance of a variant, the analytical system can trace back the solution and accurately blame the components that contribute to the error[[5]]. Under some assumptions, the answers of the practice sequences can be split into K answer sequences, one for each knowledge components, and then the learner’s mastery on each knowledge components are estimated by independent HMM models.

B.   Bayesian Diagnosis Tracing Model

Let  be the state vector of k knowledge components at time t, . Let  be the state transition matrix. When the response is diagnosed as a vector of diagnosis , .

The likelihood is given as

The state transition is

If there are K knowledge components, each with M states. The state transition matrix T  is size . If there are L possible diagnosis combinations, the observation matrix E  is size . In real applications, even the sizes of K,M,L are reasonable, the model still has too many parameters to estimate. Practically, the joint likelihood has to break into the product of the likelihood of each knowledge component. In the product form, each component can be estimated by an independent HMM.

The product form requires the following assumption:

A1: The learning process of each component is independent.

A2: The diagnoses of each knowledge components are exchangeable[[6]]

A3: The symptom of each knowledge components is not related to other components.

                                                                                                                                               IV.      Real World Applications

This paper illustrates the Bayesian Diagnosis Tracing model, and its contrast to the classical BKT model, with data collected during Oct.2018 and Dec.2018 in a Chinese learning app. About one thousand students finished three items in a row. After answering each item, the student knew if she got it right. In the case of a wrong answer, the correct answer was revealed on the same screen as the mark and the solution procedure was also revealed in the next screen.

Here is the translation of the three items.

Q1: The school has a pool, 16m in length and 5m in width. To setup a fence around the pool, the length of the fence is ____ m.

Q2: The width of a rectangle is 3cm. The length is twice the width. The circumference of the rectangle is ____cm

Q3: Boy: The length of the basketball court is 28m and the width is 15m.

Girl: I walk around the court twice.

Question: The girl has walked ____m in total.

These are instances of three variants, consisting of two key knowledge components: calculating circumference of a rectangle given length and width (K1), calculating the product given multiplicand and multiplier(K2). The difference between Q2 and Q3 shows that procedures are not sufficient to distinguish variants.

For each component, the misconceptions are listed in the following table

Knowledge Component Right formula Misconception Symptom
K1 W*2+L*2

(W+L)*2

Wrong formula W*L

L*4

W*4

(W+L)*4

Flawed execution W+L

L+W*2[[7]]

W+L*2

L*2[[8]]

W*2

K2 X*Y No multiplication Y

X

Mistake for addition X+Y

The solution tree of Q1 is just P1. Q2 is K2->K1. Q3 is K1->K2. When multiple procedures are involved, the wrong responses are generated by the convolution of each procedure. For example, for Q2, K2 generate 4 intermediate answers. Taking each as an input to P1, it generates 8 answers (but only 4 category labels including right). In total, Q2 has 32 leaf nodes. If none of the leaf nodes produce the same answer, then each answer pins down a particular set of procedure misconception(s). However, when different leaf nodes produce the same answer, we rely on pedagogical expert to decide which set of misconceptions are more likely and choose it as the diagnosis.

There are two other types of special diagnosis, give-up and calculation error. Give-up are defined as answer 3/5/8[[9]] or a number from the question text, such as 16 in Q1 or 28 in Q3. Give-up does not necessarily mean the student cannot do it, but more likely not bother to. Nevertheless, if a wrong answer is identified as give-up, then all procedural diagnoses are give-up.  Calculation error is defined as wrong answers that do not contain any procedural misconceptions, for example 33[[10]] for Q3. If a wrong answer is identified as a calculation error then all procedural diagnoses are right. A wrong answer is labelled as no-diagnosis if it is not diagnosed with procedural misconceptions, nor is marked as give-up, nor is marked as calculation error [[11]].

Table 1 shows the composition of the wrong responses

Table 1
Question Procedural Misconceptions Give-up Calculation Error No-diagnosis
Q1 27% 10% 8% 55%
Q2 41% 47% 0% 13%
Q3 58% 6% 6% 31%

Among the identified procedural misconceptions, Table 2 shows the share of blame. Within the category of procedural misconceptions, the probability of both to blame is about 10%. It means the prevailing BKT method is logically correct for 10% of the wrong response. No matter how sophisticated the BKT model evolves, if the data are seriously compromised, the analysis is likely to be far from truth.

Table 2
  K1 is to blame K2 is to blame Both
Q2 28% 60% 12%
Q3 6% 87% 7%

 

In addition to better data quality, the vector of diagnoses enables the HMM models to do a better job in forming learner type cluster. Table 3 is the observation matrix of the 3 state BKT model. It is almost impossible to interpret what each state means. Table 4 is the observation matrix of the 3 state BDT model, one can easily name the three clusters: who skip, who slip and who master.

Table 3
  K1 K2
State 1 93% 97%
State 2 10% 13%
State 3 2% 2%
Table 4
    State1 State2 State3
K1 Right 96.6% 68.5% 38.5%
Wrong Formula 0.6% 4.3% 6.8%
Flawed Execution 0.2% 3.4% 7.4%
Give-up 0.2% 5.5% 22.1%
No Diagnosis 2.3% 18.2% 25.1%
K2 Right 93.9% 43.2% 33.9%
No Multiplication 4.4% 36.7% 12.3%
Mistake for Addition 0.6% 1.3% 1.7%
Give-up 0.0% 0.9% 39.5%
No Diagnosis 1.1% 17.9% 12.7%

Table 5 are the transition matrix, or the learning process. BDT model only allow for adjacent

Table 5-1
P1 State 1 State 2 State 3
State 1 91.8% 8.2%
State 2 38.6% 38.8% 22.6%
State 3 52.8% 47.2%
Table 5-2
P2 State 1 State 2 State 3
State 1 58.9% 41.1%
State 2 16.4% 60.4% 23.2%
State 3 67% 33%

 

                                                                                                                                          V.       Evidence of Potential Impacts

There are two potential productive application of the BDT model. For one thing, it makes the latent states much easier to interpret and communicate. This is essential for human tutors when interfacing with an ITS. They often complain that a probability statement of mastery is either mysterious or meaningless. For another thing, authors believe that different diagnosis shall lead to different pedagogical interventions.

                                                                                                                                                                  VI.      Summary

The Bayesian Diagnosis Tracing model solves the blaming problem in the context of the mastery tracing. The paper provides some evidence on its benefit, and some of its practical limitations. This paper only scratch the surface of the work can be done and needs to be done. For one thing, how much more effective the BDT driven intelligent tutor is compared to the current system remains to be see. While we have strong faith in its accuracy, it is expensive and risky to build solution-tree-diagnosis compatible assessment content inventory and state-based teaching and practicing material. Whether it is commercially viable remains in doubt. For another thing, the BDT framework needs to be extended to handle the multiple diagnoses. In principle, since the likelihood function can be explicitly written, the parameters can be estimated with MCMC algorithm. However, the computation complexity of real dataset and convergence quality of the resulted parameters needs to be examined.

References
  • De La Torre, Jimmy. “The generalized DINA model framework.” Psychometrika 76.2 (2011): 179-199
  • Piech, Chris, et al. “Deep knowledge tracing.”Advances in neural information processing systems. 2015.
  • Corbett, Albert T., and John R. Anderson. “Knowledge tracing: Modeling the acquisition of procedural knowledge.” User modeling and user-adapted interaction 4.4 (1994): 253-278.
  • VanLehn, K. (1990). Mind bugs: The origins of procedural misconceptions. MIT press.

 

 

 

[[1]] In the classical BKT framework, not all wrong responses are created equal. The wrong answer means incompetency for the non-mastery state while it means careless for the mastery student. This metaphor runs into trouble when there are three latent states.

[[2]] As demonstrated in the application section, incorrect reasoning branch may produce correct answer if the problem is poorly designed. Therefore, the branch of the solution tree is categorized by its reasoning process rather than the answer it produces.

[[3]] The complexity of calculation is ignored in this definition. Chinese pedagogical experts generally disagree with this simplification. However, from the perspective diagnosis, computational error can be handled separately from the mathematical modeling. In fact, if the error is attributed to calculation error, the solution blame none of the components.

[[4]] This definition is not very precise because a novel application context challenges a learner’s creativity. However, it is not clear where the line shall be drawn in the sand.

[[5]] If the parameter is not well crafted, multiple branches produce the same answer. This paper picks a branch that is favored by a human expert by experience.

[[6]] In practice, it means order the knowledge components on the solution tree is irrelevant. It is not always true.

[[7]] The origin of this error can be either (L+W)*2 but forgetting the parenthesis or L*2+W*2 but forgetting the last 2.

[[8]] It can be debated whether the student does not remember the circumference formula, or the student forget to complete the calculation. Here we chalk it up flawed execution

[[9]] Because a student uses a classical 4*3 number pad interface, students type in a number then submit without thinking. Since the student faces almost no punishment in answering an item wrong, the phenomena of “without thinking fastidiously” is obvious.

[[10]] 28+15 = 33

[[11]] For a few answers, the paper also treats typing error as calculation error. For example, 421 for Q1 is likely to be the result of student accidentally typed extra “1” after the correct answer 42. These cases are rare.

信息经济时代的教育方法论

信息经济时代的教育应该注重自主学习能力,注重单一方向的学习深度。

为实现这种教育目标,教学方法需要从现在的高度标准化的教学向技术辅助下的个性化教学转变。标准化教学内容可以由网络完成,而非标准化的内容则由老师在数据支持下完成言传身教。

实现这种教育方法的技术条件已经接近成熟,更大的挑战是创造能够在经济上支持这种教学方式的教育机构。

I.为什么要我们要学代数?

【如果你忘了什么叫代数,比如x^2-y^2 = (x-y)(x+y)就是一个例子】

  • 回答一:不学代数就找不到好工作

绝大多数工作,其实跟代数没有什么(直接)关系。拿所谓的“需要对数字有感觉的”的热门行业举例。有多少投行人士天天在那儿做因式分解?有多少咨询专家天天在那儿解多元方程组?在他们99%的工作中,所应用的数学知识不会超过4位数以下的加减乘除。其他社科人文行业就更不用说了。无间道会是一本不那么精彩的电影,如果梁朝伟在天台拿枪指着刘德华的脑袋说,“对不起,这个局面比是一个 b^2-4ac<0的一元二次方程”。
许多好工作需要代数,但是更多的好工作不需要代数。为什么学生应该把大把时间砸在一个小概率事件上?

  • 回答二:其实生活中许多地方都用到代数

有看官会反驳说:代数在我们生活中处处都存在;你看不到它的直接应用,不代表它不在起作用。

我同意。但是出来混江湖不懂的事情太多了,多它一个不多。我不懂HTML语言是怎么机器编译的,这不妨碍我用wordpress传播我的谬论。看官大概也不懂什么HTML是个啥,这不妨碍你用浏览器看到我的谬论。我敢打赌说,普通人遇到HTML语言的概率要比他遇到代数的概率高得多,为什么HTML语言不在高中必修大纲里?

  • 回答三:代数帮助我们锻炼抽象思维

在数学上小有成就的看官可能会说,其实初高中数学的确没什么用,但是抽象思维很重要。因式分解的具象表示有无限多种,但是被一个有限的公式就表现出来了,用有限表示无限,这是多么多么NB的一件事情。(一般两个nerd说到这儿,顿有一谈倾心,相见恨晚之感。)

如果老师花了这许多口水,学生流了这许多汗水,真的能让学生掌握“化繁为简,融会贯通”的功夫,的确不是一桩糟糕的买卖。但是实际上有多少高中生走出校门时回首自己的代数学习生涯说“我不会为自己的碌碌无为而悔恨,因为我学到了抽象思维”?实在是太少了。


所以这个问题最诚实的答案是:绝大多数人都不用学代数。那么同理:

为什么要逼他们学牛顿力学定律?

为什么要逼他们学酸碱反应?

为什么要逼他们学有丝分裂?

为什么要逼他们学太阳高度角?

为什么要逼他们学唯物辩证法?

为什么要逼他们记秦朝灭亡的历史意义?

为什么要逼他们学虚拟语气?

为什么要逼他们背《陋室铭》?

II. 现代教学方法的历史路径依赖

要理解现代基础教育“什么都教,什么都不教精”的特色,就要理解其历史演化的路径。

从历史文献中看,古典教育都是高度个性化的学徒制。第一个特点是跨度大。亚历山大不仅要习武,而且还要学习逻辑和修辞。而周朝的贵族们则要习六艺(礼、乐、射、御、书、数),上得厅堂,下得战场。第二个特点是标准化程度低,怎么教完全取决于老师的风格和判断。比如说,禅宗有“世尊拈花,迦叶微笑”这样“教外别传、不立文字”的传统,柏拉图学派却讲求从演讲和辩论中学习。低标准化的好处就是可以依据学生的性格和处境进行高度个性化定制,这在《论语》中多有表现。这种学徒制的好处是“名师出高徒”,有利于培养少数精锐的高素质人才。所以到今天,博士教育依然走的是学徒制的路子。

但是到了大约唐朝,古典教育开始土崩瓦解。在东方,科举制塑造了私塾体制;而在西方,正规教育被经院哲学牢牢把持着。说白了,这两种教育都是一种职业教育,前者为了培养官僚,后者为了培养神父。因为教育内容的跨度变小了,教材变得高度标准化。虽然所奉的经典不同,但是就“死读书、读死书”这一点而言,两者区别不大。因为真理是唯一的,且真理都在书上。老师怎么教差别不大,言传身教就也就失去了意义。教育的主要目的不再是学习思维方式,而是习得知识。韩愈要鼓吹“传道授业解惑”的排序,恰恰说明那时的老师们并没有什么“传道”的精神。

基于职业的标准化教育在普鲁士终于开花结果。普鲁士普及“义务教育”的初衷是培养国民对于“国家”的臣服和忠诚。要实现国民教育,首先要降低教育的成本。降低成本最快的办法就是标准化,不仅是教材的标准化,而且是教育时间的标准化(不可能养一群老贡生)。一旦变成国民教育,就不能像把内容局限在经典文献,毕竟不是每个人都能去做牧师主教的;既然鬼知道他们以后会要干嘛,就只能面面俱到,什么都教一点,寄希望于他们到了工作岗位上再“干中学”了。在工业革命初期,这不是一个糟糕的主意。因为工厂工作大多数是“重复劳动”(routine job),并不需要太多知识和创造力。总而言之,“高标准化、大跨度、低成本”的普鲁士模式在工业革命时期的经济模式中是异常有效的创新。


但是信息时代的经济模式已经与工业革命大相径庭了。那些高度标准化的“重复劳动”工作岗位已经或者即将被机器和算法取代。这有两个后果:

(1)更多的工作并不发生在生产一线,而是难以标准化的设计、管理、营销。这些工作需要创新,决策和沟通。

(2)生产一线的工人也不再是卓别林式的“人力组装机”,而是操纵和维护精密复杂仪器的技术工程师,需要在这个技术领域有非常高的造诣。

(3)由于旧职业的消亡和新职业的兴起,正常的职业流转速度会大大提高,并且不会随着年龄的增加而降低。今天40岁的美国人,65%在从事在他们高中毕业时根本不存在的工作。举个简单的例子,今天编写app的大部分程序员,在他们高中毕业时地球上还没有app这个东西。

这对于教育提出了两个要求:

(1)非智力能力(non-cognitive skill)的培养需要“教外别传、不立文字”式的言传身教,其生产方程的人力资本的投入比例很高。换言之,师生比可能需要大幅下降至个位数。

(2)学校的教学深度和企业的使用深度之间的差距需要大幅缩小,这就需要高中课程的深度大幅提高。比尔·盖茨在12岁开始编程可能是传奇,但是10后的孩子如果12岁还没有开始接触编程可能就“输在了起跑线”上。这样等他们到了大学毕业时都能达到现在所谓“全栈工程师”(full stack engineer)的标准。

(3)终身学习的习惯和自驱动学习能力将会成为最重要的教学目标。由于基础教育完全无法预测未来的知识需求,最保险的办法就是教授孩子如何Google的技能。

总之,“高标准化、大跨度、低深度”的普鲁士式工厂教育不再符合信息经济时代的教育需要。信息经济时代的教学方法论会再度回归到古典教育的学徒制中去。

信息经济时代的混合教育法

学徒制的教学法是一种非常昂贵的人力资源生产方式。互联网和机器学习在过去半个世纪的进展也只是大幅降低了标准化教学的成本,而标准化教学在学习过程中的比重将越来越小。考虑到学生的投入(主要是时间投入)如果没有达到极限,也很接近这个值了。教育生产效率提高将主要来自教师效率的提高,具体来说

(1)对于可标准化的教学内容,利用网络降低实现成本;

(2)对于不可标准化的教学内容,利用数据提高教师效率。

 标准化教学和网络教育

首先, 什么是标准化的教学内容?100%的标准化是不存在的。首先许多内容不能标准化比如讲原子结构,到底讲多深?要不要提到量子力学?,其次,即使内容可以标准化,教学方法也无法标准化。比如,同样是讲一元二次方程的求根公式,讲法也有不同。因此标准化提供了一系列局部最优的解决方案。一元二次的求根公式可能一个版本不够,但是四个版本够不够?十个版本够不够?考虑到学生的数量,十个版本已经是高度标准化了。通过流媒体技术将标准化的教材向外传播是一个已经被解决的技术问题。

 

标准化的好处是极大提高教学的最低水平。不是让1万个水平层次不齐的老师各行其道,现在是由一个高水平老师以一个较优的方式统一教授。如果你考虑到农村教师可能只有初中学历,民工子弟学校教师只有高中学历,二三线城市高中老师只有(非211)本专科学历,由一个芝加哥大学博士来讲数学或者化学是一个质的飞跃。的确,芝加哥大学的博士可能教的比北京四中、人大附中的名师要差,但是中国99%的学生都不是北四中、人大附的名师教的。他们虽然得不到最优,但是至少他们有次优。

标准化的另一个好处将极大降低教学革新的扩散成本。如果一个老师革新了,他只能影响自己的学生和同僚;如果别人不知道他的创新,也就没法办法在他的基础上继续创新。这些悲剧的根源就是传统教学模式的扩散成本太高。但是,网络教育的传播成本极低,我们可以不断调整教学内容、改进教学方法。任何革新都将被永久保存下来并且立即向所有人传播。这就意味着网络教育会变得越来越好,而分享这一改善的成本却几乎为0。


非标准化教学和数据挖掘

更加重要且更加激动人心的创新将来自于将数据分析应用于非标准化教学领域。

肯·罗宾森爵士将学校形象地比喻为“医院”,将教学分为“诊断”和“治疗”两个环节。顺着这个比喻往下讲,数据分析(或者说学习科学)可以做的是两件事:第一是提供诊断信息,即告诉教师学生哪儿有问题,问题有多严重;第二是评价治疗方案的有效性,即告诉教师各种教学法的效果。

用教育学的专业术语讲,诊断包括形成性评价(formative assessment)和终结性评价(terminal assessment)。期末考是终结性评价,其目标是评估学习者的阶段性成就,几乎与教学设计无关;随堂练是形成性评价,其目标是实时追踪学生的掌握情况,从而为下一阶段教学做准备。利用做题记录和其他学习行为进行低成本、高保真的形成性评价是数据科学可以解决的问题。其实诊断的核心技术问题已经取得了突破性的进展(早在20年前就突破了),但是现在的问题是如何让一线医生(即老师)看懂这些诊断报告。核磁共振的确大大提高了体内造影的能力,但是要是医生看不懂也是白搭。

数据对教育的第二个重要影响就是教育效果评估。教学效果的经验评估一直是教育研究的软肋。美国教育界在本世纪初时受到发展经济学的鼓励和启发,越来越重视教育创新的高质量实践验证。“啥有效结算司”(what works clearing house)就是在这个环境下产生的类似于美国食品药品管理局(FDA)的重要制度创新。随着智能设备和感应器的进一步普及,教育数据的搜集会越来越普及;因此进行“小而美”教育实验会越来越便宜,检验具体教学法的成本也会越来越低,速度也会越来越快。

因此,请假想下述的教育场景:

学生们在各自的智能终端上学习,他们的进度被实时汇报在教师的抬头显示器上(类似于Google Glass)。抬头显示器报警说小明卡在了“一元二次方程的一般解”这个知识点上,老师可以查看所有这个知识点的练习题或者互动app,各自都带着教学效果评估。老师可以为小明推送一个最适合练习,在第一时间消灭盲点;与此同时,他可以去帮助小红答疑,因为数据显示小红在两个额外教学包之后都不理解一元二次方程的图像。

这并不是科幻小说。实现这个场景的硬件和软件设备都已经到位了。现在需要的是一个愿意尝试这种场景的教育机构。

NOTE:撰写于2015年

目标体系和自适应算法:基于掌握学习理论的理解

1.学习分析算法和目标体系

学习分析算法(learning analytics)就干一件事,那就是算一个事件发生的概率。核心问题在于,什么事件有计算其概率的价值?

对于这个问题的任何答案都是一个目标体系。如果我们认为做对某个技能(e.g.听说读写)的题是有价值的事件,那么这就是ETS式的能力目标体系。如果我们认为做对某个知识点的题是有价值的事件,那么这就是Duolingo式的知识点目标体系( 中国考纲体系也是如此)。

反过来说,如果没有一个目标体系,学习分析就如同盲人摸象,只见树木而不见森林,导致分析价值大大降低。
因此,目标体系和学习分析算法是一个硬币的两面。

2.自适应学习和目标体系

自适应学习的核心问题是“适应什么”(adapt to what)?一般来说它有两个对象:学习的速度和学习的难度。

学习速度对于目标体系的依赖是显而意见的。速度=”位移”/时间,而衡量”位移”需要目标体系的标尺。看到什么样的证据可以说学生掌握了某项技能/知识点,完全取决于目标体系的规定。就像在高速公路上测速,没有标尺你还搞个毛。

学习难度对于目标体系的依赖就不那么明显了。对于某个学生而言,每一道具体题目的难度是不依赖于目标体系的。但是这道题是否需要做就依赖于目标体系。因此任何基于难度的教学方案都不可能脱离目标体系。举个极端例子,我给家长20万题,并且告诉家长你家孩子对每道题上的解答概率,家长有办法制定一个合理计划么?不能,因为他不知道自己家的孩子到底要学啥。

如果考察真正的自适应学习系统(Khan Academy,Coursera,Aleks,Knewton),不一定每一个系统都有算法支持,但是他们一定都有一个目标体系。

因此,目标体系和自适应学习也是一个硬币的两面。

3.目标体系和教学设计

基于目标体系的教学设计可以被用于日常教学的提高,因为目标体系侧重于高频的形成性测试。在此基础上可以想象许多教学场景:

(1)早期预警
当学生出现严重晚于目标体系预期的进度,可以加入早期预警体系,及时提醒老师和家长进行干预。而不用等到期末考拿了鸭蛋再回家打屁股。

(2)攻坚战
当某个班级出现系统性的进度延缓时,可以进入攻坚战模式。我们可以向老师推荐适宜的教学案例,练习题或者其他教学资源。
如果某个单元系统性地进入攻坚战模式,在数据不足的班级或者未来的教学中可以向老师提供proactive预警和推荐。

(3)自驱动学习
对于学生而言,一旦有了目标体系,学生的学习进度可以脱离全班进度。学生可以自主学习,同时满足老师或者学校的教学要求。在没有目标体系的情况下,这是不可能实现的。

继续阅读“目标体系和自适应算法:基于掌握学习理论的理解”

全栈数据工程师:从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检验绝不是把样本五五开这么简单。

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

这篇文章将介绍两种自适应学习方案:“知识点间”(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)与其说是一个技术问题,不如说是一个教学问题。笔者认为,推荐逻辑应该由“测评-教学”的两步循环来构成。在测评环节,练习推荐侧重于题目的区分度和测量精度,从而区分用户的不同类型;在教学环节,根据学生类型,练习推荐侧重于题目的教学效果。在下一个测评环境,练习推荐再测试学生的水平和类型,如此循环往复,直到学生达到指定的熟练程度为止。

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