假期时间我研读了kaggle冠军代码，12年举行的nlp比赛。才疏学浅，如果有所需要改正的地方，望各位多多指正。
概要
Autograder是来自美国的 Luis Tandalla在比赛（Automated Student Assessment Prize, Phase Two – Short Answer Scoring）中实现的程序。Autograder选择了解决short-answer responses这个题目。选手使用了relevant,words,bigrams,probabilities作为数据模型，把score1和score2拆分成了两个record,使用随机森林来进行训练，分数是：0.77166，排名第一。
问题背景
在教育实践中，为了培养学生的批判性思维，测验往往会出一些开放性的题目让学生补充。但是不得不需要大量的人工和精力去批改这些题目。为了解决这个难题，需要编写一个软件可以自动评估学生的答案来降低成本。
算法分析
Github地址：https://github.com/luistp001/LT-Autograder
在机器学习中，有两个关键，一个是模型的确立。一个是算法的选择。我根据这两个重点对LT-Autograder进行分析。
一、模型的确立
在模型确立之前，需要把短文的特征提取出来。但是短文存在非字母和数字的字符，大小写，还有一些拼写错误的问题。选手编写了一个修改拼写错误的类correct2(基于http://norvig.com/big.txt)。为了方便后面的特征选择，选择使用了PorterStemmer去掉后缀，获取单词的核心。
1. 数据预处理
由于短文中有单词，组合和三元组这几类的分别，选手编写一个a_essay函数用于把短文划分为这几类。（边幅问题，就不展开了）
2. 使用正则表达式来寻找可能的答案
划分了单词，词组和三元词组之后，选手有一个优化点可以很好地提高performance的。就是使用正则表达式来匹配答案来寻找可能的答案。因为short problem中，其实往往答案只需要关注几个关键字（我们人工批改的时候其实往往也如此，针对关键字改分）。举个例子, 在第一个问题中：
可能的答案有这么几个。
• You need to know how much vinegar was used in each container.
• You need to know what type of vinegar was used in each container.
• You need to know what materials to test.
• You need to know what size/surface area of materials should be used.
• You need to know how long each sample was rinsed in distilled water.
• You need to know what drying method to use.
• You need to know what size/type of container to use.
关键字其实就是type of vinegar，kind of vinegar等等，截取其中一段代码来表示如何匹配。
pats.append( re.compile(r"(\w+ ){0,4}\w*(how )?((much)|(mani)) (\w+ ){0,4}((vinegar)|(finger)|(liquid))\w*( \w+){0,4}") )
pats.append( re.compile(r"(\w+ ){0,4}\w*how much (\w+ ){1,2}((put)|(fill))\w*( \w+){0,4}") )
pats.append( re.compile(r"(\w+ ){0,4}\w*((vinegar)|(finger)) (\w+ ){0,4}measur\w*( \w+){0,4}") )
pats.append( re.compile(r"(\w+ ){0,4}\w*((aunt)|(man)|(a?mount)|(measur)|(volum)|(quantiti)) (\w+ ){0,3}((vinegar)|(finger)|(liquid))\w*( \w+){0,4}") )
然后选手就会根据这些正规表达式陪寻找短文中是否匹配的回答。如果匹配则用1表示，否则用0表示。得出来的匹配向量将作为特征向量使用随机森林训练。
3. 计算tf-idf
tf-idf（英语：term frequency–inverse document frequency）是一种用于信息检索与文本挖掘的常用加权技术。tf-idf是一种统计方法，用以评估一字词对于一个文件集或一个语料库中的其中一份文件的重要程度。字词的重要性随着它在文件中出现的次数成正比增加，但同时会随着它在语料库中出现的频率成反比下降。
然而，令我很无语的是，final代码里面使用的确实是使用tf-idf，在Luis Tandalla的论文里面却说，with raw counts确实是比tf-idf性能要好。截图为证。
4. 计算probabilities
我们通过上一步已经计算了每一个单词的tf-idf，所以我们得到标准答案和回答的tf-idf向量来分别表示标准答案和回答答案。
我们可以通过计算两个向量的余弦相似性，来得到这个回答跟标准答案的相似程度。（https://nlp.stanford.edu/IR-book/html/htmledition/document-and-query-weighting-schemes-1.html）
5. 模型确立
最终使用的模型特征有：
| Name | significance |
|---|---|
| relevant | 是一个跟标准答案有关的相关性向量 |
| words | 切分后的单词 |
| bigrams | 切分后的短语 |
| probabilities | 标准答案跟回答答案的余弦相似性 |
二、算法训练
在算法训练中，Luis Tandalla使用了随机森林和决策树进行训练。
在机器学习中，随机森林是一个包含多个决策树的分类器，并且其输出的类别是由个别树输出的类别的众数而定。 Leo Breiman和Adele Cutler发展出推论出随机森林的算法。而"Random Forests"是他们的商标。这个术语是1995年由贝尔实验室的Tin Kam Ho所提出的随机决策森林（random decision forests）而来的。这个方法则是结合Breimans的"Bootstrap aggregating"想法和Ho的"random subspace method" 以建造决策树的集合。
训练代码
Rscript modelingRf.R
Rscript modelingGbm.R
就像简介所说，Luis Tandalla使用了第二个成绩（第二个成绩我一开始看题目的时候十分蒙蔽），把第二个成绩独立拆分成一个独立的record进行训练。
# 随机森林
tr2 <- correct(tr, double_data) # It doubles the training data
#It trains rf
rf <- randomForest( form, data = tr2, ntree = ntrees, do.trace = FALSE, importance = TRUE)
save( models, file = paste( '../newTrainedModelFiles/models_', actual, '.RData', sep="" ) )
# Gradient Boosting Machine
tr2 <- correct(tr, double_data) # It doubles the training data
#It trains gbm
gbm1 <- gbm( form, data = tr2, n.trees = ntrees, distribution = 'gaussian' , interaction.depth = ide, shrinkage = sh, bag.fraction = tf, train.fraction = 1.0, cv.folds=ncvt , keep.data = TRUE, verbose = FALSE)
best.iter <- gbm.perf(gbm1,method="cv", plot.it = FALSE)
save( models, file = paste( '../newTrainedModelFiles/models_', actual, '.RData', sep="" ) )
随机森林：
https://zh.wikipedia.org/wiki/%E9%9A%8F%E6%9C%BA%E6%A3%AE%E6%9E%97
研究心得
在机器学习中，写好了baseline程序，其实大部分时间都在做对数据的预处理和不断优化模型。在Autograder的程序中，我们可以看到，对数据的预处理和一些模型的优化，选手用了大量的时间进行处理。而在nlp中，这些处理方式也是值得我们学习的（我对nlp不熟悉，或许有更多更好的处理方法）。
关于使用神经网络算法的问题。虽然我只是接触和使用过简单的bp神经网络，
个人觉得，如果不改动模型的话，一般的神经网络（输入层，隐藏层，输出层）训练时间过长，效果也不见得很好。后面翻阅Luis Tandalla的论文，其实当年他是试过神经网络和支持向量机来预测的，但是效果其实一般。原文如下：
I also trained Support Vector Machines and Neural Networks to predict the scores and to blend models.
They constantly produced higher cross validations kappas but lower public leaderboard kappas
但是经过翻阅资料，发现挺多在NLP的应用优化的。首先要讨论一下，冠军选手的代码的弊端。我们在得到probabilities时，其实是需要一个高纬度的向量计算，并且为了有一个好的结果，冠军选手是需要手动编写正则表达的。这样是很不利于代码的拓展性。通过了解，我们可以使用RNN来进行优化。
我这边对深度学习没有怎么了解，个人认为还是要构造词向量，如果要使算法具有一般性，可以不需要正则表达式来进行匹配答案，不过我们依然需要提取出关键的特征，可以参考Autograder提取特征的方法。
因为我们需要训练出一个可以评估语义并且进行给分的模型，因为暂时能力有限，我会选择LSTM模型吧。(不太了解)
结语（待续）
由于对R不熟悉，一开始看R代码的时候有点小蒙蔽。python的那段代码，我每一行进行断点研究，所以对预处理的那几端代码应该说是掌握到精髓了（个人认为，其实数据预处理十分重要，有时候比模型，算法更重要）。至于改进和优化，我能力有限，之前只是做个一个简单的神经网络评价模型，跟nlp相比，难度差距太大。不过如有有机会，我觉得深入下去也不会花太多的时间，我会继续深入。
